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