LLVM  13.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/StringRef.h"
15 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/IR/BasicBlock.h"
18 #include "llvm/IR/Constant.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/DerivedTypes.h"
21 #include "llvm/IR/Dominators.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/Type.h"
26 #include "llvm/IR/Use.h"
27 #include "llvm/IR/User.h"
28 #include "llvm/IR/Value.h"
29 #include "llvm/IR/Verifier.h"
30 #include "llvm/InitializePasses.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Support/Allocator.h"
33 #include "llvm/Support/Casting.h"
35 #include "llvm/Support/Compiler.h"
36 #include "llvm/Support/Debug.h"
39 #include <algorithm>
40 #include <cassert>
41 #include <cstddef>
42 #include <cstdint>
43 #include <iterator>
44 #include <map>
45 #include <set>
46 #include <utility>
47 #include <vector>
48 
49 #define DEBUG_TYPE "commgep"
50 
51 using namespace llvm;
52 
53 static cl::opt<bool> OptSpeculate("commgep-speculate", cl::init(true),
55 
56 static cl::opt<bool> OptEnableInv("commgep-inv", cl::init(true), cl::Hidden,
58 
59 static cl::opt<bool> OptEnableConst("commgep-const", cl::init(true),
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  };
184 
185  uint32_t Flags = 0;
186  union {
189  };
190  Value *Idx = nullptr;
191  Type *PTy = nullptr; // Type of the pointer operand.
192 
193  GepNode() : Parent(nullptr) {}
194  GepNode(const GepNode *N) : Flags(N->Flags), Idx(N->Idx), PTy(N->PTy) {
195  if (Flags & Root)
196  BaseVal = N->BaseVal;
197  else
198  Parent = N->Parent;
199  }
200 
201  friend raw_ostream &operator<< (raw_ostream &OS, const GepNode &GN);
202  };
203 
204  Type *next_type(Type *Ty, Value *Idx) {
205  if (auto *PTy = dyn_cast<PointerType>(Ty))
206  return PTy->getElementType();
207  return GetElementPtrInst::getTypeAtIndex(Ty, Idx);
208  }
209 
211  OS << "{ {";
212  bool Comma = false;
213  if (GN.Flags & GepNode::Root) {
214  OS << "root";
215  Comma = true;
216  }
217  if (GN.Flags & GepNode::Internal) {
218  if (Comma)
219  OS << ',';
220  OS << "internal";
221  Comma = true;
222  }
223  if (GN.Flags & GepNode::Used) {
224  if (Comma)
225  OS << ',';
226  OS << "used";
227  }
228  if (GN.Flags & GepNode::InBounds) {
229  if (Comma)
230  OS << ',';
231  OS << "inbounds";
232  }
233  OS << "} ";
234  if (GN.Flags & GepNode::Root)
235  OS << "BaseVal:" << GN.BaseVal->getName() << '(' << GN.BaseVal << ')';
236  else
237  OS << "Parent:" << GN.Parent;
238 
239  OS << " Idx:";
240  if (ConstantInt *CI = dyn_cast<ConstantInt>(GN.Idx))
241  OS << CI->getValue().getSExtValue();
242  else if (GN.Idx->hasName())
243  OS << GN.Idx->getName();
244  else
245  OS << "<anon> =" << *GN.Idx;
246 
247  OS << " PTy:";
248  if (GN.PTy->isStructTy()) {
249  StructType *STy = cast<StructType>(GN.PTy);
250  if (!STy->isLiteral())
251  OS << GN.PTy->getStructName();
252  else
253  OS << "<anon-struct>:" << *STy;
254  }
255  else
256  OS << *GN.PTy;
257  OS << " }";
258  return OS;
259  }
260 
261  template <typename NodeContainer>
262  void dump_node_container(raw_ostream &OS, const NodeContainer &S) {
263  using const_iterator = typename NodeContainer::const_iterator;
264 
265  for (const_iterator I = S.begin(), E = S.end(); I != E; ++I)
266  OS << *I << ' ' << **I << '\n';
267  }
268 
270  const NodeVect &S) LLVM_ATTRIBUTE_UNUSED;
271  raw_ostream &operator<< (raw_ostream &OS, const NodeVect &S) {
272  dump_node_container(OS, S);
273  return OS;
274  }
275 
277  const NodeToUsesMap &M) LLVM_ATTRIBUTE_UNUSED;
278  raw_ostream &operator<< (raw_ostream &OS, const NodeToUsesMap &M){
279  using const_iterator = NodeToUsesMap::const_iterator;
280 
281  for (const_iterator I = M.begin(), E = M.end(); I != E; ++I) {
282  const UseSet &Us = I->second;
283  OS << I->first << " -> #" << Us.size() << '{';
284  for (UseSet::const_iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
285  User *R = (*J)->getUser();
286  if (R->hasName())
287  OS << ' ' << R->getName();
288  else
289  OS << " <?>(" << *R << ')';
290  }
291  OS << " }\n";
292  }
293  return OS;
294  }
295 
296  struct in_set {
297  in_set(const NodeSet &S) : NS(S) {}
298 
299  bool operator() (GepNode *N) const {
300  return NS.find(N) != NS.end();
301  }
302 
303  private:
304  const NodeSet &NS;
305  };
306 
307 } // end anonymous namespace
308 
309 inline void *operator new(size_t, SpecificBumpPtrAllocator<GepNode> &A) {
310  return A.Allocate();
311 }
312 
313 void HexagonCommonGEP::getBlockTraversalOrder(BasicBlock *Root,
314  ValueVect &Order) {
315  // Compute block ordering for a typical DT-based traversal of the flow
316  // graph: "before visiting a block, all of its dominators must have been
317  // visited".
318 
319  Order.push_back(Root);
320  for (auto *DTN : children<DomTreeNode*>(DT->getNode(Root)))
321  getBlockTraversalOrder(DTN->getBlock(), Order);
322 }
323 
324 bool HexagonCommonGEP::isHandledGepForm(GetElementPtrInst *GepI) {
325  // No vector GEPs.
326  if (!GepI->getType()->isPointerTy())
327  return false;
328  // No GEPs without any indices. (Is this possible?)
329  if (GepI->idx_begin() == GepI->idx_end())
330  return false;
331  return true;
332 }
333 
334 void HexagonCommonGEP::processGepInst(GetElementPtrInst *GepI,
335  ValueToNodeMap &NM) {
336  LLVM_DEBUG(dbgs() << "Visiting GEP: " << *GepI << '\n');
337  GepNode *N = new (*Mem) GepNode;
338  Value *PtrOp = GepI->getPointerOperand();
339  uint32_t InBounds = GepI->isInBounds() ? GepNode::InBounds : 0;
340  ValueToNodeMap::iterator F = NM.find(PtrOp);
341  if (F == NM.end()) {
342  N->BaseVal = PtrOp;
343  N->Flags |= GepNode::Root | InBounds;
344  } else {
345  // If PtrOp was a GEP instruction, it must have already been processed.
346  // The ValueToNodeMap entry for it is the last gep node in the generated
347  // chain. Link to it here.
348  N->Parent = F->second;
349  }
350  N->PTy = PtrOp->getType();
351  N->Idx = *GepI->idx_begin();
352 
353  // Collect the list of users of this GEP instruction. Will add it to the
354  // last node created for it.
355  UseSet Us;
356  for (Value::user_iterator UI = GepI->user_begin(), UE = GepI->user_end();
357  UI != UE; ++UI) {
358  // Check if this gep is used by anything other than other geps that
359  // we will process.
360  if (isa<GetElementPtrInst>(*UI)) {
361  GetElementPtrInst *UserG = cast<GetElementPtrInst>(*UI);
362  if (isHandledGepForm(UserG))
363  continue;
364  }
365  Us.insert(&UI.getUse());
366  }
367  Nodes.push_back(N);
368  NodeOrder.insert(N);
369 
370  // Skip the first index operand, since we only handle 0. This dereferences
371  // the pointer operand.
372  GepNode *PN = N;
373  Type *PtrTy = cast<PointerType>(PtrOp->getType())->getElementType();
374  for (User::op_iterator OI = GepI->idx_begin()+1, OE = GepI->idx_end();
375  OI != OE; ++OI) {
376  Value *Op = *OI;
377  GepNode *Nx = new (*Mem) GepNode;
378  Nx->Parent = PN; // Link Nx to the previous node.
379  Nx->Flags |= GepNode::Internal | InBounds;
380  Nx->PTy = PtrTy;
381  Nx->Idx = Op;
382  Nodes.push_back(Nx);
383  NodeOrder.insert(Nx);
384  PN = Nx;
385 
386  PtrTy = next_type(PtrTy, Op);
387  }
388 
389  // After last node has been created, update the use information.
390  if (!Us.empty()) {
391  PN->Flags |= GepNode::Used;
392  Uses[PN].insert(Us.begin(), Us.end());
393  }
394 
395  // Link the last node with the originating GEP instruction. This is to
396  // help with linking chained GEP instructions.
397  NM.insert(std::make_pair(GepI, PN));
398 }
399 
400 void HexagonCommonGEP::collect() {
401  // Establish depth-first traversal order of the dominator tree.
402  ValueVect BO;
403  getBlockTraversalOrder(&Fn->front(), BO);
404 
405  // The creation of gep nodes requires DT-traversal. When processing a GEP
406  // instruction that uses another GEP instruction as the base pointer, the
407  // gep node for the base pointer should already exist.
408  ValueToNodeMap NM;
409  for (ValueVect::iterator I = BO.begin(), E = BO.end(); I != E; ++I) {
410  BasicBlock *B = cast<BasicBlock>(*I);
411  for (BasicBlock::iterator J = B->begin(), F = B->end(); J != F; ++J) {
412  if (!isa<GetElementPtrInst>(J))
413  continue;
414  GetElementPtrInst *GepI = cast<GetElementPtrInst>(J);
415  if (isHandledGepForm(GepI))
416  processGepInst(GepI, NM);
417  }
418  }
419 
420  LLVM_DEBUG(dbgs() << "Gep nodes after initial collection:\n" << Nodes);
421 }
422 
423 static void invert_find_roots(const NodeVect &Nodes, NodeChildrenMap &NCM,
424  NodeVect &Roots) {
425  using const_iterator = NodeVect::const_iterator;
426 
427  for (const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
428  GepNode *N = *I;
429  if (N->Flags & GepNode::Root) {
430  Roots.push_back(N);
431  continue;
432  }
433  GepNode *PN = N->Parent;
434  NCM[PN].push_back(N);
435  }
436 }
437 
438 static void nodes_for_root(GepNode *Root, NodeChildrenMap &NCM,
439  NodeSet &Nodes) {
440  NodeVect Work;
441  Work.push_back(Root);
442  Nodes.insert(Root);
443 
444  while (!Work.empty()) {
445  NodeVect::iterator First = Work.begin();
446  GepNode *N = *First;
447  Work.erase(First);
448  NodeChildrenMap::iterator CF = NCM.find(N);
449  if (CF != NCM.end()) {
450  llvm::append_range(Work, CF->second);
451  Nodes.insert(CF->second.begin(), CF->second.end());
452  }
453  }
454 }
455 
456 namespace {
457 
458  using NodeSymRel = std::set<NodeSet>;
459  using NodePair = std::pair<GepNode *, GepNode *>;
460  using NodePairSet = std::set<NodePair>;
461 
462 } // end anonymous namespace
463 
464 static const NodeSet *node_class(GepNode *N, NodeSymRel &Rel) {
465  for (NodeSymRel::iterator I = Rel.begin(), E = Rel.end(); I != E; ++I)
466  if (I->count(N))
467  return &*I;
468  return nullptr;
469 }
470 
471  // Create an ordered pair of GepNode pointers. The pair will be used in
472  // determining equality. The only purpose of the ordering is to eliminate
473  // duplication due to the commutativity of equality/non-equality.
474 static NodePair node_pair(GepNode *N1, GepNode *N2) {
475  uintptr_t P1 = reinterpret_cast<uintptr_t>(N1);
476  uintptr_t P2 = reinterpret_cast<uintptr_t>(N2);
477  if (P1 <= P2)
478  return std::make_pair(N1, N2);
479  return std::make_pair(N2, N1);
480 }
481 
482 static unsigned node_hash(GepNode *N) {
483  // Include everything except flags and parent.
485  ID.AddPointer(N->Idx);
486  ID.AddPointer(N->PTy);
487  return ID.ComputeHash();
488 }
489 
490 static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq,
491  NodePairSet &Ne) {
492  // Don't cache the result for nodes with different hashes. The hash
493  // comparison is fast enough.
494  if (node_hash(N1) != node_hash(N2))
495  return false;
496 
497  NodePair NP = node_pair(N1, N2);
498  NodePairSet::iterator FEq = Eq.find(NP);
499  if (FEq != Eq.end())
500  return true;
501  NodePairSet::iterator FNe = Ne.find(NP);
502  if (FNe != Ne.end())
503  return false;
504  // Not previously compared.
505  bool Root1 = N1->Flags & GepNode::Root;
506  bool Root2 = N2->Flags & GepNode::Root;
507  NodePair P = node_pair(N1, N2);
508  // If the Root flag has different values, the nodes are different.
509  // If both nodes are root nodes, but their base pointers differ,
510  // they are different.
511  if (Root1 != Root2 || (Root1 && N1->BaseVal != N2->BaseVal)) {
512  Ne.insert(P);
513  return false;
514  }
515  // Here the root flags are identical, and for root nodes the
516  // base pointers are equal, so the root nodes are equal.
517  // For non-root nodes, compare their parent nodes.
518  if (Root1 || node_eq(N1->Parent, N2->Parent, Eq, Ne)) {
519  Eq.insert(P);
520  return true;
521  }
522  return false;
523 }
524 
525 void HexagonCommonGEP::common() {
526  // The essence of this commoning is finding gep nodes that are equal.
527  // To do this we need to compare all pairs of nodes. To save time,
528  // first, partition the set of all nodes into sets of potentially equal
529  // nodes, and then compare pairs from within each partition.
530  using NodeSetMap = std::map<unsigned, NodeSet>;
531  NodeSetMap MaybeEq;
532 
533  for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
534  GepNode *N = *I;
535  unsigned H = node_hash(N);
536  MaybeEq[H].insert(N);
537  }
538 
539  // Compute the equivalence relation for the gep nodes. Use two caches,
540  // one for equality and the other for non-equality.
541  NodeSymRel EqRel; // Equality relation (as set of equivalence classes).
542  NodePairSet Eq, Ne; // Caches.
543  for (NodeSetMap::iterator I = MaybeEq.begin(), E = MaybeEq.end();
544  I != E; ++I) {
545  NodeSet &S = I->second;
546  for (NodeSet::iterator NI = S.begin(), NE = S.end(); NI != NE; ++NI) {
547  GepNode *N = *NI;
548  // If node already has a class, then the class must have been created
549  // in a prior iteration of this loop. Since equality is transitive,
550  // nothing more will be added to that class, so skip it.
551  if (node_class(N, EqRel))
552  continue;
553 
554  // Create a new class candidate now.
555  NodeSet C;
556  for (NodeSet::iterator NJ = std::next(NI); NJ != NE; ++NJ)
557  if (node_eq(N, *NJ, Eq, Ne))
558  C.insert(*NJ);
559  // If Tmp is empty, N would be the only element in it. Don't bother
560  // creating a class for it then.
561  if (!C.empty()) {
562  C.insert(N); // Finalize the set before adding it to the relation.
563  std::pair<NodeSymRel::iterator, bool> Ins = EqRel.insert(C);
564  (void)Ins;
565  assert(Ins.second && "Cannot add a class");
566  }
567  }
568  }
569 
570  LLVM_DEBUG({
571  dbgs() << "Gep node equality:\n";
572  for (NodePairSet::iterator I = Eq.begin(), E = Eq.end(); I != E; ++I)
573  dbgs() << "{ " << I->first << ", " << I->second << " }\n";
574 
575  dbgs() << "Gep equivalence classes:\n";
576  for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
577  dbgs() << '{';
578  const NodeSet &S = *I;
579  for (NodeSet::const_iterator J = S.begin(), F = S.end(); J != F; ++J) {
580  if (J != S.begin())
581  dbgs() << ',';
582  dbgs() << ' ' << *J;
583  }
584  dbgs() << " }\n";
585  }
586  });
587 
588  // Create a projection from a NodeSet to the minimal element in it.
589  using ProjMap = std::map<const NodeSet *, GepNode *>;
590  ProjMap PM;
591  for (NodeSymRel::iterator I = EqRel.begin(), E = EqRel.end(); I != E; ++I) {
592  const NodeSet &S = *I;
593  GepNode *Min = *std::min_element(S.begin(), S.end(), NodeOrder);
594  std::pair<ProjMap::iterator,bool> Ins = PM.insert(std::make_pair(&S, Min));
595  (void)Ins;
596  assert(Ins.second && "Cannot add minimal element");
597 
598  // Update the min element's flags, and user list.
599  uint32_t Flags = 0;
600  UseSet &MinUs = Uses[Min];
601  for (NodeSet::iterator J = S.begin(), F = S.end(); J != F; ++J) {
602  GepNode *N = *J;
603  uint32_t NF = N->Flags;
604  // If N is used, append all original values of N to the list of
605  // original values of Min.
606  if (NF & GepNode::Used)
607  MinUs.insert(Uses[N].begin(), Uses[N].end());
608  Flags |= NF;
609  }
610  if (MinUs.empty())
611  Uses.erase(Min);
612 
613  // The collected flags should include all the flags from the min element.
614  assert((Min->Flags & Flags) == Min->Flags);
615  Min->Flags = Flags;
616  }
617 
618  // Commoning: for each non-root gep node, replace "Parent" with the
619  // selected (minimum) node from the corresponding equivalence class.
620  // If a given parent does not have an equivalence class, leave it
621  // unchanged (it means that it's the only element in its class).
622  for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
623  GepNode *N = *I;
624  if (N->Flags & GepNode::Root)
625  continue;
626  const NodeSet *PC = node_class(N->Parent, EqRel);
627  if (!PC)
628  continue;
629  ProjMap::iterator F = PM.find(PC);
630  if (F == PM.end())
631  continue;
632  // Found a replacement, use it.
633  GepNode *Rep = F->second;
634  N->Parent = Rep;
635  }
636 
637  LLVM_DEBUG(dbgs() << "Gep nodes after commoning:\n" << Nodes);
638 
639  // Finally, erase the nodes that are no longer used.
640  NodeSet Erase;
641  for (NodeVect::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
642  GepNode *N = *I;
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(*I);
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 (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
765  Use *U = *I;
766  User *R = U->getUser();
767  if (!isa<Instruction>(R))
768  continue;
769  BasicBlock *PB = isa<PHINode>(R)
770  ? cast<PHINode>(R)->getIncomingBlock(*U)
771  : cast<Instruction>(R)->getParent();
772  Bs.push_back(PB);
773  }
774  }
775  // Append the location of each child.
776  NodeChildrenMap::iterator CF = NCM.find(Node);
777  if (CF != NCM.end()) {
778  NodeVect &Cs = CF->second;
779  for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
780  GepNode *CN = *I;
781  NodeToValueMap::iterator LF = Loc.find(CN);
782  // If the child is only used in GEP instructions (i.e. is not used in
783  // non-GEP instructions), the nearest dominator computed for it may
784  // have been null. In such case it won't have a location available.
785  if (LF == Loc.end())
786  continue;
787  Bs.push_back(LF->second);
788  }
789  }
790 
791  BasicBlock *DomB = nearest_common_dominator(DT, Bs);
792  if (!DomB)
793  return nullptr;
794  // Check if the index used by Node dominates the computed dominator.
795  Instruction *IdxI = dyn_cast<Instruction>(Node->Idx);
796  if (IdxI && !DT->dominates(IdxI->getParent(), DomB))
797  return nullptr;
798 
799  // Avoid putting nodes into empty blocks.
800  while (is_empty(DomB)) {
801  DomTreeNode *N = (*DT)[DomB]->getIDom();
802  if (!N)
803  break;
804  DomB = N->getBlock();
805  }
806 
807  // Otherwise, DomB is fine. Update the location map.
808  Loc[Node] = DomB;
809  return DomB;
810 }
811 
812 BasicBlock *HexagonCommonGEP::recalculatePlacementRec(GepNode *Node,
813  NodeChildrenMap &NCM, NodeToValueMap &Loc) {
814  LLVM_DEBUG(dbgs() << "LocRec begin for node:" << Node << '\n');
815  // Recalculate the placement of Node, after recursively recalculating the
816  // placements of all its children.
817  NodeChildrenMap::iterator CF = NCM.find(Node);
818  if (CF != NCM.end()) {
819  NodeVect &Cs = CF->second;
820  for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I)
821  recalculatePlacementRec(*I, NCM, Loc);
822  }
823  BasicBlock *LB = recalculatePlacement(Node, NCM, Loc);
824  LLVM_DEBUG(dbgs() << "LocRec end for node:" << Node << '\n');
825  return LB;
826 }
827 
828 bool HexagonCommonGEP::isInvariantIn(Value *Val, Loop *L) {
829  if (isa<Constant>(Val) || isa<Argument>(Val))
830  return true;
831  Instruction *In = dyn_cast<Instruction>(Val);
832  if (!In)
833  return false;
834  BasicBlock *HdrB = L->getHeader(), *DefB = In->getParent();
835  return DT->properlyDominates(DefB, HdrB);
836 }
837 
838 bool HexagonCommonGEP::isInvariantIn(GepNode *Node, Loop *L) {
839  if (Node->Flags & GepNode::Root)
840  if (!isInvariantIn(Node->BaseVal, L))
841  return false;
842  return isInvariantIn(Node->Idx, L);
843 }
844 
845 bool HexagonCommonGEP::isInMainPath(BasicBlock *B, Loop *L) {
846  BasicBlock *HB = L->getHeader();
847  BasicBlock *LB = L->getLoopLatch();
848  // B must post-dominate the loop header or dominate the loop latch.
849  if (PDT->dominates(B, HB))
850  return true;
851  if (LB && DT->dominates(B, LB))
852  return true;
853  return false;
854 }
855 
857  if (BasicBlock *PH = L->getLoopPreheader())
858  return PH;
859  if (!OptSpeculate)
860  return nullptr;
861  DomTreeNode *DN = DT->getNode(L->getHeader());
862  if (!DN)
863  return nullptr;
864  return DN->getIDom()->getBlock();
865 }
866 
867 BasicBlock *HexagonCommonGEP::adjustForInvariance(GepNode *Node,
868  NodeChildrenMap &NCM, NodeToValueMap &Loc) {
869  // Find the "topmost" location for Node: it must be dominated by both,
870  // its parent (or the BaseVal, if it's a root node), and by the index
871  // value.
872  ValueVect Bs;
873  if (Node->Flags & GepNode::Root) {
874  if (Instruction *PIn = dyn_cast<Instruction>(Node->BaseVal))
875  Bs.push_back(PIn->getParent());
876  } else {
877  Bs.push_back(Loc[Node->Parent]);
878  }
879  if (Instruction *IIn = dyn_cast<Instruction>(Node->Idx))
880  Bs.push_back(IIn->getParent());
881  BasicBlock *TopB = nearest_common_dominatee(DT, Bs);
882 
883  // Traverse the loop nest upwards until we find a loop in which Node
884  // is no longer invariant, or until we get to the upper limit of Node's
885  // placement. The traversal will also stop when a suitable "preheader"
886  // cannot be found for a given loop. The "preheader" may actually be
887  // a regular block outside of the loop (i.e. not guarded), in which case
888  // the Node will be speculated.
889  // For nodes that are not in the main path of the containing loop (i.e.
890  // are not executed in each iteration), do not move them out of the loop.
891  BasicBlock *LocB = cast_or_null<BasicBlock>(Loc[Node]);
892  if (LocB) {
893  Loop *Lp = LI->getLoopFor(LocB);
894  while (Lp) {
895  if (!isInvariantIn(Node, Lp) || !isInMainPath(LocB, Lp))
896  break;
897  BasicBlock *NewLoc = preheader(DT, Lp);
898  if (!NewLoc || !DT->dominates(TopB, NewLoc))
899  break;
900  Lp = Lp->getParentLoop();
901  LocB = NewLoc;
902  }
903  }
904  Loc[Node] = LocB;
905 
906  // Recursively compute the locations of all children nodes.
907  NodeChildrenMap::iterator CF = NCM.find(Node);
908  if (CF != NCM.end()) {
909  NodeVect &Cs = CF->second;
910  for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I)
911  adjustForInvariance(*I, NCM, Loc);
912  }
913  return LocB;
914 }
915 
916 namespace {
917 
918  struct LocationAsBlock {
919  LocationAsBlock(const NodeToValueMap &L) : Map(L) {}
920 
921  const NodeToValueMap &Map;
922  };
923 
925  const LocationAsBlock &Loc) LLVM_ATTRIBUTE_UNUSED ;
926  raw_ostream &operator<< (raw_ostream &OS, const LocationAsBlock &Loc) {
927  for (NodeToValueMap::const_iterator I = Loc.Map.begin(), E = Loc.Map.end();
928  I != E; ++I) {
929  OS << I->first << " -> ";
930  BasicBlock *B = cast<BasicBlock>(I->second);
931  OS << B->getName() << '(' << B << ')';
932  OS << '\n';
933  }
934  return OS;
935  }
936 
937  inline bool is_constant(GepNode *N) {
938  return isa<ConstantInt>(N->Idx);
939  }
940 
941 } // end anonymous namespace
942 
943 void HexagonCommonGEP::separateChainForNode(GepNode *Node, Use *U,
944  NodeToValueMap &Loc) {
945  User *R = U->getUser();
946  LLVM_DEBUG(dbgs() << "Separating chain for node (" << Node << ") user: " << *R
947  << '\n');
948  BasicBlock *PB = cast<Instruction>(R)->getParent();
949 
950  GepNode *N = Node;
951  GepNode *C = nullptr, *NewNode = nullptr;
952  while (is_constant(N) && !(N->Flags & GepNode::Root)) {
953  // XXX if (single-use) dont-replicate;
954  GepNode *NewN = new (*Mem) GepNode(N);
955  Nodes.push_back(NewN);
956  Loc[NewN] = PB;
957 
958  if (N == Node)
959  NewNode = NewN;
960  NewN->Flags &= ~GepNode::Used;
961  if (C)
962  C->Parent = NewN;
963  C = NewN;
964  N = N->Parent;
965  }
966  if (!NewNode)
967  return;
968 
969  // Move over all uses that share the same user as U from Node to NewNode.
970  NodeToUsesMap::iterator UF = Uses.find(Node);
971  assert(UF != Uses.end());
972  UseSet &Us = UF->second;
973  UseSet NewUs;
974  for (Use *U : Us) {
975  if (U->getUser() == R)
976  NewUs.insert(U);
977  }
978  for (Use *U : NewUs)
979  Us.remove(U); // erase takes an iterator.
980 
981  if (Us.empty()) {
982  Node->Flags &= ~GepNode::Used;
983  Uses.erase(UF);
984  }
985 
986  // Should at least have U in NewUs.
987  NewNode->Flags |= GepNode::Used;
988  LLVM_DEBUG(dbgs() << "new node: " << NewNode << " " << *NewNode << '\n');
989  assert(!NewUs.empty());
990  Uses[NewNode] = NewUs;
991 }
992 
993 void HexagonCommonGEP::separateConstantChains(GepNode *Node,
994  NodeChildrenMap &NCM, NodeToValueMap &Loc) {
995  // First approximation: extract all chains.
996  NodeSet Ns;
997  nodes_for_root(Node, NCM, Ns);
998 
999  LLVM_DEBUG(dbgs() << "Separating constant chains for node: " << Node << '\n');
1000  // Collect all used nodes together with the uses from loads and stores,
1001  // where the GEP node could be folded into the load/store instruction.
1002  NodeToUsesMap FNs; // Foldable nodes.
1003  for (NodeSet::iterator I = Ns.begin(), E = Ns.end(); I != E; ++I) {
1004  GepNode *N = *I;
1005  if (!(N->Flags & GepNode::Used))
1006  continue;
1007  NodeToUsesMap::iterator UF = Uses.find(N);
1008  assert(UF != Uses.end());
1009  UseSet &Us = UF->second;
1010  // Loads/stores that use the node N.
1011  UseSet LSs;
1012  for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J) {
1013  Use *U = *J;
1014  User *R = U->getUser();
1015  // We're interested in uses that provide the address. It can happen
1016  // that the value may also be provided via GEP, but we won't handle
1017  // those cases here for now.
1018  if (LoadInst *Ld = dyn_cast<LoadInst>(R)) {
1019  unsigned PtrX = LoadInst::getPointerOperandIndex();
1020  if (&Ld->getOperandUse(PtrX) == U)
1021  LSs.insert(U);
1022  } else if (StoreInst *St = dyn_cast<StoreInst>(R)) {
1023  unsigned PtrX = StoreInst::getPointerOperandIndex();
1024  if (&St->getOperandUse(PtrX) == U)
1025  LSs.insert(U);
1026  }
1027  }
1028  // Even if the total use count is 1, separating the chain may still be
1029  // beneficial, since the constant chain may be longer than the GEP alone
1030  // would be (e.g. if the parent node has a constant index and also has
1031  // other children).
1032  if (!LSs.empty())
1033  FNs.insert(std::make_pair(N, LSs));
1034  }
1035 
1036  LLVM_DEBUG(dbgs() << "Nodes with foldable users:\n" << FNs);
1037 
1038  for (NodeToUsesMap::iterator I = FNs.begin(), E = FNs.end(); I != E; ++I) {
1039  GepNode *N = I->first;
1040  UseSet &Us = I->second;
1041  for (UseSet::iterator J = Us.begin(), F = Us.end(); J != F; ++J)
1042  separateChainForNode(N, *J, Loc);
1043  }
1044 }
1045 
1046 void HexagonCommonGEP::computeNodePlacement(NodeToValueMap &Loc) {
1047  // Compute the inverse of the Node.Parent links. Also, collect the set
1048  // of root nodes.
1049  NodeChildrenMap NCM;
1050  NodeVect Roots;
1051  invert_find_roots(Nodes, NCM, Roots);
1052 
1053  // Compute the initial placement determined by the users' locations, and
1054  // the locations of the child nodes.
1055  for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1056  recalculatePlacementRec(*I, NCM, Loc);
1057 
1058  LLVM_DEBUG(dbgs() << "Initial node placement:\n" << LocationAsBlock(Loc));
1059 
1060  if (OptEnableInv) {
1061  for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1062  adjustForInvariance(*I, NCM, Loc);
1063 
1064  LLVM_DEBUG(dbgs() << "Node placement after adjustment for invariance:\n"
1065  << LocationAsBlock(Loc));
1066  }
1067  if (OptEnableConst) {
1068  for (NodeVect::iterator I = Roots.begin(), E = Roots.end(); I != E; ++I)
1069  separateConstantChains(*I, NCM, Loc);
1070  }
1071  LLVM_DEBUG(dbgs() << "Node use information:\n" << Uses);
1072 
1073  // At the moment, there is no further refinement of the initial placement.
1074  // Such a refinement could include splitting the nodes if they are placed
1075  // too far from some of its users.
1076 
1077  LLVM_DEBUG(dbgs() << "Final node placement:\n" << LocationAsBlock(Loc));
1078 }
1079 
1080 Value *HexagonCommonGEP::fabricateGEP(NodeVect &NA, BasicBlock::iterator At,
1081  BasicBlock *LocB) {
1082  LLVM_DEBUG(dbgs() << "Fabricating GEP in " << LocB->getName()
1083  << " for nodes:\n"
1084  << NA);
1085  unsigned Num = NA.size();
1086  GepNode *RN = NA[0];
1087  assert((RN->Flags & GepNode::Root) && "Creating GEP for non-root");
1088 
1089  GetElementPtrInst *NewInst = nullptr;
1090  Value *Input = RN->BaseVal;
1091  Value **IdxList = new Value*[Num+1];
1092  unsigned nax = 0;
1093  do {
1094  unsigned IdxC = 0;
1095  // If the type of the input of the first node is not a pointer,
1096  // we need to add an artificial i32 0 to the indices (because the
1097  // actual input in the IR will be a pointer).
1098  if (!NA[nax]->PTy->isPointerTy()) {
1099  Type *Int32Ty = Type::getInt32Ty(*Ctx);
1100  IdxList[IdxC++] = ConstantInt::get(Int32Ty, 0);
1101  }
1102 
1103  // Keep adding indices from NA until we have to stop and generate
1104  // an "intermediate" GEP.
1105  while (++nax <= Num) {
1106  GepNode *N = NA[nax-1];
1107  IdxList[IdxC++] = N->Idx;
1108  if (nax < Num) {
1109  // We have to stop, if the expected type of the output of this node
1110  // is not the same as the input type of the next node.
1111  Type *NextTy = next_type(N->PTy, N->Idx);
1112  if (NextTy != NA[nax]->PTy)
1113  break;
1114  }
1115  }
1116  ArrayRef<Value*> A(IdxList, IdxC);
1117  Type *InpTy = Input->getType();
1118  Type *ElTy = cast<PointerType>(InpTy->getScalarType())->getElementType();
1119  NewInst = GetElementPtrInst::Create(ElTy, Input, A, "cgep", &*At);
1120  NewInst->setIsInBounds(RN->Flags & GepNode::InBounds);
1121  LLVM_DEBUG(dbgs() << "new GEP: " << *NewInst << '\n');
1122  Input = NewInst;
1123  } while (nax <= Num);
1124 
1125  delete[] IdxList;
1126  return NewInst;
1127 }
1128 
1129 void HexagonCommonGEP::getAllUsersForNode(GepNode *Node, ValueVect &Values,
1130  NodeChildrenMap &NCM) {
1131  NodeVect Work;
1132  Work.push_back(Node);
1133 
1134  while (!Work.empty()) {
1135  NodeVect::iterator First = Work.begin();
1136  GepNode *N = *First;
1137  Work.erase(First);
1138  if (N->Flags & GepNode::Used) {
1139  NodeToUsesMap::iterator UF = Uses.find(N);
1140  assert(UF != Uses.end() && "No use information for used node");
1141  UseSet &Us = UF->second;
1142  for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I)
1143  Values.push_back((*I)->getUser());
1144  }
1145  NodeChildrenMap::iterator CF = NCM.find(N);
1146  if (CF != NCM.end()) {
1147  NodeVect &Cs = CF->second;
1148  llvm::append_range(Work, Cs);
1149  }
1150  }
1151 }
1152 
1153 void HexagonCommonGEP::materialize(NodeToValueMap &Loc) {
1154  LLVM_DEBUG(dbgs() << "Nodes before materialization:\n" << Nodes << '\n');
1155  NodeChildrenMap NCM;
1156  NodeVect Roots;
1157  // Compute the inversion again, since computing placement could alter
1158  // "parent" relation between nodes.
1159  invert_find_roots(Nodes, NCM, Roots);
1160 
1161  while (!Roots.empty()) {
1162  NodeVect::iterator First = Roots.begin();
1163  GepNode *Root = *First, *Last = *First;
1164  Roots.erase(First);
1165 
1166  NodeVect NA; // Nodes to assemble.
1167  // Append to NA all child nodes up to (and including) the first child
1168  // that:
1169  // (1) has more than 1 child, or
1170  // (2) is used, or
1171  // (3) has a child located in a different block.
1172  bool LastUsed = false;
1173  unsigned LastCN = 0;
1174  // The location may be null if the computation failed (it can legitimately
1175  // happen for nodes created from dead GEPs).
1176  Value *LocV = Loc[Last];
1177  if (!LocV)
1178  continue;
1179  BasicBlock *LastB = cast<BasicBlock>(LocV);
1180  do {
1181  NA.push_back(Last);
1182  LastUsed = (Last->Flags & GepNode::Used);
1183  if (LastUsed)
1184  break;
1185  NodeChildrenMap::iterator CF = NCM.find(Last);
1186  LastCN = (CF != NCM.end()) ? CF->second.size() : 0;
1187  if (LastCN != 1)
1188  break;
1189  GepNode *Child = CF->second.front();
1190  BasicBlock *ChildB = cast_or_null<BasicBlock>(Loc[Child]);
1191  if (ChildB != nullptr && LastB != ChildB)
1192  break;
1193  Last = Child;
1194  } while (true);
1195 
1196  BasicBlock::iterator InsertAt = LastB->getTerminator()->getIterator();
1197  if (LastUsed || LastCN > 0) {
1198  ValueVect Urs;
1199  getAllUsersForNode(Root, Urs, NCM);
1200  BasicBlock::iterator FirstUse = first_use_of_in_block(Urs, LastB);
1201  if (FirstUse != LastB->end())
1202  InsertAt = FirstUse;
1203  }
1204 
1205  // Generate a new instruction for NA.
1206  Value *NewInst = fabricateGEP(NA, InsertAt, LastB);
1207 
1208  // Convert all the children of Last node into roots, and append them
1209  // to the Roots list.
1210  if (LastCN > 0) {
1211  NodeVect &Cs = NCM[Last];
1212  for (NodeVect::iterator I = Cs.begin(), E = Cs.end(); I != E; ++I) {
1213  GepNode *CN = *I;
1214  CN->Flags &= ~GepNode::Internal;
1215  CN->Flags |= GepNode::Root;
1216  CN->BaseVal = NewInst;
1217  Roots.push_back(CN);
1218  }
1219  }
1220 
1221  // Lastly, if the Last node was used, replace all uses with the new GEP.
1222  // The uses reference the original GEP values.
1223  if (LastUsed) {
1224  NodeToUsesMap::iterator UF = Uses.find(Last);
1225  assert(UF != Uses.end() && "No use information found");
1226  UseSet &Us = UF->second;
1227  for (UseSet::iterator I = Us.begin(), E = Us.end(); I != E; ++I) {
1228  Use *U = *I;
1229  U->set(NewInst);
1230  }
1231  }
1232  }
1233 }
1234 
1235 void HexagonCommonGEP::removeDeadCode() {
1236  ValueVect BO;
1237  BO.push_back(&Fn->front());
1238 
1239  for (unsigned i = 0; i < BO.size(); ++i) {
1240  BasicBlock *B = cast<BasicBlock>(BO[i]);
1241  for (auto DTN : children<DomTreeNode*>(DT->getNode(B)))
1242  BO.push_back(DTN->getBlock());
1243  }
1244 
1245  for (unsigned i = BO.size(); i > 0; --i) {
1246  BasicBlock *B = cast<BasicBlock>(BO[i-1]);
1247  BasicBlock::InstListType &IL = B->getInstList();
1248 
1249  using reverse_iterator = BasicBlock::InstListType::reverse_iterator;
1250 
1251  ValueVect Ins;
1252  for (reverse_iterator I = IL.rbegin(), E = IL.rend(); I != E; ++I)
1253  Ins.push_back(&*I);
1254  for (ValueVect::iterator I = Ins.begin(), E = Ins.end(); I != E; ++I) {
1255  Instruction *In = cast<Instruction>(*I);
1257  In->eraseFromParent();
1258  }
1259  }
1260 }
1261 
1263  if (skipFunction(F))
1264  return false;
1265 
1266  // For now bail out on C++ exception handling.
1267  for (Function::iterator A = F.begin(), Z = F.end(); A != Z; ++A)
1268  for (BasicBlock::iterator I = A->begin(), E = A->end(); I != E; ++I)
1269  if (isa<InvokeInst>(I) || isa<LandingPadInst>(I))
1270  return false;
1271 
1272  Fn = &F;
1273  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1274  PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1275  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1276  Ctx = &F.getContext();
1277 
1278  Nodes.clear();
1279  Uses.clear();
1280  NodeOrder.clear();
1281 
1283  Mem = &Allocator;
1284 
1285  collect();
1286  common();
1287 
1288  NodeToValueMap Loc;
1289  computeNodePlacement(Loc);
1290  materialize(Loc);
1291  removeDeadCode();
1292 
1293 #ifdef EXPENSIVE_CHECKS
1294  // Run this only when expensive checks are enabled.
1295  if (verifyFunction(F, &dbgs()))
1296  report_fatal_error("Broken function");
1297 #endif
1298  return true;
1299 }
1300 
1301 namespace llvm {
1302 
1304  return new HexagonCommonGEP();
1305  }
1306 
1307 } // 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:297
false::GepNode::BaseVal
Value * BaseVal
Definition: HexagonCommonGEP.cpp:188
llvm::GetElementPtrInst::idx_begin
op_iterator idx_begin()
Definition: Instructions.h:1037
llvm::GetElementPtrInst::setIsInBounds
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
Definition: Instructions.cpp:1795
OptSpeculate
static cl::opt< bool > OptSpeculate("commgep-speculate", cl::init(true), cl::Hidden, cl::ZeroOrMore)
llvm
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:237
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::NodeSet::end
iterator end()
Definition: MachinePipeliner.h:422
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:229
llvm::Function
Definition: Function.h:61
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:438
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:317
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:1674
Local.h
node_eq
static bool node_eq(GepNode *N1, GepNode *N2, NodePairSet &Eq, NodePairSet &Ne)
Definition: HexagonCommonGEP.cpp:490
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:5724
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:376
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
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:268
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:1258
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:410
STLExtras.h
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
LLVM_ATTRIBUTE_UNUSED
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:188
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
Use.h
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:204
false::dump_node_container
void dump_node_container(raw_ostream &OS, const NodeContainer &S)
Definition: HexagonCommonGEP.cpp:262
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:129
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:583
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
GraphTraits.h
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:233
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:1799
false::in_set
Definition: HexagonCommonGEP.cpp:296
Instruction.h
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
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:35
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:464
llvm::Type::getStructName
StringRef getStructName() const
Definition: DerivedTypes.h:346
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:281
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
llvm::report_fatal_error
LLVM_ATTRIBUTE_NORETURN 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:50
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:885
llvm::initializeHexagonCommonGEPPass
void initializeHexagonCommonGEPPass(PassRegistry &)
false::GepNode::Idx
Value * Idx
Definition: HexagonCommonGEP.cpp:190
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
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:117
llvm::Value::user_end
user_iterator user_end()
Definition: Value.h:418
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:194
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:303
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:905
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
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: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:216
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
node_pair
static NodePair node_pair(GepNode *N1, GepNode *N2)
Definition: HexagonCommonGEP.cpp:474
nearest_common_dominator
static BasicBlock * nearest_common_dominator(DominatorTree *DT, T &Blocks)
Definition: HexagonCommonGEP.cpp:660
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:482
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:931
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
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 has no side ef...
Definition: Local.cpp:388
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::SymbolTableList< Instruction >
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:212
llvm::createHexagonCommonGEP
FunctionPass * createHexagonCommonGEP()
Definition: HexagonCommonGEP.cpp:1303
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
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:1690
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:298
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
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:148
FoldingSet.h
llvm::GetElementPtrInst::idx_end
op_iterator idx_end()
Definition: Instructions.h:1039
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:423
false::next_type
Type * next_type(Type *Ty, Value *Idx)
Definition: HexagonCommonGEP.cpp:204
Verifier.h
H
#define H(x, y, z)
Definition: MD5.cpp:58
false::GepNode::GepNode
GepNode()
Definition: HexagonCommonGEP.cpp:193
llvm::Value::user_iterator
user_iterator_impl< User > user_iterator
Definition: Value.h:403
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
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:1717
Function.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
false::GepNode::Parent
GepNode * Parent
Definition: HexagonCommonGEP.cpp:187
false::GepNode::Flags
uint32_t Flags
Definition: HexagonCommonGEP.cpp:185
Instructions.h
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:223
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:856
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: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
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:278
Value.h
InitializePasses.h
llvm::GetElementPtrInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:1050
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:689
false::GepNode::PTy
Type * PTy
Definition: HexagonCommonGEP.cpp:191
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:66
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38