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