/*
 * Copyright (C) 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
#define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_

#include <iostream>

#include "nodes.h"

namespace art {

class CodeGenerator;
class SsaLivenessAnalysis;

static constexpr int kNoRegister = -1;

class BlockInfo : public ArenaObject<kArenaAllocSsaLiveness> {
 public:
  BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
      : block_(block),
        live_in_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness),
        live_out_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness),
        kill_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness) {
    UNUSED(block_);
    live_in_.ClearAllBits();
    live_out_.ClearAllBits();
    kill_.ClearAllBits();
  }

 private:
  const HBasicBlock& block_;
  ArenaBitVector live_in_;
  ArenaBitVector live_out_;
  ArenaBitVector kill_;

  friend class SsaLivenessAnalysis;

  DISALLOW_COPY_AND_ASSIGN(BlockInfo);
};

/**
 * A live range contains the start and end of a range where an instruction or a temporary
 * is live.
 */
class LiveRange FINAL : public ArenaObject<kArenaAllocSsaLiveness> {
 public:
  LiveRange(size_t start, size_t end, LiveRange* next) : start_(start), end_(end), next_(next) {
    DCHECK_LT(start, end);
    DCHECK(next_ == nullptr || next_->GetStart() > GetEnd());
  }

  size_t GetStart() const { return start_; }
  size_t GetEnd() const { return end_; }
  LiveRange* GetNext() const { return next_; }

  bool IntersectsWith(const LiveRange& other) const {
    return (start_ >= other.start_ && start_ < other.end_)
        || (other.start_ >= start_ && other.start_ < end_);
  }

  bool IsBefore(const LiveRange& other) const {
    return end_ <= other.start_;
  }

  void Dump(std::ostream& stream) const {
    stream << "[" << start_ << "," << end_ << ")";
  }

  LiveRange* Dup(ArenaAllocator* allocator) const {
    return new (allocator) LiveRange(
        start_, end_, next_ == nullptr ? nullptr : next_->Dup(allocator));
  }

  LiveRange* GetLastRange() {
    return next_ == nullptr ? this : next_->GetLastRange();
  }

 private:
  size_t start_;
  size_t end_;
  LiveRange* next_;

  friend class LiveInterval;

  DISALLOW_COPY_AND_ASSIGN(LiveRange);
};

/**
 * A use position represents a live interval use at a given position.
 */
class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
 public:
  UsePosition(HInstruction* user, size_t input_index, size_t position, UsePosition* next)
      : user_(user),
        input_index_(input_index),
        position_(position),
        next_(next) {
    DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
  }

  explicit UsePosition(size_t position)
      : user_(nullptr),
        input_index_(kNoInput),
        position_(dchecked_integral_cast<uint32_t>(position)),
        next_(nullptr) {
  }

  size_t GetPosition() const { return position_; }

  UsePosition* GetNext() const { return next_; }
  void SetNext(UsePosition* next) { next_ = next; }

  HInstruction* GetUser() const { return user_; }

  bool IsSynthesized() const { return user_ == nullptr; }

  size_t GetInputIndex() const { return input_index_; }

  void Dump(std::ostream& stream) const {
    stream << position_;
  }

  HLoopInformation* GetLoopInformation() const {
    return user_->GetBlock()->GetLoopInformation();
  }

  UsePosition* Dup(ArenaAllocator* allocator) const {
    return new (allocator) UsePosition(
        user_, input_index_, position_,
        next_ == nullptr ? nullptr : next_->Dup(allocator));
  }

  bool RequiresRegister() const {
    if (IsSynthesized()) return false;
    Location location = GetUser()->GetLocations()->InAt(GetInputIndex());
    return location.IsUnallocated() && location.RequiresRegisterKind();
  }

 private:
  static constexpr uint32_t kNoInput = static_cast<uint32_t>(-1);

  HInstruction* const user_;
  const size_t input_index_;
  const size_t position_;
  UsePosition* next_;

  DISALLOW_COPY_AND_ASSIGN(UsePosition);
};

/**
 * An environment use position represents a live interval for environment use at a given position.
 */
class EnvUsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
 public:
  EnvUsePosition(HEnvironment* environment,
                 size_t input_index,
                 size_t position,
                 EnvUsePosition* next)
      : environment_(environment),
        input_index_(input_index),
        position_(position),
        next_(next) {
    DCHECK(environment != nullptr);
    DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
  }

  size_t GetPosition() const { return position_; }

  EnvUsePosition* GetNext() const { return next_; }
  void SetNext(EnvUsePosition* next) { next_ = next; }

  HEnvironment* GetEnvironment() const { return environment_; }
  size_t GetInputIndex() const { return input_index_; }

  void Dump(std::ostream& stream) const {
    stream << position_;
  }

  EnvUsePosition* Dup(ArenaAllocator* allocator) const {
    return new (allocator) EnvUsePosition(
        environment_, input_index_, position_,
        next_ == nullptr ? nullptr : next_->Dup(allocator));
  }

 private:
  HEnvironment* const environment_;
  const size_t input_index_;
  const size_t position_;
  EnvUsePosition* next_;

  DISALLOW_COPY_AND_ASSIGN(EnvUsePosition);
};

class SafepointPosition : public ArenaObject<kArenaAllocSsaLiveness> {
 public:
  explicit SafepointPosition(HInstruction* instruction)
      : instruction_(instruction),
        next_(nullptr) {}

  void SetNext(SafepointPosition* next) {
    next_ = next;
  }

