xref: /llvm-project/llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp (revision 8e702735090388a3231a863e343f880d0f96fecb) 
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/Value.h"
32 #include "llvm/InitializePasses.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/Casting.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Compiler.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/raw_ostream.h"
39 #include "llvm/Transforms/Scalar.h"
40 #include "llvm/Transforms/Utils.h"
41 #include <cassert>
42 #include <map>
43 #include <memory>
44 #include <set>
45 
46 using namespace llvm;
47 
48 #define DEBUG_TYPE "hexagon-vlcr"
49 
50 STATISTIC(HexagonNumVectorLoopCarriedReuse,
51           "Number of values that were reused from a previous iteration.");
52 
53 static cl::opt<int> HexagonVLCRIterationLim(
54     "hexagon-vlcr-iteration-lim", cl::Hidden,
55     cl::desc("Maximum distance of loop carried dependences that are handled"),
56     cl::init(2));
57 
58 namespace llvm {
59 
60 void initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PassRegistry &);
61 Pass *createHexagonVectorLoopCarriedReuseLegacyPass();
62 
63 } // end namespace llvm
64 
65 namespace {
66 
67   // See info about DepChain in the comments at the top of this file.
68   using ChainOfDependences = SmallVector<Instruction *, 4>;
69 
70   class DepChain {
71     ChainOfDependences Chain;
72 
73   public:
74     bool isIdentical(DepChain &Other) const {
75       if (Other.size() != size())
76         return false;
77       ChainOfDependences &OtherChain = Other.getChain();
78       for (int i = 0; i < size(); ++i) {
79         if (Chain[i] != OtherChain[i])
80           return false;
81       }
82       return true;
83     }
84 
85     ChainOfDependences &getChain() {
86       return Chain;
87     }
88 
89     int size() const {
90       return Chain.size();
91     }
92 
93     void clear() {
94       Chain.clear();
95     }
96 
97     void push_back(Instruction *I) {
98       Chain.push_back(I);
99     }
100 
101     int iterations() const {
102       return size() - 1;
103     }
104 
105     Instruction *front() const {
106       return Chain.front();
107     }
108 
109     Instruction *back() const {
110       return Chain.back();
111     }
112 
113     Instruction *&operator[](const int index) {
114       return Chain[index];
115     }
116 
117    friend raw_ostream &operator<< (raw_ostream &OS, const DepChain &D);
118   };
119 
120   LLVM_ATTRIBUTE_UNUSED
121   raw_ostream &operator<<(raw_ostream &OS, const DepChain &D) {
122     const ChainOfDependences &CD = D.Chain;
123     int ChainSize = CD.size();
124     OS << "**DepChain Start::**\n";
125     for (int i = 0; i < ChainSize -1; ++i) {
126       OS << *(CD[i]) << " -->\n";
127     }
128     OS << *CD[ChainSize-1] << "\n";
129     return OS;
130   }
131 
132   struct ReuseValue {
133     Instruction *Inst2Replace = nullptr;
134 
135     // In the new PHI node that we'll construct this is the value that'll be
136     // used over the backedge. This is the value that gets reused from a
137     // previous iteration.
138     Instruction *BackedgeInst = nullptr;
139     std::map<Instruction *, DepChain *> DepChains;
140     int Iterations = -1;
141 
142     ReuseValue() = default;
143 
144     void reset() {
145       Inst2Replace = nullptr;
146       BackedgeInst = nullptr;
147       DepChains.clear();
148       Iterations = -1;
149     }
150     bool isDefined() { return Inst2Replace != nullptr; }
151   };
152 
153   LLVM_ATTRIBUTE_UNUSED
154   raw_ostream &operator<<(raw_ostream &OS, const ReuseValue &RU) {
155     OS << "** ReuseValue ***\n";
156     OS << "Instruction to Replace: " << *(RU.Inst2Replace) << "\n";
157     OS << "Backedge Instruction: " << *(RU.BackedgeInst) << "\n";
158     return OS;
159   }
160 
161   class HexagonVectorLoopCarriedReuseLegacyPass : public LoopPass {
162   public:
163     static char ID;
164 
165     explicit HexagonVectorLoopCarriedReuseLegacyPass() : LoopPass(ID) {
166       PassRegistry *PR = PassRegistry::getPassRegistry();
167       initializeHexagonVectorLoopCarriedReuseLegacyPassPass(*PR);
168     }
169 
170     StringRef getPassName() const override {
171       return "Hexagon-specific loop carried reuse for HVX vectors";
172     }
173 
174     void getAnalysisUsage(AnalysisUsage &AU) const override {
175       AU.addRequiredID(LoopSimplifyID);
176       AU.addRequiredID(LCSSAID);
177       AU.addPreservedID(LCSSAID);
178       AU.setPreservesCFG();
179     }
180 
181     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
182   };
183 
184   class HexagonVectorLoopCarriedReuse {
185   public:
186     HexagonVectorLoopCarriedReuse(Loop *L) : CurLoop(L){};
187 
188     bool run();
189 
190   private:
191     SetVector<DepChain *> Dependences;
192     std::set<Instruction *> ReplacedInsts;
193     Loop *CurLoop;
194     ReuseValue ReuseCandidate;
195 
196     bool doVLCR();
197     void findLoopCarriedDeps();
198     void findValueToReuse();
199     void findDepChainFromPHI(Instruction *I, DepChain &D);
200     void reuseValue();
201     Value *findValueInBlock(Value *Op, BasicBlock *BB);
202     DepChain *getDepChainBtwn(Instruction *I1, Instruction *I2, int Iters);
203     bool isEquivalentOperation(Instruction *I1, Instruction *I2);
204     bool canReplace(Instruction *I);
205     bool isCallInstCommutative(CallInst *C);
206   };
207 
208 } // end anonymous namespace
209 
210 char HexagonVectorLoopCarriedReuseLegacyPass::ID = 0;
211 
212 INITIALIZE_PASS_BEGIN(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
213                       "Hexagon-specific predictive commoning for HVX vectors",
214                       false, false)
215 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
216 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
217 INITIALIZE_PASS_END(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
218                     "Hexagon-specific predictive commoning for HVX vectors",
219                     false, false)
220 
221 PreservedAnalyses
222 HexagonVectorLoopCarriedReusePass::run(Loop &L, LoopAnalysisManager &LAM,
223                                        LoopStandardAnalysisResults &AR,
224                                        LPMUpdater &U) {
225   HexagonVectorLoopCarriedReuse Vlcr(&L);
226   if (!Vlcr.run())
227     return PreservedAnalyses::all();
228   PreservedAnalyses PA;
229   PA.preserveSet<CFGAnalyses>();
230   return PA;
231 }
232 
233 bool HexagonVectorLoopCarriedReuseLegacyPass::runOnLoop(Loop *L,
234                                                         LPPassManager &LPM) {
235   if (skipLoop(L))
236     return false;
237   HexagonVectorLoopCarriedReuse Vlcr(L);
238   return Vlcr.run();
239 }
240 
241 bool HexagonVectorLoopCarriedReuse::run() {
242   if (!CurLoop->getLoopPreheader())
243     return false;
244 
245   // Work only on innermost loops.
246   if (!CurLoop->getSubLoops().empty())
247     return false;
248 
249   // Work only on single basic blocks loops.
250   if (CurLoop->getNumBlocks() != 1)
251     return false;
252 
253   return doVLCR();
254 }
255 
256 bool HexagonVectorLoopCarriedReuse::isCallInstCommutative(CallInst *C) {
257   switch (C->getCalledFunction()->getIntrinsicID()) {
258     case Intrinsic::hexagon_V6_vaddb:
259     case Intrinsic::hexagon_V6_vaddb_128B:
260     case Intrinsic::hexagon_V6_vaddh:
261     case Intrinsic::hexagon_V6_vaddh_128B:
262     case Intrinsic::hexagon_V6_vaddw:
263     case Intrinsic::hexagon_V6_vaddw_128B:
264     case Intrinsic::hexagon_V6_vaddubh:
265     case Intrinsic::hexagon_V6_vaddubh_128B:
266     case Intrinsic::hexagon_V6_vadduhw:
267     case Intrinsic::hexagon_V6_vadduhw_128B:
268     case Intrinsic::hexagon_V6_vaddhw:
269     case Intrinsic::hexagon_V6_vaddhw_128B:
270     case Intrinsic::hexagon_V6_vmaxb:
271     case Intrinsic::hexagon_V6_vmaxb_128B:
272     case Intrinsic::hexagon_V6_vmaxh:
273     case Intrinsic::hexagon_V6_vmaxh_128B:
274     case Intrinsic::hexagon_V6_vmaxw:
275     case Intrinsic::hexagon_V6_vmaxw_128B:
276     case Intrinsic::hexagon_V6_vmaxub:
277     case Intrinsic::hexagon_V6_vmaxub_128B:
278     case Intrinsic::hexagon_V6_vmaxuh:
279     case Intrinsic::hexagon_V6_vmaxuh_128B:
280     case Intrinsic::hexagon_V6_vminub:
281     case Intrinsic::hexagon_V6_vminub_128B:
282     case Intrinsic::hexagon_V6_vminuh:
283     case Intrinsic::hexagon_V6_vminuh_128B:
284     case Intrinsic::hexagon_V6_vminb:
285     case Intrinsic::hexagon_V6_vminb_128B:
286     case Intrinsic::hexagon_V6_vminh:
287     case Intrinsic::hexagon_V6_vminh_128B:
288     case Intrinsic::hexagon_V6_vminw:
289     case Intrinsic::hexagon_V6_vminw_128B:
290     case Intrinsic::hexagon_V6_vmpyub:
291     case Intrinsic::hexagon_V6_vmpyub_128B:
292     case Intrinsic::hexagon_V6_vmpyuh:
293     case Intrinsic::hexagon_V6_vmpyuh_128B:
294     case Intrinsic::hexagon_V6_vavgub:
295     case Intrinsic::hexagon_V6_vavgub_128B:
296     case Intrinsic::hexagon_V6_vavgh:
297     case Intrinsic::hexagon_V6_vavgh_128B:
298     case Intrinsic::hexagon_V6_vavguh:
299     case Intrinsic::hexagon_V6_vavguh_128B:
300     case Intrinsic::hexagon_V6_vavgw:
301     case Intrinsic::hexagon_V6_vavgw_128B:
302     case Intrinsic::hexagon_V6_vavgb:
303     case Intrinsic::hexagon_V6_vavgb_128B:
304     case Intrinsic::hexagon_V6_vavguw:
305     case Intrinsic::hexagon_V6_vavguw_128B:
306     case Intrinsic::hexagon_V6_vabsdiffh:
307     case Intrinsic::hexagon_V6_vabsdiffh_128B:
308     case Intrinsic::hexagon_V6_vabsdiffub:
309     case Intrinsic::hexagon_V6_vabsdiffub_128B:
310     case Intrinsic::hexagon_V6_vabsdiffuh:
311     case Intrinsic::hexagon_V6_vabsdiffuh_128B:
312     case Intrinsic::hexagon_V6_vabsdiffw:
313     case Intrinsic::hexagon_V6_vabsdiffw_128B:
314       return true;
315     default:
316       return false;
317   }
318 }
319 
320 bool HexagonVectorLoopCarriedReuse::isEquivalentOperation(Instruction *I1,
321                                                           Instruction *I2) {
322   if (!I1->isSameOperationAs(I2))
323     return false;
324   // This check is in place specifically for intrinsics. isSameOperationAs will
325   // return two for any two hexagon intrinsics because they are essentially the
326   // same instruciton (CallInst). We need to scratch the surface to see if they
327   // are calls to the same function.
328   if (CallInst *C1 = dyn_cast<CallInst>(I1)) {
329     if (CallInst *C2 = dyn_cast<CallInst>(I2)) {
330       if (C1->getCalledFunction() != C2->getCalledFunction())
331         return false;
332     }
333   }
334 
335   // If both the Instructions are of Vector Type and any of the element
336   // is integer constant, check their values too for equivalence.
337   if (I1->getType()->isVectorTy() && I2->getType()->isVectorTy()) {
338     unsigned NumOperands = I1->getNumOperands();
339     for (unsigned i = 0; i < NumOperands; ++i) {
340       ConstantInt *C1 = dyn_cast<ConstantInt>(I1->getOperand(i));
341       ConstantInt *C2 = dyn_cast<ConstantInt>(I2->getOperand(i));
342       if(!C1) continue;
343       assert(C2);
344       if (C1->getSExtValue() != C2->getSExtValue())
345         return false;
346     }
347   }
348 
349   return true;
350 }
351 
352 bool HexagonVectorLoopCarriedReuse::canReplace(Instruction *I) {
353   const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
354   if (!II)
355     return true;
356 
357   switch (II->getIntrinsicID()) {
358   case Intrinsic::hexagon_V6_hi:
359   case Intrinsic::hexagon_V6_lo:
360   case Intrinsic::hexagon_V6_hi_128B:
361   case Intrinsic::hexagon_V6_lo_128B:
362     LLVM_DEBUG(dbgs() << "Not considering for reuse: " << *II << "\n");
363     return false;
364   default:
365     return true;
366   }
367 }
368 void HexagonVectorLoopCarriedReuse::findValueToReuse() {
369   for (auto *D : Dependences) {
370     LLVM_DEBUG(dbgs() << "Processing dependence " << *(D->front()) << "\n");
371     if (D->iterations() > HexagonVLCRIterationLim) {
372       LLVM_DEBUG(
373           dbgs()
374           << ".. Skipping because number of iterations > than the limit\n");
375       continue;
376     }
377 
378     PHINode *PN = cast<PHINode>(D->front());
379     Instruction *BEInst = D->back();
380     int Iters = D->iterations();
381     BasicBlock *BB = PN->getParent();
382     LLVM_DEBUG(dbgs() << "Checking if any uses of " << *PN
383                       << " can be reused\n");
384 
385     SmallVector<Instruction *, 4> PNUsers;
386     for (Use &U : PN->uses()) {
387       Instruction *User = cast<Instruction>(U.getUser());
388 
389       if (User->getParent() != BB)
390         continue;
391       if (ReplacedInsts.count(User)) {
392         LLVM_DEBUG(dbgs() << *User
393                           << " has already been replaced. Skipping...\n");
394         continue;
395       }
396       if (isa<PHINode>(User))
397         continue;
398       if (User->mayHaveSideEffects())
399         continue;
400       if (!canReplace(User))
401         continue;
402 
403       PNUsers.push_back(User);
404     }
405     LLVM_DEBUG(dbgs() << PNUsers.size() << " use(s) of the PHI in the block\n");
406 
407     // For each interesting use I of PN, find an Instruction BEUser that
408     // performs the same operation as I on BEInst and whose other operands,
409     // if any, can also be rematerialized in OtherBB. We stop when we find the
410     // first such Instruction BEUser. This is because once BEUser is
411     // rematerialized in OtherBB, we may find more such "fixup" opportunities
412     // in this block. So, we'll start over again.
413     for (Instruction *I : PNUsers) {
414       for (Use &U : BEInst->uses()) {
415         Instruction *BEUser = cast<Instruction>(U.getUser());
416 
417         if (BEUser->getParent() != BB)
418           continue;
419         if (!isEquivalentOperation(I, BEUser))
420           continue;
421 
422         int NumOperands = I->getNumOperands();
423 
424         // Take operands of each PNUser one by one and try to find DepChain
425         // with every operand of the BEUser. If any of the operands of BEUser
426         // has DepChain with current operand of the PNUser, break the matcher
427         // loop. Keep doing this for Every PNUser operand. If PNUser operand
428         // does not have DepChain with any of the BEUser operand, break the
429         // outer matcher loop, mark the BEUser as null and reset the ReuseCandidate.
430         // This ensures that DepChain exist for all the PNUser operand with
431         // BEUser operand. This also ensures that DepChains are independent of
432         // the positions in PNUser and BEUser.
433         std::map<Instruction *, DepChain *> DepChains;
434         CallInst *C1 = dyn_cast<CallInst>(I);
435         if ((I && I->isCommutative()) || (C1 && isCallInstCommutative(C1))) {
436           bool Found = false;
437           for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
438             Value *Op = I->getOperand(OpNo);
439             Instruction *OpInst = dyn_cast<Instruction>(Op);
440             Found = false;
441             for (int T = 0; T < NumOperands; ++T) {
442               Value *BEOp = BEUser->getOperand(T);
443               Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
444               if (!OpInst && !BEOpInst) {
445                 if (Op == BEOp) {
446                   Found = true;
447                   break;
448                 }
449               }
450 
451               if ((OpInst && !BEOpInst) || (!OpInst && BEOpInst))
452                 continue;
453 
454               DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
455 
456               if (D) {
457                 Found = true;
458                 DepChains[OpInst] = D;
459                 break;
460               }
461             }
462             if (!Found) {
463               BEUser = nullptr;
464               break;
465             }
466           }
467         } else {
468 
469           for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
470             Value *Op = I->getOperand(OpNo);
471             Value *BEOp = BEUser->getOperand(OpNo);
472 
473             Instruction *OpInst = dyn_cast<Instruction>(Op);
474             if (!OpInst) {
475               if (Op == BEOp)
476                 continue;
477               // Do not allow reuse to occur when the operands may be different
478               // values.
479               BEUser = nullptr;
480               break;
481             }
482 
483             Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
484             DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
485 
486             if (D) {
487               DepChains[OpInst] = D;
488             } else {
489               BEUser = nullptr;
490               break;
491             }
492           }
493         }
494         if (BEUser) {
495           LLVM_DEBUG(dbgs() << "Found Value for reuse.\n");
496           ReuseCandidate.Inst2Replace = I;
497           ReuseCandidate.BackedgeInst = BEUser;
498           ReuseCandidate.DepChains = DepChains;
499           ReuseCandidate.Iterations = Iters;
500           return;
501         }
502         ReuseCandidate.reset();
503       }
504     }
505   }
506   ReuseCandidate.reset();
507 }
508 
509 Value *HexagonVectorLoopCarriedReuse::findValueInBlock(Value *Op,
510                                                        BasicBlock *BB) {
511   PHINode *PN = dyn_cast<PHINode>(Op);
512   assert(PN);
513   Value *ValueInBlock = PN->getIncomingValueForBlock(BB);
514   return ValueInBlock;
515 }
516 
517 void HexagonVectorLoopCarriedReuse::reuseValue() {
518   LLVM_DEBUG(dbgs() << ReuseCandidate);
519   Instruction *Inst2Replace = ReuseCandidate.Inst2Replace;
520   Instruction *BEInst = ReuseCandidate.BackedgeInst;
521   int NumOperands = Inst2Replace->getNumOperands();
522   std::map<Instruction *, DepChain *> &DepChains = ReuseCandidate.DepChains;
523   int Iterations = ReuseCandidate.Iterations;
524   BasicBlock *LoopPH = CurLoop->getLoopPreheader();
525   assert(!DepChains.empty() && "No DepChains");
526   LLVM_DEBUG(dbgs() << "reuseValue is making the following changes\n");
527 
528   SmallVector<Instruction *, 4> InstsInPreheader;
529   for (int i = 0; i < Iterations; ++i) {
530     Instruction *InstInPreheader = Inst2Replace->clone();
531     SmallVector<Value *, 4> Ops;
532     for (int j = 0; j < NumOperands; ++j) {
533       Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(j));
534       if (!I)
535         continue;
536       // Get the DepChain corresponding to this operand.
537       DepChain &D = *DepChains[I];
538       // Get the PHI for the iteration number and find
539       // the incoming value from the Loop Preheader for
540       // that PHI.
541       Value *ValInPreheader = findValueInBlock(D[i], LoopPH);
542       InstInPreheader->setOperand(j, ValInPreheader);
543     }
544     InstsInPreheader.push_back(InstInPreheader);
545     InstInPreheader->setName(Inst2Replace->getName() + ".hexagon.vlcr");
546     InstInPreheader->insertBefore(LoopPH->getTerminator()->getIterator());
547     LLVM_DEBUG(dbgs() << "Added " << *InstInPreheader << " to "
548                       << LoopPH->getName() << "\n");
549   }
550   BasicBlock *BB = BEInst->getParent();
551   IRBuilder<> IRB(BB);
552   IRB.SetInsertPoint(BB, BB->getFirstNonPHIIt());
553   Value *BEVal = BEInst;
554   PHINode *NewPhi;
555   for (int i = Iterations-1; i >=0 ; --i) {
556     Instruction *InstInPreheader = InstsInPreheader[i];
557     NewPhi = IRB.CreatePHI(InstInPreheader->getType(), 2);
558     NewPhi->addIncoming(InstInPreheader, LoopPH);
559     NewPhi->addIncoming(BEVal, BB);
560     LLVM_DEBUG(dbgs() << "Adding " << *NewPhi << " to " << BB->getName()
561                       << "\n");
562     BEVal = NewPhi;
563   }
564   // We are in LCSSA form. So, a value defined inside the Loop is used only
565   // inside the loop. So, the following is safe.
566   Inst2Replace->replaceAllUsesWith(NewPhi);
567   ReplacedInsts.insert(Inst2Replace);
568   ++HexagonNumVectorLoopCarriedReuse;
569 }
570 
571 bool HexagonVectorLoopCarriedReuse::doVLCR() {
572   assert(CurLoop->getSubLoops().empty() &&
573          "Can do VLCR on the innermost loop only");
574   assert((CurLoop->getNumBlocks() == 1) &&
575          "Can do VLCR only on single block loops");
576 
577   bool Changed = false;
578   bool Continue;
579 
580   LLVM_DEBUG(dbgs() << "Working on Loop: " << *CurLoop->getHeader() << "\n");
581   do {
582     // Reset datastructures.
583     Dependences.clear();
584     Continue = false;
585 
586     findLoopCarriedDeps();
587     findValueToReuse();
588     if (ReuseCandidate.isDefined()) {
589       reuseValue();
590       Changed = true;
591       Continue = true;
592     }
593     llvm::for_each(Dependences, std::default_delete<DepChain>());
594   } while (Continue);
595   return Changed;
596 }
597 
598 void HexagonVectorLoopCarriedReuse::findDepChainFromPHI(Instruction *I,
599                                                         DepChain &D) {
600   PHINode *PN = dyn_cast<PHINode>(I);
601   if (!PN) {
602     D.push_back(I);
603     return;
604   } else {
605     auto NumIncomingValues = PN->getNumIncomingValues();
606     if (NumIncomingValues != 2) {
607       D.clear();
608       return;
609     }
610 
611     BasicBlock *BB = PN->getParent();
612     if (BB != CurLoop->getHeader()) {
613       D.clear();
614       return;
615     }
616 
617     Value *BEVal = PN->getIncomingValueForBlock(BB);
618     Instruction *BEInst = dyn_cast<Instruction>(BEVal);
619     // This is a single block loop with a preheader, so at least
620     // one value should come over the backedge.
621     assert(BEInst && "There should be a value over the backedge");
622 
623     Value *PreHdrVal =
624       PN->getIncomingValueForBlock(CurLoop->getLoopPreheader());
625     if(!PreHdrVal || !isa<Instruction>(PreHdrVal)) {
626       D.clear();
627       return;
628     }
629     D.push_back(PN);
630     findDepChainFromPHI(BEInst, D);
631   }
632 }
633 
634 DepChain *HexagonVectorLoopCarriedReuse::getDepChainBtwn(Instruction *I1,
635                                                          Instruction *I2,
636                                                          int Iters) {
637   for (auto *D : Dependences) {
638     if (D->front() == I1 && D->back() == I2 && D->iterations() == Iters)
639       return D;
640   }
641   return nullptr;
642 }
643 
644 void HexagonVectorLoopCarriedReuse::findLoopCarriedDeps() {
645   BasicBlock *BB = CurLoop->getHeader();
646   for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) {
647     auto *PN = cast<PHINode>(I);
648     if (!isa<VectorType>(PN->getType()))
649       continue;
650 
651     DepChain *D = new DepChain();
652     findDepChainFromPHI(PN, *D);
653     if (D->size() != 0)
654       Dependences.insert(D);
655     else
656       delete D;
657   }
658   LLVM_DEBUG(dbgs() << "Found " << Dependences.size() << " dependences\n");
659   LLVM_DEBUG(for (const DepChain *D : Dependences) dbgs() << *D << "\n";);
660 }
661 
662 Pass *llvm::createHexagonVectorLoopCarriedReuseLegacyPass() {
663   return new HexagonVectorLoopCarriedReuseLegacyPass();
664 }
665