diff options
author | Nicolas Geoffray <ngeoffray@google.com> | 2014-05-02 08:46:00 +0100 |
---|---|---|
committer | Nicolas Geoffray <ngeoffray@google.com> | 2014-05-07 10:32:11 +0100 |
commit | 804d09372cc3d80d537da1489da4a45e0e19aa5d (patch) | |
tree | b226350fdf3dc0c55a11e1615010c8475f167f90 /compiler/optimizing/ssa_liveness_analysis.h | |
parent | 0095e0b8380a8802f40a21928800b9df6e11f1d7 (diff) | |
download | art-804d09372cc3d80d537da1489da4a45e0e19aa5d.zip art-804d09372cc3d80d537da1489da4a45e0e19aa5d.tar.gz art-804d09372cc3d80d537da1489da4a45e0e19aa5d.tar.bz2 |
Build live-in, live-out and kill sets for each block.
This information will be used when computing live ranges of
instructions.
Change-Id: I345ee833c1ccb4a8e725c7976453f6d58d350d74
Diffstat (limited to 'compiler/optimizing/ssa_liveness_analysis.h')
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.h | 101 |
1 files changed, 101 insertions, 0 deletions
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h new file mode 100644 index 0000000..6a901d1 --- /dev/null +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -0,0 +1,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_ |