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
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
new file mode 100644
index 0000000..ad9ed0c
--- /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 <string>
+#include <map>
+#include <sstream>
+
+namespace art {
+
+void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
+ current_block_ = block;
+
+ // Check consistency with respect to predecessors of `block`.
+ const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors();
+ std::map<HBasicBlock*, size_t> 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<HBasicBlock*>& 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<HBasicBlock*>& successors = block->GetSuccessors();
+ std::map<HBasicBlock*, size_t> 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<HBasicBlock*>& 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 0000000..8ddd399
--- /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<std::string>& GetErrors() const {
+ return errors_;
+ }
+
+ protected:
+ ArenaAllocator* const allocator_;
+ // The block currently visited.
+ HBasicBlock* current_block_ = nullptr;
+ // Errors encountered while checking the graph.
+ GrowableArray<std::string> 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 0000000..ea06920
--- /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 207c605..7b5a78e 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -307,6 +307,14 @@
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 @@
}
}
+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<HInstruction> it(GetUses()); !it.Done(); it.Advance()) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index d6dfeae..eebd64b 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -56,6 +56,12 @@
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 @@
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 @@
#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 <typename T>
class HUseListNode : public ArenaObject {
@@ -582,6 +593,10 @@
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 @@
}
#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 @@
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 c409529..1b930ec 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 @@
}
}
+// 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<const DexFile::CodeItem*>(data);
+ HGraph* graph = builder.BuildGraph(*item);
+ return graph;
+}
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_