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 "linear_order.h"
22#include "nodes.h"
23
24namespace art {
25
26void SsaLivenessAnalysis::Analyze() {
27  // Compute the linear order directly in the graph's data structure
28  // (there are no more following graph mutations).
29  LinearizeGraph(graph_, graph_->GetArena(), &graph_->linear_order_);
30
31  // Liveness analysis.
32  NumberInstructions();
33  ComputeLiveness();
34}
35
36void SsaLivenessAnalysis::NumberInstructions() {
37  int ssa_index = 0;
38  size_t lifetime_position = 0;
39  // Each instruction gets a lifetime position, and a block gets a lifetime
40  // start and end position. Non-phi instructions have a distinct lifetime position than
41  // the block they are in. Phi instructions have the lifetime start of their block as
42  // lifetime position.
43  //
44  // Because the register allocator will insert moves in the graph, we need
45  // to differentiate between the start and end of an instruction. Adding 2 to
46  // the lifetime position for each instruction ensures the start of an
47  // instruction is different than the end of the previous instruction.
48  for (HBasicBlock* block : graph_->GetLinearOrder()) {
49    block->SetLifetimeStart(lifetime_position);
50
51    for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
52      HInstruction* current = inst_it.Current();
53      codegen_->AllocateLocations(current);
54      LocationSummary* locations = current->GetLocations();
55      if (locations != nullptr && locations->Out().IsValid()) {
56        instructions_from_ssa_index_.push_back(current);
57        current->SetSsaIndex(ssa_index++);
58        current->SetLiveInterval(
59            LiveInterval::MakeInterval(graph_->GetArena(), current->GetType(), current));
60      }
61      current->SetLifetimePosition(lifetime_position);
62    }
63    lifetime_position += 2;
64
65    // Add a null marker to notify we are starting a block.
66    instructions_from_lifetime_position_.push_back(nullptr);
67
68    for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done();
69         inst_it.Advance()) {
70      HInstruction* current = inst_it.Current();
71      codegen_->AllocateLocations(current);
72      LocationSummary* locations = current->GetLocations();
73      if (locations != nullptr && locations->Out().IsValid()) {
74        instructions_from_ssa_index_.push_back(current);
75        current->SetSsaIndex(ssa_index++);
76        current->SetLiveInterval(
77            LiveInterval::MakeInterval(graph_->GetArena(), current->GetType(), current));
78      }
79      instructions_from_lifetime_position_.push_back(current);
80      current->SetLifetimePosition(lifetime_position);
81      lifetime_position += 2;
82    }
83
84    block->SetLifetimeEnd(lifetime_position);
85  }
86  number_of_ssa_values_ = ssa_index;
87}
88
89void SsaLivenessAnalysis::ComputeLiveness() {
90  for (HBasicBlock* block : graph_->GetLinearOrder()) {
91    block_infos_[block->GetBlockId()] =
92        new (graph_->GetArena()) BlockInfo(graph_->GetArena(), *block, number_of_ssa_values_);
93  }
94
95  // Compute the live ranges, as well as the initial live_in, live_out, and kill sets.
96  // This method does not handle backward branches for the sets, therefore live_in
97  // and live_out sets are not yet correct.
98  ComputeLiveRanges();
99
100  // Do a fixed point calculation to take into account backward branches,
101  // that will update live_in of loop headers, and therefore live_out and live_in
102  // of blocks in the loop.
103  ComputeLiveInAndLiveOutSets();
104}
105
106static void RecursivelyProcessInputs(HInstruction* current,
107                                     HInstruction* actual_user,
108                                     BitVector* live_in) {
109  HInputsRef inputs = current->GetInputs();
110  for (size_t i = 0; i < inputs.size(); ++i) {
111    HInstruction* input = inputs[i];
112    bool has_in_location = current->GetLocations()->InAt(i).IsValid();
113    bool has_out_location = input->GetLocations()->Out().IsValid();
114
115    if (has_in_location) {
116      DCHECK(has_out_location)
117          << "Instruction " << current->DebugName() << current->GetId()
118          << " expects an input value at index " << i << " but "
119          << input->DebugName() << input->GetId() << " does not produce one.";
120      DCHECK(input->HasSsaIndex());
121      // `input` generates a result used by `current`. Add use and update
122      // the live-in set.
123      input->GetLiveInterval()->AddUse(current, /* environment */ nullptr, i, actual_user);
124      live_in->SetBit(input->GetSsaIndex());
125    } else if (has_out_location) {
126      // `input` generates a result but it is not used by `current`.
127    } else {
128      // `input` is inlined into `current`. Walk over its inputs and record
129      // uses at `current`.
130      DCHECK(input->IsEmittedAtUseSite());
131      // Check that the inlined input is not a phi. Recursing on loop phis could
132      // lead to an infinite loop.
133      DCHECK(!input->IsPhi());
134      RecursivelyProcessInputs(input, actual_user, live_in);
135    }
136  }
137}
138
139void SsaLivenessAnalysis::ComputeLiveRanges() {
140  // Do a post order visit, adding inputs of instructions live in the block where
141  // that instruction is defined, and killing instructions that are being visited.
142  for (HBasicBlock* block : ReverseRange(graph_->GetLinearOrder())) {
143    BitVector* kill = GetKillSet(*block);
144    BitVector* live_in = GetLiveInSet(*block);
145
146    // Set phi inputs of successors of this block corresponding to this block
147    // as live_in.
148    for (HBasicBlock* successor : block->GetSuccessors()) {
149      live_in->Union(GetLiveInSet(*successor));
150      if (successor->IsCatchBlock()) {
151        // Inputs of catch phis will be kept alive through their environment
152        // uses, allowing the runtime to copy their values to the corresponding
153        // catch phi spill slots when an exception is thrown.
154        // The only instructions which may not be recorded in the environments
155        // are constants created by the SSA builder as typed equivalents of
156        // untyped constants from the bytecode, or phis with only such constants
157        // as inputs (verified by GraphChecker). Their raw binary value must
158        // therefore be the same and we only need to keep alive one.
159      } else {
160        size_t phi_input_index = successor->GetPredecessorIndexOf(block);
161        for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
162          HInstruction* phi = phi_it.Current();
163          HInstruction* input = phi->InputAt(phi_input_index);
164          input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block);
165          // A phi input whose last user is the phi dies at the end of the predecessor block,
166          // and not at the phi's lifetime position.
167          live_in->SetBit(input->GetSsaIndex());
168        }
169      }
170    }
171
172    // Add a range that covers this block to all instructions live_in because of successors.
173    // Instructions defined in this block will have their start of the range adjusted.
174    for (uint32_t idx : live_in->Indexes()) {
175      HInstruction* current = GetInstructionFromSsaIndex(idx);
176      current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
177    }
178
179    for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done();
180         back_it.Advance()) {
181      HInstruction* current = back_it.Current();
182      if (current->HasSsaIndex()) {
183        // Kill the instruction and shorten its interval.
184        kill->SetBit(current->GetSsaIndex());
185        live_in->ClearBit(current->GetSsaIndex());
186        current->GetLiveInterval()->SetFrom(current->GetLifetimePosition());
187      }
188
189      // Process the environment first, because we know their uses come after
190      // or at the same liveness position of inputs.
191      for (HEnvironment* environment = current->GetEnvironment();
192           environment != nullptr;
193           environment = environment->GetParent()) {
194        // Handle environment uses. See statements (b) and (c) of the
195        // SsaLivenessAnalysis.
196        for (size_t i = 0, e = environment->Size(); i < e; ++i) {
197          HInstruction* instruction = environment->GetInstructionAt(i);
198          bool should_be_live = ShouldBeLiveForEnvironment(current, instruction);
199          if (should_be_live) {
200            DCHECK(instruction->HasSsaIndex());
201            live_in->SetBit(instruction->GetSsaIndex());
202          }
203          if (instruction != nullptr) {
204            instruction->GetLiveInterval()->AddUse(
205                current, environment, i, /* actual_user */ nullptr, should_be_live);
206          }
207        }
208      }
209
210      // Process inputs of instructions.
211      if (current->IsEmittedAtUseSite()) {
212        if (kIsDebugBuild) {
213          DCHECK(!current->GetLocations()->Out().IsValid());
214          for (const HUseListNode<HInstruction*>& use : current->GetUses()) {
215            HInstruction* user = use.GetUser();
216            size_t index = use.GetIndex();
217            DCHECK(!user->GetLocations()->InAt(index).IsValid());
218          }
219          DCHECK(!current->HasEnvironmentUses());
220        }
221      } else {
222        RecursivelyProcessInputs(current, current, live_in);
223      }
224    }
225
226    // Kill phis defined in this block.
227    for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
228      HInstruction* current = inst_it.Current();
229      if (current->HasSsaIndex()) {
230        kill->SetBit(current->GetSsaIndex());
231        live_in->ClearBit(current->GetSsaIndex());
232        LiveInterval* interval = current->GetLiveInterval();
233        DCHECK((interval->GetFirstRange() == nullptr)
234               || (interval->GetStart() == current->GetLifetimePosition()));
235        interval->SetFrom(current->GetLifetimePosition());
236      }
237    }
238
239    if (block->IsLoopHeader()) {
240      if (kIsDebugBuild) {
241        CheckNoLiveInIrreducibleLoop(*block);
242      }
243      size_t last_position = block->GetLoopInformation()->GetLifetimeEnd();
244      // For all live_in instructions at the loop header, we need to create a range
245      // that covers the full loop.
246      for (uint32_t idx : live_in->Indexes()) {
247        HInstruction* current = GetInstructionFromSsaIndex(idx);
248        current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(), last_position);
249      }
250    }
251  }
252}
253
254void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
255  bool changed;
256  do {
257    changed = false;
258
259    for (const HBasicBlock* block : graph_->GetPostOrder()) {
260      // The live_in set depends on the kill set (which does not
261      // change in this loop), and the live_out set.  If the live_out
262      // set does not change, there is no need to update the live_in set.
263      if (UpdateLiveOut(*block) && UpdateLiveIn(*block)) {
264        if (kIsDebugBuild) {
265          CheckNoLiveInIrreducibleLoop(*block);
266        }
267        changed = true;
268      }
269    }
270  } while (changed);
271}
272
273bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) {
274  BitVector* live_out = GetLiveOutSet(block);
275  bool changed = false;
276  // The live_out set of a block is the union of live_in sets of its successors.
277  for (HBasicBlock* successor : block.GetSuccessors()) {
278    if (live_out->Union(GetLiveInSet(*successor))) {
279      changed = true;
280    }
281  }
282  return changed;
283}
284
285
286bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) {
287  BitVector* live_out = GetLiveOutSet(block);
288  BitVector* kill = GetKillSet(block);
289  BitVector* live_in = GetLiveInSet(block);
290  // If live_out is updated (because of backward branches), we need to make
291  // sure instructions in live_out are also in live_in, unless they are killed
292  // by this block.
293  return live_in->UnionIfNotIn(live_out, kill);
294}
295
296void LiveInterval::DumpWithContext(std::ostream& stream,
297                                   const CodeGenerator& codegen) const {
298  Dump(stream);
299  if (IsFixed()) {
300    stream << ", register:" << GetRegister() << "(";
301    if (IsFloatingPoint()) {
302      codegen.DumpFloatingPointRegister(stream, GetRegister());
303    } else {
304      codegen.DumpCoreRegister(stream, GetRegister());
305    }
306    stream << ")";
307  } else {
308    stream << ", spill slot:" << GetSpillSlot();
309  }
310  stream << ", requires_register:" << (GetDefinedBy() != nullptr && RequiresRegister());
311  if (GetParent()->GetDefinedBy() != nullptr) {
312    stream << ", defined_by:" << GetParent()->GetDefinedBy()->GetKind();
313    stream << "(" << GetParent()->GetDefinedBy()->GetLifetimePosition() << ")";
314  }
315}
316
317static int RegisterOrLowRegister(Location location) {
318  return location.IsPair() ? location.low() : location.reg();
319}
320
321int LiveInterval::FindFirstRegisterHint(size_t* free_until,
322                                        const SsaLivenessAnalysis& liveness) const {
323  DCHECK(!IsHighInterval());
324  if (IsTemp()) return kNoRegister;
325
326  if (GetParent() == this && defined_by_ != nullptr) {
327    // This is the first interval for the instruction. Try to find
328    // a register based on its definition.
329    DCHECK_EQ(defined_by_->GetLiveInterval(), this);
330    int hint = FindHintAtDefinition();
331    if (hint != kNoRegister && free_until[hint] > GetStart()) {
332      return hint;
333    }
334  }
335
336  if (IsSplit() && liveness.IsAtBlockBoundary(GetStart() / 2)) {
337    // If the start of this interval is at a block boundary, we look at the
338    // location of the interval in blocks preceding the block this interval
339    // starts at. If one location is a register we return it as a hint. This
340    // will avoid a move between the two blocks.
341    HBasicBlock* block = liveness.GetBlockFromPosition(GetStart() / 2);
342    size_t next_register_use = FirstRegisterUse();
343    for (HBasicBlock* predecessor : block->GetPredecessors()) {
344      size_t position = predecessor->GetLifetimeEnd() - 1;
345      // We know positions above GetStart() do not have a location yet.
346      if (position < GetStart()) {
347        LiveInterval* existing = GetParent()->GetSiblingAt(position);
348        if (existing != nullptr
349            && existing->HasRegister()
350            // It's worth using that register if it is available until
351            // the next use.
352            && (free_until[existing->GetRegister()] >= next_register_use)) {
353          return existing->GetRegister();
354        }
355      }
356    }
357  }
358
359  UsePosition* use = first_use_;
360  size_t start = GetStart();
361  size_t end = GetEnd();
362  while (use != nullptr && use->GetPosition() <= end) {
363    size_t use_position = use->GetPosition();
364    if (use_position >= start && !use->IsSynthesized()) {
365      HInstruction* user = use->GetUser();
366      size_t input_index = use->GetInputIndex();
367      if (user->IsPhi()) {
368        // If the phi has a register, try to use the same.
369        Location phi_location = user->GetLiveInterval()->ToLocation();
370        if (phi_location.IsRegisterKind()) {
371          DCHECK(SameRegisterKind(phi_location));
372          int reg = RegisterOrLowRegister(phi_location);
373          if (free_until[reg] >= use_position) {
374            return reg;
375          }
376        }
377        // If the instruction dies at the phi assignment, we can try having the
378        // same register.
379        if (end == user->GetBlock()->GetPredecessors()[input_index]->GetLifetimeEnd()) {
380          HInputsRef inputs = user->GetInputs();
381          for (size_t i = 0; i < inputs.size(); ++i) {
382            if (i == input_index) {
383              continue;
384            }
385            Location location = inputs[i]->GetLiveInterval()->GetLocationAt(
386                user->GetBlock()->GetPredecessors()[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
417int LiveInterval::FindHintAtDefinition() const {
418  if (defined_by_->IsPhi()) {
419    // Try to use the same register as one of the inputs.
420    const ArenaVector<HBasicBlock*>& predecessors = defined_by_->GetBlock()->GetPredecessors();
421    HInputsRef inputs = defined_by_->GetInputs();
422    for (size_t i = 0; i < inputs.size(); ++i) {
423      size_t end = predecessors[i]->GetLifetimeEnd();
424      LiveInterval* input_interval = inputs[i]->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
456bool 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
472size_t LiveInterval::NumberOfSpillSlotsNeeded() const {
473  // For a SIMD operation, compute the number of needed spill slots.
474  // TODO: do through vector type?
475  HInstruction* definition = GetParent()->GetDefinedBy();
476  if (definition != nullptr && definition->IsVecOperation()) {
477    return definition->AsVecOperation()->GetVectorNumberOfBytes() / kVRegSize;
478  }
479  // Return number of needed spill slots based on type.
480  return (type_ == Primitive::kPrimLong || type_ == Primitive::kPrimDouble) ? 2 : 1;
481}
482
483Location LiveInterval::ToLocation() const {
484  DCHECK(!IsHighInterval());
485  if (HasRegister()) {
486    if (IsFloatingPoint()) {
487      if (HasHighInterval()) {
488        return Location::FpuRegisterPairLocation(GetRegister(), GetHighInterval()->GetRegister());
489      } else {
490        return Location::FpuRegisterLocation(GetRegister());
491      }
492    } else {
493      if (HasHighInterval()) {
494        return Location::RegisterPairLocation(GetRegister(), GetHighInterval()->GetRegister());
495      } else {
496        return Location::RegisterLocation(GetRegister());
497      }
498    }
499  } else {
500    HInstruction* defined_by = GetParent()->GetDefinedBy();
501    if (defined_by->IsConstant()) {
502      return defined_by->GetLocations()->Out();
503    } else if (GetParent()->HasSpillSlot()) {
504      switch (NumberOfSpillSlotsNeeded()) {
505        case 1: return Location::StackSlot(GetParent()->GetSpillSlot());
506        case 2: return Location::DoubleStackSlot(GetParent()->GetSpillSlot());
507        case 4: return Location::SIMDStackSlot(GetParent()->GetSpillSlot());
508        default: LOG(FATAL) << "Unexpected number of spill slots"; UNREACHABLE();
509      }
510    } else {
511      return Location();
512    }
513  }
514}
515
516Location LiveInterval::GetLocationAt(size_t position) {
517  LiveInterval* sibling = GetSiblingAt(position);
518  DCHECK(sibling != nullptr);
519  return sibling->ToLocation();
520}
521
522LiveInterval* LiveInterval::GetSiblingAt(size_t position) {
523  LiveInterval* current = this;
524  while (current != nullptr && !current->IsDefinedAt(position)) {
525    current = current->GetNextSibling();
526  }
527  return current;
528}
529
530}  // namespace art
531