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
|
/*
* 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.
*/
#ifndef ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
#define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
#include "nodes.h"
namespace art {
class BlockInfo : public ArenaObject {
public:
BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
: block_(block),
live_in_(allocator, number_of_ssa_values, false),
live_out_(allocator, number_of_ssa_values, false),
kill_(allocator, number_of_ssa_values, false) {
live_in_.ClearAllBits();
live_out_.ClearAllBits();
kill_.ClearAllBits();
}
private:
const HBasicBlock& block_;
ArenaBitVector live_in_;
ArenaBitVector live_out_;
ArenaBitVector kill_;
friend class SsaLivenessAnalysis;
DISALLOW_COPY_AND_ASSIGN(BlockInfo);
};
class SsaLivenessAnalysis : public ValueObject {
public:
explicit SsaLivenessAnalysis(const HGraph& graph)
: graph_(graph),
block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
number_of_ssa_values_(0) {
block_infos_.SetSize(graph.GetBlocks().Size());
}
void Analyze();
BitVector* GetLiveInSet(const HBasicBlock& block) const {
return &block_infos_.Get(block.GetBlockId())->live_in_;
}
BitVector* GetLiveOutSet(const HBasicBlock& block) const {
return &block_infos_.Get(block.GetBlockId())->live_out_;
}
BitVector* GetKillSet(const HBasicBlock& block) const {
return &block_infos_.Get(block.GetBlockId())->kill_;
}
private:
// Give an SSA number to each instruction that defines a value used by another instruction.
void NumberInstructions();
// Compute live_in, live_out and kill sets.
void ComputeSets();
// Compute the initial live_in, live_out and kill sets, without analyzing
// backward branches.
void ComputeInitialSets();
// After computing the initial sets, this method does a fixed point
// calculation over the live_in and live_out set to take into account
// backwards branches.
void ComputeLiveInAndLiveOutSets();
// Update the live_in set of the block and returns whether it has changed.
bool UpdateLiveIn(const HBasicBlock& block);
// Update the live_out set of the block and returns whether it has changed.
bool UpdateLiveOut(const HBasicBlock& block);
const HGraph& graph_;
GrowableArray<BlockInfo*> block_infos_;
size_t number_of_ssa_values_;
DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
};
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
|
