xref: /llvm-project/llvm/test/Transforms/LoopIdiom/ARM/ctlz.ll (revision 2c2de4b20ef6792e8bf437b02fbb94e3c20bdaff) 
1; RUN: opt -passes=loop-idiom -mtriple=armv7a < %s -S | FileCheck -check-prefix=LZCNT --check-prefix=ALL %s
2; RUN: opt -passes=loop-idiom -mtriple=armv4t < %s -S | FileCheck -check-prefix=NOLZCNT --check-prefix=ALL %s
3
4; Recognize CTLZ builtin pattern.
5; Here we'll just convert loop to countable,
6; so do not insert builtin if CPU do not support CTLZ
7;
8; int ctlz_and_other(int n, char *a)
9; {
10;   n = n >= 0 ? n : -n;
11;   int i = 0, n0 = n;
12;   while(n >>= 1) {
13;     a[i] = (n0 & (1 << i)) ? 1 : 0;
14;     i++;
15;   }
16;   return i;
17; }
18;
19; LZCNT:  entry
20; LZCNT:  %0 = call i32 @llvm.ctlz.i32(i32 %shr8, i1 true)
21; LZCNT-NEXT:  %1 = sub i32 32, %0
22; LZCNT-NEXT:  %2 = zext i32 %1 to i64
23; LZCNT:  %indvars.iv.next.lcssa = phi i64 [ %2, %while.body ]
24; LZCNT:  %4 = trunc i64 %indvars.iv.next.lcssa to i32
25; LZCNT:  %i.0.lcssa = phi i32 [ 0, %entry ], [ %4, %while.end.loopexit ]
26; LZCNT:  ret i32 %i.0.lcssa
27
28; NOLZCNT:  entry
29; NOLZCNT-NOT:  @llvm.ctlz
30
31; Function Attrs: norecurse nounwind uwtable
32define i32 @ctlz_and_other(i32 %n, ptr nocapture %a) {
33entry:
34  %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)
35  %shr8 = lshr i32 %abs_n, 1
36  %tobool9 = icmp eq i32 %shr8, 0
37  br i1 %tobool9, label %while.end, label %while.body.preheader
38
39while.body.preheader:                             ; preds = %entry
40  br label %while.body
41
42while.body:                                       ; preds = %while.body.preheader, %while.body
43  %indvars.iv = phi i64 [ %indvars.iv.next, %while.body ], [ 0, %while.body.preheader ]
44  %shr11 = phi i32 [ %shr, %while.body ], [ %shr8, %while.body.preheader ]
45  %0 = trunc i64 %indvars.iv to i32
46  %shl = shl i32 1, %0
47  %and = and i32 %shl, %abs_n
48  %tobool1 = icmp ne i32 %and, 0
49  %conv = zext i1 %tobool1 to i8
50  %arrayidx = getelementptr inbounds i8, ptr %a, i64 %indvars.iv
51  store i8 %conv, ptr %arrayidx, align 1
52  %indvars.iv.next = add nuw i64 %indvars.iv, 1
53  %shr = ashr i32 %shr11, 1
54  %tobool = icmp eq i32 %shr, 0
55  br i1 %tobool, label %while.end.loopexit, label %while.body
56
57while.end.loopexit:                               ; preds = %while.body
58  %1 = trunc i64 %indvars.iv.next to i32
59  br label %while.end
60
61while.end:                                        ; preds = %while.end.loopexit, %entry
62  %i.0.lcssa = phi i32 [ 0, %entry ], [ %1, %while.end.loopexit ]
63  ret i32 %i.0.lcssa
64}
65
66; Recognize CTLZ builtin pattern.
67; Here it will replace the loop -
68; assume builtin is always profitable.
69;
70; int ctlz_zero_check(int n)
71; {
72;   n = n >= 0 ? n : -n;
73;   int i = 0;
74;   while(n) {
75;     n >>= 1;
76;     i++;
77;   }
78;   return i;
79; }
80;
81; ALL:  entry
82; ALL:  %0 = call i32 @llvm.ctlz.i32(i32 %abs_n, i1 true)
83; ALL-NEXT:  %1 = sub i32 32, %0
84; ALL:  %inc.lcssa = phi i32 [ %1, %while.body ]
85; ALL:  %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc.lcssa, %while.end.loopexit ]
86; ALL:  ret i32 %i.0.lcssa
87
88; Function Attrs: norecurse nounwind readnone uwtable
89define i32 @ctlz_zero_check(i32 %n) {
90entry:
91  %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)
92  %tobool4 = icmp eq i32 %abs_n, 0
93  br i1 %tobool4, label %while.end, label %while.body.preheader
94
95while.body.preheader:                             ; preds = %entry
96  br label %while.body
97
98while.body:                                       ; preds = %while.body.preheader, %while.body
99  %i.06 = phi i32 [ %inc, %while.body ], [ 0, %while.body.preheader ]
100  %n.addr.05 = phi i32 [ %shr, %while.body ], [ %abs_n, %while.body.preheader ]
101  %shr = ashr i32 %n.addr.05, 1
102  %inc = add nsw i32 %i.06, 1
103  %tobool = icmp eq i32 %shr, 0
104  br i1 %tobool, label %while.end.loopexit, label %while.body
105
106while.end.loopexit:                               ; preds = %while.body
107  br label %while.end
108
109while.end:                                        ; preds = %while.end.loopexit, %entry
110  %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.end.loopexit ]
111  ret i32 %i.0.lcssa
112}
113
114; Recognize CTLZ builtin pattern.
115; Here it will replace the loop -
116; assume builtin is always profitable.
117;
118; int ctlz(int n)
119; {
120;   n = n >= 0 ? n : -n;
121;   int i = 0;
122;   while(n >>= 1) {
123;     i++;
124;   }
125;   return i;
126; }
127;
128; ALL:  entry
129; ALL:  %0 = ashr i32 %abs_n, 1
130; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
131; ALL-NEXT:  %2 = sub i32 32, %1
132; ALL-NEXT:  %3 = add i32 %2, 1
133; ALL:  %i.0.lcssa = phi i32 [ %2, %while.cond ]
134; ALL:  ret i32 %i.0.lcssa
135
136; Function Attrs: norecurse nounwind readnone uwtable
137define i32 @ctlz(i32 %n) {
138entry:
139  %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)
140  br label %while.cond
141
142while.cond:                                       ; preds = %while.cond, %entry
143  %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
144  %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]
145  %shr = ashr i32 %n.addr.0, 1
146  %tobool = icmp eq i32 %shr, 0
147  %inc = add nsw i32 %i.0, 1
148  br i1 %tobool, label %while.end, label %while.cond
149
150while.end:                                        ; preds = %while.cond
151  ret i32 %i.0
152}
153
154; Recognize CTLZ builtin pattern.
155; Here it will replace the loop -
156; assume builtin is always profitable.
157;
158; int ctlz_add(int n, int i0)
159; {
160;   n = n >= 0 ? n : -n;
161;   int i = i0;
162;   while(n >>= 1) {
163;     i++;
164;   }
165;   return i;
166; }
167;
168; ALL:  entry
169; ALL:  %0 = ashr i32 %abs_n, 1
170; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
171; ALL-NEXT:  %2 = sub i32 32, %1
172; ALL-NEXT:  %3 = add i32 %2, 1
173; ALL-NEXT:  %4 = add i32 %2, %i0
174; ALL:  %i.0.lcssa = phi i32 [ %4, %while.cond ]
175; ALL:  ret i32 %i.0.lcssa
176;
177; Function Attrs: norecurse nounwind readnone uwtable
178define i32 @ctlz_add(i32 %n, i32 %i0) {
179entry:
180  %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)
181  br label %while.cond
182
183while.cond:                                       ; preds = %while.cond, %entry
184  %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
185  %i.0 = phi i32 [ %i0, %entry ], [ %inc, %while.cond ]
186  %shr = ashr i32 %n.addr.0, 1
187  %tobool = icmp eq i32 %shr, 0
188  %inc = add nsw i32 %i.0, 1
189  br i1 %tobool, label %while.end, label %while.cond
190
191while.end:                                        ; preds = %while.cond
192  ret i32 %i.0
193}
194
195; Recognize CTLZ builtin pattern.
196; Here it will replace the loop -
197; assume builtin is always profitable.
198;
199; int ctlz_sext(short in)
200; {
201;   int n = in;
202;   if (in < 0)
203;     n = -n;
204;   int i = 0;
205;   while(n >>= 1) {
206;     i++;
207;   }
208;   return i;
209; }
210;
211; ALL:  entry
212; ALL:  %0 = ashr i32 %abs_n, 1
213; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
214; ALL-NEXT:  %2 = sub i32 32, %1
215; ALL-NEXT:  %3 = add i32 %2, 1
216; ALL:  %i.0.lcssa = phi i32 [ %2, %while.cond ]
217; ALL:  ret i32 %i.0.lcssa
218
219; Function Attrs: norecurse nounwind readnone uwtable
220define i32 @ctlz_sext(i16 %in) {
221entry:
222  %abs = call i16 @llvm.abs.i16(i16 %in, i1 false)
223  %abs_n = zext i16 %abs to i32
224  br label %while.cond
225
226while.cond:                                       ; preds = %while.cond, %entry
227  %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
228  %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]
229  %shr = ashr i32 %n.addr.0, 1
230  %tobool = icmp eq i32 %shr, 0
231  %inc = add nsw i32 %i.0, 1
232  br i1 %tobool, label %while.end, label %while.cond
233
234while.end:                                        ; preds = %while.cond
235  ret i32 %i.0
236}
237
238declare i32 @llvm.abs.i32(i32, i1)
239declare i16 @llvm.abs.i16(i16, i1)
240