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