old_controlizer.c File Reference

#include <stdio.h>
#include <strings.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "ri-util.h"
#include "workspace-util.h"
#include "prettyprint.h"
#include "control.h"
#include "properties.h"
#include "misc.h"
#include "constants.h"
#include "text-util.h"

Include dependency graph for old_controlizer.c:

Go to the source code of this file.

Macros
#define	LABEL_TABLES_SIZE   10
#define	ADD_PRED_IF_NOT_ALREADY_HERE(pred, c)   (gen_once(pred,control_predecessors(c)))
	In C, we can have some "goto" inside a block from outside, that translate as any complex control graph into an "unstructured" in the PIPS jargon. More...
#define	ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE(pred, c)   (gen_once(pred,gen_copy_seq(control_predecessors(c))))
#define	UPDATE_CONTROL(c, s, pd, sc)
	Update control c by setting its statement to s, by unioning its predecessor set with pd, and by setting its successor set to sc (i.e. More...
#define	PREDS_OF_SUCCS   1
#define	SUCCS_OF_PREDS   2

Functions
static bool	controlize (statement st, control pred, control succ, control c_res, hash_table used_labels)
	Computes in c_res the control node of the statement st whose predecessor control node is pred and successor succ. More...
static void	patch_references (int how, control fnode, control tnode)
	PATCH_REFERENCES replaces all occurrences of FNODE by TNODE in the predecessors or successors lists of its predecessors or successors list (according to HOW, PREDS_OF_SUCCS or SUCCS_OF_PREDS). More...
static control	make_conditional_control (statement st)
	Make a control node from a statement if needed. More...
static control	get_label_control (string name)
	Get the control node associated to a label name. More...
static void	update_used_labels (hash_table used_labels, string name, statement st)
	Add the reference to the label NAME in the statement ST. More...
static hash_table	union_used_labels (hash_table l1, hash_table l2)
	Unions 2 used-label hash maps. More...
static bool	covers_labels_p (statement st, hash_table used_labels)
	Compute whether all the label references in a statement are in a given label name to statement list mapping. More...
static void	add_proper_successor_to_predecessor (control pred, control c_res)
static bool	controlize_call (statement st, control pred, control succ, control c_res)
	CONTROLIZE_CALL controlizes the call C of statement ST in C_RES. More...
statement	loop_header (statement sl)
	LOOP_HEADER, LOOP_TEST and LOOP_INC build the desugaring phases of a do-loop L for the loop header (i=1), the test (i<10) and the increment (i=i+1). More...
statement	loop_test (statement sl)
statement	loop_inc (statement sl)
static bool	controlize_loop (statement st, loop l, control pred, control succ, control c_res, hash_table used_labels)
	CONTROLIZE_LOOP computes in C_RES the control graph of the loop L (of statement ST) with PREDecessor and SUCCessor. More...
static statement	whileloop_test (statement sl)
	Generate a test statement ts for exiting loop sl. More...
static bool	controlize_whileloop (statement st, whileloop l, control pred, control succ, control c_res, hash_table used_labels)
	CONTROLIZE_WHILELOOP computes in C_RES the control graph of the loop L (of statement ST) with PREDecessor and SUCCessor. More...
statement	forloop_header (statement sl)
statement	forloop_test (statement sl)
statement	forloop_inc (statement sl)
static bool	controlize_forloop (statement st, forloop l, control pred, control succ, control c_res, hash_table used_labels)
static void	move_declaration_control_node_declarations_to_statement (list ctls)
	Move all the declarations found in a list of control to a given statement. More...
static control	compact_list (list ctls, control c_end)
	Take a list of controls ctls coming from a controlize_list() and compact the successive statements, i.e. More...
static list	controlize_list_1 (list sts, control i_pred, control i_succ, control i_c_res, hash_table used_labels)
	Do the equivalent of a mapcar of controlize on statement list sts. More...
static bool	controlize_list (statement st, list sts, control pred, control succ, control c_res, hash_table used_labels)
	Computes in c_res the control graph of the list sts (of statement st) with pred predecessor and succ successor. More...
static bool	controlize_test (statement st, test t, control pred, control succ, control c_res, hash_table used_labels)
	Builds the control node of a statement st in c_res which is a test statement t. More...
static void	init_label (string name, statement st)
	INIT_LABEL puts the reference in the statement ST to the label NAME int the Label_statements table and allocate a slot in the Label_control table. More...
static void	create_statements_of_label (statement st)
	CREATE_STATEMENTS_OF_LABELS gathers in the Label_statements table all the references to the useful label of the statement ST. More...
static void	create_statements_of_labels (st)
static unstructured	simplified_unstructured (control top, control bottom, control res)
	SIMPLIFIED_UNSTRUCTURED tries to get rid of top-level and useless unstructured nodes. More...
unstructured	control_graph (statement st)
	CONTROL_GRAPH returns the control graph of the statement ST. More...

Variables
char	vcid_control_old_controlizer [] = "$Id: old_controlizer.c 23065 2016-03-02 09:05:50Z coelho $"
	old_controlizer.c More...
static list	Unreachable
	UNREACHABLE is the hook used as a predecessor of statements that are following a goto. More...
static hash_table	Label_statements
	LABEL_STATEMENTS maps label names to the list of statements where they appear (either as definition or reference). More...
static hash_table	Label_control
	LABEL_CONTROL maps label names to their (possible forward) control nodes. More...

Function Documentation

covers_labels_p()

static bool covers_labels_p ( statement  st, hash_table  used_labels  )

static

Compute whether all the label references in a statement are in a given label name to statement list mapping.

Parameters

st	is the statement we want to check if it owns all allusion to the given label name in the used_labels mapping
used_labels	is a hash table mapping a label name to a list of statement that use it, as their label or because it is a goto to it

Returns

true if all the label allusion in st are covered by the used_labels mapping.

ifdebug(5) {

pips_debug(5, "Statement %td (%p): \n ", statement_number(st), st);

print_statement(st);

}

For all the labels in used_labels:

The statements using label name in used_labels:

For all the statements associated to label name:

Verify that def is in all the statements associated to the label name according to used_labels.

Not useful to go on:

Definition at line 326 of file old_controlizer.c.

                                                    {
  // To quiet gcc
  pips_assert("Statement st is defined", !statement_undefined_p(st));
  /* ifdebug(5) { */
  /*   pips_debug(5, "Statement %td (%p): \n ", statement_number(st), st); */
  /*   print_statement(st); */
  /* } */
  /* For all the labels in used_labels: */
  HASH_MAP(name, sts, {
      /* The statements using label name in used_labels: */
      list stats = (list) sts;
 
      /* For all the statements associated to label name: */
      FOREACH(STATEMENT,
              def,
              (list) hash_get_default_empty_list(Label_statements, name)) {
        bool found = false;
        /* Verify that def is in all the statements associated to the
           label name according to used_labels. */
        FOREACH(STATEMENT, st, stats) {
          found |= st == def;
        }
 
        if (!found) {
          pips_debug(5, "does not cover label %s\n", (char *) name);
          /* Not useful to go on: */
          return(false);
        }
      }
    }, used_labels);
 
  ifdebug(5)
    fprintf(stderr, "covers its label usage\n");
 
  return(true);
}

References FOREACH, fprintf(), hash_get_default_empty_list(), HASH_MAP, ifdebug, Label_statements, pips_assert, pips_debug, STATEMENT, and statement_undefined_p.

Referenced by controlize_forloop(), controlize_list(), controlize_loop(), controlize_test(), and controlize_whileloop().

Here is the call graph for this function:

Here is the caller graph for this function:

create_statements_of_label()

static void create_statements_of_label ( statement  st )

static

CREATE_STATEMENTS_OF_LABELS gathers in the Label_statements table all the references to the useful label of the statement ST.

Note that for loops, the label in the DO statement is NOT introduced. Label_control is also created.

Definition at line 1797 of file old_controlizer.c.

{
    string name = entity_name(statement_label(st));
    instruction i;
 
    init_label(name, st);
 
    switch(instruction_tag(i = statement_instruction(st))) {
    case is_instruction_goto: {
        string where = entity_name(statement_label(instruction_goto(i)));
 
        init_label(where, st);
        break;
    }
 
    case is_instruction_unstructured:
        pips_internal_error("Found unstructured", "");
 
    default:
      ;
    }
}

References entity_name, init_label(), instruction_goto, instruction_tag, is_instruction_goto, is_instruction_unstructured, pips_internal_error, statement_instruction, and statement_label.

Referenced by create_statements_of_labels().

Here is the call graph for this function:

Here is the caller graph for this function:

get_label_control()

static control get_label_control ( string  name )

static

Get the control node associated to a label name.

It looks for the label name into the Label_control table.

The name must be the complete entity name, not a local or a user name.

Parameters

name	is the string name of the label entity

Returns

the associated control

Definition at line 242 of file old_controlizer.c.

                                              {
    control c;
 
    pips_assert("label is not the empty label", !empty_global_label_p(name)) ;
    c = (control)hash_get(Label_control, name);
    pips_assert("c is defined", c != (control) HASH_UNDEFINED_VALUE);
    pips_assert("c is a control", check_control(c));
    ifdebug(2) {
      check_control_coherency(c);
    }
    return(c);
}

References check_control(), check_control_coherency(), empty_global_label_p(), hash_get(), HASH_UNDEFINED_VALUE, ifdebug, Label_control, and pips_assert.

Referenced by compact_list(), and controlize().

Here is the call graph for this function:

Here is the caller graph for this function:

make_conditional_control()

static control make_conditional_control ( statement  st )

static

Make a control node from a statement if needed.

It is like make_control() except when the statement

Parameters

st	has a label and is thus already in Label_control

Returns

the new (in the case of a statement without a label) or already associated (in the case of a statement with a label) control node with the statement

It returns NULL if the statement has a label but it is not associated to any control node yet

No label, so there cannot be a control already associated by a label

Get back the control node associated with this statement label. Since we store control object in this hash table, use cast. We rely on the fact that NIL for a list is indeed NULL...

Definition at line 216 of file old_controlizer.c.

                                                      {
  string label = entity_name(statement_label(st));
 
  if (empty_global_label_p(label))
    /* No label, so there cannot be a control already associated by a
       label */
    return make_control(st, NIL, NIL);
  else
      /* Get back the control node associated with this statement
         label. Since we store control object in this hash table, use
         cast. We rely on the fact that NIL for a list is indeed
         NULL... */
    return (control)hash_get_default_empty_list(Label_control, label);
}

References empty_global_label_p(), entity_name, hash_get_default_empty_list(), Label_control, make_control(), NIL, and statement_label.

Referenced by control_graph(), controlize_forloop(), controlize_list(), controlize_list_1(), controlize_loop(), controlize_test(), and controlize_whileloop().

Here is the call graph for this function:

Here is the caller graph for this function:

move_declaration_control_node_declarations_to_statement()

static void move_declaration_control_node_declarations_to_statement ( list  ctls )

static

Move all the declarations found in a list of control to a given statement.

@ctls is a list of control nodes

It is useful in the controlizer to keep scoping of declarations even with unstructured that may destroy the variable scoping rules.

If there are conflict names on declarations, they are renamed.

It relies on correct calls to push_declarations()/push_declarations() before to track where to put the declarations.

FI: let's assume they have become scoping_statement_push/pop...

No block statement above, so it is hard to move something there :-)

