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
24 namespace art {
25
26 class 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
DoPrepareSFields(const SFieldDef * defs,size_t count)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>
PrepareSFields(const SFieldDef (& defs)[count])97 void PrepareSFields(const SFieldDef (&defs)[count]) {
98 DoPrepareSFields(defs, count);
99 }
100
DoPrepareBasicBlocks(const BBDef * defs,size_t count)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>
PrepareBasicBlocks(const BBDef (& defs)[count])152 void PrepareBasicBlocks(const BBDef (&defs)[count]) {
153 DoPrepareBasicBlocks(defs, count);
154 }
155
DoPrepareMIRs(const MIRDef * defs,size_t count)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>
PrepareMIRs(const MIRDef (& defs)[count])186 void PrepareMIRs(const MIRDef (&defs)[count]) {
187 DoPrepareMIRs(defs, count);
188 }
189
PerformClassInitCheckElimination()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
ClassInitCheckEliminationTest()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
TEST_F(ClassInitCheckEliminationTest,SingleBlock)222 TEST_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
TEST_F(ClassInitCheckEliminationTest,Diamond)265 TEST_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
TEST_F(ClassInitCheckEliminationTest,Loop)338 TEST_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
TEST_F(ClassInitCheckEliminationTest,Catch)372 TEST_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