ssa_liveness_analysis.cc revision 0d3f578909d0d1ea072ca68d78301b6fb7a44451
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#include "ssa_liveness_analysis.h" 18#include "nodes.h" 19 20namespace art { 21 22void SsaLivenessAnalysis::Analyze() { 23 LinearizeGraph(); 24 NumberInstructions(); 25 ComputeSets(); 26} 27 28static bool IsLoopExit(HLoopInformation* current, HLoopInformation* to) { 29 // `to` is either not part of a loop, or `current` is an inner loop of `to`. 30 return to == nullptr || (current != to && current->IsIn(*to)); 31} 32 33static bool IsLoop(HLoopInformation* info) { 34 return info != nullptr; 35} 36 37static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { 38 return first_loop == second_loop; 39} 40 41static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { 42 return (inner != outer) 43 && (inner != nullptr) 44 && (outer != nullptr) 45 && inner->IsIn(*outer); 46} 47 48static void VisitBlockForLinearization(HBasicBlock* block, 49 GrowableArray<HBasicBlock*>* order, 50 ArenaBitVector* visited) { 51 if (visited->IsBitSet(block->GetBlockId())) { 52 return; 53 } 54 visited->SetBit(block->GetBlockId()); 55 size_t number_of_successors = block->GetSuccessors().Size(); 56 if (number_of_successors == 0) { 57 // Nothing to do. 58 } else if (number_of_successors == 1) { 59 VisitBlockForLinearization(block->GetSuccessors().Get(0), order, visited); 60 } else { 61 DCHECK_EQ(number_of_successors, 2u); 62 HBasicBlock* first_successor = block->GetSuccessors().Get(0); 63 HBasicBlock* second_successor = block->GetSuccessors().Get(1); 64 HLoopInformation* my_loop = block->GetLoopInformation(); 65 HLoopInformation* first_loop = first_successor->GetLoopInformation(); 66 HLoopInformation* second_loop = second_successor->GetLoopInformation(); 67 68 if (!IsLoop(my_loop)) { 69 // Nothing to do. Current order is fine. 70 } else if (IsLoopExit(my_loop, second_loop) && InSameLoop(my_loop, first_loop)) { 71 // Visit the loop exit first in post order. 72 std::swap(first_successor, second_successor); 73 } else if (IsInnerLoop(my_loop, first_loop) && !IsInnerLoop(my_loop, second_loop)) { 74 // Visit the inner loop last in post order. 75 std::swap(first_successor, second_successor); 76 } 77 VisitBlockForLinearization(first_successor, order, visited); 78 VisitBlockForLinearization(second_successor, order, visited); 79 } 80 order->Add(block); 81} 82 83class HLinearOrderIterator : public ValueObject { 84 public: 85 explicit HLinearOrderIterator(const GrowableArray<HBasicBlock*>& post_order) 86 : post_order_(post_order), index_(post_order.Size()) {} 87 88 bool Done() const { return index_ == 0; } 89 HBasicBlock* Current() const { return post_order_.Get(index_ -1); } 90 void Advance() { --index_; DCHECK_GE(index_, 0U); } 91 92 private: 93 const GrowableArray<HBasicBlock*>& post_order_; 94 size_t index_; 95 96 DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); 97}; 98 99void SsaLivenessAnalysis::LinearizeGraph() { 100 // For simplicity of the implementation, we create post linear order. The order for 101 // computing live ranges is the reverse of that order. 102 ArenaBitVector visited(graph_.GetArena(), graph_.GetBlocks().Size(), false); 103 VisitBlockForLinearization(graph_.GetEntryBlock(), &linear_post_order_, &visited); 104} 105 106void SsaLivenessAnalysis::NumberInstructions() { 107 int ssa_index = 0; 108 for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) { 109 HBasicBlock* block = it.Current(); 110 111 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 112 HInstruction* current = it.Current(); 113 if (current->HasUses()) { 114 current->SetSsaIndex(ssa_index++); 115 } 116 } 117 118 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 119 HInstruction* current = it.Current(); 120 if (current->HasUses()) { 121 current->SetSsaIndex(ssa_index++); 122 } 123 } 124 } 125 number_of_ssa_values_ = ssa_index; 126} 127 128void SsaLivenessAnalysis::ComputeSets() { 129 for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) { 130 HBasicBlock* block = it.Current(); 131 block_infos_.Put( 132 block->GetBlockId(), 133 new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_)); 134 } 135 136 // Compute the initial live_in, live_out, and kill sets. This method does not handle 137 // backward branches, therefore live_in and live_out sets are not yet correct. 138 ComputeInitialSets(); 139 140 // Do a fixed point calculation to take into account backward branches, 141 // that will update live_in of loop headers, and therefore live_out and live_in 142 // of blocks in the loop. 143 ComputeLiveInAndLiveOutSets(); 144} 145 146void SsaLivenessAnalysis::ComputeInitialSets() { 147 // Do a post orderr visit, adding inputs of instructions live in the block where 148 // that instruction is defined, and killing instructions that are being visited. 149 for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) { 150 HBasicBlock* block = it.Current(); 151 152 BitVector* kill = GetKillSet(*block); 153 BitVector* live_in = GetLiveInSet(*block); 154 155 for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 156 HInstruction* current = it.Current(); 157 if (current->HasSsaIndex()) { 158 kill->SetBit(current->GetSsaIndex()); 159 live_in->ClearBit(current->GetSsaIndex()); 160 } 161 162 // All inputs of an instruction must be live. 163 for (size_t i = 0, e = current->InputCount(); i < e; ++i) { 164 DCHECK(current->InputAt(i)->HasSsaIndex()); 165 live_in->SetBit(current->InputAt(i)->GetSsaIndex()); 166 } 167 168 if (current->HasEnvironment()) { 169 // All instructions in the environment must be live. 170 GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs(); 171 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 172 HInstruction* instruction = environment->Get(i); 173 if (instruction != nullptr) { 174 DCHECK(instruction->HasSsaIndex()); 175 live_in->SetBit(instruction->GetSsaIndex()); 176 } 177 } 178 } 179 } 180 181 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 182 HInstruction* current = it.Current(); 183 if (current->HasSsaIndex()) { 184 kill->SetBit(current->GetSsaIndex()); 185 live_in->ClearBit(current->GetSsaIndex()); 186 } 187 188 // Mark a phi input live_in for its corresponding predecessor. 189 for (size_t i = 0, e = current->InputCount(); i < e; ++i) { 190 HInstruction* input = current->InputAt(i); 191 192 HBasicBlock* predecessor = block->GetPredecessors().Get(i); 193 size_t ssa_index = input->GetSsaIndex(); 194 BitVector* predecessor_kill = GetKillSet(*predecessor); 195 BitVector* predecessor_live_in = GetLiveInSet(*predecessor); 196 197 // Phi inputs from a back edge have already been visited. If the back edge 198 // block defines that input, we should not add it to its live_in. 199 if (!predecessor_kill->IsBitSet(ssa_index)) { 200 predecessor_live_in->SetBit(ssa_index); 201 } 202 } 203 } 204 } 205} 206 207void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() { 208 bool changed; 209 do { 210 changed = false; 211 212 for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) { 213 const HBasicBlock& block = *it.Current(); 214 215 // The live_in set depends on the kill set (which does not 216 // change in this loop), and the live_out set. If the live_out 217 // set does not change, there is no need to update the live_in set. 218 if (UpdateLiveOut(block) && UpdateLiveIn(block)) { 219 changed = true; 220 } 221 } 222 } while (changed); 223} 224 225bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) { 226 BitVector* live_out = GetLiveOutSet(block); 227 bool changed = false; 228 // The live_out set of a block is the union of live_in sets of its successors. 229 for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) { 230 HBasicBlock* successor = block.GetSuccessors().Get(i); 231 if (live_out->Union(GetLiveInSet(*successor))) { 232 changed = true; 233 } 234 } 235 return changed; 236} 237 238 239bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) { 240 BitVector* live_out = GetLiveOutSet(block); 241 BitVector* kill = GetKillSet(block); 242 BitVector* live_in = GetLiveInSet(block); 243 // If live_out is updated (because of backward branches), we need to make 244 // sure instructions in live_out are also in live_in, unless they are killed 245 // by this block. 246 return live_in->UnionIfNotIn(live_out, kill); 247} 248 249} // namespace art 250