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 "scheduler.h"
18
19 #include "base/arena_allocator.h"
20 #include "builder.h"
21 #include "codegen_test_utils.h"
22 #include "common_compiler_test.h"
23 #include "load_store_analysis.h"
24 #include "nodes.h"
25 #include "optimizing_unit_test.h"
26 #include "pc_relative_fixups_x86.h"
27 #include "register_allocator.h"
28
29 #ifdef ART_ENABLE_CODEGEN_arm64
30 #include "scheduler_arm64.h"
31 #endif
32
33 #ifdef ART_ENABLE_CODEGEN_arm
34 #include "scheduler_arm.h"
35 #endif
36
37 namespace art {
38
39 // Return all combinations of ISA and code generator that are executable on
40 // hardware, or on simulator, and that we'd like to test.
GetTargetConfigs()41 static ::std::vector<CodegenTargetConfig> GetTargetConfigs() {
42 ::std::vector<CodegenTargetConfig> v;
43 ::std::vector<CodegenTargetConfig> test_config_candidates = {
44 #ifdef ART_ENABLE_CODEGEN_arm
45 // TODO: Should't this be `kThumb2` instead of `kArm` here?
46 CodegenTargetConfig(InstructionSet::kArm, create_codegen_arm_vixl32),
47 #endif
48 #ifdef ART_ENABLE_CODEGEN_arm64
49 CodegenTargetConfig(InstructionSet::kArm64, create_codegen_arm64),
50 #endif
51 #ifdef ART_ENABLE_CODEGEN_x86
52 CodegenTargetConfig(InstructionSet::kX86, create_codegen_x86),
53 #endif
54 #ifdef ART_ENABLE_CODEGEN_x86_64
55 CodegenTargetConfig(InstructionSet::kX86_64, create_codegen_x86_64),
56 #endif
57 #ifdef ART_ENABLE_CODEGEN_mips
58 CodegenTargetConfig(InstructionSet::kMips, create_codegen_mips),
59 #endif
60 #ifdef ART_ENABLE_CODEGEN_mips64
61 CodegenTargetConfig(InstructionSet::kMips64, create_codegen_mips64)
62 #endif
63 };
64
65 for (const CodegenTargetConfig& test_config : test_config_candidates) {
66 if (CanExecute(test_config.GetInstructionSet())) {
67 v.push_back(test_config);
68 }
69 }
70
71 return v;
72 }
73
74 class SchedulerTest : public OptimizingUnitTest {
75 public:
SchedulerTest()76 SchedulerTest() : graph_(CreateGraph()) { }
77
78 // Build scheduling graph, and run target specific scheduling on it.
TestBuildDependencyGraphAndSchedule(HScheduler * scheduler)79 void TestBuildDependencyGraphAndSchedule(HScheduler* scheduler) {
80 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
81 HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_);
82 graph_->AddBlock(entry);
83 graph_->AddBlock(block1);
84 graph_->SetEntryBlock(entry);
85
86 // entry:
87 // array ParameterValue
88 // c1 IntConstant
89 // c2 IntConstant
90 // block1:
91 // add1 Add [c1, c2]
92 // add2 Add [add1, c2]
93 // mul Mul [add1, add2]
94 // div_check DivZeroCheck [add2] (env: add2, mul)
95 // div Div [add1, div_check]
96 // array_get1 ArrayGet [array, add1]
97 // array_set1 ArraySet [array, add1, add2]
98 // array_get2 ArrayGet [array, add1]
99 // array_set2 ArraySet [array, add1, add2]
100
101 HInstruction* array = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
102 dex::TypeIndex(0),
103 0,
104 DataType::Type::kReference);
105 HInstruction* c1 = graph_->GetIntConstant(1);
106 HInstruction* c2 = graph_->GetIntConstant(10);
107 HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, c1, c2);
108 HInstruction* add2 = new (GetAllocator()) HAdd(DataType::Type::kInt32, add1, c2);
109 HInstruction* mul = new (GetAllocator()) HMul(DataType::Type::kInt32, add1, add2);
110 HInstruction* div_check = new (GetAllocator()) HDivZeroCheck(add2, 0);
111 HInstruction* div = new (GetAllocator()) HDiv(DataType::Type::kInt32, add1, div_check, 0);
112 HInstruction* array_get1 =
113 new (GetAllocator()) HArrayGet(array, add1, DataType::Type::kInt32, 0);
114 HInstruction* array_set1 =
115 new (GetAllocator()) HArraySet(array, add1, add2, DataType::Type::kInt32, 0);
116 HInstruction* array_get2 =
117 new (GetAllocator()) HArrayGet(array, add1, DataType::Type::kInt32, 0);
118 HInstruction* array_set2 =
119 new (GetAllocator()) HArraySet(array, add1, add2, DataType::Type::kInt32, 0);
120
121 DCHECK(div_check->CanThrow());
122
123 entry->AddInstruction(array);
124
125 HInstruction* block_instructions[] = {add1,
126 add2,
127 mul,
128 div_check,
129 div,
130 array_get1,
131 array_set1,
132 array_get2,
133 array_set2};
134 for (HInstruction* instr : block_instructions) {
135 block1->AddInstruction(instr);
136 }
137
138 HEnvironment* environment = new (GetAllocator()) HEnvironment(GetAllocator(),
139 2,
140 graph_->GetArtMethod(),
141 0,
142 div_check);
143 div_check->SetRawEnvironment(environment);
144 environment->SetRawEnvAt(0, add2);
145 add2->AddEnvUseAt(div_check->GetEnvironment(), 0);
146 environment->SetRawEnvAt(1, mul);
147 mul->AddEnvUseAt(div_check->GetEnvironment(), 1);
148
149 SchedulingGraph scheduling_graph(scheduler, GetScopedAllocator());
150 // Instructions must be inserted in reverse order into the scheduling graph.
151 for (HInstruction* instr : ReverseRange(block_instructions)) {
152 scheduling_graph.AddNode(instr);
153 }
154
155 // Should not have dependencies cross basic blocks.
156 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, c1));
157 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add2, c2));
158
159 // Define-use dependency.
160 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(add2, add1));
161 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, add2));
162 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div_check, add2));
163 ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(div_check, add1));
164 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div, div_check));
165 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add1));
166 ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add2));
167
168 // Read and write dependencies
169 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, array_get1));
170 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_get2));
171 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_get2, array_set1));
172 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_set1));
173
174 // Env dependency.
175 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(div_check, mul));
176 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(mul, div_check));
177
178 // CanThrow.
179 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, div_check));
180
181 // Exercise the code path of target specific scheduler and SchedulingLatencyVisitor.
182 scheduler->Schedule(graph_);
183 }
184
CompileWithRandomSchedulerAndRun(const std::vector<uint16_t> & data,bool has_result,int expected)185 void CompileWithRandomSchedulerAndRun(const std::vector<uint16_t>& data,
186 bool has_result,
187 int expected) {
188 for (CodegenTargetConfig target_config : GetTargetConfigs()) {
189 HGraph* graph = CreateCFG(data);
190
191 // Schedule the graph randomly.
192 HInstructionScheduling scheduling(graph, target_config.GetInstructionSet());
193 scheduling.Run(/*only_optimize_loop_blocks*/ false, /*schedule_randomly*/ true);
194
195 RunCode(target_config,
196 graph,
197 [](HGraph* graph_arg) { RemoveSuspendChecks(graph_arg); },
198 has_result, expected);
199 }
200 }
201
TestDependencyGraphOnAliasingArrayAccesses(HScheduler * scheduler)202 void TestDependencyGraphOnAliasingArrayAccesses(HScheduler* scheduler) {
203 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
204 graph_->AddBlock(entry);
205 graph_->SetEntryBlock(entry);
206 graph_->BuildDominatorTree();
207
208 HInstruction* arr = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
209 dex::TypeIndex(0),
210 0,
211 DataType::Type::kReference);
212 HInstruction* i = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
213 dex::TypeIndex(1),
214 1,
215 DataType::Type::kInt32);
216 HInstruction* j = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
217 dex::TypeIndex(1),
218 1,
219 DataType::Type::kInt32);
220 HInstruction* object = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
221 dex::TypeIndex(0),
222 0,
223 DataType::Type::kReference);
224 HInstruction* c0 = graph_->GetIntConstant(0);
225 HInstruction* c1 = graph_->GetIntConstant(1);
226 HInstruction* add0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, i, c0);
227 HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, i, c1);
228 HInstruction* sub0 = new (GetAllocator()) HSub(DataType::Type::kInt32, i, c0);
229 HInstruction* sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, i, c1);
230 HInstruction* arr_set_0 =
231 new (GetAllocator()) HArraySet(arr, c0, c0, DataType::Type::kInt32, 0);
232 HInstruction* arr_set_1 =
233 new (GetAllocator()) HArraySet(arr, c1, c0, DataType::Type::kInt32, 0);
234 HInstruction* arr_set_i = new (GetAllocator()) HArraySet(arr, i, c0, DataType::Type::kInt32, 0);
235 HInstruction* arr_set_add0 =
236 new (GetAllocator()) HArraySet(arr, add0, c0, DataType::Type::kInt32, 0);
237 HInstruction* arr_set_add1 =
238 new (GetAllocator()) HArraySet(arr, add1, c0, DataType::Type::kInt32, 0);
239 HInstruction* arr_set_sub0 =
240 new (GetAllocator()) HArraySet(arr, sub0, c0, DataType::Type::kInt32, 0);
241 HInstruction* arr_set_sub1 =
242 new (GetAllocator()) HArraySet(arr, sub1, c0, DataType::Type::kInt32, 0);
243 HInstruction* arr_set_j = new (GetAllocator()) HArraySet(arr, j, c0, DataType::Type::kInt32, 0);
244 HInstanceFieldSet* set_field10 = new (GetAllocator()) HInstanceFieldSet(object,
245 c1,
246 nullptr,
247 DataType::Type::kInt32,
248 MemberOffset(10),
249 false,
250 kUnknownFieldIndex,
251 kUnknownClassDefIndex,
252 graph_->GetDexFile(),
253 0);
254
255 HInstruction* block_instructions[] = {arr,
256 i,
257 j,
258 object,
259 add0,
260 add1,
261 sub0,
262 sub1,
263 arr_set_0,
264 arr_set_1,
265 arr_set_i,
266 arr_set_add0,
267 arr_set_add1,
268 arr_set_sub0,
269 arr_set_sub1,
270 arr_set_j,
271 set_field10};
272
273 for (HInstruction* instr : block_instructions) {
274 entry->AddInstruction(instr);
275 }
276
277 SchedulingGraph scheduling_graph(scheduler, GetScopedAllocator());
278 HeapLocationCollector heap_location_collector(graph_);
279 heap_location_collector.VisitBasicBlock(entry);
280 heap_location_collector.BuildAliasingMatrix();
281 scheduling_graph.SetHeapLocationCollector(heap_location_collector);
282
283 for (HInstruction* instr : ReverseRange(block_instructions)) {
284 // Build scheduling graph with memory access aliasing information
285 // from LSA/heap_location_collector.
286 scheduling_graph.AddNode(instr);
287 }
288
289 // LSA/HeapLocationCollector should see those ArraySet instructions.
290 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 9U);
291 ASSERT_TRUE(heap_location_collector.HasHeapStores());
292
293 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
294 // HeapLocationCollector and SchedulingGraph should report consistent relationships.
295 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
296 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
297
298 // Test side effect dependency: array[0] and array[1]
299 loc1 = heap_location_collector.GetArrayHeapLocation(arr, c0);
300 loc2 = heap_location_collector.GetArrayHeapLocation(arr, c1);
301 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
302 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_1, arr_set_0));
303
304 // Test side effect dependency based on LSA analysis: array[i] and array[j]
305 loc1 = heap_location_collector.GetArrayHeapLocation(arr, i);
306 loc2 = heap_location_collector.GetArrayHeapLocation(arr, j);
307 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
308 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i));
309
310 // Test side effect dependency based on LSA analysis: array[i] and array[i+0]
311 loc1 = heap_location_collector.GetArrayHeapLocation(arr, i);
312 loc2 = heap_location_collector.GetArrayHeapLocation(arr, add0);
313 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
314 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_add0, arr_set_i));
315
316 // Test side effect dependency based on LSA analysis: array[i] and array[i-0]
317 loc1 = heap_location_collector.GetArrayHeapLocation(arr, i);
318 loc2 = heap_location_collector.GetArrayHeapLocation(arr, sub0);
319 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
320 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub0, arr_set_i));
321
322 // Test side effect dependency based on LSA analysis: array[i] and array[i+1]
323 loc1 = heap_location_collector.GetArrayHeapLocation(arr, i);
324 loc2 = heap_location_collector.GetArrayHeapLocation(arr, add1);
325 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
326 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_add1, arr_set_i));
327
328 // Test side effect dependency based on LSA analysis: array[i+1] and array[i-1]
329 loc1 = heap_location_collector.GetArrayHeapLocation(arr, add1);
330 loc2 = heap_location_collector.GetArrayHeapLocation(arr, sub1);
331 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
332 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub1, arr_set_add1));
333
334 // Test side effect dependency based on LSA analysis: array[j] and all others array accesses
335 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i));
336 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_add0));
337 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_sub0));
338 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_add1));
339 ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_sub1));
340
341 // Test that ArraySet and FieldSet should not have side effect dependency
342 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_i, set_field10));
343 ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, set_field10));
344
345 // Exercise target specific scheduler and SchedulingLatencyVisitor.
346 scheduler->Schedule(graph_);
347 }
348
349 HGraph* graph_;
350 };
351
352 #if defined(ART_ENABLE_CODEGEN_arm64)
TEST_F(SchedulerTest,DependencyGraphAndSchedulerARM64)353 TEST_F(SchedulerTest, DependencyGraphAndSchedulerARM64) {
354 CriticalPathSchedulingNodeSelector critical_path_selector;
355 arm64::HSchedulerARM64 scheduler(GetScopedAllocator(), &critical_path_selector);
356 TestBuildDependencyGraphAndSchedule(&scheduler);
357 }
358
TEST_F(SchedulerTest,ArrayAccessAliasingARM64)359 TEST_F(SchedulerTest, ArrayAccessAliasingARM64) {
360 CriticalPathSchedulingNodeSelector critical_path_selector;
361 arm64::HSchedulerARM64 scheduler(GetScopedAllocator(), &critical_path_selector);
362 TestDependencyGraphOnAliasingArrayAccesses(&scheduler);
363 }
364 #endif
365
366 #if defined(ART_ENABLE_CODEGEN_arm)
TEST_F(SchedulerTest,DependencyGraphAndSchedulerARM)367 TEST_F(SchedulerTest, DependencyGraphAndSchedulerARM) {
368 CriticalPathSchedulingNodeSelector critical_path_selector;
369 arm::SchedulingLatencyVisitorARM arm_latency_visitor(/*CodeGenerator*/ nullptr);
370 arm::HSchedulerARM scheduler(GetScopedAllocator(), &critical_path_selector, &arm_latency_visitor);
371 TestBuildDependencyGraphAndSchedule(&scheduler);
372 }
373
TEST_F(SchedulerTest,ArrayAccessAliasingARM)374 TEST_F(SchedulerTest, ArrayAccessAliasingARM) {
375 CriticalPathSchedulingNodeSelector critical_path_selector;
376 arm::SchedulingLatencyVisitorARM arm_latency_visitor(/*CodeGenerator*/ nullptr);
377 arm::HSchedulerARM scheduler(GetScopedAllocator(), &critical_path_selector, &arm_latency_visitor);
378 TestDependencyGraphOnAliasingArrayAccesses(&scheduler);
379 }
380 #endif
381
TEST_F(SchedulerTest,RandomScheduling)382 TEST_F(SchedulerTest, RandomScheduling) {
383 //
384 // Java source: crafted code to make sure (random) scheduling should get correct result.
385 //
386 // int result = 0;
387 // float fr = 10.0f;
388 // for (int i = 1; i < 10; i++) {
389 // fr ++;
390 // int t1 = result >> i;
391 // int t2 = result * i;
392 // result = result + t1 - t2;
393 // fr = fr / i;
394 // result += (int)fr;
395 // }
396 // return result;
397 //
398 const std::vector<uint16_t> data = SIX_REGISTERS_CODE_ITEM(
399 Instruction::CONST_4 | 0 << 12 | 2 << 8, // const/4 v2, #int 0
400 Instruction::CONST_HIGH16 | 0 << 8, 0x4120, // const/high16 v0, #float 10.0 // #41200000
401 Instruction::CONST_4 | 1 << 12 | 1 << 8, // const/4 v1, #int 1
402 Instruction::CONST_16 | 5 << 8, 0x000a, // const/16 v5, #int 10
403 Instruction::IF_GE | 5 << 12 | 1 << 8, 0x0014, // if-ge v1, v5, 001a // +0014
404 Instruction::CONST_HIGH16 | 5 << 8, 0x3f80, // const/high16 v5, #float 1.0 // #3f800000
405 Instruction::ADD_FLOAT_2ADDR | 5 << 12 | 0 << 8, // add-float/2addr v0, v5
406 Instruction::SHR_INT | 3 << 8, 1 << 8 | 2 , // shr-int v3, v2, v1
407 Instruction::MUL_INT | 4 << 8, 1 << 8 | 2, // mul-int v4, v2, v1
408 Instruction::ADD_INT | 5 << 8, 3 << 8 | 2, // add-int v5, v2, v3
409 Instruction::SUB_INT | 2 << 8, 4 << 8 | 5, // sub-int v2, v5, v4
410 Instruction::INT_TO_FLOAT | 1 << 12 | 5 << 8, // int-to-float v5, v1
411 Instruction::DIV_FLOAT_2ADDR | 5 << 12 | 0 << 8, // div-float/2addr v0, v5
412 Instruction::FLOAT_TO_INT | 0 << 12 | 5 << 8, // float-to-int v5, v0
413 Instruction::ADD_INT_2ADDR | 5 << 12 | 2 << 8, // add-int/2addr v2, v5
414 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8 | 1, // add-int/lit8 v1, v1, #int 1 // #01
415 Instruction::GOTO | 0xeb << 8, // goto 0004 // -0015
416 Instruction::RETURN | 2 << 8); // return v2
417
418 constexpr int kNumberOfRuns = 10;
419 for (int i = 0; i < kNumberOfRuns; ++i) {
420 CompileWithRandomSchedulerAndRun(data, true, 138774);
421 }
422 }
423
424 } // namespace art
425