llvm/test/Transforms/DeadStoreElimination/multiblock-loop-carried-dependence.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2
   3 ; RUN: opt -passes=dse -S %s | FileCheck %s
   4
   5 target datalayout = "e-m:e-i64:64-n32:64-v256:256:256-v512:512:512"
   6
   7 declare void @use(i32)
   8
   9 ; Test cases with a loop carried dependence in %loop.2, where both %l.0 and
  10 ; %l.1 read the value stored by the previous iteration. Hence, the store in
  11 ; %loop.2 is not dead at the end of the function.
  12 define void @test.1() {
  13 ; CHECK-LABEL: @test.1(
  14 ; CHECK-NEXT:  entry:
  15 ; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
  16 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
  17 ; CHECK:       loop.1:
  18 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
  19 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_1]]
  20 ; CHECK-NEXT:    store i32 0, ptr [[ARRAYIDX1]], align 4
  21 ; CHECK-NEXT:    [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
  22 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
  23 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
  24 ; CHECK:       loop.2.ph:
  25 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
  26 ; CHECK:       loop.2:
  27 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
  28 ; CHECK-NEXT:    [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_2]]
  29 ; CHECK-NEXT:    [[L_0:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
  30 ; CHECK-NEXT:    call void @use(i32 [[L_0]])
  31 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
  32 ; CHECK-NEXT:    [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[ADD]]
  33 ; CHECK-NEXT:    store i32 10, ptr [[PTR_IV_2_ADD_1]], align 4
  34 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
  35 ; CHECK-NEXT:    call void @use(i32 [[L_1]])
  36 ; CHECK-NEXT:    [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
  37 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
  38 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
  39 ; CHECK:       exit:
  40 ; CHECK-NEXT:    ret void
  41 ;
  42 entry:
  43   %A = alloca [100 x i32], align 4
  44   br label %loop.1
  45
  46 loop.1:
  47   %iv.1 = phi i64 [ 1, %entry ], [ %iv.1.next, %loop.1 ]
  48   %arrayidx1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.1
  49   store i32 0, ptr %arrayidx1, align 4
  50   %iv.1.next = add nsw i64 %iv.1, 1
  51   %c.1 = icmp slt i64 %iv.1.next, 100
  52   br i1 %c.1, label %loop.1, label %loop.2.ph
  53
  54 loop.2.ph:
  55   br label %loop.2
  56
  57 loop.2:
  58   %iv.2 = phi i64 [ %iv.2.next, %loop.2 ], [ 0, %loop.2.ph ]
  59   %ptr.iv.2 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.2
  60   %l.0 = load i32, ptr %ptr.iv.2, align 4
  61   call void @use(i32 %l.0)
  62   %add = add nsw i64 %iv.2, 1
  63   %ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %add
  64   store i32 10, ptr %ptr.iv.2.add.1, align 4
  65   %l.1 = load i32, ptr %ptr.iv.2, align 4
  66   call void @use(i32 %l.1)
  67   %iv.2.next = add nsw i64 %iv.2, 1
  68   %c.2 = icmp slt i64 %iv.2.next, 100
  69   br i1 %c.2, label %loop.2, label %exit
  70
  71 exit:
  72   ret void
  73 }
  74
  75 ; Test cases with a loop carried dependence in %loop.2, where both %l.0 and
  76 ; %l.1 read the value stored by the previous iteration. Hence, the store in
  77 ; %loop.2 is not dead at the end of the function or after the call to lifetime.end().
  78 define void @test.2() {
  79 ; CHECK-LABEL: @test.2(
  80 ; CHECK-NEXT:  entry:
  81 ; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
  82 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
  83 ; CHECK:       loop.1:
  84 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
  85 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_1]]
  86 ; CHECK-NEXT:    store i32 0, ptr [[ARRAYIDX1]], align 4
  87 ; CHECK-NEXT:    [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
  88 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
  89 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
  90 ; CHECK:       loop.2.ph:
  91 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
  92 ; CHECK:       loop.2:
  93 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
  94 ; CHECK-NEXT:    [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV_2]]
  95 ; CHECK-NEXT:    [[L_0:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
  96 ; CHECK-NEXT:    call void @use(i32 [[L_0]])
  97 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
  98 ; CHECK-NEXT:    [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[ADD]]
  99 ; CHECK-NEXT:    store i32 10, ptr [[PTR_IV_2_ADD_1]], align 4
 100 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, ptr [[PTR_IV_2]], align 4
 101 ; CHECK-NEXT:    call void @use(i32 [[L_1]])
 102 ; CHECK-NEXT:    [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
 103 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
 104 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
 105 ; CHECK:       exit:
 106 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 400, ptr nonnull [[A]])
 107 ; CHECK-NEXT:    ret void
 108 ;
 109 entry:
 110   %A = alloca [100 x i32], align 4
 111   br label %loop.1
 112
 113 loop.1:
 114   %iv.1 = phi i64 [ 1, %entry ], [ %iv.1.next, %loop.1 ]
 115   %arrayidx1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.1
 116   store i32 0, ptr %arrayidx1, align 4
 117   %iv.1.next = add nsw i64 %iv.1, 1
 118   %c.1 = icmp slt i64 %iv.1.next, 100
 119   br i1 %c.1, label %loop.1, label %loop.2.ph
 120
 121 loop.2.ph:
 122   br label %loop.2
 123
 124 loop.2:
 125   %iv.2 = phi i64 [ %iv.2.next, %loop.2 ], [ 0, %loop.2.ph ]
 126   %ptr.iv.2 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv.2
 127   %l.0 = load i32, ptr %ptr.iv.2, align 4
 128   call void @use(i32 %l.0)
 129   %add = add nsw i64 %iv.2, 1
 130   %ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %add
 131   store i32 10, ptr %ptr.iv.2.add.1, align 4
 132   %l.1 = load i32, ptr %ptr.iv.2, align 4
 133   call void @use(i32 %l.1)
 134   %iv.2.next = add nsw i64 %iv.2, 1
 135   %c.2 = icmp slt i64 %iv.2.next, 100
 136   br i1 %c.2, label %loop.2, label %exit
 137
 138 exit:
 139   call void @llvm.lifetime.end.p0(i64 400, ptr nonnull %A) #5
 140   ret void
 141 }
 142
 143 declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture)
 144
 145 ; Make sure `store i32 10, ptr %ptr.2` in %cond.store is not removed. The
 146 ; stored value may be read by `%use = load i32, ptr %ptr.1` in a future
 147 ; iteration.
 148 define void@test.3() {
 149 ; CHECK-LABEL: @test.3(
 150 ; CHECK-NEXT:  entry:
 151 ; CHECK-NEXT:    [[NODESTACK:%.*]] = alloca [12 x i32], align 4
 152 ; CHECK-NEXT:    [[C_1:%.*]] = call i1 @cond(i32 1)
 153 ; CHECK-NEXT:    br i1 [[C_1]], label [[CLEANUP:%.*]], label [[LOOP_HEADER:%.*]]
 154 ; CHECK:       loop.header:
 155 ; CHECK-NEXT:    [[DEPTH_1:%.*]] = phi i32 [ [[DEPTH_1_BE:%.*]], [[LOOP_LATCH:%.*]] ], [ 3, [[ENTRY:%.*]] ]
 156 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[DEPTH_1]], 0
 157 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_READ:%.*]], label [[COND_STORE:%.*]]
 158 ; CHECK:       cond.read:
 159 ; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[DEPTH_1]], -3
 160 ; CHECK-NEXT:    [[PTR_1:%.*]] = getelementptr inbounds [12 x i32], ptr [[NODESTACK]], i32 0, i32 [[SUB]]
 161 ; CHECK-NEXT:    [[USE:%.*]] = load i32, ptr [[PTR_1]], align 4
 162 ; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond(i32 [[USE]])
 163 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_LATCH]], label [[COND_STORE]]
 164 ; CHECK:       cond.store:
 165 ; CHECK-NEXT:    [[PTR_2:%.*]] = getelementptr inbounds [12 x i32], ptr [[NODESTACK]], i32 0, i32 [[DEPTH_1]]
 166 ; CHECK-NEXT:    store i32 10, ptr [[PTR_2]], align 4
 167 ; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 [[DEPTH_1]], 1
 168 ; CHECK-NEXT:    [[C_3:%.*]] = call i1 @cond(i32 20)
 169 ; CHECK-NEXT:    br i1 [[C_3]], label [[CLEANUP]], label [[LOOP_LATCH]]
 170 ; CHECK:       loop.latch:
 171 ; CHECK-NEXT:    [[DEPTH_1_BE]] = phi i32 [ [[SUB]], [[COND_READ]] ], [ [[INC]], [[COND_STORE]] ]
 172 ; CHECK-NEXT:    br label [[LOOP_HEADER]]
 173 ; CHECK:       cleanup:
 174 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 48, ptr nonnull [[NODESTACK]])
 175 ; CHECK-NEXT:    ret void
 176 ;
 177 entry:
 178   %nodeStack = alloca [12 x i32], align 4
 179   %c.1 = call i1 @cond(i32 1)
 180   br i1 %c.1, label %cleanup, label %loop.header
 181
 182 loop.header:                                       ; preds = %entry, %while.cond.backedge
 183   %depth.1 = phi i32 [ %depth.1.be, %loop.latch ], [ 3, %entry ]
 184   %cmp = icmp sgt i32 %depth.1, 0
 185   br i1 %cmp, label %cond.read, label %cond.store
 186
 187 cond.read:                                        ; preds = %while.cond
 188   %sub = add nsw i32 %depth.1, -3
 189   %ptr.1 = getelementptr inbounds [12 x i32], ptr %nodeStack, i32 0, i32 %sub
 190   %use = load i32, ptr %ptr.1, align 4
 191   %c.2 = call i1 @cond(i32 %use)
 192   br i1 %c.2, label %loop.latch, label %cond.store
 193
 194 cond.store:
 195   %ptr.2 = getelementptr inbounds [12 x i32], ptr %nodeStack, i32 0, i32 %depth.1
 196   store i32 10, ptr %ptr.2, align 4
 197   %inc = add nsw i32 %depth.1, 1
 198   %c.3 = call i1 @cond(i32 20)
 199   br i1 %c.3, label %cleanup, label %loop.latch
 200
 201 loop.latch:
 202   %depth.1.be = phi i32 [ %sub, %cond.read ], [ %inc, %cond.store ]
 203   br label %loop.header
 204
 205 cleanup:                                          ; preds = %while.body, %while.end, %entry
 206   call void @llvm.lifetime.end.p0(i64 48, ptr nonnull %nodeStack) #3
 207   ret void
 208 }
 209
 210 define void @store_to_invariant_loc() {
 211 ; CHECK-LABEL: @store_to_invariant_loc(
 212 ; CHECK-NEXT:  entry:
 213 ; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
 214 ; CHECK-NEXT:    [[PTR_20:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 20
 215 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 216 ; CHECK:       loop:
 217 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
 218 ; CHECK-NEXT:    [[PTR_IV:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 [[IV]]
 219 ; CHECK-NEXT:    [[L_0:%.*]] = load i32, ptr [[PTR_IV]], align 4
 220 ; CHECK-NEXT:    call void @use(i32 [[L_0]])
 221 ; CHECK-NEXT:    store i32 10, ptr [[PTR_20]], align 4
 222 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i64 [[IV]], 1
 223 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i64 [[IV_NEXT]], 100
 224 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]]
 225 ; CHECK:       exit:
 226 ; CHECK-NEXT:    ret void
 227 ;
 228 entry:
 229   %A = alloca [100 x i32], align 4
 230   %ptr.20 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 20
 231   br label %loop
 232
 233 loop:
 234   %iv = phi i64 [ %iv.next, %loop ], [ 0, %entry ]
 235   %ptr.iv = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv
 236   %l.0 = load i32, ptr %ptr.iv, align 4
 237   call void @use(i32 %l.0)
 238   store i32 10, ptr %ptr.20, align 4
 239   %iv.next = add nsw i64 %iv, 1
 240   %c = icmp slt i64 %iv.next, 100
 241   br i1 %c, label %loop , label %exit
 242
 243 exit:
 244   ret void
 245 }
 246
 247 declare i1 @cond(i32)