diff options
Diffstat (limited to 'compiler/optimizing/scheduler_test.cc')
| -rw-r--r-- | compiler/optimizing/scheduler_test.cc | 238 |
1 files changed, 238 insertions, 0 deletions
diff --git a/compiler/optimizing/scheduler_test.cc b/compiler/optimizing/scheduler_test.cc new file mode 100644 index 0000000000..31d13e2a26 --- /dev/null +++ b/compiler/optimizing/scheduler_test.cc @@ -0,0 +1,238 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "base/arena_allocator.h" +#include "builder.h" +#include "codegen_test_utils.h" +#include "common_compiler_test.h" +#include "nodes.h" +#include "optimizing_unit_test.h" +#include "pc_relative_fixups_x86.h" +#include "register_allocator.h" +#include "scheduler.h" + +#ifdef ART_ENABLE_CODEGEN_arm64 +#include "scheduler_arm64.h" +#endif + +namespace art { + +// Return all combinations of ISA and code generator that are executable on +// hardware, or on simulator, and that we'd like to test. +static ::std::vector<CodegenTargetConfig> GetTargetConfigs() { + ::std::vector<CodegenTargetConfig> v; + ::std::vector<CodegenTargetConfig> test_config_candidates = { +#ifdef ART_ENABLE_CODEGEN_arm + CodegenTargetConfig(kArm, create_codegen_arm), + CodegenTargetConfig(kThumb2, create_codegen_arm), +#endif +#ifdef ART_ENABLE_CODEGEN_arm64 + CodegenTargetConfig(kArm64, create_codegen_arm64), +#endif +#ifdef ART_ENABLE_CODEGEN_x86 + CodegenTargetConfig(kX86, create_codegen_x86), +#endif +#ifdef ART_ENABLE_CODEGEN_x86_64 + CodegenTargetConfig(kX86_64, create_codegen_x86_64), +#endif +#ifdef ART_ENABLE_CODEGEN_mips + CodegenTargetConfig(kMips, create_codegen_mips), +#endif +#ifdef ART_ENABLE_CODEGEN_mips64 + CodegenTargetConfig(kMips64, create_codegen_mips64) +#endif + }; + + for (auto test_config : test_config_candidates) { + if (CanExecute(test_config.GetInstructionSet())) { + v.push_back(test_config); + } + } + + return v; +} + +class SchedulerTest : public CommonCompilerTest {}; + +#ifdef ART_ENABLE_CODEGEN_arm64 +TEST_F(SchedulerTest, DependencyGraph) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + HGraph* graph = CreateGraph(&allocator); + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->AddBlock(block1); + graph->SetEntryBlock(entry); + + // entry: + // array ParameterValue + // c1 IntConstant + // c2 IntConstant + // block1: + // add1 Add [c1, c2] + // add2 Add [add1, c2] + // mul Mul [add1, add2] + // div_check DivZeroCheck [add2] (env: add2, mul) + // div Div [add1, div_check] + // array_get1 ArrayGet [array, add1] + // array_set1 ArraySet [array, add1, add2] + // array_get2 ArrayGet [array, add1] + // array_set2 ArraySet [array, add1, add2] + + HInstruction* array = new (&allocator) HParameterValue(graph->GetDexFile(), + dex::TypeIndex(0), + 0, + Primitive::kPrimNot); + HInstruction* c1 = graph->GetIntConstant(1); + HInstruction* c2 = graph->GetIntConstant(10); + HInstruction* add1 = new (&allocator) HAdd(Primitive::kPrimInt, c1, c2); + HInstruction* add2 = new (&allocator) HAdd(Primitive::kPrimInt, add1, c2); + HInstruction* mul = new (&allocator) HMul(Primitive::kPrimInt, add1, add2); + HInstruction* div_check = new (&allocator) HDivZeroCheck(add2, 0); + HInstruction* div = new (&allocator) HDiv(Primitive::kPrimInt, add1, div_check, 0); + HInstruction* array_get1 = new (&allocator) HArrayGet(array, add1, Primitive::kPrimInt, 0); + HInstruction* array_set1 = new (&allocator) HArraySet(array, add1, add2, Primitive::kPrimInt, 0); + HInstruction* array_get2 = new (&allocator) HArrayGet(array, add1, Primitive::kPrimInt, 0); + HInstruction* array_set2 = new (&allocator) HArraySet(array, add1, add2, Primitive::kPrimInt, 0); + + DCHECK(div_check->CanThrow()); + + entry->AddInstruction(array); + + HInstruction* block_instructions[] = {add1, + add2, + mul, + div_check, + div, + array_get1, + array_set1, + array_get2, + array_set2}; + for (auto instr : block_instructions) { + block1->AddInstruction(instr); + } + + HEnvironment* environment = new (&allocator) HEnvironment(&allocator, + 2, + graph->GetArtMethod(), + 0, + div_check); + div_check->SetRawEnvironment(environment); + environment->SetRawEnvAt(0, add2); + add2->AddEnvUseAt(div_check->GetEnvironment(), 0); + environment->SetRawEnvAt(1, mul); + mul->AddEnvUseAt(div_check->GetEnvironment(), 1); + + ArenaAllocator* arena = graph->GetArena(); + CriticalPathSchedulingNodeSelector critical_path_selector; + arm64::HSchedulerARM64 scheduler(arena, &critical_path_selector); + SchedulingGraph scheduling_graph(&scheduler, arena); + // Instructions must be inserted in reverse order into the scheduling graph. + for (auto instr : ReverseRange(block_instructions)) { + scheduling_graph.AddNode(instr); + } + + // Should not have dependencies cross basic blocks. + ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, c1)); + ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add2, c2)); + + // Define-use dependency. + ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(add2, add1)); + ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, add2)); + ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div_check, add2)); + ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(div_check, add1)); + ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div, div_check)); + ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add1)); + ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add2)); + + // Read and write dependencies + ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, array_get1)); + ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_get2)); + ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_get2, array_set1)); + ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_set1)); + + // Env dependency. + ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(div_check, mul)); + ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(mul, div_check)); + + // CanThrow. + ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, div_check)); +} +#endif + +static void CompileWithRandomSchedulerAndRun(const uint16_t* data, + bool has_result, + int expected) { + for (CodegenTargetConfig target_config : GetTargetConfigs()) { + ArenaPool pool; + ArenaAllocator arena(&pool); + HGraph* graph = CreateCFG(&arena, data); + + // Schedule the graph randomly. + HInstructionScheduling scheduling(graph, target_config.GetInstructionSet()); + scheduling.Run(/*only_optimize_loop_blocks*/ false, /*schedule_randomly*/ true); + + RunCode(target_config, + graph, + [](HGraph* graph_arg) { RemoveSuspendChecks(graph_arg); }, + has_result, expected); + } +} + +TEST_F(SchedulerTest, RandomScheduling) { + // + // Java source: crafted code to make sure (random) scheduling should get correct result. + // + // int result = 0; + // float fr = 10.0f; + // for (int i = 1; i < 10; i++) { + // fr ++; + // int t1 = result >> i; + // int t2 = result * i; + // result = result + t1 - t2; + // fr = fr / i; + // result += (int)fr; + // } + // return result; + // + const uint16_t data[] = SIX_REGISTERS_CODE_ITEM( + Instruction::CONST_4 | 0 << 12 | 2 << 8, // const/4 v2, #int 0 + Instruction::CONST_HIGH16 | 0 << 8, 0x4120, // const/high16 v0, #float 10.0 // #41200000 + Instruction::CONST_4 | 1 << 12 | 1 << 8, // const/4 v1, #int 1 + Instruction::CONST_16 | 5 << 8, 0x000a, // const/16 v5, #int 10 + Instruction::IF_GE | 5 << 12 | 1 << 8, 0x0014, // if-ge v1, v5, 001a // +0014 + Instruction::CONST_HIGH16 | 5 << 8, 0x3f80, // const/high16 v5, #float 1.0 // #3f800000 + Instruction::ADD_FLOAT_2ADDR | 5 << 12 | 0 << 8, // add-float/2addr v0, v5 + Instruction::SHR_INT | 3 << 8, 1 << 8 | 2 , // shr-int v3, v2, v1 + Instruction::MUL_INT | 4 << 8, 1 << 8 | 2, // mul-int v4, v2, v1 + Instruction::ADD_INT | 5 << 8, 3 << 8 | 2, // add-int v5, v2, v3 + Instruction::SUB_INT | 2 << 8, 4 << 8 | 5, // sub-int v2, v5, v4 + Instruction::INT_TO_FLOAT | 1 << 12 | 5 << 8, // int-to-float v5, v1 + Instruction::DIV_FLOAT_2ADDR | 5 << 12 | 0 << 8, // div-float/2addr v0, v5 + Instruction::FLOAT_TO_INT | 0 << 12 | 5 << 8, // float-to-int v5, v0 + Instruction::ADD_INT_2ADDR | 5 << 12 | 2 << 8, // add-int/2addr v2, v5 + Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8 | 1, // add-int/lit8 v1, v1, #int 1 // #01 + Instruction::GOTO | 0xeb << 8, // goto 0004 // -0015 + Instruction::RETURN | 2 << 8); // return v2 + + constexpr int kNumberOfRuns = 10; + for (int i = 0; i < kNumberOfRuns; ++i) { + CompileWithRandomSchedulerAndRun(data, true, 138774); + } +} + +} // namespace art |