compiler/optimizing/block_builder.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 "block_builder.h"

#include "base/logging.h"  // FOR VLOG.
#include "dex/bytecode_utils.h"
#include "dex/code_item_accessors-inl.h"
#include "dex/dex_file_exception_helpers.h"
#include "quicken_info.h"

namespace art {

HBasicBlockBuilder::HBasicBlockBuilder(HGraph* graph,
                                       const DexFile* const dex_file,
                                       const CodeItemDebugInfoAccessor& accessor,
                                       ScopedArenaAllocator* local_allocator)
    : allocator_(graph->GetAllocator()),
      graph_(graph),
      dex_file_(dex_file),
      code_item_accessor_(accessor),
      local_allocator_(local_allocator),
      branch_targets_(code_item_accessor_.HasCodeItem()
                          ? code_item_accessor_.InsnsSizeInCodeUnits()
                          : /* fake dex_pc=0 for intrinsic graph */ 1u,
                      nullptr,
                      local_allocator->Adapter(kArenaAllocGraphBuilder)),
      throwing_blocks_(kDefaultNumberOfThrowingBlocks,
                       local_allocator->Adapter(kArenaAllocGraphBuilder)),
      number_of_branches_(0u),
      quicken_index_for_dex_pc_(std::less<uint32_t>(),
                                local_allocator->Adapter(kArenaAllocGraphBuilder)) {}

HBasicBlock* HBasicBlockBuilder::MaybeCreateBlockAt(uint32_t dex_pc) {
  return MaybeCreateBlockAt(dex_pc, dex_pc);
}

HBasicBlock* HBasicBlockBuilder::MaybeCreateBlockAt(uint32_t semantic_dex_pc,
                                                    uint32_t store_dex_pc) {
  HBasicBlock* block = branch_targets_[store_dex_pc];
  if (block == nullptr) {
    block = new (allocator_) HBasicBlock(graph_, semantic_dex_pc);
    branch_targets_[store_dex_pc] = block;
  }
  DCHECK_EQ(block->GetDexPc(), semantic_dex_pc);
  return block;
}

bool HBasicBlockBuilder::CreateBranchTargets() {
  // Create the first block for the dex instructions, single successor of the entry block.
  MaybeCreateBlockAt(0u);

  if (code_item_accessor_.TriesSize() != 0) {
    // Create branch targets at the start/end of the TryItem range. These are
    // places where the program might fall through into/out of the a block and
    // where TryBoundary instructions will be inserted later. Other edges which
    // enter/exit the try blocks are a result of branches/switches.
    for (const dex::TryItem& try_item : code_item_accessor_.TryItems()) {
      uint32_t dex_pc_start = try_item.start_addr_;
      uint32_t dex_pc_end = dex_pc_start + try_item.insn_count_;
      MaybeCreateBlockAt(dex_pc_start);
      if (dex_pc_end < code_item_accessor_.InsnsSizeInCodeUnits()) {
        // TODO: Do not create block if the last instruction cannot fall through.
        MaybeCreateBlockAt(dex_pc_end);
      } else if (dex_pc_end == code_item_accessor_.InsnsSizeInCodeUnits()) {
        // The TryItem spans until the very end of the CodeItem and therefore
        // cannot have any code afterwards.
      } else {
        // The TryItem spans beyond the end of the CodeItem. This is invalid code.
        VLOG(compiler) << "Not compiled: TryItem spans beyond the end of the CodeItem";
        return false;
      }
    }

    // Create branch targets for exception handlers.
    const uint8_t* handlers_ptr = code_item_accessor_.GetCatchHandlerData();
    uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr);
    for (uint32_t idx = 0; idx < handlers_size; ++idx) {
      CatchHandlerIterator iterator(handlers_ptr);
      for (; iterator.HasNext(); iterator.Next()) {
        MaybeCreateBlockAt(iterator.GetHandlerAddress());
      }
      handlers_ptr = iterator.EndDataPointer();
    }
  }

