ssa_liveness_analysis.cc revision 674f519fe00ae07e0db90c4374f785bb418ae332
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 IsLoop(HLoopInformation* info) { 32 return info != nullptr; 33} 34 35static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { 36 return first_loop == second_loop; 37} 38 39static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { 40 return (inner != outer) 41 && (inner != nullptr) 42 && (outer != nullptr) 43 && inner->IsIn(*outer); 44} 45 46static void AddToListForLinearization(ArenaVector<HBasicBlock*>* worklist, HBasicBlock* block) { 47 HLoopInformation* block_loop = block->GetLoopInformation(); 48 auto insert_pos = worklist->rbegin(); // insert_pos.base() will be the actual position. 49 for (auto end = worklist->rend(); insert_pos != end; ++insert_pos) { 50 HBasicBlock* current = *insert_pos; 51 HLoopInformation* current_loop = current->GetLoopInformation(); 52 if (InSameLoop(block_loop, current_loop) 53 || !IsLoop(current_loop) 54 || IsInnerLoop(current_loop, block_loop)) { 55 // The block can be processed immediately. 56 break; 57 } 58 } 59 worklist->insert(insert_pos.base(), block); 60} 61 62void SsaLivenessAnalysis::LinearizeGraph() { 63 // Create a reverse post ordering with the following properties: 64 // - Blocks in a loop are consecutive, 65 // - Back-edge is the last block before loop exits. 66 67 // (1): Record the number of forward predecessors for each block. This is to 68 // ensure the resulting order is reverse post order. We could use the 69 // current reverse post order in the graph, but it would require making 70 // order queries to a GrowableArray, which is not the best data structure 71 // for it. 72 ArenaVector<uint32_t> forward_predecessors(graph_->GetBlocks().size(), 73 graph_->GetArena()->Adapter(kArenaAllocSsaLiveness)); 74 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 75 HBasicBlock* block = it.Current(); 76 size_t number_of_forward_predecessors = block->GetPredecessors().size(); 77 if (block->IsLoopHeader()) { 78 number_of_forward_predecessors -= block->GetLoopInformation()->NumberOfBackEdges(); 79 } 80 forward_predecessors[block->GetBlockId()] = number_of_forward_predecessors; 81 } 82 83 // (2): Following a worklist approach, first start with the entry block, and 84 // iterate over the successors. When all non-back edge predecessors of a 85 // successor block are visited, the successor block is added in the worklist 86 // following an order that satisfies the requirements to build our linear graph. 87 graph_->linear_order_.reserve(graph_->GetReversePostOrder().size()); 88 ArenaVector<HBasicBlock*> worklist(graph_->GetArena()->Adapter(kArenaAllocSsaLiveness)); 89 worklist.push_back(graph_->GetEntryBlock()); 90 do { 91 HBasicBlock* current = worklist.back(); 92 worklist.pop_back(); 93 graph_->linear_order_.push_back(current); 94 for (HBasicBlock* successor : current->GetSuccessors()) { 95 int block_id = successor->GetBlockId(); 96 size_t number_of_remaining_predecessors = forward_predecessors[block_id]; 97 if (number_of_remaining_predecessors == 1) { 98 AddToListForLinearization(&worklist, successor); 99 } 100 forward_predecessors[block_id] = number_of_remaining_predecessors - 1; 101 } 102 } while (!worklist.empty()); 103} 104 105void SsaLivenessAnalysis::NumberInstructions() { 106 int ssa_index = 0; 107 size_t lifetime_position = 0; 108 // Each instruction gets a lifetime position, and a block gets a lifetime 109 // start and end position. Non-phi instructions have a distinct lifetime position than 110 // the block they are in. Phi instructions have the lifetime start of their block as 111 // lifetime position. 112 // 113 // Because the register allocator will insert moves in the graph, we need 114 // to differentiate between the start and end of an instruction. Adding 2 to 115 // the lifetime position for each instruction ensures the start of an 116 // instruction is different than the end of the previous instruction. 117 for (HLinearOrderIterator it(*graph_); !it.Done(); it.Advance()) { 118 HBasicBlock* block = it.Current(); 119 block->SetLifetimeStart(lifetime_position); 120 121 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 122 HInstruction* current = inst_it.Current(); 123 codegen_->AllocateLocations(current); 124 LocationSummary* locations = current->GetLocations(); 125 if (locations != nullptr && locations->Out().IsValid()) { 126 instructions_from_ssa_index_.push_back(current); 127 current->SetSsaIndex(ssa_index++); 128 current->SetLiveInterval( 129 LiveInterval::MakeInterval(graph_->GetArena(), current->GetType(), current)); 130 } 131 current->SetLifetimePosition(lifetime_position); 132 } 133 lifetime_position += 2; 134 135 // Add a null marker to notify we are starting a block. 136 instructions_from_lifetime_position_.push_back(nullptr); 137 138 for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done(); 139 inst_it.Advance()) { 140 HInstruction* current = inst_it.Current(); 141 codegen_->AllocateLocations(current); 142 LocationSummary* locations = current->GetLocations(); 143 if (locations != nullptr && locations->Out().IsValid()) { 144 instructions_from_ssa_index_.push_back(current); 145 current->SetSsaIndex(ssa_index++); 146 current->SetLiveInterval( 147 LiveInterval::MakeInterval(graph_->GetArena(), current->GetType(), current)); 148 } 149 instructions_from_lifetime_position_.push_back(current); 150 current->SetLifetimePosition(lifetime_position); 151 lifetime_position += 2; 152 } 153 154 block->SetLifetimeEnd(lifetime_position); 155 } 156 number_of_ssa_values_ = ssa_index; 157} 158 159void SsaLivenessAnalysis::ComputeLiveness() { 160 for (HLinearOrderIterator it(*graph_); !it.Done(); it.Advance()) { 161 HBasicBlock* block = it.Current(); 162 block_infos_[block->GetBlockId()] = 163 new (graph_->GetArena()) BlockInfo(graph_->GetArena(), *block, number_of_ssa_values_); 164 } 165 166 // Compute the live ranges, as well as the initial live_in, live_out, and kill sets. 167 // This method does not handle backward branches for the sets, therefore live_in 168 // and live_out sets are not yet correct. 169 ComputeLiveRanges(); 170 171 // Do a fixed point calculation to take into account backward branches, 172 // that will update live_in of loop headers, and therefore live_out and live_in 173 // of blocks in the loop. 174 ComputeLiveInAndLiveOutSets(); 175} 176 177static void RecursivelyProcessInputs(HInstruction* current, 178 HInstruction* actual_user, 179 BitVector* live_in) { 180 for (size_t i = 0, e = current->InputCount(); i < e; ++i) { 181 HInstruction* input = current->InputAt(i); 182 bool has_in_location = current->GetLocations()->InAt(i).IsValid(); 183 bool has_out_location = input->GetLocations()->Out().IsValid(); 184 185 if (has_in_location) { 186 DCHECK(has_out_location) 187 << "Instruction " << current->DebugName() << current->GetId() 188 << " expects an input value at index " << i << " but " 189 << input->DebugName() << input->GetId() << " does not produce one."; 190 DCHECK(input->HasSsaIndex()); 191 // `input` generates a result used by `current`. Add use and update 192 // the live-in set. 193 input->GetLiveInterval()->AddUse(current, /* environment */ nullptr, i, actual_user); 194 live_in->SetBit(input->GetSsaIndex()); 195 } else if (has_out_location) { 196 // `input` generates a result but it is not used by `current`. 197 } else { 198 // `input` is inlined into `current`. Walk over its inputs and record 199 // uses at `current`. 200 DCHECK(input->IsEmittedAtUseSite()); 201 // Check that the inlined input is not a phi. Recursing on loop phis could 202 // lead to an infinite loop. 203 DCHECK(!input->IsPhi()); 204 RecursivelyProcessInputs(input, actual_user, live_in); 205 } 206 } 207} 208 209void SsaLivenessAnalysis::ComputeLiveRanges() { 210 // Do a post order visit, adding inputs of instructions live in the block where 211 // that instruction is defined, and killing instructions that are being visited. 212 for (HLinearPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 213 HBasicBlock* block = it.Current(); 214 215 BitVector* kill = GetKillSet(*block); 216 BitVector* live_in = GetLiveInSet(*block); 217 218 // Set phi inputs of successors of this block corresponding to this block 219 // as live_in. 220 for (HBasicBlock* successor : block->GetSuccessors()) { 221 live_in->Union(GetLiveInSet(*successor)); 222 if (successor->IsCatchBlock()) { 223 // Inputs of catch phis will be kept alive through their environment 224 // uses, allowing the runtime to copy their values to the corresponding 225 // catch phi spill slots when an exception is thrown. 226 // The only instructions which may not be recorded in the environments 227 // are constants created by the SSA builder as typed equivalents of 228 // untyped constants from the bytecode, or phis with only such constants 229 // as inputs (verified by SSAChecker). Their raw binary value must 230 // therefore be the same and we only need to keep alive one. 231 } else { 232 size_t phi_input_index = successor->GetPredecessorIndexOf(block); 233 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 234 HInstruction* phi = phi_it.Current(); 235 HInstruction* input = phi->InputAt(phi_input_index); 236 input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block); 237 // A phi input whose last user is the phi dies at the end of the predecessor block, 238 // and not at the phi's lifetime position. 239 live_in->SetBit(input->GetSsaIndex()); 240 } 241 } 242 } 243 244 // Add a range that covers this block to all instructions live_in because of successors. 245 // Instructions defined in this block will have their start of the range adjusted. 246 for (uint32_t idx : live_in->Indexes()) { 247 HInstruction* current = GetInstructionFromSsaIndex(idx); 248 current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd()); 249 } 250 251 for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); 252 back_it.Advance()) { 253 HInstruction* current = back_it.Current(); 254 if (current->HasSsaIndex()) { 255 // Kill the instruction and shorten its interval. 256 kill->SetBit(current->GetSsaIndex()); 257 live_in->ClearBit(current->GetSsaIndex()); 258 current->GetLiveInterval()->SetFrom(current->GetLifetimePosition()); 259 } 260 261 // Process the environment first, because we know their uses come after 262 // or at the same liveness position of inputs. 263 for (HEnvironment* environment = current->GetEnvironment(); 264 environment != nullptr; 265 environment = environment->GetParent()) { 266 // Handle environment uses. See statements (b) and (c) of the 267 // SsaLivenessAnalysis. 268 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 269 HInstruction* instruction = environment->GetInstructionAt(i); 270 bool should_be_live = ShouldBeLiveForEnvironment(current, instruction); 271 if (should_be_live) { 272 DCHECK(instruction->HasSsaIndex()); 273 live_in->SetBit(instruction->GetSsaIndex()); 274 } 275 if (instruction != nullptr) { 276 instruction->GetLiveInterval()->AddUse( 277 current, environment, i, /* actual_user */ nullptr, should_be_live); 278 } 279 } 280 } 281 282 // Process inputs of instructions. 283 if (current->IsEmittedAtUseSite()) { 284 if (kIsDebugBuild) { 285 DCHECK(!current->GetLocations()->Out().IsValid()); 286 for (HUseIterator<HInstruction*> use_it(current->GetUses()); 287 !use_it.Done(); 288 use_it.Advance()) { 289 HInstruction* user = use_it.Current()->GetUser(); 290 size_t index = use_it.Current()->GetIndex(); 291 DCHECK(!user->GetLocations()->InAt(index).IsValid()); 292 } 293 DCHECK(!current->HasEnvironmentUses()); 294 } 295 } else { 296 RecursivelyProcessInputs(current, current, live_in); 297 } 298 } 299 300 // Kill phis defined in this block. 301 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 302 HInstruction* current = inst_it.Current(); 303 if (current->HasSsaIndex()) { 304 kill->SetBit(current->GetSsaIndex()); 305 live_in->ClearBit(current->GetSsaIndex()); 306 LiveInterval* interval = current->GetLiveInterval(); 307 DCHECK((interval->GetFirstRange() == nullptr) 308 || (interval->GetStart() == current->GetLifetimePosition())); 309 interval->SetFrom(current->GetLifetimePosition()); 310 } 311 } 312 313 if (block->IsLoopHeader()) { 314 if (kIsDebugBuild && block->GetLoopInformation()->IsIrreducible()) { 315 // To satisfy our liveness algorithm, we need to ensure loop headers of 316 // irreducible loops do not have any live-in instructions, except constants 317 // and the current method, which can be trivially re-materialized. 318 for (uint32_t idx : live_in->Indexes()) { 319 HInstruction* instruction = GetInstructionFromSsaIndex(idx); 320 DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName(); 321 DCHECK(!instruction->IsParameterValue()) << instruction->DebugName(); 322 DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant()) 323 << instruction->DebugName(); 324 } 325 } 326 size_t last_position = block->GetLoopInformation()->GetLifetimeEnd(); 327 // For all live_in instructions at the loop header, we need to create a range 328 // that covers the full loop. 329 for (uint32_t idx : live_in->Indexes()) { 330 HInstruction* current = GetInstructionFromSsaIndex(idx); 331 current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(), last_position); 332 } 333 } 334 } 335} 336 337void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() { 338 bool changed; 339 do { 340 changed = false; 341 342 for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 343 const HBasicBlock& block = *it.Current(); 344 345 // The live_in set depends on the kill set (which does not 346 // change in this loop), and the live_out set. If the live_out 347 // set does not change, there is no need to update the live_in set. 348 if (UpdateLiveOut(block) && UpdateLiveIn(block)) { 349 changed = true; 350 } 351 } 352 } while (changed); 353} 354 355bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) { 356 BitVector* live_out = GetLiveOutSet(block); 357 bool changed = false; 358 // The live_out set of a block is the union of live_in sets of its successors. 359 for (HBasicBlock* successor : block.GetSuccessors()) { 360 if (live_out->Union(GetLiveInSet(*successor))) { 361 changed = true; 362 } 363 } 364 return changed; 365} 366 367 368bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) { 369 BitVector* live_out = GetLiveOutSet(block); 370 BitVector* kill = GetKillSet(block); 371 BitVector* live_in = GetLiveInSet(block); 372 // If live_out is updated (because of backward branches), we need to make 373 // sure instructions in live_out are also in live_in, unless they are killed 374 // by this block. 375 return live_in->UnionIfNotIn(live_out, kill); 376} 377 378static int RegisterOrLowRegister(Location location) { 379 return location.IsPair() ? location.low() : location.reg(); 380} 381 382int LiveInterval::FindFirstRegisterHint(size_t* free_until, 383 const SsaLivenessAnalysis& liveness) const { 384 DCHECK(!IsHighInterval()); 385 if (IsTemp()) return kNoRegister; 386 387 if (GetParent() == this && defined_by_ != nullptr) { 388 // This is the first interval for the instruction. Try to find 389 // a register based on its definition. 390 DCHECK_EQ(defined_by_->GetLiveInterval(), this); 391 int hint = FindHintAtDefinition(); 392 if (hint != kNoRegister && free_until[hint] > GetStart()) { 393 return hint; 394 } 395 } 396 397 if (IsSplit() && liveness.IsAtBlockBoundary(GetStart() / 2)) { 398 // If the start of this interval is at a block boundary, we look at the 399 // location of the interval in blocks preceding the block this interval 400 // starts at. If one location is a register we return it as a hint. This 401 // will avoid a move between the two blocks. 402 HBasicBlock* block = liveness.GetBlockFromPosition(GetStart() / 2); 403 size_t next_register_use = FirstRegisterUse(); 404 for (HBasicBlock* predecessor : block->GetPredecessors()) { 405 size_t position = predecessor->GetLifetimeEnd() - 1; 406 // We know positions above GetStart() do not have a location yet. 407 if (position < GetStart()) { 408 LiveInterval* existing = GetParent()->GetSiblingAt(position); 409 if (existing != nullptr 410 && existing->HasRegister() 411 // It's worth using that register if it is available until 412 // the next use. 413 && (free_until[existing->GetRegister()] >= next_register_use)) { 414 return existing->GetRegister(); 415 } 416 } 417 } 418 } 419 420 UsePosition* use = first_use_; 421 size_t start = GetStart(); 422 size_t end = GetEnd(); 423 while (use != nullptr && use->GetPosition() <= end) { 424 size_t use_position = use->GetPosition(); 425 if (use_position >= start && !use->IsSynthesized()) { 426 HInstruction* user = use->GetUser(); 427 size_t input_index = use->GetInputIndex(); 428 if (user->IsPhi()) { 429 // If the phi has a register, try to use the same. 430 Location phi_location = user->GetLiveInterval()->ToLocation(); 431 if (phi_location.IsRegisterKind()) { 432 DCHECK(SameRegisterKind(phi_location)); 433 int reg = RegisterOrLowRegister(phi_location); 434 if (free_until[reg] >= use_position) { 435 return reg; 436 } 437 } 438 // If the instruction dies at the phi assignment, we can try having the 439 // same register. 440 if (end == user->GetBlock()->GetPredecessors()[input_index]->GetLifetimeEnd()) { 441 for (size_t i = 0, e = user->InputCount(); i < e; ++i) { 442 if (i == input_index) { 443 continue; 444 } 445 HInstruction* input = user->InputAt(i); 446 Location location = input->GetLiveInterval()->GetLocationAt( 447 user->GetBlock()->GetPredecessors()[i]->GetLifetimeEnd() - 1); 448 if (location.IsRegisterKind()) { 449 int reg = RegisterOrLowRegister(location); 450 if (free_until[reg] >= use_position) { 451 return reg; 452 } 453 } 454 } 455 } 456 } else { 457 // If the instruction is expected in a register, try to use it. 458 LocationSummary* locations = user->GetLocations(); 459 Location expected = locations->InAt(use->GetInputIndex()); 460 // We use the user's lifetime position - 1 (and not `use_position`) because the 461 // register is blocked at the beginning of the user. 462 size_t position = user->GetLifetimePosition() - 1; 463 if (expected.IsRegisterKind()) { 464 DCHECK(SameRegisterKind(expected)); 465 int reg = RegisterOrLowRegister(expected); 466 if (free_until[reg] >= position) { 467 return reg; 468 } 469 } 470 } 471 } 472 use = use->GetNext(); 473 } 474 475 return kNoRegister; 476} 477 478int LiveInterval::FindHintAtDefinition() const { 479 if (defined_by_->IsPhi()) { 480 // Try to use the same register as one of the inputs. 481 const ArenaVector<HBasicBlock*>& predecessors = defined_by_->GetBlock()->GetPredecessors(); 482 for (size_t i = 0, e = defined_by_->InputCount(); i < e; ++i) { 483 HInstruction* input = defined_by_->InputAt(i); 484 size_t end = predecessors[i]->GetLifetimeEnd(); 485 LiveInterval* input_interval = input->GetLiveInterval()->GetSiblingAt(end - 1); 486 if (input_interval->GetEnd() == end) { 487 // If the input dies at the end of the predecessor, we know its register can 488 // be reused. 489 Location input_location = input_interval->ToLocation(); 490 if (input_location.IsRegisterKind()) { 491 DCHECK(SameRegisterKind(input_location)); 492 return RegisterOrLowRegister(input_location); 493 } 494 } 495 } 496 } else { 497 LocationSummary* locations = GetDefinedBy()->GetLocations(); 498 Location out = locations->Out(); 499 if (out.IsUnallocated() && out.GetPolicy() == Location::kSameAsFirstInput) { 500 // Try to use the same register as the first input. 501 LiveInterval* input_interval = 502 GetDefinedBy()->InputAt(0)->GetLiveInterval()->GetSiblingAt(GetStart() - 1); 503 if (input_interval->GetEnd() == GetStart()) { 504 // If the input dies at the start of this instruction, we know its register can 505 // be reused. 506 Location location = input_interval->ToLocation(); 507 if (location.IsRegisterKind()) { 508 DCHECK(SameRegisterKind(location)); 509 return RegisterOrLowRegister(location); 510 } 511 } 512 } 513 } 514 return kNoRegister; 515} 516 517bool LiveInterval::SameRegisterKind(Location other) const { 518 if (IsFloatingPoint()) { 519 if (IsLowInterval() || IsHighInterval()) { 520 return other.IsFpuRegisterPair(); 521 } else { 522 return other.IsFpuRegister(); 523 } 524 } else { 525 if (IsLowInterval() || IsHighInterval()) { 526 return other.IsRegisterPair(); 527 } else { 528 return other.IsRegister(); 529 } 530 } 531} 532 533bool LiveInterval::NeedsTwoSpillSlots() const { 534 return type_ == Primitive::kPrimLong || type_ == Primitive::kPrimDouble; 535} 536 537Location LiveInterval::ToLocation() const { 538 DCHECK(!IsHighInterval()); 539 if (HasRegister()) { 540 if (IsFloatingPoint()) { 541 if (HasHighInterval()) { 542 return Location::FpuRegisterPairLocation(GetRegister(), GetHighInterval()->GetRegister()); 543 } else { 544 return Location::FpuRegisterLocation(GetRegister()); 545 } 546 } else { 547 if (HasHighInterval()) { 548 return Location::RegisterPairLocation(GetRegister(), GetHighInterval()->GetRegister()); 549 } else { 550 return Location::RegisterLocation(GetRegister()); 551 } 552 } 553 } else { 554 HInstruction* defined_by = GetParent()->GetDefinedBy(); 555 if (defined_by->IsConstant()) { 556 return defined_by->GetLocations()->Out(); 557 } else if (GetParent()->HasSpillSlot()) { 558 if (NeedsTwoSpillSlots()) { 559 return Location::DoubleStackSlot(GetParent()->GetSpillSlot()); 560 } else { 561 return Location::StackSlot(GetParent()->GetSpillSlot()); 562 } 563 } else { 564 return Location(); 565 } 566 } 567} 568 569Location LiveInterval::GetLocationAt(size_t position) { 570 LiveInterval* sibling = GetSiblingAt(position); 571 DCHECK(sibling != nullptr); 572 return sibling->ToLocation(); 573} 574 575LiveInterval* LiveInterval::GetSiblingAt(size_t position) { 576 LiveInterval* current = this; 577 while (current != nullptr && !current->IsDefinedAt(position)) { 578 current = current->GetNextSibling(); 579 } 580 return current; 581} 582 583} // namespace art 584