defs_elim.c File Reference

#include "local.h"
#include "prettyprint.h"

Include dependency graph for defs_elim.c:

Go to the source code of this file.

Functions
static vertex	get_vertex_of_statement (graph dg, statement stmt)
	– defs_elim.c More...
bool	true_dependence_with_entity_p (conflict conf, entity e)
	=========================================================================== More...
static bool	entity_dynamic_p (entity e)
	=========================================================================== More...
bool	defs_elim_of_assign_call (statement assign_stmt, graph dg)
	=========================================================================== More...
bool	defs_elim_of_statement (statement s, graph dg)
	=========================================================================== More...
void	defs_elim_of_unstructured (unstructured u, graph dg)
	=========================================================================== More...

Function Documentation

defs_elim_of_assign_call()

bool defs_elim_of_assign_call	(	statement	assign_stmt,
		graph	dg
	)

===========================================================================

bool defs_elim_of_assign_call(statement assign_stmt, graph dg): returns true if "assign_stmt" is to be eliminated. It is eliminated if the lhs of this assignment verifies two conditions :

1. it is a local variable
2. it is not at the source of a def-use dependence, ie true dependence.

Definitions upon non local (non dynamic) variables are always kept.

Gets the vertex of the dependence graph that gives all the edges of which the assign statement is the source.

We scan all the dependences of the assign statement. If at least one true dependence is found, the statement is not removed.

Parameters

assign_stmt	ssign_stmt
dg	g

Definition at line 136 of file defs_elim.c.

{
    call assign_call;
    expression lhs_exp;
    entity lhs_ent;
    vertex stmt_vertex;
    list succs;
    bool true_dep_found = false;
 
    if(instruction_tag(statement_instruction(assign_stmt)) != is_instruction_call)
        pips_internal_error("Statement must be a CALL");
 
    assign_call = instruction_call(statement_instruction(assign_stmt));
    if(! ENTITY_ASSIGN_P(call_function(assign_call)))
        pips_internal_error("Call must be an ASSIGN");
 
    pips_debug(5, "begin ASSIGN : %s\n",
               words_to_string(Words_Call(assign_call, 0, true, true)));
 
    lhs_exp = EXPRESSION(CAR(call_arguments(assign_call)));
    if(syntax_tag(expression_syntax(lhs_exp)) != is_syntax_reference)
        pips_internal_error("Lhs must be a REFERENCE");
 
    lhs_ent = reference_variable(syntax_reference(expression_syntax(lhs_exp)));
 
/* Definitions upon non local (non dynamic) variables are always kept. */
    if(! entity_dynamic_p(lhs_ent) )
        return(false);
 
/* Gets the vertex of the dependence graph that gives all the edges of
 * which the assign statement is the source.
 */
    stmt_vertex = get_vertex_of_statement(dg, assign_stmt);
 
/* We scan all the dependences of the assign statement. If at least one
 * true dependence is found, the statement is not removed.
 */
    if(stmt_vertex != vertex_undefined)
    {
        list confs;
        dg_arc_label dal;
        succs = vertex_successors(stmt_vertex);
        for(; (succs != NIL) && (! true_dep_found) ; succs = CDR(succs))
        {
            dal = (dg_arc_label) successor_arc_label(SUCCESSOR(CAR(succs)));
            confs = dg_arc_label_conflicts(dal);
            for(; (confs != NIL) && (! true_dep_found) ; confs = CDR(confs))
                if( true_dependence_with_entity_p(CONFLICT(CAR(confs)), lhs_ent) )
                    true_dep_found = true;
        }
    }
    else
        user_warning("defs_elim_of_assign_call",
                     "Vertex of assign stmt should not be undefined\n");
 
    debug(5, "defs_elim_of_assign_call", "end ASSIGN , true dep : %s\n",
          bool_to_string(true_dep_found));
 
    return(! true_dep_found);
}

