#include "llvm/ADT/SmallSet.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
/// runOnFunction - Top level algorithm.
///
bool JumpThreading::runOnFunction(Function &F) {
- DEBUG(errs() << "Jump threading on function '" << F.getName() << "'\n");
+ DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
TD = getAnalysisIfAvailable<TargetData>();
LVI = EnableLVI ? &getAnalysis<LazyValueInfo>() : 0;
// edges which simplifies the CFG.
if (pred_begin(BB) == pred_end(BB) &&
BB != &BB->getParent()->getEntryBlock()) {
- DEBUG(errs() << " JT: Deleting dead block '" << BB->getName()
+ DEBUG(dbgs() << " JT: Deleting dead block '" << BB->getName()
<< "' with terminator: " << *BB->getTerminator() << '\n');
LoopHeaders.erase(BB);
DeleteDeadBlock(BB);
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.
+ // reinsert afterward if needed.
bool ErasedFromLoopHeaders = LoopHeaders.erase(BB);
+ BasicBlock *Succ = BI->getSuccessor(0);
- if (TryToSimplifyUncondBranchFromEmptyBlock(BB))
+ if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) {
Changed = true;
- else if (ErasedFromLoopHeaders)
+ // If we deleted BB and BB was the header of a loop, then the
+ // successor is now the header of the loop.
+ BB = Succ;
+ }
+
+ if (ErasedFromLoopHeaders)
LoopHeaders.insert(BB);
}
}
/// predecessor based on its terminator.
//
if (LVI) {
+ // FIXME: change this to use the more-rich 'getPredicateOnEdge' method if
+ // "I" is a non-local compare-with-a-constant instruction. This would be
+ // able to handle value inequalities better, for example if the compare is
+ // "X < 4" and "X < 3" is known true but "X < 4" itself is not available.
+ // Perhaps getConstantOnEdge should be smart enough to do this?
+
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.
// Invert the known values.
for (unsigned i = 0, e = Result.size(); i != e; ++i)
- Result[i].first =
- cast<ConstantInt>(ConstantExpr::getNot(Result[i].first));
+ if (Result[i].first)
+ Result[i].first =
+ cast<ConstantInt>(ConstantExpr::getNot(Result[i].first));
return true;
}
}
Value *RHS = Cmp->getOperand(1)->DoPHITranslation(BB, PredBB);
Value *Res = SimplifyCmpInst(Cmp->getPredicate(), LHS, RHS, TD);
- if (Res == 0) continue;
+ if (Res == 0) {
+ if (!LVI || !isa<Constant>(RHS))
+ continue;
+
+ LazyValueInfo::Tristate
+ ResT = LVI->getPredicateOnEdge(Cmp->getPredicate(), LHS,
+ cast<Constant>(RHS), PredBB, BB);
+ if (ResT == LazyValueInfo::Unknown)
+ continue;
+ Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT);
+ }
if (isa<UndefValue>(Res))
Result.push_back(std::make_pair((ConstantInt*)0, PredBB));
// terminator to an unconditional branch. This can occur due to threading in
// other blocks.
if (isa<ConstantInt>(Condition)) {
- DEBUG(errs() << " In block '" << BB->getName()
+ DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folding terminator: " << *BB->getTerminator() << '\n');
++NumFolds;
ConstantFoldTerminator(BB);
RemovePredecessorAndSimplify(BBTerm->getSuccessor(i), BB, TD);
}
- DEBUG(errs() << " In block '" << BB->getName()
+ DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folding undef terminator: " << *BBTerm << '\n');
BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
BBTerm->eraseFromParent();
if (isa<Constant>(CondCmp->getOperand(1)))
SimplifyValue = CondCmp->getOperand(0);
+ // TODO: There are other places where load PRE would be profitable, such as
+ // more complex comparisons.
if (LoadInst *LI = dyn_cast<LoadInst>(SimplifyValue))
if (SimplifyPartiallyRedundantLoad(LI))
return true;
else if (PredBI->getSuccessor(0) != BB)
BranchDir = false;
else {
- DEBUG(errs() << " In block '" << PredBB->getName()
+ DEBUG(dbgs() << " In block '" << PredBB->getName()
<< "' folding terminator: " << *PredBB->getTerminator() << '\n');
++NumFolds;
ConstantFoldTerminator(PredBB);
// If the dest block has one predecessor, just fix the branch condition to a
// constant and fold it.
if (BB->getSinglePredecessor()) {
- DEBUG(errs() << " In block '" << BB->getName()
+ DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folding condition to '" << BranchDir << "': "
<< *BB->getTerminator() << '\n');
++NumFolds;
if (PredSI->getSuccessor(PredCase) != DestBB &&
DestSI->getSuccessor(i) != DestBB)
continue;
+
+ // Do not forward this if it already goes to this destination, this would
+ // be an infinite loop.
+ if (PredSI->getSuccessor(PredCase) == DestSucc)
+ continue;
// Otherwise, we're safe to make the change. Make sure that the edge from
// DestSI to DestSucc is not critical and has no PHI nodes.
- DEBUG(errs() << "FORWARDING EDGE " << *DestVal << " FROM: " << *PredSI);
- DEBUG(errs() << "THROUGH: " << *DestSI);
+ DEBUG(dbgs() << "FORWARDING EDGE " << *DestVal << " FROM: " << *PredSI);
+ DEBUG(dbgs() << "THROUGH: " << *DestSI);
// If the destination has PHI nodes, just split the edge for updating
// simplicity.
Value *LoadedPtr = LI->getOperand(0);
// If the loaded operand is defined in the LoadBB, it can't be available.
- // FIXME: Could do PHI translation, that would be fun :)
+ // TODO: Could do simple PHI translation, that would be fun :)
if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
if (PtrOp->getParent() == LoadBB)
return false;
// the entry to its block.
BasicBlock::iterator BBIt = LI;
- if (Value *AvailableVal = FindAvailableLoadedValue(LoadedPtr, LoadBB,
- BBIt, 6)) {
+ if (Value *AvailableVal =
+ FindAvailableLoadedValue(LoadedPtr, LoadBB, BBIt, 6)) {
// If the value if the load is locally available within the block, just use
// it. This frequently occurs for reg2mem'd allocas.
//cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n";
// Split them out to their own block.
UnavailablePred =
SplitBlockPredecessors(LoadBB, &PredsToSplit[0], PredsToSplit.size(),
- "thread-split", this);
+ "thread-pre-split", this);
}
// If the value isn't available in all predecessors, then there will be
if (UnavailablePred) {
assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
"Can't handle critical edge here!");
- Value *NewVal = new LoadInst(LoadedPtr, LI->getName()+".pr",
+ Value *NewVal = new LoadInst(LoadedPtr, LI->getName()+".pr", false,
+ LI->getAlignment(),
UnavailablePred->getTerminator());
AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal));
}
assert(!PredValues.empty() &&
"ComputeValueKnownInPredecessors returned true with no values");
- DEBUG(errs() << "IN BB: " << *BB;
+ DEBUG(dbgs() << "IN BB: " << *BB;
for (unsigned i = 0, e = PredValues.size(); i != e; ++i) {
- errs() << " BB '" << BB->getName() << "': FOUND condition = ";
+ dbgs() << " BB '" << BB->getName() << "': FOUND condition = ";
if (PredValues[i].first)
- errs() << *PredValues[i].first;
+ dbgs() << *PredValues[i].first;
else
- errs() << "UNDEF";
- errs() << " for pred '" << PredValues[i].second->getName()
+ dbgs() << "UNDEF";
+ dbgs() << " for pred '" << PredValues[i].second->getName()
<< "'.\n";
});
BasicBlock *SuccBB) {
// If threading to the same block as we come from, we would infinite loop.
if (SuccBB == BB) {
- DEBUG(errs() << " Not threading across BB '" << BB->getName()
+ DEBUG(dbgs() << " Not threading across BB '" << BB->getName()
<< "' - would thread to self!\n");
return false;
}
// 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 across loop header BB '" << BB->getName()
+ DEBUG(dbgs() << " Not threading across loop header BB '" << BB->getName()
<< "' to dest BB '" << SuccBB->getName()
<< "' - it might create an irreducible loop!\n");
return false;
unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
if (JumpThreadCost > Threshold) {
- DEBUG(errs() << " Not threading BB '" << BB->getName()
+ DEBUG(dbgs() << " Not threading BB '" << BB->getName()
<< "' - Cost is too high: " << JumpThreadCost << "\n");
return false;
}
if (PredBBs.size() == 1)
PredBB = PredBBs[0];
else {
- DEBUG(errs() << " Factoring out " << PredBBs.size()
+ DEBUG(dbgs() << " 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 '"
+ DEBUG(dbgs() << " Threading edge from '" << PredBB->getName() << "' to '"
<< SuccBB->getName() << "' with cost: " << JumpThreadCost
<< ", across block:\n "
<< *BB << "\n");
if (UsesToRename.empty())
continue;
- DEBUG(errs() << "JT: Renaming non-local uses of: " << *I << "\n");
+ DEBUG(dbgs() << "JT: Renaming non-local uses of: " << *I << "\n");
// We found a use of I outside of BB. Rename all uses of I that are outside
// its block to be uses of the appropriate PHI node etc. See ValuesInBlocks
while (!UsesToRename.empty())
SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
- DEBUG(errs() << "\n");
+ DEBUG(dbgs() << "\n");
}
// cause us to transform this into an irreducible loop, don't do this.
// See the comments above FindLoopHeaders for justifications and caveats.
if (LoopHeaders.count(BB)) {
- DEBUG(errs() << " Not duplicating loop header '" << BB->getName()
+ DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName()
<< "' into predecessor block '" << PredBB->getName()
<< "' - it might create an irreducible loop!\n");
return false;
unsigned DuplicationCost = getJumpThreadDuplicationCost(BB);
if (DuplicationCost > Threshold) {
- DEBUG(errs() << " Not duplicating BB '" << BB->getName()
+ DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()
<< "' - Cost is too high: " << DuplicationCost << "\n");
return false;
}
// Okay, we decided to do this! Clone all the instructions in BB onto the end
// of PredBB.
- DEBUG(errs() << " Duplicating block '" << BB->getName() << "' into end of '"
+ DEBUG(dbgs() << " Duplicating block '" << BB->getName() << "' into end of '"
<< PredBB->getName() << "' to eliminate branch on phi. Cost: "
<< DuplicationCost << " block is:" << *BB << "\n");
if (UsesToRename.empty())
continue;
- DEBUG(errs() << "JT: Renaming non-local uses of: " << *I << "\n");
+ DEBUG(dbgs() << "JT: Renaming non-local uses of: " << *I << "\n");
// We found a use of I outside of BB. Rename all uses of I that are outside
// its block to be uses of the appropriate PHI node etc. See ValuesInBlocks
while (!UsesToRename.empty())
SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
- DEBUG(errs() << "\n");
+ DEBUG(dbgs() << "\n");
}
// PredBB no longer jumps to BB, remove entries in the PHI node for the edge