From bd92b73be7cc90a3671310a44c1195e7a7087820 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 19 Jun 2003 21:15:11 +0000 Subject: [PATCH] * Changes to make NodeType be private to DSNode. * Add new MultiObject flag to DSNode which keeps track of whether or not multiple objects have been merged into the node, allowing must-alias info to be tracked. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@6794 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../DataStructure/BottomUpClosure.cpp | 2 +- lib/Analysis/DataStructure/DataStructure.cpp | 73 +++++++++++-------- .../DataStructure/DataStructureAA.cpp | 45 ++++++++---- lib/Analysis/DataStructure/Local.cpp | 42 ++++++----- lib/Analysis/DataStructure/Printer.cpp | 21 +++--- 5 files changed, 107 insertions(+), 76 deletions(-) diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp index 0833a029129..9f504366b6f 100644 --- a/lib/Analysis/DataStructure/BottomUpClosure.cpp +++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp @@ -33,7 +33,7 @@ static bool isVAHackFn(const Function *F) { // if the call sites are not external. // static inline bool isCompleteNode(DSNode *N) { - if (N->NodeType & DSNode::Incomplete) return false; + if (N->isIncomplete()) return false; const std::vector &Callees = N->getGlobals(); for (unsigned i = 0, e = Callees.size(); i != e; ++i) if (Callees[i]->isExternal()) diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp index 5f232e2054d..9e00860365b 100644 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ b/lib/Analysis/DataStructure/DataStructure.cpp @@ -49,8 +49,8 @@ DSNode *DSNodeHandle::HandleForwarding() const { // DSNode Implementation //===----------------------------------------------------------------------===// -DSNode::DSNode(unsigned NT, const Type *T, DSGraph *G) - : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(NT) { +DSNode::DSNode(const Type *T, DSGraph *G) + : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(0) { // Add the type entry if it is specified... if (T) mergeTypeInfo(T, 0); G->getNodes().push_back(this); @@ -68,6 +68,12 @@ void DSNode::assertOK() const { Ty == Type::VoidTy && (Size == 0 || (NodeType & DSNode::Array))) && "Node not OK!"); + + // Check to ensure that the multiobject constraints are met... + unsigned Comp = NodeType & DSNode::Composition; + assert((NodeType & DSNode::MultiObject) || + Comp == 0 || Comp == DSNode::AllocaNode || Comp == DSNode::HeapNode || + Comp == DSNode::GlobalNode || Comp == DSNode::UnknownNode); } /// forwardNode - Mark this node as being obsolete, and all references to it @@ -97,6 +103,8 @@ void DSNode::addGlobal(GlobalValue *GV) { if (I == Globals.end() || *I != GV) { //assert(GV->getType()->getElementType() == Ty); Globals.insert(I, GV); + if (NodeType & DSNode::Composition) + NodeType |= DSNode::MultiObject; NodeType |= GlobalNode; } } @@ -112,7 +120,8 @@ void DSNode::foldNodeCompletely() { ++NumFolds; // Create the node we are going to forward to... - DSNode *DestNode = new DSNode(NodeType|DSNode::Array, 0, ParentGraph); + DSNode *DestNode = new DSNode(0, ParentGraph); + DestNode->NodeType = NodeType|DSNode::Array; DestNode->Ty = Type::VoidTy; DestNode->Size = 1; DestNode->Globals.swap(Globals); @@ -446,7 +455,7 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { // Merge the type entries of the two nodes together... if (NH.getNode()->Ty != Type::VoidTy) CurNodeH.getNode()->mergeTypeInfo(NH.getNode()->Ty, NOffset); - assert((CurNodeH.getNode()->NodeType & DSNode::DEAD) == 0); + assert(!CurNodeH.getNode()->isDeadNode()); // If we are merging a node with a completely folded node, then both nodes are // now completely folded. @@ -471,12 +480,17 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { DSNode *N = NH.getNode(); if (CurNodeH.getNode() == N || N == 0) return; - assert((CurNodeH.getNode()->NodeType & DSNode::DEAD) == 0); + assert(!CurNodeH.getNode()->isDeadNode()); - // Start forwarding to the new node! + // Merge the NodeType information... + if ((CurNodeH.getNode()->NodeType & DSNode::Composition) != 0 && + (N->NodeType & DSNode::Composition) != 0) + N->NodeType |= DSNode::MultiObject; // Multiple composition -> multiobject CurNodeH.getNode()->NodeType |= N->NodeType; + + // Start forwarding to the new node! N->forwardNode(CurNodeH.getNode(), NOffset); - assert((CurNodeH.getNode()->NodeType & DSNode::DEAD) == 0); + assert(!CurNodeH.getNode()->isDeadNode()); // Make all of the outgoing links of N now be outgoing links of CurNodeH. // @@ -522,8 +536,7 @@ void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { if (N == 0 || (N == this && NH.getOffset() == Offset)) return; // Noop - assert((N->NodeType & DSNode::DEAD) == 0); - assert((NodeType & DSNode::DEAD) == 0); + assert(!N->isDeadNode() && !isDeadNode()); assert(!hasNoReferrers() && "Should not try to fold a useless node!"); if (N == this) { @@ -630,13 +643,13 @@ DSNodeHandle DSGraph::cloneInto(const DSGraph &G, Nodes.reserve(FN+G.Nodes.size()); // Remove alloca or mod/ref bits as specified... - unsigned clearBits = (CloneFlags & StripAllocaBit ? DSNode::AllocaNode : 0) - | (CloneFlags & StripModRefBits ? (DSNode::Modified | DSNode::Read) : 0); - clearBits |= DSNode::DEAD; // Clear dead flag... + unsigned BitsToClear =((CloneFlags & StripAllocaBit) ? DSNode::AllocaNode : 0) + | ((CloneFlags & StripModRefBits) ? (DSNode::Modified | DSNode::Read) : 0); + BitsToClear |= DSNode::DEAD; // Clear dead flag... for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i) { DSNode *Old = G.Nodes[i]; DSNode *New = new DSNode(*Old, this); - New->NodeType &= ~clearBits; + New->maskNodeTypes(~BitsToClear); OldNodeMap[Old] = New; } @@ -743,16 +756,16 @@ void DSGraph::mergeInGraph(DSCallSite &CS, const DSGraph &Graph, // markIncompleteNodes - Mark the specified node as having contents that are not // known with the current analysis we have performed. Because a node makes all -// of the nodes it can reach imcomplete if the node itself is incomplete, we +// of the nodes it can reach incomplete if the node itself is incomplete, we // must recursively traverse the data structure graph, marking all reachable // nodes as incomplete. // static void markIncompleteNode(DSNode *N) { // Stop recursion if no node, or if node already marked... - if (N == 0 || (N->NodeType & DSNode::Incomplete)) return; + if (N == 0 || (N->isIncomplete())) return; // Actually mark the node - N->NodeType |= DSNode::Incomplete; + N->setIncompleteMarker(); // Recusively process children... for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize) @@ -798,14 +811,15 @@ void DSGraph::markIncompleteNodes(unsigned Flags) { // Mark all global nodes as incomplete... if ((Flags & DSGraph::IgnoreGlobals) == 0) for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - if (Nodes[i]->NodeType & DSNode::GlobalNode && Nodes[i]->getNumLinks()) + if (Nodes[i]->isGlobalNode() && Nodes[i]->getNumLinks()) markIncompleteNode(Nodes[i]); } static inline void killIfUselessEdge(DSNodeHandle &Edge) { if (DSNode *N = Edge.getNode()) // Is there an edge? if (N->getNumReferrers() == 1) // Does it point to a lonely node? - if ((N->NodeType & ~DSNode::Incomplete) == 0 && // No interesting info? + // No interesting info? + if ((N->getNodeFlags() & ~DSNode::Incomplete) == 0 && N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded()) Edge.setNode(0); // Kill the edge! } @@ -835,7 +849,7 @@ static void removeIdenticalCalls(std::vector &Calls, // If the Callee is a useless edge, this must be an unreachable call site, // eliminate it. if (CS.isIndirectCall() && CS.getCalleeNode()->getNumReferrers() == 1 && - CS.getCalleeNode()->NodeType == 0) { // No useful info? + CS.getCalleeNode()->getNodeFlags() == 0) { // No useful info? std::cerr << "WARNING: Useless call site found??\n"; CS.swap(Calls.back()); Calls.pop_back(); @@ -914,8 +928,7 @@ void DSGraph::removeTriviallyDeadNodes() { for (unsigned i = 0; i != Nodes.size(); ++i) { DSNode *Node = Nodes[i]; - if (!(Node->NodeType & ~(DSNode::Composition | DSNode::Array | - DSNode::DEAD))) { + if (!Node->isIncomplete() && !Node->isModified() && !Node->isRead()) { // This is a useless node if it has no mod/ref info (checked above), // outgoing edges (which it cannot, as it is not modified in this // context), and it has no incoming edges. If it is a global node it may @@ -923,7 +936,7 @@ void DSGraph::removeTriviallyDeadNodes() { // scalar map, so we check those now. // if (Node->getNumReferrers() == Node->getGlobals().size()) { - std::vector &Globals = Node->getGlobals(); + const std::vector &Globals = Node->getGlobals(); // Loop through and make sure all of the globals are referring directly // to the node... @@ -932,20 +945,16 @@ void DSGraph::removeTriviallyDeadNodes() { assert(N == Node && "ScalarMap doesn't match globals list!"); } - // Make sure numreferrers still agrees, if so, the node is truely dead. + // Make sure NumReferrers still agrees, if so, the node is truly dead. if (Node->getNumReferrers() == Globals.size()) { for (unsigned j = 0, e = Globals.size(); j != e; ++j) ScalarMap.erase(Globals[j]); - - Globals.clear(); - assert(Node->hasNoReferrers() && "Shouldn't have refs now!"); - - Node->NodeType = DSNode::DEAD; + Node->makeNodeDead(); } } } - if ((Node->NodeType & ~DSNode::DEAD) == 0 && Node->hasNoReferrers()) { + if (Node->getNodeFlags() == 0 && Node->hasNoReferrers()) { // This node is dead! delete Node; // Free memory... Nodes[i--] = Nodes.back(); @@ -1055,7 +1064,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) { // these, prune the scalar pointing to it. // DSNode *N = I->second.getNode(); - if (N->NodeType == DSNode::UnknownNode && !isa(I->first)) { + if (N->isUnknownNode() && !isa(I->first)) { ScalarMap.erase(I++); } else { I->second.getNode()->markReachableNodes(Alive); @@ -1128,7 +1137,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) { GlobalsGraph->Nodes.push_back(N); // Move node to globals graph N->setParentGraph(GlobalsGraph); } else { // Otherwise, delete the node - assert(((N->NodeType & DSNode::GlobalNode) == 0 || + assert((!N->isGlobalNode() || (Flags & DSGraph::RemoveUnreachableGlobals)) && "Killing a global?"); //std::cerr << "[" << i+1 << "/" << DeadNodes.size() @@ -1189,7 +1198,7 @@ void DSGraph::AssertGraphOK() const { assert(I->second.getNode() && "Null node in scalarmap!"); AssertNodeInGraph(I->second.getNode()); if (GlobalValue *GV = dyn_cast(I->first)) { - assert((I->second.getNode()->NodeType & DSNode::GlobalNode) && + assert(I->second.getNode()->isGlobalNode() && "Global points to node, but node isn't global?"); AssertNodeContainsGlobal(I->second.getNode(), GV); } diff --git a/lib/Analysis/DataStructure/DataStructureAA.cpp b/lib/Analysis/DataStructure/DataStructureAA.cpp index 5c3d946478a..d7c40c6f5a6 100644 --- a/lib/Analysis/DataStructure/DataStructureAA.cpp +++ b/lib/Analysis/DataStructure/DataStructureAA.cpp @@ -68,15 +68,12 @@ static const Function *getValueFunction(const Value *V) { // alias - This is the only method here that does anything interesting... AliasAnalysis::AliasResult DSAA::alias(const Value *V1, unsigned V1Size, const Value *V2, unsigned V2Size) { - // FIXME: This should handle the Size argument as well! + if (V1 == V2) return MustAlias; + const Function *F1 = getValueFunction(V1); const Function *F2 = getValueFunction(V2); assert((!F1 || !F2 || F1 == F2) && "Alias query for 2 different functions?"); - - // FIXME: This can return must alias if querying a DSNode for a global value - // where the node has only the G composition bit set, and only one entry in - // the globals list... if (F2) F1 = F2; if (F1) { // Get the graph for a function... @@ -88,17 +85,33 @@ AliasAnalysis::AliasResult DSAA::alias(const Value *V1, unsigned V1Size, hash_map::iterator J = GSM.find((Value*)V2); if (J != GSM.end()) { assert(J->second.getNode() && "Scalar map points to null node?"); - if (I->second.getNode() != J->second.getNode()) { - // Return noalias if one of the nodes is complete... - if ((~I->second.getNode()->NodeType | ~J->second.getNode()->NodeType) - & DSNode::Incomplete) - return NoAlias; - // both are incomplete, they may alias... - } else { - // Both point to the same node, see if they point to different - // offsets... FIXME: This needs to know the size of the alias query - if (I->second.getOffset() != J->second.getOffset()) - return NoAlias; + + DSNode *N1 = I->second.getNode(), *N2 = J->second.getNode(); + unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset(); + + // We can only make a judgement of one of the nodes is complete... + if (!N1->isIncomplete() || !N2->isIncomplete()) { + if (N1 != N2) + return NoAlias; // Completely different nodes. + + // Both point to the same node and same offset, and there is only one + // physical memory object represented in the node, return must alias. + if (O1 == O2 && !N1->isMultiObject()) + return MustAlias; // Exactly the same object & offset + + // See if they point to different offsets... if so, we may be able to + // determine that they do not alias... + if (O1 != O2) { + if (O2 < O1) { // Ensure that O1 <= O2 + std::swap(V1, V2); + std::swap(O1, O2); + std::swap(V1Size, V2Size); + } + + // FIXME: This is not correct because we do not handle array + // indexing correctly with this check! + //if (O1+V1Size <= O2) return NoAlias; + } } } } diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp index 369b76d6119..a7751f23f7c 100644 --- a/lib/Analysis/DataStructure/Local.cpp +++ b/lib/Analysis/DataStructure/Local.cpp @@ -86,9 +86,9 @@ namespace { private: // Visitor functions, used to handle each instruction type we encounter... friend class InstVisitor; - void visitMallocInst(MallocInst &MI) { handleAlloc(MI, DSNode::HeapNode); } - void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, DSNode::AllocaNode);} - void handleAlloc(AllocationInst &AI, DSNode::NodeTy NT); + void visitMallocInst(MallocInst &MI) { handleAlloc(MI, true); } + void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, false); } + void handleAlloc(AllocationInst &AI, bool isHeap); void visitPHINode(PHINode &PN); @@ -108,8 +108,8 @@ namespace { /// createNode - Create a new DSNode, ensuring that it is properly added to /// the graph. /// - DSNode *createNode(DSNode::NodeTy NodeType, const Type *Ty = 0) { - DSNode *N = new DSNode(NodeType, Ty, &G); // Create the node + DSNode *createNode(const Type *Ty = 0) { + DSNode *N = new DSNode(Ty, &G); // Create the node if (DisableFieldSensitivity) { N->foldNodeCompletely(); if (DSNode *FN = N->getForwardNode()) @@ -194,7 +194,7 @@ DSNodeHandle GraphBuilder::getValueDest(Value &Val) { NH = I->second; } else { // This returns a conservative unknown node for any unhandled ConstExpr - return NH = createNode(DSNode::UnknownNode); + return NH = createNode()->setUnknownNodeMarker(); } if (NH.getNode() == 0) { // (getelementptr null, X) returns null ScalarMap.erase(V); @@ -204,7 +204,7 @@ DSNodeHandle GraphBuilder::getValueDest(Value &Val) { } else if (ConstantIntegral *CI = dyn_cast(C)) { // Random constants are unknown mem - return NH = createNode(DSNode::UnknownNode); + return NH = createNode()->setUnknownNodeMarker(); } else { assert(0 && "Unknown constant type!"); } @@ -213,11 +213,11 @@ DSNodeHandle GraphBuilder::getValueDest(Value &Val) { DSNode *N; if (GlobalValue *GV = dyn_cast(V)) { // Create a new global node for this global variable... - N = createNode(DSNode::GlobalNode, GV->getType()->getElementType()); + N = createNode(GV->getType()->getElementType()); N->addGlobal(GV); } else { // Otherwise just create a shadow node - N = createNode(DSNode::ShadowNode); + N = createNode(); } NH.setNode(N); // Remember that we are pointing to it... @@ -237,7 +237,7 @@ DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, unsigned LinkNo) { DSNodeHandle &Link = Node.getLink(LinkNo); if (!Link.getNode()) { // If the link hasn't been created yet, make and return a new shadow node - Link = createNode(DSNode::ShadowNode); + Link = createNode(); } return Link; } @@ -263,8 +263,13 @@ void GraphBuilder::setDestTo(Value &V, const DSNodeHandle &NH) { /// Alloca & Malloc instruction implementation - Simply create a new memory /// object, pointing the scalar to it. /// -void GraphBuilder::handleAlloc(AllocationInst &AI, DSNode::NodeTy NodeType) { - setDestTo(AI, createNode(NodeType)); +void GraphBuilder::handleAlloc(AllocationInst &AI, bool isHeap) { + DSNode *N = createNode(); + if (isHeap) + N->setHeapNodeMarker(); + else + N->setAllocaNodeMarker(); + setDestTo(AI, N); } // PHINode - Make the scalar for the PHI node point to all of the things the @@ -368,7 +373,7 @@ void GraphBuilder::visitLoadInst(LoadInst &LI) { if (Ptr.getNode() == 0) return; // Make that the node is read from... - Ptr.getNode()->NodeType |= DSNode::Read; + Ptr.getNode()->setReadMarker(); // Ensure a typerecord exists... Ptr.getNode()->mergeTypeInfo(LI.getType(), Ptr.getOffset(), false); @@ -383,7 +388,7 @@ void GraphBuilder::visitStoreInst(StoreInst &SI) { if (Dest.getNode() == 0) return; // Mark that the node is written to... - Dest.getNode()->NodeType |= DSNode::Modified; + Dest.getNode()->setModifiedMarker(); // Ensure a typerecord exists... Dest.getNode()->mergeTypeInfo(StoredTy, Dest.getOffset()); @@ -426,8 +431,9 @@ void GraphBuilder::visitCallInst(CallInst &CI) { void GraphBuilder::visitFreeInst(FreeInst &FI) { // Mark that the node is written to... - getValueDest(*FI.getOperand(0)).getNode()->NodeType - |= DSNode::Modified | DSNode::HeapNode; + DSNode *N = getValueDest(*FI.getOperand(0)).getNode(); + N->setModifiedMarker(); + N->setHeapNodeMarker(); } /// Handle casts... @@ -441,7 +447,7 @@ void GraphBuilder::visitCastInst(CastInst &CI) { // to track the fact that the node points to SOMETHING, just something we // don't know about. Make an "Unknown" node. // - setDestTo(CI, createNode(DSNode::UnknownNode)); + setDestTo(CI, createNode()->setUnknownNodeMarker()); } } @@ -458,7 +464,7 @@ void GraphBuilder::visitInstruction(Instruction &Inst) { CurNode.mergeWith(getValueDest(**I)); if (CurNode.getNode()) - CurNode.getNode()->NodeType |= DSNode::UnknownNode; + CurNode.getNode()->setUnknownNodeMarker(); } diff --git a/lib/Analysis/DataStructure/Printer.cpp b/lib/Analysis/DataStructure/Printer.cpp index 7f0bf5a5120..9bde0b7e891 100644 --- a/lib/Analysis/DataStructure/Printer.cpp +++ b/lib/Analysis/DataStructure/Printer.cpp @@ -38,16 +38,19 @@ static std::string getCaption(const DSNode *N, const DSGraph *G) { if (N->isArray()) OS << " array"; } - if (N->NodeType) { + if (unsigned NodeType = N->getNodeFlags()) { OS << ": "; - if (N->NodeType & DSNode::AllocaNode ) OS << "S"; - if (N->NodeType & DSNode::HeapNode ) OS << "H"; - if (N->NodeType & DSNode::GlobalNode ) OS << "G"; - if (N->NodeType & DSNode::UnknownNode) OS << "U"; - if (N->NodeType & DSNode::Incomplete ) OS << "I"; - if (N->NodeType & DSNode::Modified ) OS << "M"; - if (N->NodeType & DSNode::Read ) OS << "R"; - if (N->NodeType & DSNode::DEAD ) OS << ""; + if (NodeType & DSNode::AllocaNode ) OS << "S"; + if (NodeType & DSNode::HeapNode ) OS << "H"; + if (NodeType & DSNode::GlobalNode ) OS << "G"; + if (NodeType & DSNode::UnknownNode) OS << "U"; + if (NodeType & DSNode::Incomplete ) OS << "I"; + if (NodeType & DSNode::Modified ) OS << "M"; + if (NodeType & DSNode::Read ) OS << "R"; + if (NodeType & DSNode::MultiObject) OS << "m"; +#ifndef NDEBUG + if (NodeType & DSNode::DEAD ) OS << ""; +#endif OS << "\n"; } -- 2.34.1