106f32e7eSjoerg //===- HexagonVectorLoopCarriedReuse.cpp ----------------------------------===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This pass removes the computation of provably redundant expressions that have
1006f32e7eSjoerg // been computed earlier in a previous iteration. It relies on the use of PHIs
1106f32e7eSjoerg // to identify loop carried dependences. This is scalar replacement for vector
1206f32e7eSjoerg // types.
1306f32e7eSjoerg //
1406f32e7eSjoerg //===----------------------------------------------------------------------===//
1506f32e7eSjoerg
16*da58b97aSjoerg #include "HexagonVectorLoopCarriedReuse.h"
1706f32e7eSjoerg #include "llvm/ADT/SetVector.h"
1806f32e7eSjoerg #include "llvm/ADT/SmallVector.h"
1906f32e7eSjoerg #include "llvm/ADT/Statistic.h"
2006f32e7eSjoerg #include "llvm/Analysis/LoopInfo.h"
2106f32e7eSjoerg #include "llvm/Analysis/LoopPass.h"
2206f32e7eSjoerg #include "llvm/IR/BasicBlock.h"
2306f32e7eSjoerg #include "llvm/IR/DerivedTypes.h"
2406f32e7eSjoerg #include "llvm/IR/IRBuilder.h"
2506f32e7eSjoerg #include "llvm/IR/Instruction.h"
2606f32e7eSjoerg #include "llvm/IR/Instructions.h"
2706f32e7eSjoerg #include "llvm/IR/IntrinsicInst.h"
2806f32e7eSjoerg #include "llvm/IR/Intrinsics.h"
29*da58b97aSjoerg #include "llvm/IR/IntrinsicsHexagon.h"
3006f32e7eSjoerg #include "llvm/IR/Use.h"
3106f32e7eSjoerg #include "llvm/IR/User.h"
3206f32e7eSjoerg #include "llvm/IR/Value.h"
33*da58b97aSjoerg #include "llvm/InitializePasses.h"
3406f32e7eSjoerg #include "llvm/Pass.h"
3506f32e7eSjoerg #include "llvm/Support/Casting.h"
3606f32e7eSjoerg #include "llvm/Support/CommandLine.h"
3706f32e7eSjoerg #include "llvm/Support/Compiler.h"
3806f32e7eSjoerg #include "llvm/Support/Debug.h"
3906f32e7eSjoerg #include "llvm/Support/raw_ostream.h"
4006f32e7eSjoerg #include "llvm/Transforms/Scalar.h"
4106f32e7eSjoerg #include "llvm/Transforms/Utils.h"
4206f32e7eSjoerg #include <algorithm>
4306f32e7eSjoerg #include <cassert>
4406f32e7eSjoerg #include <cstddef>
4506f32e7eSjoerg #include <map>
4606f32e7eSjoerg #include <memory>
4706f32e7eSjoerg #include <set>
4806f32e7eSjoerg
4906f32e7eSjoerg using namespace llvm;
5006f32e7eSjoerg
5106f32e7eSjoerg #define DEBUG_TYPE "hexagon-vlcr"
5206f32e7eSjoerg
5306f32e7eSjoerg STATISTIC(HexagonNumVectorLoopCarriedReuse,
5406f32e7eSjoerg "Number of values that were reused from a previous iteration.");
5506f32e7eSjoerg
5606f32e7eSjoerg static cl::opt<int> HexagonVLCRIterationLim("hexagon-vlcr-iteration-lim",
5706f32e7eSjoerg cl::Hidden,
5806f32e7eSjoerg cl::desc("Maximum distance of loop carried dependences that are handled"),
5906f32e7eSjoerg cl::init(2), cl::ZeroOrMore);
6006f32e7eSjoerg
6106f32e7eSjoerg namespace llvm {
6206f32e7eSjoerg
63*da58b97aSjoerg void initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PassRegistry &);
64*da58b97aSjoerg Pass *createHexagonVectorLoopCarriedReuseLegacyPass();
6506f32e7eSjoerg
6606f32e7eSjoerg } // end namespace llvm
6706f32e7eSjoerg
6806f32e7eSjoerg namespace {
6906f32e7eSjoerg
7006f32e7eSjoerg // See info about DepChain in the comments at the top of this file.
7106f32e7eSjoerg using ChainOfDependences = SmallVector<Instruction *, 4>;
7206f32e7eSjoerg
7306f32e7eSjoerg class DepChain {
7406f32e7eSjoerg ChainOfDependences Chain;
7506f32e7eSjoerg
7606f32e7eSjoerg public:
isIdentical(DepChain & Other) const7706f32e7eSjoerg bool isIdentical(DepChain &Other) const {
7806f32e7eSjoerg if (Other.size() != size())
7906f32e7eSjoerg return false;
8006f32e7eSjoerg ChainOfDependences &OtherChain = Other.getChain();
8106f32e7eSjoerg for (int i = 0; i < size(); ++i) {
8206f32e7eSjoerg if (Chain[i] != OtherChain[i])
8306f32e7eSjoerg return false;
8406f32e7eSjoerg }
8506f32e7eSjoerg return true;
8606f32e7eSjoerg }
8706f32e7eSjoerg
getChain()8806f32e7eSjoerg ChainOfDependences &getChain() {
8906f32e7eSjoerg return Chain;
9006f32e7eSjoerg }
9106f32e7eSjoerg
size() const9206f32e7eSjoerg int size() const {
9306f32e7eSjoerg return Chain.size();
9406f32e7eSjoerg }
9506f32e7eSjoerg
clear()9606f32e7eSjoerg void clear() {
9706f32e7eSjoerg Chain.clear();
9806f32e7eSjoerg }
9906f32e7eSjoerg
push_back(Instruction * I)10006f32e7eSjoerg void push_back(Instruction *I) {
10106f32e7eSjoerg Chain.push_back(I);
10206f32e7eSjoerg }
10306f32e7eSjoerg
iterations() const10406f32e7eSjoerg int iterations() const {
10506f32e7eSjoerg return size() - 1;
10606f32e7eSjoerg }
10706f32e7eSjoerg
front() const10806f32e7eSjoerg Instruction *front() const {
10906f32e7eSjoerg return Chain.front();
11006f32e7eSjoerg }
11106f32e7eSjoerg
back() const11206f32e7eSjoerg Instruction *back() const {
11306f32e7eSjoerg return Chain.back();
11406f32e7eSjoerg }
11506f32e7eSjoerg
operator [](const int index)11606f32e7eSjoerg Instruction *&operator[](const int index) {
11706f32e7eSjoerg return Chain[index];
11806f32e7eSjoerg }
11906f32e7eSjoerg
12006f32e7eSjoerg friend raw_ostream &operator<< (raw_ostream &OS, const DepChain &D);
12106f32e7eSjoerg };
12206f32e7eSjoerg
12306f32e7eSjoerg LLVM_ATTRIBUTE_UNUSED
operator <<(raw_ostream & OS,const DepChain & D)12406f32e7eSjoerg raw_ostream &operator<<(raw_ostream &OS, const DepChain &D) {
12506f32e7eSjoerg const ChainOfDependences &CD = D.Chain;
12606f32e7eSjoerg int ChainSize = CD.size();
12706f32e7eSjoerg OS << "**DepChain Start::**\n";
12806f32e7eSjoerg for (int i = 0; i < ChainSize -1; ++i) {
12906f32e7eSjoerg OS << *(CD[i]) << " -->\n";
13006f32e7eSjoerg }
13106f32e7eSjoerg OS << *CD[ChainSize-1] << "\n";
13206f32e7eSjoerg return OS;
13306f32e7eSjoerg }
13406f32e7eSjoerg
13506f32e7eSjoerg struct ReuseValue {
13606f32e7eSjoerg Instruction *Inst2Replace = nullptr;
13706f32e7eSjoerg
13806f32e7eSjoerg // In the new PHI node that we'll construct this is the value that'll be
13906f32e7eSjoerg // used over the backedge. This is the value that gets reused from a
14006f32e7eSjoerg // previous iteration.
14106f32e7eSjoerg Instruction *BackedgeInst = nullptr;
14206f32e7eSjoerg std::map<Instruction *, DepChain *> DepChains;
14306f32e7eSjoerg int Iterations = -1;
14406f32e7eSjoerg
14506f32e7eSjoerg ReuseValue() = default;
14606f32e7eSjoerg
reset__anon172936f50111::ReuseValue14706f32e7eSjoerg void reset() {
14806f32e7eSjoerg Inst2Replace = nullptr;
14906f32e7eSjoerg BackedgeInst = nullptr;
15006f32e7eSjoerg DepChains.clear();
15106f32e7eSjoerg Iterations = -1;
15206f32e7eSjoerg }
isDefined__anon172936f50111::ReuseValue15306f32e7eSjoerg bool isDefined() { return Inst2Replace != nullptr; }
15406f32e7eSjoerg };
15506f32e7eSjoerg
15606f32e7eSjoerg LLVM_ATTRIBUTE_UNUSED
operator <<(raw_ostream & OS,const ReuseValue & RU)15706f32e7eSjoerg raw_ostream &operator<<(raw_ostream &OS, const ReuseValue &RU) {
15806f32e7eSjoerg OS << "** ReuseValue ***\n";
15906f32e7eSjoerg OS << "Instruction to Replace: " << *(RU.Inst2Replace) << "\n";
16006f32e7eSjoerg OS << "Backedge Instruction: " << *(RU.BackedgeInst) << "\n";
16106f32e7eSjoerg return OS;
16206f32e7eSjoerg }
16306f32e7eSjoerg
164*da58b97aSjoerg class HexagonVectorLoopCarriedReuseLegacyPass : public LoopPass {
16506f32e7eSjoerg public:
16606f32e7eSjoerg static char ID;
16706f32e7eSjoerg
HexagonVectorLoopCarriedReuseLegacyPass()168*da58b97aSjoerg explicit HexagonVectorLoopCarriedReuseLegacyPass() : LoopPass(ID) {
16906f32e7eSjoerg PassRegistry *PR = PassRegistry::getPassRegistry();
170*da58b97aSjoerg initializeHexagonVectorLoopCarriedReuseLegacyPassPass(*PR);
17106f32e7eSjoerg }
17206f32e7eSjoerg
getPassName() const17306f32e7eSjoerg StringRef getPassName() const override {
17406f32e7eSjoerg return "Hexagon-specific loop carried reuse for HVX vectors";
17506f32e7eSjoerg }
17606f32e7eSjoerg
getAnalysisUsage(AnalysisUsage & AU) const17706f32e7eSjoerg void getAnalysisUsage(AnalysisUsage &AU) const override {
17806f32e7eSjoerg AU.addRequiredID(LoopSimplifyID);
17906f32e7eSjoerg AU.addRequiredID(LCSSAID);
18006f32e7eSjoerg AU.addPreservedID(LCSSAID);
18106f32e7eSjoerg AU.setPreservesCFG();
18206f32e7eSjoerg }
18306f32e7eSjoerg
18406f32e7eSjoerg bool runOnLoop(Loop *L, LPPassManager &LPM) override;
185*da58b97aSjoerg };
186*da58b97aSjoerg
187*da58b97aSjoerg class HexagonVectorLoopCarriedReuse {
188*da58b97aSjoerg public:
HexagonVectorLoopCarriedReuse(Loop * L)189*da58b97aSjoerg HexagonVectorLoopCarriedReuse(Loop *L) : CurLoop(L){};
190*da58b97aSjoerg
191*da58b97aSjoerg bool run();
19206f32e7eSjoerg
19306f32e7eSjoerg private:
19406f32e7eSjoerg SetVector<DepChain *> Dependences;
19506f32e7eSjoerg std::set<Instruction *> ReplacedInsts;
19606f32e7eSjoerg Loop *CurLoop;
19706f32e7eSjoerg ReuseValue ReuseCandidate;
19806f32e7eSjoerg
19906f32e7eSjoerg bool doVLCR();
20006f32e7eSjoerg void findLoopCarriedDeps();
20106f32e7eSjoerg void findValueToReuse();
20206f32e7eSjoerg void findDepChainFromPHI(Instruction *I, DepChain &D);
20306f32e7eSjoerg void reuseValue();
20406f32e7eSjoerg Value *findValueInBlock(Value *Op, BasicBlock *BB);
20506f32e7eSjoerg DepChain *getDepChainBtwn(Instruction *I1, Instruction *I2, int Iters);
20606f32e7eSjoerg bool isEquivalentOperation(Instruction *I1, Instruction *I2);
20706f32e7eSjoerg bool canReplace(Instruction *I);
20806f32e7eSjoerg bool isCallInstCommutative(CallInst *C);
20906f32e7eSjoerg };
21006f32e7eSjoerg
21106f32e7eSjoerg } // end anonymous namespace
21206f32e7eSjoerg
213*da58b97aSjoerg char HexagonVectorLoopCarriedReuseLegacyPass::ID = 0;
21406f32e7eSjoerg
215*da58b97aSjoerg INITIALIZE_PASS_BEGIN(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
216*da58b97aSjoerg "Hexagon-specific predictive commoning for HVX vectors",
217*da58b97aSjoerg false, false)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)21806f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
21906f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
220*da58b97aSjoerg INITIALIZE_PASS_END(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
221*da58b97aSjoerg "Hexagon-specific predictive commoning for HVX vectors",
222*da58b97aSjoerg false, false)
22306f32e7eSjoerg
224*da58b97aSjoerg PreservedAnalyses
225*da58b97aSjoerg HexagonVectorLoopCarriedReusePass::run(Loop &L, LoopAnalysisManager &LAM,
226*da58b97aSjoerg LoopStandardAnalysisResults &AR,
227*da58b97aSjoerg LPMUpdater &U) {
228*da58b97aSjoerg HexagonVectorLoopCarriedReuse Vlcr(&L);
229*da58b97aSjoerg if (!Vlcr.run())
230*da58b97aSjoerg return PreservedAnalyses::all();
231*da58b97aSjoerg PreservedAnalyses PA;
232*da58b97aSjoerg PA.preserveSet<CFGAnalyses>();
233*da58b97aSjoerg return PA;
234*da58b97aSjoerg }
235*da58b97aSjoerg
runOnLoop(Loop * L,LPPassManager & LPM)236*da58b97aSjoerg bool HexagonVectorLoopCarriedReuseLegacyPass::runOnLoop(Loop *L,
237*da58b97aSjoerg LPPassManager &LPM) {
23806f32e7eSjoerg if (skipLoop(L))
23906f32e7eSjoerg return false;
240*da58b97aSjoerg HexagonVectorLoopCarriedReuse Vlcr(L);
241*da58b97aSjoerg return Vlcr.run();
242*da58b97aSjoerg }
24306f32e7eSjoerg
run()244*da58b97aSjoerg bool HexagonVectorLoopCarriedReuse::run() {
245*da58b97aSjoerg if (!CurLoop->getLoopPreheader())
24606f32e7eSjoerg return false;
24706f32e7eSjoerg
24806f32e7eSjoerg // Work only on innermost loops.
249*da58b97aSjoerg if (!CurLoop->getSubLoops().empty())
25006f32e7eSjoerg return false;
25106f32e7eSjoerg
25206f32e7eSjoerg // Work only on single basic blocks loops.
253*da58b97aSjoerg if (CurLoop->getNumBlocks() != 1)
25406f32e7eSjoerg return false;
25506f32e7eSjoerg
25606f32e7eSjoerg return doVLCR();
25706f32e7eSjoerg }
25806f32e7eSjoerg
isCallInstCommutative(CallInst * C)25906f32e7eSjoerg bool HexagonVectorLoopCarriedReuse::isCallInstCommutative(CallInst *C) {
26006f32e7eSjoerg switch (C->getCalledFunction()->getIntrinsicID()) {
26106f32e7eSjoerg case Intrinsic::hexagon_V6_vaddb:
26206f32e7eSjoerg case Intrinsic::hexagon_V6_vaddb_128B:
26306f32e7eSjoerg case Intrinsic::hexagon_V6_vaddh:
26406f32e7eSjoerg case Intrinsic::hexagon_V6_vaddh_128B:
26506f32e7eSjoerg case Intrinsic::hexagon_V6_vaddw:
26606f32e7eSjoerg case Intrinsic::hexagon_V6_vaddw_128B:
26706f32e7eSjoerg case Intrinsic::hexagon_V6_vaddubh:
26806f32e7eSjoerg case Intrinsic::hexagon_V6_vaddubh_128B:
26906f32e7eSjoerg case Intrinsic::hexagon_V6_vadduhw:
27006f32e7eSjoerg case Intrinsic::hexagon_V6_vadduhw_128B:
27106f32e7eSjoerg case Intrinsic::hexagon_V6_vaddhw:
27206f32e7eSjoerg case Intrinsic::hexagon_V6_vaddhw_128B:
27306f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxb:
27406f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxb_128B:
27506f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxh:
27606f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxh_128B:
27706f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxw:
27806f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxw_128B:
27906f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxub:
28006f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxub_128B:
28106f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxuh:
28206f32e7eSjoerg case Intrinsic::hexagon_V6_vmaxuh_128B:
28306f32e7eSjoerg case Intrinsic::hexagon_V6_vminub:
28406f32e7eSjoerg case Intrinsic::hexagon_V6_vminub_128B:
28506f32e7eSjoerg case Intrinsic::hexagon_V6_vminuh:
28606f32e7eSjoerg case Intrinsic::hexagon_V6_vminuh_128B:
28706f32e7eSjoerg case Intrinsic::hexagon_V6_vminb:
28806f32e7eSjoerg case Intrinsic::hexagon_V6_vminb_128B:
28906f32e7eSjoerg case Intrinsic::hexagon_V6_vminh:
29006f32e7eSjoerg case Intrinsic::hexagon_V6_vminh_128B:
29106f32e7eSjoerg case Intrinsic::hexagon_V6_vminw:
29206f32e7eSjoerg case Intrinsic::hexagon_V6_vminw_128B:
29306f32e7eSjoerg case Intrinsic::hexagon_V6_vmpyub:
29406f32e7eSjoerg case Intrinsic::hexagon_V6_vmpyub_128B:
29506f32e7eSjoerg case Intrinsic::hexagon_V6_vmpyuh:
29606f32e7eSjoerg case Intrinsic::hexagon_V6_vmpyuh_128B:
29706f32e7eSjoerg case Intrinsic::hexagon_V6_vavgub:
29806f32e7eSjoerg case Intrinsic::hexagon_V6_vavgub_128B:
29906f32e7eSjoerg case Intrinsic::hexagon_V6_vavgh:
30006f32e7eSjoerg case Intrinsic::hexagon_V6_vavgh_128B:
30106f32e7eSjoerg case Intrinsic::hexagon_V6_vavguh:
30206f32e7eSjoerg case Intrinsic::hexagon_V6_vavguh_128B:
30306f32e7eSjoerg case Intrinsic::hexagon_V6_vavgw:
30406f32e7eSjoerg case Intrinsic::hexagon_V6_vavgw_128B:
30506f32e7eSjoerg case Intrinsic::hexagon_V6_vavgb:
30606f32e7eSjoerg case Intrinsic::hexagon_V6_vavgb_128B:
30706f32e7eSjoerg case Intrinsic::hexagon_V6_vavguw:
30806f32e7eSjoerg case Intrinsic::hexagon_V6_vavguw_128B:
30906f32e7eSjoerg case Intrinsic::hexagon_V6_vabsdiffh:
31006f32e7eSjoerg case Intrinsic::hexagon_V6_vabsdiffh_128B:
31106f32e7eSjoerg case Intrinsic::hexagon_V6_vabsdiffub:
31206f32e7eSjoerg case Intrinsic::hexagon_V6_vabsdiffub_128B:
31306f32e7eSjoerg case Intrinsic::hexagon_V6_vabsdiffuh:
31406f32e7eSjoerg case Intrinsic::hexagon_V6_vabsdiffuh_128B:
31506f32e7eSjoerg case Intrinsic::hexagon_V6_vabsdiffw:
31606f32e7eSjoerg case Intrinsic::hexagon_V6_vabsdiffw_128B:
31706f32e7eSjoerg return true;
31806f32e7eSjoerg default:
31906f32e7eSjoerg return false;
32006f32e7eSjoerg }
32106f32e7eSjoerg }
32206f32e7eSjoerg
isEquivalentOperation(Instruction * I1,Instruction * I2)32306f32e7eSjoerg bool HexagonVectorLoopCarriedReuse::isEquivalentOperation(Instruction *I1,
32406f32e7eSjoerg Instruction *I2) {
32506f32e7eSjoerg if (!I1->isSameOperationAs(I2))
32606f32e7eSjoerg return false;
32706f32e7eSjoerg // This check is in place specifically for intrinsics. isSameOperationAs will
32806f32e7eSjoerg // return two for any two hexagon intrinsics because they are essentially the
32906f32e7eSjoerg // same instruciton (CallInst). We need to scratch the surface to see if they
33006f32e7eSjoerg // are calls to the same function.
33106f32e7eSjoerg if (CallInst *C1 = dyn_cast<CallInst>(I1)) {
33206f32e7eSjoerg if (CallInst *C2 = dyn_cast<CallInst>(I2)) {
33306f32e7eSjoerg if (C1->getCalledFunction() != C2->getCalledFunction())
33406f32e7eSjoerg return false;
33506f32e7eSjoerg }
33606f32e7eSjoerg }
33706f32e7eSjoerg
33806f32e7eSjoerg // If both the Instructions are of Vector Type and any of the element
33906f32e7eSjoerg // is integer constant, check their values too for equivalence.
34006f32e7eSjoerg if (I1->getType()->isVectorTy() && I2->getType()->isVectorTy()) {
34106f32e7eSjoerg unsigned NumOperands = I1->getNumOperands();
34206f32e7eSjoerg for (unsigned i = 0; i < NumOperands; ++i) {
34306f32e7eSjoerg ConstantInt *C1 = dyn_cast<ConstantInt>(I1->getOperand(i));
34406f32e7eSjoerg ConstantInt *C2 = dyn_cast<ConstantInt>(I2->getOperand(i));
34506f32e7eSjoerg if(!C1) continue;
34606f32e7eSjoerg assert(C2);
34706f32e7eSjoerg if (C1->getSExtValue() != C2->getSExtValue())
34806f32e7eSjoerg return false;
34906f32e7eSjoerg }
35006f32e7eSjoerg }
35106f32e7eSjoerg
35206f32e7eSjoerg return true;
35306f32e7eSjoerg }
35406f32e7eSjoerg
canReplace(Instruction * I)35506f32e7eSjoerg bool HexagonVectorLoopCarriedReuse::canReplace(Instruction *I) {
35606f32e7eSjoerg const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
35706f32e7eSjoerg if (!II)
35806f32e7eSjoerg return true;
35906f32e7eSjoerg
36006f32e7eSjoerg switch (II->getIntrinsicID()) {
36106f32e7eSjoerg case Intrinsic::hexagon_V6_hi:
36206f32e7eSjoerg case Intrinsic::hexagon_V6_lo:
36306f32e7eSjoerg case Intrinsic::hexagon_V6_hi_128B:
36406f32e7eSjoerg case Intrinsic::hexagon_V6_lo_128B:
36506f32e7eSjoerg LLVM_DEBUG(dbgs() << "Not considering for reuse: " << *II << "\n");
36606f32e7eSjoerg return false;
36706f32e7eSjoerg default:
36806f32e7eSjoerg return true;
36906f32e7eSjoerg }
37006f32e7eSjoerg }
findValueToReuse()37106f32e7eSjoerg void HexagonVectorLoopCarriedReuse::findValueToReuse() {
37206f32e7eSjoerg for (auto *D : Dependences) {
37306f32e7eSjoerg LLVM_DEBUG(dbgs() << "Processing dependence " << *(D->front()) << "\n");
37406f32e7eSjoerg if (D->iterations() > HexagonVLCRIterationLim) {
37506f32e7eSjoerg LLVM_DEBUG(
37606f32e7eSjoerg dbgs()
37706f32e7eSjoerg << ".. Skipping because number of iterations > than the limit\n");
37806f32e7eSjoerg continue;
37906f32e7eSjoerg }
38006f32e7eSjoerg
38106f32e7eSjoerg PHINode *PN = cast<PHINode>(D->front());
38206f32e7eSjoerg Instruction *BEInst = D->back();
38306f32e7eSjoerg int Iters = D->iterations();
38406f32e7eSjoerg BasicBlock *BB = PN->getParent();
38506f32e7eSjoerg LLVM_DEBUG(dbgs() << "Checking if any uses of " << *PN
38606f32e7eSjoerg << " can be reused\n");
38706f32e7eSjoerg
38806f32e7eSjoerg SmallVector<Instruction *, 4> PNUsers;
38906f32e7eSjoerg for (auto UI = PN->use_begin(), E = PN->use_end(); UI != E; ++UI) {
39006f32e7eSjoerg Use &U = *UI;
39106f32e7eSjoerg Instruction *User = cast<Instruction>(U.getUser());
39206f32e7eSjoerg
39306f32e7eSjoerg if (User->getParent() != BB)
39406f32e7eSjoerg continue;
39506f32e7eSjoerg if (ReplacedInsts.count(User)) {
39606f32e7eSjoerg LLVM_DEBUG(dbgs() << *User
39706f32e7eSjoerg << " has already been replaced. Skipping...\n");
39806f32e7eSjoerg continue;
39906f32e7eSjoerg }
40006f32e7eSjoerg if (isa<PHINode>(User))
40106f32e7eSjoerg continue;
40206f32e7eSjoerg if (User->mayHaveSideEffects())
40306f32e7eSjoerg continue;
40406f32e7eSjoerg if (!canReplace(User))
40506f32e7eSjoerg continue;
40606f32e7eSjoerg
40706f32e7eSjoerg PNUsers.push_back(User);
40806f32e7eSjoerg }
40906f32e7eSjoerg LLVM_DEBUG(dbgs() << PNUsers.size() << " use(s) of the PHI in the block\n");
41006f32e7eSjoerg
41106f32e7eSjoerg // For each interesting use I of PN, find an Instruction BEUser that
41206f32e7eSjoerg // performs the same operation as I on BEInst and whose other operands,
41306f32e7eSjoerg // if any, can also be rematerialized in OtherBB. We stop when we find the
41406f32e7eSjoerg // first such Instruction BEUser. This is because once BEUser is
41506f32e7eSjoerg // rematerialized in OtherBB, we may find more such "fixup" opportunities
41606f32e7eSjoerg // in this block. So, we'll start over again.
41706f32e7eSjoerg for (Instruction *I : PNUsers) {
41806f32e7eSjoerg for (auto UI = BEInst->use_begin(), E = BEInst->use_end(); UI != E;
41906f32e7eSjoerg ++UI) {
42006f32e7eSjoerg Use &U = *UI;
42106f32e7eSjoerg Instruction *BEUser = cast<Instruction>(U.getUser());
42206f32e7eSjoerg
42306f32e7eSjoerg if (BEUser->getParent() != BB)
42406f32e7eSjoerg continue;
42506f32e7eSjoerg if (!isEquivalentOperation(I, BEUser))
42606f32e7eSjoerg continue;
42706f32e7eSjoerg
42806f32e7eSjoerg int NumOperands = I->getNumOperands();
42906f32e7eSjoerg
43006f32e7eSjoerg // Take operands of each PNUser one by one and try to find DepChain
43106f32e7eSjoerg // with every operand of the BEUser. If any of the operands of BEUser
43206f32e7eSjoerg // has DepChain with current operand of the PNUser, break the matcher
43306f32e7eSjoerg // loop. Keep doing this for Every PNUser operand. If PNUser operand
43406f32e7eSjoerg // does not have DepChain with any of the BEUser operand, break the
43506f32e7eSjoerg // outer matcher loop, mark the BEUser as null and reset the ReuseCandidate.
43606f32e7eSjoerg // This ensures that DepChain exist for all the PNUser operand with
43706f32e7eSjoerg // BEUser operand. This also ensures that DepChains are independent of
43806f32e7eSjoerg // the positions in PNUser and BEUser.
43906f32e7eSjoerg std::map<Instruction *, DepChain *> DepChains;
44006f32e7eSjoerg CallInst *C1 = dyn_cast<CallInst>(I);
44106f32e7eSjoerg if ((I && I->isCommutative()) || (C1 && isCallInstCommutative(C1))) {
44206f32e7eSjoerg bool Found = false;
44306f32e7eSjoerg for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
44406f32e7eSjoerg Value *Op = I->getOperand(OpNo);
44506f32e7eSjoerg Instruction *OpInst = dyn_cast<Instruction>(Op);
44606f32e7eSjoerg Found = false;
44706f32e7eSjoerg for (int T = 0; T < NumOperands; ++T) {
44806f32e7eSjoerg Value *BEOp = BEUser->getOperand(T);
44906f32e7eSjoerg Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
45006f32e7eSjoerg if (!OpInst && !BEOpInst) {
45106f32e7eSjoerg if (Op == BEOp) {
45206f32e7eSjoerg Found = true;
45306f32e7eSjoerg break;
45406f32e7eSjoerg }
45506f32e7eSjoerg }
45606f32e7eSjoerg
45706f32e7eSjoerg if ((OpInst && !BEOpInst) || (!OpInst && BEOpInst))
45806f32e7eSjoerg continue;
45906f32e7eSjoerg
46006f32e7eSjoerg DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
46106f32e7eSjoerg
46206f32e7eSjoerg if (D) {
46306f32e7eSjoerg Found = true;
46406f32e7eSjoerg DepChains[OpInst] = D;
46506f32e7eSjoerg break;
46606f32e7eSjoerg }
46706f32e7eSjoerg }
46806f32e7eSjoerg if (!Found) {
46906f32e7eSjoerg BEUser = nullptr;
47006f32e7eSjoerg break;
47106f32e7eSjoerg }
47206f32e7eSjoerg }
47306f32e7eSjoerg } else {
47406f32e7eSjoerg
47506f32e7eSjoerg for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
47606f32e7eSjoerg Value *Op = I->getOperand(OpNo);
47706f32e7eSjoerg Value *BEOp = BEUser->getOperand(OpNo);
47806f32e7eSjoerg
47906f32e7eSjoerg Instruction *OpInst = dyn_cast<Instruction>(Op);
48006f32e7eSjoerg if (!OpInst) {
48106f32e7eSjoerg if (Op == BEOp)
48206f32e7eSjoerg continue;
48306f32e7eSjoerg // Do not allow reuse to occur when the operands may be different
48406f32e7eSjoerg // values.
48506f32e7eSjoerg BEUser = nullptr;
48606f32e7eSjoerg break;
48706f32e7eSjoerg }
48806f32e7eSjoerg
48906f32e7eSjoerg Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
49006f32e7eSjoerg DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
49106f32e7eSjoerg
49206f32e7eSjoerg if (D) {
49306f32e7eSjoerg DepChains[OpInst] = D;
49406f32e7eSjoerg } else {
49506f32e7eSjoerg BEUser = nullptr;
49606f32e7eSjoerg break;
49706f32e7eSjoerg }
49806f32e7eSjoerg }
49906f32e7eSjoerg }
50006f32e7eSjoerg if (BEUser) {
50106f32e7eSjoerg LLVM_DEBUG(dbgs() << "Found Value for reuse.\n");
50206f32e7eSjoerg ReuseCandidate.Inst2Replace = I;
50306f32e7eSjoerg ReuseCandidate.BackedgeInst = BEUser;
50406f32e7eSjoerg ReuseCandidate.DepChains = DepChains;
50506f32e7eSjoerg ReuseCandidate.Iterations = Iters;
50606f32e7eSjoerg return;
50706f32e7eSjoerg }
50806f32e7eSjoerg ReuseCandidate.reset();
50906f32e7eSjoerg }
51006f32e7eSjoerg }
51106f32e7eSjoerg }
51206f32e7eSjoerg ReuseCandidate.reset();
51306f32e7eSjoerg }
51406f32e7eSjoerg
findValueInBlock(Value * Op,BasicBlock * BB)51506f32e7eSjoerg Value *HexagonVectorLoopCarriedReuse::findValueInBlock(Value *Op,
51606f32e7eSjoerg BasicBlock *BB) {
51706f32e7eSjoerg PHINode *PN = dyn_cast<PHINode>(Op);
51806f32e7eSjoerg assert(PN);
51906f32e7eSjoerg Value *ValueInBlock = PN->getIncomingValueForBlock(BB);
52006f32e7eSjoerg return ValueInBlock;
52106f32e7eSjoerg }
52206f32e7eSjoerg
reuseValue()52306f32e7eSjoerg void HexagonVectorLoopCarriedReuse::reuseValue() {
52406f32e7eSjoerg LLVM_DEBUG(dbgs() << ReuseCandidate);
52506f32e7eSjoerg Instruction *Inst2Replace = ReuseCandidate.Inst2Replace;
52606f32e7eSjoerg Instruction *BEInst = ReuseCandidate.BackedgeInst;
52706f32e7eSjoerg int NumOperands = Inst2Replace->getNumOperands();
52806f32e7eSjoerg std::map<Instruction *, DepChain *> &DepChains = ReuseCandidate.DepChains;
52906f32e7eSjoerg int Iterations = ReuseCandidate.Iterations;
53006f32e7eSjoerg BasicBlock *LoopPH = CurLoop->getLoopPreheader();
53106f32e7eSjoerg assert(!DepChains.empty() && "No DepChains");
53206f32e7eSjoerg LLVM_DEBUG(dbgs() << "reuseValue is making the following changes\n");
53306f32e7eSjoerg
53406f32e7eSjoerg SmallVector<Instruction *, 4> InstsInPreheader;
53506f32e7eSjoerg for (int i = 0; i < Iterations; ++i) {
53606f32e7eSjoerg Instruction *InstInPreheader = Inst2Replace->clone();
53706f32e7eSjoerg SmallVector<Value *, 4> Ops;
53806f32e7eSjoerg for (int j = 0; j < NumOperands; ++j) {
53906f32e7eSjoerg Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(j));
54006f32e7eSjoerg if (!I)
54106f32e7eSjoerg continue;
54206f32e7eSjoerg // Get the DepChain corresponding to this operand.
54306f32e7eSjoerg DepChain &D = *DepChains[I];
54406f32e7eSjoerg // Get the PHI for the iteration number and find
54506f32e7eSjoerg // the incoming value from the Loop Preheader for
54606f32e7eSjoerg // that PHI.
54706f32e7eSjoerg Value *ValInPreheader = findValueInBlock(D[i], LoopPH);
54806f32e7eSjoerg InstInPreheader->setOperand(j, ValInPreheader);
54906f32e7eSjoerg }
55006f32e7eSjoerg InstsInPreheader.push_back(InstInPreheader);
55106f32e7eSjoerg InstInPreheader->setName(Inst2Replace->getName() + ".hexagon.vlcr");
55206f32e7eSjoerg InstInPreheader->insertBefore(LoopPH->getTerminator());
55306f32e7eSjoerg LLVM_DEBUG(dbgs() << "Added " << *InstInPreheader << " to "
55406f32e7eSjoerg << LoopPH->getName() << "\n");
55506f32e7eSjoerg }
55606f32e7eSjoerg BasicBlock *BB = BEInst->getParent();
55706f32e7eSjoerg IRBuilder<> IRB(BB);
55806f32e7eSjoerg IRB.SetInsertPoint(BB->getFirstNonPHI());
55906f32e7eSjoerg Value *BEVal = BEInst;
56006f32e7eSjoerg PHINode *NewPhi;
56106f32e7eSjoerg for (int i = Iterations-1; i >=0 ; --i) {
56206f32e7eSjoerg Instruction *InstInPreheader = InstsInPreheader[i];
56306f32e7eSjoerg NewPhi = IRB.CreatePHI(InstInPreheader->getType(), 2);
56406f32e7eSjoerg NewPhi->addIncoming(InstInPreheader, LoopPH);
56506f32e7eSjoerg NewPhi->addIncoming(BEVal, BB);
56606f32e7eSjoerg LLVM_DEBUG(dbgs() << "Adding " << *NewPhi << " to " << BB->getName()
56706f32e7eSjoerg << "\n");
56806f32e7eSjoerg BEVal = NewPhi;
56906f32e7eSjoerg }
57006f32e7eSjoerg // We are in LCSSA form. So, a value defined inside the Loop is used only
57106f32e7eSjoerg // inside the loop. So, the following is safe.
57206f32e7eSjoerg Inst2Replace->replaceAllUsesWith(NewPhi);
57306f32e7eSjoerg ReplacedInsts.insert(Inst2Replace);
57406f32e7eSjoerg ++HexagonNumVectorLoopCarriedReuse;
57506f32e7eSjoerg }
57606f32e7eSjoerg
doVLCR()57706f32e7eSjoerg bool HexagonVectorLoopCarriedReuse::doVLCR() {
57806f32e7eSjoerg assert(CurLoop->getSubLoops().empty() &&
57906f32e7eSjoerg "Can do VLCR on the innermost loop only");
58006f32e7eSjoerg assert((CurLoop->getNumBlocks() == 1) &&
58106f32e7eSjoerg "Can do VLCR only on single block loops");
58206f32e7eSjoerg
58306f32e7eSjoerg bool Changed = false;
58406f32e7eSjoerg bool Continue;
58506f32e7eSjoerg
58606f32e7eSjoerg LLVM_DEBUG(dbgs() << "Working on Loop: " << *CurLoop->getHeader() << "\n");
58706f32e7eSjoerg do {
58806f32e7eSjoerg // Reset datastructures.
58906f32e7eSjoerg Dependences.clear();
59006f32e7eSjoerg Continue = false;
59106f32e7eSjoerg
59206f32e7eSjoerg findLoopCarriedDeps();
59306f32e7eSjoerg findValueToReuse();
59406f32e7eSjoerg if (ReuseCandidate.isDefined()) {
59506f32e7eSjoerg reuseValue();
59606f32e7eSjoerg Changed = true;
59706f32e7eSjoerg Continue = true;
59806f32e7eSjoerg }
59906f32e7eSjoerg llvm::for_each(Dependences, std::default_delete<DepChain>());
60006f32e7eSjoerg } while (Continue);
60106f32e7eSjoerg return Changed;
60206f32e7eSjoerg }
60306f32e7eSjoerg
findDepChainFromPHI(Instruction * I,DepChain & D)60406f32e7eSjoerg void HexagonVectorLoopCarriedReuse::findDepChainFromPHI(Instruction *I,
60506f32e7eSjoerg DepChain &D) {
60606f32e7eSjoerg PHINode *PN = dyn_cast<PHINode>(I);
60706f32e7eSjoerg if (!PN) {
60806f32e7eSjoerg D.push_back(I);
60906f32e7eSjoerg return;
61006f32e7eSjoerg } else {
61106f32e7eSjoerg auto NumIncomingValues = PN->getNumIncomingValues();
61206f32e7eSjoerg if (NumIncomingValues != 2) {
61306f32e7eSjoerg D.clear();
61406f32e7eSjoerg return;
61506f32e7eSjoerg }
61606f32e7eSjoerg
61706f32e7eSjoerg BasicBlock *BB = PN->getParent();
61806f32e7eSjoerg if (BB != CurLoop->getHeader()) {
61906f32e7eSjoerg D.clear();
62006f32e7eSjoerg return;
62106f32e7eSjoerg }
62206f32e7eSjoerg
62306f32e7eSjoerg Value *BEVal = PN->getIncomingValueForBlock(BB);
62406f32e7eSjoerg Instruction *BEInst = dyn_cast<Instruction>(BEVal);
62506f32e7eSjoerg // This is a single block loop with a preheader, so at least
62606f32e7eSjoerg // one value should come over the backedge.
62706f32e7eSjoerg assert(BEInst && "There should be a value over the backedge");
62806f32e7eSjoerg
62906f32e7eSjoerg Value *PreHdrVal =
63006f32e7eSjoerg PN->getIncomingValueForBlock(CurLoop->getLoopPreheader());
63106f32e7eSjoerg if(!PreHdrVal || !isa<Instruction>(PreHdrVal)) {
63206f32e7eSjoerg D.clear();
63306f32e7eSjoerg return;
63406f32e7eSjoerg }
63506f32e7eSjoerg D.push_back(PN);
63606f32e7eSjoerg findDepChainFromPHI(BEInst, D);
63706f32e7eSjoerg }
63806f32e7eSjoerg }
63906f32e7eSjoerg
getDepChainBtwn(Instruction * I1,Instruction * I2,int Iters)64006f32e7eSjoerg DepChain *HexagonVectorLoopCarriedReuse::getDepChainBtwn(Instruction *I1,
64106f32e7eSjoerg Instruction *I2,
64206f32e7eSjoerg int Iters) {
64306f32e7eSjoerg for (auto *D : Dependences) {
64406f32e7eSjoerg if (D->front() == I1 && D->back() == I2 && D->iterations() == Iters)
64506f32e7eSjoerg return D;
64606f32e7eSjoerg }
64706f32e7eSjoerg return nullptr;
64806f32e7eSjoerg }
64906f32e7eSjoerg
findLoopCarriedDeps()65006f32e7eSjoerg void HexagonVectorLoopCarriedReuse::findLoopCarriedDeps() {
65106f32e7eSjoerg BasicBlock *BB = CurLoop->getHeader();
65206f32e7eSjoerg for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) {
65306f32e7eSjoerg auto *PN = cast<PHINode>(I);
65406f32e7eSjoerg if (!isa<VectorType>(PN->getType()))
65506f32e7eSjoerg continue;
65606f32e7eSjoerg
65706f32e7eSjoerg DepChain *D = new DepChain();
65806f32e7eSjoerg findDepChainFromPHI(PN, *D);
65906f32e7eSjoerg if (D->size() != 0)
66006f32e7eSjoerg Dependences.insert(D);
66106f32e7eSjoerg else
66206f32e7eSjoerg delete D;
66306f32e7eSjoerg }
66406f32e7eSjoerg LLVM_DEBUG(dbgs() << "Found " << Dependences.size() << " dependences\n");
66506f32e7eSjoerg LLVM_DEBUG(for (size_t i = 0; i < Dependences.size();
66606f32e7eSjoerg ++i) { dbgs() << *Dependences[i] << "\n"; });
66706f32e7eSjoerg }
66806f32e7eSjoerg
createHexagonVectorLoopCarriedReuseLegacyPass()669*da58b97aSjoerg Pass *llvm::createHexagonVectorLoopCarriedReuseLegacyPass() {
670*da58b97aSjoerg return new HexagonVectorLoopCarriedReuseLegacyPass();
67106f32e7eSjoerg }
672