Index: lib/Transforms/InstCombine/InstCombineInternal.h =================================================================== --- lib/Transforms/InstCombine/InstCombineInternal.h +++ lib/Transforms/InstCombine/InstCombineInternal.h @@ -757,6 +757,9 @@ /// /// If the multiplication is known not to overflow then NoSignedWrap is set. Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap); + + // Try to sink instruction from its current block to one of its successors. + void tryToSinkInstruction(Instruction *I); }; } // end namespace llvm. Index: lib/Transforms/InstCombine/InstructionCombining.cpp =================================================================== --- lib/Transforms/InstCombine/InstructionCombining.cpp +++ lib/Transforms/InstCombine/InstructionCombining.cpp @@ -2532,6 +2532,7 @@ SmallPtrSet AlreadyCaught; // Typeinfos known caught already. for (unsigned i = 0, e = LI.getNumClauses(); i != e; ++i) { + // bool isLastClause = i + 1 == e; if (LI.isCatch(i)) { // A catch clause. @@ -2830,8 +2831,7 @@ /// beginning of DestBlock, which can only happen if it's safe to move the /// instruction past all of the instructions between it and the end of its /// block. -static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) { - assert(I->hasOneUse() && "Invariants didn't hold!"); +static bool TryToSinkInstructionInto(Instruction *I, BasicBlock *DestBlock) { // Cannot move control-flow-involving, volatile loads, vaarg, etc. if (isa(I) || I->isEHPad() || I->mayHaveSideEffects() || @@ -2868,6 +2868,61 @@ return true; } +void InstCombiner::tryToSinkInstruction(Instruction *I) { + BasicBlock *BB = I->getParent(); + + BasicBlock *DestBlock = nullptr; + + for (auto UI = I->user_begin(), UE = I->user_end(); UI != UE; ++UI) { + Instruction *UserInst = cast(*UI); + + // Get the block the use occurs in. + BasicBlock *UserParent; + if (PHINode *PN = dyn_cast(UserInst)) + UserParent = PN->getIncomingBlock(UI.getUse()); + else + UserParent = UserInst->getParent(); + + // If this User is the current block, there's nothing to do. + if (UserParent == BB) + return; + + if (!DestBlock) { + bool UserIsSuccessor = false; + // See if the user is one of our successors. + for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) + if (*SI == UserParent) { + UserIsSuccessor = true; + break; + } + + // If the user is one of our immediate successors, and if that successor + // only has us as a predecessors (we'd have to split the critical edge + // otherwise), we can keep going. + if (!UserIsSuccessor || !UserParent->getUniquePredecessor()) + return; + + DestBlock = UserParent; + } else if (DestBlock != UserParent) + return; + } + + if (!DestBlock) + return; + + // Okay, the CFG is simple enough, try to sink this instruction. + if (TryToSinkInstructionInto(I, DestBlock)) { + DEBUG(dbgs() << "IC: Sink: " << *I << '\n'); + MadeIRChange = true; + // We'll add uses of the sunk instruction below, but since sinking + // can expose opportunities for it's *operands* add them to the + // worklist + for (Use &U : I->operands()) + if (Instruction *OpI = dyn_cast(U.get())) + Worklist.Add(OpI); + } +} + bool InstCombiner::run() { while (!Worklist.isEmpty()) { Instruction *I = Worklist.RemoveOne(); @@ -2922,44 +2977,7 @@ } // See if we can trivially sink this instruction to a successor basic block. - if (I->hasOneUse()) { - BasicBlock *BB = I->getParent(); - Instruction *UserInst = cast(*I->user_begin()); - BasicBlock *UserParent; - - // Get the block the use occurs in. - if (PHINode *PN = dyn_cast(UserInst)) - UserParent = PN->getIncomingBlock(*I->use_begin()); - else - UserParent = UserInst->getParent(); - - if (UserParent != BB) { - bool UserIsSuccessor = false; - // See if the user is one of our successors. - for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) - if (*SI == UserParent) { - UserIsSuccessor = true; - break; - } - - // If the user is one of our immediate successors, and if that successor - // only has us as a predecessors (we'd have to split the critical edge - // otherwise), we can keep going. - if (UserIsSuccessor && UserParent->getUniquePredecessor()) { - // Okay, the CFG is simple enough, try to sink this instruction. - if (TryToSinkInstruction(I, UserParent)) { - DEBUG(dbgs() << "IC: Sink: " << *I << '\n'); - MadeIRChange = true; - // We'll add uses of the sunk instruction below, but since sinking - // can expose opportunities for it's *operands* add them to the - // worklist - for (Use &U : I->operands()) - if (Instruction *OpI = dyn_cast(U.get())) - Worklist.Add(OpI); - } - } - } - } + tryToSinkInstruction(I); // Now that we have an instruction, try combining it to simplify it. Builder.SetInsertPoint(I); Index: test/Transforms/InstCombine/sink_instruction.ll =================================================================== --- test/Transforms/InstCombine/sink_instruction.ll +++ test/Transforms/InstCombine/sink_instruction.ll @@ -1,3 +1,4 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -instcombine -S < %s | FileCheck %s ;; This tests that the instructions in the entry blocks are sunk into each @@ -77,3 +78,28 @@ %sum.0 = phi i32 [ %add, %sw.bb ], [ 0, %entry ] ret i32 %sum.0 } + +define i32 @test4(i1 %C, i1 %D, i1 %E, i32 %A) { +; CHECK-LABEL: @test4( +; CHECK-NEXT: br i1 [[C:%.*]], label [[THEN:%.*]], label [[ENDIF:%.*]] +; CHECK: then: +; CHECK-NEXT: [[OR1:%.*]] = or i32 [[A:%.*]], 65537 +; CHECK-NEXT: [[SELECT1:%.*]] = select i1 [[D:%.*]], i32 [[OR1]], i32 [[A]] +; CHECK-NEXT: [[OR2:%.*]] = or i32 [[SELECT1]], 131074 +; CHECK-NEXT: [[SELECT2:%.*]] = select i1 [[E:%.*]], i32 [[OR2]], i32 [[SELECT1]] +; CHECK-NEXT: ret i32 [[SELECT2]] +; CHECK: endif: +; CHECK-NEXT: ret i32 [[A]] +; + %or1 = or i32 %A, 65537 + %select1 = select i1 %D, i32 %or1, i32 %A + %or2 = or i32 %select1, 131074 + %select2 = select i1 %E, i32 %or2, i32 %select1 + br i1 %C, label %then, label %endif + +then: + ret i32 %select2 + +endif: + ret i32 %A +}