LLVM API Documentation
00001 //===- DataStructure.cpp - Implement the core data structure analysis -----===// 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 // This file implements the core data structure functionality. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/Analysis/DataStructure/DSGraphTraits.h" 00015 #include "llvm/Function.h" 00016 #include "llvm/GlobalVariable.h" 00017 #include "llvm/Instructions.h" 00018 #include "llvm/DerivedTypes.h" 00019 #include "llvm/Target/TargetData.h" 00020 #include "llvm/Assembly/Writer.h" 00021 #include "llvm/Support/CommandLine.h" 00022 #include "llvm/Support/Debug.h" 00023 #include "llvm/ADT/DepthFirstIterator.h" 00024 #include "llvm/ADT/STLExtras.h" 00025 #include "llvm/ADT/Statistic.h" 00026 #include "llvm/Support/Timer.h" 00027 #include <algorithm> 00028 using namespace llvm; 00029 00030 namespace { 00031 Statistic<> NumFolds ("dsa", "Number of nodes completely folded"); 00032 Statistic<> NumCallNodesMerged("dsa", "Number of call nodes merged"); 00033 Statistic<> NumNodeAllocated ("dsa", "Number of nodes allocated"); 00034 Statistic<> NumDNE ("dsa", "Number of nodes removed by reachability"); 00035 Statistic<> NumTrivialDNE ("dsa", "Number of nodes trivially removed"); 00036 Statistic<> NumTrivialGlobalDNE("dsa", "Number of globals trivially removed"); 00037 }; 00038 00039 #if 1 00040 #define TIME_REGION(VARNAME, DESC) \ 00041 NamedRegionTimer VARNAME(DESC) 00042 #else 00043 #define TIME_REGION(VARNAME, DESC) 00044 #endif 00045 00046 using namespace DS; 00047 00048 /// isForwarding - Return true if this NodeHandle is forwarding to another 00049 /// one. 00050 bool DSNodeHandle::isForwarding() const { 00051 return N && N->isForwarding(); 00052 } 00053 00054 DSNode *DSNodeHandle::HandleForwarding() const { 00055 assert(N->isForwarding() && "Can only be invoked if forwarding!"); 00056 00057 // Handle node forwarding here! 00058 DSNode *Next = N->ForwardNH.getNode(); // Cause recursive shrinkage 00059 Offset += N->ForwardNH.getOffset(); 00060 00061 if (--N->NumReferrers == 0) { 00062 // Removing the last referrer to the node, sever the forwarding link 00063 N->stopForwarding(); 00064 } 00065 00066 N = Next; 00067 N->NumReferrers++; 00068 if (N->Size <= Offset) { 00069 assert(N->Size <= 1 && "Forwarded to shrunk but not collapsed node?"); 00070 Offset = 0; 00071 } 00072 return N; 00073 } 00074 00075 //===----------------------------------------------------------------------===// 00076 // DSNode Implementation 00077 //===----------------------------------------------------------------------===// 00078 00079 DSNode::DSNode(const Type *T, DSGraph *G) 00080 : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(0) { 00081 // Add the type entry if it is specified... 00082 if (T) mergeTypeInfo(T, 0); 00083 if (G) G->addNode(this); 00084 ++NumNodeAllocated; 00085 } 00086 00087 // DSNode copy constructor... do not copy over the referrers list! 00088 DSNode::DSNode(const DSNode &N, DSGraph *G, bool NullLinks) 00089 : NumReferrers(0), Size(N.Size), ParentGraph(G), 00090 Ty(N.Ty), NodeType(N.NodeType) { 00091 if (!NullLinks) { 00092 Links = N.Links; 00093 Globals = N.Globals; 00094 } else 00095 Links.resize(N.Links.size()); // Create the appropriate number of null links 00096 G->addNode(this); 00097 ++NumNodeAllocated; 00098 } 00099 00100 /// getTargetData - Get the target data object used to construct this node. 00101 /// 00102 const TargetData &DSNode::getTargetData() const { 00103 return ParentGraph->getTargetData(); 00104 } 00105 00106 void DSNode::assertOK() const { 00107 assert((Ty != Type::VoidTy || 00108 Ty == Type::VoidTy && (Size == 0 || 00109 (NodeType & DSNode::Array))) && 00110 "Node not OK!"); 00111 00112 assert(ParentGraph && "Node has no parent?"); 00113 const DSScalarMap &SM = ParentGraph->getScalarMap(); 00114 for (unsigned i = 0, e = Globals.size(); i != e; ++i) { 00115 assert(SM.count(Globals[i])); 00116 assert(SM.find(Globals[i])->second.getNode() == this); 00117 } 00118 } 00119 00120 /// forwardNode - Mark this node as being obsolete, and all references to it 00121 /// should be forwarded to the specified node and offset. 00122 /// 00123 void DSNode::forwardNode(DSNode *To, unsigned Offset) { 00124 assert(this != To && "Cannot forward a node to itself!"); 00125 assert(ForwardNH.isNull() && "Already forwarding from this node!"); 00126 if (To->Size <= 1) Offset = 0; 00127 assert((Offset < To->Size || (Offset == To->Size && Offset == 0)) && 00128 "Forwarded offset is wrong!"); 00129 ForwardNH.setTo(To, Offset); 00130 NodeType = DEAD; 00131 Size = 0; 00132 Ty = Type::VoidTy; 00133 00134 // Remove this node from the parent graph's Nodes list. 00135 ParentGraph->unlinkNode(this); 00136 ParentGraph = 0; 00137 } 00138 00139 // addGlobal - Add an entry for a global value to the Globals list. This also 00140 // marks the node with the 'G' flag if it does not already have it. 00141 // 00142 void DSNode::addGlobal(GlobalValue *GV) { 00143 // Keep the list sorted. 00144 std::vector<GlobalValue*>::iterator I = 00145 std::lower_bound(Globals.begin(), Globals.end(), GV); 00146 00147 if (I == Globals.end() || *I != GV) { 00148 //assert(GV->getType()->getElementType() == Ty); 00149 Globals.insert(I, GV); 00150 NodeType |= GlobalNode; 00151 } 00152 } 00153 00154 /// foldNodeCompletely - If we determine that this node has some funny 00155 /// behavior happening to it that we cannot represent, we fold it down to a 00156 /// single, completely pessimistic, node. This node is represented as a 00157 /// single byte with a single TypeEntry of "void". 00158 /// 00159 void DSNode::foldNodeCompletely() { 00160 if (isNodeCompletelyFolded()) return; // If this node is already folded... 00161 00162 ++NumFolds; 00163 00164 // If this node has a size that is <= 1, we don't need to create a forwarding 00165 // node. 00166 if (getSize() <= 1) { 00167 NodeType |= DSNode::Array; 00168 Ty = Type::VoidTy; 00169 Size = 1; 00170 assert(Links.size() <= 1 && "Size is 1, but has more links?"); 00171 Links.resize(1); 00172 } else { 00173 // Create the node we are going to forward to. This is required because 00174 // some referrers may have an offset that is > 0. By forcing them to 00175 // forward, the forwarder has the opportunity to correct the offset. 00176 DSNode *DestNode = new DSNode(0, ParentGraph); 00177 DestNode->NodeType = NodeType|DSNode::Array; 00178 DestNode->Ty = Type::VoidTy; 00179 DestNode->Size = 1; 00180 DestNode->Globals.swap(Globals); 00181 00182 // Start forwarding to the destination node... 00183 forwardNode(DestNode, 0); 00184 00185 if (!Links.empty()) { 00186 DestNode->Links.reserve(1); 00187 00188 DSNodeHandle NH(DestNode); 00189 DestNode->Links.push_back(Links[0]); 00190 00191 // If we have links, merge all of our outgoing links together... 00192 for (unsigned i = Links.size()-1; i != 0; --i) 00193 NH.getNode()->Links[0].mergeWith(Links[i]); 00194 Links.clear(); 00195 } else { 00196 DestNode->Links.resize(1); 00197 } 00198 } 00199 } 00200 00201 /// isNodeCompletelyFolded - Return true if this node has been completely 00202 /// folded down to something that can never be expanded, effectively losing 00203 /// all of the field sensitivity that may be present in the node. 00204 /// 00205 bool DSNode::isNodeCompletelyFolded() const { 00206 return getSize() == 1 && Ty == Type::VoidTy && isArray(); 00207 } 00208 00209 namespace { 00210 /// TypeElementWalker Class - Used for implementation of physical subtyping... 00211 /// 00212 class TypeElementWalker { 00213 struct StackState { 00214 const Type *Ty; 00215 unsigned Offset; 00216 unsigned Idx; 00217 StackState(const Type *T, unsigned Off = 0) 00218 : Ty(T), Offset(Off), Idx(0) {} 00219 }; 00220 00221 std::vector<StackState> Stack; 00222 const TargetData &TD; 00223 public: 00224 TypeElementWalker(const Type *T, const TargetData &td) : TD(td) { 00225 Stack.push_back(T); 00226 StepToLeaf(); 00227 } 00228 00229 bool isDone() const { return Stack.empty(); } 00230 const Type *getCurrentType() const { return Stack.back().Ty; } 00231 unsigned getCurrentOffset() const { return Stack.back().Offset; } 00232 00233 void StepToNextType() { 00234 PopStackAndAdvance(); 00235 StepToLeaf(); 00236 } 00237 00238 private: 00239 /// PopStackAndAdvance - Pop the current element off of the stack and 00240 /// advance the underlying element to the next contained member. 00241 void PopStackAndAdvance() { 00242 assert(!Stack.empty() && "Cannot pop an empty stack!"); 00243 Stack.pop_back(); 00244 while (!Stack.empty()) { 00245 StackState &SS = Stack.back(); 00246 if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) { 00247 ++SS.Idx; 00248 if (SS.Idx != ST->getNumElements()) { 00249 const StructLayout *SL = TD.getStructLayout(ST); 00250 SS.Offset += SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1]; 00251 return; 00252 } 00253 Stack.pop_back(); // At the end of the structure 00254 } else { 00255 const ArrayType *AT = cast<ArrayType>(SS.Ty); 00256 ++SS.Idx; 00257 if (SS.Idx != AT->getNumElements()) { 00258 SS.Offset += TD.getTypeSize(AT->getElementType()); 00259 return; 00260 } 00261 Stack.pop_back(); // At the end of the array 00262 } 00263 } 00264 } 00265 00266 /// StepToLeaf - Used by physical subtyping to move to the first leaf node 00267 /// on the type stack. 00268 void StepToLeaf() { 00269 if (Stack.empty()) return; 00270 while (!Stack.empty() && !Stack.back().Ty->isFirstClassType()) { 00271 StackState &SS = Stack.back(); 00272 if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) { 00273 if (ST->getNumElements() == 0) { 00274 assert(SS.Idx == 0); 00275 PopStackAndAdvance(); 00276 } else { 00277 // Step into the structure... 00278 assert(SS.Idx < ST->getNumElements()); 00279 const StructLayout *SL = TD.getStructLayout(ST); 00280 Stack.push_back(StackState(ST->getElementType(SS.Idx), 00281 SS.Offset+SL->MemberOffsets[SS.Idx])); 00282 } 00283 } else { 00284 const ArrayType *AT = cast<ArrayType>(SS.Ty); 00285 if (AT->getNumElements() == 0) { 00286 assert(SS.Idx == 0); 00287 PopStackAndAdvance(); 00288 } else { 00289 // Step into the array... 00290 assert(SS.Idx < AT->getNumElements()); 00291 Stack.push_back(StackState(AT->getElementType(), 00292 SS.Offset+SS.Idx* 00293 TD.getTypeSize(AT->getElementType()))); 00294 } 00295 } 00296 } 00297 } 00298 }; 00299 } // end anonymous namespace 00300 00301 /// ElementTypesAreCompatible - Check to see if the specified types are 00302 /// "physically" compatible. If so, return true, else return false. We only 00303 /// have to check the fields in T1: T2 may be larger than T1. If AllowLargerT1 00304 /// is true, then we also allow a larger T1. 00305 /// 00306 static bool ElementTypesAreCompatible(const Type *T1, const Type *T2, 00307 bool AllowLargerT1, const TargetData &TD){ 00308 TypeElementWalker T1W(T1, TD), T2W(T2, TD); 00309 00310 while (!T1W.isDone() && !T2W.isDone()) { 00311 if (T1W.getCurrentOffset() != T2W.getCurrentOffset()) 00312 return false; 00313 00314 const Type *T1 = T1W.getCurrentType(); 00315 const Type *T2 = T2W.getCurrentType(); 00316 if (T1 != T2 && !T1->isLosslesslyConvertibleTo(T2)) 00317 return false; 00318 00319 T1W.StepToNextType(); 00320 T2W.StepToNextType(); 00321 } 00322 00323 return AllowLargerT1 || T1W.isDone(); 00324 } 00325 00326 00327 /// mergeTypeInfo - This method merges the specified type into the current node 00328 /// at the specified offset. This may update the current node's type record if 00329 /// this gives more information to the node, it may do nothing to the node if 00330 /// this information is already known, or it may merge the node completely (and 00331 /// return true) if the information is incompatible with what is already known. 00332 /// 00333 /// This method returns true if the node is completely folded, otherwise false. 00334 /// 00335 bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, 00336 bool FoldIfIncompatible) { 00337 const TargetData &TD = getTargetData(); 00338 // Check to make sure the Size member is up-to-date. Size can be one of the 00339 // following: 00340 // Size = 0, Ty = Void: Nothing is known about this node. 00341 // Size = 0, Ty = FnTy: FunctionPtr doesn't have a size, so we use zero 00342 // Size = 1, Ty = Void, Array = 1: The node is collapsed 00343 // Otherwise, sizeof(Ty) = Size 00344 // 00345 assert(((Size == 0 && Ty == Type::VoidTy && !isArray()) || 00346 (Size == 0 && !Ty->isSized() && !isArray()) || 00347 (Size == 1 && Ty == Type::VoidTy && isArray()) || 00348 (Size == 0 && !Ty->isSized() && !isArray()) || 00349 (TD.getTypeSize(Ty) == Size)) && 00350 "Size member of DSNode doesn't match the type structure!"); 00351 assert(NewTy != Type::VoidTy && "Cannot merge void type into DSNode!"); 00352 00353 if (Offset == 0 && NewTy == Ty) 00354 return false; // This should be a common case, handle it efficiently 00355 00356 // Return true immediately if the node is completely folded. 00357 if (isNodeCompletelyFolded()) return true; 00358 00359 // If this is an array type, eliminate the outside arrays because they won't 00360 // be used anyway. This greatly reduces the size of large static arrays used 00361 // as global variables, for example. 00362 // 00363 bool WillBeArray = false; 00364 while (const ArrayType *AT = dyn_cast<ArrayType>(NewTy)) { 00365 // FIXME: we might want to keep small arrays, but must be careful about 00366 // things like: [2 x [10000 x int*]] 00367 NewTy = AT->getElementType(); 00368 WillBeArray = true; 00369 } 00370 00371 // Figure out how big the new type we're merging in is... 00372 unsigned NewTySize = NewTy->isSized() ? TD.getTypeSize(NewTy) : 0; 00373 00374 // Otherwise check to see if we can fold this type into the current node. If 00375 // we can't, we fold the node completely, if we can, we potentially update our 00376 // internal state. 00377 // 00378 if (Ty == Type::VoidTy) { 00379 // If this is the first type that this node has seen, just accept it without 00380 // question.... 00381 assert(Offset == 0 && !isArray() && 00382 "Cannot have an offset into a void node!"); 00383 Ty = NewTy; 00384 NodeType &= ~Array; 00385 if (WillBeArray) NodeType |= Array; 00386 Size = NewTySize; 00387 00388 // Calculate the number of outgoing links from this node. 00389 Links.resize((Size+DS::PointerSize-1) >> DS::PointerShift); 00390 return false; 00391 } 00392 00393 // Handle node expansion case here... 00394 if (Offset+NewTySize > Size) { 00395 // It is illegal to grow this node if we have treated it as an array of 00396 // objects... 00397 if (isArray()) { 00398 if (FoldIfIncompatible) foldNodeCompletely(); 00399 return true; 00400 } 00401 00402 if (Offset) { // We could handle this case, but we don't for now... 00403 std::cerr << "UNIMP: Trying to merge a growth type into " 00404 << "offset != 0: Collapsing!\n"; 00405 if (FoldIfIncompatible) foldNodeCompletely(); 00406 return true; 00407 } 00408 00409 // Okay, the situation is nice and simple, we are trying to merge a type in 00410 // at offset 0 that is bigger than our current type. Implement this by 00411 // switching to the new type and then merge in the smaller one, which should 00412 // hit the other code path here. If the other code path decides it's not 00413 // ok, it will collapse the node as appropriate. 00414 // 00415 const Type *OldTy = Ty; 00416 Ty = NewTy; 00417 NodeType &= ~Array; 00418 if (WillBeArray) NodeType |= Array; 00419 Size = NewTySize; 00420 00421 // Must grow links to be the appropriate size... 00422 Links.resize((Size+DS::PointerSize-1) >> DS::PointerShift); 00423 00424 // Merge in the old type now... which is guaranteed to be smaller than the 00425 // "current" type. 00426 return mergeTypeInfo(OldTy, 0); 00427 } 00428 00429 assert(Offset <= Size && 00430 "Cannot merge something into a part of our type that doesn't exist!"); 00431 00432 // Find the section of Ty that NewTy overlaps with... first we find the 00433 // type that starts at offset Offset. 00434 // 00435 unsigned O = 0; 00436 const Type *SubType = Ty; 00437 while (O < Offset) { 00438 assert(Offset-O < TD.getTypeSize(SubType) && "Offset out of range!"); 00439 00440 switch (SubType->getTypeID()) { 00441 case Type::StructTyID: { 00442 const StructType *STy = cast<StructType>(SubType); 00443 const StructLayout &SL = *TD.getStructLayout(STy); 00444 00445 unsigned i = 0, e = SL.MemberOffsets.size(); 00446 for (; i+1 < e && SL.MemberOffsets[i+1] <= Offset-O; ++i) 00447 /* empty */; 00448 00449 // The offset we are looking for must be in the i'th element... 00450 SubType = STy->getElementType(i); 00451 O += SL.MemberOffsets[i]; 00452 break; 00453 } 00454 case Type::ArrayTyID: { 00455 SubType = cast<ArrayType>(SubType)->getElementType(); 00456 unsigned ElSize = TD.getTypeSize(SubType); 00457 unsigned Remainder = (Offset-O) % ElSize; 00458 O = Offset-Remainder; 00459 break; 00460 } 00461 default: 00462 if (FoldIfIncompatible) foldNodeCompletely(); 00463 return true; 00464 } 00465 } 00466 00467 assert(O == Offset && "Could not achieve the correct offset!"); 00468 00469 // If we found our type exactly, early exit 00470 if (SubType == NewTy) return false; 00471 00472 // Differing function types don't require us to merge. They are not values 00473 // anyway. 00474 if (isa<FunctionType>(SubType) && 00475 isa<FunctionType>(NewTy)) return false; 00476 00477 unsigned SubTypeSize = SubType->isSized() ? TD.getTypeSize(SubType) : 0; 00478 00479 // Ok, we are getting desperate now. Check for physical subtyping, where we 00480 // just require each element in the node to be compatible. 00481 if (NewTySize <= SubTypeSize && NewTySize && NewTySize < 256 && 00482 SubTypeSize && SubTypeSize < 256 && 00483 ElementTypesAreCompatible(NewTy, SubType, !isArray(), TD)) 00484 return false; 00485 00486 // Okay, so we found the leader type at the offset requested. Search the list 00487 // of types that starts at this offset. If SubType is currently an array or 00488 // structure, the type desired may actually be the first element of the 00489 // composite type... 00490 // 00491 unsigned PadSize = SubTypeSize; // Size, including pad memory which is ignored 00492 while (SubType != NewTy) { 00493 const Type *NextSubType = 0; 00494 unsigned NextSubTypeSize = 0; 00495 unsigned NextPadSize = 0; 00496 switch (SubType->getTypeID()) { 00497 case Type::StructTyID: { 00498 const StructType *STy = cast<StructType>(SubType); 00499 const StructLayout &SL = *TD.getStructLayout(STy); 00500 if (SL.MemberOffsets.size() > 1) 00501 NextPadSize = SL.MemberOffsets[1]; 00502 else 00503 NextPadSize = SubTypeSize; 00504 NextSubType = STy->getElementType(0); 00505 NextSubTypeSize = TD.getTypeSize(NextSubType); 00506 break; 00507 } 00508 case Type::ArrayTyID: 00509 NextSubType = cast<ArrayType>(SubType)->getElementType(); 00510 NextSubTypeSize = TD.getTypeSize(NextSubType); 00511 NextPadSize = NextSubTypeSize; 00512 break; 00513 default: ; 00514 // fall out 00515 } 00516 00517 if (NextSubType == 0) 00518 break; // In the default case, break out of the loop 00519 00520 if (NextPadSize < NewTySize) 00521 break; // Don't allow shrinking to a smaller type than NewTySize 00522 SubType = NextSubType; 00523 SubTypeSize = NextSubTypeSize; 00524 PadSize = NextPadSize; 00525 } 00526 00527 // If we found the type exactly, return it... 00528 if (SubType == NewTy) 00529 return false; 00530 00531 // Check to see if we have a compatible, but different type... 00532 if (NewTySize == SubTypeSize) { 00533 // Check to see if this type is obviously convertible... int -> uint f.e. 00534 if (NewTy->isLosslesslyConvertibleTo(SubType)) 00535 return false; 00536 00537 // Check to see if we have a pointer & integer mismatch going on here, 00538 // loading a pointer as a long, for example. 00539 // 00540 if (SubType->isInteger() && isa<PointerType>(NewTy) || 00541 NewTy->isInteger() && isa<PointerType>(SubType)) 00542 return false; 00543 } else if (NewTySize > SubTypeSize && NewTySize <= PadSize) { 00544 // We are accessing the field, plus some structure padding. Ignore the 00545 // structure padding. 00546 return false; 00547 } 00548 00549 Module *M = 0; 00550 if (getParentGraph()->getReturnNodes().size()) 00551 M = getParentGraph()->getReturnNodes().begin()->first->getParent(); 00552 DEBUG(std::cerr << "MergeTypeInfo Folding OrigTy: "; 00553 WriteTypeSymbolic(std::cerr, Ty, M) << "\n due to:"; 00554 WriteTypeSymbolic(std::cerr, NewTy, M) << " @ " << Offset << "!\n" 00555 << "SubType: "; 00556 WriteTypeSymbolic(std::cerr, SubType, M) << "\n\n"); 00557 00558 if (FoldIfIncompatible) foldNodeCompletely(); 00559 return true; 00560 } 00561 00562 00563 00564 /// addEdgeTo - Add an edge from the current node to the specified node. This 00565 /// can cause merging of nodes in the graph. 00566 /// 00567 void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) { 00568 if (NH.isNull()) return; // Nothing to do 00569 00570 DSNodeHandle &ExistingEdge = getLink(Offset); 00571 if (!ExistingEdge.isNull()) { 00572 // Merge the two nodes... 00573 ExistingEdge.mergeWith(NH); 00574 } else { // No merging to perform... 00575 setLink(Offset, NH); // Just force a link in there... 00576 } 00577 } 00578 00579 00580 /// MergeSortedVectors - Efficiently merge a vector into another vector where 00581 /// duplicates are not allowed and both are sorted. This assumes that 'T's are 00582 /// efficiently copyable and have sane comparison semantics. 00583 /// 00584 static void MergeSortedVectors(std::vector<GlobalValue*> &Dest, 00585 const std::vector<GlobalValue*> &Src) { 00586 // By far, the most common cases will be the simple ones. In these cases, 00587 // avoid having to allocate a temporary vector... 00588 // 00589 if (Src.empty()) { // Nothing to merge in... 00590 return; 00591 } else if (Dest.empty()) { // Just copy the result in... 00592 Dest = Src; 00593 } else if (Src.size() == 1) { // Insert a single element... 00594 const GlobalValue *V = Src[0]; 00595 std::vector<GlobalValue*>::iterator I = 00596 std::lower_bound(Dest.begin(), Dest.end(), V); 00597 if (I == Dest.end() || *I != Src[0]) // If not already contained... 00598 Dest.insert(I, Src[0]); 00599 } else if (Dest.size() == 1) { 00600 GlobalValue *Tmp = Dest[0]; // Save value in temporary... 00601 Dest = Src; // Copy over list... 00602 std::vector<GlobalValue*>::iterator I = 00603 std::lower_bound(Dest.begin(), Dest.end(), Tmp); 00604 if (I == Dest.end() || *I != Tmp) // If not already contained... 00605 Dest.insert(I, Tmp); 00606 00607 } else { 00608 // Make a copy to the side of Dest... 00609 std::vector<GlobalValue*> Old(Dest); 00610 00611 // Make space for all of the type entries now... 00612 Dest.resize(Dest.size()+Src.size()); 00613 00614 // Merge the two sorted ranges together... into Dest. 00615 std::merge(Old.begin(), Old.end(), Src.begin(), Src.end(), Dest.begin()); 00616 00617 // Now erase any duplicate entries that may have accumulated into the 00618 // vectors (because they were in both of the input sets) 00619 Dest.erase(std::unique(Dest.begin(), Dest.end()), Dest.end()); 00620 } 00621 } 00622 00623 void DSNode::mergeGlobals(const std::vector<GlobalValue*> &RHS) { 00624 MergeSortedVectors(Globals, RHS); 00625 } 00626 00627 // MergeNodes - Helper function for DSNode::mergeWith(). 00628 // This function does the hard work of merging two nodes, CurNodeH 00629 // and NH after filtering out trivial cases and making sure that 00630 // CurNodeH.offset >= NH.offset. 00631 // 00632 // ***WARNING*** 00633 // Since merging may cause either node to go away, we must always 00634 // use the node-handles to refer to the nodes. These node handles are 00635 // automatically updated during merging, so will always provide access 00636 // to the correct node after a merge. 00637 // 00638 void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { 00639 assert(CurNodeH.getOffset() >= NH.getOffset() && 00640 "This should have been enforced in the caller."); 00641 assert(CurNodeH.getNode()->getParentGraph()==NH.getNode()->getParentGraph() && 00642 "Cannot merge two nodes that are not in the same graph!"); 00643 00644 // Now we know that Offset >= NH.Offset, so convert it so our "Offset" (with 00645 // respect to NH.Offset) is now zero. NOffset is the distance from the base 00646 // of our object that N starts from. 00647 // 00648 unsigned NOffset = CurNodeH.getOffset()-NH.getOffset(); 00649 unsigned NSize = NH.getNode()->getSize(); 00650 00651 // If the two nodes are of different size, and the smaller node has the array 00652 // bit set, collapse! 00653 if (NSize != CurNodeH.getNode()->getSize()) { 00654 if (NSize < CurNodeH.getNode()->getSize()) { 00655 if (NH.getNode()->isArray()) 00656 NH.getNode()->foldNodeCompletely(); 00657 } else if (CurNodeH.getNode()->isArray()) { 00658 NH.getNode()->foldNodeCompletely(); 00659 } 00660 } 00661 00662 // Merge the type entries of the two nodes together... 00663 if (NH.getNode()->Ty != Type::VoidTy) 00664 CurNodeH.getNode()->mergeTypeInfo(NH.getNode()->Ty, NOffset); 00665 assert(!CurNodeH.getNode()->isDeadNode()); 00666 00667 // If we are merging a node with a completely folded node, then both nodes are 00668 // now completely folded. 00669 // 00670 if (CurNodeH.getNode()->isNodeCompletelyFolded()) { 00671 if (!NH.getNode()->isNodeCompletelyFolded()) { 00672 NH.getNode()->foldNodeCompletely(); 00673 assert(NH.getNode() && NH.getOffset() == 0 && 00674 "folding did not make offset 0?"); 00675 NOffset = NH.getOffset(); 00676 NSize = NH.getNode()->getSize(); 00677 assert(NOffset == 0 && NSize == 1); 00678 } 00679 } else if (NH.getNode()->isNodeCompletelyFolded()) { 00680 CurNodeH.getNode()->foldNodeCompletely(); 00681 assert(CurNodeH.getNode() && CurNodeH.getOffset() == 0 && 00682 "folding did not make offset 0?"); 00683 NSize = NH.getNode()->getSize(); 00684 NOffset = NH.getOffset(); 00685 assert(NOffset == 0 && NSize == 1); 00686 } 00687 00688 DSNode *N = NH.getNode(); 00689 if (CurNodeH.getNode() == N || N == 0) return; 00690 assert(!CurNodeH.getNode()->isDeadNode()); 00691 00692 // Merge the NodeType information. 00693 CurNodeH.getNode()->NodeType |= N->NodeType; 00694 00695 // Start forwarding to the new node! 00696 N->forwardNode(CurNodeH.getNode(), NOffset); 00697 assert(!CurNodeH.getNode()->isDeadNode()); 00698 00699 // Make all of the outgoing links of N now be outgoing links of CurNodeH. 00700 // 00701 for (unsigned i = 0; i < N->getNumLinks(); ++i) { 00702 DSNodeHandle &Link = N->getLink(i << DS::PointerShift); 00703 if (Link.getNode()) { 00704 // Compute the offset into the current node at which to 00705 // merge this link. In the common case, this is a linear 00706 // relation to the offset in the original node (with 00707 // wrapping), but if the current node gets collapsed due to 00708 // recursive merging, we must make sure to merge in all remaining 00709 // links at offset zero. 00710 unsigned MergeOffset = 0; 00711 DSNode *CN = CurNodeH.getNode(); 00712 if (CN->Size != 1) 00713 MergeOffset = ((i << DS::PointerShift)+NOffset) % CN->getSize(); 00714 CN->addEdgeTo(MergeOffset, Link); 00715 } 00716 } 00717 00718 // Now that there are no outgoing edges, all of the Links are dead. 00719 N->Links.clear(); 00720 00721 // Merge the globals list... 00722 if (!N->Globals.empty()) { 00723 CurNodeH.getNode()->mergeGlobals(N->Globals); 00724 00725 // Delete the globals from the old node... 00726 std::vector<GlobalValue*>().swap(N->Globals); 00727 } 00728 } 00729 00730 00731 /// mergeWith - Merge this node and the specified node, moving all links to and 00732 /// from the argument node into the current node, deleting the node argument. 00733 /// Offset indicates what offset the specified node is to be merged into the 00734 /// current node. 00735 /// 00736 /// The specified node may be a null pointer (in which case, we update it to 00737 /// point to this node). 00738 /// 00739 void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { 00740 DSNode *N = NH.getNode(); 00741 if (N == this && NH.getOffset() == Offset) 00742 return; // Noop 00743 00744 // If the RHS is a null node, make it point to this node! 00745 if (N == 0) { 00746 NH.mergeWith(DSNodeHandle(this, Offset)); 00747 return; 00748 } 00749 00750 assert(!N->isDeadNode() && !isDeadNode()); 00751 assert(!hasNoReferrers() && "Should not try to fold a useless node!"); 00752 00753 if (N == this) { 00754 // We cannot merge two pieces of the same node together, collapse the node 00755 // completely. 00756 DEBUG(std::cerr << "Attempting to merge two chunks of" 00757 << " the same node together!\n"); 00758 foldNodeCompletely(); 00759 return; 00760 } 00761 00762 // If both nodes are not at offset 0, make sure that we are merging the node 00763 // at an later offset into the node with the zero offset. 00764 // 00765 if (Offset < NH.getOffset()) { 00766 N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset()); 00767 return; 00768 } else if (Offset == NH.getOffset() && getSize() < N->getSize()) { 00769 // If the offsets are the same, merge the smaller node into the bigger node 00770 N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset()); 00771 return; 00772 } 00773 00774 // Ok, now we can merge the two nodes. Use a static helper that works with 00775 // two node handles, since "this" may get merged away at intermediate steps. 00776 DSNodeHandle CurNodeH(this, Offset); 00777 DSNodeHandle NHCopy(NH); 00778 DSNode::MergeNodes(CurNodeH, NHCopy); 00779 } 00780 00781 00782 //===----------------------------------------------------------------------===// 00783 // ReachabilityCloner Implementation 00784 //===----------------------------------------------------------------------===// 00785 00786 DSNodeHandle ReachabilityCloner::getClonedNH(const DSNodeHandle &SrcNH) { 00787 if (SrcNH.isNull()) return DSNodeHandle(); 00788 const DSNode *SN = SrcNH.getNode(); 00789 00790 DSNodeHandle &NH = NodeMap[SN]; 00791 if (!NH.isNull()) { // Node already mapped? 00792 DSNode *NHN = NH.getNode(); 00793 return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset()); 00794 } 00795 00796 // If SrcNH has globals and the destination graph has one of the same globals, 00797 // merge this node with the destination node, which is much more efficient. 00798 if (SN->global_begin() != SN->global_end()) { 00799 DSScalarMap &DestSM = Dest.getScalarMap(); 00800 for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end(); 00801 I != E; ++I) { 00802 GlobalValue *GV = *I; 00803 DSScalarMap::iterator GI = DestSM.find(GV); 00804 if (GI != DestSM.end() && !GI->second.isNull()) { 00805 // We found one, use merge instead! 00806 merge(GI->second, Src.getNodeForValue(GV)); 00807 assert(!NH.isNull() && "Didn't merge node!"); 00808 DSNode *NHN = NH.getNode(); 00809 return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset()); 00810 } 00811 } 00812 } 00813 00814 DSNode *DN = new DSNode(*SN, &Dest, true /* Null out all links */); 00815 DN->maskNodeTypes(BitsToKeep); 00816 NH = DN; 00817 00818 // Next, recursively clone all outgoing links as necessary. Note that 00819 // adding these links can cause the node to collapse itself at any time, and 00820 // the current node may be merged with arbitrary other nodes. For this 00821 // reason, we must always go through NH. 00822 DN = 0; 00823 for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) { 00824 const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift); 00825 if (!SrcEdge.isNull()) { 00826 const DSNodeHandle &DestEdge = getClonedNH(SrcEdge); 00827 // Compute the offset into the current node at which to 00828 // merge this link. In the common case, this is a linear 00829 // relation to the offset in the original node (with 00830 // wrapping), but if the current node gets collapsed due to 00831 // recursive merging, we must make sure to merge in all remaining 00832 // links at offset zero. 00833 unsigned MergeOffset = 0; 00834 DSNode *CN = NH.getNode(); 00835 if (CN->getSize() != 1) 00836 MergeOffset = ((i << DS::PointerShift)+NH.getOffset()) % CN->getSize(); 00837 CN->addEdgeTo(MergeOffset, DestEdge); 00838 } 00839 } 00840 00841 // If this node contains any globals, make sure they end up in the scalar 00842 // map with the correct offset. 00843 for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end(); 00844 I != E; ++I) { 00845 GlobalValue *GV = *I; 00846 const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV); 00847 DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()]; 00848 assert(DestGNH.getNode() == NH.getNode() &&"Global mapping inconsistent"); 00849 Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(), 00850 DestGNH.getOffset()+SrcGNH.getOffset())); 00851 00852 if (CloneFlags & DSGraph::UpdateInlinedGlobals) 00853 Dest.getInlinedGlobals().insert(GV); 00854 } 00855 NH.getNode()->mergeGlobals(SN->getGlobals()); 00856 00857 return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset()); 00858 } 00859 00860 void ReachabilityCloner::merge(const DSNodeHandle &NH, 00861 const DSNodeHandle &SrcNH) { 00862 if (SrcNH.isNull()) return; // Noop 00863 if (NH.isNull()) { 00864 // If there is no destination node, just clone the source and assign the 00865 // destination node to be it. 00866 NH.mergeWith(getClonedNH(SrcNH)); 00867 return; 00868 } 00869 00870 // Okay, at this point, we know that we have both a destination and a source 00871 // node that need to be merged. Check to see if the source node has already 00872 // been cloned. 00873 const DSNode *SN = SrcNH.getNode(); 00874 DSNodeHandle &SCNH = NodeMap[SN]; // SourceClonedNodeHandle 00875 if (!SCNH.isNull()) { // Node already cloned? 00876 DSNode *SCNHN = SCNH.getNode(); 00877 NH.mergeWith(DSNodeHandle(SCNHN, 00878 SCNH.getOffset()+SrcNH.getOffset())); 00879 return; // Nothing to do! 00880 } 00881 00882 // Okay, so the source node has not already been cloned. Instead of creating 00883 // a new DSNode, only to merge it into the one we already have, try to perform 00884 // the merge in-place. The only case we cannot handle here is when the offset 00885 // into the existing node is less than the offset into the virtual node we are 00886 // merging in. In this case, we have to extend the existing node, which 00887 // requires an allocation anyway. 00888 DSNode *DN = NH.getNode(); // Make sure the Offset is up-to-date 00889 if (NH.getOffset() >= SrcNH.getOffset()) { 00890 if (!DN->isNodeCompletelyFolded()) { 00891 // Make sure the destination node is folded if the source node is folded. 00892 if (SN->isNodeCompletelyFolded()) { 00893 DN->foldNodeCompletely(); 00894 DN = NH.getNode(); 00895 } else if (SN->getSize() != DN->getSize()) { 00896 // If the two nodes are of different size, and the smaller node has the 00897 // array bit set, collapse! 00898 if (SN->getSize() < DN->getSize()) { 00899 if (SN->isArray()) { 00900 DN->foldNodeCompletely(); 00901 DN = NH.getNode(); 00902 } 00903 } else if (DN->isArray()) { 00904 DN->foldNodeCompletely(); 00905 DN = NH.getNode(); 00906 } 00907 } 00908 00909 // Merge the type entries of the two nodes together... 00910 if (SN->getType() != Type::VoidTy && !DN->isNodeCompletelyFolded()) { 00911 DN->mergeTypeInfo(SN->getType(), NH.getOffset()-SrcNH.getOffset()); 00912 DN = NH.getNode(); 00913 } 00914 } 00915 00916 assert(!DN->isDeadNode()); 00917 00918 // Merge the NodeType information. 00919 DN->mergeNodeFlags(SN->getNodeFlags() & BitsToKeep); 00920 00921 // Before we start merging outgoing links and updating the scalar map, make 00922 // sure it is known that this is the representative node for the src node. 00923 SCNH = DSNodeHandle(DN, NH.getOffset()-SrcNH.getOffset()); 00924 00925 // If the source node contains any globals, make sure they end up in the 00926 // scalar map with the correct offset. 00927 if (SN->global_begin() != SN->global_end()) { 00928 // Update the globals in the destination node itself. 00929 DN->mergeGlobals(SN->getGlobals()); 00930 00931 // Update the scalar map for the graph we are merging the source node 00932 // into. 00933 for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end(); 00934 I != E; ++I) { 00935 GlobalValue *GV = *I; 00936 const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV); 00937 DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()]; 00938 assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent"); 00939 Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(), 00940 DestGNH.getOffset()+SrcGNH.getOffset())); 00941 00942 if (CloneFlags & DSGraph::UpdateInlinedGlobals) 00943 Dest.getInlinedGlobals().insert(GV); 00944 } 00945 NH.getNode()->mergeGlobals(SN->getGlobals()); 00946 } 00947 } else { 00948 // We cannot handle this case without allocating a temporary node. Fall 00949 // back on being simple. 00950 DSNode *NewDN = new DSNode(*SN, &Dest, true /* Null out all links */); 00951 NewDN->maskNodeTypes(BitsToKeep); 00952 00953 unsigned NHOffset = NH.getOffset(); 00954 NH.mergeWith(DSNodeHandle(NewDN, SrcNH.getOffset())); 00955 00956 assert(NH.getNode() && 00957 (NH.getOffset() > NHOffset || 00958 (NH.getOffset() == 0 && NH.getNode()->isNodeCompletelyFolded())) && 00959 "Merging did not adjust the offset!"); 00960 00961 // Before we start merging outgoing links and updating the scalar map, make 00962 // sure it is known that this is the representative node for the src node. 00963 SCNH = DSNodeHandle(NH.getNode(), NH.getOffset()-SrcNH.getOffset()); 00964 00965 // If the source node contained any globals, make sure to create entries 00966 // in the scalar map for them! 00967 for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end(); 00968 I != E; ++I) { 00969 GlobalValue *GV = *I; 00970 const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV); 00971 DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()]; 00972 assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent"); 00973 assert(SrcGNH.getNode() == SN && "Global mapping inconsistent"); 00974 Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(), 00975 DestGNH.getOffset()+SrcGNH.getOffset())); 00976 00977 if (CloneFlags & DSGraph::UpdateInlinedGlobals) 00978 Dest.getInlinedGlobals().insert(GV); 00979 } 00980 } 00981 00982 00983 // Next, recursively merge all outgoing links as necessary. Note that 00984 // adding these links can cause the destination node to collapse itself at 00985 // any time, and the current node may be merged with arbitrary other nodes. 00986 // For this reason, we must always go through NH. 00987 DN = 0; 00988 for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) { 00989 const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift); 00990 if (!SrcEdge.isNull()) { 00991 // Compute the offset into the current node at which to 00992 // merge this link. In the common case, this is a linear 00993 // relation to the offset in the original node (with 00994 // wrapping), but if the current node gets collapsed due to 00995 // recursive merging, we must make sure to merge in all remaining 00996 // links at offset zero. 00997 DSNode *CN = SCNH.getNode(); 00998 unsigned MergeOffset = 00999 ((i << DS::PointerShift)+SCNH.getOffset()) % CN->getSize(); 01000 01001 DSNodeHandle Tmp = CN->getLink(MergeOffset); 01002 if (!Tmp.isNull()) { 01003 // Perform the recursive merging. Make sure to create a temporary NH, 01004 // because the Link can disappear in the process of recursive merging. 01005 merge(Tmp, SrcEdge); 01006 } else { 01007 Tmp.mergeWith(getClonedNH(SrcEdge)); 01008 // Merging this could cause all kinds of recursive things to happen, 01009 // culminating in the current node being eliminated. Since this is 01010 // possible, make sure to reaquire the link from 'CN'. 01011 01012 unsigned MergeOffset = 0; 01013 CN = SCNH.getNode(); 01014 MergeOffset = ((i << DS::PointerShift)+SCNH.getOffset()) %CN->getSize(); 01015 CN->getLink(MergeOffset).mergeWith(Tmp); 01016 } 01017 } 01018 } 01019 } 01020 01021 /// mergeCallSite - Merge the nodes reachable from the specified src call 01022 /// site into the nodes reachable from DestCS. 01023 void ReachabilityCloner::mergeCallSite(const DSCallSite &DestCS, 01024 const DSCallSite &SrcCS) { 01025 merge(DestCS.getRetVal(), SrcCS.getRetVal()); 01026 unsigned MinArgs = DestCS.getNumPtrArgs(); 01027 if (SrcCS.getNumPtrArgs() < MinArgs) MinArgs = SrcCS.getNumPtrArgs(); 01028 01029 for (unsigned a = 0; a != MinArgs; ++a) 01030 merge(DestCS.getPtrArg(a), SrcCS.getPtrArg(a)); 01031 } 01032 01033 01034 //===----------------------------------------------------------------------===// 01035 // DSCallSite Implementation 01036 //===----------------------------------------------------------------------===// 01037 01038 // Define here to avoid including iOther.h and BasicBlock.h in DSGraph.h 01039 Function &DSCallSite::getCaller() const { 01040 return *Site.getInstruction()->getParent()->getParent(); 01041 } 01042 01043 void DSCallSite::InitNH(DSNodeHandle &NH, const DSNodeHandle &Src, 01044 ReachabilityCloner &RC) { 01045 NH = RC.getClonedNH(Src); 01046 } 01047 01048 //===----------------------------------------------------------------------===// 01049 // DSGraph Implementation 01050 //===----------------------------------------------------------------------===// 01051 01052 /// getFunctionNames - Return a space separated list of the name of the 01053 /// functions in this graph (if any) 01054 std::string DSGraph::getFunctionNames() const { 01055 switch (getReturnNodes().size()) { 01056 case 0: return "Globals graph"; 01057 case 1: return getReturnNodes().begin()->first->getName(); 01058 default: 01059 std::string Return; 01060 for (DSGraph::ReturnNodesTy::const_iterator I = getReturnNodes().begin(); 01061 I != getReturnNodes().end(); ++I) 01062 Return += I->first->getName() + " "; 01063 Return.erase(Return.end()-1, Return.end()); // Remove last space character 01064 return Return; 01065 } 01066 } 01067 01068 01069 DSGraph::DSGraph(const DSGraph &G) : GlobalsGraph(0), TD(G.TD) { 01070 PrintAuxCalls = false; 01071 NodeMapTy NodeMap; 01072 cloneInto(G, ScalarMap, ReturnNodes, NodeMap); 01073 } 01074 01075 DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap) 01076 : GlobalsGraph(0), TD(G.TD) { 01077 PrintAuxCalls = false; 01078 cloneInto(G, ScalarMap, ReturnNodes, NodeMap); 01079 } 01080 01081 DSGraph::~DSGraph() { 01082 FunctionCalls.clear(); 01083 AuxFunctionCalls.clear(); 01084 InlinedGlobals.clear(); 01085 ScalarMap.clear(); 01086 ReturnNodes.clear(); 01087 01088 // Drop all intra-node references, so that assertions don't fail... 01089 for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) 01090 (*NI)->dropAllReferences(); 01091 01092 // Free all of the nodes. 01093 Nodes.clear(); 01094 } 01095 01096 // dump - Allow inspection of graph in a debugger. 01097 void DSGraph::dump() const { print(std::cerr); } 01098 01099 01100 /// remapLinks - Change all of the Links in the current node according to the 01101 /// specified mapping. 01102 /// 01103 void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) { 01104 for (unsigned i = 0, e = Links.size(); i != e; ++i) 01105 if (DSNode *N = Links[i].getNode()) { 01106 DSGraph::NodeMapTy::const_iterator ONMI = OldNodeMap.find(N); 01107 if (ONMI != OldNodeMap.end()) { 01108 DSNode *ONMIN = ONMI->second.getNode(); 01109 Links[i].setTo(ONMIN, Links[i].getOffset()+ONMI->second.getOffset()); 01110 } 01111 } 01112 } 01113 01114 /// updateFromGlobalGraph - This function rematerializes global nodes and 01115 /// nodes reachable from them from the globals graph into the current graph. 01116 /// It uses the vector InlinedGlobals to avoid cloning and merging globals that 01117 /// are already up-to-date in the current graph. In practice, in the TD pass, 01118 /// this is likely to be a large fraction of the live global nodes in each 01119 /// function (since most live nodes are likely to have been brought up-to-date 01120 /// in at _some_ caller or callee). 01121 /// 01122 void DSGraph::updateFromGlobalGraph() { 01123 TIME_REGION(X, "updateFromGlobalGraph"); 01124 ReachabilityCloner RC(*this, *GlobalsGraph, 0); 01125 01126 // Clone the non-up-to-date global nodes into this graph. 01127 for (DSScalarMap::global_iterator I = getScalarMap().global_begin(), 01128 E = getScalarMap().global_end(); I != E; ++I) 01129 if (InlinedGlobals.count(*I) == 0) { // GNode is not up-to-date 01130 DSScalarMap::iterator It = GlobalsGraph->ScalarMap.find(*I); 01131 if (It != GlobalsGraph->ScalarMap.end()) 01132 RC.merge(getNodeForValue(*I), It->second); 01133 } 01134 } 01135 01136 /// cloneInto - Clone the specified DSGraph into the current graph. The 01137 /// translated ScalarMap for the old function is filled into the OldValMap 01138 /// member, and the translated ReturnNodes map is returned into ReturnNodes. 01139 /// 01140 /// The CloneFlags member controls various aspects of the cloning process. 01141 /// 01142 void DSGraph::cloneInto(const DSGraph &G, DSScalarMap &OldValMap, 01143 ReturnNodesTy &OldReturnNodes, NodeMapTy &OldNodeMap, 01144 unsigned CloneFlags) { 01145 TIME_REGION(X, "cloneInto"); 01146 assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!"); 01147 assert(&G != this && "Cannot clone graph into itself!"); 01148 01149 // Remove alloca or mod/ref bits as specified... 01150 unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0) 01151 | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0) 01152 | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0); 01153 BitsToClear |= DSNode::DEAD; // Clear dead flag... 01154 01155 for (node_iterator I = G.node_begin(), E = G.node_end(); I != E; ++I) { 01156 assert(!(*I)->isForwarding() && 01157 "Forward nodes shouldn't be in node list!"); 01158 DSNode *New = new DSNode(**I, this); 01159 New->maskNodeTypes(~BitsToClear); 01160 OldNodeMap[*I] = New; 01161 } 01162 01163 #ifndef NDEBUG 01164 Timer::addPeakMemoryMeasurement(); 01165 #endif 01166 01167 // Rewrite the links in the new nodes to point into the current graph now. 01168 // Note that we don't loop over the node's list to do this. The problem is 01169 // that remaping links can cause recursive merging to happen, which means 01170 // that node_iterator's can get easily invalidated! Because of this, we 01171 // loop over the OldNodeMap, which contains all of the new nodes as the 01172 // .second element of the map elements. Also note that if we remap a node 01173 // more than once, we won't break anything. 01174 for (NodeMapTy::iterator I = OldNodeMap.begin(), E = OldNodeMap.end(); 01175 I != E; ++I) 01176 I->second.getNode()->remapLinks(OldNodeMap); 01177 01178 // Copy the scalar map... merging all of the global nodes... 01179 for (DSScalarMap::const_iterator I = G.ScalarMap.begin(), 01180 E = G.ScalarMap.end(); I != E; ++I) { 01181 DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()]; 01182 DSNodeHandle &H = OldValMap[I->first]; 01183 DSNode *MappedNodeN = MappedNode.getNode(); 01184 H.mergeWith(DSNodeHandle(MappedNodeN, 01185 I->second.getOffset()+MappedNode.getOffset())); 01186 01187 // If this is a global, add the global to this fn or merge if already exists 01188 if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) { 01189 ScalarMap[GV].mergeWith(H); 01190 if (CloneFlags & DSGraph::UpdateInlinedGlobals) 01191 InlinedGlobals.insert(GV); 01192 } 01193 } 01194 01195 if (!(CloneFlags & DontCloneCallNodes)) { 01196 // Copy the function calls list... 01197 unsigned FC = FunctionCalls.size(); // FirstCall 01198 FunctionCalls.reserve(FC+G.FunctionCalls.size()); 01199 for (unsigned i = 0, ei = G.FunctionCalls.size(); i != ei; ++i) 01200 FunctionCalls.push_back(DSCallSite(G.FunctionCalls[i], OldNodeMap)); 01201 } 01202 01203 if (!(CloneFlags & DontCloneAuxCallNodes)) { 01204 // Copy the auxiliary function calls list... 01205 unsigned FC = AuxFunctionCalls.size(); // FirstCall 01206 AuxFunctionCalls.reserve(FC+G.AuxFunctionCalls.size()); 01207 for (unsigned i = 0, ei = G.AuxFunctionCalls.size(); i != ei; ++i) 01208 AuxFunctionCalls.push_back(DSCallSite(G.AuxFunctionCalls[i], OldNodeMap)); 01209 } 01210 01211 // Map the return node pointers over... 01212 for (ReturnNodesTy::const_iterator I = G.getReturnNodes().begin(), 01213 E = G.getReturnNodes().end(); I != E; ++I) { 01214 const DSNodeHandle &Ret = I->second; 01215 DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()]; 01216 DSNode *MappedRetN = MappedRet.getNode(); 01217 OldReturnNodes.insert(std::make_pair(I->first, 01218 DSNodeHandle(MappedRetN, 01219 MappedRet.getOffset()+Ret.getOffset()))); 01220 } 01221 } 01222 01223 static bool PathExistsToClonedNode(const DSNode *N, ReachabilityCloner &RC) { 01224 if (N) 01225 for (df_iterator<const DSNode*> I = df_begin(N), E = df_end(N); I != E; ++I) 01226 if (RC.hasClonedNode(*I)) 01227 return true; 01228 return false; 01229 } 01230 01231 static bool PathExistsToClonedNode(const DSCallSite &CS, 01232 ReachabilityCloner &RC) { 01233 if (PathExistsToClonedNode(CS.getRetVal().getNode(), RC)) 01234 return true; 01235 for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) 01236 if (PathExistsToClonedNode(CS.getPtrArg(i).getNode(), RC)) 01237 return true; 01238 return false; 01239 } 01240 01241 /// mergeInGraph - The method is used for merging graphs together. If the 01242 /// argument graph is not *this, it makes a clone of the specified graph, then 01243 /// merges the nodes specified in the call site with the formal arguments in the 01244 /// graph. 01245 /// 01246 void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F, 01247 const DSGraph &Graph, unsigned CloneFlags) { 01248 TIME_REGION(X, "mergeInGraph"); 01249 01250 // Fastpath for a noop inline. 01251 if (CS.getNumPtrArgs() == 0 && CS.getRetVal().isNull()) 01252 return; 01253 01254 // If this is not a recursive call, clone the graph into this graph... 01255 if (&Graph != this) { 01256 // Clone the callee's graph into the current graph, keeping track of where 01257 // scalars in the old graph _used_ to point, and of the new nodes matching 01258 // nodes of the old graph. 01259 ReachabilityCloner RC(*this, Graph, CloneFlags); 01260 01261 // Set up argument bindings 01262 Function::aiterator AI = F.abegin(); 01263 for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) { 01264 // Advance the argument iterator to the first pointer argument... 01265 while (AI != F.aend() && !isPointerType(AI->getType())) { 01266 ++AI; 01267 #ifndef NDEBUG // FIXME: We should merge vararg arguments! 01268 if (AI == F.aend() && !F.getFunctionType()->isVarArg()) 01269 std::cerr << "Bad call to Function: " << F.getName() << "\n"; 01270 #endif 01271 } 01272 if (AI == F.aend()) break; 01273 01274 // Add the link from the argument scalar to the provided value. 01275 RC.merge(CS.getPtrArg(i), Graph.getNodeForValue(AI)); 01276 } 01277 01278 // Map the return node pointer over. 01279 if (!CS.getRetVal().isNull()) 01280 RC.merge(CS.getRetVal(), Graph.getReturnNodeFor(F)); 01281 01282 // If requested, copy all of the calls. 01283 if (!(CloneFlags & DontCloneCallNodes)) { 01284 // Copy the function calls list... 01285 FunctionCalls.reserve(FunctionCalls.size()+Graph.FunctionCalls.size()); 01286 for (unsigned i = 0, ei = Graph.FunctionCalls.size(); i != ei; ++i) 01287 FunctionCalls.push_back(DSCallSite(Graph.FunctionCalls[i], RC)); 01288 } 01289 01290 // If the user has us copying aux calls (the normal case), set up a data 01291 // structure to keep track of which ones we've copied over. 01292 std::vector<bool> CopiedAuxCall; 01293 if (!(CloneFlags & DontCloneAuxCallNodes)) { 01294 AuxFunctionCalls.reserve(AuxFunctionCalls.size()+ 01295 Graph.AuxFunctionCalls.size()); 01296 CopiedAuxCall.resize(Graph.AuxFunctionCalls.size()); 01297 } 01298 01299 // Clone over all globals that appear in the caller and callee graphs. 01300 hash_set<GlobalVariable*> NonCopiedGlobals; 01301 for (DSScalarMap::global_iterator GI = Graph.getScalarMap().global_begin(), 01302 E = Graph.getScalarMap().global_end(); GI != E; ++GI) 01303 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*GI)) 01304 if (ScalarMap.count(GV)) 01305 RC.merge(ScalarMap[GV], Graph.getNodeForValue(GV)); 01306 else 01307 NonCopiedGlobals.insert(GV); 01308 01309 // If the global does not appear in the callers graph we generally don't 01310 // want to copy the node. However, if there is a path from the node global 01311 // node to a node that we did copy in the graph, we *must* copy it to 01312 // maintain the connection information. Every time we decide to include a 01313 // new global, this might make other globals live, so we must iterate 01314 // unfortunately. 01315 bool MadeChange = true; 01316 while (MadeChange) { 01317 MadeChange = false; 01318 for (hash_set<GlobalVariable*>::iterator I = NonCopiedGlobals.begin(); 01319 I != NonCopiedGlobals.end();) { 01320 DSNode *GlobalNode = Graph.getNodeForValue(*I).getNode(); 01321 if (RC.hasClonedNode(GlobalNode)) { 01322 // Already cloned it, remove from set. 01323 NonCopiedGlobals.erase(I++); 01324 MadeChange = true; 01325 } else if (PathExistsToClonedNode(GlobalNode, RC)) { 01326 RC.getClonedNH(Graph.getNodeForValue(*I)); 01327 NonCopiedGlobals.erase(I++); 01328 MadeChange = true; 01329 } else { 01330 ++I; 01331 } 01332 } 01333 01334 // If requested, copy any aux calls that can reach copied nodes. 01335 if (!(CloneFlags & DontCloneAuxCallNodes)) { 01336 for (unsigned i = 0, ei = Graph.AuxFunctionCalls.size(); i != ei; ++i) 01337 if (!CopiedAuxCall[i] && 01338 PathExistsToClonedNode(Graph.AuxFunctionCalls[i], RC)) { 01339 AuxFunctionCalls.push_back(DSCallSite(Graph.AuxFunctionCalls[i], 01340 RC)); 01341 CopiedAuxCall[i] = true; 01342 MadeChange = true; 01343 } 01344 } 01345 } 01346 01347 } else { 01348 DSNodeHandle RetVal = getReturnNodeFor(F); 01349 01350 // Merge the return value with the return value of the context... 01351 RetVal.mergeWith(CS.getRetVal()); 01352 01353 // Resolve all of the function arguments... 01354 Function::aiterator AI = F.abegin(); 01355 01356 for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) { 01357 // Advance the argument iterator to the first pointer argument... 01358 while (AI != F.aend() && !isPointerType(AI->getType())) { 01359 ++AI; 01360 #ifndef NDEBUG // FIXME: We should merge varargs arguments!! 01361 if (AI == F.aend() && !F.getFunctionType()->isVarArg()) 01362 std::cerr << "Bad call to Function: " << F.getName() << "\n"; 01363 #endif 01364 } 01365 if (AI == F.aend()) break; 01366 01367 // Add the link from the argument scalar to the provided value 01368 DSNodeHandle &NH = getNodeForValue(AI); 01369 assert(!NH.isNull() && "Pointer argument without scalarmap entry?"); 01370 NH.mergeWith(CS.getPtrArg(i)); 01371 } 01372 } 01373 } 01374 01375 /// getCallSiteForArguments - Get the arguments and return value bindings for 01376 /// the specified function in the current graph. 01377 /// 01378 DSCallSite DSGraph::getCallSiteForArguments(Function &F) const { 01379 std::vector<DSNodeHandle> Args; 01380 01381 for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) 01382 if (isPointerType(I->getType())) 01383 Args.push_back(getNodeForValue(I)); 01384 01385 return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args); 01386 } 01387 01388 /// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in 01389 /// the context of this graph, return the DSCallSite for it. 01390 DSCallSite DSGraph::getDSCallSiteForCallSite(CallSite CS) const { 01391 DSNodeHandle RetVal; 01392 Instruction *I = CS.getInstruction(); 01393 if (isPointerType(I->getType())) 01394 RetVal = getNodeForValue(I); 01395 01396 std::vector<DSNodeHandle> Args; 01397 Args.reserve(CS.arg_end()-CS.arg_begin()); 01398 01399 // Calculate the arguments vector... 01400 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) 01401 if (isPointerType((*I)->getType())) 01402 Args.push_back(getNodeForValue(*I)); 01403 01404 // Add a new function call entry... 01405 if (Function *F = CS.getCalledFunction()) 01406 return DSCallSite(CS, RetVal, F, Args); 01407 else 01408 return DSCallSite(CS, RetVal, 01409 getNodeForValue(CS.getCalledValue()).getNode(), Args); 01410 } 01411 01412 01413 01414 // markIncompleteNodes - Mark the specified node as having contents that are not 01415 // known with the current analysis we have performed. Because a node makes all 01416 // of the nodes it can reach incomplete if the node itself is incomplete, we 01417 // must recursively traverse the data structure graph, marking all reachable 01418 // nodes as incomplete. 01419 // 01420 static void markIncompleteNode(DSNode *N) { 01421 // Stop recursion if no node, or if node already marked... 01422 if (N == 0 || N->isIncomplete()) return; 01423 01424 // Actually mark the node 01425 N->setIncompleteMarker(); 01426 01427 // Recursively process children... 01428 for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize) 01429 if (DSNode *DSN = N->getLink(i).getNode()) 01430 markIncompleteNode(DSN); 01431 } 01432 01433 static void markIncomplete(DSCallSite &Call) { 01434 // Then the return value is certainly incomplete! 01435 markIncompleteNode(Call.getRetVal().getNode()); 01436 01437 // All objects pointed to by function arguments are incomplete! 01438 for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i) 01439 markIncompleteNode(Call.getPtrArg(i).getNode()); 01440 } 01441 01442 // markIncompleteNodes - Traverse the graph, identifying nodes that may be 01443 // modified by other functions that have not been resolved yet. This marks 01444 // nodes that are reachable through three sources of "unknownness": 01445 // 01446 // Global Variables, Function Calls, and Incoming Arguments 01447 // 01448 // For any node that may have unknown components (because something outside the 01449 // scope of current analysis may have modified it), the 'Incomplete' flag is 01450 // added to the NodeType. 01451 // 01452 void DSGraph::markIncompleteNodes(unsigned Flags) { 01453 // Mark any incoming arguments as incomplete... 01454 if (Flags & DSGraph::MarkFormalArgs) 01455 for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end(); 01456 FI != E; ++FI) { 01457 Function &F = *FI->first; 01458 if (F.getName() != "main") 01459 for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) 01460 if (isPointerType(I->getType())) 01461 markIncompleteNode(getNodeForValue(I).getNode()); 01462 } 01463 01464 // Mark stuff passed into functions calls as being incomplete... 01465 if (!shouldPrintAuxCalls()) 01466 for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) 01467 markIncomplete(FunctionCalls[i]); 01468 else 01469 for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) 01470 markIncomplete(AuxFunctionCalls[i]); 01471 01472 01473 // Mark all global nodes as incomplete... 01474 if ((Flags & DSGraph::IgnoreGlobals) == 0) 01475 for (DSScalarMap::global_iterator I = ScalarMap.global_begin(), 01476 E = ScalarMap.global_end(); I != E; ++I) 01477 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I)) 01478 if (!GV->isConstant() || !GV->hasInitializer()) 01479 markIncompleteNode(ScalarMap[GV].getNode()); 01480 } 01481 01482 static inline void killIfUselessEdge(DSNodeHandle &Edge) { 01483 if (DSNode *N = Edge.getNode()) // Is there an edge? 01484 if (N->getNumReferrers() == 1) // Does it point to a lonely node? 01485 // No interesting info? 01486 if ((N->getNodeFlags() & ~DSNode::Incomplete) == 0 && 01487 N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded()) 01488 Edge.setTo(0, 0); // Kill the edge! 01489 } 01490 01491 static inline bool nodeContainsExternalFunction(const DSNode *N) { 01492 const std::vector<GlobalValue*> &Globals = N->getGlobals(); 01493 for (unsigned i = 0, e = Globals.size(); i != e; ++i) 01494 if (Globals[i]->isExternal() && isa<Function>(Globals[i])) 01495 return true; 01496 return false; 01497 } 01498 01499 static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) { 01500 // Remove trivially identical function calls 01501 unsigned NumFns = Calls.size(); 01502 std::sort(Calls.begin(), Calls.end()); // Sort by callee as primary key! 01503 01504 #if 1 01505 // Scan the call list cleaning it up as necessary... 01506 DSNode *LastCalleeNode = 0; 01507 Function *LastCalleeFunc = 0; 01508 unsigned NumDuplicateCalls = 0; 01509 bool LastCalleeContainsExternalFunction = false; 01510 01511 std::vector<unsigned> CallsToDelete; 01512 01513 for (unsigned i = 0; i != Calls.size(); ++i) { 01514 DSCallSite &CS = Calls[i]; 01515 01516 // If the Callee is a useless edge, this must be an unreachable call site, 01517 // eliminate it. 01518 if (CS.isIndirectCall() && CS.getCalleeNode()->getNumReferrers() == 1 && 01519 CS.getCalleeNode()->isComplete() && 01520 CS.getCalleeNode()->getGlobals().empty()) { // No useful info? 01521 #ifndef NDEBUG 01522 std::cerr << "WARNING: Useless call site found.\n"; 01523 #endif 01524 CallsToDelete.push_back(i); 01525 } else { 01526 // If the return value or any arguments point to a void node with no 01527 // information at all in it, and the call node is the only node to point 01528 // to it, remove the edge to the node (killing the node). 01529 // 01530 killIfUselessEdge(CS.getRetVal()); 01531 for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a) 01532 killIfUselessEdge(CS.getPtrArg(a)); 01533 01534 // If this call site calls the same function as the last call site, and if 01535 // the function pointer contains an external function, this node will 01536 // never be resolved. Merge the arguments of the call node because no 01537 // information will be lost. 01538 // 01539 if ((CS.isDirectCall() && CS.getCalleeFunc() == LastCalleeFunc) || 01540 (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) { 01541 ++NumDuplicateCalls; 01542 if (NumDuplicateCalls == 1) { 01543 if (LastCalleeNode) 01544 LastCalleeContainsExternalFunction = 01545 nodeContainsExternalFunction(LastCalleeNode); 01546 else 01547 LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal(); 01548 } 01549 01550 // It is not clear why, but enabling this code makes DSA really 01551 // sensitive to node forwarding. Basically, with this enabled, DSA 01552 // performs different number of inlinings based on which nodes are 01553 // forwarding or not. This is clearly a problem, so this code is 01554 // disabled until this can be resolved. 01555 #if 1 01556 if (LastCalleeContainsExternalFunction 01557 #if 0 01558 || 01559 // This should be more than enough context sensitivity! 01560 // FIXME: Evaluate how many times this is tripped! 01561 NumDuplicateCalls > 20 01562 #endif 01563 ) { 01564 DSCallSite &OCS = Calls[i-1]; 01565 OCS.mergeWith(CS); 01566 01567 // No need to keep this call anymore. 01568 CallsToDelete.push_back(i); 01569 } 01570 #endif 01571 } else { 01572 if (CS.isDirectCall()) { 01573 LastCalleeFunc = CS.getCalleeFunc(); 01574 LastCalleeNode = 0; 01575 } else { 01576 LastCalleeNode = CS.getCalleeNode(); 01577 LastCalleeFunc = 0; 01578 } 01579 NumDuplicateCalls = 0; 01580 } 01581 } 01582 } 01583 #endif 01584 01585 unsigned NumDeleted = 0; 01586 for (unsigned i = 0, e = CallsToDelete.size(); i != e; ++i) 01587 Calls.erase(Calls.begin()+CallsToDelete[i]-NumDeleted++); 01588 01589 Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end()); 01590 01591 // Track the number of call nodes merged away... 01592 NumCallNodesMerged += NumFns-Calls.size(); 01593 01594 DEBUG(if (NumFns != Calls.size()) 01595 std::cerr << "Merged " << (NumFns-Calls.size()) << " call nodes.\n";); 01596 } 01597 01598 01599 // removeTriviallyDeadNodes - After the graph has been constructed, this method 01600 // removes all unreachable nodes that are created because they got merged with 01601 // other nodes in the graph. These nodes will all be trivially unreachable, so 01602 // we don't have to perform any non-trivial analysis here. 01603 // 01604 void DSGraph::removeTriviallyDeadNodes() { 01605 TIME_REGION(X, "removeTriviallyDeadNodes"); 01606 01607 #if 0 01608 /// NOTE: This code is disabled. This slows down DSA on 177.mesa 01609 /// substantially! 01610 01611 // Loop over all of the nodes in the graph, calling getNode on each field. 01612 // This will cause all nodes to update their forwarding edges, causing 01613 // forwarded nodes to be delete-able. 01614 { TIME_REGION(X, "removeTriviallyDeadNodes:node_iterate"); 01615 for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) { 01616 DSNode *N = *NI; 01617 for (unsigned l = 0, e = N->getNumLinks(); l != e; ++l) 01618 N->getLink(l*N->getPointerSize()).getNode(); 01619 } 01620 } 01621 01622 // NOTE: This code is disabled. Though it should, in theory, allow us to 01623 // remove more nodes down below, the scan of the scalar map is incredibly 01624 // expensive for certain programs (with large SCCs). In the future, if we can 01625 // make the scalar map scan more efficient, then we can reenable this. 01626 { TIME_REGION(X, "removeTriviallyDeadNodes:scalarmap"); 01627 01628 // Likewise, forward any edges from the scalar nodes. While we are at it, 01629 // clean house a bit. 01630 for (DSScalarMap::iterator I = ScalarMap.begin(),E = ScalarMap.end();I != E;){ 01631 I->second.getNode(); 01632 ++I; 01633 } 01634 } 01635 #endif 01636 bool isGlobalsGraph = !GlobalsGraph; 01637 01638 for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E; ) { 01639 DSNode &Node = *NI; 01640 01641 // Do not remove *any* global nodes in the globals graph. 01642 // This is a special case because such nodes may not have I, M, R flags set. 01643 if (Node.isGlobalNode() && isGlobalsGraph) { 01644 ++NI; 01645 continue; 01646 } 01647 01648 if (Node.isComplete() && !Node.isModified() && !Node.isRead()) { 01649 // This is a useless node if it has no mod/ref info (checked above), 01650 // outgoing edges (which it cannot, as it is not modified in this 01651 // context), and it has no incoming edges. If it is a global node it may 01652 // have all of these properties and still have incoming edges, due to the 01653 // scalar map, so we check those now. 01654 // 01655 if (Node.getNumReferrers() == Node.getGlobals().size()) { 01656 const std::vector<GlobalValue*> &Globals = Node.getGlobals(); 01657 01658 // Loop through and make sure all of the globals are referring directly 01659 // to the node... 01660 for (unsigned j = 0, e = Globals.size(); j != e; ++j) { 01661 DSNode *N = getNodeForValue(Globals[j]).getNode(); 01662 assert(N == &Node && "ScalarMap doesn't match globals list!"); 01663 } 01664 01665 // Make sure NumReferrers still agrees, if so, the node is truly dead. 01666 if (Node.getNumReferrers() == Globals.size()) { 01667 for (unsigned j = 0, e = Globals.size(); j != e; ++j) 01668 ScalarMap.erase(Globals[j]); 01669 Node.makeNodeDead(); 01670 ++NumTrivialGlobalDNE; 01671 } 01672 } 01673 } 01674 01675 if (Node.getNodeFlags() == 0 && Node.hasNoReferrers()) { 01676 // This node is dead! 01677 NI = Nodes.erase(NI); // Erase & remove from node list. 01678 ++NumTrivialDNE; 01679 } else { 01680 ++NI; 01681 } 01682 } 01683 01684 removeIdenticalCalls(FunctionCalls); 01685 removeIdenticalCalls(AuxFunctionCalls); 01686 } 01687 01688 01689 /// markReachableNodes - This method recursively traverses the specified 01690 /// DSNodes, marking any nodes which are reachable. All reachable nodes it adds 01691 /// to the set, which allows it to only traverse visited nodes once. 01692 /// 01693 void DSNode::markReachableNodes(hash_set<DSNode*> &ReachableNodes) { 01694 if (this == 0) return; 01695 assert(getForwardNode() == 0 && "Cannot mark a forwarded node!"); 01696 if (ReachableNodes.insert(this).second) // Is newly reachable? 01697 for (unsigned i = 0, e = getSize(); i < e; i += DS::PointerSize) 01698 getLink(i).getNode()->markReachableNodes(ReachableNodes); 01699 } 01700 01701 void DSCallSite::markReachableNodes(hash_set<DSNode*> &Nodes) { 01702 getRetVal().getNode()->markReachableNodes(Nodes); 01703 if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes); 01704 01705 for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i) 01706 getPtrArg(i).getNode()->markReachableNodes(Nodes); 01707 } 01708 01709 // CanReachAliveNodes - Simple graph walker that recursively traverses the graph 01710 // looking for a node that is marked alive. If an alive node is found, return 01711 // true, otherwise return false. If an alive node is reachable, this node is 01712 // marked as alive... 01713 // 01714 static bool CanReachAliveNodes(DSNode *N, hash_set<DSNode*> &Alive, 01715 hash_set<DSNode*> &Visited, 01716 bool IgnoreGlobals) { 01717 if (N == 0) return false; 01718 assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!"); 01719 01720 // If this is a global node, it will end up in the globals graph anyway, so we 01721 // don't need to worry about it. 01722 if (IgnoreGlobals && N->isGlobalNode()) return false; 01723 01724 // If we know that this node is alive, return so! 01725 if (Alive.count(N)) return true; 01726 01727 // Otherwise, we don't think the node is alive yet, check for infinite 01728 // recursion. 01729 if (Visited.count(N)) return false; // Found a cycle 01730 Visited.insert(N); // No recursion, insert into Visited... 01731 01732 for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize) 01733 if (CanReachAliveNodes(N->getLink(i).getNode(), Alive, Visited, 01734 IgnoreGlobals)) { 01735 N->markReachableNodes(Alive); 01736 return true; 01737 } 01738 return false; 01739 } 01740 01741 // CallSiteUsesAliveArgs - Return true if the specified call site can reach any 01742 // alive nodes. 01743 // 01744 static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set<DSNode*> &Alive, 01745 hash_set<DSNode*> &Visited, 01746 bool IgnoreGlobals) { 01747 if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited, 01748 IgnoreGlobals)) 01749 return true; 01750 if (CS.isIndirectCall() && 01751 CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited, IgnoreGlobals)) 01752 return true; 01753 for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) 01754 if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited, 01755 IgnoreGlobals)) 01756 return true; 01757 return false; 01758 } 01759 01760 // removeDeadNodes - Use a more powerful reachability analysis to eliminate 01761 // subgraphs that are unreachable. This often occurs because the data 01762 // structure doesn't "escape" into it's caller, and thus should be eliminated 01763 // from the caller's graph entirely. This is only appropriate to use when 01764 // inlining graphs. 01765 // 01766 void DSGraph::removeDeadNodes(unsigned Flags) { 01767 DEBUG(AssertGraphOK(); if (GlobalsGraph) GlobalsGraph->AssertGraphOK()); 01768 01769 // Reduce the amount of work we have to do... remove dummy nodes left over by 01770 // merging... 01771 removeTriviallyDeadNodes(); 01772 01773 TIME_REGION(X, "removeDeadNodes"); 01774 01775 // FIXME: Merge non-trivially identical call nodes... 01776 01777 // Alive - a set that holds all nodes found to be reachable/alive. 01778 hash_set<DSNode*> Alive; 01779 std::vector<std::pair<Value*, DSNode*> > GlobalNodes; 01780 01781 // Copy and merge all information about globals to the GlobalsGraph if this is 01782 // not a final pass (where unreachable globals are removed). 01783 // 01784 // Strip all alloca bits since the current function is only for the BU pass. 01785 // Strip all incomplete bits since they are short-lived properties and they 01786 // will be correctly computed when rematerializing nodes into the functions. 01787 // 01788 ReachabilityCloner GGCloner(*GlobalsGraph, *this, DSGraph::StripAllocaBit | 01789 DSGraph::StripIncompleteBit); 01790 01791 // Mark all nodes reachable by (non-global) scalar nodes as alive... 01792 { TIME_REGION(Y, "removeDeadNodes:scalarscan"); 01793 for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end(); I !=E;) 01794 if (isa<GlobalValue>(I->first)) { // Keep track of global nodes 01795 assert(!I->second.isNull() && "Null global node?"); 01796 assert(I->second.getNode()->isGlobalNode() && "Should be a global node!"); 01797 GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode())); 01798 01799 // Make sure that all globals are cloned over as roots. 01800 if (!(Flags & DSGraph::RemoveUnreachableGlobals)) { 01801 DSGraph::ScalarMapTy::iterator SMI = 01802 GlobalsGraph->getScalarMap().find(I->first); 01803 if (SMI != GlobalsGraph->getScalarMap().end()) 01804 GGCloner.merge(SMI->second, I->second); 01805 else 01806 GGCloner.getClonedNH(I->second); 01807 } 01808 ++I; 01809 } else { 01810 DSNode *N = I->second.getNode(); 01811 #if 0 01812 // Check to see if this is a worthless node generated for non-pointer 01813 // values, such as integers. Consider an addition of long types: A+B. 01814 // Assuming we can track all uses of the value in this context, and it is 01815 // NOT used as a pointer, we can delete the node. We will be able to 01816 // detect this situation if the node pointed to ONLY has Unknown bit set 01817 // in the node. In this case, the node is not incomplete, does not point 01818 // to any other nodes (no mod/ref bits set), and is therefore 01819 // uninteresting for data structure analysis. If we run across one of 01820 // these, prune the scalar pointing to it. 01821 // 01822 if (N->getNodeFlags() == DSNode::UnknownNode && !isa<Argument>(I->first)) 01823 ScalarMap.erase(I++); 01824 else { 01825 #endif 01826 N->markReachableNodes(Alive); 01827 ++I; 01828 //} 01829 } 01830 } 01831 01832 // The return values are alive as well. 01833 for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end(); 01834 I != E; ++I) 01835 I->second.getNode()->markReachableNodes(Alive); 01836 01837 // Mark any nodes reachable by primary calls as alive... 01838 for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) 01839 FunctionCalls[i].markReachableNodes(Alive); 01840 01841 01842 // Now find globals and aux call nodes that are already live or reach a live 01843 // value (which makes them live in turn), and continue till no more are found. 01844 // 01845 bool Iterate; 01846 hash_set<DSNode*> Visited; 01847 std::vector<unsigned char> AuxFCallsAlive(AuxFunctionCalls.size()); 01848 do { 01849 Visited.clear(); 01850 // If any global node points to a non-global that is "alive", the global is 01851 // "alive" as well... Remove it from the GlobalNodes list so we only have 01852 // unreachable globals in the list. 01853 // 01854 Iterate = false; 01855 if (!(Flags & DSGraph::RemoveUnreachableGlobals)) 01856 for (unsigned i = 0; i != GlobalNodes.size(); ++i) 01857 if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited, 01858 Flags & DSGraph::RemoveUnreachableGlobals)) { 01859 std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to... 01860 GlobalNodes.pop_back(); // erase efficiently 01861 Iterate = true; 01862 } 01863 01864 // Mark only unresolvable call nodes for moving to the GlobalsGraph since 01865 // call nodes that get resolved will be difficult to remove from that graph. 01866 // The final unresolved call nodes must be handled specially at the end of 01867 // the BU pass (i.e., in main or other roots of the call graph). 01868 for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) 01869 if (!AuxFCallsAlive[i] && 01870 (AuxFunctionCalls[i].isIndirectCall() 01871 || CallSiteUsesAliveArgs(AuxFunctionCalls[i], Alive, Visited, 01872 Flags & DSGraph::RemoveUnreachableGlobals))) { 01873 AuxFunctionCalls[i].markReachableNodes(Alive); 01874 AuxFCallsAlive[i] = true; 01875 Iterate = true; 01876 } 01877 } while (Iterate); 01878 01879 // Move dead aux function calls to the end of the list 01880 unsigned CurIdx = 0; 01881 for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) 01882 if (AuxFCallsAlive[i]) 01883 AuxFunctionCalls[CurIdx++].swap(AuxFunctionCalls[i]); 01884 01885 // Copy and merge all global nodes and dead aux call nodes into the 01886 // GlobalsGraph, and all nodes reachable from those nodes 01887 // 01888 if (!(Flags & DSGraph::RemoveUnreachableGlobals)) { 01889 // Copy the unreachable call nodes to the globals graph, updating their 01890 // target pointers using the GGCloner 01891 for (unsigned i = CurIdx, e = AuxFunctionCalls.size(); i != e; ++i) 01892 GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(AuxFunctionCalls[i], 01893 GGCloner)); 01894 } 01895 // Crop all the useless ones out... 01896 AuxFunctionCalls.erase(AuxFunctionCalls.begin()+CurIdx, 01897 AuxFunctionCalls.end()); 01898 01899 // We are finally done with the GGCloner so we can destroy it. 01900 GGCloner.destroy(); 01901 01902 // At this point, any nodes which are visited, but not alive, are nodes 01903 // which can be removed. Loop over all nodes, eliminating completely 01904 // unreachable nodes. 01905 // 01906 std::vector<DSNode*> DeadNodes; 01907 DeadNodes.reserve(Nodes.size()); 01908 for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E;) { 01909 DSNode *N = NI++; 01910 assert(!N->isForwarding() && "Forwarded node in nodes list?"); 01911 01912 if (!Alive.count(N)) { 01913 Nodes.remove(N); 01914 assert(!N->isForwarding() && "Cannot remove a forwarding node!"); 01915 DeadNodes.push_back(N); 01916 N->dropAllReferences(); 01917 ++NumDNE; 01918 } 01919 } 01920 01921 // Remove all unreachable globals from the ScalarMap. 01922 // If flag RemoveUnreachableGlobals is set, GlobalNodes has only dead nodes. 01923 // In either case, the dead nodes will not be in the set Alive. 01924 for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) 01925 if (!Alive.count(GlobalNodes[i].second)) 01926 ScalarMap.erase(GlobalNodes[i].first); 01927 else 01928 assert((Flags & DSGraph::RemoveUnreachableGlobals) && "non-dead global"); 01929 01930 // Delete all dead nodes now since their referrer counts are zero. 01931 for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i) 01932 delete DeadNodes[i]; 01933 01934 DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK()); 01935 } 01936 01937 void DSGraph::AssertCallSiteInGraph(const DSCallSite &CS) const { 01938 if (CS.isIndirectCall()) { 01939 AssertNodeInGraph(CS.getCalleeNode()); 01940 #if 0 01941 if (CS.getNumPtrArgs() && CS.getCalleeNode() == CS.getPtrArg(0).getNode() && 01942 CS.getCalleeNode() && CS.getCalleeNode()->getGlobals().empty()) 01943 std::cerr << "WARNING: WIERD CALL SITE FOUND!\n"; 01944 #endif 01945 } 01946 AssertNodeInGraph(CS.getRetVal().getNode()); 01947 for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j) 01948 AssertNodeInGraph(CS.getPtrArg(j).getNode()); 01949 } 01950 01951 void DSGraph::AssertCallNodesInGraph() const { 01952 for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) 01953 AssertCallSiteInGraph(FunctionCalls[i]); 01954 } 01955 void DSGraph::AssertAuxCallNodesInGraph() const { 01956 for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) 01957 AssertCallSiteInGraph(AuxFunctionCalls[i]); 01958 } 01959 01960 void DSGraph::AssertGraphOK() const { 01961 for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) 01962 (*NI)->assertOK(); 01963 01964 for (ScalarMapTy::const_iterator I = ScalarMap.begin(), 01965 E = ScalarMap.end(); I != E; ++I) { 01966 assert(!I->second.isNull() && "Null node in scalarmap!"); 01967 AssertNodeInGraph(I->second.getNode()); 01968 if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) { 01969 assert(I->second.getNode()->isGlobalNode() && 01970 "Global points to node, but node isn't global?"); 01971 AssertNodeContainsGlobal(I->second.getNode(), GV); 01972 } 01973 } 01974 AssertCallNodesInGraph(); 01975 AssertAuxCallNodesInGraph(); 01976 01977 // Check that all pointer arguments to any functions in this graph have 01978 // destinations. 01979 for (ReturnNodesTy::const_iterator RI = ReturnNodes.begin(), 01980 E = ReturnNodes.end(); 01981 RI != E; ++RI) { 01982 Function &F = *RI->first; 01983 for (Function::aiterator AI = F.abegin(); AI != F.aend(); ++AI) 01984 if (isPointerType(AI->getType())) 01985 assert(!getNodeForValue(AI).isNull() && 01986 "Pointer argument must be in the scalar map!"); 01987 } 01988 } 01989 01990 /// computeNodeMapping - Given roots in two different DSGraphs, traverse the 01991 /// nodes reachable from the two graphs, computing the mapping of nodes from the 01992 /// first to the second graph. This mapping may be many-to-one (i.e. the first 01993 /// graph may have multiple nodes representing one node in the second graph), 01994 /// but it will not work if there is a one-to-many or many-to-many mapping. 01995 /// 01996 void DSGraph::computeNodeMapping(const DSNodeHandle &NH1, 01997 const DSNodeHandle &NH2, NodeMapTy &NodeMap, 01998 bool StrictChecking) { 01999 DSNode *N1 = NH1.getNode(), *N2 = NH2.getNode(); 02000 if (N1 == 0 || N2 == 0) return; 02001 02002 DSNodeHandle &Entry = NodeMap[N1]; 02003 if (!Entry.isNull()) { 02004 // Termination of recursion! 02005 if (StrictChecking) { 02006 assert(Entry.getNode() == N2 && "Inconsistent mapping detected!"); 02007 assert((Entry.getOffset() == (NH2.getOffset()-NH1.getOffset()) || 02008 Entry.getNode()->isNodeCompletelyFolded()) && 02009 "Inconsistent mapping detected!"); 02010 } 02011 return; 02012 } 02013 02014 Entry.setTo(N2, NH2.getOffset()-NH1.getOffset()); 02015 02016 // Loop over all of the fields that N1 and N2 have in common, recursively 02017 // mapping the edges together now. 02018 int N2Idx = NH2.getOffset()-NH1.getOffset(); 02019 unsigned N2Size = N2->getSize(); 02020 for (unsigned i = 0, e = N1->getSize(); i < e; i += DS::PointerSize) 02021 if (unsigned(N2Idx)+i < N2Size) 02022 computeNodeMapping(N1->getLink(i), N2->getLink(N2Idx+i), NodeMap); 02023 else 02024 computeNodeMapping(N1->getLink(i), 02025 N2->getLink(unsigned(N2Idx+i) % N2Size), NodeMap); 02026 }