248 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2 3; RUN: opt -passes=dse -S %s | FileCheck %s4 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 both %l.0 and10; %l.1 read the value stored by the previous iteration. Hence, the store in11; %loop.2 is not dead at the end of the function.12define void @test.1() {13; CHECK-LABEL: @test.1(14; CHECK-NEXT: entry:15; CHECK-NEXT: [[A:%.*]] = alloca [100 x i32], align 416; 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 421; CHECK-NEXT: [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 122; CHECK-NEXT: [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 10023; 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 430; CHECK-NEXT: call void @use(i32 [[L_0]])31; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[IV_2]], 132; 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 434; CHECK-NEXT: [[L_1:%.*]] = load i32, ptr [[PTR_IV_2]], align 435; CHECK-NEXT: call void @use(i32 [[L_1]])36; CHECK-NEXT: [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 137; CHECK-NEXT: [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 10038; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]39; CHECK: exit:40; CHECK-NEXT: ret void41;42entry:43 %A = alloca [100 x i32], align 444 br label %loop.145 46loop.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.149 store i32 0, ptr %arrayidx1, align 450 %iv.1.next = add nsw i64 %iv.1, 151 %c.1 = icmp slt i64 %iv.1.next, 10052 br i1 %c.1, label %loop.1, label %loop.2.ph53 54loop.2.ph:55 br label %loop.256 57loop.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.260 %l.0 = load i32, ptr %ptr.iv.2, align 461 call void @use(i32 %l.0)62 %add = add nsw i64 %iv.2, 163 %ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %add64 store i32 10, ptr %ptr.iv.2.add.1, align 465 %l.1 = load i32, ptr %ptr.iv.2, align 466 call void @use(i32 %l.1)67 %iv.2.next = add nsw i64 %iv.2, 168 %c.2 = icmp slt i64 %iv.2.next, 10069 br i1 %c.2, label %loop.2, label %exit70 71exit:72 ret void73}74 75; Test cases with a loop carried dependence in %loop.2, where both %l.0 and76; %l.1 read the value stored by the previous iteration. Hence, the store in77; %loop.2 is not dead at the end of the function or after the call to lifetime.end().78define void @test.2() {79; CHECK-LABEL: @test.2(80; CHECK-NEXT: entry:81; CHECK-NEXT: [[A:%.*]] = alloca [100 x i32], align 482; 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 487; CHECK-NEXT: [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 188; CHECK-NEXT: [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 10089; 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 496; CHECK-NEXT: call void @use(i32 [[L_0]])97; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[IV_2]], 198; 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 4100; CHECK-NEXT: [[L_1:%.*]] = load i32, ptr [[PTR_IV_2]], align 4101; CHECK-NEXT: call void @use(i32 [[L_1]])102; CHECK-NEXT: [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1103; CHECK-NEXT: [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100104; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]105; CHECK: exit:106; CHECK-NEXT: call void @llvm.lifetime.end.p0(ptr nonnull [[A]])107; CHECK-NEXT: ret void108;109entry:110 %A = alloca [100 x i32], align 4111 br label %loop.1112 113loop.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.1116 store i32 0, ptr %arrayidx1, align 4117 %iv.1.next = add nsw i64 %iv.1, 1118 %c.1 = icmp slt i64 %iv.1.next, 100119 br i1 %c.1, label %loop.1, label %loop.2.ph120 121loop.2.ph:122 br label %loop.2123 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], ptr %A, i64 0, i64 %iv.2127 %l.0 = load i32, ptr %ptr.iv.2, align 4128 call void @use(i32 %l.0)129 %add = add nsw i64 %iv.2, 1130 %ptr.iv.2.add.1 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %add131 store i32 10, ptr %ptr.iv.2.add.1, align 4132 %l.1 = load i32, ptr %ptr.iv.2, align 4133 call void @use(i32 %l.1)134 %iv.2.next = add nsw i64 %iv.2, 1135 %c.2 = icmp slt i64 %iv.2.next, 100136 br i1 %c.2, label %loop.2, label %exit137 138exit:139 call void @llvm.lifetime.end.p0(ptr nonnull %A) #5140 ret void141}142 143declare void @llvm.lifetime.end.p0(ptr nocapture)144 145; Make sure `store i32 10, ptr %ptr.2` in %cond.store is not removed. The146; stored value may be read by `%use = load i32, ptr %ptr.1` in a future147; iteration.148define void@test.3() {149; CHECK-LABEL: @test.3(150; CHECK-NEXT: entry:151; CHECK-NEXT: [[NODESTACK:%.*]] = alloca [12 x i32], align 4152; 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]], 0157; CHECK-NEXT: br i1 [[CMP]], label [[COND_READ:%.*]], label [[COND_STORE:%.*]]158; CHECK: cond.read:159; CHECK-NEXT: [[SUB:%.*]] = add nsw i32 [[DEPTH_1]], -3160; 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 4162; 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 4167; CHECK-NEXT: [[INC:%.*]] = add nsw i32 [[DEPTH_1]], 1168; 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(ptr nonnull [[NODESTACK]])175; CHECK-NEXT: ret void176;177entry:178 %nodeStack = alloca [12 x i32], align 4179 %c.1 = call i1 @cond(i32 1)180 br i1 %c.1, label %cleanup, label %loop.header181 182loop.header: ; preds = %entry, %while.cond.backedge183 %depth.1 = phi i32 [ %depth.1.be, %loop.latch ], [ 3, %entry ]184 %cmp = icmp sgt i32 %depth.1, 0185 br i1 %cmp, label %cond.read, label %cond.store186 187cond.read: ; preds = %while.cond188 %sub = add nsw i32 %depth.1, -3189 %ptr.1 = getelementptr inbounds [12 x i32], ptr %nodeStack, i32 0, i32 %sub190 %use = load i32, ptr %ptr.1, align 4191 %c.2 = call i1 @cond(i32 %use)192 br i1 %c.2, label %loop.latch, label %cond.store193 194cond.store:195 %ptr.2 = getelementptr inbounds [12 x i32], ptr %nodeStack, i32 0, i32 %depth.1196 store i32 10, ptr %ptr.2, align 4197 %inc = add nsw i32 %depth.1, 1198 %c.3 = call i1 @cond(i32 20)199 br i1 %c.3, label %cleanup, label %loop.latch200 201loop.latch:202 %depth.1.be = phi i32 [ %sub, %cond.read ], [ %inc, %cond.store ]203 br label %loop.header204 205cleanup: ; preds = %while.body, %while.end, %entry206 call void @llvm.lifetime.end.p0(ptr nonnull %nodeStack) #3207 ret void208}209 210define 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 4214; CHECK-NEXT: [[PTR_20:%.*]] = getelementptr inbounds [100 x i32], ptr [[A]], i64 0, i64 20215; 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 4220; CHECK-NEXT: call void @use(i32 [[L_0]])221; CHECK-NEXT: store i32 10, ptr [[PTR_20]], align 4222; CHECK-NEXT: [[IV_NEXT]] = add nsw i64 [[IV]], 1223; CHECK-NEXT: [[C:%.*]] = icmp slt i64 [[IV_NEXT]], 100224; CHECK-NEXT: br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]]225; CHECK: exit:226; CHECK-NEXT: ret void227;228entry:229 %A = alloca [100 x i32], align 4230 %ptr.20 = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 20231 br label %loop232 233loop:234 %iv = phi i64 [ %iv.next, %loop ], [ 0, %entry ]235 %ptr.iv = getelementptr inbounds [100 x i32], ptr %A, i64 0, i64 %iv236 %l.0 = load i32, ptr %ptr.iv, align 4237 call void @use(i32 %l.0)238 store i32 10, ptr %ptr.20, align 4239 %iv.next = add nsw i64 %iv, 1240 %c = icmp slt i64 %iv.next, 100241 br i1 %c, label %loop , label %exit242 243exit:244 ret void245}246 247declare i1 @cond(i32)248