228 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 --check-prefix=ALL %s3; RUN: opt -passes=loop-idiom -mtriple=x86_64 -mcpu=corei7 < %s -S | FileCheck --check-prefix=ALL %s4 5; Recognize CTTZ builtin pattern.6; Here it will replace the loop -7; assume builtin is always profitable.8;9; int cttz_zero_check(int n)10; {11; int i = 0;12; while(n) {13; n <<= 1;14; i++;15; }16; return i;17; }18;19define i32 @cttz_zero_check(i32 %n) {20; ALL-LABEL: @cttz_zero_check(21; ALL-NEXT: entry:22; ALL-NEXT: [[TOBOOL4:%.*]] = icmp eq i32 [[N:%.*]], 023; ALL-NEXT: br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]24; ALL: while.body.preheader:25; ALL-NEXT: [[TMP0:%.*]] = call i32 @llvm.cttz.i32(i32 [[N]], i1 true)26; ALL-NEXT: [[TMP1:%.*]] = sub i32 32, [[TMP0]]27; ALL-NEXT: br label [[WHILE_BODY:%.*]]28; ALL: while.body:29; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]30; ALL-NEXT: [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]31; ALL-NEXT: [[N_ADDR_05:%.*]] = phi i32 [ [[SHL:%.*]], [[WHILE_BODY]] ], [ [[N]], [[WHILE_BODY_PREHEADER]] ]32; ALL-NEXT: [[SHL]] = shl i32 [[N_ADDR_05]], 133; ALL-NEXT: [[INC]] = add nsw i32 [[I_06]], 134; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 135; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 036; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]37; ALL: while.end.loopexit:38; ALL-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY]] ]39; ALL-NEXT: br label [[WHILE_END]]40; ALL: while.end:41; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]42; ALL-NEXT: ret i32 [[I_0_LCSSA]]43;44entry:45 %tobool4 = icmp eq i32 %n, 046 br i1 %tobool4, label %while.end, label %while.body.preheader47 48while.body.preheader: ; preds = %entry49 br label %while.body50 51while.body: ; preds = %while.body.preheader, %while.body52 %i.06 = phi i32 [ %inc, %while.body ], [ 0, %while.body.preheader ]53 %n.addr.05 = phi i32 [ %shl, %while.body ], [ %n, %while.body.preheader ]54 %shl = shl i32 %n.addr.05, 155 %inc = add nsw i32 %i.06, 156 %tobool = icmp eq i32 %shl, 057 br i1 %tobool, label %while.end.loopexit, label %while.body58 59while.end.loopexit: ; preds = %while.body60 br label %while.end61 62while.end: ; preds = %while.end.loopexit, %entry63 %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.end.loopexit ]64 ret i32 %i.0.lcssa65}66 67; Recognize CTTZ builtin pattern.68; Here it will replace the loop -69; assume builtin is always profitable.70;71; int cttz(int n)72; {73; int i = 0;74; while(n <<= 1) {75; i++;76; }77; return i;78; }79;80define i32 @cttz(i32 %n) {81; ALL-LABEL: @cttz(82; ALL-NEXT: entry:83; ALL-NEXT: [[TMP0:%.*]] = shl i32 [[N:%.*]], 184; ALL-NEXT: [[TMP1:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0]], i1 false)85; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]86; ALL-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 187; ALL-NEXT: br label [[WHILE_COND:%.*]]88; ALL: while.cond:89; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]90; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SHL:%.*]], [[WHILE_COND]] ]91; ALL-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]92; ALL-NEXT: [[SHL]] = shl i32 [[N_ADDR_0]], 193; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 194; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 095; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], 196; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]97; ALL: while.end:98; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[WHILE_COND]] ]99; ALL-NEXT: ret i32 [[I_0_LCSSA]]100;101entry:102 br label %while.cond103 104while.cond: ; preds = %while.cond, %entry105 %n.addr.0 = phi i32 [ %n, %entry ], [ %shl, %while.cond ]106 %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]107 %shl = shl i32 %n.addr.0, 1108 %tobool = icmp eq i32 %shl, 0109 %inc = add nsw i32 %i.0, 1110 br i1 %tobool, label %while.end, label %while.cond111 112while.end: ; preds = %while.cond113 ret i32 %i.0114}115 116; Recognize CTTZ builtin pattern.117; Here it will replace the loop -118; assume builtin is always profitable.119;120; int ctlz_decrement(int n)121; {122; int i = 32;123; while(n) {124; n <<= 1;125; i--;126; }127; return i;128; }129;130define i32 @cttz_decrement(i32 %n) {131; ALL-LABEL: @cttz_decrement(132; ALL-NEXT: entry:133; ALL-NEXT: [[TOBOOL4:%.*]] = icmp eq i32 [[N:%.*]], 0134; ALL-NEXT: br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]135; ALL: while.body.preheader:136; ALL-NEXT: [[TMP0:%.*]] = call i32 @llvm.cttz.i32(i32 [[N]], i1 true)137; ALL-NEXT: [[TMP1:%.*]] = sub i32 32, [[TMP0]]138; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]139; ALL-NEXT: br label [[WHILE_BODY:%.*]]140; ALL: while.body:141; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]142; ALL-NEXT: [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 32, [[WHILE_BODY_PREHEADER]] ]143; ALL-NEXT: [[N_ADDR_05:%.*]] = phi i32 [ [[SHL:%.*]], [[WHILE_BODY]] ], [ [[N]], [[WHILE_BODY_PREHEADER]] ]144; ALL-NEXT: [[SHL]] = shl i32 [[N_ADDR_05]], 1145; ALL-NEXT: [[INC]] = add nsw i32 [[I_06]], -1146; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1147; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0148; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]149; ALL: while.end.loopexit:150; ALL-NEXT: [[INC_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[WHILE_BODY]] ]151; ALL-NEXT: br label [[WHILE_END]]152; ALL: while.end:153; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ 32, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]154; ALL-NEXT: ret i32 [[I_0_LCSSA]]155;156entry:157 %tobool4 = icmp eq i32 %n, 0158 br i1 %tobool4, label %while.end, label %while.body.preheader159 160while.body.preheader: ; preds = %entry161 br label %while.body162 163while.body: ; preds = %while.body.preheader, %while.body164 %i.06 = phi i32 [ %inc, %while.body ], [ 32, %while.body.preheader ]165 %n.addr.05 = phi i32 [ %shl, %while.body ], [ %n, %while.body.preheader ]166 %shl = shl i32 %n.addr.05, 1167 %inc = add nsw i32 %i.06, -1168 %tobool = icmp eq i32 %shl, 0169 br i1 %tobool, label %while.end.loopexit, label %while.body170 171while.end.loopexit: ; preds = %while.body172 br label %while.end173 174while.end: ; preds = %while.end.loopexit, %entry175 %i.0.lcssa = phi i32 [ 32, %entry ], [ %inc, %while.end.loopexit ]176 ret i32 %i.0.lcssa177}178 179; Recognize CTTZ builtin pattern.180; Here it will replace the loop -181; assume builtin is always profitable.182;183; int cttz_shl_decrement(int n)184; {185; int i = 31;186; while(n <<= 1) {187; i--;188; }189; return i;190; }191;192define i32 @cttz_shl_decrement(i32 %n) {193; ALL-LABEL: @cttz_shl_decrement(194; ALL-NEXT: entry:195; ALL-NEXT: [[TMP0:%.*]] = shl i32 [[N:%.*]], 1196; ALL-NEXT: [[TMP1:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0]], i1 false)197; ALL-NEXT: [[TMP2:%.*]] = sub i32 32, [[TMP1]]198; ALL-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1199; ALL-NEXT: [[TMP4:%.*]] = sub i32 31, [[TMP2]]200; ALL-NEXT: br label [[WHILE_COND:%.*]]201; ALL: while.cond:202; ALL-NEXT: [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]203; ALL-NEXT: [[N_ADDR_0:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SHL:%.*]], [[WHILE_COND]] ]204; ALL-NEXT: [[I_0:%.*]] = phi i32 [ 31, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]205; ALL-NEXT: [[SHL]] = shl i32 [[N_ADDR_0]], 1206; ALL-NEXT: [[TCDEC]] = sub nsw i32 [[TCPHI]], 1207; ALL-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0208; ALL-NEXT: [[INC]] = add nsw i32 [[I_0]], -1209; ALL-NEXT: br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]210; ALL: while.end:211; ALL-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP4]], [[WHILE_COND]] ]212; ALL-NEXT: ret i32 [[I_0_LCSSA]]213;214entry:215 br label %while.cond216 217while.cond: ; preds = %while.cond, %entry218 %n.addr.0 = phi i32 [ %n, %entry ], [ %shl, %while.cond ]219 %i.0 = phi i32 [ 31, %entry ], [ %inc, %while.cond ]220 %shl = shl i32 %n.addr.0, 1221 %tobool = icmp eq i32 %shl, 0222 %inc = add nsw i32 %i.0, -1223 br i1 %tobool, label %while.end, label %while.cond224 225while.end: ; preds = %while.cond226 ret i32 %i.0227}228