  size_t GetPosition() const {
    return instruction_->GetLifetimePosition();
  }

  SafepointPosition* GetNext() const {
    return next_;
  }

  LocationSummary* GetLocations() const {
    return instruction_->GetLocations();
  }

  HInstruction* GetInstruction() const {
    return instruction_;
  }

 private:
  HInstruction* const instruction_;
  SafepointPosition* next_;

  DISALLOW_COPY_AND_ASSIGN(SafepointPosition);
};

/**
 * An interval is a list of disjoint live ranges where an instruction is live.
 * Each instruction that has uses gets an interval.
 */
class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
 public:
  static LiveInterval* MakeInterval(ArenaAllocator* allocator,
                                    Primitive::Type type,
                                    HInstruction* instruction = nullptr) {
    return new (allocator) LiveInterval(allocator, type, instruction);
  }

  static LiveInterval* MakeFixedInterval(ArenaAllocator* allocator, int reg, Primitive::Type type) {
    return new (allocator) LiveInterval(allocator, type, nullptr, true, reg, false);
  }

  static LiveInterval* MakeTempInterval(ArenaAllocator* allocator, Primitive::Type type) {
    return new (allocator) LiveInterval(allocator, type, nullptr, false, kNoRegister, true);
  }

  bool IsFixed() const { return is_fixed_; }
  bool IsTemp() const { return is_temp_; }
  // This interval is the result of a split.
  bool IsSplit() const { return parent_ != this; }

  void AddTempUse(HInstruction* instruction, size_t temp_index) {
    DCHECK(IsTemp());
    DCHECK(first_use_ == nullptr) << "A temporary can only have one user";
    DCHECK(first_env_use_ == nullptr) << "A temporary cannot have environment user";
    size_t position = instruction->GetLifetimePosition();
    first_use_ = new (allocator_) UsePosition(
        instruction, temp_index, position, first_use_);
    AddRange(position, position + 1);
  }

  // Record use of an input. The use will be recorded as an environment use if
  // `environment` is not null and as register use otherwise. If `actual_user`
  // is specified, the use will be recorded at `actual_user`'s lifetime position.
  void AddUse(HInstruction* instruction,
              HEnvironment* environment,
              size_t input_index,
              HInstruction* actual_user = nullptr,
              bool keep_alive = false) {
    bool is_environment = (environment != nullptr);
    LocationSummary* locations = instruction->GetLocations();
    if (actual_user == nullptr) {
      actual_user = instruction;
    }

    // Set the use within the instruction.
    size_t position = actual_user->GetLifetimePosition() + 1;
    if (!is_environment) {
      if (locations->IsFixedInput(input_index) || locations->OutputUsesSameAs(input_index)) {
        // For fixed inputs and output same as input, the register allocator
        // requires to have inputs die at the instruction, so that input moves use the
        // location of the input just before that instruction (and not potential moves due
        // to splitting).
        DCHECK_EQ(instruction, actual_user);
        position = actual_user->GetLifetimePosition();
      } else if (!locations->InAt(input_index).IsValid()) {
        return;
      }
    }

    if (!is_environment && instruction->IsInLoop()) {
      AddBackEdgeUses(*instruction->GetBlock());
    }

    if ((first_use_ != nullptr)
        && (first_use_->GetUser() == actual_user)
        && (first_use_->GetPosition() < position)) {
      // The user uses the instruction multiple times, and one use dies before the other.
      // We update the use list so that the latter is first.
      DCHECK(!is_environment);
      UsePosition* cursor = first_use_;
      while ((cursor->GetNext() != nullptr) && (cursor->GetNext()->GetPosition() < position)) {
        cursor = cursor->GetNext();
      }
      DCHECK(first_use_->GetPosition() + 1 == position);
      UsePosition* new_use = new (allocator_) UsePosition(
          instruction, input_index, position, cursor->GetNext());
      cursor->SetNext(new_use);
      if (first_range_->GetEnd() == first_use_->GetPosition()) {
        first_range_->end_ = position;
      }
      return;
    }

    if (is_environment) {
      first_env_use_ = new (allocator_) EnvUsePosition(
          environment, input_index, position, first_env_use_);
    } else {
      first_use_ = new (allocator_) UsePosition(
          instruction, input_index, position, first_use_);
    }

    if (is_environment && !keep_alive) {
      // If this environment use does not keep the instruction live, it does not
      // affect the live range of that instruction.
      return;
    }

    size_t start_block_position = instruction->GetBlock()->GetLifetimeStart();
    if (first_range_ == nullptr) {
      // First time we see a use of that interval.
      first_range_ = last_range_ = range_search_start_ =
          new (allocator_) LiveRange(start_block_position, position, nullptr);
    } else if (first_range_->GetStart() == start_block_position) {
      // There is a use later in the same block or in a following block.
      // Note that in such a case, `AddRange` for the whole blocks has been called
      // before arriving in this method, and this is the reason the start of
      // `first_range_` is before the given `position`.
      DCHECK_LE(position, first_range_->GetEnd());
    } else {
      DCHECK(first_range_->GetStart() > position);
      // There is a hole in the interval. Create a new range.
      // Note that the start of `first_range_` can be equal to `end`: two blocks
      // having adjacent lifetime positions are not necessarily
      // predecessor/successor. When two blocks are predecessor/successor, the
      // liveness algorithm has called `AddRange` before arriving in this method,
      // and the check line 205 would succeed.
      first_range_ = range_search_start_ =
          new (allocator_) LiveRange(start_block_position, position, first_range_);
    }
  }

  void AddPhiUse(HInstruction* instruction, size_t input_index, HBasicBlock* block) {
    DCHECK(instruction->IsPhi());
    if (block->IsInLoop()) {
      AddBackEdgeUses(*block);
    }
    first_use_ = new (allocator_) UsePosition(
        instruction, input_index, block->GetLifetimeEnd(), first_use_);
  }

  ALWAYS_INLINE void AddRange(size_t start, size_t end) {
    if (first_range_ == nullptr) {
      first_range_ = last_range_ = range_search_start_ =
          new (allocator_) LiveRange(start, end, first_range_);
    } else if (first_range_->GetStart() == end) {
      // There is a use in the following block.
      first_range_->start_ = start;
    } else if (first_range_->GetStart() == start && first_range_->GetEnd() == end) {
      DCHECK(is_fixed_);
    } else {
      DCHECK_GT(first_range_->GetStart(), end);
      // There is a hole in the interval. Create a new range.
      first_range_ = range_search_start_ = new (allocator_) LiveRange(start, end, first_range_);
    }
  }

  void AddLoopRange(size_t start, size_t end) {
    DCHECK(first_range_ != nullptr);
    DCHECK_LE(start, first_range_->GetStart());
    // Find the range that covers the positions after the loop.
    LiveRange* after_loop = first_range_;
    LiveRange* last_in_loop = nullptr;
    while (after_loop != nullptr && after_loop->GetEnd() < end) {
      DCHECK_LE(start, after_loop->GetStart());
      last_in_loop = after_loop;
      after_loop = after_loop->GetNext();
    }
    if (after_loop == nullptr) {
      // Uses are only in the loop.
      first_range_ = last_range_ = range_search_start_ =
          new (allocator_) LiveRange(start, end, nullptr);
    } else if (after_loop->GetStart() <= end) {
      first_range_ = range_search_start_ = after_loop;
      // There are uses after the loop.
      first_range_->start_ = start;
    } else {
      // The use after the loop is after a lifetime hole.
      DCHECK(last_in_loop != nullptr);
      first_range_ = range_search_start_ = last_in_loop;
      first_range_->start_ = start;
      first_range_->end_ = end;
    }
  }

  bool HasSpillSlot() const { return spill_slot_ != kNoSpillSlot; }
  void SetSpillSlot(int slot) {
    DCHECK(!is_fixed_);
    DCHECK(!is_temp_);
    spill_slot_ = slot;
  }
  int GetSpillSlot() const { return spill_slot_; }

  void SetFrom(size_t from) {
    if (first_range_ != nullptr) {
      first_range_->start_ = from;
    } else {
      // Instruction without uses.
      DCHECK(first_use_ == nullptr);
      DCHECK(from == defined_by_->GetLifetimePosition());
      first_range_ = last_range_ = range_search_start_ =
          new (allocator_) LiveRange(from, from + 2, nullptr);
    }
  }

  LiveInterval* GetParent() const { return parent_; }

  // Returns whether this interval is the parent interval, that is, the interval
  // that starts where the HInstruction is defined.
  bool IsParent() const { return parent_ == this; }

  LiveRange* GetFirstRange() const { return first_range_; }
  LiveRange* GetLastRange() const { return last_range_; }

  int GetRegister() const { return register_; }
  void SetRegister(int reg) { register_ = reg; }
  void ClearRegister() { register_ = kNoRegister; }
  bool HasRegister() const { return register_ != kNoRegister; }

  bool IsDeadAt(size_t position) const {
    return GetEnd() <= position;
  }

  bool IsDefinedAt(size_t position) const {
    return GetStart() <= position && !IsDeadAt(position);
  }

  // Returns true if the interval contains a LiveRange covering `position`.
  // The range at or immediately after the current position of linear scan
  // is cached for better performance. If `position` can be smaller than
  // that, CoversSlow should be used instead.
  bool Covers(size_t position) {
    LiveRange* candidate = FindRangeAtOrAfter(position, range_search_start_);
    range_search_start_ = candidate;
    return (candidate != nullptr && candidate->GetStart() <= position);
  }

  // Same as Covers but always tests all ranges.
  bool CoversSlow(size_t position) const {
    LiveRange* candidate = FindRangeAtOrAfter(position, first_range_);
    return candidate != nullptr && candidate->GetStart() <= position;
  }

  // Returns the first intersection of this interval with `current`, which
  // must be the interval currently being allocated by linear scan.
  size_t FirstIntersectionWith(LiveInterval* current) const {
    // Find the first range after the start of `current`. We use the search
    // cache to improve performance.
    DCHECK(GetStart() <= current->GetStart() || IsFixed());
    LiveRange* other_range = current->first_range_;
    LiveRange* my_range = FindRangeAtOrAfter(other_range->GetStart(), range_search_start_);
    if (my_range == nullptr) {
      return kNoLifetime;
    }

    // Advance both intervals and find the first matching range start in
    // this interval.
    do {
      if (my_range->IsBefore(*other_range)) {
        my_range = my_range->GetNext();
        if (my_range == nullptr) {
          return kNoLifetime;
        }
      } else if (other_range->IsBefore(*my_range)) {
        other_range = other_range->GetNext();
        if (other_range == nullptr) {
          return kNoLifetime;
        }
      } else {
        DCHECK(my_range->IntersectsWith(*other_range));
        return std::max(my_range->GetStart(), other_range->GetStart());
      }
    } while (true);
  }

  size_t GetStart() const {
    return first_range_->GetStart();
  }

  size_t GetEnd() const {
    return last_range_->GetEnd();
  }

  size_t GetLength() const {
    return GetEnd() - GetStart();
  }

  size_t FirstRegisterUseAfter(size_t position) const {
    if (is_temp_) {
      return position == GetStart() ? position : kNoLifetime;
    }

    if (IsDefiningPosition(position) && DefinitionRequiresRegister()) {
      return position;
    }

    UsePosition* use = first_use_;
    size_t end = GetEnd();
    while (use != nullptr && use->GetPosition() <= end) {
      size_t use_position = use->GetPosition();
      if (use_position > position) {
        if (use->RequiresRegister()) {
          return use_position;
        }
      }
      use = use->GetNext();
    }
    return kNoLifetime;
  }

  // Returns the location of the first register use for this live interval,
  // including a register definition if applicable.
  size_t FirstRegisterUse() const {
    return FirstRegisterUseAfter(GetStart());
  }

  // Whether the interval requires a register rather than a stack location.
  // If needed for performance, this could be cached.
  bool RequiresRegister() const {
    return !HasRegister() && FirstRegisterUse() != kNoLifetime;
  }

  size_t FirstUseAfter(size_t position) const {
    if (is_temp_) {
      return position == GetStart() ? position : kNoLifetime;
    }

    if (IsDefiningPosition(position)) {
      DCHECK(defined_by_->GetLocations()->Out().IsValid());
      return position;
    }

    UsePosition* use = first_use_;
    size_t end = GetEnd();
    while (use != nullptr && use->GetPosition() <= end) {
      size_t use_position = use->GetPosition();
      if (use_position > position) {
        return use_position;
      }
      use = use->GetNext();
    }
    return kNoLifetime;
  }

  UsePosition* GetFirstUse() const {
    return first_use_;
  }

  EnvUsePosition* GetFirstEnvironmentUse() const {
    return first_env_use_;
  }

  Primitive::Type GetType() const {
    return type_;
  }

  HInstruction* GetDefinedBy() const {
    return defined_by_;
  }

  bool HasWillCallSafepoint() const {
    for (SafepointPosition* safepoint = first_safepoint_;
         safepoint != nullptr;
         safepoint = safepoint->GetNext()) {
      if (safepoint->GetLocations()->WillCall()) return true;
    }
    return false;
  }

  SafepointPosition* FindSafepointJustBefore(size_t position) const {
    for (SafepointPosition* safepoint = first_safepoint_, *previous = nullptr;
         safepoint != nullptr;
         previous = safepoint, safepoint = safepoint->GetNext()) {
      if (safepoint->GetPosition() >= position) return previous;
    }
    return last_safepoint_;
  }

  /**
   * Split this interval at `position`. This interval is changed to:
   * [start ... position).
   *
   * The new interval covers:
   * [position ... end)
   */
  LiveInterval* SplitAt(size_t position) {
    DCHECK(!is_temp_);
    DCHECK(!is_fixed_);
    DCHECK_GT(position, GetStart());

    if (GetEnd() <= position) {
      // This range dies before `position`, no need to split.
      return nullptr;
    }

    LiveInterval* new_interval = new (allocator_) LiveInterval(allocator_, type_);
    SafepointPosition* new_last_safepoint = FindSafepointJustBefore(position);
    if (new_last_safepoint == nullptr) {
      new_interval->first_safepoint_ = first_safepoint_;
      new_interval->last_safepoint_ = last_safepoint_;
      first_safepoint_ = last_safepoint_ = nullptr;
    } else if (last_safepoint_ != new_last_safepoint) {
      new_interval->last_safepoint_ = last_safepoint_;
      new_interval->first_safepoint_ = new_last_safepoint->GetNext();
      DCHECK(new_interval->first_safepoint_ != nullptr);
      last_safepoint_ = new_last_safepoint;
      last_safepoint_->SetNext(nullptr);
    }

    new_interval->next_sibling_ = next_sibling_;
    next_sibling_ = new_interval;
    new_interval->parent_ = parent_;

    new_interval->first_use_ = first_use_;
    new_interval->first_env_use_ = first_env_use_;
    LiveRange* current = first_range_;
    LiveRange* previous = nullptr;
    // Iterate over the ranges, and either find a range that covers this position, or
    // two ranges in between this position (that is, the position is in a lifetime hole).
    do {
      if (position >= current->GetEnd()) {
        // Move to next range.
        previous = current;
        current = current->next_;
      } else if (position <= current->GetStart()) {
        // If the previous range did not cover this position, we know position is in
        // a lifetime hole. We can just break the first_range_ and last_range_ links
        // and return the new interval.
        DCHECK(previous != nullptr);
        DCHECK(current != first_range_);
        new_interval->last_range_ = last_range_;
        last_range_ = previous;
        previous->next_ = nullptr;
        new_interval->first_range_ = current;
        if (range_search_start_ != nullptr && range_search_start_->GetEnd() >= current->GetEnd()) {
          // Search start point is inside `new_interval`. Change it to null
          // (i.e. the end of the interval) in the original interval.
          range_search_start_ = nullptr;
        }
        new_interval->range_search_start_ = new_interval->first_range_;
        return new_interval;
      } else {
        // This range covers position. We create a new last_range_ for this interval
        // that covers last_range_->Start() and position. We also shorten the current
        // range and make it the first range of the new interval.
        DCHECK(position < current->GetEnd() && position > current->GetStart());
        new_interval->last_range_ = last_range_;
        last_range_ = new (allocator_) LiveRange(current->start_, position, nullptr);
        if (previous != nullptr) {
          previous->next_ = last_range_;
        } else {
          first_range_ = last_range_;
        }
        new_interval->first_range_ = current;
        current->start_ = position;
        if (range_search_start_ != nullptr && range_search_start_->GetEnd() >= current->GetEnd()) {
          // Search start point is inside `new_interval`. Change it to `last_range`
          // in the original interval. This is conservative but always correct.
          range_search_start_ = last_range_;
        }
        new_interval->range_search_start_ = new_interval->first_range_;
        return new_interval;
      }
    } while (current != nullptr);

    LOG(FATAL) << "Unreachable";
    return nullptr;
  }

  bool StartsBeforeOrAt(LiveInterval* other) const {
    return GetStart() <= other->GetStart();
  }

  bool StartsAfter(LiveInterval* other) const {
    return GetStart() > other->GetStart();
  }

  void Dump(std::ostream& stream) const {
    stream << "ranges: { ";
    LiveRange* current = first_range_;
    while (current != nullptr) {
      current->Dump(stream);
      stream << " ";
      current = current->GetNext();
    }
    stream << "}, uses: { ";
    const UsePosition* use = first_use_;
    if (use != nullptr) {
      do {
        use->Dump(stream);
        stream << " ";
      } while ((use = use->GetNext()) != nullptr);
    }
    stream << "}, { ";
    const EnvUsePosition* env_use = first_env_use_;
    if (env_use != nullptr) {
      do {
        env_use->Dump(stream);
        stream << " ";
      } while ((env_use = env_use->GetNext()) != nullptr);
    }
    stream << "}";
    stream << " is_fixed: " << is_fixed_ << ", is_split: " << IsSplit();
    stream << " is_low: " << IsLowInterval();
    stream << " is_high: " << IsHighInterval();
  }

  // Same as Dump, but adds context such as the instruction defining this interval, and
  // the register currently assigned to this interval.
  void DumpWithContext(std::ostream& stream, const CodeGenerator& codegen) const;

  LiveInterval* GetNextSibling() const { return next_sibling_; }
  LiveInterval* GetLastSibling() {
    LiveInterval* result = this;
    while (result->next_sibling_ != nullptr) {
      result = result->next_sibling_;
    }
    return result;
  }

  // Returns the first register hint that is at least free before
  // the value contained in `free_until`. If none is found, returns
  // `kNoRegister`.
  int FindFirstRegisterHint(size_t* free_until, const SsaLivenessAnalysis& liveness) const;

  // If there is enough at the definition site to find a register (for example
  // it uses the same input as the first input), returns the register as a hint.
  // Returns kNoRegister otherwise.
  int FindHintAtDefinition() const;

  // Returns whether the interval needs two (Dex virtual register size `kVRegSize`)
  // slots for spilling.
  bool NeedsTwoSpillSlots() const;

  bool IsFloatingPoint() const {
    return type_ == Primitive::kPrimFloat || type_ == Primitive::kPrimDouble;
  }

  // Converts the location of the interval to a `Location` object.
  Location ToLocation() const;

  // Returns the location of the interval following its siblings at `position`.
  Location GetLocationAt(size_t position);

  // Finds the sibling that is defined at `position`.
  LiveInterval* GetSiblingAt(size_t position);

  // Returns whether `other` and `this` share the same kind of register.
  bool SameRegisterKind(Location other) const;
  bool SameRegisterKind(const LiveInterval& other) const {
    return IsFloatingPoint() == other.IsFloatingPoint();
  }

  bool HasHighInterval() const {
    return IsLowInterval();
  }

  bool HasLowInterval() const {
    return IsHighInterval();
  }

  LiveInterval* GetLowInterval() const {
    DCHECK(HasLowInterval());
    return high_or_low_interval_;
  }

  LiveInterval* GetHighInterval() const {
    DCHECK(HasHighInterval());
    return high_or_low_interval_;
  }

  bool IsHighInterval() const {
    return GetParent()->is_high_interval_;
  }

  bool IsLowInterval() const {
    return !IsHighInterval() && (GetParent()->high_or_low_interval_ != nullptr);
  }

  void SetLowInterval(LiveInterval* low) {
    DCHECK(IsHighInterval());
    high_or_low_interval_ = low;
  }

  void SetHighInterval(LiveInterval* high) {
    DCHECK(IsLowInterval());
    high_or_low_interval_ = high;
  }

  void AddHighInterval(bool is_temp = false) {
    DCHECK(IsParent());
    DCHECK(!HasHighInterval());
    DCHECK(!HasLowInterval());
    high_or_low_interval_ = new (allocator_) LiveInterval(
        allocator_, type_, defined_by_, false, kNoRegister, is_temp, true);
    high_or_low_interval_->high_or_low_interval_ = this;
    if (first_range_ != nullptr) {
      high_or_low_interval_->first_range_ = first_range_->Dup(allocator_);
      high_or_low_interval_->last_range_ = high_or_low_interval_->first_range_->GetLastRange();
      high_or_low_interval_->range_search_start_ = high_or_low_interval_->first_range_;
    }
    if (first_use_ != nullptr) {
      high_or_low_interval_->first_use_ = first_use_->Dup(allocator_);
    }

    if (first_env_use_ != nullptr) {
      high_or_low_interval_->first_env_use_ = first_env_use_->Dup(allocator_);
    }
  }

  // Returns whether an interval, when it is non-split, is using
  // the same register of one of its input.
  bool IsUsingInputRegister() const {
    CHECK(kIsDebugBuild) << "Function should be used only for DCHECKs";
    if (defined_by_ != nullptr && !IsSplit()) {
      for (const HInstruction* input : defined_by_->GetInputs()) {
        LiveInterval* interval = input->GetLiveInterval();

        // Find the interval that covers `defined_by`_. Calls to this function
        // are made outside the linear scan, hence we need to use CoversSlow.
        while (interval != nullptr && !interval->CoversSlow(defined_by_->GetLifetimePosition())) {
          interval = interval->GetNextSibling();
        }

        // Check if both intervals have the same register of the same kind.
        if (interval != nullptr
            && interval->SameRegisterKind(*this)
            && interval->GetRegister() == GetRegister()) {
          return true;
        }
      }
    }
    return false;
  }

  // Returns whether an interval, when it is non-split, can safely use
  // the same register of one of its input. Note that this method requires
  // IsUsingInputRegister() to be true.
  bool CanUseInputRegister() const {
    CHECK(kIsDebugBuild) << "Function should be used only for DCHECKs";
    DCHECK(IsUsingInputRegister());
    if (defined_by_ != nullptr && !IsSplit()) {
      LocationSummary* locations = defined_by_->GetLocations();
      if (locations->OutputCanOverlapWithInputs()) {
        return false;
      }
      for (const HInstruction* input : defined_by_->GetInputs()) {
        LiveInterval* interval = input->GetLiveInterval();

        // Find the interval that covers `defined_by`_. Calls to this function
        // are made outside the linear scan, hence we need to use CoversSlow.
        while (interval != nullptr && !interval->CoversSlow(defined_by_->GetLifetimePosition())) {
          interval = interval->GetNextSibling();
        }

        if (interval != nullptr
            && interval->SameRegisterKind(*this)
            && interval->GetRegister() == GetRegister()) {
          // We found the input that has the same register. Check if it is live after
          // `defined_by`_.
          return !interval->CoversSlow(defined_by_->GetLifetimePosition() + 1);
        }
      }
    }
    LOG(FATAL) << "Unreachable";
    UNREACHABLE();
  }

  void AddSafepoint(HInstruction* instruction) {
    SafepointPosition* safepoint = new (allocator_) SafepointPosition(instruction);
    if (first_safepoint_ == nullptr) {
      first_safepoint_ = last_safepoint_ = safepoint;
    } else {
      DCHECK_LT(last_safepoint_->GetPosition(), safepoint->GetPosition());
      last_safepoint_->SetNext(safepoint);
      last_safepoint_ = safepoint;
    }
  }

  SafepointPosition* GetFirstSafepoint() const {
    return first_safepoint_;
  }

  // Resets the starting point for range-searching queries to the first range.
  // Intervals must be reset prior to starting a new linear scan over them.
  void ResetSearchCache() {
    range_search_start_ = first_range_;
  }

  bool DefinitionRequiresRegister() const {
    DCHECK(IsParent());
    LocationSummary* locations = defined_by_->GetLocations();
    Location location = locations->Out();
    // This interval is the first interval of the instruction. If the output
    // of the instruction requires a register, we return the position of that instruction
    // as the first register use.
    if (location.IsUnallocated()) {
      if ((location.GetPolicy() == Location::kRequiresRegister)
           || (location.GetPolicy() == Location::kSameAsFirstInput
               && (locations->InAt(0).IsRegister()
                   || locations->InAt(0).IsRegisterPair()
                   || locations->InAt(0).GetPolicy() == Location::kRequiresRegister))) {
        return true;
      } else if ((location.GetPolicy() == Location::kRequiresFpuRegister)
                 || (location.GetPolicy() == Location::kSameAsFirstInput
                     && (locations->InAt(0).IsFpuRegister()
                         || locations->InAt(0).IsFpuRegisterPair()
                         || locations->InAt(0).GetPolicy() == Location::kRequiresFpuRegister))) {
        return true;
      }
    } else if (location.IsRegister() || location.IsRegisterPair()) {
      return true;
    }
    return false;
  }

 private:
  LiveInterval(ArenaAllocator* allocator,
               Primitive::Type type,
               HInstruction* defined_by = nullptr,
               bool is_fixed = false,
               int reg = kNoRegister,
               bool is_temp = false,
               bool is_high_interval = false)
      : allocator_(allocator),
        first_range_(nullptr),
        last_range_(nullptr),
        range_search_start_(nullptr),
        first_safepoint_(nullptr),
        last_safepoint_(nullptr),
        first_use_(nullptr),
        first_env_use_(nullptr),
        type_(type),
        next_sibling_(nullptr),
        parent_(this),
        register_(reg),
        spill_slot_(kNoSpillSlot),
        is_fixed_(is_fixed),
        is_temp_(is_temp),
        is_high_interval_(is_high_interval),
        high_or_low_interval_(nullptr),
        defined_by_(defined_by) {}

  // Searches for a LiveRange that either covers the given position or is the
  // first next LiveRange. Returns null if no such LiveRange exists. Ranges
  // known to end before `position` can be skipped with `search_start`.
  LiveRange* FindRangeAtOrAfter(size_t position, LiveRange* search_start) const {
    if (kIsDebugBuild) {
      if (search_start != first_range_) {
        // If we are not searching the entire list of ranges, make sure we do
        // not skip the range we are searching for.
        if (search_start == nullptr) {
          DCHECK(IsDeadAt(position));
        } else if (search_start->GetStart() > position) {
          DCHECK_EQ(search_start, FindRangeAtOrAfter(position, first_range_));
        }
      }
    }

    LiveRange* range;
    for (range = search_start;
         range != nullptr && range->GetEnd() <= position;
         range = range->GetNext()) {
      continue;
    }
    return range;
  }

  bool IsDefiningPosition(size_t position) const {
    return IsParent() && (position == GetStart());
  }

  bool HasSynthesizeUseAt(size_t position) const {
    UsePosition* use = first_use_;
    while (use != nullptr) {
      size_t use_position = use->GetPosition();
      if ((use_position == position) && use->IsSynthesized()) {
        return true;
      }
      if (use_position > position) break;
      use = use->GetNext();
    }
    return false;
  }

  void AddBackEdgeUses(const HBasicBlock& block_at_use) {
    DCHECK(block_at_use.IsInLoop());
    if (block_at_use.GetGraph()->HasIrreducibleLoops()) {
      // Linear order may not be well formed when irreducible loops are present,
      // i.e. loop blocks may not be adjacent and a back edge may not be last,
      // which violates assumptions made in this method.
      return;
    }

    // Add synthesized uses at the back edge of loops to help the register allocator.
    // Note that this method is called in decreasing liveness order, to faciliate adding
    // uses at the head of the `first_use_` linked list. Because below
    // we iterate from inner-most to outer-most, which is in increasing liveness order,
    // we need to take extra care of how the `first_use_` linked list is being updated.
    UsePosition* first_in_new_list = nullptr;
    UsePosition* last_in_new_list = nullptr;
    for (HLoopInformationOutwardIterator it(block_at_use);
         !it.Done();
         it.Advance()) {
      HLoopInformation* current = it.Current();
      if (GetDefinedBy()->GetLifetimePosition() >= current->GetHeader()->GetLifetimeStart()) {
        // This interval is defined in the loop. We can stop going outward.
        break;
      }

      // We're only adding a synthesized use at the last back edge. Adding syntehsized uses on
      // all back edges is not necessary: anything used in the loop will have its use at the
      // last back edge. If we want branches in a loop to have better register allocation than
      // another branch, then it is the linear order we should change.
      size_t back_edge_use_position = current->GetLifetimeEnd();
      if ((first_use_ != nullptr) && (first_use_->GetPosition() <= back_edge_use_position)) {
        // There was a use already seen in this loop. Therefore the previous call to `AddUse`
        // already inserted the backedge use. We can stop going outward.
        DCHECK(HasSynthesizeUseAt(back_edge_use_position));
        break;
      }

      DCHECK(last_in_new_list == nullptr ||
             back_edge_use_position > last_in_new_list->GetPosition());

      UsePosition* new_use = new (allocator_) UsePosition(back_edge_use_position);

      if (last_in_new_list != nullptr) {
        // Going outward. The latest created use needs to point to the new use.
        last_in_new_list->SetNext(new_use);
      } else {
        // This is the inner-most loop.
        DCHECK_EQ(current, block_at_use.GetLoopInformation());
        first_in_new_list = new_use;
      }
      last_in_new_list = new_use;
    }
    // Link the newly created linked list with `first_use_`.
    if (last_in_new_list != nullptr) {
      last_in_new_list->SetNext(first_use_);
      first_use_ = first_in_new_list;
    }
  }

  ArenaAllocator* const allocator_;

  // Ranges of this interval. We need a quick access to the last range to test
  // for liveness (see `IsDeadAt`).
  LiveRange* first_range_;
  LiveRange* last_range_;

  // The first range at or after the current position of a linear scan. It is
  // used to optimize range-searching queries.
  LiveRange* range_search_start_;

  // Safepoints where this interval is live.
  SafepointPosition* first_safepoint_;
  SafepointPosition* last_safepoint_;

  // Uses of this interval. Note that this linked list is shared amongst siblings.
  UsePosition* first_use_;
  EnvUsePosition* first_env_use_;

  // The instruction type this interval corresponds to.
  const Primitive::Type type_;

  // Live interval that is the result of a split.
  LiveInterval* next_sibling_;

  // The first interval from which split intervals come from.
  LiveInterval* parent_;

  // The register allocated to this interval.
  int register_;

  // The spill slot allocated to this interval.
  int spill_slot_;

  // Whether the interval is for a fixed register.
  const bool is_fixed_;

  // Whether the interval is for a temporary.
  const bool is_temp_;

  // Whether this interval is a synthesized interval for register pair.
  const bool is_high_interval_;

  // If this interval needs a register pair, the high or low equivalent.
  // `is_high_interval_` tells whether this holds the low or the high.
  LiveInterval* high_or_low_interval_;

  // The instruction represented by this interval.
  HInstruction* const defined_by_;

  static constexpr int kNoRegister = -1;
  static constexpr int kNoSpillSlot = -1;

  ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive);

  DISALLOW_COPY_AND_ASSIGN(LiveInterval);
};

