runtime/vm/compiler/backend/loops.cc

// Copyright (c) 2018, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#include "vm/compiler/backend/loops.h"

#include "vm/bit_vector.h"
#include "vm/compiler/backend/il.h"

namespace dart {

// Private class to perform induction variable analysis on a single loop
// or a full loop hierarchy. The analysis implementation is based on the
// paper by M. Gerlek et al. "Beyond Induction Variables: Detecting and
// Classifying Sequences Using a Demand-Driven SSA Form" (ACM Transactions
// on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995).
//
// The algorithm discovers and classifies definitions within loops that
// behave like induction variables, and attaches an InductionVar record
// to it (this mapping is stored in the loop data structure). The algorithm
// first finds strongly connected components in the flow graph and classifies
// each component as an induction when possible. Due to the descendant-first
// nature, classification happens "on-demand" (e.g. basic induction is
// classified before derived induction).
class InductionVarAnalysis : public ValueObject {
 public:
  // Constructor to set up analysis phase.
  explicit InductionVarAnalysis(const GrowableArray<BlockEntryInstr*>& preorder)
      : preorder_(preorder),
        stack_(),
        scc_(),
        cycle_(),
        map_(),
        current_index_(0),
        zone_(Thread::Current()->zone()) {}

  // Detects induction variables on the full loop hierarchy.
  void VisitHierarchy(LoopInfo* loop);

  // Detects induction variables on a single loop.
  void VisitLoop(LoopInfo* loop);

 private:
  // An information node needed during SCC traversal that can
  // reside in a map without any explicit memory allocation.
  struct SCCInfo {
    SCCInfo() : depth(-1), done(false) {}
    explicit SCCInfo(intptr_t d) : depth(d), done(false) {}
    intptr_t depth;
    bool done;
    bool operator!=(const SCCInfo& other) const {
      return depth != other.depth || done != other.done;
    }
    bool operator==(const SCCInfo& other) const {
      return depth == other.depth && done == other.done;
    }
  };
  typedef RawPointerKeyValueTrait<Definition, SCCInfo> VisitKV;

  // Traversal methods.
  bool Visit(LoopInfo* loop, Definition* def);
  intptr_t VisitDescendant(LoopInfo* loop, Definition* def);
  void Classify(LoopInfo* loop, Definition* def);
  void ClassifySCC(LoopInfo* loop);
  void ClassifyControl(LoopInfo* loop);

  // Transfer methods. Compute how induction of the operands, if any,
  // transfers over the operation performed by the given definition.
  InductionVar* TransferPhi(LoopInfo* loop, Definition* def, intptr_t idx = -1);
  InductionVar* TransferDef(LoopInfo* loop, Definition* def);
  InductionVar* TransferBinary(LoopInfo* loop, Definition* def);
  InductionVar* TransferUnary(LoopInfo* loop, Definition* def);

  // Solver methods. Compute how temporary meaning given to the
  // definitions in a cycle transfer over the operation performed
  // by the given definition.
  InductionVar* SolvePhi(LoopInfo* loop, Definition* def, intptr_t idx = -1);
  InductionVar* SolveConstraint(LoopInfo* loop,
                                Definition* def,
                                InductionVar* init);
  InductionVar* SolveBinary(LoopInfo* loop,
                            Definition* def,
                            InductionVar* init);
  InductionVar* SolveUnary(LoopInfo* loop, Definition* def, InductionVar* init);

  // Lookup.
  InductionVar* Lookup(LoopInfo* loop, Definition* def);
  InductionVar* LookupCycle(Definition* def);

  // Arithmetic.
  InductionVar* Add(InductionVar* x, InductionVar* y);
  InductionVar* Sub(InductionVar* x, InductionVar* y);
  InductionVar* Mul(InductionVar* x, InductionVar* y);

  // Bookkeeping data (released when analysis goes out of scope).
  const GrowableArray<BlockEntryInstr*>& preorder_;
  GrowableArray<Definition*> stack_;
  GrowableArray<Definition*> scc_;
  GrowableArray<BranchInstr*> branches_;
  DirectChainedHashMap<LoopInfo::InductionKV> cycle_;
  DirectChainedHashMap<VisitKV> map_;
  intptr_t current_index_;
  Zone* zone_;

