1 //===- LoopIdiomRecognize.cpp - Loop idiom recognition --------------------===// 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 implements an idiom recognizer that transforms simple loops into a 10 // non-loop form. In cases that this kicks in, it can be a significant 11 // performance win. 12 // 13 // If compiling for code size we avoid idiom recognition if the resulting 14 // code could be larger than the code for the original loop. One way this could 15 // happen is if the loop is not removable after idiom recognition due to the 16 // presence of non-idiom instructions. The initial implementation of the 17 // heuristics applies to idioms in multi-block loops. 18 // 19 //===----------------------------------------------------------------------===// 20 // 21 // TODO List: 22 // 23 // Future loop memory idioms to recognize: 24 // memcmp, strlen, etc. 25 // Future floating point idioms to recognize in -ffast-math mode: 26 // fpowi 27 // Future integer operation idioms to recognize: 28 // ctpop 29 // 30 // Beware that isel's default lowering for ctpop is highly inefficient for 31 // i64 and larger types when i64 is legal and the value has few bits set. It 32 // would be good to enhance isel to emit a loop for ctpop in this case. 33 // 34 // This could recognize common matrix multiplies and dot product idioms and 35 // replace them with calls to BLAS (if linked in??). 36 // 37 //===----------------------------------------------------------------------===// 38 39 #include "llvm/Transforms/Scalar/LoopIdiomRecognize.h" 40 #include "llvm/ADT/APInt.h" 41 #include "llvm/ADT/ArrayRef.h" 42 #include "llvm/ADT/DenseMap.h" 43 #include "llvm/ADT/MapVector.h" 44 #include "llvm/ADT/SetVector.h" 45 #include "llvm/ADT/SmallPtrSet.h" 46 #include "llvm/ADT/SmallVector.h" 47 #include "llvm/ADT/Statistic.h" 48 #include "llvm/ADT/StringRef.h" 49 #include "llvm/Analysis/AliasAnalysis.h" 50 #include "llvm/Analysis/CmpInstAnalysis.h" 51 #include "llvm/Analysis/LoopAccessAnalysis.h" 52 #include "llvm/Analysis/LoopInfo.h" 53 #include "llvm/Analysis/LoopPass.h" 54 #include "llvm/Analysis/MemoryLocation.h" 55 #include "llvm/Analysis/MemorySSA.h" 56 #include "llvm/Analysis/MemorySSAUpdater.h" 57 #include "llvm/Analysis/MustExecute.h" 58 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 59 #include "llvm/Analysis/ScalarEvolution.h" 60 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 61 #include "llvm/Analysis/TargetLibraryInfo.h" 62 #include "llvm/Analysis/TargetTransformInfo.h" 63 #include "llvm/Analysis/ValueTracking.h" 64 #include "llvm/IR/Attributes.h" 65 #include "llvm/IR/BasicBlock.h" 66 #include "llvm/IR/Constant.h" 67 #include "llvm/IR/Constants.h" 68 #include "llvm/IR/DataLayout.h" 69 #include "llvm/IR/DebugLoc.h" 70 #include "llvm/IR/DerivedTypes.h" 71 #include "llvm/IR/Dominators.h" 72 #include "llvm/IR/GlobalValue.h" 73 #include "llvm/IR/GlobalVariable.h" 74 #include "llvm/IR/IRBuilder.h" 75 #include "llvm/IR/InstrTypes.h" 76 #include "llvm/IR/Instruction.h" 77 #include "llvm/IR/Instructions.h" 78 #include "llvm/IR/IntrinsicInst.h" 79 #include "llvm/IR/Intrinsics.h" 80 #include "llvm/IR/LLVMContext.h" 81 #include "llvm/IR/Module.h" 82 #include "llvm/IR/PassManager.h" 83 #include "llvm/IR/PatternMatch.h" 84 #include "llvm/IR/Type.h" 85 #include "llvm/IR/User.h" 86 #include "llvm/IR/Value.h" 87 #include "llvm/IR/ValueHandle.h" 88 #include "llvm/InitializePasses.h" 89 #include "llvm/Pass.h" 90 #include "llvm/Support/Casting.h" 91 #include "llvm/Support/CommandLine.h" 92 #include "llvm/Support/Debug.h" 93 #include "llvm/Support/InstructionCost.h" 94 #include "llvm/Support/raw_ostream.h" 95 #include "llvm/Transforms/Scalar.h" 96 #include "llvm/Transforms/Utils/BuildLibCalls.h" 97 #include "llvm/Transforms/Utils/Local.h" 98 #include "llvm/Transforms/Utils/LoopUtils.h" 99 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 100 #include <algorithm> 101 #include <cassert> 102 #include <cstdint> 103 #include <utility> 104 #include <vector> 105 106 using namespace llvm; 107 108 #define DEBUG_TYPE "loop-idiom" 109 110 STATISTIC(NumMemSet, "Number of memset's formed from loop stores"); 111 STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores"); 112 STATISTIC(NumMemMove, "Number of memmove's formed from loop load+stores"); 113 STATISTIC( 114 NumShiftUntilBitTest, 115 "Number of uncountable loops recognized as 'shift until bitttest' idiom"); 116 STATISTIC(NumShiftUntilZero, 117 "Number of uncountable loops recognized as 'shift until zero' idiom"); 118 119 bool DisableLIRP::All; 120 static cl::opt<bool, true> 121 DisableLIRPAll("disable-" DEBUG_TYPE "-all", 122 cl::desc("Options to disable Loop Idiom Recognize Pass."), 123 cl::location(DisableLIRP::All), cl::init(false), 124 cl::ReallyHidden); 125 126 bool DisableLIRP::Memset; 127 static cl::opt<bool, true> 128 DisableLIRPMemset("disable-" DEBUG_TYPE "-memset", 129 cl::desc("Proceed with loop idiom recognize pass, but do " 130 "not convert loop(s) to memset."), 131 cl::location(DisableLIRP::Memset), cl::init(false), 132 cl::ReallyHidden); 133 134 bool DisableLIRP::Memcpy; 135 static cl::opt<bool, true> 136 DisableLIRPMemcpy("disable-" DEBUG_TYPE "-memcpy", 137 cl::desc("Proceed with loop idiom recognize pass, but do " 138 "not convert loop(s) to memcpy."), 139 cl::location(DisableLIRP::Memcpy), cl::init(false), 140 cl::ReallyHidden); 141 142 static cl::opt<bool> UseLIRCodeSizeHeurs( 143 "use-lir-code-size-heurs", 144 cl::desc("Use loop idiom recognition code size heuristics when compiling" 145 "with -Os/-Oz"), 146 cl::init(true), cl::Hidden); 147 148 namespace { 149 150 class LoopIdiomRecognize { 151 Loop *CurLoop = nullptr; 152 AliasAnalysis *AA; 153 DominatorTree *DT; 154 LoopInfo *LI; 155 ScalarEvolution *SE; 156 TargetLibraryInfo *TLI; 157 const TargetTransformInfo *TTI; 158 const DataLayout *DL; 159 OptimizationRemarkEmitter &ORE; 160 bool ApplyCodeSizeHeuristics; 161 std::unique_ptr<MemorySSAUpdater> MSSAU; 162 163 public: 164 explicit LoopIdiomRecognize(AliasAnalysis *AA, DominatorTree *DT, 165 LoopInfo *LI, ScalarEvolution *SE, 166 TargetLibraryInfo *TLI, 167 const TargetTransformInfo *TTI, MemorySSA *MSSA, 168 const DataLayout *DL, 169 OptimizationRemarkEmitter &ORE) 170 : AA(AA), DT(DT), LI(LI), SE(SE), TLI(TLI), TTI(TTI), DL(DL), ORE(ORE) { 171 if (MSSA) 172 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA); 173 } 174 175 bool runOnLoop(Loop *L); 176 177 private: 178 using StoreList = SmallVector<StoreInst *, 8>; 179 using StoreListMap = MapVector<Value *, StoreList>; 180 181 StoreListMap StoreRefsForMemset; 182 StoreListMap StoreRefsForMemsetPattern; 183 StoreList StoreRefsForMemcpy; 184 bool HasMemset; 185 bool HasMemsetPattern; 186 bool HasMemcpy; 187 188 /// Return code for isLegalStore() 189 enum LegalStoreKind { 190 None = 0, 191 Memset, 192 MemsetPattern, 193 Memcpy, 194 UnorderedAtomicMemcpy, 195 DontUse // Dummy retval never to be used. Allows catching errors in retval 196 // handling. 197 }; 198 199 /// \name Countable Loop Idiom Handling 200 /// @{ 201 202 bool runOnCountableLoop(); 203 bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount, 204 SmallVectorImpl<BasicBlock *> &ExitBlocks); 205 206 void collectStores(BasicBlock *BB); 207 LegalStoreKind isLegalStore(StoreInst *SI); 208 enum class ForMemset { No, Yes }; 209 bool processLoopStores(SmallVectorImpl<StoreInst *> &SL, const SCEV *BECount, 210 ForMemset For); 211 212 template <typename MemInst> 213 bool processLoopMemIntrinsic( 214 BasicBlock *BB, 215 bool (LoopIdiomRecognize::*Processor)(MemInst *, const SCEV *), 216 const SCEV *BECount); 217 bool processLoopMemCpy(MemCpyInst *MCI, const SCEV *BECount); 218 bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount); 219 220 bool processLoopStridedStore(Value *DestPtr, const SCEV *StoreSizeSCEV, 221 MaybeAlign StoreAlignment, Value *StoredVal, 222 Instruction *TheStore, 223 SmallPtrSetImpl<Instruction *> &Stores, 224 const SCEVAddRecExpr *Ev, const SCEV *BECount, 225 bool IsNegStride, bool IsLoopMemset = false); 226 bool processLoopStoreOfLoopLoad(StoreInst *SI, const SCEV *BECount); 227 bool processLoopStoreOfLoopLoad(Value *DestPtr, Value *SourcePtr, 228 const SCEV *StoreSize, MaybeAlign StoreAlign, 229 MaybeAlign LoadAlign, Instruction *TheStore, 230 Instruction *TheLoad, 231 const SCEVAddRecExpr *StoreEv, 232 const SCEVAddRecExpr *LoadEv, 233 const SCEV *BECount); 234 bool avoidLIRForMultiBlockLoop(bool IsMemset = false, 235 bool IsLoopMemset = false); 236 237 /// @} 238 /// \name Noncountable Loop Idiom Handling 239 /// @{ 240 241 bool runOnNoncountableLoop(); 242 243 bool recognizePopcount(); 244 void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst, 245 PHINode *CntPhi, Value *Var); 246 bool recognizeAndInsertFFS(); /// Find First Set: ctlz or cttz 247 void transformLoopToCountable(Intrinsic::ID IntrinID, BasicBlock *PreCondBB, 248 Instruction *CntInst, PHINode *CntPhi, 249 Value *Var, Instruction *DefX, 250 const DebugLoc &DL, bool ZeroCheck, 251 bool IsCntPhiUsedOutsideLoop); 252 253 bool recognizeShiftUntilBitTest(); 254 bool recognizeShiftUntilZero(); 255 256 /// @} 257 }; 258 259 class LoopIdiomRecognizeLegacyPass : public LoopPass { 260 public: 261 static char ID; 262 263 explicit LoopIdiomRecognizeLegacyPass() : LoopPass(ID) { 264 initializeLoopIdiomRecognizeLegacyPassPass( 265 *PassRegistry::getPassRegistry()); 266 } 267 268 bool runOnLoop(Loop *L, LPPassManager &LPM) override { 269 if (DisableLIRP::All) 270 return false; 271 272 if (skipLoop(L)) 273 return false; 274 275 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 276 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 277 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 278 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 279 TargetLibraryInfo *TLI = 280 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI( 281 *L->getHeader()->getParent()); 282 const TargetTransformInfo *TTI = 283 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI( 284 *L->getHeader()->getParent()); 285 const DataLayout *DL = &L->getHeader()->getModule()->getDataLayout(); 286 auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>(); 287 MemorySSA *MSSA = nullptr; 288 if (MSSAAnalysis) 289 MSSA = &MSSAAnalysis->getMSSA(); 290 291 // For the old PM, we can't use OptimizationRemarkEmitter as an analysis 292 // pass. Function analyses need to be preserved across loop transformations 293 // but ORE cannot be preserved (see comment before the pass definition). 294 OptimizationRemarkEmitter ORE(L->getHeader()->getParent()); 295 296 LoopIdiomRecognize LIR(AA, DT, LI, SE, TLI, TTI, MSSA, DL, ORE); 297 return LIR.runOnLoop(L); 298 } 299 300 /// This transformation requires natural loop information & requires that 301 /// loop preheaders be inserted into the CFG. 302 void getAnalysisUsage(AnalysisUsage &AU) const override { 303 AU.addRequired<TargetLibraryInfoWrapperPass>(); 304 AU.addRequired<TargetTransformInfoWrapperPass>(); 305 AU.addPreserved<MemorySSAWrapperPass>(); 306 getLoopAnalysisUsage(AU); 307 } 308 }; 309 310 } // end anonymous namespace 311 312 char LoopIdiomRecognizeLegacyPass::ID = 0; 313 314 PreservedAnalyses LoopIdiomRecognizePass::run(Loop &L, LoopAnalysisManager &AM, 315 LoopStandardAnalysisResults &AR, 316 LPMUpdater &) { 317 if (DisableLIRP::All) 318 return PreservedAnalyses::all(); 319 320 const auto *DL = &L.getHeader()->getModule()->getDataLayout(); 321 322 // For the new PM, we also can't use OptimizationRemarkEmitter as an analysis 323 // pass. Function analyses need to be preserved across loop transformations 324 // but ORE cannot be preserved (see comment before the pass definition). 325 OptimizationRemarkEmitter ORE(L.getHeader()->getParent()); 326 327 LoopIdiomRecognize LIR(&AR.AA, &AR.DT, &AR.LI, &AR.SE, &AR.TLI, &AR.TTI, 328 AR.MSSA, DL, ORE); 329 if (!LIR.runOnLoop(&L)) 330 return PreservedAnalyses::all(); 331 332 auto PA = getLoopPassPreservedAnalyses(); 333 if (AR.MSSA) 334 PA.preserve<MemorySSAAnalysis>(); 335 return PA; 336 } 337 338 INITIALIZE_PASS_BEGIN(LoopIdiomRecognizeLegacyPass, "loop-idiom", 339 "Recognize loop idioms", false, false) 340 INITIALIZE_PASS_DEPENDENCY(LoopPass) 341 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 342 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 343 INITIALIZE_PASS_END(LoopIdiomRecognizeLegacyPass, "loop-idiom", 344 "Recognize loop idioms", false, false) 345 346 Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognizeLegacyPass(); } 347 348 static void deleteDeadInstruction(Instruction *I) { 349 I->replaceAllUsesWith(UndefValue::get(I->getType())); 350 I->eraseFromParent(); 351 } 352 353 //===----------------------------------------------------------------------===// 354 // 355 // Implementation of LoopIdiomRecognize 356 // 357 //===----------------------------------------------------------------------===// 358 359 bool LoopIdiomRecognize::runOnLoop(Loop *L) { 360 CurLoop = L; 361 // If the loop could not be converted to canonical form, it must have an 362 // indirectbr in it, just give up. 363 if (!L->getLoopPreheader()) 364 return false; 365 366 // Disable loop idiom recognition if the function's name is a common idiom. 367 StringRef Name = L->getHeader()->getParent()->getName(); 368 if (Name == "memset" || Name == "memcpy") 369 return false; 370 371 // Determine if code size heuristics need to be applied. 372 ApplyCodeSizeHeuristics = 373 L->getHeader()->getParent()->hasOptSize() && UseLIRCodeSizeHeurs; 374 375 HasMemset = TLI->has(LibFunc_memset); 376 HasMemsetPattern = TLI->has(LibFunc_memset_pattern16); 377 HasMemcpy = TLI->has(LibFunc_memcpy); 378 379 if (HasMemset || HasMemsetPattern || HasMemcpy) 380 if (SE->hasLoopInvariantBackedgeTakenCount(L)) 381 return runOnCountableLoop(); 382 383 return runOnNoncountableLoop(); 384 } 385 386 bool LoopIdiomRecognize::runOnCountableLoop() { 387 const SCEV *BECount = SE->getBackedgeTakenCount(CurLoop); 388 assert(!isa<SCEVCouldNotCompute>(BECount) && 389 "runOnCountableLoop() called on a loop without a predictable" 390 "backedge-taken count"); 391 392 // If this loop executes exactly one time, then it should be peeled, not 393 // optimized by this pass. 394 if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount)) 395 if (BECst->getAPInt() == 0) 396 return false; 397 398 SmallVector<BasicBlock *, 8> ExitBlocks; 399 CurLoop->getUniqueExitBlocks(ExitBlocks); 400 401 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F[" 402 << CurLoop->getHeader()->getParent()->getName() 403 << "] Countable Loop %" << CurLoop->getHeader()->getName() 404 << "\n"); 405 406 // The following transforms hoist stores/memsets into the loop pre-header. 407 // Give up if the loop has instructions that may throw. 408 SimpleLoopSafetyInfo SafetyInfo; 409 SafetyInfo.computeLoopSafetyInfo(CurLoop); 410 if (SafetyInfo.anyBlockMayThrow()) 411 return false; 412 413 bool MadeChange = false; 414 415 // Scan all the blocks in the loop that are not in subloops. 416 for (auto *BB : CurLoop->getBlocks()) { 417 // Ignore blocks in subloops. 418 if (LI->getLoopFor(BB) != CurLoop) 419 continue; 420 421 MadeChange |= runOnLoopBlock(BB, BECount, ExitBlocks); 422 } 423 return MadeChange; 424 } 425 426 static APInt getStoreStride(const SCEVAddRecExpr *StoreEv) { 427 const SCEVConstant *ConstStride = cast<SCEVConstant>(StoreEv->getOperand(1)); 428 return ConstStride->getAPInt(); 429 } 430 431 /// getMemSetPatternValue - If a strided store of the specified value is safe to 432 /// turn into a memset_pattern16, return a ConstantArray of 16 bytes that should 433 /// be passed in. Otherwise, return null. 434 /// 435 /// Note that we don't ever attempt to use memset_pattern8 or 4, because these 436 /// just replicate their input array and then pass on to memset_pattern16. 437 static Constant *getMemSetPatternValue(Value *V, const DataLayout *DL) { 438 // FIXME: This could check for UndefValue because it can be merged into any 439 // other valid pattern. 440 441 // If the value isn't a constant, we can't promote it to being in a constant 442 // array. We could theoretically do a store to an alloca or something, but 443 // that doesn't seem worthwhile. 444 Constant *C = dyn_cast<Constant>(V); 445 if (!C) 446 return nullptr; 447 448 // Only handle simple values that are a power of two bytes in size. 449 uint64_t Size = DL->getTypeSizeInBits(V->getType()); 450 if (Size == 0 || (Size & 7) || (Size & (Size - 1))) 451 return nullptr; 452 453 // Don't care enough about darwin/ppc to implement this. 454 if (DL->isBigEndian()) 455 return nullptr; 456 457 // Convert to size in bytes. 458 Size /= 8; 459 460 // TODO: If CI is larger than 16-bytes, we can try slicing it in half to see 461 // if the top and bottom are the same (e.g. for vectors and large integers). 462 if (Size > 16) 463 return nullptr; 464 465 // If the constant is exactly 16 bytes, just use it. 466 if (Size == 16) 467 return C; 468 469 // Otherwise, we'll use an array of the constants. 470 unsigned ArraySize = 16 / Size; 471 ArrayType *AT = ArrayType::get(V->getType(), ArraySize); 472 return ConstantArray::get(AT, std::vector<Constant *>(ArraySize, C)); 473 } 474 475 LoopIdiomRecognize::LegalStoreKind 476 LoopIdiomRecognize::isLegalStore(StoreInst *SI) { 477 // Don't touch volatile stores. 478 if (SI->isVolatile()) 479 return LegalStoreKind::None; 480 // We only want simple or unordered-atomic stores. 481 if (!SI->isUnordered()) 482 return LegalStoreKind::None; 483 484 // Avoid merging nontemporal stores. 485 if (SI->getMetadata(LLVMContext::MD_nontemporal)) 486 return LegalStoreKind::None; 487 488 Value *StoredVal = SI->getValueOperand(); 489 Value *StorePtr = SI->getPointerOperand(); 490 491 // Don't convert stores of non-integral pointer types to memsets (which stores 492 // integers). 493 if (DL->isNonIntegralPointerType(StoredVal->getType()->getScalarType())) 494 return LegalStoreKind::None; 495 496 // Reject stores that are so large that they overflow an unsigned. 497 // When storing out scalable vectors we bail out for now, since the code 498 // below currently only works for constant strides. 499 TypeSize SizeInBits = DL->getTypeSizeInBits(StoredVal->getType()); 500 if (SizeInBits.isScalable() || (SizeInBits.getFixedSize() & 7) || 501 (SizeInBits.getFixedSize() >> 32) != 0) 502 return LegalStoreKind::None; 503 504 // See if the pointer expression is an AddRec like {base,+,1} on the current 505 // loop, which indicates a strided store. If we have something else, it's a 506 // random store we can't handle. 507 const SCEVAddRecExpr *StoreEv = 508 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr)); 509 if (!StoreEv || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine()) 510 return LegalStoreKind::None; 511 512 // Check to see if we have a constant stride. 513 if (!isa<SCEVConstant>(StoreEv->getOperand(1))) 514 return LegalStoreKind::None; 515 516 // See if the store can be turned into a memset. 517 518 // If the stored value is a byte-wise value (like i32 -1), then it may be 519 // turned into a memset of i8 -1, assuming that all the consecutive bytes 520 // are stored. A store of i32 0x01020304 can never be turned into a memset, 521 // but it can be turned into memset_pattern if the target supports it. 522 Value *SplatValue = isBytewiseValue(StoredVal, *DL); 523 524 // Note: memset and memset_pattern on unordered-atomic is yet not supported 525 bool UnorderedAtomic = SI->isUnordered() && !SI->isSimple(); 526 527 // If we're allowed to form a memset, and the stored value would be 528 // acceptable for memset, use it. 529 if (!UnorderedAtomic && HasMemset && SplatValue && !DisableLIRP::Memset && 530 // Verify that the stored value is loop invariant. If not, we can't 531 // promote the memset. 532 CurLoop->isLoopInvariant(SplatValue)) { 533 // It looks like we can use SplatValue. 534 return LegalStoreKind::Memset; 535 } 536 if (!UnorderedAtomic && HasMemsetPattern && !DisableLIRP::Memset && 537 // Don't create memset_pattern16s with address spaces. 538 StorePtr->getType()->getPointerAddressSpace() == 0 && 539 getMemSetPatternValue(StoredVal, DL)) { 540 // It looks like we can use PatternValue! 541 return LegalStoreKind::MemsetPattern; 542 } 543 544 // Otherwise, see if the store can be turned into a memcpy. 545 if (HasMemcpy && !DisableLIRP::Memcpy) { 546 // Check to see if the stride matches the size of the store. If so, then we 547 // know that every byte is touched in the loop. 548 APInt Stride = getStoreStride(StoreEv); 549 unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType()); 550 if (StoreSize != Stride && StoreSize != -Stride) 551 return LegalStoreKind::None; 552 553 // The store must be feeding a non-volatile load. 554 LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand()); 555 556 // Only allow non-volatile loads 557 if (!LI || LI->isVolatile()) 558 return LegalStoreKind::None; 559 // Only allow simple or unordered-atomic loads 560 if (!LI->isUnordered()) 561 return LegalStoreKind::None; 562 563 // See if the pointer expression is an AddRec like {base,+,1} on the current 564 // loop, which indicates a strided load. If we have something else, it's a 565 // random load we can't handle. 566 const SCEVAddRecExpr *LoadEv = 567 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getPointerOperand())); 568 if (!LoadEv || LoadEv->getLoop() != CurLoop || !LoadEv->isAffine()) 569 return LegalStoreKind::None; 570 571 // The store and load must share the same stride. 572 if (StoreEv->getOperand(1) != LoadEv->getOperand(1)) 573 return LegalStoreKind::None; 574 575 // Success. This store can be converted into a memcpy. 576 UnorderedAtomic = UnorderedAtomic || LI->isAtomic(); 577 return UnorderedAtomic ? LegalStoreKind::UnorderedAtomicMemcpy 578 : LegalStoreKind::Memcpy; 579 } 580 // This store can't be transformed into a memset/memcpy. 581 return LegalStoreKind::None; 582 } 583 584 void LoopIdiomRecognize::collectStores(BasicBlock *BB) { 585 StoreRefsForMemset.clear(); 586 StoreRefsForMemsetPattern.clear(); 587 StoreRefsForMemcpy.clear(); 588 for (Instruction &I : *BB) { 589 StoreInst *SI = dyn_cast<StoreInst>(&I); 590 if (!SI) 591 continue; 592 593 // Make sure this is a strided store with a constant stride. 594 switch (isLegalStore(SI)) { 595 case LegalStoreKind::None: 596 // Nothing to do 597 break; 598 case LegalStoreKind::Memset: { 599 // Find the base pointer. 600 Value *Ptr = getUnderlyingObject(SI->getPointerOperand()); 601 StoreRefsForMemset[Ptr].push_back(SI); 602 } break; 603 case LegalStoreKind::MemsetPattern: { 604 // Find the base pointer. 605 Value *Ptr = getUnderlyingObject(SI->getPointerOperand()); 606 StoreRefsForMemsetPattern[Ptr].push_back(SI); 607 } break; 608 case LegalStoreKind::Memcpy: 609 case LegalStoreKind::UnorderedAtomicMemcpy: 610 StoreRefsForMemcpy.push_back(SI); 611 break; 612 default: 613 assert(false && "unhandled return value"); 614 break; 615 } 616 } 617 } 618 619 /// runOnLoopBlock - Process the specified block, which lives in a counted loop 620 /// with the specified backedge count. This block is known to be in the current 621 /// loop and not in any subloops. 622 bool LoopIdiomRecognize::runOnLoopBlock( 623 BasicBlock *BB, const SCEV *BECount, 624 SmallVectorImpl<BasicBlock *> &ExitBlocks) { 625 // We can only promote stores in this block if they are unconditionally 626 // executed in the loop. For a block to be unconditionally executed, it has 627 // to dominate all the exit blocks of the loop. Verify this now. 628 for (BasicBlock *ExitBlock : ExitBlocks) 629 if (!DT->dominates(BB, ExitBlock)) 630 return false; 631 632 bool MadeChange = false; 633 // Look for store instructions, which may be optimized to memset/memcpy. 634 collectStores(BB); 635 636 // Look for a single store or sets of stores with a common base, which can be 637 // optimized into a memset (memset_pattern). The latter most commonly happens 638 // with structs and handunrolled loops. 639 for (auto &SL : StoreRefsForMemset) 640 MadeChange |= processLoopStores(SL.second, BECount, ForMemset::Yes); 641 642 for (auto &SL : StoreRefsForMemsetPattern) 643 MadeChange |= processLoopStores(SL.second, BECount, ForMemset::No); 644 645 // Optimize the store into a memcpy, if it feeds an similarly strided load. 646 for (auto &SI : StoreRefsForMemcpy) 647 MadeChange |= processLoopStoreOfLoopLoad(SI, BECount); 648 649 MadeChange |= processLoopMemIntrinsic<MemCpyInst>( 650 BB, &LoopIdiomRecognize::processLoopMemCpy, BECount); 651 MadeChange |= processLoopMemIntrinsic<MemSetInst>( 652 BB, &LoopIdiomRecognize::processLoopMemSet, BECount); 653 654 return MadeChange; 655 } 656 657 /// See if this store(s) can be promoted to a memset. 658 bool LoopIdiomRecognize::processLoopStores(SmallVectorImpl<StoreInst *> &SL, 659 const SCEV *BECount, ForMemset For) { 660 // Try to find consecutive stores that can be transformed into memsets. 661 SetVector<StoreInst *> Heads, Tails; 662 SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain; 663 664 // Do a quadratic search on all of the given stores and find 665 // all of the pairs of stores that follow each other. 666 SmallVector<unsigned, 16> IndexQueue; 667 for (unsigned i = 0, e = SL.size(); i < e; ++i) { 668 assert(SL[i]->isSimple() && "Expected only non-volatile stores."); 669 670 Value *FirstStoredVal = SL[i]->getValueOperand(); 671 Value *FirstStorePtr = SL[i]->getPointerOperand(); 672 const SCEVAddRecExpr *FirstStoreEv = 673 cast<SCEVAddRecExpr>(SE->getSCEV(FirstStorePtr)); 674 APInt FirstStride = getStoreStride(FirstStoreEv); 675 unsigned FirstStoreSize = DL->getTypeStoreSize(SL[i]->getValueOperand()->getType()); 676 677 // See if we can optimize just this store in isolation. 678 if (FirstStride == FirstStoreSize || -FirstStride == FirstStoreSize) { 679 Heads.insert(SL[i]); 680 continue; 681 } 682 683 Value *FirstSplatValue = nullptr; 684 Constant *FirstPatternValue = nullptr; 685 686 if (For == ForMemset::Yes) 687 FirstSplatValue = isBytewiseValue(FirstStoredVal, *DL); 688 else 689 FirstPatternValue = getMemSetPatternValue(FirstStoredVal, DL); 690 691 assert((FirstSplatValue || FirstPatternValue) && 692 "Expected either splat value or pattern value."); 693 694 IndexQueue.clear(); 695 // If a store has multiple consecutive store candidates, search Stores 696 // array according to the sequence: from i+1 to e, then from i-1 to 0. 697 // This is because usually pairing with immediate succeeding or preceding 698 // candidate create the best chance to find memset opportunity. 699 unsigned j = 0; 700 for (j = i + 1; j < e; ++j) 701 IndexQueue.push_back(j); 702 for (j = i; j > 0; --j) 703 IndexQueue.push_back(j - 1); 704 705 for (auto &k : IndexQueue) { 706 assert(SL[k]->isSimple() && "Expected only non-volatile stores."); 707 Value *SecondStorePtr = SL[k]->getPointerOperand(); 708 const SCEVAddRecExpr *SecondStoreEv = 709 cast<SCEVAddRecExpr>(SE->getSCEV(SecondStorePtr)); 710 APInt SecondStride = getStoreStride(SecondStoreEv); 711 712 if (FirstStride != SecondStride) 713 continue; 714 715 Value *SecondStoredVal = SL[k]->getValueOperand(); 716 Value *SecondSplatValue = nullptr; 717 Constant *SecondPatternValue = nullptr; 718 719 if (For == ForMemset::Yes) 720 SecondSplatValue = isBytewiseValue(SecondStoredVal, *DL); 721 else 722 SecondPatternValue = getMemSetPatternValue(SecondStoredVal, DL); 723 724 assert((SecondSplatValue || SecondPatternValue) && 725 "Expected either splat value or pattern value."); 726 727 if (isConsecutiveAccess(SL[i], SL[k], *DL, *SE, false)) { 728 if (For == ForMemset::Yes) { 729 if (isa<UndefValue>(FirstSplatValue)) 730 FirstSplatValue = SecondSplatValue; 731 if (FirstSplatValue != SecondSplatValue) 732 continue; 733 } else { 734 if (isa<UndefValue>(FirstPatternValue)) 735 FirstPatternValue = SecondPatternValue; 736 if (FirstPatternValue != SecondPatternValue) 737 continue; 738 } 739 Tails.insert(SL[k]); 740 Heads.insert(SL[i]); 741 ConsecutiveChain[SL[i]] = SL[k]; 742 break; 743 } 744 } 745 } 746 747 // We may run into multiple chains that merge into a single chain. We mark the 748 // stores that we transformed so that we don't visit the same store twice. 749 SmallPtrSet<Value *, 16> TransformedStores; 750 bool Changed = false; 751 752 // For stores that start but don't end a link in the chain: 753 for (StoreInst *I : Heads) { 754 if (Tails.count(I)) 755 continue; 756 757 // We found a store instr that starts a chain. Now follow the chain and try 758 // to transform it. 759 SmallPtrSet<Instruction *, 8> AdjacentStores; 760 StoreInst *HeadStore = I; 761 unsigned StoreSize = 0; 762 763 // Collect the chain into a list. 764 while (Tails.count(I) || Heads.count(I)) { 765 if (TransformedStores.count(I)) 766 break; 767 AdjacentStores.insert(I); 768 769 StoreSize += DL->getTypeStoreSize(I->getValueOperand()->getType()); 770 // Move to the next value in the chain. 771 I = ConsecutiveChain[I]; 772 } 773 774 Value *StoredVal = HeadStore->getValueOperand(); 775 Value *StorePtr = HeadStore->getPointerOperand(); 776 const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr)); 777 APInt Stride = getStoreStride(StoreEv); 778 779 // Check to see if the stride matches the size of the stores. If so, then 780 // we know that every byte is touched in the loop. 781 if (StoreSize != Stride && StoreSize != -Stride) 782 continue; 783 784 bool IsNegStride = StoreSize == -Stride; 785 786 Type *IntIdxTy = DL->getIndexType(StorePtr->getType()); 787 const SCEV *StoreSizeSCEV = SE->getConstant(IntIdxTy, StoreSize); 788 if (processLoopStridedStore(StorePtr, StoreSizeSCEV, 789 MaybeAlign(HeadStore->getAlignment()), 790 StoredVal, HeadStore, AdjacentStores, StoreEv, 791 BECount, IsNegStride)) { 792 TransformedStores.insert(AdjacentStores.begin(), AdjacentStores.end()); 793 Changed = true; 794 } 795 } 796 797 return Changed; 798 } 799 800 /// processLoopMemIntrinsic - Template function for calling different processor 801 /// functions based on mem instrinsic type. 802 template <typename MemInst> 803 bool LoopIdiomRecognize::processLoopMemIntrinsic( 804 BasicBlock *BB, 805 bool (LoopIdiomRecognize::*Processor)(MemInst *, const SCEV *), 806 const SCEV *BECount) { 807 bool MadeChange = false; 808 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) { 809 Instruction *Inst = &*I++; 810 // Look for memory instructions, which may be optimized to a larger one. 811 if (MemInst *MI = dyn_cast<MemInst>(Inst)) { 812 WeakTrackingVH InstPtr(&*I); 813 if (!(this->*Processor)(MI, BECount)) 814 continue; 815 MadeChange = true; 816 817 // If processing the instruction invalidated our iterator, start over from 818 // the top of the block. 819 if (!InstPtr) 820 I = BB->begin(); 821 } 822 } 823 return MadeChange; 824 } 825 826 /// processLoopMemCpy - See if this memcpy can be promoted to a large memcpy 827 bool LoopIdiomRecognize::processLoopMemCpy(MemCpyInst *MCI, 828 const SCEV *BECount) { 829 // We can only handle non-volatile memcpys with a constant size. 830 if (MCI->isVolatile() || !isa<ConstantInt>(MCI->getLength())) 831 return false; 832 833 // If we're not allowed to hack on memcpy, we fail. 834 if ((!HasMemcpy && !isa<MemCpyInlineInst>(MCI)) || DisableLIRP::Memcpy) 835 return false; 836 837 Value *Dest = MCI->getDest(); 838 Value *Source = MCI->getSource(); 839 if (!Dest || !Source) 840 return false; 841 842 // See if the load and store pointer expressions are AddRec like {base,+,1} on 843 // the current loop, which indicates a strided load and store. If we have 844 // something else, it's a random load or store we can't handle. 845 const SCEVAddRecExpr *StoreEv = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Dest)); 846 if (!StoreEv || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine()) 847 return false; 848 const SCEVAddRecExpr *LoadEv = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Source)); 849 if (!LoadEv || LoadEv->getLoop() != CurLoop || !LoadEv->isAffine()) 850 return false; 851 852 // Reject memcpys that are so large that they overflow an unsigned. 853 uint64_t SizeInBytes = cast<ConstantInt>(MCI->getLength())->getZExtValue(); 854 if ((SizeInBytes >> 32) != 0) 855 return false; 856 857 // Check if the stride matches the size of the memcpy. If so, then we know 858 // that every byte is touched in the loop. 859 const SCEVConstant *ConstStoreStride = 860 dyn_cast<SCEVConstant>(StoreEv->getOperand(1)); 861 const SCEVConstant *ConstLoadStride = 862 dyn_cast<SCEVConstant>(LoadEv->getOperand(1)); 863 if (!ConstStoreStride || !ConstLoadStride) 864 return false; 865 866 APInt StoreStrideValue = ConstStoreStride->getAPInt(); 867 APInt LoadStrideValue = ConstLoadStride->getAPInt(); 868 // Huge stride value - give up 869 if (StoreStrideValue.getBitWidth() > 64 || LoadStrideValue.getBitWidth() > 64) 870 return false; 871 872 if (SizeInBytes != StoreStrideValue && SizeInBytes != -StoreStrideValue) { 873 ORE.emit([&]() { 874 return OptimizationRemarkMissed(DEBUG_TYPE, "SizeStrideUnequal", MCI) 875 << ore::NV("Inst", "memcpy") << " in " 876 << ore::NV("Function", MCI->getFunction()) 877 << " function will not be hoisted: " 878 << ore::NV("Reason", "memcpy size is not equal to stride"); 879 }); 880 return false; 881 } 882 883 int64_t StoreStrideInt = StoreStrideValue.getSExtValue(); 884 int64_t LoadStrideInt = LoadStrideValue.getSExtValue(); 885 // Check if the load stride matches the store stride. 886 if (StoreStrideInt != LoadStrideInt) 887 return false; 888 889 return processLoopStoreOfLoopLoad( 890 Dest, Source, SE->getConstant(Dest->getType(), SizeInBytes), 891 MCI->getDestAlign(), MCI->getSourceAlign(), MCI, MCI, StoreEv, LoadEv, 892 BECount); 893 } 894 895 /// processLoopMemSet - See if this memset can be promoted to a large memset. 896 bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI, 897 const SCEV *BECount) { 898 // We can only handle non-volatile memsets. 899 if (MSI->isVolatile()) 900 return false; 901 902 // If we're not allowed to hack on memset, we fail. 903 if (!HasMemset || DisableLIRP::Memset) 904 return false; 905 906 Value *Pointer = MSI->getDest(); 907 908 // See if the pointer expression is an AddRec like {base,+,1} on the current 909 // loop, which indicates a strided store. If we have something else, it's a 910 // random store we can't handle. 911 const SCEVAddRecExpr *Ev = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Pointer)); 912 if (!Ev || Ev->getLoop() != CurLoop) 913 return false; 914 if (!Ev->isAffine()) { 915 LLVM_DEBUG(dbgs() << " Pointer is not affine, abort\n"); 916 return false; 917 } 918 919 const SCEV *PointerStrideSCEV = Ev->getOperand(1); 920 const SCEV *MemsetSizeSCEV = SE->getSCEV(MSI->getLength()); 921 if (!PointerStrideSCEV || !MemsetSizeSCEV) 922 return false; 923 924 bool IsNegStride = false; 925 const bool IsConstantSize = isa<ConstantInt>(MSI->getLength()); 926 927 if (IsConstantSize) { 928 // Memset size is constant. 929 // Check if the pointer stride matches the memset size. If so, then 930 // we know that every byte is touched in the loop. 931 LLVM_DEBUG(dbgs() << " memset size is constant\n"); 932 uint64_t SizeInBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 933 const SCEVConstant *ConstStride = dyn_cast<SCEVConstant>(Ev->getOperand(1)); 934 if (!ConstStride) 935 return false; 936 937 APInt Stride = ConstStride->getAPInt(); 938 if (SizeInBytes != Stride && SizeInBytes != -Stride) 939 return false; 940 941 IsNegStride = SizeInBytes == -Stride; 942 } else { 943 // Memset size is non-constant. 944 // Check if the pointer stride matches the memset size. 945 // To be conservative, the pass would not promote pointers that aren't in 946 // address space zero. Also, the pass only handles memset length and stride 947 // that are invariant for the top level loop. 948 LLVM_DEBUG(dbgs() << " memset size is non-constant\n"); 949 if (Pointer->getType()->getPointerAddressSpace() != 0) { 950 LLVM_DEBUG(dbgs() << " pointer is not in address space zero, " 951 << "abort\n"); 952 return false; 953 } 954 if (!SE->isLoopInvariant(MemsetSizeSCEV, CurLoop)) { 955 LLVM_DEBUG(dbgs() << " memset size is not a loop-invariant, " 956 << "abort\n"); 957 return false; 958 } 959 960 // Compare positive direction PointerStrideSCEV with MemsetSizeSCEV 961 IsNegStride = PointerStrideSCEV->isNonConstantNegative(); 962 const SCEV *PositiveStrideSCEV = 963 IsNegStride ? SE->getNegativeSCEV(PointerStrideSCEV) 964 : PointerStrideSCEV; 965 LLVM_DEBUG(dbgs() << " MemsetSizeSCEV: " << *MemsetSizeSCEV << "\n" 966 << " PositiveStrideSCEV: " << *PositiveStrideSCEV 967 << "\n"); 968 969 if (PositiveStrideSCEV != MemsetSizeSCEV) { 970 // TODO: folding can be done to the SCEVs 971 // The folding is to fold expressions that is covered by the loop guard 972 // at loop entry. After the folding, compare again and proceed 973 // optimization if equal. 974 LLVM_DEBUG(dbgs() << " SCEV don't match, abort\n"); 975 return false; 976 } 977 } 978 979 // Verify that the memset value is loop invariant. If not, we can't promote 980 // the memset. 981 Value *SplatValue = MSI->getValue(); 982 if (!SplatValue || !CurLoop->isLoopInvariant(SplatValue)) 983 return false; 984 985 SmallPtrSet<Instruction *, 1> MSIs; 986 MSIs.insert(MSI); 987 return processLoopStridedStore(Pointer, SE->getSCEV(MSI->getLength()), 988 MaybeAlign(MSI->getDestAlignment()), 989 SplatValue, MSI, MSIs, Ev, BECount, 990 IsNegStride, /*IsLoopMemset=*/true); 991 } 992 993 /// mayLoopAccessLocation - Return true if the specified loop might access the 994 /// specified pointer location, which is a loop-strided access. The 'Access' 995 /// argument specifies what the verboten forms of access are (read or write). 996 static bool 997 mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L, 998 const SCEV *BECount, const SCEV *StoreSizeSCEV, 999 AliasAnalysis &AA, 1000 SmallPtrSetImpl<Instruction *> &IgnoredInsts) { 1001 // Get the location that may be stored across the loop. Since the access is 1002 // strided positively through memory, we say that the modified location starts 1003 // at the pointer and has infinite size. 1004 LocationSize AccessSize = LocationSize::afterPointer(); 1005 1006 // If the loop iterates a fixed number of times, we can refine the access size 1007 // to be exactly the size of the memset, which is (BECount+1)*StoreSize 1008 const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount); 1009 const SCEVConstant *ConstSize = dyn_cast<SCEVConstant>(StoreSizeSCEV); 1010 if (BECst && ConstSize) 1011 AccessSize = LocationSize::precise((BECst->getValue()->getZExtValue() + 1) * 1012 ConstSize->getValue()->getZExtValue()); 1013 1014 // TODO: For this to be really effective, we have to dive into the pointer 1015 // operand in the store. Store to &A[i] of 100 will always return may alias 1016 // with store of &A[100], we need to StoreLoc to be "A" with size of 100, 1017 // which will then no-alias a store to &A[100]. 1018 MemoryLocation StoreLoc(Ptr, AccessSize); 1019 1020 for (BasicBlock *B : L->blocks()) 1021 for (Instruction &I : *B) 1022 if (!IgnoredInsts.contains(&I) && 1023 isModOrRefSet( 1024 intersectModRef(AA.getModRefInfo(&I, StoreLoc), Access))) 1025 return true; 1026 return false; 1027 } 1028 1029 // If we have a negative stride, Start refers to the end of the memory location 1030 // we're trying to memset. Therefore, we need to recompute the base pointer, 1031 // which is just Start - BECount*Size. 1032 static const SCEV *getStartForNegStride(const SCEV *Start, const SCEV *BECount, 1033 Type *IntPtr, const SCEV *StoreSizeSCEV, 1034 ScalarEvolution *SE) { 1035 const SCEV *Index = SE->getTruncateOrZeroExtend(BECount, IntPtr); 1036 if (!StoreSizeSCEV->isOne()) { 1037 // index = back edge count * store size 1038 Index = SE->getMulExpr(Index, 1039 SE->getTruncateOrZeroExtend(StoreSizeSCEV, IntPtr), 1040 SCEV::FlagNUW); 1041 } 1042 // base pointer = start - index * store size 1043 return SE->getMinusSCEV(Start, Index); 1044 } 1045 1046 /// Compute trip count from the backedge taken count. 1047 static const SCEV *getTripCount(const SCEV *BECount, Type *IntPtr, 1048 Loop *CurLoop, const DataLayout *DL, 1049 ScalarEvolution *SE) { 1050 const SCEV *TripCountS = nullptr; 1051 // The # stored bytes is (BECount+1). Expand the trip count out to 1052 // pointer size if it isn't already. 1053 // 1054 // If we're going to need to zero extend the BE count, check if we can add 1055 // one to it prior to zero extending without overflow. Provided this is safe, 1056 // it allows better simplification of the +1. 1057 if (DL->getTypeSizeInBits(BECount->getType()) < 1058 DL->getTypeSizeInBits(IntPtr) && 1059 SE->isLoopEntryGuardedByCond( 1060 CurLoop, ICmpInst::ICMP_NE, BECount, 1061 SE->getNegativeSCEV(SE->getOne(BECount->getType())))) { 1062 TripCountS = SE->getZeroExtendExpr( 1063 SE->getAddExpr(BECount, SE->getOne(BECount->getType()), SCEV::FlagNUW), 1064 IntPtr); 1065 } else { 1066 TripCountS = SE->getAddExpr(SE->getTruncateOrZeroExtend(BECount, IntPtr), 1067 SE->getOne(IntPtr), SCEV::FlagNUW); 1068 } 1069 1070 return TripCountS; 1071 } 1072 1073 /// Compute the number of bytes as a SCEV from the backedge taken count. 1074 /// 1075 /// This also maps the SCEV into the provided type and tries to handle the 1076 /// computation in a way that will fold cleanly. 1077 static const SCEV *getNumBytes(const SCEV *BECount, Type *IntPtr, 1078 const SCEV *StoreSizeSCEV, Loop *CurLoop, 1079 const DataLayout *DL, ScalarEvolution *SE) { 1080 const SCEV *TripCountSCEV = getTripCount(BECount, IntPtr, CurLoop, DL, SE); 1081 1082 return SE->getMulExpr(TripCountSCEV, 1083 SE->getTruncateOrZeroExtend(StoreSizeSCEV, IntPtr), 1084 SCEV::FlagNUW); 1085 } 1086 1087 /// processLoopStridedStore - We see a strided store of some value. If we can 1088 /// transform this into a memset or memset_pattern in the loop preheader, do so. 1089 bool LoopIdiomRecognize::processLoopStridedStore( 1090 Value *DestPtr, const SCEV *StoreSizeSCEV, MaybeAlign StoreAlignment, 1091 Value *StoredVal, Instruction *TheStore, 1092 SmallPtrSetImpl<Instruction *> &Stores, const SCEVAddRecExpr *Ev, 1093 const SCEV *BECount, bool IsNegStride, bool IsLoopMemset) { 1094 Value *SplatValue = isBytewiseValue(StoredVal, *DL); 1095 Constant *PatternValue = nullptr; 1096 1097 if (!SplatValue) 1098 PatternValue = getMemSetPatternValue(StoredVal, DL); 1099 1100 assert((SplatValue || PatternValue) && 1101 "Expected either splat value or pattern value."); 1102 1103 // The trip count of the loop and the base pointer of the addrec SCEV is 1104 // guaranteed to be loop invariant, which means that it should dominate the 1105 // header. This allows us to insert code for it in the preheader. 1106 unsigned DestAS = DestPtr->getType()->getPointerAddressSpace(); 1107 BasicBlock *Preheader = CurLoop->getLoopPreheader(); 1108 IRBuilder<> Builder(Preheader->getTerminator()); 1109 SCEVExpander Expander(*SE, *DL, "loop-idiom"); 1110 SCEVExpanderCleaner ExpCleaner(Expander, *DT); 1111 1112 Type *DestInt8PtrTy = Builder.getInt8PtrTy(DestAS); 1113 Type *IntIdxTy = DL->getIndexType(DestPtr->getType()); 1114 1115 bool Changed = false; 1116 const SCEV *Start = Ev->getStart(); 1117 // Handle negative strided loops. 1118 if (IsNegStride) 1119 Start = getStartForNegStride(Start, BECount, IntIdxTy, StoreSizeSCEV, SE); 1120 1121 // TODO: ideally we should still be able to generate memset if SCEV expander 1122 // is taught to generate the dependencies at the latest point. 1123 if (!isSafeToExpand(Start, *SE)) 1124 return Changed; 1125 1126 // Okay, we have a strided store "p[i]" of a splattable value. We can turn 1127 // this into a memset in the loop preheader now if we want. However, this 1128 // would be unsafe to do if there is anything else in the loop that may read 1129 // or write to the aliased location. Check for any overlap by generating the 1130 // base pointer and checking the region. 1131 Value *BasePtr = 1132 Expander.expandCodeFor(Start, DestInt8PtrTy, Preheader->getTerminator()); 1133 1134 // From here on out, conservatively report to the pass manager that we've 1135 // changed the IR, even if we later clean up these added instructions. There 1136 // may be structural differences e.g. in the order of use lists not accounted 1137 // for in just a textual dump of the IR. This is written as a variable, even 1138 // though statically all the places this dominates could be replaced with 1139 // 'true', with the hope that anyone trying to be clever / "more precise" with 1140 // the return value will read this comment, and leave them alone. 1141 Changed = true; 1142 1143 if (mayLoopAccessLocation(BasePtr, ModRefInfo::ModRef, CurLoop, BECount, 1144 StoreSizeSCEV, *AA, Stores)) 1145 return Changed; 1146 1147 if (avoidLIRForMultiBlockLoop(/*IsMemset=*/true, IsLoopMemset)) 1148 return Changed; 1149 1150 // Okay, everything looks good, insert the memset. 1151 1152 const SCEV *NumBytesS = 1153 getNumBytes(BECount, IntIdxTy, StoreSizeSCEV, CurLoop, DL, SE); 1154 1155 // TODO: ideally we should still be able to generate memset if SCEV expander 1156 // is taught to generate the dependencies at the latest point. 1157 if (!isSafeToExpand(NumBytesS, *SE)) 1158 return Changed; 1159 1160 Value *NumBytes = 1161 Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator()); 1162 1163 CallInst *NewCall; 1164 if (SplatValue) { 1165 NewCall = Builder.CreateMemSet(BasePtr, SplatValue, NumBytes, 1166 MaybeAlign(StoreAlignment)); 1167 } else { 1168 // Everything is emitted in default address space 1169 Type *Int8PtrTy = DestInt8PtrTy; 1170 1171 Module *M = TheStore->getModule(); 1172 StringRef FuncName = "memset_pattern16"; 1173 FunctionCallee MSP = M->getOrInsertFunction(FuncName, Builder.getVoidTy(), 1174 Int8PtrTy, Int8PtrTy, IntIdxTy); 1175 inferLibFuncAttributes(M, FuncName, *TLI); 1176 1177 // Otherwise we should form a memset_pattern16. PatternValue is known to be 1178 // an constant array of 16-bytes. Plop the value into a mergable global. 1179 GlobalVariable *GV = new GlobalVariable(*M, PatternValue->getType(), true, 1180 GlobalValue::PrivateLinkage, 1181 PatternValue, ".memset_pattern"); 1182 GV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); // Ok to merge these. 1183 GV->setAlignment(Align(16)); 1184 Value *PatternPtr = ConstantExpr::getBitCast(GV, Int8PtrTy); 1185 NewCall = Builder.CreateCall(MSP, {BasePtr, PatternPtr, NumBytes}); 1186 } 1187 NewCall->setDebugLoc(TheStore->getDebugLoc()); 1188 1189 if (MSSAU) { 1190 MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB( 1191 NewCall, nullptr, NewCall->getParent(), MemorySSA::BeforeTerminator); 1192 MSSAU->insertDef(cast<MemoryDef>(NewMemAcc), true); 1193 } 1194 1195 LLVM_DEBUG(dbgs() << " Formed memset: " << *NewCall << "\n" 1196 << " from store to: " << *Ev << " at: " << *TheStore 1197 << "\n"); 1198 1199 ORE.emit([&]() { 1200 OptimizationRemark R(DEBUG_TYPE, "ProcessLoopStridedStore", 1201 NewCall->getDebugLoc(), Preheader); 1202 R << "Transformed loop-strided store in " 1203 << ore::NV("Function", TheStore->getFunction()) 1204 << " function into a call to " 1205 << ore::NV("NewFunction", NewCall->getCalledFunction()) 1206 << "() intrinsic"; 1207 if (!Stores.empty()) 1208 R << ore::setExtraArgs(); 1209 for (auto *I : Stores) { 1210 R << ore::NV("FromBlock", I->getParent()->getName()) 1211 << ore::NV("ToBlock", Preheader->getName()); 1212 } 1213 return R; 1214 }); 1215 1216 // Okay, the memset has been formed. Zap the original store and anything that 1217 // feeds into it. 1218 for (auto *I : Stores) { 1219 if (MSSAU) 1220 MSSAU->removeMemoryAccess(I, true); 1221 deleteDeadInstruction(I); 1222 } 1223 if (MSSAU && VerifyMemorySSA) 1224 MSSAU->getMemorySSA()->verifyMemorySSA(); 1225 ++NumMemSet; 1226 ExpCleaner.markResultUsed(); 1227 return true; 1228 } 1229 1230 /// If the stored value is a strided load in the same loop with the same stride 1231 /// this may be transformable into a memcpy. This kicks in for stuff like 1232 /// for (i) A[i] = B[i]; 1233 bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI, 1234 const SCEV *BECount) { 1235 assert(SI->isUnordered() && "Expected only non-volatile non-ordered stores."); 1236 1237 Value *StorePtr = SI->getPointerOperand(); 1238 const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr)); 1239 unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType()); 1240 1241 // The store must be feeding a non-volatile load. 1242 LoadInst *LI = cast<LoadInst>(SI->getValueOperand()); 1243 assert(LI->isUnordered() && "Expected only non-volatile non-ordered loads."); 1244 1245 // See if the pointer expression is an AddRec like {base,+,1} on the current 1246 // loop, which indicates a strided load. If we have something else, it's a 1247 // random load we can't handle. 1248 Value *LoadPtr = LI->getPointerOperand(); 1249 const SCEVAddRecExpr *LoadEv = cast<SCEVAddRecExpr>(SE->getSCEV(LoadPtr)); 1250 1251 const SCEV *StoreSizeSCEV = SE->getConstant(StorePtr->getType(), StoreSize); 1252 return processLoopStoreOfLoopLoad(StorePtr, LoadPtr, StoreSizeSCEV, 1253 SI->getAlign(), LI->getAlign(), SI, LI, 1254 StoreEv, LoadEv, BECount); 1255 } 1256 1257 class MemmoveVerifier { 1258 public: 1259 explicit MemmoveVerifier(const Value &LoadBasePtr, const Value &StoreBasePtr, 1260 const DataLayout &DL) 1261 : DL(DL), LoadOff(0), StoreOff(0), 1262 BP1(llvm::GetPointerBaseWithConstantOffset( 1263 LoadBasePtr.stripPointerCasts(), LoadOff, DL)), 1264 BP2(llvm::GetPointerBaseWithConstantOffset( 1265 StoreBasePtr.stripPointerCasts(), StoreOff, DL)), 1266 IsSameObject(BP1 == BP2) {} 1267 1268 bool loadAndStoreMayFormMemmove(unsigned StoreSize, bool IsNegStride, 1269 const Instruction &TheLoad, 1270 bool IsMemCpy) const { 1271 if (IsMemCpy) { 1272 // Ensure that LoadBasePtr is after StoreBasePtr or before StoreBasePtr 1273 // for negative stride. 1274 if ((!IsNegStride && LoadOff <= StoreOff) || 1275 (IsNegStride && LoadOff >= StoreOff)) 1276 return false; 1277 } else { 1278 // Ensure that LoadBasePtr is after StoreBasePtr or before StoreBasePtr 1279 // for negative stride. LoadBasePtr shouldn't overlap with StoreBasePtr. 1280 int64_t LoadSize = 1281 DL.getTypeSizeInBits(TheLoad.getType()).getFixedSize() / 8; 1282 if (BP1 != BP2 || LoadSize != int64_t(StoreSize)) 1283 return false; 1284 if ((!IsNegStride && LoadOff < StoreOff + int64_t(StoreSize)) || 1285 (IsNegStride && LoadOff + LoadSize > StoreOff)) 1286 return false; 1287 } 1288 return true; 1289 } 1290 1291 private: 1292 const DataLayout &DL; 1293 int64_t LoadOff; 1294 int64_t StoreOff; 1295 const Value *BP1; 1296 const Value *BP2; 1297 1298 public: 1299 const bool IsSameObject; 1300 }; 1301 1302 bool LoopIdiomRecognize::processLoopStoreOfLoopLoad( 1303 Value *DestPtr, Value *SourcePtr, const SCEV *StoreSizeSCEV, 1304 MaybeAlign StoreAlign, MaybeAlign LoadAlign, Instruction *TheStore, 1305 Instruction *TheLoad, const SCEVAddRecExpr *StoreEv, 1306 const SCEVAddRecExpr *LoadEv, const SCEV *BECount) { 1307 1308 // FIXME: until llvm.memcpy.inline supports dynamic sizes, we need to 1309 // conservatively bail here, since otherwise we may have to transform 1310 // llvm.memcpy.inline into llvm.memcpy which is illegal. 1311 if (isa<MemCpyInlineInst>(TheStore)) 1312 return false; 1313 1314 // The trip count of the loop and the base pointer of the addrec SCEV is 1315 // guaranteed to be loop invariant, which means that it should dominate the 1316 // header. This allows us to insert code for it in the preheader. 1317 BasicBlock *Preheader = CurLoop->getLoopPreheader(); 1318 IRBuilder<> Builder(Preheader->getTerminator()); 1319 SCEVExpander Expander(*SE, *DL, "loop-idiom"); 1320 1321 SCEVExpanderCleaner ExpCleaner(Expander, *DT); 1322 1323 bool Changed = false; 1324 const SCEV *StrStart = StoreEv->getStart(); 1325 unsigned StrAS = DestPtr->getType()->getPointerAddressSpace(); 1326 Type *IntIdxTy = Builder.getIntNTy(DL->getIndexSizeInBits(StrAS)); 1327 1328 APInt Stride = getStoreStride(StoreEv); 1329 const SCEVConstant *ConstStoreSize = dyn_cast<SCEVConstant>(StoreSizeSCEV); 1330 1331 // TODO: Deal with non-constant size; Currently expect constant store size 1332 assert(ConstStoreSize && "store size is expected to be a constant"); 1333 1334 int64_t StoreSize = ConstStoreSize->getValue()->getZExtValue(); 1335 bool IsNegStride = StoreSize == -Stride; 1336 1337 // Handle negative strided loops. 1338 if (IsNegStride) 1339 StrStart = 1340 getStartForNegStride(StrStart, BECount, IntIdxTy, StoreSizeSCEV, SE); 1341 1342 // Okay, we have a strided store "p[i]" of a loaded value. We can turn 1343 // this into a memcpy in the loop preheader now if we want. However, this 1344 // would be unsafe to do if there is anything else in the loop that may read 1345 // or write the memory region we're storing to. This includes the load that 1346 // feeds the stores. Check for an alias by generating the base address and 1347 // checking everything. 1348 Value *StoreBasePtr = Expander.expandCodeFor( 1349 StrStart, Builder.getInt8PtrTy(StrAS), Preheader->getTerminator()); 1350 1351 // From here on out, conservatively report to the pass manager that we've 1352 // changed the IR, even if we later clean up these added instructions. There 1353 // may be structural differences e.g. in the order of use lists not accounted 1354 // for in just a textual dump of the IR. This is written as a variable, even 1355 // though statically all the places this dominates could be replaced with 1356 // 'true', with the hope that anyone trying to be clever / "more precise" with 1357 // the return value will read this comment, and leave them alone. 1358 Changed = true; 1359 1360 SmallPtrSet<Instruction *, 2> IgnoredInsts; 1361 IgnoredInsts.insert(TheStore); 1362 1363 bool IsMemCpy = isa<MemCpyInst>(TheStore); 1364 const StringRef InstRemark = IsMemCpy ? "memcpy" : "load and store"; 1365 1366 bool LoopAccessStore = 1367 mayLoopAccessLocation(StoreBasePtr, ModRefInfo::ModRef, CurLoop, BECount, 1368 StoreSizeSCEV, *AA, IgnoredInsts); 1369 if (LoopAccessStore) { 1370 // For memmove case it's not enough to guarantee that loop doesn't access 1371 // TheStore and TheLoad. Additionally we need to make sure that TheStore is 1372 // the only user of TheLoad. 1373 if (!TheLoad->hasOneUse()) 1374 return Changed; 1375 IgnoredInsts.insert(TheLoad); 1376 if (mayLoopAccessLocation(StoreBasePtr, ModRefInfo::ModRef, CurLoop, 1377 BECount, StoreSizeSCEV, *AA, IgnoredInsts)) { 1378 ORE.emit([&]() { 1379 return OptimizationRemarkMissed(DEBUG_TYPE, "LoopMayAccessStore", 1380 TheStore) 1381 << ore::NV("Inst", InstRemark) << " in " 1382 << ore::NV("Function", TheStore->getFunction()) 1383 << " function will not be hoisted: " 1384 << ore::NV("Reason", "The loop may access store location"); 1385 }); 1386 return Changed; 1387 } 1388 IgnoredInsts.erase(TheLoad); 1389 } 1390 1391 const SCEV *LdStart = LoadEv->getStart(); 1392 unsigned LdAS = SourcePtr->getType()->getPointerAddressSpace(); 1393 1394 // Handle negative strided loops. 1395 if (IsNegStride) 1396 LdStart = 1397 getStartForNegStride(LdStart, BECount, IntIdxTy, StoreSizeSCEV, SE); 1398 1399 // For a memcpy, we have to make sure that the input array is not being 1400 // mutated by the loop. 1401 Value *LoadBasePtr = Expander.expandCodeFor( 1402 LdStart, Builder.getInt8PtrTy(LdAS), Preheader->getTerminator()); 1403 1404 // If the store is a memcpy instruction, we must check if it will write to 1405 // the load memory locations. So remove it from the ignored stores. 1406 if (IsMemCpy) 1407 IgnoredInsts.erase(TheStore); 1408 MemmoveVerifier Verifier(*LoadBasePtr, *StoreBasePtr, *DL); 1409 if (mayLoopAccessLocation(LoadBasePtr, ModRefInfo::Mod, CurLoop, BECount, 1410 StoreSizeSCEV, *AA, IgnoredInsts)) { 1411 if (!IsMemCpy) { 1412 ORE.emit([&]() { 1413 return OptimizationRemarkMissed(DEBUG_TYPE, "LoopMayAccessLoad", 1414 TheLoad) 1415 << ore::NV("Inst", InstRemark) << " in " 1416 << ore::NV("Function", TheStore->getFunction()) 1417 << " function will not be hoisted: " 1418 << ore::NV("Reason", "The loop may access load location"); 1419 }); 1420 return Changed; 1421 } 1422 // At this point loop may access load only for memcpy in same underlying 1423 // object. If that's not the case bail out. 1424 if (!Verifier.IsSameObject) 1425 return Changed; 1426 } 1427 1428 bool UseMemMove = IsMemCpy ? Verifier.IsSameObject : LoopAccessStore; 1429 if (UseMemMove) 1430 if (!Verifier.loadAndStoreMayFormMemmove(StoreSize, IsNegStride, *TheLoad, 1431 IsMemCpy)) 1432 return Changed; 1433 1434 if (avoidLIRForMultiBlockLoop()) 1435 return Changed; 1436 1437 // Okay, everything is safe, we can transform this! 1438 1439 const SCEV *NumBytesS = 1440 getNumBytes(BECount, IntIdxTy, StoreSizeSCEV, CurLoop, DL, SE); 1441 1442 Value *NumBytes = 1443 Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator()); 1444 1445 CallInst *NewCall = nullptr; 1446 // Check whether to generate an unordered atomic memcpy: 1447 // If the load or store are atomic, then they must necessarily be unordered 1448 // by previous checks. 1449 if (!TheStore->isAtomic() && !TheLoad->isAtomic()) { 1450 if (UseMemMove) 1451 NewCall = Builder.CreateMemMove(StoreBasePtr, StoreAlign, LoadBasePtr, 1452 LoadAlign, NumBytes); 1453 else 1454 NewCall = Builder.CreateMemCpy(StoreBasePtr, StoreAlign, LoadBasePtr, 1455 LoadAlign, NumBytes); 1456 } else { 1457 // For now don't support unordered atomic memmove. 1458 if (UseMemMove) 1459 return Changed; 1460 // We cannot allow unaligned ops for unordered load/store, so reject 1461 // anything where the alignment isn't at least the element size. 1462 assert((StoreAlign.hasValue() && LoadAlign.hasValue()) && 1463 "Expect unordered load/store to have align."); 1464 if (StoreAlign.getValue() < StoreSize || LoadAlign.getValue() < StoreSize) 1465 return Changed; 1466 1467 // If the element.atomic memcpy is not lowered into explicit 1468 // loads/stores later, then it will be lowered into an element-size 1469 // specific lib call. If the lib call doesn't exist for our store size, then 1470 // we shouldn't generate the memcpy. 1471 if (StoreSize > TTI->getAtomicMemIntrinsicMaxElementSize()) 1472 return Changed; 1473 1474 // Create the call. 1475 // Note that unordered atomic loads/stores are *required* by the spec to 1476 // have an alignment but non-atomic loads/stores may not. 1477 NewCall = Builder.CreateElementUnorderedAtomicMemCpy( 1478 StoreBasePtr, StoreAlign.getValue(), LoadBasePtr, LoadAlign.getValue(), 1479 NumBytes, StoreSize); 1480 } 1481 NewCall->setDebugLoc(TheStore->getDebugLoc()); 1482 1483 if (MSSAU) { 1484 MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB( 1485 NewCall, nullptr, NewCall->getParent(), MemorySSA::BeforeTerminator); 1486 MSSAU->insertDef(cast<MemoryDef>(NewMemAcc), true); 1487 } 1488 1489 LLVM_DEBUG(dbgs() << " Formed new call: " << *NewCall << "\n" 1490 << " from load ptr=" << *LoadEv << " at: " << *TheLoad 1491 << "\n" 1492 << " from store ptr=" << *StoreEv << " at: " << *TheStore 1493 << "\n"); 1494 1495 ORE.emit([&]() { 1496 return OptimizationRemark(DEBUG_TYPE, "ProcessLoopStoreOfLoopLoad", 1497 NewCall->getDebugLoc(), Preheader) 1498 << "Formed a call to " 1499 << ore::NV("NewFunction", NewCall->getCalledFunction()) 1500 << "() intrinsic from " << ore::NV("Inst", InstRemark) 1501 << " instruction in " << ore::NV("Function", TheStore->getFunction()) 1502 << " function" 1503 << ore::setExtraArgs() 1504 << ore::NV("FromBlock", TheStore->getParent()->getName()) 1505 << ore::NV("ToBlock", Preheader->getName()); 1506 }); 1507 1508 // Okay, a new call to memcpy/memmove has been formed. Zap the original store 1509 // and anything that feeds into it. 1510 if (MSSAU) 1511 MSSAU->removeMemoryAccess(TheStore, true); 1512 deleteDeadInstruction(TheStore); 1513 if (MSSAU && VerifyMemorySSA) 1514 MSSAU->getMemorySSA()->verifyMemorySSA(); 1515 if (UseMemMove) 1516 ++NumMemMove; 1517 else 1518 ++NumMemCpy; 1519 ExpCleaner.markResultUsed(); 1520 return true; 1521 } 1522 1523 // When compiling for codesize we avoid idiom recognition for a multi-block loop 1524 // unless it is a loop_memset idiom or a memset/memcpy idiom in a nested loop. 1525 // 1526 bool LoopIdiomRecognize::avoidLIRForMultiBlockLoop(bool IsMemset, 1527 bool IsLoopMemset) { 1528 if (ApplyCodeSizeHeuristics && CurLoop->getNumBlocks() > 1) { 1529 if (CurLoop->isOutermost() && (!IsMemset || !IsLoopMemset)) { 1530 LLVM_DEBUG(dbgs() << " " << CurLoop->getHeader()->getParent()->getName() 1531 << " : LIR " << (IsMemset ? "Memset" : "Memcpy") 1532 << " avoided: multi-block top-level loop\n"); 1533 return true; 1534 } 1535 } 1536 1537 return false; 1538 } 1539 1540 bool LoopIdiomRecognize::runOnNoncountableLoop() { 1541 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F[" 1542 << CurLoop->getHeader()->getParent()->getName() 1543 << "] Noncountable Loop %" 1544 << CurLoop->getHeader()->getName() << "\n"); 1545 1546 return recognizePopcount() || recognizeAndInsertFFS() || 1547 recognizeShiftUntilBitTest() || recognizeShiftUntilZero(); 1548 } 1549 1550 /// Check if the given conditional branch is based on the comparison between 1551 /// a variable and zero, and if the variable is non-zero or zero (JmpOnZero is 1552 /// true), the control yields to the loop entry. If the branch matches the 1553 /// behavior, the variable involved in the comparison is returned. This function 1554 /// will be called to see if the precondition and postcondition of the loop are 1555 /// in desirable form. 1556 static Value *matchCondition(BranchInst *BI, BasicBlock *LoopEntry, 1557 bool JmpOnZero = false) { 1558 if (!BI || !BI->isConditional()) 1559 return nullptr; 1560 1561 ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition()); 1562 if (!Cond) 1563 return nullptr; 1564 1565 ConstantInt *CmpZero = dyn_cast<ConstantInt>(Cond->getOperand(1)); 1566 if (!CmpZero || !CmpZero->isZero()) 1567 return nullptr; 1568 1569 BasicBlock *TrueSucc = BI->getSuccessor(0); 1570 BasicBlock *FalseSucc = BI->getSuccessor(1); 1571 if (JmpOnZero) 1572 std::swap(TrueSucc, FalseSucc); 1573 1574 ICmpInst::Predicate Pred = Cond->getPredicate(); 1575 if ((Pred == ICmpInst::ICMP_NE && TrueSucc == LoopEntry) || 1576 (Pred == ICmpInst::ICMP_EQ && FalseSucc == LoopEntry)) 1577 return Cond->getOperand(0); 1578 1579 return nullptr; 1580 } 1581 1582 // Check if the recurrence variable `VarX` is in the right form to create 1583 // the idiom. Returns the value coerced to a PHINode if so. 1584 static PHINode *getRecurrenceVar(Value *VarX, Instruction *DefX, 1585 BasicBlock *LoopEntry) { 1586 auto *PhiX = dyn_cast<PHINode>(VarX); 1587 if (PhiX && PhiX->getParent() == LoopEntry && 1588 (PhiX->getOperand(0) == DefX || PhiX->getOperand(1) == DefX)) 1589 return PhiX; 1590 return nullptr; 1591 } 1592 1593 /// Return true iff the idiom is detected in the loop. 1594 /// 1595 /// Additionally: 1596 /// 1) \p CntInst is set to the instruction counting the population bit. 1597 /// 2) \p CntPhi is set to the corresponding phi node. 1598 /// 3) \p Var is set to the value whose population bits are being counted. 1599 /// 1600 /// The core idiom we are trying to detect is: 1601 /// \code 1602 /// if (x0 != 0) 1603 /// goto loop-exit // the precondition of the loop 1604 /// cnt0 = init-val; 1605 /// do { 1606 /// x1 = phi (x0, x2); 1607 /// cnt1 = phi(cnt0, cnt2); 1608 /// 1609 /// cnt2 = cnt1 + 1; 1610 /// ... 1611 /// x2 = x1 & (x1 - 1); 1612 /// ... 1613 /// } while(x != 0); 1614 /// 1615 /// loop-exit: 1616 /// \endcode 1617 static bool detectPopcountIdiom(Loop *CurLoop, BasicBlock *PreCondBB, 1618 Instruction *&CntInst, PHINode *&CntPhi, 1619 Value *&Var) { 1620 // step 1: Check to see if the look-back branch match this pattern: 1621 // "if (a!=0) goto loop-entry". 1622 BasicBlock *LoopEntry; 1623 Instruction *DefX2, *CountInst; 1624 Value *VarX1, *VarX0; 1625 PHINode *PhiX, *CountPhi; 1626 1627 DefX2 = CountInst = nullptr; 1628 VarX1 = VarX0 = nullptr; 1629 PhiX = CountPhi = nullptr; 1630 LoopEntry = *(CurLoop->block_begin()); 1631 1632 // step 1: Check if the loop-back branch is in desirable form. 1633 { 1634 if (Value *T = matchCondition( 1635 dyn_cast<BranchInst>(LoopEntry->getTerminator()), LoopEntry)) 1636 DefX2 = dyn_cast<Instruction>(T); 1637 else 1638 return false; 1639 } 1640 1641 // step 2: detect instructions corresponding to "x2 = x1 & (x1 - 1)" 1642 { 1643 if (!DefX2 || DefX2->getOpcode() != Instruction::And) 1644 return false; 1645 1646 BinaryOperator *SubOneOp; 1647 1648 if ((SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(0)))) 1649 VarX1 = DefX2->getOperand(1); 1650 else { 1651 VarX1 = DefX2->getOperand(0); 1652 SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(1)); 1653 } 1654 if (!SubOneOp || SubOneOp->getOperand(0) != VarX1) 1655 return false; 1656 1657 ConstantInt *Dec = dyn_cast<ConstantInt>(SubOneOp->getOperand(1)); 1658 if (!Dec || 1659 !((SubOneOp->getOpcode() == Instruction::Sub && Dec->isOne()) || 1660 (SubOneOp->getOpcode() == Instruction::Add && 1661 Dec->isMinusOne()))) { 1662 return false; 1663 } 1664 } 1665 1666 // step 3: Check the recurrence of variable X 1667 PhiX = getRecurrenceVar(VarX1, DefX2, LoopEntry); 1668 if (!PhiX) 1669 return false; 1670 1671 // step 4: Find the instruction which count the population: cnt2 = cnt1 + 1 1672 { 1673 CountInst = nullptr; 1674 for (Instruction &Inst : llvm::make_range( 1675 LoopEntry->getFirstNonPHI()->getIterator(), LoopEntry->end())) { 1676 if (Inst.getOpcode() != Instruction::Add) 1677 continue; 1678 1679 ConstantInt *Inc = dyn_cast<ConstantInt>(Inst.getOperand(1)); 1680 if (!Inc || !Inc->isOne()) 1681 continue; 1682 1683 PHINode *Phi = getRecurrenceVar(Inst.getOperand(0), &Inst, LoopEntry); 1684 if (!Phi) 1685 continue; 1686 1687 // Check if the result of the instruction is live of the loop. 1688 bool LiveOutLoop = false; 1689 for (User *U : Inst.users()) { 1690 if ((cast<Instruction>(U))->getParent() != LoopEntry) { 1691 LiveOutLoop = true; 1692 break; 1693 } 1694 } 1695 1696 if (LiveOutLoop) { 1697 CountInst = &Inst; 1698 CountPhi = Phi; 1699 break; 1700 } 1701 } 1702 1703 if (!CountInst) 1704 return false; 1705 } 1706 1707 // step 5: check if the precondition is in this form: 1708 // "if (x != 0) goto loop-head ; else goto somewhere-we-don't-care;" 1709 { 1710 auto *PreCondBr = dyn_cast<BranchInst>(PreCondBB->getTerminator()); 1711 Value *T = matchCondition(PreCondBr, CurLoop->getLoopPreheader()); 1712 if (T != PhiX->getOperand(0) && T != PhiX->getOperand(1)) 1713 return false; 1714 1715 CntInst = CountInst; 1716 CntPhi = CountPhi; 1717 Var = T; 1718 } 1719 1720 return true; 1721 } 1722 1723 /// Return true if the idiom is detected in the loop. 1724 /// 1725 /// Additionally: 1726 /// 1) \p CntInst is set to the instruction Counting Leading Zeros (CTLZ) 1727 /// or nullptr if there is no such. 1728 /// 2) \p CntPhi is set to the corresponding phi node 1729 /// or nullptr if there is no such. 1730 /// 3) \p Var is set to the value whose CTLZ could be used. 1731 /// 4) \p DefX is set to the instruction calculating Loop exit condition. 1732 /// 1733 /// The core idiom we are trying to detect is: 1734 /// \code 1735 /// if (x0 == 0) 1736 /// goto loop-exit // the precondition of the loop 1737 /// cnt0 = init-val; 1738 /// do { 1739 /// x = phi (x0, x.next); //PhiX 1740 /// cnt = phi(cnt0, cnt.next); 1741 /// 1742 /// cnt.next = cnt + 1; 1743 /// ... 1744 /// x.next = x >> 1; // DefX 1745 /// ... 1746 /// } while(x.next != 0); 1747 /// 1748 /// loop-exit: 1749 /// \endcode 1750 static bool detectShiftUntilZeroIdiom(Loop *CurLoop, const DataLayout &DL, 1751 Intrinsic::ID &IntrinID, Value *&InitX, 1752 Instruction *&CntInst, PHINode *&CntPhi, 1753 Instruction *&DefX) { 1754 BasicBlock *LoopEntry; 1755 Value *VarX = nullptr; 1756 1757 DefX = nullptr; 1758 CntInst = nullptr; 1759 CntPhi = nullptr; 1760 LoopEntry = *(CurLoop->block_begin()); 1761 1762 // step 1: Check if the loop-back branch is in desirable form. 1763 if (Value *T = matchCondition( 1764 dyn_cast<BranchInst>(LoopEntry->getTerminator()), LoopEntry)) 1765 DefX = dyn_cast<Instruction>(T); 1766 else 1767 return false; 1768 1769 // step 2: detect instructions corresponding to "x.next = x >> 1 or x << 1" 1770 if (!DefX || !DefX->isShift()) 1771 return false; 1772 IntrinID = DefX->getOpcode() == Instruction::Shl ? Intrinsic::cttz : 1773 Intrinsic::ctlz; 1774 ConstantInt *Shft = dyn_cast<ConstantInt>(DefX->getOperand(1)); 1775 if (!Shft || !Shft->isOne()) 1776 return false; 1777 VarX = DefX->getOperand(0); 1778 1779 // step 3: Check the recurrence of variable X 1780 PHINode *PhiX = getRecurrenceVar(VarX, DefX, LoopEntry); 1781 if (!PhiX) 1782 return false; 1783 1784 InitX = PhiX->getIncomingValueForBlock(CurLoop->getLoopPreheader()); 1785 1786 // Make sure the initial value can't be negative otherwise the ashr in the 1787 // loop might never reach zero which would make the loop infinite. 1788 if (DefX->getOpcode() == Instruction::AShr && !isKnownNonNegative(InitX, DL)) 1789 return false; 1790 1791 // step 4: Find the instruction which count the CTLZ: cnt.next = cnt + 1 1792 // or cnt.next = cnt + -1. 1793 // TODO: We can skip the step. If loop trip count is known (CTLZ), 1794 // then all uses of "cnt.next" could be optimized to the trip count 1795 // plus "cnt0". Currently it is not optimized. 1796 // This step could be used to detect POPCNT instruction: 1797 // cnt.next = cnt + (x.next & 1) 1798 for (Instruction &Inst : llvm::make_range( 1799 LoopEntry->getFirstNonPHI()->getIterator(), LoopEntry->end())) { 1800 if (Inst.getOpcode() != Instruction::Add) 1801 continue; 1802 1803 ConstantInt *Inc = dyn_cast<ConstantInt>(Inst.getOperand(1)); 1804 if (!Inc || (!Inc->isOne() && !Inc->isMinusOne())) 1805 continue; 1806 1807 PHINode *Phi = getRecurrenceVar(Inst.getOperand(0), &Inst, LoopEntry); 1808 if (!Phi) 1809 continue; 1810 1811 CntInst = &Inst; 1812 CntPhi = Phi; 1813 break; 1814 } 1815 if (!CntInst) 1816 return false; 1817 1818 return true; 1819 } 1820 1821 /// Recognize CTLZ or CTTZ idiom in a non-countable loop and convert the loop 1822 /// to countable (with CTLZ / CTTZ trip count). If CTLZ / CTTZ inserted as a new 1823 /// trip count returns true; otherwise, returns false. 1824 bool LoopIdiomRecognize::recognizeAndInsertFFS() { 1825 // Give up if the loop has multiple blocks or multiple backedges. 1826 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1) 1827 return false; 1828 1829 Intrinsic::ID IntrinID; 1830 Value *InitX; 1831 Instruction *DefX = nullptr; 1832 PHINode *CntPhi = nullptr; 1833 Instruction *CntInst = nullptr; 1834 // Help decide if transformation is profitable. For ShiftUntilZero idiom, 1835 // this is always 6. 1836 size_t IdiomCanonicalSize = 6; 1837 1838 if (!detectShiftUntilZeroIdiom(CurLoop, *DL, IntrinID, InitX, 1839 CntInst, CntPhi, DefX)) 1840 return false; 1841 1842 bool IsCntPhiUsedOutsideLoop = false; 1843 for (User *U : CntPhi->users()) 1844 if (!CurLoop->contains(cast<Instruction>(U))) { 1845 IsCntPhiUsedOutsideLoop = true; 1846 break; 1847 } 1848 bool IsCntInstUsedOutsideLoop = false; 1849 for (User *U : CntInst->users()) 1850 if (!CurLoop->contains(cast<Instruction>(U))) { 1851 IsCntInstUsedOutsideLoop = true; 1852 break; 1853 } 1854 // If both CntInst and CntPhi are used outside the loop the profitability 1855 // is questionable. 1856 if (IsCntInstUsedOutsideLoop && IsCntPhiUsedOutsideLoop) 1857 return false; 1858 1859 // For some CPUs result of CTLZ(X) intrinsic is undefined 1860 // when X is 0. If we can not guarantee X != 0, we need to check this 1861 // when expand. 1862 bool ZeroCheck = false; 1863 // It is safe to assume Preheader exist as it was checked in 1864 // parent function RunOnLoop. 1865 BasicBlock *PH = CurLoop->getLoopPreheader(); 1866 1867 // If we are using the count instruction outside the loop, make sure we 1868 // have a zero check as a precondition. Without the check the loop would run 1869 // one iteration for before any check of the input value. This means 0 and 1 1870 // would have identical behavior in the original loop and thus 1871 if (!IsCntPhiUsedOutsideLoop) { 1872 auto *PreCondBB = PH->getSinglePredecessor(); 1873 if (!PreCondBB) 1874 return false; 1875 auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator()); 1876 if (!PreCondBI) 1877 return false; 1878 if (matchCondition(PreCondBI, PH) != InitX) 1879 return false; 1880 ZeroCheck = true; 1881 } 1882 1883 // Check if CTLZ / CTTZ intrinsic is profitable. Assume it is always 1884 // profitable if we delete the loop. 1885 1886 // the loop has only 6 instructions: 1887 // %n.addr.0 = phi [ %n, %entry ], [ %shr, %while.cond ] 1888 // %i.0 = phi [ %i0, %entry ], [ %inc, %while.cond ] 1889 // %shr = ashr %n.addr.0, 1 1890 // %tobool = icmp eq %shr, 0 1891 // %inc = add nsw %i.0, 1 1892 // br i1 %tobool 1893 1894 const Value *Args[] = {InitX, 1895 ConstantInt::getBool(InitX->getContext(), ZeroCheck)}; 1896 1897 // @llvm.dbg doesn't count as they have no semantic effect. 1898 auto InstWithoutDebugIt = CurLoop->getHeader()->instructionsWithoutDebug(); 1899 uint32_t HeaderSize = 1900 std::distance(InstWithoutDebugIt.begin(), InstWithoutDebugIt.end()); 1901 1902 IntrinsicCostAttributes Attrs(IntrinID, InitX->getType(), Args); 1903 InstructionCost Cost = 1904 TTI->getIntrinsicInstrCost(Attrs, TargetTransformInfo::TCK_SizeAndLatency); 1905 if (HeaderSize != IdiomCanonicalSize && 1906 Cost > TargetTransformInfo::TCC_Basic) 1907 return false; 1908 1909 transformLoopToCountable(IntrinID, PH, CntInst, CntPhi, InitX, DefX, 1910 DefX->getDebugLoc(), ZeroCheck, 1911 IsCntPhiUsedOutsideLoop); 1912 return true; 1913 } 1914 1915 /// Recognizes a population count idiom in a non-countable loop. 1916 /// 1917 /// If detected, transforms the relevant code to issue the popcount intrinsic 1918 /// function call, and returns true; otherwise, returns false. 1919 bool LoopIdiomRecognize::recognizePopcount() { 1920 if (TTI->getPopcntSupport(32) != TargetTransformInfo::PSK_FastHardware) 1921 return false; 1922 1923 // Counting population are usually conducted by few arithmetic instructions. 1924 // Such instructions can be easily "absorbed" by vacant slots in a 1925 // non-compact loop. Therefore, recognizing popcount idiom only makes sense 1926 // in a compact loop. 1927 1928 // Give up if the loop has multiple blocks or multiple backedges. 1929 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1) 1930 return false; 1931 1932 BasicBlock *LoopBody = *(CurLoop->block_begin()); 1933 if (LoopBody->size() >= 20) { 1934 // The loop is too big, bail out. 1935 return false; 1936 } 1937 1938 // It should have a preheader containing nothing but an unconditional branch. 1939 BasicBlock *PH = CurLoop->getLoopPreheader(); 1940 if (!PH || &PH->front() != PH->getTerminator()) 1941 return false; 1942 auto *EntryBI = dyn_cast<BranchInst>(PH->getTerminator()); 1943 if (!EntryBI || EntryBI->isConditional()) 1944 return false; 1945 1946 // It should have a precondition block where the generated popcount intrinsic 1947 // function can be inserted. 1948 auto *PreCondBB = PH->getSinglePredecessor(); 1949 if (!PreCondBB) 1950 return false; 1951 auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator()); 1952 if (!PreCondBI || PreCondBI->isUnconditional()) 1953 return false; 1954 1955 Instruction *CntInst; 1956 PHINode *CntPhi; 1957 Value *Val; 1958 if (!detectPopcountIdiom(CurLoop, PreCondBB, CntInst, CntPhi, Val)) 1959 return false; 1960 1961 transformLoopToPopcount(PreCondBB, CntInst, CntPhi, Val); 1962 return true; 1963 } 1964 1965 static CallInst *createPopcntIntrinsic(IRBuilder<> &IRBuilder, Value *Val, 1966 const DebugLoc &DL) { 1967 Value *Ops[] = {Val}; 1968 Type *Tys[] = {Val->getType()}; 1969 1970 Module *M = IRBuilder.GetInsertBlock()->getParent()->getParent(); 1971 Function *Func = Intrinsic::getDeclaration(M, Intrinsic::ctpop, Tys); 1972 CallInst *CI = IRBuilder.CreateCall(Func, Ops); 1973 CI->setDebugLoc(DL); 1974 1975 return CI; 1976 } 1977 1978 static CallInst *createFFSIntrinsic(IRBuilder<> &IRBuilder, Value *Val, 1979 const DebugLoc &DL, bool ZeroCheck, 1980 Intrinsic::ID IID) { 1981 Value *Ops[] = {Val, IRBuilder.getInt1(ZeroCheck)}; 1982 Type *Tys[] = {Val->getType()}; 1983 1984 Module *M = IRBuilder.GetInsertBlock()->getParent()->getParent(); 1985 Function *Func = Intrinsic::getDeclaration(M, IID, Tys); 1986 CallInst *CI = IRBuilder.CreateCall(Func, Ops); 1987 CI->setDebugLoc(DL); 1988 1989 return CI; 1990 } 1991 1992 /// Transform the following loop (Using CTLZ, CTTZ is similar): 1993 /// loop: 1994 /// CntPhi = PHI [Cnt0, CntInst] 1995 /// PhiX = PHI [InitX, DefX] 1996 /// CntInst = CntPhi + 1 1997 /// DefX = PhiX >> 1 1998 /// LOOP_BODY 1999 /// Br: loop if (DefX != 0) 2000 /// Use(CntPhi) or Use(CntInst) 2001 /// 2002 /// Into: 2003 /// If CntPhi used outside the loop: 2004 /// CountPrev = BitWidth(InitX) - CTLZ(InitX >> 1) 2005 /// Count = CountPrev + 1 2006 /// else 2007 /// Count = BitWidth(InitX) - CTLZ(InitX) 2008 /// loop: 2009 /// CntPhi = PHI [Cnt0, CntInst] 2010 /// PhiX = PHI [InitX, DefX] 2011 /// PhiCount = PHI [Count, Dec] 2012 /// CntInst = CntPhi + 1 2013 /// DefX = PhiX >> 1 2014 /// Dec = PhiCount - 1 2015 /// LOOP_BODY 2016 /// Br: loop if (Dec != 0) 2017 /// Use(CountPrev + Cnt0) // Use(CntPhi) 2018 /// or 2019 /// Use(Count + Cnt0) // Use(CntInst) 2020 /// 2021 /// If LOOP_BODY is empty the loop will be deleted. 2022 /// If CntInst and DefX are not used in LOOP_BODY they will be removed. 2023 void LoopIdiomRecognize::transformLoopToCountable( 2024 Intrinsic::ID IntrinID, BasicBlock *Preheader, Instruction *CntInst, 2025 PHINode *CntPhi, Value *InitX, Instruction *DefX, const DebugLoc &DL, 2026 bool ZeroCheck, bool IsCntPhiUsedOutsideLoop) { 2027 BranchInst *PreheaderBr = cast<BranchInst>(Preheader->getTerminator()); 2028 2029 // Step 1: Insert the CTLZ/CTTZ instruction at the end of the preheader block 2030 IRBuilder<> Builder(PreheaderBr); 2031 Builder.SetCurrentDebugLocation(DL); 2032 2033 // If there are no uses of CntPhi crate: 2034 // Count = BitWidth - CTLZ(InitX); 2035 // NewCount = Count; 2036 // If there are uses of CntPhi create: 2037 // NewCount = BitWidth - CTLZ(InitX >> 1); 2038 // Count = NewCount + 1; 2039 Value *InitXNext; 2040 if (IsCntPhiUsedOutsideLoop) { 2041 if (DefX->getOpcode() == Instruction::AShr) 2042 InitXNext = Builder.CreateAShr(InitX, 1); 2043 else if (DefX->getOpcode() == Instruction::LShr) 2044 InitXNext = Builder.CreateLShr(InitX, 1); 2045 else if (DefX->getOpcode() == Instruction::Shl) // cttz 2046 InitXNext = Builder.CreateShl(InitX, 1); 2047 else 2048 llvm_unreachable("Unexpected opcode!"); 2049 } else 2050 InitXNext = InitX; 2051 Value *Count = 2052 createFFSIntrinsic(Builder, InitXNext, DL, ZeroCheck, IntrinID); 2053 Type *CountTy = Count->getType(); 2054 Count = Builder.CreateSub( 2055 ConstantInt::get(CountTy, CountTy->getIntegerBitWidth()), Count); 2056 Value *NewCount = Count; 2057 if (IsCntPhiUsedOutsideLoop) 2058 Count = Builder.CreateAdd(Count, ConstantInt::get(CountTy, 1)); 2059 2060 NewCount = Builder.CreateZExtOrTrunc(NewCount, CntInst->getType()); 2061 2062 Value *CntInitVal = CntPhi->getIncomingValueForBlock(Preheader); 2063 if (cast<ConstantInt>(CntInst->getOperand(1))->isOne()) { 2064 // If the counter was being incremented in the loop, add NewCount to the 2065 // counter's initial value, but only if the initial value is not zero. 2066 ConstantInt *InitConst = dyn_cast<ConstantInt>(CntInitVal); 2067 if (!InitConst || !InitConst->isZero()) 2068 NewCount = Builder.CreateAdd(NewCount, CntInitVal); 2069 } else { 2070 // If the count was being decremented in the loop, subtract NewCount from 2071 // the counter's initial value. 2072 NewCount = Builder.CreateSub(CntInitVal, NewCount); 2073 } 2074 2075 // Step 2: Insert new IV and loop condition: 2076 // loop: 2077 // ... 2078 // PhiCount = PHI [Count, Dec] 2079 // ... 2080 // Dec = PhiCount - 1 2081 // ... 2082 // Br: loop if (Dec != 0) 2083 BasicBlock *Body = *(CurLoop->block_begin()); 2084 auto *LbBr = cast<BranchInst>(Body->getTerminator()); 2085 ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition()); 2086 2087 PHINode *TcPhi = PHINode::Create(CountTy, 2, "tcphi", &Body->front()); 2088 2089 Builder.SetInsertPoint(LbCond); 2090 Instruction *TcDec = cast<Instruction>(Builder.CreateSub( 2091 TcPhi, ConstantInt::get(CountTy, 1), "tcdec", false, true)); 2092 2093 TcPhi->addIncoming(Count, Preheader); 2094 TcPhi->addIncoming(TcDec, Body); 2095 2096 CmpInst::Predicate Pred = 2097 (LbBr->getSuccessor(0) == Body) ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ; 2098 LbCond->setPredicate(Pred); 2099 LbCond->setOperand(0, TcDec); 2100 LbCond->setOperand(1, ConstantInt::get(CountTy, 0)); 2101 2102 // Step 3: All the references to the original counter outside 2103 // the loop are replaced with the NewCount 2104 if (IsCntPhiUsedOutsideLoop) 2105 CntPhi->replaceUsesOutsideBlock(NewCount, Body); 2106 else 2107 CntInst->replaceUsesOutsideBlock(NewCount, Body); 2108 2109 // step 4: Forget the "non-computable" trip-count SCEV associated with the 2110 // loop. The loop would otherwise not be deleted even if it becomes empty. 2111 SE->forgetLoop(CurLoop); 2112 } 2113 2114 void LoopIdiomRecognize::transformLoopToPopcount(BasicBlock *PreCondBB, 2115 Instruction *CntInst, 2116 PHINode *CntPhi, Value *Var) { 2117 BasicBlock *PreHead = CurLoop->getLoopPreheader(); 2118 auto *PreCondBr = cast<BranchInst>(PreCondBB->getTerminator()); 2119 const DebugLoc &DL = CntInst->getDebugLoc(); 2120 2121 // Assuming before transformation, the loop is following: 2122 // if (x) // the precondition 2123 // do { cnt++; x &= x - 1; } while(x); 2124 2125 // Step 1: Insert the ctpop instruction at the end of the precondition block 2126 IRBuilder<> Builder(PreCondBr); 2127 Value *PopCnt, *PopCntZext, *NewCount, *TripCnt; 2128 { 2129 PopCnt = createPopcntIntrinsic(Builder, Var, DL); 2130 NewCount = PopCntZext = 2131 Builder.CreateZExtOrTrunc(PopCnt, cast<IntegerType>(CntPhi->getType())); 2132 2133 if (NewCount != PopCnt) 2134 (cast<Instruction>(NewCount))->setDebugLoc(DL); 2135 2136 // TripCnt is exactly the number of iterations the loop has 2137 TripCnt = NewCount; 2138 2139 // If the population counter's initial value is not zero, insert Add Inst. 2140 Value *CntInitVal = CntPhi->getIncomingValueForBlock(PreHead); 2141 ConstantInt *InitConst = dyn_cast<ConstantInt>(CntInitVal); 2142 if (!InitConst || !InitConst->isZero()) { 2143 NewCount = Builder.CreateAdd(NewCount, CntInitVal); 2144 (cast<Instruction>(NewCount))->setDebugLoc(DL); 2145 } 2146 } 2147 2148 // Step 2: Replace the precondition from "if (x == 0) goto loop-exit" to 2149 // "if (NewCount == 0) loop-exit". Without this change, the intrinsic 2150 // function would be partial dead code, and downstream passes will drag 2151 // it back from the precondition block to the preheader. 2152 { 2153 ICmpInst *PreCond = cast<ICmpInst>(PreCondBr->getCondition()); 2154 2155 Value *Opnd0 = PopCntZext; 2156 Value *Opnd1 = ConstantInt::get(PopCntZext->getType(), 0); 2157 if (PreCond->getOperand(0) != Var) 2158 std::swap(Opnd0, Opnd1); 2159 2160 ICmpInst *NewPreCond = cast<ICmpInst>( 2161 Builder.CreateICmp(PreCond->getPredicate(), Opnd0, Opnd1)); 2162 PreCondBr->setCondition(NewPreCond); 2163 2164 RecursivelyDeleteTriviallyDeadInstructions(PreCond, TLI); 2165 } 2166 2167 // Step 3: Note that the population count is exactly the trip count of the 2168 // loop in question, which enable us to convert the loop from noncountable 2169 // loop into a countable one. The benefit is twofold: 2170 // 2171 // - If the loop only counts population, the entire loop becomes dead after 2172 // the transformation. It is a lot easier to prove a countable loop dead 2173 // than to prove a noncountable one. (In some C dialects, an infinite loop 2174 // isn't dead even if it computes nothing useful. In general, DCE needs 2175 // to prove a noncountable loop finite before safely delete it.) 2176 // 2177 // - If the loop also performs something else, it remains alive. 2178 // Since it is transformed to countable form, it can be aggressively 2179 // optimized by some optimizations which are in general not applicable 2180 // to a noncountable loop. 2181 // 2182 // After this step, this loop (conceptually) would look like following: 2183 // newcnt = __builtin_ctpop(x); 2184 // t = newcnt; 2185 // if (x) 2186 // do { cnt++; x &= x-1; t--) } while (t > 0); 2187 BasicBlock *Body = *(CurLoop->block_begin()); 2188 { 2189 auto *LbBr = cast<BranchInst>(Body->getTerminator()); 2190 ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition()); 2191 Type *Ty = TripCnt->getType(); 2192 2193 PHINode *TcPhi = PHINode::Create(Ty, 2, "tcphi", &Body->front()); 2194 2195 Builder.SetInsertPoint(LbCond); 2196 Instruction *TcDec = cast<Instruction>( 2197 Builder.CreateSub(TcPhi, ConstantInt::get(Ty, 1), 2198 "tcdec", false, true)); 2199 2200 TcPhi->addIncoming(TripCnt, PreHead); 2201 TcPhi->addIncoming(TcDec, Body); 2202 2203 CmpInst::Predicate Pred = 2204 (LbBr->getSuccessor(0) == Body) ? CmpInst::ICMP_UGT : CmpInst::ICMP_SLE; 2205 LbCond->setPredicate(Pred); 2206 LbCond->setOperand(0, TcDec); 2207 LbCond->setOperand(1, ConstantInt::get(Ty, 0)); 2208 } 2209 2210 // Step 4: All the references to the original population counter outside 2211 // the loop are replaced with the NewCount -- the value returned from 2212 // __builtin_ctpop(). 2213 CntInst->replaceUsesOutsideBlock(NewCount, Body); 2214 2215 // step 5: Forget the "non-computable" trip-count SCEV associated with the 2216 // loop. The loop would otherwise not be deleted even if it becomes empty. 2217 SE->forgetLoop(CurLoop); 2218 } 2219 2220 /// Match loop-invariant value. 2221 template <typename SubPattern_t> struct match_LoopInvariant { 2222 SubPattern_t SubPattern; 2223 const Loop *L; 2224 2225 match_LoopInvariant(const SubPattern_t &SP, const Loop *L) 2226 : SubPattern(SP), L(L) {} 2227 2228 template <typename ITy> bool match(ITy *V) { 2229 return L->isLoopInvariant(V) && SubPattern.match(V); 2230 } 2231 }; 2232 2233 /// Matches if the value is loop-invariant. 2234 template <typename Ty> 2235 inline match_LoopInvariant<Ty> m_LoopInvariant(const Ty &M, const Loop *L) { 2236 return match_LoopInvariant<Ty>(M, L); 2237 } 2238 2239 /// Return true if the idiom is detected in the loop. 2240 /// 2241 /// The core idiom we are trying to detect is: 2242 /// \code 2243 /// entry: 2244 /// <...> 2245 /// %bitmask = shl i32 1, %bitpos 2246 /// br label %loop 2247 /// 2248 /// loop: 2249 /// %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] 2250 /// %x.curr.bitmasked = and i32 %x.curr, %bitmask 2251 /// %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 2252 /// %x.next = shl i32 %x.curr, 1 2253 /// <...> 2254 /// br i1 %x.curr.isbitunset, label %loop, label %end 2255 /// 2256 /// end: 2257 /// %x.curr.res = phi i32 [ %x.curr, %loop ] <...> 2258 /// %x.next.res = phi i32 [ %x.next, %loop ] <...> 2259 /// <...> 2260 /// \endcode 2261 static bool detectShiftUntilBitTestIdiom(Loop *CurLoop, Value *&BaseX, 2262 Value *&BitMask, Value *&BitPos, 2263 Value *&CurrX, Instruction *&NextX) { 2264 LLVM_DEBUG(dbgs() << DEBUG_TYPE 2265 " Performing shift-until-bittest idiom detection.\n"); 2266 2267 // Give up if the loop has multiple blocks or multiple backedges. 2268 if (CurLoop->getNumBlocks() != 1 || CurLoop->getNumBackEdges() != 1) { 2269 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad block/backedge count.\n"); 2270 return false; 2271 } 2272 2273 BasicBlock *LoopHeaderBB = CurLoop->getHeader(); 2274 BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader(); 2275 assert(LoopPreheaderBB && "There is always a loop preheader."); 2276 2277 using namespace PatternMatch; 2278 2279 // Step 1: Check if the loop backedge is in desirable form. 2280 2281 ICmpInst::Predicate Pred; 2282 Value *CmpLHS, *CmpRHS; 2283 BasicBlock *TrueBB, *FalseBB; 2284 if (!match(LoopHeaderBB->getTerminator(), 2285 m_Br(m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS)), 2286 m_BasicBlock(TrueBB), m_BasicBlock(FalseBB)))) { 2287 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge structure.\n"); 2288 return false; 2289 } 2290 2291 // Step 2: Check if the backedge's condition is in desirable form. 2292 2293 auto MatchVariableBitMask = [&]() { 2294 return ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero()) && 2295 match(CmpLHS, 2296 m_c_And(m_Value(CurrX), 2297 m_CombineAnd( 2298 m_Value(BitMask), 2299 m_LoopInvariant(m_Shl(m_One(), m_Value(BitPos)), 2300 CurLoop)))); 2301 }; 2302 auto MatchConstantBitMask = [&]() { 2303 return ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero()) && 2304 match(CmpLHS, m_And(m_Value(CurrX), 2305 m_CombineAnd(m_Value(BitMask), m_Power2()))) && 2306 (BitPos = ConstantExpr::getExactLogBase2(cast<Constant>(BitMask))); 2307 }; 2308 auto MatchDecomposableConstantBitMask = [&]() { 2309 APInt Mask; 2310 return llvm::decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, CurrX, Mask) && 2311 ICmpInst::isEquality(Pred) && Mask.isPowerOf2() && 2312 (BitMask = ConstantInt::get(CurrX->getType(), Mask)) && 2313 (BitPos = ConstantInt::get(CurrX->getType(), Mask.logBase2())); 2314 }; 2315 2316 if (!MatchVariableBitMask() && !MatchConstantBitMask() && 2317 !MatchDecomposableConstantBitMask()) { 2318 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge comparison.\n"); 2319 return false; 2320 } 2321 2322 // Step 3: Check if the recurrence is in desirable form. 2323 auto *CurrXPN = dyn_cast<PHINode>(CurrX); 2324 if (!CurrXPN || CurrXPN->getParent() != LoopHeaderBB) { 2325 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Not an expected PHI node.\n"); 2326 return false; 2327 } 2328 2329 BaseX = CurrXPN->getIncomingValueForBlock(LoopPreheaderBB); 2330 NextX = 2331 dyn_cast<Instruction>(CurrXPN->getIncomingValueForBlock(LoopHeaderBB)); 2332 2333 assert(CurLoop->isLoopInvariant(BaseX) && 2334 "Expected BaseX to be avaliable in the preheader!"); 2335 2336 if (!NextX || !match(NextX, m_Shl(m_Specific(CurrX), m_One()))) { 2337 // FIXME: support right-shift? 2338 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad recurrence.\n"); 2339 return false; 2340 } 2341 2342 // Step 4: Check if the backedge's destinations are in desirable form. 2343 2344 assert(ICmpInst::isEquality(Pred) && 2345 "Should only get equality predicates here."); 2346 2347 // cmp-br is commutative, so canonicalize to a single variant. 2348 if (Pred != ICmpInst::Predicate::ICMP_EQ) { 2349 Pred = ICmpInst::getInversePredicate(Pred); 2350 std::swap(TrueBB, FalseBB); 2351 } 2352 2353 // We expect to exit loop when comparison yields false, 2354 // so when it yields true we should branch back to loop header. 2355 if (TrueBB != LoopHeaderBB) { 2356 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge flow.\n"); 2357 return false; 2358 } 2359 2360 // Okay, idiom checks out. 2361 return true; 2362 } 2363 2364 /// Look for the following loop: 2365 /// \code 2366 /// entry: 2367 /// <...> 2368 /// %bitmask = shl i32 1, %bitpos 2369 /// br label %loop 2370 /// 2371 /// loop: 2372 /// %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ] 2373 /// %x.curr.bitmasked = and i32 %x.curr, %bitmask 2374 /// %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0 2375 /// %x.next = shl i32 %x.curr, 1 2376 /// <...> 2377 /// br i1 %x.curr.isbitunset, label %loop, label %end 2378 /// 2379 /// end: 2380 /// %x.curr.res = phi i32 [ %x.curr, %loop ] <...> 2381 /// %x.next.res = phi i32 [ %x.next, %loop ] <...> 2382 /// <...> 2383 /// \endcode 2384 /// 2385 /// And transform it into: 2386 /// \code 2387 /// entry: 2388 /// %bitmask = shl i32 1, %bitpos 2389 /// %lowbitmask = add i32 %bitmask, -1 2390 /// %mask = or i32 %lowbitmask, %bitmask 2391 /// %x.masked = and i32 %x, %mask 2392 /// %x.masked.numleadingzeros = call i32 @llvm.ctlz.i32(i32 %x.masked, 2393 /// i1 true) 2394 /// %x.masked.numactivebits = sub i32 32, %x.masked.numleadingzeros 2395 /// %x.masked.leadingonepos = add i32 %x.masked.numactivebits, -1 2396 /// %backedgetakencount = sub i32 %bitpos, %x.masked.leadingonepos 2397 /// %tripcount = add i32 %backedgetakencount, 1 2398 /// %x.curr = shl i32 %x, %backedgetakencount 2399 /// %x.next = shl i32 %x, %tripcount 2400 /// br label %loop 2401 /// 2402 /// loop: 2403 /// %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.next, %loop ] 2404 /// %loop.iv.next = add nuw i32 %loop.iv, 1 2405 /// %loop.ivcheck = icmp eq i32 %loop.iv.next, %tripcount 2406 /// <...> 2407 /// br i1 %loop.ivcheck, label %end, label %loop 2408 /// 2409 /// end: 2410 /// %x.curr.res = phi i32 [ %x.curr, %loop ] <...> 2411 /// %x.next.res = phi i32 [ %x.next, %loop ] <...> 2412 /// <...> 2413 /// \endcode 2414 bool LoopIdiomRecognize::recognizeShiftUntilBitTest() { 2415 bool MadeChange = false; 2416 2417 Value *X, *BitMask, *BitPos, *XCurr; 2418 Instruction *XNext; 2419 if (!detectShiftUntilBitTestIdiom(CurLoop, X, BitMask, BitPos, XCurr, 2420 XNext)) { 2421 LLVM_DEBUG(dbgs() << DEBUG_TYPE 2422 " shift-until-bittest idiom detection failed.\n"); 2423 return MadeChange; 2424 } 2425 LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-bittest idiom detected!\n"); 2426 2427 // Ok, it is the idiom we were looking for, we *could* transform this loop, 2428 // but is it profitable to transform? 2429 2430 BasicBlock *LoopHeaderBB = CurLoop->getHeader(); 2431 BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader(); 2432 assert(LoopPreheaderBB && "There is always a loop preheader."); 2433 2434 BasicBlock *SuccessorBB = CurLoop->getExitBlock(); 2435 assert(SuccessorBB && "There is only a single successor."); 2436 2437 IRBuilder<> Builder(LoopPreheaderBB->getTerminator()); 2438 Builder.SetCurrentDebugLocation(cast<Instruction>(XCurr)->getDebugLoc()); 2439 2440 Intrinsic::ID IntrID = Intrinsic::ctlz; 2441 Type *Ty = X->getType(); 2442 unsigned Bitwidth = Ty->getScalarSizeInBits(); 2443 2444 TargetTransformInfo::TargetCostKind CostKind = 2445 TargetTransformInfo::TCK_SizeAndLatency; 2446 2447 // The rewrite is considered to be unprofitable iff and only iff the 2448 // intrinsic/shift we'll use are not cheap. Note that we are okay with *just* 2449 // making the loop countable, even if nothing else changes. 2450 IntrinsicCostAttributes Attrs( 2451 IntrID, Ty, {UndefValue::get(Ty), /*is_zero_undef=*/Builder.getTrue()}); 2452 InstructionCost Cost = TTI->getIntrinsicInstrCost(Attrs, CostKind); 2453 if (Cost > TargetTransformInfo::TCC_Basic) { 2454 LLVM_DEBUG(dbgs() << DEBUG_TYPE 2455 " Intrinsic is too costly, not beneficial\n"); 2456 return MadeChange; 2457 } 2458 if (TTI->getArithmeticInstrCost(Instruction::Shl, Ty, CostKind) > 2459 TargetTransformInfo::TCC_Basic) { 2460 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Shift is too costly, not beneficial\n"); 2461 return MadeChange; 2462 } 2463 2464 // Ok, transform appears worthwhile. 2465 MadeChange = true; 2466 2467 // Step 1: Compute the loop trip count. 2468 2469 Value *LowBitMask = Builder.CreateAdd(BitMask, Constant::getAllOnesValue(Ty), 2470 BitPos->getName() + ".lowbitmask"); 2471 Value *Mask = 2472 Builder.CreateOr(LowBitMask, BitMask, BitPos->getName() + ".mask"); 2473 Value *XMasked = Builder.CreateAnd(X, Mask, X->getName() + ".masked"); 2474 CallInst *XMaskedNumLeadingZeros = Builder.CreateIntrinsic( 2475 IntrID, Ty, {XMasked, /*is_zero_undef=*/Builder.getTrue()}, 2476 /*FMFSource=*/nullptr, XMasked->getName() + ".numleadingzeros"); 2477 Value *XMaskedNumActiveBits = Builder.CreateSub( 2478 ConstantInt::get(Ty, Ty->getScalarSizeInBits()), XMaskedNumLeadingZeros, 2479 XMasked->getName() + ".numactivebits", /*HasNUW=*/true, 2480 /*HasNSW=*/Bitwidth != 2); 2481 Value *XMaskedLeadingOnePos = 2482 Builder.CreateAdd(XMaskedNumActiveBits, Constant::getAllOnesValue(Ty), 2483 XMasked->getName() + ".leadingonepos", /*HasNUW=*/false, 2484 /*HasNSW=*/Bitwidth > 2); 2485 2486 Value *LoopBackedgeTakenCount = Builder.CreateSub( 2487 BitPos, XMaskedLeadingOnePos, CurLoop->getName() + ".backedgetakencount", 2488 /*HasNUW=*/true, /*HasNSW=*/true); 2489 // We know loop's backedge-taken count, but what's loop's trip count? 2490 // Note that while NUW is always safe, while NSW is only for bitwidths != 2. 2491 Value *LoopTripCount = 2492 Builder.CreateAdd(LoopBackedgeTakenCount, ConstantInt::get(Ty, 1), 2493 CurLoop->getName() + ".tripcount", /*HasNUW=*/true, 2494 /*HasNSW=*/Bitwidth != 2); 2495 2496 // Step 2: Compute the recurrence's final value without a loop. 2497 2498 // NewX is always safe to compute, because `LoopBackedgeTakenCount` 2499 // will always be smaller than `bitwidth(X)`, i.e. we never get poison. 2500 Value *NewX = Builder.CreateShl(X, LoopBackedgeTakenCount); 2501 NewX->takeName(XCurr); 2502 if (auto *I = dyn_cast<Instruction>(NewX)) 2503 I->copyIRFlags(XNext, /*IncludeWrapFlags=*/true); 2504 2505 Value *NewXNext; 2506 // Rewriting XNext is more complicated, however, because `X << LoopTripCount` 2507 // will be poison iff `LoopTripCount == bitwidth(X)` (which will happen 2508 // iff `BitPos` is `bitwidth(x) - 1` and `X` is `1`). So unless we know 2509 // that isn't the case, we'll need to emit an alternative, safe IR. 2510 if (XNext->hasNoSignedWrap() || XNext->hasNoUnsignedWrap() || 2511 PatternMatch::match( 2512 BitPos, PatternMatch::m_SpecificInt_ICMP( 2513 ICmpInst::ICMP_NE, APInt(Ty->getScalarSizeInBits(), 2514 Ty->getScalarSizeInBits() - 1)))) 2515 NewXNext = Builder.CreateShl(X, LoopTripCount); 2516 else { 2517 // Otherwise, just additionally shift by one. It's the smallest solution, 2518 // alternatively, we could check that NewX is INT_MIN (or BitPos is ) 2519 // and select 0 instead. 2520 NewXNext = Builder.CreateShl(NewX, ConstantInt::get(Ty, 1)); 2521 } 2522 2523 NewXNext->takeName(XNext); 2524 if (auto *I = dyn_cast<Instruction>(NewXNext)) 2525 I->copyIRFlags(XNext, /*IncludeWrapFlags=*/true); 2526 2527 // Step 3: Adjust the successor basic block to recieve the computed 2528 // recurrence's final value instead of the recurrence itself. 2529 2530 XCurr->replaceUsesOutsideBlock(NewX, LoopHeaderBB); 2531 XNext->replaceUsesOutsideBlock(NewXNext, LoopHeaderBB); 2532 2533 // Step 4: Rewrite the loop into a countable form, with canonical IV. 2534 2535 // The new canonical induction variable. 2536 Builder.SetInsertPoint(&LoopHeaderBB->front()); 2537 auto *IV = Builder.CreatePHI(Ty, 2, CurLoop->getName() + ".iv"); 2538 2539 // The induction itself. 2540 // Note that while NUW is always safe, while NSW is only for bitwidths != 2. 2541 Builder.SetInsertPoint(LoopHeaderBB->getTerminator()); 2542 auto *IVNext = 2543 Builder.CreateAdd(IV, ConstantInt::get(Ty, 1), IV->getName() + ".next", 2544 /*HasNUW=*/true, /*HasNSW=*/Bitwidth != 2); 2545 2546 // The loop trip count check. 2547 auto *IVCheck = Builder.CreateICmpEQ(IVNext, LoopTripCount, 2548 CurLoop->getName() + ".ivcheck"); 2549 Builder.CreateCondBr(IVCheck, SuccessorBB, LoopHeaderBB); 2550 LoopHeaderBB->getTerminator()->eraseFromParent(); 2551 2552 // Populate the IV PHI. 2553 IV->addIncoming(ConstantInt::get(Ty, 0), LoopPreheaderBB); 2554 IV->addIncoming(IVNext, LoopHeaderBB); 2555 2556 // Step 5: Forget the "non-computable" trip-count SCEV associated with the 2557 // loop. The loop would otherwise not be deleted even if it becomes empty. 2558 2559 SE->forgetLoop(CurLoop); 2560 2561 // Other passes will take care of actually deleting the loop if possible. 2562 2563 LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-bittest idiom optimized!\n"); 2564 2565 ++NumShiftUntilBitTest; 2566 return MadeChange; 2567 } 2568 2569 /// Return true if the idiom is detected in the loop. 2570 /// 2571 /// The core idiom we are trying to detect is: 2572 /// \code 2573 /// entry: 2574 /// <...> 2575 /// %start = <...> 2576 /// %extraoffset = <...> 2577 /// <...> 2578 /// br label %for.cond 2579 /// 2580 /// loop: 2581 /// %iv = phi i8 [ %start, %entry ], [ %iv.next, %for.cond ] 2582 /// %nbits = add nsw i8 %iv, %extraoffset 2583 /// %val.shifted = {{l,a}shr,shl} i8 %val, %nbits 2584 /// %val.shifted.iszero = icmp eq i8 %val.shifted, 0 2585 /// %iv.next = add i8 %iv, 1 2586 /// <...> 2587 /// br i1 %val.shifted.iszero, label %end, label %loop 2588 /// 2589 /// end: 2590 /// %iv.res = phi i8 [ %iv, %loop ] <...> 2591 /// %nbits.res = phi i8 [ %nbits, %loop ] <...> 2592 /// %val.shifted.res = phi i8 [ %val.shifted, %loop ] <...> 2593 /// %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ] <...> 2594 /// %iv.next.res = phi i8 [ %iv.next, %loop ] <...> 2595 /// <...> 2596 /// \endcode 2597 static bool detectShiftUntilZeroIdiom(Loop *CurLoop, ScalarEvolution *SE, 2598 Instruction *&ValShiftedIsZero, 2599 Intrinsic::ID &IntrinID, Instruction *&IV, 2600 Value *&Start, Value *&Val, 2601 const SCEV *&ExtraOffsetExpr, 2602 bool &InvertedCond) { 2603 LLVM_DEBUG(dbgs() << DEBUG_TYPE 2604 " Performing shift-until-zero idiom detection.\n"); 2605 2606 // Give up if the loop has multiple blocks or multiple backedges. 2607 if (CurLoop->getNumBlocks() != 1 || CurLoop->getNumBackEdges() != 1) { 2608 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad block/backedge count.\n"); 2609 return false; 2610 } 2611 2612 Instruction *ValShifted, *NBits, *IVNext; 2613 Value *ExtraOffset; 2614 2615 BasicBlock *LoopHeaderBB = CurLoop->getHeader(); 2616 BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader(); 2617 assert(LoopPreheaderBB && "There is always a loop preheader."); 2618 2619 using namespace PatternMatch; 2620 2621 // Step 1: Check if the loop backedge, condition is in desirable form. 2622 2623 ICmpInst::Predicate Pred; 2624 BasicBlock *TrueBB, *FalseBB; 2625 if (!match(LoopHeaderBB->getTerminator(), 2626 m_Br(m_Instruction(ValShiftedIsZero), m_BasicBlock(TrueBB), 2627 m_BasicBlock(FalseBB))) || 2628 !match(ValShiftedIsZero, 2629 m_ICmp(Pred, m_Instruction(ValShifted), m_Zero())) || 2630 !ICmpInst::isEquality(Pred)) { 2631 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge structure.\n"); 2632 return false; 2633 } 2634 2635 // Step 2: Check if the comparison's operand is in desirable form. 2636 // FIXME: Val could be a one-input PHI node, which we should look past. 2637 if (!match(ValShifted, m_Shift(m_LoopInvariant(m_Value(Val), CurLoop), 2638 m_Instruction(NBits)))) { 2639 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad comparisons value computation.\n"); 2640 return false; 2641 } 2642 IntrinID = ValShifted->getOpcode() == Instruction::Shl ? Intrinsic::cttz 2643 : Intrinsic::ctlz; 2644 2645 // Step 3: Check if the shift amount is in desirable form. 2646 2647 if (match(NBits, m_c_Add(m_Instruction(IV), 2648 m_LoopInvariant(m_Value(ExtraOffset), CurLoop))) && 2649 (NBits->hasNoSignedWrap() || NBits->hasNoUnsignedWrap())) 2650 ExtraOffsetExpr = SE->getNegativeSCEV(SE->getSCEV(ExtraOffset)); 2651 else if (match(NBits, 2652 m_Sub(m_Instruction(IV), 2653 m_LoopInvariant(m_Value(ExtraOffset), CurLoop))) && 2654 NBits->hasNoSignedWrap()) 2655 ExtraOffsetExpr = SE->getSCEV(ExtraOffset); 2656 else { 2657 IV = NBits; 2658 ExtraOffsetExpr = SE->getZero(NBits->getType()); 2659 } 2660 2661 // Step 4: Check if the recurrence is in desirable form. 2662 auto *IVPN = dyn_cast<PHINode>(IV); 2663 if (!IVPN || IVPN->getParent() != LoopHeaderBB) { 2664 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Not an expected PHI node.\n"); 2665 return false; 2666 } 2667 2668 Start = IVPN->getIncomingValueForBlock(LoopPreheaderBB); 2669 IVNext = dyn_cast<Instruction>(IVPN->getIncomingValueForBlock(LoopHeaderBB)); 2670 2671 if (!IVNext || !match(IVNext, m_Add(m_Specific(IVPN), m_One()))) { 2672 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad recurrence.\n"); 2673 return false; 2674 } 2675 2676 // Step 4: Check if the backedge's destinations are in desirable form. 2677 2678 assert(ICmpInst::isEquality(Pred) && 2679 "Should only get equality predicates here."); 2680 2681 // cmp-br is commutative, so canonicalize to a single variant. 2682 InvertedCond = Pred != ICmpInst::Predicate::ICMP_EQ; 2683 if (InvertedCond) { 2684 Pred = ICmpInst::getInversePredicate(Pred); 2685 std::swap(TrueBB, FalseBB); 2686 } 2687 2688 // We expect to exit loop when comparison yields true, 2689 // so when it yields false we should branch back to loop header. 2690 if (FalseBB != LoopHeaderBB) { 2691 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge flow.\n"); 2692 return false; 2693 } 2694 2695 // The new, countable, loop will certainly only run a known number of 2696 // iterations, It won't be infinite. But the old loop might be infinite 2697 // under certain conditions. For logical shifts, the value will become zero 2698 // after at most bitwidth(%Val) loop iterations. However, for arithmetic 2699 // right-shift, iff the sign bit was set, the value will never become zero, 2700 // and the loop may never finish. 2701 if (ValShifted->getOpcode() == Instruction::AShr && 2702 !isMustProgress(CurLoop) && !SE->isKnownNonNegative(SE->getSCEV(Val))) { 2703 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Can not prove the loop is finite.\n"); 2704 return false; 2705 } 2706 2707 // Okay, idiom checks out. 2708 return true; 2709 } 2710 2711 /// Look for the following loop: 2712 /// \code 2713 /// entry: 2714 /// <...> 2715 /// %start = <...> 2716 /// %extraoffset = <...> 2717 /// <...> 2718 /// br label %for.cond 2719 /// 2720 /// loop: 2721 /// %iv = phi i8 [ %start, %entry ], [ %iv.next, %for.cond ] 2722 /// %nbits = add nsw i8 %iv, %extraoffset 2723 /// %val.shifted = {{l,a}shr,shl} i8 %val, %nbits 2724 /// %val.shifted.iszero = icmp eq i8 %val.shifted, 0 2725 /// %iv.next = add i8 %iv, 1 2726 /// <...> 2727 /// br i1 %val.shifted.iszero, label %end, label %loop 2728 /// 2729 /// end: 2730 /// %iv.res = phi i8 [ %iv, %loop ] <...> 2731 /// %nbits.res = phi i8 [ %nbits, %loop ] <...> 2732 /// %val.shifted.res = phi i8 [ %val.shifted, %loop ] <...> 2733 /// %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ] <...> 2734 /// %iv.next.res = phi i8 [ %iv.next, %loop ] <...> 2735 /// <...> 2736 /// \endcode 2737 /// 2738 /// And transform it into: 2739 /// \code 2740 /// entry: 2741 /// <...> 2742 /// %start = <...> 2743 /// %extraoffset = <...> 2744 /// <...> 2745 /// %val.numleadingzeros = call i8 @llvm.ct{l,t}z.i8(i8 %val, i1 0) 2746 /// %val.numactivebits = sub i8 8, %val.numleadingzeros 2747 /// %extraoffset.neg = sub i8 0, %extraoffset 2748 /// %tmp = add i8 %val.numactivebits, %extraoffset.neg 2749 /// %iv.final = call i8 @llvm.smax.i8(i8 %tmp, i8 %start) 2750 /// %loop.tripcount = sub i8 %iv.final, %start 2751 /// br label %loop 2752 /// 2753 /// loop: 2754 /// %loop.iv = phi i8 [ 0, %entry ], [ %loop.iv.next, %loop ] 2755 /// %loop.iv.next = add i8 %loop.iv, 1 2756 /// %loop.ivcheck = icmp eq i8 %loop.iv.next, %loop.tripcount 2757 /// %iv = add i8 %loop.iv, %start 2758 /// <...> 2759 /// br i1 %loop.ivcheck, label %end, label %loop 2760 /// 2761 /// end: 2762 /// %iv.res = phi i8 [ %iv.final, %loop ] <...> 2763 /// <...> 2764 /// \endcode 2765 bool LoopIdiomRecognize::recognizeShiftUntilZero() { 2766 bool MadeChange = false; 2767 2768 Instruction *ValShiftedIsZero; 2769 Intrinsic::ID IntrID; 2770 Instruction *IV; 2771 Value *Start, *Val; 2772 const SCEV *ExtraOffsetExpr; 2773 bool InvertedCond; 2774 if (!detectShiftUntilZeroIdiom(CurLoop, SE, ValShiftedIsZero, IntrID, IV, 2775 Start, Val, ExtraOffsetExpr, InvertedCond)) { 2776 LLVM_DEBUG(dbgs() << DEBUG_TYPE 2777 " shift-until-zero idiom detection failed.\n"); 2778 return MadeChange; 2779 } 2780 LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-zero idiom detected!\n"); 2781 2782 // Ok, it is the idiom we were looking for, we *could* transform this loop, 2783 // but is it profitable to transform? 2784 2785 BasicBlock *LoopHeaderBB = CurLoop->getHeader(); 2786 BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader(); 2787 assert(LoopPreheaderBB && "There is always a loop preheader."); 2788 2789 BasicBlock *SuccessorBB = CurLoop->getExitBlock(); 2790 assert(SuccessorBB && "There is only a single successor."); 2791 2792 IRBuilder<> Builder(LoopPreheaderBB->getTerminator()); 2793 Builder.SetCurrentDebugLocation(IV->getDebugLoc()); 2794 2795 Type *Ty = Val->getType(); 2796 unsigned Bitwidth = Ty->getScalarSizeInBits(); 2797 2798 TargetTransformInfo::TargetCostKind CostKind = 2799 TargetTransformInfo::TCK_SizeAndLatency; 2800 2801 // The rewrite is considered to be unprofitable iff and only iff the 2802 // intrinsic we'll use are not cheap. Note that we are okay with *just* 2803 // making the loop countable, even if nothing else changes. 2804 IntrinsicCostAttributes Attrs( 2805 IntrID, Ty, {UndefValue::get(Ty), /*is_zero_undef=*/Builder.getFalse()}); 2806 InstructionCost Cost = TTI->getIntrinsicInstrCost(Attrs, CostKind); 2807 if (Cost > TargetTransformInfo::TCC_Basic) { 2808 LLVM_DEBUG(dbgs() << DEBUG_TYPE 2809 " Intrinsic is too costly, not beneficial\n"); 2810 return MadeChange; 2811 } 2812 2813 // Ok, transform appears worthwhile. 2814 MadeChange = true; 2815 2816 bool OffsetIsZero = false; 2817 if (auto *ExtraOffsetExprC = dyn_cast<SCEVConstant>(ExtraOffsetExpr)) 2818 OffsetIsZero = ExtraOffsetExprC->isZero(); 2819 2820 // Step 1: Compute the loop's final IV value / trip count. 2821 2822 CallInst *ValNumLeadingZeros = Builder.CreateIntrinsic( 2823 IntrID, Ty, {Val, /*is_zero_undef=*/Builder.getFalse()}, 2824 /*FMFSource=*/nullptr, Val->getName() + ".numleadingzeros"); 2825 Value *ValNumActiveBits = Builder.CreateSub( 2826 ConstantInt::get(Ty, Ty->getScalarSizeInBits()), ValNumLeadingZeros, 2827 Val->getName() + ".numactivebits", /*HasNUW=*/true, 2828 /*HasNSW=*/Bitwidth != 2); 2829 2830 SCEVExpander Expander(*SE, *DL, "loop-idiom"); 2831 Expander.setInsertPoint(&*Builder.GetInsertPoint()); 2832 Value *ExtraOffset = Expander.expandCodeFor(ExtraOffsetExpr); 2833 2834 Value *ValNumActiveBitsOffset = Builder.CreateAdd( 2835 ValNumActiveBits, ExtraOffset, ValNumActiveBits->getName() + ".offset", 2836 /*HasNUW=*/OffsetIsZero, /*HasNSW=*/true); 2837 Value *IVFinal = Builder.CreateIntrinsic(Intrinsic::smax, {Ty}, 2838 {ValNumActiveBitsOffset, Start}, 2839 /*FMFSource=*/nullptr, "iv.final"); 2840 2841 auto *LoopBackedgeTakenCount = cast<Instruction>(Builder.CreateSub( 2842 IVFinal, Start, CurLoop->getName() + ".backedgetakencount", 2843 /*HasNUW=*/OffsetIsZero, /*HasNSW=*/true)); 2844 // FIXME: or when the offset was `add nuw` 2845 2846 // We know loop's backedge-taken count, but what's loop's trip count? 2847 Value *LoopTripCount = 2848 Builder.CreateAdd(LoopBackedgeTakenCount, ConstantInt::get(Ty, 1), 2849 CurLoop->getName() + ".tripcount", /*HasNUW=*/true, 2850 /*HasNSW=*/Bitwidth != 2); 2851 2852 // Step 2: Adjust the successor basic block to recieve the original 2853 // induction variable's final value instead of the orig. IV itself. 2854 2855 IV->replaceUsesOutsideBlock(IVFinal, LoopHeaderBB); 2856 2857 // Step 3: Rewrite the loop into a countable form, with canonical IV. 2858 2859 // The new canonical induction variable. 2860 Builder.SetInsertPoint(&LoopHeaderBB->front()); 2861 auto *CIV = Builder.CreatePHI(Ty, 2, CurLoop->getName() + ".iv"); 2862 2863 // The induction itself. 2864 Builder.SetInsertPoint(LoopHeaderBB->getFirstNonPHI()); 2865 auto *CIVNext = 2866 Builder.CreateAdd(CIV, ConstantInt::get(Ty, 1), CIV->getName() + ".next", 2867 /*HasNUW=*/true, /*HasNSW=*/Bitwidth != 2); 2868 2869 // The loop trip count check. 2870 auto *CIVCheck = Builder.CreateICmpEQ(CIVNext, LoopTripCount, 2871 CurLoop->getName() + ".ivcheck"); 2872 auto *NewIVCheck = CIVCheck; 2873 if (InvertedCond) { 2874 NewIVCheck = Builder.CreateNot(CIVCheck); 2875 NewIVCheck->takeName(ValShiftedIsZero); 2876 } 2877 2878 // The original IV, but rebased to be an offset to the CIV. 2879 auto *IVDePHId = Builder.CreateAdd(CIV, Start, "", /*HasNUW=*/false, 2880 /*HasNSW=*/true); // FIXME: what about NUW? 2881 IVDePHId->takeName(IV); 2882 2883 // The loop terminator. 2884 Builder.SetInsertPoint(LoopHeaderBB->getTerminator()); 2885 Builder.CreateCondBr(CIVCheck, SuccessorBB, LoopHeaderBB); 2886 LoopHeaderBB->getTerminator()->eraseFromParent(); 2887 2888 // Populate the IV PHI. 2889 CIV->addIncoming(ConstantInt::get(Ty, 0), LoopPreheaderBB); 2890 CIV->addIncoming(CIVNext, LoopHeaderBB); 2891 2892 // Step 4: Forget the "non-computable" trip-count SCEV associated with the 2893 // loop. The loop would otherwise not be deleted even if it becomes empty. 2894 2895 SE->forgetLoop(CurLoop); 2896 2897 // Step 5: Try to cleanup the loop's body somewhat. 2898 IV->replaceAllUsesWith(IVDePHId); 2899 IV->eraseFromParent(); 2900 2901 ValShiftedIsZero->replaceAllUsesWith(NewIVCheck); 2902 ValShiftedIsZero->eraseFromParent(); 2903 2904 // Other passes will take care of actually deleting the loop if possible. 2905 2906 LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-zero idiom optimized!\n"); 2907 2908 ++NumShiftUntilZero; 2909 return MadeChange; 2910 } 2911