240 lines · plain
1; RUN: opt -passes=loop-idiom -mtriple=armv7a < %s -S | FileCheck -check-prefix=LZCNT --check-prefix=ALL %s2; RUN: opt -passes=loop-idiom -mtriple=armv4t < %s -S | FileCheck -check-prefix=NOLZCNT --check-prefix=ALL %s3 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 CTLZ7;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: entry20; LZCNT: %0 = call i32 @llvm.ctlz.i32(i32 %shr8, i1 true)21; LZCNT-NEXT: %1 = sub i32 32, %022; LZCNT-NEXT: %2 = zext i32 %1 to i6423; LZCNT: %indvars.iv.next.lcssa = phi i64 [ %2, %while.body ]24; LZCNT: %4 = trunc i64 %indvars.iv.next.lcssa to i3225; LZCNT: %i.0.lcssa = phi i32 [ 0, %entry ], [ %4, %while.end.loopexit ]26; LZCNT: ret i32 %i.0.lcssa27 28; NOLZCNT: entry29; NOLZCNT-NOT: @llvm.ctlz30 31; Function Attrs: norecurse nounwind uwtable32define i32 @ctlz_and_other(i32 %n, ptr nocapture %a) {33entry:34 %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)35 %shr8 = lshr i32 %abs_n, 136 %tobool9 = icmp eq i32 %shr8, 037 br i1 %tobool9, label %while.end, label %while.body.preheader38 39while.body.preheader: ; preds = %entry40 br label %while.body41 42while.body: ; preds = %while.body.preheader, %while.body43 %indvars.iv = phi i64 [ %indvars.iv.next, %while.body ], [ 0, %while.body.preheader ]44 %shr11 = phi i32 [ %shr, %while.body ], [ %shr8, %while.body.preheader ]45 %0 = trunc i64 %indvars.iv to i3246 %shl = shl i32 1, %047 %and = and i32 %shl, %abs_n48 %tobool1 = icmp ne i32 %and, 049 %conv = zext i1 %tobool1 to i850 %arrayidx = getelementptr inbounds i8, ptr %a, i64 %indvars.iv51 store i8 %conv, ptr %arrayidx, align 152 %indvars.iv.next = add nuw i64 %indvars.iv, 153 %shr = ashr i32 %shr11, 154 %tobool = icmp eq i32 %shr, 055 br i1 %tobool, label %while.end.loopexit, label %while.body56 57while.end.loopexit: ; preds = %while.body58 %1 = trunc i64 %indvars.iv.next to i3259 br label %while.end60 61while.end: ; preds = %while.end.loopexit, %entry62 %i.0.lcssa = phi i32 [ 0, %entry ], [ %1, %while.end.loopexit ]63 ret i32 %i.0.lcssa64}65 66; Recognize CTLZ builtin pattern.67; Here it will replace the loop -68; assume builtin is always profitable.69;70; int ctlz_zero_check(int n)71; {72; n = n >= 0 ? n : -n;73; int i = 0;74; while(n) {75; n >>= 1;76; i++;77; }78; return i;79; }80;81; ALL: entry82; ALL: %0 = call i32 @llvm.ctlz.i32(i32 %abs_n, i1 true)83; ALL-NEXT: %1 = sub i32 32, %084; ALL: %inc.lcssa = phi i32 [ %1, %while.body ]85; ALL: %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc.lcssa, %while.end.loopexit ]86; ALL: ret i32 %i.0.lcssa87 88; Function Attrs: norecurse nounwind readnone uwtable89define i32 @ctlz_zero_check(i32 %n) {90entry:91 %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)92 %tobool4 = icmp eq i32 %abs_n, 093 br i1 %tobool4, label %while.end, label %while.body.preheader94 95while.body.preheader: ; preds = %entry96 br label %while.body97 98while.body: ; preds = %while.body.preheader, %while.body99 %i.06 = phi i32 [ %inc, %while.body ], [ 0, %while.body.preheader ]100 %n.addr.05 = phi i32 [ %shr, %while.body ], [ %abs_n, %while.body.preheader ]101 %shr = ashr i32 %n.addr.05, 1102 %inc = add nsw i32 %i.06, 1103 %tobool = icmp eq i32 %shr, 0104 br i1 %tobool, label %while.end.loopexit, label %while.body105 106while.end.loopexit: ; preds = %while.body107 br label %while.end108 109while.end: ; preds = %while.end.loopexit, %entry110 %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.end.loopexit ]111 ret i32 %i.0.lcssa112}113 114; Recognize CTLZ builtin pattern.115; Here it will replace the loop -116; assume builtin is always profitable.117;118; int ctlz(int n)119; {120; n = n >= 0 ? n : -n;121; int i = 0;122; while(n >>= 1) {123; i++;124; }125; return i;126; }127;128; ALL: entry129; ALL: %0 = ashr i32 %abs_n, 1130; ALL-NEXT: %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)131; ALL-NEXT: %2 = sub i32 32, %1132; ALL-NEXT: %3 = add i32 %2, 1133; ALL: %i.0.lcssa = phi i32 [ %2, %while.cond ]134; ALL: ret i32 %i.0.lcssa135 136; Function Attrs: norecurse nounwind readnone uwtable137define i32 @ctlz(i32 %n) {138entry:139 %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)140 br label %while.cond141 142while.cond: ; preds = %while.cond, %entry143 %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]144 %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]145 %shr = ashr i32 %n.addr.0, 1146 %tobool = icmp eq i32 %shr, 0147 %inc = add nsw i32 %i.0, 1148 br i1 %tobool, label %while.end, label %while.cond149 150while.end: ; preds = %while.cond151 ret i32 %i.0152}153 154; Recognize CTLZ builtin pattern.155; Here it will replace the loop -156; assume builtin is always profitable.157;158; int ctlz_add(int n, int i0)159; {160; n = n >= 0 ? n : -n;161; int i = i0;162; while(n >>= 1) {163; i++;164; }165; return i;166; }167;168; ALL: entry169; ALL: %0 = ashr i32 %abs_n, 1170; ALL-NEXT: %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)171; ALL-NEXT: %2 = sub i32 32, %1172; ALL-NEXT: %3 = add i32 %2, 1173; ALL-NEXT: %4 = add i32 %2, %i0174; ALL: %i.0.lcssa = phi i32 [ %4, %while.cond ]175; ALL: ret i32 %i.0.lcssa176;177; Function Attrs: norecurse nounwind readnone uwtable178define i32 @ctlz_add(i32 %n, i32 %i0) {179entry:180 %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)181 br label %while.cond182 183while.cond: ; preds = %while.cond, %entry184 %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]185 %i.0 = phi i32 [ %i0, %entry ], [ %inc, %while.cond ]186 %shr = ashr i32 %n.addr.0, 1187 %tobool = icmp eq i32 %shr, 0188 %inc = add nsw i32 %i.0, 1189 br i1 %tobool, label %while.end, label %while.cond190 191while.end: ; preds = %while.cond192 ret i32 %i.0193}194 195; Recognize CTLZ builtin pattern.196; Here it will replace the loop -197; assume builtin is always profitable.198;199; int ctlz_sext(short in)200; {201; int n = in;202; if (in < 0)203; n = -n;204; int i = 0;205; while(n >>= 1) {206; i++;207; }208; return i;209; }210;211; ALL: entry212; ALL: %0 = ashr i32 %abs_n, 1213; ALL-NEXT: %1 = call i32 @llvm.ctlz.i32(i32 %0, i1 false)214; ALL-NEXT: %2 = sub i32 32, %1215; ALL-NEXT: %3 = add i32 %2, 1216; ALL: %i.0.lcssa = phi i32 [ %2, %while.cond ]217; ALL: ret i32 %i.0.lcssa218 219; Function Attrs: norecurse nounwind readnone uwtable220define i32 @ctlz_sext(i16 %in) {221entry:222 %abs = call i16 @llvm.abs.i16(i16 %in, i1 false)223 %abs_n = zext i16 %abs to i32224 br label %while.cond225 226while.cond: ; preds = %while.cond, %entry227 %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]228 %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]229 %shr = ashr i32 %n.addr.0, 1230 %tobool = icmp eq i32 %shr, 0231 %inc = add nsw i32 %i.0, 1232 br i1 %tobool, label %while.end, label %while.cond233 234while.end: ; preds = %while.cond235 ret i32 %i.0236}237 238declare i32 @llvm.abs.i32(i32, i1)239declare i16 @llvm.abs.i16(i16, i1)240