  DISALLOW_COPY_AND_ASSIGN(InductionVarAnalysis);
};

// Helper method that finds phi-index of the initial value
// that comes from a block outside the loop. Note that the
// algorithm still works if there are several of these.
static intptr_t InitIndex(LoopInfo* loop) {
  BlockEntryInstr* header = loop->header();
  for (intptr_t i = 0; i < header->PredecessorCount(); ++i) {
    if (!loop->Contains(header->PredecessorAt(i))) {  // pick first
      return i;
    }
  }
  UNREACHABLE();
  return -1;
}

// Helper method that determines if a definition is a constant.
static bool IsConstant(Definition* def, int64_t* val) {
  if (def->IsConstant()) {
    const Object& value = def->AsConstant()->value();
    if (value.IsInteger()) {
      *val = Integer::Cast(value).Value();  // smi and mint
      return true;
    }
  }
  return false;
}

// Helper method to determine if a non-strict (inclusive) bound on
// a unit stride linear induction can be made strict (exclusive)
// without arithmetic wrap-around complications.
static bool CanBeMadeExclusive(LoopInfo* loop,
                               InductionVar* x,
                               Instruction* branch,
                               bool is_lower) {
  InductionVar* min = nullptr;
  InductionVar* max = nullptr;
  if (x->CanComputeBounds(loop, branch, &min, &max)) {
    int64_t end = 0;
    if (is_lower) {
      if (InductionVar::IsConstant(min, &end)) {
        return kMinInt64 < end;
      }
    } else if (InductionVar::IsConstant(max, &end)) {
      return end < kMaxInt64;
    } else if (InductionVar::IsInvariant(max) && max->mult() == 1 &&
               Definition::IsLengthLoad(max->def())) {
      return max->offset() < 0;  // a.length - C, C > 0
    }
  }
  return false;
}

// Helper method to adjust a range [lower_bound,upper_bound] into the
// range [lower_bound+lower_bound_offset,upper_bound+upper_bound+offset]
// without arithmetic wrap-around complications. On entry, we know that
// lower_bound <= upper_bound is enforced by an actual comparison in the
// code (so that even if lower_bound > upper_bound, the loop is not taken).
// This method ensures the resulting range has the same property by
// very conservatively testing if everything stays between constants
// or a properly offset array length.
static bool SafelyAdjust(Zone* zone,
                         InductionVar* lower_bound,
                         int64_t lower_bound_offset,
                         InductionVar* upper_bound,
                         int64_t upper_bound_offset,
                         InductionVar** min,
                         InductionVar** max) {
  bool success = false;
  int64_t lval = 0;
  int64_t uval = 0;
  if (InductionVar::IsConstant(lower_bound, &lval)) {
    const int64_t l = lval + lower_bound_offset;
    if (InductionVar::IsConstant(upper_bound, &uval)) {
      // Make sure a proper new range [l,u] results. Even if bounds
      // were subject to arithmetic wrap-around, we preserve the
      // property that the minimum is in l and the maximum in u.
      const int64_t u = uval + upper_bound_offset;
      success = (l <= u);
    } else if (InductionVar::IsInvariant(upper_bound) &&
               upper_bound->mult() == 1 &&
               Definition::IsLengthLoad(upper_bound->def())) {
      // No arithmetic wrap-around on the lower bound, and a properly
      // non-positive offset on an array length, which is always >= 0.
      const int64_t c = upper_bound->offset() + upper_bound_offset;
      success = ((lower_bound_offset >= 0 && lval <= l) ||
                 (lower_bound_offset < 0 && lval > l)) &&
                (c <= 0);
    }
  }
  if (success) {
    *min = (lower_bound_offset == 0)
               ? lower_bound
               : new (zone) InductionVar(lval + lower_bound_offset);
    *max = (upper_bound_offset == 0)
               ? upper_bound
               : new (zone)
                     InductionVar(upper_bound->offset() + upper_bound_offset,
                                  upper_bound->mult(), upper_bound->def());
  }
  return success;
}

void InductionVarAnalysis::VisitHierarchy(LoopInfo* loop) {
  for (; loop != nullptr; loop = loop->next_) {
    VisitLoop(loop);
    VisitHierarchy(loop->inner_);
  }
}

void InductionVarAnalysis::VisitLoop(LoopInfo* loop) {
  loop->ResetInduction();
  // Find strongly connected components (SSCs) in the SSA graph of this
  // loop using Tarjan's algorithm. Due to the descendant-first nature,
  // classification happens "on-demand".
  current_index_ = 0;
  ASSERT(stack_.is_empty());
  ASSERT(map_.IsEmpty());
  ASSERT(branches_.is_empty());
  for (BitVector::Iterator it(loop->blocks_); !it.Done(); it.Advance()) {
    BlockEntryInstr* block = preorder_[it.Current()];
    ASSERT(block->loop_info() != nullptr);
    if (block->loop_info() != loop) {
      continue;  // inner loop
    }
    // Visit phi-operations.
    if (block->IsJoinEntry()) {
      for (PhiIterator it(block->AsJoinEntry()); !it.Done(); it.Advance()) {
        Visit(loop, it.Current());
      }
    }
    // Visit instructions and collect branches.
    for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
      Instruction* instruction = it.Current();
      Visit(loop, instruction->AsDefinition());
      if (instruction->IsBranch()) {
        branches_.Add(instruction->AsBranch());
      }
    }
  }
  ASSERT(stack_.is_empty());
  map_.Clear();
  // Classify loop control.
  ClassifyControl(loop);
  branches_.Clear();
}

bool InductionVarAnalysis::Visit(LoopInfo* loop, Definition* def) {
  if (def == nullptr || map_.HasKey(def)) {
    return false;  // no def, or already visited
  }
  intptr_t d = ++current_index_;
  map_.Insert(VisitKV::Pair(def, SCCInfo(d)));
  stack_.Add(def);

  // Visit all descendants.
  intptr_t low = d;
  for (intptr_t i = 0, n = def->InputCount(); i < n; i++) {
    Value* input = def->InputAt(i);
    if (input != nullptr) {
      low = Utils::Minimum(low, VisitDescendant(loop, input->definition()));
    }
  }

  // Lower or found SCC?
  if (low < d) {
    map_.Lookup(def)->value.depth = low;
  } else {
    // Pop the stack to build the SCC for classification.
    ASSERT(scc_.is_empty());
    while (!stack_.is_empty()) {
      Definition* top = stack_.RemoveLast();
      scc_.Add(top);
      map_.Lookup(top)->value.done = true;
      if (top == def) {
        break;
      }
    }
    // Classify.
    if (scc_.length() == 1) {
      Classify(loop, scc_[0]);
    } else {
      ASSERT(scc_.length() > 1);
      ASSERT(cycle_.IsEmpty());
      ClassifySCC(loop);
      cycle_.Clear();
    }
    scc_.Clear();
  }
  return true;
}

