Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/GVNHoist.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
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 hoists expressions from branches to a common dominator. It uses
10
// GVN (global value numbering) to discover expressions computing the same
11
// values. The primary goals of code-hoisting are:
12
// 1. To reduce the code size.
13
// 2. In some cases reduce critical path (by exposing more ILP).
14
//
15
// The algorithm factors out the reachability of values such that multiple
16
// queries to find reachability of values are fast. This is based on finding the
17
// ANTIC points in the CFG which do not change during hoisting. The ANTIC points
18
// are basically the dominance-frontiers in the inverse graph. So we introduce a
19
// data structure (CHI nodes) to keep track of values flowing out of a basic
20
// block. We only do this for values with multiple occurrences in the function
21
// as they are the potential hoistable candidates. This approach allows us to
22
// hoist instructions to a basic block with more than two successors, as well as
23
// deal with infinite loops in a trivial way.
24
//
25
// Limitations: This pass does not hoist fully redundant expressions because
26
// they are already handled by GVN-PRE. It is advisable to run gvn-hoist before
27
// and after gvn-pre because gvn-pre creates opportunities for more instructions
28
// to be hoisted.
29
//
30
// Hoisting may affect the performance in some cases. To mitigate that, hoisting
31
// is disabled in the following cases.
32
// 1. Scalars across calls.
33
// 2. geps when corresponding load/store cannot be hoisted.
34
//===----------------------------------------------------------------------===//
35
36
#include "llvm/ADT/DenseMap.h"
37
#include "llvm/ADT/DenseSet.h"
38
#include "llvm/ADT/STLExtras.h"
39
#include "llvm/ADT/SmallPtrSet.h"
40
#include "llvm/ADT/SmallVector.h"
41
#include "llvm/ADT/Statistic.h"
42
#include "llvm/ADT/iterator_range.h"
43
#include "llvm/Analysis/AliasAnalysis.h"
44
#include "llvm/Analysis/GlobalsModRef.h"
45
#include "llvm/Analysis/IteratedDominanceFrontier.h"
46
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
47
#include "llvm/Analysis/MemorySSA.h"
48
#include "llvm/Analysis/MemorySSAUpdater.h"
49
#include "llvm/Analysis/PostDominators.h"
50
#include "llvm/Transforms/Utils/Local.h"
51
#include "llvm/Analysis/ValueTracking.h"
52
#include "llvm/IR/Argument.h"
53
#include "llvm/IR/BasicBlock.h"
54
#include "llvm/IR/CFG.h"
55
#include "llvm/IR/Constants.h"
56
#include "llvm/IR/Dominators.h"
57
#include "llvm/IR/Function.h"
58
#include "llvm/IR/InstrTypes.h"
59
#include "llvm/IR/Instruction.h"
60
#include "llvm/IR/Instructions.h"
61
#include "llvm/IR/IntrinsicInst.h"
62
#include "llvm/IR/Intrinsics.h"
63
#include "llvm/IR/LLVMContext.h"
64
#include "llvm/IR/PassManager.h"
65
#include "llvm/IR/Use.h"
66
#include "llvm/IR/User.h"
67
#include "llvm/IR/Value.h"
68
#include "llvm/Pass.h"
69
#include "llvm/Support/Casting.h"
70
#include "llvm/Support/CommandLine.h"
71
#include "llvm/Support/Debug.h"
72
#include "llvm/Support/raw_ostream.h"
73
#include "llvm/Transforms/Scalar.h"
74
#include "llvm/Transforms/Scalar/GVN.h"
75
#include <algorithm>
76
#include <cassert>
77
#include <iterator>
78
#include <memory>
79
#include <utility>
80
#include <vector>
81
82
using namespace llvm;
83
84
#define DEBUG_TYPE "gvn-hoist"
85
86
STATISTIC(NumHoisted, "Number of instructions hoisted");
87
STATISTIC(NumRemoved, "Number of instructions removed");
88
STATISTIC(NumLoadsHoisted, "Number of loads hoisted");
89
STATISTIC(NumLoadsRemoved, "Number of loads removed");
90
STATISTIC(NumStoresHoisted, "Number of stores hoisted");
91
STATISTIC(NumStoresRemoved, "Number of stores removed");
92
STATISTIC(NumCallsHoisted, "Number of calls hoisted");
93
STATISTIC(NumCallsRemoved, "Number of calls removed");
94
95
static cl::opt<int>
96
    MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1),
97
                        cl::desc("Max number of instructions to hoist "
98
                                 "(default unlimited = -1)"));
99
100
static cl::opt<int> MaxNumberOfBBSInPath(
101
    "gvn-hoist-max-bbs", cl::Hidden, cl::init(4),
102
    cl::desc("Max number of basic blocks on the path between "
103
             "hoisting locations (default = 4, unlimited = -1)"));
104
105
static cl::opt<int> MaxDepthInBB(
106
    "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
107
    cl::desc("Hoist instructions from the beginning of the BB up to the "
108
             "maximum specified depth (default = 100, unlimited = -1)"));
109
110
static cl::opt<int>
111
    MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
112
                   cl::desc("Maximum length of dependent chains to hoist "
113
                            "(default = 10, unlimited = -1)"));
