sequence_gcm_cse.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "effects.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "text-util.h"
#include "misc.h"
#include "properties.h"
#include "resources.h"
#include "pipsdbm.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "expressions.h"
#include "eole_private.h"

Include dependency graph for sequence_gcm_cse.c:

Go to the source code of this file.

Data Structures
struct	available_scalar_t
	performs Associative-Commutative Common Subexpression Elimination on sequences. More...

Macros
#define	NO_SIMILARITY   (0)
#define	MAX_SIMILARITY   (1000)

Typedefs
typedef struct available_scalar_t *	available_scalar_pt

Functions
static bool	Is_Associative_Commutative (entity e)
static void	push_nesting (statement s)
	Keep track of statement nesting. More...
static void	pop_nesting (statement s)
	Pop the current statement from nesting list. More...
static int	current_level (void)
	The nesting depth of the current statement. More...
static bool	side_effects_p (expression e)
	There is a side effect if there is a W effect in the expression. More...
static bool	interference_on (entity var, list les)
	Compute if an effect list Some effect in les interfere with var. More...
static bool	moveable_to (list le, statement s)
	Whether sg with effects le can be moved up to s. More...
static int	level_of (list le)
	Return the level of this expression, using the current nesting list. More...
static int	expr_level_of (expression e)
	The level can be queried for a sub expression. More...
static statement	statement_of_level (int level)
	or for a statement. More...
static bool	currently_nested_p (void)
	Test if the current statement is not the top one: More...
static expression	right_side_of_assign_statement (statement stat)
static bool	entity_as_arguments (entity ent, statement stat)
	Verify if entity ent is an argument in the right expression of the assign statement stat. More...
static expression	expr_left_side_of_assign_statement (statement stat)
	Return the expression in the left side of an assign statement. More...
static entity	left_side_of_assign_statement (statement stat)
	Return the entity in left side of an assign statement. More...
static list	insertion_statement_in_correct_position (statement news, list l)
	Insert statement s in the list of statement l. More...
static void	insert_before_statement (statement news, statement s, bool last)
	Just for test static void dump_list_of_statement(list l) { fprintf(stderr, "\n===== Dump List: \n"); MAP(STATEMENT, ss, { print_statement(ss); }, l); fprintf(stderr, "\n END dumpt List!!! \n"); }. More...
static bool	atomizable_sub_expression_p (expression e)
	Atomizable if some computation. More...
static gen_array_t	group_expr_by_level (int nlevels, list le)
	of list of expressions More...
static void	do_atomize_if_different_level (expression e, int level)
	Atomize sub expressions with. More...
static void	atomize_call (call c, int level)
static void	atomize_or_associate_for_level (expression e, int level)
static bool	icm_atom_call_flt (call c)
	Don't go into I/O calls... More...
static void	atomize_instruction (instruction i)
	Atomize an instruction with call. More...
static void	atomize_test (test t)
static void	atomize_whileloop (whileloop w)
static void	atomize_or_associate (expression e)
static bool	loop_flt (loop l)
static void	loop_rwt (loop l)
static bool	number_of_use_greater_1 (statement s)
	PDSon: I use the field 'comments' of statement for counting its number of use. More...
static void	set_comment_of_statement (statement s, char *new_comment)
	Update the field 'comments' of a statement. More...
static statement	update_number_of_use (entity ent, list lst_stat, int up_down)
	Update the number of use of statement defining 'ent' which is a member of list lst_stat with step up_down (up_down = 1 | 0 | -1). More...
static void	increase_number_of_use_by_1 (entity ent, statement container)
	Increase number of use of variable ent by one. More...
static void	remove_statement_redundant (statement s, list *inserted)
	Remove statement redundant inserted before statement s. More...
static bool	cse_expression_flt (expression e, list *inserted)
static bool	cse_call_flt (call c, __attribute__((unused)) list *inserted)
	Avoid visit the left side of assign statement. More...
static void	insert_rwt (statement s)
	Insert the new statements created. More...
static bool	prepare_icm (statement s)
void	perform_icm_association (const char *name, statement s)
	Perform ICM and association on operators. More...
static void	add_ref_ent (reference r)
static void	add_call_ent (call c)
static list	get_all_entities (expression e)
static bool	try_reorder_expression_call (expression e, list availables)
static void	reorder_pointer_expression (expression e)
	make sure expressions are ordered with pointer first More...
static void	do_gather_all_expressions_perms (list sterns, list *perms)
static bool	do_gather_all_expressions (expression e, list *gathered)
static void	prune_singleton (list *l)
static bool	expr_cse_flt (expression e, __attribute__((unused)) list *skip_list)
	whether to get in here, whether to atomize... More...
static bool	expression_in_list_p (expression e, list seen)
static expression	find_equal_expression_not_in_list (expression e, list avails, list seen)
static list	common_expressions (list args, list avails)
	of expression More...
static list	list_diff (list l1, list l2)
	of expression More...
static bool	expression_eq_in_list_p (expression e, list l, expression *f)
	Define forward. More...
static int	similarity (expression e, available_scalar_pt aspt)
	Find the commun sub-expression between e & aspt. More...
static available_scalar_pt	best_similar_expression (expression e, int *best_quality)
static available_scalar_pt	make_available_scalar (entity scalar, statement container, expression contents)
static bool	call_unary_minus_p (expression e)
static void	atom_cse_expression (expression e, list *skip_list)
	Remove some inpropriate ones... More...
static bool	loop_stop (loop l, __attribute__((unused)) list *skip_list)
static bool	test_stop (test t, __attribute__((unused)) list *skip_list)
static bool	while_stop (whileloop wl, __attribute__((unused)) list *skip_list)
static bool	cse_atom_call_flt (call c, list *skip_list)
static list	atomize_cse_this_statement_expressions (statement s, list availables)
	side effects: use current_available and current_statement More...
static void	prune_non_constant (list effects, list *perms)
void	try_reorder_expressions (void *s, bool icm)
static bool	seq_flt (sequence s)
	top down. More...
static bool	call_flt (call c)
	handle all calls not in a sequence More...
void	perform_ac_cse (__attribute__((unused)) const char *name, statement s)
bool	common_subexpression_elimination (const char *module_name)
	Pipsmake phase: Common Subexpression Elimination. More...
bool	icm (const char *module_name)
	Pipsmake phase: Invariant Code Motion. More...

Variables
static char *	table_of_AC_operators []
	option: More...
static list	nesting = NIL
	assumes: More...
static list	current_available = NIL
	statement stack to current statement. More...
static statement	current_statement = statement_undefined
static list *	w_effects
	PDSon: w_effect store all the variables modified in the sequence of statement. More...
static list	seen = NIL

Macro Definition Documentation

MAX_SIMILARITY

#define MAX_SIMILARITY   (1000)

Definition at line 1317 of file sequence_gcm_cse.c.

NO_SIMILARITY

#define NO_SIMILARITY   (0)

Definition at line 1316 of file sequence_gcm_cse.c.

Typedef Documentation

available_scalar_pt

typedef struct available_scalar_t * available_scalar_pt

Function Documentation

add_call_ent()

static void add_call_ent ( call  c )

static

Definition at line 1094 of file sequence_gcm_cse.c.

{ seen = gen_once(call_function(c), seen); }

References call_function, gen_once(), and seen.

Referenced by get_all_entities().

Here is the call graph for this function:

Here is the caller graph for this function:

add_ref_ent()

static void add_ref_ent ( reference  r )

static

Definition at line 1091 of file sequence_gcm_cse.c.

{ seen = gen_once(reference_variable(r), seen); }

References gen_once(), reference_variable, and seen.

Referenced by get_all_entities().

Here is the call graph for this function:

Here is the caller graph for this function:

atom_cse_expression()

static void atom_cse_expression ( expression  e, list *  skip_list  )

static

Remove some inpropriate ones...

static void clean_current_availables(void) {

}

statement head = current_statement_head();

only left and right side of the subscript are splittable

extract every possible common subexpression

some common expression found.

identical, just make a reference to the scalar, whatever the stuff stored inside.

Set the statement to status REAL

partial common expression...

of expression

Case: in_common == aspt->contents

just substitute lo1, don't build a new aspt.

Set the statement to status REAL

now cse is a reference to the newly created scalar.

update both expressions...

in code

don't visit it later.

updates available contents

add the new scalar as an available CSE.

nothing

PDSon: Do not atomize:

• simple reference (ex: a, x)
• constant (ex: 2.6 , 5)
• Unary minus (ex: -a , -5)

create a new atom...

At fisrt, this statement is set "virtual"

don't visit it later, just in case...

???

if there are variants in the expression it cannot be moved, and it is not available. Otherwise I should move it?

exp == e == <right expression of assignment> => Atomize this expression without using temporel variable; we use the left side variable of assignment in order to reduce the number of the variable temporel for the comprehensive of the code.

Definition at line 1616 of file sequence_gcm_cse.c.