/**
 * Analysis that computes the liveness of instructions:
 *
 * (a) Non-environment uses of an instruction always make
 *     the instruction live.
 * (b) Environment uses of an instruction whose type is
 *     object (that is, non-primitive), make the instruction live.
 *     This is due to having to keep alive objects that have
 *     finalizers deleting native objects.
 * (c) When the graph has the debuggable property, environment uses
 *     of an instruction that has a primitive type make the instruction live.
 *     If the graph does not have the debuggable property, the environment
 *     use has no effect, and may get a 'none' value after register allocation.
 *
 * (b) and (c) are implemented through SsaLivenessAnalysis::ShouldBeLiveForEnvironment.
 */
class SsaLivenessAnalysis : public ValueObject {
 public:
  SsaLivenessAnalysis(HGraph* graph, CodeGenerator* codegen)
      : graph_(graph),
        codegen_(codegen),
        block_infos_(graph->GetBlocks().size(),
                     nullptr,
                     graph->GetArena()->Adapter(kArenaAllocSsaLiveness)),
        instructions_from_ssa_index_(graph->GetArena()->Adapter(kArenaAllocSsaLiveness)),
        instructions_from_lifetime_position_(graph->GetArena()->Adapter(kArenaAllocSsaLiveness)),
        number_of_ssa_values_(0) {
  }

