lib/Target/Hexagon/HexagonCommonGEP.cpp

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