X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FSimplifyCFG.cpp;h=b9432c2e6e1a638e4455431d5afd421efb203a11;hb=5e6940788fb2f8cf3ce4219d3ac0f78317f54696;hp=23a3a25056a28d452a7c7ed0754433acb987c0df;hpb=ba3c8155704e5e2ac24b5069c32bca359b0738ed;p=oota-llvm.git diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 23a3a25056a..b9432c2e6e1 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -28,6 +28,8 @@ #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 @@ -35,6 +37,10 @@ #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 { @@ -305,11 +311,32 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, // If this is an icmp against a constant, handle this as one of the cases. if (ICmpInst *ICI = dyn_cast(I)) { - if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) - if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) { + if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) { + if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) { Vals.push_back(C); return I->getOperand(0); } + + // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to + // the set. + ConstantRange Span = + ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue()); + + // If this is an and/!= check then we want to optimize "x ugt 2" into + // x != 0 && x != 1. + if (!isEQ) + Span = Span.inverse(); + + // If there are a ton of values, we don't want to make a ginormous switch. + if (Span.getSetSize().ugt(8) || Span.isEmptySet() || + // We don't handle wrapped sets yet. + Span.isWrappedSet()) + return 0; + + for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp) + Vals.push_back(ConstantInt::get(V->getContext(), Tmp)); + return I->getOperand(0); + } return 0; } @@ -1706,22 +1733,13 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { return true; } -// SimplifyIndirectBrOnSelect - Replaces -// (indirectbr (select cond, blockaddress(@fn, BlockA), -// blockaddress(@fn, BlockB))) -// with -// (br cond, BlockA, BlockB). -static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { - // Check that both operands of the select are block addresses. - BlockAddress *TBA = dyn_cast(SI->getTrueValue()); - BlockAddress *FBA = dyn_cast(SI->getFalseValue()); - if (!TBA || !FBA) - return false; - - // Extract the actual blocks. - BasicBlock *TrueBB = TBA->getBasicBlock(); - BasicBlock *FalseBB = FBA->getBasicBlock(); - +// SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a +// branch to TrueBB if Cond is true or to FalseBB if Cond is false. +// Takes care of updating the successors and removing the old terminator. +// Also makes sure not to introduce new successors by assuming that edges to +// non-successor TrueBBs and FalseBBs aren't reachable. +static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, + BasicBlock *TrueBB, BasicBlock *FalseBB){ // Remove any superfluous successor edges from the CFG. // First, figure out which successors to preserve. // If TrueBB and FalseBB are equal, only try to preserve one copy of that @@ -1730,15 +1748,15 @@ static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0; // Then remove the rest. - for (unsigned I = 0, E = IBI->getNumSuccessors(); I != E; ++I) { - BasicBlock *Succ = IBI->getSuccessor(I); + for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) { + BasicBlock *Succ = OldTerm->getSuccessor(I); // Make sure only to keep exactly one copy of each edge. if (Succ == KeepEdge1) KeepEdge1 = 0; else if (Succ == KeepEdge2) KeepEdge2 = 0; else - Succ->removePredecessor(IBI->getParent()); + Succ->removePredecessor(OldTerm->getParent()); } // Insert an appropriate new terminator. @@ -1746,31 +1764,51 @@ static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { if (TrueBB == FalseBB) // We were only looking for one successor, and it was present. // Create an unconditional branch to it. - BranchInst::Create(TrueBB, IBI); + BranchInst::Create(TrueBB, OldTerm); else // We found both of the successors we were looking for. // Create a conditional branch sharing the condition of the select. - BranchInst::Create(TrueBB, FalseBB, SI->getCondition(), IBI); + BranchInst::Create(TrueBB, FalseBB, Cond, OldTerm); } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { // Neither of the selected blocks were successors, so this - // indirectbr must be unreachable. - new UnreachableInst(IBI->getContext(), IBI); + // terminator must be unreachable. + new UnreachableInst(OldTerm->getContext(), OldTerm); } else { // One of the selected values was a successor, but the other wasn't. // Insert an unconditional branch to the one that was found; // the edge to the one that wasn't must be unreachable. if (KeepEdge1 == 0) // Only TrueBB was found. - BranchInst::Create(TrueBB, IBI); + BranchInst::Create(TrueBB, OldTerm); else // Only FalseBB was found. - BranchInst::Create(FalseBB, IBI); + BranchInst::Create(FalseBB, OldTerm); } - EraseTerminatorInstAndDCECond(IBI); + EraseTerminatorInstAndDCECond(OldTerm); return true; } +// SimplifyIndirectBrOnSelect - Replaces +// (indirectbr (select cond, blockaddress(@fn, BlockA), +// blockaddress(@fn, BlockB))) +// with +// (br cond, BlockA, BlockB). +static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { + // Check that both operands of the select are block addresses. + BlockAddress *TBA = dyn_cast(SI->getTrueValue()); + BlockAddress *FBA = dyn_cast(SI->getFalseValue()); + if (!TBA || !FBA) + return false; + + // Extract the actual blocks. + BasicBlock *TrueBB = TBA->getBasicBlock(); + BasicBlock *FalseBB = FBA->getBasicBlock(); + + // Perform the actual simplification. + return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB); +} + /// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp /// instruction (a seteq/setne with a constant) as the only instruction in a /// block that ends with an uncond branch. We are looking for a very specific @@ -1994,28 +2032,12 @@ bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI) { } // If we found some, do the transformation! - if (!UncondBranchPreds.empty()) { + if (!UncondBranchPreds.empty() && DupRet) { while (!UncondBranchPreds.empty()) { BasicBlock *Pred = UncondBranchPreds.pop_back_val(); DEBUG(dbgs() << "FOLDING: " << *BB << "INTO UNCOND BRANCH PRED: " << *Pred); - Instruction *UncondBranch = Pred->getTerminator(); - // Clone the return and add it to the end of the predecessor. - Instruction *NewRet = RI->clone(); - Pred->getInstList().push_back(NewRet); - - // If the return instruction returns a value, and if the value was a - // PHI node in "BB", propagate the right value into the return. - for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end(); - i != e; ++i) - if (PHINode *PN = dyn_cast(*i)) - if (PN->getParent() == BB) - *i = PN->getIncomingValueForBlock(Pred); - - // Update any PHI nodes in the returning block to realize that we no - // longer branch to them. - BB->removePredecessor(Pred); - UncondBranch->eraseFromParent(); + (void)FoldReturnIntoUncondBranch(RI, BB, Pred); } // If we eliminated all predecessors of the block, delete the block now.