llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp

   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
  49 using namespace llvm;
  50
  51 #define DEBUG_TYPE "hexagon-vlcr"
  52
  53 STATISTIC(HexagonNumVectorLoopCarriedReuse,
  54           "Number of values that were reused from a previous iteration.");
  55
  56 static cl::opt<int> HexagonVLCRIterationLim("hexagon-vlcr-iteration-lim",
  57     cl::Hidden,
  58     cl::desc("Maximum distance of loop carried dependences that are handled"),
  59     cl::init(2), cl::ZeroOrMore);
  60
  61 namespace llvm {
  62
  63 void initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PassRegistry &);
  64 Pass *createHexagonVectorLoopCarriedReuseLegacyPass();
  65
  66 } // end namespace llvm
  67
  68 namespace {
  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(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(LoopSimplifyID);
 179       AU.addRequiredID(LCSSAID);
 180       AU.addPreservedID(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
 213 char HexagonVectorLoopCarriedReuseLegacyPass::ID = 0;
 214
 215 INITIALIZE_PASS_BEGIN(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
 216                       "Hexagon-specific predictive commoning for HVX vectors",
 217                       false, false)
 218 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 219 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
 220 INITIALIZE_PASS_END(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",
 221                     "Hexagon-specific predictive commoning for HVX vectors",
 222                     false, false)
 223
 224 PreservedAnalyses
 225 HexagonVectorLoopCarriedReusePass::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
 236 bool HexagonVectorLoopCarriedReuseLegacyPass::runOnLoop(Loop *L,
 237                                                         LPPassManager &LPM) {
 238   if (skipLoop(L))
 239     return false;
 240   HexagonVectorLoopCarriedReuse Vlcr(L);
 241   return Vlcr.run();
 242 }
 243
 244 bool 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
 259 bool 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
 323 bool HexagonVectorLoopCarriedReuse::isEquivalentOperation(Instruction *I1,
 324                                                           Instruction *I2) {
 325   if (!I1->isSameOperationAs(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>(I1)) {
 332     if (CallInst *C2 = dyn_cast<CallInst>(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>(I1->getOperand(i));
 344       ConstantInt *C2 = dyn_cast<ConstantInt>(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
 355 bool HexagonVectorLoopCarriedReuse::canReplace(Instruction *I) {
 356   const IntrinsicInst *II = dyn_cast<IntrinsicInst>(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 }
 371 void 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>(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 (auto UI = PN->use_begin(), E = PN->use_end(); UI != E; ++UI) {
 390       Use &U = *UI;
 391       Instruction *User = cast<Instruction>(U.getUser());
 392
 393       if (User->getParent() != BB)
 394         continue;
 395       if (ReplacedInsts.count(User)) {
 396         LLVM_DEBUG(dbgs() << *User
 397                           << " has already been replaced. Skipping...\n");
 398         continue;
 399       }
 400       if (isa<PHINode>(User))
 401         continue;
 402       if (User->mayHaveSideEffects())
 403         continue;
 404       if (!canReplace(User))
 405         continue;
 406
 407       PNUsers.push_back(User);
 408     }
 409     LLVM_DEBUG(dbgs() << PNUsers.size() << " use(s) of the PHI in the block\n");
 410
 411     // For each interesting use I of PN, find an Instruction BEUser that
 412     // performs the same operation as I on BEInst and whose other operands,
 413     // if any, can also be rematerialized in OtherBB. We stop when we find the
 414     // first such Instruction BEUser. This is because once BEUser is
 415     // rematerialized in OtherBB, we may find more such "fixup" opportunities
 416     // in this block. So, we'll start over again.
 417     for (Instruction *I : PNUsers) {
 418       for (auto UI = BEInst->use_begin(), E = BEInst->use_end(); UI != E;
 419            ++UI) {
 420         Use &U = *UI;
 421         Instruction *BEUser = cast<Instruction>(U.getUser());
 422
 423         if (BEUser->getParent() != BB)
 424           continue;
 425         if (!isEquivalentOperation(I, BEUser))
 426           continue;
 427
 428         int NumOperands = I->getNumOperands();
 429
 430         // Take operands of each PNUser one by one and try to find DepChain
 431         // with every operand of the BEUser. If any of the operands of BEUser
 432         // has DepChain with current operand of the PNUser, break the matcher
 433         // loop. Keep doing this for Every PNUser operand. If PNUser operand
 434         // does not have DepChain with any of the BEUser operand, break the
 435         // outer matcher loop, mark the BEUser as null and reset the ReuseCandidate.
 436         // This ensures that DepChain exist for all the PNUser operand with
 437         // BEUser operand. This also ensures that DepChains are independent of
 438         // the positions in PNUser and BEUser.
 439         std::map<Instruction *, DepChain *> DepChains;
 440         CallInst *C1 = dyn_cast<CallInst>(I);
 441         if ((I && I->isCommutative()) || (C1 && isCallInstCommutative(C1))) {
 442           bool Found = false;
 443           for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
 444             Value *Op = I->getOperand(OpNo);
 445             Instruction *OpInst = dyn_cast<Instruction>(Op);
 446             Found = false;
 447             for (int T = 0; T < NumOperands; ++T) {
 448               Value *BEOp = BEUser->getOperand(T);
 449               Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
 450               if (!OpInst && !BEOpInst) {
 451                 if (Op == BEOp) {
 452                   Found = true;
 453                   break;
 454                 }
 455               }
 456
 457               if ((OpInst && !BEOpInst) || (!OpInst && BEOpInst))
 458                 continue;
 459
 460               DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
 461
 462               if (D) {
 463                 Found = true;
 464                 DepChains[OpInst] = D;
 465                 break;
 466               }
 467             }
 468             if (!Found) {
 469               BEUser = nullptr;
 470               break;
 471             }
 472           }
 473         } else {
 474
 475           for (int OpNo = 0; OpNo < NumOperands; ++OpNo) {
 476             Value *Op = I->getOperand(OpNo);
 477             Value *BEOp = BEUser->getOperand(OpNo);
 478
 479             Instruction *OpInst = dyn_cast<Instruction>(Op);
 480             if (!OpInst) {
 481               if (Op == BEOp)
 482                 continue;
 483               // Do not allow reuse to occur when the operands may be different
 484               // values.
 485               BEUser = nullptr;
 486               break;
 487             }
 488
 489             Instruction *BEOpInst = dyn_cast<Instruction>(BEOp);
 490             DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters);
 491
 492             if (D) {
 493               DepChains[OpInst] = D;
 494             } else {
 495               BEUser = nullptr;
 496               break;
 497             }
 498           }
 499         }
 500         if (BEUser) {
 501           LLVM_DEBUG(dbgs() << "Found Value for reuse.\n");
 502           ReuseCandidate.Inst2Replace = I;
 503           ReuseCandidate.BackedgeInst = BEUser;
 504           ReuseCandidate.DepChains = DepChains;
 505           ReuseCandidate.Iterations = Iters;
 506           return;
 507         }
 508         ReuseCandidate.reset();
 509       }
 510     }
 511   }
 512   ReuseCandidate.reset();
 513 }
 514
 515 Value *HexagonVectorLoopCarriedReuse::findValueInBlock(Value *Op,
 516                                                        BasicBlock *BB) {
 517   PHINode *PN = dyn_cast<PHINode>(Op);
 518   assert(PN);
 519   Value *ValueInBlock = PN->getIncomingValueForBlock(BB);
 520   return ValueInBlock;
 521 }
 522
 523 void HexagonVectorLoopCarriedReuse::reuseValue() {
 524   LLVM_DEBUG(dbgs() << ReuseCandidate);
 525   Instruction *Inst2Replace = ReuseCandidate.Inst2Replace;
 526   Instruction *BEInst = ReuseCandidate.BackedgeInst;
 527   int NumOperands = Inst2Replace->getNumOperands();
 528   std::map<Instruction *, DepChain *> &DepChains = ReuseCandidate.DepChains;
 529   int Iterations = ReuseCandidate.Iterations;
 530   BasicBlock *LoopPH = CurLoop->getLoopPreheader();
 531   assert(!DepChains.empty() && "No DepChains");
 532   LLVM_DEBUG(dbgs() << "reuseValue is making the following changes\n");
 533
 534   SmallVector<Instruction *, 4> InstsInPreheader;
 535   for (int i = 0; i < Iterations; ++i) {
 536     Instruction *InstInPreheader = Inst2Replace->clone();
 537     SmallVector<Value *, 4> Ops;
 538     for (int j = 0; j < NumOperands; ++j) {
 539       Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(j));
 540       if (!I)
 541         continue;
 542       // Get the DepChain corresponding to this operand.
 543       DepChain &D = *DepChains[I];
 544       // Get the PHI for the iteration number and find
 545       // the incoming value from the Loop Preheader for
 546       // that PHI.
 547       Value *ValInPreheader = findValueInBlock(D[i], LoopPH);
 548       InstInPreheader->setOperand(j, ValInPreheader);
 549     }
 550     InstsInPreheader.push_back(InstInPreheader);
 551     InstInPreheader->setName(Inst2Replace->getName() + ".hexagon.vlcr");
 552     InstInPreheader->insertBefore(LoopPH->getTerminator());
 553     LLVM_DEBUG(dbgs() << "Added " << *InstInPreheader << " to "
 554                       << LoopPH->getName() << "\n");
 555   }
 556   BasicBlock *BB = BEInst->getParent();
 557   IRBuilder<> IRB(BB);
 558   IRB.SetInsertPoint(BB->getFirstNonPHI());
 559   Value *BEVal = BEInst;
 560   PHINode *NewPhi;
 561   for (int i = Iterations-1; i >=0 ; --i) {
 562     Instruction *InstInPreheader = InstsInPreheader[i];
 563     NewPhi = IRB.CreatePHI(InstInPreheader->getType(), 2);
 564     NewPhi->addIncoming(InstInPreheader, LoopPH);
 565     NewPhi->addIncoming(BEVal, BB);
 566     LLVM_DEBUG(dbgs() << "Adding " << *NewPhi << " to " << BB->getName()
 567                       << "\n");
 568     BEVal = NewPhi;
 569   }
 570   // We are in LCSSA form. So, a value defined inside the Loop is used only
 571   // inside the loop. So, the following is safe.
 572   Inst2Replace->replaceAllUsesWith(NewPhi);
 573   ReplacedInsts.insert(Inst2Replace);
 574   ++HexagonNumVectorLoopCarriedReuse;
 575 }
 576
 577 bool HexagonVectorLoopCarriedReuse::doVLCR() {
 578   assert(CurLoop->getSubLoops().empty() &&
 579          "Can do VLCR on the innermost loop only");
 580   assert((CurLoop->getNumBlocks() == 1) &&
 581          "Can do VLCR only on single block loops");
 582
 583   bool Changed = false;
 584   bool Continue;
 585
 586   LLVM_DEBUG(dbgs() << "Working on Loop: " << *CurLoop->getHeader() << "\n");
 587   do {
 588     // Reset datastructures.
 589     Dependences.clear();
 590     Continue = false;
 591
 592     findLoopCarriedDeps();
 593     findValueToReuse();
 594     if (ReuseCandidate.isDefined()) {
 595       reuseValue();
 596       Changed = true;
 597       Continue = true;
 598     }
 599     llvm::for_each(Dependences, std::default_delete<DepChain>());
 600   } while (Continue);
 601   return Changed;
 602 }
 603
 604 void HexagonVectorLoopCarriedReuse::findDepChainFromPHI(Instruction *I,
 605                                                         DepChain &D) {
 606   PHINode *PN = dyn_cast<PHINode>(I);
 607   if (!PN) {
 608     D.push_back(I);
 609     return;
 610   } else {
 611     auto NumIncomingValues = PN->getNumIncomingValues();
 612     if (NumIncomingValues != 2) {
 613       D.clear();
 614       return;
 615     }
 616
 617     BasicBlock *BB = PN->getParent();
 618     if (BB != CurLoop->getHeader()) {
 619       D.clear();
 620       return;
 621     }
 622
 623     Value *BEVal = PN->getIncomingValueForBlock(BB);
 624     Instruction *BEInst = dyn_cast<Instruction>(BEVal);
 625     // This is a single block loop with a preheader, so at least
 626     // one value should come over the backedge.
 627     assert(BEInst && "There should be a value over the backedge");
 628
 629     Value *PreHdrVal =
 630       PN->getIncomingValueForBlock(CurLoop->getLoopPreheader());
 631     if(!PreHdrVal || !isa<Instruction>(PreHdrVal)) {
 632       D.clear();
 633       return;
 634     }
 635     D.push_back(PN);
 636     findDepChainFromPHI(BEInst, D);
 637   }
 638 }
 639
 640 DepChain *HexagonVectorLoopCarriedReuse::getDepChainBtwn(Instruction *I1,
 641                                                          Instruction *I2,
 642                                                          int Iters) {
 643   for (auto *D : Dependences) {
 644     if (D->front() == I1 && D->back() == I2 && D->iterations() == Iters)
 645       return D;
 646   }
 647   return nullptr;
 648 }
 649
 650 void HexagonVectorLoopCarriedReuse::findLoopCarriedDeps() {
 651   BasicBlock *BB = CurLoop->getHeader();
 652   for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) {
 653     auto *PN = cast<PHINode>(I);
 654     if (!isa<VectorType>(PN->getType()))
 655       continue;
 656
 657     DepChain *D = new DepChain();
 658     findDepChainFromPHI(PN, *D);
 659     if (D->size() != 0)
 660       Dependences.insert(D);
 661     else
 662       delete D;
 663   }
 664   LLVM_DEBUG(dbgs() << "Found " << Dependences.size() << " dependences\n");
 665   LLVM_DEBUG(for (size_t i = 0; i < Dependences.size();
 666                   ++i) { dbgs() << *Dependences[i] << "\n"; });
 667 }
 668
 669 Pass *llvm::createHexagonVectorLoopCarriedReuseLegacyPass() {
 670   return new HexagonVectorLoopCarriedReuseLegacyPass();
 671 }