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 -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 %l.2 reads the
  10 ; value stored by the previous iteration. Hence, the store in %loop.2 is not
  11 ; dead at the end of the function or after the call to lifetime.end().
  12
  13 define void @test.1() {
  14 ; CHECK-LABEL: @test.1(
  15 ; CHECK-NEXT:  entry:
  16 ; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
  17 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
  18 ; CHECK:       loop.1:
  19 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
  20 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_1]]
  21 ; CHECK-NEXT:    store i32 0, i32* [[ARRAYIDX1]], align 4
  22 ; CHECK-NEXT:    [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
  23 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
  24 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
  25 ; CHECK:       loop.2.ph:
  26 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
  27 ; CHECK:       loop.2:
  28 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
  29 ; CHECK-NEXT:    [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_2]]
  30 ; CHECK-NEXT:    [[L_0:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
  31 ; CHECK-NEXT:    call void @use(i32 [[L_0]])
  32 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
  33 ; CHECK-NEXT:    [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[ADD]]
  34 ; CHECK-NEXT:    store i32 10, i32* [[PTR_IV_2_ADD_1]], align 4
  35 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
  36 ; CHECK-NEXT:    call void @use(i32 [[L_1]])
  37 ; CHECK-NEXT:    [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
  38 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
  39 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
  40 ; CHECK:       exit:
  41 ; CHECK-NEXT:    ret void
  42 ;
  43 entry:
  44   %A = alloca [100 x i32], align 4
  45   br label %loop.1
  46
  47 loop.1:
  48   %iv.1 = phi i64 [ 1, %entry ], [ %iv.1.next, %loop.1 ]
  49   %arrayidx1 = getelementptr inbounds [100 x i32], [100 x i32]* %A, i64 0, i64 %iv.1
  50   store i32 0, i32* %arrayidx1, align 4
  51   %iv.1.next = add nsw i64 %iv.1, 1
  52   %c.1 = icmp slt i64 %iv.1.next, 100
  53   br i1 %c.1, label %loop.1, label %loop.2.ph
  54
  55 loop.2.ph:
  56   br label %loop.2
  57
  58 loop.2:
  59   %iv.2 = phi i64 [ %iv.2.next, %loop.2 ], [ 0, %loop.2.ph ]
  60   %ptr.iv.2 = getelementptr inbounds [100 x i32], [100 x i32]* %A, i64 0, i64 %iv.2
  61   %l.0 = load i32, i32* %ptr.iv.2, align 4
  62   call void @use(i32 %l.0)
  63   %add = add nsw i64 %iv.2, 1
  64   %ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], [100 x i32]* %A, i64 0, i64 %add
  65   store i32 10, i32* %ptr.iv.2.add.1, align 4
  66   %l.1 = load i32, i32* %ptr.iv.2, align 4
  67   call void @use(i32 %l.1)
  68   %iv.2.next = add nsw i64 %iv.2, 1
  69   %c.2 = icmp slt i64 %iv.2.next, 100
  70   br i1 %c.2, label %loop.2, label %exit
  71
  72 exit:
  73   ret void
  74 }
  75
  76 define void @test.2() {
  77 ; CHECK-LABEL: @test.2(
  78 ; CHECK-NEXT:  entry:
  79 ; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
  80 ; CHECK-NEXT:    [[A_CAST:%.*]] = bitcast [100 x i32]* [[A]] to i8*
  81 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
  82 ; CHECK:       loop.1:
  83 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
  84 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_1]]
  85 ; CHECK-NEXT:    store i32 0, i32* [[ARRAYIDX1]], align 4
  86 ; CHECK-NEXT:    [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
  87 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
  88 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
  89 ; CHECK:       loop.2.ph:
  90 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
  91 ; CHECK:       loop.2:
  92 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
  93 ; CHECK-NEXT:    [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_2]]
  94 ; CHECK-NEXT:    [[L_0:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
  95 ; CHECK-NEXT:    call void @use(i32 [[L_0]])
  96 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
  97 ; CHECK-NEXT:    [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[ADD]]
  98 ; CHECK-NEXT:    store i32 10, i32* [[PTR_IV_2_ADD_1]], align 4
  99 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
 100 ; CHECK-NEXT:    call void @use(i32 [[L_1]])
 101 ; CHECK-NEXT:    [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
 102 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
 103 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
 104 ; CHECK:       exit:
 105 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 400, i8* nonnull [[A_CAST]])
 106 ; CHECK-NEXT:    ret void
 107 ;
 108 entry:
 109   %A = alloca [100 x i32], align 4
 110   %A.cast = bitcast [100 x i32]* %A to i8*
 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], [100 x i32]* %A, i64 0, i64 %iv.1
 116   store i32 0, i32* %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], [100 x i32]* %A, i64 0, i64 %iv.2
 127   %l.0 = load i32, i32* %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], [100 x i32]* %A, i64 0, i64 %add
 131   store i32 10, i32* %ptr.iv.2.add.1, align 4
 132   %l.1 = load i32, i32* %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.p0i8(i64 400, i8* nonnull %A.cast) #5
 140   ret void
 141 }
 142
 143 declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture)
 144
 145 ; Make sure `store i32 10, i32* %ptr.2` in %cond.store is not removed. The
 146 ; stored value may be read by `%use = load i32, i32* %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:    [[NODESTACK_CAST:%.*]] = bitcast [12 x i32]* [[NODESTACK]] to i8*
 153 ; CHECK-NEXT:    [[C_1:%.*]] = call i1 @cond(i32 1)
 154 ; CHECK-NEXT:    br i1 [[C_1]], label [[CLEANUP:%.*]], label [[LOOP_HEADER:%.*]]
 155 ; CHECK:       loop.header:
 156 ; CHECK-NEXT:    [[DEPTH_1:%.*]] = phi i32 [ [[DEPTH_1_BE:%.*]], [[LOOP_LATCH:%.*]] ], [ 3, [[ENTRY:%.*]] ]
 157 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[DEPTH_1]], 0
 158 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_READ:%.*]], label [[COND_STORE:%.*]]
 159 ; CHECK:       cond.read:
 160 ; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[DEPTH_1]], -3
 161 ; CHECK-NEXT:    [[PTR_1:%.*]] = getelementptr inbounds [12 x i32], [12 x i32]* [[NODESTACK]], i32 0, i32 [[SUB]]
 162 ; CHECK-NEXT:    [[USE:%.*]] = load i32, i32* [[PTR_1]], align 4
 163 ; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond(i32 [[USE]])
 164 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_LATCH]], label [[COND_STORE]]
 165 ; CHECK:       cond.store:
 166 ; CHECK-NEXT:    [[PTR_2:%.*]] = getelementptr inbounds [12 x i32], [12 x i32]* [[NODESTACK]], i32 0, i32 [[DEPTH_1]]
 167 ; CHECK-NEXT:    store i32 10, i32* [[PTR_2]], align 4
 168 ; CHECK-NEXT:    [[INC:%.*]] = add nsw i32 [[DEPTH_1]], 1
 169 ; CHECK-NEXT:    [[C_3:%.*]] = call i1 @cond(i32 20)
 170 ; CHECK-NEXT:    br i1 [[C_3]], label [[CLEANUP]], label [[LOOP_LATCH]]
 171 ; CHECK:       loop.latch:
 172 ; CHECK-NEXT:    [[DEPTH_1_BE]] = phi i32 [ [[SUB]], [[COND_READ]] ], [ [[INC]], [[COND_STORE]] ]
 173 ; CHECK-NEXT:    br label [[LOOP_HEADER]]
 174 ; CHECK:       cleanup:
 175 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 48, i8* nonnull [[NODESTACK_CAST]])
 176 ; CHECK-NEXT:    ret void
 177 ;
 178 entry:
 179   %nodeStack = alloca [12 x i32], align 4
 180   %nodeStack.cast = bitcast [12 x i32]* %nodeStack to i8*
 181   %c.1 = call i1 @cond(i32 1)
 182   br i1 %c.1, label %cleanup, label %loop.header
 183
 184 loop.header:                                       ; preds = %entry, %while.cond.backedge
 185   %depth.1 = phi i32 [ %depth.1.be, %loop.latch ], [ 3, %entry ]
 186   %cmp = icmp sgt i32 %depth.1, 0
 187   br i1 %cmp, label %cond.read, label %cond.store
 188
 189 cond.read:                                        ; preds = %while.cond
 190   %sub = add nsw i32 %depth.1, -3
 191   %ptr.1 = getelementptr inbounds [12 x i32], [12 x i32]* %nodeStack, i32 0, i32 %sub
 192   %use = load i32, i32* %ptr.1, align 4
 193   %c.2 = call i1 @cond(i32 %use)
 194   br i1 %c.2, label %loop.latch, label %cond.store
 195
 196 cond.store:
 197   %ptr.2 = getelementptr inbounds [12 x i32], [12 x i32]* %nodeStack, i32 0, i32 %depth.1
 198   store i32 10, i32* %ptr.2, align 4
 199   %inc = add nsw i32 %depth.1, 1
 200   %c.3 = call i1 @cond(i32 20)
 201   br i1 %c.3, label %cleanup, label %loop.latch
 202
 203 loop.latch:
 204   %depth.1.be = phi i32 [ %sub, %cond.read ], [ %inc, %cond.store ]
 205   br label %loop.header
 206
 207 cleanup:                                          ; preds = %while.body, %while.end, %entry
 208   call void @llvm.lifetime.end.p0i8(i64 48, i8* nonnull %nodeStack.cast) #3
 209   ret void
 210 }
 211
 212 declare i1 @cond(i32)