769 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -passes=loop-idiom -mtriple=x86_64 -mcpu=core-avx2 < %s -S | FileCheck %s -check-prefixes=ALL,LZCNT3; RUN: opt -passes=loop-idiom -mtriple=x86_64 -mcpu=corei7 < %s -S | FileCheck %s -check-prefixes=ALL,NOLZCNT4 5; Recognize CTLZ builtin pattern.6; Here we'll just convert loop to countable,7; so do not insert builtin if CPU do not support CTLZ8;9; int ctlz_and_other(int n, char *a)10; {11; n = n >= 0 ? n : -n;12; int i = 0, n0 = n;13; while(n >>= 1) {14; a[i] = (n0 & (1 << i)) ? 1 : 0;15; i++;16; }17; return i;18; }19;20define i32 @ctlz_and_other(i32 %n, ptr nocapture %a) {21; LZCNT-LABEL: @ctlz_and_other(22; LZCNT-NEXT: entry:23; LZCNT-NEXT: [[ABS_N:%.*]] = call i32 @llvm.abs.i32(i32 [[N:%.*]], i1 true)24; LZCNT-NEXT: [[SHR8:%.*]] = lshr i32 [[ABS_N]], 125; LZCNT-NEXT: [[TOBOOL9:%.*]] = icmp eq i32 [[SHR8]], 026; LZCNT-NEXT: br i1 [[TOBOOL9]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]27; LZCNT: while.body.preheader:28; LZCNT-NEXT: [[TMP0:%.*]] = call i32 @llvm.ctlz.i32(i32 [[SHR8]], i1 true)29; LZCNT-NEXT: [[TMP1:%.*]] = sub i32 32, [[TMP0]]30; LZCNT-NEXT: [[TMP2:%.*]] = zext i32 [[TMP1]] to i6431; LZCNT-NEXT: br label [[WHILE_BODY:%.*]]32; LZCNT: while.body:33; LZCNT-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]34; LZCNT-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]35; LZCNT-NEXT: [[SHR11:%.*]] = phi i32 [ [[SHR:%.*]], [[WHILE_BODY]] ], [ [[SHR8]], [[WHILE_BODY_PREHEADER]] ]36; LZCNT-NEXT: [[TMP3:%.*]] = trunc i64 [[INDVARS_IV]] to i3237; LZCNT-NEXT: [[SHL:%.*]] = shl i32 1, [[TMP3]]38; LZCNT-NEXT: [[AND:%.*]] = and i32 [[SHL]], [[ABS_N]]39; LZCNT-NEXT: [[TOBOOL1:%.*]] = icmp ne i32 [[AND]], 040; LZCNT-NEXT: [[CONV:%.*]] = zext i1 [[TOBOOL1]] to i841; LZCNT-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i8, ptr [[A:%.*]], i64 [[INDVARS_IV]]42; LZCNT-NEXT: store i8 [[CONV]], ptr [[ARRAYIDX]], align 143; LZCNT-NEXT: [[INDVARS_IV_NEXT]] = add nuw i64 [[INDVARS_IV]], 144; LZCNT-NEXT: [[SHR]] = ashr i32 [[SHR11]], 145; LZCNT-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 146; LZCNT-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 047; LZCNT-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]48; LZCNT: while.end.loopexit:49; LZCNT-NEXT: [[INDVARS_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[TMP2]], [[WHILE_BODY]] ]50; LZCNT-NEXT: [[TMP4:%.*]] = trunc i64 [[INDVARS_IV_NEXT_LCSSA]] to i3251; LZCNT-NEXT: br label [[WHILE_END]]52; LZCNT: while.end:53; LZCNT-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP4]], [[WHILE_END_LOOPEXIT]] ]54; LZCNT-NEXT: ret i32 [[I_0_LCSSA]]55;56; NOLZCNT-LABEL: @ctlz_and_other(57; NOLZCNT-NEXT: entry:58; NOLZCNT-NEXT: [[ABS_N:%.*]] = call i32 @llvm.abs.i32(i32 [[N:%.*]], i1 true)59; NOLZCNT-NEXT: [[SHR8:%.*]] = lshr i32 [[ABS_N]], 160; NOLZCNT-NEXT: [[TOBOOL9:%.*]] = icmp eq i32 [[SHR8]], 061; NOLZCNT-NEXT: br i1 [[TOBOOL9]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]62; NOLZCNT: while.body.preheader:63; NOLZCNT-NEXT: br label [[WHILE_BODY:%.*]]64; NOLZCNT: while.body:65; NOLZCNT-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]66; NOLZCNT-NEXT: [[SHR11:%.*]] = phi i32 [ [[SHR:%.*]], [[WHILE_BODY]] ], [ [[SHR8]], [[WHILE_BODY_PREHEADER]] ]67; NOLZCNT-NEXT: [[TMP0:%.*]] = trunc i64 [[INDVARS_IV]] to i3268; NOLZCNT-NEXT: [[SHL:%.*]] = shl i32 1, [[TMP0]]69; NOLZCNT-NEXT: [[AND:%.*]] = and i32 [[SHL]], [[ABS_N]]70; NOLZCNT-NEXT: [[TOBOOL1:%.*]] = icmp ne i32 [[AND]], 071; NOLZCNT-NEXT: [[CONV:%.*]] = zext i1 [[TOBOOL1]] to i872; NOLZCNT-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i8, ptr [[A:%.*]], i64 [[INDVARS_IV]]73; NOLZCNT-NEXT: store i8 [[CONV]], ptr [[ARRAYIDX]], align 174; NOLZCNT-NEXT: [[INDVARS_IV_NEXT]] = add nuw i64 [[INDVARS_IV]], 175; NOLZCNT-NEXT: [[SHR]] = ashr i32 [[SHR11]], 176; NOLZCNT-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[SHR]], 077; NOLZCNT-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]78; NOLZCNT: while.end.loopexit:79; NOLZCNT-NEXT: [[INDVARS_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[INDVARS_IV_NEXT]], [[WHILE_BODY]] ]80; NOLZCNT-NEXT: [[TMP1:%.*]] = trunc i64 [[INDVARS_IV_NEXT_LCSSA]] to i3281; NOLZCNT-NEXT: br label [[WHILE_END]]82; NOLZCNT: while.end:83; NOLZCNT-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP1]], [[WHILE_END_LOOPEXIT]] ]84; NOLZCNT-NEXT: ret i32 [[I_0_LCSSA]]85;86entry:87 %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)88 %shr8 = lshr i32 %abs_n, 189 %tobool9 = icmp eq i32 %shr8, 090 br i1 %tobool9, label %while.end, label %while.body.preheader91 92while.body.preheader: ; preds = %entry93 br label %while.body94 95while.body: ; preds = %while.body.preheader, %while.body96 %indvars.iv = phi i64 [ %indvars.iv.next, %while.body ], [ 0, %while.body.preheader ]97 %shr11 = phi i32 [ %shr, %while.body ], [ %shr8, %while.body.preheader ]98 %0 = trunc i64 %indvars.iv to i3299 %shl = shl i32 1, %0100 %and = and i32 %shl, %abs_n101 %tobool1 = icmp ne i32 %and, 0102 %conv = zext i1 %tobool1 to i8103 %arrayidx = getelementptr inbounds i8, ptr %a, i64 %indvars.iv104 store i8 %conv, ptr %arrayidx, align 1105 %indvars.iv.next = add nuw i64 %indvars.iv, 1106 %shr = ashr i32 %shr11, 1107 %tobool = icmp eq i32 %shr, 0108 br i1 %tobool, label %while.end.loopexit, label %while.body109 110while.end.loopexit: ; preds = %while.body111 %1 = trunc i64 %indvars.iv.next to i32112 br label %while.end113 114while.end: ; preds = %while.end.loopexit, %entry115 %i.0.lcssa = phi i32 [ 0, %entry ], [ %1, %while.end.loopexit ]116 ret i32 %i.0.lcssa117}118 119; Recognize CTLZ builtin pattern.120; Here it will replace the loop -121; assume builtin is always profitable.122;123; int ctlz_zero_check(int n)124; {125; n = n >= 0 ? n : -n;126; int i = 0;127; while(n) {128; n >>= 1;129; i++;130; }131; return i;132; }133;134define i32 @ctlz_zero_check(i32 %n) {135; ALL-LABEL: @ctlz_zero_check(136; ALL-NEXT: entry:137; ALL-NEXT: [[ABS_N:%.*]] = call i32 @llvm.abs.i32(i32 [[N:%.*]], i1 true)138; ALL-NEXT: [[TOBOOL4:%.*]] = icmp eq i32 [[ABS_N]], 0139; ALL-NEXT: br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]140; ALL: while.body.preheader:141; ALL-NEXT: [[TMP0:%.*]] = call i32 @llvm.ctlz.i32(i32 [[ABS_N]], i1 true)142; ALL-NEXT: [[TMP1:%.*]] = sub i32 32, [[TMP0]]143; ALL-NEXT: br label [[WHILE_BODY:%.*]]144; ALL: while.body:145; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]146; ALL-NEXT: [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]147; ALL-NEXT: [[N_ADDR_05:%.*]] = phi i32 [ [[SHR:%.*]], [[WHILE_BODY]] ], [ [[ABS_N]], [[WHILE_BODY_PREHEADER]] ]148; ALL-NEXT: [[SHR]] = ashr i32 [[N_ADDR_05]], 1149; ALL-NEXT: [[INC]] = add nsw i32 [[I_06]], 1150; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1151; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0152; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]153; ALL: while.end.loopexit:154; ALL-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY]] ]155; ALL-NEXT: br label [[WHILE_END]]156; ALL: while.end:157; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]158; ALL-NEXT: ret i32 [[I_0_LCSSA]]159;160entry:161 %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)162 %tobool4 = icmp eq i32 %abs_n, 0163 br i1 %tobool4, label %while.end, label %while.body.preheader164 165while.body.preheader: ; preds = %entry166 br label %while.body167 168while.body: ; preds = %while.body.preheader, %while.body169 %i.06 = phi i32 [ %inc, %while.body ], [ 0, %while.body.preheader ]170 %n.addr.05 = phi i32 [ %shr, %while.body ], [ %abs_n, %while.body.preheader ]171 %shr = ashr i32 %n.addr.05, 1172 %inc = add nsw i32 %i.06, 1173 %tobool = icmp eq i32 %shr, 0174 br i1 %tobool, label %while.end.loopexit, label %while.body175 176while.end.loopexit: ; preds = %while.body177 br label %while.end178 179while.end: ; preds = %while.end.loopexit, %entry180 %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.end.loopexit ]181 ret i32 %i.0.lcssa182}183 184; Recognize CTLZ builtin pattern.185; Here it will replace the loop -186; assume builtin is always profitable.187;188; int ctlz_zero_check_lshr(int n)189; {190; int i = 0;191; while(n) {192; n >>= 1;193; i++;194; }195; return i;196; }197;198define i32 @ctlz_zero_check_lshr(i32 %n) {199; ALL-LABEL: @ctlz_zero_check_lshr(200; ALL-NEXT: entry:201; ALL-NEXT: [[TOBOOL4:%.*]] = icmp eq i32 [[N:%.*]], 0202; ALL-NEXT: br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]203; ALL: while.body.preheader:204; ALL-NEXT: [[TMP0:%.*]] = call i32 @llvm.ctlz.i32(i32 [[N]], i1 true)205; ALL-NEXT: [[TMP1:%.*]] = sub i32 32, [[TMP0]]206; ALL-NEXT: br label [[WHILE_BODY:%.*]]207; ALL: while.body:208; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]209; ALL-NEXT: [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]210; ALL-NEXT: [[N_ADDR_05:%.*]] = phi i32 [ [[SHR:%.*]], [[WHILE_BODY]] ], [ [[N]], [[WHILE_BODY_PREHEADER]] ]211; ALL-NEXT: [[SHR]] = lshr i32 [[N_ADDR_05]], 1212; ALL-NEXT: [[INC]] = add nsw i32 [[I_06]], 1213; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1214; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0215; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]216; ALL: while.end.loopexit:217; ALL-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY]] ]218; ALL-NEXT: br label [[WHILE_END]]219; ALL: while.end:220; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]221; ALL-NEXT: ret i32 [[I_0_LCSSA]]222;223entry:224 %tobool4 = icmp eq i32 %n, 0225 br i1 %tobool4, label %while.end, label %while.body.preheader226 227while.body.preheader: ; preds = %entry228 br label %while.body229 230while.body: ; preds = %while.body.preheader, %while.body231 %i.06 = phi i32 [ %inc, %while.body ], [ 0, %while.body.preheader ]232 %n.addr.05 = phi i32 [ %shr, %while.body ], [ %n, %while.body.preheader ]233 %shr = lshr i32 %n.addr.05, 1234 %inc = add nsw i32 %i.06, 1235 %tobool = icmp eq i32 %shr, 0236 br i1 %tobool, label %while.end.loopexit, label %while.body237 238while.end.loopexit: ; preds = %while.body239 br label %while.end240 241while.end: ; preds = %while.end.loopexit, %entry242 %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.end.loopexit ]243 ret i32 %i.0.lcssa244}245 246; Recognize CTLZ builtin pattern.247; Here it will replace the loop -248; assume builtin is always profitable.249;250; int ctlz(int n)251; {252; n = n >= 0 ? n : -n;253; int i = 0;254; while(n >>= 1) {255; i++;256; }257; return i;258; }259;260define i32 @ctlz(i32 %n) {261; ALL-LABEL: @ctlz(262; ALL-NEXT: entry:263; ALL-NEXT: [[ABS_N:%.*]] = call i32 @llvm.abs.i32(i32 [[N:%.*]], i1 true)264; ALL-NEXT: [[TMP0:%.*]] = ashr i32 [[ABS_N]], 1265; ALL-NEXT: [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[TMP0]], i1 false)266; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]267; ALL-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1268; ALL-NEXT: br label [[WHILE_COND:%.*]]269; ALL: while.cond:270; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]271; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[ABS_N]], [[ENTRY]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]272; ALL-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]273; ALL-NEXT: [[SHR]] = ashr i32 [[N_ADDR_0]], 1274; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1275; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0276; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], 1277; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]278; ALL: while.end:279; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[WHILE_COND]] ]280; ALL-NEXT: ret i32 [[I_0_LCSSA]]281;282entry:283 %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)284 br label %while.cond285 286while.cond: ; preds = %while.cond, %entry287 %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]288 %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]289 %shr = ashr i32 %n.addr.0, 1290 %tobool = icmp eq i32 %shr, 0291 %inc = add nsw i32 %i.0, 1292 br i1 %tobool, label %while.end, label %while.cond293 294while.end: ; preds = %while.cond295 ret i32 %i.0296}297 298; Recognize CTLZ builtin pattern.299; Here it will replace the loop -300; assume builtin is always profitable.301;302; int ctlz_lshr(int n)303; {304; int i = 0;305; while(n >>= 1) {306; i++;307; }308; return i;309; }310;311define i32 @ctlz_lshr(i32 %n) {312; ALL-LABEL: @ctlz_lshr(313; ALL-NEXT: entry:314; ALL-NEXT: [[TMP0:%.*]] = lshr i32 [[N:%.*]], 1315; ALL-NEXT: [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[TMP0]], i1 false)316; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]317; ALL-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1318; ALL-NEXT: br label [[WHILE_COND:%.*]]319; ALL: while.cond:320; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]321; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]322; ALL-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]323; ALL-NEXT: [[SHR]] = lshr i32 [[N_ADDR_0]], 1324; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1325; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0326; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], 1327; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]328; ALL: while.end:329; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[WHILE_COND]] ]330; ALL-NEXT: ret i32 [[I_0_LCSSA]]331;332entry:333 br label %while.cond334 335while.cond: ; preds = %while.cond, %entry336 %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]337 %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]338 %shr = lshr i32 %n.addr.0, 1339 %tobool = icmp eq i32 %shr, 0340 %inc = add nsw i32 %i.0, 1341 br i1 %tobool, label %while.end, label %while.cond342 343while.end: ; preds = %while.cond344 ret i32 %i.0345}346 347; Recognize CTLZ builtin pattern.348; Here it will replace the loop -349; assume builtin is always profitable.350;351; int ctlz_add(int n, int i0)352; {353; n = n >= 0 ? n : -n;354; int i = i0;355; while(n >>= 1) {356; i++;357; }358; return i;359; }360;361define i32 @ctlz_add(i32 %n, i32 %i0) {362; ALL-LABEL: @ctlz_add(363; ALL-NEXT: entry:364; ALL-NEXT: [[ABS_N:%.*]] = call i32 @llvm.abs.i32(i32 [[N:%.*]], i1 true)365; ALL-NEXT: [[TMP0:%.*]] = ashr i32 [[ABS_N]], 1366; ALL-NEXT: [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[TMP0]], i1 false)367; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]368; ALL-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1369; ALL-NEXT: [[TMP4:%.*]] = add i32 [[TMP2]], [[I0:%.*]]370; ALL-NEXT: br label [[WHILE_COND:%.*]]371; ALL: while.cond:372; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]373; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[ABS_N]], [[ENTRY]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]374; ALL-NEXT: [[I_0:%.*]] = phi i32 [ [[I0]], [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]375; ALL-NEXT: [[SHR]] = ashr i32 [[N_ADDR_0]], 1376; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1377; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0378; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], 1379; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]380; ALL: while.end:381; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP4]], [[WHILE_COND]] ]382; ALL-NEXT: ret i32 [[I_0_LCSSA]]383;384entry:385 %abs_n = call i32 @llvm.abs.i32(i32 %n, i1 true)386 br label %while.cond387 388while.cond: ; preds = %while.cond, %entry389 %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]390 %i.0 = phi i32 [ %i0, %entry ], [ %inc, %while.cond ]391 %shr = ashr i32 %n.addr.0, 1392 %tobool = icmp eq i32 %shr, 0393 %inc = add nsw i32 %i.0, 1394 br i1 %tobool, label %while.end, label %while.cond395 396while.end: ; preds = %while.cond397 ret i32 %i.0398}399 400; Recognize CTLZ builtin pattern.401; Here it will replace the loop -402; assume builtin is always profitable.403;404; int ctlz_add_lshr(int n, int i0)405; {406; int i = i0;407; while(n >>= 1) {408; i++;409; }410; return i;411; }412;413define i32 @ctlz_add_lshr(i32 %n, i32 %i0) {414; ALL-LABEL: @ctlz_add_lshr(415; ALL-NEXT: entry:416; ALL-NEXT: [[TMP0:%.*]] = lshr i32 [[N:%.*]], 1417; ALL-NEXT: [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[TMP0]], i1 false)418; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]419; ALL-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1420; ALL-NEXT: [[TMP4:%.*]] = add i32 [[TMP2]], [[I0:%.*]]421; ALL-NEXT: br label [[WHILE_COND:%.*]]422; ALL: while.cond:423; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]424; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]425; ALL-NEXT: [[I_0:%.*]] = phi i32 [ [[I0]], [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]426; ALL-NEXT: [[SHR]] = lshr i32 [[N_ADDR_0]], 1427; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1428; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0429; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], 1430; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]431; ALL: while.end:432; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP4]], [[WHILE_COND]] ]433; ALL-NEXT: ret i32 [[I_0_LCSSA]]434;435entry:436 br label %while.cond437 438while.cond: ; preds = %while.cond, %entry439 %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]440 %i.0 = phi i32 [ %i0, %entry ], [ %inc, %while.cond ]441 %shr = lshr i32 %n.addr.0, 1442 %tobool = icmp eq i32 %shr, 0443 %inc = add nsw i32 %i.0, 1444 br i1 %tobool, label %while.end, label %while.cond445 446while.end: ; preds = %while.cond447 ret i32 %i.0448}449 450; Recognize CTLZ builtin pattern.451; Here it will replace the loop -452; assume builtin is always profitable.453;454; int ctlz_sext(short in)455; {456; int n = in;457; if (in < 0)458; n = -n;459; int i = 0;460; while(n >>= 1) {461; i++;462; }463; return i;464; }465;466define i32 @ctlz_sext(i16 %in) {467; ALL-LABEL: @ctlz_sext(468; ALL-NEXT: entry:469; ALL-NEXT: [[ABS:%.*]] = call i16 @llvm.abs.i16(i16 [[IN:%.*]], i1 false)470; ALL-NEXT: [[ABS_N:%.*]] = zext i16 [[ABS]] to i32471; ALL-NEXT: [[TMP0:%.*]] = ashr i32 [[ABS_N]], 1472; ALL-NEXT: [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[TMP0]], i1 false)473; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]474; ALL-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1475; ALL-NEXT: br label [[WHILE_COND:%.*]]476; ALL: while.cond:477; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]478; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[ABS_N]], [[ENTRY]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]479; ALL-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]480; ALL-NEXT: [[SHR]] = ashr i32 [[N_ADDR_0]], 1481; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1482; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0483; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], 1484; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]485; ALL: while.end:486; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[WHILE_COND]] ]487; ALL-NEXT: ret i32 [[I_0_LCSSA]]488;489entry:490 %abs = call i16 @llvm.abs.i16(i16 %in, i1 false)491 %abs_n = zext i16 %abs to i32492 br label %while.cond493 494while.cond: ; preds = %while.cond, %entry495 %n.addr.0 = phi i32 [ %abs_n, %entry ], [ %shr, %while.cond ]496 %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]497 %shr = ashr i32 %n.addr.0, 1498 %tobool = icmp eq i32 %shr, 0499 %inc = add nsw i32 %i.0, 1500 br i1 %tobool, label %while.end, label %while.cond501 502while.end: ; preds = %while.cond503 ret i32 %i.0504}505 506; Recognize CTLZ builtin pattern.507; Here it will replace the loop -508; assume builtin is always profitable.509;510; int ctlz_sext_lshr(short in)511; {512; int i = 0;513; while(in >>= 1) {514; i++;515; }516; return i;517; }518;519define i32 @ctlz_sext_lshr(i16 %in) {520; ALL-LABEL: @ctlz_sext_lshr(521; ALL-NEXT: entry:522; ALL-NEXT: [[N:%.*]] = sext i16 [[IN:%.*]] to i32523; ALL-NEXT: [[TMP0:%.*]] = lshr i32 [[N]], 1524; ALL-NEXT: [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[TMP0]], i1 false)525; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]526; ALL-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1527; ALL-NEXT: br label [[WHILE_COND:%.*]]528; ALL: while.cond:529; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]530; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]531; ALL-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]532; ALL-NEXT: [[SHR]] = lshr i32 [[N_ADDR_0]], 1533; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1534; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0535; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], 1536; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]537; ALL: while.end:538; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[WHILE_COND]] ]539; ALL-NEXT: ret i32 [[I_0_LCSSA]]540;541entry:542 %n = sext i16 %in to i32543 br label %while.cond544 545while.cond: ; preds = %while.cond, %entry546 %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]547 %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]548 %shr = lshr i32 %n.addr.0, 1549 %tobool = icmp eq i32 %shr, 0550 %inc = add nsw i32 %i.0, 1551 br i1 %tobool, label %while.end, label %while.cond552 553while.end: ; preds = %while.cond554 ret i32 %i.0555}556 557; This loop contains a volatile store. If x is initially negative,558; the code will be an infinite loop because the ashr will eventually produce559; all ones and continue doing so. This prevents the loop from terminating. If560; we convert this to a countable loop using ctlz that loop will only run 32561; times. This is different than the infinite number of times of the original.562define i32 @foo(i32 %x) {563; ALL-LABEL: @foo(564; ALL-NEXT: entry:565; ALL-NEXT: [[V:%.*]] = alloca i8, align 1566; ALL-NEXT: [[TOBOOL4:%.*]] = icmp eq i32 [[X:%.*]], 0567; ALL-NEXT: br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_LR_PH:%.*]]568; ALL: while.body.lr.ph:569; ALL-NEXT: br label [[WHILE_BODY:%.*]]570; ALL: while.body:571; ALL-NEXT: [[CNT_06:%.*]] = phi i32 [ 0, [[WHILE_BODY_LR_PH]] ], [ [[INC:%.*]], [[WHILE_BODY]] ]572; ALL-NEXT: [[X_ADDR_05:%.*]] = phi i32 [ [[X]], [[WHILE_BODY_LR_PH]] ], [ [[SHR:%.*]], [[WHILE_BODY]] ]573; ALL-NEXT: [[SHR]] = ashr i32 [[X_ADDR_05]], 1574; ALL-NEXT: [[INC]] = add i32 [[CNT_06]], 1575; ALL-NEXT: store volatile i8 42, ptr [[V]], align 1576; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[SHR]], 0577; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_COND_WHILE_END_CRIT_EDGE:%.*]], label [[WHILE_BODY]]578; ALL: while.cond.while.end_crit_edge:579; ALL-NEXT: [[SPLIT:%.*]] = phi i32 [ [[INC]], [[WHILE_BODY]] ]580; ALL-NEXT: br label [[WHILE_END]]581; ALL: while.end:582; ALL-NEXT: [[CNT_0_LCSSA:%.*]] = phi i32 [ [[SPLIT]], [[WHILE_COND_WHILE_END_CRIT_EDGE]] ], [ 0, [[ENTRY:%.*]] ]583; ALL-NEXT: ret i32 [[CNT_0_LCSSA]]584;585entry:586 %v = alloca i8, align 1587 %tobool4 = icmp eq i32 %x, 0588 br i1 %tobool4, label %while.end, label %while.body.lr.ph589 590while.body.lr.ph: ; preds = %entry591 br label %while.body592 593while.body: ; preds = %while.body.lr.ph, %while.body594 %cnt.06 = phi i32 [ 0, %while.body.lr.ph ], [ %inc, %while.body ]595 %x.addr.05 = phi i32 [ %x, %while.body.lr.ph ], [ %shr, %while.body ]596 %shr = ashr i32 %x.addr.05, 1597 %inc = add i32 %cnt.06, 1598 store volatile i8 42, ptr %v, align 1599 %tobool = icmp eq i32 %shr, 0600 br i1 %tobool, label %while.cond.while.end_crit_edge, label %while.body601 602while.cond.while.end_crit_edge: ; preds = %while.body603 %split = phi i32 [ %inc, %while.body ]604 br label %while.end605 606while.end: ; preds = %while.cond.while.end_crit_edge, %entry607 %cnt.0.lcssa = phi i32 [ %split, %while.cond.while.end_crit_edge ], [ 0, %entry ]608 ret i32 %cnt.0.lcssa609}610 611; We can't easily transform this loop. It returns 1 for an input of both612; 0 and 1.613;614; int ctlz_bad(unsigned n)615; {616; int i = 0;617; do {618; i++;619; n >>= 1;620; } while(n != 0) {621; return i;622; }623;624define i32 @ctlz_bad(i32 %n) {625; ALL-LABEL: @ctlz_bad(626; ALL-NEXT: entry:627; ALL-NEXT: br label [[WHILE_COND:%.*]]628; ALL: while.cond:629; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[N:%.*]], [[ENTRY:%.*]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]630; ALL-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]631; ALL-NEXT: [[SHR]] = lshr i32 [[N_ADDR_0]], 1632; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[SHR]], 0633; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], 1634; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]635; ALL: while.end:636; ALL-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[INC]], [[WHILE_COND]] ]637; ALL-NEXT: ret i32 [[INC_LCSSA]]638;639entry:640 br label %while.cond641 642while.cond: ; preds = %while.cond, %entry643 %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]644 %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]645 %shr = lshr i32 %n.addr.0, 1646 %tobool = icmp eq i32 %shr, 0647 %inc = add nsw i32 %i.0, 1648 br i1 %tobool, label %while.end, label %while.cond649 650while.end: ; preds = %while.cond651 ret i32 %inc652}653 654; Recognize CTLZ builtin pattern.655; Here it will replace the loop -656; assume builtin is always profitable.657;658; int ctlz_decrement(int n)659; {660; int i = 32;661; while(n) {662; n >>= 1;663; i--;664; }665; return i;666; }667;668define i32 @ctlz_decrement(i32 %n) {669; ALL-LABEL: @ctlz_decrement(670; ALL-NEXT: entry:671; ALL-NEXT: [[TOBOOL4:%.*]] = icmp eq i32 [[N:%.*]], 0672; ALL-NEXT: br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]673; ALL: while.body.preheader:674; ALL-NEXT: [[TMP0:%.*]] = call i32 @llvm.ctlz.i32(i32 [[N]], i1 true)675; ALL-NEXT: [[TMP1:%.*]] = sub i32 32, [[TMP0]]676; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]677; ALL-NEXT: br label [[WHILE_BODY:%.*]]678; ALL: while.body:679; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]680; ALL-NEXT: [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 32, [[WHILE_BODY_PREHEADER]] ]681; ALL-NEXT: [[N_ADDR_05:%.*]] = phi i32 [ [[SHR:%.*]], [[WHILE_BODY]] ], [ [[N]], [[WHILE_BODY_PREHEADER]] ]682; ALL-NEXT: [[SHR]] = lshr i32 [[N_ADDR_05]], 1683; ALL-NEXT: [[INC]] = add nsw i32 [[I_06]], -1684; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1685; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0686; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]687; ALL: while.end.loopexit:688; ALL-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[WHILE_BODY]] ]689; ALL-NEXT: br label [[WHILE_END]]690; ALL: while.end:691; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ 32, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]692; ALL-NEXT: ret i32 [[I_0_LCSSA]]693;694entry:695 %tobool4 = icmp eq i32 %n, 0696 br i1 %tobool4, label %while.end, label %while.body.preheader697 698while.body.preheader: ; preds = %entry699 br label %while.body700 701while.body: ; preds = %while.body.preheader, %while.body702 %i.06 = phi i32 [ %inc, %while.body ], [ 32, %while.body.preheader ]703 %n.addr.05 = phi i32 [ %shr, %while.body ], [ %n, %while.body.preheader ]704 %shr = lshr i32 %n.addr.05, 1705 %inc = add nsw i32 %i.06, -1706 %tobool = icmp eq i32 %shr, 0707 br i1 %tobool, label %while.end.loopexit, label %while.body708 709while.end.loopexit: ; preds = %while.body710 br label %while.end711 712while.end: ; preds = %while.end.loopexit, %entry713 %i.0.lcssa = phi i32 [ 32, %entry ], [ %inc, %while.end.loopexit ]714 ret i32 %i.0.lcssa715}716 717; Recognize CTLZ builtin pattern.718; Here it will replace the loop -719; assume builtin is always profitable.720;721; int ctlz_lshr_decrement(int n)722; {723; int i = 31;724; while(n >>= 1) {725; i--;726; }727; return i;728; }729;730define i32 @ctlz_lshr_decrement(i32 %n) {731; ALL-LABEL: @ctlz_lshr_decrement(732; ALL-NEXT: entry:733; ALL-NEXT: [[TMP0:%.*]] = lshr i32 [[N:%.*]], 1734; ALL-NEXT: [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[TMP0]], i1 false)735; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]736; ALL-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1737; ALL-NEXT: [[TMP4:%.*]] = sub i32 31, [[TMP2]]738; ALL-NEXT: br label [[WHILE_COND:%.*]]739; ALL: while.cond:740; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]741; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SHR:%.*]], [[WHILE_COND]] ]742; ALL-NEXT: [[I_0:%.*]] = phi i32 [ 31, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]743; ALL-NEXT: [[SHR]] = lshr i32 [[N_ADDR_0]], 1744; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1745; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0746; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], -1747; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]748; ALL: while.end:749; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP4]], [[WHILE_COND]] ]750; ALL-NEXT: ret i32 [[I_0_LCSSA]]751;752entry:753 br label %while.cond754 755while.cond: ; preds = %while.cond, %entry756 %n.addr.0 = phi i32 [ %n, %entry ], [ %shr, %while.cond ]757 %i.0 = phi i32 [ 31, %entry ], [ %inc, %while.cond ]758 %shr = lshr i32 %n.addr.0, 1759 %tobool = icmp eq i32 %shr, 0760 %inc = add nsw i32 %i.0, -1761 br i1 %tobool, label %while.end, label %while.cond762 763while.end: ; preds = %while.cond764 ret i32 %i.0765}766 767declare i32 @llvm.abs.i32(i32, i1)768declare i16 @llvm.abs.i16(i16, i1)769