  void Analyze();

  BitVector* GetLiveInSet(const HBasicBlock& block) const {
    return &block_infos_[block.GetBlockId()]->live_in_;
  }

  BitVector* GetLiveOutSet(const HBasicBlock& block) const {
    return &block_infos_[block.GetBlockId()]->live_out_;
  }

  BitVector* GetKillSet(const HBasicBlock& block) const {
    return &block_infos_[block.GetBlockId()]->kill_;
  }

  HInstruction* GetInstructionFromSsaIndex(size_t index) const {
    return instructions_from_ssa_index_[index];
  }

  HInstruction* GetInstructionFromPosition(size_t index) const {
    return instructions_from_lifetime_position_[index];
  }

  HBasicBlock* GetBlockFromPosition(size_t index) const {
    HInstruction* instruction = GetInstructionFromPosition(index);
    if (instruction == nullptr) {
      // If we are at a block boundary, get the block following.
      instruction = GetInstructionFromPosition(index + 1);
    }
    return instruction->GetBlock();
  }

  bool IsAtBlockBoundary(size_t index) const {
    return GetInstructionFromPosition(index) == nullptr;
  }

  HInstruction* GetTempUser(LiveInterval* temp) const {
    // A temporary shares the same lifetime start as the instruction that requires it.
    DCHECK(temp->IsTemp());
    HInstruction* user = GetInstructionFromPosition(temp->GetStart() / 2);
    DCHECK_EQ(user, temp->GetFirstUse()->GetUser());
    return user;
  }

