local_value_numbering_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 "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;
47    uint32_t field_info;
48    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 } }
58#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, { } }
74#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) {
80    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    }
93  }
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) {
101    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    }
114  }
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;
123    mirs_ = reinterpret_cast<MIR*>(cu_.arena.Alloc(sizeof(MIR) * count, kArenaAllocMIR));
124    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;
131      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      }
138      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
147      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) {
164      value_names_[i] =  lvn_->GetValueNumber(&mirs_[i]);
165    }
166  }
167
168  LocalValueNumberingTest()
169      : pool_(),
170        cu_(&pool_),
171        mir_count_(0u),
172        mirs_(nullptr),
173        lvn_(LocalValueNumbering::Create(&cu_)) {
174    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_;
183  std::unique_ptr<LocalValueNumbering> lvn_;
184};
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}
300
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
326