18 files changed, 1297 insertions, 1179 deletions

diff --git a/compiler/optimizing/block_builder.cc b/compiler/optimizing/block_builder.cc
new file mode 100644
index 0000000000..5e70a8284d
--- /dev/null
+++ b/compiler/optimizing/block_builder.cc
@@ -0,0 +1,370 @@
+/*
+ * 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 "bytecode_utils.h"
+
+namespace art {
+
+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 (arena_) 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_.tries_size_ != 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 (size_t idx = 0; idx < code_item_.tries_size_; ++idx) {
+      const DexFile::TryItem* try_item = DexFile::GetTryItems(code_item_, idx);
+      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_.insns_size_in_code_units_) {
+        // TODO: Do not create block if the last instruction cannot fall through.
+        MaybeCreateBlockAt(dex_pc_end);
+      } else if (dex_pc_end == code_item_.insns_size_in_code_units_) {
+        // 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.
+        return false;
+      }
+    }
+
+    // Create branch targets for exception handlers.
+    const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(code_item_, 0);
+    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 (CodeItemIterator it(code_item_); !it.Done(); it.Advance()) {
+    uint32_t dex_pc = it.CurrentDexPc();
+    const Instruction& instruction = it.CurrentInstruction();
+
+    if (instruction.IsBranch()) {
+      number_of_branches_++;
+      MaybeCreateBlockAt(dex_pc + instruction.GetTargetOffset());
+    } else if (instruction.IsSwitch()) {
+      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()) {
+      if (it.IsLast()) {
+        // 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.
+        return false;
+      } else {
+        MaybeCreateBlockAt(dex_pc + it.CurrentInstruction().SizeInCodeUnits());
+      }
+    }
+  }
+
+  return true;
+}
+
+void HBasicBlockBuilder::ConnectBasicBlocks() {
+  HBasicBlock* block = graph_->GetEntryBlock();
+  graph_->AddBlock(block);
+
+  bool is_throwing_block = false;
+  for (CodeItemIterator it(code_item_); !it.Done(); it.Advance()) {
+    uint32_t dex_pc = it.CurrentDexPc();
+
+    // Check if this dex_pc address starts a new basic block.
+    HBasicBlock* next_block = GetBlockAt(dex_pc);
+    if (next_block != nullptr) {
+      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);
+    }
+
+    if (block == nullptr) {
+      // Ignore dead code.
+      continue;
+    }
+
+    const Instruction& instruction = it.CurrentInstruction();
+
+    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;
+    }
+
+    if (instruction.CanFlowThrough()) {
+      uint32_t next_dex_pc = dex_pc + instruction.SizeInCodeUnits();
+      block->AddSuccessor(GetBlockAt(next_dex_pc));
+    }
+
+    // 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 DexFile::TryItem* GetTryItem(
+    HBasicBlock* block,
+    const ArenaSafeMap<uint32_t, const DexFile::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 DexFile::CodeItem& code_item,
+                              const DexFile::TryItem* try_item,
+                              const ArenaSafeMap<uint32_t, HBasicBlock*>& catch_blocks) {
+  for (CatchHandlerIterator it(code_item, *try_item); 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 = GetDexInstructionAt(code_item_, 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_.tries_size_ == 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.
+  ArenaSafeMap<uint32_t, const DexFile::TryItem*> try_block_info(
+      std::less<uint32_t>(), arena_->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 int32_t try_item_idx = DexFile::FindTryItem(code_item_, block->GetDexPc());
+      if (try_item_idx != -1) {
+        // Block throwing and in a TryItem. Store the try block information.
+        try_block_info.Put(block->GetBlockId(), DexFile::GetTryItems(code_item_, try_item_idx));
+      }
+    }
+  }
+
+  // Map from a handler dex_pc to the corresponding catch block.
+  ArenaSafeMap<uint32_t, HBasicBlock*> catch_blocks(
+      std::less<uint32_t>(), arena_->Adapter(kArenaAllocGraphBuilder));
+
+  // Iterate over catch blocks, create artifical landing pads if necessary to
+  // simplify the CFG, and set metadata.
+  const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(code_item_, 0);
+  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();
+      if (catch_blocks.find(address) != catch_blocks.end()) {
+        // Catch block already processed.
+        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 (arena_) HBasicBlock(graph_, address);
+        new_catch_block->AddInstruction(new (arena_) 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 (arena_) 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 (auto entry : try_block_info) {
+    HBasicBlock* try_block = graph_->GetBlocks()[entry.first];
+    for (HBasicBlock* predecessor : try_block->GetPredecessors()) {
+      if (GetTryItem(predecessor, try_block_info) != entry.second) {
+        // Found a predecessor not covered by the same TryItem. Insert entering
+        // boundary block.
+        HTryBoundary* try_entry =
+            new (arena_) HTryBoundary(HTryBoundary::BoundaryKind::kEntry, try_block->GetDexPc());
+        try_block->CreateImmediateDominator()->AddInstruction(try_entry);
+        LinkToCatchBlocks(try_entry, code_item_, entry.second, 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 (auto entry : try_block_info) {
+    HBasicBlock* try_block = graph_->GetBlocks()[entry.first];
+    // 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(entry.second, GetTryItem(successor, try_block_info));
+        continue;
+      }
+
+      // Insert TryBoundary and link to catch blocks.
+      HTryBoundary* try_exit =
+          new (arena_) HTryBoundary(HTryBoundary::BoundaryKind::kExit, successor->GetDexPc());
+      graph_->SplitEdge(try_block, successor)->AddInstruction(try_exit);
+      LinkToCatchBlocks(try_exit, code_item_, entry.second, catch_blocks);
+    }
+  }
+}
+
+bool HBasicBlockBuilder::Build() {
+  DCHECK(graph_->GetBlocks().empty());
+
+  graph_->SetEntryBlock(new (arena_) HBasicBlock(graph_, kNoDexPc));
+  graph_->SetExitBlock(new (arena_) HBasicBlock(graph_, kNoDexPc));
+
+  // TODO(dbrazdil): Do CreateBranchTargets and ConnectBasicBlocks in one pass.
+  if (!CreateBranchTargets()) {
+    return false;
+  }
+
+  ConnectBasicBlocks();
+  InsertTryBoundaryBlocks();
+
+  return true;
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/block_builder.h b/compiler/optimizing/block_builder.h
new file mode 100644
index 0000000000..1be0b4ce98
--- /dev/null
+++ b/compiler/optimizing/block_builder.h
@@ -0,0 +1,88 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_BLOCK_BUILDER_H_
+#define ART_COMPILER_OPTIMIZING_BLOCK_BUILDER_H_
+
+#include "base/arena_containers.h"
+#include "base/arena_object.h"
+#include "dex_file.h"
+#include "nodes.h"
+
+namespace art {
+
+class HBasicBlockBuilder : public ValueObject {
+ public:
+  HBasicBlockBuilder(HGraph* graph,
+                     const DexFile* const dex_file,
+                     const DexFile::CodeItem& code_item)
+      : arena_(graph->GetArena()),
+        graph_(graph),
+        dex_file_(dex_file),
+        code_item_(code_item),
+        branch_targets_(code_item.insns_size_in_code_units_,
+                        nullptr,
+                        arena_->Adapter(kArenaAllocGraphBuilder)),
+        throwing_blocks_(kDefaultNumberOfThrowingBlocks, arena_->Adapter(kArenaAllocGraphBuilder)),
+        number_of_branches_(0u) {}
+
+  // Creates basic blocks in `graph_` at branch target dex_pc positions of the
+  // `code_item_`. Blocks are connected but left unpopulated with instructions.
+  // TryBoundary blocks are inserted at positions where control-flow enters/
+  // exits a try block.
+  bool Build();
+
+  size_t GetNumberOfBranches() const { return number_of_branches_; }
+  HBasicBlock* GetBlockAt(uint32_t dex_pc) const { return branch_targets_[dex_pc]; }
+
+ private:
+  // Creates a basic block starting at given `dex_pc`.
+  HBasicBlock* MaybeCreateBlockAt(uint32_t dex_pc);
+
+  // Creates a basic block for bytecode instructions at `semantic_dex_pc` and
+  // stores it under the `store_dex_pc` key. This is used when multiple blocks
+  // share the same semantic dex_pc, e.g. when building switch decision trees.
+  HBasicBlock* MaybeCreateBlockAt(uint32_t semantic_dex_pc, uint32_t store_dex_pc);
+
+  bool CreateBranchTargets();
+  void ConnectBasicBlocks();
+  void InsertTryBoundaryBlocks();
+
+  // Helper method which decides whether `catch_block` may have live normal
+  // predecessors and thus whether a synthetic catch block needs to be created
+  // to avoid mixing normal and exceptional predecessors.
+  // Should only be called during InsertTryBoundaryBlocks on blocks at catch
+  // handler dex_pcs.
+  bool MightHaveLiveNormalPredecessors(HBasicBlock* catch_block);
+
+  ArenaAllocator* const arena_;
+  HGraph* const graph_;
+
+  const DexFile* const dex_file_;
+  const DexFile::CodeItem& code_item_;
+
+  ArenaVector<HBasicBlock*> branch_targets_;
+  ArenaVector<HBasicBlock*> throwing_blocks_;
+  size_t number_of_branches_;
+
+  static constexpr size_t kDefaultNumberOfThrowingBlocks = 2u;
+
+  DISALLOW_COPY_AND_ASSIGN(HBasicBlockBuilder);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_BLOCK_BUILDER_H_
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index b6b8322f03..53158588de 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -20,6 +20,7 @@
 #include "base/arena_bit_vector.h"
 #include "base/bit_vector-inl.h"
 #include "base/logging.h"
+#include "bytecode_utils.h"
 #include "class_linker.h"
 #include "dex/verified_method.h"
 #include "dex_file-inl.h"
@@ -41,9 +42,10 @@ namespace art {
 void HGraphBuilder::InitializeLocals(uint16_t count) {
   graph_->SetNumberOfVRegs(count);
   locals_.resize(count);
+  HBasicBlock* entry_block = graph_->GetEntryBlock();
   for (int i = 0; i < count; i++) {
     HLocal* local = new (arena_) HLocal(i);
-    entry_block_->AddInstruction(local);
+    entry_block->AddInstruction(local);
     locals_[i] = local;
   }
 }
@@ -54,6 +56,8 @@ void HGraphBuilder::InitializeParameters(uint16_t number_of_parameters) {
     return;
   }
 
+  HBasicBlock* entry_block = graph_->GetEntryBlock();
+
   graph_->SetNumberOfInVRegs(number_of_parameters);
   const char* shorty = dex_compilation_unit_->GetShorty();
   int locals_index = locals_.size() - number_of_parameters;
@@ -68,9 +72,9 @@ void HGraphBuilder::InitializeParameters(uint16_t number_of_parameters) {
                                                               parameter_index++,
                                                               Primitive::kPrimNot,
                                                               true);
-    entry_block_->AddInstruction(parameter);
+    entry_block->AddInstruction(parameter);
     HLocal* local = GetLocalAt(locals_index++);
-    entry_block_->AddInstruction(new (arena_) HStoreLocal(local, parameter, local->GetDexPc()));
+    entry_block->AddInstruction(new (arena_) HStoreLocal(local, parameter, local->GetDexPc()));
     number_of_parameters--;
   }
 
@@ -84,11 +88,11 @@ void HGraphBuilder::InitializeParameters(uint16_t number_of_parameters) {
         Primitive::GetType(shorty[shorty_pos]),
         false);
     ++shorty_pos;
-    entry_block_->AddInstruction(parameter);
+    entry_block->AddInstruction(parameter);
     HLocal* local = GetLocalAt(locals_index++);
     // Store the parameter value in the local that the dex code will use
     // to reference that parameter.
-    entry_block_->AddInstruction(new (arena_) HStoreLocal(local, parameter, local->GetDexPc()));
+    entry_block->AddInstruction(new (arena_) HStoreLocal(local, parameter, local->GetDexPc()));
     bool is_wide = (parameter->GetType() == Primitive::kPrimLong)
         || (parameter->GetType() == Primitive::kPrimDouble);
     if (is_wide) {
@@ -101,36 +105,22 @@ void HGraphBuilder::InitializeParameters(uint16_t number_of_parameters) {
 
 template<typename T>
 void HGraphBuilder::If_22t(const Instruction& instruction, uint32_t dex_pc) {
-  int32_t target_offset = instruction.GetTargetOffset();
-  HBasicBlock* branch_target = FindBlockStartingAt(dex_pc + target_offset);
-  HBasicBlock* fallthrough_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
-  DCHECK(branch_target != nullptr);
-  DCHECK(fallthrough_target != nullptr);
   HInstruction* first = LoadLocal(instruction.VRegA(), Primitive::kPrimInt, dex_pc);
   HInstruction* second = LoadLocal(instruction.VRegB(), Primitive::kPrimInt, dex_pc);
   T* comparison = new (arena_) T(first, second, dex_pc);
   current_block_->AddInstruction(comparison);
   HInstruction* ifinst = new (arena_) HIf(comparison, dex_pc);
   current_block_->AddInstruction(ifinst);
-  current_block_->AddSuccessor(branch_target);
-  current_block_->AddSuccessor(fallthrough_target);
   current_block_ = nullptr;
 }
 
 template<typename T>
 void HGraphBuilder::If_21t(const Instruction& instruction, uint32_t dex_pc) {
-  int32_t target_offset = instruction.GetTargetOffset();
-  HBasicBlock* branch_target = FindBlockStartingAt(dex_pc + target_offset);
-  HBasicBlock* fallthrough_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
-  DCHECK(branch_target != nullptr);
-  DCHECK(fallthrough_target != nullptr);
   HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt, dex_pc);
   T* comparison = new (arena_) T(value, graph_->GetIntConstant(0, dex_pc), dex_pc);
   current_block_->AddInstruction(comparison);
   HInstruction* ifinst = new (arena_) HIf(comparison, dex_pc);
   current_block_->AddInstruction(ifinst);
-  current_block_->AddSuccessor(branch_target);
-  current_block_->AddSuccessor(fallthrough_target);
   current_block_ = nullptr;
 }
 
@@ -140,28 +130,32 @@ void HGraphBuilder::MaybeRecordStat(MethodCompilationStat compilation_stat) {
   }
 }
 
-bool HGraphBuilder::SkipCompilation(const DexFile::CodeItem& code_item,
-                                    size_t number_of_branches) {
+bool HGraphBuilder::SkipCompilation(size_t number_of_branches) {
+  if (compiler_driver_ == nullptr) {
+    // Note that the compiler driver is null when unit testing.
+    return false;
+  }
+
   const CompilerOptions& compiler_options = compiler_driver_->GetCompilerOptions();
   CompilerFilter::Filter compiler_filter = compiler_options.GetCompilerFilter();
   if (compiler_filter == CompilerFilter::kEverything) {
     return false;
   }
 
-  if (compiler_options.IsHugeMethod(code_item.insns_size_in_code_units_)) {
+  if (compiler_options.IsHugeMethod(code_item_.insns_size_in_code_units_)) {
     VLOG(compiler) << "Skip compilation of huge method "
                    << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
-                   << ": " << code_item.insns_size_in_code_units_ << " code units";
+                   << ": " << code_item_.insns_size_in_code_units_ << " code units";
     MaybeRecordStat(MethodCompilationStat::kNotCompiledHugeMethod);
     return true;
   }
 
   // If it's large and contains no branches, it's likely to be machine generated initialization.
-  if (compiler_options.IsLargeMethod(code_item.insns_size_in_code_units_)
+  if (compiler_options.IsLargeMethod(code_item_.insns_size_in_code_units_)
       && (number_of_branches == 0)) {
     VLOG(compiler) << "Skip compilation of large method with no branch "
                    << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
-                   << ": " << code_item.insns_size_in_code_units_ << " code units";
+                   << ": " << code_item_.insns_size_in_code_units_ << " code units";
     MaybeRecordStat(MethodCompilationStat::kNotCompiledLargeMethodNoBranches);
     return true;
   }
@@ -169,194 +163,19 @@ bool HGraphBuilder::SkipCompilation(const DexFile::CodeItem& code_item,
   return false;
 }
 
-void HGraphBuilder::CreateBlocksForTryCatch(const DexFile::CodeItem& code_item) {
-  if (code_item.tries_size_ == 0) {
-    return;
-  }
-
-  // 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 (size_t idx = 0; idx < code_item.tries_size_; ++idx) {
-    const DexFile::TryItem* try_item = DexFile::GetTryItems(code_item, idx);
-    uint32_t dex_pc_start = try_item->start_addr_;
-    uint32_t dex_pc_end = dex_pc_start + try_item->insn_count_;
-    FindOrCreateBlockStartingAt(dex_pc_start);
-    if (dex_pc_end < code_item.insns_size_in_code_units_) {
-      // TODO: Do not create block if the last instruction cannot fall through.
-      FindOrCreateBlockStartingAt(dex_pc_end);
-    } else {
-      // The TryItem spans until the very end of the CodeItem (or beyond if
-      // invalid) and therefore cannot have any code afterwards.
-    }
-  }
-
-  // Create branch targets for exception handlers.
-  const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(code_item, 0);
-  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();
-      HBasicBlock* block = FindOrCreateBlockStartingAt(address);
-      block->SetTryCatchInformation(
-        new (arena_) TryCatchInformation(iterator.GetHandlerTypeIndex(), *dex_file_));
-    }
-    handlers_ptr = iterator.EndDataPointer();
-  }
-}
-
-// Returns the TryItem stored for `block` or nullptr if there is no info for it.
-static const DexFile::TryItem* GetTryItem(
-    HBasicBlock* block,
-    const ArenaSafeMap<uint32_t, const DexFile::TryItem*>& try_block_info) {
-  auto iterator = try_block_info.find(block->GetBlockId());
-  return (iterator == try_block_info.end()) ? nullptr : iterator->second;
-}
-
-void HGraphBuilder::LinkToCatchBlocks(HTryBoundary* try_boundary,
-                                      const DexFile::CodeItem& code_item,
-                                      const DexFile::TryItem* try_item) {
-  for (CatchHandlerIterator it(code_item, *try_item); it.HasNext(); it.Next()) {
-    try_boundary->AddExceptionHandler(FindBlockStartingAt(it.GetHandlerAddress()));
-  }
-}
-
-void HGraphBuilder::InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item) {
-  if (code_item.tries_size_ == 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.
-  ArenaSafeMap<uint32_t, const DexFile::TryItem*> try_block_info(
-      std::less<uint32_t>(), arena_->Adapter(kArenaAllocGraphBuilder));
-
-  // Obtain TryItem information for blocks with throwing instructions, and split
-  // blocks which are both try & catch to simplify the graph.
-  // NOTE: We are appending new blocks inside the loop, so we need to use index
-  // because iterators can be invalidated. We remember the initial size to avoid
-  // iterating over the new blocks which cannot throw.
-  for (size_t i = 0, e = graph_->GetBlocks().size(); i < e; ++i) {
-    HBasicBlock* block = graph_->GetBlocks()[i];
-
-    // 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 (block->HasThrowingInstructions()) {
-      // Try to find a TryItem covering the block.
-      DCHECK_NE(block->GetDexPc(), kNoDexPc) << "Block must have a dex_pc to find its TryItem.";
-      const int32_t try_item_idx = DexFile::FindTryItem(code_item, block->GetDexPc());
-      if (try_item_idx != -1) {
-        // Block throwing and in a TryItem. Store the try block information.
-        HBasicBlock* throwing_block = block;
-        if (block->IsCatchBlock()) {
-          // Simplify blocks which are both try and catch, otherwise we would
-          // need a strategy for splitting exceptional edges. We split the block
-          // after the move-exception (if present) and mark the first part not
-          // throwing. The normal-flow edge between them will be split later.
-          throwing_block = block->SplitCatchBlockAfterMoveException();
-          // Move-exception does not throw and the block has throwing insructions
-          // so it must have been possible to split it.
-          DCHECK(throwing_block != nullptr);
-        }
-
-        try_block_info.Put(throwing_block->GetBlockId(),
-                           DexFile::GetTryItems(code_item, try_item_idx));
-      }
-    }
-  }
-
-  // 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 (auto entry : try_block_info) {
-    HBasicBlock* try_block = graph_->GetBlocks()[entry.first];
-    for (HBasicBlock* predecessor : try_block->GetPredecessors()) {
-      if (GetTryItem(predecessor, try_block_info) != entry.second) {
-        // Found a predecessor not covered by the same TryItem. Insert entering
-        // boundary block.
-        HTryBoundary* try_entry =
-            new (arena_) HTryBoundary(HTryBoundary::BoundaryKind::kEntry, try_block->GetDexPc());
-        try_block->CreateImmediateDominator()->AddInstruction(try_entry);
-        LinkToCatchBlocks(try_entry, code_item, entry.second);
-        break;
-      }
-    }
-  }
-
-  // Do a second pass over the try blocks and insert exit TryBoundaries where
-  // the successor is not in the same TryItem.
-  for (auto entry : try_block_info) {
-    HBasicBlock* try_block = graph_->GetBlocks()[entry.first];
-    // 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(entry.second, GetTryItem(successor, try_block_info));
-        continue;
-      }
-
-      // Preserve the invariant that Return(Void) always jumps to Exit by moving
-      // it outside the try block if necessary.
-      HInstruction* last_instruction = try_block->GetLastInstruction();
-      if (last_instruction->IsReturn() || last_instruction->IsReturnVoid()) {
-        DCHECK_EQ(successor, exit_block_);
-        successor = try_block->SplitBefore(last_instruction);
-      }
-
-      // Insert TryBoundary and link to catch blocks.
-      HTryBoundary* try_exit =
-          new (arena_) HTryBoundary(HTryBoundary::BoundaryKind::kExit, successor->GetDexPc());
-      graph_->SplitEdge(try_block, successor)->AddInstruction(try_exit);
-      LinkToCatchBlocks(try_exit, code_item, entry.second);
-    }
+static bool BlockIsNotPopulated(HBasicBlock* block) {
+  if (!block->GetPhis().IsEmpty()) {
+    return false;
+  } else if (block->IsLoopHeader()) {
+    // Suspend checks were inserted into loop headers during building of dominator tree.
+    DCHECK(block->GetFirstInstruction()->IsSuspendCheck());
+    return block->GetFirstInstruction() == block->GetLastInstruction();
+  } else {
+    return block->GetInstructions().IsEmpty();
   }
 }
 
-GraphAnalysisResult HGraphBuilder::BuildGraph(const DexFile::CodeItem& code_item,
-                                              StackHandleScopeCollection* handles) {
-  DCHECK(graph_->GetBlocks().empty());
-
-  const uint16_t* code_ptr = code_item.insns_;
-  const uint16_t* code_end = code_item.insns_ + code_item.insns_size_in_code_units_;
-  code_start_ = code_ptr;
-
-  // Setup the graph with the entry block and exit block.
-  entry_block_ = new (arena_) HBasicBlock(graph_, 0);
-  graph_->AddBlock(entry_block_);
-  exit_block_ = new (arena_) HBasicBlock(graph_, kNoDexPc);
-  graph_->SetEntryBlock(entry_block_);
-  graph_->SetExitBlock(exit_block_);
-
-  graph_->SetHasTryCatch(code_item.tries_size_ != 0);
-
-  InitializeLocals(code_item.registers_size_);
-  graph_->SetMaximumNumberOfOutVRegs(code_item.outs_size_);
-
-  // Compute the number of dex instructions, blocks, and branches. We will
-  // check these values against limits given to the compiler.
-  size_t number_of_branches = 0;
-
-  // To avoid splitting blocks, we compute ahead of time the instructions that
-  // start a new block, and create these blocks.
-  if (!ComputeBranchTargets(code_ptr, code_end, &number_of_branches)) {
-    MaybeRecordStat(MethodCompilationStat::kNotCompiledBranchOutsideMethodCode);
-    return kAnalysisInvalidBytecode;
-  }
-
-  // Note that the compiler driver is null when unit testing.
-  if ((compiler_driver_ != nullptr) && SkipCompilation(code_item, number_of_branches)) {
-    return kAnalysisInvalidBytecode;
-  }
-
+bool HGraphBuilder::GenerateInstructions() {
   // Find locations where we want to generate extra stackmaps for native debugging.
   // This allows us to generate the info only at interesting points (for example,
   // at start of java statement) rather than before every dex instruction.
@@ -364,74 +183,93 @@ GraphAnalysisResult HGraphBuilder::BuildGraph(const DexFile::CodeItem& code_item
                                  compiler_driver_->GetCompilerOptions().GetNativeDebuggable();
   ArenaBitVector* native_debug_info_locations;
   if (native_debuggable) {
-    const uint32_t num_instructions = code_item.insns_size_in_code_units_;
+    const uint32_t num_instructions = code_item_.insns_size_in_code_units_;
     native_debug_info_locations =
         ArenaBitVector::Create(arena_, num_instructions, false, kArenaAllocGraphBuilder);
-    FindNativeDebugInfoLocations(code_item, native_debug_info_locations);
+    FindNativeDebugInfoLocations(native_debug_info_locations);
   }
 
-  CreateBlocksForTryCatch(code_item);
+  InitializeLocals(code_item_.registers_size_);
+  InitializeParameters(code_item_.ins_size_);
 
-  InitializeParameters(code_item.ins_size_);
+  // Add the suspend check to the entry block.
+  current_block_ = graph_->GetEntryBlock();
+  current_block_->AddInstruction(new (arena_) HSuspendCheck(0));
 
-  size_t dex_pc = 0;
-  while (code_ptr < code_end) {
-    // Update the current block if dex_pc starts a new block.
-    MaybeUpdateCurrentBlock(dex_pc);
-    const Instruction& instruction = *Instruction::At(code_ptr);
-    if (native_debuggable && native_debug_info_locations->IsBitSet(dex_pc)) {
+  for (CodeItemIterator it(code_item_); !it.Done(); it.Advance()) {
+    uint32_t dex_pc = it.CurrentDexPc();
+
+    HBasicBlock* next_block = FindBlockStartingAt(dex_pc);
+    if (next_block != nullptr && next_block->GetGraph() != nullptr) {
       if (current_block_ != nullptr) {
-        current_block_->AddInstruction(new (arena_) HNativeDebugInfo(dex_pc));
+        // Branching instructions clear current_block, so we know
+        // the last instruction of the current block is not a branching
+        // instruction. We add an unconditional goto to the found block.
+        current_block_->AddInstruction(new (arena_) HGoto(dex_pc));
       }
+      DCHECK(BlockIsNotPopulated(next_block));
+      current_block_ = next_block;
+    }
+
+    if (current_block_ == nullptr) {
+      // Unreachable code.
+      continue;
     }
-    if (!AnalyzeDexInstruction(instruction, dex_pc)) {
-      return kAnalysisInvalidBytecode;
+
+    if (native_debuggable && native_debug_info_locations->IsBitSet(dex_pc)) {
+      current_block_->AddInstruction(new (arena_) HNativeDebugInfo(dex_pc));
+    }
+
+    if (!AnalyzeDexInstruction(it.CurrentInstruction(), dex_pc)) {
+      return false;
     }
-    dex_pc += instruction.SizeInCodeUnits();
-    code_ptr += instruction.SizeInCodeUnits();
   }
 
   // Add Exit to the exit block.
-  exit_block_->AddInstruction(new (arena_) HExit());
-  // Add the suspend check to the entry block.
-  entry_block_->AddInstruction(new (arena_) HSuspendCheck(0));
-  entry_block_->AddInstruction(new (arena_) HGoto());
-  // Add the exit block at the end.
-  graph_->AddBlock(exit_block_);
+  HBasicBlock* exit_block = graph_->GetExitBlock();
+  if (exit_block == nullptr) {
+    // Unreachable exit block was removed.
+  } else {
+    exit_block->AddInstruction(new (arena_) HExit());
+  }
+
+  return true;
+}
+
+GraphAnalysisResult HGraphBuilder::BuildGraph(StackHandleScopeCollection* handles) {
+  DCHECK(graph_->GetBlocks().empty());
+  graph_->SetMaximumNumberOfOutVRegs(code_item_.outs_size_);
+  graph_->SetHasTryCatch(code_item_.tries_size_ != 0);
+  graph_->InitializeInexactObjectRTI(handles);
+
+  // 1) Create basic blocks and link them together. Basic blocks are left
+  //    unpopulated with the exception of synthetic blocks, e.g. HTryBoundaries.
+  if (!block_builder_.Build()) {
+    return kAnalysisInvalidBytecode;
+  }
 
-  // Iterate over blocks covered by TryItems and insert TryBoundaries at entry
-  // and exit points. This requires all control-flow instructions and
-  // non-exceptional edges to have been created.
-  InsertTryBoundaryBlocks(code_item);
+  // 2) Decide whether to skip this method based on its code size and number
+  //    of branches.
+  if (SkipCompilation(block_builder_.GetNumberOfBranches())) {
+    return kAnalysisSkipped;
+  }
 
+  // 3) Build the dominator tree and fill in loop and try/catch metadata.
   GraphAnalysisResult result = graph_->BuildDominatorTree();
   if (result != kAnalysisSuccess) {
     return result;
   }
 
-  graph_->InitializeInexactObjectRTI(handles);
-  return SsaBuilder(graph_, handles).BuildSsa();
-}
-
-void HGraphBuilder::MaybeUpdateCurrentBlock(size_t dex_pc) {
-  HBasicBlock* block = FindBlockStartingAt(dex_pc);
-  if (block == nullptr) {
-    return;
+  // 4) Populate basic blocks with instructions.
+  if (!GenerateInstructions()) {
+    return kAnalysisInvalidBytecode;
   }
 
-  if (current_block_ != nullptr) {
-    // Branching instructions clear current_block, so we know
-    // the last instruction of the current block is not a branching
-    // instruction. We add an unconditional goto to the found block.
-    current_block_->AddInstruction(new (arena_) HGoto(dex_pc));
-    current_block_->AddSuccessor(block);
-  }
-  graph_->AddBlock(block);
-  current_block_ = block;
+  // 5) Type the graph and eliminate dead/redundant phis.
+  return SsaBuilder(graph_, code_item_, handles).BuildSsa();
 }
 
-void HGraphBuilder::FindNativeDebugInfoLocations(const DexFile::CodeItem& code_item,
-                                                 ArenaBitVector* locations) {
+void HGraphBuilder::FindNativeDebugInfoLocations(ArenaBitVector* locations) {
   // The callback gets called when the line number changes.
   // In other words, it marks the start of new java statement.
   struct Callback {
@@ -440,20 +278,20 @@ void HGraphBuilder::FindNativeDebugInfoLocations(const DexFile::CodeItem& code_i
       return false;
     }
   };
-  dex_file_->DecodeDebugPositionInfo(&code_item, Callback::Position, locations);
+  dex_file_->DecodeDebugPositionInfo(&code_item_, Callback::Position, locations);
   // Instruction-specific tweaks.
-  const Instruction* const begin = Instruction::At(code_item.insns_);
-  const Instruction* const end = begin->RelativeAt(code_item.insns_size_in_code_units_);
+  const Instruction* const begin = Instruction::At(code_item_.insns_);
+  const Instruction* const end = begin->RelativeAt(code_item_.insns_size_in_code_units_);
   for (const Instruction* inst = begin; inst < end; inst = inst->Next()) {
     switch (inst->Opcode()) {
       case Instruction::MOVE_EXCEPTION: {
         // Stop in native debugger after the exception has been moved.
         // The compiler also expects the move at the start of basic block so
         // we do not want to interfere by inserting native-debug-info before it.
-        locations->ClearBit(inst->GetDexPc(code_item.insns_));
+        locations->ClearBit(inst->GetDexPc(code_item_.insns_));
         const Instruction* next = inst->Next();
         if (next < end) {
-          locations->SetBit(next->GetDexPc(code_item.insns_));
+          locations->SetBit(next->GetDexPc(code_item_.insns_));
         }
         break;
       }
@@ -463,93 +301,6 @@ void HGraphBuilder::FindNativeDebugInfoLocations(const DexFile::CodeItem& code_i
   }
 }
 
-bool HGraphBuilder::ComputeBranchTargets(const uint16_t* code_ptr,
-                                         const uint16_t* code_end,
-                                         size_t* number_of_branches) {
-  branch_targets_.resize(code_end - code_ptr, nullptr);
-
-  // Create the first block for the dex instructions, single successor of the entry block.
-  HBasicBlock* block = new (arena_) HBasicBlock(graph_, 0);
-  branch_targets_[0] = block;
-  entry_block_->AddSuccessor(block);
-
-  // Iterate over all instructions and find branching instructions. Create blocks for
-  // the locations these instructions branch to.
-  uint32_t dex_pc = 0;
-  while (code_ptr < code_end) {
-    const Instruction& instruction = *Instruction::At(code_ptr);
-    if (instruction.IsBranch()) {
-      (*number_of_branches)++;
-      int32_t target = instruction.GetTargetOffset() + dex_pc;
-      // Create a block for the target instruction.
-      FindOrCreateBlockStartingAt(target);
-
-      dex_pc += instruction.SizeInCodeUnits();
-      code_ptr += instruction.SizeInCodeUnits();
-
-      if (instruction.CanFlowThrough()) {
-        if (code_ptr >= code_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.
-          return false;
-        } else {
-          FindOrCreateBlockStartingAt(dex_pc);
-        }
-      }
-    } else if (instruction.IsSwitch()) {
-      SwitchTable table(instruction, dex_pc, instruction.Opcode() == Instruction::SPARSE_SWITCH);
-
-      uint16_t num_entries = table.GetNumEntries();
-
-      // In a packed-switch, the entry at index 0 is the starting key. In a sparse-switch, the
-      // entry at index 0 is the first key, and values are after *all* keys.
-      size_t offset = table.GetFirstValueIndex();
-
-      // Use a larger loop counter type to avoid overflow issues.
-      for (size_t i = 0; i < num_entries; ++i) {
-        // The target of the case.
-        uint32_t target = dex_pc + table.GetEntryAt(i + offset);
-        FindOrCreateBlockStartingAt(target);
-
-        // Create a block for the switch-case logic. The block gets the dex_pc
-        // of the SWITCH instruction because it is part of its semantics.
-        block = new (arena_) HBasicBlock(graph_, dex_pc);
-        branch_targets_[table.GetDexPcForIndex(i)] = block;
-      }
-
-      // Fall-through. Add a block if there is more code afterwards.
-      dex_pc += instruction.SizeInCodeUnits();
-      code_ptr += instruction.SizeInCodeUnits();
-      if (code_ptr >= code_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.
-        // (A switch can fall-through so we don't need to check CanFlowThrough().)
-        return false;
-      } else {
-        FindOrCreateBlockStartingAt(dex_pc);
-      }
-    } else {
-      code_ptr += instruction.SizeInCodeUnits();
-      dex_pc += instruction.SizeInCodeUnits();
-    }
-  }
-  return true;
-}
-
-HBasicBlock* HGraphBuilder::FindBlockStartingAt(int32_t dex_pc) const {
-  DCHECK_GE(dex_pc, 0);
-  return branch_targets_[dex_pc];
-}
-
-HBasicBlock* HGraphBuilder::FindOrCreateBlockStartingAt(int32_t dex_pc) {
-  HBasicBlock* block = FindBlockStartingAt(dex_pc);
-  if (block == nullptr) {
-    block = new (arena_) HBasicBlock(graph_, dex_pc);
-    branch_targets_[dex_pc] = block;
-  }
-  return block;
-}
-
 template<typename T>
 void HGraphBuilder::Unop_12x(const Instruction& instruction,
                              Primitive::Type type,
@@ -645,6 +396,43 @@ static bool RequiresConstructorBarrier(const DexCompilationUnit* cu, const Compi
       && driver.RequiresConstructorBarrier(self, cu->GetDexFile(), cu->GetClassDefIndex());
 }
 
+// Returns true if `block` has only one successor which starts at the next
+// dex_pc after `instruction` at `dex_pc`.
+static bool IsFallthroughInstruction(const Instruction& instruction,
+                                     uint32_t dex_pc,
+                                     HBasicBlock* block) {
+  uint32_t next_dex_pc = dex_pc + instruction.SizeInCodeUnits();
+  return block->GetSingleSuccessor()->GetDexPc() == next_dex_pc;
+}
+
+void HGraphBuilder::BuildSwitch(const Instruction& instruction, uint32_t dex_pc) {
+  HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt, dex_pc);
+  DexSwitchTable table(instruction, dex_pc);
+
+  if (table.GetNumEntries() == 0) {
+    // Empty Switch. Code falls through to the next block.
+    DCHECK(IsFallthroughInstruction(instruction, dex_pc, current_block_));
+    current_block_->AddInstruction(new (arena_) HGoto(dex_pc));
+  } else if (table.ShouldBuildDecisionTree()) {
+    for (DexSwitchTableIterator it(table); !it.Done(); it.Advance()) {
+      HInstruction* case_value = graph_->GetIntConstant(it.CurrentKey(), dex_pc);
+      HEqual* comparison = new (arena_) HEqual(value, case_value, dex_pc);
+      current_block_->AddInstruction(comparison);
+      HInstruction* ifinst = new (arena_) HIf(comparison, dex_pc);
+      current_block_->AddInstruction(ifinst);
+
+      if (!it.IsLast()) {
+        current_block_ = FindBlockStartingAt(it.GetDexPcForCurrentIndex());
+      }
+    }
+  } else {
+    current_block_->AddInstruction(
+        new (arena_) HPackedSwitch(table.GetEntryAt(0), table.GetNumEntries(), value, dex_pc));
+  }
+
+  current_block_ = nullptr;
+}
+
 void HGraphBuilder::BuildReturn(const Instruction& instruction,
                                 Primitive::Type type,
                                 uint32_t dex_pc) {
@@ -662,7 +450,6 @@ void HGraphBuilder::BuildReturn(const Instruction& instruction,
     HInstruction* value = LoadLocal(instruction.VRegA(), type, dex_pc);
     current_block_->AddInstruction(new (arena_) HReturn(value, dex_pc));
   }
-  current_block_->AddSuccessor(exit_block_);
   current_block_ = nullptr;
 }
 
@@ -1697,130 +1484,6 @@ bool HGraphBuilder::NeedsAccessCheck(uint32_t type_index, bool* finalizable) con
       dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index, finalizable);
 }
 
-void HGraphBuilder::BuildSwitchJumpTable(const SwitchTable& table,
-                                         const Instruction& instruction,
-                                         HInstruction* value,
-                                         uint32_t dex_pc) {
-  // Add the successor blocks to the current block.
-  uint16_t num_entries = table.GetNumEntries();
-  for (size_t i = 1; i <= num_entries; i++) {
-    int32_t target_offset = table.GetEntryAt(i);
-    HBasicBlock* case_target = FindBlockStartingAt(dex_pc + target_offset);
-    DCHECK(case_target != nullptr);
-
-    // Add the target block as a successor.
-    current_block_->AddSuccessor(case_target);
-  }
-
-  // Add the default target block as the last successor.
-  HBasicBlock* default_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
-  DCHECK(default_target != nullptr);
-  current_block_->AddSuccessor(default_target);
-
-  // Now add the Switch instruction.
-  int32_t starting_key = table.GetEntryAt(0);
-  current_block_->AddInstruction(
-      new (arena_) HPackedSwitch(starting_key, num_entries, value, dex_pc));
-  // This block ends with control flow.
-  current_block_ = nullptr;
-}
-
-void HGraphBuilder::BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc) {
-  // Verifier guarantees that the payload for PackedSwitch contains:
-  //   (a) number of entries (may be zero)
-  //   (b) first and lowest switch case value (entry 0, always present)
-  //   (c) list of target pcs (entries 1 <= i <= N)
-  SwitchTable table(instruction, dex_pc, false);
-
-  // Value to test against.
-  HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt, dex_pc);
-
-  // Starting key value.
-  int32_t starting_key = table.GetEntryAt(0);
-
-  // Retrieve number of entries.
-  uint16_t num_entries = table.GetNumEntries();
-  if (num_entries == 0) {
-    return;
-  }
-
-  // Don't use a packed switch if there are very few entries.
-  if (num_entries > kSmallSwitchThreshold) {
-    BuildSwitchJumpTable(table, instruction, value, dex_pc);
-  } else {
-    // Chained cmp-and-branch, starting from starting_key.
-    for (size_t i = 1; i <= num_entries; i++) {
-      BuildSwitchCaseHelper(instruction,
-                            i,
-                            i == num_entries,
-                            table,
-                            value,
-                            starting_key + i - 1,
-                            table.GetEntryAt(i),
-                            dex_pc);
-    }
-  }
-}
-
-void HGraphBuilder::BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc) {
-  // Verifier guarantees that the payload for SparseSwitch contains:
-  //   (a) number of entries (may be zero)
-  //   (b) sorted key values (entries 0 <= i < N)
-  //   (c) target pcs corresponding to the switch values (entries N <= i < 2*N)
-  SwitchTable table(instruction, dex_pc, true);
-
-  // Value to test against.
-  HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt, dex_pc);
-
-  uint16_t num_entries = table.GetNumEntries();
-
-  for (size_t i = 0; i < num_entries; i++) {
-    BuildSwitchCaseHelper(instruction, i, i == static_cast<size_t>(num_entries) - 1, table, value,
-                          table.GetEntryAt(i), table.GetEntryAt(i + num_entries), dex_pc);
-  }
-}
-
-void HGraphBuilder::BuildSwitchCaseHelper(const Instruction& instruction, size_t index,
-                                          bool is_last_case, const SwitchTable& table,
-                                          HInstruction* value, int32_t case_value_int,
-                                          int32_t target_offset, uint32_t dex_pc) {
-  HBasicBlock* case_target = FindBlockStartingAt(dex_pc + target_offset);
-  DCHECK(case_target != nullptr);
-
-  // The current case's value.
-  HInstruction* this_case_value = graph_->GetIntConstant(case_value_int, dex_pc);
-
-  // Compare value and this_case_value.
-  HEqual* comparison = new (arena_) HEqual(value, this_case_value, dex_pc);
-  current_block_->AddInstruction(comparison);
-  HInstruction* ifinst = new (arena_) HIf(comparison, dex_pc);
-  current_block_->AddInstruction(ifinst);
-
-  // Case hit: use the target offset to determine where to go.
-  current_block_->AddSuccessor(case_target);
-
-  // Case miss: go to the next case (or default fall-through).
-  // When there is a next case, we use the block stored with the table offset representing this
-  // case (that is where we registered them in ComputeBranchTargets).
-  // When there is no next case, we use the following instruction.
-  // TODO: Find a good way to peel the last iteration to avoid conditional, but still have re-use.
-  if (!is_last_case) {
-    HBasicBlock* next_case_target = FindBlockStartingAt(table.GetDexPcForIndex(index));
-    DCHECK(next_case_target != nullptr);
-    current_block_->AddSuccessor(next_case_target);
-
-    // Need to manually add the block, as there is no dex-pc transition for the cases.
-    graph_->AddBlock(next_case_target);
-
-    current_block_ = next_case_target;
-  } else {
-    HBasicBlock* default_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
-    DCHECK(default_target != nullptr);
-    current_block_->AddSuccessor(default_target);
-    current_block_ = nullptr;
-  }
-}
-
 bool HGraphBuilder::CanDecodeQuickenedInfo() const {
   return interpreter_metadata_ != nullptr;
 }
@@ -1833,10 +1496,6 @@ uint16_t HGraphBuilder::LookupQuickenedInfo(uint32_t dex_pc) {
 }
 
 bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32_t dex_pc) {
-  if (current_block_ == nullptr) {
-    return true;  // Dead code
-  }
-
   switch (instruction.Opcode()) {
     case Instruction::CONST_4: {
       int32_t register_index = instruction.VRegA();
@@ -1949,11 +1608,7 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32
     case Instruction::GOTO:
     case Instruction::GOTO_16:
     case Instruction::GOTO_32: {
-      int32_t offset = instruction.GetTargetOffset();
-      HBasicBlock* target = FindBlockStartingAt(offset + dex_pc);
-      DCHECK(target != nullptr);
       current_block_->AddInstruction(new (arena_) HGoto(dex_pc));
-      current_block_->AddSuccessor(target);
       current_block_ = nullptr;
       break;
     }
@@ -2793,8 +2448,6 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32
     case Instruction::THROW: {
       HInstruction* exception = LoadLocal(instruction.VRegA_11x(), Primitive::kPrimNot, dex_pc);
       current_block_->AddInstruction(new (arena_) HThrow(exception, dex_pc));
-      // A throw instruction must branch to the exit block.
-      current_block_->AddSuccessor(exit_block_);
       // We finished building this block. Set the current block to null to avoid
       // adding dead instructions to it.
       current_block_ = nullptr;
@@ -2832,13 +2485,9 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32
       break;
     }
 
+    case Instruction::SPARSE_SWITCH:
     case Instruction::PACKED_SWITCH: {
-      BuildPackedSwitch(instruction, dex_pc);
-      break;
-    }
-
-    case Instruction::SPARSE_SWITCH: {
-      BuildSparseSwitch(instruction, dex_pc);
+      BuildSwitch(instruction, dex_pc);
       break;
     }
 
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index 48f5316222..50a13344df 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -19,6 +19,7 @@
 
 #include "base/arena_containers.h"
 #include "base/arena_object.h"
+#include "block_builder.h"
 #include "dex_file.h"
 #include "dex_file-inl.h"
 #include "driver/compiler_driver.h"
@@ -37,98 +38,67 @@ class HGraphBuilder : public ValueObject {
                 DexCompilationUnit* dex_compilation_unit,
                 const DexCompilationUnit* const outer_compilation_unit,
                 const DexFile* dex_file,
+                const DexFile::CodeItem& code_item,
                 CompilerDriver* driver,
                 OptimizingCompilerStats* compiler_stats,
                 const uint8_t* interpreter_metadata,
                 Handle<mirror::DexCache> dex_cache)
       : arena_(graph->GetArena()),
-        branch_targets_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)),
         locals_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)),
-        entry_block_(nullptr),
-        exit_block_(nullptr),
         current_block_(nullptr),
         graph_(graph),
         dex_file_(dex_file),
+        code_item_(code_item),
         dex_compilation_unit_(dex_compilation_unit),
         compiler_driver_(driver),
         outer_compilation_unit_(outer_compilation_unit),
         return_type_(Primitive::GetType(dex_compilation_unit_->GetShorty()[0])),
-        code_start_(nullptr),
+        code_start_(code_item.insns_),
+        block_builder_(graph, dex_file, code_item),
         latest_result_(nullptr),
         compilation_stats_(compiler_stats),
         interpreter_metadata_(interpreter_metadata),
         dex_cache_(dex_cache) {}
 
   // Only for unit testing.
-  HGraphBuilder(HGraph* graph, Primitive::Type return_type = Primitive::kPrimInt)
+  HGraphBuilder(HGraph* graph,
+                const DexFile::CodeItem& code_item,
+                Primitive::Type return_type = Primitive::kPrimInt)
       : arena_(graph->GetArena()),
-        branch_targets_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)),
         locals_(graph->GetArena()->Adapter(kArenaAllocGraphBuilder)),
-        entry_block_(nullptr),
-        exit_block_(nullptr),
         current_block_(nullptr),
         graph_(graph),
         dex_file_(nullptr),
+        code_item_(code_item),
         dex_compilation_unit_(nullptr),
         compiler_driver_(nullptr),
         outer_compilation_unit_(nullptr),
         return_type_(return_type),
-        code_start_(nullptr),
+        code_start_(code_item.insns_),
+        block_builder_(graph, nullptr, code_item),
         latest_result_(nullptr),
         compilation_stats_(nullptr),
         interpreter_metadata_(nullptr),
         null_dex_cache_(),
         dex_cache_(null_dex_cache_) {}
 
-  GraphAnalysisResult BuildGraph(const DexFile::CodeItem& code,
-                                 StackHandleScopeCollection* handles);
+  GraphAnalysisResult BuildGraph(StackHandleScopeCollection* handles);
 
   static constexpr const char* kBuilderPassName = "builder";
 
-  // The number of entries in a packed switch before we use a jump table or specified
-  // compare/jump series.
-  static constexpr uint16_t kSmallSwitchThreshold = 3;
-
  private:
-  // Analyzes the dex instruction and adds HInstruction to the graph
-  // to execute that instruction. Returns whether the instruction can
-  // be handled.
+  bool GenerateInstructions();
   bool AnalyzeDexInstruction(const Instruction& instruction, uint32_t dex_pc);
 
-  // Finds all instructions that start a new block, and populates branch_targets_ with
-  // the newly created blocks.
-  // As a side effect, also compute the number of dex instructions, blocks, and
-  // branches.
-  // Returns true if all the branches fall inside the method code, false otherwise.
-  // (In normal cases this should always return true but someone can artificially
-  // create a code unit in which branches fall-through out of it).
-  bool ComputeBranchTargets(const uint16_t* start,
-                            const uint16_t* end,
-                            size_t* number_of_branches);
-  void MaybeUpdateCurrentBlock(size_t dex_pc);
-  void FindNativeDebugInfoLocations(const DexFile::CodeItem& code_item, ArenaBitVector* locations);
-  HBasicBlock* FindBlockStartingAt(int32_t dex_pc) const;
-  HBasicBlock* FindOrCreateBlockStartingAt(int32_t dex_pc);
-
-  // Adds new blocks to `branch_targets_` starting at the limits of TryItems and
-  // their exception handlers.
-  void CreateBlocksForTryCatch(const DexFile::CodeItem& code_item);
-
-  // Splits edges which cross the boundaries of TryItems, inserts TryBoundary
-  // instructions and links them to the corresponding catch blocks.
-  void InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item);
-
-  // 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.
-  void LinkToCatchBlocks(HTryBoundary* try_boundary,
-                         const DexFile::CodeItem& code_item,
-                         const DexFile::TryItem* try_item);
+  void FindNativeDebugInfoLocations(ArenaBitVector* locations);
 
   bool CanDecodeQuickenedInfo() const;
   uint16_t LookupQuickenedInfo(uint32_t dex_pc);
 
+  HBasicBlock* FindBlockStartingAt(uint32_t dex_pc) const {
+    return block_builder_.GetBlockAt(dex_pc);
+  }
+
   void InitializeLocals(uint16_t count);
   HLocal* GetLocalAt(uint32_t register_index) const;
   void UpdateLocal(uint32_t register_index, HInstruction* instruction, uint32_t dex_pc) const;
@@ -241,24 +211,10 @@ class HGraphBuilder : public ValueObject {
                       uint16_t type_index,
                       uint32_t dex_pc);
 
-  // Builds an instruction sequence for a packed switch statement.
-  void BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc);
-
-  // Build a switch instruction from a packed switch statement.
-  void BuildSwitchJumpTable(const SwitchTable& table,
-                            const Instruction& instruction,
-                            HInstruction* value,
-                            uint32_t dex_pc);
+  // Builds an instruction sequence for a switch statement.
+  void BuildSwitch(const Instruction& instruction, uint32_t dex_pc);
 
-  // Builds an instruction sequence for a sparse switch statement.
-  void BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc);
-
-  void BuildSwitchCaseHelper(const Instruction& instruction, size_t index,
-                             bool is_last_case, const SwitchTable& table,
-                             HInstruction* value, int32_t case_value_int,
-                             int32_t target_offset, uint32_t dex_pc);
-
-  bool SkipCompilation(const DexFile::CodeItem& code_item, size_t number_of_branches);
+  bool SkipCompilation(size_t number_of_branches);
 
   void MaybeRecordStat(MethodCompilationStat compilation_stat);
 
@@ -319,20 +275,14 @@ class HGraphBuilder : public ValueObject {
 
   ArenaAllocator* const arena_;
 
-  // A list of the size of the dex code holding block information for
-  // the method. If an entry contains a block, then the dex instruction
-  // starting at that entry is the first instruction of a new block.
-  ArenaVector<HBasicBlock*> branch_targets_;
-
   ArenaVector<HLocal*> locals_;
 
-  HBasicBlock* entry_block_;
-  HBasicBlock* exit_block_;
   HBasicBlock* current_block_;
   HGraph* const graph_;
 
-  // The dex file where the method being compiled is.
+  // The dex file where the method being compiled is, and the bytecode data.
   const DexFile* const dex_file_;
+  const DexFile::CodeItem& code_item_;
 
   // The compilation unit of the current method being compiled. Note that
   // it can be an inlined method.
@@ -352,6 +302,8 @@ class HGraphBuilder : public ValueObject {
   // being currently compiled start.
   const uint16_t* code_start_;
 
+  HBasicBlockBuilder block_builder_;
+
   // The last invoke or fill-new-array being built. Only to be
   // used by move-result instructions.
   HInstruction* latest_result_;
diff --git a/compiler/optimizing/bytecode_utils.h b/compiler/optimizing/bytecode_utils.h
new file mode 100644
index 0000000000..6dfffce117
--- /dev/null
+++ b/compiler/optimizing/bytecode_utils.h
@@ -0,0 +1,179 @@
+/*
+ * 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_BYTECODE_UTILS_H_
+#define ART_COMPILER_OPTIMIZING_BYTECODE_UTILS_H_
+
+#include "base/arena_object.h"
+#include "dex_file.h"
+#include "dex_file-inl.h"
+#include "dex_instruction-inl.h"
+
+namespace art {
+
+class CodeItemIterator : public ValueObject {
+ public:
+  CodeItemIterator(const DexFile::CodeItem& code_item, uint32_t start_dex_pc = 0u)
+      : code_ptr_(code_item.insns_ + start_dex_pc),
+        code_end_(code_item.insns_ + code_item.insns_size_in_code_units_),
+        dex_pc_(start_dex_pc) {}
+
+  bool Done() const { return code_ptr_ >= code_end_; }
+  bool IsLast() const { return code_ptr_ + CurrentInstruction().SizeInCodeUnits() >= code_end_; }
+
+  const Instruction& CurrentInstruction() const { return *Instruction::At(code_ptr_); }
+  uint32_t CurrentDexPc() const { return dex_pc_; }
+
+  void Advance() {
+    DCHECK(!Done());
+    size_t instruction_size = CurrentInstruction().SizeInCodeUnits();
+    code_ptr_ += instruction_size;
+    dex_pc_ += instruction_size;
+  }
+
+ private:
+  const uint16_t* code_ptr_;
+  const uint16_t* const code_end_;
+  uint32_t dex_pc_;
+
+  DISALLOW_COPY_AND_ASSIGN(CodeItemIterator);
+};
+
+class DexSwitchTable : public ValueObject {
+ public:
+  DexSwitchTable(const Instruction& instruction, uint32_t dex_pc)
+      : instruction_(instruction),
+        dex_pc_(dex_pc),
+        sparse_(instruction.Opcode() == Instruction::SPARSE_SWITCH) {
+    int32_t table_offset = instruction.VRegB_31t();
+    const uint16_t* table = reinterpret_cast<const uint16_t*>(&instruction) + table_offset;
+    DCHECK_EQ(table[0], sparse_ ? static_cast<uint16_t>(Instruction::kSparseSwitchSignature)
+                                : static_cast<uint16_t>(Instruction::kPackedSwitchSignature));
+    num_entries_ = table[1];
+    values_ = reinterpret_cast<const int32_t*>(&table[2]);
+  }
+
+  uint16_t GetNumEntries() const {
+    return num_entries_;
+  }
+
+  void CheckIndex(size_t index) const {
+    if (sparse_) {
+      // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order.
+      DCHECK_LT(index, 2 * static_cast<size_t>(num_entries_));
+    } else {
+      // In a packed table, we have the starting key and num_entries_ values.
+      DCHECK_LT(index, 1 + static_cast<size_t>(num_entries_));
+    }
+  }
+
+  int32_t GetEntryAt(size_t index) const {
+    CheckIndex(index);
+    return values_[index];
+  }
+
+  uint32_t GetDexPcForIndex(size_t index) const {
+    CheckIndex(index);
+    return dex_pc_ +
+        (reinterpret_cast<const int16_t*>(values_ + index) -
+         reinterpret_cast<const int16_t*>(&instruction_));
+  }
+
+  // Index of the first value in the table.
+  size_t GetFirstValueIndex() const {
+    if (sparse_) {
+      // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order.
+      return num_entries_;
+    } else {
+      // In a packed table, we have the starting key and num_entries_ values.
+      return 1;
+    }
+  }
+
+  bool IsSparse() const { return sparse_; }
+
+  bool ShouldBuildDecisionTree() {
+    return IsSparse() || GetNumEntries() <= kSmallSwitchThreshold;
+  }
+
+ private:
+  const Instruction& instruction_;
+  const uint32_t dex_pc_;
+
+  // Whether this is a sparse-switch table (or a packed-switch one).
+  const bool sparse_;
+
+  // This can't be const as it needs to be computed off of the given instruction, and complicated
+  // expressions in the initializer list seemed very ugly.
+  uint16_t num_entries_;
+
+  const int32_t* values_;
+
+  // The number of entries in a packed switch before we use a jump table or specified
+  // compare/jump series.
+  static constexpr uint16_t kSmallSwitchThreshold = 3;
+
+  DISALLOW_COPY_AND_ASSIGN(DexSwitchTable);
+};
+
+class DexSwitchTableIterator {
+ public:
+  explicit DexSwitchTableIterator(const DexSwitchTable& table)
+      : table_(table),
+        num_entries_(static_cast<size_t>(table_.GetNumEntries())),
+        first_target_offset_(table_.GetFirstValueIndex()),
+        index_(0u) {}
+
+  bool Done() const { return index_ >= num_entries_; }
+  bool IsLast() const { return index_ == num_entries_ - 1; }
+
+  void Advance() {
+    DCHECK(!Done());
+    index_++;
+  }
+
+  int32_t CurrentKey() const {
+    return table_.IsSparse() ? table_.GetEntryAt(index_) : table_.GetEntryAt(0) + index_;
+  }
+
+  int32_t CurrentTargetOffset() const {
+    return table_.GetEntryAt(index_ + first_target_offset_);
+  }
+
+  uint32_t GetDexPcForCurrentIndex() const { return table_.GetDexPcForIndex(index_); }
+
+ private:
+  const DexSwitchTable& table_;
+  const size_t num_entries_;
+  const size_t first_target_offset_;
+
+  size_t index_;
+};
+
+inline const Instruction& GetDexInstructionAt(const DexFile::CodeItem& code_item, uint32_t dex_pc) {
+  return CodeItemIterator(code_item, dex_pc).CurrentInstruction();
+}
+
+inline bool IsThrowingDexInstruction(const Instruction& instruction) {
+  // Special-case MONITOR_EXIT which is a throwing instruction but the verifier
+  // guarantees that it will never throw. This is necessary to avoid rejecting
+  // 'synchronized' blocks/methods.
+  return instruction.IsThrow() && instruction.Opcode() != Instruction::MONITOR_EXIT;
+}
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_BYTECODE_UTILS_H_
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 7cf9072598..1d2273da9c 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -40,6 +40,7 @@
 #include "code_generator_mips64.h"
 #endif
 
+#include "bytecode_utils.h"
 #include "compiled_method.h"
 #include "dex/verified_method.h"
 #include "driver/compiler_driver.h"
@@ -680,7 +681,7 @@ static void CheckLoopEntriesCanBeUsedForOsr(const HGraph& graph,
       uint32_t target = dex_pc + instruction.GetTargetOffset();
       CheckCovers(target, graph, code_info, loop_headers, &covered);
     } else if (instruction.IsSwitch()) {
-      SwitchTable table(instruction, dex_pc, instruction.Opcode() == Instruction::SPARSE_SWITCH);
+      DexSwitchTable table(instruction, dex_pc);
       uint16_t num_entries = table.GetNumEntries();
       size_t offset = table.GetFirstValueIndex();
 
diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc
index 1e54a0adfa..b9081cb7e3 100644
--- a/compiler/optimizing/constant_folding_test.cc
+++ b/compiler/optimizing/constant_folding_test.cc
@@ -111,22 +111,21 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingNegation) {
 
   std::string expected_before =
       "BasicBlock 0, succ: 1\n"
-      "  2: IntConstant [5]\n"
-      "  10: SuspendCheck\n"
-      "  11: Goto 1\n"
+      "  4: IntConstant [7]\n"
+      "  2: SuspendCheck\n"
+      "  3: Goto 1\n"
       "BasicBlock 1, pred: 0, succ: 2\n"
-      "  5: Neg(2) [8]\n"
-      "  8: Return(5)\n"
+      "  7: Neg(4) [10]\n"
+      "  10: Return(7)\n"
       "BasicBlock 2, pred: 1\n"
-      "  9: Exit\n";
+      "  11: Exit\n";
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  2: IntConstant [5]\n", "  2: IntConstant\n" },
-    { "  10: SuspendCheck\n",   "  10: SuspendCheck\n"
-                                "  12: IntConstant [8]\n" },
-    { "  5: Neg(2) [8]\n",      removed },
-    { "  8: Return(5)\n",       "  8: Return(12)\n" }
+    { "  4: IntConstant [7]\n", "  4: IntConstant\n"
+                                "  12: IntConstant [10]\n" },
+    { "  7: Neg(4) [10]\n",     removed },
+    { "  10: Return(7)\n",      "  10: Return(12)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
@@ -139,7 +138,7 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingNegation) {
 
   // Expected difference after dead code elimination.
   diff_t expected_dce_diff = {
-    { "  2: IntConstant\n", removed },
+    { "  4: IntConstant\n", removed },
   };
   std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
 
@@ -173,22 +172,21 @@ TEST_F(ConstantFoldingTest, LongConstantFoldingNegation) {
 
   std::string expected_before =
       "BasicBlock 0, succ: 1\n"
-      "  4: LongConstant [7]\n"
-      "  12: SuspendCheck\n"
-      "  13: Goto 1\n"
+      "  6: LongConstant [9]\n"
+      "  4: SuspendCheck\n"
+      "  5: Goto 1\n"
       "BasicBlock 1, pred: 0, succ: 2\n"
-      "  7: Neg(4) [10]\n"
-      "  10: Return(7)\n"
+      "  9: Neg(6) [12]\n"
+      "  12: Return(9)\n"
       "BasicBlock 2, pred: 1\n"
-      "  11: Exit\n";
+      "  13: Exit\n";
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  4: LongConstant [7]\n", "  4: LongConstant\n" },
-    { "  12: SuspendCheck\n",    "  12: SuspendCheck\n"
-                                 "  14: LongConstant [10]\n" },
-    { "  7: Neg(4) [10]\n",      removed },
-    { "  10: Return(7)\n",       "  10: Return(14)\n" }
+    { "  6: LongConstant [9]\n", "  6: LongConstant\n"
+                                 "  14: LongConstant [12]\n" },
+    { "  9: Neg(6) [12]\n",      removed },
+    { "  12: Return(9)\n",       "  12: Return(14)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
@@ -201,7 +199,7 @@ TEST_F(ConstantFoldingTest, LongConstantFoldingNegation) {
 
   // Expected difference after dead code elimination.
   diff_t expected_dce_diff = {
-    { "  4: LongConstant\n", removed },
+    { "  6: LongConstant\n", removed },
   };
   std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
 
@@ -232,25 +230,24 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition1) {
     Instruction::RETURN | 2 << 8);
 
   std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  3: IntConstant [9]\n"
-    "  5: IntConstant [9]\n"
-    "  14: SuspendCheck\n"
-    "  15: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  9: Add(3, 5) [12]\n"
-    "  12: Return(9)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  13: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  5: IntConstant [11]\n"
+      "  7: IntConstant [11]\n"
+      "  3: SuspendCheck\n"
+      "  4: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 2\n"
+      "  11: Add(5, 7) [14]\n"
+      "  14: Return(11)\n"
+      "BasicBlock 2, pred: 1\n"
+      "  15: Exit\n";
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  3: IntConstant [9]\n", "  3: IntConstant\n" },
-    { "  5: IntConstant [9]\n", "  5: IntConstant\n" },
-    { "  14: SuspendCheck\n",   "  14: SuspendCheck\n"
-                                "  16: IntConstant [12]\n" },
-    { "  9: Add(3, 5) [12]\n",  removed },
-    { "  12: Return(9)\n",      "  12: Return(16)\n" }
+    { "  5: IntConstant [11]\n", "  5: IntConstant\n" },
+    { "  7: IntConstant [11]\n", "  7: IntConstant\n"
+                                 "  16: IntConstant [14]\n" },
+    { "  11: Add(5, 7) [14]\n",  removed },
+    { "  14: Return(11)\n",      "  14: Return(16)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
@@ -263,8 +260,8 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition1) {
 
   // Expected difference after dead code elimination.
   diff_t expected_dce_diff = {
-    { "  3: IntConstant\n", removed },
-    { "  5: IntConstant\n", removed }
+    { "  5: IntConstant\n", removed },
+    { "  7: IntConstant\n", removed }
   };
   std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
 
@@ -302,35 +299,34 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition2) {
     Instruction::RETURN | 2 << 8);
 
   std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  3: IntConstant [9]\n"
-    "  5: IntConstant [9]\n"
-    "  11: IntConstant [17]\n"
-    "  13: IntConstant [17]\n"
-    "  26: SuspendCheck\n"
-    "  27: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  9: Add(3, 5) [21]\n"
-    "  17: Add(11, 13) [21]\n"
-    "  21: Add(9, 17) [24]\n"
-    "  24: Return(21)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  25: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  5: IntConstant [11]\n"
+      "  7: IntConstant [11]\n"
+      "  13: IntConstant [19]\n"
+      "  15: IntConstant [19]\n"
+      "  3: SuspendCheck\n"
+      "  4: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 2\n"
+      "  11: Add(5, 7) [23]\n"
+      "  19: Add(13, 15) [23]\n"
+      "  23: Add(11, 19) [26]\n"
+      "  26: Return(23)\n"
+      "BasicBlock 2, pred: 1\n"
+      "  27: Exit\n";
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  3: IntConstant [9]\n",   "  3: IntConstant\n" },
-    { "  5: IntConstant [9]\n",   "  5: IntConstant\n" },
-    { "  11: IntConstant [17]\n", "  11: IntConstant\n" },
-    { "  13: IntConstant [17]\n", "  13: IntConstant\n" },
-    { "  26: SuspendCheck\n",     "  26: SuspendCheck\n"
+    { "  5: IntConstant [11]\n",  "  5: IntConstant\n" },
+    { "  7: IntConstant [11]\n",  "  7: IntConstant\n" },
+    { "  13: IntConstant [19]\n", "  13: IntConstant\n" },
+    { "  15: IntConstant [19]\n", "  15: IntConstant\n"
                                   "  28: IntConstant\n"
                                   "  29: IntConstant\n"
-                                  "  30: IntConstant [24]\n" },
-    { "  9: Add(3, 5) [21]\n",    removed },
-    { "  17: Add(11, 13) [21]\n", removed },
-    { "  21: Add(9, 17) [24]\n",  removed  },
-    { "  24: Return(21)\n",       "  24: Return(30)\n" }
+                                  "  30: IntConstant [26]\n" },
+    { "  11: Add(5, 7) [23]\n",   removed },
+    { "  19: Add(13, 15) [23]\n", removed },
+    { "  23: Add(11, 19) [26]\n", removed  },
+    { "  26: Return(23)\n",       "  26: Return(30)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
@@ -349,10 +345,10 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition2) {
 
   // Expected difference after dead code elimination.
   diff_t expected_dce_diff = {
-    { "  3: IntConstant\n",  removed },
     { "  5: IntConstant\n",  removed },
-    { "  11: IntConstant\n", removed },
+    { "  7: IntConstant\n",  removed },
     { "  13: IntConstant\n", removed },
+    { "  15: IntConstant\n", removed },
     { "  28: IntConstant\n", removed },
     { "  29: IntConstant\n", removed }
   };
@@ -384,25 +380,24 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingOnSubtraction) {
     Instruction::RETURN | 2 << 8);
 
   std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  3: IntConstant [9]\n"
-    "  5: IntConstant [9]\n"
-    "  14: SuspendCheck\n"
-    "  15: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  9: Sub(3, 5) [12]\n"
-    "  12: Return(9)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  13: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  5: IntConstant [11]\n"
+      "  7: IntConstant [11]\n"
+      "  3: SuspendCheck\n"
+      "  4: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 2\n"
+      "  11: Sub(5, 7) [14]\n"
+      "  14: Return(11)\n"
+      "BasicBlock 2, pred: 1\n"
+      "  15: Exit\n";
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  3: IntConstant [9]\n", "  3: IntConstant\n" },
-    { "  5: IntConstant [9]\n", "  5: IntConstant\n" },
-    { "  14: SuspendCheck\n",   "  14: SuspendCheck\n"
-                                "  16: IntConstant [12]\n" },
-    { "  9: Sub(3, 5) [12]\n",  removed },
-    { "  12: Return(9)\n",      "  12: Return(16)\n" }
+    { "  5: IntConstant [11]\n", "  5: IntConstant\n" },
+    { "  7: IntConstant [11]\n", "  7: IntConstant\n"
+                                 "  16: IntConstant [14]\n" },
+    { "  11: Sub(5, 7) [14]\n",  removed },
+    { "  14: Return(11)\n",      "  14: Return(16)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
@@ -415,8 +410,8 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingOnSubtraction) {
 
   // Expected difference after dead code elimination.
   diff_t expected_dce_diff = {
-    { "  3: IntConstant\n", removed },
-    { "  5: IntConstant\n", removed }
+    { "  5: IntConstant\n", removed },
+    { "  7: IntConstant\n", removed }
   };
   std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
 
@@ -448,25 +443,24 @@ TEST_F(ConstantFoldingTest, LongConstantFoldingOnAddition) {
     Instruction::RETURN_WIDE | 4 << 8);
 
   std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  6: LongConstant [12]\n"
-    "  8: LongConstant [12]\n"
-    "  17: SuspendCheck\n"
-    "  18: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  12: Add(6, 8) [15]\n"
-    "  15: Return(12)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  16: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  8: LongConstant [14]\n"
+      "  10: LongConstant [14]\n"
+      "  6: SuspendCheck\n"
+      "  7: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 2\n"
+      "  14: Add(8, 10) [17]\n"
+      "  17: Return(14)\n"
+      "BasicBlock 2, pred: 1\n"
+      "  18: Exit\n";
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  6: LongConstant [12]\n", "  6: LongConstant\n" },
-    { "  8: LongConstant [12]\n", "  8: LongConstant\n" },
-    { "  17: SuspendCheck\n",     "  17: SuspendCheck\n"
-                                  "  19: LongConstant [15]\n" },
-    { "  12: Add(6, 8) [15]\n",   removed },
-    { "  15: Return(12)\n",       "  15: Return(19)\n" }
+    { "  8: LongConstant [14]\n",  "  8: LongConstant\n" },
+    { "  10: LongConstant [14]\n", "  10: LongConstant\n"
+                                   "  19: LongConstant [17]\n" },
+    { "  14: Add(8, 10) [17]\n",   removed },
+    { "  17: Return(14)\n",        "  17: Return(19)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
@@ -479,8 +473,8 @@ TEST_F(ConstantFoldingTest, LongConstantFoldingOnAddition) {
 
   // Expected difference after dead code elimination.
   diff_t expected_dce_diff = {
-    { "  6: LongConstant\n", removed },
-    { "  8: LongConstant\n", removed }
+    { "  8: LongConstant\n", removed },
+    { "  10: LongConstant\n", removed }
   };
   std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
 
@@ -513,25 +507,24 @@ TEST_F(ConstantFoldingTest, LongConstantFoldingOnSubtraction) {
     Instruction::RETURN_WIDE | 4 << 8);
 
   std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  6: LongConstant [12]\n"
-    "  8: LongConstant [12]\n"
-    "  17: SuspendCheck\n"
-    "  18: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  12: Sub(6, 8) [15]\n"
-    "  15: Return(12)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  16: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  8: LongConstant [14]\n"
+      "  10: LongConstant [14]\n"
+      "  6: SuspendCheck\n"
+      "  7: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 2\n"
+      "  14: Sub(8, 10) [17]\n"
+      "  17: Return(14)\n"
+      "BasicBlock 2, pred: 1\n"
+      "  18: Exit\n";
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  6: LongConstant [12]\n", "  6: LongConstant\n" },
-    { "  8: LongConstant [12]\n", "  8: LongConstant\n" },
-    { "  17: SuspendCheck\n",     "  17: SuspendCheck\n"
-                                  "  19: LongConstant [15]\n" },
-    { "  12: Sub(6, 8) [15]\n",   removed },
-    { "  15: Return(12)\n",       "  15: Return(19)\n" }
+    { "  8: LongConstant [14]\n",  "  8: LongConstant\n" },
+    { "  10: LongConstant [14]\n", "  10: LongConstant\n"
+                                   "  19: LongConstant [17]\n" },
+    { "  14: Sub(8, 10) [17]\n",   removed },
+    { "  17: Return(14)\n",        "  17: Return(19)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
@@ -544,8 +537,8 @@ TEST_F(ConstantFoldingTest, LongConstantFoldingOnSubtraction) {
 
   // Expected difference after dead code elimination.
   diff_t expected_dce_diff = {
-    { "  6: LongConstant\n", removed },
-    { "  8: LongConstant\n", removed }
+    { "  8: LongConstant\n", removed },
+    { "  10: LongConstant\n", removed }
   };
   std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);
 
@@ -593,46 +586,45 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingAndJumps) {
     Instruction::RETURN | 2 << 8);
 
   std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  3: IntConstant [9]\n"            // v0 <- 1
-    "  5: IntConstant [9]\n"            // v1 <- 2
-    "  13: IntConstant [14]\n"          // const 5
-    "  18: IntConstant [19]\n"          // const 4
-    "  23: IntConstant [24]\n"          // const 8
-    "  29: SuspendCheck\n"
-    "  30: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 3\n"
-    "  9: Add(3, 5) [19]\n"             // v2 <- v0 + v1 = 1 + 2 = 3
-    "  11: Goto 3\n"                    // goto L2
-    "BasicBlock 2, pred: 3, succ: 4\n"  // L1:
-    "  14: Add(19, 13) [24]\n"          // v1 <- v0 + 3 = 7 + 5 = 12
-    "  16: Goto 4\n"                    // goto L3
-    "BasicBlock 3, pred: 1, succ: 2\n"  // L2:
-    "  19: Add(9, 18) [14]\n"           // v0 <- v2 + 2 = 3 + 4 = 7
-    "  21: Goto 2\n"                    // goto L1
-    "BasicBlock 4, pred: 2, succ: 5\n"  // L3:
-    "  24: Add(14, 23) [27]\n"          // v2 <- v1 + 4 = 12 + 8 = 20
-    "  27: Return(24)\n"                // return v2
-    "BasicBlock 5, pred: 4\n"
-    "  28: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  5: IntConstant [11]\n"            // v0 <- 1
+      "  7: IntConstant [11]\n"            // v1 <- 2
+      "  15: IntConstant [16]\n"           // const 5
+      "  20: IntConstant [21]\n"           // const 4
+      "  25: IntConstant [26]\n"           // const 8
+      "  3: SuspendCheck\n"
+      "  4: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 3\n"
+      "  11: Add(5, 7) [21]\n"             // v2 <- v0 + v1 = 1 + 2 = 3
+      "  13: Goto 3\n"                     // goto L2
+      "BasicBlock 2, pred: 3, succ: 4\n"   // L1:
+      "  16: Add(21, 15) [26]\n"           // v1 <- v0 + 3 = 7 + 5 = 12
+      "  18: Goto 4\n"                     // goto L3
+      "BasicBlock 3, pred: 1, succ: 2\n"   // L2:
+      "  21: Add(11, 20) [16]\n"           // v0 <- v2 + 2 = 3 + 4 = 7
+      "  23: Goto 2\n"                     // goto L1
+      "BasicBlock 4, pred: 2, succ: 5\n"   // L3:
+      "  26: Add(16, 25) [29]\n"           // v2 <- v1 + 4 = 12 + 8 = 20
+      "  29: Return(26)\n"                 // return v2
+      "BasicBlock 5, pred: 4\n"
+      "  30: Exit\n";
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  3: IntConstant [9]\n",   "  3: IntConstant\n" },
-    { "  5: IntConstant [9]\n",   "  5: IntConstant\n" },
-    { "  13: IntConstant [14]\n", "  13: IntConstant\n" },
-    { "  18: IntConstant [19]\n", "  18: IntConstant\n" },
-    { "  23: IntConstant [24]\n", "  23: IntConstant\n" },
-    { "  29: SuspendCheck\n",     "  29: SuspendCheck\n"
+    { "  5: IntConstant [11]\n",  "  5: IntConstant\n" },
+    { "  7: IntConstant [11]\n",  "  7: IntConstant\n" },
+    { "  15: IntConstant [16]\n", "  15: IntConstant\n" },
+    { "  20: IntConstant [21]\n", "  20: IntConstant\n" },
+    { "  25: IntConstant [26]\n", "  25: IntConstant\n"
                                   "  31: IntConstant\n"
                                   "  32: IntConstant\n"
                                   "  33: IntConstant\n"
-                                  "  34: IntConstant [27]\n" },
-    { "  9: Add(3, 5) [19]\n",    removed },
-    { "  14: Add(19, 13) [24]\n", removed },
-    { "  19: Add(9, 18) [14]\n",  removed },
-    { "  24: Add(14, 23) [27]\n", removed },
-    { "  27: Return(24)\n",       "  27: Return(34)\n"}
+                                  "  34: IntConstant [29]\n" },
+    { "  11: Add(5, 7) [21]\n",   removed },
+    { "  16: Add(21, 15) [26]\n", removed },
+    { "  21: Add(11, 20) [16]\n", removed },
+    { "  26: Add(16, 25) [29]\n", removed },
+    { "  29: Return(26)\n",       "  29: Return(34)\n"}
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
@@ -654,14 +646,14 @@ TEST_F(ConstantFoldingTest, IntConstantFoldingAndJumps) {
 
   // Expected difference after dead code elimination.
   std::string expected_after_dce =
-    "BasicBlock 0, succ: 1\n"
-    "  29: SuspendCheck\n"
-    "  34: IntConstant [27]\n"
-    "  30: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 5\n"
-    "  27: Return(34)\n"
-    "BasicBlock 5, pred: 1\n"
-    "  28: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  34: IntConstant [29]\n"
+      "  3: SuspendCheck\n"
+      "  4: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 5\n"
+      "  29: Return(34)\n"
+      "BasicBlock 5, pred: 1\n"
+      "  30: Exit\n";
 
   TestCode(data,
            expected_before,
@@ -693,31 +685,31 @@ TEST_F(ConstantFoldingTest, ConstantCondition) {
     Instruction::RETURN_VOID);
 
   std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  3: IntConstant [15, 22, 8]\n"
-    "  5: IntConstant [22, 8]\n"
-    "  19: SuspendCheck\n"
-    "  20: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 5, 2\n"
-    "  8: GreaterThanOrEqual(3, 5) [9]\n"
-    "  9: If(8)\n"
-    "BasicBlock 2, pred: 1, succ: 3\n"
-    "  12: Goto 3\n"
-    "BasicBlock 3, pred: 5, 2, succ: 4\n"
-    "  22: Phi(5, 3) [15]\n"
-    "  15: Add(22, 3)\n"
-    "  17: ReturnVoid\n"
-    "BasicBlock 4, pred: 3\n"
-    "  18: Exit\n"
-    "BasicBlock 5, pred: 1, succ: 3\n"
-    "  21: Goto 3\n";
+     "BasicBlock 0, succ: 1\n"
+      "  6: IntConstant [18, 22, 11]\n"
+      "  8: IntConstant [22, 11]\n"
+      "  4: SuspendCheck\n"
+      "  5: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 5, 2\n"
+      "  11: GreaterThanOrEqual(6, 8) [12]\n"
+      "  12: If(11)\n"
+      "BasicBlock 2, pred: 1, succ: 3\n"
+      "  15: Goto 3\n"
+      "BasicBlock 3, pred: 5, 2, succ: 4\n"
+      "  22: Phi(8, 6) [18]\n"
+      "  18: Add(22, 6)\n"
+      "  20: ReturnVoid\n"
+      "BasicBlock 4, pred: 3\n"
+      "  21: Exit\n"
+      "BasicBlock 5, pred: 1, succ: 3\n"
+      "  0: Goto 3\n";
 
   // Expected difference after constant folding.
   diff_t expected_cf_diff = {
-    { "  3: IntConstant [15, 22, 8]\n",      "  3: IntConstant [9, 15, 22]\n" },
-    { "  5: IntConstant [22, 8]\n",          "  5: IntConstant [22]\n" },
-    { "  8: GreaterThanOrEqual(3, 5) [9]\n", removed },
-    { "  9: If(8)\n",                        "  9: If(3)\n" }
+    { "  6: IntConstant [18, 22, 11]\n",       "  6: IntConstant [12, 18, 22]\n" },
+    { "  8: IntConstant [22, 11]\n",           "  8: IntConstant [22]\n" },
+    { "  11: GreaterThanOrEqual(6, 8) [12]\n", removed },
+    { "  12: If(11)\n",                        "  12: If(6)\n" }
   };
   std::string expected_after_cf = Patch(expected_before, expected_cf_diff);
 
@@ -730,13 +722,13 @@ TEST_F(ConstantFoldingTest, ConstantCondition) {
 
   // Expected graph after dead code elimination.
   std::string expected_after_dce =
-    "BasicBlock 0, succ: 1\n"
-    "  19: SuspendCheck\n"
-    "  20: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 4\n"
-    "  17: ReturnVoid\n"
-    "BasicBlock 4, pred: 1\n"
-    "  18: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  4: SuspendCheck\n"
+      "  5: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 4\n"
+      "  20: ReturnVoid\n"
+      "BasicBlock 4, pred: 1\n"
+      "  21: Exit\n";
 
   TestCode(data,
            expected_before,
@@ -766,7 +758,10 @@ TEST_F(ConstantFoldingTest, UnsignedComparisonsWithZero) {
   HInstruction* parameter = new (&allocator_) HParameterValue(
       graph_->GetDexFile(), 0, 0, Primitive::kPrimInt, true);
   entry_block->AddInstruction(parameter);
+  entry_block->AddInstruction(new (&allocator_) HGoto());
+
   HInstruction* zero = graph_->GetIntConstant(0);
+
   HInstruction* last;
   block->AddInstruction(last = new (&allocator_) HAbove(zero, parameter));
   block->AddInstruction(new (&allocator_) HSelect(last, parameter, parameter, 0));
@@ -784,70 +779,70 @@ TEST_F(ConstantFoldingTest, UnsignedComparisonsWithZero) {
   block->AddInstruction(new (&allocator_) HSelect(last, parameter, parameter, 0));
   block->AddInstruction(last = new (&allocator_) HBelowOrEqual(parameter, zero));
   block->AddInstruction(new (&allocator_) HSelect(last, parameter, parameter, 0));
-
-  entry_block->AddInstruction(new (&allocator_) HGoto());
   block->AddInstruction(new (&allocator_) HReturn(zero));
+
   exit_block->AddInstruction(new (&allocator_) HExit());
 
   graph_->BuildDominatorTree();
 
   const std::string expected_before =
       "BasicBlock 0, succ: 1\n"
-      "  0: ParameterValue [17, 17, 16, 15, 15, 14, 13, 13, 12, 11, 11, 10, 9, 9, "
-                           "8, 7, 7, 6, 5, 5, 4, 3, 3, 2]\n"
-      "  1: IntConstant [19, 16, 14, 12, 10, 8, 6, 4, 2]\n"
-      "  18: Goto 1\n"
+      "  0: ParameterValue [18, 18, 17, 16, 16, 15, 14, 14, 13, 12, 12, 11, 10, 10, 9, "
+                            "8, 8, 7, 6, 6, 5, 4, 4, 3]\n"
+      "  2: IntConstant [19, 17, 15, 13, 11, 9, 7, 5, 3]\n"
+      "  1: Goto 1\n"
       "BasicBlock 1, pred: 0, succ: 2\n"
-      "  2: Above(1, 0) [3]\n"
-      "  3: Select(0, 0, 2)\n"
-      "  4: Above(0, 1) [5]\n"
-      "  5: Select(0, 0, 4)\n"
-      "  6: AboveOrEqual(1, 0) [7]\n"
-      "  7: Select(0, 0, 6)\n"
-      "  8: AboveOrEqual(0, 1) [9]\n"
-      "  9: Select(0, 0, 8)\n"
-      "  10: Below(1, 0) [11]\n"
-      "  11: Select(0, 0, 10)\n"
-      "  12: Below(0, 1) [13]\n"
-      "  13: Select(0, 0, 12)\n"
-      "  14: BelowOrEqual(1, 0) [15]\n"
-      "  15: Select(0, 0, 14)\n"
-      "  16: BelowOrEqual(0, 1) [17]\n"
-      "  17: Select(0, 0, 16)\n"
-      "  19: Return(1)\n"
+      "  3: Above(2, 0) [4]\n"
+      "  4: Select(0, 0, 3)\n"
+      "  5: Above(0, 2) [6]\n"
+      "  6: Select(0, 0, 5)\n"
+      "  7: AboveOrEqual(2, 0) [8]\n"
+      "  8: Select(0, 0, 7)\n"
+      "  9: AboveOrEqual(0, 2) [10]\n"
+      "  10: Select(0, 0, 9)\n"
+      "  11: Below(2, 0) [12]\n"
+      "  12: Select(0, 0, 11)\n"
+      "  13: Below(0, 2) [14]\n"
+      "  14: Select(0, 0, 13)\n"
+      "  15: BelowOrEqual(2, 0) [16]\n"
+      "  16: Select(0, 0, 15)\n"
+      "  17: BelowOrEqual(0, 2) [18]\n"
+      "  18: Select(0, 0, 17)\n"
+      "  19: Return(2)\n"
       "BasicBlock 2, pred: 1\n"
       "  20: Exit\n";
 
   const std::string expected_after_cf =
       "BasicBlock 0, succ: 1\n"
-      "  0: ParameterValue [17, 17, 16, 15, 15, 13, 13, 11, 11, 10, 9, 9, 7, 7, 6, 5, 5, 4, 3, 3]\n"
-      "  1: IntConstant [13, 3, 19, 16, 10, 6, 4]\n"
-      "  21: IntConstant [15, 9]\n"
-      "  18: Goto 1\n"
+      "  0: ParameterValue [18, 18, 17, 16, 16, 14, 14, 12, 12, 11, 10, 10, "
+                            "8, 8, 7, 6, 6, 5, 4, 4]\n"
+      "  2: IntConstant [14, 4, 19, 17, 11, 7, 5]\n"
+      "  21: IntConstant [16, 10]\n"
+      "  1: Goto 1\n"
       "BasicBlock 1, pred: 0, succ: 2\n"
-      "  3: Select(0, 0, 1)\n"
-      "  4: Above(0, 1) [5]\n"
-      "  5: Select(0, 0, 4)\n"
-      "  6: AboveOrEqual(1, 0) [7]\n"
-      "  7: Select(0, 0, 6)\n"
-      "  9: Select(0, 0, 21)\n"
-      "  10: Below(1, 0) [11]\n"
-      "  11: Select(0, 0, 10)\n"
-      "  13: Select(0, 0, 1)\n"
-      "  15: Select(0, 0, 21)\n"
-      "  16: BelowOrEqual(0, 1) [17]\n"
-      "  17: Select(0, 0, 16)\n"
-      "  19: Return(1)\n"
+      "  4: Select(0, 0, 2)\n"
+      "  5: Above(0, 2) [6]\n"
+      "  6: Select(0, 0, 5)\n"
+      "  7: AboveOrEqual(2, 0) [8]\n"
+      "  8: Select(0, 0, 7)\n"
+      "  10: Select(0, 0, 21)\n"
+      "  11: Below(2, 0) [12]\n"
+      "  12: Select(0, 0, 11)\n"
+      "  14: Select(0, 0, 2)\n"
+      "  16: Select(0, 0, 21)\n"
+      "  17: BelowOrEqual(0, 2) [18]\n"
+      "  18: Select(0, 0, 17)\n"
+      "  19: Return(2)\n"
       "BasicBlock 2, pred: 1\n"
       "  20: Exit\n";
 
   const std::string expected_after_dce =
       "BasicBlock 0, succ: 1\n"
       "  0: ParameterValue\n"
-      "  1: IntConstant [19]\n"
-      "  18: Goto 1\n"
+      "  2: IntConstant [19]\n"
+      "  1: Goto 1\n"
       "BasicBlock 1, pred: 0, succ: 2\n"
-      "  19: Return(1)\n"
+      "  19: Return(2)\n"
       "BasicBlock 2, pred: 1\n"
       "  20: Exit\n";
 
diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc
index 83e724ba29..04bbd9cb30 100644
--- a/compiler/optimizing/dead_code_elimination_test.cc
+++ b/compiler/optimizing/dead_code_elimination_test.cc
@@ -78,30 +78,30 @@ TEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) {
     Instruction::RETURN_VOID);
 
   std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  3: IntConstant [15, 22, 8]\n"
-    "  5: IntConstant [22, 8]\n"
-    "  19: SuspendCheck\n"
-    "  20: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 5, 2\n"
-    "  8: GreaterThanOrEqual(3, 5) [9]\n"
-    "  9: If(8)\n"
-    "BasicBlock 2, pred: 1, succ: 3\n"
-    "  12: Goto 3\n"
-    "BasicBlock 3, pred: 5, 2, succ: 4\n"
-    "  22: Phi(5, 3) [15]\n"
-    "  15: Add(22, 3)\n"
-    "  17: ReturnVoid\n"
-    "BasicBlock 4, pred: 3\n"
-    "  18: Exit\n"
-    "BasicBlock 5, pred: 1, succ: 3\n"
-    "  21: Goto 3\n";
+      "BasicBlock 0, succ: 1\n"
+      "  6: IntConstant [18, 22, 11]\n"
+      "  8: IntConstant [22, 11]\n"
+      "  4: SuspendCheck\n"
+      "  5: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 5, 2\n"
+      "  11: GreaterThanOrEqual(6, 8) [12]\n"
+      "  12: If(11)\n"
+      "BasicBlock 2, pred: 1, succ: 3\n"
+      "  15: Goto 3\n"
+      "BasicBlock 3, pred: 5, 2, succ: 4\n"
+      "  22: Phi(8, 6) [18]\n"
+      "  18: Add(22, 6)\n"
+      "  20: ReturnVoid\n"
+      "BasicBlock 4, pred: 3\n"
+      "  21: Exit\n"
+      "BasicBlock 5, pred: 1, succ: 3\n"
+      "  0: Goto 3\n";
 
   // Expected difference after dead code elimination.
   diff_t expected_diff = {
-    { "  3: IntConstant [15, 22, 8]\n", "  3: IntConstant [22, 8]\n" },
-    { "  22: Phi(5, 3) [15]\n",         "  22: Phi(5, 3)\n" },
-    { "  15: Add(22, 3)\n",             removed }
+    { "  6: IntConstant [18, 22, 11]\n", "  6: IntConstant [22, 11]\n" },
+    { "  22: Phi(8, 6) [18]\n",          "  22: Phi(8, 6)\n" },
+    { "  18: Add(22, 6)\n",              removed }
   };
   std::string expected_after = Patch(expected_before, expected_diff);
 
@@ -144,37 +144,37 @@ TEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) {
     Instruction::RETURN_VOID);
 
   std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  3: IntConstant [9]\n"
-    "  5: IntConstant [9]\n"
-    "  13: IntConstant [14]\n"
-    "  18: IntConstant [19]\n"
-    "  23: IntConstant [24]\n"
-    "  28: SuspendCheck\n"
-    "  29: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 3\n"
-    "  9: Add(3, 5) [19]\n"
-    "  11: Goto 3\n"
-    "BasicBlock 2, pred: 3, succ: 4\n"
-    "  14: Add(19, 13) [24]\n"
-    "  16: Goto 4\n"
-    "BasicBlock 3, pred: 1, succ: 2\n"
-    "  19: Add(9, 18) [14]\n"
-    "  21: Goto 2\n"
-    "BasicBlock 4, pred: 2, succ: 5\n"
-    "  24: Add(14, 23)\n"
-    "  26: ReturnVoid\n"
-    "BasicBlock 5, pred: 4\n"
-    "  27: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  5: IntConstant [11]\n"
+      "  7: IntConstant [11]\n"
+      "  15: IntConstant [16]\n"
+      "  20: IntConstant [21]\n"
+      "  25: IntConstant [26]\n"
+      "  3: SuspendCheck\n"
+      "  4: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 3\n"
+      "  11: Add(5, 7) [21]\n"
+      "  13: Goto 3\n"
+      "BasicBlock 2, pred: 3, succ: 4\n"
+      "  16: Add(21, 15) [26]\n"
+      "  18: Goto 4\n"
+      "BasicBlock 3, pred: 1, succ: 2\n"
+      "  21: Add(11, 20) [16]\n"
+      "  23: Goto 2\n"
+      "BasicBlock 4, pred: 2, succ: 5\n"
+      "  26: Add(16, 25)\n"
+      "  28: ReturnVoid\n"
+      "BasicBlock 5, pred: 4\n"
+      "  29: Exit\n";
 
   std::string expected_after =
-    "BasicBlock 0, succ: 1\n"
-    "  28: SuspendCheck\n"
-    "  29: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 5\n"
-    "  26: ReturnVoid\n"
-    "BasicBlock 5, pred: 1\n"
-    "  27: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  3: SuspendCheck\n"
+      "  4: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 5\n"
+      "  28: ReturnVoid\n"
+      "BasicBlock 5, pred: 1\n"
+      "  29: Exit\n";
 
   TestCode(data, expected_before, expected_after);
 }
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index c790d013b5..9ea4b2dab4 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -27,6 +27,21 @@
 
 namespace art {
 
+static bool IsAllowedToJumpToExitBlock(HInstruction* instruction) {
+  return instruction->IsThrow() || instruction->IsReturn() || instruction->IsReturnVoid();
+}
+
+static bool IsExitTryBoundaryIntoExitBlock(HBasicBlock* block) {
+  if (!block->IsSingleTryBoundary()) {
+    return false;
+  }
+
+  HTryBoundary* boundary = block->GetLastInstruction()->AsTryBoundary();
+  return block->GetPredecessors().size() == 1u &&
+         boundary->GetNormalFlowSuccessor()->IsExitBlock() &&
+         !boundary->IsEntry();
+}
+
 void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
   current_block_ = block;
 
@@ -85,28 +100,17 @@ void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
                           block->GetBlockId()));
   }
 
-  // Ensure that only Return(Void) and Throw jump to Exit. An exiting
-  // TryBoundary may be between a Throw and the Exit if the Throw is in a try.
+  // Ensure that only Return(Void) and Throw jump to Exit. An exiting TryBoundary
+  // may be between the instructions if the Throw/Return(Void) is in a try block.
   if (block->IsExitBlock()) {
     for (HBasicBlock* predecessor : block->GetPredecessors()) {
-      if (predecessor->IsSingleTryBoundary()
-          && !predecessor->GetLastInstruction()->AsTryBoundary()->IsEntry()) {
-        HBasicBlock* real_predecessor = predecessor->GetSinglePredecessor();
-        HInstruction* last_instruction = real_predecessor->GetLastInstruction();
-        if (!last_instruction->IsThrow()) {
-          AddError(StringPrintf("Unexpected TryBoundary between %s:%d and Exit.",
-                                last_instruction->DebugName(),
-                                last_instruction->GetId()));
-        }
-      } else {
-        HInstruction* last_instruction = predecessor->GetLastInstruction();
-        if (!last_instruction->IsReturn()
-            && !last_instruction->IsReturnVoid()
-            && !last_instruction->IsThrow()) {
-          AddError(StringPrintf("Unexpected instruction %s:%d jumps into the exit block.",
-                                last_instruction->DebugName(),
-                                last_instruction->GetId()));
-        }
+      HInstruction* last_instruction = IsExitTryBoundaryIntoExitBlock(predecessor) ?
+        predecessor->GetSinglePredecessor()->GetLastInstruction() :
+        predecessor->GetLastInstruction();
+      if (!IsAllowedToJumpToExitBlock(last_instruction)) {
+        AddError(StringPrintf("Unexpected instruction %s:%d jumps into the exit block.",
+                              last_instruction->DebugName(),
+                              last_instruction->GetId()));
       }
     }
   }
@@ -176,16 +180,15 @@ void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
   // predecessors). Exceptional edges are synthesized and hence
   // not accounted for.
   if (block->GetSuccessors().size() > 1) {
-    for (HBasicBlock* successor : block->GetNormalSuccessors()) {
-      if (successor->IsExitBlock() &&
-          block->IsSingleTryBoundary() &&
-          block->GetPredecessors().size() == 1u &&
-          block->GetSinglePredecessor()->GetLastInstruction()->IsThrow()) {
-        // Allowed critical edge Throw->TryBoundary->Exit.
-      } else if (successor->GetPredecessors().size() > 1) {
-        AddError(StringPrintf("Critical edge between blocks %d and %d.",
-                              block->GetBlockId(),
-                              successor->GetBlockId()));
+    if (IsExitTryBoundaryIntoExitBlock(block)) {
+      // Allowed critical edge (Throw/Return/ReturnVoid)->TryBoundary->Exit.
+    } else {
+      for (HBasicBlock* successor : block->GetNormalSuccessors()) {
+        if (successor->GetPredecessors().size() > 1) {
+          AddError(StringPrintf("Critical edge between blocks %d and %d.",
+                                block->GetBlockId(),
+                                successor->GetBlockId()));
+        }
       }
     }
   }
@@ -505,7 +508,8 @@ void GraphChecker::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
 
 void GraphChecker::VisitReturn(HReturn* ret) {
   VisitInstruction(ret);
-  if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
+  HBasicBlock* successor = ret->GetBlock()->GetSingleSuccessor();
+  if (!successor->IsExitBlock() && !IsExitTryBoundaryIntoExitBlock(successor)) {
     AddError(StringPrintf("%s:%d does not jump to the exit block.",
                           ret->DebugName(),
                           ret->GetId()));
@@ -514,7 +518,8 @@ void GraphChecker::VisitReturn(HReturn* ret) {
 
 void GraphChecker::VisitReturnVoid(HReturnVoid* ret) {
   VisitInstruction(ret);
-  if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
+  HBasicBlock* successor = ret->GetBlock()->GetSingleSuccessor();
+  if (!successor->IsExitBlock() && !IsExitTryBoundaryIntoExitBlock(successor)) {
     AddError(StringPrintf("%s:%d does not jump to the exit block.",
                           ret->DebugName(),
                           ret->GetId()));
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index fce9ab8b85..e3172df7f9 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -1066,12 +1066,13 @@ bool HInliner::TryBuildAndInlineHelper(HInvoke* invoke_instruction,
                         &dex_compilation_unit,
                         &outer_compilation_unit_,
                         resolved_method->GetDexFile(),
+                        *code_item,
                         compiler_driver_,
                         &inline_stats,
                         resolved_method->GetQuickenedInfo(),
                         dex_cache);
 
-  if (builder.BuildGraph(*code_item, handles_) != kAnalysisSuccess) {
+  if (builder.BuildGraph(handles_) != kAnalysisSuccess) {
     VLOG(compiler) << "Method " << PrettyMethod(method_index, callee_dex_file)
                    << " could not be built, so cannot be inlined";
     return false;
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 950448136d..9f448af73a 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -134,46 +134,44 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
       if (block->IsExitBlock()) {
         SetExitBlock(nullptr);
       }
+      // Mark the block as removed. This is used by the HGraphBuilder to discard
+      // the block as a branch target.
+      block->SetGraph(nullptr);
     }
   }
 }
 
 GraphAnalysisResult HGraph::BuildDominatorTree() {
-  // (1) Simplify the CFG so that catch blocks have only exceptional incoming
-  //     edges. This invariant simplifies building SSA form because Phis cannot
-  //     collect both normal- and exceptional-flow values at the same time.
-  SimplifyCatchBlocks();
-
   ArenaBitVector visited(arena_, blocks_.size(), false, kArenaAllocGraphBuilder);
 
-  // (2) Find the back edges in the graph doing a DFS traversal.
+  // (1) Find the back edges in the graph doing a DFS traversal.
   FindBackEdges(&visited);
 
-  // (3) Remove instructions and phis from blocks not visited during
+  // (2) Remove instructions and phis from blocks not visited during
   //     the initial DFS as users from other instructions, so that
   //     users can be safely removed before uses later.
   RemoveInstructionsAsUsersFromDeadBlocks(visited);
 
-  // (4) Remove blocks not visited during the initial DFS.
+  // (3) Remove blocks not visited during the initial DFS.
   //     Step (5) requires dead blocks to be removed from the
   //     predecessors list of live blocks.
   RemoveDeadBlocks(visited);
 
-  // (5) Simplify the CFG now, so that we don't need to recompute
+  // (4) Simplify the CFG now, so that we don't need to recompute
   //     dominators and the reverse post order.
   SimplifyCFG();
 
-  // (6) Compute the dominance information and the reverse post order.
+  // (5) Compute the dominance information and the reverse post order.
   ComputeDominanceInformation();
 
-  // (7) Analyze loops discovered through back edge analysis, and
+  // (6) Analyze loops discovered through back edge analysis, and
   //     set the loop information on each block.
   GraphAnalysisResult result = AnalyzeLoops();
   if (result != kAnalysisSuccess) {
     return result;
   }
 
-  // (8) Precompute per-block try membership before entering the SSA builder,
+  // (7) Precompute per-block try membership before entering the SSA builder,
   //     which needs the information to build catch block phis from values of
   //     locals at throwing instructions inside try blocks.
   ComputeTryBlockInformation();
@@ -325,7 +323,11 @@ void HGraph::SimplifyLoop(HBasicBlock* header) {
   // generate the suspend check at the back edge, but needs to be careful with
   // loop phi spill slots (which are not written to at back edge).
   HInstruction* first_instruction = header->GetFirstInstruction();
-  if (!first_instruction->IsSuspendCheck()) {
+  if (first_instruction == nullptr) {
+    HSuspendCheck* check = new (arena_) HSuspendCheck(header->GetDexPc());
+    header->AddInstruction(check);
+    first_instruction = check;
+  } else if (!first_instruction->IsSuspendCheck()) {
     HSuspendCheck* check = new (arena_) HSuspendCheck(header->GetDexPc());
     header->InsertInstructionBefore(check, first_instruction);
     first_instruction = check;
@@ -333,75 +335,6 @@ void HGraph::SimplifyLoop(HBasicBlock* header) {
   info->SetSuspendCheck(first_instruction->AsSuspendCheck());
 }
 
-static bool CheckIfPredecessorAtIsExceptional(const HBasicBlock& block, size_t pred_idx) {
-  HBasicBlock* predecessor = block.GetPredecessors()[pred_idx];
-  if (!predecessor->EndsWithTryBoundary()) {
-    // Only edges from HTryBoundary can be exceptional.
-    return false;
-  }
-  HTryBoundary* try_boundary = predecessor->GetLastInstruction()->AsTryBoundary();
-  if (try_boundary->GetNormalFlowSuccessor() == &block) {
-    // This block is the normal-flow successor of `try_boundary`, but it could
-    // also be one of its exception handlers if catch blocks have not been
-    // simplified yet. Predecessors are unordered, so we will consider the first
-    // occurrence to be the normal edge and a possible second occurrence to be
-    // the exceptional edge.
-    return !block.IsFirstIndexOfPredecessor(predecessor, pred_idx);
-  } else {
-    // This is not the normal-flow successor of `try_boundary`, hence it must be
-    // one of its exception handlers.
-    DCHECK(try_boundary->HasExceptionHandler(block));
-    return true;
-  }
-}
-
-void HGraph::SimplifyCatchBlocks() {
-  // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators
-  // can be invalidated. We remember the initial size to avoid iterating over the new blocks.
-  for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) {
-    HBasicBlock* catch_block = blocks_[block_id];
-    if (catch_block == nullptr || !catch_block->IsCatchBlock()) {
-      continue;
-    }
-
-    bool exceptional_predecessors_only = true;
-    for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) {
-      if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) {
-        exceptional_predecessors_only = false;
-        break;
-      }
-    }
-
-    if (!exceptional_predecessors_only) {
-      // Catch block has normal-flow predecessors and needs to be simplified.
-      // Splitting the block before its first instruction moves all its
-      // instructions into `normal_block` and links the two blocks with a Goto.
-      // Afterwards, incoming normal-flow edges are re-linked to `normal_block`,
-      // leaving `catch_block` with the exceptional edges only.
-      //
-      // Note that catch blocks with normal-flow predecessors cannot begin with
-      // a move-exception instruction, as guaranteed by the verifier. However,
-      // trivially dead predecessors are ignored by the verifier and such code
-      // has not been removed at this stage. We therefore ignore the assumption
-      // and rely on GraphChecker to enforce it after initial DCE is run (b/25492628).
-      HBasicBlock* normal_block = catch_block->SplitCatchBlockAfterMoveException();
-      if (normal_block == nullptr) {
-        // Catch block is either empty or only contains a move-exception. It must
-        // therefore be dead and will be removed during initial DCE. Do nothing.
-        DCHECK(!catch_block->EndsWithControlFlowInstruction());
-      } else {
-        // Catch block was split. Re-link normal-flow edges to the new block.
-        for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) {
-          if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) {
-            catch_block->GetPredecessors()[j]->ReplaceSuccessor(catch_block, normal_block);
-            --j;
-          }
-        }
-      }
-    }
-  }
-}
-
 void HGraph::ComputeTryBlockInformation() {
   // Iterate in reverse post order to propagate try membership information from
   // predecessors to their successors.
@@ -447,10 +380,9 @@ void HGraph::SimplifyCFG() {
         HBasicBlock* successor = normal_successors[j];
         DCHECK(!successor->IsCatchBlock());
         if (successor == exit_block_) {
-          // Throw->TryBoundary->Exit. Special case which we do not want to split
-          // because Goto->Exit is not allowed.
+          // (Throw/Return/ReturnVoid)->TryBoundary->Exit. Special case which we
+          // do not want to split because Goto->Exit is not allowed.
           DCHECK(block->IsSingleTryBoundary());
-          DCHECK(block->GetSinglePredecessor()->GetLastInstruction()->IsThrow());
         } else if (successor->GetPredecessors().size() > 1) {
           SplitCriticalEdge(block, successor);
           // SplitCriticalEdge could have invalidated the `normal_successors`
@@ -463,8 +395,10 @@ void HGraph::SimplifyCFG() {
     }
     if (block->IsLoopHeader()) {
       SimplifyLoop(block);
-    } else if (!block->IsEntryBlock() && block->GetFirstInstruction()->IsSuspendCheck()) {
-      // We are being called by the dead code elimination pass, and what used to be
+    } else if (!block->IsEntryBlock() &&
+               block->GetFirstInstruction() != nullptr &&
+               block->GetFirstInstruction()->IsSuspendCheck()) {
+      // We are being called by the dead code elimiation pass, and what used to be
       // a loop got dismantled. Just remove the suspend check.
       block->RemoveInstruction(block->GetFirstInstruction());
     }
@@ -502,12 +436,25 @@ void HLoopInformation::Dump(std::ostream& os) {
 }
 
 void HGraph::InsertConstant(HConstant* constant) {
-  // New constants are inserted before the final control-flow instruction
-  // of the graph, or at its end if called from the graph builder.
-  if (entry_block_->EndsWithControlFlowInstruction()) {
-    entry_block_->InsertInstructionBefore(constant, entry_block_->GetLastInstruction());
-  } else {
+  // New constants are inserted before the SuspendCheck at the bottom of the
+  // entry block. Note that this method can be called from the graph builder and
+  // the entry block therefore may not end with SuspendCheck->Goto yet.
+  HInstruction* insert_before = nullptr;
+
+  HInstruction* gota = entry_block_->GetLastInstruction();
+  if (gota != nullptr && gota->IsGoto()) {
+    HInstruction* suspend_check = gota->GetPrevious();
+    if (suspend_check != nullptr && suspend_check->IsSuspendCheck()) {
+      insert_before = suspend_check;
+    } else {
+      insert_before = gota;
+    }
+  }
+
+  if (insert_before == nullptr) {
     entry_block_->AddInstruction(constant);
+  } else {
+    entry_block_->InsertInstructionBefore(constant, insert_before);
   }
 }
 
@@ -1404,34 +1351,6 @@ HBasicBlock* HBasicBlock::CreateImmediateDominator() {
   return new_block;
 }
 
-HBasicBlock* HBasicBlock::SplitCatchBlockAfterMoveException() {
-  DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented.";
-  DCHECK(IsCatchBlock()) << "This method is intended for catch blocks only.";
-
-  HInstruction* first_insn = GetFirstInstruction();
-  HInstruction* split_before = nullptr;
-
-  if (first_insn != nullptr && first_insn->IsLoadException()) {
-    // Catch block starts with a LoadException. Split the block after
-    // the StoreLocal and ClearException which must come after the load.
-    DCHECK(first_insn->GetNext()->IsStoreLocal());
-    DCHECK(first_insn->GetNext()->GetNext()->IsClearException());
-    split_before = first_insn->GetNext()->GetNext()->GetNext();
-  } else {
-    // Catch block does not load the exception. Split at the beginning
-    // to create an empty catch block.
-    split_before = first_insn;
-  }
-
-  if (split_before == nullptr) {
-    // Catch block has no instructions after the split point (must be dead).
-    // Do not split it but rather signal error by returning nullptr.
-    return nullptr;
-  } else {
-    return SplitBefore(split_before);
-  }
-}
-
 HBasicBlock* HBasicBlock::SplitBeforeForInlining(HInstruction* cursor) {
   DCHECK_EQ(cursor->GetBlock(), this);
 
@@ -1910,6 +1829,7 @@ void HGraph::DeleteDeadEmptyBlock(HBasicBlock* block) {
 
   RemoveElement(reverse_post_order_, block);
   blocks_[block->GetBlockId()] = nullptr;
+  block->SetGraph(nullptr);
 }
 
 void HGraph::UpdateLoopAndTryInformationOfNewBlock(HBasicBlock* block,
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 9425ef3267..8a2e83a9ef 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -26,7 +26,6 @@
 #include "base/arena_object.h"
 #include "base/stl_util.h"
 #include "dex/compiler_enums.h"
-#include "dex_instruction-inl.h"
 #include "entrypoints/quick/quick_entrypoints_enum.h"
 #include "handle.h"
 #include "handle_scope.h"
@@ -101,6 +100,7 @@ enum IfCondition {
 };
 
 enum GraphAnalysisResult {
+  kAnalysisSkipped,
   kAnalysisInvalidBytecode,
   kAnalysisFailThrowCatchLoop,
   kAnalysisFailAmbiguousArrayOp,
@@ -999,15 +999,6 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> {
   // Similar to `SplitBeforeForInlining` but does it after `cursor`.
   HBasicBlock* SplitAfterForInlining(HInstruction* cursor);
 
-  // Split catch block into two blocks after the original move-exception bytecode
-  // instruction, or at the beginning if not present. Returns the newly created,
-  // latter block, or nullptr if such block could not be created (must be dead
-  // in that case). Note that this method just updates raw block information,
-  // like predecessors, successors, dominators, and instruction list. It does not
-  // update the graph, reverse post order, loop information, nor make sure the
-  // blocks are consistent (for example ending with a control flow instruction).
-  HBasicBlock* SplitCatchBlockAfterMoveException();
-
   // Merge `other` at the end of `this`. Successors and dominated blocks of
   // `other` are changed to be successors and dominated blocks of `this`. Note
   // that this method does not update the graph, reverse post order, loop
@@ -5415,7 +5406,7 @@ class HBoundsCheck : public HExpression<2> {
 
 class HSuspendCheck : public HTemplateInstruction<0> {
  public:
-  explicit HSuspendCheck(uint32_t dex_pc)
+  explicit HSuspendCheck(uint32_t dex_pc = kNoDexPc)
       : HTemplateInstruction(SideEffects::CanTriggerGC(), dex_pc), slow_path_(nullptr) {}
 
   bool NeedsEnvironment() const OVERRIDE {
@@ -6707,74 +6698,6 @@ inline bool IsSameDexFile(const DexFile& lhs, const DexFile& rhs) {
   FOR_EACH_CONCRETE_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
 #undef INSTRUCTION_TYPE_CHECK
 
-class SwitchTable : public ValueObject {
- public:
-  SwitchTable(const Instruction& instruction, uint32_t dex_pc, bool sparse)
-      : instruction_(instruction), dex_pc_(dex_pc), sparse_(sparse) {
-    int32_t table_offset = instruction.VRegB_31t();
-    const uint16_t* table = reinterpret_cast<const uint16_t*>(&instruction) + table_offset;
-    if (sparse) {
-      CHECK_EQ(table[0], static_cast<uint16_t>(Instruction::kSparseSwitchSignature));
-    } else {
-      CHECK_EQ(table[0], static_cast<uint16_t>(Instruction::kPackedSwitchSignature));
-    }
-    num_entries_ = table[1];
-    values_ = reinterpret_cast<const int32_t*>(&table[2]);
-  }
-
-  uint16_t GetNumEntries() const {
-    return num_entries_;
-  }
-
-  void CheckIndex(size_t index) const {
-    if (sparse_) {
-      // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order.
-      DCHECK_LT(index, 2 * static_cast<size_t>(num_entries_));
-    } else {
-      // In a packed table, we have the starting key and num_entries_ values.
-      DCHECK_LT(index, 1 + static_cast<size_t>(num_entries_));
-    }
-  }
-
-  int32_t GetEntryAt(size_t index) const {
-    CheckIndex(index);
-    return values_[index];
-  }
-
-  uint32_t GetDexPcForIndex(size_t index) const {
-    CheckIndex(index);
-    return dex_pc_ +
-        (reinterpret_cast<const int16_t*>(values_ + index) -
-         reinterpret_cast<const int16_t*>(&instruction_));
-  }
-
-  // Index of the first value in the table.
-  size_t GetFirstValueIndex() const {
-    if (sparse_) {
-      // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order.
-      return num_entries_;
-    } else {
-      // In a packed table, we have the starting key and num_entries_ values.
-      return 1;
-    }
-  }
-
- private:
-  const Instruction& instruction_;
-  const uint32_t dex_pc_;
-
-  // Whether this is a sparse-switch table (or a packed-switch one).
-  const bool sparse_;
-
-  // This can't be const as it needs to be computed off of the given instruction, and complicated
-  // expressions in the initializer list seemed very ugly.
-  uint16_t num_entries_;
-
-  const int32_t* values_;
-
-  DISALLOW_COPY_AND_ASSIGN(SwitchTable);
-};
-
 // Create space in `blocks` for adding `number_of_new_blocks` entries
 // starting at location `at`. Blocks after `at` are moved accordingly.
 inline void MakeRoomFor(ArenaVector<HBasicBlock*>* blocks,
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 886c9e2ad4..20a666128f 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -727,14 +727,19 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* arena,
                             &dex_compilation_unit,
                             &dex_compilation_unit,
                             &dex_file,
+                            *code_item,
                             compiler_driver,
                             compilation_stats_.get(),
                             interpreter_metadata,
                             dex_cache);
-      GraphAnalysisResult result = builder.BuildGraph(*code_item, &handles);
+      GraphAnalysisResult result = builder.BuildGraph(&handles);
       if (result != kAnalysisSuccess) {
         switch (result) {
+          case kAnalysisSkipped:
+            MaybeRecordStat(MethodCompilationStat::kNotCompiledSkipped);
+            break;
           case kAnalysisInvalidBytecode:
+            MaybeRecordStat(MethodCompilationStat::kNotCompiledInvalidBytecode);
             break;
           case kAnalysisFailThrowCatchLoop:
             MaybeRecordStat(MethodCompilationStat::kNotCompiledThrowCatchLoop);
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index 3717926a97..9cc6ea45d0 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -38,7 +38,8 @@ enum MethodCompilationStat {
   kRemovedCheckedCast,
   kRemovedDeadInstruction,
   kRemovedNullCheck,
-  kNotCompiledBranchOutsideMethodCode,
+  kNotCompiledSkipped,
+  kNotCompiledInvalidBytecode,
   kNotCompiledThrowCatchLoop,
   kNotCompiledAmbiguousArrayOp,
   kNotCompiledHugeMethod,
@@ -115,7 +116,8 @@ class OptimizingCompilerStats {
       case kRemovedCheckedCast: name = "RemovedCheckedCast"; break;
       case kRemovedDeadInstruction: name = "RemovedDeadInstruction"; break;
       case kRemovedNullCheck: name = "RemovedNullCheck"; break;
-      case kNotCompiledBranchOutsideMethodCode: name = "NotCompiledBranchOutsideMethodCode"; break;
+      case kNotCompiledSkipped: name = "NotCompiledSkipped"; break;
+      case kNotCompiledInvalidBytecode: name = "NotCompiledInvalidBytecode"; break;
       case kNotCompiledThrowCatchLoop : name = "NotCompiledThrowCatchLoop"; break;
       case kNotCompiledAmbiguousArrayOp : name = "NotCompiledAmbiguousArrayOp"; break;
       case kNotCompiledHugeMethod : name = "NotCompiledHugeMethod"; break;
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index 0ca7305d13..b140125d14 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -91,8 +91,8 @@ inline HGraph* CreateCFG(ArenaAllocator* allocator,
   {
     ScopedObjectAccess soa(Thread::Current());
     StackHandleScopeCollection handles(soa.Self());
-    HGraphBuilder builder(graph, return_type);
-    bool graph_built = (builder.BuildGraph(*item, &handles) == kAnalysisSuccess);
+    HGraphBuilder builder(graph, *item, return_type);
+    bool graph_built = (builder.BuildGraph(&handles) == kAnalysisSuccess);
     return graph_built ? graph : nullptr;
   }
 }
@@ -109,7 +109,8 @@ inline std::string Patch(const std::string& original, const diff_t& diff) {
   std::string result = original;
   for (const auto& p : diff) {
     std::string::size_type pos = result.find(p.first);
-    EXPECT_NE(pos, std::string::npos);
+    DCHECK_NE(pos, std::string::npos)
+        << "Could not find: \"" << p.first << "\" in \"" << result << "\"";
     result.replace(pos, p.first.size(), p.second);
   }
   return result;
diff --git a/compiler/optimizing/pretty_printer_test.cc b/compiler/optimizing/pretty_printer_test.cc
index d5b95d284a..a444688261 100644
--- a/compiler/optimizing/pretty_printer_test.cc
+++ b/compiler/optimizing/pretty_printer_test.cc
@@ -44,27 +44,27 @@ TEST_F(PrettyPrinterTest, ReturnVoid) {
 
   const char* expected =
       "BasicBlock 0, succ: 1\n"
-      "  2: SuspendCheck\n"
-      "  3: Goto 1\n"
+      "  0: SuspendCheck\n"
+      "  1: Goto 1\n"
       "BasicBlock 1, pred: 0, succ: 2\n"
-      "  0: ReturnVoid\n"
+      "  2: ReturnVoid\n"
       "BasicBlock 2, pred: 1\n"
-      "  1: Exit\n";
+      "  3: Exit\n";
 
   TestCode(data, expected);
 }
 
 TEST_F(PrettyPrinterTest, CFG1) {
   const char* expected =
-    "BasicBlock 0, succ: 1\n"
-    "  3: SuspendCheck\n"
-    "  4: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  0: Goto 2\n"
-    "BasicBlock 2, pred: 1, succ: 3\n"
-    "  1: ReturnVoid\n"
-    "BasicBlock 3, pred: 2\n"
-    "  2: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  0: SuspendCheck\n"
+      "  1: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 2\n"
+      "  2: Goto 2\n"
+      "BasicBlock 2, pred: 1, succ: 3\n"
+      "  3: ReturnVoid\n"
+      "BasicBlock 3, pred: 2\n"
+      "  4: Exit\n";
 
   const uint16_t data[] =
     ZERO_REGISTER_CODE_ITEM(
@@ -76,17 +76,17 @@ TEST_F(PrettyPrinterTest, CFG1) {
 
 TEST_F(PrettyPrinterTest, CFG2) {
   const char* expected =
-    "BasicBlock 0, succ: 1\n"
-    "  4: SuspendCheck\n"
-    "  5: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  0: Goto 2\n"
-    "BasicBlock 2, pred: 1, succ: 3\n"
-    "  1: Goto 3\n"
-    "BasicBlock 3, pred: 2, succ: 4\n"
-    "  2: ReturnVoid\n"
-    "BasicBlock 4, pred: 3\n"
-    "  3: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  0: SuspendCheck\n"
+      "  1: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 2\n"
+      "  2: Goto 2\n"
+      "BasicBlock 2, pred: 1, succ: 3\n"
+      "  3: Goto 3\n"
+      "BasicBlock 3, pred: 2, succ: 4\n"
+      "  4: ReturnVoid\n"
+      "BasicBlock 4, pred: 3\n"
+      "  5: Exit\n";
 
   const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
     Instruction::GOTO | 0x100,
@@ -98,17 +98,17 @@ TEST_F(PrettyPrinterTest, CFG2) {
 
 TEST_F(PrettyPrinterTest, CFG3) {
   const char* expected =
-    "BasicBlock 0, succ: 1\n"
-    "  4: SuspendCheck\n"
-    "  5: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 3\n"
-    "  0: Goto 3\n"
-    "BasicBlock 2, pred: 3, succ: 4\n"
-    "  1: ReturnVoid\n"
-    "BasicBlock 3, pred: 1, succ: 2\n"
-    "  2: Goto 2\n"
-    "BasicBlock 4, pred: 2\n"
-    "  3: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  0: SuspendCheck\n"
+      "  1: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 3\n"
+      "  2: Goto 3\n"
+      "BasicBlock 2, pred: 3, succ: 4\n"
+      "  3: ReturnVoid\n"
+      "BasicBlock 3, pred: 1, succ: 2\n"
+      "  4: Goto 2\n"
+      "BasicBlock 4, pred: 2\n"
+      "  5: Exit\n";
 
   const uint16_t data1[] = ZERO_REGISTER_CODE_ITEM(
     Instruction::GOTO | 0x200,
@@ -134,14 +134,14 @@ TEST_F(PrettyPrinterTest, CFG3) {
 
 TEST_F(PrettyPrinterTest, CFG4) {
   const char* expected =
-    "BasicBlock 0, succ: 3\n"
-    "  2: SuspendCheck\n"
-    "  3: Goto 3\n"
-    "BasicBlock 1, pred: 3, 1, succ: 1\n"
-    "  5: SuspendCheck\n"
-    "  0: Goto 1\n"
-    "BasicBlock 3, pred: 0, succ: 1\n"
-    "  4: Goto 1\n";
+      "BasicBlock 0, succ: 3\n"
+      "  2: SuspendCheck\n"
+      "  3: Goto 3\n"
+      "BasicBlock 1, pred: 3, 1, succ: 1\n"
+      "  1: SuspendCheck\n"
+      "  4: Goto 1\n"
+      "BasicBlock 3, pred: 0, succ: 1\n"
+      "  0: Goto 1\n";
 
   const uint16_t data1[] = ZERO_REGISTER_CODE_ITEM(
     Instruction::NOP,
@@ -157,13 +157,13 @@ TEST_F(PrettyPrinterTest, CFG4) {
 
 TEST_F(PrettyPrinterTest, CFG5) {
   const char* expected =
-    "BasicBlock 0, succ: 1\n"
-    "  3: SuspendCheck\n"
-    "  4: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 3\n"
-    "  0: ReturnVoid\n"
-    "BasicBlock 3, pred: 1\n"
-    "  2: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  0: SuspendCheck\n"
+      "  1: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 3\n"
+      "  2: ReturnVoid\n"
+      "BasicBlock 3, pred: 1\n"
+      "  3: Exit\n";
 
   const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
     Instruction::RETURN_VOID,
@@ -175,21 +175,21 @@ TEST_F(PrettyPrinterTest, CFG5) {
 
 TEST_F(PrettyPrinterTest, CFG6) {
   const char* expected =
-    "BasicBlock 0, succ: 1\n"
-    "  1: IntConstant [5, 5]\n"
-    "  10: SuspendCheck\n"
-    "  11: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 5, 2\n"
-    "  5: Equal(1, 1) [6]\n"
-    "  6: If(5)\n"
-    "BasicBlock 2, pred: 1, succ: 3\n"
-    "  7: Goto 3\n"
-    "BasicBlock 3, pred: 5, 2, succ: 4\n"
-    "  8: ReturnVoid\n"
-    "BasicBlock 4, pred: 3\n"
-    "  9: Exit\n"
-    "BasicBlock 5, pred: 1, succ: 3\n"
-    "  12: Goto 3\n";
+      "BasicBlock 0, succ: 1\n"
+      "  4: IntConstant [8, 8]\n"
+      "  2: SuspendCheck\n"
+      "  3: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 5, 2\n"
+      "  8: Equal(4, 4) [9]\n"
+      "  9: If(8)\n"
+      "BasicBlock 2, pred: 1, succ: 3\n"
+      "  10: Goto 3\n"
+      "BasicBlock 3, pred: 5, 2, succ: 4\n"
+      "  11: ReturnVoid\n"
+      "BasicBlock 4, pred: 3\n"
+      "  12: Exit\n"
+      "BasicBlock 5, pred: 1, succ: 3\n"
+      "  0: Goto 3\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -202,22 +202,22 @@ TEST_F(PrettyPrinterTest, CFG6) {
 
 TEST_F(PrettyPrinterTest, CFG7) {
   const char* expected =
-    "BasicBlock 0, succ: 1\n"
-    "  1: IntConstant [5, 5]\n"
-    "  10: SuspendCheck\n"
-    "  11: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 5, 6\n"
-    "  5: Equal(1, 1) [6]\n"
-    "  6: If(5)\n"
-    "BasicBlock 2, pred: 6, 3, succ: 3\n"
-    "  7: Goto 3\n"
-    "BasicBlock 3, pred: 5, 2, succ: 2\n"
-    "  14: SuspendCheck\n"
-    "  8: Goto 2\n"
-    "BasicBlock 5, pred: 1, succ: 3\n"
-    "  12: Goto 3\n"
-    "BasicBlock 6, pred: 1, succ: 2\n"
-    "  13: Goto 2\n";
+      "BasicBlock 0, succ: 1\n"
+      "  6: IntConstant [10, 10]\n"
+      "  4: SuspendCheck\n"
+      "  5: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 5, 6\n"
+      "  10: Equal(6, 6) [11]\n"
+      "  11: If(10)\n"
+      "BasicBlock 2, pred: 6, 3, succ: 3\n"
+      "  12: Goto 3\n"
+      "BasicBlock 3, pred: 5, 2, succ: 2\n"
+      "  2: SuspendCheck\n"
+      "  13: Goto 2\n"
+      "BasicBlock 5, pred: 1, succ: 3\n"
+      "  0: Goto 3\n"
+      "BasicBlock 6, pred: 1, succ: 2\n"
+      "  1: Goto 2\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -230,14 +230,14 @@ TEST_F(PrettyPrinterTest, CFG7) {
 
 TEST_F(PrettyPrinterTest, IntConstant) {
   const char* expected =
-    "BasicBlock 0, succ: 1\n"
-    "  1: IntConstant\n"
-    "  5: SuspendCheck\n"
-    "  6: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  3: ReturnVoid\n"
-    "BasicBlock 2, pred: 1\n"
-    "  4: Exit\n";
+      "BasicBlock 0, succ: 1\n"
+      "  3: IntConstant\n"
+      "  1: SuspendCheck\n"
+      "  2: Goto 1\n"
+      "BasicBlock 1, pred: 0, succ: 2\n"
+      "  5: ReturnVoid\n"
+      "BasicBlock 2, pred: 1\n"
+      "  6: Exit\n";
 
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 294d00f8e2..5a05256628 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -16,6 +16,7 @@
 
 #include "ssa_builder.h"
 
+#include "bytecode_utils.h"
 #include "nodes.h"
 #include "reference_type_propagation.h"
 #include "ssa_phi_elimination.h"
@@ -627,7 +628,6 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
       // Make sure there was at least one throwing instruction which initialized
       // locals (guaranteed by HGraphBuilder) and that all try blocks have been
       // visited already (from HTryBoundary scoping and reverse post order).
-      bool throwing_instruction_found = false;
       bool catch_block_visited = false;
       for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
         HBasicBlock* current = it.Current();
@@ -636,10 +636,10 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
         } else if (current->IsTryBlock() &&
                    current->GetTryCatchInformation()->GetTryEntry().HasExceptionHandler(*block)) {
           DCHECK(!catch_block_visited) << "Catch block visited before its try block.";
-          throwing_instruction_found |= current->HasThrowingInstructions();
         }
       }
-      DCHECK(throwing_instruction_found) << "No instructions throwing into a live catch block.";
+      DCHECK_EQ(current_locals_->size(), GetGraph()->GetNumberOfVRegs())
+          << "No instructions throwing into a live catch block.";
     }
   } else if (block->IsLoopHeader()) {
     // If the block is a loop header, we know we only have visited the pre header
@@ -899,6 +899,27 @@ void SsaBuilder::VisitStoreLocal(HStoreLocal* store) {
   store->GetBlock()->RemoveInstruction(store);
 }
 
+bool SsaBuilder::IsFirstAtThrowingDexPc(HInstruction* instruction) const {
+  uint32_t dex_pc = instruction->GetDexPc();
+  if (dex_pc == kNoDexPc) {
+    return false;
+  }
+
+  // Needs to be the first HInstruction with this dex_pc.
+  HInstruction* previous = instruction->GetPrevious();
+  if (previous != nullptr && previous->GetDexPc() == dex_pc) {
+    return false;
+  }
+
+  if (instruction->IsControlFlow() && !instruction->IsThrow()) {
+    // Special-case non-throwing control-flow HInstruction because artifically
+    // created ones are given dex_pc of the nearest bytecode instructions.
+    return false;
+  }
+
+  return IsThrowingDexInstruction(GetDexInstructionAt(code_item_, dex_pc));
+}
+
 void SsaBuilder::VisitInstruction(HInstruction* instruction) {
   if (instruction->NeedsEnvironment()) {
     HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment(
@@ -914,7 +935,7 @@ void SsaBuilder::VisitInstruction(HInstruction* instruction) {
   }
 
   // If in a try block, propagate values of locals into catch blocks.
-  if (instruction->CanThrowIntoCatchBlock()) {
+  if (instruction->GetBlock()->IsTryBlock() && IsFirstAtThrowingDexPc(instruction)) {
     const HTryBoundary& try_entry =
         instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry();
     for (HBasicBlock* catch_block : try_entry.GetExceptionHandlers()) {
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 2dae9c2de0..83da3781b4 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -49,8 +49,9 @@ static constexpr int kDefaultNumberOfLoops = 2;
  */
 class SsaBuilder : public HGraphVisitor {
  public:
-  SsaBuilder(HGraph* graph, StackHandleScopeCollection* handles)
+  SsaBuilder(HGraph* graph, const DexFile::CodeItem& code_item, StackHandleScopeCollection* handles)
       : HGraphVisitor(graph),
+        code_item_(code_item),
         handles_(handles),
         agets_fixed_(false),
         current_locals_(nullptr),
@@ -105,6 +106,11 @@ class SsaBuilder : public HGraphVisitor {
 
   void RemoveRedundantUninitializedStrings();
 
+  // Returns whether `instruction` is the first generated HInstruction for its
+  // dex_pc position.
+  bool IsFirstAtThrowingDexPc(HInstruction* instruction) const;
+
+  const DexFile::CodeItem& code_item_;
   StackHandleScopeCollection* const handles_;
 
   // True if types of ambiguous ArrayGets have been resolved.