Bug Summary

File:llvm/lib/Transforms/Scalar/GVN.cpp
Warning:line 2971, 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-14~++20210828111110+16086d47c0d0/build-llvm/lib/Transforms/Scalar -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/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-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -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-14~++20210828111110+16086d47c0d0/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0=. -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-08-28-193554-24367-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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-14~++20210828111110+16086d47c0d0/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 if (performLoopLoadPRE(Load, ValuesPerBlock, UnavailableBlocks) ||
1677 PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks))
1678 return true;
1679
1680 return Changed;
1681}
1682
1683static bool impliesEquivalanceIfTrue(CmpInst* Cmp) {
1684 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_EQ)
1685 return true;
1686
1687 // Floating point comparisons can be equal, but not equivalent. Cases:
1688 // NaNs for unordered operators
1689 // +0.0 vs 0.0 for all operators
1690 if (Cmp->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
1691 (Cmp->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
1692 Cmp->getFastMathFlags().noNaNs())) {
1693 Value *LHS = Cmp->getOperand(0);
1694 Value *RHS = Cmp->getOperand(1);
1695 // If we can prove either side non-zero, then equality must imply
1696 // equivalence.
1697 // FIXME: We should do this optimization if 'no signed zeros' is
1698 // applicable via an instruction-level fast-math-flag or some other
1699 // indicator that relaxed FP semantics are being used.
1700 if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1701 return true;
1702 if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1703 return true;;
1704 // TODO: Handle vector floating point constants
1705 }
1706 return false;
1707}
1708
1709static bool impliesEquivalanceIfFalse(CmpInst* Cmp) {
1710 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_NE)
1711 return true;
1712
1713 // Floating point comparisons can be equal, but not equivelent. Cases:
1714 // NaNs for unordered operators
1715 // +0.0 vs 0.0 for all operators
1716 if ((Cmp->getPredicate() == CmpInst::Predicate::FCMP_ONE &&
1717 Cmp->getFastMathFlags().noNaNs()) ||
1718 Cmp->getPredicate() == CmpInst::Predicate::FCMP_UNE) {
1719 Value *LHS = Cmp->getOperand(0);
1720 Value *RHS = Cmp->getOperand(1);
1721 // If we can prove either side non-zero, then equality must imply
1722 // equivalence.
1723 // FIXME: We should do this optimization if 'no signed zeros' is
1724 // applicable via an instruction-level fast-math-flag or some other
1725 // indicator that relaxed FP semantics are being used.
1726 if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1727 return true;
1728 if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1729 return true;;
1730 // TODO: Handle vector floating point constants
1731 }
1732 return false;
1733}
1734
1735
1736static bool hasUsersIn(Value *V, BasicBlock *BB) {
1737 for (User *U : V->users())
1738 if (isa<Instruction>(U) &&
1739 cast<Instruction>(U)->getParent() == BB)
1740 return true;
1741 return false;
1742}
1743
1744bool GVN::processAssumeIntrinsic(AssumeInst *IntrinsicI) {
1745 Value *V = IntrinsicI->getArgOperand(0);
1746
1747 if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
1748 if (Cond->isZero()) {
1749 Type *Int8Ty = Type::getInt8Ty(V->getContext());
1750 // Insert a new store to null instruction before the load to indicate that
1751 // this code is not reachable. FIXME: We could insert unreachable
1752 // instruction directly because we can modify the CFG.
1753 auto *NewS = new StoreInst(UndefValue::get(Int8Ty),
1754 Constant::getNullValue(Int8Ty->getPointerTo()),
1755 IntrinsicI);
1756 if (MSSAU) {
1757 const MemoryUseOrDef *FirstNonDom = nullptr;
1758 const auto *AL =
1759 MSSAU->getMemorySSA()->getBlockAccesses(IntrinsicI->getParent());
1760
1761 // If there are accesses in the current basic block, find the first one
1762 // that does not come before NewS. The new memory access is inserted
1763 // after the found access or before the terminator if no such access is
1764 // found.
1765 if (AL) {
1766 for (auto &Acc : *AL) {
1767 if (auto *Current = dyn_cast<MemoryUseOrDef>(&Acc))
1768 if (!Current->getMemoryInst()->comesBefore(NewS)) {
1769 FirstNonDom = Current;
1770 break;
1771 }
1772 }
1773 }
1774
1775 // This added store is to null, so it will never executed and we can
1776 // just use the LiveOnEntry def as defining access.
1777 auto *NewDef =
1778 FirstNonDom ? MSSAU->createMemoryAccessBefore(
1779 NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
1780 const_cast<MemoryUseOrDef *>(FirstNonDom))
1781 : MSSAU->createMemoryAccessInBB(
1782 NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
1783 NewS->getParent(), MemorySSA::BeforeTerminator);
1784
1785 MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/false);
1786 }
1787 }
1788 if (isAssumeWithEmptyBundle(*IntrinsicI))
1789 markInstructionForDeletion(IntrinsicI);
1790 return false;
1791 } else if (isa<Constant>(V)) {
1792 // If it's not false, and constant, it must evaluate to true. This means our
1793 // assume is assume(true), and thus, pointless, and we don't want to do
1794 // anything more here.
1795 return false;
1796 }
1797
1798 Constant *True = ConstantInt::getTrue(V->getContext());
1799 bool Changed = false;
1800
1801 for (BasicBlock *Successor : successors(IntrinsicI->getParent())) {
1802 BasicBlockEdge Edge(IntrinsicI->getParent(), Successor);
1803
1804 // This property is only true in dominated successors, propagateEquality
1805 // will check dominance for us.
1806 Changed |= propagateEquality(V, True, Edge, false);
1807 }
1808
1809 // We can replace assume value with true, which covers cases like this:
1810 // call void @llvm.assume(i1 %cmp)
1811 // br i1 %cmp, label %bb1, label %bb2 ; will change %cmp to true
1812 ReplaceOperandsWithMap[V] = True;
1813
1814 // Similarly, after assume(!NotV) we know that NotV == false.
1815 Value *NotV;
1816 if (match(V, m_Not(m_Value(NotV))))
1817 ReplaceOperandsWithMap[NotV] = ConstantInt::getFalse(V->getContext());
1818
1819 // If we find an equality fact, canonicalize all dominated uses in this block
1820 // to one of the two values. We heuristically choice the "oldest" of the
1821 // two where age is determined by value number. (Note that propagateEquality
1822 // above handles the cross block case.)
1823 //
1824 // Key case to cover are:
1825 // 1)
1826 // %cmp = fcmp oeq float 3.000000e+00, %0 ; const on lhs could happen
1827 // call void @llvm.assume(i1 %cmp)
1828 // ret float %0 ; will change it to ret float 3.000000e+00
1829 // 2)
1830 // %load = load float, float* %addr
1831 // %cmp = fcmp oeq float %load, %0
1832 // call void @llvm.assume(i1 %cmp)
1833 // ret float %load ; will change it to ret float %0
1834 if (auto *CmpI = dyn_cast<CmpInst>(V)) {
1835 if (impliesEquivalanceIfTrue(CmpI)) {
1836 Value *CmpLHS = CmpI->getOperand(0);
1837 Value *CmpRHS = CmpI->getOperand(1);
1838 // Heuristically pick the better replacement -- the choice of heuristic
1839 // isn't terribly important here, but the fact we canonicalize on some
1840 // replacement is for exposing other simplifications.
1841 // TODO: pull this out as a helper function and reuse w/existing
1842 // (slightly different) logic.
1843 if (isa<Constant>(CmpLHS) && !isa<Constant>(CmpRHS))
1844 std::swap(CmpLHS, CmpRHS);
1845 if (!isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))
1846 std::swap(CmpLHS, CmpRHS);
1847 if ((isa<Argument>(CmpLHS) && isa<Argument>(CmpRHS)) ||
1848 (isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))) {
1849 // Move the 'oldest' value to the right-hand side, using the value
1850 // number as a proxy for age.
1851 uint32_t LVN = VN.lookupOrAdd(CmpLHS);
1852 uint32_t RVN = VN.lookupOrAdd(CmpRHS);
1853 if (LVN < RVN)
1854 std::swap(CmpLHS, CmpRHS);
1855 }
1856
1857 // Handle degenerate case where we either haven't pruned a dead path or a
1858 // removed a trivial assume yet.
1859 if (isa<Constant>(CmpLHS) && isa<Constant>(CmpRHS))
1860 return Changed;
1861
1862 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)
1863 << *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)
1864 << *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)
1865 << 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)
;
1866
1867
1868 // Setup the replacement map - this handles uses within the same block
1869 if (hasUsersIn(CmpLHS, IntrinsicI->getParent()))
1870 ReplaceOperandsWithMap[CmpLHS] = CmpRHS;
1871
1872 // NOTE: The non-block local cases are handled by the call to
1873 // propagateEquality above; this block is just about handling the block
1874 // local cases. TODO: There's a bunch of logic in propagateEqualiy which
1875 // isn't duplicated for the block local case, can we share it somehow?
1876 }
1877 }
1878 return Changed;
1879}
1880
1881static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
1882 patchReplacementInstruction(I, Repl);
1883 I->replaceAllUsesWith(Repl);
1884}
1885
1886/// Attempt to eliminate a load, first by eliminating it
1887/// locally, and then attempting non-local elimination if that fails.
1888bool GVN::processLoad(LoadInst *L) {
1889 if (!MD)
1890 return false;
1891
1892 // This code hasn't been audited for ordered or volatile memory access
1893 if (!L->isUnordered())
1894 return false;
1895
1896 if (L->use_empty()) {
1897 markInstructionForDeletion(L);
1898 return true;
1899 }
1900
1901 // ... to a pointer that has been loaded from before...
1902 MemDepResult Dep = MD->getDependency(L);
1903
1904 // If it is defined in another block, try harder.
1905 if (Dep.isNonLocal())
1906 return processNonLocalLoad(L);
1907
1908 // Only handle the local case below
1909 if (!Dep.isDef() && !Dep.isClobber()) {
1910 // This might be a NonFuncLocal or an Unknown
1911 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN: load "; L->printAsOperand
(dbgs()); dbgs() << " has unknown dependence\n";; } } while
(false)
1912 // 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)
1913 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)
1914 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)
;
1915 return false;
1916 }
1917
1918 AvailableValue AV;
1919 if (AnalyzeLoadAvailability(L, Dep, L->getPointerOperand(), AV)) {
1920 Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this);
1921
1922 // Replace the load!
1923 patchAndReplaceAllUsesWith(L, AvailableValue);
1924 markInstructionForDeletion(L);
1925 if (MSSAU)
1926 MSSAU->removeMemoryAccess(L);
1927 ++NumGVNLoad;
1928 reportLoadElim(L, AvailableValue, ORE);
1929 // Tell MDA to reexamine the reused pointer since we might have more
1930 // information after forwarding it.
1931 if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
1932 MD->invalidateCachedPointerInfo(AvailableValue);
1933 return true;
1934 }
1935
1936 return false;
1937}
1938
1939/// Return a pair the first field showing the value number of \p Exp and the
1940/// second field showing whether it is a value number newly created.
1941std::pair<uint32_t, bool>
1942GVN::ValueTable::assignExpNewValueNum(Expression &Exp) {
1943 uint32_t &e = expressionNumbering[Exp];
1944 bool CreateNewValNum = !e;
1945 if (CreateNewValNum) {
1946 Expressions.push_back(Exp);
1947 if (ExprIdx.size() < nextValueNumber + 1)
1948 ExprIdx.resize(nextValueNumber * 2);
1949 e = nextValueNumber;
1950 ExprIdx[nextValueNumber++] = nextExprNumber++;
1951 }
1952 return {e, CreateNewValNum};
1953}
1954
1955/// Return whether all the values related with the same \p num are
1956/// defined in \p BB.
1957bool GVN::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB,
1958 GVN &Gvn) {
1959 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
1960 while (Vals && Vals->BB == BB)
1961 Vals = Vals->Next;
1962 return !Vals;
1963}
1964
1965/// Wrap phiTranslateImpl to provide caching functionality.
1966uint32_t GVN::ValueTable::phiTranslate(const BasicBlock *Pred,
1967 const BasicBlock *PhiBlock, uint32_t Num,
1968 GVN &Gvn) {
1969 auto FindRes = PhiTranslateTable.find({Num, Pred});
1970 if (FindRes != PhiTranslateTable.end())
1971 return FindRes->second;
1972 uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, Gvn);
1973 PhiTranslateTable.insert({{Num, Pred}, NewNum});
1974 return NewNum;
1975}
1976
1977// Return true if the value number \p Num and NewNum have equal value.
1978// Return false if the result is unknown.
1979bool GVN::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
1980 const BasicBlock *Pred,
1981 const BasicBlock *PhiBlock, GVN &Gvn) {
1982 CallInst *Call = nullptr;
1983 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
1984 while (Vals) {
1985 Call = dyn_cast<CallInst>(Vals->Val);
1986 if (Call && Call->getParent() == PhiBlock)
1987 break;
1988 Vals = Vals->Next;
1989 }
1990
1991 if (AA->doesNotAccessMemory(Call))
1992 return true;
1993
1994 if (!MD || !AA->onlyReadsMemory(Call))
1995 return false;
1996
1997 MemDepResult local_dep = MD->getDependency(Call);
1998 if (!local_dep.isNonLocal())
1999 return false;
2000
2001 const MemoryDependenceResults::NonLocalDepInfo &deps =
2002 MD->getNonLocalCallDependency(Call);
2003
2004 // Check to see if the Call has no function local clobber.
2005 for (const NonLocalDepEntry &D : deps) {
2006 if (D.getResult().isNonFuncLocal())
2007 return true;
2008 }
2009 return false;
2010}
2011
2012/// Translate value number \p Num using phis, so that it has the values of
2013/// the phis in BB.
2014uint32_t GVN::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
2015 const BasicBlock *PhiBlock,
2016 uint32_t Num, GVN &Gvn) {
2017 if (PHINode *PN = NumberingPhi[Num]) {
2018 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
2019 if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred)
2020 if (uint32_t TransVal = lookup(PN->getIncomingValue(i), false))
2021 return TransVal;
2022 }
2023 return Num;
2024 }
2025
2026 // If there is any value related with Num is defined in a BB other than
2027 // PhiBlock, it cannot depend on a phi in PhiBlock without going through
2028 // a backedge. We can do an early exit in that case to save compile time.
2029 if (!areAllValsInBB(Num, PhiBlock, Gvn))
2030 return Num;
2031
2032 if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
2033 return Num;
2034 Expression Exp = Expressions[ExprIdx[Num]];
2035
2036 for (unsigned i = 0; i < Exp.varargs.size(); i++) {
2037 // For InsertValue and ExtractValue, some varargs are index numbers
2038 // instead of value numbers. Those index numbers should not be
2039 // translated.
2040 if ((i > 1 && Exp.opcode == Instruction::InsertValue) ||
2041 (i > 0 && Exp.opcode == Instruction::ExtractValue) ||
2042 (i > 1 && Exp.opcode == Instruction::ShuffleVector))
2043 continue;
2044 Exp.varargs[i] = phiTranslate(Pred, PhiBlock, Exp.varargs[i], Gvn);
2045 }
2046
2047 if (Exp.commutative) {
2048 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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2048, __extension__ __PRETTY_FUNCTION__))
;
2049 if (Exp.varargs[0] > Exp.varargs[1]) {
2050 std::swap(Exp.varargs[0], Exp.varargs[1]);
2051 uint32_t Opcode = Exp.opcode >> 8;
2052 if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
2053 Exp.opcode = (Opcode << 8) |
2054 CmpInst::getSwappedPredicate(
2055 static_cast<CmpInst::Predicate>(Exp.opcode & 255));
2056 }
2057 }
2058
2059 if (uint32_t NewNum = expressionNumbering[Exp]) {
2060 if (Exp.opcode == Instruction::Call && NewNum != Num)
2061 return areCallValsEqual(Num, NewNum, Pred, PhiBlock, Gvn) ? NewNum : Num;
2062 return NewNum;
2063 }
2064 return Num;
2065}
2066
2067/// Erase stale entry from phiTranslate cache so phiTranslate can be computed
2068/// again.
2069void GVN::ValueTable::eraseTranslateCacheEntry(uint32_t Num,
2070 const BasicBlock &CurrBlock) {
2071 for (const BasicBlock *Pred : predecessors(&CurrBlock))
2072 PhiTranslateTable.erase({Num, Pred});
2073}
2074
2075// In order to find a leader for a given value number at a
2076// specific basic block, we first obtain the list of all Values for that number,
2077// and then scan the list to find one whose block dominates the block in
2078// question. This is fast because dominator tree queries consist of only
2079// a few comparisons of DFS numbers.
2080Value *GVN::findLeader(const BasicBlock *BB, uint32_t num) {
2081 LeaderTableEntry Vals = LeaderTable[num];
2082 if (!Vals.Val) return nullptr;
2083
2084 Value *Val = nullptr;
2085 if (DT->dominates(Vals.BB, BB)) {
2086 Val = Vals.Val;
2087 if (isa<Constant>(Val)) return Val;
2088 }
2089
2090 LeaderTableEntry* Next = Vals.Next;
2091 while (Next) {
2092 if (DT->dominates(Next->BB, BB)) {
2093 if (isa<Constant>(Next->Val)) return Next->Val;
2094 if (!Val) Val = Next->Val;
2095 }
2096
2097 Next = Next->Next;
2098 }
2099
2100 return Val;
2101}
2102
2103/// There is an edge from 'Src' to 'Dst'. Return
2104/// true if every path from the entry block to 'Dst' passes via this edge. In
2105/// particular 'Dst' must not be reachable via another edge from 'Src'.
2106static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E,
2107 DominatorTree *DT) {
2108 // While in theory it is interesting to consider the case in which Dst has
2109 // more than one predecessor, because Dst might be part of a loop which is
2110 // only reachable from Src, in practice it is pointless since at the time
2111 // GVN runs all such loops have preheaders, which means that Dst will have
2112 // been changed to have only one predecessor, namely Src.
2113 const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
2114 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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2115, __extension__ __PRETTY_FUNCTION__))
2115 "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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2115, __extension__ __PRETTY_FUNCTION__))
;
2116 return Pred != nullptr;
2117}
2118
2119void GVN::assignBlockRPONumber(Function &F) {
2120 BlockRPONumber.clear();
2121 uint32_t NextBlockNumber = 1;
2122 ReversePostOrderTraversal<Function *> RPOT(&F);
2123 for (BasicBlock *BB : RPOT)
2124 BlockRPONumber[BB] = NextBlockNumber++;
2125 InvalidBlockRPONumbers = false;
2126}
2127
2128bool GVN::replaceOperandsForInBlockEquality(Instruction *Instr) const {
2129 bool Changed = false;
2130 for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
2131 Value *Operand = Instr->getOperand(OpNum);
2132 auto it = ReplaceOperandsWithMap.find(Operand);
2133 if (it != ReplaceOperandsWithMap.end()) {
2134 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)
2135 << *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)
;
2136 Instr->setOperand(OpNum, it->second);
2137 Changed = true;
2138 }
2139 }
2140 return Changed;
2141}
2142
2143/// The given values are known to be equal in every block
2144/// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with
2145/// 'RHS' everywhere in the scope. Returns whether a change was made.
2146/// If DominatesByEdge is false, then it means that we will propagate the RHS
2147/// value starting from the end of Root.Start.
2148bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
2149 bool DominatesByEdge) {
2150 SmallVector<std::pair<Value*, Value*>, 4> Worklist;
2151 Worklist.push_back(std::make_pair(LHS, RHS));
2152 bool Changed = false;
2153 // For speed, compute a conservative fast approximation to
2154 // DT->dominates(Root, Root.getEnd());
2155 const bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);
2156
2157 while (!Worklist.empty()) {
2158 std::pair<Value*, Value*> Item = Worklist.pop_back_val();
2159 LHS = Item.first; RHS = Item.second;
2160
2161 if (LHS == RHS)
2162 continue;
2163 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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2163, __extension__ __PRETTY_FUNCTION__))
;
2164
2165 // Don't try to propagate equalities between constants.
2166 if (isa<Constant>(LHS) && isa<Constant>(RHS))
2167 continue;
2168
2169 // Prefer a constant on the right-hand side, or an Argument if no constants.
2170 if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
2171 std::swap(LHS, RHS);
2172 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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2172, __extension__ __PRETTY_FUNCTION__))
;
2173
2174 // If there is no obvious reason to prefer the left-hand side over the
2175 // right-hand side, ensure the longest lived term is on the right-hand side,
2176 // so the shortest lived term will be replaced by the longest lived.
2177 // This tends to expose more simplifications.
2178 uint32_t LVN = VN.lookupOrAdd(LHS);
2179 if ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||
2180 (isa<Instruction>(LHS) && isa<Instruction>(RHS))) {
2181 // Move the 'oldest' value to the right-hand side, using the value number
2182 // as a proxy for age.
2183 uint32_t RVN = VN.lookupOrAdd(RHS);
2184 if (LVN < RVN) {
2185 std::swap(LHS, RHS);
2186 LVN = RVN;
2187 }
2188 }
2189
2190 // If value numbering later sees that an instruction in the scope is equal
2191 // to 'LHS' then ensure it will be turned into 'RHS'. In order to preserve
2192 // the invariant that instructions only occur in the leader table for their
2193 // own value number (this is used by removeFromLeaderTable), do not do this
2194 // if RHS is an instruction (if an instruction in the scope is morphed into
2195 // LHS then it will be turned into RHS by the next GVN iteration anyway, so
2196 // using the leader table is about compiling faster, not optimizing better).
2197 // The leader table only tracks basic blocks, not edges. Only add to if we
2198 // have the simple case where the edge dominates the end.
2199 if (RootDominatesEnd && !isa<Instruction>(RHS))
2200 addToLeaderTable(LVN, RHS, Root.getEnd());
2201
2202 // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope. As
2203 // LHS always has at least one use that is not dominated by Root, this will
2204 // never do anything if LHS has only one use.
2205 if (!LHS->hasOneUse()) {
2206 unsigned NumReplacements =
2207 DominatesByEdge
2208 ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
2209 : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());
2210
2211 Changed |= NumReplacements > 0;
2212 NumGVNEqProp += NumReplacements;
2213 // Cached information for anything that uses LHS will be invalid.
2214 if (MD)
2215 MD->invalidateCachedPointerInfo(LHS);
2216 }
2217
2218 // Now try to deduce additional equalities from this one. For example, if
2219 // the known equality was "(A != B)" == "false" then it follows that A and B
2220 // are equal in the scope. Only boolean equalities with an explicit true or
2221 // false RHS are currently supported.
2222 if (!RHS->getType()->isIntegerTy(1))
2223 // Not a boolean equality - bail out.
2224 continue;
2225 ConstantInt *CI = dyn_cast<ConstantInt>(RHS);
2226 if (!CI)
2227 // RHS neither 'true' nor 'false' - bail out.
2228 continue;
2229 // Whether RHS equals 'true'. Otherwise it equals 'false'.
2230 bool isKnownTrue = CI->isMinusOne();
2231 bool isKnownFalse = !isKnownTrue;
2232
2233 // If "A && B" is known true then both A and B are known true. If "A || B"
2234 // is known false then both A and B are known false.
2235 Value *A, *B;
2236 if ((isKnownTrue && match(LHS, m_LogicalAnd(m_Value(A), m_Value(B)))) ||
2237 (isKnownFalse && match(LHS, m_LogicalOr(m_Value(A), m_Value(B))))) {
2238 Worklist.push_back(std::make_pair(A, RHS));
2239 Worklist.push_back(std::make_pair(B, RHS));
2240 continue;
2241 }
2242
2243 // If we are propagating an equality like "(A == B)" == "true" then also
2244 // propagate the equality A == B. When propagating a comparison such as
2245 // "(A >= B)" == "true", replace all instances of "A < B" with "false".
2246 if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
2247 Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1);
2248
2249 // If "A == B" is known true, or "A != B" is known false, then replace
2250 // A with B everywhere in the scope. For floating point operations, we
2251 // have to be careful since equality does not always imply equivalance.
2252 if ((isKnownTrue && impliesEquivalanceIfTrue(Cmp)) ||
2253 (isKnownFalse && impliesEquivalanceIfFalse(Cmp)))
2254 Worklist.push_back(std::make_pair(Op0, Op1));
2255
2256 // If "A >= B" is known true, replace "A < B" with false everywhere.
2257 CmpInst::Predicate NotPred = Cmp->getInversePredicate();
2258 Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse);
2259 // Since we don't have the instruction "A < B" immediately to hand, work
2260 // out the value number that it would have and use that to find an
2261 // appropriate instruction (if any).
2262 uint32_t NextNum = VN.getNextUnusedValueNumber();
2263 uint32_t Num = VN.lookupOrAddCmp(Cmp->getOpcode(), NotPred, Op0, Op1);
2264 // If the number we were assigned was brand new then there is no point in
2265 // looking for an instruction realizing it: there cannot be one!
2266 if (Num < NextNum) {
2267 Value *NotCmp = findLeader(Root.getEnd(), Num);
2268 if (NotCmp && isa<Instruction>(NotCmp)) {
2269 unsigned NumReplacements =
2270 DominatesByEdge
2271 ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
2272 : replaceDominatedUsesWith(NotCmp, NotVal, *DT,
2273 Root.getStart());
2274 Changed |= NumReplacements > 0;
2275 NumGVNEqProp += NumReplacements;
2276 // Cached information for anything that uses NotCmp will be invalid.
2277 if (MD)
2278 MD->invalidateCachedPointerInfo(NotCmp);
2279 }
2280 }
2281 // Ensure that any instruction in scope that gets the "A < B" value number
2282 // is replaced with false.
2283 // The leader table only tracks basic blocks, not edges. Only add to if we
2284 // have the simple case where the edge dominates the end.
2285 if (RootDominatesEnd)
2286 addToLeaderTable(Num, NotVal, Root.getEnd());
2287
2288 continue;
2289 }
2290 }
2291
2292 return Changed;
2293}
2294
2295/// When calculating availability, handle an instruction
2296/// by inserting it into the appropriate sets
2297bool GVN::processInstruction(Instruction *I) {
2298 // Ignore dbg info intrinsics.
2299 if (isa<DbgInfoIntrinsic>(I))
2300 return false;
2301
2302 // If the instruction can be easily simplified then do so now in preference
2303 // to value numbering it. Value numbering often exposes redundancies, for
2304 // example if it determines that %y is equal to %x then the instruction
2305 // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
2306 const DataLayout &DL = I->getModule()->getDataLayout();
2307 if (Value *V = SimplifyInstruction(I, {DL, TLI, DT, AC})) {
2308 bool Changed = false;
2309 if (!I->use_empty()) {
2310 // Simplification can cause a special instruction to become not special.
2311 // For example, devirtualization to a willreturn function.
2312 ICF->removeUsersOf(I);
2313 I->replaceAllUsesWith(V);
2314 Changed = true;
2315 }
2316 if (isInstructionTriviallyDead(I, TLI)) {
2317 markInstructionForDeletion(I);
2318 Changed = true;
2319 }
2320 if (Changed) {
2321 if (MD && V->getType()->isPtrOrPtrVectorTy())
2322 MD->invalidateCachedPointerInfo(V);
2323 ++NumGVNSimpl;
2324 return true;
2325 }
2326 }
2327
2328 if (auto *Assume = dyn_cast<AssumeInst>(I))
2329 return processAssumeIntrinsic(Assume);
2330
2331 if (LoadInst *Load = dyn_cast<LoadInst>(I)) {
2332 if (processLoad(Load))
2333 return true;
2334
2335 unsigned Num = VN.lookupOrAdd(Load);
2336 addToLeaderTable(Num, Load, Load->getParent());
2337 return false;
2338 }
2339
2340 // For conditional branches, we can perform simple conditional propagation on
2341 // the condition value itself.
2342 if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
2343 if (!BI->isConditional())
2344 return false;
2345
2346 if (isa<Constant>(BI->getCondition()))
2347 return processFoldableCondBr(BI);
2348
2349 Value *BranchCond = BI->getCondition();
2350 BasicBlock *TrueSucc = BI->getSuccessor(0);
2351 BasicBlock *FalseSucc = BI->getSuccessor(1);
2352 // Avoid multiple edges early.
2353 if (TrueSucc == FalseSucc)
2354 return false;
2355
2356 BasicBlock *Parent = BI->getParent();
2357 bool Changed = false;
2358
2359 Value *TrueVal = ConstantInt::getTrue(TrueSucc->getContext());
2360 BasicBlockEdge TrueE(Parent, TrueSucc);
2361 Changed |= propagateEquality(BranchCond, TrueVal, TrueE, true);
2362
2363 Value *FalseVal = ConstantInt::getFalse(FalseSucc->getContext());
2364 BasicBlockEdge FalseE(Parent, FalseSucc);
2365 Changed |= propagateEquality(BranchCond, FalseVal, FalseE, true);
2366
2367 return Changed;
2368 }
2369
2370 // For switches, propagate the case values into the case destinations.
2371 if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
2372 Value *SwitchCond = SI->getCondition();
2373 BasicBlock *Parent = SI->getParent();
2374 bool Changed = false;
2375
2376 // Remember how many outgoing edges there are to every successor.
2377 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
2378 for (unsigned i = 0, n = SI->getNumSuccessors(); i != n; ++i)
2379 ++SwitchEdges[SI->getSuccessor(i)];
2380
2381 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
2382 i != e; ++i) {
2383 BasicBlock *Dst = i->getCaseSuccessor();
2384 // If there is only a single edge, propagate the case value into it.
2385 if (SwitchEdges.lookup(Dst) == 1) {
2386 BasicBlockEdge E(Parent, Dst);
2387 Changed |= propagateEquality(SwitchCond, i->getCaseValue(), E, true);
2388 }
2389 }
2390 return Changed;
2391 }
2392
2393 // Instructions with void type don't return a value, so there's
2394 // no point in trying to find redundancies in them.
2395 if (I->getType()->isVoidTy())
2396 return false;
2397
2398 uint32_t NextNum = VN.getNextUnusedValueNumber();
2399 unsigned Num = VN.lookupOrAdd(I);
2400
2401 // Allocations are always uniquely numbered, so we can save time and memory
2402 // by fast failing them.
2403 if (isa<AllocaInst>(I) || I->isTerminator() || isa<PHINode>(I)) {
2404 addToLeaderTable(Num, I, I->getParent());
2405 return false;
2406 }
2407
2408 // If the number we were assigned was a brand new VN, then we don't
2409 // need to do a lookup to see if the number already exists
2410 // somewhere in the domtree: it can't!
2411 if (Num >= NextNum) {
2412 addToLeaderTable(Num, I, I->getParent());
2413 return false;
2414 }
2415
2416 // Perform fast-path value-number based elimination of values inherited from
2417 // dominators.
2418 Value *Repl = findLeader(I->getParent(), Num);
2419 if (!Repl) {
2420 // Failure, just remember this instance for future use.
2421 addToLeaderTable(Num, I, I->getParent());
2422 return false;
2423 } else if (Repl == I) {
2424 // If I was the result of a shortcut PRE, it might already be in the table
2425 // and the best replacement for itself. Nothing to do.
2426 return false;
2427 }
2428
2429 // Remove it!
2430 patchAndReplaceAllUsesWith(I, Repl);
2431 if (MD && Repl->getType()->isPtrOrPtrVectorTy())
2432 MD->invalidateCachedPointerInfo(Repl);
2433 markInstructionForDeletion(I);
2434 return true;
2435}
2436
2437/// runOnFunction - This is the main transformation entry point for a function.
2438bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
2439 const TargetLibraryInfo &RunTLI, AAResults &RunAA,
2440 MemoryDependenceResults *RunMD, LoopInfo *LI,
2441 OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {
2442 AC = &RunAC;
2443 DT = &RunDT;
2444 VN.setDomTree(DT);
2445 TLI = &RunTLI;
2446 VN.setAliasAnalysis(&RunAA);
2447 MD = RunMD;
2448 ImplicitControlFlowTracking ImplicitCFT;
2449 ICF = &ImplicitCFT;
2450 this->LI = LI;
2451 VN.setMemDep(MD);
2452 ORE = RunORE;
2453 InvalidBlockRPONumbers = true;
2454 MemorySSAUpdater Updater(MSSA);
2455 MSSAU = MSSA ? &Updater : nullptr;
2456
2457 bool Changed = false;
2458 bool ShouldContinue = true;
2459
2460 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
2461 // Merge unconditional branches, allowing PRE to catch more
2462 // optimization opportunities.
2463 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
2464 BasicBlock *BB = &*FI++;
2465
2466 bool removedBlock = MergeBlockIntoPredecessor(BB, &DTU, LI, MSSAU, MD);
2467 if (removedBlock)
2468 ++NumGVNBlocks;
2469
2470 Changed |= removedBlock;
2471 }
2472
2473 unsigned Iteration = 0;
2474 while (ShouldContinue) {
2475 LLVM_DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN iteration: " << Iteration
<< "\n"; } } while (false)
;
2476 ShouldContinue = iterateOnFunction(F);
2477 Changed |= ShouldContinue;
2478 ++Iteration;
2479 }
2480
2481 if (isPREEnabled()) {
2482 // Fabricate val-num for dead-code in order to suppress assertion in
2483 // performPRE().
2484 assignValNumForDeadCode();
2485 bool PREChanged = true;
2486 while (PREChanged) {
2487 PREChanged = performPRE(F);
2488 Changed |= PREChanged;
2489 }
2490 }
2491
2492 // FIXME: Should perform GVN again after PRE does something. PRE can move
2493 // computations into blocks where they become fully redundant. Note that
2494 // we can't do this until PRE's critical edge splitting updates memdep.
2495 // Actually, when this happens, we should just fully integrate PRE into GVN.
2496
2497 cleanupGlobalSets();
2498 // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
2499 // iteration.
2500 DeadBlocks.clear();
2501
2502 if (MSSA && VerifyMemorySSA)
2503 MSSA->verifyMemorySSA();
2504
2505 return Changed;
2506}
2507
2508bool GVN::processBlock(BasicBlock *BB) {
2509 // FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
2510 // (and incrementing BI before processing an instruction).
2511 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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2512, __extension__ __PRETTY_FUNCTION__))
2512 "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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2512, __extension__ __PRETTY_FUNCTION__))
;
2513 if (DeadBlocks.count(BB))
2514 return false;
2515
2516 // Clearing map before every BB because it can be used only for single BB.
2517 ReplaceOperandsWithMap.clear();
2518 bool ChangedFunction = false;
2519
2520 // Since we may not have visited the input blocks of the phis, we can't
2521 // use our normal hash approach for phis. Instead, simply look for
2522 // obvious duplicates. The first pass of GVN will tend to create
2523 // identical phis, and the second or later passes can eliminate them.
2524 ChangedFunction |= EliminateDuplicatePHINodes(BB);
2525
2526 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
2527 BI != BE;) {
2528 if (!ReplaceOperandsWithMap.empty())
2529 ChangedFunction |= replaceOperandsForInBlockEquality(&*BI);
2530 ChangedFunction |= processInstruction(&*BI);
2531
2532 if (InstrsToErase.empty()) {
2533 ++BI;
2534 continue;
2535 }
2536
2537 // If we need some instructions deleted, do it now.
2538 NumGVNInstr += InstrsToErase.size();
2539
2540 // Avoid iterator invalidation.
2541 bool AtStart = BI == BB->begin();
2542 if (!AtStart)
2543 --BI;
2544
2545 for (auto *I : InstrsToErase) {
2546 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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2546, __extension__ __PRETTY_FUNCTION__))
;
2547 LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN removed: " << *I <<
'\n'; } } while (false)
;
2548 salvageKnowledge(I, AC);
2549 salvageDebugInfo(*I);
2550 if (MD) MD->removeInstruction(I);
2551 if (MSSAU)
2552 MSSAU->removeMemoryAccess(I);
2553 LLVM_DEBUG(verifyRemoved(I))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { verifyRemoved(I); } } while (false)
;
2554 ICF->removeInstruction(I);
2555 I->eraseFromParent();
2556 }
2557 InstrsToErase.clear();
2558
2559 if (AtStart)
2560 BI = BB->begin();
2561 else
2562 ++BI;
2563 }
2564
2565 return ChangedFunction;
2566}
2567
2568// Instantiate an expression in a predecessor that lacked it.
2569bool GVN::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
2570 BasicBlock *Curr, unsigned int ValNo) {
2571 // Because we are going top-down through the block, all value numbers
2572 // will be available in the predecessor by the time we need them. Any
2573 // that weren't originally present will have been instantiated earlier
2574 // in this loop.
2575 bool success = true;
2576 for (unsigned i = 0, e = Instr->getNumOperands(); i != e; ++i) {
2577 Value *Op = Instr->getOperand(i);
2578 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
2579 continue;
2580 // This could be a newly inserted instruction, in which case, we won't
2581 // find a value number, and should give up before we hurt ourselves.
2582 // FIXME: Rewrite the infrastructure to let it easier to value number
2583 // and process newly inserted instructions.
2584 if (!VN.exists(Op)) {
2585 success = false;
2586 break;
2587 }
2588 uint32_t TValNo =
2589 VN.phiTranslate(Pred, Curr, VN.lookup(Op), *this);
2590 if (Value *V = findLeader(Pred, TValNo)) {
2591 Instr->setOperand(i, V);
2592 } else {
2593 success = false;
2594 break;
2595 }
2596 }
2597
2598 // Fail out if we encounter an operand that is not available in
2599 // the PRE predecessor. This is typically because of loads which
2600 // are not value numbered precisely.
2601 if (!success)
2602 return false;
2603
2604 Instr->insertBefore(Pred->getTerminator());
2605 Instr->setName(Instr->getName() + ".pre");
2606 Instr->setDebugLoc(Instr->getDebugLoc());
2607
2608 ICF->insertInstructionTo(Instr, Pred);
2609
2610 unsigned Num = VN.lookupOrAdd(Instr);
2611 VN.add(Instr, Num);
2612
2613 // Update the availability map to include the new instruction.
2614 addToLeaderTable(Num, Instr, Pred);
2615 return true;
2616}
2617
2618bool GVN::performScalarPRE(Instruction *CurInst) {
2619 if (isa<AllocaInst>(CurInst) || CurInst->isTerminator() ||
2620 isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() ||
2621 CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
2622 isa<DbgInfoIntrinsic>(CurInst))
2623 return false;
2624
2625 // Don't do PRE on compares. The PHI would prevent CodeGenPrepare from
2626 // sinking the compare again, and it would force the code generator to
2627 // move the i1 from processor flags or predicate registers into a general
2628 // purpose register.
2629 if (isa<CmpInst>(CurInst))
2630 return false;
2631
2632 // Don't do PRE on GEPs. The inserted PHI would prevent CodeGenPrepare from
2633 // sinking the addressing mode computation back to its uses. Extending the
2634 // GEP's live range increases the register pressure, and therefore it can
2635 // introduce unnecessary spills.
2636 //
2637 // This doesn't prevent Load PRE. PHI translation will make the GEP available
2638 // to the load by moving it to the predecessor block if necessary.
2639 if (isa<GetElementPtrInst>(CurInst))
2640 return false;
2641
2642 if (auto *CallB = dyn_cast<CallBase>(CurInst)) {
2643 // We don't currently value number ANY inline asm calls.
2644 if (CallB->isInlineAsm())
2645 return false;
2646 // Don't do PRE on convergent calls.
2647 if (CallB->isConvergent())
2648 return false;
2649 }
2650
2651 uint32_t ValNo = VN.lookup(CurInst);
2652
2653 // Look for the predecessors for PRE opportunities. We're
2654 // only trying to solve the basic diamond case, where
2655 // a value is computed in the successor and one predecessor,
2656 // but not the other. We also explicitly disallow cases
2657 // where the successor is its own predecessor, because they're
2658 // more complicated to get right.
2659 unsigned NumWith = 0;
2660 unsigned NumWithout = 0;
2661 BasicBlock *PREPred = nullptr;
2662 BasicBlock *CurrentBlock = CurInst->getParent();
2663
2664 // Update the RPO numbers for this function.
2665 if (InvalidBlockRPONumbers)
2666 assignBlockRPONumber(*CurrentBlock->getParent());
2667
2668 SmallVector<std::pair<Value *, BasicBlock *>, 8> predMap;
2669 for (BasicBlock *P : predecessors(CurrentBlock)) {
2670 // We're not interested in PRE where blocks with predecessors that are
2671 // not reachable.
2672 if (!DT->isReachableFromEntry(P)) {
2673 NumWithout = 2;
2674 break;
2675 }
2676 // It is not safe to do PRE when P->CurrentBlock is a loop backedge, and
2677 // when CurInst has operand defined in CurrentBlock (so it may be defined
2678 // by phi in the loop header).
2679 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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2680, __extension__ __PRETTY_FUNCTION__))
2680 "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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2680, __extension__ __PRETTY_FUNCTION__))
;
2681 if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock] &&
2682 llvm::any_of(CurInst->operands(), [&](const Use &U) {
2683 if (auto *Inst = dyn_cast<Instruction>(U.get()))
2684 return Inst->getParent() == CurrentBlock;
2685 return false;
2686 })) {
2687 NumWithout = 2;
2688 break;
2689 }
2690
2691 uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);
2692 Value *predV = findLeader(P, TValNo);
2693 if (!predV) {
2694 predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));
2695 PREPred = P;
2696 ++NumWithout;
2697 } else if (predV == CurInst) {
2698 /* CurInst dominates this predecessor. */
2699 NumWithout = 2;
2700 break;
2701 } else {
2702 predMap.push_back(std::make_pair(predV, P));
2703 ++NumWith;
2704 }
2705 }
2706
2707 // Don't do PRE when it might increase code size, i.e. when
2708 // we would need to insert instructions in more than one pred.
2709 if (NumWithout > 1 || NumWith == 0)
2710 return false;
2711
2712 // We may have a case where all predecessors have the instruction,
2713 // and we just need to insert a phi node. Otherwise, perform
2714 // insertion.
2715 Instruction *PREInstr = nullptr;
2716
2717 if (NumWithout != 0) {
2718 if (!isSafeToSpeculativelyExecute(CurInst)) {
2719 // It is only valid to insert a new instruction if the current instruction
2720 // is always executed. An instruction with implicit control flow could
2721 // prevent us from doing it. If we cannot speculate the execution, then
2722 // PRE should be prohibited.
2723 if (ICF->isDominatedByICFIFromSameBlock(CurInst))
2724 return false;
2725 }
2726
2727 // Don't do PRE across indirect branch.
2728 if (isa<IndirectBrInst>(PREPred->getTerminator()))
2729 return false;
2730
2731 // Don't do PRE across callbr.
2732 // FIXME: Can we do this across the fallthrough edge?
2733 if (isa<CallBrInst>(PREPred->getTerminator()))
2734 return false;
2735
2736 // We can't do PRE safely on a critical edge, so instead we schedule
2737 // the edge to be split and perform the PRE the next time we iterate
2738 // on the function.
2739 unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);
2740 if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
2741 toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
2742 return false;
2743 }
2744 // We need to insert somewhere, so let's give it a shot
2745 PREInstr = CurInst->clone();
2746 if (!performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo)) {
2747 // If we failed insertion, make sure we remove the instruction.
2748 LLVM_DEBUG(verifyRemoved(PREInstr))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { verifyRemoved(PREInstr); } } while (false)
;
2749 PREInstr->deleteValue();
2750 return false;
2751 }
2752 }
2753
2754 // Either we should have filled in the PRE instruction, or we should
2755 // not have needed insertions.
2756 assert(PREInstr != nullptr || NumWithout == 0)(static_cast <bool> (PREInstr != nullptr || NumWithout ==
0) ? void (0) : __assert_fail ("PREInstr != nullptr || NumWithout == 0"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2756, __extension__ __PRETTY_FUNCTION__))
;
2757
2758 ++NumGVNPRE;
2759
2760 // Create a PHI to make the value available in this block.
2761 PHINode *Phi =
2762 PHINode::Create(CurInst->getType(), predMap.size(),
2763 CurInst->getName() + ".pre-phi", &CurrentBlock->front());
2764 for (unsigned i = 0, e = predMap.size(); i != e; ++i) {
2765 if (Value *V = predMap[i].first) {
2766 // If we use an existing value in this phi, we have to patch the original
2767 // value because the phi will be used to replace a later value.
2768 patchReplacementInstruction(CurInst, V);
2769 Phi->addIncoming(V, predMap[i].second);
2770 } else
2771 Phi->addIncoming(PREInstr, PREPred);
2772 }
2773
2774 VN.add(Phi, ValNo);
2775 // After creating a new PHI for ValNo, the phi translate result for ValNo will
2776 // be changed, so erase the related stale entries in phi translate cache.
2777 VN.eraseTranslateCacheEntry(ValNo, *CurrentBlock);
2778 addToLeaderTable(ValNo, Phi, CurrentBlock);
2779 Phi->setDebugLoc(CurInst->getDebugLoc());
2780 CurInst->replaceAllUsesWith(Phi);
2781 if (MD && Phi->getType()->isPtrOrPtrVectorTy())
2782 MD->invalidateCachedPointerInfo(Phi);
2783 VN.erase(CurInst);
2784 removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
2785
2786 LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { dbgs() << "GVN PRE removed: " << *CurInst
<< '\n'; } } while (false)
;
2787 if (MD)
2788 MD->removeInstruction(CurInst);
2789 if (MSSAU)
2790 MSSAU->removeMemoryAccess(CurInst);
2791 LLVM_DEBUG(verifyRemoved(CurInst))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn")) { verifyRemoved(CurInst); } } while (false)
;
2792 // FIXME: Intended to be markInstructionForDeletion(CurInst), but it causes
2793 // some assertion failures.
2794 ICF->removeInstruction(CurInst);
2795 CurInst->eraseFromParent();
2796 ++NumGVNInstr;
2797
2798 return true;
2799}
2800
2801/// Perform a purely local form of PRE that looks for diamond
2802/// control flow patterns and attempts to perform simple PRE at the join point.
2803bool GVN::performPRE(Function &F) {
2804 bool Changed = false;
2805 for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) {
2806 // Nothing to PRE in the entry block.
2807 if (CurrentBlock == &F.getEntryBlock())
2808 continue;
2809
2810 // Don't perform PRE on an EH pad.
2811 if (CurrentBlock->isEHPad())
2812 continue;
2813
2814 for (BasicBlock::iterator BI = CurrentBlock->begin(),
2815 BE = CurrentBlock->end();
2816 BI != BE;) {
2817 Instruction *CurInst = &*BI++;
2818 Changed |= performScalarPRE(CurInst);
2819 }
2820 }
2821
2822 if (splitCriticalEdges())
2823 Changed = true;
2824
2825 return Changed;
2826}
2827
2828/// Split the critical edge connecting the given two blocks, and return
2829/// the block inserted to the critical edge.
2830BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
2831 // GVN does not require loop-simplify, do not try to preserve it if it is not
2832 // possible.
2833 BasicBlock *BB = SplitCriticalEdge(
2834 Pred, Succ,
2835 CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());
2836 if (BB) {
2837 if (MD)
2838 MD->invalidateCachedPredecessors();
2839 InvalidBlockRPONumbers = true;
2840 }
2841 return BB;
2842}
2843
2844/// Split critical edges found during the previous
2845/// iteration that may enable further optimization.
2846bool GVN::splitCriticalEdges() {
2847 if (toSplit.empty())
2848 return false;
2849
2850 bool Changed = false;
2851 do {
2852 std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val();
2853 Changed |= SplitCriticalEdge(Edge.first, Edge.second,
2854 CriticalEdgeSplittingOptions(DT, LI, MSSAU)) !=
2855 nullptr;
2856 } while (!toSplit.empty());
2857 if (Changed) {
2858 if (MD)
2859 MD->invalidateCachedPredecessors();
2860 InvalidBlockRPONumbers = true;
2861 }
2862 return Changed;
2863}
2864
2865/// Executes one iteration of GVN
2866bool GVN::iterateOnFunction(Function &F) {
2867 cleanupGlobalSets();
2868
2869 // Top-down walk of the dominator tree
2870 bool Changed = false;
2871 // Needed for value numbering with phi construction to work.
2872 // RPOT walks the graph in its constructor and will not be invalidated during
2873 // processBlock.
2874 ReversePostOrderTraversal<Function *> RPOT(&F);
2875
2876 for (BasicBlock *BB : RPOT)
2877 Changed |= processBlock(BB);
2878
2879 return Changed;
2880}
2881
2882void GVN::cleanupGlobalSets() {
2883 VN.clear();
2884 LeaderTable.clear();
2885 BlockRPONumber.clear();
2886 TableAllocator.Reset();
2887 ICF->clear();
2888 InvalidBlockRPONumbers = true;
2889}
2890
2891/// Verify that the specified instruction does not occur in our
2892/// internal data structures.
2893void GVN::verifyRemoved(const Instruction *Inst) const {
2894 VN.verifyRemoved(Inst);
2895
2896 // Walk through the value number scope to make sure the instruction isn't
2897 // ferreted away in it.
2898 for (const auto &I : LeaderTable) {
2899 const LeaderTableEntry *Node = &I.second;
2900 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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2900, __extension__ __PRETTY_FUNCTION__))
;
2901
2902 while (Node->Next) {
2903 Node = Node->Next;
2904 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-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/Scalar/GVN.cpp"
, 2904, __extension__ __PRETTY_FUNCTION__))
;
2905 }
2906 }
2907}
2908
2909/// BB is declared dead, which implied other blocks become dead as well. This
2910/// function is to add all these blocks to "DeadBlocks". For the dead blocks'
2911/// live successors, update their phi nodes by replacing the operands
2912/// corresponding to dead blocks with UndefVal.
2913void GVN::addDeadBlock(BasicBlock *BB) {
2914 SmallVector<BasicBlock *, 4> NewDead;
2915 SmallSetVector<BasicBlock *, 4> DF;
2916
2917 NewDead.push_back(BB);
2918 while (!NewDead.empty()) {
2919 BasicBlock *D = NewDead.pop_back_val();
2920 if (DeadBlocks.count(D))
2921 continue;
2922
2923 // All blocks dominated by D are dead.
2924 SmallVector<BasicBlock *, 8> Dom;
2925 DT->getDescendants(D, Dom);
2926 DeadBlocks.insert(Dom.begin(), Dom.end());
2927
2928 // Figure out the dominance-frontier(D).
2929 for (BasicBlock *B : Dom) {
2930 for (BasicBlock *S : successors(B)) {
2931 if (DeadBlocks.count(S))
2932 continue;
2933
2934 bool AllPredDead = true;
2935 for (BasicBlock *P : predecessors(S))
2936 if (!DeadBlocks.count(P)) {
2937 AllPredDead = false;
2938 break;
2939 }
2940
2941 if (!AllPredDead) {
2942 // S could be proved dead later on. That is why we don't update phi
2943 // operands at this moment.
2944 DF.insert(S);
2945 } else {
2946 // While S is not dominated by D, it is dead by now. This could take
2947 // place if S already have a dead predecessor before D is declared
2948 // dead.
2949 NewDead.push_back(S);
2950 }
2951 }
2952 }
2953 }
2954
2955 // For the dead blocks' live successors, update their phi nodes by replacing
2956 // the operands corresponding to dead blocks with UndefVal.
2957 for (BasicBlock *B : DF) {
2958 if (DeadBlocks.count(B))
2959 continue;
2960
2961 // First, split the critical edges. This might also create additional blocks
2962 // to preserve LoopSimplify form and adjust edges accordingly.
2963 SmallVector<BasicBlock *, 4> Preds(predecessors(B));
2964 for (BasicBlock *P : Preds) {
2965 if (!DeadBlocks.count(P))
2966 continue;
2967
2968 if (llvm::is_contained(successors(P), B) &&
2969 isCriticalEdge(P->getTerminator(), B)) {
2970 if (BasicBlock *S = splitCriticalEdges(P, B))
2971 DeadBlocks.insert(P = S);
Although the value stored to 'P' is used in the enclosing expression, the value is never actually read from 'P'
2972 }
2973 }
2974
2975 // Now undef the incoming values from the dead predecessors.
2976 for (BasicBlock *P : predecessors(B)) {
2977 if (!DeadBlocks.count(P))
2978 continue;
2979 for (PHINode &Phi : B->phis()) {
2980 Phi.setIncomingValueForBlock(P, UndefValue::get(Phi.getType()));
2981 if (MD)
2982 MD->invalidateCachedPointerInfo(&Phi);
2983 }
2984 }
2985 }
2986}
2987
2988// If the given branch is recognized as a foldable branch (i.e. conditional
2989// branch with constant condition), it will perform following analyses and
2990// transformation.
2991// 1) If the dead out-coming edge is a critical-edge, split it. Let
2992// R be the target of the dead out-coming edge.
2993// 1) Identify the set of dead blocks implied by the branch's dead outcoming
2994// edge. The result of this step will be {X| X is dominated by R}
2995// 2) Identify those blocks which haves at least one dead predecessor. The
2996// result of this step will be dominance-frontier(R).
2997// 3) Update the PHIs in DF(R) by replacing the operands corresponding to
2998// dead blocks with "UndefVal" in an hope these PHIs will optimized away.
2999//
3000// Return true iff *NEW* dead code are found.
3001bool GVN::processFoldableCondBr(BranchInst *BI) {
3002 if (!BI || BI->isUnconditional())
3003 return false;
3004
3005 // If a branch has two identical successors, we cannot declare either dead.
3006 if (BI->getSuccessor(0) == BI->getSuccessor(1))
3007 return false;
3008
3009 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
3010 if (!Cond)
3011 return false;
3012
3013 BasicBlock *DeadRoot =
3014 Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0);
3015 if (DeadBlocks.count(DeadRoot))
3016 return false;
3017
3018 if (!DeadRoot->getSinglePredecessor())
3019 DeadRoot = splitCriticalEdges(BI->getParent(), DeadRoot);
3020
3021 addDeadBlock(DeadRoot);
3022 return true;
3023}
3024
3025// performPRE() will trigger assert if it comes across an instruction without
3026// associated val-num. As it normally has far more live instructions than dead
3027// instructions, it makes more sense just to "fabricate" a val-number for the
3028// dead code than checking if instruction involved is dead or not.
3029void GVN::assignValNumForDeadCode() {
3030 for (BasicBlock *BB : DeadBlocks) {
3031 for (Instruction &Inst : *BB) {
3032 unsigned ValNum = VN.lookupOrAdd(&Inst);
3033 addToLeaderTable(ValNum, &Inst, BB);
3034 }
3035 }
3036}
3037
3038class llvm::gvn::GVNLegacyPass : public FunctionPass {
3039public:
3040 static char ID; // Pass identification, replacement for typeid
3041
3042 explicit GVNLegacyPass(bool NoMemDepAnalysis = !GVNEnableMemDep)
3043 : FunctionPass(ID), Impl(GVNOptions().setMemDep(!NoMemDepAnalysis)) {
3044 initializeGVNLegacyPassPass(*PassRegistry::getPassRegistry());
3045 }
3046
3047 bool runOnFunction(Function &F) override {
3048 if (skipFunction(F))
3049 return false;
3050
3051 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
3052
3053 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
3054 return Impl.runImpl(
3055 F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
3056 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
3057 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
3058 getAnalysis<AAResultsWrapperPass>().getAAResults(),
3059 Impl.isMemDepEnabled()
3060 ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()
3061 : nullptr,
3062 LIWP ? &LIWP->getLoopInfo() : nullptr,
3063 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),
3064 MSSAWP ? &MSSAWP->getMSSA() : nullptr);
3065 }
3066
3067 void getAnalysisUsage(AnalysisUsage &AU) const override {
3068 AU.addRequired<AssumptionCacheTracker>();
3069 AU.addRequired<DominatorTreeWrapperPass>();
3070 AU.addRequired<TargetLibraryInfoWrapperPass>();
3071 AU.addRequired<LoopInfoWrapperPass>();
3072 if (Impl.isMemDepEnabled())
3073 AU.addRequired<MemoryDependenceWrapperPass>();
3074 AU.addRequired<AAResultsWrapperPass>();
3075 AU.addPreserved<DominatorTreeWrapperPass>();
3076 AU.addPreserved<GlobalsAAWrapperPass>();
3077 AU.addPreserved<TargetLibraryInfoWrapperPass>();
3078 AU.addPreserved<LoopInfoWrapperPass>();
3079 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
3080 AU.addPreserved<MemorySSAWrapperPass>();
3081 }
3082
3083private:
3084 GVN Impl;
3085};
3086
3087char GVNLegacyPass::ID = 0;
3088
3089INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)static void *initializeGVNLegacyPassPassOnce(PassRegistry &
Registry) {
3090INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);
3091INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)initializeMemoryDependenceWrapperPassPass(Registry);
3092INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
3093INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
3094INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
3095INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
3096INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
3097INITIALIZE_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)); }
3098
3099// The public interface to this file...
3100FunctionPass *llvm::createGVNPass(bool NoMemDepAnalysis) {
3101 return new GVNLegacyPass(NoMemDepAnalysis);
3102}