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