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
203
204
205
206
207
|
//===--- ARCBBState.h -------------------------------------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
#ifndef SWIFT_SILOPTIMIZER_PASSMANAGER_ARC_ARCBBSTATE_H
#define SWIFT_SILOPTIMIZER_PASSMANAGER_ARC_ARCBBSTATE_H
#include "GlobalARCSequenceDataflow.h"
namespace swift {
/// Per-BasicBlock state.
class ARCSequenceDataflowEvaluator::ARCBBState {
public:
using TopDownMapTy = SmallBlotMapVector<SILValue, TopDownRefCountState, 4>;
using BottomUpMapTy = SmallBlotMapVector<SILValue, BottomUpRefCountState, 4>;
private:
/// The basic block that this bbstate corresponds to.
SILBasicBlock *BB;
/// The top-down traversal uses this to record information known about a
/// pointer at the bottom of each block.
TopDownMapTy PtrToTopDownState;
/// The bottom-up traversal uses this to record information known about a
/// pointer at the top of each block.
BottomUpMapTy PtrToBottomUpState;
/// Is this a BB that is a trap?
bool IsTrapBB;
public:
ARCBBState() : BB() {}
ARCBBState(SILBasicBlock *BB) : BB(BB) {}
void init(SILBasicBlock *NewBB, bool NewIsTrapBB) {
assert(NewBB && "Cannot set NewBB to a nullptr.");
BB = NewBB;
IsTrapBB = NewIsTrapBB;
}
/// Is this BB a BB that fits the canonical form of a trap?
///
/// The canonical form of a trap is:
///
/// builtin "int_trap"() : $()
/// unreachable
///
/// This cannot have any uses of reference counted values since the frontend
/// just leaks at that point.
bool isTrapBB() const { return IsTrapBB; }
/// Top Down Iterators
using topdown_iterator = TopDownMapTy::iterator;
using topdown_const_iterator = TopDownMapTy::const_iterator;
topdown_iterator topdown_begin() { return PtrToTopDownState.begin(); }
topdown_iterator topdown_end() { return PtrToTopDownState.end(); }
topdown_const_iterator topdown_begin() const {
return PtrToTopDownState.begin();
}
topdown_const_iterator topdown_end() const { return PtrToTopDownState.end(); }
iterator_range<topdown_iterator> getTopDownStates() {
return make_range(topdown_begin(), topdown_end());
}
/// Bottom up iteration.
using bottomup_iterator = BottomUpMapTy::iterator;
using bottomup_const_iterator = BottomUpMapTy::const_iterator;
bottomup_iterator bottomup_begin() { return PtrToBottomUpState.begin(); }
bottomup_iterator bottomup_end() { return PtrToBottomUpState.end(); }
bottomup_const_iterator bottomup_begin() const {
return PtrToBottomUpState.begin();
}
bottomup_const_iterator bottomup_end() const {
return PtrToBottomUpState.end();
}
iterator_range<bottomup_iterator> getBottomupStates() {
return make_range(bottomup_begin(), bottomup_end());
}
/// Attempt to find the PtrState object describing the top down state for
/// pointer Arg. Return a new initialized PtrState describing the top down
/// state for Arg if we do not find one.
TopDownRefCountState &getTopDownRefCountState(SILValue Ptr) {
return PtrToTopDownState[Ptr];
}
/// Attempt to find the PtrState object describing the bottom up state for
/// pointer Arg. Return a new initialized PtrState describing the bottom up
/// state for Arg if we do not find one.
BottomUpRefCountState &getBottomUpRefCountState(SILValue Ptr) {
return PtrToBottomUpState[Ptr];
}
/// Blot \p Ptr.
void clearBottomUpRefCountState(SILValue Ptr) {
PtrToBottomUpState.erase(Ptr);
}
/// Blot \p Ptr.
void clearTopDownRefCountState(SILValue Ptr) { PtrToTopDownState.erase(Ptr); }
void clearTopDownState() { PtrToTopDownState.clear(); }
void clearBottomUpState() { PtrToBottomUpState.clear(); }
/// Clear both the bottom up *AND* top down state.
void clear() {
clearTopDownState();
clearBottomUpState();
}
/// Returns a reference to the basic block that we are tracking.
SILBasicBlock &getBB() const { return *BB; }
/// Merge in the state of the successor basic block. This is currently a stub.
void mergeSuccBottomUp(ARCBBState &SuccBB);
/// Initialize this BB with the state of the successor basic block. This is
/// called on a basic block's state and then any other successors states are
/// merged in. This is currently a stub.
void initSuccBottomUp(ARCBBState &SuccBB);
/// Merge in the state of the predecessor basic block. This is currently a
/// stub.
void mergePredTopDown(ARCBBState &PredBB);
/// Initialize the state for this BB with the state of its predecessor
/// BB. Used to create an initial state before we merge in other
/// predecessors. This is currently a stub.
void initPredTopDown(ARCBBState &PredBB);
void dumpBottomUpState();
void dumpTopDownState();
};
class ARCSequenceDataflowEvaluator::ARCBBStateInfoHandle {
friend ARCSequenceDataflowEvaluator::ARCBBStateInfo;
SILBasicBlock *BB;
ARCBBState &BBState;
NullablePtr<llvm::SmallPtrSet<SILBasicBlock *, 4>> BackedgeMap;
unsigned ID;
ARCBBStateInfoHandle(SILBasicBlock *BB, unsigned ID, ARCBBState &BBState)
: BB(BB), BBState(BBState), BackedgeMap(), ID(ID) {}
ARCBBStateInfoHandle(SILBasicBlock *BB, unsigned ID, ARCBBState &BBState,
llvm::SmallPtrSet<SILBasicBlock *, 4> &BackedgeMap)
: BB(BB), BBState(BBState), BackedgeMap(&BackedgeMap), ID(ID) {}
public:
ARCBBStateInfoHandle(const ARCBBStateInfoHandle &) = default;
ARCBBStateInfoHandle(ARCBBStateInfoHandle &&) = default;
;
~ARCBBStateInfoHandle() = default;
SILBasicBlock *getBB() const { return BB; }
unsigned getID() const { return ID; }
ARCBBState &getState() { return BBState; }
bool isBackedge(SILBasicBlock *BB) const {
if (BackedgeMap.isNull())
return false;
return BackedgeMap.get()->count(BB);
}
};
class ARCSequenceDataflowEvaluator::ARCBBStateInfo {
/// A map from BB -> BBID. A BB's BBID is its RPOT number.
llvm::DenseMap<SILBasicBlock *, unsigned> BBToBBIDMap;
/// Map from a BBID to BB's bottom up dataflow state. Meant to be used in
/// conjunction with BBToBBIDMap.
std::vector<ARCBBState> BBIDToBottomUpBBStateMap;
/// Map from a BBID to BB's top down dataflow state. Meant to be used in
/// conjunction with BBToBBIDMap.
std::vector<ARCBBState> BBIDToTopDownBBStateMap;
/// A map mapping the head to a tail of a backedge. We only compute this once
/// in the lifetime of this class.
llvm::DenseMap<SILBasicBlock *, llvm::SmallPtrSet<SILBasicBlock *, 4>>
BackedgeMap;
public:
ARCBBStateInfo(SILFunction *F, PostOrderAnalysis *POTA,
ProgramTerminationFunctionInfo *PTFI);
std::optional<ARCBBStateInfoHandle> getBottomUpBBHandle(SILBasicBlock *BB);
std::optional<ARCBBStateInfoHandle> getTopDownBBHandle(SILBasicBlock *BB);
void clear();
private:
std::optional<unsigned> getBBID(SILBasicBlock *BB) const;
};
} // end swift namespace
#endif
|