  size_t GetTempIndex(LiveInterval* temp) const {
    // We use the input index to store the index of the temporary in the user's temporary list.
    DCHECK(temp->IsTemp());
    return temp->GetFirstUse()->GetInputIndex();
  }

  size_t GetMaxLifetimePosition() const {
    return instructions_from_lifetime_position_.size() * 2 - 1;
  }

  size_t GetNumberOfSsaValues() const {
    return number_of_ssa_values_;
  }

  static constexpr const char* kLivenessPassName = "liveness";

 private:
  // Give an SSA number to each instruction that defines a value used by another instruction,
  // and setup the lifetime information of each instruction and block.
  void NumberInstructions();

  // Compute live ranges of instructions, as well as live_in, live_out and kill sets.
  void ComputeLiveness();

  // Compute the live ranges of instructions, as well as the initial live_in, live_out and
  // kill sets, that do not take into account backward branches.
  void ComputeLiveRanges();

  // After computing the initial sets, this method does a fixed point
  // calculation over the live_in and live_out set to take into account
  // backwards branches.
  void ComputeLiveInAndLiveOutSets();

  // Update the live_in set of the block and returns whether it has changed.
  bool UpdateLiveIn(const HBasicBlock& block);

  // Update the live_out set of the block and returns whether it has changed.
  bool UpdateLiveOut(const HBasicBlock& block);

