path: root/compiler/optimizing/loop_optimization.cc

/*
 * Copyright (C) 2016 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 "loop_optimization.h"

#include "base/arena_containers.h"
#include "induction_var_range.h"
#include "ssa_liveness_analysis.h"
#include "nodes.h"

namespace art {

// TODO: Generalize to cycles, as found by induction analysis?
static bool IsPhiAddSub(HPhi* phi, /*out*/ HInstruction** addsub_out) {
  HInputsRef inputs = phi->GetInputs();
  if (inputs.size() == 2 && (inputs[1]->IsAdd() || inputs[1]->IsSub())) {
    HInstruction* addsub = inputs[1];
    if (addsub->InputAt(0) == phi || addsub->InputAt(1) == phi) {
      if (addsub->GetUses().HasExactlyOneElement()) {
        *addsub_out = addsub;
        return true;
      }
    }
  }
  return false;
}

static bool IsOnlyUsedAfterLoop(const HLoopInformation& loop_info,
                                HPhi* phi, HInstruction* addsub) {
  for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
    if (use.GetUser() != addsub) {
      HLoopInformation* other_loop_info = use.GetUser()->GetBlock()->GetLoopInformation();
      if (other_loop_info != nullptr && other_loop_info->IsIn(loop_info)) {
        return false;
      }
    }
  }
  return true;
}

// Find: phi: Phi(init, addsub)
//       s:   SuspendCheck
//       c:   Condition(phi, bound)
//       i:   If(c)
// TODO: Find a less pattern matching approach?
static bool IsEmptyHeader(HBasicBlock* block, /*out*/ HInstruction** addsub) {
  HInstruction* phi = block->GetFirstPhi();
  if (phi != nullptr && phi->GetNext() == nullptr && IsPhiAddSub(phi->AsPhi(), addsub)) {
    HInstruction* s = block->GetFirstInstruction();
    if (s != nullptr && s->IsSuspendCheck()) {
      HInstruction* c = s->GetNext();
      if (c != nullptr && c->IsCondition() && c->GetUses().HasExactlyOneElement()) {
        HInstruction* i = c->GetNext();
        if (i != nullptr && i->IsIf() && i->InputAt(0) == c) {
          // Check that phi is only used inside loop as expected.
          for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
            if (use.GetUser() != *addsub && use.GetUser() != c) {
              return false;
            }
          }
          return true;
        }
      }
    }
  }
  return false;
}

static bool IsEmptyBody(HBasicBlock* block, HInstruction* addsub) {
  HInstruction* phi = block->GetFirstPhi();
  HInstruction* i = block->GetFirstInstruction();
  return phi == nullptr && i == addsub && i->GetNext() != nullptr && i->GetNext()->IsGoto();
}

static HBasicBlock* TryRemovePreHeader(HBasicBlock* preheader, HBasicBlock* entry_block) {
  if (preheader->GetPredecessors().size() == 1) {
    HBasicBlock* entry = preheader->GetSinglePredecessor();
    HInstruction* anchor = entry->GetLastInstruction();
    // If the pre-header has a single predecessor we can remove it too if
    // either the pre-header just contains a goto, or if the predecessor
    // is not the entry block so we can push instructions backward
    // (moving computation into the entry block is too dangerous!).
    if (preheader->GetFirstInstruction() == nullptr ||
        preheader->GetFirstInstruction()->IsGoto() ||
        (entry != entry_block && anchor->IsGoto())) {
      // Push non-goto statements backward to empty the pre-header.
      for (HInstructionIterator it(preheader->GetInstructions()); !it.Done(); it.Advance()) {
        HInstruction* instruction = it.Current();
        if (!instruction->IsGoto()) {
          if (!instruction->CanBeMoved()) {
            return nullptr;  // pushing failed to move all
          }
          it.Current()->MoveBefore(anchor);
        }
      }
      return entry;
    }
  }
  return nullptr;
}

