1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2 3; RUN: opt -dse -enable-dse-memoryssa -S %s | FileCheck %s 4 5target datalayout = "e-m:e-i64:64-n32:64-v256:256:256-v512:512:512" 6 7declare 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 13define 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; 43entry: 44 %A = alloca [100 x i32], align 4 45 br label %loop.1 46 47loop.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 55loop.2.ph: 56 br label %loop.2 57 58loop.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 72exit: 73 ret void 74} 75 76define 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; 108entry: 109 %A = alloca [100 x i32], align 4 110 %A.cast = bitcast [100 x i32]* %A to i8* 111 br label %loop.1 112 113loop.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 121loop.2.ph: 122 br label %loop.2 123 124loop.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 138exit: 139 call void @llvm.lifetime.end.p0i8(i64 400, i8* nonnull %A.cast) #5 140 ret void 141} 142 143declare 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. 148define 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; 178entry: 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 184loop.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 189cond.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 196cond.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 203loop.latch: 204 %depth.1.be = phi i32 [ %sub, %cond.read ], [ %inc, %cond.store ] 205 br label %loop.header 206 207cleanup: ; 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 212declare i1 @cond(i32) 213