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
diff --git a/src/compiler/bb_opt.cc b/src/compiler/bb_opt.cc
new file mode 100644
index 0000000..3ad5821
--- /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 0000000..9eba06f
--- /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 9c67cd5..8f00ac2 100644
--- a/src/compiler/compiler_ir.h
+++ b/src/compiler/compiler_ir.h
@@ -196,7 +196,6 @@
#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 @@
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 03ede70..a129382 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 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 @@
}
/* 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 @@
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 @@
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 @@
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::CMPL_DOUBLE:
- mir_next->dalvikInsn.opcode =
- static_cast<Instruction::Code>(kMirOpFusedCmplDouble);
+ case Instruction::IF_NEZ:
+ ccode = kCondNe;
break;
- case Instruction::CMPG_FLOAT:
- mir_next->dalvikInsn.opcode =
- static_cast<Instruction::Code>(kMirOpFusedCmpgFloat);
+ case Instruction::IF_LTZ:
+ ccode = kCondLt;
break;
- case Instruction::CMPG_DOUBLE:
- mir_next->dalvikInsn.opcode =
- static_cast<Instruction::Code>(kMirOpFusedCmpgDouble);
+ case Instruction::IF_GEZ:
+ ccode = kCondGe;
break;
- case Instruction::CMP_LONG:
- mir_next->dalvikInsn.opcode =
- static_cast<Instruction::Code>(kMirOpFusedCmpLong);
+ case Instruction::IF_GTZ:
+ ccode = kCondGt;
break;
- default: LOG(ERROR) << "Unexpected opcode: " << opcode;
+ case Instruction::IF_LEZ:
+ ccode = kCondLe;
+ break;
+ default:
+ break;
}
- 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;
+ // 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;
+ }
}
- }
- break;
- default:
- break;
+ break;
+ default:
+ break;
+ }
}
+ bb = NextDominatedBlock(cu, bb);
}
if (num_temps > cu->num_compiler_temps) {
@@ -2112,13 +2043,46 @@
}
}
+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 9d30b6a..e00fb68 100644
--- a/src/compiler/frontend.cc
+++ b/src/compiler/frontend.cc
@@ -1124,6 +1124,11 @@
/* 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