compiler/optimizing/induction_var_analysis.cc

/*
 * Copyright (C) 2015 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.
 */

#include "induction_var_analysis.h"

namespace art {

/**
 * Returns true if instruction is invariant within the given loop.
 */
static bool IsLoopInvariant(HLoopInformation* loop, HInstruction* instruction) {
  HLoopInformation* other_loop = instruction->GetBlock()->GetLoopInformation();
  if (other_loop != loop) {
    // If instruction does not occur in same loop, it is invariant
    // if it appears in an outer loop (including no loop at all).
    return other_loop == nullptr || loop->IsIn(*other_loop);
  }
  return false;
}

/**
 * Returns true if instruction is proper entry-phi-operation for given loop
 * (referred to as mu-operation in Gerlek's paper).
 */
static bool IsEntryPhi(HLoopInformation* loop, HInstruction* instruction) {
  return
      instruction->IsPhi() &&
      instruction->InputCount() == 2 &&
      instruction->GetBlock() == loop->GetHeader();
}

//
// Class methods.
//

HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph)
    : HOptimization(graph, kInductionPassName),
      global_depth_(0),
      stack_(graph->GetArena()->Adapter()),
      scc_(graph->GetArena()->Adapter()),
      map_(std::less<int>(), graph->GetArena()->Adapter()),
      cycle_(std::less<int>(), graph->GetArena()->Adapter()),
      induction_(std::less<int>(), graph->GetArena()->Adapter()) {
}

void HInductionVarAnalysis::Run() {
  // Detects sequence variables (generalized induction variables) during an
  // inner-loop-first traversal of all loops using Gerlek's algorithm.
  for (HPostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
    HBasicBlock* graph_block = it_graph.Current();
    if (graph_block->IsLoopHeader()) {
      VisitLoop(graph_block->GetLoopInformation());
    }
  }
}

void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
  // 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".
  global_depth_ = 0;
  CHECK(stack_.empty());
  map_.clear();

  for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
    HBasicBlock* loop_block = it_loop.Current();
    CHECK(loop_block->IsInLoop());
    if (loop_block->GetLoopInformation() != loop) {
      continue;  // Inner loops already visited.
    }
    // Visit phi-operations and instructions.
    for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) {
      HInstruction* instruction = it.Current();
      if (!IsVisitedNode(instruction->GetId())) {
        VisitNode(loop, instruction);
      }
    }
    for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) {
      HInstruction* instruction = it.Current();
      if (!IsVisitedNode(instruction->GetId())) {
        VisitNode(loop, instruction);
      }
    }
  }

  CHECK(stack_.empty());
  map_.clear();
}

void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) {
  const int id = instruction->GetId();
  const uint32_t d1 = ++global_depth_;
  map_.Put(id, NodeInfo(d1));
  stack_.push_back(instruction);

  // Visit all descendants.
  uint32_t low = d1;
  for (size_t i = 0, count = instruction->InputCount(); i < count; ++i) {
    low = std::min(low, VisitDescendant(loop, instruction->InputAt(i)));
  }

  // Lower or found SCC?
  if (low < d1) {
    map_.find(id)->second.depth = low;
  } else {
    scc_.clear();
    cycle_.clear();

    // Pop the stack to build the SCC for classification.
    while (!stack_.empty()) {
      HInstruction* x = stack_.back();
      scc_.push_back(x);
      stack_.pop_back();
      map_.find(x->GetId())->second.done = true;
      if (x == instruction) {
        break;
      }
    }

    // Classify the SCC.
    if (scc_.size() == 1 && !IsEntryPhi(loop, scc_[0])) {
      ClassifyTrivial(loop, scc_[0]);
    } else {
      ClassifyNonTrivial(loop);
    }

    scc_.clear();
    cycle_.clear();
  }
}

uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) {
  // If the definition is either outside the loop (loop invariant entry value)
  // or assigned in inner loop (inner exit value), the traversal stops.
  HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation();
  if (otherLoop != loop) {
    return global_depth_;
  }

  // Inspect descendant node.
  const int id = instruction->GetId();
  if (!IsVisitedNode(id)) {
    VisitNode(loop, instruction);
    return map_.find(id)->second.depth;
  } else {
    auto it = map_.find(id);
    return it->second.done ? global_depth_ : it->second.depth;
  }
}

void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
  InductionInfo* info = nullptr;
  if (instruction->IsPhi()) {
    for (size_t i = 1, count = instruction->InputCount(); i < count; i++) {
      info = TransferPhi(LookupInfo(loop, instruction->InputAt(0)),
                         LookupInfo(loop, instruction->InputAt(i)));
    }
  } else if (instruction->IsAdd()) {
    info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
                          LookupInfo(loop, instruction->InputAt(1)), kAdd);
  } else if (instruction->IsSub()) {
    info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
                          LookupInfo(loop, instruction->InputAt(1)), kSub);
  } else if (instruction->IsMul()) {
    info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
                       LookupInfo(loop, instruction->InputAt(1)));
  } else if (instruction->IsNeg()) {
    info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
  }

  // Successfully classified?
  if (info != nullptr) {
    AssignInfo(loop, instruction, info);
  }
}

