#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#include "llvm/Pass.h"
-#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
cl::desc("Max block size to duplicate for jump threading"),
cl::init(6), cl::Hidden);
+// Turn on use of LazyValueInfo.
+static cl::opt<bool>
+EnableLVI("enable-jump-threading-lvi", cl::ReallyHidden);
+
+
+
namespace {
/// This pass performs 'jump threading', which looks at blocks that have
/// multiple predecessors and multiple successors. If one or more of the
///
class JumpThreading : public FunctionPass {
TargetData *TD;
+ LazyValueInfo *LVI;
#ifdef NDEBUG
SmallPtrSet<BasicBlock*, 16> LoopHeaders;
#else
JumpThreading() : FunctionPass(&ID) {}
bool runOnFunction(Function &F);
- void FindLoopHeaders(Function &F);
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ if (EnableLVI)
+ AU.addRequired<LazyValueInfo>();
+ }
+
+ void FindLoopHeaders(Function &F);
bool ProcessBlock(BasicBlock *BB);
- bool ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB);
+ bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock*> &PredBBs,
+ BasicBlock *SuccBB);
bool DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB,
BasicBlock *PredBB);
- BasicBlock *FactorCommonPHIPreds(PHINode *PN, Value *Val);
typedef SmallVectorImpl<std::pair<ConstantInt*,
BasicBlock*> > PredValueInfo;
bool JumpThreading::runOnFunction(Function &F) {
DEBUG(errs() << "Jump threading on function '" << F.getName() << "'\n");
TD = getAnalysisIfAvailable<TargetData>();
+ LVI = EnableLVI ? &getAnalysis<LazyValueInfo>() : 0;
FindLoopHeaders(F);
bool Changed = false;
for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
BasicBlock *BB = I;
+ // Thread all of the branches we can over this block.
while (ProcessBlock(BB))
Changed = true;
LoopHeaders.erase(BB);
DeleteDeadBlock(BB);
Changed = true;
+ } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
+ // Can't thread an unconditional jump, but if the block is "almost
+ // empty", we can replace uses of it with uses of the successor and make
+ // this dead.
+ if (BI->isUnconditional() &&
+ BB != &BB->getParent()->getEntryBlock()) {
+ BasicBlock::iterator BBI = BB->getFirstNonPHI();
+ // Ignore dbg intrinsics.
+ while (isa<DbgInfoIntrinsic>(BBI))
+ ++BBI;
+ // If the terminator is the only non-phi instruction, try to nuke it.
+ if (BBI->isTerminator()) {
+ // Since TryToSimplifyUncondBranchFromEmptyBlock may delete the
+ // block, we have to make sure it isn't in the LoopHeaders set. We
+ // reinsert afterward in the rare case when the block isn't deleted.
+ bool ErasedFromLoopHeaders = LoopHeaders.erase(BB);
+
+ if (TryToSimplifyUncondBranchFromEmptyBlock(BB))
+ Changed = true;
+ else if (ErasedFromLoopHeaders)
+ LoopHeaders.insert(BB);
+ }
+ }
}
}
AnotherIteration = Changed;
/// Ignore PHI nodes, these will be flattened when duplication happens.
BasicBlock::const_iterator I = BB->getFirstNonPHI();
+ // FIXME: THREADING will delete values that are just used to compute the
+ // branch, so they shouldn't count against the duplication cost.
+
+
// Sum up the cost of each instruction until we get to the terminator. Don't
// include the terminator because the copy won't include it.
unsigned Size = 0;
return Size;
}
-
-
/// FindLoopHeaders - We do not want jump threading to turn proper loop
/// structures into irreducible loops. Doing this breaks up the loop nesting
/// hierarchy and pessimizes later transformations. To prevent this from
LoopHeaders.insert(const_cast<BasicBlock*>(Edges[i].second));
}
-
-/// FactorCommonPHIPreds - If there are multiple preds with the same incoming
-/// value for the PHI, factor them together so we get one block to thread for
-/// the whole group.
-/// This is important for things like "phi i1 [true, true, false, true, x]"
-/// where we only need to clone the block for the true blocks once.
-///
-BasicBlock *JumpThreading::FactorCommonPHIPreds(PHINode *PN, Value *Val) {
- SmallVector<BasicBlock*, 16> CommonPreds;
- for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
- if (PN->getIncomingValue(i) == Val)
- CommonPreds.push_back(PN->getIncomingBlock(i));
-
- if (CommonPreds.size() == 1)
- return CommonPreds[0];
-
- DEBUG(errs() << " Factoring out " << CommonPreds.size()
- << " common predecessors.\n");
- return SplitBlockPredecessors(PN->getParent(),
- &CommonPreds[0], CommonPreds.size(),
- ".thr_comm", this);
-}
-
-/// GetResultOfComparison - Given an icmp/fcmp predicate and the left and right
-/// hand sides of the compare instruction, try to determine the result. If the
-/// result can not be determined, a null pointer is returned.
-static Constant *GetResultOfComparison(CmpInst::Predicate pred,
- Value *LHS, Value *RHS) {
- if (Constant *CLHS = dyn_cast<Constant>(LHS))
- if (Constant *CRHS = dyn_cast<Constant>(RHS))
- return ConstantExpr::getCompare(pred, CLHS, CRHS);
-
- if (LHS == RHS)
- if (isa<IntegerType>(LHS->getType()) || isa<PointerType>(LHS->getType()))
- if (ICmpInst::isTrueWhenEqual(pred))
- return ConstantInt::getTrue(LHS->getContext());
- else
- return ConstantInt::getFalse(LHS->getContext());
- return 0;
-}
-
-
/// ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see
/// if we can infer that the value is a known ConstantInt in any of our
-/// predecessors. If so, return the known the list of value and pred BB in the
+/// predecessors. If so, return the known list of value and pred BB in the
/// result vector. If a value is known to be undef, it is returned as null.
///
-/// The BB basic block is known to start with a PHI node.
-///
/// This returns true if there were any known values.
///
-///
-/// TODO: Per PR2563, we could infer value range information about a predecessor
-/// based on its terminator.
bool JumpThreading::
ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){
- PHINode *TheFirstPHI = cast<PHINode>(BB->begin());
-
// If V is a constantint, then it is known in all predecessors.
if (isa<ConstantInt>(V) || isa<UndefValue>(V)) {
ConstantInt *CI = dyn_cast<ConstantInt>(V);
- Result.resize(TheFirstPHI->getNumIncomingValues());
- for (unsigned i = 0, e = Result.size(); i != e; ++i)
- Result[i] = std::make_pair(CI, TheFirstPHI->getIncomingBlock(i));
+
+ for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
+ Result.push_back(std::make_pair(CI, *PI));
return true;
}
// If V is a non-instruction value, or an instruction in a different block,
// then it can't be derived from a PHI.
Instruction *I = dyn_cast<Instruction>(V);
- if (I == 0 || I->getParent() != BB)
+ if (I == 0 || I->getParent() != BB) {
+
+ // Okay, if this is a live-in value, see if it has a known value at the end
+ // of any of our predecessors.
+ //
+ // FIXME: This should be an edge property, not a block end property.
+ /// TODO: Per PR2563, we could infer value range information about a
+ /// predecessor based on its terminator.
+ //
+ if (LVI) {
+ for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++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->getConstant(V, *PI);
+ if (PredCst == 0 ||
+ (!isa<ConstantInt>(PredCst) && !isa<UndefValue>(PredCst)))
+ continue;
+
+ Result.push_back(std::make_pair(dyn_cast<ConstantInt>(PredCst), *PI));
+ }
+
+ return !Result.empty();
+ }
+
return false;
+ }
/// If I is a PHI node, then we know the incoming values for any constants.
if (PHINode *PN = dyn_cast<PHINode>(I)) {
return !Result.empty();
}
- // TODO: Should handle the NOT form of XOR.
-
+ // Handle the NOT form of XOR.
+ if (I->getOpcode() == Instruction::Xor &&
+ isa<ConstantInt>(I->getOperand(1)) &&
+ cast<ConstantInt>(I->getOperand(1))->isOne()) {
+ ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result);
+ if (Result.empty())
+ return false;
+
+ // Invert the known values.
+ for (unsigned i = 0, e = Result.size(); i != e; ++i)
+ Result[i].first =
+ cast<ConstantInt>(ConstantExpr::getNot(Result[i].first));
+ return true;
+ }
}
// Handle compare with phi operand, where the PHI is defined in this block.
Value *LHS = PN->getIncomingValue(i);
Value *RHS = Cmp->getOperand(1)->DoPHITranslation(BB, PredBB);
- Constant *Res = GetResultOfComparison(Cmp->getPredicate(), LHS, RHS);
+ Value *Res = SimplifyCmpInst(Cmp->getPredicate(), LHS, RHS);
if (Res == 0) continue;
if (isa<UndefValue>(Res))
TerminatorInst *BBTerm = BB->getTerminator();
for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
if (i == BestSucc) continue;
- BBTerm->getSuccessor(i)->removePredecessor(BB);
+ RemovePredecessorAndSimplify(BBTerm->getSuccessor(i), BB, TD);
}
DEBUG(errs() << " In block '" << BB->getName()
// 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.
//
- // We only bother doing this if the current block has a PHI node and if the
- // conditional instruction lives in the current block. If either condition
- // fail, this won't be a computable value anyway.
- if (CondInst->getParent() == BB && isa<PHINode>(BB->front()))
- if (ProcessThreadableEdges(CondInst, BB))
- return true;
+ if (ProcessThreadableEdges(CondInst, BB))
+ return true;
// TODO: If we have: "br (X > 0)" and we have a predecessor where we know
// Next, figure out which successor we are threading to.
BasicBlock *SuccBB = DestBI->getSuccessor(!BranchDir);
+ SmallVector<BasicBlock*, 2> Preds;
+ Preds.push_back(PredBB);
+
// Ok, try to thread it!
- return ThreadEdge(BB, PredBB, SuccBB);
+ return ThreadEdge(BB, Preds, SuccBB);
}
/// ProcessSwitchOnDuplicateCond - We found a block and a predecessor of that
if (LoopHeaders.count(BB))
return false;
-
-
SmallVector<std::pair<ConstantInt*, BasicBlock*>, 8> PredValues;
if (!ComputeValueKnownInPredecessors(CondInst, BB, PredValues))
return false;
// Decide what we want to thread through. Convert our list of known values to
// a list of known destinations for each pred. This also discards duplicate
// predecessors and keeps track of the undefined inputs (which are represented
- // as a null dest in the PredToDestList.
+ // as a null dest in the PredToDestList).
SmallPtrSet<BasicBlock*, 16> SeenPreds;
SmallVector<std::pair<BasicBlock*, BasicBlock*>, 16> PredToDestList;
// predecessors that will jump to it into a single predecessor.
SmallVector<BasicBlock*, 16> PredsToFactor;
for (unsigned i = 0, e = PredToDestList.size(); i != e; ++i)
- if (PredToDestList[i].second == MostPopularDest)
- PredsToFactor.push_back(PredToDestList[i].first);
+ if (PredToDestList[i].second == MostPopularDest) {
+ BasicBlock *Pred = PredToDestList[i].first;
+
+ // This predecessor may be a switch or something else that has multiple
+ // edges to the block. Factor each of these edges by listing them
+ // according to # occurrences in PredsToFactor.
+ TerminatorInst *PredTI = Pred->getTerminator();
+ for (unsigned i = 0, e = PredTI->getNumSuccessors(); i != e; ++i)
+ if (PredTI->getSuccessor(i) == BB)
+ PredsToFactor.push_back(Pred);
+ }
- BasicBlock *PredToThread;
- if (PredsToFactor.size() == 1)
- PredToThread = PredsToFactor[0];
- else {
- DEBUG(errs() << " Factoring out " << PredsToFactor.size()
- << " common predecessors.\n");
- PredToThread = SplitBlockPredecessors(BB, &PredsToFactor[0],
- PredsToFactor.size(),
- ".thr_comm", this);
- }
-
// If the threadable edges are branching on an undefined value, we get to pick
// the destination that these predecessors should get to.
if (MostPopularDest == 0)
getSuccessor(GetBestDestForJumpOnUndef(BB));
// Ok, try to thread it!
- return ThreadEdge(BB, PredToThread, MostPopularDest);
+ return ThreadEdge(BB, PredsToFactor, MostPopularDest);
}
/// ProcessJumpOnPHI - We have a conditional branch or switch on a PHI node in
}
}
-/// ThreadEdge - We have decided that it is safe and profitable to thread an
-/// edge from PredBB to SuccBB across BB. Transform the IR to reflect this
-/// change.
-bool JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB,
+/// ThreadEdge - We have decided that it is safe and profitable to factor the
+/// blocks in PredBBs to one predecessor, then thread an edge from it to SuccBB
+/// across BB. Transform the IR to reflect this change.
+bool JumpThreading::ThreadEdge(BasicBlock *BB,
+ const SmallVectorImpl<BasicBlock*> &PredBBs,
BasicBlock *SuccBB) {
// If threading to the same block as we come from, we would infinite loop.
if (SuccBB == BB) {
// If threading this would thread across a loop header, don't thread the edge.
// See the comments above FindLoopHeaders for justifications and caveats.
if (LoopHeaders.count(BB)) {
- DEBUG(errs() << " Not threading from '" << PredBB->getName()
- << "' across loop header BB '" << BB->getName()
+ DEBUG(errs() << " Not threading across loop header BB '" << BB->getName()
<< "' to dest BB '" << SuccBB->getName()
<< "' - it might create an irreducible loop!\n");
return false;
return false;
}
+ // And finally, do it! Start by factoring the predecessors is needed.
+ BasicBlock *PredBB;
+ if (PredBBs.size() == 1)
+ PredBB = PredBBs[0];
+ else {
+ DEBUG(errs() << " Factoring out " << PredBBs.size()
+ << " common predecessors.\n");
+ PredBB = SplitBlockPredecessors(BB, &PredBBs[0], PredBBs.size(),
+ ".thr_comm", this);
+ }
+
// And finally, do it!
DEBUG(errs() << " Threading edge from '" << PredBB->getName() << "' to '"
<< SuccBB->getName() << "' with cost: " << JumpThreadCost
TerminatorInst *PredTerm = PredBB->getTerminator();
for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
if (PredTerm->getSuccessor(i) == BB) {
- BB->removePredecessor(PredBB);
+ RemovePredecessorAndSimplify(BB, PredBB, TD);
PredTerm->setSuccessor(i, NewBB);
}
BI = NewBB->begin();
for (BasicBlock::iterator E = NewBB->end(); BI != E; ) {
Instruction *Inst = BI++;
- if (Constant *C = ConstantFoldInstruction(Inst, TD)) {
- Inst->replaceAllUsesWith(C);
- Inst->eraseFromParent();
+
+ if (Value *V = SimplifyInstruction(Inst, TD)) {
+ WeakVH BIHandle(BI);
+ ReplaceAndSimplifyAllUses(Inst, V, TD);
+ if (BIHandle == 0)
+ BI = NewBB->begin();
continue;
}
// PredBB no longer jumps to BB, remove entries in the PHI node for the edge
// that we nuked.
- BB->removePredecessor(PredBB);
+ RemovePredecessorAndSimplify(BB, PredBB, TD);
// Remove the unconditional branch at the end of the PredBB block.
OldPredBranch->eraseFromParent();
projects / oota-llvm.git / blobdiff