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->SSATransformationStart();
192    cu_.mir_graph->ComputeDFSOrders();
193    cu_.mir_graph->ComputeDominators();
194    cu_.mir_graph->ComputeTopologicalSortOrder();
195    cu_.mir_graph->SSATransformationEnd();
196    bool gate_result = cu_.mir_graph->EliminateClassInitChecksGate();
197    ASSERT_TRUE(gate_result);
198    LoopRepeatingTopologicalSortIterator iterator(cu_.mir_graph.get());
199    bool change = false;
200    for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) {
201      change = cu_.mir_graph->EliminateClassInitChecks(bb);
202    }
203    cu_.mir_graph->EliminateClassInitChecksEnd();
204  }
205
206  ClassInitCheckEliminationTest()
207      : pool_(),
208        cu_(&pool_),
209        mir_count_(0u),
210        mirs_(nullptr),
211        code_item_(nullptr) {
212    cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
213  }
214
215  ArenaPool pool_;
216  CompilationUnit cu_;
217  size_t mir_count_;
218  MIR* mirs_;
219  DexFile::CodeItem* code_item_;
220};
221
222TEST_F(ClassInitCheckEliminationTest, SingleBlock) {
223  static const SFieldDef sfields[] = {
224      { 0u, 1u, 0u, 0u },
225      { 1u, 1u, 1u, 1u },
226      { 2u, 1u, 2u, 2u },
227      { 3u, 1u, 3u, 3u },  // Same declaring class as sfield[4].
228      { 4u, 1u, 3u, 4u },  // Same declaring class as sfield[3].
229      { 5u, 0u, 0u, 0u },  // Unresolved.
230  };
231  static const BBDef bbs[] = {
232      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
233      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
234      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(3)),
235      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(1)),
236  };
237  static const MIRDef mirs[] = {
238      DEF_MIR(Instruction::SPUT, 3u, 5u),  // Unresolved.
239      DEF_MIR(Instruction::SPUT, 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, 0u),
244      DEF_MIR(Instruction::SGET, 3u, 1u),
245      DEF_MIR(Instruction::SGET, 3u, 2u),
246      DEF_MIR(Instruction::SGET, 3u, 5u),  // Unresolved.
247      DEF_MIR(Instruction::SGET, 3u, 3u),
248      DEF_MIR(Instruction::SGET, 3u, 4u),
249  };
250  static const bool expected_ignore_clinit_check[] = {
251      false, false, false, false, true, true, true, true, true, false, true
252  };
253
254  PrepareSFields(sfields);
255  PrepareBasicBlocks(bbs);
256  PrepareMIRs(mirs);
257  PerformClassInitCheckElimination();
258  ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
259  for (size_t i = 0u; i != arraysize(mirs); ++i) {
260    EXPECT_EQ(expected_ignore_clinit_check[i],
261              (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
262  }
263}
264
265TEST_F(ClassInitCheckEliminationTest, Diamond) {
266  static const SFieldDef sfields[] = {
267      { 0u, 1u, 0u, 0u },
268      { 1u, 1u, 1u, 1u },
269      { 2u, 1u, 2u, 2u },
270      { 3u, 1u, 3u, 3u },
271      { 4u, 1u, 4u, 4u },
272      { 5u, 1u, 5u, 5u },
273      { 6u, 1u, 6u, 6u },
274      { 7u, 1u, 7u, 7u },
275      { 8u, 1u, 8u, 8u },  // Same declaring class as sfield[9].
276      { 9u, 1u, 8u, 9u },  // Same declaring class as sfield[8].
277      { 10u, 0u, 0u, 0u },  // Unresolved.
278  };
279  static const BBDef bbs[] = {
280      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
281      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
282      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
283      DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)),
284      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
285      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
286      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)),
287  };
288  static const MIRDef mirs[] = {
289      // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
290      DEF_MIR(Instruction::SGET, 3u, 10u),  // Unresolved.
291      DEF_MIR(Instruction::SPUT, 3u, 10u),  // Unresolved.
292      DEF_MIR(Instruction::SPUT, 3u, 0u),
293      DEF_MIR(Instruction::SGET, 6u, 0u),  // Eliminated (block #3 dominates #6).
294      DEF_MIR(Instruction::SPUT, 4u, 1u),
295      DEF_MIR(Instruction::SGET, 6u, 1u),  // Not eliminated (block #4 doesn't dominate #6).
296      DEF_MIR(Instruction::SGET, 3u, 2u),
297      DEF_MIR(Instruction::SGET, 4u, 2u),  // Eliminated (block #3 dominates #4).
298      DEF_MIR(Instruction::SGET, 3u, 3u),
299      DEF_MIR(Instruction::SGET, 5u, 3u),  // Eliminated (block #3 dominates #5).
300      DEF_MIR(Instruction::SGET, 3u, 4u),
301      DEF_MIR(Instruction::SGET, 6u, 4u),  // Eliminated (block #3 dominates #6).
302      DEF_MIR(Instruction::SGET, 4u, 5u),
303      DEF_MIR(Instruction::SGET, 6u, 5u),  // Not eliminated (block #4 doesn't dominate #6).
304      DEF_MIR(Instruction::SGET, 5u, 6u),
305      DEF_MIR(Instruction::SGET, 6u, 6u),  // Not eliminated (block #5 doesn't dominate #6).
306      DEF_MIR(Instruction::SGET, 4u, 7u),
307      DEF_MIR(Instruction::SGET, 5u, 7u),
308      DEF_MIR(Instruction::SGET, 6u, 7u),  // Eliminated (initialized in both blocks #3 and #4).
309      DEF_MIR(Instruction::SGET, 4u, 8u),
310      DEF_MIR(Instruction::SGET, 5u, 9u),
311      DEF_MIR(Instruction::SGET, 6u, 8u),  // Eliminated (with sfield[9] in block #5).
312      DEF_MIR(Instruction::SPUT, 6u, 9u),  // Eliminated (with sfield[8] in block #4).
313  };
314  static const bool expected_ignore_clinit_check[] = {
315      false, true,          // Unresolved: sfield[10], method[2]
316      false, true,          // sfield[0]
317      false, false,         // sfield[1]
318      false, true,          // sfield[2]
319      false, true,          // sfield[3]
320      false, true,          // sfield[4]
321      false, false,         // sfield[5]
322      false, false,         // sfield[6]
323      false, false, true,   // sfield[7]
324      false, false, true, true,  // sfield[8], sfield[9]
325  };
326
327  PrepareSFields(sfields);
328  PrepareBasicBlocks(bbs);
329  PrepareMIRs(mirs);
330  PerformClassInitCheckElimination();
331  ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
332  for (size_t i = 0u; i != arraysize(mirs); ++i) {
333    EXPECT_EQ(expected_ignore_clinit_check[i],
334              (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
335  }
336}
337
338TEST_F(ClassInitCheckEliminationTest, Loop) {
339  static const SFieldDef sfields[] = {
340      { 0u, 1u, 0u, 0u },
341      { 1u, 1u, 1u, 1u },
342  };
343  static const BBDef bbs[] = {
344      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
345      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
346      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
347      DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
348      DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)),  // "taken" loops to self.
349      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
350  };
351  static const MIRDef mirs[] = {
352      DEF_MIR(Instruction::SGET, 3u, 0u),
353      DEF_MIR(Instruction::SGET, 4u, 1u),
354      DEF_MIR(Instruction::SGET, 5u, 0u),  // Eliminated.
355      DEF_MIR(Instruction::SGET, 5u, 1u),  // Eliminated.
356  };
357  static const bool expected_ignore_clinit_check[] = {
358      false, false, true, true
359  };
360
361  PrepareSFields(sfields);
362  PrepareBasicBlocks(bbs);
363  PrepareMIRs(mirs);
364  PerformClassInitCheckElimination();
365  ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
366  for (size_t i = 0u; i != arraysize(mirs); ++i) {
367    EXPECT_EQ(expected_ignore_clinit_check[i],
368              (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
369  }
370}
371
372TEST_F(ClassInitCheckEliminationTest, Catch) {
373  static const SFieldDef sfields[] = {
374      { 0u, 1u, 0u, 0u },
375      { 1u, 1u, 1u, 1u },
376      { 2u, 1u, 2u, 2u },
377      { 3u, 1u, 3u, 3u },
378  };
379  static const BBDef bbs[] = {
380      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
381      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
382      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
383      DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),     // The top.
384      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),     // The throwing insn.
385      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),     // Catch handler.
386      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)),  // The merged block.
387  };
388  static const MIRDef mirs[] = {
389      DEF_MIR(Instruction::SGET, 3u, 0u),  // Before the exception edge.
390      DEF_MIR(Instruction::SGET, 3u, 1u),  // Before the exception edge.
391      DEF_MIR(Instruction::SGET, 4u, 2u),  // After the exception edge.
392      DEF_MIR(Instruction::SGET, 4u, 3u),  // After the exception edge.
393      DEF_MIR(Instruction::SGET, 5u, 0u),  // In catch handler; class init check eliminated.
394      DEF_MIR(Instruction::SGET, 5u, 2u),  // In catch handler; class init check not eliminated.
395      DEF_MIR(Instruction::SGET, 6u, 0u),  // Class init check eliminated.
396      DEF_MIR(Instruction::SGET, 6u, 1u),  // Class init check eliminated.
397      DEF_MIR(Instruction::SGET, 6u, 2u),  // Class init check eliminated.
398      DEF_MIR(Instruction::SGET, 6u, 3u),  // Class init check not eliminated.
399  };
400  static const bool expected_ignore_clinit_check[] = {
401      false, false, false, false, true, false, true, true, true, false
402  };
403
404  PrepareSFields(sfields);
405  PrepareBasicBlocks(bbs);
406  BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(5u);
407  catch_handler->catch_entry = true;
408  // Add successor block info to the check block.
409  BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u);
410  check_bb->successor_block_list_type = kCatch;
411  check_bb->successor_blocks = new (&cu_.arena) GrowableArray<SuccessorBlockInfo*>(
412      &cu_.arena, 2, kGrowableArraySuccessorBlocks);
413  SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*>
414      (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor));
415  successor_block_info->block = catch_handler->id;
416  check_bb->successor_blocks->Insert(successor_block_info);
417  PrepareMIRs(mirs);
418  PerformClassInitCheckElimination();
419  ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
420  for (size_t i = 0u; i != arraysize(mirs); ++i) {
421    EXPECT_EQ(expected_ignore_clinit_check[i],
422              (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i;
423  }
424}
425
426}  // namespace art
427