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 "linear_order.h"

namespace art {

// Remove the instruction from the graph. A bit more elaborate than the usual
// instruction removal, since there may be a cycle in the use structure.
static void RemoveFromCycle(HInstruction* instruction) {
  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),
      iset_(nullptr),
      induction_simplication_count_(0) {
}

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

  // Phase-local allocator that draws from the global pool. Since the allocator
  // itself resides on the stack, it is destructed on exiting Run(), which
  // implies its underlying memory is released immediately.
  ArenaAllocator allocator(graph_->GetArena()->GetArenaPool());
  loop_allocator_ = &allocator;

  // Perform loop optimizations.
  LocalRun();

  // Detach.
  loop_allocator_ = nullptr;
  last_loop_ = top_loop_ = nullptr;
}

void HLoopOptimization::LocalRun() {
  // Build the linear order using the phase-local allocator. This step enables building
  // a loop hierarchy that properly reflects the outer-inner and previous-next relation.
  ArenaVector<HBasicBlock*> linear_order(loop_allocator_->Adapter(kArenaAllocLinearOrder));
  LinearizeGraph(graph_, loop_allocator_, &linear_order);

  // Build the loop hierarchy.
  for (HBasicBlock* block : linear_order) {
    if (block->IsLoopHeader()) {
      AddLoop(block->GetLoopInformation());
    }
  }

  // Traverse the loop hierarchy inner-to-outer and optimize. Traversal can use
  // a temporary set that stores instructions using the phase-local allocator.
  if (top_loop_ != nullptr) {
    ArenaSet<HInstruction*> iset(loop_allocator_->Adapter(kArenaAllocLoopOptimization));
    iset_ = &iset;
    TraverseLoopsInnerToOuter(top_loop_);
    iset_ = nullptr;  // detach
  }
}

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);
  DCHECK(node->inner == nullptr);
  if (node->previous != nullptr) {
    // Within sequence.
    node->previous->next = node->next;
    if (node->next != nullptr) {
      node->next->previous = node->previous;
    }
  } else {
    // First of sequence.
    if (node->outer != nullptr) {
      node->outer->inner = node->next;
    } else {
      top_loop_ = node->next;
    }
    if (node->next != nullptr) {
      node->next->outer = node->outer;
      node->next->previous = nullptr;
    }
  }
}

