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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
|
/*
* Copyright (C) 2014 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "ssa_liveness_analysis.h"
#include "code_generator.h"
#include "nodes.h"
namespace art {
void SsaLivenessAnalysis::Analyze() {
LinearizeGraph();
NumberInstructions();
ComputeLiveness();
}
static bool IsLoopExit(HLoopInformation* current, HLoopInformation* to) {
// `to` is either not part of a loop, or `current` is an inner loop of `to`.
return to == nullptr || (current != to && current->IsIn(*to));
}
static bool IsLoop(HLoopInformation* info) {
return info != nullptr;
}
static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) {
return first_loop == second_loop;
}
static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) {
return (inner != outer)
&& (inner != nullptr)
&& (outer != nullptr)
&& inner->IsIn(*outer);
}
static void VisitBlockForLinearization(HBasicBlock* block,
GrowableArray<HBasicBlock*>* order,
ArenaBitVector* visited) {
if (visited->IsBitSet(block->GetBlockId())) {
return;
}
visited->SetBit(block->GetBlockId());
size_t number_of_successors = block->GetSuccessors().Size();
if (number_of_successors == 0) {
// Nothing to do.
} else if (number_of_successors == 1) {
VisitBlockForLinearization(block->GetSuccessors().Get(0), order, visited);
} else {
DCHECK_EQ(number_of_successors, 2u);
HBasicBlock* first_successor = block->GetSuccessors().Get(0);
HBasicBlock* second_successor = block->GetSuccessors().Get(1);
HLoopInformation* my_loop = block->GetLoopInformation();
HLoopInformation* first_loop = first_successor->GetLoopInformation();
HLoopInformation* second_loop = second_successor->GetLoopInformation();
if (!IsLoop(my_loop)) {
// Nothing to do. Current order is fine.
} else if (IsLoopExit(my_loop, second_loop) && InSameLoop(my_loop, first_loop)) {
// Visit the loop exit first in post order.
std::swap(first_successor, second_successor);
} else if (IsInnerLoop(my_loop, first_loop) && !IsInnerLoop(my_loop, second_loop)) {
// Visit the inner loop last in post order.
std::swap(first_successor, second_successor);
}
VisitBlockForLinearization(first_successor, order, visited);
VisitBlockForLinearization(second_successor, order, visited);
}
order->Add(block);
}
void SsaLivenessAnalysis::LinearizeGraph() {
// For simplicity of the implementation, we create post linear order. The order for
// computing live ranges is the reverse of that order.
ArenaBitVector visited(graph_.GetArena(), graph_.GetBlocks().Size(), false);
VisitBlockForLinearization(graph_.GetEntryBlock(), &linear_post_order_, &visited);
}
void SsaLivenessAnalysis::NumberInstructions() {
int ssa_index = 0;
size_t lifetime_position = 0;
// Each instruction gets a lifetime position, and a block gets a lifetime
// start and end position. Non-phi instructions have a distinct lifetime position than
// the block they are in. Phi instructions have the lifetime start of their block as
// lifetime position.
//
// Because the register allocator will insert moves in the graph, we need
// to differentiate between the start and end of an instruction. Adding 2 to
// the lifetime position for each instruction ensures the start of an
// instruction is different than the end of the previous instruction.
for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
block->SetLifetimeStart(lifetime_position);
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
current->Accept(codegen_->GetLocationBuilder());
LocationSummary* locations = current->GetLocations();
if (locations != nullptr && locations->Out().IsValid()) {
instructions_from_ssa_index_.Add(current);
current->SetSsaIndex(ssa_index++);
current->SetLiveInterval(
new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType(), current));
}
current->SetLifetimePosition(lifetime_position);
}
lifetime_position += 2;
// Add a null marker to notify we are starting a block.
instructions_from_lifetime_position_.Add(nullptr);
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
current->Accept(codegen_->GetLocationBuilder());
LocationSummary* locations = current->GetLocations();
if (locations != nullptr && locations->Out().IsValid()) {
instructions_from_ssa_index_.Add(current);
current->SetSsaIndex(ssa_index++);
current->SetLiveInterval(
new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType(), current));
}
instructions_from_lifetime_position_.Add(current);
current->SetLifetimePosition(lifetime_position);
lifetime_position += 2;
}
block->SetLifetimeEnd(lifetime_position);
}
number_of_ssa_values_ = ssa_index;
}
void SsaLivenessAnalysis::ComputeLiveness() {
for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
block_infos_.Put(
block->GetBlockId(),
new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_));
}
// Compute the live ranges, as well as the initial live_in, live_out, and kill sets.
// This method does not handle backward branches for the sets, therefore live_in
// and live_out sets are not yet correct.
ComputeLiveRanges();
// Do a fixed point calculation to take into account backward branches,
// that will update live_in of loop headers, and therefore live_out and live_in
// of blocks in the loop.
ComputeLiveInAndLiveOutSets();
}
void SsaLivenessAnalysis::ComputeLiveRanges() {
// Do a post order visit, adding inputs of instructions live in the block where
// that instruction is defined, and killing instructions that are being visited.
for (HLinearPostOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
BitVector* kill = GetKillSet(*block);
BitVector* live_in = GetLiveInSet(*block);
// Set phi inputs of successors of this block corresponding to this block
// as live_in.
for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
HBasicBlock* successor = block->GetSuccessors().Get(i);
live_in->Union(GetLiveInSet(*successor));
size_t phi_input_index = successor->GetPredecessorIndexOf(block);
for (HInstructionIterator it(successor->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* phi = it.Current();
HInstruction* input = phi->InputAt(phi_input_index);
input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block);
// A phi input whose last user is the phi dies at the end of the predecessor block,
// and not at the phi's lifetime position.
live_in->SetBit(input->GetSsaIndex());
}
}
// Add a range that covers this block to all instructions live_in because of successors.
for (uint32_t idx : live_in->Indexes()) {
HInstruction* current = instructions_from_ssa_index_.Get(idx);
current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
}
for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->HasSsaIndex()) {
// Kill the instruction and shorten its interval.
kill->SetBit(current->GetSsaIndex());
live_in->ClearBit(current->GetSsaIndex());
current->GetLiveInterval()->SetFrom(current->GetLifetimePosition());
}
// All inputs of an instruction must be live.
for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
HInstruction* input = current->InputAt(i);
DCHECK(input->HasSsaIndex());
live_in->SetBit(input->GetSsaIndex());
input->GetLiveInterval()->AddUse(current, i, false);
}
if (current->HasEnvironment()) {
// All instructions in the environment must be live.
GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs();
for (size_t i = 0, e = environment->Size(); i < e; ++i) {
HInstruction* instruction = environment->Get(i);
if (instruction != nullptr) {
DCHECK(instruction->HasSsaIndex());
live_in->SetBit(instruction->GetSsaIndex());
instruction->GetLiveInterval()->AddUse(current, i, true);
}
}
}
}
// Kill phis defined in this block.
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->HasSsaIndex()) {
kill->SetBit(current->GetSsaIndex());
live_in->ClearBit(current->GetSsaIndex());
LiveInterval* interval = current->GetLiveInterval();
DCHECK((interval->GetFirstRange() == nullptr)
|| (interval->GetStart() == current->GetLifetimePosition()));
interval->SetFrom(current->GetLifetimePosition());
}
}
if (block->IsLoopHeader()) {
HBasicBlock* back_edge = block->GetLoopInformation()->GetBackEdges().Get(0);
// For all live_in instructions at the loop header, we need to create a range
// that covers the full loop.
for (uint32_t idx : live_in->Indexes()) {
HInstruction* current = instructions_from_ssa_index_.Get(idx);
current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(),
back_edge->GetLifetimeEnd());
}
}
}
}
void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
bool changed;
do {
changed = false;
for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) {
const HBasicBlock& block = *it.Current();
// The live_in set depends on the kill set (which does not
// change in this loop), and the live_out set. If the live_out
// set does not change, there is no need to update the live_in set.
if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
changed = true;
}
}
} while (changed);
}
bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) {
BitVector* live_out = GetLiveOutSet(block);
bool changed = false;
// The live_out set of a block is the union of live_in sets of its successors.
for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) {
HBasicBlock* successor = block.GetSuccessors().Get(i);
if (live_out->Union(GetLiveInSet(*successor))) {
changed = true;
}
}
return changed;
}
bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) {
BitVector* live_out = GetLiveOutSet(block);
BitVector* kill = GetKillSet(block);
BitVector* live_in = GetLiveInSet(block);
// If live_out is updated (because of backward branches), we need to make
// sure instructions in live_out are also in live_in, unless they are killed
// by this block.
return live_in->UnionIfNotIn(live_out, kill);
}
} // namespace art
|