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