intptr_t InductionVarAnalysis::VisitDescendant(LoopInfo* loop,
                                               Definition* def) {
  // The traversal stops at anything not defined in this loop
  // (either a loop invariant entry value defined outside the
  // loop or an inner exit value defined by an inner loop).
  if (def->GetBlock()->loop_info() != loop) {
    return current_index_;
  }
  // Inspect descendant node.
  if (!Visit(loop, def) && map_.Lookup(def)->value.done) {
    return current_index_;
  }
  return map_.Lookup(def)->value.depth;
}

void InductionVarAnalysis::Classify(LoopInfo* loop, Definition* def) {
  // Classify different kind of instructions.
  InductionVar* induc = nullptr;
  if (loop->IsHeaderPhi(def)) {
    intptr_t idx = InitIndex(loop);
    induc = TransferPhi(loop, def, idx);
    if (induc != nullptr) {
      InductionVar* init = Lookup(loop, def->InputAt(idx)->definition());
      // Wrap-around (except for unusual header phi(x,..,x) = x).
      if (!init->IsEqual(induc)) {
        induc =
            new (zone_) InductionVar(InductionVar::kWrapAround, init, induc);
      }
    }
  } else if (def->IsPhi()) {
    induc = TransferPhi(loop, def);
  } else {
    induc = TransferDef(loop, def);
  }
  // Successfully classified?
  if (induc != nullptr) {
    loop->AddInduction(def, induc);
  }
}

void InductionVarAnalysis::ClassifySCC(LoopInfo* loop) {
  intptr_t size = scc_.length();
  // Find a header phi, usually at the end.
  intptr_t p = -1;
  for (intptr_t i = size - 1; i >= 0; i--) {
    if (loop->IsHeaderPhi(scc_[i])) {
      p = i;
      break;
    }
  }
  // Rotate header phi up front.
  if (p >= 0) {
    Definition* phi = scc_[p];
    intptr_t idx = InitIndex(loop);
    InductionVar* init = Lookup(loop, phi->InputAt(idx)->definition());
    // Inspect remainder of the cycle. The cycle mapping assigns temporary
    // meaning to instructions, seeded from the phi instruction and back.
    // The init of the phi is passed as marker token to detect first use.
    cycle_.Insert(LoopInfo::InductionKV::Pair(phi, init));
    for (intptr_t i = 1, j = p; i < size; i++) {
      if (++j >= size) j = 0;
      Definition* def = scc_[j];
      InductionVar* update = nullptr;
      if (def->IsPhi()) {
        update = SolvePhi(loop, def);
      } else if (def->IsBinaryIntegerOp()) {
        update = SolveBinary(loop, def, init);
      } else if (def->IsUnaryIntegerOp()) {
        update = SolveUnary(loop, def, init);
      } else if (def->IsConstraint()) {
        update = SolveConstraint(loop, def, init);
      } else {
        Definition* orig = def->OriginalDefinitionIgnoreBoxingAndConstraints();
        if (orig != def) {
          update = LookupCycle(orig);  // pass-through
        }
      }
      // Continue cycle?
      if (update == nullptr) {
        return;
      }
      cycle_.Insert(LoopInfo::InductionKV::Pair(def, update));
    }
    // Success if all internal links (inputs to the phi that are along
    // back-edges) received the same temporary meaning. The external
    // link (initial value coming from outside the loop) is excluded
    // while taking this join.
    InductionVar* induc = SolvePhi(loop, phi, idx);
    if (induc != nullptr) {
      // Invariant means linear induction.
      if (induc->kind_ == InductionVar::kInvariant) {
        induc = new (zone_) InductionVar(InductionVar::kLinear, init, induc);
      } else {
        ASSERT(induc->kind_ == InductionVar::kPeriodic);
      }
      // Classify first phi and then the rest of the cycle "on-demand".
      loop->AddInduction(phi, induc);
      for (intptr_t i = 1, j = p; i < size; i++) {
        if (++j >= size) j = 0;
        Classify(loop, scc_[j]);
      }
    }
  }
}

void InductionVarAnalysis::ClassifyControl(LoopInfo* loop) {
  for (auto branch : branches_) {
    // Proper comparison?
    ConditionInstr* condition = branch->condition();
    if (condition->InputCount() != 2) {
      continue;
    }
    Token::Kind cmp = condition->kind();
    // Proper loop exit? Express the condition in "loop while true" form.
    TargetEntryInstr* ift = branch->true_successor();
    TargetEntryInstr* iff = branch->false_successor();
    if (loop->Contains(ift) && !loop->Contains(iff)) {
      // ok as is
    } else if (!loop->Contains(ift) && loop->Contains(iff)) {
      cmp = Token::NegateComparison(cmp);
    } else {
      continue;
    }
    // Comparison against linear constant stride induction?
    // Express the comparison such that induction appears left.
    int64_t stride = 0;
    auto left = condition->InputAt(0)
                    ->definition()
                    ->OriginalDefinitionIgnoreBoxingAndConstraints();
    auto right = condition->InputAt(1)
                     ->definition()
                     ->OriginalDefinitionIgnoreBoxingAndConstraints();
    InductionVar* x = Lookup(loop, left);
    InductionVar* y = Lookup(loop, right);
    if (InductionVar::IsLinear(x, &stride) && InductionVar::IsInvariant(y)) {
      // ok as is
    } else if (InductionVar::IsInvariant(x) &&
               InductionVar::IsLinear(y, &stride)) {
      InductionVar* tmp = x;
      x = y;
      y = tmp;
      cmp = Token::FlipComparison(cmp);
    } else {
      continue;
    }
    // Can we find a strict (exclusive) comparison for the looping condition?
    // Note that we reject symbolic bounds in non-strict (inclusive) looping
    // conditions like i <= U as upperbound or i >= L as lowerbound since this
    // could loop forever when U is kMaxInt64 or L is kMinInt64 under Dart's
    // 64-bit arithmetic wrap-around. Non-unit strides could overshoot the
    // bound due to arithmetic wrap-around.
    switch (cmp) {
      case Token::kLT:
        // Accept i < U (i++).
        if (stride == 1) break;
        continue;
      case Token::kGT:
        // Accept i > L (i--).
        if (stride == -1) break;
        continue;
      case Token::kLTE: {
        // Accept i <= U (i++) as i < U + 1
        // only when U != MaxInt is certain.
        if (stride == 1 &&
            CanBeMadeExclusive(loop, y, branch, /*is_lower=*/false)) {
          y = Add(y, new (zone_) InductionVar(1));
          break;
        }
        continue;
      }
      case Token::kGTE: {
        // Accept i >= L (i--) as i > L - 1
        // only when L != MinInt is certain.
        if (stride == -1 &&
            CanBeMadeExclusive(loop, y, branch, /*is_lower=*/true)) {
          y = Sub(y, new (zone_) InductionVar(1));
          break;
        }
        continue;
      }
      case Token::kNE: {
        // Accept i != E as either i < E (i++) or i > E (i--)
        // for constants bounds that make the loop always-taken.
        int64_t start = 0;
        int64_t end = 0;
        if (InductionVar::IsConstant(x->initial_, &start) &&
            InductionVar::IsConstant(y, &end)) {
          if ((stride == +1 && start < end) || (stride == -1 && start > end)) {
            break;
          }
        }
        continue;
      }
      default:
        continue;
    }
    // We found a strict upper or lower bound on a unit stride linear
    // induction. Note that depending on the intended use of this
    // information, clients should still test dominance on the test
    // and the initial value of the induction variable.
    x->bounds_.Add(InductionVar::Bound(branch, y));
    // Record control induction.
    if (branch == loop->header_->last_instruction()) {
      loop->control_ = x;
    }
  }
}

