llvm/test/Transforms/LoopIdiom/X86/popcnt.ll

   1 ; RUN: opt -loop-idiom < %s -mtriple=x86_64-apple-darwin -mcpu=corei7 -S | FileCheck %s
   2
   3 target 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
  18 define i32 @popcount(i64 %a) nounwind uwtable readnone ssp {
  19 entry:
  20   %tobool3 = icmp eq i64 %a, 0
  21   br i1 %tobool3, label %while.end, label %while.body
  22
  23 while.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
  32 while.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
  51 define i32 @popcount2(i64 %a, i32 %mydata1, i32 %mydata2) nounwind uwtable readnone ssp {
  52 entry:
  53   %tobool9 = icmp eq i64 %a, 0
  54   br i1 %tobool9, label %while.end, label %while.body
  55
  56 while.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
  70 while.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
  81 define i32 @PopCntCrash1(i64 %a) nounwind uwtable readnone ssp {
  82 entry:
  83   %tobool3 = icmp eq i64 %a, 0
  84   br i1 %tobool3, label %while.end, label %while.body
  85
  86 while.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
  96 while.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
 104 define i32 @PopCntCrash2(i64 %a, i32 %b) nounwind uwtable readnone ssp {
 105 entry:
 106   %tobool3 = icmp eq i64 %a, 0
 107   br i1 %tobool3, label %while.end, label %while.body
 108
 109 while.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
 118 while.end:                                        ; preds = %while.body, %entry
 119   %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
 120   ret i32 %c.0.lcssa
 121 }
 122
 123 define i32 @PopCntCrash3(i64 %a, i32 %x) {
 124 entry:
 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
 129 while.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
 138 while.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.
 145 define 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 ;
 167 entry:
 168   %tobool3 = icmp eq i64 %a, 0
 169   br i1 %tobool3, label %while.end, label %while.body
 170
 171 while.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
 180 while.end:                                        ; preds = %while.body, %entry
 181   %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
 182   ret i32 %c.0.lcssa
 183 }