LLVM  14.0.0git
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 #include "llvm/ADT/ArrayRef.h"
10 #include "llvm/ADT/FoldingSet.h"
11 #include "llvm/ADT/GraphTraits.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/SetVector.h"
14 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/ADT/StringRef.h"
16 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/IR/BasicBlock.h"
19 #include "llvm/IR/Constant.h"
20 #include "llvm/IR/Constants.h"
21 #include "llvm/IR/DerivedTypes.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/Instruction.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/Type.h"
27 #include "llvm/IR/Use.h"
28 #include "llvm/IR/User.h"
29 #include "llvm/IR/Value.h"
30 #include "llvm/IR/Verifier.h"
31 #include "llvm/InitializePasses.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 #define DEBUG_TYPE "commgep"
51 
52 using namespace llvm;
53 
54 static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true),
56 
57 static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden,
59 
60 static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true),
62 
63 namespace llvm {
64 
66 
67 } // end namespace llvm
68 
69 namespace {
70 
71  struct GepNode;
72  using NodeSet = std::set<GepNode *>;
73  using NodeToValueMap = std::map<GepNode *, Value *>;
74  using NodeVect = std::vector<GepNode *>;
75  using NodeChildrenMap = std::map<GepNode *, NodeVect>;
76  using UseSet = SetVector<Use *>;
77  using NodeToUsesMap = std::map<GepNode *, UseSet>;
78 
79  // Numbering map for gep nodes. Used to keep track of ordering for
80  // gep nodes.
81  struct NodeOrdering {
82  NodeOrdering() = default;
83 
84  void insert(const GepNode *N) { Map.insert(std::make_pair(N, ++LastNum)); }
85  void clear() { Map.clear(); }
86 
87  bool operator()(const GepNode *N1, const GepNode *N2) const {
88  auto F1 = Map.find(N1), F2 = Map.find(N2);
89  assert(F1 != Map.end() && F2 != Map.end());
90  return F1->second < F2->second;
91  }
92 
93  private:
94  std::map<const GepNode *, unsigned> Map;
95  unsigned LastNum = 0;
96  };
97 
98  class HexagonCommonGEP : public FunctionPass {
99  public:
100  static char ID;
101 
102  HexagonCommonGEP() : FunctionPass(ID) {
104  }
105 
106  bool runOnFunction(Function &F) override;
107  StringRef getPassName() const override { return "Hexagon Common GEP"; }
108 
109  void getAnalysisUsage(AnalysisUsage &AU) const override {
117  }
118 
119  private:
120  using ValueToNodeMap = std::map<Value *, GepNode *>;
121  using ValueVect = std::vector<Value *>;
122  using NodeToValuesMap = std::map<GepNode *, ValueVect>;
123 
124  void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order);
125  bool isHandledGepForm(GetElementPtrInst *GepI);
126  void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM);
127  void collect();
128  void common();
129 
130  BasicBlock *recalculatePlacement(GepNode *Node, NodeChildrenMap &NCM,
131  NodeToValueMap &Loc);
132  BasicBlock *recalculatePlacementRec(GepNode *Node, NodeChildrenMap &NCM,
133  NodeToValueMap &Loc);
134  bool isInvariantIn(Value *Val, Loop *L);
135  bool isInvariantIn(GepNode *Node, Loop *L);
136  bool isInMainPath(BasicBlock *B, Loop *L);
137  BasicBlock *adjustForInvariance(GepNode *Node, NodeChildrenMap &NCM,
138  NodeToValueMap &Loc);
139  void separateChainForNode(GepNode *Node, Use *U, NodeToValueMap &Loc);
140  void separateConstantChains(GepNode *Node, NodeChildrenMap &NCM,
141  NodeToValueMap &Loc);
142  void computeNodePlacement(NodeToValueMap &Loc);
143 
144  Value *fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
145  BasicBlock *LocB);
146  void getAllUsersForNode(GepNode *Node, ValueVect &Values,
147  NodeChildrenMap &NCM);
148  void materialize(NodeToValueMap &Loc);
149 
150  void removeDeadCode();
151 
152  NodeVect Nodes;
153  NodeToUsesMap Uses;
154  NodeOrdering NodeOrder; // Node ordering, for deterministic behavior.
156  LLVMContext *Ctx;
157  LoopInfo *LI;
158  DominatorTree *DT;
159  PostDominatorTree *PDT;
160  Function *Fn;
161  };
162 
163 } // end anonymous namespace
164 
165 char HexagonCommonGEP::ID = 0;
166 
167 INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
168  false, false)
172 INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
174 
175 namespace {
176 
177  struct GepNode {
178  enum {
179  None = 0,
180  Root = 0x01,
181  Internal = 0x02,
182  Used = 0x04,
183  InBounds = 0x08,
184  Pointer = 0x10, // See note below.
185  };
186  // Note: GEP indices generally traverse nested types, and so a GepNode
187  // (representing a single index) can be associated with some composite
188  // type. The exception is the GEP input, which is a pointer, and not
189  // a composite type (at least not in the sense of having sub-types).
190  // Also, the corresponding index plays a different role as well: it is
191  // simply added to the input pointer. Since pointer types are becoming
192  // opaque (i.e. are no longer going to include the pointee type), the
193  // two pieces of information (1) the fact that it's a pointer, and
194  // (2) the pointee type, need to be stored separately. The pointee type
195  // will be stored in the PTy member, while the fact that the node
196  // operates on a pointer will be reflected by the flag "Pointer".
197 
198  uint32_t Flags = 0;
199  union {
202  };
203  Value *Idx = nullptr;
204  Type *PTy = nullptr; // Type indexed by this node. For pointer nodes
205  // this is the "pointee" type, and indexing a
206  // pointer does not change the type.
207 
208  GepNode() : Parent(nullptr) {}
209  GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) {
210  if (Flags & Root)
211  BaseVal = N->BaseVal;
212  else
213  Parent = N->Parent;
214  }
215 
216  friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN);
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  if (GN.Flags & GepNode::Pointer) {
243  if (Comma)
244  OS << ',';
245  OS << "pointer";
246  }
247  OS << "} ";
248  if (GN.Flags & GepNode::Root)
249  OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')';
250  else
251  OS << "Parent:" << GN.Parent;
252 
253  OS << " Idx:";
254  if (ConstantInt *CI = dyn_cast<ConstantInt>(GN.Idx))
255  OS << CI->getValue().getSExtValue();
256  else if (GN.Idx->hasName())
257  OS << GN.Idx->getName();
258  else
259  OS << "<anon> =" << *GN.Idx;
260 
261  OS << " PTy:";
262  if (GN.PTy->isStructTy()) {
263  StructType *STy = cast<StructType>(GN.PTy);
264  if (!STy->isLiteral())
265  OS << GN.PTy->getStructName();
266  else
267  OS << "<anon-struct>:" << *STy;
268  }
269  else
270  OS << *GN.PTy;
271  OS << " }";
272  return OS;
273  }
274 
275  template <typename NodeContainer>
276  void dump_node_container(raw_ostream &OS, const NodeContainer &S) {
277  using const_iterator = typename NodeContainer::const_iterator;
278 
279  for (const_iterator I = S.begin(), E = S.end(); I != E; ++I)
280  OS << *I << ' ' << **I << '\n';
281  }
282 
284  const NodeVect &S) LLVM_ATTRIBUTE_UNUSED;
285  raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) {
286  dump_node_container(OS, S);
287  return OS;
288  }
289 
291  const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED;
292  raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){
293  for (const auto &I : M) {
294  const UseSet &Us = I.second;
295  OS << I.first << " -> #" << Us.size() << '{';
296  for (const Use *U : Us) {
297  User *R = U->getUser();
298  if (R->hasName())
299  OS << ' ' << R->getName();
300  else
301  OS << " <?>(" << *R << ')';
302  }
303  OS << " }\n";
304  }
305  return OS;
306  }
307 
308  struct in_set {
309  in_set(const NodeSet &S) : NS(S) {}
310 
311  bool operator() (GepNode *N) const {
312  return NS.find(N) != NS.end();
313  }
314 
315  private:
316  const NodeSet &NS;
317  };
318 
319 } // end anonymous namespace
320 
321 inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) {
322  return A.Allocate();
323 }
324 
325 void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
326  ValueVect &Order) {
327  // Compute block ordering for a typical DT-based traversal of the flow
328  // graph: "before visiting a block, all of its dominators must have been
329  // visited".
330 
331  Order.push_back(Root);
332  for (auto *DTN : children<DomTreeNode*>(DT->getNode(Root)))
333  getBlockTraversalOrder(DTN->getBlock(), Order);
334 }
335 
336 bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
337  // No vector GEPs.
338  if (!GepI->getType()->isPointerTy())
339  return false;
340  // No GEPs without any indices. (Is this possible?)
341  if (GepI->idx_begin() == GepI->idx_end())
342  return false;
343  return true;
344 }
345 
346 void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
347  ValueToNodeMap &NM) {
348  LLVM_DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n');
349  GepNode *N = new (*Mem) GepNode;
350  Value *PtrOp = GepI->getPointerOperand();
351  uint32_t InBounds = GepI->isInBounds() ? GepNode::InBounds : 0;
352  ValueToNodeMap::iterator F = NM.find(PtrOp);
353  if (F == NM.end()) {
354  N->BaseVal = PtrOp;
355  N->Flags |= GepNode::Root | InBounds;
356  } else {
357  // If PtrOp was a GEP instruction, it must have already been processed.
358  // The ValueToNodeMap entry for it is the last gep node in the generated
359  // chain. Link to it here.
360  N->Parent = F->second;
361  }
362  N->PTy = GepI->getSourceElementType();
363  N->Flags |= GepNode::Pointer;
364  N->Idx = *GepI->idx_begin();
365 
366  // Collect the list of users of this GEP instruction. Will add it to the
367  // last node created for it.
368  UseSet Us;
369  for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end();
370  UI != UE; ++UI) {
371  // Check if this gep is used by anything other than other geps that
372  // we will process.
373  if (isa<GetElementPtrInst>(*UI)) {
374  GetElementPtrInst *UserG = cast<GetElementPtrInst>(*UI);
375  if (isHandledGepForm(UserG))
376  continue;
377  }
378  Us.insert(&UI.getUse());
379  }
380  Nodes.push_back(N);
381  NodeOrder.insert(N);
382 
383  // Skip the first index operand, since it was already handled above. This
384  // dereferences the pointer operand.
385  GepNode *PN = N;
386  Type *PtrTy = GepI->getSourceElementType();
387  for (Use &U : llvm::drop_begin(GepI->indices())) {
388  Value *Op = U;
389  GepNode *Nx = new (*Mem) GepNode;
390  Nx->Parent = PN; // Link Nx to the previous node.
391  Nx->Flags |= GepNode::Internal | InBounds;
392  Nx->PTy = PtrTy;
393  Nx->Idx = Op;
394  Nodes.push_back(Nx);
395  NodeOrder.insert(Nx);
396  PN = Nx;
397 
398  PtrTy = GetElementPtrInst::getTypeAtIndex(PtrTy, Op);
399  }
400 
401  // After last node has been created, update the use information.
402  if (!Us.empty()) {
403  PN->Flags |= GepNode::Used;
404  Uses[PN].insert(Us.begin(), Us.end());
405  }
406 
407  // Link the last node with the originating GEP instruction. This is to
408  // help with linking chained GEP instructions.
409  NM.insert(std::make_pair(GepI, PN));
410 }
411 
412 void HexagonCommonGEP::collect() {
413  // Establish depth-first traversal order of the dominator tree.
414  ValueVect BO;
415  getBlockTraversalOrder(&Fn->front(), BO);
416 
417  // The creation of gep nodes requires DT-traversal. When processing a GEP
418  // instruction that uses another GEP instruction as the base pointer, the
419  // gep node for the base pointer should already exist.
420  ValueToNodeMap NM;
421  for (Value *I : BO) {
422  BasicBlock *B = cast<BasicBlock>(I);
423  for (Instruction &J : *B)
424  if (auto *GepI = dyn_cast<GetElementPtrInst>(&J))
425  if (isHandledGepForm(GepI))
426  processGepInst(GepI, NM);
427  }
428 
429  LLVM_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  for (GepNode *N : Nodes) {
435  if (N->Flags & GepNode::Root) {
436  Roots.push_back(N);
437  continue;
438  }
439  GepNode *PN = N->Parent;
440  NCM[PN].push_back(N);
441  }
442 }
443 
444 static void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM,
445  NodeSet &Nodes) {
446  NodeVect Work;
447  Work.push_back(Root);
448  Nodes.insert(Root);
449 
450  while (!Work.empty()) {
451  NodeVect::iterator First = Work.begin();
452  GepNode *N = *First;
453  Work.erase(First);
454  NodeChildrenMap::iterator CF = NCM.find(N);
455  if (CF != NCM.end()) {
456  llvm::append_range(Work, CF->second);
457  Nodes.insert(CF->second.begin(), CF->second.end());
458  }
459  }
460 }
461 
462 namespace {
463 
464  using NodeSymRel = std::set<NodeSet>;
465  using NodePair = std::pair<GepNode *, GepNode *>;
466  using NodePairSet = std::set<NodePair>;
467 
468 } // end anonymous namespace
469 
470 static const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) {
471  for (const NodeSet &S : Rel)
472  if (S.count(N))
473  return &S;
474  return nullptr;
475 }
476 
477  // Create an ordered pair of GepNode pointers. The pair will be used in
478  // determining equality. The only purpose of the ordering is to eliminate
479  // duplication due to the commutativity of equality/non-equality.
480 static NodePair node_pair(GepNode *N1, GepNode *N2) {
481  uintptr_t P1 = reinterpret_cast<uintptr_t>(N1);
482  uintptr_t P2 = reinterpret_cast<uintptr_t>(N2);
483  if (P1 <= P2)
484  return std::make_pair(N1, N2);
485  return std::make_pair(N2, N1);
486 }
487 
488 static unsigned node_hash(GepNode *N) {
489  // Include everything except flags and parent.
491  ID.AddPointer(N->Idx);
492  ID.AddPointer(N->PTy);
493  return ID.ComputeHash();
494 }
495 
496 static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,
497  NodePairSet &Ne) {
498  // Don't cache the result for nodes with different hashes. The hash
499  // comparison is fast enough.
500  if (node_hash(N1) != node_hash(N2))
501  return false;
502 
503  NodePair NP = node_pair(N1, N2);
504  NodePairSet::iterator FEq = Eq.find(NP);
505  if (FEq != Eq.end())
506  return true;
507  NodePairSet::iterator FNe = Ne.find(NP);
508  if (FNe != Ne.end())
509  return false;
510  // Not previously compared.
511  bool Root1 = N1->Flags & GepNode::Root;
512  uint32_t CmpFlags = GepNode::Root | GepNode::Pointer;
513  bool Different = (N1->Flags & CmpFlags) != (N2->Flags & CmpFlags);
514  NodePair P = node_pair(N1, N2);
515  // If the root/pointer flags have different values, the nodes are
516  // different.
517  // If both nodes are root nodes, but their base pointers differ,
518  // they are different.
519  if (Different || (Root1 && N1->BaseVal != N2->BaseVal)) {
520  Ne.insert(P);
521  return false;
522  }
523  // Here the root/pointer 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 (GepNode *N : Nodes) {
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 (auto &I : MaybeEq) {
551  NodeSet &S = I.second;
552  for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) {
553  GepNode *N = *NI;
554  // If node already has a class, then the class must have been created
555  // in a prior iteration of this loop. Since equality is transitive,
556  // nothing more will be added to that class, so skip it.
557  if (node_class(N, EqRel))
558  continue;
559 
560  // Create a new class candidate now.
561  NodeSet C;
562  for (NodeSet::iterator NJ = std::next(NI); NJ != NE; ++NJ)
563  if (node_eq(N, *NJ, Eq, Ne))
564  C.insert(*NJ);
565  // If Tmp is empty, N would be the only element in it. Don't bother
566  // creating a class for it then.
567  if (!C.empty()) {
568  C.insert(N); // Finalize the set before adding it to the relation.
569  std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(C);
570  (void)Ins;
571  assert(Ins.second && "Cannot add a class");
572  }
573  }
574  }
575 
576  LLVM_DEBUG({
577  dbgs() << "Gep node equality:\n";
578  for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I)
579  dbgs() << "{ " << I->first << ", " << I->second << " }\n";
580 
581  dbgs() << "Gep equivalence classes:\n";
582  for (const NodeSet &S : EqRel) {
583  dbgs() << '{';
584  for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) {
585  if (J != S.begin())
586  dbgs() << ',';
587  dbgs() << ' ' << *J;
588  }
589  dbgs() << " }\n";
590  }
591  });
592 
593  // Create a projection from a NodeSet to the minimal element in it.
594  using ProjMap = std::map<const NodeSet *, GepNode *>;
595  ProjMap PM;
596  for (const NodeSet &S : EqRel) {
597  GepNode *Min = *std::min_element(S.begin(), S.end(), NodeOrder);
598  std::pair<ProjMap::iterator,bool> Ins = PM.insert(std::make_pair(&S, Min));
599  (void)Ins;
600  assert(Ins.second && "Cannot add minimal element");
601 
602  // Update the min element's flags, and user list.
603  uint32_t Flags = 0;
604  UseSet &MinUs = Uses[Min];
605  for (GepNode *N : S) {
606  uint32_t NF = N->Flags;
607  // If N is used, append all original values of N to the list of
608  // original values of Min.
609  if (NF & GepNode::Used)
610  MinUs.insert(Uses[N].begin(), Uses[N].end());
611  Flags |= NF;
612  }
613  if (MinUs.empty())
614  Uses.erase(Min);
615 
616  // The collected flags should include all the flags from the min element.
617  assert((Min->Flags & Flags) == Min->Flags);
618  Min->Flags = Flags;
619  }
620 
621  // Commoning: for each non-root gep node, replace "Parent" with the
622  // selected (minimum) node from the corresponding equivalence class.
623  // If a given parent does not have an equivalence class, leave it
624  // unchanged (it means that it's the only element in its class).
625  for (GepNode *N : Nodes) {
626  if (N->Flags & GepNode::Root)
627  continue;
628  const NodeSet *PC = node_class(N->Parent, EqRel);
629  if (!PC)
630  continue;
631  ProjMap::iterator F = PM.find(PC);
632  if (F == PM.end())
633  continue;
634  // Found a replacement, use it.
635  GepNode *Rep = F->second;
636  N->Parent = Rep;
637  }
638 
639  LLVM_DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes);
640 
641  // Finally, erase the nodes that are no longer used.
642  NodeSet Erase;
643  for (GepNode *N : Nodes) {
644  const NodeSet *PC = node_class(N, EqRel);
645  if (!PC)
646  continue;
647  ProjMap::iterator F = PM.find(PC);
648  if (F == PM.end())
649  continue;
650  if (N == F->second)
651  continue;
652  // Node for removal.
653  Erase.insert(N);
654  }
655  erase_if(Nodes, in_set(Erase));
656 
657  LLVM_DEBUG(dbgs() << "Gep nodes after post-commoning cleanup:\n" << Nodes);
658 }
659 
660 template <typename T>
662  LLVM_DEBUG({
663  dbgs() << "NCD of {";
664  for (typename T::iterator I = Blocks.begin(), E = Blocks.end(); I != E;
665  ++I) {
666  if (!*I)
667  continue;
668  BasicBlock *B = cast<BasicBlock>(*I);
669  dbgs() << ' ' << B->getName();
670  }
671  dbgs() << " }\n";
672  });
673 
674  // Allow null basic blocks in Blocks. In such cases, return nullptr.
675  typename T::iterator I = Blocks.begin(), E = Blocks.end();
676  if (I == E || !*I)
677  return nullptr;
678  BasicBlock *Dom = cast<BasicBlock>(*I);
679  while (++I != E) {
680  BasicBlock *B = cast_or_null<BasicBlock>(*I);
681  Dom = B ? DT->findNearestCommonDominator(Dom, B) : nullptr;
682  if (!Dom)
683  return nullptr;
684  }
685  LLVM_DEBUG(dbgs() << "computed:" << Dom->getName() << '\n');
686  return Dom;
687 }
688 
689 template <typename T>
691  // If two blocks, A and B, dominate a block C, then A dominates B,
692  // or B dominates A.
693  typename T::iterator I = Blocks.begin(), E = Blocks.end();
694  // Find the first non-null block.
695  while (I != E && !*I)
696  ++I;
697  if (I == E)
698  return DT->getRoot();
699  BasicBlock *DomB = cast<BasicBlock>(*I);
700  while (++I != E) {
701  if (!*I)
702  continue;
703  BasicBlock *B = cast<BasicBlock>(*I);
704  if (DT->dominates(B, DomB))
705  continue;
706  if (!DT->dominates(DomB, B))
707  return nullptr;
708  DomB = B;
709  }
710  return DomB;
711 }
712 
713 // Find the first use in B of any value from Values. If no such use,
714 // return B->end().
715 template <typename T>
717  BasicBlock::iterator FirstUse = B->end(), BEnd = B->end();
718 
719  using iterator = typename T::iterator;
720 
721  for (iterator I = Values.begin(), E = Values.end(); I != E; ++I) {
722  Value *V = *I;
723  // If V is used in a PHI node, the use belongs to the incoming block,
724  // not the block with the PHI node. In the incoming block, the use
725  // would be considered as being at the end of it, so it cannot
726  // influence the position of the first use (which is assumed to be
727  // at the end to start with).
728  if (isa<PHINode>(V))
729  continue;
730  if (!isa<Instruction>(V))
731  continue;
732  Instruction *In = cast<Instruction>(V);
733  if (In->getParent() != B)
734  continue;
735  BasicBlock::iterator It = In->getIterator();
736  if (std::distance(FirstUse, BEnd) < std::distance(It, BEnd))
737  FirstUse = It;
738  }
739  return FirstUse;
740 }
741 
742 static bool is_empty(const BasicBlock *B) {
743  return B->empty() || (&*B->begin() == B->getTerminator());
744 }
745 
746 BasicBlock *HexagonCommonGEP::recalculatePlacement(GepNode *Node,
747  NodeChildrenMap &NCM, NodeToValueMap &Loc) {
748  LLVM_DEBUG(dbgs() << "Loc for node:" << Node << '\n');
749  // Recalculate the placement for Node, assuming that the locations of
750  // its children in Loc are valid.
751  // Return nullptr if there is no valid placement for Node (for example, it
752  // uses an index value that is not available at the location required
753  // to dominate all children, etc.).
754 
755  // Find the nearest common dominator for:
756  // - all users, if the node is used, and
757  // - all children.
758  ValueVect Bs;
759  if (Node->Flags & GepNode::Used) {
760  // Append all blocks with uses of the original values to the
761  // block vector Bs.
762  NodeToUsesMap::iterator UF = Uses.find(Node);
763  assert(UF != Uses.end() && "Used node with no use information");
764  UseSet &Us = UF->second;
765  for (Use *U : Us) {
766  User *R = U->getUser();
767  if (!isa<Instruction>(R))
768  continue;
769  BasicBlock *PB = isa<PHINode>(R)
770  ? cast<PHINode>(R)->getIncomingBlock(*U)
771  : cast<Instruction>(R)->getParent();
772  Bs.push_back(PB);
773  }
774  }
775  // Append the location of each child.
776  NodeChildrenMap::iterator CF = NCM.find(Node);
777  if (CF != NCM.end()) {
778  NodeVect &Cs = CF->second;
779  for (GepNode *CN : Cs) {
780  NodeToValueMap::iterator LF = Loc.find(CN);
781  // If the child is only used in GEP instructions (i.e. is not used in
782  // non-GEP instructions), the nearest dominator computed for it may
783  // have been null. In such case it won't have a location available.
784  if (LF == Loc.end())
785  continue;
786  Bs.push_back(LF->second);
787  }
788  }
789 
790  BasicBlock *DomB = nearest_common_dominator(DT, Bs);
791  if (!DomB)
792  return nullptr;
793  // Check if the index used by Node dominates the computed dominator.
794  Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
795  if (IdxI && !DT->dominates(IdxI->getParent(), DomB))
796  return nullptr;
797 
798  // Avoid putting nodes into empty blocks.
799  while (is_empty(DomB)) {
800  DomTreeNode *N = (*DT)[DomB]->getIDom();
801  if (!N)
802  break;
803  DomB = N->getBlock();
804  }
805 
806  // Otherwise, DomB is fine. Update the location map.
807  Loc[Node] = DomB;
808  return DomB;
809 }
810 
811 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
812  NodeChildrenMap &NCM, NodeToValueMap &Loc) {
813  LLVM_DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n');
814  // Recalculate the placement of Node, after recursively recalculating the
815  // placements of all its children.
816  NodeChildrenMap::iterator CF = NCM.find(Node);
817  if (CF != NCM.end()) {
818  NodeVect &Cs = CF->second;
819  for (GepNode *C : Cs)
820  recalculatePlacementRec(C, NCM, Loc);
821  }
822  BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);
823  LLVM_DEBUG(dbgs() << "LocRec end for node:" << Node << '\n');
824  return LB;
825 }
826 
827 bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {
828  if (isa<Constant>(Val) || isa<Argument>(Val))
829  return true;
830  Instruction *In = dyn_cast<Instruction>(Val);
831  if (!In)
832  return false;
833  BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent();
834  return DT->properlyDominates(DefB, HdrB);
835 }
836 
837 bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {
838  if (Node->Flags & GepNode::Root)
839  if (!isInvariantIn(Node->BaseVal, L))
840  return false;
841  return isInvariantIn(Node->Idx, L);
842 }
843 
844 bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {
845  BasicBlock *HB = L->getHeader();
846  BasicBlock *LB = L->getLoopLatch();
847  // B must post-dominate the loop header or dominate the loop latch.
848  if (PDT->dominates(B, HB))
849  return true;
850  if (LB && DT->dominates(B, LB))
851  return true;
852  return false;
853 }
854 
856  if (BasicBlock *PH = L->getLoopPreheader())
857  return PH;
858  if (!OptSpeculate)
859  return nullptr;
860  DomTreeNode *DN = DT->getNode(L->getHeader());
861  if (!DN)
862  return nullptr;
863  return DN->getIDom()->getBlock();
864 }
865 
866 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
867  NodeChildrenMap &NCM, NodeToValueMap &Loc) {
868  // Find the "topmost" location for Node: it must be dominated by both,
869  // its parent (or the BaseVal, if it's a root node), and by the index
870  // value.
871  ValueVect Bs;
872  if (Node->Flags & GepNode::Root) {
873  if (Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal))
874  Bs.push_back(PIn->getParent());
875  } else {
876  Bs.push_back(Loc[Node->Parent]);
877  }
878  if (Instruction *IIn = dyn_cast<Instruction>(Node->Idx))
879  Bs.push_back(IIn->getParent());
880  BasicBlock *TopB = nearest_common_dominatee(DT, Bs);
881 
882  // Traverse the loop nest upwards until we find a loop in which Node
883  // is no longer invariant, or until we get to the upper limit of Node's
884  // placement. The traversal will also stop when a suitable "preheader"
885  // cannot be found for a given loop. The "preheader" may actually be
886  // a regular block outside of the loop (i.e. not guarded), in which case
887  // the Node will be speculated.
888  // For nodes that are not in the main path of the containing loop (i.e.
889  // are not executed in each iteration), do not move them out of the loop.
890  BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]);
891  if (LocB) {
892  Loop *Lp = LI->getLoopFor(LocB);
893  while (Lp) {
894  if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))
895  break;
896  BasicBlock *NewLoc = preheader(DT, Lp);
897  if (!NewLoc || !DT->dominates(TopB, NewLoc))
898  break;
899  Lp = Lp->getParentLoop();
900  LocB = NewLoc;
901  }
902  }
903  Loc[Node] = LocB;
904 
905  // Recursively compute the locations of all children nodes.
906  NodeChildrenMap::iterator CF = NCM.find(Node);
907  if (CF != NCM.end()) {
908  NodeVect &Cs = CF->second;
909  for (GepNode *C : Cs)
910  adjustForInvariance(C, NCM, Loc);
911  }
912  return LocB;
913 }
914 
915 namespace {
916 
917  struct LocationAsBlock {
918  LocationAsBlock(const NodeToValueMap &L) : Map(L) {}
919 
920  const NodeToValueMap &Map;
921  };
922 
924  const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ;
925  raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) {
926  for (const auto &I : Loc.Map) {
927  OS << I.first << " -> ";
928  if (BasicBlock *B = cast_or_null<BasicBlock>(I.second))
929  OS << B->getName() << '(' << B << ')';
930  else
931  OS << "<null-block>";
932  OS << '\n';
933  }
934  return OS;
935  }
936 
937  inline bool is_constant(GepNode *N) {
938  return isa<ConstantInt>(N->Idx);
939  }
940 
941 } // end anonymous namespace
942 
943 void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
944  NodeToValueMap &Loc) {
945  User *R = U->getUser();
946  LLVM_DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: " << *R
947  << '\n');
948  BasicBlock *PB = cast<Instruction>(R)->getParent();
949 
950  GepNode *N = Node;
951  GepNode *C = nullptr, *NewNode = nullptr;
952  while (is_constant(N) && !(N->Flags & GepNode::Root)) {
953  // XXX if (single-use) dont-replicate;
954  GepNode *NewN = new (*Mem) GepNode(N);
955  Nodes.push_back(NewN);
956  Loc[NewN] = PB;
957 
958  if (N == Node)
959  NewNode = NewN;
960  NewN->Flags &= ~GepNode::Used;
961  if (C)
962  C->Parent = NewN;
963  C = NewN;
964  N = N->Parent;
965  }
966  if (!NewNode)
967  return;
968 
969  // Move over all uses that share the same user as U from Node to NewNode.
970  NodeToUsesMap::iterator UF = Uses.find(Node);
971  assert(UF != Uses.end());
972  UseSet &Us = UF->second;
973  UseSet NewUs;
974  for (Use *U : Us) {
975  if (U->getUser() == R)
976  NewUs.insert(U);
977  }
978  for (Use *U : NewUs)
979  Us.remove(U); // erase takes an iterator.
980 
981  if (Us.empty()) {
982  Node->Flags &= ~GepNode::Used;
983  Uses.erase(UF);
984  }
985 
986  // Should at least have U in NewUs.
987  NewNode->Flags |= GepNode::Used;
988  LLVM_DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n');
989  assert(!NewUs.empty());
990  Uses[NewNode] = NewUs;
991 }
992 
993 void HexagonCommonGEP::separateConstantChains(GepNode *Node,
994  NodeChildrenMap &NCM, NodeToValueMap &Loc) {
995  // First approximation: extract all chains.
996  NodeSet Ns;
997  nodes_for_root(Node, NCM, Ns);
998 
999  LLVM_DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n');
1000  // Collect all used nodes together with the uses from loads and stores,
1001  // where the GEP node could be folded into the load/store instruction.
1002  NodeToUsesMap FNs; // Foldable nodes.
1003  for (GepNode *N : Ns) {
1004  if (!(N->Flags & GepNode::Used))
1005  continue;
1006  NodeToUsesMap::iterator UF = Uses.find(N);
1007  assert(UF != Uses.end());
1008  UseSet &Us = UF->second;
1009  // Loads/stores that use the node N.
1010  UseSet LSs;
1011  for (Use *U : Us) {
1012  User *R = U->getUser();
1013  // We're interested in uses that provide the address. It can happen
1014  // that the value may also be provided via GEP, but we won't handle
1015  // those cases here for now.
1016  if (LoadInst *Ld = dyn_cast<LoadInst>(R)) {
1017  unsigned PtrX = LoadInst::getPointerOperandIndex();
1018  if (&Ld->getOperandUse(PtrX) == U)
1019  LSs.insert(U);
1020  } else if (StoreInst *St = dyn_cast<StoreInst>(R)) {
1021  unsigned PtrX = StoreInst::getPointerOperandIndex();
1022  if (&St->getOperandUse(PtrX) == U)
1023  LSs.insert(U);
1024  }
1025  }
1026  // Even if the total use count is 1, separating the chain may still be
1027  // beneficial, since the constant chain may be longer than the GEP alone
1028  // would be (e.g. if the parent node has a constant index and also has
1029  // other children).
1030  if (!LSs.empty())
1031  FNs.insert(std::make_pair(N, LSs));
1032  }
1033 
1034  LLVM_DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs);
1035 
1036  for (auto &FN : FNs) {
1037  GepNode *N = FN.first;
1038  UseSet &Us = FN.second;
1039  for (Use *U : Us)
1040  separateChainForNode(N, U, Loc);
1041  }
1042 }
1043 
1044 void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1045  // Compute the inverse of the Node.Parent links. Also, collect the set
1046  // of root nodes.
1047  NodeChildrenMap NCM;
1048  NodeVect Roots;
1049  invert_find_roots(Nodes, NCM, Roots);
1050 
1051  // Compute the initial placement determined by the users' locations, and
1052  // the locations of the child nodes.
1053  for (GepNode *Root : Roots)
1054  recalculatePlacementRec(Root, NCM, Loc);
1055 
1056  LLVM_DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc));
1057 
1058  if (OptEnableInv) {
1059  for (GepNode *Root : Roots)
1060  adjustForInvariance(Root, NCM, Loc);
1061 
1062  LLVM_DEBUG(dbgs() << "Node placement after adjustment for invariance:\n"
1063  << LocationAsBlock(Loc));
1064  }
1065  if (OptEnableConst) {
1066  for (GepNode *Root : Roots)
1067  separateConstantChains(Root, NCM, Loc);
1068  }
1069  LLVM_DEBUG(dbgs() << "Node use information:\n" << Uses);
1070 
1071  // At the moment, there is no further refinement of the initial placement.
1072  // Such a refinement could include splitting the nodes if they are placed
1073  // too far from some of its users.
1074 
1075  LLVM_DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc));
1076 }
1077 
1078 Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
1079  BasicBlock *LocB) {
1080  LLVM_DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName()
1081  << " for nodes:\n"
1082  << NA);
1083  unsigned Num = NA.size();
1084  GepNode *RN = NA[0];
1085  assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root");
1086 
1087  GetElementPtrInst *NewInst = nullptr;
1088  Value *Input = RN->BaseVal;
1089  Type *InpTy = RN->PTy;
1090 
1091  unsigned Idx = 0;
1092  do {
1093  SmallVector<Value*, 4> IdxList;
1094  // If the type of the input of the first node is not a pointer,
1095  // we need to add an artificial i32 0 to the indices (because the
1096  // actual input in the IR will be a pointer).
1097  if (!(NA[Idx]->Flags & GepNode::Pointer)) {
1098  Type *Int32Ty = Type::getInt32Ty(*Ctx);
1099  IdxList.push_back(ConstantInt::get(Int32Ty, 0));
1100  }
1101 
1102  // Keep adding indices from NA until we have to stop and generate
1103  // an "intermediate" GEP.
1104  while (++Idx <= Num) {
1105  GepNode *N = NA[Idx-1];
1106  IdxList.push_back(N->Idx);
1107  if (Idx < Num) {
1108  // We have to stop if we reach a pointer.
1109  if (NA[Idx]->Flags & GepNode::Pointer)
1110  break;
1111  }
1112  }
1113  NewInst = GetElementPtrInst::Create(InpTy, Input, IdxList, "cgep", &*At);
1114  NewInst->setIsInBounds(RN->Flags & GepNode::InBounds);
1115  LLVM_DEBUG(dbgs() << "new GEP: " << *NewInst << '\n');
1116  if (Idx < Num) {
1117  Input = NewInst;
1118  InpTy = NA[Idx]->PTy;
1119  }
1120  } while (Idx <= Num);
1121 
1122  return NewInst;
1123 }
1124 
1125 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1126  NodeChildrenMap &NCM) {
1127  NodeVect Work;
1128  Work.push_back(Node);
1129 
1130  while (!Work.empty()) {
1131  NodeVect::iterator First = Work.begin();
1132  GepNode *N = *First;
1133  Work.erase(First);
1134  if (N->Flags & GepNode::Used) {
1135  NodeToUsesMap::iterator UF = Uses.find(N);
1136  assert(UF != Uses.end() && "No use information for used node");
1137  UseSet &Us = UF->second;
1138  for (const auto &U : Us)
1139  Values.push_back(U->getUser());
1140  }
1141  NodeChildrenMap::iterator CF = NCM.find(N);
1142  if (CF != NCM.end()) {
1143  NodeVect &Cs = CF->second;
1144  llvm::append_range(Work, Cs);
1145  }
1146  }
1147 }
1148 
1149 void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1150  LLVM_DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n');
1151  NodeChildrenMap NCM;
1152  NodeVect Roots;
1153  // Compute the inversion again, since computing placement could alter
1154  // "parent" relation between nodes.
1155  invert_find_roots(Nodes, NCM, Roots);
1156 
1157  while (!Roots.empty()) {
1158  NodeVect::iterator First = Roots.begin();
1159  GepNode *Root = *First, *Last = *First;
1160  Roots.erase(First);
1161 
1162  NodeVect NA; // Nodes to assemble.
1163  // Append to NA all child nodes up to (and including) the first child
1164  // that:
1165  // (1) has more than 1 child, or
1166  // (2) is used, or
1167  // (3) has a child located in a different block.
1168  bool LastUsed = false;
1169  unsigned LastCN = 0;
1170  // The location may be null if the computation failed (it can legitimately
1171  // happen for nodes created from dead GEPs).
1172  Value *LocV = Loc[Last];
1173  if (!LocV)
1174  continue;
1175  BasicBlock *LastB = cast<BasicBlock>(LocV);
1176  do {
1177  NA.push_back(Last);
1178  LastUsed = (Last->Flags & GepNode::Used);
1179  if (LastUsed)
1180  break;
1181  NodeChildrenMap::iterator CF = NCM.find(Last);
1182  LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1183  if (LastCN != 1)
1184  break;
1185  GepNode *Child = CF->second.front();
1186  BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
1187  if (ChildB != nullptr && LastB != ChildB)
1188  break;
1189  Last = Child;
1190  } while (true);
1191 
1192  BasicBlock::iterator InsertAt = LastB->getTerminator()->getIterator();
1193  if (LastUsed || LastCN > 0) {
1194  ValueVect Urs;
1195  getAllUsersForNode(Root, Urs, NCM);
1196  BasicBlock::iterator FirstUse = first_use_of_in_block(Urs, LastB);
1197  if (FirstUse != LastB->end())
1198  InsertAt = FirstUse;
1199  }
1200 
1201  // Generate a new instruction for NA.
1202  Value *NewInst = fabricateGEP(NA, InsertAt, LastB);
1203 
1204  // Convert all the children of Last node into roots, and append them
1205  // to the Roots list.
1206  if (LastCN > 0) {
1207  NodeVect &Cs = NCM[Last];
1208  for (GepNode *CN : Cs) {
1209  CN->Flags &= ~GepNode::Internal;
1210  CN->Flags |= GepNode::Root;
1211  CN->BaseVal = NewInst;
1212  Roots.push_back(CN);
1213  }
1214  }
1215 
1216  // Lastly, if the Last node was used, replace all uses with the new GEP.
1217  // The uses reference the original GEP values.
1218  if (LastUsed) {
1219  NodeToUsesMap::iterator UF = Uses.find(Last);
1220  assert(UF != Uses.end() && "No use information found");
1221  UseSet &Us = UF->second;
1222  for (Use *U : Us)
1223  U->set(NewInst);
1224  }
1225  }
1226 }
1227 
1228 void HexagonCommonGEP::removeDeadCode() {
1229  ValueVect BO;
1230  BO.push_back(&Fn->front());
1231 
1232  for (unsigned i = 0; i < BO.size(); ++i) {
1233  BasicBlock *B = cast<BasicBlock>(BO[i]);
1234  for (auto DTN : children<DomTreeNode*>(DT->getNode(B)))
1235  BO.push_back(DTN->getBlock());
1236  }
1237 
1238  for (Value *V : llvm::reverse(BO)) {
1239  BasicBlock *B = cast<BasicBlock>(V);
1240  ValueVect Ins;
1241  for (Instruction &I : llvm::reverse(*B))
1242  Ins.push_back(&I);
1243  for (Value *I : Ins) {
1244  Instruction *In = cast<Instruction>(I);
1246  In->eraseFromParent();
1247  }
1248  }
1249 }
1250 
1252  if (skipFunction(F))
1253  return false;
1254 
1255  // For now bail out on C++ exception handling.
1256  for (const BasicBlock &BB : F)
1257  for (const Instruction &I : BB)
1258  if (isa<InvokeInst>(I) || isa<LandingPadInst>(I))
1259  return false;
1260 
1261  Fn = &F;
1262  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1263  PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1264  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1265  Ctx = &F.getContext();
1266 
1267  Nodes.clear();
1268  Uses.clear();
1269  NodeOrder.clear();
1270 
1272  Mem = &Allocator;
1273 
1274  collect();
1275  common();
1276 
1277  NodeToValueMap Loc;
1278  computeNodePlacement(Loc);
1279  materialize(Loc);
1280  removeDeadCode();
1281 
1282 #ifdef EXPENSIVE_CHECKS
1283  // Run this only when expensive checks are enabled.
1284  if (verifyFunction(F, &dbgs()))
1285  report_fatal_error("Broken function");
1286 #endif
1287  return true;
1288 }
1289 
1290 namespace llvm {
1291 
1293  return new HexagonCommonGEP();
1294  }
1295 
1296 } // end namespace llvm
i
i
Definition: README.txt:29
Int32Ty
IntegerType * Int32Ty
Definition: NVVMIntrRange.cpp:67
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
false::in_set::in_set
in_set(const NodeSet &S)
Definition: HexagonCommonGEP.cpp:309
false::GepNode::BaseVal
Value * BaseVal
Definition: HexagonCommonGEP.cpp:201
llvm::GetElementPtrInst::idx_begin
op_iterator idx_begin()
Definition: Instructions.h:1043
llvm::GetElementPtrInst::setIsInBounds
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
Definition: Instructions.cpp:1806
OptSpeculate
static cl::opt< bool > OptSpeculate("commgep-speculate", cl::init(true), cl::Hidden, cl::ZeroOrMore)
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
llvm::DominatorTreeBase::findNearestCommonDominator
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
Definition: GenericDomTree.h:468
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:264
llvm::AArch64CC::NE
@ NE
Definition: AArch64BaseInfo.h:256
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:217
T
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
StringRef.h
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
nodes_for_root
static void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM, NodeSet &Nodes)
Definition: HexagonCommonGEP.cpp:444
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1176
llvm::NodeSet::iterator
SetVector< SUnit * >::const_iterator iterator
Definition: MachinePipeliner.h:322
llvm::Value::hasName
bool hasName() const
Definition: Value.h:261
Allocator.h
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1773
Local.h
node_eq
static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq, NodePairSet &Ne)
Definition: HexagonCommonGEP.cpp:496
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::verifyFunction
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:5920
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::SpecificBumpPtrAllocator
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:374
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:357
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
llvm::LoadInst::getPointerOperandIndex
static unsigned getPointerOperandIndex()
Definition: Instructions.h:274
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:227
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1271
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::Value::user_begin
user_iterator user_begin()
Definition: Value.h:397
STLExtras.h
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
LLVM_ATTRIBUTE_UNUSED
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:189
Use.h
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:241
false::dump_node_container
void dump_node_container(raw_ostream &OS, const NodeContainer &S)
Definition: HexagonCommonGEP.cpp:276
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::GetElementPtrInst::getSourceElementType
Type * getSourceElementType() const
Definition: Instructions.h:1008
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:208
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:583
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
GraphTraits.h
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:234
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
llvm::GetElementPtrInst::isInBounds
bool isInBounds() const
Determine whether the GEP has the inbounds flag.
Definition: Instructions.cpp:1810
false::in_set
Definition: HexagonCommonGEP.cpp:308
Instruction.h
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::NodeOrder
@ NodeOrder
Definition: SIMachineScheduler.h:37
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::msgpack::Type::Map
@ Map
PostDominators.h
P2
This might compile to this xmm1 xorps xmm0 movss xmm0 ret Now consider if the code caused xmm1 to get spilled This might produce this xmm1 movaps xmm0 movaps xmm1 movss xmm0 ret since the reload is only used by these we could fold it into the producing something like xmm1 movaps xmm0 ret saving two instructions The basic idea is that a reload from a spill if only one byte chunk is bring in zeros the one element instead of elements This can be used to simplify a variety of shuffle where the elements are fixed zeros This code generates ugly probably due to costs being off or< 4 x float > * P2
Definition: README-SSE.txt:278
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
node_class
static const NodeSet * node_class(GepNode *N, NodeSymRel &Rel)
Definition: HexagonCommonGEP.cpp:470
llvm::Type::getStructName
StringRef getStructName() const
Definition: DerivedTypes.h:344
llvm::PostDominatorTreeWrapperPass
Definition: PostDominators.h:73
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:143
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::ConstantInt::get
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:925
llvm::initializeHexagonCommonGEPPass
void initializeHexagonCommonGEPPass(PassRegistry &)
false::GepNode::Idx
Value * Idx
Definition: HexagonCommonGEP.cpp:203
llvm::NodeSet
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
Definition: MachinePipeliner.h:311
llvm::None
const NoneType None
Definition: None.h:23
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::DominatorTreeBase::getRoot
NodeT * getRoot() const
Definition: GenericDomTree.h:461
llvm::cl::ZeroOrMore
@ ZeroOrMore
Definition: CommandLine.h:120
PB
PassBuilder PB(Machine, PassOpts->PTO, None, &PIC)
llvm::Value::user_end
user_iterator user_end()
Definition: Value.h:405
first_use_of_in_block
static BasicBlock::iterator first_use_of_in_block(T &Values, BasicBlock *B)
Definition: HexagonCommonGEP.cpp:716
llvm::tgtok::In
@ In
Definition: TGLexer.h:51
BasicBlock.h
llvm::cl::opt< bool >
false::GepNode::GepNode
GepNode(const GepNode *N)
Definition: HexagonCommonGEP.cpp:209
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:309
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:58
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP", false, false) INITIALIZE_PASS_END(HexagonCommonGEP
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:933
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
ArrayRef.h
false::GepNode
Definition: HexagonCommonGEP.cpp:177
hcommgep
hcommgep
Definition: HexagonCommonGEP.cpp:172
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
node_pair
static NodePair node_pair(GepNode *N1, GepNode *N2)
Definition: HexagonCommonGEP.cpp:480
nearest_common_dominator
static BasicBlock * nearest_common_dominator(DominatorTree *DT, T &Blocks)
Definition: HexagonCommonGEP.cpp:661
llvm::IndexedInstrProf::HashT::Last
@ Last
OptEnableConst
static cl::opt< bool > OptEnableConst("commgep-const", cl::init(true), cl::Hidden, cl::ZeroOrMore)
node_hash
static unsigned node_hash(GepNode *N)
Definition: HexagonCommonGEP.cpp:488
is_empty
static bool is_empty(const BasicBlock *B)
Definition: HexagonCommonGEP.cpp:742
llvm::GetElementPtrInst::Create
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:959
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:398
llvm::LoopInfo
Definition: LoopInfo.h:1086
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::createHexagonCommonGEP
FunctionPass * createHexagonCommonGEP()
Definition: HexagonCommonGEP.cpp:1292
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
uint32_t
Compiler.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1789
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:313
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:180
llvm::BasicBlock::getTerminator
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:152
FoldingSet.h
llvm::GetElementPtrInst::idx_end
op_iterator idx_end()
Definition: Instructions.h:1045
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
Constant.h
invert_find_roots
static void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM, NodeVect &Roots)
Definition: HexagonCommonGEP.cpp:432
Verifier.h
H
#define H(x, y, z)
Definition: MD5.cpp:57
false::GepNode::GepNode
GepNode()
Definition: HexagonCommonGEP.cpp:208
llvm::Value::user_iterator
user_iterator_impl< User > user_iterator
Definition: Value.h:390
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
Casting.h
llvm::GetElementPtrInst::getTypeAtIndex
static Type * getTypeAtIndex(Type *Ty, Value *Idx)
Return the type of the element at the given index of an indexable type.
Definition: Instructions.cpp:1728
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
false::GepNode::Parent
GepNode * Parent
Definition: HexagonCommonGEP.cpp:200
false::GepNode::Flags
uint32_t Flags
Definition: HexagonCommonGEP.cpp:198
llvm::GetElementPtrInst::indices
iterator_range< op_iterator > indices()
Definition: Instructions.h:1048
Instructions.h
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:211
SmallVector.h
User.h
Dominators.h
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:146
N
#define N
preheader
static BasicBlock * preheader(DominatorTree *DT, Loop *L)
Definition: HexagonCommonGEP.cpp:855
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::MipsISD::Ins
@ Ins
Definition: MipsISelLowering.h:157
llvm::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
DerivedTypes.h
llvm::NodeSet::insert
bool insert(SUnit *SU)
Definition: MachinePipeliner.h:345
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
RN
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
Definition: README_P9.txt:262
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
OptEnableInv
static cl::opt< bool > OptEnableInv("commgep-inv", cl::init(true), cl::Hidden, cl::ZeroOrMore)
raw_ostream.h
llvm::StoreInst::getPointerOperandIndex
static unsigned getPointerOperandIndex()
Definition: Instructions.h:408
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:39
llvm::StructType::isLiteral
bool isLiteral() const
Return true if this type is uniqued by structural equivalence, false if it is a struct definition.
Definition: DerivedTypes.h:277
Value.h
InitializePasses.h
llvm::GetElementPtrInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:1056
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
nearest_common_dominatee
static BasicBlock * nearest_common_dominatee(DominatorTree *DT, T &Blocks)
Definition: HexagonCommonGEP.cpp:690
false::GepNode::PTy
Type * PTy
Definition: HexagonCommonGEP.cpp:204
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38