Bug Summary

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