[phc-internals] [phc commit] r1838 - in
branches/dataflow/src/optimize: . ssa
codesite-noreply at google.com
codesite-noreply at google.com
Wed Oct 29 20:31:50 GMT 2008
Author: paul.biggar
Date: Wed Oct 29 13:31:24 2008
New Revision: 1838
Modified:
branches/dataflow/src/optimize/Basic_block.cpp
branches/dataflow/src/optimize/Dead_code_elimination.cpp
branches/dataflow/src/optimize/Def_use.cpp
branches/dataflow/src/optimize/Def_use.h
branches/dataflow/src/optimize/ssa/HSSA.cpp
branches/dataflow/src/optimize/ssa/SSA.cpp
branches/dataflow/src/optimize/ssa/SSA_ops.cpp
Log:
Separate may_defs and defs in the use_def chains, and stop pretending that
method_invocations use proper defs.
Clarify that get_nonphi_defs is really get_real_defs, and exclude phis, mus
and chis.
Dont add chi nodes (may-defs) if there is a must-def to the same node.
These make bench_strcat work.
Modified: branches/dataflow/src/optimize/Basic_block.cpp
==============================================================================
--- branches/dataflow/src/optimize/Basic_block.cpp (original)
+++ branches/dataflow/src/optimize/Basic_block.cpp Wed Oct 29 13:31:24 2008
@@ -328,7 +328,7 @@
foreach (Edge* pred, *get_predecessor_edges ())
{
// Not all nodes have their phi argument added yet
- if (pred->pm.find (old_phi_lhs) != pred->pm.end ())
+ if (pred->pm.has (old_phi_lhs))
set_phi_arg_for_edge (
pred,
new_phi_lhs,
@@ -590,13 +590,13 @@
VARIABLE_NAME_list*
Basic_block::get_pre_ssa_defs ()
{
- return cfg->duw->get_nonphi_defs (this);
+ return cfg->duw->get_real_defs (this);
}
VARIABLE_NAME_list*
Basic_block::get_pre_ssa_uses ()
{
- return cfg->duw->get_nonphi_uses (this);
+ return cfg->duw->get_real_uses (this);
}
int
Modified: branches/dataflow/src/optimize/Dead_code_elimination.cpp
==============================================================================
--- branches/dataflow/src/optimize/Dead_code_elimination.cpp (original)
+++ branches/dataflow/src/optimize/Dead_code_elimination.cpp Wed Oct 29
13:31:24 2008
@@ -118,6 +118,8 @@
{
SSA_op* op = worklist->front ();
worklist->pop_front ();
+ DEBUG ("Processing ");
+ op->dump ();
foreach (VARIABLE_NAME* use, *op->get_uses ())
{
Modified: branches/dataflow/src/optimize/Def_use.cpp
==============================================================================
--- branches/dataflow/src/optimize/Def_use.cpp (original)
+++ branches/dataflow/src/optimize/Def_use.cpp Wed Oct 29 13:31:24 2008
@@ -39,6 +39,7 @@
Def_use_web::Def_use_web ()
: def_use_chains (&variable_name_ptr_comparison)
, use_def_chains (&variable_name_ptr_comparison)
+, may_defs (&variable_name_ptr_comparison)
{
}
@@ -84,7 +85,7 @@
}
VARIABLE_NAME_list*
-Def_use_web::get_nonphi_defs (Basic_block* bb)
+Def_use_web::get_real_defs (Basic_block* bb)
{
VARIABLE_NAME_list* result = new VARIABLE_NAME_list;
@@ -95,8 +96,10 @@
{
foreach (SSA_edge* edge, edge_list)
{
- if (!isa<SSA_phi> (edge->op)
- && edge->op->get_bb () == bb)
+ if (edge->op->get_bb () == bb
+ && !isa<SSA_phi> (edge->op)
+ && !isa<SSA_mu> (edge->op)
+ && !isa<SSA_chi> (edge->op))
{
// Dont insert the key itself, it may be the wrong var_name.
result->push_back (edge->variable_name);
@@ -107,7 +110,7 @@
}
VARIABLE_NAME_list*
-Def_use_web::get_nonphi_uses (Basic_block* bb)
+Def_use_web::get_real_uses (Basic_block* bb)
{
VARIABLE_NAME_list* result = new VARIABLE_NAME_list;
@@ -118,8 +121,32 @@
{
foreach (SSA_edge* edge, edge_list)
{
- if (!isa<SSA_phi> (edge->op)
- && edge->op->get_bb () == bb)
+ if (edge->op->get_bb () == bb
+ && !isa<SSA_phi> (edge->op)
+ && !isa<SSA_mu> (edge->op)
+ && !isa<SSA_chi> (edge->op))
+ {
+ // Dont insert the key itself, it may be the wrong var_name.
+ result->push_back (edge->variable_name);
+ }
+ }
+ }
+ return result;
+}
+
+VARIABLE_NAME_list*
+Def_use_web::get_may_defs (Basic_block* bb)
+{
+ VARIABLE_NAME_list* result = new VARIABLE_NAME_list;
+
+ // Go through the use-def result, finding those who's BB == BB
+ VARIABLE_NAME* key;
+ SSA_edge_list edge_list;
+ foreach (tie (key, edge_list), may_defs)
+ {
+ foreach (SSA_edge* edge, edge_list)
+ {
+ if (edge->op->get_bb () == bb)
{
// Dont insert the key itself, it may be the wrong var_name.
result->push_back (edge->variable_name);
@@ -196,6 +223,26 @@
DEBUG (endl);
}
+// When building use-def chains, we add may-defs for things we know arent
+// actually defs, but where there could potentially be a def. Currently,
this
+// is just method_invocation.
+// TODO: globals need the opposite: its really a def, but its doesnt may
def
+// anything else.
+void
+Def_use_web::add_may_def (MIR::VARIABLE_NAME* use, SSA_op* def)
+{
+ SSA_edge* edge = new SSA_edge (use, def);
+
+ // When used on pre-SSA form, there can be many defs.
+ may_defs[use].push_back (edge);
+
+ DEBUG ("Adding a may_def edge from ");
+ debug (use);
+ DEBUG ("to ")
+ def->dump ();
+ DEBUG (endl);
+}
+
void
Def_use_web::visit_entry_block (Entry_block* bb)
{
@@ -425,9 +472,7 @@
if (VARIABLE_NAME* var = dynamic_cast<VARIABLE_NAME*> (param->rvalue))
{
add_use (var, new SSA_stmt (bb));
- // TODO: this is a little out of place. We're cloning so that
- // conversion to SSA doesnt convert this to SSA twice.
- add_def (var->clone (), new SSA_stmt (bb));
+ add_may_def (var, new SSA_stmt (bb));
}
}
}
Modified: branches/dataflow/src/optimize/Def_use.h
==============================================================================
--- branches/dataflow/src/optimize/Def_use.h (original)
+++ branches/dataflow/src/optimize/Def_use.h Wed Oct 29 13:31:24 2008
@@ -51,6 +51,13 @@
bool (*)(MIR::VARIABLE_NAME*, MIR::VARIABLE_NAME*)
> use_def_chains;
+ Map<
+ MIR::VARIABLE_NAME*,
+ SSA_edge_list,
+ bool (*)(MIR::VARIABLE_NAME*, MIR::VARIABLE_NAME*)
+ > may_defs;
+
+
public:
Def_use_web ();
@@ -74,14 +81,15 @@
BB_list* get_pre_ssa_var_defs (MIR::VARIABLE_NAME* use);
- // Get all variables defined/used in the basic block, except for those
- // from phi nodes.
- MIR::VARIABLE_NAME_list* get_nonphi_defs (Basic_block* bb);
- MIR::VARIABLE_NAME_list* get_nonphi_uses (Basic_block* bb);
+ // Get all variables defined/used in the basic
+ // block, except for those from phis, mus and chis.
+ MIR::VARIABLE_NAME_list* get_real_defs (Basic_block* bb);
+ MIR::VARIABLE_NAME_list* get_real_uses (Basic_block* bb);
// Return the variables defined by formal parameters in the entry_block
MIR::VARIABLE_NAME_list* get_formal_defs ();
+ MIR::VARIABLE_NAME_list* get_may_defs (Basic_block* bb);
void dump ();
@@ -90,6 +98,7 @@
void add_use (MIR::VARIABLE_NAME* def, SSA_op* use);
void add_use (MIR::Rvalue* def, SSA_op* use);
void add_def (MIR::VARIABLE_NAME* use, SSA_op* def);
+ void add_may_def (MIR::VARIABLE_NAME* use, SSA_op* def);
void visit_entry_block (Entry_block* bb);
void visit_branch_block (Branch_block* bb);
Modified: branches/dataflow/src/optimize/ssa/HSSA.cpp
==============================================================================
--- branches/dataflow/src/optimize/ssa/HSSA.cpp (original)
+++ branches/dataflow/src/optimize/ssa/HSSA.cpp Wed Oct 29 13:31:24 2008
@@ -187,10 +187,10 @@
rebuild_ssa_form (); // we only care about DUW
foreach (Basic_block* bb, *cfg->get_all_bbs ())
{
- foreach (VARIABLE_NAME* var, *cfg->duw->get_nonphi_uses (bb))
+ foreach (VARIABLE_NAME* var, *cfg->duw->get_real_uses (bb))
var->drop_ssa_index();
- foreach (VARIABLE_NAME* var, *cfg->duw->get_nonphi_defs (bb))
+ foreach (VARIABLE_NAME* var, *cfg->duw->get_real_defs (bb))
var->drop_ssa_index();
}
@@ -468,14 +468,14 @@
}
- // TODO: Zero versioning is actually useful, so add steps 5 and 6. There
is
- // not necessarily a need to combine zero versioning with DCE.
+ // TODO: Zero versioning is actually useful, so add steps 5 and 6. There
+ // is not necessarily a need to combine zero versioning with GVN.
}
// Given the alias set, all for every use, add a mu of all aliased
variables,
-// and for every def, add
+// and for every def, add a chi.
void
HSSA::add_mu_and_chi_nodes (Set* aliases)
{
@@ -490,10 +490,13 @@
foreach (VARIABLE_NAME* alias, *aliases)
bb->add_mu_node (alias);
- // TODO: This doesnt add chis for actual parameters
- foreach (VARIABLE_NAME* def, *bb->get_pre_ssa_defs ())
+ VARIABLE_NAME_list* defs = new VARIABLE_NAME_list;
+ defs->push_back_all (bb->get_pre_ssa_defs ());
+ defs->push_back_all (bb->cfg->duw->get_may_defs (bb));
+ foreach (VARIABLE_NAME* def, *defs)
if (aliases->has (def))
foreach (VARIABLE_NAME* alias, *aliases)
- bb->add_chi_node (alias);
+ if (!alias->equals (def))
+ bb->add_chi_node (alias);
}
}
Modified: branches/dataflow/src/optimize/ssa/SSA.cpp
==============================================================================
--- branches/dataflow/src/optimize/ssa/SSA.cpp (original)
+++ branches/dataflow/src/optimize/ssa/SSA.cpp Wed Oct 29 13:31:24 2008
@@ -87,6 +87,8 @@
// Rename local variable uses
VARIABLE_NAME_list* uses = bb->get_pre_ssa_uses ();
+ uses->push_back_all (bb->get_mus ());
+ uses->push_back_all (bb->get_chi_rhss ());
foreach (VARIABLE_NAME* use, *uses)
{
DEBUG ("Converting use " << *use->get_ssa_var_name ());
@@ -98,6 +100,7 @@
// Create new names for defs
VARIABLE_NAME_list* defs = bb->get_pre_ssa_defs ();
+ defs->push_back_all (bb->get_chi_lhss ());
foreach (VARIABLE_NAME* def, *defs)
{
DEBUG ("Converting def " << *def->get_ssa_var_name ());
Modified: branches/dataflow/src/optimize/ssa/SSA_ops.cpp
==============================================================================
--- branches/dataflow/src/optimize/ssa/SSA_ops.cpp (original)
+++ branches/dataflow/src/optimize/ssa/SSA_ops.cpp Wed Oct 29 13:31:24 2008
@@ -76,7 +76,7 @@
void SSA_chi::dump()
{
- DEBUG ("SSA_chi: " << *lhs->get_ssa_var_name () << ", " <<
*rhs->get_ssa_var_name ());
+ DEBUG ("SSA_chi: " << *lhs->get_ssa_var_name () << " <- " <<
*rhs->get_ssa_var_name ());
bb->dump ();
}
@@ -135,7 +135,13 @@
VARIABLE_NAME_list*
SSA_stmt::get_uses ()
{
- return bb->cfg->duw->get_nonphi_uses (bb);
+ // Phis are different statements, but mus and chis are properties of the
+ // current statement.
+ VARIABLE_NAME_list* result = new VARIABLE_NAME_list;
+ result->push_back_all (bb->cfg->duw->get_real_uses (bb));
+ result->push_back_all (bb->get_mus ());
+ result->push_back_all (bb->get_chi_rhss ());
+ return result;
}
VARIABLE_NAME_list*
More information about the phc-internals
mailing list