#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <map>
-#include <set>
using namespace llvm;
// CloneBasicBlock - See comments in Cloning.h
// Add an operand to an existing MDNode. The new operand will be added at the
// back of the operand list.
-static void AddOperand(MDNode *Node, Value *Operand) {
- SmallVector<Value*, 16> Operands;
- for (unsigned i = 0; i < Node->getNumOperands(); i++) {
- Operands.push_back(Node->getOperand(i));
- }
- Operands.push_back(Operand);
- MDNode *NewNode = MDNode::get(Node->getContext(), Operands);
- Node->replaceAllUsesWith(NewNode);
+static void AddOperand(DICompileUnit CU, DIArray SPs, Metadata *NewSP) {
+ SmallVector<Metadata *, 16> NewSPs;
+ NewSPs.reserve(SPs->getNumOperands() + 1);
+ for (unsigned I = 0, E = SPs->getNumOperands(); I != E; ++I)
+ NewSPs.push_back(SPs->getOperand(I));
+ NewSPs.push_back(NewSP);
+ CU.replaceSubprograms(DIArray(MDNode::get(CU->getContext(), NewSPs)));
}
// Clone the module-level debug info associated with OldFunc. The cloned data
// Ensure that OldFunc appears in the map.
// (if it's already there it must point to NewFunc anyway)
VMap[OldFunc] = NewFunc;
- DISubprogram NewSubprogram(MapValue(OldSubprogramMDNode, VMap));
+ DISubprogram NewSubprogram(MapMetadata(OldSubprogramMDNode, VMap));
for (DICompileUnit CU : Finder.compile_units()) {
DIArray Subprograms(CU.getSubprograms());
// also contain the new one.
for (unsigned i = 0; i < Subprograms.getNumElements(); i++) {
if ((MDNode*)Subprograms.getElement(i) == OldSubprogramMDNode) {
- AddOperand(Subprograms, NewSubprogram);
+ AddOperand(CU, Subprograms, NewSubprogram);
+ break;
}
}
}
const char *NameSuffix;
ClonedCodeInfo *CodeInfo;
const DataLayout *DL;
+ CloningDirector *Director;
+ ValueMapTypeRemapper *TypeMapper;
+ ValueMaterializer *Materializer;
+
public:
PruningFunctionCloner(Function *newFunc, const Function *oldFunc,
ValueToValueMapTy &valueMap,
bool moduleLevelChanges,
const char *nameSuffix,
ClonedCodeInfo *codeInfo,
- const DataLayout *DL)
+ const DataLayout *DL,
+ CloningDirector *Director)
: NewFunc(newFunc), OldFunc(oldFunc),
VMap(valueMap), ModuleLevelChanges(moduleLevelChanges),
- NameSuffix(nameSuffix), CodeInfo(codeInfo), DL(DL) {
+ NameSuffix(nameSuffix), CodeInfo(codeInfo), DL(DL),
+ Director(Director) {
+ // These are optional components. The Director may return null.
+ if (Director) {
+ TypeMapper = Director->getTypeRemapper();
+ Materializer = Director->getValueMaterializer();
+ } else {
+ TypeMapper = nullptr;
+ Materializer = nullptr;
+ }
}
- /// CloneBlock - The specified block is found to be reachable, so clone it
- /// into NewBB.
- /// ToClone is the vector of actually cloned blocks.
- /// OrigBBs is the set of all blocks reacheable from the entry block.
- /// It contains the block candidates and makes sure each block
- /// is cloned at most once.
- void CloneBlock(const BasicBlock *BB,
- BasicBlock *NewBB,
- std::vector<const BasicBlock *> &ToClone,
- std::set<const BasicBlock *> &OrigBBs);
+ /// CloneBlock - The specified block is found to be reachable, clone it and
+ /// anything that it can reach.
+ void CloneBlock(const BasicBlock *BB,
+ BasicBlock::const_iterator StartingInst,
+ std::vector<const BasicBlock*> &ToClone);
};
}
-/// CloneBlock - The specified block is found to be reachable, so clone it
-/// into NewBB.
-/// ToClone is the vector of actually cloned blocks.
-/// OrigBBs is the set of all blocks reacheable from the entry block.
-/// It contains the block candidates and makes sure each block
-/// is cloned at most once.
+/// CloneBlock - The specified block is found to be reachable, clone it and
+/// anything that it can reach.
void PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
- BasicBlock *NewBB,
- std::vector<const BasicBlock *> &ToClone,
- std::set<const BasicBlock *> &OrigBBs) {
-
- // Remove BB from list of blocks to clone.
- // When it was not in the list, it has been cloned already, so
- // don't clone again.
- if (!OrigBBs.erase(BB)) return;
+ BasicBlock::const_iterator StartingInst,
+ std::vector<const BasicBlock*> &ToClone){
+ WeakVH &BBEntry = VMap[BB];
+ // Have we already cloned this block?
+ if (BBEntry) return;
+
// Nope, clone it now.
+ BasicBlock *NewBB;
+ BBEntry = NewBB = BasicBlock::Create(BB->getContext());
+ if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
+
+ // It is only legal to clone a function if a block address within that
+ // function is never referenced outside of the function. Given that, we
+ // want to map block addresses from the old function to block addresses in
+ // the clone. (This is different from the generic ValueMapper
+ // implementation, which generates an invalid blockaddress when
+ // cloning a function.)
+ //
+ // Note that we don't need to fix the mapping for unreachable blocks;
+ // the default mapping there is safe.
+ if (BB->hasAddressTaken()) {
+ Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
+ const_cast<BasicBlock*>(BB));
+ VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB);
+ }
bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
-
+
// Loop over all instructions, and copy them over, DCE'ing as we go. This
// loop doesn't include the terminator.
- for (BasicBlock::const_iterator II = BB->begin(), IE = --BB->end();
+ for (BasicBlock::const_iterator II = StartingInst, IE = --BB->end();
II != IE; ++II) {
+ // If the "Director" remaps the instruction, don't clone it.
+ if (Director) {
+ CloningDirector::CloningAction Action
+ = Director->handleInstruction(VMap, II, NewBB);
+ // If the cloning director says stop, we want to stop everything, not
+ // just break out of the loop (which would cause the terminator to be
+ // cloned). The cloning director is responsible for inserting a proper
+ // terminator into the new basic block in this case.
+ if (Action == CloningDirector::StopCloningBB)
+ return;
+ // If the cloning director says skip, continue to the next instruction.
+ // In this case, the cloning director is responsible for mapping the
+ // skipped instruction to some value that is defined in the new
+ // basic block.
+ if (Action == CloningDirector::SkipInstruction)
+ continue;
+ }
+
Instruction *NewInst = II->clone();
// Eagerly remap operands to the newly cloned instruction, except for PHI
// nodes for which we defer processing until we update the CFG.
if (!isa<PHINode>(NewInst)) {
RemapInstruction(NewInst, VMap,
- ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
+ ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
+ TypeMapper, Materializer);
// If we can simplify this instruction to some other value, simply add
// a mapping to that value rather than inserting a new instruction into
// Finally, clone over the terminator.
const TerminatorInst *OldTI = BB->getTerminator();
bool TerminatorDone = false;
+ if (Director) {
+ CloningDirector::CloningAction Action
+ = Director->handleInstruction(VMap, OldTI, NewBB);
+ // If the cloning director says stop, we want to stop everything, not
+ // just break out of the loop (which would cause the terminator to be
+ // cloned). The cloning director is responsible for inserting a proper
+ // terminator into the new basic block in this case.
+ if (Action == CloningDirector::StopCloningBB)
+ return;
+ assert(Action != CloningDirector::SkipInstruction &&
+ "SkipInstruction is not valid for terminators.");
+ }
if (const BranchInst *BI = dyn_cast<BranchInst>(OldTI)) {
if (BI->isConditional()) {
// If the condition was a known constant in the callee...
}
}
-/// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
-/// except that it does some simple constant prop and DCE on the fly. The
-/// effect of this is to copy significantly less code in cases where (for
-/// example) a function call with constant arguments is inlined, and those
-/// constant arguments cause a significant amount of code in the callee to be
-/// dead. Since this doesn't produce an exact copy of the input, it can't be
-/// used for things like CloneFunction or CloneModule.
-void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
+/// CloneAndPruneIntoFromInst - This works like CloneAndPruneFunctionInto, except
+/// that it does not clone the entire function. Instead it starts at an
+/// instruction provided by the caller and copies (and prunes) only the code
+/// reachable from that instruction.
+void llvm::CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
+ const Instruction *StartingInst,
ValueToValueMapTy &VMap,
bool ModuleLevelChanges,
- SmallVectorImpl<ReturnInst*> &Returns,
+ SmallVectorImpl<ReturnInst *> &Returns,
const char *NameSuffix,
ClonedCodeInfo *CodeInfo,
const DataLayout *DL,
- Instruction *TheCall) {
+ CloningDirector *Director) {
assert(NameSuffix && "NameSuffix cannot be null!");
+ ValueMapTypeRemapper *TypeMapper = nullptr;
+ ValueMaterializer *Materializer = nullptr;
+
+ if (Director) {
+ TypeMapper = Director->getTypeRemapper();
+ Materializer = Director->getValueMaterializer();
+ }
+
#ifndef NDEBUG
- for (Function::const_arg_iterator II = OldFunc->arg_begin(),
- E = OldFunc->arg_end(); II != E; ++II)
- assert(VMap.count(II) && "No mapping from source argument specified!");
+ // If the cloning starts at the begining of the function, verify that
+ // the function arguments are mapped.
+ if (!StartingInst)
+ for (Function::const_arg_iterator II = OldFunc->arg_begin(),
+ E = OldFunc->arg_end(); II != E; ++II)
+ assert(VMap.count(II) && "No mapping from source argument specified!");
#endif
PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
- NameSuffix, CodeInfo, DL);
-
- // Since all BB address references need to be known before block-by-block
- // processing, we need to create all reachable blocks before processing
- // them for instruction cloning and pruning. Some of these blocks may
- // be removed due to later pruning.
- std::vector<const BasicBlock*> CloneWorklist;
- //
- // OrigBBs consists of all blocks reachable from the entry
- // block.
- // This list will be pruned down by the CloneFunction() due to two
- // two optimizations:
- // First, when a conditional branch target is known at compile-time,
- // only the actual branch destination block needs to be cloned.
- // Second, when a switch statement target is known at compile-time,
- // only the actual case statement needs to be cloned.
- std::set<const BasicBlock *> OrigBBs;
-
- CloneWorklist.push_back(&OldFunc->getEntryBlock());
- while (!CloneWorklist.empty()) {
- const BasicBlock *BB = CloneWorklist.back();
- CloneWorklist.pop_back();
-
- // Don't revisit blocks.
- if (VMap.count(BB))
- continue;
-
- BasicBlock *NewBB = BasicBlock::Create(BB->getContext());
- if (BB->hasName())
- NewBB->setName(BB->getName() + NameSuffix);
-
- // It is legal to clone a function when a block address within that
- // function is never escapes outside of the function. Given that, we
- // want to map block addresses from the old function to block addresses in
- // the clone. (This is different from the generic ValueMapper
- // implementation, which generates an invalid block address when
- // cloning a function.)
- // Note the current escape address does not catch all legal cases: even
- // when all block addresses taken are local and the function has the
- // always_inline attribute due to the indirect branch inlining is
- // suppressed.
- // Note that we don't need to fix the mapping for unreachable blocks;
- // the default mapping there is safe.
- if (BB->hasAddressTaken()) {
- Constant *OldBBAddr = BlockAddress::get(const_cast<Function*>(OldFunc),
- const_cast<BasicBlock*>(BB));
- VMap[OldBBAddr] = BlockAddress::get(NewFunc, NewBB);
- }
-
- OrigBBs.insert(BB);
- VMap[BB] = NewBB;
- // Iterate over all possible successors and add them to the CloneWorklist.
- const TerminatorInst *Term = BB->getTerminator();
- for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
- BasicBlock *Succ = Term->getSuccessor(i);
- CloneWorklist.push_back(Succ);
- }
+ NameSuffix, CodeInfo, DL, Director);
+ const BasicBlock *StartingBB;
+ if (StartingInst)
+ StartingBB = StartingInst->getParent();
+ else {
+ StartingBB = &OldFunc->getEntryBlock();
+ StartingInst = StartingBB->begin();
}
- // Now, fill only the reachable blocks with the cloned contents
- // of the originals.
- assert(CloneWorklist.empty() && "Dirty worklist before re-use\n");
- CloneWorklist.push_back(&OldFunc->getEntryBlock());
+ // Clone the entry block, and anything recursively reachable from it.
+ std::vector<const BasicBlock*> CloneWorklist;
+ PFC.CloneBlock(StartingBB, StartingInst, CloneWorklist);
while (!CloneWorklist.empty()) {
const BasicBlock *BB = CloneWorklist.back();
CloneWorklist.pop_back();
- PFC.CloneBlock(BB, cast<BasicBlock>(VMap[BB]), CloneWorklist,
- OrigBBs);
+ PFC.CloneBlock(BB, BB->begin(), CloneWorklist);
}
-
- // FIXME: Delete BB's that were created but have been pruned.
- // Actual cloning may have found pruning opportunities since
- // branch or switch statement target may have been known at compile-time.
- // Alternatively we could write a routine CloneFunction and add a) a
- // parameter to actually do the cloning and b) a return parameter that
- // gives a list of blocks that need to be cloned also. Then we could
- // call CloneFunction when we collect the blocks to clone, but suppress
- // cloning. And then actually *do* the cloning in the while loop above. Then
- // the cleanup here would become redundant, and so would be the OrigBBs.
- for (std::set<const BasicBlock *>::iterator Oi = OrigBBs.begin(),
- Oe = OrigBBs.end(); Oi != Oe; ++Oi) {
- const BasicBlock *Orig = *Oi;
- BasicBlock *NewBB = cast<BasicBlock>(VMap[Orig]);
- delete NewBB;
- VMap[Orig] = 0;
- }
-
+
// Loop over all of the basic blocks in the old function. If the block was
// reachable, we have cloned it and the old block is now in the value map:
// insert it into the new function in the right order. If not, ignore it.
BI != BE; ++BI) {
Value *V = VMap[BI];
BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
- if (!NewBB)
- continue; // Dead block.
+ if (!NewBB) continue; // Dead block.
// Add the new block to the new function.
NewFunc->getBasicBlockList().push_back(NewBB);
// Finally, remap the terminator instructions, as those can't be remapped
// until all BBs are mapped.
RemapInstruction(NewBB->getTerminator(), VMap,
- ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
+ ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges,
+ TypeMapper, Materializer);
}
// Defer PHI resolution until rest of function is resolved, PHI resolution
// and zap unconditional fall-through branches. This happen all the time when
// specializing code: code specialization turns conditional branches into
// uncond branches, and this code folds them.
- Function::iterator Begin = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]);
+ Function::iterator Begin = cast<BasicBlock>(VMap[StartingBB]);
Function::iterator I = Begin;
while (I != NewFunc->end()) {
// Check if this block has become dead during inlining or other
// Make a final pass over the basic blocks from theh old function to gather
// any return instructions which survived folding. We have to do this here
// because we can iteratively remove and merge returns above.
- for (Function::iterator I = cast<BasicBlock>(VMap[&OldFunc->getEntryBlock()]),
+ for (Function::iterator I = cast<BasicBlock>(VMap[StartingBB]),
E = NewFunc->end();
I != E; ++I)
if (ReturnInst *RI = dyn_cast<ReturnInst>(I->getTerminator()))
Returns.push_back(RI);
}
+
+
+/// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
+/// except that it does some simple constant prop and DCE on the fly. The
+/// effect of this is to copy significantly less code in cases where (for
+/// example) a function call with constant arguments is inlined, and those
+/// constant arguments cause a significant amount of code in the callee to be
+/// dead. Since this doesn't produce an exact copy of the input, it can't be
+/// used for things like CloneFunction or CloneModule.
+void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
+ ValueToValueMapTy &VMap,
+ bool ModuleLevelChanges,
+ SmallVectorImpl<ReturnInst*> &Returns,
+ const char *NameSuffix,
+ ClonedCodeInfo *CodeInfo,
+ const DataLayout *DL,
+ Instruction *TheCall) {
+ CloneAndPruneIntoFromInst(NewFunc, OldFunc, OldFunc->front().begin(),
+ VMap, ModuleLevelChanges, Returns, NameSuffix,
+ CodeInfo, DL, nullptr);
+}