[phc-internals] [phc commit] r1661 - in branches/dataflow/src: embed optimize

codesite-noreply at google.com codesite-noreply at google.com
Wed Sep 17 17:06:11 IST 2008


Author: paul.biggar
Date: Wed Sep 17 09:05:14 2008
New Revision: 1661

Modified:
    branches/dataflow/src/embed/embed.h
    branches/dataflow/src/embed/optimize.cpp
    branches/dataflow/src/optimize/Basic_block.cpp
    branches/dataflow/src/optimize/Basic_block.h
    branches/dataflow/src/optimize/CFG.cpp
    branches/dataflow/src/optimize/CFG.h
    branches/dataflow/src/optimize/Def_use.cpp
    branches/dataflow/src/optimize/Def_use.h
    branches/dataflow/src/optimize/SCCP.cpp
    branches/dataflow/src/optimize/SCCP.h

Log:
Expand Def_use and SCCP more.
Add fold_pre_op.
Fix a bug in building SSA, where if a variable is used twice in a  
statement, only the first gets converted to SSA. This is because I used a  
set, not a list, like I should have.


Modified: branches/dataflow/src/embed/embed.h
==============================================================================
--- branches/dataflow/src/embed/embed.h	(original)
+++ branches/dataflow/src/embed/embed.h	Wed Sep 17 09:05:14 2008
@@ -56,6 +56,7 @@
  	static bool is_true (MIR::Literal* literal);
  	static MIR::Literal* cast_to (MIR::CAST* cast, MIR::Literal* literal);
  	static MIR::Literal* fold_bin_op (MIR::Literal* left, MIR::OP* op,  
MIR::Literal* right);
+	static MIR::Literal* fold_pre_op (MIR::Literal* use, MIR::OP* op);

  	// Functions
  	static bool is_pure_function (MIR::METHOD_NAME* in);

Modified: branches/dataflow/src/embed/optimize.cpp
==============================================================================
--- branches/dataflow/src/embed/optimize.cpp	(original)
+++ branches/dataflow/src/embed/optimize.cpp	Wed Sep 17 09:05:14 2008
@@ -220,7 +220,27 @@
  		return NULL;
  }

+MIR::Literal*
+PHP::fold_pre_op (MIR::Literal* use, MIR::OP* op)
+{
+	stringstream ss;
+	ss << "$temp = ";
+	MIR_unparser (ss, true).unparse (use);
+	ss << "; " << *op->value << "$temp; return $temp;";

+	// Assume this can fail for no good reason (bad types?) and that we must
+	// recover from it.
+	// TODO: warn in this case.
+	zval value;
+	if (eval_string (s(ss.str()), &value))
+	{
+		Literal* result = zval_to_mir_literal (&value);
+		zval_dtor (&value); // clear out string structure
+		return result;
+	}
+	else
+		return NULL;
+}


  #else // HAVE_EMBED

Modified: branches/dataflow/src/optimize/Basic_block.cpp
==============================================================================
--- branches/dataflow/src/optimize/Basic_block.cpp	(original)
+++ branches/dataflow/src/optimize/Basic_block.cpp	Wed Sep 17 09:05:14 2008
@@ -417,13 +417,13 @@
  	return cfg->dominance->get_blocks_dominated_by_bb (this);
  }

-Set*
+VARIABLE_NAME_list*
  Basic_block::get_pre_ssa_defs ()
  {
  	return cfg->duw->get_bb_defs (this);
  }