114
115
namespace llvm {
116
117
using BBSideEffectsSet = DenseMap<const BasicBlock *, bool>;
118
using SmallVecInsn = SmallVector<Instruction *, 4>;
119
using SmallVecImplInsn = SmallVectorImpl<Instruction *>;
120
121
// Each element of a hoisting list contains the basic block where to hoist and
122
// a list of instructions to be hoisted.
123
using HoistingPointInfo = std::pair<BasicBlock *, SmallVecInsn>;
124
125
using HoistingPointList = SmallVector<HoistingPointInfo, 4>;
126
127
// A map from a pair of VNs to all the instructions with those VNs.
128
using VNType = std::pair<unsigned, unsigned>;
129
130
using VNtoInsns = DenseMap<VNType, SmallVector<Instruction *, 4>>;
131
132
// CHI keeps information about values flowing out of a basic block.  It is
133
// similar to PHI but in the inverse graph, and used for outgoing values on each
134
// edge. For conciseness, it is computed only for instructions with multiple
135
// occurrences in the CFG because they are the only hoistable candidates.
136
//     A (CHI[{V, B, I1}, {V, C, I2}]
137
//  /     \
138
// /       \
139
// B(I1)  C (I2)
140
// The Value number for both I1 and I2 is V, the CHI node will save the
141
// instruction as well as the edge where the value is flowing to.
142
struct CHIArg {
143
  VNType VN;
144
145
  // Edge destination (shows the direction of flow), may not be where the I is.
146
  BasicBlock *Dest;
147
148
  // The instruction (VN) which uses the values flowing out of CHI.
149
  Instruction *I;
150
151
1.63k
  bool operator==(const CHIArg &A) { return VN == A.VN; }
152
1.63k
  bool operator!=(const CHIArg &A) { return !(*this == A); }
153
};
154
155
using CHIIt = SmallVectorImpl<CHIArg>::iterator;
156
using CHIArgs = iterator_range<CHIIt>;
157
using OutValuesType = DenseMap<BasicBlock *, SmallVector<CHIArg, 2>>;
158
using InValuesType =
159
    DenseMap<BasicBlock *, SmallVector<std::pair<VNType, Instruction *>, 2>>;
160
161
// An invalid value number Used when inserting a single value number into
162
// VNtoInsns.
163
enum : unsigned { InvalidVN = ~2U };
164
165
// Records all scalar instructions candidate for code hoisting.
166
class InsnInfo {
167
  VNtoInsns VNtoScalars;
168
169
public:
170
  // Inserts I and its value number in VNtoScalars.
171
839
  void insert(Instruction *I, GVN::ValueTable &VN) {
172
839
    // Scalar instruction.
173
839
    unsigned V = VN.lookupOrAdd(I);
174
839
    VNtoScalars[{V, InvalidVN}].push_back(I);
175
839
  }
176
177
131
  const VNtoInsns &getVNTable() const { return VNtoScalars; }
178
};
179
180
// Records all load instructions candidate for code hoisting.
181
class LoadInfo {
182
  VNtoInsns VNtoLoads;
183
184
public:
185
  // Insert Load and the value number of its memory address in VNtoLoads.
186
379
  void insert(LoadInst *Load, GVN::ValueTable &VN) {
187
379
    if (Load->isSimple()) {
188
379
      unsigned V = VN.lookupOrAdd(Load->getPointerOperand());
189
379
      VNtoLoads[{V, InvalidVN}].push_back(Load);
190
379
    }
191
379
  }
192
193
131
  const VNtoInsns &getVNTable() const { return VNtoLoads; }
194
};
195
196
// Records all store instructions candidate for code hoisting.
197
class StoreInfo {
198
  VNtoInsns VNtoStores;
199
200
public:
201
  // Insert the Store and a hash number of the store address and the stored
202
  // value in VNtoStores.
203
231
  void insert(StoreInst *Store, GVN::ValueTable &VN) {
204
231
    if (!Store->isSimple())
205
0
      return;
206
231
    // Hash the store address and the stored value.
207
231
    Value *Ptr = Store->getPointerOperand();
208
231
    Value *Val = Store->getValueOperand();
209
231
    VNtoStores[{VN.lookupOrAdd(Ptr), VN.lookupOrAdd(Val)}].push_back(Store);
210
231
  }
211
212
131
  const VNtoInsns &getVNTable() const { return VNtoStores; }
213
};
214
215
// Records all call instructions candidate for code hoisting.
216
class CallInfo {
217
  VNtoInsns VNtoCallsScalars;
218
  VNtoInsns VNtoCallsLoads;
219
  VNtoInsns VNtoCallsStores;
220
221
public:
222
  // Insert Call and its value numbering in one of the VNtoCalls* containers.
223
20
  void insert(CallInst *Call, GVN::ValueTable &VN) {
224
20
    // A call that doesNotAccessMemory is handled as a Scalar,
225
20
    // onlyReadsMemory will be handled as a Load instruction,
226
20
    // all other calls will be handled as stores.
227
20
    unsigned V = VN.lookupOrAdd(Call);
228
20
    auto Entry = std::make_pair(V, InvalidVN);
229
20
230
20
    if (Call->doesNotAccessMemory())
231
13
      VNtoCallsScalars[Entry].push_back(Call);
232
7
    else if (Call->onlyReadsMemory())
233
7
      VNtoCallsLoads[Entry].push_back(Call);
234
0
    else
235
0
      VNtoCallsStores[Entry].push_back(Call);
236
20
  }
237
238
131
  const VNtoInsns &getScalarVNTable() const { return VNtoCallsScalars; }
239
131
  const VNtoInsns &getLoadVNTable() const { return VNtoCallsLoads; }
240
131
  const VNtoInsns &getStoreVNTable() const { return VNtoCallsStores; }
241
};
242
243
117
static void combineKnownMetadata(Instruction *ReplInst, Instruction *I) {
244
117
  static const unsigned KnownIDs[] = {
245
117
      LLVMContext::MD_tbaa,           LLVMContext::MD_alias_scope,
246
117
      LLVMContext::MD_noalias,        LLVMContext::MD_range,
247
117
      LLVMContext::MD_fpmath,         LLVMContext::MD_invariant_load,
248
117
      LLVMContext::MD_invariant_group, LLVMContext::MD_access_group};
249
117
  combineMetadata(ReplInst, I, KnownIDs, true);
250
117
}
251
252
// This pass hoists common computations across branches sharing common
253
// dominator. The primary goal is to reduce the code size, and in some
254
// cases reduce critical path (by exposing more ILP).
255
class GVNHoist {
256
public:
257
  GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA,
258
           MemoryDependenceResults *MD, MemorySSA *MSSA)
259
      : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA),
260
71
        MSSAUpdater(llvm::make_unique<MemorySSAUpdater>(MSSA)) {}
261
262
71
  bool run(Function &F) {
263
71
    NumFuncArgs = F.arg_size();
264
71
    VN.setDomTree(DT);
265
71
    VN.setAliasAnalysis(AA);
266
71
    VN.setMemDep(MD);
267
71
    bool Res = false;
268
71
    // Perform DFS Numbering of instructions.
269
71
    unsigned BBI = 0;
270
344
    for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
271
344
      DFSNumber[BB] = ++BBI;
272
344
      unsigned I = 0;
273
344
      for (auto &Inst : *BB)
274
1.25k
        DFSNumber[&Inst] = ++I;
275
344
    }
276
71
277
71
    int ChainLength = 0;
278
71
279
71
    // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
280
131
    while (true) {
281
131
      if (MaxChainLength != -1 && ++ChainLength >= MaxChainLength)
282
0
        return Res;
283
131
284
131
      auto HoistStat = hoistExpressions(F);
285
131
      if (HoistStat.first + HoistStat.second == 0)
286
71
        return Res;
287
60
288
60
      if (HoistStat.second > 0)
289
41
        // To address a limitation of the current GVN, we need to rerun the
290
41
        // hoisting after we hoisted loads or stores in order to be able to
291
41
        // hoist all scalars dependent on the hoisted ld/st.
292
41
        VN.clear();
293
60
294
60
      Res = true;
295
60
    }
296
71
297
71
    
return Res0
;
298
71
  }
299
300
  // Copied from NewGVN.cpp
301
  // This function provides global ranking of operations so that we can place
302
  // them in a canonical order.  Note that rank alone is not necessarily enough
303
  // for a complete ordering, as constants all have the same rank.  However,
304
  // generally, we will simplify an operation with all constants so that it
305
  // doesn't matter what order they appear in.
306
5.41k
  unsigned int rank(const Value *V) const {
307
5.41k
    // Prefer constants to undef to anything else
308
5.41k
    // Undef is a constant, have to check it first.
309
5.41k
    // Prefer smaller constants to constantexprs
310
5.41k
    if (isa<ConstantExpr>(V))
311
0
      return 2;
312
5.41k
    if (isa<UndefValue>(V))
313
0
      return 1;
314
5.41k
    if (isa<Constant>(V))
315
0
      return 0;
316
5.41k
    else if (auto *A = dyn_cast<Argument>(V))
317
0
      return 3 + A->getArgNo();
318
5.41k
319
5.41k
    // Need to shift the instruction DFS by number of arguments + 3 to account
320
5.41k
    // for the constant and argument ranking above.
321
5.41k
    auto Result = DFSNumber.lookup(V);
322
5.41k
    if (Result > 0)
323
5.41k
      return 4 + NumFuncArgs + Result;
324
0
    // Unreachable or something else, just return a really large number.
325
0
    return ~0;
326
0
  }
