Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 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 "gvn.h" |
| 18 | |
Mathieu Chartier | b666f48 | 2015-02-18 14:33:14 -0800 | [diff] [blame] | 19 | #include "base/arena_allocator.h" |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 20 | #include "builder.h" |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 21 | #include "nodes.h" |
| 22 | #include "optimizing_unit_test.h" |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 23 | #include "side_effects_analysis.h" |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 24 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 25 | namespace art { |
| 26 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 27 | class GVNTest : public CommonCompilerTest {}; |
| 28 | |
| 29 | TEST_F(GVNTest, LocalFieldElimination) { |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 30 | ArenaPool pool; |
| 31 | ArenaAllocator allocator(&pool); |
| 32 | |
Nicolas Geoffray | 0a23d74 | 2015-05-07 11:57:35 +0100 | [diff] [blame] | 33 | HGraph* graph = CreateGraph(&allocator); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 34 | HBasicBlock* entry = new (&allocator) HBasicBlock(graph); |
| 35 | graph->AddBlock(entry); |
| 36 | graph->SetEntryBlock(entry); |
Calin Juravle | e6e3bea | 2015-10-14 13:53:10 +0000 | [diff] [blame] | 37 | HInstruction* parameter = new (&allocator) HParameterValue(graph->GetDexFile(), |
Andreas Gampe | a5b09a6 | 2016-11-17 15:21:22 -0800 | [diff] [blame] | 38 | dex::TypeIndex(0), |
Calin Juravle | e6e3bea | 2015-10-14 13:53:10 +0000 | [diff] [blame] | 39 | 0, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 40 | DataType::Type::kReference); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 41 | entry->AddInstruction(parameter); |
| 42 | |
| 43 | HBasicBlock* block = new (&allocator) HBasicBlock(graph); |
| 44 | graph->AddBlock(block); |
| 45 | entry->AddSuccessor(block); |
| 46 | |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 47 | block->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 48 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 49 | DataType::Type::kReference, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 50 | MemberOffset(42), |
| 51 | false, |
| 52 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 53 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 54 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 55 | 0)); |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 56 | block->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 57 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 58 | DataType::Type::kReference, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 59 | MemberOffset(42), |
| 60 | false, |
| 61 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 62 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 63 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 64 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 65 | HInstruction* to_remove = block->GetLastInstruction(); |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 66 | block->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 67 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 68 | DataType::Type::kReference, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 69 | MemberOffset(43), |
| 70 | false, |
| 71 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 72 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 73 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 74 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 75 | HInstruction* different_offset = block->GetLastInstruction(); |
| 76 | // Kill the value. |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 77 | block->AddInstruction(new (&allocator) HInstanceFieldSet(parameter, |
| 78 | parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 79 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 80 | DataType::Type::kReference, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 81 | MemberOffset(42), |
| 82 | false, |
| 83 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 84 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 85 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 86 | 0)); |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 87 | block->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 88 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 89 | DataType::Type::kReference, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 90 | MemberOffset(42), |
| 91 | false, |
| 92 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 93 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 94 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 95 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 96 | HInstruction* use_after_kill = block->GetLastInstruction(); |
| 97 | block->AddInstruction(new (&allocator) HExit()); |
| 98 | |
| 99 | ASSERT_EQ(to_remove->GetBlock(), block); |
| 100 | ASSERT_EQ(different_offset->GetBlock(), block); |
| 101 | ASSERT_EQ(use_after_kill->GetBlock(), block); |
| 102 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 103 | graph->BuildDominatorTree(); |
Nicolas Geoffray | e6f1715 | 2015-01-26 15:13:47 +0000 | [diff] [blame] | 104 | SideEffectsAnalysis side_effects(graph); |
| 105 | side_effects.Run(); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 106 | GVNOptimization(graph, side_effects).Run(); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 107 | |
| 108 | ASSERT_TRUE(to_remove->GetBlock() == nullptr); |
| 109 | ASSERT_EQ(different_offset->GetBlock(), block); |
| 110 | ASSERT_EQ(use_after_kill->GetBlock(), block); |
| 111 | } |
| 112 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 113 | TEST_F(GVNTest, GlobalFieldElimination) { |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 114 | ArenaPool pool; |
| 115 | ArenaAllocator allocator(&pool); |
| 116 | |
Nicolas Geoffray | 0a23d74 | 2015-05-07 11:57:35 +0100 | [diff] [blame] | 117 | HGraph* graph = CreateGraph(&allocator); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 118 | HBasicBlock* entry = new (&allocator) HBasicBlock(graph); |
| 119 | graph->AddBlock(entry); |
| 120 | graph->SetEntryBlock(entry); |
Calin Juravle | e6e3bea | 2015-10-14 13:53:10 +0000 | [diff] [blame] | 121 | HInstruction* parameter = new (&allocator) HParameterValue(graph->GetDexFile(), |
Andreas Gampe | a5b09a6 | 2016-11-17 15:21:22 -0800 | [diff] [blame] | 122 | dex::TypeIndex(0), |
Calin Juravle | e6e3bea | 2015-10-14 13:53:10 +0000 | [diff] [blame] | 123 | 0, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 124 | DataType::Type::kReference); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 125 | entry->AddInstruction(parameter); |
| 126 | |
| 127 | HBasicBlock* block = new (&allocator) HBasicBlock(graph); |
| 128 | graph->AddBlock(block); |
| 129 | entry->AddSuccessor(block); |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 130 | block->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 131 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 132 | DataType::Type::kBool, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 133 | MemberOffset(42), |
| 134 | false, |
| 135 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 136 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 137 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 138 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 139 | |
| 140 | block->AddInstruction(new (&allocator) HIf(block->GetLastInstruction())); |
| 141 | HBasicBlock* then = new (&allocator) HBasicBlock(graph); |
| 142 | HBasicBlock* else_ = new (&allocator) HBasicBlock(graph); |
| 143 | HBasicBlock* join = new (&allocator) HBasicBlock(graph); |
| 144 | graph->AddBlock(then); |
| 145 | graph->AddBlock(else_); |
| 146 | graph->AddBlock(join); |
| 147 | |
| 148 | block->AddSuccessor(then); |
| 149 | block->AddSuccessor(else_); |
| 150 | then->AddSuccessor(join); |
| 151 | else_->AddSuccessor(join); |
| 152 | |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 153 | then->AddInstruction(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::kBool, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 156 | MemberOffset(42), |
| 157 | false, |
| 158 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 159 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 160 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 161 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 162 | then->AddInstruction(new (&allocator) HGoto()); |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 163 | else_->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 164 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 165 | DataType::Type::kBool, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 166 | MemberOffset(42), |
| 167 | false, |
| 168 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 169 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 170 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 171 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 172 | else_->AddInstruction(new (&allocator) HGoto()); |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 173 | join->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 174 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 175 | DataType::Type::kBool, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 176 | MemberOffset(42), |
| 177 | false, |
| 178 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 179 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 180 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 181 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 182 | join->AddInstruction(new (&allocator) HExit()); |
| 183 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 184 | graph->BuildDominatorTree(); |
Nicolas Geoffray | e6f1715 | 2015-01-26 15:13:47 +0000 | [diff] [blame] | 185 | SideEffectsAnalysis side_effects(graph); |
| 186 | side_effects.Run(); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 187 | GVNOptimization(graph, side_effects).Run(); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 188 | |
| 189 | // Check that all field get instructions have been GVN'ed. |
| 190 | ASSERT_TRUE(then->GetFirstInstruction()->IsGoto()); |
| 191 | ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto()); |
| 192 | ASSERT_TRUE(join->GetFirstInstruction()->IsExit()); |
| 193 | } |
| 194 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 195 | TEST_F(GVNTest, LoopFieldElimination) { |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 196 | ArenaPool pool; |
| 197 | ArenaAllocator allocator(&pool); |
| 198 | |
Nicolas Geoffray | 0a23d74 | 2015-05-07 11:57:35 +0100 | [diff] [blame] | 199 | HGraph* graph = CreateGraph(&allocator); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 200 | HBasicBlock* entry = new (&allocator) HBasicBlock(graph); |
| 201 | graph->AddBlock(entry); |
| 202 | graph->SetEntryBlock(entry); |
| 203 | |
Calin Juravle | e6e3bea | 2015-10-14 13:53:10 +0000 | [diff] [blame] | 204 | HInstruction* parameter = new (&allocator) HParameterValue(graph->GetDexFile(), |
Andreas Gampe | a5b09a6 | 2016-11-17 15:21:22 -0800 | [diff] [blame] | 205 | dex::TypeIndex(0), |
Calin Juravle | e6e3bea | 2015-10-14 13:53:10 +0000 | [diff] [blame] | 206 | 0, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 207 | DataType::Type::kReference); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 208 | entry->AddInstruction(parameter); |
| 209 | |
| 210 | HBasicBlock* block = new (&allocator) HBasicBlock(graph); |
| 211 | graph->AddBlock(block); |
| 212 | entry->AddSuccessor(block); |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 213 | block->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 214 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 215 | DataType::Type::kBool, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 216 | MemberOffset(42), |
| 217 | false, |
| 218 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 219 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 220 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 221 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 222 | block->AddInstruction(new (&allocator) HGoto()); |
| 223 | |
| 224 | HBasicBlock* loop_header = new (&allocator) HBasicBlock(graph); |
| 225 | HBasicBlock* loop_body = new (&allocator) HBasicBlock(graph); |
| 226 | HBasicBlock* exit = new (&allocator) HBasicBlock(graph); |
| 227 | |
| 228 | graph->AddBlock(loop_header); |
| 229 | graph->AddBlock(loop_body); |
| 230 | graph->AddBlock(exit); |
| 231 | block->AddSuccessor(loop_header); |
| 232 | loop_header->AddSuccessor(loop_body); |
| 233 | loop_header->AddSuccessor(exit); |
| 234 | loop_body->AddSuccessor(loop_header); |
| 235 | |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 236 | loop_header->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 237 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 238 | DataType::Type::kBool, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 239 | MemberOffset(42), |
| 240 | false, |
| 241 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 242 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 243 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 244 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 245 | HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction(); |
| 246 | loop_header->AddInstruction(new (&allocator) HIf(block->GetLastInstruction())); |
| 247 | |
| 248 | // Kill inside the loop body to prevent field gets inside the loop header |
| 249 | // and the body to be GVN'ed. |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 250 | loop_body->AddInstruction(new (&allocator) HInstanceFieldSet(parameter, |
| 251 | parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 252 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 253 | DataType::Type::kBool, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 254 | MemberOffset(42), |
| 255 | false, |
| 256 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 257 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 258 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 259 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 260 | HInstruction* field_set = loop_body->GetLastInstruction(); |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 261 | loop_body->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 262 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 263 | DataType::Type::kBool, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 264 | MemberOffset(42), |
| 265 | false, |
| 266 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 267 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 268 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 269 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 270 | HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction(); |
| 271 | loop_body->AddInstruction(new (&allocator) HGoto()); |
| 272 | |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 273 | exit->AddInstruction(new (&allocator) HInstanceFieldGet(parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 274 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 275 | DataType::Type::kBool, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 276 | MemberOffset(42), |
| 277 | false, |
| 278 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 279 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 280 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 281 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 282 | HInstruction* field_get_in_exit = exit->GetLastInstruction(); |
| 283 | exit->AddInstruction(new (&allocator) HExit()); |
| 284 | |
| 285 | ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header); |
| 286 | ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); |
| 287 | ASSERT_EQ(field_get_in_exit->GetBlock(), exit); |
| 288 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 289 | graph->BuildDominatorTree(); |
Nicolas Geoffray | e6f1715 | 2015-01-26 15:13:47 +0000 | [diff] [blame] | 290 | { |
| 291 | SideEffectsAnalysis side_effects(graph); |
| 292 | side_effects.Run(); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 293 | GVNOptimization(graph, side_effects).Run(); |
Nicolas Geoffray | e6f1715 | 2015-01-26 15:13:47 +0000 | [diff] [blame] | 294 | } |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 295 | |
| 296 | // Check that all field get instructions are still there. |
| 297 | ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header); |
| 298 | ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); |
| 299 | // The exit block is dominated by the loop header, whose field get |
| 300 | // does not get killed by the loop flags. |
| 301 | ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr); |
| 302 | |
| 303 | // Now remove the field set, and check that all field get instructions have been GVN'ed. |
| 304 | loop_body->RemoveInstruction(field_set); |
Nicolas Geoffray | e6f1715 | 2015-01-26 15:13:47 +0000 | [diff] [blame] | 305 | { |
| 306 | SideEffectsAnalysis side_effects(graph); |
| 307 | side_effects.Run(); |
Nicolas Geoffray | 827eedb | 2015-01-26 15:18:36 +0000 | [diff] [blame] | 308 | GVNOptimization(graph, side_effects).Run(); |
Nicolas Geoffray | e6f1715 | 2015-01-26 15:13:47 +0000 | [diff] [blame] | 309 | } |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 310 | |
| 311 | ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr); |
| 312 | ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr); |
| 313 | ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr); |
| 314 | } |
| 315 | |
| 316 | // Test that inner loops affect the side effects of the outer loop. |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 317 | TEST_F(GVNTest, LoopSideEffects) { |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 318 | ArenaPool pool; |
| 319 | ArenaAllocator allocator(&pool); |
| 320 | |
Alexandre Rames | 78e3ef6 | 2015-08-12 13:43:29 +0100 | [diff] [blame] | 321 | static const SideEffects kCanTriggerGC = SideEffects::CanTriggerGC(); |
| 322 | |
Nicolas Geoffray | 0a23d74 | 2015-05-07 11:57:35 +0100 | [diff] [blame] | 323 | HGraph* graph = CreateGraph(&allocator); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 324 | HBasicBlock* entry = new (&allocator) HBasicBlock(graph); |
| 325 | graph->AddBlock(entry); |
| 326 | graph->SetEntryBlock(entry); |
| 327 | |
| 328 | HBasicBlock* outer_loop_header = new (&allocator) HBasicBlock(graph); |
| 329 | HBasicBlock* outer_loop_body = new (&allocator) HBasicBlock(graph); |
| 330 | HBasicBlock* outer_loop_exit = new (&allocator) HBasicBlock(graph); |
| 331 | HBasicBlock* inner_loop_header = new (&allocator) HBasicBlock(graph); |
| 332 | HBasicBlock* inner_loop_body = new (&allocator) HBasicBlock(graph); |
| 333 | HBasicBlock* inner_loop_exit = new (&allocator) HBasicBlock(graph); |
| 334 | |
| 335 | graph->AddBlock(outer_loop_header); |
| 336 | graph->AddBlock(outer_loop_body); |
| 337 | graph->AddBlock(outer_loop_exit); |
| 338 | graph->AddBlock(inner_loop_header); |
| 339 | graph->AddBlock(inner_loop_body); |
| 340 | graph->AddBlock(inner_loop_exit); |
| 341 | |
| 342 | entry->AddSuccessor(outer_loop_header); |
| 343 | outer_loop_header->AddSuccessor(outer_loop_body); |
| 344 | outer_loop_header->AddSuccessor(outer_loop_exit); |
| 345 | outer_loop_body->AddSuccessor(inner_loop_header); |
| 346 | inner_loop_header->AddSuccessor(inner_loop_body); |
| 347 | inner_loop_header->AddSuccessor(inner_loop_exit); |
| 348 | inner_loop_body->AddSuccessor(inner_loop_header); |
| 349 | inner_loop_exit->AddSuccessor(outer_loop_header); |
| 350 | |
Calin Juravle | e6e3bea | 2015-10-14 13:53:10 +0000 | [diff] [blame] | 351 | HInstruction* parameter = new (&allocator) HParameterValue(graph->GetDexFile(), |
Andreas Gampe | a5b09a6 | 2016-11-17 15:21:22 -0800 | [diff] [blame] | 352 | dex::TypeIndex(0), |
Calin Juravle | e6e3bea | 2015-10-14 13:53:10 +0000 | [diff] [blame] | 353 | 0, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 354 | DataType::Type::kBool); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 355 | entry->AddInstruction(parameter); |
| 356 | entry->AddInstruction(new (&allocator) HGoto()); |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 357 | outer_loop_header->AddInstruction(new (&allocator) HSuspendCheck()); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 358 | outer_loop_header->AddInstruction(new (&allocator) HIf(parameter)); |
| 359 | outer_loop_body->AddInstruction(new (&allocator) HGoto()); |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 360 | inner_loop_header->AddInstruction(new (&allocator) HSuspendCheck()); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 361 | inner_loop_header->AddInstruction(new (&allocator) HIf(parameter)); |
| 362 | inner_loop_body->AddInstruction(new (&allocator) HGoto()); |
| 363 | inner_loop_exit->AddInstruction(new (&allocator) HGoto()); |
| 364 | outer_loop_exit->AddInstruction(new (&allocator) HExit()); |
| 365 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 366 | graph->BuildDominatorTree(); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 367 | |
| 368 | ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn( |
| 369 | *outer_loop_header->GetLoopInformation())); |
| 370 | |
Alexandre Rames | 78e3ef6 | 2015-08-12 13:43:29 +0100 | [diff] [blame] | 371 | // Check that the only side effect of loops is to potentially trigger GC. |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 372 | { |
| 373 | // Make one block with a side effect. |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 374 | entry->AddInstruction(new (&allocator) HInstanceFieldSet(parameter, |
| 375 | parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 376 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 377 | DataType::Type::kReference, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 378 | MemberOffset(42), |
| 379 | false, |
| 380 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 381 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 382 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 383 | 0)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 384 | |
Nicolas Geoffray | e6f1715 | 2015-01-26 15:13:47 +0000 | [diff] [blame] | 385 | SideEffectsAnalysis side_effects(graph); |
| 386 | side_effects.Run(); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 387 | |
Aart Bik | 854a02b | 2015-07-14 16:07:00 -0700 | [diff] [blame] | 388 | ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite()); |
| 389 | ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite()); |
| 390 | ASSERT_FALSE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite()); |
| 391 | ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite()); |
Alexandre Rames | 78e3ef6 | 2015-08-12 13:43:29 +0100 | [diff] [blame] | 392 | ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).Equals(kCanTriggerGC)); |
| 393 | ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 394 | } |
| 395 | |
| 396 | // Check that the side effects of the outer loop does not affect the inner loop. |
| 397 | { |
| 398 | outer_loop_body->InsertInstructionBefore( |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 399 | new (&allocator) HInstanceFieldSet(parameter, |
| 400 | parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 401 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 402 | DataType::Type::kReference, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 403 | MemberOffset(42), |
| 404 | false, |
| 405 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 406 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 407 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 408 | 0), |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 409 | outer_loop_body->GetLastInstruction()); |
| 410 | |
Nicolas Geoffray | e6f1715 | 2015-01-26 15:13:47 +0000 | [diff] [blame] | 411 | SideEffectsAnalysis side_effects(graph); |
| 412 | side_effects.Run(); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 413 | |
Aart Bik | 854a02b | 2015-07-14 16:07:00 -0700 | [diff] [blame] | 414 | ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite()); |
| 415 | ASSERT_TRUE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite()); |
| 416 | ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite()); |
| 417 | ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite()); |
Alexandre Rames | 78e3ef6 | 2015-08-12 13:43:29 +0100 | [diff] [blame] | 418 | ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC)); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 419 | } |
| 420 | |
| 421 | // Check that the side effects of the inner loop affects the outer loop. |
| 422 | { |
| 423 | outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction()); |
| 424 | inner_loop_body->InsertInstructionBefore( |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 425 | new (&allocator) HInstanceFieldSet(parameter, |
| 426 | parameter, |
Nicolas Geoffray | c52b26d | 2016-12-19 09:18:07 +0000 | [diff] [blame] | 427 | nullptr, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 428 | DataType::Type::kReference, |
Guillaume "Vermeille" Sanchez | 104fd8a | 2015-05-20 17:52:13 +0100 | [diff] [blame] | 429 | MemberOffset(42), |
| 430 | false, |
| 431 | kUnknownFieldIndex, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 432 | kUnknownClassDefIndex, |
Mathieu Chartier | 736b560 | 2015-09-02 14:54:11 -0700 | [diff] [blame] | 433 | graph->GetDexFile(), |
Calin Juravle | 154746b | 2015-10-06 15:46:54 +0100 | [diff] [blame] | 434 | 0), |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 435 | inner_loop_body->GetLastInstruction()); |
| 436 | |
Nicolas Geoffray | e6f1715 | 2015-01-26 15:13:47 +0000 | [diff] [blame] | 437 | SideEffectsAnalysis side_effects(graph); |
| 438 | side_effects.Run(); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 439 | |
Aart Bik | 854a02b | 2015-07-14 16:07:00 -0700 | [diff] [blame] | 440 | ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite()); |
| 441 | ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite()); |
| 442 | ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite()); |
| 443 | ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite()); |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 444 | } |
| 445 | } |
| 446 | } // namespace art |