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