The variables created in case of name conflict

Look for conflicting names:

There is a conflict name between a declaration in the current statement block and one in the statement block above:

Create a new variable with a non conflicting name:

Add the inner declaration to the upper statement later

Remove the inner declaration from the inner statement block:

Add all the declarations to the statement block above and keep the same order:

Replace all the references on old variables to references to the new ones in all the corresponding control nodes by in the code

We should free in some way the old variable...

Definition at line 976 of file old_controlizer.c.

                                                                   {
  statement s = scoping_statement_head();
  list declarations = statement_declarations(s);
  statement s_above = scoping_statement_nth(2);
  pips_debug(2, "Dealing with block statement %p included into block"
             " statement %p\n", s, s_above);
  if (s_above==NULL)
    /* No block statement above, so it is hard to move something there :-) */
    return;
 
  list declarations_above  = statement_declarations(s_above);
  list new_declarations = NIL;
  /* The variables created in case of name conflict*/
  list new_variables = NIL;
  hash_table old_to_new_variables = hash_table_make(hash_chunk, 0);
 
  /* Look for conflicting names: */
  FOREACH(ENTITY, e, declarations) {
    const char * name = entity_user_name(e);
    bool conflict = false;
    FOREACH(ENTITY, e_above, declarations_above) {
      const char * name_above = entity_user_name(e_above);
      pips_debug(2, "Comparing variables %s and %s\n",
                 entity_name(e), entity_name(e_above));
 
      if (strcmp(name, name_above) == 0) {
        /* There is a conflict name between a declaration in the current
           statement block and one in the statement block above: */
        conflict = true;
        break;
      }
    }
    entity v;
    if (conflict) {
      pips_debug(2, "Conflict on variable %s\n", entity_name(e));
 
      /* Create a new variable with a non conflicting name: */
      v = clone_variable_with_unique_name(e,
                                          s_above,
                                          "",
                                          "_",
                                          entity_to_module_entity(e));
      new_variables = gen_entity_cons(v , new_variables);
      hash_put_or_update(old_to_new_variables, e, v);
    }
    else
      v = e;
    /* Add the inner declaration to the upper statement later */
    new_declarations = gen_entity_cons(v , new_declarations);
  }
  /* Remove the inner declaration from the inner statement block:
   */
  gen_free_list(statement_declarations(s));
  statement_declarations(s) = NIL;
 
  /* Add all the declarations to the statement block above and keep the
     same order: */
  statement_declarations(s_above) = gen_nconc(declarations_above,
                                              gen_nreverse(new_declarations));
 
  /* Replace all the references on old variables to references to the new
     ones in all the corresponding control nodes by in the code */
  HASH_MAP(old, new, {
      FOREACH(CONTROL, c, ctls) {
        statement s = control_statement(c);
        replace_entity(s, old, new);
      }
      /* We should free in some way the old variable... */
    }, old_to_new_variables);
  hash_table_free(old_to_new_variables);
}