static void RemoveFromCycle(HInstruction* instruction) {
  // A bit more elaborate than the usual instruction removal,
  // since there may be a cycle in the use structure.
  instruction->RemoveAsUserOfAllInputs();
  instruction->RemoveEnvironmentUsers();
  instruction->GetBlock()->RemoveInstructionOrPhi(instruction, /*ensure_safety=*/ false);
}

//
// Class methods.
//

HLoopOptimization::HLoopOptimization(HGraph* graph,
                                     HInductionVarAnalysis* induction_analysis)
    : HOptimization(graph, kLoopOptimizationPassName),
      induction_range_(induction_analysis),
      loop_allocator_(nullptr),
      top_loop_(nullptr),
      last_loop_(nullptr) {
}

void HLoopOptimization::Run() {
  // Well-behaved loops only.
  // TODO: make this less of a sledgehammer.
  if (graph_-> HasTryCatch() || graph_->HasIrreducibleLoops()) {
    return;
  }

  ArenaAllocator allocator(graph_->GetArena()->GetArenaPool());
  loop_allocator_ = &allocator;

  // Build the linear order. This step enables building a loop hierarchy that
  // properly reflects the outer-inner and previous-next relation.
  graph_->Linearize();
  // Build the loop hierarchy.
  for (HLinearOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
    HBasicBlock* block = it_graph.Current();
    if (block->IsLoopHeader()) {
      AddLoop(block->GetLoopInformation());
    }
  }
  if (top_loop_ != nullptr) {
    // Traverse the loop hierarchy inner-to-outer and optimize.
    TraverseLoopsInnerToOuter(top_loop_);
  }
  loop_allocator_ = nullptr;
}

void HLoopOptimization::AddLoop(HLoopInformation* loop_info) {
  DCHECK(loop_info != nullptr);
  LoopNode* node = new (loop_allocator_) LoopNode(loop_info);  // phase-local allocator
  if (last_loop_ == nullptr) {
    // First loop.
    DCHECK(top_loop_ == nullptr);
    last_loop_ = top_loop_ = node;
  } else if (loop_info->IsIn(*last_loop_->loop_info)) {
    // Inner loop.
    node->outer = last_loop_;
    DCHECK(last_loop_->inner == nullptr);
    last_loop_ = last_loop_->inner = node;
  } else {
    // Subsequent loop.
    while (last_loop_->outer != nullptr && !loop_info->IsIn(*last_loop_->outer->loop_info)) {
      last_loop_ = last_loop_->outer;
    }
    node->outer = last_loop_->outer;
    node->previous = last_loop_;
    DCHECK(last_loop_->next == nullptr);
    last_loop_ = last_loop_->next = node;
  }
}

void HLoopOptimization::RemoveLoop(LoopNode* node) {
  DCHECK(node != nullptr);
  // TODO: implement when needed (for current set of optimizations, we don't
  // need to keep recorded loop hierarchy up to date, but as we get different
  // traversal, we may want to remove the node from the hierarchy here.
}

void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) {
  for ( ; node != nullptr; node = node->next) {
    if (node->inner != nullptr) {
      TraverseLoopsInnerToOuter(node->inner);
    }
    // Visit loop after its inner loops have been visited.
    SimplifyInduction(node);
    RemoveIfEmptyLoop(node);
  }
}

void HLoopOptimization::SimplifyInduction(LoopNode* node) {
  HBasicBlock* header = node->loop_info->GetHeader();
  HBasicBlock* preheader = node->loop_info->GetPreHeader();
  // Scan the phis in the header to find opportunities to optimize induction.
  for (HInstructionIterator it(header->GetPhis()); !it.Done(); it.Advance()) {
    HPhi* phi = it.Current()->AsPhi();
    HInstruction* addsub = nullptr;
    // Find phi-add/sub cycle.
    if (IsPhiAddSub(phi, &addsub)) {
      // Simple case, the induction is only used by itself. Although redundant,
      // later phases do not easily detect this property. Thus, eliminate here.
      // Example: for (int i = 0; x != null; i++) { .... no i .... }
      if (phi->GetUses().HasExactlyOneElement()) {
        // Remove the cycle, including all uses. Even environment uses can be removed,
        // since these computations have no effect at all.
        RemoveFromCycle(phi);  // removes environment uses too
        RemoveFromCycle(addsub);
        continue;
      }
      // Closed form case. Only the last value of the induction is needed. Remove all
      // overhead from the loop, and replace subsequent uses with the last value.
      // Example: for (int i = 0; i < 10; i++, k++) { .... no k .... } return k;
      if (IsOnlyUsedAfterLoop(*node->loop_info, phi, addsub) &&
          induction_range_.CanGenerateLastValue(phi)) {
        HInstruction* last = induction_range_.GenerateLastValue(phi, graph_, preheader);
        // Remove the cycle, replacing all uses. Even environment uses can consume the final
        // value, since any first real use is outside the loop (although this may imply
        // that deopting may look "ahead" a bit on the phi value).
        ReplaceAllUses(phi, last, addsub);
        RemoveFromCycle(phi);  // removes environment uses too
        RemoveFromCycle(addsub);
      }
    }
  }
}

