lib/Analysis/DataStructure/DataStructure.cpp

   1 //===- DataStructure.cpp - Implement the core data structure analysis -----===//
   2 //
   3 // This file implements the core data structure functionality.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/Analysis/DSGraph.h"
   8 #include "llvm/Function.h"
   9 #include "llvm/iOther.h"
  10 #include "llvm/DerivedTypes.h"
  11 #include "llvm/Target/TargetData.h"
  12 #include "Support/STLExtras.h"
  13 #include "Support/Statistic.h"
  14 #include "Support/Timer.h"
  15 #include <algorithm>
  16
  17 namespace {
  18   Statistic<> NumFolds          ("dsnode", "Number of nodes completely folded");
  19   Statistic<> NumCallNodesMerged("dsnode", "Number of call nodes merged");
  20 };
  21
  22 namespace DS {   // TODO: FIXME
  23   extern TargetData TD;
  24 }
  25 using namespace DS;
  26
  27 DSNode *DSNodeHandle::HandleForwarding() const {
  28   assert(!N->ForwardNH.isNull() && "Can only be invoked if forwarding!");
  29
  30   // Handle node forwarding here!
  31   DSNode *Next = N->ForwardNH.getNode();  // Cause recursive shrinkage
  32   Offset += N->ForwardNH.getOffset();
  33
  34   if (--N->NumReferrers == 0) {
  35     // Removing the last referrer to the node, sever the forwarding link
  36     N->stopForwarding();
  37   }
  38
  39   N = Next;
  40   N->NumReferrers++;
  41   if (N->Size <= Offset) {
  42     assert(N->Size <= 1 && "Forwarded to shrunk but not collapsed node?");
  43     Offset = 0;
  44   }
  45   return N;
  46 }
  47
  48 //===----------------------------------------------------------------------===//
  49 // DSNode Implementation
  50 //===----------------------------------------------------------------------===//
  51
  52 DSNode::DSNode(const Type *T, DSGraph *G)
  53   : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(0) {
  54   // Add the type entry if it is specified...
  55   if (T) mergeTypeInfo(T, 0);
  56   G->getNodes().push_back(this);
  57 }
  58
  59 // DSNode copy constructor... do not copy over the referrers list!
  60 DSNode::DSNode(const DSNode &N, DSGraph *G)
  61   : NumReferrers(0), Size(N.Size), ParentGraph(G), Ty(N.Ty),
  62     Links(N.Links), Globals(N.Globals), NodeType(N.NodeType) {
  63   G->getNodes().push_back(this);
  64 }
  65
  66 void DSNode::assertOK() const {
  67   assert((Ty != Type::VoidTy ||
  68           Ty == Type::VoidTy && (Size == 0 ||
  69                                  (NodeType & DSNode::Array))) &&
  70          "Node not OK!");
  71 }
  72
  73 /// forwardNode - Mark this node as being obsolete, and all references to it
  74 /// should be forwarded to the specified node and offset.
  75 ///
  76 void DSNode::forwardNode(DSNode *To, unsigned Offset) {
  77   assert(this != To && "Cannot forward a node to itself!");
  78   assert(ForwardNH.isNull() && "Already forwarding from this node!");
  79   if (To->Size <= 1) Offset = 0;
  80   assert((Offset < To->Size || (Offset == To->Size && Offset == 0)) &&
  81          "Forwarded offset is wrong!");
  82   ForwardNH.setNode(To);
  83   ForwardNH.setOffset(Offset);
  84   NodeType = DEAD;
  85   Size = 0;
  86   Ty = Type::VoidTy;
  87 }
  88
  89 // addGlobal - Add an entry for a global value to the Globals list.  This also
  90 // marks the node with the 'G' flag if it does not already have it.
  91 //
  92 void DSNode::addGlobal(GlobalValue *GV) {
  93   // Keep the list sorted.
  94   std::vector<GlobalValue*>::iterator I =
  95     std::lower_bound(Globals.begin(), Globals.end(), GV);
  96
  97   if (I == Globals.end() || *I != GV) {
  98     //assert(GV->getType()->getElementType() == Ty);
  99     Globals.insert(I, GV);
 100     NodeType |= GlobalNode;
 101   }
 102 }
 103
 104 /// foldNodeCompletely - If we determine that this node has some funny
 105 /// behavior happening to it that we cannot represent, we fold it down to a
 106 /// single, completely pessimistic, node.  This node is represented as a
 107 /// single byte with a single TypeEntry of "void".
 108 ///
 109 void DSNode::foldNodeCompletely() {
 110   if (isNodeCompletelyFolded()) return;  // If this node is already folded...
 111
 112   ++NumFolds;
 113
 114   // Create the node we are going to forward to...
 115   DSNode *DestNode = new DSNode(0, ParentGraph);
 116   DestNode->NodeType = NodeType|DSNode::Array;
 117   DestNode->Ty = Type::VoidTy;
 118   DestNode->Size = 1;
 119   DestNode->Globals.swap(Globals);
 120
 121   // Start forwarding to the destination node...
 122   forwardNode(DestNode, 0);
 123
 124   if (Links.size()) {
 125     DestNode->Links.push_back(Links[0]);
 126     DSNodeHandle NH(DestNode);
 127
 128     // If we have links, merge all of our outgoing links together...
 129     for (unsigned i = Links.size()-1; i != 0; --i)
 130       NH.getNode()->Links[0].mergeWith(Links[i]);
 131     Links.clear();
 132   } else {
 133     DestNode->Links.resize(1);
 134   }
 135 }
 136
 137 /// isNodeCompletelyFolded - Return true if this node has been completely
 138 /// folded down to something that can never be expanded, effectively losing
 139 /// all of the field sensitivity that may be present in the node.
 140 ///
 141 bool DSNode::isNodeCompletelyFolded() const {
 142   return getSize() == 1 && Ty == Type::VoidTy && isArray();
 143 }
 144
 145
 146 namespace {
 147   /// TypeElementWalker Class - Used for implementation of physical subtyping...
 148   ///
 149   class TypeElementWalker {
 150     struct StackState {
 151       const Type *Ty;
 152       unsigned Offset;
 153       unsigned Idx;
 154       StackState(const Type *T, unsigned Off = 0)
 155         : Ty(T), Offset(Off), Idx(0) {}
 156     };
 157
 158     std::vector<StackState> Stack;
 159   public:
 160     TypeElementWalker(const Type *T) {
 161       Stack.push_back(T);
 162       StepToLeaf();
 163     }
 164
 165     bool isDone() const { return Stack.empty(); }
 166     const Type *getCurrentType()   const { return Stack.back().Ty;     }
 167     unsigned    getCurrentOffset() const { return Stack.back().Offset; }
 168
 169     void StepToNextType() {
 170       PopStackAndAdvance();
 171       StepToLeaf();
 172     }
 173
 174   private:
 175     /// PopStackAndAdvance - Pop the current element off of the stack and
 176     /// advance the underlying element to the next contained member.
 177     void PopStackAndAdvance() {
 178       assert(!Stack.empty() && "Cannot pop an empty stack!");
 179       Stack.pop_back();
 180       while (!Stack.empty()) {
 181         StackState &SS = Stack.back();
 182         if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) {
 183           ++SS.Idx;
 184           if (SS.Idx != ST->getElementTypes().size()) {
 185             const StructLayout *SL = TD.getStructLayout(ST);
 186             SS.Offset += SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1];
 187             return;
 188           }
 189           Stack.pop_back();  // At the end of the structure
 190         } else {
 191           const ArrayType *AT = cast<ArrayType>(SS.Ty);
 192           ++SS.Idx;
 193           if (SS.Idx != AT->getNumElements()) {
 194             SS.Offset += TD.getTypeSize(AT->getElementType());
 195             return;
 196           }
 197           Stack.pop_back();  // At the end of the array
 198         }
 199       }
 200     }
 201
 202     /// StepToLeaf - Used by physical subtyping to move to the first leaf node
 203     /// on the type stack.
 204     void StepToLeaf() {
 205       if (Stack.empty()) return;
 206       while (!Stack.empty() && !Stack.back().Ty->isFirstClassType()) {
 207         StackState &SS = Stack.back();
 208         if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) {
 209           if (ST->getElementTypes().empty()) {
 210             assert(SS.Idx == 0);
 211             PopStackAndAdvance();
 212           } else {
 213             // Step into the structure...
 214             assert(SS.Idx < ST->getElementTypes().size());
 215             const StructLayout *SL = TD.getStructLayout(ST);
 216             Stack.push_back(StackState(ST->getElementTypes()[SS.Idx],
 217                                        SS.Offset+SL->MemberOffsets[SS.Idx]));
 218           }
 219         } else {
 220           const ArrayType *AT = cast<ArrayType>(SS.Ty);
 221           if (AT->getNumElements() == 0) {
 222             assert(SS.Idx == 0);
 223             PopStackAndAdvance();
 224           } else {
 225             // Step into the array...
 226             assert(SS.Idx < AT->getNumElements());
 227             Stack.push_back(StackState(AT->getElementType(),
 228                                        SS.Offset+SS.Idx*
 229                                        TD.getTypeSize(AT->getElementType())));
 230           }
 231         }
 232       }
 233     }
 234   };
 235 }
 236
 237 /// ElementTypesAreCompatible - Check to see if the specified types are
 238 /// "physically" compatible.  If so, return true, else return false.  We only
 239 /// have to check the fields in T1: T2 may be larger than T1.
 240 ///
 241 static bool ElementTypesAreCompatible(const Type *T1, const Type *T2) {
 242   TypeElementWalker T1W(T1), T2W(T2);
 243
 244   while (!T1W.isDone() && !T2W.isDone()) {
 245     if (T1W.getCurrentOffset() != T2W.getCurrentOffset())
 246       return false;
 247
 248     const Type *T1 = T1W.getCurrentType();
 249     const Type *T2 = T2W.getCurrentType();
 250     if (T1 != T2 && !T1->isLosslesslyConvertibleTo(T2))
 251       return false;
 252
 253     T1W.StepToNextType();
 254     T2W.StepToNextType();
 255   }
 256
 257   return T1W.isDone();
 258 }
 259
 260
 261 /// mergeTypeInfo - This method merges the specified type into the current node
 262 /// at the specified offset.  This may update the current node's type record if
 263 /// this gives more information to the node, it may do nothing to the node if
 264 /// this information is already known, or it may merge the node completely (and
 265 /// return true) if the information is incompatible with what is already known.
 266 ///
 267 /// This method returns true if the node is completely folded, otherwise false.
 268 ///
 269 bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset,
 270                            bool FoldIfIncompatible) {
 271   // Check to make sure the Size member is up-to-date.  Size can be one of the
 272   // following:
 273   //  Size = 0, Ty = Void: Nothing is known about this node.
 274   //  Size = 0, Ty = FnTy: FunctionPtr doesn't have a size, so we use zero
 275   //  Size = 1, Ty = Void, Array = 1: The node is collapsed
 276   //  Otherwise, sizeof(Ty) = Size
 277   //
 278   assert(((Size == 0 && Ty == Type::VoidTy && !isArray()) ||
 279           (Size == 0 && !Ty->isSized() && !isArray()) ||
 280           (Size == 1 && Ty == Type::VoidTy && isArray()) ||
 281           (Size == 0 && !Ty->isSized() && !isArray()) ||
 282           (TD.getTypeSize(Ty) == Size)) &&
 283          "Size member of DSNode doesn't match the type structure!");
 284   assert(NewTy != Type::VoidTy && "Cannot merge void type into DSNode!");
 285
 286   if (Offset == 0 && NewTy == Ty)
 287     return false;  // This should be a common case, handle it efficiently
 288
 289   // Return true immediately if the node is completely folded.
 290   if (isNodeCompletelyFolded()) return true;
 291
 292   // If this is an array type, eliminate the outside arrays because they won't
 293   // be used anyway.  This greatly reduces the size of large static arrays used
 294   // as global variables, for example.
 295   //
 296   bool WillBeArray = false;
 297   while (const ArrayType *AT = dyn_cast<ArrayType>(NewTy)) {
 298     // FIXME: we might want to keep small arrays, but must be careful about
 299     // things like: [2 x [10000 x int*]]
 300     NewTy = AT->getElementType();
 301     WillBeArray = true;
 302   }
 303
 304   // Figure out how big the new type we're merging in is...
 305   unsigned NewTySize = NewTy->isSized() ? TD.getTypeSize(NewTy) : 0;
 306
 307   // Otherwise check to see if we can fold this type into the current node.  If
 308   // we can't, we fold the node completely, if we can, we potentially update our
 309   // internal state.
 310   //
 311   if (Ty == Type::VoidTy) {
 312     // If this is the first type that this node has seen, just accept it without
 313     // question....
 314     assert(Offset == 0 && "Cannot have an offset into a void node!");
 315     assert(!isArray() && "This shouldn't happen!");
 316     Ty = NewTy;
 317     NodeType &= ~Array;
 318     if (WillBeArray) NodeType |= Array;
 319     Size = NewTySize;
 320
 321     // Calculate the number of outgoing links from this node.
 322     Links.resize((Size+DS::PointerSize-1) >> DS::PointerShift);
 323     return false;
 324   }
 325
 326   // Handle node expansion case here...
 327   if (Offset+NewTySize > Size) {
 328     // It is illegal to grow this node if we have treated it as an array of
 329     // objects...
 330     if (isArray()) {
 331       if (FoldIfIncompatible) foldNodeCompletely();
 332       return true;
 333     }
 334
 335     if (Offset) {  // We could handle this case, but we don't for now...
 336       std::cerr << "UNIMP: Trying to merge a growth type into "
 337                 << "offset != 0: Collapsing!\n";
 338       if (FoldIfIncompatible) foldNodeCompletely();
 339       return true;
 340     }
 341
 342     // Okay, the situation is nice and simple, we are trying to merge a type in
 343     // at offset 0 that is bigger than our current type.  Implement this by
 344     // switching to the new type and then merge in the smaller one, which should
 345     // hit the other code path here.  If the other code path decides it's not
 346     // ok, it will collapse the node as appropriate.
 347     //
 348     const Type *OldTy = Ty;
 349     Ty = NewTy;
 350     NodeType &= ~Array;
 351     if (WillBeArray) NodeType |= Array;
 352     Size = NewTySize;
 353
 354     // Must grow links to be the appropriate size...
 355     Links.resize((Size+DS::PointerSize-1) >> DS::PointerShift);
 356
 357     // Merge in the old type now... which is guaranteed to be smaller than the
 358     // "current" type.
 359     return mergeTypeInfo(OldTy, 0);
 360   }
 361
 362   assert(Offset <= Size &&
 363          "Cannot merge something into a part of our type that doesn't exist!");
 364
 365   // Find the section of Ty that NewTy overlaps with... first we find the
 366   // type that starts at offset Offset.
 367   //
 368   unsigned O = 0;
 369   const Type *SubType = Ty;
 370   while (O < Offset) {
 371     assert(Offset-O < TD.getTypeSize(SubType) && "Offset out of range!");
 372
 373     switch (SubType->getPrimitiveID()) {
 374     case Type::StructTyID: {
 375       const StructType *STy = cast<StructType>(SubType);
 376       const StructLayout &SL = *TD.getStructLayout(STy);
 377
 378       unsigned i = 0, e = SL.MemberOffsets.size();
 379       for (; i+1 < e && SL.MemberOffsets[i+1] <= Offset-O; ++i)
 380         /* empty */;
 381
 382       // The offset we are looking for must be in the i'th element...
 383       SubType = STy->getElementTypes()[i];
 384       O += SL.MemberOffsets[i];
 385       break;
 386     }
 387     case Type::ArrayTyID: {
 388       SubType = cast<ArrayType>(SubType)->getElementType();
 389       unsigned ElSize = TD.getTypeSize(SubType);
 390       unsigned Remainder = (Offset-O) % ElSize;
 391       O = Offset-Remainder;
 392       break;
 393     }
 394     default:
 395       if (FoldIfIncompatible) foldNodeCompletely();
 396       return true;
 397     }
 398   }
 399
 400   assert(O == Offset && "Could not achieve the correct offset!");
 401
 402   // If we found our type exactly, early exit
 403   if (SubType == NewTy) return false;
 404
 405   unsigned SubTypeSize = SubType->isSized() ? TD.getTypeSize(SubType) : 0;
 406
 407   // Ok, we are getting desperate now.  Check for physical subtyping, where we
 408   // just require each element in the node to be compatible.
 409   if (NewTySize <= SubTypeSize && NewTySize && NewTySize < 256 &&
 410       SubTypeSize && SubTypeSize < 256 &&
 411       ElementTypesAreCompatible(NewTy, SubType))
 412     return false;
 413
 414   // Okay, so we found the leader type at the offset requested.  Search the list
 415   // of types that starts at this offset.  If SubType is currently an array or
 416   // structure, the type desired may actually be the first element of the
 417   // composite type...
 418   //
 419   unsigned PadSize = SubTypeSize; // Size, including pad memory which is ignored
 420   while (SubType != NewTy) {
 421     const Type *NextSubType = 0;
 422     unsigned NextSubTypeSize = 0;
 423     unsigned NextPadSize = 0;
 424     switch (SubType->getPrimitiveID()) {
 425     case Type::StructTyID: {
 426       const StructType *STy = cast<StructType>(SubType);
 427       const StructLayout &SL = *TD.getStructLayout(STy);
 428       if (SL.MemberOffsets.size() > 1)
 429         NextPadSize = SL.MemberOffsets[1];
 430       else
 431         NextPadSize = SubTypeSize;
 432       NextSubType = STy->getElementTypes()[0];
 433       NextSubTypeSize = TD.getTypeSize(NextSubType);
 434       break;
 435     }
 436     case Type::ArrayTyID:
 437       NextSubType = cast<ArrayType>(SubType)->getElementType();
 438       NextSubTypeSize = TD.getTypeSize(NextSubType);
 439       NextPadSize = NextSubTypeSize;
 440       break;
 441     default: ;
 442       // fall out
 443     }
 444
 445     if (NextSubType == 0)
 446       break;   // In the default case, break out of the loop
 447
 448     if (NextPadSize < NewTySize)
 449       break;   // Don't allow shrinking to a smaller type than NewTySize
 450     SubType = NextSubType;
 451     SubTypeSize = NextSubTypeSize;
 452     PadSize = NextPadSize;
 453   }
 454
 455   // If we found the type exactly, return it...
 456   if (SubType == NewTy)
 457     return false;
 458
 459   // Check to see if we have a compatible, but different type...
 460   if (NewTySize == SubTypeSize) {
 461     // Check to see if this type is obviously convertible... int -> uint f.e.
 462     if (NewTy->isLosslesslyConvertibleTo(SubType))
 463       return false;
 464
 465     // Check to see if we have a pointer & integer mismatch going on here,
 466     // loading a pointer as a long, for example.
 467     //
 468     if (SubType->isInteger() && isa<PointerType>(NewTy) ||
 469         NewTy->isInteger() && isa<PointerType>(SubType))
 470       return false;
 471   } else if (NewTySize > SubTypeSize && NewTySize <= PadSize) {
 472     // We are accessing the field, plus some structure padding.  Ignore the
 473     // structure padding.
 474     return false;
 475   }
 476
 477   DEBUG(std::cerr << "MergeTypeInfo Folding OrigTy: " << Ty
 478                   << "\n due to:" << NewTy << " @ " << Offset << "!\n"
 479                   << "SubType: " << SubType << "\n\n");
 480
 481   if (FoldIfIncompatible) foldNodeCompletely();
 482   return true;
 483 }
 484
 485
 486
 487 // addEdgeTo - Add an edge from the current node to the specified node.  This
 488 // can cause merging of nodes in the graph.
 489 //
 490 void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) {
 491   if (NH.getNode() == 0) return;       // Nothing to do
 492
 493   DSNodeHandle &ExistingEdge = getLink(Offset);
 494   if (ExistingEdge.getNode()) {
 495     // Merge the two nodes...
 496     ExistingEdge.mergeWith(NH);
 497   } else {                             // No merging to perform...
 498     setLink(Offset, NH);               // Just force a link in there...
 499   }
 500 }
 501
 502
 503 // MergeSortedVectors - Efficiently merge a vector into another vector where
 504 // duplicates are not allowed and both are sorted.  This assumes that 'T's are
 505 // efficiently copyable and have sane comparison semantics.
 506 //
 507 static void MergeSortedVectors(std::vector<GlobalValue*> &Dest,
 508                                const std::vector<GlobalValue*> &Src) {
 509   // By far, the most common cases will be the simple ones.  In these cases,
 510   // avoid having to allocate a temporary vector...
 511   //
 512   if (Src.empty()) {             // Nothing to merge in...
 513     return;
 514   } else if (Dest.empty()) {     // Just copy the result in...
 515     Dest = Src;
 516   } else if (Src.size() == 1) {  // Insert a single element...
 517     const GlobalValue *V = Src[0];
 518     std::vector<GlobalValue*>::iterator I =
 519       std::lower_bound(Dest.begin(), Dest.end(), V);
 520     if (I == Dest.end() || *I != Src[0])  // If not already contained...
 521       Dest.insert(I, Src[0]);
 522   } else if (Dest.size() == 1) {
 523     GlobalValue *Tmp = Dest[0];           // Save value in temporary...
 524     Dest = Src;                           // Copy over list...
 525     std::vector<GlobalValue*>::iterator I =
 526       std::lower_bound(Dest.begin(), Dest.end(), Tmp);
 527     if (I == Dest.end() || *I != Tmp)     // If not already contained...
 528       Dest.insert(I, Tmp);
 529
 530   } else {
 531     // Make a copy to the side of Dest...
 532     std::vector<GlobalValue*> Old(Dest);
 533
 534     // Make space for all of the type entries now...
 535     Dest.resize(Dest.size()+Src.size());
 536
 537     // Merge the two sorted ranges together... into Dest.
 538     std::merge(Old.begin(), Old.end(), Src.begin(), Src.end(), Dest.begin());
 539
 540     // Now erase any duplicate entries that may have accumulated into the
 541     // vectors (because they were in both of the input sets)
 542     Dest.erase(std::unique(Dest.begin(), Dest.end()), Dest.end());
 543   }
 544 }
 545
 546
 547 // MergeNodes() - Helper function for DSNode::mergeWith().
 548 // This function does the hard work of merging two nodes, CurNodeH
 549 // and NH after filtering out trivial cases and making sure that
 550 // CurNodeH.offset >= NH.offset.
 551 //
 552 // ***WARNING***
 553 // Since merging may cause either node to go away, we must always
 554 // use the node-handles to refer to the nodes.  These node handles are
 555 // automatically updated during merging, so will always provide access
 556 // to the correct node after a merge.
 557 //
 558 void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) {
 559   assert(CurNodeH.getOffset() >= NH.getOffset() &&
 560          "This should have been enforced in the caller.");
 561
 562   // Now we know that Offset >= NH.Offset, so convert it so our "Offset" (with
 563   // respect to NH.Offset) is now zero.  NOffset is the distance from the base
 564   // of our object that N starts from.
 565   //
 566   unsigned NOffset = CurNodeH.getOffset()-NH.getOffset();
 567   unsigned NSize = NH.getNode()->getSize();
 568
 569   // If the two nodes are of different size, and the smaller node has the array
 570   // bit set, collapse!
 571   if (NSize != CurNodeH.getNode()->getSize()) {
 572     if (NSize < CurNodeH.getNode()->getSize()) {
 573       if (NH.getNode()->isArray())
 574         NH.getNode()->foldNodeCompletely();
 575     } else if (CurNodeH.getNode()->isArray()) {
 576       NH.getNode()->foldNodeCompletely();
 577     }
 578   }
 579
 580   // Merge the type entries of the two nodes together...
 581   if (NH.getNode()->Ty != Type::VoidTy)
 582     CurNodeH.getNode()->mergeTypeInfo(NH.getNode()->Ty, NOffset);
 583   assert(!CurNodeH.getNode()->isDeadNode());
 584
 585   // If we are merging a node with a completely folded node, then both nodes are
 586   // now completely folded.
 587   //
 588   if (CurNodeH.getNode()->isNodeCompletelyFolded()) {
 589     if (!NH.getNode()->isNodeCompletelyFolded()) {
 590       NH.getNode()->foldNodeCompletely();
 591       assert(NH.getNode() && NH.getOffset() == 0 &&
 592              "folding did not make offset 0?");
 593       NOffset = NH.getOffset();
 594       NSize = NH.getNode()->getSize();
 595       assert(NOffset == 0 && NSize == 1);
 596     }
 597   } else if (NH.getNode()->isNodeCompletelyFolded()) {
 598     CurNodeH.getNode()->foldNodeCompletely();
 599     assert(CurNodeH.getNode() && CurNodeH.getOffset() == 0 &&
 600            "folding did not make offset 0?");
 601     NOffset = NH.getOffset();
 602     NSize = NH.getNode()->getSize();
 603     assert(NOffset == 0 && NSize == 1);
 604   }
 605
 606   DSNode *N = NH.getNode();
 607   if (CurNodeH.getNode() == N || N == 0) return;
 608   assert(!CurNodeH.getNode()->isDeadNode());
 609
 610   // Merge the NodeType information...
 611   CurNodeH.getNode()->NodeType |= N->NodeType;
 612
 613   // Start forwarding to the new node!
 614   N->forwardNode(CurNodeH.getNode(), NOffset);
 615   assert(!CurNodeH.getNode()->isDeadNode());
 616
 617   // Make all of the outgoing links of N now be outgoing links of CurNodeH.
 618   //
 619   for (unsigned i = 0; i < N->getNumLinks(); ++i) {
 620     DSNodeHandle &Link = N->getLink(i << DS::PointerShift);
 621     if (Link.getNode()) {
 622       // Compute the offset into the current node at which to
 623       // merge this link.  In the common case, this is a linear
 624       // relation to the offset in the original node (with
 625       // wrapping), but if the current node gets collapsed due to
 626       // recursive merging, we must make sure to merge in all remaining
 627       // links at offset zero.
 628       unsigned MergeOffset = 0;
 629       DSNode *CN = CurNodeH.getNode();
 630       if (CN->Size != 1)
 631         MergeOffset = ((i << DS::PointerShift)+NOffset) % CN->getSize();
 632       CN->addEdgeTo(MergeOffset, Link);
 633     }
 634   }
 635
 636   // Now that there are no outgoing edges, all of the Links are dead.
 637   N->Links.clear();
 638
 639   // Merge the globals list...
 640   if (!N->Globals.empty()) {
 641     MergeSortedVectors(CurNodeH.getNode()->Globals, N->Globals);
 642
 643     // Delete the globals from the old node...
 644     std::vector<GlobalValue*>().swap(N->Globals);
 645   }
 646 }
 647
 648
 649 // mergeWith - Merge this node and the specified node, moving all links to and
 650 // from the argument node into the current node, deleting the node argument.
 651 // Offset indicates what offset the specified node is to be merged into the
 652 // current node.
 653 //
 654 // The specified node may be a null pointer (in which case, nothing happens).
 655 //
 656 void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) {
 657   DSNode *N = NH.getNode();
 658   if (N == 0 || (N == this && NH.getOffset() == Offset))
 659     return;  // Noop
 660
 661   assert(!N->isDeadNode() && !isDeadNode());
 662   assert(!hasNoReferrers() && "Should not try to fold a useless node!");
 663
 664   if (N == this) {
 665     // We cannot merge two pieces of the same node together, collapse the node
 666     // completely.
 667     DEBUG(std::cerr << "Attempting to merge two chunks of"
 668                     << " the same node together!\n");
 669     foldNodeCompletely();
 670     return;
 671   }
 672
 673   // If both nodes are not at offset 0, make sure that we are merging the node
 674   // at an later offset into the node with the zero offset.
 675   //
 676   if (Offset < NH.getOffset()) {
 677     N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset());
 678     return;
 679   } else if (Offset == NH.getOffset() && getSize() < N->getSize()) {
 680     // If the offsets are the same, merge the smaller node into the bigger node
 681     N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset());
 682     return;
 683   }
 684
 685   // Ok, now we can merge the two nodes.  Use a static helper that works with
 686   // two node handles, since "this" may get merged away at intermediate steps.
 687   DSNodeHandle CurNodeH(this, Offset);
 688   DSNodeHandle NHCopy(NH);
 689   DSNode::MergeNodes(CurNodeH, NHCopy);
 690 }
 691
 692 //===----------------------------------------------------------------------===//
 693 // DSCallSite Implementation
 694 //===----------------------------------------------------------------------===//
 695
 696 // Define here to avoid including iOther.h and BasicBlock.h in DSGraph.h
 697 Function &DSCallSite::getCaller() const {
 698   return *Inst->getParent()->getParent();
 699 }
 700
 701
 702 //===----------------------------------------------------------------------===//
 703 // DSGraph Implementation
 704 //===----------------------------------------------------------------------===//
 705
 706 DSGraph::DSGraph(const DSGraph &G) : GlobalsGraph(0) {
 707   PrintAuxCalls = false;
 708   NodeMapTy NodeMap;
 709   cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
 710 }
 711
 712 DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap)
 713   : GlobalsGraph(0) {
 714   PrintAuxCalls = false;
 715   cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
 716 }
 717
 718 DSGraph::~DSGraph() {
 719   FunctionCalls.clear();
 720   AuxFunctionCalls.clear();
 721   ScalarMap.clear();
 722   ReturnNodes.clear();
 723
 724   // Drop all intra-node references, so that assertions don't fail...
 725   std::for_each(Nodes.begin(), Nodes.end(),
 726                 std::mem_fun(&DSNode::dropAllReferences));
 727
 728   // Delete all of the nodes themselves...
 729   std::for_each(Nodes.begin(), Nodes.end(), deleter<DSNode>);
 730 }
 731
 732 // dump - Allow inspection of graph in a debugger.
 733 void DSGraph::dump() const { print(std::cerr); }
 734
 735
 736 /// remapLinks - Change all of the Links in the current node according to the
 737 /// specified mapping.
 738 ///
 739 void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) {
 740   for (unsigned i = 0, e = Links.size(); i != e; ++i) {
 741     DSNodeHandle &H = OldNodeMap[Links[i].getNode()];
 742     Links[i].setNode(H.getNode());
 743     Links[i].setOffset(Links[i].getOffset()+H.getOffset());
 744   }
 745 }
 746
 747
 748 /// cloneInto - Clone the specified DSGraph into the current graph.  The
 749 /// translated ScalarMap for the old function is filled into the OldValMap
 750 /// member, and the translated ReturnNodes map is returned into ReturnNodes.
 751 ///
 752 /// The CloneFlags member controls various aspects of the cloning process.
 753 ///
 754 void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap,
 755                         ReturnNodesTy &OldReturnNodes, NodeMapTy &OldNodeMap,
 756                         unsigned CloneFlags) {
 757   assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!");
 758   assert(&G != this && "Cannot clone graph into itself!");
 759
 760   unsigned FN = Nodes.size();           // First new node...
 761
 762   // Duplicate all of the nodes, populating the node map...
 763   Nodes.reserve(FN+G.Nodes.size());
 764
 765   // Remove alloca or mod/ref bits as specified...
 766   unsigned BitsToClear =((CloneFlags & StripAllocaBit) ? DSNode::AllocaNode : 0)
 767     | ((CloneFlags & StripModRefBits) ? (DSNode::Modified | DSNode::Read) : 0);
 768   BitsToClear |= DSNode::DEAD;  // Clear dead flag...
 769   for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i) {
 770     DSNode *Old = G.Nodes[i];
 771     DSNode *New = new DSNode(*Old, this);
 772     New->maskNodeTypes(~BitsToClear);
 773     OldNodeMap[Old] = New;
 774   }
 775
 776 #ifndef NDEBUG
 777   Timer::addPeakMemoryMeasurement();
 778 #endif
 779
 780   // Rewrite the links in the new nodes to point into the current graph now.
 781   for (unsigned i = FN, e = Nodes.size(); i != e; ++i)
 782     Nodes[i]->remapLinks(OldNodeMap);
 783
 784   // Copy the scalar map... merging all of the global nodes...
 785   for (ScalarMapTy::const_iterator I = G.ScalarMap.begin(),
 786          E = G.ScalarMap.end(); I != E; ++I) {
 787     DSNodeHandle &H = OldValMap[I->first];
 788     DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()];
 789     H.setOffset(I->second.getOffset()+MappedNode.getOffset());
 790     H.setNode(MappedNode.getNode());
 791
 792     if (isa<GlobalValue>(I->first)) {  // Is this a global?
 793       ScalarMapTy::iterator GVI = ScalarMap.find(I->first);
 794       if (GVI != ScalarMap.end())     // Is the global value in this fn already?
 795         GVI->second.mergeWith(H);
 796       else
 797         ScalarMap[I->first] = H;      // Add global pointer to this graph
 798     }
 799   }
 800
 801   if (!(CloneFlags & DontCloneCallNodes)) {
 802     // Copy the function calls list...
 803     unsigned FC = FunctionCalls.size();  // FirstCall
 804     FunctionCalls.reserve(FC+G.FunctionCalls.size());
 805     for (unsigned i = 0, ei = G.FunctionCalls.size(); i != ei; ++i)
 806       FunctionCalls.push_back(DSCallSite(G.FunctionCalls[i], OldNodeMap));
 807   }
 808
 809   if (!(CloneFlags & DontCloneAuxCallNodes)) {
 810     // Copy the auxillary function calls list...
 811     unsigned FC = AuxFunctionCalls.size();  // FirstCall
 812     AuxFunctionCalls.reserve(FC+G.AuxFunctionCalls.size());
 813     for (unsigned i = 0, ei = G.AuxFunctionCalls.size(); i != ei; ++i)
 814       AuxFunctionCalls.push_back(DSCallSite(G.AuxFunctionCalls[i], OldNodeMap));
 815   }
 816
 817   // Map the return node pointers over...
 818   for (ReturnNodesTy::const_iterator I = G.getReturnNodes().begin(),
 819          E = G.getReturnNodes().end(); I != E; ++I) {
 820     const DSNodeHandle &Ret = I->second;
 821     DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()];
 822     OldReturnNodes.insert(std::make_pair(I->first,
 823                           DSNodeHandle(MappedRet.getNode(),
 824                                        MappedRet.getOffset()+Ret.getOffset())));
 825   }
 826 }
 827
 828 /// mergeInGraph - The method is used for merging graphs together.  If the
 829 /// argument graph is not *this, it makes a clone of the specified graph, then
 830 /// merges the nodes specified in the call site with the formal arguments in the
 831 /// graph.
 832 ///
 833 void DSGraph::mergeInGraph(DSCallSite &CS, Function &F, const DSGraph &Graph,
 834                            unsigned CloneFlags) {
 835   ScalarMapTy OldValMap;
 836   ScalarMapTy *ScalarMap = &OldValMap;
 837   DSNodeHandle RetVal;
 838
 839   // If this is not a recursive call, clone the graph into this graph...
 840   if (&Graph != this) {
 841     // Clone the callee's graph into the current graph, keeping
 842     // track of where scalars in the old graph _used_ to point,
 843     // and of the new nodes matching nodes of the old graph.
 844     NodeMapTy OldNodeMap;
 845
 846     // The clone call may invalidate any of the vectors in the data
 847     // structure graph.  Strip locals and don't copy the list of callers
 848     ReturnNodesTy OldRetNodes;
 849     cloneInto(Graph, OldValMap, OldRetNodes, OldNodeMap, CloneFlags);
 850     RetVal = OldRetNodes[&F];
 851     ScalarMap = &OldValMap;
 852   } else {
 853     RetVal = getReturnNodeFor(F);
 854     ScalarMap = &getScalarMap();
 855   }
 856
 857   // Merge the return value with the return value of the context...
 858   RetVal.mergeWith(CS.getRetVal());
 859
 860   // Resolve all of the function arguments...
 861   Function::aiterator AI = F.abegin();
 862
 863   for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) {
 864     // Advance the argument iterator to the first pointer argument...
 865     while (AI != F.aend() && !isPointerType(AI->getType())) {
 866       ++AI;
 867 #ifndef NDEBUG
 868       if (AI == F.aend())
 869         std::cerr << "Bad call to Function: " << F.getName() << "\n";
 870 #endif
 871     }
 872     if (AI == F.aend()) break;
 873
 874     // Add the link from the argument scalar to the provided value
 875     assert(ScalarMap->count(AI) && "Argument not in scalar map?");
 876     DSNodeHandle &NH = (*ScalarMap)[AI];
 877     assert(NH.getNode() && "Pointer argument without scalarmap entry?");
 878     NH.mergeWith(CS.getPtrArg(i));
 879   }
 880 }
 881
 882
 883 // markIncompleteNodes - Mark the specified node as having contents that are not
 884 // known with the current analysis we have performed.  Because a node makes all
 885 // of the nodes it can reach incomplete if the node itself is incomplete, we
 886 // must recursively traverse the data structure graph, marking all reachable
 887 // nodes as incomplete.
 888 //
 889 static void markIncompleteNode(DSNode *N) {
 890   // Stop recursion if no node, or if node already marked...
 891   if (N == 0 || N->isIncomplete()) return;
 892
 893   // Actually mark the node
 894   N->setIncompleteMarker();
 895
 896   // Recusively process children...
 897   for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize)
 898     if (DSNode *DSN = N->getLink(i).getNode())
 899       markIncompleteNode(DSN);
 900 }
 901
 902 static void markIncomplete(DSCallSite &Call) {
 903   // Then the return value is certainly incomplete!
 904   markIncompleteNode(Call.getRetVal().getNode());
 905
 906   // All objects pointed to by function arguments are incomplete!
 907   for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i)
 908     markIncompleteNode(Call.getPtrArg(i).getNode());
 909 }
 910
 911 // markIncompleteNodes - Traverse the graph, identifying nodes that may be
 912 // modified by other functions that have not been resolved yet.  This marks
 913 // nodes that are reachable through three sources of "unknownness":
 914 //
 915 //  Global Variables, Function Calls, and Incoming Arguments
 916 //
 917 // For any node that may have unknown components (because something outside the
 918 // scope of current analysis may have modified it), the 'Incomplete' flag is
 919 // added to the NodeType.
 920 //
 921 void DSGraph::markIncompleteNodes(unsigned Flags) {
 922   // Mark any incoming arguments as incomplete...
 923   if (Flags & DSGraph::MarkFormalArgs)
 924     for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end();
 925          FI != E; ++FI) {
 926       Function &F = *FI->first;
 927       if (F.getName() != "main")
 928         for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
 929           if (isPointerType(I->getType()) &&
 930               ScalarMap.find(I) != ScalarMap.end())
 931             markIncompleteNode(ScalarMap[I].getNode());
 932     }
 933
 934   // Mark stuff passed into functions calls as being incomplete...
 935   if (!shouldPrintAuxCalls())
 936     for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i)
 937       markIncomplete(FunctionCalls[i]);
 938   else
 939     for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
 940       markIncomplete(AuxFunctionCalls[i]);
 941
 942
 943   // Mark all global nodes as incomplete...
 944   if ((Flags & DSGraph::IgnoreGlobals) == 0)
 945     for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
 946       if (Nodes[i]->isGlobalNode() && Nodes[i]->getNumLinks())
 947         markIncompleteNode(Nodes[i]);
 948 }
 949
 950 static inline void killIfUselessEdge(DSNodeHandle &Edge) {
 951   if (DSNode *N = Edge.getNode())  // Is there an edge?
 952     if (N->getNumReferrers() == 1)  // Does it point to a lonely node?
 953       // No interesting info?
 954       if ((N->getNodeFlags() & ~DSNode::Incomplete) == 0 &&
 955           N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded())
 956         Edge.setNode(0);  // Kill the edge!
 957 }
 958
 959 static inline bool nodeContainsExternalFunction(const DSNode *N) {
 960   const std::vector<GlobalValue*> &Globals = N->getGlobals();
 961   for (unsigned i = 0, e = Globals.size(); i != e; ++i)
 962     if (Globals[i]->isExternal())
 963       return true;
 964   return false;
 965 }
 966
 967 static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
 968   // Remove trivially identical function calls
 969   unsigned NumFns = Calls.size();
 970   std::sort(Calls.begin(), Calls.end());  // Sort by callee as primary key!
 971
 972   // Scan the call list cleaning it up as necessary...
 973   DSNode   *LastCalleeNode = 0;
 974   Function *LastCalleeFunc = 0;
 975   unsigned NumDuplicateCalls = 0;
 976   bool LastCalleeContainsExternalFunction = false;
 977   for (unsigned i = 0; i != Calls.size(); ++i) {
 978     DSCallSite &CS = Calls[i];
 979
 980     // If the Callee is a useless edge, this must be an unreachable call site,
 981     // eliminate it.
 982     if (CS.isIndirectCall() && CS.getCalleeNode()->getNumReferrers() == 1 &&
 983         CS.getCalleeNode()->getNodeFlags() == 0) {  // No useful info?
 984       std::cerr << "WARNING: Useless call site found??\n";
 985       CS.swap(Calls.back());
 986       Calls.pop_back();
 987       --i;
 988     } else {
 989       // If the return value or any arguments point to a void node with no
 990       // information at all in it, and the call node is the only node to point
 991       // to it, remove the edge to the node (killing the node).
 992       //
 993       killIfUselessEdge(CS.getRetVal());
 994       for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
 995         killIfUselessEdge(CS.getPtrArg(a));
 996
 997       // If this call site calls the same function as the last call site, and if
 998       // the function pointer contains an external function, this node will
 999       // never be resolved.  Merge the arguments of the call node because no
1000       // information will be lost.
1001       //
1002       if ((CS.isDirectCall()   && CS.getCalleeFunc() == LastCalleeFunc) ||
1003           (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) {
1004         ++NumDuplicateCalls;
1005         if (NumDuplicateCalls == 1) {
1006           if (LastCalleeNode)
1007             LastCalleeContainsExternalFunction =
1008               nodeContainsExternalFunction(LastCalleeNode);
1009           else
1010             LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal();
1011         }
1012
1013         if (LastCalleeContainsExternalFunction ||
1014             // This should be more than enough context sensitivity!
1015             // FIXME: Evaluate how many times this is tripped!
1016             NumDuplicateCalls > 20) {
1017           DSCallSite &OCS = Calls[i-1];
1018           OCS.mergeWith(CS);
1019
1020           // The node will now be eliminated as a duplicate!
1021           if (CS.getNumPtrArgs() < OCS.getNumPtrArgs())
1022             CS = OCS;
1023           else if (CS.getNumPtrArgs() > OCS.getNumPtrArgs())
1024             OCS = CS;
1025         }
1026       } else {
1027         if (CS.isDirectCall()) {
1028           LastCalleeFunc = CS.getCalleeFunc();
1029           LastCalleeNode = 0;
1030         } else {
1031           LastCalleeNode = CS.getCalleeNode();
1032           LastCalleeFunc = 0;
1033         }
1034         NumDuplicateCalls = 0;
1035       }
1036     }
1037   }
1038
1039   Calls.erase(std::unique(Calls.begin(), Calls.end()),
1040               Calls.end());
1041
1042   // Track the number of call nodes merged away...
1043   NumCallNodesMerged += NumFns-Calls.size();
1044
1045   DEBUG(if (NumFns != Calls.size())
1046           std::cerr << "Merged " << (NumFns-Calls.size()) << " call nodes.\n";);
1047 }
1048
1049
1050 // removeTriviallyDeadNodes - After the graph has been constructed, this method
1051 // removes all unreachable nodes that are created because they got merged with
1052 // other nodes in the graph.  These nodes will all be trivially unreachable, so
1053 // we don't have to perform any non-trivial analysis here.
1054 //
1055 void DSGraph::removeTriviallyDeadNodes() {
1056   removeIdenticalCalls(FunctionCalls);
1057   removeIdenticalCalls(AuxFunctionCalls);
1058
1059   for (unsigned i = 0; i != Nodes.size(); ++i) {
1060     DSNode *Node = Nodes[i];
1061     if (Node->isComplete() && !Node->isModified() && !Node->isRead()) {
1062       // This is a useless node if it has no mod/ref info (checked above),
1063       // outgoing edges (which it cannot, as it is not modified in this
1064       // context), and it has no incoming edges.  If it is a global node it may
1065       // have all of these properties and still have incoming edges, due to the
1066       // scalar map, so we check those now.
1067       //
1068       if (Node->getNumReferrers() == Node->getGlobals().size()) {
1069         const std::vector<GlobalValue*> &Globals = Node->getGlobals();
1070
1071         // Loop through and make sure all of the globals are referring directly
1072         // to the node...
1073         for (unsigned j = 0, e = Globals.size(); j != e; ++j) {
1074           DSNode *N = ScalarMap.find(Globals[j])->second.getNode();
1075           assert(N == Node && "ScalarMap doesn't match globals list!");
1076         }
1077
1078         // Make sure NumReferrers still agrees, if so, the node is truly dead.
1079         if (Node->getNumReferrers() == Globals.size()) {
1080           for (unsigned j = 0, e = Globals.size(); j != e; ++j)
1081             ScalarMap.erase(Globals[j]);
1082           Node->makeNodeDead();
1083         }
1084       }
1085     }
1086
1087     if (Node->getNodeFlags() == 0 && Node->hasNoReferrers()) {
1088       // This node is dead!
1089       delete Node;                        // Free memory...
1090       Nodes[i--] = Nodes.back();
1091       Nodes.pop_back();                   // Remove from node list...
1092     }
1093   }
1094 }
1095
1096
1097 /// markReachableNodes - This method recursively traverses the specified
1098 /// DSNodes, marking any nodes which are reachable.  All reachable nodes it adds
1099 /// to the set, which allows it to only traverse visited nodes once.
1100 ///
1101 void DSNode::markReachableNodes(hash_set<DSNode*> &ReachableNodes) {
1102   if (this == 0) return;
1103   assert(getForwardNode() == 0 && "Cannot mark a forwarded node!");
1104   if (ReachableNodes.count(this)) return;          // Already marked reachable
1105   ReachableNodes.insert(this);                     // Is reachable now
1106
1107   for (unsigned i = 0, e = getSize(); i < e; i += DS::PointerSize)
1108     getLink(i).getNode()->markReachableNodes(ReachableNodes);
1109 }
1110
1111 void DSCallSite::markReachableNodes(hash_set<DSNode*> &Nodes) {
1112   getRetVal().getNode()->markReachableNodes(Nodes);
1113   if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes);
1114
1115   for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i)
1116     getPtrArg(i).getNode()->markReachableNodes(Nodes);
1117 }
1118
1119 // CanReachAliveNodes - Simple graph walker that recursively traverses the graph
1120 // looking for a node that is marked alive.  If an alive node is found, return
1121 // true, otherwise return false.  If an alive node is reachable, this node is
1122 // marked as alive...
1123 //
1124 static bool CanReachAliveNodes(DSNode *N, hash_set<DSNode*> &Alive,
1125                                hash_set<DSNode*> &Visited) {
1126   if (N == 0) return false;
1127   assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!");
1128
1129   // If we know that this node is alive, return so!
1130   if (Alive.count(N)) return true;
1131
1132   // Otherwise, we don't think the node is alive yet, check for infinite
1133   // recursion.
1134   if (Visited.count(N)) return false;  // Found a cycle
1135   Visited.insert(N);   // No recursion, insert into Visited...
1136
1137   for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize)
1138     if (CanReachAliveNodes(N->getLink(i).getNode(), Alive, Visited)) {
1139       N->markReachableNodes(Alive);
1140       return true;
1141     }
1142   return false;
1143 }
1144
1145 // CallSiteUsesAliveArgs - Return true if the specified call site can reach any
1146 // alive nodes.
1147 //
1148 static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set<DSNode*> &Alive,
1149                                   hash_set<DSNode*> &Visited) {
1150   if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited))
1151     return true;
1152   if (CS.isIndirectCall() &&
1153       CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited))
1154     return true;
1155   for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
1156     if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited))
1157       return true;
1158   return false;
1159 }
1160
1161 // removeDeadNodes - Use a more powerful reachability analysis to eliminate
1162 // subgraphs that are unreachable.  This often occurs because the data
1163 // structure doesn't "escape" into it's caller, and thus should be eliminated
1164 // from the caller's graph entirely.  This is only appropriate to use when
1165 // inlining graphs.
1166 //
1167 void DSGraph::removeDeadNodes(unsigned Flags) {
1168   // Reduce the amount of work we have to do... remove dummy nodes left over by
1169   // merging...
1170   removeTriviallyDeadNodes();
1171
1172   // FIXME: Merge nontrivially identical call nodes...
1173
1174   // Alive - a set that holds all nodes found to be reachable/alive.
1175   hash_set<DSNode*> Alive;
1176   std::vector<std::pair<Value*, DSNode*> > GlobalNodes;
1177
1178   // Mark all nodes reachable by (non-global) scalar nodes as alive...
1179   for (ScalarMapTy::iterator I = ScalarMap.begin(), E = ScalarMap.end(); I !=E;)
1180     if (isa<GlobalValue>(I->first)) {             // Keep track of global nodes
1181       assert(I->second.getNode() && "Null global node?");
1182       GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode()));
1183       ++I;
1184     } else {
1185       // Check to see if this is a worthless node generated for non-pointer
1186       // values, such as integers.  Consider an addition of long types: A+B.
1187       // Assuming we can track all uses of the value in this context, and it is
1188       // NOT used as a pointer, we can delete the node.  We will be able to
1189       // detect this situation if the node pointed to ONLY has Unknown bit set
1190       // in the node.  In this case, the node is not incomplete, does not point
1191       // to any other nodes (no mod/ref bits set), and is therefore
1192       // uninteresting for data structure analysis.  If we run across one of
1193       // these, prune the scalar pointing to it.
1194       //
1195       DSNode *N = I->second.getNode();
1196       if (N->isUnknownNode() && !isa<Argument>(I->first)) {
1197         ScalarMap.erase(I++);
1198       } else {
1199         I->second.getNode()->markReachableNodes(Alive);
1200         ++I;
1201       }
1202     }
1203
1204   // The return value is alive as well...
1205   for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end();
1206        I != E; ++I)
1207     I->second.getNode()->markReachableNodes(Alive);
1208
1209   // Mark any nodes reachable by primary calls as alive...
1210   for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i)
1211     FunctionCalls[i].markReachableNodes(Alive);
1212
1213   bool Iterate;
1214   hash_set<DSNode*> Visited;
1215   std::vector<unsigned char> AuxFCallsAlive(AuxFunctionCalls.size());
1216   do {
1217     Visited.clear();
1218     // If any global nodes points to a non-global that is "alive", the global is
1219     // "alive" as well...  Remove it from the GlobalNodes list so we only have
1220     // unreachable globals in the list.
1221     //
1222     Iterate = false;
1223     for (unsigned i = 0; i != GlobalNodes.size(); ++i)
1224       if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited)) {
1225         std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to erase
1226         GlobalNodes.pop_back();                          // Erase efficiently
1227         Iterate = true;
1228       }
1229
1230     for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
1231       if (!AuxFCallsAlive[i] &&
1232           CallSiteUsesAliveArgs(AuxFunctionCalls[i], Alive, Visited)) {
1233         AuxFunctionCalls[i].markReachableNodes(Alive);
1234         AuxFCallsAlive[i] = true;
1235         Iterate = true;
1236       }
1237   } while (Iterate);
1238
1239   // Remove all dead aux function calls...
1240   unsigned CurIdx = 0;
1241   for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
1242     if (AuxFCallsAlive[i])
1243       AuxFunctionCalls[CurIdx++].swap(AuxFunctionCalls[i]);
1244   if (!(Flags & DSGraph::RemoveUnreachableGlobals)) {
1245     assert(GlobalsGraph && "No globals graph available??");
1246     // Move the unreachable call nodes to the globals graph...
1247     GlobalsGraph->AuxFunctionCalls.insert(GlobalsGraph->AuxFunctionCalls.end(),
1248                                           AuxFunctionCalls.begin()+CurIdx,
1249                                           AuxFunctionCalls.end());
1250   }
1251   // Crop all the useless ones out...
1252   AuxFunctionCalls.erase(AuxFunctionCalls.begin()+CurIdx,
1253                          AuxFunctionCalls.end());
1254
1255   // At this point, any nodes which are visited, but not alive, are nodes which
1256   // should be moved to the globals graph.  Loop over all nodes, eliminating
1257   // completely unreachable nodes, and moving visited nodes to the globals graph
1258   //
1259   std::vector<DSNode*> DeadNodes;
1260   DeadNodes.reserve(Nodes.size());
1261   for (unsigned i = 0; i != Nodes.size(); ++i)
1262     if (!Alive.count(Nodes[i])) {
1263       DSNode *N = Nodes[i];
1264       Nodes[i--] = Nodes.back();            // move node to end of vector
1265       Nodes.pop_back();                     // Erase node from alive list.
1266       if (!(Flags & DSGraph::RemoveUnreachableGlobals) &&  // Not in TD pass
1267           Visited.count(N)) {                    // Visited but not alive?
1268         GlobalsGraph->Nodes.push_back(N);        // Move node to globals graph
1269         N->setParentGraph(GlobalsGraph);
1270       } else {                                 // Otherwise, delete the node
1271         assert((!N->isGlobalNode() ||
1272                 (Flags & DSGraph::RemoveUnreachableGlobals))
1273                && "Killing a global?");
1274         //std::cerr << "[" << i+1 << "/" << DeadNodes.size()
1275         //          << "] Node is dead: "; N->dump();
1276         DeadNodes.push_back(N);
1277         N->dropAllReferences();
1278       }
1279     } else {
1280       assert(Nodes[i]->getForwardNode() == 0 && "Alive forwarded node?");
1281     }
1282
1283   // Now that the nodes have either been deleted or moved to the globals graph,
1284   // loop over the scalarmap, updating the entries for globals...
1285   //
1286   if (!(Flags & DSGraph::RemoveUnreachableGlobals)) {  // Not in the TD pass?
1287     // In this array we start the remapping, which can cause merging.  Because
1288     // of this, the DSNode pointers in GlobalNodes may be invalidated, so we
1289     // must always go through the ScalarMap (which contains DSNodeHandles [which
1290     // cannot be invalidated by merging]).
1291     //
1292     for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) {
1293       Value *G = GlobalNodes[i].first;
1294       ScalarMapTy::iterator I = ScalarMap.find(G);
1295       assert(I != ScalarMap.end() && "Global not in scalar map anymore?");
1296       assert(I->second.getNode() && "Global not pointing to anything?");
1297       assert(!Alive.count(I->second.getNode()) && "Node is alive??");
1298       GlobalsGraph->ScalarMap[G].mergeWith(I->second);
1299       assert(GlobalsGraph->ScalarMap[G].getNode() &&
1300              "Global not pointing to anything?");
1301       ScalarMap.erase(I);
1302     }
1303
1304     // Merging leaves behind silly nodes, we remove them to avoid polluting the
1305     // globals graph.
1306     if (!GlobalNodes.empty())
1307       GlobalsGraph->removeTriviallyDeadNodes();
1308   } else {
1309     // If we are in the top-down pass, remove all unreachable globals from the
1310     // ScalarMap...
1311     for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
1312       ScalarMap.erase(GlobalNodes[i].first);
1313   }
1314
1315   // Loop over all of the dead nodes now, deleting them since their referrer
1316   // count is zero.
1317   for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i)
1318     delete DeadNodes[i];
1319
1320   DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK());
1321 }
1322
1323 void DSGraph::AssertGraphOK() const {
1324   for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
1325     Nodes[i]->assertOK();
1326   return;  // FIXME: remove
1327   for (ScalarMapTy::const_iterator I = ScalarMap.begin(),
1328          E = ScalarMap.end(); I != E; ++I) {
1329     assert(I->second.getNode() && "Null node in scalarmap!");
1330     AssertNodeInGraph(I->second.getNode());
1331     if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) {
1332       assert(I->second.getNode()->isGlobalNode() &&
1333              "Global points to node, but node isn't global?");
1334       AssertNodeContainsGlobal(I->second.getNode(), GV);
1335     }
1336   }
1337   AssertCallNodesInGraph();
1338   AssertAuxCallNodesInGraph();
1339 }