blob: e56e0160ca3d503ed58b51adcbfea4f510be1e42 [file] [log] [blame]
Vladimir Markof59f18b2014-02-17 15:53:57 +00001/*
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 "local_value_numbering.h"
20#include "compiler_internals.h"
21#include "gtest/gtest.h"
22
23namespace art {
24
25class LocalValueNumberingTest : public testing::Test {
26 protected:
27 struct IFieldDef {
28 uint16_t field_idx;
29 uintptr_t declaring_dex_file;
30 uint16_t declaring_field_idx;
31 bool is_volatile;
32 };
33
34 struct SFieldDef {
35 uint16_t field_idx;
36 uintptr_t declaring_dex_file;
37 uint16_t declaring_field_idx;
38 bool is_volatile;
39 };
40
41 struct MIRDef {
42 static constexpr size_t kMaxSsaDefs = 2;
43 static constexpr size_t kMaxSsaUses = 3;
44
45 Instruction::Code opcode;
46 int64_t value;
Vladimir Markobe0e5462014-02-26 11:24:15 +000047 uint32_t field_info;
Vladimir Markof59f18b2014-02-17 15:53:57 +000048 size_t num_uses;
49 int32_t uses[kMaxSsaUses];
50 size_t num_defs;
51 int32_t defs[kMaxSsaDefs];
52 };
53
54#define DEF_CONST(opcode, reg, value) \
55 { opcode, value, 0u, 0, { }, 1, { reg } }
56#define DEF_CONST_WIDE(opcode, reg, value) \
57 { opcode, value, 0u, 0, { }, 2, { reg, reg + 1 } }
Vladimir Markobe0e5462014-02-26 11:24:15 +000058#define DEF_IGET(opcode, reg, obj, field_info) \
59 { opcode, 0u, field_info, 1, { obj }, 1, { reg } }
60#define DEF_IGET_WIDE(opcode, reg, obj, field_info) \
61 { opcode, 0u, field_info, 1, { obj }, 2, { reg, reg + 1 } }
62#define DEF_IPUT(opcode, reg, obj, field_info) \
63 { opcode, 0u, field_info, 2, { reg, obj }, 0, { } }
64#define DEF_IPUT_WIDE(opcode, reg, obj, field_info) \
65 { opcode, 0u, field_info, 3, { reg, reg + 1, obj }, 0, { } }
66#define DEF_SGET(opcode, reg, field_info) \
67 { opcode, 0u, field_info, 0, { }, 1, { reg } }
68#define DEF_SGET_WIDE(opcode, reg, field_info) \
69 { opcode, 0u, field_info, 0, { }, 2, { reg, reg + 1 } }
70#define DEF_SPUT(opcode, reg, field_info) \
71 { opcode, 0u, field_info, 1, { reg }, 0, { } }
72#define DEF_SPUT_WIDE(opcode, reg, field_info) \
73 { opcode, 0u, field_info, 2, { reg, reg + 1 }, 0, { } }
Vladimir Markof59f18b2014-02-17 15:53:57 +000074#define DEF_INVOKE1(opcode, reg) \
75 { opcode, 0u, 0u, 1, { reg }, 0, { } }
76#define DEF_UNIQUE_REF(opcode, reg) \
77 { opcode, 0u, 0u, 0, { }, 1, { reg } } // CONST_CLASS, CONST_STRING, NEW_ARRAY, ...
78
79 void DoPrepareIFields(const IFieldDef* defs, size_t count) {
Vladimir Markobe0e5462014-02-26 11:24:15 +000080 cu_.mir_graph->ifield_lowering_infos_.Reset();
81 cu_.mir_graph->ifield_lowering_infos_.Resize(count);
82 for (size_t i = 0u; i != count; ++i) {
83 const IFieldDef* def = &defs[i];
84 MirIFieldLoweringInfo field_info(def->field_idx);
85 if (def->declaring_dex_file != 0u) {
86 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
87 field_info.declaring_field_idx_ = def->declaring_field_idx;
88 field_info.flags_ = 0u | // Without kFlagIsStatic.
89 (def->is_volatile ? MirIFieldLoweringInfo::kFlagIsVolatile : 0u);
90 }
91 cu_.mir_graph->ifield_lowering_infos_.Insert(field_info);
92 }
Vladimir Markof59f18b2014-02-17 15:53:57 +000093 }
94
95 template <size_t count>
96 void PrepareIFields(const IFieldDef (&defs)[count]) {
97 DoPrepareIFields(defs, count);
98 }
99
100 void DoPrepareSFields(const SFieldDef* defs, size_t count) {
Vladimir Markobe0e5462014-02-26 11:24:15 +0000101 cu_.mir_graph->sfield_lowering_infos_.Reset();
102 cu_.mir_graph->sfield_lowering_infos_.Resize(count);
103 for (size_t i = 0u; i != count; ++i) {
104 const SFieldDef* def = &defs[i];
105 MirSFieldLoweringInfo field_info(def->field_idx);
106 if (def->declaring_dex_file != 0u) {
107 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
108 field_info.declaring_field_idx_ = def->declaring_field_idx;
109 field_info.flags_ = MirSFieldLoweringInfo::kFlagIsStatic |
110 (def->is_volatile ? MirSFieldLoweringInfo::kFlagIsVolatile : 0u);
111 }
112 cu_.mir_graph->sfield_lowering_infos_.Insert(field_info);
113 }
Vladimir Markof59f18b2014-02-17 15:53:57 +0000114 }
115
116 template <size_t count>
117 void PrepareSFields(const SFieldDef (&defs)[count]) {
118 DoPrepareSFields(defs, count);
119 }
120
121 void DoPrepareMIRs(const MIRDef* defs, size_t count) {
122 mir_count_ = count;
Vladimir Marko83cc7ae2014-02-12 18:02:05 +0000123 mirs_ = reinterpret_cast<MIR*>(cu_.arena.Alloc(sizeof(MIR) * count, kArenaAllocMIR));
Vladimir Markof59f18b2014-02-17 15:53:57 +0000124 ssa_reps_.resize(count);
125 for (size_t i = 0u; i != count; ++i) {
126 const MIRDef* def = &defs[i];
127 MIR* mir = &mirs_[i];
128 mir->dalvikInsn.opcode = def->opcode;
129 mir->dalvikInsn.vB = static_cast<int32_t>(def->value);
130 mir->dalvikInsn.vB_wide = def->value;
Vladimir Markobe0e5462014-02-26 11:24:15 +0000131 if (def->opcode >= Instruction::IGET && def->opcode <= Instruction::IPUT_SHORT) {
132 ASSERT_LT(def->field_info, cu_.mir_graph->ifield_lowering_infos_.Size());
133 mir->meta.ifield_lowering_info = def->field_info;
134 } else if (def->opcode >= Instruction::SGET && def->opcode <= Instruction::SPUT_SHORT) {
135 ASSERT_LT(def->field_info, cu_.mir_graph->sfield_lowering_infos_.Size());
136 mir->meta.sfield_lowering_info = def->field_info;
137 }
Vladimir Markof59f18b2014-02-17 15:53:57 +0000138 mir->ssa_rep = &ssa_reps_[i];
139 mir->ssa_rep->num_uses = def->num_uses;
140 mir->ssa_rep->uses = const_cast<int32_t*>(def->uses); // Not modified by LVN.
141 mir->ssa_rep->fp_use = nullptr; // Not used by LVN.
142 mir->ssa_rep->num_defs = def->num_defs;
143 mir->ssa_rep->defs = const_cast<int32_t*>(def->defs); // Not modified by LVN.
144 mir->ssa_rep->fp_def = nullptr; // Not used by LVN.
145 mir->dalvikInsn.opcode = def->opcode;
146 mir->offset = i; // LVN uses offset only for debug output
Vladimir Markof59f18b2014-02-17 15:53:57 +0000147 mir->optimization_flags = 0u;
148
149 if (i != 0u) {
150 mirs_[i - 1u].next = mir;
151 }
152 }
153 mirs_[count - 1u].next = nullptr;
154 }
155
156 template <size_t count>
157 void PrepareMIRs(const MIRDef (&defs)[count]) {
158 DoPrepareMIRs(defs, count);
159 }
160
161 void PerformLVN() {
162 value_names_.resize(mir_count_);
163 for (size_t i = 0; i != mir_count_; ++i) {
Vladimir Marko83cc7ae2014-02-12 18:02:05 +0000164 value_names_[i] = lvn_->GetValueNumber(&mirs_[i]);
Vladimir Markof59f18b2014-02-17 15:53:57 +0000165 }
166 }
167
Vladimir Marko83cc7ae2014-02-12 18:02:05 +0000168 LocalValueNumberingTest()
169 : pool_(),
170 cu_(&pool_),
171 mir_count_(0u),
172 mirs_(nullptr),
173 lvn_(LocalValueNumbering::Create(&cu_)) {
Vladimir Markof59f18b2014-02-17 15:53:57 +0000174 cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
175 }
176
177 ArenaPool pool_;
178 CompilationUnit cu_;
179 size_t mir_count_;
180 MIR* mirs_;
181 std::vector<SSARepresentation> ssa_reps_;
182 std::vector<uint16_t> value_names_;
Ian Rogers700a4022014-05-19 16:49:03 -0700183 std::unique_ptr<LocalValueNumbering> lvn_;
Vladimir Markof59f18b2014-02-17 15:53:57 +0000184};
185
186TEST_F(LocalValueNumberingTest, TestIGetIGetInvokeIGet) {
187 static const IFieldDef ifields[] = {
188 { 1u, 1u, 1u, false }
189 };
190 static const MIRDef mirs[] = {
191 DEF_IGET(Instruction::IGET, 0u, 10u, 0u),
192 DEF_IGET(Instruction::IGET, 1u, 10u, 0u),
193 DEF_INVOKE1(Instruction::INVOKE_VIRTUAL, 11u),
194 DEF_IGET(Instruction::IGET, 2u, 10u, 0u),
195 };
196
197 PrepareIFields(ifields);
198 PrepareMIRs(mirs);
199 PerformLVN();
200 ASSERT_EQ(value_names_.size(), 4u);
201 EXPECT_EQ(value_names_[0], value_names_[1]);
202 EXPECT_NE(value_names_[0], value_names_[3]);
203 EXPECT_EQ(mirs_[0].optimization_flags, 0u);
204 EXPECT_EQ(mirs_[1].optimization_flags, MIR_IGNORE_NULL_CHECK);
205 EXPECT_EQ(mirs_[2].optimization_flags, 0u);
206 EXPECT_EQ(mirs_[3].optimization_flags, MIR_IGNORE_NULL_CHECK);
207}
208
209TEST_F(LocalValueNumberingTest, TestIGetIPutIGetIGetIGet) {
210 static const IFieldDef ifields[] = {
211 { 1u, 1u, 1u, false },
212 { 2u, 1u, 2u, false },
213 };
214 static const MIRDef mirs[] = {
215 DEF_IGET(Instruction::IGET, 0u, 10u, 0u),
216 DEF_IPUT(Instruction::IPUT, 1u, 11u, 0u), // May alias.
217 DEF_IGET(Instruction::IGET, 2u, 10u, 0u),
218 DEF_IGET(Instruction::IGET, 3u, 0u, 1u),
219 DEF_IGET(Instruction::IGET, 4u, 2u, 1u),
220 };
221
222 PrepareIFields(ifields);
223 PrepareMIRs(mirs);
224 PerformLVN();
225 ASSERT_EQ(value_names_.size(), 5u);
226 EXPECT_NE(value_names_[0], value_names_[2]);
227 EXPECT_NE(value_names_[3], value_names_[4]);
228 EXPECT_EQ(mirs_[0].optimization_flags, 0u);
229 EXPECT_EQ(mirs_[1].optimization_flags, 0u);
230 EXPECT_EQ(mirs_[2].optimization_flags, MIR_IGNORE_NULL_CHECK);
231 EXPECT_EQ(mirs_[3].optimization_flags, 0u);
232 EXPECT_EQ(mirs_[4].optimization_flags, 0u);
233}
234
235TEST_F(LocalValueNumberingTest, TestUniquePreserve1) {
236 static const IFieldDef ifields[] = {
237 { 1u, 1u, 1u, false },
238 };
239 static const MIRDef mirs[] = {
240 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 10u),
241 DEF_IGET(Instruction::IGET, 0u, 10u, 0u),
242 DEF_IPUT(Instruction::IPUT, 1u, 11u, 0u), // No aliasing since 10u is unique.
243 DEF_IGET(Instruction::IGET, 2u, 10u, 0u),
244 };
245
246 PrepareIFields(ifields);
247 PrepareMIRs(mirs);
248 PerformLVN();
249 ASSERT_EQ(value_names_.size(), 4u);
250 EXPECT_EQ(value_names_[1], value_names_[3]);
251 EXPECT_EQ(mirs_[1].optimization_flags, MIR_IGNORE_NULL_CHECK);
252 EXPECT_EQ(mirs_[2].optimization_flags, 0u);
253 EXPECT_EQ(mirs_[3].optimization_flags, MIR_IGNORE_NULL_CHECK);
254}
255
256TEST_F(LocalValueNumberingTest, TestUniquePreserve2) {
257 static const IFieldDef ifields[] = {
258 { 1u, 1u, 1u, false },
259 };
260 static const MIRDef mirs[] = {
261 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 11u),
262 DEF_IGET(Instruction::IGET, 0u, 10u, 0u),
263 DEF_IPUT(Instruction::IPUT, 1u, 11u, 0u), // No aliasing since 11u is unique.
264 DEF_IGET(Instruction::IGET, 2u, 10u, 0u),
265 };
266
267 PrepareIFields(ifields);
268 PrepareMIRs(mirs);
269 PerformLVN();
270 ASSERT_EQ(value_names_.size(), 4u);
271 EXPECT_EQ(value_names_[1], value_names_[3]);
272 EXPECT_EQ(mirs_[1].optimization_flags, 0u);
273 EXPECT_EQ(mirs_[2].optimization_flags, MIR_IGNORE_NULL_CHECK);
274 EXPECT_EQ(mirs_[3].optimization_flags, MIR_IGNORE_NULL_CHECK);
275}
276
277TEST_F(LocalValueNumberingTest, TestUniquePreserveAndEscape) {
278 static const IFieldDef ifields[] = {
279 { 1u, 1u, 1u, false },
280 };
281 static const MIRDef mirs[] = {
282 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 10u),
283 DEF_IGET(Instruction::IGET, 0u, 10u, 0u),
284 DEF_INVOKE1(Instruction::INVOKE_VIRTUAL, 11u), // 10u still unique.
285 DEF_IGET(Instruction::IGET, 2u, 10u, 0u),
286 DEF_INVOKE1(Instruction::INVOKE_VIRTUAL, 10u), // 10u not unique anymore.
287 DEF_IGET(Instruction::IGET, 3u, 10u, 0u),
288 };
289
290 PrepareIFields(ifields);
291 PrepareMIRs(mirs);
292 PerformLVN();
293 ASSERT_EQ(value_names_.size(), 6u);
294 EXPECT_EQ(value_names_[1], value_names_[3]);
295 EXPECT_NE(value_names_[1], value_names_[5]);
296 EXPECT_EQ(mirs_[1].optimization_flags, MIR_IGNORE_NULL_CHECK);
297 EXPECT_EQ(mirs_[3].optimization_flags, MIR_IGNORE_NULL_CHECK);
298 EXPECT_EQ(mirs_[5].optimization_flags, MIR_IGNORE_NULL_CHECK);
299}
Vladimir Markof59f18b2014-02-17 15:53:57 +0000300
301TEST_F(LocalValueNumberingTest, TestVolatile) {
302 static const IFieldDef ifields[] = {
303 { 1u, 1u, 1u, false },
304 { 2u, 1u, 2u, true },
305 };
306 static const MIRDef mirs[] = {
307 DEF_IGET(Instruction::IGET, 0u, 10u, 1u), // Volatile.
308 DEF_IGET(Instruction::IGET, 1u, 0u, 0u), // Non-volatile.
309 DEF_IGET(Instruction::IGET, 2u, 10u, 1u), // Volatile.
310 DEF_IGET(Instruction::IGET, 3u, 2u, 1u), // Non-volatile.
311 };
312
313 PrepareIFields(ifields);
314 PrepareMIRs(mirs);
315 PerformLVN();
316 ASSERT_EQ(value_names_.size(), 4u);
317 EXPECT_NE(value_names_[0], value_names_[2]); // Volatile has always different value name.
318 EXPECT_NE(value_names_[1], value_names_[3]); // Used different base because of volatile.
319 EXPECT_EQ(mirs_[0].optimization_flags, 0u);
320 EXPECT_EQ(mirs_[1].optimization_flags, 0u);
321 EXPECT_EQ(mirs_[2].optimization_flags, MIR_IGNORE_NULL_CHECK);
322 EXPECT_EQ(mirs_[3].optimization_flags, 0u);
323}
324
325} // namespace art