Bug Summary

File:llvm/lib/Transforms/Scalar/GVN.cpp
Warning:line 2989, column 29
Although the value stored to 'P' is used in the enclosing expression, the value is never actually read from 'P'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name GVN.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 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/llvm/lib/Transforms/Scalar -I include -I /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-01-19-134126-35450-1 -x c++ /build/llvm-toolchain-snapshot-14~++20220119111520+da61cb019eb2/llvm/lib/Transforms/Scalar/GVN.cpp
1//===- GVN.cpp - Eliminate redundant values and loads ---------------------===//
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 global value numbering to eliminate fully redundant
10// instructions. It also performs simple dead load elimination.
11//
12// Note that this pass does the value numbering itself; it does not use the
13// ValueNumbering analysis passes.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Transforms/Scalar/GVN.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/DepthFirstIterator.h"
20#include "llvm/ADT/Hashing.h"
21#include "llvm/ADT/MapVector.h"
22#include "llvm/ADT/PointerIntPair.h"
23#include "llvm/ADT/PostOrderIterator.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/SetVector.h"
26#include "llvm/ADT/SmallPtrSet.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/Analysis/AliasAnalysis.h"
30#include "llvm/Analysis/AssumeBundleQueries.h"
31#include "llvm/Analysis/AssumptionCache.h"
32#include "llvm/Analysis/CFG.h"
33#include "llvm/Analysis/DomTreeUpdater.h"
34#include "llvm/Analysis/GlobalsModRef.h"
35#include "llvm/Analysis/InstructionSimplify.h"
36#include "llvm/Analysis/LoopInfo.h"
37#include "llvm/Analysis/MemoryBuiltins.h"
38#include "llvm/Analysis/MemoryDependenceAnalysis.h"
39#include "llvm/Analysis/MemorySSA.h"
40#include "llvm/Analysis/MemorySSAUpdater.h"
41#include "llvm/Analysis/OptimizationRemarkEmitter.h"
42#include "llvm/Analysis/PHITransAddr.h"
43#include "llvm/Analysis/TargetLibraryInfo.h"
44#include "llvm/Analysis/ValueTracking.h"
45#include "llvm/Config/llvm-config.h"
46#include "llvm/IR/Attributes.h"
47#include "llvm/IR/BasicBlock.h"
48#include "llvm/IR/Constant.h"
49#include "llvm/IR/Constants.h"
50#include "llvm/IR/DataLayout.h"
51#include "llvm/IR/DebugLoc.h"
52#include "llvm/IR/Dominators.h"
53#include "llvm/IR/Function.h"
54#include "llvm/IR/InstrTypes.h"
55#include "llvm/IR/Instruction.h"
56#include "llvm/IR/Instructions.h"
57#include "llvm/IR/IntrinsicInst.h"
58#include "llvm/IR/Intrinsics.h"
59#include "llvm/IR/LLVMContext.h"
60#include "llvm/IR/Metadata.h"
61#include "llvm/IR/Module.h"
62#include "llvm/IR/Operator.h"
63#include "llvm/IR/PassManager.h"
64#include "llvm/IR/PatternMatch.h"
65#include "llvm/IR/Type.h"
66#include "llvm/IR/Use.h"
67#include "llvm/IR/Value.h"
68#include "llvm/InitializePasses.h"
69#include "llvm/Pass.h"
70#include "llvm/Support/Casting.h"
71#include "llvm/Support/CommandLine.h"
72#include "llvm/Support/Compiler.h"
73#include "llvm/Support/Debug.h"
74#include "llvm/Support/raw_ostream.h"
75#include "llvm/Transforms/Utils.h"
76#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
77#include "llvm/Transforms/Utils/BasicBlockUtils.h"
78#include "llvm/Transforms/Utils/Local.h"
79#include "llvm/Transforms/Utils/SSAUpdater.h"
80#include "llvm/Transforms/Utils/VNCoercion.h"
81#include <algorithm>
82#include <cassert>
83#include <cstdint>
84#include <utility>
85
86using namespace llvm;
87using namespace llvm::gvn;
88using namespace llvm::VNCoercion;
89using namespace PatternMatch;
90
91#define DEBUG_TYPE"gvn" "gvn"
92
93STATISTIC(NumGVNInstr, "Number of instructions deleted")static llvm::Statistic NumGVNInstr = {"gvn", "NumGVNInstr", "Number of instructions deleted"
}
;
94STATISTIC(NumGVNLoad, "Number of loads deleted")static llvm::Statistic NumGVNLoad = {"gvn", "NumGVNLoad", "Number of loads deleted"
}
;
95STATISTIC(NumGVNPRE, "Number of instructions PRE'd")static llvm::Statistic NumGVNPRE = {"gvn", "NumGVNPRE", "Number of instructions PRE'd"
}
;
96STATISTIC(NumGVNBlocks, "Number of blocks merged")static llvm::Statistic NumGVNBlocks = {"gvn", "NumGVNBlocks",
"Number of blocks merged"}
;
97STATISTIC(NumGVNSimpl, "Number of instructions simplified")static llvm::Statistic NumGVNSimpl = {"gvn", "NumGVNSimpl", "Number of instructions simplified"
}
;
98STATISTIC(NumGVNEqProp, "Number of equalities propagated")static llvm::Statistic NumGVNEqProp = {"gvn", "NumGVNEqProp",
"Number of equalities propagated"}
;
99STATISTIC(NumPRELoad, "Number of loads PRE'd")static llvm::Statistic NumPRELoad = {"gvn", "NumPRELoad", "Number of loads PRE'd"
}
;
100STATISTIC(NumPRELoopLoad, "Number of loop loads PRE'd")static llvm::Statistic NumPRELoopLoad = {"gvn", "NumPRELoopLoad"
, "Number of loop loads PRE'd"}
;
101
102STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,static llvm::Statistic IsValueFullyAvailableInBlockNumSpeculationsMax
= {"gvn", "IsValueFullyAvailableInBlockNumSpeculationsMax", "Number of blocks speculated as available in "
"IsValueFullyAvailableInBlock(), max"}
103 "Number of blocks speculated as available in "static llvm::Statistic IsValueFullyAvailableInBlockNumSpeculationsMax
= {"gvn", "IsValueFullyAvailableInBlockNumSpeculationsMax", "Number of blocks speculated as available in "
"IsValueFullyAvailableInBlock(), max"}
104 "IsValueFullyAvailableInBlock(), max")static llvm::Statistic IsValueFullyAvailableInBlockNumSpeculationsMax
= {"gvn", "IsValueFullyAvailableInBlockNumSpeculationsMax", "Number of blocks speculated as available in "
"IsValueFullyAvailableInBlock(), max"}
;
105STATISTIC(MaxBBSpeculationCutoffReachedTimes,static llvm::Statistic MaxBBSpeculationCutoffReachedTimes = {
"gvn", "MaxBBSpeculationCutoffReachedTimes", "Number of times we we reached gvn-max-block-speculations cut-off "
"preventing further exploration"}
106 "Number of times we we reached gvn-max-block-speculations cut-off "static llvm::Statistic MaxBBSpeculationCutoffReachedTimes = {
"gvn", "MaxBBSpeculationCutoffReachedTimes", "Number of times we we reached gvn-max-block-speculations cut-off "
"preventing further exploration"}
107 "preventing further exploration")static llvm::Statistic MaxBBSpeculationCutoffReachedTimes = {
"gvn", "MaxBBSpeculationCutoffReachedTimes", "Number of times we we reached gvn-max-block-speculations cut-off "
"preventing further exploration"}
;
108
109static cl::opt<bool> GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden);
110static cl::opt<bool> GVNEnableLoadPRE("enable-load-pre", cl::init(true));
111static cl::opt<bool> GVNEnableLoadInLoopPRE("enable-load-in-loop-pre",
112 cl::init(true));
113static cl::opt<bool>
114GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre",
115 cl::init(true));
116static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(true));
117
118static cl::opt<uint32_t> MaxNumDeps(
119 "gvn-max-num-deps", cl::Hidden, cl::init(100), cl::ZeroOrMore,
120 cl::desc("Max number of dependences to attempt Load PRE (default = 100)"));
121
122// This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat.
123static cl::opt<uint32_t> MaxBBSpeculations(
124 "gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::ZeroOrMore,
125 cl::desc("Max number of blocks we're willing to speculate on (and recurse "
126 "into) when deducing if a value is fully available or not in GVN "
127 "(default = 600)"));
128
129struct llvm::GVNPass::Expression {
130 uint32_t opcode;
131 bool commutative = false;
132 Type *type = nullptr;
133 SmallVector<uint32_t, 4> varargs;
134
135 Expression(uint32_t o = ~2U) : opcode(o) {}
136
137 bool operator==(const Expression &other) const {
138 if (opcode != other.opcode)
139 return false;
140 if (opcode == ~0U || opcode == ~1U)
141 return true;
142 if (type != other.type)
143 return false;
144 if (varargs != other.varargs)
145 return false;
146 return true;
147 }
148
149 friend hash_code hash_value(const Expression &Value) {
150 return hash_combine(
151 Value.opcode, Value.type,
152 hash_combine_range(Value.varargs.begin(), Value.varargs.end()));
153 }
154};
155
156namespace llvm {
157
158template <> struct DenseMapInfo<GVNPass::Expression> {
159 static inline GVNPass::Expression getEmptyKey() { return ~0U; }
160 static inline GVNPass::Expression getTombstoneKey() { return ~1U; }
161
162 static unsigned getHashValue(const GVNPass::Expression &e) {
163 using llvm::hash_value;
164
165 return static_cast<unsigned>(hash_value(e));
166 }
167
168 static bool isEqual(const GVNPass::Expression &LHS,
169 const GVNPass::Expression &RHS) {
170 return LHS == RHS;
171 }
172};
173
174} // end namespace llvm
175
176/// Represents a particular available value that we know how to materialize.
177/// Materialization of an AvailableValue never fails. An AvailableValue is
178/// implicitly associated with a rematerialization point which is the
179/// location of the instruction from which it was formed.
180struct llvm::gvn::AvailableValue {
181 enum ValType {
182 SimpleVal, // A simple offsetted value that is accessed.
183 LoadVal, // A value produced by a load.
184 MemIntrin, // A memory intrinsic which is loaded from.
185 UndefVal // A UndefValue representing a value from dead block (which
186 // is not yet physically removed from the CFG).
187 };
188
189 /// V - The value that is live out of the block.
190 PointerIntPair<Value *, 2, ValType> Val;
191
192 /// Offset - The byte offset in Val that is interesting for the load query.
193 unsigned Offset = 0;
194
195 static AvailableValue get(Value *V, unsigned Offset = 0) {
196 AvailableValue Res;
197 Res.Val.setPointer(V);
198 Res.Val.setInt(SimpleVal);
199 Res.Offset = Offset;
200 return Res;
201 }
202
203 static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset = 0) {
204 AvailableValue Res;
205 Res.Val.setPointer(MI);
206 Res.Val.setInt(MemIntrin);
207 Res.Offset = Offset;
208 return Res;
209 }
210
211 static AvailableValue getLoad(LoadInst *Load, unsigned Offset = 0) {
212 AvailableValue Res;
213 Res.Val.setPointer(Load);
214 Res.Val.setInt(LoadVal);
215 Res.Offset = Offset;
216 return Res;
217 }
218
219 static AvailableValue getUndef() {
220 AvailableValue Res;
221 Res.Val.setPointer(nullptr);
222 Res.Val.setInt(UndefVal);
223 Res.Offset = 0;
224 return Res;
225 }
226
227 bool isSimpleValue() const { return Val.getInt() == SimpleVal; }
228 bool isCoercedLoadValue() const { return Val.getInt() == LoadVal; }
229 bool isMemIntrinValue() const { return Val.getInt() == MemIntrin; }
230 bool isUndefValue() const { return Val.getInt() == UndefVal; }
231
232 Value *getSimpleValue() const {
233 assert(isSimpleValue() && "Wrong accessor")(static_cast <bool> (isSimpleValue() && "Wrong accessor"
) ? void (0) : __assert_fail ("isSimpleValue() && \"Wrong accessor\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 233, __extension__ __PRETTY_FUNCTION__
))
;
234 return Val.getPointer();
235 }
236
237 LoadInst *getCoercedLoadValue() const {
238 assert(isCoercedLoadValue() && "Wrong accessor")(static_cast <bool> (isCoercedLoadValue() && "Wrong accessor"
) ? void (0) : __assert_fail ("isCoercedLoadValue() && \"Wrong accessor\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 238, __extension__ __PRETTY_FUNCTION__
))
;
239 return cast<LoadInst>(Val.getPointer());
240 }
241
242 MemIntrinsic *getMemIntrinValue() const {
243 assert(isMemIntrinValue() && "Wrong accessor")(static_cast <bool> (isMemIntrinValue() && "Wrong accessor"
) ? void (0) : __assert_fail ("isMemIntrinValue() && \"Wrong accessor\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 243, __extension__ __PRETTY_FUNCTION__
))
;
244 return cast<MemIntrinsic>(Val.getPointer());
245 }
246
247 /// Emit code at the specified insertion point to adjust the value defined
248 /// here to the specified type. This handles various coercion cases.
249 Value *MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt,
250 GVNPass &gvn) const;
251};
252
253/// Represents an AvailableValue which can be rematerialized at the end of
254/// the associated BasicBlock.
255struct llvm::gvn::AvailableValueInBlock {
256 /// BB - The basic block in question.
257 BasicBlock *BB = nullptr;
258
259 /// AV - The actual available value
260 AvailableValue AV;
261
262 static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV) {
263 AvailableValueInBlock Res;
264 Res.BB = BB;
265 Res.AV = std::move(AV);
266 return Res;
267 }
268
269 static AvailableValueInBlock get(BasicBlock *BB, Value *V,
270 unsigned Offset = 0) {
271 return get(BB, AvailableValue::get(V, Offset));
272 }
273
274 static AvailableValueInBlock getUndef(BasicBlock *BB) {
275 return get(BB, AvailableValue::getUndef());
276 }
277
278 /// Emit code at the end of this block to adjust the value defined here to
279 /// the specified type. This handles various coercion cases.
280 Value *MaterializeAdjustedValue(LoadInst *Load, GVNPass &gvn) const {
281 return AV.MaterializeAdjustedValue(Load, BB->getTerminator(), gvn);
282 }
283};
284
285//===----------------------------------------------------------------------===//
286// ValueTable Internal Functions
287//===----------------------------------------------------------------------===//
288
289GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) {
290 Expression e;
291 e.type = I->getType();
292 e.opcode = I->getOpcode();
293 if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(I)) {
294 // gc.relocate is 'special' call: its second and third operands are
295 // not real values, but indices into statepoint's argument list.
296 // Use the refered to values for purposes of identity.
297 e.varargs.push_back(lookupOrAdd(GCR->getOperand(0)));
298 e.varargs.push_back(lookupOrAdd(GCR->getBasePtr()));
299 e.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
300 } else {
301 for (Use &Op : I->operands())
302 e.varargs.push_back(lookupOrAdd(Op));
303 }
304 if (I->isCommutative()) {
305 // Ensure that commutative instructions that only differ by a permutation
306 // of their operands get the same value number by sorting the operand value
307 // numbers. Since commutative operands are the 1st two operands it is more
308 // efficient to sort by hand rather than using, say, std::sort.
309 assert(I->getNumOperands() >= 2 && "Unsupported commutative instruction!")(static_cast <bool> (I->getNumOperands() >= 2 &&
"Unsupported commutative instruction!") ? void (0) : __assert_fail
("I->getNumOperands() >= 2 && \"Unsupported commutative instruction!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 309, __extension__ __PRETTY_FUNCTION__
))
;
310 if (e.varargs[0] > e.varargs[1])
311 std::swap(e.varargs[0], e.varargs[1]);
312 e.commutative = true;
313 }
314
315 if (auto *C = dyn_cast<CmpInst>(I)) {
316 // Sort the operand value numbers so x<y and y>x get the same value number.
317 CmpInst::Predicate Predicate = C->getPredicate();
318 if (e.varargs[0] > e.varargs[1]) {
319 std::swap(e.varargs[0], e.varargs[1]);
320 Predicate = CmpInst::getSwappedPredicate(Predicate);
321 }
322 e.opcode = (C->getOpcode() << 8) | Predicate;
323 e.commutative = true;
324 } else if (auto *E = dyn_cast<InsertValueInst>(I)) {
325 e.varargs.append(E->idx_begin(), E->idx_end());
326 } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
327 ArrayRef<int> ShuffleMask = SVI->getShuffleMask();
328 e.varargs.append(ShuffleMask.begin(), ShuffleMask.end());
329 }
330
331 return e;
332}
333
334GVNPass::Expression GVNPass::ValueTable::createCmpExpr(
335 unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) {
336 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&(static_cast <bool> ((Opcode == Instruction::ICmp || Opcode
== Instruction::FCmp) && "Not a comparison!") ? void
(0) : __assert_fail ("(Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) && \"Not a comparison!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 337, __extension__ __PRETTY_FUNCTION__
))
337 "Not a comparison!")(static_cast <bool> ((Opcode == Instruction::ICmp || Opcode
== Instruction::FCmp) && "Not a comparison!") ? void
(0) : __assert_fail ("(Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) && \"Not a comparison!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 337, __extension__ __PRETTY_FUNCTION__
))
;
338 Expression e;
339 e.type = CmpInst::makeCmpResultType(LHS->getType());
340 e.varargs.push_back(lookupOrAdd(LHS));
341 e.varargs.push_back(lookupOrAdd(RHS));
342
343 // Sort the operand value numbers so x<y and y>x get the same value number.
344 if (e.varargs[0] > e.varargs[1]) {
345 std::swap(e.varargs[0], e.varargs[1]);
346 Predicate = CmpInst::getSwappedPredicate(Predicate);
347 }
348 e.opcode = (Opcode << 8) | Predicate;
349 e.commutative = true;
350 return e;
351}
352
353GVNPass::Expression
354GVNPass::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) {
355 assert(EI && "Not an ExtractValueInst?")(static_cast <bool> (EI && "Not an ExtractValueInst?"
) ? void (0) : __assert_fail ("EI && \"Not an ExtractValueInst?\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 355, __extension__ __PRETTY_FUNCTION__
))
;
356 Expression e;
357 e.type = EI->getType();
358 e.opcode = 0;
359
360 WithOverflowInst *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
361 if (WO != nullptr && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
362 // EI is an extract from one of our with.overflow intrinsics. Synthesize
363 // a semantically equivalent expression instead of an extract value
364 // expression.
365 e.opcode = WO->getBinaryOp();
366 e.varargs.push_back(lookupOrAdd(WO->getLHS()));
367 e.varargs.push_back(lookupOrAdd(WO->getRHS()));
368 return e;
369 }
370
371 // Not a recognised intrinsic. Fall back to producing an extract value
372 // expression.
373 e.opcode = EI->getOpcode();
374 for (Use &Op : EI->operands())
375 e.varargs.push_back(lookupOrAdd(Op));
376
377 append_range(e.varargs, EI->indices());
378
379 return e;
380}
381
382//===----------------------------------------------------------------------===//
383// ValueTable External Functions
384//===----------------------------------------------------------------------===//
385
386GVNPass::ValueTable::ValueTable() = default;
387GVNPass::ValueTable::ValueTable(const ValueTable &) = default;
388GVNPass::ValueTable::ValueTable(ValueTable &&) = default;
389GVNPass::ValueTable::~ValueTable() = default;
390GVNPass::ValueTable &
391GVNPass::ValueTable::operator=(const GVNPass::ValueTable &Arg) = default;
392
393/// add - Insert a value into the table with a specified value number.
394void GVNPass::ValueTable::add(Value *V, uint32_t num) {
395 valueNumbering.insert(std::make_pair(V, num));
396 if (PHINode *PN = dyn_cast<PHINode>(V))
397 NumberingPhi[num] = PN;
398}
399
400uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) {
401 if (AA->doesNotAccessMemory(C)) {
402 Expression exp = createExpr(C);
403 uint32_t e = assignExpNewValueNum(exp).first;
404 valueNumbering[C] = e;
405 return e;
406 } else if (MD && AA->onlyReadsMemory(C)) {
407 Expression exp = createExpr(C);
408 auto ValNum = assignExpNewValueNum(exp);
409 if (ValNum.second) {
410 valueNumbering[C] = ValNum.first;
411 return ValNum.first;
412 }
413
414 MemDepResult local_dep = MD->getDependency(C);
415
416 if (!local_dep.isDef() && !local_dep.isNonLocal()) {
417 valueNumbering[C] = nextValueNumber;
418 return nextValueNumber++;
419 }
420
421 if (local_dep.isDef()) {
422 // For masked load/store intrinsics, the local_dep may actully be
423 // a normal load or store instruction.
424 CallInst *local_cdep = dyn_cast<CallInst>(local_dep.getInst());
425
426 if (!local_cdep || local_cdep->arg_size() != C->arg_size()) {
427 valueNumbering[C] = nextValueNumber;
428 return nextValueNumber++;
429 }
430
431 for (unsigned i = 0, e = C->arg_size(); i < e; ++i) {
432 uint32_t c_vn = lookupOrAdd(C->getArgOperand(i));
433 uint32_t cd_vn = lookupOrAdd(local_cdep->getArgOperand(i));
434 if (c_vn != cd_vn) {
435 valueNumbering[C] = nextValueNumber;
436 return nextValueNumber++;
437 }
438 }
439
440 uint32_t v = lookupOrAdd(local_cdep);
441 valueNumbering[C] = v;
442 return v;
443 }
444
445 // Non-local case.
446 const MemoryDependenceResults::NonLocalDepInfo &deps =
447 MD->getNonLocalCallDependency(C);
448 // FIXME: Move the checking logic to MemDep!
449 CallInst* cdep = nullptr;
450
451 // Check to see if we have a single dominating call instruction that is
452 // identical to C.
453 for (unsigned i = 0, e = deps.size(); i != e; ++i) {
454 const NonLocalDepEntry *I = &deps[i];
455 if (I->getResult().isNonLocal())
456 continue;
457
458 // We don't handle non-definitions. If we already have a call, reject
459 // instruction dependencies.
460 if (!I->getResult().isDef() || cdep != nullptr) {
461 cdep = nullptr;
462 break;
463 }
464
465 CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->getResult().getInst());
466 // FIXME: All duplicated with non-local case.
467 if (NonLocalDepCall && DT->properlyDominates(I->getBB(), C->getParent())){
468 cdep = NonLocalDepCall;
469 continue;
470 }
471
472 cdep = nullptr;
473 break;
474 }
475
476 if (!cdep) {
477 valueNumbering[C] = nextValueNumber;
478 return nextValueNumber++;
479 }
480
481 if (cdep->arg_size() != C->arg_size()) {
482 valueNumbering[C] = nextValueNumber;
483 return nextValueNumber++;
484 }
485 for (unsigned i = 0, e = C->arg_size(); i < e; ++i) {
486 uint32_t c_vn = lookupOrAdd(C->getArgOperand(i));
487 uint32_t cd_vn = lookupOrAdd(cdep->getArgOperand(i));
488 if (c_vn != cd_vn) {
489 valueNumbering[C] = nextValueNumber;
490 return nextValueNumber++;
491 }
492 }
493
494 uint32_t v = lookupOrAdd(cdep);
495 valueNumbering[C] = v;
496 return v;
497 } else {
498 valueNumbering[C] = nextValueNumber;
499 return nextValueNumber++;
500 }
501}
502
503/// Returns true if a value number exists for the specified value.
504bool GVNPass::ValueTable::exists(Value *V) const {
505 return valueNumbering.count(V) != 0;
506}
507
508/// lookup_or_add - Returns the value number for the specified value, assigning
509/// it a new number if it did not have one before.
510uint32_t GVNPass::ValueTable::lookupOrAdd(Value *V) {
511 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
512 if (VI != valueNumbering.end())
513 return VI->second;
514
515 if (!isa<Instruction>(V)) {
516 valueNumbering[V] = nextValueNumber;
517 return nextValueNumber++;
518 }
519
520 Instruction* I = cast<Instruction>(V);
521 Expression exp;
522 switch (I->getOpcode()) {
523 case Instruction::Call:
524 return lookupOrAddCall(cast<CallInst>(I));
525 case Instruction::FNeg:
526 case Instruction::Add:
527 case Instruction::FAdd:
528 case Instruction::Sub:
529 case Instruction::FSub:
530 case Instruction::Mul:
531 case Instruction::FMul:
532 case Instruction::UDiv:
533 case Instruction::SDiv:
534 case Instruction::FDiv:
535 case Instruction::URem:
536 case Instruction::SRem:
537 case Instruction::FRem:
538 case Instruction::Shl:
539 case Instruction::LShr:
540 case Instruction::AShr:
541 case Instruction::And:
542 case Instruction::Or:
543 case Instruction::Xor:
544 case Instruction::ICmp:
545 case Instruction::FCmp:
546 case Instruction::Trunc:
547 case Instruction::ZExt:
548 case Instruction::SExt:
549 case Instruction::FPToUI:
550 case Instruction::FPToSI:
551 case Instruction::UIToFP:
552 case Instruction::SIToFP:
553 case Instruction::FPTrunc:
554 case Instruction::FPExt:
555 case Instruction::PtrToInt:
556 case Instruction::IntToPtr:
557 case Instruction::AddrSpaceCast:
558 case Instruction::BitCast:
559 case Instruction::Select:
560 case Instruction::Freeze:
561 case Instruction::ExtractElement:
562 case Instruction::InsertElement:
563 case Instruction::ShuffleVector:
564 case Instruction::InsertValue:
565 case Instruction::GetElementPtr:
566 exp = createExpr(I);
567 break;
568 case Instruction::ExtractValue:
569 exp = createExtractvalueExpr(cast<ExtractValueInst>(I));
570 break;
571 case Instruction::PHI:
572 valueNumbering[V] = nextValueNumber;
573 NumberingPhi[nextValueNumber] = cast<PHINode>(V);
574 return nextValueNumber++;
575 default:
576 valueNumbering[V] = nextValueNumber;
577 return nextValueNumber++;
578 }
579
580 uint32_t e = assignExpNewValueNum(exp).first;
581 valueNumbering[V] = e;
582 return e;
583}
584
585/// Returns the value number of the specified value. Fails if
586/// the value has not yet been numbered.
587uint32_t GVNPass::ValueTable::lookup(Value *V, bool Verify) const {
588 DenseMap<Value*, uint32_t>::const_iterator VI = valueNumbering.find(V);
589 if (Verify) {
590 assert(VI != valueNumbering.end() && "Value not numbered?")(static_cast <bool> (VI != valueNumbering.end() &&
"Value not numbered?") ? void (0) : __assert_fail ("VI != valueNumbering.end() && \"Value not numbered?\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 590, __extension__ __PRETTY_FUNCTION__
))
;
591 return VI->second;
592 }
593 return (VI != valueNumbering.end()) ? VI->second : 0;
594}
595
596/// Returns the value number of the given comparison,
597/// assigning it a new number if it did not have one before. Useful when
598/// we deduced the result of a comparison, but don't immediately have an
599/// instruction realizing that comparison to hand.
600uint32_t GVNPass::ValueTable::lookupOrAddCmp(unsigned Opcode,
601 CmpInst::Predicate Predicate,
602 Value *LHS, Value *RHS) {
603 Expression exp = createCmpExpr(Opcode, Predicate, LHS, RHS);
604 return assignExpNewValueNum(exp).first;
605}
606
607/// Remove all entries from the ValueTable.
608void GVNPass::ValueTable::clear() {
609 valueNumbering.clear();
610 expressionNumbering.clear();
611 NumberingPhi.clear();
612 PhiTranslateTable.clear();
613 nextValueNumber = 1;
614 Expressions.clear();
615 ExprIdx.clear();
616 nextExprNumber = 0;
617}
618
619/// Remove a value from the value numbering.
620void GVNPass::ValueTable::erase(Value *V) {
621 uint32_t Num = valueNumbering.lookup(V);
622 valueNumbering.erase(V);
623 // If V is PHINode, V <--> value number is an one-to-one mapping.
624 if (isa<PHINode>(V))
625 NumberingPhi.erase(Num);
626}
627
628/// verifyRemoved - Verify that the value is removed from all internal data
629/// structures.
630void GVNPass::ValueTable::verifyRemoved(const Value *V) const {
631 for (DenseMap<Value*, uint32_t>::const_iterator
632 I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
633 assert(I->first != V && "Inst still occurs in value numbering map!")(static_cast <bool> (I->first != V && "Inst still occurs in value numbering map!"
) ? void (0) : __assert_fail ("I->first != V && \"Inst still occurs in value numbering map!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 633, __extension__ __PRETTY_FUNCTION__
))
;
634 }
635}
636
637//===----------------------------------------------------------------------===//
638// GVN Pass
639//===----------------------------------------------------------------------===//
640
641bool GVNPass::isPREEnabled() const {
642 return Options.AllowPRE.getValueOr(GVNEnablePRE);
643}
644
645bool GVNPass::isLoadPREEnabled() const {
646 return Options.AllowLoadPRE.getValueOr(GVNEnableLoadPRE);
647}
648
649bool GVNPass::isLoadInLoopPREEnabled() const {
650 return Options.AllowLoadInLoopPRE.getValueOr(GVNEnableLoadInLoopPRE);
651}
652
653bool GVNPass::isLoadPRESplitBackedgeEnabled() const {
654 return Options.AllowLoadPRESplitBackedge.getValueOr(
655 GVNEnableSplitBackedgeInLoadPRE);
656}
657
658bool GVNPass::isMemDepEnabled() const {
659 return Options.AllowMemDep.getValueOr(GVNEnableMemDep);
660}
661
662PreservedAnalyses GVNPass::run(Function &F, FunctionAnalysisManager &AM) {
663 // FIXME: The order of evaluation of these 'getResult' calls is very
664 // significant! Re-ordering these variables will cause GVN when run alone to
665 // be less effective! We should fix memdep and basic-aa to not exhibit this
666 // behavior, but until then don't change the order here.
667 auto &AC = AM.getResult<AssumptionAnalysis>(F);
668 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
669 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
670 auto &AA = AM.getResult<AAManager>(F);
671 auto *MemDep =
672 isMemDepEnabled() ? &AM.getResult<MemoryDependenceAnalysis>(F) : nullptr;
673 auto *LI = AM.getCachedResult<LoopAnalysis>(F);
674 auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);
675 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
676 bool Changed = runImpl(F, AC, DT, TLI, AA, MemDep, LI, &ORE,
677 MSSA ? &MSSA->getMSSA() : nullptr);
678 if (!Changed)
679 return PreservedAnalyses::all();
680 PreservedAnalyses PA;
681 PA.preserve<DominatorTreeAnalysis>();
682 PA.preserve<TargetLibraryAnalysis>();
683 if (MSSA)
684 PA.preserve<MemorySSAAnalysis>();
685 if (LI)
686 PA.preserve<LoopAnalysis>();
687 return PA;
688}
689
690void GVNPass::printPipeline(
691 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
692 static_cast<PassInfoMixin<GVNPass> *>(this)->printPipeline(
693 OS, MapClassName2PassName);
694
695 OS << "<";
696 if (Options.AllowPRE != None)
697 OS << (Options.AllowPRE.getValue() ? "" : "no-") << "pre;";
698 if (Options.AllowLoadPRE != None)
699 OS << (Options.AllowLoadPRE.getValue() ? "" : "no-") << "load-pre;";
700 if (Options.AllowLoadPRESplitBackedge != None)
701 OS << (Options.AllowLoadPRESplitBackedge.getValue() ? "" : "no-")
702 << "split-backedge-load-pre;";
703 if (Options.AllowMemDep != None)
704 OS << (Options.AllowMemDep.getValue() ? "" : "no-") << "memdep";
705 OS << ">";
706}
707
708#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
709LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void GVNPass::dump(DenseMap<uint32_t, Value *> &d) const {
710 errs() << "{\n";
711 for (auto &I : d) {
712 errs() << I.first << "\n";
713 I.second->dump();
714 }
715 errs() << "}\n";
716}
717#endif
718
719enum class AvailabilityState : char {
720 /// We know the block *is not* fully available. This is a fixpoint.
721 Unavailable = 0,
722 /// We know the block *is* fully available. This is a fixpoint.
723 Available = 1,
724 /// We do not know whether the block is fully available or not,
725 /// but we are currently speculating that it will be.
726 /// If it would have turned out that the block was, in fact, not fully
727 /// available, this would have been cleaned up into an Unavailable.
728 SpeculativelyAvailable = 2,
729};
730
731/// Return true if we can prove that the value
732/// we're analyzing is fully available in the specified block. As we go, keep
733/// track of which blocks we know are fully alive in FullyAvailableBlocks. This
734/// map is actually a tri-state map with the following values:
735/// 0) we know the block *is not* fully available.
736/// 1) we know the block *is* fully available.
737/// 2) we do not know whether the block is fully available or not, but we are
738/// currently speculating that it will be.
739static bool IsValueFullyAvailableInBlock(
740 BasicBlock *BB,
741 DenseMap<BasicBlock *, AvailabilityState> &FullyAvailableBlocks) {
742 SmallVector<BasicBlock *, 32> Worklist;
743 Optional<BasicBlock *> UnavailableBB;
744
745 // The number of times we didn't find an entry for a block in a map and
746 // optimistically inserted an entry marking block as speculatively available.
747 unsigned NumNewNewSpeculativelyAvailableBBs = 0;
748
749#ifndef NDEBUG
750 SmallSet<BasicBlock *, 32> NewSpeculativelyAvailableBBs;
751 SmallVector<BasicBlock *, 32> AvailableBBs;
752#endif
753
754 Worklist.emplace_back(BB);
755 while (!Worklist.empty()) {
756 BasicBlock *CurrBB = Worklist.pop_back_val(); // LoadFO - depth-first!
757 // Optimistically assume that the block is Speculatively Available and check
758 // to see if we already know about this block in one lookup.
759 std::pair<DenseMap<BasicBlock *, AvailabilityState>::iterator, bool> IV =
760 FullyAvailableBlocks.try_emplace(
761 CurrBB, AvailabilityState::SpeculativelyAvailable);
762 AvailabilityState &State = IV.first->second;
763
764 // Did the entry already exist for this block?
765 if (!IV.second) {
766 if (State == AvailabilityState::Unavailable) {
767 UnavailableBB = CurrBB;
768 break; // Backpropagate unavailability info.
769 }
770
771#ifndef NDEBUG
772 AvailableBBs.emplace_back(CurrBB);
773#endif
774 continue; // Don't recurse further, but continue processing worklist.
775 }
776
777 // No entry found for block.
778 ++NumNewNewSpeculativelyAvailableBBs;
779 bool OutOfBudget = NumNewNewSpeculativelyAvailableBBs > MaxBBSpeculations;
780
781 // If we have exhausted our budget, mark this block as unavailable.
782 // Also, if this block has no predecessors, the value isn't live-in here.
783 if (OutOfBudget || pred_empty(CurrBB)) {
784 MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget;
785 State = AvailabilityState::Unavailable;
786 UnavailableBB = CurrBB;
787 break; // Backpropagate unavailability info.
788 }
789
790 // Tentatively consider this block as speculatively available.
791#ifndef NDEBUG
792 NewSpeculativelyAvailableBBs.insert(CurrBB);
793#endif
794 // And further recurse into block's predecessors, in depth-first order!
795 Worklist.append(pred_begin(CurrBB), pred_end(CurrBB));
796 }
797
798#if LLVM_ENABLE_STATS1
799 IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax(
800 NumNewNewSpeculativelyAvailableBBs);
801#endif
802
803 // If the block isn't marked as fixpoint yet
804 // (the Unavailable and Available states are fixpoints)
805 auto MarkAsFixpointAndEnqueueSuccessors =
806 [&](BasicBlock *BB, AvailabilityState FixpointState) {
807 auto It = FullyAvailableBlocks.find(BB);
808 if (It == FullyAvailableBlocks.end())
809 return; // Never queried this block, leave as-is.
810 switch (AvailabilityState &State = It->second) {
811 case AvailabilityState::Unavailable:
812 case AvailabilityState::Available:
813 return; // Don't backpropagate further, continue processing worklist.
814 case AvailabilityState::SpeculativelyAvailable: // Fix it!
815 State = FixpointState;
816#ifndef NDEBUG
817 assert(NewSpeculativelyAvailableBBs.erase(BB) &&(static_cast <bool> (NewSpeculativelyAvailableBBs.erase
(BB) && "Found a speculatively available successor leftover?"
) ? void (0) : __assert_fail ("NewSpeculativelyAvailableBBs.erase(BB) && \"Found a speculatively available successor leftover?\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 818, __extension__ __PRETTY_FUNCTION__
))
818 "Found a speculatively available successor leftover?")(static_cast <bool> (NewSpeculativelyAvailableBBs.erase
(BB) && "Found a speculatively available successor leftover?"
) ? void (0) : __assert_fail ("NewSpeculativelyAvailableBBs.erase(BB) && \"Found a speculatively available successor leftover?\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 818, __extension__ __PRETTY_FUNCTION__
))
;
819#endif
820 // Queue successors for further processing.
821 Worklist.append(succ_begin(BB), succ_end(BB));
822 return;
823 }
824 };
825
826 if (UnavailableBB) {
827 // Okay, we have encountered an unavailable block.
828 // Mark speculatively available blocks reachable from UnavailableBB as
829 // unavailable as well. Paths are terminated when they reach blocks not in
830 // FullyAvailableBlocks or they are not marked as speculatively available.
831 Worklist.clear();
832 Worklist.append(succ_begin(*UnavailableBB), succ_end(*UnavailableBB));
833 while (!Worklist.empty())
834 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
835 AvailabilityState::Unavailable);
836 }
837
838#ifndef NDEBUG
839 Worklist.clear();
840 for (BasicBlock *AvailableBB : AvailableBBs)
841 Worklist.append(succ_begin(AvailableBB), succ_end(AvailableBB));
842 while (!Worklist.empty())
843 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
844 AvailabilityState::Available);
845
846 assert(NewSpeculativelyAvailableBBs.empty() &&(static_cast <bool> (NewSpeculativelyAvailableBBs.empty
() && "Must have fixed all the new speculatively available blocks."
) ? void (0) : __assert_fail ("NewSpeculativelyAvailableBBs.empty() && \"Must have fixed all the new speculatively available blocks.\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 847, __extension__ __PRETTY_FUNCTION__
))
847 "Must have fixed all the new speculatively available blocks.")(static_cast <bool> (NewSpeculativelyAvailableBBs.empty
() && "Must have fixed all the new speculatively available blocks."
) ? void (0) : __assert_fail ("NewSpeculativelyAvailableBBs.empty() && \"Must have fixed all the new speculatively available blocks.\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 847, __extension__ __PRETTY_FUNCTION__
))
;
848#endif
849
850 return !UnavailableBB;
851}
852
853/// Given a set of loads specified by ValuesPerBlock,
854/// construct SSA form, allowing us to eliminate Load. This returns the value
855/// that should be used at Load's definition site.
856static Value *
857ConstructSSAForLoadSet(LoadInst *Load,
858 SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
859 GVNPass &gvn) {
860 // Check for the fully redundant, dominating load case. In this case, we can
861 // just use the dominating value directly.
862 if (ValuesPerBlock.size() == 1 &&
863 gvn.getDominatorTree().properlyDominates(ValuesPerBlock[0].BB,
864 Load->getParent())) {
865 assert(!ValuesPerBlock[0].AV.isUndefValue() &&(static_cast <bool> (!ValuesPerBlock[0].AV.isUndefValue
() && "Dead BB dominate this block") ? void (0) : __assert_fail
("!ValuesPerBlock[0].AV.isUndefValue() && \"Dead BB dominate this block\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 866, __extension__ __PRETTY_FUNCTION__
))
866 "Dead BB dominate this block")(static_cast <bool> (!ValuesPerBlock[0].AV.isUndefValue
() && "Dead BB dominate this block") ? void (0) : __assert_fail
("!ValuesPerBlock[0].AV.isUndefValue() && \"Dead BB dominate this block\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 866, __extension__ __PRETTY_FUNCTION__
))
;
867 return ValuesPerBlock[0].MaterializeAdjustedValue(Load, gvn);
868 }
869
870 // Otherwise, we have to construct SSA form.
871 SmallVector<PHINode*, 8> NewPHIs;
872 SSAUpdater SSAUpdate(&NewPHIs);
873 SSAUpdate.Initialize(Load->getType(), Load->getName());
874
875 for (const AvailableValueInBlock &AV : ValuesPerBlock) {
876 BasicBlock *BB = AV.BB;
877
878 if (AV.AV.isUndefValue())
879 continue;
880
881 if (SSAUpdate.HasValueForBlock(BB))
882 continue;
883
884 // If the value is the load that we will be eliminating, and the block it's
885 // available in is the block that the load is in, then don't add it as
886 // SSAUpdater will resolve the value to the relevant phi which may let it
887 // avoid phi construction entirely if there's actually only one value.
888 if (BB == Load->getParent() &&
889 ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == Load) ||
890 (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == Load)))
891 continue;
892
893 SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(Load, gvn));
894 }
895
896 // Perform PHI construction.
897 return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
898}
899
900Value *AvailableValue::MaterializeAdjustedValue(LoadInst *Load,
901 Instruction *InsertPt,
902 GVNPass &gvn) const {
903 Value *Res;
904 Type *LoadTy = Load->getType();
905 const DataLayout &DL = Load->getModule()->getDataLayout();
906 if (isSimpleValue()) {
907 Res = getSimpleValue();
908 if (Res->getType() != LoadTy) {
909 Res = getStoreValueForLoad(Res, Offset, LoadTy, InsertPt, DL);
910
911 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offsetdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: "
<< Offset << " " << *getSimpleValue() <<
'\n' << *Res << '\n' << "\n\n\n"; } } while
(false)
912 << " " << *getSimpleValue() << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: "
<< Offset << " " << *getSimpleValue() <<
'\n' << *Res << '\n' << "\n\n\n"; } } while
(false)
913 << *Res << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: "
<< Offset << " " << *getSimpleValue() <<
'\n' << *Res << '\n' << "\n\n\n"; } } while
(false)
914 << "\n\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: "
<< Offset << " " << *getSimpleValue() <<
'\n' << *Res << '\n' << "\n\n\n"; } } while
(false)
;
915 }
916 } else if (isCoercedLoadValue()) {
917 LoadInst *CoercedLoad = getCoercedLoadValue();
918 if (CoercedLoad->getType() == LoadTy && Offset == 0) {
919 Res = CoercedLoad;
920 } else {
921 Res = getLoadValueForLoad(CoercedLoad, Offset, LoadTy, InsertPt, DL);
922 // We would like to use gvn.markInstructionForDeletion here, but we can't
923 // because the load is already memoized into the leader map table that GVN
924 // tracks. It is potentially possible to remove the load from the table,
925 // but then there all of the operations based on it would need to be
926 // rehashed. Just leave the dead load around.
927 gvn.getMemDep().removeInstruction(CoercedLoad);
928 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offsetdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: "
<< Offset << " " << *getCoercedLoadValue(
) << '\n' << *Res << '\n' << "\n\n\n"
; } } while (false)
929 << " " << *getCoercedLoadValue() << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: "
<< Offset << " " << *getCoercedLoadValue(
) << '\n' << *Res << '\n' << "\n\n\n"
; } } while (false)
930 << *Res << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: "
<< Offset << " " << *getCoercedLoadValue(
) << '\n' << *Res << '\n' << "\n\n\n"
; } } while (false)
931 << "\n\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: "
<< Offset << " " << *getCoercedLoadValue(
) << '\n' << *Res << '\n' << "\n\n\n"
; } } while (false)
;
932 }
933 } else if (isMemIntrinValue()) {
934 Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,
935 InsertPt, DL);
936 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offsetdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: "
<< Offset << " " << *getMemIntrinValue() <<
'\n' << *Res << '\n' << "\n\n\n"; } } while
(false)
937 << " " << *getMemIntrinValue() << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: "
<< Offset << " " << *getMemIntrinValue() <<
'\n' << *Res << '\n' << "\n\n\n"; } } while
(false)
938 << *Res << '\n'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: "
<< Offset << " " << *getMemIntrinValue() <<
'\n' << *Res << '\n' << "\n\n\n"; } } while
(false)
939 << "\n\n\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: "
<< Offset << " " << *getMemIntrinValue() <<
'\n' << *Res << '\n' << "\n\n\n"; } } while
(false)
;
940 } else {
941 llvm_unreachable("Should not materialize value from dead block")::llvm::llvm_unreachable_internal("Should not materialize value from dead block"
, "llvm/lib/Transforms/Scalar/GVN.cpp", 941)
;
942 }
943 assert(Res && "failed to materialize?")(static_cast <bool> (Res && "failed to materialize?"
) ? void (0) : __assert_fail ("Res && \"failed to materialize?\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 943, __extension__ __PRETTY_FUNCTION__
))
;
944 return Res;
945}
946
947static bool isLifetimeStart(const Instruction *Inst) {
948 if (const IntrinsicInst* II = dyn_cast<IntrinsicInst>(Inst))
949 return II->getIntrinsicID() == Intrinsic::lifetime_start;
950 return false;
951}
952
953/// Assuming To can be reached from both From and Between, does Between lie on
954/// every path from From to To?
955static bool liesBetween(const Instruction *From, Instruction *Between,
956 const Instruction *To, DominatorTree *DT) {
957 if (From->getParent() == Between->getParent())
958 return DT->dominates(From, Between);
959 SmallSet<BasicBlock *, 1> Exclusion;
960 Exclusion.insert(Between->getParent());
961 return !isPotentiallyReachable(From, To, &Exclusion, DT);
962}
963
964/// Try to locate the three instruction involved in a missed
965/// load-elimination case that is due to an intervening store.
966static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo,
967 DominatorTree *DT,
968 OptimizationRemarkEmitter *ORE) {
969 using namespace ore;
970
971 User *OtherAccess = nullptr;
972
973 OptimizationRemarkMissed R(DEBUG_TYPE"gvn", "LoadClobbered", Load);
974 R << "load of type " << NV("Type", Load->getType()) << " not eliminated"
975 << setExtraArgs();
976
977 for (auto *U : Load->getPointerOperand()->users()) {
978 if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
979 cast<Instruction>(U)->getFunction() == Load->getFunction() &&
980 DT->dominates(cast<Instruction>(U), Load)) {
981 // Use the most immediately dominating value
982 if (OtherAccess) {
983 if (DT->dominates(cast<Instruction>(OtherAccess), cast<Instruction>(U)))
984 OtherAccess = U;
985 else
986 assert(DT->dominates(cast<Instruction>(U),(static_cast <bool> (DT->dominates(cast<Instruction
>(U), cast<Instruction>(OtherAccess))) ? void (0) : __assert_fail
("DT->dominates(cast<Instruction>(U), cast<Instruction>(OtherAccess))"
, "llvm/lib/Transforms/Scalar/GVN.cpp", 987, __extension__ __PRETTY_FUNCTION__
))
987 cast<Instruction>(OtherAccess)))(static_cast <bool> (DT->dominates(cast<Instruction
>(U), cast<Instruction>(OtherAccess))) ? void (0) : __assert_fail
("DT->dominates(cast<Instruction>(U), cast<Instruction>(OtherAccess))"
, "llvm/lib/Transforms/Scalar/GVN.cpp", 987, __extension__ __PRETTY_FUNCTION__
))
;
988 } else
989 OtherAccess = U;
990 }
991 }
992
993 if (!OtherAccess) {
994 // There is no dominating use, check if we can find a closest non-dominating
995 // use that lies between any other potentially available use and Load.
996 for (auto *U : Load->getPointerOperand()->users()) {
997 if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
998 cast<Instruction>(U)->getFunction() == Load->getFunction() &&
999 isPotentiallyReachable(cast<Instruction>(U), Load, nullptr, DT)) {
1000 if (OtherAccess) {
1001 if (liesBetween(cast<Instruction>(OtherAccess), cast<Instruction>(U),
1002 Load, DT)) {
1003 OtherAccess = U;
1004 } else if (!liesBetween(cast<Instruction>(U),
1005 cast<Instruction>(OtherAccess), Load, DT)) {
1006 // These uses are both partially available at Load were it not for
1007 // the clobber, but neither lies strictly after the other.
1008 OtherAccess = nullptr;
1009 break;
1010 } // else: keep current OtherAccess since it lies between U and Load
1011 } else {
1012 OtherAccess = U;
1013 }
1014 }
1015 }
1016 }
1017
1018 if (OtherAccess)
1019 R << " in favor of " << NV("OtherAccess", OtherAccess);
1020
1021 R << " because it is clobbered by " << NV("ClobberedBy", DepInfo.getInst());
1022
1023 ORE->emit(R);
1024}
1025
1026bool GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
1027 Value *Address, AvailableValue &Res) {
1028 assert((DepInfo.isDef() || DepInfo.isClobber()) &&(static_cast <bool> ((DepInfo.isDef() || DepInfo.isClobber
()) && "expected a local dependence") ? void (0) : __assert_fail
("(DepInfo.isDef() || DepInfo.isClobber()) && \"expected a local dependence\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 1029, __extension__ __PRETTY_FUNCTION__
))
1029 "expected a local dependence")(static_cast <bool> ((DepInfo.isDef() || DepInfo.isClobber
()) && "expected a local dependence") ? void (0) : __assert_fail
("(DepInfo.isDef() || DepInfo.isClobber()) && \"expected a local dependence\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 1029, __extension__ __PRETTY_FUNCTION__
))
;
1030 assert(Load->isUnordered() && "rules below are incorrect for ordered access")(static_cast <bool> (Load->isUnordered() && "rules below are incorrect for ordered access"
) ? void (0) : __assert_fail ("Load->isUnordered() && \"rules below are incorrect for ordered access\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 1030, __extension__ __PRETTY_FUNCTION__
))
;
1031
1032 const DataLayout &DL = Load->getModule()->getDataLayout();
1033
1034 Instruction *DepInst = DepInfo.getInst();
1035 if (DepInfo.isClobber()) {
1036 // If the dependence is to a store that writes to a superset of the bits
1037 // read by the load, we can extract the bits we need for the load from the
1038 // stored value.
1039 if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
1040 // Can't forward from non-atomic to atomic without violating memory model.
1041 if (Address && Load->isAtomic() <= DepSI->isAtomic()) {
1042 int Offset =
1043 analyzeLoadFromClobberingStore(Load->getType(), Address, DepSI, DL);
1044 if (Offset != -1) {
1045 Res = AvailableValue::get(DepSI->getValueOperand(), Offset);
1046 return true;
1047 }
1048 }
1049 }
1050
1051 // Check to see if we have something like this:
1052 // load i32* P
1053 // load i8* (P+1)
1054 // if we have this, replace the later with an extraction from the former.
1055 if (LoadInst *DepLoad = dyn_cast<LoadInst>(DepInst)) {
1056 // If this is a clobber and L is the first instruction in its block, then
1057 // we have the first instruction in the entry block.
1058 // Can't forward from non-atomic to atomic without violating memory model.
1059 if (DepLoad != Load && Address &&
1060 Load->isAtomic() <= DepLoad->isAtomic()) {
1061 Type *LoadType = Load->getType();
1062 int Offset = -1;
1063
1064 // If MD reported clobber, check it was nested.
1065 if (DepInfo.isClobber() &&
1066 canCoerceMustAliasedValueToLoad(DepLoad, LoadType, DL)) {
1067 const auto ClobberOff = MD->getClobberOffset(DepLoad);
1068 // GVN has no deal with a negative offset.
1069 Offset = (ClobberOff == None || ClobberOff.getValue() < 0)
1070 ? -1
1071 : ClobberOff.getValue();
1072 }
1073 if (Offset == -1)
1074 Offset =
1075 analyzeLoadFromClobberingLoad(LoadType, Address, DepLoad, DL);
1076 if (Offset != -1) {
1077 Res = AvailableValue::getLoad(DepLoad, Offset);
1078 return true;
1079 }
1080 }
1081 }
1082
1083 // If the clobbering value is a memset/memcpy/memmove, see if we can
1084 // forward a value on from it.
1085 if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1086 if (Address && !Load->isAtomic()) {
1087 int Offset = analyzeLoadFromClobberingMemInst(Load->getType(), Address,
1088 DepMI, DL);
1089 if (Offset != -1) {
1090 Res = AvailableValue::getMI(DepMI, Offset);
1091 return true;
1092 }
1093 }
1094 }
1095 // Nothing known about this clobber, have to be conservative
1096 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; Load->printAsOperand
(dbgs()); dbgs() << " is clobbered by " << *DepInst
<< '\n';; } } while (false)
1097 // fast print dep, using operator<< on instruction is too slow.do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; Load->printAsOperand
(dbgs()); dbgs() << " is clobbered by " << *DepInst
<< '\n';; } } while (false)
1098 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; Load->printAsOperand
(dbgs()); dbgs() << " is clobbered by " << *DepInst
<< '\n';; } } while (false)
1099 dbgs() << " is clobbered by " << *DepInst << '\n';)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; Load->printAsOperand
(dbgs()); dbgs() << " is clobbered by " << *DepInst
<< '\n';; } } while (false)
;
1100 if (ORE->allowExtraAnalysis(DEBUG_TYPE"gvn"))
1101 reportMayClobberedLoad(Load, DepInfo, DT, ORE);
1102
1103 return false;
1104 }
1105 assert(DepInfo.isDef() && "follows from above")(static_cast <bool> (DepInfo.isDef() && "follows from above"
) ? void (0) : __assert_fail ("DepInfo.isDef() && \"follows from above\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 1105, __extension__ __PRETTY_FUNCTION__
))
;
1106
1107 // Loading the alloca -> undef.
1108 // Loading immediately after lifetime begin -> undef.
1109 if (isa<AllocaInst>(DepInst) || isLifetimeStart(DepInst)) {
1110 Res = AvailableValue::get(UndefValue::get(Load->getType()));
1111 return true;
1112 }
1113
1114 if (isAllocationFn(DepInst, TLI))
1115 if (auto *InitVal = getInitialValueOfAllocation(cast<CallBase>(DepInst),
1116 TLI, Load->getType())) {
1117 Res = AvailableValue::get(InitVal);
1118 return true;
1119 }
1120
1121 if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
1122 // Reject loads and stores that are to the same address but are of
1123 // different types if we have to. If the stored value is convertable to
1124 // the loaded value, we can reuse it.
1125 if (!canCoerceMustAliasedValueToLoad(S->getValueOperand(), Load->getType(),
1126 DL))
1127 return false;
1128
1129 // Can't forward from non-atomic to atomic without violating memory model.
1130 if (S->isAtomic() < Load->isAtomic())
1131 return false;
1132
1133 Res = AvailableValue::get(S->getValueOperand());
1134 return true;
1135 }
1136
1137 if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) {
1138 // If the types mismatch and we can't handle it, reject reuse of the load.
1139 // If the stored value is larger or equal to the loaded value, we can reuse
1140 // it.
1141 if (!canCoerceMustAliasedValueToLoad(LD, Load->getType(), DL))
1142 return false;
1143
1144 // Can't forward from non-atomic to atomic without violating memory model.
1145 if (LD->isAtomic() < Load->isAtomic())
1146 return false;
1147
1148 Res = AvailableValue::getLoad(LD);
1149 return true;
1150 }
1151
1152 // Unknown def - must be conservative
1153 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; Load->printAsOperand
(dbgs()); dbgs() << " has unknown def " << *DepInst
<< '\n';; } } while (false)
1154 // fast print dep, using operator<< on instruction is too slow.do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; Load->printAsOperand
(dbgs()); dbgs() << " has unknown def " << *DepInst
<< '\n';; } } while (false)
1155 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; Load->printAsOperand
(dbgs()); dbgs() << " has unknown def " << *DepInst
<< '\n';; } } while (false)
1156 dbgs() << " has unknown def " << *DepInst << '\n';)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; Load->printAsOperand
(dbgs()); dbgs() << " has unknown def " << *DepInst
<< '\n';; } } while (false)
;
1157 return false;
1158}
1159
1160void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
1161 AvailValInBlkVect &ValuesPerBlock,
1162 UnavailBlkVect &UnavailableBlocks) {
1163 // Filter out useless results (non-locals, etc). Keep track of the blocks
1164 // where we have a value available in repl, also keep track of whether we see
1165 // dependencies that produce an unknown value for the load (such as a call
1166 // that could potentially clobber the load).
1167 unsigned NumDeps = Deps.size();
1168 for (unsigned i = 0, e = NumDeps; i != e; ++i) {
1169 BasicBlock *DepBB = Deps[i].getBB();
1170 MemDepResult DepInfo = Deps[i].getResult();
1171
1172 if (DeadBlocks.count(DepBB)) {
1173 // Dead dependent mem-op disguise as a load evaluating the same value
1174 // as the load in question.
1175 ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
1176 continue;
1177 }
1178
1179 if (!DepInfo.isDef() && !DepInfo.isClobber()) {
1180 UnavailableBlocks.push_back(DepBB);
1181 continue;
1182 }
1183
1184 // The address being loaded in this non-local block may not be the same as
1185 // the pointer operand of the load if PHI translation occurs. Make sure
1186 // to consider the right address.
1187 Value *Address = Deps[i].getAddress();
1188
1189 AvailableValue AV;
1190 if (AnalyzeLoadAvailability(Load, DepInfo, Address, AV)) {
1191 // subtlety: because we know this was a non-local dependency, we know
1192 // it's safe to materialize anywhere between the instruction within
1193 // DepInfo and the end of it's block.
1194 ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
1195 std::move(AV)));
1196 } else {
1197 UnavailableBlocks.push_back(DepBB);
1198 }
1199 }
1200
1201 assert(NumDeps == ValuesPerBlock.size() + UnavailableBlocks.size() &&(static_cast <bool> (NumDeps == ValuesPerBlock.size() +
UnavailableBlocks.size() && "post condition violation"
) ? void (0) : __assert_fail ("NumDeps == ValuesPerBlock.size() + UnavailableBlocks.size() && \"post condition violation\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 1202, __extension__ __PRETTY_FUNCTION__
))
1202 "post condition violation")(static_cast <bool> (NumDeps == ValuesPerBlock.size() +
UnavailableBlocks.size() && "post condition violation"
) ? void (0) : __assert_fail ("NumDeps == ValuesPerBlock.size() + UnavailableBlocks.size() && \"post condition violation\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 1202, __extension__ __PRETTY_FUNCTION__
))
;
1203}
1204
1205void GVNPass::eliminatePartiallyRedundantLoad(
1206 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1207 MapVector<BasicBlock *, Value *> &AvailableLoads) {
1208 for (const auto &AvailableLoad : AvailableLoads) {
1209 BasicBlock *UnavailableBlock = AvailableLoad.first;
1210 Value *LoadPtr = AvailableLoad.second;
1211
1212 auto *NewLoad =
1213 new LoadInst(Load->getType(), LoadPtr, Load->getName() + ".pre",
1214 Load->isVolatile(), Load->getAlign(), Load->getOrdering(),
1215 Load->getSyncScopeID(), UnavailableBlock->getTerminator());
1216 NewLoad->setDebugLoc(Load->getDebugLoc());
1217 if (MSSAU) {
1218 auto *MSSA = MSSAU->getMemorySSA();
1219 // Get the defining access of the original load or use the load if it is a
1220 // MemoryDef (e.g. because it is volatile). The inserted loads are
1221 // guaranteed to load from the same definition.
1222 auto *LoadAcc = MSSA->getMemoryAccess(Load);
1223 auto *DefiningAcc =
1224 isa<MemoryDef>(LoadAcc) ? LoadAcc : LoadAcc->getDefiningAccess();
1225 auto *NewAccess = MSSAU->createMemoryAccessInBB(
1226 NewLoad, DefiningAcc, NewLoad->getParent(),
1227 MemorySSA::BeforeTerminator);
1228 if (auto *NewDef = dyn_cast<MemoryDef>(NewAccess))
1229 MSSAU->insertDef(NewDef, /*RenameUses=*/true);
1230 else
1231 MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);
1232 }
1233
1234 // Transfer the old load's AA tags to the new load.
1235 AAMDNodes Tags = Load->getAAMetadata();
1236 if (Tags)
1237 NewLoad->setAAMetadata(Tags);
1238
1239 if (auto *MD = Load->getMetadata(LLVMContext::MD_invariant_load))
1240 NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
1241 if (auto *InvGroupMD = Load->getMetadata(LLVMContext::MD_invariant_group))
1242 NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
1243 if (auto *RangeMD = Load->getMetadata(LLVMContext::MD_range))
1244 NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
1245 if (auto *AccessMD = Load->getMetadata(LLVMContext::MD_access_group))
1246 if (LI &&
1247 LI->getLoopFor(Load->getParent()) == LI->getLoopFor(UnavailableBlock))
1248 NewLoad->setMetadata(LLVMContext::MD_access_group, AccessMD);
1249
1250 // We do not propagate the old load's debug location, because the new
1251 // load now lives in a different BB, and we want to avoid a jumpy line
1252 // table.
1253 // FIXME: How do we retain source locations without causing poor debugging
1254 // behavior?
1255
1256 // Add the newly created load.
1257 ValuesPerBlock.push_back(
1258 AvailableValueInBlock::get(UnavailableBlock, NewLoad));
1259 MD->invalidateCachedPointerInfo(LoadPtr);
1260 LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN INSERTED " << *NewLoad <<
'\n'; } } while (false)
;
1261 }
1262
1263 // Perform PHI construction.
1264 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
1265 Load->replaceAllUsesWith(V);
1266 if (isa<PHINode>(V))
1267 V->takeName(Load);
1268 if (Instruction *I = dyn_cast<Instruction>(V))
1269 I->setDebugLoc(Load->getDebugLoc());
1270 if (V->getType()->isPtrOrPtrVectorTy())
1271 MD->invalidateCachedPointerInfo(V);
1272 markInstructionForDeletion(Load);
1273 ORE->emit([&]() {
1274 return OptimizationRemark(DEBUG_TYPE"gvn", "LoadPRE", Load)
1275 << "load eliminated by PRE";
1276 });
1277}
1278
1279bool GVNPass::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1280 UnavailBlkVect &UnavailableBlocks) {
1281 // Okay, we have *some* definitions of the value. This means that the value
1282 // is available in some of our (transitive) predecessors. Lets think about
1283 // doing PRE of this load. This will involve inserting a new load into the
1284 // predecessor when it's not available. We could do this in general, but
1285 // prefer to not increase code size. As such, we only do this when we know
1286 // that we only have to insert *one* load (which means we're basically moving
1287 // the load, not inserting a new one).
1288
1289 SmallPtrSet<BasicBlock *, 4> Blockers(UnavailableBlocks.begin(),
1290 UnavailableBlocks.end());
1291
1292 // Let's find the first basic block with more than one predecessor. Walk
1293 // backwards through predecessors if needed.
1294 BasicBlock *LoadBB = Load->getParent();
1295 BasicBlock *TmpBB = LoadBB;
1296
1297 // Check that there is no implicit control flow instructions above our load in
1298 // its block. If there is an instruction that doesn't always pass the
1299 // execution to the following instruction, then moving through it may become
1300 // invalid. For example:
1301 //
1302 // int arr[LEN];
1303 // int index = ???;
1304 // ...
1305 // guard(0 <= index && index < LEN);
1306 // use(arr[index]);
1307 //
1308 // It is illegal to move the array access to any point above the guard,
1309 // because if the index is out of bounds we should deoptimize rather than
1310 // access the array.
1311 // Check that there is no guard in this block above our instruction.
1312 bool MustEnsureSafetyOfSpeculativeExecution =
1313 ICF->isDominatedByICFIFromSameBlock(Load);
1314
1315 while (TmpBB->getSinglePredecessor()) {
1316 TmpBB = TmpBB->getSinglePredecessor();
1317 if (TmpBB == LoadBB) // Infinite (unreachable) loop.
1318 return false;
1319 if (Blockers.count(TmpBB))
1320 return false;
1321
1322 // If any of these blocks has more than one successor (i.e. if the edge we
1323 // just traversed was critical), then there are other paths through this
1324 // block along which the load may not be anticipated. Hoisting the load
1325 // above this block would be adding the load to execution paths along
1326 // which it was not previously executed.
1327 if (TmpBB->getTerminator()->getNumSuccessors() != 1)
1328 return false;
1329
1330 // Check that there is no implicit control flow in a block above.
1331 MustEnsureSafetyOfSpeculativeExecution =
1332 MustEnsureSafetyOfSpeculativeExecution || ICF->hasICF(TmpBB);
1333 }
1334
1335 assert(TmpBB)(static_cast <bool> (TmpBB) ? void (0) : __assert_fail (
"TmpBB", "llvm/lib/Transforms/Scalar/GVN.cpp", 1335, __extension__
__PRETTY_FUNCTION__))
;
1336 LoadBB = TmpBB;
1337
1338 // Check to see how many predecessors have the loaded value fully
1339 // available.
1340 MapVector<BasicBlock *, Value *> PredLoads;
1341 DenseMap<BasicBlock *, AvailabilityState> FullyAvailableBlocks;
1342 for (const AvailableValueInBlock &AV : ValuesPerBlock)
1343 FullyAvailableBlocks[AV.BB] = AvailabilityState::Available;
1344 for (BasicBlock *UnavailableBB : UnavailableBlocks)
1345 FullyAvailableBlocks[UnavailableBB] = AvailabilityState::Unavailable;
1346
1347 SmallVector<BasicBlock *, 4> CriticalEdgePred;
1348 for (BasicBlock *Pred : predecessors(LoadBB)) {
1349 // If any predecessor block is an EH pad that does not allow non-PHI
1350 // instructions before the terminator, we can't PRE the load.
1351 if (Pred->getTerminator()->isEHPad()) {
1352 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1353 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1354 << Pred->getName() << "': " << *Load << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
;
1355 return false;
1356 }
1357
1358 if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks)) {
1359 continue;
1360 }
1361
1362 if (Pred->getTerminator()->getNumSuccessors() != 1) {
1363 if (isa<IndirectBrInst>(Pred->getTerminator())) {
1364 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1365 dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1366 << Pred->getName() << "': " << *Load << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
;
1367 return false;
1368 }
1369
1370 // FIXME: Can we support the fallthrough edge?
1371 if (isa<CallBrInst>(Pred->getTerminator())) {
1372 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF CALLBR CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1373 dbgs() << "COULD NOT PRE LOAD BECAUSE OF CALLBR CRITICAL EDGE '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF CALLBR CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1374 << Pred->getName() << "': " << *Load << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF CALLBR CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
;
1375 return false;
1376 }
1377
1378 if (LoadBB->isEHPad()) {
1379 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1380 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1381 << Pred->getName() << "': " << *Load << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
;
1382 return false;
1383 }
1384
1385 // Do not split backedge as it will break the canonical loop form.
1386 if (!isLoadPRESplitBackedgeEnabled())
1387 if (DT->dominates(LoadBB, Pred)) {
1388 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1389 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1390 << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
1391 << Pred->getName() << "': " << *Load << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
<< Pred->getName() << "': " << *Load <<
'\n'; } } while (false)
;
1392 return false;
1393 }
1394
1395 CriticalEdgePred.push_back(Pred);
1396 } else {
1397 // Only add the predecessors that will not be split for now.
1398 PredLoads[Pred] = nullptr;
1399 }
1400 }
1401
1402 // Decide whether PRE is profitable for this load.
1403 unsigned NumUnavailablePreds = PredLoads.size() + CriticalEdgePred.size();
1404 assert(NumUnavailablePreds != 0 &&(static_cast <bool> (NumUnavailablePreds != 0 &&
"Fully available value should already be eliminated!") ? void
(0) : __assert_fail ("NumUnavailablePreds != 0 && \"Fully available value should already be eliminated!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 1405, __extension__ __PRETTY_FUNCTION__
))
1405 "Fully available value should already be eliminated!")(static_cast <bool> (NumUnavailablePreds != 0 &&
"Fully available value should already be eliminated!") ? void
(0) : __assert_fail ("NumUnavailablePreds != 0 && \"Fully available value should already be eliminated!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 1405, __extension__ __PRETTY_FUNCTION__
))
;
1406
1407 // If this load is unavailable in multiple predecessors, reject it.
1408 // FIXME: If we could restructure the CFG, we could make a common pred with
1409 // all the preds that don't have an available Load and insert a new load into
1410 // that one block.
1411 if (NumUnavailablePreds != 1)
1412 return false;
1413
1414 // Now we know where we will insert load. We must ensure that it is safe
1415 // to speculatively execute the load at that points.
1416 if (MustEnsureSafetyOfSpeculativeExecution) {
1417 if (CriticalEdgePred.size())
1418 if (!isSafeToSpeculativelyExecute(Load, LoadBB->getFirstNonPHI(), DT))
1419 return false;
1420 for (auto &PL : PredLoads)
1421 if (!isSafeToSpeculativelyExecute(Load, PL.first->getTerminator(), DT))
1422 return false;
1423 }
1424
1425 // Split critical edges, and update the unavailable predecessors accordingly.
1426 for (BasicBlock *OrigPred : CriticalEdgePred) {
1427 BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
1428 assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!")(static_cast <bool> (!PredLoads.count(OrigPred) &&
"Split edges shouldn't be in map!") ? void (0) : __assert_fail
("!PredLoads.count(OrigPred) && \"Split edges shouldn't be in map!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 1428, __extension__ __PRETTY_FUNCTION__
))
;
1429 PredLoads[NewPred] = nullptr;
1430 LLVM_DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "Split critical edge " << OrigPred
->getName() << "->" << LoadBB->getName()
<< '\n'; } } while (false)
1431 << LoadBB->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "Split critical edge " << OrigPred
->getName() << "->" << LoadBB->getName()
<< '\n'; } } while (false)
;
1432 }
1433
1434 // Check if the load can safely be moved to all the unavailable predecessors.
1435 bool CanDoPRE = true;
1436 const DataLayout &DL = Load->getModule()->getDataLayout();
1437 SmallVector<Instruction*, 8> NewInsts;
1438 for (auto &PredLoad : PredLoads) {
1439 BasicBlock *UnavailablePred = PredLoad.first;
1440
1441 // Do PHI translation to get its value in the predecessor if necessary. The
1442 // returned pointer (if non-null) is guaranteed to dominate UnavailablePred.
1443 // We do the translation for each edge we skipped by going from Load's block
1444 // to LoadBB, otherwise we might miss pieces needing translation.
1445
1446 // If all preds have a single successor, then we know it is safe to insert
1447 // the load on the pred (?!?), so we can insert code to materialize the
1448 // pointer if it is not available.
1449 Value *LoadPtr = Load->getPointerOperand();
1450 BasicBlock *Cur = Load->getParent();
1451 while (Cur != LoadBB) {
1452 PHITransAddr Address(LoadPtr, DL, AC);
1453 LoadPtr = Address.PHITranslateWithInsertion(
1454 Cur, Cur->getSinglePredecessor(), *DT, NewInsts);
1455 if (!LoadPtr) {
1456 CanDoPRE = false;
1457 break;
1458 }
1459 Cur = Cur->getSinglePredecessor();
1460 }
1461
1462 if (LoadPtr) {
1463 PHITransAddr Address(LoadPtr, DL, AC);
1464 LoadPtr = Address.PHITranslateWithInsertion(LoadBB, UnavailablePred, *DT,
1465 NewInsts);
1466 }
1467 // If we couldn't find or insert a computation of this phi translated value,
1468 // we fail PRE.
1469 if (!LoadPtr) {
1470 LLVM_DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
<< *Load->getPointerOperand() << "\n"; } } while
(false)
1471 << *Load->getPointerOperand() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
<< *Load->getPointerOperand() << "\n"; } } while
(false)
;
1472 CanDoPRE = false;
1473 break;
1474 }
1475
1476 PredLoad.second = LoadPtr;
1477 }
1478
1479 if (!CanDoPRE) {
1480 while (!NewInsts.empty()) {
1481 // Erase instructions generated by the failed PHI translation before
1482 // trying to number them. PHI translation might insert instructions
1483 // in basic blocks other than the current one, and we delete them
1484 // directly, as markInstructionForDeletion only allows removing from the
1485 // current basic block.
1486 NewInsts.pop_back_val()->eraseFromParent();
1487 }
1488 // HINT: Don't revert the edge-splitting as following transformation may
1489 // also need to split these critical edges.
1490 return !CriticalEdgePred.empty();
1491 }
1492
1493 // Okay, we can eliminate this load by inserting a reload in the predecessor
1494 // and using PHI construction to get the value in the other predecessors, do
1495 // it.
1496 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *Load << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN REMOVING PRE LOAD: " <<
*Load << '\n'; } } while (false)
;
1497 LLVM_DEBUG(if (!NewInsts.empty()) dbgs() << "INSERTED " << NewInsts.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { if (!NewInsts.empty()) dbgs() << "INSERTED "
<< NewInsts.size() << " INSTS: " << *NewInsts
.back() << '\n'; } } while (false)
1498 << " INSTS: " << *NewInsts.back()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { if (!NewInsts.empty()) dbgs() << "INSERTED "
<< NewInsts.size() << " INSTS: " << *NewInsts
.back() << '\n'; } } while (false)
1499 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { if (!NewInsts.empty()) dbgs() << "INSERTED "
<< NewInsts.size() << " INSTS: " << *NewInsts
.back() << '\n'; } } while (false)
;
1500
1501 // Assign value numbers to the new instructions.
1502 for (Instruction *I : NewInsts) {
1503 // Instructions that have been inserted in predecessor(s) to materialize
1504 // the load address do not retain their original debug locations. Doing
1505 // so could lead to confusing (but correct) source attributions.
1506 I->updateLocationAfterHoist();
1507
1508 // FIXME: We really _ought_ to insert these value numbers into their
1509 // parent's availability map. However, in doing so, we risk getting into
1510 // ordering issues. If a block hasn't been processed yet, we would be
1511 // marking a value as AVAIL-IN, which isn't what we intend.
1512 VN.lookupOrAdd(I);
1513 }
1514
1515 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads);
1516 ++NumPRELoad;
1517 return true;
1518}
1519
1520bool GVNPass::performLoopLoadPRE(LoadInst *Load,
1521 AvailValInBlkVect &ValuesPerBlock,
1522 UnavailBlkVect &UnavailableBlocks) {
1523 if (!LI)
1524 return false;
1525
1526 const Loop *L = LI->getLoopFor(Load->getParent());
1527 // TODO: Generalize to other loop blocks that dominate the latch.
1528 if (!L || L->getHeader() != Load->getParent())
1529 return false;
1530
1531 BasicBlock *Preheader = L->getLoopPreheader();
1532 BasicBlock *Latch = L->getLoopLatch();
1533 if (!Preheader || !Latch)
1534 return false;
1535
1536 Value *LoadPtr = Load->getPointerOperand();
1537 // Must be available in preheader.
1538 if (!L->isLoopInvariant(LoadPtr))
1539 return false;
1540
1541 // We plan to hoist the load to preheader without introducing a new fault.
1542 // In order to do it, we need to prove that we cannot side-exit the loop
1543 // once loop header is first entered before execution of the load.
1544 if (ICF->isDominatedByICFIFromSameBlock(Load))
1545 return false;
1546
1547 BasicBlock *LoopBlock = nullptr;
1548 for (auto *Blocker : UnavailableBlocks) {
1549 // Blockers from outside the loop are handled in preheader.
1550 if (!L->contains(Blocker))
1551 continue;
1552
1553 // Only allow one loop block. Loop header is not less frequently executed
1554 // than each loop block, and likely it is much more frequently executed. But
1555 // in case of multiple loop blocks, we need extra information (such as block
1556 // frequency info) to understand whether it is profitable to PRE into
1557 // multiple loop blocks.
1558 if (LoopBlock)
1559 return false;
1560
1561 // Do not sink into inner loops. This may be non-profitable.
1562 if (L != LI->getLoopFor(Blocker))
1563 return false;
1564
1565 // Blocks that dominate the latch execute on every single iteration, maybe
1566 // except the last one. So PREing into these blocks doesn't make much sense
1567 // in most cases. But the blocks that do not necessarily execute on each
1568 // iteration are sometimes much colder than the header, and this is when
1569 // PRE is potentially profitable.
1570 if (DT->dominates(Blocker, Latch))
1571 return false;
1572
1573 // Make sure that the terminator itself doesn't clobber.
1574 if (Blocker->getTerminator()->mayWriteToMemory())
1575 return false;
1576
1577 LoopBlock = Blocker;
1578 }
1579
1580 if (!LoopBlock)
1581 return false;
1582
1583 // Make sure the memory at this pointer cannot be freed, therefore we can
1584 // safely reload from it after clobber.
1585 if (LoadPtr->canBeFreed())
1586 return false;
1587
1588 // TODO: Support critical edge splitting if blocker has more than 1 successor.
1589 MapVector<BasicBlock *, Value *> AvailableLoads;
1590 AvailableLoads[LoopBlock] = LoadPtr;
1591 AvailableLoads[Preheader] = LoadPtr;
1592
1593 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOOP LOAD: " << *Load << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN REMOVING PRE LOOP LOAD: " <<
*Load << '\n'; } } while (false)
;
1594 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads);
1595 ++NumPRELoopLoad;
1596 return true;
1597}
1598
1599static void reportLoadElim(LoadInst *Load, Value *AvailableValue,
1600 OptimizationRemarkEmitter *ORE) {
1601 using namespace ore;
1602
1603 ORE->emit([&]() {
1604 return OptimizationRemark(DEBUG_TYPE"gvn", "LoadElim", Load)
1605 << "load of type " << NV("Type", Load->getType()) << " eliminated"
1606 << setExtraArgs() << " in favor of "
1607 << NV("InfavorOfValue", AvailableValue);
1608 });
1609}
1610
1611/// Attempt to eliminate a load whose dependencies are
1612/// non-local by performing PHI construction.
1613bool GVNPass::processNonLocalLoad(LoadInst *Load) {
1614 // non-local speculations are not allowed under asan.
1615 if (Load->getParent()->getParent()->hasFnAttribute(
1616 Attribute::SanitizeAddress) ||
1617 Load->getParent()->getParent()->hasFnAttribute(
1618 Attribute::SanitizeHWAddress))
1619 return false;
1620
1621 // Step 1: Find the non-local dependencies of the load.
1622 LoadDepVect Deps;
1623 MD->getNonLocalPointerDependency(Load, Deps);
1624
1625 // If we had to process more than one hundred blocks to find the
1626 // dependencies, this load isn't worth worrying about. Optimizing
1627 // it will be too expensive.
1628 unsigned NumDeps = Deps.size();
1629 if (NumDeps > MaxNumDeps)
1630 return false;
1631
1632 // If we had a phi translation failure, we'll have a single entry which is a
1633 // clobber in the current block. Reject this early.
1634 if (NumDeps == 1 &&
1635 !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {
1636 LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: non-local load "; Load->printAsOperand
(dbgs()); dbgs() << " has unknown dependencies\n";; } }
while (false)
1637 dbgs() << " has unknown dependencies\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: non-local load "; Load->printAsOperand
(dbgs()); dbgs() << " has unknown dependencies\n";; } }
while (false)
;
1638 return false;
1639 }
1640
1641 bool Changed = false;
1642 // If this load follows a GEP, see if we can PRE the indices before analyzing.
1643 if (GetElementPtrInst *GEP =
1644 dyn_cast<GetElementPtrInst>(Load->getOperand(0))) {
1645 for (Use &U : GEP->indices())
1646 if (Instruction *I = dyn_cast<Instruction>(U.get()))
1647 Changed |= performScalarPRE(I);
1648 }
1649
1650 // Step 2: Analyze the availability of the load
1651 AvailValInBlkVect ValuesPerBlock;
1652 UnavailBlkVect UnavailableBlocks;
1653 AnalyzeLoadAvailability(Load, Deps, ValuesPerBlock, UnavailableBlocks);
1654
1655 // If we have no predecessors that produce a known value for this load, exit
1656 // early.
1657 if (ValuesPerBlock.empty())
1658 return Changed;
1659
1660 // Step 3: Eliminate fully redundancy.
1661 //
1662 // If all of the instructions we depend on produce a known value for this
1663 // load, then it is fully redundant and we can use PHI insertion to compute
1664 // its value. Insert PHIs and remove the fully redundant value now.
1665 if (UnavailableBlocks.empty()) {
1666 LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *Load << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN REMOVING NONLOCAL LOAD: " <<
*Load << '\n'; } } while (false)
;
1667
1668 // Perform PHI construction.
1669 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
1670 Load->replaceAllUsesWith(V);
1671
1672 if (isa<PHINode>(V))
1673 V->takeName(Load);
1674 if (Instruction *I = dyn_cast<Instruction>(V))
1675 // If instruction I has debug info, then we should not update it.
1676 // Also, if I has a null DebugLoc, then it is still potentially incorrect
1677 // to propagate Load's DebugLoc because Load may not post-dominate I.
1678 if (Load->getDebugLoc() && Load->getParent() == I->getParent())
1679 I->setDebugLoc(Load->getDebugLoc());
1680 if (V->getType()->isPtrOrPtrVectorTy())
1681 MD->invalidateCachedPointerInfo(V);
1682 markInstructionForDeletion(Load);
1683 ++NumGVNLoad;
1684 reportLoadElim(Load, V, ORE);
1685 return true;
1686 }
1687
1688 // Step 4: Eliminate partial redundancy.
1689 if (!isPREEnabled() || !isLoadPREEnabled())
1690 return Changed;
1691 if (!isLoadInLoopPREEnabled() && LI && LI->getLoopFor(Load->getParent()))
1692 return Changed;
1693
1694 if (performLoopLoadPRE(Load, ValuesPerBlock, UnavailableBlocks) ||
1695 PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks))
1696 return true;
1697
1698 return Changed;
1699}
1700
1701static bool impliesEquivalanceIfTrue(CmpInst* Cmp) {
1702 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_EQ)
1703 return true;
1704
1705 // Floating point comparisons can be equal, but not equivalent. Cases:
1706 // NaNs for unordered operators
1707 // +0.0 vs 0.0 for all operators
1708 if (Cmp->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
1709 (Cmp->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
1710 Cmp->getFastMathFlags().noNaNs())) {
1711 Value *LHS = Cmp->getOperand(0);
1712 Value *RHS = Cmp->getOperand(1);
1713 // If we can prove either side non-zero, then equality must imply
1714 // equivalence.
1715 // FIXME: We should do this optimization if 'no signed zeros' is
1716 // applicable via an instruction-level fast-math-flag or some other
1717 // indicator that relaxed FP semantics are being used.
1718 if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1719 return true;
1720 if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1721 return true;;
1722 // TODO: Handle vector floating point constants
1723 }
1724 return false;
1725}
1726
1727static bool impliesEquivalanceIfFalse(CmpInst* Cmp) {
1728 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_NE)
1729 return true;
1730
1731 // Floating point comparisons can be equal, but not equivelent. Cases:
1732 // NaNs for unordered operators
1733 // +0.0 vs 0.0 for all operators
1734 if ((Cmp->getPredicate() == CmpInst::Predicate::FCMP_ONE &&
1735 Cmp->getFastMathFlags().noNaNs()) ||
1736 Cmp->getPredicate() == CmpInst::Predicate::FCMP_UNE) {
1737 Value *LHS = Cmp->getOperand(0);
1738 Value *RHS = Cmp->getOperand(1);
1739 // If we can prove either side non-zero, then equality must imply
1740 // equivalence.
1741 // FIXME: We should do this optimization if 'no signed zeros' is
1742 // applicable via an instruction-level fast-math-flag or some other
1743 // indicator that relaxed FP semantics are being used.
1744 if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1745 return true;
1746 if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1747 return true;;
1748 // TODO: Handle vector floating point constants
1749 }
1750 return false;
1751}
1752
1753
1754static bool hasUsersIn(Value *V, BasicBlock *BB) {
1755 for (User *U : V->users())
1756 if (isa<Instruction>(U) &&
1757 cast<Instruction>(U)->getParent() == BB)
1758 return true;
1759 return false;
1760}
1761
1762bool GVNPass::processAssumeIntrinsic(AssumeInst *IntrinsicI) {
1763 Value *V = IntrinsicI->getArgOperand(0);
1764
1765 if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
1766 if (Cond->isZero()) {
1767 Type *Int8Ty = Type::getInt8Ty(V->getContext());
1768 // Insert a new store to null instruction before the load to indicate that
1769 // this code is not reachable. FIXME: We could insert unreachable
1770 // instruction directly because we can modify the CFG.
1771 auto *NewS = new StoreInst(PoisonValue::get(Int8Ty),
1772 Constant::getNullValue(Int8Ty->getPointerTo()),
1773 IntrinsicI);
1774 if (MSSAU) {
1775 const MemoryUseOrDef *FirstNonDom = nullptr;
1776 const auto *AL =
1777 MSSAU->getMemorySSA()->getBlockAccesses(IntrinsicI->getParent());
1778
1779 // If there are accesses in the current basic block, find the first one
1780 // that does not come before NewS. The new memory access is inserted
1781 // after the found access or before the terminator if no such access is
1782 // found.
1783 if (AL) {
1784 for (auto &Acc : *AL) {
1785 if (auto *Current = dyn_cast<MemoryUseOrDef>(&Acc))
1786 if (!Current->getMemoryInst()->comesBefore(NewS)) {
1787 FirstNonDom = Current;
1788 break;
1789 }
1790 }
1791 }
1792
1793 // This added store is to null, so it will never executed and we can
1794 // just use the LiveOnEntry def as defining access.
1795 auto *NewDef =
1796 FirstNonDom ? MSSAU->createMemoryAccessBefore(
1797 NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
1798 const_cast<MemoryUseOrDef *>(FirstNonDom))
1799 : MSSAU->createMemoryAccessInBB(
1800 NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
1801 NewS->getParent(), MemorySSA::BeforeTerminator);
1802
1803 MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/false);
1804 }
1805 }
1806 if (isAssumeWithEmptyBundle(*IntrinsicI))
1807 markInstructionForDeletion(IntrinsicI);
1808 return false;
1809 } else if (isa<Constant>(V)) {
1810 // If it's not false, and constant, it must evaluate to true. This means our
1811 // assume is assume(true), and thus, pointless, and we don't want to do
1812 // anything more here.
1813 return false;
1814 }
1815
1816 Constant *True = ConstantInt::getTrue(V->getContext());
1817 bool Changed = false;
1818
1819 for (BasicBlock *Successor : successors(IntrinsicI->getParent())) {
1820 BasicBlockEdge Edge(IntrinsicI->getParent(), Successor);
1821
1822 // This property is only true in dominated successors, propagateEquality
1823 // will check dominance for us.
1824 Changed |= propagateEquality(V, True, Edge, false);
1825 }
1826
1827 // We can replace assume value with true, which covers cases like this:
1828 // call void @llvm.assume(i1 %cmp)
1829 // br i1 %cmp, label %bb1, label %bb2 ; will change %cmp to true
1830 ReplaceOperandsWithMap[V] = True;
1831
1832 // Similarly, after assume(!NotV) we know that NotV == false.
1833 Value *NotV;
1834 if (match(V, m_Not(m_Value(NotV))))
1835 ReplaceOperandsWithMap[NotV] = ConstantInt::getFalse(V->getContext());
1836
1837 // If we find an equality fact, canonicalize all dominated uses in this block
1838 // to one of the two values. We heuristically choice the "oldest" of the
1839 // two where age is determined by value number. (Note that propagateEquality
1840 // above handles the cross block case.)
1841 //
1842 // Key case to cover are:
1843 // 1)
1844 // %cmp = fcmp oeq float 3.000000e+00, %0 ; const on lhs could happen
1845 // call void @llvm.assume(i1 %cmp)
1846 // ret float %0 ; will change it to ret float 3.000000e+00
1847 // 2)
1848 // %load = load float, float* %addr
1849 // %cmp = fcmp oeq float %load, %0
1850 // call void @llvm.assume(i1 %cmp)
1851 // ret float %load ; will change it to ret float %0
1852 if (auto *CmpI = dyn_cast<CmpInst>(V)) {
1853 if (impliesEquivalanceIfTrue(CmpI)) {
1854 Value *CmpLHS = CmpI->getOperand(0);
1855 Value *CmpRHS = CmpI->getOperand(1);
1856 // Heuristically pick the better replacement -- the choice of heuristic
1857 // isn't terribly important here, but the fact we canonicalize on some
1858 // replacement is for exposing other simplifications.
1859 // TODO: pull this out as a helper function and reuse w/existing
1860 // (slightly different) logic.
1861 if (isa<Constant>(CmpLHS) && !isa<Constant>(CmpRHS))
1862 std::swap(CmpLHS, CmpRHS);
1863 if (!isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))
1864 std::swap(CmpLHS, CmpRHS);
1865 if ((isa<Argument>(CmpLHS) && isa<Argument>(CmpRHS)) ||
1866 (isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))) {
1867 // Move the 'oldest' value to the right-hand side, using the value
1868 // number as a proxy for age.
1869 uint32_t LVN = VN.lookupOrAdd(CmpLHS);
1870 uint32_t RVN = VN.lookupOrAdd(CmpRHS);
1871 if (LVN < RVN)
1872 std::swap(CmpLHS, CmpRHS);
1873 }
1874
1875 // Handle degenerate case where we either haven't pruned a dead path or a
1876 // removed a trivial assume yet.
1877 if (isa<Constant>(CmpLHS) && isa<Constant>(CmpRHS))
1878 return Changed;
1879
1880 LLVM_DEBUG(dbgs() << "Replacing dominated uses of "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "Replacing dominated uses of " <<
*CmpLHS << " with " << *CmpRHS << " in block "
<< IntrinsicI->getParent()->getName() << "\n"
; } } while (false)
1881 << *CmpLHS << " with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "Replacing dominated uses of " <<
*CmpLHS << " with " << *CmpRHS << " in block "
<< IntrinsicI->getParent()->getName() << "\n"
; } } while (false)
1882 << *CmpRHS << " in block "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "Replacing dominated uses of " <<
*CmpLHS << " with " << *CmpRHS << " in block "
<< IntrinsicI->getParent()->getName() << "\n"
; } } while (false)
1883 << IntrinsicI->getParent()->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "Replacing dominated uses of " <<
*CmpLHS << " with " << *CmpRHS << " in block "
<< IntrinsicI->getParent()->getName() << "\n"
; } } while (false)
;
1884
1885
1886 // Setup the replacement map - this handles uses within the same block
1887 if (hasUsersIn(CmpLHS, IntrinsicI->getParent()))
1888 ReplaceOperandsWithMap[CmpLHS] = CmpRHS;
1889
1890 // NOTE: The non-block local cases are handled by the call to
1891 // propagateEquality above; this block is just about handling the block
1892 // local cases. TODO: There's a bunch of logic in propagateEqualiy which
1893 // isn't duplicated for the block local case, can we share it somehow?
1894 }
1895 }
1896 return Changed;
1897}
1898
1899static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
1900 patchReplacementInstruction(I, Repl);
1901 I->replaceAllUsesWith(Repl);
1902}
1903
1904/// Attempt to eliminate a load, first by eliminating it
1905/// locally, and then attempting non-local elimination if that fails.
1906bool GVNPass::processLoad(LoadInst *L) {
1907 if (!MD)
1908 return false;
1909
1910 // This code hasn't been audited for ordered or volatile memory access
1911 if (!L->isUnordered())
1912 return false;
1913
1914 if (L->use_empty()) {
1915 markInstructionForDeletion(L);
1916 return true;
1917 }
1918
1919 // ... to a pointer that has been loaded from before...
1920 MemDepResult Dep = MD->getDependency(L);
1921
1922 // If it is defined in another block, try harder.
1923 if (Dep.isNonLocal())
1924 return processNonLocalLoad(L);
1925
1926 // Only handle the local case below
1927 if (!Dep.isDef() && !Dep.isClobber()) {
1928 // This might be a NonFuncLocal or an Unknown
1929 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; L->printAsOperand
(dbgs()); dbgs() << " has unknown dependence\n";; } } while
(false)
1930 // fast print dep, using operator<< on instruction is too slow.do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; L->printAsOperand
(dbgs()); dbgs() << " has unknown dependence\n";; } } while
(false)
1931 dbgs() << "GVN: load "; L->printAsOperand(dbgs());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; L->printAsOperand
(dbgs()); dbgs() << " has unknown dependence\n";; } } while
(false)
1932 dbgs() << " has unknown dependence\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; L->printAsOperand
(dbgs()); dbgs() << " has unknown dependence\n";; } } while
(false)
;
1933 return false;
1934 }
1935
1936 AvailableValue AV;
1937 if (AnalyzeLoadAvailability(L, Dep, L->getPointerOperand(), AV)) {
1938 Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this);
1939
1940 // Replace the load!
1941 patchAndReplaceAllUsesWith(L, AvailableValue);
1942 markInstructionForDeletion(L);
1943 if (MSSAU)
1944 MSSAU->removeMemoryAccess(L);
1945 ++NumGVNLoad;
1946 reportLoadElim(L, AvailableValue, ORE);
1947 // Tell MDA to reexamine the reused pointer since we might have more
1948 // information after forwarding it.
1949 if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
1950 MD->invalidateCachedPointerInfo(AvailableValue);
1951 return true;
1952 }
1953
1954 return false;
1955}
1956
1957/// Return a pair the first field showing the value number of \p Exp and the
1958/// second field showing whether it is a value number newly created.
1959std::pair<uint32_t, bool>
1960GVNPass::ValueTable::assignExpNewValueNum(Expression &Exp) {
1961 uint32_t &e = expressionNumbering[Exp];
1962 bool CreateNewValNum = !e;
1963 if (CreateNewValNum) {
1964 Expressions.push_back(Exp);
1965 if (ExprIdx.size() < nextValueNumber + 1)
1966 ExprIdx.resize(nextValueNumber * 2);
1967 e = nextValueNumber;
1968 ExprIdx[nextValueNumber++] = nextExprNumber++;
1969 }
1970 return {e, CreateNewValNum};
1971}
1972
1973/// Return whether all the values related with the same \p num are
1974/// defined in \p BB.
1975bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB,
1976 GVNPass &Gvn) {
1977 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
1978 while (Vals && Vals->BB == BB)
1979 Vals = Vals->Next;
1980 return !Vals;
1981}
1982
1983/// Wrap phiTranslateImpl to provide caching functionality.
1984uint32_t GVNPass::ValueTable::phiTranslate(const BasicBlock *Pred,
1985 const BasicBlock *PhiBlock,
1986 uint32_t Num, GVNPass &Gvn) {
1987 auto FindRes = PhiTranslateTable.find({Num, Pred});
1988 if (FindRes != PhiTranslateTable.end())
1989 return FindRes->second;
1990 uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, Gvn);
1991 PhiTranslateTable.insert({{Num, Pred}, NewNum});
1992 return NewNum;
1993}
1994
1995// Return true if the value number \p Num and NewNum have equal value.
1996// Return false if the result is unknown.
1997bool GVNPass::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
1998 const BasicBlock *Pred,
1999 const BasicBlock *PhiBlock,
2000 GVNPass &Gvn) {
2001 CallInst *Call = nullptr;
2002 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
2003 while (Vals) {
2004 Call = dyn_cast<CallInst>(Vals->Val);
2005 if (Call && Call->getParent() == PhiBlock)
2006 break;
2007 Vals = Vals->Next;
2008 }
2009
2010 if (AA->doesNotAccessMemory(Call))
2011 return true;
2012
2013 if (!MD || !AA->onlyReadsMemory(Call))
2014 return false;
2015
2016 MemDepResult local_dep = MD->getDependency(Call);
2017 if (!local_dep.isNonLocal())
2018 return false;
2019
2020 const MemoryDependenceResults::NonLocalDepInfo &deps =
2021 MD->getNonLocalCallDependency(Call);
2022
2023 // Check to see if the Call has no function local clobber.
2024 for (const NonLocalDepEntry &D : deps) {
2025 if (D.getResult().isNonFuncLocal())
2026 return true;
2027 }
2028 return false;
2029}
2030
2031/// Translate value number \p Num using phis, so that it has the values of
2032/// the phis in BB.
2033uint32_t GVNPass::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
2034 const BasicBlock *PhiBlock,
2035 uint32_t Num, GVNPass &Gvn) {
2036 if (PHINode *PN = NumberingPhi[Num]) {
2037 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
2038 if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred)
2039 if (uint32_t TransVal = lookup(PN->getIncomingValue(i), false))
2040 return TransVal;
2041 }
2042 return Num;
2043 }
2044
2045 // If there is any value related with Num is defined in a BB other than
2046 // PhiBlock, it cannot depend on a phi in PhiBlock without going through
2047 // a backedge. We can do an early exit in that case to save compile time.
2048 if (!areAllValsInBB(Num, PhiBlock, Gvn))
2049 return Num;
2050
2051 if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
2052 return Num;
2053 Expression Exp = Expressions[ExprIdx[Num]];
2054
2055 for (unsigned i = 0; i < Exp.varargs.size(); i++) {
2056 // For InsertValue and ExtractValue, some varargs are index numbers
2057 // instead of value numbers. Those index numbers should not be
2058 // translated.
2059 if ((i > 1 && Exp.opcode == Instruction::InsertValue) ||
2060 (i > 0 && Exp.opcode == Instruction::ExtractValue) ||
2061 (i > 1 && Exp.opcode == Instruction::ShuffleVector))
2062 continue;
2063 Exp.varargs[i] = phiTranslate(Pred, PhiBlock, Exp.varargs[i], Gvn);
2064 }
2065
2066 if (Exp.commutative) {
2067 assert(Exp.varargs.size() >= 2 && "Unsupported commutative instruction!")(static_cast <bool> (Exp.varargs.size() >= 2 &&
"Unsupported commutative instruction!") ? void (0) : __assert_fail
("Exp.varargs.size() >= 2 && \"Unsupported commutative instruction!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2067, __extension__ __PRETTY_FUNCTION__
))
;
2068 if (Exp.varargs[0] > Exp.varargs[1]) {
2069 std::swap(Exp.varargs[0], Exp.varargs[1]);
2070 uint32_t Opcode = Exp.opcode >> 8;
2071 if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
2072 Exp.opcode = (Opcode << 8) |
2073 CmpInst::getSwappedPredicate(
2074 static_cast<CmpInst::Predicate>(Exp.opcode & 255));
2075 }
2076 }
2077
2078 if (uint32_t NewNum = expressionNumbering[Exp]) {
2079 if (Exp.opcode == Instruction::Call && NewNum != Num)
2080 return areCallValsEqual(Num, NewNum, Pred, PhiBlock, Gvn) ? NewNum : Num;
2081 return NewNum;
2082 }
2083 return Num;
2084}
2085
2086/// Erase stale entry from phiTranslate cache so phiTranslate can be computed
2087/// again.
2088void GVNPass::ValueTable::eraseTranslateCacheEntry(
2089 uint32_t Num, const BasicBlock &CurrBlock) {
2090 for (const BasicBlock *Pred : predecessors(&CurrBlock))
2091 PhiTranslateTable.erase({Num, Pred});
2092}
2093
2094// In order to find a leader for a given value number at a
2095// specific basic block, we first obtain the list of all Values for that number,
2096// and then scan the list to find one whose block dominates the block in
2097// question. This is fast because dominator tree queries consist of only
2098// a few comparisons of DFS numbers.
2099Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t num) {
2100 LeaderTableEntry Vals = LeaderTable[num];
2101 if (!Vals.Val) return nullptr;
2102
2103 Value *Val = nullptr;
2104 if (DT->dominates(Vals.BB, BB)) {
2105 Val = Vals.Val;
2106 if (isa<Constant>(Val)) return Val;
2107 }
2108
2109 LeaderTableEntry* Next = Vals.Next;
2110 while (Next) {
2111 if (DT->dominates(Next->BB, BB)) {
2112 if (isa<Constant>(Next->Val)) return Next->Val;
2113 if (!Val) Val = Next->Val;
2114 }
2115
2116 Next = Next->Next;
2117 }
2118
2119 return Val;
2120}
2121
2122/// There is an edge from 'Src' to 'Dst'. Return
2123/// true if every path from the entry block to 'Dst' passes via this edge. In
2124/// particular 'Dst' must not be reachable via another edge from 'Src'.
2125static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E,
2126 DominatorTree *DT) {
2127 // While in theory it is interesting to consider the case in which Dst has
2128 // more than one predecessor, because Dst might be part of a loop which is
2129 // only reachable from Src, in practice it is pointless since at the time
2130 // GVN runs all such loops have preheaders, which means that Dst will have
2131 // been changed to have only one predecessor, namely Src.
2132 const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
2133 assert((!Pred || Pred == E.getStart()) &&(static_cast <bool> ((!Pred || Pred == E.getStart()) &&
"No edge between these basic blocks!") ? void (0) : __assert_fail
("(!Pred || Pred == E.getStart()) && \"No edge between these basic blocks!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2134, __extension__ __PRETTY_FUNCTION__
))
2134 "No edge between these basic blocks!")(static_cast <bool> ((!Pred || Pred == E.getStart()) &&
"No edge between these basic blocks!") ? void (0) : __assert_fail
("(!Pred || Pred == E.getStart()) && \"No edge between these basic blocks!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2134, __extension__ __PRETTY_FUNCTION__
))
;
2135 return Pred != nullptr;
2136}
2137
2138void GVNPass::assignBlockRPONumber(Function &F) {
2139 BlockRPONumber.clear();
2140 uint32_t NextBlockNumber = 1;
2141 ReversePostOrderTraversal<Function *> RPOT(&F);
2142 for (BasicBlock *BB : RPOT)
2143 BlockRPONumber[BB] = NextBlockNumber++;
2144 InvalidBlockRPONumbers = false;
2145}
2146
2147bool GVNPass::replaceOperandsForInBlockEquality(Instruction *Instr) const {
2148 bool Changed = false;
2149 for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
2150 Value *Operand = Instr->getOperand(OpNum);
2151 auto it = ReplaceOperandsWithMap.find(Operand);
2152 if (it != ReplaceOperandsWithMap.end()) {
2153 LLVM_DEBUG(dbgs() << "GVN replacing: " << *Operand << " with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN replacing: " << *Operand
<< " with " << *it->second << " in instruction "
<< *Instr << '\n'; } } while (false)
2154 << *it->second << " in instruction " << *Instr << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN replacing: " << *Operand
<< " with " << *it->second << " in instruction "
<< *Instr << '\n'; } } while (false)
;
2155 Instr->setOperand(OpNum, it->second);
2156 Changed = true;
2157 }
2158 }
2159 return Changed;
2160}
2161
2162/// The given values are known to be equal in every block
2163/// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with
2164/// 'RHS' everywhere in the scope. Returns whether a change was made.
2165/// If DominatesByEdge is false, then it means that we will propagate the RHS
2166/// value starting from the end of Root.Start.
2167bool GVNPass::propagateEquality(Value *LHS, Value *RHS,
2168 const BasicBlockEdge &Root,
2169 bool DominatesByEdge) {
2170 SmallVector<std::pair<Value*, Value*>, 4> Worklist;
2171 Worklist.push_back(std::make_pair(LHS, RHS));
2172 bool Changed = false;
2173 // For speed, compute a conservative fast approximation to
2174 // DT->dominates(Root, Root.getEnd());
2175 const bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);
2176
2177 while (!Worklist.empty()) {
2178 std::pair<Value*, Value*> Item = Worklist.pop_back_val();
2179 LHS = Item.first; RHS = Item.second;
2180
2181 if (LHS == RHS)
2182 continue;
2183 assert(LHS->getType() == RHS->getType() && "Equality but unequal types!")(static_cast <bool> (LHS->getType() == RHS->getType
() && "Equality but unequal types!") ? void (0) : __assert_fail
("LHS->getType() == RHS->getType() && \"Equality but unequal types!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2183, __extension__ __PRETTY_FUNCTION__
))
;
2184
2185 // Don't try to propagate equalities between constants.
2186 if (isa<Constant>(LHS) && isa<Constant>(RHS))
2187 continue;
2188
2189 // Prefer a constant on the right-hand side, or an Argument if no constants.
2190 if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
2191 std::swap(LHS, RHS);
2192 assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!")(static_cast <bool> ((isa<Argument>(LHS) || isa<
Instruction>(LHS)) && "Unexpected value!") ? void (
0) : __assert_fail ("(isa<Argument>(LHS) || isa<Instruction>(LHS)) && \"Unexpected value!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2192, __extension__ __PRETTY_FUNCTION__
))
;
2193
2194 // If there is no obvious reason to prefer the left-hand side over the
2195 // right-hand side, ensure the longest lived term is on the right-hand side,
2196 // so the shortest lived term will be replaced by the longest lived.
2197 // This tends to expose more simplifications.
2198 uint32_t LVN = VN.lookupOrAdd(LHS);
2199 if ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||
2200 (isa<Instruction>(LHS) && isa<Instruction>(RHS))) {
2201 // Move the 'oldest' value to the right-hand side, using the value number
2202 // as a proxy for age.
2203 uint32_t RVN = VN.lookupOrAdd(RHS);
2204 if (LVN < RVN) {
2205 std::swap(LHS, RHS);
2206 LVN = RVN;
2207 }
2208 }
2209
2210 // If value numbering later sees that an instruction in the scope is equal
2211 // to 'LHS' then ensure it will be turned into 'RHS'. In order to preserve
2212 // the invariant that instructions only occur in the leader table for their
2213 // own value number (this is used by removeFromLeaderTable), do not do this
2214 // if RHS is an instruction (if an instruction in the scope is morphed into
2215 // LHS then it will be turned into RHS by the next GVN iteration anyway, so
2216 // using the leader table is about compiling faster, not optimizing better).
2217 // The leader table only tracks basic blocks, not edges. Only add to if we
2218 // have the simple case where the edge dominates the end.
2219 if (RootDominatesEnd && !isa<Instruction>(RHS))
2220 addToLeaderTable(LVN, RHS, Root.getEnd());
2221
2222 // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope. As
2223 // LHS always has at least one use that is not dominated by Root, this will
2224 // never do anything if LHS has only one use.
2225 if (!LHS->hasOneUse()) {
2226 unsigned NumReplacements =
2227 DominatesByEdge
2228 ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
2229 : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());
2230
2231 Changed |= NumReplacements > 0;
2232 NumGVNEqProp += NumReplacements;
2233 // Cached information for anything that uses LHS will be invalid.
2234 if (MD)
2235 MD->invalidateCachedPointerInfo(LHS);
2236 }
2237
2238 // Now try to deduce additional equalities from this one. For example, if
2239 // the known equality was "(A != B)" == "false" then it follows that A and B
2240 // are equal in the scope. Only boolean equalities with an explicit true or
2241 // false RHS are currently supported.
2242 if (!RHS->getType()->isIntegerTy(1))
2243 // Not a boolean equality - bail out.
2244 continue;
2245 ConstantInt *CI = dyn_cast<ConstantInt>(RHS);
2246 if (!CI)
2247 // RHS neither 'true' nor 'false' - bail out.
2248 continue;
2249 // Whether RHS equals 'true'. Otherwise it equals 'false'.
2250 bool isKnownTrue = CI->isMinusOne();
2251 bool isKnownFalse = !isKnownTrue;
2252
2253 // If "A && B" is known true then both A and B are known true. If "A || B"
2254 // is known false then both A and B are known false.
2255 Value *A, *B;
2256 if ((isKnownTrue && match(LHS, m_LogicalAnd(m_Value(A), m_Value(B)))) ||
2257 (isKnownFalse && match(LHS, m_LogicalOr(m_Value(A), m_Value(B))))) {
2258 Worklist.push_back(std::make_pair(A, RHS));
2259 Worklist.push_back(std::make_pair(B, RHS));
2260 continue;
2261 }
2262
2263 // If we are propagating an equality like "(A == B)" == "true" then also
2264 // propagate the equality A == B. When propagating a comparison such as
2265 // "(A >= B)" == "true", replace all instances of "A < B" with "false".
2266 if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
2267 Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1);
2268
2269 // If "A == B" is known true, or "A != B" is known false, then replace
2270 // A with B everywhere in the scope. For floating point operations, we
2271 // have to be careful since equality does not always imply equivalance.
2272 if ((isKnownTrue && impliesEquivalanceIfTrue(Cmp)) ||
2273 (isKnownFalse && impliesEquivalanceIfFalse(Cmp)))
2274 Worklist.push_back(std::make_pair(Op0, Op1));
2275
2276 // If "A >= B" is known true, replace "A < B" with false everywhere.
2277 CmpInst::Predicate NotPred = Cmp->getInversePredicate();
2278 Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse);
2279 // Since we don't have the instruction "A < B" immediately to hand, work
2280 // out the value number that it would have and use that to find an
2281 // appropriate instruction (if any).
2282 uint32_t NextNum = VN.getNextUnusedValueNumber();
2283 uint32_t Num = VN.lookupOrAddCmp(Cmp->getOpcode(), NotPred, Op0, Op1);
2284 // If the number we were assigned was brand new then there is no point in
2285 // looking for an instruction realizing it: there cannot be one!
2286 if (Num < NextNum) {
2287 Value *NotCmp = findLeader(Root.getEnd(), Num);
2288 if (NotCmp && isa<Instruction>(NotCmp)) {
2289 unsigned NumReplacements =
2290 DominatesByEdge
2291 ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
2292 : replaceDominatedUsesWith(NotCmp, NotVal, *DT,
2293 Root.getStart());
2294 Changed |= NumReplacements > 0;
2295 NumGVNEqProp += NumReplacements;
2296 // Cached information for anything that uses NotCmp will be invalid.
2297 if (MD)
2298 MD->invalidateCachedPointerInfo(NotCmp);
2299 }
2300 }
2301 // Ensure that any instruction in scope that gets the "A < B" value number
2302 // is replaced with false.
2303 // The leader table only tracks basic blocks, not edges. Only add to if we
2304 // have the simple case where the edge dominates the end.
2305 if (RootDominatesEnd)
2306 addToLeaderTable(Num, NotVal, Root.getEnd());
2307
2308 continue;
2309 }
2310 }
2311
2312 return Changed;
2313}
2314
2315/// When calculating availability, handle an instruction
2316/// by inserting it into the appropriate sets
2317bool GVNPass::processInstruction(Instruction *I) {
2318 // Ignore dbg info intrinsics.
2319 if (isa<DbgInfoIntrinsic>(I))
2320 return false;
2321
2322 // If the instruction can be easily simplified then do so now in preference
2323 // to value numbering it. Value numbering often exposes redundancies, for
2324 // example if it determines that %y is equal to %x then the instruction
2325 // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
2326 const DataLayout &DL = I->getModule()->getDataLayout();
2327 if (Value *V = SimplifyInstruction(I, {DL, TLI, DT, AC})) {
2328 bool Changed = false;
2329 if (!I->use_empty()) {
2330 // Simplification can cause a special instruction to become not special.
2331 // For example, devirtualization to a willreturn function.
2332 ICF->removeUsersOf(I);
2333 I->replaceAllUsesWith(V);
2334 Changed = true;
2335 }
2336 if (isInstructionTriviallyDead(I, TLI)) {
2337 markInstructionForDeletion(I);
2338 Changed = true;
2339 }
2340 if (Changed) {
2341 if (MD && V->getType()->isPtrOrPtrVectorTy())
2342 MD->invalidateCachedPointerInfo(V);
2343 ++NumGVNSimpl;
2344 return true;
2345 }
2346 }
2347
2348 if (auto *Assume = dyn_cast<AssumeInst>(I))
2349 return processAssumeIntrinsic(Assume);
2350
2351 if (LoadInst *Load = dyn_cast<LoadInst>(I)) {
2352 if (processLoad(Load))
2353 return true;
2354
2355 unsigned Num = VN.lookupOrAdd(Load);
2356 addToLeaderTable(Num, Load, Load->getParent());
2357 return false;
2358 }
2359
2360 // For conditional branches, we can perform simple conditional propagation on
2361 // the condition value itself.
2362 if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
2363 if (!BI->isConditional())
2364 return false;
2365
2366 if (isa<Constant>(BI->getCondition()))
2367 return processFoldableCondBr(BI);
2368
2369 Value *BranchCond = BI->getCondition();
2370 BasicBlock *TrueSucc = BI->getSuccessor(0);
2371 BasicBlock *FalseSucc = BI->getSuccessor(1);
2372 // Avoid multiple edges early.
2373 if (TrueSucc == FalseSucc)
2374 return false;
2375
2376 BasicBlock *Parent = BI->getParent();
2377 bool Changed = false;
2378
2379 Value *TrueVal = ConstantInt::getTrue(TrueSucc->getContext());
2380 BasicBlockEdge TrueE(Parent, TrueSucc);
2381 Changed |= propagateEquality(BranchCond, TrueVal, TrueE, true);
2382
2383 Value *FalseVal = ConstantInt::getFalse(FalseSucc->getContext());
2384 BasicBlockEdge FalseE(Parent, FalseSucc);
2385 Changed |= propagateEquality(BranchCond, FalseVal, FalseE, true);
2386
2387 return Changed;
2388 }
2389
2390 // For switches, propagate the case values into the case destinations.
2391 if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
2392 Value *SwitchCond = SI->getCondition();
2393 BasicBlock *Parent = SI->getParent();
2394 bool Changed = false;
2395
2396 // Remember how many outgoing edges there are to every successor.
2397 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
2398 for (unsigned i = 0, n = SI->getNumSuccessors(); i != n; ++i)
2399 ++SwitchEdges[SI->getSuccessor(i)];
2400
2401 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
2402 i != e; ++i) {
2403 BasicBlock *Dst = i->getCaseSuccessor();
2404 // If there is only a single edge, propagate the case value into it.
2405 if (SwitchEdges.lookup(Dst) == 1) {
2406 BasicBlockEdge E(Parent, Dst);
2407 Changed |= propagateEquality(SwitchCond, i->getCaseValue(), E, true);
2408 }
2409 }
2410 return Changed;
2411 }
2412
2413 // Instructions with void type don't return a value, so there's
2414 // no point in trying to find redundancies in them.
2415 if (I->getType()->isVoidTy())
2416 return false;
2417
2418 uint32_t NextNum = VN.getNextUnusedValueNumber();
2419 unsigned Num = VN.lookupOrAdd(I);
2420
2421 // Allocations are always uniquely numbered, so we can save time and memory
2422 // by fast failing them.
2423 if (isa<AllocaInst>(I) || I->isTerminator() || isa<PHINode>(I)) {
2424 addToLeaderTable(Num, I, I->getParent());
2425 return false;
2426 }
2427
2428 // If the number we were assigned was a brand new VN, then we don't
2429 // need to do a lookup to see if the number already exists
2430 // somewhere in the domtree: it can't!
2431 if (Num >= NextNum) {
2432 addToLeaderTable(Num, I, I->getParent());
2433 return false;
2434 }
2435
2436 // Perform fast-path value-number based elimination of values inherited from
2437 // dominators.
2438 Value *Repl = findLeader(I->getParent(), Num);
2439 if (!Repl) {
2440 // Failure, just remember this instance for future use.
2441 addToLeaderTable(Num, I, I->getParent());
2442 return false;
2443 } else if (Repl == I) {
2444 // If I was the result of a shortcut PRE, it might already be in the table
2445 // and the best replacement for itself. Nothing to do.
2446 return false;
2447 }
2448
2449 // Remove it!
2450 patchAndReplaceAllUsesWith(I, Repl);
2451 if (MD && Repl->getType()->isPtrOrPtrVectorTy())
2452 MD->invalidateCachedPointerInfo(Repl);
2453 markInstructionForDeletion(I);
2454 return true;
2455}
2456
2457/// runOnFunction - This is the main transformation entry point for a function.
2458bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
2459 const TargetLibraryInfo &RunTLI, AAResults &RunAA,
2460 MemoryDependenceResults *RunMD, LoopInfo *LI,
2461 OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {
2462 AC = &RunAC;
2463 DT = &RunDT;
2464 VN.setDomTree(DT);
2465 TLI = &RunTLI;
2466 VN.setAliasAnalysis(&RunAA);
2467 MD = RunMD;
2468 ImplicitControlFlowTracking ImplicitCFT;
2469 ICF = &ImplicitCFT;
2470 this->LI = LI;
2471 VN.setMemDep(MD);
2472 ORE = RunORE;
2473 InvalidBlockRPONumbers = true;
2474 MemorySSAUpdater Updater(MSSA);
2475 MSSAU = MSSA ? &Updater : nullptr;
2476
2477 bool Changed = false;
2478 bool ShouldContinue = true;
2479
2480 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
2481 // Merge unconditional branches, allowing PRE to catch more
2482 // optimization opportunities.
2483 for (BasicBlock &BB : llvm::make_early_inc_range(F)) {
2484 bool removedBlock = MergeBlockIntoPredecessor(&BB, &DTU, LI, MSSAU, MD);
2485 if (removedBlock)
2486 ++NumGVNBlocks;
2487
2488 Changed |= removedBlock;
2489 }
2490
2491 unsigned Iteration = 0;
2492 while (ShouldContinue) {
2493 LLVM_DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN iteration: " << Iteration
<< "\n"; } } while (false)
;
2494 ShouldContinue = iterateOnFunction(F);
2495 Changed |= ShouldContinue;
2496 ++Iteration;
2497 }
2498
2499 if (isPREEnabled()) {
2500 // Fabricate val-num for dead-code in order to suppress assertion in
2501 // performPRE().
2502 assignValNumForDeadCode();
2503 bool PREChanged = true;
2504 while (PREChanged) {
2505 PREChanged = performPRE(F);
2506 Changed |= PREChanged;
2507 }
2508 }
2509
2510 // FIXME: Should perform GVN again after PRE does something. PRE can move
2511 // computations into blocks where they become fully redundant. Note that
2512 // we can't do this until PRE's critical edge splitting updates memdep.
2513 // Actually, when this happens, we should just fully integrate PRE into GVN.
2514
2515 cleanupGlobalSets();
2516 // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
2517 // iteration.
2518 DeadBlocks.clear();
2519
2520 if (MSSA && VerifyMemorySSA)
2521 MSSA->verifyMemorySSA();
2522
2523 return Changed;
2524}
2525
2526bool GVNPass::processBlock(BasicBlock *BB) {
2527 // FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
2528 // (and incrementing BI before processing an instruction).
2529 assert(InstrsToErase.empty() &&(static_cast <bool> (InstrsToErase.empty() && "We expect InstrsToErase to be empty across iterations"
) ? void (0) : __assert_fail ("InstrsToErase.empty() && \"We expect InstrsToErase to be empty across iterations\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2530, __extension__ __PRETTY_FUNCTION__
))
2530 "We expect InstrsToErase to be empty across iterations")(static_cast <bool> (InstrsToErase.empty() && "We expect InstrsToErase to be empty across iterations"
) ? void (0) : __assert_fail ("InstrsToErase.empty() && \"We expect InstrsToErase to be empty across iterations\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2530, __extension__ __PRETTY_FUNCTION__
))
;
2531 if (DeadBlocks.count(BB))
2532 return false;
2533
2534 // Clearing map before every BB because it can be used only for single BB.
2535 ReplaceOperandsWithMap.clear();
2536 bool ChangedFunction = false;
2537
2538 // Since we may not have visited the input blocks of the phis, we can't
2539 // use our normal hash approach for phis. Instead, simply look for
2540 // obvious duplicates. The first pass of GVN will tend to create
2541 // identical phis, and the second or later passes can eliminate them.
2542 ChangedFunction |= EliminateDuplicatePHINodes(BB);
2543
2544 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
2545 BI != BE;) {
2546 if (!ReplaceOperandsWithMap.empty())
2547 ChangedFunction |= replaceOperandsForInBlockEquality(&*BI);
2548 ChangedFunction |= processInstruction(&*BI);
2549
2550 if (InstrsToErase.empty()) {
2551 ++BI;
2552 continue;
2553 }
2554
2555 // If we need some instructions deleted, do it now.
2556 NumGVNInstr += InstrsToErase.size();
2557
2558 // Avoid iterator invalidation.
2559 bool AtStart = BI == BB->begin();
2560 if (!AtStart)
2561 --BI;
2562
2563 for (auto *I : InstrsToErase) {
2564 assert(I->getParent() == BB && "Removing instruction from wrong block?")(static_cast <bool> (I->getParent() == BB &&
"Removing instruction from wrong block?") ? void (0) : __assert_fail
("I->getParent() == BB && \"Removing instruction from wrong block?\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2564, __extension__ __PRETTY_FUNCTION__
))
;
2565 LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN removed: " << *I <<
'\n'; } } while (false)
;
2566 salvageKnowledge(I, AC);
2567 salvageDebugInfo(*I);
2568 if (MD) MD->removeInstruction(I);
2569 if (MSSAU)
2570 MSSAU->removeMemoryAccess(I);
2571 LLVM_DEBUG(verifyRemoved(I))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { verifyRemoved(I); } } while (false)
;
2572 ICF->removeInstruction(I);
2573 I->eraseFromParent();
2574 }
2575 InstrsToErase.clear();
2576
2577 if (AtStart)
2578 BI = BB->begin();
2579 else
2580 ++BI;
2581 }
2582
2583 return ChangedFunction;
2584}
2585
2586// Instantiate an expression in a predecessor that lacked it.
2587bool GVNPass::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
2588 BasicBlock *Curr, unsigned int ValNo) {
2589 // Because we are going top-down through the block, all value numbers
2590 // will be available in the predecessor by the time we need them. Any
2591 // that weren't originally present will have been instantiated earlier
2592 // in this loop.
2593 bool success = true;
2594 for (unsigned i = 0, e = Instr->getNumOperands(); i != e; ++i) {
2595 Value *Op = Instr->getOperand(i);
2596 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
2597 continue;
2598 // This could be a newly inserted instruction, in which case, we won't
2599 // find a value number, and should give up before we hurt ourselves.
2600 // FIXME: Rewrite the infrastructure to let it easier to value number
2601 // and process newly inserted instructions.
2602 if (!VN.exists(Op)) {
2603 success = false;
2604 break;
2605 }
2606 uint32_t TValNo =
2607 VN.phiTranslate(Pred, Curr, VN.lookup(Op), *this);
2608 if (Value *V = findLeader(Pred, TValNo)) {
2609 Instr->setOperand(i, V);
2610 } else {
2611 success = false;
2612 break;
2613 }
2614 }
2615
2616 // Fail out if we encounter an operand that is not available in
2617 // the PRE predecessor. This is typically because of loads which
2618 // are not value numbered precisely.
2619 if (!success)
2620 return false;
2621
2622 Instr->insertBefore(Pred->getTerminator());
2623 Instr->setName(Instr->getName() + ".pre");
2624 Instr->setDebugLoc(Instr->getDebugLoc());
2625
2626 ICF->insertInstructionTo(Instr, Pred);
2627
2628 unsigned Num = VN.lookupOrAdd(Instr);
2629 VN.add(Instr, Num);
2630
2631 // Update the availability map to include the new instruction.
2632 addToLeaderTable(Num, Instr, Pred);
2633 return true;
2634}
2635
2636bool GVNPass::performScalarPRE(Instruction *CurInst) {
2637 if (isa<AllocaInst>(CurInst) || CurInst->isTerminator() ||
2638 isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() ||
2639 CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
2640 isa<DbgInfoIntrinsic>(CurInst))
2641 return false;
2642
2643 // Don't do PRE on compares. The PHI would prevent CodeGenPrepare from
2644 // sinking the compare again, and it would force the code generator to
2645 // move the i1 from processor flags or predicate registers into a general
2646 // purpose register.
2647 if (isa<CmpInst>(CurInst))
2648 return false;
2649
2650 // Don't do PRE on GEPs. The inserted PHI would prevent CodeGenPrepare from
2651 // sinking the addressing mode computation back to its uses. Extending the
2652 // GEP's live range increases the register pressure, and therefore it can
2653 // introduce unnecessary spills.
2654 //
2655 // This doesn't prevent Load PRE. PHI translation will make the GEP available
2656 // to the load by moving it to the predecessor block if necessary.
2657 if (isa<GetElementPtrInst>(CurInst))
2658 return false;
2659
2660 if (auto *CallB = dyn_cast<CallBase>(CurInst)) {
2661 // We don't currently value number ANY inline asm calls.
2662 if (CallB->isInlineAsm())
2663 return false;
2664 // Don't do PRE on convergent calls.
2665 if (CallB->isConvergent())
2666 return false;
2667 }
2668
2669 uint32_t ValNo = VN.lookup(CurInst);
2670
2671 // Look for the predecessors for PRE opportunities. We're
2672 // only trying to solve the basic diamond case, where
2673 // a value is computed in the successor and one predecessor,
2674 // but not the other. We also explicitly disallow cases
2675 // where the successor is its own predecessor, because they're
2676 // more complicated to get right.
2677 unsigned NumWith = 0;
2678 unsigned NumWithout = 0;
2679 BasicBlock *PREPred = nullptr;
2680 BasicBlock *CurrentBlock = CurInst->getParent();
2681
2682 // Update the RPO numbers for this function.
2683 if (InvalidBlockRPONumbers)
2684 assignBlockRPONumber(*CurrentBlock->getParent());
2685
2686 SmallVector<std::pair<Value *, BasicBlock *>, 8> predMap;
2687 for (BasicBlock *P : predecessors(CurrentBlock)) {
2688 // We're not interested in PRE where blocks with predecessors that are
2689 // not reachable.
2690 if (!DT->isReachableFromEntry(P)) {
2691 NumWithout = 2;
2692 break;
2693 }
2694 // It is not safe to do PRE when P->CurrentBlock is a loop backedge, and
2695 // when CurInst has operand defined in CurrentBlock (so it may be defined
2696 // by phi in the loop header).
2697 assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) &&(static_cast <bool> (BlockRPONumber.count(P) &&
BlockRPONumber.count(CurrentBlock) && "Invalid BlockRPONumber map."
) ? void (0) : __assert_fail ("BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) && \"Invalid BlockRPONumber map.\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2698, __extension__ __PRETTY_FUNCTION__
))
2698 "Invalid BlockRPONumber map.")(static_cast <bool> (BlockRPONumber.count(P) &&
BlockRPONumber.count(CurrentBlock) && "Invalid BlockRPONumber map."
) ? void (0) : __assert_fail ("BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) && \"Invalid BlockRPONumber map.\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2698, __extension__ __PRETTY_FUNCTION__
))
;
2699 if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock] &&
2700 llvm::any_of(CurInst->operands(), [&](const Use &U) {
2701 if (auto *Inst = dyn_cast<Instruction>(U.get()))
2702 return Inst->getParent() == CurrentBlock;
2703 return false;
2704 })) {
2705 NumWithout = 2;
2706 break;
2707 }
2708
2709 uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);
2710 Value *predV = findLeader(P, TValNo);
2711 if (!predV) {
2712 predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));
2713 PREPred = P;
2714 ++NumWithout;
2715 } else if (predV == CurInst) {
2716 /* CurInst dominates this predecessor. */
2717 NumWithout = 2;
2718 break;
2719 } else {
2720 predMap.push_back(std::make_pair(predV, P));
2721 ++NumWith;
2722 }
2723 }
2724
2725 // Don't do PRE when it might increase code size, i.e. when
2726 // we would need to insert instructions in more than one pred.
2727 if (NumWithout > 1 || NumWith == 0)
2728 return false;
2729
2730 // We may have a case where all predecessors have the instruction,
2731 // and we just need to insert a phi node. Otherwise, perform
2732 // insertion.
2733 Instruction *PREInstr = nullptr;
2734
2735 if (NumWithout != 0) {
2736 if (!isSafeToSpeculativelyExecute(CurInst)) {
2737 // It is only valid to insert a new instruction if the current instruction
2738 // is always executed. An instruction with implicit control flow could
2739 // prevent us from doing it. If we cannot speculate the execution, then
2740 // PRE should be prohibited.
2741 if (ICF->isDominatedByICFIFromSameBlock(CurInst))
2742 return false;
2743 }
2744
2745 // Don't do PRE across indirect branch.
2746 if (isa<IndirectBrInst>(PREPred->getTerminator()))
2747 return false;
2748
2749 // Don't do PRE across callbr.
2750 // FIXME: Can we do this across the fallthrough edge?
2751 if (isa<CallBrInst>(PREPred->getTerminator()))
2752 return false;
2753
2754 // We can't do PRE safely on a critical edge, so instead we schedule
2755 // the edge to be split and perform the PRE the next time we iterate
2756 // on the function.
2757 unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);
2758 if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
2759 toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
2760 return false;
2761 }
2762 // We need to insert somewhere, so let's give it a shot
2763 PREInstr = CurInst->clone();
2764 if (!performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo)) {
2765 // If we failed insertion, make sure we remove the instruction.
2766 LLVM_DEBUG(verifyRemoved(PREInstr))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { verifyRemoved(PREInstr); } } while (false)
;
2767 PREInstr->deleteValue();
2768 return false;
2769 }
2770 }
2771
2772 // Either we should have filled in the PRE instruction, or we should
2773 // not have needed insertions.
2774 assert(PREInstr != nullptr || NumWithout == 0)(static_cast <bool> (PREInstr != nullptr || NumWithout ==
0) ? void (0) : __assert_fail ("PREInstr != nullptr || NumWithout == 0"
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2774, __extension__ __PRETTY_FUNCTION__
))
;
2775
2776 ++NumGVNPRE;
2777
2778 // Create a PHI to make the value available in this block.
2779 PHINode *Phi =
2780 PHINode::Create(CurInst->getType(), predMap.size(),
2781 CurInst->getName() + ".pre-phi", &CurrentBlock->front());
2782 for (unsigned i = 0, e = predMap.size(); i != e; ++i) {
2783 if (Value *V = predMap[i].first) {
2784 // If we use an existing value in this phi, we have to patch the original
2785 // value because the phi will be used to replace a later value.
2786 patchReplacementInstruction(CurInst, V);
2787 Phi->addIncoming(V, predMap[i].second);
2788 } else
2789 Phi->addIncoming(PREInstr, PREPred);
2790 }
2791
2792 VN.add(Phi, ValNo);
2793 // After creating a new PHI for ValNo, the phi translate result for ValNo will
2794 // be changed, so erase the related stale entries in phi translate cache.
2795 VN.eraseTranslateCacheEntry(ValNo, *CurrentBlock);
2796 addToLeaderTable(ValNo, Phi, CurrentBlock);
2797 Phi->setDebugLoc(CurInst->getDebugLoc());
2798 CurInst->replaceAllUsesWith(Phi);
2799 if (MD && Phi->getType()->isPtrOrPtrVectorTy())
2800 MD->invalidateCachedPointerInfo(Phi);
2801 VN.erase(CurInst);
2802 removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
2803
2804 LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN PRE removed: " << *CurInst
<< '\n'; } } while (false)
;
2805 if (MD)
2806 MD->removeInstruction(CurInst);
2807 if (MSSAU)
2808 MSSAU->removeMemoryAccess(CurInst);
2809 LLVM_DEBUG(verifyRemoved(CurInst))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { verifyRemoved(CurInst); } } while (false)
;
2810 // FIXME: Intended to be markInstructionForDeletion(CurInst), but it causes
2811 // some assertion failures.
2812 ICF->removeInstruction(CurInst);
2813 CurInst->eraseFromParent();
2814 ++NumGVNInstr;
2815
2816 return true;
2817}
2818
2819/// Perform a purely local form of PRE that looks for diamond
2820/// control flow patterns and attempts to perform simple PRE at the join point.
2821bool GVNPass::performPRE(Function &F) {
2822 bool Changed = false;
2823 for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) {
2824 // Nothing to PRE in the entry block.
2825 if (CurrentBlock == &F.getEntryBlock())
2826 continue;
2827
2828 // Don't perform PRE on an EH pad.
2829 if (CurrentBlock->isEHPad())
2830 continue;
2831
2832 for (BasicBlock::iterator BI = CurrentBlock->begin(),
2833 BE = CurrentBlock->end();
2834 BI != BE;) {
2835 Instruction *CurInst = &*BI++;
2836 Changed |= performScalarPRE(CurInst);
2837 }
2838 }
2839
2840 if (splitCriticalEdges())
2841 Changed = true;
2842
2843 return Changed;
2844}
2845
2846/// Split the critical edge connecting the given two blocks, and return
2847/// the block inserted to the critical edge.
2848BasicBlock *GVNPass::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
2849 // GVN does not require loop-simplify, do not try to preserve it if it is not
2850 // possible.
2851 BasicBlock *BB = SplitCriticalEdge(
2852 Pred, Succ,
2853 CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());
2854 if (BB) {
2855 if (MD)
2856 MD->invalidateCachedPredecessors();
2857 InvalidBlockRPONumbers = true;
2858 }
2859 return BB;
2860}
2861
2862/// Split critical edges found during the previous
2863/// iteration that may enable further optimization.
2864bool GVNPass::splitCriticalEdges() {
2865 if (toSplit.empty())
2866 return false;
2867
2868 bool Changed = false;
2869 do {
2870 std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val();
2871 Changed |= SplitCriticalEdge(Edge.first, Edge.second,
2872 CriticalEdgeSplittingOptions(DT, LI, MSSAU)) !=
2873 nullptr;
2874 } while (!toSplit.empty());
2875 if (Changed) {
2876 if (MD)
2877 MD->invalidateCachedPredecessors();
2878 InvalidBlockRPONumbers = true;
2879 }
2880 return Changed;
2881}
2882
2883/// Executes one iteration of GVN
2884bool GVNPass::iterateOnFunction(Function &F) {
2885 cleanupGlobalSets();
2886
2887 // Top-down walk of the dominator tree
2888 bool Changed = false;
2889 // Needed for value numbering with phi construction to work.
2890 // RPOT walks the graph in its constructor and will not be invalidated during
2891 // processBlock.
2892 ReversePostOrderTraversal<Function *> RPOT(&F);
2893
2894 for (BasicBlock *BB : RPOT)
2895 Changed |= processBlock(BB);
2896
2897 return Changed;
2898}
2899
2900void GVNPass::cleanupGlobalSets() {
2901 VN.clear();
2902 LeaderTable.clear();
2903 BlockRPONumber.clear();
2904 TableAllocator.Reset();
2905 ICF->clear();
2906 InvalidBlockRPONumbers = true;
2907}
2908
2909/// Verify that the specified instruction does not occur in our
2910/// internal data structures.
2911void GVNPass::verifyRemoved(const Instruction *Inst) const {
2912 VN.verifyRemoved(Inst);
2913
2914 // Walk through the value number scope to make sure the instruction isn't
2915 // ferreted away in it.
2916 for (const auto &I : LeaderTable) {
2917 const LeaderTableEntry *Node = &I.second;
2918 assert(Node->Val != Inst && "Inst still in value numbering scope!")(static_cast <bool> (Node->Val != Inst && "Inst still in value numbering scope!"
) ? void (0) : __assert_fail ("Node->Val != Inst && \"Inst still in value numbering scope!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2918, __extension__ __PRETTY_FUNCTION__
))
;
2919
2920 while (Node->Next) {
2921 Node = Node->Next;
2922 assert(Node->Val != Inst && "Inst still in value numbering scope!")(static_cast <bool> (Node->Val != Inst && "Inst still in value numbering scope!"
) ? void (0) : __assert_fail ("Node->Val != Inst && \"Inst still in value numbering scope!\""
, "llvm/lib/Transforms/Scalar/GVN.cpp", 2922, __extension__ __PRETTY_FUNCTION__
))
;
2923 }
2924 }
2925}
2926
2927/// BB is declared dead, which implied other blocks become dead as well. This
2928/// function is to add all these blocks to "DeadBlocks". For the dead blocks'
2929/// live successors, update their phi nodes by replacing the operands
2930/// corresponding to dead blocks with UndefVal.
2931void GVNPass::addDeadBlock(BasicBlock *BB) {
2932 SmallVector<BasicBlock *, 4> NewDead;
2933 SmallSetVector<BasicBlock *, 4> DF;
2934
2935 NewDead.push_back(BB);
2936 while (!NewDead.empty()) {
2937 BasicBlock *D = NewDead.pop_back_val();
2938 if (DeadBlocks.count(D))
2939 continue;
2940
2941 // All blocks dominated by D are dead.
2942 SmallVector<BasicBlock *, 8> Dom;
2943 DT->getDescendants(D, Dom);
2944 DeadBlocks.insert(Dom.begin(), Dom.end());
2945
2946 // Figure out the dominance-frontier(D).
2947 for (BasicBlock *B : Dom) {
2948 for (BasicBlock *S : successors(B)) {
2949 if (DeadBlocks.count(S))
2950 continue;
2951
2952 bool AllPredDead = true;
2953 for (BasicBlock *P : predecessors(S))
2954 if (!DeadBlocks.count(P)) {
2955 AllPredDead = false;
2956 break;
2957 }
2958
2959 if (!AllPredDead) {
2960 // S could be proved dead later on. That is why we don't update phi
2961 // operands at this moment.
2962 DF.insert(S);
2963 } else {
2964 // While S is not dominated by D, it is dead by now. This could take
2965 // place if S already have a dead predecessor before D is declared
2966 // dead.
2967 NewDead.push_back(S);
2968 }
2969 }
2970 }
2971 }
2972
2973 // For the dead blocks' live successors, update their phi nodes by replacing
2974 // the operands corresponding to dead blocks with UndefVal.
2975 for (BasicBlock *B : DF) {
2976 if (DeadBlocks.count(B))
2977 continue;
2978
2979 // First, split the critical edges. This might also create additional blocks
2980 // to preserve LoopSimplify form and adjust edges accordingly.
2981 SmallVector<BasicBlock *, 4> Preds(predecessors(B));
2982 for (BasicBlock *P : Preds) {
2983 if (!DeadBlocks.count(P))
2984 continue;
2985
2986 if (llvm::is_contained(successors(P), B) &&
2987 isCriticalEdge(P->getTerminator(), B)) {
2988 if (BasicBlock *S = splitCriticalEdges(P, B))
2989 DeadBlocks.insert(P = S);
Although the value stored to 'P' is used in the enclosing expression, the value is never actually read from 'P'
2990 }
2991 }
2992
2993 // Now poison the incoming values from the dead predecessors.
2994 for (BasicBlock *P : predecessors(B)) {
2995 if (!DeadBlocks.count(P))
2996 continue;
2997 for (PHINode &Phi : B->phis()) {
2998 Phi.setIncomingValueForBlock(P, PoisonValue::get(Phi.getType()));
2999 if (MD)
3000 MD->invalidateCachedPointerInfo(&Phi);
3001 }
3002 }
3003 }
3004}
3005
3006// If the given branch is recognized as a foldable branch (i.e. conditional
3007// branch with constant condition), it will perform following analyses and
3008// transformation.
3009// 1) If the dead out-coming edge is a critical-edge, split it. Let
3010// R be the target of the dead out-coming edge.
3011// 1) Identify the set of dead blocks implied by the branch's dead outcoming
3012// edge. The result of this step will be {X| X is dominated by R}
3013// 2) Identify those blocks which haves at least one dead predecessor. The
3014// result of this step will be dominance-frontier(R).
3015// 3) Update the PHIs in DF(R) by replacing the operands corresponding to
3016// dead blocks with "UndefVal" in an hope these PHIs will optimized away.
3017//
3018// Return true iff *NEW* dead code are found.
3019bool GVNPass::processFoldableCondBr(BranchInst *BI) {
3020 if (!BI || BI->isUnconditional())
3021 return false;
3022
3023 // If a branch has two identical successors, we cannot declare either dead.
3024 if (BI->getSuccessor(0) == BI->getSuccessor(1))
3025 return false;
3026
3027 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
3028 if (!Cond)
3029 return false;
3030
3031 BasicBlock *DeadRoot =
3032 Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0);
3033 if (DeadBlocks.count(DeadRoot))
3034 return false;
3035
3036 if (!DeadRoot->getSinglePredecessor())
3037 DeadRoot = splitCriticalEdges(BI->getParent(), DeadRoot);
3038
3039 addDeadBlock(DeadRoot);
3040 return true;
3041}
3042
3043// performPRE() will trigger assert if it comes across an instruction without
3044// associated val-num. As it normally has far more live instructions than dead
3045// instructions, it makes more sense just to "fabricate" a val-number for the
3046// dead code than checking if instruction involved is dead or not.
3047void GVNPass::assignValNumForDeadCode() {
3048 for (BasicBlock *BB : DeadBlocks) {
3049 for (Instruction &Inst : *BB) {
3050 unsigned ValNum = VN.lookupOrAdd(&Inst);
3051 addToLeaderTable(ValNum, &Inst, BB);
3052 }
3053 }
3054}
3055
3056class llvm::gvn::GVNLegacyPass : public FunctionPass {
3057public:
3058 static char ID; // Pass identification, replacement for typeid
3059
3060 explicit GVNLegacyPass(bool NoMemDepAnalysis = !GVNEnableMemDep)
3061 : FunctionPass(ID), Impl(GVNOptions().setMemDep(!NoMemDepAnalysis)) {
3062 initializeGVNLegacyPassPass(*PassRegistry::getPassRegistry());
3063 }
3064
3065 bool runOnFunction(Function &F) override {
3066 if (skipFunction(F))
3067 return false;
3068
3069 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
3070
3071 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
3072 return Impl.runImpl(
3073 F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
3074 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
3075 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
3076 getAnalysis<AAResultsWrapperPass>().getAAResults(),
3077 Impl.isMemDepEnabled()
3078 ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()
3079 : nullptr,
3080 LIWP ? &LIWP->getLoopInfo() : nullptr,
3081 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),
3082 MSSAWP ? &MSSAWP->getMSSA() : nullptr);
3083 }
3084
3085 void getAnalysisUsage(AnalysisUsage &AU) const override {
3086 AU.addRequired<AssumptionCacheTracker>();
3087 AU.addRequired<DominatorTreeWrapperPass>();
3088 AU.addRequired<TargetLibraryInfoWrapperPass>();
3089 AU.addRequired<LoopInfoWrapperPass>();
3090 if (Impl.isMemDepEnabled())
3091 AU.addRequired<MemoryDependenceWrapperPass>();
3092 AU.addRequired<AAResultsWrapperPass>();
3093 AU.addPreserved<DominatorTreeWrapperPass>();
3094 AU.addPreserved<GlobalsAAWrapperPass>();
3095 AU.addPreserved<TargetLibraryInfoWrapperPass>();
3096 AU.addPreserved<LoopInfoWrapperPass>();
3097 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
3098 AU.addPreserved<MemorySSAWrapperPass>();
3099 }
3100
3101private:
3102 GVNPass Impl;
3103};
3104
3105char GVNLegacyPass::ID = 0;
3106
3107INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)static void *initializeGVNLegacyPassPassOnce(PassRegistry &
Registry) {
3108INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);
3109INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)initializeMemoryDependenceWrapperPassPass(Registry);
3110INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
3111INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
3112INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
3113INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
3114INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
3115INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)PassInfo *PI = new PassInfo( "Global Value Numbering", "gvn",
&GVNLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<GVNLegacyPass>), false, false); Registry.registerPass(
*PI, true); return PI; } static llvm::once_flag InitializeGVNLegacyPassPassFlag
; void llvm::initializeGVNLegacyPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeGVNLegacyPassPassFlag, initializeGVNLegacyPassPassOnce
, std::ref(Registry)); }
3116
3117// The public interface to this file...
3118FunctionPass *llvm::createGVNPass(bool NoMemDepAnalysis) {
3119 return new GVNLegacyPass(NoMemDepAnalysis);
3120}