Bug Summary

File:llvm/lib/Transforms/Scalar/GVN.cpp
Warning:line 2614, column 29
Although the value stored to 'P' is used in the enclosing expression, the value is never actually read from 'P'

Annotated Source Code

Press '?' to see keyboard shortcuts

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