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