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