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
|
/*
* 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 "nodes.h"
namespace art {
void SsaLivenessAnalysis::Analyze() {
NumberInstructions();
ComputeSets();
}
void SsaLivenessAnalysis::NumberInstructions() {
int ssa_index = 0;
for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->HasUses()) {
current->SetSsaIndex(ssa_index++);
}
}
for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->HasUses()) {
current->SetSsaIndex(ssa_index++);
}
}
}
number_of_ssa_values_ = ssa_index;
}
void SsaLivenessAnalysis::ComputeSets() {
for (HReversePostOrderIterator it(graph_); !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 initial live_in, live_out, and kill sets. This method does not handle
// backward branches, therefore live_in and live_out sets are not yet correct.
ComputeInitialSets();
// 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::ComputeInitialSets() {
// Do a post orderr visit, adding inputs of instructions live in the block where
// that instruction is defined, and killing instructions that are being visited.
for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
BitVector* kill = GetKillSet(*block);
BitVector* live_in = GetLiveInSet(*block);
for (HBackwardInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->HasSsaIndex()) {
kill->SetBit(current->GetSsaIndex());
live_in->ClearBit(current->GetSsaIndex());
}
// All inputs of an instruction must be live.
for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
DCHECK(current->InputAt(i)->HasSsaIndex());
live_in->SetBit(current->InputAt(i)->GetSsaIndex());
}
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());
}
}
}
}
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());
}
// Mark a phi input live_in for its corresponding predecessor.
for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
HInstruction* input = current->InputAt(i);
HBasicBlock* predecessor = block->GetPredecessors()->Get(i);
size_t ssa_index = input->GetSsaIndex();
BitVector* predecessor_kill = GetKillSet(*predecessor);
BitVector* predecessor_live_in = GetLiveInSet(*predecessor);
// Phi inputs from a back edge have already been visited. If the back edge
// block defines that input, we should not add it to its live_in.
if (!predecessor_kill->IsBitSet(ssa_index)) {
predecessor_live_in->SetBit(ssa_index);
}
}
}
}
}
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
|