  // Iterate over all instructions and find branching instructions. Create blocks for
  // the locations these instructions branch to.
  for (const DexInstructionPcPair& pair : code_item_accessor_) {
    const uint32_t dex_pc = pair.DexPc();
    const Instruction& instruction = pair.Inst();

    if (instruction.IsBranch()) {
      number_of_branches_++;
      MaybeCreateBlockAt(dex_pc + instruction.GetTargetOffset());
    } else if (instruction.IsSwitch()) {
      number_of_branches_++;  // count as at least one branch (b/77652521)
      DexSwitchTable table(instruction, dex_pc);
      for (DexSwitchTableIterator s_it(table); !s_it.Done(); s_it.Advance()) {
        MaybeCreateBlockAt(dex_pc + s_it.CurrentTargetOffset());

        // Create N-1 blocks where we will insert comparisons of the input value
        // against the Switch's case keys.
        if (table.ShouldBuildDecisionTree() && !s_it.IsLast()) {
          // Store the block under dex_pc of the current key at the switch data
          // instruction for uniqueness but give it the dex_pc of the SWITCH
          // instruction which it semantically belongs to.
          MaybeCreateBlockAt(dex_pc, s_it.GetDexPcForCurrentIndex());
        }
      }
    } else if (instruction.Opcode() == Instruction::MOVE_EXCEPTION) {
      // End the basic block after MOVE_EXCEPTION. This simplifies the later
      // stage of TryBoundary-block insertion.
    } else {
      continue;
    }

    if (instruction.CanFlowThrough()) {
      DexInstructionIterator next(std::next(DexInstructionIterator(pair)));
      if (next == code_item_accessor_.end()) {
        // In the normal case we should never hit this but someone can artificially forge a dex
        // file to fall-through out the method code. In this case we bail out compilation.
        VLOG(compiler) << "Not compiled: Fall-through beyond the CodeItem";
        return false;
      }
      MaybeCreateBlockAt(next.DexPc());
    }
  }

  return true;
}

void HBasicBlockBuilder::ConnectBasicBlocks() {
  HBasicBlock* block = graph_->GetEntryBlock();
  graph_->AddBlock(block);

  size_t quicken_index = 0;
  bool is_throwing_block = false;
  // Calculate the qucikening index here instead of CreateBranchTargets since it's easier to
  // calculate in dex_pc order.
  for (const DexInstructionPcPair& pair : code_item_accessor_) {
    const uint32_t dex_pc = pair.DexPc();
    const Instruction& instruction = pair.Inst();

    // Check if this dex_pc address starts a new basic block.
    HBasicBlock* next_block = GetBlockAt(dex_pc);
    if (next_block != nullptr) {
      // We only need quicken index entries for basic block boundaries.
      quicken_index_for_dex_pc_.Put(dex_pc, quicken_index);
      if (block != nullptr) {
        // Last instruction did not end its basic block but a new one starts here.
        // It must have been a block falling through into the next one.
        block->AddSuccessor(next_block);
      }
      block = next_block;
      is_throwing_block = false;
      graph_->AddBlock(block);
    }
    // Make sure to increment this before the continues.
    if (QuickenInfoTable::NeedsIndexForInstruction(&instruction)) {
      ++quicken_index;
    }

    if (block == nullptr) {
      // Ignore dead code.
      continue;
    }

    if (!is_throwing_block && IsThrowingDexInstruction(instruction)) {
      DCHECK(!ContainsElement(throwing_blocks_, block));
      is_throwing_block = true;
      throwing_blocks_.push_back(block);
    }

    if (instruction.IsBranch()) {
      uint32_t target_dex_pc = dex_pc + instruction.GetTargetOffset();
      block->AddSuccessor(GetBlockAt(target_dex_pc));
    } else if (instruction.IsReturn() || (instruction.Opcode() == Instruction::THROW)) {
      block->AddSuccessor(graph_->GetExitBlock());
    } else if (instruction.IsSwitch()) {
      DexSwitchTable table(instruction, dex_pc);
      for (DexSwitchTableIterator s_it(table); !s_it.Done(); s_it.Advance()) {
        uint32_t target_dex_pc = dex_pc + s_it.CurrentTargetOffset();
        block->AddSuccessor(GetBlockAt(target_dex_pc));

        if (table.ShouldBuildDecisionTree() && !s_it.IsLast()) {
          uint32_t next_case_dex_pc = s_it.GetDexPcForCurrentIndex();
          HBasicBlock* next_case_block = GetBlockAt(next_case_dex_pc);
          block->AddSuccessor(next_case_block);
          block = next_case_block;
          graph_->AddBlock(block);
        }
      }
    } else {
      // Remaining code only applies to instructions which end their basic block.
      continue;
    }

    // Go to the next instruction in case we read dex PC below.
    if (instruction.CanFlowThrough()) {
      block->AddSuccessor(GetBlockAt(std::next(DexInstructionIterator(pair)).DexPc()));
    }

    // The basic block ends here. Do not add any more instructions.
    block = nullptr;
  }

  graph_->AddBlock(graph_->GetExitBlock());
}

