Class initialization check elimination.
Also, move null check elimination temporaries to the
ScopedArenaAllocator and reuse the same variables in the
class initialization check elimination.
Change-Id: Ic746f95427065506fa6016d4931e4cb8b34937af
diff --git a/compiler/dex/mir_optimization_test.cc b/compiler/dex/mir_optimization_test.cc
new file mode 100644
index 0000000..f499364
--- /dev/null
+++ b/compiler/dex/mir_optimization_test.cc
@@ -0,0 +1,406 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vector>
+
+#include "compiler_internals.h"
+#include "dataflow_iterator.h"
+#include "dataflow_iterator-inl.h"
+#include "gtest/gtest.h"
+
+namespace art {
+
+class ClassInitCheckEliminationTest : public testing::Test {
+ protected:
+ struct SFieldDef {
+ uint16_t field_idx;
+ uintptr_t declaring_dex_file;
+ uint16_t declaring_class_idx;
+ uint16_t declaring_field_idx;
+ };
+
+ struct BBDef {
+ static constexpr size_t kMaxSuccessors = 4;
+ static constexpr size_t kMaxPredecessors = 4;
+
+ BBType type;
+ size_t num_successors;
+ BasicBlockId successors[kMaxPredecessors];
+ size_t num_predecessors;
+ BasicBlockId predecessors[kMaxPredecessors];
+ };
+
+ struct MIRDef {
+ Instruction::Code opcode;
+ BasicBlockId bbid;
+ uint32_t field_or_method_info;
+ };
+
+#define DEF_SUCC0() \
+ 0u, { }
+#define DEF_SUCC1(s1) \
+ 1u, { s1 }
+#define DEF_SUCC2(s1, s2) \
+ 2u, { s1, s2 }
+#define DEF_SUCC3(s1, s2, s3) \
+ 3u, { s1, s2, s3 }
+#define DEF_SUCC4(s1, s2, s3, s4) \
+ 4u, { s1, s2, s3, s4 }
+#define DEF_PRED0() \
+ 0u, { }
+#define DEF_PRED1(p1) \
+ 1u, { p1 }
+#define DEF_PRED2(p1, p2) \
+ 2u, { p1, p2 }
+#define DEF_PRED3(p1, p2, p3) \
+ 3u, { p1, p2, p3 }
+#define DEF_PRED4(p1, p2, p3, p4) \
+ 4u, { p1, p2, p3, p4 }
+#define DEF_BB(type, succ, pred) \
+ { type, succ, pred }
+
+#define DEF_MIR(opcode, bb, field_info) \
+ { opcode, bb, field_info }
+
+ void DoPrepareSFields(const SFieldDef* defs, size_t count) {
+ cu_.mir_graph->sfield_lowering_infos_.Reset();
+ cu_.mir_graph->sfield_lowering_infos_.Resize(count);
+ for (size_t i = 0u; i != count; ++i) {
+ const SFieldDef* def = &defs[i];
+ MirSFieldLoweringInfo field_info(def->field_idx);
+ if (def->declaring_dex_file != 0u) {
+ field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
+ field_info.declaring_class_idx_ = def->declaring_class_idx;
+ field_info.declaring_field_idx_ = def->declaring_field_idx;
+ field_info.flags_ = MirSFieldLoweringInfo::kFlagIsStatic;
+ }
+ ASSERT_EQ(def->declaring_dex_file != 0u, field_info.IsResolved());
+ ASSERT_FALSE(field_info.IsInitialized());
+ cu_.mir_graph->sfield_lowering_infos_.Insert(field_info);
+ }
+ }
+
+ template <size_t count>
+ void PrepareSFields(const SFieldDef (&defs)[count]) {
+ DoPrepareSFields(defs, count);
+ }
+
+ void DoPrepareBasicBlocks(const BBDef* defs, size_t count) {
+ cu_.mir_graph->block_id_map_.clear();
+ cu_.mir_graph->block_list_.Reset();
+ ASSERT_LT(3u, count); // null, entry, exit and at least one bytecode block.
+ ASSERT_EQ(kNullBlock, defs[0].type);
+ ASSERT_EQ(kEntryBlock, defs[1].type);
+ ASSERT_EQ(kExitBlock, defs[2].type);
+ for (size_t i = 0u; i != count; ++i) {
+ const BBDef* def = &defs[i];
+ BasicBlock* bb = cu_.mir_graph->NewMemBB(def->type, i);
+ cu_.mir_graph->block_list_.Insert(bb);
+ if (def->num_successors <= 2) {
+ bb->successor_block_list_type = kNotUsed;
+ bb->successor_blocks = nullptr;
+ bb->fall_through = (def->num_successors >= 1) ? def->successors[0] : 0u;
+ bb->taken = (def->num_successors >= 2) ? def->successors[1] : 0u;
+ } else {
+ bb->successor_block_list_type = kPackedSwitch;
+ bb->fall_through = 0u;
+ bb->taken = 0u;
+ bb->successor_blocks = new (&cu_.arena) GrowableArray<SuccessorBlockInfo*>(
+ &cu_.arena, def->num_successors, kGrowableArraySuccessorBlocks);
+ for (size_t j = 0u; j != def->num_successors; ++j) {
+ SuccessorBlockInfo* successor_block_info =
+ static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo),
+ kArenaAllocSuccessor));
+ successor_block_info->block = j;
+ successor_block_info->key = 0u; // Not used by class init check elimination.
+ bb->successor_blocks->Insert(successor_block_info);
+ }
+ }
+ bb->predecessors = new (&cu_.arena) GrowableArray<BasicBlockId>(
+ &cu_.arena, def->num_predecessors, kGrowableArrayPredecessors);
+ for (size_t j = 0u; j != def->num_predecessors; ++j) {
+ ASSERT_NE(0u, def->predecessors[j]);
+ bb->predecessors->Insert(def->predecessors[j]);
+ }
+ if (def->type == kDalvikByteCode || def->type == kEntryBlock || def->type == kExitBlock) {
+ bb->data_flow_info = static_cast<BasicBlockDataFlow*>(
+ cu_.arena.Alloc(sizeof(BasicBlockDataFlow), kArenaAllocDFInfo));
+ }
+ }
+ cu_.mir_graph->num_blocks_ = count;
+ ASSERT_EQ(count, cu_.mir_graph->block_list_.Size());
+ cu_.mir_graph->entry_block_ = cu_.mir_graph->block_list_.Get(1);
+ ASSERT_EQ(kEntryBlock, cu_.mir_graph->entry_block_->block_type);
+ cu_.mir_graph->exit_block_ = cu_.mir_graph->block_list_.Get(2);
+ ASSERT_EQ(kExitBlock, cu_.mir_graph->exit_block_->block_type);
+ }
+
+ template <size_t count>
+ void PrepareBasicBlocks(const BBDef (&defs)[count]) {
+ DoPrepareBasicBlocks(defs, count);
+ }
+
+ void DoPrepareMIRs(const MIRDef* defs, size_t count) {
+ mir_count_ = count;
+ mirs_ = reinterpret_cast<MIR*>(cu_.arena.Alloc(sizeof(MIR) * count, kArenaAllocMIR));
+ uint64_t merged_df_flags = 0u;
+ for (size_t i = 0u; i != count; ++i) {
+ const MIRDef* def = &defs[i];
+ MIR* mir = &mirs_[i];
+ mir->dalvikInsn.opcode = def->opcode;
+ ASSERT_LT(def->bbid, cu_.mir_graph->block_list_.Size());
+ BasicBlock* bb = cu_.mir_graph->block_list_.Get(def->bbid);
+ cu_.mir_graph->AppendMIR(bb, mir);
+ if (def->opcode >= Instruction::SGET && def->opcode <= Instruction::SPUT_SHORT) {
+ ASSERT_LT(def->field_or_method_info, cu_.mir_graph->sfield_lowering_infos_.Size());
+ mir->meta.sfield_lowering_info = def->field_or_method_info;
+ }
+ mir->ssa_rep = nullptr;
+ mir->offset = 2 * i; // All insns need to be at least 2 code units long.
+ mir->width = 2u;
+ mir->optimization_flags = 0u;
+ merged_df_flags |= MIRGraph::oat_data_flow_attributes_[def->opcode];
+ }
+ cu_.mir_graph->merged_df_flags_ = merged_df_flags;
+
+ code_item_ = static_cast<DexFile::CodeItem*>(
+ cu_.arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc));
+ memset(code_item_, 0, sizeof(DexFile::CodeItem));
+ code_item_->insns_size_in_code_units_ = 2u * count;
+ cu_.mir_graph->current_code_item_ = cu_.code_item = code_item_;
+ }
+
+ template <size_t count>
+ void PrepareMIRs(const MIRDef (&defs)[count]) {
+ DoPrepareMIRs(defs, count);
+ }
+
+ void PerformClassInitCheckElimination() {
+ cu_.mir_graph->ComputeDFSOrders();
+ bool gate_result = cu_.mir_graph->EliminateClassInitChecksGate();
+ ASSERT_TRUE(gate_result);
+ RepeatingPreOrderDfsIterator iterator(cu_.mir_graph.get());
+ bool change = false;
+ for (BasicBlock *bb = iterator.Next(change); bb != 0; bb = iterator.Next(change)) {
+ change = cu_.mir_graph->EliminateClassInitChecks(bb);
+ }
+ cu_.mir_graph->EliminateClassInitChecksEnd();
+ }
+
+ ClassInitCheckEliminationTest()
+ : pool_(),
+ cu_(&pool_),
+ mir_count_(0u),
+ mirs_(nullptr),
+ code_item_(nullptr) {
+ cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
+ }
+
+ ArenaPool pool_;
+ CompilationUnit cu_;
+ size_t mir_count_;
+ MIR* mirs_;
+ DexFile::CodeItem* code_item_;
+};
+
+TEST_F(ClassInitCheckEliminationTest, SingleBlock) {
+ static const SFieldDef sfields[] = {
+ { 0u, 1u, 0u, 0u },
+ { 1u, 1u, 1u, 1u },
+ { 2u, 1u, 2u, 2u },
+ { 3u, 1u, 3u, 3u }, // Same declaring class as sfield[4].
+ { 4u, 1u, 3u, 4u }, // Same declaring class as sfield[3].
+ { 5u, 0u, 0u, 0u }, // Unresolved.
+ };
+ static const BBDef bbs[] = {
+ DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+ DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+ DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(3)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(1)),
+ };
+ static const MIRDef mirs[] = {
+ DEF_MIR(Instruction::SPUT, 3u, 5u), // Unresolved.
+ DEF_MIR(Instruction::SPUT, 3u, 0u),
+ DEF_MIR(Instruction::SGET, 3u, 1u),
+ DEF_MIR(Instruction::SGET, 3u, 2u),
+ DEF_MIR(Instruction::SGET, 3u, 5u), // Unresolved.
+ DEF_MIR(Instruction::SGET, 3u, 0u),
+ DEF_MIR(Instruction::SGET, 3u, 1u),
+ DEF_MIR(Instruction::SGET, 3u, 2u),
+ DEF_MIR(Instruction::SGET, 3u, 5u), // Unresolved.
+ DEF_MIR(Instruction::SGET, 3u, 3u),
+ DEF_MIR(Instruction::SGET, 3u, 4u),
+ };
+ static const bool expected_ignore_clinit_check[] = {
+ false, false, false, false, false, true, true, true, false, false, true
+ };
+
+ PrepareSFields(sfields);
+ PrepareBasicBlocks(bbs);
+ PrepareMIRs(mirs);
+ PerformClassInitCheckElimination();
+ ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
+ for (size_t i = 0u; i != arraysize(mirs); ++i) {
+ EXPECT_EQ(expected_ignore_clinit_check[i],
+ (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
+ }
+}
+
+TEST_F(ClassInitCheckEliminationTest, Diamond) {
+ static const SFieldDef sfields[] = {
+ { 0u, 1u, 0u, 0u },
+ { 1u, 1u, 1u, 1u },
+ { 2u, 1u, 2u, 2u },
+ { 3u, 1u, 3u, 3u },
+ { 4u, 1u, 4u, 4u },
+ { 5u, 1u, 5u, 5u },
+ { 6u, 1u, 6u, 6u },
+ { 7u, 1u, 7u, 7u },
+ { 8u, 1u, 8u, 8u }, // Same declaring class as sfield[9].
+ { 9u, 1u, 8u, 9u }, // Same declaring class as sfield[8].
+ { 10u, 0u, 0u, 0u }, // Unresolved.
+ };
+ static const BBDef bbs[] = {
+ DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+ DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+ DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)),
+ };
+ static const MIRDef mirs[] = {
+ // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
+ DEF_MIR(Instruction::SGET, 3u, 10u), // Unresolved.
+ DEF_MIR(Instruction::SPUT, 3u, 10u), // Unresolved.
+ DEF_MIR(Instruction::SPUT, 3u, 0u),
+ DEF_MIR(Instruction::SGET, 6u, 0u), // Eliminated (block #3 dominates #6).
+ DEF_MIR(Instruction::SPUT, 4u, 1u),
+ DEF_MIR(Instruction::SGET, 6u, 1u), // Not eliminated (block #4 doesn't dominate #6).
+ DEF_MIR(Instruction::SGET, 3u, 2u),
+ DEF_MIR(Instruction::SGET, 4u, 2u), // Eliminated (block #3 dominates #4).
+ DEF_MIR(Instruction::SGET, 3u, 3u),
+ DEF_MIR(Instruction::SGET, 5u, 3u), // Eliminated (block #3 dominates #5).
+ DEF_MIR(Instruction::SGET, 3u, 4u),
+ DEF_MIR(Instruction::SGET, 6u, 4u), // Eliminated (block #3 dominates #6).
+ DEF_MIR(Instruction::SGET, 4u, 5u),
+ DEF_MIR(Instruction::SGET, 6u, 5u), // Not eliminated (block #4 doesn't dominate #6).
+ DEF_MIR(Instruction::SGET, 5u, 6u),
+ DEF_MIR(Instruction::SGET, 6u, 6u), // Not eliminated (block #5 doesn't dominate #6).
+ DEF_MIR(Instruction::SGET, 4u, 7u),
+ DEF_MIR(Instruction::SGET, 5u, 7u),
+ DEF_MIR(Instruction::SGET, 6u, 7u), // Eliminated (initialized in both blocks #3 and #4).
+ DEF_MIR(Instruction::SGET, 4u, 8u),
+ DEF_MIR(Instruction::SGET, 5u, 9u),
+ DEF_MIR(Instruction::SGET, 6u, 8u), // Eliminated (with sfield[9] in block #5).
+ DEF_MIR(Instruction::SPUT, 6u, 9u), // Eliminated (with sfield[8] in block #4).
+ };
+ static const bool expected_ignore_clinit_check[] = {
+ false, false, // Unresolved: sfield[10], method[2]
+ false, true, // sfield[0]
+ false, false, // sfield[1]
+ false, true, // sfield[2]
+ false, true, // sfield[3]
+ false, true, // sfield[4]
+ false, false, // sfield[5]
+ false, false, // sfield[6]
+ false, false, true, // sfield[7]
+ false, false, true, true, // sfield[8], sfield[9]
+ };
+
+ PrepareSFields(sfields);
+ PrepareBasicBlocks(bbs);
+ PrepareMIRs(mirs);
+ PerformClassInitCheckElimination();
+ ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
+ for (size_t i = 0u; i != arraysize(mirs); ++i) {
+ EXPECT_EQ(expected_ignore_clinit_check[i],
+ (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
+ }
+}
+
+TEST_F(ClassInitCheckEliminationTest, Loop) {
+ static const SFieldDef sfields[] = {
+ { 0u, 1u, 0u, 0u },
+ { 1u, 1u, 1u, 1u },
+ };
+ static const BBDef bbs[] = {
+ DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+ DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+ DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)), // "taken" loops to self.
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
+ };
+ static const MIRDef mirs[] = {
+ DEF_MIR(Instruction::SGET, 3u, 0u),
+ DEF_MIR(Instruction::SGET, 4u, 1u),
+ DEF_MIR(Instruction::SGET, 5u, 0u), // Eliminated.
+ DEF_MIR(Instruction::SGET, 5u, 1u), // Eliminated.
+ };
+ static const bool expected_ignore_clinit_check[] = {
+ false, false, true, true
+ };
+
+ PrepareSFields(sfields);
+ PrepareBasicBlocks(bbs);
+ PrepareMIRs(mirs);
+ PerformClassInitCheckElimination();
+ ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
+ for (size_t i = 0u; i != arraysize(mirs); ++i) {
+ EXPECT_EQ(expected_ignore_clinit_check[i],
+ (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
+ }
+}
+
+TEST_F(ClassInitCheckEliminationTest, Catch) {
+ static const SFieldDef sfields[] = {
+ { 0u, 1u, 0u, 0u },
+ { 1u, 1u, 1u, 1u },
+ };
+ static const BBDef bbs[] = {
+ DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+ DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+ DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED1(1)),
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)), // Catch handler.
+ DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)),
+ };
+ static const MIRDef mirs[] = {
+ DEF_MIR(Instruction::SGET, 3u, 0u),
+ DEF_MIR(Instruction::SGET, 3u, 1u),
+ DEF_MIR(Instruction::SGET, 4u, 1u),
+ DEF_MIR(Instruction::SGET, 5u, 0u), // Not eliminated.
+ DEF_MIR(Instruction::SGET, 5u, 1u), // Eliminated.
+ };
+ static const bool expected_ignore_clinit_check[] = {
+ false, false, false, false, true
+ };
+
+ PrepareSFields(sfields);
+ PrepareBasicBlocks(bbs);
+ BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(4u);
+ catch_handler->catch_entry = true;
+ PrepareMIRs(mirs);
+ PerformClassInitCheckElimination();
+ ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
+ for (size_t i = 0u; i != arraysize(mirs); ++i) {
+ EXPECT_EQ(expected_ignore_clinit_check[i],
+ (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
+ }
+}
+
+} // namespace art