[phc-internals] [phc commit] r1620 - in branches/dataflow/src:
optimize pass_manager
codesite-noreply at google.com
codesite-noreply at google.com
Mon Sep 8 21:13:34 IST 2008
Author: paul.biggar
Date: Mon Sep 8 13:12:29 2008
New Revision: 1620
Modified:
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/Lattice.cpp
branches/dataflow/src/optimize/Lattice.h
branches/dataflow/src/optimize/SCCP.cpp
branches/dataflow/src/optimize/SCCP.h
branches/dataflow/src/pass_manager/Pass_manager.cpp
Log:
Continue propagation. This gets use as far as propagating the fact that a
variable is constat, but not its value. It also puts in most of the work on
constant folding.
Modified: branches/dataflow/src/optimize/Basic_block.cpp
==============================================================================
--- branches/dataflow/src/optimize/Basic_block.cpp (original)
+++ branches/dataflow/src/optimize/Basic_block.cpp Mon Sep 8 13:12:29 2008
@@ -192,6 +192,27 @@
return succs->front ();
}
+Edge_list*
+Basic_block::get_predecessor_edges ()
+{
+ return cfg->get_edge_predecessors (this);
+}
+
+Edge_list*
+Basic_block::get_successor_edges ()
+{
+ return cfg->get_edge_successors (this);
+}
+
+
+Edge*
+Basic_block::get_successor_edge ()
+{
+ Edge_list* succs = get_successor_edges ();
+ assert (succs->size() == 1);
+ return succs->front ();
+}
+
Basic_block*
Branch_block::get_true_successor ()
{
@@ -302,3 +323,4 @@
{
return cfg->index[vertex];
}
+
Modified: branches/dataflow/src/optimize/Basic_block.h
==============================================================================
--- branches/dataflow/src/optimize/Basic_block.h (original)
+++ branches/dataflow/src/optimize/Basic_block.h Mon Sep 8 13:12:29 2008
@@ -60,7 +60,8 @@
// Assert a block has a single successor, and return it.
Basic_block* get_successor ();
- // TODO same for edge
+ Edge* get_successor_edge ();
+ // TODO same for preds
Edge_list* get_predecessor_edges ();
Edge_list* get_successor_edges ();
Modified: branches/dataflow/src/optimize/CFG.cpp
==============================================================================
--- branches/dataflow/src/optimize/CFG.cpp (original)
+++ branches/dataflow/src/optimize/CFG.cpp Mon Sep 8 13:12:29 2008
@@ -176,7 +176,6 @@
BB_list*
CFG::get_all_bbs ()
{
-
BB_list* result = new BB_list;
foreach (vertex_t v, vertices(bs))
@@ -621,6 +620,50 @@
return ee[e];
assert (0);
+}
+
+Edge*
+CFG::get_entry_edge ()
+{
+ return get_entry_bb ()->get_successor_edge ();
+}
+
+Edge_list*
+CFG::get_all_edges ()
+{
+ Edge_list* result = new Edge_list;
+
+ foreach (edge_t e, edges(bs))
+ {
+ result->push_back (ee[e]);
+ }
+ return result;
+}
+
+Edge_list*
+CFG::get_edge_successors (Basic_block* bb)
+{
+ Edge_list* result = new Edge_list;
+
+ foreach (edge_t e, out_edges (bb->vertex, bs))
+ {
+ result->push_back (ee[e]);
+ }
+
+ return result;
+}
+
+Edge_list*
+CFG::get_edge_predecessors (Basic_block* bb)
+{
+ Edge_list* result = new Edge_list;
+
+ foreach (edge_t e, in_edges (bb->vertex, bs))
+ {
+ result->push_back (ee[e]);
+ }
+
+ return result;
}
/* returns true or false. If edge isnt true or false, asserts. */
Modified: branches/dataflow/src/optimize/CFG.h
==============================================================================
--- branches/dataflow/src/optimize/CFG.h (original)
+++ branches/dataflow/src/optimize/CFG.h Mon Sep 8 13:12:29 2008
@@ -138,8 +138,6 @@
void convert_to_ssa_form ();
void convert_out_of_ssa_form ();
- MIR::VARIABLE_NAME_list* get_all_variables ();
-
private:
Graph bs; // backing store
@@ -154,6 +152,8 @@
// For BB methods
BB_list* get_bb_successors (Basic_block* bb);
BB_list* get_bb_predecessors (Basic_block* bb);
+ Edge_list* get_edge_successors (Basic_block* bb);
+ Edge_list* get_edge_predecessors (Basic_block* bb);
Edge* get_edge (Basic_block* bb1, Basic_block* bb2);
void replace_bb (Basic_block* bb, BB_list* replacements);
void remove_bb (Basic_block* bb);
Modified: branches/dataflow/src/optimize/Lattice.cpp
==============================================================================
--- branches/dataflow/src/optimize/Lattice.cpp (original)
+++ branches/dataflow/src/optimize/Lattice.cpp Mon Sep 8 13:12:29 2008
@@ -1,6 +1,45 @@
#include "Lattice.h"
+/* VisitPhi:
+ * The lattice of the phis output variable is the meet of all the inputs
+ * (non-execable means TOP), with the meet function:
+ * any + TOP = any
+ * any + BOTTOM = BOTTOM
+ * ci + cj = ci if i == j (? surely if c_i == c_j?)
+ * c1 + c2 = BOTTOM if i != j (this can be improved with VRP, using a
similar algorithm).
+ */
+// TODO move this into SCCP
Lattice_cell meet (Lattice_cell l1, Lattice_cell l2)
{
- assert (0);
+ switch (l1)
+ {
+ case TOP:
+ return l2;
+
+ case CONST:
+ {
+ switch (l2)
+ {
+ case TOP:
+ return l1;
+
+ case CONST:
+ // TODO
+ return CONST;
+
+ case BOTTOM:
+ return BOTTOM;
+
+ default:
+ assert (0);
+ }
+ break;
+ }
+
+ case BOTTOM:
+ return BOTTOM;
+
+ default:
+ assert (0);
+ }
}
Modified: branches/dataflow/src/optimize/Lattice.h
==============================================================================
--- branches/dataflow/src/optimize/Lattice.h (original)
+++ branches/dataflow/src/optimize/Lattice.h Mon Sep 8 13:12:29 2008
@@ -7,6 +7,8 @@
#include <map>
#include "MIR.h"
+#include "Set.h"
+
// TODO templatize on the lattice type
class Lattice
@@ -24,6 +26,7 @@
> parent;
public:
Lattice ()
+ : parent (&variable_name_ptr_comparison)
{
}
Modified: branches/dataflow/src/optimize/SCCP.cpp
==============================================================================
--- branches/dataflow/src/optimize/SCCP.cpp (original)
+++ branches/dataflow/src/optimize/SCCP.cpp Mon Sep 8 13:12:29 2008
@@ -105,30 +105,30 @@
#include "SCCP.h"
#include "Lattice.h"
+#include "process_ir/debug.h"
+
using namespace MIR;
SCCP::SCCP (CFG* cfg)
+: cfg(cfg)
{
}
void
SCCP::execute ()
{
-
// 1. Initialize:
Edge_list* cfg_wl = new Edge_list(cfg->get_entry_edge ());
SSA_edge_list* ssa_wl = new SSA_edge_list;
foreach (Edge* e, *cfg->get_all_edges ())
- {
e->is_executable = false;
- }
- cfg->get_entry_edge()->is_executable = true;
- foreach (VARIABLE_NAME* var, *cfg->get_all_variables ())
- {
- lattice [var] = TOP;
- }
+ // TODO initialize lazily
+// foreach (VARIABLE_NAME* var, *cfg->get_all_variables ())
+// {
+// lattice [var] = TOP;
+// }
// 2. Stop when CFG-worklist and SSA-worklist are both empty.
while (cfg_wl->size () > 0 || ssa_wl->size () > 0)
@@ -169,10 +169,9 @@
// be > 1
assert (exec_count > 0);
- if (exec_count > 1)
+ if (exec_count == 1)
{
- assert (0); // TODO
-// visit_expr (e->target);
+ visit_block (e->target);
}
Edge_list* succs = e->target->get_successor_edges ();
@@ -206,12 +205,6 @@
void
SCCP::visit_phi (Phi* phi)
{
- Lattice_cell result = TOP;
- foreach (VARIABLE_NAME* var, *phi->args)
- {
- result = meet (result, lattice[var]);
- }
- lattice[phi->lhs] = result;
/* VisitPhi:
* The lattice of the phis output variable is the meet of all the inputs
* (non-execable means TOP), with the meet function:
@@ -220,6 +213,12 @@
* ci + cj = ci if i == j (? surely if c_i == c_j?)
* c1 + c2 = BOTTOM if i != j (this can be improved with VRP, using a
similar algorithm).
*/
+ Lattice_cell result = TOP;
+ foreach (VARIABLE_NAME* var, *phi->args)
+ {
+ result = meet (result, lattice[var]);
+ }
+ lattice[phi->lhs] = result;
}
/* VisitExpr:
@@ -230,17 +229,399 @@
* - all outgoing edges to CFGWL for BOTTOM
* - only the appropriate outgoing edge for a constant
*/
+
+void
+SCCP::visit_block (Basic_block* bb)
+{
+ if (Entry_block* eb = dynamic_cast<Entry_block*> (bb))
+ this->visit_entry_block (eb);
+
+ else if (Empty_block* eb = dynamic_cast<Empty_block*> (bb))
+ this->visit_empty_block (eb);
+
+ else if (Exit_block* eb = dynamic_cast<Exit_block*> (bb))
+ this->visit_exit_block (eb);
+
+ else if (Branch_block* brb = dynamic_cast<Branch_block*> (bb))
+ this->visit_branch_block (brb);
+
+ else if (Statement_block* sb = dynamic_cast<Statement_block*> (bb))
+ {
+ switch (sb->statement->classid ())
+ {
+ case MIR::Assign_array::ID:
+ this->visit_assign_array(sb, dyc<MIR::Assign_array>(sb->statement));
+ break;
+ case MIR::Assign_field::ID:
+ this->visit_assign_field(sb, dyc<MIR::Assign_field>(sb->statement));
+ break;
+ case MIR::Assign_var::ID:
+ this->visit_assign_var(sb, dyc<MIR::Assign_var>(sb->statement));
+ break;
+ case MIR::Assign_var_var::ID:
+ this->visit_assign_var_var(sb,
dyc<MIR::Assign_var_var>(sb->statement));
+ break;
+ case MIR::Eval_expr::ID:
+ this->visit_eval_expr(sb, dyc<MIR::Eval_expr>(sb->statement));
+ break;
+ case MIR::Foreach_end::ID:
+ this->visit_foreach_end(sb, dyc<MIR::Foreach_end>(sb->statement));
+ break;
+ case MIR::Foreach_next::ID:
+ this->visit_foreach_next(sb, dyc<MIR::Foreach_next>(sb->statement));
+ break;
+ case MIR::Foreach_reset::ID:
+ this->visit_foreach_reset(sb, dyc<MIR::Foreach_reset>(sb->statement));
+ break;
+ case MIR::Global::ID:
+ this->visit_global(sb, dyc<MIR::Global>(sb->statement));
+ break;
+ case MIR::Param_is_ref::ID:
+ this->visit_param_is_ref (sb, dyc<MIR::Param_is_ref>(sb->statement));
+ break;
+ case MIR::Pre_op::ID:
+ this->visit_pre_op(sb, dyc<MIR::Pre_op>(sb->statement));
+ break;
+ case MIR::Push_array::ID:
+ this->visit_push_array(sb, dyc<MIR::Push_array>(sb->statement));
+ break;
+ case MIR::Return::ID:
+ this->visit_return(sb, dyc<MIR::Return>(sb->statement));
+ break;
+ case MIR::Static_declaration::ID:
+ this->visit_static_declaration(sb,
dyc<MIR::Static_declaration>(sb->statement));
+ break;
+ case MIR::Throw::ID:
+ this->visit_throw(sb, dyc<MIR::Throw>(sb->statement));
+ break;
+ case MIR::Try::ID:
+ this->visit_try(sb, dyc<MIR::Try>(sb->statement));
+ break;
+ case MIR::Unset::ID:
+ this->visit_unset (sb, dyc<MIR::Unset>(sb->statement));
+ break;
+ default:
+ xdebug (sb->statement);
+ assert (0);
+ }
+ }
+}
+
+void
+SCCP::visit_entry_block (Entry_block*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_empty_block (Empty_block*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_exit_block (Exit_block*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_branch_block (Branch_block*)
+{
+ assert (0);
+}
+
+
+void
+SCCP::visit_assign_array (Statement_block*, MIR::Assign_array*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_assign_field (Statement_block*, MIR::Assign_field *)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_assign_var (Statement_block*, MIR::Assign_var* in)
+{
+ Expr* expr = in->rhs;
+ // Attempt to fold the expression.
+ switch(expr->classid())
+ {
+ case BOOL::ID:
+ case INT::ID:
+ case NIL::ID:
+ case REAL::ID:
+ case STRING::ID:
+ // do nothing
+ break;
+
+ case Constant::ID:
+ // TODO we'd very much like to know the value of this, however,
+ // since these are liekly to be deinfed at the top-level, and this
+ // optimization won't run at the top-level (until its
+ // interprocedural), it won't do much good.
+ break;
+
+ case Param_is_ref::ID:
+ // TODO go through embed.
+ assert (0);
+ break;
+
+ case Bin_op::ID:
+ {
+ Bin_op* bin_op = dyc<Bin_op> (expr);
+
+ Literal* left = get_literal (bin_op->left);
+ Literal* right = get_literal (bin_op->right);
+
+ if (left) bin_op->left = left;
+ if (right) bin_op->right = left;
+
+ if (left && right)
+ assert (0); // TODO go through embed
+ else
+ {
+ }
+ break;
+ }
+
+ case Cast::ID:
+ {
+ Cast* cast = dyc<Cast> (expr);
+ Literal* lit = get_literal (cast->variable_name);
+
+ if (lit)
+ {
+ assert (0); // go through embed
+ }
+ break;
+ }
+
+ case Foreach_get_key::ID:
+ break;
+
+ case Foreach_get_val::ID:
+ break;
+
+ case Foreach_has_key::ID:
+ break;
+
+ case Array_access::ID:
+ {
+ Array_access* ia = dyc<Array_access> (in);
+ // TODO is this a string, with a known index?
+
+ // Fold index
+ Literal* index = get_literal (ia->index);
+ if (index)
+ ia->index = index;
+
+ break;
+ }
+
+ case Isset::ID:
+ {
+ // fold isset (5) to true;
+ Isset* i = dyc<Isset> (in);
+ if (i->target == NULL
+ && isa<VARIABLE_NAME> (i->variable_name)
+ && i->array_indices->size () == 0
+ && get_literal (dyc<VARIABLE_NAME> (i->variable_name)))
+ in->rhs = new BOOL (true);
+ }
+
+ case Instanceof::ID:
+ assert (0);
+ break;
+
+ case Method_invocation::ID:
+ {
+ Method_invocation* mi = dyc<Method_invocation> (in);
+
+ // TODO APC::Optimizer has a list of pure functions. Go through
+ // embed for them.
+ assert (0);
+
+ // TODO replace Variable_variable with VARIABLE_NAME, if possible.
+
+ // TODO: we can replace a arguement with its actual parameter
+ // (watch out for refs) (only if passing by copy)
+
+/* if (isa<VARIABLE_NAME> (mi->method_name))
+ assert (0); // TODO
+
+ foreach (Actual_parameter* ap, *mi->actual_parameters)
+ {
+ VARIABLE_NAME* var_name = dynamic_cast<VARIABLE_NAME*> (ap->rvalue);
+ if (var_name)
+ use (bb, var_name);
+ }*/
+ break;
+ }
+
+ case New::ID:
+ {
+ // TODO turn a variable_varaible into a VARIABLE_NAME
+ New* n = dyc<New> (in);
+ break;
+ }
+
+ case Field_access::ID:
+ {
+ // TODO warning
+ // TODO promote name to FIEDL_NAME
+ Field_access* fa = dyc<Field_access> (in);
+
+ // This uses a variable field, not a variable expr.
+// if (isa<Variable_field> (fa->field_name))
+// use (bb, dyc<Variable_field> (fa->field_name)->variable_name);
+//
+// if (isa<VARIABLE_NAME> (fa->target))
+// use (bb, dyc<VARIABLE_NAME> (fa->target));
+
+ break;
+ }
+
+ case Unary_op::ID:
+ {
+ Unary_op* u = dyc<Unary_op> (expr);
+ Literal* lit = get_literal (u->variable_name);
+ assert (0); // go through embed
+ break;
+ }
+
+ case VARIABLE_NAME::ID:
+ {
+ VARIABLE_NAME* var_name = dyc<VARIABLE_NAME> (in);
+ if (Literal* lit = get_literal (var_name))
+ expr = lit;
+
+ break;
+ }
+
+ case Variable_variable::ID:
+ {
+ Variable_variable* var_var = dyc<Variable_variable> (in);
+ if (Literal* lit = get_literal (var_var->variable_name))
+ assert (0);
+ //expr = new VARIABLE_NAME (PHP::to_string (lit));
+
+ break;
+ }
+
+ default:
+ assert (0);
+ break;
+ }
+
+ in->rhs = expr;
+
+ if (isa<Literal> (expr))
+ {
+ assert (in->is_ref == false); // TODO
+ lattice[in->lhs] = CONST;
+ }
+}
+
+void
+SCCP::visit_assign_var_var (Statement_block*, MIR::Assign_var_var*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_eval_expr (Statement_block*, MIR::Eval_expr*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_foreach_end (Statement_block*, MIR::Foreach_end*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_foreach_next (Statement_block*, MIR::Foreach_next*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_foreach_reset (Statement_block*, MIR::Foreach_reset*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_global (Statement_block*, MIR::Global*)
+{
+}
+
+void
+SCCP::visit_param_is_ref (Statement_block*, MIR::Param_is_ref*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_pre_op (Statement_block*, MIR::Pre_op*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_push_array (Statement_block*, MIR::Push_array*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_return (Statement_block*, MIR::Return*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_static_declaration (Statement_block*, MIR::Static_declaration*)
+{
+ assert (0);
+}
+
+void
+SCCP::visit_throw (Statement_block*, MIR::Throw*)
+{
+ assert (0);
+}
+
void
-SCCP::visit_statement (Statement* in)
+SCCP::visit_try (Statement_block*, MIR::Try*)
{
- // TODO const folding
assert (0);
}
void
-SCCP::visit_branch (Branch* in)
+SCCP::visit_unset (Statement_block*, MIR::Unset*)
{
- // TODO const folding
assert (0);
}
+/* Returns NULL, or the literal in VARIABLE_NAME. We have separate
functions,
+ * because we cant substitute Literals directly into the IR in many
cases.*/
+Literal*
+SCCP::get_literal (Rvalue* in)
+{
+ if (isa<Literal> (in))
+ return dyc<Literal> (in);
+
+ VARIABLE_NAME* var_name = dyc<VARIABLE_NAME> (in);
+
+ if (lattice[var_name] != CONST)
+ return NULL;
+
+ assert (0); // TODO
+}
Modified: branches/dataflow/src/optimize/SCCP.h
==============================================================================
--- branches/dataflow/src/optimize/SCCP.h (original)
+++ branches/dataflow/src/optimize/SCCP.h Mon Sep 8 13:12:29 2008
@@ -12,10 +12,35 @@
SCCP (CFG* cfg);
void execute ();
void visit_phi (Phi* phi);
+ void visit_block (Basic_block* bb);
void visit_statement (MIR::Statement* in);
void visit_branch (MIR::Branch* in);
- };
+ void visit_entry_block (Entry_block*);
+ void visit_empty_block (Empty_block*);
+ void visit_exit_block (Exit_block*);
+ void visit_branch_block (Branch_block*);
+
+ 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*);
+ void visit_eval_expr (Statement_block*, MIR::Eval_expr*);
+ void visit_foreach_end (Statement_block*, MIR::Foreach_end*);
+ void visit_foreach_next (Statement_block*, MIR::Foreach_next*);
+ void visit_foreach_reset (Statement_block*, MIR::Foreach_reset*);
+ void visit_global (Statement_block*, MIR::Global*);
+ void visit_param_is_ref (Statement_block*, MIR::Param_is_ref*);
+ void visit_pre_op (Statement_block*, MIR::Pre_op*);
+ void visit_push_array (Statement_block*, MIR::Push_array*);
+ void visit_return (Statement_block*, MIR::Return*);
+ void visit_static_declaration (Statement_block*,
MIR::Static_declaration*);
+ void visit_throw (Statement_block*, MIR::Throw*);
+ void visit_try (Statement_block*, MIR::Try*);
+ void visit_unset (Statement_block*, MIR::Unset*);
+
+ MIR::Literal* get_literal (MIR::Rvalue* in);
+};
#endif // PHC_SCCP_H
Modified: branches/dataflow/src/pass_manager/Pass_manager.cpp
==============================================================================
--- branches/dataflow/src/pass_manager/Pass_manager.cpp (original)
+++ branches/dataflow/src/pass_manager/Pass_manager.cpp Mon Sep 8 13:12:29
2008
@@ -574,7 +574,8 @@
if (args_info->cfg_dump_given)
cfg->dump_graphviz (s("CFG - in SSA"));
- (new SCCP (cfg))->execute ();
+ SCCP* sccp = new SCCP (cfg);
+ sccp->execute ();
if (args_info->cfg_dump_given)
cfg->dump_graphviz (s("CFG - after SCCP"));
More information about the phc-internals
mailing list