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