-Set*
+VARIABLE_NAME_list*
  Basic_block::get_pre_ssa_uses ()
  {
  	return cfg->duw->get_bb_uses (this);

Modified: branches/dataflow/src/optimize/Basic_block.h
==============================================================================
--- branches/dataflow/src/optimize/Basic_block.h	(original)
+++ branches/dataflow/src/optimize/Basic_block.h	Wed Sep 17 09:05:14 2008
@@ -49,8 +49,8 @@
  	 * TODO: this will probably break for defs.
  	 * These are really for SSA_renaming. We can't use them for a different
  	 * purpose with the same semantics.*/
-	virtual Set* get_pre_ssa_defs ();
-	virtual Set* get_pre_ssa_uses ();
+	virtual MIR::VARIABLE_NAME_list* get_pre_ssa_defs ();
+	virtual MIR::VARIABLE_NAME_list* get_pre_ssa_uses ();

  	/*
  	 * CFG properties

Modified: branches/dataflow/src/optimize/CFG.cpp
==============================================================================
--- branches/dataflow/src/optimize/CFG.cpp	(original)
+++ branches/dataflow/src/optimize/CFG.cpp	Wed Sep 17 09:05:14 2008
@@ -163,16 +163,16 @@
  	consistency_check ();
  }

-Basic_block*
+Entry_block*
  CFG::get_entry_bb ()
  {
-	return vb[entry];
+	return dyc<Entry_block> (vb[entry]);
  }

-Basic_block*
+Exit_block*
  CFG::get_exit_bb ()
  {
-	return vb[exit];
+	return dyc<Exit_block> (vb[exit]);
  }

  BB_list*
@@ -233,7 +233,7 @@
  		// headlabel and taillabel attributes dont expand the area they are
  		// in, and so are frequently unreadable.
  	}
-#define LINE_LENGTH 30
+#define LINE_LENGTH 20
  	void operator()(std::ostream& out, const vertex_t& v) const
  	{
  		out << "[";
@@ -350,7 +350,11 @@
  CFG::dump_graphviz (String* label)
  {
  	renumber_vertex_indices ();
-	consistency_check ();
+	if (label == NULL) // for debugging
+	{
+		consistency_check ();
+		label = s ("TEST");
+	}
  	write_graphviz (
  		cout,
  		bs,
@@ -532,9 +536,9 @@
  		foreach (Basic_block* frontier, *bb->get_dominance_frontier ())
  		{
  			// Get defs (including phi node LHSs)
-			Set* def_list = bb->get_pre_ssa_defs ();
+			VARIABLE_NAME_list* def_list = bb->get_pre_ssa_defs ();
  			foreach (Phi* phi, *bb->get_phi_nodes())
-				def_list->insert (phi->lhs);
+				def_list->push_back (phi->lhs);

  			bool def_added = false;
  			foreach (VARIABLE_NAME* var_name, *def_list)

Modified: branches/dataflow/src/optimize/CFG.h
==============================================================================
--- branches/dataflow/src/optimize/CFG.h	(original)
+++ branches/dataflow/src/optimize/CFG.h	Wed Sep 17 09:05:14 2008
@@ -17,6 +17,8 @@

  class Basic_block;
  class Branch_block;
+class Entry_block;
+class Exit_block;
  typedef List<Basic_block*> BB_list;

  class Edge;
@@ -116,8 +118,8 @@
  	/*
  	 * CFG access
  	 */
-	Basic_block* get_entry_bb ();
-	Basic_block* get_exit_bb ();
+	Entry_block* get_entry_bb ();
+	Exit_block* get_exit_bb ();

  	BB_list* get_all_bbs ();
  	BB_list* get_all_bbs_top_down ();

Modified: branches/dataflow/src/optimize/Def_use.cpp
==============================================================================
--- branches/dataflow/src/optimize/Def_use.cpp	(original)
+++ branches/dataflow/src/optimize/Def_use.cpp	Wed Sep 17 09:05:14 2008
@@ -22,10 +22,10 @@
  {
  }

-Set*
+VARIABLE_NAME_list*
  Def_use_web::get_bb_defs (Basic_block* bb)
  {
-	Set* result = new Set;
+	VARIABLE_NAME_list* result = new VARIABLE_NAME_list;

  	// Go through the use-def result, finding those who's BB == BB
  	pair<VARIABLE_NAME*, SSA_edge_list> pair;
@@ -37,16 +37,16 @@

  			// Dont insert the key, it may be the wrong var_name.
  			if (edge->bb == bb)
-				result->insert (edge->variable_name);
+				result->push_back (edge->variable_name);
  		}
  	}
  	return result;
  }

-Set*
+VARIABLE_NAME_list*
  Def_use_web::get_bb_uses (Basic_block* bb)
  {
-	Set* result = new Set;
+	VARIABLE_NAME_list* result = new VARIABLE_NAME_list;

  	// Go through the def-use result, finding those who's BB == BB
  	pair<VARIABLE_NAME*, SSA_edge_list> pair;
@@ -58,7 +58,7 @@

  			// Dont insert the key, it may be the wrong var_name.
  			if (edge->bb == bb)
-				result->insert (edge->variable_name);
+				result->push_back (edge->variable_name);
  		}
  	}

