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