diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Scalar/JumpThreading.cpp')
| -rw-r--r-- | contrib/llvm/lib/Transforms/Scalar/JumpThreading.cpp | 130 |
1 files changed, 84 insertions, 46 deletions
diff --git a/contrib/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/contrib/llvm/lib/Transforms/Scalar/JumpThreading.cpp index 21f80385..78beb3f 100644 --- a/contrib/llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ b/contrib/llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -26,6 +26,7 @@ #include "llvm/IR/DataLayout.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Metadata.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" @@ -44,7 +45,7 @@ STATISTIC(NumFolds, "Number of terminators folded"); STATISTIC(NumDupes, "Number of branch blocks duplicated to eliminate phi"); static cl::opt<unsigned> -Threshold("jump-threading-threshold", +BBDuplicateThreshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden); @@ -87,6 +88,8 @@ namespace { #endif DenseSet<std::pair<Value*, BasicBlock*> > RecursionSet; + unsigned BBDupThreshold; + // RAII helper for updating the recursion stack. struct RecursionSetRemover { DenseSet<std::pair<Value*, BasicBlock*> > &TheSet; @@ -102,7 +105,8 @@ namespace { }; public: static char ID; // Pass identification - JumpThreading() : FunctionPass(ID) { + JumpThreading(int T = -1) : FunctionPass(ID) { + BBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T); initializeJumpThreadingPass(*PassRegistry::getPassRegistry()); } @@ -123,9 +127,11 @@ namespace { bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, - ConstantPreference Preference); + ConstantPreference Preference, + Instruction *CxtI = nullptr); bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, - ConstantPreference Preference); + ConstantPreference Preference, + Instruction *CxtI = nullptr); bool ProcessBranchOnPHI(PHINode *PN); bool ProcessBranchOnXOR(BinaryOperator *BO); @@ -144,7 +150,7 @@ INITIALIZE_PASS_END(JumpThreading, "jump-threading", "Jump Threading", false, false) // Public interface to the Jump Threading pass -FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); } +FunctionPass *llvm::createJumpThreadingPass(int Threshold) { return new JumpThreading(Threshold); } /// runOnFunction - Top level algorithm. /// @@ -182,7 +188,7 @@ bool JumpThreading::runOnFunction(Function &F) { // If the block is trivially dead, zap it. This eliminates the successor // edges which simplifies the CFG. - if (pred_begin(BB) == pred_end(BB) && + if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) { DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName() << "' with terminator: " << *BB->getTerminator() << '\n'); @@ -339,7 +345,8 @@ static Constant *getKnownConstant(Value *Val, ConstantPreference Preference) { /// bool JumpThreading:: ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, - ConstantPreference Preference) { + ConstantPreference Preference, + Instruction *CxtI) { // This method walks up use-def chains recursively. Because of this, we could // get into an infinite loop going around loops in the use-def chain. To // prevent this, keep track of what (value, block) pairs we've already visited @@ -381,7 +388,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, BasicBlock *P = *PI; // If the value is known by LazyValueInfo to be a constant in a // predecessor, use that information to try to thread this block. - Constant *PredCst = LVI->getConstantOnEdge(V, P, BB); + Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI); if (Constant *KC = getKnownConstant(PredCst, Preference)) Result.push_back(std::make_pair(KC, P)); } @@ -397,7 +404,8 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i))); } else { Constant *CI = LVI->getConstantOnEdge(InVal, - PN->getIncomingBlock(i), BB); + PN->getIncomingBlock(i), + BB, CxtI); if (Constant *KC = getKnownConstant(CI, Preference)) Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i))); } @@ -416,9 +424,9 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, if (I->getOpcode() == Instruction::Or || I->getOpcode() == Instruction::And) { ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, - WantInteger); + WantInteger, CxtI); ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals, - WantInteger); + WantInteger, CxtI); if (LHSVals.empty() && RHSVals.empty()) return false; @@ -459,7 +467,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, isa<ConstantInt>(I->getOperand(1)) && cast<ConstantInt>(I->getOperand(1))->isOne()) { ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result, - WantInteger); + WantInteger, CxtI); if (Result.empty()) return false; @@ -477,7 +485,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) { PredValueInfoTy LHSVals; ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals, - WantInteger); + WantInteger, CxtI); // Try to use constant folding to simplify the binary operator. for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { @@ -511,7 +519,8 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, LazyValueInfo::Tristate ResT = LVI->getPredicateOnEdge(Cmp->getPredicate(), LHS, - cast<Constant>(RHS), PredBB, BB); + cast<Constant>(RHS), PredBB, BB, + CxtI ? CxtI : Cmp); if (ResT == LazyValueInfo::Unknown) continue; Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT); @@ -524,7 +533,6 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, return !Result.empty(); } - // If comparing a live-in value against a constant, see if we know the // live-in value on any predecessors. if (isa<Constant>(Cmp->getOperand(1)) && Cmp->getType()->isIntegerTy()) { @@ -538,7 +546,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, // predecessor, use that information to try to thread this block. LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(Cmp->getPredicate(), Cmp->getOperand(0), - RHSCst, P, BB); + RHSCst, P, BB, CxtI ? CxtI : Cmp); if (Res == LazyValueInfo::Unknown) continue; @@ -554,7 +562,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, if (Constant *CmpConst = dyn_cast<Constant>(Cmp->getOperand(1))) { PredValueInfoTy LHSVals; ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, - WantInteger); + WantInteger, CxtI); for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { Constant *V = LHSVals[i].first; @@ -577,7 +585,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, PredValueInfoTy Conds; if ((TrueVal || FalseVal) && ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds, - WantInteger)) { + WantInteger, CxtI)) { for (unsigned i = 0, e = Conds.size(); i != e; ++i) { Constant *Cond = Conds[i].first; @@ -604,7 +612,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, } // If all else fails, see if LVI can figure out a constant value for us. - Constant *CI = LVI->getConstant(V, BB); + Constant *CI = LVI->getConstant(V, BB, CxtI); if (Constant *KC = getKnownConstant(CI, Preference)) { for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) Result.push_back(std::make_pair(KC, *PI)); @@ -654,7 +662,7 @@ static bool hasAddressTakenAndUsed(BasicBlock *BB) { bool JumpThreading::ProcessBlock(BasicBlock *BB) { // If the block is trivially dead, just return and let the caller nuke it. // This simplifies other transformations. - if (pred_begin(BB) == pred_end(BB) && + if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) return false; @@ -744,7 +752,7 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) { // All the rest of our checks depend on the condition being an instruction. if (!CondInst) { // FIXME: Unify this with code below. - if (ProcessThreadableEdges(Condition, BB, Preference)) + if (ProcessThreadableEdges(Condition, BB, Preference, Terminator)) return true; return false; } @@ -766,13 +774,14 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) { // FIXME: We could handle mixed true/false by duplicating code. LazyValueInfo::Tristate Baseline = LVI->getPredicateOnEdge(CondCmp->getPredicate(), CondCmp->getOperand(0), - CondConst, *PI, BB); + CondConst, *PI, BB, CondCmp); if (Baseline != LazyValueInfo::Unknown) { // Check that all remaining incoming values match the first one. while (++PI != PE) { LazyValueInfo::Tristate Ret = LVI->getPredicateOnEdge(CondCmp->getPredicate(), - CondCmp->getOperand(0), CondConst, *PI, BB); + CondCmp->getOperand(0), CondConst, *PI, BB, + CondCmp); if (Ret != Baseline) break; } @@ -787,6 +796,21 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) { } } + } else if (CondBr && CondConst && CondBr->isConditional()) { + // There might be an invariant in the same block with the conditional + // that can determine the predicate. + + LazyValueInfo::Tristate Ret = + LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0), + CondConst, CondCmp); + if (Ret != LazyValueInfo::Unknown) { + unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0; + unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1; + CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true); + BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr); + CondBr->eraseFromParent(); + return true; + } } if (CondBr && CondConst && TryToUnfoldSelect(CondCmp, BB)) @@ -814,7 +838,7 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) { // a PHI node in the current block. If we can prove that any predecessors // compute a predictable value based on a PHI node, thread those predecessors. // - if (ProcessThreadableEdges(CondInst, BB, Preference)) + if (ProcessThreadableEdges(CondInst, BB, Preference, Terminator)) return true; // If this is an otherwise-unfoldable branch on a phi node in the current @@ -877,6 +901,9 @@ bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { // If the returned value is the load itself, replace with an undef. This can // only happen in dead loops. if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType()); + if (AvailableVal->getType() != LI->getType()) + AvailableVal = + CastInst::CreateBitOrPointerCast(AvailableVal, LI->getType(), "", LI); LI->replaceAllUsesWith(AvailableVal); LI->eraseFromParent(); return true; @@ -888,9 +915,10 @@ bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { if (BBIt != LoadBB->begin()) return false; - // If all of the loads and stores that feed the value have the same TBAA tag, - // then we can propagate it onto any newly inserted loads. - MDNode *TBAATag = LI->getMetadata(LLVMContext::MD_tbaa); + // If all of the loads and stores that feed the value have the same AA tags, + // then we can propagate them onto any newly inserted loads. + AAMDNodes AATags; + LI->getAAMetadata(AATags); SmallPtrSet<BasicBlock*, 8> PredsScanned; typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy; @@ -904,21 +932,21 @@ bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { BasicBlock *PredBB = *PI; // If we already scanned this predecessor, skip it. - if (!PredsScanned.insert(PredBB)) + if (!PredsScanned.insert(PredBB).second) continue; // Scan the predecessor to see if the value is available in the pred. BBIt = PredBB->end(); - MDNode *ThisTBAATag = nullptr; + AAMDNodes ThisAATags; Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6, - nullptr, &ThisTBAATag); + nullptr, &ThisAATags); if (!PredAvailable) { OneUnavailablePred = PredBB; continue; } - // If tbaa tags disagree or are not present, forget about them. - if (TBAATag != ThisTBAATag) TBAATag = nullptr; + // If AA tags disagree or are not present, forget about them. + if (AATags != ThisAATags) AATags = AAMDNodes(); // If so, this load is partially redundant. Remember this info so that we // can create a PHI node. @@ -978,8 +1006,8 @@ bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { LI->getAlignment(), UnavailablePred->getTerminator()); NewVal->setDebugLoc(LI->getDebugLoc()); - if (TBAATag) - NewVal->setMetadata(LLVMContext::MD_tbaa, TBAATag); + if (AATags) + NewVal->setAAMetadata(AATags); AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal)); } @@ -1006,7 +1034,16 @@ bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { assert(I != AvailablePreds.end() && I->first == P && "Didn't find entry for predecessor!"); - PN->addIncoming(I->second, I->first); + // If we have an available predecessor but it requires casting, insert the + // cast in the predecessor and use the cast. Note that we have to update the + // AvailablePreds vector as we go so that all of the PHI entries for this + // predecessor use the same bitcast. + Value *&PredV = I->second; + if (PredV->getType() != LI->getType()) + PredV = CastInst::CreateBitOrPointerCast(PredV, LI->getType(), "", + P->getTerminator()); + + PN->addIncoming(PredV, I->first); } //cerr << "PRE: " << *LI << *PN << "\n"; @@ -1081,14 +1118,15 @@ FindMostPopularDest(BasicBlock *BB, } bool JumpThreading::ProcessThreadableEdges(Value *Cond, BasicBlock *BB, - ConstantPreference Preference) { + ConstantPreference Preference, + Instruction *CxtI) { // If threading this would thread across a loop header, don't even try to // thread the edge. if (LoopHeaders.count(BB)) return false; PredValueInfoTy PredValues; - if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference)) + if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference, CxtI)) return false; assert(!PredValues.empty() && @@ -1113,7 +1151,7 @@ bool JumpThreading::ProcessThreadableEdges(Value *Cond, BasicBlock *BB, for (unsigned i = 0, e = PredValues.size(); i != e; ++i) { BasicBlock *Pred = PredValues[i].second; - if (!SeenPreds.insert(Pred)) + if (!SeenPreds.insert(Pred).second) continue; // Duplicate predecessor entry. // If the predecessor ends with an indirect goto, we can't change its @@ -1253,10 +1291,10 @@ bool JumpThreading::ProcessBranchOnXOR(BinaryOperator *BO) { PredValueInfoTy XorOpValues; bool isLHS = true; if (!ComputeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues, - WantInteger)) { + WantInteger, BO)) { assert(XorOpValues.empty()); if (!ComputeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues, - WantInteger)) + WantInteger, BO)) return false; isLHS = false; } @@ -1366,8 +1404,8 @@ bool JumpThreading::ThreadEdge(BasicBlock *BB, return false; } - unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB, Threshold); - if (JumpThreadCost > Threshold) { + unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB, BBDupThreshold); + if (JumpThreadCost > BBDupThreshold) { DEBUG(dbgs() << " Not threading BB '" << BB->getName() << "' - Cost is too high: " << JumpThreadCost << "\n"); return false; @@ -1509,8 +1547,8 @@ bool JumpThreading::DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB, return false; } - unsigned DuplicationCost = getJumpThreadDuplicationCost(BB, Threshold); - if (DuplicationCost > Threshold) { + unsigned DuplicationCost = getJumpThreadDuplicationCost(BB, BBDupThreshold); + if (DuplicationCost > BBDupThreshold) { DEBUG(dbgs() << " Not duplicating BB '" << BB->getName() << "' - Cost is too high: " << DuplicationCost << "\n"); return false; @@ -1672,10 +1710,10 @@ bool JumpThreading::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { // cases will be threaded in any case. LazyValueInfo::Tristate LHSFolds = LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1), - CondRHS, Pred, BB); + CondRHS, Pred, BB, CondCmp); LazyValueInfo::Tristate RHSFolds = LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2), - CondRHS, Pred, BB); + CondRHS, Pred, BB, CondCmp); if ((LHSFolds != LazyValueInfo::Unknown || RHSFolds != LazyValueInfo::Unknown) && LHSFolds != RHSFolds) { |
