compiler/dex/global_value_numbering.cc

/*
 * 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.
 */

#include "global_value_numbering.h"

#include "base/bit_vector-inl.h"
#include "base/stl_util.h"
#include "local_value_numbering.h"

namespace art {

GlobalValueNumbering::GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator,
                                           Mode mode)
    : cu_(cu),
      mir_graph_(cu->mir_graph.get()),
      allocator_(allocator),
      bbs_processed_(0u),
      max_bbs_to_process_(kMaxBbsToProcessMultiplyFactor * mir_graph_->GetNumReachableBlocks()),
      last_value_(kNullValue),
      modifications_allowed_(true),
      mode_(mode),
      global_value_map_(std::less<uint64_t>(), allocator->Adapter()),
      array_location_map_(ArrayLocationComparator(), allocator->Adapter()),
      array_location_reverse_map_(allocator->Adapter()),
      ref_set_map_(std::less<ValueNameSet>(), allocator->Adapter()),
      lvns_(mir_graph_->GetNumBlocks(), nullptr, allocator->Adapter()),
      work_lvn_(nullptr),
      merge_lvns_(allocator->Adapter()) {
}

GlobalValueNumbering::~GlobalValueNumbering() {
  STLDeleteElements(&lvns_);
}

LocalValueNumbering* GlobalValueNumbering::PrepareBasicBlock(BasicBlock* bb,
                                                             ScopedArenaAllocator* allocator) {
  if (UNLIKELY(!Good())) {
    return nullptr;
  }
  if (bb->block_type != kDalvikByteCode && bb->block_type != kEntryBlock) {
    DCHECK(bb->first_mir_insn == nullptr);
    return nullptr;
  }
  if (mode_ == kModeGvn && UNLIKELY(bbs_processed_ == max_bbs_to_process_)) {
    // If we're still trying to converge, stop now. Otherwise, proceed to apply optimizations.
    last_value_ = kNoValue;  // Make bad.
    return nullptr;
  }
  if (mode_ == kModeGvnPostProcessing &&
    mir_graph_->GetTopologicalSortOrderLoopHeadStack()->empty()) {
    // Modifications outside loops are performed during the main phase.
    return nullptr;
  }
  if (allocator == nullptr) {
    allocator = allocator_;
  }
  DCHECK(work_lvn_.get() == nullptr);
  work_lvn_.reset(new (allocator) LocalValueNumbering(this, bb->id, allocator));
  if (bb->block_type == kEntryBlock) {
    work_lvn_->PrepareEntryBlock();
    DCHECK(bb->first_mir_insn == nullptr);  // modifications_allowed_ is irrelevant.
  } else {
    // To avoid repeated allocation on the ArenaStack, reuse a single vector kept as a member.
    DCHECK(merge_lvns_.empty());
    // If we're running the full GVN, the RepeatingTopologicalSortIterator keeps the loop
    // head stack in the MIRGraph up to date and for a loop head we need to check whether
    // we're making the initial computation and need to merge only preceding blocks in the
    // topological order, or we're recalculating a loop head and need to merge all incoming
    // LVNs. When we're not at a loop head (including having an empty loop head stack) all
    // predecessors should be preceding blocks and we shall merge all of them anyway.
    bool use_all_predecessors = true;
    uint16_t loop_head_idx = 0u;  // Used only if !use_all_predecessors.
    if (mode_ == kModeGvn && mir_graph_->GetTopologicalSortOrderLoopHeadStack()->size() != 0) {
      // Full GVN inside a loop, see if we're at the loop head for the first time.
      modifications_allowed_ = false;
      auto top = mir_graph_->GetTopologicalSortOrderLoopHeadStack()->back();
      loop_head_idx = top.first;
      bool recalculating = top.second;
      use_all_predecessors = recalculating ||
          loop_head_idx != mir_graph_->GetTopologicalSortOrderIndexes()[bb->id];
    } else {
      modifications_allowed_ = true;
    }
    for (BasicBlockId pred_id : bb->predecessors) {
      DCHECK_NE(pred_id, NullBasicBlockId);
      if (lvns_[pred_id] != nullptr &&
          (use_all_predecessors ||
              mir_graph_->GetTopologicalSortOrderIndexes()[pred_id] < loop_head_idx)) {
        merge_lvns_.push_back(lvns_[pred_id]);
      }
    }
    // Determine merge type.
    LocalValueNumbering::MergeType merge_type = LocalValueNumbering::kNormalMerge;
    if (bb->catch_entry) {
      merge_type = LocalValueNumbering::kCatchMerge;
    } else if (bb->last_mir_insn != nullptr &&
        IsInstructionReturn(bb->last_mir_insn->dalvikInsn.opcode) &&
        bb->GetFirstNonPhiInsn() == bb->last_mir_insn) {
      merge_type = LocalValueNumbering::kReturnMerge;
    }
    // At least one predecessor must have been processed before this bb.
    CHECK(!merge_lvns_.empty());
    if (merge_lvns_.size() == 1u) {
      work_lvn_->MergeOne(*merge_lvns_[0], merge_type);
    } else {
      work_lvn_->Merge(merge_type);
    }
  }
  return work_lvn_.get();
}

