Bug Summary

File:llvm/lib/Transforms/Scalar/LICM.cpp
Warning:line 1020, column 22
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 LICM.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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/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/local/include -internal-isystem /usr/lib/llvm-11/lib/clang/11.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++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c++ /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp
1//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
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 performs loop invariant code motion, attempting to remove as much
10// code from the body of a loop as possible. It does this by either hoisting
11// code into the preheader block, or by sinking code to the exit blocks if it is
12// safe. This pass also promotes must-aliased memory locations in the loop to
13// live in registers, thus hoisting and sinking "invariant" loads and stores.
14//
15// This pass uses alias analysis for two purposes:
16//
17// 1. Moving loop invariant loads and calls out of loops. If we can determine
18// that a load or call inside of a loop never aliases anything stored to,
19// we can hoist it or sink it like any other instruction.
20// 2. Scalar Promotion of Memory - If there is a store instruction inside of
21// the loop, we try to move the store to happen AFTER the loop instead of
22// inside of the loop. This can only happen if a few conditions are true:
23// A. The pointer stored through is loop invariant
24// B. There are no stores or loads in the loop which _may_ alias the
25// pointer. There are no calls in the loop which mod/ref the pointer.
26// If these conditions are true, we can promote the loads and stores in the
27// loop of the pointer to use a temporary alloca'd variable. We then use
28// the SSAUpdater to construct the appropriate SSA form for the value.
29//
30//===----------------------------------------------------------------------===//
31
32#include "llvm/Transforms/Scalar/LICM.h"
33#include "llvm/ADT/SetOperations.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/Analysis/AliasAnalysis.h"
36#include "llvm/Analysis/AliasSetTracker.h"
37#include "llvm/Analysis/BasicAliasAnalysis.h"
38#include "llvm/Analysis/CaptureTracking.h"
39#include "llvm/Analysis/ConstantFolding.h"
40#include "llvm/Analysis/GlobalsModRef.h"
41#include "llvm/Analysis/GuardUtils.h"
42#include "llvm/Analysis/Loads.h"
43#include "llvm/Analysis/LoopInfo.h"
44#include "llvm/Analysis/LoopIterator.h"
45#include "llvm/Analysis/LoopPass.h"
46#include "llvm/Analysis/MemoryBuiltins.h"
47#include "llvm/Analysis/MemorySSA.h"
48#include "llvm/Analysis/MemorySSAUpdater.h"
49#include "llvm/Analysis/OptimizationRemarkEmitter.h"
50#include "llvm/Analysis/ScalarEvolution.h"
51#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
52#include "llvm/Analysis/TargetLibraryInfo.h"
53#include "llvm/Analysis/ValueTracking.h"
54#include "llvm/IR/CFG.h"
55#include "llvm/IR/Constants.h"
56#include "llvm/IR/DataLayout.h"
57#include "llvm/IR/DebugInfoMetadata.h"
58#include "llvm/IR/DerivedTypes.h"
59#include "llvm/IR/Dominators.h"
60#include "llvm/IR/Instructions.h"
61#include "llvm/IR/IntrinsicInst.h"
62#include "llvm/IR/LLVMContext.h"
63#include "llvm/IR/Metadata.h"
64#include "llvm/IR/PatternMatch.h"
65#include "llvm/IR/PredIteratorCache.h"
66#include "llvm/InitializePasses.h"
67#include "llvm/Support/CommandLine.h"
68#include "llvm/Support/Debug.h"
69#include "llvm/Support/raw_ostream.h"
70#include "llvm/Transforms/Scalar.h"
71#include "llvm/Transforms/Scalar/LoopPassManager.h"
72#include "llvm/Transforms/Utils/BasicBlockUtils.h"
73#include "llvm/Transforms/Utils/Local.h"
74#include "llvm/Transforms/Utils/LoopUtils.h"
75#include "llvm/Transforms/Utils/SSAUpdater.h"
76#include <algorithm>
77#include <utility>
78using namespace llvm;
79
80#define DEBUG_TYPE"licm" "licm"
81
82STATISTIC(NumCreatedBlocks, "Number of blocks created")static llvm::Statistic NumCreatedBlocks = {"licm", "NumCreatedBlocks"
, "Number of blocks created"}
;
83STATISTIC(NumClonedBranches, "Number of branches cloned")static llvm::Statistic NumClonedBranches = {"licm", "NumClonedBranches"
, "Number of branches cloned"}
;
84STATISTIC(NumSunk, "Number of instructions sunk out of loop")static llvm::Statistic NumSunk = {"licm", "NumSunk", "Number of instructions sunk out of loop"
}
;
85STATISTIC(NumHoisted, "Number of instructions hoisted out of loop")static llvm::Statistic NumHoisted = {"licm", "NumHoisted", "Number of instructions hoisted out of loop"
}
;
86STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk")static llvm::Statistic NumMovedLoads = {"licm", "NumMovedLoads"
, "Number of load insts hoisted or sunk"}
;
87STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk")static llvm::Statistic NumMovedCalls = {"licm", "NumMovedCalls"
, "Number of call insts hoisted or sunk"}
;
88STATISTIC(NumPromoted, "Number of memory locations promoted to registers")static llvm::Statistic NumPromoted = {"licm", "NumPromoted", "Number of memory locations promoted to registers"
}
;
89
90/// Memory promotion is enabled by default.
91static cl::opt<bool>
92 DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
93 cl::desc("Disable memory promotion in LICM pass"));
94
95static cl::opt<bool> ControlFlowHoisting(
96 "licm-control-flow-hoisting", cl::Hidden, cl::init(false),
97 cl::desc("Enable control flow (and PHI) hoisting in LICM"));
98
99static cl::opt<uint32_t> MaxNumUsesTraversed(
100 "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
101 cl::desc("Max num uses visited for identifying load "
102 "invariance in loop using invariant start (default = 8)"));
103
104// Default value of zero implies we use the regular alias set tracker mechanism
105// instead of the cross product using AA to identify aliasing of the memory
106// location we are interested in.
107static cl::opt<int>
108LICMN2Theshold("licm-n2-threshold", cl::Hidden, cl::init(0),
109 cl::desc("How many instruction to cross product using AA"));
110
111// Experimental option to allow imprecision in LICM in pathological cases, in
112// exchange for faster compile. This is to be removed if MemorySSA starts to
113// address the same issue. This flag applies only when LICM uses MemorySSA
114// instead on AliasSetTracker. LICM calls MemorySSAWalker's
115// getClobberingMemoryAccess, up to the value of the Cap, getting perfect
116// accuracy. Afterwards, LICM will call into MemorySSA's getDefiningAccess,
117// which may not be precise, since optimizeUses is capped. The result is
118// correct, but we may not get as "far up" as possible to get which access is
119// clobbering the one queried.
120cl::opt<unsigned> llvm::SetLicmMssaOptCap(
121 "licm-mssa-optimization-cap", cl::init(100), cl::Hidden,
122 cl::desc("Enable imprecision in LICM in pathological cases, in exchange "
123 "for faster compile. Caps the MemorySSA clobbering calls."));
124
125// Experimentally, memory promotion carries less importance than sinking and
126// hoisting. Limit when we do promotion when using MemorySSA, in order to save
127// compile time.
128cl::opt<unsigned> llvm::SetLicmMssaNoAccForPromotionCap(
129 "licm-mssa-max-acc-promotion", cl::init(250), cl::Hidden,
130 cl::desc("[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
131 "effect. When MSSA in LICM is enabled, then this is the maximum "
132 "number of accesses allowed to be present in a loop in order to "
133 "enable memory promotion."));
134
135static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
136static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
137 const LoopSafetyInfo *SafetyInfo,
138 TargetTransformInfo *TTI, bool &FreeInLoop);
139static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
140 BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
141 MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
142 OptimizationRemarkEmitter *ORE);
143static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
144 const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
145 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE);
146static bool isSafeToExecuteUnconditionally(Instruction &Inst,
147 const DominatorTree *DT,
148 const Loop *CurLoop,
149 const LoopSafetyInfo *SafetyInfo,
150 OptimizationRemarkEmitter *ORE,
151 const Instruction *CtxI = nullptr);
152static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
153 AliasSetTracker *CurAST, Loop *CurLoop,
154 AliasAnalysis *AA);
155static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
156 Loop *CurLoop,
157 SinkAndHoistLICMFlags &Flags);
158static Instruction *cloneInstructionInExitBlock(
159 Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
160 const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU);
161
162static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
163 AliasSetTracker *AST, MemorySSAUpdater *MSSAU);
164
165static void moveInstructionBefore(Instruction &I, Instruction &Dest,
166 ICFLoopSafetyInfo &SafetyInfo,
167 MemorySSAUpdater *MSSAU, ScalarEvolution *SE);
168
169namespace {
170struct LoopInvariantCodeMotion {
171 bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
172 TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
173 ScalarEvolution *SE, MemorySSA *MSSA,
174 OptimizationRemarkEmitter *ORE);
175
176 LoopInvariantCodeMotion(unsigned LicmMssaOptCap,
177 unsigned LicmMssaNoAccForPromotionCap)
178 : LicmMssaOptCap(LicmMssaOptCap),
179 LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap) {}
180
181private:
182 unsigned LicmMssaOptCap;
183 unsigned LicmMssaNoAccForPromotionCap;
184
185 std::unique_ptr<AliasSetTracker>
186 collectAliasInfoForLoop(Loop *L, LoopInfo *LI, AliasAnalysis *AA);
187 std::unique_ptr<AliasSetTracker>
188 collectAliasInfoForLoopWithMSSA(Loop *L, AliasAnalysis *AA,
189 MemorySSAUpdater *MSSAU);
190};
191
192struct LegacyLICMPass : public LoopPass {
193 static char ID; // Pass identification, replacement for typeid
194 LegacyLICMPass(
195 unsigned LicmMssaOptCap = SetLicmMssaOptCap,
196 unsigned LicmMssaNoAccForPromotionCap = SetLicmMssaNoAccForPromotionCap)
197 : LoopPass(ID), LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap) {
198 initializeLegacyLICMPassPass(*PassRegistry::getPassRegistry());
199 }
200
201 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
202 if (skipLoop(L))
203 return false;
204
205 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
206 MemorySSA *MSSA = EnableMSSALoopDependency
207 ? (&getAnalysis<MemorySSAWrapperPass>().getMSSA())
208 : nullptr;
209 // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
210 // pass. Function analyses need to be preserved across loop transformations
211 // but ORE cannot be preserved (see comment before the pass definition).
212 OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
213 return LICM.runOnLoop(L,
214 &getAnalysis<AAResultsWrapperPass>().getAAResults(),
215 &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
216 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
217 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
218 *L->getHeader()->getParent()),
219 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
220 *L->getHeader()->getParent()),
221 SE ? &SE->getSE() : nullptr, MSSA, &ORE);
222 }
223
224 /// This transformation requires natural loop information & requires that
225 /// loop preheaders be inserted into the CFG...
226 ///
227 void getAnalysisUsage(AnalysisUsage &AU) const override {
228 AU.addPreserved<DominatorTreeWrapperPass>();
229 AU.addPreserved<LoopInfoWrapperPass>();
230 AU.addRequired<TargetLibraryInfoWrapperPass>();
231 if (EnableMSSALoopDependency) {
232 AU.addRequired<MemorySSAWrapperPass>();
233 AU.addPreserved<MemorySSAWrapperPass>();
234 }
235 AU.addRequired<TargetTransformInfoWrapperPass>();
236 getLoopAnalysisUsage(AU);
237 }
238
239private:
240 LoopInvariantCodeMotion LICM;
241};
242} // namespace
243
244PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM,
245 LoopStandardAnalysisResults &AR, LPMUpdater &) {
246 // For the new PM, we also can't use OptimizationRemarkEmitter as an analysis
247 // pass. Function analyses need to be preserved across loop transformations
248 // but ORE cannot be preserved (see comment before the pass definition).
249 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
250
251 LoopInvariantCodeMotion LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap);
252 if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.TTI, &AR.SE,
253 AR.MSSA, &ORE))
254 return PreservedAnalyses::all();
255
256 auto PA = getLoopPassPreservedAnalyses();
257
258 PA.preserve<DominatorTreeAnalysis>();
259 PA.preserve<LoopAnalysis>();
260 if (AR.MSSA)
261 PA.preserve<MemorySSAAnalysis>();
262
263 return PA;
264}
265
266char LegacyLICMPass::ID = 0;
267INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",static void *initializeLegacyLICMPassPassOnce(PassRegistry &
Registry) {
268 false, false)static void *initializeLegacyLICMPassPassOnce(PassRegistry &
Registry) {
269INITIALIZE_PASS_DEPENDENCY(LoopPass)initializeLoopPassPass(Registry);
270INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
271INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
272INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry);
273INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,PassInfo *PI = new PassInfo( "Loop Invariant Code Motion", "licm"
, &LegacyLICMPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LegacyLICMPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLegacyLICMPassPassFlag
; void llvm::initializeLegacyLICMPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeLegacyLICMPassPassFlag, initializeLegacyLICMPassPassOnce
, std::ref(Registry)); }
274 false)PassInfo *PI = new PassInfo( "Loop Invariant Code Motion", "licm"
, &LegacyLICMPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LegacyLICMPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLegacyLICMPassPassFlag
; void llvm::initializeLegacyLICMPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeLegacyLICMPassPassFlag, initializeLegacyLICMPassPassOnce
, std::ref(Registry)); }
275
276Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
277Pass *llvm::createLICMPass(unsigned LicmMssaOptCap,
278 unsigned LicmMssaNoAccForPromotionCap) {
279 return new LegacyLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap);
280}
281
282/// Hoist expressions out of the specified loop. Note, alias info for inner
283/// loop is not preserved so it is not a good idea to run LICM multiple
284/// times on one loop.
285bool LoopInvariantCodeMotion::runOnLoop(
286 Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
287 TargetLibraryInfo *TLI, TargetTransformInfo *TTI, ScalarEvolution *SE,
288 MemorySSA *MSSA, OptimizationRemarkEmitter *ORE) {
289 bool Changed = false;
290
291 assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.")((L->isLCSSAForm(*DT) && "Loop is not in LCSSA form."
) ? static_cast<void> (0) : __assert_fail ("L->isLCSSAForm(*DT) && \"Loop is not in LCSSA form.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 291, __PRETTY_FUNCTION__))
;
292
293 // If this loop has metadata indicating that LICM is not to be performed then
294 // just exit.
295 if (hasDisableLICMTransformsHint(L)) {
296 return false;
297 }
298
299 std::unique_ptr<AliasSetTracker> CurAST;
300 std::unique_ptr<MemorySSAUpdater> MSSAU;
301 bool NoOfMemAccTooLarge = false;
302 unsigned LicmMssaOptCounter = 0;
303
304 if (!MSSA) {
305 LLVM_DEBUG(dbgs() << "LICM: Using Alias Set Tracker.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM: Using Alias Set Tracker.\n"
; } } while (false)
;
306 CurAST = collectAliasInfoForLoop(L, LI, AA);
307 } else {
308 LLVM_DEBUG(dbgs() << "LICM: Using MemorySSA.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM: Using MemorySSA.\n"; } } while
(false)
;
309 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
310
311 unsigned AccessCapCount = 0;
312 for (auto *BB : L->getBlocks()) {
313 if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
314 for (const auto &MA : *Accesses) {
315 (void)MA;
316 AccessCapCount++;
317 if (AccessCapCount > LicmMssaNoAccForPromotionCap) {
318 NoOfMemAccTooLarge = true;
319 break;
320 }
321 }
322 }
323 if (NoOfMemAccTooLarge)
324 break;
325 }
326 }
327
328 // Get the preheader block to move instructions into...
329 BasicBlock *Preheader = L->getLoopPreheader();
330
331 // Compute loop safety information.
332 ICFLoopSafetyInfo SafetyInfo(DT);
333 SafetyInfo.computeLoopSafetyInfo(L);
334
335 // We want to visit all of the instructions in this loop... that are not parts
336 // of our subloops (they have already had their invariants hoisted out of
337 // their loop, into this loop, so there is no need to process the BODIES of
338 // the subloops).
339 //
340 // Traverse the body of the loop in depth first order on the dominator tree so
341 // that we are guaranteed to see definitions before we see uses. This allows
342 // us to sink instructions in one pass, without iteration. After sinking
343 // instructions, we perform another pass to hoist them out of the loop.
344 SinkAndHoistLICMFlags Flags = {NoOfMemAccTooLarge, LicmMssaOptCounter,
345 LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
346 /*IsSink=*/true};
347 if (L->hasDedicatedExits())
348 Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L,
349 CurAST.get(), MSSAU.get(), &SafetyInfo, Flags, ORE);
350 Flags.IsSink = false;
351 if (Preheader)
352 Changed |=
353 hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
354 CurAST.get(), MSSAU.get(), SE, &SafetyInfo, Flags, ORE);
355
356 // Now that all loop invariants have been removed from the loop, promote any
357 // memory references to scalars that we can.
358 // Don't sink stores from loops without dedicated block exits. Exits
359 // containing indirect branches are not transformed by loop simplify,
360 // make sure we catch that. An additional load may be generated in the
361 // preheader for SSA updater, so also avoid sinking when no preheader
362 // is available.
363 if (!DisablePromotion && Preheader && L->hasDedicatedExits() &&
364 !NoOfMemAccTooLarge) {
365 // Figure out the loop exits and their insertion points
366 SmallVector<BasicBlock *, 8> ExitBlocks;
367 L->getUniqueExitBlocks(ExitBlocks);
368
369 // We can't insert into a catchswitch.
370 bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
371 return isa<CatchSwitchInst>(Exit->getTerminator());
372 });
373
374 if (!HasCatchSwitch) {
375 SmallVector<Instruction *, 8> InsertPts;
376 SmallVector<MemoryAccess *, 8> MSSAInsertPts;
377 InsertPts.reserve(ExitBlocks.size());
378 if (MSSAU)
379 MSSAInsertPts.reserve(ExitBlocks.size());
380 for (BasicBlock *ExitBlock : ExitBlocks) {
381 InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
382 if (MSSAU)
383 MSSAInsertPts.push_back(nullptr);
384 }
385
386 PredIteratorCache PIC;
387
388 bool Promoted = false;
389
390 // Build an AST using MSSA.
391 if (!CurAST.get())
392 CurAST = collectAliasInfoForLoopWithMSSA(L, AA, MSSAU.get());
393
394 // Loop over all of the alias sets in the tracker object.
395 for (AliasSet &AS : *CurAST) {
396 // We can promote this alias set if it has a store, if it is a "Must"
397 // alias set, if the pointer is loop invariant, and if we are not
398 // eliminating any volatile loads or stores.
399 if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
400 !L->isLoopInvariant(AS.begin()->getValue()))
401 continue;
402
403 assert(((!AS.empty() && "Must alias set should have at least one pointer element in it!"
) ? static_cast<void> (0) : __assert_fail ("!AS.empty() && \"Must alias set should have at least one pointer element in it!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 405, __PRETTY_FUNCTION__))
404 !AS.empty() &&((!AS.empty() && "Must alias set should have at least one pointer element in it!"
) ? static_cast<void> (0) : __assert_fail ("!AS.empty() && \"Must alias set should have at least one pointer element in it!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 405, __PRETTY_FUNCTION__))
405 "Must alias set should have at least one pointer element in it!")((!AS.empty() && "Must alias set should have at least one pointer element in it!"
) ? static_cast<void> (0) : __assert_fail ("!AS.empty() && \"Must alias set should have at least one pointer element in it!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 405, __PRETTY_FUNCTION__))
;
406
407 SmallSetVector<Value *, 8> PointerMustAliases;
408 for (const auto &ASI : AS)
409 PointerMustAliases.insert(ASI.getValue());
410
411 Promoted |= promoteLoopAccessesToScalars(
412 PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts, PIC, LI,
413 DT, TLI, L, CurAST.get(), MSSAU.get(), &SafetyInfo, ORE);
414 }
415
416 // Once we have promoted values across the loop body we have to
417 // recursively reform LCSSA as any nested loop may now have values defined
418 // within the loop used in the outer loop.
419 // FIXME: This is really heavy handed. It would be a bit better to use an
420 // SSAUpdater strategy during promotion that was LCSSA aware and reformed
421 // it as it went.
422 if (Promoted)
423 formLCSSARecursively(*L, *DT, LI, SE);
424
425 Changed |= Promoted;
426 }
427 }
428
429 // Check that neither this loop nor its parent have had LCSSA broken. LICM is
430 // specifically moving instructions across the loop boundary and so it is
431 // especially in need of sanity checking here.
432 assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!")((L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!"
) ? static_cast<void> (0) : __assert_fail ("L->isLCSSAForm(*DT) && \"Loop not left in LCSSA form after LICM!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 432, __PRETTY_FUNCTION__))
;
433 assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&(((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm
(*DT)) && "Parent loop not left in LCSSA form after LICM!"
) ? static_cast<void> (0) : __assert_fail ("(!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) && \"Parent loop not left in LCSSA form after LICM!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 434, __PRETTY_FUNCTION__))
434 "Parent loop not left in LCSSA form after LICM!")(((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm
(*DT)) && "Parent loop not left in LCSSA form after LICM!"
) ? static_cast<void> (0) : __assert_fail ("(!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) && \"Parent loop not left in LCSSA form after LICM!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 434, __PRETTY_FUNCTION__))
;
435
436 if (MSSAU.get() && VerifyMemorySSA)
437 MSSAU->getMemorySSA()->verifyMemorySSA();
438
439 if (Changed && SE)
440 SE->forgetLoopDispositions(L);
441 return Changed;
442}
443
444/// Walk the specified region of the CFG (defined by all blocks dominated by
445/// the specified block, and that are in the current loop) in reverse depth
446/// first order w.r.t the DominatorTree. This allows us to visit uses before
447/// definitions, allowing us to sink a loop body in one pass without iteration.
448///
449bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
450 DominatorTree *DT, TargetLibraryInfo *TLI,
451 TargetTransformInfo *TTI, Loop *CurLoop,
452 AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
453 ICFLoopSafetyInfo *SafetyInfo,
454 SinkAndHoistLICMFlags &Flags,
455 OptimizationRemarkEmitter *ORE) {
456
457 // Verify inputs.
458 assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to sinkRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to sinkRegion.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 460, __PRETTY_FUNCTION__))
459 CurLoop != nullptr && SafetyInfo != nullptr &&((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to sinkRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to sinkRegion.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 460, __PRETTY_FUNCTION__))
460 "Unexpected input to sinkRegion.")((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to sinkRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to sinkRegion.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 460, __PRETTY_FUNCTION__))
;
461 assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 462, __PRETTY_FUNCTION__))
462 "Either AliasSetTracker or MemorySSA should be initialized.")((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 462, __PRETTY_FUNCTION__))
;
463
464 // We want to visit children before parents. We will enque all the parents
465 // before their children in the worklist and process the worklist in reverse
466 // order.
467 SmallVector<DomTreeNode *, 16> Worklist = collectChildrenInLoop(N, CurLoop);
468
469 bool Changed = false;
470 for (DomTreeNode *DTN : reverse(Worklist)) {
471 BasicBlock *BB = DTN->getBlock();
472 // Only need to process the contents of this block if it is not part of a
473 // subloop (which would already have been processed).
474 if (inSubLoop(BB, CurLoop, LI))
475 continue;
476
477 for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
478 Instruction &I = *--II;
479
480 // If the instruction is dead, we would try to sink it because it isn't
481 // used in the loop, instead, just delete it.
482 if (isInstructionTriviallyDead(&I, TLI)) {
483 LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM deleting dead inst: " <<
I << '\n'; } } while (false)
;
484 salvageDebugInfo(I);
485 ++II;
486 eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
487 Changed = true;
488 continue;
489 }
490
491 // Check to see if we can sink this instruction to the exit blocks
492 // of the loop. We can do this if the all users of the instruction are
493 // outside of the loop. In this case, it doesn't even matter if the
494 // operands of the instruction are loop invariant.
495 //
496 bool FreeInLoop = false;
497 if (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
498 canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
499 ORE) &&
500 !I.mayHaveSideEffects()) {
501 if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
502 if (!FreeInLoop) {
503 ++II;
504 eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
505 }
506 Changed = true;
507 }
508 }
509 }
510 }
511 if (MSSAU && VerifyMemorySSA)
512 MSSAU->getMemorySSA()->verifyMemorySSA();
513 return Changed;
514}
515
516namespace {
517// This is a helper class for hoistRegion to make it able to hoist control flow
518// in order to be able to hoist phis. The way this works is that we initially
519// start hoisting to the loop preheader, and when we see a loop invariant branch
520// we make note of this. When we then come to hoist an instruction that's
521// conditional on such a branch we duplicate the branch and the relevant control
522// flow, then hoist the instruction into the block corresponding to its original
523// block in the duplicated control flow.
524class ControlFlowHoister {
525private:
526 // Information about the loop we are hoisting from
527 LoopInfo *LI;
528 DominatorTree *DT;
529 Loop *CurLoop;
530 MemorySSAUpdater *MSSAU;
531
532 // A map of blocks in the loop to the block their instructions will be hoisted
533 // to.
534 DenseMap<BasicBlock *, BasicBlock *> HoistDestinationMap;
535
536 // The branches that we can hoist, mapped to the block that marks a
537 // convergence point of their control flow.
538 DenseMap<BranchInst *, BasicBlock *> HoistableBranches;
539
540public:
541 ControlFlowHoister(LoopInfo *LI, DominatorTree *DT, Loop *CurLoop,
542 MemorySSAUpdater *MSSAU)
543 : LI(LI), DT(DT), CurLoop(CurLoop), MSSAU(MSSAU) {}
544
545 void registerPossiblyHoistableBranch(BranchInst *BI) {
546 // We can only hoist conditional branches with loop invariant operands.
547 if (!ControlFlowHoisting || !BI->isConditional() ||
548 !CurLoop->hasLoopInvariantOperands(BI))
549 return;
550
551 // The branch destinations need to be in the loop, and we don't gain
552 // anything by duplicating conditional branches with duplicate successors,
553 // as it's essentially the same as an unconditional branch.
554 BasicBlock *TrueDest = BI->getSuccessor(0);
555 BasicBlock *FalseDest = BI->getSuccessor(1);
556 if (!CurLoop->contains(TrueDest) || !CurLoop->contains(FalseDest) ||
557 TrueDest == FalseDest)
558 return;
559
560 // We can hoist BI if one branch destination is the successor of the other,
561 // or both have common successor which we check by seeing if the
562 // intersection of their successors is non-empty.
563 // TODO: This could be expanded to allowing branches where both ends
564 // eventually converge to a single block.
565 SmallPtrSet<BasicBlock *, 4> TrueDestSucc, FalseDestSucc;
566 TrueDestSucc.insert(succ_begin(TrueDest), succ_end(TrueDest));
567 FalseDestSucc.insert(succ_begin(FalseDest), succ_end(FalseDest));
568 BasicBlock *CommonSucc = nullptr;
569 if (TrueDestSucc.count(FalseDest)) {
570 CommonSucc = FalseDest;
571 } else if (FalseDestSucc.count(TrueDest)) {
572 CommonSucc = TrueDest;
573 } else {
574 set_intersect(TrueDestSucc, FalseDestSucc);
575 // If there's one common successor use that.
576 if (TrueDestSucc.size() == 1)
577 CommonSucc = *TrueDestSucc.begin();
578 // If there's more than one pick whichever appears first in the block list
579 // (we can't use the value returned by TrueDestSucc.begin() as it's
580 // unpredicatable which element gets returned).
581 else if (!TrueDestSucc.empty()) {
582 Function *F = TrueDest->getParent();
583 auto IsSucc = [&](BasicBlock &BB) { return TrueDestSucc.count(&BB); };
584 auto It = std::find_if(F->begin(), F->end(), IsSucc);
585 assert(It != F->end() && "Could not find successor in function")((It != F->end() && "Could not find successor in function"
) ? static_cast<void> (0) : __assert_fail ("It != F->end() && \"Could not find successor in function\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 585, __PRETTY_FUNCTION__))
;
586 CommonSucc = &*It;
587 }
588 }
589 // The common successor has to be dominated by the branch, as otherwise
590 // there will be some other path to the successor that will not be
591 // controlled by this branch so any phi we hoist would be controlled by the
592 // wrong condition. This also takes care of avoiding hoisting of loop back
593 // edges.
594 // TODO: In some cases this could be relaxed if the successor is dominated
595 // by another block that's been hoisted and we can guarantee that the
596 // control flow has been replicated exactly.
597 if (CommonSucc && DT->dominates(BI, CommonSucc))
598 HoistableBranches[BI] = CommonSucc;
599 }
600
601 bool canHoistPHI(PHINode *PN) {
602 // The phi must have loop invariant operands.
603 if (!ControlFlowHoisting || !CurLoop->hasLoopInvariantOperands(PN))
604 return false;
605 // We can hoist phis if the block they are in is the target of hoistable
606 // branches which cover all of the predecessors of the block.
607 SmallPtrSet<BasicBlock *, 8> PredecessorBlocks;
608 BasicBlock *BB = PN->getParent();
609 for (BasicBlock *PredBB : predecessors(BB))
610 PredecessorBlocks.insert(PredBB);
611 // If we have less predecessor blocks than predecessors then the phi will
612 // have more than one incoming value for the same block which we can't
613 // handle.
614 // TODO: This could be handled be erasing some of the duplicate incoming
615 // values.
616 if (PredecessorBlocks.size() != pred_size(BB))
617 return false;
618 for (auto &Pair : HoistableBranches) {
619 if (Pair.second == BB) {
620 // Which blocks are predecessors via this branch depends on if the
621 // branch is triangle-like or diamond-like.
622 if (Pair.first->getSuccessor(0) == BB) {
623 PredecessorBlocks.erase(Pair.first->getParent());
624 PredecessorBlocks.erase(Pair.first->getSuccessor(1));
625 } else if (Pair.first->getSuccessor(1) == BB) {
626 PredecessorBlocks.erase(Pair.first->getParent());
627 PredecessorBlocks.erase(Pair.first->getSuccessor(0));
628 } else {
629 PredecessorBlocks.erase(Pair.first->getSuccessor(0));
630 PredecessorBlocks.erase(Pair.first->getSuccessor(1));
631 }
632 }
633 }
634 // PredecessorBlocks will now be empty if for every predecessor of BB we
635 // found a hoistable branch source.
636 return PredecessorBlocks.empty();
637 }
638
639 BasicBlock *getOrCreateHoistedBlock(BasicBlock *BB) {
640 if (!ControlFlowHoisting)
641 return CurLoop->getLoopPreheader();
642 // If BB has already been hoisted, return that
643 if (HoistDestinationMap.count(BB))
644 return HoistDestinationMap[BB];
645
646 // Check if this block is conditional based on a pending branch
647 auto HasBBAsSuccessor =
648 [&](DenseMap<BranchInst *, BasicBlock *>::value_type &Pair) {
649 return BB != Pair.second && (Pair.first->getSuccessor(0) == BB ||
650 Pair.first->getSuccessor(1) == BB);
651 };
652 auto It = std::find_if(HoistableBranches.begin(), HoistableBranches.end(),
653 HasBBAsSuccessor);
654
655 // If not involved in a pending branch, hoist to preheader
656 BasicBlock *InitialPreheader = CurLoop->getLoopPreheader();
657 if (It == HoistableBranches.end()) {
658 LLVM_DEBUG(dbgs() << "LICM using " << InitialPreheader->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM using " << InitialPreheader
->getName() << " as hoist destination for " <<
BB->getName() << "\n"; } } while (false)
659 << " as hoist destination for " << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM using " << InitialPreheader
->getName() << " as hoist destination for " <<
BB->getName() << "\n"; } } while (false)
660 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM using " << InitialPreheader
->getName() << " as hoist destination for " <<
BB->getName() << "\n"; } } while (false)
;
661 HoistDestinationMap[BB] = InitialPreheader;
662 return InitialPreheader;
663 }
664 BranchInst *BI = It->first;
665 assert(std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) ==((std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor
) == HoistableBranches.end() && "BB is expected to be the target of at most one branch"
) ? static_cast<void> (0) : __assert_fail ("std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) == HoistableBranches.end() && \"BB is expected to be the target of at most one branch\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 667, __PRETTY_FUNCTION__))
666 HoistableBranches.end() &&((std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor
) == HoistableBranches.end() && "BB is expected to be the target of at most one branch"
) ? static_cast<void> (0) : __assert_fail ("std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) == HoistableBranches.end() && \"BB is expected to be the target of at most one branch\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 667, __PRETTY_FUNCTION__))
667 "BB is expected to be the target of at most one branch")((std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor
) == HoistableBranches.end() && "BB is expected to be the target of at most one branch"
) ? static_cast<void> (0) : __assert_fail ("std::find_if(++It, HoistableBranches.end(), HasBBAsSuccessor) == HoistableBranches.end() && \"BB is expected to be the target of at most one branch\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 667, __PRETTY_FUNCTION__))
;
668
669 LLVMContext &C = BB->getContext();
670 BasicBlock *TrueDest = BI->getSuccessor(0);
671 BasicBlock *FalseDest = BI->getSuccessor(1);
672 BasicBlock *CommonSucc = HoistableBranches[BI];
673 BasicBlock *HoistTarget = getOrCreateHoistedBlock(BI->getParent());
674
675 // Create hoisted versions of blocks that currently don't have them
676 auto CreateHoistedBlock = [&](BasicBlock *Orig) {
677 if (HoistDestinationMap.count(Orig))
678 return HoistDestinationMap[Orig];
679 BasicBlock *New =
680 BasicBlock::Create(C, Orig->getName() + ".licm", Orig->getParent());
681 HoistDestinationMap[Orig] = New;
682 DT->addNewBlock(New, HoistTarget);
683 if (CurLoop->getParentLoop())
684 CurLoop->getParentLoop()->addBasicBlockToLoop(New, *LI);
685 ++NumCreatedBlocks;
686 LLVM_DEBUG(dbgs() << "LICM created " << New->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM created " << New->
getName() << " as hoist destination for " << Orig
->getName() << "\n"; } } while (false)
687 << " as hoist destination for " << Orig->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM created " << New->
getName() << " as hoist destination for " << Orig
->getName() << "\n"; } } while (false)
688 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM created " << New->
getName() << " as hoist destination for " << Orig
->getName() << "\n"; } } while (false)
;
689 return New;
690 };
691 BasicBlock *HoistTrueDest = CreateHoistedBlock(TrueDest);
692 BasicBlock *HoistFalseDest = CreateHoistedBlock(FalseDest);
693 BasicBlock *HoistCommonSucc = CreateHoistedBlock(CommonSucc);
694
695 // Link up these blocks with branches.
696 if (!HoistCommonSucc->getTerminator()) {
697 // The new common successor we've generated will branch to whatever that
698 // hoist target branched to.
699 BasicBlock *TargetSucc = HoistTarget->getSingleSuccessor();
700 assert(TargetSucc && "Expected hoist target to have a single successor")((TargetSucc && "Expected hoist target to have a single successor"
) ? static_cast<void> (0) : __assert_fail ("TargetSucc && \"Expected hoist target to have a single successor\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 700, __PRETTY_FUNCTION__))
;
701 HoistCommonSucc->moveBefore(TargetSucc);
702 BranchInst::Create(TargetSucc, HoistCommonSucc);
703 }
704 if (!HoistTrueDest->getTerminator()) {
705 HoistTrueDest->moveBefore(HoistCommonSucc);
706 BranchInst::Create(HoistCommonSucc, HoistTrueDest);
707 }
708 if (!HoistFalseDest->getTerminator()) {
709 HoistFalseDest->moveBefore(HoistCommonSucc);
710 BranchInst::Create(HoistCommonSucc, HoistFalseDest);
711 }
712
713 // If BI is being cloned to what was originally the preheader then
714 // HoistCommonSucc will now be the new preheader.
715 if (HoistTarget == InitialPreheader) {
716 // Phis in the loop header now need to use the new preheader.
717 InitialPreheader->replaceSuccessorsPhiUsesWith(HoistCommonSucc);
718 if (MSSAU)
719 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
720 HoistTarget->getSingleSuccessor(), HoistCommonSucc, {HoistTarget});
721 // The new preheader dominates the loop header.
722 DomTreeNode *PreheaderNode = DT->getNode(HoistCommonSucc);
723 DomTreeNode *HeaderNode = DT->getNode(CurLoop->getHeader());
724 DT->changeImmediateDominator(HeaderNode, PreheaderNode);
725 // The preheader hoist destination is now the new preheader, with the
726 // exception of the hoist destination of this branch.
727 for (auto &Pair : HoistDestinationMap)
728 if (Pair.second == InitialPreheader && Pair.first != BI->getParent())
729 Pair.second = HoistCommonSucc;
730 }
731
732 // Now finally clone BI.
733 ReplaceInstWithInst(
734 HoistTarget->getTerminator(),
735 BranchInst::Create(HoistTrueDest, HoistFalseDest, BI->getCondition()));
736 ++NumClonedBranches;
737
738 assert(CurLoop->getLoopPreheader() &&((CurLoop->getLoopPreheader() && "Hoisting blocks should not have destroyed preheader"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->getLoopPreheader() && \"Hoisting blocks should not have destroyed preheader\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 739, __PRETTY_FUNCTION__))
739 "Hoisting blocks should not have destroyed preheader")((CurLoop->getLoopPreheader() && "Hoisting blocks should not have destroyed preheader"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->getLoopPreheader() && \"Hoisting blocks should not have destroyed preheader\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 739, __PRETTY_FUNCTION__))
;
740 return HoistDestinationMap[BB];
741 }
742};
743} // namespace
744
745/// Walk the specified region of the CFG (defined by all blocks dominated by
746/// the specified block, and that are in the current loop) in depth first
747/// order w.r.t the DominatorTree. This allows us to visit definitions before
748/// uses, allowing us to hoist a loop body in one pass without iteration.
749///
750bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
751 DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
752 AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
753 ScalarEvolution *SE, ICFLoopSafetyInfo *SafetyInfo,
754 SinkAndHoistLICMFlags &Flags,
755 OptimizationRemarkEmitter *ORE) {
756 // Verify inputs.
757 assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to hoistRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to hoistRegion.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 759, __PRETTY_FUNCTION__))
758 CurLoop != nullptr && SafetyInfo != nullptr &&((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to hoistRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to hoistRegion.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 759, __PRETTY_FUNCTION__))
759 "Unexpected input to hoistRegion.")((N != nullptr && AA != nullptr && LI != nullptr
&& DT != nullptr && CurLoop != nullptr &&
SafetyInfo != nullptr && "Unexpected input to hoistRegion."
) ? static_cast<void> (0) : __assert_fail ("N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && CurLoop != nullptr && SafetyInfo != nullptr && \"Unexpected input to hoistRegion.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 759, __PRETTY_FUNCTION__))
;
760 assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 761, __PRETTY_FUNCTION__))
761 "Either AliasSetTracker or MemorySSA should be initialized.")((((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."
) ? static_cast<void> (0) : __assert_fail ("((CurAST != nullptr) ^ (MSSAU != nullptr)) && \"Either AliasSetTracker or MemorySSA should be initialized.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 761, __PRETTY_FUNCTION__))
;
762
763 ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
764
765 // Keep track of instructions that have been hoisted, as they may need to be
766 // re-hoisted if they end up not dominating all of their uses.
767 SmallVector<Instruction *, 16> HoistedInstructions;
768
769 // For PHI hoisting to work we need to hoist blocks before their successors.
770 // We can do this by iterating through the blocks in the loop in reverse
771 // post-order.
772 LoopBlocksRPO Worklist(CurLoop);
773 Worklist.perform(LI);
774 bool Changed = false;
775 for (BasicBlock *BB : Worklist) {
776 // Only need to process the contents of this block if it is not part of a
777 // subloop (which would already have been processed).
778 if (inSubLoop(BB, CurLoop, LI))
779 continue;
780
781 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
782 Instruction &I = *II++;
783 // Try constant folding this instruction. If all the operands are
784 // constants, it is technically hoistable, but it would be better to
785 // just fold it.
786 if (Constant *C = ConstantFoldInstruction(
787 &I, I.getModule()->getDataLayout(), TLI)) {
788 LLVM_DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *Cdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM folding inst: " << I <<
" --> " << *C << '\n'; } } while (false)
789 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM folding inst: " << I <<
" --> " << *C << '\n'; } } while (false)
;
790 if (CurAST)
791 CurAST->copyValue(&I, C);
792 // FIXME MSSA: Such replacements may make accesses unoptimized (D51960).
793 I.replaceAllUsesWith(C);
794 if (isInstructionTriviallyDead(&I, TLI))
795 eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
796 Changed = true;
797 continue;
798 }
799
800 // Try hoisting the instruction out to the preheader. We can only do
801 // this if all of the operands of the instruction are loop invariant and
802 // if it is safe to hoist the instruction.
803 // TODO: It may be safe to hoist if we are hoisting to a conditional block
804 // and we have accurately duplicated the control flow from the loop header
805 // to that block.
806 if (CurLoop->hasLoopInvariantOperands(&I) &&
807 canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
808 ORE) &&
809 isSafeToExecuteUnconditionally(
810 I, DT, CurLoop, SafetyInfo, ORE,
811 CurLoop->getLoopPreheader()->getTerminator())) {
812 hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
813 MSSAU, SE, ORE);
814 HoistedInstructions.push_back(&I);
815 Changed = true;
816 continue;
817 }
818
819 // Attempt to remove floating point division out of the loop by
820 // converting it to a reciprocal multiplication.
821 if (I.getOpcode() == Instruction::FDiv && I.hasAllowReciprocal() &&
822 CurLoop->isLoopInvariant(I.getOperand(1))) {
823 auto Divisor = I.getOperand(1);
824 auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
825 auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
826 ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
827 SafetyInfo->insertInstructionTo(ReciprocalDivisor, I.getParent());
828 ReciprocalDivisor->insertBefore(&I);
829
830 auto Product =
831 BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
832 Product->setFastMathFlags(I.getFastMathFlags());
833 SafetyInfo->insertInstructionTo(Product, I.getParent());
834 Product->insertAfter(&I);
835 I.replaceAllUsesWith(Product);
836 eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
837
838 hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
839 SafetyInfo, MSSAU, SE, ORE);
840 HoistedInstructions.push_back(ReciprocalDivisor);
841 Changed = true;
842 continue;
843 }
844
845 auto IsInvariantStart = [&](Instruction &I) {
846 using namespace PatternMatch;
847 return I.use_empty() &&
848 match(&I, m_Intrinsic<Intrinsic::invariant_start>());
849 };
850 auto MustExecuteWithoutWritesBefore = [&](Instruction &I) {
851 return SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop) &&
852 SafetyInfo->doesNotWriteMemoryBefore(I, CurLoop);
853 };
854 if ((IsInvariantStart(I) || isGuard(&I)) &&
855 CurLoop->hasLoopInvariantOperands(&I) &&
856 MustExecuteWithoutWritesBefore(I)) {
857 hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
858 MSSAU, SE, ORE);
859 HoistedInstructions.push_back(&I);
860 Changed = true;
861 continue;
862 }
863
864 if (PHINode *PN = dyn_cast<PHINode>(&I)) {
865 if (CFH.canHoistPHI(PN)) {
866 // Redirect incoming blocks first to ensure that we create hoisted
867 // versions of those blocks before we hoist the phi.
868 for (unsigned int i = 0; i < PN->getNumIncomingValues(); ++i)
869 PN->setIncomingBlock(
870 i, CFH.getOrCreateHoistedBlock(PN->getIncomingBlock(i)));
871 hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
872 MSSAU, SE, ORE);
873 assert(DT->dominates(PN, BB) && "Conditional PHIs not expected")((DT->dominates(PN, BB) && "Conditional PHIs not expected"
) ? static_cast<void> (0) : __assert_fail ("DT->dominates(PN, BB) && \"Conditional PHIs not expected\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 873, __PRETTY_FUNCTION__))
;
874 Changed = true;
875 continue;
876 }
877 }
878
879 // Remember possibly hoistable branches so we can actually hoist them
880 // later if needed.
881 if (BranchInst *BI = dyn_cast<BranchInst>(&I))
882 CFH.registerPossiblyHoistableBranch(BI);
883 }
884 }
885
886 // If we hoisted instructions to a conditional block they may not dominate
887 // their uses that weren't hoisted (such as phis where some operands are not
888 // loop invariant). If so make them unconditional by moving them to their
889 // immediate dominator. We iterate through the instructions in reverse order
890 // which ensures that when we rehoist an instruction we rehoist its operands,
891 // and also keep track of where in the block we are rehoisting to to make sure
892 // that we rehoist instructions before the instructions that use them.
893 Instruction *HoistPoint = nullptr;
894 if (ControlFlowHoisting) {
895 for (Instruction *I : reverse(HoistedInstructions)) {
896 if (!llvm::all_of(I->uses(),
897 [&](Use &U) { return DT->dominates(I, U); })) {
898 BasicBlock *Dominator =
899 DT->getNode(I->getParent())->getIDom()->getBlock();
900 if (!HoistPoint || !DT->dominates(HoistPoint->getParent(), Dominator)) {
901 if (HoistPoint)
902 assert(DT->dominates(Dominator, HoistPoint->getParent()) &&((DT->dominates(Dominator, HoistPoint->getParent()) &&
"New hoist point expected to dominate old hoist point") ? static_cast
<void> (0) : __assert_fail ("DT->dominates(Dominator, HoistPoint->getParent()) && \"New hoist point expected to dominate old hoist point\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 903, __PRETTY_FUNCTION__))
903 "New hoist point expected to dominate old hoist point")((DT->dominates(Dominator, HoistPoint->getParent()) &&
"New hoist point expected to dominate old hoist point") ? static_cast
<void> (0) : __assert_fail ("DT->dominates(Dominator, HoistPoint->getParent()) && \"New hoist point expected to dominate old hoist point\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 903, __PRETTY_FUNCTION__))
;
904 HoistPoint = Dominator->getTerminator();
905 }
906 LLVM_DEBUG(dbgs() << "LICM rehoisting to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM rehoisting to " << HoistPoint
->getParent()->getName() << ": " << *I <<
"\n"; } } while (false)
907 << HoistPoint->getParent()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM rehoisting to " << HoistPoint
->getParent()->getName() << ": " << *I <<
"\n"; } } while (false)
908 << ": " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM rehoisting to " << HoistPoint
->getParent()->getName() << ": " << *I <<
"\n"; } } while (false)
;
909 moveInstructionBefore(*I, *HoistPoint, *SafetyInfo, MSSAU, SE);
910 HoistPoint = I;
911 Changed = true;
912 }
913 }
914 }
915 if (MSSAU && VerifyMemorySSA)
916 MSSAU->getMemorySSA()->verifyMemorySSA();
917
918 // Now that we've finished hoisting make sure that LI and DT are still
919 // valid.
920#ifdef EXPENSIVE_CHECKS
921 if (Changed) {
922 assert(DT->verify(DominatorTree::VerificationLevel::Fast) &&((DT->verify(DominatorTree::VerificationLevel::Fast) &&
"Dominator tree verification failed") ? static_cast<void>
(0) : __assert_fail ("DT->verify(DominatorTree::VerificationLevel::Fast) && \"Dominator tree verification failed\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 923, __PRETTY_FUNCTION__))
923 "Dominator tree verification failed")((DT->verify(DominatorTree::VerificationLevel::Fast) &&
"Dominator tree verification failed") ? static_cast<void>
(0) : __assert_fail ("DT->verify(DominatorTree::VerificationLevel::Fast) && \"Dominator tree verification failed\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 923, __PRETTY_FUNCTION__))
;
924 LI->verify(*DT);
925 }
926#endif
927
928 return Changed;
929}
930
931// Return true if LI is invariant within scope of the loop. LI is invariant if
932// CurLoop is dominated by an invariant.start representing the same memory
933// location and size as the memory location LI loads from, and also the
934// invariant.start has no uses.
935static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT,
936 Loop *CurLoop) {
937 Value *Addr = LI->getOperand(0);
938 const DataLayout &DL = LI->getModule()->getDataLayout();
939 const uint32_t LocSizeInBits = DL.getTypeSizeInBits(LI->getType());
940
941 // if the type is i8 addrspace(x)*, we know this is the type of
942 // llvm.invariant.start operand
943 auto *PtrInt8Ty = PointerType::get(Type::getInt8Ty(LI->getContext()),
944 LI->getPointerAddressSpace());
945 unsigned BitcastsVisited = 0;
946 // Look through bitcasts until we reach the i8* type (this is invariant.start
947 // operand type).
948 while (Addr->getType() != PtrInt8Ty) {
949 auto *BC = dyn_cast<BitCastInst>(Addr);
950 // Avoid traversing high number of bitcast uses.
951 if (++BitcastsVisited > MaxNumUsesTraversed || !BC)
952 return false;
953 Addr = BC->getOperand(0);
954 }
955
956 unsigned UsesVisited = 0;
957 // Traverse all uses of the load operand value, to see if invariant.start is
958 // one of the uses, and whether it dominates the load instruction.
959 for (auto *U : Addr->users()) {
960 // Avoid traversing for Load operand with high number of users.
961 if (++UsesVisited > MaxNumUsesTraversed)
962 return false;
963 IntrinsicInst *II = dyn_cast<IntrinsicInst>(U);
964 // If there are escaping uses of invariant.start instruction, the load maybe
965 // non-invariant.
966 if (!II || II->getIntrinsicID() != Intrinsic::invariant_start ||
967 !II->use_empty())
968 continue;
969 unsigned InvariantSizeInBits =
970 cast<ConstantInt>(II->getArgOperand(0))->getSExtValue() * 8;
971 // Confirm the invariant.start location size contains the load operand size
972 // in bits. Also, the invariant.start should dominate the load, and we
973 // should not hoist the load out of a loop that contains this dominating
974 // invariant.start.
975 if (LocSizeInBits <= InvariantSizeInBits &&
976 DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
977 return true;
978 }
979
980 return false;
981}
982
983namespace {
984/// Return true if-and-only-if we know how to (mechanically) both hoist and
985/// sink a given instruction out of a loop. Does not address legality
986/// concerns such as aliasing or speculation safety.
987bool isHoistableAndSinkableInst(Instruction &I) {
988 // Only these instructions are hoistable/sinkable.
989 return (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
2
Assuming 'I' is not a 'LoadInst'
3
Assuming 'I' is not a 'StoreInst'
4
Assuming 'I' is not a 'CallInst'
16
Returning the value 1, which participates in a condition later
990 isa<FenceInst>(I) || isa<CastInst>(I) || isa<UnaryOperator>(I) ||
5
Assuming 'I' is not a 'FenceInst'
6
Assuming 'I' is not a 'CastInst'
7
Assuming 'I' is not a 'UnaryOperator'
991 isa<BinaryOperator>(I) || isa<SelectInst>(I) ||
8
Assuming 'I' is not a 'BinaryOperator'
9
Assuming 'I' is not a 'SelectInst'
992 isa<GetElementPtrInst>(I) || isa<CmpInst>(I) ||
10
Assuming 'I' is not a 'GetElementPtrInst'
11
Assuming 'I' is not a 'CmpInst'
993 isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
12
Assuming 'I' is not a 'InsertElementInst'
13
Assuming 'I' is not a 'ExtractElementInst'
994 isa<ShuffleVectorInst>(I) || isa<ExtractValueInst>(I) ||
14
Assuming 'I' is not a 'ShuffleVectorInst'
15
Assuming 'I' is a 'ExtractValueInst'
995 isa<InsertValueInst>(I) || isa<FreezeInst>(I));
996}
997/// Return true if all of the alias sets within this AST are known not to
998/// contain a Mod, or if MSSA knows thare are no MemoryDefs in the loop.
999bool isReadOnly(AliasSetTracker *CurAST, const MemorySSAUpdater *MSSAU,
1000 const Loop *L) {
1001 if (CurAST) {
1002 for (AliasSet &AS : *CurAST) {
1003 if (!AS.isForwardingAliasSet() && AS.isMod()) {
1004 return false;
1005 }
1006 }
1007 return true;
1008 } else { /*MSSAU*/
1009 for (auto *BB : L->getBlocks())
1010 if (MSSAU->getMemorySSA()->getBlockDefs(BB))
1011 return false;
1012 return true;
1013 }
1014}
1015
1016/// Return true if I is the only Instruction with a MemoryAccess in L.
1017bool isOnlyMemoryAccess(const Instruction *I, const Loop *L,
1018 const MemorySSAUpdater *MSSAU) {
1019 for (auto *BB : L->getBlocks())
32
Assuming '__begin1' is not equal to '__end1'
1020 if (auto *Accs = MSSAU->getMemorySSA()->getBlockAccesses(BB)) {
33
Called C++ object pointer is null
1021 int NotAPhi = 0;
1022 for (const auto &Acc : *Accs) {
1023 if (isa<MemoryPhi>(&Acc))
1024 continue;
1025 const auto *MUD = cast<MemoryUseOrDef>(&Acc);
1026 if (MUD->getMemoryInst() != I || NotAPhi++ == 1)
1027 return false;
1028 }
1029 }
1030 return true;
1031}
1032}
1033
1034bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
1035 Loop *CurLoop, AliasSetTracker *CurAST,
1036 MemorySSAUpdater *MSSAU,
1037 bool TargetExecutesOncePerLoop,
1038 SinkAndHoistLICMFlags *Flags,
1039 OptimizationRemarkEmitter *ORE) {
1040 // If we don't understand the instruction, bail early.
1041 if (!isHoistableAndSinkableInst(I))
1
Calling 'isHoistableAndSinkableInst'
17
Returning from 'isHoistableAndSinkableInst'
18
Taking false branch
1042 return false;
1043
1044 MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
19
Assuming 'MSSAU' is null
20
'?' condition is false
1045 if (MSSA
20.1
'MSSA' is null
)
21
Taking false branch
1046 assert(Flags != nullptr && "Flags cannot be null.")((Flags != nullptr && "Flags cannot be null.") ? static_cast
<void> (0) : __assert_fail ("Flags != nullptr && \"Flags cannot be null.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1046, __PRETTY_FUNCTION__))
;
1047
1048 // Loads have extra constraints we have to verify before we can hoist them.
1049 if (LoadInst *LI
22.1
'LI' is null
= dyn_cast<LoadInst>(&I)) {
22
Assuming the object is not a 'LoadInst'
23
Taking false branch
1050 if (!LI->isUnordered())
1051 return false; // Don't sink/hoist volatile or ordered atomic loads!
1052
1053 // Loads from constant memory are always safe to move, even if they end up
1054 // in the same alias set as something that ends up being modified.
1055 if (AA->pointsToConstantMemory(LI->getOperand(0)))
1056 return true;
1057 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1058 return true;
1059
1060 if (LI->isAtomic() && !TargetExecutesOncePerLoop)
1061 return false; // Don't risk duplicating unordered loads
1062
1063 // This checks for an invariant.start dominating the load.
1064 if (isLoadInvariantInLoop(LI, DT, CurLoop))
1065 return true;
1066
1067 bool Invalidated;
1068 if (CurAST)
1069 Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI), CurAST,
1070 CurLoop, AA);
1071 else
1072 Invalidated = pointerInvalidatedByLoopWithMSSA(
1073 MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)), CurLoop, *Flags);
1074 // Check loop-invariant address because this may also be a sinkable load
1075 // whose address is not necessarily loop-invariant.
1076 if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1077 ORE->emit([&]() {
1078 return OptimizationRemarkMissed(
1079 DEBUG_TYPE"licm", "LoadWithLoopInvariantAddressInvalidated", LI)
1080 << "failed to move load with loop-invariant address "
1081 "because the loop may invalidate its value";
1082 });
1083
1084 return !Invalidated;
1085 } else if (CallInst *CI
24.1
'CI' is null
= dyn_cast<CallInst>(&I)) {
24
Assuming the object is not a 'CallInst'
25
Taking false branch
1086 // Don't sink or hoist dbg info; it's legal, but not useful.
1087 if (isa<DbgInfoIntrinsic>(I))
1088 return false;
1089
1090 // Don't sink calls which can throw.
1091 if (CI->mayThrow())
1092 return false;
1093
1094 using namespace PatternMatch;
1095 if (match(CI, m_Intrinsic<Intrinsic::assume>()))
1096 // Assumes don't actually alias anything or throw
1097 return true;
1098
1099 if (match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
1100 // Widenable conditions don't actually alias anything or throw
1101 return true;
1102
1103 // Handle simple cases by querying alias analysis.
1104 FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
1105 if (Behavior == FMRB_DoesNotAccessMemory)
1106 return true;
1107 if (AliasAnalysis::onlyReadsMemory(Behavior)) {
1108 // A readonly argmemonly function only reads from memory pointed to by
1109 // it's arguments with arbitrary offsets. If we can prove there are no
1110 // writes to this memory in the loop, we can hoist or sink.
1111 if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) {
1112 // TODO: expand to writeable arguments
1113 for (Value *Op : CI->arg_operands())
1114 if (Op->getType()->isPointerTy()) {
1115 bool Invalidated;
1116 if (CurAST)
1117 Invalidated = pointerInvalidatedByLoop(
1118 MemoryLocation(Op, LocationSize::unknown(), AAMDNodes()),
1119 CurAST, CurLoop, AA);
1120 else
1121 Invalidated = pointerInvalidatedByLoopWithMSSA(
1122 MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(CI)), CurLoop,
1123 *Flags);
1124 if (Invalidated)
1125 return false;
1126 }
1127 return true;
1128 }
1129
1130 // If this call only reads from memory and there are no writes to memory
1131 // in the loop, we can hoist or sink the call as appropriate.
1132 if (isReadOnly(CurAST, MSSAU, CurLoop))
1133 return true;
1134 }
1135
1136 // FIXME: This should use mod/ref information to see if we can hoist or
1137 // sink the call.
1138
1139 return false;
1140 } else if (auto *FI
26.1
'FI' is non-null
= dyn_cast<FenceInst>(&I)) {
26
Assuming the object is a 'FenceInst'
27
Taking true branch
1141 // Fences alias (most) everything to provide ordering. For the moment,
1142 // just give up if there are any other memory operations in the loop.
1143 if (CurAST) {
28
Assuming 'CurAST' is null
29
Taking false branch
1144 auto Begin = CurAST->begin();
1145 assert(Begin != CurAST->end() && "must contain FI")((Begin != CurAST->end() && "must contain FI") ? static_cast
<void> (0) : __assert_fail ("Begin != CurAST->end() && \"must contain FI\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1145, __PRETTY_FUNCTION__))
;
1146 if (std::next(Begin) != CurAST->end())
1147 // constant memory for instance, TODO: handle better
1148 return false;
1149 auto *UniqueI = Begin->getUniqueInstruction();
1150 if (!UniqueI)
1151 // other memory op, give up
1152 return false;
1153 (void)FI; // suppress unused variable warning
1154 assert(UniqueI == FI && "AS must contain FI")((UniqueI == FI && "AS must contain FI") ? static_cast
<void> (0) : __assert_fail ("UniqueI == FI && \"AS must contain FI\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1154, __PRETTY_FUNCTION__))
;
1155 return true;
1156 } else // MSSAU
1157 return isOnlyMemoryAccess(FI, CurLoop, MSSAU);
30
Passing null pointer value via 3rd parameter 'MSSAU'
31
Calling 'isOnlyMemoryAccess'
1158 } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
1159 if (!SI->isUnordered())
1160 return false; // Don't sink/hoist volatile or ordered atomic store!
1161
1162 // We can only hoist a store that we can prove writes a value which is not
1163 // read or overwritten within the loop. For those cases, we fallback to
1164 // load store promotion instead. TODO: We can extend this to cases where
1165 // there is exactly one write to the location and that write dominates an
1166 // arbitrary number of reads in the loop.
1167 if (CurAST) {
1168 auto &AS = CurAST->getAliasSetFor(MemoryLocation::get(SI));
1169
1170 if (AS.isRef() || !AS.isMustAlias())
1171 // Quick exit test, handled by the full path below as well.
1172 return false;
1173 auto *UniqueI = AS.getUniqueInstruction();
1174 if (!UniqueI)
1175 // other memory op, give up
1176 return false;
1177 assert(UniqueI == SI && "AS must contain SI")((UniqueI == SI && "AS must contain SI") ? static_cast
<void> (0) : __assert_fail ("UniqueI == SI && \"AS must contain SI\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1177, __PRETTY_FUNCTION__))
;
1178 return true;
1179 } else { // MSSAU
1180 if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
1181 return true;
1182 // If there are more accesses than the Promotion cap, give up, we're not
1183 // walking a list that long.
1184 if (Flags->NoOfMemAccTooLarge)
1185 return false;
1186 // Check store only if there's still "quota" to check clobber.
1187 if (Flags->LicmMssaOptCounter >= Flags->LicmMssaOptCap)
1188 return false;
1189 // If there are interfering Uses (i.e. their defining access is in the
1190 // loop), or ordered loads (stored as Defs!), don't move this store.
1191 // Could do better here, but this is conservatively correct.
1192 // TODO: Cache set of Uses on the first walk in runOnLoop, update when
1193 // moving accesses. Can also extend to dominating uses.
1194 auto *SIMD = MSSA->getMemoryAccess(SI);
1195 for (auto *BB : CurLoop->getBlocks())
1196 if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
1197 for (const auto &MA : *Accesses)
1198 if (const auto *MU = dyn_cast<MemoryUse>(&MA)) {
1199 auto *MD = MU->getDefiningAccess();
1200 if (!MSSA->isLiveOnEntryDef(MD) &&
1201 CurLoop->contains(MD->getBlock()))
1202 return false;
1203 // Disable hoisting past potentially interfering loads. Optimized
1204 // Uses may point to an access outside the loop, as getClobbering
1205 // checks the previous iteration when walking the backedge.
1206 // FIXME: More precise: no Uses that alias SI.
1207 if (!Flags->IsSink && !MSSA->dominates(SIMD, MU))
1208 return false;
1209 } else if (const auto *MD = dyn_cast<MemoryDef>(&MA)) {
1210 if (auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
1211 (void)LI; // Silence warning.
1212 assert(!LI->isUnordered() && "Expected unordered load")((!LI->isUnordered() && "Expected unordered load")
? static_cast<void> (0) : __assert_fail ("!LI->isUnordered() && \"Expected unordered load\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1212, __PRETTY_FUNCTION__))
;
1213 return false;
1214 }
1215 // Any call, while it may not be clobbering SI, it may be a use.
1216 if (auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
1217 // Check if the call may read from the memory locattion written
1218 // to by SI. Check CI's attributes and arguments; the number of
1219 // such checks performed is limited above by NoOfMemAccTooLarge.
1220 ModRefInfo MRI = AA->getModRefInfo(CI, MemoryLocation::get(SI));
1221 if (isModOrRefSet(MRI))
1222 return false;
1223 }
1224 }
1225 }
1226
1227 auto *Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(SI);
1228 Flags->LicmMssaOptCounter++;
1229 // If there are no clobbering Defs in the loop, store is safe to hoist.
1230 return MSSA->isLiveOnEntryDef(Source) ||
1231 !CurLoop->contains(Source->getBlock());
1232 }
1233 }
1234
1235 assert(!I.mayReadOrWriteMemory() && "unhandled aliasing")((!I.mayReadOrWriteMemory() && "unhandled aliasing") ?
static_cast<void> (0) : __assert_fail ("!I.mayReadOrWriteMemory() && \"unhandled aliasing\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1235, __PRETTY_FUNCTION__))
;
1236
1237 // We've established mechanical ability and aliasing, it's up to the caller
1238 // to check fault safety
1239 return true;
1240}
1241
1242/// Returns true if a PHINode is a trivially replaceable with an
1243/// Instruction.
1244/// This is true when all incoming values are that instruction.
1245/// This pattern occurs most often with LCSSA PHI nodes.
1246///
1247static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I) {
1248 for (const Value *IncValue : PN.incoming_values())
1249 if (IncValue != &I)
1250 return false;
1251
1252 return true;
1253}
1254
1255/// Return true if the instruction is free in the loop.
1256static bool isFreeInLoop(const Instruction &I, const Loop *CurLoop,
1257 const TargetTransformInfo *TTI) {
1258
1259 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1260 if (TTI->getUserCost(GEP) != TargetTransformInfo::TCC_Free)
1261 return false;
1262 // For a GEP, we cannot simply use getUserCost because currently it
1263 // optimistically assume that a GEP will fold into addressing mode
1264 // regardless of its users.
1265 const BasicBlock *BB = GEP->getParent();
1266 for (const User *U : GEP->users()) {
1267 const Instruction *UI = cast<Instruction>(U);
1268 if (CurLoop->contains(UI) &&
1269 (BB != UI->getParent() ||
1270 (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
1271 return false;
1272 }
1273 return true;
1274 } else
1275 return TTI->getUserCost(&I) == TargetTransformInfo::TCC_Free;
1276}
1277
1278/// Return true if the only users of this instruction are outside of
1279/// the loop. If this is true, we can sink the instruction to the exit
1280/// blocks of the loop.
1281///
1282/// We also return true if the instruction could be folded away in lowering.
1283/// (e.g., a GEP can be folded into a load as an addressing mode in the loop).
1284static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
1285 const LoopSafetyInfo *SafetyInfo,
1286 TargetTransformInfo *TTI, bool &FreeInLoop) {
1287 const auto &BlockColors = SafetyInfo->getBlockColors();
1288 bool IsFree = isFreeInLoop(I, CurLoop, TTI);
1289 for (const User *U : I.users()) {
1290 const Instruction *UI = cast<Instruction>(U);
1291 if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
1292 const BasicBlock *BB = PN->getParent();
1293 // We cannot sink uses in catchswitches.
1294 if (isa<CatchSwitchInst>(BB->getTerminator()))
1295 return false;
1296
1297 // We need to sink a callsite to a unique funclet. Avoid sinking if the
1298 // phi use is too muddled.
1299 if (isa<CallInst>(I))
1300 if (!BlockColors.empty() &&
1301 BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
1302 return false;
1303 }
1304
1305 if (CurLoop->contains(UI)) {
1306 if (IsFree) {
1307 FreeInLoop = true;
1308 continue;
1309 }
1310 return false;
1311 }
1312 }
1313 return true;
1314}
1315
1316static Instruction *cloneInstructionInExitBlock(
1317 Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
1318 const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU) {
1319 Instruction *New;
1320 if (auto *CI = dyn_cast<CallInst>(&I)) {
1321 const auto &BlockColors = SafetyInfo->getBlockColors();
1322
1323 // Sinking call-sites need to be handled differently from other
1324 // instructions. The cloned call-site needs a funclet bundle operand
1325 // appropriate for its location in the CFG.
1326 SmallVector<OperandBundleDef, 1> OpBundles;
1327 for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
1328 BundleIdx != BundleEnd; ++BundleIdx) {
1329 OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
1330 if (Bundle.getTagID() == LLVMContext::OB_funclet)
1331 continue;
1332
1333 OpBundles.emplace_back(Bundle);
1334 }
1335
1336 if (!BlockColors.empty()) {
1337 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
1338 assert(CV.size() == 1 && "non-unique color for exit block!")((CV.size() == 1 && "non-unique color for exit block!"
) ? static_cast<void> (0) : __assert_fail ("CV.size() == 1 && \"non-unique color for exit block!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1338, __PRETTY_FUNCTION__))
;
1339 BasicBlock *BBColor = CV.front();
1340 Instruction *EHPad = BBColor->getFirstNonPHI();
1341 if (EHPad->isEHPad())
1342 OpBundles.emplace_back("funclet", EHPad);
1343 }
1344
1345 New = CallInst::Create(CI, OpBundles);
1346 } else {
1347 New = I.clone();
1348 }
1349
1350 ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
1351 if (!I.getName().empty())
1352 New->setName(I.getName() + ".le");
1353
1354 if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
1355 // Create a new MemoryAccess and let MemorySSA set its defining access.
1356 MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
1357 New, nullptr, New->getParent(), MemorySSA::Beginning);
1358 if (NewMemAcc) {
1359 if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
1360 MSSAU->insertDef(MemDef, /*RenameUses=*/true);
1361 else {
1362 auto *MemUse = cast<MemoryUse>(NewMemAcc);
1363 MSSAU->insertUse(MemUse, /*RenameUses=*/true);
1364 }
1365 }
1366 }
1367
1368 // Build LCSSA PHI nodes for any in-loop operands. Note that this is
1369 // particularly cheap because we can rip off the PHI node that we're
1370 // replacing for the number and blocks of the predecessors.
1371 // OPT: If this shows up in a profile, we can instead finish sinking all
1372 // invariant instructions, and then walk their operands to re-establish
1373 // LCSSA. That will eliminate creating PHI nodes just to nuke them when
1374 // sinking bottom-up.
1375 for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
1376 ++OI)
1377 if (Instruction *OInst = dyn_cast<Instruction>(*OI))
1378 if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
1379 if (!OLoop->contains(&PN)) {
1380 PHINode *OpPN =
1381 PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
1382 OInst->getName() + ".lcssa", &ExitBlock.front());
1383 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1384 OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
1385 *OI = OpPN;
1386 }
1387 return New;
1388}
1389
1390static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
1391 AliasSetTracker *AST, MemorySSAUpdater *MSSAU) {
1392 if (AST)
1393 AST->deleteValue(&I);
1394 if (MSSAU)
1395 MSSAU->removeMemoryAccess(&I);
1396 SafetyInfo.removeInstruction(&I);
1397 I.eraseFromParent();
1398}
1399
1400static void moveInstructionBefore(Instruction &I, Instruction &Dest,
1401 ICFLoopSafetyInfo &SafetyInfo,
1402 MemorySSAUpdater *MSSAU,
1403 ScalarEvolution *SE) {
1404 SafetyInfo.removeInstruction(&I);
1405 SafetyInfo.insertInstructionTo(&I, Dest.getParent());
1406 I.moveBefore(&Dest);
1407 if (MSSAU)
1408 if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
1409 MSSAU->getMemorySSA()->getMemoryAccess(&I)))
1410 MSSAU->moveToPlace(OldMemAcc, Dest.getParent(),
1411 MemorySSA::BeforeTerminator);
1412 if (SE)
1413 SE->forgetValue(&I);
1414}
1415
1416static Instruction *sinkThroughTriviallyReplaceablePHI(
1417 PHINode *TPN, Instruction *I, LoopInfo *LI,
1418 SmallDenseMap<BasicBlock *, Instruction *, 32> &SunkCopies,
1419 const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop,
1420 MemorySSAUpdater *MSSAU) {
1421 assert(isTriviallyReplaceablePHI(*TPN, *I) &&((isTriviallyReplaceablePHI(*TPN, *I) && "Expect only trivially replaceable PHI"
) ? static_cast<void> (0) : __assert_fail ("isTriviallyReplaceablePHI(*TPN, *I) && \"Expect only trivially replaceable PHI\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1422, __PRETTY_FUNCTION__))
1422 "Expect only trivially replaceable PHI")((isTriviallyReplaceablePHI(*TPN, *I) && "Expect only trivially replaceable PHI"
) ? static_cast<void> (0) : __assert_fail ("isTriviallyReplaceablePHI(*TPN, *I) && \"Expect only trivially replaceable PHI\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1422, __PRETTY_FUNCTION__))
;
1423 BasicBlock *ExitBlock = TPN->getParent();
1424 Instruction *New;
1425 auto It = SunkCopies.find(ExitBlock);
1426 if (It != SunkCopies.end())
1427 New = It->second;
1428 else
1429 New = SunkCopies[ExitBlock] = cloneInstructionInExitBlock(
1430 *I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
1431 return New;
1432}
1433
1434static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo) {
1435 BasicBlock *BB = PN->getParent();
1436 if (!BB->canSplitPredecessors())
1437 return false;
1438 // It's not impossible to split EHPad blocks, but if BlockColors already exist
1439 // it require updating BlockColors for all offspring blocks accordingly. By
1440 // skipping such corner case, we can make updating BlockColors after splitting
1441 // predecessor fairly simple.
1442 if (!SafetyInfo->getBlockColors().empty() && BB->getFirstNonPHI()->isEHPad())
1443 return false;
1444 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
1445 BasicBlock *BBPred = *PI;
1446 if (isa<IndirectBrInst>(BBPred->getTerminator()) ||
1447 isa<CallBrInst>(BBPred->getTerminator()))
1448 return false;
1449 }
1450 return true;
1451}
1452
1453static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT,
1454 LoopInfo *LI, const Loop *CurLoop,
1455 LoopSafetyInfo *SafetyInfo,
1456 MemorySSAUpdater *MSSAU) {
1457#ifndef NDEBUG
1458 SmallVector<BasicBlock *, 32> ExitBlocks;
1459 CurLoop->getUniqueExitBlocks(ExitBlocks);
1460 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1461 ExitBlocks.end());
1462#endif
1463 BasicBlock *ExitBB = PN->getParent();
1464 assert(ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block.")((ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block."
) ? static_cast<void> (0) : __assert_fail ("ExitBlockSet.count(ExitBB) && \"Expect the PHI is in an exit block.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1464, __PRETTY_FUNCTION__))
;
1465
1466 // Split predecessors of the loop exit to make instructions in the loop are
1467 // exposed to exit blocks through trivially replaceable PHIs while keeping the
1468 // loop in the canonical form where each predecessor of each exit block should
1469 // be contained within the loop. For example, this will convert the loop below
1470 // from
1471 //
1472 // LB1:
1473 // %v1 =
1474 // br %LE, %LB2
1475 // LB2:
1476 // %v2 =
1477 // br %LE, %LB1
1478 // LE:
1479 // %p = phi [%v1, %LB1], [%v2, %LB2] <-- non-trivially replaceable
1480 //
1481 // to
1482 //
1483 // LB1:
1484 // %v1 =
1485 // br %LE.split, %LB2
1486 // LB2:
1487 // %v2 =
1488 // br %LE.split2, %LB1
1489 // LE.split:
1490 // %p1 = phi [%v1, %LB1] <-- trivially replaceable
1491 // br %LE
1492 // LE.split2:
1493 // %p2 = phi [%v2, %LB2] <-- trivially replaceable
1494 // br %LE
1495 // LE:
1496 // %p = phi [%p1, %LE.split], [%p2, %LE.split2]
1497 //
1498 const auto &BlockColors = SafetyInfo->getBlockColors();
1499 SmallSetVector<BasicBlock *, 8> PredBBs(pred_begin(ExitBB), pred_end(ExitBB));
1500 while (!PredBBs.empty()) {
1501 BasicBlock *PredBB = *PredBBs.begin();
1502 assert(CurLoop->contains(PredBB) &&((CurLoop->contains(PredBB) && "Expect all predecessors are in the loop"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->contains(PredBB) && \"Expect all predecessors are in the loop\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1503, __PRETTY_FUNCTION__))
1503 "Expect all predecessors are in the loop")((CurLoop->contains(PredBB) && "Expect all predecessors are in the loop"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->contains(PredBB) && \"Expect all predecessors are in the loop\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1503, __PRETTY_FUNCTION__))
;
1504 if (PN->getBasicBlockIndex(PredBB) >= 0) {
1505 BasicBlock *NewPred = SplitBlockPredecessors(
1506 ExitBB, PredBB, ".split.loop.exit", DT, LI, MSSAU, true);
1507 // Since we do not allow splitting EH-block with BlockColors in
1508 // canSplitPredecessors(), we can simply assign predecessor's color to
1509 // the new block.
1510 if (!BlockColors.empty())
1511 // Grab a reference to the ColorVector to be inserted before getting the
1512 // reference to the vector we are copying because inserting the new
1513 // element in BlockColors might cause the map to be reallocated.
1514 SafetyInfo->copyColors(NewPred, PredBB);
1515 }
1516 PredBBs.remove(PredBB);
1517 }
1518}
1519
1520/// When an instruction is found to only be used outside of the loop, this
1521/// function moves it to the exit blocks and patches up SSA form as needed.
1522/// This method is guaranteed to remove the original instruction from its
1523/// position, and may either delete it or move it to outside of the loop.
1524///
1525static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
1526 const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
1527 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE) {
1528 LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM sinking instruction: " <<
I << "\n"; } } while (false)
;
1529 ORE->emit([&]() {
1530 return OptimizationRemark(DEBUG_TYPE"licm", "InstSunk", &I)
1531 << "sinking " << ore::NV("Inst", &I);
1532 });
1533 bool Changed = false;
1534 if (isa<LoadInst>(I))
1535 ++NumMovedLoads;
1536 else if (isa<CallInst>(I))
1537 ++NumMovedCalls;
1538 ++NumSunk;
1539
1540 // Iterate over users to be ready for actual sinking. Replace users via
1541 // unreachable blocks with undef and make all user PHIs trivially replaceable.
1542 SmallPtrSet<Instruction *, 8> VisitedUsers;
1543 for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
1544 auto *User = cast<Instruction>(*UI);
1545 Use &U = UI.getUse();
1546 ++UI;
1547
1548 if (VisitedUsers.count(User) || CurLoop->contains(User))
1549 continue;
1550
1551 if (!DT->isReachableFromEntry(User->getParent())) {
1552 U = UndefValue::get(I.getType());
1553 Changed = true;
1554 continue;
1555 }
1556
1557 // The user must be a PHI node.
1558 PHINode *PN = cast<PHINode>(User);
1559
1560 // Surprisingly, instructions can be used outside of loops without any
1561 // exits. This can only happen in PHI nodes if the incoming block is
1562 // unreachable.
1563 BasicBlock *BB = PN->getIncomingBlock(U);
1564 if (!DT->isReachableFromEntry(BB)) {
1565 U = UndefValue::get(I.getType());
1566 Changed = true;
1567 continue;
1568 }
1569
1570 VisitedUsers.insert(PN);
1571 if (isTriviallyReplaceablePHI(*PN, I))
1572 continue;
1573
1574 if (!canSplitPredecessors(PN, SafetyInfo))
1575 return Changed;
1576
1577 // Split predecessors of the PHI so that we can make users trivially
1578 // replaceable.
1579 splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo, MSSAU);
1580
1581 // Should rebuild the iterators, as they may be invalidated by
1582 // splitPredecessorsOfLoopExit().
1583 UI = I.user_begin();
1584 UE = I.user_end();
1585 }
1586
1587 if (VisitedUsers.empty())
1588 return Changed;
1589
1590#ifndef NDEBUG
1591 SmallVector<BasicBlock *, 32> ExitBlocks;
1592 CurLoop->getUniqueExitBlocks(ExitBlocks);
1593 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
1594 ExitBlocks.end());
1595#endif
1596
1597 // Clones of this instruction. Don't create more than one per exit block!
1598 SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
1599
1600 // If this instruction is only used outside of the loop, then all users are
1601 // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
1602 // the instruction.
1603 SmallSetVector<User*, 8> Users(I.user_begin(), I.user_end());
1604 for (auto *UI : Users) {
1605 auto *User = cast<Instruction>(UI);
1606
1607 if (CurLoop->contains(User))
1608 continue;
1609
1610 PHINode *PN = cast<PHINode>(User);
1611 assert(ExitBlockSet.count(PN->getParent()) &&((ExitBlockSet.count(PN->getParent()) && "The LCSSA PHI is not in an exit block!"
) ? static_cast<void> (0) : __assert_fail ("ExitBlockSet.count(PN->getParent()) && \"The LCSSA PHI is not in an exit block!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1612, __PRETTY_FUNCTION__))
1612 "The LCSSA PHI is not in an exit block!")((ExitBlockSet.count(PN->getParent()) && "The LCSSA PHI is not in an exit block!"
) ? static_cast<void> (0) : __assert_fail ("ExitBlockSet.count(PN->getParent()) && \"The LCSSA PHI is not in an exit block!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1612, __PRETTY_FUNCTION__))
;
1613 // The PHI must be trivially replaceable.
1614 Instruction *New = sinkThroughTriviallyReplaceablePHI(
1615 PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
1616 PN->replaceAllUsesWith(New);
1617 eraseInstruction(*PN, *SafetyInfo, nullptr, nullptr);
1618 Changed = true;
1619 }
1620 return Changed;
1621}
1622
1623/// When an instruction is found to only use loop invariant operands that
1624/// is safe to hoist, this instruction is called to do the dirty work.
1625///
1626static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
1627 BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
1628 MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
1629 OptimizationRemarkEmitter *ORE) {
1630 LLVM_DEBUG(dbgs() << "LICM hoisting to " << Dest->getName() << ": " << Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM hoisting to " << Dest
->getName() << ": " << I << "\n"; } } while
(false)
1631 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM hoisting to " << Dest
->getName() << ": " << I << "\n"; } } while
(false)
;
1632 ORE->emit([&]() {
1633 return OptimizationRemark(DEBUG_TYPE"licm", "Hoisted", &I) << "hoisting "
1634 << ore::NV("Inst", &I);
1635 });
1636
1637 // Metadata can be dependent on conditions we are hoisting above.
1638 // Conservatively strip all metadata on the instruction unless we were
1639 // guaranteed to execute I if we entered the loop, in which case the metadata
1640 // is valid in the loop preheader.
1641 if (I.hasMetadataOtherThanDebugLoc() &&
1642 // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
1643 // time in isGuaranteedToExecute if we don't actually have anything to
1644 // drop. It is a compile time optimization, not required for correctness.
1645 !SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop))
1646 I.dropUnknownNonDebugMetadata();
1647
1648 if (isa<PHINode>(I))
1649 // Move the new node to the end of the phi list in the destination block.
1650 moveInstructionBefore(I, *Dest->getFirstNonPHI(), *SafetyInfo, MSSAU, SE);
1651 else
1652 // Move the new node to the destination block, before its terminator.
1653 moveInstructionBefore(I, *Dest->getTerminator(), *SafetyInfo, MSSAU, SE);
1654
1655 // Apply line 0 debug locations when we are moving instructions to different
1656 // basic blocks because we want to avoid jumpy line tables.
1657 if (const DebugLoc &DL = I.getDebugLoc())
1658 I.setDebugLoc(DebugLoc::get(0, 0, DL.getScope(), DL.getInlinedAt()));
1659
1660 if (isa<LoadInst>(I))
1661 ++NumMovedLoads;
1662 else if (isa<CallInst>(I))
1663 ++NumMovedCalls;
1664 ++NumHoisted;
1665}
1666
1667/// Only sink or hoist an instruction if it is not a trapping instruction,
1668/// or if the instruction is known not to trap when moved to the preheader.
1669/// or if it is a trapping instruction and is guaranteed to execute.
1670static bool isSafeToExecuteUnconditionally(Instruction &Inst,
1671 const DominatorTree *DT,
1672 const Loop *CurLoop,
1673 const LoopSafetyInfo *SafetyInfo,
1674 OptimizationRemarkEmitter *ORE,
1675 const Instruction *CtxI) {
1676 if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
1677 return true;
1678
1679 bool GuaranteedToExecute =
1680 SafetyInfo->isGuaranteedToExecute(Inst, DT, CurLoop);
1681
1682 if (!GuaranteedToExecute) {
1683 auto *LI = dyn_cast<LoadInst>(&Inst);
1684 if (LI && CurLoop->isLoopInvariant(LI->getPointerOperand()))
1685 ORE->emit([&]() {
1686 return OptimizationRemarkMissed(
1687 DEBUG_TYPE"licm", "LoadWithLoopInvariantAddressCondExecuted", LI)
1688 << "failed to hoist load with loop-invariant address "
1689 "because load is conditionally executed";
1690 });
1691 }
1692
1693 return GuaranteedToExecute;
1694}
1695
1696namespace {
1697class LoopPromoter : public LoadAndStorePromoter {
1698 Value *SomePtr; // Designated pointer to store to.
1699 const SmallSetVector<Value *, 8> &PointerMustAliases;
1700 SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
1701 SmallVectorImpl<Instruction *> &LoopInsertPts;
1702 SmallVectorImpl<MemoryAccess *> &MSSAInsertPts;
1703 PredIteratorCache &PredCache;
1704 AliasSetTracker &AST;
1705 MemorySSAUpdater *MSSAU;
1706 LoopInfo &LI;
1707 DebugLoc DL;
1708 int Alignment;
1709 bool UnorderedAtomic;
1710 AAMDNodes AATags;
1711 ICFLoopSafetyInfo &SafetyInfo;
1712
1713 Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
1714 if (Instruction *I = dyn_cast<Instruction>(V))
1715 if (Loop *L = LI.getLoopFor(I->getParent()))
1716 if (!L->contains(BB)) {
1717 // We need to create an LCSSA PHI node for the incoming value and
1718 // store that.
1719 PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
1720 I->getName() + ".lcssa", &BB->front());
1721 for (BasicBlock *Pred : PredCache.get(BB))
1722 PN->addIncoming(I, Pred);
1723 return PN;
1724 }
1725 return V;
1726 }
1727
1728public:
1729 LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
1730 const SmallSetVector<Value *, 8> &PMA,
1731 SmallVectorImpl<BasicBlock *> &LEB,
1732 SmallVectorImpl<Instruction *> &LIP,
1733 SmallVectorImpl<MemoryAccess *> &MSSAIP, PredIteratorCache &PIC,
1734 AliasSetTracker &ast, MemorySSAUpdater *MSSAU, LoopInfo &li,
1735 DebugLoc dl, int alignment, bool UnorderedAtomic,
1736 const AAMDNodes &AATags, ICFLoopSafetyInfo &SafetyInfo)
1737 : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
1738 LoopExitBlocks(LEB), LoopInsertPts(LIP), MSSAInsertPts(MSSAIP),
1739 PredCache(PIC), AST(ast), MSSAU(MSSAU), LI(li), DL(std::move(dl)),
1740 Alignment(alignment), UnorderedAtomic(UnorderedAtomic), AATags(AATags),
1741 SafetyInfo(SafetyInfo) {}
1742
1743 bool isInstInList(Instruction *I,
1744 const SmallVectorImpl<Instruction *> &) const override {
1745 Value *Ptr;
1746 if (LoadInst *LI = dyn_cast<LoadInst>(I))
1747 Ptr = LI->getOperand(0);
1748 else
1749 Ptr = cast<StoreInst>(I)->getPointerOperand();
1750 return PointerMustAliases.count(Ptr);
1751 }
1752
1753 void doExtraRewritesBeforeFinalDeletion() override {
1754 // Insert stores after in the loop exit blocks. Each exit block gets a
1755 // store of the live-out values that feed them. Since we've already told
1756 // the SSA updater about the defs in the loop and the preheader
1757 // definition, it is all set and we can start using it.
1758 for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
1759 BasicBlock *ExitBlock = LoopExitBlocks[i];
1760 Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
1761 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
1762 Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
1763 Instruction *InsertPos = LoopInsertPts[i];
1764 StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
1765 if (UnorderedAtomic)
1766 NewSI->setOrdering(AtomicOrdering::Unordered);
1767 NewSI->setAlignment(MaybeAlign(Alignment));
1768 NewSI->setDebugLoc(DL);
1769 if (AATags)
1770 NewSI->setAAMetadata(AATags);
1771
1772 if (MSSAU) {
1773 MemoryAccess *MSSAInsertPoint = MSSAInsertPts[i];
1774 MemoryAccess *NewMemAcc;
1775 if (!MSSAInsertPoint) {
1776 NewMemAcc = MSSAU->createMemoryAccessInBB(
1777 NewSI, nullptr, NewSI->getParent(), MemorySSA::Beginning);
1778 } else {
1779 NewMemAcc =
1780 MSSAU->createMemoryAccessAfter(NewSI, nullptr, MSSAInsertPoint);
1781 }
1782 MSSAInsertPts[i] = NewMemAcc;
1783 MSSAU->insertDef(cast<MemoryDef>(NewMemAcc), true);
1784 // FIXME: true for safety, false may still be correct.
1785 }
1786 }
1787 }
1788
1789 void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
1790 // Update alias analysis.
1791 AST.copyValue(LI, V);
1792 }
1793 void instructionDeleted(Instruction *I) const override {
1794 SafetyInfo.removeInstruction(I);
1795 AST.deleteValue(I);
1796 if (MSSAU)
1797 MSSAU->removeMemoryAccess(I);
1798 }
1799};
1800
1801
1802/// Return true iff we can prove that a caller of this function can not inspect
1803/// the contents of the provided object in a well defined program.
1804bool isKnownNonEscaping(Value *Object, const TargetLibraryInfo *TLI) {
1805 if (isa<AllocaInst>(Object))
1806 // Since the alloca goes out of scope, we know the caller can't retain a
1807 // reference to it and be well defined. Thus, we don't need to check for
1808 // capture.
1809 return true;
1810
1811 // For all other objects we need to know that the caller can't possibly
1812 // have gotten a reference to the object. There are two components of
1813 // that:
1814 // 1) Object can't be escaped by this function. This is what
1815 // PointerMayBeCaptured checks.
1816 // 2) Object can't have been captured at definition site. For this, we
1817 // need to know the return value is noalias. At the moment, we use a
1818 // weaker condition and handle only AllocLikeFunctions (which are
1819 // known to be noalias). TODO
1820 return isAllocLikeFn(Object, TLI) &&
1821 !PointerMayBeCaptured(Object, true, true);
1822}
1823
1824} // namespace
1825
1826/// Try to promote memory values to scalars by sinking stores out of the
1827/// loop and moving loads to before the loop. We do this by looping over
1828/// the stores in the loop, looking for stores to Must pointers which are
1829/// loop invariant.
1830///
1831bool llvm::promoteLoopAccessesToScalars(
1832 const SmallSetVector<Value *, 8> &PointerMustAliases,
1833 SmallVectorImpl<BasicBlock *> &ExitBlocks,
1834 SmallVectorImpl<Instruction *> &InsertPts,
1835 SmallVectorImpl<MemoryAccess *> &MSSAInsertPts, PredIteratorCache &PIC,
1836 LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
1837 Loop *CurLoop, AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
1838 ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) {
1839 // Verify inputs.
1840 assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&((LI != nullptr && DT != nullptr && CurLoop !=
nullptr && CurAST != nullptr && SafetyInfo !=
nullptr && "Unexpected Input to promoteLoopAccessesToScalars"
) ? static_cast<void> (0) : __assert_fail ("LI != nullptr && DT != nullptr && CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr && \"Unexpected Input to promoteLoopAccessesToScalars\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1842, __PRETTY_FUNCTION__))
1841 CurAST != nullptr && SafetyInfo != nullptr &&((LI != nullptr && DT != nullptr && CurLoop !=
nullptr && CurAST != nullptr && SafetyInfo !=
nullptr && "Unexpected Input to promoteLoopAccessesToScalars"
) ? static_cast<void> (0) : __assert_fail ("LI != nullptr && DT != nullptr && CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr && \"Unexpected Input to promoteLoopAccessesToScalars\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1842, __PRETTY_FUNCTION__))
1842 "Unexpected Input to promoteLoopAccessesToScalars")((LI != nullptr && DT != nullptr && CurLoop !=
nullptr && CurAST != nullptr && SafetyInfo !=
nullptr && "Unexpected Input to promoteLoopAccessesToScalars"
) ? static_cast<void> (0) : __assert_fail ("LI != nullptr && DT != nullptr && CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr && \"Unexpected Input to promoteLoopAccessesToScalars\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 1842, __PRETTY_FUNCTION__))
;
1843
1844 Value *SomePtr = *PointerMustAliases.begin();
1845 BasicBlock *Preheader = CurLoop->getLoopPreheader();
1846
1847 // It is not safe to promote a load/store from the loop if the load/store is
1848 // conditional. For example, turning:
1849 //
1850 // for () { if (c) *P += 1; }
1851 //
1852 // into:
1853 //
1854 // tmp = *P; for () { if (c) tmp +=1; } *P = tmp;
1855 //
1856 // is not safe, because *P may only be valid to access if 'c' is true.
1857 //
1858 // The safety property divides into two parts:
1859 // p1) The memory may not be dereferenceable on entry to the loop. In this
1860 // case, we can't insert the required load in the preheader.
1861 // p2) The memory model does not allow us to insert a store along any dynamic
1862 // path which did not originally have one.
1863 //
1864 // If at least one store is guaranteed to execute, both properties are
1865 // satisfied, and promotion is legal.
1866 //
1867 // This, however, is not a necessary condition. Even if no store/load is
1868 // guaranteed to execute, we can still establish these properties.
1869 // We can establish (p1) by proving that hoisting the load into the preheader
1870 // is safe (i.e. proving dereferenceability on all paths through the loop). We
1871 // can use any access within the alias set to prove dereferenceability,
1872 // since they're all must alias.
1873 //
1874 // There are two ways establish (p2):
1875 // a) Prove the location is thread-local. In this case the memory model
1876 // requirement does not apply, and stores are safe to insert.
1877 // b) Prove a store dominates every exit block. In this case, if an exit
1878 // blocks is reached, the original dynamic path would have taken us through
1879 // the store, so inserting a store into the exit block is safe. Note that this
1880 // is different from the store being guaranteed to execute. For instance,
1881 // if an exception is thrown on the first iteration of the loop, the original
1882 // store is never executed, but the exit blocks are not executed either.
1883
1884 bool DereferenceableInPH = false;
1885 bool SafeToInsertStore = false;
1886
1887 SmallVector<Instruction *, 64> LoopUses;
1888
1889 // We start with an alignment of one and try to find instructions that allow
1890 // us to prove better alignment.
1891 unsigned Alignment = 1;
1892 // Keep track of which types of access we see
1893 bool SawUnorderedAtomic = false;
1894 bool SawNotAtomic = false;
1895 AAMDNodes AATags;
1896
1897 const DataLayout &MDL = Preheader->getModule()->getDataLayout();
1898
1899 bool IsKnownThreadLocalObject = false;
1900 if (SafetyInfo->anyBlockMayThrow()) {
1901 // If a loop can throw, we have to insert a store along each unwind edge.
1902 // That said, we can't actually make the unwind edge explicit. Therefore,
1903 // we have to prove that the store is dead along the unwind edge. We do
1904 // this by proving that the caller can't have a reference to the object
1905 // after return and thus can't possibly load from the object.
1906 Value *Object = GetUnderlyingObject(SomePtr, MDL);
1907 if (!isKnownNonEscaping(Object, TLI))
1908 return false;
1909 // Subtlety: Alloca's aren't visible to callers, but *are* potentially
1910 // visible to other threads if captured and used during their lifetimes.
1911 IsKnownThreadLocalObject = !isa<AllocaInst>(Object);
1912 }
1913
1914 // Check that all of the pointers in the alias set have the same type. We
1915 // cannot (yet) promote a memory location that is loaded and stored in
1916 // different sizes. While we are at it, collect alignment and AA info.
1917 for (Value *ASIV : PointerMustAliases) {
1918 // Check that all of the pointers in the alias set have the same type. We
1919 // cannot (yet) promote a memory location that is loaded and stored in
1920 // different sizes.
1921 if (SomePtr->getType() != ASIV->getType())
1922 return false;
1923
1924 for (User *U : ASIV->users()) {
1925 // Ignore instructions that are outside the loop.
1926 Instruction *UI = dyn_cast<Instruction>(U);
1927 if (!UI || !CurLoop->contains(UI))
1928 continue;
1929
1930 // If there is an non-load/store instruction in the loop, we can't promote
1931 // it.
1932 if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
1933 if (!Load->isUnordered())
1934 return false;
1935
1936 SawUnorderedAtomic |= Load->isAtomic();
1937 SawNotAtomic |= !Load->isAtomic();
1938
1939 unsigned InstAlignment = Load->getAlignment();
1940 if (!InstAlignment)
1941 InstAlignment =
1942 MDL.getABITypeAlignment(Load->getType());
1943
1944 // Note that proving a load safe to speculate requires proving
1945 // sufficient alignment at the target location. Proving it guaranteed
1946 // to execute does as well. Thus we can increase our guaranteed
1947 // alignment as well.
1948 if (!DereferenceableInPH || (InstAlignment > Alignment))
1949 if (isSafeToExecuteUnconditionally(*Load, DT, CurLoop, SafetyInfo,
1950 ORE, Preheader->getTerminator())) {
1951 DereferenceableInPH = true;
1952 Alignment = std::max(Alignment, InstAlignment);
1953 }
1954 } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
1955 // Stores *of* the pointer are not interesting, only stores *to* the
1956 // pointer.
1957 if (UI->getOperand(1) != ASIV)
1958 continue;
1959 if (!Store->isUnordered())
1960 return false;
1961
1962 SawUnorderedAtomic |= Store->isAtomic();
1963 SawNotAtomic |= !Store->isAtomic();
1964
1965 // If the store is guaranteed to execute, both properties are satisfied.
1966 // We may want to check if a store is guaranteed to execute even if we
1967 // already know that promotion is safe, since it may have higher
1968 // alignment than any other guaranteed stores, in which case we can
1969 // raise the alignment on the promoted store.
1970 unsigned InstAlignment = Store->getAlignment();
1971 if (!InstAlignment)
1972 InstAlignment =
1973 MDL.getABITypeAlignment(Store->getValueOperand()->getType());
1974
1975 if (!DereferenceableInPH || !SafeToInsertStore ||
1976 (InstAlignment > Alignment)) {
1977 if (SafetyInfo->isGuaranteedToExecute(*UI, DT, CurLoop)) {
1978 DereferenceableInPH = true;
1979 SafeToInsertStore = true;
1980 Alignment = std::max(Alignment, InstAlignment);
1981 }
1982 }
1983
1984 // If a store dominates all exit blocks, it is safe to sink.
1985 // As explained above, if an exit block was executed, a dominating
1986 // store must have been executed at least once, so we are not
1987 // introducing stores on paths that did not have them.
1988 // Note that this only looks at explicit exit blocks. If we ever
1989 // start sinking stores into unwind edges (see above), this will break.
1990 if (!SafeToInsertStore)
1991 SafeToInsertStore = llvm::all_of(ExitBlocks, [&](BasicBlock *Exit) {
1992 return DT->dominates(Store->getParent(), Exit);
1993 });
1994
1995 // If the store is not guaranteed to execute, we may still get
1996 // deref info through it.
1997 if (!DereferenceableInPH) {
1998 DereferenceableInPH = isDereferenceableAndAlignedPointer(
1999 Store->getPointerOperand(), Store->getValueOperand()->getType(),
2000 MaybeAlign(Store->getAlignment()), MDL,
2001 Preheader->getTerminator(), DT);
2002 }
2003 } else
2004 return false; // Not a load or store.
2005
2006 // Merge the AA tags.
2007 if (LoopUses.empty()) {
2008 // On the first load/store, just take its AA tags.
2009 UI->getAAMetadata(AATags);
2010 } else if (AATags) {
2011 UI->getAAMetadata(AATags, /* Merge = */ true);
2012 }
2013
2014 LoopUses.push_back(UI);
2015 }
2016 }
2017
2018 // If we found both an unordered atomic instruction and a non-atomic memory
2019 // access, bail. We can't blindly promote non-atomic to atomic since we
2020 // might not be able to lower the result. We can't downgrade since that
2021 // would violate memory model. Also, align 0 is an error for atomics.
2022 if (SawUnorderedAtomic && SawNotAtomic)
2023 return false;
2024
2025 // If we're inserting an atomic load in the preheader, we must be able to
2026 // lower it. We're only guaranteed to be able to lower naturally aligned
2027 // atomics.
2028 auto *SomePtrElemType = SomePtr->getType()->getPointerElementType();
2029 if (SawUnorderedAtomic &&
2030 Alignment < MDL.getTypeStoreSize(SomePtrElemType))
2031 return false;
2032
2033 // If we couldn't prove we can hoist the load, bail.
2034 if (!DereferenceableInPH)
2035 return false;
2036
2037 // We know we can hoist the load, but don't have a guaranteed store.
2038 // Check whether the location is thread-local. If it is, then we can insert
2039 // stores along paths which originally didn't have them without violating the
2040 // memory model.
2041 if (!SafeToInsertStore) {
2042 if (IsKnownThreadLocalObject)
2043 SafeToInsertStore = true;
2044 else {
2045 Value *Object = GetUnderlyingObject(SomePtr, MDL);
2046 SafeToInsertStore =
2047 (isAllocLikeFn(Object, TLI) || isa<AllocaInst>(Object)) &&
2048 !PointerMayBeCaptured(Object, true, true);
2049 }
2050 }
2051
2052 // If we've still failed to prove we can sink the store, give up.
2053 if (!SafeToInsertStore)
2054 return false;
2055
2056 // Otherwise, this is safe to promote, lets do it!
2057 LLVM_DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtrdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM: Promoting value stored to in loop: "
<< *SomePtr << '\n'; } } while (false)
2058 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "LICM: Promoting value stored to in loop: "
<< *SomePtr << '\n'; } } while (false)
;
2059 ORE->emit([&]() {
2060 return OptimizationRemark(DEBUG_TYPE"licm", "PromoteLoopAccessesToScalar",
2061 LoopUses[0])
2062 << "Moving accesses to memory location out of the loop";
2063 });
2064 ++NumPromoted;
2065
2066 // Grab a debug location for the inserted loads/stores; given that the
2067 // inserted loads/stores have little relation to the original loads/stores,
2068 // this code just arbitrarily picks a location from one, since any debug
2069 // location is better than none.
2070 DebugLoc DL = LoopUses[0]->getDebugLoc();
2071
2072 // We use the SSAUpdater interface to insert phi nodes as required.
2073 SmallVector<PHINode *, 16> NewPHIs;
2074 SSAUpdater SSA(&NewPHIs);
2075 LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
2076 InsertPts, MSSAInsertPts, PIC, *CurAST, MSSAU, *LI, DL,
2077 Alignment, SawUnorderedAtomic, AATags, *SafetyInfo);
2078
2079 // Set up the preheader to have a definition of the value. It is the live-out
2080 // value from the preheader that uses in the loop will use.
2081 LoadInst *PreheaderLoad = new LoadInst(
2082 SomePtr->getType()->getPointerElementType(), SomePtr,
2083 SomePtr->getName() + ".promoted", Preheader->getTerminator());
2084 if (SawUnorderedAtomic)
2085 PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
2086 PreheaderLoad->setAlignment(MaybeAlign(Alignment));
2087 PreheaderLoad->setDebugLoc(DL);
2088 if (AATags)
2089 PreheaderLoad->setAAMetadata(AATags);
2090 SSA.AddAvailableValue(Preheader, PreheaderLoad);
2091
2092 if (MSSAU) {
2093 MemoryAccess *PreheaderLoadMemoryAccess = MSSAU->createMemoryAccessInBB(
2094 PreheaderLoad, nullptr, PreheaderLoad->getParent(), MemorySSA::End);
2095 MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
2096 MSSAU->insertUse(NewMemUse, /*RenameUses=*/true);
2097 }
2098
2099 if (MSSAU && VerifyMemorySSA)
2100 MSSAU->getMemorySSA()->verifyMemorySSA();
2101 // Rewrite all the loads in the loop and remember all the definitions from
2102 // stores in the loop.
2103 Promoter.run(LoopUses);
2104
2105 if (MSSAU && VerifyMemorySSA)
2106 MSSAU->getMemorySSA()->verifyMemorySSA();
2107 // If the SSAUpdater didn't use the load in the preheader, just zap it now.
2108 if (PreheaderLoad->use_empty())
2109 eraseInstruction(*PreheaderLoad, *SafetyInfo, CurAST, MSSAU);
2110
2111 return true;
2112}
2113
2114/// Returns an owning pointer to an alias set which incorporates aliasing info
2115/// from L and all subloops of L.
2116std::unique_ptr<AliasSetTracker>
2117LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
2118 AliasAnalysis *AA) {
2119 auto CurAST = std::make_unique<AliasSetTracker>(*AA);
2120
2121 // Add everything from all the sub loops.
2122 for (Loop *InnerL : L->getSubLoops())
2123 for (BasicBlock *BB : InnerL->blocks())
2124 CurAST->add(*BB);
2125
2126 // And merge in this loop (without anything from inner loops).
2127 for (BasicBlock *BB : L->blocks())
2128 if (LI->getLoopFor(BB) == L)
2129 CurAST->add(*BB);
2130
2131 return CurAST;
2132}
2133
2134std::unique_ptr<AliasSetTracker>
2135LoopInvariantCodeMotion::collectAliasInfoForLoopWithMSSA(
2136 Loop *L, AliasAnalysis *AA, MemorySSAUpdater *MSSAU) {
2137 auto *MSSA = MSSAU->getMemorySSA();
2138 auto CurAST = std::make_unique<AliasSetTracker>(*AA, MSSA, L);
2139 CurAST->addAllInstructionsInLoopUsingMSSA();
2140 return CurAST;
2141}
2142
2143static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
2144 AliasSetTracker *CurAST, Loop *CurLoop,
2145 AliasAnalysis *AA) {
2146 // First check to see if any of the basic blocks in CurLoop invalidate *V.
2147 bool isInvalidatedAccordingToAST = CurAST->getAliasSetFor(MemLoc).isMod();
2148
2149 if (!isInvalidatedAccordingToAST || !LICMN2Theshold)
2150 return isInvalidatedAccordingToAST;
2151
2152 // Check with a diagnostic analysis if we can refine the information above.
2153 // This is to identify the limitations of using the AST.
2154 // The alias set mechanism used by LICM has a major weakness in that it
2155 // combines all things which may alias into a single set *before* asking
2156 // modref questions. As a result, a single readonly call within a loop will
2157 // collapse all loads and stores into a single alias set and report
2158 // invalidation if the loop contains any store. For example, readonly calls
2159 // with deopt states have this form and create a general alias set with all
2160 // loads and stores. In order to get any LICM in loops containing possible
2161 // deopt states we need a more precise invalidation of checking the mod ref
2162 // info of each instruction within the loop and LI. This has a complexity of
2163 // O(N^2), so currently, it is used only as a diagnostic tool since the
2164 // default value of LICMN2Threshold is zero.
2165
2166 // Don't look at nested loops.
2167 if (CurLoop->begin() != CurLoop->end())
2168 return true;
2169
2170 int N = 0;
2171 for (BasicBlock *BB : CurLoop->getBlocks())
2172 for (Instruction &I : *BB) {
2173 if (N >= LICMN2Theshold) {
2174 LLVM_DEBUG(dbgs() << "Alasing N2 threshold exhausted for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Alasing N2 threshold exhausted for "
<< *(MemLoc.Ptr) << "\n"; } } while (false)
2175 << *(MemLoc.Ptr) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Alasing N2 threshold exhausted for "
<< *(MemLoc.Ptr) << "\n"; } } while (false)
;
2176 return true;
2177 }
2178 N++;
2179 auto Res = AA->getModRefInfo(&I, MemLoc);
2180 if (isModSet(Res)) {
2181 LLVM_DEBUG(dbgs() << "Aliasing failed on " << I << " for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Aliasing failed on " << I <<
" for " << *(MemLoc.Ptr) << "\n"; } } while (false
)
2182 << *(MemLoc.Ptr) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Aliasing failed on " << I <<
" for " << *(MemLoc.Ptr) << "\n"; } } while (false
)
;
2183 return true;
2184 }
2185 }
2186 LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("licm")) { dbgs() << "Aliasing okay for " << *(MemLoc
.Ptr) << "\n"; } } while (false)
;
2187 return false;
2188}
2189
2190static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
2191 Loop *CurLoop,
2192 SinkAndHoistLICMFlags &Flags) {
2193 // For hoisting, use the walker to determine safety
2194 if (!Flags.IsSink) {
2195 MemoryAccess *Source;
2196 // See declaration of SetLicmMssaOptCap for usage details.
2197 if (Flags.LicmMssaOptCounter >= Flags.LicmMssaOptCap)
2198 Source = MU->getDefiningAccess();
2199 else {
2200 Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(MU);
2201 Flags.LicmMssaOptCounter++;
2202 }
2203 return !MSSA->isLiveOnEntryDef(Source) &&
2204 CurLoop->contains(Source->getBlock());
2205 }
2206
2207 // For sinking, we'd need to check all Defs below this use. The getClobbering
2208 // call will look on the backedge of the loop, but will check aliasing with
2209 // the instructions on the previous iteration.
2210 // For example:
2211 // for (i ... )
2212 // load a[i] ( Use (LoE)
2213 // store a[i] ( 1 = Def (2), with 2 = Phi for the loop.
2214 // i++;
2215 // The load sees no clobbering inside the loop, as the backedge alias check
2216 // does phi translation, and will check aliasing against store a[i-1].
2217 // However sinking the load outside the loop, below the store is incorrect.
2218
2219 // For now, only sink if there are no Defs in the loop, and the existing ones
2220 // precede the use and are in the same block.
2221 // FIXME: Increase precision: Safe to sink if Use post dominates the Def;
2222 // needs PostDominatorTreeAnalysis.
2223 // FIXME: More precise: no Defs that alias this Use.
2224 if (Flags.NoOfMemAccTooLarge)
2225 return true;
2226 for (auto *BB : CurLoop->getBlocks())
2227 if (auto *Accesses = MSSA->getBlockDefs(BB))
2228 for (const auto &MA : *Accesses)
2229 if (const auto *MD = dyn_cast<MemoryDef>(&MA))
2230 if (MU->getBlock() != MD->getBlock() ||
2231 !MSSA->locallyDominates(MD, MU))
2232 return true;
2233 return false;
2234}
2235
2236/// Little predicate that returns true if the specified basic block is in
2237/// a subloop of the current one, not the current one itself.
2238///
2239static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
2240 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop")((CurLoop->contains(BB) && "Only valid if BB is IN the loop"
) ? static_cast<void> (0) : __assert_fail ("CurLoop->contains(BB) && \"Only valid if BB is IN the loop\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/LICM.cpp"
, 2240, __PRETTY_FUNCTION__))
;
2241 return LI->getLoopFor(BB) != CurLoop;
2242}