327
328
private:
329
  GVN::ValueTable VN;
330
  DominatorTree *DT;
331
  PostDominatorTree *PDT;
332
  AliasAnalysis *AA;
333
  MemoryDependenceResults *MD;
334
  MemorySSA *MSSA;
335
  std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
336
  DenseMap<const Value *, unsigned> DFSNumber;
337
  BBSideEffectsSet BBSideEffects;
338
  DenseSet<const BasicBlock *> HoistBarrier;
339
  SmallVector<BasicBlock *, 32> IDFBlocks;
340
  unsigned NumFuncArgs;
341
  const bool HoistingGeps = false;
342
343
  enum InsKind { Unknown, Scalar, Load, Store };
344
345
  // Return true when there are exception handling in BB.
346
799
  bool hasEH(const BasicBlock *BB) {
347
799
    auto It = BBSideEffects.find(BB);
348
799
    if (It != BBSideEffects.end())
349
633
      return It->second;
350
166
351
166
    if (BB->isEHPad() || 
BB->hasAddressTaken()164
) {
352
2
      BBSideEffects[BB] = true;
353
2
      return true;
354
2
    }
355
164
356
164
    if (BB->getTerminator()->mayThrow()) {
357
0
      BBSideEffects[BB] = true;
358
0
      return true;
359
0
    }
360
164
361
164
    BBSideEffects[BB] = false;
362
164
    return false;
363
164
  }
364
365
  // Return true when a successor of BB dominates A.
366
0
  bool successorDominate(const BasicBlock *BB, const BasicBlock *A) {
367
0
    for (const BasicBlock *Succ : successors(BB))
368
0
      if (DT->dominates(Succ, A))
369
0
        return true;
370
0
371
0
    return false;
372
0
  }
373
374
  // Return true when I1 appears before I2 in the instructions of BB.
375
54
  bool firstInBB(const Instruction *I1, const Instruction *I2) {
376
54
    assert(I1->getParent() == I2->getParent());
377
54
    unsigned I1DFS = DFSNumber.lookup(I1);
378
54
    unsigned I2DFS = DFSNumber.lookup(I2);
379
54
    assert(I1DFS && I2DFS);
380
54
    return I1DFS < I2DFS;
381
54
  }
382
383
  // Return true when there are memory uses of Def in BB.
384
  bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
385
54
                    const BasicBlock *BB) {
386
54
    const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
387
54
    if (!Acc)
388
0
      return false;
389
54
390
54
    Instruction *OldPt = Def->getMemoryInst();
391
54
    const BasicBlock *OldBB = OldPt->getParent();
392
54
    const BasicBlock *NewBB = NewPt->getParent();
393
54
    bool ReachedNewPt = false;
394
54
395
54
    for (const MemoryAccess &MA : *Acc)
396
86
      if (const MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
397
10
        Instruction *Insn = MU->getMemoryInst();
398
10
399
10
        // Do not check whether MU aliases Def when MU occurs after OldPt.
400
10
        if (BB == OldBB && firstInBB(OldPt, Insn))
401
9
          break;
402
1
403
1
        // Do not check whether MU aliases Def when MU occurs before NewPt.
404
1
        if (BB == NewBB) {
405
0
          if (!ReachedNewPt) {
406
0
            if (firstInBB(Insn, NewPt))
407
0
              continue;
408
0
            ReachedNewPt = true;
409
0
          }
410
0
        }
411
1
        if (MemorySSAUtil::defClobbersUseOrDef(Def, MU, *AA))
412
1
          return true;
413
1
      }
414
54
415
54
    
return false53
;
416
54
  }
417
418
  bool hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
419
342
                   int &NBBsOnAllPaths) {
420
342
    // Stop walk once the limit is reached.
421
342
    if (NBBsOnAllPaths == 0)
422
1
      return true;
423
341
424
341
    // Impossible to hoist with exceptions on the path.
425
341
    if (hasEH(BB))
426
8
      return true;
427
333
428
333
    // No such instruction after HoistBarrier in a basic block was
429
333
    // selected for hoisting so instructions selected within basic block with
430
333
    // a hoist barrier can be hoisted.
431
333
    if ((BB != SrcBB) && 
HoistBarrier.count(BB)21
)
432
2
      return true;
433
331
434
331
    return false;
435
331
  }
436
437
  // Return true when there are exception handling or loads of memory Def
438
  // between Def and NewPt.  This function is only called for stores: Def is
439
  // the MemoryDef of the store to be hoisted.
440
441
  // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
442
  // return true when the counter NBBsOnAllPaths reaces 0, except when it is
443
  // initialized to -1 which is unlimited.
444
  bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
445
54
                          int &NBBsOnAllPaths) {
446
54
    const BasicBlock *NewBB = NewPt->getParent();
447
54
    const BasicBlock *OldBB = Def->getBlock();
448
54
    assert(DT->dominates(NewBB, OldBB) && "invalid path");
449
54
    assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
450
54
           "def does not dominate new hoisting point");
451
54
452
54
    // Walk all basic blocks reachable in depth-first iteration on the inverse
453
54
    // CFG from OldBB to NewBB. These blocks are all the blocks that may be
454
54
    // executed between the execution of NewBB and OldBB. Hoisting an expression
455
54
    // from OldBB into NewBB has to be safe on all execution paths.
456
160
    for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
457
107
      const BasicBlock *BB = *I;
458
107
      if (BB == NewBB) {
459
53
        // Stop traversal when reaching HoistPt.
460
53
        I.skipChildren();
461
53
        continue;
462
53
      }
463
54
464
54
      if (hasEHhelper(BB, OldBB, NBBsOnAllPaths))
465
0
        return true;
466
54
467
54
      // Check that we do not move a store past loads.
468
54
      if (hasMemoryUse(NewPt, Def, BB))
469
1
        return true;
470
53
471
53
      // -1 is unlimited number of blocks on all paths.
472
53
      if (NBBsOnAllPaths != -1)
473
53
        --NBBsOnAllPaths;
474
53
475
53
      ++I;
476
53
    }
477
54
478
54
    
return false53
;
479
54
  }
480
481
  // Return true when there are exception handling between HoistPt and BB.
482
  // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
483
  // return true when the counter NBBsOnAllPaths reaches 0, except when it is
484
  // initialized to -1 which is unlimited.
485
  bool hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
