LLVM  14.0.0git
HexagonVectorLoopCarriedReuse.cpp
Go to the documentation of this file.
1 //===- HexagonVectorLoopCarriedReuse.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 // This pass removes the computation of provably redundant expressions that have
10 // been computed earlier in a previous iteration. It relies on the use of PHIs
11 // to identify loop carried dependences. This is scalar replacement for vector
12 // types.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/SetVector.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/LoopPass.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/DerivedTypes.h"
24 #include "llvm/IR/IRBuilder.h"
25 #include "llvm/IR/Instruction.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/IntrinsicInst.h"
28 #include "llvm/IR/Intrinsics.h"
29 #include "llvm/IR/IntrinsicsHexagon.h"
30 #include "llvm/IR/Use.h"
31 #include "llvm/IR/User.h"
32 #include "llvm/IR/Value.h"
33 #include "llvm/InitializePasses.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/Casting.h"
37 #include "llvm/Support/Compiler.h"
38 #include "llvm/Support/Debug.h"
40 #include "llvm/Transforms/Scalar.h"
41 #include "llvm/Transforms/Utils.h"
42 #include <algorithm>
43 #include <cassert>
44 #include <cstddef>
45 #include <map>
46 #include <memory>
47 #include <set>
48 
49 using namespace llvm;
50 
51 #define DEBUG_TYPE "hexagon-vlcr"
52 
53 STATISTIC(HexagonNumVectorLoopCarriedReuse,
54  "Number of values that were reused from a previous iteration.");
55 
56 static cl::opt<int> HexagonVLCRIterationLim("hexagon-vlcr-iteration-lim",
57  cl::Hidden,
58  cl::desc("Maximum distance of loop carried dependences that are handled"),
60 
61 namespace llvm {
62 
65 
66 } // end namespace llvm
67 
68 namespace {
69 
70  // See info about DepChain in the comments at the top of this file.
71  using ChainOfDependences = SmallVector<Instruction *, 4>;
72 
73  class DepChain {
74  ChainOfDependences Chain;
75 
76  public:
77  bool isIdentical(DepChain &Other) const {
78  if (Other.size() != size())
79  return false;
80  ChainOfDependences &OtherChain = Other.getChain();
81  for (int i = 0; i < size(); ++i) {
82  if (Chain[i] != OtherChain[i])
83  return false;
84  }
85  return true;
86  }
87 
88  ChainOfDependences &getChain() {
89  return Chain;
90  }
91 
92  int size() const {
93  return Chain.size();
94  }
95 
96  void clear() {
97  Chain.clear();
98  }
99 
100  void push_back(Instruction *I) {
101  Chain.push_back(I);
102  }
103 
104  int iterations() const {
105  return size() - 1;
106  }
107 
108  Instruction *front() const {
109  return Chain.front();
110  }
111 
112  Instruction *back() const {
113  return Chain.back();
114  }
115 
116  Instruction *&operator[](const int index) {
117  return Chain[index];
118  }
119 
120  friend raw_ostream &operator<< (raw_ostream &OS, const DepChain &D);
121  };
122 
124  raw_ostream &operator<<(raw_ostream &OS, const DepChain &D) {
125  const ChainOfDependences &CD = D.Chain;
126  int ChainSize = CD.size();
127  OS << "**DepChain Start::**\n";
128  for (int i = 0; i < ChainSize -1; ++i) {
129  OS << *(CD[i]) << " -->\n";
130  }
131  OS << *CD[ChainSize-1] << "\n";
132  return OS;
133  }
134 
135  struct ReuseValue {
136  Instruction *Inst2Replace = nullptr;
137 
138  // In the new PHI node that we'll construct this is the value that'll be
139  // used over the backedge. This is the value that gets reused from a
140  // previous iteration.
141  Instruction *BackedgeInst = nullptr;
142  std::map<Instruction *, DepChain *> DepChains;
143  int Iterations = -1;
144 
145  ReuseValue() = default;
146 
147  void reset() {
148  Inst2Replace = nullptr;
149  BackedgeInst = nullptr;
150  DepChains.clear();
151  Iterations = -1;
152  }
153  bool isDefined() { return Inst2Replace != nullptr; }
154  };
155 
157  raw_ostream &operator<<(raw_ostream &OS, const ReuseValue &RU) {
158  OS << "** ReuseValue ***\n";
159  OS << "Instruction to Replace: " << *(RU.Inst2Replace) << "\n";
160  OS << "Backedge Instruction: " << *(RU.BackedgeInst) << "\n";
161  return OS;
162  }
163 
164  class HexagonVectorLoopCarriedReuseLegacyPass : public LoopPass {
165  public:
166  static char ID;
167 
168  explicit HexagonVectorLoopCarriedReuseLegacyPass() : LoopPass(ID) {
171  }
172 
173  StringRef getPassName() const override {
174  return "Hexagon-specific loop carried reuse for HVX vectors";
175  }
176 
177  void getAnalysisUsage(AnalysisUsage &AU) const override {
181  AU.setPreservesCFG();
182  }
183 
184  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
185  };
186 
187  class HexagonVectorLoopCarriedReuse {
188  public:
189  HexagonVectorLoopCarriedReuse(Loop *L) : CurLoop(L){};
190 
191  bool run();
192 
193  private:
194  SetVector<DepChain *> Dependences;
195  std::set<Instruction *> ReplacedInsts;
196  Loop *CurLoop;
197  ReuseValue ReuseCandidate;
198 
199  bool doVLCR();
200  void findLoopCarriedDeps();
201  void findValueToReuse();
202  void findDepChainFromPHI(Instruction *I, DepChain &D);
203  void reuseValue();
204  Value *findValueInBlock(Value *Op, BasicBlock *BB);
205  DepChain *getDepChainBtwn(Instruction *I1, Instruction *I2, int Iters);
206  bool isEquivalentOperation(Instruction *I1, Instruction *I2);
207  bool canReplace(Instruction *I);
208  bool isCallInstCommutative(CallInst *C);
209  };
210 
211 } // end anonymous namespace
212 
214 
215 INITIALIZE_PASS_BEGIN(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
216  "Hexagon-specific predictive commoning for HVX vectors",
217  false, false)
218 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
219 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
220 INITIALIZE_PASS_END(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
221  "Hexagon-specific predictive commoning for HVX vectors",
223 
227  LPMUpdater &U) {
228  HexagonVectorLoopCarriedReuse Vlcr(&L);
229  if (!Vlcr.run())
230  return PreservedAnalyses::all();
232  PA.preserveSet<CFGAnalyses>();
233  return PA;
234 }
235 
236 bool HexagonVectorLoopCarriedReuseLegacyPass::runOnLoop(Loop *L,
237  LPPassManager &LPM) {
238  if (skipLoop(L))
239  return false;
240  HexagonVectorLoopCarriedReuse Vlcr(L);
241  return Vlcr.run();
242 }
243 
244 bool HexagonVectorLoopCarriedReuse::run() {
245  if (!CurLoop->getLoopPreheader())
246  return false;
247 
248  // Work only on innermost loops.
249  if (!CurLoop->getSubLoops().empty())
250  return false;
251 
252  // Work only on single basic blocks loops.
253  if (CurLoop->getNumBlocks() != 1)
254  return false;
255 
256  return doVLCR();
257 }
258 
259 bool HexagonVectorLoopCarriedReuse::isCallInstCommutative(CallInst *C) {
260  switch (C->getCalledFunction()->getIntrinsicID()) {
261  case Intrinsic::hexagon_V6_vaddb:
262  case Intrinsic::hexagon_V6_vaddb_128B:
263  case Intrinsic::hexagon_V6_vaddh:
264  case Intrinsic::hexagon_V6_vaddh_128B:
265  case Intrinsic::hexagon_V6_vaddw:
266  case Intrinsic::hexagon_V6_vaddw_128B:
267  case Intrinsic::hexagon_V6_vaddubh:
268  case Intrinsic::hexagon_V6_vaddubh_128B:
269  case Intrinsic::hexagon_V6_vadduhw:
270  case Intrinsic::hexagon_V6_vadduhw_128B:
271  case Intrinsic::hexagon_V6_vaddhw:
272  case Intrinsic::hexagon_V6_vaddhw_128B:
273  case Intrinsic::hexagon_V6_vmaxb:
274  case Intrinsic::hexagon_V6_vmaxb_128B:
275  case Intrinsic::hexagon_V6_vmaxh:
276  case Intrinsic::hexagon_V6_vmaxh_128B:
277  case Intrinsic::hexagon_V6_vmaxw:
278  case Intrinsic::hexagon_V6_vmaxw_128B:
279  case Intrinsic::hexagon_V6_vmaxub:
280  case Intrinsic::hexagon_V6_vmaxub_128B:
281  case Intrinsic::hexagon_V6_vmaxuh:
282  case Intrinsic::hexagon_V6_vmaxuh_128B:
283  case Intrinsic::hexagon_V6_vminub:
284  case Intrinsic::hexagon_V6_vminub_128B:
285  case Intrinsic::hexagon_V6_vminuh:
286  case Intrinsic::hexagon_V6_vminuh_128B:
287  case Intrinsic::hexagon_V6_vminb:
288  case Intrinsic::hexagon_V6_vminb_128B:
289  case Intrinsic::hexagon_V6_vminh:
290  case Intrinsic::hexagon_V6_vminh_128B:
291  case Intrinsic::hexagon_V6_vminw:
292  case Intrinsic::hexagon_V6_vminw_128B:
293  case Intrinsic::hexagon_V6_vmpyub:
294  case Intrinsic::hexagon_V6_vmpyub_128B:
295  case Intrinsic::hexagon_V6_vmpyuh:
296  case Intrinsic::hexagon_V6_vmpyuh_128B:
297  case Intrinsic::hexagon_V6_vavgub:
298  case Intrinsic::hexagon_V6_vavgub_128B:
299  case Intrinsic::hexagon_V6_vavgh:
300  case Intrinsic::hexagon_V6_vavgh_128B:
301  case Intrinsic::hexagon_V6_vavguh:
302  case Intrinsic::hexagon_V6_vavguh_128B:
303  case Intrinsic::hexagon_V6_vavgw:
304  case Intrinsic::hexagon_V6_vavgw_128B:
305  case Intrinsic::hexagon_V6_vavgb:
306  case Intrinsic::hexagon_V6_vavgb_128B:
307  case Intrinsic::hexagon_V6_vavguw:
308  case Intrinsic::hexagon_V6_vavguw_128B:
309  case Intrinsic::hexagon_V6_vabsdiffh:
310  case Intrinsic::hexagon_V6_vabsdiffh_128B:
311  case Intrinsic::hexagon_V6_vabsdiffub:
312  case Intrinsic::hexagon_V6_vabsdiffub_128B:
313  case Intrinsic::hexagon_V6_vabsdiffuh:
314  case Intrinsic::hexagon_V6_vabsdiffuh_128B:
315  case Intrinsic::hexagon_V6_vabsdiffw:
316  case Intrinsic::hexagon_V6_vabsdiffw_128B:
317  return true;
318  default:
319  return false;
320  }
321 }
322 
323 bool HexagonVectorLoopCarriedReuse::isEquivalentOperation(Instruction *I1,
324  Instruction *I2) {
325  if (!I1->isSameOperationAs(I2))
326  return false;
327  // This check is in place specifically for intrinsics. isSameOperationAs will
328  // return two for any two hexagon intrinsics because they are essentially the
329  // same instruciton (CallInst). We need to scratch the surface to see if they
330  // are calls to the same function.
331  if (CallInst *C1 = dyn_cast<CallInst>(I1)) {
332  if (CallInst *C2 = dyn_cast<CallInst>(I2)) {
333  if (C1->getCalledFunction() != C2->getCalledFunction())
334  return false;
335  }
336  }
337 
338  // If both the Instructions are of Vector Type and any of the element
339  // is integer constant, check their values too for equivalence.
340  if (I1->getType()->isVectorTy() && I2->getType()->isVectorTy()) {
341  unsigned NumOperands = I1->getNumOperands();
342  for (unsigned i = 0; i < NumOperands; ++i) {
343  ConstantInt *C1 = dyn_cast<ConstantInt>(I1->getOperand(i));
344  ConstantInt *C2 = dyn_cast<ConstantInt>(I2->getOperand(i));
345  if(!C1) continue;
346  assert(C2);
347  if (C1->getSExtValue() != C2->getSExtValue())
348  return false;
349  }
350  }
351 
352  return true;
353 }
354 
355 bool HexagonVectorLoopCarriedReuse::canReplace(Instruction *I) {
356  const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
357  if (!II)
358  return true;
359 
360  switch (II->getIntrinsicID()) {
361  case Intrinsic::hexagon_V6_hi:
362  case Intrinsic::hexagon_V6_lo:
363  case Intrinsic::hexagon_V6_hi_128B:
364  case Intrinsic::hexagon_V6_lo_128B:
365  LLVM_DEBUG(dbgs() << "Not considering for reuse: " << *II << "\n");
366  return false;
367  default:
368  return true;
369  }
370 }
371 void HexagonVectorLoopCarriedReuse::findValueToReuse() {
372  for (auto *D : Dependences) {
373  LLVM_DEBUG(dbgs() << "Processing dependence " << *(D->front()) << "\n");
374  if (D->iterations() > HexagonVLCRIterationLim) {
375  LLVM_DEBUG(
376  dbgs()
377  << ".. Skipping because number of iterations > than the limit\n");
378  continue;
379  }
380 
381  PHINode *PN = cast<PHINode>(D->front());
382  Instruction *BEInst = D->back();
383  int Iters = D->iterations();
384  BasicBlock *BB = PN->getParent();
385  LLVM_DEBUG(dbgs() << "Checking if any uses of " << *PN
386  << " can be reused\n");
387 
389  for (Use &U : PN->uses()) {
390  Instruction *User = cast<Instruction>(U.getUser());
391 
392  if (User->getParent() != BB)
393  continue;
394  if (ReplacedInsts.count(User)) {
395  LLVM_DEBUG(dbgs() << *User
396  << " has already been replaced. Skipping...\n");
397  continue;
398  }
399  if (isa<PHINode>(User))
400  continue;
401  if (User->mayHaveSideEffects())
402  continue;
403  if (!canReplace(User))
404  continue;
405 
406  PNUsers.push_back(User);
407  }
408  LLVM_DEBUG(dbgs() << PNUsers.size() << " use(s) of the PHI in the block\n");
409 
410  // For each interesting use I of PN, find an Instruction BEUser that
411  // performs the same operation as I on BEInst and whose other operands,
412  // if any, can also be rematerialized in OtherBB. We stop when we find the
413  // first such Instruction BEUser. This is because once BEUser is
414  // rematerialized in OtherBB, we may find more such "fixup" opportunities
415  // in this block. So, we'll start over again.
416  for (Instruction *I : PNUsers) {
417  for (Use &U : BEInst->uses()) {
418  Instruction *BEUser = cast<Instruction>(U.getUser());
419 
420  if (BEUser->getParent() != BB)
421  continue;
422  if (!isEquivalentOperation(I, BEUser))
423  continue;
424 
425  int NumOperands = I->getNumOperands();
426 
427  // Take operands of each PNUser one by one and try to find DepChain
428  // with every operand of the BEUser. If any of the operands of BEUser
429  // has DepChain with current operand of the PNUser, break the matcher
430  // loop. Keep doing this for Every PNUser operand. If PNUser operand
431  // does not have DepChain with any of the BEUser operand, break the
432  // outer matcher loop, mark the BEUser as null and reset the ReuseCandidate.
433  // This ensures that DepChain exist for all the PNUser operand with
434  // BEUser operand. This also ensures that DepChains are independent of
435  // the positions in PNUser and BEUser.
436  std::map<Instruction *, DepChain *> DepChains;
437  CallInst *C1 = dyn_cast<CallInst>(I);
438  if ((I && I->isCommutative()) || (C1 && isCallInstCommutative(C1))) {
439  bool Found = false;
440  for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
441  Value *Op = I->getOperand(OpNo);
442  Instruction *OpInst = dyn_cast<Instruction>(Op);
443  Found = false;
444  for (int T = 0; T < NumOperands; ++T) {
445  Value *BEOp = BEUser->getOperand(T);
446  Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
447  if (!OpInst && !BEOpInst) {
448  if (Op == BEOp) {
449  Found = true;
450  break;
451  }
452  }
453 
454  if ((OpInst && !BEOpInst) || (!OpInst && BEOpInst))
455  continue;
456 
457  DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
458 
459  if (D) {
460  Found = true;
461  DepChains[OpInst] = D;
462  break;
463  }
464  }
465  if (!Found) {
466  BEUser = nullptr;
467  break;
468  }
469  }
470  } else {
471 
472  for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
473  Value *Op = I->getOperand(OpNo);
474  Value *BEOp = BEUser->getOperand(OpNo);
475 
476  Instruction *OpInst = dyn_cast<Instruction>(Op);
477  if (!OpInst) {
478  if (Op == BEOp)
479  continue;
480  // Do not allow reuse to occur when the operands may be different
481  // values.
482  BEUser = nullptr;
483  break;
484  }
485 
486  Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
487  DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
488 
489  if (D) {
490  DepChains[OpInst] = D;
491  } else {
492  BEUser = nullptr;
493  break;
494  }
495  }
496  }
497  if (BEUser) {
498  LLVM_DEBUG(dbgs() << "Found Value for reuse.\n");
499  ReuseCandidate.Inst2Replace = I;
500  ReuseCandidate.BackedgeInst = BEUser;
501  ReuseCandidate.DepChains = DepChains;
502  ReuseCandidate.Iterations = Iters;
503  return;
504  }
505  ReuseCandidate.reset();
506  }
507  }
508  }
509  ReuseCandidate.reset();
510 }
511 
512 Value *HexagonVectorLoopCarriedReuse::findValueInBlock(Value *Op,
513  BasicBlock *BB) {
514  PHINode *PN = dyn_cast<PHINode>(Op);
515  assert(PN);
516  Value *ValueInBlock = PN->getIncomingValueForBlock(BB);
517  return ValueInBlock;
518 }
519 
520 void HexagonVectorLoopCarriedReuse::reuseValue() {
521  LLVM_DEBUG(dbgs() << ReuseCandidate);
522  Instruction *Inst2Replace = ReuseCandidate.Inst2Replace;
523  Instruction *BEInst = ReuseCandidate.BackedgeInst;
524  int NumOperands = Inst2Replace->getNumOperands();
525  std::map<Instruction *, DepChain *> &DepChains = ReuseCandidate.DepChains;
526  int Iterations = ReuseCandidate.Iterations;
527  BasicBlock *LoopPH = CurLoop->getLoopPreheader();
528  assert(!DepChains.empty() && "No DepChains");
529  LLVM_DEBUG(dbgs() << "reuseValue is making the following changes\n");
530 
531  SmallVector<Instruction *, 4> InstsInPreheader;
532  for (int i = 0; i < Iterations; ++i) {
533  Instruction *InstInPreheader = Inst2Replace->clone();
535  for (int j = 0; j < NumOperands; ++j) {
536  Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(j));
537  if (!I)
538  continue;
539  // Get the DepChain corresponding to this operand.
540  DepChain &D = *DepChains[I];
541  // Get the PHI for the iteration number and find
542  // the incoming value from the Loop Preheader for
543  // that PHI.
544  Value *ValInPreheader = findValueInBlock(D[i], LoopPH);
545  InstInPreheader->setOperand(j, ValInPreheader);
546  }
547  InstsInPreheader.push_back(InstInPreheader);
548  InstInPreheader->setName(Inst2Replace->getName() + ".hexagon.vlcr");
549  InstInPreheader->insertBefore(LoopPH->getTerminator());
550  LLVM_DEBUG(dbgs() << "Added " << *InstInPreheader << " to "
551  << LoopPH->getName() << "\n");
552  }
553  BasicBlock *BB = BEInst->getParent();
554  IRBuilder<> IRB(BB);
555  IRB.SetInsertPoint(BB->getFirstNonPHI());
556  Value *BEVal = BEInst;
557  PHINode *NewPhi;
558  for (int i = Iterations-1; i >=0 ; --i) {
559  Instruction *InstInPreheader = InstsInPreheader[i];
560  NewPhi = IRB.CreatePHI(InstInPreheader->getType(), 2);
561  NewPhi->addIncoming(InstInPreheader, LoopPH);
562  NewPhi->addIncoming(BEVal, BB);
563  LLVM_DEBUG(dbgs() << "Adding " << *NewPhi << " to " << BB->getName()
564  << "\n");
565  BEVal = NewPhi;
566  }
567  // We are in LCSSA form. So, a value defined inside the Loop is used only
568  // inside the loop. So, the following is safe.
569  Inst2Replace->replaceAllUsesWith(NewPhi);
570  ReplacedInsts.insert(Inst2Replace);
571  ++HexagonNumVectorLoopCarriedReuse;
572 }
573 
574 bool HexagonVectorLoopCarriedReuse::doVLCR() {
575  assert(CurLoop->getSubLoops().empty() &&
576  "Can do VLCR on the innermost loop only");
577  assert((CurLoop->getNumBlocks() == 1) &&
578  "Can do VLCR only on single block loops");
579 
580  bool Changed = false;
581  bool Continue;
582 
583  LLVM_DEBUG(dbgs() << "Working on Loop: " << *CurLoop->getHeader() << "\n");
584  do {
585  // Reset datastructures.
586  Dependences.clear();
587  Continue = false;
588 
589  findLoopCarriedDeps();
590  findValueToReuse();
591  if (ReuseCandidate.isDefined()) {
592  reuseValue();
593  Changed = true;
594  Continue = true;
595  }
596  llvm::for_each(Dependences, std::default_delete<DepChain>());
597  } while (Continue);
598  return Changed;
599 }
600 
601 void HexagonVectorLoopCarriedReuse::findDepChainFromPHI(Instruction *I,
602  DepChain &D) {
603  PHINode *PN = dyn_cast<PHINode>(I);
604  if (!PN) {
605  D.push_back(I);
606  return;
607  } else {
608  auto NumIncomingValues = PN->getNumIncomingValues();
609  if (NumIncomingValues != 2) {
610  D.clear();
611  return;
612  }
613 
614  BasicBlock *BB = PN->getParent();
615  if (BB != CurLoop->getHeader()) {
616  D.clear();
617  return;
618  }
619 
620  Value *BEVal = PN->getIncomingValueForBlock(BB);
621  Instruction *BEInst = dyn_cast<Instruction>(BEVal);
622  // This is a single block loop with a preheader, so at least
623  // one value should come over the backedge.
624  assert(BEInst && "There should be a value over the backedge");
625 
626  Value *PreHdrVal =
627  PN->getIncomingValueForBlock(CurLoop->getLoopPreheader());
628  if(!PreHdrVal || !isa<Instruction>(PreHdrVal)) {
629  D.clear();
630  return;
631  }
632  D.push_back(PN);
633  findDepChainFromPHI(BEInst, D);
634  }
635 }
636 
637 DepChain *HexagonVectorLoopCarriedReuse::getDepChainBtwn(Instruction *I1,
638  Instruction *I2,
639  int Iters) {
640  for (auto *D : Dependences) {
641  if (D->front() == I1 && D->back() == I2 && D->iterations() == Iters)
642  return D;
643  }
644  return nullptr;
645 }
646 
647 void HexagonVectorLoopCarriedReuse::findLoopCarriedDeps() {
648  BasicBlock *BB = CurLoop->getHeader();
649  for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) {
650  auto *PN = cast<PHINode>(I);
651  if (!isa<VectorType>(PN->getType()))
652  continue;
653 
654  DepChain *D = new DepChain();
655  findDepChainFromPHI(PN, *D);
656  if (D->size() != 0)
657  Dependences.insert(D);
658  else
659  delete D;
660  }
661  LLVM_DEBUG(dbgs() << "Found " << Dependences.size() << " dependences\n");
662  LLVM_DEBUG(for (size_t i = 0; i < Dependences.size();
663  ++i) { dbgs() << *Dependences[i] << "\n"; });
664 }
665 
667  return new HexagonVectorLoopCarriedReuseLegacyPass();
668 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::createHexagonVectorLoopCarriedReuseLegacyPass
Pass * createHexagonVectorLoopCarriedReuseLegacyPass()
Definition: HexagonVectorLoopCarriedReuse.cpp:666
IntrinsicInst.h
Scalar.h
T
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Pass.h
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:52
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::IRBuilder<>
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:84
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
vectors
hexagon Hexagon specific predictive commoning for HVX vectors
Definition: HexagonVectorLoopCarriedReuse.cpp:221
HexagonVLCRIterationLim
static cl::opt< int > HexagonVLCRIterationLim("hexagon-vlcr-iteration-lim", cl::Hidden, cl::desc("Maximum distance of loop carried dependences that are handled"), cl::init(2), cl::ZeroOrMore)
LLVM_ATTRIBUTE_UNUSED
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:188
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::initializeHexagonVectorLoopCarriedReuseLegacyPassPass
void initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PassRegistry &)
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:234
Instruction.h
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:226
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
false
Definition: StackSlotColoring.cpp:142
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2851
llvm::Instruction
Definition: Instruction.h:45
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
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::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:376
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::LPPassManager
Definition: LoopPass.h:75
Utils.h
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2758
vlcr
hexagon vlcr
Definition: HexagonVectorLoopCarriedReuse.cpp:220
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::cl::ZeroOrMore
@ ZeroOrMore
Definition: CommandLine.h:120
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1432
index
splat index
Definition: README_ALTIVEC.txt:181
llvm::for_each
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1574
llvm::LoopPass
Definition: LoopPass.h:27
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:263
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2816
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
HexagonVectorLoopCarriedReuse.h
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1562
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:856
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
LoopPass.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
Compiler.h
llvm::ConstantInt::getSExtValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:148
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
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
LAM
LoopAnalysisManager LAM
Definition: PassBuilderBindings.cpp:58
j
return j(j<< 16)
llvm::LCSSAID
char & LCSSAID
Definition: LCSSA.cpp:485
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:799
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Casting.h
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
SmallVector.h
User.h
llvm::HexagonVectorLoopCarriedReusePass
Hexagon Vector Loop Carried Reuse Pass.
Definition: HexagonVectorLoopCarriedReuse.h:128
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode
Definition: Instructions.h:2666
DerivedTypes.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1487
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:267
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:412
raw_ostream.h
llvm::Instruction::isSameOperationAs
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const
This function determines if the specified instruction executes the same operation as the current one.
Definition: Instruction.cpp:528
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
SetVector.h
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1191
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr", "Hexagon-specific predictive commoning for HVX vectors", false, false) INITIALIZE_PASS_END(HexagonVectorLoopCarriedReuseLegacyPass
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38