InductionVar* InductionVarAnalysis::TransferPhi(LoopInfo* loop,
                                                Definition* def,
                                                intptr_t idx) {
  InductionVar* induc = nullptr;
  for (intptr_t i = 0, n = def->InputCount(); i < n; i++) {
    if (i != idx) {
      InductionVar* x = Lookup(loop, def->InputAt(i)->definition());
      if (x == nullptr) {
        return nullptr;
      } else if (induc == nullptr) {
        induc = x;
      } else if (!induc->IsEqual(x)) {
        return nullptr;
      }
    }
  }
  return induc;
}

InductionVar* InductionVarAnalysis::TransferDef(LoopInfo* loop,
                                                Definition* def) {
  if (def->IsBinaryIntegerOp()) {
    return TransferBinary(loop, def);
  } else if (def->IsUnaryIntegerOp()) {
    return TransferUnary(loop, def);
  } else {
    // Note that induction analysis does not really need the second
    // argument of a bound check, since it will just pass-through the
    // index. However, we do a lookup on the, most likely loop-invariant,
    // length anyway, to make sure it is stored in the induction
    // environment for later lookup during BCE.
    if (auto check = def->AsCheckBoundBase()) {
      Definition* len = check->length()
                            ->definition()
                            ->OriginalDefinitionIgnoreBoxingAndConstraints();
      Lookup(loop, len);  // pre-store likely invariant length
    }
    // Proceed with regular pass-through.
    Definition* orig = def->OriginalDefinitionIgnoreBoxingAndConstraints();
    if (orig != def) {
      return Lookup(loop, orig);  // pass-through
    }
  }
  return nullptr;
}

InductionVar* InductionVarAnalysis::TransferBinary(LoopInfo* loop,
                                                   Definition* def) {
  InductionVar* x = Lookup(loop, def->InputAt(0)->definition());
  InductionVar* y = Lookup(loop, def->InputAt(1)->definition());

  switch (def->AsBinaryIntegerOp()->op_kind()) {
    case Token::kADD:
      return Add(x, y);
    case Token::kSUB:
      return Sub(x, y);
    case Token::kMUL:
      return Mul(x, y);
    default:
      return nullptr;
  }
}

InductionVar* InductionVarAnalysis::TransferUnary(LoopInfo* loop,
                                                  Definition* def) {
  InductionVar* x = Lookup(loop, def->InputAt(0)->definition());
  switch (def->AsUnaryIntegerOp()->op_kind()) {
    case Token::kNEGATE: {
      InductionVar* zero = new (zone_) InductionVar(0);
      return Sub(zero, x);
    }
    default:
      return nullptr;
  }
}

InductionVar* InductionVarAnalysis::SolvePhi(LoopInfo* loop,
                                             Definition* def,
                                             intptr_t idx) {
  InductionVar* induc = nullptr;
  for (intptr_t i = 0, n = def->InputCount(); i < n; i++) {
    if (i != idx) {
      InductionVar* c = LookupCycle(def->InputAt(i)->definition());
      if (c == nullptr) {
        return nullptr;
      } else if (induc == nullptr) {
        induc = c;
      } else if (!induc->IsEqual(c)) {
        return nullptr;
      }
    }
  }
  return induc;
}

InductionVar* InductionVarAnalysis::SolveConstraint(LoopInfo* loop,
                                                    Definition* def,
                                                    InductionVar* init) {
  InductionVar* c = LookupCycle(def->InputAt(0)->definition());
  if (c == init) {
    // Record a non-artificial bound constraint on a phi.
    ConstraintInstr* constraint = def->AsConstraint();
    if (constraint->target() != nullptr) {
      loop->limit_ = constraint;
    }
  }
  return c;
}