References bool_to_string(), call_arguments, call_function, CAR, CDR, CONFLICT, debug(), dg, dg_arc_label_conflicts, ENTITY_ASSIGN_P, entity_dynamic_p(), EXPRESSION, expression_syntax, get_vertex_of_statement(), instruction_call, instruction_tag, is_instruction_call, is_syntax_reference, NIL, pips_debug, pips_internal_error, reference_variable, statement_instruction, SUCCESSOR, successor_arc_label, syntax_reference, syntax_tag, true_dependence_with_entity_p(), user_warning, vertex_successors, vertex_undefined, Words_Call(), and words_to_string().

Referenced by defs_elim_of_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

defs_elim_of_statement()

bool defs_elim_of_statement	(	statement	s,
		graph	dg
	)

===========================================================================

bool defs_elim_of_statement(statement s, graph dg): returns true if "s" is to be eliminated. As we eliminate assign statements, only statement with call to the assign function may be eliminated.

Called_functions : _ make_empty_statement() : ri-util/statement.c

We scan all the statements of the block, and we build in the same time a new block where the statements to delete do not appear.

Parameters

dg

g

Definition at line 211 of file defs_elim.c.

{
    bool elim = false;
    instruction inst = statement_instruction(s);
 
    debug(4, "defs_elim_of_statement", "begin STATEMENT\n");
 
    switch(instruction_tag(inst))
    {
        /* We scan all the statements of the block, and we build in the same time
         * a new block where the statements to delete do not appear.
         */
    case is_instruction_block :
    {
        list new_block = NIL,
            block = instruction_block(inst);
        for(; block != NIL ; block = CDR(block))
        {
            statement stmt = STATEMENT(CAR(block));
            if(! defs_elim_of_statement(stmt, dg) )
                new_block = gen_nconc(new_block, CONS(STATEMENT, stmt, NIL));
        }
        instruction_block(inst) = new_block;
        break;
    }
    case is_instruction_test :
    {
        test t = instruction_test(inst);
        if( defs_elim_of_statement(test_true(t), dg) )
            test_true(t) = make_empty_statement();
        if( defs_elim_of_statement(test_false(t), dg) )
            test_false(t) = make_empty_statement();
        break;
    }
    case is_instruction_loop :
    {
        loop l = instruction_loop(inst);
        if( defs_elim_of_statement(loop_body(l), dg) )
            loop_body(l) = make_empty_statement();
        break;
    }
    case is_instruction_call : 
    {
        call c = instruction_call(inst);
 
        debug(4, "defs_elim_of_statement", "Stmt CALL: %s\n",
              entity_local_name(call_function(c)));
 
        if(ENTITY_ASSIGN_P(call_function(c)))
            elim = defs_elim_of_assign_call(s, dg);
        break;
    }
    case is_instruction_goto : break;
    case is_instruction_unstructured :
    {
        defs_elim_of_unstructured(instruction_unstructured(inst), dg);
        break;
    }
    default : pips_internal_error("Bad instruction tag");
    }
    debug(4, "defs_elim_of_statement", "end STATEMENT\n");
 
    return(elim);
}

References call_function, CAR, CDR, CONS, debug(), defs_elim_of_assign_call(), defs_elim_of_statement(), defs_elim_of_unstructured(), dg, ENTITY_ASSIGN_P, entity_local_name(), gen_nconc(), instruction_block, instruction_call, instruction_loop, instruction_tag, instruction_test, instruction_unstructured, is_instruction_block, is_instruction_call, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, loop_body, make_empty_statement, NIL, pips_internal_error, STATEMENT, statement_instruction, test_false, and test_true.

Referenced by atomizer(), defs_elim_of_statement(), and defs_elim_of_unstructured().

Here is the call graph for this function:

Here is the caller graph for this function:

defs_elim_of_unstructured()

void defs_elim_of_unstructured	(	unstructured	u,
		graph	dg
	)

===========================================================================

void defs_elim_of_unstructured(unstructured, graph dg): computes the elimination of all the definitions with no def-use dependence of an unstructured instruction.

If the statement of the control of a node of the control graph has to be eliminated, it is replaced by an empty block of statement.

Called_functions : _ make_empty_statement() : ri-util/statement.c

Parameters

dg

g

Definition at line 291 of file defs_elim.c.