486
265
                   int &NBBsOnAllPaths) {
487
265
    assert(DT->dominates(HoistPt, SrcBB) && "Invalid path");
488
265
489
265
    // Walk all basic blocks reachable in depth-first iteration on
490
265
    // the inverse CFG from BBInsn to NewHoistPt. These blocks are all the
491
265
    // blocks that may be executed between the execution of NewHoistPt and
492
265
    // BBInsn. Hoisting an expression from BBInsn into NewHoistPt has to be safe
493
265
    // on all execution paths.
494
796
    for (auto I = idf_begin(SrcBB), E = idf_end(SrcBB); I != E;) {
495
542
      const BasicBlock *BB = *I;
496
542
      if (BB == HoistPt) {
497
254
        // Stop traversal when reaching NewHoistPt.
498
254
        I.skipChildren();
499
254
        continue;
500
254
      }
501
288
502
288
      if (hasEHhelper(BB, SrcBB, NBBsOnAllPaths))
503
11
        return true;
504
277
505
277
      // -1 is unlimited number of blocks on all paths.
506
277
      if (NBBsOnAllPaths != -1)
507
277
        --NBBsOnAllPaths;
508
277
509
277
      ++I;
510
277
    }
511
265
512
265
    
return false254
;
513
265
  }
514
515
  // Return true when it is safe to hoist a memory load or store U from OldPt
516
  // to NewPt.
517
  bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
518
231
                       MemoryUseOrDef *U, InsKind K, int &NBBsOnAllPaths) {
519
231
    // In place hoisting is safe.
520
231
    if (NewPt == OldPt)
521
0
      return true;
522
231
523
231
    const BasicBlock *NewBB = NewPt->getParent();
524
231
    const BasicBlock *OldBB = OldPt->getParent();
525
231
    const BasicBlock *UBB = U->getBlock();
526
231
527
231
    // Check for dependences on the Memory SSA.
528
231
    MemoryAccess *D = U->getDefiningAccess();
529
231
    BasicBlock *DBB = D->getBlock();
530
231
    if (DT->properlyDominates(NewBB, DBB))
531
54
      // Cannot move the load or store to NewBB above its definition in DBB.
532
54
      return false;
533
177
534
177
    if (NewBB == DBB && 
!MSSA->isLiveOnEntryDef(D)131
)
535
54
      if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
536
44
        if (!firstInBB(UD->getMemoryInst(), NewPt))
537
2
          // Cannot move the load or store to NewPt above its definition in D.
538
2
          return false;
539
175
540
175
    // Check for unsafe hoistings due to side effects.
541
175
    if (K == InsKind::Store) {
542
54
      if (hasEHOrLoadsOnPath(NewPt, dyn_cast<MemoryDef>(U), NBBsOnAllPaths))
543
1
        return false;
544
121
    } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
545
0
      return false;
546
174
547
174
    if (UBB == NewBB) {
548
0
      if (DT->properlyDominates(DBB, NewBB))
549
0
        return true;
550
0
      assert(UBB == DBB);
551
0
      assert(MSSA->locallyDominates(D, U));
552
0
    }
553
174
554
174
    // No side effects: it is safe to hoist.
555
174
    return true;
556
174
  }
557
558
  // Return true when it is safe to hoist scalar instructions from all blocks in
559
  // WL to HoistBB.
560
  bool safeToHoistScalar(const BasicBlock *HoistBB, const BasicBlock *BB,
561
144
                         int &NBBsOnAllPaths) {
562
144
    return !hasEHOnPath(HoistBB, BB, NBBsOnAllPaths);
563
144
  }
564
565
  // In the inverse CFG, the dominance frontier of basic block (BB) is the
566
  // point where ANTIC needs to be computed for instructions which are going
567
  // to be hoisted. Since this point does not change during gvn-hoist,
568
  // we compute it only once (on demand).
569
  // The ides is inspired from:
570
  // "Partial Redundancy Elimination in SSA Form"
571
  // ROBERT KENNEDY, SUN CHAN, SHIN-MING LIU, RAYMOND LO, PENG TU and FRED CHOW
572
  // They use similar idea in the forward graph to find fully redundant and
573
  // partially redundant expressions, here it is used in the inverse graph to
574
  // find fully anticipable instructions at merge point (post-dominator in
575
  // the inverse CFG).
576
  // Returns the edge via which an instruction in BB will get the values from.
577
578
  // Returns true when the values are flowing out to each edge.
579
245
  bool valueAnticipable(CHIArgs C, Instruction *TI) const {
580
245
    if (TI->getNumSuccessors() > (unsigned)size(C))
581
124
      return false; // Not enough args in this CHI.
582
121
583
243
    
for (auto CHI : C)121
{
584
243
      BasicBlock *Dest = CHI.Dest;
585
243
      // Find if all the edges have values flowing out of BB.
586
243
      bool Found = llvm::any_of(
587
366
          successors(TI), [Dest](const BasicBlock *BB) { return BB == Dest; });
588
243
      if (!Found)
589
0
        return false;
590
243
    }
591
121
    return true;
592
121
  }
593
594
  // Check if it is safe to hoist values tracked by CHI in the range
595
  // [Begin, End) and accumulate them in Safe.
596
  void checkSafety(CHIArgs C, BasicBlock *BB, InsKind K,
597
245
                   SmallVectorImpl<CHIArg> &Safe) {
598
245
    int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
599
510
    for (auto CHI : C) {
600
510
      Instruction *Insn = CHI.I;
601
510
      if (!Insn) // No instruction was inserted in this CHI.
602
135
        continue;
603
375
      if (K == InsKind::Scalar) {
604
144
        if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))
605
133
          Safe.push_back(CHI);
606
231
      } else {
607
231
        MemoryUseOrDef *UD = MSSA->getMemoryAccess(Insn);
608
231
        if (safeToHoistLdSt(BB->getTerminator(), Insn, UD, K, NumBBsOnAllPaths))
609
174
          Safe.push_back(CHI);
610
231
      }
611
375
    }
612
245
  }
613
614
  using RenameStackType = DenseMap<VNType, SmallVector<Instruction *, 2>>;
615
616
  // Push all the VNs corresponding to BB into RenameStack.
617
  void fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
618
3.99k
                       RenameStackType &RenameStack) {
619
3.99k
    auto it1 = ValueBBs.find(BB);
620
3.99k
    if (it1 != ValueBBs.end()) {
621
260
      // Iterate in reverse order to keep lower ranked values on the top.
622
458
      for (std::pair<VNType, Instruction *> &VI : reverse(it1->second)) {
623
458
        // Get the value of instruction I
624
458
        LLVM_DEBUG(dbgs() << "\nPushing on stack: " << *VI.second);
625
458
        RenameStack[VI.first].push_back(VI.second);
626
458
      }
627
260
    }
628
3.99k
  }
629
630
  void fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
