LLVM API Documentation
00001 //===- DSNode.h - Node definition for datastructure graphs ------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Data structure graph nodes and some implementation of DSNodeHandle. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ANALYSIS_DSNODE_H 00015 #define LLVM_ANALYSIS_DSNODE_H 00016 00017 #include "llvm/Analysis/DataStructure/DSSupport.h" 00018 #include "llvm/ADT/hash_map" 00019 00020 namespace llvm { 00021 00022 template<typename BaseType> 00023 class DSNodeIterator; // Data structure graph traversal iterator 00024 class TargetData; 00025 00026 //===----------------------------------------------------------------------===// 00027 /// DSNode - Data structure node class 00028 /// 00029 /// This class represents an untyped memory object of Size bytes. It keeps 00030 /// track of any pointers that have been stored into the object as well as the 00031 /// different types represented in this object. 00032 /// 00033 class DSNode { 00034 /// NumReferrers - The number of DSNodeHandles pointing to this node... if 00035 /// this is a forwarding node, then this is the number of node handles which 00036 /// are still forwarding over us. 00037 /// 00038 unsigned NumReferrers; 00039 00040 /// ForwardNH - This NodeHandle contain the node (and offset into the node) 00041 /// that this node really is. When nodes get folded together, the node to be 00042 /// eliminated has these fields filled in, otherwise ForwardNH.getNode() is 00043 /// null. 00044 /// 00045 DSNodeHandle ForwardNH; 00046 00047 /// Next, Prev - These instance variables are used to keep the node on a 00048 /// doubly-linked ilist in the DSGraph. 00049 /// 00050 DSNode *Next, *Prev; 00051 friend struct ilist_traits<DSNode>; 00052 00053 /// Size - The current size of the node. This should be equal to the size of 00054 /// the current type record. 00055 /// 00056 unsigned Size; 00057 00058 /// ParentGraph - The graph this node is currently embedded into. 00059 /// 00060 DSGraph *ParentGraph; 00061 00062 /// Ty - Keep track of the current outer most type of this object, in addition 00063 /// to whether or not it has been indexed like an array or not. If the 00064 /// isArray bit is set, the node cannot grow. 00065 /// 00066 const Type *Ty; // The type itself... 00067 00068 /// Links - Contains one entry for every sizeof(void*) bytes in this memory 00069 /// object. Note that if the node is not a multiple of size(void*) bytes 00070 /// large, that there is an extra entry for the "remainder" of the node as 00071 /// well. For this reason, nodes of 1 byte in size do have one link. 00072 /// 00073 std::vector<DSNodeHandle> Links; 00074 00075 /// Globals - The list of global values that are merged into this node. 00076 /// 00077 std::vector<GlobalValue*> Globals; 00078 00079 void operator=(const DSNode &); // DO NOT IMPLEMENT 00080 DSNode(const DSNode &); // DO NOT IMPLEMENT 00081 public: 00082 enum NodeTy { 00083 ShadowNode = 0, // Nothing is known about this node... 00084 AllocaNode = 1 << 0, // This node was allocated with alloca 00085 HeapNode = 1 << 1, // This node was allocated with malloc 00086 GlobalNode = 1 << 2, // This node was allocated by a global var decl 00087 UnknownNode = 1 << 3, // This node points to unknown allocated memory 00088 Incomplete = 1 << 4, // This node may not be complete 00089 00090 Modified = 1 << 5, // This node is modified in this context 00091 Read = 1 << 6, // This node is read in this context 00092 00093 Array = 1 << 7, // This node is treated like an array 00094 //#ifndef NDEBUG 00095 DEAD = 1 << 8, // This node is dead and should not be pointed to 00096 //#endif 00097 00098 Composition = AllocaNode | HeapNode | GlobalNode | UnknownNode 00099 }; 00100 00101 /// NodeType - A union of the above bits. "Shadow" nodes do not add any flags 00102 /// to the nodes in the data structure graph, so it is possible to have nodes 00103 /// with a value of 0 for their NodeType. 00104 /// 00105 private: 00106 unsigned short NodeType; 00107 public: 00108 00109 /// DSNode ctor - Create a node of the specified type, inserting it into the 00110 /// specified graph. 00111 /// 00112 DSNode(const Type *T, DSGraph *G); 00113 00114 /// DSNode "copy ctor" - Copy the specified node, inserting it into the 00115 /// specified graph. If NullLinks is true, then null out all of the links, 00116 /// but keep the same number of them. This can be used for efficiency if the 00117 /// links are just going to be clobbered anyway. 00118 /// 00119 DSNode(const DSNode &, DSGraph *G, bool NullLinks = false); 00120 00121 ~DSNode() { 00122 dropAllReferences(); 00123 assert(hasNoReferrers() && "Referrers to dead node exist!"); 00124 } 00125 00126 // Iterator for graph interface... Defined in DSGraphTraits.h 00127 typedef DSNodeIterator<DSNode> iterator; 00128 typedef DSNodeIterator<const DSNode> const_iterator; 00129 inline iterator begin(); 00130 inline iterator end(); 00131 inline const_iterator begin() const; 00132 inline const_iterator end() const; 00133 00134 //===-------------------------------------------------- 00135 // Accessors 00136 00137 /// getSize - Return the maximum number of bytes occupied by this object... 00138 /// 00139 unsigned getSize() const { return Size; } 00140 00141 /// getType - Return the node type of this object... 00142 /// 00143 const Type *getType() const { return Ty; } 00144 00145 bool isArray() const { return NodeType & Array; } 00146 00147 /// hasNoReferrers - Return true if nothing is pointing to this node at all. 00148 /// 00149 bool hasNoReferrers() const { return getNumReferrers() == 0; } 00150 00151 /// getNumReferrers - This method returns the number of referrers to the 00152 /// current node. Note that if this node is a forwarding node, this will 00153 /// return the number of nodes forwarding over the node! 00154 unsigned getNumReferrers() const { return NumReferrers; } 00155 00156 DSGraph *getParentGraph() const { return ParentGraph; } 00157 void setParentGraph(DSGraph *G) { ParentGraph = G; } 00158 00159 00160 /// getTargetData - Get the target data object used to construct this node. 00161 /// 00162 const TargetData &getTargetData() const; 00163 00164 /// getForwardNode - This method returns the node that this node is forwarded 00165 /// to, if any. 00166 /// 00167 DSNode *getForwardNode() const { return ForwardNH.getNode(); } 00168 00169 /// isForwarding - Return true if this node is forwarding to another. 00170 /// 00171 bool isForwarding() const { return !ForwardNH.isNull(); } 00172 00173 /// stopForwarding - When the last reference to this forwarding node has been 00174 /// dropped, delete the node. 00175 /// 00176 void stopForwarding() { 00177 assert(isForwarding() && 00178 "Node isn't forwarding, cannot stopForwarding()!"); 00179 ForwardNH.setTo(0, 0); 00180 assert(ParentGraph == 0 && 00181 "Forwarding nodes must have been removed from graph!"); 00182 delete this; 00183 } 00184 00185 /// hasLink - Return true if this memory object has a link in slot LinkNo 00186 /// 00187 bool hasLink(unsigned Offset) const { 00188 assert((Offset & ((1 << DS::PointerShift)-1)) == 0 && 00189 "Pointer offset not aligned correctly!"); 00190 unsigned Index = Offset >> DS::PointerShift; 00191 assert(Index < Links.size() && "Link index is out of range!"); 00192 return Links[Index].getNode(); 00193 } 00194 00195 /// getLink - Return the link at the specified offset. 00196 /// 00197 DSNodeHandle &getLink(unsigned Offset) { 00198 assert((Offset & ((1 << DS::PointerShift)-1)) == 0 && 00199 "Pointer offset not aligned correctly!"); 00200 unsigned Index = Offset >> DS::PointerShift; 00201 assert(Index < Links.size() && "Link index is out of range!"); 00202 return Links[Index]; 00203 } 00204 const DSNodeHandle &getLink(unsigned Offset) const { 00205 assert((Offset & ((1 << DS::PointerShift)-1)) == 0 && 00206 "Pointer offset not aligned correctly!"); 00207 unsigned Index = Offset >> DS::PointerShift; 00208 assert(Index < Links.size() && "Link index is out of range!"); 00209 return Links[Index]; 00210 } 00211 00212 /// getNumLinks - Return the number of links in a node... 00213 /// 00214 unsigned getNumLinks() const { return Links.size(); } 00215 00216 /// edge_* - Provide iterators for accessing outgoing edges. Some outgoing 00217 /// edges may be null. 00218 typedef std::vector<DSNodeHandle>::iterator edge_iterator; 00219 typedef std::vector<DSNodeHandle>::const_iterator const_edge_iterator; 00220 edge_iterator edge_begin() { return Links.begin(); } 00221 edge_iterator edge_end() { return Links.end(); } 00222 const_edge_iterator edge_begin() const { return Links.begin(); } 00223 const_edge_iterator edge_end() const { return Links.end(); } 00224 00225 00226 /// mergeTypeInfo - This method merges the specified type into the current 00227 /// node at the specified offset. This may update the current node's type 00228 /// record if this gives more information to the node, it may do nothing to 00229 /// the node if this information is already known, or it may merge the node 00230 /// completely (and return true) if the information is incompatible with what 00231 /// is already known. 00232 /// 00233 /// This method returns true if the node is completely folded, otherwise 00234 /// false. 00235 /// 00236 bool mergeTypeInfo(const Type *Ty, unsigned Offset, 00237 bool FoldIfIncompatible = true); 00238 00239 /// foldNodeCompletely - If we determine that this node has some funny 00240 /// behavior happening to it that we cannot represent, we fold it down to a 00241 /// single, completely pessimistic, node. This node is represented as a 00242 /// single byte with a single TypeEntry of "void" with isArray = true. 00243 /// 00244 void foldNodeCompletely(); 00245 00246 /// isNodeCompletelyFolded - Return true if this node has been completely 00247 /// folded down to something that can never be expanded, effectively losing 00248 /// all of the field sensitivity that may be present in the node. 00249 /// 00250 bool isNodeCompletelyFolded() const; 00251 00252 /// setLink - Set the link at the specified offset to the specified 00253 /// NodeHandle, replacing what was there. It is uncommon to use this method, 00254 /// instead one of the higher level methods should be used, below. 00255 /// 00256 void setLink(unsigned Offset, const DSNodeHandle &NH) { 00257 assert((Offset & ((1 << DS::PointerShift)-1)) == 0 && 00258 "Pointer offset not aligned correctly!"); 00259 unsigned Index = Offset >> DS::PointerShift; 00260 assert(Index < Links.size() && "Link index is out of range!"); 00261 Links[Index] = NH; 00262 } 00263 00264 /// getPointerSize - Return the size of a pointer for the current target. 00265 /// 00266 unsigned getPointerSize() const { return DS::PointerSize; } 00267 00268 /// addEdgeTo - Add an edge from the current node to the specified node. This 00269 /// can cause merging of nodes in the graph. 00270 /// 00271 void addEdgeTo(unsigned Offset, const DSNodeHandle &NH); 00272 00273 /// mergeWith - Merge this node and the specified node, moving all links to 00274 /// and from the argument node into the current node, deleting the node 00275 /// argument. Offset indicates what offset the specified node is to be merged 00276 /// into the current node. 00277 /// 00278 /// The specified node may be a null pointer (in which case, nothing happens). 00279 /// 00280 void mergeWith(const DSNodeHandle &NH, unsigned Offset); 00281 00282 /// addGlobal - Add an entry for a global value to the Globals list. This 00283 /// also marks the node with the 'G' flag if it does not already have it. 00284 /// 00285 void addGlobal(GlobalValue *GV); 00286 00287 /// removeGlobal - Remove the specified global that is explicitly in the 00288 /// globals list. 00289 void removeGlobal(GlobalValue *GV); 00290 00291 void mergeGlobals(const std::vector<GlobalValue*> &RHS); 00292 void clearGlobals() { std::vector<GlobalValue*>().swap(Globals); } 00293 00294 /// getGlobalsList - Return the set of global leaders that are represented by 00295 /// this node. Note that globals that are in this equivalence class but are 00296 /// not leaders are not returned: for that, use addFullGlobalsList(). 00297 const std::vector<GlobalValue*> &getGlobalsList() const { return Globals; } 00298 00299 /// addFullGlobalsList - Compute the full set of global values that are 00300 /// represented by this node. Unlike getGlobalsList(), this requires fair 00301 /// amount of work to compute, so don't treat this method call as free. 00302 void addFullGlobalsList(std::vector<GlobalValue*> &List) const; 00303 00304 /// addFullFunctionList - Identical to addFullGlobalsList, but only return the 00305 /// functions in the full list. 00306 void addFullFunctionList(std::vector<Function*> &List) const; 00307 00308 /// globals_iterator/begin/end - Provide iteration methods over the global 00309 /// value leaders set that is merged into this node. Like the getGlobalsList 00310 /// method, these iterators do not return globals that are part of the 00311 /// equivalence classes for globals in this node, but aren't leaders. 00312 typedef std::vector<GlobalValue*>::const_iterator globals_iterator; 00313 globals_iterator globals_begin() const { return Globals.begin(); } 00314 globals_iterator globals_end() const { return Globals.end(); } 00315 00316 00317 /// maskNodeTypes - Apply a mask to the node types bitfield. 00318 /// 00319 void maskNodeTypes(unsigned Mask) { 00320 NodeType &= Mask; 00321 } 00322 00323 void mergeNodeFlags(unsigned RHS) { 00324 NodeType |= RHS; 00325 } 00326 00327 /// getNodeFlags - Return all of the flags set on the node. If the DEAD flag 00328 /// is set, hide it from the caller. 00329 /// 00330 unsigned getNodeFlags() const { return NodeType & ~DEAD; } 00331 00332 bool isAllocaNode() const { return NodeType & AllocaNode; } 00333 bool isHeapNode() const { return NodeType & HeapNode; } 00334 bool isGlobalNode() const { return NodeType & GlobalNode; } 00335 bool isUnknownNode() const { return NodeType & UnknownNode; } 00336 00337 bool isModified() const { return NodeType & Modified; } 00338 bool isRead() const { return NodeType & Read; } 00339 00340 bool isIncomplete() const { return NodeType & Incomplete; } 00341 bool isComplete() const { return !isIncomplete(); } 00342 bool isDeadNode() const { return NodeType & DEAD; } 00343 00344 DSNode *setAllocaNodeMarker() { NodeType |= AllocaNode; return this; } 00345 DSNode *setHeapNodeMarker() { NodeType |= HeapNode; return this; } 00346 DSNode *setGlobalNodeMarker() { NodeType |= GlobalNode; return this; } 00347 DSNode *setUnknownNodeMarker() { NodeType |= UnknownNode; return this; } 00348 00349 DSNode *setIncompleteMarker() { NodeType |= Incomplete; return this; } 00350 DSNode *setModifiedMarker() { NodeType |= Modified; return this; } 00351 DSNode *setReadMarker() { NodeType |= Read; return this; } 00352 DSNode *setArrayMarker() { NodeType |= Array; return this; } 00353 00354 void makeNodeDead() { 00355 Globals.clear(); 00356 assert(hasNoReferrers() && "Dead node shouldn't have refs!"); 00357 NodeType = DEAD; 00358 } 00359 00360 /// forwardNode - Mark this node as being obsolete, and all references to it 00361 /// should be forwarded to the specified node and offset. 00362 /// 00363 void forwardNode(DSNode *To, unsigned Offset); 00364 00365 void print(std::ostream &O, const DSGraph *G) const; 00366 void dump() const; 00367 00368 void assertOK() const; 00369 00370 void dropAllReferences() { 00371 Links.clear(); 00372 if (isForwarding()) 00373 ForwardNH.setTo(0, 0); 00374 } 00375 00376 /// remapLinks - Change all of the Links in the current node according to the 00377 /// specified mapping. 00378 /// 00379 void remapLinks(hash_map<const DSNode*, DSNodeHandle> &OldNodeMap); 00380 00381 /// markReachableNodes - This method recursively traverses the specified 00382 /// DSNodes, marking any nodes which are reachable. All reachable nodes it 00383 /// adds to the set, which allows it to only traverse visited nodes once. 00384 /// 00385 void markReachableNodes(hash_set<const DSNode*> &ReachableNodes) const; 00386 00387 private: 00388 friend class DSNodeHandle; 00389 00390 // static mergeNodes - Helper for mergeWith() 00391 static void MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH); 00392 }; 00393 00394 //===----------------------------------------------------------------------===// 00395 // Define the ilist_traits specialization for the DSGraph ilist. 00396 // 00397 template<> 00398 struct ilist_traits<DSNode> { 00399 static DSNode *getPrev(const DSNode *N) { return N->Prev; } 00400 static DSNode *getNext(const DSNode *N) { return N->Next; } 00401 00402 static void setPrev(DSNode *N, DSNode *Prev) { N->Prev = Prev; } 00403 static void setNext(DSNode *N, DSNode *Next) { N->Next = Next; } 00404 00405 static DSNode *createSentinel() { return new DSNode(0,0); } 00406 static void destroySentinel(DSNode *N) { delete N; } 00407 //static DSNode *createNode(const DSNode &V) { return new DSNode(V); } 00408 00409 00410 void addNodeToList(DSNode *NTy) {} 00411 void removeNodeFromList(DSNode *NTy) {} 00412 void transferNodesFromList(iplist<DSNode, ilist_traits> &L2, 00413 ilist_iterator<DSNode> first, 00414 ilist_iterator<DSNode> last) {} 00415 }; 00416 00417 template<> 00418 struct ilist_traits<const DSNode> : public ilist_traits<DSNode> {}; 00419 00420 //===----------------------------------------------------------------------===// 00421 // Define inline DSNodeHandle functions that depend on the definition of DSNode 00422 // 00423 inline DSNode *DSNodeHandle::getNode() const { 00424 // Disabling this assertion because it is failing on a "magic" struct 00425 // in named (from bind). The fourth field is an array of length 0, 00426 // presumably used to create struct instances of different sizes. 00427 // In a variable length struct, Offset could exceed Size when getNode() 00428 // is called before such a node is folded. In this case, the DS Analysis now 00429 // correctly folds this node after calling getNode. 00430 /* assert((!N || 00431 N->isNodeCompletelyFolded() || 00432 (N->Size == 0 && Offset == 0) || 00433 (int(Offset) >= 0 && Offset < N->Size) || 00434 (int(Offset) < 0 && -int(Offset) < int(N->Size)) || 00435 N->isForwarding()) && "Node handle offset out of range!"); 00436 */ 00437 if (N == 0 || !N->isForwarding()) 00438 return N; 00439 00440 return HandleForwarding(); 00441 } 00442 00443 inline void DSNodeHandle::setTo(DSNode *n, unsigned NewOffset) const { 00444 assert(!n || !n->isForwarding() && "Cannot set node to a forwarded node!"); 00445 if (N) getNode()->NumReferrers--; 00446 N = n; 00447 Offset = NewOffset; 00448 if (N) { 00449 N->NumReferrers++; 00450 if (Offset >= N->Size) { 00451 assert((Offset == 0 || N->Size == 1) && 00452 "Pointer to non-collapsed node with invalid offset!"); 00453 Offset = 0; 00454 } 00455 } 00456 assert(!N || ((N->NodeType & DSNode::DEAD) == 0)); 00457 assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) || 00458 N->isForwarding()) && "Node handle offset out of range!"); 00459 } 00460 00461 inline bool DSNodeHandle::hasLink(unsigned Num) const { 00462 assert(N && "DSNodeHandle does not point to a node yet!"); 00463 return getNode()->hasLink(Num+Offset); 00464 } 00465 00466 00467 /// getLink - Treat this current node pointer as a pointer to a structure of 00468 /// some sort. This method will return the pointer a mem[this+Num] 00469 /// 00470 inline const DSNodeHandle &DSNodeHandle::getLink(unsigned Off) const { 00471 assert(N && "DSNodeHandle does not point to a node yet!"); 00472 return getNode()->getLink(Offset+Off); 00473 } 00474 inline DSNodeHandle &DSNodeHandle::getLink(unsigned Off) { 00475 assert(N && "DSNodeHandle does not point to a node yet!"); 00476 return getNode()->getLink(Off+Offset); 00477 } 00478 00479 inline void DSNodeHandle::setLink(unsigned Off, const DSNodeHandle &NH) { 00480 assert(N && "DSNodeHandle does not point to a node yet!"); 00481 getNode()->setLink(Off+Offset, NH); 00482 } 00483 00484 /// addEdgeTo - Add an edge from the current node to the specified node. This 00485 /// can cause merging of nodes in the graph. 00486 /// 00487 inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) { 00488 assert(N && "DSNodeHandle does not point to a node yet!"); 00489 getNode()->addEdgeTo(Off+Offset, Node); 00490 } 00491 00492 /// mergeWith - Merge the logical node pointed to by 'this' with the node 00493 /// pointed to by 'N'. 00494 /// 00495 inline void DSNodeHandle::mergeWith(const DSNodeHandle &Node) const { 00496 if (!isNull()) 00497 getNode()->mergeWith(Node, Offset); 00498 else { // No node to merge with, so just point to Node 00499 Offset = 0; 00500 DSNode *NN = Node.getNode(); 00501 setTo(NN, Node.getOffset()); 00502 } 00503 } 00504 00505 } // End llvm namespace 00506 00507 #endif