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