1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
#pragma once
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
//===- SROA.h - Scalar Replacement Of Aggregates ----------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
/// \file
/// This file provides the interface for LLVM's Scalar Replacement of
/// Aggregates pass. This pass provides both aggregate splitting and the
/// primary SSA formation used in the compiler.
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_SCALAR_SROA_H
#define LLVM_TRANSFORMS_SCALAR_SROA_H
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ValueHandle.h"
#include <vector>
namespace llvm {
class AllocaInst;
class LoadInst;
class StoreInst;
class AssumptionCache;
class DominatorTree;
class DomTreeUpdater;
class Function;
class LLVMContext;
class PHINode;
class SelectInst;
class Use;
/// A private "module" namespace for types and utilities used by SROA. These
/// are implementation details and should not be used by clients.
namespace sroa LLVM_LIBRARY_VISIBILITY {
class AllocaSliceRewriter;
class AllocaSlices;
class Partition;
class SROALegacyPass;
class SelectHandSpeculativity {
unsigned char Storage = 0; // None are speculatable by default.
using TrueVal = Bitfield::Element<bool, 0, 1>; // Low 0'th bit.
using FalseVal = Bitfield::Element<bool, 1, 1>; // Low 1'th bit.
public:
SelectHandSpeculativity() = default;
SelectHandSpeculativity &setAsSpeculatable(bool isTrueVal);
bool isSpeculatable(bool isTrueVal) const;
bool areAllSpeculatable() const;
bool areAnySpeculatable() const;
bool areNoneSpeculatable() const;
// For interop as int half of PointerIntPair.
explicit operator intptr_t() const { return static_cast<intptr_t>(Storage); }
explicit SelectHandSpeculativity(intptr_t Storage_) : Storage(Storage_) {}
};
static_assert(sizeof(SelectHandSpeculativity) == sizeof(unsigned char));
using PossiblySpeculatableLoad =
PointerIntPair<LoadInst *, 2, sroa::SelectHandSpeculativity>;
using UnspeculatableStore = StoreInst *;
using RewriteableMemOp =
std::variant<PossiblySpeculatableLoad, UnspeculatableStore>;
using RewriteableMemOps = SmallVector<RewriteableMemOp, 2>;
} // end namespace sroa
enum class SROAOptions : bool { ModifyCFG, PreserveCFG };
/// An optimization pass providing Scalar Replacement of Aggregates.
///
/// This pass takes allocations which can be completely analyzed (that is, they
/// don't escape) and tries to turn them into scalar SSA values. There are
/// a few steps to this process.
///
/// 1) It takes allocations of aggregates and analyzes the ways in which they
/// are used to try to split them into smaller allocations, ideally of
/// a single scalar data type. It will split up memcpy and memset accesses
/// as necessary and try to isolate individual scalar accesses.
/// 2) It will transform accesses into forms which are suitable for SSA value
/// promotion. This can be replacing a memset with a scalar store of an
/// integer value, or it can involve speculating operations on a PHI or
/// select to be a PHI or select of the results.
/// 3) Finally, this will try to detect a pattern of accesses which map cleanly
/// onto insert and extract operations on a vector value, and convert them to
/// this form. By doing so, it will enable promotion of vector aggregates to
/// SSA vector values.
class SROAPass : public PassInfoMixin<SROAPass> {
LLVMContext *C = nullptr;
DomTreeUpdater *DTU = nullptr;
AssumptionCache *AC = nullptr;
const bool PreserveCFG;
/// Worklist of alloca instructions to simplify.
///
/// Each alloca in the function is added to this. Each new alloca formed gets
/// added to it as well to recursively simplify unless that alloca can be
/// directly promoted. Finally, each time we rewrite a use of an alloca other
/// the one being actively rewritten, we add it back onto the list if not
/// already present to ensure it is re-visited.
SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist;
/// A collection of instructions to delete.
/// We try to batch deletions to simplify code and make things a bit more
/// efficient. We also make sure there is no dangling pointers.
SmallVector<WeakVH, 8> DeadInsts;
/// Post-promotion worklist.
///
/// Sometimes we discover an alloca which has a high probability of becoming
/// viable for SROA after a round of promotion takes place. In those cases,
/// the alloca is enqueued here for re-processing.
///
/// Note that we have to be very careful to clear allocas out of this list in
/// the event they are deleted.
SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> PostPromotionWorklist;
/// A collection of alloca instructions we can directly promote.
std::vector<AllocaInst *> PromotableAllocas;
/// A worklist of PHIs to speculate prior to promoting allocas.
///
/// All of these PHIs have been checked for the safety of speculation and by
/// being speculated will allow promoting allocas currently in the promotable
/// queue.
SetVector<PHINode *, SmallVector<PHINode *, 8>> SpeculatablePHIs;
/// A worklist of select instructions to rewrite prior to promoting
/// allocas.
SmallMapVector<SelectInst *, sroa::RewriteableMemOps, 8> SelectsToRewrite;
/// Select instructions that use an alloca and are subsequently loaded can be
/// rewritten to load both input pointers and then select between the result,
/// allowing the load of the alloca to be promoted.
/// From this:
/// %P2 = select i1 %cond, ptr %Alloca, ptr %Other
/// %V = load <type>, ptr %P2
/// to:
/// %V1 = load <type>, ptr %Alloca -> will be mem2reg'd
/// %V2 = load <type>, ptr %Other
/// %V = select i1 %cond, <type> %V1, <type> %V2
///
/// We can do this to a select if its only uses are loads
/// and if either the operand to the select can be loaded unconditionally,
/// or if we are allowed to perform CFG modifications.
/// If found an intervening bitcast with a single use of the load,
/// allow the promotion.
static std::optional<sroa::RewriteableMemOps>
isSafeSelectToSpeculate(SelectInst &SI, bool PreserveCFG);
public:
/// If \p PreserveCFG is set, then the pass is not allowed to modify CFG
/// in any way, even if it would update CFG analyses.
SROAPass(SROAOptions PreserveCFG);
/// Run the pass over the function.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
void printPipeline(raw_ostream &OS,
function_ref<StringRef(StringRef)> MapClassName2PassName);
private:
friend class sroa::AllocaSliceRewriter;
friend class sroa::SROALegacyPass;
/// Helper used by both the public run method and by the legacy pass.
PreservedAnalyses runImpl(Function &F, DomTreeUpdater &RunDTU,
AssumptionCache &RunAC);
PreservedAnalyses runImpl(Function &F, DominatorTree &RunDT,
AssumptionCache &RunAC);
bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS);
AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS,
sroa::Partition &P);
bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS);
std::pair<bool /*Changed*/, bool /*CFGChanged*/> runOnAlloca(AllocaInst &AI);
void clobberUse(Use &U);
bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
bool promoteAllocas(Function &F);
};
} // end namespace llvm
#endif // LLVM_TRANSFORMS_SCALAR_SROA_H
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
|
