| //===- Local.cpp - Compute a local data structure graph for a function ----===// |
| // |
| // 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. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Compute the local version of the data structure graph for a function. The |
| // external interface to this file is the DSGraph constructor. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "dsa-local" |
| |
| #include "dsa/DataStructure.h" |
| #include "dsa/DSGraph.h" |
| |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/ADT/DenseSet.h" |
| #include "llvm/ADT/Triple.h" |
| #include "llvm/IR/Constants.h" |
| #include "llvm/IR/DataLayout.h" |
| #include "llvm/IR/DerivedTypes.h" |
| #include "llvm/IR/InlineAsm.h" |
| #include "llvm/IR/Intrinsics.h" |
| #include "llvm/IR/Instructions.h" |
| #include "llvm/IR/IntrinsicInst.h" |
| #include "llvm/IR/Use.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/FormattedStream.h" |
| #include "llvm/IR/GetElementPtrTypeIterator.h" |
| #include "llvm/IR/InstVisitor.h" |
| #include "llvm/Support/Timer.h" |
| |
| #include <fstream> |
| |
| // FIXME: This should eventually be a FunctionPass that is automatically |
| // aggregated into a Pass. |
| // |
| #include "llvm/IR/Module.h" |
| |
| using namespace llvm; |
| |
| namespace { |
| STATISTIC(NumDirectCall, "Number of direct calls added"); |
| STATISTIC(NumIndirectCall, "Number of indirect calls added"); |
| STATISTIC(NumAsmCall, "Number of asm calls collapsed/seen"); |
| STATISTIC(NumIntrinsicCall, "Number of intrinsics called"); |
| STATISTIC(NumBoringIntToPtr, "Number of inttoptr used only in cmp"); |
| //STATISTIC(NumSimpleIntToPtr, "Number of inttoptr from ptrtoint"); |
| STATISTIC(NumIgnoredInst, "Number of instructions ignored"); |
| |
| RegisterPass<LocalDataStructures> |
| X("dsa-local", "Local Data Structure Analysis"); |
| |
| cl::opt<std::string> hasMagicSections("dsa-magic-sections", |
| cl::desc("File with section to global mapping")); //, cl::ReallyHidden); |
| } |
| cl::opt<bool> TypeInferenceOptimize("enable-type-inference-opts", |
| cl::desc("Enable Type Inference Optimizations added to DSA."), |
| cl::Hidden, |
| cl::init(false)); |
| |
| namespace { |
| //===--------------------------------------------------------------------===// |
| // GraphBuilder Class |
| //===--------------------------------------------------------------------===// |
| // |
| /// This class is the builder class that constructs the local data structure |
| /// graph by performing a single pass over the function in question. |
| /// |
| class GraphBuilder : InstVisitor<GraphBuilder> { |
| DSGraph &G; |
| Function* FB; |
| LocalDataStructures* DS; |
| const DataLayout& TD; |
| DSNodeHandle VAArrayNH; |
| |
| //////////////////////////////////////////////////////////////////////////// |
| // Helper functions used to implement the visitation functions... |
| |
| void MergeConstantInitIntoNode(DSNodeHandle &NH, Type* Ty, Constant *C); |
| |
| /// createNode - Create a new DSNode, ensuring that it is properly added to |
| /// the graph. |
| /// |
| DSNode *createNode() |
| { |
| DSNode* ret = new DSNode(&G); |
| assert(ret->getParentGraph() && "No parent?"); |
| return ret; |
| } |
| |
| /// setDestTo - Set the ScalarMap entry for the specified value to point to |
| /// the specified destination. If the Value already points to a node, make |
| /// sure to merge the two destinations together. |
| /// |
| void setDestTo(Value &V, const DSNodeHandle &NH); |
| |
| /// getValueDest - Return the DSNode that the actual value points to. |
| /// |
| DSNodeHandle getValueDest(Value* V); |
| |
| /// getLink - This method is used to return the specified link in the |
| /// specified node if one exists. If a link does not already exist (it's |
| /// null), then we create a new node, link it, then return it. |
| /// |
| DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link = 0); |
| |
| //////////////////////////////////////////////////////////////////////////// |
| // Visitor functions, used to handle each instruction type we encounter... |
| friend class InstVisitor<GraphBuilder>; |
| |
| void visitAllocaInst(AllocaInst &AI) |
| { setDestTo(AI, createNode()->setAllocaMarker()); } |
| |
| //the simple ones |
| void visitPHINode(PHINode &PN); |
| void visitSelectInst(SelectInst &SI); |
| void visitLoadInst(LoadInst &LI); |
| void visitStoreInst(StoreInst &SI); |
| void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I); |
| void visitAtomicRMWInst(AtomicRMWInst &I); |
| void visitReturnInst(ReturnInst &RI); |
| void visitVAArgInst(VAArgInst &I); |
| void visitIntToPtrInst(IntToPtrInst &I); |
| void visitPtrToIntInst(PtrToIntInst &I); |
| void visitBitCastInst(BitCastInst &I); |
| void visitCmpInst(CmpInst &I); |
| void visitInsertValueInst(InsertValueInst& I); |
| void visitExtractValueInst(ExtractValueInst& I); |
| |
| //the nasty ones |
| void visitGetElementPtrInst(User &GEP); |
| void visitCallInst(CallInst &CI); |
| void visitInvokeInst(InvokeInst &II); |
| void visitInstruction(Instruction &I); |
| |
| bool visitIntrinsic(CallSite CS, Function* F); |
| void visitCallSite(CallSite CS); |
| void visitVAStart(CallSite CS); |
| void visitVAStartNode(DSNode* N); |
| |
| public: |
| GraphBuilder(Function &f, DSGraph &g, LocalDataStructures& DSi) |
| : G(g), FB(&f), DS(&DSi), TD(g.getDataLayout()), VAArrayNH(0) { |
| // Create scalar nodes for all pointer arguments... |
| for (Function::arg_iterator I = f.arg_begin(), E = f.arg_end(); |
| I != E; ++I) { |
| if (isa<PointerType>(I->getType())) { |
| // WD: Why do we set the external marker so early in the analysis? |
| // Functions we have definitions for, but are externally reachable have no external contexts |
| // that we'd want to BU external information into (since those contexts are by definition |
| // ones we don't have code for). Shouldn't this just be set in TD? |
| #if 0 |
| DSNode * Node = getValueDest(I).getNode(); |
| |
| if (!f.hasInternalLinkage() || !f.hasPrivateLinkage()) |
| Node->setExternalMarker(); |
| #else |
| getValueDest(I).getNode(); |
| #endif |
| |
| } |
| } |
| |
| // Create an entry for the return, which tracks which functions are in |
| // the graph |
| g.getOrCreateReturnNodeFor(f); |
| |
| // Create a node to handle information about variable arguments |
| g.getOrCreateVANodeFor(f); |
| |
| visit(f); // Single pass over the function |
| |
| // If there are any constant globals referenced in this function, merge |
| // their initializers into the local graph from the globals graph. |
| // This resolves indirect calls in some common cases |
| // Only merge info for nodes that already exist in the local pass |
| // otherwise leaf functions could contain less collapsing than the globals |
| // graph |
| if (g.getScalarMap().global_begin() != g.getScalarMap().global_end()) { |
| ReachabilityCloner RC(&g, g.getGlobalsGraph(), 0); |
| for (DSScalarMap::global_iterator I = g.getScalarMap().global_begin(), |
| E = g.getScalarMap().global_end(); I != E; ++I) { |
| if (const GlobalVariable * GV = dyn_cast<GlobalVariable > (*I)) |
| if (GV->isConstant()) |
| RC.merge(g.getNodeForValue(GV), g.getGlobalsGraph()->getNodeForValue(GV)); |
| } |
| } |
| |
| g.markIncompleteNodes(DSGraph::MarkFormalArgs); |
| |
| // Compute sources of external |
| unsigned EFlags = 0 |
| | DSGraph::DontMarkFormalsExternal |
| | DSGraph::ProcessCallSites; |
| |
| g.computeExternalFlags(EFlags); |
| g.computeIntPtrFlags(); |
| |
| // Remove any nodes made dead due to merging... |
| g.removeDeadNodes(DSGraph::KeepUnreachableGlobals); |
| } |
| |
| // GraphBuilder ctor for working on the globals graph |
| explicit GraphBuilder(DSGraph& g) |
| :G(g), FB(0), TD(g.getDataLayout()), VAArrayNH(0) |
| {} |
| |
| void mergeInGlobalInitializer(GlobalVariable *GV); |
| void mergeExternalGlobal(GlobalVariable* GV); |
| void mergeFunction(Function* F) { getValueDest(F); } |
| }; |
| |
| /// Traverse the whole DSGraph, and propagate the unknown flags through all |
| /// out edges. |
| static void propagateUnknownFlag(DSGraph * G) { |
| std::vector<DSNode *> workList; |
| DenseSet<DSNode *> visited; |
| for (DSGraph::node_iterator I = G->node_begin(), E = G->node_end(); I != E; ++I) |
| if (I->isUnknownNode()) |
| workList.push_back(&*I); |
| |
| while (!workList.empty()) { |
| DSNode * N = workList.back(); |
| workList.pop_back(); |
| if (visited.count(N) != 0) continue; |
| visited.insert(N); |
| N->setUnknownMarker(); |
| for (DSNode::edge_iterator I = N->edge_begin(), E = N->edge_end(); I != E; ++I) |
| if (!I->second.isNull()) |
| workList.push_back(I->second.getNode()); |
| } |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Helper method implementations... |
| // |
| |
| |
| /// |
| /// getValueDest - Return the DSNode that the actual value points to. |
| /// |
| DSNodeHandle GraphBuilder::getValueDest(Value* V) { |
| if (isa<Constant>(V) && cast<Constant>(V)->isNullValue()) |
| return 0; // Null doesn't point to anything, don't add to ScalarMap! |
| |
| DSNodeHandle &NH = G.getNodeForValue(V); |
| if (!NH.isNull()) |
| return NH; // Already have a node? Just return it... |
| |
| // Otherwise we need to create a new node to point to. |
| // Check first for constant expressions that must be traversed to |
| // extract the actual value. |
| DSNode* N; |
| if (Function * F = dyn_cast<Function > (V)) { |
| // Create a new global node for this function. |
| N = createNode(); |
| N->addFunction(F); |
| if (F->isDeclaration()) |
| N->setExternFuncMarker(); |
| } else if (GlobalValue * GV = dyn_cast<GlobalValue > (V)) { |
| // Create a new global node for this global variable. |
| N = createNode(); |
| N->addGlobal(GV); |
| if (GV->isDeclaration()) |
| N->setExternGlobalMarker(); |
| } else if (Constant *C = dyn_cast<Constant>(V)) { |
| if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { |
| if (CE->isCast()) { |
| if (isa<PointerType>(CE->getOperand(0)->getType())) |
| NH = getValueDest(CE->getOperand(0)); |
| else |
| NH = createNode()->setUnknownMarker(); |
| } else if (CE->getOpcode() == Instruction::GetElementPtr) { |
| visitGetElementPtrInst(*CE); |
| assert(G.hasNodeForValue(CE) && "GEP didn't get processed right?"); |
| NH = G.getNodeForValue(CE); |
| } else { |
| // This returns a conservative unknown node for any unhandled ConstExpr |
| NH = createNode()->setUnknownMarker(); |
| } |
| if (NH.isNull()) { // (getelementptr null, X) returns null |
| G.eraseNodeForValue(V); |
| return 0; |
| } |
| return NH; |
| } else if (isa<UndefValue>(C)) { |
| G.eraseNodeForValue(V); |
| return 0; |
| } else if (isa<GlobalAlias>(C)) { |
| // XXX: Need more investigation |
| // According to Andrew, DSA is broken on global aliasing, since it does |
| // not handle the aliases of parameters correctly. Here is only a quick |
| // fix for some special cases. |
| NH = getValueDest(cast<GlobalAlias>(C)->getAliasee()); |
| return NH; |
| } else if (isa<BlockAddress>(C)) { |
| // |
| // FIXME: This may not be quite right; we should probably add a |
| // BlockAddress flag to the DSNode instead of using the unknown flag. |
| // |
| N = createNode(); |
| N->setUnknownMarker(); |
| } else if (isa<ConstantStruct>(C) || isa<ConstantArray>(C) || |
| isa<ConstantDataSequential>(C) || isa<ConstantDataArray>(C) || |
| isa<ConstantDataVector>(C)) { |
| // Treat these the same way we treat global initializers |
| N = createNode(); |
| NH.mergeWith(N); |
| MergeConstantInitIntoNode(NH, C->getType(), C); |
| } else { |
| errs() << "Unknown constant: " << *C << "\n"; |
| assert(0 && "Unknown constant type!"); |
| } |
| N = createNode(); // just create a shadow node |
| } else { |
| // Otherwise just create a shadow node |
| N = createNode(); |
| } |
| |
| NH.setTo(N, 0); // Remember that we are pointing to it... |
| return NH; |
| } |
| |
| |
| /// getLink - This method is used to return the specified link in the |
| /// specified node if one exists. If a link does not already exist (it's |
| /// null), then we create a new node, link it, then return it. We must |
| /// specify the type of the Node field we are accessing so that we know what |
| /// type should be linked to if we need to create a new node. |
| /// |
| DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, unsigned LinkNo) { |
| DSNodeHandle &Node = const_cast<DSNodeHandle&>(node); |
| DSNodeHandle &Link = Node.getLink(LinkNo); |
| if (Link.isNull()) { |
| // If the link hasn't been created yet, make and return a new shadow node |
| Link = createNode(); |
| } |
| return Link; |
| } |
| |
| |
| /// setDestTo - Set the ScalarMap entry for the specified value to point to the |
| /// specified destination. If the Value already points to a node, make sure to |
| /// merge the two destinations together. |
| /// |
| void GraphBuilder::setDestTo(Value &V, const DSNodeHandle &NH) { |
| G.getNodeForValue(&V).mergeWith(NH); |
| } |
| |
| |
| //===----------------------------------------------------------------------===// |
| // Specific instruction type handler implementations... |
| // |
| |
| // PHINode - Make the scalar for the PHI node point to all of the things the |
| // incoming values point to... which effectively causes them to be merged. |
| // |
| void GraphBuilder::visitPHINode(PHINode &PN) { |
| if (!isa<PointerType>(PN.getType())) return; // Only pointer PHIs |
| |
| DSNodeHandle &PNDest = G.getNodeForValue(&PN); |
| for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) |
| PNDest.mergeWith(getValueDest(PN.getIncomingValue(i))); |
| } |
| |
| void GraphBuilder::visitSelectInst(SelectInst &SI) { |
| if (!isa<PointerType>(SI.getType())) |
| return; // Only pointer Selects |
| |
| DSNodeHandle &Dest = G.getNodeForValue(&SI); |
| DSNodeHandle S1 = getValueDest(SI.getOperand(1)); |
| DSNodeHandle S2 = getValueDest(SI.getOperand(2)); |
| Dest.mergeWith(S1); |
| Dest.mergeWith(S2); |
| } |
| |
| void GraphBuilder::visitLoadInst(LoadInst &LI) { |
| // |
| // Create a DSNode for the pointer dereferenced by the load. If the DSNode |
| // is NULL, do nothing more (this can occur if the load is loading from a |
| // NULL pointer constant (bugpoint can generate such code). |
| // |
| DSNodeHandle Ptr = getValueDest(LI.getPointerOperand()); |
| if (Ptr.isNull()) return; // Load from null |
| |
| // Make that the node is read from... |
| Ptr.getNode()->setReadMarker(); |
| |
| // Ensure a typerecord exists... |
| Ptr.getNode()->growSizeForType(LI.getType(), Ptr.getOffset()); |
| |
| if (isa<PointerType>(LI.getType())) |
| setDestTo(LI, getLink(Ptr)); |
| |
| // check that it is the inserted value |
| if(TypeInferenceOptimize) |
| if(LI.hasOneUse()) |
| if(StoreInst *SI = dyn_cast<StoreInst>(*(LI.user_begin()))) |
| if(SI->getOperand(0) == &LI) { |
| ++NumIgnoredInst; |
| return; |
| } |
| Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset()); |
| } |
| |
| void GraphBuilder::visitStoreInst(StoreInst &SI) { |
| Type *StoredTy = SI.getOperand(0)->getType(); |
| DSNodeHandle Dest = getValueDest(SI.getOperand(1)); |
| if (Dest.isNull()) return; |
| |
| // Mark that the node is written to... |
| Dest.getNode()->setModifiedMarker(); |
| |
| // Ensure a type-record exists... |
| Dest.getNode()->growSizeForType(StoredTy, Dest.getOffset()); |
| |
| // Avoid adding edges from null, or processing non-"pointer" stores |
| if (isa<PointerType>(StoredTy)) |
| Dest.addEdgeTo(getValueDest(SI.getOperand(0))); |
| |
| if(TypeInferenceOptimize) |
| if(SI.getOperand(0)->hasOneUse()) |
| if(isa<LoadInst>(SI.getOperand(0))){ |
| ++NumIgnoredInst; |
| return; |
| } |
| Dest.getNode()->mergeTypeInfo(StoredTy, Dest.getOffset()); |
| } |
| |
| void GraphBuilder::visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) { |
| if (isa<PointerType>(I.getType())) { |
| visitInstruction (I); |
| return; |
| } |
| |
| // |
| // Create a DSNode for the dereferenced pointer . If the DSNode is NULL, do |
| // nothing more (this can occur if the pointer is a NULL constant; bugpoint |
| // can generate such code). |
| // |
| DSNodeHandle Ptr = getValueDest(I.getPointerOperand()); |
| if (Ptr.isNull()) return; |
| |
| // |
| // Make that the memory object is read and written. |
| // |
| Ptr.getNode()->setReadMarker(); |
| Ptr.getNode()->setModifiedMarker(); |
| |
| // |
| // If the result of the compare-and-swap is a pointer, then we need to do |
| // a few things: |
| // o Merge the compare and swap values (which are pointers) with the result |
| // o Merge the DSNode of the pointer *within* the memory object with the |
| // DSNode of the compare, swap, and result DSNode. |
| // |
| if (isa<PointerType>(I.getType())) { |
| // |
| // Get the DSNodeHandle of the memory object returned from the load. Make |
| // it the DSNodeHandle of the instruction's result. |
| // |
| DSNodeHandle FieldPtr = getLink (Ptr); |
| setDestTo(I, getLink(Ptr)); |
| |
| // |
| // Merge the result, compare, and swap values of the instruction. |
| // |
| FieldPtr.mergeWith (getValueDest (I.getCompareOperand())); |
| FieldPtr.mergeWith (getValueDest (I.getNewValOperand())); |
| } |
| |
| // |
| // Modify the DSNode so that it has the loaded/written type at the |
| // appropriate offset. |
| // |
| Ptr.getNode()->growSizeForType(I.getType(), Ptr.getOffset()); |
| Ptr.getNode()->mergeTypeInfo(I.getType(), Ptr.getOffset()); |
| return; |
| } |
| |
| void GraphBuilder::visitAtomicRMWInst(AtomicRMWInst &I) { |
| // |
| // Create a DSNode for the dereferenced pointer . If the DSNode is NULL, do |
| // nothing more (this can occur if the pointer is a NULL constant; bugpoint |
| // can generate such code). |
| // |
| DSNodeHandle Ptr = getValueDest(I.getPointerOperand()); |
| if (Ptr.isNull()) return; |
| |
| // |
| // Make that the memory object is read and written. |
| // |
| Ptr.getNode()->setReadMarker(); |
| Ptr.getNode()->setModifiedMarker(); |
| |
| // |
| // Modify the DSNode so that it has the loaded/written type at the |
| // appropriate offset. |
| // |
| Ptr.getNode()->growSizeForType(I.getType(), Ptr.getOffset()); |
| Ptr.getNode()->mergeTypeInfo(I.getType(), Ptr.getOffset()); |
| return; |
| } |
| |
| void GraphBuilder::visitReturnInst(ReturnInst &RI) { |
| if (RI.getNumOperands() && isa<PointerType>(RI.getOperand(0)->getType())) |
| G.getOrCreateReturnNodeFor(*FB).mergeWith(getValueDest(RI.getOperand(0))); |
| } |
| |
| void GraphBuilder::visitVAArgInst(VAArgInst &I) { |
| Module *M = FB->getParent(); |
| Triple TargetTriple(M->getTargetTriple()); |
| Triple::ArchType Arch = TargetTriple.getArch(); |
| switch(Arch) { |
| case Triple::x86_64: { |
| // On x86_64, we have va_list as a struct {i32, i32, i8*, i8* } |
| // The first i8* is where arguments generally go, but the second i8* can |
| // be used also to pass arguments by register. |
| // We model this by having both the i8*'s point to an array of pointers |
| // to the arguments. |
| DSNodeHandle Ptr = G.getVANodeFor(*FB); |
| DSNodeHandle Dest = getValueDest(&I); |
| if (Ptr.isNull()) return; |
| |
| // Make that the node is read and written |
| Ptr.getNode()->setReadMarker()->setModifiedMarker(); |
| |
| // Not updating type info, as it is already a collapsed node |
| |
| if (isa<PointerType>(I.getType())) |
| Dest.mergeWith(Ptr); |
| return; |
| } |
| |
| default: { |
| assert(0 && "What frontend generates this?"); |
| DSNodeHandle Ptr = getValueDest(I.getOperand(0)); |
| |
| //FIXME: also updates the argument |
| if (Ptr.isNull()) return; |
| |
| // Make that the node is read and written |
| Ptr.getNode()->setReadMarker()->setModifiedMarker(); |
| |
| // Ensure a type record exists. |
| DSNode *PtrN = Ptr.getNode(); |
| PtrN->mergeTypeInfo(I.getType(), Ptr.getOffset()); |
| |
| if (isa<PointerType>(I.getType())) |
| setDestTo(I, getLink(Ptr)); |
| } |
| } |
| } |
| |
| void GraphBuilder::visitIntToPtrInst(IntToPtrInst &I) { |
| DSNode *N = createNode(); |
| if(I.hasOneUse()) { |
| if(isa<ICmpInst>(*(I.user_begin()))) { |
| NumBoringIntToPtr++; |
| return; |
| } |
| } else { |
| N->setIntToPtrMarker(); |
| N->setUnknownMarker(); |
| } |
| setDestTo(I, N); |
| } |
| |
| void GraphBuilder::visitPtrToIntInst(PtrToIntInst& I) { |
| DSNode* N = getValueDest(I.getOperand(0)).getNode(); |
| if(I.hasOneUse()) { |
| if(isa<ICmpInst>(*(I.user_begin()))) { |
| NumBoringIntToPtr++; |
| return; |
| } |
| } |
| if(I.hasOneUse()) { |
| Value *V = dyn_cast<Value>(*(I.user_begin())); |
| DenseSet<Value *> Seen; |
| while(V && V->hasOneUse() && |
| Seen.insert(V).second) { |
| if(isa<LoadInst>(V)) |
| break; |
| if(isa<StoreInst>(V)) |
| break; |
| if(isa<CallInst>(V)) |
| break; |
| V = dyn_cast<Value>(*(V->user_begin())); |
| } |
| if(isa<BranchInst>(V)){ |
| NumBoringIntToPtr++; |
| return; |
| } |
| } |
| if(N) |
| N->setPtrToIntMarker(); |
| } |
| |
| |
| void GraphBuilder::visitBitCastInst(BitCastInst &I) { |
| if (!isa<PointerType>(I.getType())) return; // Only pointers |
| DSNodeHandle Ptr = getValueDest(I.getOperand(0)); |
| if (Ptr.isNull()) return; |
| setDestTo(I, Ptr); |
| } |
| |
| void GraphBuilder::visitCmpInst(CmpInst &I) { |
| //Address can escape through cmps |
| } |
| |
| unsigned getValueOffset(Type *Ty, ArrayRef<unsigned> Idxs, |
| const DataLayout &TD) { |
| unsigned Offset = 0; |
| for (ArrayRef<unsigned>::iterator I = Idxs.begin(), E = Idxs.end(); I != E; |
| ++I) { |
| // Lifted from DataLayout.cpp's getIndexedOffset. |
| // We can't use that because it insists on only allowing pointer types. |
| if (StructType *STy = dyn_cast<StructType>(Ty)) { |
| unsigned FieldNo = *I; |
| |
| // Get structure layout information... |
| const StructLayout *Layout = TD.getStructLayout(STy); |
| |
| // Add in the offset, as calculated by the structure layout info... |
| Offset += Layout->getElementOffset(FieldNo); |
| |
| // Update Ty to refer to current element |
| Ty = STy->getElementType(FieldNo); |
| } else { |
| // Update Ty to refer to current element |
| Ty = cast<SequentialType>(Ty)->getElementType(); |
| |
| // Get the array index and the size of each array element. |
| int64_t arrayIdx = *I; |
| Offset += (uint64_t)arrayIdx * TD.getTypeAllocSize(Ty); |
| } |
| } |
| return Offset; |
| } |
| |
| void GraphBuilder::visitInsertValueInst(InsertValueInst& I) { |
| setDestTo(I, createNode()->setAllocaMarker()); |
| |
| Type *StoredTy = I.getInsertedValueOperand()->getType(); |
| DSNodeHandle Dest = getValueDest(&I); |
| Dest.mergeWith(getValueDest(I.getAggregateOperand())); |
| |
| // Mark that the node is written to... |
| Dest.getNode()->setModifiedMarker(); |
| Type* STy = I.getAggregateOperand()->getType(); |
| |
| unsigned Offset = getValueOffset(STy, I.getIndices(), TD); |
| |
| // Ensure a type-record exists... |
| Dest.getNode()->mergeTypeInfo(StoredTy, Offset); |
| |
| // Avoid adding edges from null, or processing non-"pointer" stores |
| if (isa<PointerType>(StoredTy)) |
| Dest.addEdgeTo(getValueDest(I.getInsertedValueOperand())); |
| } |
| |
| void GraphBuilder::visitExtractValueInst(ExtractValueInst& I) { |
| DSNodeHandle Ptr = getValueDest(I.getAggregateOperand()); |
| |
| // Make that the node is read from... |
| Ptr.getNode()->setReadMarker(); |
| Type* STy = I.getAggregateOperand()->getType(); |
| |
| unsigned Offset = getValueOffset(STy, I.getIndices(), TD); |
| |
| // Ensure a typerecord exists... |
| Ptr.getNode()->mergeTypeInfo(I.getType(), Offset); |
| |
| if (isa<PointerType>(I.getType())) |
| setDestTo(I, getLink(Ptr)); |
| } |
| |
| void GraphBuilder::visitGetElementPtrInst(User &GEP) { |
| // |
| // Ensure that the indexed pointer has a DSNode. |
| // |
| DSNodeHandle NodeH = getValueDest(GEP.getOperand(0)); |
| if (NodeH.isNull()) |
| NodeH = createNode(); |
| |
| // |
| // There are a few quick and easy cases to handle. If the DSNode of the |
| // indexed pointer is already folded, then we know that the result of the |
| // GEP will have the same offset into the same DSNode |
| // as the indexed pointer. |
| // |
| |
| if (!NodeH.isNull() && |
| NodeH.getNode()->isNodeCompletelyFolded()) { |
| setDestTo(GEP, NodeH); |
| return; |
| } |
| |
| // |
| // Okay, no easy way out. Calculate the offset into the object being |
| // indexed. |
| // |
| |
| int Offset = 0; |
| |
| // FIXME: I am not sure if the code below is completely correct (especially |
| // if we start doing fancy analysis on non-constant array indices). |
| // What if the array is indexed using a larger index than its declared |
| // size? Does the LLVM verifier catch such issues? |
| // |
| |
| // |
| // Determine the offset (in bytes) between the result of the GEP and the |
| // GEP's pointer operand. |
| // |
| // Note: All of these subscripts are indexing INTO the elements we have... |
| // |
| // FIXME: We can do better for array indexing. First, if the array index is |
| // constant, we can determine how much farther we're moving the |
| // pointer. Second, we can try to use the results of other analysis |
| // passes (e.g., ScalarEvolution) to find min/max values to do less |
| // conservative type-folding. |
| // |
| for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP); |
| I != E; ++I) |
| if (StructType *STy = dyn_cast<StructType>(*I)) { |
| // indexing into a structure |
| // next index must be a constant |
| const ConstantInt* CUI = cast<ConstantInt>(I.getOperand()); |
| int FieldNo = CUI->getSExtValue(); |
| // increment the offset by the actual byte offset being accessed |
| |
| unsigned requiredSize = TD.getTypeAllocSize(STy) + NodeH.getOffset() + Offset; |
| |
| // |
| // Grow the DSNode size as needed. |
| // |
| if (!NodeH.getNode()->isArrayNode() || NodeH.getNode()->getSize() <= 0){ |
| if (requiredSize > NodeH.getNode()->getSize()) |
| NodeH.getNode()->growSize(requiredSize); |
| } |
| |
| Offset += (unsigned)TD.getStructLayout(STy)->getElementOffset(FieldNo); |
| if (TypeInferenceOptimize) { |
| if (ArrayType* AT = dyn_cast<ArrayType>(STy->getTypeAtIndex(FieldNo))) { |
| NodeH.getNode()->mergeTypeInfo(AT, NodeH.getOffset() + Offset); |
| if ((++I) == E) { |
| break; |
| } |
| |
| // Check if we are still indexing into an array. |
| // We only record the topmost array type of any nested array. |
| // Keep skipping indexes till we reach a non-array type. |
| // J is the type of the next index. |
| // Uncomment the line below to get all the nested types. |
| gep_type_iterator J = I; |
| while (isa<ArrayType>(*(++J))) { |
| // NodeH.getNode()->mergeTypeInfo(AT1, NodeH.getOffset() + Offset); |
| if((++I) == E) { |
| break; |
| } |
| J = I; |
| } |
| if ((I) == E) { |
| break; |
| } |
| } |
| } |
| } else if (ArrayType *ATy = dyn_cast<ArrayType>(*I)) { |
| // indexing into an array. |
| NodeH.getNode()->setArrayMarker(); |
| Type *CurTy = ATy->getElementType(); |
| |
| // |
| // Ensure that the DSNode's size is large enough to contain one |
| // element of the type to which the pointer points. |
| // |
| if (!isa<ArrayType>(CurTy) && NodeH.getNode()->getSize() <= 0) { |
| NodeH.getNode()->growSize(TD.getTypeAllocSize(CurTy)); |
| } else if(isa<ArrayType>(CurTy) && NodeH.getNode()->getSize() <= 0){ |
| Type *ETy = (cast<ArrayType>(CurTy))->getElementType(); |
| while(isa<ArrayType>(ETy)) { |
| ETy = (cast<ArrayType>(ETy))->getElementType(); |
| } |
| NodeH.getNode()->growSize(TD.getTypeAllocSize(ETy)); |
| } |
| |
| // Find if the DSNode belongs to the array |
| // If not fold. |
| if((NodeH.getOffset() || Offset != 0) |
| || (!isa<ArrayType>(CurTy) |
| && (NodeH.getNode()->getSize() != TD.getTypeAllocSize(CurTy)))) { |
| NodeH.getNode()->foldNodeCompletely(); |
| NodeH.getNode(); |
| Offset = 0; |
| break; |
| } |
| } else if (const PointerType *PtrTy = dyn_cast<PointerType>(*I)) { |
| // Get the type pointed to by the pointer |
| Type *CurTy = PtrTy->getElementType(); |
| |
| // |
| // Some LLVM transforms lower structure indexing into byte-level |
| // indexing. Try to recognize forms of that here. |
| // |
| Type * Int8Type = Type::getInt8Ty(CurTy->getContext()); |
| ConstantInt * IS = dyn_cast<ConstantInt>(I.getOperand()); |
| if (IS && |
| (NodeH.getOffset() == 0) && |
| (!(NodeH.getNode()->isArrayNode())) && |
| (CurTy == Int8Type)) { |
| // Calculate the offset of the field |
| Offset += IS->getSExtValue() * TD.getTypeAllocSize (Int8Type); |
| |
| // |
| // Grow the DSNode size as needed. |
| // |
| unsigned requiredSize = Offset + TD.getTypeAllocSize (Int8Type); |
| if (NodeH.getNode()->getSize() <= requiredSize){ |
| NodeH.getNode()->growSize (requiredSize); |
| } |
| |
| // Add in the offset calculated... |
| NodeH.setOffset(NodeH.getOffset()+Offset); |
| |
| // Check the offset |
| DSNode *N = NodeH.getNode(); |
| if (N) N->checkOffsetFoldIfNeeded(NodeH.getOffset()); |
| |
| // NodeH is now the pointer we want to GEP to be... |
| setDestTo(GEP, NodeH); |
| return; |
| } |
| |
| // |
| // Unless we're advancing the pointer by zero bytes via array indexing, |
| // fold the node (i.e., mark it type-unknown) and indicate that we're |
| // indexing zero bytes into the object (because all fields are aliased). |
| // |
| // Note that we break out of the loop if we fold the node. Once |
| // something is folded, all values within it are considered to alias. |
| // |
| if (!isa<Constant>(I.getOperand()) || |
| !cast<Constant>(I.getOperand())->isNullValue()) { |
| |
| // |
| // Treat the memory object (DSNode) as an array. |
| // |
| NodeH.getNode()->setArrayMarker(); |
| |
| // |
| // Ensure that the DSNode's size is large enough to contain one |
| // element of the type to which the pointer points. |
| // |
| if (!isa<ArrayType>(CurTy) && NodeH.getNode()->getSize() <= 0){ |
| NodeH.getNode()->growSize(TD.getTypeAllocSize(CurTy)); |
| } else if (isa<ArrayType>(CurTy) && NodeH.getNode()->getSize() <= 0){ |
| Type *ETy = (cast<ArrayType>(CurTy))->getElementType(); |
| while (isa<ArrayType>(ETy)) { |
| ETy = (cast<ArrayType>(ETy))->getElementType(); |
| } |
| NodeH.getNode()->growSize(TD.getTypeAllocSize(ETy)); |
| } |
| |
| // |
| // Fold the DSNode if we're indexing into it in a type-incompatible |
| // manner. That can occur if: |
| // 1) The DSNode represents a pointer into the object at a non-zero |
| // offset. |
| // 2) The offset of the pointer is already non-zero. |
| // 3) The size of the array element does not match the size into which |
| // the pointer indexing is indexing. |
| // |
| if (NodeH.getOffset() || Offset != 0 || |
| (!isa<ArrayType>(CurTy) && |
| (NodeH.getNode()->getSize() != TD.getTypeAllocSize(CurTy)))) { |
| NodeH.getNode()->foldNodeCompletely(); |
| NodeH.getNode(); |
| Offset = 0; |
| break; |
| } |
| } |
| } |
| |
| // Add in the offset calculated... |
| NodeH.setOffset(NodeH.getOffset()+Offset); |
| |
| // Check the offset |
| DSNode *N = NodeH.getNode(); |
| if (N) N->checkOffsetFoldIfNeeded(NodeH.getOffset()); |
| |
| // NodeH is now the pointer we want to GEP to be... |
| setDestTo(GEP, NodeH); |
| } |
| |
| |
| void GraphBuilder::visitCallInst(CallInst &CI) { |
| visitCallSite(&CI); |
| } |
| |
| void GraphBuilder::visitInvokeInst(InvokeInst &II) { |
| visitCallSite(&II); |
| } |
| |
| void GraphBuilder::visitVAStart(CallSite CS) { |
| // Build out DSNodes for the va_list depending on the target arch |
| // And assosiate the right node with the VANode for this function |
| // so it can be merged with the right arguments from callsites |
| |
| DSNodeHandle RetNH = getValueDest(CS.getArgument(0)); |
| |
| if (DSNode *N = RetNH.getNode()) |
| visitVAStartNode(N); |
| } |
| |
| void GraphBuilder::visitVAStartNode(DSNode* N) { |
| assert(N && "Null node as argument"); |
| assert(FB && "No function for this graph?"); |
| Module *M = FB->getParent(); |
| assert(M && "No module for function"); |
| Triple TargetTriple(M->getTargetTriple()); |
| Triple::ArchType Arch = TargetTriple.getArch(); |
| |
| // Fetch the VANode associated with the func containing the call to va_start |
| DSNodeHandle & VANH = G.getVANodeFor(*FB); |
| // Make sure this NodeHandle has a node to go with it |
| if (VANH.isNull()) VANH.mergeWith(createNode()); |
| |
| // Create a dsnode for an array of pointers to the VAInfo for this func |
| // We create one such array for each function analyzed, as all |
| // calls to va_start will populate their argument with the same data. |
| if (VAArrayNH.isNull()) VAArrayNH.mergeWith(createNode()); |
| VAArrayNH.getNode()->setArrayMarker(); |
| VAArrayNH.getNode()->foldNodeCompletely(); |
| VAArrayNH.setLink(0,VANH); |
| |
| //VAStart modifies its argument |
| N->setModifiedMarker(); |
| |
| // For the architectures we support, build dsnodes that match |
| // how we know va_list is used. |
| switch (Arch) { |
| case Triple::x86: |
| // On x86, we have: |
| // va_list as a pointer to an array of pointers to the variable arguments |
| if (!N->isCollapsedNode() && N->getSize() < 1) { |
| N->growSize(1); |
| } |
| N->addEdgeTo(0, VAArrayNH); |
| break; |
| case Triple::x86_64: |
| // On x86_64, we have va_list as a struct {i32, i32, i8*, i8* } |
| // The first i8* is where arguments generally go, but the second i8* can |
| // be used also to pass arguments by register. |
| // We model this by having both the i8*'s point to an array of pointers |
| // to the arguments. |
| if (!N->isCollapsedNode() && N->getSize() < 24) { |
| N->growSize(24); //sizeof the va_list struct mentioned above |
| } |
| N->addEdgeTo(8, VAArrayNH); // first i8* |
| N->addEdgeTo(16, VAArrayNH); // second i8* |
| |
| break; |
| default: |
| // FIXME: For now we abort if we don't know how to handle this arch |
| // Either add support for other architectures, or at least mark the |
| // nodes unknown/incomplete or whichever results in the correct |
| // conservative behavior in the general case |
| assert(0 && "VAstart not supported on this architecture!"); |
| //XXX: This might be good enough in those cases that we don't know |
| //what the arch does |
| N->setIncompleteMarker()->setUnknownMarker()->foldNodeCompletely(); |
| } |
| |
| // XXX: We used to set the alloca marker for the DSNode passed to va_start. |
| // Seems to me that you could allocate the va_list on the heap, so ignoring |
| // for now. |
| N->setModifiedMarker()->setVAStartMarker(); |
| } |
| |
| /// |
| /// Method: visitIntrinsic() |
| /// |
| /// Description: |
| /// Generate correct DSNodes for calls to LLVM intrinsic functions. |
| /// |
| /// Inputs: |
| /// CS - The CallSite representing the call or invoke to the intrinsic. |
| /// F - A pointer to the function called by the call site. |
| /// |
| /// Return value: |
| /// true - This intrinsic is properly handled by this method. |
| /// false - This intrinsic is not recognized by DSA. |
| /// |
| bool GraphBuilder::visitIntrinsic(CallSite CS, Function *F) { |
| ++NumIntrinsicCall; |
| |
| // |
| // If this is a debug intrinsic, then don't do any special processing. |
| // |
| if (isa<DbgInfoIntrinsic>(CS.getInstruction())) |
| return true; |
| |
| switch (F->getIntrinsicID()) { |
| case Intrinsic::vastart: { |
| visitVAStart(CS); |
| return true; |
| } |
| case Intrinsic::vacopy: { |
| // Simply merge the two arguments to va_copy. |
| // This results in loss of precision on the temporaries used to manipulate |
| // the va_list, and so isn't a big deal. In theory we would build a |
| // separate graph for this (like the one created in visitVAStartNode) |
| // and only merge the node containing the variable arguments themselves. |
| DSNodeHandle destNH = getValueDest(CS.getArgument(0)); |
| DSNodeHandle srcNH = getValueDest(CS.getArgument(1)); |
| destNH.mergeWith(srcNH); |
| return true; |
| } |
| case Intrinsic::stacksave: { |
| DSNode * Node = createNode(); |
| Node->setAllocaMarker()->setIncompleteMarker()->setUnknownMarker(); |
| Node->foldNodeCompletely(); |
| setDestTo (*(CS.getInstruction()), Node); |
| return true; |
| } |
| case Intrinsic::stackrestore: |
| getValueDest(CS.getInstruction()).getNode()->setAllocaMarker() |
| ->setIncompleteMarker() |
| ->setUnknownMarker() |
| ->foldNodeCompletely(); |
| return true; |
| case Intrinsic::vaend: |
| // TODO: What to do here? |
| return true; |
| case Intrinsic::memcpy: |
| case Intrinsic::memmove: { |
| // Merge the first & second arguments, and mark the memory read and |
| // modified. |
| DSNodeHandle RetNH = getValueDest(CS.getArgument(0)); |
| RetNH.mergeWith(getValueDest(CS.getArgument(1))); |
| if (DSNode *N = RetNH.getNode()) |
| N->setModifiedMarker()->setReadMarker(); |
| return true; |
| } |
| case Intrinsic::memset: |
| // Mark the memory modified. |
| if (DSNode *N = getValueDest(CS.getArgument(0)).getNode()) |
| N->setModifiedMarker(); |
| return true; |
| |
| // TODO: Add support for the new EH system |
| #if 0 |
| case Intrinsic::eh_exception: { |
| DSNode * Node = createNode(); |
| Node->setIncompleteMarker(); |
| Node->foldNodeCompletely(); |
| setDestTo (*(CS.getInstruction()), Node); |
| return true; |
| } |
| |
| case Intrinsic::eh_selector: { |
| for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); |
| I != E; ++I) { |
| if (isa<PointerType>((*I)->getType())) { |
| DSNodeHandle Ptr = getValueDest(*I); |
| if(Ptr.getNode()) { |
| Ptr.getNode()->setReadMarker(); |
| Ptr.getNode()->setIncompleteMarker(); |
| } |
| } |
| } |
| return true; |
| } |
| #endif |
| |
| case Intrinsic::eh_typeid_for: { |
| DSNodeHandle Ptr = getValueDest(CS.getArgument(0)); |
| Ptr.getNode()->setReadMarker(); |
| Ptr.getNode()->setIncompleteMarker(); |
| return true; |
| } |
| |
| case Intrinsic::prefetch: |
| return true; |
| |
| case Intrinsic::objectsize: |
| return true; |
| |
| // |
| // The return address/frame address aliases with the stack, |
| // is type-unknown, and should |
| // have the unknown flag set since we don't know where it goes. |
| // |
| case Intrinsic::returnaddress: |
| case Intrinsic::frameaddress: { |
| DSNode * Node = createNode(); |
| Node->setAllocaMarker()->setIncompleteMarker()->setUnknownMarker(); |
| Node->foldNodeCompletely(); |
| setDestTo (*(CS.getInstruction()), Node); |
| return true; |
| } |
| |
| // Process lifetime intrinsics |
| case Intrinsic::lifetime_start: |
| case Intrinsic::lifetime_end: |
| case Intrinsic::invariant_start: |
| case Intrinsic::invariant_end: |
| return true; |
| |
| default: { |
| //ignore pointer free intrinsics |
| if (!isa<PointerType>(F->getReturnType())) { |
| bool hasPtr = false; |
| for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); |
| I != E && !hasPtr; ++I) |
| if (isa<PointerType>(I->getType())) |
| hasPtr = true; |
| if (!hasPtr) |
| return true; |
| } |
| |
| DEBUG(errs() << "[dsa:local] Unhandled intrinsic: " << F->getName() << "\n"); |
| assert(0 && "Unhandled intrinsic"); |
| return false; |
| } |
| } |
| } |
| |
| void GraphBuilder::visitCallSite(CallSite CS) { |
| // |
| // Get the called value. Strip off any casts which are lossless. |
| // |
| Value *Callee = CS.getCalledValue()->stripPointerCasts(); |
| |
| // Special case handling of certain libc allocation functions here. |
| if (Function *F = dyn_cast<Function>(Callee)) |
| if (F->isIntrinsic() && visitIntrinsic(CS, F)) |
| return; |
| |
| //Can't do much about inline asm (yet!) |
| if (isa<InlineAsm> (Callee)) { |
| ++NumAsmCall; |
| DSNodeHandle RetVal; |
| Instruction *I = CS.getInstruction(); |
| if (isa<PointerType > (I->getType())) |
| RetVal = getValueDest(I); |
| |
| // Calculate the arguments vector... |
| for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) |
| if (isa<PointerType > ((*I)->getType())) |
| RetVal.mergeWith(getValueDest(*I)); |
| if (!RetVal.isNull()) |
| RetVal.getNode()->foldNodeCompletely(); |
| return; |
| } |
| |
| // Set up the return value... |
| DSNodeHandle RetVal; |
| Instruction *I = CS.getInstruction(); |
| if (isa<PointerType>(I->getType())) |
| RetVal = getValueDest(I); |
| |
| DSNode *CalleeNode = 0; |
| if (!isa<Function>(Callee)) { |
| CalleeNode = getValueDest(Callee).getNode(); |
| if (CalleeNode == 0) { |
| DEBUG(errs() << "WARNING: Program is calling through a null pointer?\n" << *I); |
| return; // Calling a null pointer? |
| } |
| } |
| |
| // NOTE: This code is identical to 'DSGraph::getDSCallSiteForCallSite', |
| // the reason it's duplicated is because this calls getValueDest instead |
| // of getNodeForValue to get the DSNodes for the arguments. Since we're in |
| // local it's possible that we need to create a DSNode for the argument, as |
| // opposed to getNodeForValue which simply retrieves the existing node. |
| |
| |
| //Get the FunctionType for the called function |
| const FunctionType *CalleeFuncType = DSCallSite::FunctionTypeOfCallSite(CS); |
| int NumFixedArgs = CalleeFuncType->getNumParams(); |
| |
| // Sanity check--this really, really shouldn't happen |
| if (!CalleeFuncType->isVarArg()) |
| assert(CS.arg_size() == static_cast<unsigned>(NumFixedArgs) && |
| "Too many arguments/incorrect function signature!"); |
| |
| std::vector<DSNodeHandle> Args; |
| Args.reserve(CS.arg_size()); |
| DSNodeHandle VarArgNH; |
| |
| // Calculate the arguments vector... |
| // Add all fixed pointer arguments, then merge the rest together |
| for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); |
| I != E; ++I) |
| if (isa<PointerType>((*I)->getType())) { |
| DSNodeHandle ArgNode = getValueDest(*I); |
| if (I - CS.arg_begin() < NumFixedArgs) { |
| Args.push_back(ArgNode); |
| } else { |
| VarArgNH.mergeWith(ArgNode); |
| } |
| } |
| |
| // Add a new function call entry... |
| if (CalleeNode) { |
| ++NumIndirectCall; |
| G.getFunctionCalls().push_back(DSCallSite(CS, RetVal, VarArgNH, CalleeNode, |
| Args)); |
| } else { |
| ++NumDirectCall; |
| G.getFunctionCalls().push_back(DSCallSite(CS, RetVal, VarArgNH, |
| cast<Function>(Callee), |
| Args)); |
| } |
| |
| |
| } |
| |
| // visitInstruction - For all other instruction types, if we have any arguments |
| // that are of pointer type, make them have unknown composition bits, and merge |
| // the nodes together. |
| void GraphBuilder::visitInstruction(Instruction &Inst) { |
| DSNodeHandle CurNode; |
| if (isa<PointerType>(Inst.getType())) |
| CurNode = getValueDest(&Inst); |
| for (User::op_iterator I = Inst.op_begin(), E = Inst.op_end(); I != E; ++I) |
| if (isa<PointerType>((*I)->getType())) |
| CurNode.mergeWith(getValueDest(*I)); |
| |
| if (DSNode *N = CurNode.getNode()) |
| N->setUnknownMarker(); |
| } |
| |
| |
| |
| //===----------------------------------------------------------------------===// |
| // LocalDataStructures Implementation |
| //===----------------------------------------------------------------------===// |
| |
| // |
| // Function: MergeConstantInitIntoNode() |
| // |
| // Description: |
| // Merge the specified constant into the specified DSNode. |
| // |
| void |
| GraphBuilder::MergeConstantInitIntoNode(DSNodeHandle &NH, |
| Type* Ty, |
| Constant *C) { |
| // |
| // Ensure a type-record exists... |
| // |
| DSNode *NHN = NH.getNode(); |
| //NHN->mergeTypeInfo(Ty, NH.getOffset()); |
| |
| // |
| // If we've found something of pointer type, create or find its DSNode and |
| // make a link from the specified DSNode to the new DSNode describing the |
| // pointer we've just found. |
| // |
| if (isa<PointerType>(Ty)) { |
| NHN->mergeTypeInfo(Ty, NH.getOffset()); |
| NH.addEdgeTo(getValueDest(C)); |
| return; |
| } |
| |
| // |
| // If the type of the object (array element, structure field, etc.) is an |
| // integer or floating point type, then just ignore it. It has no DSNode. |
| // |
| if (Ty->isIntOrIntVectorTy() || Ty->isFPOrFPVectorTy()) return; |
| |
| // |
| // Handle aggregate constants. |
| // |
| if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) { |
| // |
| // For an array, we don't worry about different elements pointing to |
| // different objects; we essentially pretend that all array elements alias. |
| // |
| Type * ElementType = cast<ArrayType>(Ty)->getElementType(); |
| for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) { |
| Constant * ConstElement = cast<Constant>(CA->getOperand(i)); |
| MergeConstantInitIntoNode(NH, ElementType, ConstElement); |
| } |
| } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) { |
| // |
| // For a structure, we need to merge each element of the constant structure |
| // into the specified DSNode. However, we must also handle structures that |
| // end with a zero-length array ([0 x sbyte]); this is a common C idiom |
| // that continues to plague the world. |
| // |
| //NHN->mergeTypeInfo(Ty, NH.getOffset()); |
| |
| const StructLayout *SL = TD.getStructLayout(cast<StructType>(Ty)); |
| |
| for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) { |
| DSNode *NHN = NH.getNode(); |
| if (SL->getElementOffset(i) < SL->getSizeInBytes()) { |
| // |
| // Get the type and constant value of this particular element of the |
| // constant structure. |
| // |
| Type * ElementType = cast<StructType>(Ty)->getElementType(i); |
| Constant * ConstElement = cast<Constant>(CS->getOperand(i)); |
| |
| // |
| // Get the offset (in bytes) into the memory object that we're |
| // analyzing. |
| // |
| unsigned offset = NH.getOffset()+(unsigned)SL->getElementOffset(i); |
| NHN->mergeTypeInfo(ElementType, offset); |
| // |
| // Create a new DSNodeHandle. This DSNodeHandle will point to the same |
| // DSNode as the one we're constructing for our caller; however, it |
| // will point into a different offset into that DSNode. |
| // |
| DSNodeHandle NewNH (NHN, offset); |
| assert ((NHN->isNodeCompletelyFolded() || (NewNH.getOffset() == offset)) |
| && "Need to resize DSNode!"); |
| |
| // |
| // Recursively merge in this element of the constant struture into the |
| // DSNode. |
| // |
| MergeConstantInitIntoNode(NewNH, ElementType, ConstElement); |
| } else if (SL->getElementOffset(i) == SL->getSizeInBytes()) { |
| // |
| // If this is one of those cute structures that ends with a zero-length |
| // array, just fold the DSNode now and get it over with. |
| // |
| DEBUG(errs() << "Zero size element at end of struct\n" ); |
| NHN->foldNodeCompletely(); |
| } else { |
| assert(0 && "type was smaller than offsets of struct layout indicate"); |
| } |
| } |
| } else if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) { |
| // |
| // Undefined values and NULL pointers have no DSNodes, so they do nothing. |
| // |
| } else if (isa<ConstantDataSequential>(C)) { |
| // |
| // ConstantDataSequential's are arrays of integers or floats, so they |
| // have no DSNodes. Nothing to do here. |
| // |
| } else { |
| assert(0 && "Unknown constant type!"); |
| } |
| } |
| |
| void GraphBuilder::mergeInGlobalInitializer(GlobalVariable *GV) { |
| // Ensure that the global variable is not external |
| assert(!GV->isDeclaration() && "Cannot merge in external global!"); |
| |
| // |
| // Get a node handle to the global node and merge the initializer into it. |
| // |
| DSNodeHandle NH = getValueDest(GV); |
| |
| // |
| // Ensure that the DSNode is large enough to hold the new constant that we'll |
| // be adding to it. |
| // |
| Type * ElementType = GV->getType()->getElementType(); |
| while(ArrayType *ATy = dyn_cast<ArrayType>(ElementType)) { |
| ElementType = ATy->getElementType(); |
| } |
| if(!NH.getNode()->isNodeCompletelyFolded()) { |
| unsigned requiredSize = TD.getTypeAllocSize(ElementType) + NH.getOffset(); |
| if (NH.getNode()->getSize() < requiredSize){ |
| NH.getNode()->growSize (requiredSize); |
| } |
| } |
| |
| // |
| // Do the actual merging in of the constant initializer. |
| // |
| MergeConstantInitIntoNode(NH, GV->getType()->getElementType(), GV->getInitializer()); |
| |
| } |
| |
| void GraphBuilder::mergeExternalGlobal(GlobalVariable *GV) { |
| // Get a node handle to the global node and merge the initializer into it. |
| DSNodeHandle NH = getValueDest(GV); |
| } |
| |
| // some evil programs use sections as linker generated arrays |
| // read a description of this behavior in and apply it |
| // format: numglobals section globals... |
| // terminates when numglobals == 0 |
| void handleMagicSections(DSGraph* GlobalsGraph, Module& M) { |
| std::ifstream msf(hasMagicSections.c_str(), std::ifstream::in); |
| if (msf.good()) { |
| //no checking happens here |
| unsigned count = 0; |
| msf >> count; |
| while (count) { |
| std::string section; |
| msf >> section; |
| svset<Value*> inSection; |
| for (Module::iterator MI = M.begin(), ME = M.end(); |
| MI != ME; ++MI) |
| if (MI->hasSection() && MI->getSection() == section) |
| inSection.insert(MI); |
| for (Module::global_iterator MI = M.global_begin(), ME = M.global_end(); |
| MI != ME; ++MI) |
| if (MI->hasSection() && MI->getSection() == section) |
| inSection.insert(MI); |
| |
| for (unsigned x = 0; x < count; ++x) { |
| std::string global; |
| msf >> global; |
| Value* V = M.getNamedValue(global); |
| if (V) { |
| DSNodeHandle& DHV = GlobalsGraph->getNodeForValue(V); |
| for (svset<Value*>::iterator SI = inSection.begin(), |
| SE = inSection.end(); SI != SE; ++SI) { |
| DEBUG(errs() << "Merging " << V->getName().str() << " with " |
| << (*SI)->getName().str() << "\n"); |
| GlobalsGraph->getNodeForValue(*SI).mergeWith(DHV); |
| } |
| } |
| } |
| msf >> count; |
| } |
| } else { |
| errs() << "Failed to open magic sections file:" << hasMagicSections << |
| "\n"; |
| } |
| } |
| |
| char LocalDataStructures::ID; |
| |
| bool LocalDataStructures::runOnModule(Module &M) { |
| init(&getAnalysis<DataLayoutPass>().getDataLayout()); |
| addrAnalysis = &getAnalysis<AddressTakenAnalysis>(); |
| |
| // First step, build the globals graph. |
| { |
| GraphBuilder GGB(*GlobalsGraph); |
| |
| // Add initializers for all of the globals to the globals graph. |
| for (Module::global_iterator I = M.global_begin(), E = M.global_end(); |
| I != E; ++I) |
| if (!(I->hasSection() && I->getSection() == "llvm.metadata")) { |
| if (I->isDeclaration()) |
| GGB.mergeExternalGlobal(I); |
| else |
| GGB.mergeInGlobalInitializer(I); |
| } |
| // Add Functions to the globals graph. |
| for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI){ |
| if(addrAnalysis->hasAddressTaken(FI)) { |
| GGB.mergeFunction(FI); |
| } |
| } |
| } |
| |
| if (hasMagicSections.size()) |
| handleMagicSections(GlobalsGraph, M); |
| |
| // Next step, iterate through the nodes in the globals graph, unioning |
| // together the globals into equivalence classes. |
| formGlobalECs(); |
| |
| // Iterate through the address taken functions in the globals graph, |
| // collecting them in a list, to be used as target for call sites that |
| // cant be resolved. |
| formGlobalFunctionList(); |
| GlobalsGraph->maskIncompleteMarkers(); |
| |
| // Calculate all of the graphs... |
| for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) |
| if (!I->isDeclaration()) { |
| DSGraph* G = new DSGraph(GlobalECs, getDataLayout(), *TypeSS, GlobalsGraph); |
| GraphBuilder GGB(*I, *G, *this); |
| G->getAuxFunctionCalls() = G->getFunctionCalls(); |
| setDSGraph(*I, G); |
| propagateUnknownFlag(G); |
| callgraph.insureEntry(I); |
| G->buildCallGraph(callgraph, GlobalFunctionList, true); |
| G->maskIncompleteMarkers(); |
| G->markIncompleteNodes(DSGraph::MarkFormalArgs |
| |DSGraph::IgnoreGlobals); |
| cloneIntoGlobals(G, DSGraph::DontCloneCallNodes | |
| DSGraph::DontCloneAuxCallNodes | |
| DSGraph::StripAllocaBit); |
| formGlobalECs(); |
| DEBUG(G->AssertGraphOK()); |
| } |
| |
| //GlobalsGraph->removeTriviallyDeadNodes(); |
| GlobalsGraph->markIncompleteNodes(DSGraph::MarkFormalArgs |
| |DSGraph::IgnoreGlobals); |
| GlobalsGraph->computeExternalFlags(DSGraph::ProcessCallSites); |
| |
| // Now that we've computed all of the graphs, and merged all of the info into |
| // the globals graph, see if we have further constrained the globals in the |
| // program if so, update GlobalECs and remove the extraneous globals from the |
| // program. |
| formGlobalECs(); |
| |
| propagateUnknownFlag(GlobalsGraph); |
| for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) |
| if (!I->isDeclaration()) { |
| DSGraph *Graph = getOrCreateGraph(I); |
| Graph->maskIncompleteMarkers(); |
| cloneGlobalsInto(Graph, DSGraph::DontCloneCallNodes | |
| DSGraph::DontCloneAuxCallNodes); |
| Graph->markIncompleteNodes(DSGraph::MarkFormalArgs |
| |DSGraph::IgnoreGlobals); |
| } |
| |
| return false; |
| } |
| |