Coverage Report

Created: 2019-07-24 05:18

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