[phc-internals] [phc commit] r1464 - branches/dataflow/src/optimize

[codesite-noreply at google.com]

Author: paul.biggar
Date: Thu Jul 24 04:13:37 2008
New Revision: 1464

Modified:
   branches/dataflow/src/optimize/Backwards_flow_visitor.cpp
   branches/dataflow/src/optimize/Backwards_flow_visitor.h
   branches/dataflow/src/optimize/Basic_block.h
   branches/dataflow/src/optimize/Live_variable_analysis.cpp
   branches/dataflow/src/optimize/Live_variable_analysis.h

Log:
More progress on dataflow. This does a good bit of the 
live-variable-analysis. We still need to add the transfer equations, 
add dead-code-elimination, make it sound (add address-taken alias 
analysis), and generalize the solution.


Modified: branches/dataflow/src/optimize/Backwards_flow_visitor.cpp
==============================================================================
--- branches/dataflow/src/optimize/Backwards_flow_visitor.cpp	(original)
+++ branches/dataflow/src/optimize/Backwards_flow_visitor.cpp	Thu Jul 
24 04:13:37 2008
@@ -83,3 +83,116 @@
 		}
 	}
 }
+
+void
+Backwards_flow_visitor::process_entry (Entry_block*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_empty (Empty_block*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_exit (Exit_block*)
+{
+	assert (0);
+}
+void
+Backwards_flow_visitor::process_branch (Branch_block*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_assign_array (Statement_block* sb, MIR::Assign_array*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_assign_target (Statement_block* sb, MIR::Assign_target*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_assign_var (Statement_block* sb, MIR::Assign_var*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_assign_var_var (Statement_block* sb, MIR::Assign_var_var*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_eval_expr (Statement_block* sb, MIR::Eval_expr*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_foreach_end (Statement_block* sb, MIR::Foreach_end*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_foreach_next (Statement_block* sb, MIR::Foreach_next*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_foreach_reset (Statement_block* sb, MIR::Foreach_reset*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_global (Statement_block* sb, MIR::Global*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_pre_op (Statement_block* sb, MIR::Pre_op*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_push_array (Statement_block* sb, MIR::Push_array*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_return (Statement_block* sb, MIR::Return*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_static_declaration (Statement_block* 
sb, MIR::Static_declaration*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_throw (Statement_block* sb, MIR::Throw*)
+{
+	assert (0);
+}
+
+void
+Backwards_flow_visitor::process_try (Statement_block* sb, MIR::Try*)
+{
+	assert (0);
+}

Modified: branches/dataflow/src/optimize/Backwards_flow_visitor.h
==============================================================================
--- branches/dataflow/src/optimize/Backwards_flow_visitor.h	(original)
+++ branches/dataflow/src/optimize/Backwards_flow_visitor.h	Thu Jul 24 
04:13:37 2008
@@ -10,25 +10,25 @@
 	void run (CFG* cfg);
 	void process_bb (Basic_block* bb);
 public:
-	virtual void process_entry (Entry_block*) = 0;
-	virtual void process_empty (Empty_block*) = 0;
-	virtual void process_exit (Exit_block*) = 0;
-	virtual void process_branch (Branch_block*) = 0;
-	virtual void process_return (Statement_block* sb, MIR::Return*) = 0;
-	virtual void process_static_declaration (Statement_block* sb, 
MIR::Static_declaration*) = 0;
-	virtual void process_global (Statement_block* sb, MIR::Global*) = 0;
-	virtual void process_try (Statement_block* sb, MIR::Try*) = 0;
-	virtual void process_throw (Statement_block* sb, MIR::Throw*) = 0;
-	virtual void process_foreach_next (Statement_block* sb, 
MIR::Foreach_next*) = 0;
-	virtual void process_foreach_reset (Statement_block* sb, 
MIR::Foreach_reset*) = 0;
-	virtual void process_foreach_end (Statement_block* sb, 
MIR::Foreach_end*) = 0;
-	virtual void process_assign_var (Statement_block* sb, 
MIR::Assign_var*) = 0;
-	virtual void process_assign_var_var (Statement_block* sb, 
MIR::Assign_var_var*) = 0;
-	virtual void process_assign_array (Statement_block* sb, 
MIR::Assign_array*) = 0;
-	virtual void process_push_array (Statement_block* sb, 
MIR::Push_array*) = 0;
-	virtual void process_assign_target (Statement_block* sb, 
MIR::Assign_target*) = 0;
-	virtual void process_eval_expr (Statement_block* sb, MIR::Eval_expr*) 
= 0;
-	virtual void process_pre_op (Statement_block* sb, MIR::Pre_op*) = 0;
+	virtual void process_entry (Entry_block*);
+	virtual void process_empty (Empty_block*);
+	virtual void process_exit (Exit_block*);
+	virtual void process_branch (Branch_block*);
+	virtual void process_return (Statement_block* sb, MIR::Return*);
+	virtual void process_static_declaration (Statement_block* sb, MIR::Static_declaration*);
+	virtual void process_global (Statement_block* sb, MIR::Global*);
+	virtual void process_try (Statement_block* sb, MIR::Try*);
+	virtual void process_throw (Statement_block* sb, MIR::Throw*);
+	virtual void process_foreach_next (Statement_block* sb, MIR::Foreach_next*);
+	virtual void process_foreach_reset (Statement_block* sb, MIR::Foreach_reset*);
+	virtual void process_foreach_end (Statement_block* sb, MIR::Foreach_end*);
+	virtual void process_assign_var (Statement_block* sb, MIR::Assign_var*);
+	virtual void process_assign_var_var (Statement_block* sb, MIR::Assign_var_var*);
+	virtual void process_assign_array (Statement_block* sb, MIR::Assign_array*);
+	virtual void process_push_array (Statement_block* sb, MIR::Push_array*);
+	virtual void process_assign_target (Statement_block* sb, MIR::Assign_target*);
+	virtual void process_eval_expr (Statement_block* sb, MIR::Eval_expr*);
+	virtual void process_pre_op (Statement_block* sb, MIR::Pre_op*);
 };



Modified: branches/dataflow/src/optimize/Basic_block.h
==============================================================================
--- branches/dataflow/src/optimize/Basic_block.h	(original)
+++ branches/dataflow/src/optimize/Basic_block.h	Thu Jul 24 04:13:37 2008
@@ -27,6 +27,10 @@

 	// Dataflow solution
 public:
+	set<string> defs;
+	set<string> uses;
+	set<string> live_in;
+	set<string> live_out;
 	int iteration_count;
 	


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	Thu Jul 
24 04:13:37 2008
@@ -36,83 +36,97 @@
 		CFG* cfg = new CFG ();
 		cfg->add_statements (method->statements);
 		cfg->dump_graphviz ();
+		Backwards_flow_visitor::run (cfg);
 	}
 }

+#define USE(VAR) bb->uses.insert (*VAR->value);
+#define DEF(VAR) bb->defs.insert (*VAR->value);
+
+void use_expr (Basic_block* bb, Expr* in) {}
+
 void
-Live_variable_analysis::process_entry (Entry_block*)
-{
-}
-void
-Live_variable_analysis::process_empty (Empty_block*)
-{
-}
-void
-Live_variable_analysis::process_exit (Exit_block*)
-{
-}
-void
-Live_variable_analysis::process_branch (Branch_block*)
-{
-}
-void
-Live_variable_analysis::process_return (Statement_block* sb, MIR::Return*)
-{
-}
-void
-Live_variable_analysis::process_static_declaration (Statement_block* 
sb, MIR::Static_declaration*)
-{
-}
-void
-Live_variable_analysis::process_global (Statement_block* sb, MIR::Global*)
+Live_variable_analysis::process_branch (Branch_block* bb)
 {
+	USE (bb->branch->variable_name);
 }
+
 void
-Live_variable_analysis::process_try (Statement_block* sb, MIR::Try*)
+Live_variable_analysis::process_assign_array (Statement_block* bb, 
MIR::Assign_array* in)
 {
+	USE (in->lhs); // may be defined, but we conservativly say it won't.
+	USE (in->index);
+	USE (in->rhs); // cant be defined
 }
+
 void
-Live_variable_analysis::process_throw (Statement_block* sb, MIR::Throw*)
+Live_variable_analysis::process_assign_target (Statement_block* bb, 
MIR::Assign_target* in)
 {
+	assert (0); //use_expr (in->target);
+	assert (0); // USE (in->lhs);
+	USE (in->rhs);
 }
+
 void
-Live_variable_analysis::process_foreach_next (Statement_block* sb, MIR::Foreach_next*)
+Live_variable_analysis::process_assign_var (Statement_block* bb, 
MIR::Assign_var* in)
 {
+	DEF (in->lhs);
+	assert (0); //use_expr (bb, in->expr);
 }
+
 void
-Live_variable_analysis::process_foreach_reset (Statement_block* sb, MIR::Foreach_reset*)
+Live_variable_analysis::process_assign_var_var (Statement_block* bb, 
MIR::Assign_var_var* in)
 {
+	// We don't know what variable is assigned, so we conservatively say none.
+	USE (in->rhs);
 }
+
 void
-Live_variable_analysis::process_foreach_end (Statement_block* sb, MIR::Foreach_end*)
+Live_variable_analysis::process_eval_expr (Statement_block* bb, 
MIR::Eval_expr* in)
 {
+	use_expr (bb, in->expr);
 }
+
 void
-Live_variable_analysis::process_assign_var (Statement_block* sb, MIR::Assign_var*)
+Live_variable_analysis::process_foreach_end (Statement_block* bb, 
MIR::Foreach_end* in)
 {
+	USE (in->array);
 }
+
 void
-Live_variable_analysis::process_assign_var_var (Statement_block* sb, MIR::Assign_var_var*)
+Live_variable_analysis::process_foreach_next (Statement_block* bb, 
MIR::Foreach_next* in)
 {
+	USE (in->array);
 }
+
 void
-Live_variable_analysis::process_assign_array (Statement_block* sb, MIR::Assign_array*)
+Live_variable_analysis::process_foreach_reset (Statement_block* bb, 
MIR::Foreach_reset* in)
 {
+	USE (in->array);
 }
+
 void
-Live_variable_analysis::process_push_array (Statement_block* sb, MIR::Push_array*)
+Live_variable_analysis::process_global (Statement_block* bb, 
MIR::Global* in)
 {
+	// TODO This might define the variable in some cases. Is that useful?
 }
+
 void
-Live_variable_analysis::process_assign_target (Statement_block* sb, MIR::Assign_target*)
+Live_variable_analysis::process_pre_op (Statement_block* bb, 
MIR::Pre_op* in)
 {
+	USE (in->variable_name);
+	// Technically, it is also DEF, but it makes no difference.
 }
+
 void
-Live_variable_analysis::process_eval_expr (Statement_block* sb, MIR::Eval_expr*)
+Live_variable_analysis::process_push_array (Statement_block* bb, 
MIR::Push_array* in)
 {
+	USE (in->lhs);
+	USE (in->rhs);
 }
+
 void
-Live_variable_analysis::process_pre_op (Statement_block* sb, MIR::Pre_op*)
+Live_variable_analysis::process_return (Statement_block* bb, 
MIR::Return* in)
 {
+	use_expr (bb, in->expr);
 }
-

Modified: branches/dataflow/src/optimize/Live_variable_analysis.h
==============================================================================
--- branches/dataflow/src/optimize/Live_variable_analysis.h	(original)
+++ branches/dataflow/src/optimize/Live_variable_analysis.h	Thu Jul 24 
04:13:37 2008
@@ -18,25 +18,22 @@
 	bool pass_is_enabled (Pass_manager* pm);
 	void run (IR::PHP_script* ir_script, Pass_manager* pm);
 public:
-	void process_entry (Entry_block*);
-	void process_empty (Empty_block*);
-	void process_exit (Exit_block*);
+	void process_entry (Entry_block*) {}
+	void process_empty (Empty_block*) {}
+	void process_exit (Exit_block*) {}
 	void process_branch (Branch_block*);
-	void process_return (Statement_block* sb, MIR::Return*);
-	void process_static_declaration (Statement_block* sb, MIR::Static_declaration*);
-	void process_global (Statement_block* sb, MIR::Global*);
-	void process_try (Statement_block* sb, MIR::Try*);
-	void process_throw (Statement_block* sb, MIR::Throw*);
-	void process_foreach_next (Statement_block* sb, MIR::Foreach_next*);
-	void process_foreach_reset (Statement_block* sb, MIR::Foreach_reset*);
-	void process_foreach_end (Statement_block* sb, MIR::Foreach_end*);
-	void process_assign_var (Statement_block* sb, MIR::Assign_var*);
-	void process_assign_var_var (Statement_block* sb, MIR::Assign_var_var*);
 	void process_assign_array (Statement_block* sb, MIR::Assign_array*);
-	void process_push_array (Statement_block* sb, MIR::Push_array*);
 	void process_assign_target (Statement_block* sb, MIR::Assign_target*);
+	void process_assign_var (Statement_block* sb, MIR::Assign_var*);
+	void process_assign_var_var (Statement_block* sb, MIR::Assign_var_var*);
 	void process_eval_expr (Statement_block* sb, MIR::Eval_expr*);
+	void process_foreach_end (Statement_block* sb, MIR::Foreach_end*);
+	void process_foreach_next (Statement_block* sb, MIR::Foreach_next*);
+	void process_foreach_reset (Statement_block* sb, MIR::Foreach_reset*);
+	void process_global (Statement_block* sb, MIR::Global*);
 	void process_pre_op (Statement_block* sb, MIR::Pre_op*);
+	void process_push_array (Statement_block* sb, MIR::Push_array*);
+	void process_return (Statement_block* sb, MIR::Return*);
 };

 #endif // LIVE_VARIABLE_ANALYSIS