X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FSimplifyCFG.cpp;h=b9432c2e6e1a638e4455431d5afd421efb203a11;hb=5e6940788fb2f8cf3ce4219d3ac0f78317f54696;hp=a8a9e306f379b4e8ddc498254872b6a928e0656f;hpb=7b550ccfc5a3346c17e0390a59e2d6d19bc52705;p=oota-llvm.git diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index a8a9e306f37..b9432c2e6e1 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -19,23 +19,55 @@ #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" #include "llvm/ADT/SmallVector.h" #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 #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 { +class SimplifyCFGOpt { + const TargetData *const TD; + + Value *isValueEqualityComparison(TerminatorInst *TI); + BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, + std::vector > &Cases); + bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, + BasicBlock *Pred); + bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI); + + bool SimplifyReturn(ReturnInst *RI); + bool SimplifyUnwind(UnwindInst *UI); + bool SimplifyUnreachable(UnreachableInst *UI); + bool SimplifySwitch(SwitchInst *SI); + bool SimplifyIndirectBr(IndirectBrInst *IBI); + bool SimplifyUncondBranch(BranchInst *BI); + bool SimplifyCondBranch(BranchInst *BI); + +public: + explicit SimplifyCFGOpt(const TargetData *td) : TD(td) {} + bool run(BasicBlock *BB); +}; +} + /// SafeToMergeTerminators - Return true if it is safe to merge these two /// terminator instructions together. /// @@ -68,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; @@ -78,189 +108,30 @@ static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); } -/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an -/// almost-empty BB ending in an unconditional branch to Succ, into succ. -/// -/// Assumption: Succ is the single successor for BB. -/// -static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { - assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); - - DEBUG(errs() << "Looking to fold " << BB->getName() << " into " - << Succ->getName() << "\n"); - // Shortcut, if there is only a single predecessor it must be BB and merging - // is always safe - if (Succ->getSinglePredecessor()) return true; - - // Make a list of the predecessors of BB - typedef SmallPtrSet BlockSet; - BlockSet BBPreds(pred_begin(BB), pred_end(BB)); - - // Use that list to make another list of common predecessors of BB and Succ - BlockSet CommonPreds; - for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); - PI != PE; ++PI) - if (BBPreds.count(*PI)) - CommonPreds.insert(*PI); - - // Shortcut, if there are no common predecessors, merging is always safe - if (CommonPreds.empty()) - return true; - - // Look at all the phi nodes in Succ, to see if they present a conflict when - // merging these blocks - for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { - PHINode *PN = cast(I); - - // If the incoming value from BB is again a PHINode in - // BB which has the same incoming value for *PI as PN does, we can - // merge the phi nodes and then the blocks can still be merged - PHINode *BBPN = dyn_cast(PN->getIncomingValueForBlock(BB)); - if (BBPN && BBPN->getParent() == BB) { - for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); - PI != PE; PI++) { - if (BBPN->getIncomingValueForBlock(*PI) - != PN->getIncomingValueForBlock(*PI)) { - DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " - << Succ->getName() << " is conflicting with " - << BBPN->getName() << " with regard to common predecessor " - << (*PI)->getName() << "\n"); - return false; - } - } - } else { - Value* Val = PN->getIncomingValueForBlock(BB); - for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); - PI != PE; PI++) { - // See if the incoming value for the common predecessor is equal to the - // one for BB, in which case this phi node will not prevent the merging - // of the block. - if (Val != PN->getIncomingValueForBlock(*PI)) { - DEBUG(errs() << "Can't fold, phi node " << PN->getName() << " in " - << Succ->getName() << " is conflicting with regard to common " - << "predecessor " << (*PI)->getName() << "\n"); - return false; - } - } - } - } - - return true; -} - -/// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional -/// branch to Succ, and contains no instructions other than PHI nodes and the -/// branch. If possible, eliminate BB. -static bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, - BasicBlock *Succ) { - // Check to see if merging these blocks would cause conflicts for any of the - // phi nodes in BB or Succ. If not, we can safely merge. - if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; - - // Check for cases where Succ has multiple predecessors and a PHI node in BB - // has uses which will not disappear when the PHI nodes are merged. It is - // possible to handle such cases, but difficult: it requires checking whether - // BB dominates Succ, which is non-trivial to calculate in the case where - // Succ has multiple predecessors. Also, it requires checking whether - // constructing the necessary self-referential PHI node doesn't intoduce any - // conflicts; this isn't too difficult, but the previous code for doing this - // was incorrect. - // - // Note that if this check finds a live use, BB dominates Succ, so BB is - // something like a loop pre-header (or rarely, a part of an irreducible CFG); - // folding the branch isn't profitable in that case anyway. - if (!Succ->getSinglePredecessor()) { - BasicBlock::iterator BBI = BB->begin(); - while (isa(*BBI)) { - for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); - UI != E; ++UI) { - if (PHINode* PN = dyn_cast(*UI)) { - if (PN->getIncomingBlock(UI) != BB) - return false; - } else { - return false; - } - } - ++BBI; - } - } - - DEBUG(errs() << "Killing Trivial BB: \n" << *BB); - - if (isa(Succ->begin())) { - // If there is more than one pred of succ, and there are PHI nodes in - // the successor, then we need to add incoming edges for the PHI nodes - // - const SmallVector BBPreds(pred_begin(BB), pred_end(BB)); - - // Loop over all of the PHI nodes in the successor of BB. - for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { - PHINode *PN = cast(I); - Value *OldVal = PN->removeIncomingValue(BB, false); - assert(OldVal && "No entry in PHI for Pred BB!"); - - // If this incoming value is one of the PHI nodes in BB, the new entries - // in the PHI node are the entries from the old PHI. - if (isa(OldVal) && cast(OldVal)->getParent() == BB) { - PHINode *OldValPN = cast(OldVal); - for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) - // Note that, since we are merging phi nodes and BB and Succ might - // have common predecessors, we could end up with a phi node with - // identical incoming branches. This will be cleaned up later (and - // will trigger asserts if we try to clean it up now, without also - // simplifying the corresponding conditional branch). - PN->addIncoming(OldValPN->getIncomingValue(i), - OldValPN->getIncomingBlock(i)); - } else { - // Add an incoming value for each of the new incoming values. - for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) - PN->addIncoming(OldVal, BBPreds[i]); - } - } - } - - while (PHINode *PN = dyn_cast(&BB->front())) { - if (Succ->getSinglePredecessor()) { - // BB is the only predecessor of Succ, so Succ will end up with exactly - // the same predecessors BB had. - Succ->getInstList().splice(Succ->begin(), - BB->getInstList(), BB->begin()); - } else { - // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. - assert(PN->use_empty() && "There shouldn't be any uses here!"); - PN->eraseFromParent(); - } - } - - // Everything that jumped to BB now goes to Succ. - BB->replaceAllUsesWith(Succ); - if (!Succ->hasName()) Succ->takeName(BB); - BB->eraseFromParent(); // Delete the old basic block. - return true; -} -/// 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. @@ -277,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 && @@ -293,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 @@ -338,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 @@ -356,122 +223,164 @@ 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 its 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; } -/// GatherConstantSetEQs - Given a potentially 'or'd together collection of -/// icmp_eq instructions that compare a value against a constant, return the -/// value being compared, and stick the constant into the Values vector. -static Value *GatherConstantSetEQs(Value *V, std::vector &Values){ - if (Instruction *Inst = dyn_cast(V)) { - if (Inst->getOpcode() == Instruction::ICmp && - cast(Inst)->getPredicate() == ICmpInst::ICMP_EQ) { - if (ConstantInt *C = dyn_cast(Inst->getOperand(1))) { - Values.push_back(C); - return Inst->getOperand(0); - } else if (ConstantInt *C = dyn_cast(Inst->getOperand(0))) { - Values.push_back(C); - return Inst->getOperand(1); +/// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr +/// and PointerNullValue. Return NULL if value is not a constant int. +static ConstantInt *GetConstantInt(Value *V, const TargetData *TD) { + // Normal constant int. + ConstantInt *CI = dyn_cast(V); + if (CI || !TD || !isa(V) || !V->getType()->isPointerTy()) + return CI; + + // This is some kind of pointer constant. Turn it into a pointer-sized + // ConstantInt if possible. + const IntegerType *PtrTy = TD->getIntPtrType(V->getContext()); + + // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). + if (isa(V)) + return ConstantInt::get(PtrTy, 0); + + // IntToPtr const int. + if (ConstantExpr *CE = dyn_cast(V)) + if (CE->getOpcode() == Instruction::IntToPtr) + if (ConstantInt *CI = dyn_cast(CE->getOperand(0))) { + // The constant is very likely to have the right type already. + if (CI->getType() == PtrTy) + return CI; + else + return cast + (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); } - } else if (Inst->getOpcode() == Instruction::Or) { - if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) - if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) - if (LHS == RHS) - return LHS; - } - } return 0; } -/// GatherConstantSetNEs - Given a potentially 'and'd together collection of -/// setne instructions that compare a value against a constant, return the value -/// being compared, and stick the constant into the Values vector. -static Value *GatherConstantSetNEs(Value *V, std::vector &Values){ - if (Instruction *Inst = dyn_cast(V)) { - if (Inst->getOpcode() == Instruction::ICmp && - cast(Inst)->getPredicate() == ICmpInst::ICMP_NE) { - if (ConstantInt *C = dyn_cast(Inst->getOperand(1))) { - Values.push_back(C); - return Inst->getOperand(0); - } else if (ConstantInt *C = dyn_cast(Inst->getOperand(0))) { - Values.push_back(C); - return Inst->getOperand(1); +/// GatherConstantCompares - Given a potentially 'or'd or 'and'd together +/// collection of icmp eq/ne instructions that compare a value against a +/// constant, return the value being compared, and stick the constant into the +/// Values vector. +static Value * +GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, + const TargetData *TD, bool isEQ) { + Instruction *I = dyn_cast(V); + if (I == 0) return 0; + + // If this is an icmp against a constant, handle this as one of the cases. + if (ICmpInst *ICI = dyn_cast(I)) { + 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); } - } else if (Inst->getOpcode() == Instruction::And) { - if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) - if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) - if (LHS == RHS) - return LHS; + + // 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; } - return 0; -} - -/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a -/// bunch of comparisons of one value against constants, return the value and -/// the constants being compared. -static bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, - std::vector &Values) { - if (Cond->getOpcode() == Instruction::Or) { - CompVal = GatherConstantSetEQs(Cond, Values); - - // Return true to indicate that the condition is true if the CompVal is - // equal to one of the constants. - return true; - } else if (Cond->getOpcode() == Instruction::And) { - CompVal = GatherConstantSetNEs(Cond, Values); + + // Otherwise, we can only handle an | or &, depending on isEQ. + if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And)) + return 0; + + unsigned NumValsBeforeLHS = Vals.size(); + if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD, + isEQ)) { + unsigned NumVals = Vals.size(); + if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, + isEQ)) { + if (LHS == RHS) + return LHS; + Vals.resize(NumVals); + } - // Return false to indicate that the condition is false if the CompVal is - // equal to one of the constants. - return false; + // The RHS of the or/and can't be folded in and we haven't used "Extra" yet, + // set it and return success. + if (Extra == 0 || Extra == I->getOperand(1)) { + Extra = I->getOperand(1); + return LHS; + } + + Vals.resize(NumValsBeforeLHS); + return 0; } - return false; + + // If the LHS can't be folded in, but Extra is available and RHS can, try to + // use LHS as Extra. + if (Extra == 0 || Extra == I->getOperand(0)) { + Value *OldExtra = Extra; + Extra = I->getOperand(0); + if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, + isEQ)) + return RHS; + assert(Vals.size() == NumValsBeforeLHS); + Extra = OldExtra; + } + + return 0; } - + static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { Instruction* Cond = 0; if (SwitchInst *SI = dyn_cast(TI)) { @@ -479,6 +388,8 @@ static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { } else if (BranchInst *BI = dyn_cast(TI)) { if (BI->isConditional()) Cond = dyn_cast(BI->getCondition()); + } else if (IndirectBrInst *IBI = dyn_cast(TI)) { + Cond = dyn_cast(IBI->getAddress()); } TI->eraseFromParent(); @@ -487,29 +398,32 @@ static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { /// isValueEqualityComparison - Return true if the specified terminator checks /// to see if a value is equal to constant integer value. -static Value *isValueEqualityComparison(TerminatorInst *TI) { +Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { + Value *CV = 0; if (SwitchInst *SI = dyn_cast(TI)) { // Do not permit merging of large switch instructions into their // predecessors unless there is only one predecessor. - if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), - pred_end(SI->getParent())) > 128) - return 0; - - return SI->getCondition(); - } - if (BranchInst *BI = dyn_cast(TI)) + if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()), + pred_end(SI->getParent())) <= 128) + CV = SI->getCondition(); + } else if (BranchInst *BI = dyn_cast(TI)) if (BI->isConditional() && BI->getCondition()->hasOneUse()) if (ICmpInst *ICI = dyn_cast(BI->getCondition())) if ((ICI->getPredicate() == ICmpInst::ICMP_EQ || ICI->getPredicate() == ICmpInst::ICMP_NE) && - isa(ICI->getOperand(1))) - return ICI->getOperand(0); - return 0; + GetConstantInt(ICI->getOperand(1), TD)) + CV = ICI->getOperand(0); + + // Unwrap any lossless ptrtoint cast. + if (TD && CV && CV->getType() == TD->getIntPtrType(CV->getContext())) + if (PtrToIntInst *PTII = dyn_cast(CV)) + CV = PTII->getOperand(0); + return CV; } /// GetValueEqualityComparisonCases - Given a value comparison instruction, /// decode all of the 'cases' that it represents and return the 'default' block. -static BasicBlock * +BasicBlock *SimplifyCFGOpt:: GetValueEqualityComparisonCases(TerminatorInst *TI, std::vector > &Cases) { @@ -522,7 +436,7 @@ GetValueEqualityComparisonCases(TerminatorInst *TI, BranchInst *BI = cast(TI); ICmpInst *ICI = cast(BI->getCondition()); - Cases.push_back(std::make_pair(cast(ICI->getOperand(1)), + Cases.push_back(std::make_pair(GetConstantInt(ICI->getOperand(1), TD), BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE))); return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); @@ -561,8 +475,8 @@ ValuesOverlap(std::vector > &C1, } // Otherwise, just sort both lists and compare element by element. - std::sort(V1->begin(), V1->end()); - std::sort(V2->begin(), V2->end()); + array_pod_sort(V1->begin(), V1->end()); + array_pod_sort(V2->begin(), V2->end()); unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); while (i1 != e1 && i2 != e2) { if ((*V1)[i1].first == (*V2)[i2].first) @@ -581,8 +495,9 @@ ValuesOverlap(std::vector > &C1, /// comparison with the same value, and if that comparison determines the /// outcome of this comparison. If so, simplify TI. This does a very limited /// form of jump threading. -static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, - BasicBlock *Pred) { +bool SimplifyCFGOpt:: +SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, + BasicBlock *Pred) { Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); if (!PredVal) return false; // Not a value comparison in predecessor. @@ -607,90 +522,87 @@ static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, // If we are here, we know that the value is none of those cases listed in // PredCases. If there are any cases in ThisCases that are in PredCases, we // can simplify TI. - if (ValuesOverlap(PredCases, ThisCases)) { - if (isa(TI)) { - // Okay, one of the successors of this condbr is dead. Convert it to a - // uncond br. - assert(ThisCases.size() == 1 && "Branch can only have one case!"); - // Insert the new branch. - Instruction *NI = BranchInst::Create(ThisDef, TI); - (void) NI; - - // Remove PHI node entries for the dead edge. - ThisCases[0].second->removePredecessor(TI->getParent()); - - DEBUG(errs() << "Threading pred instr: " << *Pred->getTerminator() - << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); - - EraseTerminatorInstAndDCECond(TI); - return true; - - } else { - SwitchInst *SI = cast(TI); - // Okay, TI has cases that are statically dead, prune them away. - SmallPtrSet DeadCases; - for (unsigned i = 0, e = PredCases.size(); i != e; ++i) - DeadCases.insert(PredCases[i].first); + if (!ValuesOverlap(PredCases, ThisCases)) + return false; + + if (isa(TI)) { + // Okay, one of the successors of this condbr is dead. Convert it to a + // uncond br. + assert(ThisCases.size() == 1 && "Branch can only have one case!"); + // Insert the new branch. + Instruction *NI = BranchInst::Create(ThisDef, TI); + (void) NI; - DEBUG(errs() << "Threading pred instr: " << *Pred->getTerminator() - << "Through successor TI: " << *TI); + // Remove PHI node entries for the dead edge. + ThisCases[0].second->removePredecessor(TI->getParent()); - for (unsigned i = SI->getNumCases()-1; i != 0; --i) - if (DeadCases.count(SI->getCaseValue(i))) { - SI->getSuccessor(i)->removePredecessor(TI->getParent()); - SI->removeCase(i); - } + DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() + << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); - DEBUG(errs() << "Leaving: " << *TI << "\n"); - return true; - } + EraseTerminatorInstAndDCECond(TI); + return true; } - - } else { - // Otherwise, TI's block must correspond to some matched value. Find out - // which value (or set of values) this is. - ConstantInt *TIV = 0; - BasicBlock *TIBB = TI->getParent(); + + SwitchInst *SI = cast(TI); + // Okay, TI has cases that are statically dead, prune them away. + SmallPtrSet DeadCases; for (unsigned i = 0, e = PredCases.size(); i != e; ++i) - if (PredCases[i].second == TIBB) { - if (TIV == 0) - TIV = PredCases[i].first; - else - return false; // Cannot handle multiple values coming to this block. - } - assert(TIV && "No edge from pred to succ?"); - - // Okay, we found the one constant that our value can be if we get into TI's - // BB. Find out which successor will unconditionally be branched to. - BasicBlock *TheRealDest = 0; - for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) - if (ThisCases[i].first == TIV) { - TheRealDest = ThisCases[i].second; - break; + DeadCases.insert(PredCases[i].first); + + DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() + << "Through successor TI: " << *TI); + + for (unsigned i = SI->getNumCases()-1; i != 0; --i) + if (DeadCases.count(SI->getCaseValue(i))) { + SI->getSuccessor(i)->removePredecessor(TI->getParent()); + SI->removeCase(i); } - // If not handled by any explicit cases, it is handled by the default case. - if (TheRealDest == 0) TheRealDest = ThisDef; + DEBUG(dbgs() << "Leaving: " << *TI << "\n"); + return true; + } + + // Otherwise, TI's block must correspond to some matched value. Find out + // which value (or set of values) this is. + ConstantInt *TIV = 0; + BasicBlock *TIBB = TI->getParent(); + for (unsigned i = 0, e = PredCases.size(); i != e; ++i) + if (PredCases[i].second == TIBB) { + if (TIV != 0) + return false; // Cannot handle multiple values coming to this block. + TIV = PredCases[i].first; + } + assert(TIV && "No edge from pred to succ?"); + + // Okay, we found the one constant that our value can be if we get into TI's + // BB. Find out which successor will unconditionally be branched to. + BasicBlock *TheRealDest = 0; + for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) + if (ThisCases[i].first == TIV) { + TheRealDest = ThisCases[i].second; + break; + } + + // If not handled by any explicit cases, it is handled by the default case. + if (TheRealDest == 0) TheRealDest = ThisDef; - // Remove PHI node entries for dead edges. - BasicBlock *CheckEdge = TheRealDest; - for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) - if (*SI != CheckEdge) - (*SI)->removePredecessor(TIBB); - else - CheckEdge = 0; + // Remove PHI node entries for dead edges. + BasicBlock *CheckEdge = TheRealDest; + for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) + if (*SI != CheckEdge) + (*SI)->removePredecessor(TIBB); + else + CheckEdge = 0; - // Insert the new branch. - Instruction *NI = BranchInst::Create(TheRealDest, TI); - (void) NI; + // Insert the new branch. + Instruction *NI = BranchInst::Create(TheRealDest, TI); + (void) NI; - DEBUG(errs() << "Threading pred instr: " << *Pred->getTerminator() - << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); + DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() + << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); - EraseTerminatorInstAndDCECond(TI); - return true; - } - return false; + EraseTerminatorInstAndDCECond(TI); + return true; } namespace { @@ -704,11 +616,21 @@ namespace { }; } +static int ConstantIntSortPredicate(const void *P1, const void *P2) { + const ConstantInt *LHS = *(const ConstantInt**)P1; + const ConstantInt *RHS = *(const ConstantInt**)P2; + if (LHS->getValue().ult(RHS->getValue())) + return 1; + if (LHS->getValue() == RHS->getValue()) + return 0; + return -1; +} + /// FoldValueComparisonIntoPredecessors - The specified terminator is a value /// equality comparison instruction (either a switch or a branch on "X == c"). /// See if any of the predecessors of the terminator block are value comparisons /// on the same value. If so, and if safe to do so, fold them together. -static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { +bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { BasicBlock *BB = TI->getParent(); Value *CV = isValueEqualityComparison(TI); // CondVal assert(CV && "Not a comparison?"); @@ -801,6 +723,13 @@ static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) AddPredecessorToBlock(NewSuccessors[i], Pred, BB); + // Convert pointer to int before we switch. + if (CV->getType()->isPointerTy()) { + assert(TD && "Cannot switch on pointer without TargetData"); + CV = new PtrToIntInst(CV, TD->getIntPtrType(CV->getContext()), + "magicptr", PTI); + } + // Now that the successors are updated, create the new Switch instruction. SwitchInst *NewSI = SwitchInst::Create(CV, PredDefault, PredCases.size(), PTI); @@ -892,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)) @@ -913,7 +842,7 @@ HoistTerminator: // Okay, it is safe to hoist the terminator. Instruction *NT = I1->clone(); BIParent->getInstList().insert(BI, NT); - if (NT->getType() != Type::getVoidTy(BB1->getContext())) { + if (!NT->getType()->isVoidTy()) { I1->replaceAllUsesWith(NT); I2->replaceAllUsesWith(NT); NT->takeName(I1); @@ -930,18 +859,18 @@ HoistTerminator: (PN = dyn_cast(BBI)); ++BBI) { Value *BB1V = PN->getIncomingValueForBlock(BB1); Value *BB2V = PN->getIncomingValueForBlock(BB2); - if (BB1V != BB2V) { - // These values do not agree. Insert a select instruction before NT - // that determines the right value. - SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; - if (SI == 0) - SI = SelectInst::Create(BI->getCondition(), BB1V, BB2V, - BB1V->getName()+"."+BB2V->getName(), NT); - // Make the PHI node use the select for all incoming values for BB1/BB2 - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) - if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) - PN->setIncomingValue(i, SI); - } + if (BB1V == BB2V) continue; + + // These values do not agree. Insert a select instruction before NT + // that determines the right value. + SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; + if (SI == 0) + SI = SelectInst::Create(BI->getCondition(), BB1V, BB2V, + BB1V->getName()+"."+BB2V->getName(), NT); + // Make the PHI node use the select for all incoming values for BB1/BB2 + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) + PN->setIncomingValue(i, SI); } } @@ -966,21 +895,19 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { BBI != BBE; ++BBI) { Instruction *I = BBI; // Skip debug info. - if (isa(I)) continue; - if (I == Term) break; + if (isa(I)) continue; + if (I == Term) break; - if (!HInst) - HInst = I; - else + if (HInst) return false; + HInst = I; } if (!HInst) return false; // Be conservative for now. FP select instruction can often be expensive. Value *BrCond = BI->getCondition(); - if (isa(BrCond) && - cast(BrCond)->getOpcode() == Instruction::FCmp) + if (isa(BrCond)) return false; // If BB1 is actually on the false edge of the conditional branch, remember @@ -1009,7 +936,7 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { case Instruction::Add: case Instruction::Sub: // Not worth doing for vector ops. - if (isa(HInst->getType())) + if (HInst->getType()->isVectorTy()) return false; break; case Instruction::And: @@ -1019,7 +946,7 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { case Instruction::LShr: case Instruction::AShr: // Don't mess with vector operations. - if (isa(HInst->getType())) + if (HInst->getType()->isVectorTy()) return false; break; // These are all cheap and non-trapping instructions. } @@ -1043,7 +970,7 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { UI != E; ++UI) { // Ignore any user that is not a PHI node in BB2. These can only occur in // unreachable blocks, because they would not be dominated by the instr. - PHINode *PN = dyn_cast(UI); + PHINode *PN = dyn_cast(*UI); if (!PN || PN->getParent() != BB2) return false; PHIUses.push_back(PN); @@ -1084,12 +1011,12 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { for(Value::use_iterator UI = BrCond->use_begin(), UE = BrCond->use_end(); UI != UE; ++UI) { Instruction *Use = cast(*UI); - if (BB1Insns.count(Use)) { - // If BrCond uses the instruction that place it just before - // branch instruction. - InsertPos = BI; - break; - } + if (!BB1Insns.count(Use)) continue; + + // If BrCond uses the instruction that place it just before + // branch instruction. + InsertPos = BI; + break; } } else InsertPos = BI; @@ -1110,8 +1037,7 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { for (unsigned i = 0, e = PHIUses.size(); i != e; ++i) { PHINode *PN = PHIUses[i]; for (unsigned j = 0, ee = PN->getNumIncomingValues(); j != ee; ++j) - if (PN->getIncomingBlock(j) == BB1 || - PN->getIncomingBlock(j) == BIParent) + if (PN->getIncomingBlock(j) == BB1 || PN->getIncomingBlock(j) == BIParent) PN->setIncomingValue(j, SI); } @@ -1149,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 @@ -1169,78 +1095,73 @@ static bool FoldCondBranchOnPHI(BranchInst *BI) { // Okay, this is a simple enough basic block. See if any phi values are // constants. for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { - ConstantInt *CB; - if ((CB = dyn_cast(PN->getIncomingValue(i))) && - CB->getType() == Type::getInt1Ty(BB->getContext())) { - // Okay, we now know that all edges from PredBB should be revectored to - // branch to RealDest. - BasicBlock *PredBB = PN->getIncomingBlock(i); - BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); + ConstantInt *CB = dyn_cast(PN->getIncomingValue(i)); + if (CB == 0 || !CB->getType()->isIntegerTy(1)) continue; + + // Okay, we now know that all edges from PredBB should be revectored to + // branch to RealDest. + BasicBlock *PredBB = PN->getIncomingBlock(i); + BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); + + if (RealDest == BB) continue; // Skip self loops. + + // The dest block might have PHI nodes, other predecessors and other + // difficult cases. Instead of being smart about this, just insert a new + // block that jumps to the destination block, effectively splitting + // the edge we are about to create. + BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), + RealDest->getName()+".critedge", + RealDest->getParent(), RealDest); + BranchInst::Create(RealDest, 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 + // cloned instructions outside of EdgeBB. + BasicBlock::iterator InsertPt = EdgeBB->begin(); + DenseMap TranslateMap; // Track translated values. + for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { + if (PHINode *PN = dyn_cast(BBI)) { + TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); + continue; + } + // Clone the instruction. + Instruction *N = BBI->clone(); + if (BBI->hasName()) N->setName(BBI->getName()+".c"); - if (RealDest == BB) continue; // Skip self loops. + // Update operands due to translation. + for (User::op_iterator i = N->op_begin(), e = N->op_end(); + i != e; ++i) { + DenseMap::iterator PI = TranslateMap.find(*i); + if (PI != TranslateMap.end()) + *i = PI->second; + } - // The dest block might have PHI nodes, other predecessors and other - // difficult cases. Instead of being smart about this, just insert a new - // block that jumps to the destination block, effectively splitting - // the edge we are about to create. - BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), - 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); + // Check for trivial simplification. + 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); + if (!BBI->use_empty()) + TranslateMap[BBI] = N; } + } - // BB may have instructions that are being threaded over. Clone these - // instructions into EdgeBB. We know that there will be no uses of the - // cloned instructions outside of EdgeBB. - BasicBlock::iterator InsertPt = EdgeBB->begin(); - std::map TranslateMap; // Track translated values. - for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { - if (PHINode *PN = dyn_cast(BBI)) { - TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); - } else { - // Clone the instruction. - Instruction *N = BBI->clone(); - if (BBI->hasName()) N->setName(BBI->getName()+".c"); - - // Update operands due to translation. - for (User::op_iterator i = N->op_begin(), e = N->op_end(); - i != e; ++i) { - std::map::iterator PI = - TranslateMap.find(*i); - if (PI != TranslateMap.end()) - *i = PI->second; - } - - // Check for trivial simplification. - if (Constant *C = ConstantFoldInstruction(N)) { - TranslateMap[BBI] = C; - delete N; // Constant folded away, don't need actual inst - } else { - // Insert the new instruction into its new home. - EdgeBB->getInstList().insert(InsertPt, N); - if (!BBI->use_empty()) - TranslateMap[BBI] = N; - } - } + // Loop over all of the edges from PredBB to BB, changing them to branch + // to EdgeBB instead. + TerminatorInst *PredBBTI = PredBB->getTerminator(); + for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) + if (PredBBTI->getSuccessor(i) == BB) { + BB->removePredecessor(PredBB); + PredBBTI->setSuccessor(i, EdgeBB); } - - // Loop over all of the edges from PredBB to BB, changing them to branch - // to EdgeBB instead. - TerminatorInst *PredBBTI = PredBB->getTerminator(); - for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) - if (PredBBTI->getSuccessor(i) == BB) { - BB->removePredecessor(PredBB); - PredBBTI->setSuccessor(i, EdgeBB); - } - - // Recurse, simplifying any other constants. - return FoldCondBranchOnPHI(BI) | true; - } + + // Recurse, simplifying any other constants. + return FoldCondBranchOnPHI(BI, TD) | true; } return false; @@ -1248,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. @@ -1271,42 +1194,49 @@ static bool FoldTwoEntryPHINode(PHINode *PN) { if (NumPhis > 2) return false; - DEBUG(errs() << "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 @@ -1315,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 @@ -1328,56 +1257,45 @@ 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(), - IfBlock1->getInstList(), - IfBlock1->begin(), + if (IfBlock1) + DomBlock->getInstList().splice(InsertPt, + IfBlock1->getInstList(), IfBlock1->begin(), IfBlock1->getTerminator()); - } - if (IfBlock2) { - DomBlock->getInstList().splice(DomBlock->getTerminator(), - IfBlock2->getInstList(), - IfBlock2->begin(), + if (IfBlock2) + DomBlock->getInstList().splice(InsertPt, + IfBlock2->getInstList(), IfBlock2->begin(), IfBlock2->getTerminator()); - } while (PHINode *PN = dyn_cast(BB->begin())) { // Change the PHI node into a select instruction. - Value *TrueVal = - PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); - Value *FalseVal = - PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); + 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; } -/// isTerminatorFirstRelevantInsn - Return true if Term is very first -/// instruction ignoring Phi nodes and dbg intrinsics. -static bool isTerminatorFirstRelevantInsn(BasicBlock *BB, Instruction *Term) { - BasicBlock::iterator BBI = Term; - while (BBI != BB->begin()) { - --BBI; - if (!isa(BBI)) - break; - } - - if (isa(BBI) || &*BBI == Term || isa(BBI)) - return true; - return false; -} - /// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes /// to two returning blocks, try to merge them together into one return, /// introducing a select if the return values disagree. @@ -1391,9 +1309,9 @@ static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { // Check to ensure both blocks are empty (just a return) or optionally empty // with PHI nodes. If there are other instructions, merging would cause extra // computation on one path or the other. - if (!isTerminatorFirstRelevantInsn(TrueSucc, TrueRet)) + if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator()) return false; - if (!isTerminatorFirstRelevantInsn(FalseSucc, FalseRet)) + if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator()) return false; // Okay, we found a branch that is going to two return nodes. If @@ -1455,7 +1373,7 @@ static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { ReturnInst::Create(BI->getContext(), TrueValue, BI); (void) RI; - DEBUG(errs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" + DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" << "\n " << *BI << "NewRet = " << *RI << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); @@ -1471,21 +1389,34 @@ static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { bool llvm::FoldBranchToCommonDest(BranchInst *BI) { BasicBlock *BB = BI->getParent(); Instruction *Cond = dyn_cast(BI->getCondition()); - if (Cond == 0) return false; - + if (Cond == 0 || (!isa(Cond) && !isa(Cond)) || + Cond->getParent() != BB || !Cond->hasOneUse()) + return false; // Only allow this if the condition is a simple instruction that can be // executed unconditionally. It must be in the same block as the branch, and // must be at the front of the block. BasicBlock::iterator FrontIt = BB->front(); // Ignore dbg intrinsics. - while(isa(FrontIt)) + while (isa(FrontIt)) + ++FrontIt; + + // Allow a single instruction to be hoisted in addition to the compare + // that feeds the branch. We later ensure that any values that _it_ uses + // were also live in the predecessor, so that we don't unnecessarily create + // register pressure or inhibit out-of-order execution. + Instruction *BonusInst = 0; + if (&*FrontIt != Cond && + FrontIt->hasOneUse() && *FrontIt->use_begin() == Cond && + FrontIt->isSafeToSpeculativelyExecute()) { + BonusInst = &*FrontIt; ++FrontIt; - if ((!isa(Cond) && !isa(Cond)) || - Cond->getParent() != BB || &*FrontIt != Cond || !Cond->hasOneUse()) { - return false; } + // Only a single bonus inst is allowed. + if (&*FrontIt != Cond) + return false; + // Make sure the instruction after the condition is the cond branch. BasicBlock::iterator CondIt = Cond; ++CondIt; // Ingore dbg intrinsics. @@ -1523,6 +1454,44 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { !SafeToMergeTerminators(BI, PBI)) continue; + // Ensure that any values used in the bonus instruction are also used + // by the terminator of the predecessor. This means that those values + // must already have been resolved, so we won't be inhibiting the + // out-of-order core by speculating them earlier. + if (BonusInst) { + // Collect the values used by the bonus inst + SmallPtrSet UsedValues; + for (Instruction::op_iterator OI = BonusInst->op_begin(), + OE = BonusInst->op_end(); OI != OE; ++OI) { + Value* V = *OI; + if (!isa(V)) + UsedValues.insert(V); + } + + SmallVector, 4> Worklist; + Worklist.push_back(std::make_pair(PBI->getOperand(0), 0)); + + // Walk up to four levels back up the use-def chain of the predecessor's + // terminator to see if all those values were used. The choice of four + // levels is arbitrary, to provide a compile-time-cost bound. + while (!Worklist.empty()) { + std::pair Pair = Worklist.back(); + Worklist.pop_back(); + + if (Pair.second >= 4) continue; + UsedValues.erase(Pair.first); + if (UsedValues.empty()) break; + + if (Instruction *I = dyn_cast(Pair.first)) { + for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); + OI != OE; ++OI) + Worklist.push_back(std::make_pair(OI->get(), Pair.second+1)); + } + } + + if (!UsedValues.empty()) return false; + } + Instruction::BinaryOps Opc; bool InvertPredCond = false; @@ -1537,13 +1506,20 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { else continue; - DEBUG(errs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB); + DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB); // If we need to invert the condition in the pred block to match, do so now. if (InvertPredCond) { - Value *NewCond = - BinaryOperator::CreateNot(PBI->getCondition(), + Value *NewCond = PBI->getCondition(); + + if (NewCond->hasOneUse() && isa(NewCond)) { + CmpInst *CI = cast(NewCond); + CI->setPredicate(CI->getInversePredicate()); + } else { + NewCond = BinaryOperator::CreateNot(NewCond, PBI->getCondition()->getName()+".not", PBI); + } + PBI->setCondition(NewCond); BasicBlock *OldTrue = PBI->getSuccessor(0); BasicBlock *OldFalse = PBI->getSuccessor(1); @@ -1551,9 +1527,19 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { PBI->setSuccessor(1, OldTrue); } + // If we have a bonus inst, clone it into the predecessor block. + Instruction *NewBonus = 0; + if (BonusInst) { + NewBonus = BonusInst->clone(); + PredBlock->getInstList().insert(PBI, NewBonus); + NewBonus->takeName(BonusInst); + BonusInst->setName(BonusInst->getName()+".old"); + } + // Clone Cond into the predecessor basic block, and or/and the // two conditions together. Instruction *New = Cond->clone(); + if (BonusInst) New->replaceUsesOfWith(BonusInst, NewBonus); PredBlock->getInstList().insert(PBI, New); New->takeName(Cond); Cond->setName(New->getName()+".old"); @@ -1607,17 +1593,19 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { // Okay, we're going to insert the PHI node. Since PBI is not the only // predecessor, compute the PHI'd conditional value for all of the preds. // Any predecessor where the condition is not computable we keep symbolic. - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) - if ((PBI = dyn_cast((*PI)->getTerminator())) && + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + BasicBlock *P = *PI; + if ((PBI = dyn_cast(P->getTerminator())) && PBI != BI && PBI->isConditional() && PBI->getCondition() == BI->getCondition() && PBI->getSuccessor(0) != PBI->getSuccessor(1)) { bool CondIsTrue = PBI->getSuccessor(0) == BB; NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), - CondIsTrue), *PI); + CondIsTrue), P); } else { - NewPN->addIncoming(BI->getCondition(), *PI); + NewPN->addIncoming(BI->getCondition(), P); } + } BI->setCondition(NewPN); return true; @@ -1671,7 +1659,7 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { // Finally, if everything is ok, fold the branches to logical ops. BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); - DEBUG(errs() << "FOLDING BRs:" << *PBI->getParent() + DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() << "AND: " << *BI->getParent()); @@ -1691,7 +1679,7 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { OtherDest = InfLoopBlock; } - DEBUG(errs() << *PBI->getParent()->getParent()); + DEBUG(dbgs() << *PBI->getParent()->getParent()); // BI may have other predecessors. Because of this, we leave // it alone, but modify PBI. @@ -1717,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); @@ -1741,529 +1725,754 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { } } - DEBUG(errs() << "INTO: " << *PBI->getParent()); - DEBUG(errs() << *PBI->getParent()->getParent()); + DEBUG(dbgs() << "INTO: " << *PBI->getParent()); + DEBUG(dbgs() << *PBI->getParent()->getParent()); // This basic block is probably dead. We know it has at least // one fewer predecessor. return true; } -/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI -/// nodes in this block. This doesn't try to be clever about PHI nodes -/// which differ only in the order of the incoming values, but instcombine -/// orders them so it usually won't matter. -/// -static bool EliminateDuplicatePHINodes(BasicBlock *BB) { - bool Changed = false; - - // This implementation doesn't currently consider undef operands - // specially. Theroetically, two phis which are identical except for - // one having an undef where the other doesn't could be collapsed. - - // Map from PHI hash values to PHI nodes. If multiple PHIs have - // the same hash value, the element is the first PHI in the - // linked list in CollisionMap. - DenseMap HashMap; - - // Maintain linked lists of PHI nodes with common hash values. - DenseMap CollisionMap; - - // Examine each PHI. - for (BasicBlock::iterator I = BB->begin(); - PHINode *PN = dyn_cast(I++); ) { - // Compute a hash value on the operands. Instcombine will likely have sorted - // them, which helps expose duplicates, but we have to check all the - // operands to be safe in case instcombine hasn't run. - uintptr_t Hash = 0; - for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { - // This hash algorithm is quite weak as hash functions go, but it seems - // to do a good enough job for this particular purpose, and is very quick. - Hash ^= reinterpret_cast(static_cast(*I)); - Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); - } - // If we've never seen this hash value before, it's a unique PHI. - std::pair::iterator, bool> Pair = - HashMap.insert(std::make_pair(Hash, PN)); - if (Pair.second) continue; - // Otherwise it's either a duplicate or a hash collision. - for (PHINode *OtherPN = Pair.first->second; ; ) { - if (OtherPN->isIdenticalTo(PN)) { - // A duplicate. Replace this PHI with its duplicate. - PN->replaceAllUsesWith(OtherPN); - PN->eraseFromParent(); - Changed = true; - break; - } - // A non-duplicate hash collision. - DenseMap::iterator I = CollisionMap.find(OtherPN); - if (I == CollisionMap.end()) { - // Set this PHI to be the head of the linked list of colliding PHIs. - PHINode *Old = Pair.first->second; - Pair.first->second = PN; - CollisionMap[PN] = Old; - break; - } - // Procede to the next PHI in the list. - OtherPN = I->second; - } +// 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 + // successor. + BasicBlock *KeepEdge1 = TrueBB; + BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0; + + // Then remove the rest. + 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(OldTerm->getParent()); } - return Changed; -} + // Insert an appropriate new terminator. + if ((KeepEdge1 == 0) && (KeepEdge2 == 0)) { + if (TrueBB == FalseBB) + // We were only looking for one successor, and it was present. + // Create an unconditional branch to it. + 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, Cond, OldTerm); + } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { + // Neither of the selected blocks were successors, so this + // 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, OldTerm); + else + // Only FalseBB was found. + BranchInst::Create(FalseBB, OldTerm); + } -/// SimplifyCFG - This function is used to do simplification of a CFG. For -/// example, it adjusts branches to branches to eliminate the extra hop, it -/// eliminates unreachable basic blocks, and does other "peephole" optimization -/// of the CFG. It returns true if a modification was made. -/// -/// WARNING: The entry node of a function may not be simplified. -/// -bool llvm::SimplifyCFG(BasicBlock *BB) { - bool Changed = false; - Function *M = BB->getParent(); + EraseTerminatorInstAndDCECond(OldTerm); + return true; +} - assert(BB && BB->getParent() && "Block not embedded in function!"); - assert(BB->getTerminator() && "Degenerate basic block encountered!"); - assert(&BB->getParent()->getEntryBlock() != BB && - "Can't Simplify entry block!"); +// 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; - // Remove basic blocks that have no predecessors... or that just have themself - // as a predecessor. These are unreachable. - if (pred_begin(BB) == pred_end(BB) || BB->getSinglePredecessor() == BB) { - DEBUG(errs() << "Removing BB: \n" << *BB); - DeleteDeadBlock(BB); - return true; - } + // Extract the actual blocks. + BasicBlock *TrueBB = TBA->getBasicBlock(); + BasicBlock *FalseBB = FBA->getBasicBlock(); - // Check to see if we can constant propagate this terminator instruction - // away... - Changed |= ConstantFoldTerminator(BB); + // Perform the actual simplification. + return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB); +} - // Check for and eliminate duplicate PHI nodes in this block. - Changed |= EliminateDuplicatePHINodes(BB); +/// 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 +/// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified. In +/// this case, we merge the first two "or's of icmp" into a switch, but then the +/// default value goes to an uncond block with a seteq in it, we get something +/// like: +/// +/// switch i8 %A, label %DEFAULT [ i8 1, label %end i8 2, label %end ] +/// DEFAULT: +/// %tmp = icmp eq i8 %A, 92 +/// br label %end +/// end: +/// ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ] +/// +/// 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, + 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. + if (isa(BB->begin()) || !ICI->hasOneUse()) return false; + + Value *V = ICI->getOperand(0); + ConstantInt *Cst = cast(ICI->getOperand(1)); + + // The pattern we're looking for is where our only predecessor is a switch on + // 'V' and this block is the default case for the switch. In this case we can + // fold the compared value into the switch to simplify things. + BasicBlock *Pred = BB->getSinglePredecessor(); + if (Pred == 0 || !isa(Pred->getTerminator())) return false; + + SwitchInst *SI = cast(Pred->getTerminator()); + if (SI->getCondition() != V) + return false; + + // If BB is reachable on a non-default case, then we simply know the value of + // V in this block. Substitute it and constant fold the icmp instruction + // away. + if (SI->getDefaultDest() != BB) { + ConstantInt *VVal = SI->findCaseDest(BB); + assert(VVal && "Should have a unique destination value"); + ICI->setOperand(0, VVal); + + if (Value *V = SimplifyInstruction(ICI, TD)) { + ICI->replaceAllUsesWith(V); + ICI->eraseFromParent(); + } + // BB is now empty, so it is likely to simplify away. + return SimplifyCFG(BB) | true; + } + + // Ok, the block is reachable from the default dest. If the constant we're + // comparing exists in one of the other edges, then we can constant fold ICI + // and zap it. + if (SI->findCaseValue(Cst) != 0) { + Value *V; + if (ICI->getPredicate() == ICmpInst::ICMP_EQ) + V = ConstantInt::getFalse(BB->getContext()); + else + V = ConstantInt::getTrue(BB->getContext()); + + ICI->replaceAllUsesWith(V); + ICI->eraseFromParent(); + // BB is now empty, so it is likely to simplify away. + return SimplifyCFG(BB) | true; + } + + // The use of the icmp has to be in the 'end' block, by the only PHI node in + // the block. + BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0); + PHINode *PHIUse = dyn_cast(ICI->use_back()); + if (PHIUse == 0 || PHIUse != &SuccBlock->front() || + isa(++BasicBlock::iterator(PHIUse))) + return false; - // If there is a trivial two-entry PHI node in this basic block, and we can - // eliminate it, do so now. - if (PHINode *PN = dyn_cast(BB->begin())) - if (PN->getNumIncomingValues() == 2) - Changed |= FoldTwoEntryPHINode(PN); + // If the icmp is a SETEQ, then the default dest gets false, the new edge gets + // true in the PHI. + Constant *DefaultCst = ConstantInt::getTrue(BB->getContext()); + Constant *NewCst = ConstantInt::getFalse(BB->getContext()); - // If this is a returning block with only PHI nodes in it, fold the return - // instruction into any unconditional branch predecessors. - // - // If any predecessor is a conditional branch that just selects among - // different return values, fold the replace the branch/return with a select - // and return. - if (ReturnInst *RI = dyn_cast(BB->getTerminator())) { - if (isTerminatorFirstRelevantInsn(BB, BB->getTerminator())) { - // Find predecessors that end with branches. - SmallVector UncondBranchPreds; - SmallVector CondBranchPreds; - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { - TerminatorInst *PTI = (*PI)->getTerminator(); - if (BranchInst *BI = dyn_cast(PTI)) { - if (BI->isUnconditional()) - UncondBranchPreds.push_back(*PI); - else - CondBranchPreds.push_back(BI); - } - } + if (ICI->getPredicate() == ICmpInst::ICMP_EQ) + std::swap(DefaultCst, NewCst); - // If we found some, do the transformation! - if (!UncondBranchPreds.empty()) { - while (!UncondBranchPreds.empty()) { - BasicBlock *Pred = UncondBranchPreds.pop_back_val(); - DEBUG(errs() << "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); - - BasicBlock::iterator BBI = RI; - if (BBI != BB->begin()) { - // Move region end info into the predecessor. - if (DbgRegionEndInst *DREI = dyn_cast(--BBI)) - DREI->moveBefore(NewRet); - } + // Replace ICI (which is used by the PHI for the default value) with true or + // false depending on if it is EQ or NE. + ICI->replaceAllUsesWith(DefaultCst); + ICI->eraseFromParent(); - // 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); - } + // Okay, the switch goes to this block on a default value. Add an edge from + // the switch to the merge point on the compared value. + BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge", + BB->getParent(), BB); + SI->addCase(Cst, NewBB); + + // NewBB branches to the phi block, add the uncond branch and the phi entry. + BranchInst::Create(SuccBlock, NewBB); + PHIUse->addIncoming(NewCst, NewBB); + return true; +} - // If we eliminated all predecessors of the block, delete the block now. - if (pred_begin(BB) == pred_end(BB)) - // We know there are no successors, so just nuke the block. - M->getBasicBlockList().erase(BB); +/// SimplifyBranchOnICmpChain - The specified branch is a conditional branch. +/// Check to see if it is branching on an or/and chain of icmp instructions, and +/// fold it into a switch instruction if so. +static bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD) { + Instruction *Cond = dyn_cast(BI->getCondition()); + if (Cond == 0) return false; + + + // Change br (X == 0 | X == 1), T, F into a switch instruction. + // If this is a bunch of seteq's or'd together, or if it's a bunch of + // 'setne's and'ed together, collect them. + Value *CompVal = 0; + std::vector Values; + bool TrueWhenEqual = true; + Value *ExtraCase = 0; + + if (Cond->getOpcode() == Instruction::Or) { + CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true); + } else if (Cond->getOpcode() == Instruction::And) { + CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false); + TrueWhenEqual = false; + } + + // If we didn't have a multiply compared value, fail. + if (CompVal == 0) return false; - return true; - } + // There might be duplicate constants in the list, which the switch + // instruction can't handle, remove them now. + array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate); + Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); + + // If Extra was used, we require at least two switch values to do the + // transformation. A switch with one value is just an cond branch. + if (ExtraCase && Values.size() < 2) return false; + + // Figure out which block is which destination. + BasicBlock *DefaultBB = BI->getSuccessor(1); + BasicBlock *EdgeBB = BI->getSuccessor(0); + if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); + + BasicBlock *BB = BI->getParent(); + + 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) { + BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test"); + // Remove the uncond branch added to the old block. + TerminatorInst *OldTI = BB->getTerminator(); + + if (TrueWhenEqual) + BranchInst::Create(EdgeBB, NewBB, ExtraCase, OldTI); + else + BranchInst::Create(NewBB, EdgeBB, ExtraCase, OldTI); + + OldTI->eraseFromParent(); + + // If there are PHI nodes in EdgeBB, then we need to add a new entry to them + // for the edge we just added. + AddPredecessorToBlock(EdgeBB, BB, NewBB); + + DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase + << "\nEXTRABB = " << *BB); + BB = NewBB; + } + + // Convert pointer to int before we switch. + if (CompVal->getType()->isPointerTy()) { + assert(TD && "Cannot switch on pointer without TargetData"); + CompVal = new PtrToIntInst(CompVal, + TD->getIntPtrType(CompVal->getContext()), + "magicptr", BI); + } + + // Create the new switch instruction now. + SwitchInst *New = SwitchInst::Create(CompVal, DefaultBB, Values.size(), BI); + + // Add all of the 'cases' to the switch instruction. + for (unsigned i = 0, e = Values.size(); i != e; ++i) + New->addCase(Values[i], EdgeBB); + + // We added edges from PI to the EdgeBB. As such, if there were any + // PHI nodes in EdgeBB, they need entries to be added corresponding to + // the number of edges added. + for (BasicBlock::iterator BBI = EdgeBB->begin(); + isa(BBI); ++BBI) { + PHINode *PN = cast(BBI); + Value *InVal = PN->getIncomingValueForBlock(BB); + for (unsigned i = 0, e = Values.size()-1; i != e; ++i) + PN->addIncoming(InVal, BB); + } + + // Erase the old branch instruction. + EraseTerminatorInstAndDCECond(BI); + + DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n'); + return true; +} - // Check out all of the conditional branches going to this return - // instruction. If any of them just select between returns, change the - // branch itself into a select/return pair. - while (!CondBranchPreds.empty()) { - BranchInst *BI = CondBranchPreds.pop_back_val(); - - // Check to see if the non-BB successor is also a return block. - if (isa(BI->getSuccessor(0)->getTerminator()) && - isa(BI->getSuccessor(1)->getTerminator()) && - SimplifyCondBranchToTwoReturns(BI)) - return true; - } +bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI) { + BasicBlock *BB = RI->getParent(); + if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; + + // Find predecessors that end with branches. + SmallVector UncondBranchPreds; + SmallVector CondBranchPreds; + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + BasicBlock *P = *PI; + TerminatorInst *PTI = P->getTerminator(); + if (BranchInst *BI = dyn_cast(PTI)) { + if (BI->isUnconditional()) + UncondBranchPreds.push_back(P); + else + CondBranchPreds.push_back(BI); } - } else if (isa(BB->begin())) { - // Check to see if the first instruction in this block is just an unwind. - // If so, replace any invoke instructions which use this as an exception - // destination with call instructions. - // - SmallVector Preds(pred_begin(BB), pred_end(BB)); - while (!Preds.empty()) { - BasicBlock *Pred = Preds.back(); - if (InvokeInst *II = dyn_cast(Pred->getTerminator())) - if (II->getUnwindDest() == BB) { - // Insert a new branch instruction before the invoke, because this - // is now a fall through. - BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); - Pred->getInstList().remove(II); // Take out of symbol table - - // Insert the call now. - SmallVector Args(II->op_begin()+3, II->op_end()); - CallInst *CI = CallInst::Create(II->getCalledValue(), - Args.begin(), Args.end(), - II->getName(), BI); - CI->setCallingConv(II->getCallingConv()); - CI->setAttributes(II->getAttributes()); - // If the invoke produced a value, the Call now does instead. - II->replaceAllUsesWith(CI); - delete II; - Changed = true; - } - - Preds.pop_back(); + } + + // If we found some, do the transformation! + if (!UncondBranchPreds.empty() && DupRet) { + while (!UncondBranchPreds.empty()) { + BasicBlock *Pred = UncondBranchPreds.pop_back_val(); + DEBUG(dbgs() << "FOLDING: " << *BB + << "INTO UNCOND BRANCH PRED: " << *Pred); + (void)FoldReturnIntoUncondBranch(RI, BB, Pred); } - - // If this block is now dead, remove it. - if (pred_begin(BB) == pred_end(BB)) { + + // If we eliminated all predecessors of the block, delete the block now. + if (pred_begin(BB) == pred_end(BB)) // We know there are no successors, so just nuke the block. - M->getBasicBlockList().erase(BB); + BB->eraseFromParent(); + + return true; + } + + // Check out all of the conditional branches going to this return + // instruction. If any of them just select between returns, change the + // branch itself into a select/return pair. + while (!CondBranchPreds.empty()) { + BranchInst *BI = CondBranchPreds.pop_back_val(); + + // Check to see if the non-BB successor is also a return block. + if (isa(BI->getSuccessor(0)->getTerminator()) && + isa(BI->getSuccessor(1)->getTerminator()) && + SimplifyCondBranchToTwoReturns(BI)) return true; - } + } + return false; +} - } else if (SwitchInst *SI = dyn_cast(BB->getTerminator())) { - if (isValueEqualityComparison(SI)) { - // If we only have one predecessor, and if it is a branch on this value, - // see if that predecessor totally determines the outcome of this switch. - if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) - if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) - return SimplifyCFG(BB) || 1; - - // If the block only contains the switch, see if we can fold the block - // away into any preds. - BasicBlock::iterator BBI = BB->begin(); - // Ignore dbg intrinsics. - while (isa(BBI)) - ++BBI; - if (SI == &*BBI) - if (FoldValueComparisonIntoPredecessors(SI)) - return SimplifyCFG(BB) || 1; - } - } else if (BranchInst *BI = dyn_cast(BB->getTerminator())) { - if (BI->isUnconditional()) { - BasicBlock::iterator BBI = BB->getFirstNonPHI(); +bool SimplifyCFGOpt::SimplifyUnwind(UnwindInst *UI) { + // Check to see if the first instruction in this block is just an unwind. + // If so, replace any invoke instructions which use this as an exception + // destination with call instructions. + BasicBlock *BB = UI->getParent(); + if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; - BasicBlock *Succ = BI->getSuccessor(0); - // Ignore dbg intrinsics. - while (isa(BBI)) - ++BBI; - if (BBI->isTerminator() && // Terminator is the only non-phi instruction! - Succ != BB) // Don't hurt infinite loops! - if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ)) - return true; + bool Changed = false; + SmallVector Preds(pred_begin(BB), pred_end(BB)); + while (!Preds.empty()) { + BasicBlock *Pred = Preds.back(); + InvokeInst *II = dyn_cast(Pred->getTerminator()); + if (II && II->getUnwindDest() == BB) { + // Insert a new branch instruction before the invoke, because this + // is now a fall through. + BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); + Pred->getInstList().remove(II); // Take out of symbol table - } else { // Conditional branch - if (isValueEqualityComparison(BI)) { - // If we only have one predecessor, and if it is a branch on this value, - // see if that predecessor totally determines the outcome of this - // switch. - if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) - if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) - return SimplifyCFG(BB) || 1; - - // This block must be empty, except for the setcond inst, if it exists. - // Ignore dbg intrinsics. - BasicBlock::iterator I = BB->begin(); - // Ignore dbg intrinsics. - while (isa(I)) - ++I; - if (&*I == BI) { - if (FoldValueComparisonIntoPredecessors(BI)) - return SimplifyCFG(BB) | true; - } else if (&*I == cast(BI->getCondition())){ - ++I; - // Ignore dbg intrinsics. - while (isa(I)) - ++I; - if(&*I == BI) { - if (FoldValueComparisonIntoPredecessors(BI)) - return SimplifyCFG(BB) | true; - } - } - } - - // If this is a branch on a phi node in the current block, thread control - // 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)) - 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 SimplifyCFG(BB) | 1; - - - // Scan predecessor blocks for conditional branches. - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) - if (BranchInst *PBI = dyn_cast((*PI)->getTerminator())) - if (PBI != BI && PBI->isConditional()) - if (SimplifyCondBranchToCondBranch(PBI, BI)) - return SimplifyCFG(BB) | true; - } - } else if (isa(BB->getTerminator())) { - // If there are any instructions immediately before the unreachable that can - // be removed, do so. - Instruction *Unreachable = BB->getTerminator(); - while (Unreachable != BB->begin()) { - BasicBlock::iterator BBI = Unreachable; - --BBI; - // Do not delete instructions that can have side effects, like calls - // (which may never return) and volatile loads and stores. - if (isa(BBI) && !isa(BBI)) break; - - if (StoreInst *SI = dyn_cast(BBI)) - if (SI->isVolatile()) - break; - - if (LoadInst *LI = dyn_cast(BBI)) - if (LI->isVolatile()) - break; - - // Delete this instruction - BB->getInstList().erase(BBI); + // Insert the call now. + SmallVector Args(II->op_begin(), II->op_end()-3); + CallInst *CI = CallInst::Create(II->getCalledValue(), + Args.begin(), Args.end(), + II->getName(), BI); + CI->setCallingConv(II->getCallingConv()); + CI->setAttributes(II->getAttributes()); + // If the invoke produced a value, the Call now does instead. + II->replaceAllUsesWith(CI); + delete II; Changed = true; } + + Preds.pop_back(); + } + + // If this block is now dead (and isn't the entry block), remove it. + if (pred_begin(BB) == pred_end(BB) && + BB != &BB->getParent()->getEntryBlock()) { + // We know there are no successors, so just nuke the block. + BB->eraseFromParent(); + return true; + } + + return Changed; +} - // If the unreachable instruction is the first in the block, take a gander - // at all of the predecessors of this instruction, and simplify them. - if (&BB->front() == Unreachable) { - SmallVector Preds(pred_begin(BB), pred_end(BB)); - for (unsigned i = 0, e = Preds.size(); i != e; ++i) { - TerminatorInst *TI = Preds[i]->getTerminator(); - - if (BranchInst *BI = dyn_cast(TI)) { - if (BI->isUnconditional()) { - if (BI->getSuccessor(0) == BB) { - new UnreachableInst(TI->getContext(), TI); - TI->eraseFromParent(); - Changed = true; - } - } else { - if (BI->getSuccessor(0) == BB) { - BranchInst::Create(BI->getSuccessor(1), BI); - EraseTerminatorInstAndDCECond(BI); - } else if (BI->getSuccessor(1) == BB) { - BranchInst::Create(BI->getSuccessor(0), BI); - EraseTerminatorInstAndDCECond(BI); - Changed = true; - } +bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { + BasicBlock *BB = UI->getParent(); + + bool Changed = false; + + // If there are any instructions immediately before the unreachable that can + // be removed, do so. + while (UI != BB->begin()) { + BasicBlock::iterator BBI = UI; + --BBI; + // Do not delete instructions that can have side effects, like calls + // (which may never return) and volatile loads and stores. + if (isa(BBI) && !isa(BBI)) break; + + if (StoreInst *SI = dyn_cast(BBI)) + if (SI->isVolatile()) + break; + + if (LoadInst *LI = dyn_cast(BBI)) + if (LI->isVolatile()) + break; + + // Delete this instruction + BBI->eraseFromParent(); + Changed = true; + } + + // If the unreachable instruction is the first in the block, take a gander + // at all of the predecessors of this instruction, and simplify them. + if (&BB->front() != UI) return Changed; + + SmallVector Preds(pred_begin(BB), pred_end(BB)); + for (unsigned i = 0, e = Preds.size(); i != e; ++i) { + TerminatorInst *TI = Preds[i]->getTerminator(); + + if (BranchInst *BI = dyn_cast(TI)) { + if (BI->isUnconditional()) { + if (BI->getSuccessor(0) == BB) { + new UnreachableInst(TI->getContext(), TI); + TI->eraseFromParent(); + Changed = true; + } + } else { + if (BI->getSuccessor(0) == BB) { + BranchInst::Create(BI->getSuccessor(1), BI); + EraseTerminatorInstAndDCECond(BI); + } else if (BI->getSuccessor(1) == BB) { + BranchInst::Create(BI->getSuccessor(0), BI); + EraseTerminatorInstAndDCECond(BI); + Changed = true; + } + } + } else if (SwitchInst *SI = dyn_cast(TI)) { + for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) + if (SI->getSuccessor(i) == BB) { + BB->removePredecessor(SI->getParent()); + SI->removeCase(i); + --i; --e; + Changed = true; + } + // If the default value is unreachable, figure out the most popular + // destination and make it the default. + if (SI->getSuccessor(0) == BB) { + std::map Popularity; + for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) + Popularity[SI->getSuccessor(i)]++; + + // Find the most popular block. + unsigned MaxPop = 0; + BasicBlock *MaxBlock = 0; + for (std::map::iterator + I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { + if (I->second > MaxPop) { + MaxPop = I->second; + MaxBlock = I->first; } - } else if (SwitchInst *SI = dyn_cast(TI)) { + } + if (MaxBlock) { + // Make this the new default, allowing us to delete any explicit + // edges to it. + SI->setSuccessor(0, MaxBlock); + Changed = true; + + // If MaxBlock has phinodes in it, remove MaxPop-1 entries from + // it. + if (isa(MaxBlock->begin())) + for (unsigned i = 0; i != MaxPop-1; ++i) + MaxBlock->removePredecessor(SI->getParent()); + for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) - if (SI->getSuccessor(i) == BB) { - BB->removePredecessor(SI->getParent()); + if (SI->getSuccessor(i) == MaxBlock) { SI->removeCase(i); --i; --e; - Changed = true; - } - // If the default value is unreachable, figure out the most popular - // destination and make it the default. - if (SI->getSuccessor(0) == BB) { - std::map Popularity; - for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) - Popularity[SI->getSuccessor(i)]++; - - // Find the most popular block. - unsigned MaxPop = 0; - BasicBlock *MaxBlock = 0; - for (std::map::iterator - I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { - if (I->second > MaxPop) { - MaxPop = I->second; - MaxBlock = I->first; - } - } - if (MaxBlock) { - // Make this the new default, allowing us to delete any explicit - // edges to it. - SI->setSuccessor(0, MaxBlock); - Changed = true; - - // If MaxBlock has phinodes in it, remove MaxPop-1 entries from - // it. - if (isa(MaxBlock->begin())) - for (unsigned i = 0; i != MaxPop-1; ++i) - MaxBlock->removePredecessor(SI->getParent()); - - for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) - if (SI->getSuccessor(i) == MaxBlock) { - SI->removeCase(i); - --i; --e; - } } - } - } else if (InvokeInst *II = dyn_cast(TI)) { - if (II->getUnwindDest() == BB) { - // Convert the invoke to a call instruction. This would be a good - // place to note that the call does not throw though. - BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); - II->removeFromParent(); // Take out of symbol table - - // Insert the call now... - SmallVector Args(II->op_begin()+3, II->op_end()); - CallInst *CI = CallInst::Create(II->getCalledValue(), - Args.begin(), Args.end(), - II->getName(), BI); - CI->setCallingConv(II->getCallingConv()); - CI->setAttributes(II->getAttributes()); - // If the invoke produced a value, the Call does now instead. - II->replaceAllUsesWith(CI); - delete II; - Changed = true; - } } } + } else if (InvokeInst *II = dyn_cast(TI)) { + if (II->getUnwindDest() == BB) { + // Convert the invoke to a call instruction. This would be a good + // place to note that the call does not throw though. + BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); + II->removeFromParent(); // Take out of symbol table + + // Insert the call now... + SmallVector Args(II->op_begin(), II->op_end()-3); + CallInst *CI = CallInst::Create(II->getCalledValue(), + Args.begin(), Args.end(), + II->getName(), BI); + CI->setCallingConv(II->getCallingConv()); + CI->setAttributes(II->getAttributes()); + // If the invoke produced a value, the call does now instead. + II->replaceAllUsesWith(CI); + delete II; + Changed = true; + } + } + } + + // If this block is now dead, remove it. + if (pred_begin(BB) == pred_end(BB) && + BB != &BB->getParent()->getEntryBlock()) { + // We know there are no successors, so just nuke the block. + BB->eraseFromParent(); + return true; + } + + return Changed; +} - // If this block is now dead, remove it. - if (pred_begin(BB) == pred_end(BB)) { - // We know there are no successors, so just nuke the block. - M->getBasicBlockList().erase(BB); + +bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI) { + // If this switch is too complex to want to look at, ignore it. + if (!isValueEqualityComparison(SI)) + return false; + + BasicBlock *BB = SI->getParent(); + + // If we only have one predecessor, and if it is a branch on this value, + // see if that predecessor totally determines the outcome of this switch. + if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) + if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) + return SimplifyCFG(BB) | true; + + // If the block only contains the switch, see if we can fold the block + // away into any preds. + BasicBlock::iterator BBI = BB->begin(); + // Ignore dbg intrinsics. + while (isa(BBI)) + ++BBI; + if (SI == &*BBI) + if (FoldValueComparisonIntoPredecessors(SI)) + return SimplifyCFG(BB) | true; + + return false; +} + +bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { + BasicBlock *BB = IBI->getParent(); + bool Changed = false; + + // Eliminate redundant destinations. + SmallPtrSet Succs; + for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { + BasicBlock *Dest = IBI->getDestination(i); + if (!Dest->hasAddressTaken() || !Succs.insert(Dest)) { + Dest->removePredecessor(BB); + IBI->removeDestination(i); + --i; --e; + Changed = true; + } + } + + if (IBI->getNumDestinations() == 0) { + // If the indirectbr has no successors, change it to unreachable. + new UnreachableInst(IBI->getContext(), IBI); + EraseTerminatorInstAndDCECond(IBI); + return true; + } + + if (IBI->getNumDestinations() == 1) { + // If the indirectbr has one successor, change it to a direct branch. + BranchInst::Create(IBI->getDestination(0), IBI); + EraseTerminatorInstAndDCECond(IBI); + return true; + } + + if (SelectInst *SI = dyn_cast(IBI->getAddress())) { + if (SimplifyIndirectBrOnSelect(IBI, SI)) + return SimplifyCFG(BB) | true; + } + return Changed; +} + +bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI) { + BasicBlock *BB = BI->getParent(); + + // If the Terminator is the only non-phi instruction, simplify the block. + BasicBlock::iterator I = BB->getFirstNonPHIOrDbg(); + if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && + TryToSimplifyUncondBranchFromEmptyBlock(BB)) + return true; + + // If the only instruction in the block is a seteq/setne comparison + // against a constant, try to simplify the block. + if (ICmpInst *ICI = dyn_cast(I)) + if (ICI->isEquality() && isa(ICI->getOperand(1))) { + for (++I; isa(I); ++I) + ; + if (I->isTerminator() && TryToSimplifyUncondBranchWithICmpInIt(ICI, TD)) return true; - } } + + return false; +} + + +bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI) { + BasicBlock *BB = BI->getParent(); + + // Conditional branch + if (isValueEqualityComparison(BI)) { + // If we only have one predecessor, and if it is a branch on this value, + // see if that predecessor totally determines the outcome of this + // switch. + if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) + if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) + return SimplifyCFG(BB) | true; + + // This block must be empty, except for the setcond inst, if it exists. + // Ignore dbg intrinsics. + BasicBlock::iterator I = BB->begin(); + // Ignore dbg intrinsics. + while (isa(I)) + ++I; + if (&*I == BI) { + if (FoldValueComparisonIntoPredecessors(BI)) + return SimplifyCFG(BB) | true; + } else if (&*I == cast(BI->getCondition())){ + ++I; + // Ignore dbg intrinsics. + while (isa(I)) + ++I; + if (&*I == BI && FoldValueComparisonIntoPredecessors(BI)) + return SimplifyCFG(BB) | true; + } + } + + // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction. + if (SimplifyBranchOnICmpChain(BI, TD)) + return true; + + // We have a conditional branch to two blocks that are only reachable + // from BI. We know that the condbr dominates the two blocks, so see if + // there is any identical code in the "then" and "else" blocks. If so, we + // can hoist it up to the branching block. + if (BI->getSuccessor(0)->getSinglePredecessor() != 0) { + if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { + if (HoistThenElseCodeToIf(BI)) + return SimplifyCFG(BB) | true; + } else { + // If Successor #1 has multiple preds, we may be able to conditionally + // execute Successor #0 if it branches to successor #1. + TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator(); + if (Succ0TI->getNumSuccessors() == 1 && + Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) + if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0))) + return SimplifyCFG(BB) | true; + } + } else if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { + // If Successor #0 has multiple preds, we may be able to conditionally + // execute Successor #1 if it branches to successor #0. + TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator(); + if (Succ1TI->getNumSuccessors() == 1 && + Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) + if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1))) + return SimplifyCFG(BB) | true; + } + + // If this is a branch on a phi node in the current block, thread control + // 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, 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 SimplifyCFG(BB) | true; + + // Scan predecessor blocks for conditional branches. + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) + if (BranchInst *PBI = dyn_cast((*PI)->getTerminator())) + if (PBI != BI && PBI->isConditional()) + if (SimplifyCondBranchToCondBranch(PBI, BI)) + return SimplifyCFG(BB) | true; + + return false; +} + +bool SimplifyCFGOpt::run(BasicBlock *BB) { + bool Changed = false; + + 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 != &BB->getParent()->getEntryBlock()) || + BB->getSinglePredecessor() == BB) { + DEBUG(dbgs() << "Removing BB: \n" << *BB); + DeleteDeadBlock(BB); + return true; } + // Check to see if we can constant propagate this terminator instruction + // away... + Changed |= ConstantFoldTerminator(BB); + + // Check for and eliminate duplicate PHI nodes in this block. + Changed |= EliminateDuplicatePHINodes(BB); + // Merge basic blocks into their predecessor if there is only one distinct // pred, and if there is only one distinct successor of the predecessor, and // if there are no PHI nodes. // if (MergeBlockIntoPredecessor(BB)) return true; - - // Otherwise, if this block only has a single predecessor, and if that block - // is a conditional branch, see if we can hoist any code from this block up - // into our predecessor. - pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); - BasicBlock *OnlyPred = *PI++; - for (; PI != PE; ++PI) // Search all predecessors, see if they are all same - if (*PI != OnlyPred) { - OnlyPred = 0; // There are multiple different predecessors... - break; - } - if (OnlyPred) - if (BranchInst *BI = dyn_cast(OnlyPred->getTerminator())) - if (BI->isConditional()) { - // Get the other block. - BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); - PI = pred_begin(OtherBB); - ++PI; - - if (PI == pred_end(OtherBB)) { - // We have a conditional branch to two blocks that are only reachable - // from the condbr. We know that the condbr dominates the two blocks, - // so see if there is any identical code in the "then" and "else" - // blocks. If so, we can hoist it up to the branching block. - Changed |= HoistThenElseCodeToIf(BI); - } else { - BasicBlock* OnlySucc = NULL; - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); - SI != SE; ++SI) { - if (!OnlySucc) - OnlySucc = *SI; - else if (*SI != OnlySucc) { - OnlySucc = 0; // There are multiple distinct successors! - break; - } - } - - if (OnlySucc == OtherBB) { - // If BB's only successor is the other successor of the predecessor, - // i.e. a triangle, see if we can hoist any code from this block up - // to the "if" block. - Changed |= SpeculativelyExecuteBB(BI, BB); - } - } - } - - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) - if (BranchInst *BI = dyn_cast((*PI)->getTerminator())) - // Change br (X == 0 | X == 1), T, F into a switch instruction. - if (BI->isConditional() && isa(BI->getCondition())) { - Instruction *Cond = cast(BI->getCondition()); - // If this is a bunch of seteq's or'd together, or if it's a bunch of - // 'setne's and'ed together, collect them. - Value *CompVal = 0; - std::vector Values; - bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); - if (CompVal && CompVal->getType()->isInteger()) { - // There might be duplicate constants in the list, which the switch - // instruction can't handle, remove them now. - std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); - Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); - - // Figure out which block is which destination. - BasicBlock *DefaultBB = BI->getSuccessor(1); - BasicBlock *EdgeBB = BI->getSuccessor(0); - if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); - - // Create the new switch instruction now. - SwitchInst *New = SwitchInst::Create(CompVal, DefaultBB, - Values.size(), BI); - - // Add all of the 'cases' to the switch instruction. - for (unsigned i = 0, e = Values.size(); i != e; ++i) - New->addCase(Values[i], EdgeBB); - - // We added edges from PI to the EdgeBB. As such, if there were any - // PHI nodes in EdgeBB, they need entries to be added corresponding to - // the number of edges added. - for (BasicBlock::iterator BBI = EdgeBB->begin(); - isa(BBI); ++BBI) { - PHINode *PN = cast(BBI); - Value *InVal = PN->getIncomingValueForBlock(*PI); - for (unsigned i = 0, e = Values.size()-1; i != e; ++i) - PN->addIncoming(InVal, *PI); - } + // If there is a trivial two-entry PHI node in this basic block, and we can + // eliminate it, do so now. + if (PHINode *PN = dyn_cast(BB->begin())) + if (PN->getNumIncomingValues() == 2) + Changed |= FoldTwoEntryPHINode(PN, TD); - // Erase the old branch instruction. - EraseTerminatorInstAndDCECond(BI); - return true; - } - } + if (BranchInst *BI = dyn_cast(BB->getTerminator())) { + if (BI->isUnconditional()) { + if (SimplifyUncondBranch(BI)) return true; + } else { + if (SimplifyCondBranch(BI)) return true; + } + } else if (ReturnInst *RI = dyn_cast(BB->getTerminator())) { + if (SimplifyReturn(RI)) return true; + } else if (SwitchInst *SI = dyn_cast(BB->getTerminator())) { + if (SimplifySwitch(SI)) return true; + } else if (UnreachableInst *UI = + dyn_cast(BB->getTerminator())) { + if (SimplifyUnreachable(UI)) return true; + } else if (UnwindInst *UI = dyn_cast(BB->getTerminator())) { + if (SimplifyUnwind(UI)) return true; + } else if (IndirectBrInst *IBI = + dyn_cast(BB->getTerminator())) { + if (SimplifyIndirectBr(IBI)) return true; + } return Changed; } + +/// SimplifyCFG - This function is used to do simplification of a CFG. For +/// example, it adjusts branches to branches to eliminate the extra hop, it +/// eliminates unreachable basic blocks, and does other "peephole" optimization +/// of the CFG. It returns true if a modification was made. +/// +bool llvm::SimplifyCFG(BasicBlock *BB, const TargetData *TD) { + return SimplifyCFGOpt(TD).run(BB); +}