1 //===- HexagonVectorLoopCarriedReuse.cpp ----------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass removes the computation of provably redundant expressions that have
11 // been computed earlier in a previous iteration. It relies on the use of PHIs
12 // to identify loop carried dependences. This is scalar replacement for vector
13 // types.
14 //
15 //-----------------------------------------------------------------------------
16 // Motivation: Consider the case where we have the following loop structure.
17 //
18 // Loop:
19 // t0 = a[i];
20 // t1 = f(t0);
21 // t2 = g(t1);
22 // ...
23 // t3 = a[i+1];
24 // t4 = f(t3);
25 // t5 = g(t4);
26 // t6 = op(t2, t5)
27 // cond_branch <Loop>
28 //
29 // This can be converted to
30 // t00 = a[0];
31 // t10 = f(t00);
32 // t20 = g(t10);
33 // Loop:
34 // t2 = t20;
35 // t3 = a[i+1];
36 // t4 = f(t3);
37 // t5 = g(t4);
38 // t6 = op(t2, t5)
39 // t20 = t5
40 // cond_branch <Loop>
41 //
42 // SROA does a good job of reusing a[i+1] as a[i] in the next iteration.
43 // Such a loop comes to this pass in the following form.
44 //
45 // LoopPreheader:
46 // X0 = a[0];
47 // Loop:
48 // X2 = PHI<(X0, LoopPreheader), (X1, Loop)>
49 // t1 = f(X2) <-- I1
50 // t2 = g(t1)
51 // ...
52 // X1 = a[i+1]
53 // t4 = f(X1) <-- I2
54 // t5 = g(t4)
55 // t6 = op(t2, t5)
56 // cond_branch <Loop>
57 //
58 // In this pass, we look for PHIs such as X2 whose incoming values come only
59 // from the Loop Preheader and over the backedge and additionaly, both these
60 // values are the results of the same operation in terms of opcode. We call such
61 // a PHI node a dependence chain or DepChain. In this case, the dependence of X2
62 // over X1 is carried over only one iteration and so the DepChain is only one
63 // PHI node long.
64 //
65 // Then, we traverse the uses of the PHI (X2) and the uses of the value of the
66 // PHI coming over the backedge (X1). We stop at the first pair of such users
67 // I1 (of X2) and I2 (of X1) that meet the following conditions.
68 // 1. I1 and I2 are the same operation, but with different operands.
69 // 2. X2 and X1 are used at the same operand number in the two instructions.
70 // 3. All other operands Op1 of I1 and Op2 of I2 are also such that there is a
71 // a DepChain from Op1 to Op2 of the same length as that between X2 and X1.
72 //
73 // We then make the following transformation
74 // LoopPreheader:
75 // X0 = a[0];
76 // Y0 = f(X0);
77 // Loop:
78 // X2 = PHI<(X0, LoopPreheader), (X1, Loop)>
79 // Y2 = PHI<(Y0, LoopPreheader), (t4, Loop)>
80 // t1 = f(X2) <-- Will be removed by DCE.
81 // t2 = g(Y2)
82 // ...
83 // X1 = a[i+1]
84 // t4 = f(X1)
85 // t5 = g(t4)
86 // t6 = op(t2, t5)
87 // cond_branch <Loop>
88 //
89 // We proceed until we cannot find any more such instructions I1 and I2.
90 //
91 // --- DepChains & Loop carried dependences ---
92 // Consider a single basic block loop such as
93 //
94 // LoopPreheader:
95 // X0 = ...
96 // Y0 = ...
97 // Loop:
98 // X2 = PHI<(X0, LoopPreheader), (X1, Loop)>
99 // Y2 = PHI<(Y0, LoopPreheader), (X2, Loop)>
100 // ...
101 // X1 = ...
102 // ...
103 // cond_branch <Loop>
104 //
105 // Then there is a dependence between X2 and X1 that goes back one iteration,
106 // i.e. X1 is used as X2 in the very next iteration. We represent this as a
107 // DepChain from X2 to X1 (X2->X1).
108 // Similarly, there is a dependence between Y2 and X1 that goes back two
109 // iterations. X1 is used as Y2 two iterations after it is computed. This is
110 // represented by a DepChain as (Y2->X2->X1).
111 //
112 // A DepChain has the following properties.
113 // 1. Num of edges in DepChain = Number of Instructions in DepChain = Number of
114 // iterations of carried dependence + 1.
115 // 2. All instructions in the DepChain except the last are PHIs.
116 //
117 //===----------------------------------------------------------------------===//
118
119 #include "llvm/ADT/SetVector.h"
120 #include "llvm/ADT/SmallVector.h"
121 #include "llvm/ADT/Statistic.h"
122 #include "llvm/Analysis/LoopInfo.h"
123 #include "llvm/Analysis/LoopPass.h"
124 #include "llvm/IR/BasicBlock.h"
125 #include "llvm/IR/DerivedTypes.h"
126 #include "llvm/IR/IRBuilder.h"
127 #include "llvm/IR/Instruction.h"
128 #include "llvm/IR/Instructions.h"
129 #include "llvm/IR/IntrinsicInst.h"
130 #include "llvm/IR/Intrinsics.h"
131 #include "llvm/IR/Use.h"
132 #include "llvm/IR/User.h"
133 #include "llvm/IR/Value.h"
134 #include "llvm/Pass.h"
135 #include "llvm/Support/Casting.h"
136 #include "llvm/Support/CommandLine.h"
137 #include "llvm/Support/Compiler.h"
138 #include "llvm/Support/Debug.h"
139 #include "llvm/Support/raw_ostream.h"
140 #include "llvm/Transforms/Scalar.h"
141 #include "llvm/Transforms/Utils.h"
142 #include <algorithm>
143 #include <cassert>
144 #include <cstddef>
145 #include <map>
146 #include <memory>
147 #include <set>
148
149 using namespace llvm;
150
151 #define DEBUG_TYPE "hexagon-vlcr"
152
153 STATISTIC(HexagonNumVectorLoopCarriedReuse,
154 "Number of values that were reused from a previous iteration.");
155
156 static cl::opt<int> HexagonVLCRIterationLim("hexagon-vlcr-iteration-lim",
157 cl::Hidden,
158 cl::desc("Maximum distance of loop carried dependences that are handled"),
159 cl::init(2), cl::ZeroOrMore);
160
161 namespace llvm {
162
163 void initializeHexagonVectorLoopCarriedReusePass(PassRegistry&);
164 Pass *createHexagonVectorLoopCarriedReusePass();
165
166 } // end namespace llvm
167
168 namespace {
169
170 // See info about DepChain in the comments at the top of this file.
171 using ChainOfDependences = SmallVector<Instruction *, 4>;
172
173 class DepChain {
174 ChainOfDependences Chain;
175
176 public:
isIdentical(DepChain & Other) const177 bool isIdentical(DepChain &Other) const {
178 if (Other.size() != size())
179 return false;
180 ChainOfDependences &OtherChain = Other.getChain();
181 for (int i = 0; i < size(); ++i) {
182 if (Chain[i] != OtherChain[i])
183 return false;
184 }
185 return true;
186 }
187
getChain()188 ChainOfDependences &getChain() {
189 return Chain;
190 }
191
size() const192 int size() const {
193 return Chain.size();
194 }
195
clear()196 void clear() {
197 Chain.clear();
198 }
199
push_back(Instruction * I)200 void push_back(Instruction *I) {
201 Chain.push_back(I);
202 }
203
iterations() const204 int iterations() const {
205 return size() - 1;
206 }
207
front() const208 Instruction *front() const {
209 return Chain.front();
210 }
211
back() const212 Instruction *back() const {
213 return Chain.back();
214 }
215
operator [](const int index)216 Instruction *&operator[](const int index) {
217 return Chain[index];
218 }
219
220 friend raw_ostream &operator<< (raw_ostream &OS, const DepChain &D);
221 };
222
223 LLVM_ATTRIBUTE_UNUSED
operator <<(raw_ostream & OS,const DepChain & D)224 raw_ostream &operator<<(raw_ostream &OS, const DepChain &D) {
225 const ChainOfDependences &CD = D.Chain;
226 int ChainSize = CD.size();
227 OS << "**DepChain Start::**\n";
228 for (int i = 0; i < ChainSize -1; ++i) {
229 OS << *(CD[i]) << " -->\n";
230 }
231 OS << *CD[ChainSize-1] << "\n";
232 return OS;
233 }
234
235 struct ReuseValue {
236 Instruction *Inst2Replace = nullptr;
237
238 // In the new PHI node that we'll construct this is the value that'll be
239 // used over the backedge. This is teh value that gets reused from a
240 // previous iteration.
241 Instruction *BackedgeInst = nullptr;
242
243 ReuseValue() = default;
244
reset__anon020bc6570111::ReuseValue245 void reset() { Inst2Replace = nullptr; BackedgeInst = nullptr; }
isDefined__anon020bc6570111::ReuseValue246 bool isDefined() { return Inst2Replace != nullptr; }
247 };
248
249 LLVM_ATTRIBUTE_UNUSED
operator <<(raw_ostream & OS,const ReuseValue & RU)250 raw_ostream &operator<<(raw_ostream &OS, const ReuseValue &RU) {
251 OS << "** ReuseValue ***\n";
252 OS << "Instruction to Replace: " << *(RU.Inst2Replace) << "\n";
253 OS << "Backedge Instruction: " << *(RU.BackedgeInst) << "\n";
254 return OS;
255 }
256
257 class HexagonVectorLoopCarriedReuse : public LoopPass {
258 public:
259 static char ID;
260
HexagonVectorLoopCarriedReuse()261 explicit HexagonVectorLoopCarriedReuse() : LoopPass(ID) {
262 PassRegistry *PR = PassRegistry::getPassRegistry();
263 initializeHexagonVectorLoopCarriedReusePass(*PR);
264 }
265
getPassName() const266 StringRef getPassName() const override {
267 return "Hexagon-specific loop carried reuse for HVX vectors";
268 }
269
getAnalysisUsage(AnalysisUsage & AU) const270 void getAnalysisUsage(AnalysisUsage &AU) const override {
271 AU.addRequired<LoopInfoWrapperPass>();
272 AU.addRequiredID(LoopSimplifyID);
273 AU.addRequiredID(LCSSAID);
274 AU.addPreservedID(LCSSAID);
275 AU.setPreservesCFG();
276 }
277
278 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
279
280 private:
281 SetVector<DepChain *> Dependences;
282 std::set<Instruction *> ReplacedInsts;
283 Loop *CurLoop;
284 ReuseValue ReuseCandidate;
285
286 bool doVLCR();
287 void findLoopCarriedDeps();
288 void findValueToReuse();
289 void findDepChainFromPHI(Instruction *I, DepChain &D);
290 void reuseValue();
291 Value *findValueInBlock(Value *Op, BasicBlock *BB);
292 bool isDepChainBtwn(Instruction *I1, Instruction *I2, int Iters);
293 DepChain *getDepChainBtwn(Instruction *I1, Instruction *I2);
294 bool isEquivalentOperation(Instruction *I1, Instruction *I2);
295 bool canReplace(Instruction *I);
296 };
297
298 } // end anonymous namespace
299
300 char HexagonVectorLoopCarriedReuse::ID = 0;
301
302 INITIALIZE_PASS_BEGIN(HexagonVectorLoopCarriedReuse, "hexagon-vlcr",
303 "Hexagon-specific predictive commoning for HVX vectors", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)304 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
305 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
306 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
307 INITIALIZE_PASS_END(HexagonVectorLoopCarriedReuse, "hexagon-vlcr",
308 "Hexagon-specific predictive commoning for HVX vectors", false, false)
309
310 bool HexagonVectorLoopCarriedReuse::runOnLoop(Loop *L, LPPassManager &LPM) {
311 if (skipLoop(L))
312 return false;
313
314 if (!L->getLoopPreheader())
315 return false;
316
317 // Work only on innermost loops.
318 if (!L->getSubLoops().empty())
319 return false;
320
321 // Work only on single basic blocks loops.
322 if (L->getNumBlocks() != 1)
323 return false;
324
325 CurLoop = L;
326
327 return doVLCR();
328 }
329
isEquivalentOperation(Instruction * I1,Instruction * I2)330 bool HexagonVectorLoopCarriedReuse::isEquivalentOperation(Instruction *I1,
331 Instruction *I2) {
332 if (!I1->isSameOperationAs(I2))
333 return false;
334 // This check is in place specifically for intrinsics. isSameOperationAs will
335 // return two for any two hexagon intrinsics because they are essentially the
336 // same instruciton (CallInst). We need to scratch the surface to see if they
337 // are calls to the same function.
338 if (CallInst *C1 = dyn_cast<CallInst>(I1)) {
339 if (CallInst *C2 = dyn_cast<CallInst>(I2)) {
340 if (C1->getCalledFunction() != C2->getCalledFunction())
341 return false;
342 }
343 }
344
345 // If both the Instructions are of Vector Type and any of the element
346 // is integer constant, check their values too for equivalence.
347 if (I1->getType()->isVectorTy() && I2->getType()->isVectorTy()) {
348 unsigned NumOperands = I1->getNumOperands();
349 for (unsigned i = 0; i < NumOperands; ++i) {
350 ConstantInt *C1 = dyn_cast<ConstantInt>(I1->getOperand(i));
351 ConstantInt *C2 = dyn_cast<ConstantInt>(I2->getOperand(i));
352 if(!C1) continue;
353 assert(C2);
354 if (C1->getSExtValue() != C2->getSExtValue())
355 return false;
356 }
357 }
358
359 return true;
360 }
361
canReplace(Instruction * I)362 bool HexagonVectorLoopCarriedReuse::canReplace(Instruction *I) {
363 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
364 if (II &&
365 (II->getIntrinsicID() == Intrinsic::hexagon_V6_hi ||
366 II->getIntrinsicID() == Intrinsic::hexagon_V6_lo)) {
367 LLVM_DEBUG(dbgs() << "Not considering for reuse: " << *II << "\n");
368 return false;
369 }
370 return true;
371 }
findValueToReuse()372 void HexagonVectorLoopCarriedReuse::findValueToReuse() {
373 for (auto *D : Dependences) {
374 LLVM_DEBUG(dbgs() << "Processing dependence " << *(D->front()) << "\n");
375 if (D->iterations() > HexagonVLCRIterationLim) {
376 LLVM_DEBUG(
377 dbgs()
378 << ".. Skipping because number of iterations > than the limit\n");
379 continue;
380 }
381
382 PHINode *PN = cast<PHINode>(D->front());
383 Instruction *BEInst = D->back();
384 int Iters = D->iterations();
385 BasicBlock *BB = PN->getParent();
386 LLVM_DEBUG(dbgs() << "Checking if any uses of " << *PN
387 << " can be reused\n");
388
389 SmallVector<Instruction *, 4> PNUsers;
390 for (auto UI = PN->use_begin(), E = PN->use_end(); UI != E; ++UI) {
391 Use &U = *UI;
392 Instruction *User = cast<Instruction>(U.getUser());
393
394 if (User->getParent() != BB)
395 continue;
396 if (ReplacedInsts.count(User)) {
397 LLVM_DEBUG(dbgs() << *User
398 << " has already been replaced. Skipping...\n");
399 continue;
400 }
401 if (isa<PHINode>(User))
402 continue;
403 if (User->mayHaveSideEffects())
404 continue;
405 if (!canReplace(User))
406 continue;
407
408 PNUsers.push_back(User);
409 }
410 LLVM_DEBUG(dbgs() << PNUsers.size() << " use(s) of the PHI in the block\n");
411
412 // For each interesting use I of PN, find an Instruction BEUser that
413 // performs the same operation as I on BEInst and whose other operands,
414 // if any, can also be rematerialized in OtherBB. We stop when we find the
415 // first such Instruction BEUser. This is because once BEUser is
416 // rematerialized in OtherBB, we may find more such "fixup" opportunities
417 // in this block. So, we'll start over again.
418 for (Instruction *I : PNUsers) {
419 for (auto UI = BEInst->use_begin(), E = BEInst->use_end(); UI != E;
420 ++UI) {
421 Use &U = *UI;
422 Instruction *BEUser = cast<Instruction>(U.getUser());
423
424 if (BEUser->getParent() != BB)
425 continue;
426 if (!isEquivalentOperation(I, BEUser))
427 continue;
428
429 int NumOperands = I->getNumOperands();
430
431 for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
432 Value *Op = I->getOperand(OpNo);
433 Instruction *OpInst = dyn_cast<Instruction>(Op);
434 if (!OpInst)
435 continue;
436
437 Value *BEOp = BEUser->getOperand(OpNo);
438 Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
439
440 if (!isDepChainBtwn(OpInst, BEOpInst, Iters)) {
441 BEUser = nullptr;
442 break;
443 }
444 }
445 if (BEUser) {
446 LLVM_DEBUG(dbgs() << "Found Value for reuse.\n");
447 ReuseCandidate.Inst2Replace = I;
448 ReuseCandidate.BackedgeInst = BEUser;
449 return;
450 } else
451 ReuseCandidate.reset();
452 }
453 }
454 }
455 ReuseCandidate.reset();
456 }
457
findValueInBlock(Value * Op,BasicBlock * BB)458 Value *HexagonVectorLoopCarriedReuse::findValueInBlock(Value *Op,
459 BasicBlock *BB) {
460 PHINode *PN = dyn_cast<PHINode>(Op);
461 assert(PN);
462 Value *ValueInBlock = PN->getIncomingValueForBlock(BB);
463 return ValueInBlock;
464 }
465
reuseValue()466 void HexagonVectorLoopCarriedReuse::reuseValue() {
467 LLVM_DEBUG(dbgs() << ReuseCandidate);
468 Instruction *Inst2Replace = ReuseCandidate.Inst2Replace;
469 Instruction *BEInst = ReuseCandidate.BackedgeInst;
470 int NumOperands = Inst2Replace->getNumOperands();
471 std::map<Instruction *, DepChain *> DepChains;
472 int Iterations = -1;
473 BasicBlock *LoopPH = CurLoop->getLoopPreheader();
474
475 for (int i = 0; i < NumOperands; ++i) {
476 Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(i));
477 if(!I)
478 continue;
479 else {
480 Instruction *J = cast<Instruction>(BEInst->getOperand(i));
481 DepChain *D = getDepChainBtwn(I, J);
482
483 assert(D &&
484 "No DepChain between corresponding operands in ReuseCandidate\n");
485 if (Iterations == -1)
486 Iterations = D->iterations();
487 assert(Iterations == D->iterations() && "Iterations mismatch");
488 DepChains[I] = D;
489 }
490 }
491
492 LLVM_DEBUG(dbgs() << "reuseValue is making the following changes\n");
493
494 SmallVector<Instruction *, 4> InstsInPreheader;
495 for (int i = 0; i < Iterations; ++i) {
496 Instruction *InstInPreheader = Inst2Replace->clone();
497 SmallVector<Value *, 4> Ops;
498 for (int j = 0; j < NumOperands; ++j) {
499 Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(j));
500 if (!I)
501 continue;
502 // Get the DepChain corresponding to this operand.
503 DepChain &D = *DepChains[I];
504 // Get the PHI for the iteration number and find
505 // the incoming value from the Loop Preheader for
506 // that PHI.
507 Value *ValInPreheader = findValueInBlock(D[i], LoopPH);
508 InstInPreheader->setOperand(j, ValInPreheader);
509 }
510 InstsInPreheader.push_back(InstInPreheader);
511 InstInPreheader->setName(Inst2Replace->getName() + ".hexagon.vlcr");
512 InstInPreheader->insertBefore(LoopPH->getTerminator());
513 LLVM_DEBUG(dbgs() << "Added " << *InstInPreheader << " to "
514 << LoopPH->getName() << "\n");
515 }
516 BasicBlock *BB = BEInst->getParent();
517 IRBuilder<> IRB(BB);
518 IRB.SetInsertPoint(BB->getFirstNonPHI());
519 Value *BEVal = BEInst;
520 PHINode *NewPhi;
521 for (int i = Iterations-1; i >=0 ; --i) {
522 Instruction *InstInPreheader = InstsInPreheader[i];
523 NewPhi = IRB.CreatePHI(InstInPreheader->getType(), 2);
524 NewPhi->addIncoming(InstInPreheader, LoopPH);
525 NewPhi->addIncoming(BEVal, BB);
526 LLVM_DEBUG(dbgs() << "Adding " << *NewPhi << " to " << BB->getName()
527 << "\n");
528 BEVal = NewPhi;
529 }
530 // We are in LCSSA form. So, a value defined inside the Loop is used only
531 // inside the loop. So, the following is safe.
532 Inst2Replace->replaceAllUsesWith(NewPhi);
533 ReplacedInsts.insert(Inst2Replace);
534 ++HexagonNumVectorLoopCarriedReuse;
535 }
536
doVLCR()537 bool HexagonVectorLoopCarriedReuse::doVLCR() {
538 assert(CurLoop->getSubLoops().empty() &&
539 "Can do VLCR on the innermost loop only");
540 assert((CurLoop->getNumBlocks() == 1) &&
541 "Can do VLCR only on single block loops");
542
543 bool Changed = false;
544 bool Continue;
545
546 LLVM_DEBUG(dbgs() << "Working on Loop: " << *CurLoop->getHeader() << "\n");
547 do {
548 // Reset datastructures.
549 Dependences.clear();
550 Continue = false;
551
552 findLoopCarriedDeps();
553 findValueToReuse();
554 if (ReuseCandidate.isDefined()) {
555 reuseValue();
556 Changed = true;
557 Continue = true;
558 }
559 llvm::for_each(Dependences, std::default_delete<DepChain>());
560 } while (Continue);
561 return Changed;
562 }
563
findDepChainFromPHI(Instruction * I,DepChain & D)564 void HexagonVectorLoopCarriedReuse::findDepChainFromPHI(Instruction *I,
565 DepChain &D) {
566 PHINode *PN = dyn_cast<PHINode>(I);
567 if (!PN) {
568 D.push_back(I);
569 return;
570 } else {
571 auto NumIncomingValues = PN->getNumIncomingValues();
572 if (NumIncomingValues != 2) {
573 D.clear();
574 return;
575 }
576
577 BasicBlock *BB = PN->getParent();
578 if (BB != CurLoop->getHeader()) {
579 D.clear();
580 return;
581 }
582
583 Value *BEVal = PN->getIncomingValueForBlock(BB);
584 Instruction *BEInst = dyn_cast<Instruction>(BEVal);
585 // This is a single block loop with a preheader, so at least
586 // one value should come over the backedge.
587 assert(BEInst && "There should be a value over the backedge");
588
589 Value *PreHdrVal =
590 PN->getIncomingValueForBlock(CurLoop->getLoopPreheader());
591 if(!PreHdrVal || !isa<Instruction>(PreHdrVal)) {
592 D.clear();
593 return;
594 }
595 D.push_back(PN);
596 findDepChainFromPHI(BEInst, D);
597 }
598 }
599
isDepChainBtwn(Instruction * I1,Instruction * I2,int Iters)600 bool HexagonVectorLoopCarriedReuse::isDepChainBtwn(Instruction *I1,
601 Instruction *I2,
602 int Iters) {
603 for (auto *D : Dependences) {
604 if (D->front() == I1 && D->back() == I2 && D->iterations() == Iters)
605 return true;
606 }
607 return false;
608 }
609
getDepChainBtwn(Instruction * I1,Instruction * I2)610 DepChain *HexagonVectorLoopCarriedReuse::getDepChainBtwn(Instruction *I1,
611 Instruction *I2) {
612 for (auto *D : Dependences) {
613 if (D->front() == I1 && D->back() == I2)
614 return D;
615 }
616 return nullptr;
617 }
618
findLoopCarriedDeps()619 void HexagonVectorLoopCarriedReuse::findLoopCarriedDeps() {
620 BasicBlock *BB = CurLoop->getHeader();
621 for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) {
622 auto *PN = cast<PHINode>(I);
623 if (!isa<VectorType>(PN->getType()))
624 continue;
625
626 DepChain *D = new DepChain();
627 findDepChainFromPHI(PN, *D);
628 if (D->size() != 0)
629 Dependences.insert(D);
630 else
631 delete D;
632 }
633 LLVM_DEBUG(dbgs() << "Found " << Dependences.size() << " dependences\n");
634 LLVM_DEBUG(for (size_t i = 0; i < Dependences.size();
635 ++i) { dbgs() << *Dependences[i] << "\n"; });
636 }
637
createHexagonVectorLoopCarriedReusePass()638 Pass *llvm::createHexagonVectorLoopCarriedReusePass() {
639 return new HexagonVectorLoopCarriedReuse();
640 }
641