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