InductionVar* InductionVarAnalysis::SolveBinary(LoopInfo* loop,
                                                Definition* def,
                                                InductionVar* init) {
  InductionVar* x = Lookup(loop, def->InputAt(0)->definition());
  InductionVar* y = Lookup(loop, def->InputAt(1)->definition());
  switch (def->AsBinaryIntegerOp()->op_kind()) {
    case Token::kADD:
      if (InductionVar::IsInvariant(x)) {
        InductionVar* c = LookupCycle(def->InputAt(1)->definition());
        // The init marker denotes first use, otherwise aggregate.
        if (c == init) {
          return x;
        } else if (InductionVar::IsInvariant(c)) {
          return Add(x, c);
        }
      }
      if (InductionVar::IsInvariant(y)) {
        InductionVar* c = LookupCycle(def->InputAt(0)->definition());
        // The init marker denotes first use, otherwise aggregate.
        if (c == init) {
          return y;
        } else if (InductionVar::IsInvariant(c)) {
          return Add(c, y);
        }
      }
      return nullptr;
    case Token::kSUB:
      if (InductionVar::IsInvariant(x)) {
        InductionVar* c = LookupCycle(def->InputAt(1)->definition());
        // Note that i = x - i is periodic. The temporary
        // meaning is expressed in terms of the header phi.
        if (c == init) {
          InductionVar* next = Sub(x, init);
          if (InductionVar::IsInvariant(next)) {
            return new (zone_)
                InductionVar(InductionVar::kPeriodic, init, next);
          }
        }
      }
      if (InductionVar::IsInvariant(y)) {
        InductionVar* c = LookupCycle(def->InputAt(0)->definition());
        // The init marker denotes first use, otherwise aggregate.
        if (c == init) {
          InductionVar* zero = new (zone_) InductionVar(0);
          return Sub(zero, y);
        } else if (InductionVar::IsInvariant(c)) {
          return Sub(c, y);
        }
      }
      return nullptr;
    default:
      return nullptr;
  }
}

InductionVar* InductionVarAnalysis::SolveUnary(LoopInfo* loop,
                                               Definition* def,
                                               InductionVar* init) {
  InductionVar* c = LookupCycle(def->InputAt(0)->definition());
  switch (def->AsUnaryIntegerOp()->op_kind()) {
    case Token::kNEGATE:
      // Note that i = - i is periodic. The temporary
      // meaning is expressed in terms of the header phi.
      if (c == init) {
        InductionVar* zero = new (zone_) InductionVar(0);
        InductionVar* next = Sub(zero, init);
        if (InductionVar::IsInvariant(next)) {
          return new (zone_) InductionVar(InductionVar::kPeriodic, init, next);
        }
      }
      return nullptr;
    default:
      return nullptr;
  }
}

InductionVar* InductionVarAnalysis::Lookup(LoopInfo* loop, Definition* def) {
  InductionVar* induc = loop->LookupInduction(def);
  if (induc == nullptr) {
    // Loop-invariants are added lazily.
    int64_t val = 0;
    if (IsConstant(def, &val)) {
      induc = new (zone_) InductionVar(val);
      loop->AddInduction(def, induc);
    } else if (!loop->Contains(def->GetBlock())) {
      // Look "under the hood" of invariant definitions to expose
      // more details on common constructs like "length - 1".
      induc = TransferDef(loop, def);
      if (induc == nullptr) {
        induc = new (zone_) InductionVar(0, 1, def);
      }
      loop->AddInduction(def, induc);
    }
  }
  return induc;
}

InductionVar* InductionVarAnalysis::LookupCycle(Definition* def) {
  LoopInfo::InductionKV::Pair* pair = cycle_.Lookup(def);
  if (pair != nullptr) {
    return pair->value;
  }
  return nullptr;
}

InductionVar* InductionVarAnalysis::Add(InductionVar* x, InductionVar* y) {
  if (InductionVar::IsInvariant(x)) {
    if (InductionVar::IsInvariant(y)) {
      // Invariant + Invariant : only for same or just one instruction.
      if (x->def_ == y->def_) {
        return new (zone_)
            InductionVar(Utils::AddWithWrapAround(x->offset_, y->offset_),
                         Utils::AddWithWrapAround(x->mult_, y->mult_), x->def_);
      } else if (y->mult_ == 0) {
        return new (zone_)
            InductionVar(Utils::AddWithWrapAround(x->offset_, y->offset_),
                         x->mult_, x->def_);
      } else if (x->mult_ == 0) {
        return new (zone_)
            InductionVar(Utils::AddWithWrapAround(x->offset_, y->offset_),
                         y->mult_, y->def_);
      }
    } else if (y != nullptr) {
      // Invariant + Induction.
      InductionVar* i = Add(x, y->initial_);
      InductionVar* n =
          y->kind_ == InductionVar::kLinear ? y->next_ : Add(x, y->next_);
      if (i != nullptr && n != nullptr) {
        return new (zone_) InductionVar(y->kind_, i, n);
      }
    }
  } else if (InductionVar::IsInvariant(y)) {
    if (x != nullptr) {
      // Induction + Invariant.
      ASSERT(!InductionVar::IsInvariant(x));
      InductionVar* i = Add(x->initial_, y);
      InductionVar* n =
          x->kind_ == InductionVar::kLinear ? x->next_ : Add(x->next_, y);
      if (i != nullptr && n != nullptr) {
        return new (zone_) InductionVar(x->kind_, i, n);
      }
    }
  } else if (InductionVar::IsLinear(x) && InductionVar::IsLinear(y)) {
    // Linear + Linear.
    InductionVar* i = Add(x->initial_, y->initial_);
    InductionVar* n = Add(x->next_, y->next_);
    if (i != nullptr && n != nullptr) {
      return new (zone_) InductionVar(InductionVar::kLinear, i, n);
    }
  }
  return nullptr;
}

