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