1 //===- HexagonVectorLoopCarriedReuse.cpp ----------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
15 //-----------------------------------------------------------------------------
16 // Motivation: Consider the case where we have the following loop structure.
29 // This can be converted to
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.
48 // X2 = PHI<(X0, LoopPreheader), (X1, Loop)>
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
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.
73 // We then make the following transformation
78 // X2 = PHI<(X0, LoopPreheader), (X1, Loop)>
79 // Y2 = PHI<(Y0, LoopPreheader), (t4, Loop)>
80 // t1 = f(X2) <-- Will be removed by DCE.
89 // We proceed until we cannot find any more such instructions I1 and I2.
91 // --- DepChains & Loop carried dependences ---
92 // Consider a single basic block loop such as
98 // X2 = PHI<(X0, LoopPreheader), (X1, Loop)>
99 // Y2 = PHI<(Y0, LoopPreheader), (X2, Loop)>
103 // cond_branch <Loop>
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).
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.
117 //===----------------------------------------------------------------------===//
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"
148 using namespace llvm;
150 #define DEBUG_TYPE "hexagon-vlcr"
152 STATISTIC(HexagonNumVectorLoopCarriedReuse,
153 "Number of values that were reused from a previous iteration.");
155 static cl::opt<int> HexagonVLCRIterationLim("hexagon-vlcr-iteration-lim",
157 cl::desc("Maximum distance of loop carried dependences that are handled"),
158 cl::init(2), cl::ZeroOrMore);
162 void initializeHexagonVectorLoopCarriedReusePass(PassRegistry&);
163 Pass *createHexagonVectorLoopCarriedReusePass();
165 } // end namespace llvm
169 // See info about DepChain in the comments at the top of this file.
170 using ChainOfDependences = SmallVector<Instruction *, 4>;
173 ChainOfDependences Chain;
176 bool isIdentical(DepChain &Other) const {
177 if (Other.size() != size())
179 ChainOfDependences &OtherChain = Other.getChain();
180 for (int i = 0; i < size(); ++i) {
181 if (Chain[i] != OtherChain[i])
187 ChainOfDependences &getChain() {
199 void push_back(Instruction *I) {
203 int iterations() const {
207 Instruction *front() const {
208 return Chain.front();
211 Instruction *back() const {
215 Instruction *&operator[](const int index) {
219 friend raw_ostream &operator<< (raw_ostream &OS, const DepChain &D);
222 LLVM_ATTRIBUTE_UNUSED
223 raw_ostream &operator<<(raw_ostream &OS, const DepChain &D) {
224 const ChainOfDependences &CD = D.Chain;
225 int ChainSize = CD.size();
226 OS << "**DepChain Start::**\n";
227 for (int i = 0; i < ChainSize -1; ++i) {
228 OS << *(CD[i]) << " -->\n";
230 OS << *CD[ChainSize-1] << "\n";
235 Instruction *Inst2Replace = nullptr;
237 // In the new PHI node that we'll construct this is the value that'll be
238 // used over the backedge. This is teh value that gets reused from a
239 // previous iteration.
240 Instruction *BackedgeInst = nullptr;
242 ReuseValue() = default;
244 void reset() { Inst2Replace = nullptr; BackedgeInst = nullptr; }
245 bool isDefined() { return Inst2Replace != nullptr; }
248 LLVM_ATTRIBUTE_UNUSED
249 raw_ostream &operator<<(raw_ostream &OS, const ReuseValue &RU) {
250 OS << "** ReuseValue ***\n";
251 OS << "Instruction to Replace: " << *(RU.Inst2Replace) << "\n";
252 OS << "Backedge Instruction: " << *(RU.BackedgeInst) << "\n";
256 class HexagonVectorLoopCarriedReuse : public LoopPass {
260 explicit HexagonVectorLoopCarriedReuse() : LoopPass(ID) {
261 PassRegistry *PR = PassRegistry::getPassRegistry();
262 initializeHexagonVectorLoopCarriedReusePass(*PR);
265 StringRef getPassName() const override {
266 return "Hexagon-specific loop carried reuse for HVX vectors";
269 void getAnalysisUsage(AnalysisUsage &AU) const override {
270 AU.addRequired<LoopInfoWrapperPass>();
271 AU.addRequiredID(LoopSimplifyID);
272 AU.addRequiredID(LCSSAID);
273 AU.addPreservedID(LCSSAID);
274 AU.setPreservesCFG();
277 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
280 SetVector<DepChain *> Dependences;
281 std::set<Instruction *> ReplacedInsts;
283 ReuseValue ReuseCandidate;
286 void findLoopCarriedDeps();
287 void findValueToReuse();
288 void findDepChainFromPHI(Instruction *I, DepChain &D);
290 Value *findValueInBlock(Value *Op, BasicBlock *BB);
291 bool isDepChainBtwn(Instruction *I1, Instruction *I2, int Iters);
292 DepChain *getDepChainBtwn(Instruction *I1, Instruction *I2);
293 bool isEquivalentOperation(Instruction *I1, Instruction *I2);
294 bool canReplace(Instruction *I);
297 } // end anonymous namespace
299 char HexagonVectorLoopCarriedReuse::ID = 0;
301 INITIALIZE_PASS_BEGIN(HexagonVectorLoopCarriedReuse, "hexagon-vlcr",
302 "Hexagon-specific predictive commoning for HVX vectors", false, false)
303 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
304 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
305 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
306 INITIALIZE_PASS_END(HexagonVectorLoopCarriedReuse, "hexagon-vlcr",
307 "Hexagon-specific predictive commoning for HVX vectors", false, false)
309 bool HexagonVectorLoopCarriedReuse::runOnLoop(Loop *L, LPPassManager &LPM) {
313 if (!L->getLoopPreheader())
316 // Work only on innermost loops.
317 if (!L->getSubLoops().empty())
320 // Work only on single basic blocks loops.
321 if (L->getNumBlocks() != 1)
329 bool HexagonVectorLoopCarriedReuse::isEquivalentOperation(Instruction *I1,
331 if (!I1->isSameOperationAs(I2))
333 // This check is in place specifically for intrinsics. isSameOperationAs will
334 // return two for any two hexagon intrinsics because they are essentially the
335 // same instruciton (CallInst). We need to scratch the surface to see if they
336 // are calls to the same function.
337 if (CallInst *C1 = dyn_cast<CallInst>(I1)) {
338 if (CallInst *C2 = dyn_cast<CallInst>(I2)) {
339 if (C1->getCalledFunction() != C2->getCalledFunction())
344 // If both the Instructions are of Vector Type and any of the element
345 // is integer constant, check their values too for equivalence.
346 if (I1->getType()->isVectorTy() && I2->getType()->isVectorTy()) {
347 unsigned NumOperands = I1->getNumOperands();
348 for (unsigned i = 0; i < NumOperands; ++i) {
349 ConstantInt *C1 = dyn_cast<ConstantInt>(I1->getOperand(i));
350 ConstantInt *C2 = dyn_cast<ConstantInt>(I2->getOperand(i));
353 if (C1->getSExtValue() != C2->getSExtValue())
361 bool HexagonVectorLoopCarriedReuse::canReplace(Instruction *I) {
362 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
364 (II->getIntrinsicID() == Intrinsic::hexagon_V6_hi ||
365 II->getIntrinsicID() == Intrinsic::hexagon_V6_lo)) {
366 DEBUG(dbgs() << "Not considering for reuse: " << *II << "\n");
371 void HexagonVectorLoopCarriedReuse::findValueToReuse() {
372 for (auto *D : Dependences) {
373 DEBUG(dbgs() << "Processing dependence " << *(D->front()) << "\n");
374 if (D->iterations() > HexagonVLCRIterationLim) {
376 ".. Skipping because number of iterations > than the limit\n");
380 PHINode *PN = cast<PHINode>(D->front());
381 Instruction *BEInst = D->back();
382 int Iters = D->iterations();
383 BasicBlock *BB = PN->getParent();
384 DEBUG(dbgs() << "Checking if any uses of " << *PN << " can be reused\n");
386 SmallVector<Instruction *, 4> PNUsers;
387 for (auto UI = PN->use_begin(), E = PN->use_end(); UI != E; ++UI) {
389 Instruction *User = cast<Instruction>(U.getUser());
391 if (User->getParent() != BB)
393 if (ReplacedInsts.count(User)) {
394 DEBUG(dbgs() << *User << " has already been replaced. Skipping...\n");
397 if (isa<PHINode>(User))
399 if (User->mayHaveSideEffects())
401 if (!canReplace(User))
404 PNUsers.push_back(User);
406 DEBUG(dbgs() << PNUsers.size() << " use(s) of the PHI in the block\n");
408 // For each interesting use I of PN, find an Instruction BEUser that
409 // performs the same operation as I on BEInst and whose other operands,
410 // if any, can also be rematerialized in OtherBB. We stop when we find the
411 // first such Instruction BEUser. This is because once BEUser is
412 // rematerialized in OtherBB, we may find more such "fixup" opportunities
413 // in this block. So, we'll start over again.
414 for (Instruction *I : PNUsers) {
415 for (auto UI = BEInst->use_begin(), E = BEInst->use_end(); UI != E;
418 Instruction *BEUser = cast<Instruction>(U.getUser());
420 if (BEUser->getParent() != BB)
422 if (!isEquivalentOperation(I, BEUser))
425 int NumOperands = I->getNumOperands();
427 for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
428 Value *Op = I->getOperand(OpNo);
429 Instruction *OpInst = dyn_cast<Instruction>(Op);
433 Value *BEOp = BEUser->getOperand(OpNo);
434 Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
436 if (!isDepChainBtwn(OpInst, BEOpInst, Iters)) {
442 DEBUG(dbgs() << "Found Value for reuse.\n");
443 ReuseCandidate.Inst2Replace = I;
444 ReuseCandidate.BackedgeInst = BEUser;
447 ReuseCandidate.reset();
451 ReuseCandidate.reset();
454 Value *HexagonVectorLoopCarriedReuse::findValueInBlock(Value *Op,
456 PHINode *PN = dyn_cast<PHINode>(Op);
458 Value *ValueInBlock = PN->getIncomingValueForBlock(BB);
462 void HexagonVectorLoopCarriedReuse::reuseValue() {
463 DEBUG(dbgs() << ReuseCandidate);
464 Instruction *Inst2Replace = ReuseCandidate.Inst2Replace;
465 Instruction *BEInst = ReuseCandidate.BackedgeInst;
466 int NumOperands = Inst2Replace->getNumOperands();
467 std::map<Instruction *, DepChain *> DepChains;
469 BasicBlock *LoopPH = CurLoop->getLoopPreheader();
471 for (int i = 0; i < NumOperands; ++i) {
472 Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(i));
476 Instruction *J = cast<Instruction>(BEInst->getOperand(i));
477 DepChain *D = getDepChainBtwn(I, J);
480 "No DepChain between corresponding operands in ReuseCandidate\n");
481 if (Iterations == -1)
482 Iterations = D->iterations();
483 assert(Iterations == D->iterations() && "Iterations mismatch");
488 DEBUG(dbgs() << "reuseValue is making the following changes\n");
490 SmallVector<Instruction *, 4> InstsInPreheader;
491 for (int i = 0; i < Iterations; ++i) {
492 Instruction *InstInPreheader = Inst2Replace->clone();
493 SmallVector<Value *, 4> Ops;
494 for (int j = 0; j < NumOperands; ++j) {
495 Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(j));
498 // Get the DepChain corresponding to this operand.
499 DepChain &D = *DepChains[I];
500 // Get the PHI for the iteration number and find
501 // the incoming value from the Loop Preheader for
503 Value *ValInPreheader = findValueInBlock(D[i], LoopPH);
504 InstInPreheader->setOperand(j, ValInPreheader);
506 InstsInPreheader.push_back(InstInPreheader);
507 InstInPreheader->setName(Inst2Replace->getName() + ".hexagon.vlcr");
508 InstInPreheader->insertBefore(LoopPH->getTerminator());
509 DEBUG(dbgs() << "Added " << *InstInPreheader << " to " << LoopPH->getName()
512 BasicBlock *BB = BEInst->getParent();
514 IRB.SetInsertPoint(BB->getFirstNonPHI());
515 Value *BEVal = BEInst;
517 for (int i = Iterations-1; i >=0 ; --i) {
518 Instruction *InstInPreheader = InstsInPreheader[i];
519 NewPhi = IRB.CreatePHI(InstInPreheader->getType(), 2);
520 NewPhi->addIncoming(InstInPreheader, LoopPH);
521 NewPhi->addIncoming(BEVal, BB);
522 DEBUG(dbgs() << "Adding " << *NewPhi << " to " << BB->getName() << "\n");
525 // We are in LCSSA form. So, a value defined inside the Loop is used only
526 // inside the loop. So, the following is safe.
527 Inst2Replace->replaceAllUsesWith(NewPhi);
528 ReplacedInsts.insert(Inst2Replace);
529 ++HexagonNumVectorLoopCarriedReuse;
532 bool HexagonVectorLoopCarriedReuse::doVLCR() {
533 assert(CurLoop->getSubLoops().empty() &&
534 "Can do VLCR on the innermost loop only");
535 assert((CurLoop->getNumBlocks() == 1) &&
536 "Can do VLCR only on single block loops");
538 bool Changed = false;
541 DEBUG(dbgs() << "Working on Loop: " << *CurLoop->getHeader() << "\n");
543 // Reset datastructures.
547 findLoopCarriedDeps();
549 if (ReuseCandidate.isDefined()) {
554 llvm::for_each(Dependences, std::default_delete<DepChain>());
559 void HexagonVectorLoopCarriedReuse::findDepChainFromPHI(Instruction *I,
561 PHINode *PN = dyn_cast<PHINode>(I);
566 auto NumIncomingValues = PN->getNumIncomingValues();
567 if (NumIncomingValues != 2) {
572 BasicBlock *BB = PN->getParent();
573 if (BB != CurLoop->getHeader()) {
578 Value *BEVal = PN->getIncomingValueForBlock(BB);
579 Instruction *BEInst = dyn_cast<Instruction>(BEVal);
580 // This is a single block loop with a preheader, so at least
581 // one value should come over the backedge.
582 assert(BEInst && "There should be a value over the backedge");
585 PN->getIncomingValueForBlock(CurLoop->getLoopPreheader());
586 if(!PreHdrVal || !isa<Instruction>(PreHdrVal)) {
591 findDepChainFromPHI(BEInst, D);
595 bool HexagonVectorLoopCarriedReuse::isDepChainBtwn(Instruction *I1,
598 for (auto *D : Dependences) {
599 if (D->front() == I1 && D->back() == I2 && D->iterations() == Iters)
605 DepChain *HexagonVectorLoopCarriedReuse::getDepChainBtwn(Instruction *I1,
607 for (auto *D : Dependences) {
608 if (D->front() == I1 && D->back() == I2)
614 void HexagonVectorLoopCarriedReuse::findLoopCarriedDeps() {
615 BasicBlock *BB = CurLoop->getHeader();
616 for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) {
617 auto *PN = cast<PHINode>(I);
618 if (!isa<VectorType>(PN->getType()))
621 DepChain *D = new DepChain();
622 findDepChainFromPHI(PN, *D);
624 Dependences.insert(D);
628 DEBUG(dbgs() << "Found " << Dependences.size() << " dependences\n");
629 DEBUG(for (size_t i = 0; i < Dependences.size(); ++i) {
630 dbgs() << *Dependences[i] << "\n";
634 Pass *llvm::createHexagonVectorLoopCarriedReusePass() {
635 return new HexagonVectorLoopCarriedReuse();