void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
  const size_t size = scc_.size();
  CHECK_GE(size, 1u);
  HInstruction* phi = scc_[size - 1];
  if (!IsEntryPhi(loop, phi)) {
    return;
  }
  HInstruction* external = phi->InputAt(0);
  HInstruction* internal = phi->InputAt(1);
  InductionInfo* initial = LookupInfo(loop, external);
  if (initial == nullptr || initial->induction_class != kInvariant) {
    return;
  }

  // Singleton entry-phi-operation may be a wrap-around induction.
  if (size == 1) {
    InductionInfo* update = LookupInfo(loop, internal);
    if (update != nullptr) {
      AssignInfo(loop, phi, NewInductionInfo(kWrapAround, kNop, initial, update, nullptr));
    }
    return;
  }

  // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
  // temporary meaning to its nodes.
  cycle_.Overwrite(phi->GetId(), nullptr);
  for (size_t i = 0; i < size - 1; i++) {
    HInstruction* operation = scc_[i];
    InductionInfo* update = nullptr;
    if (operation->IsPhi()) {
      update = TransferCycleOverPhi(operation);
    } else if (operation->IsAdd()) {
      update = TransferCycleOverAddSub(loop, operation->InputAt(0), operation->InputAt(1), kAdd, true);
    } else if (operation->IsSub()) {
      update = TransferCycleOverAddSub(loop, operation->InputAt(0), operation->InputAt(1), kSub, true);
    }
    if (update == nullptr) {
      return;
    }
    cycle_.Overwrite(operation->GetId(), update);
  }

  // Success if the internal link received accumulated nonzero update.
  auto it = cycle_.find(internal->GetId());
  if (it != cycle_.end() && it->second != nullptr) {
    // Classify header phi and feed the cycle "on-demand".
    AssignInfo(loop, phi, NewInductionInfo(kLinear, kNop, it->second, initial, nullptr));
    for (size_t i = 0; i < size - 1; i++) {
      ClassifyTrivial(loop, scc_[i]);
    }
  }
}

HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(InductionInfo* a,
                                                                         InductionInfo* b) {
  // Transfer over a phi: if both inputs are identical, result is input.
  if (InductionEqual(a, b)) {
    return a;
  }
  return nullptr;
}

HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
                                                                            InductionInfo* b,
                                                                            InductionOp op) {
  // Transfer over an addition or subtraction: invariant or linear
  // inputs combine into new invariant or linear result.
  if (a != nullptr && b != nullptr) {
    if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
      return NewInductionInfo(kInvariant, op, a, b, nullptr);
    } else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
      return NewInductionInfo(
          kLinear,
          kNop,
          a->op_a,
          NewInductionInfo(kInvariant, op, a->op_b, b, nullptr),
          nullptr);
    } else if (a->induction_class == kInvariant && b->induction_class == kLinear) {
      InductionInfo* ba = b->op_a;
      if (op == kSub) {  // negation required
        ba = NewInductionInfo(kInvariant, kNeg, nullptr, ba, nullptr);
      }
      return NewInductionInfo(
          kLinear,
          kNop,
          ba,
          NewInductionInfo(kInvariant, op, a, b->op_b, nullptr),
          nullptr);
    } else if (a->induction_class == kLinear && b->induction_class == kLinear) {
      return NewInductionInfo(
          kLinear,
          kNop,
          NewInductionInfo(kInvariant, op, a->op_a, b->op_a, nullptr),
          NewInductionInfo(kInvariant, op, a->op_b, b->op_b, nullptr),
          nullptr);
    }
  }
  return nullptr;
}

HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a,
                                                                         InductionInfo* b) {
  // Transfer over a multiplication: invariant or linear
  // inputs combine into new invariant or linear result.
  // Two linear inputs would become quadratic.
  if (a != nullptr && b != nullptr) {
    if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
      return NewInductionInfo(kInvariant, kMul, a, b, nullptr);
    } else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
      return NewInductionInfo(
          kLinear,
          kNop,
          NewInductionInfo(kInvariant, kMul, a->op_a, b, nullptr),
          NewInductionInfo(kInvariant, kMul, a->op_b, b, nullptr),
          nullptr);
    } else if (a->induction_class == kInvariant && b->induction_class == kLinear) {
      return NewInductionInfo(
          kLinear,
          kNop,
          NewInductionInfo(kInvariant, kMul, a, b->op_a, nullptr),
          NewInductionInfo(kInvariant, kMul, a, b->op_b, nullptr),
          nullptr);
    }
  }
  return nullptr;
}

HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
  // Transfer over a unary negation: invariant or linear input
  // yields a similar, but negated result.
  if (a != nullptr) {
    if (a->induction_class == kInvariant) {
      return NewInductionInfo(kInvariant, kNeg, nullptr, a, nullptr);
    } else if (a->induction_class == kLinear) {
      return NewInductionInfo(
          kLinear,
          kNop,
          NewInductionInfo(kInvariant, kNeg, nullptr, a->op_a, nullptr),
          NewInductionInfo(kInvariant, kNeg, nullptr, a->op_b, nullptr),
          nullptr);
    }
  }
  return nullptr;
}

HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCycleOverPhi(HInstruction* phi) {
  // Transfer within a cycle over a phi: only identical inputs
  // can be combined into that input as result.
  const size_t count = phi->InputCount();
  CHECK_GT(count, 0u);
  auto ita = cycle_.find(phi->InputAt(0)->GetId());
  if (ita != cycle_.end()) {
    InductionInfo* a = ita->second;
    for (size_t i = 1; i < count; i++) {
      auto itb = cycle_.find(phi->InputAt(i)->GetId());
      if (itb == cycle_.end() ||!HInductionVarAnalysis::InductionEqual(a, itb->second)) {
        return nullptr;
      }
    }
    return a;
  }
  return nullptr;
}

HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCycleOverAddSub(
    HLoopInformation* loop,
    HInstruction* x,
    HInstruction* y,
    InductionOp op,
    bool first) {
  // Transfer within a cycle over an addition or subtraction: adding or
  // subtracting an invariant value adds to the stride of the induction,
  // starting with the phi value denoted by the unusual nullptr value.
  auto it = cycle_.find(x->GetId());
  if (it != cycle_.end()) {
    InductionInfo* a = it->second;
    InductionInfo* b = LookupInfo(loop, y);
    if (b != nullptr && b->induction_class == kInvariant) {
      if (a == nullptr) {
        if (op == kSub) {  // negation required
          return NewInductionInfo(kInvariant, kNeg, nullptr, b, nullptr);
        }
        return b;
      } else if (a->induction_class == kInvariant) {
        return NewInductionInfo(kInvariant, op, a, b, nullptr);
      }
    }
  }
  // On failure, try alternatives.
  if (op == kAdd) {
    // Try the other way around for an addition.
    if (first) {
      return TransferCycleOverAddSub(loop, y, x, op, false);
    }
  }
  return nullptr;
}

void HInductionVarAnalysis::PutInfo(int loop_id, int id, InductionInfo* info) {
  auto it = induction_.find(loop_id);
  if (it == induction_.end()) {
    it = induction_.Put(
        loop_id, ArenaSafeMap<int, InductionInfo*>(std::less<int>(), graph_->GetArena()->Adapter()));
  }
  it->second.Overwrite(id, info);
}

HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::GetInfo(int loop_id, int id) {
  auto it = induction_.find(loop_id);
  if (it != induction_.end()) {
    auto loop_it = it->second.find(id);
    if (loop_it != it->second.end()) {
      return loop_it->second;
    }
  }
  return nullptr;
}

void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
                                       HInstruction* instruction,
                                       InductionInfo* info) {
  const int loopId = loop->GetHeader()->GetBlockId();
  const int id = instruction->GetId();
  PutInfo(loopId, id, info);
}

HInductionVarAnalysis::InductionInfo*
HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
                                  HInstruction* instruction) {
  const int loop_id = loop->GetHeader()->GetBlockId();
  const int id = instruction->GetId();
  InductionInfo* info = GetInfo(loop_id, id);
  if (info == nullptr && IsLoopInvariant(loop, instruction)) {
    info = NewInductionInfo(kInvariant, kFetch, nullptr, nullptr, instruction);
    PutInfo(loop_id, id, info);
  }
  return info;
}

bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
                                           InductionInfo* info2) {
  // Test structural equality only, without accounting for simplifications.
  if (info1 != nullptr && info2 != nullptr) {
    return
        info1->induction_class == info2->induction_class &&
        info1->operation       == info2->operation       &&
        info1->fetch           == info2->fetch           &&
        InductionEqual(info1->op_a, info2->op_a)         &&
        InductionEqual(info1->op_b, info2->op_b);
  }
  // Otherwise only two nullptrs are considered equal.
  return info1 == info2;
}

std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
  if (info != nullptr) {
    if (info->induction_class == kInvariant) {
      std::string inv = "(";
      inv += InductionToString(info->op_a);
      switch (info->operation) {
        case kNop: inv += " ? "; break;
        case kAdd: inv += " + "; break;
        case kSub:
        case kNeg: inv += " - "; break;
        case kMul: inv += " * "; break;
        case kDiv: inv += " / "; break;
        case kFetch:
          CHECK(info->fetch != nullptr);
          inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
          break;
      }
      inv += InductionToString(info->op_b);
      return inv + ")";
    } else {
      CHECK(info->operation == kNop);
      if (info->induction_class == kLinear) {
        return "(" + InductionToString(info->op_a) + " * i + " +
                     InductionToString(info->op_b) + ")";
      } else if (info->induction_class == kWrapAround) {
        return "wrap(" + InductionToString(info->op_a) + ", " +
                         InductionToString(info->op_b) + ")";
      } else if (info->induction_class == kPeriodic) {
        return "periodic(" + InductionToString(info->op_a) + ", " +
                             InductionToString(info->op_b) + ")";
      }
    }
  }
  return "";
}

}  // namespace art