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