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