{
    pips_debug(1,"considering expression:");
    ifdebug(1) print_expression(e);
    /* statement head = current_statement_head(); */
    syntax s = expression_syntax(e);
    int quality;
    available_scalar_pt aspt;
 
    /* only left and right side of the subscript are splittable */
    if(syntax_subscript_p(s)) return;
    if(gen_find_eq(e,*skip_list)!=gen_chunk_undefined) return;
    if(gen_find_eq(e,*skip_list)!=gen_chunk_undefined) return;
 
    do { /* extract every possible common subexpression */
        aspt = best_similar_expression(e, &quality);
 
        if (aspt) /* some common expression found. */
        {
        expression unused;
        if(expression_eq_in_list_p(e, *(aspt->w_effects), &unused))
            return;
        switch (syntax_tag(s))
        {
        case is_syntax_reference:
          syntax_reference(s) = make_reference(aspt->scalar, NIL);
          increase_number_of_use_by_1(aspt->scalar, aspt->container);
          return;
        case is_syntax_call:
        {
          call c = syntax_call(s);
          if (quality==MAX_SIMILARITY)
          {
            /* identical, just make a reference to the scalar,
               whatever the stuff stored inside.
            */
 
            syntax_tag(s) = is_syntax_reference;
            syntax_reference(s) = make_reference(aspt->scalar, NIL);
 
            /* Set the statement to status REAL */
            increase_number_of_use_by_1(aspt->scalar, aspt->container);
 
            return;
          }
          else /* partial common expression... */
          {
            available_scalar_pt naspt;
            syntax sa = expression_syntax(aspt->contents);
            entity op = call_function(c), scalar;
            expression cse, cse2;
            statement scse;
            list /* of expression */ in_common, linit, lo1, lo2, old;
 
            pips_assert("AC operator",
                        Is_Associative_Commutative(op) && op==aspt->operator);
            pips_assert("contents is a call", syntax_call_p(sa));
            call ca = syntax_call(sa);
 
            linit = call_arguments(ca);
 
            /*
              there is a common part to build,
              and a CSE to substitute in both...
            */
            in_common = common_expressions(list_diff(call_arguments(c),
                                                     *(aspt->w_effects)),
                                           aspt->available_contents);
 
            /* Case: in_common == aspt->contents
             * =================================
             */
            if (gen_length(linit)==gen_length(in_common))
            {
              /* just substitute lo1, don't build a new aspt. */
              lo1 = list_diff(call_arguments(c), in_common);
              free_arguments(call_arguments(c));
              call_arguments(c) =
                gen_nconc(lo1,
                          CONS(EXPRESSION,
                               entity_to_expression(aspt->scalar), NIL));
 
              /* Set the statement to status REAL */
              increase_number_of_use_by_1(aspt->scalar, aspt->container);
            }
            else
            {
              lo1 = list_diff(call_arguments(c), in_common);
              lo2 = list_diff(linit, in_common);
 
              cse = call_to_expression(make_call(aspt->operator,
                                                 in_common));
              scse = atomize_this_expression(make_new_scalar_variable, cse);
 
              /* now cse is a reference to the newly created scalar. */
              pips_assert("a reference...",
                          syntax_reference_p(expression_syntax(cse)));
              scalar = reference_variable(syntax_reference
                                          (expression_syntax(cse)));
              cse2 = copy_expression(cse);
 
              /* update both expressions... */
              old = call_arguments(c); /* in code */
              if (gen_length(call_arguments(c))==gen_length(in_common))
              {
                expression_syntax(e) = expression_syntax(cse);
                expression_normalized(e) = expression_normalized(cse);
              }
              else
              {
                call_arguments(c) = CONS(EXPRESSION, cse, lo1);
              }
              gen_free_list(old);
 
              old = call_arguments(ca);
              call_arguments(ca) = CONS(EXPRESSION, cse2, lo2);
              gen_free_list(old);
 
              set_comment_of_statement(scse, strdup("1"));
              insert_before_statement(scse, aspt->container, false);
              increase_number_of_use_by_1(scalar, aspt->container);
 
              /* don't visit it later. */
              gen_recurse_stop(scse);
 
              /* updates available contents */
              aspt->depends = CONS(ENTITY, scalar, aspt->depends);
              old = aspt->available_contents;
              aspt->available_contents = CONS(EXPRESSION, cse,
                                              list_diff(old, in_common));
              gen_free_list(old);
 
              /* add the new scalar as an available CSE. */
              naspt = make_available_scalar(scalar,
                                            aspt->container,
                                            EXPRESSION(CAR(CDR(call_arguments(
                                                                 instruction_call(statement_instruction(scse)))))));
              current_available = CONS(STRING, (char*)naspt, current_available);
            }
          }
          break;
        }
        case is_syntax_range:
        default:
          /* nothing */
          return;
        }
        }
    } while(aspt);
 
    /* PDSon: Do not atomize:
     *   - simple reference (ex: a, x)
     *   - constant (ex: 2.6 , 5)
     *   - Unary minus (ex: -a , -5)
     */
    if (!(expression_scalar_p(e)||expression_pointer_p(e)) &&
            !expression_constant_p(e) &&
            !call_unary_minus_p(e))
    {
        expression exp = NULL;
        /*
        instruction ins = statement_instruction(current_statement);
        if (instruction_call_p(ins))
        {
            call c_assign = instruction_call(ins);
 
            if (ENTITY_ASSIGN_P(call_function(c_assign)))
            {
                exp = EXPRESSION(CAR(CDR(call_arguments(c_assign))));
            }
        }*/
 
        if (exp != e)
        {
            statement atom;
 
            /* create a new atom... */
            atom = atomize_this_expression(make_new_scalar_variable, e);
            if(atom) {
                /* At fisrt, this statement is set "virtual" */
                set_comment_of_statement(atom,strdup("1"));
                insert_before_statement(atom, current_statement, true);
 
                /* don't visit it later, just in case... */
                gen_recurse_stop(atom);
                {
                    entity scalar;
                    call ic;
                    syntax s = expression_syntax(e);
                    instruction i = statement_instruction(atom);
                    pips_assert("it is a reference", syntax_reference_p(s));
                    pips_assert("instruction is an assign",
                            instruction_call_p(i)); /* ??? */
 
                    scalar = reference_variable(syntax_reference(s));
                    ic = instruction_call(i);
 
                    /* if there are variants in the expression it cannot be moved,
                       and it is not available. Otherwise I should move it?
                       */
                    aspt = make_available_scalar(scalar,
                            current_statement,
                            EXPRESSION(CAR(CDR(call_arguments(ic)))));
 
                    current_available = CONS(STRING, (char*)aspt, current_available);
                }
            }
        }
        else 
                /* exp == e == <right expression of assignment>
              * => Atomize this expression without using temporel variable;
              *    we use the left side variable of assignment in order to reduce
              *    the number of the variable temporel for the comprehensive of
              *    the code.
              */
        {
            entity scalar = left_side_of_assign_statement(current_statement);
            if(!entity_undefined_p(scalar))
            {
                expression rhs;
                statement assign;
                syntax ref;
 
                rhs = make_expression(expression_syntax(e), normalized_undefined);
                normalize_all_expressions_of(rhs);
 
                ref = make_syntax(is_syntax_reference, make_reference(scalar, NIL));
 
                assign = make_assign_statement(make_expression(copy_syntax(ref),
                            normalized_undefined),
                        rhs);
                expression_syntax(e) = ref;
 
                set_comment_of_statement(assign,strdup("1"));
                insert_before_statement(assign, current_statement, true);
 
                aspt = make_available_scalar(scalar, current_statement, rhs);
                current_available = CONS(STRING, (char*)aspt, current_available);
            }
        }
    }
}

References atomize_this_expression(), available_scalar_t::available_contents, best_similar_expression(), call_arguments, call_function, call_to_expression(), call_unary_minus_p(), CAR, CDR, common_expressions(), CONS, available_scalar_t::container, available_scalar_t::contents, copy_expression(), copy_syntax(), current_available, current_statement, available_scalar_t::depends, ENTITY, entity_to_expression(), entity_undefined_p, exp, EXPRESSION, expression_constant_p(), expression_eq_in_list_p(), expression_normalized, expression_pointer_p(), expression_scalar_p, expression_syntax, free_arguments(), gen_chunk_undefined, gen_find_eq(), gen_free_list(), gen_length(), gen_nconc(), gen_recurse_stop(), ifdebug, increase_number_of_use_by_1(), insert_before_statement(), instruction_call, instruction_call_p, Is_Associative_Commutative(), is_syntax_call, is_syntax_range, is_syntax_reference, left_side_of_assign_statement(), list_diff(), make_assign_statement(), make_available_scalar(), make_call(), make_expression(), make_new_scalar_variable(), make_reference(), make_syntax(), MAX_SIMILARITY, NIL, normalize_all_expressions_of(), normalized_undefined, available_scalar_t::operator, pips_assert, pips_debug, print_expression(), ref, reference_variable, available_scalar_t::scalar, set_comment_of_statement(), statement_instruction, strdup(), STRING, syntax_call, syntax_call_p, syntax_reference, syntax_reference_p, syntax_subscript_p, syntax_tag, and available_scalar_t::w_effects.

Referenced by atomize_cse_this_statement_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

atomizable_sub_expression_p()

static bool atomizable_sub_expression_p ( expression  e )

static

Atomizable if some computation.

Missing cases? user functions? I/O?

Definition at line 421 of file sequence_gcm_cse.c.

{
  syntax s = expression_syntax(e);
  switch (syntax_tag(s))
  {
  case is_syntax_range:
  case is_syntax_reference:
    return false;
  case is_syntax_call:
    {
      entity called = call_function(syntax_call(s));
      /* Missing cases? user functions? I/O? */
      return !entity_constant_p(called) && !ENTITY_IMPLIEDDO_P(called);
    }
  default:
    pips_internal_error("unexpected syntax tag: %d", syntax_tag(s));
    return false;
  }
}

References call_function, entity_constant_p, ENTITY_IMPLIEDDO_P, expression_syntax, is_syntax_call, is_syntax_range, is_syntax_reference, pips_internal_error, syntax_call, and syntax_tag.

Referenced by do_atomize_if_different_level().

Here is the caller graph for this function:

atomize_call()

static void atomize_call ( call  c, int  level  )

static

of expression

Definition at line 550 of file sequence_gcm_cse.c.

{
  list /* of expression */ args;
  int lenargs;
 
  args = call_arguments(c);
  lenargs = gen_length(args);
 
  if (lenargs>=2)
  {
    FOREACH(EXPRESSION, sube, args)
        do_atomize_if_different_level(sube, level);
  }
}

References call_arguments, do_atomize_if_different_level(), EXPRESSION, FOREACH, gen_length(), and level.

Referenced by atomize_instruction(), and atomize_or_associate_for_level().

Here is the call graph for this function:

Here is the caller graph for this function:

atomize_cse_this_statement_expressions()

static list atomize_cse_this_statement_expressions ( statement  s, list  availables  )

static

side effects: use current_available and current_statement

of available_scalar_pt

scan expressions in s; atomize/cse them; update availables;

statement_domain, current_statement_filter, current_statement_rewrite,

don't go inside these...

do the job on the found expression.

free_current_statement_stack();

Update w_effects: add the variable modified by the current statement

Update contents

Update address: w_effects always points to the end of the list of variable modified which is filled after each statement

Definition at line 1907 of file sequence_gcm_cse.c.

{
  current_available = availables;
  current_statement = s;
  list skip_list = NIL;
 
  /* scan expressions in s;
     atomize/cse them;
     update availables;
  */
  gen_context_multi_recurse(s,&skip_list,
                    /* statement_domain, current_statement_filter,
                       current_statement_rewrite, */
 
                    /* don't go inside these... */
                    loop_domain, loop_stop, gen_null,
                    test_domain, test_stop, gen_null,
                    unstructured_domain, gen_false, gen_null,
                    whileloop_domain, while_stop, gen_null,
 
                    /* . */
                    call_domain, cse_atom_call_flt, gen_null,
 
                    /* do the job on the found expression. */
                    expression_domain, expr_cse_flt, atom_cse_expression,
                    NULL);
  gen_free_list(skip_list);
 
  /* free_current_statement_stack(); */
  availables = current_available;
 
  current_statement = statement_undefined;
  current_available = NIL;
 
  /* Update w_effects: add the variable modified by the current statement */
  if (assignment_statement_p(s))
  {
    /* Update contents */
    expression var_defined =
      copy_expression(expr_left_side_of_assign_statement(s));
    *w_effects = CONS(EXPRESSION, var_defined, NIL);
 
    /* Update address: w_effects always points to the end of the list of
     * variable modified which is filled after each statement
     */
    w_effects = &CDR(*w_effects);
  }
 
  return availables;
}

References assignment_statement_p(), atom_cse_expression(), call_domain, CDR, CONS, copy_expression(), cse_atom_call_flt(), current_available, current_statement, expr_cse_flt(), expr_left_side_of_assign_statement(), EXPRESSION, expression_domain, gen_context_multi_recurse(), gen_false(), gen_free_list(), gen_null(), loop_domain, loop_stop(), NIL, statement_undefined, test_domain, test_stop(), unstructured_domain, w_effects, while_stop(), and whileloop_domain.

Referenced by call_flt(), and seq_flt().

Here is the call graph for this function:

Here is the caller graph for this function:

atomize_instruction()

static void atomize_instruction ( instruction  i )

static

Atomize an instruction with call.

Maybe I could consider moving the call as a whole?

Since we are at the top level statement, impossible to move something outside...

Should have been dealt by other means in the gen_multi_recurse() from gen_multi_recurse() before

stat_level_of(current_statement_head()));

Definition at line 668 of file sequence_gcm_cse.c.

{
  if (!currently_nested_p())
    /* Since we are at the top level statement, impossible to move
       something outside... */
    return;
 
  if (!instruction_call_p(i))
    /* Should have been dealt by other means in the gen_multi_recurse()
       from gen_multi_recurse() before */
    return;
 
  /* stat_level_of(current_statement_head())); */
  atomize_call(instruction_call(i), current_level());
}

References atomize_call(), current_level(), currently_nested_p(), instruction_call, and instruction_call_p.

Referenced by perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

atomize_or_associate()

