test/Transforms/LoopIdiom/ARM/ctlz.ll

   1 ; RUN: opt -loop-idiom -mtriple=armv7a < %s -S | FileCheck -check-prefix=LZCNT --check-prefix=ALL %s
   2 ; RUN: opt -loop-idiom -mtriple=armv4t < %s -S | FileCheck -check-prefix=NOLZCNT --check-prefix=ALL %s
   3
   4 ; Recognize CTLZ builtin pattern.
   5 ; Here we'll just convert loop to countable,
   6 ; so do not insert builtin if CPU do not support CTLZ
   7 ;
   8 ; int ctlz_and_other(int n, char *a)
   9 ; {
  10 ;   n = n >= 0 ? n : -n;
  11 ;   int i = 0, n0 = n;
  12 ;   while(n >>= 1) {
  13 ;     a[i] = (n0 & (1 << i)) ? 1 : 0;
  14 ;     i++;
  15 ;   }
  16 ;   return i;
  17 ; }
  18 ;
  19 ; LZCNT:  entry
  20 ; LZCNT:  %0 = call i32 @llvm.ctlz.i32(i32 %shr8, i1 true)
  21 ; LZCNT-NEXT:  %1 = sub i32 32, %0
  22 ; LZCNT-NEXT:  %2 = zext i32 %1 to i64
  23 ; LZCNT:  %indvars.iv.next.lcssa = phi i64 [ %2, %while.body ]
  24 ; LZCNT:  %4 = trunc i64 %indvars.iv.next.lcssa to i32
  25 ; LZCNT:  %i.0.lcssa = phi i32 [ 0, %entry ], [ %4, %while.end.loopexit ]
  26 ; LZCNT:  ret i32 %i.0.lcssa
  27
  28 ; NOLZCNT:  entry
  29 ; NOLZCNT-NOT:  @llvm.ctlz
  30
  31 ; Function Attrs: norecurse nounwind uwtable
  32 define i32 @ctlz_and_other(i32 %n, i8* nocapture %a) {
  33 entry:
  34   %c = icmp sgt i32 %n, 0
  35   %negn = sub nsw i32 0, %n
  36   %abs_n = select i1 %c, i32 %n, i32 %negn
  37   %shr8 = lshr i32 %abs_n, 1
  38   %tobool9 = icmp eq i32 %shr8, 0
  39   br i1 %tobool9, label %while.end, label %while.body.preheader
  40
  41 while.body.preheader:                             ; preds = %entry
  42   br label %while.body
  43
  44 while.body:                                       ; preds = %while.body.preheader, %while.body
  45   %indvars.iv = phi i64 [ %indvars.iv.next, %while.body ], [ 0, %while.body.preheader ]
  46   %shr11 = phi i32 [ %shr, %while.body ], [ %shr8, %while.body.preheader ]
  47   %0 = trunc i64 %indvars.iv to i32
  48   %shl = shl i32 1, %0
  49   %and = and i32 %shl, %abs_n
  50   %tobool1 = icmp ne i32 %and, 0
  51   %conv = zext i1 %tobool1 to i8
  52   %arrayidx = getelementptr inbounds i8, i8* %a, i64 %indvars.iv
  53   store i8 %conv, i8* %arrayidx, align 1
  54   %indvars.iv.next = add nuw i64 %indvars.iv, 1
  55   %shr = ashr i32 %shr11, 1
  56   %tobool = icmp eq i32 %shr, 0
  57   br i1 %tobool, label %while.end.loopexit, label %while.body
  58
  59 while.end.loopexit:                               ; preds = %while.body
  60   %1 = trunc i64 %indvars.iv.next to i32
  61   br label %while.end
  62
  63 while.end:                                        ; preds = %while.end.loopexit, %entry
  64   %i.0.lcssa = phi i32 [ 0, %entry ], [ %1, %while.end.loopexit ]
  65   ret i32 %i.0.lcssa
  66 }
  67
  68 ; Recognize CTLZ builtin pattern.
  69 ; Here it will replace the loop -
  70 ; assume builtin is always profitable.
  71 ;
  72 ; int ctlz_zero_check(int n)
  73 ; {
  74 ;   n = n >= 0 ? n : -n;
  75 ;   int i = 0;
  76 ;   while(n) {
  77 ;     n >>= 1;
  78 ;     i++;
  79 ;   }
  80 ;   return i;
  81 ; }
  82 ;
  83 ; ALL:  entry
  84 ; ALL:  %0 = call i32 @llvm.ctlz.i32(i32 %abs_n, i1 true)
  85 ; ALL-NEXT:  %1 = sub i32 32, %0
  86 ; ALL:  %inc.lcssa = phi i32 [ %1, %while.body ]
  87 ; ALL:  %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc.lcssa, %while.end.loopexit ]
  88 ; ALL:  ret i32 %i.0.lcssa
  89
  90 ; Function Attrs: norecurse nounwind readnone uwtable
  91 define i32 @ctlz_zero_check(i32 %n) {
  92 entry:
  93   %c = icmp sgt i32 %n, 0
  94   %negn = sub nsw i32 0, %n
  95   %abs_n = select i1 %c, i32 %n, i32 %negn
  96   %tobool4 = icmp eq i32 %abs_n, 0
  97   br i1 %tobool4, label %while.end, label %while.body.preheader
  98
  99 while.body.preheader:                             ; preds = %entry
 100   br label %while.body
 101
 102 while.body:                                       ; preds = %while.body.preheader, %while.body
 103   %i.06 = phi i32 [ %inc, %while.body ], [ 0, %while.body.preheader ]
 104   %n.addr.05 = phi i32 [ %shr, %while.body ], [ %abs_n, %while.body.preheader ]
 105   %shr = ashr i32 %n.addr.05, 1
 106   %inc = add nsw i32 %i.06, 1
 107   %tobool = icmp eq i32 %shr, 0
 108   br i1 %tobool, label %while.end.loopexit, label %while.body
 109
 110 while.end.loopexit:                               ; preds = %while.body
 111   br label %while.end
 112
 113 while.end:                                        ; preds = %while.end.loopexit, %entry
 114   %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.end.loopexit ]
 115   ret i32 %i.0.lcssa
 116 }
 117
 118 ; Recognize CTLZ builtin pattern.
 119 ; Here it will replace the loop -
 120 ; assume builtin is always profitable.
 121 ;
 122 ; int ctlz(int n)
 123 ; {
 124 ;   n = n >= 0 ? n : -n;
 125 ;   int i = 0;
 126 ;   while(n >>= 1) {
 127 ;     i++;
 128 ;   }
 129 ;   return i;
 130 ; }
 131 ;
 132 ; ALL:  entry
 133 ; ALL:  %0 = ashr i32 %abs_n, 1
 134 ; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
 135 ; ALL-NEXT:  %2 = sub i32 32, %1
 136 ; ALL-NEXT:  %3 = add i32 %2, 1
 137 ; ALL:  %i.0.lcssa = phi i32 [ %2, %while.cond ]
 138 ; ALL:  ret i32 %i.0.lcssa
 139
 140 ; Function Attrs: norecurse nounwind readnone uwtable
 141 define i32 @ctlz(i32 %n) {
 142 entry:
 143   %c = icmp sgt i32 %n, 0
 144   %negn = sub nsw i32 0, %n
 145   %abs_n = select i1 %c, i32 %n, i32 %negn
 146   br label %while.cond
 147
 148 while.cond:                                       ; preds = %while.cond, %entry
 149   %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
 150   %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]
 151   %shr = ashr i32 %n.addr.0, 1
 152   %tobool = icmp eq i32 %shr, 0
 153   %inc = add nsw i32 %i.0, 1
 154   br i1 %tobool, label %while.end, label %while.cond
 155
 156 while.end:                                        ; preds = %while.cond
 157   ret i32 %i.0
 158 }
 159
 160 ; Recognize CTLZ builtin pattern.
 161 ; Here it will replace the loop -
 162 ; assume builtin is always profitable.
 163 ;
 164 ; int ctlz_add(int n, int i0)
 165 ; {
 166 ;   n = n >= 0 ? n : -n;
 167 ;   int i = i0;
 168 ;   while(n >>= 1) {
 169 ;     i++;
 170 ;   }
 171 ;   return i;
 172 ; }
 173 ;
 174 ; ALL:  entry
 175 ; ALL:  %0 = ashr i32 %abs_n, 1
 176 ; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
 177 ; ALL-NEXT:  %2 = sub i32 32, %1
 178 ; ALL-NEXT:  %3 = add i32 %2, 1
 179 ; ALL-NEXT:  %4 = add i32 %2, %i0
 180 ; ALL:  %i.0.lcssa = phi i32 [ %4, %while.cond ]
 181 ; ALL:  ret i32 %i.0.lcssa
 182 ;
 183 ; Function Attrs: norecurse nounwind readnone uwtable
 184 define i32 @ctlz_add(i32 %n, i32 %i0) {
 185 entry:
 186   %c = icmp sgt i32 %n, 0
 187   %negn = sub nsw i32 0, %n
 188   %abs_n = select i1 %c, i32 %n, i32 %negn
 189   br label %while.cond
 190
 191 while.cond:                                       ; preds = %while.cond, %entry
 192   %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
 193   %i.0 = phi i32 [ %i0, %entry ], [ %inc, %while.cond ]
 194   %shr = ashr i32 %n.addr.0, 1
 195   %tobool = icmp eq i32 %shr, 0
 196   %inc = add nsw i32 %i.0, 1
 197   br i1 %tobool, label %while.end, label %while.cond
 198
 199 while.end:                                        ; preds = %while.cond
 200   ret i32 %i.0
 201 }
 202
 203 ; Recognize CTLZ builtin pattern.
 204 ; Here it will replace the loop -
 205 ; assume builtin is always profitable.
 206 ;
 207 ; int ctlz_sext(short in)
 208 ; {
 209 ;   int n = in;
 210 ;   if (in < 0)
 211 ;     n = -n;
 212 ;   int i = 0;
 213 ;   while(n >>= 1) {
 214 ;     i++;
 215 ;   }
 216 ;   return i;
 217 ; }
 218 ;
 219 ; ALL:  entry
 220 ; ALL:  %0 = ashr i32 %abs_n, 1
 221 ; ALL-NEXT:  %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)
 222 ; ALL-NEXT:  %2 = sub i32 32, %1
 223 ; ALL-NEXT:  %3 = add i32 %2, 1
 224 ; ALL:  %i.0.lcssa = phi i32 [ %2, %while.cond ]
 225 ; ALL:  ret i32 %i.0.lcssa
 226
 227 ; Function Attrs: norecurse nounwind readnone uwtable
 228 define i32 @ctlz_sext(i16 %in) {
 229 entry:
 230   %n = sext i16 %in to i32
 231   %c = icmp sgt i16 %in, 0
 232   %negn = sub nsw i32 0, %n
 233   %abs_n = select i1 %c, i32 %n, i32 %negn
 234   br label %while.cond
 235
 236 while.cond:                                       ; preds = %while.cond, %entry
 237   %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]
 238   %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]
 239   %shr = ashr i32 %n.addr.0, 1
 240   %tobool = icmp eq i32 %shr, 0
 241   %inc = add nsw i32 %i.0, 1
 242   br i1 %tobool, label %while.end, label %while.cond
 243
 244 while.end:                                        ; preds = %while.cond
 245   ret i32 %i.0
 246 }