631
3.99k
                   RenameStackType &RenameStack) {
632
3.99k
    // For each *predecessor* (because Post-DOM) of BB check if it has a CHI
633
4.34k
    for (auto Pred : predecessors(BB)) {
634
4.34k
      auto P = CHIBBs.find(Pred);
635
4.34k
      if (P == CHIBBs.end()) {
636
4.02k
        continue;
637
4.02k
      }
638
315
      LLVM_DEBUG(dbgs() << "\nLooking at CHIs in: " << Pred->getName(););
639
315
      // A CHI is found (BB -> Pred is an edge in the CFG)
640
315
      // Pop the stack until Top(V) = Ve.
641
315
      auto &VCHI = P->second;
642
999
      for (auto It = VCHI.begin(), E = VCHI.end(); It != E;) {
643
684
        CHIArg &C = *It;
644
684
        if (!C.Dest) {
645
490
          auto si = RenameStack.find(C.VN);
646
490
          // The Basic Block where CHI is must dominate the value we want to
647
490
          // track in a CHI. In the PDom walk, there can be values in the
648
490
          // stack which are not control dependent e.g., nested loop.
649
490
          if (si != RenameStack.end() && 
si->second.size()439
&&
650
490
              
DT->properlyDominates(Pred, si->second.back()->getParent())384
) {
651
375
            C.Dest = BB;                     // Assign the edge
652
375
            C.I = si->second.pop_back_val(); // Assign the argument
653
375
            LLVM_DEBUG(dbgs()
654
375
                       << "\nCHI Inserted in BB: " << C.Dest->getName() << *C.I
655
375
                       << ", VN: " << C.VN.first << ", " << C.VN.second);
656
375
          }
657
490
          // Move to next CHI of a different value
658
490
          It = std::find_if(It, VCHI.end(),
659
1.03k
                            [It](CHIArg &A) { return A != *It; });
660
490
        } else
661
194
          ++It;
662
684
      }
663
315
    }
664
3.99k
  }
665
666
  // Walk the post-dominator tree top-down and use a stack for each value to
667
  // store the last value you see. When you hit a CHI from a given edge, the
668
  // value to use as the argument is at the top of the stack, add the value to
669
  // CHI and pop.
670
786
  void insertCHI(InValuesType &ValueBBs, OutValuesType &CHIBBs) {
671
786
    auto Root = PDT->getNode(nullptr);
672
786
    if (!Root)
673
0
      return;
674
786
    // Depth first walk on PDom tree to fill the CHIargs at each PDF.
675
786
    RenameStackType RenameStack;
676
4.77k
    for (auto Node : depth_first(Root)) {
677
4.77k
      BasicBlock *BB = Node->getBlock();
678
4.77k
      if (!BB)
679
786
        continue;
680
3.99k
681
3.99k
      // Collect all values in BB and push to stack.
682
3.99k
      fillRenameStack(BB, ValueBBs, RenameStack);
683
3.99k
684
3.99k
      // Fill outgoing values in each CHI corresponding to BB.
685
3.99k
      fillChiArgs(BB, CHIBBs, RenameStack);
686
3.99k
    }
687
786
  }
688
689
  // Walk all the CHI-nodes to find ones which have a empty-entry and remove
690
  // them Then collect all the instructions which are safe to hoist and see if
691
  // they form a list of anticipable values. OutValues contains CHIs
692
  // corresponding to each basic block.
693
  void findHoistableCandidates(OutValuesType &CHIBBs, InsKind K,
694
786
                               HoistingPointList &HPL) {
695
786
    auto cmpVN = [](const CHIArg &A, const CHIArg &B) 
{ return A.VN < B.VN; }490
;
696
786
697
786
    // CHIArgs now have the outgoing values, so check for anticipability and
698
786
    // accumulate hoistable candidates in HPL.
699
786
    for (std::pair<BasicBlock *, SmallVector<CHIArg, 2>> &A : CHIBBs) {
700
153
      BasicBlock *BB = A.first;
701
153
      SmallVectorImpl<CHIArg> &CHIs = A.second;
702
153
      // Vector of PHIs contains PHIs for different instructions.
703
153
      // Sort the args according to their VNs, such that identical
704
153
      // instructions are together.
705
153
      llvm::stable_sort(CHIs, cmpVN);
706
153
      auto TI = BB->getTerminator();
707
153
      auto B = CHIs.begin();
708
153
      // [PreIt, PHIIt) form a range of CHIs which have identical VNs.
709
153
      auto PHIIt = std::find_if(CHIs.begin(), CHIs.end(),
710
372
                                 [B](CHIArg &A) { return A != *B; });
711
153
      auto PrevIt = CHIs.begin();
712
398
      while (PrevIt != PHIIt) {
713
245
        // Collect values which satisfy safety checks.
714
245
        SmallVector<CHIArg, 2> Safe;
715
245
        // We check for safety first because there might be multiple values in
716
245
        // the same path, some of which are not safe to be hoisted, but overall
717
245
        // each edge has at least one value which can be hoisted, making the
718
245
        // value anticipable along that path.
719
245
        checkSafety(make_range(PrevIt, PHIIt), BB, K, Safe);
720
245
721
245
        // List of safe values should be anticipable at TI.
722
245
        if (valueAnticipable(make_range(Safe.begin(), Safe.end()), TI)) {
723
121
          HPL.push_back({BB, SmallVecInsn()});
724
121
          SmallVecInsn &V = HPL.back().second;
725
121
          for (auto B : Safe)
726
243
            V.push_back(B.I);
727
121
        }
728
245
729
245
        // Check other VNs
730
245
        PrevIt = PHIIt;
731
245
        PHIIt = std::find_if(PrevIt, CHIs.end(),
732
245
                             [PrevIt](CHIArg &A) 
{ return A != *PrevIt; }230
);
733
245
      }
734
153
    }
735
786
  }
736
737
  // Compute insertion points for each values which can be fully anticipated at
738
  // a dominator. HPL contains all such values.
739
  void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
740
786
                              InsKind K) {
741
786
    // Sort VNs based on their rankings
742
786
    std::vector<VNType> Ranks;
743
1.20k
    for (const auto &Entry : Map) {
744
1.20k
      Ranks.push_back(Entry.first);
745
1.20k
    }
746
786
747
786
    // TODO: Remove fully-redundant expressions.
748
786
    // Get instruction from the Map, assume that all the Instructions
749
786
    // with same VNs have same rank (this is an approximation).
750
2.70k
    llvm::sort(Ranks, [this, &Map](const VNType &r1, const VNType &r2) {
751
2.70k
      return (rank(*Map.lookup(r1).begin()) < rank(*Map.lookup(r2).begin()));
752
2.70k
    });
753
786
754
786
    // - Sort VNs according to their rank, and start with lowest ranked VN
755
786
    // - Take a VN and for each instruction with same VN
756
786
    //   - Find the dominance frontier in the inverse graph (PDF)
757
786
    //   - Insert the chi-node at PDF
758
786
    // - Remove the chi-nodes with missing entries
759
786
    // - Remove values from CHI-nodes which do not truly flow out, e.g.,
760
786
    //   modified along the path.
761
786
    // - Collect the remaining values that are still anticipable
762
786
    SmallVector<BasicBlock *, 2> IDFBlocks;
763
786
    ReverseIDFCalculator IDFs(*PDT);
764
786
    OutValuesType OutValue;
765
786
    InValuesType InValue;
766
1.20k
    for (const auto &R : Ranks) {
767
1.20k
      const SmallVecInsn &V = Map.lookup(R);
768
1.20k
      if (V.size() < 2)
769
1.01k
        continue;
770
198
      const VNType &VN = R;
771
198
      SmallPtrSet<BasicBlock *, 2> VNBlocks;
772
458
      for (auto &I : V) {
773
458
        BasicBlock *BBI = I->getParent();
774
458
        if (!hasEH(BBI))
775
452
          VNBlocks.insert(BBI);
776
458
      }
777
198
      // Compute the Post Dominance Frontiers of each basic block
778
198
      // The dominance frontier of a live block X in the reverse
779
198
      // control graph is the set of blocks upon which X is control
780
198
      // dependent. The following sequence computes the set of blocks
781
198
      // which currently have dead terminators that are control
782
198
      // dependence sources of a block which is in NewLiveBlocks.
783
198
      IDFs.setDefiningBlocks(VNBlocks);
784
198
      IDFBlocks.clear();
785
198
      IDFs.calculate(IDFBlocks);
786
198
787
198
      // Make a map of BB vs instructions to be hoisted.
788
656
      for (unsigned i = 0; i < V.size(); 
++i458
) {
789
458
        InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
790
458
      }
791
198
      // Insert empty CHI node for this VN. This is used to factor out
792
198
      // basic blocks where the ANTIC can potentially change.
793
274
      for (auto IDFB : IDFBlocks) {
794
944
        for (unsigned i = 0; i < V.size(); 
++i670
) {
795
670
          CHIArg C = {VN, nullptr, nullptr};
796
670
           // Ignore spurious PDFs.
797
670
          if (DT->properlyDominates(IDFB, V[i]->getParent())) {
798
510
            OutValue[IDFB].push_back(C);
799
510
            LLVM_DEBUG(dbgs() << "\nInsertion a CHI for BB: " << IDFB->getName()
800
510
                              << ", for Insn: " << *V[i]);
801
510
          }
802
670
        }
803
274
      }
804
198
    }
805
786
806
786
    // Insert CHI args at each PDF to iterate on factored graph of
807
786
    // control dependence.
808
786
    insertCHI(InValue, OutValue);
809
786
    // Using the CHI args inserted at each PDF, find fully anticipable values.
810
786
    findHoistableCandidates(OutValue, K, HPL);
811
786
  }