static void atomize_or_associate ( expression  e )

static

Definition at line 696 of file sequence_gcm_cse.c.

{
  atomize_or_associate_for_level(e, expr_level_of(e));
}

References atomize_or_associate_for_level(), and expr_level_of().

Referenced by perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

atomize_or_associate_for_level()

static void atomize_or_associate_for_level ( expression  e, int  level  )

static

of expression

Some depth, otherwise no ICM needed! should be fixed if root statement is pushed?

skip casts

Only do something with calls

something to icm

Reassociation + atomization maybe needed. code taken from JZ.

Note: the last level of an expression MUST NOT be moved! indeed, there may be a side effects in another part of the expr.

Insert expression in upward expression, eventually in e!

Fix last level if necessary.

Definition at line 566 of file sequence_gcm_cse.c.

{
  syntax syn;
  call c;
  entity func;
  list /* of expression */ args;
  int lenargs;
 
  /* Some depth, otherwise no ICM needed!
   * should be fixed if root statement is pushed?
   */
  if (!currently_nested_p()) return;
 
 
  syn = expression_syntax(e);
 
  /* skip casts */
  if(syntax_cast_p(syn)) return atomize_or_associate_for_level(cast_expression(syntax_cast(syn)),level);
 
  /* Only do something with calls */
  if (!syntax_call_p(syn))
    return;
 
  pips_debug(1,"considering expression %s\n",expression_to_string(e));
 
  /* something to icm
   */
  c = syntax_call(syn);
  func = call_function(c);
  args = call_arguments(c);
  lenargs = gen_length(args);
 
  if (Is_Associative_Commutative(func) && lenargs>2)
  {
    /* Reassociation + atomization maybe needed.
     * code taken from JZ.
     */
      int i, nlevels = current_level();
      gen_array_t groups = group_expr_by_level(nlevels, args);
      list lenl;
 
      /* Note: the last level of an expression MUST NOT be moved!
       * indeed, there may be a side effects in another part of the expr.
       */
      for (i=0; i<nlevels; i++)
      {
        list lei = (list) gen_array_item(groups, i);
        if (lei!=list_undefined)
        {
          int j;
          bool satom_inserted = false;
          syntax satom = make_syntax_call(make_call(func, lei));
          expression eatom = expression_undefined;
          statement atom;
 
          /* Insert expression in upward expression, eventually in e!
           */
          for (j=i+1; j<=nlevels && !satom_inserted; j++)
          {
            list lej = (list) gen_array_item(groups, j);
            if (lej!=list_undefined)
            {
              eatom = make_expression(satom, normalized_undefined);
              lej = CONS(EXPRESSION, eatom, lej);
              gen_array_addto(groups, j, lej);
              satom_inserted = true;
            }
          }
          if (!satom_inserted)
          {
            expression_syntax(e) = satom;
            eatom = e;
          }
 
          atom = atomize_this_expression(make_new_scalar_variable, eatom);
          insert_before_statement(atom, statement_of_level(i), true);
        }
      }
 
      /* Fix last level if necessary.
       */
      lenl = (list) gen_array_item(groups, nlevels);
      if (lenl != list_undefined)
        call_arguments(c) = lenl;
  }
  else
  {
    atomize_call(c, level);
  }
}

References atomize_call(), atomize_this_expression(), call_arguments, call_function, cast_expression, CONS, current_level(), currently_nested_p(), EXPRESSION, expression_syntax, expression_to_string(), expression_undefined, gen_array_addto(), gen_array_item(), gen_length(), group_expr_by_level(), insert_before_statement(), Is_Associative_Commutative(), level, list_undefined, make_call(), make_expression(), make_new_scalar_variable(), make_syntax_call(), normalized_undefined, pips_debug, statement_of_level(), syntax_call, syntax_call_p, syntax_cast, and syntax_cast_p.

Referenced by atomize_or_associate().

Here is the call graph for this function:

Here is the caller graph for this function:

atomize_test()

static void atomize_test ( test  t )

static

Definition at line 684 of file sequence_gcm_cse.c.

{
  if (!currently_nested_p()) return;
  do_atomize_if_different_level(test_condition(t), current_level());
}

References current_level(), currently_nested_p(), do_atomize_if_different_level(), and test_condition.

Referenced by perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

atomize_whileloop()

static void atomize_whileloop ( whileloop  w )

static

Definition at line 690 of file sequence_gcm_cse.c.

{
  if (!currently_nested_p()) return;
  do_atomize_if_different_level(whileloop_condition(w), current_level());
}

References current_level(), currently_nested_p(), do_atomize_if_different_level(), and whileloop_condition.

Referenced by perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

best_similar_expression()

static available_scalar_pt best_similar_expression ( expression  e, int *  best_quality  )

static

Definition at line 1497 of file sequence_gcm_cse.c.

{
    available_scalar_pt best = NULL;
    (*best_quality) = 0;
 
    FOREACH(STRING,caspt,current_available)
    {
        available_scalar_pt aspt = (available_scalar_pt) caspt;
        int quality = similarity(e, aspt);
        if (quality==MAX_SIMILARITY)
        {
            (*best_quality) = quality;
            return aspt;
        }
        if (quality>0 && (*best_quality)<quality)
        {
            best = aspt;
            (*best_quality) = quality;
        }
    }
 
    return best;
}

References current_available, FOREACH, MAX_SIMILARITY, similarity(), and STRING.

Referenced by atom_cse_expression().

Here is the call graph for this function:

Here is the caller graph for this function:

call_flt()

static bool call_flt ( call  c )

static

handle all calls not in a sequence

Definition at line 2022 of file sequence_gcm_cse.c.

{
    statement parent = (statement)gen_get_ancestor(statement_domain,c);
    pips_debug(1,"considering statement:\n");
    ifdebug(1) { print_statement(parent); }
    list availables = NIL;
    list *top_of_w_effects = w_effects = &CDR(gen_cons(NIL,NIL));
    availables = atomize_cse_this_statement_expressions(parent,availables);
    gen_full_free_list(*top_of_w_effects);
    return true;
}

References atomize_cse_this_statement_expressions(), CDR, gen_cons(), gen_full_free_list(), gen_get_ancestor(), ifdebug, NIL, pips_debug, print_statement(), statement_domain, and w_effects.

Referenced by perform_ac_cse().

Here is the call graph for this function:

Here is the caller graph for this function:

call_unary_minus_p()

static bool call_unary_minus_p ( expression  e )

static

Definition at line 1598 of file sequence_gcm_cse.c.

{
  syntax s = expression_syntax(e);
  if(syntax_call_p(s))
  {
    call c = syntax_call(s);
    return ENTITY_UNARY_MINUS_P(call_function(c));
  }
  return false;
}

References call_function, ENTITY_UNARY_MINUS_P, expression_syntax, syntax_call, and syntax_call_p.

Referenced by atom_cse_expression().

Here is the caller graph for this function:

common_expressions()

static list common_expressions ( list  args, list  avails  )

static

of expression

Definition at line 1373 of file sequence_gcm_cse.c.

{
  list already_seen = NIL;
 
  FOREACH(EXPRESSION, e, args)
  {
    expression n = find_equal_expression_not_in_list(e, avails, already_seen);
    if (n) already_seen = CONS(EXPRESSION, n, already_seen);
  }
 
  return already_seen;
}

References CONS, EXPRESSION, find_equal_expression_not_in_list(), FOREACH, and NIL.

Referenced by atom_cse_expression(), and similarity().

Here is the call graph for this function:

Here is the caller graph for this function:

common_subexpression_elimination()

bool common_subexpression_elimination

(

const char *

module_name

)

Pipsmake phase: Common Subexpression Elimination.

Parameters

[in]

module_name

is the name of the module we want to apply the Common Subexpression Elimination on

Returns

true if everything goes fine.

Parameters

module_name

odule_name

Definition at line 2075 of file sequence_gcm_cse.c.

{
  bool   result;
  const char* os = get_string_property("EOLE_OPTIMIZATION_STRATEGY");
 
  // Optimize expressions with "CSE" optimization strategy
  set_string_property("EOLE_OPTIMIZATION_STRATEGY", "CSE");
  result = optimize_expressions(module_name);
 
  // Restore original optimization strategy
  set_string_property("EOLE_OPTIMIZATION_STRATEGY", os);
 
  return result;
}

References get_string_property(), module_name(), optimize_expressions(), and set_string_property().

Here is the call graph for this function:

cse_atom_call_flt()

static bool cse_atom_call_flt ( call  c, list *  skip_list  )

static

should avoid any W effect...

Update address: w_effects always points to the end of the list of variable modified which is filled after each statement

Definition at line 1879 of file sequence_gcm_cse.c.

{
  entity called = call_function(c);
 
  /* should avoid any W effect... */
  if (ENTITY_ASSIGN_P(called))
  {
      expression lhs = binary_call_lhs(c);
      if(get_bool_property("COMMON_SUBEXPRESSION_ELIMINATION_SKIP_LHS")) gen_recurse_stop(lhs);
      else if(!syntax_subscript_p(expression_syntax(lhs)))
      {
          *skip_list=CONS(EXPRESSION,lhs,*skip_list);
          expression var_defined =
              copy_expression(lhs);
          *w_effects = CONS(EXPRESSION, var_defined, NIL);
 
          /* Update address: w_effects always points to the end of the list of
           * variable modified which is filled after each statement
           */
          w_effects = &CDR(*w_effects);
      }
  }
  return !(io_intrinsic_p(called) || ENTITY_IMPLIEDDO_P(called));
}

References binary_call_lhs, call_function, CDR, CONS, copy_expression(), ENTITY_ASSIGN_P, ENTITY_IMPLIEDDO_P, EXPRESSION, expression_syntax, gen_recurse_stop(), get_bool_property(), io_intrinsic_p(), NIL, syntax_subscript_p, and w_effects.

Referenced by atomize_cse_this_statement_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

cse_call_flt()

static bool cse_call_flt ( call  c, __attribute__((unused)) list *  inserted  )

static

Avoid visit the left side of assign statement.

Go down!

Definition at line 931 of file sequence_gcm_cse.c.

{
  if(ENTITY_ASSIGN_P(call_function(c)))
  {
      expression lhs = binary_call_lhs(c);
      if(get_bool_property("COMMON_SUBEXPRESSION_ELIMINATION_SKIP_LHS") || expression_scalar_p(lhs) || expression_pointer_p(lhs) )
          gen_recurse_stop(lhs);
  }
  /* Go down! */
  return true;
}

References binary_call_lhs, call_function, ENTITY_ASSIGN_P, expression_pointer_p(), expression_scalar_p, gen_recurse_stop(), and get_bool_property().

Referenced by remove_statement_redundant().

Here is the call graph for this function:

Here is the caller graph for this function:

cse_expression_flt()

static bool cse_expression_flt ( expression  e, list *  inserted  )

static

Go down

This statement is a real one. But it maybe contains a variable temporal -> Continue remove redundant statement from this one

Remove its comment for pretty look: It is visited! Not do again!

Go up

This statement is already visited! Not do again! Go up

s is a redundant statement. Replace e by the right side of the assign statement s

Remove s from list

Continue go down the new expression

Nothing is done! Go up

Definition at line 865 of file sequence_gcm_cse.c.

