xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp (revision 994297b01b98816bea1abf45ae4bac1bc69ee7a0) 
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 (auto UI = PN->use_begin(), E = PN->use_end(); UI != E; ++UI) {
390       Use &U = *UI;
391       Instruction *User = cast<Instruction>(U.getUser());
392 
393       if (User->getParent() != BB)
394         continue;
395       if (ReplacedInsts.count(User)) {
396         LLVM_DEBUG(dbgs() << *User
397                           << " has already been replaced. Skipping...\n");
398         continue;
399       }
400       if (isa<PHINode>(User))
401         continue;
402       if (User->mayHaveSideEffects())
403         continue;
404       if (!canReplace(User))
405         continue;
406 
407       PNUsers.push_back(User);
408     }
409     LLVM_DEBUG(dbgs() << PNUsers.size() << " use(s) of the PHI in the block\n");
410 
411     // For each interesting use I of PN, find an Instruction BEUser that
412     // performs the same operation as I on BEInst and whose other operands,
413     // if any, can also be rematerialized in OtherBB. We stop when we find the
414     // first such Instruction BEUser. This is because once BEUser is
415     // rematerialized in OtherBB, we may find more such "fixup" opportunities
416     // in this block. So, we'll start over again.
417     for (Instruction *I : PNUsers) {
418       for (auto UI = BEInst->use_begin(), E = BEInst->use_end(); UI != E;
419            ++UI) {
420         Use &U = *UI;
421         Instruction *BEUser = cast<Instruction>(U.getUser());
422 
423         if (BEUser->getParent() != BB)
424           continue;
425         if (!isEquivalentOperation(I, BEUser))
426           continue;
427 
428         int NumOperands = I->getNumOperands();
429 
430         // Take operands of each PNUser one by one and try to find DepChain
431         // with every operand of the BEUser. If any of the operands of BEUser
432         // has DepChain with current operand of the PNUser, break the matcher
433         // loop. Keep doing this for Every PNUser operand. If PNUser operand
434         // does not have DepChain with any of the BEUser operand, break the
435         // outer matcher loop, mark the BEUser as null and reset the ReuseCandidate.
436         // This ensures that DepChain exist for all the PNUser operand with
437         // BEUser operand. This also ensures that DepChains are independent of
438         // the positions in PNUser and BEUser.
439         std::map<Instruction *, DepChain *> DepChains;
440         CallInst *C1 = dyn_cast<CallInst>(I);
441         if ((I && I->isCommutative()) || (C1 && isCallInstCommutative(C1))) {
442           bool Found = false;
443           for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
444             Value *Op = I->getOperand(OpNo);
445             Instruction *OpInst = dyn_cast<Instruction>(Op);
446             Found = false;
447             for (int T = 0; T < NumOperands; ++T) {
448               Value *BEOp = BEUser->getOperand(T);
449               Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
450               if (!OpInst && !BEOpInst) {
451                 if (Op == BEOp) {
452                   Found = true;
453                   break;
454                 }
455               }
456 
457               if ((OpInst && !BEOpInst) || (!OpInst && BEOpInst))
458                 continue;
459 
460               DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
461 
462               if (D) {
463                 Found = true;
464                 DepChains[OpInst] = D;
465                 break;
466               }
467             }
468             if (!Found) {
469               BEUser = nullptr;
470               break;
471             }
472           }
473         } else {
474 
475           for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
476             Value *Op = I->getOperand(OpNo);
477             Value *BEOp = BEUser->getOperand(OpNo);
478 
479             Instruction *OpInst = dyn_cast<Instruction>(Op);
480             if (!OpInst) {
481               if (Op == BEOp)
482                 continue;
483               // Do not allow reuse to occur when the operands may be different
484               // values.
485               BEUser = nullptr;
486               break;
487             }
488 
489             Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
490             DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
491 
492             if (D) {
493               DepChains[OpInst] = D;
494             } else {
495               BEUser = nullptr;
496               break;
497             }
498           }
499         }
500         if (BEUser) {
501           LLVM_DEBUG(dbgs() << "Found Value for reuse.\n");
502           ReuseCandidate.Inst2Replace = I;
503           ReuseCandidate.BackedgeInst = BEUser;
504           ReuseCandidate.DepChains = DepChains;
505           ReuseCandidate.Iterations = Iters;
506           return;
507         }
508         ReuseCandidate.reset();
509       }
510     }
511   }
512   ReuseCandidate.reset();
513 }
514 
515 Value *HexagonVectorLoopCarriedReuse::findValueInBlock(Value *Op,
516                                                        BasicBlock *BB) {
517   PHINode *PN = dyn_cast<PHINode>(Op);
518   assert(PN);
519   Value *ValueInBlock = PN->getIncomingValueForBlock(BB);
520   return ValueInBlock;
521 }
522 
523 void HexagonVectorLoopCarriedReuse::reuseValue() {
524   LLVM_DEBUG(dbgs() << ReuseCandidate);
525   Instruction *Inst2Replace = ReuseCandidate.Inst2Replace;
526   Instruction *BEInst = ReuseCandidate.BackedgeInst;
527   int NumOperands = Inst2Replace->getNumOperands();
528   std::map<Instruction *, DepChain *> &DepChains = ReuseCandidate.DepChains;
529   int Iterations = ReuseCandidate.Iterations;
530   BasicBlock *LoopPH = CurLoop->getLoopPreheader();
531   assert(!DepChains.empty() && "No DepChains");
532   LLVM_DEBUG(dbgs() << "reuseValue is making the following changes\n");
533 
534   SmallVector<Instruction *, 4> InstsInPreheader;
535   for (int i = 0; i < Iterations; ++i) {
536     Instruction *InstInPreheader = Inst2Replace->clone();
537     SmallVector<Value *, 4> Ops;
538     for (int j = 0; j < NumOperands; ++j) {
539       Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(j));
540       if (!I)
541         continue;
542       // Get the DepChain corresponding to this operand.
543       DepChain &D = *DepChains[I];
544       // Get the PHI for the iteration number and find
545       // the incoming value from the Loop Preheader for
546       // that PHI.
547       Value *ValInPreheader = findValueInBlock(D[i], LoopPH);
548       InstInPreheader->setOperand(j, ValInPreheader);
549     }
550     InstsInPreheader.push_back(InstInPreheader);
551     InstInPreheader->setName(Inst2Replace->getName() + ".hexagon.vlcr");
552     InstInPreheader->insertBefore(LoopPH->getTerminator());
553     LLVM_DEBUG(dbgs() << "Added " << *InstInPreheader << " to "
554                       << LoopPH->getName() << "\n");
555   }
556   BasicBlock *BB = BEInst->getParent();
557   IRBuilder<> IRB(BB);
558   IRB.SetInsertPoint(BB->getFirstNonPHI());
559   Value *BEVal = BEInst;
560   PHINode *NewPhi;
561   for (int i = Iterations-1; i >=0 ; --i) {
562     Instruction *InstInPreheader = InstsInPreheader[i];
563     NewPhi = IRB.CreatePHI(InstInPreheader->getType(), 2);
564     NewPhi->addIncoming(InstInPreheader, LoopPH);
565     NewPhi->addIncoming(BEVal, BB);
566     LLVM_DEBUG(dbgs() << "Adding " << *NewPhi << " to " << BB->getName()
567                       << "\n");
568     BEVal = NewPhi;
569   }
570   // We are in LCSSA form. So, a value defined inside the Loop is used only
571   // inside the loop. So, the following is safe.
572   Inst2Replace->replaceAllUsesWith(NewPhi);
573   ReplacedInsts.insert(Inst2Replace);
574   ++HexagonNumVectorLoopCarriedReuse;
575 }
576 
577 bool HexagonVectorLoopCarriedReuse::doVLCR() {
578   assert(CurLoop->getSubLoops().empty() &&
579          "Can do VLCR on the innermost loop only");
580   assert((CurLoop->getNumBlocks() == 1) &&
581          "Can do VLCR only on single block loops");
582 
583   bool Changed = false;
584   bool Continue;
585 
586   LLVM_DEBUG(dbgs() << "Working on Loop: " << *CurLoop->getHeader() << "\n");
587   do {
588     // Reset datastructures.
589     Dependences.clear();
590     Continue = false;
591 
592     findLoopCarriedDeps();
593     findValueToReuse();
594     if (ReuseCandidate.isDefined()) {
595       reuseValue();
596       Changed = true;
597       Continue = true;
598     }
599     llvm::for_each(Dependences, std::default_delete<DepChain>());
600   } while (Continue);
601   return Changed;
602 }
603 
604 void HexagonVectorLoopCarriedReuse::findDepChainFromPHI(Instruction *I,
605                                                         DepChain &D) {
606   PHINode *PN = dyn_cast<PHINode>(I);
607   if (!PN) {
608     D.push_back(I);
609     return;
610   } else {
611     auto NumIncomingValues = PN->getNumIncomingValues();
612     if (NumIncomingValues != 2) {
613       D.clear();
614       return;
615     }
616 
617     BasicBlock *BB = PN->getParent();
618     if (BB != CurLoop->getHeader()) {
619       D.clear();
620       return;
621     }
622 
623     Value *BEVal = PN->getIncomingValueForBlock(BB);
624     Instruction *BEInst = dyn_cast<Instruction>(BEVal);
625     // This is a single block loop with a preheader, so at least
626     // one value should come over the backedge.
627     assert(BEInst && "There should be a value over the backedge");
628 
629     Value *PreHdrVal =
630       PN->getIncomingValueForBlock(CurLoop->getLoopPreheader());
631     if(!PreHdrVal || !isa<Instruction>(PreHdrVal)) {
632       D.clear();
633       return;
634     }
635     D.push_back(PN);
636     findDepChainFromPHI(BEInst, D);
637   }
638 }
639 
640 DepChain *HexagonVectorLoopCarriedReuse::getDepChainBtwn(Instruction *I1,
641                                                          Instruction *I2,
642                                                          int Iters) {
643   for (auto *D : Dependences) {
644     if (D->front() == I1 && D->back() == I2 && D->iterations() == Iters)
645       return D;
646   }
647   return nullptr;
648 }
649 
650 void HexagonVectorLoopCarriedReuse::findLoopCarriedDeps() {
651   BasicBlock *BB = CurLoop->getHeader();
652   for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) {
653     auto *PN = cast<PHINode>(I);
654     if (!isa<VectorType>(PN->getType()))
655       continue;
656 
657     DepChain *D = new DepChain();
658     findDepChainFromPHI(PN, *D);
659     if (D->size() != 0)
660       Dependences.insert(D);
661     else
662       delete D;
663   }
664   LLVM_DEBUG(dbgs() << "Found " << Dependences.size() << " dependences\n");
665   LLVM_DEBUG(for (size_t i = 0; i < Dependences.size();
666                   ++i) { dbgs() << *Dependences[i] << "\n"; });
667 }
668 
669 Pass *llvm::createHexagonVectorLoopCarriedReuseLegacyPass() {
670   return new HexagonVectorLoopCarriedReuseLegacyPass();
671 }
672