References clone_variable_with_unique_name(), CONTROL, control_statement, ENTITY, entity_name, entity_to_module_entity(), entity_user_name(), FOREACH, gen_entity_cons(), gen_free_list(), gen_nconc(), gen_nreverse(), hash_chunk, HASH_MAP, hash_put_or_update, hash_table_free(), hash_table_make(), NIL, pips_debug, replace_entity(), and statement_declarations.

Referenced by controlize_list().

Here is the call graph for this function:

Here is the caller graph for this function:

union_used_labels()

static hash_table union_used_labels ( hash_table  l1, hash_table  l2  )

static

Unions 2 used-label hash maps.

Parameters

l1	is an hash map
l2	is another hash map

Returns

the union of l1 and l2 interpreted as in the context of update_used_labels()

Definition at line 303 of file old_controlizer.c.

                                                   {
  HASH_MAP(name, sts, {
      FOREACH(STATEMENT, s, sts) {
        update_used_labels(l1, name, s);
      };
    }, l2);
  return l1;
}

References FOREACH, HASH_MAP, STATEMENT, and update_used_labels().

Referenced by controlize_forloop(), controlize_list(), controlize_loop(), controlize_test(), and controlize_whileloop().

Here is the call graph for this function:

Here is the caller graph for this function:

update_used_labels()