// Returns the TryItem stored for `block` or nullptr if there is no info for it.
static const dex::TryItem* GetTryItem(
    HBasicBlock* block,
    const ScopedArenaSafeMap<uint32_t, const dex::TryItem*>& try_block_info) {
  auto iterator = try_block_info.find(block->GetBlockId());
  return (iterator == try_block_info.end()) ? nullptr : iterator->second;
}

// Iterates over the exception handlers of `try_item`, finds the corresponding
// catch blocks and makes them successors of `try_boundary`. The order of
// successors matches the order in which runtime exception delivery searches
// for a handler.
static void LinkToCatchBlocks(HTryBoundary* try_boundary,
                              const CodeItemDataAccessor& accessor,
                              const dex::TryItem* try_item,
                              const ScopedArenaSafeMap<uint32_t, HBasicBlock*>& catch_blocks) {
  for (CatchHandlerIterator it(accessor.GetCatchHandlerData(try_item->handler_off_));
      it.HasNext();
      it.Next()) {
    try_boundary->AddExceptionHandler(catch_blocks.Get(it.GetHandlerAddress()));
  }
}

bool HBasicBlockBuilder::MightHaveLiveNormalPredecessors(HBasicBlock* catch_block) {
  if (kIsDebugBuild) {
    DCHECK_NE(catch_block->GetDexPc(), kNoDexPc) << "Should not be called on synthetic blocks";
    DCHECK(!graph_->GetEntryBlock()->GetSuccessors().empty())
        << "Basic blocks must have been created and connected";
    for (HBasicBlock* predecessor : catch_block->GetPredecessors()) {
      DCHECK(!predecessor->IsSingleTryBoundary())
          << "TryBoundary blocks must not have not been created yet";
    }
  }

  const Instruction& first = code_item_accessor_.InstructionAt(catch_block->GetDexPc());
  if (first.Opcode() == Instruction::MOVE_EXCEPTION) {
    // Verifier guarantees that if a catch block begins with MOVE_EXCEPTION then
    // it has no live normal predecessors.
    return false;
  } else if (catch_block->GetPredecessors().empty()) {
    // Normal control-flow edges have already been created. Since block's list of
    // predecessors is empty, it cannot have any live or dead normal predecessors.
    return false;
  }

  // The catch block has normal predecessors but we do not know which are live
  // and which will be removed during the initial DCE. Return `true` to signal
  // that it may have live normal predecessors.
  return true;
}