812
813
  // Return true when all operands of Instr are available at insertion point
814
  // HoistPt. When limiting the number of hoisted expressions, one could hoist
815
  // a load without hoisting its access function. So before hoisting any
816
  // expression, make sure that all its operands are available at insert point.
817
  bool allOperandsAvailable(const Instruction *I,
818
121
                            const BasicBlock *HoistPt) const {
819
121
    for (const Use &Op : I->operands())
820
186
      if (const auto *Inst = dyn_cast<Instruction>(&Op))
821
106
        if (!DT->dominates(Inst->getParent(), HoistPt))
822
21
          return false;
823
121
824
121
    
return true100
;
825
121
  }
826
827
  // Same as allOperandsAvailable with recursive check for GEP operands.
828
  bool allGepOperandsAvailable(const Instruction *I,
829
23
                               const BasicBlock *HoistPt) const {
830
23
    for (const Use &Op : I->operands())
831
60
      if (const auto *Inst = dyn_cast<Instruction>(&Op))
832
15
        if (!DT->dominates(Inst->getParent(), HoistPt)) {
833
2
          if (const GetElementPtrInst *GepOp =
834
2
                  dyn_cast<GetElementPtrInst>(Inst)) {
835
2
            if (!allGepOperandsAvailable(GepOp, HoistPt))
836
0
              return false;
837
0
            // Gep is available if all operands of GepOp are available.
838
0
          } else {
839
0
            // Gep is not available if it has operands other than GEPs that are
840
0
            // defined in blocks not dominating HoistPt.
841
0
            return false;
842
0
          }
843
2
        }
844
23
    return true;
845
23
  }
846
847
  // Make all operands of the GEP available.
848
  void makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
849
                         const SmallVecInsn &InstructionsToHoist,
850
19
                         Instruction *Gep) const {
851
19
    assert(allGepOperandsAvailable(Gep, HoistPt) &&
852
19
           "GEP operands not available");
853
19
854
19
    Instruction *ClonedGep = Gep->clone();
855
71
    for (unsigned i = 0, e = Gep->getNumOperands(); i != e; 
++i52
)
856
52
      if (Instruction *Op = dyn_cast<Instruction>(Gep->getOperand(i))) {
857
13
        // Check whether the operand is already available.
858
13
        if (DT->dominates(Op->getParent(), HoistPt))
859
11
          continue;
860
2
861
2
        // As a GEP can refer to other GEPs, recursively make all the operands
862
2
        // of this GEP available at HoistPt.
863
2
        if (GetElementPtrInst *GepOp = dyn_cast<GetElementPtrInst>(Op))
864
2
          makeGepsAvailable(ClonedGep, HoistPt, InstructionsToHoist, GepOp);
865
2
      }
866
19
867
19
    // Copy Gep and replace its uses in Repl with ClonedGep.
868
19
    ClonedGep->insertBefore(HoistPt->getTerminator());
869
19
870
19
    // Conservatively discard any optimization hints, they may differ on the
871
19
    // other paths.
872
19
    ClonedGep->dropUnknownNonDebugMetadata();
873
19
874
19
    // If we have optimization hints which agree with each other along different
875
19
    // paths, preserve them.
876
38
    for (const Instruction *OtherInst : InstructionsToHoist) {
877
38
      const GetElementPtrInst *OtherGep;
878
38
      if (auto *OtherLd = dyn_cast<LoadInst>(OtherInst))
879
24
        OtherGep = cast<GetElementPtrInst>(OtherLd->getPointerOperand());
880
14
      else
881
14
        OtherGep = cast<GetElementPtrInst>(
882
14
            cast<StoreInst>(OtherInst)->getPointerOperand());
883
38
      ClonedGep->andIRFlags(OtherGep);
884
38
    }
885
19
886
19
    // Replace uses of Gep with ClonedGep in Repl.
887
19
    Repl->replaceUsesOfWith(Gep, ClonedGep);
888
19
  }
889
890
117
  void updateAlignment(Instruction *I, Instruction *Repl) {
891
117
    if (auto *ReplacementLoad = dyn_cast<LoadInst>(Repl)) {
892
43
      ReplacementLoad->setAlignment(
893
43
          std::min(ReplacementLoad->getAlignment(),
894
43
                   cast<LoadInst>(I)->getAlignment()));
895
43
      ++NumLoadsRemoved;
896
74
    } else if (auto *ReplacementStore = dyn_cast<StoreInst>(Repl)) {
897
16
      ReplacementStore->setAlignment(
898
16
          std::min(ReplacementStore->getAlignment(),
899
16
                   cast<StoreInst>(I)->getAlignment()));
900
16
      ++NumStoresRemoved;
901
58
    } else if (auto *ReplacementAlloca = dyn_cast<AllocaInst>(Repl)) {
902
0
      ReplacementAlloca->setAlignment(
903
0
          std::max(ReplacementAlloca->getAlignment(),
904
0
                   cast<AllocaInst>(I)->getAlignment()));
905
58
    } else if (isa<CallInst>(Repl)) {
906
3
      ++NumCallsRemoved;
907
3
    }
908
117
  }
909
910
  // Remove all the instructions in Candidates and replace their usage with Repl.
911
  // Returns the number of instructions removed.
