1; RUN: opt -loop-idiom < %s -mtriple=x86_64-apple-darwin -mcpu=corei7 -S | FileCheck %s
2
3target triple = "x86_64-apple-macosx10.8.0"
4
5;To recognize this pattern:
6;int popcount(unsigned long long a) {
7;    int c = 0;
8;    while (a) {
9;        c++;
10;        a &= a - 1;
11;    }
12;    return c;
13;}
14;
15; CHECK: entry
16; CHECK: llvm.ctpop.i64
17; CHECK: ret
18define i32 @popcount(i64 %a) nounwind uwtable readnone ssp {
19entry:
20  %tobool3 = icmp eq i64 %a, 0
21  br i1 %tobool3, label %while.end, label %while.body
22
23while.body:                                       ; preds = %entry, %while.body
24  %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
25  %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
26  %inc = add nsw i32 %c.05, 1
27  %sub = add i64 %a.addr.04, -1
28  %and = and i64 %sub, %a.addr.04
29  %tobool = icmp eq i64 %and, 0
30  br i1 %tobool, label %while.end, label %while.body
31
32while.end:                                        ; preds = %while.body, %entry
33  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
34  ret i32 %c.0.lcssa
35}
36
37; To recognize this pattern:
38;int popcount(unsigned long long a, int mydata1, int mydata2) {
39;    int c = 0;
40;    while (a) {
41;        c++;
42;        a &= a - 1;
43;        mydata1 *= c;
44;        mydata2 *= (int)a;
45;    }
46;    return c + mydata1 + mydata2;
47;}
48; CHECK: entry
49; CHECK: llvm.ctpop.i64
50; CHECK: ret
51define i32 @popcount2(i64 %a, i32 %mydata1, i32 %mydata2) nounwind uwtable readnone ssp {
52entry:
53  %tobool9 = icmp eq i64 %a, 0
54  br i1 %tobool9, label %while.end, label %while.body
55
56while.body:                                       ; preds = %entry, %while.body
57  %c.013 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
58  %mydata2.addr.012 = phi i32 [ %mul1, %while.body ], [ %mydata2, %entry ]
59  %mydata1.addr.011 = phi i32 [ %mul, %while.body ], [ %mydata1, %entry ]
60  %a.addr.010 = phi i64 [ %and, %while.body ], [ %a, %entry ]
61  %inc = add nsw i32 %c.013, 1
62  %sub = add i64 %a.addr.010, -1
63  %and = and i64 %sub, %a.addr.010
64  %mul = mul nsw i32 %inc, %mydata1.addr.011
65  %conv = trunc i64 %and to i32
66  %mul1 = mul nsw i32 %conv, %mydata2.addr.012
67  %tobool = icmp eq i64 %and, 0
68  br i1 %tobool, label %while.end, label %while.body
69
70while.end:                                        ; preds = %while.body, %entry
71  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
72  %mydata2.addr.0.lcssa = phi i32 [ %mydata2, %entry ], [ %mul1, %while.body ]
73  %mydata1.addr.0.lcssa = phi i32 [ %mydata1, %entry ], [ %mul, %while.body ]
74  %add = add i32 %mydata2.addr.0.lcssa, %mydata1.addr.0.lcssa
75  %add2 = add i32 %add, %c.0.lcssa
76  ret i32 %add2
77}
78
79; Some variants once cause crash
80
81define i32 @PopCntCrash1(i64 %a) nounwind uwtable readnone ssp {
82entry:
83  %tobool3 = icmp eq i64 %a, 0
84  br i1 %tobool3, label %while.end, label %while.body
85
86while.body:                                       ; preds = %entry, %while.body
87  %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
88  %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
89  %t = add i32 %c.05, %c.05
90  %inc = add nsw i32 %t, 1
91  %sub = add i64 %a.addr.04, -1
92  %and = and i64 %sub, %a.addr.04
93  %tobool = icmp eq i64 %and, 0
94  br i1 %tobool, label %while.end, label %while.body
95
96while.end:                                        ; preds = %while.body, %entry
97  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
98  ret i32 %c.0.lcssa
99
100; CHECK: entry
101; CHECK: ret
102}
103
104define i32 @PopCntCrash2(i64 %a, i32 %b) nounwind uwtable readnone ssp {
105entry:
106  %tobool3 = icmp eq i64 %a, 0
107  br i1 %tobool3, label %while.end, label %while.body
108
109while.body:                                       ; preds = %entry, %while.body
110  %c.05 = phi i32 [ %inc, %while.body ], [ %b, %entry ]
111  %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
112  %inc = add nsw i32 %c.05, 1
113  %sub = add i64 %a.addr.04, -1
114  %and = and i64 %sub, %a.addr.04
115  %tobool = icmp eq i64 %and, 0
116  br i1 %tobool, label %while.end, label %while.body
117
118while.end:                                        ; preds = %while.body, %entry
119  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
120  ret i32 %c.0.lcssa
121}
122
123define i32 @PopCntCrash3(i64 %a, i32 %x) {
124entry:
125  %tobool3 = icmp eq i64 %a, 0
126  %cmp = icmp eq i32 %x, 0
127  br i1 %tobool3, label %while.end, label %while.body
128
129while.body:                                       ; preds = %entry, %while.body
130  %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
131  %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
132  %inc = add nsw i32 %c.05, 1
133  %sub = add i64 %a.addr.04, -1
134  %and = and i64 %sub, %a.addr.04
135  %tobool = icmp eq i64 %and, 0
136  br i1 %cmp, label %while.end, label %while.body
137
138while.end:                                        ; preds = %while.body, %entry
139  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
140  ret i32 %c.0.lcssa
141}
142
143; The a & (a - 1) in the loop is a & (b - 1) in this code. Make sure we don't
144; convert it.
145define i32 @popcount_bad(i64 %a, i64 %b) nounwind uwtable readnone ssp {
146; CHECK-LABEL: @popcount_bad(
147; CHECK-NEXT:  entry:
148; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp eq i64 [[A:%.*]], 0
149; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
150; CHECK:       while.body.preheader:
151; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
152; CHECK:       while.body:
153; CHECK-NEXT:    [[C_05:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
154; CHECK-NEXT:    [[A_ADDR_04:%.*]] = phi i64 [ [[AND:%.*]], [[WHILE_BODY]] ], [ [[A]], [[WHILE_BODY_PREHEADER]] ]
155; CHECK-NEXT:    [[INC]] = add nsw i32 [[C_05]], 1
156; CHECK-NEXT:    [[SUB:%.*]] = add i64 [[B:%.*]], -1
157; CHECK-NEXT:    [[AND]] = and i64 [[SUB]], [[A_ADDR_04]]
158; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[AND]], 0
159; CHECK-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
160; CHECK:       while.end.loopexit:
161; CHECK-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[WHILE_BODY]] ]
162; CHECK-NEXT:    br label [[WHILE_END]]
163; CHECK:       while.end:
164; CHECK-NEXT:    [[C_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
165; CHECK-NEXT:    ret i32 [[C_0_LCSSA]]
166;
167entry:
168  %tobool3 = icmp eq i64 %a, 0
169  br i1 %tobool3, label %while.end, label %while.body
170
171while.body:                                       ; preds = %entry, %while.body
172  %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
173  %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
174  %inc = add nsw i32 %c.05, 1
175  %sub = add i64 %b, -1
176  %and = and i64 %sub, %a.addr.04
177  %tobool = icmp eq i64 %and, 0
178  br i1 %tobool, label %while.end, label %while.body
179
180while.end:                                        ; preds = %while.body, %entry
181  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
182  ret i32 %c.0.lcssa
183}
184