//===- TailDuplication.cpp - Simplify CFG through tail duplication --------===// // // The LLVM Compiler Infrastructure // // This file was developed by the LLVM research group and is distributed under // the University of Illinois Open Source License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This pass performs a limited form of tail duplication, intended to simplify // CFGs by removing some unconditional branches. This pass is necessary to // straighten out loops created by the C front-end, but also is capable of // making other code nicer. After this pass is run, the CFG simplify pass // should be run to clean up the mess. // // This pass could be enhanced in the future to use profile information to be // more aggressive. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar.h" #include "llvm/Constant.h" #include "llvm/Function.h" #include "llvm/iPHINode.h" #include "llvm/iTerminators.h" #include "llvm/Pass.h" #include "llvm/Type.h" #include "llvm/Support/CFG.h" #include "llvm/Support/ValueHolder.h" #include "llvm/Transforms/Utils/Local.h" #include "Support/Debug.h" #include "Support/Statistic.h" using namespace llvm; namespace { Statistic<> NumEliminated("tailduplicate", "Number of unconditional branches eliminated"); Statistic<> NumPHINodes("tailduplicate", "Number of phi nodes inserted"); class TailDup : public FunctionPass { bool runOnFunction(Function &F); private: inline bool shouldEliminateUnconditionalBranch(TerminatorInst *TI); inline bool canEliminateUnconditionalBranch(TerminatorInst *TI); inline void eliminateUnconditionalBranch(BranchInst *BI); inline void InsertPHINodesIfNecessary(Instruction *OrigInst, Value *NewInst, BasicBlock *NewBlock); inline Value *GetValueInBlock(BasicBlock *BB, Value *OrigVal, std::map &ValueMap, std::map &OutValueMap); inline Value *GetValueOutBlock(BasicBlock *BB, Value *OrigVal, std::map &ValueMap, std::map &OutValueMap); }; RegisterOpt X("tailduplicate", "Tail Duplication"); } // Public interface to the Tail Duplication pass Pass *llvm::createTailDuplicationPass() { return new TailDup(); } /// runOnFunction - Top level algorithm - Loop over each unconditional branch in /// the function, eliminating it if it looks attractive enough. /// bool TailDup::runOnFunction(Function &F) { bool Changed = false; for (Function::iterator I = F.begin(), E = F.end(); I != E; ) if (shouldEliminateUnconditionalBranch(I->getTerminator()) && canEliminateUnconditionalBranch(I->getTerminator())) { eliminateUnconditionalBranch(cast(I->getTerminator())); Changed = true; } else { ++I; } return Changed; } /// shouldEliminateUnconditionalBranch - Return true if this branch looks /// attractive to eliminate. We eliminate the branch if the destination basic /// block has <= 5 instructions in it, not counting PHI nodes. In practice, /// since one of these is a terminator instruction, this means that we will add /// up to 4 instructions to the new block. /// /// We don't count PHI nodes in the count since they will be removed when the /// contents of the block are copied over. /// bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI) { BranchInst *BI = dyn_cast(TI); if (!BI || !BI->isUnconditional()) return false; // Not an uncond branch! BasicBlock *Dest = BI->getSuccessor(0); if (Dest == BI->getParent()) return false; // Do not loop infinitely! // Do not inline a block if we will just get another branch to the same block! if (BranchInst *DBI = dyn_cast(Dest->getTerminator())) if (DBI->isUnconditional() && DBI->getSuccessor(0) == Dest) return false; // Do not loop infinitely! // Do not bother working on dead blocks... pred_iterator PI = pred_begin(Dest), PE = pred_end(Dest); if (PI == PE && Dest != Dest->getParent()->begin()) return false; // It's just a dead block, ignore it... // Also, do not bother with blocks with only a single predecessor: simplify // CFG will fold these two blocks together! ++PI; if (PI == PE) return false; // Exactly one predecessor! BasicBlock::iterator I = Dest->begin(); while (isa(*I)) ++I; for (unsigned Size = 0; I != Dest->end(); ++Size, ++I) if (Size == 6) return false; // The block is too large... return true; } /// canEliminateUnconditionalBranch - Unfortunately, the general form of tail /// duplication can do very bad things to SSA form, by destroying arbitrary /// relationships between dominators and dominator frontiers as it processes the /// program. The right solution for this is to have an incrementally updating /// dominator data structure, which can gracefully react to arbitrary /// "addEdge/removeEdge" changes to the CFG. Implementing this is nontrivial, /// however, so we just disable the transformation in cases where it is not /// currently safe. /// bool TailDup::canEliminateUnconditionalBranch(TerminatorInst *TI) { // Basically, we refuse to make the transformation if any of the values // computed in the 'tail' are used in any other basic blocks. BasicBlock *BB = TI->getParent(); BasicBlock *Tail = TI->getSuccessor(0); assert(isa(TI) && cast(TI)->isUnconditional()); for (BasicBlock::iterator I = Tail->begin(), E = Tail->end(); I != E; ++I) for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) { Instruction *User = cast(*UI); if (User->getParent() != Tail && User->getParent() != BB) return false; // The 'swap' problem foils the tail duplication rewriting code. if (isa(User) && User->getParent() == Tail) return false; } return true; } /// eliminateUnconditionalBranch - Clone the instructions from the destination /// block into the source block, eliminating the specified unconditional branch. /// If the destination block defines values used by successors of the dest /// block, we may need to insert PHI nodes. /// void TailDup::eliminateUnconditionalBranch(BranchInst *Branch) { BasicBlock *SourceBlock = Branch->getParent(); BasicBlock *DestBlock = Branch->getSuccessor(0); assert(SourceBlock != DestBlock && "Our predicate is broken!"); DEBUG(std::cerr << "TailDuplication[" << SourceBlock->getParent()->getName() << "]: Eliminating branch: " << *Branch); // We are going to have to map operands from the original block B to the new // copy of the block B'. If there are PHI nodes in the DestBlock, these PHI // nodes also define part of this mapping. Loop over these PHI nodes, adding // them to our mapping. // std::map ValueMapping; BasicBlock::iterator BI = DestBlock->begin(); bool HadPHINodes = isa(BI); for (; PHINode *PN = dyn_cast(BI); ++BI) ValueMapping[PN] = PN->getIncomingValueForBlock(SourceBlock); // Clone the non-phi instructions of the dest block into the source block, // keeping track of the mapping... // for (; BI != DestBlock->end(); ++BI) { Instruction *New = BI->clone(); New->setName(BI->getName()); SourceBlock->getInstList().push_back(New); ValueMapping[BI] = New; } // Now that we have built the mapping information and cloned all of the // instructions (giving us a new terminator, among other things), walk the new // instructions, rewriting references of old instructions to use new // instructions. // BI = Branch; ++BI; // Get an iterator to the first new instruction for (; BI != SourceBlock->end(); ++BI) for (unsigned i = 0, e = BI->getNumOperands(); i != e; ++i) if (Value *Remapped = ValueMapping[BI->getOperand(i)]) BI->setOperand(i, Remapped); // Next we check to see if any of the successors of DestBlock had PHI nodes. // If so, we need to add entries to the PHI nodes for SourceBlock now. for (succ_iterator SI = succ_begin(DestBlock), SE = succ_end(DestBlock); SI != SE; ++SI) { BasicBlock *Succ = *SI; for (BasicBlock::iterator PNI = Succ->begin(); PHINode *PN = dyn_cast(PNI); ++PNI) { // Ok, we have a PHI node. Figure out what the incoming value was for the // DestBlock. Value *IV = PN->getIncomingValueForBlock(DestBlock); // Remap the value if necessary... if (Value *MappedIV = ValueMapping[IV]) IV = MappedIV; PN->addIncoming(IV, SourceBlock); } } // Now that all of the instructions are correctly copied into the SourceBlock, // we have one more minor problem: the successors of the original DestBB may // use the values computed in DestBB either directly (if DestBB dominated the // block), or through a PHI node. In either case, we need to insert PHI nodes // into any successors of DestBB (which are now our successors) for each value // that is computed in DestBB, but is used outside of it. All of these uses // we have to rewrite with the new PHI node. // if (succ_begin(SourceBlock) != succ_end(SourceBlock)) // Avoid wasting time... for (BI = DestBlock->begin(); BI != DestBlock->end(); ++BI) if (BI->getType() != Type::VoidTy) InsertPHINodesIfNecessary(BI, ValueMapping[BI], SourceBlock); // Final step: now that we have finished everything up, walk the cloned // instructions one last time, constant propagating and DCE'ing them, because // they may not be needed anymore. // BI = Branch; ++BI; // Get an iterator to the first new instruction if (HadPHINodes) while (BI != SourceBlock->end()) if (!dceInstruction(BI) && !doConstantPropagation(BI)) ++BI; DestBlock->removePredecessor(SourceBlock); // Remove entries in PHI nodes... SourceBlock->getInstList().erase(Branch); // Destroy the uncond branch... ++NumEliminated; // We just killed a branch! } /// InsertPHINodesIfNecessary - So at this point, we cloned the OrigInst /// instruction into the NewBlock with the value of NewInst. If OrigInst was /// used outside of its defining basic block, we need to insert a PHI nodes into /// the successors. /// void TailDup::InsertPHINodesIfNecessary(Instruction *OrigInst, Value *NewInst, BasicBlock *NewBlock) { // Loop over all of the uses of OrigInst, rewriting them to be newly inserted // PHI nodes, unless they are in the same basic block as OrigInst. BasicBlock *OrigBlock = OrigInst->getParent(); std::vector Users; Users.reserve(OrigInst->use_size()); for (Value::use_iterator I = OrigInst->use_begin(), E = OrigInst->use_end(); I != E; ++I) { Instruction *In = cast(*I); if (In->getParent() != OrigBlock || // Don't modify uses in the orig block! isa(In)) Users.push_back(In); } // The common case is that the instruction is only used within the block that // defines it. If we have this case, quick exit. // if (Users.empty()) return; // Otherwise, we have a more complex case, handle it now. This requires the // construction of a mapping between a basic block and the value to use when // in the scope of that basic block. This map will map to the original and // new values when in the original or new block, but will map to inserted PHI // nodes when in other blocks. // std::map ValueMap; std::map OutValueMap; // The outgoing value map OutValueMap[OrigBlock] = OrigInst; OutValueMap[NewBlock ] = NewInst; // Seed the initial values... DEBUG(std::cerr << " ** Inserting PHI nodes for " << OrigInst); while (!Users.empty()) { Instruction *User = Users.back(); Users.pop_back(); if (PHINode *PN = dyn_cast(User)) { // PHI nodes must be handled specially here, because their operands are // actually defined in predecessor basic blocks, NOT in the block that the // PHI node lives in. Note that we have already added entries to PHI nods // which are in blocks that are immediate successors of OrigBlock, so // don't modify them again. for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) if (PN->getIncomingValue(i) == OrigInst && PN->getIncomingBlock(i) != OrigBlock) { Value *V = GetValueOutBlock(PN->getIncomingBlock(i), OrigInst, ValueMap, OutValueMap); PN->setIncomingValue(i, V); } } else { // Any other user of the instruction can just replace any uses with the // new value defined in the block it resides in. Value *V = GetValueInBlock(User->getParent(), OrigInst, ValueMap, OutValueMap); User->replaceUsesOfWith(OrigInst, V); } } } /// GetValueInBlock - This is a recursive method which inserts PHI nodes into /// the function until there is a value available in basic block BB. /// Value *TailDup::GetValueInBlock(BasicBlock *BB, Value *OrigVal, std::map &ValueMap, std::map &OutValueMap){ ValueHolder &BBVal = ValueMap[BB]; if (BBVal) return BBVal; // Value already computed for this block? // If this block has no predecessors, then it must be unreachable, thus, it // doesn't matter which value we use. if (pred_begin(BB) == pred_end(BB)) return BBVal = Constant::getNullValue(OrigVal->getType()); // If there is no value already available in this basic block, we need to // either reuse a value from an incoming, dominating, basic block, or we need // to create a new PHI node to merge in different incoming values. Because we // don't know if we're part of a loop at this point or not, we create a PHI // node, even if we will ultimately eliminate it. PHINode *PN = new PHINode(OrigVal->getType(), OrigVal->getName()+".pn", BB->begin()); BBVal = PN; // Insert this into the BBVal slot in case of cycles... ValueHolder &BBOutVal = OutValueMap[BB]; if (BBOutVal == 0) BBOutVal = PN; // Now that we have created the PHI node, loop over all of the predecessors of // this block, computing an incoming value for the predecessor. std::vector Preds(pred_begin(BB), pred_end(BB)); for (unsigned i = 0, e = Preds.size(); i != e; ++i) PN->addIncoming(GetValueOutBlock(Preds[i], OrigVal, ValueMap, OutValueMap), Preds[i]); // The PHI node is complete. In many cases, however the PHI node was // ultimately unnecessary: we could have just reused a dominating incoming // value. If this is the case, nuke the PHI node and replace the map entry // with the dominating value. // assert(PN->getNumIncomingValues() > 0 && "No predecessors?"); // Check to see if all of the elements in the PHI node are either the PHI node // itself or ONE particular value. unsigned i = 0; Value *ReplVal = PN->getIncomingValue(i); for (; ReplVal == PN && i != PN->getNumIncomingValues(); ++i) ReplVal = PN->getIncomingValue(i); // Skip values equal to the PN for (; i != PN->getNumIncomingValues(); ++i) if (PN->getIncomingValue(i) != PN && PN->getIncomingValue(i) != ReplVal) { ReplVal = 0; break; } // Found a value to replace the PHI node with? if (ReplVal && ReplVal != PN) { PN->replaceAllUsesWith(ReplVal); BB->getInstList().erase(PN); // Erase the PHI node... } else { ++NumPHINodes; } return BBVal; } Value *TailDup::GetValueOutBlock(BasicBlock *BB, Value *OrigVal, std::map &ValueMap, std::map &OutValueMap) { ValueHolder &BBVal = OutValueMap[BB]; if (BBVal) return BBVal; // Value already computed for this block? return GetValueInBlock(BB, OrigVal, ValueMap, OutValueMap); }