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