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