Home | History | Annotate | Download | only in X86 
      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 
     77 ; Some variants once cause crash
     78 target triple = "x86_64-apple-macosx10.8.0"
     79 
     80 define i32 @PopCntCrash1(i64 %a) nounwind uwtable readnone ssp {
     81 entry:
     82   %tobool3 = icmp eq i64 %a, 0
     83   br i1 %tobool3, label %while.end, label %while.body
     84 
     85 while.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 
     95 while.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 
    103 define i32 @PopCntCrash2(i64 %a, i32 %b) nounwind uwtable readnone ssp {
    104 entry:
    105   %tobool3 = icmp eq i64 %a, 0
    106   br i1 %tobool3, label %while.end, label %while.body
    107 
    108 while.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 
    117 while.end:                                        ; preds = %while.body, %entry
    118   %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
    119   ret i32 %c.0.lcssa
    120 }
    121 
    122 define i32 @PopCntCrash3(i64 %a, i32 %x) {
    123 entry:
    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 
    128 while.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 
    137 while.end:                                        ; preds = %while.body, %entry
    138   %c.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
    139   ret i32 %c.0.lcssa
    140 }
    141