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