1; RUN: opt < %s -S -indvars -loop-unroll -verify-loop-info | FileCheck %s
2;
3; Unit tests for loop unrolling using ScalarEvolution to compute trip counts.
4;
5; Indvars is run first to generate an "old" SCEV result. Some unit
6; tests may check that SCEV is properly invalidated between passes.
7
8; Completely unroll loops without a canonical IV.
9;
10; CHECK-LABEL: @sansCanonical(
11; CHECK-NOT: phi
12; CHECK-NOT: icmp
13; CHECK: ret
14define i32 @sansCanonical(i32* %base) nounwind {
15entry:
16  br label %while.body
17
18while.body:
19  %iv = phi i64 [ 10, %entry ], [ %iv.next, %while.body ]
20  %sum = phi i32 [ 0, %entry ], [ %sum.next, %while.body ]
21  %iv.next = add i64 %iv, -1
22  %adr = getelementptr inbounds i32* %base, i64 %iv.next
23  %tmp = load i32* %adr, align 8
24  %sum.next = add i32 %sum, %tmp
25  %iv.narrow = trunc i64 %iv.next to i32
26  %cmp.i65 = icmp sgt i32 %iv.narrow, 0
27  br i1 %cmp.i65, label %while.body, label %exit
28
29exit:
30  ret i32 %sum
31}
32
33; SCEV unrolling properly handles loops with multiple exits. In this
34; case, the computed trip count based on a canonical IV is *not* for a
35; latch block. Canonical unrolling incorrectly unrolls it, but SCEV
36; unrolling does not.
37;
38; CHECK-LABEL: @earlyLoopTest(
39; CHECK: tail:
40; CHECK-NOT: br
41; CHECK: br i1 %cmp2, label %loop, label %exit2
42define i64 @earlyLoopTest(i64* %base) nounwind {
43entry:
44  br label %loop
45
46loop:
47  %iv = phi i64 [ 0, %entry ], [ %inc, %tail ]
48  %s = phi i64 [ 0, %entry ], [ %s.next, %tail ]
49  %adr = getelementptr i64* %base, i64 %iv
50  %val = load i64* %adr
51  %s.next = add i64 %s, %val
52  %inc = add i64 %iv, 1
53  %cmp = icmp ne i64 %inc, 4
54  br i1 %cmp, label %tail, label %exit1
55
56tail:
57  %cmp2 = icmp ne i64 %val, 0
58  br i1 %cmp2, label %loop, label %exit2
59
60exit1:
61  ret i64 %s
62
63exit2:
64  ret i64 %s.next
65}
66
67; SCEV properly unrolls multi-exit loops.
68;
69; SCEV cannot currently unroll this loop.
70; It should ideally detect a trip count of 5.
71; rdar:14038809 [SCEV]: Optimize trip count computation for multi-exit loops.
72; CHECK-LABEL: @multiExit(
73; CHECKFIXME: getelementptr i32* %base, i32 10
74; CHECKFIXME-NEXT: load i32*
75; CHECKFIXME: br i1 false, label %l2.10, label %exit1
76; CHECKFIXME: l2.10:
77; CHECKFIXME-NOT: br
78; CHECKFIXME: ret i32
79define i32 @multiExit(i32* %base) nounwind {
80entry:
81  br label %l1
82l1:
83  %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l2 ]
84  %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l2 ]
85  %inc1 = add i32 %iv1, 1
86  %inc2 = add i32 %iv2, 1
87  %adr = getelementptr i32* %base, i32 %iv1
88  %val = load i32* %adr
89  %cmp1 = icmp slt i32 %iv1, 5
90  br i1 %cmp1, label %l2, label %exit1
91l2:
92  %cmp2 = icmp slt i32 %iv2, 10
93  br i1 %cmp2, label %l1, label %exit2
94exit1:
95  ret i32 1
96exit2:
97  ret i32 %val
98}
99
100
101; SCEV should not unroll a multi-exit loops unless the latch block has
102; a known trip count, regardless of the early exit trip counts. The
103; LoopUnroll utility uses this assumption to optimize the latch
104; block's branch.
105;
106; CHECK-LABEL: @multiExitIncomplete(
107; CHECK: l3:
108; CHECK-NOT: br
109; CHECK:   br i1 %cmp3, label %l1, label %exit3
110define i32 @multiExitIncomplete(i32* %base) nounwind {
111entry:
112  br label %l1
113l1:
114  %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l3 ]
115  %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l3 ]
116  %inc1 = add i32 %iv1, 1
117  %inc2 = add i32 %iv2, 1
118  %adr = getelementptr i32* %base, i32 %iv1
119  %val = load i32* %adr
120  %cmp1 = icmp slt i32 %iv1, 5
121  br i1 %cmp1, label %l2, label %exit1
122l2:
123  %cmp2 = icmp slt i32 %iv2, 10
124  br i1 %cmp2, label %l3, label %exit2
125l3:
126  %cmp3 = icmp ne i32 %val, 0
127  br i1 %cmp3, label %l1, label %exit3
128
129exit1:
130  ret i32 1
131exit2:
132  ret i32 2
133exit3:
134  ret i32 3
135}
136
137; When loop unroll merges a loop exit with one of its parent loop's
138; exits, SCEV must forget its ExitNotTaken info.
139;
140; CHECK-LABEL: @nestedUnroll(
141; CHECK-NOT: br i1
142; CHECK: for.body87:
143define void @nestedUnroll() nounwind {
144entry:
145  br label %for.inc
146
147for.inc:
148  br i1 false, label %for.inc, label %for.body38.preheader
149
150for.body38.preheader:
151  br label %for.body38
152
153for.body38:
154  %i.113 = phi i32 [ %inc76, %for.inc74 ], [ 0, %for.body38.preheader ]
155  %mul48 = mul nsw i32 %i.113, 6
156  br label %for.body43
157
158for.body43:
159  %j.011 = phi i32 [ 0, %for.body38 ], [ %inc72, %for.body43 ]
160  %add49 = add nsw i32 %j.011, %mul48
161  %sh_prom50 = zext i32 %add49 to i64
162  %inc72 = add nsw i32 %j.011, 1
163  br i1 false, label %for.body43, label %for.inc74
164
165for.inc74:
166  %inc76 = add nsw i32 %i.113, 1
167  br i1 false, label %for.body38, label %for.body87.preheader
168
169for.body87.preheader:
170  br label %for.body87
171
172for.body87:
173  br label %for.body87
174}
175
176; PR16130: clang produces incorrect code with loop/expression at -O2
177; rdar:14036816 loop-unroll makes assumptions about undefined behavior
178;
179; The loop latch is assumed to exit after the first iteration because
180; of the induction variable's NSW flag. However, the loop latch's
181; equality test is skipped and the loop exits after the second
182; iteration via the early exit. So loop unrolling cannot assume that
183; the loop latch's exit count of zero is an upper bound on the number
184; of iterations.
185;
186; CHECK-LABEL: @nsw_latch(
187; CHECK: for.body:
188; CHECK: %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ]
189; CHECK: return:
190; CHECK: %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ]
191define void @nsw_latch(i32* %a) nounwind {
192entry:
193  br label %for.body
194
195for.body:                                         ; preds = %for.cond, %entry
196  %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ]
197  %tobool = icmp eq i32 %b.03, 0
198  %add = add nsw i32 %b.03, 8
199  br i1 %tobool, label %for.cond, label %return
200
201for.cond:                                         ; preds = %for.body
202  %cmp = icmp eq i32 %add, 13
203  br i1 %cmp, label %return, label %for.body
204
205return:                                           ; preds = %for.body, %for.cond
206  %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ]
207  %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ]
208  store i32 %b.03.lcssa, i32* %a, align 4
209  ret void
210}
211