lib/Target/Hexagon/HexagonCommonGEP.cpp

   1 //===--- HexagonCommonGEP.cpp ---------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #define DEBUG_TYPE "commgep"
  11
  12 #include "llvm/Pass.h"
  13 #include "llvm/ADT/FoldingSet.h"
  14 #include "llvm/ADT/STLExtras.h"
  15 #include "llvm/Analysis/LoopInfo.h"
  16 #include "llvm/Analysis/PostDominators.h"
  17 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
  18 #include "llvm/IR/Constants.h"
  19 #include "llvm/IR/Dominators.h"
  20 #include "llvm/IR/Function.h"
  21 #include "llvm/IR/Instructions.h"
  22 #include "llvm/IR/Verifier.h"
  23 #include "llvm/Support/Allocator.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include "llvm/Transforms/Scalar.h"
  28 #include "llvm/Transforms/Utils/Local.h"
  29
  30 #include <map>
  31 #include <set>
  32 #include <vector>
  33
  34 #include "HexagonTargetMachine.h"
  35
  36 using namespace llvm;
  37
  38 static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true),
  39   cl::Hidden, cl::ZeroOrMore);
  40
  41 static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden,
  42   cl::ZeroOrMore);
  43
  44 static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true),
  45   cl::Hidden, cl::ZeroOrMore);
  46
  47 namespace llvm {
  48   void initializeHexagonCommonGEPPass(PassRegistry&);
  49 }
  50
  51 namespace {
  52   struct GepNode;
  53   typedef std::set<GepNode*> NodeSet;
  54   typedef std::map<GepNode*,Value*> NodeToValueMap;
  55   typedef std::vector<GepNode*> NodeVect;
  56   typedef std::map<GepNode*,NodeVect> NodeChildrenMap;
  57   typedef std::set<Use*> UseSet;
  58   typedef std::map<GepNode*,UseSet> NodeToUsesMap;
  59
  60   // Numbering map for gep nodes. Used to keep track of ordering for
  61   // gep nodes.
  62   struct NodeNumbering : public std::map<const GepNode*,unsigned> {
  63   };
  64
  65   struct NodeOrdering : public NodeNumbering {
  66     NodeOrdering() : LastNum(0) {}
  67 #ifdef _MSC_VER
  68     void special_insert_for_special_msvc(const GepNode *N)
  69 #else
  70     using NodeNumbering::insert;
  71     void insert(const GepNode* N)
  72 #endif
  73     {
  74       insert(std::make_pair(N, ++LastNum));
  75     }
  76     bool operator() (const GepNode* N1, const GepNode *N2) const {
  77       const_iterator F1 = find(N1), F2 = find(N2);
  78       assert(F1 != end() && F2 != end());
  79       return F1->second < F2->second;
  80     }
  81   private:
  82     unsigned LastNum;
  83   };
  84
  85
  86   class HexagonCommonGEP : public FunctionPass {
  87   public:
  88     static char ID;
  89     HexagonCommonGEP() : FunctionPass(ID) {
  90       initializeHexagonCommonGEPPass(*PassRegistry::getPassRegistry());
  91     }
  92     virtual bool runOnFunction(Function &F);
  93     virtual const char *getPassName() const {
  94       return "Hexagon Common GEP";
  95     }
  96
  97     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  98       AU.addRequired<DominatorTreeWrapperPass>();
  99       AU.addPreserved<DominatorTreeWrapperPass>();
 100       AU.addRequired<PostDominatorTree>();
 101       AU.addPreserved<PostDominatorTree>();
 102       AU.addRequired<LoopInfoWrapperPass>();
 103       AU.addPreserved<LoopInfoWrapperPass>();
 104       FunctionPass::getAnalysisUsage(AU);
 105     }
 106
 107   private:
 108     typedef std::map<Value*,GepNode*> ValueToNodeMap;
 109     typedef std::vector<Value*> ValueVect;
 110     typedef std::map<GepNode*,ValueVect> NodeToValuesMap;
 111
 112     void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order);
 113     bool isHandledGepForm(GetElementPtrInst *GepI);
 114     void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM);
 115     void collect();
 116     void common();
 117
 118     BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM,
 119                                      NodeToValueMap &Loc);
 120     BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM,
 121                                         NodeToValueMap &Loc);
 122     bool isInvariantIn(Value *Val, Loop *L);
 123     bool isInvariantIn(GepNode *Node, Loop *L);
 124     bool isInMainPath(BasicBlock *B, Loop *L);
 125     BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM,
 126                                     NodeToValueMap &Loc);
 127     void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc);
 128     void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM,
 129                                 NodeToValueMap &Loc);
 130     void computeNodePlacement(NodeToValueMap &Loc);
 131
 132     Value *fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
 133                         BasicBlock *LocB);
 134     void getAllUsersForNode(GepNode *Node, ValueVect &Values,
 135                             NodeChildrenMap &NCM);
 136     void materialize(NodeToValueMap &Loc);
 137
 138     void removeDeadCode();
 139
 140     NodeVect Nodes;
 141     NodeToUsesMap Uses;
 142     NodeOrdering NodeOrder;   // Node ordering, for deterministic behavior.
 143     SpecificBumpPtrAllocator<GepNode> *Mem;
 144     LLVMContext *Ctx;
 145     LoopInfo *LI;
 146     DominatorTree *DT;
 147     PostDominatorTree *PDT;
 148     Function *Fn;
 149   };
 150 }
 151
 152
 153 char HexagonCommonGEP::ID = 0;
 154 INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
 155       false, false)
 156 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 157 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
 158 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 159 INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
 160       false, false)
 161
 162 namespace {
 163   struct GepNode {
 164     enum {
 165       None      = 0,
 166       Root      = 0x01,
 167       Internal  = 0x02,
 168       Used      = 0x04
 169     };
 170
 171     uint32_t Flags;
 172     union {
 173       GepNode *Parent;
 174       Value *BaseVal;
 175     };
 176     Value *Idx;
 177     Type *PTy;  // Type of the pointer operand.
 178
 179     GepNode() : Flags(0), Parent(0), Idx(0), PTy(0) {}
 180     GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) {
 181       if (Flags & Root)
 182         BaseVal = N->BaseVal;
 183       else
 184         Parent = N->Parent;
 185     }
 186     friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN);
 187   };
 188
 189
 190   Type *next_type(Type *Ty, Value *Idx) {
 191     // Advance the type.
 192     if (!Ty->isStructTy()) {
 193       Type *NexTy = cast<SequentialType>(Ty)->getElementType();
 194       return NexTy;
 195     }
 196     // Otherwise it is a struct type.
 197     ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
 198     assert(CI && "Struct type with non-constant index");
 199     int64_t i = CI->getValue().getSExtValue();
 200     Type *NextTy = cast<StructType>(Ty)->getElementType(i);
 201     return NextTy;
 202   }
 203
 204
 205   raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN) {
 206     OS << "{ {";
 207     bool Comma = false;
 208     if (GN.Flags & GepNode::Root) {
 209       OS << "root";
 210       Comma = true;
 211     }
 212     if (GN.Flags & GepNode::Internal) {
 213       if (Comma)
 214         OS << ',';
 215       OS << "internal";
 216       Comma = true;
 217     }
 218     if (GN.Flags & GepNode::Used) {
 219       if (Comma)
 220         OS << ',';
 221       OS << "used";
 222       Comma = true;
 223     }
 224     OS << "} ";
 225     if (GN.Flags & GepNode::Root)
 226       OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')';
 227     else
 228       OS << "Parent:" << GN.Parent;
 229
 230     OS << " Idx:";
 231     if (ConstantInt *CI = dyn_cast<ConstantInt>(GN.Idx))
 232       OS << CI->getValue().getSExtValue();
 233     else if (GN.Idx->hasName())
 234       OS << GN.Idx->getName();
 235     else
 236       OS << "<anon> =" << *GN.Idx;
 237
 238     OS << " PTy:";
 239     if (GN.PTy->isStructTy()) {
 240       StructType *STy = cast<StructType>(GN.PTy);
 241       if (!STy->isLiteral())
 242         OS << GN.PTy->getStructName();
 243       else
 244         OS << "<anon-struct>:" << *STy;
 245     }
 246     else
 247       OS << *GN.PTy;
 248     OS << " }";
 249     return OS;
 250   }
 251
 252
 253   template <typename NodeContainer>
 254   void dump_node_container(raw_ostream &OS, const NodeContainer &S) {
 255     typedef typename NodeContainer::const_iterator const_iterator;
 256     for (const_iterator I = S.begin(), E = S.end(); I != E; ++I)
 257       OS << *I << ' ' << **I << '\n';
 258   }
 259
 260   raw_ostream &operator<< (raw_ostream &OS,
 261                            const NodeVect &S) LLVM_ATTRIBUTE_UNUSED;
 262   raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) {
 263     dump_node_container(OS, S);
 264     return OS;
 265   }
 266
 267
 268   raw_ostream &operator<< (raw_ostream &OS,
 269                            const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED;
 270   raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){
 271     typedef NodeToUsesMap::const_iterator const_iterator;
 272     for (const_iterator I = M.begin(), E = M.end(); I != E; ++I) {
 273       const UseSet &Us = I->second;
 274       OS << I->first << " -> #" << Us.size() << '{';
 275       for (UseSet::const_iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
 276         User *R = (*J)->getUser();
 277         if (R->hasName())
 278           OS << ' ' << R->getName();
 279         else
 280           OS << " <?>(" << *R << ')';
 281       }
 282       OS << " }\n";
 283     }
 284     return OS;
 285   }
 286
 287
 288   struct in_set {
 289     in_set(const NodeSet &S) : NS(S) {}
 290     bool operator() (GepNode *N) const {
 291       return NS.find(N) != NS.end();
 292     }
 293   private:
 294     const NodeSet &NS;
 295   };
 296 }
 297
 298
 299 inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) {
 300   return A.Allocate();
 301 }
 302
 303
 304 void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
 305       ValueVect &Order) {
 306   // Compute block ordering for a typical DT-based traversal of the flow
 307   // graph: "before visiting a block, all of its dominators must have been
 308   // visited".
 309
 310   Order.push_back(Root);
 311   DomTreeNode *DTN = DT->getNode(Root);
 312   typedef GraphTraits<DomTreeNode*> GTN;
 313   typedef GTN::ChildIteratorType Iter;
 314   for (Iter I = GTN::child_begin(DTN), E = GTN::child_end(DTN); I != E; ++I)
 315     getBlockTraversalOrder((*I)->getBlock(), Order);
 316 }
 317
 318
 319 bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
 320   // No vector GEPs.
 321   if (!GepI->getType()->isPointerTy())
 322     return false;
 323   // No GEPs without any indices.  (Is this possible?)
 324   if (GepI->idx_begin() == GepI->idx_end())
 325     return false;
 326   return true;
 327 }
 328
 329
 330 void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
 331       ValueToNodeMap &NM) {
 332   DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n');
 333   GepNode *N = new (*Mem) GepNode;
 334   Value *PtrOp = GepI->getPointerOperand();
 335   ValueToNodeMap::iterator F = NM.find(PtrOp);
 336   if (F == NM.end()) {
 337     N->BaseVal = PtrOp;
 338     N->Flags |= GepNode::Root;
 339   } else {
 340     // If PtrOp was a GEP instruction, it must have already been processed.
 341     // The ValueToNodeMap entry for it is the last gep node in the generated
 342     // chain. Link to it here.
 343     N->Parent = F->second;
 344   }
 345   N->PTy = PtrOp->getType();
 346   N->Idx = *GepI->idx_begin();
 347
 348   // Collect the list of users of this GEP instruction. Will add it to the
 349   // last node created for it.
 350   UseSet Us;
 351   for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end();
 352        UI != UE; ++UI) {
 353     // Check if this gep is used by anything other than other geps that
 354     // we will process.
 355     if (isa<GetElementPtrInst>(*UI)) {
 356       GetElementPtrInst *UserG = cast<GetElementPtrInst>(*UI);
 357       if (isHandledGepForm(UserG))
 358         continue;
 359     }
 360     Us.insert(&UI.getUse());
 361   }
 362   Nodes.push_back(N);
 363 #ifdef _MSC_VER
 364   NodeOrder.special_insert_for_special_msvc(N);
 365 #else
 366   NodeOrder.insert(N);
 367 #endif
 368
 369   // Skip the first index operand, since we only handle 0. This dereferences
 370   // the pointer operand.
 371   GepNode *PN = N;
 372   Type *PtrTy = cast<PointerType>(PtrOp->getType())->getElementType();
 373   for (User::op_iterator OI = GepI->idx_begin()+1, OE = GepI->idx_end();
 374        OI != OE; ++OI) {
 375     Value *Op = *OI;
 376     GepNode *Nx = new (*Mem) GepNode;
 377     Nx->Parent = PN;  // Link Nx to the previous node.
 378     Nx->Flags |= GepNode::Internal;
 379     Nx->PTy = PtrTy;
 380     Nx->Idx = Op;
 381     Nodes.push_back(Nx);
 382 #ifdef _MSC_VER
 383     NodeOrder.special_insert_for_special_msvc(Nx);
 384 #else
 385     NodeOrder.insert(Nx);
 386 #endif
 387     PN = Nx;
 388
 389     PtrTy = next_type(PtrTy, Op);
 390   }
 391
 392   // After last node has been created, update the use information.
 393   if (!Us.empty()) {
 394     PN->Flags |= GepNode::Used;
 395     Uses[PN].insert(Us.begin(), Us.end());
 396   }
 397
 398   // Link the last node with the originating GEP instruction. This is to
 399   // help with linking chained GEP instructions.
 400   NM.insert(std::make_pair(GepI, PN));
 401 }
 402
 403
 404 void HexagonCommonGEP::collect() {
 405   // Establish depth-first traversal order of the dominator tree.
 406   ValueVect BO;
 407   getBlockTraversalOrder(Fn->begin(), BO);
 408
 409   // The creation of gep nodes requires DT-traversal. When processing a GEP
 410   // instruction that uses another GEP instruction as the base pointer, the
 411   // gep node for the base pointer should already exist.
 412   ValueToNodeMap NM;
 413   for (ValueVect::iterator I = BO.begin(), E = BO.end(); I != E; ++I) {
 414     BasicBlock *B = cast<BasicBlock>(*I);
 415     for (BasicBlock::iterator J = B->begin(), F = B->end(); J != F; ++J) {
 416       if (!isa<GetElementPtrInst>(J))
 417         continue;
 418       GetElementPtrInst *GepI = cast<GetElementPtrInst>(J);
 419       if (isHandledGepForm(GepI))
 420         processGepInst(GepI, NM);
 421     }
 422   }
 423
 424   DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes);
 425 }
 426
 427
 428 namespace {
 429   void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM,
 430         NodeVect &Roots) {
 431     typedef NodeVect::const_iterator const_iterator;
 432     for (const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
 433       GepNode *N = *I;
 434       if (N->Flags & GepNode::Root) {
 435         Roots.push_back(N);
 436         continue;
 437       }
 438       GepNode *PN = N->Parent;
 439       NCM[PN].push_back(N);
 440     }
 441   }
 442
 443   void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM, NodeSet &Nodes) {
 444     NodeVect Work;
 445     Work.push_back(Root);
 446     Nodes.insert(Root);
 447
 448     while (!Work.empty()) {
 449       NodeVect::iterator First = Work.begin();
 450       GepNode *N = *First;
 451       Work.erase(First);
 452       NodeChildrenMap::iterator CF = NCM.find(N);
 453       if (CF != NCM.end()) {
 454         Work.insert(Work.end(), CF->second.begin(), CF->second.end());
 455         Nodes.insert(CF->second.begin(), CF->second.end());
 456       }
 457     }
 458   }
 459 }
 460
 461
 462 namespace {
 463   typedef std::set<NodeSet> NodeSymRel;
 464   typedef std::pair<GepNode*,GepNode*> NodePair;
 465   typedef std::set<NodePair> NodePairSet;
 466
 467   const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) {
 468     for (NodeSymRel::iterator I = Rel.begin(), E = Rel.end(); I != E; ++I)
 469       if (I->count(N))
 470         return &*I;
 471     return 0;
 472   }
 473
 474   // Create an ordered pair of GepNode pointers. The pair will be used in
 475   // determining equality. The only purpose of the ordering is to eliminate
 476   // duplication due to the commutativity of equality/non-equality.
 477   NodePair node_pair(GepNode *N1, GepNode *N2) {
 478     uintptr_t P1 = uintptr_t(N1), P2 = uintptr_t(N2);
 479     if (P1 <= P2)
 480       return std::make_pair(N1, N2);
 481     return std::make_pair(N2, N1);
 482   }
 483
 484   unsigned node_hash(GepNode *N) {
 485     // Include everything except flags and parent.
 486     FoldingSetNodeID ID;
 487     ID.AddPointer(N->Idx);
 488     ID.AddPointer(N->PTy);
 489     return ID.ComputeHash();
 490   }
 491
 492   bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq, NodePairSet &Ne) {
 493     // Don't cache the result for nodes with different hashes. The hash
 494     // comparison is fast enough.
 495     if (node_hash(N1) != node_hash(N2))
 496       return false;
 497
 498     NodePair NP = node_pair(N1, N2);
 499     NodePairSet::iterator FEq = Eq.find(NP);
 500     if (FEq != Eq.end())
 501       return true;
 502     NodePairSet::iterator FNe = Ne.find(NP);
 503     if (FNe != Ne.end())
 504       return false;
 505     // Not previously compared.
 506     bool Root1 = N1->Flags & GepNode::Root;
 507     bool Root2 = N2->Flags & GepNode::Root;
 508     NodePair P = node_pair(N1, N2);
 509     // If the Root flag has different values, the nodes are different.
 510     // If both nodes are root nodes, but their base pointers differ,
 511     // they are different.
 512     if (Root1 != Root2 || (Root1 && N1->BaseVal != N2->BaseVal)) {
 513       Ne.insert(P);
 514       return false;
 515     }
 516     // Here the root flags are identical, and for root nodes the
 517     // base pointers are equal, so the root nodes are equal.
 518     // For non-root nodes, compare their parent nodes.
 519     if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) {
 520       Eq.insert(P);
 521       return true;
 522     }
 523     return false;
 524   }
 525 }
 526
 527
 528 void HexagonCommonGEP::common() {
 529   // The essence of this commoning is finding gep nodes that are equal.
 530   // To do this we need to compare all pairs of nodes. To save time,
 531   // first, partition the set of all nodes into sets of potentially equal
 532   // nodes, and then compare pairs from within each partition.
 533   typedef std::map<unsigned,NodeSet> NodeSetMap;
 534   NodeSetMap MaybeEq;
 535
 536   for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
 537     GepNode *N = *I;
 538     unsigned H = node_hash(N);
 539     MaybeEq[H].insert(N);
 540   }
 541
 542   // Compute the equivalence relation for the gep nodes.  Use two caches,
 543   // one for equality and the other for non-equality.
 544   NodeSymRel EqRel;  // Equality relation (as set of equivalence classes).
 545   NodePairSet Eq, Ne;  // Caches.
 546   for (NodeSetMap::iterator I = MaybeEq.begin(), E = MaybeEq.end();
 547        I != E; ++I) {
 548     NodeSet &S = I->second;
 549     for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) {
 550       GepNode *N = *NI;
 551       // If node already has a class, then the class must have been created
 552       // in a prior iteration of this loop. Since equality is transitive,
 553       // nothing more will be added to that class, so skip it.
 554       if (node_class(N, EqRel))
 555         continue;
 556
 557       // Create a new class candidate now.
 558       NodeSet C;
 559       for (NodeSet::iterator NJ = std::next(NI); NJ != NE; ++NJ)
 560         if (node_eq(N, *NJ, Eq, Ne))
 561           C.insert(*NJ);
 562       // If Tmp is empty, N would be the only element in it. Don't bother
 563       // creating a class for it then.
 564       if (!C.empty()) {
 565         C.insert(N);  // Finalize the set before adding it to the relation.
 566         std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(C);
 567         (void)Ins;
 568         assert(Ins.second && "Cannot add a class");
 569       }
 570     }
 571   }
 572
 573   DEBUG({
 574     dbgs() << "Gep node equality:\n";
 575     for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I)
 576       dbgs() << "{ " << I->first << ", " << I->second << " }\n";
 577
 578     dbgs() << "Gep equivalence classes:\n";
 579     for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
 580       dbgs() << '{';
 581       const NodeSet &S = *I;
 582       for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) {
 583         if (J != S.begin())
 584           dbgs() << ',';
 585         dbgs() << ' ' << *J;
 586       }
 587       dbgs() << " }\n";
 588     }
 589   });
 590
 591
 592   // Create a projection from a NodeSet to the minimal element in it.
 593   typedef std::map<const NodeSet*,GepNode*> ProjMap;
 594   ProjMap PM;
 595   for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
 596     const NodeSet &S = *I;
 597     GepNode *Min = *std::min_element(S.begin(), S.end(), NodeOrder);
 598     std::pair<ProjMap::iterator,bool> Ins = PM.insert(std::make_pair(&S, Min));
 599     (void)Ins;
 600     assert(Ins.second && "Cannot add minimal element");
 601
 602     // Update the min element's flags, and user list.
 603     uint32_t Flags = 0;
 604     UseSet &MinUs = Uses[Min];
 605     for (NodeSet::iterator J = S.begin(), F = S.end(); J != F; ++J) {
 606       GepNode *N = *J;
 607       uint32_t NF = N->Flags;
 608       // If N is used, append all original values of N to the list of
 609       // original values of Min.
 610       if (NF & GepNode::Used)
 611         MinUs.insert(Uses[N].begin(), Uses[N].end());
 612       Flags |= NF;
 613     }
 614     if (MinUs.empty())
 615       Uses.erase(Min);
 616
 617     // The collected flags should include all the flags from the min element.
 618     assert((Min->Flags & Flags) == Min->Flags);
 619     Min->Flags = Flags;
 620   }
 621
 622   // Commoning: for each non-root gep node, replace "Parent" with the
 623   // selected (minimum) node from the corresponding equivalence class.
 624   // If a given parent does not have an equivalence class, leave it
 625   // unchanged (it means that it's the only element in its class).
 626   for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
 627     GepNode *N = *I;
 628     if (N->Flags & GepNode::Root)
 629       continue;
 630     const NodeSet *PC = node_class(N->Parent, EqRel);
 631     if (!PC)
 632       continue;
 633     ProjMap::iterator F = PM.find(PC);
 634     if (F == PM.end())
 635       continue;
 636     // Found a replacement, use it.
 637     GepNode *Rep = F->second;
 638     N->Parent = Rep;
 639   }
 640
 641   DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes);
 642
 643   // Finally, erase the nodes that are no longer used.
 644   NodeSet Erase;
 645   for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
 646     GepNode *N = *I;
 647     const NodeSet *PC = node_class(N, EqRel);
 648     if (!PC)
 649       continue;
 650     ProjMap::iterator F = PM.find(PC);
 651     if (F == PM.end())
 652       continue;
 653     if (N == F->second)
 654       continue;
 655     // Node for removal.
 656     Erase.insert(*I);
 657   }
 658   NodeVect::iterator NewE = std::remove_if(Nodes.begin(), Nodes.end(),
 659                                            in_set(Erase));
 660   Nodes.resize(std::distance(Nodes.begin(), NewE));
 661
 662   DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes);
 663 }
 664
 665
 666 namespace {
 667   template <typename T>
 668   BasicBlock *nearest_common_dominator(DominatorTree *DT, T &Blocks) {
 669     DEBUG({
 670       dbgs() << "NCD of {";
 671       for (typename T::iterator I = Blocks.begin(), E = Blocks.end();
 672            I != E; ++I) {
 673         if (!*I)
 674           continue;
 675         BasicBlock *B = cast<BasicBlock>(*I);
 676         dbgs() << ' ' << B->getName();
 677       }
 678       dbgs() << " }\n";
 679     });
 680
 681     // Allow null basic blocks in Blocks.  In such cases, return 0.
 682     typename T::iterator I = Blocks.begin(), E = Blocks.end();
 683     if (I == E || !*I)
 684       return 0;
 685     BasicBlock *Dom = cast<BasicBlock>(*I);
 686     while (++I != E) {
 687       BasicBlock *B = cast_or_null<BasicBlock>(*I);
 688       Dom = B ? DT->findNearestCommonDominator(Dom, B) : 0;
 689       if (!Dom)
 690         return 0;
 691     }
 692     DEBUG(dbgs() << "computed:" << Dom->getName() << '\n');
 693     return Dom;
 694   }
 695
 696   template <typename T>
 697   BasicBlock *nearest_common_dominatee(DominatorTree *DT, T &Blocks) {
 698     // If two blocks, A and B, dominate a block C, then A dominates B,
 699     // or B dominates A.
 700     typename T::iterator I = Blocks.begin(), E = Blocks.end();
 701     // Find the first non-null block.
 702     while (I != E && !*I)
 703       ++I;
 704     if (I == E)
 705       return DT->getRoot();
 706     BasicBlock *DomB = cast<BasicBlock>(*I);
 707     while (++I != E) {
 708       if (!*I)
 709         continue;
 710       BasicBlock *B = cast<BasicBlock>(*I);
 711       if (DT->dominates(B, DomB))
 712         continue;
 713       if (!DT->dominates(DomB, B))
 714         return 0;
 715       DomB = B;
 716     }
 717     return DomB;
 718   }
 719
 720   // Find the first use in B of any value from Values. If no such use,
 721   // return B->end().
 722   template <typename T>
 723   BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B) {
 724     BasicBlock::iterator FirstUse = B->end(), BEnd = B->end();
 725     typedef typename T::iterator iterator;
 726     for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) {
 727       Value *V = *I;
 728       // If V is used in a PHI node, the use belongs to the incoming block,
 729       // not the block with the PHI node. In the incoming block, the use
 730       // would be considered as being at the end of it, so it cannot
 731       // influence the position of the first use (which is assumed to be
 732       // at the end to start with).
 733       if (isa<PHINode>(V))
 734         continue;
 735       if (!isa<Instruction>(V))
 736         continue;
 737       Instruction *In = cast<Instruction>(V);
 738       if (In->getParent() != B)
 739         continue;
 740       BasicBlock::iterator It = In;
 741       if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd))
 742         FirstUse = It;
 743     }
 744     return FirstUse;
 745   }
 746
 747   bool is_empty(const BasicBlock *B) {
 748     return B->empty() || (&*B->begin() == B->getTerminator());
 749   }
 750 }
 751
 752
 753 BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
 754       NodeChildrenMap &NCM, NodeToValueMap &Loc) {
 755   DEBUG(dbgs() << "Loc for node:" << Node << '\n');
 756   // Recalculate the placement for Node, assuming that the locations of
 757   // its children in Loc are valid.
 758   // Return 0 if there is no valid placement for Node (for example, it
 759   // uses an index value that is not available at the location required
 760   // to dominate all children, etc.).
 761
 762   // Find the nearest common dominator for:
 763   // - all users, if the node is used, and
 764   // - all children.
 765   ValueVect Bs;
 766   if (Node->Flags & GepNode::Used) {
 767     // Append all blocks with uses of the original values to the
 768     // block vector Bs.
 769     NodeToUsesMap::iterator UF = Uses.find(Node);
 770     assert(UF != Uses.end() && "Used node with no use information");
 771     UseSet &Us = UF->second;
 772     for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
 773       Use *U = *I;
 774       User *R = U->getUser();
 775       if (!isa<Instruction>(R))
 776         continue;
 777       BasicBlock *PB = isa<PHINode>(R)
 778           ? cast<PHINode>(R)->getIncomingBlock(*U)
 779           : cast<Instruction>(R)->getParent();
 780       Bs.push_back(PB);
 781     }
 782   }
 783   // Append the location of each child.
 784   NodeChildrenMap::iterator CF = NCM.find(Node);
 785   if (CF != NCM.end()) {
 786     NodeVect &Cs = CF->second;
 787     for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
 788       GepNode *CN = *I;
 789       NodeToValueMap::iterator LF = Loc.find(CN);
 790       // If the child is only used in GEP instructions (i.e. is not used in
 791       // non-GEP instructions), the nearest dominator computed for it may
 792       // have been null. In such case it won't have a location available.
 793       if (LF == Loc.end())
 794         continue;
 795       Bs.push_back(LF->second);
 796     }
 797   }
 798
 799   BasicBlock *DomB = nearest_common_dominator(DT, Bs);
 800   if (!DomB)
 801     return 0;
 802   // Check if the index used by Node dominates the computed dominator.
 803   Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
 804   if (IdxI && !DT->dominates(IdxI->getParent(), DomB))
 805     return 0;
 806
 807   // Avoid putting nodes into empty blocks.
 808   while (is_empty(DomB)) {
 809     DomTreeNode *N = (*DT)[DomB]->getIDom();
 810     if (!N)
 811       break;
 812     DomB = N->getBlock();
 813   }
 814
 815   // Otherwise, DomB is fine. Update the location map.
 816   Loc[Node] = DomB;
 817   return DomB;
 818 }
 819
 820
 821 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
 822       NodeChildrenMap &NCM, NodeToValueMap &Loc) {
 823   DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n');
 824   // Recalculate the placement of Node, after recursively recalculating the
 825   // placements of all its children.
 826   NodeChildrenMap::iterator CF = NCM.find(Node);
 827   if (CF != NCM.end()) {
 828     NodeVect &Cs = CF->second;
 829     for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I)
 830       recalculatePlacementRec(*I, NCM, Loc);
 831   }
 832   BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);
 833   DEBUG(dbgs() << "LocRec end for node:" << Node << '\n');
 834   return LB;
 835 }
 836
 837
 838 bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {
 839   if (isa<Constant>(Val) || isa<Argument>(Val))
 840     return true;
 841   Instruction *In = dyn_cast<Instruction>(Val);
 842   if (!In)
 843     return false;
 844   BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent();
 845   return DT->properlyDominates(DefB, HdrB);
 846 }
 847
 848
 849 bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {
 850   if (Node->Flags & GepNode::Root)
 851     if (!isInvariantIn(Node->BaseVal, L))
 852       return false;
 853   return isInvariantIn(Node->Idx, L);
 854 }
 855
 856
 857 bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {
 858   BasicBlock *HB = L->getHeader();
 859   BasicBlock *LB = L->getLoopLatch();
 860   // B must post-dominate the loop header or dominate the loop latch.
 861   if (PDT->dominates(B, HB))
 862     return true;
 863   if (LB && DT->dominates(B, LB))
 864     return true;
 865   return false;
 866 }
 867
 868
 869 namespace {
 870   BasicBlock *preheader(DominatorTree *DT, Loop *L) {
 871     if (BasicBlock *PH = L->getLoopPreheader())
 872       return PH;
 873     if (!OptSpeculate)
 874       return 0;
 875     DomTreeNode *DN = DT->getNode(L->getHeader());
 876     if (!DN)
 877       return 0;
 878     return DN->getIDom()->getBlock();
 879   }
 880 }
 881
 882
 883 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
 884       NodeChildrenMap &NCM, NodeToValueMap &Loc) {
 885   // Find the "topmost" location for Node: it must be dominated by both,
 886   // its parent (or the BaseVal, if it's a root node), and by the index
 887   // value.
 888   ValueVect Bs;
 889   if (Node->Flags & GepNode::Root) {
 890     if (Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal))
 891       Bs.push_back(PIn->getParent());
 892   } else {
 893     Bs.push_back(Loc[Node->Parent]);
 894   }
 895   if (Instruction *IIn = dyn_cast<Instruction>(Node->Idx))
 896     Bs.push_back(IIn->getParent());
 897   BasicBlock *TopB = nearest_common_dominatee(DT, Bs);
 898
 899   // Traverse the loop nest upwards until we find a loop in which Node
 900   // is no longer invariant, or until we get to the upper limit of Node's
 901   // placement. The traversal will also stop when a suitable "preheader"
 902   // cannot be found for a given loop. The "preheader" may actually be
 903   // a regular block outside of the loop (i.e. not guarded), in which case
 904   // the Node will be speculated.
 905   // For nodes that are not in the main path of the containing loop (i.e.
 906   // are not executed in each iteration), do not move them out of the loop.
 907   BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]);
 908   if (LocB) {
 909     Loop *Lp = LI->getLoopFor(LocB);
 910     while (Lp) {
 911       if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))
 912         break;
 913       BasicBlock *NewLoc = preheader(DT, Lp);
 914       if (!NewLoc || !DT->dominates(TopB, NewLoc))
 915         break;
 916       Lp = Lp->getParentLoop();
 917       LocB = NewLoc;
 918     }
 919   }
 920   Loc[Node] = LocB;
 921
 922   // Recursively compute the locations of all children nodes.
 923   NodeChildrenMap::iterator CF = NCM.find(Node);
 924   if (CF != NCM.end()) {
 925     NodeVect &Cs = CF->second;
 926     for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I)
 927       adjustForInvariance(*I, NCM, Loc);
 928   }
 929   return LocB;
 930 }
 931
 932
 933 namespace {
 934   struct LocationAsBlock {
 935     LocationAsBlock(const NodeToValueMap &L) : Map(L) {}
 936     const NodeToValueMap &Map;
 937   };
 938
 939   raw_ostream &operator<< (raw_ostream &OS,
 940                            const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ;
 941   raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) {
 942     for (NodeToValueMap::const_iterator I = Loc.Map.begin(), E = Loc.Map.end();
 943          I != E; ++I) {
 944       OS << I->first << " -> ";
 945       BasicBlock *B = cast<BasicBlock>(I->second);
 946       OS << B->getName() << '(' << B << ')';
 947       OS << '\n';
 948     }
 949     return OS;
 950   }
 951
 952   inline bool is_constant(GepNode *N) {
 953     return isa<ConstantInt>(N->Idx);
 954   }
 955 }
 956
 957
 958 void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
 959       NodeToValueMap &Loc) {
 960   User *R = U->getUser();
 961   DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: "
 962                << *R << '\n');
 963   BasicBlock *PB = cast<Instruction>(R)->getParent();
 964
 965   GepNode *N = Node;
 966   GepNode *C = 0, *NewNode = 0;
 967   while (is_constant(N) && !(N->Flags & GepNode::Root)) {
 968     // XXX if (single-use) dont-replicate;
 969     GepNode *NewN = new (*Mem) GepNode(N);
 970     Nodes.push_back(NewN);
 971     Loc[NewN] = PB;
 972
 973     if (N == Node)
 974       NewNode = NewN;
 975     NewN->Flags &= ~GepNode::Used;
 976     if (C)
 977       C->Parent = NewN;
 978     C = NewN;
 979     N = N->Parent;
 980   }
 981   if (!NewNode)
 982     return;
 983
 984   // Move over all uses that share the same user as U from Node to NewNode.
 985   NodeToUsesMap::iterator UF = Uses.find(Node);
 986   assert(UF != Uses.end());
 987   UseSet &Us = UF->second;
 988   UseSet NewUs;
 989   for (UseSet::iterator I = Us.begin(); I != Us.end(); ) {
 990     User *S = (*I)->getUser();
 991     UseSet::iterator Nx = std::next(I);
 992     if (S == R) {
 993       NewUs.insert(*I);
 994       Us.erase(I);
 995     }
 996     I = Nx;
 997   }
 998   if (Us.empty()) {
 999     Node->Flags &= ~GepNode::Used;
1000     Uses.erase(UF);
1001   }
1002
1003   // Should at least have U in NewUs.
1004   NewNode->Flags |= GepNode::Used;
1005   DEBUG(dbgs() << "new node: " << NewNode << "  " << *NewNode << '\n');
1006   assert(!NewUs.empty());
1007   Uses[NewNode] = NewUs;
1008 }
1009
1010
1011 void HexagonCommonGEP::separateConstantChains(GepNode *Node,
1012       NodeChildrenMap &NCM, NodeToValueMap &Loc) {
1013   // First approximation: extract all chains.
1014   NodeSet Ns;
1015   nodes_for_root(Node, NCM, Ns);
1016
1017   DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n');
1018   // Collect all used nodes together with the uses from loads and stores,
1019   // where the GEP node could be folded into the load/store instruction.
1020   NodeToUsesMap FNs; // Foldable nodes.
1021   for (NodeSet::iterator I = Ns.begin(), E = Ns.end(); I != E; ++I) {
1022     GepNode *N = *I;
1023     if (!(N->Flags & GepNode::Used))
1024       continue;
1025     NodeToUsesMap::iterator UF = Uses.find(N);
1026     assert(UF != Uses.end());
1027     UseSet &Us = UF->second;
1028     // Loads/stores that use the node N.
1029     UseSet LSs;
1030     for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
1031       Use *U = *J;
1032       User *R = U->getUser();
1033       // We're interested in uses that provide the address. It can happen
1034       // that the value may also be provided via GEP, but we won't handle
1035       // those cases here for now.
1036       if (LoadInst *Ld = dyn_cast<LoadInst>(R)) {
1037         unsigned PtrX = LoadInst::getPointerOperandIndex();
1038         if (&Ld->getOperandUse(PtrX) == U)
1039           LSs.insert(U);
1040       } else if (StoreInst *St = dyn_cast<StoreInst>(R)) {
1041         unsigned PtrX = StoreInst::getPointerOperandIndex();
1042         if (&St->getOperandUse(PtrX) == U)
1043           LSs.insert(U);
1044       }
1045     }
1046     // Even if the total use count is 1, separating the chain may still be
1047     // beneficial, since the constant chain may be longer than the GEP alone
1048     // would be (e.g. if the parent node has a constant index and also has
1049     // other children).
1050     if (!LSs.empty())
1051       FNs.insert(std::make_pair(N, LSs));
1052   }
1053
1054   DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs);
1055
1056   for (NodeToUsesMap::iterator I = FNs.begin(), E = FNs.end(); I != E; ++I) {
1057     GepNode *N = I->first;
1058     UseSet &Us = I->second;
1059     for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J)
1060       separateChainForNode(N, *J, Loc);
1061   }
1062 }
1063
1064
1065 void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1066   // Compute the inverse of the Node.Parent links. Also, collect the set
1067   // of root nodes.
1068   NodeChildrenMap NCM;
1069   NodeVect Roots;
1070   invert_find_roots(Nodes, NCM, Roots);
1071
1072   // Compute the initial placement determined by the users' locations, and
1073   // the locations of the child nodes.
1074   for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1075     recalculatePlacementRec(*I, NCM, Loc);
1076
1077   DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc));
1078
1079   if (OptEnableInv) {
1080     for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1081       adjustForInvariance(*I, NCM, Loc);
1082
1083     DEBUG(dbgs() << "Node placement after adjustment for invariance:\n"
1084                  << LocationAsBlock(Loc));
1085   }
1086   if (OptEnableConst) {
1087     for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1088       separateConstantChains(*I, NCM, Loc);
1089   }
1090   DEBUG(dbgs() << "Node use information:\n" << Uses);
1091
1092   // At the moment, there is no further refinement of the initial placement.
1093   // Such a refinement could include splitting the nodes if they are placed
1094   // too far from some of its users.
1095
1096   DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc));
1097 }
1098
1099
1100 Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
1101       BasicBlock *LocB) {
1102   DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName()
1103                << " for nodes:\n" << NA);
1104   unsigned Num = NA.size();
1105   GepNode *RN = NA[0];
1106   assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root");
1107
1108   Value *NewInst = 0;
1109   Value *Input = RN->BaseVal;
1110   Value **IdxList = new Value*[Num+1];
1111   unsigned nax = 0;
1112   do {
1113     unsigned IdxC = 0;
1114     // If the type of the input of the first node is not a pointer,
1115     // we need to add an artificial i32 0 to the indices (because the
1116     // actual input in the IR will be a pointer).
1117     if (!NA[nax]->PTy->isPointerTy()) {
1118       Type *Int32Ty = Type::getInt32Ty(*Ctx);
1119       IdxList[IdxC++] = ConstantInt::get(Int32Ty, 0);
1120     }
1121
1122     // Keep adding indices from NA until we have to stop and generate
1123     // an "intermediate" GEP.
1124     while (++nax <= Num) {
1125       GepNode *N = NA[nax-1];
1126       IdxList[IdxC++] = N->Idx;
1127       if (nax < Num) {
1128         // We have to stop, if the expected type of the output of this node
1129         // is not the same as the input type of the next node.
1130         Type *NextTy = next_type(N->PTy, N->Idx);
1131         if (NextTy != NA[nax]->PTy)
1132           break;
1133       }
1134     }
1135     ArrayRef<Value*> A(IdxList, IdxC);
1136     Type *InpTy = Input->getType();
1137     Type *ElTy = cast<PointerType>(InpTy->getScalarType())->getElementType();
1138     NewInst = GetElementPtrInst::Create(ElTy, Input, A, "cgep", At);
1139     DEBUG(dbgs() << "new GEP: " << *NewInst << '\n');
1140     Input = NewInst;
1141   } while (nax <= Num);
1142
1143   delete[] IdxList;
1144   return NewInst;
1145 }
1146
1147
1148 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1149       NodeChildrenMap &NCM) {
1150   NodeVect Work;
1151   Work.push_back(Node);
1152
1153   while (!Work.empty()) {
1154     NodeVect::iterator First = Work.begin();
1155     GepNode *N = *First;
1156     Work.erase(First);
1157     if (N->Flags & GepNode::Used) {
1158       NodeToUsesMap::iterator UF = Uses.find(N);
1159       assert(UF != Uses.end() && "No use information for used node");
1160       UseSet &Us = UF->second;
1161       for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I)
1162         Values.push_back((*I)->getUser());
1163     }
1164     NodeChildrenMap::iterator CF = NCM.find(N);
1165     if (CF != NCM.end()) {
1166       NodeVect &Cs = CF->second;
1167       Work.insert(Work.end(), Cs.begin(), Cs.end());
1168     }
1169   }
1170 }
1171
1172
1173 void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1174   DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n');
1175   NodeChildrenMap NCM;
1176   NodeVect Roots;
1177   // Compute the inversion again, since computing placement could alter
1178   // "parent" relation between nodes.
1179   invert_find_roots(Nodes, NCM, Roots);
1180
1181   while (!Roots.empty()) {
1182     NodeVect::iterator First = Roots.begin();
1183     GepNode *Root = *First, *Last = *First;
1184     Roots.erase(First);
1185
1186     NodeVect NA;  // Nodes to assemble.
1187     // Append to NA all child nodes up to (and including) the first child
1188     // that:
1189     // (1) has more than 1 child, or
1190     // (2) is used, or
1191     // (3) has a child located in a different block.
1192     bool LastUsed = false;
1193     unsigned LastCN = 0;
1194     // The location may be null if the computation failed (it can legitimately
1195     // happen for nodes created from dead GEPs).
1196     Value *LocV = Loc[Last];
1197     if (!LocV)
1198       continue;
1199     BasicBlock *LastB = cast<BasicBlock>(LocV);
1200     do {
1201       NA.push_back(Last);
1202       LastUsed = (Last->Flags & GepNode::Used);
1203       if (LastUsed)
1204         break;
1205       NodeChildrenMap::iterator CF = NCM.find(Last);
1206       LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1207       if (LastCN != 1)
1208         break;
1209       GepNode *Child = CF->second.front();
1210       BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
1211       if (ChildB != 0 && LastB != ChildB)
1212         break;
1213       Last = Child;
1214     } while (true);
1215
1216     BasicBlock::iterator InsertAt = LastB->getTerminator();
1217     if (LastUsed || LastCN > 0) {
1218       ValueVect Urs;
1219       getAllUsersForNode(Root, Urs, NCM);
1220       BasicBlock::iterator FirstUse = first_use_of_in_block(Urs, LastB);
1221       if (FirstUse != LastB->end())
1222         InsertAt = FirstUse;
1223     }
1224
1225     // Generate a new instruction for NA.
1226     Value *NewInst = fabricateGEP(NA, InsertAt, LastB);
1227
1228     // Convert all the children of Last node into roots, and append them
1229     // to the Roots list.
1230     if (LastCN > 0) {
1231       NodeVect &Cs = NCM[Last];
1232       for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
1233         GepNode *CN = *I;
1234         CN->Flags &= ~GepNode::Internal;
1235         CN->Flags |= GepNode::Root;
1236         CN->BaseVal = NewInst;
1237         Roots.push_back(CN);
1238       }
1239     }
1240
1241     // Lastly, if the Last node was used, replace all uses with the new GEP.
1242     // The uses reference the original GEP values.
1243     if (LastUsed) {
1244       NodeToUsesMap::iterator UF = Uses.find(Last);
1245       assert(UF != Uses.end() && "No use information found");
1246       UseSet &Us = UF->second;
1247       for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
1248         Use *U = *I;
1249         U->set(NewInst);
1250       }
1251     }
1252   }
1253 }
1254
1255
1256 void HexagonCommonGEP::removeDeadCode() {
1257   ValueVect BO;
1258   BO.push_back(&Fn->front());
1259
1260   for (unsigned i = 0; i < BO.size(); ++i) {
1261     BasicBlock *B = cast<BasicBlock>(BO[i]);
1262     DomTreeNode *N = DT->getNode(B);
1263     typedef GraphTraits<DomTreeNode*> GTN;
1264     typedef GTN::ChildIteratorType Iter;
1265     for (Iter I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I)
1266       BO.push_back((*I)->getBlock());
1267   }
1268
1269   for (unsigned i = BO.size(); i > 0; --i) {
1270     BasicBlock *B = cast<BasicBlock>(BO[i-1]);
1271     BasicBlock::InstListType &IL = B->getInstList();
1272     typedef BasicBlock::InstListType::reverse_iterator reverse_iterator;
1273     ValueVect Ins;
1274     for (reverse_iterator I = IL.rbegin(), E = IL.rend(); I != E; ++I)
1275       Ins.push_back(&*I);
1276     for (ValueVect::iterator I = Ins.begin(), E = Ins.end(); I != E; ++I) {
1277       Instruction *In = cast<Instruction>(*I);
1278       if (isInstructionTriviallyDead(In))
1279         In->eraseFromParent();
1280     }
1281   }
1282 }
1283
1284
1285 bool HexagonCommonGEP::runOnFunction(Function &F) {
1286   // For now bail out on C++ exception handling.
1287   for (Function::iterator A = F.begin(), Z = F.end(); A != Z; ++A)
1288     for (BasicBlock::iterator I = A->begin(), E = A->end(); I != E; ++I)
1289       if (isa<InvokeInst>(I) || isa<LandingPadInst>(I))
1290         return false;
1291
1292   Fn = &F;
1293   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1294   PDT = &getAnalysis<PostDominatorTree>();
1295   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1296   Ctx = &F.getContext();
1297
1298   Nodes.clear();
1299   Uses.clear();
1300   NodeOrder.clear();
1301
1302   SpecificBumpPtrAllocator<GepNode> Allocator;
1303   Mem = &Allocator;
1304
1305   collect();
1306   common();
1307
1308   NodeToValueMap Loc;
1309   computeNodePlacement(Loc);
1310   materialize(Loc);
1311   removeDeadCode();
1312
1313 #ifdef XDEBUG
1314   // Run this only when expensive checks are enabled.
1315   verifyFunction(F);
1316 #endif
1317   return true;
1318 }
1319
1320
1321 namespace llvm {
1322   FunctionPass *createHexagonCommonGEP() {
1323     return new HexagonCommonGEP();
1324   }
1325 }