Implement default traversals in CFG & SSA graph checkers.
- Check CFG graphs using an insertion order traversal.
- Check SSA form graphs using a reverse post-order traversal.
Change-Id: Ib9062599bdbf3c17b9f213b743274b2d71a9fa90
diff --git a/compiler/optimizing/constant_propagation_test.cc b/compiler/optimizing/constant_propagation_test.cc
index 342777a..ff44805 100644
--- a/compiler/optimizing/constant_propagation_test.cc
+++ b/compiler/optimizing/constant_propagation_test.cc
@@ -62,7 +62,7 @@
ASSERT_EQ(expected_after_dce, actual_after_dce);
SSAChecker ssa_checker(&allocator, graph);
- ssa_checker.VisitInsertionOrder();
+ ssa_checker.Run();
ASSERT_TRUE(ssa_checker.IsValid());
}
diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc
index 245bcb2..3e0ba3a 100644
--- a/compiler/optimizing/dead_code_elimination_test.cc
+++ b/compiler/optimizing/dead_code_elimination_test.cc
@@ -47,7 +47,7 @@
ASSERT_EQ(actual_after, expected_after);
SSAChecker ssa_checker(&allocator, graph);
- ssa_checker.VisitInsertionOrder();
+ ssa_checker.Run();
ASSERT_TRUE(ssa_checker.IsValid());
}
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 34a770b..862f1b6 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -29,6 +29,9 @@
allocator_(allocator),
errors_(allocator, 0) {}
+ // Check the whole graph (in insertion order).
+ virtual void Run() { VisitInsertionOrder(); }
+
// Check `block`.
virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
@@ -65,6 +68,14 @@
SSAChecker(ArenaAllocator* allocator, HGraph* graph)
: GraphChecker(allocator, graph) {}
+ // Check the whole graph (in reverse post-order).
+ virtual void Run() {
+ // VisitReversePostOrder is used instead of VisitInsertionOrder,
+ // as the latter might visit dead blocks removed by the dominator
+ // computation.
+ VisitReversePostOrder();
+ }
+
// Perform SSA form checks on `block`.
virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
// Loop-related checks from block `loop_header`.
diff --git a/compiler/optimizing/graph_checker_test.cc b/compiler/optimizing/graph_checker_test.cc
index ea06920..39def82 100644
--- a/compiler/optimizing/graph_checker_test.cc
+++ b/compiler/optimizing/graph_checker_test.cc
@@ -51,7 +51,7 @@
ASSERT_NE(graph, nullptr);
GraphChecker graph_checker(&allocator, graph);
- graph_checker.VisitInsertionOrder();
+ graph_checker.Run();
ASSERT_TRUE(graph_checker.IsValid());
}
@@ -65,7 +65,7 @@
graph->TransformToSSA();
SSAChecker ssa_checker(&allocator, graph);
- ssa_checker.VisitInsertionOrder();
+ ssa_checker.Run();
ASSERT_TRUE(ssa_checker.IsValid());
}
@@ -113,13 +113,13 @@
HGraph* graph = CreateSimpleCFG(&allocator);
GraphChecker graph_checker(&allocator, graph);
- graph_checker.VisitInsertionOrder();
+ graph_checker.Run();
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();
+ graph_checker.Run();
ASSERT_FALSE(graph_checker.IsValid());
}
@@ -131,7 +131,7 @@
HGraph* graph = CreateSimpleCFG(&allocator);
GraphChecker graph_checker(&allocator, graph);
- graph_checker.VisitInsertionOrder();
+ graph_checker.Run();
ASSERT_TRUE(graph_checker.IsValid());
// Remove the sole instruction of the exit block (composed of a
@@ -141,7 +141,7 @@
HInstruction* last_inst = exit_block->GetLastInstruction();
exit_block->RemoveInstruction(last_inst);
- graph_checker.VisitInsertionOrder();
+ graph_checker.Run();
ASSERT_FALSE(graph_checker.IsValid());
}
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index a058dea..aee2177 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -553,6 +553,12 @@
}
}
+void HGraphVisitor::VisitReversePostOrder() {
+ for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ VisitBasicBlock(it.Current());
+ }
+}
+
void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
it.Current()->Accept(this);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index c6eb806..e60a7e6 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1961,8 +1961,12 @@
virtual void VisitInstruction(HInstruction* instruction) {}
virtual void VisitBasicBlock(HBasicBlock* block);
+ // Visit the graph following basic block insertion order.
void VisitInsertionOrder();
+ // Visit the graph following dominator tree reverse post-order.
+ void VisitReversePostOrder();
+
HGraph* GetGraph() const { return graph_; }
// Visit functions for instruction classes.