lib/Analysis/DataStructure/DataStructure.cpp

   1 //===- DataStructure.cpp - Implement the core data structure analysis -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the core data structure functionality.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/DSGraph.h"
  15 #include "llvm/Function.h"
  16 #include "llvm/iOther.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Target/TargetData.h"
  19 #include "llvm/Assembly/Writer.h"
  20 #include "Support/Debug.h"
  21 #include "Support/STLExtras.h"
  22 #include "Support/Statistic.h"
  23 #include "Support/Timer.h"
  24 #include <algorithm>
  25 using namespace llvm;
  26
  27 namespace {
  28   Statistic<> NumFolds          ("dsnode", "Number of nodes completely folded");
  29   Statistic<> NumCallNodesMerged("dsnode", "Number of call nodes merged");
  30 };
  31
  32 #if 0
  33 #define TIME_REGION(VARNAME, DESC) \
  34    NamedRegionTimer VARNAME(DESC)
  35 #else
  36 #define TIME_REGION(VARNAME, DESC)
  37 #endif
  38
  39
  40
  41 using namespace DS;
  42
  43 DSNode *DSNodeHandle::HandleForwarding() const {
  44   assert(!N->ForwardNH.isNull() && "Can only be invoked if forwarding!");
  45
  46   // Handle node forwarding here!
  47   DSNode *Next = N->ForwardNH.getNode();  // Cause recursive shrinkage
  48   Offset += N->ForwardNH.getOffset();
  49
  50   if (--N->NumReferrers == 0) {
  51     // Removing the last referrer to the node, sever the forwarding link
  52     N->stopForwarding();
  53   }
  54
  55   N = Next;
  56   N->NumReferrers++;
  57   if (N->Size <= Offset) {
  58     assert(N->Size <= 1 && "Forwarded to shrunk but not collapsed node?");
  59     Offset = 0;
  60   }
  61   return N;
  62 }
  63
  64 //===----------------------------------------------------------------------===//
  65 // DSNode Implementation
  66 //===----------------------------------------------------------------------===//
  67
  68 DSNode::DSNode(const Type *T, DSGraph *G)
  69   : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(0) {
  70   // Add the type entry if it is specified...
  71   if (T) mergeTypeInfo(T, 0);
  72   G->getNodes().push_back(this);
  73 }
  74
  75 // DSNode copy constructor... do not copy over the referrers list!
  76 DSNode::DSNode(const DSNode &N, DSGraph *G)
  77   : NumReferrers(0), Size(N.Size), ParentGraph(G),
  78     Ty(N.Ty), Links(N.Links), Globals(N.Globals), NodeType(N.NodeType) {
  79   G->getNodes().push_back(this);
  80 }
  81
  82 /// getTargetData - Get the target data object used to construct this node.
  83 ///
  84 const TargetData &DSNode::getTargetData() const {
  85   return ParentGraph->getTargetData();
  86 }
  87
  88 void DSNode::assertOK() const {
  89   assert((Ty != Type::VoidTy ||
  90           Ty == Type::VoidTy && (Size == 0 ||
  91                                  (NodeType & DSNode::Array))) &&
  92          "Node not OK!");
  93
  94   assert(ParentGraph && "Node has no parent?");
  95   const DSGraph::ScalarMapTy &SM = ParentGraph->getScalarMap();
  96   for (unsigned i = 0, e = Globals.size(); i != e; ++i) {
  97     assert(SM.find(Globals[i]) != SM.end());
  98     assert(SM.find(Globals[i])->second.getNode() == this);
  99   }
 100 }
 101
 102 /// forwardNode - Mark this node as being obsolete, and all references to it
 103 /// should be forwarded to the specified node and offset.
 104 ///
 105 void DSNode::forwardNode(DSNode *To, unsigned Offset) {
 106   assert(this != To && "Cannot forward a node to itself!");
 107   assert(ForwardNH.isNull() && "Already forwarding from this node!");
 108   if (To->Size <= 1) Offset = 0;
 109   assert((Offset < To->Size || (Offset == To->Size && Offset == 0)) &&
 110          "Forwarded offset is wrong!");
 111   ForwardNH.setNode(To);
 112   ForwardNH.setOffset(Offset);
 113   NodeType = DEAD;
 114   Size = 0;
 115   Ty = Type::VoidTy;
 116 }
 117
 118 // addGlobal - Add an entry for a global value to the Globals list.  This also
 119 // marks the node with the 'G' flag if it does not already have it.
 120 //
 121 void DSNode::addGlobal(GlobalValue *GV) {
 122   // Keep the list sorted.
 123   std::vector<GlobalValue*>::iterator I =
 124     std::lower_bound(Globals.begin(), Globals.end(), GV);
 125
 126   if (I == Globals.end() || *I != GV) {
 127     //assert(GV->getType()->getElementType() == Ty);
 128     Globals.insert(I, GV);
 129     NodeType |= GlobalNode;
 130   }
 131 }
 132
 133 /// foldNodeCompletely - If we determine that this node has some funny
 134 /// behavior happening to it that we cannot represent, we fold it down to a
 135 /// single, completely pessimistic, node.  This node is represented as a
 136 /// single byte with a single TypeEntry of "void".
 137 ///
 138 void DSNode::foldNodeCompletely() {
 139   if (isNodeCompletelyFolded()) return;  // If this node is already folded...
 140
 141   ++NumFolds;
 142
 143   // Create the node we are going to forward to...
 144   DSNode *DestNode = new DSNode(0, ParentGraph);
 145   DestNode->NodeType = NodeType|DSNode::Array;
 146   DestNode->Ty = Type::VoidTy;
 147   DestNode->Size = 1;
 148   DestNode->Globals.swap(Globals);
 149
 150   // Start forwarding to the destination node...
 151   forwardNode(DestNode, 0);
 152
 153   if (Links.size()) {
 154     DestNode->Links.push_back(Links[0]);
 155     DSNodeHandle NH(DestNode);
 156
 157     // If we have links, merge all of our outgoing links together...
 158     for (unsigned i = Links.size()-1; i != 0; --i)
 159       NH.getNode()->Links[0].mergeWith(Links[i]);
 160     Links.clear();
 161   } else {
 162     DestNode->Links.resize(1);
 163   }
 164 }
 165
 166 /// isNodeCompletelyFolded - Return true if this node has been completely
 167 /// folded down to something that can never be expanded, effectively losing
 168 /// all of the field sensitivity that may be present in the node.
 169 ///
 170 bool DSNode::isNodeCompletelyFolded() const {
 171   return getSize() == 1 && Ty == Type::VoidTy && isArray();
 172 }
 173
 174 namespace {
 175   /// TypeElementWalker Class - Used for implementation of physical subtyping...
 176   ///
 177   class TypeElementWalker {
 178     struct StackState {
 179       const Type *Ty;
 180       unsigned Offset;
 181       unsigned Idx;
 182       StackState(const Type *T, unsigned Off = 0)
 183         : Ty(T), Offset(Off), Idx(0) {}
 184     };
 185
 186     std::vector<StackState> Stack;
 187     const TargetData &TD;
 188   public:
 189     TypeElementWalker(const Type *T, const TargetData &td) : TD(td) {
 190       Stack.push_back(T);
 191       StepToLeaf();
 192     }
 193
 194     bool isDone() const { return Stack.empty(); }
 195     const Type *getCurrentType()   const { return Stack.back().Ty;     }
 196     unsigned    getCurrentOffset() const { return Stack.back().Offset; }
 197
 198     void StepToNextType() {
 199       PopStackAndAdvance();
 200       StepToLeaf();
 201     }
 202
 203   private:
 204     /// PopStackAndAdvance - Pop the current element off of the stack and
 205     /// advance the underlying element to the next contained member.
 206     void PopStackAndAdvance() {
 207       assert(!Stack.empty() && "Cannot pop an empty stack!");
 208       Stack.pop_back();
 209       while (!Stack.empty()) {
 210         StackState &SS = Stack.back();
 211         if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) {
 212           ++SS.Idx;
 213           if (SS.Idx != ST->getElementTypes().size()) {
 214             const StructLayout *SL = TD.getStructLayout(ST);
 215             SS.Offset += SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1];
 216             return;
 217           }
 218           Stack.pop_back();  // At the end of the structure
 219         } else {
 220           const ArrayType *AT = cast<ArrayType>(SS.Ty);
 221           ++SS.Idx;
 222           if (SS.Idx != AT->getNumElements()) {
 223             SS.Offset += TD.getTypeSize(AT->getElementType());
 224             return;
 225           }
 226           Stack.pop_back();  // At the end of the array
 227         }
 228       }
 229     }
 230
 231     /// StepToLeaf - Used by physical subtyping to move to the first leaf node
 232     /// on the type stack.
 233     void StepToLeaf() {
 234       if (Stack.empty()) return;
 235       while (!Stack.empty() && !Stack.back().Ty->isFirstClassType()) {
 236         StackState &SS = Stack.back();
 237         if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) {
 238           if (ST->getElementTypes().empty()) {
 239             assert(SS.Idx == 0);
 240             PopStackAndAdvance();
 241           } else {
 242             // Step into the structure...
 243             assert(SS.Idx < ST->getElementTypes().size());
 244             const StructLayout *SL = TD.getStructLayout(ST);
 245             Stack.push_back(StackState(ST->getElementTypes()[SS.Idx],
 246                                        SS.Offset+SL->MemberOffsets[SS.Idx]));
 247           }
 248         } else {
 249           const ArrayType *AT = cast<ArrayType>(SS.Ty);
 250           if (AT->getNumElements() == 0) {
 251             assert(SS.Idx == 0);
 252             PopStackAndAdvance();
 253           } else {
 254             // Step into the array...
 255             assert(SS.Idx < AT->getNumElements());
 256             Stack.push_back(StackState(AT->getElementType(),
 257                                        SS.Offset+SS.Idx*
 258                                        TD.getTypeSize(AT->getElementType())));
 259           }
 260         }
 261       }
 262     }
 263   };
 264 } // end anonymous namespace
 265
 266 /// ElementTypesAreCompatible - Check to see if the specified types are
 267 /// "physically" compatible.  If so, return true, else return false.  We only
 268 /// have to check the fields in T1: T2 may be larger than T1.  If AllowLargerT1
 269 /// is true, then we also allow a larger T1.
 270 ///
 271 static bool ElementTypesAreCompatible(const Type *T1, const Type *T2,
 272                                       bool AllowLargerT1, const TargetData &TD){
 273   TypeElementWalker T1W(T1, TD), T2W(T2, TD);
 274
 275   while (!T1W.isDone() && !T2W.isDone()) {
 276     if (T1W.getCurrentOffset() != T2W.getCurrentOffset())
 277       return false;
 278
 279     const Type *T1 = T1W.getCurrentType();
 280     const Type *T2 = T2W.getCurrentType();
 281     if (T1 != T2 && !T1->isLosslesslyConvertibleTo(T2))
 282       return false;
 283
 284     T1W.StepToNextType();
 285     T2W.StepToNextType();
 286   }
 287
 288   return AllowLargerT1 || T1W.isDone();
 289 }
 290
 291
 292 /// mergeTypeInfo - This method merges the specified type into the current node
 293 /// at the specified offset.  This may update the current node's type record if
 294 /// this gives more information to the node, it may do nothing to the node if
 295 /// this information is already known, or it may merge the node completely (and
 296 /// return true) if the information is incompatible with what is already known.
 297 ///
 298 /// This method returns true if the node is completely folded, otherwise false.
 299 ///
 300 bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset,
 301                            bool FoldIfIncompatible) {
 302   const TargetData &TD = getTargetData();
 303   // Check to make sure the Size member is up-to-date.  Size can be one of the
 304   // following:
 305   //  Size = 0, Ty = Void: Nothing is known about this node.
 306   //  Size = 0, Ty = FnTy: FunctionPtr doesn't have a size, so we use zero
 307   //  Size = 1, Ty = Void, Array = 1: The node is collapsed
 308   //  Otherwise, sizeof(Ty) = Size
 309   //
 310   assert(((Size == 0 && Ty == Type::VoidTy && !isArray()) ||
 311           (Size == 0 && !Ty->isSized() && !isArray()) ||
 312           (Size == 1 && Ty == Type::VoidTy && isArray()) ||
 313           (Size == 0 && !Ty->isSized() && !isArray()) ||
 314           (TD.getTypeSize(Ty) == Size)) &&
 315          "Size member of DSNode doesn't match the type structure!");
 316   assert(NewTy != Type::VoidTy && "Cannot merge void type into DSNode!");
 317
 318   if (Offset == 0 && NewTy == Ty)
 319     return false;  // This should be a common case, handle it efficiently
 320
 321   // Return true immediately if the node is completely folded.
 322   if (isNodeCompletelyFolded()) return true;
 323
 324   // If this is an array type, eliminate the outside arrays because they won't
 325   // be used anyway.  This greatly reduces the size of large static arrays used
 326   // as global variables, for example.
 327   //
 328   bool WillBeArray = false;
 329   while (const ArrayType *AT = dyn_cast<ArrayType>(NewTy)) {
 330     // FIXME: we might want to keep small arrays, but must be careful about
 331     // things like: [2 x [10000 x int*]]
 332     NewTy = AT->getElementType();
 333     WillBeArray = true;
 334   }
 335
 336   // Figure out how big the new type we're merging in is...
 337   unsigned NewTySize = NewTy->isSized() ? TD.getTypeSize(NewTy) : 0;
 338
 339   // Otherwise check to see if we can fold this type into the current node.  If
 340   // we can't, we fold the node completely, if we can, we potentially update our
 341   // internal state.
 342   //
 343   if (Ty == Type::VoidTy) {
 344     // If this is the first type that this node has seen, just accept it without
 345     // question....
 346     assert(Offset == 0 && !isArray() &&
 347            "Cannot have an offset into a void node!");
 348     Ty = NewTy;
 349     NodeType &= ~Array;
 350     if (WillBeArray) NodeType |= Array;
 351     Size = NewTySize;
 352
 353     // Calculate the number of outgoing links from this node.
 354     Links.resize((Size+DS::PointerSize-1) >> DS::PointerShift);
 355     return false;
 356   }
 357
 358   // Handle node expansion case here...
 359   if (Offset+NewTySize > Size) {
 360     // It is illegal to grow this node if we have treated it as an array of
 361     // objects...
 362     if (isArray()) {
 363       if (FoldIfIncompatible) foldNodeCompletely();
 364       return true;
 365     }
 366
 367     if (Offset) {  // We could handle this case, but we don't for now...
 368       std::cerr << "UNIMP: Trying to merge a growth type into "
 369                 << "offset != 0: Collapsing!\n";
 370       if (FoldIfIncompatible) foldNodeCompletely();
 371       return true;
 372     }
 373
 374     // Okay, the situation is nice and simple, we are trying to merge a type in
 375     // at offset 0 that is bigger than our current type.  Implement this by
 376     // switching to the new type and then merge in the smaller one, which should
 377     // hit the other code path here.  If the other code path decides it's not
 378     // ok, it will collapse the node as appropriate.
 379     //
 380     const Type *OldTy = Ty;
 381     Ty = NewTy;
 382     NodeType &= ~Array;
 383     if (WillBeArray) NodeType |= Array;
 384     Size = NewTySize;
 385
 386     // Must grow links to be the appropriate size...
 387     Links.resize((Size+DS::PointerSize-1) >> DS::PointerShift);
 388
 389     // Merge in the old type now... which is guaranteed to be smaller than the
 390     // "current" type.
 391     return mergeTypeInfo(OldTy, 0);
 392   }
 393
 394   assert(Offset <= Size &&
 395          "Cannot merge something into a part of our type that doesn't exist!");
 396
 397   // Find the section of Ty that NewTy overlaps with... first we find the
 398   // type that starts at offset Offset.
 399   //
 400   unsigned O = 0;
 401   const Type *SubType = Ty;
 402   while (O < Offset) {
 403     assert(Offset-O < TD.getTypeSize(SubType) && "Offset out of range!");
 404
 405     switch (SubType->getPrimitiveID()) {
 406     case Type::StructTyID: {
 407       const StructType *STy = cast<StructType>(SubType);
 408       const StructLayout &SL = *TD.getStructLayout(STy);
 409
 410       unsigned i = 0, e = SL.MemberOffsets.size();
 411       for (; i+1 < e && SL.MemberOffsets[i+1] <= Offset-O; ++i)
 412         /* empty */;
 413
 414       // The offset we are looking for must be in the i'th element...
 415       SubType = STy->getElementTypes()[i];
 416       O += SL.MemberOffsets[i];
 417       break;
 418     }
 419     case Type::ArrayTyID: {
 420       SubType = cast<ArrayType>(SubType)->getElementType();
 421       unsigned ElSize = TD.getTypeSize(SubType);
 422       unsigned Remainder = (Offset-O) % ElSize;
 423       O = Offset-Remainder;
 424       break;
 425     }
 426     default:
 427       if (FoldIfIncompatible) foldNodeCompletely();
 428       return true;
 429     }
 430   }
 431
 432   assert(O == Offset && "Could not achieve the correct offset!");
 433
 434   // If we found our type exactly, early exit
 435   if (SubType == NewTy) return false;
 436
 437   unsigned SubTypeSize = SubType->isSized() ? TD.getTypeSize(SubType) : 0;
 438
 439   // Ok, we are getting desperate now.  Check for physical subtyping, where we
 440   // just require each element in the node to be compatible.
 441   if (NewTySize <= SubTypeSize && NewTySize && NewTySize < 256 &&
 442       SubTypeSize && SubTypeSize < 256 &&
 443       ElementTypesAreCompatible(NewTy, SubType, !isArray(), TD))
 444     return false;
 445
 446   // Okay, so we found the leader type at the offset requested.  Search the list
 447   // of types that starts at this offset.  If SubType is currently an array or
 448   // structure, the type desired may actually be the first element of the
 449   // composite type...
 450   //
 451   unsigned PadSize = SubTypeSize; // Size, including pad memory which is ignored
 452   while (SubType != NewTy) {
 453     const Type *NextSubType = 0;
 454     unsigned NextSubTypeSize = 0;
 455     unsigned NextPadSize = 0;
 456     switch (SubType->getPrimitiveID()) {
 457     case Type::StructTyID: {
 458       const StructType *STy = cast<StructType>(SubType);
 459       const StructLayout &SL = *TD.getStructLayout(STy);
 460       if (SL.MemberOffsets.size() > 1)
 461         NextPadSize = SL.MemberOffsets[1];
 462       else
 463         NextPadSize = SubTypeSize;
 464       NextSubType = STy->getElementTypes()[0];
 465       NextSubTypeSize = TD.getTypeSize(NextSubType);
 466       break;
 467     }
 468     case Type::ArrayTyID:
 469       NextSubType = cast<ArrayType>(SubType)->getElementType();
 470       NextSubTypeSize = TD.getTypeSize(NextSubType);
 471       NextPadSize = NextSubTypeSize;
 472       break;
 473     default: ;
 474       // fall out
 475     }
 476
 477     if (NextSubType == 0)
 478       break;   // In the default case, break out of the loop
 479
 480     if (NextPadSize < NewTySize)
 481       break;   // Don't allow shrinking to a smaller type than NewTySize
 482     SubType = NextSubType;
 483     SubTypeSize = NextSubTypeSize;
 484     PadSize = NextPadSize;
 485   }
 486
 487   // If we found the type exactly, return it...
 488   if (SubType == NewTy)
 489     return false;
 490
 491   // Check to see if we have a compatible, but different type...
 492   if (NewTySize == SubTypeSize) {
 493     // Check to see if this type is obviously convertible... int -> uint f.e.
 494     if (NewTy->isLosslesslyConvertibleTo(SubType))
 495       return false;
 496
 497     // Check to see if we have a pointer & integer mismatch going on here,
 498     // loading a pointer as a long, for example.
 499     //
 500     if (SubType->isInteger() && isa<PointerType>(NewTy) ||
 501         NewTy->isInteger() && isa<PointerType>(SubType))
 502       return false;
 503   } else if (NewTySize > SubTypeSize && NewTySize <= PadSize) {
 504     // We are accessing the field, plus some structure padding.  Ignore the
 505     // structure padding.
 506     return false;
 507   }
 508
 509   Module *M = 0;
 510   if (getParentGraph()->getReturnNodes().size())
 511     M = getParentGraph()->getReturnNodes().begin()->first->getParent();
 512   DEBUG(std::cerr << "MergeTypeInfo Folding OrigTy: ";
 513         WriteTypeSymbolic(std::cerr, Ty, M) << "\n due to:";
 514         WriteTypeSymbolic(std::cerr, NewTy, M) << " @ " << Offset << "!\n"
 515                   << "SubType: ";
 516         WriteTypeSymbolic(std::cerr, SubType, M) << "\n\n");
 517
 518   if (FoldIfIncompatible) foldNodeCompletely();
 519   return true;
 520 }
 521
 522
 523
 524 // addEdgeTo - Add an edge from the current node to the specified node.  This
 525 // can cause merging of nodes in the graph.
 526 //
 527 void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) {
 528   if (NH.getNode() == 0) return;       // Nothing to do
 529
 530   DSNodeHandle &ExistingEdge = getLink(Offset);
 531   if (ExistingEdge.getNode()) {
 532     // Merge the two nodes...
 533     ExistingEdge.mergeWith(NH);
 534   } else {                             // No merging to perform...
 535     setLink(Offset, NH);               // Just force a link in there...
 536   }
 537 }
 538
 539
 540 // MergeSortedVectors - Efficiently merge a vector into another vector where
 541 // duplicates are not allowed and both are sorted.  This assumes that 'T's are
 542 // efficiently copyable and have sane comparison semantics.
 543 //
 544 static void MergeSortedVectors(std::vector<GlobalValue*> &Dest,
 545                                const std::vector<GlobalValue*> &Src) {
 546   // By far, the most common cases will be the simple ones.  In these cases,
 547   // avoid having to allocate a temporary vector...
 548   //
 549   if (Src.empty()) {             // Nothing to merge in...
 550     return;
 551   } else if (Dest.empty()) {     // Just copy the result in...
 552     Dest = Src;
 553   } else if (Src.size() == 1) {  // Insert a single element...
 554     const GlobalValue *V = Src[0];
 555     std::vector<GlobalValue*>::iterator I =
 556       std::lower_bound(Dest.begin(), Dest.end(), V);
 557     if (I == Dest.end() || *I != Src[0])  // If not already contained...
 558       Dest.insert(I, Src[0]);
 559   } else if (Dest.size() == 1) {
 560     GlobalValue *Tmp = Dest[0];           // Save value in temporary...
 561     Dest = Src;                           // Copy over list...
 562     std::vector<GlobalValue*>::iterator I =
 563       std::lower_bound(Dest.begin(), Dest.end(), Tmp);
 564     if (I == Dest.end() || *I != Tmp)     // If not already contained...
 565       Dest.insert(I, Tmp);
 566
 567   } else {
 568     // Make a copy to the side of Dest...
 569     std::vector<GlobalValue*> Old(Dest);
 570
 571     // Make space for all of the type entries now...
 572     Dest.resize(Dest.size()+Src.size());
 573
 574     // Merge the two sorted ranges together... into Dest.
 575     std::merge(Old.begin(), Old.end(), Src.begin(), Src.end(), Dest.begin());
 576
 577     // Now erase any duplicate entries that may have accumulated into the
 578     // vectors (because they were in both of the input sets)
 579     Dest.erase(std::unique(Dest.begin(), Dest.end()), Dest.end());
 580   }
 581 }
 582
 583
 584 // MergeNodes() - Helper function for DSNode::mergeWith().
 585 // This function does the hard work of merging two nodes, CurNodeH
 586 // and NH after filtering out trivial cases and making sure that
 587 // CurNodeH.offset >= NH.offset.
 588 //
 589 // ***WARNING***
 590 // Since merging may cause either node to go away, we must always
 591 // use the node-handles to refer to the nodes.  These node handles are
 592 // automatically updated during merging, so will always provide access
 593 // to the correct node after a merge.
 594 //
 595 void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) {
 596   assert(CurNodeH.getOffset() >= NH.getOffset() &&
 597          "This should have been enforced in the caller.");
 598
 599   // Now we know that Offset >= NH.Offset, so convert it so our "Offset" (with
 600   // respect to NH.Offset) is now zero.  NOffset is the distance from the base
 601   // of our object that N starts from.
 602   //
 603   unsigned NOffset = CurNodeH.getOffset()-NH.getOffset();
 604   unsigned NSize = NH.getNode()->getSize();
 605
 606   // If the two nodes are of different size, and the smaller node has the array
 607   // bit set, collapse!
 608   if (NSize != CurNodeH.getNode()->getSize()) {
 609     if (NSize < CurNodeH.getNode()->getSize()) {
 610       if (NH.getNode()->isArray())
 611         NH.getNode()->foldNodeCompletely();
 612     } else if (CurNodeH.getNode()->isArray()) {
 613       NH.getNode()->foldNodeCompletely();
 614     }
 615   }
 616
 617   // Merge the type entries of the two nodes together...
 618   if (NH.getNode()->Ty != Type::VoidTy)
 619     CurNodeH.getNode()->mergeTypeInfo(NH.getNode()->Ty, NOffset);
 620   assert(!CurNodeH.getNode()->isDeadNode());
 621
 622   // If we are merging a node with a completely folded node, then both nodes are
 623   // now completely folded.
 624   //
 625   if (CurNodeH.getNode()->isNodeCompletelyFolded()) {
 626     if (!NH.getNode()->isNodeCompletelyFolded()) {
 627       NH.getNode()->foldNodeCompletely();
 628       assert(NH.getNode() && NH.getOffset() == 0 &&
 629              "folding did not make offset 0?");
 630       NOffset = NH.getOffset();
 631       NSize = NH.getNode()->getSize();
 632       assert(NOffset == 0 && NSize == 1);
 633     }
 634   } else if (NH.getNode()->isNodeCompletelyFolded()) {
 635     CurNodeH.getNode()->foldNodeCompletely();
 636     assert(CurNodeH.getNode() && CurNodeH.getOffset() == 0 &&
 637            "folding did not make offset 0?");
 638     NOffset = NH.getOffset();
 639     NSize = NH.getNode()->getSize();
 640     assert(NOffset == 0 && NSize == 1);
 641   }
 642
 643   DSNode *N = NH.getNode();
 644   if (CurNodeH.getNode() == N || N == 0) return;
 645   assert(!CurNodeH.getNode()->isDeadNode());
 646
 647   // Merge the NodeType information...
 648   CurNodeH.getNode()->NodeType |= N->NodeType;
 649
 650   // Start forwarding to the new node!
 651   N->forwardNode(CurNodeH.getNode(), NOffset);
 652   assert(!CurNodeH.getNode()->isDeadNode());
 653
 654   // Make all of the outgoing links of N now be outgoing links of CurNodeH.
 655   //
 656   for (unsigned i = 0; i < N->getNumLinks(); ++i) {
 657     DSNodeHandle &Link = N->getLink(i << DS::PointerShift);
 658     if (Link.getNode()) {
 659       // Compute the offset into the current node at which to
 660       // merge this link.  In the common case, this is a linear
 661       // relation to the offset in the original node (with
 662       // wrapping), but if the current node gets collapsed due to
 663       // recursive merging, we must make sure to merge in all remaining
 664       // links at offset zero.
 665       unsigned MergeOffset = 0;
 666       DSNode *CN = CurNodeH.getNode();
 667       if (CN->Size != 1)
 668         MergeOffset = ((i << DS::PointerShift)+NOffset) % CN->getSize();
 669       CN->addEdgeTo(MergeOffset, Link);
 670     }
 671   }
 672
 673   // Now that there are no outgoing edges, all of the Links are dead.
 674   N->Links.clear();
 675
 676   // Merge the globals list...
 677   if (!N->Globals.empty()) {
 678     MergeSortedVectors(CurNodeH.getNode()->Globals, N->Globals);
 679
 680     // Delete the globals from the old node...
 681     std::vector<GlobalValue*>().swap(N->Globals);
 682   }
 683 }
 684
 685
 686 // mergeWith - Merge this node and the specified node, moving all links to and
 687 // from the argument node into the current node, deleting the node argument.
 688 // Offset indicates what offset the specified node is to be merged into the
 689 // current node.
 690 //
 691 // The specified node may be a null pointer (in which case, we update it to
 692 // point to this node).
 693 //
 694 void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) {
 695   DSNode *N = NH.getNode();
 696   if (N == this && NH.getOffset() == Offset)
 697     return;  // Noop
 698
 699   // If the RHS is a null node, make it point to this node!
 700   if (N == 0) {
 701     NH.mergeWith(DSNodeHandle(this, Offset));
 702     return;
 703   }
 704
 705   assert(!N->isDeadNode() && !isDeadNode());
 706   assert(!hasNoReferrers() && "Should not try to fold a useless node!");
 707
 708   if (N == this) {
 709     // We cannot merge two pieces of the same node together, collapse the node
 710     // completely.
 711     DEBUG(std::cerr << "Attempting to merge two chunks of"
 712                     << " the same node together!\n");
 713     foldNodeCompletely();
 714     return;
 715   }
 716
 717   // If both nodes are not at offset 0, make sure that we are merging the node
 718   // at an later offset into the node with the zero offset.
 719   //
 720   if (Offset < NH.getOffset()) {
 721     N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset());
 722     return;
 723   } else if (Offset == NH.getOffset() && getSize() < N->getSize()) {
 724     // If the offsets are the same, merge the smaller node into the bigger node
 725     N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset());
 726     return;
 727   }
 728
 729   // Ok, now we can merge the two nodes.  Use a static helper that works with
 730   // two node handles, since "this" may get merged away at intermediate steps.
 731   DSNodeHandle CurNodeH(this, Offset);
 732   DSNodeHandle NHCopy(NH);
 733   DSNode::MergeNodes(CurNodeH, NHCopy);
 734 }
 735
 736 //===----------------------------------------------------------------------===//
 737 // DSCallSite Implementation
 738 //===----------------------------------------------------------------------===//
 739
 740 // Define here to avoid including iOther.h and BasicBlock.h in DSGraph.h
 741 Function &DSCallSite::getCaller() const {
 742   return *Site.getInstruction()->getParent()->getParent();
 743 }
 744
 745
 746 //===----------------------------------------------------------------------===//
 747 // DSGraph Implementation
 748 //===----------------------------------------------------------------------===//
 749
 750 /// getFunctionNames - Return a space separated list of the name of the
 751 /// functions in this graph (if any)
 752 std::string DSGraph::getFunctionNames() const {
 753   switch (getReturnNodes().size()) {
 754   case 0: return "Globals graph";
 755   case 1: return getReturnNodes().begin()->first->getName();
 756   default:
 757     std::string Return;
 758     for (DSGraph::ReturnNodesTy::const_iterator I = getReturnNodes().begin();
 759          I != getReturnNodes().end(); ++I)
 760       Return += I->first->getName() + " ";
 761     Return.erase(Return.end()-1, Return.end());   // Remove last space character
 762     return Return;
 763   }
 764 }
 765
 766
 767 DSGraph::DSGraph(const DSGraph &G) : GlobalsGraph(0), TD(G.TD) {
 768   PrintAuxCalls = false;
 769   NodeMapTy NodeMap;
 770   cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
 771   InlinedGlobals.clear();               // clear set of "up-to-date" globals
 772 }
 773
 774 DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap)
 775   : GlobalsGraph(0), TD(G.TD) {
 776   PrintAuxCalls = false;
 777   cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
 778   InlinedGlobals.clear();               // clear set of "up-to-date" globals
 779 }
 780
 781 DSGraph::~DSGraph() {
 782   FunctionCalls.clear();
 783   AuxFunctionCalls.clear();
 784   InlinedGlobals.clear();
 785   ScalarMap.clear();
 786   ReturnNodes.clear();
 787
 788   // Drop all intra-node references, so that assertions don't fail...
 789   std::for_each(Nodes.begin(), Nodes.end(),
 790                 std::mem_fun(&DSNode::dropAllReferences));
 791
 792   // Delete all of the nodes themselves...
 793   std::for_each(Nodes.begin(), Nodes.end(), deleter<DSNode>);
 794 }
 795
 796 // dump - Allow inspection of graph in a debugger.
 797 void DSGraph::dump() const { print(std::cerr); }
 798
 799
 800 /// remapLinks - Change all of the Links in the current node according to the
 801 /// specified mapping.
 802 ///
 803 void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) {
 804   for (unsigned i = 0, e = Links.size(); i != e; ++i) {
 805     DSNodeHandle &H = OldNodeMap[Links[i].getNode()];
 806     Links[i].setNode(H.getNode());
 807     Links[i].setOffset(Links[i].getOffset()+H.getOffset());
 808   }
 809 }
 810
 811
 812 /// cloneReachableNodes - Clone all reachable nodes from *Node into the
 813 /// current graph.  This is a recursive function.  The map OldNodeMap is a
 814 /// map from the original nodes to their clones.
 815 ///
 816 void DSGraph::cloneReachableNodes(const DSNode*  Node,
 817                                   unsigned BitsToClear,
 818                                   NodeMapTy& OldNodeMap,
 819                                   NodeMapTy& CompletedNodeMap) {
 820   if (CompletedNodeMap.find(Node) != CompletedNodeMap.end())
 821     return;
 822
 823   DSNodeHandle& NH = OldNodeMap[Node];
 824   if (NH.getNode() != NULL)
 825     return;
 826
 827   // else Node has not yet been cloned: clone it and clear the specified bits
 828   NH = new DSNode(*Node, this);          // enters in OldNodeMap
 829   NH.getNode()->maskNodeTypes(~BitsToClear);
 830
 831   // now recursively clone nodes pointed to by this node
 832   for (unsigned i = 0, e = Node->getNumLinks(); i != e; ++i) {
 833     const DSNodeHandle &Link = Node->getLink(i << DS::PointerShift);
 834     if (const DSNode* nextNode = Link.getNode())
 835       cloneReachableNodes(nextNode, BitsToClear, OldNodeMap, CompletedNodeMap);
 836   }
 837 }
 838
 839 void DSGraph::cloneReachableSubgraph(const DSGraph& G,
 840                                      const hash_set<const DSNode*>& RootNodes,
 841                                      NodeMapTy& OldNodeMap,
 842                                      NodeMapTy& CompletedNodeMap,
 843                                      unsigned CloneFlags) {
 844   if (RootNodes.empty())
 845     return;
 846
 847   assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!");
 848   assert(&G != this && "Cannot clone graph into itself!");
 849   assert((*RootNodes.begin())->getParentGraph() == &G &&
 850          "Root nodes do not belong to this graph!");
 851
 852   // Remove alloca or mod/ref bits as specified...
 853   unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0)
 854     | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0)
 855     | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0);
 856   BitsToClear |= DSNode::DEAD;  // Clear dead flag...
 857
 858   // Clone all nodes reachable from each root node, using a recursive helper
 859   for (hash_set<const DSNode*>::const_iterator I = RootNodes.begin(),
 860          E = RootNodes.end(); I != E; ++I)
 861     cloneReachableNodes(*I, BitsToClear, OldNodeMap, CompletedNodeMap);
 862
 863   // Merge the map entries in OldNodeMap and CompletedNodeMap to remap links
 864   NodeMapTy MergedMap(OldNodeMap);
 865   MergedMap.insert(CompletedNodeMap.begin(), CompletedNodeMap.end());
 866
 867   // Rewrite the links in the newly created nodes (the nodes in OldNodeMap)
 868   // to point into the current graph.  MergedMap gives the full mapping.
 869   for (NodeMapTy::iterator I=OldNodeMap.begin(), E=OldNodeMap.end(); I!= E; ++I)
 870     I->second.getNode()->remapLinks(MergedMap);
 871
 872   // Now merge cloned global nodes with their copies in the current graph
 873   // Just look through OldNodeMap to find such nodes!
 874   for (NodeMapTy::iterator I=OldNodeMap.begin(), E=OldNodeMap.end(); I!= E; ++I)
 875     if (I->first->isGlobalNode()) {
 876       DSNodeHandle &GClone = I->second;
 877       assert(GClone.getNode() != NULL && "NULL node in OldNodeMap?");
 878       const std::vector<GlobalValue*> &Globals = I->first->getGlobals();
 879       for (unsigned gi = 0, ge = Globals.size(); gi != ge; ++gi) {
 880         DSNodeHandle &GH = ScalarMap[Globals[gi]];
 881         GH.mergeWith(GClone);
 882       }
 883     }
 884 }
 885
 886
 887 /// updateFromGlobalGraph - This function rematerializes global nodes and
 888 /// nodes reachable from them from the globals graph into the current graph.
 889 /// It invokes cloneReachableSubgraph, using the globals in the current graph
 890 /// as the roots.  It also uses the vector InlinedGlobals to avoid cloning and
 891 /// merging globals that are already up-to-date in the current graph.  In
 892 /// practice, in the TD pass, this is likely to be a large fraction of the
 893 /// live global nodes in each function (since most live nodes are likely to
 894 /// have been brought up-to-date in at _some_ caller or callee).
 895 ///
 896 void DSGraph::updateFromGlobalGraph() {
 897
 898   // Use a map to keep track of the mapping between nodes in the globals graph
 899   // and this graph for up-to-date global nodes, which do not need to be cloned.
 900   NodeMapTy CompletedMap;
 901
 902   // Put the live, non-up-to-date global nodes into a set and the up-to-date
 903   // ones in the map above, mapping node in GlobalsGraph to the up-to-date node.
 904   hash_set<const DSNode*> GlobalNodeSet;
 905   for (ScalarMapTy::const_iterator I = getScalarMap().begin(),
 906          E = getScalarMap().end(); I != E; ++I)
 907     if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
 908       DSNode* GNode = I->second.getNode();
 909       assert(GNode && "No node for live global in current Graph?");
 910       if (const DSNode* GGNode = GlobalsGraph->ScalarMap[GV].getNode())
 911         if (InlinedGlobals.count(GV) == 0) // GNode is not up-to-date
 912           GlobalNodeSet.insert(GGNode);
 913         else {                                       // GNode is up-to-date
 914           CompletedMap[GGNode] = I->second;
 915           assert(GGNode->getNumLinks() == GNode->getNumLinks() &&
 916                  "Links dont match in a node that is supposed to be up-to-date?"
 917                  "\nremapLinks() will not work if the links don't match!");
 918         }
 919     }
 920
 921   // Clone the subgraph reachable from the vector of nodes in GlobalNodes
 922   // and merge the cloned global nodes with the corresponding ones, if any.
 923   NodeMapTy OldNodeMap;
 924   cloneReachableSubgraph(*GlobalsGraph, GlobalNodeSet, OldNodeMap,CompletedMap);
 925
 926   // Merging global nodes leaves behind unused nodes: get rid of them now.
 927   OldNodeMap.clear();      // remove references before dead node cleanup
 928   CompletedMap.clear();    // remove references before dead node cleanup
 929   removeTriviallyDeadNodes();
 930 }
 931
 932 /// cloneInto - Clone the specified DSGraph into the current graph.  The
 933 /// translated ScalarMap for the old function is filled into the OldValMap
 934 /// member, and the translated ReturnNodes map is returned into ReturnNodes.
 935 ///
 936 /// The CloneFlags member controls various aspects of the cloning process.
 937 ///
 938 void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap,
 939                         ReturnNodesTy &OldReturnNodes, NodeMapTy &OldNodeMap,
 940                         unsigned CloneFlags) {
 941   TIME_REGION(X, "cloneInto");
 942   assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!");
 943   assert(&G != this && "Cannot clone graph into itself!");
 944
 945   unsigned FN = Nodes.size();           // First new node...
 946
 947   // Duplicate all of the nodes, populating the node map...
 948   Nodes.reserve(FN+G.Nodes.size());
 949
 950   // Remove alloca or mod/ref bits as specified...
 951   unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0)
 952     | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0)
 953     | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0);
 954   BitsToClear |= DSNode::DEAD;  // Clear dead flag...
 955   for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i) {
 956     DSNode *Old = G.Nodes[i];
 957     DSNode *New = new DSNode(*Old, this);
 958     New->maskNodeTypes(~BitsToClear);
 959     OldNodeMap[Old] = New;
 960   }
 961 #ifndef NDEBUG
 962   Timer::addPeakMemoryMeasurement();
 963 #endif
 964
 965   // Rewrite the links in the new nodes to point into the current graph now.
 966   for (unsigned i = FN, e = Nodes.size(); i != e; ++i)
 967     Nodes[i]->remapLinks(OldNodeMap);
 968
 969   { TIME_REGION(X, "cloneInto:scalars");
 970
 971   // Copy the scalar map... merging all of the global nodes...
 972   for (ScalarMapTy::const_iterator I = G.ScalarMap.begin(),
 973          E = G.ScalarMap.end(); I != E; ++I) {
 974     DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()];
 975     DSNodeHandle &H = OldValMap[I->first];
 976     H.mergeWith(DSNodeHandle(MappedNode.getNode(),
 977                              I->second.getOffset()+MappedNode.getOffset()));
 978
 979     // If this is a global, add the global to this fn or merge if already exists
 980     if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
 981       ScalarMap[GV].mergeWith(H);
 982       InlinedGlobals.insert(GV);
 983     }
 984   }
 985   }
 986
 987   if (!(CloneFlags & DontCloneCallNodes)) {
 988     // Copy the function calls list...
 989     unsigned FC = FunctionCalls.size();  // FirstCall
 990     FunctionCalls.reserve(FC+G.FunctionCalls.size());
 991     for (unsigned i = 0, ei = G.FunctionCalls.size(); i != ei; ++i)
 992       FunctionCalls.push_back(DSCallSite(G.FunctionCalls[i], OldNodeMap));
 993   }
 994
 995   if (!(CloneFlags & DontCloneAuxCallNodes)) {
 996     // Copy the auxiliary function calls list...
 997     unsigned FC = AuxFunctionCalls.size();  // FirstCall
 998     AuxFunctionCalls.reserve(FC+G.AuxFunctionCalls.size());
 999     for (unsigned i = 0, ei = G.AuxFunctionCalls.size(); i != ei; ++i)
1000       AuxFunctionCalls.push_back(DSCallSite(G.AuxFunctionCalls[i], OldNodeMap));
1001   }
1002
1003   // Map the return node pointers over...
1004   for (ReturnNodesTy::const_iterator I = G.getReturnNodes().begin(),
1005          E = G.getReturnNodes().end(); I != E; ++I) {
1006     const DSNodeHandle &Ret = I->second;
1007     DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()];
1008     OldReturnNodes.insert(std::make_pair(I->first,
1009                           DSNodeHandle(MappedRet.getNode(),
1010                                        MappedRet.getOffset()+Ret.getOffset())));
1011   }
1012 }
1013
1014 /// clonePartiallyInto - Clone the reachable subset of the specified DSGraph
1015 /// into the current graph, for the specified function.
1016 ///
1017 /// This differs from cloneInto in that it only clones nodes reachable from
1018 /// globals, call nodes, the scalars specified in ValBindings, and the return
1019 /// value of the specified function.  This method merges the the cloned
1020 /// version of the scalars and return value with the specified DSNodeHandles.
1021 ///
1022 /// On return, OldNodeMap contains a mapping from the original nodes to the
1023 /// newly cloned nodes, for the subset of nodes that were actually cloned.
1024 ///
1025 /// The CloneFlags member controls various aspects of the cloning process.
1026 ///
1027 void DSGraph::clonePartiallyInto(const DSGraph &G, Function &F,
1028                                  const DSNodeHandle &RetVal,
1029                                  const ScalarMapTy &ValBindings,
1030                                  NodeMapTy &OldNodeMap,
1031                                  unsigned CloneFlags) {
1032
1033   TIME_REGION(X, "clonePartiallyInto");
1034   assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!");
1035   assert(&G != this && "Cannot clone graph into itself!");
1036
1037   unsigned FN = Nodes.size();           // First new node...
1038
1039   /// FIXME: This currently clones the whole graph over, instead of doing it
1040   /// incrementally.  This could be sped up quite a bit further!
1041
1042   // Duplicate all of the nodes, populating the node map...
1043   Nodes.reserve(FN+G.Nodes.size());
1044
1045   // Remove alloca or mod/ref bits as specified...
1046   unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0)
1047     | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0)
1048     | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0);
1049   BitsToClear |= DSNode::DEAD;  // Clear dead flag...
1050
1051   GlobalSetTy ClonedGlobals;
1052   for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i) {
1053     DSNode *Old = G.Nodes[i];
1054     DSNode *New = new DSNode(*Old, this);
1055     New->maskNodeTypes(~BitsToClear);
1056     OldNodeMap[Old] = New;
1057
1058     ClonedGlobals.insert(New->getGlobals().begin(), New->getGlobals().end());
1059   }
1060 #ifndef NDEBUG
1061   Timer::addPeakMemoryMeasurement();
1062 #endif
1063
1064   // Rewrite the links in the new nodes to point into the current graph now.
1065   for (unsigned i = FN, e = Nodes.size(); i != e; ++i)
1066     Nodes[i]->remapLinks(OldNodeMap);
1067
1068   // Ensure that all global nodes end up in the scalar map, as appropriate.
1069   for (GlobalSetTy::iterator CI = ClonedGlobals.begin(),
1070          E = ClonedGlobals.end(); CI != E; ++CI) {
1071     const DSNodeHandle &NGH = G.ScalarMap.find(*CI)->second;
1072
1073     DSNodeHandle &MappedNode = OldNodeMap[NGH.getNode()];
1074     DSNodeHandle H(MappedNode.getNode(),NGH.getOffset()+MappedNode.getOffset());
1075     ScalarMap[*CI].mergeWith(H);
1076     InlinedGlobals.insert(*CI);
1077   }
1078
1079   // Merge the requested portion of the scalar map with the values specified.
1080   for (ScalarMapTy::const_iterator I = ValBindings.begin(),
1081          E = ValBindings.end(); I != E; ++I) {
1082     ScalarMapTy::const_iterator SMI = G.ScalarMap.find(I->first);
1083     assert(SMI != G.ScalarMap.end() && "Cannot map non-existant scalar!");
1084
1085     DSNodeHandle &MappedNode = OldNodeMap[SMI->second.getNode()];
1086     DSNodeHandle H(MappedNode.getNode(),
1087                    SMI->second.getOffset()+MappedNode.getOffset());
1088     H.mergeWith(I->second);
1089   }
1090
1091   // Map the return node pointer over.
1092   if (RetVal.getNode()) {
1093     const DSNodeHandle &Ret = G.getReturnNodeFor(F);
1094     DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()];
1095     DSNodeHandle H(MappedRet.getNode(),
1096                  MappedRet.getOffset()+Ret.getOffset());
1097     H.mergeWith(RetVal);
1098   }
1099
1100   // If requested, copy the calls or aux-calls lists.
1101   if (!(CloneFlags & DontCloneCallNodes)) {
1102     // Copy the function calls list...
1103     unsigned FC = FunctionCalls.size();  // FirstCall
1104     FunctionCalls.reserve(FC+G.FunctionCalls.size());
1105     for (unsigned i = 0, ei = G.FunctionCalls.size(); i != ei; ++i)
1106       FunctionCalls.push_back(DSCallSite(G.FunctionCalls[i], OldNodeMap));
1107   }
1108
1109   if (!(CloneFlags & DontCloneAuxCallNodes)) {
1110     // Copy the auxiliary function calls list...
1111     unsigned FC = AuxFunctionCalls.size();  // FirstCall
1112     AuxFunctionCalls.reserve(FC+G.AuxFunctionCalls.size());
1113     for (unsigned i = 0, ei = G.AuxFunctionCalls.size(); i != ei; ++i)
1114       AuxFunctionCalls.push_back(DSCallSite(G.AuxFunctionCalls[i], OldNodeMap));
1115   }
1116 }
1117
1118
1119
1120
1121 /// mergeInGraph - The method is used for merging graphs together.  If the
1122 /// argument graph is not *this, it makes a clone of the specified graph, then
1123 /// merges the nodes specified in the call site with the formal arguments in the
1124 /// graph.
1125 ///
1126 void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
1127                            const DSGraph &Graph, unsigned CloneFlags) {
1128   // If this is not a recursive call, clone the graph into this graph...
1129   if (&Graph != this) {
1130     // Clone the callee's graph into the current graph, keeping
1131     // track of where scalars in the old graph _used_ to point,
1132     // and of the new nodes matching nodes of the old graph.
1133     ScalarMapTy ValueBindings;
1134
1135     // Set up argument bindings
1136     Function::aiterator AI = F.abegin();
1137     for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) {
1138       // Advance the argument iterator to the first pointer argument...
1139       while (AI != F.aend() && !isPointerType(AI->getType())) {
1140         ++AI;
1141 #ifndef NDEBUG
1142         if (AI == F.aend())
1143           std::cerr << "Bad call to Function: " << F.getName() << "\n";
1144 #endif
1145       }
1146       if (AI == F.aend()) break;
1147
1148       // Add the link from the argument scalar to the provided value.
1149       ValueBindings[AI] = CS.getPtrArg(i);
1150     }
1151
1152     NodeMapTy OldNodeMap;
1153     clonePartiallyInto(Graph, F, CS.getRetVal(), ValueBindings, OldNodeMap,
1154                        CloneFlags);
1155
1156   } else {
1157     DSNodeHandle RetVal = getReturnNodeFor(F);
1158     ScalarMapTy &ScalarMap = getScalarMap();
1159
1160     // Merge the return value with the return value of the context...
1161     RetVal.mergeWith(CS.getRetVal());
1162
1163     // Resolve all of the function arguments...
1164     Function::aiterator AI = F.abegin();
1165
1166     for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) {
1167       // Advance the argument iterator to the first pointer argument...
1168       while (AI != F.aend() && !isPointerType(AI->getType())) {
1169         ++AI;
1170 #ifndef NDEBUG
1171         if (AI == F.aend())
1172           std::cerr << "Bad call to Function: " << F.getName() << "\n";
1173 #endif
1174       }
1175       if (AI == F.aend()) break;
1176
1177       // Add the link from the argument scalar to the provided value
1178       assert(ScalarMap.count(AI) && "Argument not in scalar map?");
1179       DSNodeHandle &NH = ScalarMap[AI];
1180       assert(NH.getNode() && "Pointer argument without scalarmap entry?");
1181       NH.mergeWith(CS.getPtrArg(i));
1182     }
1183   }
1184 }
1185
1186 /// getCallSiteForArguments - Get the arguments and return value bindings for
1187 /// the specified function in the current graph.
1188 ///
1189 DSCallSite DSGraph::getCallSiteForArguments(Function &F) const {
1190   std::vector<DSNodeHandle> Args;
1191
1192   for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
1193     if (isPointerType(I->getType()))
1194       Args.push_back(getScalarMap().find(I)->second);
1195
1196   return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args);
1197 }
1198
1199
1200
1201 // markIncompleteNodes - Mark the specified node as having contents that are not
1202 // known with the current analysis we have performed.  Because a node makes all
1203 // of the nodes it can reach incomplete if the node itself is incomplete, we
1204 // must recursively traverse the data structure graph, marking all reachable
1205 // nodes as incomplete.
1206 //
1207 static void markIncompleteNode(DSNode *N) {
1208   // Stop recursion if no node, or if node already marked...
1209   if (N == 0 || N->isIncomplete()) return;
1210
1211   // Actually mark the node
1212   N->setIncompleteMarker();
1213
1214   // Recursively process children...
1215   for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize)
1216     if (DSNode *DSN = N->getLink(i).getNode())
1217       markIncompleteNode(DSN);
1218 }
1219
1220 static void markIncomplete(DSCallSite &Call) {
1221   // Then the return value is certainly incomplete!
1222   markIncompleteNode(Call.getRetVal().getNode());
1223
1224   // All objects pointed to by function arguments are incomplete!
1225   for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i)
1226     markIncompleteNode(Call.getPtrArg(i).getNode());
1227 }
1228
1229 // markIncompleteNodes - Traverse the graph, identifying nodes that may be
1230 // modified by other functions that have not been resolved yet.  This marks
1231 // nodes that are reachable through three sources of "unknownness":
1232 //
1233 //  Global Variables, Function Calls, and Incoming Arguments
1234 //
1235 // For any node that may have unknown components (because something outside the
1236 // scope of current analysis may have modified it), the 'Incomplete' flag is
1237 // added to the NodeType.
1238 //
1239 void DSGraph::markIncompleteNodes(unsigned Flags) {
1240   // Mark any incoming arguments as incomplete...
1241   if (Flags & DSGraph::MarkFormalArgs)
1242     for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end();
1243          FI != E; ++FI) {
1244       Function &F = *FI->first;
1245       if (F.getName() != "main")
1246         for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
1247           if (isPointerType(I->getType()) &&
1248               ScalarMap.find(I) != ScalarMap.end())
1249             markIncompleteNode(ScalarMap[I].getNode());
1250     }
1251
1252   // Mark stuff passed into functions calls as being incomplete...
1253   if (!shouldPrintAuxCalls())
1254     for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i)
1255       markIncomplete(FunctionCalls[i]);
1256   else
1257     for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
1258       markIncomplete(AuxFunctionCalls[i]);
1259
1260
1261   // Mark all global nodes as incomplete...
1262   if ((Flags & DSGraph::IgnoreGlobals) == 0)
1263     for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
1264       if (Nodes[i]->isGlobalNode() && Nodes[i]->getNumLinks())
1265         markIncompleteNode(Nodes[i]);
1266 }
1267
1268 static inline void killIfUselessEdge(DSNodeHandle &Edge) {
1269   if (DSNode *N = Edge.getNode())  // Is there an edge?
1270     if (N->getNumReferrers() == 1)  // Does it point to a lonely node?
1271       // No interesting info?
1272       if ((N->getNodeFlags() & ~DSNode::Incomplete) == 0 &&
1273           N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded())
1274         Edge.setNode(0);  // Kill the edge!
1275 }
1276
1277 static inline bool nodeContainsExternalFunction(const DSNode *N) {
1278   const std::vector<GlobalValue*> &Globals = N->getGlobals();
1279   for (unsigned i = 0, e = Globals.size(); i != e; ++i)
1280     if (Globals[i]->isExternal())
1281       return true;
1282   return false;
1283 }
1284
1285 static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
1286
1287   // Remove trivially identical function calls
1288   unsigned NumFns = Calls.size();
1289   std::sort(Calls.begin(), Calls.end());  // Sort by callee as primary key!
1290
1291   // Scan the call list cleaning it up as necessary...
1292   DSNode   *LastCalleeNode = 0;
1293   Function *LastCalleeFunc = 0;
1294   unsigned NumDuplicateCalls = 0;
1295   bool LastCalleeContainsExternalFunction = false;
1296   for (unsigned i = 0; i != Calls.size(); ++i) {
1297     DSCallSite &CS = Calls[i];
1298
1299     // If the Callee is a useless edge, this must be an unreachable call site,
1300     // eliminate it.
1301     if (CS.isIndirectCall() && CS.getCalleeNode()->getNumReferrers() == 1 &&
1302         CS.getCalleeNode()->getNodeFlags() == 0) {  // No useful info?
1303       std::cerr << "WARNING: Useless call site found??\n";
1304       CS.swap(Calls.back());
1305       Calls.pop_back();
1306       --i;
1307     } else {
1308       // If the return value or any arguments point to a void node with no
1309       // information at all in it, and the call node is the only node to point
1310       // to it, remove the edge to the node (killing the node).
1311       //
1312       killIfUselessEdge(CS.getRetVal());
1313       for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
1314         killIfUselessEdge(CS.getPtrArg(a));
1315
1316       // If this call site calls the same function as the last call site, and if
1317       // the function pointer contains an external function, this node will
1318       // never be resolved.  Merge the arguments of the call node because no
1319       // information will be lost.
1320       //
1321       if ((CS.isDirectCall()   && CS.getCalleeFunc() == LastCalleeFunc) ||
1322           (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) {
1323         ++NumDuplicateCalls;
1324         if (NumDuplicateCalls == 1) {
1325           if (LastCalleeNode)
1326             LastCalleeContainsExternalFunction =
1327               nodeContainsExternalFunction(LastCalleeNode);
1328           else
1329             LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal();
1330         }
1331
1332 #if 1
1333         if (LastCalleeContainsExternalFunction ||
1334             // This should be more than enough context sensitivity!
1335             // FIXME: Evaluate how many times this is tripped!
1336             NumDuplicateCalls > 20) {
1337           DSCallSite &OCS = Calls[i-1];
1338           OCS.mergeWith(CS);
1339
1340           // The node will now be eliminated as a duplicate!
1341           if (CS.getNumPtrArgs() < OCS.getNumPtrArgs())
1342             CS = OCS;
1343           else if (CS.getNumPtrArgs() > OCS.getNumPtrArgs())
1344             OCS = CS;
1345         }
1346 #endif
1347       } else {
1348         if (CS.isDirectCall()) {
1349           LastCalleeFunc = CS.getCalleeFunc();
1350           LastCalleeNode = 0;
1351         } else {
1352           LastCalleeNode = CS.getCalleeNode();
1353           LastCalleeFunc = 0;
1354         }
1355         NumDuplicateCalls = 0;
1356       }
1357     }
1358   }
1359
1360   Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end());
1361
1362   // Track the number of call nodes merged away...
1363   NumCallNodesMerged += NumFns-Calls.size();
1364
1365   DEBUG(if (NumFns != Calls.size())
1366           std::cerr << "Merged " << (NumFns-Calls.size()) << " call nodes.\n";);
1367 }
1368
1369
1370 // removeTriviallyDeadNodes - After the graph has been constructed, this method
1371 // removes all unreachable nodes that are created because they got merged with
1372 // other nodes in the graph.  These nodes will all be trivially unreachable, so
1373 // we don't have to perform any non-trivial analysis here.
1374 //
1375 void DSGraph::removeTriviallyDeadNodes() {
1376   TIME_REGION(X, "removeTriviallyDeadNodes");
1377
1378   removeIdenticalCalls(FunctionCalls);
1379   removeIdenticalCalls(AuxFunctionCalls);
1380
1381   // Loop over all of the nodes in the graph, calling getNode on each field.
1382   // This will cause all nodes to update their forwarding edges, causing
1383   // forwarded nodes to be delete-able.
1384   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
1385     DSNode *N = Nodes[i];
1386     for (unsigned l = 0, e = N->getNumLinks(); l != e; ++l)
1387       N->getLink(l*N->getPointerSize()).getNode();
1388   }
1389
1390   // Likewise, forward any edges from the scalar nodes.  While we are at it,
1391   // clean house a bit.
1392   for (ScalarMapTy::iterator I = ScalarMap.begin(),E = ScalarMap.end();I != E;){
1393     // Check to see if this is a worthless node generated for non-pointer
1394     // values, such as integers.  Consider an addition of long types: A+B.
1395     // Assuming we can track all uses of the value in this context, and it is
1396     // NOT used as a pointer, we can delete the node.  We will be able to detect
1397     // this situation if the node pointed to ONLY has Unknown bit set in the
1398     // node.  In this case, the node is not incomplete, does not point to any
1399     // other nodes (no mod/ref bits set), and is therefore uninteresting for
1400     // data structure analysis.  If we run across one of these, prune the scalar
1401     // pointing to it.
1402     //
1403     DSNode *N = I->second.getNode();
1404     if (N->getNodeFlags() == DSNode::UnknownNode && !isa<Argument>(I->first))
1405       ScalarMap.erase(I++);
1406     else
1407       ++I;
1408   }
1409
1410   bool isGlobalsGraph = !GlobalsGraph;
1411
1412   for (unsigned i = 0; i != Nodes.size(); ++i) {
1413     DSNode *Node = Nodes[i];
1414
1415     // Do not remove *any* global nodes in the globals graph.
1416     // This is a special case because such nodes may not have I, M, R flags set.
1417     if (Node->isGlobalNode() && isGlobalsGraph)
1418       continue;
1419
1420     if (Node->isComplete() && !Node->isModified() && !Node->isRead()) {
1421       // This is a useless node if it has no mod/ref info (checked above),
1422       // outgoing edges (which it cannot, as it is not modified in this
1423       // context), and it has no incoming edges.  If it is a global node it may
1424       // have all of these properties and still have incoming edges, due to the
1425       // scalar map, so we check those now.
1426       //
1427       if (Node->getNumReferrers() == Node->getGlobals().size()) {
1428         const std::vector<GlobalValue*> &Globals = Node->getGlobals();
1429
1430         // Loop through and make sure all of the globals are referring directly
1431         // to the node...
1432         for (unsigned j = 0, e = Globals.size(); j != e; ++j) {
1433           DSNode *N = ScalarMap.find(Globals[j])->second.getNode();
1434           assert(N == Node && "ScalarMap doesn't match globals list!");
1435         }
1436
1437         // Make sure NumReferrers still agrees, if so, the node is truly dead.
1438         if (Node->getNumReferrers() == Globals.size()) {
1439           for (unsigned j = 0, e = Globals.size(); j != e; ++j)
1440             ScalarMap.erase(Globals[j]);
1441           Node->makeNodeDead();
1442         }
1443       }
1444
1445 #ifdef SANER_CODE_FOR_CHECKING_IF_ALL_REFERRERS_ARE_FROM_SCALARMAP
1446       //
1447       // *** It seems to me that we should be able to simply check if
1448       // *** there are fewer or equal #referrers as #globals and make
1449       // *** sure that all those referrers are in the scalar map?
1450       //
1451       if (Node->getNumReferrers() <= Node->getGlobals().size()) {
1452         const std::vector<GlobalValue*> &Globals = Node->getGlobals();
1453
1454 #ifndef NDEBUG
1455         // Loop through and make sure all of the globals are referring directly
1456         // to the node...
1457         for (unsigned j = 0, e = Globals.size(); j != e; ++j) {
1458           DSNode *N = ScalarMap.find(Globals[j])->second.getNode();
1459           assert(N == Node && "ScalarMap doesn't match globals list!");
1460         }
1461 #endif
1462
1463         // Make sure NumReferrers still agrees.  The node is truly dead.
1464         assert(Node->getNumReferrers() == Globals.size());
1465         for (unsigned j = 0, e = Globals.size(); j != e; ++j)
1466           ScalarMap.erase(Globals[j]);
1467         Node->makeNodeDead();
1468       }
1469 #endif
1470     }
1471
1472     if (Node->getNodeFlags() == 0 && Node->hasNoReferrers()) {
1473       // This node is dead!
1474       delete Node;                        // Free memory...
1475       Nodes[i--] = Nodes.back();
1476       Nodes.pop_back();                   // Remove from node list...
1477     }
1478   }
1479 }
1480
1481
1482 /// markReachableNodes - This method recursively traverses the specified
1483 /// DSNodes, marking any nodes which are reachable.  All reachable nodes it adds
1484 /// to the set, which allows it to only traverse visited nodes once.
1485 ///
1486 void DSNode::markReachableNodes(hash_set<DSNode*> &ReachableNodes) {
1487   if (this == 0) return;
1488   assert(getForwardNode() == 0 && "Cannot mark a forwarded node!");
1489   if (ReachableNodes.insert(this).second)        // Is newly reachable?
1490     for (unsigned i = 0, e = getSize(); i < e; i += DS::PointerSize)
1491       getLink(i).getNode()->markReachableNodes(ReachableNodes);
1492 }
1493
1494 void DSCallSite::markReachableNodes(hash_set<DSNode*> &Nodes) {
1495   getRetVal().getNode()->markReachableNodes(Nodes);
1496   if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes);
1497
1498   for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i)
1499     getPtrArg(i).getNode()->markReachableNodes(Nodes);
1500 }
1501
1502 // CanReachAliveNodes - Simple graph walker that recursively traverses the graph
1503 // looking for a node that is marked alive.  If an alive node is found, return
1504 // true, otherwise return false.  If an alive node is reachable, this node is
1505 // marked as alive...
1506 //
1507 static bool CanReachAliveNodes(DSNode *N, hash_set<DSNode*> &Alive,
1508                                hash_set<DSNode*> &Visited,
1509                                bool IgnoreGlobals) {
1510   if (N == 0) return false;
1511   assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!");
1512
1513   // If this is a global node, it will end up in the globals graph anyway, so we
1514   // don't need to worry about it.
1515   if (IgnoreGlobals && N->isGlobalNode()) return false;
1516
1517   // If we know that this node is alive, return so!
1518   if (Alive.count(N)) return true;
1519
1520   // Otherwise, we don't think the node is alive yet, check for infinite
1521   // recursion.
1522   if (Visited.count(N)) return false;  // Found a cycle
1523   Visited.insert(N);   // No recursion, insert into Visited...
1524
1525   for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize)
1526     if (CanReachAliveNodes(N->getLink(i).getNode(), Alive, Visited,
1527                            IgnoreGlobals)) {
1528       N->markReachableNodes(Alive);
1529       return true;
1530     }
1531   return false;
1532 }
1533
1534 // CallSiteUsesAliveArgs - Return true if the specified call site can reach any
1535 // alive nodes.
1536 //
1537 static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set<DSNode*> &Alive,
1538                                   hash_set<DSNode*> &Visited,
1539                                   bool IgnoreGlobals) {
1540   if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited,
1541                          IgnoreGlobals))
1542     return true;
1543   if (CS.isIndirectCall() &&
1544       CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited, IgnoreGlobals))
1545     return true;
1546   for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
1547     if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited,
1548                            IgnoreGlobals))
1549       return true;
1550   return false;
1551 }
1552
1553 // removeDeadNodes - Use a more powerful reachability analysis to eliminate
1554 // subgraphs that are unreachable.  This often occurs because the data
1555 // structure doesn't "escape" into it's caller, and thus should be eliminated
1556 // from the caller's graph entirely.  This is only appropriate to use when
1557 // inlining graphs.
1558 //
1559 void DSGraph::removeDeadNodes(unsigned Flags) {
1560   DEBUG(AssertGraphOK(); if (GlobalsGraph) GlobalsGraph->AssertGraphOK());
1561
1562   // Reduce the amount of work we have to do... remove dummy nodes left over by
1563   // merging...
1564   removeTriviallyDeadNodes();
1565
1566   TIME_REGION(X, "removeDeadNodes");
1567
1568   // FIXME: Merge non-trivially identical call nodes...
1569
1570   // Alive - a set that holds all nodes found to be reachable/alive.
1571   hash_set<DSNode*> Alive;
1572   std::vector<std::pair<Value*, DSNode*> > GlobalNodes;
1573
1574   // Mark all nodes reachable by (non-global) scalar nodes as alive...
1575   for (ScalarMapTy::iterator I = ScalarMap.begin(), E = ScalarMap.end(); I != E;
1576        ++I)
1577     if (isa<GlobalValue>(I->first)) {             // Keep track of global nodes
1578       assert(I->second.getNode() && "Null global node?");
1579       assert(I->second.getNode()->isGlobalNode() && "Should be a global node!");
1580       GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode()));
1581     } else {
1582       I->second.getNode()->markReachableNodes(Alive);
1583     }
1584
1585   // The return value is alive as well...
1586   for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end();
1587        I != E; ++I)
1588     I->second.getNode()->markReachableNodes(Alive);
1589
1590   // Mark any nodes reachable by primary calls as alive...
1591   for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i)
1592     FunctionCalls[i].markReachableNodes(Alive);
1593
1594   // Copy and merge all information about globals to the GlobalsGraph
1595   // if this is not a final pass (where unreachable globals are removed)
1596   NodeMapTy GlobalNodeMap;
1597   hash_set<const DSNode*> GlobalNodeSet;
1598
1599   for (std::vector<std::pair<Value*, DSNode*> >::const_iterator
1600          I = GlobalNodes.begin(), E = GlobalNodes.end(); I != E; ++I)
1601     GlobalNodeSet.insert(I->second);    // put global nodes into a set
1602
1603   // Now find globals and aux call nodes that are already live or reach a live
1604   // value (which makes them live in turn), and continue till no more are found.
1605   //
1606   bool Iterate;
1607   hash_set<DSNode*> Visited;
1608   std::vector<unsigned char> AuxFCallsAlive(AuxFunctionCalls.size());
1609   do {
1610     Visited.clear();
1611     // If any global node points to a non-global that is "alive", the global is
1612     // "alive" as well...  Remove it from the GlobalNodes list so we only have
1613     // unreachable globals in the list.
1614     //
1615     Iterate = false;
1616     if (!(Flags & DSGraph::RemoveUnreachableGlobals))
1617        for (unsigned i = 0; i != GlobalNodes.size(); ++i)
1618          if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited,
1619                                 Flags & DSGraph::RemoveUnreachableGlobals)) {
1620            std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to...
1621            GlobalNodes.pop_back();                          // erase efficiently
1622            Iterate = true;
1623          }
1624
1625     // Mark only unresolvable call nodes for moving to the GlobalsGraph since
1626     // call nodes that get resolved will be difficult to remove from that graph.
1627     // The final unresolved call nodes must be handled specially at the end of
1628     // the BU pass (i.e., in main or other roots of the call graph).
1629     for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
1630       if (!AuxFCallsAlive[i] &&
1631           (AuxFunctionCalls[i].isIndirectCall()
1632            || CallSiteUsesAliveArgs(AuxFunctionCalls[i], Alive, Visited,
1633                                   Flags & DSGraph::RemoveUnreachableGlobals))) {
1634         AuxFunctionCalls[i].markReachableNodes(Alive);
1635         AuxFCallsAlive[i] = true;
1636         Iterate = true;
1637       }
1638   } while (Iterate);
1639
1640   // Move dead aux function calls to the end of the list
1641   unsigned CurIdx = 0;
1642   for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
1643     if (AuxFCallsAlive[i])
1644       AuxFunctionCalls[CurIdx++].swap(AuxFunctionCalls[i]);
1645
1646   // Copy and merge all global nodes and dead aux call nodes into the
1647   // GlobalsGraph, and all nodes reachable from those nodes
1648   //
1649   if (!(Flags & DSGraph::RemoveUnreachableGlobals)) {
1650
1651     // First, add the dead aux call nodes to the set of root nodes for cloning
1652     // -- return value at this call site, if any
1653     // -- actual arguments passed at this call site
1654     // -- callee node at this call site, if this is an indirect call
1655     for (unsigned i = CurIdx, e = AuxFunctionCalls.size(); i != e; ++i) {
1656       if (const DSNode* RetNode = AuxFunctionCalls[i].getRetVal().getNode())
1657         GlobalNodeSet.insert(RetNode);
1658       for (unsigned j=0, N=AuxFunctionCalls[i].getNumPtrArgs(); j < N; ++j)
1659         if (const DSNode* ArgTarget=AuxFunctionCalls[i].getPtrArg(j).getNode())
1660           GlobalNodeSet.insert(ArgTarget);
1661       if (AuxFunctionCalls[i].isIndirectCall())
1662         GlobalNodeSet.insert(AuxFunctionCalls[i].getCalleeNode());
1663     }
1664
1665     // There are no "pre-completed" nodes so use any empty map for those.
1666     // Strip all alloca bits since the current function is only for the BU pass.
1667     // Strip all incomplete bits since they are short-lived properties and they
1668     // will be correctly computed when rematerializing nodes into the functions.
1669     //
1670     NodeMapTy CompletedMap;
1671     GlobalsGraph->cloneReachableSubgraph(*this, GlobalNodeSet,
1672                                          GlobalNodeMap, CompletedMap,
1673                                          (DSGraph::StripAllocaBit |
1674                                           DSGraph::StripIncompleteBit));
1675   }
1676
1677   // Remove all dead aux function calls...
1678   if (!(Flags & DSGraph::RemoveUnreachableGlobals)) {
1679     assert(GlobalsGraph && "No globals graph available??");
1680
1681     // Copy the unreachable call nodes to the globals graph, updating
1682     // their target pointers using the GlobalNodeMap
1683     for (unsigned i = CurIdx, e = AuxFunctionCalls.size(); i != e; ++i)
1684       GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(AuxFunctionCalls[i],
1685                                                           GlobalNodeMap));
1686   }
1687   // Crop all the useless ones out...
1688   AuxFunctionCalls.erase(AuxFunctionCalls.begin()+CurIdx,
1689                          AuxFunctionCalls.end());
1690
1691   // We are finally done with the GlobalNodeMap so we can clear it and
1692   // then get rid of unused nodes in the GlobalsGraph produced by merging.
1693   GlobalNodeMap.clear();
1694   GlobalsGraph->removeTriviallyDeadNodes();
1695
1696   // At this point, any nodes which are visited, but not alive, are nodes
1697   // which can be removed.  Loop over all nodes, eliminating completely
1698   // unreachable nodes.
1699   //
1700   std::vector<DSNode*> DeadNodes;
1701   DeadNodes.reserve(Nodes.size());
1702   for (unsigned i = 0; i != Nodes.size(); ++i)
1703     if (!Alive.count(Nodes[i])) {
1704       DSNode *N = Nodes[i];
1705       Nodes[i--] = Nodes.back();            // move node to end of vector
1706       Nodes.pop_back();                     // Erase node from alive list.
1707       DeadNodes.push_back(N);
1708       N->dropAllReferences();
1709     } else {
1710       assert(Nodes[i]->getForwardNode() == 0 && "Alive forwarded node?");
1711     }
1712
1713   // Remove all unreachable globals from the ScalarMap.
1714   // If flag RemoveUnreachableGlobals is set, GlobalNodes has only dead nodes.
1715   // In either case, the dead nodes will not be in the set Alive.
1716   for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) {
1717     assert(((Flags & DSGraph::RemoveUnreachableGlobals) ||
1718             !Alive.count(GlobalNodes[i].second)) && "huh? non-dead global");
1719     if (!Alive.count(GlobalNodes[i].second))
1720       ScalarMap.erase(GlobalNodes[i].first);
1721   }
1722
1723   // Delete all dead nodes now since their referrer counts are zero.
1724   for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i)
1725     delete DeadNodes[i];
1726
1727   DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK());
1728 }
1729
1730 void DSGraph::AssertGraphOK() const {
1731   for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
1732     Nodes[i]->assertOK();
1733
1734   for (ScalarMapTy::const_iterator I = ScalarMap.begin(),
1735          E = ScalarMap.end(); I != E; ++I) {
1736     assert(I->second.getNode() && "Null node in scalarmap!");
1737     AssertNodeInGraph(I->second.getNode());
1738     if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) {
1739       assert(I->second.getNode()->isGlobalNode() &&
1740              "Global points to node, but node isn't global?");
1741       AssertNodeContainsGlobal(I->second.getNode(), GV);
1742     }
1743   }
1744   AssertCallNodesInGraph();
1745   AssertAuxCallNodesInGraph();
1746 }
1747
1748 /// mergeInGlobalsGraph - This method is useful for clients to incorporate the
1749 /// globals graph into the DS, BU or TD graph for a function.  This code retains
1750 /// all globals, i.e., does not delete unreachable globals after they are
1751 /// inlined.
1752 ///
1753 void DSGraph::mergeInGlobalsGraph() {
1754   NodeMapTy GlobalNodeMap;
1755   ScalarMapTy OldValMap;
1756   ReturnNodesTy OldRetNodes;
1757   cloneInto(*GlobalsGraph, OldValMap, OldRetNodes, GlobalNodeMap,
1758             DSGraph::KeepAllocaBit | DSGraph::DontCloneCallNodes |
1759             DSGraph::DontCloneAuxCallNodes);
1760
1761   // Now merge existing global nodes in the GlobalsGraph with their copies
1762   for (ScalarMapTy::iterator I = ScalarMap.begin(), E = ScalarMap.end();
1763        I != E; ++I)
1764     if (isa<GlobalValue>(I->first)) {             // Found a global node
1765       DSNodeHandle &GH = I->second;
1766       DSNodeHandle &GGNodeH = GlobalsGraph->getScalarMap()[I->first];
1767       GH.mergeWith(GlobalNodeMap[GGNodeH.getNode()]);
1768     }
1769
1770   // Merging leaves behind unused nodes: get rid of them now.
1771   GlobalNodeMap.clear();
1772   OldValMap.clear();
1773   OldRetNodes.clear();
1774   removeTriviallyDeadNodes();
1775 }
1776
1777
1778 /// computeNodeMapping - Given roots in two different DSGraphs, traverse the
1779 /// nodes reachable from the two graphs, computing the mapping of nodes from
1780 /// the first to the second graph.
1781 ///
1782 void DSGraph::computeNodeMapping(const DSNodeHandle &NH1,
1783                                  const DSNodeHandle &NH2, NodeMapTy &NodeMap,
1784                                  bool StrictChecking) {
1785   DSNode *N1 = NH1.getNode(), *N2 = NH2.getNode();
1786   if (N1 == 0 || N2 == 0) return;
1787
1788   DSNodeHandle &Entry = NodeMap[N1];
1789   if (Entry.getNode()) {
1790     // Termination of recursion!
1791     assert(!StrictChecking ||
1792            (Entry.getNode() == N2 &&
1793             Entry.getOffset() == (NH2.getOffset()-NH1.getOffset())) &&
1794            "Inconsistent mapping detected!");
1795     return;
1796   }
1797
1798   Entry.setNode(N2);
1799   Entry.setOffset(NH2.getOffset()-NH1.getOffset());
1800
1801   // Loop over all of the fields that N1 and N2 have in common, recursively
1802   // mapping the edges together now.
1803   int N2Idx = NH2.getOffset()-NH1.getOffset();
1804   unsigned N2Size = N2->getSize();
1805   for (unsigned i = 0, e = N1->getSize(); i < e; i += DS::PointerSize)
1806     if (unsigned(N2Idx)+i < N2Size)
1807       computeNodeMapping(N1->getLink(i), N2->getLink(N2Idx+i), NodeMap);
1808 }