637 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=dse -S | FileCheck %s3 4target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"5 6declare void @use(ptr)7 8; Tests where the pointer/object is accessible after the function returns.9 10define void @accessible_after_return_1(ptr noalias %P, i1 %c1) {11; CHECK-LABEL: @accessible_after_return_1(12; CHECK-NEXT: br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]13; CHECK: bb1:14; CHECK-NEXT: store i32 0, ptr [[P:%.*]], align 415; CHECK-NEXT: br label [[BB5:%.*]]16; CHECK: bb2:17; CHECK-NEXT: store i32 3, ptr [[P]], align 418; CHECK-NEXT: br label [[BB5]]19; CHECK: bb5:20; CHECK-NEXT: call void @use(ptr [[P]])21; CHECK-NEXT: ret void22;23 store i32 1, ptr %P24 br i1 %c1, label %bb1, label %bb225 26bb1:27 store i32 0, ptr %P28 br label %bb529bb2:30 store i32 3, ptr %P31 br label %bb532 33bb5:34 call void @use(ptr %P)35 ret void36}37 38define void @accessible_after_return_2(ptr noalias %P, i1 %c.1, i1 %c.2) {39; CHECK-LABEL: @accessible_after_return_2(40; CHECK-NEXT: br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]41; CHECK: bb1:42; CHECK-NEXT: store i32 0, ptr [[P:%.*]], align 443; CHECK-NEXT: br label [[BB5:%.*]]44; CHECK: bb2:45; CHECK-NEXT: br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]46; CHECK: bb3:47; CHECK-NEXT: store i32 3, ptr [[P]], align 448; CHECK-NEXT: br label [[BB5]]49; CHECK: bb4:50; CHECK-NEXT: store i32 5, ptr [[P]], align 451; CHECK-NEXT: br label [[BB5]]52; CHECK: bb5:53; CHECK-NEXT: call void @use(ptr [[P]])54; CHECK-NEXT: ret void55;56 store i32 1, ptr %P57 br i1 %c.1, label %bb1, label %bb258bb1:59 store i32 0, ptr %P60 br label %bb561 62bb2:63 br i1 %c.2, label %bb3, label %bb464 65bb3:66 store i32 3, ptr %P67 br label %bb568 69bb4:70 store i32 5, ptr %P71 br label %bb572 73bb5:74 call void @use(ptr %P)75 ret void76}77 78; Cannot remove store in entry block because it is not overwritten on path79; entry->bb2->bb5.80define void @accessible_after_return_3(ptr noalias %P, i1 %c1) {81; CHECK-LABEL: @accessible_after_return_3(82; CHECK-NEXT: store i32 1, ptr [[P:%.*]], align 483; CHECK-NEXT: br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]84; CHECK: bb1:85; CHECK-NEXT: store i32 0, ptr [[P]], align 486; CHECK-NEXT: br label [[BB5:%.*]]87; CHECK: bb2:88; CHECK-NEXT: br label [[BB5]]89; CHECK: bb5:90; CHECK-NEXT: call void @use(ptr [[P]])91; CHECK-NEXT: ret void92;93 store i32 1, ptr %P94 br i1 %c1, label %bb1, label %bb295 96bb1:97 store i32 0, ptr %P98 br label %bb599 100bb2:101 br label %bb5102 103bb5:104 call void @use(ptr %P)105 ret void106}107 108; Cannot remove store in entry block because it is not overwritten on path109; entry->bb2->bb5.110define void @accessible_after_return_4(ptr noalias %P, i1 %c1) {111; CHECK-LABEL: @accessible_after_return_4(112; CHECK-NEXT: store i32 1, ptr [[P:%.*]], align 4113; CHECK-NEXT: br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]114; CHECK: bb1:115; CHECK-NEXT: store i32 0, ptr [[P]], align 4116; CHECK-NEXT: call void @use(ptr [[P]])117; CHECK-NEXT: br label [[BB5:%.*]]118; CHECK: bb2:119; CHECK-NEXT: br label [[BB5]]120; CHECK: bb5:121; CHECK-NEXT: ret void122;123 store i32 1, ptr %P124 br i1 %c1, label %bb1, label %bb2125 126bb1:127 store i32 0, ptr %P128 call void @use(ptr %P)129 br label %bb5130 131bb2:132 br label %bb5133 134bb5:135 ret void136}137 138; Cannot remove the store in entry, as it is not overwritten on all paths to an139; exit (patch including bb4).140define void @accessible_after_return5(ptr %P, i1 %c.1, i1 %c.2) {141; CHECK-LABEL: @accessible_after_return5(142; CHECK-NEXT: entry:143; CHECK-NEXT: store i32 0, ptr [[P:%.*]], align 4144; CHECK-NEXT: br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]145; CHECK: bb1:146; CHECK-NEXT: br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]147; CHECK: bb2:148; CHECK-NEXT: store i32 1, ptr [[P]], align 4149; CHECK-NEXT: br label [[BB5:%.*]]150; CHECK: bb3:151; CHECK-NEXT: store i32 2, ptr [[P]], align 4152; CHECK-NEXT: br label [[BB5]]153; CHECK: bb4:154; CHECK-NEXT: br label [[BB5]]155; CHECK: bb5:156; CHECK-NEXT: ret void157;158entry:159 store i32 0, ptr %P160 br i1 %c.1, label %bb1, label %bb2161 162bb1:163 br i1 %c.2, label %bb3, label %bb4164 165bb2:166 store i32 1, ptr %P167 br label %bb5168 169bb3:170 store i32 2, ptr %P171 br label %bb5172 173bb4:174 br label %bb5175 176bb5:177 ret void178}179 180; Can remove store in entry block, because it is overwritten before each return.181define void @accessible_after_return6(ptr %P, i1 %c.1, i1 %c.2) {182; CHECK-LABEL: @accessible_after_return6(183; CHECK-NEXT: entry:184; CHECK-NEXT: br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]185; CHECK: bb1:186; CHECK-NEXT: br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]187; CHECK: bb2:188; CHECK-NEXT: store i32 1, ptr [[P:%.*]], align 4189; CHECK-NEXT: ret void190; CHECK: bb3:191; CHECK-NEXT: store i32 2, ptr [[P]], align 4192; CHECK-NEXT: ret void193; CHECK: bb4:194; CHECK-NEXT: store i32 3, ptr [[P]], align 4195; CHECK-NEXT: ret void196;197entry:198 store i32 0, ptr %P199 br i1 %c.1, label %bb1, label %bb2200 201bb1:202 br i1 %c.2, label %bb3, label %bb4203 204bb2:205 store i32 1, ptr %P206 ret void207 208bb3:209 store i32 2, ptr %P210 ret void211 212bb4:213 store i32 3, ptr %P214 ret void215}216 217; Can remove store in bb1, because it is overwritten along each path218; from bb1 to the exit.219define void @accessible_after_return7(ptr %P, i1 %c.1, i1 %c.2) {220; CHECK-LABEL: @accessible_after_return7(221; CHECK-NEXT: entry:222; CHECK-NEXT: br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]223; CHECK: bb1:224; CHECK-NEXT: br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]225; CHECK: bb3:226; CHECK-NEXT: store i32 2, ptr [[P:%.*]], align 4227; CHECK-NEXT: br label [[BB5:%.*]]228; CHECK: bb4:229; CHECK-NEXT: store i32 1, ptr [[P]], align 4230; CHECK-NEXT: br label [[BB5]]231; CHECK: bb2:232; CHECK-NEXT: br label [[BB5]]233; CHECK: bb5:234; CHECK-NEXT: ret void235;236entry:237 br i1 %c.1, label %bb1, label %bb2238 239bb1:240 store i32 0, ptr %P241 br i1 %c.2, label %bb3, label %bb4242 243bb3:244 store i32 2, ptr %P245 br label %bb5246 247bb4:248 store i32 1, ptr %P249 br label %bb5250 251bb2:252 br label %bb5253 254bb5:255 ret void256}257 258 259; Cannot remove store in entry block, because it is overwritten along each path to260; the exit (entry->bb1->bb4->bb5).261define void @accessible_after_return8(ptr %P, i1 %c.1, i1 %c.2) {262; CHECK-LABEL: @accessible_after_return8(263; CHECK-NEXT: entry:264; CHECK-NEXT: store i32 0, ptr [[P:%.*]], align 4265; CHECK-NEXT: br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]266; CHECK: bb1:267; CHECK-NEXT: br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]268; CHECK: bb2:269; CHECK-NEXT: store i32 1, ptr [[P]], align 4270; CHECK-NEXT: br label [[BB5:%.*]]271; CHECK: bb3:272; CHECK-NEXT: store i32 2, ptr [[P]], align 4273; CHECK-NEXT: br label [[BB5]]274; CHECK: bb4:275; CHECK-NEXT: br label [[BB5]]276; CHECK: bb5:277; CHECK-NEXT: ret void278;279entry:280 store i32 0, ptr %P281 br i1 %c.1, label %bb1, label %bb2282 283bb1:284 br i1 %c.2, label %bb3, label %bb4285 286bb2:287 store i32 1, ptr %P288 br label %bb5289 290bb3:291 store i32 2, ptr %P292 br label %bb5293 294bb4:295 br label %bb5296 297bb5:298 ret void299}300 301; Make sure no stores are removed here. In particular, the store in if.then302; should not be removed.303define void @accessible_after_return9(ptr noalias %ptr) {304; CHECK-LABEL: @accessible_after_return9(305; CHECK-NEXT: entry:306; CHECK-NEXT: [[C_0:%.*]] = call i1 @cond()307; CHECK-NEXT: br i1 [[C_0]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]308; CHECK: for.body:309; CHECK-NEXT: store i8 99, ptr [[PTR:%.*]], align 8310; CHECK-NEXT: [[C_1:%.*]] = call i1 @cond()311; CHECK-NEXT: br i1 [[C_1]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]312; CHECK: if.then:313; CHECK-NEXT: store i8 20, ptr [[PTR]], align 8314; CHECK-NEXT: br label [[IF_END]]315; CHECK: if.end:316; CHECK-NEXT: [[C_2:%.*]] = call i1 @cond()317; CHECK-NEXT: br i1 [[C_2]], label [[IF_THEN10:%.*]], label [[FOR_INC:%.*]]318; CHECK: if.then10:319; CHECK-NEXT: store i8 0, ptr [[PTR]], align 8320; CHECK-NEXT: br label [[FOR_INC]]321; CHECK: for.inc:322; CHECK-NEXT: [[C_3:%.*]] = call i1 @cond()323; CHECK-NEXT: br i1 [[C_3]], label [[FOR_BODY]], label [[FOR_END]]324; CHECK: for.end:325; CHECK-NEXT: ret void326;327entry:328 %c.0 = call i1 @cond()329 br i1 %c.0, label %for.body, label %for.end330 331for.body:332 store i8 99, ptr %ptr, align 8333 %c.1 = call i1 @cond()334 br i1 %c.1, label %if.end, label %if.then335 336if.then:337 store i8 20, ptr %ptr, align 8338 br label %if.end339 340if.end:341 %c.2 = call i1 @cond()342 br i1 %c.2, label %if.then10, label %for.inc343 344if.then10:345 store i8 0, ptr %ptr, align 8346 br label %for.inc347 348for.inc:349 %c.3 = call i1 @cond()350 br i1 %c.3, label %for.body, label %for.end351 352for.end:353 ret void354}355 356; Cannot remove store in entry block because it is not overwritten on path357; entry->bb2->bb4. Also make sure we deal with dead exit blocks without358; crashing.359define void @accessible_after_return10_dead_block(ptr %P, i1 %c.1, i1 %c.2) {360; CHECK-LABEL: @accessible_after_return10_dead_block(361; CHECK-NEXT: entry:362; CHECK-NEXT: store i32 0, ptr [[P:%.*]], align 4363; CHECK-NEXT: br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]364; CHECK: bb1:365; CHECK-NEXT: br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]366; CHECK: bb2:367; CHECK-NEXT: store i32 1, ptr [[P]], align 4368; CHECK-NEXT: ret void369; CHECK: bb3:370; CHECK-NEXT: store i32 2, ptr [[P]], align 4371; CHECK-NEXT: ret void372; CHECK: bb4:373; CHECK-NEXT: ret void374; CHECK: bb5:375; CHECK-NEXT: ret void376;377entry:378 store i32 0, ptr %P379 br i1 %c.1, label %bb1, label %bb2380 381bb1:382 br i1 %c.2, label %bb3, label %bb4383 384bb2:385 store i32 1, ptr %P386 ret void387 388bb3:389 store i32 2, ptr %P390 ret void391 392bb4:393 ret void394 395bb5:396 ret void397}398 399@linenum = external local_unnamed_addr global i32, align 4400 401define void @accessible_after_return11_loop(ptr noalias %p) {402; CHECK-LABEL: @accessible_after_return11_loop(403; CHECK-NEXT: entry:404; CHECK-NEXT: br label [[FOR_BODY_I:%.*]]405; CHECK: for.body.i:406; CHECK-NEXT: [[C_1:%.*]] = call i1 @cond()407; CHECK-NEXT: br i1 [[C_1]], label [[FOR_BODY_I]], label [[INIT_PARSE_EXIT:%.*]]408; CHECK: init_parse.exit:409; CHECK-NEXT: store i32 1, ptr [[P:%.*]], align 4410; CHECK-NEXT: store i32 0, ptr @linenum, align 4411; CHECK-NEXT: br label [[FOR_BODY_I20:%.*]]412; CHECK: for.body.i20:413; CHECK-NEXT: [[C_2:%.*]] = call i1 @cond()414; CHECK-NEXT: br i1 [[C_2]], label [[FOR_BODY_I20]], label [[EXIT:%.*]]415; CHECK: exit:416; CHECK-NEXT: ret void417;418entry:419 br label %for.body.i420 421for.body.i: ; preds = %for.body.i, %entry422 %c.1 = call i1 @cond()423 br i1 %c.1, label %for.body.i, label %init_parse.exit424 425init_parse.exit: ; preds = %for.body.i426 store i32 0, ptr @linenum, align 4427 store i32 1, ptr %p428 store i32 0, ptr @linenum, align 4429 br label %for.body.i20430 431for.body.i20: ; preds = %for.body.i20, %init_parse.exit432 %c.2 = call i1 @cond()433 br i1 %c.2, label %for.body.i20, label %exit434 435exit:436 ret void437}438declare i1 @cond() readnone nounwind439 440; Tests where the pointer/object is *NOT* accessible after the function returns.441 442; The store in the entry block can be eliminated, because it is overwritten443; on all paths to the exit.444define void @alloca_1(i1 %c1) {445; CHECK-LABEL: @alloca_1(446; CHECK-NEXT: [[P:%.*]] = alloca i32, align 4447; CHECK-NEXT: br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]448; CHECK: bb1:449; CHECK-NEXT: store i32 0, ptr [[P]], align 4450; CHECK-NEXT: br label [[BB5:%.*]]451; CHECK: bb2:452; CHECK-NEXT: store i32 3, ptr [[P]], align 4453; CHECK-NEXT: br label [[BB5]]454; CHECK: bb5:455; CHECK-NEXT: call void @use(ptr [[P]])456; CHECK-NEXT: ret void457;458 %P = alloca i32459 store i32 1, ptr %P460 br i1 %c1, label %bb1, label %bb2461 462bb1:463 store i32 0, ptr %P464 br label %bb5465bb2:466 store i32 3, ptr %P467 br label %bb5468 469bb5:470 call void @use(ptr %P)471 ret void472}473 474; The store in the entry block can be eliminated, because it is overwritten475; on all paths to the exit.476define void @alloca_2(i1 %c.1, i1 %c.2) {477; CHECK-LABEL: @alloca_2(478; CHECK-NEXT: [[P:%.*]] = alloca i32, align 4479; CHECK-NEXT: br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]480; CHECK: bb1:481; CHECK-NEXT: store i32 0, ptr [[P]], align 4482; CHECK-NEXT: br label [[BB5:%.*]]483; CHECK: bb2:484; CHECK-NEXT: br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]485; CHECK: bb3:486; CHECK-NEXT: store i32 3, ptr [[P]], align 4487; CHECK-NEXT: br label [[BB5]]488; CHECK: bb4:489; CHECK-NEXT: store i32 5, ptr [[P]], align 4490; CHECK-NEXT: br label [[BB5]]491; CHECK: bb5:492; CHECK-NEXT: call void @use(ptr [[P]])493; CHECK-NEXT: ret void494;495 %P = alloca i32496 store i32 1, ptr %P497 br i1 %c.1, label %bb1, label %bb2498 499bb1:500 store i32 0, ptr %P501 br label %bb5502 503bb2:504 br i1 %c.2, label %bb3, label %bb4505 506bb3:507 store i32 3, ptr %P508 br label %bb5509 510bb4:511 store i32 5, ptr %P512 br label %bb5513 514bb5:515 call void @use(ptr %P)516 ret void517}518 519; The store in the entry block cannot be eliminated. There's a path from the520; first store to the read in bb5, where the location is not overwritten.521define void @alloca_3(i1 %c1) {522; CHECK-LABEL: @alloca_3(523; CHECK-NEXT: [[P:%.*]] = alloca i32, align 4524; CHECK-NEXT: store i32 1, ptr [[P]], align 4525; CHECK-NEXT: br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]526; CHECK: bb1:527; CHECK-NEXT: store i32 0, ptr [[P]], align 4528; CHECK-NEXT: br label [[BB5:%.*]]529; CHECK: bb2:530; CHECK-NEXT: br label [[BB5]]531; CHECK: bb5:532; CHECK-NEXT: call void @use(ptr [[P]])533; CHECK-NEXT: ret void534;535 %P = alloca i32536 store i32 1, ptr %P537 br i1 %c1, label %bb1, label %bb2538 539bb1:540 store i32 0, ptr %P541 br label %bb5542bb2:543 br label %bb5544 545bb5:546 call void @use(ptr %P)547 ret void548}549 550; The store in the entry block can be eliminated, because it is overwritten551; before the use in bb1 and not read on other paths to the function exit. The552; object cannot be accessed by the caller.553define void @alloca_4(i1 %c1) {554; CHECK-LABEL: @alloca_4(555; CHECK-NEXT: [[P:%.*]] = alloca i32, align 4556; CHECK-NEXT: br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]557; CHECK: bb1:558; CHECK-NEXT: store i32 0, ptr [[P]], align 4559; CHECK-NEXT: call void @use(ptr [[P]])560; CHECK-NEXT: br label [[BB5:%.*]]561; CHECK: bb2:562; CHECK-NEXT: br label [[BB5]]563; CHECK: bb5:564; CHECK-NEXT: ret void565;566 %P = alloca i32567 store i32 1, ptr %P568 br i1 %c1, label %bb1, label %bb2569 570bb1:571 store i32 0, ptr %P572 call void @use(ptr %P)573 br label %bb5574 575bb2:576 br label %bb5577 578bb5:579 ret void580}581 582%struct.blam.4 = type { %struct.bar.5, [4 x i8] }583%struct.bar.5 = type <{ i64, ptr, i32, i64 }>584 585; Make sure we do not eliminate the store in %bb.586define void @alloca_5(i1 %c) {587; CHECK-LABEL: @alloca_5(588; CHECK-NEXT: bb:589; CHECK-NEXT: [[TMP:%.*]] = alloca [[STRUCT_BLAM_4:%.*]], align 8590; CHECK-NEXT: [[TMP38:%.*]] = getelementptr inbounds [[STRUCT_BLAM_4]], ptr [[TMP]], i64 0, i32 0, i32 3591; CHECK-NEXT: store i64 0, ptr [[TMP38]], align 4592; CHECK-NEXT: br i1 [[C:%.*]], label [[BB46:%.*]], label [[BB47:%.*]]593; CHECK: bb46:594; CHECK-NEXT: ret void595; CHECK: bb47:596; CHECK-NEXT: [[TMP48:%.*]] = getelementptr inbounds [[STRUCT_BLAM_4]], ptr [[TMP]], i64 0, i32 0, i32 2597; CHECK-NEXT: store i32 20, ptr [[TMP48]], align 8598; CHECK-NEXT: br label [[BB52:%.*]]599; CHECK: bb52:600; CHECK-NEXT: br i1 [[C]], label [[BB68:%.*]], label [[BB59:%.*]]601; CHECK: bb59:602; CHECK-NEXT: call void @use.2(ptr [[TMP]])603; CHECK-NEXT: ret void604; CHECK: bb68:605; CHECK-NEXT: ret void606;607bb:608 %tmp = alloca %struct.blam.4, align 8609 %tmp36 = getelementptr inbounds %struct.blam.4, ptr %tmp, i64 0, i32 0, i32 1610 %tmp38 = getelementptr inbounds %struct.blam.4, ptr %tmp, i64 0, i32 0, i32 3611 store i64 0, ptr %tmp38, align 4612 br i1 %c, label %bb46, label %bb47613 614bb46: ; preds = %bb12615 call void @llvm.memset.p0.i64(ptr nonnull align 8 dereferenceable(20) %tmp36, i8 0, i64 26, i1 false)616 ret void617 618bb47: ; preds = %bb12619 %tmp48 = getelementptr inbounds %struct.blam.4, ptr %tmp, i64 0, i32 0, i32 2620 store i32 20, ptr %tmp48, align 8621 br label %bb52622 623bb52: ; preds = %bb47624 br i1 %c, label %bb68, label %bb59625 626bb59: ; preds = %bb52627 call void @use.2(ptr %tmp)628 ret void629 630bb68: ; preds = %bb52631 ret void632}633 634declare void @use.2(ptr)635 636declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg)637