@@ -138,9 +138,11 @@
  }

  void
-Def_use_web::visit_assign_array (Statement_block*, MIR::Assign_array* in)
+Def_use_web::visit_assign_array (Statement_block* bb, MIR::Assign_array*  
in)
  {
-	assert (0);
+	add_use (in->lhs, new SSA_edge (bb));
+	add_use (in->rhs, new SSA_edge (bb));
+	add_use (in->index, new SSA_edge (bb));
  }

  void
@@ -213,9 +215,9 @@
  }

  void
-Def_use_web::visit_return (Statement_block*, MIR::Return* in)
+Def_use_web::visit_return (Statement_block* bb, MIR::Return* in)
  {
-	assert (0);
+	add_use (in->variable_name, new SSA_edge (bb));
  }

  void
@@ -244,9 +246,13 @@
  }

  void
-Def_use_web::visit_unset (Statement_block*, MIR::Unset* in)
+Def_use_web::visit_unset (Statement_block* bb, MIR::Unset* in)
  {
-	assert (0);
+	assert (in->target == NULL);
+	assert (in->array_indices->size () == 0);
+	assert (isa<VARIABLE_NAME> (in->variable_name));
+
+	add_def (dyc<VARIABLE_NAME> (in->variable_name), new SSA_edge (bb));
  }

  /*
@@ -256,7 +262,8 @@
  void
  Def_use_web::visit_array_access (Statement_block* bb, Array_access* in)
  {
-	assert (0);
+	add_use (in->variable_name, new SSA_edge (bb));
+	add_use (in->index, new SSA_edge (bb));
  }

  void

Modified: branches/dataflow/src/optimize/Def_use.h
==============================================================================
--- branches/dataflow/src/optimize/Def_use.h	(original)
+++ branches/dataflow/src/optimize/Def_use.h	Wed Sep 17 09:05:14 2008
@@ -31,8 +31,8 @@
  	Def_use_web ();

  	// These are intended for use during the conversion to SSA.
-	Set* get_bb_defs (Basic_block* bb);
-	Set* get_bb_uses (Basic_block* bb);
+	MIR::VARIABLE_NAME_list* get_bb_defs (Basic_block* bb);
+	MIR::VARIABLE_NAME_list* get_bb_uses (Basic_block* bb);

  	// For the variable DEF, return its uses.
  	SSA_edge_list* get_var_uses (MIR::VARIABLE_NAME* def);

Modified: branches/dataflow/src/optimize/SCCP.cpp
==============================================================================
--- branches/dataflow/src/optimize/SCCP.cpp	(original)
+++ branches/dataflow/src/optimize/SCCP.cpp	Wed Sep 17 09:05:14 2008
@@ -231,7 +231,7 @@
  		if (!pair.second->is_executable)
  			; // use TOP, aka do nothing
  		else
-			result = meet (result, lattice[pair.first]);
+			result = ::meet (result, lattice[pair.first]);
  	}
  	lattice[phi->lhs] = result;
  }
@@ -298,12 +298,6 @@
   */

  void
-SCCP::visit_assign_array (Statement_block*, MIR::Assign_array*)
-{
-	die ();
-}
-
-void
  SCCP::visit_assign_field (Statement_block*, MIR::Assign_field *)
  {
  	die ();
@@ -393,9 +387,11 @@

  	else
  	{
-		Literal* lit = lattice[in->use]->get_value ();
-		die (); // TODO go through embed
-		// TODO lower the lattice (same as in assign_var)
+		Literal* lit = get_literal (in->use);
+		Literal* result = PHP::fold_pre_op (lit, in->op);
+
+		if (result)
+			meet (in->def, result);
  	}
  }

@@ -412,9 +408,14 @@
  }

  void
