diff options
-rw-r--r-- | build/Android.gtest.mk | 1 | ||||
-rw-r--r-- | compiler/optimizing/graph_test.cc | 322 | ||||
-rw-r--r-- | compiler/optimizing/live_ranges_test.cc | 15 | ||||
-rw-r--r-- | compiler/optimizing/nodes.cc | 19 | ||||
-rw-r--r-- | compiler/optimizing/nodes.h | 44 | ||||
-rw-r--r-- | compiler/optimizing/ssa_builder.cc | 4 | ||||
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.cc | 2 | ||||
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.h | 2 | ||||
-rw-r--r-- | compiler/optimizing/ssa_test.cc | 47 |
9 files changed, 421 insertions, 35 deletions
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk index b07e4f8..b32fc9b 100644 --- a/build/Android.gtest.mk +++ b/build/Android.gtest.mk @@ -80,6 +80,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \ compiler/optimizing/codegen_test.cc \ compiler/optimizing/dominator_test.cc \ compiler/optimizing/find_loops_test.cc \ + compiler/optimizing/graph_test.cc \ compiler/optimizing/linearize_test.cc \ compiler/optimizing/liveness_test.cc \ compiler/optimizing/live_interval_test.cc \ diff --git a/compiler/optimizing/graph_test.cc b/compiler/optimizing/graph_test.cc new file mode 100644 index 0000000..371478c --- /dev/null +++ b/compiler/optimizing/graph_test.cc @@ -0,0 +1,322 @@ +/* + * 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 "base/stringprintf.h" +#include "builder.h" +#include "nodes.h" +#include "optimizing_unit_test.h" +#include "pretty_printer.h" +#include "utils/arena_allocator.h" + +#include "gtest/gtest.h" + +namespace art { + +static HBasicBlock* createIfBlock(HGraph* graph, ArenaAllocator* allocator) { + HBasicBlock* if_block = new (allocator) HBasicBlock(graph); + graph->AddBlock(if_block); + HInstruction* instr = new (allocator) HIntConstant(4); + if_block->AddInstruction(instr); + instr = new (allocator) HIf(instr); + if_block->AddInstruction(instr); + return if_block; +} + +static HBasicBlock* createGotoBlock(HGraph* graph, ArenaAllocator* allocator) { + HBasicBlock* block = new (allocator) HBasicBlock(graph); + graph->AddBlock(block); + HInstruction* got = new (allocator) HGoto(); + block->AddInstruction(got); + return block; +} + +static HBasicBlock* createReturnBlock(HGraph* graph, ArenaAllocator* allocator) { + HBasicBlock* block = new (allocator) HBasicBlock(graph); + graph->AddBlock(block); + HInstruction* return_instr = new (allocator) HReturnVoid(); + block->AddInstruction(return_instr); + return block; +} + +static HBasicBlock* createExitBlock(HGraph* graph, ArenaAllocator* allocator) { + HBasicBlock* block = new (allocator) HBasicBlock(graph); + graph->AddBlock(block); + HInstruction* exit_instr = new (allocator) HExit(); + block->AddInstruction(exit_instr); + return block; +} + + +// Test that the successors of an if block stay consistent after a SimplifyCFG. +// This test sets the false block to be the return block. +TEST(GraphTest, IfSuccessorSimpleJoinBlock1) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry_block = createGotoBlock(graph, &allocator); + HBasicBlock* if_block = createIfBlock(graph, &allocator); + HBasicBlock* if_true = createGotoBlock(graph, &allocator); + HBasicBlock* return_block = createReturnBlock(graph, &allocator); + HBasicBlock* exit_block = createExitBlock(graph, &allocator); + + entry_block->AddSuccessor(if_block); + if_block->AddSuccessor(if_true); + if_true->AddSuccessor(return_block); + if_block->AddSuccessor(return_block); + return_block->AddSuccessor(exit_block); + + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true); + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); + + graph->SimplifyCFG(); + + // Ensure we still have the same if true block. + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_true); + + // Ensure the critical edge has been removed. + HBasicBlock* false_block = if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(); + ASSERT_NE(false_block, return_block); + + // Ensure the new block branches to the join block. + ASSERT_EQ(false_block->GetSuccessors().Get(0), return_block); +} + +// Test that the successors of an if block stay consistent after a SimplifyCFG. +// This test sets the true block to be the return block. +TEST(GraphTest, IfSuccessorSimpleJoinBlock2) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry_block = createGotoBlock(graph, &allocator); + HBasicBlock* if_block = createIfBlock(graph, &allocator); + HBasicBlock* if_false = createGotoBlock(graph, &allocator); + HBasicBlock* return_block = createReturnBlock(graph, &allocator); + HBasicBlock* exit_block = createExitBlock(graph, &allocator); + + entry_block->AddSuccessor(if_block); + if_block->AddSuccessor(return_block); + if_false->AddSuccessor(return_block); + if_block->AddSuccessor(if_false); + return_block->AddSuccessor(exit_block); + + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false); + + graph->SimplifyCFG(); + + // Ensure we still have the same if true block. + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_false); + + // Ensure the critical edge has been removed. + HBasicBlock* true_block = if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(); + ASSERT_NE(true_block, return_block); + + // Ensure the new block branches to the join block. + ASSERT_EQ(true_block->GetSuccessors().Get(0), return_block); +} + +// Test that the successors of an if block stay consistent after a SimplifyCFG. +// This test sets the true block to be the loop header. +TEST(GraphTest, IfSuccessorMultipleBackEdges1) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry_block = createGotoBlock(graph, &allocator); + HBasicBlock* if_block = createIfBlock(graph, &allocator); + HBasicBlock* return_block = createReturnBlock(graph, &allocator); + HBasicBlock* exit_block = createExitBlock(graph, &allocator); + + graph->SetEntryBlock(entry_block); + entry_block->AddSuccessor(if_block); + if_block->AddSuccessor(if_block); + if_block->AddSuccessor(return_block); + return_block->AddSuccessor(exit_block); + + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), if_block); + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); + + graph->BuildDominatorTree(); + + // Ensure we still have the same if false block. + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); + + // Ensure there is only one back edge. + ASSERT_EQ(if_block->GetPredecessors().Size(), 2u); + ASSERT_EQ(if_block->GetPredecessors().Get(0), entry_block); + ASSERT_NE(if_block->GetPredecessors().Get(1), if_block); + + // Ensure the new block is the back edge. + ASSERT_EQ(if_block->GetPredecessors().Get(1), + if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor()); +} + +// Test that the successors of an if block stay consistent after a SimplifyCFG. +// This test sets the false block to be the loop header. +TEST(GraphTest, IfSuccessorMultipleBackEdges2) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry_block = createGotoBlock(graph, &allocator); + HBasicBlock* if_block = createIfBlock(graph, &allocator); + HBasicBlock* return_block = createReturnBlock(graph, &allocator); + HBasicBlock* exit_block = createExitBlock(graph, &allocator); + + graph->SetEntryBlock(entry_block); + entry_block->AddSuccessor(if_block); + if_block->AddSuccessor(return_block); + if_block->AddSuccessor(if_block); + return_block->AddSuccessor(exit_block); + + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), if_block); + + graph->BuildDominatorTree(); + + // Ensure we still have the same if true block. + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); + + // Ensure there is only one back edge. + ASSERT_EQ(if_block->GetPredecessors().Size(), 2u); + ASSERT_EQ(if_block->GetPredecessors().Get(0), entry_block); + ASSERT_NE(if_block->GetPredecessors().Get(1), if_block); + + // Ensure the new block is the back edge. + ASSERT_EQ(if_block->GetPredecessors().Get(1), + if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor()); +} + +// Test that the successors of an if block stay consistent after a SimplifyCFG. +// This test sets the true block to be a loop header with multiple pre headers. +TEST(GraphTest, IfSuccessorMultiplePreHeaders1) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry_block = createGotoBlock(graph, &allocator); + HBasicBlock* first_if_block = createIfBlock(graph, &allocator); + HBasicBlock* if_block = createIfBlock(graph, &allocator); + HBasicBlock* loop_block = createGotoBlock(graph, &allocator); + HBasicBlock* return_block = createReturnBlock(graph, &allocator); + + graph->SetEntryBlock(entry_block); + entry_block->AddSuccessor(first_if_block); + first_if_block->AddSuccessor(if_block); + first_if_block->AddSuccessor(loop_block); + loop_block->AddSuccessor(loop_block); + if_block->AddSuccessor(loop_block); + if_block->AddSuccessor(return_block); + + + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), loop_block); + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), return_block); + + graph->BuildDominatorTree(); + + HIf* if_instr = if_block->GetLastInstruction()->AsIf(); + // Ensure we still have the same if false block. + ASSERT_EQ(if_instr->IfFalseSuccessor(), return_block); + + // Ensure there is only one pre header.. + ASSERT_EQ(loop_block->GetPredecessors().Size(), 2u); + + // Ensure the new block is the successor of the true block. + ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Size(), 1u); + ASSERT_EQ(if_instr->IfTrueSuccessor()->GetSuccessors().Get(0), + loop_block->GetLoopInformation()->GetPreHeader()); +} + +// Test that the successors of an if block stay consistent after a SimplifyCFG. +// This test sets the false block to be a loop header with multiple pre headers. +TEST(GraphTest, IfSuccessorMultiplePreHeaders2) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* entry_block = createGotoBlock(graph, &allocator); + HBasicBlock* first_if_block = createIfBlock(graph, &allocator); + HBasicBlock* if_block = createIfBlock(graph, &allocator); + HBasicBlock* loop_block = createGotoBlock(graph, &allocator); + HBasicBlock* return_block = createReturnBlock(graph, &allocator); + + graph->SetEntryBlock(entry_block); + entry_block->AddSuccessor(first_if_block); + first_if_block->AddSuccessor(if_block); + first_if_block->AddSuccessor(loop_block); + loop_block->AddSuccessor(loop_block); + if_block->AddSuccessor(return_block); + if_block->AddSuccessor(loop_block); + + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfTrueSuccessor(), return_block); + ASSERT_EQ(if_block->GetLastInstruction()->AsIf()->IfFalseSuccessor(), loop_block); + + graph->BuildDominatorTree(); + + HIf* if_instr = if_block->GetLastInstruction()->AsIf(); + // Ensure we still have the same if true block. + ASSERT_EQ(if_instr->IfTrueSuccessor(), return_block); + + // Ensure there is only one pre header.. + ASSERT_EQ(loop_block->GetPredecessors().Size(), 2u); + + // Ensure the new block is the successor of the false block. + ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().Size(), 1u); + ASSERT_EQ(if_instr->IfFalseSuccessor()->GetSuccessors().Get(0), + loop_block->GetLoopInformation()->GetPreHeader()); +} + +TEST(GraphTest, InsertInstructionBefore) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + HBasicBlock* block = createGotoBlock(graph, &allocator); + HInstruction* got = block->GetLastInstruction(); + ASSERT_TRUE(got->IsControlFlow()); + + // Test at the beginning of the block. + HInstruction* first_instruction = new (&allocator) HIntConstant(4); + block->InsertInstructionBefore(first_instruction, got); + + ASSERT_NE(first_instruction->GetId(), -1); + ASSERT_EQ(first_instruction->GetBlock(), block); + ASSERT_EQ(block->GetFirstInstruction(), first_instruction); + ASSERT_EQ(block->GetLastInstruction(), got); + ASSERT_EQ(first_instruction->GetNext(), got); + ASSERT_EQ(first_instruction->GetPrevious(), nullptr); + ASSERT_EQ(got->GetNext(), nullptr); + ASSERT_EQ(got->GetPrevious(), first_instruction); + + // Test in the middle of the block. + HInstruction* second_instruction = new (&allocator) HIntConstant(4); + block->InsertInstructionBefore(second_instruction, got); + + ASSERT_NE(second_instruction->GetId(), -1); + ASSERT_EQ(second_instruction->GetBlock(), block); + ASSERT_EQ(block->GetFirstInstruction(), first_instruction); + ASSERT_EQ(block->GetLastInstruction(), got); + ASSERT_EQ(first_instruction->GetNext(), second_instruction); + ASSERT_EQ(first_instruction->GetPrevious(), nullptr); + ASSERT_EQ(second_instruction->GetNext(), got); + ASSERT_EQ(second_instruction->GetPrevious(), first_instruction); + ASSERT_EQ(got->GetNext(), nullptr); + ASSERT_EQ(got->GetPrevious(), second_instruction); +} + +} // namespace art diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc index c797497..017117a 100644 --- a/compiler/optimizing/live_ranges_test.cc +++ b/compiler/optimizing/live_ranges_test.cc @@ -152,22 +152,22 @@ TEST(LiveRangesTest, CFG3) { SsaLivenessAnalysis liveness(*graph); liveness.Analyze(); - // Test for the 0 constant. - LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); + // Test for the 4 constant. + LiveInterval* interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval(); LiveRange* range = interval->GetFirstRange(); - ASSERT_EQ(2u, range->GetStart()); + ASSERT_EQ(4u, range->GetStart()); // Last use is the phi at the return block so instruction is live until // the end of the then block. ASSERT_EQ(18u, range->GetEnd()); ASSERT_TRUE(range->GetNext() == nullptr); - // Test for the 4 constant. - interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval(); + // Test for the 0 constant. + interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); // The then branch is a hole for this constant, therefore its interval has 2 ranges. // First range starts from the definition and ends at the if block. range = interval->GetFirstRange(); - ASSERT_EQ(4u, range->GetStart()); - // 9 is the end of the if block. + ASSERT_EQ(2u, range->GetStart()); + // 14 is the end of the if block. ASSERT_EQ(14u, range->GetEnd()); // Second range is the else block. range = range->GetNext(); @@ -179,6 +179,7 @@ TEST(LiveRangesTest, CFG3) { // Test for the phi. interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval(); range = interval->GetFirstRange(); + ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(3)->GetLifetimePosition()); ASSERT_EQ(22u, range->GetStart()); ASSERT_EQ(24u, range->GetEnd()); ASSERT_TRUE(range->GetNext() == nullptr); diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 752466b..2a97fad 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -35,7 +35,7 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const { if (!visited.IsBitSet(i)) { HBasicBlock* block = blocks_.Get(i); for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { - block->GetSuccessors().Get(j)->RemovePredecessor(block, false); + block->GetSuccessors().Get(j)->RemovePredecessor(block); } for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { block->RemovePhi(it.Current()->AsPhi()); @@ -143,8 +143,7 @@ void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { HBasicBlock* new_block = new (arena_) HBasicBlock(this); AddBlock(new_block); new_block->AddInstruction(new (arena_) HGoto()); - block->RemoveSuccessor(successor); - block->AddSuccessor(new_block); + block->ReplaceSuccessor(successor, new_block); new_block->AddSuccessor(successor); if (successor->IsLoopHeader()) { // If we split at a back edge boundary, make the new block the back edge. @@ -168,8 +167,7 @@ void HGraph::SimplifyLoop(HBasicBlock* header) { new_back_edge->AddInstruction(new (arena_) HGoto()); for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) { HBasicBlock* back_edge = info->GetBackEdges().Get(pred); - header->RemovePredecessor(back_edge); - back_edge->AddSuccessor(new_back_edge); + back_edge->ReplaceSuccessor(header, new_back_edge); } info->ClearBackEdges(); info->AddBackEdge(new_back_edge); @@ -190,9 +188,8 @@ void HGraph::SimplifyLoop(HBasicBlock* header) { for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) { HBasicBlock* predecessor = header->GetPredecessors().Get(pred); if (predecessor != back_edge) { - header->RemovePredecessor(predecessor); + predecessor->ReplaceSuccessor(header, pre_header); pred--; - predecessor->AddSuccessor(pre_header); } } pre_header->AddSuccessor(header); @@ -294,12 +291,20 @@ bool HBasicBlock::Dominates(HBasicBlock* other) const { void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { DCHECK(cursor->AsPhi() == nullptr); DCHECK(instruction->AsPhi() == nullptr); + DCHECK_EQ(instruction->GetId(), -1); + DCHECK_NE(cursor->GetId(), -1); + DCHECK_EQ(cursor->GetBlock(), this); + DCHECK(!instruction->IsControlFlow()); instruction->next_ = cursor; instruction->previous_ = cursor->previous_; cursor->previous_ = instruction; if (GetFirstInstruction() == cursor) { instructions_.first_instruction_ = instruction; + } else { + instruction->previous_->next_ = instruction; } + instruction->SetBlock(this); + instruction->SetId(GetGraph()->GetNextInstructionId()); } static void Add(HInstructionList* instruction_list, diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index b1c8016..68848de 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -283,18 +283,16 @@ class HBasicBlock : public ArenaObject { block->predecessors_.Add(this); } - void RemovePredecessor(HBasicBlock* block, bool remove_in_successor = true) { - predecessors_.Delete(block); - if (remove_in_successor) { - block->successors_.Delete(this); - } + void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { + size_t successor_index = GetSuccessorIndexOf(existing); + DCHECK_NE(successor_index, static_cast<size_t>(-1)); + existing->RemovePredecessor(this); + new_block->predecessors_.Add(this); + successors_.Put(successor_index, new_block); } - void RemoveSuccessor(HBasicBlock* block, bool remove_in_predecessor = true) { - successors_.Delete(block); - if (remove_in_predecessor) { - block->predecessors_.Delete(this); - } + void RemovePredecessor(HBasicBlock* block) { + predecessors_.Delete(block); } void ClearAllPredecessors() { @@ -315,6 +313,15 @@ class HBasicBlock : public ArenaObject { return -1; } + size_t GetSuccessorIndexOf(HBasicBlock* successor) { + for (size_t i = 0, e = successors_.Size(); i < e; ++i) { + if (successors_.Get(i) == successor) { + return i; + } + } + return -1; + } + void AddInstruction(HInstruction* instruction); void RemoveInstruction(HInstruction* instruction); void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); @@ -455,6 +462,7 @@ class HInstruction : public ArenaObject { virtual void SetRawInputAt(size_t index, HInstruction* input) = 0; virtual bool NeedsEnvironment() const { return false; } + virtual bool IsControlFlow() const { return false; } void AddUseAt(HInstruction* user, size_t index) { uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_); @@ -733,7 +741,9 @@ class HTemplateInstruction: public HInstruction { // instruction that branches to the exit block. class HReturnVoid : public HTemplateInstruction<0> { public: - HReturnVoid() { } + HReturnVoid() {} + + virtual bool IsControlFlow() const { return true; } DECLARE_INSTRUCTION(ReturnVoid); @@ -749,6 +759,8 @@ class HReturn : public HTemplateInstruction<1> { SetRawInputAt(0, value); } + virtual bool IsControlFlow() const { return true; } + DECLARE_INSTRUCTION(Return); private: @@ -760,7 +772,9 @@ class HReturn : public HTemplateInstruction<1> { // exit block. class HExit : public HTemplateInstruction<0> { public: - HExit() { } + HExit() {} + + virtual bool IsControlFlow() const { return true; } DECLARE_INSTRUCTION(Exit); @@ -771,12 +785,14 @@ class HExit : public HTemplateInstruction<0> { // Jumps from one block to another. class HGoto : public HTemplateInstruction<0> { public: - HGoto() { } + HGoto() {} HBasicBlock* GetSuccessor() const { return GetBlock()->GetSuccessors().Get(0); } + virtual bool IsControlFlow() const { return true; } + DECLARE_INSTRUCTION(Goto); private: @@ -799,6 +815,8 @@ class HIf : public HTemplateInstruction<1> { return GetBlock()->GetSuccessors().Get(1); } + virtual bool IsControlFlow() const { return true; } + DECLARE_INSTRUCTION(If); private: diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index 1284a97..54c3c5d 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -102,8 +102,8 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { HInstruction* current = ValueOfLocal(block->GetPredecessors().Get(i), local); if (current == nullptr) { -// one_predecessor_has_no_value = true; -// break; + one_predecessor_has_no_value = true; + break; } else if (current != value) { is_different = true; } diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index dc4b2e5..c367611 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -134,7 +134,6 @@ void SsaLivenessAnalysis::NumberInstructions() { for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); block->SetLifetimeStart(lifetime_position); - lifetime_position += 2; for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { HInstruction* current = it.Current(); @@ -146,6 +145,7 @@ void SsaLivenessAnalysis::NumberInstructions() { } current->SetLifetimePosition(lifetime_position); } + lifetime_position += 2; for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { HInstruction* current = it.Current(); diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index 4d56e1f..733535e 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -99,7 +99,7 @@ class UsePosition : public ArenaObject { HInstruction* GetUser() const { return user_; } - void Dump(std::ostream& stream) { + void Dump(std::ostream& stream) const { stream << position_; } diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc index 485ea27..3b354f1 100644 --- a/compiler/optimizing/ssa_test.cc +++ b/compiler/optimizing/ssa_test.cc @@ -99,7 +99,7 @@ TEST(SsaTest, CFG1) { "BasicBlock 0, succ: 1\n" " 0: IntConstant 0 [2, 2]\n" " 1: Goto\n" - "BasicBlock 1, pred: 0, succ: 2, 5\n" + "BasicBlock 1, pred: 0, succ: 5, 2\n" " 2: Equal(0, 0) [3]\n" " 3: If(2)\n" "BasicBlock 2, pred: 1, succ: 3\n" @@ -129,7 +129,7 @@ TEST(SsaTest, CFG2) { " 0: IntConstant 0 [6, 3, 3]\n" " 1: IntConstant 4 [6]\n" " 2: Goto\n" - "BasicBlock 1, pred: 0, succ: 2, 5\n" + "BasicBlock 1, pred: 0, succ: 5, 2\n" " 3: Equal(0, 0) [4]\n" " 4: If(3)\n" "BasicBlock 2, pred: 1, succ: 3\n" @@ -409,7 +409,7 @@ TEST(SsaTest, Loop7) { " 3: Goto\n" "BasicBlock 1, pred: 0, succ: 2\n" " 4: Goto\n" - "BasicBlock 2, pred: 1, 5, succ: 3, 8\n" + "BasicBlock 2, pred: 1, 5, succ: 8, 3\n" " 5: Phi(0, 1) [12, 6, 6]\n" " 6: Equal(5, 5) [7]\n" " 7: If(6)\n" @@ -467,7 +467,7 @@ TEST(SsaTest, LocalInIf) { " 0: IntConstant 0 [3, 3]\n" " 1: IntConstant 4\n" " 2: Goto\n" - "BasicBlock 1, pred: 0, succ: 2, 5\n" + "BasicBlock 1, pred: 0, succ: 5, 2\n" " 3: Equal(0, 0) [4]\n" " 4: If(3)\n" "BasicBlock 2, pred: 1, succ: 3\n" @@ -489,4 +489,43 @@ TEST(SsaTest, LocalInIf) { TestCode(data, expected); } +TEST(SsaTest, MultiplePredecessors) { + // Test that we do not create a phi when one predecessor + // does not update the local. + const char* expected = + "BasicBlock 0, succ: 1\n" + " 0: IntConstant 0 [4, 8, 6, 6, 2, 2, 8, 4]\n" + " 1: Goto\n" + "BasicBlock 1, pred: 0, succ: 3, 2\n" + " 2: Equal(0, 0) [3]\n" + " 3: If(2)\n" + "BasicBlock 2, pred: 1, succ: 5\n" + " 4: Add(0, 0)\n" + " 5: Goto\n" + "BasicBlock 3, pred: 1, succ: 7, 4\n" + " 6: Equal(0, 0) [7]\n" + " 7: If(6)\n" + "BasicBlock 4, pred: 3, succ: 5\n" + " 8: Add(0, 0)\n" + " 9: Goto\n" + // This block should not get a phi for local 1. + "BasicBlock 5, pred: 2, 4, 7, succ: 6\n" + " 10: ReturnVoid\n" + "BasicBlock 6, pred: 5\n" + " 11: Exit\n" + "BasicBlock 7, pred: 3, succ: 5\n" + " 12: Goto\n"; + + const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 5, + Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8, + Instruction::GOTO | 0x0500, + Instruction::IF_EQ, 4, + Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8, + Instruction::RETURN_VOID); + + TestCode(data, expected); +} + } // namespace art |