bool GlobalValueNumbering::FinishBasicBlock(BasicBlock* bb) {
  DCHECK(work_lvn_ != nullptr);
  DCHECK_EQ(bb->id, work_lvn_->Id());
  ++bbs_processed_;
  merge_lvns_.clear();

  bool change = (lvns_[bb->id] == nullptr) || !lvns_[bb->id]->Equals(*work_lvn_);
  if (mode_ == kModeGvn) {
    // In GVN mode, keep the latest LVN even if Equals() indicates no change. This is
    // to keep the correct values of fields that do not contribute to Equals() as long
    // as they depend only on predecessor LVNs' fields that do contribute to Equals().
    // Currently, that's LVN::merge_map_ used by LVN::GetStartingVregValueNumberImpl().
    std::unique_ptr<const LocalValueNumbering> old_lvn(lvns_[bb->id]);
    lvns_[bb->id] = work_lvn_.release();
  } else {
    work_lvn_.reset();
  }
  return change;
}

uint16_t GlobalValueNumbering::GetArrayLocation(uint16_t base, uint16_t index) {
  auto cmp = array_location_map_.key_comp();
  ArrayLocation key = { base, index };
  auto lb = array_location_map_.lower_bound(key);
  if (lb != array_location_map_.end() && !cmp(key, lb->first)) {
    return lb->second;
  }
  uint16_t location = static_cast<uint16_t>(array_location_reverse_map_.size());
  DCHECK_EQ(location, array_location_reverse_map_.size());  // No overflow.
  auto it = array_location_map_.PutBefore(lb, key, location);
  array_location_reverse_map_.push_back(&*it);
  return location;
}

bool GlobalValueNumbering::HasNullCheckLastInsn(const BasicBlock* pred_bb,
                                                BasicBlockId succ_id) {
  if (pred_bb->block_type != kDalvikByteCode || pred_bb->last_mir_insn == nullptr) {
    return false;
  }
  Instruction::Code last_opcode = pred_bb->last_mir_insn->dalvikInsn.opcode;
  return ((last_opcode == Instruction::IF_EQZ && pred_bb->fall_through == succ_id) ||
      (last_opcode == Instruction::IF_NEZ && pred_bb->taken == succ_id));
}

bool GlobalValueNumbering::NullCheckedInAllPredecessors(
    const ScopedArenaVector<uint16_t>& merge_names) const {
  // Implicit parameters:
  //   - *work_lvn: the LVN for which we're checking predecessors.
  //   - merge_lvns_: the predecessor LVNs.
  DCHECK_EQ(merge_lvns_.size(), merge_names.size());
  for (size_t i = 0, size = merge_lvns_.size(); i != size; ++i) {
    const LocalValueNumbering* pred_lvn = merge_lvns_[i];
    uint16_t value_name = merge_names[i];
    if (!pred_lvn->IsValueNullChecked(value_name)) {
      // Check if the predecessor has an IF_EQZ/IF_NEZ as the last insn.
      const BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_lvn->Id());
      if (!HasNullCheckLastInsn(pred_bb, work_lvn_->Id())) {
        return false;
      }
      // IF_EQZ/IF_NEZ checks some sreg, see if that sreg contains the value_name.
      int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0];
      if (pred_lvn->GetSregValue(s_reg) != value_name) {
        return false;
      }
    }
  }
  return true;
}

bool GlobalValueNumbering::DivZeroCheckedInAllPredecessors(
    const ScopedArenaVector<uint16_t>& merge_names) const {
  // Implicit parameters:
  //   - *work_lvn: the LVN for which we're checking predecessors.
  //   - merge_lvns_: the predecessor LVNs.
  DCHECK_EQ(merge_lvns_.size(), merge_names.size());
  for (size_t i = 0, size = merge_lvns_.size(); i != size; ++i) {
    const LocalValueNumbering* pred_lvn = merge_lvns_[i];
    uint16_t value_name = merge_names[i];
    if (!pred_lvn->IsValueDivZeroChecked(value_name)) {
      return false;
    }
  }
  return true;
}

bool GlobalValueNumbering::IsBlockEnteredOnTrue(uint16_t cond, BasicBlockId bb_id) {
  DCHECK_NE(cond, kNoValue);
  BasicBlock* bb = mir_graph_->GetBasicBlock(bb_id);
  if (bb->predecessors.size() == 1u) {
    BasicBlockId pred_id = bb->predecessors[0];
    BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_id);
    if (pred_bb->last_mir_insn != nullptr) {
      Instruction::Code opcode = pred_bb->last_mir_insn->dalvikInsn.opcode;
      if ((opcode == Instruction::IF_NEZ && pred_bb->taken == bb_id) ||
          (opcode == Instruction::IF_EQZ && pred_bb->fall_through == bb_id)) {
        DCHECK(lvns_[pred_id] != nullptr);
        uint16_t operand = lvns_[pred_id]->GetSregValue(pred_bb->last_mir_insn->ssa_rep->uses[0]);
        if (operand == cond) {
          return true;
        }
      }
    }
  }
  return false;
}

bool GlobalValueNumbering::IsTrueInBlock(uint16_t cond, BasicBlockId bb_id) {
  // We're not doing proper value propagation, so just see if the condition is used
  // with if-nez/if-eqz to branch/fall-through to this bb or one of its dominators.
  DCHECK_NE(cond, kNoValue);
  if (IsBlockEnteredOnTrue(cond, bb_id)) {
    return true;
  }
  BasicBlock* bb = mir_graph_->GetBasicBlock(bb_id);
  for (uint32_t dom_id : bb->dominators->Indexes()) {
    if (IsBlockEnteredOnTrue(cond, dom_id)) {
      return true;
    }
  }
  return false;
}

}  // namespace art