Coverage Report

Created: 2019-07-24 05:18

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