void HBasicBlockBuilder::InsertTryBoundaryBlocks() {
  if (code_item_accessor_.TriesSize() == 0) {
    return;
  }

  // Keep a map of all try blocks and their respective TryItems. We do not use
  // the block's pointer but rather its id to ensure deterministic iteration.
  ScopedArenaSafeMap<uint32_t, const dex::TryItem*> try_block_info(
      std::less<uint32_t>(), local_allocator_->Adapter(kArenaAllocGraphBuilder));

  // Obtain TryItem information for blocks with throwing instructions, and split
  // blocks which are both try & catch to simplify the graph.
  for (HBasicBlock* block : graph_->GetBlocks()) {
    if (block->GetDexPc() == kNoDexPc) {
      continue;
    }

    // Do not bother creating exceptional edges for try blocks which have no
    // throwing instructions. In that case we simply assume that the block is
    // not covered by a TryItem. This prevents us from creating a throw-catch
    // loop for synchronized blocks.
    if (ContainsElement(throwing_blocks_, block)) {
      // Try to find a TryItem covering the block.
      const dex::TryItem* try_item = code_item_accessor_.FindTryItem(block->GetDexPc());
      if (try_item != nullptr) {
        // Block throwing and in a TryItem. Store the try block information.
        try_block_info.Put(block->GetBlockId(), try_item);
      }
    }
  }

  // Map from a handler dex_pc to the corresponding catch block.
  ScopedArenaSafeMap<uint32_t, HBasicBlock*> catch_blocks(
      std::less<uint32_t>(), local_allocator_->Adapter(kArenaAllocGraphBuilder));

  // Iterate over catch blocks, create artifical landing pads if necessary to
  // simplify the CFG, and set metadata.
  const uint8_t* handlers_ptr = code_item_accessor_.GetCatchHandlerData();
  uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr);
  for (uint32_t idx = 0; idx < handlers_size; ++idx) {
    CatchHandlerIterator iterator(handlers_ptr);
    for (; iterator.HasNext(); iterator.Next()) {
      uint32_t address = iterator.GetHandlerAddress();
      auto existing = catch_blocks.find(address);
      if (existing != catch_blocks.end()) {
        // Catch block already processed.
        TryCatchInformation* info = existing->second->GetTryCatchInformation();
        if (iterator.GetHandlerTypeIndex() != info->GetCatchTypeIndex()) {
          // The handler is for multiple types. We could record all the types, but
          // doing class resolution here isn't ideal, and it's unclear whether wasting
          // the space in TryCatchInformation is worth it.
          info->SetInvalidTypeIndex();
        }
        continue;
      }

      // Check if we should create an artifical landing pad for the catch block.
      // We create one if the catch block is also a try block because we do not
      // have a strategy for inserting TryBoundaries on exceptional edges.
      // We also create one if the block might have normal predecessors so as to
      // simplify register allocation.
      HBasicBlock* catch_block = GetBlockAt(address);
      bool is_try_block = (try_block_info.find(catch_block->GetBlockId()) != try_block_info.end());
      if (is_try_block || MightHaveLiveNormalPredecessors(catch_block)) {
        HBasicBlock* new_catch_block = new (allocator_) HBasicBlock(graph_, address);
        new_catch_block->AddInstruction(new (allocator_) HGoto(address));
        new_catch_block->AddSuccessor(catch_block);
        graph_->AddBlock(new_catch_block);
        catch_block = new_catch_block;
      }

      catch_blocks.Put(address, catch_block);
      catch_block->SetTryCatchInformation(
          new (allocator_) TryCatchInformation(iterator.GetHandlerTypeIndex(), *dex_file_));
    }
    handlers_ptr = iterator.EndDataPointer();
  }

  // Do a pass over the try blocks and insert entering TryBoundaries where at
  // least one predecessor is not covered by the same TryItem as the try block.
  // We do not split each edge separately, but rather create one boundary block
  // that all predecessors are relinked to. This preserves loop headers (b/23895756).
  for (const auto& entry : try_block_info) {
    uint32_t block_id = entry.first;
    const dex::TryItem* try_item = entry.second;
    HBasicBlock* try_block = graph_->GetBlocks()[block_id];
    for (HBasicBlock* predecessor : try_block->GetPredecessors()) {
      if (GetTryItem(predecessor, try_block_info) != try_item) {
        // Found a predecessor not covered by the same TryItem. Insert entering
        // boundary block.
        HTryBoundary* try_entry = new (allocator_) HTryBoundary(
            HTryBoundary::BoundaryKind::kEntry, try_block->GetDexPc());
        try_block->CreateImmediateDominator()->AddInstruction(try_entry);
        LinkToCatchBlocks(try_entry, code_item_accessor_, try_item, catch_blocks);
        break;
      }
    }
  }

  // Do a second pass over the try blocks and insert exit TryBoundaries where
  // the successor is not in the same TryItem.
  for (const auto& entry : try_block_info) {
    uint32_t block_id = entry.first;
    const dex::TryItem* try_item = entry.second;
    HBasicBlock* try_block = graph_->GetBlocks()[block_id];
    // NOTE: Do not use iterators because SplitEdge would invalidate them.
    for (size_t i = 0, e = try_block->GetSuccessors().size(); i < e; ++i) {
      HBasicBlock* successor = try_block->GetSuccessors()[i];

      // If the successor is a try block, all of its predecessors must be
      // covered by the same TryItem. Otherwise the previous pass would have
      // created a non-throwing boundary block.
      if (GetTryItem(successor, try_block_info) != nullptr) {
        DCHECK_EQ(try_item, GetTryItem(successor, try_block_info));
        continue;
      }

      // Insert TryBoundary and link to catch blocks.
      HTryBoundary* try_exit =
          new (allocator_) HTryBoundary(HTryBoundary::BoundaryKind::kExit, successor->GetDexPc());
      graph_->SplitEdge(try_block, successor)->AddInstruction(try_exit);
      LinkToCatchBlocks(try_exit, code_item_accessor_, try_item, catch_blocks);
    }
  }
}