void HLoopOptimization::RemoveIfEmptyLoop(LoopNode* node) {
  HBasicBlock* header = node->loop_info->GetHeader();
  HBasicBlock* preheader = node->loop_info->GetPreHeader();
  // Ensure there is only a single loop-body (besides the header).
  HBasicBlock* body = nullptr;
  for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
    if (it.Current() != header) {
      if (body != nullptr) {
        return;
      }
      body = it.Current();
    }
  }
  // Ensure there is only a single exit point.
  if (header->GetSuccessors().size() != 2) {
    return;
  }
  HBasicBlock* exit = (header->GetSuccessors()[0] == body)
      ? header->GetSuccessors()[1]
      : header->GetSuccessors()[0];
  // Ensure exit can only be reached by exiting loop (this seems typically the
  // case anyway, and simplifies code generation below; TODO: perhaps relax?).
  if (exit->GetPredecessors().size() != 1) {
    return;
  }
  // Detect an empty loop: no side effects other than plain iteration.
  HInstruction* addsub = nullptr;
  if (IsEmptyHeader(header, &addsub) && IsEmptyBody(body, addsub)) {
    HBasicBlock* entry = TryRemovePreHeader(preheader, graph_->GetEntryBlock());
    body->DisconnectAndDelete();
    exit->RemovePredecessor(header);
    header->RemoveSuccessor(exit);
    header->ClearDominanceInformation();
    header->SetDominator(preheader);  // needed by next disconnect.
    header->DisconnectAndDelete();
    // If allowed, remove preheader too, which may expose next outer empty loop
    // Otherwise, link preheader directly to exit to restore the flow graph.
    if (entry != nullptr) {
      entry->ReplaceSuccessor(preheader, exit);
      entry->AddDominatedBlock(exit);
      exit->SetDominator(entry);
      preheader->DisconnectAndDelete();
    } else {
      preheader->AddSuccessor(exit);
      preheader->AddInstruction(new (graph_->GetArena()) HGoto());  // global allocator
      preheader->AddDominatedBlock(exit);
      exit->SetDominator(preheader);
    }
    // Update hierarchy.
    RemoveLoop(node);
  }
}

void HLoopOptimization::ReplaceAllUses(HInstruction* instruction,
                                       HInstruction* replacement,
                                       HInstruction* exclusion) {
  const HUseList<HInstruction*>& uses = instruction->GetUses();
  for (auto it = uses.begin(), end = uses.end(); it != end;) {
    HInstruction* user = it->GetUser();
    size_t index = it->GetIndex();
    ++it;  // increment before replacing
    if (user != exclusion) {
      user->ReplaceInput(replacement, index);
      induction_range_.Replace(user, instruction, replacement);  // update induction
    }
  }
  const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses();
  for (auto it = env_uses.begin(), end = env_uses.end(); it != end;) {
    HEnvironment* user = it->GetUser();
    size_t index = it->GetIndex();
    ++it;  // increment before replacing
    if (user->GetHolder() != exclusion) {
      user->RemoveAsUserOfInput(index);
      user->SetRawEnvAt(index, replacement);
      replacement->AddEnvUseAt(user, index);
    }
  }
}

}  // namespace art