[phc-internals] [phc commit] r1483 - in branches/dataflow/src: optimize process_ir

[codesite-noreply at google.com]

Author: paul.biggar
Date: Tue Jul 29 08:14:04 2008
New Revision: 1483

Modified:
   branches/dataflow/src/optimize/CFG.cpp
   branches/dataflow/src/optimize/CFG.h
   branches/dataflow/src/optimize/Live_variable_analysis.cpp
   branches/dataflow/src/process_ir/fresh.cpp
   branches/dataflow/src/process_ir/fresh.h

Log:
Convert the CFG back into linear statements. It uses the same 
alghorithm as on the saturn branch: we do a depth-first-search over the 
CFG, and return a label, a statement and a goto to the next statement. 
After the traversal, redundant gotos are removed, followed by unused labels.

This hasn't been heavily tested, but its the final step required to 
test the whole lot.


Modified: branches/dataflow/src/optimize/CFG.cpp
==============================================================================
--- branches/dataflow/src/optimize/CFG.cpp	(original)
+++ branches/dataflow/src/optimize/CFG.cpp	Tue Jul 29 08:14:04 2008
@@ -7,6 +7,8 @@

 #include "boost/foreach.hpp"
 #include "boost/graph/graphviz.hpp"
+#include "boost/graph/depth_first_search.hpp"
+#include "boost/graph/visitors.hpp"

 #include "CFG.h"
 #include "process_ast/DOT_unparser.h"
@@ -345,3 +347,114 @@
 		remove_bb (bb);
 	}
 }
+
+// Do a depth first search. For each block, add a label, and a goto to 
the next
+// block(s).
+class Linearizer : public default_dfs_visitor
+{
+public:
+	List<Statement*>* statements;
+	map<vertex_t, LABEL_NAME*> labels;
+	Linearizer()
+	{
+		statements = new List<Statement*>;
+	}
+
+	/* Assign a label for each block. */
+	void initialize_vertex (vertex_t v, const Graph& g)
+	{
+		labels [v] = fresh_label_name ();
+	}
+
+	/* Return a Goto to the next statement. */
+	Goto* get_goto_next (Basic_block* bb, const Graph& g)
+	{
+		vertex_t v = bb->vertex;
+		assert (out_degree (v, g) == 1);
+		vertex_t t = target (*out_edges (v, g).first, g);
+		return new Goto (labels[t]);
+	}
+
+	void discover_vertex (vertex_t v, const Graph& g)
+	{
+		Basic_block* bb = get(vertex_bb_t(), g)[v];
+
+		if (Statement_block* sb = dynamic_cast<Statement_block*> (bb))
+		{
+			statements->push_back (new Label(labels[v]->clone ()));
+			statements->push_back (sb->statement);
+			statements->push_back (get_goto_next (bb, g));
+		}
+
+		else if (dynamic_cast<Entry_block*> (bb))
+			statements->push_back (get_goto_next (bb, g));
+
+		else if (dynamic_cast<Exit_block*> (bb))
+			statements->push_back (new Label(labels[v]->clone ()));
+
+		else if (dynamic_cast<Empty_block*> (bb))
+		{
+			statements->push_back (new Label(labels[v]->clone ()));
+			statements->push_back (get_goto_next (bb, g));
+		}
+		else
+			assert (0); // TODO branches
+	}
+};
+
+class Label_counter : public Visitor
+{
+	map<string, int>* counts;
+public:
+	Label_counter (map<string, int>* c) : counts(c) {}
+
+	void pre_label_name (LABEL_NAME* in)
+	{
+		(*counts)[*in->value]++;
+	}
+};
+
+List<Statement*>*
+CFG::get_linear_statements ()
+{
+	Linearizer linearizer;
+	depth_first_search (bs, visitor (linearizer));
+	List<Statement*>* results = linearizer.statements;
+
+	/* Remove redundant gotos, which would fall-through to their targets
+	 * anyway. */
+	List<Statement*>::iterator i = results->begin ();
+	while (i != results->end ())
+	{
+		Wildcard<LABEL_NAME>* ln = new Wildcard<LABEL_NAME>;
+		Statement* s = *i;
+		Statement* next = *(++i);
+		if (s->match (new Goto (ln))
+			&& next->match (new Label (ln->value)))
+		{
+			i--;
+
+			// Use this form of looping so that the iterator moves to the next
+			// iterm before its invalidated.
+			results->erase (i++);
+		}
+	}
+
+	/* Remove labels that are only used once. */
+	map<string, int> label_counts;
+	(new Label_counter (&label_counts))->visit_statement_list (results);
+
+	i = results->begin ();
+	while (i != results->end ())
+	{
+		Wildcard<LABEL_NAME>* ln = new Wildcard<LABEL_NAME>;
+		if ((*i)->match (new Label (ln))
+			&& label_counts[*ln->value->value] == 1)
+			results->erase (i++);
+		else
+			i++;
+	}
+
+	return results;
+}
+

Modified: branches/dataflow/src/optimize/CFG.h
==============================================================================
--- branches/dataflow/src/optimize/CFG.h	(original)
+++ branches/dataflow/src/optimize/CFG.h	Tue Jul 29 08:14:04 2008
@@ -61,6 +61,7 @@

 	CFG ();
 	void add_statements (List<MIR::Statement*>* statements);
+	List<MIR::Statement*>* get_linear_statements ();

 	// Add the BB to the graph, and update the BB's vertex.
 	vertex_t add_bb (Basic_block* bb);

Modified: branches/dataflow/src/optimize/Live_variable_analysis.cpp
==============================================================================
--- branches/dataflow/src/optimize/Live_variable_analysis.cpp	(original)
+++ branches/dataflow/src/optimize/Live_variable_analysis.cpp	Tue Jul 
29 08:14:04 2008
@@ -42,6 +42,7 @@
 		Dead_code_elimination* dce = new Dead_code_elimination;
 		dce->visit (cfg);
 		cfg->dump_graphviz (s("AFTER DCE"));
+		method->statements = cfg->get_linear_statements ();
 	}
 }


Modified: branches/dataflow/src/process_ir/fresh.cpp
==============================================================================
--- branches/dataflow/src/process_ir/fresh.cpp	(original)
+++ branches/dataflow/src/process_ir/fresh.cpp	Tue Jul 29 08:14:04 2008
@@ -115,9 +115,14 @@

 	Label* fresh_label ()
 	{
+		return new Label (fresh_label_name ());
+	}
+
+	LABEL_NAME* fresh_label_name ()
+	{
 		int suffix = fresh_suffix ();
 		LABEL_NAME* result = new LABEL_NAME (fresh ("L", suffix));
 		result->attrs->set ("phc.fresh.suffix", new Integer (suffix));
-		return new Label (result);
+		return result;
 	}
 }

Modified: branches/dataflow/src/process_ir/fresh.h
==============================================================================
--- branches/dataflow/src/process_ir/fresh.h	(original)
+++ branches/dataflow/src/process_ir/fresh.h	Tue Jul 29 08:14:04 2008
@@ -31,6 +31,7 @@
 {
 	MIR::VARIABLE_NAME* fresh_var_name (string prefix);
 	MIR::Label* fresh_label ();
+	LABEL_NAME* fresh_label_name ();
 	MIR::HT_ITERATOR* fresh_iter ();
 }