Bug Summary

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