1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -unify-loop-exits -S | FileCheck %s
3
4; Loop consists of A and B:
5; - A is the header
6; - A and B are exiting blocks
7; - C and return are exit blocks.
8; Pattern: Value (%mytmp42) defined in exiting block (A) and used in
9;          exit block (return).
10;          The relevant code uses DT::dominates(Value,
11;          BasicBlock). This is misnamed because it actually checks
12;          strict dominance, causing the pattern to be miscompiled
13;          (the use receives an undef value).
14define i32 @exiting-used-in-exit(i32* %arg1, i32* %arg2) local_unnamed_addr align 2 {
15; CHECK-LABEL: @exiting-used-in-exit(
16; CHECK-NEXT:  entry:
17; CHECK-NEXT:    br label [[A:%.*]]
18; CHECK:       A:
19; CHECK-NEXT:    [[MYTMP42:%.*]] = load i32, i32* [[ARG1:%.*]], align 4
20; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[MYTMP42]], 0
21; CHECK-NEXT:    br i1 [[CMP1]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
22; CHECK:       B:
23; CHECK-NEXT:    [[MYTMP41:%.*]] = load i32, i32* [[ARG2:%.*]], align 4
24; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP41]], 0
25; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
26; CHECK:       C:
27; CHECK-NEXT:    [[INC:%.*]] = add i32 [[MYTMP41_MOVED:%.*]], 1
28; CHECK-NEXT:    br label [[RETURN:%.*]]
29; CHECK:       return:
30; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[INC]], [[C:%.*]] ], [ [[PHI_MOVED:%.*]], [[LOOP_EXIT_GUARD]] ]
31; CHECK-NEXT:    ret i32 [[PHI]]
32; CHECK:       loop.exit.guard:
33; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[B]] ]
34; CHECK-NEXT:    [[PHI_MOVED]] = phi i32 [ [[MYTMP42]], [[A]] ], [ undef, [[B]] ]
35; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[B]] ]
36; CHECK-NEXT:    br i1 [[GUARD_RETURN]], label [[RETURN]], label [[C]]
37;
38entry:
39  br label %A
40
41A:
42  %mytmp42 = load i32, i32* %arg1, align 4
43  %cmp1 = icmp slt i32 %mytmp42, 0
44  br i1 %cmp1, label %B, label %return
45
46B:
47  %mytmp41 = load i32, i32* %arg2, align 4
48  %cmp = icmp slt i32 %mytmp41, 0
49  br i1 %cmp, label %A, label %C
50
51C:
52  %inc = add i32 %mytmp41, 1
53  br label %return
54
55return:
56  %phi = phi i32 [ %inc, %C ], [ %mytmp42, %A ]
57  ret i32 %phi
58}
59
60; Loop consists of A, B and C:
61; - A is the header
62; - A and C are exiting blocks
63; - B is an "internal" block that dominates exiting block C
64; - D and return are exit blocks.
65; Pattern: Value (%mytmp41) defined in internal block (B) and used in an
66;          exit block (D).
67define i32 @internal-used-in-exit(i32* %arg1, i32* %arg2) local_unnamed_addr align 2 {
68; CHECK-LABEL: @internal-used-in-exit(
69; CHECK-NEXT:  entry:
70; CHECK-NEXT:    [[MYTMP42:%.*]] = load i32, i32* [[ARG1:%.*]], align 4
71; CHECK-NEXT:    br label [[A:%.*]]
72; CHECK:       A:
73; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[MYTMP42]], 0
74; CHECK-NEXT:    br i1 [[CMP1]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
75; CHECK:       B:
76; CHECK-NEXT:    [[MYTMP41:%.*]] = load i32, i32* [[ARG2:%.*]], align 4
77; CHECK-NEXT:    br label [[C:%.*]]
78; CHECK:       C:
79; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP42]], 0
80; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
81; CHECK:       D:
82; CHECK-NEXT:    [[INC:%.*]] = add i32 [[MYTMP41_MOVED:%.*]], 1
83; CHECK-NEXT:    br label [[RETURN:%.*]]
84; CHECK:       return:
85; CHECK-NEXT:    ret i32 0
86; CHECK:       loop.exit.guard:
87; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
88; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[C]] ]
89; CHECK-NEXT:    br i1 [[GUARD_RETURN]], label [[RETURN]], label [[D:%.*]]
90;
91entry:
92  %mytmp42 = load i32, i32* %arg1, align 4
93  br label %A
94
95A:
96  %cmp1 = icmp slt i32 %mytmp42, 0
97  br i1 %cmp1, label %B, label %return
98
99B:
100  %mytmp41 = load i32, i32* %arg2, align 4
101  br label %C
102
103C:
104  %cmp = icmp slt i32 %mytmp42, 0
105  br i1 %cmp, label %A, label %D
106
107D:
108  %inc = add i32 %mytmp41, 1
109  br label %return
110
111return:
112  ret i32 0
113}
114
115; Loop consists of A, B and C:
116; - A is the header
117; - A and C are exiting blocks
118; - B is an "internal" block that dominates exiting block C
119; - D and return are exit blocks.
120; Pattern: %return contains a phi node that receives values from
121;          %entry, %A and %D. This mixes all the special cases in a single phi.
122define i32 @mixed-use-in-exit(i32* %arg1, i32* %arg2) local_unnamed_addr align 2 {
123; CHECK-LABEL: @mixed-use-in-exit(
124; CHECK-NEXT:  entry:
125; CHECK-NEXT:    [[MYTMP42:%.*]] = load i32, i32* [[ARG1:%.*]], align 4
126; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[MYTMP42]], 0
127; CHECK-NEXT:    br i1 [[CMP2]], label [[A:%.*]], label [[RETURN:%.*]]
128; CHECK:       A:
129; CHECK-NEXT:    [[MYTMP43:%.*]] = add i32 [[MYTMP42]], 1
130; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[MYTMP42]], 0
131; CHECK-NEXT:    br i1 [[CMP1]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
132; CHECK:       B:
133; CHECK-NEXT:    [[MYTMP41:%.*]] = load i32, i32* [[ARG2:%.*]], align 4
134; CHECK-NEXT:    br label [[C:%.*]]
135; CHECK:       C:
136; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP42]], 0
137; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
138; CHECK:       D:
139; CHECK-NEXT:    br label [[RETURN]]
140; CHECK:       return:
141; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[MYTMP41_MOVED:%.*]], [[D:%.*]] ], [ [[MYTMP42]], [[ENTRY:%.*]] ], [ [[PHI_MOVED:%.*]], [[LOOP_EXIT_GUARD]] ]
142; CHECK-NEXT:    ret i32 [[PHI]]
143; CHECK:       loop.exit.guard:
144; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
145; CHECK-NEXT:    [[PHI_MOVED]] = phi i32 [ [[MYTMP43]], [[A]] ], [ undef, [[C]] ]
146; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[C]] ]
147; CHECK-NEXT:    br i1 [[GUARD_RETURN]], label [[RETURN]], label [[D]]
148;
149entry:
150  %mytmp42 = load i32, i32* %arg1, align 4
151  %cmp2 = icmp slt i32 %mytmp42, 0
152  br i1 %cmp2, label %A, label %return
153
154A:
155  %mytmp43 = add i32 %mytmp42, 1
156  %cmp1 = icmp slt i32 %mytmp42, 0
157  br i1 %cmp1, label %B, label %return
158
159B:
160  %mytmp41 = load i32, i32* %arg2, align 4
161  br label %C
162
163C:
164  %cmp = icmp slt i32 %mytmp42, 0
165  br i1 %cmp, label %A, label %D
166
167D:
168  br label %return
169
170return:
171  %phi = phi i32 [ %mytmp41, %D ], [ %mytmp43, %A ], [%mytmp42, %entry]
172  ret i32 %phi
173}
174
175; Loop consists of A, B and C:
176; - A is the header
177; - A and C are exiting blocks
178; - B is an "internal" block that dominates exiting block C
179; - D and E are exit blocks.
180; Pattern: Value (%mytmp41) defined in internal block (B) and used in a
181;          downstream block not related to the loop (return). The use
182;          is a phi where the incoming block for %mytmp41 is not related
183;          to the loop (D).
184;          This pattern does not involve either the exiting blocks or
185;          the exit blocks, which catches any such assumptions built
186;          into the SSA reconstruction phase.
187define i32 @phi-via-external-block(i32* %arg1, i32* %arg2) local_unnamed_addr align 2 {
188; CHECK-LABEL: @phi-via-external-block(
189; CHECK-NEXT:  entry:
190; CHECK-NEXT:    [[MYTMP42:%.*]] = load i32, i32* [[ARG1:%.*]], align 4
191; CHECK-NEXT:    br label [[A:%.*]]
192; CHECK:       A:
193; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[MYTMP42]], 0
194; CHECK-NEXT:    br i1 [[CMP1]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
195; CHECK:       B:
196; CHECK-NEXT:    [[MYTMP41:%.*]] = load i32, i32* [[ARG2:%.*]], align 4
197; CHECK-NEXT:    br label [[C:%.*]]
198; CHECK:       C:
199; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP42]], 0
200; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
201; CHECK:       D:
202; CHECK-NEXT:    br label [[RETURN:%.*]]
203; CHECK:       E:
204; CHECK-NEXT:    br label [[RETURN]]
205; CHECK:       return:
206; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[MYTMP41_MOVED:%.*]], [[D:%.*]] ], [ [[MYTMP42]], [[E:%.*]] ]
207; CHECK-NEXT:    ret i32 [[PHI]]
208; CHECK:       loop.exit.guard:
209; CHECK-NEXT:    [[GUARD_E:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
210; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[C]] ]
211; CHECK-NEXT:    br i1 [[GUARD_E]], label [[E]], label [[D]]
212;
213entry:
214  %mytmp42 = load i32, i32* %arg1, align 4
215  br label %A
216
217A:
218  %cmp1 = icmp slt i32 %mytmp42, 0
219  br i1 %cmp1, label %B, label %E
220
221B:
222  %mytmp41 = load i32, i32* %arg2, align 4
223  br label %C
224
225C:
226  %cmp = icmp slt i32 %mytmp42, 0
227  br i1 %cmp, label %A, label %D
228
229D:
230  br label %return
231
232E:
233  br label %return
234
235return:
236  %phi = phi i32 [ %mytmp41, %D ], [ %mytmp42, %E ]
237  ret i32 %phi
238}
239