mir_optimization_test.cc revision ef562fdef7e0071cae11e07a9e53fb152d0934b8 
1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <vector>
18
19#include "compiler_internals.h"
20#include "dataflow_iterator.h"
21#include "dataflow_iterator-inl.h"
22#include "gtest/gtest.h"
23
24namespace art {
25
26class ClassInitCheckEliminationTest : public testing::Test {
27 protected:
28  struct SFieldDef {
29    uint16_t field_idx;
30    uintptr_t declaring_dex_file;
31    uint16_t declaring_class_idx;
32    uint16_t declaring_field_idx;
33  };
34
35  struct BBDef {
36    static constexpr size_t kMaxSuccessors = 4;
37    static constexpr size_t kMaxPredecessors = 4;
38
39    BBType type;
40    size_t num_successors;
41    BasicBlockId successors[kMaxPredecessors];
42    size_t num_predecessors;
43    BasicBlockId predecessors[kMaxPredecessors];
44  };
45
46  struct MIRDef {
47    Instruction::Code opcode;
48    BasicBlockId bbid;
49    uint32_t field_or_method_info;
50  };
51
52#define DEF_SUCC0() \
53    0u, { }
54#define DEF_SUCC1(s1) \
55    1u, { s1 }
56#define DEF_SUCC2(s1, s2) \
57    2u, { s1, s2 }
58#define DEF_SUCC3(s1, s2, s3) \
59    3u, { s1, s2, s3 }
60#define DEF_SUCC4(s1, s2, s3, s4) \
61    4u, { s1, s2, s3, s4 }
62#define DEF_PRED0() \
63    0u, { }
64#define DEF_PRED1(p1) \
65    1u, { p1 }
66#define DEF_PRED2(p1, p2) \
67    2u, { p1, p2 }
68#define DEF_PRED3(p1, p2, p3) \
69    3u, { p1, p2, p3 }
70#define DEF_PRED4(p1, p2, p3, p4) \
71    4u, { p1, p2, p3, p4 }
72#define DEF_BB(type, succ, pred) \
73    { type, succ, pred }
74
75#define DEF_MIR(opcode, bb, field_info) \
76    { opcode, bb, field_info }
77
78  void DoPrepareSFields(const SFieldDef* defs, size_t count) {
79    cu_.mir_graph->sfield_lowering_infos_.Reset();
80    cu_.mir_graph->sfield_lowering_infos_.Resize(count);
81    for (size_t i = 0u; i != count; ++i) {
82      const SFieldDef* def = &defs[i];
83      MirSFieldLoweringInfo field_info(def->field_idx);
84      if (def->declaring_dex_file != 0u) {
85        field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
86        field_info.declaring_class_idx_ = def->declaring_class_idx;
87        field_info.declaring_field_idx_ = def->declaring_field_idx;
88        field_info.flags_ = MirSFieldLoweringInfo::kFlagIsStatic;
89      }
90      ASSERT_EQ(def->declaring_dex_file != 0u, field_info.IsResolved());
91      ASSERT_FALSE(field_info.IsInitialized());
92      cu_.mir_graph->sfield_lowering_infos_.Insert(field_info);
93    }
94  }
95
96  template <size_t count>
97  void PrepareSFields(const SFieldDef (&defs)[count]) {
98    DoPrepareSFields(defs, count);
99  }
100
101  void DoPrepareBasicBlocks(const BBDef* defs, size_t count) {
102    cu_.mir_graph->block_id_map_.clear();
103    cu_.mir_graph->block_list_.Reset();
104    ASSERT_LT(3u, count);  // null, entry, exit and at least one bytecode block.
105    ASSERT_EQ(kNullBlock, defs[0].type);
106    ASSERT_EQ(kEntryBlock, defs[1].type);
107    ASSERT_EQ(kExitBlock, defs[2].type);
108    for (size_t i = 0u; i != count; ++i) {
109      const BBDef* def = &defs[i];
110      BasicBlock* bb = cu_.mir_graph->NewMemBB(def->type, i);
111      cu_.mir_graph->block_list_.Insert(bb);
112      if (def->num_successors <= 2) {
113        bb->successor_block_list_type = kNotUsed;
114        bb->successor_blocks = nullptr;
115        bb->fall_through = (def->num_successors >= 1) ? def->successors[0] : 0u;
116        bb->taken = (def->num_successors >= 2) ? def->successors[1] : 0u;
117      } else {
118        bb->successor_block_list_type = kPackedSwitch;
119        bb->fall_through = 0u;
120        bb->taken = 0u;
121        bb->successor_blocks = new (&cu_.arena) GrowableArray<SuccessorBlockInfo*>(
122            &cu_.arena, def->num_successors, kGrowableArraySuccessorBlocks);
123        for (size_t j = 0u; j != def->num_successors; ++j) {
124          SuccessorBlockInfo* successor_block_info =
125              static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo),
126                                                               kArenaAllocSuccessor));
127          successor_block_info->block = j;
128          successor_block_info->key = 0u;  // Not used by class init check elimination.
129          bb->successor_blocks->Insert(successor_block_info);
130        }
131      }
132      bb->predecessors = new (&cu_.arena) GrowableArray<BasicBlockId>(
133          &cu_.arena, def->num_predecessors, kGrowableArrayPredecessors);
134      for (size_t j = 0u; j != def->num_predecessors; ++j) {
135        ASSERT_NE(0u, def->predecessors[j]);
136        bb->predecessors->Insert(def->predecessors[j]);
137      }
138      if (def->type == kDalvikByteCode || def->type == kEntryBlock || def->type == kExitBlock) {
139        bb->data_flow_info = static_cast<BasicBlockDataFlow*>(
140            cu_.arena.Alloc(sizeof(BasicBlockDataFlow), kArenaAllocDFInfo));
141      }
142    }
143    cu_.mir_graph->num_blocks_ = count;
144    ASSERT_EQ(count, cu_.mir_graph->block_list_.Size());
145    cu_.mir_graph->entry_block_ = cu_.mir_graph->block_list_.Get(1);
146    ASSERT_EQ(kEntryBlock, cu_.mir_graph->entry_block_->block_type);
147    cu_.mir_graph->exit_block_ = cu_.mir_graph->block_list_.Get(2);
148    ASSERT_EQ(kExitBlock, cu_.mir_graph->exit_block_->block_type);
149  }
150
151  template <size_t count>
152  void PrepareBasicBlocks(const BBDef (&defs)[count]) {
153    DoPrepareBasicBlocks(defs, count);
154  }
155
156  void DoPrepareMIRs(const MIRDef* defs, size_t count) {
157    mir_count_ = count;
158    mirs_ = reinterpret_cast<MIR*>(cu_.arena.Alloc(sizeof(MIR) * count, kArenaAllocMIR));
159    uint64_t merged_df_flags = 0u;
160    for (size_t i = 0u; i != count; ++i) {
161      const MIRDef* def = &defs[i];
162      MIR* mir = &mirs_[i];
163      mir->dalvikInsn.opcode = def->opcode;
164      ASSERT_LT(def->bbid, cu_.mir_graph->block_list_.Size());
165      BasicBlock* bb = cu_.mir_graph->block_list_.Get(def->bbid);
166      bb->AppendMIR(mir);
167      if (def->opcode >= Instruction::SGET && def->opcode <= Instruction::SPUT_SHORT) {
168        ASSERT_LT(def->field_or_method_info, cu_.mir_graph->sfield_lowering_infos_.Size());
169        mir->meta.sfield_lowering_info = def->field_or_method_info;
170      }
171      mir->ssa_rep = nullptr;
172      mir->offset = 2 * i;  // All insns need to be at least 2 code units long.
173      mir->optimization_flags = 0u;
174      merged_df_flags |= MIRGraph::GetDataFlowAttributes(def->opcode);
175    }
176    cu_.mir_graph->merged_df_flags_ = merged_df_flags;
177
178    code_item_ = static_cast<DexFile::CodeItem*>(
179        cu_.arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc));
180    memset(code_item_, 0, sizeof(DexFile::CodeItem));
181    code_item_->insns_size_in_code_units_ = 2u * count;
182    cu_.mir_graph->current_code_item_ = cu_.code_item = code_item_;
183  }
184
185  template <size_t count>
186  void PrepareMIRs(const MIRDef (&defs)[count]) {
187    DoPrepareMIRs(defs, count);
188  }
189
190  void PerformClassInitCheckElimination() {
191    cu_.mir_graph->ComputeDFSOrders();
192    bool gate_result = cu_.mir_graph->EliminateClassInitChecksGate();
193    ASSERT_TRUE(gate_result);
194    RepeatingPreOrderDfsIterator iterator(cu_.mir_graph.get());
195    bool change = false;
196    for (BasicBlock *bb = iterator.Next(change); bb != 0; bb = iterator.Next(change)) {
197      change = cu_.mir_graph->EliminateClassInitChecks(bb);
198    }
199    cu_.mir_graph->EliminateClassInitChecksEnd();
200  }
201
202  ClassInitCheckEliminationTest()
203      : pool_(),
204        cu_(&pool_),
205        mir_count_(0u),
206        mirs_(nullptr),
207        code_item_(nullptr) {
208    cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
209  }
210
211  ArenaPool pool_;
212  CompilationUnit cu_;
213  size_t mir_count_;
214  MIR* mirs_;
215  DexFile::CodeItem* code_item_;
216};
217
218TEST_F(ClassInitCheckEliminationTest, SingleBlock) {
219  static const SFieldDef sfields[] = {
220      { 0u, 1u, 0u, 0u },
221      { 1u, 1u, 1u, 1u },
222      { 2u, 1u, 2u, 2u },
223      { 3u, 1u, 3u, 3u },  // Same declaring class as sfield[4].
224      { 4u, 1u, 3u, 4u },  // Same declaring class as sfield[3].
225      { 5u, 0u, 0u, 0u },  // Unresolved.
226  };
227  static const BBDef bbs[] = {
228      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
229      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
230      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(3)),
231      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(1)),
232  };
233  static const MIRDef mirs[] = {
234      DEF_MIR(Instruction::SPUT, 3u, 5u),  // Unresolved.
235      DEF_MIR(Instruction::SPUT, 3u, 0u),
236      DEF_MIR(Instruction::SGET, 3u, 1u),
237      DEF_MIR(Instruction::SGET, 3u, 2u),
238      DEF_MIR(Instruction::SGET, 3u, 5u),  // Unresolved.
239      DEF_MIR(Instruction::SGET, 3u, 0u),
240      DEF_MIR(Instruction::SGET, 3u, 1u),
241      DEF_MIR(Instruction::SGET, 3u, 2u),
242      DEF_MIR(Instruction::SGET, 3u, 5u),  // Unresolved.
243      DEF_MIR(Instruction::SGET, 3u, 3u),
244      DEF_MIR(Instruction::SGET, 3u, 4u),
245  };
246  static const bool expected_ignore_clinit_check[] = {
247      false, false, false, false, false, true, true, true, false, false, true
248  };
249
250  PrepareSFields(sfields);
251  PrepareBasicBlocks(bbs);
252  PrepareMIRs(mirs);
253  PerformClassInitCheckElimination();
254  ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
255  for (size_t i = 0u; i != arraysize(mirs); ++i) {
256    EXPECT_EQ(expected_ignore_clinit_check[i],
257              (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
258  }
259}
260
261TEST_F(ClassInitCheckEliminationTest, Diamond) {
262  static const SFieldDef sfields[] = {
263      { 0u, 1u, 0u, 0u },
264      { 1u, 1u, 1u, 1u },
265      { 2u, 1u, 2u, 2u },
266      { 3u, 1u, 3u, 3u },
267      { 4u, 1u, 4u, 4u },
268      { 5u, 1u, 5u, 5u },
269      { 6u, 1u, 6u, 6u },
270      { 7u, 1u, 7u, 7u },
271      { 8u, 1u, 8u, 8u },  // Same declaring class as sfield[9].
272      { 9u, 1u, 8u, 9u },  // Same declaring class as sfield[8].
273      { 10u, 0u, 0u, 0u },  // Unresolved.
274  };
275  static const BBDef bbs[] = {
276      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
277      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
278      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
279      DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)),
280      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
281      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
282      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)),
283  };
284  static const MIRDef mirs[] = {
285      // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
286      DEF_MIR(Instruction::SGET, 3u, 10u),  // Unresolved.
287      DEF_MIR(Instruction::SPUT, 3u, 10u),  // Unresolved.
288      DEF_MIR(Instruction::SPUT, 3u, 0u),
289      DEF_MIR(Instruction::SGET, 6u, 0u),  // Eliminated (block #3 dominates #6).
290      DEF_MIR(Instruction::SPUT, 4u, 1u),
291      DEF_MIR(Instruction::SGET, 6u, 1u),  // Not eliminated (block #4 doesn't dominate #6).
292      DEF_MIR(Instruction::SGET, 3u, 2u),
293      DEF_MIR(Instruction::SGET, 4u, 2u),  // Eliminated (block #3 dominates #4).
294      DEF_MIR(Instruction::SGET, 3u, 3u),
295      DEF_MIR(Instruction::SGET, 5u, 3u),  // Eliminated (block #3 dominates #5).
296      DEF_MIR(Instruction::SGET, 3u, 4u),
297      DEF_MIR(Instruction::SGET, 6u, 4u),  // Eliminated (block #3 dominates #6).
298      DEF_MIR(Instruction::SGET, 4u, 5u),
299      DEF_MIR(Instruction::SGET, 6u, 5u),  // Not eliminated (block #4 doesn't dominate #6).
300      DEF_MIR(Instruction::SGET, 5u, 6u),
301      DEF_MIR(Instruction::SGET, 6u, 6u),  // Not eliminated (block #5 doesn't dominate #6).
302      DEF_MIR(Instruction::SGET, 4u, 7u),
303      DEF_MIR(Instruction::SGET, 5u, 7u),
304      DEF_MIR(Instruction::SGET, 6u, 7u),  // Eliminated (initialized in both blocks #3 and #4).
305      DEF_MIR(Instruction::SGET, 4u, 8u),
306      DEF_MIR(Instruction::SGET, 5u, 9u),
307      DEF_MIR(Instruction::SGET, 6u, 8u),  // Eliminated (with sfield[9] in block #5).
308      DEF_MIR(Instruction::SPUT, 6u, 9u),  // Eliminated (with sfield[8] in block #4).
309  };
310  static const bool expected_ignore_clinit_check[] = {
311      false, false,         // Unresolved: sfield[10], method[2]
312      false, true,          // sfield[0]
313      false, false,         // sfield[1]
314      false, true,          // sfield[2]
315      false, true,          // sfield[3]
316      false, true,          // sfield[4]
317      false, false,         // sfield[5]
318      false, false,         // sfield[6]
319      false, false, true,   // sfield[7]
320      false, false, true, true,  // sfield[8], sfield[9]
321  };
322
323  PrepareSFields(sfields);
324  PrepareBasicBlocks(bbs);
325  PrepareMIRs(mirs);
326  PerformClassInitCheckElimination();
327  ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
328  for (size_t i = 0u; i != arraysize(mirs); ++i) {
329    EXPECT_EQ(expected_ignore_clinit_check[i],
330              (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
331  }
332}
333
334TEST_F(ClassInitCheckEliminationTest, Loop) {
335  static const SFieldDef sfields[] = {
336      { 0u, 1u, 0u, 0u },
337      { 1u, 1u, 1u, 1u },
338  };
339  static const BBDef bbs[] = {
340      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
341      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
342      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
343      DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
344      DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)),  // "taken" loops to self.
345      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
346  };
347  static const MIRDef mirs[] = {
348      DEF_MIR(Instruction::SGET, 3u, 0u),
349      DEF_MIR(Instruction::SGET, 4u, 1u),
350      DEF_MIR(Instruction::SGET, 5u, 0u),  // Eliminated.
351      DEF_MIR(Instruction::SGET, 5u, 1u),  // Eliminated.
352  };
353  static const bool expected_ignore_clinit_check[] = {
354      false, false, true, true
355  };
356
357  PrepareSFields(sfields);
358  PrepareBasicBlocks(bbs);
359  PrepareMIRs(mirs);
360  PerformClassInitCheckElimination();
361  ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
362  for (size_t i = 0u; i != arraysize(mirs); ++i) {
363    EXPECT_EQ(expected_ignore_clinit_check[i],
364              (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
365  }
366}
367
368TEST_F(ClassInitCheckEliminationTest, Catch) {
369  static const SFieldDef sfields[] = {
370      { 0u, 1u, 0u, 0u },
371      { 1u, 1u, 1u, 1u },
372  };
373  static const BBDef bbs[] = {
374      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
375      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
376      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
377      DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED1(1)),
378      DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)),  // Catch handler.
379      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)),
380  };
381  static const MIRDef mirs[] = {
382      DEF_MIR(Instruction::SGET, 3u, 0u),
383      DEF_MIR(Instruction::SGET, 3u, 1u),
384      DEF_MIR(Instruction::SGET, 4u, 1u),
385      DEF_MIR(Instruction::SGET, 5u, 0u),  // Not eliminated.
386      DEF_MIR(Instruction::SGET, 5u, 1u),  // Eliminated.
387  };
388  static const bool expected_ignore_clinit_check[] = {
389      false, false, false, false, true
390  };
391
392  PrepareSFields(sfields);
393  PrepareBasicBlocks(bbs);
394  BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(4u);
395  catch_handler->catch_entry = true;
396  PrepareMIRs(mirs);
397  PerformClassInitCheckElimination();
398  ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
399  for (size_t i = 0u; i != arraysize(mirs); ++i) {
400    EXPECT_EQ(expected_ignore_clinit_check[i],
401              (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
402  }
403}
404
405}  // namespace art
406