{
    pips_debug(2,"examining expression:");
    ifdebug(2) { print_expression(e); }
  entity scala;
 
  if(!syntax_reference_p(expression_syntax(e)))
  {
    /* Go down  */
    return true;
  }
 
  scala = reference_variable(syntax_reference(expression_syntax(e)));
  FOREACH(STATEMENT, s,*inserted)
  {
      entity ent = left_side_of_assign_statement(s);
      if (scala == ent)
      {
          if (number_of_use_greater_1(s))
          {
              /* This statement is a real one. But it maybe contains a variable
               * temporal -> Continue remove redundant statement from this one
               */
              remove_statement_redundant(s, inserted);
 
              /* Remove its comment for pretty look: It is visited! Not do again! */
              set_comment_of_statement(s, string_undefined);
 
              /* Go up */
              return false;
          }
          else if (string_undefined_p(statement_comments(s)))
          {
              /* This statement is already visited! Not do again! Go up */
              return false;
          }
          else
          {
              pips_debug(1,"redundant statement purged:\n");
              ifdebug(1) { print_statement(s); }
              /* s is a redundant statement. Replace e by the right side of
               * the assign statement s
               */
              expression exp = right_side_of_assign_statement(s);
              expression_syntax(e) = expression_syntax(exp);
              expression_syntax(exp) = NULL;
 
              /* Remove s from list
              */
              gen_remove_once(inserted, s);
 
              free_statement(s);
 
              /* Continue go down the new expression */
              return true;
          }
      }
  }
 
  /* Nothing is done! Go up */
  return false;
}

References exp, expression_syntax, FOREACH, free_statement(), gen_remove_once(), ifdebug, left_side_of_assign_statement(), number_of_use_greater_1(), pips_debug, print_expression(), print_statement(), reference_variable, remove_statement_redundant(), right_side_of_assign_statement(), set_comment_of_statement(), STATEMENT, statement_comments, string_undefined, string_undefined_p, syntax_reference, and syntax_reference_p.

Referenced by remove_statement_redundant().

Here is the call graph for this function:

Here is the caller graph for this function:

current_level()

static int current_level ( void  )

static

The nesting depth of the current statement.

Definition at line 145 of file sequence_gcm_cse.c.

{
  return gen_length(nesting);
}

References gen_length(), and nesting.

Referenced by atomize_instruction(), atomize_or_associate_for_level(), atomize_test(), atomize_whileloop(), currently_nested_p(), loop_rwt(), and statement_of_level().

Here is the call graph for this function:

Here is the caller graph for this function:

currently_nested_p()

static bool currently_nested_p ( void  )

static

Test if the current statement is not the top one:

Definition at line 274 of file sequence_gcm_cse.c.

{
#if defined(PUSH_BODY)
  return current_level()>1;
#else
  return current_level()>0;
#endif
}

References current_level().

Referenced by atomize_instruction(), atomize_or_associate_for_level(), atomize_test(), atomize_whileloop(), and loop_rwt().

Here is the call graph for this function:

Here is the caller graph for this function:

do_atomize_if_different_level()

static void do_atomize_if_different_level ( expression  e, int  level  )

static

Atomize sub expressions with.

• lower level
• not simple (references or constants)
• no side effects.

Definition at line 530 of file sequence_gcm_cse.c.

{
    int elevel = expr_level_of(e);
 
    pips_debug(1,"considering expression %s\n",expression_to_string(e));
    if (elevel!=-1 &&
            elevel<level &&
            atomizable_sub_expression_p(e) &&
            !side_effects_p(e))
    {
        pips_debug(1,"atomize \n");
        statement atom = atomize_this_expression(make_new_scalar_variable, e);
        if (atom)
            insert_before_statement(atom, statement_of_level(elevel), true);
    }
    else
        pips_debug(1,"not atomize\n");
}

References atomizable_sub_expression_p(), atomize_this_expression(), expr_level_of(), expression_to_string(), insert_before_statement(), level, make_new_scalar_variable(), pips_debug, side_effects_p(), and statement_of_level().

Referenced by atomize_call(), atomize_test(), atomize_whileloop(), and loop_rwt().

Here is the call graph for this function:

Here is the caller graph for this function:

do_gather_all_expressions()

static bool do_gather_all_expressions ( expression  e, list *  gathered  )

static

Definition at line 1259 of file sequence_gcm_cse.c.

                                                                     {
    NORMALIZE_EXPRESSION(e);
    normalized n = expression_normalized(e);
    if(normalized_linear_p(n)) {
        Pvecteur pv = normalized_linear(n);
        list sterns=NIL;
        for(Pvecteur ipv = pv; !VECTEUR_NUL_P(ipv) ; ipv=vecteur_succ(ipv)) {
            expression stern = int_to_expression(vecteur_val(ipv));
            if(TCST != vecteur_var(ipv)) {
                stern = make_op_exp(MULTIPLY_OPERATOR_NAME,
                    stern,
                    entity_to_expression(vecteur_var(ipv)));
            }
            sterns=CONS(EXPRESSION,stern,sterns);
        }
        list perms = NIL;
        do_gather_all_expressions_perms(sterns,&perms);
        *gathered=gen_nconc(*gathered,perms);
        return false;
    }
    return true;
}

References CONS, do_gather_all_expressions_perms(), entity_to_expression(), EXPRESSION, expression_normalized, gen_nconc(), int_to_expression(), make_op_exp(), MULTIPLY_OPERATOR_NAME, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, TCST, VECTEUR_NUL_P, vecteur_succ, vecteur_val, and vecteur_var.

Referenced by try_reorder_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

do_gather_all_expressions_perms()

static void do_gather_all_expressions_perms ( list  sterns, list *  perms  )

static

Definition at line 1236 of file sequence_gcm_cse.c.

                                                                      {
    if(ENDP(sterns)) *perms=NIL;
    else {
        expression head = EXPRESSION(CAR(sterns));
        unnormalize_expression(head);
        NORMALIZE_EXPRESSION(head);
        POP(sterns);
        *perms = CONS(EXPRESSION,copy_expression(head),*perms);
        list nperms = NIL;
        do_gather_all_expressions_perms(sterns,&nperms);
        FOREACH(EXPRESSION,exp,nperms) {
            NORMALIZE_EXPRESSION(exp);
            Pvecteur pv = vect_add(normalized_linear(expression_normalized(exp)),
                    normalized_linear(expression_normalized(head)));
            expression epv = Pvecteur_to_expression(pv);
            reorder_pointer_expression(epv);
            convert_to_c_operators(epv);
            *perms=CONS(EXPRESSION,epv,*perms);
        }
        *perms=gen_nconc(*perms,nperms);
    }
}

References CAR, CONS, convert_to_c_operators(), copy_expression(), ENDP, exp, EXPRESSION, expression_normalized, FOREACH, gen_nconc(), NIL, NORMALIZE_EXPRESSION, normalized_linear, POP, Pvecteur_to_expression(), reorder_pointer_expression(), unnormalize_expression(), and vect_add().

Referenced by do_gather_all_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

entity_as_arguments()

static bool entity_as_arguments ( entity  ent, statement  stat  )

static

Verify if entity ent is an argument in the right expression of the assign statement stat.

Argument is maybe a call to a constant

Definition at line 305 of file sequence_gcm_cse.c.

{
  expression right_side;
  call right_call;
 
  right_side = right_side_of_assign_statement(stat);
 
  pips_assert("Right expression is a call!",
              syntax_call_p(expression_syntax(right_side)));
  right_call = syntax_call(expression_syntax(right_side));
 
  FOREACH(EXPRESSION, e,call_arguments(right_call))
  {
      syntax s = expression_syntax(e);
      /* Argument is maybe a call to a constant */
      if (syntax_reference_p(s) &&
              ent == reference_variable(syntax_reference(s)))
      {
          return true;
      }
  }
 
  return false;
}

References call_arguments, EXPRESSION, expression_syntax, FOREACH, pips_assert, reference_variable, right_side_of_assign_statement(), syntax_call, syntax_call_p, syntax_reference, and syntax_reference_p.

Referenced by insertion_statement_in_correct_position().

Here is the call graph for this function:

Here is the caller graph for this function:

expr_cse_flt()

static bool expr_cse_flt ( expression  e, __attribute__((unused)) list *  skip_list  )

static

whether to get in here, whether to atomize...

Definition at line 1297 of file sequence_gcm_cse.c.

{
    pips_debug(2,"considering expression:");
    ifdebug(2) print_expression(e);
    syntax s = expression_syntax(e);
    switch (syntax_tag(s))
    {
        case is_syntax_call:
             return !IO_CALL_P(expression_call(e));
        case is_syntax_reference:
            //return entity_scalar_p(reference_variable(syntax_reference(s)));
        case is_syntax_subscript:
        case is_syntax_cast:
            return true;
        default:
            return false;
    }
}

References expression_call(), expression_syntax, ifdebug, IO_CALL_P, is_syntax_call, is_syntax_cast, is_syntax_reference, is_syntax_subscript, pips_debug, print_expression(), and syntax_tag.

Referenced by atomize_cse_this_statement_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

expr_left_side_of_assign_statement()

static expression expr_left_side_of_assign_statement ( statement  stat )

static

Return the expression in the left side of an assign statement.

Definition at line 332 of file sequence_gcm_cse.c.

{
  if (assignment_statement_p(stat))
  {
    call assign = instruction_call(statement_instruction(stat));
    return EXPRESSION(CAR(call_arguments(assign)));
  }
 
  pips_internal_error("It is not an assign statement !");
 
  return NULL;
}

References assignment_statement_p(), call_arguments, CAR, EXPRESSION, instruction_call, pips_internal_error, and statement_instruction.

Referenced by atomize_cse_this_statement_expressions(), and left_side_of_assign_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

expr_level_of()

static int expr_level_of ( expression  e )

static

The level can be queried for a sub expression.

try again !

assigns...

Definition at line 225 of file sequence_gcm_cse.c.

{
  list le;
  if (!bound_expr_prw_effects_p(e)) {
      /* try again ! */
      le = proper_effects_of_expression(e);
      bool writes = false;
      FOREACH(EFFECT,eff,le) {
          if((writes=effect_write_p(eff))) break;
      }
      if(writes)
          return -1; /* assigns... */
      else {
          int res = level_of(le);
          gen_full_free_list(le);
          return res;
      }
  }
  else {
      le = effects_effects(load_expr_prw_effects(e));
      return level_of(le);
  }
}

References bound_expr_prw_effects_p(), EFFECT, effect_write_p, effects_effects, FOREACH, gen_full_free_list(), level_of(), load_expr_prw_effects(), and proper_effects_of_expression().

Referenced by atomize_or_associate(), do_atomize_if_different_level(), and group_expr_by_level().

Here is the call graph for this function:

Here is the caller graph for this function:

expression_eq_in_list_p()

static bool expression_eq_in_list_p ( expression  e, list  l, expression *  f  )

static

Define forward.

Define forward

Definition at line 1558 of file sequence_gcm_cse.c.

{
  FOREACH(EXPRESSION, et,l)
  {
    if (expression_equal_p(e, et))
    {
      *f = et;
      return true;
    }
  }
 
  return false;
}

References EXPRESSION, expression_equal_p(), f(), and FOREACH.

Referenced by atom_cse_expression(), list_diff(), and similarity().

Here is the call graph for this function:

Here is the caller graph for this function:

expression_in_list_p()

static bool expression_in_list_p ( expression  e, list  seen  )

static

Definition at line 1358 of file sequence_gcm_cse.c.

{
  MAP(EXPRESSION, f, if (e==f) return true, seen);
  return false;
}

References EXPRESSION, f(), MAP, and seen.

Referenced by find_equal_expression_not_in_list().

Here is the call graph for this function:

Here is the caller graph for this function:

find_equal_expression_not_in_list()

static expression find_equal_expression_not_in_list ( expression  e, list  avails, list  seen  )

static

