| //===-- StructureFieldVisitor.cpp - Implement StructureFieldVisitor -------===// |
| // |
| // 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 file implements the StructureFieldVisitor and related classes. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "StructureFieldVisitor.h" |
| #include "llvm/Constants.h" |
| #include "llvm/DerivedTypes.h" |
| #include "llvm/Analysis/DataStructure/DataStructure.h" |
| #include "llvm/Analysis/DataStructure/DSGraph.h" |
| #include "llvm/Intrinsics.h" |
| #include "llvm/Support/InstVisitor.h" |
| #include <algorithm> |
| #include <iostream> |
| |
| using namespace llvm::Macroscopic; |
| using namespace llvm; |
| |
| /// FindAllDataStructures - Inspect the program specified by ECG, adding to |
| /// 'Nodes' all of the data structures node in the program that contain the |
| /// "IncludeFlags" and do not contain "ExcludeFlags" node flags. If |
| /// OnlyHomogenous is true, only type-homogenous nodes are considered. |
| void FindAllDataStructures(std::set<DSNode*> &Nodes, unsigned IncludeFlags, |
| unsigned ExcludeFlags, bool OnlyHomogenous, |
| EquivClassGraphs &ECG) { |
| // Loop over all of the graphs in ECG, finding nodes that are not incomplete |
| // and do not have any of the flags specified by Flags. |
| ExcludeFlags |= DSNode::Incomplete; |
| |
| /// FIXME: nodes in the global graph should not be marked incomplete in main!! |
| for (hash_map<const Function*, DSGraph*>::iterator GI = ECG.DSInfo.begin(), |
| E = ECG.DSInfo.end(); GI != E; ++GI) { |
| assert(GI->second && "Null graph pointer?"); |
| DSGraph &G = *GI->second; |
| for (DSGraph::node_iterator I = G.node_begin(), E = G.node_end(); |
| I != E; ++I) |
| // If this node matches our constraints, include it. |
| if ((I->getNodeFlags() & IncludeFlags) == IncludeFlags && |
| (I->getNodeFlags() & ExcludeFlags) == 0) |
| if (!OnlyHomogenous || !I->isNodeCompletelyFolded()) |
| Nodes.insert(I); |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // LatticeValue class implementation |
| // |
| |
| DSGraph &LatticeValue::getParentGraph() const { |
| DSGraph *PG = getNode()->getParentGraph(); |
| assert(PG && "Node doesn't have a parent, is it a GlobalGraph node?"); |
| return *PG; |
| } |
| |
| /// getFieldOffset - Return the offset of this field from the start of the node. |
| /// |
| unsigned LatticeValue::getFieldOffset() const { |
| const TargetData &TD = getNode()->getParentGraph()->getTargetData(); |
| |
| unsigned Offset = 0; |
| const Type *Ty = Node->getType(); |
| for (unsigned i = 0, e = Idxs.size(); i != e; ++i) |
| if (const StructType *STy = dyn_cast<StructType>(Ty)) { |
| const StructLayout *SL = TD.getStructLayout(STy); |
| Offset += SL->MemberOffsets[Idxs[i]]; |
| Ty = STy->getElementType(Idxs[i]); |
| } else { |
| const SequentialType *STy = cast<SequentialType>(Ty); |
| Ty = STy->getElementType(); |
| --i; // This doesn't index a struct. |
| } |
| return Offset; |
| } |
| |
| |
| |
| void LatticeValue::dump() const { |
| std::cerr << "\nFunction: " << Node->getParentGraph()->getFunctionNames() |
| << "\n"; |
| Node->dump(); |
| if (!Idxs.empty()) { |
| std::cerr << "Field: "; |
| for (unsigned i = 0, e = Idxs.size(); i != e; ++i) |
| std::cerr << Idxs[i] << "."; |
| } |
| std::cerr << "\n"; |
| } |
| |
| bool LatticeValue::visitLoad(LoadInst &) { |
| std::cerr << "ERROR: Client requested load visitation, but did not " |
| << "overload visitLoad!\n"; |
| dump(); |
| return true; |
| } |
| bool LatticeValue::visitStore(StoreInst &) { |
| std::cerr << "ERROR: Client requested store visitation, but did not " |
| << "overload visitStore!\n"; |
| dump(); |
| return true; |
| } |
| |
| bool LatticeValue::visitGlobalInit(Constant *) { |
| std::cerr << "ERROR: Client requested store visitation, but did not " |
| << "overload visitGlobalInit!\n"; |
| dump(); |
| return true; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // SFVInstVisitor class implementation |
| // |
| |
| namespace { |
| /// SFVInstVisitor - This visitor is used to do the actual visitation of |
| /// memory instructions in the program. |
| /// |
| struct SFVInstVisitor : public InstVisitor<SFVInstVisitor, bool> { |
| DSGraph &DSG; |
| const unsigned Callbacks; |
| std::multimap<DSNode*, LatticeValue*> &NodeLVs; |
| |
| // DirectCallSites - When we see call sites, we don't process them, but we |
| // do remember them if they are direct calls. |
| std::set<Instruction*> DirectCallSites; |
| |
| SFVInstVisitor(DSGraph &dsg, unsigned CBs, |
| std::multimap<DSNode*, LatticeValue*> &LVs) |
| : DSG(dsg), Callbacks(CBs), NodeLVs(LVs) {} |
| |
| // Methods used by visitation methods. |
| LatticeValue *getLatticeValueForField(Value *Ptr); |
| bool RemoveLatticeValueAtBottom(LatticeValue *LV); |
| |
| /// Visitation methods - These methods should return true when a lattice |
| /// value is driven to 'bottom' and removed from NodeLVs. |
| bool visitLoadInst(LoadInst &LI); |
| bool visitStoreInst(StoreInst &SI); |
| |
| /// These are not implemented yet. |
| bool visitGetElementPtrInst(GetElementPtrInst &GEPI) { return false; } |
| bool visitMallocInst(MallocInst &MI) { return false; } |
| bool visitAllocaInst(AllocaInst &AI) { return false; } |
| bool visitFreeInst(FreeInst &FI) { return false; } |
| bool visitPHINode(PHINode &PN) { return false; } |
| bool visitSelectInst(SelectInst &SI) { return false; } |
| bool visitSetCondInst(SetCondInst &SCI) { return false; } |
| bool visitCastInst(CastInst &CI) { return false; } |
| bool visitReturnInst(ReturnInst &RI) { return false; } |
| |
| // visitCallInst/visitInvokeInst - Call and invoke are handled specially, so |
| // they are just noops here. |
| bool visitCallInst(CallInst &CI) { return visitCallSite(CI); } |
| bool visitInvokeInst(InvokeInst &II) { return visitCallSite(II); } |
| bool visitCallSite(Instruction &I) { |
| // Remember direct function calls. |
| if (isa<Function>(I.getOperand(0))) DirectCallSites.insert(&I); |
| return false; |
| } |
| |
| bool visitInstruction(Instruction &I) { |
| #ifndef NDEBUG |
| // Check to make sure this instruction really isn't using anything we the |
| // client needs to know about. |
| assert(getLatticeValueForField(&I) == 0 && "Inst should be handled!"); |
| for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) |
| assert(getLatticeValueForField(I.getOperand(i)) == 0 && |
| "Inst should be handled by visitor!"); |
| #endif |
| return false; |
| } |
| }; |
| } |
| |
| static void ComputeStructureFieldIndices(const Type *Ty, unsigned Offset, |
| std::vector<unsigned> &Idxs, |
| const TargetData &TD) { |
| if (Ty->isFirstClassType()) { |
| assert(Offset == 0 && "Illegal structure index!"); |
| return; |
| } |
| |
| if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) { |
| ComputeStructureFieldIndices(STy->getElementType(), Offset, Idxs, TD); |
| } else if (const StructType *STy = dyn_cast<StructType>(Ty)) { |
| const StructLayout *SL = TD.getStructLayout(STy); |
| |
| std::vector<uint64_t>::const_iterator SI = |
| std::upper_bound(SL->MemberOffsets.begin(), SL->MemberOffsets.end(), |
| Offset); |
| assert(SI != SL->MemberOffsets.begin() && "Offset not in structure type!"); |
| --SI; |
| assert(*SI <= Offset && "upper_bound didn't work"); |
| assert((SI == SL->MemberOffsets.begin() || *(SI-1) < Offset) && |
| (SI+1 == SL->MemberOffsets.end() || *(SI+1) > Offset) && |
| "Upper bound didn't work!"); |
| Offset -= *SI; // Skip over the offset to this structure field. |
| unsigned Idx = SI - SL->MemberOffsets.begin(); |
| assert(Idx < STy->getNumElements() && "Illegal structure index"); |
| Idxs.push_back(Idx); |
| ComputeStructureFieldIndices(STy->getElementType(Idx), Offset, Idxs, TD); |
| } else { |
| assert(0 && "Unknown type to index into!"); |
| } |
| } |
| |
| LatticeValue *SFVInstVisitor::getLatticeValueForField(Value *Ptr) { |
| if (!isa<PointerType>(Ptr->getType()) || |
| isa<ConstantPointerNull>(Ptr)) return 0; |
| |
| const DSNodeHandle *NH = &DSG.getNodeForValue(Ptr); |
| DSNode *Node = NH->getNode(); |
| assert(Node && "Pointer doesn't have node??"); |
| |
| std::multimap<DSNode*, LatticeValue*>::iterator I = NodeLVs.find(Node); |
| if (I == NodeLVs.end()) return 0; // Not a node we are still tracking. |
| |
| // Okay, next convert the node offset to a field index expression. |
| std::vector<unsigned> Idxs; |
| ComputeStructureFieldIndices(Node->getType(), NH->getOffset(), Idxs, |
| Node->getParentGraph()->getTargetData()); |
| |
| for (; I != NodeLVs.end() && I->first == Node; ++I) |
| if (I->second->getIndices() == Idxs) |
| return I->second; |
| return 0; |
| } |
| |
| /// RemoveLatticeValueAtBottom - When analysis determines that LV hit bottom, |
| /// this method is used to remove it from the NodeLVs map. This method always |
| /// returns true to simplify caller code. |
| /// |
| bool SFVInstVisitor::RemoveLatticeValueAtBottom(LatticeValue *LV) { |
| for (std::multimap<DSNode*, LatticeValue*>::iterator I |
| = NodeLVs.find(LV->getNode());; ++I) { |
| assert(I != NodeLVs.end() && "Lattice value not in map??"); |
| if (I->second == LV) { |
| NodeLVs.erase(I); |
| return true; |
| } |
| } |
| } |
| |
| |
| bool SFVInstVisitor::visitLoadInst(LoadInst &LI) { |
| if ((Callbacks & Visit::Loads) == 0) return false; |
| |
| if (LatticeValue *LV = getLatticeValueForField(LI.getOperand(0))) |
| if (LV->visitLoad(LI)) |
| return RemoveLatticeValueAtBottom(LV); |
| |
| return false; |
| } |
| |
| bool SFVInstVisitor::visitStoreInst(StoreInst &SI) { |
| if ((Callbacks & Visit::Stores) == 0) return false; |
| |
| if (LatticeValue *LV = getLatticeValueForField(SI.getOperand(1))) |
| if (LV->visitStore(SI)) |
| return RemoveLatticeValueAtBottom(LV); |
| |
| return false; |
| } |
| |
| |
| //===----------------------------------------------------------------------===// |
| // StructureFieldVisitorBase class implementation |
| // |
| |
| void StructureFieldVisitorBase:: |
| AddLatticeValuesForFields(DSNode *Node, const Type *Ty, |
| const std::vector<unsigned> &Idxs, |
| std::set<LatticeValue*> &Values) { |
| if (Ty->isFirstClassType()) { |
| if (LatticeValue *LV = createLatticeValue(Node, Idxs, Ty)) |
| Values.insert(LV); |
| return; |
| } |
| |
| const StructType *STy = dyn_cast<StructType>(Ty); |
| if (STy == 0) return; // Not handling arrays yet! |
| |
| std::vector<unsigned> NextIdxs(Idxs); |
| NextIdxs.push_back(0); |
| for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { |
| NextIdxs.back() = i; |
| AddLatticeValuesForFields(Node, STy->getElementType(i), NextIdxs, Values); |
| } |
| } |
| |
| void StructureFieldVisitorBase:: |
| AddLatticeValuesForNode(DSNode *N, std::set<LatticeValue*> &Values) { |
| if (N->isNodeCompletelyFolded() || |
| N->getType() == Type::VoidTy) return; // Can't analyze node. |
| std::vector<unsigned> Idxs; |
| AddLatticeValuesForFields(N, N->getType(), Idxs, Values); |
| } |
| |
| |
| /// visitNodes - This is a simple wrapper around visitFields that creates a |
| /// lattice value for every field in the specified collection of nodes. |
| /// |
| std::set<LatticeValue*> StructureFieldVisitorBase:: |
| visitNodes(const std::set<DSNode*> &Nodes) { |
| std::set<LatticeValue*> Result; |
| |
| // Create lattice values for all of the fields in these nodes. |
| for (std::set<DSNode*>::const_iterator I = Nodes.begin(), E = Nodes.end(); |
| I != E; ++I) |
| AddLatticeValuesForNode(*I, Result); |
| |
| // Now that we have the lattice values, just use visitFields to do the grunt |
| // work. |
| visitFields(Result); |
| return Result; |
| } |
| |
| |
| /// VisitGlobalInit - The specified lattice value corresponds to a field (or |
| /// several) in the specified global. Merge all of the overlapping initializer |
| /// values into LV (up-to and until it becomes overdefined). |
| /// |
| static bool VisitGlobalInit(LatticeValue *LV, Constant *Init, |
| unsigned FieldOffset) { |
| const TargetData &TD = LV->getParentGraph().getTargetData(); |
| |
| if (Init->isNullValue()) |
| return LV->visitGlobalInit(Constant::getNullValue(LV->getFieldType())); |
| if (isa<UndefValue>(Init)) |
| return LV->visitGlobalInit(UndefValue::get(LV->getFieldType())); |
| |
| if (LV->getNode()->isArray() && |
| TD.getTypeSize(Init->getType()) > LV->getNode()->getSize()) { |
| ConstantArray *CA = cast<ConstantArray>(Init); |
| for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) |
| if (VisitGlobalInit(LV, CA->getOperand(i), FieldOffset)) |
| return true; |
| return false; |
| } |
| |
| NextStep: // Manual tail recursion |
| |
| if (Init->isNullValue()) |
| return LV->visitGlobalInit(Constant::getNullValue(LV->getFieldType())); |
| if (isa<UndefValue>(Init)) |
| return LV->visitGlobalInit(UndefValue::get(LV->getFieldType())); |
| if (Init->getType()->isFirstClassType()) { |
| assert(FieldOffset == 0 && "GV Init mismatch!"); |
| return LV->visitGlobalInit(Init); |
| } |
| |
| if (const StructType *STy = dyn_cast<StructType>(Init->getType())) { |
| const StructLayout *SL = TD.getStructLayout(STy); |
| unsigned Field = SL->getElementContainingOffset(FieldOffset); |
| FieldOffset -= SL->MemberOffsets[Field]; |
| Init = cast<ConstantStruct>(Init)->getOperand(Field); |
| goto NextStep; |
| } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) { |
| unsigned ElSz = TD.getTypeSize(ATy->getElementType()); |
| unsigned Idx = FieldOffset / ElSz; |
| FieldOffset -= Idx*ElSz; |
| Init = cast<ConstantArray>(Init)->getOperand(Idx); |
| goto NextStep; |
| } else { |
| assert(0 && "Unexpected initializer type!"); |
| return true; |
| } |
| } |
| |
| |
| /// visitFields - Visit all uses of the specified fields, updating the lattice |
| /// values as appropriate. |
| /// |
| void StructureFieldVisitorBase::visitFields(std::set<LatticeValue*> &Fields) { |
| // Now that we added all of the initial nodes, find out what graphs these |
| // nodes are rooted in. For efficiency, handle batches of nodes in the same |
| // function together at the same time. To do this, pull everything out of |
| // Fields and put it into FieldsByGraph. |
| std::multimap<DSGraph*, LatticeValue*> FieldsByGraph; |
| while (!Fields.empty()) { |
| LatticeValue *LV = *Fields.begin(); |
| Fields.erase(Fields.begin()); |
| FieldsByGraph.insert(std::make_pair(&LV->getParentGraph(), LV)); |
| } |
| |
| // Now that everything is grouped by graph, process a graph worth of nodes at |
| // a time, moving the results back to Fields if they are not overdefined. |
| while (!FieldsByGraph.empty()) { |
| // NodeLVs - Inspect all of the lattice values that are active in this |
| // graph. |
| std::multimap<DSNode*, LatticeValue*> NodeLVs; |
| DSGraph &DSG = *FieldsByGraph.begin()->first; |
| |
| // Pull out all nodes in this graph, putting them into NodeLVs. |
| while (FieldsByGraph.begin()->first == &DSG) { |
| LatticeValue *LV = FieldsByGraph.begin()->second; |
| FieldsByGraph.erase(FieldsByGraph.begin()); |
| NodeLVs.insert(std::make_pair(LV->getNode(), LV)); |
| } |
| |
| // Visit all operations in this graph, looking at how these lattice values |
| // are used! |
| visitGraph(DSG, NodeLVs); |
| |
| if (NodeLVs.empty()) continue; |
| |
| // If any of the nodes have globals, and if we are inspecting stores, make |
| // sure to notice the global variable initializers. |
| if (Callbacks & Visit::Stores) { |
| for (std::multimap<DSNode*, LatticeValue*>::iterator I = NodeLVs.begin(); |
| I != NodeLVs.end(); ) { |
| // If this node has globals, incorporate them. |
| bool LVisOverdefined = false; |
| std::vector<GlobalValue*> GVs; |
| I->first->addFullGlobalsList(GVs); |
| for (unsigned i = 0, e = GVs.size(); i != e; ++i) |
| if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GVs[i])) { |
| assert(GV->hasInitializer() && "Should not be analyzing this GV!"); |
| if (VisitGlobalInit(I->second, GV->getInitializer(), |
| I->second->getFieldOffset())) { |
| LVisOverdefined = true; |
| break; |
| } |
| } |
| |
| if (LVisOverdefined) |
| NodeLVs.erase(I++); |
| else |
| ++I; |
| } |
| if (NodeLVs.empty()) continue; |
| } |
| |
| // Okay, final check. If we have any dataflow facts about nodes that are |
| // reachable from global variable nodes, we must make sure to check every |
| // function in the program that uses the global for uses of the node. |
| // Because of the globals graph, we might not have all of the information we |
| // need with our (potentially) truncated call graph traversal. |
| ProcessNodesReachableFromGlobals(DSG, NodeLVs); |
| |
| // Everything that survived goes into Fields now that we processed it. |
| while (!NodeLVs.empty()) { |
| Fields.insert(NodeLVs.begin()->second); |
| NodeLVs.erase(NodeLVs.begin()); |
| } |
| } |
| } |
| |
| /// ComputeInverseGraphFrom - Perform a simple depth-first search of the |
| /// DSGraph, recording the inverse of all of the edges in the graph. |
| /// |
| static void ComputeInverseGraphFrom(DSNode *N, |
| std::set<std::pair<DSNode*,DSNode*> > &InverseGraph) { |
| for (DSNode::edge_iterator I = N->edge_begin(), E = N->edge_end(); I != E;++I) |
| if (DSNode *Target = I->getNode()) |
| if (InverseGraph.insert(std::make_pair(Target, N)).second) |
| ComputeInverseGraphFrom(Target, InverseGraph); |
| } |
| |
| |
| /// ComputeNodesReacahbleFrom - Compute the set of nodes in the specified |
| /// inverse graph that are reachable from N. This is a simple depth first |
| /// search. |
| /// |
| static void ComputeNodesReachableFrom(DSNode *N, |
| std::set<std::pair<DSNode*,DSNode*> > &InverseGraph, |
| hash_set<const DSNode*> &Reachable) { |
| if (!Reachable.insert(N).second) return; // Already visited! |
| |
| std::set<std::pair<DSNode*,DSNode*> >::iterator I = |
| InverseGraph.lower_bound(std::make_pair(N, (DSNode*)0)); |
| for (; I != InverseGraph.end() && I->first == N; ++I) |
| ComputeNodesReachableFrom(I->second, InverseGraph, Reachable); |
| } |
| |
| /// ProcessNodesReachableFromGlobals - If we inferred anything about nodes |
| /// reachable from globals, we have to make sure that we incorporate data for |
| /// all graphs that include those globals due to the nature of the globals |
| /// graph. |
| /// |
| void StructureFieldVisitorBase:: |
| ProcessNodesReachableFromGlobals(DSGraph &DSG, |
| std::multimap<DSNode*,LatticeValue*> &NodeLVs){ |
| // Start by marking all nodes reachable from globals. |
| DSScalarMap &SM = DSG.getScalarMap(); |
| if (SM.global_begin() == SM.global_end()) return; |
| |
| hash_set<const DSNode*> Reachable; |
| for (DSScalarMap::global_iterator GI = SM.global_begin(), |
| E = SM.global_end(); GI != E; ++GI) |
| SM[*GI].getNode()->markReachableNodes(Reachable); |
| if (Reachable.empty()) return; |
| |
| // If any of the nodes with dataflow facts are reachable from the globals |
| // graph, we have to do the GG processing step. |
| bool MustProcessThroughGlobalsGraph = false; |
| for (std::multimap<DSNode*, LatticeValue*>::iterator I = NodeLVs.begin(), |
| E = NodeLVs.end(); I != E; ++I) |
| if (Reachable.count(I->first)) { |
| MustProcessThroughGlobalsGraph = true; |
| break; |
| } |
| |
| if (!MustProcessThroughGlobalsGraph) return; |
| Reachable.clear(); |
| |
| // Compute the mapping from DSG to the globals graph. |
| DSGraph::NodeMapTy DSGToGGMap; |
| DSG.computeGToGGMapping(DSGToGGMap); |
| |
| // Most of the times when we find facts about things reachable from globals we |
| // we are in the main graph. This means that we have *all* of the globals |
| // graph in this DSG. To be efficient, we compute the minimum set of globals |
| // that can reach any of the NodeLVs facts. |
| // |
| // I'm not aware of any wonderful way of computing the set of globals that |
| // points to the set of nodes in NodeLVs that is not N^2 in either NodeLVs or |
| // the number of globals, except to compute the inverse of DSG. As such, we |
| // compute the inverse graph of DSG, which basically has the edges going from |
| // pointed to nodes to pointing nodes. Because we only care about one |
| // connectedness properties, we ignore field info. In addition, we only |
| // compute inverse of the portion of the graph reachable from the globals. |
| std::set<std::pair<DSNode*,DSNode*> > InverseGraph; |
| |
| for (DSScalarMap::global_iterator GI = SM.global_begin(), |
| E = SM.global_end(); GI != E; ++GI) |
| ComputeInverseGraphFrom(SM[*GI].getNode(), InverseGraph); |
| |
| // Okay, now that we have our bastardized inverse graph, compute the set of |
| // globals nodes reachable from our lattice nodes. |
| for (std::multimap<DSNode*, LatticeValue*>::iterator I = NodeLVs.begin(), |
| E = NodeLVs.end(); I != E; ++I) |
| ComputeNodesReachableFrom(I->first, InverseGraph, Reachable); |
| |
| // Now that we know which nodes point to the data flow facts, figure out which |
| // globals point to the data flow facts. |
| std::set<GlobalValue*> Globals; |
| for (hash_set<const DSNode*>::iterator I = Reachable.begin(), |
| E = Reachable.end(); I != E; ++I) |
| Globals.insert((*I)->globals_begin(), (*I)->globals_end()); |
| |
| // Finally, loop over all of the DSGraphs for the program, computing |
| // information for the graph if not done already, mapping the result into our |
| // context. |
| for (hash_map<const Function*, DSGraph*>::iterator GI = ECG.DSInfo.begin(), |
| E = ECG.DSInfo.end(); GI != E; ++GI) { |
| DSGraph &FG = *GI->second; |
| // Graphs can contain multiple functions, only process the graph once. |
| if (GI->first != FG.retnodes_begin()->first || |
| // Also, do not bother reprocessing DSG. |
| &FG == &DSG) |
| continue; |
| |
| bool GraphUsesGlobal = false; |
| for (std::set<GlobalValue*>::iterator I = Globals.begin(), |
| E = Globals.end(); I != E; ++I) |
| if (FG.getScalarMap().count(*I)) { |
| GraphUsesGlobal = true; |
| break; |
| } |
| |
| // If this graph does not contain the global at all, there is no reason to |
| // even think about it. |
| if (!GraphUsesGlobal) continue; |
| |
| // Otherwise, compute the full set of dataflow effects of the function. |
| std::multimap<DSNode*, LatticeValue*> &FGF = getCalleeFacts(FG); |
| //std::cerr << "Computed: " << FG.getFunctionNames() << "\n"; |
| |
| #if 0 |
| for (std::multimap<DSNode*, LatticeValue*>::iterator I = FGF.begin(), |
| E = FGF.end(); I != E; ++I) |
| I->second->dump(); |
| #endif |
| // Compute the mapping of nodes in the globals graph to the function's |
| // graph. Note that this function graph may not have nodes (or may have |
| // fragments of full nodes) in the globals graph, and we don't want this to |
| // pessimize the analysis. |
| std::multimap<const DSNode*, std::pair<DSNode*,int> > GraphMap; |
| DSGraph::NodeMapTy GraphToGGMap; |
| FG.computeGToGGMapping(GraphToGGMap); |
| |
| // "Invert" the mapping. We compute the mapping from the start of a global |
| // graph node to a place in the graph's node. Note that not all of the GG |
| // node may be present in the graphs node, so there may be a negative offset |
| // involved. |
| while (!GraphToGGMap.empty()) { |
| DSNode *GN = const_cast<DSNode*>(GraphToGGMap.begin()->first); |
| DSNodeHandle &GGNH = GraphToGGMap.begin()->second; |
| GraphMap.insert(std::make_pair(GGNH.getNode(), |
| std::make_pair(GN, -GGNH.getOffset()))); |
| GraphToGGMap.erase(GraphToGGMap.begin()); |
| } |
| |
| // Loop over all of the dataflow facts that we have computed, mapping them |
| // to the globals graph. |
| for (std::multimap<DSNode*, LatticeValue*>::iterator I = NodeLVs.begin(), |
| E = NodeLVs.end(); I != E; ) { |
| bool FactHitBottom = false; |
| |
| //I->second->dump(); |
| |
| assert(I->first->getParentGraph() == &DSG); |
| assert(I->second->getNode()->getParentGraph() == &DSG); |
| |
| // Node is in the GG? |
| DSGraph::NodeMapTy::iterator DSGToGGMapI = DSGToGGMap.find(I->first); |
| if (DSGToGGMapI != DSGToGGMap.end()) { |
| DSNodeHandle &GGNH = DSGToGGMapI->second; |
| const DSNode *GGNode = GGNH.getNode(); |
| unsigned DSGToGGOffset = GGNH.getOffset(); |
| |
| // See if there is a node in FG that corresponds to this one. If not, |
| // no information will be computed in this scope, as the memory is not |
| // accessed. |
| std::multimap<const DSNode*, std::pair<DSNode*,int> >::iterator GMI = |
| GraphMap.find(GGNode); |
| |
| // LatticeValOffset - The offset from the start of the GG Node to the |
| // start of the field we are interested in. |
| unsigned LatticeValOffset = I->second->getFieldOffset()+DSGToGGOffset; |
| |
| // Loop over all of the nodes in FG that correspond to this single node |
| // in the GG. |
| for (; GMI != GraphMap.end() && GMI->first == GGNode; ++GMI) { |
| // Compute the offset to the field in the user graph. |
| unsigned FieldOffset = LatticeValOffset - GMI->second.second; |
| |
| // If the field is within the amount of memory accessed by this scope, |
| // then there must be a corresponding lattice value. |
| DSNode *FGNode = GMI->second.first; |
| if (FieldOffset < FGNode->getSize()) { |
| LatticeValue *CorrespondingLV = 0; |
| |
| std::multimap<DSNode*, LatticeValue*>::iterator FGFI = |
| FGF.find(FGNode); |
| for (; FGFI != FGF.end() && FGFI->first == FGNode; ++FGFI) |
| if (FGFI->second->getFieldOffset() == FieldOffset) { |
| CorrespondingLV = FGFI->second; |
| break; |
| } |
| |
| // Finally, if either there was no corresponding fact (because it |
| // hit bottom in this scope), or if merging the two pieces of |
| // information makes it hit bottom, remember this. |
| if (CorrespondingLV == 0 || |
| I->second->mergeInValue(CorrespondingLV)) |
| FactHitBottom = true; |
| } |
| } |
| } |
| |
| if (FactHitBottom) { |
| delete I->second; |
| NodeLVs.erase(I++); |
| if (NodeLVs.empty()) return; |
| } else { |
| ++I; |
| } |
| } |
| } |
| } |
| |
| |
| /// getCalleeFacts - Compute the data flow effect that calling one of the |
| /// functions in this graph has on the caller. This information is cached after |
| /// it is computed for a function the first time. |
| /// |
| std::multimap<DSNode*, LatticeValue*> & |
| StructureFieldVisitorBase::getCalleeFacts(DSGraph &DSG) { |
| // Already computed? |
| std::map<DSGraph*, std::multimap<DSNode*,LatticeValue*> >::iterator |
| I = CalleeFnFacts.find(&DSG); |
| if (I != CalleeFnFacts.end()) |
| return I->second; // We already computed stuff for this fn! |
| |
| std::multimap<DSNode*, LatticeValue*> &Result = CalleeFnFacts[&DSG]; |
| |
| std::set<LatticeValue*> LVs; |
| for (DSGraph::node_iterator NI = DSG.node_begin(), E = DSG.node_end(); |
| NI != E; ++NI) |
| AddLatticeValuesForNode(NI, LVs); |
| |
| while (!LVs.empty()) { |
| Result.insert(std::make_pair((*LVs.begin())->getNode(), *LVs.begin())); |
| LVs.erase(LVs.begin()); |
| } |
| |
| if (!Result.empty()) |
| visitGraph(DSG, Result); |
| return Result; |
| } |
| |
| |
| /// NodeCanPossiblyBeInteresting - Return true if the specified node can |
| /// potentially be interesting to a client that is only interested in |
| /// VisitFlags events. This is used to reduce the cost of interprocedural |
| /// analysis by not traversing the call graph through portions that the DSGraph |
| /// can answer immediately. |
| /// |
| static bool NodeCanPossiblyBeInteresting(const DSNode *N, unsigned VisitFlags) { |
| // No fields are accessed in this context. |
| if (N->getType() == Type::VoidTy) return false; |
| |
| // This node is possibly interesting if we are looking for reads and it is |
| // read, we're looking for writes and it is modified, etc. |
| if ((VisitFlags & Visit::Loads) && N->isRead()) return true; |
| if ((VisitFlags & Visit::Stores) && N->isModified()) return true; |
| |
| assert((VisitFlags & ~(Visit::Loads|Visit::Stores)) == 0 && |
| "Unknown visitation type!"); |
| |
| // Otherwise, this node is not interesting to the current client. |
| return false; |
| } |
| |
| /// visitGraph - Visit the functions in the specified graph, updating the |
| /// specified lattice values for all of their uses. |
| /// |
| void StructureFieldVisitorBase:: |
| visitGraph(DSGraph &DSG, std::multimap<DSNode*, LatticeValue*> &NodeLVs) { |
| assert(!NodeLVs.empty() && "No lattice values to compute!"); |
| |
| // To visit a graph, first step, we visit the instruction making up each |
| // function in the graph, but ignore calls when processing them. We handle |
| // call nodes explicitly by looking at call nodes in the graph if needed. We |
| // handle instructions before calls to avoid interprocedural analysis if we |
| // can drive lattice values to bottom early. |
| // |
| SFVInstVisitor IV(DSG, Callbacks, NodeLVs); |
| |
| for (DSGraph::retnodes_iterator FI = DSG.retnodes_begin(), |
| E = DSG.retnodes_end(); FI != E; ++FI) |
| for (Function::iterator BB = FI->first->begin(), E = FI->first->end(); |
| BB != E; ++BB) |
| for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) |
| if (IV.visit(*I) && NodeLVs.empty()) |
| return; // Nothing left to analyze. |
| |
| // Keep track of which actual direct callees are handled. |
| std::set<Function*> CalleesHandled; |
| |
| // Once we have visited all of the instructions in the function bodies, if |
| // there are lattice values that have not been driven to bottom, see if any of |
| // the nodes involved are passed into function calls. If so, we potentially |
| // have to recursively traverse the call graph. |
| for (DSGraph::fc_iterator CS = DSG.fc_begin(), E = DSG.fc_end(); |
| CS != E; ++CS) { |
| // Figure out the mapping from a node in the caller (potentially several) |
| // nodes in the callee. |
| DSGraph::NodeMapTy CallNodeMap; |
| |
| Instruction *TheCall = CS->getCallSite().getInstruction(); |
| |
| // If this is an indirect function call, assume nothing gets passed through |
| // it. FIXME: THIS IS BROKEN! Just get the ECG for the fn ptr if it's not |
| // direct. |
| if (CS->isIndirectCall()) |
| continue; |
| |
| // If this is an external function call, it cannot be involved with this |
| // node, because otherwise the node would be marked incomplete! |
| if (CS->getCalleeFunc()->isExternal()) |
| continue; |
| |
| // If we can handle this function call, remove it from the set of direct |
| // calls found by the visitor. |
| CalleesHandled.insert(CS->getCalleeFunc()); |
| |
| std::vector<DSNodeHandle> Args; |
| |
| DSGraph *CG = &ECG.getDSGraph(*CS->getCalleeFunc()); |
| CG->getFunctionArgumentsForCall(CS->getCalleeFunc(), Args); |
| |
| if (!CS->getRetVal().isNull()) |
| DSGraph::computeNodeMapping(Args[0], CS->getRetVal(), CallNodeMap); |
| for (unsigned i = 0, e = CS->getNumPtrArgs(); i != e; ++i) { |
| if (i == Args.size()-1) break; |
| DSGraph::computeNodeMapping(Args[i+1], CS->getPtrArg(i), CallNodeMap); |
| } |
| Args.clear(); |
| |
| // The mapping we just computed maps from nodes in the callee to nodes in |
| // the caller, so we can't query it efficiently. Instead of going through |
| // the trouble of inverting the map to do this (linear time with the size of |
| // the mapping), we just do a linear search to see if any affected nodes are |
| // passed into this call. |
| bool CallCanModifyDataFlow = false; |
| for (DSGraph::NodeMapTy::iterator MI = CallNodeMap.begin(), |
| E = CallNodeMap.end(); MI != E; ++MI) |
| if (NodeLVs.count(MI->second.getNode())) |
| // Okay, the node is passed in, check to see if the call might do |
| // something interesting to it (i.e. if analyzing the call can produce |
| // anything other than "top"). |
| if ((CallCanModifyDataFlow = NodeCanPossiblyBeInteresting(MI->first, |
| Callbacks))) |
| break; |
| |
| // If this function call cannot impact the analysis (either because the |
| // nodes we are tracking are not passed into the call, or the DSGraph for |
| // the callee tells us that analysis of the callee can't provide interesting |
| // information), ignore it. |
| if (!CallCanModifyDataFlow) |
| continue; |
| |
| // Okay, either compute analysis results for the callee function, or reuse |
| // results previously computed. |
| std::multimap<DSNode*, LatticeValue*> &CalleeFacts = getCalleeFacts(*CG); |
| |
| // Merge all of the facts for the callee into the facts for the caller. If |
| // this reduces anything in the caller to 'bottom', remove them. |
| for (DSGraph::NodeMapTy::iterator MI = CallNodeMap.begin(), |
| E = CallNodeMap.end(); MI != E; ++MI) { |
| // If we have Lattice facts in the caller for this node in the callee, |
| // merge any information from the callee into the caller. |
| |
| // If the node is not accessed in the callee at all, don't update. |
| if (MI->first->getType() == Type::VoidTy) |
| continue; |
| |
| // If there are no data-flow facts live in the caller for this node, don't |
| // both processing it. |
| std::multimap<DSNode*, LatticeValue*>::iterator NLVI = |
| NodeLVs.find(MI->second.getNode()); |
| if (NLVI == NodeLVs.end()) continue; |
| |
| |
| // Iterate over all of the lattice values that have corresponding fields |
| // in the callee, merging in information as we go. Be careful about the |
| // fact that the callee may get passed the address of a substructure and |
| // other funny games. |
| //if (CalleeFacts.count(const_cast<DSNode*>(MI->first)) == 0) { |
| |
| DSNode *CalleeNode = const_cast<DSNode*>(MI->first); |
| |
| unsigned CalleeNodeOffset = MI->second.getOffset(); |
| while (NLVI->first == MI->second.getNode()) { |
| // Figure out what offset in the callee this field would land. |
| unsigned FieldOff = NLVI->second->getFieldOffset()+CalleeNodeOffset; |
| |
| // If the field is not within the callee node, ignore it. |
| if (FieldOff >= CalleeNode->getSize()) { |
| ++NLVI; |
| continue; |
| } |
| |
| // Okay, check to see if we have a lattice value for the field at offset |
| // FieldOff in the callee node. |
| const LatticeValue *CalleeLV = 0; |
| |
| std::multimap<DSNode*, LatticeValue*>::iterator CFI = |
| CalleeFacts.lower_bound(CalleeNode); |
| for (; CFI != CalleeFacts.end() && CFI->first == CalleeNode; ++CFI) |
| if (CFI->second->getFieldOffset() == FieldOff) { |
| CalleeLV = CFI->second; // Found it! |
| break; |
| } |
| |
| // If we don't, the lattice value hit bottom and we should remove the |
| // lattice value in the caller. |
| if (!CalleeLV) { |
| delete NLVI->second; // The lattice value hit bottom. |
| NodeLVs.erase(NLVI++); |
| continue; |
| } |
| |
| // Finally, if we did find a corresponding entry, merge the information |
| // into the caller's lattice value and keep going. |
| if (NLVI->second->mergeInValue(CalleeLV)) { |
| // Okay, merging these two caused the caller value to hit bottom. |
| // Remove it. |
| delete NLVI->second; // The lattice value hit bottom. |
| NodeLVs.erase(NLVI++); |
| } |
| |
| ++NLVI; // We successfully merged in some information! |
| } |
| |
| // If we ran out of facts to prove, just exit. |
| if (NodeLVs.empty()) return; |
| } |
| } |
| |
| // The local analysis pass inconveniently discards many local function calls |
| // from the graph if they are to known functions. Loop over direct function |
| // calls not handled above and visit them as appropriate. |
| while (!IV.DirectCallSites.empty()) { |
| Instruction *Call = *IV.DirectCallSites.begin(); |
| IV.DirectCallSites.erase(IV.DirectCallSites.begin()); |
| |
| // Is this one actually handled by DSA? |
| if (CalleesHandled.count(cast<Function>(Call->getOperand(0)))) |
| continue; |
| |
| // Collect the pointers involved in this call. |
| std::vector<Value*> Pointers; |
| if (isa<PointerType>(Call->getType())) |
| Pointers.push_back(Call); |
| for (unsigned i = 1, e = Call->getNumOperands(); i != e; ++i) |
| if (isa<PointerType>(Call->getOperand(i)->getType())) |
| Pointers.push_back(Call->getOperand(i)); |
| |
| // If this is an intrinsic function call, figure out which one. |
| unsigned IID = cast<Function>(Call->getOperand(0))->getIntrinsicID(); |
| |
| for (unsigned i = 0, e = Pointers.size(); i != e; ++i) { |
| // If any of our lattice values are passed into this call, which is |
| // specially handled by the local analyzer, inform the lattice function. |
| DSNode *N = DSG.getNodeForValue(Pointers[i]).getNode(); |
| for (std::multimap<DSNode*, LatticeValue*>::iterator LVI = |
| NodeLVs.lower_bound(N); LVI != NodeLVs.end() && LVI->first == N;) { |
| bool AtBottom = false; |
| switch (IID) { |
| default: |
| AtBottom = LVI->second->visitRecognizedCall(*Call); |
| break; |
| case Intrinsic::memset: |
| if (Callbacks & Visit::Stores) |
| AtBottom = LVI->second->visitMemSet(*cast<CallInst>(Call)); |
| break; |
| } |
| |
| if (AtBottom) { |
| delete LVI->second; |
| NodeLVs.erase(LVI++); |
| } else { |
| ++LVI; |
| } |
| } |
| } |
| } |
| } |