-SCCP::visit_unset (Statement_block*, MIR::Unset*)
+SCCP::visit_unset (Statement_block*, MIR::Unset* in)
  {
-	die ();
+	assert (in->target == NULL);
+	assert (in->array_indices->size () == 0);
+	assert (isa<VARIABLE_NAME> (in->variable_name));
+
+	// Def_use asserts what we cant handle, for now.
+	meet (dyc<VARIABLE_NAME> (in->variable_name), new NIL ());
  }

  /* Returns NULL, or the literal in VARIABLE_NAME. We have separate  
functions,
@@ -433,6 +434,18 @@
  	return lattice[var_name]->get_value ()->clone ();
  }

+void
+SCCP::meet (VARIABLE_NAME* var_name, Literal* lit)
+{
+	meet (var_name, new Lattice_cell (lit));
+}
+
+void
+SCCP::meet (VARIABLE_NAME* var_name, Lattice_cell* lat)
+{
+	lattice[var_name] = ::meet (lattice[var_name], lat);
+}
+

  /*
   * Exprs
@@ -443,12 +456,17 @@
  Expr*
  SCCP::transform_array_access (Statement_block*, Array_access* in)
  {
-	// TODO is this a string, with a known index
-	assert (get_literal (in->variable_name) == NULL);
+	Literal* index = 0;

  	// Fold index
-	if (Literal* lit = get_literal (in->index))
-		in->index = lit;
+	if (Literal* index = get_literal (in->index))
+		in->index = index;
+
+	// Is this a string, with a known index.
+	Literal* array = get_literal (in->variable_name);
+	if (array && index)
+		die ();
+//		return fold_string_index (array, literal);

  	return in;
  }
@@ -655,9 +673,11 @@
  		}
  	}

-	void visit_assign_array (Statement_block*, MIR::Assign_array*)
+	void visit_assign_array (Statement_block*, MIR::Assign_array* in)
  	{
-		die ();
+		Literal* lit = get_literal (in->index);
+		if (lit)
+			in->index = lit;
  	}

  	void visit_assign_field (Statement_block*, MIR::Assign_field *)
@@ -712,16 +732,19 @@
  		die ();
  	}

-	void visit_ssa_pre_op (Statement_block*, MIR::SSA_pre_op* in)
+	void visit_ssa_pre_op (Statement_block* bb, MIR::SSA_pre_op* in)
  	{
-		// TODO go through embed
-		if (get_literal (in->use))
-			die ();
+		if (Literal* lit = get_literal (in->def))
+			bb->statement = new Assign_var (in->def, false, lit);
  	}

-	void visit_return (Statement_block*, MIR::Return*)
+	void visit_return (Statement_block* bb, MIR::Return* in)
  	{
-		die ();
+		// Dont propagate to return-by-ref
+		if (bb->cfg->get_entry_bb ()->method->signature->is_ref)
+			return;
+
+		// TODO change Return to take an Rvalue
  	}

  	void visit_static_declaration (Statement_block*, MIR::Static_declaration*)
@@ -739,9 +762,13 @@
  		die ();
  	}

-	void visit_unset (Statement_block*, MIR::Unset*)
+	void visit_unset (Statement_block*, MIR::Unset* in)
  	{
-		die ();
+		assert (in->target == NULL);
+		assert (in->array_indices->size () == 0);
+		assert (isa<VARIABLE_NAME> (in->variable_name));
+
+		// do nothing for a normal variable
  	}

  	/* Returns NULL, or the literal in VARIABLE_NAME. We have separate

Modified: branches/dataflow/src/optimize/SCCP.h
==============================================================================
--- branches/dataflow/src/optimize/SCCP.h	(original)
+++ branches/dataflow/src/optimize/SCCP.h	Wed Sep 17 09:05:14 2008
@@ -18,6 +18,9 @@
  	int get_predecessor_executable_count (Basic_block* bb);
  	void update_ir (CFG*);

+	void meet (MIR::VARIABLE_NAME* var_name, MIR::Literal* lit);
+	void meet (MIR::VARIABLE_NAME* var_name, Lattice_cell* lat);
+
  	// High-level SSA properties
  	void visit_phi (Phi* phi);
  	void visit_ssa_edge (SSA_edge* phi);
@@ -26,7 +29,6 @@
  	void visit_branch_block (Branch_block*);

  	// Statement blocks
-	void visit_assign_array (Statement_block*, MIR::Assign_array*);
  	void visit_assign_field (Statement_block*, MIR::Assign_field *);
  	void visit_assign_var (Statement_block*, MIR::Assign_var*);
  	void visit_assign_var_var (Statement_block*, MIR::Assign_var_var*);


More information about the phc-internals mailing list