Bug Summary

File:llvm/lib/Transforms/Scalar/LICM.cpp
Warning:line 1010, column 11
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

/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'
18
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 not a 'ExtractValueInst'
995 isa<InsertValueInst>(I) || isa<FreezeInst>(I));
16
Assuming 'I' is not a 'InsertValueInst'
17
Assuming 'I' is a 'FreezeInst'
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) {
64
Assuming 'CurAST' is null
65
Taking false branch
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())
66
Assuming '__begin2' is not equal to '__end2'
1010 if (MSSAU->getMemorySSA()->getBlockDefs(BB))
67
Called C++ object pointer is null
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())
1020 if (auto *Accs = MSSAU->getMemorySSA()->getBlockAccesses(BB)) {
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'
19
Returning from 'isHoistableAndSinkableInst'
20
Taking false branch
1042 return false;
1043
1044 MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
21
Assuming 'MSSAU' is null
22
'?' condition is false
1045 if (MSSA
22.1
'MSSA' is null
22.1
'MSSA' is null
22.1
'MSSA' is null
)
23
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
24.1
'LI' is null
24.1
'LI' is null
24.1
'LI' is null
= dyn_cast<LoadInst>(&I)) {
24
Assuming the object is not a 'LoadInst'
25
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
26.1
'CI' is non-null
26.1
'CI' is non-null
26.1
'CI' is non-null
= dyn_cast<CallInst>(&I)) {
26
Assuming the object is a 'CallInst'
27
Taking true branch
1086 // Don't sink or hoist dbg info; it's legal, but not useful.
1087 if (isa<DbgInfoIntrinsic>(I))
28
Assuming 'I' is not a 'DbgInfoIntrinsic'
29
Taking false branch
1088 return false;
1089
1090 // Don't sink calls which can throw.
1091 if (CI->mayThrow())
30
Assuming the condition is false
31
Taking false branch
1092 return false;
1093
1094 using namespace PatternMatch;
1095 if (match(CI, m_Intrinsic<Intrinsic::assume>()))
32
Calling 'match<llvm::CallInst, llvm::PatternMatch::IntrinsicID_match>'
39
Returning from 'match<llvm::CallInst, llvm::PatternMatch::IntrinsicID_match>'
40
Taking false branch
1096 // Assumes don't actually alias anything or throw
1097 return true;
1098
1099 if (match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
41
Calling 'match<llvm::CallInst, llvm::PatternMatch::IntrinsicID_match>'
48
Returning from 'match<llvm::CallInst, llvm::PatternMatch::IntrinsicID_match>'
49
Taking false branch
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)
50
Assuming 'Behavior' is not equal to FMRB_DoesNotAccessMemory
51
Taking false branch
1106 return true;
1107 if (AliasAnalysis::onlyReadsMemory(Behavior)) {
52
Calling 'AAResults::onlyReadsMemory'
55
Returning from 'AAResults::onlyReadsMemory'
56
Taking true branch
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)) {
57
Calling 'AAResults::onlyAccessesArgPointees'
60
Returning from 'AAResults::onlyAccessesArgPointees'
61
Taking false branch
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))
62
Passing null pointer value via 2nd parameter 'MSSAU'
63
Calling 'isReadOnly'
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 = dyn_cast<FenceInst>(&I)) {
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) {
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);
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}

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/IR/PatternMatch.h

