Bug Summary

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