void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) {
  for ( ; node != nullptr; node = node->next) {
    int current_induction_simplification_count = induction_simplication_count_;
    if (node->inner != nullptr) {
      TraverseLoopsInnerToOuter(node->inner);
    }
    // Visit loop after its inner loops have been visited. If the induction of any inner
    // loop has been simplified, recompute the induction information of this loop first.
    if (current_induction_simplification_count != induction_simplication_count_) {
      induction_range_.ReVisit(node->loop_info);
    }
    SimplifyBlocks(node);
    SimplifyInduction(node);
    SimplifyBlocks(node);
    if (node->inner == nullptr) {
      RemoveIfEmptyInnerLoop(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 simplify an induction
  // cycle that is only used outside the loop. Replace these uses, if any, with
  // the last value and remove the induction cycle.
  // Examples: for (int i = 0; x != null;   i++) { .... no i .... }
  //           for (int i = 0; i < 10; i++, k++) { .... no k .... } return k;
  for (HInstructionIterator it(header->GetPhis()); !it.Done(); it.Advance()) {
    HPhi* phi = it.Current()->AsPhi();
    iset_->clear();
    int32_t use_count = 0;
    if (IsPhiInduction(phi) &&
        IsOnlyUsedAfterLoop(node->loop_info, phi, &use_count) &&
        TryReplaceWithLastValue(phi, use_count, preheader)) {
      for (HInstruction* i : *iset_) {
        RemoveFromCycle(i);
      }
      induction_simplication_count_++;
    }
  }
}

void HLoopOptimization::SimplifyBlocks(LoopNode* node) {
  for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
    HBasicBlock* block = it.Current();
    // Remove instructions that are dead.
    for (HBackwardInstructionIterator i(block->GetInstructions()); !i.Done(); i.Advance()) {
      HInstruction* instruction = i.Current();
      if (instruction->IsDeadAndRemovable()) {
        block->RemoveInstruction(instruction);
      }
    }
    // Remove trivial control flow blocks from the loop-body.
    if (block->GetPredecessors().size() == 1 &&
        block->GetSuccessors().size() == 1 &&
        block->GetFirstInstruction()->IsGoto()) {
      HBasicBlock* pred = block->GetSinglePredecessor();
      HBasicBlock* succ = block->GetSingleSuccessor();
      if (succ->GetPredecessors().size() == 1) {
        pred->ReplaceSuccessor(block, succ);
        block->ClearDominanceInformation();
        block->SetDominator(pred);  // needed by next disconnect.
        block->DisconnectAndDelete();
        pred->AddDominatedBlock(succ);
        succ->SetDominator(pred);
      }
    }
  }
}

void HLoopOptimization::RemoveIfEmptyInnerLoop(LoopNode* node) {
  HBasicBlock* header = node->loop_info->GetHeader();
  HBasicBlock* preheader = node->loop_info->GetPreHeader();
  // Ensure loop header logic is finite.
  if (!induction_range_.IsFinite(node->loop_info)) {
    return;
  }
  // 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.
  if (exit->GetPredecessors().size() != 1) {
    return;
  }
  // Detect an empty loop: no side effects other than plain iteration. Replace
  // subsequent index uses, if any, with the last value and remove the loop.
  iset_->clear();
  int32_t use_count = 0;
  if (IsEmptyHeader(header) &&
      IsEmptyBody(body) &&
      IsOnlyUsedAfterLoop(node->loop_info, header->GetFirstPhi(), &use_count) &&
      TryReplaceWithLastValue(header->GetFirstPhi(), use_count, preheader)) {
    body->DisconnectAndDelete();
    exit->RemovePredecessor(header);
    header->RemoveSuccessor(exit);
    header->ClearDominanceInformation();
    header->SetDominator(preheader);  // needed by next disconnect.
    header->DisconnectAndDelete();
    preheader->AddSuccessor(exit);
    preheader->AddInstruction(new (graph_->GetArena()) HGoto());  // global allocator
    preheader->AddDominatedBlock(exit);
    exit->SetDominator(preheader);
    // Update hierarchy.
    RemoveLoop(node);
  }
}

bool HLoopOptimization::IsPhiInduction(HPhi* phi) {
  ArenaSet<HInstruction*>* set = induction_range_.LookupCycle(phi);
  if (set != nullptr) {
    for (HInstruction* i : *set) {
      // Check that, other than phi, instruction are removable with uses contained in the cycle.
      // TODO: investigate what cases are no longer in the graph.
      if (i != phi) {
        if (!i->IsInBlock() || !i->IsRemovable()) {
          return false;
        }
        for (const HUseListNode<HInstruction*>& use : i->GetUses()) {
          if (set->find(use.GetUser()) == set->end()) {
            return false;
          }
        }
      }
    }
    DCHECK(iset_->empty());
    iset_->insert(set->begin(), set->end());  // copy
    return true;
  }
  return false;
}

// Find: phi: Phi(init, addsub)
//       s:   SuspendCheck
//       c:   Condition(phi, bound)
//       i:   If(c)
// TODO: Find a less pattern matching approach?
bool HLoopOptimization::IsEmptyHeader(HBasicBlock* block) {
  DCHECK(iset_->empty());
  HInstruction* phi = block->GetFirstPhi();
  if (phi != nullptr && phi->GetNext() == nullptr && IsPhiInduction(phi->AsPhi())) {
    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) {
          iset_->insert(c);
          iset_->insert(s);
          return true;
        }
      }
    }
  }
  return false;
}

bool HLoopOptimization::IsEmptyBody(HBasicBlock* block) {
  if (block->GetFirstPhi() == nullptr) {
    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
      HInstruction* instruction = it.Current();
      if (!instruction->IsGoto() && iset_->find(instruction) == iset_->end()) {
        return false;
      }
    }
    return true;
  }
  return false;
}

bool HLoopOptimization::IsOnlyUsedAfterLoop(HLoopInformation* loop_info,
                                            HInstruction* instruction,
                                            /*out*/ int32_t* use_count) {
  for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
    HInstruction* user = use.GetUser();
    if (iset_->find(user) == iset_->end()) {  // not excluded?
      HLoopInformation* other_loop_info = user->GetBlock()->GetLoopInformation();
      if (other_loop_info != nullptr && other_loop_info->IsIn(*loop_info)) {
        return false;
      }
      ++*use_count;
    }
  }
  return true;
}

void HLoopOptimization::ReplaceAllUses(HInstruction* instruction, HInstruction* replacement) {
  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 (iset_->find(user) == iset_->end()) {  // not excluded?
      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 (iset_->find(user->GetHolder()) == iset_->end()) {  // not excluded?
      user->RemoveAsUserOfInput(index);
      user->SetRawEnvAt(index, replacement);
      replacement->AddEnvUseAt(user, index);
    }
  }
}

bool HLoopOptimization::TryReplaceWithLastValue(HInstruction* instruction,
                                                int32_t use_count,
                                                HBasicBlock* block) {
  // If true uses appear after the loop, replace these uses with the last value. Environment
  // uses can consume this value too, since any first true use is outside the loop (although
  // this may imply that de-opting may look "ahead" a bit on the phi value). If there are only
  // environment uses, the value is dropped altogether, since the computations have no effect.
  if (use_count > 0) {
    if (!induction_range_.CanGenerateLastValue(instruction)) {
      return false;
    }
    ReplaceAllUses(instruction, induction_range_.GenerateLastValue(instruction, graph_, block));
  }
  return true;
}

}  // namespace art