  // Returns whether `instruction` in an HEnvironment held by `env_holder`
  // should be kept live by the HEnvironment.
  static bool ShouldBeLiveForEnvironment(HInstruction* env_holder, HInstruction* instruction) {
    if (instruction == nullptr) return false;
    // A value that's not live in compiled code may still be needed in interpreter,
    // due to code motion, etc.
    if (env_holder->IsDeoptimize()) return true;
    // A value live at a throwing instruction in a try block may be copied by
    // the exception handler to its location at the top of the catch block.
    if (env_holder->CanThrowIntoCatchBlock()) return true;
    if (instruction->GetBlock()->GetGraph()->IsDebuggable()) return true;
    return instruction->GetType() == Primitive::kPrimNot;
  }

  void CheckNoLiveInIrreducibleLoop(const HBasicBlock& block) const {
    if (!block.IsLoopHeader() || !block.GetLoopInformation()->IsIrreducible()) {
      return;
    }
    BitVector* live_in = GetLiveInSet(block);
    // To satisfy our liveness algorithm, we need to ensure loop headers of
    // irreducible loops do not have any live-in instructions, except constants
    // and the current method, which can be trivially re-materialized.
    for (uint32_t idx : live_in->Indexes()) {
      HInstruction* instruction = GetInstructionFromSsaIndex(idx);
      DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
      DCHECK(!instruction->IsParameterValue());
      DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
          << instruction->DebugName();
    }
  }

  HGraph* const graph_;
  CodeGenerator* const codegen_;
  ArenaVector<BlockInfo*> block_infos_;

  // Temporary array used when computing live_in, live_out, and kill sets.
  ArenaVector<HInstruction*> instructions_from_ssa_index_;

  // Temporary array used when inserting moves in the graph.
  ArenaVector<HInstruction*> instructions_from_lifetime_position_;
  size_t number_of_ssa_values_;

  ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive);
  ART_FRIEND_TEST(RegisterAllocatorTest, FreeUntil);

  DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
};

}  // namespace art

#endif  // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_