912
  unsigned rauw(const SmallVecInsn &Candidates, Instruction *Repl,
913
116
                MemoryUseOrDef *NewMemAcc) {
914
116
    unsigned NR = 0;
915
233
    for (Instruction *I : Candidates) {
916
233
      if (I != Repl) {
917
117
        ++NR;
918
117
        updateAlignment(I, Repl);
919
117
        if (NewMemAcc) {
920
59
          // Update the uses of the old MSSA access with NewMemAcc.
921
59
          MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
922
59
          OldMA->replaceAllUsesWith(NewMemAcc);
923
59
          MSSAUpdater->removeMemoryAccess(OldMA);
924
59
        }
925
117
926
117
        Repl->andIRFlags(I);
927
117
        combineKnownMetadata(Repl, I);
928
117
        I->replaceAllUsesWith(Repl);
929
117
        // Also invalidate the Alias Analysis cache.
930
117
        MD->removeInstruction(I);
931
117
        I->eraseFromParent();
932
117
      }
933
233
    }
934
116
    return NR;
935
116
  }
936
937
  // Replace all Memory PHI usage with NewMemAcc.
938
58
  void raMPHIuw(MemoryUseOrDef *NewMemAcc) {
939
58
    SmallPtrSet<MemoryPhi *, 4> UsePhis;
940
58
    for (User *U : NewMemAcc->users())
941
24
      if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(U))
942
16
        UsePhis.insert(Phi);
943
58
944
58
    for (MemoryPhi *Phi : UsePhis) {
945
11
      auto In = Phi->incoming_values();
946
18
      if (
llvm::all_of(In, [&](Use &U) 11
{ return U == NewMemAcc; })) {
947
5
        Phi->replaceAllUsesWith(NewMemAcc);
948
5
        MSSAUpdater->removeMemoryAccess(Phi);
949
5
      }
950
11
    }
951
58
  }
952
953
  // Remove all other instructions and replace them with Repl.
954
  unsigned removeAndReplace(const SmallVecInsn &Candidates, Instruction *Repl,
955
116
                            BasicBlock *DestBB, bool MoveAccess) {
956
116
    MemoryUseOrDef *NewMemAcc = MSSA->getMemoryAccess(Repl);
957
116
    if (MoveAccess && NewMemAcc) {
958
58
        // The definition of this ld/st will not change: ld/st hoisting is
959
58
        // legal when the ld/st is not moved past its current definition.
960
58
        MSSAUpdater->moveToPlace(NewMemAcc, DestBB, MemorySSA::End);
961
58
    }
962
116
963
116
    // Replace all other instructions with Repl with memory access NewMemAcc.
964
116
    unsigned NR = rauw(Candidates, Repl, NewMemAcc);
965
116
966
116
    // Remove MemorySSA phi nodes with the same arguments.
967
116
    if (NewMemAcc)
968
58
      raMPHIuw(NewMemAcc);
969
116
    return NR;
970
116
  }
971
972
  // In the case Repl is a load or a store, we make all their GEPs
973
  // available: GEPs are not hoisted by default to avoid the address
974
  // computations to be hoisted without the associated load or store.
975
  bool makeGepOperandsAvailable(Instruction *Repl, BasicBlock *HoistPt,
976
21
                                const SmallVecInsn &InstructionsToHoist) const {
977
21
    // Check whether the GEP of a ld/st can be synthesized at HoistPt.
978
21
    GetElementPtrInst *Gep = nullptr;
979
21
    Instruction *Val = nullptr;
980
21
    if (auto *Ld = dyn_cast<LoadInst>(Repl)) {
981
10
      Gep = dyn_cast<GetElementPtrInst>(Ld->getPointerOperand());
982
11
    } else if (auto *St = dyn_cast<StoreInst>(Repl)) {
983
10
      Gep = dyn_cast<GetElementPtrInst>(St->getPointerOperand());
984
10
      Val = dyn_cast<Instruction>(St->getValueOperand());
985
10
      // Check that the stored value is available.
986
10
      if (Val) {
987
7
        if (isa<GetElementPtrInst>(Val)) {
988
5
          // Check whether we can compute the GEP at HoistPt.
989
5
          if (!allGepOperandsAvailable(Val, HoistPt))
990
0
            return false;
991
2
        } else if (!DT->dominates(Val->getParent(), HoistPt))
992
0
          return false;
993
21
      }
994
10
    }
995
21
996
21
    // Check whether we can compute the Gep at HoistPt.
997
21
    if (!Gep || 
!allGepOperandsAvailable(Gep, HoistPt)16
)
998
5
      return false;
999
16
1000
16
    makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Gep);
1001
16
1002
16
    if (Val && 
isa<GetElementPtrInst>(Val)3
)
1003
1
      makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Val);
1004
16
1005
16
    return true;
1006
16
  }
1007
1008
131
  std::pair<unsigned, unsigned> hoist(HoistingPointList &HPL) {
1009
131
    unsigned NI = 0, NL = 0, NS = 0, NC = 0, NR = 0;
1010
131
    for (const HoistingPointInfo &HP : HPL) {
1011
121
      // Find out whether we already have one of the instructions in HoistPt,
1012
121
      // in which case we do not have to move it.
1013
121
      BasicBlock *DestBB = HP.first;
1014
121
      const SmallVecInsn &InstructionsToHoist = HP.second;
1015
121
      Instruction *Repl = nullptr;
1016
121
      for (Instruction *I : InstructionsToHoist)
1017
243
        if (I->getParent() == DestBB)
1018
0
          // If there are two instructions in HoistPt to be hoisted in place:
1019
0
          // update Repl to be the first one, such that we can rename the uses
1020
0
          // of the second based on the first.
1021
0
          if (!Repl || firstInBB(I, Repl))
1022
0
            Repl = I;
1023
121
1024
121
      // Keep track of whether we moved the instruction so we know whether we
1025
121
      // should move the MemoryAccess.
1026
121
      bool MoveAccess = true;
1027
121
      if (Repl) {
1028
0
        // Repl is already in HoistPt: it remains in place.
1029
0
        assert(allOperandsAvailable(Repl, DestBB) &&
1030
0
               "instruction depends on operands that are not available");
1031
0
        MoveAccess = false;
1032
121
      } else {
1033
121
        // When we do not find Repl in HoistPt, select the first in the list
1034
121
        // and move it to HoistPt.
1035
121
        Repl = InstructionsToHoist.front();
1036
121
1037
121
        // We can move Repl in HoistPt only when all operands are available.
1038
121
        // The order in which hoistings are done may influence the availability
1039
121
        // of operands.
1040
121
        if (!allOperandsAvailable(Repl, DestBB)) {
1041
21
          // When HoistingGeps there is nothing more we can do to make the
1042
21
          // operands available: just continue.
1043
21
          if (HoistingGeps)
1044
0
            continue;
1045
21
1046
21
          // When not HoistingGeps we need to copy the GEPs.
1047
21
          if (!makeGepOperandsAvailable(Repl, DestBB, InstructionsToHoist))
1048
5
            continue;
1049
116
        }
1050
116
1051
116
        // Move the instruction at the end of HoistPt.
1052
116
        Instruction *Last = DestBB->getTerminator();
1053
116
        MD->removeInstruction(Repl);
1054
116
        Repl->moveBefore(Last);
1055
116
1056
116
        DFSNumber[Repl] = DFSNumber[Last]++;
1057
116
      }
1058
121
1059
121
      NR += removeAndReplace(InstructionsToHoist, Repl, DestBB, MoveAccess);
1060
116
1061
116
      if (isa<LoadInst>(Repl))
1062
43
        ++NL;
1063
73
      else if (isa<StoreInst>(Repl))
1064
15
        ++NS;
1065
58
      else if (isa<CallInst>(Repl))
1066
3
        ++NC;
1067
55
      else // Scalar
1068
55
        ++NI;
1069
116
    }
1070
131
1071
131
    NumHoisted += NL + NS + NC + NI;
1072
131
    NumRemoved += NR;
1073
131
    NumLoadsHoisted += NL;
1074
131
    NumStoresHoisted += NS;
1075
131
    NumCallsHoisted += NC;
1076
131
    return {NI, NL + NC + NS};
1077
131
  }
