1; RUN: opt -loop-idiom < %s -mtriple=x86_64-apple-darwin -mcpu=corei7 -S | FileCheck %s
2
3;To recognize this pattern:
4;int popcount(unsigned long long a) {
5;    int c = 0;
6;    while (a) {
7;        c++;
8;        a &= a - 1;
9;    }
10;    return c;
11;}
12;
13; CHECK: entry
14; CHECK: llvm.ctpop.i64
15; CHECK: ret
16define i32 @popcount(i64 %a) nounwind uwtable readnone ssp {
17entry:
18  %tobool3 = icmp eq i64 %a, 0
19  br i1 %tobool3, label %while.end, label %while.body
20
21while.body:                                       ; preds = %entry, %while.body
22  %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
23  %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
24  %inc = add nsw i32 %c.05, 1
25  %sub = add i64 %a.addr.04, -1
26  %and = and i64 %sub, %a.addr.04
27  %tobool = icmp eq i64 %and, 0
28  br i1 %tobool, label %while.end, label %while.body
29
30while.end:                                        ; preds = %while.body, %entry
31  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
32  ret i32 %c.0.lcssa
33}
34
35; To recognize this pattern:
36;int popcount(unsigned long long a, int mydata1, int mydata2) {
37;    int c = 0;
38;    while (a) {
39;        c++;
40;        a &= a - 1;
41;        mydata1 *= c;
42;        mydata2 *= (int)a;
43;    }
44;    return c + mydata1 + mydata2;
45;}
46; CHECK: entry
47; CHECK: llvm.ctpop.i64
48; CHECK: ret
49define i32 @popcount2(i64 %a, i32 %mydata1, i32 %mydata2) nounwind uwtable readnone ssp {
50entry:
51  %tobool9 = icmp eq i64 %a, 0
52  br i1 %tobool9, label %while.end, label %while.body
53
54while.body:                                       ; preds = %entry, %while.body
55  %c.013 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
56  %mydata2.addr.012 = phi i32 [ %mul1, %while.body ], [ %mydata2, %entry ]
57  %mydata1.addr.011 = phi i32 [ %mul, %while.body ], [ %mydata1, %entry ]
58  %a.addr.010 = phi i64 [ %and, %while.body ], [ %a, %entry ]
59  %inc = add nsw i32 %c.013, 1
60  %sub = add i64 %a.addr.010, -1
61  %and = and i64 %sub, %a.addr.010
62  %mul = mul nsw i32 %inc, %mydata1.addr.011
63  %conv = trunc i64 %and to i32
64  %mul1 = mul nsw i32 %conv, %mydata2.addr.012
65  %tobool = icmp eq i64 %and, 0
66  br i1 %tobool, label %while.end, label %while.body
67
68while.end:                                        ; preds = %while.body, %entry
69  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
70  %mydata2.addr.0.lcssa = phi i32 [ %mydata2, %entry ], [ %mul1, %while.body ]
71  %mydata1.addr.0.lcssa = phi i32 [ %mydata1, %entry ], [ %mul, %while.body ]
72  %add = add i32 %mydata2.addr.0.lcssa, %mydata1.addr.0.lcssa
73  %add2 = add i32 %add, %c.0.lcssa
74  ret i32 %add2
75}
76
77; Some variants once cause crash
78target triple = "x86_64-apple-macosx10.8.0"
79
80define i32 @PopCntCrash1(i64 %a) nounwind uwtable readnone ssp {
81entry:
82  %tobool3 = icmp eq i64 %a, 0
83  br i1 %tobool3, label %while.end, label %while.body
84
85while.body:                                       ; preds = %entry, %while.body
86  %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
87  %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
88  %t = add i32 %c.05, %c.05
89  %inc = add nsw i32 %t, 1
90  %sub = add i64 %a.addr.04, -1
91  %and = and i64 %sub, %a.addr.04
92  %tobool = icmp eq i64 %and, 0
93  br i1 %tobool, label %while.end, label %while.body
94
95while.end:                                        ; preds = %while.body, %entry
96  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
97  ret i32 %c.0.lcssa
98
99; CHECK: entry
100; CHECK: ret
101}
102
103define i32 @PopCntCrash2(i64 %a, i32 %b) nounwind uwtable readnone ssp {
104entry:
105  %tobool3 = icmp eq i64 %a, 0
106  br i1 %tobool3, label %while.end, label %while.body
107
108while.body:                                       ; preds = %entry, %while.body
109  %c.05 = phi i32 [ %inc, %while.body ], [ %b, %entry ]
110  %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
111  %inc = add nsw i32 %c.05, 1
112  %sub = add i64 %a.addr.04, -1
113  %and = and i64 %sub, %a.addr.04
114  %tobool = icmp eq i64 %and, 0
115  br i1 %tobool, label %while.end, label %while.body
116
117while.end:                                        ; preds = %while.body, %entry
118  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
119  ret i32 %c.0.lcssa
120}
121
122define i32 @PopCntCrash3(i64 %a, i32 %x) {
123entry:
124  %tobool3 = icmp eq i64 %a, 0
125  %cmp = icmp eq i32 %x, 0
126  br i1 %tobool3, label %while.end, label %while.body
127
128while.body:                                       ; preds = %entry, %while.body
129  %c.05 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
130  %a.addr.04 = phi i64 [ %and, %while.body ], [ %a, %entry ]
131  %inc = add nsw i32 %c.05, 1
132  %sub = add i64 %a.addr.04, -1
133  %and = and i64 %sub, %a.addr.04
134  %tobool = icmp eq i64 %and, 0
135  br i1 %cmp, label %while.end, label %while.body
136
137while.end:                                        ; preds = %while.body, %entry
138  %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
139  ret i32 %c.0.lcssa
140}
141