llvm/test/Transforms/LoopStrengthReduce/depth-limit-overrun.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -passes 'loop-reduce' -scalar-evolution-max-arith-depth=2 -S < %s | FileCheck --check-prefixes=DEFAULT %s
   3 ; RUN: opt -loop-reduce -scalar-evolution-max-arith-depth=2 -S < %s | FileCheck --check-prefixes=LIMIT %s
   4
   5 ; This test should just compile cleanly without assertions.
   6
   7 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
   8
   9 define void @test(i32 %A, i32 %B, i32 %C) {
  10 ; DEFAULT-LABEL: @test(
  11 ; DEFAULT-NEXT:  entry:
  12 ; DEFAULT-NEXT:    [[TMP0:%.*]] = mul i32 [[C:%.*]], -3
  13 ; DEFAULT-NEXT:    br label [[OUTER_LOOP:%.*]]
  14 ; DEFAULT:       outer_loop:
  15 ; DEFAULT-NEXT:    [[PHI2:%.*]] = phi i32 [ [[A:%.*]], [[ENTRY:%.*]] ], [ 204, [[OUTER_TAIL:%.*]] ]
  16 ; DEFAULT-NEXT:    [[PHI3:%.*]] = phi i32 [ [[A]], [[ENTRY]] ], [ 243, [[OUTER_TAIL]] ]
  17 ; DEFAULT-NEXT:    [[PHI4:%.*]] = phi i32 [ [[B:%.*]], [[ENTRY]] ], [ [[I35:%.*]], [[OUTER_TAIL]] ]
  18 ; DEFAULT-NEXT:    br label [[GUARD:%.*]]
  19 ; DEFAULT:       guard:
  20 ; DEFAULT-NEXT:    [[LCMP_MOD:%.*]] = icmp eq i32 [[C]], 0
  21 ; DEFAULT-NEXT:    br i1 [[LCMP_MOD]], label [[OUTER_TAIL]], label [[PREHEADER:%.*]]
  22 ; DEFAULT:       preheader:
  23 ; DEFAULT-NEXT:    [[I15:%.*]] = shl i32 [[B]], 1
  24 ; DEFAULT-NEXT:    [[TMP1:%.*]] = mul i32 [[PHI2]], -1
  25 ; DEFAULT-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP1]], -1
  26 ; DEFAULT-NEXT:    [[TMP3:%.*]] = sub i32 [[PHI4]], [[TMP2]]
  27 ; DEFAULT-NEXT:    [[TMP4:%.*]] = add i32 [[B]], [[PHI4]]
  28 ; DEFAULT-NEXT:    [[TMP5:%.*]] = sub i32 [[TMP4]], [[TMP2]]
  29 ; DEFAULT-NEXT:    [[TMP6:%.*]] = sub i32 14, [[TMP5]]
  30 ; DEFAULT-NEXT:    [[TMP7:%.*]] = add i32 [[TMP0]], [[PHI2]]
  31 ; DEFAULT-NEXT:    br label [[INNER_LOOP:%.*]]
  32 ; DEFAULT:       inner_loop:
  33 ; DEFAULT-NEXT:    [[LSR_IV3:%.*]] = phi i32 [ [[LSR_IV_NEXT4:%.*]], [[INNER_LOOP]] ], [ [[TMP6]], [[PREHEADER]] ]
  34 ; DEFAULT-NEXT:    [[LSR_IV1:%.*]] = phi i32 [ [[LSR_IV_NEXT2:%.*]], [[INNER_LOOP]] ], [ [[TMP5]], [[PREHEADER]] ]
  35 ; DEFAULT-NEXT:    [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], [[INNER_LOOP]] ], [ [[TMP3]], [[PREHEADER]] ]
  36 ; DEFAULT-NEXT:    [[PHI5:%.*]] = phi i32 [ [[PHI3]], [[PREHEADER]] ], [ [[I30:%.*]], [[INNER_LOOP]] ]
  37 ; DEFAULT-NEXT:    [[PHI6:%.*]] = phi i32 [ [[PHI2]], [[PREHEADER]] ], [ [[I33:%.*]], [[INNER_LOOP]] ]
  38 ; DEFAULT-NEXT:    [[ITER:%.*]] = phi i32 [ [[C]], [[PREHEADER]] ], [ [[ITER_SUB:%.*]], [[INNER_LOOP]] ]
  39 ; DEFAULT-NEXT:    [[I17:%.*]] = sub i32 [[PHI4]], [[PHI6]]
  40 ; DEFAULT-NEXT:    [[I18:%.*]] = sub i32 14, [[PHI5]]
  41 ; DEFAULT-NEXT:    [[I19:%.*]] = mul i32 [[I18]], [[C]]
  42 ; DEFAULT-NEXT:    [[FACTOR_PROL:%.*]] = shl i32 [[PHI5]], 1
  43 ; DEFAULT-NEXT:    [[TMP8:%.*]] = add i32 [[LSR_IV1]], [[I19]]
  44 ; DEFAULT-NEXT:    [[TMP9:%.*]] = add i32 [[TMP8]], [[FACTOR_PROL]]
  45 ; DEFAULT-NEXT:    [[TMP10:%.*]] = shl i32 [[TMP9]], 1
  46 ; DEFAULT-NEXT:    [[TMP11:%.*]] = add i32 [[LSR_IV]], [[TMP10]]
  47 ; DEFAULT-NEXT:    [[TMP12:%.*]] = sub i32 [[LSR_IV3]], [[I19]]
  48 ; DEFAULT-NEXT:    [[TMP13:%.*]] = sub i32 [[TMP12]], [[FACTOR_PROL]]
  49 ; DEFAULT-NEXT:    [[TMP14:%.*]] = mul i32 [[C]], [[TMP13]]
  50 ; DEFAULT-NEXT:    [[TMP15:%.*]] = add i32 [[LSR_IV1]], [[I19]]
  51 ; DEFAULT-NEXT:    [[TMP16:%.*]] = add i32 [[TMP15]], [[FACTOR_PROL]]
  52 ; DEFAULT-NEXT:    [[TMP17:%.*]] = shl i32 [[TMP16]], 1
  53 ; DEFAULT-NEXT:    [[TMP18:%.*]] = add i32 [[TMP14]], [[TMP17]]
  54 ; DEFAULT-NEXT:    [[TMP19:%.*]] = add i32 [[LSR_IV]], [[TMP18]]
  55 ; DEFAULT-NEXT:    [[I29:%.*]] = mul i32 [[TMP11]], [[C]]
  56 ; DEFAULT-NEXT:    [[FACTOR_2_PROL:%.*]] = shl i32 [[TMP19]], 1
  57 ; DEFAULT-NEXT:    [[I30]] = add i32 [[I17]], [[FACTOR_2_PROL]]
  58 ; DEFAULT-NEXT:    [[I33]] = add i32 [[PHI6]], -3
  59 ; DEFAULT-NEXT:    [[ITER_SUB]] = add i32 [[ITER]], -1
  60 ; DEFAULT-NEXT:    [[LSR_IV_NEXT]] = add i32 [[LSR_IV]], 3
  61 ; DEFAULT-NEXT:    [[LSR_IV_NEXT2]] = add i32 [[LSR_IV1]], 3
  62 ; DEFAULT-NEXT:    [[LSR_IV_NEXT4]] = add i32 [[LSR_IV3]], -3
  63 ; DEFAULT-NEXT:    [[ITER_CMP:%.*]] = icmp eq i32 [[ITER_SUB]], 0
  64 ; DEFAULT-NEXT:    br i1 [[ITER_CMP]], label [[OUTER_TAIL_LOOPEXIT:%.*]], label [[INNER_LOOP]]
  65 ; DEFAULT:       outer_tail.loopexit:
  66 ; DEFAULT-NEXT:    br label [[OUTER_TAIL]]
  67 ; DEFAULT:       outer_tail:
  68 ; DEFAULT-NEXT:    [[PHI7:%.*]] = phi i32 [ [[PHI2]], [[GUARD]] ], [ [[TMP7]], [[OUTER_TAIL_LOOPEXIT]] ]
  69 ; DEFAULT-NEXT:    [[I35]] = sub i32 [[A]], [[PHI7]]
  70 ; DEFAULT-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[I35]], 9876
  71 ; DEFAULT-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[OUTER_LOOP]]
  72 ; DEFAULT:       exit:
  73 ; DEFAULT-NEXT:    ret void
  74 ;
  75 ; LIMIT-LABEL: @test(
  76 ; LIMIT-NEXT:  entry:
  77 ; LIMIT-NEXT:    [[TMP0:%.*]] = mul i32 [[C:%.*]], -3
  78 ; LIMIT-NEXT:    br label [[OUTER_LOOP:%.*]]
  79 ; LIMIT:       outer_loop:
  80 ; LIMIT-NEXT:    [[PHI2:%.*]] = phi i32 [ [[A:%.*]], [[ENTRY:%.*]] ], [ 204, [[OUTER_TAIL:%.*]] ]
  81 ; LIMIT-NEXT:    [[PHI3:%.*]] = phi i32 [ [[A]], [[ENTRY]] ], [ 243, [[OUTER_TAIL]] ]
  82 ; LIMIT-NEXT:    [[PHI4:%.*]] = phi i32 [ [[B:%.*]], [[ENTRY]] ], [ [[I35:%.*]], [[OUTER_TAIL]] ]
  83 ; LIMIT-NEXT:    br label [[GUARD:%.*]]
  84 ; LIMIT:       guard:
  85 ; LIMIT-NEXT:    [[LCMP_MOD:%.*]] = icmp eq i32 [[C]], 0
  86 ; LIMIT-NEXT:    br i1 [[LCMP_MOD]], label [[OUTER_TAIL]], label [[PREHEADER:%.*]]
  87 ; LIMIT:       preheader:
  88 ; LIMIT-NEXT:    [[I15:%.*]] = shl i32 [[B]], 1
  89 ; LIMIT-NEXT:    [[TMP1:%.*]] = mul i32 [[PHI2]], -1
  90 ; LIMIT-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP1]], -1
  91 ; LIMIT-NEXT:    [[TMP3:%.*]] = sub i32 [[PHI4]], [[TMP2]]
  92 ; LIMIT-NEXT:    [[TMP4:%.*]] = add i32 [[B]], [[PHI4]]
  93 ; LIMIT-NEXT:    [[TMP5:%.*]] = sub i32 [[TMP4]], [[TMP2]]
  94 ; LIMIT-NEXT:    [[TMP6:%.*]] = sub i32 14, [[TMP5]]
  95 ; LIMIT-NEXT:    [[TMP7:%.*]] = add i32 [[TMP0]], [[PHI2]]
  96 ; LIMIT-NEXT:    br label [[INNER_LOOP:%.*]]
  97 ; LIMIT:       inner_loop:
  98 ; LIMIT-NEXT:    [[LSR_IV3:%.*]] = phi i32 [ [[LSR_IV_NEXT4:%.*]], [[INNER_LOOP]] ], [ [[TMP6]], [[PREHEADER]] ]
  99 ; LIMIT-NEXT:    [[LSR_IV1:%.*]] = phi i32 [ [[LSR_IV_NEXT2:%.*]], [[INNER_LOOP]] ], [ [[TMP5]], [[PREHEADER]] ]
 100 ; LIMIT-NEXT:    [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], [[INNER_LOOP]] ], [ [[TMP3]], [[PREHEADER]] ]
 101 ; LIMIT-NEXT:    [[PHI5:%.*]] = phi i32 [ [[PHI3]], [[PREHEADER]] ], [ [[I30:%.*]], [[INNER_LOOP]] ]
 102 ; LIMIT-NEXT:    [[PHI6:%.*]] = phi i32 [ [[PHI2]], [[PREHEADER]] ], [ [[I33:%.*]], [[INNER_LOOP]] ]
 103 ; LIMIT-NEXT:    [[ITER:%.*]] = phi i32 [ [[C]], [[PREHEADER]] ], [ [[ITER_SUB:%.*]], [[INNER_LOOP]] ]
 104 ; LIMIT-NEXT:    [[I17:%.*]] = sub i32 [[PHI4]], [[PHI6]]
 105 ; LIMIT-NEXT:    [[I18:%.*]] = sub i32 14, [[PHI5]]
 106 ; LIMIT-NEXT:    [[I19:%.*]] = mul i32 [[I18]], [[C]]
 107 ; LIMIT-NEXT:    [[FACTOR_PROL:%.*]] = shl i32 [[PHI5]], 1
 108 ; LIMIT-NEXT:    [[TMP8:%.*]] = add i32 [[LSR_IV1]], [[I19]]
 109 ; LIMIT-NEXT:    [[TMP9:%.*]] = add i32 [[TMP8]], [[FACTOR_PROL]]
 110 ; LIMIT-NEXT:    [[TMP10:%.*]] = shl i32 [[TMP9]], 1
 111 ; LIMIT-NEXT:    [[TMP11:%.*]] = add i32 [[LSR_IV]], [[TMP10]]
 112 ; LIMIT-NEXT:    [[TMP12:%.*]] = sub i32 [[LSR_IV3]], [[I19]]
 113 ; LIMIT-NEXT:    [[TMP13:%.*]] = sub i32 [[TMP12]], [[FACTOR_PROL]]
 114 ; LIMIT-NEXT:    [[TMP14:%.*]] = mul i32 [[C]], [[TMP13]]
 115 ; LIMIT-NEXT:    [[TMP15:%.*]] = add i32 [[LSR_IV1]], [[I19]]
 116 ; LIMIT-NEXT:    [[TMP16:%.*]] = add i32 [[TMP15]], [[FACTOR_PROL]]
 117 ; LIMIT-NEXT:    [[TMP17:%.*]] = shl i32 [[TMP16]], 1
 118 ; LIMIT-NEXT:    [[TMP18:%.*]] = add i32 [[TMP14]], [[TMP17]]
 119 ; LIMIT-NEXT:    [[TMP19:%.*]] = add i32 [[LSR_IV]], [[TMP18]]
 120 ; LIMIT-NEXT:    [[I29:%.*]] = mul i32 [[TMP11]], [[C]]
 121 ; LIMIT-NEXT:    [[FACTOR_2_PROL:%.*]] = shl i32 [[TMP19]], 1
 122 ; LIMIT-NEXT:    [[I30]] = add i32 [[I17]], [[FACTOR_2_PROL]]
 123 ; LIMIT-NEXT:    [[I33]] = add i32 [[PHI6]], -3
 124 ; LIMIT-NEXT:    [[ITER_SUB]] = add i32 [[ITER]], -1
 125 ; LIMIT-NEXT:    [[LSR_IV_NEXT]] = add i32 [[LSR_IV]], 3
 126 ; LIMIT-NEXT:    [[LSR_IV_NEXT2]] = add i32 [[LSR_IV1]], 3
 127 ; LIMIT-NEXT:    [[LSR_IV_NEXT4]] = add i32 [[LSR_IV3]], -3
 128 ; LIMIT-NEXT:    [[ITER_CMP:%.*]] = icmp eq i32 [[ITER_SUB]], 0
 129 ; LIMIT-NEXT:    br i1 [[ITER_CMP]], label [[OUTER_TAIL_LOOPEXIT:%.*]], label [[INNER_LOOP]]
 130 ; LIMIT:       outer_tail.loopexit:
 131 ; LIMIT-NEXT:    br label [[OUTER_TAIL]]
 132 ; LIMIT:       outer_tail:
 133 ; LIMIT-NEXT:    [[PHI7:%.*]] = phi i32 [ [[PHI2]], [[GUARD]] ], [ [[TMP7]], [[OUTER_TAIL_LOOPEXIT]] ]
 134 ; LIMIT-NEXT:    [[I35]] = sub i32 [[A]], [[PHI7]]
 135 ; LIMIT-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[I35]], 9876
 136 ; LIMIT-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[OUTER_LOOP]]
 137 ; LIMIT:       exit:
 138 ; LIMIT-NEXT:    ret void
 139 ;
 140 entry:
 141   br label %outer_loop
 142
 143 outer_loop:
 144   %phi2 = phi i32 [ %A, %entry ], [ 204, %outer_tail ]
 145   %phi3 = phi i32 [ %A, %entry ], [ 243, %outer_tail ]
 146   %phi4 = phi i32 [ %B, %entry ], [ %i35, %outer_tail ]
 147   br label %guard
 148
 149 guard:
 150   %lcmp.mod = icmp eq i32 %C, 0
 151   br i1 %lcmp.mod, label %outer_tail, label %preheader
 152
 153 preheader:
 154   %i15 = shl i32 %B, 1
 155   br label %inner_loop
 156
 157 inner_loop:
 158   %phi5 = phi i32 [ %phi3, %preheader ], [ %i30, %inner_loop ]
 159   %phi6 = phi i32 [ %phi2, %preheader ], [ %i33, %inner_loop ]
 160   %iter = phi i32 [ %C, %preheader ], [ %iter.sub, %inner_loop ]
 161   %i17 = sub i32 %phi4, %phi6
 162   %i18 = sub i32 14, %phi5
 163   %i19 = mul i32 %i18, %C
 164   %factor.prol = shl i32 %phi5, 1
 165   %i20 = add i32 %i17, %factor.prol
 166   %i21 = add i32 %i20, %B
 167   %i22 = add i32 %i21, %i19
 168   %i23 = sub i32 14, %i22
 169   %i24 = mul i32 %i23, %C
 170   %factor.1.prol = shl i32 %i22, 1
 171   %i25 = add i32 %i17, %factor.1.prol
 172   %i27 = add i32 %i25, %i24
 173   %i29 = mul i32 %i25, %C
 174   %factor.2.prol = shl i32 %i27, 1
 175   %i30 = add i32 %i17, %factor.2.prol
 176   %i33 = add nsw i32 %phi6, -3
 177   %iter.sub = add i32 %iter, -1
 178   %iter.cmp = icmp eq i32 %iter.sub, 0
 179   br i1 %iter.cmp, label %outer_tail, label %inner_loop
 180
 181 outer_tail:
 182   %phi7 = phi i32 [ %phi2, %guard ], [ %i33, %inner_loop ]
 183   %i35 = sub i32 %A, %phi7
 184   %cmp = icmp sgt i32 %i35, 9876
 185   br i1 %cmp, label %exit, label %outer_loop
 186
 187 exit:
 188   ret void
 189
 190 }