Bug Summary

File:lib/Transforms/Scalar/LoopIdiomRecognize.cpp
Warning:line 1503, column 48
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoopIdiomRecognize.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp -faddrsig
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:
24// memcmp, memmove, strlen, etc.
25// Future floating point idioms to recognize in -ffast-math mode:
26// fpowi
27// Future integer operation idioms to recognize:
28// ctpop
29//
30// Beware that isel's default lowering for ctpop is highly inefficient for
31// i64 and larger types when i64 is legal and the value has few bits set. It
32// would be good to enhance isel to emit a loop for ctpop in this case.
33//
34// This could recognize common matrix multiplies and dot product idioms and
35// replace them with calls to BLAS (if linked in??).
36//
37//===----------------------------------------------------------------------===//
38
39#include "llvm/Transforms/Scalar/LoopIdiomRecognize.h"
40#include "llvm/ADT/APInt.h"
41#include "llvm/ADT/ArrayRef.h"
42#include "llvm/ADT/DenseMap.h"
43#include "llvm/ADT/MapVector.h"
44#include "llvm/ADT/SetVector.h"
45#include "llvm/ADT/SmallPtrSet.h"
46#include "llvm/ADT/SmallVector.h"
47#include "llvm/ADT/Statistic.h"
48#include "llvm/ADT/StringRef.h"
49#include "llvm/Analysis/AliasAnalysis.h"
50#include "llvm/Analysis/LoopAccessAnalysis.h"
51#include "llvm/Analysis/LoopInfo.h"
52#include "llvm/Analysis/LoopPass.h"
53#include "llvm/Analysis/MemoryLocation.h"
54#include "llvm/Analysis/OptimizationRemarkEmitter.h"
55#include "llvm/Analysis/ScalarEvolution.h"
56#include "llvm/Analysis/ScalarEvolutionExpander.h"
57#include "llvm/Analysis/ScalarEvolutionExpressions.h"
58#include "llvm/Analysis/TargetLibraryInfo.h"
59#include "llvm/Analysis/TargetTransformInfo.h"
60#include "llvm/Analysis/ValueTracking.h"
61#include "llvm/IR/Attributes.h"
62#include "llvm/IR/BasicBlock.h"
63#include "llvm/IR/Constant.h"
64#include "llvm/IR/Constants.h"
65#include "llvm/IR/DataLayout.h"
66#include "llvm/IR/DebugLoc.h"
67#include "llvm/IR/DerivedTypes.h"
68#include "llvm/IR/Dominators.h"
69#include "llvm/IR/GlobalValue.h"
70#include "llvm/IR/GlobalVariable.h"
71#include "llvm/IR/IRBuilder.h"
72#include "llvm/IR/InstrTypes.h"
73#include "llvm/IR/Instruction.h"
74#include "llvm/IR/Instructions.h"
75#include "llvm/IR/IntrinsicInst.h"
76#include "llvm/IR/Intrinsics.h"
77#include "llvm/IR/LLVMContext.h"
78#include "llvm/IR/Module.h"
79#include "llvm/IR/PassManager.h"
80#include "llvm/IR/Type.h"
81#include "llvm/IR/User.h"
82#include "llvm/IR/Value.h"
83#include "llvm/IR/ValueHandle.h"
84#include "llvm/Pass.h"
85#include "llvm/Support/Casting.h"
86#include "llvm/Support/CommandLine.h"
87#include "llvm/Support/Debug.h"
88#include "llvm/Support/raw_ostream.h"
89#include "llvm/Transforms/Scalar.h"
90#include "llvm/Transforms/Utils/BuildLibCalls.h"
91#include "llvm/Transforms/Utils/Local.h"
92#include "llvm/Transforms/Utils/LoopUtils.h"
93#include <algorithm>
94#include <cassert>
95#include <cstdint>
96#include <utility>
97#include <vector>
98
99using namespace llvm;
100
101#define DEBUG_TYPE"loop-idiom" "loop-idiom"
102
103STATISTIC(NumMemSet, "Number of memset's formed from loop stores")static llvm::Statistic NumMemSet = {"loop-idiom", "NumMemSet"
, "Number of memset's formed from loop stores", {0}, {false}}
;
104STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores")static llvm::Statistic NumMemCpy = {"loop-idiom", "NumMemCpy"
, "Number of memcpy's formed from loop load+stores", {0}, {false
}}
;
105
106static cl::opt<bool> UseLIRCodeSizeHeurs(
107 "use-lir-code-size-heurs",
108 cl::desc("Use loop idiom recognition code size heuristics when compiling"
109 "with -Os/-Oz"),
110 cl::init(true), cl::Hidden);
111
112namespace {
113
114class LoopIdiomRecognize {
115 Loop *CurLoop = nullptr;
116 AliasAnalysis *AA;
117 DominatorTree *DT;
118 LoopInfo *LI;
119 ScalarEvolution *SE;
120 TargetLibraryInfo *TLI;
121 const TargetTransformInfo *TTI;
122 const DataLayout *DL;
123 OptimizationRemarkEmitter &ORE;
124 bool ApplyCodeSizeHeuristics;
125
126public:
127 explicit LoopIdiomRecognize(AliasAnalysis *AA, DominatorTree *DT,
128 LoopInfo *LI, ScalarEvolution *SE,
129 TargetLibraryInfo *TLI,
130 const TargetTransformInfo *TTI,
131 const DataLayout *DL,
132 OptimizationRemarkEmitter &ORE)
133 : AA(AA), DT(DT), LI(LI), SE(SE), TLI(TLI), TTI(TTI), DL(DL), ORE(ORE) {}
134
135 bool runOnLoop(Loop *L);
136
137private:
138 using StoreList = SmallVector<StoreInst *, 8>;
139 using StoreListMap = MapVector<Value *, StoreList>;
140
141 StoreListMap StoreRefsForMemset;
142 StoreListMap StoreRefsForMemsetPattern;
143 StoreList StoreRefsForMemcpy;
144 bool HasMemset;
145 bool HasMemsetPattern;
146 bool HasMemcpy;
147
148 /// Return code for isLegalStore()
149 enum LegalStoreKind {
150 None = 0,
151 Memset,
152 MemsetPattern,
153 Memcpy,
154 UnorderedAtomicMemcpy,
155 DontUse // Dummy retval never to be used. Allows catching errors in retval
156 // handling.
157 };
158
159 /// \name Countable Loop Idiom Handling
160 /// @{
161
162 bool runOnCountableLoop();
163 bool runOnLoopBlock(BasicBlock *BB, const SCEV *BECount,
164 SmallVectorImpl<BasicBlock *> &ExitBlocks);
165
166 void collectStores(BasicBlock *BB);
167 LegalStoreKind isLegalStore(StoreInst *SI);
168 enum class ForMemset { No, Yes };
169 bool processLoopStores(SmallVectorImpl<StoreInst *> &SL, const SCEV *BECount,
170 ForMemset For);
171 bool processLoopMemSet(MemSetInst *MSI, const SCEV *BECount);
172
173 bool processLoopStridedStore(Value *DestPtr, unsigned StoreSize,
174 unsigned StoreAlignment, Value *StoredVal,
175 Instruction *TheStore,
176 SmallPtrSetImpl<Instruction *> &Stores,
177 const SCEVAddRecExpr *Ev, const SCEV *BECount,
178 bool NegStride, bool IsLoopMemset = false);
179 bool processLoopStoreOfLoopLoad(StoreInst *SI, const SCEV *BECount);
180 bool avoidLIRForMultiBlockLoop(bool IsMemset = false,
181 bool IsLoopMemset = false);
182
183 /// @}
184 /// \name Noncountable Loop Idiom Handling
185 /// @{
186
187 bool runOnNoncountableLoop();
188
189 bool recognizePopcount();
190 void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst,
191 PHINode *CntPhi, Value *Var);
192 bool recognizeAndInsertFFS(); /// Find First Set: ctlz or cttz
193 void transformLoopToCountable(Intrinsic::ID IntrinID, BasicBlock *PreCondBB,
194 Instruction *CntInst, PHINode *CntPhi,
195 Value *Var, Instruction *DefX,
196 const DebugLoc &DL, bool ZeroCheck,
197 bool IsCntPhiUsedOutsideLoop);
198
199 /// @}
200};
201
202class LoopIdiomRecognizeLegacyPass : public LoopPass {
203public:
204 static char ID;
205
206 explicit LoopIdiomRecognizeLegacyPass() : LoopPass(ID) {
207 initializeLoopIdiomRecognizeLegacyPassPass(
208 *PassRegistry::getPassRegistry());
209 }
210
211 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
212 if (skipLoop(L))
213 return false;
214
215 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
216 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
217 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
218 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
219 TargetLibraryInfo *TLI =
220 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
221 const TargetTransformInfo *TTI =
222 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
223 *L->getHeader()->getParent());
224 const DataLayout *DL = &L->getHeader()->getModule()->getDataLayout();
225
226 // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
227 // pass. Function analyses need to be preserved across loop transformations
228 // but ORE cannot be preserved (see comment before the pass definition).
229 OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
230
231 LoopIdiomRecognize LIR(AA, DT, LI, SE, TLI, TTI, DL, ORE);
232 return LIR.runOnLoop(L);
233 }
234
235 /// This transformation requires natural loop information & requires that
236 /// loop preheaders be inserted into the CFG.
237 void getAnalysisUsage(AnalysisUsage &AU) const override {
238 AU.addRequired<TargetLibraryInfoWrapperPass>();
239 AU.addRequired<TargetTransformInfoWrapperPass>();
240 getLoopAnalysisUsage(AU);
241 }
242};
243
244} // end anonymous namespace
245
246char LoopIdiomRecognizeLegacyPass::ID = 0;
247
248PreservedAnalyses LoopIdiomRecognizePass::run(Loop &L, LoopAnalysisManager &AM,
249 LoopStandardAnalysisResults &AR,
250 LPMUpdater &) {
251 const auto *DL = &L.getHeader()->getModule()->getDataLayout();
252
253 const auto &FAM =
254 AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
255 Function *F = L.getHeader()->getParent();
256
257 auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
258 // FIXME: This should probably be optional rather than required.
259 if (!ORE)
1
Taking false branch
260 report_fatal_error(
261 "LoopIdiomRecognizePass: OptimizationRemarkEmitterAnalysis not cached "
262 "at a higher level");
263
264 LoopIdiomRecognize LIR(&AR.AA, &AR.DT, &AR.LI, &AR.SE, &AR.TLI, &AR.TTI, DL,
265 *ORE);
266 if (!LIR.runOnLoop(&L))
2
Calling 'LoopIdiomRecognize::runOnLoop'
267 return PreservedAnalyses::all();
268
269 return getLoopPassPreservedAnalyses();
270}
271
272INITIALIZE_PASS_BEGIN(LoopIdiomRecognizeLegacyPass, "loop-idiom",static void *initializeLoopIdiomRecognizeLegacyPassPassOnce(PassRegistry
&Registry) {
273 "Recognize loop idioms", false, false)static void *initializeLoopIdiomRecognizeLegacyPassPassOnce(PassRegistry
&Registry) {
274INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
275INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
276INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
277INITIALIZE_PASS_END(LoopIdiomRecognizeLegacyPass, "loop-idiom",PassInfo *PI = new PassInfo( "Recognize loop idioms", "loop-idiom"
, &LoopIdiomRecognizeLegacyPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<LoopIdiomRecognizeLegacyPass>), false,
false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeLoopIdiomRecognizeLegacyPassPassFlag
; void llvm::initializeLoopIdiomRecognizeLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeLoopIdiomRecognizeLegacyPassPassFlag
, initializeLoopIdiomRecognizeLegacyPassPassOnce, std::ref(Registry
)); }
278 "Recognize loop idioms", false, false)PassInfo *PI = new PassInfo( "Recognize loop idioms", "loop-idiom"
, &LoopIdiomRecognizeLegacyPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<LoopIdiomRecognizeLegacyPass>), false,
false); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeLoopIdiomRecognizeLegacyPassPassFlag
; void llvm::initializeLoopIdiomRecognizeLegacyPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeLoopIdiomRecognizeLegacyPassPassFlag
, initializeLoopIdiomRecognizeLegacyPassPassOnce, std::ref(Registry
)); }
279
280Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognizeLegacyPass(); }
281
282static void deleteDeadInstruction(Instruction *I) {
283 I->replaceAllUsesWith(UndefValue::get(I->getType()));
284 I->eraseFromParent();
285}
286
287//===----------------------------------------------------------------------===//
288//
289// Implementation of LoopIdiomRecognize
290//
291//===----------------------------------------------------------------------===//
292
293bool LoopIdiomRecognize::runOnLoop(Loop *L) {
294 CurLoop = L;
295 // If the loop could not be converted to canonical form, it must have an
296 // indirectbr in it, just give up.
297 if (!L->getLoopPreheader())
3
Assuming the condition is false
4
Taking false branch
298 return false;
299
300 // Disable loop idiom recognition if the function's name is a common idiom.
301 StringRef Name = L->getHeader()->getParent()->getName();
302 if (Name == "memset" || Name == "memcpy")
5
Assuming the condition is false
6
Assuming the condition is false
7
Taking false branch
303 return false;
304
305 // Determine if code size heuristics need to be applied.
306 ApplyCodeSizeHeuristics =
307 L->getHeader()->getParent()->hasOptSize() && UseLIRCodeSizeHeurs;
8
Assuming the condition is false
308
309 HasMemset = TLI->has(LibFunc_memset);
310 HasMemsetPattern = TLI->has(LibFunc_memset_pattern16);
311 HasMemcpy = TLI->has(LibFunc_memcpy);
312
313 if (HasMemset || HasMemsetPattern || HasMemcpy)
9
Taking false branch
314 if (SE->hasLoopInvariantBackedgeTakenCount(L))
315 return runOnCountableLoop();
316
317 return runOnNoncountableLoop();
10
Calling 'LoopIdiomRecognize::runOnNoncountableLoop'
318}
319
320bool LoopIdiomRecognize::runOnCountableLoop() {
321 const SCEV *BECount = SE->getBackedgeTakenCount(CurLoop);
322 assert(!isa<SCEVCouldNotCompute>(BECount) &&((!isa<SCEVCouldNotCompute>(BECount) && "runOnCountableLoop() called on a loop without a predictable"
"backedge-taken count") ? static_cast<void> (0) : __assert_fail
("!isa<SCEVCouldNotCompute>(BECount) && \"runOnCountableLoop() called on a loop without a predictable\" \"backedge-taken count\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 324, __PRETTY_FUNCTION__))
323 "runOnCountableLoop() called on a loop without a predictable"((!isa<SCEVCouldNotCompute>(BECount) && "runOnCountableLoop() called on a loop without a predictable"
"backedge-taken count") ? static_cast<void> (0) : __assert_fail
("!isa<SCEVCouldNotCompute>(BECount) && \"runOnCountableLoop() called on a loop without a predictable\" \"backedge-taken count\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 324, __PRETTY_FUNCTION__))
324 "backedge-taken count")((!isa<SCEVCouldNotCompute>(BECount) && "runOnCountableLoop() called on a loop without a predictable"
"backedge-taken count") ? static_cast<void> (0) : __assert_fail
("!isa<SCEVCouldNotCompute>(BECount) && \"runOnCountableLoop() called on a loop without a predictable\" \"backedge-taken count\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 324, __PRETTY_FUNCTION__))
;
325
326 // If this loop executes exactly one time, then it should be peeled, not
327 // optimized by this pass.
328 if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
329 if (BECst->getAPInt() == 0)
330 return false;
331
332 SmallVector<BasicBlock *, 8> ExitBlocks;
333 CurLoop->getUniqueExitBlocks(ExitBlocks);
334
335 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << "loop-idiom" " Scanning: F["
<< CurLoop->getHeader()->getParent()->getName
() << "] Countable Loop %" << CurLoop->getHeader
()->getName() << "\n"; } } while (false)
336 << CurLoop->getHeader()->getParent()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << "loop-idiom" " Scanning: F["
<< CurLoop->getHeader()->getParent()->getName
() << "] Countable Loop %" << CurLoop->getHeader
()->getName() << "\n"; } } while (false)
337 << "] Countable Loop %" << CurLoop->getHeader()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << "loop-idiom" " Scanning: F["
<< CurLoop->getHeader()->getParent()->getName
() << "] Countable Loop %" << CurLoop->getHeader
()->getName() << "\n"; } } while (false)
338 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << "loop-idiom" " Scanning: F["
<< CurLoop->getHeader()->getParent()->getName
() << "] Countable Loop %" << CurLoop->getHeader
()->getName() << "\n"; } } while (false)
;
339
340 bool MadeChange = false;
341
342 // The following transforms hoist stores/memsets into the loop pre-header.
343 // Give up if the loop has instructions may throw.
344 SimpleLoopSafetyInfo SafetyInfo;
345 SafetyInfo.computeLoopSafetyInfo(CurLoop);
346 if (SafetyInfo.anyBlockMayThrow())
347 return MadeChange;
348
349 // Scan all the blocks in the loop that are not in subloops.
350 for (auto *BB : CurLoop->getBlocks()) {
351 // Ignore blocks in subloops.
352 if (LI->getLoopFor(BB) != CurLoop)
353 continue;
354
355 MadeChange |= runOnLoopBlock(BB, BECount, ExitBlocks);
356 }
357 return MadeChange;
358}
359
360static APInt getStoreStride(const SCEVAddRecExpr *StoreEv) {
361 const SCEVConstant *ConstStride = cast<SCEVConstant>(StoreEv->getOperand(1));
362 return ConstStride->getAPInt();
363}
364
365/// getMemSetPatternValue - If a strided store of the specified value is safe to
366/// turn into a memset_pattern16, return a ConstantArray of 16 bytes that should
367/// be passed in. Otherwise, return null.
368///
369/// Note that we don't ever attempt to use memset_pattern8 or 4, because these
370/// just replicate their input array and then pass on to memset_pattern16.
371static Constant *getMemSetPatternValue(Value *V, const DataLayout *DL) {
372 // FIXME: This could check for UndefValue because it can be merged into any
373 // other valid pattern.
374
375 // If the value isn't a constant, we can't promote it to being in a constant
376 // array. We could theoretically do a store to an alloca or something, but
377 // that doesn't seem worthwhile.
378 Constant *C = dyn_cast<Constant>(V);
379 if (!C)
380 return nullptr;
381
382 // Only handle simple values that are a power of two bytes in size.
383 uint64_t Size = DL->getTypeSizeInBits(V->getType());
384 if (Size == 0 || (Size & 7) || (Size & (Size - 1)))
385 return nullptr;
386
387 // Don't care enough about darwin/ppc to implement this.
388 if (DL->isBigEndian())
389 return nullptr;
390
391 // Convert to size in bytes.
392 Size /= 8;
393
394 // TODO: If CI is larger than 16-bytes, we can try slicing it in half to see
395 // if the top and bottom are the same (e.g. for vectors and large integers).
396 if (Size > 16)
397 return nullptr;
398
399 // If the constant is exactly 16 bytes, just use it.
400 if (Size == 16)
401 return C;
402
403 // Otherwise, we'll use an array of the constants.
404 unsigned ArraySize = 16 / Size;
405 ArrayType *AT = ArrayType::get(V->getType(), ArraySize);
406 return ConstantArray::get(AT, std::vector<Constant *>(ArraySize, C));
407}
408
409LoopIdiomRecognize::LegalStoreKind
410LoopIdiomRecognize::isLegalStore(StoreInst *SI) {
411 // Don't touch volatile stores.
412 if (SI->isVolatile())
413 return LegalStoreKind::None;
414 // We only want simple or unordered-atomic stores.
415 if (!SI->isUnordered())
416 return LegalStoreKind::None;
417
418 // Don't convert stores of non-integral pointer types to memsets (which stores
419 // integers).
420 if (DL->isNonIntegralPointerType(SI->getValueOperand()->getType()))
421 return LegalStoreKind::None;
422
423 // Avoid merging nontemporal stores.
424 if (SI->getMetadata(LLVMContext::MD_nontemporal))
425 return LegalStoreKind::None;
426
427 Value *StoredVal = SI->getValueOperand();
428 Value *StorePtr = SI->getPointerOperand();
429
430 // Reject stores that are so large that they overflow an unsigned.
431 uint64_t SizeInBits = DL->getTypeSizeInBits(StoredVal->getType());
432 if ((SizeInBits & 7) || (SizeInBits >> 32) != 0)
433 return LegalStoreKind::None;
434
435 // See if the pointer expression is an AddRec like {base,+,1} on the current
436 // loop, which indicates a strided store. If we have something else, it's a
437 // random store we can't handle.
438 const SCEVAddRecExpr *StoreEv =
439 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
440 if (!StoreEv || StoreEv->getLoop() != CurLoop || !StoreEv->isAffine())
441 return LegalStoreKind::None;
442
443 // Check to see if we have a constant stride.
444 if (!isa<SCEVConstant>(StoreEv->getOperand(1)))
445 return LegalStoreKind::None;
446
447 // See if the store can be turned into a memset.
448
449 // If the stored value is a byte-wise value (like i32 -1), then it may be
450 // turned into a memset of i8 -1, assuming that all the consecutive bytes
451 // are stored. A store of i32 0x01020304 can never be turned into a memset,
452 // but it can be turned into memset_pattern if the target supports it.
453 Value *SplatValue = isBytewiseValue(StoredVal);
454 Constant *PatternValue = nullptr;
455
456 // Note: memset and memset_pattern on unordered-atomic is yet not supported
457 bool UnorderedAtomic = SI->isUnordered() && !SI->isSimple();
458
459 // If we're allowed to form a memset, and the stored value would be
460 // acceptable for memset, use it.
461 if (!UnorderedAtomic && HasMemset && SplatValue &&
462 // Verify that the stored value is loop invariant. If not, we can't
463 // promote the memset.
464 CurLoop->isLoopInvariant(SplatValue)) {
465 // It looks like we can use SplatValue.
466 return LegalStoreKind::Memset;
467 } else if (!UnorderedAtomic && HasMemsetPattern &&
468 // Don't create memset_pattern16s with address spaces.
469 StorePtr->getType()->getPointerAddressSpace() == 0 &&
470 (PatternValue = getMemSetPatternValue(StoredVal, DL))) {
471 // It looks like we can use PatternValue!
472 return LegalStoreKind::MemsetPattern;
473 }
474
475 // Otherwise, see if the store can be turned into a memcpy.
476 if (HasMemcpy) {
477 // Check to see if the stride matches the size of the store. If so, then we
478 // know that every byte is touched in the loop.
479 APInt Stride = getStoreStride(StoreEv);
480 unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType());
481 if (StoreSize != Stride && StoreSize != -Stride)
482 return LegalStoreKind::None;
483
484 // The store must be feeding a non-volatile load.
485 LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand());
486
487 // Only allow non-volatile loads
488 if (!LI || LI->isVolatile())
489 return LegalStoreKind::None;
490 // Only allow simple or unordered-atomic loads
491 if (!LI->isUnordered())
492 return LegalStoreKind::None;
493
494 // See if the pointer expression is an AddRec like {base,+,1} on the current
495 // loop, which indicates a strided load. If we have something else, it's a
496 // random load we can't handle.
497 const SCEVAddRecExpr *LoadEv =
498 dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LI->getPointerOperand()));
499 if (!LoadEv || LoadEv->getLoop() != CurLoop || !LoadEv->isAffine())
500 return LegalStoreKind::None;
501
502 // The store and load must share the same stride.
503 if (StoreEv->getOperand(1) != LoadEv->getOperand(1))
504 return LegalStoreKind::None;
505
506 // Success. This store can be converted into a memcpy.
507 UnorderedAtomic = UnorderedAtomic || LI->isAtomic();
508 return UnorderedAtomic ? LegalStoreKind::UnorderedAtomicMemcpy
509 : LegalStoreKind::Memcpy;
510 }
511 // This store can't be transformed into a memset/memcpy.
512 return LegalStoreKind::None;
513}
514
515void LoopIdiomRecognize::collectStores(BasicBlock *BB) {
516 StoreRefsForMemset.clear();
517 StoreRefsForMemsetPattern.clear();
518 StoreRefsForMemcpy.clear();
519 for (Instruction &I : *BB) {
520 StoreInst *SI = dyn_cast<StoreInst>(&I);
521 if (!SI)
522 continue;
523
524 // Make sure this is a strided store with a constant stride.
525 switch (isLegalStore(SI)) {
526 case LegalStoreKind::None:
527 // Nothing to do
528 break;
529 case LegalStoreKind::Memset: {
530 // Find the base pointer.
531 Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), *DL);
532 StoreRefsForMemset[Ptr].push_back(SI);
533 } break;
534 case LegalStoreKind::MemsetPattern: {
535 // Find the base pointer.
536 Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), *DL);
537 StoreRefsForMemsetPattern[Ptr].push_back(SI);
538 } break;
539 case LegalStoreKind::Memcpy:
540 case LegalStoreKind::UnorderedAtomicMemcpy:
541 StoreRefsForMemcpy.push_back(SI);
542 break;
543 default:
544 assert(false && "unhandled return value")((false && "unhandled return value") ? static_cast<
void> (0) : __assert_fail ("false && \"unhandled return value\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 544, __PRETTY_FUNCTION__))
;
545 break;
546 }
547 }
548}
549
550/// runOnLoopBlock - Process the specified block, which lives in a counted loop
551/// with the specified backedge count. This block is known to be in the current
552/// loop and not in any subloops.
553bool LoopIdiomRecognize::runOnLoopBlock(
554 BasicBlock *BB, const SCEV *BECount,
555 SmallVectorImpl<BasicBlock *> &ExitBlocks) {
556 // We can only promote stores in this block if they are unconditionally
557 // executed in the loop. For a block to be unconditionally executed, it has
558 // to dominate all the exit blocks of the loop. Verify this now.
559 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
560 if (!DT->dominates(BB, ExitBlocks[i]))
561 return false;
562
563 bool MadeChange = false;
564 // Look for store instructions, which may be optimized to memset/memcpy.
565 collectStores(BB);
566
567 // Look for a single store or sets of stores with a common base, which can be
568 // optimized into a memset (memset_pattern). The latter most commonly happens
569 // with structs and handunrolled loops.
570 for (auto &SL : StoreRefsForMemset)
571 MadeChange |= processLoopStores(SL.second, BECount, ForMemset::Yes);
572
573 for (auto &SL : StoreRefsForMemsetPattern)
574 MadeChange |= processLoopStores(SL.second, BECount, ForMemset::No);
575
576 // Optimize the store into a memcpy, if it feeds an similarly strided load.
577 for (auto &SI : StoreRefsForMemcpy)
578 MadeChange |= processLoopStoreOfLoopLoad(SI, BECount);
579
580 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
581 Instruction *Inst = &*I++;
582 // Look for memset instructions, which may be optimized to a larger memset.
583 if (MemSetInst *MSI = dyn_cast<MemSetInst>(Inst)) {
584 WeakTrackingVH InstPtr(&*I);
585 if (!processLoopMemSet(MSI, BECount))
586 continue;
587 MadeChange = true;
588
589 // If processing the memset invalidated our iterator, start over from the
590 // top of the block.
591 if (!InstPtr)
592 I = BB->begin();
593 continue;
594 }
595 }
596
597 return MadeChange;
598}
599
600/// See if this store(s) can be promoted to a memset.
601bool LoopIdiomRecognize::processLoopStores(SmallVectorImpl<StoreInst *> &SL,
602 const SCEV *BECount, ForMemset For) {
603 // Try to find consecutive stores that can be transformed into memsets.
604 SetVector<StoreInst *> Heads, Tails;
605 SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain;
606
607 // Do a quadratic search on all of the given stores and find
608 // all of the pairs of stores that follow each other.
609 SmallVector<unsigned, 16> IndexQueue;
610 for (unsigned i = 0, e = SL.size(); i < e; ++i) {
611 assert(SL[i]->isSimple() && "Expected only non-volatile stores.")((SL[i]->isSimple() && "Expected only non-volatile stores."
) ? static_cast<void> (0) : __assert_fail ("SL[i]->isSimple() && \"Expected only non-volatile stores.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 611, __PRETTY_FUNCTION__))
;
612
613 Value *FirstStoredVal = SL[i]->getValueOperand();
614 Value *FirstStorePtr = SL[i]->getPointerOperand();
615 const SCEVAddRecExpr *FirstStoreEv =
616 cast<SCEVAddRecExpr>(SE->getSCEV(FirstStorePtr));
617 APInt FirstStride = getStoreStride(FirstStoreEv);
618 unsigned FirstStoreSize = DL->getTypeStoreSize(SL[i]->getValueOperand()->getType());
619
620 // See if we can optimize just this store in isolation.
621 if (FirstStride == FirstStoreSize || -FirstStride == FirstStoreSize) {
622 Heads.insert(SL[i]);
623 continue;
624 }
625
626 Value *FirstSplatValue = nullptr;
627 Constant *FirstPatternValue = nullptr;
628
629 if (For == ForMemset::Yes)
630 FirstSplatValue = isBytewiseValue(FirstStoredVal);
631 else
632 FirstPatternValue = getMemSetPatternValue(FirstStoredVal, DL);
633
634 assert((FirstSplatValue || FirstPatternValue) &&(((FirstSplatValue || FirstPatternValue) && "Expected either splat value or pattern value."
) ? static_cast<void> (0) : __assert_fail ("(FirstSplatValue || FirstPatternValue) && \"Expected either splat value or pattern value.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 635, __PRETTY_FUNCTION__))
635 "Expected either splat value or pattern value.")(((FirstSplatValue || FirstPatternValue) && "Expected either splat value or pattern value."
) ? static_cast<void> (0) : __assert_fail ("(FirstSplatValue || FirstPatternValue) && \"Expected either splat value or pattern value.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 635, __PRETTY_FUNCTION__))
;
636
637 IndexQueue.clear();
638 // If a store has multiple consecutive store candidates, search Stores
639 // array according to the sequence: from i+1 to e, then from i-1 to 0.
640 // This is because usually pairing with immediate succeeding or preceding
641 // candidate create the best chance to find memset opportunity.
642 unsigned j = 0;
643 for (j = i + 1; j < e; ++j)
644 IndexQueue.push_back(j);
645 for (j = i; j > 0; --j)
646 IndexQueue.push_back(j - 1);
647
648 for (auto &k : IndexQueue) {
649 assert(SL[k]->isSimple() && "Expected only non-volatile stores.")((SL[k]->isSimple() && "Expected only non-volatile stores."
) ? static_cast<void> (0) : __assert_fail ("SL[k]->isSimple() && \"Expected only non-volatile stores.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 649, __PRETTY_FUNCTION__))
;
650 Value *SecondStorePtr = SL[k]->getPointerOperand();
651 const SCEVAddRecExpr *SecondStoreEv =
652 cast<SCEVAddRecExpr>(SE->getSCEV(SecondStorePtr));
653 APInt SecondStride = getStoreStride(SecondStoreEv);
654
655 if (FirstStride != SecondStride)
656 continue;
657
658 Value *SecondStoredVal = SL[k]->getValueOperand();
659 Value *SecondSplatValue = nullptr;
660 Constant *SecondPatternValue = nullptr;
661
662 if (For == ForMemset::Yes)
663 SecondSplatValue = isBytewiseValue(SecondStoredVal);
664 else
665 SecondPatternValue = getMemSetPatternValue(SecondStoredVal, DL);
666
667 assert((SecondSplatValue || SecondPatternValue) &&(((SecondSplatValue || SecondPatternValue) && "Expected either splat value or pattern value."
) ? static_cast<void> (0) : __assert_fail ("(SecondSplatValue || SecondPatternValue) && \"Expected either splat value or pattern value.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 668, __PRETTY_FUNCTION__))
668 "Expected either splat value or pattern value.")(((SecondSplatValue || SecondPatternValue) && "Expected either splat value or pattern value."
) ? static_cast<void> (0) : __assert_fail ("(SecondSplatValue || SecondPatternValue) && \"Expected either splat value or pattern value.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 668, __PRETTY_FUNCTION__))
;
669
670 if (isConsecutiveAccess(SL[i], SL[k], *DL, *SE, false)) {
671 if (For == ForMemset::Yes) {
672 if (isa<UndefValue>(FirstSplatValue))
673 FirstSplatValue = SecondSplatValue;
674 if (FirstSplatValue != SecondSplatValue)
675 continue;
676 } else {
677 if (isa<UndefValue>(FirstPatternValue))
678 FirstPatternValue = SecondPatternValue;
679 if (FirstPatternValue != SecondPatternValue)
680 continue;
681 }
682 Tails.insert(SL[k]);
683 Heads.insert(SL[i]);
684 ConsecutiveChain[SL[i]] = SL[k];
685 break;
686 }
687 }
688 }
689
690 // We may run into multiple chains that merge into a single chain. We mark the
691 // stores that we transformed so that we don't visit the same store twice.
692 SmallPtrSet<Value *, 16> TransformedStores;
693 bool Changed = false;
694
695 // For stores that start but don't end a link in the chain:
696 for (SetVector<StoreInst *>::iterator it = Heads.begin(), e = Heads.end();
697 it != e; ++it) {
698 if (Tails.count(*it))
699 continue;
700
701 // We found a store instr that starts a chain. Now follow the chain and try
702 // to transform it.
703 SmallPtrSet<Instruction *, 8> AdjacentStores;
704 StoreInst *I = *it;
705
706 StoreInst *HeadStore = I;
707 unsigned StoreSize = 0;
708
709 // Collect the chain into a list.
710 while (Tails.count(I) || Heads.count(I)) {
711 if (TransformedStores.count(I))
712 break;
713 AdjacentStores.insert(I);
714
715 StoreSize += DL->getTypeStoreSize(I->getValueOperand()->getType());
716 // Move to the next value in the chain.
717 I = ConsecutiveChain[I];
718 }
719
720 Value *StoredVal = HeadStore->getValueOperand();
721 Value *StorePtr = HeadStore->getPointerOperand();
722 const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
723 APInt Stride = getStoreStride(StoreEv);
724
725 // Check to see if the stride matches the size of the stores. If so, then
726 // we know that every byte is touched in the loop.
727 if (StoreSize != Stride && StoreSize != -Stride)
728 continue;
729
730 bool NegStride = StoreSize == -Stride;
731
732 if (processLoopStridedStore(StorePtr, StoreSize, HeadStore->getAlignment(),
733 StoredVal, HeadStore, AdjacentStores, StoreEv,
734 BECount, NegStride)) {
735 TransformedStores.insert(AdjacentStores.begin(), AdjacentStores.end());
736 Changed = true;
737 }
738 }
739
740 return Changed;
741}
742
743/// processLoopMemSet - See if this memset can be promoted to a large memset.
744bool LoopIdiomRecognize::processLoopMemSet(MemSetInst *MSI,
745 const SCEV *BECount) {
746 // We can only handle non-volatile memsets with a constant size.
747 if (MSI->isVolatile() || !isa<ConstantInt>(MSI->getLength()))
748 return false;
749
750 // If we're not allowed to hack on memset, we fail.
751 if (!HasMemset)
752 return false;
753
754 Value *Pointer = MSI->getDest();
755
756 // See if the pointer expression is an AddRec like {base,+,1} on the current
757 // loop, which indicates a strided store. If we have something else, it's a
758 // random store we can't handle.
759 const SCEVAddRecExpr *Ev = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Pointer));
760 if (!Ev || Ev->getLoop() != CurLoop || !Ev->isAffine())
761 return false;
762
763 // Reject memsets that are so large that they overflow an unsigned.
764 uint64_t SizeInBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue();
765 if ((SizeInBytes >> 32) != 0)
766 return false;
767
768 // Check to see if the stride matches the size of the memset. If so, then we
769 // know that every byte is touched in the loop.
770 const SCEVConstant *ConstStride = dyn_cast<SCEVConstant>(Ev->getOperand(1));
771 if (!ConstStride)
772 return false;
773
774 APInt Stride = ConstStride->getAPInt();
775 if (SizeInBytes != Stride && SizeInBytes != -Stride)
776 return false;
777
778 // Verify that the memset value is loop invariant. If not, we can't promote
779 // the memset.
780 Value *SplatValue = MSI->getValue();
781 if (!SplatValue || !CurLoop->isLoopInvariant(SplatValue))
782 return false;
783
784 SmallPtrSet<Instruction *, 1> MSIs;
785 MSIs.insert(MSI);
786 bool NegStride = SizeInBytes == -Stride;
787 return processLoopStridedStore(Pointer, (unsigned)SizeInBytes,
788 MSI->getDestAlignment(), SplatValue, MSI, MSIs,
789 Ev, BECount, NegStride, /*IsLoopMemset=*/true);
790}
791
792/// mayLoopAccessLocation - Return true if the specified loop might access the
793/// specified pointer location, which is a loop-strided access. The 'Access'
794/// argument specifies what the verboten forms of access are (read or write).
795static bool
796mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
797 const SCEV *BECount, unsigned StoreSize,
798 AliasAnalysis &AA,
799 SmallPtrSetImpl<Instruction *> &IgnoredStores) {
800 // Get the location that may be stored across the loop. Since the access is
801 // strided positively through memory, we say that the modified location starts
802 // at the pointer and has infinite size.
803 LocationSize AccessSize = LocationSize::unknown();
804
805 // If the loop iterates a fixed number of times, we can refine the access size
806 // to be exactly the size of the memset, which is (BECount+1)*StoreSize
807 if (const SCEVConstant *BECst = dyn_cast<SCEVConstant>(BECount))
808 AccessSize = LocationSize::precise((BECst->getValue()->getZExtValue() + 1) *
809 StoreSize);
810
811 // TODO: For this to be really effective, we have to dive into the pointer
812 // operand in the store. Store to &A[i] of 100 will always return may alias
813 // with store of &A[100], we need to StoreLoc to be "A" with size of 100,
814 // which will then no-alias a store to &A[100].
815 MemoryLocation StoreLoc(Ptr, AccessSize);
816
817 for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E;
818 ++BI)
819 for (Instruction &I : **BI)
820 if (IgnoredStores.count(&I) == 0 &&
821 isModOrRefSet(
822 intersectModRef(AA.getModRefInfo(&I, StoreLoc), Access)))
823 return true;
824
825 return false;
826}
827
828// If we have a negative stride, Start refers to the end of the memory location
829// we're trying to memset. Therefore, we need to recompute the base pointer,
830// which is just Start - BECount*Size.
831static const SCEV *getStartForNegStride(const SCEV *Start, const SCEV *BECount,
832 Type *IntPtr, unsigned StoreSize,
833 ScalarEvolution *SE) {
834 const SCEV *Index = SE->getTruncateOrZeroExtend(BECount, IntPtr);
835 if (StoreSize != 1)
836 Index = SE->getMulExpr(Index, SE->getConstant(IntPtr, StoreSize),
837 SCEV::FlagNUW);
838 return SE->getMinusSCEV(Start, Index);
839}
840
841/// Compute the number of bytes as a SCEV from the backedge taken count.
842///
843/// This also maps the SCEV into the provided type and tries to handle the
844/// computation in a way that will fold cleanly.
845static const SCEV *getNumBytes(const SCEV *BECount, Type *IntPtr,
846 unsigned StoreSize, Loop *CurLoop,
847 const DataLayout *DL, ScalarEvolution *SE) {
848 const SCEV *NumBytesS;
849 // The # stored bytes is (BECount+1)*Size. Expand the trip count out to
850 // pointer size if it isn't already.
851 //
852 // If we're going to need to zero extend the BE count, check if we can add
853 // one to it prior to zero extending without overflow. Provided this is safe,
854 // it allows better simplification of the +1.
855 if (DL->getTypeSizeInBits(BECount->getType()) <
856 DL->getTypeSizeInBits(IntPtr) &&
857 SE->isLoopEntryGuardedByCond(
858 CurLoop, ICmpInst::ICMP_NE, BECount,
859 SE->getNegativeSCEV(SE->getOne(BECount->getType())))) {
860 NumBytesS = SE->getZeroExtendExpr(
861 SE->getAddExpr(BECount, SE->getOne(BECount->getType()), SCEV::FlagNUW),
862 IntPtr);
863 } else {
864 NumBytesS = SE->getAddExpr(SE->getTruncateOrZeroExtend(BECount, IntPtr),
865 SE->getOne(IntPtr), SCEV::FlagNUW);
866 }
867
868 // And scale it based on the store size.
869 if (StoreSize != 1) {
870 NumBytesS = SE->getMulExpr(NumBytesS, SE->getConstant(IntPtr, StoreSize),
871 SCEV::FlagNUW);
872 }
873 return NumBytesS;
874}
875
876/// processLoopStridedStore - We see a strided store of some value. If we can
877/// transform this into a memset or memset_pattern in the loop preheader, do so.
878bool LoopIdiomRecognize::processLoopStridedStore(
879 Value *DestPtr, unsigned StoreSize, unsigned StoreAlignment,
880 Value *StoredVal, Instruction *TheStore,
881 SmallPtrSetImpl<Instruction *> &Stores, const SCEVAddRecExpr *Ev,
882 const SCEV *BECount, bool NegStride, bool IsLoopMemset) {
883 Value *SplatValue = isBytewiseValue(StoredVal);
884 Constant *PatternValue = nullptr;
885
886 if (!SplatValue)
887 PatternValue = getMemSetPatternValue(StoredVal, DL);
888
889 assert((SplatValue || PatternValue) &&(((SplatValue || PatternValue) && "Expected either splat value or pattern value."
) ? static_cast<void> (0) : __assert_fail ("(SplatValue || PatternValue) && \"Expected either splat value or pattern value.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 890, __PRETTY_FUNCTION__))
890 "Expected either splat value or pattern value.")(((SplatValue || PatternValue) && "Expected either splat value or pattern value."
) ? static_cast<void> (0) : __assert_fail ("(SplatValue || PatternValue) && \"Expected either splat value or pattern value.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 890, __PRETTY_FUNCTION__))
;
891
892 // The trip count of the loop and the base pointer of the addrec SCEV is
893 // guaranteed to be loop invariant, which means that it should dominate the
894 // header. This allows us to insert code for it in the preheader.
895 unsigned DestAS = DestPtr->getType()->getPointerAddressSpace();
896 BasicBlock *Preheader = CurLoop->getLoopPreheader();
897 IRBuilder<> Builder(Preheader->getTerminator());
898 SCEVExpander Expander(*SE, *DL, "loop-idiom");
899
900 Type *DestInt8PtrTy = Builder.getInt8PtrTy(DestAS);
901 Type *IntPtr = Builder.getIntPtrTy(*DL, DestAS);
902
903 const SCEV *Start = Ev->getStart();
904 // Handle negative strided loops.
905 if (NegStride)
906 Start = getStartForNegStride(Start, BECount, IntPtr, StoreSize, SE);
907
908 // TODO: ideally we should still be able to generate memset if SCEV expander
909 // is taught to generate the dependencies at the latest point.
910 if (!isSafeToExpand(Start, *SE))
911 return false;
912
913 // Okay, we have a strided store "p[i]" of a splattable value. We can turn
914 // this into a memset in the loop preheader now if we want. However, this
915 // would be unsafe to do if there is anything else in the loop that may read
916 // or write to the aliased location. Check for any overlap by generating the
917 // base pointer and checking the region.
918 Value *BasePtr =
919 Expander.expandCodeFor(Start, DestInt8PtrTy, Preheader->getTerminator());
920 if (mayLoopAccessLocation(BasePtr, ModRefInfo::ModRef, CurLoop, BECount,
921 StoreSize, *AA, Stores)) {
922 Expander.clear();
923 // If we generated new code for the base pointer, clean up.
924 RecursivelyDeleteTriviallyDeadInstructions(BasePtr, TLI);
925 return false;
926 }
927
928 if (avoidLIRForMultiBlockLoop(/*IsMemset=*/true, IsLoopMemset))
929 return false;
930
931 // Okay, everything looks good, insert the memset.
932
933 const SCEV *NumBytesS =
934 getNumBytes(BECount, IntPtr, StoreSize, CurLoop, DL, SE);
935
936 // TODO: ideally we should still be able to generate memset if SCEV expander
937 // is taught to generate the dependencies at the latest point.
938 if (!isSafeToExpand(NumBytesS, *SE))
939 return false;
940
941 Value *NumBytes =
942 Expander.expandCodeFor(NumBytesS, IntPtr, Preheader->getTerminator());
943
944 CallInst *NewCall;
945 if (SplatValue) {
946 NewCall =
947 Builder.CreateMemSet(BasePtr, SplatValue, NumBytes, StoreAlignment);
948 } else {
949 // Everything is emitted in default address space
950 Type *Int8PtrTy = DestInt8PtrTy;
951
952 Module *M = TheStore->getModule();
953 StringRef FuncName = "memset_pattern16";
954 FunctionCallee MSP = M->getOrInsertFunction(FuncName, Builder.getVoidTy(),
955 Int8PtrTy, Int8PtrTy, IntPtr);
956 inferLibFuncAttributes(M, FuncName, *TLI);
957
958 // Otherwise we should form a memset_pattern16. PatternValue is known to be
959 // an constant array of 16-bytes. Plop the value into a mergable global.
960 GlobalVariable *GV = new GlobalVariable(*M, PatternValue->getType(), true,
961 GlobalValue::PrivateLinkage,
962 PatternValue, ".memset_pattern");
963 GV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); // Ok to merge these.
964 GV->setAlignment(16);
965 Value *PatternPtr = ConstantExpr::getBitCast(GV, Int8PtrTy);
966 NewCall = Builder.CreateCall(MSP, {BasePtr, PatternPtr, NumBytes});
967 }
968
969 LLVM_DEBUG(dbgs() << " Formed memset: " << *NewCall << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " Formed memset: " <<
*NewCall << "\n" << " from store to: " <<
*Ev << " at: " << *TheStore << "\n"; } } while
(false)
970 << " from store to: " << *Ev << " at: " << *TheStoredo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " Formed memset: " <<
*NewCall << "\n" << " from store to: " <<
*Ev << " at: " << *TheStore << "\n"; } } while
(false)
971 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " Formed memset: " <<
*NewCall << "\n" << " from store to: " <<
*Ev << " at: " << *TheStore << "\n"; } } while
(false)
;
972 NewCall->setDebugLoc(TheStore->getDebugLoc());
973
974 ORE.emit([&]() {
975 return OptimizationRemark(DEBUG_TYPE"loop-idiom", "ProcessLoopStridedStore",
976 NewCall->getDebugLoc(), Preheader)
977 << "Transformed loop-strided store into a call to "
978 << ore::NV("NewFunction", NewCall->getCalledFunction())
979 << "() function";
980 });
981
982 // Okay, the memset has been formed. Zap the original store and anything that
983 // feeds into it.
984 for (auto *I : Stores)
985 deleteDeadInstruction(I);
986 ++NumMemSet;
987 return true;
988}
989
990/// If the stored value is a strided load in the same loop with the same stride
991/// this may be transformable into a memcpy. This kicks in for stuff like
992/// for (i) A[i] = B[i];
993bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
994 const SCEV *BECount) {
995 assert(SI->isUnordered() && "Expected only non-volatile non-ordered stores.")((SI->isUnordered() && "Expected only non-volatile non-ordered stores."
) ? static_cast<void> (0) : __assert_fail ("SI->isUnordered() && \"Expected only non-volatile non-ordered stores.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 995, __PRETTY_FUNCTION__))
;
996
997 Value *StorePtr = SI->getPointerOperand();
998 const SCEVAddRecExpr *StoreEv = cast<SCEVAddRecExpr>(SE->getSCEV(StorePtr));
999 APInt Stride = getStoreStride(StoreEv);
1000 unsigned StoreSize = DL->getTypeStoreSize(SI->getValueOperand()->getType());
1001 bool NegStride = StoreSize == -Stride;
1002
1003 // The store must be feeding a non-volatile load.
1004 LoadInst *LI = cast<LoadInst>(SI->getValueOperand());
1005 assert(LI->isUnordered() && "Expected only non-volatile non-ordered loads.")((LI->isUnordered() && "Expected only non-volatile non-ordered loads."
) ? static_cast<void> (0) : __assert_fail ("LI->isUnordered() && \"Expected only non-volatile non-ordered loads.\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 1005, __PRETTY_FUNCTION__))
;
1006
1007 // See if the pointer expression is an AddRec like {base,+,1} on the current
1008 // loop, which indicates a strided load. If we have something else, it's a
1009 // random load we can't handle.
1010 const SCEVAddRecExpr *LoadEv =
1011 cast<SCEVAddRecExpr>(SE->getSCEV(LI->getPointerOperand()));
1012
1013 // The trip count of the loop and the base pointer of the addrec SCEV is
1014 // guaranteed to be loop invariant, which means that it should dominate the
1015 // header. This allows us to insert code for it in the preheader.
1016 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1017 IRBuilder<> Builder(Preheader->getTerminator());
1018 SCEVExpander Expander(*SE, *DL, "loop-idiom");
1019
1020 const SCEV *StrStart = StoreEv->getStart();
1021 unsigned StrAS = SI->getPointerAddressSpace();
1022 Type *IntPtrTy = Builder.getIntPtrTy(*DL, StrAS);
1023
1024 // Handle negative strided loops.
1025 if (NegStride)
1026 StrStart = getStartForNegStride(StrStart, BECount, IntPtrTy, StoreSize, SE);
1027
1028 // Okay, we have a strided store "p[i]" of a loaded value. We can turn
1029 // this into a memcpy in the loop preheader now if we want. However, this
1030 // would be unsafe to do if there is anything else in the loop that may read
1031 // or write the memory region we're storing to. This includes the load that
1032 // feeds the stores. Check for an alias by generating the base address and
1033 // checking everything.
1034 Value *StoreBasePtr = Expander.expandCodeFor(
1035 StrStart, Builder.getInt8PtrTy(StrAS), Preheader->getTerminator());
1036
1037 SmallPtrSet<Instruction *, 1> Stores;
1038 Stores.insert(SI);
1039 if (mayLoopAccessLocation(StoreBasePtr, ModRefInfo::ModRef, CurLoop, BECount,
1040 StoreSize, *AA, Stores)) {
1041 Expander.clear();
1042 // If we generated new code for the base pointer, clean up.
1043 RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
1044 return false;
1045 }
1046
1047 const SCEV *LdStart = LoadEv->getStart();
1048 unsigned LdAS = LI->getPointerAddressSpace();
1049
1050 // Handle negative strided loops.
1051 if (NegStride)
1052 LdStart = getStartForNegStride(LdStart, BECount, IntPtrTy, StoreSize, SE);
1053
1054 // For a memcpy, we have to make sure that the input array is not being
1055 // mutated by the loop.
1056 Value *LoadBasePtr = Expander.expandCodeFor(
1057 LdStart, Builder.getInt8PtrTy(LdAS), Preheader->getTerminator());
1058
1059 if (mayLoopAccessLocation(LoadBasePtr, ModRefInfo::Mod, CurLoop, BECount,
1060 StoreSize, *AA, Stores)) {
1061 Expander.clear();
1062 // If we generated new code for the base pointer, clean up.
1063 RecursivelyDeleteTriviallyDeadInstructions(LoadBasePtr, TLI);
1064 RecursivelyDeleteTriviallyDeadInstructions(StoreBasePtr, TLI);
1065 return false;
1066 }
1067
1068 if (avoidLIRForMultiBlockLoop())
1069 return false;
1070
1071 // Okay, everything is safe, we can transform this!
1072
1073 const SCEV *NumBytesS =
1074 getNumBytes(BECount, IntPtrTy, StoreSize, CurLoop, DL, SE);
1075
1076 Value *NumBytes =
1077 Expander.expandCodeFor(NumBytesS, IntPtrTy, Preheader->getTerminator());
1078
1079 CallInst *NewCall = nullptr;
1080 // Check whether to generate an unordered atomic memcpy:
1081 // If the load or store are atomic, then they must necessarily be unordered
1082 // by previous checks.
1083 if (!SI->isAtomic() && !LI->isAtomic())
1084 NewCall = Builder.CreateMemCpy(StoreBasePtr, SI->getAlignment(),
1085 LoadBasePtr, LI->getAlignment(), NumBytes);
1086 else {
1087 // We cannot allow unaligned ops for unordered load/store, so reject
1088 // anything where the alignment isn't at least the element size.
1089 unsigned Align = std::min(SI->getAlignment(), LI->getAlignment());
1090 if (Align < StoreSize)
1091 return false;
1092
1093 // If the element.atomic memcpy is not lowered into explicit
1094 // loads/stores later, then it will be lowered into an element-size
1095 // specific lib call. If the lib call doesn't exist for our store size, then
1096 // we shouldn't generate the memcpy.
1097 if (StoreSize > TTI->getAtomicMemIntrinsicMaxElementSize())
1098 return false;
1099
1100 // Create the call.
1101 // Note that unordered atomic loads/stores are *required* by the spec to
1102 // have an alignment but non-atomic loads/stores may not.
1103 NewCall = Builder.CreateElementUnorderedAtomicMemCpy(
1104 StoreBasePtr, SI->getAlignment(), LoadBasePtr, LI->getAlignment(),
1105 NumBytes, StoreSize);
1106 }
1107 NewCall->setDebugLoc(SI->getDebugLoc());
1108
1109 LLVM_DEBUG(dbgs() << " Formed memcpy: " << *NewCall << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " Formed memcpy: " <<
*NewCall << "\n" << " from load ptr=" <<
*LoadEv << " at: " << *LI << "\n" <<
" from store ptr=" << *StoreEv << " at: " <<
*SI << "\n"; } } while (false)
1110 << " from load ptr=" << *LoadEv << " at: " << *LI << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " Formed memcpy: " <<
*NewCall << "\n" << " from load ptr=" <<
*LoadEv << " at: " << *LI << "\n" <<
" from store ptr=" << *StoreEv << " at: " <<
*SI << "\n"; } } while (false)
1111 << " from store ptr=" << *StoreEv << " at: " << *SIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " Formed memcpy: " <<
*NewCall << "\n" << " from load ptr=" <<
*LoadEv << " at: " << *LI << "\n" <<
" from store ptr=" << *StoreEv << " at: " <<
*SI << "\n"; } } while (false)
1112 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " Formed memcpy: " <<
*NewCall << "\n" << " from load ptr=" <<
*LoadEv << " at: " << *LI << "\n" <<
" from store ptr=" << *StoreEv << " at: " <<
*SI << "\n"; } } while (false)
;
1113
1114 ORE.emit([&]() {
1115 return OptimizationRemark(DEBUG_TYPE"loop-idiom", "ProcessLoopStoreOfLoopLoad",
1116 NewCall->getDebugLoc(), Preheader)
1117 << "Formed a call to "
1118 << ore::NV("NewFunction", NewCall->getCalledFunction())
1119 << "() function";
1120 });
1121
1122 // Okay, the memcpy has been formed. Zap the original store and anything that
1123 // feeds into it.
1124 deleteDeadInstruction(SI);
1125 ++NumMemCpy;
1126 return true;
1127}
1128
1129// When compiling for codesize we avoid idiom recognition for a multi-block loop
1130// unless it is a loop_memset idiom or a memset/memcpy idiom in a nested loop.
1131//
1132bool LoopIdiomRecognize::avoidLIRForMultiBlockLoop(bool IsMemset,
1133 bool IsLoopMemset) {
1134 if (ApplyCodeSizeHeuristics && CurLoop->getNumBlocks() > 1) {
1135 if (!CurLoop->getParentLoop() && (!IsMemset || !IsLoopMemset)) {
1136 LLVM_DEBUG(dbgs() << " " << CurLoop->getHeader()->getParent()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " " << CurLoop->getHeader
()->getParent()->getName() << " : LIR " << (
IsMemset ? "Memset" : "Memcpy") << " avoided: multi-block top-level loop\n"
; } } while (false)
1137 << " : LIR " << (IsMemset ? "Memset" : "Memcpy")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " " << CurLoop->getHeader
()->getParent()->getName() << " : LIR " << (
IsMemset ? "Memset" : "Memcpy") << " avoided: multi-block top-level loop\n"
; } } while (false)
1138 << " avoided: multi-block top-level loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << " " << CurLoop->getHeader
()->getParent()->getName() << " : LIR " << (
IsMemset ? "Memset" : "Memcpy") << " avoided: multi-block top-level loop\n"
; } } while (false)
;
1139 return true;
1140 }
1141 }
1142
1143 return false;
1144}
1145
1146bool LoopIdiomRecognize::runOnNoncountableLoop() {
1147 LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << "loop-idiom" " Scanning: F["
<< CurLoop->getHeader()->getParent()->getName
() << "] Noncountable Loop %" << CurLoop->getHeader
()->getName() << "\n"; } } while (false)
11
Assuming 'DebugFlag' is 0
12
Loop condition is false. Exiting loop
1148 << CurLoop->getHeader()->getParent()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << "loop-idiom" " Scanning: F["
<< CurLoop->getHeader()->getParent()->getName
() << "] Noncountable Loop %" << CurLoop->getHeader
()->getName() << "\n"; } } while (false)
1149 << "] Noncountable Loop %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << "loop-idiom" " Scanning: F["
<< CurLoop->getHeader()->getParent()->getName
() << "] Noncountable Loop %" << CurLoop->getHeader
()->getName() << "\n"; } } while (false)
1150 << CurLoop->getHeader()->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-idiom")) { dbgs() << "loop-idiom" " Scanning: F["
<< CurLoop->getHeader()->getParent()->getName
() << "] Noncountable Loop %" << CurLoop->getHeader
()->getName() << "\n"; } } while (false)
;
1151
1152 return recognizePopcount() || recognizeAndInsertFFS();
13
Calling 'LoopIdiomRecognize::recognizeAndInsertFFS'
1153}
1154
1155/// Check if the given conditional branch is based on the comparison between
1156/// a variable and zero, and if the variable is non-zero or zero (JmpOnZero is
1157/// true), the control yields to the loop entry. If the branch matches the
1158/// behavior, the variable involved in the comparison is returned. This function
1159/// will be called to see if the precondition and postcondition of the loop are
1160/// in desirable form.
1161static Value *matchCondition(BranchInst *BI, BasicBlock *LoopEntry,
1162 bool JmpOnZero = false) {
1163 if (!BI || !BI->isConditional())
1164 return nullptr;
1165
1166 ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition());
1167 if (!Cond)
1168 return nullptr;
1169
1170 ConstantInt *CmpZero = dyn_cast<ConstantInt>(Cond->getOperand(1));
1171 if (!CmpZero || !CmpZero->isZero())
1172 return nullptr;
1173
1174 BasicBlock *TrueSucc = BI->getSuccessor(0);
1175 BasicBlock *FalseSucc = BI->getSuccessor(1);
1176 if (JmpOnZero)
1177 std::swap(TrueSucc, FalseSucc);
1178
1179 ICmpInst::Predicate Pred = Cond->getPredicate();
1180 if ((Pred == ICmpInst::ICMP_NE && TrueSucc == LoopEntry) ||
1181 (Pred == ICmpInst::ICMP_EQ && FalseSucc == LoopEntry))
1182 return Cond->getOperand(0);
1183
1184 return nullptr;
1185}
1186
1187// Check if the recurrence variable `VarX` is in the right form to create
1188// the idiom. Returns the value coerced to a PHINode if so.
1189static PHINode *getRecurrenceVar(Value *VarX, Instruction *DefX,
1190 BasicBlock *LoopEntry) {
1191 auto *PhiX = dyn_cast<PHINode>(VarX);
1192 if (PhiX && PhiX->getParent() == LoopEntry &&
1193 (PhiX->getOperand(0) == DefX || PhiX->getOperand(1) == DefX))
1194 return PhiX;
1195 return nullptr;
1196}
1197
1198/// Return true iff the idiom is detected in the loop.
1199///
1200/// Additionally:
1201/// 1) \p CntInst is set to the instruction counting the population bit.
1202/// 2) \p CntPhi is set to the corresponding phi node.
1203/// 3) \p Var is set to the value whose population bits are being counted.
1204///
1205/// The core idiom we are trying to detect is:
1206/// \code
1207/// if (x0 != 0)
1208/// goto loop-exit // the precondition of the loop
1209/// cnt0 = init-val;
1210/// do {
1211/// x1 = phi (x0, x2);
1212/// cnt1 = phi(cnt0, cnt2);
1213///
1214/// cnt2 = cnt1 + 1;
1215/// ...
1216/// x2 = x1 & (x1 - 1);
1217/// ...
1218/// } while(x != 0);
1219///
1220/// loop-exit:
1221/// \endcode
1222static bool detectPopcountIdiom(Loop *CurLoop, BasicBlock *PreCondBB,
1223 Instruction *&CntInst, PHINode *&CntPhi,
1224 Value *&Var) {
1225 // step 1: Check to see if the look-back branch match this pattern:
1226 // "if (a!=0) goto loop-entry".
1227 BasicBlock *LoopEntry;
1228 Instruction *DefX2, *CountInst;
1229 Value *VarX1, *VarX0;
1230 PHINode *PhiX, *CountPhi;
1231
1232 DefX2 = CountInst = nullptr;
1233 VarX1 = VarX0 = nullptr;
1234 PhiX = CountPhi = nullptr;
1235 LoopEntry = *(CurLoop->block_begin());
1236
1237 // step 1: Check if the loop-back branch is in desirable form.
1238 {
1239 if (Value *T = matchCondition(
1240 dyn_cast<BranchInst>(LoopEntry->getTerminator()), LoopEntry))
1241 DefX2 = dyn_cast<Instruction>(T);
1242 else
1243 return false;
1244 }
1245
1246 // step 2: detect instructions corresponding to "x2 = x1 & (x1 - 1)"
1247 {
1248 if (!DefX2 || DefX2->getOpcode() != Instruction::And)
1249 return false;
1250
1251 BinaryOperator *SubOneOp;
1252
1253 if ((SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(0))))
1254 VarX1 = DefX2->getOperand(1);
1255 else {
1256 VarX1 = DefX2->getOperand(0);
1257 SubOneOp = dyn_cast<BinaryOperator>(DefX2->getOperand(1));
1258 }
1259 if (!SubOneOp || SubOneOp->getOperand(0) != VarX1)
1260 return false;
1261
1262 ConstantInt *Dec = dyn_cast<ConstantInt>(SubOneOp->getOperand(1));
1263 if (!Dec ||
1264 !((SubOneOp->getOpcode() == Instruction::Sub && Dec->isOne()) ||
1265 (SubOneOp->getOpcode() == Instruction::Add &&
1266 Dec->isMinusOne()))) {
1267 return false;
1268 }
1269 }
1270
1271 // step 3: Check the recurrence of variable X
1272 PhiX = getRecurrenceVar(VarX1, DefX2, LoopEntry);
1273 if (!PhiX)
1274 return false;
1275
1276 // step 4: Find the instruction which count the population: cnt2 = cnt1 + 1
1277 {
1278 CountInst = nullptr;
1279 for (BasicBlock::iterator Iter = LoopEntry->getFirstNonPHI()->getIterator(),
1280 IterE = LoopEntry->end();
1281 Iter != IterE; Iter++) {
1282 Instruction *Inst = &*Iter;
1283 if (Inst->getOpcode() != Instruction::Add)
1284 continue;
1285
1286 ConstantInt *Inc = dyn_cast<ConstantInt>(Inst->getOperand(1));
1287 if (!Inc || !Inc->isOne())
1288 continue;
1289
1290 PHINode *Phi = getRecurrenceVar(Inst->getOperand(0), Inst, LoopEntry);
1291 if (!Phi)
1292 continue;
1293
1294 // Check if the result of the instruction is live of the loop.
1295 bool LiveOutLoop = false;
1296 for (User *U : Inst->users()) {
1297 if ((cast<Instruction>(U))->getParent() != LoopEntry) {
1298 LiveOutLoop = true;
1299 break;
1300 }
1301 }
1302
1303 if (LiveOutLoop) {
1304 CountInst = Inst;
1305 CountPhi = Phi;
1306 break;
1307 }
1308 }
1309
1310 if (!CountInst)
1311 return false;
1312 }
1313
1314 // step 5: check if the precondition is in this form:
1315 // "if (x != 0) goto loop-head ; else goto somewhere-we-don't-care;"
1316 {
1317 auto *PreCondBr = dyn_cast<BranchInst>(PreCondBB->getTerminator());
1318 Value *T = matchCondition(PreCondBr, CurLoop->getLoopPreheader());
1319 if (T != PhiX->getOperand(0) && T != PhiX->getOperand(1))
1320 return false;
1321
1322 CntInst = CountInst;
1323 CntPhi = CountPhi;
1324 Var = T;
1325 }
1326
1327 return true;
1328}
1329
1330/// Return true if the idiom is detected in the loop.
1331///
1332/// Additionally:
1333/// 1) \p CntInst is set to the instruction Counting Leading Zeros (CTLZ)
1334/// or nullptr if there is no such.
1335/// 2) \p CntPhi is set to the corresponding phi node
1336/// or nullptr if there is no such.
1337/// 3) \p Var is set to the value whose CTLZ could be used.
1338/// 4) \p DefX is set to the instruction calculating Loop exit condition.
1339///
1340/// The core idiom we are trying to detect is:
1341/// \code
1342/// if (x0 == 0)
1343/// goto loop-exit // the precondition of the loop
1344/// cnt0 = init-val;
1345/// do {
1346/// x = phi (x0, x.next); //PhiX
1347/// cnt = phi(cnt0, cnt.next);
1348///
1349/// cnt.next = cnt + 1;
1350/// ...
1351/// x.next = x >> 1; // DefX
1352/// ...
1353/// } while(x.next != 0);
1354///
1355/// loop-exit:
1356/// \endcode
1357static bool detectShiftUntilZeroIdiom(Loop *CurLoop, const DataLayout &DL,
1358 Intrinsic::ID &IntrinID, Value *&InitX,
1359 Instruction *&CntInst, PHINode *&CntPhi,
1360 Instruction *&DefX) {
1361 BasicBlock *LoopEntry;
1362 Value *VarX = nullptr;
1363
1364 DefX = nullptr;
1365 CntInst = nullptr;
1366 CntPhi = nullptr;
1367 LoopEntry = *(CurLoop->block_begin());
1368
1369 // step 1: Check if the loop-back branch is in desirable form.
1370 if (Value *T = matchCondition(
18
Assuming 'T' is non-null
19
Taking true branch
1371 dyn_cast<BranchInst>(LoopEntry->getTerminator()), LoopEntry))
1372 DefX = dyn_cast<Instruction>(T);
1373 else
1374 return false;
1375
1376 // step 2: detect instructions corresponding to "x.next = x >> 1 or x << 1"
1377 if (!DefX || !DefX->isShift())
20
Assuming the condition is false
21
Assuming the condition is false
22
Taking false branch
1378 return false;
1379 IntrinID = DefX->getOpcode() == Instruction::Shl ? Intrinsic::cttz :
23
Assuming the condition is false
24
'?' condition is false
1380 Intrinsic::ctlz;
1381 ConstantInt *Shft = dyn_cast<ConstantInt>(DefX->getOperand(1));
1382 if (!Shft || !Shft->isOne())
25
Assuming 'Shft' is non-null
26
Assuming the condition is false
27
Taking false branch
1383 return false;
1384 VarX = DefX->getOperand(0);
1385
1386 // step 3: Check the recurrence of variable X
1387 PHINode *PhiX = getRecurrenceVar(VarX, DefX, LoopEntry);
1388 if (!PhiX)
28
Assuming 'PhiX' is non-null
29
Taking false branch
1389 return false;
1390
1391 InitX = PhiX->getIncomingValueForBlock(CurLoop->getLoopPreheader());
30
Value assigned to 'InitX'
1392
1393 // Make sure the initial value can't be negative otherwise the ashr in the
1394 // loop might never reach zero which would make the loop infinite.
1395 if (DefX->getOpcode() == Instruction::AShr && !isKnownNonNegative(InitX, DL))
31
Assuming the condition is false
1396 return false;
1397
1398 // step 4: Find the instruction which count the CTLZ: cnt.next = cnt + 1
1399 // TODO: We can skip the step. If loop trip count is known (CTLZ),
1400 // then all uses of "cnt.next" could be optimized to the trip count
1401 // plus "cnt0". Currently it is not optimized.
1402 // This step could be used to detect POPCNT instruction:
1403 // cnt.next = cnt + (x.next & 1)
1404 for (BasicBlock::iterator Iter = LoopEntry->getFirstNonPHI()->getIterator(),
32
Loop condition is true. Entering loop body
1405 IterE = LoopEntry->end();
1406 Iter != IterE; Iter++) {
1407 Instruction *Inst = &*Iter;
1408 if (Inst->getOpcode() != Instruction::Add)
33
Assuming the condition is false
34
Taking false branch
1409 continue;
1410
1411 ConstantInt *Inc = dyn_cast<ConstantInt>(Inst->getOperand(1));
1412 if (!Inc || !Inc->isOne())
35
Assuming 'Inc' is non-null
36
Assuming the condition is false
37
Taking false branch
1413 continue;
1414
1415 PHINode *Phi = getRecurrenceVar(Inst->getOperand(0), Inst, LoopEntry);
1416 if (!Phi)
38
Assuming 'Phi' is non-null
39
Taking false branch
1417 continue;
1418
1419 CntInst = Inst;
1420 CntPhi = Phi;
1421 break;
40
Execution continues on line 1423
1422 }
1423 if (!CntInst)
41
Taking false branch
1424 return false;
1425
1426 return true;
1427}
1428
1429/// Recognize CTLZ or CTTZ idiom in a non-countable loop and convert the loop
1430/// to countable (with CTLZ / CTTZ trip count). If CTLZ / CTTZ inserted as a new
1431/// trip count returns true; otherwise, returns false.
1432bool LoopIdiomRecognize::recognizeAndInsertFFS() {
1433 // Give up if the loop has multiple blocks or multiple backedges.
1434 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
14
Assuming the condition is false
15
Assuming the condition is false
16
Taking false branch
1435 return false;
1436
1437 Intrinsic::ID IntrinID;
1438 Value *InitX;
1439 Instruction *DefX = nullptr;
1440 PHINode *CntPhi = nullptr;
1441 Instruction *CntInst = nullptr;
1442 // Help decide if transformation is profitable. For ShiftUntilZero idiom,
1443 // this is always 6.
1444 size_t IdiomCanonicalSize = 6;
1445
1446 if (!detectShiftUntilZeroIdiom(CurLoop, *DL, IntrinID, InitX,
17
Calling 'detectShiftUntilZeroIdiom'
42
Returning from 'detectShiftUntilZeroIdiom'
43
Taking false branch
1447 CntInst, CntPhi, DefX))
1448 return false;
1449
1450 bool IsCntPhiUsedOutsideLoop = false;
1451 for (User *U : CntPhi->users())
1452 if (!CurLoop->contains(cast<Instruction>(U))) {
1453 IsCntPhiUsedOutsideLoop = true;
1454 break;
1455 }
1456 bool IsCntInstUsedOutsideLoop = false;
1457 for (User *U : CntInst->users())
1458 if (!CurLoop->contains(cast<Instruction>(U))) {
1459 IsCntInstUsedOutsideLoop = true;
1460 break;
1461 }
1462 // If both CntInst and CntPhi are used outside the loop the profitability
1463 // is questionable.
1464 if (IsCntInstUsedOutsideLoop && IsCntPhiUsedOutsideLoop)
1465 return false;
1466
1467 // For some CPUs result of CTLZ(X) intrinsic is undefined
1468 // when X is 0. If we can not guarantee X != 0, we need to check this
1469 // when expand.
1470 bool ZeroCheck = false;
1471 // It is safe to assume Preheader exist as it was checked in
1472 // parent function RunOnLoop.
1473 BasicBlock *PH = CurLoop->getLoopPreheader();
1474
1475 // If we are using the count instruction outside the loop, make sure we
1476 // have a zero check as a precondition. Without the check the loop would run
1477 // one iteration for before any check of the input value. This means 0 and 1
1478 // would have identical behavior in the original loop and thus
1479 if (!IsCntPhiUsedOutsideLoop) {
44
Taking true branch
1480 auto *PreCondBB = PH->getSinglePredecessor();
1481 if (!PreCondBB)
45
Assuming 'PreCondBB' is non-null
46
Taking false branch
1482 return false;
1483 auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator());
1484 if (!PreCondBI)
47
Assuming 'PreCondBI' is non-null
48
Taking false branch
1485 return false;
1486 if (matchCondition(PreCondBI, PH) != InitX)
49
Assuming pointer value is null
50
Taking false branch
1487 return false;
1488 ZeroCheck = true;
1489 }
1490
1491 // Check if CTLZ / CTTZ intrinsic is profitable. Assume it is always
1492 // profitable if we delete the loop.
1493
1494 // the loop has only 6 instructions:
1495 // %n.addr.0 = phi [ %n, %entry ], [ %shr, %while.cond ]
1496 // %i.0 = phi [ %i0, %entry ], [ %inc, %while.cond ]
1497 // %shr = ashr %n.addr.0, 1
1498 // %tobool = icmp eq %shr, 0
1499 // %inc = add nsw %i.0, 1
1500 // br i1 %tobool
1501
1502 const Value *Args[] =
1503 {InitX, ZeroCheck ? ConstantInt::getTrue(InitX->getContext())
51
'?' condition is true
52
Called C++ object pointer is null
1504 : ConstantInt::getFalse(InitX->getContext())};
1505
1506 // @llvm.dbg doesn't count as they have no semantic effect.
1507 auto InstWithoutDebugIt = CurLoop->getHeader()->instructionsWithoutDebug();
1508 uint32_t HeaderSize =
1509 std::distance(InstWithoutDebugIt.begin(), InstWithoutDebugIt.end());
1510
1511 if (HeaderSize != IdiomCanonicalSize &&
1512 TTI->getIntrinsicCost(IntrinID, InitX->getType(), Args) >
1513 TargetTransformInfo::TCC_Basic)
1514 return false;
1515
1516 transformLoopToCountable(IntrinID, PH, CntInst, CntPhi, InitX, DefX,
1517 DefX->getDebugLoc(), ZeroCheck,
1518 IsCntPhiUsedOutsideLoop);
1519 return true;
1520}
1521
1522/// Recognizes a population count idiom in a non-countable loop.
1523///
1524/// If detected, transforms the relevant code to issue the popcount intrinsic
1525/// function call, and returns true; otherwise, returns false.
1526bool LoopIdiomRecognize::recognizePopcount() {
1527 if (TTI->getPopcntSupport(32) != TargetTransformInfo::PSK_FastHardware)
1528 return false;
1529
1530 // Counting population are usually conducted by few arithmetic instructions.
1531 // Such instructions can be easily "absorbed" by vacant slots in a
1532 // non-compact loop. Therefore, recognizing popcount idiom only makes sense
1533 // in a compact loop.
1534
1535 // Give up if the loop has multiple blocks or multiple backedges.
1536 if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
1537 return false;
1538
1539 BasicBlock *LoopBody = *(CurLoop->block_begin());
1540 if (LoopBody->size() >= 20) {
1541 // The loop is too big, bail out.
1542 return false;
1543 }
1544
1545 // It should have a preheader containing nothing but an unconditional branch.
1546 BasicBlock *PH = CurLoop->getLoopPreheader();
1547 if (!PH || &PH->front() != PH->getTerminator())
1548 return false;
1549 auto *EntryBI = dyn_cast<BranchInst>(PH->getTerminator());
1550 if (!EntryBI || EntryBI->isConditional())
1551 return false;
1552
1553 // It should have a precondition block where the generated popcount intrinsic
1554 // function can be inserted.
1555 auto *PreCondBB = PH->getSinglePredecessor();
1556 if (!PreCondBB)
1557 return false;
1558 auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator());
1559 if (!PreCondBI || PreCondBI->isUnconditional())
1560 return false;
1561
1562 Instruction *CntInst;
1563 PHINode *CntPhi;
1564 Value *Val;
1565 if (!detectPopcountIdiom(CurLoop, PreCondBB, CntInst, CntPhi, Val))
1566 return false;
1567
1568 transformLoopToPopcount(PreCondBB, CntInst, CntPhi, Val);
1569 return true;
1570}
1571
1572static CallInst *createPopcntIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
1573 const DebugLoc &DL) {
1574 Value *Ops[] = {Val};
1575 Type *Tys[] = {Val->getType()};
1576
1577 Module *M = IRBuilder.GetInsertBlock()->getParent()->getParent();
1578 Function *Func = Intrinsic::getDeclaration(M, Intrinsic::ctpop, Tys);
1579 CallInst *CI = IRBuilder.CreateCall(Func, Ops);
1580 CI->setDebugLoc(DL);
1581
1582 return CI;
1583}
1584
1585static CallInst *createFFSIntrinsic(IRBuilder<> &IRBuilder, Value *Val,
1586 const DebugLoc &DL, bool ZeroCheck,
1587 Intrinsic::ID IID) {
1588 Value *Ops[] = {Val, ZeroCheck ? IRBuilder.getTrue() : IRBuilder.getFalse()};
1589 Type *Tys[] = {Val->getType()};
1590
1591 Module *M = IRBuilder.GetInsertBlock()->getParent()->getParent();
1592 Function *Func = Intrinsic::getDeclaration(M, IID, Tys);
1593 CallInst *CI = IRBuilder.CreateCall(Func, Ops);
1594 CI->setDebugLoc(DL);
1595
1596 return CI;
1597}
1598
1599/// Transform the following loop (Using CTLZ, CTTZ is similar):
1600/// loop:
1601/// CntPhi = PHI [Cnt0, CntInst]
1602/// PhiX = PHI [InitX, DefX]
1603/// CntInst = CntPhi + 1
1604/// DefX = PhiX >> 1
1605/// LOOP_BODY
1606/// Br: loop if (DefX != 0)
1607/// Use(CntPhi) or Use(CntInst)
1608///
1609/// Into:
1610/// If CntPhi used outside the loop:
1611/// CountPrev = BitWidth(InitX) - CTLZ(InitX >> 1)
1612/// Count = CountPrev + 1
1613/// else
1614/// Count = BitWidth(InitX) - CTLZ(InitX)
1615/// loop:
1616/// CntPhi = PHI [Cnt0, CntInst]
1617/// PhiX = PHI [InitX, DefX]
1618/// PhiCount = PHI [Count, Dec]
1619/// CntInst = CntPhi + 1
1620/// DefX = PhiX >> 1
1621/// Dec = PhiCount - 1
1622/// LOOP_BODY
1623/// Br: loop if (Dec != 0)
1624/// Use(CountPrev + Cnt0) // Use(CntPhi)
1625/// or
1626/// Use(Count + Cnt0) // Use(CntInst)
1627///
1628/// If LOOP_BODY is empty the loop will be deleted.
1629/// If CntInst and DefX are not used in LOOP_BODY they will be removed.
1630void LoopIdiomRecognize::transformLoopToCountable(
1631 Intrinsic::ID IntrinID, BasicBlock *Preheader, Instruction *CntInst,
1632 PHINode *CntPhi, Value *InitX, Instruction *DefX, const DebugLoc &DL,
1633 bool ZeroCheck, bool IsCntPhiUsedOutsideLoop) {
1634 BranchInst *PreheaderBr = cast<BranchInst>(Preheader->getTerminator());
1635
1636 // Step 1: Insert the CTLZ/CTTZ instruction at the end of the preheader block
1637 IRBuilder<> Builder(PreheaderBr);
1638 Builder.SetCurrentDebugLocation(DL);
1639 Value *FFS, *Count, *CountPrev, *NewCount, *InitXNext;
1640
1641 // Count = BitWidth - CTLZ(InitX);
1642 // If there are uses of CntPhi create:
1643 // CountPrev = BitWidth - CTLZ(InitX >> 1);
1644 if (IsCntPhiUsedOutsideLoop) {
1645 if (DefX->getOpcode() == Instruction::AShr)
1646 InitXNext =
1647 Builder.CreateAShr(InitX, ConstantInt::get(InitX->getType(), 1));
1648 else if (DefX->getOpcode() == Instruction::LShr)
1649 InitXNext =
1650 Builder.CreateLShr(InitX, ConstantInt::get(InitX->getType(), 1));
1651 else if (DefX->getOpcode() == Instruction::Shl) // cttz
1652 InitXNext =
1653 Builder.CreateShl(InitX, ConstantInt::get(InitX->getType(), 1));
1654 else
1655 llvm_unreachable("Unexpected opcode!")::llvm::llvm_unreachable_internal("Unexpected opcode!", "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/LoopIdiomRecognize.cpp"
, 1655)
;
1656 } else
1657 InitXNext = InitX;
1658 FFS = createFFSIntrinsic(Builder, InitXNext, DL, ZeroCheck, IntrinID);
1659 Count = Builder.CreateSub(
1660 ConstantInt::get(FFS->getType(),
1661 FFS->getType()->getIntegerBitWidth()),
1662 FFS);
1663 if (IsCntPhiUsedOutsideLoop) {
1664 CountPrev = Count;
1665 Count = Builder.CreateAdd(
1666 CountPrev,
1667 ConstantInt::get(CountPrev->getType(), 1));
1668 }
1669
1670 NewCount = Builder.CreateZExtOrTrunc(
1671 IsCntPhiUsedOutsideLoop ? CountPrev : Count,
1672 cast<IntegerType>(CntInst->getType()));
1673
1674 // If the counter's initial value is not zero, insert Add Inst.
1675 Value *CntInitVal = CntPhi->getIncomingValueForBlock(Preheader);
1676 ConstantInt *InitConst = dyn_cast<ConstantInt>(CntInitVal);
1677 if (!InitConst || !InitConst->isZero())
1678 NewCount = Builder.CreateAdd(NewCount, CntInitVal);
1679
1680 // Step 2: Insert new IV and loop condition:
1681 // loop:
1682 // ...
1683 // PhiCount = PHI [Count, Dec]
1684 // ...
1685 // Dec = PhiCount - 1
1686 // ...
1687 // Br: loop if (Dec != 0)
1688 BasicBlock *Body = *(CurLoop->block_begin());
1689 auto *LbBr = cast<BranchInst>(Body->getTerminator());
1690 ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition());
1691 Type *Ty = Count->getType();
1692
1693 PHINode *TcPhi = PHINode::Create(Ty, 2, "tcphi", &Body->front());
1694
1695 Builder.SetInsertPoint(LbCond);
1696 Instruction *TcDec = cast<Instruction>(
1697 Builder.CreateSub(TcPhi, ConstantInt::get(Ty, 1),
1698 "tcdec", false, true));
1699
1700 TcPhi->addIncoming(Count, Preheader);
1701 TcPhi->addIncoming(TcDec, Body);
1702
1703 CmpInst::Predicate Pred =
1704 (LbBr->getSuccessor(0) == Body) ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ;
1705 LbCond->setPredicate(Pred);
1706 LbCond->setOperand(0, TcDec);
1707 LbCond->setOperand(1, ConstantInt::get(Ty, 0));
1708
1709 // Step 3: All the references to the original counter outside
1710 // the loop are replaced with the NewCount
1711 if (IsCntPhiUsedOutsideLoop)
1712 CntPhi->replaceUsesOutsideBlock(NewCount, Body);
1713 else
1714 CntInst->replaceUsesOutsideBlock(NewCount, Body);
1715
1716 // step 4: Forget the "non-computable" trip-count SCEV associated with the
1717 // loop. The loop would otherwise not be deleted even if it becomes empty.
1718 SE->forgetLoop(CurLoop);
1719}
1720
1721void LoopIdiomRecognize::transformLoopToPopcount(BasicBlock *PreCondBB,
1722 Instruction *CntInst,
1723 PHINode *CntPhi, Value *Var) {
1724 BasicBlock *PreHead = CurLoop->getLoopPreheader();
1725 auto *PreCondBr = cast<BranchInst>(PreCondBB->getTerminator());
1726 const DebugLoc &DL = CntInst->getDebugLoc();
1727
1728 // Assuming before transformation, the loop is following:
1729 // if (x) // the precondition
1730 // do { cnt++; x &= x - 1; } while(x);
1731
1732 // Step 1: Insert the ctpop instruction at the end of the precondition block
1733 IRBuilder<> Builder(PreCondBr);
1734 Value *PopCnt, *PopCntZext, *NewCount, *TripCnt;
1735 {
1736 PopCnt = createPopcntIntrinsic(Builder, Var, DL);
1737 NewCount = PopCntZext =
1738 Builder.CreateZExtOrTrunc(PopCnt, cast<IntegerType>(CntPhi->getType()));
1739
1740 if (NewCount != PopCnt)
1741 (cast<Instruction>(NewCount))->setDebugLoc(DL);
1742
1743 // TripCnt is exactly the number of iterations the loop has
1744 TripCnt = NewCount;
1745
1746 // If the population counter's initial value is not zero, insert Add Inst.
1747 Value *CntInitVal = CntPhi->getIncomingValueForBlock(PreHead);
1748 ConstantInt *InitConst = dyn_cast<ConstantInt>(CntInitVal);
1749 if (!InitConst || !InitConst->isZero()) {
1750 NewCount = Builder.CreateAdd(NewCount, CntInitVal);
1751 (cast<Instruction>(NewCount))->setDebugLoc(DL);
1752 }
1753 }
1754
1755 // Step 2: Replace the precondition from "if (x == 0) goto loop-exit" to
1756 // "if (NewCount == 0) loop-exit". Without this change, the intrinsic
1757 // function would be partial dead code, and downstream passes will drag
1758 // it back from the precondition block to the preheader.
1759 {
1760 ICmpInst *PreCond = cast<ICmpInst>(PreCondBr->getCondition());
1761
1762 Value *Opnd0 = PopCntZext;
1763 Value *Opnd1 = ConstantInt::get(PopCntZext->getType(), 0);
1764 if (PreCond->getOperand(0) != Var)
1765 std::swap(Opnd0, Opnd1);
1766
1767 ICmpInst *NewPreCond = cast<ICmpInst>(
1768 Builder.CreateICmp(PreCond->getPredicate(), Opnd0, Opnd1));
1769 PreCondBr->setCondition(NewPreCond);
1770
1771 RecursivelyDeleteTriviallyDeadInstructions(PreCond, TLI);
1772 }
1773
1774 // Step 3: Note that the population count is exactly the trip count of the
1775 // loop in question, which enable us to convert the loop from noncountable
1776 // loop into a countable one. The benefit is twofold:
1777 //
1778 // - If the loop only counts population, the entire loop becomes dead after
1779 // the transformation. It is a lot easier to prove a countable loop dead
1780 // than to prove a noncountable one. (In some C dialects, an infinite loop
1781 // isn't dead even if it computes nothing useful. In general, DCE needs
1782 // to prove a noncountable loop finite before safely delete it.)
1783 //
1784 // - If the loop also performs something else, it remains alive.
1785 // Since it is transformed to countable form, it can be aggressively
1786 // optimized by some optimizations which are in general not applicable
1787 // to a noncountable loop.
1788 //
1789 // After this step, this loop (conceptually) would look like following:
1790 // newcnt = __builtin_ctpop(x);
1791 // t = newcnt;
1792 // if (x)
1793 // do { cnt++; x &= x-1; t--) } while (t > 0);
1794 BasicBlock *Body = *(CurLoop->block_begin());
1795 {
1796 auto *LbBr = cast<BranchInst>(Body->getTerminator());
1797 ICmpInst *LbCond = cast<ICmpInst>(LbBr->getCondition());
1798 Type *Ty = TripCnt->getType();
1799
1800 PHINode *TcPhi = PHINode::Create(Ty, 2, "tcphi", &Body->front());
1801
1802 Builder.SetInsertPoint(LbCond);
1803 Instruction *TcDec = cast<Instruction>(
1804 Builder.CreateSub(TcPhi, ConstantInt::get(Ty, 1),
1805 "tcdec", false, true));
1806
1807 TcPhi->addIncoming(TripCnt, PreHead);
1808 TcPhi->addIncoming(TcDec, Body);
1809
1810 CmpInst::Predicate Pred =
1811 (LbBr->getSuccessor(0) == Body) ? CmpInst::ICMP_UGT : CmpInst::ICMP_SLE;
1812 LbCond->setPredicate(Pred);
1813 LbCond->setOperand(0, TcDec);
1814 LbCond->setOperand(1, ConstantInt::get(Ty, 0));
1815 }
1816
1817 // Step 4: All the references to the original population counter outside
1818 // the loop are replaced with the NewCount -- the value returned from
1819 // __builtin_ctpop().
1820 CntInst->replaceUsesOutsideBlock(NewCount, Body);
1821
1822 // step 5: Forget the "non-computable" trip-count SCEV associated with the
1823 // loop. The loop would otherwise not be deleted even if it becomes empty.
1824 SE->forgetLoop(CurLoop);
1825}