lib/Target/Hexagon/HexagonCommonGEP.cpp

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