ssa_liveness_analysis.cc revision e50fa5887b1342b845826197d81950e26753fc9c
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 "base/bit_vector-inl.h" 20#include "code_generator.h" 21#include "nodes.h" 22 23namespace art { 24 25void SsaLivenessAnalysis::Analyze() { 26 LinearizeGraph(); 27 NumberInstructions(); 28 ComputeLiveness(); 29} 30 31static bool IsLoopExit(HLoopInformation* current, HLoopInformation* to) { 32 // `to` is either not part of a loop, or `current` is an inner loop of `to`. 33 return to == nullptr || (current != to && current->IsIn(*to)); 34} 35 36static bool IsLoop(HLoopInformation* info) { 37 return info != nullptr; 38} 39 40static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { 41 return first_loop == second_loop; 42} 43 44static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { 45 return (inner != outer) 46 && (inner != nullptr) 47 && (outer != nullptr) 48 && inner->IsIn(*outer); 49} 50 51static void VisitBlockForLinearization(HBasicBlock* block, 52 GrowableArray<HBasicBlock*>* order, 53 ArenaBitVector* visited) { 54 if (visited->IsBitSet(block->GetBlockId())) { 55 return; 56 } 57 visited->SetBit(block->GetBlockId()); 58 size_t number_of_successors = block->GetSuccessors().Size(); 59 if (number_of_successors == 0) { 60 // Nothing to do. 61 } else if (number_of_successors == 1) { 62 VisitBlockForLinearization(block->GetSuccessors().Get(0), order, visited); 63 } else { 64 DCHECK_EQ(number_of_successors, 2u); 65 HBasicBlock* first_successor = block->GetSuccessors().Get(0); 66 HBasicBlock* second_successor = block->GetSuccessors().Get(1); 67 HLoopInformation* my_loop = block->GetLoopInformation(); 68 HLoopInformation* first_loop = first_successor->GetLoopInformation(); 69 HLoopInformation* second_loop = second_successor->GetLoopInformation(); 70 71 if (!IsLoop(my_loop)) { 72 // Nothing to do. Current order is fine. 73 } else if (IsLoopExit(my_loop, second_loop) && InSameLoop(my_loop, first_loop)) { 74 // Visit the loop exit first in post order. 75 std::swap(first_successor, second_successor); 76 } else if (IsInnerLoop(my_loop, first_loop) && !IsInnerLoop(my_loop, second_loop)) { 77 // Visit the inner loop last in post order. 78 std::swap(first_successor, second_successor); 79 } 80 VisitBlockForLinearization(first_successor, order, visited); 81 VisitBlockForLinearization(second_successor, order, visited); 82 } 83 order->Add(block); 84} 85 86void SsaLivenessAnalysis::LinearizeGraph() { 87 // For simplicity of the implementation, we create post linear order. The order for 88 // computing live ranges is the reverse of that order. 89 ArenaBitVector visited(graph_.GetArena(), graph_.GetBlocks().Size(), false); 90 VisitBlockForLinearization(graph_.GetEntryBlock(), &linear_post_order_, &visited); 91} 92 93void SsaLivenessAnalysis::NumberInstructions() { 94 int ssa_index = 0; 95 size_t lifetime_position = 0; 96 // Each instruction gets a lifetime position, and a block gets a lifetime 97 // start and end position. Non-phi instructions have a distinct lifetime position than 98 // the block they are in. Phi instructions have the lifetime start of their block as 99 // lifetime position. 100 // 101 // Because the register allocator will insert moves in the graph, we need 102 // to differentiate between the start and end of an instruction. Adding 2 to 103 // the lifetime position for each instruction ensures the start of an 104 // instruction is different than the end of the previous instruction. 105 HGraphVisitor* location_builder = codegen_->GetLocationBuilder(); 106 for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) { 107 HBasicBlock* block = it.Current(); 108 block->SetLifetimeStart(lifetime_position); 109 110 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 111 HInstruction* current = inst_it.Current(); 112 current->Accept(location_builder); 113 LocationSummary* locations = current->GetLocations(); 114 if (locations != nullptr && locations->Out().IsValid()) { 115 instructions_from_ssa_index_.Add(current); 116 current->SetSsaIndex(ssa_index++); 117 current->SetLiveInterval( 118 LiveInterval::MakeInterval(graph_.GetArena(), current->GetType(), current)); 119 } 120 current->SetLifetimePosition(lifetime_position); 121 } 122 lifetime_position += 2; 123 124 // Add a null marker to notify we are starting a block. 125 instructions_from_lifetime_position_.Add(nullptr); 126 127 for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done(); 128 inst_it.Advance()) { 129 HInstruction* current = inst_it.Current(); 130 current->Accept(codegen_->GetLocationBuilder()); 131 LocationSummary* locations = current->GetLocations(); 132 if (locations != nullptr && locations->Out().IsValid()) { 133 instructions_from_ssa_index_.Add(current); 134 current->SetSsaIndex(ssa_index++); 135 current->SetLiveInterval( 136 LiveInterval::MakeInterval(graph_.GetArena(), current->GetType(), current)); 137 } 138 instructions_from_lifetime_position_.Add(current); 139 current->SetLifetimePosition(lifetime_position); 140 lifetime_position += 2; 141 } 142 143 block->SetLifetimeEnd(lifetime_position); 144 } 145 number_of_ssa_values_ = ssa_index; 146} 147 148void SsaLivenessAnalysis::ComputeLiveness() { 149 for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) { 150 HBasicBlock* block = it.Current(); 151 block_infos_.Put( 152 block->GetBlockId(), 153 new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_)); 154 } 155 156 // Compute the live ranges, as well as the initial live_in, live_out, and kill sets. 157 // This method does not handle backward branches for the sets, therefore live_in 158 // and live_out sets are not yet correct. 159 ComputeLiveRanges(); 160 161 // Do a fixed point calculation to take into account backward branches, 162 // that will update live_in of loop headers, and therefore live_out and live_in 163 // of blocks in the loop. 164 ComputeLiveInAndLiveOutSets(); 165} 166 167void SsaLivenessAnalysis::ComputeLiveRanges() { 168 // Do a post order visit, adding inputs of instructions live in the block where 169 // that instruction is defined, and killing instructions that are being visited. 170 for (HLinearPostOrderIterator it(*this); !it.Done(); it.Advance()) { 171 HBasicBlock* block = it.Current(); 172 173 BitVector* kill = GetKillSet(*block); 174 BitVector* live_in = GetLiveInSet(*block); 175 176 // Set phi inputs of successors of this block corresponding to this block 177 // as live_in. 178 for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) { 179 HBasicBlock* successor = block->GetSuccessors().Get(i); 180 live_in->Union(GetLiveInSet(*successor)); 181 size_t phi_input_index = successor->GetPredecessorIndexOf(block); 182 for (HInstructionIterator inst_it(successor->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 183 HInstruction* phi = inst_it.Current(); 184 HInstruction* input = phi->InputAt(phi_input_index); 185 input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block); 186 // A phi input whose last user is the phi dies at the end of the predecessor block, 187 // and not at the phi's lifetime position. 188 live_in->SetBit(input->GetSsaIndex()); 189 } 190 } 191 192 // Add a range that covers this block to all instructions live_in because of successors. 193 // Instructions defined in this block will have their start of the range adjusted. 194 for (uint32_t idx : live_in->Indexes()) { 195 HInstruction* current = instructions_from_ssa_index_.Get(idx); 196 current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd()); 197 } 198 199 for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); 200 back_it.Advance()) { 201 HInstruction* current = back_it.Current(); 202 if (current->HasSsaIndex()) { 203 // Kill the instruction and shorten its interval. 204 kill->SetBit(current->GetSsaIndex()); 205 live_in->ClearBit(current->GetSsaIndex()); 206 current->GetLiveInterval()->SetFrom(current->GetLifetimePosition()); 207 } 208 209 // All inputs of an instruction must be live. 210 for (size_t i = 0, e = current->InputCount(); i < e; ++i) { 211 HInstruction* input = current->InputAt(i); 212 // Some instructions 'inline' their inputs, that is they do not need 213 // to be materialized. 214 if (input->HasSsaIndex()) { 215 live_in->SetBit(input->GetSsaIndex()); 216 input->GetLiveInterval()->AddUse(current, i, false); 217 } 218 } 219 220 if (current->HasEnvironment()) { 221 // All instructions in the environment must be live. 222 GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs(); 223 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 224 HInstruction* instruction = environment->Get(i); 225 if (instruction != nullptr) { 226 DCHECK(instruction->HasSsaIndex()); 227 live_in->SetBit(instruction->GetSsaIndex()); 228 instruction->GetLiveInterval()->AddUse(current, i, true); 229 } 230 } 231 } 232 } 233 234 // Kill phis defined in this block. 235 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 236 HInstruction* current = inst_it.Current(); 237 if (current->HasSsaIndex()) { 238 kill->SetBit(current->GetSsaIndex()); 239 live_in->ClearBit(current->GetSsaIndex()); 240 LiveInterval* interval = current->GetLiveInterval(); 241 DCHECK((interval->GetFirstRange() == nullptr) 242 || (interval->GetStart() == current->GetLifetimePosition())); 243 interval->SetFrom(current->GetLifetimePosition()); 244 } 245 } 246 247 if (block->IsLoopHeader()) { 248 HBasicBlock* back_edge = block->GetLoopInformation()->GetBackEdges().Get(0); 249 // For all live_in instructions at the loop header, we need to create a range 250 // that covers the full loop. 251 for (uint32_t idx : live_in->Indexes()) { 252 HInstruction* current = instructions_from_ssa_index_.Get(idx); 253 current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(), 254 back_edge->GetLifetimeEnd()); 255 } 256 } 257 } 258} 259 260void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() { 261 bool changed; 262 do { 263 changed = false; 264 265 for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) { 266 const HBasicBlock& block = *it.Current(); 267 268 // The live_in set depends on the kill set (which does not 269 // change in this loop), and the live_out set. If the live_out 270 // set does not change, there is no need to update the live_in set. 271 if (UpdateLiveOut(block) && UpdateLiveIn(block)) { 272 changed = true; 273 } 274 } 275 } while (changed); 276} 277 278bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) { 279 BitVector* live_out = GetLiveOutSet(block); 280 bool changed = false; 281 // The live_out set of a block is the union of live_in sets of its successors. 282 for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) { 283 HBasicBlock* successor = block.GetSuccessors().Get(i); 284 if (live_out->Union(GetLiveInSet(*successor))) { 285 changed = true; 286 } 287 } 288 return changed; 289} 290 291 292bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) { 293 BitVector* live_out = GetLiveOutSet(block); 294 BitVector* kill = GetKillSet(block); 295 BitVector* live_in = GetLiveInSet(block); 296 // If live_out is updated (because of backward branches), we need to make 297 // sure instructions in live_out are also in live_in, unless they are killed 298 // by this block. 299 return live_in->UnionIfNotIn(live_out, kill); 300} 301 302int LiveInterval::FindFirstRegisterHint(size_t* free_until) const { 303 if (GetParent() == this && defined_by_ != nullptr) { 304 // This is the first interval for the instruction. Try to find 305 // a register based on its definition. 306 DCHECK_EQ(defined_by_->GetLiveInterval(), this); 307 int hint = FindHintAtDefinition(); 308 if (hint != kNoRegister && free_until[hint] > GetStart()) { 309 return hint; 310 } 311 } 312 313 UsePosition* use = first_use_; 314 size_t start = GetStart(); 315 size_t end = GetEnd(); 316 while (use != nullptr && use->GetPosition() <= end) { 317 size_t use_position = use->GetPosition(); 318 if (use_position >= start && !use->GetIsEnvironment()) { 319 HInstruction* user = use->GetUser(); 320 size_t input_index = use->GetInputIndex(); 321 if (user->IsPhi()) { 322 // If the phi has a register, try to use the same. 323 Location phi_location = user->GetLiveInterval()->ToLocation(); 324 if (SameRegisterKind(phi_location) && free_until[phi_location.reg()] >= use_position) { 325 return phi_location.reg(); 326 } 327 const GrowableArray<HBasicBlock*>& predecessors = user->GetBlock()->GetPredecessors(); 328 // If the instruction dies at the phi assignment, we can try having the 329 // same register. 330 if (end == predecessors.Get(input_index)->GetLifetimeEnd()) { 331 for (size_t i = 0, e = user->InputCount(); i < e; ++i) { 332 if (i == input_index) { 333 continue; 334 } 335 HInstruction* input = user->InputAt(i); 336 Location location = input->GetLiveInterval()->GetLocationAt( 337 predecessors.Get(i)->GetLifetimeEnd() - 1); 338 if (location.IsRegister() && free_until[location.reg()] >= use_position) { 339 return location.reg(); 340 } 341 } 342 } 343 } else { 344 // If the instruction is expected in a register, try to use it. 345 LocationSummary* locations = user->GetLocations(); 346 Location expected = locations->InAt(use->GetInputIndex()); 347 // We use the user's lifetime position - 1 (and not `use_position`) because the 348 // register is blocked at the beginning of the user. 349 size_t position = user->GetLifetimePosition() - 1; 350 if (SameRegisterKind(expected) && free_until[expected.reg()] >= position) { 351 return expected.reg(); 352 } 353 } 354 } 355 use = use->GetNext(); 356 } 357 358 return kNoRegister; 359} 360 361int LiveInterval::FindHintAtDefinition() const { 362 if (defined_by_->IsPhi()) { 363 // Try to use the same register as one of the inputs. 364 const GrowableArray<HBasicBlock*>& predecessors = defined_by_->GetBlock()->GetPredecessors(); 365 for (size_t i = 0, e = defined_by_->InputCount(); i < e; ++i) { 366 HInstruction* input = defined_by_->InputAt(i); 367 size_t end = predecessors.Get(i)->GetLifetimeEnd(); 368 const LiveInterval& input_interval = input->GetLiveInterval()->GetIntervalAt(end - 1); 369 if (input_interval.GetEnd() == end) { 370 // If the input dies at the end of the predecessor, we know its register can 371 // be reused. 372 Location input_location = input_interval.ToLocation(); 373 if (SameRegisterKind(input_location)) { 374 return input_location.reg(); 375 } 376 } 377 } 378 } else { 379 LocationSummary* locations = GetDefinedBy()->GetLocations(); 380 Location out = locations->Out(); 381 if (out.IsUnallocated() && out.GetPolicy() == Location::kSameAsFirstInput) { 382 // Try to use the same register as the first input. 383 const LiveInterval& input_interval = 384 GetDefinedBy()->InputAt(0)->GetLiveInterval()->GetIntervalAt(GetStart() - 1); 385 if (input_interval.GetEnd() == GetStart()) { 386 // If the input dies at the start of this instruction, we know its register can 387 // be reused. 388 Location location = input_interval.ToLocation(); 389 if (SameRegisterKind(location)) { 390 return location.reg(); 391 } 392 } 393 } 394 } 395 return kNoRegister; 396} 397 398bool LiveInterval::SameRegisterKind(Location other) const { 399 return IsFloatingPoint() 400 ? other.IsFpuRegister() 401 : other.IsRegister(); 402} 403 404bool LiveInterval::NeedsTwoSpillSlots() const { 405 return type_ == Primitive::kPrimLong || type_ == Primitive::kPrimDouble; 406} 407 408Location LiveInterval::ToLocation() const { 409 if (HasRegister()) { 410 return IsFloatingPoint() 411 ? Location::FpuRegisterLocation(GetRegister()) 412 : Location::RegisterLocation(GetRegister()); 413 } else { 414 HInstruction* defined_by = GetParent()->GetDefinedBy(); 415 if (defined_by->IsConstant()) { 416 return defined_by->GetLocations()->Out(); 417 } else if (GetParent()->HasSpillSlot()) { 418 if (NeedsTwoSpillSlots()) { 419 return Location::DoubleStackSlot(GetParent()->GetSpillSlot()); 420 } else { 421 return Location::StackSlot(GetParent()->GetSpillSlot()); 422 } 423 } else { 424 return Location(); 425 } 426 } 427} 428 429Location LiveInterval::GetLocationAt(size_t position) const { 430 return GetIntervalAt(position).ToLocation(); 431} 432 433const LiveInterval& LiveInterval::GetIntervalAt(size_t position) const { 434 const LiveInterval* current = this; 435 while (!current->Covers(position)) { 436 current = current->GetNextSibling(); 437 DCHECK(current != nullptr); 438 } 439 return *current; 440} 441 442} // namespace art 443