void HBasicBlockBuilder::InsertSynthesizedLoopsForOsr() {
  ArenaSet<uint32_t> targets(allocator_->Adapter(kArenaAllocGraphBuilder));
  // Collect basic blocks that are targets of a negative branch.
  for (const DexInstructionPcPair& pair : code_item_accessor_) {
    const uint32_t dex_pc = pair.DexPc();
    const Instruction& instruction = pair.Inst();
    if (instruction.IsBranch()) {
      uint32_t target_dex_pc = dex_pc + instruction.GetTargetOffset();
      if (target_dex_pc < dex_pc) {
        HBasicBlock* block = GetBlockAt(target_dex_pc);
        CHECK_NE(kNoDexPc, block->GetDexPc());
        targets.insert(block->GetBlockId());
      }
    } else if (instruction.IsSwitch()) {
      DexSwitchTable table(instruction, dex_pc);
      for (DexSwitchTableIterator s_it(table); !s_it.Done(); s_it.Advance()) {
        uint32_t target_dex_pc = dex_pc + s_it.CurrentTargetOffset();
        if (target_dex_pc < dex_pc) {
          HBasicBlock* block = GetBlockAt(target_dex_pc);
          CHECK_NE(kNoDexPc, block->GetDexPc());
          targets.insert(block->GetBlockId());
        }
      }
    }
  }

  // Insert synthesized loops before the collected blocks.
  for (uint32_t block_id : targets) {
    HBasicBlock* block = graph_->GetBlocks()[block_id];
    HBasicBlock* loop_block = new (allocator_) HBasicBlock(graph_, block->GetDexPc());
    graph_->AddBlock(loop_block);
    while (!block->GetPredecessors().empty()) {
      block->GetPredecessors()[0]->ReplaceSuccessor(block, loop_block);
    }
    loop_block->AddSuccessor(loop_block);
    loop_block->AddSuccessor(block);
    // We loop on false - we know this won't be optimized later on as the loop
    // is marked irreducible, which disables loop optimizations.
    loop_block->AddInstruction(new (allocator_) HIf(graph_->GetIntConstant(0), kNoDexPc));
  }
}

bool HBasicBlockBuilder::Build() {
  DCHECK(code_item_accessor_.HasCodeItem());
  DCHECK(graph_->GetBlocks().empty());

  graph_->SetEntryBlock(new (allocator_) HBasicBlock(graph_, kNoDexPc));
  graph_->SetExitBlock(new (allocator_) HBasicBlock(graph_, kNoDexPc));

  // TODO(dbrazdil): Do CreateBranchTargets and ConnectBasicBlocks in one pass.
  if (!CreateBranchTargets()) {
    return false;
  }

  ConnectBasicBlocks();
  InsertTryBoundaryBlocks();

  if (graph_->IsCompilingOsr()) {
    InsertSynthesizedLoopsForOsr();
  }

  return true;
}

void HBasicBlockBuilder::BuildIntrinsic() {
  DCHECK(!code_item_accessor_.HasCodeItem());
  DCHECK(graph_->GetBlocks().empty());

  // Create blocks.
  HBasicBlock* entry_block = new (allocator_) HBasicBlock(graph_, kNoDexPc);
  HBasicBlock* exit_block = new (allocator_) HBasicBlock(graph_, kNoDexPc);
  HBasicBlock* body = MaybeCreateBlockAt(/* semantic_dex_pc= */ kNoDexPc, /* store_dex_pc= */ 0u);

  // Add blocks to the graph.
  graph_->AddBlock(entry_block);
  graph_->AddBlock(body);
  graph_->AddBlock(exit_block);
  graph_->SetEntryBlock(entry_block);
  graph_->SetExitBlock(exit_block);

  // Connect blocks.
  entry_block->AddSuccessor(body);
  body->AddSuccessor(exit_block);
}

size_t HBasicBlockBuilder::GetQuickenIndex(uint32_t dex_pc) const {
  return quicken_index_for_dex_pc_.Get(dex_pc);
}

}  // namespace art