Definition at line 1364 of file sequence_gcm_cse.c.

{
  FOREACH(EXPRESSION, f,avails)
      if (expression_equal_p(e, f) && !expression_in_list_p(f, seen))
        return f;
  return NULL;
}

References EXPRESSION, expression_equal_p(), expression_in_list_p(), f(), FOREACH, and seen.

Referenced by common_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

get_all_entities()

static list get_all_entities ( expression  e )

static

Definition at line 1097 of file sequence_gcm_cse.c.

{
  list result;
  seen = NIL;
 
  gen_multi_recurse(e,
                    reference_domain, gen_true, add_ref_ent,
                    call_domain, gen_true, add_call_ent,
                    NULL);
 
  result = seen;
  seen = NIL;
  return result;
}

References add_call_ent(), add_ref_ent(), call_domain, gen_multi_recurse(), gen_true(), NIL, reference_domain, and seen.

Referenced by make_available_scalar().

Here is the call graph for this function:

Here is the caller graph for this function:

group_expr_by_level()

static gen_array_t group_expr_by_level ( int  nlevels, list  le  )

static

of list of expressions

initialize chunks.

put expressions in chunks.

Fix expressions by useful levels, with some operations.

Definition at line 442 of file sequence_gcm_cse.c.

{
  gen_array_t result = gen_array_make(nlevels+1);
  int i;
  bool first_alone;
 
  /* initialize chunks. */
  for (i=0; i<=nlevels; i++)
    gen_array_addto(result, i, list_undefined);
 
  /* put expressions in chunks. */
  FOREACH(EXPRESSION, e,le)
  {
      int elevel = expr_level_of(e);
      list eatlevel;
      pips_assert("coherent level", elevel>=0 && elevel<=nlevels);
 
      if (side_effects_p(e))
      {
          elevel = nlevels;
      }
 
      eatlevel = (list) gen_array_item(result, elevel);
      if (eatlevel == list_undefined)
      {
          eatlevel = CONS(EXPRESSION, e, NIL);
      }
      else
      {
          eatlevel = CONS(EXPRESSION, e, eatlevel);
      }
      gen_array_addto(result, elevel, eatlevel);
  }
 
  /* Fix expressions by useful levels, with some operations.
   */
  first_alone = true;
  for (i=0; i<nlevels && first_alone; i++)
  {
    list lei = (list) gen_array_item(result, i);
    if (lei != list_undefined)
    {
      int lenlei = gen_length(lei);
      if (lenlei == 1)
      {
        list next = (list) gen_array_item(result, i+1);
        if (next == list_undefined)
          next = lei;
        else
          next = gen_nconc(next, lei);
        gen_array_addto(result, i+1, next);
        gen_array_addto(result, i, list_undefined);
      }
      else
        first_alone = false;
    }
  }
 
  return result;
}

References CONS, expr_level_of(), EXPRESSION, FOREACH, gen_array_addto(), gen_array_item(), gen_array_make(), gen_length(), gen_nconc(), list_undefined, NIL, pips_assert, and side_effects_p().

Referenced by atomize_or_associate_for_level().

Here is the call graph for this function:

Here is the caller graph for this function:

icm()

bool icm

(

const char *

module_name

)

Pipsmake phase: Invariant Code Motion.

Parameters

[in]

module_name

is the name of the module we want to apply the Invariant Code Motion on

Returns

true if everything goes file.

Beware, invariant_code_motion phase already exists too but deal with loop invariant code motion...

Parameters

module_name

odule_name

Definition at line 2101 of file sequence_gcm_cse.c.

{
  bool   result;
  const char* os = get_string_property("EOLE_OPTIMIZATION_STRATEGY");
 
  // Optimize expressions with "ICM" optimization strategy
  set_string_property("EOLE_OPTIMIZATION_STRATEGY", "ICM");
  result = optimize_expressions(module_name);
 
  // Restore original optimization strategy
  set_string_property("EOLE_OPTIMIZATION_STRATEGY", os);
 
  return result;
}

References get_string_property(), module_name(), optimize_expressions(), and set_string_property().

Referenced by try_reorder_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

icm_atom_call_flt()

static bool icm_atom_call_flt ( call  c )

static

Don't go into I/O calls...

Definition at line 658 of file sequence_gcm_cse.c.

{
  entity called = call_function(c);
  return !(io_intrinsic_p(called) || ENTITY_IMPLIEDDO_P(called));
}

References call_function, ENTITY_IMPLIEDDO_P, and io_intrinsic_p().

Referenced by perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

increase_number_of_use_by_1()

static void increase_number_of_use_by_1 ( entity  ent, statement  container  )

static

Increase number of use of variable ent by one.

Reduce by 1 number of use of variables contained by statement Updated

Definition at line 813 of file sequence_gcm_cse.c.

{
    if (bound_inserted_p(container))
    {
        statement updated, sblock = load_inserted(container);
        instruction i = statement_instruction(sblock);
        sequence seq;
        int step;
        pips_assert("it is a sequence", instruction_sequence_p(i)&&entity_empty_label_p(statement_label(sblock)));
 
        seq = instruction_sequence(i);
 
        step = +1;
        if(assignment_statement_p(container))
        {
            if (ent == left_side_of_assign_statement(container))
            {
                step = 0;
            }
        }
 
        if (!(updated = update_number_of_use(ent, sequence_statements(seq), step)))
        {
            pips_internal_error("No statement defines '%s'", entity_name(ent));
        }
 
        /* Reduce by 1 number of use of variables contained by statement Updated */
        {
            expression exp = right_side_of_assign_statement(updated);
            if (syntax_call_p(expression_syntax(exp)))
            {
                list args = call_arguments(syntax_call(expression_syntax(exp)));
                FOREACH(EXPRESSION, arg,args)
                {
                    syntax syn = expression_syntax(arg);
                    if(syntax_reference_p(syn))
                    {
                        entity en = reference_variable(syntax_reference(syn));
                        update_number_of_use(en, sequence_statements(seq), -1);
                    }
                }
            }
        }
    }
    else
    {
        pips_internal_error("No statement inserted!");
    }
}

References assignment_statement_p(), call_arguments, entity_empty_label_p(), entity_name, exp, EXPRESSION, expression_syntax, FOREACH, instruction_sequence, instruction_sequence_p, left_side_of_assign_statement(), pips_assert, pips_internal_error, reference_variable, right_side_of_assign_statement(), sequence_statements, statement_instruction, statement_label, syntax_call, syntax_call_p, syntax_reference, syntax_reference_p, and update_number_of_use().

Referenced by atom_cse_expression().

Here is the call graph for this function:

Here is the caller graph for this function:

insert_before_statement()

static void insert_before_statement ( statement  news, statement  s, bool  last  )

static

Just for test static void dump_list_of_statement(list l) { fprintf(stderr, "\n===== Dump List: \n"); MAP(STATEMENT, ss, { print_statement(ss); }, l); fprintf(stderr, "\n END dumpt List!!! \n"); }.

Statements are stored in reverse order... this will have to be fixed latter on. see #1#.

Insert in the front of list

Insert just before the appropriate statement of list

Definition at line 383 of file sequence_gcm_cse.c.

{
    cleanup_subscripts((gen_chunkp)news);
    if (!bound_inserted_p(s))
    {
        store_inserted(s, make_block_statement(CONS(STATEMENT, news, NIL)));
    }
    else
    {
        statement sb = load_inserted(s);
        instruction i = statement_instruction(sb);
 
        pips_assert("inserted in block", statement_block_p(sb) && entity_empty_label_p(statement_label(sb)));
 
        /* Statements are stored in reverse order...
           this will have to be fixed latter on. see #1#.
           */
 
        /* Insert in the front of list
         * ===========================
         */
        if (last)
        {
            instruction_block(i) = CONS(STATEMENT, news, instruction_block(i));
        }
        /* Insert just before the appropriate statement of list
         * ====================================================
         */
        else
        {
            instruction_block(i) =
                insertion_statement_in_correct_position(news, instruction_block(i));
        }
    }
}

References cleanup_subscripts(), CONS, entity_empty_label_p(), insertion_statement_in_correct_position(), instruction_block, make_block_statement(), NIL, pips_assert, STATEMENT, statement_block_p, statement_instruction, and statement_label.

Referenced by atom_cse_expression(), atomize_or_associate_for_level(), and do_atomize_if_different_level().

Here is the call graph for this function:

Here is the caller graph for this function:

insert_rwt()

static void insert_rwt ( statement  s )

static

Insert the new statements created.

