X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FSimplifyCFG.cpp;h=d7ca45e6e9700eafa253fbb12d32bc6b2f8e55e9;hb=43a8241b65b70ded3a87fb26852719633908a1e4;hp=96cd299242da8464dbe84238345d557e908f1518;hpb=3aaf5d993365c803dad9a8815b6c9864505af5b6;p=oota-llvm.git diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 96cd299242d..d7ca45e6e97 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -18,10 +18,13 @@ #include "llvm/IntrinsicInst.h" #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/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" @@ -33,10 +36,6 @@ using namespace llvm; STATISTIC(NumSpeculations, "Number of speculative executed instructions"); -#include "llvm/Support/CommandLine.h" -static cl::opt -DisableXForm("disable-xform", cl::Hidden, cl::init(false)); - /// SafeToMergeTerminators - Return true if it is safe to merge these two /// terminator instructions together. /// @@ -79,188 +78,6 @@ 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!"); - - DOUT << "Looking to fold " << BB->getNameStart() << " into " - << Succ->getNameStart() << "\n"; - // Shortcut, if there is only a single predecessor is must be BB and merging - // is always safe - if (Succ->getSinglePredecessor()) return true; - - typedef SmallPtrSet InstrSet; - InstrSet BBPHIs; - - // Make a list of all phi nodes in BB - BasicBlock::iterator BBI = BB->begin(); - while (isa(*BBI)) BBPHIs.insert(BBI++); - - // 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)) { - DOUT << "Can't fold, phi node " << *PN->getNameStart() << " in " - << Succ->getNameStart() << " is conflicting with " - << BBPN->getNameStart() << " with regard to common predecessor " - << (*PI)->getNameStart() << "\n"; - return false; - } - } - // Remove this phinode from the list of phis in BB, since it has been - // handled. - BBPHIs.erase(BBPN); - } 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)) { - DOUT << "Can't fold, phi node " << *PN->getNameStart() << " in " - << Succ->getNameStart() << " is conflicting with regard to common " - << "predecessor " << (*PI)->getNameStart() << "\n"; - return false; - } - } - } - } - - // If there are any other phi nodes in BB that don't have a phi node in Succ - // to merge with, they must be moved to Succ completely. However, for any - // predecessors of Succ, branches will be added to the phi node that just - // point to itself. So, for any common predecessors, this must not cause - // conflicts. - for (InstrSet::iterator I = BBPHIs.begin(), E = BBPHIs.end(); - I != E; I++) { - PHINode *PN = cast(*I); - for (BlockSet::iterator PI = CommonPreds.begin(), PE = CommonPreds.end(); - PI != PE; PI++) - if (PN->getIncomingValueForBlock(*PI) != PN) { - DOUT << "Can't fold, phi node " << *PN->getNameStart() << " in " - << BB->getNameStart() << " is conflicting with regard to common " - << "predecessor " << (*PI)->getNameStart() << "\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; - - DOUT << "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]); - } - } - } - - if (isa(&BB->front())) { - SmallVector - OldSuccPreds(pred_begin(Succ), pred_end(Succ)); - - // Move all PHI nodes in BB to Succ if they are alive, otherwise - // delete them. - while (PHINode *PN = dyn_cast(&BB->front())) { - if (PN->use_empty()) { - // Just remove the dead phi. This happens if Succ's PHIs were the only - // users of the PHI nodes. - PN->eraseFromParent(); - continue; - } - - // The instruction is alive, so this means that BB must dominate all - // predecessors of Succ (Since all uses of the PN are after its - // definition, so in Succ or a block dominated by Succ. If a predecessor - // of Succ would not be dominated by BB, PN would violate the def before - // use SSA demand). Therefore, we can simply move the phi node to the - // next block. - Succ->getInstList().splice(Succ->begin(), - BB->getInstList(), BB->begin()); - - // We need to add new entries for the PHI node to account for - // predecessors of Succ that the PHI node does not take into - // account. At this point, since we know that BB dominated succ and all - // of its predecessors, this means that we should any newly added - // incoming edges should use the PHI node itself as the value for these - // edges, because they are loop back edges. - for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) - if (OldSuccPreds[i] != BB) - PN->addIncoming(PN, OldSuccPreds[i]); - } - } - - // 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 @@ -351,7 +168,6 @@ static Value *GetIfCondition(BasicBlock *BB, return 0; } - /// DominatesMergePoint - If we have a merge point of an "if condition" as /// accepted above, return true if the specified value dominates the block. We /// don't handle the true generality of domination here, just a special case @@ -387,23 +203,22 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, // 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; + switch (I->getOpcode()) { default: return false; // Cannot hoist this out safely. - case Instruction::Load: - // We can hoist loads that are non-volatile and obviously cannot trap. - if (cast(I)->isVolatile()) - return false; - // FIXME: A computation of a constant can trap! - if (!isa(I->getOperand(0)) && - !isa(I->getOperand(0))) - return false; - - // Finally, 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. - if (PBB->begin() != BasicBlock::iterator(I)) + 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: @@ -413,9 +228,6 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB, case Instruction::LShr: case Instruction::AShr: case Instruction::ICmp: - case Instruction::FCmp: - if (I->getOperand(0)->getType()->isFPOrFPVector()) - return false; // FP arithmetic might trap. break; // These are all cheap and non-trapping instructions. } @@ -642,12 +454,13 @@ static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 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()); - DOUT << "Threading pred instr: " << *Pred->getTerminator() - << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"; + DEBUG(errs() << "Threading pred instr: " << *Pred->getTerminator() + << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); EraseTerminatorInstAndDCECond(TI); return true; @@ -659,8 +472,8 @@ static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, for (unsigned i = 0, e = PredCases.size(); i != e; ++i) DeadCases.insert(PredCases[i].first); - DOUT << "Threading pred instr: " << *Pred->getTerminator() - << "Through successor TI: " << *TI; + DEBUG(errs() << "Threading pred instr: " << *Pred->getTerminator() + << "Through successor TI: " << *TI); for (unsigned i = SI->getNumCases()-1; i != 0; --i) if (DeadCases.count(SI->getCaseValue(i))) { @@ -668,7 +481,7 @@ static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, SI->removeCase(i); } - DOUT << "Leaving: " << *TI << "\n"; + DEBUG(errs() << "Leaving: " << *TI << "\n"); return true; } } @@ -709,9 +522,10 @@ static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, // Insert the new branch. Instruction *NI = BranchInst::Create(TheRealDest, TI); + (void) NI; - DOUT << "Threading pred instr: " << *Pred->getTerminator() - << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"; + DEBUG(errs() << "Threading pred instr: " << *Pred->getTerminator() + << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); EraseTerminatorInstAndDCECond(TI); return true; @@ -719,6 +533,17 @@ static bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, return false; } +namespace { + /// ConstantIntOrdering - This class implements a stable ordering of constant + /// integers that does not depend on their address. This is important for + /// applications that sort ConstantInt's to ensure uniqueness. + struct ConstantIntOrdering { + bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { + return LHS->getValue().ult(RHS->getValue()); + } + }; +} + /// 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 @@ -731,8 +556,7 @@ static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { SmallVector Preds(pred_begin(BB), pred_end(BB)); while (!Preds.empty()) { - BasicBlock *Pred = Preds.back(); - Preds.pop_back(); + BasicBlock *Pred = Preds.pop_back_val(); // See if the predecessor is a comparison with the same value. TerminatorInst *PTI = Pred->getTerminator(); @@ -754,7 +578,7 @@ static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { if (PredDefault == BB) { // If this is the default destination from PTI, only the edges in TI // that don't occur in PTI, or that branch to BB will be activated. - std::set PTIHandled; + std::set PTIHandled; for (unsigned i = 0, e = PredCases.size(); i != e; ++i) if (PredCases[i].second != BB) PTIHandled.insert(PredCases[i].first); @@ -782,7 +606,7 @@ static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { // If this is not the default destination from PSI, only the edges // in SI that occur in PSI with a destination of BB will be // activated. - std::set PTIHandled; + std::set PTIHandled; for (unsigned i = 0, e = PredCases.size(); i != e; ++i) if (PredCases[i].second == BB) { PTIHandled.insert(PredCases[i].first); @@ -803,7 +627,8 @@ static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { // If there are any constants vectored to BB that TI doesn't handle, // they must go to the default destination of TI. - for (std::set::iterator I = PTIHandled.begin(), + for (std::set::iterator I = + PTIHandled.begin(), E = PTIHandled.end(); I != E; ++I) { PredCases.push_back(std::make_pair(*I, BBDefault)); NewSuccessors.push_back(BBDefault); @@ -833,7 +658,8 @@ static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { if (InfLoopBlock == 0) { // Insert it at the end of the function, because it's either code, // or it won't matter if it's hot. :) - InfLoopBlock = BasicBlock::Create("infloop", BB->getParent()); + InfLoopBlock = BasicBlock::Create(BB->getContext(), + "infloop", BB->getParent()); BranchInst::Create(InfLoopBlock, InfLoopBlock); } NewSI->setSuccessor(i, InfLoopBlock); @@ -845,6 +671,26 @@ static bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { return Changed; } +// isSafeToHoistInvoke - If we would need to insert a select that uses the +// value of this invoke (comments in HoistThenElseCodeToIf explain why we +// would need to do this), we can't hoist the invoke, as there is nowhere +// to put the select in this case. +static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, + Instruction *I1, Instruction *I2) { + for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { + PHINode *PN; + for (BasicBlock::iterator BBI = SI->begin(); + (PN = dyn_cast(BBI)); ++BBI) { + Value *BB1V = PN->getIncomingValueForBlock(BB1); + Value *BB2V = PN->getIncomingValueForBlock(BB2); + if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) { + return false; + } + } + } + return true; +} + /// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and /// BB2, hoist any common code in the two blocks up into the branch block. The /// caller of this function guarantees that BI's block dominates BB1 and BB2. @@ -865,8 +711,9 @@ static bool HoistThenElseCodeToIf(BranchInst *BI) { I1 = BB1_Itr++; while (isa(I2)) I2 = BB2_Itr++; - if (I1->getOpcode() != I2->getOpcode() || isa(I1) || - isa(I1) || !I1->isIdenticalTo(I2)) + if (I1->getOpcode() != I2->getOpcode() || isa(I1) || + !I1->isIdenticalToWhenDefined(I2) || + (isa(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) return false; // If we get here, we can hoist at least one instruction. @@ -884,6 +731,7 @@ static bool HoistThenElseCodeToIf(BranchInst *BI) { BIParent->getInstList().splice(BI, BB1->getInstList(), I1); if (!I2->use_empty()) I2->replaceAllUsesWith(I1); + I1->intersectOptionalDataWith(I2); BB2->getInstList().erase(I2); I1 = BB1_Itr++; @@ -892,15 +740,20 @@ static bool HoistThenElseCodeToIf(BranchInst *BI) { I2 = BB2_Itr++; while (isa(I2)) I2 = BB2_Itr++; - } while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2)); + } while (I1->getOpcode() == I2->getOpcode() && + I1->isIdenticalToWhenDefined(I2)); return true; HoistTerminator: + // It may not be possible to hoist an invoke. + if (isa(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) + return true; + // Okay, it is safe to hoist the terminator. Instruction *NT = I1->clone(); BIParent->getInstList().insert(BI, NT); - if (NT->getType() != Type::VoidTy) { + if (NT->getType() != Type::getVoidTy(BB1->getContext())) { I1->replaceAllUsesWith(NT); I2->replaceAllUsesWith(NT); NT->takeName(I1); @@ -947,11 +800,22 @@ HoistTerminator: static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { // Only speculatively execution a single instruction (not counting the // terminator) for now. - BasicBlock::iterator BBI = BB1->begin(); - ++BBI; // must have at least a terminator - if (BBI == BB1->end()) return false; // only one inst - ++BBI; - if (BBI != BB1->end()) return false; // more than 2 insts. + Instruction *HInst = NULL; + Instruction *Term = BB1->getTerminator(); + for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); + BBI != BBE; ++BBI) { + Instruction *I = BBI; + // Skip debug info. + if (isa(I)) continue; + if (I == Term) break; + + if (!HInst) + HInst = I; + else + return false; + } + if (!HInst) + return false; // Be conservative for now. FP select instruction can often be expensive. Value *BrCond = BI->getCondition(); @@ -980,13 +844,12 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { // %t1 = icmp // %t4 = add %t2, c // %t3 = select i1 %t1, %t2, %t3 - Instruction *I = BB1->begin(); - switch (I->getOpcode()) { + switch (HInst->getOpcode()) { default: return false; // Not safe / profitable to hoist. case Instruction::Add: case Instruction::Sub: - // FP arithmetic might trap. Not worth doing for vector ops. - if (I->getType()->isFloatingPoint() || isa(I->getType())) + // Not worth doing for vector ops. + if (isa(HInst->getType())) return false; break; case Instruction::And: @@ -996,14 +859,14 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { case Instruction::LShr: case Instruction::AShr: // Don't mess with vector operations. - if (isa(I->getType())) + if (isa(HInst->getType())) return false; break; // These are all cheap and non-trapping instructions. } // If the instruction is obviously dead, don't try to predicate it. - if (I->use_empty()) { - I->eraseFromParent(); + if (HInst->use_empty()) { + HInst->eraseFromParent(); return true; } @@ -1016,7 +879,7 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { Value *FalseV = NULL; BasicBlock *BB2 = BB1->getTerminator()->getSuccessor(0); - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); + for (Value::use_iterator UI = HInst->use_begin(), E = HInst->use_end(); 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. @@ -1037,7 +900,8 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { // Do not hoist the instruction if any of its operands are defined but not // used in this BB. The transformation will prevent the operand from // being sunk into the use block. - for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) { + for (User::op_iterator i = HInst->op_begin(), e = HInst->op_end(); + i != e; ++i) { Instruction *OpI = dyn_cast(*i); if (OpI && OpI->getParent() == BIParent && !OpI->isUsedInBasicBlock(BIParent)) @@ -1045,9 +909,12 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { } // If we get here, we can hoist the instruction. Try to place it - // before the icmp instruction preceeding the conditional branch. + // before the icmp instruction preceding the conditional branch. BasicBlock::iterator InsertPos = BI; - if (InsertPos != BIParent->begin()) + if (InsertPos != BIParent->begin()) + --InsertPos; + // Skip debug info between condition and branch. + while (InsertPos != BIParent->begin() && isa(InsertPos)) --InsertPos; if (InsertPos == BrCond && !isa(BrCond)) { SmallPtrSet BB1Insns; @@ -1066,17 +933,17 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { } } else InsertPos = BI; - BIParent->getInstList().splice(InsertPos, BB1->getInstList(), I); + BIParent->getInstList().splice(InsertPos, BB1->getInstList(), HInst); // Create a select whose true value is the speculatively executed value and // false value is the previously determined FalseV. SelectInst *SI; if (Invert) - SI = SelectInst::Create(BrCond, FalseV, I, - FalseV->getName() + "." + I->getName(), BI); + SI = SelectInst::Create(BrCond, FalseV, HInst, + FalseV->getName() + "." + HInst->getName(), BI); else - SI = SelectInst::Create(BrCond, I, FalseV, - I->getName() + "." + FalseV->getName(), BI); + SI = SelectInst::Create(BrCond, HInst, FalseV, + HInst->getName() + "." + FalseV->getName(), BI); // Make the PHI node use the select for all incoming values for "then" and // "if" blocks. @@ -1098,12 +965,13 @@ static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { BranchInst *BI = cast(BB->getTerminator()); unsigned Size = 0; - // If this basic block contains anything other than a PHI (which controls the - // branch) and branch itself, bail out. FIXME: improve this in the future. - for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI, ++Size) { + for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { + if (isa(BBI)) + continue; if (Size > 10) return false; // Don't clone large BB's. + ++Size; - // We can only support instructions that are do not define values that are + // We can only support instructions that do not define values that are // live outside of the current basic block. for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); UI != E; ++UI) { @@ -1143,7 +1011,7 @@ static bool FoldCondBranchOnPHI(BranchInst *BI) { for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { ConstantInt *CB; if ((CB = dyn_cast(PN->getIncomingValue(i))) && - CB->getType() == Type::Int1Ty) { + 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); @@ -1155,7 +1023,8 @@ static bool FoldCondBranchOnPHI(BranchInst *BI) { // 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(RealDest->getName()+".critedge", + BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), + RealDest->getName()+".critedge", RealDest->getParent(), RealDest); BranchInst::Create(RealDest, EdgeBB); PHINode *PN; @@ -1242,8 +1111,8 @@ static bool FoldTwoEntryPHINode(PHINode *PN) { if (NumPhis > 2) return false; - DOUT << "FOUND IF CONDITION! " << *IfCond << " T: " - << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"; + 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 @@ -1373,7 +1242,7 @@ static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { if (FalseRet->getNumOperands() == 0) { TrueSucc->removePredecessor(BI->getParent()); FalseSucc->removePredecessor(BI->getParent()); - ReturnInst::Create(0, BI); + ReturnInst::Create(BI->getContext(), 0, BI); EraseTerminatorInstAndDCECond(BI); return true; } @@ -1422,12 +1291,13 @@ static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { } Value *RI = !TrueValue ? - ReturnInst::Create(BI) : - ReturnInst::Create(TrueValue, BI); + ReturnInst::Create(BI->getContext(), BI) : + ReturnInst::Create(BI->getContext(), TrueValue, BI); + (void) RI; - DOUT << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" - << "\n " << *BI << "NewRet = " << *RI - << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc; + DEBUG(errs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" + << "\n " << *BI << "NewRet = " << *RI + << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); EraseTerminatorInstAndDCECond(BI); @@ -1438,7 +1308,7 @@ static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { /// 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. -static bool FoldBranchToCommonDest(BranchInst *BI) { +bool llvm::FoldBranchToCommonDest(BranchInst *BI) { BasicBlock *BB = BI->getParent(); Instruction *Cond = dyn_cast(BI->getCondition()); if (Cond == 0) return false; @@ -1507,7 +1377,7 @@ static bool FoldBranchToCommonDest(BranchInst *BI) { else continue; - DOUT << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB; + DEBUG(errs() << "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) { @@ -1551,7 +1421,7 @@ static bool FoldBranchToCommonDest(BranchInst *BI) { static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { assert(PBI->isConditional() && BI->isConditional()); BasicBlock *BB = BI->getParent(); - + // If this block ends with a branch instruction, and if there is a // predecessor that ends on a branch of the same condition, make // this conditional branch redundant. @@ -1562,7 +1432,8 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { if (BB->getSinglePredecessor()) { // Turn this into a branch on constant. bool CondIsTrue = PBI->getSuccessor(0) == BB; - BI->setCondition(ConstantInt::get(Type::Int1Ty, CondIsTrue)); + BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), + CondIsTrue)); return true; // Nuke the branch on constant. } @@ -1570,7 +1441,7 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { // in the constant and simplify the block result. Subsequent passes of // simplifycfg will thread the block. if (BlockIsSimpleEnoughToThreadThrough(BB)) { - PHINode *NewPN = PHINode::Create(Type::Int1Ty, + PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()), BI->getCondition()->getName() + ".pr", BB->begin()); // Okay, we're going to insert the PHI node. Since PBI is not the only @@ -1582,7 +1453,7 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { PBI->getCondition() == BI->getCondition() && PBI->getSuccessor(0) != PBI->getSuccessor(1)) { bool CondIsTrue = PBI->getSuccessor(0) == BB; - NewPN->addIncoming(ConstantInt::get(Type::Int1Ty, + NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), CondIsTrue), *PI); } else { NewPN->addIncoming(BI->getCondition(), *PI); @@ -1640,8 +1511,8 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { // Finally, if everything is ok, fold the branches to logical ops. BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); - DOUT << "FOLDING BRs:" << *PBI->getParent() - << "AND: " << *BI->getParent(); + DEBUG(errs() << "FOLDING BRs:" << *PBI->getParent() + << "AND: " << *BI->getParent()); // If OtherDest *is* BB, then BB is a basic block with a single conditional @@ -1654,12 +1525,13 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { if (OtherDest == BB) { // Insert it at the end of the function, because it's either code, // or it won't matter if it's hot. :) - BasicBlock *InfLoopBlock = BasicBlock::Create("infloop", BB->getParent()); + BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(), + "infloop", BB->getParent()); BranchInst::Create(InfLoopBlock, InfLoopBlock); OtherDest = InfLoopBlock; } - DOUT << *PBI->getParent()->getParent(); + DEBUG(errs() << *PBI->getParent()->getParent()); // BI may have other predecessors. Because of this, we leave // it alone, but modify PBI. @@ -1709,27 +1581,14 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { } } - DOUT << "INTO: " << *PBI->getParent(); - - DOUT << *PBI->getParent()->getParent(); + DEBUG(errs() << "INTO: " << *PBI->getParent()); + DEBUG(errs() << *PBI->getParent()->getParent()); // This basic block is probably dead. We know it has at least // one fewer predecessor. return true; } - -namespace { - /// ConstantIntOrdering - This class implements a stable ordering of constant - /// integers that does not depend on their address. This is important for - /// applications that sort ConstantInt's to ensure uniqueness. - struct ConstantIntOrdering { - bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { - return LHS->getValue().ult(RHS->getValue()); - } - }; -} - /// 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 @@ -1749,7 +1608,7 @@ bool llvm::SimplifyCFG(BasicBlock *BB) { // 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) { - DOUT << "Removing BB: \n" << *BB; + DEBUG(errs() << "Removing BB: \n" << *BB); DeleteDeadBlock(BB); return true; } @@ -1758,6 +1617,9 @@ bool llvm::SimplifyCFG(BasicBlock *BB) { // away... Changed |= ConstantFoldTerminator(BB); + // Check for and eliminate duplicate PHI nodes in this block. + Changed |= EliminateDuplicatePHINodes(BB); + // 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())) @@ -1786,12 +1648,11 @@ bool llvm::SimplifyCFG(BasicBlock *BB) { } // If we found some, do the transformation! - if (!UncondBranchPreds.empty() && !DisableXForm) { + if (!UncondBranchPreds.empty()) { while (!UncondBranchPreds.empty()) { - BasicBlock *Pred = UncondBranchPreds.back(); - DOUT << "FOLDING: " << *BB - << "INTO UNCOND BRANCH PRED: " << *Pred; - UncondBranchPreds.pop_back(); + 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(); @@ -1830,8 +1691,7 @@ bool llvm::SimplifyCFG(BasicBlock *BB) { // instruction. If any of them just select between returns, change the // branch itself into a select/return pair. while (!CondBranchPreds.empty()) { - BranchInst *BI = CondBranchPreds.back(); - CondBranchPreds.pop_back(); + 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()) && @@ -1843,33 +1703,26 @@ bool llvm::SimplifyCFG(BasicBlock *BB) { } 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, and any unconditional branch - // predecessor with an unwind. + // destination with call instructions. // SmallVector Preds(pred_begin(BB), pred_end(BB)); while (!Preds.empty()) { BasicBlock *Pred = Preds.back(); - if (BranchInst *BI = dyn_cast(Pred->getTerminator())) { - if (BI->isUnconditional()) { - Pred->getInstList().pop_back(); // nuke uncond branch - new UnwindInst(Pred); // Use unwind. - Changed = true; - } - } else if (InvokeInst *II = dyn_cast(Pred->getTerminator())) + 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... + // 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... + // 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 + // If the invoke produced a value, the Call now does instead. II->replaceAllUsesWith(CI); delete II; Changed = true; @@ -1907,13 +1760,11 @@ bool llvm::SimplifyCFG(BasicBlock *BB) { if (BI->isUnconditional()) { BasicBlock::iterator BBI = BB->getFirstNonPHI(); - 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)) + if (BBI->isTerminator()) // Terminator is the only non-phi instruction! + if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) return true; } else { // Conditional branch @@ -1976,7 +1827,7 @@ bool llvm::SimplifyCFG(BasicBlock *BB) { --BBI; // Do not delete instructions that can have side effects, like calls // (which may never return) and volatile loads and stores. - if (isa(BBI)) break; + if (isa(BBI) && !isa(BBI)) break; if (StoreInst *SI = dyn_cast(BBI)) if (SI->isVolatile()) @@ -2001,7 +1852,7 @@ bool llvm::SimplifyCFG(BasicBlock *BB) { if (BranchInst *BI = dyn_cast(TI)) { if (BI->isUnconditional()) { if (BI->getSuccessor(0) == BB) { - new UnreachableInst(TI); + new UnreachableInst(TI->getContext(), TI); TI->eraseFromParent(); Changed = true; }