557 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -mtriple=x86_64-unknown-unknown -select-optimize -S < %s | FileCheck %s3; RUN: opt -mtriple=x86_64-unknown-unknown -passes='require<profile-summary>,function(select-optimize)' -S < %s | FileCheck %s4 5 6;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;7;; Test base heuristic 1:8;; highly-biased selects assumed to be highly predictable, converted to branches9;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;10 11; If a select is obviously predictable, turn it into a branch.12define i32 @weighted_select1(i32 %a, i32 %b, i1 %cmp) {13; CHECK-LABEL: @weighted_select1(14; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]15; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF16:![0-9]+]]16; CHECK: select.false:17; CHECK-NEXT: br label [[SELECT_END]]18; CHECK: select.end:19; CHECK-NEXT: [[SEL:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]20; CHECK-NEXT: ret i32 [[SEL]]21;22 %sel = select i1 %cmp, i32 %a, i32 %b, !prof !1523 ret i32 %sel24}25 26; If a select is obviously predictable (reversed profile weights),27; turn it into a branch.28define i32 @weighted_select2(i32 %a, i32 %b, i1 %cmp) {29; CHECK-LABEL: @weighted_select2(30; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]31; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF17:![0-9]+]]32; CHECK: select.false:33; CHECK-NEXT: br label [[SELECT_END]]34; CHECK: select.end:35; CHECK-NEXT: [[SEL:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]36; CHECK-NEXT: ret i32 [[SEL]]37;38 %sel = select i1 %cmp, i32 %a, i32 %b, !prof !1639 ret i32 %sel40}41 42; Not obvioulsy predictable select.43define i32 @weighted_select3(i32 %a, i32 %b, i1 %cmp) {44; CHECK-LABEL: @weighted_select3(45; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !prof [[PROF18:![0-9]+]]46; CHECK-NEXT: ret i32 [[SEL]]47;48 %sel = select i1 %cmp, i32 %a, i32 %b, !prof !1749 ret i32 %sel50}51 52; Unpredictable select should not form a branch.53define i32 @unpred_select(i32 %a, i32 %b, i1 %cmp) {54; CHECK-LABEL: @unpred_select(55; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !unpredictable [[META19:![0-9]+]]56; CHECK-NEXT: ret i32 [[SEL]]57;58 %sel = select i1 %cmp, i32 %a, i32 %b, !unpredictable !2059 ret i32 %sel60}61 62; Predictable select in function with optsize attribute should not form branch.63define i32 @weighted_select_optsize(i32 %a, i32 %b, i1 %cmp) optsize {64; CHECK-LABEL: @weighted_select_optsize(65; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !prof [[PROF16]]66; CHECK-NEXT: ret i32 [[SEL]]67;68 %sel = select i1 %cmp, i32 %a, i32 %b, !prof !1569 ret i32 %sel70}71 72define i32 @weighted_select_pgso(i32 %a, i32 %b, i1 %cmp) !prof !14 {73; CHECK-LABEL: @weighted_select_pgso(74; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !prof [[PROF16]]75; CHECK-NEXT: ret i32 [[SEL]]76;77 %sel = select i1 %cmp, i32 %a, i32 %b, !prof !1578 ret i32 %sel79}80 81; If two selects in a row are predictable, turn them into branches.82define i32 @weighted_selects(i32 %a, i32 %b) !prof !19 {83; CHECK-LABEL: @weighted_selects(84; CHECK-NEXT: [[CMP:%.*]] = icmp ne i32 [[A:%.*]], 085; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP]]86; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF16]]87; CHECK: select.false:88; CHECK-NEXT: br label [[SELECT_END]]89; CHECK: select.end:90; CHECK-NEXT: [[SEL:%.*]] = phi i32 [ [[A]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]91; CHECK-NEXT: [[CMP1:%.*]] = icmp ne i32 [[SEL]], 092; CHECK-NEXT: [[CMP1_FROZEN:%.*]] = freeze i1 [[CMP1]]93; CHECK-NEXT: br i1 [[CMP1_FROZEN]], label [[SELECT_END1:%.*]], label [[SELECT_FALSE2:%.*]], !prof [[PROF16]]94; CHECK: select.false2:95; CHECK-NEXT: br label [[SELECT_END1]]96; CHECK: select.end1:97; CHECK-NEXT: [[SEL1:%.*]] = phi i32 [ [[B]], [[SELECT_END]] ], [ [[A]], [[SELECT_FALSE2]] ]98; CHECK-NEXT: ret i32 [[SEL1]]99;100 %cmp = icmp ne i32 %a, 0101 %sel = select i1 %cmp, i32 %a, i32 %b, !prof !15102 %cmp1 = icmp ne i32 %sel, 0103 %sel1 = select i1 %cmp1, i32 %b, i32 %a, !prof !15104 ret i32 %sel1105}106 107; If select group predictable, turn it into a branch.108define i32 @weighted_select_group(i32 %a, i32 %b, i32 %c, i1 %cmp) !prof !19 {109; CHECK-LABEL: @weighted_select_group(110; CHECK-NEXT: [[A1:%.*]] = add i32 [[A:%.*]], 1111; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]112; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_FALSE_SINK:%.*]], !prof [[PROF16]]113; CHECK: select.true.sink:114; CHECK-NEXT: [[C1:%.*]] = add i32 [[C:%.*]], 1115; CHECK-NEXT: br label [[SELECT_END:%.*]]116; CHECK: select.false.sink:117; CHECK-NEXT: [[B1:%.*]] = add i32 [[B:%.*]], 1118; CHECK-NEXT: br label [[SELECT_END]]119; CHECK: select.end:120; CHECK-NEXT: [[SEL1:%.*]] = phi i32 [ [[A1]], [[SELECT_TRUE_SINK]] ], [ [[B1]], [[SELECT_FALSE_SINK]] ]121; CHECK-NEXT: [[SEL2:%.*]] = phi i32 [ [[C1]], [[SELECT_TRUE_SINK]] ], [ [[A1]], [[SELECT_FALSE_SINK]] ]122; CHECK-NEXT: #dbg_value(i32 [[SEL1]], [[META22:![0-9]+]], !DIExpression(), [[META26:![0-9]+]])123; CHECK-NEXT: [[ADD:%.*]] = add i32 [[SEL1]], [[SEL2]]124; CHECK-NEXT: ret i32 [[ADD]]125;126 %a1 = add i32 %a, 1127 %b1 = add i32 %b, 1128 %c1 = add i32 %c, 1129 %sel1 = select i1 %cmp, i32 %a1, i32 %b1, !prof !15130 call void @llvm.dbg.value(metadata i32 %sel1, metadata !24, metadata !DIExpression()), !dbg !DILocation(scope: !23)131 %sel2 = select i1 %cmp, i32 %c1, i32 %a1, !prof !15132 %add = add i32 %sel1, %sel2133 ret i32 %add134}135 136; Predictable select group with intra-group dependence converted to branch137define i32 @select_group_intra_group(i32 %a, i32 %b, i32 %c, i1 %cmp) {138; CHECK-LABEL: @select_group_intra_group(139; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]140; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF16]]141; CHECK: select.false:142; CHECK-NEXT: br label [[SELECT_END]]143; CHECK: select.end:144; CHECK-NEXT: [[SEL1:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]145; CHECK-NEXT: [[SEL2:%.*]] = phi i32 [ [[C:%.*]], [[TMP0]] ], [ [[B]], [[SELECT_FALSE]] ]146; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[SEL1]], [[SEL2]]147; CHECK-NEXT: ret i32 [[SUB]]148;149 %sel1 = select i1 %cmp, i32 %a, i32 %b,!prof !15150 %sel2 = select i1 %cmp, i32 %c, i32 %sel1, !prof !15151 %sub = sub i32 %sel1, %sel2152 ret i32 %sub153}154 155;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;156;; Test base heuristic 2:157;; look for expensive instructions in the one-use slice of the cold path158;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;159 160; Select with cold one-use load value operand should form branch and161; sink load162define i32 @expensive_val_operand1(ptr nocapture %a, i32 %y, i1 %cmp) {163; CHECK-LABEL: @expensive_val_operand1(164; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]165; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]166; CHECK: select.true.sink:167; CHECK-NEXT: [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8168; CHECK-NEXT: br label [[SELECT_END]]169; CHECK: select.end:170; CHECK-NEXT: [[SEL:%.*]] = phi i32 [ [[LOAD]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[TMP0:%.*]] ]171; CHECK-NEXT: ret i32 [[SEL]]172;173 %load = load i32, ptr %a, align 8174 %sel = select i1 %cmp, i32 %load, i32 %y, !prof !17175 ret i32 %sel176}177 178; Expensive hot value operand and cheap cold value operand.179define i32 @expensive_val_operand2(ptr nocapture %a, i32 %x, i1 %cmp) {180; CHECK-LABEL: @expensive_val_operand2(181; CHECK-NEXT: [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8182; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[X:%.*]], i32 [[LOAD]], !prof [[PROF18]]183; CHECK-NEXT: ret i32 [[SEL]]184;185 %load = load i32, ptr %a, align 8186 %sel = select i1 %cmp, i32 %x, i32 %load, !prof !17187 ret i32 %sel188}189 190; Cold value operand with load in its one-use dependence slice should result191; into a branch with sinked dependence slice.192define i32 @expensive_val_operand3(ptr nocapture %a, i32 %b, i32 %y, i1 %cmp) {193; CHECK-LABEL: @expensive_val_operand3(194; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]195; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]196; CHECK: select.true.sink:197; CHECK-NEXT: [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8198; CHECK-NEXT: [[X:%.*]] = add i32 [[LOAD]], [[B:%.*]]199; CHECK-NEXT: br label [[SELECT_END]]200; CHECK: select.end:201; CHECK-NEXT: [[SEL:%.*]] = phi i32 [ [[X]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[TMP0:%.*]] ]202; CHECK-NEXT: ret i32 [[SEL]]203;204 %load = load i32, ptr %a, align 8205 %x = add i32 %load, %b206 %sel = select i1 %cmp, i32 %x, i32 %y, !prof !17207 ret i32 %sel208}209 210; Expensive cold value operand with unsafe-to-sink (due to func call) load (partial slice sinking).211define i32 @expensive_val_operand4(ptr nocapture %a, i32 %b, i32 %y, i1 %cmp) {212; CHECK-LABEL: @expensive_val_operand4(213; CHECK-NEXT: [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8214; CHECK-NEXT: call void @free(ptr [[A]])215; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]216; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]217; CHECK: select.true.sink:218; CHECK-NEXT: [[X:%.*]] = add i32 [[LOAD]], [[B:%.*]]219; CHECK-NEXT: br label [[SELECT_END]]220; CHECK: select.end:221; CHECK-NEXT: [[SEL:%.*]] = phi i32 [ [[X]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[TMP0:%.*]] ]222; CHECK-NEXT: ret i32 [[SEL]]223;224 %load = load i32, ptr %a, align 8225 call void @free(ptr %a)226 %x = add i32 %load, %b227 %sel = select i1 %cmp, i32 %x, i32 %y, !prof !17228 ret i32 %sel229}230 231; Expensive cold value operand with unsafe-to-sink (due to lifetime-end marker) load (partial slice sinking).232define i32 @expensive_val_operand5(i32 %b, i32 %y, i1 %cmp) {233; CHECK-LABEL: @expensive_val_operand5(234; CHECK-NEXT: [[A:%.*]] = alloca i32, align 4235; CHECK-NEXT: [[LOAD:%.*]] = load i32, ptr [[A]], align 8236; CHECK-NEXT: call void @llvm.lifetime.end.p0(ptr nonnull [[A]])237; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]238; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]239; CHECK: select.true.sink:240; CHECK-NEXT: [[X:%.*]] = add i32 [[LOAD]], [[B:%.*]]241; CHECK-NEXT: br label [[SELECT_END]]242; CHECK: select.end:243; CHECK-NEXT: [[SEL:%.*]] = phi i32 [ [[X]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[TMP0:%.*]] ]244; CHECK-NEXT: ret i32 [[SEL]]245;246 %a = alloca i32247 %load = load i32, ptr %a, align 8248 call void @llvm.lifetime.end.p0(ptr nonnull %a)249 %x = add i32 %load, %b250 %sel = select i1 %cmp, i32 %x, i32 %y, !prof !17251 ret i32 %sel252}253 254; Expensive cold value operand with potentially-unsafe-to-sink load (located255; in a different basic block and thus unchecked for sinkability).256define i32 @expensive_val_operand6(ptr nocapture %a, i32 %b, i32 %y, i1 %cmp) {257; CHECK-LABEL: @expensive_val_operand6(258; CHECK-NEXT: entry:259; CHECK-NEXT: [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8260; CHECK-NEXT: br label [[BB1:%.*]]261; CHECK: bb1:262; CHECK-NEXT: [[CMP_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]263; CHECK-NEXT: br i1 [[CMP_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]264; CHECK: select.true.sink:265; CHECK-NEXT: [[X:%.*]] = add i32 [[LOAD]], [[B:%.*]]266; CHECK-NEXT: br label [[SELECT_END]]267; CHECK: select.end:268; CHECK-NEXT: [[SEL:%.*]] = phi i32 [ [[X]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[BB1]] ]269; CHECK-NEXT: ret i32 [[SEL]]270;271entry:272 %load = load i32, ptr %a, align 8273 br label %bb1274bb1: ; preds = %entry275 %x = add i32 %load, %b276 %sel = select i1 %cmp, i32 %x, i32 %y, !prof !17277 ret i32 %sel278}279 280; Multiple uses of the load value operand.281define i32 @expensive_val_operand7(i32 %a, ptr nocapture %b, i32 %x, i1 %cmp) {282; CHECK-LABEL: @expensive_val_operand7(283; CHECK-NEXT: [[LOAD:%.*]] = load i32, ptr [[B:%.*]], align 4284; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[X:%.*]], i32 [[LOAD]]285; CHECK-NEXT: [[ADD:%.*]] = add i32 [[SEL]], [[LOAD]]286; CHECK-NEXT: ret i32 [[ADD]]287;288 %load = load i32, ptr %b, align 4289 %sel = select i1 %cmp, i32 %x, i32 %load290 %add = add i32 %sel, %load291 ret i32 %add292}293 294;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;295;; Test loop heuristic: loop-level critical-path analysis296;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;297 298;; Use of cmov in this test would put a load and a fsub on the critical path.299;; Loop-level analysis should decide to form a branch.300;;301;;double cmov_on_critical_path(int n, double x, ptr a) {302;; for (int i = 0; i < n; i++) {303;; double r = a[i];304;; if (x > r)305;; // 50% of iterations306;; x -= r;307;; }308;; return x;309;;}310define double @cmov_on_critical_path(i32 %n, double %x, ptr nocapture %a) {311; CHECK-LABEL: @cmov_on_critical_path(312; CHECK-NEXT: entry:313; CHECK-NEXT: [[CMP1:%.*]] = icmp sgt i32 [[N:%.*]], 0314; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]315; CHECK: for.cond.cleanup:316; CHECK-NEXT: ret double [[X:%.*]]317; CHECK: for.body.preheader:318; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64319; CHECK-NEXT: br label [[FOR_BODY:%.*]]320; CHECK: for.body:321; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[SELECT_END:%.*]] ], [ 0, [[FOR_BODY_PREHEADER]] ]322; CHECK-NEXT: [[X1:%.*]] = phi double [ [[X2:%.*]], [[SELECT_END]] ], [ [[X]], [[FOR_BODY_PREHEADER]] ]323; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds double, ptr [[A:%.*]], i64 [[INDVARS_IV]]324; CHECK-NEXT: [[R:%.*]] = load double, ptr [[ARRAYIDX]], align 8325; CHECK-NEXT: [[CMP2:%.*]] = fcmp ogt double [[X1]], [[R]]326; CHECK-NEXT: [[CMP2_FROZEN:%.*]] = freeze i1 [[CMP2]]327; CHECK-NEXT: br i1 [[CMP2_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END]], !prof [[PROF27:![0-9]+]]328; CHECK: select.true.sink:329; CHECK-NEXT: [[SUB:%.*]] = fsub double [[X1]], [[R]]330; CHECK-NEXT: br label [[SELECT_END]]331; CHECK: select.end:332; CHECK-NEXT: [[X2]] = phi double [ [[SUB]], [[SELECT_TRUE_SINK]] ], [ [[X1]], [[FOR_BODY]] ]333; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1334; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]335; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_EXIT:%.*]], label [[FOR_BODY]]336; CHECK: for.exit:337; CHECK-NEXT: ret double [[X2]]338;339entry:340 %cmp1 = icmp sgt i32 %n, 0341 br i1 %cmp1, label %for.body.preheader, label %for.cond.cleanup342 343for.cond.cleanup: ; preds = %entry344 ret double %x345 346for.body.preheader: ; preds = %entry347 %wide.trip.count = zext i32 %n to i64348 br label %for.body349 350for.body: ; preds = %for.body.preheader, %for.body351 %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]352 %x1 = phi double [ %x2, %for.body ], [ %x, %for.body.preheader ]353 %arrayidx = getelementptr inbounds double, ptr %a, i64 %indvars.iv354 %r = load double, ptr %arrayidx, align 8355 %sub = fsub double %x1, %r356 %cmp2 = fcmp ogt double %x1, %r357 %x2 = select i1 %cmp2, double %sub, double %x1, !prof !18358 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1359 %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count360 br i1 %exitcond, label %for.exit, label %for.body361 362for.exit: ; preds = %for.body363 ret double %x2364}365 366;; The common path includes expensive operations (load and fsub) making367;; branch similarly expensive to cmov, and thus the gain is small.368;; Loop-level analysis should decide on not forming a branch.369;;370;;double small_gain(int n, double x, ptr a) {371;; for (int i = 0; i < n; i++) {372;; double r = a[i];373;; if (x > r)374;; // 99% of iterations375;; x -= r;376;; }377;; return x;378;;}379define double @small_gain(i32 %n, double %x, ptr nocapture %a) {380; CHECK-LABEL: @small_gain(381; CHECK-NEXT: entry:382; CHECK-NEXT: [[CMP1:%.*]] = icmp sgt i32 [[N:%.*]], 0383; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]384; CHECK: for.cond.cleanup:385; CHECK-NEXT: ret double [[X:%.*]]386; CHECK: for.body.preheader:387; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64388; CHECK-NEXT: br label [[FOR_BODY:%.*]]389; CHECK: for.body:390; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_BODY_PREHEADER]] ]391; CHECK-NEXT: [[X1:%.*]] = phi double [ [[X2:%.*]], [[FOR_BODY]] ], [ [[X]], [[FOR_BODY_PREHEADER]] ]392; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds double, ptr [[A:%.*]], i64 [[INDVARS_IV]]393; CHECK-NEXT: [[R:%.*]] = load double, ptr [[ARRAYIDX]], align 8394; CHECK-NEXT: [[SUB:%.*]] = fsub double [[X1]], [[R]]395; CHECK-NEXT: [[CMP2:%.*]] = fcmp ole double [[X1]], [[R]]396; CHECK-NEXT: [[X2]] = select i1 [[CMP2]], double [[X1]], double [[SUB]], !prof [[PROF18]]397; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1398; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]399; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_EXIT:%.*]], label [[FOR_BODY]]400; CHECK: for.exit:401; CHECK-NEXT: ret double [[X2]]402;403entry:404 %cmp1 = icmp sgt i32 %n, 0405 br i1 %cmp1, label %for.body.preheader, label %for.cond.cleanup406 407for.cond.cleanup: ; preds = %entry408 ret double %x409 410for.body.preheader: ; preds = %entry411 %wide.trip.count = zext i32 %n to i64412 br label %for.body413 414for.body: ; preds = %for.body.preheader, %for.body415 %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]416 %x1 = phi double [ %x2, %for.body ], [ %x, %for.body.preheader ]417 %arrayidx = getelementptr inbounds double, ptr %a, i64 %indvars.iv418 %r = load double, ptr %arrayidx, align 8419 %sub = fsub double %x1, %r420 %cmp2 = fcmp ole double %x1, %r421 %x2 = select i1 %cmp2, double %x1, double %sub, !prof !17422 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1423 %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count424 br i1 %exitcond, label %for.exit, label %for.body425 426for.exit: ; preds = %for.body427 ret double %x2428}429 430;; One select on the critical path and one off the critical path.431;; Loop-level analysis should decide to form a branch only for432;; the select on the critical path.433;;434;;double loop_select_groups(int n, double x, ptr a, int k) {435;; int c = 0;436;; for (int i = 0; i < n; i++) {437;; double r = a[i];438;; if (x > r)439;; x -= r;440;; if (i == k)441;; c += n;442;; }443;; return x + c;444;;}445define double @loop_select_groups(i32 %n, double %x, ptr nocapture %a, i32 %k) {446; CHECK-LABEL: @loop_select_groups(447; CHECK-NEXT: entry:448; CHECK-NEXT: [[CMP19:%.*]] = icmp sgt i32 [[N:%.*]], 0449; CHECK-NEXT: br i1 [[CMP19]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]450; CHECK: for.body.preheader:451; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64452; CHECK-NEXT: br label [[FOR_BODY:%.*]]453; CHECK: for.cond.cleanup.loopexit:454; CHECK-NEXT: [[PHI_CAST:%.*]] = sitofp i32 [[C_1:%.*]] to double455; CHECK-NEXT: br label [[FOR_COND_CLEANUP]]456; CHECK: for.cond.cleanup:457; CHECK-NEXT: [[C_0_LCSSA:%.*]] = phi double [ 0.000000e+00, [[ENTRY:%.*]] ], [ [[PHI_CAST]], [[FOR_COND_CLEANUP_LOOPEXIT:%.*]] ]458; CHECK-NEXT: [[X_ADDR_0_LCSSA:%.*]] = phi double [ [[X:%.*]], [[ENTRY]] ], [ [[X_ADDR_1:%.*]], [[FOR_COND_CLEANUP_LOOPEXIT]] ]459; CHECK-NEXT: [[ADD5:%.*]] = fadd double [[X_ADDR_0_LCSSA]], [[C_0_LCSSA]]460; CHECK-NEXT: ret double [[ADD5]]461; CHECK: for.body:462; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[SELECT_END:%.*]] ]463; CHECK-NEXT: [[X_ADDR_022:%.*]] = phi double [ [[X]], [[FOR_BODY_PREHEADER]] ], [ [[X_ADDR_1]], [[SELECT_END]] ]464; CHECK-NEXT: [[C_020:%.*]] = phi i32 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[C_1]], [[SELECT_END]] ]465; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds double, ptr [[A:%.*]], i64 [[INDVARS_IV]]466; CHECK-NEXT: [[TMP0:%.*]] = load double, ptr [[ARRAYIDX]], align 8467; CHECK-NEXT: [[CMP1:%.*]] = fcmp ogt double [[X_ADDR_022]], [[TMP0]]468; CHECK-NEXT: [[CMP1_FROZEN:%.*]] = freeze i1 [[CMP1]]469; CHECK-NEXT: br i1 [[CMP1_FROZEN]], label [[SELECT_END]], label [[SELECT_FALSE:%.*]]470; CHECK: select.false:471; CHECK-NEXT: br label [[SELECT_END]]472; CHECK: select.end:473; CHECK-NEXT: [[SUB:%.*]] = phi double [ [[TMP0]], [[FOR_BODY]] ], [ 0.000000e+00, [[SELECT_FALSE]] ]474; CHECK-NEXT: [[X_ADDR_1]] = fsub double [[X_ADDR_022]], [[SUB]]475; CHECK-NEXT: [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32476; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[K:%.*]], [[N]]477; CHECK-NEXT: [[ADD:%.*]] = select i1 [[CMP2]], i32 [[N]], i32 0478; CHECK-NEXT: [[C_1]] = add nsw i32 [[ADD]], [[C_020]]479; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1480; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]481; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP_LOOPEXIT]], label [[FOR_BODY]]482;483entry:484 %cmp19 = icmp sgt i32 %n, 0485 br i1 %cmp19, label %for.body.preheader, label %for.cond.cleanup486 487for.body.preheader: ; preds = %entry488 %wide.trip.count = zext i32 %n to i64489 br label %for.body490 491for.cond.cleanup.loopexit: ; preds = %for.body492 %phi.cast = sitofp i32 %c.1 to double493 br label %for.cond.cleanup494 495for.cond.cleanup: ; preds = %for.cond.cleanup.loopexit, %entry496 %c.0.lcssa = phi double [ 0.000000e+00, %entry ], [ %phi.cast, %for.cond.cleanup.loopexit ]497 %x.addr.0.lcssa = phi double [ %x, %entry ], [ %x.addr.1, %for.cond.cleanup.loopexit ]498 %add5 = fadd double %x.addr.0.lcssa, %c.0.lcssa499 ret double %add5500 501for.body: ; preds = %for.body.preheader, %for.body502 %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]503 %x.addr.022 = phi double [ %x, %for.body.preheader ], [ %x.addr.1, %for.body ]504 %c.020 = phi i32 [ 0, %for.body.preheader ], [ %c.1, %for.body ]505 %arrayidx = getelementptr inbounds double, ptr %a, i64 %indvars.iv506 %0 = load double, ptr %arrayidx, align 8507 %cmp1 = fcmp ogt double %x.addr.022, %0508 %sub = select i1 %cmp1, double %0, double 0.000000e+00509 %x.addr.1 = fsub double %x.addr.022, %sub510 %1 = trunc i64 %indvars.iv to i32511 %cmp2 = icmp eq i32 %k, %n512 %add = select i1 %cmp2, i32 %n, i32 0513 %c.1 = add nsw i32 %add, %c.020514 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1515 %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count516 br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body517}518 519; Function Attrs: nounwind readnone speculatable willreturn520declare void @llvm.dbg.value(metadata, metadata, metadata)521 522; Function Attrs: argmemonly mustprogress nocallback nofree nosync nounwind willreturn523declare void @llvm.lifetime.end.p0(ptr nocapture)524 525declare void @free(ptr nocapture)526 527!llvm.module.flags = !{!0, !26, !27}528!0 = !{i32 1, !"ProfileSummary", !1}529!1 = !{!2, !3, !4, !5, !6, !7, !8, !9}530!2 = !{!"ProfileFormat", !"InstrProf"}531!3 = !{!"TotalCount", i64 10000}532!4 = !{!"MaxCount", i64 10}533!5 = !{!"MaxInternalCount", i64 1}534!6 = !{!"MaxFunctionCount", i64 1000}535!7 = !{!"NumCounts", i64 3}536!8 = !{!"NumFunctions", i64 3}537!9 = !{!"DetailedSummary", !10}538!10 = !{!11, !12, !13}539!11 = !{i32 10000, i64 100, i32 1}540!12 = !{i32 999000, i64 100, i32 1}541!13 = !{i32 999999, i64 1, i32 2}542!14 = !{!"function_entry_count", i64 0}543!15 = !{!"branch_weights", i32 1, i32 100}544!16 = !{!"branch_weights", i32 100, i32 1}545!17 = !{!"branch_weights", i32 1, i32 99}546!18 = !{!"branch_weights", i32 50, i32 50}547!19 = !{!"function_entry_count", i64 100}548!20 = !{}549!21 = !DIFile(filename: "test.c", directory: "/test")550!22 = distinct !DICompileUnit(language: DW_LANG_C99, file: !21, producer: "clang version 15.0.0", isOptimized: true, emissionKind: FullDebug, globals: !25, splitDebugInlining: false, nameTableKind: None)551!23 = distinct !DISubprogram(name: "test", scope: !21, file: !21, line: 1, unit: !22)552!24 = !DILocalVariable(name: "x", scope: !23)553!25 = !{}554!26 = !{i32 2, !"Dwarf Version", i32 4}555!27 = !{i32 1, !"Debug Info Version", i32 3}556!28 = !{!"branch_weights", i32 30, i32 70}557