1//===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
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 file provides a simple and efficient mechanism for performing general
10// tree-based pattern matches on the LLVM IR. The power of these routines is
11// that it allows you to write concise patterns that are expressive and easy to
12// understand. The other major advantage of this is that it allows you to
13// trivially capture/bind elements in the pattern to variables. For example,
14// you can do something like this:
15//
16// Value *Exp = ...
17// Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2)
18// if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
19// m_And(m_Value(Y), m_ConstantInt(C2))))) {
20// ... Pattern is matched and variables are bound ...
21// }
22//
23// This is primarily useful to things like the instruction combiner, but can
24// also be useful for static analysis tools or code generators.
25//
26//===----------------------------------------------------------------------===//
27
28#ifndef LLVM_IR_PATTERNMATCH_H
29#define LLVM_IR_PATTERNMATCH_H
30
31#include "llvm/ADT/APFloat.h"
32#include "llvm/ADT/APInt.h"
33#include "llvm/IR/Constant.h"
34#include "llvm/IR/Constants.h"
35#include "llvm/IR/DataLayout.h"
36#include "llvm/IR/InstrTypes.h"
37#include "llvm/IR/Instruction.h"
38#include "llvm/IR/Instructions.h"
39#include "llvm/IR/IntrinsicInst.h"
40#include "llvm/IR/Intrinsics.h"
41#include "llvm/IR/Operator.h"
42#include "llvm/IR/Value.h"
43#include "llvm/Support/Casting.h"
44#include <cstdint>
45
46namespace llvm {
47namespace PatternMatch {
48
49template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
50 return const_cast<Pattern &>(P).match(V);
33
Calling 'IntrinsicID_match::match'
37
Returning from 'IntrinsicID_match::match'
38
Returning zero, which participates in a condition later
42
Calling 'IntrinsicID_match::match'
46
Returning from 'IntrinsicID_match::match'
47
Returning zero, which participates in a condition later
51}
52
53template <typename SubPattern_t> struct OneUse_match {
54 SubPattern_t SubPattern;
55
56 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
57
58 template <typename OpTy> bool match(OpTy *V) {
59 return V->hasOneUse() && SubPattern.match(V);
60 }
61};
62
63template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
64 return SubPattern;
65}
66
67template <typename Class> struct class_match {
68 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
69};
70
71/// Match an arbitrary value and ignore it.
72inline class_match<Value> m_Value() { return class_match<Value>(); }
73
74/// Match an arbitrary binary operation and ignore it.
75inline class_match<BinaryOperator> m_BinOp() {
76 return class_match<BinaryOperator>();
77}
78
79/// Matches any compare instruction and ignore it.
80inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
81
82/// Match an arbitrary ConstantInt and ignore it.
83inline class_match<ConstantInt> m_ConstantInt() {
84 return class_match<ConstantInt>();
85}
86
87/// Match an arbitrary undef constant.
88inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
89
90/// Match an arbitrary Constant and ignore it.
91inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
92
93/// Match an arbitrary basic block value and ignore it.
94inline class_match<BasicBlock> m_BasicBlock() {
95 return class_match<BasicBlock>();
96}
97
98/// Inverting matcher
99template <typename Ty> struct match_unless {
100 Ty M;
101
102 match_unless(const Ty &Matcher) : M(Matcher) {}
103
104 template <typename ITy> bool match(ITy *V) { return !M.match(V); }
105};
106
107/// Match if the inner matcher does *NOT* match.
108template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
109 return match_unless<Ty>(M);
110}
111
112/// Matching combinators
113template <typename LTy, typename RTy> struct match_combine_or {
114 LTy L;
115 RTy R;
116
117 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
118
119 template <typename ITy> bool match(ITy *V) {
120 if (L.match(V))
121 return true;
122 if (R.match(V))
123 return true;
124 return false;
125 }
126};
127
128template <typename LTy, typename RTy> struct match_combine_and {
129 LTy L;
130 RTy R;
131
132 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
133
134 template <typename ITy> bool match(ITy *V) {
135 if (L.match(V))
136 if (R.match(V))
137 return true;
138 return false;
139 }
140};
141
142/// Combine two pattern matchers matching L || R
143template <typename LTy, typename RTy>
144inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
145 return match_combine_or<LTy, RTy>(L, R);
146}
147
148/// Combine two pattern matchers matching L && R
149template <typename LTy, typename RTy>
150inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
151 return match_combine_and<LTy, RTy>(L, R);
152}
153
154struct apint_match {
155 const APInt *&Res;
156 bool AllowUndef;
157
158 apint_match(const APInt *&Res, bool AllowUndef)
159 : Res(Res), AllowUndef(AllowUndef) {}
160
161 template <typename ITy> bool match(ITy *V) {
162 if (auto *CI = dyn_cast<ConstantInt>(V)) {
163 Res = &CI->getValue();
164 return true;
165 }
166 if (V->getType()->isVectorTy())
167 if (const auto *C = dyn_cast<Constant>(V))
168 if (auto *CI = dyn_cast_or_null<ConstantInt>(
169 C->getSplatValue(AllowUndef))) {
170 Res = &CI->getValue();
171 return true;
172 }
173 return false;
174 }
175};
176// Either constexpr if or renaming ConstantFP::getValueAPF to
177// ConstantFP::getValue is needed to do it via single template
178// function for both apint/apfloat.
179struct apfloat_match {
180 const APFloat *&Res;
181 bool AllowUndef;
182
183 apfloat_match(const APFloat *&Res, bool AllowUndef)
184 : Res(Res), AllowUndef(AllowUndef) {}
185
186 template <typename ITy> bool match(ITy *V) {
187 if (auto *CI = dyn_cast<ConstantFP>(V)) {
188 Res = &CI->getValueAPF();
189 return true;
190 }
191 if (V->getType()->isVectorTy())
192 if (const auto *C = dyn_cast<Constant>(V))
193 if (auto *CI = dyn_cast_or_null<ConstantFP>(
194 C->getSplatValue(AllowUndef))) {
195 Res = &CI->getValueAPF();
196 return true;
197 }
198 return false;
199 }
200};
201
202/// Match a ConstantInt or splatted ConstantVector, binding the
203/// specified pointer to the contained APInt.
204inline apint_match m_APInt(const APInt *&Res) {
205 // Forbid undefs by default to maintain previous behavior.
206 return apint_match(Res, /* AllowUndef */ false);
207}
208
209/// Match APInt while allowing undefs in splat vector constants.
210inline apint_match m_APIntAllowUndef(const APInt *&Res) {
211 return apint_match(Res, /* AllowUndef */ true);
212}
213
214/// Match APInt while forbidding undefs in splat vector constants.
215inline apint_match m_APIntForbidUndef(const APInt *&Res) {
216 return apint_match(Res, /* AllowUndef */ false);
217}
218
219/// Match a ConstantFP or splatted ConstantVector, binding the
220/// specified pointer to the contained APFloat.
221inline apfloat_match m_APFloat(const APFloat *&Res) {
222 // Forbid undefs by default to maintain previous behavior.
223 return apfloat_match(Res, /* AllowUndef */ false);
224}
225
226/// Match APFloat while allowing undefs in splat vector constants.
227inline apfloat_match m_APFloatAllowUndef(const APFloat *&Res) {
228 return apfloat_match(Res, /* AllowUndef */ true);
229}
230
231/// Match APFloat while forbidding undefs in splat vector constants.
232inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) {
233 return apfloat_match(Res, /* AllowUndef */ false);
234}
235
236template <int64_t Val> struct constantint_match {
237 template <typename ITy> bool match(ITy *V) {
238 if (const auto *CI = dyn_cast<ConstantInt>(V)) {
239 const APInt &CIV = CI->getValue();
240 if (Val >= 0)
241 return CIV == static_cast<uint64_t>(Val);
242 // If Val is negative, and CI is shorter than it, truncate to the right
243 // number of bits. If it is larger, then we have to sign extend. Just
244 // compare their negated values.
245 return -CIV == -Val;
246 }
247 return false;
248 }
249};
250
251/// Match a ConstantInt with a specific value.
252template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
253 return constantint_match<Val>();
254}
255
256/// This helper class is used to match scalar and vector integer constants that
257/// satisfy a specified predicate.
258/// For vector constants, undefined elements are ignored.
259template <typename Predicate> struct cst_pred_ty : public Predicate {
260 template <typename ITy> bool match(ITy *V) {
261 if (const auto *CI = dyn_cast<ConstantInt>(V))
262 return this->isValue(CI->getValue());
263 if (V->getType()->isVectorTy()) {
264 if (const auto *C = dyn_cast<Constant>(V)) {
265 if (const auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
266 return this->isValue(CI->getValue());
267
268 // Non-splat vector constant: check each element for a match.
269 unsigned NumElts = V->getType()->getVectorNumElements();
270 assert(NumElts != 0 && "Constant vector with no elements?")((NumElts != 0 && "Constant vector with no elements?"
) ? static_cast<void> (0) : __assert_fail ("NumElts != 0 && \"Constant vector with no elements?\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/IR/PatternMatch.h"
, 270, __PRETTY_FUNCTION__))
;
271 bool HasNonUndefElements = false;
272 for (unsigned i = 0; i != NumElts; ++i) {
273 Constant *Elt = C->getAggregateElement(i);
274 if (!Elt)
275 return false;
276 if (isa<UndefValue>(Elt))
277 continue;
278 auto *CI = dyn_cast<ConstantInt>(Elt);
279 if (!CI || !this->isValue(CI->getValue()))
280 return false;
281 HasNonUndefElements = true;
282 }
283 return HasNonUndefElements;
284 }
285 }
286 return false;
287 }
288};
289
290/// This helper class is used to match scalar and vector constants that
291/// satisfy a specified predicate, and bind them to an APInt.
292template <typename Predicate> struct api_pred_ty : public Predicate {
293 const APInt *&Res;
294
295 api_pred_ty(const APInt *&R) : Res(R) {}
296
297 template <typename ITy> bool match(ITy *V) {
298 if (const auto *CI = dyn_cast<ConstantInt>(V))
299 if (this->isValue(CI->getValue())) {
300 Res = &CI->getValue();
301 return true;
302 }
303 if (V->getType()->isVectorTy())
304 if (const auto *C = dyn_cast<Constant>(V))
305 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
306 if (this->isValue(CI->getValue())) {
307 Res = &CI->getValue();
308 return true;
309 }
310
311 return false;
312 }
313};
314
315/// This helper class is used to match scalar and vector floating-point
316/// constants that satisfy a specified predicate.
317/// For vector constants, undefined elements are ignored.
318template <typename Predicate> struct cstfp_pred_ty : public Predicate {
319 template <typename ITy> bool match(ITy *V) {
320 if (const auto *CF = dyn_cast<ConstantFP>(V))
321 return this->isValue(CF->getValueAPF());
322 if (V->getType()->isVectorTy()) {
323 if (const auto *C = dyn_cast<Constant>(V)) {
324 if (const auto *CF = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
325 return this->isValue(CF->getValueAPF());
326
327 // Non-splat vector constant: check each element for a match.
328 unsigned NumElts = V->getType()->getVectorNumElements();
329 assert(NumElts != 0 && "Constant vector with no elements?")((NumElts != 0 && "Constant vector with no elements?"
) ? static_cast<void> (0) : __assert_fail ("NumElts != 0 && \"Constant vector with no elements?\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/IR/PatternMatch.h"
, 329, __PRETTY_FUNCTION__))
;
330 bool HasNonUndefElements = false;
331 for (unsigned i = 0; i != NumElts; ++i) {
332 Constant *Elt = C->getAggregateElement(i);
333 if (!Elt)
334 return false;
335 if (isa<UndefValue>(Elt))
336 continue;
337 auto *CF = dyn_cast<ConstantFP>(Elt);
338 if (!CF || !this->isValue(CF->getValueAPF()))
339 return false;
340 HasNonUndefElements = true;
341 }
342 return HasNonUndefElements;
343 }
344 }
345 return false;
346 }
347};
348
349///////////////////////////////////////////////////////////////////////////////
350//
351// Encapsulate constant value queries for use in templated predicate matchers.
352// This allows checking if constants match using compound predicates and works
353// with vector constants, possibly with relaxed constraints. For example, ignore
354// undef values.
355//
356///////////////////////////////////////////////////////////////////////////////
357
358struct is_any_apint {
359 bool isValue(const APInt &C) { return true; }
360};
361/// Match an integer or vector with any integral constant.
362/// For vectors, this includes constants with undefined elements.
363inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() {
364 return cst_pred_ty<is_any_apint>();
365}
366
367struct is_all_ones {
368 bool isValue(const APInt &C) { return C.isAllOnesValue(); }
369};
370/// Match an integer or vector with all bits set.
371/// For vectors, this includes constants with undefined elements.
372inline cst_pred_ty<is_all_ones> m_AllOnes() {
373 return cst_pred_ty<is_all_ones>();
374}
375
376struct is_maxsignedvalue {
377 bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
378};
379/// Match an integer or vector with values having all bits except for the high
380/// bit set (0x7f...).
381/// For vectors, this includes constants with undefined elements.
382inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
383 return cst_pred_ty<is_maxsignedvalue>();
384}
385inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
386 return V;
387}
388
389struct is_negative {
390 bool isValue(const APInt &C) { return C.isNegative(); }
391};
392/// Match an integer or vector of negative values.
393/// For vectors, this includes constants with undefined elements.
394inline cst_pred_ty<is_negative> m_Negative() {
395 return cst_pred_ty<is_negative>();
396}
397inline api_pred_ty<is_negative> m_Negative(const APInt *&V) {
398 return V;
399}
400
401struct is_nonnegative {
402 bool isValue(const APInt &C) { return C.isNonNegative(); }
403};
404/// Match an integer or vector of non-negative values.
405/// For vectors, this includes constants with undefined elements.
406inline cst_pred_ty<is_nonnegative> m_NonNegative() {
407 return cst_pred_ty<is_nonnegative>();
408}
409inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) {
410 return V;
411}
412
413struct is_strictlypositive {
414 bool isValue(const APInt &C) { return C.isStrictlyPositive(); }
415};
416/// Match an integer or vector of strictly positive values.
417/// For vectors, this includes constants with undefined elements.
418inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() {
419 return cst_pred_ty<is_strictlypositive>();
420}
421inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) {
422 return V;
423}
424
425struct is_nonpositive {
426 bool isValue(const APInt &C) { return C.isNonPositive(); }
427};
428/// Match an integer or vector of non-positive values.
429/// For vectors, this includes constants with undefined elements.
430inline cst_pred_ty<is_nonpositive> m_NonPositive() {
431 return cst_pred_ty<is_nonpositive>();
432}
433inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; }
434
435struct is_one {
436 bool isValue(const APInt &C) { return C.isOneValue(); }
437};
438/// Match an integer 1 or a vector with all elements equal to 1.
439/// For vectors, this includes constants with undefined elements.
440inline cst_pred_ty<is_one> m_One() {
441 return cst_pred_ty<is_one>();
442}
443
444struct is_zero_int {
445 bool isValue(const APInt &C) { return C.isNullValue(); }
446};
447/// Match an integer 0 or a vector with all elements equal to 0.
448/// For vectors, this includes constants with undefined elements.
449inline cst_pred_ty<is_zero_int> m_ZeroInt() {
450 return cst_pred_ty<is_zero_int>();
451}
452
453struct is_zero {
454 template <typename ITy> bool match(ITy *V) {
455 auto *C = dyn_cast<Constant>(V);
456 return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
457 }
458};
459/// Match any null constant or a vector with all elements equal to 0.
460/// For vectors, this includes constants with undefined elements.
461inline is_zero m_Zero() {
462 return is_zero();
463}
464
465struct is_power2 {
466 bool isValue(const APInt &C) { return C.isPowerOf2(); }
467};
468/// Match an integer or vector power-of-2.
469/// For vectors, this includes constants with undefined elements.
470inline cst_pred_ty<is_power2> m_Power2() {
471 return cst_pred_ty<is_power2>();
472}
473inline api_pred_ty<is_power2> m_Power2(const APInt *&V) {
474 return V;
475}
476
477struct is_negated_power2 {
478 bool isValue(const APInt &C) { return (-C).isPowerOf2(); }
479};
480/// Match a integer or vector negated power-of-2.
481/// For vectors, this includes constants with undefined elements.
482inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
483 return cst_pred_ty<is_negated_power2>();
484}
485inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
486 return V;
487}
488
489struct is_power2_or_zero {
490 bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
491};
492/// Match an integer or vector of 0 or power-of-2 values.
493/// For vectors, this includes constants with undefined elements.
494inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
495 return cst_pred_ty<is_power2_or_zero>();
496}
497inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
498 return V;
499}
500
501struct is_sign_mask {
502 bool isValue(const APInt &C) { return C.isSignMask(); }
503};
504/// Match an integer or vector with only the sign bit(s) set.
505/// For vectors, this includes constants with undefined elements.
506inline cst_pred_ty<is_sign_mask> m_SignMask() {
507 return cst_pred_ty<is_sign_mask>();
508}
509
510struct is_lowbit_mask {
511 bool isValue(const APInt &C) { return C.isMask(); }
512};
513/// Match an integer or vector with only the low bit(s) set.
514/// For vectors, this includes constants with undefined elements.
515inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
516 return cst_pred_ty<is_lowbit_mask>();
517}
518
519struct icmp_pred_with_threshold {
520 ICmpInst::Predicate Pred;
521 const APInt *Thr;
522 bool isValue(const APInt &C) {
523 switch (Pred) {
524 case ICmpInst::Predicate::ICMP_EQ:
525 return C.eq(*Thr);
526 case ICmpInst::Predicate::ICMP_NE:
527 return C.ne(*Thr);
528 case ICmpInst::Predicate::ICMP_UGT:
529 return C.ugt(*Thr);
530 case ICmpInst::Predicate::ICMP_UGE:
531 return C.uge(*Thr);
532 case ICmpInst::Predicate::ICMP_ULT:
533 return C.ult(*Thr);
534 case ICmpInst::Predicate::ICMP_ULE:
535 return C.ule(*Thr);
536 case ICmpInst::Predicate::ICMP_SGT:
537 return C.sgt(*Thr);
538 case ICmpInst::Predicate::ICMP_SGE:
539 return C.sge(*Thr);
540 case ICmpInst::Predicate::ICMP_SLT:
541 return C.slt(*Thr);
542 case ICmpInst::Predicate::ICMP_SLE:
543 return C.sle(*Thr);
544 default:
545 llvm_unreachable("Unhandled ICmp predicate")::llvm::llvm_unreachable_internal("Unhandled ICmp predicate",
"/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/IR/PatternMatch.h"
, 545)
;
546 }
547 }
548};
549/// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
550/// to Threshold. For vectors, this includes constants with undefined elements.
551inline cst_pred_ty<icmp_pred_with_threshold>
552m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) {
553 cst_pred_ty<icmp_pred_with_threshold> P;
554 P.Pred = Predicate;
555 P.Thr = &Threshold;
556 return P;
557}
558
559struct is_nan {
560 bool isValue(const APFloat &C) { return C.isNaN(); }
561};
562/// Match an arbitrary NaN constant. This includes quiet and signalling nans.
563/// For vectors, this includes constants with undefined elements.
564inline cstfp_pred_ty<is_nan> m_NaN() {
565 return cstfp_pred_ty<is_nan>();
566}
567
568struct is_any_zero_fp {
569 bool isValue(const APFloat &C) { return C.isZero(); }
570};
571/// Match a floating-point negative zero or positive zero.
572/// For vectors, this includes constants with undefined elements.
573inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
574 return cstfp_pred_ty<is_any_zero_fp>();
575}
576
577struct is_pos_zero_fp {
578 bool isValue(const APFloat &C) { return C.isPosZero(); }
579};
580/// Match a floating-point positive zero.
581/// For vectors, this includes constants with undefined elements.
582inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
583 return cstfp_pred_ty<is_pos_zero_fp>();
584}
585
586struct is_neg_zero_fp {
587 bool isValue(const APFloat &C) { return C.isNegZero(); }
588};
589/// Match a floating-point negative zero.
590/// For vectors, this includes constants with undefined elements.
591inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
592 return cstfp_pred_ty<is_neg_zero_fp>();
593}
594
595///////////////////////////////////////////////////////////////////////////////
596
597template <typename Class> struct bind_ty {
598 Class *&VR;
599
600 bind_ty(Class *&V) : VR(V) {}
601
602 template <typename ITy> bool match(ITy *V) {
603 if (auto *CV = dyn_cast<Class>(V)) {
604 VR = CV;
605 return true;
606 }
607 return false;
608 }
609};
610
611/// Match a value, capturing it if we match.
612inline bind_ty<Value> m_Value(Value *&V) { return V; }
613inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
614
615/// Match an instruction, capturing it if we match.
616inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
617/// Match a binary operator, capturing it if we match.
618inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
619/// Match a with overflow intrinsic, capturing it if we match.
620inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; }
621
622/// Match a ConstantInt, capturing the value if we match.
623inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
624
625/// Match a Constant, capturing the value if we match.
626inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
627
628/// Match a ConstantFP, capturing the value if we match.
629inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
630
631/// Match a basic block value, capturing it if we match.
632inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
633inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
634 return V;
635}
636
637/// Match a specified Value*.
638struct specificval_ty {
639 const Value *Val;
640
641 specificval_ty(const Value *V) : Val(V) {}
642
643 template <typename ITy> bool match(ITy *V) { return V == Val; }
644};
645
646/// Match if we have a specific specified value.
647inline specificval_ty m_Specific(const Value *V) { return V; }
648
649/// Stores a reference to the Value *, not the Value * itself,
650/// thus can be used in commutative matchers.
651template <typename Class> struct deferredval_ty {
652 Class *const &Val;
653
654 deferredval_ty(Class *const &V) : Val(V) {}
655
656 template <typename ITy> bool match(ITy *const V) { return V == Val; }
657};
658
659/// A commutative-friendly version of m_Specific().
660inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
661inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
662 return V;
663}
664
665/// Match a specified floating point value or vector of all elements of
666/// that value.
667struct specific_fpval {
668 double Val;
669
670 specific_fpval(double V) : Val(V) {}
671
672 template <typename ITy> bool match(ITy *V) {
673 if (const auto *CFP = dyn_cast<ConstantFP>(V))
674 return CFP->isExactlyValue(Val);
675 if (V->getType()->isVectorTy())
676 if (const auto *C = dyn_cast<Constant>(V))
677 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
678 return CFP->isExactlyValue(Val);
679 return false;
680 }
681};
682
683/// Match a specific floating point value or vector with all elements
684/// equal to the value.
685inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
686
687/// Match a float 1.0 or vector with all elements equal to 1.0.
688inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
689
690struct bind_const_intval_ty {
691 uint64_t &VR;
692
693 bind_const_intval_ty(uint64_t &V) : VR(V) {}
694
695 template <typename ITy> bool match(ITy *V) {
696 if (const auto *CV = dyn_cast<ConstantInt>(V))
697 if (CV->getValue().ule(UINT64_MAX(18446744073709551615UL))) {
698 VR = CV->getZExtValue();
699 return true;
700 }
701 return false;
702 }
703};
704
705/// Match a specified integer value or vector of all elements of that
706/// value.
707struct specific_intval {
708 APInt Val;
709
710 specific_intval(APInt V) : Val(std::move(V)) {}
711
712 template <typename ITy> bool match(ITy *V) {
713 const auto *CI = dyn_cast<ConstantInt>(V);
714 if (!CI && V->getType()->isVectorTy())
715 if (const auto *C = dyn_cast<Constant>(V))
716 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue());
717
718 return CI && APInt::isSameValue(CI->getValue(), Val);
719 }
720};
721
722/// Match a specific integer value or vector with all elements equal to
723/// the value.
724inline specific_intval m_SpecificInt(APInt V) {
725 return specific_intval(std::move(V));
726}
727
728inline specific_intval m_SpecificInt(uint64_t V) {
729 return m_SpecificInt(APInt(64, V));
730}
731
732/// Match a ConstantInt and bind to its value. This does not match
733/// ConstantInts wider than 64-bits.
734inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
735
736/// Match a specified basic block value.
737struct specific_bbval {
738 BasicBlock *Val;
739
740 specific_bbval(BasicBlock *Val) : Val(Val) {}
741
742 template <typename ITy> bool match(ITy *V) {
743 const auto *BB = dyn_cast<BasicBlock>(V);
744 return BB && BB == Val;
745 }
746};
747
748/// Match a specific basic block value.
749inline specific_bbval m_SpecificBB(BasicBlock *BB) {
750 return specific_bbval(BB);
751}
752
753/// A commutative-friendly version of m_Specific().
754inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
755 return BB;
756}
757inline deferredval_ty<const BasicBlock>
758m_Deferred(const BasicBlock *const &BB) {
759 return BB;
760}
761
762//===----------------------------------------------------------------------===//
763// Matcher for any binary operator.
764//
765template <typename LHS_t, typename RHS_t, bool Commutable = false>
766struct AnyBinaryOp_match {
767 LHS_t L;
768 RHS_t R;
769
770 // The evaluation order is always stable, regardless of Commutability.
771 // The LHS is always matched first.
772 AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
773
774 template <typename OpTy> bool match(OpTy *V) {
775 if (auto *I = dyn_cast<BinaryOperator>(V))
776 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
777 (Commutable && L.match(I->getOperand(1)) &&
778 R.match(I->getOperand(0)));
779 return false;
780 }
781};
782
783template <typename LHS, typename RHS>
784inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
785 return AnyBinaryOp_match<LHS, RHS>(L, R);
786}
787
788//===----------------------------------------------------------------------===//
789// Matchers for specific binary operators.
790//
791
792template <typename LHS_t, typename RHS_t, unsigned Opcode,
793 bool Commutable = false>
794struct BinaryOp_match {
795 LHS_t L;
796 RHS_t R;
797
798 // The evaluation order is always stable, regardless of Commutability.
799 // The LHS is always matched first.
800 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
801
802 template <typename OpTy> bool match(OpTy *V) {
803 if (V->getValueID() == Value::InstructionVal + Opcode) {
804 auto *I = cast<BinaryOperator>(V);
805 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
806 (Commutable && L.match(I->getOperand(1)) &&
807 R.match(I->getOperand(0)));
808 }
809 if (auto *CE = dyn_cast<ConstantExpr>(V))
810 return CE->getOpcode() == Opcode &&
811 ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
812 (Commutable && L.match(CE->getOperand(1)) &&
813 R.match(CE->getOperand(0))));
814 return false;
815 }
816};
817
818template <typename LHS, typename RHS>
819inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
820 const RHS &R) {
821 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
822}
823
824template <typename LHS, typename RHS>
825inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
826 const RHS &R) {
827 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
828}
829
830template <typename LHS, typename RHS>
831inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
832 const RHS &R) {
833 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
834}
835
836template <typename LHS, typename RHS>
837inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
838 const RHS &R) {
839 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
840}
841
842template <typename Op_t> struct FNeg_match {
843 Op_t X;
844
845 FNeg_match(const Op_t &Op) : X(Op) {}
846 template <typename OpTy> bool match(OpTy *V) {
847 auto *FPMO = dyn_cast<FPMathOperator>(V);
848 if (!FPMO) return false;
849
850 if (FPMO->getOpcode() == Instruction::FNeg)
851 return X.match(FPMO->getOperand(0));
852
853 if (FPMO->getOpcode() == Instruction::FSub) {
854 if (FPMO->hasNoSignedZeros()) {
855 // With 'nsz', any zero goes.
856 if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
857 return false;
858 } else {
859 // Without 'nsz', we need fsub -0.0, X exactly.
860 if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
861 return false;
862 }
863
864 return X.match(FPMO->getOperand(1));
865 }
866
867 return false;
868 }
869};
870
871/// Match 'fneg X' as 'fsub -0.0, X'.
872template <typename OpTy>
873inline FNeg_match<OpTy>
874m_FNeg(const OpTy &X) {
875 return FNeg_match<OpTy>(X);
876}
877
878/// Match 'fneg X' as 'fsub +-0.0, X'.
879template <typename RHS>
880inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
881m_FNegNSZ(const RHS &X) {
882 return m_FSub(m_AnyZeroFP(), X);
883}
884
885template <typename LHS, typename RHS>
886inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
887 const RHS &R) {
888 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
889}
890
891template <typename LHS, typename RHS>
892inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
893 const RHS &R) {
894 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
895}
896
897template <typename LHS, typename RHS>
898inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
899 const RHS &R) {
900 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
901}
902
903template <typename LHS, typename RHS>
904inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
905 const RHS &R) {
906 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
907}
908
909template <typename LHS, typename RHS>
910inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
911 const RHS &R) {
912 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
913}
914
915template <typename LHS, typename RHS>
916inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
917 const RHS &R) {
918 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
919}
920
921template <typename LHS, typename RHS>
922inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
923 const RHS &R) {
924 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
925}
926
927template <typename LHS, typename RHS>
928inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
929 const RHS &R) {
930 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
931}
932
933template <typename LHS, typename RHS>
934inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
935 const RHS &R) {
936 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
937}
938
939template <typename LHS, typename RHS>
940inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
941 const RHS &R) {
942 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
943}
944
945template <typename LHS, typename RHS>
946inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
947 const RHS &R) {
948 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
949}
950
951template <typename LHS, typename RHS>
952inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
953 const RHS &R) {
954 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
955}
956
957template <typename LHS, typename RHS>
958inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
959 const RHS &R) {
960 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
961}
962
963template <typename LHS, typename RHS>
964inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
965 const RHS &R) {
966 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
967}
968
969template <typename LHS_t, typename RHS_t, unsigned Opcode,
970 unsigned WrapFlags = 0>
971struct OverflowingBinaryOp_match {
972 LHS_t L;
973 RHS_t R;
974
975 OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
976 : L(LHS), R(RHS) {}
977
978 template <typename OpTy> bool match(OpTy *V) {
979 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
980 if (Op->getOpcode() != Opcode)
981 return false;
982 if (WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap &&
983 !Op->hasNoUnsignedWrap())
984 return false;
985 if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap &&
986 !Op->hasNoSignedWrap())
987 return false;
988 return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
989 }
990 return false;
991 }
992};
993
994template <typename LHS, typename RHS>
995inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
996 OverflowingBinaryOperator::NoSignedWrap>
997m_NSWAdd(const LHS &L, const RHS &R) {
998 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
999 OverflowingBinaryOperator::NoSignedWrap>(
1000 L, R);
1001}
1002template <typename LHS, typename RHS>
1003inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1004 OverflowingBinaryOperator::NoSignedWrap>
1005m_NSWSub(const LHS &L, const RHS &R) {
1006 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1007 OverflowingBinaryOperator::NoSignedWrap>(
1008 L, R);
1009}
1010template <typename LHS, typename RHS>
1011inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1012 OverflowingBinaryOperator::NoSignedWrap>
1013m_NSWMul(const LHS &L, const RHS &R) {
1014 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1015 OverflowingBinaryOperator::NoSignedWrap>(
1016 L, R);
1017}
1018template <typename LHS, typename RHS>
1019inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1020 OverflowingBinaryOperator::NoSignedWrap>
1021m_NSWShl(const LHS &L, const RHS &R) {
1022 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1023 OverflowingBinaryOperator::NoSignedWrap>(
1024 L, R);
1025}
1026
1027template <typename LHS, typename RHS>
1028inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1029 OverflowingBinaryOperator::NoUnsignedWrap>
1030m_NUWAdd(const LHS &L, const RHS &R) {
1031 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1032 OverflowingBinaryOperator::NoUnsignedWrap>(
1033 L, R);
1034}
1035template <typename LHS, typename RHS>
1036inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1037 OverflowingBinaryOperator::NoUnsignedWrap>
1038m_NUWSub(const LHS &L, const RHS &R) {
1039 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1040 OverflowingBinaryOperator::NoUnsignedWrap>(
1041 L, R);
1042}
1043template <typename LHS, typename RHS>
1044inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1045 OverflowingBinaryOperator::NoUnsignedWrap>
1046m_NUWMul(const LHS &L, const RHS &R) {
1047 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1048 OverflowingBinaryOperator::NoUnsignedWrap>(
1049 L, R);
1050}
1051template <typename LHS, typename RHS>
1052inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1053 OverflowingBinaryOperator::NoUnsignedWrap>
1054m_NUWShl(const LHS &L, const RHS &R) {
1055 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1056 OverflowingBinaryOperator::NoUnsignedWrap>(
1057 L, R);
1058}
1059
1060//===----------------------------------------------------------------------===//
1061// Class that matches a group of binary opcodes.
1062//
1063template <typename LHS_t, typename RHS_t, typename Predicate>
1064struct BinOpPred_match : Predicate {
1065 LHS_t L;
1066 RHS_t R;
1067
1068 BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1069
1070 template <typename OpTy> bool match(OpTy *V) {
1071 if (auto *I = dyn_cast<Instruction>(V))
1072 return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
1073 R.match(I->getOperand(1));
1074 if (auto *CE = dyn_cast<ConstantExpr>(V))
1075 return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
1076 R.match(CE->getOperand(1));
1077 return false;
1078 }
1079};
1080
1081struct is_shift_op {
1082 bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
1083};
1084
1085struct is_right_shift_op {
1086 bool isOpType(unsigned Opcode) {
1087 return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
1088 }
1089};
1090
1091struct is_logical_shift_op {
1092 bool isOpType(unsigned Opcode) {
1093 return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
1094 }
1095};
1096
1097struct is_bitwiselogic_op {
1098 bool isOpType(unsigned Opcode) {
1099 return Instruction::isBitwiseLogicOp(Opcode);
1100 }
1101};
1102
1103struct is_idiv_op {
1104 bool isOpType(unsigned Opcode) {
1105 return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
1106 }
1107};
1108
1109struct is_irem_op {
1110 bool isOpType(unsigned Opcode) {
1111 return Opcode == Instruction::SRem || Opcode == Instruction::URem;
1112 }
1113};
1114
1115/// Matches shift operations.
1116template <typename LHS, typename RHS>
1117inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
1118 const RHS &R) {
1119 return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
1120}
1121
1122/// Matches logical shift operations.
1123template <typename LHS, typename RHS>
1124inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L,
1125 const RHS &R) {
1126 return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R);
1127}
1128
1129/// Matches logical shift operations.
1130template <typename LHS, typename RHS>
1131inline BinOpPred_match<LHS, RHS, is_logical_shift_op>
1132m_LogicalShift(const LHS &L, const RHS &R) {
1133 return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R);
1134}
1135
1136/// Matches bitwise logic operations.
1137template <typename LHS, typename RHS>
1138inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op>
1139m_BitwiseLogic(const LHS &L, const RHS &R) {
1140 return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R);
1141}
1142
1143/// Matches integer division operations.
1144template <typename LHS, typename RHS>
1145inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
1146 const RHS &R) {
1147 return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
1148}
1149
1150/// Matches integer remainder operations.
1151template <typename LHS, typename RHS>
1152inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L,
1153 const RHS &R) {
1154 return BinOpPred_match<LHS, RHS, is_irem_op>(L, R);
1155}
1156
1157//===----------------------------------------------------------------------===//
1158// Class that matches exact binary ops.
1159//
1160template <typename SubPattern_t> struct Exact_match {
1161 SubPattern_t SubPattern;
1162
1163 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
1164
1165 template <typename OpTy> bool match(OpTy *V) {
1166 if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
1167 return PEO->isExact() && SubPattern.match(V);
1168 return false;
1169 }
1170};
1171
1172template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
1173 return SubPattern;
1174}
1175
1176//===----------------------------------------------------------------------===//
1177// Matchers for CmpInst classes
1178//
1179
1180template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
1181 bool Commutable = false>
1182struct CmpClass_match {
1183 PredicateTy &Predicate;
1184 LHS_t L;
1185 RHS_t R;
1186
1187 // The evaluation order is always stable, regardless of Commutability.
1188 // The LHS is always matched first.
1189 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
1190 : Predicate(Pred), L(LHS), R(RHS) {}
1191
1192 template <typename OpTy> bool match(OpTy *V) {
1193 if (auto *I = dyn_cast<Class>(V)) {
1194 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
1195 Predicate = I->getPredicate();
1196 return true;
1197 } else if (Commutable && L.match(I->getOperand(1)) &&
1198 R.match(I->getOperand(0))) {
1199 Predicate = I->getSwappedPredicate();
1200 return true;
1201 }
1202 }
1203 return false;
1204 }
1205};
1206
1207template <typename LHS, typename RHS>
1208inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
1209m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1210 return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
1211}
1212
1213template <typename LHS, typename RHS>
1214inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
1215m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1216 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R);
1217}
1218
1219template <typename LHS, typename RHS>
1220inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
1221m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1222 return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
1223}
1224
1225//===----------------------------------------------------------------------===//
1226// Matchers for instructions with a given opcode and number of operands.
1227//
1228
1229/// Matches instructions with Opcode and three operands.
1230template <typename T0, unsigned Opcode> struct OneOps_match {
1231 T0 Op1;
1232
1233 OneOps_match(const T0 &Op1) : Op1(Op1) {}
1234
1235 template <typename OpTy> bool match(OpTy *V) {
1236 if (V->getValueID() == Value::InstructionVal + Opcode) {
1237 auto *I = cast<Instruction>(V);
1238 return Op1.match(I->getOperand(0));
1239 }
1240 return false;
1241 }
1242};
1243
1244/// Matches instructions with Opcode and three operands.
1245template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
1246 T0 Op1;
1247 T1 Op2;
1248
1249 TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
1250
1251 template <typename OpTy> bool match(OpTy *V) {
1252 if (V->getValueID() == Value::InstructionVal + Opcode) {
1253 auto *I = cast<Instruction>(V);
1254 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
1255 }
1256 return false;
1257 }
1258};
1259
1260/// Matches instructions with Opcode and three operands.
1261template <typename T0, typename T1, typename T2, unsigned Opcode>
1262struct ThreeOps_match {
1263 T0 Op1;
1264 T1 Op2;
1265 T2 Op3;
1266
1267 ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
1268 : Op1(Op1), Op2(Op2), Op3(Op3) {}
1269
1270 template <typename OpTy> bool match(OpTy *V) {
1271 if (V->getValueID() == Value::InstructionVal + Opcode) {
1272 auto *I = cast<Instruction>(V);
1273 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1274 Op3.match(I->getOperand(2));
1275 }
1276 return false;
1277 }
1278};
1279
1280/// Matches SelectInst.
1281template <typename Cond, typename LHS, typename RHS>
1282inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
1283m_Select(const Cond &C, const LHS &L, const RHS &R) {
1284 return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
1285}
1286
1287/// This matches a select of two constants, e.g.:
1288/// m_SelectCst<-1, 0>(m_Value(V))
1289template <int64_t L, int64_t R, typename Cond>
1290inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>,
1291 Instruction::Select>
1292m_SelectCst(const Cond &C) {
1293 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
1294}
1295
1296/// Matches FreezeInst.
1297template <typename OpTy>
1298inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) {
1299 return OneOps_match<OpTy, Instruction::Freeze>(Op);
1300}
1301
1302/// Matches InsertElementInst.
1303template <typename Val_t, typename Elt_t, typename Idx_t>
1304inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>
1305m_InsertElement(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
1306 return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
1307 Val, Elt, Idx);
1308}
1309
1310/// Matches ExtractElementInst.
1311template <typename Val_t, typename Idx_t>
1312inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
1313m_ExtractElement(const Val_t &Val, const Idx_t &Idx) {
1314 return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
1315}
1316
1317/// Matches ShuffleVectorInst.
1318template <typename V1_t, typename V2_t, typename Mask_t>
1319inline ThreeOps_match<V1_t, V2_t, Mask_t, Instruction::ShuffleVector>
1320m_ShuffleVector(const V1_t &v1, const V2_t &v2, const Mask_t &m) {
1321 return ThreeOps_match<V1_t, V2_t, Mask_t, Instruction::ShuffleVector>(v1, v2,
1322 m);
1323}
1324
1325/// Matches LoadInst.
1326template <typename OpTy>
1327inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) {
1328 return OneOps_match<OpTy, Instruction::Load>(Op);
1329}
1330
1331/// Matches StoreInst.
1332template <typename ValueOpTy, typename PointerOpTy>
1333inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>
1334m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
1335 return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
1336 PointerOp);
1337}
1338
1339//===----------------------------------------------------------------------===//
1340// Matchers for CastInst classes
1341//
1342
1343template <typename Op_t, unsigned Opcode> struct CastClass_match {
1344 Op_t Op;
1345
1346 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
1347
1348 template <typename OpTy> bool match(OpTy *V) {
1349 if (auto *O = dyn_cast<Operator>(V))
1350 return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
1351 return false;
1352 }
1353};
1354
1355/// Matches BitCast.
1356template <typename OpTy>
1357inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
1358 return CastClass_match<OpTy, Instruction::BitCast>(Op);
1359}
1360
1361/// Matches PtrToInt.
1362template <typename OpTy>
1363inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) {
1364 return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
1365}
1366
1367/// Matches Trunc.
1368template <typename OpTy>
1369inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) {
1370 return CastClass_match<OpTy, Instruction::Trunc>(Op);
1371}
1372
1373template <typename OpTy>
1374inline match_combine_or<CastClass_match<OpTy, Instruction::Trunc>, OpTy>
1375m_TruncOrSelf(const OpTy &Op) {
1376 return m_CombineOr(m_Trunc(Op), Op);
1377}
1378
1379/// Matches SExt.
1380template <typename OpTy>
1381inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) {
1382 return CastClass_match<OpTy, Instruction::SExt>(Op);
1383}
1384
1385/// Matches ZExt.
1386template <typename OpTy>
1387inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) {
1388 return CastClass_match<OpTy, Instruction::ZExt>(Op);
1389}
1390
1391template <typename OpTy>
1392inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, OpTy>
1393m_ZExtOrSelf(const OpTy &Op) {
1394 return m_CombineOr(m_ZExt(Op), Op);
1395}
1396
1397template <typename OpTy>
1398inline match_combine_or<CastClass_match<OpTy, Instruction::SExt>, OpTy>
1399m_SExtOrSelf(const OpTy &Op) {
1400 return m_CombineOr(m_SExt(Op), Op);
1401}
1402
1403template <typename OpTy>
1404inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1405 CastClass_match<OpTy, Instruction::SExt>>
1406m_ZExtOrSExt(const OpTy &Op) {
1407 return m_CombineOr(m_ZExt(Op), m_SExt(Op));
1408}
1409
1410template <typename OpTy>
1411inline match_combine_or<
1412 match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1413 CastClass_match<OpTy, Instruction::SExt>>,
1414 OpTy>
1415m_ZExtOrSExtOrSelf(const OpTy &Op) {
1416 return m_CombineOr(m_ZExtOrSExt(Op), Op);
1417}
1418
1419/// Matches UIToFP.
1420template <typename OpTy>
1421inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) {
1422 return CastClass_match<OpTy, Instruction::UIToFP>(Op);
1423}
1424
1425/// Matches SIToFP.
1426template <typename OpTy>
1427inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) {
1428 return CastClass_match<OpTy, Instruction::SIToFP>(Op);
1429}
1430
1431/// Matches FPTrunc
1432template <typename OpTy>
1433inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) {
1434 return CastClass_match<OpTy, Instruction::FPTrunc>(Op);
1435}
1436
1437/// Matches FPExt
1438template <typename OpTy>
1439inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) {
1440 return CastClass_match<OpTy, Instruction::FPExt>(Op);
1441}
1442
1443//===----------------------------------------------------------------------===//
1444// Matchers for control flow.
1445//
1446
1447struct br_match {
1448 BasicBlock *&Succ;
1449
1450 br_match(BasicBlock *&Succ) : Succ(Succ) {}
1451
1452 template <typename OpTy> bool match(OpTy *V) {
1453 if (auto *BI = dyn_cast<BranchInst>(V))
1454 if (BI->isUnconditional()) {
1455 Succ = BI->getSuccessor(0);
1456 return true;
1457 }
1458 return false;
1459 }
1460};
1461
1462inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1463
1464template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1465struct brc_match {
1466 Cond_t Cond;
1467 TrueBlock_t T;
1468 FalseBlock_t F;
1469
1470 brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
1471 : Cond(C), T(t), F(f) {}
1472
1473 template <typename OpTy> bool match(OpTy *V) {
1474 if (auto *BI = dyn_cast<BranchInst>(V))
1475 if (BI->isConditional() && Cond.match(BI->getCondition()))
1476 return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
1477 return false;
1478 }
1479};
1480
1481template <typename Cond_t>
1482inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
1483m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1484 return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
1485 C, m_BasicBlock(T), m_BasicBlock(F));
1486}
1487
1488template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1489inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t>
1490m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
1491 return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F);
1492}
1493
1494//===----------------------------------------------------------------------===//
1495// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1496//
1497
1498template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1499 bool Commutable = false>
1500struct MaxMin_match {
1501 LHS_t L;
1502 RHS_t R;
1503
1504 // The evaluation order is always stable, regardless of Commutability.
1505 // The LHS is always matched first.
1506 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1507
1508 template <typename OpTy> bool match(OpTy *V) {
1509 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1510 auto *SI = dyn_cast<SelectInst>(V);
1511 if (!SI)
1512 return false;
1513 auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1514 if (!Cmp)
1515 return false;
1516 // At this point we have a select conditioned on a comparison. Check that
1517 // it is the values returned by the select that are being compared.
1518 Value *TrueVal = SI->getTrueValue();
1519 Value *FalseVal = SI->getFalseValue();
1520 Value *LHS = Cmp->getOperand(0);
1521 Value *RHS = Cmp->getOperand(1);
1522 if ((TrueVal != LHS || FalseVal != RHS) &&
1523 (TrueVal != RHS || FalseVal != LHS))
1524 return false;
1525 typename CmpInst_t::Predicate Pred =
1526 LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1527 // Does "(x pred y) ? x : y" represent the desired max/min operation?
1528 if (!Pred_t::match(Pred))
1529 return false;
1530 // It does! Bind the operands.
1531 return (L.match(LHS) && R.match(RHS)) ||
1532 (Commutable && L.match(RHS) && R.match(LHS));
1533 }
1534};
1535
1536/// Helper class for identifying signed max predicates.
1537struct smax_pred_ty {
1538 static bool match(ICmpInst::Predicate Pred) {
1539 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1540 }
1541};
1542
1543/// Helper class for identifying signed min predicates.
1544struct smin_pred_ty {
1545 static bool match(ICmpInst::Predicate Pred) {
1546 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1547 }
1548};
1549
1550/// Helper class for identifying unsigned max predicates.
1551struct umax_pred_ty {
1552 static bool match(ICmpInst::Predicate Pred) {
1553 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1554 }
1555};
1556
1557/// Helper class for identifying unsigned min predicates.
1558struct umin_pred_ty {
1559 static bool match(ICmpInst::Predicate Pred) {
1560 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1561 }
1562};
1563
1564/// Helper class for identifying ordered max predicates.
1565struct ofmax_pred_ty {
1566 static bool match(FCmpInst::Predicate Pred) {
1567 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1568 }
1569};
1570
1571/// Helper class for identifying ordered min predicates.
1572struct ofmin_pred_ty {
1573 static bool match(FCmpInst::Predicate Pred) {
1574 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1575 }
1576};
1577
1578/// Helper class for identifying unordered max predicates.
1579struct ufmax_pred_ty {
1580 static bool match(FCmpInst::Predicate Pred) {
1581 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1582 }
1583};
1584
1585/// Helper class for identifying unordered min predicates.
1586struct ufmin_pred_ty {
1587 static bool match(FCmpInst::Predicate Pred) {
1588 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1589 }
1590};
1591
1592template <typename LHS, typename RHS>
1593inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
1594 const RHS &R) {
1595 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
1596}
1597
1598template <typename LHS, typename RHS>
1599inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L,
1600 const RHS &R) {
1601 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R);
1602}
1603
1604template <typename LHS, typename RHS>
1605inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L,
1606 const RHS &R) {
1607 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R);
1608}
1609
1610template <typename LHS, typename RHS>
1611inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L,
1612 const RHS &R) {
1613 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R);
1614}
1615
1616/// Match an 'ordered' floating point maximum function.
1617/// Floating point has one special value 'NaN'. Therefore, there is no total
1618/// order. However, if we can ignore the 'NaN' value (for example, because of a
1619/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1620/// semantics. In the presence of 'NaN' we have to preserve the original
1621/// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1622///
1623/// max(L, R) iff L and R are not NaN
1624/// m_OrdFMax(L, R) = R iff L or R are NaN
1625template <typename LHS, typename RHS>
1626inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
1627 const RHS &R) {
1628 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
1629}
1630
1631/// Match an 'ordered' floating point minimum function.
1632/// Floating point has one special value 'NaN'. Therefore, there is no total
1633/// order. However, if we can ignore the 'NaN' value (for example, because of a
1634/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1635/// semantics. In the presence of 'NaN' we have to preserve the original
1636/// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1637///
1638/// min(L, R) iff L and R are not NaN
1639/// m_OrdFMin(L, R) = R iff L or R are NaN
1640template <typename LHS, typename RHS>
1641inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
1642 const RHS &R) {
1643 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
1644}
1645
1646/// Match an 'unordered' floating point maximum function.
1647/// Floating point has one special value 'NaN'. Therefore, there is no total
1648/// order. However, if we can ignore the 'NaN' value (for example, because of a
1649/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1650/// semantics. In the presence of 'NaN' we have to preserve the original
1651/// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1652///
1653/// max(L, R) iff L and R are not NaN
1654/// m_UnordFMax(L, R) = L iff L or R are NaN
1655template <typename LHS, typename RHS>
1656inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
1657m_UnordFMax(const LHS &L, const RHS &R) {
1658 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
1659}
1660
1661/// Match an 'unordered' floating point minimum function.
1662/// Floating point has one special value 'NaN'. Therefore, there is no total
1663/// order. However, if we can ignore the 'NaN' value (for example, because of a
1664/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1665/// semantics. In the presence of 'NaN' we have to preserve the original
1666/// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1667///
1668/// min(L, R) iff L and R are not NaN
1669/// m_UnordFMin(L, R) = L iff L or R are NaN
1670template <typename LHS, typename RHS>
1671inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
1672m_UnordFMin(const LHS &L, const RHS &R) {
1673 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
1674}
1675
1676//===----------------------------------------------------------------------===//
1677// Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b
1678// Note that S might be matched to other instructions than AddInst.
1679//
1680
1681template <typename LHS_t, typename RHS_t, typename Sum_t>
1682struct UAddWithOverflow_match {
1683 LHS_t L;
1684 RHS_t R;
1685 Sum_t S;
1686
1687 UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1688 : L(L), R(R), S(S) {}
1689
1690 template <typename OpTy> bool match(OpTy *V) {
1691 Value *ICmpLHS, *ICmpRHS;
1692 ICmpInst::Predicate Pred;
1693 if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1694 return false;
1695
1696 Value *AddLHS, *AddRHS;
1697 auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1698
1699 // (a + b) u< a, (a + b) u< b
1700 if (Pred == ICmpInst::ICMP_ULT)
1701 if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1702 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1703
1704 // a >u (a + b), b >u (a + b)
1705 if (Pred == ICmpInst::ICMP_UGT)
1706 if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1707 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1708
1709 Value *Op1;
1710 auto XorExpr = m_OneUse(m_Xor(m_Value(Op1), m_AllOnes()));
1711 // (a ^ -1) <u b
1712 if (Pred == ICmpInst::ICMP_ULT) {
1713 if (XorExpr.match(ICmpLHS))
1714 return L.match(Op1) && R.match(ICmpRHS) && S.match(ICmpLHS);
1715 }
1716 // b > u (a ^ -1)
1717 if (Pred == ICmpInst::ICMP_UGT) {
1718 if (XorExpr.match(ICmpRHS))
1719 return L.match(Op1) && R.match(ICmpLHS) && S.match(ICmpRHS);
1720 }
1721
1722 // Match special-case for increment-by-1.
1723 if (Pred == ICmpInst::ICMP_EQ) {
1724 // (a + 1) == 0
1725 // (1 + a) == 0
1726 if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
1727 (m_One().match(AddLHS) || m_One().match(AddRHS)))
1728 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1729 // 0 == (a + 1)
1730 // 0 == (1 + a)
1731 if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
1732 (m_One().match(AddLHS) || m_One().match(AddRHS)))
1733 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1734 }
1735
1736 return false;
1737 }
1738};
1739
1740/// Match an icmp instruction checking for unsigned overflow on addition.
1741///
1742/// S is matched to the addition whose result is being checked for overflow, and
1743/// L and R are matched to the LHS and RHS of S.
1744template <typename LHS_t, typename RHS_t, typename Sum_t>
1745UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
1746m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
1747 return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
1748}
1749
1750template <typename Opnd_t> struct Argument_match {
1751 unsigned OpI;
1752 Opnd_t Val;
1753
1754 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
1755
1756 template <typename OpTy> bool match(OpTy *V) {
1757 // FIXME: Should likely be switched to use `CallBase`.
1758 if (const auto *CI = dyn_cast<CallInst>(V))
1759 return Val.match(CI->getArgOperand(OpI));
1760 return false;
1761 }
1762};
1763
1764/// Match an argument.
1765template <unsigned OpI, typename Opnd_t>
1766inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
1767 return Argument_match<Opnd_t>(OpI, Op);
1768}
1769
1770/// Intrinsic matchers.
1771struct IntrinsicID_match {
1772 unsigned ID;
1773
1774 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
1775
1776 template <typename OpTy> bool match(OpTy *V) {
1777 if (const auto *CI
34.1
'CI' is null
43.1
'CI' is null
34.1
'CI' is null
43.1
'CI' is null
34.1
'CI' is null
43.1
'CI' is null
= dyn_cast<CallInst>(V))
34
Assuming 'V' is not a 'CallInst'
35
Taking false branch
43
'V' is not a 'CallInst'
44
Taking false branch
1778 if (const auto *F = CI->getCalledFunction())
1779 return F->getIntrinsicID() == ID;
1780 return false;
36
Returning zero, which participates in a condition later
45
Returning zero, which participates in a condition later
1781 }
1782};
1783
1784/// Intrinsic matches are combinations of ID matchers, and argument
1785/// matchers. Higher arity matcher are defined recursively in terms of and-ing
1786/// them with lower arity matchers. Here's some convenient typedefs for up to
1787/// several arguments, and more can be added as needed
1788template <typename T0 = void, typename T1 = void, typename T2 = void,
1789 typename T3 = void, typename T4 = void, typename T5 = void,
1790 typename T6 = void, typename T7 = void, typename T8 = void,
1791 typename T9 = void, typename T10 = void>
1792struct m_Intrinsic_Ty;
1793template <typename T0> struct m_Intrinsic_Ty<T0> {
1794 using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>;
1795};
1796template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
1797 using Ty =
1798 match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>;
1799};
1800template <typename T0, typename T1, typename T2>
1801struct m_Intrinsic_Ty<T0, T1, T2> {
1802 using Ty =
1803 match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty,
1804 Argument_match<T2>>;
1805};
1806template <typename T0, typename T1, typename T2, typename T3>
1807struct m_Intrinsic_Ty<T0, T1, T2, T3> {
1808 using Ty =
1809 match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty,
1810 Argument_match<T3>>;
1811};
1812
1813template <typename T0, typename T1, typename T2, typename T3, typename T4>
1814struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> {
1815 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty,
1816 Argument_match<T4>>;
1817};
1818
1819/// Match intrinsic calls like this:
1820/// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
1821template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
1822 return IntrinsicID_match(IntrID);
1823}
1824
1825template <Intrinsic::ID IntrID, typename T0>
1826inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
1827 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
1828}
1829
1830template <Intrinsic::ID IntrID, typename T0, typename T1>
1831inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
1832 const T1 &Op1) {
1833 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
1834}
1835
1836template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
1837inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
1838m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
1839 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
1840}
1841
1842template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1843 typename T3>
1844inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
1845m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
1846 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
1847}
1848
1849template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1850 typename T3, typename T4>
1851inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty
1852m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
1853 const T4 &Op4) {
1854 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3),
1855 m_Argument<4>(Op4));
1856}
1857
1858// Helper intrinsic matching specializations.
1859template <typename Opnd0>
1860inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
1861 return m_Intrinsic<Intrinsic::bitreverse>(Op0);
1862}
1863
1864template <typename Opnd0>
1865inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
1866 return m_Intrinsic<Intrinsic::bswap>(Op0);
1867}
1868
1869template <typename Opnd0>
1870inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
1871 return m_Intrinsic<Intrinsic::fabs>(Op0);
1872}
1873
1874template <typename Opnd0>
1875inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
1876 return m_Intrinsic<Intrinsic::canonicalize>(Op0);
1877}
1878
1879template <typename Opnd0, typename Opnd1>
1880inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
1881 const Opnd1 &Op1) {
1882 return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
1883}
1884
1885template <typename Opnd0, typename Opnd1>
1886inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
1887 const Opnd1 &Op1) {
1888 return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
1889}
1890
1891//===----------------------------------------------------------------------===//
1892// Matchers for two-operands operators with the operators in either order
1893//
1894
1895/// Matches a BinaryOperator with LHS and RHS in either order.
1896template <typename LHS, typename RHS>
1897inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
1898 return AnyBinaryOp_match<LHS, RHS, true>(L, R);
1899}
1900
1901/// Matches an ICmp with a predicate over LHS and RHS in either order.
1902/// Swaps the predicate if operands are commuted.
1903template <typename LHS, typename RHS>
1904inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
1905m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1906 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
1907 R);
1908}
1909
1910/// Matches a Add with LHS and RHS in either order.
1911template <typename LHS, typename RHS>
1912inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
1913 const RHS &R) {
1914 return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
1915}
1916
1917/// Matches a Mul with LHS and RHS in either order.
1918template <typename LHS, typename RHS>
1919inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
1920 const RHS &R) {
1921 return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
1922}
1923
1924/// Matches an And with LHS and RHS in either order.
1925template <typename LHS, typename RHS>
1926inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
1927 const RHS &R) {
1928 return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
1929}
1930
1931/// Matches an Or with LHS and RHS in either order.
1932template <typename LHS, typename RHS>
1933inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
1934 const RHS &R) {
1935 return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
1936}
1937
1938/// Matches an Xor with LHS and RHS in either order.
1939template <typename LHS, typename RHS>
1940inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
1941 const RHS &R) {
1942 return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
1943}
1944
1945/// Matches a 'Neg' as 'sub 0, V'.
1946template <typename ValTy>
1947inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
1948m_Neg(const ValTy &V) {
1949 return m_Sub(m_ZeroInt(), V);
1950}
1951
1952/// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
1953template <typename ValTy>
1954inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
1955m_Not(const ValTy &V) {
1956 return m_c_Xor(V, m_AllOnes());
1957}
1958
1959/// Matches an SMin with LHS and RHS in either order.
1960template <typename LHS, typename RHS>
1961inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
1962m_c_SMin(const LHS &L, const RHS &R) {
1963 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
1964}
1965/// Matches an SMax with LHS and RHS in either order.
1966template <typename LHS, typename RHS>
1967inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
1968m_c_SMax(const LHS &L, const RHS &R) {
1969 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
1970}
1971/// Matches a UMin with LHS and RHS in either order.
1972template <typename LHS, typename RHS>
1973inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
1974m_c_UMin(const LHS &L, const RHS &R) {
1975 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
1976}
1977/// Matches a UMax with LHS and RHS in either order.
1978template <typename LHS, typename RHS>
1979inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
1980m_c_UMax(const LHS &L, const RHS &R) {
1981 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
1982}
1983
1984/// Matches FAdd with LHS and RHS in either order.
1985template <typename LHS, typename RHS>
1986inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
1987m_c_FAdd(const LHS &L, const RHS &R) {
1988 return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
1989}
1990
1991/// Matches FMul with LHS and RHS in either order.
1992template <typename LHS, typename RHS>
1993inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
1994m_c_FMul(const LHS &L, const RHS &R) {
1995 return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
1996}
1997
1998template <typename Opnd_t> struct Signum_match {
1999 Opnd_t Val;
2000 Signum_match(const Opnd_t &V) : Val(V) {}
2001
2002 template <typename OpTy> bool match(OpTy *V) {
2003 unsigned TypeSize = V->getType()->getScalarSizeInBits();
2004 if (TypeSize == 0)
2005 return false;
2006
2007 unsigned ShiftWidth = TypeSize - 1;
2008 Value *OpL = nullptr, *OpR = nullptr;
2009
2010 // This is the representation of signum we match:
2011 //
2012 // signum(x) == (x >> 63) | (-x >>u 63)
2013 //
2014 // An i1 value is its own signum, so it's correct to match
2015 //
2016 // signum(x) == (x >> 0) | (-x >>u 0)
2017 //
2018 // for i1 values.
2019
2020 auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
2021 auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
2022 auto Signum = m_Or(LHS, RHS);
2023
2024 return Signum.match(V) && OpL == OpR && Val.match(OpL);
2025 }
2026};
2027
2028/// Matches a signum pattern.
2029///
2030/// signum(x) =
2031/// x > 0 -> 1
2032/// x == 0 -> 0
2033/// x < 0 -> -1
2034template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
2035 return Signum_match<Val_t>(V);
2036}
2037
2038template <int Ind, typename Opnd_t> struct ExtractValue_match {
2039 Opnd_t Val;
2040 ExtractValue_match(const Opnd_t &V) : Val(V) {}
2041
2042 template <typename OpTy> bool match(OpTy *V) {
2043 if (auto *I = dyn_cast<ExtractValueInst>(V))
2044 return I->getNumIndices() == 1 && I->getIndices()[0] == Ind &&
2045 Val.match(I->getAggregateOperand());
2046 return false;
2047 }
2048};
2049
2050/// Match a single index ExtractValue instruction.
2051/// For example m_ExtractValue<1>(...)
2052template <int Ind, typename Val_t>
2053inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) {
2054 return ExtractValue_match<Ind, Val_t>(V);
2055}
2056
2057/// Matches patterns for `vscale`. This can either be a call to `llvm.vscale` or
2058/// the constant expression
2059/// `ptrtoint(gep <vscale x 1 x i8>, <vscale x 1 x i8>* null, i32 1>`
2060/// under the right conditions determined by DataLayout.
2061struct VScaleVal_match {
2062private:
2063 template <typename Base, typename Offset>
2064 inline BinaryOp_match<Base, Offset, Instruction::GetElementPtr>
2065 m_OffsetGep(const Base &B, const Offset &O) {
2066 return BinaryOp_match<Base, Offset, Instruction::GetElementPtr>(B, O);
2067 }
2068
2069public:
2070 const DataLayout &DL;
2071 VScaleVal_match(const DataLayout &DL) : DL(DL) {}
2072
2073 template <typename ITy> bool match(ITy *V) {
2074 if (m_Intrinsic<Intrinsic::vscale>().match(V))
2075 return true;
2076
2077 if (m_PtrToInt(m_OffsetGep(m_Zero(), m_SpecificInt(1))).match(V)) {
2078 Type *PtrTy = cast<Operator>(V)->getOperand(0)->getType();
2079 Type *DerefTy = PtrTy->getPointerElementType();
2080 if (DerefTy->isVectorTy() && DerefTy->getVectorIsScalable() &&
2081 DL.getTypeAllocSizeInBits(DerefTy).getKnownMinSize() == 8)
2082 return true;
2083 }
2084
2085 return false;
2086 }
2087};
2088
2089inline VScaleVal_match m_VScale(const DataLayout &DL) {
2090 return VScaleVal_match(DL);
2091}
2092
2093} // end namespace PatternMatch
2094} // end namespace llvm
2095
2096#endif // LLVM_IR_PATTERNMATCH_H

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Analysis/AliasAnalysis.h