static void update_used_labels ( hash_table  used_labels, string  name, statement  st  )

static

Add the reference to the label NAME in the statement ST.

A used_label is a hash_table that maps the label name to the list of statements that references it.

A statement can appear many times for a label

Parameters

used_labels	is the hash table used to record the statements related to a label
name	is the label entity name
st	is the statement to be recorded as related to the label

Do something only of there is a label:

Get a previous list of statements related with this label:

Add the given statement to the list

If there was already something associated to the label, register the new list:

Or create a new entry:

Definition at line 269 of file old_controlizer.c.

                                             {
  list sts ;
 
  /* Do something only of there is a label: */
  if (!empty_global_label_p(name)) {
    list new_sts;
    /* Get a previous list of statements related with this label: */
    sts = hash_get_default_empty_list(used_labels, name) ;
    /* Add the given statement to the list */
    new_sts = CONS(STATEMENT, st, sts);
    if (hash_defined_p(used_labels, name))
      /* If there was already something associated to the label, register
         the new list: */
      hash_update(used_labels, name,  new_sts);
    else
      /* Or create a new entry: */
      hash_put(used_labels, name,  new_sts);
    debug(5, "update_used_labels", "Reference to statement %d seen\n",
          statement_number( st )) ;
  }
}

References CONS, debug(), empty_global_label_p(), hash_defined_p(), hash_get_default_empty_list(), hash_put(), hash_update(), STATEMENT, and statement_number.

Referenced by controlize(), and union_used_labels().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

vcid_control_old_controlizer

char vcid_control_old_controlizer[] = "$Id: old_controlizer.c 23065 2016-03-02 09:05:50Z coelho $"

old_controlizer.c

Definition at line 29 of file old_controlizer.c.