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