1078
1079
  // Hoist all expressions. Returns Number of scalars hoisted
1080
  // and number of non-scalars hoisted.
1081
131
  std::pair<unsigned, unsigned> hoistExpressions(Function &F) {
1082
131
    InsnInfo II;
1083
131
    LoadInfo LI;
1084
131
    StoreInfo SI;
1085
131
    CallInfo CI;
1086
665
    for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1087
665
      int InstructionNb = 0;
1088
2.36k
      for (Instruction &I1 : *BB) {
1089
2.36k
        // If I1 cannot guarantee progress, subsequent instructions
1090
2.36k
        // in BB cannot be hoisted anyways.
1091
2.36k
        if (!isGuaranteedToTransferExecutionToSuccessor(&I1)) {
1092
210
          HoistBarrier.insert(BB);
1093
210
          break;
1094
210
        }
1095
2.15k
        // Only hoist the first instructions in BB up to MaxDepthInBB. Hoisting
1096
2.15k
        // deeper may increase the register pressure and compilation time.
1097
2.15k
        if (MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
1098
0
          break;
1099
2.15k
1100
2.15k
        // Do not value number terminator instructions.
1101
2.15k
        if (I1.isTerminator())
1102
446
          break;
1103
1.71k
1104
1.71k
        if (auto *Load = dyn_cast<LoadInst>(&I1))
1105
379
          LI.insert(Load, VN);
1106
1.33k
        else if (auto *Store = dyn_cast<StoreInst>(&I1))
1107
231
          SI.insert(Store, VN);
1108
1.10k
        else if (auto *Call = dyn_cast<CallInst>(&I1)) {
1109
31
          if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
1110
9
            if (isa<DbgInfoIntrinsic>(Intr) ||
1111
9
                Intr->getIntrinsicID() == Intrinsic::assume ||
1112
9
                Intr->getIntrinsicID() == Intrinsic::sideeffect)
1113
2
              continue;
1114
29
          }
1115
29
          if (Call->mayHaveSideEffects())
1116
1
            break;
1117
28
1118
28
          if (Call->isConvergent())
1119
8
            break;
1120
20
1121
20
          CI.insert(Call, VN);
1122
1.06k
        } else if (HoistingGeps || !isa<GetElementPtrInst>(&I1))
1123
839
          // Do not hoist scalars past calls that may write to memory because
1124
839
          // that could result in spills later. geps are handled separately.
1125
839
          // TODO: We can relax this for targets like AArch64 as they have more
1126
839
          // registers than X86.
1127
839
          II.insert(&I1, VN);
1128
1.71k
      }
1129
665
    }
1130
131
1131
131
    HoistingPointList HPL;
1132
131
    computeInsertionPoints(II.getVNTable(), HPL, InsKind::Scalar);
1133
131
    computeInsertionPoints(LI.getVNTable(), HPL, InsKind::Load);
1134
131
    computeInsertionPoints(SI.getVNTable(), HPL, InsKind::Store);
1135
131
    computeInsertionPoints(CI.getScalarVNTable(), HPL, InsKind::Scalar);
1136
131
    computeInsertionPoints(CI.getLoadVNTable(), HPL, InsKind::Load);
1137
131
    computeInsertionPoints(CI.getStoreVNTable(), HPL, InsKind::Store);
1138
131
    return hoist(HPL);
1139
131
  }
1140
};
1141
1142
class GVNHoistLegacyPass : public FunctionPass {
1143
public:
1144
  static char ID;
1145
1146
35
  GVNHoistLegacyPass() : FunctionPass(ID) {
1147
35
    initializeGVNHoistLegacyPassPass(*PassRegistry::getPassRegistry());
1148
35
  }
1149
1150
71
  bool runOnFunction(Function &F) override {
1151
71
    if (skipFunction(F))
1152
0
      return false;
1153
71
    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1154
71
    auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1155
71
    auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1156
71
    auto &MD = getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
1157
71
    auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
1158
71
1159
71
    GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
1160
71
    return G.run(F);
1161
71
  }
1162
1163
35
  void getAnalysisUsage(AnalysisUsage &AU) const override {
1164
35
    AU.addRequired<DominatorTreeWrapperPass>();
1165
35
    AU.addRequired<PostDominatorTreeWrapperPass>();
1166
35
    AU.addRequired<AAResultsWrapperPass>();
1167
35
    AU.addRequired<MemoryDependenceWrapperPass>();
1168
35
    AU.addRequired<MemorySSAWrapperPass>();
1169
35
    AU.addPreserved<DominatorTreeWrapperPass>();
1170
35
    AU.addPreserved<MemorySSAWrapperPass>();
1171
35
    AU.addPreserved<GlobalsAAWrapperPass>();
1172
35
  }
1173
};
1174
1175
} // end namespace llvm
1176
1177
0
PreservedAnalyses GVNHoistPass::run(Function &F, FunctionAnalysisManager &AM) {
1178
0
  DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
1179
0
  PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
1180
0
  AliasAnalysis &AA = AM.getResult<AAManager>(F);
1181
0
  MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
1182
0
  MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
1183
0
  GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
1184
0
  if (!G.run(F))
1185
0
    return PreservedAnalyses::all();
1186
0
1187
0
  PreservedAnalyses PA;
1188
0
  PA.preserve<DominatorTreeAnalysis>();
1189
0
  PA.preserve<MemorySSAAnalysis>();
1190
0
  PA.preserve<GlobalsAA>();
1191
0
  return PA;
1192
0
}
1193
1194
char GVNHoistLegacyPass::ID = 0;
1195
1196
36.0k
INITIALIZE_PASS_BEGIN(GVNHoistLegacyPass, "gvn-hoist",
1197
36.0k
                      "Early GVN Hoisting of Expressions", false, false)
1198
36.0k
INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
1199
36.0k
INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
1200
36.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1201
36.0k
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
1202
36.0k
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1203
36.0k
INITIALIZE_PASS_END(GVNHoistLegacyPass, "gvn-hoist",
1204
                    "Early GVN Hoisting of Expressions", false, false)
1205
1206
1
FunctionPass *llvm::createGVNHoistPass() { return new GVNHoistLegacyPass(); }