Bug Summary

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