reorder.c File Reference

These functions compute the statement_ordering of their arguments. More...

#include <stdio.h>
#include <strings.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "misc.h"
#include "ri-util.h"

Include dependency graph for reorder.c:

Go to the source code of this file.

Functions
void	reset_unstructured_number ()
	Reset the unstructured number for a new module reordering. More...
static int	get_unstructured_number ()
	Compute the next unstructured order. More...
static int	get_next_unstructured_number ()
	Compute the next unstructured order. More...
static int	statement_reorder (statement st, int un, int sn, bool *changed)
	Compute the statement ordering of a statement and all its components. More...
void	control_node_reorder (__attribute__((unused)) control c, __attribute__((unused)) set visited_control)
bool	unstructured_reorder (unstructured u)
	Reorder an unstructured. More...
bool	module_body_reorder (statement body)
	Reorder a module. More...
bool	module_reorder (statement body)
	Reorder a module and recompute order to statement if any. More...

Variables
static int	u_number
	The current unstructured number, that is the number of control node encountered during depth first visiting More...

Detailed Description

These functions compute the statement_ordering of their arguments.

To ease referencing statements, statements are numbered with an ordering that is made of 2 parts, an unstructured order that is the occurence order of unstructured control node in a depth first visit of the RI, and a local order that corresponds to appearance order in a depth first visit of the statements inside a control node. This last number in reset to one when encountering a control node.

Definition in file reorder.c.

Function Documentation

control_node_reorder()

void control_node_reorder	(	__attribute__((unused)) control	c,
		__attribute__((unused)) set	visited_control
	)

Definition at line 153 of file reorder.c.

                                                                       {
}

get_next_unstructured_number()

static int get_next_unstructured_number ( )

static

Compute the next unstructured order.

Definition at line 68 of file reorder.c.

                                          {
  return ++u_number;
}

References u_number.

Referenced by unstructured_reorder().

Here is the caller graph for this function:

get_unstructured_number()

static int get_unstructured_number ( )

static

Compute the next unstructured order.

Definition at line 62 of file reorder.c.

                                     {
  return u_number;
}

References u_number.

Referenced by module_body_reorder().

Here is the caller graph for this function:

module_body_reorder()

bool module_body_reorder

(

statement

body

)

Reorder a module.

This recompute the ordering of a module, that is the ordering number of all the statements in the module..

Parameters

body	is the top-level statement of the module to reorder

If a module_body_reorder() is required, ordering_to_statement must be recomputed if any. So use module_reorder() instead of the low-level module_body_reorder():

Reorder the module statements by beginning with unstructured number and statement number at 1

Parameters

body

ody

Definition at line 211 of file reorder.c.

{
  /* If a module_body_reorder() is required, ordering_to_statement must be
     recomputed if any. So use module_reorder() instead of the low-level
     module_body_reorder(): */
  pips_assert("ordering to statement is not initialized",
              !ordering_to_statement_initialized_p());
 
  debug_on("CONTROL_DEBUG_LEVEL");
 
  reset_unstructured_number();
 
  /* Reorder the module statements by beginning with unstructured number
     and statement number at 1 */
  bool changed = false;
  statement_reorder(body, get_unstructured_number(), 1, &changed);
 
  debug_off();
 
  return changed;
}

References debug_off, debug_on, get_unstructured_number(), ordering_to_statement_initialized_p(), pips_assert, reset_unstructured_number(), and statement_reorder().

Referenced by do_it(), and module_reorder().

Here is the call graph for this function:

Here is the caller graph for this function:

module_reorder()

bool module_reorder

(

statement

body

)

Reorder a module and recompute order to statement if any.

This recompute the ordering of a module, that is the ordering number of all the statements in the module..

If there is also already a mapping from the ordering to the statements, it is reset and recompute after reordering.

Parameters

body	is the top-level statement of the module to reorder

There was a mapping to associate a statement to a given ordering, so clean it:

There was a mapping to associate a statement to a given ordering, so we recompute it:

FI: I'd rather use set_ordering_to_statement() so that reset are properly called and no outdated ots hash table remains for ever in the background, but I do not want to break PIPS right now.

How do you know ordering to statement to be useful in the future?

May be, we are going to work on a different module very soon..

Parameters

body

ody

Definition at line 244 of file reorder.c.

