1 /*
2 * Copyright (C) 2016 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 "base/arena_allocator.h"
18 #include "builder.h"
19 #include "codegen_test_utils.h"
20 #include "common_compiler_test.h"
21 #include "nodes.h"
22 #include "optimizing_unit_test.h"
23 #include "pc_relative_fixups_x86.h"
24 #include "register_allocator.h"
25 #include "scheduler.h"
26
27 #ifdef ART_ENABLE_CODEGEN_arm64
28 #include "scheduler_arm64.h"
29 #endif
30
31 namespace art {
32
33 // Return all combinations of ISA and code generator that are executable on
34 // hardware, or on simulator, and that we'd like to test.
GetTargetConfigs()35 static ::std::vector<CodegenTargetConfig> GetTargetConfigs() {
36 ::std::vector<CodegenTargetConfig> v;
37 ::std::vector<CodegenTargetConfig> test_config_candidates = {
38 #ifdef ART_ENABLE_CODEGEN_arm
39 CodegenTargetConfig(kArm, create_codegen_arm),
40 CodegenTargetConfig(kThumb2, create_codegen_arm),
41 #endif
42 #ifdef ART_ENABLE_CODEGEN_arm64
43 CodegenTargetConfig(kArm64, create_codegen_arm64),
44 #endif
45 #ifdef ART_ENABLE_CODEGEN_x86
46 CodegenTargetConfig(kX86, create_codegen_x86),
47 #endif
48 #ifdef ART_ENABLE_CODEGEN_x86_64
49 CodegenTargetConfig(kX86_64, create_codegen_x86_64),
50 #endif
51 #ifdef ART_ENABLE_CODEGEN_mips
52 CodegenTargetConfig(kMips, create_codegen_mips),
53 #endif
54 #ifdef ART_ENABLE_CODEGEN_mips64
55 CodegenTargetConfig(kMips64, create_codegen_mips64)
56 #endif
57 };
58
59 for (auto test_config : test_config_candidates) {
60 if (CanExecute(test_config.GetInstructionSet())) {
61 v.push_back(test_config);
62 }
63 }
64
65 return v;
66 }
67
68 class SchedulerTest : public CommonCompilerTest {};
69
70 #ifdef ART_ENABLE_CODEGEN_arm64
TEST_F(SchedulerTest,DependencyGraph)71 TEST_F(SchedulerTest, DependencyGraph) {
72 ArenaPool pool;
73 ArenaAllocator allocator(&pool);
74 HGraph* graph = CreateGraph(&allocator);
75 HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
76 HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
77 graph->AddBlock(entry);
78 graph->AddBlock(block1);
79 graph->SetEntryBlock(entry);
80
81 // entry:
82 // array ParameterValue
83 // c1 IntConstant
84 // c2 IntConstant
85 // block1:
86 // add1 Add [c1, c2]
87 // add2 Add [add1, c2]
88 // mul Mul [add1, add2]
89 // div_check DivZeroCheck [add2] (env: add2, mul)
90 // div Div [add1, div_check]
91 // array_get1 ArrayGet [array, add1]
92 // array_set1 ArraySet [array, add1, add2]
93 // array_get2 ArrayGet [array, add1]
94 // array_set2 ArraySet [array, add1, add2]
95
96 HInstruction* array = new (&allocator) HParameterValue(graph->GetDexFile(),
97 dex::TypeIndex(0),
98 0,
99 Primitive::kPrimNot);
100 HInstruction* c1 = graph->GetIntConstant(1);
101 HInstruction* c2 = graph->GetIntConstant(10);
102 HInstruction* add1 = new (&allocator) HAdd(Primitive::kPrimInt, c1, c2);
103 HInstruction* add2 = new (&allocator) HAdd(Primitive::kPrimInt, add1, c2);
104 HInstruction* mul = new (&allocator) HMul(Primitive::kPrimInt, add1, add2);
105 HInstruction* div_check = new (&allocator) HDivZeroCheck(add2, 0);
106 HInstruction* div = new (&allocator) HDiv(Primitive::kPrimInt, add1, div_check, 0);
107 HInstruction* array_get1 = new (&allocator) HArrayGet(array, add1, Primitive::kPrimInt, 0);
108 HInstruction* array_set1 = new (&allocator) HArraySet(array, add1, add2, Primitive::kPrimInt, 0);
109 HInstruction* array_get2 = new (&allocator) HArrayGet(array, add1, Primitive::kPrimInt, 0);
110 HInstruction* array_set2 = new (&allocator) HArraySet(array, add1, add2, Primitive::kPrimInt, 0);
111
112 DCHECK(div_check->CanThrow());
113
114 entry->AddInstruction(array);
115
116 HInstruction* block_instructions[] = {add1,
117 add2,
118 mul,
119 div_check,
120 div,
121 array_get1,
122 array_set1,
123 array_get2,
124 array_set2};
125 for (auto instr : block_instructions) {
126 block1->AddInstruction(instr);
127 }
128
129 HEnvironment* environment = new (&allocator) HEnvironment(&allocator,
130 2,
131 graph->GetArtMethod(),
132 0,
133 div_check);
134 div_check->SetRawEnvironment(environment);
135 environment->SetRawEnvAt(0, add2);
136 add2->AddEnvUseAt(div_check->GetEnvironment(), 0);
137 environment->SetRawEnvAt(1, mul);
138 mul->AddEnvUseAt(div_check->GetEnvironment(), 1);
139
140 ArenaAllocator* arena = graph->GetArena();
141 CriticalPathSchedulingNodeSelector critical_path_selector;
142 arm64::HSchedulerARM64 scheduler(arena, &critical_path_selector);
143 SchedulingGraph scheduling_graph(&scheduler, arena);
144 // Instructions must be inserted in reverse order into the scheduling graph.
145 for (auto instr : ReverseRange(block_instructions)) {
146 scheduling_graph.AddNode(instr);
147 }
148
149 // Should not have dependencies cross basic blocks.
150 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, c1));
151 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add2, c2));
152
153 // Define-use dependency.
154 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(add2, add1));
155 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, add2));
156 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div_check, add2));
157 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(div_check, add1));
158 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div, div_check));
159 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add1));
160 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add2));
161
162 // Read and write dependencies
163 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, array_get1));
164 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_get2));
165 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_get2, array_set1));
166 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_set1));
167
168 // Env dependency.
169 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(div_check, mul));
170 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(mul, div_check));
171
172 // CanThrow.
173 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, div_check));
174 }
175 #endif
176
CompileWithRandomSchedulerAndRun(const uint16_t * data,bool has_result,int expected)177 static void CompileWithRandomSchedulerAndRun(const uint16_t* data,
178 bool has_result,
179 int expected) {
180 for (CodegenTargetConfig target_config : GetTargetConfigs()) {
181 ArenaPool pool;
182 ArenaAllocator arena(&pool);
183 HGraph* graph = CreateCFG(&arena, data);
184
185 // Schedule the graph randomly.
186 HInstructionScheduling scheduling(graph, target_config.GetInstructionSet());
187 scheduling.Run(/*only_optimize_loop_blocks*/ false, /*schedule_randomly*/ true);
188
189 RunCode(target_config,
190 graph,
191 [](HGraph* graph_arg) { RemoveSuspendChecks(graph_arg); },
192 has_result, expected);
193 }
194 }
195
TEST_F(SchedulerTest,RandomScheduling)196 TEST_F(SchedulerTest, RandomScheduling) {
197 //
198 // Java source: crafted code to make sure (random) scheduling should get correct result.
199 //
200 // int result = 0;
201 // float fr = 10.0f;
202 // for (int i = 1; i < 10; i++) {
203 // fr ++;
204 // int t1 = result >> i;
205 // int t2 = result * i;
206 // result = result + t1 - t2;
207 // fr = fr / i;
208 // result += (int)fr;
209 // }
210 // return result;
211 //
212 const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
213 Instruction::CONST_4 | 0 << 12 | 2 << 8, // const/4 v2, #int 0
214 Instruction::CONST_HIGH16 | 0 << 8, 0x4120, // const/high16 v0, #float 10.0 // #41200000
215 Instruction::CONST_4 | 1 << 12 | 1 << 8, // const/4 v1, #int 1
216 Instruction::CONST_16 | 5 << 8, 0x000a, // const/16 v5, #int 10
217 Instruction::IF_GE | 5 << 12 | 1 << 8, 0x0014, // if-ge v1, v5, 001a // +0014
218 Instruction::CONST_HIGH16 | 5 << 8, 0x3f80, // const/high16 v5, #float 1.0 // #3f800000
219 Instruction::ADD_FLOAT_2ADDR | 5 << 12 | 0 << 8, // add-float/2addr v0, v5
220 Instruction::SHR_INT | 3 << 8, 1 << 8 | 2 , // shr-int v3, v2, v1
221 Instruction::MUL_INT | 4 << 8, 1 << 8 | 2, // mul-int v4, v2, v1
222 Instruction::ADD_INT | 5 << 8, 3 << 8 | 2, // add-int v5, v2, v3
223 Instruction::SUB_INT | 2 << 8, 4 << 8 | 5, // sub-int v2, v5, v4
224 Instruction::INT_TO_FLOAT | 1 << 12 | 5 << 8, // int-to-float v5, v1
225 Instruction::DIV_FLOAT_2ADDR | 5 << 12 | 0 << 8, // div-float/2addr v0, v5
226 Instruction::FLOAT_TO_INT | 0 << 12 | 5 << 8, // float-to-int v5, v0
227 Instruction::ADD_INT_2ADDR | 5 << 12 | 2 << 8, // add-int/2addr v2, v5
228 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8 | 1, // add-int/lit8 v1, v1, #int 1 // #01
229 Instruction::GOTO | 0xeb << 8, // goto 0004 // -0015
230 Instruction::RETURN | 2 << 8); // return v2
231
232 constexpr int kNumberOfRuns = 10;
233 for (int i = 0; i < kNumberOfRuns; ++i) {
234 CompileWithRandomSchedulerAndRun(data, true, 138774);
235 }
236 }
237
238 } // namespace art
239