InductionVar* InductionVarAnalysis::Sub(InductionVar* x, InductionVar* y) {
  if (InductionVar::IsInvariant(x)) {
    if (InductionVar::IsInvariant(y)) {
      // Invariant + Invariant : only for same or just one instruction.
      if (x->def_ == y->def_) {
        return new (zone_)
            InductionVar(Utils::SubWithWrapAround(x->offset_, y->offset_),
                         Utils::SubWithWrapAround(x->mult_, y->mult_), x->def_);
      } else if (y->mult_ == 0) {
        return new (zone_)
            InductionVar(Utils::SubWithWrapAround(x->offset_, y->offset_),
                         x->mult_, x->def_);
      } else if (x->mult_ == 0) {
        return new (zone_)
            InductionVar(Utils::SubWithWrapAround(x->offset_, y->offset_),
                         Utils::NegWithWrapAround(y->mult_), y->def_);
      }
    } else if (y != nullptr) {
      // Invariant - Induction.
      InductionVar* i = Sub(x, y->initial_);
      InductionVar* n;
      if (y->kind_ == InductionVar::kLinear) {
        InductionVar* zero = new (zone_) InductionVar(0, 0, nullptr);
        n = Sub(zero, y->next_);
      } else {
        n = Sub(x, y->next_);
      }
      if (i != nullptr && n != nullptr) {
        return new (zone_) InductionVar(y->kind_, i, n);
      }
    }
  } else if (InductionVar::IsInvariant(y)) {
    if (x != nullptr) {
      // Induction - Invariant.
      ASSERT(!InductionVar::IsInvariant(x));
      InductionVar* i = Sub(x->initial_, y);
      InductionVar* n =
          x->kind_ == InductionVar::kLinear ? x->next_ : Sub(x->next_, y);
      if (i != nullptr && n != nullptr) {
        return new (zone_) InductionVar(x->kind_, i, n);
      }
    }
  } else if (InductionVar::IsLinear(x) && InductionVar::IsLinear(y)) {
    // Linear - Linear.
    InductionVar* i = Sub(x->initial_, y->initial_);
    InductionVar* n = Sub(x->next_, y->next_);
    if (i != nullptr && n != nullptr) {
      return new (zone_) InductionVar(InductionVar::kLinear, i, n);
    }
  }
  return nullptr;
}

InductionVar* InductionVarAnalysis::Mul(InductionVar* x, InductionVar* y) {
  // Swap constant left.
  if (!InductionVar::IsConstant(x)) {
    InductionVar* tmp = x;
    x = y;
    y = tmp;
  }
  // Apply constant to any induction.
  if (InductionVar::IsConstant(x) && y != nullptr) {
    if (y->kind_ == InductionVar::kInvariant) {
      return new (zone_)
          InductionVar(Utils::MulWithWrapAround(x->offset_, y->offset_),
                       Utils::MulWithWrapAround(x->offset_, y->mult_), y->def_);
    }
    return new (zone_)
        InductionVar(y->kind_, Mul(x, y->initial_), Mul(x, y->next_));
  }
  return nullptr;
}

bool InductionVar::CanComputeDifferenceWith(const InductionVar* other,
                                            int64_t* diff) const {
  if (IsInvariant(this) && IsInvariant(other)) {
    if (def_ == other->def_ && mult_ == other->mult_) {
      *diff = other->offset_ - offset_;
      return true;
    }
  } else if (IsLinear(this) && IsLinear(other)) {
    return next_->IsEqual(other->next_) &&
           initial_->CanComputeDifferenceWith(other->initial_, diff);
  }
  // TODO(ajcbik): examine other induction kinds too?
  return false;
}

bool InductionVar::CanComputeBoundsImpl(LoopInfo* loop,
                                        Instruction* pos,
                                        InductionVar** min,
                                        InductionVar** max) {
  // Refine symbolic part of an invariant with outward induction.
  if (IsInvariant(this)) {
    if (mult_ == 1 && def_ != nullptr) {
      for (loop = loop->outer(); loop != nullptr; loop = loop->outer()) {
        InductionVar* induc = loop->LookupInduction(def_);
        InductionVar* i_min = nullptr;
        InductionVar* i_max = nullptr;
        // Accept i+C with i in [L,U] as [L+C,U+C] when this adjustment
        // does not have arithmetic wrap-around complications.
        if (IsInduction(induc) &&
            induc->CanComputeBounds(loop, pos, &i_min, &i_max)) {
          Zone* z = Thread::Current()->zone();
          return SafelyAdjust(z, i_min, offset_, i_max, offset_, min, max);
        }
      }
    }
    // Otherwise invariant itself suffices.
    *min = *max = this;
    return true;
  }
  // Refine unit stride induction with lower and upper bound.
  //    for (int i = L; i < U; i++)
  //       j = i+C in [L+C,U+C-1]
  int64_t stride = 0;
  int64_t off = 0;
  if (IsLinear(this, &stride) && Utils::Abs(stride) == 1 &&
      CanComputeDifferenceWith(loop->control(), &off)) {
    // Find ranges on both L and U first (and not just minimum
    // of L and maximum of U) to avoid arithmetic wrap-around
    // complications such as the one shown below.
    //   for (int i = 0; i < maxint - 10; i++)
    //     for (int j = i + 20; j < 100; j++)
    //       j in [minint, 99] and not in [20, 100]
    InductionVar* l_min = nullptr;
    InductionVar* l_max = nullptr;
    if (initial_->CanComputeBounds(loop, pos, &l_min, &l_max)) {
      // Find extreme using a control bound for which the branch dominates
      // the given position (to make sure it really is under its control).
      // Then refine with anything that dominates that branch.
      for (auto bound : loop->control()->bounds()) {
        if (pos->IsDominatedBy(bound.branch_)) {
          InductionVar* u_min = nullptr;
          InductionVar* u_max = nullptr;
          if (bound.limit_->CanComputeBounds(loop, bound.branch_, &u_min,
                                             &u_max)) {
            Zone* z = Thread::Current()->zone();
            return stride > 0 ? SafelyAdjust(z, l_min, 0, u_max, -stride - off,
                                             min, max)
                              : SafelyAdjust(z, u_min, -stride - off, l_max, 0,
                                             min, max);
          }
        }
      }
    }
  }
  // Failure. TODO(ajcbik): examine other kinds of induction too?
  return false;
}