{
  bool ordering_mapping_used = ordering_to_statement_initialized_p();
  if(ordering_mapping_used)
    /* There was a mapping to associate a statement to a given ordering,
       so clean it: */
    reset_ordering_to_statement();
 
  bool changed = module_body_reorder(body);
 
  if (ordering_mapping_used) {
    /* There was a mapping to associate a statement to a given ordering,
       so we recompute it: */
    set_ordering_to_statement(body);
    /* FI: I'd rather use set_ordering_to_statement() so that reset are
       properly called and no outdated ots hash table remains for ever in
       the background, but I do not want to break PIPS right now.
 
       How do you know ordering to statement to be useful in the future?
 
       May be, we are going to work on a different module very soon..
    */
  }
 
  return changed;
}

References module_body_reorder(), ordering_to_statement_initialized_p(), reset_ordering_to_statement(), and set_ordering_to_statement().

Referenced by add_control_counters(), AddEntityToCompilationUnit(), array_bound_check_bottom_up(), array_bound_check_interprocedural(), array_bound_check_top_down(), array_expansion(), atomizer(), bdsc_code_instrumentation(), controlizer(), copy_value_of_write(), copy_value_of_write_with_cumulated_regions(), deatomizer(), delay_communications(), delay_communications_interprocedurally(), delay_load_communications(), delay_store_communications(), do_kernelize(), dowhile_to_while(), dsc_code_parallelization(), eliminate_original_variables(), expression_substitution(), flatten_code(), for_loop_to_do_loop(), for_loop_to_while_loop(), freia_unroll_while(), fsm_generation(), fsm_merge_states(), fsm_split_state(), full_fsm_generation(), full_spaghettify(), full_unroll(), full_unroll_pragma(), generate_starpu_pragma(), generate_two_addresses_code(), global_parallelization(), gpu_promote_sequential(), group_constants(), guard_elimination(), if_conversion(), if_conversion_compact(), if_conversion_init(), interactive_loop_transformation(), invariant_code_motion(), isolate_statement(), kernel_load_store_engine(), kernelize(), linearize_array_generic(), loop_auto_unroll(), loop_expansion(), loop_expansion_init(), loop_nest_unswitching(), module_to_wp65_modules(), mpi_conversion(), mpi_task_generation(), new_atomizer(), new_controlizer(), normalize_microcode(), old_array_bound_check_instrumentation(), old_reductions(), one_thread_parallelize(), openmp_task_generation(), optimize_expressions(), outline(), partial_eval(), phrase_comEngine_distributor(), phrase_distributor(), phrase_distributor_control_code(), phrase_distributor_init(), phrase_remove_dependences(), reduction_atomization(), reduction_detection(), reduction_propagation(), redundant_load_store_elimination(), regions_to_loops(), RemoveEntityFromCompilationUnit(), restructure_control(), safescale_distributor(), safescale_distributor_init(), scalar_renaming(), sesamify(), simd_atomizer(), simd_remove_reductions(), simdizer(), simdizer_auto_tile(), simdizer_auto_unroll(), simdizer_init(), simplify_complex(), simplify_subscripts(), solve_hardware_constraints(), spaghettify(), spire_distributed_unstructured_to_structured(), spire_shared_unstructured_to_structured(), split_initializations(), split_structures(), statement_insertion(), static_controlize(), step_parser(), strip_mine(), symbolic_tiling(), taskify(), terapix_warmup(), tiling_sequence(), unroll(), unspaghettify(), variable_replication(), and wrap_kernel_argument().

Here is the call graph for this function:

reset_unstructured_number()

void reset_unstructured_number

(

void

)

Reset the unstructured number for a new module reordering.

reorder.c

Definition at line 56 of file reorder.c.

                                 {
  u_number = 0;
}

References u_number.

Referenced by control_graph(), and module_body_reorder().

Here is the caller graph for this function:

statement_reorder()

static int statement_reorder ( statement  st, int  un, int  sn, bool *  changed  )

static

Compute the statement ordering of a statement and all its components.

This function should be rewritten with a gen_multi_recurse_context() on statements and controls...

Parameters

st	is the statement which we want to compute the ordering
un	is the unstructured number before statement entry
st	is the statement number before statement entry

Returns

the statement number after the end of the given statement

Definition at line 83 of file reorder.c.

