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