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