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