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