#include "llvm/Pass.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Target/TargetData.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
/// revectored to the false side of the second if.
///
class VISIBILITY_HIDDEN JumpThreading : public FunctionPass {
+ TargetData *TD;
public:
static char ID; // Pass identification
JumpThreading() : FunctionPass(&ID) {}
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<TargetData>();
+ }
+
bool runOnFunction(Function &F);
bool ProcessBlock(BasicBlock *BB);
void ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB);
BasicBlock *FactorCommonPHIPreds(PHINode *PN, Constant *CstVal);
+ bool ProcessBranchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
+ bool ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
bool ProcessJumpOnPHI(PHINode *PN);
bool ProcessBranchOnLogical(Value *V, BasicBlock *BB, bool isAnd);
///
bool JumpThreading::runOnFunction(Function &F) {
DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
+ TD = &getAnalysis<TargetData>();
bool AnotherIteration = true, EverChanged = false;
while (AnotherIteration) {
AnotherIteration = false;
bool Changed = false;
- for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
- while (ProcessBlock(I))
+ for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
+ BasicBlock *BB = I;
+ while (ProcessBlock(BB))
+ Changed = true;
+
+ ++I;
+
+ // If the block is trivially dead, zap it. This eliminates the successor
+ // edges which simplifies the CFG.
+ if (pred_begin(BB) == pred_end(BB) &&
+ BB != &BB->getParent()->getEntryBlock()) {
+ DOUT << " JT: Deleting dead block '" << BB->getNameStart()
+ << "' with terminator: " << *BB->getTerminator();
+ DeleteDeadBlock(BB);
Changed = true;
+ }
+ }
AnotherIteration = Changed;
EverChanged |= Changed;
}
// because now the condition in this block can be threaded through
// predecessors of our predecessor block.
if (BasicBlock *SinglePred = BB->getSinglePredecessor())
- if (SinglePred->getTerminator()->getNumSuccessors() == 1) {
+ if (SinglePred->getTerminator()->getNumSuccessors() == 1 &&
+ SinglePred != BB) {
+ // 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();
MergeBasicBlockIntoOnlyPred(BB);
+
+ if (isEntry && BB != &BB->getParent()->getEntryBlock())
+ BB->moveBefore(&BB->getParent()->getEntryBlock());
return true;
}
return true;
}
+ // If the terminator is branching on an undef, we can pick any of the
+ // successors to branch to. Since this is arbitrary, we pick the successor
+ // with the fewest predecessors. This should reduce the in-degree of the
+ // others.
+ if (isa<UndefValue>(Condition)) {
+ TerminatorInst *BBTerm = BB->getTerminator();
+ unsigned MinSucc = 0;
+ BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc);
+ // Compute the successor with the minimum number of predecessors.
+ unsigned MinNumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
+ for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {
+ TestBB = BBTerm->getSuccessor(i);
+ unsigned NumPreds = std::distance(pred_begin(TestBB), pred_end(TestBB));
+ if (NumPreds < MinNumPreds)
+ MinSucc = i;
+ }
+
+ // Fold the branch/switch.
+ for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
+ if (i == MinSucc) continue;
+ BBTerm->getSuccessor(i)->removePredecessor(BB);
+ }
+
+ DOUT << " In block '" << BB->getNameStart()
+ << "' folding undef terminator: " << *BBTerm;
+ BranchInst::Create(BBTerm->getSuccessor(MinSucc), BBTerm);
+ BBTerm->eraseFromParent();
+ return true;
+ }
+
+ Instruction *CondInst = dyn_cast<Instruction>(Condition);
+
+ // If the condition is an instruction defined in another block, see if a
+ // predecessor has the same condition:
+ // br COND, BBX, BBY
+ // BBX:
+ // br COND, BBZ, BBW
+ if (!Condition->hasOneUse() && // Multiple uses.
+ (CondInst == 0 || CondInst->getParent() != BB)) { // Non-local definition.
+ pred_iterator PI = pred_begin(BB), E = pred_end(BB);
+ if (isa<BranchInst>(BB->getTerminator())) {
+ for (; PI != E; ++PI)
+ if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
+ if (PBI->isConditional() && PBI->getCondition() == Condition &&
+ ProcessBranchOnDuplicateCond(*PI, BB))
+ return true;
+ } else {
+ assert(isa<SwitchInst>(BB->getTerminator()) && "Unknown jump terminator");
+ for (; PI != E; ++PI)
+ if (SwitchInst *PSI = dyn_cast<SwitchInst>((*PI)->getTerminator()))
+ if (PSI->getCondition() == Condition &&
+ ProcessSwitchOnDuplicateCond(*PI, BB))
+ return true;
+ }
+ }
+
// If there is only a single predecessor of this block, nothing to fold.
if (BB->getSinglePredecessor())
return false;
-
+
+ // All the rest of our checks depend on the condition being an instruction.
+ if (CondInst == 0)
+ return false;
+
// See if this is a phi node in the current block.
- PHINode *PN = dyn_cast<PHINode>(Condition);
- if (PN && PN->getParent() == BB)
- return ProcessJumpOnPHI(PN);
+ if (PHINode *PN = dyn_cast<PHINode>(CondInst))
+ if (PN->getParent() == BB)
+ return ProcessJumpOnPHI(PN);
// If this is a conditional branch whose condition is and/or of a phi, try to
// simplify it.
- if (BinaryOperator *CondI = dyn_cast<BinaryOperator>(Condition)) {
- if ((CondI->getOpcode() == Instruction::And ||
- CondI->getOpcode() == Instruction::Or) &&
- isa<BranchInst>(BB->getTerminator()) &&
- ProcessBranchOnLogical(CondI, BB,
- CondI->getOpcode() == Instruction::And))
- return true;
- }
+ if ((CondInst->getOpcode() == Instruction::And ||
+ CondInst->getOpcode() == Instruction::Or) &&
+ isa<BranchInst>(BB->getTerminator()) &&
+ ProcessBranchOnLogical(CondInst, BB,
+ CondInst->getOpcode() == Instruction::And))
+ return true;
// If we have "br (phi != 42)" and the phi node has any constant values as
// operands, we can thread through this block.
- if (CmpInst *CondCmp = dyn_cast<CmpInst>(Condition))
+ if (CmpInst *CondCmp = dyn_cast<CmpInst>(CondInst))
if (isa<PHINode>(CondCmp->getOperand(0)) &&
isa<Constant>(CondCmp->getOperand(1)) &&
ProcessBranchOnCompare(CondCmp, BB))
//
// This is particularly important because reg2mem inserts loads and stores all
// over the place, and this blocks jump threading if we don't zap them.
- Value *SimplifyValue = Condition;
+ Value *SimplifyValue = CondInst;
if (CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
if (isa<Constant>(CondCmp->getOperand(1)))
SimplifyValue = CondCmp->getOperand(0);
return false;
}
-
-/// FindAvailableLoadedValue - Scan backwards from ScanFrom checking to see if
-/// we have the value at the memory address *Ptr locally available within a
-/// small number of instructions. If the value is available, return it.
+/// ProcessBranchOnDuplicateCond - We found a block and a predecessor of that
+/// block that jump on exactly the same condition. This means that we almost
+/// always know the direction of the edge in the DESTBB:
+/// PREDBB:
+/// br COND, DESTBB, BBY
+/// DESTBB:
+/// br COND, BBZ, BBW
///
-/// If not, return the iterator for the last validated instruction that the
-/// value would be live through. If we scanned the entire block, ScanFrom would
-/// be left at begin().
+/// If DESTBB has multiple predecessors, we can't just constant fold the branch
+/// in DESTBB, we have to thread over it.
+bool JumpThreading::ProcessBranchOnDuplicateCond(BasicBlock *PredBB,
+ BasicBlock *BB) {
+ BranchInst *PredBI = cast<BranchInst>(PredBB->getTerminator());
+
+ // If both successors of PredBB go to DESTBB, we don't know anything. We can
+ // fold the branch to an unconditional one, which allows other recursive
+ // simplifications.
+ bool BranchDir;
+ if (PredBI->getSuccessor(1) != BB)
+ BranchDir = true;
+ else if (PredBI->getSuccessor(0) != BB)
+ BranchDir = false;
+ else {
+ DOUT << " In block '" << PredBB->getNameStart()
+ << "' folding terminator: " << *PredBB->getTerminator();
+ ++NumFolds;
+ ConstantFoldTerminator(PredBB);
+ return true;
+ }
+
+ BranchInst *DestBI = cast<BranchInst>(BB->getTerminator());
+
+ // If the dest block has one predecessor, just fix the branch condition to a
+ // constant and fold it.
+ if (BB->getSinglePredecessor()) {
+ DOUT << " In block '" << BB->getNameStart()
+ << "' folding condition to '" << BranchDir << "': "
+ << *BB->getTerminator();
+ ++NumFolds;
+ DestBI->setCondition(ConstantInt::get(Type::Int1Ty, BranchDir));
+ ConstantFoldTerminator(BB);
+ return true;
+ }
+
+ // Otherwise we need to thread from PredBB to DestBB's successor which
+ // involves code duplication. Check to see if it is worth it.
+ unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
+ if (JumpThreadCost > Threshold) {
+ DOUT << " Not threading BB '" << BB->getNameStart()
+ << "' - Cost is too high: " << JumpThreadCost << "\n";
+ return false;
+ }
+
+ // Next, figure out which successor we are threading to.
+ BasicBlock *SuccBB = DestBI->getSuccessor(!BranchDir);
+
+ // If threading to the same block as we come from, we would infinite loop.
+ if (SuccBB == BB) {
+ DOUT << " Not threading BB '" << BB->getNameStart()
+ << "' - would thread to self!\n";
+ return false;
+ }
+
+ // And finally, do it!
+ DOUT << " Threading edge from '" << PredBB->getNameStart() << "' to '"
+ << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
+ << ", across block:\n "
+ << *BB << "\n";
+
+ ThreadEdge(BB, PredBB, SuccBB);
+ ++NumThreads;
+ return true;
+}
+
+/// ProcessSwitchOnDuplicateCond - We found a block and a predecessor of that
+/// block that switch on exactly the same condition. This means that we almost
+/// always know the direction of the edge in the DESTBB:
+/// PREDBB:
+/// switch COND [... DESTBB, BBY ... ]
+/// DESTBB:
+/// switch COND [... BBZ, BBW ]
///
-/// FIXME: Move this to transform utils and use from
-/// InstCombiner::visitLoadInst. It would also be nice to optionally take AA so
-/// that GVN could do this.
-static Value *FindAvailableLoadedValue(Value *Ptr,
- BasicBlock *ScanBB,
- BasicBlock::iterator &ScanFrom) {
-
- unsigned NumToScan = 6;
- while (ScanFrom != ScanBB->begin()) {
- // Don't scan huge blocks.
- if (--NumToScan == 0) return 0;
-
- Instruction *Inst = --ScanFrom;
-
- // If this is a load of Ptr, the loaded value is available.
- if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
- if (LI->getOperand(0) == Ptr)
- return LI;
-
- if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
- // If this is a store through Ptr, the value is available!
- if (SI->getOperand(1) == Ptr)
- return SI->getOperand(0);
-
- // If Ptr is an alloca and this is a store to a different alloca, ignore
- // the store. This is a trivial form of alias analysis that is important
- // for reg2mem'd code.
- if ((isa<AllocaInst>(Ptr) || isa<GlobalVariable>(Ptr)) &&
- (isa<AllocaInst>(SI->getOperand(1)) ||
- isa<GlobalVariable>(SI->getOperand(1))))
- continue;
+/// Optimizing switches like this is very important, because simplifycfg builds
+/// switches out of repeated 'if' conditions.
+bool JumpThreading::ProcessSwitchOnDuplicateCond(BasicBlock *PredBB,
+ BasicBlock *DestBB) {
+ SwitchInst *PredSI = cast<SwitchInst>(PredBB->getTerminator());
+ SwitchInst *DestSI = cast<SwitchInst>(DestBB->getTerminator());
+
+ // There are a variety of optimizations that we can potentially do on these
+ // blocks: we order them from most to least preferable.
+
+ // If DESTBB *just* contains the switch, then we can forward edges from PREDBB
+ // directly to their destination. This does not introduce *any* code size
+ // growth.
+
+ // FIXME: Thread if it just contains a PHI.
+ if (isa<SwitchInst>(DestBB->begin())) {
+ bool MadeChange = false;
+ // Ignore the default edge for now.
+ for (unsigned i = 1, e = DestSI->getNumSuccessors(); i != e; ++i) {
+ ConstantInt *DestVal = DestSI->getCaseValue(i);
+ BasicBlock *DestSucc = DestSI->getSuccessor(i);
- // Otherwise the store that may or may not alias the pointer, bail out.
- ++ScanFrom;
- return 0;
+ // Okay, DestSI has a case for 'DestVal' that goes to 'DestSucc'. See if
+ // PredSI has an explicit case for it. If so, forward. If it is covered
+ // by the default case, we can't update PredSI.
+ unsigned PredCase = PredSI->findCaseValue(DestVal);
+ if (PredCase == 0) continue;
+
+ // If PredSI doesn't go to DestBB on this value, then it won't reach the
+ // case on this condition.
+ if (PredSI->getSuccessor(PredCase) != DestBB &&
+ DestSI->getSuccessor(i) != DestBB)
+ 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.
+ DOUT << "FORWARDING EDGE " << *DestVal << " FROM: " << *PredSI;
+ DOUT << "THROUGH: " << *DestSI;
+
+ // If the destination has PHI nodes, just split the edge for updating
+ // simplicity.
+ if (isa<PHINode>(DestSucc->begin()) && !DestSucc->getSinglePredecessor()){
+ SplitCriticalEdge(DestSI, i, this);
+ DestSucc = DestSI->getSuccessor(i);
+ }
+ FoldSingleEntryPHINodes(DestSucc);
+ PredSI->setSuccessor(PredCase, DestSucc);
+ MadeChange = true;
}
-
- // If this is some other instruction that may clobber Ptr, bail out.
- if (Inst->mayWriteToMemory()) {
- // May modify the pointer, bail out.
- ++ScanFrom;
- return 0;
- }
+ if (MadeChange)
+ return true;
}
- // Got to the start of the block, we didn't find it, but are done for this
- // block.
- return 0;
+ return false;
}
// the entry to its block.
BasicBlock::iterator BBIt = LI;
- if (Value *AvailableVal = FindAvailableLoadedValue(LoadedPtr, LoadBB, BBIt)) {
+ 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";
// Scan the predecessor to see if the value is available in the pred.
BBIt = PredBB->end();
- Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt);
+ Value *PredAvailable = FindAvailableLoadedValue(LoadedPtr, PredBB, BBIt, 6);
if (!PredAvailable) {
OneUnavailablePred = PredBB;
continue;
// Now we know that each predecessor of this block has a value in
// AvailablePreds, sort them for efficient access as we're walking the preds.
- std::sort(AvailablePreds.begin(), AvailablePreds.end());
+ array_pod_sort(AvailablePreds.begin(), AvailablePreds.end());
// Create a PHI node at the start of the block for the PRE'd load value.
PHINode *PN = PHINode::Create(LI->getType(), "", LoadBB->begin());
PN->addIncoming(IV, NewBB);
}
- // Finally, NewBB is good to go. Update the terminator of PredBB to jump to
+ // Ok, NewBB is good to go. Update the terminator of PredBB to jump to
// NewBB instead of BB. This eliminates predecessors from BB, which requires
// us to simplify any PHI nodes in BB.
TerminatorInst *PredTerm = PredBB->getTerminator();
BB->removePredecessor(PredBB);
PredTerm->setSuccessor(i, NewBB);
}
+
+ // At this point, the IR is fully up to date and consistent. Do a quick scan
+ // over the new instructions and zap any that are constants or dead. This
+ // frequently happens because of phi translation.
+ 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();
+ continue;
+ }
+
+ RecursivelyDeleteTriviallyDeadInstructions(Inst);
+ }
}
projects / oota-llvm.git / blobdiff