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/DataStructure/DSGraphTraits.h"
  15 #include "llvm/Constants.h"
  16 #include "llvm/Function.h"
  17 #include "llvm/GlobalVariable.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/DerivedTypes.h"
  20 #include "llvm/Target/TargetData.h"
  21 #include "llvm/Assembly/Writer.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/ADT/DepthFirstIterator.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/ADT/SCCIterator.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/Support/Timer.h"
  29 #include <algorithm>
  30 using namespace llvm;
  31
  32 #define COLLAPSE_ARRAYS_AGGRESSIVELY 0
  33
  34 namespace {
  35   Statistic NumFolds          ("dsa", "Number of nodes completely folded");
  36   Statistic NumCallNodesMerged("dsa", "Number of call nodes merged");
  37   Statistic NumNodeAllocated  ("dsa", "Number of nodes allocated");
  38   Statistic NumDNE            ("dsa", "Number of nodes removed by reachability");
  39   Statistic NumTrivialDNE     ("dsa", "Number of nodes trivially removed");
  40   Statistic NumTrivialGlobalDNE("dsa", "Number of globals trivially removed");
  41   static cl::opt<unsigned>
  42   DSAFieldLimit("dsa-field-limit", cl::Hidden,
  43                 cl::desc("Number of fields to track before collapsing a node"),
  44                 cl::init(256));
  45 }
  46
  47 #if 0
  48 #define TIME_REGION(VARNAME, DESC) \
  49    NamedRegionTimer VARNAME(DESC)
  50 #else
  51 #define TIME_REGION(VARNAME, DESC)
  52 #endif
  53
  54 using namespace DS;
  55
  56 /// isForwarding - Return true if this NodeHandle is forwarding to another
  57 /// one.
  58 bool DSNodeHandle::isForwarding() const {
  59   return N && N->isForwarding();
  60 }
  61
  62 DSNode *DSNodeHandle::HandleForwarding() const {
  63   assert(N->isForwarding() && "Can only be invoked if forwarding!");
  64   DEBUG(
  65         { //assert not looping
  66           DSNode* NH = N;
  67           std::set<DSNode*> seen;
  68           while(NH && NH->isForwarding()) {
  69             assert(seen.find(NH) == seen.end() && "Loop detected");
  70             seen.insert(NH);
  71             NH = NH->ForwardNH.N;
  72           }
  73         }
  74         );
  75   // Handle node forwarding here!
  76   DSNode *Next = N->ForwardNH.getNode();  // Cause recursive shrinkage
  77   Offset += N->ForwardNH.getOffset();
  78
  79   if (--N->NumReferrers == 0) {
  80     // Removing the last referrer to the node, sever the forwarding link
  81     N->stopForwarding();
  82   }
  83
  84   N = Next;
  85   N->NumReferrers++;
  86   if (N->Size <= Offset) {
  87     assert(N->Size <= 1 && "Forwarded to shrunk but not collapsed node?");
  88     Offset = 0;
  89   }
  90   return N;
  91 }
  92
  93 //===----------------------------------------------------------------------===//
  94 // DSScalarMap Implementation
  95 //===----------------------------------------------------------------------===//
  96
  97 DSNodeHandle &DSScalarMap::AddGlobal(GlobalValue *GV) {
  98   assert(ValueMap.count(GV) == 0 && "GV already exists!");
  99
 100   // If the node doesn't exist, check to see if it's a global that is
 101   // equated to another global in the program.
 102   EquivalenceClasses<GlobalValue*>::iterator ECI = GlobalECs.findValue(GV);
 103   if (ECI != GlobalECs.end()) {
 104     GlobalValue *Leader = *GlobalECs.findLeader(ECI);
 105     if (Leader != GV) {
 106       GV = Leader;
 107       iterator I = ValueMap.find(GV);
 108       if (I != ValueMap.end())
 109         return I->second;
 110     }
 111   }
 112
 113   // Okay, this is either not an equivalenced global or it is the leader, it
 114   // will be inserted into the scalar map now.
 115   GlobalSet.insert(GV);
 116
 117   return ValueMap.insert(std::make_pair(GV, DSNodeHandle())).first->second;
 118 }
 119
 120
 121 //===----------------------------------------------------------------------===//
 122 // DSNode Implementation
 123 //===----------------------------------------------------------------------===//
 124
 125 DSNode::DSNode(const Type *T, DSGraph *G)
 126   : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(0) {
 127   // Add the type entry if it is specified...
 128   if (T) mergeTypeInfo(T, 0);
 129   if (G) G->addNode(this);
 130   ++NumNodeAllocated;
 131 }
 132
 133 // DSNode copy constructor... do not copy over the referrers list!
 134 DSNode::DSNode(const DSNode &N, DSGraph *G, bool NullLinks)
 135   : NumReferrers(0), Size(N.Size), ParentGraph(G),
 136     Ty(N.Ty), Globals(N.Globals), NodeType(N.NodeType) {
 137   if (!NullLinks) {
 138     Links = N.Links;
 139   } else
 140     Links.resize(N.Links.size()); // Create the appropriate number of null links
 141   G->addNode(this);
 142   ++NumNodeAllocated;
 143 }
 144
 145 /// getTargetData - Get the target data object used to construct this node.
 146 ///
 147 const TargetData &DSNode::getTargetData() const {
 148   return ParentGraph->getTargetData();
 149 }
 150
 151 void DSNode::assertOK() const {
 152   assert((Ty != Type::VoidTy ||
 153           Ty == Type::VoidTy && (Size == 0 ||
 154                                  (NodeType & DSNode::Array))) &&
 155          "Node not OK!");
 156
 157   assert(ParentGraph && "Node has no parent?");
 158   const DSScalarMap &SM = ParentGraph->getScalarMap();
 159   for (unsigned i = 0, e = Globals.size(); i != e; ++i) {
 160     assert(SM.global_count(Globals[i]));
 161     assert(SM.find(Globals[i])->second.getNode() == this);
 162   }
 163 }
 164
 165 /// forwardNode - Mark this node as being obsolete, and all references to it
 166 /// should be forwarded to the specified node and offset.
 167 ///
 168 void DSNode::forwardNode(DSNode *To, unsigned Offset) {
 169   assert(this != To && "Cannot forward a node to itself!");
 170   assert(ForwardNH.isNull() && "Already forwarding from this node!");
 171   if (To->Size <= 1) Offset = 0;
 172   assert((Offset < To->Size || (Offset == To->Size && Offset == 0)) &&
 173          "Forwarded offset is wrong!");
 174   ForwardNH.setTo(To, Offset);
 175   NodeType = DEAD;
 176   Size = 0;
 177   Ty = Type::VoidTy;
 178
 179   // Remove this node from the parent graph's Nodes list.
 180   ParentGraph->unlinkNode(this);
 181   ParentGraph = 0;
 182 }
 183
 184 // addGlobal - Add an entry for a global value to the Globals list.  This also
 185 // marks the node with the 'G' flag if it does not already have it.
 186 //
 187 void DSNode::addGlobal(GlobalValue *GV) {
 188   // First, check to make sure this is the leader if the global is in an
 189   // equivalence class.
 190   GV = getParentGraph()->getScalarMap().getLeaderForGlobal(GV);
 191
 192   // Keep the list sorted.
 193   std::vector<GlobalValue*>::iterator I =
 194     std::lower_bound(Globals.begin(), Globals.end(), GV);
 195
 196   if (I == Globals.end() || *I != GV) {
 197     Globals.insert(I, GV);
 198     NodeType |= GlobalNode;
 199   }
 200 }
 201
 202 // removeGlobal - Remove the specified global that is explicitly in the globals
 203 // list.
 204 void DSNode::removeGlobal(GlobalValue *GV) {
 205   std::vector<GlobalValue*>::iterator I =
 206     std::lower_bound(Globals.begin(), Globals.end(), GV);
 207   assert(I != Globals.end() && *I == GV && "Global not in node!");
 208   Globals.erase(I);
 209 }
 210
 211 /// foldNodeCompletely - If we determine that this node has some funny
 212 /// behavior happening to it that we cannot represent, we fold it down to a
 213 /// single, completely pessimistic, node.  This node is represented as a
 214 /// single byte with a single TypeEntry of "void".
 215 ///
 216 void DSNode::foldNodeCompletely() {
 217   if (isNodeCompletelyFolded()) return;  // If this node is already folded...
 218
 219   ++NumFolds;
 220
 221   // If this node has a size that is <= 1, we don't need to create a forwarding
 222   // node.
 223   if (getSize() <= 1) {
 224     NodeType |= DSNode::Array;
 225     Ty = Type::VoidTy;
 226     Size = 1;
 227     assert(Links.size() <= 1 && "Size is 1, but has more links?");
 228     Links.resize(1);
 229   } else {
 230     // Create the node we are going to forward to.  This is required because
 231     // some referrers may have an offset that is > 0.  By forcing them to
 232     // forward, the forwarder has the opportunity to correct the offset.
 233     DSNode *DestNode = new DSNode(0, ParentGraph);
 234     DestNode->NodeType = NodeType|DSNode::Array;
 235     DestNode->Ty = Type::VoidTy;
 236     DestNode->Size = 1;
 237     DestNode->Globals.swap(Globals);
 238
 239     // Start forwarding to the destination node...
 240     forwardNode(DestNode, 0);
 241
 242     if (!Links.empty()) {
 243       DestNode->Links.reserve(1);
 244
 245       DSNodeHandle NH(DestNode);
 246       DestNode->Links.push_back(Links[0]);
 247
 248       // If we have links, merge all of our outgoing links together...
 249       for (unsigned i = Links.size()-1; i != 0; --i)
 250         NH.getNode()->Links[0].mergeWith(Links[i]);
 251       Links.clear();
 252     } else {
 253       DestNode->Links.resize(1);
 254     }
 255   }
 256 }
 257
 258 /// isNodeCompletelyFolded - Return true if this node has been completely
 259 /// folded down to something that can never be expanded, effectively losing
 260 /// all of the field sensitivity that may be present in the node.
 261 ///
 262 bool DSNode::isNodeCompletelyFolded() const {
 263   return getSize() == 1 && Ty == Type::VoidTy && isArray();
 264 }
 265
 266 /// addFullGlobalsList - Compute the full set of global values that are
 267 /// represented by this node.  Unlike getGlobalsList(), this requires fair
 268 /// amount of work to compute, so don't treat this method call as free.
 269 void DSNode::addFullGlobalsList(std::vector<GlobalValue*> &List) const {
 270   if (globals_begin() == globals_end()) return;
 271
 272   EquivalenceClasses<GlobalValue*> &EC = getParentGraph()->getGlobalECs();
 273
 274   for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) {
 275     EquivalenceClasses<GlobalValue*>::iterator ECI = EC.findValue(*I);
 276     if (ECI == EC.end())
 277       List.push_back(*I);
 278     else
 279       List.insert(List.end(), EC.member_begin(ECI), EC.member_end());
 280   }
 281 }
 282
 283 /// addFullFunctionList - Identical to addFullGlobalsList, but only return the
 284 /// functions in the full list.
 285 void DSNode::addFullFunctionList(std::vector<Function*> &List) const {
 286   if (globals_begin() == globals_end()) return;
 287
 288   EquivalenceClasses<GlobalValue*> &EC = getParentGraph()->getGlobalECs();
 289
 290   for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) {
 291     EquivalenceClasses<GlobalValue*>::iterator ECI = EC.findValue(*I);
 292     if (ECI == EC.end()) {
 293       if (Function *F = dyn_cast<Function>(*I))
 294         List.push_back(F);
 295     } else {
 296       for (EquivalenceClasses<GlobalValue*>::member_iterator MI =
 297              EC.member_begin(ECI), E = EC.member_end(); MI != E; ++MI)
 298         if (Function *F = dyn_cast<Function>(*MI))
 299           List.push_back(F);
 300     }
 301   }
 302 }
 303
 304 namespace {
 305   /// TypeElementWalker Class - Used for implementation of physical subtyping...
 306   ///
 307   class TypeElementWalker {
 308     struct StackState {
 309       const Type *Ty;
 310       unsigned Offset;
 311       unsigned Idx;
 312       StackState(const Type *T, unsigned Off = 0)
 313         : Ty(T), Offset(Off), Idx(0) {}
 314     };
 315
 316     std::vector<StackState> Stack;
 317     const TargetData &TD;
 318   public:
 319     TypeElementWalker(const Type *T, const TargetData &td) : TD(td) {
 320       Stack.push_back(T);
 321       StepToLeaf();
 322     }
 323
 324     bool isDone() const { return Stack.empty(); }
 325     const Type *getCurrentType()   const { return Stack.back().Ty;     }
 326     unsigned    getCurrentOffset() const { return Stack.back().Offset; }
 327
 328     void StepToNextType() {
 329       PopStackAndAdvance();
 330       StepToLeaf();
 331     }
 332
 333   private:
 334     /// PopStackAndAdvance - Pop the current element off of the stack and
 335     /// advance the underlying element to the next contained member.
 336     void PopStackAndAdvance() {
 337       assert(!Stack.empty() && "Cannot pop an empty stack!");
 338       Stack.pop_back();
 339       while (!Stack.empty()) {
 340         StackState &SS = Stack.back();
 341         if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) {
 342           ++SS.Idx;
 343           if (SS.Idx != ST->getNumElements()) {
 344             const StructLayout *SL = TD.getStructLayout(ST);
 345             SS.Offset +=
 346                unsigned(SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1]);
 347             return;
 348           }
 349           Stack.pop_back();  // At the end of the structure
 350         } else {
 351           const ArrayType *AT = cast<ArrayType>(SS.Ty);
 352           ++SS.Idx;
 353           if (SS.Idx != AT->getNumElements()) {
 354             SS.Offset += unsigned(TD.getTypeSize(AT->getElementType()));
 355             return;
 356           }
 357           Stack.pop_back();  // At the end of the array
 358         }
 359       }
 360     }
 361
 362     /// StepToLeaf - Used by physical subtyping to move to the first leaf node
 363     /// on the type stack.
 364     void StepToLeaf() {
 365       if (Stack.empty()) return;
 366       while (!Stack.empty() && !Stack.back().Ty->isFirstClassType()) {
 367         StackState &SS = Stack.back();
 368         if (const StructType *ST = dyn_cast<StructType>(SS.Ty)) {
 369           if (ST->getNumElements() == 0) {
 370             assert(SS.Idx == 0);
 371             PopStackAndAdvance();
 372           } else {
 373             // Step into the structure...
 374             assert(SS.Idx < ST->getNumElements());
 375             const StructLayout *SL = TD.getStructLayout(ST);
 376             Stack.push_back(StackState(ST->getElementType(SS.Idx),
 377                             SS.Offset+unsigned(SL->MemberOffsets[SS.Idx])));
 378           }
 379         } else {
 380           const ArrayType *AT = cast<ArrayType>(SS.Ty);
 381           if (AT->getNumElements() == 0) {
 382             assert(SS.Idx == 0);
 383             PopStackAndAdvance();
 384           } else {
 385             // Step into the array...
 386             assert(SS.Idx < AT->getNumElements());
 387             Stack.push_back(StackState(AT->getElementType(),
 388                                        SS.Offset+SS.Idx*
 389                              unsigned(TD.getTypeSize(AT->getElementType()))));
 390           }
 391         }
 392       }
 393     }
 394   };
 395 } // end anonymous namespace
 396
 397 /// ElementTypesAreCompatible - Check to see if the specified types are
 398 /// "physically" compatible.  If so, return true, else return false.  We only
 399 /// have to check the fields in T1: T2 may be larger than T1.  If AllowLargerT1
 400 /// is true, then we also allow a larger T1.
 401 ///
 402 static bool ElementTypesAreCompatible(const Type *T1, const Type *T2,
 403                                       bool AllowLargerT1, const TargetData &TD){
 404   TypeElementWalker T1W(T1, TD), T2W(T2, TD);
 405
 406   while (!T1W.isDone() && !T2W.isDone()) {
 407     if (T1W.getCurrentOffset() != T2W.getCurrentOffset())
 408       return false;
 409
 410     const Type *T1 = T1W.getCurrentType();
 411     const Type *T2 = T2W.getCurrentType();
 412     if (T1 != T2 && !T1->canLosslesslyBitCastTo(T2))
 413       return false;
 414
 415     T1W.StepToNextType();
 416     T2W.StepToNextType();
 417   }
 418
 419   return AllowLargerT1 || T1W.isDone();
 420 }
 421
 422
 423 /// mergeTypeInfo - This method merges the specified type into the current node
 424 /// at the specified offset.  This may update the current node's type record if
 425 /// this gives more information to the node, it may do nothing to the node if
 426 /// this information is already known, or it may merge the node completely (and
 427 /// return true) if the information is incompatible with what is already known.
 428 ///
 429 /// This method returns true if the node is completely folded, otherwise false.
 430 ///
 431 bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset,
 432                            bool FoldIfIncompatible) {
 433   DOUT << "merging " << *NewTy << " at " << Offset << " with " << *Ty << "\n";
 434   const TargetData &TD = getTargetData();
 435   // Check to make sure the Size member is up-to-date.  Size can be one of the
 436   // following:
 437   //  Size = 0, Ty = Void: Nothing is known about this node.
 438   //  Size = 0, Ty = FnTy: FunctionPtr doesn't have a size, so we use zero
 439   //  Size = 1, Ty = Void, Array = 1: The node is collapsed
 440   //  Otherwise, sizeof(Ty) = Size
 441   //
 442   assert(((Size == 0 && Ty == Type::VoidTy && !isArray()) ||
 443           (Size == 0 && !Ty->isSized() && !isArray()) ||
 444           (Size == 1 && Ty == Type::VoidTy && isArray()) ||
 445           (Size == 0 && !Ty->isSized() && !isArray()) ||
 446           (TD.getTypeSize(Ty) == Size)) &&
 447          "Size member of DSNode doesn't match the type structure!");
 448   assert(NewTy != Type::VoidTy && "Cannot merge void type into DSNode!");
 449
 450   if (Offset == 0 && NewTy == Ty)
 451     return false;  // This should be a common case, handle it efficiently
 452
 453   // Return true immediately if the node is completely folded.
 454   if (isNodeCompletelyFolded()) return true;
 455
 456   // If this is an array type, eliminate the outside arrays because they won't
 457   // be used anyway.  This greatly reduces the size of large static arrays used
 458   // as global variables, for example.
 459   //
 460   bool WillBeArray = false;
 461   while (const ArrayType *AT = dyn_cast<ArrayType>(NewTy)) {
 462     // FIXME: we might want to keep small arrays, but must be careful about
 463     // things like: [2 x [10000 x int*]]
 464     NewTy = AT->getElementType();
 465     WillBeArray = true;
 466   }
 467
 468   // Figure out how big the new type we're merging in is...
 469   unsigned NewTySize = NewTy->isSized() ? (unsigned)TD.getTypeSize(NewTy) : 0;
 470
 471   // Otherwise check to see if we can fold this type into the current node.  If
 472   // we can't, we fold the node completely, if we can, we potentially update our
 473   // internal state.
 474   //
 475   if (Ty == Type::VoidTy) {
 476     // If this is the first type that this node has seen, just accept it without
 477     // question....
 478     assert(Offset == 0 && !isArray() &&
 479            "Cannot have an offset into a void node!");
 480
 481     // If this node would have to have an unreasonable number of fields, just
 482     // collapse it.  This can occur for fortran common blocks, which have stupid
 483     // things like { [100000000 x double], [1000000 x double] }.
 484     unsigned NumFields = (NewTySize+DS::PointerSize-1) >> DS::PointerShift;
 485     if (NumFields > DSAFieldLimit) {
 486       foldNodeCompletely();
 487       return true;
 488     }
 489
 490     Ty = NewTy;
 491     NodeType &= ~Array;
 492     if (WillBeArray) NodeType |= Array;
 493     Size = NewTySize;
 494
 495     // Calculate the number of outgoing links from this node.
 496     Links.resize(NumFields);
 497     return false;
 498   }
 499
 500   // Handle node expansion case here...
 501   if (Offset+NewTySize > Size) {
 502     // It is illegal to grow this node if we have treated it as an array of
 503     // objects...
 504     if (isArray()) {
 505       if (FoldIfIncompatible) foldNodeCompletely();
 506       return true;
 507     }
 508
 509     // If this node would have to have an unreasonable number of fields, just
 510     // collapse it.  This can occur for fortran common blocks, which have stupid
 511     // things like { [100000000 x double], [1000000 x double] }.
 512     unsigned NumFields = (NewTySize+Offset+DS::PointerSize-1) >> DS::PointerShift;
 513     if (NumFields > DSAFieldLimit) {
 514       foldNodeCompletely();
 515       return true;
 516     }
 517
 518     if (Offset) {
 519       //handle some common cases:
 520       // Ty:    struct { t1, t2, t3, t4, ..., tn}
 521       // NewTy: struct { offset, stuff...}
 522       // try merge with NewTy: struct {t1, t2, stuff...} if offset lands exactly
 523       // on a field in Ty
 524       if (isa<StructType>(NewTy) && isa<StructType>(Ty)) {
 525         DOUT << "Ty: " << *Ty << "\nNewTy: " << *NewTy << "@" << Offset << "\n";
 526         const StructType *STy = cast<StructType>(Ty);
 527         const StructLayout &SL = *TD.getStructLayout(STy);
 528         unsigned i = SL.getElementContainingOffset(Offset);
 529         //Either we hit it exactly or give up
 530         if (SL.MemberOffsets[i] != Offset) {
 531           if (FoldIfIncompatible) foldNodeCompletely();
 532           return true;
 533         }
 534         std::vector<const Type*> nt;
 535         for (unsigned x = 0; x < i; ++x)
 536           nt.push_back(STy->getElementType(x));
 537         STy = cast<StructType>(NewTy);
 538         nt.insert(nt.end(), STy->element_begin(), STy->element_end());
 539         //and merge
 540         STy = StructType::get(nt);
 541         DOUT << "Trying with: " << *STy << "\n";
 542         return mergeTypeInfo(STy, 0);
 543       }
 544
 545       //Ty: struct { t1, t2, t3 ... tn}
 546       //NewTy T offset x
 547       //try merge with NewTy: struct : {t1, t2, T} if offset lands on a field
 548       //in Ty
 549       if (isa<StructType>(Ty)) {
 550         DOUT << "Ty: " << *Ty << "\nNewTy: " << *NewTy << "@" << Offset << "\n";
 551         const StructType *STy = cast<StructType>(Ty);
 552         const StructLayout &SL = *TD.getStructLayout(STy);
 553         unsigned i = SL.getElementContainingOffset(Offset);
 554         //Either we hit it exactly or give up
 555         if (SL.MemberOffsets[i] != Offset) {
 556           if (FoldIfIncompatible) foldNodeCompletely();
 557           return true;
 558         }
 559         std::vector<const Type*> nt;
 560         for (unsigned x = 0; x < i; ++x)
 561           nt.push_back(STy->getElementType(x));
 562         nt.push_back(NewTy);
 563         //and merge
 564         STy = StructType::get(nt);
 565         DOUT << "Trying with: " << *STy << "\n";
 566         return mergeTypeInfo(STy, 0);
 567       }
 568
 569       assert(0 &&
 570              "UNIMP: Trying to merge a growth type into "
 571              "offset != 0: Collapsing!");
 572       abort();
 573       if (FoldIfIncompatible) foldNodeCompletely();
 574       return true;
 575
 576     }
 577
 578
 579     // Okay, the situation is nice and simple, we are trying to merge a type in
 580     // at offset 0 that is bigger than our current type.  Implement this by
 581     // switching to the new type and then merge in the smaller one, which should
 582     // hit the other code path here.  If the other code path decides it's not
 583     // ok, it will collapse the node as appropriate.
 584     //
 585
 586     const Type *OldTy = Ty;
 587     Ty = NewTy;
 588     NodeType &= ~Array;
 589     if (WillBeArray) NodeType |= Array;
 590     Size = NewTySize;
 591
 592     // Must grow links to be the appropriate size...
 593     Links.resize(NumFields);
 594
 595     // Merge in the old type now... which is guaranteed to be smaller than the
 596     // "current" type.
 597     return mergeTypeInfo(OldTy, 0);
 598   }
 599
 600   assert(Offset <= Size &&
 601          "Cannot merge something into a part of our type that doesn't exist!");
 602
 603   // Find the section of Ty that NewTy overlaps with... first we find the
 604   // type that starts at offset Offset.
 605   //
 606   unsigned O = 0;
 607   const Type *SubType = Ty;
 608   while (O < Offset) {
 609     assert(Offset-O < TD.getTypeSize(SubType) && "Offset out of range!");
 610
 611     switch (SubType->getTypeID()) {
 612     case Type::StructTyID: {
 613       const StructType *STy = cast<StructType>(SubType);
 614       const StructLayout &SL = *TD.getStructLayout(STy);
 615       unsigned i = SL.getElementContainingOffset(Offset-O);
 616
 617       // The offset we are looking for must be in the i'th element...
 618       SubType = STy->getElementType(i);
 619       O += (unsigned)SL.MemberOffsets[i];
 620       break;
 621     }
 622     case Type::ArrayTyID: {
 623       SubType = cast<ArrayType>(SubType)->getElementType();
 624       unsigned ElSize = (unsigned)TD.getTypeSize(SubType);
 625       unsigned Remainder = (Offset-O) % ElSize;
 626       O = Offset-Remainder;
 627       break;
 628     }
 629     default:
 630       if (FoldIfIncompatible) foldNodeCompletely();
 631       return true;
 632     }
 633   }
 634
 635   assert(O == Offset && "Could not achieve the correct offset!");
 636
 637   // If we found our type exactly, early exit
 638   if (SubType == NewTy) return false;
 639
 640   // Differing function types don't require us to merge.  They are not values
 641   // anyway.
 642   if (isa<FunctionType>(SubType) &&
 643       isa<FunctionType>(NewTy)) return false;
 644
 645   unsigned SubTypeSize = SubType->isSized() ?
 646        (unsigned)TD.getTypeSize(SubType) : 0;
 647
 648   // Ok, we are getting desperate now.  Check for physical subtyping, where we
 649   // just require each element in the node to be compatible.
 650   if (NewTySize <= SubTypeSize && NewTySize && NewTySize < 256 &&
 651       SubTypeSize && SubTypeSize < 256 &&
 652       ElementTypesAreCompatible(NewTy, SubType, !isArray(), TD))
 653     return false;
 654
 655   // Okay, so we found the leader type at the offset requested.  Search the list
 656   // of types that starts at this offset.  If SubType is currently an array or
 657   // structure, the type desired may actually be the first element of the
 658   // composite type...
 659   //
 660   unsigned PadSize = SubTypeSize; // Size, including pad memory which is ignored
 661   while (SubType != NewTy) {
 662     const Type *NextSubType = 0;
 663     unsigned NextSubTypeSize = 0;
 664     unsigned NextPadSize = 0;
 665     switch (SubType->getTypeID()) {
 666     case Type::StructTyID: {
 667       const StructType *STy = cast<StructType>(SubType);
 668       const StructLayout &SL = *TD.getStructLayout(STy);
 669       if (SL.MemberOffsets.size() > 1)
 670         NextPadSize = (unsigned)SL.MemberOffsets[1];
 671       else
 672         NextPadSize = SubTypeSize;
 673       NextSubType = STy->getElementType(0);
 674       NextSubTypeSize = (unsigned)TD.getTypeSize(NextSubType);
 675       break;
 676     }
 677     case Type::ArrayTyID:
 678       NextSubType = cast<ArrayType>(SubType)->getElementType();
 679       NextSubTypeSize = (unsigned)TD.getTypeSize(NextSubType);
 680       NextPadSize = NextSubTypeSize;
 681       break;
 682     default: ;
 683       // fall out
 684     }
 685
 686     if (NextSubType == 0)
 687       break;   // In the default case, break out of the loop
 688
 689     if (NextPadSize < NewTySize)
 690       break;   // Don't allow shrinking to a smaller type than NewTySize
 691     SubType = NextSubType;
 692     SubTypeSize = NextSubTypeSize;
 693     PadSize = NextPadSize;
 694   }
 695
 696   // If we found the type exactly, return it...
 697   if (SubType == NewTy)
 698     return false;
 699
 700   // Check to see if we have a compatible, but different type...
 701   if (NewTySize == SubTypeSize) {
 702     // Check to see if this type is obviously convertible... int -> uint f.e.
 703     if (NewTy->canLosslesslyBitCastTo(SubType))
 704       return false;
 705
 706     // Check to see if we have a pointer & integer mismatch going on here,
 707     // loading a pointer as a long, for example.
 708     //
 709     if (SubType->isInteger() && isa<PointerType>(NewTy) ||
 710         NewTy->isInteger() && isa<PointerType>(SubType))
 711       return false;
 712   } else if (NewTySize > SubTypeSize && NewTySize <= PadSize) {
 713     // We are accessing the field, plus some structure padding.  Ignore the
 714     // structure padding.
 715     return false;
 716   }
 717
 718   Module *M = 0;
 719   if (getParentGraph()->retnodes_begin() != getParentGraph()->retnodes_end())
 720     M = getParentGraph()->retnodes_begin()->first->getParent();
 721
 722   DOUT << "MergeTypeInfo Folding OrigTy: ";
 723   DEBUG(WriteTypeSymbolic(*cerr.stream(), Ty, M) << "\n due to:";
 724         WriteTypeSymbolic(*cerr.stream(), NewTy, M) << " @ " << Offset << "!\n"
 725                                                     << "SubType: ";
 726         WriteTypeSymbolic(*cerr.stream(), SubType, M) << "\n\n");
 727
 728   if (FoldIfIncompatible) foldNodeCompletely();
 729   return true;
 730 }
 731
 732
 733
 734 /// addEdgeTo - Add an edge from the current node to the specified node.  This
 735 /// can cause merging of nodes in the graph.
 736 ///
 737 void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) {
 738   if (NH.isNull()) return;       // Nothing to do
 739
 740   if (isNodeCompletelyFolded())
 741     Offset = 0;
 742
 743   DSNodeHandle &ExistingEdge = getLink(Offset);
 744   if (!ExistingEdge.isNull()) {
 745     // Merge the two nodes...
 746     ExistingEdge.mergeWith(NH);
 747   } else {                             // No merging to perform...
 748     setLink(Offset, NH);               // Just force a link in there...
 749   }
 750 }
 751
 752
 753 /// MergeSortedVectors - Efficiently merge a vector into another vector where
 754 /// duplicates are not allowed and both are sorted.  This assumes that 'T's are
 755 /// efficiently copyable and have sane comparison semantics.
 756 ///
 757 static void MergeSortedVectors(std::vector<GlobalValue*> &Dest,
 758                                const std::vector<GlobalValue*> &Src) {
 759   // By far, the most common cases will be the simple ones.  In these cases,
 760   // avoid having to allocate a temporary vector...
 761   //
 762   if (Src.empty()) {             // Nothing to merge in...
 763     return;
 764   } else if (Dest.empty()) {     // Just copy the result in...
 765     Dest = Src;
 766   } else if (Src.size() == 1) {  // Insert a single element...
 767     const GlobalValue *V = Src[0];
 768     std::vector<GlobalValue*>::iterator I =
 769       std::lower_bound(Dest.begin(), Dest.end(), V);
 770     if (I == Dest.end() || *I != Src[0])  // If not already contained...
 771       Dest.insert(I, Src[0]);
 772   } else if (Dest.size() == 1) {
 773     GlobalValue *Tmp = Dest[0];           // Save value in temporary...
 774     Dest = Src;                           // Copy over list...
 775     std::vector<GlobalValue*>::iterator I =
 776       std::lower_bound(Dest.begin(), Dest.end(), Tmp);
 777     if (I == Dest.end() || *I != Tmp)     // If not already contained...
 778       Dest.insert(I, Tmp);
 779
 780   } else {
 781     // Make a copy to the side of Dest...
 782     std::vector<GlobalValue*> Old(Dest);
 783
 784     // Make space for all of the type entries now...
 785     Dest.resize(Dest.size()+Src.size());
 786
 787     // Merge the two sorted ranges together... into Dest.
 788     std::merge(Old.begin(), Old.end(), Src.begin(), Src.end(), Dest.begin());
 789
 790     // Now erase any duplicate entries that may have accumulated into the
 791     // vectors (because they were in both of the input sets)
 792     Dest.erase(std::unique(Dest.begin(), Dest.end()), Dest.end());
 793   }
 794 }
 795
 796 void DSNode::mergeGlobals(const std::vector<GlobalValue*> &RHS) {
 797   MergeSortedVectors(Globals, RHS);
 798 }
 799
 800 // MergeNodes - Helper function for DSNode::mergeWith().
 801 // This function does the hard work of merging two nodes, CurNodeH
 802 // and NH after filtering out trivial cases and making sure that
 803 // CurNodeH.offset >= NH.offset.
 804 //
 805 // ***WARNING***
 806 // Since merging may cause either node to go away, we must always
 807 // use the node-handles to refer to the nodes.  These node handles are
 808 // automatically updated during merging, so will always provide access
 809 // to the correct node after a merge.
 810 //
 811 void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) {
 812   assert(CurNodeH.getOffset() >= NH.getOffset() &&
 813          "This should have been enforced in the caller.");
 814   assert(CurNodeH.getNode()->getParentGraph()==NH.getNode()->getParentGraph() &&
 815          "Cannot merge two nodes that are not in the same graph!");
 816
 817   // Now we know that Offset >= NH.Offset, so convert it so our "Offset" (with
 818   // respect to NH.Offset) is now zero.  NOffset is the distance from the base
 819   // of our object that N starts from.
 820   //
 821   unsigned NOffset = CurNodeH.getOffset()-NH.getOffset();
 822   unsigned NSize = NH.getNode()->getSize();
 823
 824   // If the two nodes are of different size, and the smaller node has the array
 825   // bit set, collapse!
 826   if (NSize != CurNodeH.getNode()->getSize()) {
 827 #if COLLAPSE_ARRAYS_AGGRESSIVELY
 828     if (NSize < CurNodeH.getNode()->getSize()) {
 829       if (NH.getNode()->isArray())
 830         NH.getNode()->foldNodeCompletely();
 831     } else if (CurNodeH.getNode()->isArray()) {
 832       NH.getNode()->foldNodeCompletely();
 833     }
 834 #endif
 835   }
 836
 837   // Merge the type entries of the two nodes together...
 838   if (NH.getNode()->Ty != Type::VoidTy)
 839     CurNodeH.getNode()->mergeTypeInfo(NH.getNode()->Ty, NOffset);
 840   assert(!CurNodeH.getNode()->isDeadNode());
 841
 842   // If we are merging a node with a completely folded node, then both nodes are
 843   // now completely folded.
 844   //
 845   if (CurNodeH.getNode()->isNodeCompletelyFolded()) {
 846     if (!NH.getNode()->isNodeCompletelyFolded()) {
 847       NH.getNode()->foldNodeCompletely();
 848       assert(NH.getNode() && NH.getOffset() == 0 &&
 849              "folding did not make offset 0?");
 850       NOffset = NH.getOffset();
 851       NSize = NH.getNode()->getSize();
 852       assert(NOffset == 0 && NSize == 1);
 853     }
 854   } else if (NH.getNode()->isNodeCompletelyFolded()) {
 855     CurNodeH.getNode()->foldNodeCompletely();
 856     assert(CurNodeH.getNode() && CurNodeH.getOffset() == 0 &&
 857            "folding did not make offset 0?");
 858     NSize = NH.getNode()->getSize();
 859     NOffset = NH.getOffset();
 860     assert(NOffset == 0 && NSize == 1);
 861   }
 862
 863   DSNode *N = NH.getNode();
 864   if (CurNodeH.getNode() == N || N == 0) return;
 865   assert(!CurNodeH.getNode()->isDeadNode());
 866
 867   // Merge the NodeType information.
 868   CurNodeH.getNode()->NodeType |= N->NodeType;
 869
 870   // Start forwarding to the new node!
 871   N->forwardNode(CurNodeH.getNode(), NOffset);
 872   assert(!CurNodeH.getNode()->isDeadNode());
 873
 874   // Make all of the outgoing links of N now be outgoing links of CurNodeH.
 875   //
 876   for (unsigned i = 0; i < N->getNumLinks(); ++i) {
 877     DSNodeHandle &Link = N->getLink(i << DS::PointerShift);
 878     if (Link.getNode()) {
 879       // Compute the offset into the current node at which to
 880       // merge this link.  In the common case, this is a linear
 881       // relation to the offset in the original node (with
 882       // wrapping), but if the current node gets collapsed due to
 883       // recursive merging, we must make sure to merge in all remaining
 884       // links at offset zero.
 885       unsigned MergeOffset = 0;
 886       DSNode *CN = CurNodeH.getNode();
 887       if (CN->Size != 1)
 888         MergeOffset = ((i << DS::PointerShift)+NOffset) % CN->getSize();
 889       CN->addEdgeTo(MergeOffset, Link);
 890     }
 891   }
 892
 893   // Now that there are no outgoing edges, all of the Links are dead.
 894   N->Links.clear();
 895
 896   // Merge the globals list...
 897   if (!N->Globals.empty()) {
 898     CurNodeH.getNode()->mergeGlobals(N->Globals);
 899
 900     // Delete the globals from the old node...
 901     std::vector<GlobalValue*>().swap(N->Globals);
 902   }
 903 }
 904
 905
 906 /// mergeWith - Merge this node and the specified node, moving all links to and
 907 /// from the argument node into the current node, deleting the node argument.
 908 /// Offset indicates what offset the specified node is to be merged into the
 909 /// current node.
 910 ///
 911 /// The specified node may be a null pointer (in which case, we update it to
 912 /// point to this node).
 913 ///
 914 void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) {
 915   DSNode *N = NH.getNode();
 916   if (N == this && NH.getOffset() == Offset)
 917     return;  // Noop
 918
 919   // If the RHS is a null node, make it point to this node!
 920   if (N == 0) {
 921     NH.mergeWith(DSNodeHandle(this, Offset));
 922     return;
 923   }
 924
 925   assert(!N->isDeadNode() && !isDeadNode());
 926   assert(!hasNoReferrers() && "Should not try to fold a useless node!");
 927
 928   if (N == this) {
 929     // We cannot merge two pieces of the same node together, collapse the node
 930     // completely.
 931     DOUT << "Attempting to merge two chunks of the same node together!\n";
 932     foldNodeCompletely();
 933     return;
 934   }
 935
 936   // If both nodes are not at offset 0, make sure that we are merging the node
 937   // at an later offset into the node with the zero offset.
 938   //
 939   if (Offset < NH.getOffset()) {
 940     N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset());
 941     return;
 942   } else if (Offset == NH.getOffset() && getSize() < N->getSize()) {
 943     // If the offsets are the same, merge the smaller node into the bigger node
 944     N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset());
 945     return;
 946   }
 947
 948   // Ok, now we can merge the two nodes.  Use a static helper that works with
 949   // two node handles, since "this" may get merged away at intermediate steps.
 950   DSNodeHandle CurNodeH(this, Offset);
 951   DSNodeHandle NHCopy(NH);
 952   if (CurNodeH.getOffset() >= NHCopy.getOffset())
 953     DSNode::MergeNodes(CurNodeH, NHCopy);
 954   else
 955     DSNode::MergeNodes(NHCopy, CurNodeH);
 956 }
 957
 958
 959 //===----------------------------------------------------------------------===//
 960 // ReachabilityCloner Implementation
 961 //===----------------------------------------------------------------------===//
 962
 963 DSNodeHandle ReachabilityCloner::getClonedNH(const DSNodeHandle &SrcNH) {
 964   if (SrcNH.isNull()) return DSNodeHandle();
 965   const DSNode *SN = SrcNH.getNode();
 966
 967   DSNodeHandle &NH = NodeMap[SN];
 968   if (!NH.isNull()) {   // Node already mapped?
 969     DSNode *NHN = NH.getNode();
 970     return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset());
 971   }
 972
 973   // If SrcNH has globals and the destination graph has one of the same globals,
 974   // merge this node with the destination node, which is much more efficient.
 975   if (SN->globals_begin() != SN->globals_end()) {
 976     DSScalarMap &DestSM = Dest.getScalarMap();
 977     for (DSNode::globals_iterator I = SN->globals_begin(),E = SN->globals_end();
 978          I != E; ++I) {
 979       GlobalValue *GV = *I;
 980       DSScalarMap::iterator GI = DestSM.find(GV);
 981       if (GI != DestSM.end() && !GI->second.isNull()) {
 982         // We found one, use merge instead!
 983         merge(GI->second, Src.getNodeForValue(GV));
 984         assert(!NH.isNull() && "Didn't merge node!");
 985         DSNode *NHN = NH.getNode();
 986         return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset());
 987       }
 988     }
 989   }
 990
 991   DSNode *DN = new DSNode(*SN, &Dest, true /* Null out all links */);
 992   DN->maskNodeTypes(BitsToKeep);
 993   NH = DN;
 994
 995   // Next, recursively clone all outgoing links as necessary.  Note that
 996   // adding these links can cause the node to collapse itself at any time, and
 997   // the current node may be merged with arbitrary other nodes.  For this
 998   // reason, we must always go through NH.
 999   DN = 0;
