#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
-#include "llvm/DebugInfo.h"
+#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
+#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
-#include "llvm/Support/CFG.h"
+#include "llvm/IR/Module.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#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
assert(VMap.count(I) && "No mapping from source argument specified!");
#endif
+ // Copy all attributes other than those stored in the AttributeSet. We need
+ // to remap the parameter indices of the AttributeSet.
+ AttributeSet NewAttrs = NewFunc->getAttributes();
+ NewFunc->copyAttributesFrom(OldFunc);
+ NewFunc->setAttributes(NewAttrs);
+
AttributeSet OldAttrs = OldFunc->getAttributes();
// Clone any argument attributes that are present in the VMap.
- for (Function::const_arg_iterator I = OldFunc->arg_begin(),
- E = OldFunc->arg_end();
- I != E; ++I)
- if (Argument *Anew = dyn_cast<Argument>(VMap[I])) {
+ for (const Argument &OldArg : OldFunc->args())
+ if (Argument *NewArg = dyn_cast<Argument>(VMap[&OldArg])) {
AttributeSet attrs =
- OldAttrs.getParamAttributes(I->getArgNo() + 1);
+ OldAttrs.getParamAttributes(OldArg.getArgNo() + 1);
if (attrs.getNumSlots() > 0)
- Anew->addAttr(attrs);
+ NewArg->addAttr(attrs);
}
- NewFunc->setAttributes(NewFunc->getAttributes()
- .addAttributes(NewFunc->getContext(),
- AttributeSet::ReturnIndex,
- OldAttrs.getRetAttributes()));
- NewFunc->setAttributes(NewFunc->getAttributes()
- .addAttributes(NewFunc->getContext(),
- AttributeSet::FunctionIndex,
- OldAttrs.getFnAttributes()));
+ NewFunc->setAttributes(
+ NewFunc->getAttributes()
+ .addAttributes(NewFunc->getContext(), AttributeSet::ReturnIndex,
+ OldAttrs.getRetAttributes())
+ .addAttributes(NewFunc->getContext(), AttributeSet::FunctionIndex,
+ OldAttrs.getFnAttributes()));
// Loop over all of the basic blocks in the function, cloning them as
// appropriate. Note that we save BE this way in order to handle cloning of
TypeMapper, Materializer);
}
+// Find the MDNode which corresponds to the DISubprogram data that described F.
+static MDNode* FindSubprogram(const Function *F, DebugInfoFinder &Finder) {
+ for (DISubprogram Subprogram : Finder.subprograms()) {
+ if (Subprogram.describes(F)) return Subprogram;
+ }
+ return nullptr;
+}
+
+// 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);
+}
+
+// Clone the module-level debug info associated with OldFunc. The cloned data
+// will point to NewFunc instead.
+static void CloneDebugInfoMetadata(Function *NewFunc, const Function *OldFunc,
+ ValueToValueMapTy &VMap) {
+ DebugInfoFinder Finder;
+ Finder.processModule(*OldFunc->getParent());
+
+ const MDNode *OldSubprogramMDNode = FindSubprogram(OldFunc, Finder);
+ if (!OldSubprogramMDNode) return;
+
+ // 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));
+
+ for (DICompileUnit CU : Finder.compile_units()) {
+ DIArray Subprograms(CU.getSubprograms());
+
+ // If the compile unit's function list contains the old function, it should
+ // also contain the new one.
+ for (unsigned i = 0; i < Subprograms.getNumElements(); i++) {
+ if ((MDNode*)Subprograms.getElement(i) == OldSubprogramMDNode) {
+ AddOperand(Subprograms, NewSubprogram);
+ }
+ }
+ }
+}
+
/// CloneFunction - Return a copy of the specified function, but without
/// embedding the function into another module. Also, any references specified
/// in the VMap are changed to refer to their mapped value instead of the
VMap[I] = DestI++; // Add mapping to VMap
}
+ if (ModuleLevelChanges)
+ CloneDebugInfoMetadata(NewF, F, VMap);
+
SmallVector<ReturnInst*, 8> Returns; // Ignore returns cloned.
CloneFunctionInto(NewF, F, VMap, ModuleLevelChanges, Returns, "", CodeInfo);
return NewF;
NameSuffix(nameSuffix), CodeInfo(codeInfo), DL(DL) {
}
- /// CloneBlock - The specified block is found to be reachable, clone it and
- /// anything that it can reach.
+ /// 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,
- std::vector<const BasicBlock*> &ToClone);
+ 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.
+/// 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 PruningFunctionCloner::CloneBlock(const BasicBlock *BB,
- std::vector<const BasicBlock*> &ToClone){
- WeakVH &BBEntry = VMap[BB];
-
- // Have we already cloned this block?
- if (BBEntry) return;
+ BasicBlock *NewBB,
+ std::vector<const BasicBlock *> &ToClone,
+ std::set<const BasicBlock *> &OrigBBs) {
- // Nope, clone it now.
- BasicBlock *NewBB;
- BBEntry = NewBB = BasicBlock::Create(BB->getContext());
- if (BB->hasName()) NewBB->setName(BB->getName()+NameSuffix);
+ // 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;
- // 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);
- }
-
+ // Nope, clone it now.
bool hasCalls = false, hasDynamicAllocas = false, hasStaticAllocas = false;
// If the condition was a known constant in the callee...
ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
// Or is a known constant in the caller...
- if (Cond == 0) {
+ if (!Cond) {
Value *V = VMap[BI->getCondition()];
Cond = dyn_cast_or_null<ConstantInt>(V);
}
} else if (const SwitchInst *SI = dyn_cast<SwitchInst>(OldTI)) {
// If switching on a value known constant in the caller.
ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition());
- if (Cond == 0) { // Or known constant after constant prop in the callee...
+ if (!Cond) { // Or known constant after constant prop in the callee...
Value *V = VMap[SI->getCondition()];
Cond = dyn_cast_or_null<ConstantInt>(V);
}
const DataLayout *DL,
Instruction *TheCall) {
assert(NameSuffix && "NameSuffix cannot be null!");
-
+
#ifndef NDEBUG
for (Function::const_arg_iterator II = OldFunc->arg_begin(),
E = OldFunc->arg_end(); II != E; ++II)
PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
NameSuffix, CodeInfo, DL);
- // Clone the entry block, and anything recursively reachable from it.
+ // 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();
- PFC.CloneBlock(BB, CloneWorklist);
+
+ // 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);
+ }
}
-
+
+ // 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());
+ while (!CloneWorklist.empty()) {
+ const BasicBlock *BB = CloneWorklist.back();
+ CloneWorklist.pop_back();
+ PFC.CloneBlock(BB, cast<BasicBlock>(VMap[BB]), CloneWorklist,
+ OrigBBs);
+ }
+
+ // 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 == 0) continue; // Dead block.
+ if (!NewBB)
+ continue; // Dead block.
// Add the new block to the new function.
NewFunc->getBasicBlockList().push_back(NewBB);