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