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