{
  instruction i = statement_instruction(st);
  pips_assert("instruction is defined", !instruction_undefined_p(i));
 
  // temporary, just to avoid rebooting...
  static int check_depth_hack = 0;
  check_depth_hack++;
  pips_assert("not too deep", check_depth_hack<10000);
 
  pips_debug(5, "entering for %"_intFMT" : (%d,%d)\n",
             statement_number(st), un, sn);
 
  // update ordering if needed
  int new_order = MAKE_ORDERING(un, sn);
  if (new_order != statement_ordering(st))
  {
    statement_ordering(st) = new_order;
    *changed = true;
  }
  sn += 1;
 
  switch (instruction_tag(i))
  {
  case is_instruction_sequence:
    pips_debug(5, "sequence\n");
    FOREACH (statement, s, sequence_statements(instruction_sequence(i)))
      sn = statement_reorder(s, un, sn, changed);
    break;
  case is_instruction_test:
    pips_debug(5, "test\n");
    sn = statement_reorder(test_true(instruction_test(i)), un, sn, changed);
    sn = statement_reorder(test_false(instruction_test(i)), un, sn, changed);
    break;
  case is_instruction_loop:
    pips_debug(5, "loop\n");
    sn = statement_reorder(loop_body(instruction_loop(i)), un, sn, changed);
    break;
  case is_instruction_whileloop:
    pips_debug(5, "whileloop\n");
    sn = statement_reorder(whileloop_body(instruction_whileloop(i)),
                           un, sn, changed);
    break;
  case is_instruction_forloop:
    pips_debug(5, "forloop\n");
    sn = statement_reorder(forloop_body(instruction_forloop(i)),
                           un, sn, changed);
    break;
  case is_instruction_goto:
  case is_instruction_call:
    pips_debug(5, "goto or call\n");
    // nothing to do, does not contain statements
    break;
  case is_instruction_expression:
    pips_debug(5, "expression\n");
    break;
  case is_instruction_unstructured:
    pips_debug(5, "unstructured\n");
    *changed |= unstructured_reorder(instruction_unstructured(i));
    break;
    // missing: is_instruction_multitest
  default:
    pips_internal_error("Unknown tag %d", instruction_tag(i));
  }
  pips_debug(5, "exiting %d\n", sn);
  check_depth_hack--;
  return sn;
}

References _intFMT, FOREACH, forloop_body, instruction_forloop, instruction_loop, instruction_sequence, instruction_tag, instruction_test, instruction_undefined_p, instruction_unstructured, instruction_whileloop, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_sequence, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, loop_body, MAKE_ORDERING, pips_assert, pips_debug, pips_internal_error, sequence_statements, statement_instruction, statement_number, statement_ordering, test_false, test_true, unstructured_reorder(), and whileloop_body.

Referenced by module_body_reorder(), and unstructured_reorder().

Here is the call graph for this function:

Here is the caller graph for this function:

unstructured_reorder()

bool unstructured_reorder

(

unstructured

u

)

Reorder an unstructured.

All the nodes of the unstructured are numbered, first the reachable one and the the unreachable ones if any.

Parameters

u	the unstructured to reorder.

this function is used by control/old_controlizer.c

To store the visited nodes by CONTROL_MAP and avoid visiting twice a control node:

To avoid renaming twice a control node statement, keep track of the visited statements:

First iterate on the reachable control nodes from the entry node of the unstructured and then from the exit node:

Since we enter a control node, increase the unstructured order:

ifdebug(3)

print_statement(st);

Since we enter a control node, number the statements inside this control node with a statement number starting from 1:

Free the list build up during the visit:

Definition at line 166 of file reorder.c.

{
  bool changed = false;
  /* To store the visited nodes by CONTROL_MAP and avoid visiting twice a
     control node: */
  list blocs = NIL;
  /* To avoid renaming twice a control node statement, keep track of the
     visited statements: */
  // set visited_control =
 
  pips_debug(2, "entering\n");
 
  /* First iterate on the reachable control nodes from the entry node of
     the unstructured and then from the exit node: */
  UNSTRUCTURED_CONTROL_MAP(c, u, blocs, {
      statement st = control_statement(c);
      /* Since we enter a control node, increase the unstructured
         order: */
      int un =  get_next_unstructured_number();
 
      pips_debug(3, "will reorder %ld %d\n", statement_number(st), un);
      /* ifdebug(3) */
      /*        print_statement(st); */
 
      /* Since we enter a control node, number the statements inside this
           control node with a statement number starting from 1: */
      statement_reorder(st, un, 1, &changed);
    });
 
  /* Free the list build up during the visit: */
  gen_free_list(blocs);
 
  debug(3, "unstructured_reorder", "exiting\n");
 
  return changed;
}

References control_statement, debug(), gen_free_list(), get_next_unstructured_number(), NIL, pips_debug, statement_number, statement_reorder(), and UNSTRUCTURED_CONTROL_MAP.

Referenced by control_graph(), and statement_reorder().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

u_number

int u_number

static

The current unstructured number, that is the number of control node encountered during depth first visiting

Definition at line 52 of file reorder.c.

Referenced by get_next_unstructured_number(), get_unstructured_number(), and reset_unstructured_number().