X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FSimplifyCFG.cpp;h=b9432c2e6e1a638e4455431d5afd421efb203a11;hb=5e6940788fb2f8cf3ce4219d3ac0f78317f54696;hp=12960c946452e4951e214410269d0c117f428c6d;hpb=94c58a0906522bca664ecf7adfd0d88d37bad84d;p=oota-llvm.git diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 12960c94645..b9432c2e6e1 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -19,10 +19,7 @@ #include "llvm/Type.h" #include "llvm/DerivedTypes.h" #include "llvm/GlobalVariable.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Target/TargetData.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/ADT/DenseMap.h" @@ -30,11 +27,20 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/ConstantRange.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include #include #include using namespace llvm; +static cl::opt +DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false), + cl::desc("Duplicate return instructions into unconditional branches")); + STATISTIC(NumSpeculations, "Number of speculative executed instructions"); namespace { @@ -94,8 +100,6 @@ static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { /// ExistPred, an existing predecessor of Succ. static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred) { - assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != - succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); if (!isa(Succ->begin())) return; // Quick exit if nothing to do PHINode *PN; @@ -105,28 +109,29 @@ static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, } -/// GetIfCondition - Given a basic block (BB) with two predecessors (and -/// presumably PHI nodes in it), check to see if the merge at this block is due +/// GetIfCondition - Given a basic block (BB) with two predecessors (and at +/// least one PHI node in it), check to see if the merge at this block is due /// to an "if condition". If so, return the boolean condition that determines /// which entry into BB will be taken. Also, return by references the block /// that will be entered from if the condition is true, and the block that will /// be entered if the condition is false. /// -/// -static Value *GetIfCondition(BasicBlock *BB, - BasicBlock *&IfTrue, BasicBlock *&IfFalse) { - assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && +/// This does no checking to see if the true/false blocks have large or unsavory +/// instructions in them. +static Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, + BasicBlock *&IfFalse) { + PHINode *SomePHI = cast(BB->begin()); + assert(SomePHI->getNumIncomingValues() == 2 && "Function can only handle blocks with 2 predecessors!"); - BasicBlock *Pred1 = *pred_begin(BB); - BasicBlock *Pred2 = *++pred_begin(BB); + BasicBlock *Pred1 = SomePHI->getIncomingBlock(0); + BasicBlock *Pred2 = SomePHI->getIncomingBlock(1); // We can only handle branches. Other control flow will be lowered to // branches if possible anyway. - if (!isa(Pred1->getTerminator()) || - !isa(Pred2->getTerminator())) + BranchInst *Pred1Br = dyn_cast(Pred1->getTerminator()); + BranchInst *Pred2Br = dyn_cast(Pred2->getTerminator()); + if (Pred1Br == 0 || Pred2Br == 0) return 0; - BranchInst *Pred1Br = cast(Pred1->getTerminator()); - BranchInst *Pred2Br = cast(Pred2->getTerminator()); // Eliminate code duplication by ensuring that Pred1Br is conditional if // either are. @@ -143,6 +148,12 @@ static Value *GetIfCondition(BasicBlock *BB, } if (Pred1Br->isConditional()) { + // The only thing we have to watch out for here is to make sure that Pred2 + // doesn't have incoming edges from other blocks. If it does, the condition + // doesn't dominate BB. + if (Pred2->getSinglePredecessor() == 0) + return 0; + // If we found a conditional branch predecessor, make sure that it branches // to BB and Pred2Br. If it doesn't, this isn't an "if statement". if (Pred1Br->getSuccessor(0) == BB && @@ -159,39 +170,29 @@ static Value *GetIfCondition(BasicBlock *BB, return 0; } - // The only thing we have to watch out for here is to make sure that Pred2 - // doesn't have incoming edges from other blocks. If it does, the condition - // doesn't dominate BB. - if (++pred_begin(Pred2) != pred_end(Pred2)) - return 0; - return Pred1Br->getCondition(); } // Ok, if we got here, both predecessors end with an unconditional branch to // BB. Don't panic! If both blocks only have a single (identical) // predecessor, and THAT is a conditional branch, then we're all ok! - if (pred_begin(Pred1) == pred_end(Pred1) || - ++pred_begin(Pred1) != pred_end(Pred1) || - pred_begin(Pred2) == pred_end(Pred2) || - ++pred_begin(Pred2) != pred_end(Pred2) || - *pred_begin(Pred1) != *pred_begin(Pred2)) + BasicBlock *CommonPred = Pred1->getSinglePredecessor(); + if (CommonPred == 0 || CommonPred != Pred2->getSinglePredecessor()) return 0; // Otherwise, if this is a conditional branch, then we can use it! - BasicBlock *CommonPred = *pred_begin(Pred1); - if (BranchInst *BI = dyn_cast(CommonPred->getTerminator())) { - assert(BI->isConditional() && "Two successors but not conditional?"); - if (BI->getSuccessor(0) == Pred1) { - IfTrue = Pred1; - IfFalse = Pred2; - } else { - IfTrue = Pred2; - IfFalse = Pred1; - } - return BI->getCondition(); + BranchInst *BI = dyn_cast(CommonPred->getTerminator()); + if (BI == 0) return 0; + + assert(BI->isConditional() && "Two successors but not conditional?"); + if (BI->getSuccessor(0) == Pred1) { + IfTrue = Pred1; + IfFalse = Pred2; + } else { + IfTrue = Pred2; + IfFalse = Pred1; } - return 0; + return BI->getCondition(); } /// DominatesMergePoint - If we have a merge point of an "if condition" as @@ -204,7 +205,7 @@ static Value *GetIfCondition(BasicBlock *BB, /// non-trapping. If both are true, the instruction is inserted into the set /// and true is returned. static bool DominatesMergePoint(Value *V, BasicBlock *BB, - std::set *AggressiveInsts) { + SmallPtrSet *AggressiveInsts) { Instruction *I = dyn_cast(V); if (!I) { // Non-instructions all dominate instructions, but not all constantexprs @@ -222,50 +223,49 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, // If this instruction is defined in a block that contains an unconditional // branch to BB, then it must be in the 'conditional' part of the "if - // statement". - if (BranchInst *BI = dyn_cast(PBB->getTerminator())) - if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { - if (!AggressiveInsts) return false; - // Okay, it looks like the instruction IS in the "condition". Check to - // see if it's a cheap instruction to unconditionally compute, and if it - // only uses stuff defined outside of the condition. If so, hoist it out. - if (!I->isSafeToSpeculativelyExecute()) - return false; + // statement". If not, it definitely dominates the region. + BranchInst *BI = dyn_cast(PBB->getTerminator()); + if (BI == 0 || BI->isConditional() || BI->getSuccessor(0) != BB) + return true; - switch (I->getOpcode()) { - default: return false; // Cannot hoist this out safely. - case Instruction::Load: { - // We have to check to make sure there are no instructions before the - // load in its basic block, as we are going to hoist the loop out to - // its predecessor. - BasicBlock::iterator IP = PBB->begin(); - while (isa(IP)) - IP++; - if (IP != BasicBlock::iterator(I)) - return false; - break; - } - case Instruction::Add: - case Instruction::Sub: - case Instruction::And: - case Instruction::Or: - case Instruction::Xor: - case Instruction::Shl: - case Instruction::LShr: - case Instruction::AShr: - case Instruction::ICmp: - break; // These are all cheap and non-trapping instructions. - } + // If we aren't allowing aggressive promotion anymore, then don't consider + // instructions in the 'if region'. + if (AggressiveInsts == 0) return false; + + // Okay, it looks like the instruction IS in the "condition". Check to + // see if it's a cheap instruction to unconditionally compute, and if it + // only uses stuff defined outside of the condition. If so, hoist it out. + if (!I->isSafeToSpeculativelyExecute()) + return false; - // Okay, we can only really hoist these out if their operands are not - // defined in the conditional region. - for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) - if (!DominatesMergePoint(*i, BB, 0)) - return false; - // Okay, it's safe to do this! Remember this instruction. - AggressiveInsts->insert(I); - } + switch (I->getOpcode()) { + default: return false; // Cannot hoist this out safely. + case Instruction::Load: + // We have to check to make sure there are no instructions before the + // load in its basic block, as we are going to hoist the load out to its + // predecessor. + if (PBB->getFirstNonPHIOrDbg() != I) + return false; + break; + case Instruction::Add: + case Instruction::Sub: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: + case Instruction::Shl: + case Instruction::LShr: + case Instruction::AShr: + case Instruction::ICmp: + break; // These are all cheap and non-trapping instructions. + } + // Okay, we can only really hoist these out if their operands are not + // defined in the conditional region. + for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) + if (!DominatesMergePoint(*i, BB, 0)) + return false; + // Okay, it's safe to do this! Remember this instruction. + AggressiveInsts->insert(I); return true; } @@ -311,11 +311,32 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, // If this is an icmp against a constant, handle this as one of the cases. if (ICmpInst *ICI = dyn_cast(I)) { - if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) - if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) { + if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) { + if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) { Vals.push_back(C); return I->getOperand(0); } + + // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to + // the set. + ConstantRange Span = + ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue()); + + // If this is an and/!= check then we want to optimize "x ugt 2" into + // x != 0 && x != 1. + if (!isEQ) + Span = Span.inverse(); + + // If there are a ton of values, we don't want to make a ginormous switch. + if (Span.getSetSize().ugt(8) || Span.isEmptySet() || + // We don't handle wrapped sets yet. + Span.isWrappedSet()) + return 0; + + for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp) + Vals.push_back(ConstantInt::get(V->getContext(), Tmp)); + return I->getOperand(0); + } return 0; } @@ -598,7 +619,11 @@ namespace { static int ConstantIntSortPredicate(const void *P1, const void *P2) { const ConstantInt *LHS = *(const ConstantInt**)P1; const ConstantInt *RHS = *(const ConstantInt**)P2; - return LHS->getValue().ult(RHS->getValue()) ? 1 : -1; + if (LHS->getValue().ult(RHS->getValue())) + return 1; + if (LHS->getValue() == RHS->getValue()) + return 0; + return -1; } /// FoldValueComparisonIntoPredecessors - The specified terminator is a value @@ -796,7 +821,7 @@ static bool HoistThenElseCodeToIf(BranchInst *BI) { if (!I2->use_empty()) I2->replaceAllUsesWith(I1); I1->intersectOptionalDataWith(I2); - BB2->getInstList().erase(I2); + I2->eraseFromParent(); I1 = BB1_Itr++; while (isa(I1)) @@ -1050,7 +1075,7 @@ static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { /// that is defined in the same block as the branch and if any PHI entries are /// constants, thread edges corresponding to that entry to be branches to their /// ultimate destination. -static bool FoldCondBranchOnPHI(BranchInst *BI) { +static bool FoldCondBranchOnPHI(BranchInst *BI, const TargetData *TD) { BasicBlock *BB = BI->getParent(); PHINode *PN = dyn_cast(BI->getCondition()); // NOTE: we currently cannot transform this case if the PHI node is used @@ -1088,12 +1113,9 @@ static bool FoldCondBranchOnPHI(BranchInst *BI) { RealDest->getName()+".critedge", RealDest->getParent(), RealDest); BranchInst::Create(RealDest, EdgeBB); - PHINode *PN; - for (BasicBlock::iterator BBI = RealDest->begin(); - (PN = dyn_cast(BBI)); ++BBI) { - Value *V = PN->getIncomingValueForBlock(BB); - PN->addIncoming(V, EdgeBB); - } + + // Update PHI nodes. + AddPredecessorToBlock(RealDest, EdgeBB, BB); // BB may have instructions that are being threaded over. Clone these // instructions into EdgeBB. We know that there will be no uses of the @@ -1118,9 +1140,9 @@ static bool FoldCondBranchOnPHI(BranchInst *BI) { } // Check for trivial simplification. - if (Constant *C = ConstantFoldInstruction(N)) { - TranslateMap[BBI] = C; - delete N; // Constant folded away, don't need actual inst + if (Value *V = SimplifyInstruction(N, TD)) { + TranslateMap[BBI] = V; + delete N; // Instruction folded away, don't need actual inst } else { // Insert the new instruction into its new home. EdgeBB->getInstList().insert(InsertPt, N); @@ -1139,7 +1161,7 @@ static bool FoldCondBranchOnPHI(BranchInst *BI) { } // Recurse, simplifying any other constants. - return FoldCondBranchOnPHI(BI) | true; + return FoldCondBranchOnPHI(BI, TD) | true; } return false; @@ -1147,18 +1169,20 @@ static bool FoldCondBranchOnPHI(BranchInst *BI) { /// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry /// PHI node, see if we can eliminate it. -static bool FoldTwoEntryPHINode(PHINode *PN) { +static bool FoldTwoEntryPHINode(PHINode *PN, const TargetData *TD) { // Ok, this is a two entry PHI node. Check to see if this is a simple "if // statement", which has a very simple dominance structure. Basically, we // are trying to find the condition that is being branched on, which // subsequently causes this merge to happen. We really want control // dependence information for this check, but simplifycfg can't keep it up // to date, and this catches most of the cases we care about anyway. - // BasicBlock *BB = PN->getParent(); BasicBlock *IfTrue, *IfFalse; Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); - if (!IfCond) return false; + if (!IfCond || + // Don't bother if the branch will be constant folded trivially. + isa(IfCond)) + return false; // Okay, we found that we can merge this two-entry phi node into a select. // Doing so would require us to fold *all* two entry phi nodes in this block. @@ -1170,42 +1194,49 @@ static bool FoldTwoEntryPHINode(PHINode *PN) { if (NumPhis > 2) return false; - DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: " - << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); - // Loop over the PHI's seeing if we can promote them all to select // instructions. While we are at it, keep track of the instructions // that need to be moved to the dominating block. - std::set AggressiveInsts; - - BasicBlock::iterator AfterPHIIt = BB->begin(); - while (isa(AfterPHIIt)) { - PHINode *PN = cast(AfterPHIIt++); - if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { - if (PN->getIncomingValue(0) != PN) - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - else - PN->replaceAllUsesWith(UndefValue::get(PN->getType())); - } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, - &AggressiveInsts) || - !DominatesMergePoint(PN->getIncomingValue(1), BB, - &AggressiveInsts)) { - return false; + SmallPtrSet AggressiveInsts; + + for (BasicBlock::iterator II = BB->begin(); isa(II);) { + PHINode *PN = cast(II++); + if (Value *V = SimplifyInstruction(PN, TD)) { + PN->replaceAllUsesWith(V); + PN->eraseFromParent(); + continue; } + + if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts) || + !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts)) + return false; } + // If we folded the the first phi, PN dangles at this point. Refresh it. If + // we ran out of PHIs then we simplified them all. + PN = dyn_cast(BB->begin()); + if (PN == 0) return true; + + // Don't fold i1 branches on PHIs which contain binary operators. These can + // often be turned into switches and other things. + if (PN->getType()->isIntegerTy(1) && + (isa(PN->getIncomingValue(0)) || + isa(PN->getIncomingValue(1)) || + isa(IfCond))) + return false; + // If we all PHI nodes are promotable, check to make sure that all // instructions in the predecessor blocks can be promoted as well. If // not, we won't be able to get rid of the control flow, so it's not // worth promoting to select instructions. - BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; - PN = cast(BB->begin()); - BasicBlock *Pred = PN->getIncomingBlock(0); - if (cast(Pred->getTerminator())->isUnconditional()) { - IfBlock1 = Pred; - DomBlock = *pred_begin(Pred); - for (BasicBlock::iterator I = Pred->begin(); - !isa(I); ++I) + BasicBlock *DomBlock = 0; + BasicBlock *IfBlock1 = PN->getIncomingBlock(0); + BasicBlock *IfBlock2 = PN->getIncomingBlock(1); + if (cast(IfBlock1->getTerminator())->isConditional()) { + IfBlock1 = 0; + } else { + DomBlock = *pred_begin(IfBlock1); + for (BasicBlock::iterator I = IfBlock1->begin();!isa(I);++I) if (!AggressiveInsts.count(I) && !isa(I)) { // This is not an aggressive instruction that we can promote. // Because of this, we won't be able to get rid of the control @@ -1214,12 +1245,11 @@ static bool FoldTwoEntryPHINode(PHINode *PN) { } } - Pred = PN->getIncomingBlock(1); - if (cast(Pred->getTerminator())->isUnconditional()) { - IfBlock2 = Pred; - DomBlock = *pred_begin(Pred); - for (BasicBlock::iterator I = Pred->begin(); - !isa(I); ++I) + if (cast(IfBlock2->getTerminator())->isConditional()) { + IfBlock2 = 0; + } else { + DomBlock = *pred_begin(IfBlock2); + for (BasicBlock::iterator I = IfBlock2->begin();!isa(I);++I) if (!AggressiveInsts.count(I) && !isa(I)) { // This is not an aggressive instruction that we can promote. // Because of this, we won't be able to get rid of the control @@ -1227,18 +1257,22 @@ static bool FoldTwoEntryPHINode(PHINode *PN) { return false; } } + + DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: " + << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); // If we can still promote the PHI nodes after this gauntlet of tests, // do all of the PHI's now. - + Instruction *InsertPt = DomBlock->getTerminator(); + // Move all 'aggressive' instructions, which are defined in the // conditional parts of the if's up to the dominating block. if (IfBlock1) - DomBlock->getInstList().splice(DomBlock->getTerminator(), + DomBlock->getInstList().splice(InsertPt, IfBlock1->getInstList(), IfBlock1->begin(), IfBlock1->getTerminator()); if (IfBlock2) - DomBlock->getInstList().splice(DomBlock->getTerminator(), + DomBlock->getInstList().splice(InsertPt, IfBlock2->getInstList(), IfBlock2->begin(), IfBlock2->getTerminator()); @@ -1247,12 +1281,18 @@ static bool FoldTwoEntryPHINode(PHINode *PN) { Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); - Value *NV = SelectInst::Create(IfCond, TrueVal, FalseVal, "", AfterPHIIt); + Value *NV = SelectInst::Create(IfCond, TrueVal, FalseVal, "", InsertPt); PN->replaceAllUsesWith(NV); NV->takeName(PN); - - BB->getInstList().erase(PN); + PN->eraseFromParent(); } + + // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement + // has been flattened. Change DomBlock to jump directly to our new block to + // avoid other simplifycfg's kicking in on the diamond. + TerminatorInst *OldTI = DomBlock->getTerminator(); + BranchInst::Create(BB, OldTI); + OldTI->eraseFromParent(); return true; } @@ -1515,7 +1555,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { AddPredecessorToBlock(FalseDest, PredBlock, BB); PBI->setSuccessor(1, FalseDest); } - return SimplifyCFG(PBI->getParent()) | true; + return true; } return false; } @@ -1665,17 +1705,13 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { // OtherDest may have phi nodes. If so, add an entry from PBI's // block that are identical to the entries for BI's block. - PHINode *PN; - for (BasicBlock::iterator II = OtherDest->begin(); - (PN = dyn_cast(II)); ++II) { - Value *V = PN->getIncomingValueForBlock(BB); - PN->addIncoming(V, PBI->getParent()); - } + AddPredecessorToBlock(OtherDest, PBI->getParent(), BB); // We know that the CommonDest already had an edge from PBI to // it. If it has PHIs though, the PHIs may have different // entries for BB and PBI's BB. If so, insert a select to make // them agree. + PHINode *PN; for (BasicBlock::iterator II = CommonDest->begin(); (PN = dyn_cast(II)); ++II) { Value *BIV = PN->getIncomingValueForBlock(BB); @@ -1697,22 +1733,13 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { return true; } -// SimplifyIndirectBrOnSelect - Replaces -// (indirectbr (select cond, blockaddress(@fn, BlockA), -// blockaddress(@fn, BlockB))) -// with -// (br cond, BlockA, BlockB). -static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { - // Check that both operands of the select are block addresses. - BlockAddress *TBA = dyn_cast(SI->getTrueValue()); - BlockAddress *FBA = dyn_cast(SI->getFalseValue()); - if (!TBA || !FBA) - return false; - - // Extract the actual blocks. - BasicBlock *TrueBB = TBA->getBasicBlock(); - BasicBlock *FalseBB = FBA->getBasicBlock(); - +// SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a +// branch to TrueBB if Cond is true or to FalseBB if Cond is false. +// Takes care of updating the successors and removing the old terminator. +// Also makes sure not to introduce new successors by assuming that edges to +// non-successor TrueBBs and FalseBBs aren't reachable. +static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, + BasicBlock *TrueBB, BasicBlock *FalseBB){ // Remove any superfluous successor edges from the CFG. // First, figure out which successors to preserve. // If TrueBB and FalseBB are equal, only try to preserve one copy of that @@ -1721,15 +1748,15 @@ static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0; // Then remove the rest. - for (unsigned I = 0, E = IBI->getNumSuccessors(); I != E; ++I) { - BasicBlock *Succ = IBI->getSuccessor(I); + for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) { + BasicBlock *Succ = OldTerm->getSuccessor(I); // Make sure only to keep exactly one copy of each edge. if (Succ == KeepEdge1) KeepEdge1 = 0; else if (Succ == KeepEdge2) KeepEdge2 = 0; else - Succ->removePredecessor(IBI->getParent()); + Succ->removePredecessor(OldTerm->getParent()); } // Insert an appropriate new terminator. @@ -1737,31 +1764,51 @@ static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { if (TrueBB == FalseBB) // We were only looking for one successor, and it was present. // Create an unconditional branch to it. - BranchInst::Create(TrueBB, IBI); + BranchInst::Create(TrueBB, OldTerm); else // We found both of the successors we were looking for. // Create a conditional branch sharing the condition of the select. - BranchInst::Create(TrueBB, FalseBB, SI->getCondition(), IBI); + BranchInst::Create(TrueBB, FalseBB, Cond, OldTerm); } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { // Neither of the selected blocks were successors, so this - // indirectbr must be unreachable. - new UnreachableInst(IBI->getContext(), IBI); + // terminator must be unreachable. + new UnreachableInst(OldTerm->getContext(), OldTerm); } else { // One of the selected values was a successor, but the other wasn't. // Insert an unconditional branch to the one that was found; // the edge to the one that wasn't must be unreachable. if (KeepEdge1 == 0) // Only TrueBB was found. - BranchInst::Create(TrueBB, IBI); + BranchInst::Create(TrueBB, OldTerm); else // Only FalseBB was found. - BranchInst::Create(FalseBB, IBI); + BranchInst::Create(FalseBB, OldTerm); } - EraseTerminatorInstAndDCECond(IBI); + EraseTerminatorInstAndDCECond(OldTerm); return true; } +// SimplifyIndirectBrOnSelect - Replaces +// (indirectbr (select cond, blockaddress(@fn, BlockA), +// blockaddress(@fn, BlockB))) +// with +// (br cond, BlockA, BlockB). +static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { + // Check that both operands of the select are block addresses. + BlockAddress *TBA = dyn_cast(SI->getTrueValue()); + BlockAddress *FBA = dyn_cast(SI->getFalseValue()); + if (!TBA || !FBA) + return false; + + // Extract the actual blocks. + BasicBlock *TrueBB = TBA->getBasicBlock(); + BasicBlock *FalseBB = FBA->getBasicBlock(); + + // Perform the actual simplification. + return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB); +} + /// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp /// instruction (a seteq/setne with a constant) as the only instruction in a /// block that ends with an uncond branch. We are looking for a very specific @@ -1779,7 +1826,8 @@ static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { /// /// We prefer to split the edge to 'end' so that there is a true/false entry to /// the PHI, merging the third icmp into the switch. -static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI) { +static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI, + const TargetData *TD) { BasicBlock *BB = ICI->getParent(); // If the block has any PHIs in it or the icmp has multiple uses, it is too // complex. @@ -1806,8 +1854,8 @@ static bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI) { assert(VVal && "Should have a unique destination value"); ICI->setOperand(0, VVal); - if (Constant *C = ConstantFoldInstruction(ICI)) { - ICI->replaceAllUsesWith(C); + if (Value *V = SimplifyInstruction(ICI, TD)) { + ICI->replaceAllUsesWith(V); ICI->eraseFromParent(); } // BB is now empty, so it is likely to simplify away. @@ -1905,16 +1953,13 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD) { BasicBlock *BB = BI->getParent(); - DEBUG(dbgs() << "CONVERTING 'icmp' CHAIN with " << Values.size() + DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size() << " cases into SWITCH. BB is:\n" << *BB); // If there are any extra values that couldn't be folded into the switch // then we evaluate them with an explicit branch first. Split the block // right before the condbr to handle it. if (ExtraCase) { - DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase - << '\n'); - BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test"); // Remove the uncond branch added to the old block. TerminatorInst *OldTI = BB->getTerminator(); @@ -1928,10 +1973,10 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD) { // If there are PHI nodes in EdgeBB, then we need to add a new entry to them // for the edge we just added. - for (BasicBlock::iterator I = EdgeBB->begin(); isa(I); ++I) { - PHINode *PN = cast(I); - PN->addIncoming(PN->getIncomingValueForBlock(NewBB), BB); - } + AddPredecessorToBlock(EdgeBB, BB, NewBB); + + DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase + << "\nEXTRABB = " << *BB); BB = NewBB; } @@ -1964,6 +2009,7 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD) { // Erase the old branch instruction. EraseTerminatorInstAndDCECond(BI); + DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n'); return true; } @@ -1986,28 +2032,12 @@ bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI) { } // If we found some, do the transformation! - if (!UncondBranchPreds.empty()) { + if (!UncondBranchPreds.empty() && DupRet) { while (!UncondBranchPreds.empty()) { BasicBlock *Pred = UncondBranchPreds.pop_back_val(); DEBUG(dbgs() << "FOLDING: " << *BB << "INTO UNCOND BRANCH PRED: " << *Pred); - Instruction *UncondBranch = Pred->getTerminator(); - // Clone the return and add it to the end of the predecessor. - Instruction *NewRet = RI->clone(); - Pred->getInstList().push_back(NewRet); - - // If the return instruction returns a value, and if the value was a - // PHI node in "BB", propagate the right value into the return. - for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end(); - i != e; ++i) - if (PHINode *PN = dyn_cast(*i)) - if (PN->getParent() == BB) - *i = PN->getIncomingValueForBlock(Pred); - - // Update any PHI nodes in the returning block to realize that we no - // longer branch to them. - BB->removePredecessor(Pred); - Pred->getInstList().erase(UncondBranch); + (void)FoldReturnIntoUncondBranch(RI, BB, Pred); } // If we eliminated all predecessors of the block, delete the block now. @@ -2101,7 +2131,7 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { break; // Delete this instruction - BB->getInstList().erase(BBI); + BBI->eraseFromParent(); Changed = true; } @@ -2286,7 +2316,7 @@ bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI) { if (ICI->isEquality() && isa(ICI->getOperand(1))) { for (++I; isa(I); ++I) ; - if (I->isTerminator() && TryToSimplifyUncondBranchWithICmpInIt(ICI)) + if (I->isTerminator() && TryToSimplifyUncondBranchWithICmpInIt(ICI, TD)) return true; } @@ -2360,14 +2390,14 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI) { // through this block if any PHI node entries are constants. if (PHINode *PN = dyn_cast(BI->getCondition())) if (PN->getParent() == BI->getParent()) - if (FoldCondBranchOnPHI(BI)) + if (FoldCondBranchOnPHI(BI, TD)) return SimplifyCFG(BB) | true; // If this basic block is ONLY a setcc and a branch, and if a predecessor // branches to us and one of our successors, fold the setcc into the // predecessor and use logical operations to pick the right destination. if (FoldBranchToCommonDest(BI)) - return true; + return SimplifyCFG(BB) | true; // Scan predecessor blocks for conditional branches. for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) @@ -2381,14 +2411,14 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI) { bool SimplifyCFGOpt::run(BasicBlock *BB) { bool Changed = false; - Function *Fn = BB->getParent(); - assert(BB && Fn && "Block not embedded in function!"); + assert(BB && BB->getParent() && "Block not embedded in function!"); assert(BB->getTerminator() && "Degenerate basic block encountered!"); // Remove basic blocks that have no predecessors (except the entry block)... // or that just have themself as a predecessor. These are unreachable. - if ((pred_begin(BB) == pred_end(BB) && BB != &Fn->getEntryBlock()) || + if ((pred_begin(BB) == pred_end(BB) && + BB != &BB->getParent()->getEntryBlock()) || BB->getSinglePredecessor() == BB) { DEBUG(dbgs() << "Removing BB: \n" << *BB); DeleteDeadBlock(BB); @@ -2413,7 +2443,7 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { // eliminate it, do so now. if (PHINode *PN = dyn_cast(BB->begin())) if (PN->getNumIncomingValues() == 2) - Changed |= FoldTwoEntryPHINode(PN); + Changed |= FoldTwoEntryPHINode(PN, TD); if (BranchInst *BI = dyn_cast(BB->getTerminator())) { if (BI->isUnconditional()) {