{
    list blocs = NIL;
 
    debug(3, "defs_elim_of_unstructured", "begin UNSTRUCTURED\n");
 
    CONTROL_MAP(c, { bool elim = defs_elim_of_statement(control_statement(c), dg);
    if(elim) { control_statement(c) = make_empty_statement();};},
    unstructured_control( u ), blocs);
 
    gen_free_list(blocs);
 
    debug(3, "defs_elim_of_unstructured", "end UNSTRUCTURED\n");
}

References CONTROL_MAP, control_statement, debug(), defs_elim_of_statement(), dg, gen_free_list(), make_empty_statement, NIL, and unstructured_control.

Referenced by defs_elim_of_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

entity_dynamic_p()

static bool entity_dynamic_p ( entity  e )

static

===========================================================================

static bool entity_dynamic_p(entity e): returns true if "e" is a local variable, ie an entity with a storage DYNAMIC.

Called_functions : _ dynamic_area_p() : ri-util/util.c

Definition at line 114 of file defs_elim.c.

{
    ram r;
    storage s = entity_storage(e);
 
    if(storage_tag(s) != is_storage_ram)
        return(false);
    r = storage_ram(s);
    if(dynamic_area_p(ram_section(r)))
        return(true);
    return(false);
}

References dynamic_area_p(), entity_storage, is_storage_ram, ram_section, storage_ram, and storage_tag.

Referenced by defs_elim_of_assign_call().

Here is the call graph for this function:

Here is the caller graph for this function:

get_vertex_of_statement()

static vertex get_vertex_of_statement ( graph  dg, statement  stmt  )

static

– defs_elim.c

package atomizer : Alexis Platonoff, aout 91

Those functions remove the definition instructions with no def-use dependence. =========================================================================== static vertex get_vertex_of_statement(graph dg, statement stmt): returns the vertex of "dg" corresponding to "stmt".

We scan all the "dg" until we find the "vertex" with the same "ordering" as "stmt".

Definition at line 49 of file defs_elim.c.

{
    vertex rv = vertex_undefined;
    list dg_vertices = graph_vertices(dg);
    bool not_found = true;
 
    for(; (dg_vertices != NIL) && not_found ; dg_vertices = CDR(dg_vertices))
    {
        vertex v = VERTEX(CAR(dg_vertices));
        if( vertex_ordering(v) == statement_ordering(stmt) )
        {
            rv = v;
            not_found = false;
        }
    }
    return(rv);
}

References CAR, CDR, dg, graph_vertices, NIL, statement_ordering, VERTEX, vertex_ordering(), and vertex_undefined.

Referenced by defs_elim_of_assign_call().

Here is the call graph for this function:

Here is the caller graph for this function:

true_dependence_with_entity_p()

bool true_dependence_with_entity_p	(	conflict	conf,
		entity	e
	)

===========================================================================

defs_elim.c

bool true_dependence_with_entity_p(conflict conf, entity e): returns TRUE if the conflict "conf" is a true dependence upon the entity "e".

A true dependence is a conflict with a Write at the "source" and a Read at the "sink".

called functions : _ effect_entity() : ri-util/util.c _ same_entity_p() : ri-util/util.c

Parameters

conf

onf

Definition at line 82 of file defs_elim.c.

{
    effect source_eff, sink_eff;
    entity source_ent, sink_ent;
 
    source_eff = conflict_source(conf);
    sink_eff = conflict_sink(conf);
    source_ent = effect_entity(source_eff);
    sink_ent = effect_entity(sink_eff);
 
    pips_debug(6, "  CONFLICT : %s --> %s\n",
          effect_to_string(source_eff),
          effect_to_string(sink_eff));
 
    if(! same_entity_p(source_ent, sink_ent))
        pips_internal_error("Source and sink entities must be equal");
 
    return( same_entity_p(e, source_ent)                               &&
            (action_tag(effect_action(source_eff)) == is_action_write) &&
            (action_tag(effect_action(sink_eff)) == is_action_read)       );
}

References action_tag, conflict_sink, conflict_source, effect_action, effect_entity(), effect_to_string(), is_action_read, is_action_write, pips_debug, pips_internal_error, and same_entity_p().

Referenced by defs_elim_of_assign_call().

Here is the call graph for this function:

Here is the caller graph for this function: