#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Target/TargetData.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
static cl::opt<bool>
EnableLVI("enable-jump-threading-lvi",
cl::desc("Use LVI for jump threading"),
- cl::init(false),
+ cl::init(true),
cl::ReallyHidden);
#else
SmallSet<AssertingVH<BasicBlock>, 16> LoopHeaders;
#endif
+ DenseSet<std::pair<Value*, BasicBlock*> > RecursionSet;
public:
static char ID; // Pass identification
JumpThreading() : FunctionPass(ID) {}
DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName()
<< "' with terminator: " << *BB->getTerminator() << '\n');
LoopHeaders.erase(BB);
+ if (LVI) LVI->eraseBlock(BB);
DeleteDeadBlock(BB);
Changed = true;
} else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
bool ErasedFromLoopHeaders = LoopHeaders.erase(BB);
BasicBlock *Succ = BI->getSuccessor(0);
+ // FIXME: It is always conservatively correct to drop the info
+ // for a block even if it doesn't get erased. This isn't totally
+ // awesome, but it allows us to use AssertingVH to prevent nasty
+ // dangling pointer issues within LazyValueInfo.
+ if (LVI) LVI->eraseBlock(BB);
if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) {
Changed = true;
// If we deleted BB and BB was the header of a loop, then the
///
bool JumpThreading::
ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){
+ if (!RecursionSet.insert(std::make_pair(V, BB)).second)
+ return false;
+
// 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);
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
Result.push_back(std::make_pair(CI, *PI));
+
+ RecursionSet.erase(std::make_pair(V, BB));
return true;
}
Result.push_back(std::make_pair(dyn_cast<ConstantInt>(PredCst), P));
}
+ RecursionSet.erase(std::make_pair(V, BB));
return !Result.empty();
}
+ RecursionSet.erase(std::make_pair(V, BB));
return false;
}
if (isa<ConstantInt>(InVal) || isa<UndefValue>(InVal)) {
ConstantInt *CI = dyn_cast<ConstantInt>(InVal);
Result.push_back(std::make_pair(CI, PN->getIncomingBlock(i)));
+ } else if (LVI) {
+ Constant *CI = LVI->getConstantOnEdge(InVal,
+ PN->getIncomingBlock(i), BB);
+ // LVI returns null is no value could be determined.
+ if (!CI) continue;
+ if (ConstantInt *CInt = dyn_cast<ConstantInt>(CI))
+ Result.push_back(std::make_pair(CInt, PN->getIncomingBlock(i)));
+ else if (isa<UndefValue>(CI))
+ Result.push_back(std::make_pair((ConstantInt*)0,
+ PN->getIncomingBlock(i)));
}
}
+
+ RecursionSet.erase(std::make_pair(V, BB));
return !Result.empty();
}
ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals);
ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals);
- if (LHSVals.empty() && RHSVals.empty())
+ if (LHSVals.empty() && RHSVals.empty()) {
+ RecursionSet.erase(std::make_pair(V, BB));
return false;
+ }
ConstantInt *InterestingVal;
if (I->getOpcode() == Instruction::Or)
Result.back().first = InterestingVal;
}
}
+
+ RecursionSet.erase(std::make_pair(V, BB));
return !Result.empty();
}
isa<ConstantInt>(I->getOperand(1)) &&
cast<ConstantInt>(I->getOperand(1))->isOne()) {
ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result);
- if (Result.empty())
+ if (Result.empty()) {
+ RecursionSet.erase(std::make_pair(V, BB));
return false;
+ }
// Invert the known values.
for (unsigned i = 0, e = Result.size(); i != e; ++i)
if (Result[i].first)
Result[i].first =
cast<ConstantInt>(ConstantExpr::getNot(Result[i].first));
+
+ RecursionSet.erase(std::make_pair(V, BB));
return true;
}
+
+ // Try to simplify some other binary operator values.
+ } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
+ ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1));
+ if (CI) {
+ SmallVector<std::pair<ConstantInt*, BasicBlock*>, 8> LHSVals;
+ ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals);
+
+ // Try to use constant folding to simplify the binary operator.
+ for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) {
+ Constant *Folded = 0;
+ if (LHSVals[i].first == 0) {
+ Folded = ConstantExpr::get(BO->getOpcode(),
+ UndefValue::get(BO->getType()),
+ CI);
+ } else {
+ Folded = ConstantExpr::get(BO->getOpcode(), LHSVals[i].first, CI);
+ }
+
+ if (ConstantInt *FoldedCInt = dyn_cast<ConstantInt>(Folded))
+ Result.push_back(std::make_pair(FoldedCInt, LHSVals[i].second));
+ else if (isa<UndefValue>(Folded))
+ Result.push_back(std::make_pair((ConstantInt*)0, LHSVals[i].second));
+ }
+ }
+
+ RecursionSet.erase(std::make_pair(V, BB));
+ return !Result.empty();
}
// Handle compare with phi operand, where the PHI is defined in this block.
Result.push_back(std::make_pair(CI, PredBB));
}
+ RecursionSet.erase(std::make_pair(V, BB));
return !Result.empty();
}
// If comparing a live-in value against a constant, see if we know the
// live-in value on any predecessors.
if (LVI && isa<Constant>(Cmp->getOperand(1)) &&
- Cmp->getType()->isIntegerTy() && // Not vector compare.
- (!isa<Instruction>(Cmp->getOperand(0)) ||
- cast<Instruction>(Cmp->getOperand(0))->getParent() != BB)) {
- Constant *RHSCst = cast<Constant>(Cmp->getOperand(1));
+ Cmp->getType()->isIntegerTy()) {
+ if (!isa<Instruction>(Cmp->getOperand(0)) ||
+ cast<Instruction>(Cmp->getOperand(0))->getParent() != BB) {
+ Constant *RHSCst = cast<Constant>(Cmp->getOperand(1));
+
+ for (pred_iterator PI = pred_begin(BB), E = pred_end(BB);PI != E; ++PI){
+ 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.
+ LazyValueInfo::Tristate Res =
+ LVI->getPredicateOnEdge(Cmp->getPredicate(), Cmp->getOperand(0),
+ RHSCst, P, BB);
+ if (Res == LazyValueInfo::Unknown)
+ continue;
- for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
- 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.
- LazyValueInfo::Tristate
- Res = LVI->getPredicateOnEdge(Cmp->getPredicate(), Cmp->getOperand(0),
- RHSCst, P, BB);
- if (Res == LazyValueInfo::Unknown)
- continue;
+ Constant *ResC = ConstantInt::get(Cmp->getType(), Res);
+ Result.push_back(std::make_pair(cast<ConstantInt>(ResC), P));
+ }
- Constant *ResC = ConstantInt::get(Cmp->getType(), Res);
- Result.push_back(std::make_pair(cast<ConstantInt>(ResC), P));
+ RecursionSet.erase(std::make_pair(V, BB));
+ return !Result.empty();
}
-
- return !Result.empty();
+
+ // Try to find a constant value for the LHS of a comparison,
+ // and evaluate it statically if we can.
+ if (Constant *CmpConst = dyn_cast<Constant>(Cmp->getOperand(1))) {
+ SmallVector<std::pair<ConstantInt*, BasicBlock*>, 8> LHSVals;
+ ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals);
+
+ for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) {
+ Constant * Folded = 0;
+ if (LHSVals[i].first == 0)
+ Folded = ConstantExpr::getCompare(Cmp->getPredicate(),
+ UndefValue::get(CmpConst->getType()), CmpConst);
+ else
+ Folded = ConstantExpr::getCompare(Cmp->getPredicate(),
+ LHSVals[i].first, CmpConst);
+
+ if (ConstantInt *FoldedCInt = dyn_cast<ConstantInt>(Folded))
+ Result.push_back(std::make_pair(FoldedCInt, LHSVals[i].second));
+ else if (isa<UndefValue>(Folded))
+ Result.push_back(std::make_pair((ConstantInt*)0,LHSVals[i].second));
+ }
+
+ RecursionSet.erase(std::make_pair(V, BB));
+ return !Result.empty();
+ }
+ }
+ }
+
+ if (LVI) {
+ // If all else fails, see if LVI can figure out a constant value for us.
+ Constant *CI = LVI->getConstant(V, BB);
+ ConstantInt *CInt = dyn_cast_or_null<ConstantInt>(CI);
+ if (CInt) {
+ for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
+ Result.push_back(std::make_pair(CInt, *PI));
}
+
+ RecursionSet.erase(std::make_pair(V, BB));
+ return !Result.empty();
}
+
+ RecursionSet.erase(std::make_pair(V, BB));
return false;
}
// Remember if SinglePred was the entry block of the function. If so, we
// will need to move BB back to the entry position.
bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
+ if (LVI) LVI->eraseBlock(SinglePred);
MergeBasicBlockIntoOnlyPred(BB);
if (isEntry && BB != &BB->getParent()->getEntryBlock())
}
}
}
+
+ // For a comparison where the LHS is outside this block, it's possible
+ // that we've branched on it before. Used LVI to see if we can simplify
+ // the branch based on that.
+ BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
+ Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1));
+ if (LVI && CondBr && CondConst && CondBr->isConditional() &&
+ (!isa<Instruction>(CondCmp->getOperand(0)) ||
+ cast<Instruction>(CondCmp->getOperand(0))->getParent() != BB)) {
+ // For predecessor edge, determine if the comparison is true or false
+ // on that edge. If they're all true or all false, we can simplify the
+ // branch.
+ // FIXME: We could handle mixed true/false by duplicating code.
+ unsigned Trues = 0, Falses = 0, predcount = 0;
+ for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);PI != PE; ++PI){
+ ++predcount;
+ LazyValueInfo::Tristate Ret =
+ LVI->getPredicateOnEdge(CondCmp->getPredicate(),
+ CondCmp->getOperand(0), CondConst, *PI, BB);
+ if (Ret == LazyValueInfo::True)
+ ++Trues;
+ else if (Ret == LazyValueInfo::False)
+ ++Falses;
+ }
+
+ // If we can determine the branch direction statically, convert
+ // the conditional branch to an unconditional one.
+ if (Trues && Trues == predcount) {
+ RemovePredecessorAndSimplify(CondBr->getSuccessor(1), BB, TD);
+ BranchInst::Create(CondBr->getSuccessor(0), CondBr);
+ CondBr->eraseFromParent();
+ return true;
+ } else if (Falses && Falses == predcount) {
+ RemovePredecessorAndSimplify(CondBr->getSuccessor(0), BB, TD);
+ BranchInst::Create(CondBr->getSuccessor(1), CondBr);
+ CondBr->eraseFromParent();
+ return true;
+ }
+ }
}
// Check for some cases that are worth simplifying. Right now we want to look
return false;
SmallVector<std::pair<ConstantInt*, BasicBlock*>, 8> PredValues;
- if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues))
+ if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues)) {
return false;
+ }
assert(!PredValues.empty() &&
"ComputeValueKnownInPredecessors returned true with no values");
OSDN Git Service
