385 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -passes=instcombine -S < %s | FileCheck %s3 4;; This tests that the instructions in the entry blocks are sunk into each5;; arm of the 'if'.6 7define i32 @test1(i1 %C, i32 %A, i32 %B) {8; CHECK-LABEL: @test1(9; CHECK-NEXT: entry:10; CHECK-NEXT: br i1 [[C:%.*]], label [[THEN:%.*]], label [[ENDIF:%.*]]11; CHECK: then:12; CHECK-NEXT: [[TMP_9:%.*]] = add i32 [[B:%.*]], [[A:%.*]]13; CHECK-NEXT: ret i32 [[TMP_9]]14; CHECK: endif:15; CHECK-NEXT: [[TMP_2:%.*]] = sdiv i32 [[A]], [[B]]16; CHECK-NEXT: ret i32 [[TMP_2]]17;18entry:19 %tmp.2 = sdiv i32 %A, %B ; <i32> [#uses=1]20 %tmp.9 = add i32 %B, %A ; <i32> [#uses=1]21 br i1 %C, label %then, label %endif22 23then: ; preds = %entry24 ret i32 %tmp.925 26endif: ; preds = %entry27 ret i32 %tmp.228}29 30; We fail to reach a fixpoint, because sunk instructions get revisited too31; early. In @test2 the sunk add is revisited before the dominating condition32; is visited and added to the DomConditionCache.33 34;; PHI use, sink divide before call.35define i32 @test2(i32 %x) nounwind ssp "instcombine-no-verify-fixpoint" {36; CHECK-LABEL: @test2(37; CHECK-NEXT: entry:38; CHECK-NEXT: br label [[BB:%.*]]39; CHECK: bb:40; CHECK-NEXT: [[X_ADDR_17:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_ADDR_0:%.*]], [[BB2:%.*]] ]41; CHECK-NEXT: [[I_06:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[TMP4:%.*]], [[BB2]] ]42; CHECK-NEXT: [[TMP0:%.*]] = icmp eq i32 [[X_ADDR_17]], 043; CHECK-NEXT: br i1 [[TMP0]], label [[BB1:%.*]], label [[BB2]]44; CHECK: bb1:45; CHECK-NEXT: [[TMP1:%.*]] = add nsw i32 [[X_ADDR_17]], 146; CHECK-NEXT: [[TMP2:%.*]] = sdiv i32 [[TMP1]], [[X_ADDR_17]]47; CHECK-NEXT: [[TMP3:%.*]] = tail call i32 @bar() #[[ATTR3:[0-9]+]]48; CHECK-NEXT: br label [[BB2]]49; CHECK: bb2:50; CHECK-NEXT: [[X_ADDR_0]] = phi i32 [ [[TMP2]], [[BB1]] ], [ [[X_ADDR_17]], [[BB]] ]51; CHECK-NEXT: [[TMP4]] = add nuw nsw i32 [[I_06]], 152; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[TMP4]], 100000053; CHECK-NEXT: br i1 [[EXITCOND]], label [[BB4:%.*]], label [[BB]]54; CHECK: bb4:55; CHECK-NEXT: ret i32 [[X_ADDR_0]]56;57entry:58 br label %bb59 60bb: ; preds = %bb2, %entry61 %x_addr.17 = phi i32 [ %x, %entry ], [ %x_addr.0, %bb2 ] ; <i32> [#uses=4]62 %i.06 = phi i32 [ 0, %entry ], [ %4, %bb2 ] ; <i32> [#uses=1]63 %0 = add nsw i32 %x_addr.17, 1 ; <i32> [#uses=1]64 %1 = sdiv i32 %0, %x_addr.17 ; <i32> [#uses=1]65 %2 = icmp eq i32 %x_addr.17, 0 ; <i1> [#uses=1]66 br i1 %2, label %bb1, label %bb267 68bb1: ; preds = %bb69 %3 = tail call i32 @bar() nounwind ; <i32> [#uses=0]70 br label %bb271 72bb2: ; preds = %bb, %bb173 %x_addr.0 = phi i32 [ %1, %bb1 ], [ %x_addr.17, %bb ] ; <i32> [#uses=2]74 %4 = add nsw i32 %i.06, 1 ; <i32> [#uses=2]75 %exitcond = icmp eq i32 %4, 1000000 ; <i1> [#uses=1]76 br i1 %exitcond, label %bb4, label %bb77 78bb4: ; preds = %bb279 ret i32 %x_addr.080}81 82declare i32 @bar()83 84define i32 @test3(ptr nocapture readonly %P, i32 %i) {85; CHECK-LABEL: @test3(86; CHECK-NEXT: entry:87; CHECK-NEXT: switch i32 [[I:%.*]], label [[SW_EPILOG:%.*]] [88; CHECK-NEXT: i32 5, label [[SW_BB:%.*]]89; CHECK-NEXT: i32 2, label [[SW_BB]]90; CHECK-NEXT: ]91; CHECK: sw.bb:92; CHECK-NEXT: [[IDXPROM:%.*]] = sext i32 [[I]] to i6493; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[IDXPROM]]94; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 495; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[TMP0]], [[I]]96; CHECK-NEXT: br label [[SW_EPILOG]]97; CHECK: sw.epilog:98; CHECK-NEXT: [[SUM_0:%.*]] = phi i32 [ [[ADD]], [[SW_BB]] ], [ 0, [[ENTRY:%.*]] ]99; CHECK-NEXT: ret i32 [[SUM_0]]100;101entry:102 %idxprom = sext i32 %i to i64103 %arrayidx = getelementptr inbounds i32, ptr %P, i64 %idxprom104 %0 = load i32, ptr %arrayidx, align 4105 switch i32 %i, label %sw.epilog [106 i32 5, label %sw.bb107 i32 2, label %sw.bb108 ]109 110sw.bb: ; preds = %entry, %entry111 %add = add nsw i32 %0, %i112 br label %sw.epilog113 114sw.epilog: ; preds = %entry, %sw.bb115 %sum.0 = phi i32 [ %add, %sw.bb ], [ 0, %entry ]116 ret i32 %sum.0117}118 119declare i32 @foo(i32, i32)120; Two uses in a single user. We can still sink the instruction (tmp.9).121define i32 @test4(i32 %A, i32 %B, i1 %C) {122; CHECK-LABEL: @test4(123; CHECK-NEXT: entry:124; CHECK-NEXT: br i1 [[C:%.*]], label [[THEN:%.*]], label [[ENDIF:%.*]]125; CHECK: then:126; CHECK-NEXT: [[TMP_9:%.*]] = add i32 [[B:%.*]], [[A:%.*]]127; CHECK-NEXT: [[RES:%.*]] = call i32 @foo(i32 [[TMP_9]], i32 [[TMP_9]])128; CHECK-NEXT: ret i32 [[RES]]129; CHECK: endif:130; CHECK-NEXT: [[TMP_2:%.*]] = sdiv i32 [[A]], [[B]]131; CHECK-NEXT: ret i32 [[TMP_2]]132;133entry:134 %tmp.2 = sdiv i32 %A, %B ; <i32> [#uses=1]135 %tmp.9 = add i32 %B, %A ; <i32> [#uses=1]136 br i1 %C, label %then, label %endif137 138then: ; preds = %entry139 %res = call i32 @foo(i32 %tmp.9, i32 %tmp.9)140 ret i32 %res141 142endif: ; preds = %entry143 ret i32 %tmp.2144}145 146; Two uses in a single user (phi node). We just bail out.147define i32 @test5(ptr nocapture readonly %P, i32 %i, i1 %cond) {148; CHECK-LABEL: @test5(149; CHECK-NEXT: entry:150; CHECK-NEXT: [[IDXPROM:%.*]] = sext i32 [[I:%.*]] to i64151; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[IDXPROM]]152; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4153; CHECK-NEXT: br i1 [[COND:%.*]], label [[DISPATCHBB:%.*]], label [[SW_EPILOG:%.*]]154; CHECK: dispatchBB:155; CHECK-NEXT: [[ADD:%.*]] = shl nsw i32 [[I]], 1156; CHECK-NEXT: br label [[SW_EPILOG]]157; CHECK: sw.bb:158; CHECK-NEXT: br label [[SW_EPILOG]]159; CHECK: sw.epilog:160; CHECK-NEXT: [[SUM_0:%.*]] = phi i32 [ [[TMP0]], [[SW_BB:%.*]] ], [ [[ADD]], [[DISPATCHBB]] ], [ [[TMP0]], [[ENTRY:%.*]] ]161; CHECK-NEXT: ret i32 [[SUM_0]]162;163entry:164 %idxprom = sext i32 %i to i64165 %arrayidx = getelementptr inbounds i32, ptr %P, i64 %idxprom166 %0 = load i32, ptr %arrayidx, align 4167 br i1 %cond, label %dispatchBB, label %sw.epilog168 169dispatchBB:170 %add = add nsw i32 %i, %i171 br label %sw.epilog172 173sw.bb: ; preds = %entry, %entry174 br label %sw.epilog175 176sw.epilog: ; preds = %entry, %sw.bb177 %sum.0 = phi i32 [ %0, %sw.bb ], [ %add, %dispatchBB ], [ %0, %entry ]178 ret i32 %sum.0179}180 181; Multiple uses but from same BB. We can sink.182define i32 @test6(ptr nocapture readonly %P, i32 %i, i1 %cond) {183; CHECK-LABEL: @test6(184; CHECK-NEXT: entry:185; CHECK-NEXT: [[ADD:%.*]] = shl nsw i32 [[I:%.*]], 1186; CHECK-NEXT: br label [[DISPATCHBB:%.*]]187; CHECK: dispatchBB:188; CHECK-NEXT: [[IDXPROM:%.*]] = sext i32 [[I]] to i64189; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[IDXPROM]]190; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4191; CHECK-NEXT: switch i32 [[I]], label [[SW_BB:%.*]] [192; CHECK-NEXT: i32 5, label [[SW_EPILOG:%.*]]193; CHECK-NEXT: i32 2, label [[SW_EPILOG]]194; CHECK-NEXT: ]195; CHECK: sw.bb:196; CHECK-NEXT: br label [[SW_EPILOG]]197; CHECK: sw.epilog:198; CHECK-NEXT: [[SUM_0:%.*]] = phi i32 [ [[ADD]], [[SW_BB]] ], [ [[TMP0]], [[DISPATCHBB]] ], [ [[TMP0]], [[DISPATCHBB]] ]199; CHECK-NEXT: ret i32 [[SUM_0]]200;201entry:202 %idxprom = sext i32 %i to i64203 %arrayidx = getelementptr inbounds i32, ptr %P, i64 %idxprom204 %0 = load i32, ptr %arrayidx, align 4205 %add = add nsw i32 %i, %i206 br label %dispatchBB207 208dispatchBB:209 switch i32 %i, label %sw.bb [210 i32 5, label %sw.epilog211 i32 2, label %sw.epilog212 ]213 214sw.bb: ; preds = %entry, %entry215 br label %sw.epilog216 217sw.epilog: ; preds = %entry, %sw.bb218 %sum.0 = phi i32 [ %add, %sw.bb ], [ %0, %dispatchBB ], [ %0, %dispatchBB ]219 ret i32 %sum.0220}221 222declare void @checkd(double)223declare double @log(double) willreturn nounwind readnone224define void @test7(i1 %cond, double %d) {225; CHECK-LABEL: @test7(226; CHECK-NEXT: br i1 [[COND:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]227; CHECK: if:228; CHECK-NEXT: [[A:%.*]] = call double @log(double [[D:%.*]])229; CHECK-NEXT: call void @checkd(double [[A]])230; CHECK-NEXT: ret void231; CHECK: else:232; CHECK-NEXT: ret void233;234 %A = call double @log(double %d)235 br i1 %cond, label %if, label %else236 237if:238 call void @checkd(double %A)239 ret void240else:241 ret void242}243 244declare void @abort()245declare { i64, i1 } @llvm.umul.with.overflow.i64(i64, i64)246declare void @dummy(i64)247; Two uses in two different users of a single successor block. We can sink.248define i64 @test8(i64 %c) {249; CHECK-LABEL: @test8(250; CHECK-NEXT: bb1:251; CHECK-NEXT: [[OVERFLOW:%.*]] = icmp ugt i64 [[C:%.*]], 2305843009213693951252; CHECK-NEXT: br i1 [[OVERFLOW]], label [[ABORT:%.*]], label [[BB2:%.*]]253; CHECK: bb2:254; CHECK-NEXT: call void @dummy(i64 8)255; CHECK-NEXT: ret i64 8256; CHECK: abort:257; CHECK-NEXT: call void @abort()258; CHECK-NEXT: unreachable259;260bb1:261 %mul = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %c, i64 8)262 %overflow = extractvalue { i64, i1 } %mul, 1263 %select = select i1 %overflow, i64 0, i64 8264 br i1 %overflow, label %abort, label %bb2265 266bb2:267 call void @dummy(i64 %select)268 ret i64 %select269 270abort:271 call void @abort()272 unreachable273}274 275; Loads marked invariant can be sunk past potential memory writes.276 277define i32 @invariant_load_metadata(ptr %p, i1 %cond) {278; CHECK-LABEL: @invariant_load_metadata(279; CHECK-NEXT: entry:280; CHECK-NEXT: br i1 [[COND:%.*]], label [[BLOCK:%.*]], label [[END:%.*]]281; CHECK: block:282; CHECK-NEXT: call void @fn()283; CHECK-NEXT: br label [[END]]284; CHECK: end:285; CHECK-NEXT: [[V:%.*]] = load i32, ptr [[P:%.*]], align 4, !invariant.load [[META0:![0-9]+]]286; CHECK-NEXT: ret i32 [[V]]287;288entry:289 %v = load i32, ptr %p, !invariant.load !0290 br i1 %cond, label %block, label %end291block:292 call void @fn()293 br label %end294end:295 ret i32 %v296}297 298; Loads not marked invariant cannot be sunk past potential memory writes.299 300define i32 @invariant_load_neg(ptr %p, i1 %cond) {301; CHECK-LABEL: @invariant_load_neg(302; CHECK-NEXT: entry:303; CHECK-NEXT: [[V:%.*]] = load i32, ptr [[P:%.*]], align 4304; CHECK-NEXT: br i1 [[COND:%.*]], label [[BLOCK:%.*]], label [[END:%.*]]305; CHECK: block:306; CHECK-NEXT: call void @fn()307; CHECK-NEXT: br label [[END]]308; CHECK: end:309; CHECK-NEXT: ret i32 [[V]]310;311entry:312 %v = load i32, ptr %p313 br i1 %cond, label %block, label %end314block:315 call void @fn()316 br label %end317end:318 ret i32 %v319}320 321; Loads that aren't marked invariant but used in one branch322; can be sunk to that branch.323 324define void @invariant_load_use_in_br(ptr %p, i1 %cond) {325; CHECK-LABEL: @invariant_load_use_in_br(326; CHECK-NEXT: entry:327; CHECK-NEXT: br i1 [[COND:%.*]], label [[TRUE_BR:%.*]], label [[FALSE_BR:%.*]]328; CHECK: true.br:329; CHECK-NEXT: call void @fn()330; CHECK-NEXT: br label [[EXIT:%.*]]331; CHECK: false.br:332; CHECK-NEXT: [[VAL:%.*]] = load i32, ptr [[P:%.*]], align 4333; CHECK-NEXT: call void @fn(i32 [[VAL]])334; CHECK-NEXT: br label [[EXIT]]335; CHECK: exit:336; CHECK-NEXT: ret void337;338entry:339 %val = load i32, ptr %p340 br i1 %cond, label %true.br, label %false.br341true.br:342 call void @fn()343 br label %exit344false.br:345 call void @fn(i32 %val)346 br label %exit347exit:348 ret void349}350 351; Invariant loads marked with metadata can be sunk past calls.352 353define void @invariant_load_metadata_call(ptr %p, i1 %cond) {354; CHECK-LABEL: @invariant_load_metadata_call(355; CHECK-NEXT: entry:356; CHECK-NEXT: call void @fn()357; CHECK-NEXT: br i1 [[COND:%.*]], label [[TRUE_BR:%.*]], label [[FALSE_BR:%.*]]358; CHECK: true.br:359; CHECK-NEXT: call void @fn()360; CHECK-NEXT: br label [[EXIT:%.*]]361; CHECK: false.br:362; CHECK-NEXT: [[VAL:%.*]] = load i32, ptr [[P:%.*]], align 4, !invariant.load [[META0]]363; CHECK-NEXT: call void @fn(i32 [[VAL]])364; CHECK-NEXT: br label [[EXIT]]365; CHECK: exit:366; CHECK-NEXT: ret void367;368entry:369 %val = load i32, ptr %p, !invariant.load !0370 call void @fn()371 br i1 %cond, label %true.br, label %false.br372true.br:373 call void @fn()374 br label %exit375false.br:376 call void @fn(i32 %val)377 br label %exit378exit:379 ret void380}381 382declare void @fn()383 384!0 = !{}385