Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2015 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 "licm.h" |
| 18 | |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 19 | #include "base/arena_allocator.h" |
| 20 | #include "builder.h" |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 21 | #include "nodes.h" |
| 22 | #include "optimizing_unit_test.h" |
| 23 | #include "side_effects_analysis.h" |
| 24 | |
| 25 | namespace art { |
| 26 | |
| 27 | /** |
| 28 | * Fixture class for the LICM tests. |
| 29 | */ |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 30 | class LICMTest : public CommonCompilerTest { |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 31 | public: |
Andreas Gampe | d9911ee | 2017-03-27 13:27:24 -0700 | [diff] [blame] | 32 | LICMTest() |
| 33 | : pool_(), |
| 34 | allocator_(&pool_), |
| 35 | entry_(nullptr), |
| 36 | loop_preheader_(nullptr), |
| 37 | loop_header_(nullptr), |
| 38 | loop_body_(nullptr), |
| 39 | return_(nullptr), |
| 40 | exit_(nullptr), |
| 41 | parameter_(nullptr), |
| 42 | int_constant_(nullptr), |
| 43 | float_constant_(nullptr) { |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 44 | graph_ = CreateGraph(&allocator_); |
| 45 | } |
| 46 | |
| 47 | ~LICMTest() { } |
| 48 | |
| 49 | // Builds a singly-nested loop structure in CFG. Tests can further populate |
| 50 | // the basic blocks with instructions to set up interesting scenarios. |
| 51 | void BuildLoop() { |
| 52 | entry_ = new (&allocator_) HBasicBlock(graph_); |
| 53 | loop_preheader_ = new (&allocator_) HBasicBlock(graph_); |
| 54 | loop_header_ = new (&allocator_) HBasicBlock(graph_); |
| 55 | loop_body_ = new (&allocator_) HBasicBlock(graph_); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 56 | return_ = new (&allocator_) HBasicBlock(graph_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 57 | exit_ = new (&allocator_) HBasicBlock(graph_); |
| 58 | |
| 59 | graph_->AddBlock(entry_); |
| 60 | graph_->AddBlock(loop_preheader_); |
| 61 | graph_->AddBlock(loop_header_); |
| 62 | graph_->AddBlock(loop_body_); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 63 | graph_->AddBlock(return_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 64 | graph_->AddBlock(exit_); |
| 65 | |
| 66 | graph_->SetEntryBlock(entry_); |
| 67 | graph_->SetExitBlock(exit_); |
| 68 | |
| 69 | // Set up loop flow in CFG. |
| 70 | entry_->AddSuccessor(loop_preheader_); |
| 71 | loop_preheader_->AddSuccessor(loop_header_); |
| 72 | loop_header_->AddSuccessor(loop_body_); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 73 | loop_header_->AddSuccessor(return_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 74 | loop_body_->AddSuccessor(loop_header_); |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 75 | return_->AddSuccessor(exit_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 76 | |
| 77 | // Provide boiler-plate instructions. |
Andreas Gampe | a5b09a6 | 2016-11-17 15:21:22 -0800 | [diff] [blame] | 78 | parameter_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), |
| 79 | dex::TypeIndex(0), |
| 80 | 0, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 81 | DataType::Type::kReference); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 82 | entry_->AddInstruction(parameter_); |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 83 | int_constant_ = graph_->GetIntConstant(42); |
| 84 | float_constant_ = graph_->GetFloatConstant(42.0f); |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 85 | loop_preheader_->AddInstruction(new (&allocator_) HGoto()); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 86 | loop_header_->AddInstruction(new (&allocator_) HIf(parameter_)); |
| 87 | loop_body_->AddInstruction(new (&allocator_) HGoto()); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 88 | return_->AddInstruction(new (&allocator_) HReturnVoid()); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 89 | exit_->AddInstruction(new (&allocator_) HExit()); |
| 90 | } |
| 91 | |
| 92 | // Performs LICM optimizations (after proper set up). |
| 93 | void PerformLICM() { |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 94 | graph_->BuildDominatorTree(); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 95 | SideEffectsAnalysis side_effects(graph_); |
| 96 | side_effects.Run(); |
Jean-Philippe Halimi | 38e9e80 | 2016-02-18 16:42:03 +0100 | [diff] [blame] | 97 | LICM(graph_, side_effects, nullptr).Run(); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 98 | } |
| 99 | |
| 100 | // General building fields. |
| 101 | ArenaPool pool_; |
| 102 | ArenaAllocator allocator_; |
| 103 | HGraph* graph_; |
| 104 | |
| 105 | // Specific basic blocks. |
| 106 | HBasicBlock* entry_; |
| 107 | HBasicBlock* loop_preheader_; |
| 108 | HBasicBlock* loop_header_; |
| 109 | HBasicBlock* loop_body_; |
David Brazdil | db51efb | 2015-11-06 01:36:20 +0000 | [diff] [blame] | 110 | HBasicBlock* return_; |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 111 | HBasicBlock* exit_; |
| 112 | |
| 113 | HInstruction* parameter_; // "this" |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 114 | HInstruction* int_constant_; |
| 115 | HInstruction* float_constant_; |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 116 | }; |
| 117 | |
| 118 | // |
| 119 | // The actual LICM tests. |
| 120 | // |
| 121 | |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 122 | TEST_F(LICMTest, FieldHoisting) { |
| 123 | BuildLoop(); |
| 124 | |
| 125 | // Populate the loop with instructions: set/get field with different types. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 126 | HInstruction* get_field = new (&allocator_) HInstanceFieldGet(parameter_, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 127 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 128 | DataType::Type::kInt64, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 129 | MemberOffset(10), |
| 130 | false, |
| 131 | kUnknownFieldIndex, |
| 132 | kUnknownClassDefIndex, |
| 133 | graph_->GetDexFile(), |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 134 | 0); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 135 | loop_body_->InsertInstructionBefore(get_field, loop_body_->GetLastInstruction()); |
| 136 | HInstruction* set_field = new (&allocator_) HInstanceFieldSet( |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 137 | parameter_, int_constant_, nullptr, DataType::Type::kInt32, MemberOffset(20), |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 138 | false, kUnknownFieldIndex, kUnknownClassDefIndex, graph_->GetDexFile(), 0); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 139 | loop_body_->InsertInstructionBefore(set_field, loop_body_->GetLastInstruction()); |
| 140 | |
Aart Bik | 8f08f9e | 2015-07-22 11:27:39 -0700 | [diff] [blame] | 141 | EXPECT_EQ(get_field->GetBlock(), loop_body_); |
| 142 | EXPECT_EQ(set_field->GetBlock(), loop_body_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 143 | PerformLICM(); |
Aart Bik | 8f08f9e | 2015-07-22 11:27:39 -0700 | [diff] [blame] | 144 | EXPECT_EQ(get_field->GetBlock(), loop_preheader_); |
| 145 | EXPECT_EQ(set_field->GetBlock(), loop_body_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 146 | } |
| 147 | |
| 148 | TEST_F(LICMTest, NoFieldHoisting) { |
| 149 | BuildLoop(); |
| 150 | |
| 151 | // Populate the loop with instructions: set/get field with same types. |
Mathieu Chartier | 9865bde | 2015-12-21 09:58:16 -0800 | [diff] [blame] | 152 | ScopedNullHandle<mirror::DexCache> dex_cache; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 153 | HInstruction* get_field = new (&allocator_) HInstanceFieldGet(parameter_, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 154 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 155 | DataType::Type::kInt64, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 156 | MemberOffset(10), |
| 157 | false, |
| 158 | kUnknownFieldIndex, |
| 159 | kUnknownClassDefIndex, |
| 160 | graph_->GetDexFile(), |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 161 | 0); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 162 | loop_body_->InsertInstructionBefore(get_field, loop_body_->GetLastInstruction()); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 163 | HInstruction* set_field = new (&allocator_) HInstanceFieldSet(parameter_, |
| 164 | get_field, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 165 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 166 | DataType::Type::kInt64, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 167 | MemberOffset(10), |
| 168 | false, |
| 169 | kUnknownFieldIndex, |
| 170 | kUnknownClassDefIndex, |
| 171 | graph_->GetDexFile(), |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 172 | 0); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 173 | loop_body_->InsertInstructionBefore(set_field, loop_body_->GetLastInstruction()); |
| 174 | |
Aart Bik | 8f08f9e | 2015-07-22 11:27:39 -0700 | [diff] [blame] | 175 | EXPECT_EQ(get_field->GetBlock(), loop_body_); |
| 176 | EXPECT_EQ(set_field->GetBlock(), loop_body_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 177 | PerformLICM(); |
Aart Bik | 8f08f9e | 2015-07-22 11:27:39 -0700 | [diff] [blame] | 178 | EXPECT_EQ(get_field->GetBlock(), loop_body_); |
| 179 | EXPECT_EQ(set_field->GetBlock(), loop_body_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 180 | } |
| 181 | |
| 182 | TEST_F(LICMTest, ArrayHoisting) { |
| 183 | BuildLoop(); |
| 184 | |
| 185 | // Populate the loop with instructions: set/get array with different types. |
| 186 | HInstruction* get_array = new (&allocator_) HArrayGet( |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 187 | parameter_, int_constant_, DataType::Type::kInt32, 0); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 188 | loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); |
| 189 | HInstruction* set_array = new (&allocator_) HArraySet( |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 190 | parameter_, int_constant_, float_constant_, DataType::Type::kFloat32, 0); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 191 | loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); |
| 192 | |
Aart Bik | 8f08f9e | 2015-07-22 11:27:39 -0700 | [diff] [blame] | 193 | EXPECT_EQ(get_array->GetBlock(), loop_body_); |
| 194 | EXPECT_EQ(set_array->GetBlock(), loop_body_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 195 | PerformLICM(); |
Aart Bik | 8f08f9e | 2015-07-22 11:27:39 -0700 | [diff] [blame] | 196 | EXPECT_EQ(get_array->GetBlock(), loop_preheader_); |
| 197 | EXPECT_EQ(set_array->GetBlock(), loop_body_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 198 | } |
| 199 | |
| 200 | TEST_F(LICMTest, NoArrayHoisting) { |
| 201 | BuildLoop(); |
| 202 | |
| 203 | // Populate the loop with instructions: set/get array with same types. |
| 204 | HInstruction* get_array = new (&allocator_) HArrayGet( |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 205 | parameter_, int_constant_, DataType::Type::kFloat32, 0); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 206 | loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); |
| 207 | HInstruction* set_array = new (&allocator_) HArraySet( |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 208 | parameter_, get_array, float_constant_, DataType::Type::kFloat32, 0); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 209 | loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); |
| 210 | |
Aart Bik | 8f08f9e | 2015-07-22 11:27:39 -0700 | [diff] [blame] | 211 | EXPECT_EQ(get_array->GetBlock(), loop_body_); |
| 212 | EXPECT_EQ(set_array->GetBlock(), loop_body_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 213 | PerformLICM(); |
Aart Bik | 8f08f9e | 2015-07-22 11:27:39 -0700 | [diff] [blame] | 214 | EXPECT_EQ(get_array->GetBlock(), loop_body_); |
| 215 | EXPECT_EQ(set_array->GetBlock(), loop_body_); |
Aart Bik | 3f307f3 | 2015-07-21 18:30:18 -0700 | [diff] [blame] | 216 | } |
| 217 | |
| 218 | } // namespace art |