Basic block optimization refactoring

Various optimization improvements for the common frontend.

Before applying basic block optimizations, split the graph
into extended basic blocks.  Replace existing pattern-match
range-check elimination with a scheme based on local value
numbering (which could also serve as the basis for some CSE
if the existing, but so-far untested, common frontend temp
register mechanism works as designed).

For the framework, this CL improves null check elimination
from 90.74% (statically) to 91.24% removed, and range
check elimination from 3.45% to 8.17%.

Change-Id: Ie1ce730cfe12a12fef665a30fe3814bad1993895

6 files changed, 805 insertions, 164 deletions

diff --git a/build/Android.libart-compiler.mk b/build/Android.libart-compiler.mk
index 8084be2e9d..829dd6a683 100644
--- a/build/Android.libart-compiler.mk
+++ b/build/Android.libart-compiler.mk
@@ -18,6 +18,7 @@ LIBART_COMPILER_SRC_FILES += \
 	src/compiler/dataflow.cc \
 	src/compiler/frontend.cc \
 	src/compiler/ralloc.cc \
+	src/compiler/bb_opt.cc \
 	src/compiler/ssa_transformation.cc \
 	src/compiler/compiler_utility.cc \
 	src/compiler/codegen/ralloc_util.cc \
diff --git a/src/compiler/bb_opt.cc b/src/compiler/bb_opt.cc
new file mode 100644
index 0000000000..3ad58213ae
--- /dev/null
+++ b/src/compiler/bb_opt.cc
@@ -0,0 +1,519 @@
+/*
+ * Copyright (C) 2012 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 "bb_opt.h"
+#include "dataflow.h"
+
+namespace art {
+
+
+uint16_t BBOpt::GetValueNumber(MIR* mir)
+{
+  uint16_t res = NO_VALUE;
+  uint16_t opcode = mir->dalvikInsn.opcode;
+  switch (opcode) {
+    case Instruction::NOP:
+    case Instruction::RETURN_VOID:
+    case Instruction::RETURN:
+    case Instruction::RETURN_OBJECT:
+    case Instruction::RETURN_WIDE:
+    case Instruction::MONITOR_ENTER:
+    case Instruction::MONITOR_EXIT:
+    case Instruction::GOTO:
+    case Instruction::GOTO_16:
+    case Instruction::GOTO_32:
+    case Instruction::CHECK_CAST:
+    case Instruction::THROW:
+    case Instruction::FILL_ARRAY_DATA:
+    case Instruction::FILLED_NEW_ARRAY:
+    case Instruction::FILLED_NEW_ARRAY_RANGE:
+    case Instruction::PACKED_SWITCH:
+    case Instruction::SPARSE_SWITCH:
+    case Instruction::IF_EQ:
+    case Instruction::IF_NE:
+    case Instruction::IF_LT:
+    case Instruction::IF_GE:
+    case Instruction::IF_GT:
+    case Instruction::IF_LE:
+    case Instruction::IF_EQZ:
+    case Instruction::IF_NEZ:
+    case Instruction::IF_LTZ:
+    case Instruction::IF_GEZ:
+    case Instruction::IF_GTZ:
+    case Instruction::IF_LEZ:
+    case Instruction::INVOKE_STATIC_RANGE:
+    case Instruction::INVOKE_STATIC:
+    case Instruction::INVOKE_DIRECT:
+    case Instruction::INVOKE_DIRECT_RANGE:
+    case Instruction::INVOKE_VIRTUAL:
+    case Instruction::INVOKE_VIRTUAL_RANGE:
+    case Instruction::INVOKE_SUPER:
+    case Instruction::INVOKE_SUPER_RANGE:
+    case Instruction::INVOKE_INTERFACE:
+    case Instruction::INVOKE_INTERFACE_RANGE:
+    case kMirOpFusedCmplFloat:
+    case kMirOpFusedCmpgFloat:
+    case kMirOpFusedCmplDouble:
+    case kMirOpFusedCmpgDouble:
+    case kMirOpFusedCmpLong:
+      // Nothing defined - take no action.
+      break;
+
+    case Instruction::MOVE_EXCEPTION:
+    case Instruction::MOVE_RESULT:
+    case Instruction::MOVE_RESULT_OBJECT:
+    case Instruction::INSTANCE_OF:
+    case Instruction::NEW_INSTANCE:
+    case Instruction::CONST_STRING:
+    case Instruction::CONST_STRING_JUMBO:
+    case Instruction::CONST_CLASS:
+    case Instruction::NEW_ARRAY: {
+        // 1 result, treat as unique each time, use result s_reg - will be unique.
+        uint16_t res = GetOperandValue(mir->ssa_rep->defs[0]);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+    case Instruction::MOVE_RESULT_WIDE: {
+        // 1 wide result, treat as unique each time, use result s_reg - will be unique.
+        uint16_t res = GetOperandValueWide(mir->ssa_rep->defs[0]);
+        SetOperandValueWide(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case kMirOpPhi:
+      /*
+       * Because we'll only see phi nodes at the beginning of an extended basic block,
+       * we can ignore them.  Revisit if we shift to global value numbering.
+       */
+      break;
+
+    case Instruction::MOVE:
+    case Instruction::MOVE_OBJECT:
+    case Instruction::MOVE_16:
+    case Instruction::MOVE_OBJECT_16:
+    case Instruction::MOVE_FROM16:
+    case Instruction::MOVE_OBJECT_FROM16:
+    case kMirOpCopy: {
+        // Just copy value number of source to value number of resulit.
+        uint16_t res = GetOperandValue(mir->ssa_rep->uses[0]);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::MOVE_WIDE:
+    case Instruction::MOVE_WIDE_16:
+    case Instruction::MOVE_WIDE_FROM16: {
+        // Just copy value number of source to value number of result.
+        uint16_t res = GetOperandValueWide(mir->ssa_rep->uses[0]);
+        SetOperandValueWide(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::CONST:
+    case Instruction::CONST_4:
+    case Instruction::CONST_16: {
+        uint16_t res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB),
+                                   High16Bits(mir->dalvikInsn.vB >> 16), 0);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::CONST_HIGH16: {
+        uint16_t res = LookupValue(Instruction::CONST, 0, mir->dalvikInsn.vB, 0);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::CONST_WIDE_16:
+    case Instruction::CONST_WIDE_32: {
+        uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB),
+                                       High16Bits(mir->dalvikInsn.vB >> 16), 1);
+        uint16_t high_res;
+        if (mir->dalvikInsn.vB & 0x80000000) {
+          high_res = LookupValue(Instruction::CONST, 0xffff, 0xffff, 2);
+        } else {
+          high_res = LookupValue(Instruction::CONST, 0, 0, 2);
+        }
+        uint16_t res = LookupValue(Instruction::CONST, low_res, high_res, 3);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::CONST_WIDE: {
+        uint32_t low_word = Low32Bits(mir->dalvikInsn.vB_wide);
+        uint32_t high_word = High32Bits(mir->dalvikInsn.vB_wide);
+        uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(low_word),
+                                       High16Bits(low_word), 1);
+        uint16_t high_res = LookupValue(Instruction::CONST, Low16Bits(high_word),
+                                       High16Bits(high_word), 2);
+        uint16_t res = LookupValue(Instruction::CONST, low_res, high_res, 3);
+        SetOperandValueWide(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::CONST_WIDE_HIGH16: {
+        uint16_t low_res = LookupValue(Instruction::CONST, 0, 0, 1);
+        uint16_t high_res = LookupValue(Instruction::CONST, 0, Low16Bits(mir->dalvikInsn.vB), 2);
+        uint16_t res = LookupValue(Instruction::CONST, low_res, high_res, 3);
+        SetOperandValueWide(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::ARRAY_LENGTH:
+    case Instruction::NEG_INT:
+    case Instruction::NOT_INT:
+    case Instruction::NEG_FLOAT:
+    case Instruction::INT_TO_BYTE:
+    case Instruction::INT_TO_SHORT:
+    case Instruction::INT_TO_CHAR:
+    case Instruction::INT_TO_FLOAT:
+    case Instruction::FLOAT_TO_INT: {
+        // res = op + 1 operand
+        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
+        uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::LONG_TO_FLOAT:
+    case Instruction::LONG_TO_INT:
+    case Instruction::DOUBLE_TO_FLOAT:
+    case Instruction::DOUBLE_TO_INT: {
+        // res = op + 1 wide operand
+        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
+        uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+
+    case Instruction::DOUBLE_TO_LONG:
+    case Instruction::LONG_TO_DOUBLE:
+    case Instruction::NEG_LONG:
+    case Instruction::NOT_LONG:
+    case Instruction::NEG_DOUBLE: {
+        // wide res = op + 1 wide operand
+        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
+        uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE);
+        SetOperandValueWide(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::FLOAT_TO_DOUBLE:
+    case Instruction::FLOAT_TO_LONG:
+    case Instruction::INT_TO_DOUBLE:
+    case Instruction::INT_TO_LONG: {
+        // wide res = op + 1 operand
+        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
+        uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE);
+        SetOperandValueWide(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::CMPL_DOUBLE:
+    case Instruction::CMPG_DOUBLE:
+    case Instruction::CMP_LONG: {
+        // res = op + 2 wide operands
+        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
+        uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]);
+        uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::CMPG_FLOAT:
+    case Instruction::CMPL_FLOAT:
+    case Instruction::ADD_INT:
+    case Instruction::ADD_INT_2ADDR:
+    case Instruction::MUL_INT:
+    case Instruction::MUL_INT_2ADDR:
+    case Instruction::AND_INT:
+    case Instruction::AND_INT_2ADDR:
+    case Instruction::OR_INT:
+    case Instruction::OR_INT_2ADDR:
+    case Instruction::XOR_INT:
+    case Instruction::XOR_INT_2ADDR:
+    case Instruction::SUB_INT:
+    case Instruction::SUB_INT_2ADDR:
+    case Instruction::DIV_INT:
+    case Instruction::DIV_INT_2ADDR:
+    case Instruction::REM_INT:
+    case Instruction::REM_INT_2ADDR:
+    case Instruction::SHL_INT:
+    case Instruction::SHL_INT_2ADDR:
+    case Instruction::SHR_INT:
+    case Instruction::SHR_INT_2ADDR:
+    case Instruction::USHR_INT:
+    case Instruction::USHR_INT_2ADDR: {
+        // res = op + 2 operands
+        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
+        uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]);
+        uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::ADD_LONG:
+    case Instruction::SUB_LONG:
+    case Instruction::MUL_LONG:
+    case Instruction::DIV_LONG:
+    case Instruction::REM_LONG:
+    case Instruction::AND_LONG:
+    case Instruction::OR_LONG:
+    case Instruction::XOR_LONG:
+    case Instruction::ADD_LONG_2ADDR:
+    case Instruction::SUB_LONG_2ADDR:
+    case Instruction::MUL_LONG_2ADDR:
+    case Instruction::DIV_LONG_2ADDR:
+    case Instruction::REM_LONG_2ADDR:
+    case Instruction::AND_LONG_2ADDR:
+    case Instruction::OR_LONG_2ADDR:
+    case Instruction::XOR_LONG_2ADDR:
+    case Instruction::ADD_DOUBLE:
+    case Instruction::SUB_DOUBLE:
+    case Instruction::MUL_DOUBLE:
+    case Instruction::DIV_DOUBLE:
+    case Instruction::REM_DOUBLE:
+    case Instruction::ADD_DOUBLE_2ADDR:
+    case Instruction::SUB_DOUBLE_2ADDR:
+    case Instruction::MUL_DOUBLE_2ADDR:
+    case Instruction::DIV_DOUBLE_2ADDR:
+    case Instruction::REM_DOUBLE_2ADDR: {
+        // wide res = op + 2 wide operands
+        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
+        uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]);
+        uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
+        SetOperandValueWide(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::SHL_LONG:
+    case Instruction::SHR_LONG:
+    case Instruction::USHR_LONG:
+    case Instruction::SHL_LONG_2ADDR:
+    case Instruction::SHR_LONG_2ADDR:
+    case Instruction::USHR_LONG_2ADDR: {
+        // wide res = op + 1 wide operand + 1 operand
+        uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
+        uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]);
+        uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
+        SetOperandValueWide(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::ADD_FLOAT:
+    case Instruction::SUB_FLOAT:
+    case Instruction::MUL_FLOAT:
+    case Instruction::DIV_FLOAT:
+    case Instruction::REM_FLOAT:
+    case Instruction::ADD_FLOAT_2ADDR:
+    case Instruction::SUB_FLOAT_2ADDR:
+    case Instruction::MUL_FLOAT_2ADDR:
+    case Instruction::DIV_FLOAT_2ADDR:
+    case Instruction::REM_FLOAT_2ADDR: {
+        // res = op + 2 operands
+        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
+        uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]);
+        uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::RSUB_INT:
+    case Instruction::ADD_INT_LIT16:
+    case Instruction::MUL_INT_LIT16:
+    case Instruction::DIV_INT_LIT16:
+    case Instruction::REM_INT_LIT16:
+    case Instruction::AND_INT_LIT16:
+    case Instruction::OR_INT_LIT16:
+    case Instruction::XOR_INT_LIT16:
+    case Instruction::ADD_INT_LIT8:
+    case Instruction::RSUB_INT_LIT8:
+    case Instruction::MUL_INT_LIT8:
+    case Instruction::DIV_INT_LIT8:
+    case Instruction::REM_INT_LIT8:
+    case Instruction::AND_INT_LIT8:
+    case Instruction::OR_INT_LIT8:
+    case Instruction::XOR_INT_LIT8:
+    case Instruction::SHL_INT_LIT8:
+    case Instruction::SHR_INT_LIT8:
+    case Instruction::USHR_INT_LIT8: {
+        // Same as res = op + 2 operands, except use vB as operand 2
+        uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
+        uint16_t operand2 = LookupValue(Instruction::CONST, mir->dalvikInsn.vB, 0, 0);
+        uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+      }
+      break;
+
+    case Instruction::AGET_WIDE:
+    case Instruction::AGET:
+    case Instruction::AGET_OBJECT:
+    case Instruction::AGET_BOOLEAN:
+    case Instruction::AGET_BYTE:
+    case Instruction::AGET_CHAR:
+    case Instruction::AGET_SHORT: {
+        uint16_t array = GetOperandValue(mir->ssa_rep->uses[0]);
+        if (null_checked_.find(array) != null_checked_.end()) {
+          if (cu_->verbose) {
+            LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset;
+          }
+          mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
+        } else {
+          null_checked_.insert(array);
+        }
+        uint16_t index = GetOperandValue(mir->ssa_rep->uses[1]);
+        if (ValueExists(ARRAY_REF, array, index, NO_VALUE)) {
+          if (cu_->verbose) {
+            LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset;
+          }
+          mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK;
+        }
+        mir->meta.throw_insn->optimization_flags |= mir->optimization_flags;
+        // Use side effect to note range check completed.
+        (void)LookupValue(ARRAY_REF, array, index, NO_VALUE);
+        // Establish value number for loaded register. Note use of memory version.
+        uint16_t memory_version = GetMemoryVersion(array, NO_VALUE);
+        uint16_t res = LookupValue(ARRAY_REF, array, index, memory_version);
+        if (opcode == Instruction::AGET_WIDE) {
+          SetOperandValueWide(mir->ssa_rep->defs[0], res);
+        } else {
+          SetOperandValue(mir->ssa_rep->defs[0], res);
+        }
+      }
+      break;
+
+    case Instruction::APUT_WIDE:
+    case Instruction::APUT:
+    case Instruction::APUT_OBJECT:
+    case Instruction::APUT_SHORT:
+    case Instruction::APUT_CHAR:
+    case Instruction::APUT_BYTE:
+    case Instruction::APUT_BOOLEAN: {
+        int array_idx = (opcode == Instruction::APUT_WIDE) ? 2 : 1;
+        int index_idx = array_idx + 1;
+        uint16_t array = GetOperandValue(mir->ssa_rep->uses[array_idx]);
+        if (null_checked_.find(array) != null_checked_.end()) {
+          if (cu_->verbose) {
+            LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset;
+          }
+          mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
+        } else {
+          null_checked_.insert(array);
+        }
+        uint16_t index = GetOperandValue(mir->ssa_rep->uses[index_idx]);
+        if (ValueExists(ARRAY_REF, array, index, NO_VALUE)) {
+          if (cu_->verbose) {
+            LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset;
+          }
+          mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK;
+        }
+        mir->meta.throw_insn->optimization_flags |= mir->optimization_flags;
+        // Use side effect to note range check completed.
+        (void)LookupValue(ARRAY_REF, array, index, NO_VALUE);
+        // Rev the memory version
+        AdvanceMemoryVersion(array, NO_VALUE);
+      }
+      break;
+
+    case Instruction::IGET_OBJECT:
+    case Instruction::IGET_WIDE:
+    case Instruction::IGET:
+    case Instruction::IGET_CHAR:
+    case Instruction::IGET_SHORT:
+    case Instruction::IGET_BOOLEAN:
+    case Instruction::IGET_BYTE: {
+        uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]);
+        if (null_checked_.find(base) != null_checked_.end()) {
+          if (cu_->verbose) {
+            LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset;
+          }
+          mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
+        } else {
+          null_checked_.insert(base);
+        }
+        mir->meta.throw_insn->optimization_flags |= mir->optimization_flags;
+        uint16_t field_ref = mir->dalvikInsn.vC;
+        uint16_t memory_version = GetMemoryVersion(base, field_ref);
+        if (opcode == Instruction::IGET_WIDE) {
+          uint16_t res = LookupValue(Instruction::IGET_WIDE, base, field_ref, memory_version);
+          SetOperandValueWide(mir->ssa_rep->defs[0], res);
+        } else {
+          uint16_t res = LookupValue(Instruction::IGET, base, field_ref, memory_version);
+          SetOperandValue(mir->ssa_rep->defs[0], res);
+        }
+      }
+      break;
+
+    case Instruction::IPUT_WIDE:
+    case Instruction::IPUT_OBJECT:
+    case Instruction::IPUT:
+    case Instruction::IPUT_BOOLEAN:
+    case Instruction::IPUT_BYTE:
+    case Instruction::IPUT_CHAR:
+    case Instruction::IPUT_SHORT: {
+        int base_reg = (opcode == Instruction::IPUT_WIDE) ? 2 : 1;
+        uint16_t base = GetOperandValue(mir->ssa_rep->uses[base_reg]);
+        if (null_checked_.find(base) != null_checked_.end()) {
+          if (cu_->verbose) {
+            LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset;
+          }
+          mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
+        } else {
+          null_checked_.insert(base);
+        }
+        mir->meta.throw_insn->optimization_flags |= mir->optimization_flags;
+        uint16_t field_ref = mir->dalvikInsn.vC;
+        AdvanceMemoryVersion(base, field_ref);
+      }
+      break;
+
+    case Instruction::SGET_OBJECT:
+    case Instruction::SGET:
+    case Instruction::SGET_BOOLEAN:
+    case Instruction::SGET_BYTE:
+    case Instruction::SGET_CHAR:
+    case Instruction::SGET_SHORT:
+    case Instruction::SGET_WIDE: {
+        uint16_t field_ref = mir->dalvikInsn.vB;
+        uint16_t memory_version = GetMemoryVersion(NO_VALUE, field_ref);
+        if (opcode == Instruction::SGET_WIDE) {
+          uint16_t res = LookupValue(Instruction::SGET_WIDE, NO_VALUE, field_ref, memory_version);
+          SetOperandValueWide(mir->ssa_rep->defs[0], res);
+        } else {
+          uint16_t res = LookupValue(Instruction::SGET, NO_VALUE, field_ref, memory_version);
+          SetOperandValue(mir->ssa_rep->defs[0], res);
+        }
+      }
+      break;
+
+    case Instruction::SPUT_OBJECT:
+    case Instruction::SPUT:
+    case Instruction::SPUT_BOOLEAN:
+    case Instruction::SPUT_BYTE:
+    case Instruction::SPUT_CHAR:
+    case Instruction::SPUT_SHORT:
+    case Instruction::SPUT_WIDE: {
+        uint16_t field_ref = mir->dalvikInsn.vB;
+        AdvanceMemoryVersion(NO_VALUE, field_ref);
+      }
+      break;
+
+  }
+  return res;
+}
+
+}    // namespace art
diff --git a/src/compiler/bb_opt.h b/src/compiler/bb_opt.h
new file mode 100644
index 0000000000..9eba06fbdc
--- /dev/null
+++ b/src/compiler/bb_opt.h
@@ -0,0 +1,152 @@
+/*
+ * Copyright (C) 2012 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_SRC_COMPILER_BBOPT_H_
+#define ART_SRC_COMPILER_BBOPT_H_
+
+#include "compiler_internals.h"
+
+#define NO_VALUE 0xffff
+#define ARRAY_REF 0xfffe
+
+namespace art {
+
+// Key is s_reg, value is value name.
+typedef SafeMap<uint16_t, uint16_t> SregValueMap;
+// Key is concatenation of quad, value is value name.
+typedef SafeMap<uint64_t, uint16_t> ValueMap;
+// Key represents a memory address, value is generation.
+typedef SafeMap<uint32_t, uint16_t> MemoryVersionMap;
+
+class BBOpt {
+ public:
+  BBOpt(CompilationUnit* cu) : cu_(cu) {};
+
+  uint64_t BuildKey(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier)
+  {
+    return (static_cast<uint64_t>(op) << 48 | static_cast<uint64_t>(operand1) << 32 |
+            static_cast<uint64_t>(operand2) << 16 | static_cast<uint64_t>(modifier));
+  };
+
+  uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier)
+  {
+    uint16_t res;
+    uint64_t key = BuildKey(op, operand1, operand2, modifier);
+    ValueMap::iterator it = value_map_.find(key);
+    if (it != value_map_.end()) {
+      res = it->second;
+    } else {
+      res = value_map_.size() + 1;
+      value_map_.Put(key, res);
+    }
+    return res;
+  };
+
+  bool ValueExists(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier)
+  {
+    uint64_t key = BuildKey(op, operand1, operand2, modifier);
+    ValueMap::iterator it = value_map_.find(key);
+    return (it != value_map_.end());
+  };
+
+  uint16_t GetMemoryVersion(uint16_t base, uint16_t field)
+  {
+    uint32_t key = (base << 16) | field;
+    uint16_t res;
+    MemoryVersionMap::iterator it = memory_version_map_.find(key);
+    if (it == memory_version_map_.end()) {
+      res = 0;
+      memory_version_map_.Put(key, res);
+    } else {
+      res = it->second;
+    }
+    return res;
+  };
+
+  void AdvanceMemoryVersion(uint16_t base, uint16_t field)
+  {
+    uint32_t key = (base << 16) | field;
+    MemoryVersionMap::iterator it = memory_version_map_.find(key);
+    if (it == memory_version_map_.end()) {
+      memory_version_map_.Put(key, 0);
+    } else {
+      it->second++;
+    }
+  };
+
+  void SetOperandValue(uint16_t s_reg, uint16_t value)
+  {
+    SregValueMap::iterator it = sreg_value_map_.find(s_reg);
+    if (it != sreg_value_map_.end()) {
+      DCHECK_EQ(it->second, value);
+    } else {
+      sreg_value_map_.Put(s_reg, value);
+    }
+  };
+
+  uint16_t GetOperandValue(int s_reg)
+  {
+    uint16_t res = NO_VALUE;
+    SregValueMap::iterator it = sreg_value_map_.find(s_reg);
+    if (it != sreg_value_map_.end()) {
+      res = it->second;
+    } else {
+      // First use
+      res = LookupValue(NO_VALUE, s_reg, NO_VALUE, NO_VALUE);
+      sreg_value_map_.Put(s_reg, res);
+    }
+    return res;
+  };
+
+  void SetOperandValueWide(uint16_t s_reg, uint16_t value)
+  {
+    SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg);
+    if (it != sreg_wide_value_map_.end()) {
+      DCHECK_EQ(it->second, value);
+    } else {
+      sreg_wide_value_map_.Put(s_reg, value);
+    }
+  };
+
+  uint16_t GetOperandValueWide(int s_reg)
+  {
+    uint16_t res = NO_VALUE;
+    SregValueMap::iterator it = sreg_wide_value_map_.find(s_reg);
+    if (it != sreg_wide_value_map_.end()) {
+      res = it->second;
+    } else {
+      // First use
+      res = LookupValue(NO_VALUE, s_reg, NO_VALUE, NO_VALUE);
+      sreg_wide_value_map_.Put(s_reg, res);
+    }
+    return res;
+  };
+
+  uint16_t GetValueNumber(MIR* mir);
+
+ private:
+  CompilationUnit* cu_;
+  SregValueMap sreg_value_map_;
+  SregValueMap sreg_wide_value_map_;
+  ValueMap value_map_;
+  MemoryVersionMap memory_version_map_;
+  std::set<uint16_t> null_checked_;
+
+};
+
+} // namespace art
+
+#endif   // ART_SRC_COMPILER_BBOPT_H_
diff --git a/src/compiler/compiler_ir.h b/src/compiler/compiler_ir.h
index 9c67cd567c..8f00ac2282 100644
--- a/src/compiler/compiler_ir.h
+++ b/src/compiler/compiler_ir.h
@@ -196,7 +196,6 @@ struct SSARepresentation;
 #define MIR_CALLEE                      (1 << kMIRCallee)
 #define MIR_IGNORE_SUSPEND_CHECK        (1 << kMIRIgnoreSuspendCheck)
 #define MIR_DUP                         (1 << kMIRDup)
-#define MIR_MARK                        (1 << kMIRMark)
 
 struct Checkstats {
   int null_checks;
@@ -400,6 +399,7 @@ struct CompilationUnit {
   std::vector<uint32_t> core_vmap_table;
   std::vector<uint32_t> fp_vmap_table;
   std::vector<uint8_t> native_gc_map;
+  std::vector<BasicBlock*> extended_basic_blocks;
   bool verbose;
   bool has_loop;                       // Contains a loop.
   bool has_invoke;                     // Contains an invoke instruction.
diff --git a/src/compiler/dataflow.cc b/src/compiler/dataflow.cc
index 03ede70453..a129382807 100644
--- a/src/compiler/dataflow.cc
+++ b/src/compiler/dataflow.cc
@@ -16,6 +16,7 @@
 
 #include "compiler_internals.h"
 #include "dataflow.h"
+#include "bb_opt.h"
 
 namespace art {
 
@@ -863,8 +864,8 @@ static std::string GetSSAName(const CompilationUnit* cu, int ssa_reg)
 static std::string GetSSANameWithConst(const CompilationUnit* cu, int ssa_reg, bool singles_only)
 {
   if (cu->reg_location == NULL) {
-    // Pre-SSA - just use the Dalvik vreg
-    return StringPrintf("v%d", ssa_reg);
+    // Pre-SSA - just use the standard name
+    return GetSSAName(cu, ssa_reg);
   }
   if (cu->reg_location[ssa_reg].is_const) {
     if (!singles_only && cu->reg_location[ssa_reg].wide) {
@@ -1564,8 +1565,8 @@ void DataFlowAnalysisDispatcher(CompilationUnit* cu,
 }
 
 /* Advance to next strictly dominated MIR node in an extended basic block */
-static MIR* AdvanceMIR(CompilationUnit* cu, BasicBlock** p_bb, MIR* mir,
-                       ArenaBitVector* bv, bool clear_mark) {
+static MIR* AdvanceMIR(CompilationUnit* cu, BasicBlock** p_bb, MIR* mir)
+{
   BasicBlock* bb = *p_bb;
   if (mir != NULL) {
     mir = mir->next;
@@ -1574,17 +1575,11 @@ static MIR* AdvanceMIR(CompilationUnit* cu, BasicBlock** p_bb, MIR* mir,
       if ((bb == NULL) || bb->predecessors->num_used != 1) {
         mir = NULL;
       } else {
-        if (bv) {
-          SetBit(cu, bv, bb->id);
-        }
       *p_bb = bb;
       mir = bb->first_mir_insn;
       }
     }
   }
-  if (mir && clear_mark) {
-    mir->optimization_flags &= ~MIR_MARK;
-  }
   return mir;
 }
 
@@ -1598,7 +1593,7 @@ static MIR* AdvanceMIR(CompilationUnit* cu, BasicBlock** p_bb, MIR* mir,
 MIR* FindMoveResult(CompilationUnit* cu, BasicBlock* bb, MIR* mir)
 {
   BasicBlock* tbb = bb;
-  mir = AdvanceMIR(cu, &tbb, mir, NULL, false);
+  mir = AdvanceMIR(cu, &tbb, mir);
   while (mir != NULL) {
     int opcode = mir->dalvikInsn.opcode;
     if ((mir->dalvikInsn.opcode == Instruction::MOVE_RESULT) ||
@@ -1610,178 +1605,114 @@ MIR* FindMoveResult(CompilationUnit* cu, BasicBlock* bb, MIR* mir)
     if (opcode < kNumPackedOpcodes) {
       mir = NULL;
     } else {
-      mir = AdvanceMIR(cu, &tbb, mir, NULL, false);
+      mir = AdvanceMIR(cu, &tbb, mir);
     }
   }
   return mir;
 }
 
-static void SquashDupRangeChecks(CompilationUnit* cu, BasicBlock** p_bp, MIR* mir,
-                                 int array_sreg, int index_sreg)
+static BasicBlock* NextDominatedBlock(CompilationUnit* cu, BasicBlock* bb)
 {
-  while (true) {
-    mir = AdvanceMIR(cu, p_bp, mir, NULL, false);
-    if (!mir) {
-      break;
-    }
-    if ((mir->ssa_rep == NULL) ||
-        (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK)) {
-       continue;
-    }
-    int check_array = INVALID_SREG;
-    int check_index = INVALID_SREG;
-    switch (mir->dalvikInsn.opcode) {
-      case Instruction::AGET:
-      case Instruction::AGET_OBJECT:
-      case Instruction::AGET_BOOLEAN:
-      case Instruction::AGET_BYTE:
-      case Instruction::AGET_CHAR:
-      case Instruction::AGET_SHORT:
-      case Instruction::AGET_WIDE:
-        check_array = mir->ssa_rep->uses[0];
-        check_index = mir->ssa_rep->uses[1];
-        break;
-      case Instruction::APUT:
-      case Instruction::APUT_OBJECT:
-      case Instruction::APUT_SHORT:
-      case Instruction::APUT_CHAR:
-      case Instruction::APUT_BYTE:
-      case Instruction::APUT_BOOLEAN:
-        check_array = mir->ssa_rep->uses[1];
-        check_index = mir->ssa_rep->uses[2];
-        break;
-      case Instruction::APUT_WIDE:
-        check_array = mir->ssa_rep->uses[2];
-        check_index = mir->ssa_rep->uses[3];
-      default:
-        break;
-    }
-    if (check_array == INVALID_SREG) {
-      continue;
-    }
-    if ((array_sreg == check_array) && (index_sreg == check_index)) {
-      if (cu->verbose) {
-        LOG(INFO) << "Squashing range check @ 0x" << std::hex << mir->offset;
-      }
-      mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK;
-    }
+  DCHECK((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
+      || (bb->block_type == kExitBlock));
+  bb = bb->fall_through;
+  if (bb == NULL || (bb->predecessors->num_used != 1)) {
+    return NULL;
   }
+  DCHECK((bb->block_type == kDalvikByteCode) || (bb->block_type == kExitBlock));
+  return bb;
 }
 
-/* Do some MIR-level basic block optimizations */
+/* Do some MIR-level extended basic block optimizations */
 static bool BasicBlockOpt(CompilationUnit* cu, BasicBlock* bb)
 {
   int num_temps = 0;
-
-  for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
-    // Look for interesting opcodes, skip otherwise
-    Instruction::Code opcode = mir->dalvikInsn.opcode;
-    switch (opcode) {
-      case Instruction::AGET:
-      case Instruction::AGET_OBJECT:
-      case Instruction::AGET_BOOLEAN:
-      case Instruction::AGET_BYTE:
-      case Instruction::AGET_CHAR:
-      case Instruction::AGET_SHORT:
-      case Instruction::AGET_WIDE:
-        if (!(mir->optimization_flags & MIR_IGNORE_RANGE_CHECK)) {
-          int arr_sreg = mir->ssa_rep->uses[0];
-          int idx_sreg = mir->ssa_rep->uses[1];
-          BasicBlock* tbb = bb;
-          SquashDupRangeChecks(cu, &tbb, mir, arr_sreg, idx_sreg);
-        }
-        break;
-      case Instruction::APUT:
-      case Instruction::APUT_OBJECT:
-      case Instruction::APUT_SHORT:
-      case Instruction::APUT_CHAR:
-      case Instruction::APUT_BYTE:
-      case Instruction::APUT_BOOLEAN:
-      case Instruction::APUT_WIDE:
-        if (!(mir->optimization_flags & MIR_IGNORE_RANGE_CHECK)) {
-          int start = (opcode == Instruction::APUT_WIDE) ? 2 : 1;
-          int arr_sreg = mir->ssa_rep->uses[start];
-          int idx_sreg = mir->ssa_rep->uses[start + 1];
-          BasicBlock* tbb = bb;
-          SquashDupRangeChecks(cu, &tbb, mir, arr_sreg, idx_sreg);
-        }
-        break;
-      case Instruction::CMPL_FLOAT:
-      case Instruction::CMPL_DOUBLE:
-      case Instruction::CMPG_FLOAT:
-      case Instruction::CMPG_DOUBLE:
-      case Instruction::CMP_LONG:
-        if (cu->gen_bitcode) {
-          // Bitcode doesn't allow this optimization.
-          break;
-        }
-        if (mir->next != NULL) {
-          MIR* mir_next = mir->next;
-          Instruction::Code br_opcode = mir_next->dalvikInsn.opcode;
-          ConditionCode ccode = kCondNv;
-          switch(br_opcode) {
-            case Instruction::IF_EQZ:
-              ccode = kCondEq;
-              break;
-            case Instruction::IF_NEZ:
-              ccode = kCondNe;
-              break;
-            case Instruction::IF_LTZ:
-              ccode = kCondLt;
-              break;
-            case Instruction::IF_GEZ:
-              ccode = kCondGe;
-              break;
-            case Instruction::IF_GTZ:
-              ccode = kCondGt;
-              break;
-            case Instruction::IF_LEZ:
-              ccode = kCondLe;
-              break;
-            default:
-              break;
+  BBOpt bb_opt(cu);
+  while (bb != NULL) {
+    for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
+      // TUNING: use the returned value number for CSE.
+      bb_opt.GetValueNumber(mir);
+      // Look for interesting opcodes, skip otherwise
+      Instruction::Code opcode = mir->dalvikInsn.opcode;
+      switch (opcode) {
+        case Instruction::CMPL_FLOAT:
+        case Instruction::CMPL_DOUBLE:
+        case Instruction::CMPG_FLOAT:
+        case Instruction::CMPG_DOUBLE:
+        case Instruction::CMP_LONG:
+          if (cu->gen_bitcode) {
+            // Bitcode doesn't allow this optimization.
+            break;
           }
-          // Make sure result of cmp is used by next insn and nowhere else
-          if ((ccode != kCondNv) &&
-              (mir->ssa_rep->defs[0] == mir_next->ssa_rep->uses[0]) &&
-              (GetSSAUseCount(cu, mir->ssa_rep->defs[0]) == 1)) {
-            mir_next->dalvikInsn.arg[0] = ccode;
-            switch(opcode) {
-              case Instruction::CMPL_FLOAT:
-                mir_next->dalvikInsn.opcode =
-                    static_cast<Instruction::Code>(kMirOpFusedCmplFloat);
+          if (mir->next != NULL) {
+            MIR* mir_next = mir->next;
+            Instruction::Code br_opcode = mir_next->dalvikInsn.opcode;
+            ConditionCode ccode = kCondNv;
+            switch(br_opcode) {
+              case Instruction::IF_EQZ:
+                ccode = kCondEq;
+                break;
+              case Instruction::IF_NEZ:
+                ccode = kCondNe;
                 break;
-              case Instruction::CMPL_DOUBLE:
-                mir_next->dalvikInsn.opcode =
-                    static_cast<Instruction::Code>(kMirOpFusedCmplDouble);
+              case Instruction::IF_LTZ:
+                ccode = kCondLt;
                 break;
-              case Instruction::CMPG_FLOAT:
-                mir_next->dalvikInsn.opcode =
-                    static_cast<Instruction::Code>(kMirOpFusedCmpgFloat);
+              case Instruction::IF_GEZ:
+                ccode = kCondGe;
                 break;
-              case Instruction::CMPG_DOUBLE:
-                mir_next->dalvikInsn.opcode =
-                    static_cast<Instruction::Code>(kMirOpFusedCmpgDouble);
+              case Instruction::IF_GTZ:
+                ccode = kCondGt;
                 break;
-              case Instruction::CMP_LONG:
-                mir_next->dalvikInsn.opcode =
-                    static_cast<Instruction::Code>(kMirOpFusedCmpLong);
+              case Instruction::IF_LEZ:
+                ccode = kCondLe;
                 break;
-              default: LOG(ERROR) << "Unexpected opcode: " << opcode;
+              default:
+                break;
+            }
+            // Make sure result of cmp is used by next insn and nowhere else
+            if ((ccode != kCondNv) &&
+                (mir->ssa_rep->defs[0] == mir_next->ssa_rep->uses[0]) &&
+                (GetSSAUseCount(cu, mir->ssa_rep->defs[0]) == 1)) {
+              mir_next->dalvikInsn.arg[0] = ccode;
+              switch(opcode) {
+                case Instruction::CMPL_FLOAT:
+                  mir_next->dalvikInsn.opcode =
+                      static_cast<Instruction::Code>(kMirOpFusedCmplFloat);
+                  break;
+                case Instruction::CMPL_DOUBLE:
+                  mir_next->dalvikInsn.opcode =
+                      static_cast<Instruction::Code>(kMirOpFusedCmplDouble);
+                  break;
+                case Instruction::CMPG_FLOAT:
+                  mir_next->dalvikInsn.opcode =
+                      static_cast<Instruction::Code>(kMirOpFusedCmpgFloat);
+                  break;
+                case Instruction::CMPG_DOUBLE:
+                  mir_next->dalvikInsn.opcode =
+                      static_cast<Instruction::Code>(kMirOpFusedCmpgDouble);
+                  break;
+                case Instruction::CMP_LONG:
+                  mir_next->dalvikInsn.opcode =
+                      static_cast<Instruction::Code>(kMirOpFusedCmpLong);
+                  break;
+                default: LOG(ERROR) << "Unexpected opcode: " << opcode;
+              }
+              mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
+              mir_next->ssa_rep->num_uses = mir->ssa_rep->num_uses;
+              mir_next->ssa_rep->uses = mir->ssa_rep->uses;
+              mir_next->ssa_rep->fp_use = mir->ssa_rep->fp_use;
+              mir_next->ssa_rep->num_defs = 0;
+              mir->ssa_rep->num_uses = 0;
+              mir->ssa_rep->num_defs = 0;
             }
-            mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
-            mir_next->ssa_rep->num_uses = mir->ssa_rep->num_uses;
-            mir_next->ssa_rep->uses = mir->ssa_rep->uses;
-            mir_next->ssa_rep->fp_use = mir->ssa_rep->fp_use;
-            mir_next->ssa_rep->num_defs = 0;
-            mir->ssa_rep->num_uses = 0;
-            mir->ssa_rep->num_defs = 0;
           }
-        }
-        break;
-      default:
-        break;
+          break;
+        default:
+          break;
+      }
     }
+    bb = NextDominatedBlock(cu, bb);
   }
 
   if (num_temps > cu->num_compiler_temps) {
@@ -2112,13 +2043,46 @@ void DumpCheckStats(CompilationUnit *cu)
   }
 }
 
+bool BuildExtendedBBList(struct CompilationUnit* cu, struct BasicBlock* bb)
+{
+  if (bb->visited) return false;
+  if (!((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
+      || (bb->block_type == kExitBlock))) {
+    // Ignore special blocks
+    bb->visited = true;
+    return false;
+  }
+  // Must be head of extended basic block.
+  if (cu->verbose) {
+    LOG(INFO) << "Extended bb head " << bb->id;
+  }
+  cu->extended_basic_blocks.push_back(bb);
+  // Visit blocks strictly dominated by this head.
+  while (bb != NULL) {
+    bb->visited = true;
+    bb = NextDominatedBlock(cu, bb);
+    if (cu->verbose && (bb != NULL)) {
+      LOG(INFO) << "...added bb " << bb->id;
+    }
+  }
+  return false; // Not iterative - return value will be ignored
+}
+
 void BasicBlockOptimization(CompilationUnit *cu)
 {
   if (!(cu->disable_opt & (1 << kBBOpt))) {
     CompilerInitGrowableList(cu, &cu->compiler_temps, 6, kListMisc);
     DCHECK_EQ(cu->num_compiler_temps, 0);
-    DataFlowAnalysisDispatcher(cu, BasicBlockOpt,
+    // Mark all blocks as not visited
+    DataFlowAnalysisDispatcher(cu, ClearVisitedFlag,
                                   kAllNodes, false /* is_iterative */);
+    DataFlowAnalysisDispatcher(cu, BuildExtendedBBList,
+                                  kPreOrderDFSTraversal,
+                                  false /* is_iterative */);
+    // Perform extended basic block optimizations.
+    for (unsigned int i = 0; i < cu->extended_basic_blocks.size(); i++) {
+      BasicBlockOpt(cu, cu->extended_basic_blocks[i]);
+    }
   }
 }
 
diff --git a/src/compiler/frontend.cc b/src/compiler/frontend.cc
index 9d30b6ad0b..e00fb68621 100644
--- a/src/compiler/frontend.cc
+++ b/src/compiler/frontend.cc
@@ -1124,6 +1124,11 @@ static CompiledMethod* CompileMethod(Compiler& compiler,
   /* Allocate Registers using simple local allocation scheme */
   SimpleRegAlloc(cu.get());
 
+  if (cu->enable_debug & (1 << kDebugDumpCFG)) {
+    DumpCFG(cu.get(), "/sdcard/7_post_ralloc_cfg/", true);
+  }
+
+
   /* Go the LLVM path? */
   if (cu->gen_bitcode) {
     // MIR->Bitcode