test/Transforms/LoopIdiom/popcnt.ll

   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
  16 define i32 @popcount(i64 %a) nounwind uwtable readnone ssp {
  17 entry:
  18   %tobool3 = icmp eq i64 %a, 0
  19   br i1 %tobool3, label %while.end, label %while.body
  20
  21 while.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
  30 while.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
  49 define i32 @popcount2(i64 %a, i32 %mydata1, i32 %mydata2) nounwind uwtable readnone ssp {
  50 entry:
  51   %tobool9 = icmp eq i64 %a, 0
  52   br i1 %tobool9, label %while.end, label %while.body
  53
  54 while.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
  68 while.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