xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp (revision 924226fba12cc9a228c73b956e1b7fa24c60b055)
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 
16 #include "HexagonVectorLoopCarriedReuse.h"
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"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/Compiler.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.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"),
59     cl::init(2), cl::ZeroOrMore);
60 
61 namespace llvm {
62 
63 void initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PassRegistry &);
64 Pass *createHexagonVectorLoopCarriedReuseLegacyPass();
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 
123   LLVM_ATTRIBUTE_UNUSED
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 
156   LLVM_ATTRIBUTE_UNUSED
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) {
169       PassRegistry *PR = PassRegistry::getPassRegistry();
170       initializeHexagonVectorLoopCarriedReuseLegacyPassPass(*PR);
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 {
178       AU.addRequiredID(LoopSimplifyID);
179       AU.addRequiredID(LCSSAID);
180       AU.addPreservedID(LCSSAID);
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 
213 char HexagonVectorLoopCarriedReuseLegacyPass::ID = 0;
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",
222                     false, false)
223 
224 PreservedAnalyses
225 HexagonVectorLoopCarriedReusePass::run(Loop &L, LoopAnalysisManager &LAM,
226                                        LoopStandardAnalysisResults &AR,
227                                        LPMUpdater &U) {
228   HexagonVectorLoopCarriedReuse Vlcr(&L);
229   if (!Vlcr.run())
230     return PreservedAnalyses::all();
231   PreservedAnalyses PA;
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 
388     SmallVector<Instruction *, 4> PNUsers;
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();
534     SmallVector<Value *, 4> Ops;
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 (const DepChain *D : Dependences) dbgs() << *D << "\n";);
663 }
664 
665 Pass *llvm::createHexagonVectorLoopCarriedReuseLegacyPass() {
666   return new HexagonVectorLoopCarriedReuseLegacyPass();
667 }
668