From ccc07a9579c554443cd03a306ca9b4f943fd2a93 Mon Sep 17 00:00:00 2001 From: Roland Levillain Date: Tue, 16 Sep 2014 14:48:16 +0100 Subject: [PATCH] Add CFG and SSA form checkers in the optimizing compiler. Checks performed on control-flow graphs: - Ensure that the predecessors and successors of a basic block are consistent within a control-flow graph. - Ensure basic blocks end with a branch instruction. - Detect phi functions listed in non-phi instruction lists and vice versa. - Ensure a block's instructions (and phi functions) are associated with this very block. Checks performed on SSA form graphs: - Ensure an instruction dominates all its uses. - Ensure there are no critical edges. Change-Id: I1c12b4a61ecf608682152c897980ababa7eca847 --- build/Android.gtest.mk | 1 + compiler/Android.mk | 1 + compiler/optimizing/graph_checker.cc | 183 +++++++++++++++++++++++++++++ compiler/optimizing/graph_checker.h | 80 +++++++++++++ compiler/optimizing/graph_checker_test.cc | 159 +++++++++++++++++++++++++ compiler/optimizing/nodes.cc | 56 +++++++++ compiler/optimizing/nodes.h | 36 ++++-- compiler/optimizing/optimizing_unit_test.h | 13 ++ 8 files changed, 520 insertions(+), 9 deletions(-) create mode 100644 compiler/optimizing/graph_checker.cc create mode 100644 compiler/optimizing/graph_checker.h create mode 100644 compiler/optimizing/graph_checker_test.cc diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk index 4ecda918e..e2ba86747 100644 --- a/build/Android.gtest.mk +++ b/build/Android.gtest.mk @@ -142,6 +142,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_checker_test.cc \ compiler/optimizing/graph_test.cc \ compiler/optimizing/linearize_test.cc \ compiler/optimizing/liveness_test.cc \ diff --git a/compiler/Android.mk b/compiler/Android.mk index 6e48bdf2e..f76b66aec 100644 --- a/compiler/Android.mk +++ b/compiler/Android.mk @@ -90,6 +90,7 @@ LIBART_COMPILER_SRC_FILES := \ optimizing/code_generator_arm.cc \ optimizing/code_generator_x86.cc \ optimizing/code_generator_x86_64.cc \ + optimizing/graph_checker.cc \ optimizing/graph_visualizer.cc \ optimizing/locations.cc \ optimizing/nodes.cc \ diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc new file mode 100644 index 000000000..ad9ed0c1c --- /dev/null +++ b/compiler/optimizing/graph_checker.cc @@ -0,0 +1,183 @@ +/* + * 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 "graph_checker.h" + +#include +#include +#include + +namespace art { + +void GraphChecker::VisitBasicBlock(HBasicBlock* block) { + current_block_ = block; + + // Check consistency with respect to predecessors of `block`. + const GrowableArray& predecessors = block->GetPredecessors(); + std::map predecessors_count; + for (size_t i = 0, e = predecessors.Size(); i < e; ++i) { + HBasicBlock* p = predecessors.Get(i); + ++predecessors_count[p]; + } + for (auto& pc : predecessors_count) { + HBasicBlock* p = pc.first; + size_t p_count_in_block_predecessors = pc.second; + const GrowableArray& p_successors = p->GetSuccessors(); + size_t block_count_in_p_successors = 0; + for (size_t j = 0, f = p_successors.Size(); j < f; ++j) { + if (p_successors.Get(j) == block) { + ++block_count_in_p_successors; + } + } + if (p_count_in_block_predecessors != block_count_in_p_successors) { + std::stringstream error; + error << "Block " << block->GetBlockId() + << " lists " << p_count_in_block_predecessors + << " occurrences of block " << p->GetBlockId() + << " in its predecessors, whereas block " << p->GetBlockId() + << " lists " << block_count_in_p_successors + << " occurrences of block " << block->GetBlockId() + << " in its successors."; + errors_.Insert(error.str()); + } + } + + // Check consistency with respect to successors of `block`. + const GrowableArray& successors = block->GetSuccessors(); + std::map successors_count; + for (size_t i = 0, e = successors.Size(); i < e; ++i) { + HBasicBlock* s = successors.Get(i); + ++successors_count[s]; + } + for (auto& sc : successors_count) { + HBasicBlock* s = sc.first; + size_t s_count_in_block_successors = sc.second; + const GrowableArray& s_predecessors = s->GetPredecessors(); + size_t block_count_in_s_predecessors = 0; + for (size_t j = 0, f = s_predecessors.Size(); j < f; ++j) { + if (s_predecessors.Get(j) == block) { + ++block_count_in_s_predecessors; + } + } + if (s_count_in_block_successors != block_count_in_s_predecessors) { + std::stringstream error; + error << "Block " << block->GetBlockId() + << " lists " << s_count_in_block_successors + << " occurrences of block " << s->GetBlockId() + << " in its successors, whereas block " << s->GetBlockId() + << " lists " << block_count_in_s_predecessors + << " occurrences of block " << block->GetBlockId() + << " in its predecessors."; + errors_.Insert(error.str()); + } + } + + // Ensure `block` ends with a branch instruction. + HInstruction* last_inst = block->GetLastInstruction(); + if (last_inst == nullptr || !last_inst->IsControlFlow()) { + std::stringstream error; + error << "Block " << block->GetBlockId() + << " does not end with a branch instruction."; + errors_.Insert(error.str()); + } + + // Visit this block's list of phis. + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + // Ensure this block's list of phis contains only phis. + if (!it.Current()->IsPhi()) { + std::stringstream error; + error << "Block " << current_block_->GetBlockId() + << " has a non-phi in its phi list."; + errors_.Insert(error.str()); + } + it.Current()->Accept(this); + } + + // Visit this block's list of instructions. + for (HInstructionIterator it(block->GetInstructions()); !it.Done(); + it.Advance()) { + // Ensure this block's list of instructions does not contains phis. + if (it.Current()->IsPhi()) { + std::stringstream error; + error << "Block " << current_block_->GetBlockId() + << " has a phi in its non-phi list."; + errors_.Insert(error.str()); + } + it.Current()->Accept(this); + } +} + +void GraphChecker::VisitInstruction(HInstruction* instruction) { + // Ensure `instruction` is associated with `current_block_`. + if (instruction->GetBlock() != current_block_) { + std::stringstream error; + if (instruction->IsPhi()) { + error << "Phi "; + } else { + error << "Instruction "; + } + error << instruction->GetId() << " in block " + << current_block_->GetBlockId(); + if (instruction->GetBlock() != nullptr) { + error << " associated with block " + << instruction->GetBlock()->GetBlockId() << "."; + } else { + error << " not associated with any block."; + } + errors_.Insert(error.str()); + } +} + +void SSAChecker::VisitBasicBlock(HBasicBlock* block) { + super_type::VisitBasicBlock(block); + + // Ensure there is no critical edge (i.e., an edge connecting a + // block with multiple successors to a block with multiple + // predecessors). + if (block->GetSuccessors().Size() > 1) { + for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { + HBasicBlock* successor = block->GetSuccessors().Get(j); + if (successor->GetPredecessors().Size() > 1) { + std::stringstream error; + error << "Critical edge between blocks " << block->GetBlockId() + << " and " << successor->GetBlockId() << "."; + errors_.Insert(error.str()); + } + } + } +} + +void SSAChecker::VisitInstruction(HInstruction* instruction) { + super_type::VisitInstruction(instruction); + + // Ensure an instruction dominates all its uses (or in the present + // case, that all uses of an instruction (used as input) are + // dominated by its definition). + for (HInputIterator input_it(instruction); !input_it.Done(); + input_it.Advance()) { + HInstruction* input = input_it.Current(); + if (!input->Dominates(instruction)) { + std::stringstream error; + error << "Instruction " << input->GetId() + << " in block " << input->GetBlock()->GetBlockId() + << " does not dominate use " << instruction->GetId() + << " in block " << current_block_->GetBlockId() << "."; + errors_.Insert(error.str()); + } + } +} + +} // namespace art diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h new file mode 100644 index 000000000..8ddd39945 --- /dev/null +++ b/compiler/optimizing/graph_checker.h @@ -0,0 +1,80 @@ +/* + * 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. + */ + +#ifndef ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_ +#define ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_ + +#include "nodes.h" + +namespace art { + +// A control-flow graph visitor performing various checks. +class GraphChecker : public HGraphVisitor { + public: + GraphChecker(ArenaAllocator* allocator, HGraph* graph) + : HGraphVisitor(graph), + allocator_(allocator), + errors_(allocator, 0) {} + + // Check `block`. + virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE; + + // Check `instruction`. + virtual void VisitInstruction(HInstruction* instruction) OVERRIDE; + + // Was the last visit of the graph valid? + bool IsValid() const { + return errors_.IsEmpty(); + } + + // Get the list of detected errors. + const GrowableArray& GetErrors() const { + return errors_; + } + + protected: + ArenaAllocator* const allocator_; + // The block currently visited. + HBasicBlock* current_block_ = nullptr; + // Errors encountered while checking the graph. + GrowableArray errors_; + + private: + DISALLOW_COPY_AND_ASSIGN(GraphChecker); +}; + + +// An SSA graph visitor performing various checks. +class SSAChecker : public GraphChecker { + public: + typedef GraphChecker super_type; + + SSAChecker(ArenaAllocator* allocator, HGraph* graph) + : GraphChecker(allocator, graph) {} + + // Perform SSA form checks on `block`. + virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE; + + // Perform SSA form checks on `instruction`. + virtual void VisitInstruction(HInstruction* instruction) OVERRIDE; + + private: + DISALLOW_COPY_AND_ASSIGN(SSAChecker); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_ diff --git a/compiler/optimizing/graph_checker_test.cc b/compiler/optimizing/graph_checker_test.cc new file mode 100644 index 000000000..ea0692088 --- /dev/null +++ b/compiler/optimizing/graph_checker_test.cc @@ -0,0 +1,159 @@ +/* + * 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 "graph_checker.h" +#include "optimizing_unit_test.h" + +#include "gtest/gtest.h" + +namespace art { + +/** + * Create a simple control-flow graph composed of two blocks: + * + * BasicBlock 0, succ: 1 + * 0: Goto 1 + * BasicBlock 1, pred: 0 + * 1: Exit + */ +HGraph* CreateSimpleCFG(ArenaAllocator* allocator) { + HGraph* graph = new (allocator) HGraph(allocator); + HBasicBlock* entry_block = new (allocator) HBasicBlock(graph); + entry_block->AddInstruction(new (allocator) HGoto()); + graph->AddBlock(entry_block); + graph->SetEntryBlock(entry_block); + HBasicBlock* exit_block = new (allocator) HBasicBlock(graph); + exit_block->AddInstruction(new (allocator) HExit()); + graph->AddBlock(exit_block); + graph->SetExitBlock(exit_block); + entry_block->AddSuccessor(exit_block); + return graph; +} + + +static void TestCode(const uint16_t* data) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + HGraph* graph = CreateCFG(&allocator, data); + ASSERT_NE(graph, nullptr); + + GraphChecker graph_checker(&allocator, graph); + graph_checker.VisitInsertionOrder(); + ASSERT_TRUE(graph_checker.IsValid()); +} + +static void TestCodeSSA(const uint16_t* data) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + HGraph* graph = CreateCFG(&allocator, data); + ASSERT_NE(graph, nullptr); + + graph->BuildDominatorTree(); + graph->TransformToSSA(); + + SSAChecker ssa_checker(&allocator, graph); + ssa_checker.VisitInsertionOrder(); + ASSERT_TRUE(ssa_checker.IsValid()); +} + + +TEST(GraphChecker, ReturnVoid) { + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( + Instruction::RETURN_VOID); + + TestCode(data); +} + +TEST(GraphChecker, CFG1) { + const uint16_t data[] = ZERO_REGISTER_CODE_ITEM( + Instruction::GOTO | 0x100, + Instruction::RETURN_VOID); + + TestCode(data); +} + +TEST(GraphChecker, CFG2) { + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 3, + Instruction::GOTO | 0x100, + Instruction::RETURN_VOID); + + TestCode(data); +} + +TEST(GraphChecker, CFG3) { + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 3, + Instruction::GOTO | 0x100, + Instruction::GOTO | 0xFF00); + + TestCode(data); +} + +// Test case with an invalid graph containing inconsistent +// predecessor/successor arcs in CFG. +TEST(GraphChecker, InconsistentPredecessorsAndSuccessors) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = CreateSimpleCFG(&allocator); + GraphChecker graph_checker(&allocator, graph); + graph_checker.VisitInsertionOrder(); + ASSERT_TRUE(graph_checker.IsValid()); + + // Remove the entry block from the exit block's predecessors, to create an + // inconsistent successor/predecessor relation. + graph->GetExitBlock()->RemovePredecessor(graph->GetEntryBlock()); + graph_checker.VisitInsertionOrder(); + ASSERT_FALSE(graph_checker.IsValid()); +} + +// Test case with an invalid graph containing a non-branch last +// instruction in a block. +TEST(GraphChecker, BlockEndingWithNonBranchInstruction) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = CreateSimpleCFG(&allocator); + GraphChecker graph_checker(&allocator, graph); + graph_checker.VisitInsertionOrder(); + ASSERT_TRUE(graph_checker.IsValid()); + + // Remove the sole instruction of the exit block (composed of a + // single Exit instruction) to make it invalid (i.e. not ending by a + // branch instruction). + HBasicBlock* exit_block = graph->GetExitBlock(); + HInstruction* last_inst = exit_block->GetLastInstruction(); + exit_block->RemoveInstruction(last_inst); + + graph_checker.VisitInsertionOrder(); + ASSERT_FALSE(graph_checker.IsValid()); +} + +TEST(SSAChecker, SSAPhi) { + // This code creates one Phi function during the conversion to SSA form. + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 3, + Instruction::CONST_4 | 4 << 12 | 0, + Instruction::RETURN | 0 << 8); + + TestCodeSSA(data); +} + +} // namespace art diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 207c605dd..7b5a78eb3 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -307,6 +307,14 @@ void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstructio instruction->SetId(GetGraph()->GetNextInstructionId()); } +void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, + HInstruction* replacement) { + DCHECK(initial->GetBlock() == this); + InsertInstructionBefore(replacement, initial); + initial->ReplaceWith(replacement); + RemoveInstruction(initial); +} + static void Add(HInstructionList* instruction_list, HBasicBlock* block, HInstruction* instruction) { @@ -392,6 +400,54 @@ void HInstructionList::RemoveInstruction(HInstruction* instruction) { } } +bool HInstructionList::FoundBefore(const HInstruction* instruction1, + const HInstruction* instruction2) const { + DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock()); + for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { + if (it.Current() == instruction1) { + return true; + } + if (it.Current() == instruction2) { + return false; + } + } + LOG(FATAL) << "Did not find an order between two instructions of the same block."; + return true; +} + +bool HInstruction::Dominates(HInstruction* other_instruction) const { + HBasicBlock* block = GetBlock(); + HBasicBlock* other_block = other_instruction->GetBlock(); + if (block != other_block) { + return GetBlock()->Dominates(other_instruction->GetBlock()); + } else { + // If both instructions are in the same block, ensure this + // instruction comes before `other_instruction`. + if (IsPhi()) { + if (!other_instruction->IsPhi()) { + // Phis appear before non phi-instructions so this instruction + // dominates `other_instruction`. + return true; + } else { + // There is no order among phis. + LOG(FATAL) << "There is no dominance between phis of a same block."; + return false; + } + } else { + // `this` is not a phi. + if (other_instruction->IsPhi()) { + // Phis appear before non phi-instructions so this instruction + // does not dominate `other_instruction`. + return false; + } else { + // Check whether this instruction comes before + // `other_instruction` in the instruction list. + return block->GetInstructions().FoundBefore(this, other_instruction); + } + } + } +} + void HInstruction::ReplaceWith(HInstruction* other) { DCHECK(other != nullptr); for (HUseIterator it(GetUses()); !it.Done(); it.Advance()) { diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index d6dfeaede..eebd64bbf 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -56,6 +56,12 @@ class HInstructionList { void AddInstruction(HInstruction* instruction); void RemoveInstruction(HInstruction* instruction); + // Return true if `instruction1` is found before `instruction2` in + // this instruction list and false otherwise. Abort if none + // of these instructions is found. + bool FoundBefore(const HInstruction* instruction1, + const HInstruction* instruction2) const; + private: HInstruction* first_instruction_; HInstruction* last_instruction_; @@ -352,6 +358,9 @@ class HBasicBlock : public ArenaObject { void AddInstruction(HInstruction* instruction); void RemoveInstruction(HInstruction* instruction); void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); + // Replace instruction `initial` with `replacement` within this block. + void ReplaceAndRemoveInstructionWith(HInstruction* initial, + HInstruction* replacement); void AddPhi(HPhi* phi); void RemovePhi(HPhi* phi); @@ -448,19 +457,21 @@ class HBasicBlock : public ArenaObject { #define FOR_EACH_INSTRUCTION(M) \ FOR_EACH_CONCRETE_INSTRUCTION(M) \ - M(Constant) + M(Constant) \ + M(BinaryOperation) #define FORWARD_DECLARATION(type) class H##type; FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) #undef FORWARD_DECLARATION -#define DECLARE_INSTRUCTION(type) \ - virtual const char* DebugName() const { return #type; } \ - virtual H##type* As##type() { return this; } \ - virtual bool InstructionTypeEquals(HInstruction* other) const { \ - return other->Is##type(); \ - } \ - virtual void Accept(HGraphVisitor* visitor) \ +#define DECLARE_INSTRUCTION(type) \ + virtual const char* DebugName() const { return #type; } \ + virtual const H##type* As##type() const OVERRIDE { return this; } \ + virtual H##type* As##type() OVERRIDE { return this; } \ + virtual bool InstructionTypeEquals(HInstruction* other) const { \ + return other->Is##type(); \ + } \ + virtual void Accept(HGraphVisitor* visitor) template class HUseListNode : public ArenaObject { @@ -582,6 +593,10 @@ class HInstruction : public ArenaObject { return result; } + // Does this instruction dominate `other_instruction`? Aborts if + // this instruction and `other_instruction` are both phis. + bool Dominates(HInstruction* other_instruction) const; + int GetId() const { return id_; } void SetId(int id) { id_ = id; } @@ -607,7 +622,8 @@ class HInstruction : public ArenaObject { } #define INSTRUCTION_TYPE_CHECK(type) \ - bool Is##type() { return (As##type() != nullptr); } \ + bool Is##type() const { return (As##type() != nullptr); } \ + virtual const H##type* As##type() const { return nullptr; } \ virtual H##type* As##type() { return nullptr; } FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) @@ -984,6 +1000,8 @@ class HBinaryOperation : public HExpression<2> { virtual bool CanBeMoved() const { return true; } virtual bool InstructionDataEquals(HInstruction* other) const { return true; } + DECLARE_INSTRUCTION(BinaryOperation); + private: DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); }; diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h index c40952972..1b930ec3d 100644 --- a/compiler/optimizing/optimizing_unit_test.h +++ b/compiler/optimizing/optimizing_unit_test.h @@ -17,6 +17,10 @@ #ifndef ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_ #define ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_ +#include "nodes.h" +#include "builder.h" +#include "dex_file.h" +#include "dex_instruction.h" #include "ssa_liveness_analysis.h" namespace art { @@ -61,6 +65,15 @@ void RemoveSuspendChecks(HGraph* graph) { } } +// Create a control-flow graph from Dex instructions. +inline HGraph* CreateCFG(ArenaAllocator* allocator, const uint16_t* data) { + HGraphBuilder builder(allocator); + const DexFile::CodeItem* item = + reinterpret_cast(data); + HGraph* graph = builder.BuildGraph(*item); + return graph; +} + } // namespace art #endif // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_ -- 2.11.0