llvm/test/Transforms/IndVarSimplify/rlev-add-me.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -S -passes=indvars < %s | FileCheck %s
   3 target datalayout = "n8:16:32:64"
   4 @G = external global i32
   5
   6 ; Basic case where we know the value of an induction variable along one
   7 ; exit edge, but not another.
   8 define i32 @test(i32 %n) {
   9 ; CHECK-LABEL: @test(
  10 ; CHECK-NEXT:  entry:
  11 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
  12 ; CHECK-NEXT:    br label [[HEADER:%.*]]
  13 ; CHECK:       header:
  14 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
  15 ; CHECK-NEXT:    [[V:%.*]] = load volatile i32, ptr @G
  16 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[V]], 0
  17 ; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]]
  18 ; CHECK:       latch:
  19 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
  20 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]]
  21 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]]
  22 ; CHECK:       exit1:
  23 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[HEADER]] ]
  24 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
  25 ; CHECK:       exit2:
  26 ; CHECK-NEXT:    ret i32 [[N]]
  27 ;
  28 entry:
  29   br label %header
  30 header:
  31   %iv = phi i32 [0, %entry], [%iv.next, %latch]
  32   %v = load volatile i32, ptr @G
  33   %cmp1 = icmp eq i32 %v, 0
  34   br i1 %cmp1, label %latch, label %exit1
  35
  36 latch:
  37   %iv.next = add i32 %iv, 1
  38   %cmp2 = icmp ult i32 %iv, %n
  39   br i1 %cmp2, label %header, label %exit2
  40 exit1:
  41   ret i32 %iv
  42 exit2:
  43   ret i32 %iv
  44 }
  45
  46 define i32 @test2(i32 %n) {
  47 ; CHECK-LABEL: @test2(
  48 ; CHECK-NEXT:  entry:
  49 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
  50 ; CHECK-NEXT:    br label [[HEADER:%.*]]
  51 ; CHECK:       header:
  52 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
  53 ; CHECK-NEXT:    [[V:%.*]] = load volatile i32, ptr @G
  54 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[V]], 0
  55 ; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]]
  56 ; CHECK:       latch:
  57 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
  58 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]]
  59 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]]
  60 ; CHECK:       exit1:
  61 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[HEADER]] ]
  62 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
  63 ; CHECK:       exit2:
  64 ; CHECK-NEXT:    ret i32 [[TMP0]]
  65 ;
  66 entry:
  67   br label %header
  68 header:
  69   %iv = phi i32 [0, %entry], [%iv.next, %latch]
  70   %v = load volatile i32, ptr @G
  71   %cmp1 = icmp eq i32 %v, 0
  72   br i1 %cmp1, label %latch, label %exit1
  73
  74 latch:
  75   %iv.next = add i32 %iv, 1
  76   %cmp2 = icmp ult i32 %iv, %n
  77   br i1 %cmp2, label %header, label %exit2
  78 exit1:
  79   ret i32 %iv
  80 exit2:
  81   ret i32 %iv.next
  82 }
  83
  84 define i32 @neg_wrong_loop(i32 %n) {
  85 ; CHECK-LABEL: @neg_wrong_loop(
  86 ; CHECK-NEXT:  entry:
  87 ; CHECK-NEXT:    br label [[WRONG_LOOP:%.*]]
  88 ; CHECK:       wrong_loop:
  89 ; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV2_NEXT:%.*]], [[WRONG_LOOP]] ]
  90 ; CHECK-NEXT:    [[IV2_NEXT]] = add i32 [[IV2]], 1
  91 ; CHECK-NEXT:    [[UNKNOWN:%.*]] = load volatile i32, ptr @G
  92 ; CHECK-NEXT:    [[CMP_UNK:%.*]] = icmp eq i32 [[UNKNOWN]], 0
  93 ; CHECK-NEXT:    br i1 [[CMP_UNK]], label [[HEADER_PREHEADER:%.*]], label [[WRONG_LOOP]]
  94 ; CHECK:       header.preheader:
  95 ; CHECK-NEXT:    [[IV2_LCSSA:%.*]] = phi i32 [ [[IV2]], [[WRONG_LOOP]] ]
  96 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
  97 ; CHECK-NEXT:    br label [[HEADER:%.*]]
  98 ; CHECK:       header:
  99 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[HEADER_PREHEADER]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
 100 ; CHECK-NEXT:    [[V:%.*]] = load volatile i32, ptr @G
 101 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[V]], 0
 102 ; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]]
 103 ; CHECK:       latch:
 104 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 105 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]]
 106 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]]
 107 ; CHECK:       exit1:
 108 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[HEADER]] ]
 109 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 110 ; CHECK:       exit2:
 111 ; CHECK-NEXT:    [[EXITVAL:%.*]] = phi i32 [ [[IV2_LCSSA]], [[LATCH]] ]
 112 ; CHECK-NEXT:    ret i32 [[EXITVAL]]
 113 ;
 114 entry:
 115   br label %wrong_loop
 116
 117 wrong_loop:
 118   %iv2 = phi i32 [0, %entry], [%iv2.next, %wrong_loop]
 119   %iv2.next = add i32 %iv2, 1
 120   %unknown = load volatile i32, ptr @G
 121   %cmp_unk = icmp eq i32 %unknown, 0
 122   br i1 %cmp_unk, label %header.preheader, label %wrong_loop
 123
 124 header.preheader:
 125   %iv2.lcssa = phi i32 [%iv2, %wrong_loop]
 126   br label %header
 127
 128 header:
 129   %iv = phi i32 [0, %header.preheader], [%iv.next, %latch]
 130   %v = load volatile i32, ptr @G
 131   %cmp1 = icmp eq i32 %v, 0
 132   br i1 %cmp1, label %latch, label %exit1
 133
 134 latch:
 135   %iv.next = add i32 %iv, 1
 136   %cmp2 = icmp ult i32 %iv, %n
 137   br i1 %cmp2, label %header, label %exit2
 138 exit1:
 139   ret i32 %iv
 140 exit2:
 141   %exitval = phi i32 [%iv2.lcssa, %latch]
 142   ret i32 %exitval
 143 }
 144
 145 ; TODO: Generalize the code to handle other SCEV expressions
 146 define i32 @test3(i32 %n) {
 147 ; CHECK-LABEL: @test3(
 148 ; CHECK-NEXT:  entry:
 149 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
 150 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 151 ; CHECK:       header:
 152 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
 153 ; CHECK-NEXT:    [[EXPR:%.*]] = udiv i32 [[IV]], 5
 154 ; CHECK-NEXT:    [[V:%.*]] = load volatile i32, ptr @G
 155 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[V]], 0
 156 ; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]]
 157 ; CHECK:       latch:
 158 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 159 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]]
 160 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]]
 161 ; CHECK:       exit1:
 162 ; CHECK-NEXT:    [[EXPR_LCSSA:%.*]] = phi i32 [ [[EXPR]], [[HEADER]] ]
 163 ; CHECK-NEXT:    ret i32 [[EXPR_LCSSA]]
 164 ; CHECK:       exit2:
 165 ; CHECK-NEXT:    [[EXPR_LCSSA1:%.*]] = phi i32 [ [[EXPR]], [[LATCH]] ]
 166 ; CHECK-NEXT:    ret i32 [[EXPR_LCSSA1]]
 167 ;
 168 entry:
 169   br label %header
 170 header:
 171   %iv = phi i32 [0, %entry], [%iv.next, %latch]
 172   %expr = udiv i32 %iv, 5
 173   %v = load volatile i32, ptr @G
 174   %cmp1 = icmp eq i32 %v, 0
 175   br i1 %cmp1, label %latch, label %exit1
 176
 177 latch:
 178   %iv.next = add i32 %iv, 1
 179   %cmp2 = icmp ult i32 %iv, %n
 180   br i1 %cmp2, label %header, label %exit2
 181 exit1:
 182   ret i32 %expr
 183 exit2:
 184   ret i32 %expr
 185 }
 186
 187
 188 ; A slightly more real example where we're searching for either a) the first
 189 ; non-zero element, or b) the end of a memory region.
 190 define i32 @bounded_find(i32 %n) {
 191 ; CHECK-LABEL: @bounded_find(
 192 ; CHECK-NEXT:  entry:
 193 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 1
 194 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 195 ; CHECK:       header:
 196 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
 197 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, ptr @G, i32 [[IV]]
 198 ; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[ADDR]]
 199 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[V]], 0
 200 ; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]]
 201 ; CHECK:       latch:
 202 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 203 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]]
 204 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]]
 205 ; CHECK:       exit1:
 206 ; CHECK-NEXT:    [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[HEADER]] ]
 207 ; CHECK-NEXT:    ret i32 [[IV_LCSSA]]
 208 ; CHECK:       exit2:
 209 ; CHECK-NEXT:    ret i32 [[N]]
 210 ;
 211 entry:
 212   br label %header
 213 header:
 214   %iv = phi i32 [0, %entry], [%iv.next, %latch]
 215   %addr = getelementptr i32, ptr @G, i32 %iv
 216   %v = load i32, ptr %addr
 217   %cmp1 = icmp eq i32 %v, 0
 218   br i1 %cmp1, label %latch, label %exit1
 219
 220 latch:
 221   %iv.next = add i32 %iv, 1
 222   %cmp2 = icmp ult i32 %iv, %n
 223   br i1 %cmp2, label %header, label %exit2
 224 exit1:
 225   ret i32 %iv
 226 exit2:
 227   ret i32 %iv
 228 }