• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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: @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: @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; CHECK: @multiExit
70; CHECK: getelementptr i32* %base, i32 10
71; CHECK-NEXT: load i32*
72; CHECK: br i1 false, label %l2.10, label %exit1
73; CHECK: l2.10:
74; CHECK-NOT: br
75; CHECK: ret i32
76define i32 @multiExit(i32* %base) nounwind {
77entry:
78  br label %l1
79l1:
80  %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l2 ]
81  %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l2 ]
82  %inc1 = add i32 %iv1, 1
83  %inc2 = add i32 %iv2, 1
84  %adr = getelementptr i32* %base, i32 %iv1
85  %val = load i32* %adr
86  %cmp1 = icmp slt i32 %iv1, 5
87  br i1 %cmp1, label %l2, label %exit1
88l2:
89  %cmp2 = icmp slt i32 %iv2, 10
90  br i1 %cmp2, label %l1, label %exit2
91exit1:
92  ret i32 1
93exit2:
94  ret i32 %val
95}
96
97
98; SCEV should not unroll a multi-exit loops unless the latch block has
99; a known trip count, regardless of the early exit trip counts. The
100; LoopUnroll utility uses this assumption to optimize the latch
101; block's branch.
102;
103; CHECK: @multiExit
104; CHECK: l3:
105; CHECK-NOT: br
106; CHECK:   br i1 %cmp3, label %l1, label %exit3
107define i32 @multiExitIncomplete(i32* %base) nounwind {
108entry:
109  br label %l1
110l1:
111  %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l3 ]
112  %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l3 ]
113  %inc1 = add i32 %iv1, 1
114  %inc2 = add i32 %iv2, 1
115  %adr = getelementptr i32* %base, i32 %iv1
116  %val = load i32* %adr
117  %cmp1 = icmp slt i32 %iv1, 5
118  br i1 %cmp1, label %l2, label %exit1
119l2:
120  %cmp2 = icmp slt i32 %iv2, 10
121  br i1 %cmp2, label %l3, label %exit2
122l3:
123  %cmp3 = icmp ne i32 %val, 0
124  br i1 %cmp3, label %l1, label %exit3
125
126exit1:
127  ret i32 1
128exit2:
129  ret i32 2
130exit3:
131  ret i32 3
132}
133
134; When loop unroll merges a loop exit with one of its parent loop's
135; exits, SCEV must forget its ExitNotTaken info.
136;
137; CHECK: @nestedUnroll
138; CHECK-NOT: br i1
139; CHECK: for.body87:
140define void @nestedUnroll() nounwind {
141entry:
142  br label %for.inc
143
144for.inc:
145  br i1 false, label %for.inc, label %for.body38.preheader
146
147for.body38.preheader:
148  br label %for.body38
149
150for.body38:
151  %i.113 = phi i32 [ %inc76, %for.inc74 ], [ 0, %for.body38.preheader ]
152  %mul48 = mul nsw i32 %i.113, 6
153  br label %for.body43
154
155for.body43:
156  %j.011 = phi i32 [ 0, %for.body38 ], [ %inc72, %for.body43 ]
157  %add49 = add nsw i32 %j.011, %mul48
158  %sh_prom50 = zext i32 %add49 to i64
159  %inc72 = add nsw i32 %j.011, 1
160  br i1 false, label %for.body43, label %for.inc74
161
162for.inc74:
163  %inc76 = add nsw i32 %i.113, 1
164  br i1 false, label %for.body38, label %for.body87.preheader
165
166for.body87.preheader:
167  br label %for.body87
168
169for.body87:
170  br label %for.body87
171}
172
173