codegen_test.cc revision cd2de0c1c7f1051a2f7bdb0e827dd6057f3bafcd 
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 <functional>
18
19#include "base/macros.h"
20#include "builder.h"
21#include "code_generator_arm.h"
22#include "code_generator_arm64.h"
23#include "code_generator_x86.h"
24#include "code_generator_x86_64.h"
25#include "common_compiler_test.h"
26#include "dex_file.h"
27#include "dex_instruction.h"
28#include "instruction_set.h"
29#include "nodes.h"
30#include "optimizing_unit_test.h"
31#include "prepare_for_register_allocation.h"
32#include "register_allocator.h"
33#include "ssa_liveness_analysis.h"
34
35#include "gtest/gtest.h"
36
37namespace art {
38
39class InternalCodeAllocator : public CodeAllocator {
40 public:
41  InternalCodeAllocator() { }
42
43  virtual uint8_t* Allocate(size_t size) {
44    size_ = size;
45    memory_.reset(new uint8_t[size]);
46    return memory_.get();
47  }
48
49  size_t GetSize() const { return size_; }
50  uint8_t* GetMemory() const { return memory_.get(); }
51
52 private:
53  size_t size_;
54  std::unique_ptr<uint8_t[]> memory_;
55
56  DISALLOW_COPY_AND_ASSIGN(InternalCodeAllocator);
57};
58
59static void Run(const InternalCodeAllocator& allocator,
60                const CodeGenerator& codegen,
61                bool has_result,
62                int32_t expected) {
63  typedef int32_t (*fptr)();
64  CommonCompilerTest::MakeExecutable(allocator.GetMemory(), allocator.GetSize());
65  fptr f = reinterpret_cast<fptr>(allocator.GetMemory());
66  if (codegen.GetInstructionSet() == kThumb2) {
67    // For thumb we need the bottom bit set.
68    f = reinterpret_cast<fptr>(reinterpret_cast<uintptr_t>(f) + 1);
69  }
70  int32_t result = f();
71  if (has_result) {
72    ASSERT_EQ(result, expected);
73  }
74}
75
76static void RunCodeBaseline(HGraph* graph, bool has_result, int32_t expected) {
77  InternalCodeAllocator allocator;
78
79  x86::CodeGeneratorX86 codegenX86(graph);
80  // We avoid doing a stack overflow check that requires the runtime being setup,
81  // by making sure the compiler knows the methods we are running are leaf methods.
82  codegenX86.CompileBaseline(&allocator, true);
83  if (kRuntimeISA == kX86) {
84    Run(allocator, codegenX86, has_result, expected);
85  }
86
87  arm::CodeGeneratorARM codegenARM(graph);
88  codegenARM.CompileBaseline(&allocator, true);
89  if (kRuntimeISA == kArm || kRuntimeISA == kThumb2) {
90    Run(allocator, codegenARM, has_result, expected);
91  }
92
93  x86_64::CodeGeneratorX86_64 codegenX86_64(graph);
94  codegenX86_64.CompileBaseline(&allocator, true);
95  if (kRuntimeISA == kX86_64) {
96    Run(allocator, codegenX86_64, has_result, expected);
97  }
98
99  arm64::CodeGeneratorARM64 codegenARM64(graph);
100  codegenARM64.CompileBaseline(&allocator, true);
101  if (kRuntimeISA == kArm64) {
102    Run(allocator, codegenARM64, has_result, expected);
103  }
104}
105
106static void RunCodeOptimized(CodeGenerator* codegen,
107                             HGraph* graph,
108                             std::function<void(HGraph*)> hook_before_codegen,
109                             bool has_result,
110                             int32_t expected) {
111  SsaLivenessAnalysis liveness(*graph, codegen);
112  liveness.Analyze();
113
114  RegisterAllocator register_allocator(graph->GetArena(), codegen, liveness);
115  register_allocator.AllocateRegisters();
116  hook_before_codegen(graph);
117
118  InternalCodeAllocator allocator;
119  codegen->CompileOptimized(&allocator);
120  Run(allocator, *codegen, has_result, expected);
121}
122
123static void RunCodeOptimized(HGraph* graph,
124                             std::function<void(HGraph*)> hook_before_codegen,
125                             bool has_result,
126                             int32_t expected) {
127  if (kRuntimeISA == kX86) {
128    x86::CodeGeneratorX86 codegenX86(graph);
129    RunCodeOptimized(&codegenX86, graph, hook_before_codegen, has_result, expected);
130  } else if (kRuntimeISA == kArm || kRuntimeISA == kThumb2) {
131    arm::CodeGeneratorARM codegenARM(graph);
132    RunCodeOptimized(&codegenARM, graph, hook_before_codegen, has_result, expected);
133  } else if (kRuntimeISA == kX86_64) {
134    x86_64::CodeGeneratorX86_64 codegenX86_64(graph);
135    RunCodeOptimized(&codegenX86_64, graph, hook_before_codegen, has_result, expected);
136  }
137}
138
139static void TestCode(const uint16_t* data, bool has_result = false, int32_t expected = 0) {
140  ArenaPool pool;
141  ArenaAllocator arena(&pool);
142  HGraphBuilder builder(&arena);
143  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
144  HGraph* graph = builder.BuildGraph(*item);
145  ASSERT_NE(graph, nullptr);
146  // Remove suspend checks, they cannot be executed in this context.
147  RemoveSuspendChecks(graph);
148  RunCodeBaseline(graph, has_result, expected);
149}
150
151TEST(CodegenTest, ReturnVoid) {
152  const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(Instruction::RETURN_VOID);
153  TestCode(data);
154}
155
156TEST(CodegenTest, CFG1) {
157  const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
158    Instruction::GOTO | 0x100,
159    Instruction::RETURN_VOID);
160
161  TestCode(data);
162}
163
164TEST(CodegenTest, CFG2) {
165  const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
166    Instruction::GOTO | 0x100,
167    Instruction::GOTO | 0x100,
168    Instruction::RETURN_VOID);
169
170  TestCode(data);
171}
172
173TEST(CodegenTest, CFG3) {
174  const uint16_t data1[] = ZERO_REGISTER_CODE_ITEM(
175    Instruction::GOTO | 0x200,
176    Instruction::RETURN_VOID,
177    Instruction::GOTO | 0xFF00);
178
179  TestCode(data1);
180
181  const uint16_t data2[] = ZERO_REGISTER_CODE_ITEM(
182    Instruction::GOTO_16, 3,
183    Instruction::RETURN_VOID,
184    Instruction::GOTO_16, 0xFFFF);
185
186  TestCode(data2);
187
188  const uint16_t data3[] = ZERO_REGISTER_CODE_ITEM(
189    Instruction::GOTO_32, 4, 0,
190    Instruction::RETURN_VOID,
191    Instruction::GOTO_32, 0xFFFF, 0xFFFF);
192
193  TestCode(data3);
194}
195
196TEST(CodegenTest, CFG4) {
197  const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
198    Instruction::RETURN_VOID,
199    Instruction::GOTO | 0x100,
200    Instruction::GOTO | 0xFE00);
201
202  TestCode(data);
203}
204
205TEST(CodegenTest, CFG5) {
206  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
207    Instruction::CONST_4 | 0 | 0,
208    Instruction::IF_EQ, 3,
209    Instruction::GOTO | 0x100,
210    Instruction::RETURN_VOID);
211
212  TestCode(data);
213}
214
215TEST(CodegenTest, IntConstant) {
216  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
217    Instruction::CONST_4 | 0 | 0,
218    Instruction::RETURN_VOID);
219
220  TestCode(data);
221}
222
223TEST(CodegenTest, Return1) {
224  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
225    Instruction::CONST_4 | 0 | 0,
226    Instruction::RETURN | 0);
227
228  TestCode(data, true, 0);
229}
230
231TEST(CodegenTest, Return2) {
232  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
233    Instruction::CONST_4 | 0 | 0,
234    Instruction::CONST_4 | 0 | 1 << 8,
235    Instruction::RETURN | 1 << 8);
236
237  TestCode(data, true, 0);
238}
239
240TEST(CodegenTest, Return3) {
241  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
242    Instruction::CONST_4 | 0 | 0,
243    Instruction::CONST_4 | 1 << 8 | 1 << 12,
244    Instruction::RETURN | 1 << 8);
245
246  TestCode(data, true, 1);
247}
248
249TEST(CodegenTest, ReturnIf1) {
250  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
251    Instruction::CONST_4 | 0 | 0,
252    Instruction::CONST_4 | 1 << 8 | 1 << 12,
253    Instruction::IF_EQ, 3,
254    Instruction::RETURN | 0 << 8,
255    Instruction::RETURN | 1 << 8);
256
257  TestCode(data, true, 1);
258}
259
260TEST(CodegenTest, ReturnIf2) {
261  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
262    Instruction::CONST_4 | 0 | 0,
263    Instruction::CONST_4 | 1 << 8 | 1 << 12,
264    Instruction::IF_EQ | 0 << 4 | 1 << 8, 3,
265    Instruction::RETURN | 0 << 8,
266    Instruction::RETURN | 1 << 8);
267
268  TestCode(data, true, 0);
269}
270
271// Exercise bit-wise (one's complement) not-int instruction.
272#define NOT_INT_TEST(TEST_NAME, INPUT, EXPECTED_OUTPUT) \
273TEST(CodegenTest, TEST_NAME) {                          \
274  const int32_t input = INPUT;                          \
275  const uint16_t input_lo = input & 0x0000FFFF;         \
276  const uint16_t input_hi = input >> 16;                \
277  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(      \
278      Instruction::CONST | 0 << 8, input_lo, input_hi,  \
279      Instruction::NOT_INT | 1 << 8 | 0 << 12 ,         \
280      Instruction::RETURN | 1 << 8);                    \
281                                                        \
282  TestCode(data, true, EXPECTED_OUTPUT);                \
283}
284
285NOT_INT_TEST(ReturnNotIntMinus2, -2, 1)
286NOT_INT_TEST(ReturnNotIntMinus1, -1, 0)
287NOT_INT_TEST(ReturnNotInt0, 0, -1)
288NOT_INT_TEST(ReturnNotInt1, 1, -2)
289NOT_INT_TEST(ReturnNotIntINT_MIN, -2147483648, 2147483647)  // (2^31) - 1
290NOT_INT_TEST(ReturnNotIntINT_MINPlus1, -2147483647, 2147483646)  // (2^31) - 2
291NOT_INT_TEST(ReturnNotIntINT_MAXMinus1, 2147483646, -2147483647)  // -(2^31) - 1
292NOT_INT_TEST(ReturnNotIntINT_MAX, 2147483647, -2147483648)  // -(2^31)
293
294#undef NOT_INT_TEST
295
296TEST(CodegenTest, ReturnAdd1) {
297  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
298    Instruction::CONST_4 | 3 << 12 | 0,
299    Instruction::CONST_4 | 4 << 12 | 1 << 8,
300    Instruction::ADD_INT, 1 << 8 | 0,
301    Instruction::RETURN);
302
303  TestCode(data, true, 7);
304}
305
306TEST(CodegenTest, ReturnAdd2) {
307  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
308    Instruction::CONST_4 | 3 << 12 | 0,
309    Instruction::CONST_4 | 4 << 12 | 1 << 8,
310    Instruction::ADD_INT_2ADDR | 1 << 12,
311    Instruction::RETURN);
312
313  TestCode(data, true, 7);
314}
315
316TEST(CodegenTest, ReturnAdd3) {
317  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
318    Instruction::CONST_4 | 4 << 12 | 0 << 8,
319    Instruction::ADD_INT_LIT8, 3 << 8 | 0,
320    Instruction::RETURN);
321
322  TestCode(data, true, 7);
323}
324
325TEST(CodegenTest, ReturnAdd4) {
326  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
327    Instruction::CONST_4 | 4 << 12 | 0 << 8,
328    Instruction::ADD_INT_LIT16, 3,
329    Instruction::RETURN);
330
331  TestCode(data, true, 7);
332}
333
334TEST(CodegenTest, NonMaterializedCondition) {
335  ArenaPool pool;
336  ArenaAllocator allocator(&pool);
337
338  HGraph* graph = new (&allocator) HGraph(&allocator);
339  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
340  graph->AddBlock(entry);
341  graph->SetEntryBlock(entry);
342  entry->AddInstruction(new (&allocator) HGoto());
343
344  HBasicBlock* first_block = new (&allocator) HBasicBlock(graph);
345  graph->AddBlock(first_block);
346  entry->AddSuccessor(first_block);
347  HIntConstant* constant0 = new (&allocator) HIntConstant(0);
348  entry->AddInstruction(constant0);
349  HIntConstant* constant1 = new (&allocator) HIntConstant(1);
350  entry->AddInstruction(constant1);
351  HEqual* equal = new (&allocator) HEqual(constant0, constant0);
352  first_block->AddInstruction(equal);
353  first_block->AddInstruction(new (&allocator) HIf(equal));
354
355  HBasicBlock* then = new (&allocator) HBasicBlock(graph);
356  HBasicBlock* else_ = new (&allocator) HBasicBlock(graph);
357  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
358
359  graph->AddBlock(then);
360  graph->AddBlock(else_);
361  graph->AddBlock(exit);
362  first_block->AddSuccessor(then);
363  first_block->AddSuccessor(else_);
364  then->AddSuccessor(exit);
365  else_->AddSuccessor(exit);
366
367  exit->AddInstruction(new (&allocator) HExit());
368  then->AddInstruction(new (&allocator) HReturn(constant0));
369  else_->AddInstruction(new (&allocator) HReturn(constant1));
370
371  ASSERT_TRUE(equal->NeedsMaterialization());
372  graph->BuildDominatorTree();
373  PrepareForRegisterAllocation(graph).Run();
374  ASSERT_FALSE(equal->NeedsMaterialization());
375
376  auto hook_before_codegen = [](HGraph* graph_in) {
377    HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessors().Get(0);
378    HParallelMove* move = new (graph_in->GetArena()) HParallelMove(graph_in->GetArena());
379    block->InsertInstructionBefore(move, block->GetLastInstruction());
380  };
381
382  RunCodeOptimized(graph, hook_before_codegen, true, 0);
383}
384
385#define MUL_TEST(TYPE, TEST_NAME)                     \
386  TEST(CodegenTest, Return ## TEST_NAME) {            \
387    const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(  \
388      Instruction::CONST_4 | 3 << 12 | 0,             \
389      Instruction::CONST_4 | 4 << 12 | 1 << 8,        \
390      Instruction::MUL_ ## TYPE, 1 << 8 | 0,          \
391      Instruction::RETURN);                           \
392                                                      \
393    TestCode(data, true, 12);                         \
394  }                                                   \
395                                                      \
396  TEST(CodegenTest, Return ## TEST_NAME ## 2addr) {   \
397    const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(  \
398      Instruction::CONST_4 | 3 << 12 | 0,             \
399      Instruction::CONST_4 | 4 << 12 | 1 << 8,        \
400      Instruction::MUL_ ## TYPE ## _2ADDR | 1 << 12,  \
401      Instruction::RETURN);                           \
402                                                      \
403    TestCode(data, true, 12);                         \
404  }
405
406#if !defined(__aarch64__)
407MUL_TEST(INT, MulInt);
408MUL_TEST(LONG, MulLong);
409#endif
410
411TEST(CodegenTest, ReturnMulIntLit8) {
412  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
413    Instruction::CONST_4 | 4 << 12 | 0 << 8,
414    Instruction::MUL_INT_LIT8, 3 << 8 | 0,
415    Instruction::RETURN);
416
417  TestCode(data, true, 12);
418}
419
420TEST(CodegenTest, ReturnMulIntLit16) {
421  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
422    Instruction::CONST_4 | 4 << 12 | 0 << 8,
423    Instruction::MUL_INT_LIT16, 3,
424    Instruction::RETURN);
425
426  TestCode(data, true, 12);
427}
428
429TEST(CodegenTest, MaterializedCondition1) {
430  // Check that condition are materialized correctly. A materialized condition
431  // should yield `1` if it evaluated to true, and `0` otherwise.
432  // We force the materialization of comparisons for different combinations of
433  // inputs and check the results.
434
435  int lhs[] = {1, 2, -1, 2, 0xabc};
436  int rhs[] = {2, 1, 2, -1, 0xabc};
437
438  for (size_t i = 0; i < arraysize(lhs); i++) {
439    ArenaPool pool;
440    ArenaAllocator allocator(&pool);
441    HGraph* graph = new (&allocator) HGraph(&allocator);
442
443    HBasicBlock* entry_block = new (&allocator) HBasicBlock(graph);
444    graph->AddBlock(entry_block);
445    graph->SetEntryBlock(entry_block);
446    entry_block->AddInstruction(new (&allocator) HGoto());
447    HBasicBlock* code_block = new (&allocator) HBasicBlock(graph);
448    graph->AddBlock(code_block);
449    HBasicBlock* exit_block = new (&allocator) HBasicBlock(graph);
450    graph->AddBlock(exit_block);
451    exit_block->AddInstruction(new (&allocator) HExit());
452
453    entry_block->AddSuccessor(code_block);
454    code_block->AddSuccessor(exit_block);
455    graph->SetExitBlock(exit_block);
456
457    HIntConstant cst_lhs(lhs[i]);
458    code_block->AddInstruction(&cst_lhs);
459    HIntConstant cst_rhs(rhs[i]);
460    code_block->AddInstruction(&cst_rhs);
461    HLessThan cmp_lt(&cst_lhs, &cst_rhs);
462    code_block->AddInstruction(&cmp_lt);
463    HReturn ret(&cmp_lt);
464    code_block->AddInstruction(&ret);
465
466    auto hook_before_codegen = [](HGraph* graph_in) {
467      HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessors().Get(0);
468      HParallelMove* move = new (graph_in->GetArena()) HParallelMove(graph_in->GetArena());
469      block->InsertInstructionBefore(move, block->GetLastInstruction());
470    };
471
472    RunCodeOptimized(graph, hook_before_codegen, true, lhs[i] < rhs[i]);
473  }
474}
475
476TEST(CodegenTest, MaterializedCondition2) {
477  // Check that HIf correctly interprets a materialized condition.
478  // We force the materialization of comparisons for different combinations of
479  // inputs. An HIf takes the materialized combination as input and returns a
480  // value that we verify.
481
482  int lhs[] = {1, 2, -1, 2, 0xabc};
483  int rhs[] = {2, 1, 2, -1, 0xabc};
484
485
486  for (size_t i = 0; i < arraysize(lhs); i++) {
487    ArenaPool pool;
488    ArenaAllocator allocator(&pool);
489    HGraph* graph = new (&allocator) HGraph(&allocator);
490
491    HBasicBlock* entry_block = new (&allocator) HBasicBlock(graph);
492    graph->AddBlock(entry_block);
493    graph->SetEntryBlock(entry_block);
494    entry_block->AddInstruction(new (&allocator) HGoto());
495
496    HBasicBlock* if_block = new (&allocator) HBasicBlock(graph);
497    graph->AddBlock(if_block);
498    HBasicBlock* if_true_block = new (&allocator) HBasicBlock(graph);
499    graph->AddBlock(if_true_block);
500    HBasicBlock* if_false_block = new (&allocator) HBasicBlock(graph);
501    graph->AddBlock(if_false_block);
502    HBasicBlock* exit_block = new (&allocator) HBasicBlock(graph);
503    graph->AddBlock(exit_block);
504    exit_block->AddInstruction(new (&allocator) HExit());
505
506    graph->SetEntryBlock(entry_block);
507    entry_block->AddSuccessor(if_block);
508    if_block->AddSuccessor(if_true_block);
509    if_block->AddSuccessor(if_false_block);
510    if_true_block->AddSuccessor(exit_block);
511    if_false_block->AddSuccessor(exit_block);
512    graph->SetExitBlock(exit_block);
513
514    HIntConstant cst_lhs(lhs[i]);
515    if_block->AddInstruction(&cst_lhs);
516    HIntConstant cst_rhs(rhs[i]);
517    if_block->AddInstruction(&cst_rhs);
518    HLessThan cmp_lt(&cst_lhs, &cst_rhs);
519    if_block->AddInstruction(&cmp_lt);
520    // We insert a temporary to separate the HIf from the HLessThan and force
521    // the materialization of the condition.
522    HTemporary force_materialization(0);
523    if_block->AddInstruction(&force_materialization);
524    HIf if_lt(&cmp_lt);
525    if_block->AddInstruction(&if_lt);
526
527    HIntConstant cst_lt(1);
528    if_true_block->AddInstruction(&cst_lt);
529    HReturn ret_lt(&cst_lt);
530    if_true_block->AddInstruction(&ret_lt);
531    HIntConstant cst_ge(0);
532    if_false_block->AddInstruction(&cst_ge);
533    HReturn ret_ge(&cst_ge);
534    if_false_block->AddInstruction(&ret_ge);
535
536    auto hook_before_codegen = [](HGraph* graph_in) {
537      HBasicBlock* block = graph_in->GetEntryBlock()->GetSuccessors().Get(0);
538      HParallelMove* move = new (graph_in->GetArena()) HParallelMove(graph_in->GetArena());
539      block->InsertInstructionBefore(move, block->GetLastInstruction());
540    };
541
542    RunCodeOptimized(graph, hook_before_codegen, true, lhs[i] < rhs[i]);
543  }
544}
545
546#if defined(__aarch64__)
547TEST(CodegenTest, DISABLED_ReturnDivIntLit8) {
548#else
549TEST(CodegenTest, ReturnDivIntLit8) {
550#endif
551  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
552    Instruction::CONST_4 | 4 << 12 | 0 << 8,
553    Instruction::DIV_INT_LIT8, 3 << 8 | 0,
554    Instruction::RETURN);
555
556  TestCode(data, true, 1);
557}
558
559}  // namespace art
560