// Driver method to compute bounds with per-loop memoization.
bool InductionVar::CanComputeBounds(LoopInfo* loop,
                                    Instruction* pos,
                                    InductionVar** min,
                                    InductionVar** max) {
  // Consult cache first.
  LoopInfo::MemoKV::Pair* pair1 = loop->memo_cache_.Lookup(this);
  if (pair1 != nullptr) {
    LoopInfo::MemoVal::PosKV::Pair* pair2 = pair1->value->memo_.Lookup(pos);
    if (pair2 != nullptr) {
      *min = pair2->value.first;
      *max = pair2->value.second;
      return true;
    }
  }
  // Compute and cache.
  if (CanComputeBoundsImpl(loop, pos, min, max)) {
    ASSERT(*min != nullptr && *max != nullptr);
    LoopInfo::MemoVal* memo = nullptr;
    if (pair1 != nullptr) {
      memo = pair1->value;
    } else {
      memo = new LoopInfo::MemoVal();
      loop->memo_cache_.Insert(LoopInfo::MemoKV::Pair(this, memo));
    }
    memo->memo_.Insert(
        LoopInfo::MemoVal::PosKV::Pair(pos, std::make_pair(*min, *max)));
    return true;
  }
  return false;
}

void InductionVar::PrintTo(BaseTextBuffer* f) const {
  switch (kind_) {
    case kInvariant:
      if (mult_ != 0) {
        f->Printf("(%" Pd64 " + %" Pd64 " x %.4s)", offset_, mult_,
                  def_->ToCString());
      } else {
        f->Printf("%" Pd64, offset_);
      }
      break;
    case kLinear:
      f->Printf("LIN(%s + %s * i)", initial_->ToCString(), next_->ToCString());
      break;
    case kWrapAround:
      f->Printf("WRAP(%s, %s)", initial_->ToCString(), next_->ToCString());
      break;
    case kPeriodic:
      f->Printf("PERIOD(%s, %s)", initial_->ToCString(), next_->ToCString());
      break;
  }
}

const char* InductionVar::ToCString() const {
  char buffer[1024];
  BufferFormatter f(buffer, sizeof(buffer));
  PrintTo(&f);
  return Thread::Current()->zone()->MakeCopyOfString(buffer);
}

LoopInfo::LoopInfo(intptr_t id, BlockEntryInstr* header, BitVector* blocks)
    : id_(id),
      header_(header),
      blocks_(blocks),
      back_edges_(),
      induction_(),
      memo_cache_(),
      limit_(nullptr),
      control_(nullptr),
      outer_(nullptr),
      inner_(nullptr),
      next_(nullptr) {}

void LoopInfo::AddBlocks(BitVector* blocks) {
  blocks_->AddAll(blocks);
}

void LoopInfo::AddBackEdge(BlockEntryInstr* block) {
  back_edges_.Add(block);
}

bool LoopInfo::IsBackEdge(BlockEntryInstr* block) const {
  for (intptr_t i = 0, n = back_edges_.length(); i < n; i++) {
    if (back_edges_[i] == block) {
      return true;
    }
  }
  return false;
}

bool LoopInfo::IsAlwaysTaken(BlockEntryInstr* block) const {
  // The loop header is always executed when executing a loop (including
  // loop body of a do-while). Reject any other loop body block that is
  // not directly controlled by header.
  if (block == header_) {
    return true;
  } else if (block->PredecessorCount() != 1 ||
             block->PredecessorAt(0) != header_) {
    return false;
  }
  // If the loop has a control induction, make sure the condition is such
  // that the loop body is entered at least once from the header.
  if (control_ != nullptr) {
    InductionVar* limit = nullptr;
    for (auto bound : control_->bounds()) {
      if (bound.branch_ == header_->last_instruction()) {
        limit = bound.limit_;
        break;
      }
    }
    // Control iterates at least once?
    if (limit != nullptr) {
      int64_t stride = 0;
      int64_t begin = 0;
      int64_t end = 0;
      if (InductionVar::IsLinear(control_, &stride) &&
          InductionVar::IsConstant(control_->initial(), &begin) &&
          InductionVar::IsConstant(limit, &end) &&
          ((stride == 1 && begin < end) || (stride == -1 && begin > end))) {
        return true;
      }
    }
  }
  return false;
}

bool LoopInfo::IsHeaderPhi(Definition* def) const {
  return def != nullptr && def->IsPhi() && def->GetBlock() == header_ &&
         !def->AsPhi()->IsRedundant();  // phi(x,..,x) = x
}

bool LoopInfo::IsIn(LoopInfo* loop) const {
  if (loop != nullptr) {
    return loop->Contains(header_);
  }
  return false;
}

bool LoopInfo::Contains(BlockEntryInstr* block) const {
  return blocks_->Contains(block->preorder_number());
}

intptr_t LoopInfo::NestingDepth() const {
  intptr_t nesting_depth = 1;
  for (LoopInfo* o = outer_; o != nullptr; o = o->outer()) {
    nesting_depth++;
  }
  return nesting_depth;
}

