llvm/test/CodeGen/X86/select-optimize.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -mtriple=x86_64-unknown-unknown -select-optimize -S < %s | FileCheck %s
   3
   4 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   5 ;; Test base heuristic 1:
   6 ;; highly-biased selects assumed to be highly predictable, converted to branches
   7 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   8
   9 ; If a select is obviously predictable, turn it into a branch.
  10 define i32 @weighted_select1(i32 %a, i32 %b, i1 %cmp) {
  11 ; CHECK-LABEL: @weighted_select1(
  12 ; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
  13 ; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF16:![0-9]+]]
  14 ; CHECK:       select.false:
  15 ; CHECK-NEXT:    br label [[SELECT_END]]
  16 ; CHECK:       select.end:
  17 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]
  18 ; CHECK-NEXT:    ret i32 [[SEL]]
  19 ;
  20   %sel = select i1 %cmp, i32 %a, i32 %b, !prof !15
  21   ret i32 %sel
  22 }
  23
  24 ; If a select is obviously predictable (reversed profile weights),
  25 ; turn it into a branch.
  26 define i32 @weighted_select2(i32 %a, i32 %b, i1 %cmp) {
  27 ; CHECK-LABEL: @weighted_select2(
  28 ; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
  29 ; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF17:![0-9]+]]
  30 ; CHECK:       select.false:
  31 ; CHECK-NEXT:    br label [[SELECT_END]]
  32 ; CHECK:       select.end:
  33 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]
  34 ; CHECK-NEXT:    ret i32 [[SEL]]
  35 ;
  36   %sel = select i1 %cmp, i32 %a, i32 %b, !prof !16
  37   ret i32 %sel
  38 }
  39
  40 ; Not obvioulsy predictable select.
  41 define i32 @weighted_select3(i32 %a, i32 %b, i1 %cmp) {
  42 ; CHECK-LABEL: @weighted_select3(
  43 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !prof [[PROF18:![0-9]+]]
  44 ; CHECK-NEXT:    ret i32 [[SEL]]
  45 ;
  46   %sel = select i1 %cmp, i32 %a, i32 %b, !prof !17
  47   ret i32 %sel
  48 }
  49
  50 ; Unpredictable select should not form a branch.
  51 define i32 @unpred_select(i32 %a, i32 %b, i1 %cmp) {
  52 ; CHECK-LABEL: @unpred_select(
  53 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !unpredictable !19
  54 ; CHECK-NEXT:    ret i32 [[SEL]]
  55 ;
  56   %sel = select i1 %cmp, i32 %a, i32 %b, !unpredictable !20
  57   ret i32 %sel
  58 }
  59
  60 ; Predictable select in function with optsize attribute should not form branch.
  61 define i32 @weighted_select_optsize(i32 %a, i32 %b, i1 %cmp) optsize {
  62 ; CHECK-LABEL: @weighted_select_optsize(
  63 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !prof [[PROF16]]
  64 ; CHECK-NEXT:    ret i32 [[SEL]]
  65 ;
  66   %sel = select i1 %cmp, i32 %a, i32 %b, !prof !15
  67   ret i32 %sel
  68 }
  69
  70 define i32 @weighted_select_pgso(i32 %a, i32 %b, i1 %cmp) !prof !14 {
  71 ; CHECK-LABEL: @weighted_select_pgso(
  72 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], !prof [[PROF16]]
  73 ; CHECK-NEXT:    ret i32 [[SEL]]
  74 ;
  75   %sel = select i1 %cmp, i32 %a, i32 %b, !prof !15
  76   ret i32 %sel
  77 }
  78
  79 ; If two selects in a row are predictable, turn them into branches.
  80 define i32 @weighted_selects(i32 %a, i32 %b) !prof !19 {
  81 ; CHECK-LABEL: @weighted_selects(
  82 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[A:%.*]], 0
  83 ; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP]]
  84 ; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF16]]
  85 ; CHECK:       select.false:
  86 ; CHECK-NEXT:    br label [[SELECT_END]]
  87 ; CHECK:       select.end:
  88 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[A]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]
  89 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[SEL]], 0
  90 ; CHECK-NEXT:    [[SEL1_FROZEN:%.*]] = freeze i1 [[CMP1]]
  91 ; CHECK-NEXT:    br i1 [[SEL1_FROZEN]], label [[SELECT_END1:%.*]], label [[SELECT_FALSE2:%.*]], !prof [[PROF16]]
  92 ; CHECK:       select.false2:
  93 ; CHECK-NEXT:    br label [[SELECT_END1]]
  94 ; CHECK:       select.end1:
  95 ; CHECK-NEXT:    [[SEL1:%.*]] = phi i32 [ [[B]], [[SELECT_END]] ], [ [[A]], [[SELECT_FALSE2]] ]
  96 ; CHECK-NEXT:    ret i32 [[SEL1]]
  97 ;
  98   %cmp = icmp ne i32 %a, 0
  99   %sel = select i1 %cmp, i32 %a, i32 %b, !prof !15
 100   %cmp1 = icmp ne i32 %sel, 0
 101   %sel1 = select i1 %cmp1, i32 %b, i32 %a, !prof !15
 102   ret i32 %sel1
 103 }
 104
 105 ; If select group predictable, turn it into a branch.
 106 define i32 @weighted_select_group(i32 %a, i32 %b, i32 %c, i1 %cmp) !prof !19 {
 107 ; CHECK-LABEL: @weighted_select_group(
 108 ; CHECK-NEXT:    [[A1:%.*]] = add i32 [[A:%.*]], 1
 109 ; CHECK-NEXT:    [[SEL1_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
 110 ; CHECK-NEXT:    br i1 [[SEL1_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_FALSE_SINK:%.*]], !prof [[PROF16]]
 111 ; CHECK:       select.true.sink:
 112 ; CHECK-NEXT:    [[C1:%.*]] = add i32 [[C:%.*]], 1
 113 ; CHECK-NEXT:    br label [[SELECT_END:%.*]]
 114 ; CHECK:       select.false.sink:
 115 ; CHECK-NEXT:    [[B1:%.*]] = add i32 [[B:%.*]], 1
 116 ; CHECK-NEXT:    br label [[SELECT_END]]
 117 ; CHECK:       select.end:
 118 ; CHECK-NEXT:    [[SEL1:%.*]] = phi i32 [ [[A1]], [[SELECT_TRUE_SINK]] ], [ [[B1]], [[SELECT_FALSE_SINK]] ]
 119 ; CHECK-NEXT:    [[SEL2:%.*]] = phi i32 [ [[C1]], [[SELECT_TRUE_SINK]] ], [ [[A1]], [[SELECT_FALSE_SINK]] ]
 120 ; CHECK-NEXT:    call void @llvm.dbg.value(metadata i32 [[SEL1]], metadata [[META22:![0-9]+]], metadata !DIExpression()), !dbg [[DBG26:![0-9]+]]
 121 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SEL1]], [[SEL2]]
 122 ; CHECK-NEXT:    ret i32 [[ADD]]
 123 ;
 124   %a1 = add i32 %a, 1
 125   %b1 = add i32 %b, 1
 126   %c1 = add i32 %c, 1
 127   %sel1 = select i1 %cmp, i32 %a1, i32 %b1, !prof !15
 128   call void @llvm.dbg.value(metadata i32 %sel1, metadata !24, metadata !DIExpression()), !dbg !DILocation(scope: !23)
 129   %sel2 = select i1 %cmp, i32 %c1, i32 %a1, !prof !15
 130   %add = add i32 %sel1, %sel2
 131   ret i32 %add
 132 }
 133
 134 ; Predictable select group with intra-group dependence converted to branch
 135 define i32 @select_group_intra_group(i32 %a, i32 %b, i32 %c, i1 %cmp) {
 136 ; CHECK-LABEL: @select_group_intra_group(
 137 ; CHECK-NEXT:    [[SEL1_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
 138 ; CHECK-NEXT:    br i1 [[SEL1_FROZEN]], label [[SELECT_END:%.*]], label [[SELECT_FALSE:%.*]], !prof [[PROF16]]
 139 ; CHECK:       select.false:
 140 ; CHECK-NEXT:    br label [[SELECT_END]]
 141 ; CHECK:       select.end:
 142 ; CHECK-NEXT:    [[SEL1:%.*]] = phi i32 [ [[A:%.*]], [[TMP0:%.*]] ], [ [[B:%.*]], [[SELECT_FALSE]] ]
 143 ; CHECK-NEXT:    [[SEL2:%.*]] = phi i32 [ [[C:%.*]], [[TMP0]] ], [ [[B]], [[SELECT_FALSE]] ]
 144 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[SEL1]], [[SEL2]]
 145 ; CHECK-NEXT:    ret i32 [[SUB]]
 146 ;
 147   %sel1 = select i1 %cmp, i32 %a, i32 %b,!prof !15
 148   %sel2 = select i1 %cmp, i32 %c, i32 %sel1, !prof !15
 149   %sub = sub i32 %sel1, %sel2
 150   ret i32 %sub
 151 }
 152
 153 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 154 ;; Test base heuristic 2:
 155 ;; look for expensive instructions in the one-use slice of the cold path
 156 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 157
 158 ; Select with cold one-use load value operand should form branch and
 159 ; sink load
 160 define i32 @expensive_val_operand1(ptr nocapture %a, i32 %y, i1 %cmp) {
 161 ; CHECK-LABEL: @expensive_val_operand1(
 162 ; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
 163 ; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]
 164 ; CHECK:       select.true.sink:
 165 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8
 166 ; CHECK-NEXT:    br label [[SELECT_END]]
 167 ; CHECK:       select.end:
 168 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[LOAD]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[TMP0:%.*]] ]
 169 ; CHECK-NEXT:    ret i32 [[SEL]]
 170 ;
 171   %load = load i32, ptr %a, align 8
 172   %sel = select i1 %cmp, i32 %load, i32 %y, !prof !17
 173   ret i32 %sel
 174 }
 175
 176 ; Expensive hot value operand and cheap cold value operand.
 177 define i32 @expensive_val_operand2(ptr nocapture %a, i32 %x, i1 %cmp) {
 178 ; CHECK-LABEL: @expensive_val_operand2(
 179 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8
 180 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[X:%.*]], i32 [[LOAD]], !prof [[PROF18]]
 181 ; CHECK-NEXT:    ret i32 [[SEL]]
 182 ;
 183   %load = load i32, ptr %a, align 8
 184   %sel = select i1 %cmp, i32 %x, i32 %load, !prof !17
 185   ret i32 %sel
 186 }
 187
 188 ; Cold value operand with load in its one-use dependence slice should result
 189 ; into a branch with sinked dependence slice.
 190 define i32 @expensive_val_operand3(ptr nocapture %a, i32 %b, i32 %y, i1 %cmp) {
 191 ; CHECK-LABEL: @expensive_val_operand3(
 192 ; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
 193 ; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]
 194 ; CHECK:       select.true.sink:
 195 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8
 196 ; CHECK-NEXT:    [[X:%.*]] = add i32 [[LOAD]], [[B:%.*]]
 197 ; CHECK-NEXT:    br label [[SELECT_END]]
 198 ; CHECK:       select.end:
 199 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[X]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[TMP0:%.*]] ]
 200 ; CHECK-NEXT:    ret i32 [[SEL]]
 201 ;
 202   %load = load i32, ptr %a, align 8
 203   %x = add i32 %load, %b
 204   %sel = select i1 %cmp, i32 %x, i32 %y, !prof !17
 205   ret i32 %sel
 206 }
 207
 208 ; Expensive cold value operand with unsafe-to-sink (due to func call) load (partial slice sinking).
 209 define i32 @expensive_val_operand4(ptr nocapture %a, i32 %b, i32 %y, i1 %cmp) {
 210 ; CHECK-LABEL: @expensive_val_operand4(
 211 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8
 212 ; CHECK-NEXT:    call void @free(ptr [[A]])
 213 ; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
 214 ; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]
 215 ; CHECK:       select.true.sink:
 216 ; CHECK-NEXT:    [[X:%.*]] = add i32 [[LOAD]], [[B:%.*]]
 217 ; CHECK-NEXT:    br label [[SELECT_END]]
 218 ; CHECK:       select.end:
 219 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[X]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[TMP0:%.*]] ]
 220 ; CHECK-NEXT:    ret i32 [[SEL]]
 221 ;
 222   %load = load i32, ptr %a, align 8
 223   call void @free(ptr %a)
 224   %x = add i32 %load, %b
 225   %sel = select i1 %cmp, i32 %x, i32 %y, !prof !17
 226   ret i32 %sel
 227 }
 228
 229 ; Expensive cold value operand with unsafe-to-sink (due to lifetime-end marker) load (partial slice sinking).
 230 define i32 @expensive_val_operand5(ptr nocapture %a, i32 %b, i32 %y, i1 %cmp) {
 231 ; CHECK-LABEL: @expensive_val_operand5(
 232 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8
 233 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 2, ptr nonnull [[A]])
 234 ; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
 235 ; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]
 236 ; CHECK:       select.true.sink:
 237 ; CHECK-NEXT:    [[X:%.*]] = add i32 [[LOAD]], [[B:%.*]]
 238 ; CHECK-NEXT:    br label [[SELECT_END]]
 239 ; CHECK:       select.end:
 240 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[X]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[TMP0:%.*]] ]
 241 ; CHECK-NEXT:    ret i32 [[SEL]]
 242 ;
 243   %load = load i32, ptr %a, align 8
 244   call void @llvm.lifetime.end.p0(i64 2, ptr nonnull %a)
 245   %x = add i32 %load, %b
 246   %sel = select i1 %cmp, i32 %x, i32 %y, !prof !17
 247   ret i32 %sel
 248 }
 249
 250 ; Expensive cold value operand with potentially-unsafe-to-sink load (located
 251 ; in a different basic block and thus unchecked for sinkability).
 252 define i32 @expensive_val_operand6(ptr nocapture %a, i32 %b, i32 %y, i1 %cmp) {
 253 ; CHECK-LABEL: @expensive_val_operand6(
 254 ; CHECK-NEXT:  entry:
 255 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[A:%.*]], align 8
 256 ; CHECK-NEXT:    br label [[BB1:%.*]]
 257 ; CHECK:       bb1:
 258 ; CHECK-NEXT:    [[SEL_FROZEN:%.*]] = freeze i1 [[CMP:%.*]]
 259 ; CHECK-NEXT:    br i1 [[SEL_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END:%.*]], !prof [[PROF18]]
 260 ; CHECK:       select.true.sink:
 261 ; CHECK-NEXT:    [[X:%.*]] = add i32 [[LOAD]], [[B:%.*]]
 262 ; CHECK-NEXT:    br label [[SELECT_END]]
 263 ; CHECK:       select.end:
 264 ; CHECK-NEXT:    [[SEL:%.*]] = phi i32 [ [[X]], [[SELECT_TRUE_SINK]] ], [ [[Y:%.*]], [[BB1]] ]
 265 ; CHECK-NEXT:    ret i32 [[SEL]]
 266 ;
 267 entry:
 268   %load = load i32, ptr %a, align 8
 269   br label %bb1
 270 bb1:                                 ; preds = %entry
 271   %x = add i32 %load, %b
 272   %sel = select i1 %cmp, i32 %x, i32 %y, !prof !17
 273   ret i32 %sel
 274 }
 275
 276 ; Multiple uses of the load value operand.
 277 define i32 @expensive_val_operand7(i32 %a, ptr nocapture %b, i32 %x, i1 %cmp) {
 278 ; CHECK-LABEL: @expensive_val_operand7(
 279 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[B:%.*]], align 4
 280 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP:%.*]], i32 [[X:%.*]], i32 [[LOAD]]
 281 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SEL]], [[LOAD]]
 282 ; CHECK-NEXT:    ret i32 [[ADD]]
 283 ;
 284   %load = load i32, ptr %b, align 4
 285   %sel = select i1 %cmp, i32 %x, i32 %load
 286   %add = add i32 %sel, %load
 287   ret i32 %add
 288 }
 289
 290 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 291 ;; Test loop heuristic: loop-level critical-path analysis
 292 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 293
 294 ;; Use of cmov in this test would put a load and a fsub on the critical path.
 295 ;; Loop-level analysis should decide to form a branch.
 296 ;;
 297 ;;double cmov_on_critical_path(int n, double x, ptr a) {
 298 ;;  for (int i = 0; i < n; i++) {
 299 ;;    double r = a[i];
 300 ;;    if (x > r)
 301 ;;                      // 50% of iterations
 302 ;;              x -= r;
 303 ;;  }
 304 ;;  return x;
 305 ;;}
 306 define double @cmov_on_critical_path(i32 %n, double %x, ptr nocapture %a) {
 307 ; CHECK-LABEL: @cmov_on_critical_path(
 308 ; CHECK-NEXT:  entry:
 309 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[N:%.*]], 0
 310 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
 311 ; CHECK:       for.cond.cleanup:
 312 ; CHECK-NEXT:    ret double [[X:%.*]]
 313 ; CHECK:       for.body.preheader:
 314 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
 315 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 316 ; CHECK:       for.body:
 317 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[SELECT_END:%.*]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
 318 ; CHECK-NEXT:    [[X1:%.*]] = phi double [ [[X2:%.*]], [[SELECT_END]] ], [ [[X]], [[FOR_BODY_PREHEADER]] ]
 319 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds double, ptr [[A:%.*]], i64 [[INDVARS_IV]]
 320 ; CHECK-NEXT:    [[R:%.*]] = load double, ptr [[ARRAYIDX]], align 8
 321 ; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ogt double [[X1]], [[R]]
 322 ; CHECK-NEXT:    [[X2_FROZEN:%.*]] = freeze i1 [[CMP2]]
 323 ; CHECK-NEXT:    br i1 [[X2_FROZEN]], label [[SELECT_TRUE_SINK:%.*]], label [[SELECT_END]], !prof [[PROF27:![0-9]+]]
 324 ; CHECK:       select.true.sink:
 325 ; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[X1]], [[R]]
 326 ; CHECK-NEXT:    br label [[SELECT_END]]
 327 ; CHECK:       select.end:
 328 ; CHECK-NEXT:    [[X2]] = phi double [ [[SUB]], [[SELECT_TRUE_SINK]] ], [ [[X1]], [[FOR_BODY]] ]
 329 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 330 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 331 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_EXIT:%.*]], label [[FOR_BODY]]
 332 ; CHECK:       for.exit:
 333 ; CHECK-NEXT:    ret double [[X2]]
 334 ;
 335 entry:
 336   %cmp1 = icmp sgt i32 %n, 0
 337   br i1 %cmp1, label %for.body.preheader, label %for.cond.cleanup
 338
 339 for.cond.cleanup:                                 ; preds = %entry
 340   ret double %x
 341
 342 for.body.preheader:                               ; preds = %entry
 343   %wide.trip.count = zext i32 %n to i64
 344   br label %for.body
 345
 346 for.body:                                         ; preds = %for.body.preheader, %for.body
 347   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
 348   %x1 = phi double [ %x2, %for.body ], [ %x, %for.body.preheader ]
 349   %arrayidx = getelementptr inbounds double, ptr %a, i64 %indvars.iv
 350   %r = load double, ptr %arrayidx, align 8
 351   %sub = fsub double %x1, %r
 352   %cmp2 = fcmp ogt double %x1, %r
 353   %x2 = select i1 %cmp2, double %sub, double %x1, !prof !18
 354   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 355   %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
 356   br i1 %exitcond, label %for.exit, label %for.body
 357
 358 for.exit:                                         ; preds = %for.body
 359   ret double %x2
 360 }
 361
 362 ;; The common path includes expensive operations (load and fsub) making
 363 ;; branch similarly expensive to cmov, and thus the gain is small.
 364 ;; Loop-level analysis should decide on not forming a branch.
 365 ;;
 366 ;;double small_gain(int n, double x, ptr a) {
 367 ;;  for (int i = 0; i < n; i++) {
 368 ;;    double r = a[i];
 369 ;;    if (x > r)
 370 ;;      // 99% of iterations
 371 ;;      x -= r;
 372 ;;  }
 373 ;;  return x;
 374 ;;}
 375 define double @small_gain(i32 %n, double %x, ptr nocapture %a) {
 376 ; CHECK-LABEL: @small_gain(
 377 ; CHECK-NEXT:  entry:
 378 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[N:%.*]], 0
 379 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
 380 ; CHECK:       for.cond.cleanup:
 381 ; CHECK-NEXT:    ret double [[X:%.*]]
 382 ; CHECK:       for.body.preheader:
 383 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
 384 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 385 ; CHECK:       for.body:
 386 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
 387 ; CHECK-NEXT:    [[X1:%.*]] = phi double [ [[X2:%.*]], [[FOR_BODY]] ], [ [[X]], [[FOR_BODY_PREHEADER]] ]
 388 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds double, ptr [[A:%.*]], i64 [[INDVARS_IV]]
 389 ; CHECK-NEXT:    [[R:%.*]] = load double, ptr [[ARRAYIDX]], align 8
 390 ; CHECK-NEXT:    [[SUB:%.*]] = fsub double [[X1]], [[R]]
 391 ; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ole double [[X1]], [[R]]
 392 ; CHECK-NEXT:    [[X2]] = select i1 [[CMP2]], double [[X1]], double [[SUB]], !prof [[PROF18]]
 393 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 394 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 395 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_EXIT:%.*]], label [[FOR_BODY]]
 396 ; CHECK:       for.exit:
 397 ; CHECK-NEXT:    ret double [[X2]]
 398 ;
 399 entry:
 400   %cmp1 = icmp sgt i32 %n, 0
 401   br i1 %cmp1, label %for.body.preheader, label %for.cond.cleanup
 402
 403 for.cond.cleanup:                                 ; preds = %entry
 404   ret double %x
 405
 406 for.body.preheader:                               ; preds = %entry
 407   %wide.trip.count = zext i32 %n to i64
 408   br label %for.body
 409
 410 for.body:                                         ; preds = %for.body.preheader, %for.body
 411   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
 412   %x1 = phi double [ %x2, %for.body ], [ %x, %for.body.preheader ]
 413   %arrayidx = getelementptr inbounds double, ptr %a, i64 %indvars.iv
 414   %r = load double, ptr %arrayidx, align 8
 415   %sub = fsub double %x1, %r
 416   %cmp2 = fcmp ole double %x1, %r
 417   %x2 = select i1 %cmp2, double %x1, double %sub, !prof !17
 418   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 419   %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
 420   br i1 %exitcond, label %for.exit, label %for.body
 421
 422 for.exit:                                         ; preds = %for.body
 423   ret double %x2
 424 }
 425
 426 ;; One select on the critical path and one off the critical path.
 427 ;; Loop-level analysis should decide to form a branch only for
 428 ;; the select on the critical path.
 429 ;;
 430 ;;double loop_select_groups(int n, double x, ptr a, int k) {
 431 ;;  int c = 0;
 432 ;;  for (int i = 0; i < n; i++) {
 433 ;;    double r = a[i];
 434 ;;    if (x > r)
 435 ;;      x -= r;
 436 ;;    if (i == k)
 437 ;;      c += n;
 438 ;;  }
 439 ;;  return x + c;
 440 ;;}
 441 define double @loop_select_groups(i32 %n, double %x, ptr nocapture %a, i32 %k) {
 442 ; CHECK-LABEL: @loop_select_groups(
 443 ; CHECK-NEXT:  entry:
 444 ; CHECK-NEXT:    [[CMP19:%.*]] = icmp sgt i32 [[N:%.*]], 0
 445 ; CHECK-NEXT:    br i1 [[CMP19]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
 446 ; CHECK:       for.body.preheader:
 447 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
 448 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 449 ; CHECK:       for.cond.cleanup.loopexit:
 450 ; CHECK-NEXT:    [[PHI_CAST:%.*]] = sitofp i32 [[C_1:%.*]] to double
 451 ; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
 452 ; CHECK:       for.cond.cleanup:
 453 ; CHECK-NEXT:    [[C_0_LCSSA:%.*]] = phi double [ 0.000000e+00, [[ENTRY:%.*]] ], [ [[PHI_CAST]], [[FOR_COND_CLEANUP_LOOPEXIT:%.*]] ]
 454 ; CHECK-NEXT:    [[X_ADDR_0_LCSSA:%.*]] = phi double [ [[X:%.*]], [[ENTRY]] ], [ [[X_ADDR_1:%.*]], [[FOR_COND_CLEANUP_LOOPEXIT]] ]
 455 ; CHECK-NEXT:    [[ADD5:%.*]] = fadd double [[X_ADDR_0_LCSSA]], [[C_0_LCSSA]]
 456 ; CHECK-NEXT:    ret double [[ADD5]]
 457 ; CHECK:       for.body:
 458 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[SELECT_END:%.*]] ]
 459 ; CHECK-NEXT:    [[X_ADDR_022:%.*]] = phi double [ [[X]], [[FOR_BODY_PREHEADER]] ], [ [[X_ADDR_1]], [[SELECT_END]] ]
 460 ; CHECK-NEXT:    [[C_020:%.*]] = phi i32 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[C_1]], [[SELECT_END]] ]
 461 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds double, ptr [[A:%.*]], i64 [[INDVARS_IV]]
 462 ; CHECK-NEXT:    [[TMP0:%.*]] = load double, ptr [[ARRAYIDX]], align 8
 463 ; CHECK-NEXT:    [[CMP1:%.*]] = fcmp ogt double [[X_ADDR_022]], [[TMP0]]
 464 ; CHECK-NEXT:    [[SUB_FROZEN:%.*]] = freeze i1 [[CMP1]]
 465 ; CHECK-NEXT:    br i1 [[SUB_FROZEN]], label [[SELECT_END]], label [[SELECT_FALSE:%.*]]
 466 ; CHECK:       select.false:
 467 ; CHECK-NEXT:    br label [[SELECT_END]]
 468 ; CHECK:       select.end:
 469 ; CHECK-NEXT:    [[SUB:%.*]] = phi double [ [[TMP0]], [[FOR_BODY]] ], [ 0.000000e+00, [[SELECT_FALSE]] ]
 470 ; CHECK-NEXT:    [[X_ADDR_1]] = fsub double [[X_ADDR_022]], [[SUB]]
 471 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32
 472 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[K:%.*]], [[N]]
 473 ; CHECK-NEXT:    [[ADD:%.*]] = select i1 [[CMP2]], i32 [[N]], i32 0
 474 ; CHECK-NEXT:    [[C_1]] = add nsw i32 [[ADD]], [[C_020]]
 475 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 476 ; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 477 ; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP_LOOPEXIT]], label [[FOR_BODY]]
 478 ;
 479 entry:
 480   %cmp19 = icmp sgt i32 %n, 0
 481   br i1 %cmp19, label %for.body.preheader, label %for.cond.cleanup
 482
 483 for.body.preheader:                               ; preds = %entry
 484   %wide.trip.count = zext i32 %n to i64
 485   br label %for.body
 486
 487 for.cond.cleanup.loopexit:                        ; preds = %for.body
 488   %phi.cast = sitofp i32 %c.1 to double
 489   br label %for.cond.cleanup
 490
 491 for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
 492   %c.0.lcssa = phi double [ 0.000000e+00, %entry ], [ %phi.cast, %for.cond.cleanup.loopexit ]
 493   %x.addr.0.lcssa = phi double [ %x, %entry ], [ %x.addr.1, %for.cond.cleanup.loopexit ]
 494   %add5 = fadd double %x.addr.0.lcssa, %c.0.lcssa
 495   ret double %add5
 496
 497 for.body:                                         ; preds = %for.body.preheader, %for.body
 498   %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
 499   %x.addr.022 = phi double [ %x, %for.body.preheader ], [ %x.addr.1, %for.body ]
 500   %c.020 = phi i32 [ 0, %for.body.preheader ], [ %c.1, %for.body ]
 501   %arrayidx = getelementptr inbounds double, ptr %a, i64 %indvars.iv
 502   %0 = load double, ptr %arrayidx, align 8
 503   %cmp1 = fcmp ogt double %x.addr.022, %0
 504   %sub = select i1 %cmp1, double %0, double 0.000000e+00
 505   %x.addr.1 = fsub double %x.addr.022, %sub
 506   %1 = trunc i64 %indvars.iv to i32
 507   %cmp2 = icmp eq i32 %k, %n
 508   %add = select i1 %cmp2, i32 %n, i32 0
 509   %c.1 = add nsw i32 %add, %c.020
 510   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 511   %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count
 512   br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body
 513 }
 514
 515 ; Function Attrs: nounwind readnone speculatable willreturn
 516 declare void @llvm.dbg.value(metadata, metadata, metadata)
 517
 518 ; Function Attrs: argmemonly mustprogress nocallback nofree nosync nounwind willreturn
 519 declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture)
 520
 521 declare void @free(ptr nocapture)
 522
 523 !llvm.module.flags = !{!0, !26, !27}
 524 !0 = !{i32 1, !"ProfileSummary", !1}
 525 !1 = !{!2, !3, !4, !5, !6, !7, !8, !9}
 526 !2 = !{!"ProfileFormat", !"InstrProf"}
 527 !3 = !{!"TotalCount", i64 10000}
 528 !4 = !{!"MaxCount", i64 10}
 529 !5 = !{!"MaxInternalCount", i64 1}
 530 !6 = !{!"MaxFunctionCount", i64 1000}
 531 !7 = !{!"NumCounts", i64 3}
 532 !8 = !{!"NumFunctions", i64 3}
 533 !9 = !{!"DetailedSummary", !10}
 534 !10 = !{!11, !12, !13}
 535 !11 = !{i32 10000, i64 100, i32 1}
 536 !12 = !{i32 999000, i64 100, i32 1}
 537 !13 = !{i32 999999, i64 1, i32 2}
 538 !14 = !{!"function_entry_count", i64 0}
 539 !15 = !{!"branch_weights", i32 1, i32 100}
 540 !16 = !{!"branch_weights", i32 100, i32 1}
 541 !17 = !{!"branch_weights", i32 1, i32 99}
 542 !18 = !{!"branch_weights", i32 50, i32 50}
 543 !19 = !{!"function_entry_count", i64 100}
 544 !20 = !{}
 545 !21 = !DIFile(filename: "test.c", directory: "/test")
 546 !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)
 547 !23 = distinct !DISubprogram(name: "test", scope: !21, file: !21, line: 1, unit: !22)
 548 !24 = !DILocalVariable(name: "x", scope: !23)
 549 !25 = !{}
 550 !26 = !{i32 2, !"Dwarf Version", i32 4}
 551 !27 = !{i32 1, !"Debug Info Version", i32 3}
 552 !28 = !{!"branch_weights", i32 30, i32 70}