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: memcmp, etc.
24//
25// This could recognize common matrix multiplies and dot product idioms and
26// replace them with calls to BLAS (if linked in??).
27//
28//===----------------------------------------------------------------------===//
29
30#include "llvm/Transforms/Scalar/LoopIdiomRecognize.h"
31#include "llvm/ADT/APInt.h"
32#include "llvm/ADT/ArrayRef.h"
33#include "llvm/ADT/DenseMap.h"
34#include "llvm/ADT/MapVector.h"
35#include "llvm/ADT/SetVector.h"
36#include "llvm/ADT/SmallPtrSet.h"
37#include "llvm/ADT/SmallVector.h"
38#include "llvm/ADT/Statistic.h"
39#include "llvm/ADT/StringRef.h"
40#include "llvm/Analysis/AliasAnalysis.h"
41#include "llvm/Analysis/CmpInstAnalysis.h"
42#include "llvm/Analysis/HashRecognize.h"
43#include "llvm/Analysis/LoopAccessAnalysis.h"
44#include "llvm/Analysis/LoopInfo.h"
45#include "llvm/Analysis/LoopPass.h"
46#include "llvm/Analysis/MemoryLocation.h"
47#include "llvm/Analysis/MemorySSA.h"
48#include "llvm/Analysis/MemorySSAUpdater.h"
49#include "llvm/Analysis/MustExecute.h"
50#include "llvm/Analysis/OptimizationRemarkEmitter.h"
51#include "llvm/Analysis/ScalarEvolution.h"
52#include "llvm/Analysis/ScalarEvolutionExpressions.h"
53#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
54#include "llvm/Analysis/TargetLibraryInfo.h"
55#include "llvm/Analysis/TargetTransformInfo.h"
56#include "llvm/Analysis/ValueTracking.h"
57#include "llvm/IR/BasicBlock.h"
58#include "llvm/IR/Constant.h"
59#include "llvm/IR/Constants.h"
60#include "llvm/IR/DataLayout.h"
61#include "llvm/IR/DebugLoc.h"
62#include "llvm/IR/DerivedTypes.h"
63#include "llvm/IR/Dominators.h"
64#include "llvm/IR/GlobalValue.h"
65#include "llvm/IR/GlobalVariable.h"
66#include "llvm/IR/IRBuilder.h"
67#include "llvm/IR/InstrTypes.h"
68#include "llvm/IR/Instruction.h"
69#include "llvm/IR/Instructions.h"
70#include "llvm/IR/IntrinsicInst.h"
71#include "llvm/IR/Intrinsics.h"
72#include "llvm/IR/LLVMContext.h"
73#include "llvm/IR/Module.h"
74#include "llvm/IR/PassManager.h"
75#include "llvm/IR/PatternMatch.h"
76#include "llvm/IR/ProfDataUtils.h"
77#include "llvm/IR/Type.h"
78#include "llvm/IR/User.h"
79#include "llvm/IR/Value.h"
80#include "llvm/IR/ValueHandle.h"
81#include "llvm/Support/Casting.h"
82#include "llvm/Support/CommandLine.h"
83#include "llvm/Support/Debug.h"
84#include "llvm/Support/InstructionCost.h"
85#include "llvm/Support/raw_ostream.h"
86#include "llvm/Transforms/Utils/BuildLibCalls.h"
87#include "llvm/Transforms/Utils/Local.h"
88#include "llvm/Transforms/Utils/LoopUtils.h"
89#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
90#include <algorithm>
91#include <cassert>
92#include <cstdint>
93#include <utility>
94
95using namespace llvm;
96using namespace SCEVPatternMatch;
97
98#define DEBUG_TYPE "loop-idiom"
99
100STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
101STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores");
102STATISTIC(NumMemMove, "Number of memmove's formed from loop load+stores");
103STATISTIC(NumStrLen, "Number of strlen's and wcslen's formed from loop loads");
104STATISTIC(
105 NumShiftUntilBitTest,
106 "Number of uncountable loops recognized as 'shift until bitttest' idiom");
107STATISTIC(NumShiftUntilZero,
108 "Number of uncountable loops recognized as 'shift until zero' idiom");
109
110namespace llvm {
111bool DisableLIRP::All;
112static cl::opt<bool, true>
113 DisableLIRPAll("disable-" DEBUG_TYPE "-all",
114 cl::desc("Options to disable Loop Idiom Recognize Pass."),
115 cl::location(L&: DisableLIRP::All), cl::init(Val: false),
116 cl::ReallyHidden);
117
118bool DisableLIRP::Memset;
119static cl::opt<bool, true>
120 DisableLIRPMemset("disable-" DEBUG_TYPE "-memset",
121 cl::desc("Proceed with loop idiom recognize pass, but do "
122 "not convert loop(s) to memset."),
123 cl::location(L&: DisableLIRP::Memset), cl::init(Val: false),
124 cl::ReallyHidden);
125
126bool DisableLIRP::Memcpy;
127static cl::opt<bool, true>
128 DisableLIRPMemcpy("disable-" DEBUG_TYPE "-memcpy",
129 cl::desc("Proceed with loop idiom recognize pass, but do "
130 "not convert loop(s) to memcpy."),
131 cl::location(L&: DisableLIRP::Memcpy), cl::init(Val: false),
132 cl::ReallyHidden);
133
134bool DisableLIRP::Strlen;
135static cl::opt<bool, true>
136 DisableLIRPStrlen("disable-loop-idiom-strlen",
137 cl::desc("Proceed with loop idiom recognize pass, but do "
138 "not convert loop(s) to strlen."),
139 cl::location(L&: DisableLIRP::Strlen), cl::init(Val: false),
140 cl::ReallyHidden);
141
142bool DisableLIRP::Wcslen;
143static cl::opt<bool, true>
144 EnableLIRPWcslen("disable-loop-idiom-wcslen",
145 cl::desc("Proceed with loop idiom recognize pass, "
146 "enable conversion of loop(s) to wcslen."),
147 cl::location(L&: DisableLIRP::Wcslen), cl::init(Val: false),
148 cl::ReallyHidden);
149
150bool DisableLIRP::HashRecognize;
151static cl::opt<bool, true>
152 DisableLIRPHashRecognize("disable-" DEBUG_TYPE "-hashrecognize",
153 cl::desc("Proceed with loop idiom recognize pass, "
154 "but do not optimize CRC loops."),
155 cl::location(L&: DisableLIRP::HashRecognize),
156 cl::init(Val: false), cl::ReallyHidden);
157
158static cl::opt<bool> UseLIRCodeSizeHeurs(
159 "use-lir-code-size-heurs",
160 cl::desc("Use loop idiom recognition code size heuristics when compiling "
161 "with -Os/-Oz"),
162 cl::init(Val: true), cl::Hidden);
163
164static cl::opt<bool> ForceMemsetPatternIntrinsic(
165 "loop-idiom-force-memset-pattern-intrinsic",
166 cl::desc("Use memset.pattern intrinsic whenever possible"), cl::init(Val: false),
167 cl::Hidden);
168
169extern cl::opt<bool> ProfcheckDisableMetadataFixes;
170
171} // namespace llvm
172
173namespace {
174
175class LoopIdiomRecognize {
176 Loop *CurLoop = nullptr;
177 AliasAnalysis *AA;
178 DominatorTree *DT;
179 LoopInfo *LI;
180 ScalarEvolution *SE;
181 TargetLibraryInfo *TLI;
182 const TargetTransformInfo *TTI;
183 const DataLayout *DL;
184 OptimizationRemarkEmitter &ORE;
185 bool ApplyCodeSizeHeuristics;
186 std::unique_ptr<MemorySSAUpdater> MSSAU;
187
188public:
189 explicit LoopIdiomRecognize(AliasAnalysis *AA, DominatorTree *DT,
190 LoopInfo *LI, ScalarEvolution *SE,
191 TargetLibraryInfo *TLI,
192 const TargetTransformInfo *TTI, MemorySSA *MSSA,
193 const DataLayout *DL,
194 OptimizationRemarkEmitter &ORE)
195 : AA(AA), DT(DT), LI(LI), SE(SE), TLI(TLI), TTI(TTI), DL(DL), ORE(ORE) {
196 if (MSSA)
197 MSSAU = std::make_unique<MemorySSAUpdater>(args&: MSSA);
198 }
199
200 bool runOnLoop(Loop *L);
201
202private:
203 using StoreList = SmallVector<StoreInst *, 8>;
204 using StoreListMap = MapVector<Value *, StoreList>;
205
206 StoreListMap StoreRefsForMemset;
207 StoreListMap StoreRefsForMemsetPattern;
208 StoreList StoreRefsForMemcpy;
209 bool HasMemset;
210 bool HasMemsetPattern;
211 bool HasMemcpy;
212
213 /// Return code for isLegalStore()
214 enum LegalStoreKind {
215 None = 0,
216 Memset,
217 MemsetPattern,
218 Memcpy,
219 UnorderedAtomicMemcpy,
220 DontUse // Dummy retval never to be used. Allows catching errors in retval
221 // handling.
222 };
223
224 /// \name Countable Loop Idiom Handling
225 /// @{
226
227 bool runOnCountableLoop();
228 bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
229 SmallVectorImpl<BasicBlock *> &ExitBlocks);
230
231 void collectStores(BasicBlock *BB);
232 LegalStoreKind isLegalStore(StoreInst *SI);
233 enum class ForMemset { No, Yes };
234 bool processLoopStores(SmallVectorImpl<StoreInst *> &SL, const SCEV *BECount,
235 ForMemset For);
236
237 template <typename MemInst>
238 bool processLoopMemIntrinsic(
239 BasicBlock *BB,
240 bool (LoopIdiomRecognize::*Processor)(MemInst *, const SCEV *),
241 const SCEV *BECount);
242 bool processLoopMemCpy(MemCpyInst *MCI, const SCEV *BECount);
243 bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
244
245 bool processLoopStridedStore(Value *DestPtr, const SCEV *StoreSizeSCEV,
246 MaybeAlign StoreAlignment, Value *StoredVal,
247 Instruction *TheStore,
248 SmallPtrSetImpl<Instruction *> &Stores,
249 const SCEVAddRecExpr *Ev, const SCEV *BECount,
250 bool IsNegStride, bool IsLoopMemset = false);
251 bool processLoopStoreOfLoopLoad(StoreInst *SI, const SCEV *BECount);
252 bool processLoopStoreOfLoopLoad(Value *DestPtr, Value *SourcePtr,
253 const SCEV *StoreSize, MaybeAlign StoreAlign,
254 MaybeAlign LoadAlign, Instruction *TheStore,
255 Instruction *TheLoad,
256 const SCEVAddRecExpr *StoreEv,
257 const SCEVAddRecExpr *LoadEv,
258 const SCEV *BECount);
259 bool avoidLIRForMultiBlockLoop(bool IsMemset = false,
260 bool IsLoopMemset = false);
261 bool optimizeCRCLoop(const PolynomialInfo &Info);
262
263 /// @}
264 /// \name Noncountable Loop Idiom Handling
265 /// @{
266
267 bool runOnNoncountableLoop();
268
269 bool recognizePopcount();
270 void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst,
271 PHINode *CntPhi, Value *Var);
272 bool isProfitableToInsertFFS(Intrinsic::ID IntrinID, Value *InitX,
273 bool ZeroCheck, size_t CanonicalSize);
274 bool insertFFSIfProfitable(Intrinsic::ID IntrinID, Value *InitX,
275 Instruction *DefX, PHINode *CntPhi,
276 Instruction *CntInst);
277 bool recognizeAndInsertFFS(); /// Find First Set: ctlz or cttz
278 bool recognizeShiftUntilLessThan();
279 void transformLoopToCountable(Intrinsic::ID IntrinID, BasicBlock *PreCondBB,
280 Instruction *CntInst, PHINode *CntPhi,
281 Value *Var, Instruction *DefX,
282 const DebugLoc &DL, bool ZeroCheck,
283 bool IsCntPhiUsedOutsideLoop,
284 bool InsertSub = false);
285
286 bool recognizeShiftUntilBitTest();
287 bool recognizeShiftUntilZero();
288 bool recognizeAndInsertStrLen();
289
290 /// @}
291};
292} // end anonymous namespace
293
294PreservedAnalyses LoopIdiomRecognizePass::run(Loop &L, LoopAnalysisManager &AM,
295 LoopStandardAnalysisResults &AR,
296 LPMUpdater &) {
297 if (DisableLIRP::All)
298 return PreservedAnalyses::all();
299
300 const auto *DL = &L.getHeader()->getDataLayout();
301
302 // For the new PM, we also can't use OptimizationRemarkEmitter as an analysis
303 // pass. Function analyses need to be preserved across loop transformations
304 // but ORE cannot be preserved (see comment before the pass definition).
305 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
306
307 LoopIdiomRecognize LIR(&AR.AA, &AR.DT, &AR.LI, &AR.SE, &AR.TLI, &AR.TTI,
308 AR.MSSA, DL, ORE);
309 if (!LIR.runOnLoop(L: &L))
310 return PreservedAnalyses::all();
311
312 auto PA = getLoopPassPreservedAnalyses();
313 if (AR.MSSA)
314 PA.preserve<MemorySSAAnalysis>();
315 return PA;
316}
317
318static void deleteDeadInstruction(Instruction *I) {
319 I->replaceAllUsesWith(V: PoisonValue::get(T: I->getType()));
320 I->eraseFromParent();
321}
322
323//===----------------------------------------------------------------------===//
324//
325// Implementation of LoopIdiomRecognize
326//
327//===----------------------------------------------------------------------===//
328
329bool LoopIdiomRecognize::runOnLoop(Loop *L) {
330 CurLoop = L;
331 // If the loop could not be converted to canonical form, it must have an
332 // indirectbr in it, just give up.
333 if (!L->getLoopPreheader())
334 return false;
335
336 // Disable loop idiom recognition if the function's name is a common idiom.
337 StringRef Name = L->getHeader()->getParent()->getName();
338 if (Name == "memset" || Name == "memcpy" || Name == "strlen" ||
339 Name == "wcslen")
340 return false;
341
342 // Determine if code size heuristics need to be applied.
343 ApplyCodeSizeHeuristics =
344 L->getHeader()->getParent()->hasOptSize() && UseLIRCodeSizeHeurs;
345
346 HasMemset = TLI->has(F: LibFunc_memset);
347 // TODO: Unconditionally enable use of the memset pattern intrinsic (or at
348 // least, opt-in via target hook) once we are confident it will never result
349 // in worse codegen than without. For now, use it only when the target
350 // supports memset_pattern16 libcall (or unless this is overridden by
351 // command line option).
352 HasMemsetPattern = TLI->has(F: LibFunc_memset_pattern16);
353 HasMemcpy = TLI->has(F: LibFunc_memcpy);
354
355 if (HasMemset || HasMemsetPattern || ForceMemsetPatternIntrinsic ||
356 HasMemcpy || !DisableLIRP::HashRecognize)
357 if (SE->hasLoopInvariantBackedgeTakenCount(L))
358 return runOnCountableLoop();
359
360 return runOnNoncountableLoop();
361}
362
363bool LoopIdiomRecognize::runOnCountableLoop() {
364 const SCEV *BECount = SE->getBackedgeTakenCount(L: CurLoop);
365 assert(!isa<SCEVCouldNotCompute>(BECount) &&
366 "runOnCountableLoop() called on a loop without a predictable"
367 "backedge-taken count");
368
369 // If this loop executes exactly one time, then it should be peeled, not
370 // optimized by this pass.
371 if (BECount->isZero())
372 return false;
373
374 SmallVector<BasicBlock *, 8> ExitBlocks;
375 CurLoop->getUniqueExitBlocks(ExitBlocks);
376
377 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["
378 << CurLoop->getHeader()->getParent()->getName()
379 << "] Countable Loop %" << CurLoop->getHeader()->getName()
380 << "\n");
381
382 // The following transforms hoist stores/memsets into the loop pre-header.
383 // Give up if the loop has instructions that may throw.
384 SimpleLoopSafetyInfo SafetyInfo;
385 SafetyInfo.computeLoopSafetyInfo(CurLoop);
386 if (SafetyInfo.anyBlockMayThrow())
387 return false;
388
389 bool MadeChange = false;
390
391 // Scan all the blocks in the loop that are not in subloops.
392 for (auto *BB : CurLoop->getBlocks()) {
393 // Ignore blocks in subloops.
394 if (LI->getLoopFor(BB) != CurLoop)
395 continue;
396
397 MadeChange |= runOnLoopBlock(BB, BECount, ExitBlocks);
398 }
399
400 // Optimize a CRC loop if HashRecognize found one, provided we're not
401 // optimizing for size.
402 if (!DisableLIRP::HashRecognize && !ApplyCodeSizeHeuristics)
403 if (auto Res = HashRecognize(*CurLoop, *SE).getResult())
404 optimizeCRCLoop(Info: *Res);
405
406 return MadeChange;
407}
408
409static APInt getStoreStride(const SCEVAddRecExpr *StoreEv) {
410 const SCEVConstant *ConstStride = cast<SCEVConstant>(Val: StoreEv->getOperand(i: 1));
411 return ConstStride->getAPInt();
412}
413
414/// getMemSetPatternValue - If a strided store of the specified value is safe to
415/// turn into a memset.patternn intrinsic, return the Constant that should
416/// be passed in. Otherwise, return null.
417///
418/// TODO this function could allow more constants than it does today (e.g.
419/// those over 16 bytes) now it has transitioned to being used for the
420/// memset.pattern intrinsic rather than directly the memset_pattern16
421/// libcall.
422static Constant *getMemSetPatternValue(Value *V, const DataLayout *DL) {
423 // FIXME: This could check for UndefValue because it can be merged into any
424 // other valid pattern.
425
426 // If the value isn't a constant, we can't promote it to being in a constant
427 // array. We could theoretically do a store to an alloca or something, but
428 // that doesn't seem worthwhile.
429 Constant *C = dyn_cast<Constant>(Val: V);
430 if (!C || isa<ConstantExpr>(Val: C))
431 return nullptr;
432
433 // Only handle simple values that are a power of two bytes in size.
434 uint64_t Size = DL->getTypeSizeInBits(Ty: V->getType());
435 if (Size == 0 || (Size & 7) || (Size & (Size - 1)))
436 return nullptr;
437
438 // Don't care enough about darwin/ppc to implement this.
439 if (DL->isBigEndian())
440 return nullptr;
441
442 // Convert to size in bytes.
443 Size /= 8;
444
445 // TODO: If CI is larger than 16-bytes, we can try slicing it in half to see
446 // if the top and bottom are the same (e.g. for vectors and large integers).
447 if (Size > 16)
448 return nullptr;
449
450 // For now, don't handle types that aren't int, floats, or pointers.
451 Type *CTy = C->getType();
452 if (!CTy->isIntOrPtrTy() && !CTy->isFloatingPointTy())
453 return nullptr;
454
455 return C;
456}
457
458LoopIdiomRecognize::LegalStoreKind
459LoopIdiomRecognize::isLegalStore(StoreInst *SI) {
460 // Don't touch volatile stores.
461 if (SI->isVolatile())
462 return LegalStoreKind::None;
463 // We only want simple or unordered-atomic stores.
464 if (!SI->isUnordered())
465 return LegalStoreKind::None;
466
467 // Avoid merging nontemporal stores.
468 if (SI->getMetadata(KindID: LLVMContext::MD_nontemporal))
469 return LegalStoreKind::None;
470
471 Value *StoredVal = SI->getValueOperand();
472 Value *StorePtr = SI->getPointerOperand();
473
474 if (DL->hasUnstableRepresentation(Ty: StoredVal->getType()))
475 return LegalStoreKind::None;
476
477 // Transformations could invalidate the external-state pointers
478 // memcpy - LangRef specifies that a valid memcpy must preserve external
479 // state, so no transformations are blocked by it.
480 // memset - We assume that a memset of 0 has an equivalent external state
481 // effect as a null pointer store. This is currently not explicitly
482 // specified, but is true of the one exemplar we have (CHERI
483 // capabilities). All other memset formations are not safe.
484 bool MustPreserveExternalState = DL->hasExternalState(Ty: StoredVal->getType()) &&
485 !isa<ConstantPointerNull>(Val: StoredVal);
486
487 // Reject stores that are so large that they overflow an unsigned.
488 // When storing out scalable vectors we bail out for now, since the code
489 // below currently only works for constant strides.
490 TypeSize SizeInBits = DL->getTypeSizeInBits(Ty: StoredVal->getType());
491 if (SizeInBits.isScalable() || (SizeInBits.getFixedValue() & 7) ||
492 (SizeInBits.getFixedValue() >> 32) != 0)
493 return LegalStoreKind::None;
494
495 // See if the pointer expression is an AddRec like {base,+,1} on the current
496 // loop, which indicates a strided store. If we have something else, it's a
497 // random store we can't handle.
498 const SCEV *StoreEv = SE->getSCEV(V: StorePtr);
499 const SCEVConstant *Stride;
500 if (!match(S: StoreEv, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEVConstant(V&: Stride),
501 L: m_SpecificLoop(L: CurLoop))))
502 return LegalStoreKind::None;
503
504 // See if the store can be turned into a memset.
505
506 // If the stored value is a byte-wise value (like i32 -1), then it may be
507 // turned into a memset of i8 -1, assuming that all the consecutive bytes
508 // are stored. A store of i32 0x01020304 can never be turned into a memset,
509 // but it can be turned into memset_pattern if the target supports it.
510 Value *SplatValue = isBytewiseValue(V: StoredVal, DL: *DL);
511
512 // Note: memset and memset_pattern on unordered-atomic is yet not supported
513 bool UnorderedAtomic = SI->isUnordered() && !SI->isSimple();
514
515 // If we're allowed to form a memset, and the stored value would be
516 // acceptable for memset, use it.
517 if (!MustPreserveExternalState && !UnorderedAtomic && HasMemset &&
518 SplatValue && !DisableLIRP::Memset &&
519 // Verify that the stored value is loop invariant. If not, we can't
520 // promote the memset.
521 CurLoop->isLoopInvariant(V: SplatValue)) {
522 // It looks like we can use SplatValue.
523 return LegalStoreKind::Memset;
524 }
525 if (!MustPreserveExternalState && !UnorderedAtomic &&
526 (HasMemsetPattern || ForceMemsetPatternIntrinsic) &&
527 !DisableLIRP::Memset &&
528 // Don't create memset_pattern16s with address spaces.
529 StorePtr->getType()->getPointerAddressSpace() == 0 &&
530 getMemSetPatternValue(V: StoredVal, DL)) {
531 // It looks like we can use PatternValue!
532 return LegalStoreKind::MemsetPattern;
533 }
534
535 // Otherwise, see if the store can be turned into a memcpy.
536 if (HasMemcpy && !DisableLIRP::Memcpy) {
537 // Check to see if the stride matches the size of the store. If so, then we
538 // know that every byte is touched in the loop.
539 unsigned StoreSize = DL->getTypeStoreSize(Ty: SI->getValueOperand()->getType());
540 APInt StrideAP = Stride->getAPInt();
541 if (StoreSize != StrideAP && StoreSize != -StrideAP)
542 return LegalStoreKind::None;
543
544 // The store must be feeding a non-volatile load.
545 LoadInst *LI = dyn_cast<LoadInst>(Val: SI->getValueOperand());
546
547 // Only allow non-volatile loads
548 if (!LI || LI->isVolatile())
549 return LegalStoreKind::None;
550 // Only allow simple or unordered-atomic loads
551 if (!LI->isUnordered())
552 return LegalStoreKind::None;
553
554 // See if the pointer expression is an AddRec like {base,+,1} on the current
555 // loop, which indicates a strided load. If we have something else, it's a
556 // random load we can't handle.
557 const SCEV *LoadEv = SE->getSCEV(V: LI->getPointerOperand());
558
559 // The store and load must share the same stride.
560 if (!match(S: LoadEv, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_scev_Specific(S: Stride),
561 L: m_SpecificLoop(L: CurLoop))))
562 return LegalStoreKind::None;
563
564 // Success. This store can be converted into a memcpy.
565 UnorderedAtomic = UnorderedAtomic || LI->isAtomic();
566 return UnorderedAtomic ? LegalStoreKind::UnorderedAtomicMemcpy
567 : LegalStoreKind::Memcpy;
568 }
569 // This store can't be transformed into a memset/memcpy.
570 return LegalStoreKind::None;
571}
572
573void LoopIdiomRecognize::collectStores(BasicBlock *BB) {
574 StoreRefsForMemset.clear();
575 StoreRefsForMemsetPattern.clear();
576 StoreRefsForMemcpy.clear();
577 for (Instruction &I : *BB) {
578 StoreInst *SI = dyn_cast<StoreInst>(Val: &I);
579 if (!SI)
580 continue;
581
582 // Make sure this is a strided store with a constant stride.
583 switch (isLegalStore(SI)) {
584 case LegalStoreKind::None:
585 // Nothing to do
586 break;
587 case LegalStoreKind::Memset: {
588 // Find the base pointer.
589 Value *Ptr = getUnderlyingObject(V: SI->getPointerOperand());
590 StoreRefsForMemset[Ptr].push_back(Elt: SI);
591 } break;
592 case LegalStoreKind::MemsetPattern: {
593 // Find the base pointer.
594 Value *Ptr = getUnderlyingObject(V: SI->getPointerOperand());
595 StoreRefsForMemsetPattern[Ptr].push_back(Elt: SI);
596 } break;
597 case LegalStoreKind::Memcpy:
598 case LegalStoreKind::UnorderedAtomicMemcpy:
599 StoreRefsForMemcpy.push_back(Elt: SI);
600 break;
601 default:
602 assert(false && "unhandled return value");
603 break;
604 }
605 }
606}
607
608/// runOnLoopBlock - Process the specified block, which lives in a counted loop
609/// with the specified backedge count. This block is known to be in the current
610/// loop and not in any subloops.
611bool LoopIdiomRecognize::runOnLoopBlock(
612 BasicBlock *BB, const SCEV *BECount,
613 SmallVectorImpl<BasicBlock *> &ExitBlocks) {
614 // We can only promote stores in this block if they are unconditionally
615 // executed in the loop. For a block to be unconditionally executed, it has
616 // to dominate all the exit blocks of the loop. Verify this now.
617 for (BasicBlock *ExitBlock : ExitBlocks)
618 if (!DT->dominates(A: BB, B: ExitBlock))
619 return false;
620
621 bool MadeChange = false;
622 // Look for store instructions, which may be optimized to memset/memcpy.
623 collectStores(BB);
624
625 // Look for a single store or sets of stores with a common base, which can be
626 // optimized into a memset (memset_pattern). The latter most commonly happens
627 // with structs and handunrolled loops.
628 for (auto &SL : StoreRefsForMemset)
629 MadeChange |= processLoopStores(SL&: SL.second, BECount, For: ForMemset::Yes);
630
631 for (auto &SL : StoreRefsForMemsetPattern)
632 MadeChange |= processLoopStores(SL&: SL.second, BECount, For: ForMemset::No);
633
634 // Optimize the store into a memcpy, if it feeds an similarly strided load.
635 for (auto &SI : StoreRefsForMemcpy)
636 MadeChange |= processLoopStoreOfLoopLoad(SI, BECount);
637
638 MadeChange |= processLoopMemIntrinsic<MemCpyInst>(
639 BB, Processor: &LoopIdiomRecognize::processLoopMemCpy, BECount);
640 MadeChange |= processLoopMemIntrinsic<MemSetInst>(
641 BB, Processor: &LoopIdiomRecognize::processLoopMemSet, BECount);
642
643 return MadeChange;
644}
645
646/// See if this store(s) can be promoted to a memset.
647bool LoopIdiomRecognize::processLoopStores(SmallVectorImpl<StoreInst *> &SL,
648 const SCEV *BECount, ForMemset For) {
649 // Try to find consecutive stores that can be transformed into memsets.
650 SetVector<StoreInst *> Heads, Tails;
651 SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain;
652
653 // Do a quadratic search on all of the given stores and find
654 // all of the pairs of stores that follow each other.
655 SmallVector<unsigned, 16> IndexQueue;
656 for (unsigned i = 0, e = SL.size(); i < e; ++i) {
657 assert(SL[i]->isSimple() && "Expected only non-volatile stores.");
658
659 Value *FirstStoredVal = SL[i]->getValueOperand();
660 Value *FirstStorePtr = SL[i]->getPointerOperand();
661 const SCEVAddRecExpr *FirstStoreEv =
662 cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: FirstStorePtr));
663 APInt FirstStride = getStoreStride(StoreEv: FirstStoreEv);
664 unsigned FirstStoreSize = DL->getTypeStoreSize(Ty: SL[i]->getValueOperand()->getType());
665
666 // See if we can optimize just this store in isolation.
667 if (FirstStride == FirstStoreSize || -FirstStride == FirstStoreSize) {
668 Heads.insert(X: SL[i]);
669 continue;
670 }
671
672 Value *FirstSplatValue = nullptr;
673 Constant *FirstPatternValue = nullptr;
674
675 if (For == ForMemset::Yes)
676 FirstSplatValue = isBytewiseValue(V: FirstStoredVal, DL: *DL);
677 else
678 FirstPatternValue = getMemSetPatternValue(V: FirstStoredVal, DL);
679
680 assert((FirstSplatValue || FirstPatternValue) &&
681 "Expected either splat value or pattern value.");
682
683 IndexQueue.clear();
684 // If a store has multiple consecutive store candidates, search Stores
685 // array according to the sequence: from i+1 to e, then from i-1 to 0.
686 // This is because usually pairing with immediate succeeding or preceding
687 // candidate create the best chance to find memset opportunity.
688 unsigned j = 0;
689 for (j = i + 1; j < e; ++j)
690 IndexQueue.push_back(Elt: j);
691 for (j = i; j > 0; --j)
692 IndexQueue.push_back(Elt: j - 1);
693
694 for (auto &k : IndexQueue) {
695 assert(SL[k]->isSimple() && "Expected only non-volatile stores.");
696 Value *SecondStorePtr = SL[k]->getPointerOperand();
697 const SCEVAddRecExpr *SecondStoreEv =
698 cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: SecondStorePtr));
699 APInt SecondStride = getStoreStride(StoreEv: SecondStoreEv);
700
701 if (FirstStride != SecondStride)
702 continue;
703
704 Value *SecondStoredVal = SL[k]->getValueOperand();
705 Value *SecondSplatValue = nullptr;
706 Constant *SecondPatternValue = nullptr;
707
708 if (For == ForMemset::Yes)
709 SecondSplatValue = isBytewiseValue(V: SecondStoredVal, DL: *DL);
710 else
711 SecondPatternValue = getMemSetPatternValue(V: SecondStoredVal, DL);
712
713 assert((SecondSplatValue || SecondPatternValue) &&
714 "Expected either splat value or pattern value.");
715
716 if (isConsecutiveAccess(A: SL[i], B: SL[k], DL: *DL, SE&: *SE, CheckType: false)) {
717 if (For == ForMemset::Yes) {
718 if (isa<UndefValue>(Val: FirstSplatValue))
719 FirstSplatValue = SecondSplatValue;
720 if (FirstSplatValue != SecondSplatValue)
721 continue;
722 } else {
723 if (isa<UndefValue>(Val: FirstPatternValue))
724 FirstPatternValue = SecondPatternValue;
725 if (FirstPatternValue != SecondPatternValue)
726 continue;
727 }
728 Tails.insert(X: SL[k]);
729 Heads.insert(X: SL[i]);
730 ConsecutiveChain[SL[i]] = SL[k];
731 break;
732 }
733 }
734 }
735
736 // We may run into multiple chains that merge into a single chain. We mark the
737 // stores that we transformed so that we don't visit the same store twice.
738 SmallPtrSet<Value *, 16> TransformedStores;
739 bool Changed = false;
740
741 // For stores that start but don't end a link in the chain:
742 for (StoreInst *I : Heads) {
743 if (Tails.count(key: I))
744 continue;
745
746 // We found a store instr that starts a chain. Now follow the chain and try
747 // to transform it.
748 SmallPtrSet<Instruction *, 8> AdjacentStores;
749 StoreInst *HeadStore = I;
750 unsigned StoreSize = 0;
751
752 // Collect the chain into a list.
753 while (Tails.count(key: I) || Heads.count(key: I)) {
754 if (TransformedStores.count(Ptr: I))
755 break;
756 AdjacentStores.insert(Ptr: I);
757
758 StoreSize += DL->getTypeStoreSize(Ty: I->getValueOperand()->getType());
759 // Move to the next value in the chain.
760 I = ConsecutiveChain[I];
761 }
762
763 Value *StoredVal = HeadStore->getValueOperand();
764 Value *StorePtr = HeadStore->getPointerOperand();
765 const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: StorePtr));
766 APInt Stride = getStoreStride(StoreEv);
767
768 // Check to see if the stride matches the size of the stores. If so, then
769 // we know that every byte is touched in the loop.
770 if (StoreSize != Stride && StoreSize != -Stride)
771 continue;
772
773 bool IsNegStride = StoreSize == -Stride;
774
775 Type *IntIdxTy = DL->getIndexType(PtrTy: StorePtr->getType());
776 const SCEV *StoreSizeSCEV = SE->getConstant(Ty: IntIdxTy, V: StoreSize);
777 if (processLoopStridedStore(DestPtr: StorePtr, StoreSizeSCEV,
778 StoreAlignment: MaybeAlign(HeadStore->getAlign()), StoredVal,
779 TheStore: HeadStore, Stores&: AdjacentStores, Ev: StoreEv, BECount,
780 IsNegStride)) {
781 TransformedStores.insert_range(R&: AdjacentStores);
782 Changed = true;
783 }
784 }
785
786 return Changed;
787}
788
789/// processLoopMemIntrinsic - Template function for calling different processor
790/// functions based on mem intrinsic type.
791template <typename MemInst>
792bool LoopIdiomRecognize::processLoopMemIntrinsic(
793 BasicBlock *BB,
794 bool (LoopIdiomRecognize::*Processor)(MemInst *, const SCEV *),
795 const SCEV *BECount) {
796 bool MadeChange = false;
797 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
798 Instruction *Inst = &*I++;
799 // Look for memory instructions, which may be optimized to a larger one.
800 if (MemInst *MI = dyn_cast<MemInst>(Inst)) {
801 WeakTrackingVH InstPtr(&*I);
802 if (!(this->*Processor)(MI, BECount))
803 continue;
804 MadeChange = true;
805
806 // If processing the instruction invalidated our iterator, start over from
807 // the top of the block.
808 if (!InstPtr)
809 I = BB->begin();
810 }
811 }
812 return MadeChange;
813}
814
815/// processLoopMemCpy - See if this memcpy can be promoted to a large memcpy
816bool LoopIdiomRecognize::processLoopMemCpy(MemCpyInst *MCI,
817 const SCEV *BECount) {
818 // We can only handle non-volatile memcpys with a constant size.
819 if (MCI->isVolatile() || !isa<ConstantInt>(Val: MCI->getLength()))
820 return false;
821
822 // If we're not allowed to hack on memcpy, we fail.
823 if ((!HasMemcpy && !MCI->isForceInlined()) || DisableLIRP::Memcpy)
824 return false;
825
826 Value *Dest = MCI->getDest();
827 Value *Source = MCI->getSource();
828 if (!Dest || !Source)
829 return false;
830
831 // See if the load and store pointer expressions are AddRec like {base,+,1} on
832 // the current loop, which indicates a strided load and store. If we have
833 // something else, it's a random load or store we can't handle.
834 const SCEV *StoreEv = SE->getSCEV(V: Dest);
835 const SCEV *LoadEv = SE->getSCEV(V: Source);
836 const APInt *StoreStrideValue, *LoadStrideValue;
837 if (!match(S: StoreEv,
838 P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_scev_APInt(C&: StoreStrideValue),
839 L: m_SpecificLoop(L: CurLoop))) ||
840 !match(S: LoadEv,
841 P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_scev_APInt(C&: LoadStrideValue),
842 L: m_SpecificLoop(L: CurLoop))))
843 return false;
844
845 // Reject memcpys that are so large that they overflow an unsigned.
846 uint64_t SizeInBytes = cast<ConstantInt>(Val: MCI->getLength())->getZExtValue();
847 if ((SizeInBytes >> 32) != 0)
848 return false;
849
850 // Huge stride value - give up
851 if (StoreStrideValue->getBitWidth() > 64 ||
852 LoadStrideValue->getBitWidth() > 64)
853 return false;
854
855 if (SizeInBytes != *StoreStrideValue && SizeInBytes != -*StoreStrideValue) {
856 ORE.emit(RemarkBuilder: [&]() {
857 return OptimizationRemarkMissed(DEBUG_TYPE, "SizeStrideUnequal", MCI)
858 << ore::NV("Inst", "memcpy") << " in "
859 << ore::NV("Function", MCI->getFunction())
860 << " function will not be hoisted: "
861 << ore::NV("Reason", "memcpy size is not equal to stride");
862 });
863 return false;
864 }
865
866 int64_t StoreStrideInt = StoreStrideValue->getSExtValue();
867 int64_t LoadStrideInt = LoadStrideValue->getSExtValue();
868 // Check if the load stride matches the store stride.
869 if (StoreStrideInt != LoadStrideInt)
870 return false;
871
872 return processLoopStoreOfLoopLoad(
873 DestPtr: Dest, SourcePtr: Source, StoreSize: SE->getConstant(Ty: Dest->getType(), V: SizeInBytes),
874 StoreAlign: MCI->getDestAlign(), LoadAlign: MCI->getSourceAlign(), TheStore: MCI, TheLoad: MCI,
875 StoreEv: cast<SCEVAddRecExpr>(Val: StoreEv), LoadEv: cast<SCEVAddRecExpr>(Val: LoadEv), BECount);
876}
877
878/// processLoopMemSet - See if this memset can be promoted to a large memset.
879bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI,
880 const SCEV *BECount) {
881 // We can only handle non-volatile memsets.
882 if (MSI->isVolatile())
883 return false;
884
885 // If we're not allowed to hack on memset, we fail.
886 if (!HasMemset || DisableLIRP::Memset)
887 return false;
888
889 Value *Pointer = MSI->getDest();
890
891 // See if the pointer expression is an AddRec like {base,+,1} on the current
892 // loop, which indicates a strided store. If we have something else, it's a
893 // random store we can't handle.
894 const SCEV *Ev = SE->getSCEV(V: Pointer);
895 const SCEV *PointerStrideSCEV;
896 if (!match(S: Ev, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV(V&: PointerStrideSCEV),
897 L: m_SpecificLoop(L: CurLoop)))) {
898 LLVM_DEBUG(dbgs() << " Pointer is not affine, abort\n");
899 return false;
900 }
901
902 SCEVUse MemsetSizeSCEV = SE->getSCEV(V: MSI->getLength());
903
904 bool IsNegStride = false;
905 const bool IsConstantSize = isa<ConstantInt>(Val: MSI->getLength());
906
907 if (IsConstantSize) {
908 // Memset size is constant.
909 // Check if the pointer stride matches the memset size. If so, then
910 // we know that every byte is touched in the loop.
911 LLVM_DEBUG(dbgs() << " memset size is constant\n");
912 uint64_t SizeInBytes = cast<ConstantInt>(Val: MSI->getLength())->getZExtValue();
913 const APInt *Stride;
914 if (!match(S: PointerStrideSCEV, P: m_scev_APInt(C&: Stride)))
915 return false;
916
917 if (SizeInBytes != *Stride && SizeInBytes != -*Stride)
918 return false;
919
920 IsNegStride = SizeInBytes == -*Stride;
921 } else {
922 // Memset size is non-constant.
923 // Check if the pointer stride matches the memset size.
924 // To be conservative, the pass would not promote pointers that aren't in
925 // address space zero. Also, the pass only handles memset length and stride
926 // that are invariant for the top level loop.
927 LLVM_DEBUG(dbgs() << " memset size is non-constant\n");
928 if (Pointer->getType()->getPointerAddressSpace() != 0) {
929 LLVM_DEBUG(dbgs() << " pointer is not in address space zero, "
930 << "abort\n");
931 return false;
932 }
933 if (!SE->isLoopInvariant(S: MemsetSizeSCEV, L: CurLoop)) {
934 LLVM_DEBUG(dbgs() << " memset size is not a loop-invariant, "
935 << "abort\n");
936 return false;
937 }
938
939 // Compare positive direction PointerStrideSCEV with MemsetSizeSCEV
940 IsNegStride = PointerStrideSCEV->isNonConstantNegative();
941 SCEVUse PositiveStrideSCEV =
942 IsNegStride ? SCEVUse(SE->getNegativeSCEV(V: PointerStrideSCEV))
943 : SCEVUse(PointerStrideSCEV);
944 LLVM_DEBUG(dbgs() << " MemsetSizeSCEV: " << *MemsetSizeSCEV << "\n"
945 << " PositiveStrideSCEV: " << *PositiveStrideSCEV
946 << "\n");
947
948 if (PositiveStrideSCEV != MemsetSizeSCEV) {
949 // If an expression is covered by the loop guard, compare again and
950 // proceed with optimization if equal.
951 const SCEV *FoldedPositiveStride =
952 SE->applyLoopGuards(Expr: PositiveStrideSCEV, L: CurLoop);
953 const SCEV *FoldedMemsetSize =
954 SE->applyLoopGuards(Expr: MemsetSizeSCEV, L: CurLoop);
955
956 LLVM_DEBUG(dbgs() << " Try to fold SCEV based on loop guard\n"
957 << " FoldedMemsetSize: " << *FoldedMemsetSize << "\n"
958 << " FoldedPositiveStride: " << *FoldedPositiveStride
959 << "\n");
960
961 if (FoldedPositiveStride != FoldedMemsetSize) {
962 LLVM_DEBUG(dbgs() << " SCEV don't match, abort\n");
963 return false;
964 }
965 }
966 }
967
968 // Verify that the memset value is loop invariant. If not, we can't promote
969 // the memset.
970 Value *SplatValue = MSI->getValue();
971 if (!SplatValue || !CurLoop->isLoopInvariant(V: SplatValue))
972 return false;
973
974 SmallPtrSet<Instruction *, 1> MSIs;
975 MSIs.insert(Ptr: MSI);
976 return processLoopStridedStore(DestPtr: Pointer, StoreSizeSCEV: SE->getSCEV(V: MSI->getLength()),
977 StoreAlignment: MSI->getDestAlign(), StoredVal: SplatValue, TheStore: MSI, Stores&: MSIs,
978 Ev: cast<SCEVAddRecExpr>(Val: Ev), BECount, IsNegStride,
979 /*IsLoopMemset=*/true);
980}
981
982/// mayLoopAccessLocation - Return true if the specified loop might access the
983/// specified pointer location, which is a loop-strided access. The 'Access'
984/// argument specifies what the verboten forms of access are (read or write).
985static bool
986mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
987 const SCEV *BECount, const SCEV *StoreSizeSCEV,
988 AliasAnalysis &AA,
989 SmallPtrSetImpl<Instruction *> &IgnoredInsts) {
990 // Get the location that may be stored across the loop. Since the access is
991 // strided positively through memory, we say that the modified location starts
992 // at the pointer and has infinite size.
993 LocationSize AccessSize = LocationSize::afterPointer();
994
995 // If the loop iterates a fixed number of times, we can refine the access size
996 // to be exactly the size of the memset, which is (BECount+1)*StoreSize
997 const APInt *BECst, *ConstSize;
998 if (match(S: BECount, P: m_scev_APInt(C&: BECst)) &&
999 match(S: StoreSizeSCEV, P: m_scev_APInt(C&: ConstSize))) {
1000 std::optional<uint64_t> BEInt = BECst->tryZExtValue();
1001 std::optional<uint64_t> SizeInt = ConstSize->tryZExtValue();
1002 // FIXME: Should this check for overflow?
1003 if (BEInt && SizeInt)
1004 AccessSize = LocationSize::precise(Value: (*BEInt + 1) * *SizeInt);
1005 }
1006
1007 // TODO: For this to be really effective, we have to dive into the pointer
1008 // operand in the store. Store to &A[i] of 100 will always return may alias
1009 // with store of &A[100], we need to StoreLoc to be "A" with size of 100,
1010 // which will then no-alias a store to &A[100].
1011 MemoryLocation StoreLoc(Ptr, AccessSize);
1012
1013 for (BasicBlock *B : L->blocks())
1014 for (Instruction &I : *B)
1015 if (!IgnoredInsts.contains(Ptr: &I) &&
1016 isModOrRefSet(MRI: AA.getModRefInfo(I: &I, OptLoc: StoreLoc) & Access))
1017 return true;
1018 return false;
1019}
1020
1021// If we have a negative stride, Start refers to the end of the memory location
1022// we're trying to memset. Therefore, we need to recompute the base pointer,
1023// which is just Start - BECount*Size.
1024static const SCEV *getStartForNegStride(const SCEV *Start, const SCEV *BECount,
1025 Type *IntPtr, const SCEV *StoreSizeSCEV,
1026 ScalarEvolution *SE) {
1027 const SCEV *Index = SE->getTruncateOrZeroExtend(V: BECount, Ty: IntPtr);
1028 if (!StoreSizeSCEV->isOne()) {
1029 // index = back edge count * store size
1030 Index = SE->getMulExpr(LHS: Index,
1031 RHS: SE->getTruncateOrZeroExtend(V: StoreSizeSCEV, Ty: IntPtr),
1032 Flags: SCEV::FlagNUW);
1033 }
1034 // base pointer = start - index * store size
1035 return SE->getMinusSCEV(LHS: Start, RHS: Index);
1036}
1037
1038/// Compute the number of bytes as a SCEV from the backedge taken count.
1039///
1040/// This also maps the SCEV into the provided type and tries to handle the
1041/// computation in a way that will fold cleanly.
1042static const SCEV *getNumBytes(const SCEV *BECount, Type *IntPtr,
1043 const SCEV *StoreSizeSCEV, Loop *CurLoop,
1044 const DataLayout *DL, ScalarEvolution *SE) {
1045 const SCEV *TripCountSCEV =
1046 SE->getTripCountFromExitCount(ExitCount: BECount, EvalTy: IntPtr, L: CurLoop);
1047 return SE->getMulExpr(LHS: TripCountSCEV,
1048 RHS: SE->getTruncateOrZeroExtend(V: StoreSizeSCEV, Ty: IntPtr),
1049 Flags: SCEV::FlagNUW);
1050}
1051
1052/// processLoopStridedStore - We see a strided store of some value. If we can
1053/// transform this into a memset or memset_pattern in the loop preheader, do so.
1054bool LoopIdiomRecognize::processLoopStridedStore(
1055 Value *DestPtr, const SCEV *StoreSizeSCEV, MaybeAlign StoreAlignment,
1056 Value *StoredVal, Instruction *TheStore,
1057 SmallPtrSetImpl<Instruction *> &Stores, const SCEVAddRecExpr *Ev,
1058 const SCEV *BECount, bool IsNegStride, bool IsLoopMemset) {
1059 Module *M = TheStore->getModule();
1060
1061 // The trip count of the loop and the base pointer of the addrec SCEV is
1062 // guaranteed to be loop invariant, which means that it should dominate the
1063 // header. This allows us to insert code for it in the preheader.
1064 unsigned DestAS = DestPtr->getType()->getPointerAddressSpace();
1065 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1066 IRBuilder<> Builder(Preheader->getTerminator());
1067 SCEVExpander Expander(*SE, "loop-idiom");
1068 SCEVExpanderCleaner ExpCleaner(Expander);
1069
1070 Type *DestInt8PtrTy = Builder.getPtrTy(AddrSpace: DestAS);
1071 Type *IntIdxTy = DL->getIndexType(PtrTy: DestPtr->getType());
1072
1073 bool Changed = false;
1074 const SCEV *Start = Ev->getStart();
1075 // Handle negative strided loops.
1076 if (IsNegStride)
1077 Start = getStartForNegStride(Start, BECount, IntPtr: IntIdxTy, StoreSizeSCEV, SE);
1078
1079 // TODO: ideally we should still be able to generate memset if SCEV expander
1080 // is taught to generate the dependencies at the latest point.
1081 if (!Expander.isSafeToExpand(S: Start))
1082 return Changed;
1083
1084 // Okay, we have a strided store "p[i]" of a splattable value. We can turn
1085 // this into a memset in the loop preheader now if we want. However, this
1086 // would be unsafe to do if there is anything else in the loop that may read
1087 // or write to the aliased location. Check for any overlap by generating the
1088 // base pointer and checking the region.
1089 Value *BasePtr =
1090 Expander.expandCodeFor(SH: Start, Ty: DestInt8PtrTy, I: Preheader->getTerminator());
1091
1092 // From here on out, conservatively report to the pass manager that we've
1093 // changed the IR, even if we later clean up these added instructions. There
1094 // may be structural differences e.g. in the order of use lists not accounted
1095 // for in just a textual dump of the IR. This is written as a variable, even
1096 // though statically all the places this dominates could be replaced with
1097 // 'true', with the hope that anyone trying to be clever / "more precise" with
1098 // the return value will read this comment, and leave them alone.
1099 Changed = true;
1100
1101 if (mayLoopAccessLocation(Ptr: BasePtr, Access: ModRefInfo::ModRef, L: CurLoop, BECount,
1102 StoreSizeSCEV, AA&: *AA, IgnoredInsts&: Stores))
1103 return Changed;
1104
1105 if (avoidLIRForMultiBlockLoop(/*IsMemset=*/true, IsLoopMemset))
1106 return Changed;
1107
1108 // Okay, everything looks good, insert the memset.
1109 Value *SplatValue = isBytewiseValue(V: StoredVal, DL: *DL);
1110 Constant *PatternValue = nullptr;
1111 if (!SplatValue)
1112 PatternValue = getMemSetPatternValue(V: StoredVal, DL);
1113
1114 // MemsetArg is the number of bytes for the memset libcall, and the number
1115 // of pattern repetitions if the memset.pattern intrinsic is being used.
1116 Value *MemsetArg;
1117 std::optional<int64_t> BytesWritten;
1118
1119 if (PatternValue && (HasMemsetPattern || ForceMemsetPatternIntrinsic)) {
1120 const SCEV *TripCountS =
1121 SE->getTripCountFromExitCount(ExitCount: BECount, EvalTy: IntIdxTy, L: CurLoop);
1122 if (!Expander.isSafeToExpand(S: TripCountS))
1123 return Changed;
1124 const SCEVConstant *ConstStoreSize = dyn_cast<SCEVConstant>(Val: StoreSizeSCEV);
1125 if (!ConstStoreSize)
1126 return Changed;
1127 Value *TripCount = Expander.expandCodeFor(SH: TripCountS, Ty: IntIdxTy,
1128 I: Preheader->getTerminator());
1129 uint64_t PatternRepsPerTrip =
1130 (ConstStoreSize->getValue()->getZExtValue() * 8) /
1131 DL->getTypeSizeInBits(Ty: PatternValue->getType());
1132 // If ConstStoreSize is not equal to the width of PatternValue, then
1133 // MemsetArg is TripCount * (ConstStoreSize/PatternValueWidth). Else
1134 // MemSetArg is just TripCount.
1135 MemsetArg =
1136 PatternRepsPerTrip == 1
1137 ? TripCount
1138 : Builder.CreateMul(LHS: TripCount,
1139 RHS: Builder.getIntN(N: IntIdxTy->getIntegerBitWidth(),
1140 C: PatternRepsPerTrip));
1141 if (auto *CI = dyn_cast<ConstantInt>(Val: TripCount))
1142 BytesWritten =
1143 CI->getZExtValue() * ConstStoreSize->getValue()->getZExtValue();
1144
1145 } else {
1146 const SCEV *NumBytesS =
1147 getNumBytes(BECount, IntPtr: IntIdxTy, StoreSizeSCEV, CurLoop, DL, SE);
1148
1149 // TODO: ideally we should still be able to generate memset if SCEV expander
1150 // is taught to generate the dependencies at the latest point.
1151 if (!Expander.isSafeToExpand(S: NumBytesS))
1152 return Changed;
1153 MemsetArg =
1154 Expander.expandCodeFor(SH: NumBytesS, Ty: IntIdxTy, I: Preheader->getTerminator());
1155 if (auto *CI = dyn_cast<ConstantInt>(Val: MemsetArg))
1156 BytesWritten = CI->getZExtValue();
1157 }
1158 assert(MemsetArg && "MemsetArg should have been set");
1159
1160 AAMDNodes AATags = TheStore->getAAMetadata();
1161 for (Instruction *Store : Stores)
1162 AATags = AATags.merge(Other: Store->getAAMetadata());
1163 if (BytesWritten)
1164 AATags = AATags.extendTo(Len: BytesWritten.value());
1165 else
1166 AATags = AATags.extendTo(Len: -1);
1167
1168 CallInst *NewCall;
1169 if (SplatValue) {
1170 NewCall = Builder.CreateMemSet(Ptr: BasePtr, Val: SplatValue, Size: MemsetArg,
1171 Align: MaybeAlign(StoreAlignment),
1172 /*isVolatile=*/false, AAInfo: AATags);
1173 } else if (ForceMemsetPatternIntrinsic ||
1174 isLibFuncEmittable(M, TLI, TheLibFunc: LibFunc_memset_pattern16)) {
1175 assert(isa<SCEVConstant>(StoreSizeSCEV) && "Expected constant store size");
1176
1177 NewCall = Builder.CreateIntrinsicWithoutFolding(
1178 ID: Intrinsic::experimental_memset_pattern,
1179 OverloadTypes: {DestInt8PtrTy, PatternValue->getType(), IntIdxTy},
1180 Args: {BasePtr, PatternValue, MemsetArg,
1181 ConstantInt::getFalse(Context&: M->getContext())});
1182 if (StoreAlignment)
1183 cast<MemSetPatternInst>(Val: NewCall)->setDestAlignment(*StoreAlignment);
1184 NewCall->setAAMetadata(AATags);
1185 } else {
1186 // Neither a memset, nor memset_pattern16
1187 return Changed;
1188 }
1189
1190 NewCall->setDebugLoc(TheStore->getDebugLoc());
1191
1192 if (MSSAU) {
1193 MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
1194 I: NewCall, Definition: nullptr, BB: NewCall->getParent(), Point: MemorySSA::BeforeTerminator);
1195 MSSAU->insertDef(Def: cast<MemoryDef>(Val: NewMemAcc), RenameUses: true);
1196 }
1197
1198 LLVM_DEBUG(dbgs() << " Formed memset: " << *NewCall << "\n"
1199 << " from store to: " << *Ev << " at: " << *TheStore
1200 << "\n");
1201
1202 ORE.emit(RemarkBuilder: [&]() {
1203 OptimizationRemark R(DEBUG_TYPE, "ProcessLoopStridedStore",
1204 NewCall->getDebugLoc(), Preheader);
1205 R << "Transformed loop-strided store in "
1206 << ore::NV("Function", TheStore->getFunction())
1207 << " function into a call to "
1208 << ore::NV("NewFunction", NewCall->getCalledFunction())
1209 << "() intrinsic";
1210 if (!Stores.empty())
1211 R << ore::setExtraArgs();
1212 for (auto *I : Stores) {
1213 R << ore::NV("FromBlock", I->getParent()->getName())
1214 << ore::NV("ToBlock", Preheader->getName());
1215 }
1216 return R;
1217 });
1218
1219 // Okay, the memset has been formed. Zap the original store and anything that
1220 // feeds into it.
1221 for (auto *I : Stores) {
1222 if (MSSAU)
1223 MSSAU->removeMemoryAccess(I, OptimizePhis: true);
1224 deleteDeadInstruction(I);
1225 }
1226 if (MSSAU && VerifyMemorySSA)
1227 MSSAU->getMemorySSA()->verifyMemorySSA();
1228 ++NumMemSet;
1229 ExpCleaner.markResultUsed();
1230 return true;
1231}
1232
1233/// If the stored value is a strided load in the same loop with the same stride
1234/// this may be transformable into a memcpy. This kicks in for stuff like
1235/// for (i) A[i] = B[i];
1236bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
1237 const SCEV *BECount) {
1238 assert(SI->isUnordered() && "Expected only non-volatile non-ordered stores.");
1239
1240 Value *StorePtr = SI->getPointerOperand();
1241 const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: StorePtr));
1242 unsigned StoreSize = DL->getTypeStoreSize(Ty: SI->getValueOperand()->getType());
1243
1244 // The store must be feeding a non-volatile load.
1245 LoadInst *LI = cast<LoadInst>(Val: SI->getValueOperand());
1246 assert(LI->isUnordered() && "Expected only non-volatile non-ordered loads.");
1247
1248 // See if the pointer expression is an AddRec like {base,+,1} on the current
1249 // loop, which indicates a strided load. If we have something else, it's a
1250 // random load we can't handle.
1251 Value *LoadPtr = LI->getPointerOperand();
1252 const SCEVAddRecExpr *LoadEv = cast<SCEVAddRecExpr>(Val: SE->getSCEV(V: LoadPtr));
1253
1254 const SCEV *StoreSizeSCEV = SE->getConstant(Ty: StorePtr->getType(), V: StoreSize);
1255 return processLoopStoreOfLoopLoad(DestPtr: StorePtr, SourcePtr: LoadPtr, StoreSize: StoreSizeSCEV,
1256 StoreAlign: SI->getAlign(), LoadAlign: LI->getAlign(), TheStore: SI, TheLoad: LI,
1257 StoreEv, LoadEv, BECount);
1258}
1259
1260namespace {
1261class MemmoveVerifier {
1262public:
1263 explicit MemmoveVerifier(const Value &LoadBasePtr, const Value &StoreBasePtr,
1264 const DataLayout &DL)
1265 : DL(DL), BP1(llvm::GetPointerBaseWithConstantOffset(
1266 Ptr: LoadBasePtr.stripPointerCasts(), Offset&: LoadOff, DL)),
1267 BP2(llvm::GetPointerBaseWithConstantOffset(
1268 Ptr: StoreBasePtr.stripPointerCasts(), Offset&: StoreOff, DL)),
1269 IsSameObject(BP1 == BP2) {}
1270
1271 bool loadAndStoreMayFormMemmove(unsigned StoreSize, bool IsNegStride,
1272 const Instruction &TheLoad,
1273 bool IsMemCpy) const {
1274 if (IsMemCpy) {
1275 // Ensure that LoadBasePtr is after StoreBasePtr or before StoreBasePtr
1276 // for negative stride.
1277 if ((!IsNegStride && LoadOff <= StoreOff) ||
1278 (IsNegStride && LoadOff >= StoreOff))
1279 return false;
1280 } else {
1281 // Ensure that LoadBasePtr is after StoreBasePtr or before StoreBasePtr
1282 // for negative stride. LoadBasePtr shouldn't overlap with StoreBasePtr.
1283 int64_t LoadSize =
1284 DL.getTypeSizeInBits(Ty: TheLoad.getType()).getFixedValue() / 8;
1285 if (BP1 != BP2 || LoadSize != int64_t(StoreSize))
1286 return false;
1287 if ((!IsNegStride && LoadOff < StoreOff + int64_t(StoreSize)) ||
1288 (IsNegStride && LoadOff + LoadSize > StoreOff))
1289 return false;
1290 }
1291 return true;
1292 }
1293
1294private:
1295 const DataLayout &DL;
1296 int64_t LoadOff = 0;
1297 int64_t StoreOff = 0;
1298 const Value *BP1;
1299 const Value *BP2;
1300
1301public:
1302 const bool IsSameObject;
1303};
1304} // namespace
1305
1306bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(
1307 Value *DestPtr, Value *SourcePtr, const SCEV *StoreSizeSCEV,
1308 MaybeAlign StoreAlign, MaybeAlign LoadAlign, Instruction *TheStore,
1309 Instruction *TheLoad, const SCEVAddRecExpr *StoreEv,
1310 const SCEVAddRecExpr *LoadEv, const SCEV *BECount) {
1311
1312 // FIXME: until llvm.memcpy.inline supports dynamic sizes, we need to
1313 // conservatively bail here, since otherwise we may have to transform
1314 // llvm.memcpy.inline into llvm.memcpy which is illegal.
1315 if (auto *MCI = dyn_cast<MemCpyInst>(Val: TheStore); MCI && MCI->isForceInlined())
1316 return false;
1317
1318 // The trip count of the loop and the base pointer of the addrec SCEV is
1319 // guaranteed to be loop invariant, which means that it should dominate the
1320 // header. This allows us to insert code for it in the preheader.
1321 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1322 IRBuilder<> Builder(Preheader->getTerminator());
1323 SCEVExpander Expander(*SE, "loop-idiom");
1324
1325 SCEVExpanderCleaner ExpCleaner(Expander);
1326
1327 bool Changed = false;
1328 const SCEV *StrStart = StoreEv->getStart();
1329 unsigned StrAS = DestPtr->getType()->getPointerAddressSpace();
1330 Type *IntIdxTy = Builder.getIntNTy(N: DL->getIndexSizeInBits(AS: StrAS));
1331
1332 APInt Stride = getStoreStride(StoreEv);
1333 const SCEVConstant *ConstStoreSize = dyn_cast<SCEVConstant>(Val: StoreSizeSCEV);
1334
1335 // TODO: Deal with non-constant size; Currently expect constant store size
1336 assert(ConstStoreSize && "store size is expected to be a constant");
1337
1338 int64_t StoreSize = ConstStoreSize->getValue()->getZExtValue();
1339 bool IsNegStride = StoreSize == -Stride;
1340
1341 // Handle negative strided loops.
1342 if (IsNegStride)
1343 StrStart =
1344 getStartForNegStride(Start: StrStart, BECount, IntPtr: IntIdxTy, StoreSizeSCEV, SE);
1345
1346 // Okay, we have a strided store "p[i]" of a loaded value. We can turn
1347 // this into a memcpy in the loop preheader now if we want. However, this
1348 // would be unsafe to do if there is anything else in the loop that may read
1349 // or write the memory region we're storing to. This includes the load that
1350 // feeds the stores. Check for an alias by generating the base address and
1351 // checking everything.
1352 Value *StoreBasePtr = Expander.expandCodeFor(
1353 SH: StrStart, Ty: Builder.getPtrTy(AddrSpace: StrAS), I: Preheader->getTerminator());
1354
1355 // From here on out, conservatively report to the pass manager that we've
1356 // changed the IR, even if we later clean up these added instructions. There
1357 // may be structural differences e.g. in the order of use lists not accounted
1358 // for in just a textual dump of the IR. This is written as a variable, even
1359 // though statically all the places this dominates could be replaced with
1360 // 'true', with the hope that anyone trying to be clever / "more precise" with
1361 // the return value will read this comment, and leave them alone.
1362 Changed = true;
1363
1364 SmallPtrSet<Instruction *, 2> IgnoredInsts;
1365 IgnoredInsts.insert(Ptr: TheStore);
1366
1367 bool IsMemCpy = isa<MemCpyInst>(Val: TheStore);
1368 const StringRef InstRemark = IsMemCpy ? "memcpy" : "load and store";
1369
1370 bool LoopAccessStore =
1371 mayLoopAccessLocation(Ptr: StoreBasePtr, Access: ModRefInfo::ModRef, L: CurLoop, BECount,
1372 StoreSizeSCEV, AA&: *AA, IgnoredInsts);
1373 if (LoopAccessStore) {
1374 // For memmove case it's not enough to guarantee that loop doesn't access
1375 // TheStore and TheLoad. Additionally we need to make sure that TheStore is
1376 // the only user of TheLoad.
1377 if (!TheLoad->hasOneUse())
1378 return Changed;
1379 IgnoredInsts.insert(Ptr: TheLoad);
1380 if (mayLoopAccessLocation(Ptr: StoreBasePtr, Access: ModRefInfo::ModRef, L: CurLoop,
1381 BECount, StoreSizeSCEV, AA&: *AA, IgnoredInsts)) {
1382 ORE.emit(RemarkBuilder: [&]() {
1383 return OptimizationRemarkMissed(DEBUG_TYPE, "LoopMayAccessStore",
1384 TheStore)
1385 << ore::NV("Inst", InstRemark) << " in "
1386 << ore::NV("Function", TheStore->getFunction())
1387 << " function will not be hoisted: "
1388 << ore::NV("Reason", "The loop may access store location");
1389 });
1390 return Changed;
1391 }
1392 IgnoredInsts.erase(Ptr: TheLoad);
1393 }
1394
1395 const SCEV *LdStart = LoadEv->getStart();
1396 unsigned LdAS = SourcePtr->getType()->getPointerAddressSpace();
1397
1398 // Handle negative strided loops.
1399 if (IsNegStride)
1400 LdStart =
1401 getStartForNegStride(Start: LdStart, BECount, IntPtr: IntIdxTy, StoreSizeSCEV, SE);
1402
1403 // For a memcpy, we have to make sure that the input array is not being
1404 // mutated by the loop.
1405 Value *LoadBasePtr = Expander.expandCodeFor(SH: LdStart, Ty: Builder.getPtrTy(AddrSpace: LdAS),
1406 I: Preheader->getTerminator());
1407
1408 // If the store is a memcpy instruction, we must check if it will write to
1409 // the load memory locations. So remove it from the ignored stores.
1410 MemmoveVerifier Verifier(*LoadBasePtr, *StoreBasePtr, *DL);
1411 if (IsMemCpy && !Verifier.IsSameObject)
1412 IgnoredInsts.erase(Ptr: TheStore);
1413 if (mayLoopAccessLocation(Ptr: LoadBasePtr, Access: ModRefInfo::Mod, L: CurLoop, BECount,
1414 StoreSizeSCEV, AA&: *AA, IgnoredInsts)) {
1415 ORE.emit(RemarkBuilder: [&]() {
1416 return OptimizationRemarkMissed(DEBUG_TYPE, "LoopMayAccessLoad", TheLoad)
1417 << ore::NV("Inst", InstRemark) << " in "
1418 << ore::NV("Function", TheStore->getFunction())
1419 << " function will not be hoisted: "
1420 << ore::NV("Reason", "The loop may access load location");
1421 });
1422 return Changed;
1423 }
1424
1425 bool IsAtomic = TheStore->isAtomic() || TheLoad->isAtomic();
1426 bool UseMemMove = IsMemCpy ? Verifier.IsSameObject : LoopAccessStore;
1427
1428 if (IsAtomic) {
1429 // For now don't support unordered atomic memmove.
1430 if (UseMemMove)
1431 return Changed;
1432
1433 // We cannot allow unaligned ops for unordered load/store, so reject
1434 // anything where the alignment isn't at least the element size.
1435 assert((StoreAlign && LoadAlign) &&
1436 "Expect unordered load/store to have align.");
1437 if (*StoreAlign < StoreSize || *LoadAlign < StoreSize)
1438 return Changed;
1439
1440 // If the element.atomic memcpy is not lowered into explicit
1441 // loads/stores later, then it will be lowered into an element-size
1442 // specific lib call. If the lib call doesn't exist for our store size, then
1443 // we shouldn't generate the memcpy.
1444 if (StoreSize > TTI->getAtomicMemIntrinsicMaxElementSize())
1445 return Changed;
1446 }
1447
1448 if (UseMemMove)
1449 if (!Verifier.loadAndStoreMayFormMemmove(StoreSize, IsNegStride, TheLoad: *TheLoad,
1450 IsMemCpy))
1451 return Changed;
1452
1453 if (avoidLIRForMultiBlockLoop())
1454 return Changed;
1455
1456 // Okay, everything is safe, we can transform this!
1457
1458 const SCEV *NumBytesS =
1459 getNumBytes(BECount, IntPtr: IntIdxTy, StoreSizeSCEV, CurLoop, DL, SE);
1460
1461 Value *NumBytes =
1462 Expander.expandCodeFor(SH: NumBytesS, Ty: IntIdxTy, I: Preheader->getTerminator());
1463
1464 AAMDNodes AATags = TheLoad->getAAMetadata();
1465 AAMDNodes StoreAATags = TheStore->getAAMetadata();
1466 AATags = AATags.merge(Other: StoreAATags);
1467 if (auto CI = dyn_cast<ConstantInt>(Val: NumBytes))
1468 AATags = AATags.extendTo(Len: CI->getZExtValue());
1469 else
1470 AATags = AATags.extendTo(Len: -1);
1471
1472 CallInst *NewCall = nullptr;
1473 // Check whether to generate an unordered atomic memcpy:
1474 // If the load or store are atomic, then they must necessarily be unordered
1475 // by previous checks.
1476 if (!IsAtomic) {
1477 if (UseMemMove)
1478 NewCall = Builder.CreateMemMove(Dst: StoreBasePtr, DstAlign: StoreAlign, Src: LoadBasePtr,
1479 SrcAlign: LoadAlign, Size: NumBytes,
1480 /*isVolatile=*/false, AAInfo: AATags);
1481 else
1482 NewCall =
1483 Builder.CreateMemCpy(Dst: StoreBasePtr, DstAlign: StoreAlign, Src: LoadBasePtr, SrcAlign: LoadAlign,
1484 Size: NumBytes, /*isVolatile=*/false, AAInfo: AATags);
1485 } else {
1486 // Create the call.
1487 // Note that unordered atomic loads/stores are *required* by the spec to
1488 // have an alignment but non-atomic loads/stores may not.
1489 NewCall = Builder.CreateElementUnorderedAtomicMemCpy(
1490 Dst: StoreBasePtr, DstAlign: *StoreAlign, Src: LoadBasePtr, SrcAlign: *LoadAlign, Size: NumBytes, ElementSize: StoreSize,
1491 AAInfo: AATags);
1492 }
1493 NewCall->setDebugLoc(TheStore->getDebugLoc());
1494
1495 if (MSSAU) {
1496 MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
1497 I: NewCall, Definition: nullptr, BB: NewCall->getParent(), Point: MemorySSA::BeforeTerminator);
1498 MSSAU->insertDef(Def: cast<MemoryDef>(Val: NewMemAcc), RenameUses: true);
1499 }
1500
1501 LLVM_DEBUG(dbgs() << " Formed new call: " << *NewCall << "\n"
1502 << " from load ptr=" << *LoadEv << " at: " << *TheLoad
1503 << "\n"
1504 << " from store ptr=" << *StoreEv << " at: " << *TheStore
1505 << "\n");
1506
1507 ORE.emit(RemarkBuilder: [&]() {
1508 return OptimizationRemark(DEBUG_TYPE, "ProcessLoopStoreOfLoopLoad",
1509 NewCall->getDebugLoc(), Preheader)
1510 << "Formed a call to "
1511 << ore::NV("NewFunction", NewCall->getCalledFunction())
1512 << "() intrinsic from " << ore::NV("Inst", InstRemark)
1513 << " instruction in " << ore::NV("Function", TheStore->getFunction())
1514 << " function"
1515 << ore::setExtraArgs()
1516 << ore::NV("FromBlock", TheStore->getParent()->getName())
1517 << ore::NV("ToBlock", Preheader->getName());
1518 });
1519
1520 // Okay, a new call to memcpy/memmove has been formed. Zap the original store
1521 // and anything that feeds into it.
1522 if (MSSAU)
1523 MSSAU->removeMemoryAccess(I: TheStore, OptimizePhis: true);
1524 deleteDeadInstruction(I: TheStore);
1525 if (MSSAU && VerifyMemorySSA)
1526 MSSAU->getMemorySSA()->verifyMemorySSA();
1527 if (UseMemMove)
1528 ++NumMemMove;
1529 else
1530 ++NumMemCpy;
1531 ExpCleaner.markResultUsed();
1532 return true;
1533}
1534
1535// When compiling for codesize we avoid idiom recognition for a multi-block loop
1536// unless it is a loop_memset idiom or a memset/memcpy idiom in a nested loop.
1537//
1538bool LoopIdiomRecognize::avoidLIRForMultiBlockLoop(bool IsMemset,
1539 bool IsLoopMemset) {
1540 if (ApplyCodeSizeHeuristics && CurLoop->getNumBlocks() > 1) {
1541 if (CurLoop->isOutermost() && (!IsMemset || !IsLoopMemset)) {
1542 LLVM_DEBUG(dbgs() << " " << CurLoop->getHeader()->getParent()->getName()
1543 << " : LIR " << (IsMemset ? "Memset" : "Memcpy")
1544 << " avoided: multi-block top-level loop\n");
1545 return true;
1546 }
1547 }
1548
1549 return false;
1550}
1551
1552bool LoopIdiomRecognize::optimizeCRCLoop(const PolynomialInfo &Info) {
1553 // FIXME: Hexagon has a special HexagonLoopIdiom that optimizes CRC using
1554 // carry-less multiplication instructions, which is more efficient than our
1555 // Sarwate table-lookup optimization. Hence, until we're able to emit
1556 // target-specific instructions for Hexagon, subsuming HexagonLoopIdiom,
1557 // disable the optimization for Hexagon.
1558 Module &M = *CurLoop->getHeader()->getModule();
1559 Triple TT(M.getTargetTriple());
1560 if (TT.getArch() == Triple::hexagon)
1561 return false;
1562
1563 // First, create a new GlobalVariable corresponding to the
1564 // Sarwate-lookup-table.
1565 Type *CRCTy = Info.LHS->getType();
1566 unsigned CRCBW = CRCTy->getIntegerBitWidth();
1567 std::array<Constant *, 256> CRCConstants;
1568 transform(Range: HashRecognize::genSarwateTable(GenPoly: Info.RHS, IsBigEndian: Info.IsBigEndian),
1569 d_first: CRCConstants.begin(),
1570 F: [CRCTy](const APInt &E) { return ConstantInt::get(Ty: CRCTy, V: E); });
1571 Constant *ConstArray =
1572 ConstantArray::get(T: ArrayType::get(ElementType: CRCTy, NumElements: 256), V: CRCConstants);
1573 GlobalVariable *GV =
1574 new GlobalVariable(M, ConstArray->getType(), true,
1575 GlobalValue::PrivateLinkage, ConstArray, ".crctable");
1576
1577 PHINode *IV = CurLoop->getCanonicalInductionVariable();
1578 SmallVector<PHINode *, 2> Cleanup;
1579
1580 // Next, mark all PHIs for removal except IV.
1581 {
1582 for (PHINode &PN : CurLoop->getHeader()->phis()) {
1583 if (&PN == IV)
1584 continue;
1585 PN.replaceAllUsesWith(V: PoisonValue::get(T: PN.getType()));
1586 Cleanup.push_back(Elt: &PN);
1587 }
1588 }
1589
1590 // Next, fix up the trip count.
1591 {
1592 unsigned NewBTC = (Info.TripCount / 8) - 1;
1593 BasicBlock *LoopBlk = CurLoop->getLoopLatch();
1594 CondBrInst *BrInst = cast<CondBrInst>(Val: LoopBlk->getTerminator());
1595 CmpPredicate ExitPred = BrInst->getSuccessor(i: 0) == LoopBlk
1596 ? ICmpInst::Predicate::ICMP_NE
1597 : ICmpInst::Predicate::ICMP_EQ;
1598 Instruction *ExitCond = CurLoop->getLatchCmpInst();
1599 Value *ExitLimit = ConstantInt::get(Ty: IV->getType(), V: NewBTC);
1600 IRBuilder<> Builder(ExitCond);
1601 Value *NewExitCond =
1602 Builder.CreateICmp(P: ExitPred, LHS: IV, RHS: ExitLimit, Name: "exit.cond");
1603 ExitCond->replaceAllUsesWith(V: NewExitCond);
1604 deleteDeadInstruction(I: ExitCond);
1605 }
1606
1607 // Finally, fill the loop with the Sarwate-table-lookup logic, and replace all
1608 // uses of ComputedValue.
1609 //
1610 // Little-endian:
1611 // crc = (crc >> 8) ^ tbl[(iv'th byte of data) ^ (bottom byte of crc)]
1612 // Big-Endian:
1613 // crc = (crc << 8) ^ tbl[(iv'th byte of data) ^ (top byte of crc)]
1614 {
1615 auto LoByte = [](IRBuilderBase &Builder, Value *Op, const Twine &Name) {
1616 return Builder.CreateZExtOrTrunc(
1617 V: Op, DestTy: IntegerType::getInt8Ty(C&: Op->getContext()), Name);
1618 };
1619 auto HiIdx = [LoByte, CRCBW](IRBuilderBase &Builder, Value *Op,
1620 const Twine &Name) {
1621 Type *OpTy = Op->getType();
1622
1623 // When the bitwidth of the CRC mismatches the Op's bitwidth, we need to
1624 // use the CRC's bitwidth as the reference for shifting right.
1625 return LoByte(Builder,
1626 CRCBW > 8 ? Builder.CreateLShr(
1627 LHS: Op, RHS: ConstantInt::get(Ty: OpTy, V: CRCBW - 8), Name)
1628 : Op,
1629 Name + ".lo.byte");
1630 };
1631
1632 IRBuilder<> Builder(CurLoop->getHeader(),
1633 CurLoop->getHeader()->getFirstNonPHIIt());
1634
1635 // Create the CRC PHI, and initialize its incoming value to the initial
1636 // value of CRC.
1637 PHINode *CRCPhi = Builder.CreatePHI(Ty: CRCTy, NumReservedValues: 2, Name: "crc");
1638 CRCPhi->addIncoming(V: Info.LHS, BB: CurLoop->getLoopPreheader());
1639
1640 // CRC is now an evolving variable, initialized to the PHI.
1641 Value *CRC = CRCPhi;
1642
1643 // TableIndexer = ((top|bottom) byte of CRC). It is XOR'ed with (iv'th byte
1644 // of LHSAux), if LHSAux is non-nullptr.
1645 Value *Indexer = CRC;
1646 if (Value *Data = Info.LHSAux) {
1647 Type *DataTy = Data->getType();
1648
1649 // To index into the (iv'th byte of LHSAux), we multiply iv by 8, and we
1650 // shift right by that amount, and take the lo-byte (in the little-endian
1651 // case), or shift left by that amount, and take the hi-idx (in the
1652 // big-endian case).
1653 Value *IVBits = Builder.CreateZExtOrTrunc(
1654 V: Builder.CreateShl(LHS: IV, RHS: 3, Name: "iv.bits"), DestTy: DataTy, Name: "iv.indexer");
1655 Value *DataIndexer =
1656 Info.IsBigEndian ? Builder.CreateShl(LHS: Data, RHS: IVBits, Name: "data.indexer")
1657 : Builder.CreateLShr(LHS: Data, RHS: IVBits, Name: "data.indexer");
1658 Indexer = Builder.CreateXor(
1659 LHS: DataIndexer,
1660 RHS: Builder.CreateZExtOrTrunc(V: Indexer, DestTy: DataTy, Name: "crc.indexer.cast"),
1661 Name: "crc.data.indexer");
1662 }
1663
1664 Indexer = Info.IsBigEndian ? HiIdx(Builder, Indexer, "indexer.hi")
1665 : LoByte(Builder, Indexer, "indexer.lo");
1666
1667 // Always index into a GEP using the index type.
1668 Indexer = Builder.CreateZExt(
1669 V: Indexer, DestTy: SE->getDataLayout().getIndexType(PtrTy: GV->getType()),
1670 Name: "indexer.ext");
1671
1672 // CRCTableLd = CRCTable[(iv'th byte of data) ^ (top|bottom) byte of CRC].
1673 Value *CRCTableGEP =
1674 Builder.CreateInBoundsGEP(Ty: CRCTy, Ptr: GV, IdxList: Indexer, Name: "tbl.ptradd");
1675 Value *CRCTableLd = Builder.CreateLoad(Ty: CRCTy, Ptr: CRCTableGEP, Name: "tbl.ld");
1676
1677 // CRCNext = (CRC (<<|>>) 8) ^ CRCTableLd, or simply CRCTableLd in case of
1678 // CRC-8.
1679 Value *CRCNext = CRCTableLd;
1680 if (CRCBW > 8) {
1681 Value *CRCShift = Info.IsBigEndian
1682 ? Builder.CreateShl(LHS: CRC, RHS: 8, Name: "crc.be.shift")
1683 : Builder.CreateLShr(LHS: CRC, RHS: 8, Name: "crc.le.shift");
1684 CRCNext = Builder.CreateXor(LHS: CRCShift, RHS: CRCTableLd, Name: "crc.next");
1685 }
1686
1687 // Connect the back-edge for the loop, and RAUW the ComputedValue.
1688 CRCPhi->addIncoming(V: CRCNext, BB: CurLoop->getLoopLatch());
1689 Info.ComputedValue->replaceUsesOutsideBlock(V: CRCNext,
1690 BB: CurLoop->getLoopLatch());
1691 }
1692
1693 // Cleanup.
1694 {
1695 for (PHINode *PN : Cleanup)
1696 RecursivelyDeleteDeadPHINode(PN);
1697 SE->forgetLoop(L: CurLoop);
1698 }
1699 return true;
1700}
1701
1702bool LoopIdiomRecognize::runOnNoncountableLoop() {
1703 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["
1704 << CurLoop->getHeader()->getParent()->getName()
1705 << "] Noncountable Loop %"
1706 << CurLoop->getHeader()->getName() << "\n");
1707
1708 return recognizePopcount() || recognizeAndInsertFFS() ||
1709 recognizeShiftUntilBitTest() || recognizeShiftUntilZero() ||
1710 recognizeShiftUntilLessThan() || recognizeAndInsertStrLen();
1711}
1712
1713/// Check if the given conditional branch is based on the comparison between
1714/// a variable and zero, and if the variable is non-zero or zero (JmpOnZero is
1715/// true), the control yields to the loop entry. If the branch matches the
1716/// behavior, the variable involved in the comparison is returned. This function
1717/// will be called to see if the precondition and postcondition of the loop are
1718/// in desirable form.
1719static Value *matchCondition(CondBrInst *BI, BasicBlock *LoopEntry,
1720 bool JmpOnZero = false) {
1721 ICmpInst *Cond = dyn_cast<ICmpInst>(Val: BI->getCondition());
1722 if (!Cond)
1723 return nullptr;
1724
1725 auto *CmpZero = dyn_cast<ConstantInt>(Val: Cond->getOperand(i_nocapture: 1));
1726 if (!CmpZero || !CmpZero->isZero())
1727 return nullptr;
1728
1729 BasicBlock *TrueSucc = BI->getSuccessor(i: 0);
1730 BasicBlock *FalseSucc = BI->getSuccessor(i: 1);
1731 if (JmpOnZero)
1732 std::swap(a&: TrueSucc, b&: FalseSucc);
1733
1734 ICmpInst::Predicate Pred = Cond->getPredicate();
1735 if ((Pred == ICmpInst::ICMP_NE && TrueSucc == LoopEntry) ||
1736 (Pred == ICmpInst::ICMP_EQ && FalseSucc == LoopEntry))
1737 return Cond->getOperand(i_nocapture: 0);
1738
1739 return nullptr;
1740}
1741
1742namespace {
1743
1744class StrlenVerifier {
1745public:
1746 explicit StrlenVerifier(const Loop *CurLoop, ScalarEvolution *SE,
1747 const TargetLibraryInfo *TLI)
1748 : CurLoop(CurLoop), SE(SE), TLI(TLI) {}
1749
1750 bool isValidStrlenIdiom() {
1751 // Give up if the loop has multiple blocks, multiple backedges, or
1752 // multiple exit blocks
1753 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1 ||
1754 !CurLoop->getUniqueExitBlock())
1755 return false;
1756
1757 // It should have a preheader and a branch instruction.
1758 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1759 if (!Preheader ||
1760 !isa<UncondBrInst, CondBrInst>(Val: Preheader->getTerminator()))
1761 return false;
1762
1763 // The loop exit must be conditioned on an icmp with 0 the null terminator.
1764 // The icmp operand has to be a load on some SSA reg that increments
1765 // by 1 in the loop.
1766 BasicBlock *LoopBody = *CurLoop->block_begin();
1767
1768 // Skip if the body is too big as it most likely is not a strlen idiom.
1769 if (!LoopBody || LoopBody->size() >= 15)
1770 return false;
1771
1772 CondBrInst *LoopTerm = dyn_cast<CondBrInst>(Val: LoopBody->getTerminator());
1773 if (!LoopTerm)
1774 return false;
1775 Value *LoopCond = matchCondition(BI: LoopTerm, LoopEntry: LoopBody);
1776 if (!LoopCond)
1777 return false;
1778
1779 LoadInst *LoopLoad = dyn_cast<LoadInst>(Val: LoopCond);
1780 if (!LoopLoad || LoopLoad->getPointerAddressSpace() != 0)
1781 return false;
1782
1783 OperandType = LoopLoad->getType();
1784 if (!OperandType || !OperandType->isIntegerTy())
1785 return false;
1786
1787 // See if the pointer expression is an AddRec with constant step a of form
1788 // ({n,+,a}) where a is the width of the char type.
1789 Value *IncPtr = LoopLoad->getPointerOperand();
1790 const SCEV *LoadEv = SE->getSCEV(V: IncPtr);
1791 const APInt *Step;
1792 if (!match(S: LoadEv,
1793 P: m_scev_AffineAddRec(Op0: m_SCEV(V&: LoadBaseEv), Op1: m_scev_APInt(C&: Step))))
1794 return false;
1795
1796 LLVM_DEBUG(dbgs() << "pointer load scev: " << *LoadEv << "\n");
1797
1798 unsigned StepSize = Step->getZExtValue();
1799
1800 // Verify that StepSize is consistent with platform char width.
1801 OpWidth = OperandType->getIntegerBitWidth();
1802 unsigned WcharSize = TLI->getWCharSize(M: *LoopLoad->getModule());
1803 if (OpWidth != StepSize * 8)
1804 return false;
1805 if (OpWidth != 8 && OpWidth != 16 && OpWidth != 32)
1806 return false;
1807 if (OpWidth >= 16)
1808 if (OpWidth != WcharSize * 8)
1809 return false;
1810
1811 // Scan every instruction in the loop to ensure there are no side effects.
1812 for (Instruction &I : *LoopBody)
1813 if (I.mayHaveSideEffects())
1814 return false;
1815
1816 BasicBlock *LoopExitBB = CurLoop->getExitBlock();
1817 if (!LoopExitBB)
1818 return false;
1819
1820 for (PHINode &PN : LoopExitBB->phis()) {
1821 if (!SE->isSCEVable(Ty: PN.getType()))
1822 return false;
1823
1824 const SCEV *Ev = SE->getSCEV(V: &PN);
1825 if (!Ev)
1826 return false;
1827
1828 LLVM_DEBUG(dbgs() << "loop exit phi scev: " << *Ev << "\n");
1829
1830 // Since we verified that the loop trip count will be a valid strlen
1831 // idiom, we can expand all lcssa phi with {n,+,1} as (n + strlen) and use
1832 // SCEVExpander materialize the loop output.
1833 const SCEVAddRecExpr *AddRecEv = dyn_cast<SCEVAddRecExpr>(Val: Ev);
1834 if (!AddRecEv || !AddRecEv->isAffine())
1835 return false;
1836
1837 // We only want RecAddExpr with recurrence step that is constant. This
1838 // is good enough for all the idioms we want to recognize. Later we expand
1839 // and materialize the recurrence as {base,+,a} -> (base + a * strlen)
1840 if (!isa<SCEVConstant>(Val: AddRecEv->getStepRecurrence(SE&: *SE)))
1841 return false;
1842 }
1843
1844 return true;
1845 }
1846
1847public:
1848 const Loop *CurLoop;
1849 ScalarEvolution *SE;
1850 const TargetLibraryInfo *TLI;
1851
1852 unsigned OpWidth;
1853 ConstantInt *StepSizeCI;
1854 const SCEV *LoadBaseEv;
1855 Type *OperandType;
1856};
1857
1858} // namespace
1859
1860/// The Strlen Idiom we are trying to detect has the following structure
1861///
1862/// preheader:
1863/// ...
1864/// br label %body, ...
1865///
1866/// body:
1867/// ... ; %0 is incremented by a gep
1868/// %1 = load i8, ptr %0, align 1
1869/// %2 = icmp eq i8 %1, 0
1870/// br i1 %2, label %exit, label %body
1871///
1872/// exit:
1873/// %lcssa = phi [%0, %body], ...
1874///
1875/// We expect the strlen idiom to have a load of a character type that
1876/// is compared against '\0', and such load pointer operand must have scev
1877/// expression of the form {%str,+,c} where c is a ConstantInt of the
1878/// appropiate character width for the idiom, and %str is the base of the string
1879/// And, that all lcssa phis have the form {...,+,n} where n is a constant,
1880///
1881/// When transforming the output of the strlen idiom, the lccsa phi are
1882/// expanded using SCEVExpander as {base scev,+,a} -> (base scev + a * strlen)
1883/// and all subsequent uses are replaced. For example,
1884///
1885/// \code{.c}
1886/// const char* base = str;
1887/// while (*str != '\0')
1888/// ++str;
1889/// size_t result = str - base;
1890/// \endcode
1891///
1892/// will be transformed as follows: The idiom will be replaced by a strlen
1893/// computation to compute the address of the null terminator of the string.
1894///
1895/// \code{.c}
1896/// const char* base = str;
1897/// const char* end = base + strlen(str);
1898/// size_t result = end - base;
1899/// \endcode
1900///
1901/// In the case we index by an induction variable, as long as the induction
1902/// variable has a constant int increment, we can replace all such indvars
1903/// with the closed form computation of strlen
1904///
1905/// \code{.c}
1906/// size_t i = 0;
1907/// while (str[i] != '\0')
1908/// ++i;
1909/// size_t result = i;
1910/// \endcode
1911///
1912/// Will be replaced by
1913///
1914/// \code{.c}
1915/// size_t i = 0 + strlen(str);
1916/// size_t result = i;
1917/// \endcode
1918///
1919bool LoopIdiomRecognize::recognizeAndInsertStrLen() {
1920 if (DisableLIRP::All)
1921 return false;
1922
1923 StrlenVerifier Verifier(CurLoop, SE, TLI);
1924
1925 if (!Verifier.isValidStrlenIdiom())
1926 return false;
1927
1928 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1929 BasicBlock *LoopBody = *CurLoop->block_begin();
1930 BasicBlock *LoopExitBB = CurLoop->getExitBlock();
1931 CondBrInst *LoopTerm = cast<CondBrInst>(Val: LoopBody->getTerminator());
1932 assert(Preheader && LoopBody && LoopExitBB &&
1933 "Should be verified to be valid by StrlenVerifier");
1934
1935 if (Verifier.OpWidth == 8) {
1936 if (DisableLIRP::Strlen)
1937 return false;
1938 if (!isLibFuncEmittable(M: Preheader->getModule(), TLI, TheLibFunc: LibFunc_strlen))
1939 return false;
1940 } else {
1941 if (DisableLIRP::Wcslen)
1942 return false;
1943 if (!isLibFuncEmittable(M: Preheader->getModule(), TLI, TheLibFunc: LibFunc_wcslen))
1944 return false;
1945 }
1946
1947 IRBuilder<> Builder(Preheader->getTerminator());
1948 Builder.SetCurrentDebugLocation(CurLoop->getStartLoc());
1949 SCEVExpander Expander(*SE, "strlen_idiom");
1950 Value *MaterialzedBase = Expander.expandCodeFor(
1951 SH: Verifier.LoadBaseEv, Ty: Verifier.LoadBaseEv->getType(),
1952 I: Builder.GetInsertPoint());
1953
1954 Value *StrLenFunc = nullptr;
1955 if (Verifier.OpWidth == 8) {
1956 StrLenFunc = emitStrLen(Ptr: MaterialzedBase, B&: Builder, DL: *DL, TLI);
1957 } else {
1958 StrLenFunc = emitWcsLen(Ptr: MaterialzedBase, B&: Builder, DL: *DL, TLI);
1959 }
1960 assert(StrLenFunc && "Failed to emit strlen function.");
1961
1962 const SCEV *StrlenEv = SE->getSCEV(V: StrLenFunc);
1963 SmallVector<PHINode *, 4> Cleanup;
1964 for (PHINode &PN : LoopExitBB->phis()) {
1965 // We can now materialize the loop output as all phi have scev {base,+,a}.
1966 // We expand the phi as:
1967 // %strlen = call i64 @strlen(%str)
1968 // %phi.new = base expression + step * %strlen
1969 const SCEV *Ev = SE->getSCEV(V: &PN);
1970 const SCEVAddRecExpr *AddRecEv = dyn_cast<SCEVAddRecExpr>(Val: Ev);
1971 const SCEVConstant *Step =
1972 dyn_cast<SCEVConstant>(Val: AddRecEv->getStepRecurrence(SE&: *SE));
1973 const SCEV *Base = AddRecEv->getStart();
1974
1975 // It is safe to truncate to base since if base is narrower than size_t
1976 // the equivalent user code will have to truncate anyways.
1977 const SCEV *NewEv = SE->getAddExpr(
1978 LHS: Base, RHS: SE->getMulExpr(LHS: Step, RHS: SE->getTruncateOrSignExtend(
1979 V: StrlenEv, Ty: Base->getType())));
1980
1981 Value *MaterializedPHI = Expander.expandCodeFor(SH: NewEv, Ty: NewEv->getType(),
1982 I: Builder.GetInsertPoint());
1983 Expander.clear();
1984 PN.replaceAllUsesWith(V: MaterializedPHI);
1985 Cleanup.push_back(Elt: &PN);
1986 }
1987
1988 // All LCSSA Loop Phi are dead, the left over dead loop body can be cleaned
1989 // up by later passes
1990 for (PHINode *PN : Cleanup)
1991 RecursivelyDeleteDeadPHINode(PN);
1992
1993 // LoopDeletion only delete invariant loops with known trip-count. We can
1994 // update the condition so it will reliablely delete the invariant loop
1995 assert((LoopTerm->getSuccessor(0) == LoopBody ||
1996 LoopTerm->getSuccessor(1) == LoopBody) &&
1997 "loop body must have a successor that is it self");
1998 ConstantInt *NewLoopCond = LoopTerm->getSuccessor(i: 0) == LoopBody
1999 ? Builder.getFalse()
2000 : Builder.getTrue();
2001 LoopTerm->setCondition(NewLoopCond);
2002 SE->forgetLoop(L: CurLoop);
2003
2004 ++NumStrLen;
2005 LLVM_DEBUG(dbgs() << " Formed strlen idiom: " << *StrLenFunc << "\n");
2006 ORE.emit(RemarkBuilder: [&]() {
2007 return OptimizationRemark(DEBUG_TYPE, "recognizeAndInsertStrLen",
2008 CurLoop->getStartLoc(), Preheader)
2009 << "Transformed " << StrLenFunc->getName() << " loop idiom";
2010 });
2011
2012 return true;
2013}
2014
2015/// Check if the given conditional branch is based on an unsigned less-than
2016/// comparison between a variable and a constant, and if the comparison is false
2017/// the control yields to the loop entry. If the branch matches the behaviour,
2018/// the variable involved in the comparison is returned.
2019static Value *matchShiftULTCondition(CondBrInst *BI, BasicBlock *LoopEntry,
2020 APInt &Threshold) {
2021 ICmpInst *Cond = dyn_cast<ICmpInst>(Val: BI->getCondition());
2022 if (!Cond)
2023 return nullptr;
2024
2025 ConstantInt *CmpConst = dyn_cast<ConstantInt>(Val: Cond->getOperand(i_nocapture: 1));
2026 if (!CmpConst)
2027 return nullptr;
2028
2029 BasicBlock *FalseSucc = BI->getSuccessor(i: 1);
2030 ICmpInst::Predicate Pred = Cond->getPredicate();
2031
2032 if (Pred == ICmpInst::ICMP_ULT && FalseSucc == LoopEntry) {
2033 Threshold = CmpConst->getValue();
2034 return Cond->getOperand(i_nocapture: 0);
2035 }
2036
2037 return nullptr;
2038}
2039
2040// Check if the recurrence variable `VarX` is in the right form to create
2041// the idiom. Returns the value coerced to a PHINode if so.
2042static PHINode *getRecurrenceVar(Value *VarX, Instruction *DefX,
2043 BasicBlock *LoopEntry) {
2044 auto *PhiX = dyn_cast<PHINode>(Val: VarX);
2045 if (PhiX && PhiX->getParent() == LoopEntry &&
2046 (PhiX->getOperand(i_nocapture: 0) == DefX || PhiX->getOperand(i_nocapture: 1) == DefX))
2047 return PhiX;
2048 return nullptr;
2049}
2050
2051/// Return true if the idiom is detected in the loop.
2052///
2053/// Additionally:
2054/// 1) \p CntInst is set to the instruction Counting Leading Zeros (CTLZ)
2055/// or nullptr if there is no such.
2056/// 2) \p CntPhi is set to the corresponding phi node
2057/// or nullptr if there is no such.
2058/// 3) \p InitX is set to the value whose CTLZ could be used.
2059/// 4) \p DefX is set to the instruction calculating Loop exit condition.
2060/// 5) \p Threshold is set to the constant involved in the unsigned less-than
2061/// comparison.
2062///
2063/// The core idiom we are trying to detect is:
2064/// \code
2065/// if (x0 < 2)
2066/// goto loop-exit // the precondition of the loop
2067/// cnt0 = init-val
2068/// do {
2069/// x = phi (x0, x.next); //PhiX
2070/// cnt = phi (cnt0, cnt.next)
2071///
2072/// cnt.next = cnt + 1;
2073/// ...
2074/// x.next = x >> 1; // DefX
2075/// } while (x >= 4)
2076/// loop-exit:
2077/// \endcode
2078static bool detectShiftUntilLessThanIdiom(Loop *CurLoop, const DataLayout &DL,
2079 Intrinsic::ID &IntrinID,
2080 Value *&InitX, Instruction *&CntInst,
2081 PHINode *&CntPhi, Instruction *&DefX,
2082 APInt &Threshold) {
2083 BasicBlock *LoopEntry;
2084
2085 DefX = nullptr;
2086 CntInst = nullptr;
2087 CntPhi = nullptr;
2088 LoopEntry = *(CurLoop->block_begin());
2089
2090 // step 1: Check if the loop-back branch is in desirable form.
2091 auto *EntryBI = dyn_cast<CondBrInst>(Val: LoopEntry->getTerminator());
2092 if (!EntryBI)
2093 return false;
2094 if (Value *T = matchShiftULTCondition(BI: EntryBI, LoopEntry, Threshold))
2095 DefX = dyn_cast<Instruction>(Val: T);
2096 else
2097 return false;
2098
2099 // step 2: Check the recurrence of variable X
2100 if (!DefX || !isa<PHINode>(Val: DefX))
2101 return false;
2102
2103 PHINode *VarPhi = cast<PHINode>(Val: DefX);
2104 int Idx = VarPhi->getBasicBlockIndex(BB: LoopEntry);
2105 if (Idx == -1)
2106 return false;
2107
2108 DefX = dyn_cast<Instruction>(Val: VarPhi->getIncomingValue(i: Idx));
2109 if (!DefX || DefX->getNumOperands() == 0 || DefX->getOperand(i: 0) != VarPhi)
2110 return false;
2111
2112 // step 3: detect instructions corresponding to "x.next = x >> 1"
2113 if (DefX->getOpcode() != Instruction::LShr)
2114 return false;
2115
2116 IntrinID = Intrinsic::ctlz;
2117 ConstantInt *Shft = dyn_cast<ConstantInt>(Val: DefX->getOperand(i: 1));
2118 if (!Shft || !Shft->isOne())
2119 return false;
2120
2121 InitX = VarPhi->getIncomingValueForBlock(BB: CurLoop->getLoopPreheader());
2122
2123 // step 4: Find the instruction which count the CTLZ: cnt.next = cnt + 1
2124 // or cnt.next = cnt + -1.
2125 // TODO: We can skip the step. If loop trip count is known (CTLZ),
2126 // then all uses of "cnt.next" could be optimized to the trip count
2127 // plus "cnt0". Currently it is not optimized.
2128 // This step could be used to detect POPCNT instruction:
2129 // cnt.next = cnt + (x.next & 1)
2130 for (Instruction &Inst :
2131 llvm::make_range(x: LoopEntry->getFirstNonPHIIt(), y: LoopEntry->end())) {
2132 if (Inst.getOpcode() != Instruction::Add)
2133 continue;
2134
2135 ConstantInt *Inc = dyn_cast<ConstantInt>(Val: Inst.getOperand(i: 1));
2136 if (!Inc || (!Inc->isOne() && !Inc->isMinusOne()))
2137 continue;
2138
2139 PHINode *Phi = getRecurrenceVar(VarX: Inst.getOperand(i: 0), DefX: &Inst, LoopEntry);
2140 if (!Phi)
2141 continue;
2142
2143 CntInst = &Inst;
2144 CntPhi = Phi;
2145 break;
2146 }
2147 if (!CntInst)
2148 return false;
2149
2150 return true;
2151}
2152
2153/// Return true iff the idiom is detected in the loop.
2154///
2155/// Additionally:
2156/// 1) \p CntInst is set to the instruction counting the population bit.
2157/// 2) \p CntPhi is set to the corresponding phi node.
2158/// 3) \p Var is set to the value whose population bits are being counted.
2159///
2160/// The core idiom we are trying to detect is:
2161/// \code
2162/// if (x0 != 0)
2163/// goto loop-exit // the precondition of the loop
2164/// cnt0 = init-val;
2165/// do {
2166/// x1 = phi (x0, x2);
2167/// cnt1 = phi(cnt0, cnt2);
2168///
2169/// cnt2 = cnt1 + 1;
2170/// ...
2171/// x2 = x1 & (x1 - 1);
2172/// ...
2173/// } while(x != 0);
2174///
2175/// loop-exit:
2176/// \endcode
2177static bool detectPopcountIdiom(Loop *CurLoop, BasicBlock *PreCondBB,
2178 Instruction *&CntInst, PHINode *&CntPhi,
2179 Value *&Var) {
2180 // step 1: Check to see if the look-back branch match this pattern:
2181 // "if (a!=0) goto loop-entry".
2182 BasicBlock *LoopEntry;
2183 Instruction *DefX2, *CountInst;
2184 Value *VarX1, *VarX0;
2185 PHINode *PhiX, *CountPhi;
2186
2187 DefX2 = CountInst = nullptr;
2188 VarX1 = VarX0 = nullptr;
2189 PhiX = CountPhi = nullptr;
2190 LoopEntry = *(CurLoop->block_begin());
2191
2192 // step 1: Check if the loop-back branch is in desirable form.
2193 {
2194 auto *LoopTerm = dyn_cast<CondBrInst>(Val: LoopEntry->getTerminator());
2195 if (!LoopTerm)
2196 return false;
2197 DefX2 = dyn_cast_or_null<Instruction>(Val: matchCondition(BI: LoopTerm, LoopEntry));
2198 }
2199
2200 // step 2: detect instructions corresponding to "x2 = x1 & (x1 - 1)"
2201 {
2202 if (!DefX2 || DefX2->getOpcode() != Instruction::And)
2203 return false;
2204
2205 BinaryOperator *SubOneOp;
2206
2207 if ((SubOneOp = dyn_cast<BinaryOperator>(Val: DefX2->getOperand(i: 0))))
2208 VarX1 = DefX2->getOperand(i: 1);
2209 else {
2210 VarX1 = DefX2->getOperand(i: 0);
2211 SubOneOp = dyn_cast<BinaryOperator>(Val: DefX2->getOperand(i: 1));
2212 }
2213 if (!SubOneOp || SubOneOp->getOperand(i_nocapture: 0) != VarX1)
2214 return false;
2215
2216 ConstantInt *Dec = dyn_cast<ConstantInt>(Val: SubOneOp->getOperand(i_nocapture: 1));
2217 if (!Dec ||
2218 !((SubOneOp->getOpcode() == Instruction::Sub && Dec->isOne()) ||
2219 (SubOneOp->getOpcode() == Instruction::Add &&
2220 Dec->isMinusOne()))) {
2221 return false;
2222 }
2223 }
2224
2225 // step 3: Check the recurrence of variable X
2226 PhiX = getRecurrenceVar(VarX: VarX1, DefX: DefX2, LoopEntry);
2227 if (!PhiX)
2228 return false;
2229
2230 // step 4: Find the instruction which count the population: cnt2 = cnt1 + 1
2231 {
2232 CountInst = nullptr;
2233 for (Instruction &Inst :
2234 llvm::make_range(x: LoopEntry->getFirstNonPHIIt(), y: LoopEntry->end())) {
2235 if (Inst.getOpcode() != Instruction::Add)
2236 continue;
2237
2238 ConstantInt *Inc = dyn_cast<ConstantInt>(Val: Inst.getOperand(i: 1));
2239 if (!Inc || !Inc->isOne())
2240 continue;
2241
2242 PHINode *Phi = getRecurrenceVar(VarX: Inst.getOperand(i: 0), DefX: &Inst, LoopEntry);
2243 if (!Phi)
2244 continue;
2245
2246 // Check if the result of the instruction is live of the loop.
2247 bool LiveOutLoop = false;
2248 for (User *U : Inst.users()) {
2249 if ((cast<Instruction>(Val: U))->getParent() != LoopEntry) {
2250 LiveOutLoop = true;
2251 break;
2252 }
2253 }
2254
2255 if (LiveOutLoop) {
2256 CountInst = &Inst;
2257 CountPhi = Phi;
2258 break;
2259 }
2260 }
2261
2262 if (!CountInst)
2263 return false;
2264 }
2265
2266 // step 5: check if the precondition is in this form:
2267 // "if (x != 0) goto loop-head ; else goto somewhere-we-don't-care;"
2268 {
2269 auto *PreCondBr = dyn_cast<CondBrInst>(Val: PreCondBB->getTerminator());
2270 if (!PreCondBr)
2271 return false;
2272 Value *T = matchCondition(BI: PreCondBr, LoopEntry: CurLoop->getLoopPreheader());
2273 if (T != PhiX->getOperand(i_nocapture: 0) && T != PhiX->getOperand(i_nocapture: 1))
2274 return false;
2275
2276 CntInst = CountInst;
2277 CntPhi = CountPhi;
2278 Var = T;
2279 }
2280
2281 return true;
2282}
2283
2284/// Return true if the idiom is detected in the loop.
2285///
2286/// Additionally:
2287/// 1) \p CntInst is set to the instruction Counting Leading Zeros (CTLZ)
2288/// or nullptr if there is no such.
2289/// 2) \p CntPhi is set to the corresponding phi node
2290/// or nullptr if there is no such.
2291/// 3) \p Var is set to the value whose CTLZ could be used.
2292/// 4) \p DefX is set to the instruction calculating Loop exit condition.
2293///
2294/// The core idiom we are trying to detect is:
2295/// \code
2296/// if (x0 == 0)
2297/// goto loop-exit // the precondition of the loop
2298/// cnt0 = init-val;
2299/// do {
2300/// x = phi (x0, x.next); //PhiX
2301/// cnt = phi(cnt0, cnt.next);
2302///
2303/// cnt.next = cnt + 1;
2304/// ...
2305/// x.next = x >> 1; // DefX
2306/// ...
2307/// } while(x.next != 0);
2308///
2309/// loop-exit:
2310/// \endcode
2311static bool detectShiftUntilZeroIdiom(Loop *CurLoop, const DataLayout &DL,
2312 Intrinsic::ID &IntrinID, Value *&InitX,
2313 Instruction *&CntInst, PHINode *&CntPhi,
2314 Instruction *&DefX) {
2315 BasicBlock *LoopEntry;
2316 Value *VarX = nullptr;
2317
2318 DefX = nullptr;
2319 CntInst = nullptr;
2320 CntPhi = nullptr;
2321 LoopEntry = *(CurLoop->block_begin());
2322
2323 // step 1: Check if the loop-back branch is in desirable form.
2324 auto *LoopTerm = dyn_cast<CondBrInst>(Val: LoopEntry->getTerminator());
2325 if (!LoopTerm)
2326 return false;
2327 DefX = dyn_cast_or_null<Instruction>(Val: matchCondition(BI: LoopTerm, LoopEntry));
2328
2329 // step 2: detect instructions corresponding to "x.next = x >> 1 or x << 1"
2330 if (!DefX || !DefX->isShift())
2331 return false;
2332 IntrinID = DefX->getOpcode() == Instruction::Shl ? Intrinsic::cttz :
2333 Intrinsic::ctlz;
2334 ConstantInt *Shft = dyn_cast<ConstantInt>(Val: DefX->getOperand(i: 1));
2335 if (!Shft || !Shft->isOne())
2336 return false;
2337 VarX = DefX->getOperand(i: 0);
2338
2339 // step 3: Check the recurrence of variable X
2340 PHINode *PhiX = getRecurrenceVar(VarX, DefX, LoopEntry);
2341 if (!PhiX)
2342 return false;
2343
2344 InitX = PhiX->getIncomingValueForBlock(BB: CurLoop->getLoopPreheader());
2345
2346 // Make sure the initial value can't be negative otherwise the ashr in the
2347 // loop might never reach zero which would make the loop infinite.
2348 if (DefX->getOpcode() == Instruction::AShr && !isKnownNonNegative(V: InitX, SQ: DL))
2349 return false;
2350
2351 // step 4: Find the instruction which count the CTLZ: cnt.next = cnt + 1
2352 // or cnt.next = cnt + -1.
2353 // TODO: We can skip the step. If loop trip count is known (CTLZ),
2354 // then all uses of "cnt.next" could be optimized to the trip count
2355 // plus "cnt0". Currently it is not optimized.
2356 // This step could be used to detect POPCNT instruction:
2357 // cnt.next = cnt + (x.next & 1)
2358 for (Instruction &Inst :
2359 llvm::make_range(x: LoopEntry->getFirstNonPHIIt(), y: LoopEntry->end())) {
2360 if (Inst.getOpcode() != Instruction::Add)
2361 continue;
2362
2363 ConstantInt *Inc = dyn_cast<ConstantInt>(Val: Inst.getOperand(i: 1));
2364 if (!Inc || (!Inc->isOne() && !Inc->isMinusOne()))
2365 continue;
2366
2367 PHINode *Phi = getRecurrenceVar(VarX: Inst.getOperand(i: 0), DefX: &Inst, LoopEntry);
2368 if (!Phi)
2369 continue;
2370
2371 CntInst = &Inst;
2372 CntPhi = Phi;
2373 break;
2374 }
2375 if (!CntInst)
2376 return false;
2377
2378 return true;
2379}
2380
2381// Check if CTLZ / CTTZ intrinsic is profitable. Assume it is always
2382// profitable if we delete the loop.
2383bool LoopIdiomRecognize::isProfitableToInsertFFS(Intrinsic::ID IntrinID,
2384 Value *InitX, bool ZeroCheck,
2385 size_t CanonicalSize) {
2386 const Value *Args[] = {InitX,
2387 ConstantInt::getBool(Context&: InitX->getContext(), V: ZeroCheck)};
2388
2389 uint32_t HeaderSize = CurLoop->getHeader()->size();
2390
2391 IntrinsicCostAttributes Attrs(IntrinID, InitX->getType(), Args);
2392 InstructionCost Cost = TTI->getIntrinsicInstrCost(
2393 ICA: Attrs, CostKind: TargetTransformInfo::TCK_SizeAndLatency);
2394 if (HeaderSize != CanonicalSize && Cost > TargetTransformInfo::TCC_Basic)
2395 return false;
2396
2397 return true;
2398}
2399
2400/// Convert CTLZ / CTTZ idiom loop into countable loop.
2401/// If CTLZ / CTTZ inserted as a new trip count returns true; otherwise,
2402/// returns false.
2403bool LoopIdiomRecognize::insertFFSIfProfitable(Intrinsic::ID IntrinID,
2404 Value *InitX, Instruction *DefX,
2405 PHINode *CntPhi,
2406 Instruction *CntInst) {
2407 bool IsCntPhiUsedOutsideLoop = false;
2408 for (User *U : CntPhi->users())
2409 if (!CurLoop->contains(Inst: cast<Instruction>(Val: U))) {
2410 IsCntPhiUsedOutsideLoop = true;
2411 break;
2412 }
2413 bool IsCntInstUsedOutsideLoop = false;
2414 for (User *U : CntInst->users())
2415 if (!CurLoop->contains(Inst: cast<Instruction>(Val: U))) {
2416 IsCntInstUsedOutsideLoop = true;
2417 break;
2418 }
2419 // If both CntInst and CntPhi are used outside the loop the profitability
2420 // is questionable.
2421 if (IsCntInstUsedOutsideLoop && IsCntPhiUsedOutsideLoop)
2422 return false;
2423
2424 // For some CPUs result of CTLZ(X) intrinsic is undefined
2425 // when X is 0. If we can not guarantee X != 0, we need to check this
2426 // when expand.
2427 bool ZeroCheck = false;
2428 // It is safe to assume Preheader exist as it was checked in
2429 // parent function RunOnLoop.
2430 BasicBlock *PH = CurLoop->getLoopPreheader();
2431
2432 // If we are using the count instruction outside the loop, make sure we
2433 // have a zero check as a precondition. Without the check the loop would run
2434 // one iteration for before any check of the input value. This means 0 and 1
2435 // would have identical behavior in the original loop and thus
2436 if (!IsCntPhiUsedOutsideLoop) {
2437 auto *PreCondBB = PH->getSinglePredecessor();
2438 if (!PreCondBB)
2439 return false;
2440 auto *PreCondBI = dyn_cast<CondBrInst>(Val: PreCondBB->getTerminator());
2441 if (!PreCondBI)
2442 return false;
2443 if (matchCondition(BI: PreCondBI, LoopEntry: PH) != InitX)
2444 return false;
2445 ZeroCheck = true;
2446 }
2447
2448 // FFS idiom loop has only 6 instructions:
2449 // %n.addr.0 = phi [ %n, %entry ], [ %shr, %while.cond ]
2450 // %i.0 = phi [ %i0, %entry ], [ %inc, %while.cond ]
2451 // %shr = ashr %n.addr.0, 1
2452 // %tobool = icmp eq %shr, 0
2453 // %inc = add nsw %i.0, 1
2454 // br i1 %tobool
2455 size_t IdiomCanonicalSize = 6;
2456 if (!isProfitableToInsertFFS(IntrinID, InitX, ZeroCheck, CanonicalSize: IdiomCanonicalSize))
2457 return false;
2458
2459 transformLoopToCountable(IntrinID, PreCondBB: PH, CntInst, CntPhi, Var: InitX, DefX,
2460 DL: DefX->getDebugLoc(), ZeroCheck,
2461 IsCntPhiUsedOutsideLoop);
2462 return true;
2463}
2464
2465/// Recognize CTLZ or CTTZ idiom in a non-countable loop and convert the loop
2466/// to countable (with CTLZ / CTTZ trip count). If CTLZ / CTTZ inserted as a new
2467/// trip count returns true; otherwise, returns false.
2468bool LoopIdiomRecognize::recognizeAndInsertFFS() {
2469 // Give up if the loop has multiple blocks or multiple backedges.
2470 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
2471 return false;
2472
2473 Intrinsic::ID IntrinID;
2474 Value *InitX;
2475 Instruction *DefX = nullptr;
2476 PHINode *CntPhi = nullptr;
2477 Instruction *CntInst = nullptr;
2478
2479 if (!detectShiftUntilZeroIdiom(CurLoop, DL: *DL, IntrinID, InitX, CntInst, CntPhi,
2480 DefX))
2481 return false;
2482
2483 return insertFFSIfProfitable(IntrinID, InitX, DefX, CntPhi, CntInst);
2484}
2485
2486bool LoopIdiomRecognize::recognizeShiftUntilLessThan() {
2487 // Give up if the loop has multiple blocks or multiple backedges.
2488 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
2489 return false;
2490
2491 Intrinsic::ID IntrinID;
2492 Value *InitX;
2493 Instruction *DefX = nullptr;
2494 PHINode *CntPhi = nullptr;
2495 Instruction *CntInst = nullptr;
2496
2497 APInt LoopThreshold;
2498 if (!detectShiftUntilLessThanIdiom(CurLoop, DL: *DL, IntrinID, InitX, CntInst,
2499 CntPhi, DefX, Threshold&: LoopThreshold))
2500 return false;
2501
2502 if (LoopThreshold == 2) {
2503 // Treat as regular FFS.
2504 return insertFFSIfProfitable(IntrinID, InitX, DefX, CntPhi, CntInst);
2505 }
2506
2507 // Look for Floor Log2 Idiom.
2508 if (LoopThreshold != 4)
2509 return false;
2510
2511 // Abort if CntPhi is used outside of the loop.
2512 for (User *U : CntPhi->users())
2513 if (!CurLoop->contains(Inst: cast<Instruction>(Val: U)))
2514 return false;
2515
2516 // It is safe to assume Preheader exist as it was checked in
2517 // parent function RunOnLoop.
2518 BasicBlock *PH = CurLoop->getLoopPreheader();
2519 auto *PreCondBB = PH->getSinglePredecessor();
2520 if (!PreCondBB)
2521 return false;
2522 auto *PreCondBI = dyn_cast<CondBrInst>(Val: PreCondBB->getTerminator());
2523 if (!PreCondBI)
2524 return false;
2525
2526 APInt PreLoopThreshold;
2527 if (matchShiftULTCondition(BI: PreCondBI, LoopEntry: PH, Threshold&: PreLoopThreshold) != InitX ||
2528 PreLoopThreshold != 2)
2529 return false;
2530
2531 bool ZeroCheck = true;
2532
2533 // the loop has only 6 instructions:
2534 // %n.addr.0 = phi [ %n, %entry ], [ %shr, %while.cond ]
2535 // %i.0 = phi [ %i0, %entry ], [ %inc, %while.cond ]
2536 // %shr = ashr %n.addr.0, 1
2537 // %tobool = icmp ult %n.addr.0, C
2538 // %inc = add nsw %i.0, 1
2539 // br i1 %tobool
2540 size_t IdiomCanonicalSize = 6;
2541 if (!isProfitableToInsertFFS(IntrinID, InitX, ZeroCheck, CanonicalSize: IdiomCanonicalSize))
2542 return false;
2543
2544 // log2(x) = w − 1 − clz(x)
2545 transformLoopToCountable(IntrinID, PreCondBB: PH, CntInst, CntPhi, Var: InitX, DefX,
2546 DL: DefX->getDebugLoc(), ZeroCheck,
2547 /*IsCntPhiUsedOutsideLoop=*/false,
2548 /*InsertSub=*/true);
2549 return true;
2550}
2551
2552/// Recognizes a population count idiom in a non-countable loop.
2553///
2554/// If detected, transforms the relevant code to issue the popcount intrinsic
2555/// function call, and returns true; otherwise, returns false.
2556bool LoopIdiomRecognize::recognizePopcount() {
2557 if (TTI->getPopcntSupport(IntTyWidthInBit: 32) != TargetTransformInfo::PSK_FastHardware)
2558 return false;
2559
2560 // Counting population are usually conducted by few arithmetic instructions.
2561 // Such instructions can be easily "absorbed" by vacant slots in a
2562 // non-compact loop. Therefore, recognizing popcount idiom only makes sense
2563 // in a compact loop.
2564
2565 // Give up if the loop has multiple blocks or multiple backedges.
2566 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
2567 return false;
2568
2569 BasicBlock *LoopBody = *(CurLoop->block_begin());
2570 if (LoopBody->size() >= 20) {
2571 // The loop is too big, bail out.
2572 return false;
2573 }
2574
2575 // It should have a preheader containing nothing but an unconditional branch.
2576 BasicBlock *PH = CurLoop->getLoopPreheader();
2577 if (!PH || &PH->front() != PH->getTerminator())
2578 return false;
2579 auto *EntryBI = dyn_cast<UncondBrInst>(Val: PH->getTerminator());
2580 if (!EntryBI)
2581 return false;
2582
2583 // It should have a precondition block where the generated popcount intrinsic
2584 // function can be inserted.
2585 auto *PreCondBB = PH->getSinglePredecessor();
2586 if (!PreCondBB)
2587 return false;
2588 auto *PreCondBI = dyn_cast<CondBrInst>(Val: PreCondBB->getTerminator());
2589 if (!PreCondBI)
2590 return false;
2591
2592 Instruction *CntInst;
2593 PHINode *CntPhi;
2594 Value *Val;
2595 if (!detectPopcountIdiom(CurLoop, PreCondBB, CntInst, CntPhi, Var&: Val))
2596 return false;
2597
2598 transformLoopToPopcount(PreCondBB, CntInst, CntPhi, Var: Val);
2599 return true;
2600}
2601
2602static Value *createPopcntIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
2603 const DebugLoc &DL) {
2604 Value *Ops[] = {Val};
2605 Type *Tys[] = {Val->getType()};
2606
2607 IRBuilder.SetCurrentDebugLocation(DL);
2608 return IRBuilder.CreateIntrinsic(ID: Intrinsic::ctpop, OverloadTypes: Tys, Args: Ops);
2609}
2610
2611static Value *createFFSIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
2612 const DebugLoc &DL, bool ZeroCheck,
2613 Intrinsic::ID IID) {
2614 Value *Ops[] = {Val, IRBuilder.getInt1(V: ZeroCheck)};
2615 Type *Tys[] = {Val->getType()};
2616
2617 IRBuilder.SetCurrentDebugLocation(DL);
2618 return IRBuilder.CreateIntrinsic(ID: IID, OverloadTypes: Tys, Args: Ops);
2619}
2620
2621/// Transform the following loop (Using CTLZ, CTTZ is similar):
2622/// loop:
2623/// CntPhi = PHI [Cnt0, CntInst]
2624/// PhiX = PHI [InitX, DefX]
2625/// CntInst = CntPhi + 1
2626/// DefX = PhiX >> 1
2627/// LOOP_BODY
2628/// Br: loop if (DefX != 0)
2629/// Use(CntPhi) or Use(CntInst)
2630///
2631/// Into:
2632/// If CntPhi used outside the loop:
2633/// CountPrev = BitWidth(InitX) - CTLZ(InitX >> 1)
2634/// Count = CountPrev + 1
2635/// else
2636/// Count = BitWidth(InitX) - CTLZ(InitX)
2637/// loop:
2638/// CntPhi = PHI [Cnt0, CntInst]
2639/// PhiX = PHI [InitX, DefX]
2640/// PhiCount = PHI [Count, Dec]
2641/// CntInst = CntPhi + 1
2642/// DefX = PhiX >> 1
2643/// Dec = PhiCount - 1
2644/// LOOP_BODY
2645/// Br: loop if (Dec != 0)
2646/// Use(CountPrev + Cnt0) // Use(CntPhi)
2647/// or
2648/// Use(Count + Cnt0) // Use(CntInst)
2649///
2650/// If LOOP_BODY is empty the loop will be deleted.
2651/// If CntInst and DefX are not used in LOOP_BODY they will be removed.
2652void LoopIdiomRecognize::transformLoopToCountable(
2653 Intrinsic::ID IntrinID, BasicBlock *Preheader, Instruction *CntInst,
2654 PHINode *CntPhi, Value *InitX, Instruction *DefX, const DebugLoc &DL,
2655 bool ZeroCheck, bool IsCntPhiUsedOutsideLoop, bool InsertSub) {
2656 // Step 1: Insert the CTLZ/CTTZ instruction at the end of the preheader block
2657 IRBuilder<> Builder(Preheader->getTerminator());
2658 Builder.SetCurrentDebugLocation(DL);
2659
2660 // If there are no uses of CntPhi crate:
2661 // Count = BitWidth - CTLZ(InitX);
2662 // NewCount = Count;
2663 // If there are uses of CntPhi create:
2664 // NewCount = BitWidth - CTLZ(InitX >> 1);
2665 // Count = NewCount + 1;
2666 Value *InitXNext;
2667 if (IsCntPhiUsedOutsideLoop) {
2668 if (DefX->getOpcode() == Instruction::AShr)
2669 InitXNext = Builder.CreateAShr(LHS: InitX, RHS: 1);
2670 else if (DefX->getOpcode() == Instruction::LShr)
2671 InitXNext = Builder.CreateLShr(LHS: InitX, RHS: 1);
2672 else if (DefX->getOpcode() == Instruction::Shl) // cttz
2673 InitXNext = Builder.CreateShl(LHS: InitX, RHS: 1);
2674 else
2675 llvm_unreachable("Unexpected opcode!");
2676 } else
2677 InitXNext = InitX;
2678 Value *Count =
2679 createFFSIntrinsic(IRBuilder&: Builder, Val: InitXNext, DL, ZeroCheck, IID: IntrinID);
2680 Type *CountTy = Count->getType();
2681 Count = Builder.CreateSub(
2682 LHS: ConstantInt::get(Ty: CountTy, V: CountTy->getIntegerBitWidth()), RHS: Count);
2683 if (InsertSub)
2684 Count = Builder.CreateSub(LHS: Count, RHS: ConstantInt::get(Ty: CountTy, V: 1));
2685 Value *NewCount = Count;
2686 if (IsCntPhiUsedOutsideLoop)
2687 Count = Builder.CreateAdd(LHS: Count, RHS: ConstantInt::get(Ty: CountTy, V: 1));
2688
2689 NewCount = Builder.CreateZExtOrTrunc(V: NewCount, DestTy: CntInst->getType());
2690
2691 Value *CntInitVal = CntPhi->getIncomingValueForBlock(BB: Preheader);
2692 if (cast<ConstantInt>(Val: CntInst->getOperand(i: 1))->isOne()) {
2693 // If the counter was being incremented in the loop, add NewCount to the
2694 // counter's initial value, but only if the initial value is not zero.
2695 ConstantInt *InitConst = dyn_cast<ConstantInt>(Val: CntInitVal);
2696 if (!InitConst || !InitConst->isZero())
2697 NewCount = Builder.CreateAdd(LHS: NewCount, RHS: CntInitVal);
2698 } else {
2699 // If the count was being decremented in the loop, subtract NewCount from
2700 // the counter's initial value.
2701 NewCount = Builder.CreateSub(LHS: CntInitVal, RHS: NewCount);
2702 }
2703
2704 // Step 2: Insert new IV and loop condition:
2705 // loop:
2706 // ...
2707 // PhiCount = PHI [Count, Dec]
2708 // ...
2709 // Dec = PhiCount - 1
2710 // ...
2711 // Br: loop if (Dec != 0)
2712 BasicBlock *Body = *(CurLoop->block_begin());
2713 auto *LbBr = cast<CondBrInst>(Val: Body->getTerminator());
2714 ICmpInst *LbCond = cast<ICmpInst>(Val: LbBr->getCondition());
2715
2716 PHINode *TcPhi = PHINode::Create(Ty: CountTy, NumReservedValues: 2, NameStr: "tcphi");
2717 TcPhi->insertBefore(InsertPos: Body->begin());
2718
2719 Builder.SetInsertPoint(LbCond);
2720 Instruction *TcDec = cast<Instruction>(Val: Builder.CreateSub(
2721 LHS: TcPhi, RHS: ConstantInt::get(Ty: CountTy, V: 1), Name: "tcdec", HasNUW: false, HasNSW: true));
2722
2723 TcPhi->addIncoming(V: Count, BB: Preheader);
2724 TcPhi->addIncoming(V: TcDec, BB: Body);
2725
2726 CmpInst::Predicate Pred =
2727 (LbBr->getSuccessor(i: 0) == Body) ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ;
2728 LbCond->setPredicate(Pred);
2729 LbCond->setOperand(i_nocapture: 0, Val_nocapture: TcDec);
2730 LbCond->setOperand(i_nocapture: 1, Val_nocapture: ConstantInt::get(Ty: CountTy, V: 0));
2731
2732 // Step 3: All the references to the original counter outside
2733 // the loop are replaced with the NewCount
2734 if (IsCntPhiUsedOutsideLoop)
2735 CntPhi->replaceUsesOutsideBlock(V: NewCount, BB: Body);
2736 else
2737 CntInst->replaceUsesOutsideBlock(V: NewCount, BB: Body);
2738
2739 // step 4: Forget the "non-computable" trip-count SCEV associated with the
2740 // loop. The loop would otherwise not be deleted even if it becomes empty.
2741 SE->forgetLoop(L: CurLoop);
2742}
2743
2744void LoopIdiomRecognize::transformLoopToPopcount(BasicBlock *PreCondBB,
2745 Instruction *CntInst,
2746 PHINode *CntPhi, Value *Var) {
2747 BasicBlock *PreHead = CurLoop->getLoopPreheader();
2748 auto *PreCondBr = cast<CondBrInst>(Val: PreCondBB->getTerminator());
2749 const DebugLoc &DL = CntInst->getDebugLoc();
2750
2751 // Assuming before transformation, the loop is following:
2752 // if (x) // the precondition
2753 // do { cnt++; x &= x - 1; } while(x);
2754
2755 // Step 1: Insert the ctpop instruction at the end of the precondition block
2756 IRBuilder<> Builder(PreCondBr);
2757 Value *PopCnt, *PopCntZext, *NewCount, *TripCnt;
2758 {
2759 PopCnt = createPopcntIntrinsic(IRBuilder&: Builder, Val: Var, DL);
2760 NewCount = PopCntZext =
2761 Builder.CreateZExtOrTrunc(V: PopCnt, DestTy: cast<IntegerType>(Val: CntPhi->getType()));
2762
2763 if (NewCount != PopCnt)
2764 (cast<Instruction>(Val: NewCount))->setDebugLoc(DL);
2765
2766 // TripCnt is exactly the number of iterations the loop has
2767 TripCnt = NewCount;
2768
2769 // If the population counter's initial value is not zero, insert Add Inst.
2770 Value *CntInitVal = CntPhi->getIncomingValueForBlock(BB: PreHead);
2771 ConstantInt *InitConst = dyn_cast<ConstantInt>(Val: CntInitVal);
2772 if (!InitConst || !InitConst->isZero()) {
2773 NewCount = Builder.CreateAdd(LHS: NewCount, RHS: CntInitVal);
2774 (cast<Instruction>(Val: NewCount))->setDebugLoc(DL);
2775 }
2776 }
2777
2778 // Step 2: Replace the precondition from "if (x == 0) goto loop-exit" to
2779 // "if (NewCount == 0) loop-exit". Without this change, the intrinsic
2780 // function would be partial dead code, and downstream passes will drag
2781 // it back from the precondition block to the preheader.
2782 {
2783 ICmpInst *PreCond = cast<ICmpInst>(Val: PreCondBr->getCondition());
2784
2785 Value *Opnd0 = PopCntZext;
2786 Value *Opnd1 = ConstantInt::get(Ty: PopCntZext->getType(), V: 0);
2787 if (PreCond->getOperand(i_nocapture: 0) != Var)
2788 std::swap(a&: Opnd0, b&: Opnd1);
2789
2790 ICmpInst *NewPreCond = cast<ICmpInst>(
2791 Val: Builder.CreateICmp(P: PreCond->getPredicate(), LHS: Opnd0, RHS: Opnd1));
2792 PreCondBr->setCondition(NewPreCond);
2793
2794 RecursivelyDeleteTriviallyDeadInstructions(V: PreCond, TLI);
2795 }
2796
2797 // Step 3: Note that the population count is exactly the trip count of the
2798 // loop in question, which enable us to convert the loop from noncountable
2799 // loop into a countable one. The benefit is twofold:
2800 //
2801 // - If the loop only counts population, the entire loop becomes dead after
2802 // the transformation. It is a lot easier to prove a countable loop dead
2803 // than to prove a noncountable one. (In some C dialects, an infinite loop
2804 // isn't dead even if it computes nothing useful. In general, DCE needs
2805 // to prove a noncountable loop finite before safely delete it.)
2806 //
2807 // - If the loop also performs something else, it remains alive.
2808 // Since it is transformed to countable form, it can be aggressively
2809 // optimized by some optimizations which are in general not applicable
2810 // to a noncountable loop.
2811 //
2812 // After this step, this loop (conceptually) would look like following:
2813 // newcnt = __builtin_ctpop(x);
2814 // t = newcnt;
2815 // if (x)
2816 // do { cnt++; x &= x-1; t--) } while (t > 0);
2817 BasicBlock *Body = *(CurLoop->block_begin());
2818 {
2819 auto *LbBr = cast<CondBrInst>(Val: Body->getTerminator());
2820 ICmpInst *LbCond = cast<ICmpInst>(Val: LbBr->getCondition());
2821 Type *Ty = TripCnt->getType();
2822
2823 PHINode *TcPhi = PHINode::Create(Ty, NumReservedValues: 2, NameStr: "tcphi");
2824 TcPhi->insertBefore(InsertPos: Body->begin());
2825
2826 Builder.SetInsertPoint(LbCond);
2827 Instruction *TcDec = cast<Instruction>(
2828 Val: Builder.CreateSub(LHS: TcPhi, RHS: ConstantInt::get(Ty, V: 1),
2829 Name: "tcdec", HasNUW: false, HasNSW: true));
2830
2831 TcPhi->addIncoming(V: TripCnt, BB: PreHead);
2832 TcPhi->addIncoming(V: TcDec, BB: Body);
2833
2834 CmpInst::Predicate Pred =
2835 (LbBr->getSuccessor(i: 0) == Body) ? CmpInst::ICMP_UGT : CmpInst::ICMP_SLE;
2836 LbCond->setPredicate(Pred);
2837 LbCond->setOperand(i_nocapture: 0, Val_nocapture: TcDec);
2838 LbCond->setOperand(i_nocapture: 1, Val_nocapture: ConstantInt::get(Ty, V: 0));
2839 }
2840
2841 // Step 4: All the references to the original population counter outside
2842 // the loop are replaced with the NewCount -- the value returned from
2843 // __builtin_ctpop().
2844 CntInst->replaceUsesOutsideBlock(V: NewCount, BB: Body);
2845
2846 // step 5: Forget the "non-computable" trip-count SCEV associated with the
2847 // loop. The loop would otherwise not be deleted even if it becomes empty.
2848 SE->forgetLoop(L: CurLoop);
2849}
2850
2851/// Match loop-invariant value.
2852template <typename SubPattern_t> struct match_LoopInvariant {
2853 SubPattern_t SubPattern;
2854 const Loop *L;
2855
2856 match_LoopInvariant(const SubPattern_t &SP, const Loop *L)
2857 : SubPattern(SP), L(L) {}
2858
2859 template <typename ITy> bool match(ITy *V) const {
2860 return L->isLoopInvariant(V) && SubPattern.match(V);
2861 }
2862};
2863
2864/// Matches if the value is loop-invariant.
2865template <typename Ty>
2866inline match_LoopInvariant<Ty> m_LoopInvariant(const Ty &M, const Loop *L) {
2867 return match_LoopInvariant<Ty>(M, L);
2868}
2869
2870/// Return true if the idiom is detected in the loop.
2871///
2872/// The core idiom we are trying to detect is:
2873/// \code
2874/// entry:
2875/// <...>
2876/// %bitmask = shl i32 1, %bitpos
2877/// br label %loop
2878///
2879/// loop:
2880/// %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
2881/// %x.curr.bitmasked = and i32 %x.curr, %bitmask
2882/// %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
2883/// %x.next = shl i32 %x.curr, 1
2884/// <...>
2885/// br i1 %x.curr.isbitunset, label %loop, label %end
2886///
2887/// end:
2888/// %x.curr.res = phi i32 [ %x.curr, %loop ] <...>
2889/// %x.next.res = phi i32 [ %x.next, %loop ] <...>
2890/// <...>
2891/// \endcode
2892static bool detectShiftUntilBitTestIdiom(Loop *CurLoop, Value *&BaseX,
2893 Value *&BitMask, Value *&BitPos,
2894 Value *&CurrX, Instruction *&NextX) {
2895 LLVM_DEBUG(dbgs() << DEBUG_TYPE
2896 " Performing shift-until-bittest idiom detection.\n");
2897
2898 // Give up if the loop has multiple blocks or multiple backedges.
2899 if (CurLoop->getNumBlocks() != 1 || CurLoop->getNumBackEdges() != 1) {
2900 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad block/backedge count.\n");
2901 return false;
2902 }
2903
2904 BasicBlock *LoopHeaderBB = CurLoop->getHeader();
2905 BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader();
2906 assert(LoopPreheaderBB && "There is always a loop preheader.");
2907
2908 using namespace PatternMatch;
2909
2910 // Step 1: Check if the loop backedge is in desirable form.
2911
2912 CmpPredicate Pred;
2913 Value *CmpLHS, *CmpRHS;
2914 BasicBlock *TrueBB, *FalseBB;
2915 if (!match(V: LoopHeaderBB->getTerminator(),
2916 P: m_Br(C: m_ICmp(Pred, L: m_Value(V&: CmpLHS), R: m_Value(V&: CmpRHS)),
2917 T: m_BasicBlock(V&: TrueBB), F: m_BasicBlock(V&: FalseBB)))) {
2918 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge structure.\n");
2919 return false;
2920 }
2921
2922 // Step 2: Check if the backedge's condition is in desirable form.
2923
2924 auto MatchVariableBitMask = [&]() {
2925 return ICmpInst::isEquality(P: Pred) && match(V: CmpRHS, P: m_Zero()) &&
2926 match(V: CmpLHS,
2927 P: m_c_And(L: m_Value(V&: CurrX),
2928 R: m_CombineAnd(
2929 Ps: m_Value(V&: BitMask),
2930 Ps: m_LoopInvariant(M: m_Shl(L: m_One(), R: m_Value(V&: BitPos)),
2931 L: CurLoop))));
2932 };
2933
2934 auto MatchDecomposableConstantBitMask = [&]() {
2935 auto Res = llvm::decomposeBitTestICmp(
2936 LHS: CmpLHS, RHS: CmpRHS, Pred, /*LookThroughTrunc=*/true,
2937 /*AllowNonZeroC=*/false, /*DecomposeAnd=*/true);
2938 if (Res && Res->Mask.isPowerOf2()) {
2939 assert(ICmpInst::isEquality(Res->Pred));
2940 Pred = Res->Pred;
2941 CurrX = Res->X;
2942 BitMask = ConstantInt::get(Ty: CurrX->getType(), V: Res->Mask);
2943 BitPos = ConstantInt::get(Ty: CurrX->getType(), V: Res->Mask.logBase2());
2944 return true;
2945 }
2946 return false;
2947 };
2948
2949 if (!MatchVariableBitMask() && !MatchDecomposableConstantBitMask()) {
2950 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge comparison.\n");
2951 return false;
2952 }
2953
2954 // Step 3: Check if the recurrence is in desirable form.
2955 auto *CurrXPN = dyn_cast<PHINode>(Val: CurrX);
2956 if (!CurrXPN || CurrXPN->getParent() != LoopHeaderBB) {
2957 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Not an expected PHI node.\n");
2958 return false;
2959 }
2960
2961 BaseX = CurrXPN->getIncomingValueForBlock(BB: LoopPreheaderBB);
2962 NextX =
2963 dyn_cast<Instruction>(Val: CurrXPN->getIncomingValueForBlock(BB: LoopHeaderBB));
2964
2965 assert(CurLoop->isLoopInvariant(BaseX) &&
2966 "Expected BaseX to be available in the preheader!");
2967
2968 if (!NextX || !match(V: NextX, P: m_Shl(L: m_Specific(V: CurrX), R: m_One()))) {
2969 // FIXME: support right-shift?
2970 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad recurrence.\n");
2971 return false;
2972 }
2973
2974 // Step 4: Check if the backedge's destinations are in desirable form.
2975
2976 assert(ICmpInst::isEquality(Pred) &&
2977 "Should only get equality predicates here.");
2978
2979 // cmp-br is commutative, so canonicalize to a single variant.
2980 if (Pred != ICmpInst::Predicate::ICMP_EQ) {
2981 Pred = ICmpInst::getInversePredicate(pred: Pred);
2982 std::swap(a&: TrueBB, b&: FalseBB);
2983 }
2984
2985 // We expect to exit loop when comparison yields false,
2986 // so when it yields true we should branch back to loop header.
2987 if (TrueBB != LoopHeaderBB) {
2988 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge flow.\n");
2989 return false;
2990 }
2991
2992 // Okay, idiom checks out.
2993 return true;
2994}
2995
2996/// Look for the following loop:
2997/// \code
2998/// entry:
2999/// <...>
3000/// %bitmask = shl i32 1, %bitpos
3001/// br label %loop
3002///
3003/// loop:
3004/// %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
3005/// %x.curr.bitmasked = and i32 %x.curr, %bitmask
3006/// %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
3007/// %x.next = shl i32 %x.curr, 1
3008/// <...>
3009/// br i1 %x.curr.isbitunset, label %loop, label %end
3010///
3011/// end:
3012/// %x.curr.res = phi i32 [ %x.curr, %loop ] <...>
3013/// %x.next.res = phi i32 [ %x.next, %loop ] <...>
3014/// <...>
3015/// \endcode
3016///
3017/// And transform it into:
3018/// \code
3019/// entry:
3020/// %bitmask = shl i32 1, %bitpos
3021/// %lowbitmask = add i32 %bitmask, -1
3022/// %mask = or i32 %lowbitmask, %bitmask
3023/// %x.masked = and i32 %x, %mask
3024/// %x.masked.numleadingzeros = call i32 @llvm.ctlz.i32(i32 %x.masked,
3025/// i1 true)
3026/// %x.masked.numactivebits = sub i32 32, %x.masked.numleadingzeros
3027/// %x.masked.leadingonepos = add i32 %x.masked.numactivebits, -1
3028/// %backedgetakencount = sub i32 %bitpos, %x.masked.leadingonepos
3029/// %tripcount = add i32 %backedgetakencount, 1
3030/// %x.curr = shl i32 %x, %backedgetakencount
3031/// %x.next = shl i32 %x, %tripcount
3032/// br label %loop
3033///
3034/// loop:
3035/// %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.next, %loop ]
3036/// %loop.iv.next = add nuw i32 %loop.iv, 1
3037/// %loop.ivcheck = icmp eq i32 %loop.iv.next, %tripcount
3038/// <...>
3039/// br i1 %loop.ivcheck, label %end, label %loop
3040///
3041/// end:
3042/// %x.curr.res = phi i32 [ %x.curr, %loop ] <...>
3043/// %x.next.res = phi i32 [ %x.next, %loop ] <...>
3044/// <...>
3045/// \endcode
3046bool LoopIdiomRecognize::recognizeShiftUntilBitTest() {
3047 bool MadeChange = false;
3048
3049 Value *X, *BitMask, *BitPos, *XCurr;
3050 Instruction *XNext;
3051 if (!detectShiftUntilBitTestIdiom(CurLoop, BaseX&: X, BitMask, BitPos, CurrX&: XCurr,
3052 NextX&: XNext)) {
3053 LLVM_DEBUG(dbgs() << DEBUG_TYPE
3054 " shift-until-bittest idiom detection failed.\n");
3055 return MadeChange;
3056 }
3057 LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-bittest idiom detected!\n");
3058
3059 // Ok, it is the idiom we were looking for, we *could* transform this loop,
3060 // but is it profitable to transform?
3061
3062 BasicBlock *LoopHeaderBB = CurLoop->getHeader();
3063 BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader();
3064 assert(LoopPreheaderBB && "There is always a loop preheader.");
3065
3066 BasicBlock *SuccessorBB = CurLoop->getExitBlock();
3067 assert(SuccessorBB && "There is only a single successor.");
3068
3069 IRBuilder<> Builder(LoopPreheaderBB->getTerminator());
3070 Builder.SetCurrentDebugLocation(cast<Instruction>(Val: XCurr)->getDebugLoc());
3071
3072 Intrinsic::ID IntrID = Intrinsic::ctlz;
3073 Type *Ty = X->getType();
3074 unsigned Bitwidth = Ty->getScalarSizeInBits();
3075
3076 TargetTransformInfo::TargetCostKind CostKind =
3077 TargetTransformInfo::TCK_SizeAndLatency;
3078
3079 // The rewrite is considered to be unprofitable iff and only iff the
3080 // intrinsic/shift we'll use are not cheap. Note that we are okay with *just*
3081 // making the loop countable, even if nothing else changes.
3082 IntrinsicCostAttributes Attrs(
3083 IntrID, Ty, {PoisonValue::get(T: Ty), /*is_zero_poison=*/Builder.getTrue()});
3084 InstructionCost Cost = TTI->getIntrinsicInstrCost(ICA: Attrs, CostKind);
3085 if (Cost > TargetTransformInfo::TCC_Basic) {
3086 LLVM_DEBUG(dbgs() << DEBUG_TYPE
3087 " Intrinsic is too costly, not beneficial\n");
3088 return MadeChange;
3089 }
3090 if (TTI->getArithmeticInstrCost(Opcode: Instruction::Shl, Ty, CostKind) >
3091 TargetTransformInfo::TCC_Basic) {
3092 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Shift is too costly, not beneficial\n");
3093 return MadeChange;
3094 }
3095
3096 // Ok, transform appears worthwhile.
3097 MadeChange = true;
3098
3099 if (!isGuaranteedNotToBeUndefOrPoison(V: BitPos)) {
3100 // BitMask may be computed from BitPos, Freeze BitPos so we can increase
3101 // it's use count.
3102 std::optional<BasicBlock::iterator> InsertPt = std::nullopt;
3103 if (auto *BitPosI = dyn_cast<Instruction>(Val: BitPos))
3104 InsertPt = BitPosI->getInsertionPointAfterDef();
3105 else
3106 InsertPt = DT->getRoot()->getFirstNonPHIOrDbgOrAlloca();
3107 if (!InsertPt)
3108 return false;
3109 FreezeInst *BitPosFrozen =
3110 new FreezeInst(BitPos, BitPos->getName() + ".fr", *InsertPt);
3111 BitPos->replaceUsesWithIf(New: BitPosFrozen, ShouldReplace: [BitPosFrozen](Use &U) {
3112 return U.getUser() != BitPosFrozen;
3113 });
3114 BitPos = BitPosFrozen;
3115 }
3116
3117 // Step 1: Compute the loop trip count.
3118
3119 Value *LowBitMask = Builder.CreateAdd(LHS: BitMask, RHS: Constant::getAllOnesValue(Ty),
3120 Name: BitPos->getName() + ".lowbitmask");
3121 Value *Mask =
3122 Builder.CreateOr(LHS: LowBitMask, RHS: BitMask, Name: BitPos->getName() + ".mask");
3123 Value *XMasked = Builder.CreateAnd(LHS: X, RHS: Mask, Name: X->getName() + ".masked");
3124 Value *XMaskedNumLeadingZeros = Builder.CreateIntrinsic(
3125 ID: IntrID, OverloadTypes: Ty, Args: {XMasked, /*is_zero_poison=*/Builder.getTrue()},
3126 /*FMFSource=*/nullptr, Name: XMasked->getName() + ".numleadingzeros");
3127 Value *XMaskedNumActiveBits = Builder.CreateSub(
3128 LHS: ConstantInt::get(Ty, V: Ty->getScalarSizeInBits()), RHS: XMaskedNumLeadingZeros,
3129 Name: XMasked->getName() + ".numactivebits", /*HasNUW=*/true,
3130 /*HasNSW=*/Bitwidth != 2);
3131 Value *XMaskedLeadingOnePos =
3132 Builder.CreateAdd(LHS: XMaskedNumActiveBits, RHS: Constant::getAllOnesValue(Ty),
3133 Name: XMasked->getName() + ".leadingonepos", /*HasNUW=*/false,
3134 /*HasNSW=*/Bitwidth > 2);
3135
3136 Value *LoopBackedgeTakenCount = Builder.CreateSub(
3137 LHS: BitPos, RHS: XMaskedLeadingOnePos, Name: CurLoop->getName() + ".backedgetakencount",
3138 /*HasNUW=*/true, /*HasNSW=*/true);
3139 // We know loop's backedge-taken count, but what's loop's trip count?
3140 // Note that while NUW is always safe, while NSW is only for bitwidths != 2.
3141 Value *LoopTripCount =
3142 Builder.CreateAdd(LHS: LoopBackedgeTakenCount, RHS: ConstantInt::get(Ty, V: 1),
3143 Name: CurLoop->getName() + ".tripcount", /*HasNUW=*/true,
3144 /*HasNSW=*/Bitwidth != 2);
3145
3146 // Step 2: Compute the recurrence's final value without a loop.
3147
3148 // NewX is always safe to compute, because `LoopBackedgeTakenCount`
3149 // will always be smaller than `bitwidth(X)`, i.e. we never get poison.
3150 Value *NewX = Builder.CreateShl(LHS: X, RHS: LoopBackedgeTakenCount);
3151 NewX->takeName(V: XCurr);
3152 if (auto *I = dyn_cast<Instruction>(Val: NewX))
3153 I->copyIRFlags(V: XNext, /*IncludeWrapFlags=*/true);
3154
3155 Value *NewXNext;
3156 // Rewriting XNext is more complicated, however, because `X << LoopTripCount`
3157 // will be poison iff `LoopTripCount == bitwidth(X)` (which will happen
3158 // iff `BitPos` is `bitwidth(x) - 1` and `X` is `1`). So unless we know
3159 // that isn't the case, we'll need to emit an alternative, safe IR.
3160 if (XNext->hasNoSignedWrap() || XNext->hasNoUnsignedWrap() ||
3161 PatternMatch::match(
3162 V: BitPos, P: PatternMatch::m_SpecificInt_ICMP(
3163 Predicate: ICmpInst::ICMP_NE, Threshold: APInt(Ty->getScalarSizeInBits(),
3164 Ty->getScalarSizeInBits() - 1))))
3165 NewXNext = Builder.CreateShl(LHS: X, RHS: LoopTripCount);
3166 else {
3167 // Otherwise, just additionally shift by one. It's the smallest solution,
3168 // alternatively, we could check that NewX is INT_MIN (or BitPos is )
3169 // and select 0 instead.
3170 NewXNext = Builder.CreateShl(LHS: NewX, RHS: ConstantInt::get(Ty, V: 1));
3171 }
3172
3173 NewXNext->takeName(V: XNext);
3174 if (auto *I = dyn_cast<Instruction>(Val: NewXNext))
3175 I->copyIRFlags(V: XNext, /*IncludeWrapFlags=*/true);
3176
3177 // Step 3: Adjust the successor basic block to receive the computed
3178 // recurrence's final value instead of the recurrence itself.
3179
3180 XCurr->replaceUsesOutsideBlock(V: NewX, BB: LoopHeaderBB);
3181 XNext->replaceUsesOutsideBlock(V: NewXNext, BB: LoopHeaderBB);
3182
3183 // Step 4: Rewrite the loop into a countable form, with canonical IV.
3184
3185 // The new canonical induction variable.
3186 Builder.SetInsertPoint(TheBB: LoopHeaderBB, IP: LoopHeaderBB->begin());
3187 auto *IV = Builder.CreatePHI(Ty, NumReservedValues: 2, Name: CurLoop->getName() + ".iv");
3188
3189 // The induction itself.
3190 // Note that while NUW is always safe, while NSW is only for bitwidths != 2.
3191 Builder.SetInsertPoint(LoopHeaderBB->getTerminator());
3192 auto *IVNext =
3193 Builder.CreateAdd(LHS: IV, RHS: ConstantInt::get(Ty, V: 1), Name: IV->getName() + ".next",
3194 /*HasNUW=*/true, /*HasNSW=*/Bitwidth != 2);
3195
3196 // The loop trip count check.
3197 auto *IVCheck = Builder.CreateICmpEQ(LHS: IVNext, RHS: LoopTripCount,
3198 Name: CurLoop->getName() + ".ivcheck");
3199 SmallVector<uint32_t> BranchWeights;
3200 const bool HasBranchWeights =
3201 !ProfcheckDisableMetadataFixes &&
3202 extractBranchWeights(I: *LoopHeaderBB->getTerminator(), Weights&: BranchWeights);
3203
3204 auto *BI = Builder.CreateCondBr(Cond: IVCheck, True: SuccessorBB, False: LoopHeaderBB);
3205 if (HasBranchWeights) {
3206 if (SuccessorBB == LoopHeaderBB->getTerminator()->getSuccessor(Idx: 1))
3207 std::swap(a&: BranchWeights[0], b&: BranchWeights[1]);
3208 // We're not changing the loop profile, so we can reuse the original loop's
3209 // profile.
3210 setBranchWeights(I&: *BI, Weights: BranchWeights,
3211 /*IsExpected=*/false);
3212 }
3213
3214 LoopHeaderBB->getTerminator()->eraseFromParent();
3215
3216 // Populate the IV PHI.
3217 IV->addIncoming(V: ConstantInt::get(Ty, V: 0), BB: LoopPreheaderBB);
3218 IV->addIncoming(V: IVNext, BB: LoopHeaderBB);
3219
3220 // Step 5: Forget the "non-computable" trip-count SCEV associated with the
3221 // loop. The loop would otherwise not be deleted even if it becomes empty.
3222
3223 SE->forgetLoop(L: CurLoop);
3224
3225 // Other passes will take care of actually deleting the loop if possible.
3226
3227 LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-bittest idiom optimized!\n");
3228
3229 ++NumShiftUntilBitTest;
3230 return MadeChange;
3231}
3232
3233/// Return true if the idiom is detected in the loop.
3234///
3235/// The core idiom we are trying to detect is:
3236/// \code
3237/// entry:
3238/// <...>
3239/// %start = <...>
3240/// %extraoffset = <...>
3241/// <...>
3242/// br label %for.cond
3243///
3244/// loop:
3245/// %iv = phi i8 [ %start, %entry ], [ %iv.next, %for.cond ]
3246/// %nbits = add nsw i8 %iv, %extraoffset
3247/// %val.shifted = {{l,a}shr,shl} i8 %val, %nbits
3248/// %val.shifted.iszero = icmp eq i8 %val.shifted, 0
3249/// %iv.next = add i8 %iv, 1
3250/// <...>
3251/// br i1 %val.shifted.iszero, label %end, label %loop
3252///
3253/// end:
3254/// %iv.res = phi i8 [ %iv, %loop ] <...>
3255/// %nbits.res = phi i8 [ %nbits, %loop ] <...>
3256/// %val.shifted.res = phi i8 [ %val.shifted, %loop ] <...>
3257/// %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ] <...>
3258/// %iv.next.res = phi i8 [ %iv.next, %loop ] <...>
3259/// <...>
3260/// \endcode
3261static bool detectShiftUntilZeroIdiom(Loop *CurLoop, ScalarEvolution *SE,
3262 Instruction *&ValShiftedIsZero,
3263 Intrinsic::ID &IntrinID, Instruction *&IV,
3264 Value *&Start, Value *&Val,
3265 const SCEV *&ExtraOffsetExpr,
3266 bool &InvertedCond) {
3267 LLVM_DEBUG(dbgs() << DEBUG_TYPE
3268 " Performing shift-until-zero idiom detection.\n");
3269
3270 // Give up if the loop has multiple blocks or multiple backedges.
3271 if (CurLoop->getNumBlocks() != 1 || CurLoop->getNumBackEdges() != 1) {
3272 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad block/backedge count.\n");
3273 return false;
3274 }
3275
3276 Instruction *ValShifted, *NBits, *IVNext;
3277 Value *ExtraOffset;
3278
3279 BasicBlock *LoopHeaderBB = CurLoop->getHeader();
3280 BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader();
3281 assert(LoopPreheaderBB && "There is always a loop preheader.");
3282
3283 using namespace PatternMatch;
3284
3285 // Step 1: Check if the loop backedge, condition is in desirable form.
3286
3287 CmpPredicate Pred;
3288 BasicBlock *TrueBB, *FalseBB;
3289 if (!match(V: LoopHeaderBB->getTerminator(),
3290 P: m_Br(C: m_Instruction(I&: ValShiftedIsZero), T: m_BasicBlock(V&: TrueBB),
3291 F: m_BasicBlock(V&: FalseBB))) ||
3292 !match(V: ValShiftedIsZero,
3293 P: m_ICmp(Pred, L: m_Instruction(I&: ValShifted), R: m_Zero())) ||
3294 !ICmpInst::isEquality(P: Pred)) {
3295 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge structure.\n");
3296 return false;
3297 }
3298
3299 // Step 2: Check if the comparison's operand is in desirable form.
3300 // FIXME: Val could be a one-input PHI node, which we should look past.
3301 if (!match(V: ValShifted, P: m_Shift(L: m_LoopInvariant(M: m_Value(V&: Val), L: CurLoop),
3302 R: m_Instruction(I&: NBits)))) {
3303 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad comparisons value computation.\n");
3304 return false;
3305 }
3306 IntrinID = ValShifted->getOpcode() == Instruction::Shl ? Intrinsic::cttz
3307 : Intrinsic::ctlz;
3308
3309 // Step 3: Check if the shift amount is in desirable form.
3310
3311 if (match(V: NBits, P: m_c_Add(L: m_Instruction(I&: IV),
3312 R: m_LoopInvariant(M: m_Value(V&: ExtraOffset), L: CurLoop))) &&
3313 (NBits->hasNoSignedWrap() || NBits->hasNoUnsignedWrap()))
3314 ExtraOffsetExpr = SE->getNegativeSCEV(V: SE->getSCEV(V: ExtraOffset));
3315 else if (match(V: NBits,
3316 P: m_Sub(L: m_Instruction(I&: IV),
3317 R: m_LoopInvariant(M: m_Value(V&: ExtraOffset), L: CurLoop))) &&
3318 NBits->hasNoSignedWrap())
3319 ExtraOffsetExpr = SE->getSCEV(V: ExtraOffset);
3320 else {
3321 IV = NBits;
3322 ExtraOffsetExpr = SE->getZero(Ty: NBits->getType());
3323 }
3324
3325 // Step 4: Check if the recurrence is in desirable form.
3326 auto *IVPN = dyn_cast<PHINode>(Val: IV);
3327 if (!IVPN || IVPN->getParent() != LoopHeaderBB) {
3328 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Not an expected PHI node.\n");
3329 return false;
3330 }
3331
3332 Start = IVPN->getIncomingValueForBlock(BB: LoopPreheaderBB);
3333 IVNext = dyn_cast<Instruction>(Val: IVPN->getIncomingValueForBlock(BB: LoopHeaderBB));
3334
3335 if (!IVNext || !match(V: IVNext, P: m_Add(L: m_Specific(V: IVPN), R: m_One()))) {
3336 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad recurrence.\n");
3337 return false;
3338 }
3339
3340 // Step 4: Check if the backedge's destinations are in desirable form.
3341
3342 assert(ICmpInst::isEquality(Pred) &&
3343 "Should only get equality predicates here.");
3344
3345 // cmp-br is commutative, so canonicalize to a single variant.
3346 InvertedCond = Pred != ICmpInst::Predicate::ICMP_EQ;
3347 if (InvertedCond) {
3348 Pred = ICmpInst::getInversePredicate(pred: Pred);
3349 std::swap(a&: TrueBB, b&: FalseBB);
3350 }
3351
3352 // We expect to exit loop when comparison yields true,
3353 // so when it yields false we should branch back to loop header.
3354 if (FalseBB != LoopHeaderBB) {
3355 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Bad backedge flow.\n");
3356 return false;
3357 }
3358
3359 // The new, countable, loop will certainly only run a known number of
3360 // iterations, It won't be infinite. But the old loop might be infinite
3361 // under certain conditions. For logical shifts, the value will become zero
3362 // after at most bitwidth(%Val) loop iterations. However, for arithmetic
3363 // right-shift, iff the sign bit was set, the value will never become zero,
3364 // and the loop may never finish.
3365 if (ValShifted->getOpcode() == Instruction::AShr &&
3366 !isMustProgress(L: CurLoop) && !SE->isKnownNonNegative(S: SE->getSCEV(V: Val))) {
3367 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Can not prove the loop is finite.\n");
3368 return false;
3369 }
3370
3371 // Okay, idiom checks out.
3372 return true;
3373}
3374
3375/// Look for the following loop:
3376/// \code
3377/// entry:
3378/// <...>
3379/// %start = <...>
3380/// %extraoffset = <...>
3381/// <...>
3382/// br label %loop
3383///
3384/// loop:
3385/// %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
3386/// %nbits = add nsw i8 %iv, %extraoffset
3387/// %val.shifted = {{l,a}shr,shl} i8 %val, %nbits
3388/// %val.shifted.iszero = icmp eq i8 %val.shifted, 0
3389/// %iv.next = add i8 %iv, 1
3390/// <...>
3391/// br i1 %val.shifted.iszero, label %end, label %loop
3392///
3393/// end:
3394/// %iv.res = phi i8 [ %iv, %loop ] <...>
3395/// %nbits.res = phi i8 [ %nbits, %loop ] <...>
3396/// %val.shifted.res = phi i8 [ %val.shifted, %loop ] <...>
3397/// %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ] <...>
3398/// %iv.next.res = phi i8 [ %iv.next, %loop ] <...>
3399/// <...>
3400/// \endcode
3401///
3402/// And transform it into:
3403/// \code
3404/// entry:
3405/// <...>
3406/// %start = <...>
3407/// %extraoffset = <...>
3408/// <...>
3409/// %val.numleadingzeros = call i8 @llvm.ct{l,t}z.i8(i8 %val, i1 0)
3410/// %val.numactivebits = sub i8 8, %val.numleadingzeros
3411/// %extraoffset.neg = sub i8 0, %extraoffset
3412/// %tmp = add i8 %val.numactivebits, %extraoffset.neg
3413/// %iv.final = call i8 @llvm.smax.i8(i8 %tmp, i8 %start)
3414/// %loop.tripcount = sub i8 %iv.final, %start
3415/// br label %loop
3416///
3417/// loop:
3418/// %loop.iv = phi i8 [ 0, %entry ], [ %loop.iv.next, %loop ]
3419/// %loop.iv.next = add i8 %loop.iv, 1
3420/// %loop.ivcheck = icmp eq i8 %loop.iv.next, %loop.tripcount
3421/// %iv = add i8 %loop.iv, %start
3422/// <...>
3423/// br i1 %loop.ivcheck, label %end, label %loop
3424///
3425/// end:
3426/// %iv.res = phi i8 [ %iv.final, %loop ] <...>
3427/// <...>
3428/// \endcode
3429bool LoopIdiomRecognize::recognizeShiftUntilZero() {
3430 bool MadeChange = false;
3431
3432 Instruction *ValShiftedIsZero;
3433 Intrinsic::ID IntrID;
3434 Instruction *IV;
3435 Value *Start, *Val;
3436 const SCEV *ExtraOffsetExpr;
3437 bool InvertedCond;
3438 if (!detectShiftUntilZeroIdiom(CurLoop, SE, ValShiftedIsZero, IntrinID&: IntrID, IV,
3439 Start, Val, ExtraOffsetExpr, InvertedCond)) {
3440 LLVM_DEBUG(dbgs() << DEBUG_TYPE
3441 " shift-until-zero idiom detection failed.\n");
3442 return MadeChange;
3443 }
3444 LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-zero idiom detected!\n");
3445
3446 // Ok, it is the idiom we were looking for, we *could* transform this loop,
3447 // but is it profitable to transform?
3448
3449 BasicBlock *LoopHeaderBB = CurLoop->getHeader();
3450 BasicBlock *LoopPreheaderBB = CurLoop->getLoopPreheader();
3451 assert(LoopPreheaderBB && "There is always a loop preheader.");
3452
3453 BasicBlock *SuccessorBB = CurLoop->getExitBlock();
3454 assert(SuccessorBB && "There is only a single successor.");
3455
3456 IRBuilder<> Builder(LoopPreheaderBB->getTerminator());
3457 Builder.SetCurrentDebugLocation(IV->getDebugLoc());
3458
3459 Type *Ty = Val->getType();
3460 unsigned Bitwidth = Ty->getScalarSizeInBits();
3461
3462 TargetTransformInfo::TargetCostKind CostKind =
3463 TargetTransformInfo::TCK_SizeAndLatency;
3464
3465 // The rewrite is considered to be unprofitable iff and only iff the
3466 // intrinsic we'll use are not cheap. Note that we are okay with *just*
3467 // making the loop countable, even if nothing else changes.
3468 IntrinsicCostAttributes Attrs(
3469 IntrID, Ty, {PoisonValue::get(T: Ty), /*is_zero_poison=*/Builder.getFalse()});
3470 InstructionCost Cost = TTI->getIntrinsicInstrCost(ICA: Attrs, CostKind);
3471 if (Cost > TargetTransformInfo::TCC_Basic) {
3472 LLVM_DEBUG(dbgs() << DEBUG_TYPE
3473 " Intrinsic is too costly, not beneficial\n");
3474 return MadeChange;
3475 }
3476
3477 // Ok, transform appears worthwhile.
3478 MadeChange = true;
3479
3480 bool OffsetIsZero = ExtraOffsetExpr->isZero();
3481
3482 // Step 1: Compute the loop's final IV value / trip count.
3483
3484 Value *ValNumLeadingZeros = Builder.CreateIntrinsic(
3485 ID: IntrID, OverloadTypes: Ty, Args: {Val, /*is_zero_poison=*/Builder.getFalse()},
3486 /*FMFSource=*/nullptr, Name: Val->getName() + ".numleadingzeros");
3487 Value *ValNumActiveBits = Builder.CreateSub(
3488 LHS: ConstantInt::get(Ty, V: Ty->getScalarSizeInBits()), RHS: ValNumLeadingZeros,
3489 Name: Val->getName() + ".numactivebits", /*HasNUW=*/true,
3490 /*HasNSW=*/Bitwidth != 2);
3491
3492 SCEVExpander Expander(*SE, "loop-idiom");
3493 Expander.setInsertPoint(&*Builder.GetInsertPoint());
3494 Value *ExtraOffset = Expander.expandCodeFor(SH: ExtraOffsetExpr);
3495
3496 Value *ValNumActiveBitsOffset = Builder.CreateAdd(
3497 LHS: ValNumActiveBits, RHS: ExtraOffset, Name: ValNumActiveBits->getName() + ".offset",
3498 /*HasNUW=*/OffsetIsZero, /*HasNSW=*/true);
3499 Value *IVFinal = Builder.CreateIntrinsic(ID: Intrinsic::smax, OverloadTypes: {Ty},
3500 Args: {ValNumActiveBitsOffset, Start},
3501 /*FMFSource=*/nullptr, Name: "iv.final");
3502
3503 auto *LoopBackedgeTakenCount = cast<Instruction>(Val: Builder.CreateSub(
3504 LHS: IVFinal, RHS: Start, Name: CurLoop->getName() + ".backedgetakencount",
3505 /*HasNUW=*/OffsetIsZero, /*HasNSW=*/true));
3506 // FIXME: or when the offset was `add nuw`
3507
3508 // We know loop's backedge-taken count, but what's loop's trip count?
3509 Value *LoopTripCount =
3510 Builder.CreateAdd(LHS: LoopBackedgeTakenCount, RHS: ConstantInt::get(Ty, V: 1),
3511 Name: CurLoop->getName() + ".tripcount", /*HasNUW=*/true,
3512 /*HasNSW=*/Bitwidth != 2);
3513
3514 // Step 2: Adjust the successor basic block to receive the original
3515 // induction variable's final value instead of the orig. IV itself.
3516
3517 IV->replaceUsesOutsideBlock(V: IVFinal, BB: LoopHeaderBB);
3518
3519 // Step 3: Rewrite the loop into a countable form, with canonical IV.
3520
3521 // The new canonical induction variable.
3522 Builder.SetInsertPoint(TheBB: LoopHeaderBB, IP: LoopHeaderBB->begin());
3523 auto *CIV = Builder.CreatePHI(Ty, NumReservedValues: 2, Name: CurLoop->getName() + ".iv");
3524
3525 // The induction itself.
3526 Builder.SetInsertPoint(TheBB: LoopHeaderBB, IP: LoopHeaderBB->getFirstNonPHIIt());
3527 auto *CIVNext =
3528 Builder.CreateAdd(LHS: CIV, RHS: ConstantInt::get(Ty, V: 1), Name: CIV->getName() + ".next",
3529 /*HasNUW=*/true, /*HasNSW=*/Bitwidth != 2);
3530
3531 // The loop trip count check.
3532 auto *CIVCheck = Builder.CreateICmpEQ(LHS: CIVNext, RHS: LoopTripCount,
3533 Name: CurLoop->getName() + ".ivcheck");
3534 auto *NewIVCheck = CIVCheck;
3535 if (InvertedCond) {
3536 NewIVCheck = Builder.CreateNot(V: CIVCheck);
3537 NewIVCheck->takeName(V: ValShiftedIsZero);
3538 }
3539
3540 // The original IV, but rebased to be an offset to the CIV.
3541 auto *IVDePHId = Builder.CreateAdd(LHS: CIV, RHS: Start, Name: "", /*HasNUW=*/false,
3542 /*HasNSW=*/true); // FIXME: what about NUW?
3543 IVDePHId->takeName(V: IV);
3544
3545 // The loop terminator.
3546 Builder.SetInsertPoint(LoopHeaderBB->getTerminator());
3547 SmallVector<uint32_t> BranchWeights;
3548 const bool HasBranchWeights =
3549 !ProfcheckDisableMetadataFixes &&
3550 extractBranchWeights(I: *LoopHeaderBB->getTerminator(), Weights&: BranchWeights);
3551
3552 auto *BI = Builder.CreateCondBr(Cond: CIVCheck, True: SuccessorBB, False: LoopHeaderBB);
3553 if (HasBranchWeights) {
3554 if (InvertedCond)
3555 std::swap(a&: BranchWeights[0], b&: BranchWeights[1]);
3556 // We're not changing the loop profile, so we can reuse the original loop's
3557 // profile.
3558 setBranchWeights(I&: *BI, Weights: BranchWeights, /*IsExpected=*/false);
3559 }
3560 LoopHeaderBB->getTerminator()->eraseFromParent();
3561
3562 // Populate the IV PHI.
3563 CIV->addIncoming(V: ConstantInt::get(Ty, V: 0), BB: LoopPreheaderBB);
3564 CIV->addIncoming(V: CIVNext, BB: LoopHeaderBB);
3565
3566 // Step 4: Forget the "non-computable" trip-count SCEV associated with the
3567 // loop. The loop would otherwise not be deleted even if it becomes empty.
3568
3569 SE->forgetLoop(L: CurLoop);
3570
3571 // Step 5: Try to cleanup the loop's body somewhat.
3572 IV->replaceAllUsesWith(V: IVDePHId);
3573 IV->eraseFromParent();
3574
3575 ValShiftedIsZero->replaceAllUsesWith(V: NewIVCheck);
3576 ValShiftedIsZero->eraseFromParent();
3577
3578 // Other passes will take care of actually deleting the loop if possible.
3579
3580 LLVM_DEBUG(dbgs() << DEBUG_TYPE " shift-until-zero idiom optimized!\n");
3581
3582 ++NumShiftUntilZero;
3583 return MadeChange;
3584}
3585