Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Transforms/Scalar/SROA.h
Line
Count
Source
1
//===- SROA.h - Scalar Replacement Of Aggregates ----------------*- C++ -*-===//
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
/// \file
10
/// This file provides the interface for LLVM's Scalar Replacement of
11
/// Aggregates pass. This pass provides both aggregate splitting and the
12
/// primary SSA formation used in the compiler.
13
///
14
//===----------------------------------------------------------------------===//
15
16
#ifndef LLVM_TRANSFORMS_SCALAR_SROA_H
17
#define LLVM_TRANSFORMS_SCALAR_SROA_H
18
19
#include "llvm/ADT/SetVector.h"
20
#include "llvm/ADT/SmallVector.h"
21
#include "llvm/IR/PassManager.h"
22
#include "llvm/Support/Compiler.h"
23
#include <vector>
24
25
namespace llvm {
26
27
class AllocaInst;
28
class AssumptionCache;
29
class DominatorTree;
30
class Function;
31
class Instruction;
32
class LLVMContext;
33
class PHINode;
34
class SelectInst;
35
class Use;
36
37
/// A private "module" namespace for types and utilities used by SROA. These
38
/// are implementation details and should not be used by clients.
39
namespace sroa LLVM_LIBRARY_VISIBILITY {
40
41
class AllocaSliceRewriter;
42
class AllocaSlices;
43
class Partition;
44
class SROALegacyPass;
45
46
} // end namespace sroa
47
48
/// \brief An optimization pass providing Scalar Replacement of Aggregates.
49
///
50
/// This pass takes allocations which can be completely analyzed (that is, they
51
/// don't escape) and tries to turn them into scalar SSA values. There are
52
/// a few steps to this process.
53
///
54
/// 1) It takes allocations of aggregates and analyzes the ways in which they
55
///    are used to try to split them into smaller allocations, ideally of
56
///    a single scalar data type. It will split up memcpy and memset accesses
57
///    as necessary and try to isolate individual scalar accesses.
58
/// 2) It will transform accesses into forms which are suitable for SSA value
59
///    promotion. This can be replacing a memset with a scalar store of an
60
///    integer value, or it can involve speculating operations on a PHI or
61
///    select to be a PHI or select of the results.
62
/// 3) Finally, this will try to detect a pattern of accesses which map cleanly
63
///    onto insert and extract operations on a vector value, and convert them to
64
///    this form. By doing so, it will enable promotion of vector aggregates to
65
///    SSA vector values.
66
class SROA : public PassInfoMixin<SROA> {
67
  LLVMContext *C = nullptr;
68
  DominatorTree *DT = nullptr;
69
  AssumptionCache *AC = nullptr;
70
71
  /// \brief Worklist of alloca instructions to simplify.
72
  ///
73
  /// Each alloca in the function is added to this. Each new alloca formed gets
74
  /// added to it as well to recursively simplify unless that alloca can be
75
  /// directly promoted. Finally, each time we rewrite a use of an alloca other
76
  /// the one being actively rewritten, we add it back onto the list if not
77
  /// already present to ensure it is re-visited.
78
  SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist;
79
80
  /// \brief A collection of instructions to delete.
81
  /// We try to batch deletions to simplify code and make things a bit more
82
  /// efficient.
83
  SetVector<Instruction *, SmallVector<Instruction *, 8>> DeadInsts;
84
85
  /// \brief Post-promotion worklist.
86
  ///
87
  /// Sometimes we discover an alloca which has a high probability of becoming
88
  /// viable for SROA after a round of promotion takes place. In those cases,
89
  /// the alloca is enqueued here for re-processing.
90
  ///
91
  /// Note that we have to be very careful to clear allocas out of this list in
92
  /// the event they are deleted.
93
  SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> PostPromotionWorklist;
94
95
  /// \brief A collection of alloca instructions we can directly promote.
96
  std::vector<AllocaInst *> PromotableAllocas;
97
98
  /// \brief A worklist of PHIs to speculate prior to promoting allocas.
99
  ///
100
  /// All of these PHIs have been checked for the safety of speculation and by
101
  /// being speculated will allow promoting allocas currently in the promotable
102
  /// queue.
103
  SetVector<PHINode *, SmallVector<PHINode *, 2>> SpeculatablePHIs;
104
105
  /// \brief A worklist of select instructions to speculate prior to promoting
106
  /// allocas.
107
  ///
108
  /// All of these select instructions have been checked for the safety of
109
  /// speculation and by being speculated will allow promoting allocas
110
  /// currently in the promotable queue.
111
  SetVector<SelectInst *, SmallVector<SelectInst *, 2>> SpeculatableSelects;
112
113
public:
114
36.5k
  SROA() = default;
115
116
  /// \brief Run the pass over the function.
117
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
118
119
private:
120
  friend class sroa::AllocaSliceRewriter;
121
  friend class sroa::SROALegacyPass;
122
123
  /// Helper used by both the public run method and by the legacy pass.
124
  PreservedAnalyses runImpl(Function &F, DominatorTree &RunDT,
125
                            AssumptionCache &RunAC);
126
127
  bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS);
128
  AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS,
129
                               sroa::Partition &P);
130
  bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS);
131
  bool runOnAlloca(AllocaInst &AI);
132
  void clobberUse(Use &U);
133
  void deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
134
  bool promoteAllocas(Function &F);
135
};
136
137
} // end namespace llvm
138
139
#endif // LLVM_TRANSFORMS_SCALAR_SROA_H