void LoopInfo::ResetInduction() {
  induction_.Clear();
  memo_cache_.Clear();
}

void LoopInfo::AddInduction(Definition* def, InductionVar* induc) {
  ASSERT(def != nullptr);
  ASSERT(induc != nullptr);
  induction_.Insert(InductionKV::Pair(def, induc));
}

InductionVar* LoopInfo::LookupInduction(Definition* def) const {
  InductionKV::Pair* pair = induction_.Lookup(def);
  if (pair != nullptr) {
    return pair->value;
  }
  return nullptr;
}

// Checks if an index is in range of a given length:
//   for (int i = initial; i <= length - C; i++) {
//     .... a[i] ....  // initial >= 0 and C > 0:
//   }
bool LoopInfo::IsInRange(Instruction* pos, Value* index, Value* length) {
  InductionVar* induc = LookupInduction(
      index->definition()->OriginalDefinitionIgnoreBoxingAndConstraints());
  InductionVar* len = LookupInduction(
      length->definition()->OriginalDefinitionIgnoreBoxingAndConstraints());
  if (induc != nullptr && len != nullptr) {
    // First, try the most common case. A simple induction directly
    // bounded by [c>=0,length-C>=0) for the length we are looking for.
    int64_t stride = 0;
    int64_t val = 0;
    int64_t diff = 0;
    if (InductionVar::IsLinear(induc, &stride) && stride == 1 &&
        InductionVar::IsConstant(induc->initial(), &val) && 0 <= val) {
      for (auto bound : induc->bounds()) {
        if (pos->IsDominatedBy(bound.branch_) &&
            len->CanComputeDifferenceWith(bound.limit_, &diff) && diff <= 0) {
          return true;
        }
      }
    }
    // If that fails, try to compute bounds using more outer loops.
    // Since array lengths >= 0, the conditions used during this
    // process avoid arithmetic wrap-around complications.
    InductionVar* min = nullptr;
    InductionVar* max = nullptr;
    if (induc->CanComputeBounds(this, pos, &min, &max)) {
      return InductionVar::IsConstant(min, &val) && 0 <= val &&
             len->CanComputeDifferenceWith(max, &diff) && diff < 0;
    }
  }
  return false;
}

void LoopInfo::PrintTo(BaseTextBuffer* f) const {
  f->Printf("%*c", static_cast<int>(2 * NestingDepth()), ' ');
  f->Printf("loop%" Pd " B%" Pd " ", id_, header_->block_id());
  intptr_t num_blocks = 0;
  for (BitVector::Iterator it(blocks_); !it.Done(); it.Advance()) {
    num_blocks++;
  }
  f->Printf("#blocks=%" Pd, num_blocks);
  if (outer_ != nullptr) f->Printf(" outer=%" Pd, outer_->id_);
  if (inner_ != nullptr) f->Printf(" inner=%" Pd, inner_->id_);
  if (next_ != nullptr) f->Printf(" next=%" Pd, next_->id_);
  f->AddString(" [");
  for (intptr_t i = 0, n = back_edges_.length(); i < n; i++) {
    f->Printf(" B%" Pd, back_edges_[i]->block_id());
  }
  f->AddString(" ]");
}

const char* LoopInfo::ToCString() const {
  char buffer[1024];
  BufferFormatter f(buffer, sizeof(buffer));
  PrintTo(&f);
  return Thread::Current()->zone()->MakeCopyOfString(buffer);
}

LoopHierarchy::LoopHierarchy(ZoneGrowableArray<BlockEntryInstr*>* headers,
                             const GrowableArray<BlockEntryInstr*>& preorder,
                             bool print_traces)
    : headers_(headers),
      preorder_(preorder),
      top_(nullptr),
      print_traces_(print_traces) {
  Build();
}

void LoopHierarchy::Build() {
  // Link every entry block to the closest enveloping loop.
  for (intptr_t i = 0, n = headers_->length(); i < n; ++i) {
    LoopInfo* loop = (*headers_)[i]->loop_info();
    for (BitVector::Iterator it(loop->blocks_); !it.Done(); it.Advance()) {
      BlockEntryInstr* block = preorder_[it.Current()];
      if (block->loop_info() == nullptr) {
        block->set_loop_info(loop);
      } else {
        ASSERT(block->loop_info()->IsIn(loop));
      }
    }
  }
  // Build hierarchy from headers.
  for (intptr_t i = 0, n = headers_->length(); i < n; ++i) {
    BlockEntryInstr* header = (*headers_)[i];
    LoopInfo* loop = header->loop_info();
    LoopInfo* dom_loop = header->dominator()->loop_info();
    ASSERT(loop->outer_ == nullptr);
    ASSERT(loop->next_ == nullptr);
    if (loop->IsIn(dom_loop)) {
      loop->outer_ = dom_loop;
      loop->next_ = dom_loop->inner_;
      dom_loop->inner_ = loop;
    } else {
      loop->next_ = top_;
      top_ = loop;
    }
  }
  // If tracing is requested, print the loop hierarchy.
  if (FLAG_trace_optimization && print_traces_) {
    Print(top_);
  }
}

void LoopHierarchy::Print(LoopInfo* loop) const {
  for (; loop != nullptr; loop = loop->next_) {
    THR_Print("%s {", loop->ToCString());
    for (BitVector::Iterator it(loop->blocks_); !it.Done(); it.Advance()) {
      THR_Print(" B%" Pd, preorder_[it.Current()]->block_id());
    }
    THR_Print(" }\n");
    Print(loop->inner_);
  }
}

void LoopHierarchy::ComputeInduction() const {
  InductionVarAnalysis(preorder_).VisitHierarchy(top_);
}

}  // namespace dart