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

1 files changed, 406 insertions, 0 deletions

diff --git a/compiler/dex/mir_optimization_test.cc b/compiler/dex/mir_optimization_test.cc
new file mode 100644
index 0000000000..f499364118
--- /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