1//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
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 file defines the generic AliasAnalysis interface, which is used as the
10// common interface used by all clients of alias analysis information, and
11// implemented by all alias analysis implementations. Mod/Ref information is
12// also captured by this interface.
13//
14// Implementations of this interface must implement the various virtual methods,
15// which automatically provides functionality for the entire suite of client
16// APIs.
17//
18// This API identifies memory regions with the MemoryLocation class. The pointer
19// component specifies the base memory address of the region. The Size specifies
20// the maximum size (in address units) of the memory region, or
21// MemoryLocation::UnknownSize if the size is not known. The TBAA tag
22// identifies the "type" of the memory reference; see the
23// TypeBasedAliasAnalysis class for details.
24//
25// Some non-obvious details include:
26// - Pointers that point to two completely different objects in memory never
27// alias, regardless of the value of the Size component.
28// - NoAlias doesn't imply inequal pointers. The most obvious example of this
29// is two pointers to constant memory. Even if they are equal, constant
30// memory is never stored to, so there will never be any dependencies.
31// In this and other situations, the pointers may be both NoAlias and
32// MustAlias at the same time. The current API can only return one result,
33// though this is rarely a problem in practice.
34//
35//===----------------------------------------------------------------------===//
36
37#ifndef LLVM_ANALYSIS_ALIASANALYSIS_H
38#define LLVM_ANALYSIS_ALIASANALYSIS_H
39
40#include "llvm/ADT/DenseMap.h"
41#include "llvm/ADT/None.h"
42#include "llvm/ADT/Optional.h"
43#include "llvm/ADT/SmallVector.h"
44#include "llvm/Analysis/MemoryLocation.h"
45#include "llvm/Analysis/TargetLibraryInfo.h"
46#include "llvm/IR/Function.h"
47#include "llvm/IR/Instruction.h"
48#include "llvm/IR/Instructions.h"
49#include "llvm/IR/PassManager.h"
50#include "llvm/Pass.h"
51#include <cstdint>
52#include <functional>
53#include <memory>
54#include <vector>
55
56namespace llvm {
57
58class AnalysisUsage;
59class BasicAAResult;
60class BasicBlock;
61class DominatorTree;
62class Value;
63
64/// The possible results of an alias query.
65///
66/// These results are always computed between two MemoryLocation objects as
67/// a query to some alias analysis.
68///
69/// Note that these are unscoped enumerations because we would like to support
70/// implicitly testing a result for the existence of any possible aliasing with
71/// a conversion to bool, but an "enum class" doesn't support this. The
72/// canonical names from the literature are suffixed and unique anyways, and so
73/// they serve as global constants in LLVM for these results.
74///
75/// See docs/AliasAnalysis.html for more information on the specific meanings
76/// of these values.
77enum AliasResult : uint8_t {
78 /// The two locations do not alias at all.
79 ///
80 /// This value is arranged to convert to false, while all other values
81 /// convert to true. This allows a boolean context to convert the result to
82 /// a binary flag indicating whether there is the possibility of aliasing.
83 NoAlias = 0,
84 /// The two locations may or may not alias. This is the least precise result.
85 MayAlias,
86 /// The two locations alias, but only due to a partial overlap.
87 PartialAlias,
88 /// The two locations precisely alias each other.
89 MustAlias,
90};
91
92/// << operator for AliasResult.
93raw_ostream &operator<<(raw_ostream &OS, AliasResult AR);
94
95/// Flags indicating whether a memory access modifies or references memory.
96///
97/// This is no access at all, a modification, a reference, or both
98/// a modification and a reference. These are specifically structured such that
99/// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must'
100/// work with any of the possible values.
101enum class ModRefInfo : uint8_t {
102 /// Must is provided for completeness, but no routines will return only
103 /// Must today. See definition of Must below.
104 Must = 0,
105 /// The access may reference the value stored in memory,
106 /// a mustAlias relation was found, and no mayAlias or partialAlias found.
107 MustRef = 1,
108 /// The access may modify the value stored in memory,
109 /// a mustAlias relation was found, and no mayAlias or partialAlias found.
110 MustMod = 2,
111 /// The access may reference, modify or both the value stored in memory,
112 /// a mustAlias relation was found, and no mayAlias or partialAlias found.
113 MustModRef = MustRef | MustMod,
114 /// The access neither references nor modifies the value stored in memory.
115 NoModRef = 4,
116 /// The access may reference the value stored in memory.
117 Ref = NoModRef | MustRef,
118 /// The access may modify the value stored in memory.
119 Mod = NoModRef | MustMod,
120 /// The access may reference and may modify the value stored in memory.
121 ModRef = Ref | Mod,
122
123 /// About Must:
124 /// Must is set in a best effort manner.
125 /// We usually do not try our best to infer Must, instead it is merely
126 /// another piece of "free" information that is presented when available.
127 /// Must set means there was certainly a MustAlias found. For calls,
128 /// where multiple arguments are checked (argmemonly), this translates to
129 /// only MustAlias or NoAlias was found.
130 /// Must is not set for RAR accesses, even if the two locations must
131 /// alias. The reason is that two read accesses translate to an early return
132 /// of NoModRef. An additional alias check to set Must may be
133 /// expensive. Other cases may also not set Must(e.g. callCapturesBefore).
134 /// We refer to Must being *set* when the most significant bit is *cleared*.
135 /// Conversely we *clear* Must information by *setting* the Must bit to 1.
136};
137
138LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isNoModRef(const ModRefInfo MRI) {
139 return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
140 static_cast<int>(ModRefInfo::Must);
141}
142LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isModOrRefSet(const ModRefInfo MRI) {
143 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef);
144}
145LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isModAndRefSet(const ModRefInfo MRI) {
146 return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
147 static_cast<int>(ModRefInfo::MustModRef);
148}
149LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isModSet(const ModRefInfo MRI) {
150 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod);
151}
152LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isRefSet(const ModRefInfo MRI) {
153 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef);
154}
155LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isMustSet(const ModRefInfo MRI) {
156 return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef));
157}
158
159LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setMod(const ModRefInfo MRI) {
160 return ModRefInfo(static_cast<int>(MRI) |
161 static_cast<int>(ModRefInfo::MustMod));
162}
163LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setRef(const ModRefInfo MRI) {
164 return ModRefInfo(static_cast<int>(MRI) |
165 static_cast<int>(ModRefInfo::MustRef));
166}
167LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setMust(const ModRefInfo MRI) {
168 return ModRefInfo(static_cast<int>(MRI) &
169 static_cast<int>(ModRefInfo::MustModRef));
170}
171LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setModAndRef(const ModRefInfo MRI) {
172 return ModRefInfo(static_cast<int>(MRI) |
173 static_cast<int>(ModRefInfo::MustModRef));
174}
175LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo clearMod(const ModRefInfo MRI) {
176 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref));
177}
178LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo clearRef(const ModRefInfo MRI) {
179 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod));
180}
181LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo clearMust(const ModRefInfo MRI) {
182 return ModRefInfo(static_cast<int>(MRI) |
183 static_cast<int>(ModRefInfo::NoModRef));
184}
185LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo unionModRef(const ModRefInfo MRI1,
186 const ModRefInfo MRI2) {
187 return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2));
188}
189LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo intersectModRef(const ModRefInfo MRI1,
190 const ModRefInfo MRI2) {
191 return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2));
192}
193
194/// The locations at which a function might access memory.
195///
196/// These are primarily used in conjunction with the \c AccessKind bits to
197/// describe both the nature of access and the locations of access for a
198/// function call.
199enum FunctionModRefLocation {
200 /// Base case is no access to memory.
201 FMRL_Nowhere = 0,
202 /// Access to memory via argument pointers.
203 FMRL_ArgumentPointees = 8,
204 /// Memory that is inaccessible via LLVM IR.
205 FMRL_InaccessibleMem = 16,
206 /// Access to any memory.
207 FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees
208};
209
210/// Summary of how a function affects memory in the program.
211///
212/// Loads from constant globals are not considered memory accesses for this
213/// interface. Also, functions may freely modify stack space local to their
214/// invocation without having to report it through these interfaces.
215enum FunctionModRefBehavior {
216 /// This function does not perform any non-local loads or stores to memory.
217 ///
218 /// This property corresponds to the GCC 'const' attribute.
219 /// This property corresponds to the LLVM IR 'readnone' attribute.
220 /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
221 FMRB_DoesNotAccessMemory =
222 FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef),
223
224 /// The only memory references in this function (if it has any) are
225 /// non-volatile loads from objects pointed to by its pointer-typed
226 /// arguments, with arbitrary offsets.
227 ///
228 /// This property corresponds to the combination of the IntrReadMem
229 /// and IntrArgMemOnly LLVM intrinsic flags.
230 FMRB_OnlyReadsArgumentPointees =
231 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref),
232
233 /// The only memory references in this function (if it has any) are
234 /// non-volatile stores from objects pointed to by its pointer-typed
235 /// arguments, with arbitrary offsets.
236 ///
237 /// This property corresponds to the combination of the IntrWriteMem
238 /// and IntrArgMemOnly LLVM intrinsic flags.
239 FMRB_OnlyWritesArgumentPointees =
240 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Mod),
241
242 /// The only memory references in this function (if it has any) are
243 /// non-volatile loads and stores from objects pointed to by its
244 /// pointer-typed arguments, with arbitrary offsets.
245 ///
246 /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag.
247 FMRB_OnlyAccessesArgumentPointees =
248 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef),
249
250 /// The only memory references in this function (if it has any) are
251 /// reads of memory that is otherwise inaccessible via LLVM IR.
252 ///
253 /// This property corresponds to the LLVM IR inaccessiblememonly attribute.
254 FMRB_OnlyReadsInaccessibleMem =
255 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Ref),
256
257 /// The only memory references in this function (if it has any) are
258 /// writes to memory that is otherwise inaccessible via LLVM IR.
259 ///
260 /// This property corresponds to the LLVM IR inaccessiblememonly attribute.
261 FMRB_OnlyWritesInaccessibleMem =
262 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Mod),
263
264 /// The only memory references in this function (if it has any) are
265 /// references of memory that is otherwise inaccessible via LLVM IR.
266 ///
267 /// This property corresponds to the LLVM IR inaccessiblememonly attribute.
268 FMRB_OnlyAccessesInaccessibleMem =
269 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef),
270
271 /// The function may perform non-volatile loads from objects pointed
272 /// to by its pointer-typed arguments, with arbitrary offsets, and
273 /// it may also perform loads of memory that is otherwise
274 /// inaccessible via LLVM IR.
275 ///
276 /// This property corresponds to the LLVM IR
277 /// inaccessiblemem_or_argmemonly attribute.
278 FMRB_OnlyReadsInaccessibleOrArgMem = FMRL_InaccessibleMem |
279 FMRL_ArgumentPointees |
280 static_cast<int>(ModRefInfo::Ref),
281
282 /// The function may perform non-volatile stores to objects pointed
283 /// to by its pointer-typed arguments, with arbitrary offsets, and
284 /// it may also perform stores of memory that is otherwise
285 /// inaccessible via LLVM IR.
286 ///
287 /// This property corresponds to the LLVM IR
288 /// inaccessiblemem_or_argmemonly attribute.
289 FMRB_OnlyWritesInaccessibleOrArgMem = FMRL_InaccessibleMem |
290 FMRL_ArgumentPointees |
291 static_cast<int>(ModRefInfo::Mod),
292
293 /// The function may perform non-volatile loads and stores of objects
294 /// pointed to by its pointer-typed arguments, with arbitrary offsets, and
295 /// it may also perform loads and stores of memory that is otherwise
296 /// inaccessible via LLVM IR.
297 ///
298 /// This property corresponds to the LLVM IR
299 /// inaccessiblemem_or_argmemonly attribute.
300 FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem |
301 FMRL_ArgumentPointees |
302 static_cast<int>(ModRefInfo::ModRef),
303
304 /// This function does not perform any non-local stores or volatile loads,
305 /// but may read from any memory location.
306 ///
307 /// This property corresponds to the GCC 'pure' attribute.
308 /// This property corresponds to the LLVM IR 'readonly' attribute.
309 /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
310 FMRB_OnlyReadsMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Ref),
311
312 // This function does not read from memory anywhere, but may write to any
313 // memory location.
314 //
315 // This property corresponds to the LLVM IR 'writeonly' attribute.
316 // This property corresponds to the IntrWriteMem LLVM intrinsic flag.
317 FMRB_OnlyWritesMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Mod),
318
319 /// This indicates that the function could not be classified into one of the
320 /// behaviors above.
321 FMRB_UnknownModRefBehavior =
322 FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef)
323};
324
325// Wrapper method strips bits significant only in FunctionModRefBehavior,
326// to obtain a valid ModRefInfo. The benefit of using the wrapper is that if
327// ModRefInfo enum changes, the wrapper can be updated to & with the new enum
328// entry with all bits set to 1.
329LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo
330createModRefInfo(const FunctionModRefBehavior FMRB) {
331 return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef));
332}
333
334/// This class stores info we want to provide to or retain within an alias
335/// query. By default, the root query is stateless and starts with a freshly
336/// constructed info object. Specific alias analyses can use this query info to
337/// store per-query state that is important for recursive or nested queries to
338/// avoid recomputing. To enable preserving this state across multiple queries
339/// where safe (due to the IR not changing), use a `BatchAAResults` wrapper.
340/// The information stored in an `AAQueryInfo` is currently limitted to the
341/// caches used by BasicAA, but can further be extended to fit other AA needs.
342class AAQueryInfo {
343public:
344 using LocPair = std::pair<MemoryLocation, MemoryLocation>;
345 using AliasCacheT = SmallDenseMap<LocPair, AliasResult, 8>;
346 AliasCacheT AliasCache;
347
348 using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
349 IsCapturedCacheT IsCapturedCache;
350
351 AAQueryInfo() : AliasCache(), IsCapturedCache() {}
352};
353
354class BatchAAResults;
355
356class AAResults {
357public:
358 // Make these results default constructable and movable. We have to spell
359 // these out because MSVC won't synthesize them.
360 AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}
361 AAResults(AAResults &&Arg);
362 ~AAResults();
363
364 /// Register a specific AA result.
365 template <typename AAResultT> void addAAResult(AAResultT &AAResult) {
366 // FIXME: We should use a much lighter weight system than the usual
367 // polymorphic pattern because we don't own AAResult. It should
368 // ideally involve two pointers and no separate allocation.
369 AAs.emplace_back(new Model<AAResultT>(AAResult, *this));
370 }
371
372 /// Register a function analysis ID that the results aggregation depends on.
373 ///
374 /// This is used in the new pass manager to implement the invalidation logic
375 /// where we must invalidate the results aggregation if any of our component
376 /// analyses become invalid.
377 void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); }
378
379 /// Handle invalidation events in the new pass manager.
380 ///
381 /// The aggregation is invalidated if any of the underlying analyses is
382 /// invalidated.
383 bool invalidate(Function &F, const PreservedAnalyses &PA,
384 FunctionAnalysisManager::Invalidator &Inv);
385
386 //===--------------------------------------------------------------------===//
387 /// \name Alias Queries
388 /// @{
389
390 /// The main low level interface to the alias analysis implementation.
391 /// Returns an AliasResult indicating whether the two pointers are aliased to
392 /// each other. This is the interface that must be implemented by specific
393 /// alias analysis implementations.
394 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
395
396 /// A convenience wrapper around the primary \c alias interface.
397 AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2,
398 LocationSize V2Size) {
399 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
400 }
401
402 /// A convenience wrapper around the primary \c alias interface.
403 AliasResult alias(const Value *V1, const Value *V2) {
404 return alias(V1, LocationSize::unknown(), V2, LocationSize::unknown());
405 }
406
407 /// A trivial helper function to check to see if the specified pointers are
408 /// no-alias.
409 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
410 return alias(LocA, LocB) == NoAlias;
411 }
412
413 /// A convenience wrapper around the \c isNoAlias helper interface.
414 bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2,
415 LocationSize V2Size) {
416 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
417 }
418
419 /// A convenience wrapper around the \c isNoAlias helper interface.
420 bool isNoAlias(const Value *V1, const Value *V2) {
421 return isNoAlias(MemoryLocation(V1), MemoryLocation(V2));
422 }
423
424 /// A trivial helper function to check to see if the specified pointers are
425 /// must-alias.
426 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
427 return alias(LocA, LocB) == MustAlias;
428 }
429
430 /// A convenience wrapper around the \c isMustAlias helper interface.
431 bool isMustAlias(const Value *V1, const Value *V2) {
432 return alias(V1, LocationSize::precise(1), V2, LocationSize::precise(1)) ==
433 MustAlias;
434 }
435
436 /// Checks whether the given location points to constant memory, or if
437 /// \p OrLocal is true whether it points to a local alloca.
438 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false);
439
440 /// A convenience wrapper around the primary \c pointsToConstantMemory
441 /// interface.
442 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
443 return pointsToConstantMemory(MemoryLocation(P), OrLocal);
444 }
445
446 /// @}
447 //===--------------------------------------------------------------------===//
448 /// \name Simple mod/ref information
449 /// @{
450
451 /// Get the ModRef info associated with a pointer argument of a call. The
452 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
453 /// that these bits do not necessarily account for the overall behavior of
454 /// the function, but rather only provide additional per-argument
455 /// information. This never sets ModRefInfo::Must.
456 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
457
458 /// Return the behavior of the given call site.
459 FunctionModRefBehavior getModRefBehavior(const CallBase *Call);
460
461 /// Return the behavior when calling the given function.
462 FunctionModRefBehavior getModRefBehavior(const Function *F);
463
464 /// Checks if the specified call is known to never read or write memory.
465 ///
466 /// Note that if the call only reads from known-constant memory, it is also
467 /// legal to return true. Also, calls that unwind the stack are legal for
468 /// this predicate.
469 ///
470 /// Many optimizations (such as CSE and LICM) can be performed on such calls
471 /// without worrying about aliasing properties, and many calls have this
472 /// property (e.g. calls to 'sin' and 'cos').
473 ///
474 /// This property corresponds to the GCC 'const' attribute.
475 bool doesNotAccessMemory(const CallBase *Call) {
476 return getModRefBehavior(Call) == FMRB_DoesNotAccessMemory;
477 }
478
479 /// Checks if the specified function is known to never read or write memory.
480 ///
481 /// Note that if the function only reads from known-constant memory, it is
482 /// also legal to return true. Also, function that unwind the stack are legal
483 /// for this predicate.
484 ///
485 /// Many optimizations (such as CSE and LICM) can be performed on such calls
486 /// to such functions without worrying about aliasing properties, and many
487 /// functions have this property (e.g. 'sin' and 'cos').
488 ///
489 /// This property corresponds to the GCC 'const' attribute.
490 bool doesNotAccessMemory(const Function *F) {
491 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
492 }
493
494 /// Checks if the specified call is known to only read from non-volatile
495 /// memory (or not access memory at all).
496 ///
497 /// Calls that unwind the stack are legal for this predicate.
498 ///
499 /// This property allows many common optimizations to be performed in the
500 /// absence of interfering store instructions, such as CSE of strlen calls.
501 ///
502 /// This property corresponds to the GCC 'pure' attribute.
503 bool onlyReadsMemory(const CallBase *Call) {
504 return onlyReadsMemory(getModRefBehavior(Call));
505 }
506
507 /// Checks if the specified function is known to only read from non-volatile
508 /// memory (or not access memory at all).
509 ///
510 /// Functions that unwind the stack are legal for this predicate.
511 ///
512 /// This property allows many common optimizations to be performed in the
513 /// absence of interfering store instructions, such as CSE of strlen calls.
514 ///
515 /// This property corresponds to the GCC 'pure' attribute.
516 bool onlyReadsMemory(const Function *F) {
517 return onlyReadsMemory(getModRefBehavior(F));
518 }
519
520 /// Checks if functions with the specified behavior are known to only read
521 /// from non-volatile memory (or not access memory at all).
522 static bool onlyReadsMemory(FunctionModRefBehavior MRB) {
523 return !isModSet(createModRefInfo(MRB));
53
Assuming the condition is true
54
Returning the value 1, which participates in a condition later
524 }
525
526 /// Checks if functions with the specified behavior are known to only write
527 /// memory (or not access memory at all).
528 static bool doesNotReadMemory(FunctionModRefBehavior MRB) {
529 return !isRefSet(createModRefInfo(MRB));
530 }
531
532 /// Checks if functions with the specified behavior are known to read and
533 /// write at most from objects pointed to by their pointer-typed arguments
534 /// (with arbitrary offsets).
535 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) {
536 return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
58
Assuming the condition is false
59
Returning zero, which participates in a condition later
537 }
538
539 /// Checks if functions with the specified behavior are known to potentially
540 /// read or write from objects pointed to be their pointer-typed arguments
541 /// (with arbitrary offsets).
542 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) {
543 return isModOrRefSet(createModRefInfo(MRB)) &&
544 (MRB & FMRL_ArgumentPointees);
545 }
546
547 /// Checks if functions with the specified behavior are known to read and
548 /// write at most from memory that is inaccessible from LLVM IR.
549 static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) {
550 return !(MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem);
551 }
552
553 /// Checks if functions with the specified behavior are known to potentially
554 /// read or write from memory that is inaccessible from LLVM IR.
555 static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) {
556 return isModOrRefSet(createModRefInfo(MRB)) && (MRB & FMRL_InaccessibleMem);
557 }
558
559 /// Checks if functions with the specified behavior are known to read and
560 /// write at most from memory that is inaccessible from LLVM IR or objects
561 /// pointed to by their pointer-typed arguments (with arbitrary offsets).
562 static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) {
563 return !(MRB & FMRL_Anywhere &
564 ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees));
565 }
566
567 /// getModRefInfo (for call sites) - Return information about whether
568 /// a particular call site modifies or reads the specified memory location.
569 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc);
570
571 /// getModRefInfo (for call sites) - A convenience wrapper.
572 ModRefInfo getModRefInfo(const CallBase *Call, const Value *P,
573 LocationSize Size) {
574 return getModRefInfo(Call, MemoryLocation(P, Size));
575 }
576
577 /// getModRefInfo (for loads) - Return information about whether
578 /// a particular load modifies or reads the specified memory location.
579 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
580
581 /// getModRefInfo (for loads) - A convenience wrapper.
582 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P,
583 LocationSize Size) {
584 return getModRefInfo(L, MemoryLocation(P, Size));
585 }
586
587 /// getModRefInfo (for stores) - Return information about whether
588 /// a particular store modifies or reads the specified memory location.
589 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
590
591 /// getModRefInfo (for stores) - A convenience wrapper.
592 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P,
593 LocationSize Size) {
594 return getModRefInfo(S, MemoryLocation(P, Size));
595 }
596
597 /// getModRefInfo (for fences) - Return information about whether
598 /// a particular store modifies or reads the specified memory location.
599 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc);
600
601 /// getModRefInfo (for fences) - A convenience wrapper.
602 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P,
603 LocationSize Size) {
604 return getModRefInfo(S, MemoryLocation(P, Size));
605 }
606
607 /// getModRefInfo (for cmpxchges) - Return information about whether
608 /// a particular cmpxchg modifies or reads the specified memory location.
609 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
610 const MemoryLocation &Loc);
611
612 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
613 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P,
614 LocationSize Size) {
615 return getModRefInfo(CX, MemoryLocation(P, Size));
616 }
617
618 /// getModRefInfo (for atomicrmws) - Return information about whether
619 /// a particular atomicrmw modifies or reads the specified memory location.
620 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);
621
622 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
623 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
624 LocationSize Size) {
625 return getModRefInfo(RMW, MemoryLocation(P, Size));
626 }
627
628 /// getModRefInfo (for va_args) - Return information about whether
629 /// a particular va_arg modifies or reads the specified memory location.
630 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
631
632 /// getModRefInfo (for va_args) - A convenience wrapper.
633 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P,
634 LocationSize Size) {
635 return getModRefInfo(I, MemoryLocation(P, Size));
636 }
637
638 /// getModRefInfo (for catchpads) - Return information about whether
639 /// a particular catchpad modifies or reads the specified memory location.
640 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc);
641
642 /// getModRefInfo (for catchpads) - A convenience wrapper.
643 ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P,
644 LocationSize Size) {
645 return getModRefInfo(I, MemoryLocation(P, Size));
646 }
647
648 /// getModRefInfo (for catchrets) - Return information about whether
649 /// a particular catchret modifies or reads the specified memory location.
650 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc);
651
652 /// getModRefInfo (for catchrets) - A convenience wrapper.
653 ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P,
654 LocationSize Size) {
655 return getModRefInfo(I, MemoryLocation(P, Size));
656 }
657
658 /// Check whether or not an instruction may read or write the optionally
659 /// specified memory location.
660 ///
661 ///
662 /// An instruction that doesn't read or write memory may be trivially LICM'd
663 /// for example.
664 ///
665 /// For function calls, this delegates to the alias-analysis specific
666 /// call-site mod-ref behavior queries. Otherwise it delegates to the specific
667 /// helpers above.
668 ModRefInfo getModRefInfo(const Instruction *I,
669 const Optional<MemoryLocation> &OptLoc) {
670 AAQueryInfo AAQIP;
671 return getModRefInfo(I, OptLoc, AAQIP);
672 }
673
674 /// A convenience wrapper for constructing the memory location.
675 ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
676 LocationSize Size) {
677 return getModRefInfo(I, MemoryLocation(P, Size));
678 }
679
680 /// Return information about whether a call and an instruction may refer to
681 /// the same memory locations.
682 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call);
683
684 /// Return information about whether two call sites may refer to the same set
685 /// of memory locations. See the AA documentation for details:
686 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
687 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2);
688
689 /// Return information about whether a particular call site modifies
690 /// or reads the specified memory location \p MemLoc before instruction \p I
691 /// in a BasicBlock.
692 /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
693 /// set.
694 ModRefInfo callCapturesBefore(const Instruction *I,
695 const MemoryLocation &MemLoc, DominatorTree *DT);
696
697 /// A convenience wrapper to synthesize a memory location.
698 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
699 LocationSize Size, DominatorTree *DT) {
700 return callCapturesBefore(I, MemoryLocation(P, Size), DT);
701 }
702
703 /// @}
704 //===--------------------------------------------------------------------===//
705 /// \name Higher level methods for querying mod/ref information.
706 /// @{
707
708 /// Check if it is possible for execution of the specified basic block to
709 /// modify the location Loc.
710 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
711
712 /// A convenience wrapper synthesizing a memory location.
713 bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
714 LocationSize Size) {
715 return canBasicBlockModify(BB, MemoryLocation(P, Size));
716 }
717
718 /// Check if it is possible for the execution of the specified instructions
719 /// to mod\ref (according to the mode) the location Loc.
720 ///
721 /// The instructions to consider are all of the instructions in the range of
722 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
723 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
724 const MemoryLocation &Loc,
725 const ModRefInfo Mode);
726
727 /// A convenience wrapper synthesizing a memory location.
728 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
729 const Value *Ptr, LocationSize Size,
730 const ModRefInfo Mode) {
731 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
732 }
733
734private:
735 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
736 AAQueryInfo &AAQI);
737 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
738 bool OrLocal = false);
739 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2,
740 AAQueryInfo &AAQIP);
741 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
742 AAQueryInfo &AAQI);
743 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
744 AAQueryInfo &AAQI);
745 ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc,
746 AAQueryInfo &AAQI);
747 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc,
748 AAQueryInfo &AAQI);
749 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc,
750 AAQueryInfo &AAQI);
751 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc,
752 AAQueryInfo &AAQI);
753 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
754 const MemoryLocation &Loc, AAQueryInfo &AAQI);
755 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc,
756 AAQueryInfo &AAQI);
757 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc,
758 AAQueryInfo &AAQI);
759 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc,
760 AAQueryInfo &AAQI);
761 ModRefInfo getModRefInfo(const Instruction *I,
762 const Optional<MemoryLocation> &OptLoc,
763 AAQueryInfo &AAQIP) {
764 if (OptLoc == None) {
765 if (const auto *Call = dyn_cast<CallBase>(I)) {
766 return createModRefInfo(getModRefBehavior(Call));
767 }
768 }
769
770 const MemoryLocation &Loc = OptLoc.getValueOr(MemoryLocation());
771
772 switch (I->getOpcode()) {
773 case Instruction::VAArg:
774 return getModRefInfo((const VAArgInst *)I, Loc, AAQIP);
775 case Instruction::Load:
776 return getModRefInfo((const LoadInst *)I, Loc, AAQIP);
777 case Instruction::Store:
778 return getModRefInfo((const StoreInst *)I, Loc, AAQIP);
779 case Instruction::Fence:
780 return getModRefInfo((const FenceInst *)I, Loc, AAQIP);
781 case Instruction::AtomicCmpXchg:
782 return getModRefInfo((const AtomicCmpXchgInst *)I, Loc, AAQIP);
783 case Instruction::AtomicRMW:
784 return getModRefInfo((const AtomicRMWInst *)I, Loc, AAQIP);
785 case Instruction::Call:
786 return getModRefInfo((const CallInst *)I, Loc, AAQIP);
787 case Instruction::Invoke:
788 return getModRefInfo((const InvokeInst *)I, Loc, AAQIP);
789 case Instruction::CatchPad:
790 return getModRefInfo((const CatchPadInst *)I, Loc, AAQIP);
791 case Instruction::CatchRet:
792 return getModRefInfo((const CatchReturnInst *)I, Loc, AAQIP);
793 default:
794 return ModRefInfo::NoModRef;
795 }
796 }
797
798 class Concept;
799
800 template <typename T> class Model;
801
802 template <typename T> friend class AAResultBase;
803
804 const TargetLibraryInfo &TLI;
805
806 std::vector<std::unique_ptr<Concept>> AAs;
807
808 std::vector<AnalysisKey *> AADeps;
809
810 friend class BatchAAResults;
811};
812
813/// This class is a wrapper over an AAResults, and it is intended to be used
814/// only when there are no IR changes inbetween queries. BatchAAResults is
815/// reusing the same `AAQueryInfo` to preserve the state across queries,
816/// esentially making AA work in "batch mode". The internal state cannot be
817/// cleared, so to go "out-of-batch-mode", the user must either use AAResults,
818/// or create a new BatchAAResults.
819class BatchAAResults {
820 AAResults &AA;
821 AAQueryInfo AAQI;
822
823public:
824 BatchAAResults(AAResults &AAR) : AA(AAR), AAQI() {}
825 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
826 return AA.alias(LocA, LocB, AAQI);
827 }
828 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
829 return AA.pointsToConstantMemory(Loc, AAQI, OrLocal);
830 }
831 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) {
832 return AA.getModRefInfo(Call, Loc, AAQI);
833 }
834 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2) {
835 return AA.getModRefInfo(Call1, Call2, AAQI);
836 }
837 ModRefInfo getModRefInfo(const Instruction *I,
838 const Optional<MemoryLocation> &OptLoc) {
839 return AA.getModRefInfo(I, OptLoc, AAQI);
840 }
841 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2) {
842 return AA.getModRefInfo(I, Call2, AAQI);
843 }
844 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
845 return AA.getArgModRefInfo(Call, ArgIdx);
846 }
847 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
848 return AA.getModRefBehavior(Call);
849 }
850};
851
852/// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
853/// pointer or reference.
854using AliasAnalysis = AAResults;
855
856/// A private abstract base class describing the concept of an individual alias
857/// analysis implementation.
858///
859/// This interface is implemented by any \c Model instantiation. It is also the
860/// interface which a type used to instantiate the model must provide.
861///
862/// All of these methods model methods by the same name in the \c
863/// AAResults class. Only differences and specifics to how the
864/// implementations are called are documented here.
865class AAResults::Concept {
866public:
867 virtual ~Concept() = 0;
868
869 /// An update API used internally by the AAResults to provide
870 /// a handle back to the top level aggregation.
871 virtual void setAAResults(AAResults *NewAAR) = 0;
872
873 //===--------------------------------------------------------------------===//
874 /// \name Alias Queries
875 /// @{
876
877 /// The main low level interface to the alias analysis implementation.
878 /// Returns an AliasResult indicating whether the two pointers are aliased to
879 /// each other. This is the interface that must be implemented by specific
880 /// alias analysis implementations.
881 virtual AliasResult alias(const MemoryLocation &LocA,
882 const MemoryLocation &LocB, AAQueryInfo &AAQI) = 0;
883
884 /// Checks whether the given location points to constant memory, or if
885 /// \p OrLocal is true whether it points to a local alloca.
886 virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
887 AAQueryInfo &AAQI, bool OrLocal) = 0;
888
889 /// @}
890 //===--------------------------------------------------------------------===//
891 /// \name Simple mod/ref information
892 /// @{
893
894 /// Get the ModRef info associated with a pointer argument of a callsite. The
895 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
896 /// that these bits do not necessarily account for the overall behavior of
897 /// the function, but rather only provide additional per-argument
898 /// information.
899 virtual ModRefInfo getArgModRefInfo(const CallBase *Call,
900 unsigned ArgIdx) = 0;
901
902 /// Return the behavior of the given call site.
903 virtual FunctionModRefBehavior getModRefBehavior(const CallBase *Call) = 0;
904
905 /// Return the behavior when calling the given function.
906 virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0;
907
908 /// getModRefInfo (for call sites) - Return information about whether
909 /// a particular call site modifies or reads the specified memory location.
910 virtual ModRefInfo getModRefInfo(const CallBase *Call,
911 const MemoryLocation &Loc,
912 AAQueryInfo &AAQI) = 0;
913
914 /// Return information about whether two call sites may refer to the same set
915 /// of memory locations. See the AA documentation for details:
916 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
917 virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
918 AAQueryInfo &AAQI) = 0;
919
920 /// @}
921};
922
923/// A private class template which derives from \c Concept and wraps some other
924/// type.
925///
926/// This models the concept by directly forwarding each interface point to the
927/// wrapped type which must implement a compatible interface. This provides
928/// a type erased binding.
929template <typename AAResultT> class AAResults::Model final : public Concept {
930 AAResultT &Result;
931
932public:
933 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {
934 Result.setAAResults(&AAR);
935 }
936 ~Model() override = default;
937
938 void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); }
939
940 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
941 AAQueryInfo &AAQI) override {
942 return Result.alias(LocA, LocB, AAQI);
943 }
944
945 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
946 bool OrLocal) override {
947 return Result.pointsToConstantMemory(Loc, AAQI, OrLocal);
948 }
949
950 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override {
951 return Result.getArgModRefInfo(Call, ArgIdx);
952 }
953
954 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) override {
955 return Result.getModRefBehavior(Call);
956 }
957
958 FunctionModRefBehavior getModRefBehavior(const Function *F) override {
959 return Result.getModRefBehavior(F);
960 }
961
962 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
963 AAQueryInfo &AAQI) override {
964 return Result.getModRefInfo(Call, Loc, AAQI);
965 }
966
967 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
968 AAQueryInfo &AAQI) override {
969 return Result.getModRefInfo(Call1, Call2, AAQI);
970 }
971};
972
973/// A CRTP-driven "mixin" base class to help implement the function alias
974/// analysis results concept.
975///
976/// Because of the nature of many alias analysis implementations, they often
977/// only implement a subset of the interface. This base class will attempt to
978/// implement the remaining portions of the interface in terms of simpler forms
979/// of the interface where possible, and otherwise provide conservatively
980/// correct fallback implementations.
981///
982/// Implementors of an alias analysis should derive from this CRTP, and then
983/// override specific methods that they wish to customize. There is no need to
984/// use virtual anywhere, the CRTP base class does static dispatch to the
985/// derived type passed into it.
986template <typename DerivedT> class AAResultBase {
987 // Expose some parts of the interface only to the AAResults::Model
988 // for wrapping. Specifically, this allows the model to call our
989 // setAAResults method without exposing it as a fully public API.
990 friend class AAResults::Model<DerivedT>;
991
992 /// A pointer to the AAResults object that this AAResult is
993 /// aggregated within. May be null if not aggregated.
994 AAResults *AAR = nullptr;
995
996 /// Helper to dispatch calls back through the derived type.
997 DerivedT &derived() { return static_cast<DerivedT &>(*this); }
998
999 /// A setter for the AAResults pointer, which is used to satisfy the
1000 /// AAResults::Model contract.
1001 void setAAResults(AAResults *NewAAR) { AAR = NewAAR; }
1002
1003protected:
1004 /// This proxy class models a common pattern where we delegate to either the
1005 /// top-level \c AAResults aggregation if one is registered, or to the
1006 /// current result if none are registered.
1007 class AAResultsProxy {
1008 AAResults *AAR;
1009 DerivedT &CurrentResult;
1010
1011 public:
1012 AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult)
1013 : AAR(AAR), CurrentResult(CurrentResult) {}
1014
1015 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
1016 AAQueryInfo &AAQI) {
1017 return AAR ? AAR->alias(LocA, LocB, AAQI)
1018 : CurrentResult.alias(LocA, LocB, AAQI);
1019 }
1020
1021 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
1022 bool OrLocal) {
1023 return AAR ? AAR->pointsToConstantMemory(Loc, AAQI, OrLocal)
1024 : CurrentResult.pointsToConstantMemory(Loc, AAQI, OrLocal);
1025 }
1026
1027 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
1028 return AAR ? AAR->getArgModRefInfo(Call, ArgIdx)
1029 : CurrentResult.getArgModRefInfo(Call, ArgIdx);
1030 }
1031
1032 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
1033 return AAR ? AAR->getModRefBehavior(Call)
1034 : CurrentResult.getModRefBehavior(Call);
1035 }
1036
1037 FunctionModRefBehavior getModRefBehavior(const Function *F) {
1038 return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F);
1039 }
1040
1041 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
1042 AAQueryInfo &AAQI) {
1043 return AAR ? AAR->getModRefInfo(Call, Loc, AAQI)
1044 : CurrentResult.getModRefInfo(Call, Loc, AAQI);
1045 }
1046
1047 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
1048 AAQueryInfo &AAQI) {
1049 return AAR ? AAR->getModRefInfo(Call1, Call2, AAQI)
1050 : CurrentResult.getModRefInfo(Call1, Call2, AAQI);
1051 }
1052 };
1053
1054 explicit AAResultBase() = default;
1055
1056 // Provide all the copy and move constructors so that derived types aren't
1057 // constrained.
1058 AAResultBase(const AAResultBase &Arg) {}
1059 AAResultBase(AAResultBase &&Arg) {}
1060
1061 /// Get a proxy for the best AA result set to query at this time.
1062 ///
1063 /// When this result is part of a larger aggregation, this will proxy to that
1064 /// aggregation. When this result is used in isolation, it will just delegate
1065 /// back to the derived class's implementation.
1066 ///
1067 /// Note that callers of this need to take considerable care to not cause
1068 /// performance problems when they use this routine, in the case of a large
1069 /// number of alias analyses being aggregated, it can be expensive to walk
1070 /// back across the chain.
1071 AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); }
1072
1073public:
1074 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
1075 AAQueryInfo &AAQI) {
1076 return MayAlias;
1077 }
1078
1079 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
1080 bool OrLocal) {
1081 return false;
1082 }
1083
1084 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
1085 return ModRefInfo::ModRef;
1086 }
1087
1088 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
1089 return FMRB_UnknownModRefBehavior;
1090 }
1091
1092 FunctionModRefBehavior getModRefBehavior(const Function *F) {
1093 return FMRB_UnknownModRefBehavior;
1094 }
1095
1096 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
1097 AAQueryInfo &AAQI) {
1098 return ModRefInfo::ModRef;
1099 }
1100
1101 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
1102 AAQueryInfo &AAQI) {
1103 return ModRefInfo::ModRef;
1104 }
1105};
1106
1107/// Return true if this pointer is returned by a noalias function.
1108bool isNoAliasCall(const Value *V);
1109
1110/// Return true if this is an argument with the noalias attribute.
1111bool isNoAliasArgument(const Value *V);
1112
1113/// Return true if this pointer refers to a distinct and identifiable object.
1114/// This returns true for:
1115/// Global Variables and Functions (but not Global Aliases)
1116/// Allocas
1117/// ByVal and NoAlias Arguments
1118/// NoAlias returns (e.g. calls to malloc)
1119///
1120bool isIdentifiedObject(const Value *V);
1121
1122/// Return true if V is umabigously identified at the function-level.
1123/// Different IdentifiedFunctionLocals can't alias.
1124/// Further, an IdentifiedFunctionLocal can not alias with any function
1125/// arguments other than itself, which is not necessarily true for
1126/// IdentifiedObjects.
1127bool isIdentifiedFunctionLocal(const Value *V);
1128
1129/// A manager for alias analyses.
1130///
1131/// This class can have analyses registered with it and when run, it will run
1132/// all of them and aggregate their results into single AA results interface
1133/// that dispatches across all of the alias analysis results available.
1134///
1135/// Note that the order in which analyses are registered is very significant.
1136/// That is the order in which the results will be aggregated and queried.
1137///
1138/// This manager effectively wraps the AnalysisManager for registering alias
1139/// analyses. When you register your alias analysis with this manager, it will
1140/// ensure the analysis itself is registered with its AnalysisManager.
1141///
1142/// The result of this analysis is only invalidated if one of the particular
1143/// aggregated AA results end up being invalidated. This removes the need to
1144/// explicitly preserve the results of `AAManager`. Note that analyses should no
1145/// longer be registered once the `AAManager` is run.
1146class AAManager : public AnalysisInfoMixin<AAManager> {
1147public:
1148 using Result = AAResults;
1149
1150 /// Register a specific AA result.
1151 template <typename AnalysisT> void registerFunctionAnalysis() {
1152 ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>);
1153 }
1154
1155 /// Register a specific AA result.
1156 template <typename AnalysisT> void registerModuleAnalysis() {
1157 ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>);
1158 }
1159
1160 Result run(Function &F, FunctionAnalysisManager &AM) {
1161 Result R(AM.getResult<TargetLibraryAnalysis>(F));
1162 for (auto &Getter : ResultGetters)
1163 (*Getter)(F, AM, R);
1164 return R;
1165 }
1166
1167private:
1168 friend AnalysisInfoMixin<AAManager>;
1169
1170 static AnalysisKey Key;
1171
1172 SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM,
1173 AAResults &AAResults),
1174 4> ResultGetters;
1175
1176 template <typename AnalysisT>
1177 static void getFunctionAAResultImpl(Function &F,
1178 FunctionAnalysisManager &AM,
1179 AAResults &AAResults) {
1180 AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
1181 AAResults.addAADependencyID(AnalysisT::ID());
1182 }
1183
1184 template <typename AnalysisT>
1185 static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM,
1186 AAResults &AAResults) {
1187 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
1188 auto &MAM = MAMProxy.getManager();
1189 if (auto *R = MAM.template getCachedResult<AnalysisT>(*F.getParent())) {
1190 AAResults.addAAResult(*R);
1191 MAMProxy
1192 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
1193 }
1194 }
1195};
1196
1197/// A wrapper pass to provide the legacy pass manager access to a suitably
1198/// prepared AAResults object.
1199class AAResultsWrapperPass : public FunctionPass {
1200 std::unique_ptr<AAResults> AAR;
1201
1202public:
1203 static char ID;
1204
1205 AAResultsWrapperPass();
1206
1207 AAResults &getAAResults() { return *AAR; }
1208 const AAResults &getAAResults() const { return *AAR; }
1209
1210 bool runOnFunction(Function &F) override;
1211
1212 void getAnalysisUsage(AnalysisUsage &AU) const override;
1213};
1214
1215/// A wrapper pass for external alias analyses. This just squirrels away the
1216/// callback used to run any analyses and register their results.
1217struct ExternalAAWrapperPass : ImmutablePass {
1218 using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
1219
1220 CallbackT CB;
1221
1222 static char ID;
1223
1224 ExternalAAWrapperPass();
1225
1226 explicit ExternalAAWrapperPass(CallbackT CB);
1227
1228 void getAnalysisUsage(AnalysisUsage &AU) const override {
1229 AU.setPreservesAll();
1230 }
1231};
1232
1233FunctionPass *createAAResultsWrapperPass();
1234
1235/// A wrapper pass around a callback which can be used to populate the
1236