Reverse list of inserted statements (#1#)

Remove statements redundant

need some patching

Definition at line 957 of file sequence_gcm_cse.c.

{
    if (bound_inserted_p(s))
    {
        statement sblock = load_inserted(s);
        instruction i = statement_instruction(sblock);
        sequence seq;
 
        pips_assert("it is a sequence", instruction_sequence_p(i) && entity_empty_label_p(statement_label(sblock)));
 
        /* Reverse list of inserted statements (#1#) */
        seq = instruction_sequence(i);
 
        /* Remove statements redundant */
        remove_statement_redundant(s, &sequence_statements(seq));
 
        statement clone = instruction_to_statement(copy_instruction(statement_instruction(s)));
        /* need some patching */
        free_extensions(statement_extensions(clone));
        statement_extensions(clone)=statement_extensions(s);
        statement_extensions(s)=empty_extensions();
        statement_label(clone)=statement_label(s);
        statement_label(s)=entity_empty_label();
        sequence_statements(seq)=CONS(STATEMENT,clone,sequence_statements(seq));
        sequence_statements(seq) = gen_nreverse(sequence_statements(seq));
 
        update_statement_instruction(s,i);
    }
}

References clone(), CONS, copy_instruction(), empty_extensions(), entity_empty_label(), entity_empty_label_p(), free_extensions(), gen_nreverse(), instruction_sequence, instruction_sequence_p, instruction_to_statement(), pips_assert, remove_statement_redundant(), sequence_statements, STATEMENT, statement_extensions, statement_instruction, statement_label, and update_statement_instruction().

Referenced by perform_ac_cse(), and perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

insertion_statement_in_correct_position()

static list insertion_statement_in_correct_position ( statement  news, list  l  )

static

Insert statement s in the list of statement l.

Definition at line 358 of file sequence_gcm_cse.c.

{
  entity ent = left_side_of_assign_statement(news);
  statement s = STATEMENT(CAR(l));
 
  if (entity_undefined_p(ent) || entity_as_arguments(ent, s) || ENDP(CDR(l)) )
  {
    return CONS(STATEMENT, s, CONS(STATEMENT, news, CDR(l)));
  }
  return CONS(STATEMENT, s,
              insertion_statement_in_correct_position(news, CDR(l)));
}

References CAR, CDR, CONS, ENDP, entity_as_arguments(), entity_undefined_p, left_side_of_assign_statement(), and STATEMENT.

Referenced by insert_before_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

interference_on()

static bool interference_on ( entity  var, list  les  )

static

Compute if an effect list Some effect in les interfere with var.

Parameters

[in]	var	is the variable to test interference with the effects
[in]	les	is the effect list to look for var

Returns

true if there may be a write effect on var

There is an interference only if there is a write effect:

If an effect can write anywhere, it may be also on var:

If we may have a write effect on var, mark a conflict:

Parameters

les

of effect

Definition at line 174 of file sequence_gcm_cse.c.

{
  FOREACH(EFFECT, ef, les) {
    /* There is an interference only if there is a write effect: */
    if (effect_write_p(ef)) {
      if (entity_all_locations_p(effect_entity(ef)))
        /* If an effect can write anywhere, it may be also on var: */
        return true;
 
      if (entities_may_conflict_p(var, reference_variable(effect_any_reference(ef))))
        /* If we may have a write effect on var, mark a conflict: */
        return true;
    }
  }
  return false;
}

References EFFECT, effect_any_reference, effect_entity(), effect_write_p, entities_may_conflict_p(), entity_all_locations_p(), FOREACH, and reference_variable.

Referenced by moveable_to().

Here is the call graph for this function:

Here is the caller graph for this function:

Is_Associative_Commutative()

static bool Is_Associative_Commutative ( entity  e )

static

Definition at line 81 of file sequence_gcm_cse.c.

{
  const char* local_name = entity_local_name(e);
  int i = 0;
 
  while (table_of_AC_operators[i])
    {
      if (same_string_p(local_name,table_of_AC_operators[i])){
        pips_debug(3," %s is Associative Commutative \n", local_name);
        return true;
      }
      i++;
    }
  pips_debug(3," %s is NOT Associative Commutative \n", local_name);
  return false;
}

References entity_local_name(), local_name(), pips_debug, same_string_p, and table_of_AC_operators.

Referenced by atom_cse_expression(), atomize_or_associate_for_level(), make_available_scalar(), and similarity().

Here is the call graph for this function:

Here is the caller graph for this function:

left_side_of_assign_statement()

static entity left_side_of_assign_statement ( statement  stat )

static

Return the entity in left side of an assign statement.

Definition at line 347 of file sequence_gcm_cse.c.

{
  expression left_side = expr_left_side_of_assign_statement(stat);
  if( ! syntax_reference_p(expression_syntax(left_side)) )
      return entity_undefined;
  else
      return reference_variable(syntax_reference(expression_syntax(left_side)));
}

References entity_undefined, expr_left_side_of_assign_statement(), expression_syntax, reference_variable, syntax_reference, and syntax_reference_p.

Referenced by atom_cse_expression(), cse_expression_flt(), increase_number_of_use_by_1(), insertion_statement_in_correct_position(), and update_number_of_use().

Here is the call graph for this function:

Here is the caller graph for this function:

level_of()

static int level_of ( list  le )

static

Return the level of this expression, using the current nesting list.

0: before any statement! n: outside nth loop. and so on.

of statement

Parameters

le	of effects

Definition at line 208 of file sequence_gcm_cse.c.

{
  list /* of statement */ up_nesting = gen_nreverse(gen_copy_seq(nesting));
  int level = 0;
  FOREACH(STATEMENT, s,up_nesting)
  {
      if (moveable_to(le, s))
        break;
      else
        level++;
  }
  gen_free_list(up_nesting);
  return level;
 
}

References FOREACH, gen_copy_seq(), gen_free_list(), gen_nreverse(), level, moveable_to(), nesting, and STATEMENT.

Referenced by expr_level_of().

Here is the call graph for this function:

Here is the caller graph for this function:

list_diff()

static list list_diff ( list  l1, list  l2  )

static

of expression

returns an allocated l1-l2 with expression_equal_p l2 included in l1.

of expression

Definition at line 1576 of file sequence_gcm_cse.c.

{
  list diff = NIL, l2bis = gen_copy_seq(l2);
  expression found;
 
  FOREACH(EXPRESSION, e,l1)
  {
    if (expression_eq_in_list_p(e, l2bis, &found))
    {
      gen_remove(&l2bis, found);
    }
    else
    {
      diff = CONS(EXPRESSION, e, diff);
    }
  }
 
  if (l2bis) gen_free_list(l2bis);
 
  return diff;
}

References CONS, EXPRESSION, expression_eq_in_list_p(), FOREACH, gen_copy_seq(), gen_free_list(), gen_remove(), and NIL.

Referenced by atom_cse_expression(), and similarity().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_flt()

static bool loop_flt ( loop  l )

static

RK: Why ?

Definition at line 701 of file sequence_gcm_cse.c.

{
  statement sofl = current_statement_head();
  pips_assert("statement of loop",
              instruction_loop(statement_instruction(sofl))==l);
  /* RK: Why ? */
  push_nesting(sofl);
  return true;
}

References instruction_loop, pips_assert, push_nesting(), and statement_instruction.

Referenced by perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_rwt()

static void loop_rwt ( loop  l )

static

RK: Why ?

Deal with loop bound expressions

Nothing to do if we are in the top-level statement

Atomize the loop bound expressions:

Definition at line 711 of file sequence_gcm_cse.c.

{
  range bounds;
  int level;
  statement sofl = current_statement_head();
  /* RK: Why ? */
  pop_nesting(sofl);
 
  /* Deal with loop bound expressions
   */
  if (!currently_nested_p())
    /* Nothing to do if we are in the top-level statement */
    return;
  bounds = loop_range(l);
  level = current_level();
  /* Atomize the loop bound expressions: */
  do_atomize_if_different_level(range_lower(bounds), 1+level);
  do_atomize_if_different_level(range_upper(bounds), 1+level);
  do_atomize_if_different_level(range_increment(bounds), 1+level);
}

References current_level(), currently_nested_p(), do_atomize_if_different_level(), level, loop_range, pop_nesting(), range_increment, range_lower, and range_upper.

Referenced by perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_stop()

static bool loop_stop ( loop  l, __attribute__((unused)) list *  skip_list  )

static

Definition at line 1859 of file sequence_gcm_cse.c.

{
  gen_recurse_stop(loop_body(l));
  return true;
}

References gen_recurse_stop(), and loop_body.

Referenced by atomize_cse_this_statement_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

make_available_scalar()

static available_scalar_pt make_available_scalar ( entity  scalar, statement  container, expression  contents  )

static

Definition at line 1521 of file sequence_gcm_cse.c.

{
    pips_debug(2,"adding new scalar to pool:%s\nas a container for %s\n",
               entity_user_name(scalar),expression_to_string(contents));
  syntax s = expression_syntax(contents);
 
  available_scalar_pt aspt =
    (available_scalar_pt) malloc(sizeof(available_scalar_t));
 
  aspt->scalar = scalar;
  aspt->container = container;
  aspt->contents = contents;
 
  aspt->depends = get_all_entities(contents);
 
  aspt->w_effects = w_effects;
 
  if (syntax_call_p(s))
  {
    call c = syntax_call(s);
    aspt->operator = call_function(c);
    if (Is_Associative_Commutative(aspt->operator))
      aspt->available_contents = gen_copy_seq(call_arguments(c));
    else
      aspt->available_contents = NIL;
  }
  else
  {
    aspt->operator = NULL;
    aspt->available_contents = NIL;
  }
 
  return aspt;
}

References available_scalar_t::available_contents, call_arguments, call_function, available_scalar_t::container, available_scalar_t::contents, available_scalar_t::depends, entity_user_name(), expression_syntax, expression_to_string(), gen_copy_seq(), get_all_entities(), Is_Associative_Commutative(), malloc(), NIL, available_scalar_t::operator, pips_debug, available_scalar_t::scalar, syntax_call, syntax_call_p, w_effects, and available_scalar_t::w_effects.

Referenced by atom_cse_expression().

Here is the call graph for this function:

Here is the caller graph for this function:

moveable_to()

static bool moveable_to ( list  le, statement  s  )

static

Whether sg with effects le can be moved up to s.

Parameters

le	of effects

Definition at line 194 of file sequence_gcm_cse.c.

{
  list les = load_cumulated_rw_effects_list(s);
  FOREACH(EFFECT, ef,le)
      if (interference_on(reference_variable(effect_any_reference(ef)), les))
        return false;
  return true;
}

References EFFECT, effect_any_reference, FOREACH, interference_on(), load_cumulated_rw_effects_list(), and reference_variable.

Referenced by level_of().

Here is the call graph for this function:

Here is the caller graph for this function:

number_of_use_greater_1()

static bool number_of_use_greater_1 ( statement  s )

static

PDSon: I use the field 'comments' of statement for counting its number of use.

Raison: The field 'comments' of new statement added is always empty! This function verifies if number of use is greater than 1 or not.

Definition at line 736 of file sequence_gcm_cse.c.

{
  char* comment = statement_comments(s);
  int number = 0;
 
  if(empty_comments_p(comment))
  {
    return false;
  }
 
  sscanf((const char*)comment,"%d", &number);
  return (number > 1);
}

References comment(), empty_comments_p(), and statement_comments.

Referenced by cse_expression_flt().

Here is the call graph for this function:

Here is the caller graph for this function:

perform_ac_cse()

void perform_ac_cse	(	__attribute__((unused)) const char *	name,
		statement	s
	)

they have to be recomputed, because if ICM before.

set full (expr and statements) PROPER EFFECTS well, they are computed twice here... looks rather temporary.

make_current_statement_stack();

insert moved code in statement.

Remove the "inserted" mapping:

Definition at line 2034 of file sequence_gcm_cse.c.

{
  /* they have to be recomputed, because if ICM before. */
 
  /* set full (expr and statements) PROPER EFFECTS
     well, they are computed twice here...
     looks rather temporary.
   */
  /*
  full_simple_proper_effects(name, s);
  simple_cumulated_effects(name, s);
  */
 
  /* make_current_statement_stack(); */
  init_inserted();
 
  gen_multi_recurse(s,
          sequence_domain, seq_flt, gen_null,
          call_domain, call_flt, gen_null,
          0);
 
  /* insert moved code in statement. */
  gen_multi_recurse(s, statement_domain, gen_true, insert_rwt, NULL);
  cleanup_subscripts((gen_chunkp)s);
  /* Remove the "inserted" mapping: */
  close_inserted();
  /*
  close_expr_prw_effects();
  close_proper_rw_effects();
  close_rw_effects();
  */
}

References call_domain, call_flt(), cleanup_subscripts(), gen_multi_recurse(), gen_null(), gen_true(), insert_rwt(), seq_flt(), sequence_domain, and statement_domain.

Here is the call graph for this function:

perform_icm_association()

void perform_icm_association	(	const char *	name,
		statement	s
	)

Perform ICM and association on operators.

sequence_gcm_cse.c

This is kind of an atomization. many side effects: modifies the code, uses simple effects

Parameters

[in]	name	specified the module name to work on
[in,out]	s	is the statement of the module

GET CUMULATED EFFECTS

SG: reorder expression so that the icm algorithm matches more cases

Set full (expr and statements) PROPER EFFECTS

Initialize the "inserted" mapping:

Create the stack to track current statement:

ATOMIZE and REASSOCIATE by level.

On each statement, we push the statement top-down on the current_statement stack, and when climbing bottom-up, we pull back the statement and verify it was the same on the stack. Nowadays we could use statement parent information directly from NewGen...

Atomize instructions with calls during bottom-up phase:

could also push while loops...

do not atomize index computations at the time...

skip IO calls

Insert moved code in statement at the right place:

Delete the stack used to track current statement:

no memory leaks?

some clean up

This only works in Fortran because of C local declarations. It's easier to let restructure_control() or flatten_code take care of it.

Parameters

name	ame
s	of the module of the module

Definition at line 1002 of file sequence_gcm_cse.c.

{
  pips_assert("clean static structures on entry",
              (get_current_statement_stack() == stack_undefined) &&
              inserted_undefined_p() &&
              (nesting==NIL));
 
  /*
  simple_cumulated_effects(name, s);
  set_cumulated_rw_effects(get_rw_effects());
  */
 
  /* GET CUMULATED EFFECTS
   */
  set_cumulated_rw_effects((statement_effects)
        db_get_memory_resource(DBR_CUMULATED_EFFECTS, name, true));
 
  /* SG: reorder expression so that the icm algorithm matches more cases */
  gen_recurse(s,statement_domain,prepare_icm,gen_null);
 
  /* Set full (expr and statements) PROPER EFFECTS
   */
  full_simple_proper_effects(name, s);
 
  /* Initialize the "inserted" mapping: */
  init_inserted();
  /* Create the stack to track current statement: */
  make_current_statement_stack();
 
#if defined(PUSH_BODY)
  push_nesting(s);
#endif
 
  /* ATOMIZE and REASSOCIATE by level.
   */
  gen_multi_recurse(s,
                    /* On each statement, we push the statement top-down
                       on the current_statement stack, and when climbing
                       bottom-up, we pull back the statement and verify it
                       was the same on the stack. Nowadays we could use
                       statement parent information directly from
                       NewGen... */
      statement_domain, current_statement_filter, current_statement_rewrite,
                    /* Atomize instructions with calls during bottom-up
                       phase: */
      instruction_domain, gen_true, atomize_instruction,
                    /* */
      loop_domain, loop_flt, loop_rwt,
      test_domain, gen_true, atomize_test,
      whileloop_domain, gen_true, atomize_whileloop,
      /* could also push while loops... */
      expression_domain, gen_true, atomize_or_associate,
      /* do not atomize index computations at the time... */
      //reference_domain, gen_false, gen_null,
      call_domain, icm_atom_call_flt, gen_null, /* skip IO calls */
                    NULL);
  /* Insert moved code in statement at the right place: */
  gen_multi_recurse(s, statement_domain, gen_true, insert_rwt, NULL);
 
 
#if defined(PUSH_BODY)
  pop_nesting(s);
#endif
 
  pips_assert("clean static structure on exit",
              (nesting==NIL) &&
              (current_statement_size()==0));
 
  /* Delete the stack used to track current statement: */
  free_current_statement_stack();
  close_inserted();
 
  reset_cumulated_rw_effects();
 
  close_expr_prw_effects();  /* no memory leaks? */
  close_proper_rw_effects();
 
  /* some clean up */
  /* This only works in Fortran because of C local declarations. It's
     easier to let restructure_control() or flatten_code take care of
     it. */
  //flatten_sequences(s);
}

References atomize_instruction(), atomize_or_associate(), atomize_test(), atomize_whileloop(), call_domain, close_expr_prw_effects(), close_proper_rw_effects(), db_get_memory_resource(), expression_domain, full_simple_proper_effects(), gen_multi_recurse(), gen_null(), gen_recurse, gen_true(), icm_atom_call_flt(), insert_rwt(), instruction_domain, loop_domain, loop_flt(), loop_rwt(), nesting, NIL, pips_assert, pop_nesting(), prepare_icm(), push_nesting(), reset_cumulated_rw_effects(), set_cumulated_rw_effects(), stack_undefined, statement_domain, test_domain, and whileloop_domain.

Referenced by optimize_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

pop_nesting()

static void pop_nesting ( statement  s )

static

Pop the current statement from nesting list.

Definition at line 135 of file sequence_gcm_cse.c.

{
  list old = nesting;
  pips_assert("same ", nesting && (s == STATEMENT(CAR(nesting))));
  nesting = CDR(nesting);
  CDR(old) = NIL;
  gen_free_list(old);
}

References CAR, CDR, gen_free_list(), nesting, NIL, pips_assert, and STATEMENT.

Referenced by loop_rwt(), and perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

prepare_icm()

static bool prepare_icm ( statement  s )

static

Definition at line 987 of file sequence_gcm_cse.c.

                                     {
    if(statement_loop_p(s)) {
        try_reorder_expressions(s,true);
    }
    return true;
}

References statement_loop_p(), and try_reorder_expressions().

Referenced by perform_icm_association().

Here is the call graph for this function:

Here is the caller graph for this function:

prune_non_constant()

static void prune_non_constant ( list  effects, list *  perms  )

static

Definition at line 1957 of file sequence_gcm_cse.c.

                                                          {
    list out = NIL;
    FOREACH(EXPRESSION,exp,*perms) {
        set re = get_referenced_entities(exp);
        bool conflict = false;
        SET_FOREACH(entity,e,re) {
            if(effects_write_variable_p(effects,e)) {
                conflict=true;
                break;
            }
        }
        set_free(re);
        if(!conflict) out=CONS(EXPRESSION,exp,out);
    }
    gen_free_list(*perms);
    *perms=out;
}

References CONS, effects_write_variable_p(), exp, EXPRESSION, FOREACH, gen_free_list(), get_referenced_entities(), NIL, out, SET_FOREACH, and set_free().

Referenced by try_reorder_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

prune_singleton()

static void prune_singleton ( list *  l )

static

Definition at line 1282 of file sequence_gcm_cse.c.

                                      {
    list new = NIL;
    FOREACH(EXPRESSION,e0,*l) {
        FOREACH(EXPRESSION,e1,*l) {
            if(e0!=e1 && same_expression_p(e0,e1) ) {
                new=CONS(EXPRESSION,copy_expression(e0),new);
                break;
            }
        }
    }
    gen_full_free_list(*l);
    *l=new;
}

References CONS, copy_expression(), EXPRESSION, FOREACH, gen_full_free_list(), NIL, and same_expression_p().

Referenced by try_reorder_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

push_nesting()

static void push_nesting ( statement  s )

static

Keep track of statement nesting.

Definition at line 129 of file sequence_gcm_cse.c.

{
  nesting = CONS(STATEMENT, s, nesting);
}

References CONS, nesting, and STATEMENT.

Referenced by loop_flt(), and perform_icm_association().

Here is the caller graph for this function:

remove_statement_redundant()

static void remove_statement_redundant ( statement  s, list *  inserted  )

static

Remove statement redundant inserted before statement s.

Definition at line 946 of file sequence_gcm_cse.c.

{
  gen_context_multi_recurse(s, inserted,
                            call_domain, cse_call_flt, gen_null,
                            expression_domain, cse_expression_flt, gen_null,
                            NULL);
}

References call_domain, cse_call_flt(), cse_expression_flt(), expression_domain, gen_context_multi_recurse(), and gen_null().

Referenced by cse_expression_flt(), and insert_rwt().

Here is the call graph for this function:

Here is the caller graph for this function:

reorder_pointer_expression()

static void reorder_pointer_expression ( expression  e )

static

make sure expressions are ordered with pointer first

Definition at line 1218 of file sequence_gcm_cse.c.

                                                     {
    if(expression_call_p(e)) {
        call c = expression_call(e);
        if(commutative_call_p(c)) {
            expression lhs = binary_call_lhs(c),
                       rhs = binary_call_rhs(c);
            basic brhs = basic_of_expression(rhs);
            if(basic_pointer_p(brhs)) {
                gen_free_list(call_arguments(c));
                call_arguments(c)=make_expression_list(
                        rhs,lhs);
            }
        }
        FOREACH(EXPRESSION,e,call_arguments(c))
            reorder_pointer_expression(e);
    }
}

References basic_of_expression(), basic_pointer_p, binary_call_lhs, binary_call_rhs, call_arguments, commutative_call_p(), EXPRESSION, expression_call(), expression_call_p(), FOREACH, gen_free_list(), and make_expression_list.

Referenced by do_gather_all_expressions_perms().

Here is the call graph for this function:

Here is the caller graph for this function:

right_side_of_assign_statement()

static expression right_side_of_assign_statement ( statement  stat )

static

Definition at line 283 of file sequence_gcm_cse.c.

{
  instruction i;
  call assign;
  expression right_side;
 
  i = statement_instruction(stat);
 
  pips_assert("Instruction is a call", instruction_call_p(i));
  assign = instruction_call(i);
 
  pips_assert("Call is an assignment!",
              ENTITY_ASSIGN_P(call_function(assign)));
 
  right_side = EXPRESSION(CAR(CDR(call_arguments(assign))));
 
  return right_side;
}

References call_arguments, call_function, CAR, CDR, ENTITY_ASSIGN_P, EXPRESSION, instruction_call, instruction_call_p, pips_assert, and statement_instruction.

Referenced by cse_expression_flt(), entity_as_arguments(), and increase_number_of_use_by_1().

Here is the caller graph for this function:

seq_flt()

static bool seq_flt ( sequence  s )

static

top down.

At first, w_effects is empty list BUT not list points to NIL!!!

SG: not valid due to newgen check w_effects = &CDR(CONS(EXPRESSION, NIL, NIL));

top_of_w_effects points to the top of list, It is used to free memory later

SG we try to perform some reordering of linear expression to ease matching. To do so we (optimistically) gather similar expressions, and when pairs are found, they are kept for further matching. The pair gathering is store unaware, but the later process takes care of this. At worse we did some useless reordering.

Free top_of_w_effects and availables

Definition at line 1987 of file sequence_gcm_cse.c.

{
    pips_debug(1,"considering statement:\n");
    ifdebug(1) {
        FOREACH(STATEMENT, ss,sequence_statements(s))
            print_statement(ss);
    }
    list availables = NIL;
    list *top_of_w_effects;
 
    /* At first, w_effects is empty list BUT not list points to NIL!!!*/
    /* SG: not valid due to newgen check w_effects = &CDR(CONS(EXPRESSION, NIL, NIL));*/
    w_effects = &CDR(gen_cons(NIL,NIL));
 
    /* top_of_w_effects points to the top of list,
     * It is used to free memory later
     */
    top_of_w_effects = w_effects;
 
    /* SG we try to perform some reordering of linear expression to ease matching.
     * To do so we (optimistically) gather similar expressions, and when pairs are found, they are kept for further matching.
     * The pair gathering is store unaware, but the later process takes care of this. At worse we did some useless reordering.*/
    try_reorder_expressions(s,false);
 
    FOREACH(STATEMENT, ss,sequence_statements(s))
    {
        availables = atomize_cse_this_statement_expressions(ss, availables);
    }
 
    /* Free top_of_w_effects and availables */
    gen_full_free_list(*top_of_w_effects);
    return true;
}

References atomize_cse_this_statement_expressions(), CDR, FOREACH, gen_cons(), gen_full_free_list(), ifdebug, NIL, pips_debug, print_statement(), sequence_statements, STATEMENT, try_reorder_expressions(), and w_effects.

Referenced by perform_ac_cse().

Here is the call graph for this function:

Here is the caller graph for this function:

set_comment_of_statement()

static void set_comment_of_statement ( statement  s, char *  new_comment  )

static

Update the field 'comments' of a statement.

Definition at line 752 of file sequence_gcm_cse.c.

{
  if (empty_comments_p(statement_comments(s)))
  {
    statement_comments(s) = new_comment;
  }
  else
  {
    free(statement_comments(s));
    statement_comments(s) = new_comment;
  }
}

References empty_comments_p(), free(), and statement_comments.

Referenced by atom_cse_expression(), cse_expression_flt(), and update_number_of_use().

Here is the call graph for this function:

Here is the caller graph for this function:

side_effects_p()

static bool side_effects_p ( expression  e )

static

There is a side effect if there is a W effect in the expression.

of effect

Definition at line 152 of file sequence_gcm_cse.c.

{
    pips_debug(1,"considering expression %s\n",expression_to_string(e));
    effects ef = load_expr_prw_effects(e);
    list /* of effect */ le = effects_effects(ef);
    FOREACH(EFFECT, ef,le)
        if (effect_write_p(ef)) {
            pips_debug(1,"has side effects\n");
            return true;
        }
    pips_debug(1,"does not have side effects\n");
    return false;
}

References EFFECT, effect_write_p, effects_effects, expression_to_string(), FOREACH, load_expr_prw_effects(), and pips_debug.

Referenced by do_atomize_if_different_level(), and group_expr_by_level().

Here is the call graph for this function:

Here is the caller graph for this function:

similarity()

static int similarity ( expression  e, available_scalar_pt  aspt  )

static

Find the commun sub-expression between e & aspt.

Attention: Commun expression does't contain any expression in w_effects

same function...

similarity is the number of args in common. inversion is not tested at the time.

any call: must be equal

A variable is already modified !

Definition at line 1427 of file sequence_gcm_cse.c.

{
  syntax s = expression_syntax(e), sa = expression_syntax(aspt->contents);
 
  /*
  fprintf(stderr, "similarity on %s\n", entity_name(aspt->scalar));
  print_expression(e);
  dump_aspt(aspt);
  */
 
  if (syntax_tag(s)!=syntax_tag(sa)) return NO_SIMILARITY;
 
  if (syntax_reference_p(s))
  {
    reference r = syntax_reference(s), ra = syntax_reference(sa);
    if (reference_equal_p(r, ra))
    {
      return MAX_SIMILARITY;
    }
  }
 
  if (syntax_call_p(s))
  {
    call c = syntax_call(s), ca = syntax_call(sa);
    entity cf = call_function(c);
    if (cf!=call_function(ca)) return NO_SIMILARITY;
 
    /* same function...
     */
    if (Is_Associative_Commutative(cf))
    {
      /* similarity is the number of args in common.
         inversion is not tested at the time.
      */
      list com = common_expressions(list_diff(call_arguments(c),
                                              *(aspt->w_effects)),
                                    aspt->available_contents);
      size_t n = gen_length(com);
      gen_free_list(com);
      if (n<=1) return NO_SIMILARITY;
      return (n == gen_length(call_arguments(ca)) &&
              n == gen_length(call_arguments(c))) ? MAX_SIMILARITY: n;
    }
    else
    {
      /* any call: must be equal
       */
      list l = call_arguments(c), la = call_arguments(ca);
      pips_assert("same length", gen_length(l)==gen_length(la));
      for (; l; l = CDR(l), la = CDR(la))
      {
        expression el = EXPRESSION(CAR(l)), ela = EXPRESSION(CAR(la));
        if (!expression_equal_p(el, ela))
        {
          return NO_SIMILARITY;
        }
 
        if (expression_eq_in_list_p(el, *(aspt->w_effects), &el))
        {
          /* A variable is already modified ! */
          return NO_SIMILARITY;
        }
      }
      return MAX_SIMILARITY;
    }
  }
 
  return NO_SIMILARITY;
}

References available_scalar_t::available_contents, call_arguments, call_function, CAR, CDR, common_expressions(), available_scalar_t::contents, EXPRESSION, expression_eq_in_list_p(), expression_equal_p(), expression_syntax, gen_free_list(), gen_length(), Is_Associative_Commutative(), list_diff(), MAX_SIMILARITY, NO_SIMILARITY, pips_assert, reference_equal_p(), syntax_call, syntax_call_p, syntax_reference, syntax_reference_p, syntax_tag, and available_scalar_t::w_effects.

Referenced by best_similar_expression().

Here is the call graph for this function:

Here is the caller graph for this function:

statement_of_level()

static statement statement_of_level ( int  level )

static

or for a statement.

Returns the statement of the specified level should returns current_statement_head() to avoid ICM directly.

Definition at line 261 of file sequence_gcm_cse.c.

{
#if !defined(NO_ICM)
  int n = current_level()-1-level;
 
  if (n>=0)
    return STATEMENT(gen_nth(n, nesting));
  else
#endif
    return current_statement_head();
}

References current_level(), gen_nth(), level, nesting, and STATEMENT.

Referenced by atomize_or_associate_for_level(), and do_atomize_if_different_level().

Here is the call graph for this function:

Here is the caller graph for this function:

test_stop()

static bool test_stop ( test  t, __attribute__((unused)) list *  skip_list  )

static

Definition at line 1865 of file sequence_gcm_cse.c.

{
  gen_recurse_stop(test_true(t));
  gen_recurse_stop(test_false(t));
  return true;
}

References gen_recurse_stop(), test_false, and test_true.

Referenced by atomize_cse_this_statement_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

try_reorder_expression_call()

static bool try_reorder_expression_call ( expression  e, list  availables  )

static

update normalized field, and make sure it is consistent

the idea is to split an expression into two linear parts, one that is already available and one that is not

Definition at line 1171 of file sequence_gcm_cse.c.

                                                                       {
    /* update normalized field, and make sure it is consistent */
    unnormalize_expression(e);
    NORMALIZE_EXPRESSION(e);
    normalized n = expression_normalized(e);
    /* the idea is to split an expression into two linear parts, one that is already available and one that is not */
    if(normalized_linear_p(n)){
        Pvecteur pv =normalized_linear(n);
        int cplx =vect_size(pv);
        int bestcplx = INT_MAX;
        expression bestexp = expression_undefined;
        FOREACH(EXPRESSION,eavailable, availables){
            NORMALIZE_EXPRESSION(eavailable);
            normalized navailable = expression_normalized(eavailable);
            if(normalized_linear_p(navailable)) {
                Pvecteur pva = normalized_linear(navailable);
                Pvecteur diff = vect_substract(pv,pva);
                int dcplx = vect_size(diff);
                if(dcplx < cplx && dcplx < bestcplx) {
                    bestexp = eavailable;
                    bestcplx=dcplx;
                }
                vect_rm(diff);
            }
        }
        if(!expression_undefined_p(bestexp) && !same_expression_p(e,bestexp)) {
            update_expression_syntax(e,
                    make_syntax_call(
                        make_call(
                            entity_intrinsic(PLUS_C_OPERATOR_NAME),
                            make_expression_list(
                                make_op_exp(MINUS_OPERATOR_NAME,
                                    copy_expression(e),
                                    copy_expression(bestexp)
                                    ),
                                copy_expression(bestexp)
                                )
                            )
                        )
                    );
            return false;
        }
    }
    return true;
}

References copy_expression(), entity_intrinsic(), EXPRESSION, expression_normalized, expression_undefined, expression_undefined_p, FOREACH, make_call(), make_expression_list, make_op_exp(), make_syntax_call(), MINUS_OPERATOR_NAME, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, PLUS_C_OPERATOR_NAME, same_expression_p(), unnormalize_expression(), update_expression_syntax(), vect_rm(), vect_size(), and vect_substract().

Referenced by try_reorder_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

try_reorder_expressions()

void try_reorder_expressions	(	void *	s,
		bool	icm
	)

Parameters

icm

cm

Definition at line 1975 of file sequence_gcm_cse.c.

    {
        list gathered = NIL;
        gen_context_recurse(s, &gathered, expression_domain, do_gather_all_expressions, gen_null2);
        if(icm) prune_non_constant(load_cumulated_rw_effects_list(s),&gathered);
        else prune_singleton(&gathered);
        gen_context_recurse(s, gathered,
          expression_domain, try_reorder_expression_call, gen_null2);
        gen_full_free_list(gathered);
    }

References do_gather_all_expressions(), expression_domain, gen_context_recurse, gen_full_free_list(), gen_null2(), icm(), load_cumulated_rw_effects_list(), NIL, prune_non_constant(), prune_singleton(), and try_reorder_expression_call().

Referenced by prepare_icm(), and seq_flt().

Here is the call graph for this function:

Here is the caller graph for this function:

update_number_of_use()

static statement update_number_of_use ( entity  ent, list  lst_stat, int  up_down  )

static

Update the number of use of statement defining 'ent' which is a member of list lst_stat with step up_down (up_down = 1 | 0 | -1).

If ent is a variable of original code (ex: x, y), not new variable added (ex: F_0, F_1,..), there is not any statement in lst_stat defining ent. Return: statement updated

First time, no value

Update old value

Definition at line 771 of file sequence_gcm_cse.c.

{
  FOREACH(STATEMENT, s,lst_stat)
  {
      entity left_side = left_side_of_assign_statement(s);
      if(ent == left_side) // s defines ent
      {
          if (up_down == 0)
          {
              return s;
          }
 
          /* First time, no value */
          if (empty_comments_p(statement_comments(s)))
          {
              if (up_down == -1)
              {
                  pips_internal_error("Number of use of '%s' < 0 !!!",
                          entity_name(ent));
              }
              set_comment_of_statement(s, strdup("1"));
          }
          /* Update old value */
          else
          {
              char *new;
              int number_use = 0;
              char* comment = statement_comments(s);
              sscanf((const char*)comment, "%d", &number_use);
 
              number_use += up_down;
              new=int2a(number_use);
              set_comment_of_statement(s, (new));
          }
          return s;
      }
  }
 
  return NULL;
}

References comment(), empty_comments_p(), entity_name, FOREACH, int2a(), left_side_of_assign_statement(), pips_internal_error, set_comment_of_statement(), STATEMENT, statement_comments, and strdup().

Referenced by increase_number_of_use_by_1().

Here is the call graph for this function:

Here is the caller graph for this function:

while_stop()

static bool while_stop ( whileloop  wl, __attribute__((unused)) list *  skip_list  )

static

Definition at line 1872 of file sequence_gcm_cse.c.

{
  gen_recurse_stop(whileloop_body(wl));
  return true;
}

References gen_recurse_stop(), and whileloop_body.

Referenced by atomize_cse_this_statement_expressions().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

current_available

list current_available = NIL

static

statement stack to current statement.

statements to be inserted as a sequence. For CSE

Definition at line 119 of file sequence_gcm_cse.c.

Referenced by atom_cse_expression(), atomize_cse_this_statement_expressions(), and best_similar_expression().

current_statement

statement current_statement = statement_undefined

static

Definition at line 120 of file sequence_gcm_cse.c.

Referenced by atom_cse_expression(), atomize_cse_this_statement_expressions(), and make_fsm_transitions_statement().

nesting

list nesting = NIL

static

assumes:

• cumulated effects (as a dependence abstraction).
• proper effects for statements AND sub-expressions... current nesting of code, bottom-up order, to determine level.

Definition at line 108 of file sequence_gcm_cse.c.

Referenced by adg_path_possible_source(), current_level(), level_of(), perform_icm_association(), pop_nesting(), push_nesting(), and statement_of_level().

seen

list seen = NIL

static

Definition at line 1089 of file sequence_gcm_cse.c.

Referenced by add_call_ent(), add_ref_ent(), expression_in_list_p(), find_equal_expression_not_in_list(), and get_all_entities().

table_of_AC_operators

char* table_of_AC_operators[]

static

Initial value:

=
{ EOLE_SUM_OPERATOR_NAME,
  EOLE_PROD_OPERATOR_NAME,
  MIN_OPERATOR_NAME,
  MAX_OPERATOR_NAME,
  PLUS_OPERATOR_NAME,
  PLUS_C_OPERATOR_NAME,
  MINUS_OPERATOR_NAME,
  MINUS_C_OPERATOR_NAME,
  MULTIPLY_OPERATOR_NAME,
  NULL
}

option:

• whether to push the procedure statement (default no).
• whether to do ICM or not directly (default yes). #define PUSH_BODY #define NO_ICM List of associative and commutative n-ary operators

Definition at line 68 of file sequence_gcm_cse.c.

Referenced by Is_Associative_Commutative().

w_effects

list* w_effects

static

PDSon: w_effect store all the variables modified in the sequence of statement.

Definition at line 125 of file sequence_gcm_cse.c.

Referenced by atomize_cse_this_statement_expressions(), call_flt(), cse_atom_call_flt(), make_available_scalar(), seq_flt(), and two_addresses_code_generator().