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
49using namespace llvm;
50
51#define DEBUG_TYPE "hexagon-vlcr"
52
53STATISTIC(HexagonNumVectorLoopCarriedReuse,
54 "Number of values that were reused from a previous iteration.");
55
56static cl::opt<int> HexagonVLCRIterationLim(
57 "hexagon-vlcr-iteration-lim", cl::Hidden,
58 cl::desc("Maximum distance of loop carried dependences that are handled"),
59 cl::init(Val: 2));
60
61namespace llvm {
62
63void initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PassRegistry &);
64Pass *createHexagonVectorLoopCarriedReuseLegacyPass();
65
66} // end namespace llvm
67
68namespace {
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(Elt: 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(ID&: LoopSimplifyID);
179 AU.addRequiredID(ID&: LCSSAID);
180 AU.addPreservedID(ID&: 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
213char HexagonVectorLoopCarriedReuseLegacyPass::ID = 0;
214
215INITIALIZE_PASS_BEGIN(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
216 "Hexagon-specific predictive commoning for HVX vectors",
217 false, false)
218INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
219INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
220INITIALIZE_PASS_END(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
221 "Hexagon-specific predictive commoning for HVX vectors",
222 false, false)
223
224PreservedAnalyses
225HexagonVectorLoopCarriedReusePass::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
236bool HexagonVectorLoopCarriedReuseLegacyPass::runOnLoop(Loop *L,
237 LPPassManager &LPM) {
238 if (skipLoop(L))
239 return false;
240 HexagonVectorLoopCarriedReuse Vlcr(L);
241 return Vlcr.run();
242}
243
244bool 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
259bool 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
323bool HexagonVectorLoopCarriedReuse::isEquivalentOperation(Instruction *I1,
324 Instruction *I2) {
325 if (!I1->isSameOperationAs(I: 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>(Val: I1)) {
332 if (CallInst *C2 = dyn_cast<CallInst>(Val: 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>(Val: I1->getOperand(i));
344 ConstantInt *C2 = dyn_cast<ConstantInt>(Val: 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
355bool HexagonVectorLoopCarriedReuse::canReplace(Instruction *I) {
356 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: 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}
371void 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>(Val: 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>(Val: U.getUser());
391
392 if (User->getParent() != BB)
393 continue;
394 if (ReplacedInsts.count(x: User)) {
395 LLVM_DEBUG(dbgs() << *User
396 << " has already been replaced. Skipping...\n");
397 continue;
398 }
399 if (isa<PHINode>(Val: User))
400 continue;
401 if (User->mayHaveSideEffects())
402 continue;
403 if (!canReplace(I: User))
404 continue;
405
406 PNUsers.push_back(Elt: 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>(Val: U.getUser());
419
420 if (BEUser->getParent() != BB)
421 continue;
422 if (!isEquivalentOperation(I1: I, I2: 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>(Val: I);
438 if ((I && I->isCommutative()) || (C1 && isCallInstCommutative(C: C1))) {
439 bool Found = false;
440 for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
441 Value *Op = I->getOperand(i: OpNo);
442 Instruction *OpInst = dyn_cast<Instruction>(Val: Op);
443 Found = false;
444 for (int T = 0; T < NumOperands; ++T) {
445 Value *BEOp = BEUser->getOperand(i: T);
446 Instruction *BEOpInst = dyn_cast<Instruction>(Val: 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(I1: OpInst, I2: 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(i: OpNo);
474 Value *BEOp = BEUser->getOperand(i: OpNo);
475
476 Instruction *OpInst = dyn_cast<Instruction>(Val: 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>(Val: BEOp);
487 DepChain *D = getDepChainBtwn(I1: OpInst, I2: 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
512Value *HexagonVectorLoopCarriedReuse::findValueInBlock(Value *Op,
513 BasicBlock *BB) {
514 PHINode *PN = dyn_cast<PHINode>(Val: Op);
515 assert(PN);
516 Value *ValueInBlock = PN->getIncomingValueForBlock(BB);
517 return ValueInBlock;
518}
519
520void 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>(Val: Inst2Replace->getOperand(i: 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(Op: D[i], BB: LoopPH);
545 InstInPreheader->setOperand(i: j, Val: ValInPreheader);
546 }
547 InstsInPreheader.push_back(Elt: InstInPreheader);
548 InstInPreheader->setName(Inst2Replace->getName() + ".hexagon.vlcr");
549 InstInPreheader->insertBefore(InsertPos: 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(TheBB: BB, IP: BB->getFirstNonPHIIt());
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(Ty: InstInPreheader->getType(), NumReservedValues: 2);
561 NewPhi->addIncoming(V: InstInPreheader, BB: LoopPH);
562 NewPhi->addIncoming(V: 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(V: NewPhi);
570 ReplacedInsts.insert(x: Inst2Replace);
571 ++HexagonNumVectorLoopCarriedReuse;
572}
573
574bool 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(Range&: Dependences, F: std::default_delete<DepChain>());
597 } while (Continue);
598 return Changed;
599}
600
601void HexagonVectorLoopCarriedReuse::findDepChainFromPHI(Instruction *I,
602 DepChain &D) {
603 PHINode *PN = dyn_cast<PHINode>(Val: 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>(Val: 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(BB: CurLoop->getLoopPreheader());
628 if(!PreHdrVal || !isa<Instruction>(Val: PreHdrVal)) {
629 D.clear();
630 return;
631 }
632 D.push_back(I: PN);
633 findDepChainFromPHI(I: BEInst, D);
634 }
635}
636
637DepChain *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
647void HexagonVectorLoopCarriedReuse::findLoopCarriedDeps() {
648 BasicBlock *BB = CurLoop->getHeader();
649 for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(Val: I); ++I) {
650 auto *PN = cast<PHINode>(Val&: I);
651 if (!isa<VectorType>(Val: PN->getType()))
652 continue;
653
654 DepChain *D = new DepChain();
655 findDepChainFromPHI(I: PN, D&: *D);
656 if (D->size() != 0)
657 Dependences.insert(X: 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
665Pass *llvm::createHexagonVectorLoopCarriedReuseLegacyPass() {
666 return new HexagonVectorLoopCarriedReuseLegacyPass();
667}
668