[sanitizer] Improve FreeBSD ASLR detection
[llvm-project.git] / llvm / test / Transforms / StructurizeCFG / interleaved-loop-order.ll
blob3cca3c90212c8340d50422d3147e4e9134a37e26
1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2 ; RUN: opt -S -lowerswitch -structurizecfg %s -o - | FileCheck %s
4 ; This test have an outer loop containing an inner loop,
5 ; for which there is an interleaved post-order traversal.
7 ; This used to produce incorrect code.
8 ; For example %outer.loop.body used to branched to %inner.loop.end
9 ; (instead of %inner.loop.header).
11 define i1 @test_nested(i32 %x, i1 %b1, i1 %b2, i1 %b3) {
12 ; CHECK-LABEL: @test_nested(
13 ; CHECK-NEXT:  entry:
14 ; CHECK-NEXT:    [[B3_INV:%.*]] = xor i1 [[B3:%.*]], true
15 ; CHECK-NEXT:    br label [[OUTER_LOOP_HEADER:%.*]]
16 ; CHECK:       Flow12:
17 ; CHECK-NEXT:    br i1 [[TMP3:%.*]], label [[EXIT_TRUE:%.*]], label [[FLOW13:%.*]]
18 ; CHECK:       exit.true:
19 ; CHECK-NEXT:    br label [[FLOW13]]
20 ; CHECK:       Flow13:
21 ; CHECK-NEXT:    br i1 [[TMP2:%.*]], label [[NEWDEFAULT:%.*]], label [[FLOW14:%.*]]
22 ; CHECK:       NewDefault:
23 ; CHECK-NEXT:    br label [[EXIT_FALSE:%.*]]
24 ; CHECK:       Flow14:
25 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, [[EXIT_FALSE]] ], [ true, [[FLOW13]] ]
26 ; CHECK-NEXT:    br label [[EXIT:%.*]]
27 ; CHECK:       exit.false:
28 ; CHECK-NEXT:    br label [[FLOW14]]
29 ; CHECK:       outer.loop.header:
30 ; CHECK-NEXT:    br i1 [[B1:%.*]], label [[OUTER_LOOP_BODY:%.*]], label [[FLOW3:%.*]]
31 ; CHECK:       outer.loop.body:
32 ; CHECK-NEXT:    br label [[INNER_LOOP_HEADER:%.*]]
33 ; CHECK:       Flow3:
34 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP16:%.*]], [[FLOW11:%.*]] ], [ true, [[OUTER_LOOP_HEADER]] ]
35 ; CHECK-NEXT:    [[TMP2]] = phi i1 [ [[TMP12:%.*]], [[FLOW11]] ], [ false, [[OUTER_LOOP_HEADER]] ]
36 ; CHECK-NEXT:    [[TMP3]] = phi i1 [ false, [[FLOW11]] ], [ true, [[OUTER_LOOP_HEADER]] ]
37 ; CHECK-NEXT:    br i1 [[TMP1]], label [[FLOW12:%.*]], label [[OUTER_LOOP_HEADER]]
38 ; CHECK:       inner.loop.header:
39 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[TMP8:%.*]], [[FLOW4:%.*]] ], [ false, [[OUTER_LOOP_BODY]] ]
40 ; CHECK-NEXT:    br i1 [[B2:%.*]], label [[INNER_LOOP_BODY:%.*]], label [[FLOW4]]
41 ; CHECK:       Flow6:
42 ; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ false, [[INNER_LOOP_LATCH:%.*]] ], [ true, [[LEAFBLOCK:%.*]] ]
43 ; CHECK-NEXT:    br label [[FLOW5:%.*]]
44 ; CHECK:       Flow7:
45 ; CHECK-NEXT:    br i1 [[TMP10:%.*]], label [[INNER_LOOP_END:%.*]], label [[FLOW8:%.*]]
46 ; CHECK:       inner.loop.end:
47 ; CHECK-NEXT:    br label [[FLOW8]]
48 ; CHECK:       inner.loop.body:
49 ; CHECK-NEXT:    br i1 [[B3_INV]], label [[INNER_LOOP_BODY_ELSE:%.*]], label [[FLOW:%.*]]
50 ; CHECK:       inner.loop.body.else:
51 ; CHECK-NEXT:    br label [[FLOW]]
52 ; CHECK:       Flow:
53 ; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ false, [[INNER_LOOP_BODY_ELSE]] ], [ true, [[INNER_LOOP_BODY]] ]
54 ; CHECK-NEXT:    br i1 [[TMP6]], label [[INNER_LOOP_BODY_THEN:%.*]], label [[INNER_LOOP_COND:%.*]]
55 ; CHECK:       inner.loop.body.then:
56 ; CHECK-NEXT:    br label [[INNER_LOOP_COND]]
57 ; CHECK:       Flow4:
58 ; CHECK-NEXT:    [[TMP7:%.*]] = phi i1 [ [[TMP17:%.*]], [[FLOW5]] ], [ true, [[INNER_LOOP_HEADER]] ]
59 ; CHECK-NEXT:    [[TMP8]] = phi i1 [ [[TMP18:%.*]], [[FLOW5]] ], [ [[TMP4]], [[INNER_LOOP_HEADER]] ]
60 ; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ [[TMP19:%.*]], [[FLOW5]] ], [ false, [[INNER_LOOP_HEADER]] ]
61 ; CHECK-NEXT:    [[TMP10]] = phi i1 [ false, [[FLOW5]] ], [ true, [[INNER_LOOP_HEADER]] ]
62 ; CHECK-NEXT:    br i1 [[TMP7]], label [[FLOW7:%.*]], label [[INNER_LOOP_HEADER]]
63 ; CHECK:       inner.loop.cond:
64 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
65 ; CHECK:       NodeBlock:
66 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[X:%.*]], 1
67 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[LEAFBLOCK]], label [[FLOW5]]
68 ; CHECK:       Flow8:
69 ; CHECK-NEXT:    [[TMP11:%.*]] = phi i1 [ true, [[INNER_LOOP_END]] ], [ false, [[FLOW7]] ]
70 ; CHECK-NEXT:    br i1 [[TMP9]], label [[LEAFBLOCK1:%.*]], label [[FLOW9:%.*]]
71 ; CHECK:       LeafBlock1:
72 ; CHECK-NEXT:    [[SWITCHLEAF2:%.*]] = icmp eq i32 [[X]], 1
73 ; CHECK-NEXT:    br i1 [[SWITCHLEAF2]], label [[INNER_LOOP_BREAK:%.*]], label [[FLOW10:%.*]]
74 ; CHECK:       LeafBlock:
75 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[X]], 0
76 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[INNER_LOOP_LATCH]], label [[FLOW6:%.*]]
77 ; CHECK:       Flow9:
78 ; CHECK-NEXT:    [[TMP12]] = phi i1 [ [[TMP14:%.*]], [[FLOW10]] ], [ [[TMP8]], [[FLOW8]] ]
79 ; CHECK-NEXT:    [[TMP13:%.*]] = phi i1 [ [[TMP15:%.*]], [[FLOW10]] ], [ [[TMP11]], [[FLOW8]] ]
80 ; CHECK-NEXT:    br i1 [[TMP13]], label [[OUTER_LOOP_CLEANUP:%.*]], label [[FLOW11]]
81 ; CHECK:       inner.loop.break:
82 ; CHECK-NEXT:    br label [[FLOW10]]
83 ; CHECK:       Flow10:
84 ; CHECK-NEXT:    [[TMP14]] = phi i1 [ false, [[INNER_LOOP_BREAK]] ], [ true, [[LEAFBLOCK1]] ]
85 ; CHECK-NEXT:    [[TMP15]] = phi i1 [ true, [[INNER_LOOP_BREAK]] ], [ [[TMP11]], [[LEAFBLOCK1]] ]
86 ; CHECK-NEXT:    br label [[FLOW9]]
87 ; CHECK:       outer.loop.cleanup:
88 ; CHECK-NEXT:    br label [[OUTER_LOOP_LATCH:%.*]]
89 ; CHECK:       Flow11:
90 ; CHECK-NEXT:    [[TMP16]] = phi i1 [ false, [[OUTER_LOOP_LATCH]] ], [ true, [[FLOW9]] ]
91 ; CHECK-NEXT:    br label [[FLOW3]]
92 ; CHECK:       outer.loop.latch:
93 ; CHECK-NEXT:    br label [[FLOW11]]
94 ; CHECK:       Flow5:
95 ; CHECK-NEXT:    [[TMP17]] = phi i1 [ [[TMP5]], [[FLOW6]] ], [ true, [[NODEBLOCK]] ]
96 ; CHECK-NEXT:    [[TMP18]] = phi i1 [ [[TMP5]], [[FLOW6]] ], [ [[TMP4]], [[NODEBLOCK]] ]
97 ; CHECK-NEXT:    [[TMP19]] = phi i1 [ false, [[FLOW6]] ], [ true, [[NODEBLOCK]] ]
98 ; CHECK-NEXT:    br label [[FLOW4]]
99 ; CHECK:       inner.loop.latch:
100 ; CHECK-NEXT:    br label [[FLOW6]]
101 ; CHECK:       exit:
102 ; CHECK-NEXT:    ret i1 [[TMP0]]
104 entry:
105   br label %outer.loop.header
107 exit.true:                                       ; preds = %outer.loop.header
108   br label %exit
110 exit.false:                                      ; preds = %inner.loop.cond
111   br label %exit
113 outer.loop.header:                               ; preds = %outer.loop.latch, %entry
114   br i1 %b1, label %outer.loop.body, label %exit.true
116 outer.loop.body:                                 ; preds = %outer.loop.header
117   br label %inner.loop.header
119 inner.loop.header:                               ; preds = %inner.loop.latch, %outer.loop.body
120   br i1 %b2, label %inner.loop.body, label %inner.loop.end
122 inner.loop.end:                                  ; preds = %inner.loop.header
123   br label %outer.loop.cleanup
125 inner.loop.body:                                 ; preds = %inner.loop.header
126   br i1 %b3, label %inner.loop.body.then, label %inner.loop.body.else
128 inner.loop.body.else:                            ; preds = %inner.loop.body
129   br label %inner.loop.cond
131 inner.loop.body.then:                            ; preds = %inner.loop.body
132   br label %inner.loop.cond
134 inner.loop.cond:                                 ; preds = %inner.loop.body.then, %inner.loop.body.else
135   switch i32 %x, label %exit.false [
136   i32 0, label %inner.loop.latch
137   i32 1, label %inner.loop.break
138   ]
140 inner.loop.break:                                ; preds = %inner.loop.cond
141   br label %outer.loop.cleanup
143 outer.loop.cleanup:                              ; preds = %inner.loop.break, %inner.loop.end
144   br label %outer.loop.latch
146 outer.loop.latch:                                ; preds = %outer.loop.cleanup
147   br label %outer.loop.header
149 inner.loop.latch:                                ; preds = %inner.loop.cond
150   br label %inner.loop.header
152 exit:                                            ; preds = %exit.false, %exit.true
153   %r = phi i1 [ true, %exit.true ], [ false, %exit.false ]
154   ret i1 %r
157 ; This test checks sibling loops that by default have an
158 ; interleaved post-order traversal.
160 define void @test_siblings(i1 %b1, i1 %b2, i1 %b3, i1 %b4, i1 %b5, i1 %b6, i1 %b7, i1 %b8, i1 %b9) {
161 ; CHECK-LABEL: @test_siblings(
162 ; CHECK-NEXT:  entry:
163 ; CHECK-NEXT:    [[B9_INV:%.*]] = xor i1 [[B9:%.*]], true
164 ; CHECK-NEXT:    [[B6_INV:%.*]] = xor i1 [[B6:%.*]], true
165 ; CHECK-NEXT:    [[B2_INV:%.*]] = xor i1 [[B2:%.*]], true
166 ; CHECK-NEXT:    [[B8_INV:%.*]] = xor i1 [[B8:%.*]], true
167 ; CHECK-NEXT:    [[B5_INV:%.*]] = xor i1 [[B5:%.*]], true
168 ; CHECK-NEXT:    [[B3_INV:%.*]] = xor i1 [[B3:%.*]], true
169 ; CHECK-NEXT:    [[B4_INV:%.*]] = xor i1 [[B4:%.*]], true
170 ; CHECK-NEXT:    [[B1_INV:%.*]] = xor i1 [[B1:%.*]], true
171 ; CHECK-NEXT:    br i1 [[B1_INV]], label [[IF_ELSE:%.*]], label [[FLOW:%.*]]
172 ; CHECK:       if.else:
173 ; CHECK-NEXT:    br label [[FLOW]]
174 ; CHECK:       Flow:
175 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ [[TMP0]], [[FLOW1:%.*]] ], [ [[B2]], [[IF_ELSE]] ], [ false, [[ENTRY:%.*]] ]
176 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP5:%.*]], [[FLOW1]] ], [ [[B2_INV]], [[IF_ELSE]] ], [ false, [[ENTRY]] ]
177 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ false, [[FLOW1]] ], [ false, [[IF_ELSE]] ], [ true, [[ENTRY]] ]
178 ; CHECK-NEXT:    br i1 [[TMP2]], label [[LOOP1_HEADER:%.*]], label [[FLOW1]]
179 ; CHECK:       loop1.header:
180 ; CHECK-NEXT:    br i1 [[B3_INV]], label [[LOOP1_BODY:%.*]], label [[FLOW2:%.*]]
181 ; CHECK:       Flow2:
182 ; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ true, [[LOOP1_BODY]] ], [ [[TMP1]], [[LOOP1_HEADER]] ]
183 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[B5_INV]], [[LOOP1_BODY]] ], [ [[B3]], [[LOOP1_HEADER]] ]
184 ; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP1_LATCH:%.*]], label [[FLOW3:%.*]]
185 ; CHECK:       loop1.latch:
186 ; CHECK-NEXT:    br label [[FLOW3]]
187 ; CHECK:       Flow1:
188 ; CHECK-NEXT:    [[TMP5]] = phi i1 [ [[TMP6:%.*]], [[FLOW3]] ], [ [[TMP1]], [[FLOW]] ]
189 ; CHECK-NEXT:    br i1 true, label [[FLOW4:%.*]], label [[FLOW]]
190 ; CHECK:       loop1.body:
191 ; CHECK-NEXT:    br label [[FLOW2]]
192 ; CHECK:       Flow3:
193 ; CHECK-NEXT:    [[TMP6]] = phi i1 [ false, [[LOOP1_LATCH]] ], [ [[TMP3]], [[FLOW2]] ]
194 ; CHECK-NEXT:    br label [[FLOW1]]
195 ; CHECK:       Flow4:
196 ; CHECK-NEXT:    [[TMP7:%.*]] = phi i1 [ false, [[FLOW5:%.*]] ], [ [[TMP5]], [[FLOW1]] ]
197 ; CHECK-NEXT:    br i1 [[TMP7]], label [[LOOP2_HEADER:%.*]], label [[FLOW5]]
198 ; CHECK:       loop2.header:
199 ; CHECK-NEXT:    br i1 [[B6_INV]], label [[LOOP2_BODY:%.*]], label [[FLOW6:%.*]]
200 ; CHECK:       Flow5:
201 ; CHECK-NEXT:    [[TMP8:%.*]] = phi i1 [ [[TMP11:%.*]], [[FLOW7:%.*]] ], [ false, [[FLOW4]] ]
202 ; CHECK-NEXT:    br i1 true, label [[FLOW8:%.*]], label [[FLOW4]]
203 ; CHECK:       loop2.body:
204 ; CHECK-NEXT:    br label [[FLOW6]]
205 ; CHECK:       Flow6:
206 ; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ true, [[LOOP2_BODY]] ], [ false, [[LOOP2_HEADER]] ]
207 ; CHECK-NEXT:    [[TMP10:%.*]] = phi i1 [ [[B7:%.*]], [[LOOP2_BODY]] ], [ [[B6]], [[LOOP2_HEADER]] ]
208 ; CHECK-NEXT:    br i1 [[TMP10]], label [[LOOP2_LATCH:%.*]], label [[FLOW7]]
209 ; CHECK:       loop2.latch:
210 ; CHECK-NEXT:    br label [[FLOW7]]
211 ; CHECK:       Flow7:
212 ; CHECK-NEXT:    [[TMP11]] = phi i1 [ false, [[LOOP2_LATCH]] ], [ [[TMP9]], [[FLOW6]] ]
213 ; CHECK-NEXT:    br label [[FLOW5]]
214 ; CHECK:       Flow8:
215 ; CHECK-NEXT:    [[TMP12:%.*]] = phi i1 [ false, [[FLOW10:%.*]] ], [ [[TMP0]], [[FLOW5]] ]
216 ; CHECK-NEXT:    [[TMP13:%.*]] = phi i1 [ false, [[FLOW10]] ], [ [[TMP8]], [[FLOW5]] ]
217 ; CHECK-NEXT:    br i1 [[TMP13]], label [[LOOP3_HEADER:%.*]], label [[FLOW9:%.*]]
218 ; CHECK:       loop3.header:
219 ; CHECK-NEXT:    br label [[FLOW9]]
220 ; CHECK:       Flow9:
221 ; CHECK-NEXT:    [[TMP14:%.*]] = phi i1 [ true, [[LOOP3_HEADER]] ], [ [[TMP12]], [[FLOW8]] ]
222 ; CHECK-NEXT:    br i1 [[TMP14]], label [[LOOP3_LATCH:%.*]], label [[FLOW10]]
223 ; CHECK:       loop3.latch:
224 ; CHECK-NEXT:    br label [[FLOW10]]
225 ; CHECK:       Flow10:
226 ; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[FLOW8]]
227 ; CHECK:       exit:
228 ; CHECK-NEXT:    ret void
230 entry:
231   br i1 %b1, label %loop1.header, label %if.else
233 if.else:
234   br i1 %b2, label %loop3.latch, label %loop2.header
236 loop1.header:
237   br i1 %b3, label %loop1.latch, label %loop1.body
239 loop1.latch:
240   br i1 %b4, label %loop1.header, label %exit
242 loop1.body:
243   br i1 %b5, label %loop2.header, label %loop1.latch
245 loop2.header:
246   br i1 %b6, label %loop2.latch, label %loop2.body
248 loop2.body:
249   br i1 %b7, label %loop2.latch, label %loop3.header
251 loop2.latch:
252   br i1 %b8, label %loop2.header, label %exit
254 loop3.header:
255   br label %loop3.latch
257 loop3.latch:
258   br i1 %b9, label %loop3.header, label %exit
260 exit:
261   ret void