| /* |
| * Copyright (C) 2014 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "gvn.h" |
| |
| #include "base/arena_allocator.h" |
| #include "builder.h" |
| #include "nodes.h" |
| #include "optimizing_unit_test.h" |
| #include "side_effects_analysis.h" |
| |
| namespace art { |
| |
| class GVNTest : public OptimizingUnitTest {}; |
| |
| TEST_F(GVNTest, LocalFieldElimination) { |
| HGraph* graph = CreateGraph(); |
| HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph); |
| graph->AddBlock(entry); |
| graph->SetEntryBlock(entry); |
| HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(), |
| dex::TypeIndex(0), |
| 0, |
| DataType::Type::kReference); |
| entry->AddInstruction(parameter); |
| |
| HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph); |
| graph->AddBlock(block); |
| entry->AddSuccessor(block); |
| |
| block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kReference, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kReference, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| HInstruction* to_remove = block->GetLastInstruction(); |
| block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kReference, |
| MemberOffset(43), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| HInstruction* different_offset = block->GetLastInstruction(); |
| // Kill the value. |
| block->AddInstruction(new (GetAllocator()) HInstanceFieldSet(parameter, |
| parameter, |
| nullptr, |
| DataType::Type::kReference, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kReference, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| HInstruction* use_after_kill = block->GetLastInstruction(); |
| block->AddInstruction(new (GetAllocator()) HExit()); |
| |
| ASSERT_EQ(to_remove->GetBlock(), block); |
| ASSERT_EQ(different_offset->GetBlock(), block); |
| ASSERT_EQ(use_after_kill->GetBlock(), block); |
| |
| graph->BuildDominatorTree(); |
| SideEffectsAnalysis side_effects(graph); |
| side_effects.Run(); |
| GVNOptimization(graph, side_effects).Run(); |
| |
| ASSERT_TRUE(to_remove->GetBlock() == nullptr); |
| ASSERT_EQ(different_offset->GetBlock(), block); |
| ASSERT_EQ(use_after_kill->GetBlock(), block); |
| } |
| |
| TEST_F(GVNTest, GlobalFieldElimination) { |
| HGraph* graph = CreateGraph(); |
| HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph); |
| graph->AddBlock(entry); |
| graph->SetEntryBlock(entry); |
| HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(), |
| dex::TypeIndex(0), |
| 0, |
| DataType::Type::kReference); |
| entry->AddInstruction(parameter); |
| |
| HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph); |
| graph->AddBlock(block); |
| entry->AddSuccessor(block); |
| block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kBool, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| |
| block->AddInstruction(new (GetAllocator()) HIf(block->GetLastInstruction())); |
| HBasicBlock* then = new (GetAllocator()) HBasicBlock(graph); |
| HBasicBlock* else_ = new (GetAllocator()) HBasicBlock(graph); |
| HBasicBlock* join = new (GetAllocator()) HBasicBlock(graph); |
| graph->AddBlock(then); |
| graph->AddBlock(else_); |
| graph->AddBlock(join); |
| |
| block->AddSuccessor(then); |
| block->AddSuccessor(else_); |
| then->AddSuccessor(join); |
| else_->AddSuccessor(join); |
| |
| then->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kBool, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| then->AddInstruction(new (GetAllocator()) HGoto()); |
| else_->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kBool, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| else_->AddInstruction(new (GetAllocator()) HGoto()); |
| join->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kBool, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| join->AddInstruction(new (GetAllocator()) HExit()); |
| |
| graph->BuildDominatorTree(); |
| SideEffectsAnalysis side_effects(graph); |
| side_effects.Run(); |
| GVNOptimization(graph, side_effects).Run(); |
| |
| // Check that all field get instructions have been GVN'ed. |
| ASSERT_TRUE(then->GetFirstInstruction()->IsGoto()); |
| ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto()); |
| ASSERT_TRUE(join->GetFirstInstruction()->IsExit()); |
| } |
| |
| TEST_F(GVNTest, LoopFieldElimination) { |
| HGraph* graph = CreateGraph(); |
| HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph); |
| graph->AddBlock(entry); |
| graph->SetEntryBlock(entry); |
| |
| HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(), |
| dex::TypeIndex(0), |
| 0, |
| DataType::Type::kReference); |
| entry->AddInstruction(parameter); |
| |
| HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph); |
| graph->AddBlock(block); |
| entry->AddSuccessor(block); |
| block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kBool, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| block->AddInstruction(new (GetAllocator()) HGoto()); |
| |
| HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph); |
| HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph); |
| HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph); |
| |
| graph->AddBlock(loop_header); |
| graph->AddBlock(loop_body); |
| graph->AddBlock(exit); |
| block->AddSuccessor(loop_header); |
| loop_header->AddSuccessor(loop_body); |
| loop_header->AddSuccessor(exit); |
| loop_body->AddSuccessor(loop_header); |
| |
| loop_header->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kBool, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction(); |
| loop_header->AddInstruction(new (GetAllocator()) HIf(block->GetLastInstruction())); |
| |
| // Kill inside the loop body to prevent field gets inside the loop header |
| // and the body to be GVN'ed. |
| loop_body->AddInstruction(new (GetAllocator()) HInstanceFieldSet(parameter, |
| parameter, |
| nullptr, |
| DataType::Type::kBool, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| HInstruction* field_set = loop_body->GetLastInstruction(); |
| loop_body->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kBool, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction(); |
| loop_body->AddInstruction(new (GetAllocator()) HGoto()); |
| |
| exit->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter, |
| nullptr, |
| DataType::Type::kBool, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| HInstruction* field_get_in_exit = exit->GetLastInstruction(); |
| exit->AddInstruction(new (GetAllocator()) HExit()); |
| |
| ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header); |
| ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); |
| ASSERT_EQ(field_get_in_exit->GetBlock(), exit); |
| |
| graph->BuildDominatorTree(); |
| { |
| SideEffectsAnalysis side_effects(graph); |
| side_effects.Run(); |
| GVNOptimization(graph, side_effects).Run(); |
| } |
| |
| // Check that all field get instructions are still there. |
| ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header); |
| ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); |
| // The exit block is dominated by the loop header, whose field get |
| // does not get killed by the loop flags. |
| ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr); |
| |
| // Now remove the field set, and check that all field get instructions have been GVN'ed. |
| loop_body->RemoveInstruction(field_set); |
| { |
| SideEffectsAnalysis side_effects(graph); |
| side_effects.Run(); |
| GVNOptimization(graph, side_effects).Run(); |
| } |
| |
| ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr); |
| ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr); |
| ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr); |
| } |
| |
| // Test that inner loops affect the side effects of the outer loop. |
| TEST_F(GVNTest, LoopSideEffects) { |
| static const SideEffects kCanTriggerGC = SideEffects::CanTriggerGC(); |
| |
| HGraph* graph = CreateGraph(); |
| HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph); |
| graph->AddBlock(entry); |
| graph->SetEntryBlock(entry); |
| |
| HBasicBlock* outer_loop_header = new (GetAllocator()) HBasicBlock(graph); |
| HBasicBlock* outer_loop_body = new (GetAllocator()) HBasicBlock(graph); |
| HBasicBlock* outer_loop_exit = new (GetAllocator()) HBasicBlock(graph); |
| HBasicBlock* inner_loop_header = new (GetAllocator()) HBasicBlock(graph); |
| HBasicBlock* inner_loop_body = new (GetAllocator()) HBasicBlock(graph); |
| HBasicBlock* inner_loop_exit = new (GetAllocator()) HBasicBlock(graph); |
| |
| graph->AddBlock(outer_loop_header); |
| graph->AddBlock(outer_loop_body); |
| graph->AddBlock(outer_loop_exit); |
| graph->AddBlock(inner_loop_header); |
| graph->AddBlock(inner_loop_body); |
| graph->AddBlock(inner_loop_exit); |
| |
| entry->AddSuccessor(outer_loop_header); |
| outer_loop_header->AddSuccessor(outer_loop_body); |
| outer_loop_header->AddSuccessor(outer_loop_exit); |
| outer_loop_body->AddSuccessor(inner_loop_header); |
| inner_loop_header->AddSuccessor(inner_loop_body); |
| inner_loop_header->AddSuccessor(inner_loop_exit); |
| inner_loop_body->AddSuccessor(inner_loop_header); |
| inner_loop_exit->AddSuccessor(outer_loop_header); |
| |
| HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(), |
| dex::TypeIndex(0), |
| 0, |
| DataType::Type::kBool); |
| entry->AddInstruction(parameter); |
| entry->AddInstruction(new (GetAllocator()) HGoto()); |
| outer_loop_header->AddInstruction(new (GetAllocator()) HSuspendCheck()); |
| outer_loop_header->AddInstruction(new (GetAllocator()) HIf(parameter)); |
| outer_loop_body->AddInstruction(new (GetAllocator()) HGoto()); |
| inner_loop_header->AddInstruction(new (GetAllocator()) HSuspendCheck()); |
| inner_loop_header->AddInstruction(new (GetAllocator()) HIf(parameter)); |
| inner_loop_body->AddInstruction(new (GetAllocator()) HGoto()); |
| inner_loop_exit->AddInstruction(new (GetAllocator()) HGoto()); |
| outer_loop_exit->AddInstruction(new (GetAllocator()) HExit()); |
| |
| graph->BuildDominatorTree(); |
| |
| ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn( |
| *outer_loop_header->GetLoopInformation())); |
| |
| // Check that the only side effect of loops is to potentially trigger GC. |
| { |
| // Make one block with a side effect. |
| entry->AddInstruction(new (GetAllocator()) HInstanceFieldSet(parameter, |
| parameter, |
| nullptr, |
| DataType::Type::kReference, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0)); |
| |
| SideEffectsAnalysis side_effects(graph); |
| side_effects.Run(); |
| |
| ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite()); |
| ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite()); |
| ASSERT_FALSE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite()); |
| ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite()); |
| ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).Equals(kCanTriggerGC)); |
| ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC)); |
| } |
| |
| // Check that the side effects of the outer loop does not affect the inner loop. |
| { |
| outer_loop_body->InsertInstructionBefore( |
| new (GetAllocator()) HInstanceFieldSet(parameter, |
| parameter, |
| nullptr, |
| DataType::Type::kReference, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0), |
| outer_loop_body->GetLastInstruction()); |
| |
| SideEffectsAnalysis side_effects(graph); |
| side_effects.Run(); |
| |
| ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite()); |
| ASSERT_TRUE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite()); |
| ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite()); |
| ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite()); |
| ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC)); |
| } |
| |
| // Check that the side effects of the inner loop affects the outer loop. |
| { |
| outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction()); |
| inner_loop_body->InsertInstructionBefore( |
| new (GetAllocator()) HInstanceFieldSet(parameter, |
| parameter, |
| nullptr, |
| DataType::Type::kReference, |
| MemberOffset(42), |
| false, |
| kUnknownFieldIndex, |
| kUnknownClassDefIndex, |
| graph->GetDexFile(), |
| 0), |
| inner_loop_body->GetLastInstruction()); |
| |
| SideEffectsAnalysis side_effects(graph); |
| side_effects.Run(); |
| |
| ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite()); |
| ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite()); |
| ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite()); |
| ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite()); |
| } |
| } |
| } // namespace art |