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