xref: /llvm-project/llvm/test/Transforms/InstCombine/infinite-loop-postdom.ll (revision 8df17b4dc12292cd7adc9c46a5bd75b8db26d49e) 
1; RUN: opt < %s -disable-output -branch-prob -instcombine -block-freq -verify-dom-info
2; RUN: opt < %s -postdomtree -analyze -enable-new-pm=0 | FileCheck --check-prefixes=CHECK-POSTDOM %s
3; RUN: opt < %s -passes='print<postdomtree>' 2>&1 | FileCheck --check-prefixes=CHECK-POSTDOM %s
4
5; Demonstrate that Predicate Canonicalization (InstCombine) does not invalidate PostDomTree
6; if the basic block is post-dom unreachable.
7
8define void @test1(i24 %a, i24 %b) {
9entry:
10  br label %LOOP
11
12LOOP:
13  %f = icmp uge i24 %a, %b
14  br i1 %f, label %B1, label %B2
15
16B1:
17  %x = add i24 %a, %b
18  br label %B2
19
20B2:
21  br label %LOOP
22}
23
24; The same as @test1 except the LOOP condition canonicalized (as by instcombine).
25define void @test1-canonicalized(i24 %a, i24 %b) {
26entry:
27  br label %LOOP
28
29LOOP:
30  %f.not = icmp ult i24 %a, %b
31  br i1 %f.not, label %B2, label %B1
32
33B1:
34  %x = add i24 %a, %b
35  br label %B2
36
37B2:
38  br label %LOOP
39}
40
41; The same as @test1 but different order of B1 and B2 in the function.
42; The different order makes PostDomTree different in presense of postdom
43; unreachable blocks.
44define void @test2(i24 %a, i24 %b) {
45entry:
46  br label %LOOP
47
48LOOP:
49  %f = icmp uge i24 %a, %b
50  br i1 %f, label %B1, label %B2
51
52B2:
53  br label %LOOP
54
55B1:
56  %x = add i24 %a, %b
57  br label %B2
58}
59
60; The same as @test2 except the LOOP condition canonicalized (as by instcombine).
61define void @test2-canonicalized(i24 %a, i24 %b) {
62entry:
63  br label %LOOP
64
65LOOP:
66  %f.not = icmp ult i24 %a, %b
67  br i1 %f.not, label %B2, label %B1
68
69B2:
70  br label %LOOP
71
72B1:
73  %x = add i24 %a, %b
74  br label %B2
75}
76
77; Two reverse unreachable subgraphs with RU1* and RU2* basic blocks respectively.
78define void @test3(i24 %a, i24 %b, i32 %flag) {
79entry:
80  switch i32 %flag, label %EXIT [
81    i32 1, label %RU1
82    i32 2, label %RU2
83    i32 3, label %RU2_B1
84  ]
85
86RU1:
87  %f = icmp uge i24 %a, %b
88  br label %RU1_LOOP
89
90RU1_LOOP:
91  br i1 %f, label %RU1_B1, label %RU1_B2
92
93RU1_B1:
94  %x = add i24 %a, %b
95  br label %RU1_B2
96
97RU1_B2:
98  br label %RU1_LOOP
99
100RU2:
101  %f2 = icmp uge i24 %a, %b
102  br i1 %f2, label %RU2_B1, label %RU2_B2
103
104RU2_B1:
105  br label %RU2_B2
106
107RU2_B2:
108  br label %RU2_B1
109
110EXIT:
111  ret void
112}
113
114; The same as @test3 except the icmp conditions are canonicalized (as by instcombine).
115define void @test3-canonicalized(i24 %a, i24 %b, i32 %flag) {
116entry:
117  switch i32 %flag, label %EXIT [
118    i32 1, label %RU1
119    i32 2, label %RU2
120    i32 3, label %RU2_B1
121  ]
122
123RU1:
124  %f.not = icmp ult i24 %a, %b
125  br label %RU1_LOOP
126
127RU1_LOOP:
128  br i1 %f.not, label %RU1_B2, label %RU1_B1
129
130RU1_B1:
131  %x = add i24 %a, %b
132  br label %RU1_B2
133
134RU1_B2:
135  br label %RU1_LOOP
136
137RU2:
138  %f2.not = icmp ult i24 %a, %b
139  br i1 %f2.not, label %RU2_B2, label %RU2_B1
140
141RU2_B1:
142  br label %RU2_B2
143
144RU2_B2:
145  br label %RU2_B1
146
147EXIT:
148  ret void
149}
150
151; PostDomTrees of @test1(), @test2() and @test3() are different.
152; PostDomTrees of @testX() and @testX-canonicalize() are the same.
153
154; CHECK-POSTDOM-LABEL: test1
155; CHECK-POSTDOM-NEXT: =============================--------------------------------
156; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
157; CHECK-POSTDOM-NEXT:   [1]  <<exit node>>
158; CHECK-POSTDOM-NEXT:     [2] %B1
159; CHECK-POSTDOM-NEXT:       [3] %LOOP
160; CHECK-POSTDOM-NEXT:         [4] %entry
161; CHECK-POSTDOM-NEXT:         [4] %B2
162; CHECK-POSTDOM-NEXT: Roots: %B1
163
164; CHECK-POSTDOM-LABEL: test1-canonicalized
165; CHECK-POSTDOM-NEXT: =============================--------------------------------
166; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
167; CHECK-POSTDOM-NEXT:   [1]  <<exit node>>
168; CHECK-POSTDOM-NEXT:     [2] %B1
169; CHECK-POSTDOM-NEXT:       [3] %LOOP
170; CHECK-POSTDOM-NEXT:         [4] %entry
171; CHECK-POSTDOM-NEXT:         [4] %B2
172; CHECK-POSTDOM-NEXT: Roots: %B1
173
174; CHECK-POSTDOM-LABEL: test2
175; CHECK-POSTDOM-NEXT: =============================--------------------------------
176; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
177; CHECK-POSTDOM-NEXT:   [1]  <<exit node>>
178; CHECK-POSTDOM-NEXT:     [2] %B2
179; CHECK-POSTDOM-NEXT:       [3] %LOOP
180; CHECK-POSTDOM-NEXT:         [4] %entry
181; CHECK-POSTDOM-NEXT:       [3] %B1
182; CHECK-POSTDOM-NEXT: Roots: %B2
183
184; CHECK-POSTDOM-LABEL: test2-canonicalized
185; CHECK-POSTDOM-NEXT: =============================--------------------------------
186; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
187; CHECK-POSTDOM-NEXT:   [1]  <<exit node>>
188; CHECK-POSTDOM-NEXT:     [2] %B2
189; CHECK-POSTDOM-NEXT:       [3] %LOOP
190; CHECK-POSTDOM-NEXT:         [4] %entry
191; CHECK-POSTDOM-NEXT:       [3] %B1
192; CHECK-POSTDOM-NEXT: Roots: %B2
193
194; CHECK-POSTDOM-LABEL: test3
195; CHECK-POSTDOM-NEXT:=============================--------------------------------
196; CHECK-POSTDOM-NEXT:Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
197; CHECK-POSTDOM-NEXT:  [1]  <<exit node>>
198; CHECK-POSTDOM-NEXT:    [2] %EXIT
199; CHECK-POSTDOM-NEXT:    [2] %entry
200; CHECK-POSTDOM-NEXT:    [2] %RU1_B1
201; CHECK-POSTDOM-NEXT:      [3] %RU1_LOOP
202; CHECK-POSTDOM-NEXT:        [4] %RU1
203; CHECK-POSTDOM-NEXT:        [4] %RU1_B2
204; CHECK-POSTDOM-NEXT:    [2] %RU2_B1
205; CHECK-POSTDOM-NEXT:      [3] %RU2
206; CHECK-POSTDOM-NEXT:      [3] %RU2_B2
207; CHECK-POSTDOM-NEXT:Roots: %EXIT %RU1_B1 %RU2_B1
208
209; CHECK-POSTDOM-LABEL: test3-canonicalized
210; CHECK-POSTDOM-NEXT:=============================--------------------------------
211; CHECK-POSTDOM-NEXT:Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
212; CHECK-POSTDOM-NEXT:  [1]  <<exit node>>
213; CHECK-POSTDOM-NEXT:    [2] %EXIT
214; CHECK-POSTDOM-NEXT:    [2] %entry
215; CHECK-POSTDOM-NEXT:    [2] %RU1_B1
216; CHECK-POSTDOM-NEXT:      [3] %RU1_LOOP
217; CHECK-POSTDOM-NEXT:        [4] %RU1
218; CHECK-POSTDOM-NEXT:        [4] %RU1_B2
219; CHECK-POSTDOM-NEXT:    [2] %RU2_B1
220; CHECK-POSTDOM-NEXT:      [3] %RU2
221; CHECK-POSTDOM-NEXT:      [3] %RU2_B2
222; CHECK-POSTDOM-NEXT:Roots: %EXIT %RU1_B1 %RU2_B1
223