Bug Summary

File:build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Transforms/Scalar/GVN.cpp
Warning:line 3092, column 29
Although the value stored to 'P' is used in the enclosing expression, the value is never actually read from 'P'

Annotated Source Code

Press '?' to see keyboard shortcuts

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