1000   for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) {
1001     const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift);
1002     if (!SrcEdge.isNull()) {
1003       const DSNodeHandle &DestEdge = getClonedNH(SrcEdge);
1004       // Compute the offset into the current node at which to
1005       // merge this link.  In the common case, this is a linear
1006       // relation to the offset in the original node (with
1007       // wrapping), but if the current node gets collapsed due to
1008       // recursive merging, we must make sure to merge in all remaining
1009       // links at offset zero.
1010       unsigned MergeOffset = 0;
1011       DSNode *CN = NH.getNode();
1012       if (CN->getSize() != 1)
1013         MergeOffset = ((i << DS::PointerShift)+NH.getOffset()) % CN->getSize();
1014       CN->addEdgeTo(MergeOffset, DestEdge);
1015     }
1016   }
1017
1018   // If this node contains any globals, make sure they end up in the scalar
1019   // map with the correct offset.
1020   for (DSNode::globals_iterator I = SN->globals_begin(), E = SN->globals_end();
1021        I != E; ++I) {
1022     GlobalValue *GV = *I;
1023     const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV);
1024     DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
1025     assert(DestGNH.getNode() == NH.getNode() &&"Global mapping inconsistent");
1026     Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
1027                                        DestGNH.getOffset()+SrcGNH.getOffset()));
1028   }
1029   NH.getNode()->mergeGlobals(SN->getGlobalsList());
1030
1031   return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset());
1032 }
1033
1034 void ReachabilityCloner::merge(const DSNodeHandle &NH,
1035                                const DSNodeHandle &SrcNH) {
1036   if (SrcNH.isNull()) return;  // Noop
1037   if (NH.isNull()) {
1038     // If there is no destination node, just clone the source and assign the
1039     // destination node to be it.
1040     NH.mergeWith(getClonedNH(SrcNH));
1041     return;
1042   }
1043
1044   // Okay, at this point, we know that we have both a destination and a source
1045   // node that need to be merged.  Check to see if the source node has already
1046   // been cloned.
1047   const DSNode *SN = SrcNH.getNode();
1048   DSNodeHandle &SCNH = NodeMap[SN];  // SourceClonedNodeHandle
1049   if (!SCNH.isNull()) {   // Node already cloned?
1050     DSNode *SCNHN = SCNH.getNode();
1051     NH.mergeWith(DSNodeHandle(SCNHN,
1052                               SCNH.getOffset()+SrcNH.getOffset()));
1053     return;  // Nothing to do!
1054   }
1055
1056   // Okay, so the source node has not already been cloned.  Instead of creating
1057   // a new DSNode, only to merge it into the one we already have, try to perform
1058   // the merge in-place.  The only case we cannot handle here is when the offset
1059   // into the existing node is less than the offset into the virtual node we are
1060   // merging in.  In this case, we have to extend the existing node, which
1061   // requires an allocation anyway.
1062   DSNode *DN = NH.getNode();   // Make sure the Offset is up-to-date
1063   if (NH.getOffset() >= SrcNH.getOffset()) {
1064     if (!DN->isNodeCompletelyFolded()) {
1065       // Make sure the destination node is folded if the source node is folded.
1066       if (SN->isNodeCompletelyFolded()) {
1067         DN->foldNodeCompletely();
1068         DN = NH.getNode();
1069       } else if (SN->getSize() != DN->getSize()) {
1070         // If the two nodes are of different size, and the smaller node has the
1071         // array bit set, collapse!
1072 #if COLLAPSE_ARRAYS_AGGRESSIVELY
1073         if (SN->getSize() < DN->getSize()) {
1074           if (SN->isArray()) {
1075             DN->foldNodeCompletely();
1076             DN = NH.getNode();
1077           }
1078         } else if (DN->isArray()) {
1079           DN->foldNodeCompletely();
1080           DN = NH.getNode();
1081         }
1082 #endif
1083       }
1084
1085       // Merge the type entries of the two nodes together...
1086       if (SN->getType() != Type::VoidTy && !DN->isNodeCompletelyFolded()) {
1087         DN->mergeTypeInfo(SN->getType(), NH.getOffset()-SrcNH.getOffset());
1088         DN = NH.getNode();
1089       }
1090     }
1091
1092     assert(!DN->isDeadNode());
1093
1094     // Merge the NodeType information.
1095     DN->mergeNodeFlags(SN->getNodeFlags() & BitsToKeep);
1096
1097     // Before we start merging outgoing links and updating the scalar map, make
1098     // sure it is known that this is the representative node for the src node.
1099     SCNH = DSNodeHandle(DN, NH.getOffset()-SrcNH.getOffset());
1100
1101     // If the source node contains any globals, make sure they end up in the
1102     // scalar map with the correct offset.
1103     if (SN->globals_begin() != SN->globals_end()) {
1104       // Update the globals in the destination node itself.
1105       DN->mergeGlobals(SN->getGlobalsList());
1106
1107       // Update the scalar map for the graph we are merging the source node
1108       // into.
1109       for (DSNode::globals_iterator I = SN->globals_begin(),
1110              E = SN->globals_end(); I != E; ++I) {
1111         GlobalValue *GV = *I;
1112         const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV);
1113         DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
1114         assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent");
1115         Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
1116                                       DestGNH.getOffset()+SrcGNH.getOffset()));
1117       }
1118       NH.getNode()->mergeGlobals(SN->getGlobalsList());
1119     }
1120   } else {
1121     // We cannot handle this case without allocating a temporary node.  Fall
1122     // back on being simple.
1123     DSNode *NewDN = new DSNode(*SN, &Dest, true /* Null out all links */);
1124     NewDN->maskNodeTypes(BitsToKeep);
1125
1126     unsigned NHOffset = NH.getOffset();
1127     NH.mergeWith(DSNodeHandle(NewDN, SrcNH.getOffset()));
1128
1129     assert(NH.getNode() &&
1130            (NH.getOffset() > NHOffset ||
1131             (NH.getOffset() == 0 && NH.getNode()->isNodeCompletelyFolded())) &&
1132            "Merging did not adjust the offset!");
1133
1134     // Before we start merging outgoing links and updating the scalar map, make
1135     // sure it is known that this is the representative node for the src node.
1136     SCNH = DSNodeHandle(NH.getNode(), NH.getOffset()-SrcNH.getOffset());
1137
1138     // If the source node contained any globals, make sure to create entries
1139     // in the scalar map for them!
1140     for (DSNode::globals_iterator I = SN->globals_begin(),
1141            E = SN->globals_end(); I != E; ++I) {
1142       GlobalValue *GV = *I;
1143       const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV);
1144       DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
1145       assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent");
1146       assert(SrcGNH.getNode() == SN && "Global mapping inconsistent");
1147       Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
1148                                     DestGNH.getOffset()+SrcGNH.getOffset()));
1149     }
1150   }
1151
1152
1153   // Next, recursively merge all outgoing links as necessary.  Note that
1154   // adding these links can cause the destination node to collapse itself at
1155   // any time, and the current node may be merged with arbitrary other nodes.
1156   // For this reason, we must always go through NH.
1157   DN = 0;
1158   for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) {
1159     const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift);
1160     if (!SrcEdge.isNull()) {
1161       // Compute the offset into the current node at which to
1162       // merge this link.  In the common case, this is a linear
1163       // relation to the offset in the original node (with
1164       // wrapping), but if the current node gets collapsed due to
1165       // recursive merging, we must make sure to merge in all remaining
1166       // links at offset zero.
1167       DSNode *CN = SCNH.getNode();
1168       unsigned MergeOffset =
1169         ((i << DS::PointerShift)+SCNH.getOffset()) % CN->getSize();
1170
1171       DSNodeHandle Tmp = CN->getLink(MergeOffset);
1172       if (!Tmp.isNull()) {
1173         // Perform the recursive merging.  Make sure to create a temporary NH,
1174         // because the Link can disappear in the process of recursive merging.
1175         merge(Tmp, SrcEdge);
1176       } else {
1177         Tmp.mergeWith(getClonedNH(SrcEdge));
1178         // Merging this could cause all kinds of recursive things to happen,
1179         // culminating in the current node being eliminated.  Since this is
1180         // possible, make sure to reaquire the link from 'CN'.
1181
1182         unsigned MergeOffset = 0;
1183         CN = SCNH.getNode();
1184         MergeOffset = ((i << DS::PointerShift)+SCNH.getOffset()) %CN->getSize();
1185         CN->getLink(MergeOffset).mergeWith(Tmp);
1186       }
1187     }
1188   }
1189 }
1190
1191 /// mergeCallSite - Merge the nodes reachable from the specified src call
1192 /// site into the nodes reachable from DestCS.
1193 void ReachabilityCloner::mergeCallSite(DSCallSite &DestCS,
1194                                        const DSCallSite &SrcCS) {
1195   merge(DestCS.getRetVal(), SrcCS.getRetVal());
1196   unsigned MinArgs = DestCS.getNumPtrArgs();
1197   if (SrcCS.getNumPtrArgs() < MinArgs) MinArgs = SrcCS.getNumPtrArgs();
1198
1199   for (unsigned a = 0; a != MinArgs; ++a)
1200     merge(DestCS.getPtrArg(a), SrcCS.getPtrArg(a));
1201
1202   for (unsigned a = MinArgs, e = SrcCS.getNumPtrArgs(); a != e; ++a)
1203     DestCS.addPtrArg(getClonedNH(SrcCS.getPtrArg(a)));
1204 }
1205
1206
1207 //===----------------------------------------------------------------------===//
1208 // DSCallSite Implementation
1209 //===----------------------------------------------------------------------===//
1210
1211 // Define here to avoid including iOther.h and BasicBlock.h in DSGraph.h
1212 Function &DSCallSite::getCaller() const {
1213   return *Site.getInstruction()->getParent()->getParent();
1214 }
1215
1216 void DSCallSite::InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
1217                         ReachabilityCloner &RC) {
1218   NH = RC.getClonedNH(Src);
1219 }
1220
1221 //===----------------------------------------------------------------------===//
1222 // DSGraph Implementation
1223 //===----------------------------------------------------------------------===//
1224
1225 /// getFunctionNames - Return a space separated list of the name of the
1226 /// functions in this graph (if any)
1227 std::string DSGraph::getFunctionNames() const {
1228   switch (getReturnNodes().size()) {
1229   case 0: return "Globals graph";
1230   case 1: return retnodes_begin()->first->getName();
1231   default:
1232     std::string Return;
1233     for (DSGraph::retnodes_iterator I = retnodes_begin();
1234          I != retnodes_end(); ++I)
1235       Return += I->first->getName() + " ";
1236     Return.erase(Return.end()-1, Return.end());   // Remove last space character
1237     return Return;
1238   }
1239 }
1240
1241
1242 DSGraph::DSGraph(const DSGraph &G, EquivalenceClasses<GlobalValue*> &ECs,
1243                  unsigned CloneFlags)
1244   : GlobalsGraph(0), ScalarMap(ECs), TD(G.TD) {
1245   PrintAuxCalls = false;
1246   cloneInto(G, CloneFlags);
1247 }
1248
1249 DSGraph::~DSGraph() {
1250   FunctionCalls.clear();
1251   AuxFunctionCalls.clear();
1252   ScalarMap.clear();
1253   ReturnNodes.clear();
1254
1255   // Drop all intra-node references, so that assertions don't fail...
1256   for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI)
1257     NI->dropAllReferences();
1258
1259   // Free all of the nodes.
1260   Nodes.clear();
1261 }
1262
1263 // dump - Allow inspection of graph in a debugger.
1264 void DSGraph::dump() const { print(cerr); }
1265
1266
1267 /// remapLinks - Change all of the Links in the current node according to the
1268 /// specified mapping.
1269 ///
1270 void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) {
1271   for (unsigned i = 0, e = Links.size(); i != e; ++i)
1272     if (DSNode *N = Links[i].getNode()) {
1273       DSGraph::NodeMapTy::const_iterator ONMI = OldNodeMap.find(N);
1274       if (ONMI != OldNodeMap.end()) {
1275         DSNode *ONMIN = ONMI->second.getNode();
1276         Links[i].setTo(ONMIN, Links[i].getOffset()+ONMI->second.getOffset());
1277       }
1278     }
1279 }
1280
1281 /// addObjectToGraph - This method can be used to add global, stack, and heap
1282 /// objects to the graph.  This can be used when updating DSGraphs due to the
1283 /// introduction of new temporary objects.  The new object is not pointed to
1284 /// and does not point to any other objects in the graph.
1285 DSNode *DSGraph::addObjectToGraph(Value *Ptr, bool UseDeclaredType) {
1286   assert(isa<PointerType>(Ptr->getType()) && "Ptr is not a pointer!");
1287   const Type *Ty = cast<PointerType>(Ptr->getType())->getElementType();
1288   DSNode *N = new DSNode(UseDeclaredType ? Ty : 0, this);
1289   assert(ScalarMap[Ptr].isNull() && "Object already in this graph!");
1290   ScalarMap[Ptr] = N;
1291
1292   if (GlobalValue *GV = dyn_cast<GlobalValue>(Ptr)) {
1293     N->addGlobal(GV);
1294   } else if (isa<MallocInst>(Ptr)) {
1295     N->setHeapNodeMarker();
1296   } else if (isa<AllocaInst>(Ptr)) {
1297     N->setAllocaNodeMarker();
1298   } else {
1299     assert(0 && "Illegal memory object input!");
1300   }
1301   return N;
1302 }
1303
1304
1305 /// cloneInto - Clone the specified DSGraph into the current graph.  The
1306 /// translated ScalarMap for the old function is filled into the ScalarMap
1307 /// for the graph, and the translated ReturnNodes map is returned into
1308 /// ReturnNodes.
1309 ///
1310 /// The CloneFlags member controls various aspects of the cloning process.
1311 ///
1312 void DSGraph::cloneInto(const DSGraph &G, unsigned CloneFlags) {
1313   TIME_REGION(X, "cloneInto");
1314   assert(&G != this && "Cannot clone graph into itself!");
1315
1316   NodeMapTy OldNodeMap;
1317
1318   // Remove alloca or mod/ref bits as specified...
1319   unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0)
1320     | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0)
1321     | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0);
1322   BitsToClear |= DSNode::DEAD;  // Clear dead flag...
1323
1324   for (node_const_iterator I = G.node_begin(), E = G.node_end(); I != E; ++I) {
1325     assert(!I->isForwarding() &&
1326            "Forward nodes shouldn't be in node list!");
1327     DSNode *New = new DSNode(*I, this);
1328     New->maskNodeTypes(~BitsToClear);
1329     OldNodeMap[I] = New;
1330   }
1331
1332 #ifndef NDEBUG
1333   Timer::addPeakMemoryMeasurement();
1334 #endif
1335
1336   // Rewrite the links in the new nodes to point into the current graph now.
1337   // Note that we don't loop over the node's list to do this.  The problem is
1338   // that remaping links can cause recursive merging to happen, which means
1339   // that node_iterator's can get easily invalidated!  Because of this, we
1340   // loop over the OldNodeMap, which contains all of the new nodes as the
1341   // .second element of the map elements.  Also note that if we remap a node
1342   // more than once, we won't break anything.
1343   for (NodeMapTy::iterator I = OldNodeMap.begin(), E = OldNodeMap.end();
1344        I != E; ++I)
1345     I->second.getNode()->remapLinks(OldNodeMap);
1346
1347   // Copy the scalar map... merging all of the global nodes...
1348   for (DSScalarMap::const_iterator I = G.ScalarMap.begin(),
1349          E = G.ScalarMap.end(); I != E; ++I) {
1350     DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()];
1351     DSNodeHandle &H = ScalarMap.getRawEntryRef(I->first);
1352     DSNode *MappedNodeN = MappedNode.getNode();
1353     H.mergeWith(DSNodeHandle(MappedNodeN,
1354                              I->second.getOffset()+MappedNode.getOffset()));
1355   }
1356
1357   if (!(CloneFlags & DontCloneCallNodes)) {
1358     // Copy the function calls list.
1359     for (fc_iterator I = G.fc_begin(), E = G.fc_end(); I != E; ++I)
1360       FunctionCalls.push_back(DSCallSite(*I, OldNodeMap));
1361   }
1362
1363   if (!(CloneFlags & DontCloneAuxCallNodes)) {
1364     // Copy the auxiliary function calls list.
1365     for (afc_iterator I = G.afc_begin(), E = G.afc_end(); I != E; ++I)
1366       AuxFunctionCalls.push_back(DSCallSite(*I, OldNodeMap));
1367   }
1368
1369   // Map the return node pointers over...
1370   for (retnodes_iterator I = G.retnodes_begin(),
1371          E = G.retnodes_end(); I != E; ++I) {
1372     const DSNodeHandle &Ret = I->second;
1373     DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()];
1374     DSNode *MappedRetN = MappedRet.getNode();
1375     ReturnNodes.insert(std::make_pair(I->first,
1376                                       DSNodeHandle(MappedRetN,
1377                                      MappedRet.getOffset()+Ret.getOffset())));
1378   }
1379 }
1380
1381 /// spliceFrom - Logically perform the operation of cloning the RHS graph into
1382 /// this graph, then clearing the RHS graph.  Instead of performing this as
1383 /// two seperate operations, do it as a single, much faster, one.
1384 ///
1385 void DSGraph::spliceFrom(DSGraph &RHS) {
1386   // Change all of the nodes in RHS to think we are their parent.
1387   for (NodeListTy::iterator I = RHS.Nodes.begin(), E = RHS.Nodes.end();
1388        I != E; ++I)
1389     I->setParentGraph(this);
1390   // Take all of the nodes.
1391   Nodes.splice(Nodes.end(), RHS.Nodes);
1392
1393   // Take all of the calls.
1394   FunctionCalls.splice(FunctionCalls.end(), RHS.FunctionCalls);
1395   AuxFunctionCalls.splice(AuxFunctionCalls.end(), RHS.AuxFunctionCalls);
1396
1397   // Take all of the return nodes.
1398   if (ReturnNodes.empty()) {
1399     ReturnNodes.swap(RHS.ReturnNodes);
1400   } else {
1401     ReturnNodes.insert(RHS.ReturnNodes.begin(), RHS.ReturnNodes.end());
1402     RHS.ReturnNodes.clear();
1403   }
1404
1405   // Merge the scalar map in.
1406   ScalarMap.spliceFrom(RHS.ScalarMap);
1407 }
1408
1409 /// spliceFrom - Copy all entries from RHS, then clear RHS.
1410 ///
1411 void DSScalarMap::spliceFrom(DSScalarMap &RHS) {
1412   // Special case if this is empty.
1413   if (ValueMap.empty()) {
1414     ValueMap.swap(RHS.ValueMap);
1415     GlobalSet.swap(RHS.GlobalSet);
1416   } else {
1417     GlobalSet.insert(RHS.GlobalSet.begin(), RHS.GlobalSet.end());
1418     for (ValueMapTy::iterator I = RHS.ValueMap.begin(), E = RHS.ValueMap.end();
1419          I != E; ++I)
1420       ValueMap[I->first].mergeWith(I->second);
1421     RHS.ValueMap.clear();
1422   }
1423 }
1424
1425
1426 /// getFunctionArgumentsForCall - Given a function that is currently in this
1427 /// graph, return the DSNodeHandles that correspond to the pointer-compatible
1428 /// function arguments.  The vector is filled in with the return value (or
1429 /// null if it is not pointer compatible), followed by all of the
1430 /// pointer-compatible arguments.
1431 void DSGraph::getFunctionArgumentsForCall(Function *F,
1432                                        std::vector<DSNodeHandle> &Args) const {
1433   Args.push_back(getReturnNodeFor(*F));
1434   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
1435        AI != E; ++AI)
1436     if (isPointerType(AI->getType())) {
1437       Args.push_back(getNodeForValue(AI));
1438       assert(!Args.back().isNull() && "Pointer argument w/o scalarmap entry!?");
1439     }
1440 }
1441
1442 namespace {
1443   // HackedGraphSCCFinder - This is used to find nodes that have a path from the
1444   // node to a node cloned by the ReachabilityCloner object contained.  To be
1445   // extra obnoxious it ignores edges from nodes that are globals, and truncates
1446   // search at RC marked nodes.  This is designed as an object so that
1447   // intermediate results can be memoized across invocations of
1448   // PathExistsToClonedNode.
1449   struct HackedGraphSCCFinder {
1450     ReachabilityCloner &RC;
1451     unsigned CurNodeId;
1452     std::vector<const DSNode*> SCCStack;
1453     std::map<const DSNode*, std::pair<unsigned, bool> > NodeInfo;
1454
1455     HackedGraphSCCFinder(ReachabilityCloner &rc) : RC(rc), CurNodeId(1) {
1456       // Remove null pointer as a special case.
1457       NodeInfo[0] = std::make_pair(0, false);
1458     }
1459
1460     std::pair<unsigned, bool> &VisitForSCCs(const DSNode *N);
1461
1462     bool PathExistsToClonedNode(const DSNode *N) {
1463       return VisitForSCCs(N).second;
1464     }
1465
1466     bool PathExistsToClonedNode(const DSCallSite &CS) {
1467       if (PathExistsToClonedNode(CS.getRetVal().getNode()))
1468         return true;
1469       for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
1470         if (PathExistsToClonedNode(CS.getPtrArg(i).getNode()))
1471           return true;
1472       return false;
1473     }
1474   };
1475 }
1476
1477 std::pair<unsigned, bool> &HackedGraphSCCFinder::
1478 VisitForSCCs(const DSNode *N) {
1479   std::map<const DSNode*, std::pair<unsigned, bool> >::iterator
1480     NodeInfoIt = NodeInfo.lower_bound(N);
1481   if (NodeInfoIt != NodeInfo.end() && NodeInfoIt->first == N)
1482     return NodeInfoIt->second;
1483
1484   unsigned Min = CurNodeId++;
1485   unsigned MyId = Min;
1486   std::pair<unsigned, bool> &ThisNodeInfo =
1487     NodeInfo.insert(NodeInfoIt,
1488                     std::make_pair(N, std::make_pair(MyId, false)))->second;
1489
1490   // Base case: if we find a global, this doesn't reach the cloned graph
1491   // portion.
1492   if (N->isGlobalNode()) {
1493     ThisNodeInfo.second = false;
1494     return ThisNodeInfo;
1495   }
1496
1497   // Base case: if this does reach the cloned graph portion... it does. :)
1498   if (RC.hasClonedNode(N)) {
1499     ThisNodeInfo.second = true;
1500     return ThisNodeInfo;
1501   }
1502
1503   SCCStack.push_back(N);
1504
1505   // Otherwise, check all successors.
1506   bool AnyDirectSuccessorsReachClonedNodes = false;
1507   for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
1508        EI != EE; ++EI)
1509     if (DSNode *Succ = EI->getNode()) {
1510       std::pair<unsigned, bool> &SuccInfo = VisitForSCCs(Succ);
1511       if (SuccInfo.first < Min) Min = SuccInfo.first;
1512       AnyDirectSuccessorsReachClonedNodes |= SuccInfo.second;
1513     }
1514
1515   if (Min != MyId)
1516     return ThisNodeInfo;  // Part of a large SCC.  Leave self on stack.
1517
1518   if (SCCStack.back() == N) {  // Special case single node SCC.
1519     SCCStack.pop_back();
1520     ThisNodeInfo.second = AnyDirectSuccessorsReachClonedNodes;
1521     return ThisNodeInfo;
1522   }
1523
1524   // Find out if any direct successors of any node reach cloned nodes.
1525   if (!AnyDirectSuccessorsReachClonedNodes)
1526     for (unsigned i = SCCStack.size()-1; SCCStack[i] != N; --i)
1527       for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
1528            EI != EE; ++EI)
1529         if (DSNode *N = EI->getNode())
1530           if (NodeInfo[N].second) {
1531             AnyDirectSuccessorsReachClonedNodes = true;
1532             goto OutOfLoop;
1533           }
1534 OutOfLoop:
1535   // If any successor reaches a cloned node, mark all nodes in this SCC as
1536   // reaching the cloned node.
1537   if (AnyDirectSuccessorsReachClonedNodes)
1538     while (SCCStack.back() != N) {
1539       NodeInfo[SCCStack.back()].second = true;
1540       SCCStack.pop_back();
1541     }
1542   SCCStack.pop_back();
1543   ThisNodeInfo.second = true;
1544   return ThisNodeInfo;
1545 }
1546
1547 /// mergeInCallFromOtherGraph - This graph merges in the minimal number of
1548 /// nodes from G2 into 'this' graph, merging the bindings specified by the
1549 /// call site (in this graph) with the bindings specified by the vector in G2.
1550 /// The two DSGraphs must be different.
1551 ///
1552 void DSGraph::mergeInGraph(const DSCallSite &CS,
1553                            std::vector<DSNodeHandle> &Args,
1554                            const DSGraph &Graph, unsigned CloneFlags) {
1555   TIME_REGION(X, "mergeInGraph");
1556
1557   assert((CloneFlags & DontCloneCallNodes) &&
1558          "Doesn't support copying of call nodes!");
1559
1560   // If this is not a recursive call, clone the graph into this graph...
1561   if (&Graph == this) {
1562     // Merge the return value with the return value of the context.
1563     Args[0].mergeWith(CS.getRetVal());
1564
1565     // Resolve all of the function arguments.
1566     for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) {
1567       if (i == Args.size()-1)
1568         break;
1569
1570       // Add the link from the argument scalar to the provided value.
1571       Args[i+1].mergeWith(CS.getPtrArg(i));
1572     }
1573     return;
1574   }
1575
1576   // Clone the callee's graph into the current graph, keeping track of where
1577   // scalars in the old graph _used_ to point, and of the new nodes matching
1578   // nodes of the old graph.
1579   ReachabilityCloner RC(*this, Graph, CloneFlags);
1580
1581   // Map the return node pointer over.
1582   if (!CS.getRetVal().isNull())
1583     RC.merge(CS.getRetVal(), Args[0]);
1584
1585   // Map over all of the arguments.
1586   for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) {
1587     if (i == Args.size()-1)
1588       break;
1589
1590     // Add the link from the argument scalar to the provided value.
1591     RC.merge(CS.getPtrArg(i), Args[i+1]);
1592   }
1593
1594   // We generally don't want to copy global nodes or aux calls from the callee
1595   // graph to the caller graph.  However, we have to copy them if there is a
1596   // path from the node to a node we have already copied which does not go
1597   // through another global.  Compute the set of node that can reach globals and
1598   // aux call nodes to copy over, then do it.
1599   std::vector<const DSCallSite*> AuxCallToCopy;
1600   std::vector<GlobalValue*> GlobalsToCopy;
1601
1602   // NodesReachCopiedNodes - Memoize results for efficiency.  Contains a
1603   // true/false value for every visited node that reaches a copied node without
1604   // going through a global.
1605   HackedGraphSCCFinder SCCFinder(RC);
1606
1607   if (!(CloneFlags & DontCloneAuxCallNodes))
1608     for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I)
1609       if (SCCFinder.PathExistsToClonedNode(*I))
1610         AuxCallToCopy.push_back(&*I);
1611 //       else if (I->isIndirectCall()){
1612 //      //If the call node doesn't have any callees, clone it
1613 //      std::vector< Function *> List;
1614 //      I->getCalleeNode()->addFullFunctionList(List);
1615 //      if (!List.size())
1616 //        AuxCallToCopy.push_back(&*I);
1617 //        }
1618
1619   const DSScalarMap &GSM = Graph.getScalarMap();
1620   for (DSScalarMap::global_iterator GI = GSM.global_begin(),
1621          E = GSM.global_end(); GI != E; ++GI) {
1622     DSNode *GlobalNode = Graph.getNodeForValue(*GI).getNode();
1623     for (DSNode::edge_iterator EI = GlobalNode->edge_begin(),
1624            EE = GlobalNode->edge_end(); EI != EE; ++EI)
1625       if (SCCFinder.PathExistsToClonedNode(EI->getNode())) {
1626         GlobalsToCopy.push_back(*GI);
1627         break;
1628       }
1629   }
1630
1631   // Copy aux calls that are needed.
1632   for (unsigned i = 0, e = AuxCallToCopy.size(); i != e; ++i)
1633     AuxFunctionCalls.push_back(DSCallSite(*AuxCallToCopy[i], RC));
1634
1635   // Copy globals that are needed.
1636   for (unsigned i = 0, e = GlobalsToCopy.size(); i != e; ++i)
1637     RC.getClonedNH(Graph.getNodeForValue(GlobalsToCopy[i]));
1638 }
1639
1640
1641
1642 /// mergeInGraph - The method is used for merging graphs together.  If the
1643 /// argument graph is not *this, it makes a clone of the specified graph, then
1644 /// merges the nodes specified in the call site with the formal arguments in the
1645 /// graph.
1646 ///
1647 void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
1648                            const DSGraph &Graph, unsigned CloneFlags) {
1649   // Set up argument bindings.
1650   std::vector<DSNodeHandle> Args;
1651   Graph.getFunctionArgumentsForCall(&F, Args);
1652
1653   mergeInGraph(CS, Args, Graph, CloneFlags);
1654 }
1655
1656 /// getCallSiteForArguments - Get the arguments and return value bindings for
1657 /// the specified function in the current graph.
1658 ///
1659 DSCallSite DSGraph::getCallSiteForArguments(Function &F) const {
1660   std::vector<DSNodeHandle> Args;
1661
1662   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
1663     if (isPointerType(I->getType()))
1664       Args.push_back(getNodeForValue(I));
1665
1666   return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args);
1667 }
1668
1669 /// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in
1670 /// the context of this graph, return the DSCallSite for it.
1671 DSCallSite DSGraph::getDSCallSiteForCallSite(CallSite CS) const {
1672   DSNodeHandle RetVal;
1673   Instruction *I = CS.getInstruction();
1674   if (isPointerType(I->getType()))
1675     RetVal = getNodeForValue(I);
1676
1677   std::vector<DSNodeHandle> Args;
1678   Args.reserve(CS.arg_end()-CS.arg_begin());
1679
1680   // Calculate the arguments vector...
1681   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
1682     if (isPointerType((*I)->getType()))
1683       if (isa<ConstantPointerNull>(*I))
1684         Args.push_back(DSNodeHandle());
1685       else
1686         Args.push_back(getNodeForValue(*I));
1687
1688   // Add a new function call entry...
1689   if (Function *F = CS.getCalledFunction())
1690     return DSCallSite(CS, RetVal, F, Args);
1691   else
1692     return DSCallSite(CS, RetVal,
1693                       getNodeForValue(CS.getCalledValue()).getNode(), Args);
1694 }
1695
1696
1697
1698 // markIncompleteNodes - Mark the specified node as having contents that are not
1699 // known with the current analysis we have performed.  Because a node makes all
1700 // of the nodes it can reach incomplete if the node itself is incomplete, we
1701 // must recursively traverse the data structure graph, marking all reachable
1702 // nodes as incomplete.
1703 //
1704 static void markIncompleteNode(DSNode *N) {
1705   // Stop recursion if no node, or if node already marked...
1706   if (N == 0 || N->isIncomplete()) return;
1707
1708   // Actually mark the node
1709   N->setIncompleteMarker();
1710
1711   // Recursively process children...
1712   for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I)
1713     if (DSNode *DSN = I->getNode())
1714       markIncompleteNode(DSN);
1715 }
1716
1717 static void markIncomplete(DSCallSite &Call) {
1718   // Then the return value is certainly incomplete!
1719   markIncompleteNode(Call.getRetVal().getNode());
1720
1721   // All objects pointed to by function arguments are incomplete!
1722   for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i)
1723     markIncompleteNode(Call.getPtrArg(i).getNode());
1724 }
1725
1726 // markIncompleteNodes - Traverse the graph, identifying nodes that may be
1727 // modified by other functions that have not been resolved yet.  This marks
1728 // nodes that are reachable through three sources of "unknownness":
1729 //
1730 //  Global Variables, Function Calls, and Incoming Arguments
1731 //
1732 // For any node that may have unknown components (because something outside the
1733 // scope of current analysis may have modified it), the 'Incomplete' flag is
1734 // added to the NodeType.
1735 //
1736 void DSGraph::markIncompleteNodes(unsigned Flags) {
1737   // Mark any incoming arguments as incomplete.
1738   if (Flags & DSGraph::MarkFormalArgs)
1739     for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end();
1740          FI != E; ++FI) {
1741       Function &F = *FI->first;
1742       for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
1743            I != E; ++I)
1744         if (isPointerType(I->getType()))
1745           markIncompleteNode(getNodeForValue(I).getNode());
1746       markIncompleteNode(FI->second.getNode());
1747     }
1748
1749   // Mark stuff passed into functions calls as being incomplete.
1750   if (!shouldPrintAuxCalls())
1751     for (std::list<DSCallSite>::iterator I = FunctionCalls.begin(),
1752            E = FunctionCalls.end(); I != E; ++I)
1753       markIncomplete(*I);
1754   else
1755     for (std::list<DSCallSite>::iterator I = AuxFunctionCalls.begin(),
1756            E = AuxFunctionCalls.end(); I != E; ++I)
1757       markIncomplete(*I);
1758
1759   // Mark all global nodes as incomplete.
1760   for (DSScalarMap::global_iterator I = ScalarMap.global_begin(),
1761          E = ScalarMap.global_end(); I != E; ++I)
1762     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I))
1763       if (!GV->hasInitializer() ||    // Always mark external globals incomp.
1764           (!GV->isConstant() && (Flags & DSGraph::IgnoreGlobals) == 0))
1765         markIncompleteNode(ScalarMap[GV].getNode());
1766 }
1767
1768 static inline void killIfUselessEdge(DSNodeHandle &Edge) {
1769   if (DSNode *N = Edge.getNode())  // Is there an edge?
1770     if (N->getNumReferrers() == 1)  // Does it point to a lonely node?
1771       // No interesting info?
1772       if ((N->getNodeFlags() & ~DSNode::Incomplete) == 0 &&
1773           N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded())
1774         Edge.setTo(0, 0);  // Kill the edge!
1775 }
1776
1777 static inline bool nodeContainsExternalFunction(const DSNode *N) {
1778   std::vector<Function*> Funcs;
1779   N->addFullFunctionList(Funcs);
1780   for (unsigned i = 0, e = Funcs.size(); i != e; ++i)
1781     if (Funcs[i]->isExternal()) return true;
1782   return false;
1783 }
1784
1785 static void removeIdenticalCalls(std::list<DSCallSite> &Calls) {
1786   // Remove trivially identical function calls
1787   Calls.sort();  // Sort by callee as primary key!
1788
1789   // Scan the call list cleaning it up as necessary...
1790   DSNodeHandle LastCalleeNode;
1791 #if 0
1792   Function *LastCalleeFunc = 0;
1793   unsigned NumDuplicateCalls = 0;
1794 #endif
1795   bool LastCalleeContainsExternalFunction = false;
1796
1797   unsigned NumDeleted = 0;
1798   for (std::list<DSCallSite>::iterator I = Calls.begin(), E = Calls.end();
1799        I != E;) {
1800     DSCallSite &CS = *I;
1801     std::list<DSCallSite>::iterator OldIt = I++;
1802
1803     if (!CS.isIndirectCall()) {
1804       LastCalleeNode = 0;
1805     } else {
1806       DSNode *Callee = CS.getCalleeNode();
1807
1808       // If the Callee is a useless edge, this must be an unreachable call site,
1809       // eliminate it.
1810       if (Callee->getNumReferrers() == 1 && Callee->isComplete() &&
1811           Callee->getGlobalsList().empty()) {  // No useful info?
1812         DOUT << "WARNING: Useless call site found.\n";
1813         Calls.erase(OldIt);
1814         ++NumDeleted;
1815         continue;
1816       }
1817
1818       // If the last call site in the list has the same callee as this one, and
1819       // if the callee contains an external function, it will never be
1820       // resolvable, just merge the call sites.
1821       if (!LastCalleeNode.isNull() && LastCalleeNode.getNode() == Callee) {
1822         LastCalleeContainsExternalFunction =
1823           nodeContainsExternalFunction(Callee);
1824
1825         std::list<DSCallSite>::iterator PrevIt = OldIt;
1826         --PrevIt;
1827         PrevIt->mergeWith(CS);
1828
1829         // No need to keep this call anymore.
1830         Calls.erase(OldIt);
1831         ++NumDeleted;
1832         continue;
1833       } else {
1834         LastCalleeNode = Callee;
1835       }
1836     }
1837
1838     // If the return value or any arguments point to a void node with no
1839     // information at all in it, and the call node is the only node to point
1840     // to it, remove the edge to the node (killing the node).
1841     //
1842     killIfUselessEdge(CS.getRetVal());
1843     for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
1844       killIfUselessEdge(CS.getPtrArg(a));
1845
1846 #if 0
1847     // If this call site calls the same function as the last call site, and if
1848     // the function pointer contains an external function, this node will
1849     // never be resolved.  Merge the arguments of the call node because no
1850     // information will be lost.
1851     //
1852     if ((CS.isDirectCall()   && CS.getCalleeFunc() == LastCalleeFunc) ||
1853         (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) {
1854       ++NumDuplicateCalls;
1855       if (NumDuplicateCalls == 1) {
1856         if (LastCalleeNode)
1857           LastCalleeContainsExternalFunction =
1858             nodeContainsExternalFunction(LastCalleeNode);
1859         else
1860           LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal();
1861       }
1862
1863       // It is not clear why, but enabling this code makes DSA really
1864       // sensitive to node forwarding.  Basically, with this enabled, DSA
1865       // performs different number of inlinings based on which nodes are
1866       // forwarding or not.  This is clearly a problem, so this code is
1867       // disabled until this can be resolved.
1868 #if 1
1869       if (LastCalleeContainsExternalFunction
1870 #if 0
1871           ||
1872           // This should be more than enough context sensitivity!
1873           // FIXME: Evaluate how many times this is tripped!
1874           NumDuplicateCalls > 20
1875 #endif
1876           ) {
1877
1878         std::list<DSCallSite>::iterator PrevIt = OldIt;
1879         --PrevIt;
1880         PrevIt->mergeWith(CS);
1881
1882         // No need to keep this call anymore.
1883         Calls.erase(OldIt);
1884         ++NumDeleted;
1885         continue;
1886       }
1887 #endif
1888     } else {
1889       if (CS.isDirectCall()) {
1890         LastCalleeFunc = CS.getCalleeFunc();
1891         LastCalleeNode = 0;
1892       } else {
1893         LastCalleeNode = CS.getCalleeNode();
1894         LastCalleeFunc = 0;
1895       }
1896       NumDuplicateCalls = 0;
1897     }
1898 #endif
1899
1900     if (I != Calls.end() && CS == *I) {
1901       LastCalleeNode = 0;
1902       Calls.erase(OldIt);
1903       ++NumDeleted;
1904       continue;
1905     }
1906   }
1907
1908   // Resort now that we simplified things.
1909   Calls.sort();
1910
1911   // Now that we are in sorted order, eliminate duplicates.
1912   std::list<DSCallSite>::iterator CI = Calls.begin(), CE = Calls.end();
1913   if (CI != CE)
1914     while (1) {
1915       std::list<DSCallSite>::iterator OldIt = CI++;
1916       if (CI == CE) break;
1917
1918       // If this call site is now the same as the previous one, we can delete it
1919       // as a duplicate.
1920       if (*OldIt == *CI) {
1921         Calls.erase(CI);
1922         CI = OldIt;
1923         ++NumDeleted;
1924       }
1925     }
1926
1927   //Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end());
1928
1929   // Track the number of call nodes merged away...
1930   NumCallNodesMerged += NumDeleted;
1931
1932   if (NumDeleted)
1933     DOUT << "Merged " << NumDeleted << " call nodes.\n";
1934 }
1935
1936
1937 // removeTriviallyDeadNodes - After the graph has been constructed, this method
1938 // removes all unreachable nodes that are created because they got merged with
1939 // other nodes in the graph.  These nodes will all be trivially unreachable, so
1940 // we don't have to perform any non-trivial analysis here.
1941 //
1942 void DSGraph::removeTriviallyDeadNodes() {
1943   TIME_REGION(X, "removeTriviallyDeadNodes");
1944
1945 #if 0
1946   /// NOTE: This code is disabled.  This slows down DSA on 177.mesa
1947   /// substantially!
1948
1949   // Loop over all of the nodes in the graph, calling getNode on each field.
1950   // This will cause all nodes to update their forwarding edges, causing
1951   // forwarded nodes to be delete-able.
1952   { TIME_REGION(X, "removeTriviallyDeadNodes:node_iterate");
1953   for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) {
1954     DSNode &N = *NI;
1955     for (unsigned l = 0, e = N.getNumLinks(); l != e; ++l)
1956       N.getLink(l*N.getPointerSize()).getNode();
1957   }
1958   }
1959
1960   // NOTE: This code is disabled.  Though it should, in theory, allow us to
1961   // remove more nodes down below, the scan of the scalar map is incredibly
1962   // expensive for certain programs (with large SCCs).  In the future, if we can
1963   // make the scalar map scan more efficient, then we can reenable this.
1964   { TIME_REGION(X, "removeTriviallyDeadNodes:scalarmap");
1965
1966   // Likewise, forward any edges from the scalar nodes.  While we are at it,
1967   // clean house a bit.
1968   for (DSScalarMap::iterator I = ScalarMap.begin(),E = ScalarMap.end();I != E;){
1969     I->second.getNode();
1970     ++I;
1971   }
1972   }
1973 #endif
1974   bool isGlobalsGraph = !GlobalsGraph;
1975
1976   for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E; ) {
1977     DSNode &Node = *NI;
1978
1979     // Do not remove *any* global nodes in the globals graph.
1980     // This is a special case because such nodes may not have I, M, R flags set.
1981     if (Node.isGlobalNode() && isGlobalsGraph) {
1982       ++NI;
1983       continue;
1984     }
1985
1986     if (Node.isComplete() && !Node.isModified() && !Node.isRead()) {
1987       // This is a useless node if it has no mod/ref info (checked above),
1988       // outgoing edges (which it cannot, as it is not modified in this
1989       // context), and it has no incoming edges.  If it is a global node it may
1990       // have all of these properties and still have incoming edges, due to the
1991       // scalar map, so we check those now.
1992       //
1993       if (Node.getNumReferrers() == Node.getGlobalsList().size()) {
1994         const std::vector<GlobalValue*> &Globals = Node.getGlobalsList();
1995
1996         // Loop through and make sure all of the globals are referring directly
1997         // to the node...
1998         for (unsigned j = 0, e = Globals.size(); j != e; ++j) {
1999           DSNode *N = getNodeForValue(Globals[j]).getNode();
2000           assert(N == &Node && "ScalarMap doesn't match globals list!");
2001         }
2002
2003         // Make sure NumReferrers still agrees, if so, the node is truly dead.
2004         if (Node.getNumReferrers() == Globals.size()) {
2005           for (unsigned j = 0, e = Globals.size(); j != e; ++j)
2006             ScalarMap.erase(Globals[j]);
2007           Node.makeNodeDead();
2008           ++NumTrivialGlobalDNE;
2009         }
2010       }
2011     }
2012
2013     if (Node.getNodeFlags() == 0 && Node.hasNoReferrers()) {
2014       // This node is dead!
2015       NI = Nodes.erase(NI);    // Erase & remove from node list.
2016       ++NumTrivialDNE;
2017     } else {
2018       ++NI;
2019     }
2020   }
2021
2022   removeIdenticalCalls(FunctionCalls);
2023   removeIdenticalCalls(AuxFunctionCalls);
2024 }
2025
2026
2027 /// markReachableNodes - This method recursively traverses the specified
2028 /// DSNodes, marking any nodes which are reachable.  All reachable nodes it adds
2029 /// to the set, which allows it to only traverse visited nodes once.
2030 ///
2031 void DSNode::markReachableNodes(hash_set<const DSNode*> &ReachableNodes) const {
2032   if (this == 0) return;
2033   assert(getForwardNode() == 0 && "Cannot mark a forwarded node!");
2034   if (ReachableNodes.insert(this).second)        // Is newly reachable?
2035     for (DSNode::const_edge_iterator I = edge_begin(), E = edge_end();
2036          I != E; ++I)
2037       I->getNode()->markReachableNodes(ReachableNodes);
2038 }
2039
2040 void DSCallSite::markReachableNodes(hash_set<const DSNode*> &Nodes) const {
2041   getRetVal().getNode()->markReachableNodes(Nodes);
2042   if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes);
2043
2044   for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i)
2045     getPtrArg(i).getNode()->markReachableNodes(Nodes);
2046 }
2047
2048 // CanReachAliveNodes - Simple graph walker that recursively traverses the graph
2049 // looking for a node that is marked alive.  If an alive node is found, return
2050 // true, otherwise return false.  If an alive node is reachable, this node is
2051 // marked as alive...
2052 //
2053 static bool CanReachAliveNodes(DSNode *N, hash_set<const DSNode*> &Alive,
2054                                hash_set<const DSNode*> &Visited,
2055                                bool IgnoreGlobals) {
2056   if (N == 0) return false;
2057   assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!");
2058
2059   // If this is a global node, it will end up in the globals graph anyway, so we
2060   // don't need to worry about it.
2061   if (IgnoreGlobals && N->isGlobalNode()) return false;
2062
2063   // If we know that this node is alive, return so!
2064   if (Alive.count(N)) return true;
2065
2066   // Otherwise, we don't think the node is alive yet, check for infinite
2067   // recursion.
2068   if (Visited.count(N)) return false;  // Found a cycle
2069   Visited.insert(N);   // No recursion, insert into Visited...
2070
2071   for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I)
2072     if (CanReachAliveNodes(I->getNode(), Alive, Visited, IgnoreGlobals)) {
2073       N->markReachableNodes(Alive);
2074       return true;
2075     }
2076   return false;
2077 }
2078
2079 // CallSiteUsesAliveArgs - Return true if the specified call site can reach any
2080 // alive nodes.
2081 //
2082 static bool CallSiteUsesAliveArgs(const DSCallSite &CS,
2083                                   hash_set<const DSNode*> &Alive,
2084                                   hash_set<const DSNode*> &Visited,
2085                                   bool IgnoreGlobals) {
2086   if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited,
2087                          IgnoreGlobals))
2088     return true;
2089   if (CS.isIndirectCall() &&
2090       CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited, IgnoreGlobals))
2091     return true;
2092   for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
2093     if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited,
2094                            IgnoreGlobals))
2095       return true;
2096   return false;
2097 }
2098
2099 // removeDeadNodes - Use a more powerful reachability analysis to eliminate
2100 // subgraphs that are unreachable.  This often occurs because the data
2101 // structure doesn't "escape" into it's caller, and thus should be eliminated
2102 // from the caller's graph entirely.  This is only appropriate to use when
2103 // inlining graphs.
2104 //
2105 void DSGraph::removeDeadNodes(unsigned Flags) {
2106   DEBUG(AssertGraphOK(); if (GlobalsGraph) GlobalsGraph->AssertGraphOK());
2107
2108   // Reduce the amount of work we have to do... remove dummy nodes left over by
2109   // merging...
2110   removeTriviallyDeadNodes();
2111
2112   TIME_REGION(X, "removeDeadNodes");
2113
2114   // FIXME: Merge non-trivially identical call nodes...
2115
2116   // Alive - a set that holds all nodes found to be reachable/alive.
2117   hash_set<const DSNode*> Alive;
2118   std::vector<std::pair<Value*, DSNode*> > GlobalNodes;
2119
2120   // Copy and merge all information about globals to the GlobalsGraph if this is
2121   // not a final pass (where unreachable globals are removed).
2122   //
2123   // Strip all alloca bits since the current function is only for the BU pass.
2124   // Strip all incomplete bits since they are short-lived properties and they
2125   // will be correctly computed when rematerializing nodes into the functions.
2126   //
2127   ReachabilityCloner GGCloner(*GlobalsGraph, *this, DSGraph::StripAllocaBit |
2128                               DSGraph::StripIncompleteBit);
2129
2130   // Mark all nodes reachable by (non-global) scalar nodes as alive...
2131 { TIME_REGION(Y, "removeDeadNodes:scalarscan");
2132   for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end();
2133        I != E; ++I)
2134     if (isa<GlobalValue>(I->first)) {             // Keep track of global nodes
2135       assert(!I->second.isNull() && "Null global node?");
2136       assert(I->second.getNode()->isGlobalNode() && "Should be a global node!");
2137       GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode()));
2138
2139       // Make sure that all globals are cloned over as roots.
2140       if (!(Flags & DSGraph::RemoveUnreachableGlobals) && GlobalsGraph) {
2141         DSGraph::ScalarMapTy::iterator SMI =
2142           GlobalsGraph->getScalarMap().find(I->first);
2143         if (SMI != GlobalsGraph->getScalarMap().end())
2144           GGCloner.merge(SMI->second, I->second);
2145         else
2146           GGCloner.getClonedNH(I->second);
2147       }
2148     } else {
2149       I->second.getNode()->markReachableNodes(Alive);
2150     }
2151 }
2152
2153   // The return values are alive as well.
2154   for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end();
2155        I != E; ++I)
2156     I->second.getNode()->markReachableNodes(Alive);
2157
2158   // Mark any nodes reachable by primary calls as alive...
2159   for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I)
2160     I->markReachableNodes(Alive);
2161
2162
2163   // Now find globals and aux call nodes that are already live or reach a live
2164   // value (which makes them live in turn), and continue till no more are found.
2165   //
2166   bool Iterate;
2167   hash_set<const DSNode*> Visited;
2168   hash_set<const DSCallSite*> AuxFCallsAlive;
2169   do {
2170     Visited.clear();
2171     // If any global node points to a non-global that is "alive", the global is
2172     // "alive" as well...  Remove it from the GlobalNodes list so we only have
2173     // unreachable globals in the list.
2174     //
2175     Iterate = false;
2176     if (!(Flags & DSGraph::RemoveUnreachableGlobals))
2177       for (unsigned i = 0; i != GlobalNodes.size(); ++i)
2178         if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited,
2179                                Flags & DSGraph::RemoveUnreachableGlobals)) {
2180           std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to...
2181           GlobalNodes.pop_back();                          // erase efficiently
2182           Iterate = true;
2183         }
2184
2185     // Mark only unresolvable call nodes for moving to the GlobalsGraph since
2186     // call nodes that get resolved will be difficult to remove from that graph.
2187     // The final unresolved call nodes must be handled specially at the end of
2188     // the BU pass (i.e., in main or other roots of the call graph).
2189     for (afc_iterator CI = afc_begin(), E = afc_end(); CI != E; ++CI)
2190       if (!AuxFCallsAlive.count(&*CI) &&
2191           (CI->isIndirectCall()
2192            || CallSiteUsesAliveArgs(*CI, Alive, Visited,
2193                                   Flags & DSGraph::RemoveUnreachableGlobals))) {
2194         CI->markReachableNodes(Alive);
2195         AuxFCallsAlive.insert(&*CI);
2196         Iterate = true;
2197       }
2198   } while (Iterate);
2199
2200   // Move dead aux function calls to the end of the list
2201   for (std::list<DSCallSite>::iterator CI = AuxFunctionCalls.begin(),
2202          E = AuxFunctionCalls.end(); CI != E; )
2203     if (AuxFCallsAlive.count(&*CI))
2204       ++CI;
2205     else {
2206       // Copy and merge global nodes and dead aux call nodes into the
2207       // GlobalsGraph, and all nodes reachable from those nodes.  Update their
2208       // target pointers using the GGCloner.
2209       //
2210       if (!(Flags & DSGraph::RemoveUnreachableGlobals))
2211         GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(*CI, GGCloner));
2212
2213       AuxFunctionCalls.erase(CI++);
2214     }
2215
2216   // We are finally done with the GGCloner so we can destroy it.
2217   GGCloner.destroy();
2218
2219   // At this point, any nodes which are visited, but not alive, are nodes
2220   // which can be removed.  Loop over all nodes, eliminating completely
2221   // unreachable nodes.
2222   //
2223   std::vector<DSNode*> DeadNodes;
2224   DeadNodes.reserve(Nodes.size());
2225   for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E;) {
2226     DSNode *N = NI++;
2227     assert(!N->isForwarding() && "Forwarded node in nodes list?");
2228
2229     if (!Alive.count(N)) {
2230       Nodes.remove(N);
2231       assert(!N->isForwarding() && "Cannot remove a forwarding node!");
2232       DeadNodes.push_back(N);
2233       N->dropAllReferences();
2234       ++NumDNE;
2235     }
2236   }
2237
2238   // Remove all unreachable globals from the ScalarMap.
2239   // If flag RemoveUnreachableGlobals is set, GlobalNodes has only dead nodes.
2240   // In either case, the dead nodes will not be in the set Alive.
2241   for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
2242     if (!Alive.count(GlobalNodes[i].second))
2243       ScalarMap.erase(GlobalNodes[i].first);
2244     else
2245       assert((Flags & DSGraph::RemoveUnreachableGlobals) && "non-dead global");
2246
2247   // Delete all dead nodes now since their referrer counts are zero.
2248   for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i)
2249     delete DeadNodes[i];
2250
2251   DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK());
2252 }
2253
2254 void DSGraph::AssertNodeContainsGlobal(const DSNode *N, GlobalValue *GV) const {
2255   assert(std::find(N->globals_begin(),N->globals_end(), GV) !=
2256          N->globals_end() && "Global value not in node!");
2257 }
2258
2259 void DSGraph::AssertCallSiteInGraph(const DSCallSite &CS) const {
2260   if (CS.isIndirectCall()) {
2261     AssertNodeInGraph(CS.getCalleeNode());
2262 #if 0
2263     if (CS.getNumPtrArgs() && CS.getCalleeNode() == CS.getPtrArg(0).getNode() &&
2264         CS.getCalleeNode() && CS.getCalleeNode()->getGlobals().empty())
2265       DOUT << "WARNING: WEIRD CALL SITE FOUND!\n";
2266 #endif
2267   }
2268   AssertNodeInGraph(CS.getRetVal().getNode());
2269   for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j)
2270     AssertNodeInGraph(CS.getPtrArg(j).getNode());
2271 }
2272
2273 void DSGraph::AssertCallNodesInGraph() const {
2274   for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I)
2275     AssertCallSiteInGraph(*I);
2276 }
2277 void DSGraph::AssertAuxCallNodesInGraph() const {
2278   for (afc_iterator I = afc_begin(), E = afc_end(); I != E; ++I)
2279     AssertCallSiteInGraph(*I);
2280 }
2281
2282 void DSGraph::AssertGraphOK() const {
2283   for (node_const_iterator NI = node_begin(), E = node_end(); NI != E; ++NI)
2284     NI->assertOK();
2285
2286   for (ScalarMapTy::const_iterator I = ScalarMap.begin(),
2287          E = ScalarMap.end(); I != E; ++I) {
2288     assert(!I->second.isNull() && "Null node in scalarmap!");
2289     AssertNodeInGraph(I->second.getNode());
2290     if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) {
2291       assert(I->second.getNode()->isGlobalNode() &&
2292              "Global points to node, but node isn't global?");
2293       AssertNodeContainsGlobal(I->second.getNode(), GV);
2294     }
2295   }
2296   AssertCallNodesInGraph();
2297   AssertAuxCallNodesInGraph();
2298
2299   // Check that all pointer arguments to any functions in this graph have
2300   // destinations.
2301   for (ReturnNodesTy::const_iterator RI = ReturnNodes.begin(),
2302          E = ReturnNodes.end();
2303        RI != E; ++RI) {
2304     Function &F = *RI->first;
2305     for (Function::arg_iterator AI = F.arg_begin(); AI != F.arg_end(); ++AI)
2306       if (isPointerType(AI->getType()))
2307         assert(!getNodeForValue(AI).isNull() &&
2308                "Pointer argument must be in the scalar map!");
2309   }
2310 }
2311
2312 /// computeNodeMapping - Given roots in two different DSGraphs, traverse the
2313 /// nodes reachable from the two graphs, computing the mapping of nodes from the
2314 /// first to the second graph.  This mapping may be many-to-one (i.e. the first
2315 /// graph may have multiple nodes representing one node in the second graph),
2316 /// but it will not work if there is a one-to-many or many-to-many mapping.
2317 ///
2318 void DSGraph::computeNodeMapping(const DSNodeHandle &NH1,
2319                                  const DSNodeHandle &NH2, NodeMapTy &NodeMap,
2320                                  bool StrictChecking) {
2321   DSNode *N1 = NH1.getNode(), *N2 = NH2.getNode();
2322   if (N1 == 0 || N2 == 0) return;
2323
2324   DSNodeHandle &Entry = NodeMap[N1];
2325   if (!Entry.isNull()) {
2326     // Termination of recursion!
2327     if (StrictChecking) {
2328       assert(Entry.getNode() == N2 && "Inconsistent mapping detected!");
2329       assert((Entry.getOffset() == (NH2.getOffset()-NH1.getOffset()) ||
2330               Entry.getNode()->isNodeCompletelyFolded()) &&
2331              "Inconsistent mapping detected!");
2332     }
2333     return;
2334   }
2335
2336   Entry.setTo(N2, NH2.getOffset()-NH1.getOffset());
2337
2338   // Loop over all of the fields that N1 and N2 have in common, recursively
2339   // mapping the edges together now.
2340   int N2Idx = NH2.getOffset()-NH1.getOffset();
2341   unsigned N2Size = N2->getSize();
2342   if (N2Size == 0) return;   // No edges to map to.
2343
2344   for (unsigned i = 0, e = N1->getSize(); i < e; i += DS::PointerSize) {
2345     const DSNodeHandle &N1NH = N1->getLink(i);
2346     // Don't call N2->getLink if not needed (avoiding crash if N2Idx is not
2347     // aligned right).
2348     if (!N1NH.isNull()) {
2349       if (unsigned(N2Idx)+i < N2Size)
2350         computeNodeMapping(N1NH, N2->getLink(N2Idx+i), NodeMap);
2351       else
2352         computeNodeMapping(N1NH,
2353                            N2->getLink(unsigned(N2Idx+i) % N2Size), NodeMap);
2354     }
2355   }
2356 }
2357
2358
2359 /// computeGToGGMapping - Compute the mapping of nodes in the global graph to
2360 /// nodes in this graph.
2361 void DSGraph::computeGToGGMapping(NodeMapTy &NodeMap) {
2362   DSGraph &GG = *getGlobalsGraph();
2363
2364   DSScalarMap &SM = getScalarMap();
2365   for (DSScalarMap::global_iterator I = SM.global_begin(),
2366          E = SM.global_end(); I != E; ++I)
2367     DSGraph::computeNodeMapping(SM[*I], GG.getNodeForValue(*I), NodeMap);
2368 }
2369
2370 /// computeGGToGMapping - Compute the mapping of nodes in the global graph to
2371 /// nodes in this graph.  Note that any uses of this method are probably bugs,
2372 /// unless it is known that the globals graph has been merged into this graph!
2373 void DSGraph::computeGGToGMapping(InvNodeMapTy &InvNodeMap) {
2374   NodeMapTy NodeMap;
2375   computeGToGGMapping(NodeMap);
2376
2377   while (!NodeMap.empty()) {
2378     InvNodeMap.insert(std::make_pair(NodeMap.begin()->second,
2379                                      NodeMap.begin()->first));
2380     NodeMap.erase(NodeMap.begin());
2381   }
2382 }
2383
2384
2385 /// computeCalleeCallerMapping - Given a call from a function in the current
2386 /// graph to the 'Callee' function (which lives in 'CalleeGraph'), compute the
2387 /// mapping of nodes from the callee to nodes in the caller.
2388 void DSGraph::computeCalleeCallerMapping(DSCallSite CS, const Function &Callee,
2389                                          DSGraph &CalleeGraph,
2390                                          NodeMapTy &NodeMap) {
2391
2392   DSCallSite CalleeArgs =
2393     CalleeGraph.getCallSiteForArguments(const_cast<Function&>(Callee));
2394
2395   computeNodeMapping(CalleeArgs.getRetVal(), CS.getRetVal(), NodeMap);
2396
2397   unsigned NumArgs = CS.getNumPtrArgs();
2398   if (NumArgs > CalleeArgs.getNumPtrArgs())
2399     NumArgs = CalleeArgs.getNumPtrArgs();
2400
2401   for (unsigned i = 0; i != NumArgs; ++i)
2402     computeNodeMapping(CalleeArgs.getPtrArg(i), CS.getPtrArg(i), NodeMap);
2403
2404   // Map the nodes that are pointed to by globals.
2405   DSScalarMap &CalleeSM = CalleeGraph.getScalarMap();
2406   DSScalarMap &CallerSM = getScalarMap();
2407
2408   if (CalleeSM.global_size() >= CallerSM.global_size()) {
2409     for (DSScalarMap::global_iterator GI = CallerSM.global_begin(),
2410            E = CallerSM.global_end(); GI != E; ++GI)
2411       if (CalleeSM.global_count(*GI))
2412         computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap);
2413   } else {
2414     for (DSScalarMap::global_iterator GI = CalleeSM.global_begin(),
2415            E = CalleeSM.global_end(); GI != E; ++GI)
2416       if (CallerSM.global_count(*GI))
2417         computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap);
2418   }
2419 }
2420
2421 /// updateFromGlobalGraph - This function rematerializes global nodes and
2422 /// nodes reachable from them from the globals graph into the current graph.
2423 ///
2424 void DSGraph::updateFromGlobalGraph() {
2425   TIME_REGION(X, "updateFromGlobalGraph");
2426   ReachabilityCloner RC(*this, *GlobalsGraph, 0);
2427
2428   // Clone the non-up-to-date global nodes into this graph.
2429   for (DSScalarMap::global_iterator I = getScalarMap().global_begin(),
2430          E = getScalarMap().global_end(); I != E; ++I) {
2431     DSScalarMap::iterator It = GlobalsGraph->ScalarMap.find(*I);
2432     if (It != GlobalsGraph->ScalarMap.end())
2433       RC.merge(getNodeForValue(*I), It->second);
2434   }
2435 }