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