Bug Summary

File:lib/Transforms/Scalar/GVNSink.cpp
Warning:line 399, column 7
Called C++ object pointer is null

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 GVNSink.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -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 -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn326246/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-7~svn326246/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn326246/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.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++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn326246/build-llvm/lib/Transforms/Scalar -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-02-28-041547-14988-1 -x c++ /build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar/GVNSink.cpp
1//===- GVNSink.cpp - sink expressions into successors ---------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10/// \file GVNSink.cpp
11/// This pass attempts to sink instructions into successors, reducing static
12/// instruction count and enabling if-conversion.
13///
14/// We use a variant of global value numbering to decide what can be sunk.
15/// Consider:
16///
17/// [ %a1 = add i32 %b, 1 ] [ %c1 = add i32 %d, 1 ]
18/// [ %a2 = xor i32 %a1, 1 ] [ %c2 = xor i32 %c1, 1 ]
19/// \ /
20/// [ %e = phi i32 %a2, %c2 ]
21/// [ add i32 %e, 4 ]
22///
23///
24/// GVN would number %a1 and %c1 differently because they compute different
25/// results - the VN of an instruction is a function of its opcode and the
26/// transitive closure of its operands. This is the key property for hoisting
27/// and CSE.
28///
29/// What we want when sinking however is for a numbering that is a function of
30/// the *uses* of an instruction, which allows us to answer the question "if I
31/// replace %a1 with %c1, will it contribute in an equivalent way to all
32/// successive instructions?". The PostValueTable class in GVN provides this
33/// mapping.
34//
35//===----------------------------------------------------------------------===//
36
37#include "llvm/ADT/ArrayRef.h"
38#include "llvm/ADT/DenseMap.h"
39#include "llvm/ADT/DenseMapInfo.h"
40#include "llvm/ADT/DenseSet.h"
41#include "llvm/ADT/Hashing.h"
42#include "llvm/ADT/None.h"
43#include "llvm/ADT/Optional.h"
44#include "llvm/ADT/PostOrderIterator.h"
45#include "llvm/ADT/STLExtras.h"
46#include "llvm/ADT/SmallPtrSet.h"
47#include "llvm/ADT/SmallVector.h"
48#include "llvm/ADT/Statistic.h"
49#include "llvm/ADT/StringExtras.h"
50#include "llvm/Analysis/GlobalsModRef.h"
51#include "llvm/IR/BasicBlock.h"
52#include "llvm/IR/CFG.h"
53#include "llvm/IR/Constants.h"
54#include "llvm/IR/Function.h"
55#include "llvm/IR/InstrTypes.h"
56#include "llvm/IR/Instruction.h"
57#include "llvm/IR/Instructions.h"
58#include "llvm/IR/PassManager.h"
59#include "llvm/IR/Type.h"
60#include "llvm/IR/Use.h"
61#include "llvm/IR/Value.h"
62#include "llvm/Pass.h"
63#include "llvm/Support/Allocator.h"
64#include "llvm/Support/ArrayRecycler.h"
65#include "llvm/Support/AtomicOrdering.h"
66#include "llvm/Support/Casting.h"
67#include "llvm/Support/Compiler.h"
68#include "llvm/Support/Debug.h"
69#include "llvm/Support/raw_ostream.h"
70#include "llvm/Transforms/Scalar.h"
71#include "llvm/Transforms/Scalar/GVN.h"
72#include "llvm/Transforms/Scalar/GVNExpression.h"
73#include "llvm/Transforms/Utils/BasicBlockUtils.h"
74#include "llvm/Transforms/Utils/Local.h"
75#include <algorithm>
76#include <cassert>
77#include <cstddef>
78#include <cstdint>
79#include <iterator>
80#include <utility>
81
82using namespace llvm;
83
84#define DEBUG_TYPE"gvn-sink" "gvn-sink"
85
86STATISTIC(NumRemoved, "Number of instructions removed")static llvm::Statistic NumRemoved = {"gvn-sink", "NumRemoved"
, "Number of instructions removed", {0}, {false}}
;
87
88namespace llvm {
89namespace GVNExpression {
90
91LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void Expression::dump() const {
92 print(dbgs());
93 dbgs() << "\n";
94}
95
96} // end namespace GVNExpression
97} // end namespace llvm
98
99namespace {
100
101static bool isMemoryInst(const Instruction *I) {
102 return isa<LoadInst>(I) || isa<StoreInst>(I) ||
103 (isa<InvokeInst>(I) && !cast<InvokeInst>(I)->doesNotAccessMemory()) ||
104 (isa<CallInst>(I) && !cast<CallInst>(I)->doesNotAccessMemory());
105}
106
107/// Iterates through instructions in a set of blocks in reverse order from the
108/// first non-terminator. For example (assume all blocks have size n):
109/// LockstepReverseIterator I([B1, B2, B3]);
110/// *I-- = [B1[n], B2[n], B3[n]];
111/// *I-- = [B1[n-1], B2[n-1], B3[n-1]];
112/// *I-- = [B1[n-2], B2[n-2], B3[n-2]];
113/// ...
114///
115/// It continues until all blocks have been exhausted. Use \c getActiveBlocks()
116/// to
117/// determine which blocks are still going and the order they appear in the
118/// list returned by operator*.
119class LockstepReverseIterator {
120 ArrayRef<BasicBlock *> Blocks;
121 SmallSetVector<BasicBlock *, 4> ActiveBlocks;
122 SmallVector<Instruction *, 4> Insts;
123 bool Fail;
124
125public:
126 LockstepReverseIterator(ArrayRef<BasicBlock *> Blocks) : Blocks(Blocks) {
127 reset();
128 }
129
130 void reset() {
131 Fail = false;
132 ActiveBlocks.clear();
133 for (BasicBlock *BB : Blocks)
134 ActiveBlocks.insert(BB);
135 Insts.clear();
136 for (BasicBlock *BB : Blocks) {
137 if (BB->size() <= 1) {
138 // Block wasn't big enough - only contained a terminator.
139 ActiveBlocks.remove(BB);
140 continue;
141 }
142 Insts.push_back(BB->getTerminator()->getPrevNode());
143 }
144 if (Insts.empty())
145 Fail = true;
146 }
147
148 bool isValid() const { return !Fail; }
149 ArrayRef<Instruction *> operator*() const { return Insts; }
150
151 // Note: This needs to return a SmallSetVector as the elements of
152 // ActiveBlocks will be later copied to Blocks using std::copy. The
153 // resultant order of elements in Blocks needs to be deterministic.
154 // Using SmallPtrSet instead causes non-deterministic order while
155 // copying. And we cannot simply sort Blocks as they need to match the
156 // corresponding Values.
157 SmallSetVector<BasicBlock *, 4> &getActiveBlocks() { return ActiveBlocks; }
158
159 void restrictToBlocks(SmallSetVector<BasicBlock *, 4> &Blocks) {
160 for (auto II = Insts.begin(); II != Insts.end();) {
161 if (std::find(Blocks.begin(), Blocks.end(), (*II)->getParent()) ==
162 Blocks.end()) {
163 ActiveBlocks.remove((*II)->getParent());
164 II = Insts.erase(II);
165 } else {
166 ++II;
167 }
168 }
169 }
170
171 void operator--() {
172 if (Fail)
173 return;
174 SmallVector<Instruction *, 4> NewInsts;
175 for (auto *Inst : Insts) {
176 if (Inst == &Inst->getParent()->front())
177 ActiveBlocks.remove(Inst->getParent());
178 else
179 NewInsts.push_back(Inst->getPrevNode());
180 }
181 if (NewInsts.empty()) {
182 Fail = true;
183 return;
184 }
185 Insts = NewInsts;
186 }
187};
188
189//===----------------------------------------------------------------------===//
190
191/// Candidate solution for sinking. There may be different ways to
192/// sink instructions, differing in the number of instructions sunk,
193/// the number of predecessors sunk from and the number of PHIs
194/// required.
195struct SinkingInstructionCandidate {
196 unsigned NumBlocks;
197 unsigned NumInstructions;
198 unsigned NumPHIs;
199 unsigned NumMemoryInsts;
200 int Cost = -1;
201 SmallVector<BasicBlock *, 4> Blocks;
202
203 void calculateCost(unsigned NumOrigPHIs, unsigned NumOrigBlocks) {
204 unsigned NumExtraPHIs = NumPHIs - NumOrigPHIs;
205 unsigned SplitEdgeCost = (NumOrigBlocks > NumBlocks) ? 2 : 0;
206 Cost = (NumInstructions * (NumBlocks - 1)) -
207 (NumExtraPHIs *
208 NumExtraPHIs) // PHIs are expensive, so make sure they're worth it.
209 - SplitEdgeCost;
210 }
211
212 bool operator>(const SinkingInstructionCandidate &Other) const {
213 return Cost > Other.Cost;
214 }
215};
216
217#ifndef NDEBUG
218raw_ostream &operator<<(raw_ostream &OS, const SinkingInstructionCandidate &C) {
219 OS << "<Candidate Cost=" << C.Cost << " #Blocks=" << C.NumBlocks
220 << " #Insts=" << C.NumInstructions << " #PHIs=" << C.NumPHIs << ">";
221 return OS;
222}
223#endif
224
225//===----------------------------------------------------------------------===//
226
227/// Describes a PHI node that may or may not exist. These track the PHIs
228/// that must be created if we sunk a sequence of instructions. It provides
229/// a hash function for efficient equality comparisons.
230class ModelledPHI {
231 SmallVector<Value *, 4> Values;
232 SmallVector<BasicBlock *, 4> Blocks;
233
234public:
235 ModelledPHI() = default;
236
237 ModelledPHI(const PHINode *PN) {
238 // BasicBlock comes first so we sort by basic block pointer order, then by value pointer order.
239 SmallVector<std::pair<BasicBlock *, Value *>, 4> Ops;
240 for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I)
241 Ops.push_back({PN->getIncomingBlock(I), PN->getIncomingValue(I)});
242 std::sort(Ops.begin(), Ops.end());
243 for (auto &P : Ops) {
244 Blocks.push_back(P.first);
245 Values.push_back(P.second);
246 }
247 }
248
249 /// Create a dummy ModelledPHI that will compare unequal to any other ModelledPHI
250 /// without the same ID.
251 /// \note This is specifically for DenseMapInfo - do not use this!
252 static ModelledPHI createDummy(size_t ID) {
253 ModelledPHI M;
254 M.Values.push_back(reinterpret_cast<Value*>(ID));
255 return M;
256 }
257
258 /// Create a PHI from an array of incoming values and incoming blocks.
259 template <typename VArray, typename BArray>
260 ModelledPHI(const VArray &V, const BArray &B) {
261 std::copy(V.begin(), V.end(), std::back_inserter(Values));
262 std::copy(B.begin(), B.end(), std::back_inserter(Blocks));
263 }
264
265 /// Create a PHI from [I[OpNum] for I in Insts].
266 template <typename BArray>
267 ModelledPHI(ArrayRef<Instruction *> Insts, unsigned OpNum, const BArray &B) {
268 std::copy(B.begin(), B.end(), std::back_inserter(Blocks));
269 for (auto *I : Insts)
270 Values.push_back(I->getOperand(OpNum));
271 }
272
273 /// Restrict the PHI's contents down to only \c NewBlocks.
274 /// \c NewBlocks must be a subset of \c this->Blocks.
275 void restrictToBlocks(const SmallSetVector<BasicBlock *, 4> &NewBlocks) {
276 auto BI = Blocks.begin();
277 auto VI = Values.begin();
278 while (BI != Blocks.end()) {
279 assert(VI != Values.end())(static_cast <bool> (VI != Values.end()) ? void (0) : __assert_fail
("VI != Values.end()", "/build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar/GVNSink.cpp"
, 279, __extension__ __PRETTY_FUNCTION__))
;
280 if (std::find(NewBlocks.begin(), NewBlocks.end(), *BI) ==
281 NewBlocks.end()) {
282 BI = Blocks.erase(BI);
283 VI = Values.erase(VI);
284 } else {
285 ++BI;
286 ++VI;
287 }
288 }
289 assert(Blocks.size() == NewBlocks.size())(static_cast <bool> (Blocks.size() == NewBlocks.size())
? void (0) : __assert_fail ("Blocks.size() == NewBlocks.size()"
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar/GVNSink.cpp"
, 289, __extension__ __PRETTY_FUNCTION__))
;
290 }
291
292 ArrayRef<Value *> getValues() const { return Values; }
293
294 bool areAllIncomingValuesSame() const {
295 return llvm::all_of(Values, [&](Value *V) { return V == Values[0]; });
296 }
297
298 bool areAllIncomingValuesSameType() const {
299 return llvm::all_of(
300 Values, [&](Value *V) { return V->getType() == Values[0]->getType(); });
301 }
302
303 bool areAnyIncomingValuesConstant() const {
304 return llvm::any_of(Values, [&](Value *V) { return isa<Constant>(V); });
305 }
306
307 // Hash functor
308 unsigned hash() const {
309 return (unsigned)hash_combine_range(Values.begin(), Values.end());
310 }
311
312 bool operator==(const ModelledPHI &Other) const {
313 return Values == Other.Values && Blocks == Other.Blocks;
314 }
315};
316
317template <typename ModelledPHI> struct DenseMapInfo {
318 static inline ModelledPHI &getEmptyKey() {
319 static ModelledPHI Dummy = ModelledPHI::createDummy(0);
320 return Dummy;
321 }
322
323 static inline ModelledPHI &getTombstoneKey() {
324 static ModelledPHI Dummy = ModelledPHI::createDummy(1);
325 return Dummy;
326 }
327
328 static unsigned getHashValue(const ModelledPHI &V) { return V.hash(); }
329
330 static bool isEqual(const ModelledPHI &LHS, const ModelledPHI &RHS) {
331 return LHS == RHS;
332 }
333};
334
335using ModelledPHISet = DenseSet<ModelledPHI, DenseMapInfo<ModelledPHI>>;
336
337//===----------------------------------------------------------------------===//
338// ValueTable
339//===----------------------------------------------------------------------===//
340// This is a value number table where the value number is a function of the
341// *uses* of a value, rather than its operands. Thus, if VN(A) == VN(B) we know
342// that the program would be equivalent if we replaced A with PHI(A, B).
343//===----------------------------------------------------------------------===//
344
345/// A GVN expression describing how an instruction is used. The operands
346/// field of BasicExpression is used to store uses, not operands.
347///
348/// This class also contains fields for discriminators used when determining
349/// equivalence of instructions with sideeffects.
350class InstructionUseExpr : public GVNExpression::BasicExpression {
351 unsigned MemoryUseOrder = -1;
352 bool Volatile = false;
353
354public:
355 InstructionUseExpr(Instruction *I, ArrayRecycler<Value *> &R,
356 BumpPtrAllocator &A)
357 : GVNExpression::BasicExpression(I->getNumUses()) {
358 allocateOperands(R, A);
359 setOpcode(I->getOpcode());
360 setType(I->getType());
361
362 for (auto &U : I->uses())
363 op_push_back(U.getUser());
364 std::sort(op_begin(), op_end());
365 }
366
367 void setMemoryUseOrder(unsigned MUO) { MemoryUseOrder = MUO; }
368 void setVolatile(bool V) { Volatile = V; }
369
370 hash_code getHashValue() const override {
371 return hash_combine(GVNExpression::BasicExpression::getHashValue(),
372 MemoryUseOrder, Volatile);
373 }
374
375 template <typename Function> hash_code getHashValue(Function MapFn) {
376 hash_code H =
377 hash_combine(getOpcode(), getType(), MemoryUseOrder, Volatile);
378 for (auto *V : operands())
379 H = hash_combine(H, MapFn(V));
380 return H;
381 }
382};
383
384class ValueTable {
385 DenseMap<Value *, uint32_t> ValueNumbering;
386 DenseMap<GVNExpression::Expression *, uint32_t> ExpressionNumbering;
387 DenseMap<size_t, uint32_t> HashNumbering;
388 BumpPtrAllocator Allocator;
389 ArrayRecycler<Value *> Recycler;
390 uint32_t nextValueNumber = 1;
391
392 /// Create an expression for I based on its opcode and its uses. If I
393 /// touches or reads memory, the expression is also based upon its memory
394 /// order - see \c getMemoryUseOrder().
395 InstructionUseExpr *createExpr(Instruction *I) {
396 InstructionUseExpr *E =
4
'E' initialized to a null pointer value
397 new (Allocator) InstructionUseExpr(I, Recycler, Allocator);
398 if (isMemoryInst(I))
5
Taking true branch
399 E->setMemoryUseOrder(getMemoryUseOrder(I));
6
Called C++ object pointer is null
400
401 if (CmpInst *C = dyn_cast<CmpInst>(I)) {
402 CmpInst::Predicate Predicate = C->getPredicate();
403 E->setOpcode((C->getOpcode() << 8) | Predicate);
404 }
405 return E;
406 }
407
408 /// Helper to compute the value number for a memory instruction
409 /// (LoadInst/StoreInst), including checking the memory ordering and
410 /// volatility.
411 template <class Inst> InstructionUseExpr *createMemoryExpr(Inst *I) {
412 if (isStrongerThanUnordered(I->getOrdering()) || I->isAtomic())
1
Assuming the condition is false
2
Taking false branch
413 return nullptr;
414 InstructionUseExpr *E = createExpr(I);
3
Calling 'ValueTable::createExpr'
415 E->setVolatile(I->isVolatile());
416 return E;
417 }
418
419public:
420 ValueTable() = default;
421
422 /// Returns the value number for the specified value, assigning
423 /// it a new number if it did not have one before.
424 uint32_t lookupOrAdd(Value *V) {
425 auto VI = ValueNumbering.find(V);
426 if (VI != ValueNumbering.end())
427 return VI->second;
428
429 if (!isa<Instruction>(V)) {
430 ValueNumbering[V] = nextValueNumber;
431 return nextValueNumber++;
432 }
433
434 Instruction *I = cast<Instruction>(V);
435 InstructionUseExpr *exp = nullptr;
436 switch (I->getOpcode()) {
437 case Instruction::Load:
438 exp = createMemoryExpr(cast<LoadInst>(I));
439 break;
440 case Instruction::Store:
441 exp = createMemoryExpr(cast<StoreInst>(I));
442 break;
443 case Instruction::Call:
444 case Instruction::Invoke:
445 case Instruction::Add:
446 case Instruction::FAdd:
447 case Instruction::Sub:
448 case Instruction::FSub:
449 case Instruction::Mul:
450 case Instruction::FMul:
451 case Instruction::UDiv:
452 case Instruction::SDiv:
453 case Instruction::FDiv:
454 case Instruction::URem:
455 case Instruction::SRem:
456 case Instruction::FRem:
457 case Instruction::Shl:
458 case Instruction::LShr:
459 case Instruction::AShr:
460 case Instruction::And:
461 case Instruction::Or:
462 case Instruction::Xor:
463 case Instruction::ICmp:
464 case Instruction::FCmp:
465 case Instruction::Trunc:
466 case Instruction::ZExt:
467 case Instruction::SExt:
468 case Instruction::FPToUI:
469 case Instruction::FPToSI:
470 case Instruction::UIToFP:
471 case Instruction::SIToFP:
472 case Instruction::FPTrunc:
473 case Instruction::FPExt:
474 case Instruction::PtrToInt:
475 case Instruction::IntToPtr:
476 case Instruction::BitCast:
477 case Instruction::Select:
478 case Instruction::ExtractElement:
479 case Instruction::InsertElement:
480 case Instruction::ShuffleVector:
481 case Instruction::InsertValue:
482 case Instruction::GetElementPtr:
483 exp = createExpr(I);
484 break;
485 default:
486 break;
487 }
488
489 if (!exp) {
490 ValueNumbering[V] = nextValueNumber;
491 return nextValueNumber++;
492 }
493
494 uint32_t e = ExpressionNumbering[exp];
495 if (!e) {
496 hash_code H = exp->getHashValue([=](Value *V) { return lookupOrAdd(V); });
497 auto I = HashNumbering.find(H);
498 if (I != HashNumbering.end()) {
499 e = I->second;
500 } else {
501 e = nextValueNumber++;
502 HashNumbering[H] = e;
503 ExpressionNumbering[exp] = e;
504 }
505 }
506 ValueNumbering[V] = e;
507 return e;
508 }
509
510 /// Returns the value number of the specified value. Fails if the value has
511 /// not yet been numbered.
512 uint32_t lookup(Value *V) const {
513 auto VI = ValueNumbering.find(V);
514 assert(VI != ValueNumbering.end() && "Value not numbered?")(static_cast <bool> (VI != ValueNumbering.end() &&
"Value not numbered?") ? void (0) : __assert_fail ("VI != ValueNumbering.end() && \"Value not numbered?\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar/GVNSink.cpp"
, 514, __extension__ __PRETTY_FUNCTION__))
;
515 return VI->second;
516 }
517
518 /// Removes all value numberings and resets the value table.
519 void clear() {
520 ValueNumbering.clear();
521 ExpressionNumbering.clear();
522 HashNumbering.clear();
523 Recycler.clear(Allocator);
524 nextValueNumber = 1;
525 }
526
527 /// \c Inst uses or touches memory. Return an ID describing the memory state
528 /// at \c Inst such that if getMemoryUseOrder(I1) == getMemoryUseOrder(I2),
529 /// the exact same memory operations happen after I1 and I2.
530 ///
531 /// This is a very hard problem in general, so we use domain-specific
532 /// knowledge that we only ever check for equivalence between blocks sharing a
533 /// single immediate successor that is common, and when determining if I1 ==
534 /// I2 we will have already determined that next(I1) == next(I2). This
535 /// inductive property allows us to simply return the value number of the next
536 /// instruction that defines memory.
537 uint32_t getMemoryUseOrder(Instruction *Inst) {
538 auto *BB = Inst->getParent();
539 for (auto I = std::next(Inst->getIterator()), E = BB->end();
540 I != E && !I->isTerminator(); ++I) {
541 if (!isMemoryInst(&*I))
542 continue;
543 if (isa<LoadInst>(&*I))
544 continue;
545 CallInst *CI = dyn_cast<CallInst>(&*I);
546 if (CI && CI->onlyReadsMemory())
547 continue;
548 InvokeInst *II = dyn_cast<InvokeInst>(&*I);
549 if (II && II->onlyReadsMemory())
550 continue;
551 return lookupOrAdd(&*I);
552 }
553 return 0;
554 }
555};
556
557//===----------------------------------------------------------------------===//
558
559class GVNSink {
560public:
561 GVNSink() = default;
562
563 bool run(Function &F) {
564 DEBUG(dbgs() << "GVNSink: running on function @" << F.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << "GVNSink: running on function @"
<< F.getName() << "\n"; } } while (false)
;
565
566 unsigned NumSunk = 0;
567 ReversePostOrderTraversal<Function*> RPOT(&F);
568 for (auto *N : RPOT)
569 NumSunk += sinkBB(N);
570
571 return NumSunk > 0;
572 }
573
574private:
575 ValueTable VN;
576
577 bool isInstructionBlacklisted(Instruction *I) {
578 // These instructions may change or break semantics if moved.
579 if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) ||
580 I->getType()->isTokenTy())
581 return true;
582 return false;
583 }
584
585 /// The main heuristic function. Analyze the set of instructions pointed to by
586 /// LRI and return a candidate solution if these instructions can be sunk, or
587 /// None otherwise.
588 Optional<SinkingInstructionCandidate> analyzeInstructionForSinking(
589 LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum,
590 ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents);
591
592 /// Create a ModelledPHI for each PHI in BB, adding to PHIs.
593 void analyzeInitialPHIs(BasicBlock *BB, ModelledPHISet &PHIs,
594 SmallPtrSetImpl<Value *> &PHIContents) {
595 for (PHINode &PN : BB->phis()) {
596 auto MPHI = ModelledPHI(&PN);
597 PHIs.insert(MPHI);
598 for (auto *V : MPHI.getValues())
599 PHIContents.insert(V);
600 }
601 }
602
603 /// The main instruction sinking driver. Set up state and try and sink
604 /// instructions into BBEnd from its predecessors.
605 unsigned sinkBB(BasicBlock *BBEnd);
606
607 /// Perform the actual mechanics of sinking an instruction from Blocks into
608 /// BBEnd, which is their only successor.
609 void sinkLastInstruction(ArrayRef<BasicBlock *> Blocks, BasicBlock *BBEnd);
610
611 /// Remove PHIs that all have the same incoming value.
612 void foldPointlessPHINodes(BasicBlock *BB) {
613 auto I = BB->begin();
614 while (PHINode *PN = dyn_cast<PHINode>(I++)) {
615 if (!llvm::all_of(PN->incoming_values(), [&](const Value *V) {
616 return V == PN->getIncomingValue(0);
617 }))
618 continue;
619 if (PN->getIncomingValue(0) != PN)
620 PN->replaceAllUsesWith(PN->getIncomingValue(0));
621 else
622 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
623 PN->eraseFromParent();
624 }
625 }
626};
627
628Optional<SinkingInstructionCandidate> GVNSink::analyzeInstructionForSinking(
629 LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum,
630 ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents) {
631 auto Insts = *LRI;
632 DEBUG(dbgs() << " -- Analyzing instruction set: [\n"; for (auto *Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Analyzing instruction set: [\n"
; for (auto *I : Insts) { I->dump(); } dbgs() << " ]\n"
;; } } while (false)
633 : Insts) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Analyzing instruction set: [\n"
; for (auto *I : Insts) { I->dump(); } dbgs() << " ]\n"
;; } } while (false)
634 I->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Analyzing instruction set: [\n"
; for (auto *I : Insts) { I->dump(); } dbgs() << " ]\n"
;; } } while (false)
635 } dbgs() << " ]\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Analyzing instruction set: [\n"
; for (auto *I : Insts) { I->dump(); } dbgs() << " ]\n"
;; } } while (false)
;
636
637 DenseMap<uint32_t, unsigned> VNums;
638 for (auto *I : Insts) {
639 uint32_t N = VN.lookupOrAdd(I);
640 DEBUG(dbgs() << " VN=" << Twine::utohexstr(N) << " for" << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " VN=" << Twine::utohexstr
(N) << " for" << *I << "\n"; } } while (false
)
;
641 if (N == ~0U)
642 return None;
643 VNums[N]++;
644 }
645 unsigned VNumToSink =
646 std::max_element(VNums.begin(), VNums.end(),
647 [](const std::pair<uint32_t, unsigned> &I,
648 const std::pair<uint32_t, unsigned> &J) {
649 return I.second < J.second;
650 })
651 ->first;
652
653 if (VNums[VNumToSink] == 1)
654 // Can't sink anything!
655 return None;
656
657 // Now restrict the number of incoming blocks down to only those with
658 // VNumToSink.
659 auto &ActivePreds = LRI.getActiveBlocks();
660 unsigned InitialActivePredSize = ActivePreds.size();
661 SmallVector<Instruction *, 4> NewInsts;
662 for (auto *I : Insts) {
663 if (VN.lookup(I) != VNumToSink)
664 ActivePreds.remove(I->getParent());
665 else
666 NewInsts.push_back(I);
667 }
668 for (auto *I : NewInsts)
669 if (isInstructionBlacklisted(I))
670 return None;
671
672 // If we've restricted the incoming blocks, restrict all needed PHIs also
673 // to that set.
674 bool RecomputePHIContents = false;
675 if (ActivePreds.size() != InitialActivePredSize) {
676 ModelledPHISet NewNeededPHIs;
677 for (auto P : NeededPHIs) {
678 P.restrictToBlocks(ActivePreds);
679 NewNeededPHIs.insert(P);
680 }
681 NeededPHIs = NewNeededPHIs;
682 LRI.restrictToBlocks(ActivePreds);
683 RecomputePHIContents = true;
684 }
685
686 // The sunk instruction's results.
687 ModelledPHI NewPHI(NewInsts, ActivePreds);
688
689 // Does sinking this instruction render previous PHIs redundant?
690 if (NeededPHIs.find(NewPHI) != NeededPHIs.end()) {
691 NeededPHIs.erase(NewPHI);
692 RecomputePHIContents = true;
693 }
694
695 if (RecomputePHIContents) {
696 // The needed PHIs have changed, so recompute the set of all needed
697 // values.
698 PHIContents.clear();
699 for (auto &PHI : NeededPHIs)
700 PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
701 }
702
703 // Is this instruction required by a later PHI that doesn't match this PHI?
704 // if so, we can't sink this instruction.
705 for (auto *V : NewPHI.getValues())
706 if (PHIContents.count(V))
707 // V exists in this PHI, but the whole PHI is different to NewPHI
708 // (else it would have been removed earlier). We cannot continue
709 // because this isn't representable.
710 return None;
711
712 // Which operands need PHIs?
713 // FIXME: If any of these fail, we should partition up the candidates to
714 // try and continue making progress.
715 Instruction *I0 = NewInsts[0];
716 for (unsigned OpNum = 0, E = I0->getNumOperands(); OpNum != E; ++OpNum) {
717 ModelledPHI PHI(NewInsts, OpNum, ActivePreds);
718 if (PHI.areAllIncomingValuesSame())
719 continue;
720 if (!canReplaceOperandWithVariable(I0, OpNum))
721 // We can 't create a PHI from this instruction!
722 return None;
723 if (NeededPHIs.count(PHI))
724 continue;
725 if (!PHI.areAllIncomingValuesSameType())
726 return None;
727 // Don't create indirect calls! The called value is the final operand.
728 if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OpNum == E - 1 &&
729 PHI.areAnyIncomingValuesConstant())
730 return None;
731
732 NeededPHIs.reserve(NeededPHIs.size());
733 NeededPHIs.insert(PHI);
734 PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
735 }
736
737 if (isMemoryInst(NewInsts[0]))
738 ++MemoryInstNum;
739
740 SinkingInstructionCandidate Cand;
741 Cand.NumInstructions = ++InstNum;
742 Cand.NumMemoryInsts = MemoryInstNum;
743 Cand.NumBlocks = ActivePreds.size();
744 Cand.NumPHIs = NeededPHIs.size();
745 for (auto *C : ActivePreds)
746 Cand.Blocks.push_back(C);
747
748 return Cand;
749}
750
751unsigned GVNSink::sinkBB(BasicBlock *BBEnd) {
752 DEBUG(dbgs() << "GVNSink: running on basic block ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << "GVNSink: running on basic block "
; BBEnd->printAsOperand(dbgs()); dbgs() << "\n"; } }
while (false)
753 BBEnd->printAsOperand(dbgs()); dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << "GVNSink: running on basic block "
; BBEnd->printAsOperand(dbgs()); dbgs() << "\n"; } }
while (false)
;
754 SmallVector<BasicBlock *, 4> Preds;
755 for (auto *B : predecessors(BBEnd)) {
756 auto *T = B->getTerminator();
757 if (isa<BranchInst>(T) || isa<SwitchInst>(T))
758 Preds.push_back(B);
759 else
760 return 0;
761 }
762 if (Preds.size() < 2)
763 return 0;
764 std::sort(Preds.begin(), Preds.end());
765
766 unsigned NumOrigPreds = Preds.size();
767 // We can only sink instructions through unconditional branches.
768 for (auto I = Preds.begin(); I != Preds.end();) {
769 if ((*I)->getTerminator()->getNumSuccessors() != 1)
770 I = Preds.erase(I);
771 else
772 ++I;
773 }
774
775 LockstepReverseIterator LRI(Preds);
776 SmallVector<SinkingInstructionCandidate, 4> Candidates;
777 unsigned InstNum = 0, MemoryInstNum = 0;
778 ModelledPHISet NeededPHIs;
779 SmallPtrSet<Value *, 4> PHIContents;
780 analyzeInitialPHIs(BBEnd, NeededPHIs, PHIContents);
781 unsigned NumOrigPHIs = NeededPHIs.size();
782
783 while (LRI.isValid()) {
784 auto Cand = analyzeInstructionForSinking(LRI, InstNum, MemoryInstNum,
785 NeededPHIs, PHIContents);
786 if (!Cand)
787 break;
788 Cand->calculateCost(NumOrigPHIs, Preds.size());
789 Candidates.emplace_back(*Cand);
790 --LRI;
791 }
792
793 std::stable_sort(
794 Candidates.begin(), Candidates.end(),
795 [](const SinkingInstructionCandidate &A,
796 const SinkingInstructionCandidate &B) { return A > B; });
797 DEBUG(dbgs() << " -- Sinking candidates:\n"; for (auto &Cdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Sinking candidates:\n"; for
(auto &C : Candidates) dbgs() << " " << C <<
"\n";; } } while (false)
798 : Candidates) dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Sinking candidates:\n"; for
(auto &C : Candidates) dbgs() << " " << C <<
"\n";; } } while (false)
799 << " " << C << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Sinking candidates:\n"; for
(auto &C : Candidates) dbgs() << " " << C <<
"\n";; } } while (false)
;
800
801 // Pick the top candidate, as long it is positive!
802 if (Candidates.empty() || Candidates.front().Cost <= 0)
803 return 0;
804 auto C = Candidates.front();
805
806 DEBUG(dbgs() << " -- Sinking: " << C << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Sinking: " << C <<
"\n"; } } while (false)
;
807 BasicBlock *InsertBB = BBEnd;
808 if (C.Blocks.size() < NumOrigPreds) {
809 DEBUG(dbgs() << " -- Splitting edge to "; BBEnd->printAsOperand(dbgs());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Splitting edge to "; BBEnd
->printAsOperand(dbgs()); dbgs() << "\n"; } } while (
false)
810 dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- Splitting edge to "; BBEnd
->printAsOperand(dbgs()); dbgs() << "\n"; } } while (
false)
;
811 InsertBB = SplitBlockPredecessors(BBEnd, C.Blocks, ".gvnsink.split");
812 if (!InsertBB) {
813 DEBUG(dbgs() << " -- FAILED to split edge!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("gvn-sink")) { dbgs() << " -- FAILED to split edge!\n"
; } } while (false)
;
814 // Edge couldn't be split.
815 return 0;
816 }
817 }
818
819 for (unsigned I = 0; I < C.NumInstructions; ++I)
820 sinkLastInstruction(C.Blocks, InsertBB);
821
822 return C.NumInstructions;
823}
824
825void GVNSink::sinkLastInstruction(ArrayRef<BasicBlock *> Blocks,
826 BasicBlock *BBEnd) {
827 SmallVector<Instruction *, 4> Insts;
828 for (BasicBlock *BB : Blocks)
829 Insts.push_back(BB->getTerminator()->getPrevNode());
830 Instruction *I0 = Insts.front();
831
832 SmallVector<Value *, 4> NewOperands;
833 for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) {
834 bool NeedPHI = llvm::any_of(Insts, [&I0, O](const Instruction *I) {
835 return I->getOperand(O) != I0->getOperand(O);
836 });
837 if (!NeedPHI) {
838 NewOperands.push_back(I0->getOperand(O));
839 continue;
840 }
841
842 // Create a new PHI in the successor block and populate it.
843 auto *Op = I0->getOperand(O);
844 assert(!Op->getType()->isTokenTy() && "Can't PHI tokens!")(static_cast <bool> (!Op->getType()->isTokenTy() &&
"Can't PHI tokens!") ? void (0) : __assert_fail ("!Op->getType()->isTokenTy() && \"Can't PHI tokens!\""
, "/build/llvm-toolchain-snapshot-7~svn326246/lib/Transforms/Scalar/GVNSink.cpp"
, 844, __extension__ __PRETTY_FUNCTION__))
;
845 auto *PN = PHINode::Create(Op->getType(), Insts.size(),
846 Op->getName() + ".sink", &BBEnd->front());
847 for (auto *I : Insts)
848 PN->addIncoming(I->getOperand(O), I->getParent());
849 NewOperands.push_back(PN);
850 }
851
852 // Arbitrarily use I0 as the new "common" instruction; remap its operands
853 // and move it to the start of the successor block.
854 for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O)
855 I0->getOperandUse(O).set(NewOperands[O]);
856 I0->moveBefore(&*BBEnd->getFirstInsertionPt());
857
858 // Update metadata and IR flags.
859 for (auto *I : Insts)
860 if (I != I0) {
861 combineMetadataForCSE(I0, I);
862 I0->andIRFlags(I);
863 }
864
865 for (auto *I : Insts)
866 if (I != I0)
867 I->replaceAllUsesWith(I0);
868 foldPointlessPHINodes(BBEnd);
869
870 // Finally nuke all instructions apart from the common instruction.
871 for (auto *I : Insts)
872 if (I != I0)
873 I->eraseFromParent();
874
875 NumRemoved += Insts.size() - 1;
876}
877
878////////////////////////////////////////////////////////////////////////////////
879// Pass machinery / boilerplate
880
881class GVNSinkLegacyPass : public FunctionPass {
882public:
883 static char ID;
884
885 GVNSinkLegacyPass() : FunctionPass(ID) {
886 initializeGVNSinkLegacyPassPass(*PassRegistry::getPassRegistry());
887 }
888
889 bool runOnFunction(Function &F) override {
890 if (skipFunction(F))
891 return false;
892 GVNSink G;
893 return G.run(F);
894 }
895
896 void getAnalysisUsage(AnalysisUsage &AU) const override {
897 AU.addPreserved<GlobalsAAWrapperPass>();
898 }
899};
900
901} // end anonymous namespace
902
903PreservedAnalyses GVNSinkPass::run(Function &F, FunctionAnalysisManager &AM) {
904 GVNSink G;
905 if (!G.run(F))
906 return PreservedAnalyses::all();
907
908 PreservedAnalyses PA;
909 PA.preserve<GlobalsAA>();
910 return PA;
911}
912
913char GVNSinkLegacyPass::ID = 0;
914
915INITIALIZE_PASS_BEGIN(GVNSinkLegacyPass, "gvn-sink",static void *initializeGVNSinkLegacyPassPassOnce(PassRegistry
&Registry) {
916 "Early GVN sinking of Expressions", false, false)static void *initializeGVNSinkLegacyPassPassOnce(PassRegistry
&Registry) {
917INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
918INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry);
919INITIALIZE_PASS_END(GVNSinkLegacyPass, "gvn-sink",PassInfo *PI = new PassInfo( "Early GVN sinking of Expressions"
, "gvn-sink", &GVNSinkLegacyPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<GVNSinkLegacyPass>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeGVNSinkLegacyPassPassFlag; void llvm::initializeGVNSinkLegacyPassPass
(PassRegistry &Registry) { llvm::call_once(InitializeGVNSinkLegacyPassPassFlag
, initializeGVNSinkLegacyPassPassOnce, std::ref(Registry)); }
920 "Early GVN sinking of Expressions", false, false)PassInfo *PI = new PassInfo( "Early GVN sinking of Expressions"
, "gvn-sink", &GVNSinkLegacyPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<GVNSinkLegacyPass>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeGVNSinkLegacyPassPassFlag; void llvm::initializeGVNSinkLegacyPassPass
(PassRegistry &Registry) { llvm::call_once(InitializeGVNSinkLegacyPassPassFlag
, initializeGVNSinkLegacyPassPassOnce, std::ref(Registry)); }
921
922FunctionPass *llvm::createGVNSinkPass() { return new GVNSinkLegacyPass(); }