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 19 #include "code_generator.h" 20 #include "nodes.h" 21 22 namespace art { 23 24 void SsaLivenessAnalysis::Analyze() { 25 LinearizeGraph(); 26 NumberInstructions(); 27 ComputeLiveness(); 28 } 29 30 static bool IsLoopExit(HLoopInformation* current, HLoopInformation* to) { 31 // `to` is either not part of a loop, or `current` is an inner loop of `to`. 32 return to == nullptr || (current != to && current->IsIn(*to)); 33 } 34 35 static bool IsLoop(HLoopInformation* info) { 36 return info != nullptr; 37 } 38 39 static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { 40 return first_loop == second_loop; 41 } 42 43 static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { 44 return (inner != outer) 45 && (inner != nullptr) 46 && (outer != nullptr) 47 && inner->IsIn(*outer); 48 } 49 50 static void VisitBlockForLinearization(HBasicBlock* block, 51 GrowableArray<HBasicBlock*>* order, 52 ArenaBitVector* visited) { 53 if (visited->IsBitSet(block->GetBlockId())) { 54 return; 55 } 56 visited->SetBit(block->GetBlockId()); 57 size_t number_of_successors = block->GetSuccessors().Size(); 58 if (number_of_successors == 0) { 59 // Nothing to do. 60 } else if (number_of_successors == 1) { 61 VisitBlockForLinearization(block->GetSuccessors().Get(0), order, visited); 62 } else { 63 DCHECK_EQ(number_of_successors, 2u); 64 HBasicBlock* first_successor = block->GetSuccessors().Get(0); 65 HBasicBlock* second_successor = block->GetSuccessors().Get(1); 66 HLoopInformation* my_loop = block->GetLoopInformation(); 67 HLoopInformation* first_loop = first_successor->GetLoopInformation(); 68 HLoopInformation* second_loop = second_successor->GetLoopInformation(); 69 70 if (!IsLoop(my_loop)) { 71 // Nothing to do. Current order is fine. 72 } else if (IsLoopExit(my_loop, second_loop) && InSameLoop(my_loop, first_loop)) { 73 // Visit the loop exit first in post order. 74 std::swap(first_successor, second_successor); 75 } else if (IsInnerLoop(my_loop, first_loop) && !IsInnerLoop(my_loop, second_loop)) { 76 // Visit the inner loop last in post order. 77 std::swap(first_successor, second_successor); 78 } 79 VisitBlockForLinearization(first_successor, order, visited); 80 VisitBlockForLinearization(second_successor, order, visited); 81 } 82 order->Add(block); 83 } 84 85 void SsaLivenessAnalysis::LinearizeGraph() { 86 // For simplicity of the implementation, we create post linear order. The order for 87 // computing live ranges is the reverse of that order. 88 ArenaBitVector visited(graph_.GetArena(), graph_.GetBlocks().Size(), false); 89 VisitBlockForLinearization(graph_.GetEntryBlock(), &linear_post_order_, &visited); 90 } 91 92 void SsaLivenessAnalysis::NumberInstructions() { 93 int ssa_index = 0; 94 size_t lifetime_position = 0; 95 // Each instruction gets a lifetime position, and a block gets a lifetime 96 // start and end position. Non-phi instructions have a distinct lifetime position than 97 // the block they are in. Phi instructions have the lifetime start of their block as 98 // lifetime position. 99 // 100 // Because the register allocator will insert moves in the graph, we need 101 // to differentiate between the start and end of an instruction. Adding 2 to 102 // the lifetime position for each instruction ensures the start of an 103 // instruction is different than the end of the previous instruction. 104 for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) { 105 HBasicBlock* block = it.Current(); 106 block->SetLifetimeStart(lifetime_position); 107 108 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 109 HInstruction* current = it.Current(); 110 current->Accept(codegen_->GetLocationBuilder()); 111 LocationSummary* locations = current->GetLocations(); 112 if (locations != nullptr && locations->Out().IsValid()) { 113 instructions_from_ssa_index_.Add(current); 114 current->SetSsaIndex(ssa_index++); 115 current->SetLiveInterval( 116 new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType(), current)); 117 } 118 current->SetLifetimePosition(lifetime_position); 119 } 120 lifetime_position += 2; 121 122 // Add a null marker to notify we are starting a block. 123 instructions_from_lifetime_position_.Add(nullptr); 124 125 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 126 HInstruction* current = it.Current(); 127 current->Accept(codegen_->GetLocationBuilder()); 128 LocationSummary* locations = current->GetLocations(); 129 if (locations != nullptr && locations->Out().IsValid()) { 130 instructions_from_ssa_index_.Add(current); 131 current->SetSsaIndex(ssa_index++); 132 current->SetLiveInterval( 133 new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType(), current)); 134 } 135 instructions_from_lifetime_position_.Add(current); 136 current->SetLifetimePosition(lifetime_position); 137 lifetime_position += 2; 138 } 139 140 block->SetLifetimeEnd(lifetime_position); 141 } 142 number_of_ssa_values_ = ssa_index; 143 } 144 145 void SsaLivenessAnalysis::ComputeLiveness() { 146 for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) { 147 HBasicBlock* block = it.Current(); 148 block_infos_.Put( 149 block->GetBlockId(), 150 new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_)); 151 } 152 153 // Compute the live ranges, as well as the initial live_in, live_out, and kill sets. 154 // This method does not handle backward branches for the sets, therefore live_in 155 // and live_out sets are not yet correct. 156 ComputeLiveRanges(); 157 158 // Do a fixed point calculation to take into account backward branches, 159 // that will update live_in of loop headers, and therefore live_out and live_in 160 // of blocks in the loop. 161 ComputeLiveInAndLiveOutSets(); 162 } 163 164 void SsaLivenessAnalysis::ComputeLiveRanges() { 165 // Do a post order visit, adding inputs of instructions live in the block where 166 // that instruction is defined, and killing instructions that are being visited. 167 for (HLinearPostOrderIterator it(*this); !it.Done(); it.Advance()) { 168 HBasicBlock* block = it.Current(); 169 170 BitVector* kill = GetKillSet(*block); 171 BitVector* live_in = GetLiveInSet(*block); 172 173 // Set phi inputs of successors of this block corresponding to this block 174 // as live_in. 175 for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) { 176 HBasicBlock* successor = block->GetSuccessors().Get(i); 177 live_in->Union(GetLiveInSet(*successor)); 178 size_t phi_input_index = successor->GetPredecessorIndexOf(block); 179 for (HInstructionIterator it(successor->GetPhis()); !it.Done(); it.Advance()) { 180 HInstruction* phi = it.Current(); 181 HInstruction* input = phi->InputAt(phi_input_index); 182 input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block); 183 // A phi input whose last user is the phi dies at the end of the predecessor block, 184 // and not at the phi's lifetime position. 185 live_in->SetBit(input->GetSsaIndex()); 186 } 187 } 188 189 // Add a range that covers this block to all instructions live_in because of successors. 190 for (uint32_t idx : live_in->Indexes()) { 191 HInstruction* current = instructions_from_ssa_index_.Get(idx); 192 current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd()); 193 } 194 195 for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 196 HInstruction* current = it.Current(); 197 if (current->HasSsaIndex()) { 198 // Kill the instruction and shorten its interval. 199 kill->SetBit(current->GetSsaIndex()); 200 live_in->ClearBit(current->GetSsaIndex()); 201 current->GetLiveInterval()->SetFrom(current->GetLifetimePosition()); 202 } 203 204 // All inputs of an instruction must be live. 205 for (size_t i = 0, e = current->InputCount(); i < e; ++i) { 206 HInstruction* input = current->InputAt(i); 207 // Some instructions 'inline' their inputs, that is they do not need 208 // to be materialized. 209 if (input->HasSsaIndex()) { 210 live_in->SetBit(input->GetSsaIndex()); 211 input->GetLiveInterval()->AddUse(current, i, false); 212 } 213 } 214 215 if (current->HasEnvironment()) { 216 // All instructions in the environment must be live. 217 GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs(); 218 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 219 HInstruction* instruction = environment->Get(i); 220 if (instruction != nullptr) { 221 DCHECK(instruction->HasSsaIndex()); 222 live_in->SetBit(instruction->GetSsaIndex()); 223 instruction->GetLiveInterval()->AddUse(current, i, true); 224 } 225 } 226 } 227 } 228 229 // Kill phis defined in this block. 230 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 231 HInstruction* current = it.Current(); 232 if (current->HasSsaIndex()) { 233 kill->SetBit(current->GetSsaIndex()); 234 live_in->ClearBit(current->GetSsaIndex()); 235 LiveInterval* interval = current->GetLiveInterval(); 236 DCHECK((interval->GetFirstRange() == nullptr) 237 || (interval->GetStart() == current->GetLifetimePosition())); 238 interval->SetFrom(current->GetLifetimePosition()); 239 } 240 } 241 242 if (block->IsLoopHeader()) { 243 HBasicBlock* back_edge = block->GetLoopInformation()->GetBackEdges().Get(0); 244 // For all live_in instructions at the loop header, we need to create a range 245 // that covers the full loop. 246 for (uint32_t idx : live_in->Indexes()) { 247 HInstruction* current = instructions_from_ssa_index_.Get(idx); 248 current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(), 249 back_edge->GetLifetimeEnd()); 250 } 251 } 252 } 253 } 254 255 void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() { 256 bool changed; 257 do { 258 changed = false; 259 260 for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) { 261 const HBasicBlock& block = *it.Current(); 262 263 // The live_in set depends on the kill set (which does not 264 // change in this loop), and the live_out set. If the live_out 265 // set does not change, there is no need to update the live_in set. 266 if (UpdateLiveOut(block) && UpdateLiveIn(block)) { 267 changed = true; 268 } 269 } 270 } while (changed); 271 } 272 273 bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) { 274 BitVector* live_out = GetLiveOutSet(block); 275 bool changed = false; 276 // The live_out set of a block is the union of live_in sets of its successors. 277 for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) { 278 HBasicBlock* successor = block.GetSuccessors().Get(i); 279 if (live_out->Union(GetLiveInSet(*successor))) { 280 changed = true; 281 } 282 } 283 return changed; 284 } 285 286 287 bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) { 288 BitVector* live_out = GetLiveOutSet(block); 289 BitVector* kill = GetKillSet(block); 290 BitVector* live_in = GetLiveInSet(block); 291 // If live_out is updated (because of backward branches), we need to make 292 // sure instructions in live_out are also in live_in, unless they are killed 293 // by this block. 294 return live_in->UnionIfNotIn(live_out, kill); 295 } 296 297 } // namespace art 298