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