Controlizer phase to build the Hierarchical Control Flow Graph

lint More...

Collaboration diagram for Controlizer phase to build the Hierarchical Control Flow Graph:

Modules
	Desugaring functions used to transform
	non well structured à la Fortran do-loop into an equivalent code with tests and gotos.

Macros
#define	LABEL_TABLES_SIZE   10
#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 control	make_conditional_control (statement st)
	In C, we can have some "goto" inside a block from outside, that translates as any complex control graph into an "unstructured" in the PIPS jargon. 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)
	Mark a statement as related to a label. More...
static hash_table	union_used_labels (hash_table l1, hash_table l2)
	Unions 2 hash maps that list statements referencing labels into one. 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 local mapping. More...
static void	create_statements_of_label (statement st)
	Update the global module-level Label_statements table according to the labels a statement references. More...
static void	create_statements_of_labels (statement st)
	Initialize the global Label_statements mapping for the module that associates for any label in the module the statements that refer to it. More...
static bool	controlize_loop (control c_res, control succ, hash_table used_labels)
	Computes the control graph of a Fortran do-loop statement. More...
static bool	controlize_forloop (control c_res, control succ, hash_table used_labels)
	Computes the control graph of a C for loop statement. More...
static bool	controlize_whileloop (control c_res, control succ, hash_table used_labels)
	Computes the control graph of a Fortran or C while loop statement. More...
static bool	controlize_repeatloop (control c_res, control succ, hash_table used_labels)
	Computes the control graph of a C repeat until loop statement. More...
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...
control	find_exit_control_node (list ctls, control succ)
	Find the exit node of a sub-CFG defined by the list of nodes ctls and by the first node to execute when finished. More...
control	find_or_create_exit_control_node (list ctls, control succ)
	FI: remake of function above, incomplete backward approach, now obsolete because the forward approach works. More...
static bool	controlize_sequence (control c_res, control succ, hash_table used_labels)
	Computes the control graph of a sequence statement. More...
static bool	controlize_test (control c_res, control succ, hash_table used_labels)
	Builds the control node of a test statement. More...
static bool	controlize_goto (control c_res, control succ, hash_table used_labels)
	Deal with "goto" when building the HCFG. More...
static bool	controlize_call (control c_res, control succ)
	Controlize a call statement. More...
bool	controlize_statement (control c_res, control succ, hash_table used_labels)
	Controlize a statement that is in a control node, that is restructure it to have a HCFG recursively (a hierarchical control flow graph). More...
statement	hcfg (statement st)
	Compute the hierarchical control flow graph (HCFG) of a statement. More...
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 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 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_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
static hash_table	Label_statements
	This maps label names to the list of statements where they appear (either as definition or reference). More...
static hash_table	Label_control
	This maps label names to their (possible forward) control nodes. 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...

Detailed Description

lint

It computes the Hierarchical Control Flow Graph of a given statement according the control hierarchy.

It is used in PIPS to transform the output of the parsers (the PARSED_CODE resource) into HCFG code (the CODE resource).

For example if there are some "goto" in a program, it will encapsulate the unstructured graph into an "unstructured" object covering all the gotos and their label targets to localize the messy part. Then this object is put into a normal statement so that, seen from above, the code keep a good hierarchy.

In PIPS the RI (Internal Representation or AST) is quite simple so that it is easy to deal with. But the counterpart is that some complex control structures need to be "unsugared". For example switch/case/break/default are transformed into tests, goto and label, for(;;) with break or continue are transformed into while() loops with goto/label, and so on. It is up to the prettyprinter to recover the high level construction if needed (...and possible).

In the case of C, it is far more complicated than with Fortran77 that was targeted by PIPS at the beginning because we need to deal with variable scoping according to their block definitions that may not be the same hierarchy that the HCFG, for example when you have a goto inside a block from outside and when you have local variables in the block. In C99 it is even worse since you can have executable declarations.

There are other phases in PIPS that can be used later to operate on the CODE to optimize it further.

Even if there is no fundamental reason that we cannot controlize an already controlized code, it is not implemented yet. For example, it could be useful to modify some CODE by adding some goto or complex control code and call again the controlizer on the CODE to have nice unstructured back instead of building correct unstructured statements from scratch or using some CODE dump-and-reparse as it is done in some PIPS phases (outliner...).

TODO: a zen-er version of the recursion that avoid passing along the successor everywhere since we know at entry that it is the only successor of the main control node.

This is the new version of the controlizer version rewritten by Ronan.nosp@m..Ker.nosp@m.yell@.nosp@m.hpc-.nosp@m.proje.nosp@m.ct.c.nosp@m.om

It computes the Hierarchical Control Flow Graph of a given statement according the control hierarchy.

It is used in PIPS to transform the output of the parsers (the PARSED_CODE resource) into HCFG code (the PARSED_CODE resource).

For example if there are some "goto" in a program, it will encapsulated the unstructured graph in an "unstructured" object covering all the goto and their label targets to localize the messy part and this object is put into a normal statement so that seen from above the code keep a good hierarchy.

In PIPS the RI (Internal Representation or AST) is quite simple so that it is easy to deal with. But the counterpart is that some complex control structures need to be "unsugared". For example switch/case/break/default are transformed into tests, goto and label, for(;;) with break or continue are transformed into while() loops with goto/label, and so on.

There are other phases in PIPS that can be used later to operate on the CODE to optimize it further.

WARNINGS:

. Temporary locations malloc()ed while recursing in the process are often not freed (to be done latter ... if required)

. The desugaring of DO loops is not perfect (in case of side-effects inside loop ranges.

Pierre Jouvelot (27/5/89) <- this is a French date :-)

MODIFICATIONS (historian fun):

. hash_get interface modification: in one hash table an undefined key meant an error; in another one an undefined key was associated to the default value empty_list; this worked as long as NULL was returned as NOT_FOUND value (i.e. HASH_UNDEFINED_VALUE); this would work again if HASH_UNDEFINED_VALUE can be user definable; Francois Irigoin, 7 Sept. 90

Macro Definition Documentation

ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE

#define ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE	(		pred,
			c
	)		(gen_once(pred,gen_copy_seq(control_predecessors(c))))

Definition at line 151 of file old_controlizer.c.

ADD_PRED_IF_NOT_ALREADY_HERE

#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.

Unfortunately, that means it break the structured block nesting that may carry declarations with the scoping information.

So we need to track this scope information independently of the control graph. This is the aim of this declaration scope stack that is used to track scoping during visiting the RI. FI -> PJ:

The naming for ADD_PRED et ADD_SUCC is misleading. ADD_SUCC is in fact a SET_SUCC. ADD_PRED is UNION_PRED. When used to Newgen but not to control, ADD_SUCC reduces readability.

Furthermore, ADD_SUCC() is dangerous when used on a control that is a test since the position in the successor list is significant. true successors are in the odd positions (the first element is of rank one). false successors are in the odd position. Add control "pred" to the predecessor set of control c if not already here

Definition at line 150 of file old_controlizer.c.

LABEL_TABLES_SIZE [1/2]

#define LABEL_TABLES_SIZE   10

Definition at line 115 of file controlizer.c.

LABEL_TABLES_SIZE [2/2]

#define LABEL_TABLES_SIZE   10

Definition at line 101 of file old_controlizer.c.

PREDS_OF_SUCCS

#define PREDS_OF_SUCCS   1

Definition at line 171 of file old_controlizer.c.

SUCCS_OF_PREDS

#define SUCCS_OF_PREDS   2

Definition at line 172 of file old_controlizer.c.

UPDATE_CONTROL

#define UPDATE_CONTROL	(		c,
			s,
			pd,
			sc
	)

Value:

        { \
        control_statement(c)=s; \
        MAPL(preds, {control_predecessors(c) = \
                              ADD_PRED_IF_NOT_ALREADY_HERE(CONTROL(CAR(preds)), c);}, \
              pd); \
    gen_free_list(pd);\
    gen_free_list( control_successors(c));\
        control_successors(c)=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.

previous successors are lost, but not previous predecessors).

Note: This macro does not preserve the consistency of the control flow graph as pd's successor list and sc predecessor list are not updated.

Definition at line 161 of file old_controlizer.c.

Function Documentation

add_proper_successor_to_predecessor()

static void add_proper_successor_to_predecessor ( control  pred, control  c_res  )

static

Replaces the following statement:

control_successors(pred) = ADD_SUCC(c_res, pred);

Usually, too much of a mess: do not try to be too strict!

Do whatever was done before and let memory leak!

Definition at line 365 of file old_controlizer.c.

{
  /* Replaces the following statement: */
  /* control_successors(pred) = ADD_SUCC(c_res, pred); */
 
  /* Usually, too much of a mess: do not try to be too strict! */
  /*
  if(statement_test_p(control_statement(pred))) {
    control_successors(pred) = gen_nconc(control_successors(pred),
                                         CONS(CONTROL, c_res, NIL));
    pips_assert("While building the CFG, "
                "a test control node may have one or two successors",
                gen_length(control_successors(pred))<=2);
  }
  else {
    if(gen_length(control_successors(pred))==0) {
      control_successors(pred) = CONS(CONTROL, c_res, NIL);
    }
    else if(gen_length(control_successors(pred))==1) {
      if(gen_in_list_p(succ,control_successors(pred))) {
        ;
      }
      else {
        pips_internal_error("Two or more candidate successors "
                            "for a standard statement: %p and %p\n",
                            succ, CONTROL(CAR(control_successors(pred))));
      }
    }
    else {
      pips_internal_error("Two or more successors for non-test node %p",
                          pred);
    }
  }
  */
 
  if(statement_test_p(control_statement(pred))) {
    if(!gen_in_list_p(c_res, control_successors(pred))) {
      control_successors(pred) = gen_nconc(control_successors(pred),
                                           CONS(CONTROL, c_res, NIL));
    }
    pips_assert("While building the CFG, "
                "a test control node may have one or two successors",
                gen_length(control_successors(pred))<=2);
  }
  else {
    /* Do whatever was done before and let memory leak! */
    gen_free_list(control_successors(pred));
    control_successors(pred) = CONS(CONTROL, c_res, NIL);
  }
}

References CONS, CONTROL, control_statement, control_successors, gen_free_list(), gen_in_list_p(), gen_length(), gen_nconc(), NIL, pips_assert, and statement_test_p().

Referenced by controlize(), controlize_call(), controlize_forloop(), controlize_loop(), controlize_test(), and controlize_whileloop().

Here is the call graph for this function:

Here is the caller graph for this function:

compact_list()

static control compact_list ( list  ctls, control  c_end  )

static

Take a list of controls ctls coming from a controlize_list() and compact the successive statements, i.e.

concatenates (i=1) followed by (j=2) in a single control with a block statement (i=1;j=2).

Returns

the last control node of the remaining control list. It may not be c_end if this one has been fused with a previous control node.

Added a set to avoid investigating a removed node. Many memory leaks removed. RK.

This procedure cannot be replaced by fuse_sequences_in_unstructured() since the API is not the same and because of various goto from/to outside, this control list may belong to quite larger unstructured.

Pointer to the end of the current unstructured:

Empty statement control list, clearly nothing to do:

This is the iterator on the first element of the control list:

Do not reprocess an already seen node.

We are at a non structured node or at the exit: keep the node and go on inspecting next node from the list. RK

Ok, succ is defined. RK

Verify if the control node is not reachable on its label:

There is a label that may be used on this control node: do not fuse

This happens quite often in Syntax with no consequences; this leads to a core dump for C_syntax/block_scope13.c

Do not fuse: go to next control node:

If it is not a loop on c_res, fuse the nodes:

You need a new block to fuse and to respect the scopes

Remove the useless control:

We are at the end and the last node has disappeared... Update the pointer to the new one:

Definition at line 1063 of file old_controlizer.c.

{
  control c_res;
  set processed_nodes;
  /* Pointer to the end of the current unstructured: */
  control c_last = c_end ;
 
  ifdebug(5) {
    pips_debug(5, "Begin with list c_end %p, ctls:", c_end);
    display_address_of_control_nodes(ctls);
    fprintf(stderr, "\n");
  }
 
  if (ENDP(ctls)) {
    /* Empty statement control list, clearly nothing to do: */
    return c_last;
  }
 
  processed_nodes = set_make(set_pointer);
 
  /* This is the iterator on the first element of the control list: */
  c_res = CONTROL(CAR(ctls));
 
  for(ctls = CDR(ctls); !ENDP(ctls); ctls = CDR(ctls)) {
    cons *succs, *succs_of_succ;
    instruction i, succ_i;
    statement st, succ_st;
    control succ;
 
    if (set_belong_p(processed_nodes, (char *) c_res)) {
      /* Do not reprocess an already seen node. */
      c_res = CONTROL(CAR(ctls));
      continue;
    }
 
    if (gen_length(succs=control_successors(c_res)) != 1 ||
        gen_length(control_predecessors(succ=CONTROL(CAR(succs)))) != 1 ||
        gen_length(succs_of_succ=control_successors(succ)) != 1 ||
        CONTROL(CAR(succs_of_succ)) == c_res ) {
      /* We are at a non structured node or at the exit: keep
         the node and go on inspecting next node from the
         list. RK */
      c_res = CONTROL(CAR(ctls));
      continue;
    }
 
    st = control_statement(c_res) ;
 
    // NL: If it's uncomment, it remove some pragma in some case, I don't
    // know why. For instance C_syntax/pragma05
    // // if there is an extension for the statement don't make fusion
    // if (!empty_extensions_p(statement_extensions(st))) {
    //   c_res = CONTROL(CAR(ctls));
    //   continue;
    // }
 
    ifdebug(1) {
      statement_consistent_p(st);
      pips_assert("st is a block or a continue or st carries no delarations",
          statement_block_p(st)
          || continue_statement_p(st)
          || ENDP(statement_declarations(st)));
    }
    /* Ok, succ is defined. RK */
    succ_st = control_statement(succ);
    set_add_element(processed_nodes, processed_nodes, (char *) succ);
 
    if(!statement_undefined_p(control_statement(succ))
        && !entity_empty_label_p(statement_label(control_statement(succ)))
        && !return_label_p(entity_name(statement_label(control_statement(succ))))) {
      /* Verify if the control node is not reachable on its label: */
      entity l = statement_label(control_statement(succ));
      string ln = entity_name(l);
      control c = get_label_control(ln);
      if(!control_undefined_p(c)) {
        /* There is a label that may be used on this control node: do
               not fuse */
        if (c==succ) {
          /* This happens quite often in Syntax with no
             consequences; this leads to a core dump for
             C_syntax/block_scope13.c */
          pips_debug(2, "Do not fuse control %p since we will have a latent goto on it through label \"%s\"\n",
              c_res, ln);
          /* Do not fuse: go to next control node: */
          c_res = CONTROL(CAR(ctls));
          continue;
        }
        else
          pips_internal_error("Inconsistent hash table Label_control: "
              "same label points towards two different controls");
      }
    }
    if(c_res != succ) {
      /* If it is not a loop on c_res, fuse the nodes: */
      if((statement_block_p(st) && !ENDP(statement_declarations(st)))
          || (statement_block_p(succ_st) && !ENDP(statement_declarations(succ_st)))
          || (statement_block_p(succ_st) && !empty_extensions_p(statement_extensions(succ_st)))
          ) {
        /* You need a new block to fuse and to respect the scopes */
        i = make_instruction_block(CONS(STATEMENT, st,
            CONS(STATEMENT, succ_st, NIL)));
        control_statement(c_res) =
            make_statement(entity_empty_label(),
                STATEMENT_NUMBER_UNDEFINED,
                STATEMENT_ORDERING_UNDEFINED,
                string_undefined,
                i,NIL,NULL,
                empty_extensions (), make_synchronization_none());
        ;
      }
      else {
        if(!ENDP(statement_declarations(st))
            && !continue_statement_p(st)) {
          pips_user_warning("Declarations carried by a statement \"%s\""
              " which is not a block nor a continue!\n",
              statement_identification(st));
        }
        if(!instruction_block_p(i=statement_instruction(st))) {
          i = make_instruction_block(CONS(STATEMENT, st, NIL));
          control_statement(c_res) =
              make_statement(entity_empty_label(),
                  STATEMENT_NUMBER_UNDEFINED,
                  STATEMENT_ORDERING_UNDEFINED,
                  string_undefined,
                  i,NIL,NULL,
                  empty_extensions (), make_synchronization_none());
        }
        if(instruction_block_p(succ_i=statement_instruction(succ_st))){
          instruction_block(i) =
              gen_nconc(instruction_block(i),
                  instruction_block(succ_i));
          pips_debug(8, "Free statement %p with identification %s from control succ %p\n",
              succ_st, statement_identification(succ_st), succ);
          statement_instruction(succ_st) = instruction_undefined;
          free_statement(succ_st);
          succ_st = statement_undefined;
          control_statement(succ) = statement_undefined;
        }
        else {
          instruction_block(i) =
              gen_nconc(instruction_block(i),
                  CONS(STATEMENT, succ_st, NIL));
        }
      }
      ifdebug(1) {
        pips_assert("control succ and its statement are consistent",
            control_consistent_p(succ));
      }
      /* Remove the useless control: */
      control_statement(succ) = statement_undefined;
      remove_a_control_from_an_unstructured(succ);
    }
 
    if(succ == c_last) {
      /* We are at the end and the last node has
         disappeared... Update the pointer to the new one: */
      c_last = c_res;
      break;
    }
    ifdebug(1) {
      statement_consistent_p(st);
      statement_consistent_p(succ_st);
    }
  }
  set_free(processed_nodes);
  return c_last;
}

References CAR, CDR, CONS, continue_statement_p(), CONTROL, control_consistent_p(), control_predecessors, control_statement, control_successors, control_undefined_p, display_address_of_control_nodes(), empty_extensions(), empty_extensions_p(), ENDP, entity_empty_label(), entity_empty_label_p(), entity_name, fprintf(), free_statement(), gen_length(), gen_nconc(), get_label_control(), ifdebug, instruction_block, instruction_block_p, instruction_undefined, make_instruction_block(), make_statement(), make_synchronization_none(), NIL, pips_assert, pips_debug, pips_internal_error, pips_user_warning, remove_a_control_from_an_unstructured(), return_label_p(), set_add_element(), set_belong_p(), set_free(), set_make(), set_pointer, STATEMENT, statement_block_p, statement_consistent_p(), statement_declarations, statement_extensions, statement_identification(), statement_instruction, statement_label, STATEMENT_NUMBER_UNDEFINED, STATEMENT_ORDERING_UNDEFINED, statement_undefined, statement_undefined_p, and string_undefined.

Referenced by controlize_list().

Here is the call graph for this function:

Here is the caller graph for this function:

control_graph()

unstructured control_graph

(

statement

st

)

CONTROL_GRAPH returns the control graph of the statement ST.

Since the controlizer does not seem to accept GOTO inside sequence from outside but it appears in the code with READ/WRITE with I/O exceptions (end=, etc), first remove useless blocks. RK

To track declaration scoping independently of control structure:

FI: structured or not, let's build an unstructured...

Clean up scoping stack:

The statement st is not consistent anymore here.

Since the controlizer is a sensitive pass, avoid leaking basic errors...

Parameters

st

t

Definition at line 2190 of file old_controlizer.c.

{
    control result, top, bottom;
    hash_table used_labels = hash_table_make(hash_string, 0);
    unstructured u = unstructured_undefined;
 
    ifdebug(1) {
      pips_assert("Statement should be OK.", statement_consistent_p(st));
      set_bool_property("PRETTYPRINT_BLOCKS", true);
      set_bool_property("PRETTYPRINT_EMPTY_BLOCKS", true);
    }
 
    /* Since the controlizer does not seem to accept GOTO inside
       sequence from outside but it appears in the code with
       READ/WRITE with I/O exceptions (end=, etc), first remove
       useless blocks. RK */
    clean_up_sequences(st);
 
    ifdebug(1) {
      statement_consistent_p(st);
    }
 
    Label_statements = hash_table_make(hash_string, LABEL_TABLES_SIZE);
    Label_control = hash_table_make(hash_string, LABEL_TABLES_SIZE);
    create_statements_of_labels(st);
 
    result = make_conditional_control(st);
    top = make_control(make_plain_continue_statement(), NIL, NIL);
    bottom = make_control(make_plain_continue_statement(), NIL, NIL);
    Unreachable = NIL;
 
    ifdebug(1) {
      statement_consistent_p(st);
    }
 
    /* To track declaration scoping independently of control structure: */
    make_scoping_statement_stack();
 
    /* FI: structured or not, let's build an unstructured... */
    (void) controlize(st, top, bottom, result, used_labels);
 
    /* Clean up scoping stack: */
    free_scoping_statement_stack();
 
    /* The statement st is not consistent anymore here. */
    //statement_consistent_p(st);
 
    if(!ENDP(Unreachable)) {
      pips_user_warning("Some statements are unreachable\n");
      pips_user_warning("Unreachable statements:\n");
      FOREACH(STATEMENT, s, Unreachable) {
        // This interesting information makes library control dependent on library prettyprint
        pips_user_warning("Statement:\n%s\n", text_to_string(statement_to_text(s)));
          if (statement_number(s) != -1) {
            pips_user_warning("Statement number: %d\n", statement_number(s));
          }
      }
    }
    hash_table_free(Label_statements);
    hash_table_free(Label_control);
    hash_table_free(used_labels);
 
    u = simplified_unstructured(top, bottom, result);
 
    ifdebug(5) {
      pips_debug(1,
          "Nodes in unstructured %p (entry %p, exit %p) from entry:\n",
          u, unstructured_control(u), unstructured_exit(u));
      display_linked_control_nodes(unstructured_control(u));
      pips_debug(1, "Accessible nodes from exit:\n");
      display_linked_control_nodes(unstructured_exit(u));
    }
 
    /* Since the controlizer is a sensitive pass, avoid leaking basic
       errors... */
    ifdebug(1) {
      unstructured_consistent_p(u);
    }
 
    reset_unstructured_number();
    unstructured_reorder(u);
 
    ifdebug(1) {
      check_control_coherency(unstructured_control(u));
      check_control_coherency(unstructured_exit(u));
      pips_assert("Unstructured should be OK.", unstructured_consistent_p(u));
    }
 
    return(u);
}

controlize()

static bool controlize ( statement  st, control  pred, control  succ, control  c_res, hash_table  used_labels  )

static

Computes in c_res the control node of the statement st whose predecessor control node is pred and successor succ.

The used_LABELS is modified to deal with local use of labels.

The invariant is that it links predecessors and successors of c_res, updates the successors of pred and the predecessors of succ.

In fact, it cannot update the successors of pred because it cannot know which successor of pred c_RES is when pred is associated to a test. pred and c_res must be linked together when you enter controlize(), or they must be linked later by the caller. But they cannot be linked here thru the successor list of pred and, if the consistency is true here, they cannot be linked either by the predecessor list of succ. If they are linked later, it is useless to pass pred down. If they are linked earlier, they might have to be unlinked when structured code is found.

Returns

true if the current statement isn't a structured control.

print_statement(st);

A C block may have a label and even goto from outside on it.

A block may only contain declarations with initializations and side effects on the store

Empty block

If st carries local declarations, so should the statement associated to c_res.

Get the label name of the statement the goto point to:

Memory leak in CONS(CONTROL, pred, NIL). Also forgot to unlink the predecessor of the former successor of pred. RK

control_successors(pred) = ADD_SUCC(c_res, pred);

I do not know why, but my following code does not work. So I put back former one above... :-( RK.

FI: IO calls may have control effects; they should be handled here!

SG+EC:some label may have been lost in the process fix it here instead of understanding why

PJ: controlize_call() controlize any "nice" statement

no break

pips_debug(1, "st %p at exit:\n", st);

print_statement(st);

The declarations may be preserved at a lower level if(!ENDP(statement_declarations(st)) && ENDP(statement_declarations(control_statement(c_res)))) { pips_internal_error("Lost local declarations"); }

Update the association between the current statement and its label:

Definition at line 1969 of file old_controlizer.c.

{
  instruction i = statement_instruction(st);
  entity elabel = statement_label(st);
  string label = entity_name(elabel);
  bool controlized = false;
  control n_succ = control_undefined; // To be used in case of goto
 
  ifdebug(5) {
    pips_debug(1,
        "Begin with (st = %p, pred = %p, succ = %p, c_res = %p)\n"
        "st at entry:\n",
        st, pred, succ, c_res);
    ifdebug(1) {
      statement_consistent_p(st);
    }
    /* print_statement(st); */
    /*
    pips_assert("pred is a predecessor of c_res",
        gen_in_list_p(pred, control_predecessors(c_res)));
    pips_assert("c_res is a successor of pred",
        gen_in_list_p(c_res, control_successors(pred)));
     */
    pips_debug(1, "Begin with result c_res %p:\n", c_res);
    display_linked_control_nodes(c_res);
    check_control_coherency(pred);
    check_control_coherency(succ);
    check_control_coherency(c_res);
  }
 
  switch(instruction_tag(i)) {
  case is_instruction_block: {
    /* A C block may have a label and even goto from outside on it. */
    /* A block may only contain declarations with initializations
         and side effects on the store */
    if(ENDP(instruction_block(i))) {
      /* Empty block */
      controlized = controlize_call(st, pred, succ, c_res);
      ifdebug(1) {
        statement_consistent_p(st);
      }
    }
    else {
      ifdebug(1) {
        statement_consistent_p(st);
      }
      scoping_statement_push(st);
      controlized = controlize_list(st, instruction_block(i),
          pred, succ, c_res, used_labels);
      ifdebug(1) {
        statement_consistent_p(st);
      }
 
      ifdebug(5) {
        pips_debug(1, "CFG consistency check before list6 controlization."
            " Control \"pred\" %p:\n", pred);
        display_linked_control_nodes(pred);
        pips_debug(1, "Control \"succ\" %p:\n", succ);
        display_linked_control_nodes(succ);
 
        check_control_coherency(pred);
        check_control_coherency(succ);
        check_control_coherency(c_res);
      }
      /* If st carries local declarations, so should the statement
           associated to c_res. */
      if(controlized && !ENDP(statement_declarations(st))
          && ENDP(statement_declarations(control_statement(c_res)))) {
        print_entities(statement_declarations(st));
        pips_user_warning("Some local declarations may have been lost\n");
      }
      scoping_statement_pop();
      ifdebug(1) {
        statement_consistent_p(st);
      }
    }
    break;
  }
  case is_instruction_test:
    controlized = controlize_test(st, instruction_test(i),
        pred, succ, c_res, used_labels);
    ifdebug(1) {
      statement_consistent_p(st);
    }
    break;
  case is_instruction_loop:
    controlized = controlize_loop(st, instruction_loop(i),
        pred, succ, c_res, used_labels);
    ifdebug(1) {
      statement_consistent_p(st);
    }
    break;
  case is_instruction_whileloop:
    controlized = controlize_whileloop(st, instruction_whileloop(i),
        pred, succ, c_res, used_labels);
    ifdebug(1) {
      statement_consistent_p(st);
    }
    break;
  case is_instruction_goto: {
    /* Get the label name of the statement the goto point to: */
    string name = entity_name(statement_label(instruction_goto(i)));
    statement nop = make_continue_statement(statement_label(st));
 
    statement_number(nop) = statement_number(st);
    statement_comments(nop) = statement_comments(st);
    // Well, let's try this for the time being. What is the scope?!?
    statement_declarations(nop) = statement_declarations(st);
    statement_decls_text(nop) = statement_decls_text(st);
 
    n_succ = get_label_control(name);
 
    ifdebug(5) {
      pips_debug(1, "CFG consistency check before goto controlization."
          " Control \"pred\" %p:\n", pred);
      display_linked_control_nodes(pred);
      pips_debug(1, "Control \"n_succ\" %p:\n", n_succ);
      display_linked_control_nodes(n_succ);
      check_control_coherency(pred);
      check_control_coherency(n_succ);
      check_control_coherency(c_res);
    }
 
    /* Memory leak in CONS(CONTROL, pred, NIL). Also forgot to
           unlink the predecessor of the former successor of pred. RK */
    /* control_successors(pred) = ADD_SUCC(c_res, pred); */
    add_proper_successor_to_predecessor(pred, c_res);
    UPDATE_CONTROL(c_res, nop,
        CONS(CONTROL, pred, NIL),
        CONS(CONTROL, n_succ, NIL));
    control_predecessors(n_succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_res, n_succ);
    /* I do not know why, but my following code does not work. So
           I put back former one above... :-( RK. */
#if 0
    /* Use my procedures instead to set a GOTO from pred to
           c_res. RK */
    if (gen_length(control_successors(pred)) == 1)
      unlink_2_control_nodes(pred, CONTROL(CAR(control_successors(pred))));
    link_2_control_nodes(pred, c_res);
    link_2_control_nodes(c_res, n_succ);
    /* Hmmm... A memory leak on the previous statement of c_res? */
    control_statement(c_res) = nop;
#endif
    update_used_labels(used_labels, name, st);
    controlized = true;
    break;
  }
  case is_instruction_call:
    /* FI: IO calls may have control effects; they should be handled here! */
    controlized = controlize_call(st, pred, succ, c_res);
    ifdebug(1) {
      statement_consistent_p(st);
    }
    break;
  case is_instruction_forloop:
    pips_assert("We are really dealing with a for loop",
        instruction_forloop_p(statement_instruction(st)));
    controlized = controlize_forloop(st, instruction_forloop(i),
        pred, succ, c_res, used_labels);
    ifdebug(1) {
      statement_consistent_p(st);
    }
    /* SG+EC:some label may have been lost in the process
           fix it here instead of understanding why */
    if(!same_entity_p(statement_label(st),elabel)) {
      statement_label(st)=elabel;
    }
    break;
  case is_instruction_expression:
    /* PJ: controlize_call() controlize any "nice" statement */
    controlized = return_instruction_p(i) || controlize_call(st, pred, succ, c_res);
 
    ifdebug(1) {
      statement_consistent_p(st);
    }
    break;
  case is_instruction_unstructured:
    pips_internal_error("is_instruction_unstructured not treated, never happen?");
    break;
  case is_instruction_multitest:
    pips_internal_error("is_instruction_multitest not treated, never happen?");
    break;
  default:
    pips_internal_error("Unknown instruction tag %d", instruction_tag(i));
    /* no break */
  }
 
  ifdebug(5) {
    statement_consistent_p(st);
    /* pips_debug(1, "st %p at exit:\n", st); */
    /* print_statement(st); */
    pips_debug(1, "Resulting Control c_res %p at exit:\n", c_res);
    display_linked_control_nodes(c_res);
    fprintf(stderr, "---\n");
    /* The declarations may be preserved at a lower level
      if(!ENDP(statement_declarations(st))
          && ENDP(statement_declarations(control_statement(c_res)))) {
        pips_internal_error("Lost local declarations");
      }
     */
    check_control_coherency(pred);
    if(control_undefined_p(n_succ))
      check_control_coherency(succ);
    else
      check_control_coherency(n_succ);
    check_control_coherency(c_res);
  }
 
  /* Update the association between the current statement and its label:
   */
  update_used_labels(used_labels, label, st);
 
  return(controlized);
}

References ADD_PRED_IF_NOT_ALREADY_HERE, add_proper_successor_to_predecessor(), CAR, check_control_coherency(), CONS, CONTROL, control_predecessors, control_statement, control_successors, control_undefined, control_undefined_p, controlize_call(), controlize_forloop(), controlize_list(), controlize_loop(), controlize_test(), controlize_whileloop(), display_linked_control_nodes(), ENDP, entity_name, fprintf(), gen_length(), get_label_control(), ifdebug, instruction_block, instruction_forloop, instruction_forloop_p, instruction_goto, instruction_loop, instruction_tag, instruction_test, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_multitest, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, link_2_control_nodes(), make_continue_statement(), NIL, pips_assert, pips_debug, pips_internal_error, pips_user_warning, print_entities(), return_instruction_p(), same_entity_p(), statement_comments, statement_consistent_p(), statement_declarations, statement_decls_text, statement_instruction, statement_label, statement_number, unlink_2_control_nodes(), UPDATE_CONTROL, and update_used_labels().

Referenced by control_graph(), controlize_forloop(), 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:

controlize_call() [1/2]

static bool controlize_call ( control  c_res, control  succ  )

static

Controlize a call statement.

The deal is to correctly manage STOP; since we don't know how to do it yet, we assume this is a usual call with a continuation !

To avoid non-standard successors, IO statement with multiple continuations are not dealt with here. The END= and ERR= clauses are simulated by hidden tests.

Parameters

[in]	c_res	is the control node with a call statement to controlize
[in]	succ	is the control node successor of c_res

Returns

false since we do nothing, so no non-structured graph generation yet...

Definition at line 2455 of file controlizer.c.

{
  statement st = control_statement(c_res);
  pips_debug(5, "(st = %p, c_res = %p, succ = %p)\n",
             st, c_res, succ);
 
  return false;
}

References control_statement, and pips_debug.

Referenced by controlize_statement().

Here is the caller graph for this function:

controlize_call() [2/2]

static bool controlize_call ( statement  st, control  pred, control  succ, control  c_res  )

static

CONTROLIZE_CALL controlizes the call C of statement ST in C_RES.

The deal is to correctly manage STOP; since we don't know how to do it, so we assume this is a usual call with a continuation !!

To avoid non-standard successors, IO statement with multiple continuations are not dealt with here. The END= and ERR= clauses are simulated by hidden tests.

control_successors(pred) = ADD_SUCC(c_res, pred);

Definition at line 425 of file old_controlizer.c.

{
  pips_debug(5, "(st = %p, pred = %p, succ = %p, c_res = %p)\n",
             st, pred, succ, c_res);
 
  UPDATE_CONTROL(c_res, st,ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE(pred, c_res),
                 CONS(CONTROL, succ, NIL));
 
  /* control_successors(pred) = ADD_SUCC(c_res, pred); */
  add_proper_successor_to_predecessor(pred, c_res);
  control_predecessors(succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_res, succ);
  return(false);
}

References ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE, ADD_PRED_IF_NOT_ALREADY_HERE, add_proper_successor_to_predecessor(), CONS, CONTROL, control_predecessors, NIL, pips_debug, and UPDATE_CONTROL.

Referenced by controlize().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_forloop() [1/2]

static bool controlize_forloop ( control  c_res, control  succ, hash_table  used_labels  )

static

Computes the control graph of a C for loop statement.

Parameters

[in,out]	c_res	is the entry control node with the for loop statement to controlize. If the for loop has complex control code such as some goto to outside, it is transformed into an equivalent control graph.
[in,out]	succ	must be the control node successor of c_res that will be the current end of the control node sequence and an exit node
[in,out]	used_labels	is a hash table mapping a label name to a list of statements that use it, as their label or because it is a goto to it

Returns

true if the code is not a structured control.

To track the statement related to labels inside the loop body:

Remove the loop body from the loop just in case we want to prettyprint our work in progress:

Create a control node to host the loop body and insert it in the control graph:

We also insert a dummy node between the body and the exit that will be used for the incrementation because if the control body has goto to succ node, we will have trouble to insert it later:

TODO switch(get_prettyprint_language_tag()) { case is_language_fortran: case is_language_fortran95: cs = strdup(concatenate(prev_comm, get_comment_sentinel(), " DO loop ", lab, " with exit had to be desugared\n", NULL)); break; case is_language_c: cs = prev_comm; break; default: pips_internal_error("This language is not handled !"); break; }

Recurse by controlizing inside the loop:

First the easy way. We have a kindly control-localized loop body, revert to the original code

Remove the control node from the control graph by carefully relinking around:

Remove also the dummy increment node that has not been used either:

Move the loop body into its own loop:

We are in trouble since the loop body is not locally structured, there are goto from inside or outside the loop body. So we replace the do-loop with a desugared version with an equivalent control graph.

Update the increment control node with the real computation:

First remove the dummy statement added above:

And put "i = i + s" instead:

Now build the desugared loop:

We can replace the former loop statement by the new header. That means that all pragma, comment, extensions, label on the previous loop stay on this.

Add the continuation test between the header and the body that are already connected:

Detach the increment node from the loop exit

And reconnect it to the test node to make the loop:

Add the else branch of the test toward the loop exit:

Detach the succ node from the body node

We can remove

Keep track of labels that were used by the statements of the loop:

Definition at line 723 of file controlizer.c.

{
  /* To track the statement related to labels inside the loop body: */
  hash_table loop_used_labels = hash_table_make(hash_string, 0);
  statement sl = control_statement(c_res);
 
  pips_debug(5, "(st = %p, c_res = %p, succ = %p)\n", sl, c_res, succ);
 
  forloop l = statement_forloop(sl);
  statement body_s = forloop_body(l);
 
  /* Remove the loop body from the loop just in case we want to
     prettyprint our work in progress: */
  //loop_body(l) = statement_undefined;
  forloop_body(l) = make_plain_continue_statement();
  /* Create a control node to host the loop body and insert it in the
     control graph: */
  control c_body = make_conditional_control(body_s);
  insert_control_in_arc(c_body, c_res, succ);
  /* We also insert a dummy node between the body and the exit that will
     be used for the incrementation because if the control body has goto
     to succ node, we will have trouble to insert it later: */
  control c_inc = make_control(make_plain_continue_statement(), NIL, NIL);
  insert_control_in_arc(c_inc, c_body, succ);
  /* TODO
  switch(get_prettyprint_language_tag()) {
    case is_language_fortran:
    case is_language_fortran95:
      cs = strdup(concatenate(prev_comm,
                              get_comment_sentinel(),
                              "     DO loop ",
                              lab,
                              " with exit had to be desugared\n",
                              NULL));
      break;
    case is_language_c:
      cs = prev_comm;
      break;
    default:
      pips_internal_error("This language is not handled !");
      break;
  }
  */
  /* Recurse by controlizing inside the loop: */
  // link_2_control_nodes(c_body, c_inc); already done by insert_control_in_arc
  bool controlized = controlize_statement(c_body, c_inc, loop_used_labels);
 
  if (!controlized) {
    /* First the easy way. We have a kindly control-localized loop body,
       revert to the original code */
    pips_debug(6, "Since we can keep the do-loop, remove the useless control node %p that was allocated for the loop_body.\n", c_body);
    control_statement(c_body) = statement_undefined;
    /* Remove the control node from the control graph by carefully
       relinking around: */
    remove_a_control_from_an_unstructured(c_body);
    /* Remove also the dummy increment node that has not been used
       either: */
    remove_a_control_from_an_unstructured(c_inc);
    /* Move the loop body into its own loop: */
    forloop_body(l) = body_s;
  }
  else {
    /* We are in trouble since the loop body is not locally structured,
       there are goto from inside or outside the loop body. So we
       replace the do-loop with a desugared version with an equivalent
       control graph. */
    /* Update the increment control node with the real computation: */
    /* First remove the dummy statement added above: */
    free_statement(control_statement(c_inc));
    /* And put "i = i + s" instead: */
    control_statement(c_inc) = unsugared_forloop_inc(sl);
    /* Now build the desugared loop: */
    /* We can replace the former loop statement by the new header. That
       means that all pragma, comment, extensions, label on the previous
       loop stay on this. */
    control_statement(c_res) = unsugared_forloop_header(sl);
    /* Add the continuation test between the header and the body that are
       already connected: */
    control c_test = make_control(unsugared_forloop_test(sl), NIL, NIL);
    insert_control_in_arc(c_test, c_res, c_body);
    /* Detach the increment node from the loop exit */
    unlink_2_control_nodes(c_inc, succ);
    /* And reconnect it to the test node to make the loop: */
    link_2_control_nodes(c_inc, c_test);
    /* Add the else branch of the test toward the loop exit: */
    // link_2_control_nodes(c_test, succ) does not support distinction
    // between true and false branch as first and second successors
    // FI: I hesitated to define a new loe level procedure in ri-util/control.c
    control_successors(c_test) = gen_nconc(control_successors(c_test),
                                           CONS(CONTROL, succ, NIL));
    control_predecessors(succ) = gen_nconc(control_predecessors(succ),
                                           CONS(CONTROL, c_test, NIL));
    /* Detach the succ node from the body node */
    //unlink_2_control_nodes(c_body, succ);
    /* We can remove  */
  }
 
  /* Keep track of labels that were used by the statements of the loop: */
  union_used_labels( used_labels, loop_used_labels);
  hash_table_free(loop_used_labels);
 
  pips_debug(5, "Exiting\n");
 
  return controlized;
}

References c_test(), CONS, CONTROL, control_predecessors, control_statement, control_successors, controlize_statement(), forloop_body, free_statement(), gen_nconc(), hash_string, hash_table_free(), hash_table_make(), insert_control_in_arc(), link_2_control_nodes(), make_conditional_control(), make_control(), make_plain_continue_statement(), NIL, pips_debug, remove_a_control_from_an_unstructured(), statement_forloop(), statement_undefined, union_used_labels(), unlink_2_control_nodes(), unsugared_forloop_header(), unsugared_forloop_inc(), and unsugared_forloop_test().

Referenced by controlize_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_forloop() [2/2]

static bool controlize_forloop ( statement  st, forloop  l, control  pred, control  succ, control  c_res, hash_table  used_labels  )

static

To avoid gcc warning about possible non-initialization

Try an unsafe conversion to a Fortran style DO loop: it assumes that the loop body does not define the loop index, but effects are not yet available when the controlizer is run.

If the DO conversion has failed, the WHILE conversion may be requested

As a sequence cannot carry comments, the for loop comments are moved to the while loop

These three fields have been re-used or freed by the previous call

Quite a lot of sharing between st and d_st

Since we may have replaced a statement that may have comments and labels by a sequence, do not forget to forward them where they can be:

The for loop cannot be preserved as a control structure

NN : I do not know how to deal with this, the following code does not always work

pips_internal_error("Forloop with goto not implemented yet");

control_successors(pred) = ADD_SUCC(c_res, pred);

Definition at line 822 of file old_controlizer.c.

{
  hash_table loop_used_labels = hash_table_make(hash_string, 0);
  control c_body = make_conditional_control(forloop_body(l));
  control c_inc = make_control(make_plain_continue_statement(), NIL, NIL);
  control c_test = make_control(make_plain_continue_statement(), NIL, NIL);
  bool controlized = false; /* To avoid gcc warning about possible
                               non-initialization */
 
  pips_debug(5, "(st = %p, pred = %p, succ = %p, c_res = %p)\n",
             st, pred, succ, c_res);
  ifdebug(1) {
    statement_consistent_p(st);
  }
 
  controlize(forloop_body(l), c_test, c_inc, c_body, loop_used_labels);
 
  ifdebug(1) {
    statement_consistent_p(st);
  }
 
  if (covers_labels_p(forloop_body(l),loop_used_labels)) {
    instruction ni = instruction_undefined;
 
    /* Try an unsafe conversion to a Fortran style DO loop: it assumes
       that the loop body does not define the loop index, but effects are
       not yet available when the controlizer is run. */
    if(get_bool_property("FOR_TO_DO_LOOP_IN_CONTROLIZER")) {
        forloop_body(l)= control_statement(c_body);
        sequence new_l = for_to_do_loop_conversion(l,st);
 
        if(!sequence_undefined_p(new_l)) {
            ni = make_instruction_sequence( new_l);
        }
    }
 
    /* If the DO conversion has failed, the WHILE conversion may be requested */
    if(instruction_undefined_p(ni)) {
        if(get_bool_property("FOR_TO_WHILE_LOOP_IN_CONTROLIZER")) {
            /* As a sequence cannot carry comments, the for loop comments
               are moved to the while loop */
            sequence wls = for_to_while_loop_conversion(forloop_initialization(l),
                    forloop_condition(l),
                    forloop_increment(l),
                    control_statement(c_body),
                    statement_extensions(st));
 
            /* These three fields have been re-used or freed by the previous call */
            forloop_initialization(l) = expression_undefined;
            forloop_condition(l) = expression_undefined;
            forloop_increment(l) = expression_undefined;
 
            ni = make_instruction_sequence(wls);
        }
        else {
            forloop new_l = make_forloop(forloop_initialization(l),
                    forloop_condition(l),
                    forloop_increment(l),
                    control_statement(c_body));
 
            ni = make_instruction_forloop(new_l);
        }
    }
 
    gen_remove(&control_successors(c_body), c_res);
    gen_remove(&control_predecessors(c_body), c_res);
    gen_remove(&control_predecessors(c_res), c_body);
 
    /* Quite a lot of sharing between st and d_st*/
    st = normalize_statement(st);
    statement d_st = make_statement(statement_label(st),
                                    statement_number(st),
                                    STATEMENT_ORDERING_UNDEFINED,
                                    strdup(statement_comments(st)),
                                    ni,
                                    gen_copy_seq(statement_declarations(st)),
                                    strdup(statement_decls_text(st)),
                                    copy_extensions(statement_extensions(st)), make_synchronization_none());
    ifdebug(1) {
      statement_consistent_p(st);
      statement_consistent_p(d_st);
    }
    /* Since we may have replaced a statement that may have comments and
       labels by a sequence, do not forget to forward them where they can
       be: */
    fix_statement_attributes_if_sequence(d_st);
    ifdebug(1) {
      statement_consistent_p(d_st);
    }
 
    UPDATE_CONTROL(c_res,
                   d_st,
                   ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE(pred, c_res),
                   CONS(CONTROL, succ, NIL));
    controlized = false;
    control_predecessors(succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_res, succ);
  }
  else /* The for loop cannot be preserved as a control structure*/
    {
      /* NN : I do not know how to deal with this, the following code does not always work
 
         pips_internal_error("Forloop with goto not implemented yet");*/
 
      free_statement(control_statement(c_test));
      control_statement(c_test) = forloop_test(st);
      control_predecessors(c_test) =
        CONS(CONTROL, c_res, CONS(CONTROL, c_inc, NIL)),
        control_successors(c_test) =
        CONS(CONTROL, succ, CONS(CONTROL, c_body, NIL));
      free_statement(control_statement(c_inc));
      control_statement(c_inc) = forloop_inc(st);
      control_successors(c_inc) = CONS(CONTROL, c_test, NIL);
      UPDATE_CONTROL(c_res,
                     forloop_header(st),
                     ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE(pred, c_res),
                     CONS(CONTROL, c_test, NIL));
      controlized = true ;
      control_predecessors(succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_test, succ);
    }
  add_proper_successor_to_predecessor(pred, c_res);
  /* control_successors(pred) = ADD_SUCC(c_res, pred); */
 
  ifdebug(5) check_control_coherency(c_res);
 
  union_used_labels( used_labels, loop_used_labels);
  hash_table_free(loop_used_labels);
 
  pips_debug(5, "Exiting\n");
 
  return(controlized);
}

References ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE, ADD_PRED_IF_NOT_ALREADY_HERE, add_proper_successor_to_predecessor(), c_test(), check_control_coherency(), CONS, CONTROL, control_predecessors, control_statement, control_successors, controlize(), copy_extensions(), covers_labels_p(), expression_undefined, fix_statement_attributes_if_sequence(), for_to_do_loop_conversion(), for_to_while_loop_conversion(), forloop_body, forloop_condition, forloop_header(), forloop_inc(), forloop_increment, forloop_initialization, forloop_test(), free_statement(), gen_copy_seq(), gen_remove(), get_bool_property(), hash_string, hash_table_free(), hash_table_make(), ifdebug, instruction_undefined, instruction_undefined_p, make_conditional_control(), make_control(), make_forloop(), make_instruction_forloop(), make_instruction_sequence(), make_plain_continue_statement(), make_statement(), make_synchronization_none(), NIL, normalize_statement(), pips_debug, sequence_undefined_p, statement_comments, statement_consistent_p(), statement_declarations, statement_decls_text, statement_extensions, statement_label, statement_number, STATEMENT_ORDERING_UNDEFINED, strdup(), true, union_used_labels(), and UPDATE_CONTROL.

Referenced by controlize().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_goto()

static bool controlize_goto ( control  c_res, control  succ, hash_table  used_labels  )

static

Deal with "goto" when building the HCFG.

Parameters

[in,out]	c_res	is the control node with the "goto" statement (that is an empty one in the unstructured since the "goto" in the HCFG is an arc, no longer a statement) that will point to a new control node with the given label
[in,out]	succ	is the control node successor of c_res. Except if it is also the target of the "goto" by chance, it will become unreachable.
[in,out]	used_labels	is a hash table mapping a label name to a list of statements that use it, as their label or because they are a goto to it

Get the label name of the statement the goto points to:

Since the goto by itself is transformed into an arc in the control graph, the "goto" statement is no longer used. But some informations associated to the "goto" statement such as a comment or an extension must survive, so we keep them in a nop statement that will receive its attribute and will be the source arc representing the goto:

Disconnect the target statement:

Get the control node associated with the label we want to go to:

Since it is a goto just on the next statement, nothing to do and it is not unstructured. But st must no longer be associated to name in hash table Label_statements.

The goto target is somewhere else, so it is clearly unstructured:

Disconnect the nop from the successor:

And add the edge in place of the goto from c_res to n_succ:

Add st as locally related to this label name but do not add the target since it may be non local:

Definition at line 2362 of file controlizer.c.

{
  bool controlized;
  statement st = control_statement(c_res);
  statement go_to = statement_goto(st);
  /* Get the label name of the statement the goto points to: */
  string name = entity_name(statement_label(go_to));
  /* Since the goto by itself is transformed into an arc in the control
     graph, the "goto" statement is no longer used. But some informations
     associated to the "goto" statement such as a comment or an extension
     must survive, so we keep them in a nop statement that will receive
     its attribute and will be the source arc representing the goto: */
  instruction i = statement_instruction(st);
  /* Disconnect the target statement: */
  instruction_goto(i) = statement_undefined;
  free_instruction(i);
  statement_instruction(st) = make_continue_instruction();
 
  /* Get the control node associated with the label we want to go to: */
  control n_succ = get_label_control(name);
 
  ifdebug(5) {
    pips_debug(5, "After freeing the goto, from c_res = %p:\n", c_res);
    display_linked_control_nodes(c_res);
    check_control_coherency(c_res);
    pips_debug(5, "From n_succ = %p:\n", n_succ);
    display_linked_control_nodes(n_succ);
    check_control_coherency(n_succ);
  }
  if (succ ==  n_succ) {
    /* Since it is a goto just on the next statement, nothing to do and it
       is not unstructured. But st must no longer be associated to name
       in hash table Label_statements. */
    list sl = (list) hash_get_default_empty_list(Label_statements, (void *) name);
    if(gen_in_list_p((void *) st, sl)) {
      gen_remove(&sl, (void *) st);
      hash_update(Label_statements, (void *) name, (void *) sl);
    }
    else {
      pips_internal_error("Label %s associated to statement %p is not associated"
                          " to statement %p in hash table Label_statements\n");
    }
    controlized = false;
  }
  else {
    /* The goto target is somewhere else, so it is clearly
       unstructured: */
    controlized = true;
    pips_debug(5, "Unstructured goto to label %s: control n_succ %p\n"
               "\tSo statement in control %p is now unreachable from this way\n",
               name, n_succ, succ);
    /* Disconnect the nop from the successor:*/
    unlink_2_control_nodes(c_res, succ);
    /* And add the edge in place of the goto from c_res to n_succ: */
    link_2_control_nodes(c_res, n_succ);
 
    /* Add st as locally related to this label name but do not add the
       target since it may be non local: */
    update_used_labels(used_labels, name, st);
 
    ifdebug(5) {
      pips_debug(5, "After freeing the goto, from c_res = %p:\n", c_res);
      display_linked_control_nodes(c_res);
      check_control_coherency(c_res);
      pips_debug(5, "From n_succ = %p:\n", succ);
      display_linked_control_nodes(succ);
      check_control_coherency(succ);
    }
    ifdebug(1)
      check_control_coherency(n_succ);
  }
  return controlized;
}

References check_control_coherency(), control_statement, display_linked_control_nodes(), entity_name, free_instruction(), gen_in_list_p(), gen_remove(), get_label_control(), hash_get_default_empty_list(), hash_update(), ifdebug, instruction_goto, Label_statements, link_2_control_nodes(), make_continue_instruction(), pips_debug, pips_internal_error, statement_goto(), statement_instruction, statement_label, statement_undefined, unlink_2_control_nodes(), and update_used_labels().

Referenced by controlize_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_list()

static bool controlize_list ( statement  st, list  sts, control  pred, control  succ, control  c_res, hash_table  used_labels  )

static

Computes in c_res the control graph of the list sts (of statement st) with pred predecessor and succ successor.

We try to minimize the number of graphs by looking for graphs with one node only and picking the statement in that case.

Returns

true if the code is not a structured control.

Empty statement list. It looks like from controlize() that we cannot be called with an empty statement list... So I guess this is dead code here. RK

Should be empty_comments ?

FI: the statement extension of st is lost

What happens to the declarations and comments attached to st?

Create a control node to hold what was the statement block, with the first statement in it:

Do the real transformation of a statement list into a control graph:

Compute if there are goto from/to the statements of the statement list:

We are in trouble since we will have an unstructured with goto from or to outside this statement sequence, but the statement sequence that define the scoping rules is going to disappear... So we gather all the declaration and push them up:

Since we have generated a big control graph from what could be a more structured statement block, try to restructure things a little bit, with c_last pointing to the last control node of the list:

To avoid compact list: c_last = c_end;

There is no GOTO to/from outside the statement list: hierarchize the control graph.

Unlink the c_block from the unstructured. RK.

c_block is a lonely control node:

PJ: fragile attempt at keeping local declarations and their scope

FI: Can't we remove the declarations in st? Why are they gen_copy_seq?

‍**it will add block for statement before add the extension

FI: no need to update declarations as the code is structured

The control is kept in an unstructured:

FI: So here you are putting declarations in an unstructured? No surprise we end up in trouble later.

Not a good idea from mine to add this free... RK free_statement(control_statement(c_res));

FI: when going down controlize list, these two nodes are already linked, and they are relinked unconditionnally by link_2_control_nodes() which does not check that its input assumption is met.

Update c_res to reflect c_block in fact:

We alredy have pred linked to c_block and the exit node linked to succ. RK

Definition at line 1358 of file old_controlizer.c.

{
  hash_table block_used_labels = hash_table_make(hash_string, 0);
  control c_block = control_undefined;
  control c_end = make_control(make_plain_continue_statement(), NIL, NIL);
  control c_last = c_end;
  list ctls;
  bool controlized;
  bool hierarchized_labels;
 
  ifdebug(1) {
    pips_debug(5, "Begin with (st = %p, pred = %p, succ = %p, c_res = %p)\n",
        st, pred, succ, c_res);
    ifdebug(8) {
      pips_debug(8, "\nControl nodes linked to pred = %p:\n", pred);
      display_linked_control_nodes(pred);
      pips_debug(8, "\n");
    }
 
    statement_consistent_p(st);
    check_control_coherency(pred);
    check_control_coherency(succ);
    check_control_coherency(c_res);
  }
 
  if(ENDP(sts)) {
    /* Empty statement list. It looks like from controlize() that we
       cannot be called with an empty statement list... So I guess this
       is dead code here. RK */
    list d = gen_copy_seq(statement_declarations(st));
    string dt
    = (statement_decls_text(st)==NULL || string_undefined_p(statement_decls_text(st))) ?
        strdup("")
        : strdup(statement_decls_text(st));
    string ct = string_undefined_p(statement_comments(st))?
        string_undefined /* Should be empty_comments ? */
        : strdup(statement_comments(st));
 
    /* FI: the statement extension of st is lost */
    c_block = make_control(make_empty_statement_with_declarations_and_comments(d, dt, ct),
        NIL, NIL);
    /*
    pips_assert("declarations are preserved in control",
        gen_length(statement_declarations(st))
        ==gen_length(statement_declarations(control_statement(c_block))));
    */
  }
  else {
    /* What happens to the declarations and comments attached to st? */
    /* Create a control node to hold what was the statement block, with
       the first statement in it: */
    c_block = make_conditional_control(STATEMENT(CAR(sts)));
    /*
    pips_assert("declarations are preserved in conditional control",
        gen_length(statement_declarations(st))
        ==gen_length(statement_declarations(control_statement(c_block))));
    */
  }
 
  ifdebug(1) {
    statement_consistent_p(st);
  }
 
  /* Do the real transformation of a statement list into a control
       graph: */
  ctls = controlize_list_1(sts, pred, c_end, c_block, block_used_labels);
 
  /* Compute if there are goto from/to the statements of the statement
       list: */
  hierarchized_labels = covers_labels_p(st, block_used_labels);
 
  if (!hierarchized_labels) {
    /* We are in trouble since we will have an unstructured with goto
       from or to outside this statement sequence, but the statement
       sequence that define the scoping rules is going to disappear...
       So we gather all the declaration and push them up: */
    move_declaration_control_node_declarations_to_statement(ctls);
  }
  /* Since we have generated a big control graph from what could be a
       more structured statement block, try to restructure things a little
       bit, with c_last pointing to the last control node of the list: */
  c_last = compact_list(ctls, c_end);
  /* To avoid compact list: c_last = c_end; */
  //c_last = c_end;
  gen_free_list(ctls);
  ifdebug(5) {
    pips_debug(5, "Nodes from c_block %p\n", c_block);
    display_linked_control_nodes(c_block);
    pips_debug(5, "Nodes from c_last %p\n", c_last);
    display_linked_control_nodes(c_last);
  }
  /*
  pips_assert("declarations are preserved in list",
      gen_length(statement_declarations(st))
      ==gen_length(statement_declarations(control_statement(c_block))));
  */
 
  if (hierarchized_labels) {
    /* There is no GOTO to/from  outside the statement list:
       hierarchize the control graph. */
    statement new_st = statement_undefined;
 
    /* Unlink the c_block from the unstructured. RK. */
    unlink_2_control_nodes(pred, c_block);
    unlink_2_control_nodes(c_block, c_end);
 
    if(ENDP(control_predecessors(c_block)) &&
        ENDP(control_successors(c_block))) {
      /* c_block is a lonely control node: */
      new_st = control_statement(c_block);
 
      ///* FI: fragile attempt at keeping local declarations and their scope */
      ///* Does not work when st has been changed... */
      //if(/*!statement_block_p(new_st) &&*/ !ENDP(statement_declarations(st))) {
      //  /* new_st = st*/;
      //}
 
      /* PJ: fragile attempt at keeping local declarations and their scope */
      ifdebug(1) {
        statement_consistent_p(st);
      }
      if(!ENDP(statement_declarations(st))) {
        pips_assert("the declarations are carried by a block",
            statement_block_p(st));
        ifdebug(8) {
          pips_debug(8, "Block declarations to copy: ");
          print_entities(statement_declarations(st));
          pips_debug(8, "End of declarations.\n");
        }
        if(statement_block_p(new_st)) {
          if(ENDP(statement_declarations(new_st))) {
            statement_declarations(new_st) =
                gen_copy_seq(statement_declarations(st));
          }
          else {
            new_st = make_block_statement(CONS(STATEMENT, new_st, NIL));
            statement_declarations(new_st) =
                gen_copy_seq(statement_declarations(st));
          }
        }
        else {
          new_st = make_block_statement(CONS(STATEMENT, new_st, NIL));
          statement_declarations(new_st) =
              gen_copy_seq(statement_declarations(st));
        }
        /* FI: Can't we remove the declarations in st? Why are
               they gen_copy_seq? */
      }
      if (!extensions_undefined_p(statement_extensions(st)) && !empty_extensions_p(statement_extensions(st))) {
        ///* it will add block for statement before add the extension
        // *   ie,  statement* -> { statement* }
        // * not need in fact,
        // * either block is already present, so no need to add
        // * or block are useless, so no need to add
        // */
        //if (!instruction_block_p(statement_instruction(new_st))
        //    && instruction_block_p(statement_instruction(st))
        //    ) {
        //  new_st = make_block_statement(CONS(STATEMENT, new_st, NIL));
        //}
        extensions_extension(statement_extensions(new_st)) = gen_full_copy_list(extensions_extension(statement_extensions(st)));
      }
 
      control_statement(c_block) = statement_undefined;
      free_control(c_block);
 
      /* FI: no need to update declarations as the code is structured */
      ifdebug(1) {
        statement_consistent_p(st);
      }
    }
    else {
      /* The control is kept in an unstructured: */
      unstructured u = make_unstructured(c_block, c_last);
      instruction i =
          make_instruction(is_instruction_unstructured, u);
 
      ifdebug(1) {
        check_control_coherency(unstructured_control(u));
        check_control_coherency(unstructured_exit(u));
      }
      /* FI: So here you are putting declarations in an
             unstructured? No surprise we end up in trouble
             later. */
      st = normalize_statement(st);
      if(ENDP(statement_declarations(st))) {
        new_st = make_statement(entity_empty_label(),
            statement_number(st),
            STATEMENT_ORDERING_UNDEFINED,
            strdup(statement_comments(st)),
            i,
            gen_copy_seq(statement_declarations(st)),
            strdup(statement_decls_text(st)),
            copy_extensions(statement_extensions(st)), make_synchronization_none());
      }
      else {
        statement us =
            make_statement(entity_empty_label(),
                statement_number(st),
                STATEMENT_ORDERING_UNDEFINED,
                strdup(statement_comments(st)),
                i,
                NIL,
                strdup(""),
                empty_extensions(), make_synchronization_none());
        new_st =
            make_empty_statement_with_declarations_and_comments(
                gen_copy_seq(statement_declarations(st)),
                strdup(statement_decls_text(st)),
                empty_comments);
        statement_extensions(new_st) = copy_extensions(statement_extensions(st));
        statement_instruction(new_st) =
            make_instruction_block(CONS(STATEMENT, us, NIL));
      }
    }
 
    /* Not a good idea from mine to add this free... RK
       free_statement(control_statement(c_res)); */
 
    control_statement(c_res) = new_st;
 
    /* FI: when going down controlize list, these two nodes are
           already linked, and they are relinked unconditionnally by
           link_2_control_nodes() which does not check that its input
           assumption is met. */
    unlink_2_control_nodes(pred, c_res);
 
    link_2_control_nodes(pred, c_res);
    link_2_control_nodes(c_res, succ);
    controlized = false;
  }
  else {
    pips_debug(2, "There are goto to/from outside this statement list\n");
    /* Update c_res to reflect c_block in fact: */
    /* We alredy have pred linked to c_block and the exit node
           linked to succ. RK */
    UPDATE_CONTROL(c_res,
        control_statement(c_block),
        gen_copy_seq(control_predecessors(c_block)),
        control_successors(c_block));
    control_predecessors(succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_end, succ);
    control_successors(c_end) = CONS(CONTROL, succ, NIL);
    patch_references(PREDS_OF_SUCCS, c_block, c_res);
    patch_references(SUCCS_OF_PREDS, c_block, c_res);
    controlized = true;
    /*
    pips_assert("declarations are preserved",
        gen_length(statement_declarations(st))
        ==gen_length(statement_declarations(control_statement(c_res))));
    */
  }
 
  ifdebug(1) {
    statement_consistent_p(st);
  }
 
  union_used_labels(used_labels, block_used_labels);
 
  hash_table_free(block_used_labels);
 
  pips_debug(5, "Exiting with controlized = %s\n",
      bool_to_string(controlized));
  ifdebug(1) {
    ifdebug(8) {
      pips_debug(8, "\nNodes linked to pred %p\n", pred);
      display_linked_control_nodes(pred);
      pips_debug(8, "\n");
    }
    check_control_coherency(pred);
    check_control_coherency(succ);
    check_control_coherency(c_res);
    /*
    pips_assert("declarations are preserved",
        gen_length(statement_declarations(st))
        ==gen_length(statement_declarations(control_statement(c_res))));
     */
 
    statement_consistent_p(st);
  }
  return(controlized);
}

References ADD_PRED_IF_NOT_ALREADY_HERE, bool_to_string(), CAR, check_control_coherency(), compact_list(), CONS, CONTROL, control_predecessors, control_statement, control_successors, control_undefined, controlize_list_1(), copy_extensions(), covers_labels_p(), display_linked_control_nodes(), empty_comments, empty_extensions(), empty_extensions_p(), ENDP, entity_empty_label(), extensions_extension, extensions_undefined_p, free_control(), gen_copy_seq(), gen_free_list(), gen_full_copy_list(), hash_string, hash_table_free(), hash_table_make(), ifdebug, is_instruction_unstructured, link_2_control_nodes(), make_block_statement(), make_conditional_control(), make_control(), make_empty_statement_with_declarations_and_comments(), make_instruction(), make_instruction_block(), make_plain_continue_statement(), make_statement(), make_synchronization_none(), make_unstructured(), move_declaration_control_node_declarations_to_statement(), NIL, normalize_statement(), patch_references(), pips_assert, pips_debug, PREDS_OF_SUCCS, print_entities(), STATEMENT, statement_block_p, statement_comments, statement_consistent_p(), statement_declarations, statement_decls_text, statement_extensions, statement_instruction, statement_number, STATEMENT_ORDERING_UNDEFINED, statement_undefined, strdup(), string_undefined, string_undefined_p, SUCCS_OF_PREDS, union_used_labels(), unlink_2_control_nodes(), unstructured_control, unstructured_exit, and UPDATE_CONTROL.

Referenced by controlize().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_list_1()

static list controlize_list_1 ( list  sts, control  i_pred, control  i_succ, control  i_c_res, hash_table  used_labels  )

static

Do the equivalent of a mapcar of controlize on statement list sts.

The trick is to keep a list of the controls to compact them later. Note that if a statement is controlized, then the predecessor has to be computed (i.e. is not the previous control of sts); this is the purpose of c_in.

This function used to update its formal parameters pred and c_res, which makes stack visualization and debugging difficult.

The list of all the control nodes associated to this statement list:

On all the statement list:

Create a control node for the successor of this statement if not the last one:

Controlize the current statement:

Keep track of the control node associated to this statement:

Keep track globally of the unreachable code:

ifdebug(2) {

pips_debug(2, "There is a new unreachable statement:\n");

print_statement(st);

}

The previous controlize() returned a non structured control

Insert c_in as a predecessor of c_next

RK: I do not understand why this is needed...

If the next control node is unreachable, it will not be connected to the previous predecessor, so allocate a new one so that it has a predecessor that is completely unconnected of previous control graph.

The next control node is the control node of the next statement:

The consistency check should be applied to all elements in ctls. Let's hope all controls in ctls are linked one way or the other.

Since we built the list in reverse order to have a O(n) construction:

Definition at line 1243 of file old_controlizer.c.

                            {
  /* The list of all the control nodes associated to this statement
     list: */
  list ctls = NIL;
  control pred = i_pred;
  control succ = i_succ;
  control c_res = i_c_res;
 
  /* On all the statement list: */
  for(; !ENDP(sts); sts = CDR(sts)) {
    statement st = STATEMENT(CAR(sts));
    /* Create a control node for the successor of this statement if
       not the last one: */
    control c_next = ENDP(CDR(sts)) ? succ :
        make_conditional_control(STATEMENT(CAR(CDR(sts))));
    bool controlized;
    bool unreachable;
 
    ifdebug(5) {
      pips_debug(5, "Nodes linked with pred %p:\n", pred);
      display_linked_control_nodes(pred);
    }
 
    ifdebug(1) {
      check_control_coherency(pred);
      check_control_coherency(succ);
      check_control_coherency(c_next);
      check_control_coherency(c_res);
    }
 
    /* Controlize the current statement: */
    controlized = controlize(st, pred, c_next, c_res, used_labels);
    unreachable = ENDP(control_predecessors(c_next));
 
    /* Keep track of the control node associated to this statement: */
    ctls = CONS(CONTROL, c_res, ctls);
 
    if (unreachable) {
      /* Keep track globally of the unreachable code: */
      Unreachable = CONS(STATEMENT, st, Unreachable);
      /* ifdebug(2) { */
      /*   pips_debug(2, "There is a new unreachable statement:\n"); */
      /*   print_statement(st); */
      /* } */
    }
 
    if (controlized) {
      /* The previous controlize() returned a non structured control */
      control c_in = make_control(make_plain_continue_statement(), NIL, NIL);
 
      ctls = CONS(CONTROL, c_in, ctls);
      /* Insert c_in as a predecessor of c_next
 
         RK: I do not understand why this is needed...
      */
      control_predecessors(c_in) = control_predecessors(c_next);
      control_successors(c_in) = CONS(CONTROL, c_next, NIL);
      patch_references(SUCCS_OF_PREDS, c_next, c_in);
      control_predecessors(c_next) = CONS(CONTROL, c_in, NIL) ;
      pred = c_in;
    }
    else {
      /* If the next control node is unreachable, it will not be
         connected to the previous predecessor, so allocate a new one
         so that it has a predecessor that is completely unconnected of
         previous control graph. */
      pred = (unreachable) ?
          make_control(make_plain_continue_statement(), NIL, NIL) :
          c_res;
    }
    /* The next control node is the control node of the next
       statement: */
    c_res = c_next ;
  }
 
  ifdebug(1) {
    /* The consistency check should be applied to all elements in
       ctls. Let's hope all controls in ctls are linked one way or
       the other. */
    control c = CONTROL(CAR(ctls));
    pips_debug(5, "Nodes from c %p\n", c);
    display_linked_control_nodes(c);
    check_control_coherency(c);
 
    check_control_coherency(pred);
    check_control_coherency(succ);
    check_control_coherency(c_res);
    pips_debug(5, "(pred = %p, succ = %p, c_res = %p)\n",
        pred, succ, c_res);
    pips_debug(5, "Nodes from pred %p\n", pred);
    display_linked_control_nodes(pred);
    pips_debug(5, "Nodes from succ %p\n", succ);
    display_linked_control_nodes(succ);
    pips_debug(5, "Nodes from c_res %p\n", c_res);
    display_linked_control_nodes(c_res);
  }
 
  /* Since we built the list in reverse order to have a O(n)
     construction: */
  return gen_nreverse(ctls);
}

References c_in, CAR, CDR, check_control_coherency(), CONS, CONTROL, control_predecessors, control_successors, controlize(), display_linked_control_nodes(), ENDP, gen_nreverse(), ifdebug, make_conditional_control(), make_control(), make_plain_continue_statement(), NIL, patch_references(), pips_debug, STATEMENT, SUCCS_OF_PREDS, and Unreachable.

Referenced by controlize_list().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_loop() [1/2]

static bool controlize_loop ( control  c_res, control  succ, hash_table  used_labels  )

static

Computes the control graph of a Fortran do-loop statement.

Parameters

[in,out]	c_res	is the entry control node with the do-loop statement to controlize. If the do-loop has complex control code such as some goto to outside, it is transformed into an equivalent control graph.
[in,out]	succ	must be the control node successor of c_res that will be the current end of the control node sequence and an exit node
[in,out]	used_labels	is a hash table mapping a label name to a list of statements that use it, as their label or because it is a goto to it

Returns

true if the code is not a structured control.

To track the statement related to labels inside the loop body:

Remove the loop body from the loop just in case we want to prettyprint our work in progress:

Create a control node to host the loop body and insert it in the control graph:

We also insert a dummy node between the body and the exit that will be used for the incrementation because if the control body has goto to succ node, we will have trouble to insert it later:

TODO switch(get_prettyprint_language_tag()) { case is_language_fortran: case is_language_fortran95: cs = strdup(concatenate(prev_comm, get_comment_sentinel(), " DO loop ", lab, " with exit had to be desugared\n", NULL)); break; case is_language_c: cs = prev_comm; break; default: pips_internal_error("This language is not handled !"); break; }

Recurse by controlizing inside the loop:

First the easy way. We have a kindly control-localized loop body, revert to the original code

Remove the control node from the control graph by carefully relinking around:

Remove also the dummy increment node that has not been used either:

Move the loop body into its own loop:

We are in trouble since the loop body is not locally structured, there are goto from inside or outside the loop body. So we replace the do-loop with a desugared version with an equivalent control graph.

Update the increment control node with the real computation:

First remove the dummy statement added above:

And put "i = i + s" instead:

Now build the desugared loop:

We can replace the former loop statement by the new header. That means that all pragma, comment, extensions, label on the previous loop stay on this.

Add the continuation test between the header and the body that are already connected:

Detach the increment node from the loop exit

And reconnect it to the test node to make the loop:

Add the else branch of the test toward the loop exit:

Detach the succ node from the body node

We can remove

Keep track of labels that were used by the statements of the loop:

Definition at line 597 of file controlizer.c.

{
  /* To track the statement related to labels inside the loop body: */
  hash_table loop_used_labels = hash_table_make(hash_string, 0);
  statement sl = control_statement(c_res);
 
  pips_debug(5, "(st = %p, c_res = %p, succ = %p)\n", sl, c_res, succ);
 
  loop l = statement_loop(sl);
  statement body_s = loop_body(l);
 
  /* Remove the loop body from the loop just in case we want to
     prettyprint our work in progress: */
  //loop_body(l) = statement_undefined;
  loop_body(l) = make_plain_continue_statement();
  /* Create a control node to host the loop body and insert it in the
     control graph: */
  control c_body = make_conditional_control(body_s);
  insert_control_in_arc(c_body, c_res, succ);
  /* We also insert a dummy node between the body and the exit that will
     be used for the incrementation because if the control body has goto
     to succ node, we will have trouble to insert it later: */
  control c_inc = make_control(make_plain_continue_statement(), NIL, NIL);
  insert_control_in_arc(c_inc, c_body, succ);
  /* TODO
  switch(get_prettyprint_language_tag()) {
    case is_language_fortran:
    case is_language_fortran95:
      cs = strdup(concatenate(prev_comm,
                              get_comment_sentinel(),
                              "     DO loop ",
                              lab,
                              " with exit had to be desugared\n",
                              NULL));
      break;
    case is_language_c:
      cs = prev_comm;
      break;
    default:
      pips_internal_error("This language is not handled !");
      break;
  }
  */
  /* Recurse by controlizing inside the loop: */
  // FI: this seems redundant with the above call to insert_control_in_arc()
  //link_2_control_nodes(c_body, c_inc);
  bool controlized = controlize_statement(c_body, c_inc, loop_used_labels);
 
  if (!controlized) {
    /* First the easy way. We have a kindly control-localized loop body,
       revert to the original code */
    pips_debug(6, "Since we can keep the do-loop, remove the useless control node %p that was allocated for the loop_body.\n", c_body);
    control_statement(c_body) = statement_undefined;
    /* Remove the control node from the control graph by carefully
       relinking around: */
    remove_a_control_from_an_unstructured(c_body);
    /* Remove also the dummy increment node that has not been used
       either: */
    remove_a_control_from_an_unstructured(c_inc);
    /* Move the loop body into its own loop: */
    loop_body(l) = body_s;
  }
  else {
    /* We are in trouble since the loop body is not locally structured,
       there are goto from inside or outside the loop body. So we
       replace the do-loop with a desugared version with an equivalent
       control graph. */
    /* Update the increment control node with the real computation: */
    /* First remove the dummy statement added above: */
    free_statement(control_statement(c_inc));
    /* And put "i = i + s" instead: */
    control_statement(c_inc) = unsugared_loop_inc(sl);
    /* Now build the desugared loop: */
    /* We can replace the former loop statement by the new header. That
       means that all pragma, comment, extensions, label on the previous
       loop stay on this. */
    control_statement(c_res) = unsugared_loop_header(sl);
    /* Add the continuation test between the header and the body that are
       already connected: */
    control c_test = make_control(unsugared_loop_test(sl), NIL, NIL);
    insert_control_in_arc(c_test, c_res, c_body);
    /* Detach the increment node from the loop exit */
    unlink_2_control_nodes(c_inc, succ);
    /* And reconnect it to the test node to make the loop: */
    link_2_control_nodes(c_inc, c_test);
    /* Add the else branch of the test toward the loop exit: */
    // FI: try to get the true and false successors at the right location...
    // link_2_control_nodes(c_test, succ);
    //control_successors(c_test) = gen_nconc(control_successors(c_test),
    //                             CONS(CONTROL, succ, NIL));
    //control_successors(c_test) = gen_nreverse(control_successors(c_test));
    control_successors(c_test) = CONS(CONTROL, succ, control_successors(c_test));
    control_predecessors(succ) = gen_nconc(control_predecessors(succ),
                                           CONS(CONTROL, c_test, NIL));
    /* Detach the succ node from the body node */
    //unlink_2_control_nodes(c_body, succ);
    /* We can remove  */
  }
 
  /* Keep track of labels that were used by the statements of the loop: */
  union_used_labels( used_labels, loop_used_labels);
  hash_table_free(loop_used_labels);
 
  pips_debug(5, "Exiting\n");
 
  return controlized;
}

References c_test(), CONS, CONTROL, control_predecessors, control_statement, control_successors, controlize_statement(), free_statement(), gen_nconc(), hash_string, hash_table_free(), hash_table_make(), insert_control_in_arc(), link_2_control_nodes(), loop_body, make_conditional_control(), make_control(), make_plain_continue_statement(), NIL, pips_debug, remove_a_control_from_an_unstructured(), statement_loop(), statement_undefined, union_used_labels(), unlink_2_control_nodes(), unsugared_loop_header(), unsugared_loop_inc(), and unsugared_loop_test().

Referenced by controlize_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_loop() [2/2]

static bool controlize_loop ( statement  st, loop  l, control  pred, control  succ, control  c_res, hash_table  used_labels  )

static

CONTROLIZE_LOOP computes in C_RES the control graph of the loop L (of statement ST) with PREDecessor and SUCCessor.

control_successors(pred) = ADD_SUCC(c_res, pred);

Definition at line 536 of file old_controlizer.c.

{
    hash_table loop_used_labels = hash_table_make(hash_string, 0);
    control c_body = make_conditional_control(loop_body(l));
    control c_inc = make_control(make_plain_continue_statement(), NIL, NIL);
    control c_test = make_control(make_plain_continue_statement(), NIL, NIL);
    bool controlized;
 
    pips_debug(5, "(st = %p, pred = %p, succ = %p, c_res = %p)\n",
               st, pred, succ, c_res);
 
    controlize(loop_body(l), c_test, c_inc, c_body, loop_used_labels);
 
    if(covers_labels_p(loop_body(l),loop_used_labels)) {
        loop new_l = make_loop(loop_index(l),
                               loop_range(l),
                               control_statement(c_body),
                               loop_label(l),
                               loop_execution(l),
                               loop_locals(l));
 
        st = normalize_statement(st);
        UPDATE_CONTROL(c_res,
                       make_statement(statement_label(st),
                                      statement_number(st),
                                      STATEMENT_ORDERING_UNDEFINED,
                                      statement_comments(st),
                                      make_instruction(is_instruction_loop, new_l),
                                      gen_copy_seq(statement_declarations(st)),
                                      strdup(statement_decls_text(st)),
                                      copy_extensions(statement_extensions(st)), make_synchronization_none()),
                       ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE(pred, c_res),
                       CONS(CONTROL, succ, NIL)) ;
        controlized = false;
        control_predecessors(succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_res, succ);
    }
    else {
        control_statement(c_test) = loop_test(st);
        control_predecessors(c_test) =
                CONS(CONTROL, c_res, CONS(CONTROL, c_inc, NIL)),
        control_successors(c_test) =
                CONS(CONTROL, succ, CONS(CONTROL, c_body, NIL));
        control_statement(c_inc) = loop_inc(st);
        control_successors(c_inc) = CONS(CONTROL, c_test, NIL);
        UPDATE_CONTROL(c_res,
                       loop_header(st),
                       ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE(pred, c_res),
                       CONS(CONTROL, c_test, NIL));
        controlized = true ;
        control_predecessors(succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_test, succ);
    }
    add_proper_successor_to_predecessor(pred, c_res);
    /* control_successors(pred) = ADD_SUCC(c_res, pred); */
 
    union_used_labels( used_labels, loop_used_labels);
    hash_table_free(loop_used_labels);
 
    pips_debug(5, "Exiting\n");
 
    return(controlized);
}

References ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE, ADD_PRED_IF_NOT_ALREADY_HERE, add_proper_successor_to_predecessor(), c_test(), CONS, CONTROL, control_predecessors, control_statement, control_successors, controlize(), copy_extensions(), covers_labels_p(), gen_copy_seq(), hash_string, hash_table_free(), hash_table_make(), is_instruction_loop, loop_body, loop_execution, loop_header(), loop_inc(), loop_index, loop_label, loop_locals, loop_range, loop_test(), make_conditional_control(), make_control(), make_instruction(), make_loop(), make_plain_continue_statement(), make_statement(), make_synchronization_none(), NIL, normalize_statement(), pips_debug, statement_comments, statement_declarations, statement_decls_text, statement_extensions, statement_label, statement_number, STATEMENT_ORDERING_UNDEFINED, strdup(), true, union_used_labels(), and UPDATE_CONTROL.

Referenced by controlize().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_repeatloop()

static bool controlize_repeatloop ( control  c_res, control  succ, hash_table  used_labels  )

static

Computes the control graph of a C repeat until loop statement.

Parameters

[in,out]	c_res	is the entry control node with the do-loop statement to controlize. If the do-loop has complex control code such as some goto to outside, it is transformed into an equivalent control graph.
[in,out]	succ	must be the control node successor of c_res that will be the current end of the control node sequence and an exit node
[in,out]	used_labels	is a hash table mapping a label name to a list of statements that use it, as their label or because it is a goto to it

Returns

true if the code is not a structured control.

To track the statement related to labels inside the loop body:

Remove the loop body from the loop just in case we want to prettyprint our work in progress:

Create a control node to host the loop body and insert it in the control graph:

We also insert a dummy node between the body and the exit that will be used for the incrementation because if the control body has goto to succ node, we will have trouble to insert it later:

TODO switch(get_prettyprint_language_tag()) { case is_language_fortran: case is_language_fortran95: cs = strdup(concatenate(prev_comm, get_comment_sentinel(), " DO loop ", lab, " with exit had to be desugared\n", NULL)); break; case is_language_c: cs = prev_comm; break; default: pips_internal_error("This language is not handled !"); break; }

Recurse by controlizing inside the loop:

First the easy way. We have a kindly control-localized loop body, revert to the original code

Remove the control node from the control graph by carefully relinking around:

Remove also the dummy increment node that has not been used either:

Move the loop body into its own loop:

We are in trouble since the loop body is not locally structured, there are goto from inside or outside the loop body. So we replace the do-loop with a desugared version with an equivalent control graph.

Update the increment control node with the real computation:

First remove the dummy statement added above:

And put "i = i + s" instead:

Now build the desugared loop:

We can replace the former loop statement by the new header. That means that all pragma, comment, extensions, label on the previous loop stay on this.

Add the continuation test between the header and the body that are already connected:

Detach the increment node from the loop exit

And reconnect it to the test node to make the loop:

Add the else branch of the test toward the loop exit:

We can remove

Add the else branch of the test toward the loop exit: arc ordering matters

Keep track of labels that were used by the statements of the loop:

Definition at line 990 of file controlizer.c.

{
  /* To track the statement related to labels inside the loop body: */
  hash_table loop_used_labels = hash_table_make(hash_string, 0);
  statement sl = control_statement(c_res);
 
  pips_debug(5, "(st = %p, c_res = %p, succ = %p)\n", sl, c_res, succ);
 
  whileloop wl = statement_whileloop(sl);
  statement body_s = whileloop_body(wl);
 
  /* Remove the loop body from the loop just in case we want to
     prettyprint our work in progress: */
  whileloop_body(wl) = make_plain_continue_statement();
  /* Create a control node to host the loop body and insert it in the
     control graph: */
  control c_body = make_conditional_control(body_s);
  //insert_control_in_arc(c_body, c_res, succ);
  /* We also insert a dummy node between the body and the exit that will
     be used for the incrementation because if the control body has goto
     to succ node, we will have trouble to insert it later: */
  //control c_inc = make_control(make_plain_continue_statement(), NIL, NIL);
  //insert_control_in_arc(c_inc, c_body, succ);
  /* TODO
  switch(get_prettyprint_language_tag()) {
    case is_language_fortran:
    case is_language_fortran95:
      cs = strdup(concatenate(prev_comm,
                              get_comment_sentinel(),
                              "     DO loop ",
                              lab,
                              " with exit had to be desugared\n",
                              NULL));
      break;
    case is_language_c:
      cs = prev_comm;
      break;
    default:
      pips_internal_error("This language is not handled !");
      break;
  }
  */
  control c_test = make_control(unsugared_whileloop_test(sl), NIL, NIL);
  /* Recurse by controlizing inside the loop: */
  link_2_control_nodes(c_body, c_test);
  bool controlized = controlize_statement(c_body, c_test, loop_used_labels);
 
  if (!controlized) {
    /* First the easy way. We have a kindly control-localized loop body,
       revert to the original code */
    pips_debug(6, "Since we can keep the do-loop, remove the useless control node %p that was allocated for the loop_body.\n", c_body);
    control_statement(c_body) = statement_undefined;
    /* Remove the control node from the control graph by carefully
       relinking around: */
    remove_a_control_from_an_unstructured(c_body);
    /* Remove also the dummy increment node that has not been used
       either: */
    //remove_a_control_from_an_unstructured(c_inc);
    /* Move the loop body into its own loop: */
    whileloop_body(wl) = body_s;
  }
  else {
    /* We are in trouble since the loop body is not locally structured,
       there are goto from inside or outside the loop body. So we
       replace the do-loop with a desugared version with an equivalent
       control graph. */
    /* Update the increment control node with the real computation: */
    /* First remove the dummy statement added above: */
    //free_statement(control_statement(c_inc));
    /* And put "i = i + s" instead: */
    //control_statement(c_inc) = unsugared_loop_inc(sl);
    /* Now build the desugared loop: */
    /* We can replace the former loop statement by the new header. That
       means that all pragma, comment, extensions, label on the previous
       loop stay on this. */
    control_statement(c_res) = unsugared_whileloop_header(sl);
    /* Add the continuation test between the header and the body that are
       already connected: */
    //control c_test = make_control(unsugared_loop_test(sl), NIL, NIL);
    // insert_control_in_arc(c_test, c_res, c_body);
    /* Detach the increment node from the loop exit */
    //unlink_2_control_nodes(c_inc, succ);
    /* And reconnect it to the test node to make the loop: */
    //link_2_control_nodes(c_inc, c_test);
    //link_2_control_nodes(c_body, c_test);
    //link_2_control_nodes(c_test, c_res);
    /* Add the else branch of the test toward the loop exit: */
    //link_2_control_nodes(c_test, succ);
    /* We can remove  */
    unlink_2_control_nodes(c_res, succ);
    link_2_control_nodes(c_res, c_body);
    /* Add the else branch of the test toward the loop exit: arc
       ordering matters */
    unlink_2_control_nodes(c_test, c_body);
    //link_2_control_nodes(c_test, succ);
    //link_2_control_nodes(c_test, c_body);
    link_3_control_nodes(c_test, c_body, succ);
 
    pips_assert("c_test is a test with two successors",
                gen_length(control_successors(c_test))==2
                && statement_test_p(control_statement(c_test)));
    pips_assert("c_body may have two successors if it is a test",
                ( gen_length(control_successors(c_body))==2
                  && statement_test_p(control_statement(c_body)) )
                ||
                ( gen_length(control_successors(c_body))==1
                  && !statement_test_p(control_statement(c_body)) )
                );
    pips_assert("c_res should not be a test",
                gen_length(control_successors(c_res))==1
                && !statement_test_p(control_statement(c_res)) );
  }
 
  /* Keep track of labels that were used by the statements of the loop: */
  union_used_labels( used_labels, loop_used_labels);
  hash_table_free(loop_used_labels);
 
  pips_debug(5, "Exiting\n");
 
  return controlized;
}

References c_test(), control_statement, control_successors, controlize_statement(), gen_length(), hash_string, hash_table_free(), hash_table_make(), link_2_control_nodes(), link_3_control_nodes(), make_conditional_control(), make_control(), make_plain_continue_statement(), NIL, pips_assert, pips_debug, remove_a_control_from_an_unstructured(), statement_test_p(), statement_undefined, statement_whileloop(), union_used_labels(), unlink_2_control_nodes(), unsugared_whileloop_header(), unsugared_whileloop_test(), and whileloop_body.

Referenced by controlize_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_sequence()

static bool controlize_sequence ( control  c_res, control  succ, hash_table  used_labels  )

static

Computes the control graph of a sequence statement.

We try to minimize the number of graphs by looking for graphs with one node only and picking the statement in that case.

Parameters

[in,out]	c_res	is the entry control node with the sequence statement to controlize. It may be at exit the entry control node of a potential unstructured
[in,out]	succ	must be the control node successor of c_res that will be the current end of the control node sequence and an exit node
[in,out]	used_labels	is a hash table mapping a label name to a list of statements that use it, as their label or because it is a goto to it

Returns

true if the code is not a structured control, i.e. it has to be "controlized", i.e. transformed into an "unstructured".

Also, side effect on hash table Label_statements if ever a goto is replaced by a continue because it points to the very next statement, via an indirect call to controlize_goto().

To see if the control graph will stay local or not:

A C block may have a label and even goto from outside on it.

To track variable scoping, track this statement

Get the list of statements in the block statement:

The list of all the control nodes associated to this statement list:

To track where to insert the current control node of a sequence element:

We first transform a structured block of statement in a thread of control node with all the statements that we insert from c_res up to succ:

Create a new control node for this statement, or retrieve one if it as a label:

Keep track of the control node associated to this statement. Note that the list is built in reverse order:

The next control node will be inserted after the new created node:

Now do the real controlizer job on the previously inserted thread of control nodes.

Note that we iterate in the reverse order of the statements since the control list was built up in reverse order. Indeed doing this in reverse order is simpler to write with this "next" stuff because we already have the current element and the successor "succ".

Recurse on each statement: controlized has been initialized to false

The currently processed element will be the successor of the one to be processed:

&& !statement_test_p(control_statement(c))

Each control node of the sequence is indeed well structured, that each control node is without any goto from or to outside itself. So we can keep the original sequence back!

Easy, just remove all the control nodes of the sequence and relink around the control graph:

Do not forget to detach the statement of its control node since we do not want the statement to be freed at the same time:

Remove the control node from the control graph by carefully relinking around:

So, there is some unstructured stuff. We can consider 2 cases to simplify the generated code:

• If the unstructured control code is local to the sequence statements, we can keep some locality by encapsulated this mess into an unstructured so that from outside this unstructured the code is view as structured (the H in HCFG!).
• If not, there are some goto to or from control nodes outside of the sequence statement and then we cannot do anything and return the control graph marked as with control side effect.

Remove the sequence list but not the statements themselves since each one has been moved into a control node:

There are no goto from/to the statements of the statement list, so we can encapsulate all this local control graph in an "unstructured" statement:

Get the local exit node that is the head of the control list since it was built in reverse order. Note that ctls cannot be empty here because it an empty statement sequence should be structured by definition and caught by the previous test.

FI: when the last statement is controlized, there is no guarantee any longer that the control corrresponding to the last statement of the sequence is the exit node. Also, an exit node should have no successor by definition. To avoid the issue, we could systematically add a nop statement to the sequence. Or we could check that the last control node has no successors, else look for the node connected to succ (might be dangerous because succ may not really be part of the code) and, if no such node is found because the sequence loops forever, create a new unreachable control node with a NOP statement.

First detach the local graph:

FI: Not such a good idea to return succ as exit control node...

Reconnect around the unstructured:

And create the local "unstructured" statement to take this local graph:

Make sure that the new unstructured u is not linked to code sitting above

We keep the old block statement since it may old extensions, declarations... If useless, it should be removed later by another phase. So, move the unstructured statement as the only statement of the block:

From outside of this block statement, everything is hierarchized, so we claim it:

There are some goto from or to external control nodes, so we cannot localize stuff.

Keep the empty block statement for extensions and declarations:

Integrate the statements related to the labels inside its statement to the current statement itself:

Remove local label association hash map:

‍**Revert to the variable scope of the outer block statement: *‍/

Definition at line 1914 of file controlizer.c.

                                                        {
  statement st = control_statement(c_res);
  /* To see if the control graph will stay local or not: */
  hash_table block_used_labels = hash_table_make(hash_string, 0);
  bool controlized = false;
 
  pips_assert("st it a statement sequence", statement_sequence_p(st));
 
  ifdebug(5) {
    pips_debug(5, "Entering with nodes linked with c_res %p:\n", c_res);
    display_linked_control_nodes(c_res);
  }
  ifdebug(1) {
    check_control_coherency(c_res);
    check_control_coherency(succ);
  }
 
  scoping_statement_push(st);
 
  /* A C block may have a label and even goto from outside on it. */
  /* To track variable scoping, track this statement */
  // TODO scoping_statement_push(st);
 
  /* Get the list of statements in the block statement: */
  list sts = statement_block(st);
  /* The list of all the control nodes associated to this statement
     list: */
  list ctls = NIL;
 
  /* To track where to insert the current control node of a sequence
     element: */
  control pred = c_res;
  /* We first transform a structured block of statement in a thread of
     control node with all the statements that we insert from c_res up to
     succ: */
  bool must_be_controlized_p = false;
  //bool previous_control_preexisting_p = false;
 
  FOREACH(STATEMENT, s, sts) {
    /* Create a new control node for this statement, or retrieve one
       if it as a label: */
    control c = make_conditional_control(s);
    //bool control_preexisting_p = false;
 
    // FI: I'm not sure this is enough to detect that
    // make_conditional_control() has not made a new control but
    // retrieved a control by its label...
    //if(!ENDP(control_successors(c)) || !ENDP(control_predecessors(c)) ) {
    // FI: too bad if the label is unused... or used locally... or is
    // useless as happens after inlining for FREIA: "goto l1;l1: ;"
    if(!unlabelled_statement_p(s)) {
      pips_debug(8, "This control %p pre-existed. "
                 "The sequence cannot be controlized.\n", c);
      must_be_controlized_p = true;
      //control_preexisting_p = true;
    }
 
    // "insert_control_in_arc(c, pred, succ);" with additional checks
    unlink_2_control_nodes(pred,succ); // whether they are linked or not
    if(ENDP(control_successors(pred)))
      link_2_control_nodes(pred, c);
    if(ENDP(control_successors(c)))
      link_2_control_nodes(c, succ);
 
 
    /* Keep track of the control node associated to this statement. Note
       that the list is built in reverse order: */
    ctls = CONS(CONTROL, c, ctls);
    /* The next control node will be inserted after the new created node: */
    pred = c;
    //previous_control_preexisting_p = control_preexisting_p;
  }
 
  // FI: check that this is a neat sequence if it does not must be controlized
  if(!must_be_controlized_p) {
    FOREACH(CONTROL, c, ctls) {
      pips_assert("c may have only one successor even if it is a test "
                  "a this point",
                  ( gen_length(control_successors(c))==1
                    && statement_test_p(control_statement(c)) )
                  ||
                  ( gen_length(control_successors(c))==1
                    && !statement_test_p(control_statement(c)) )
                  );
    }
  }
 
  /* Now do the real controlizer job on the previously inserted thread of
     control nodes. */
  /* Note that we iterate in the reverse order of the
     statements since the control list was built up in reverse
     order. Indeed doing this in reverse order is simpler to write with
     this "next" stuff because we already have the current element and the
     successor "succ". */
  control next = succ;
  pips_debug(5, "Controlize each statement sequence node in reverse order:\n");
  FOREACH(CONTROL, c, ctls) {
    /* Recurse on each statement: controlized has been initialized to
       false */
    controlized |= controlize_statement(c, next, block_used_labels);
    /* The currently processed element will be the successor of the one to
       be processed: */
    next = c;
  }
 
  if (!controlized && !must_be_controlized_p) {
 
    // FI: check that this is a neat sequence
    FOREACH(CONTROL, c, ctls) {
      if(controlized) // unstructured case: impossible
        pips_assert("c may have two successors only if it is a test",
                    ( gen_length(control_successors(c))==2
                      && statement_test_p(control_statement(c)) )
                    ||
                    ( gen_length(control_successors(c))<=1
                      && !statement_test_p(control_statement(c)) )
                    );
      else // the sequence is structured: always
        pips_assert("c may have two successors only if it is a test",
                    ( gen_length(control_successors(c))==2
                      && statement_test_p(control_statement(c)) )
                    ||
                    ( gen_length(control_successors(c))==1
                      // FI: the test may not be unstructured; a
                      // structured test has only one successor
                      /* && !statement_test_p(control_statement(c))*/ )
                    );
    }
    /* Each control node of the sequence is indeed well structured, that
       each control node is without any goto from or to outside itself. So
       we can keep the original sequence back! */
    pips_debug(5, "Keep a statement sequence and thus remove"
               " previously allocated control nodes for the sequence.\n");
    /* Easy, just remove all the control nodes of the sequence and relink
       around the control graph: */
    FOREACH(CONTROL, c, ctls) {
      statement s = control_statement(c);
      int nsucc = (int) gen_length(control_successors(c));
      /* Do not forget to detach the statement of its control node since
         we do not want the statement to be freed at the same time: */
      pips_debug(6, "Removing useless control node %p.\n", c);
      control_statement(c) = statement_undefined;
 
      if(statement_test_p(s)) {
        // FI: this had not been planned by Ronan
        if(nsucc==1) {
          // FI: might this happen when a test is found out well-structured?
          remove_a_control_from_an_unstructured(c);
        }
        else {
          pips_assert("a test has two successors\n", nsucc==2);
          remove_a_control_from_an_unstructured_without_relinking(c);
        }
      }
      else {
        if(nsucc<=1) {
          pips_assert("a non test has one successor at most\n", nsucc<=1);
          /* Remove the control node from the control graph by carefully
             relinking around: */
          remove_a_control_from_an_unstructured(c);
        }
        else {
          pips_debug(1, "Abnormal control: not a test, two successors.\n");
          remove_a_control_from_an_unstructured_without_relinking(c);
        }
      }
    }
    // You may have to fix C89 declarations if some unstructured has
    // been created below in the recursion
    if(get_bool_property("C89_CODE_GENERATION")) {
      fix_block_statement_declarations(st);
    }
  }
  else {
    /* So, there is some unstructured stuff. We can consider 2 cases to
       simplify the generated code:
 
       - If the unstructured control code is local to the sequence
         statements, we can keep some locality by encapsulated this mess
         into an unstructured so that from outside this unstructured the
         code is view as structured (the H in HCFG!).
 
       - If not, there are some goto to or from control nodes outside of
         the sequence statement and then we cannot do anything and return
         the control graph marked as with control side effect.
    */
    bool covers_p = covers_labels_p(st, block_used_labels);
    /* Remove the sequence list but not the statements themselves since
       each one has been moved into a control node: */
    gen_free_list(sequence_statements(statement_sequence(st)));
    sequence_statements(statement_sequence(st)) = NIL;
 
    // FI: this fails because st has been gutted out... covers_p must
    // be computed earlier
    if (covers_p) {
      /* There are no goto from/to the statements of the statement list,
         so we can encapsulate all this local control graph in an
         "unstructured" statement: */
      /* Get the local exit node that is the head of the control list
         since it was built in reverse order. Note that ctls cannot be
         empty here because it an empty statement sequence should be
         structured by definition and caught by the previous test. */
      /* FI: when the last statement is controlized, there is no
         guarantee any longer that the control corrresponding to the
         last statement of the sequence is the exit node. Also, an
         exit node should have no successor by definition. To avoid
         the issue, we could systematically add a nop statement to the
         sequence. Or we could check that the last control node has no
         successors, else look for the node connected to succ (might
         be dangerous because succ may not really be part of the code)
         and, if no such node is found because the sequence loops
         forever, create a new unreachable control node with a NOP
         statement. */
      // control exit = CONTROL(CAR(ctls));
      control exit = find_exit_control_node(ctls, succ);
      //control exit = find_or_create_exit_control_node(ctls, succ);
      control entry = CONTROL(CAR(gen_last(ctls)));
      pips_debug(5, "Create a local unstructured with entry node %p and exit node %p\n", entry, exit);
 
      /* First detach the local graph: */
      unlink_2_control_nodes(c_res, entry);
      /* FI: Not such a good idea to return succ as exit control node... */
      unlink_2_control_nodes(exit, succ);
      /* Reconnect around the unstructured: */
      link_2_control_nodes(c_res, succ);
      /* And create the local "unstructured" statement to take this local
         graph: */
      unstructured u = make_unstructured(entry, exit);
      ifdebug(1) {
        check_control_coherency(entry);
        check_control_coherency(exit);
 
        /* Make sure that the new unstructured u is not linked to code
           sitting above */
        list linked_nodes = NIL;
        control_map_get_blocs(entry, &linked_nodes);
        if(gen_in_list_p(c_res, linked_nodes)) {
          list cp = NIL;
          list vp = NIL;
          find_a_control_path(entry, c_res, &cp, &vp, 0);
          print_control_nodes(cp);
          pips_internal_error("Some issue due to \"c_res\" with covers_p\n");
        }
        else if(gen_in_list_p(succ, linked_nodes)) {
          list cp = NIL;
          list vp = NIL;
          find_a_control_path(entry, c_res, &cp, &vp, 0);
          print_control_nodes(cp);
          pips_internal_error("Some issue due to \"succ\" with covers_p\n");
        }
      }
 
      statement u_s =
        instruction_to_statement(make_instruction_unstructured(u));
      /* We keep the old block statement since it may old extensions,
         declarations... If useless, it should be removed later by another
         phase. So, move the unstructured statement as the only statement
         of the block: */
      sequence_statements(instruction_sequence(statement_instruction(st))) =
        CONS(STATEMENT, u_s, NIL);
      // You may have to fix C89 declarations if some unstructured has
      // been created below in the recursion
      //if(get_bool_property("C89_CODE_GENERATION")) {
      fix_block_statement_declarations(st);
      //}
      /* From outside of this block statement, everything is hierarchized,
         so we claim it: */
      controlized = false;
    }
    else {
      /* There are some goto from or to external control nodes, so we
         cannot localize stuff. */
      pips_debug(5, "There are goto to/from outside this statement list"
                 " so keep control nodes without any hierarchy here.\n");
      /* Keep the empty block statement for extensions and declarations: */
      // FI; maybe for extensions, but certainly not for declarations;
      // similar code to flatten_code must be used to rename the local
      // variables and to move them up the AST; see sequence04.c for instance
      sequence_statements(instruction_sequence(statement_instruction(st))) =
        NIL;
      // TODO move declarations up, keep extensions & here
      move_declaration_control_node_declarations_to_statement(ctls);
      controlized = true;
    }
  }
  /* Integrate the statements related to the labels inside its statement
     to the current statement itself: */
  union_used_labels(used_labels, block_used_labels);
  /* Remove local label association hash map: */
  hash_table_free(block_used_labels);
 
#if 0
//  TODO
    if (!hierarchized_labels) {
    /* We are in trouble since we will have an unstructured with goto
       from or to outside this statement sequence, but the statement
       sequence that define the scoping rules is going to disappear...
       So we gather all the declaration and push them up: */
    move_declaration_control_node_declarations_to_statement(ctls);
  }
#endif
    ///* Revert to the variable scope of the outer block statement: */
  // TODO scoping_statement_pop();
  scoping_statement_pop();
  statement_consistent_p(st);
 
  return controlized;
}

References CAR, check_control_coherency(), CONS, CONTROL, control_map_get_blocs(), control_statement, control_successors, controlize_statement(), covers_labels_p(), cp, display_linked_control_nodes(), ENDP, exit, find_a_control_path(), find_exit_control_node(), fix_block_statement_declarations(), FOREACH, gen_free_list(), gen_in_list_p(), gen_last(), gen_length(), get_bool_property(), hash_string, hash_table_free(), hash_table_make(), ifdebug, instruction_sequence, instruction_to_statement(), int, link_2_control_nodes(), make_conditional_control(), make_instruction_unstructured(), make_unstructured(), move_declaration_control_node_declarations_to_statement(), NIL, pips_assert, pips_debug, pips_internal_error, print_control_nodes(), remove_a_control_from_an_unstructured(), remove_a_control_from_an_unstructured_without_relinking(), sequence_statements, STATEMENT, statement_block(), statement_consistent_p(), statement_instruction, statement_sequence(), statement_sequence_p(), statement_test_p(), statement_undefined, union_used_labels(), unlabelled_statement_p(), and unlink_2_control_nodes().

Referenced by controlize_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_statement()

bool controlize_statement	(	control	c_res,
		control	succ,
		hash_table	used_labels
	)

Controlize a statement that is in a control node, that is restructure it to have a HCFG recursively (a hierarchical control flow graph).

Parameters

[in,out]	c_res	is the control node with the main statement to controlize. c_res should already own the statement at entry that will be recursively controlized. c_res can be seen as a potential unstructured entry node.
[in,out]	succ	is the successor control node of c_res at entry. It may be no longer the case at exit if for example the code is unreachable or there is a goto to elsewhere in @p_res. succ can be seen as a potential unstructured exit node.
[in,out]	used_labels	is a way to define a community of label we encounter in a top-down approac during the recursion with their related statements. With it, during the bottom-up approach, we can use it to know if a statement can be control-hierarchized or not. More concretely, it is a hash table mapping a label name to a list of statements that reference it, as their label or because it is a goto to it. This hash map is modified to represent local labels with their local related statements. This table is used later to know if all the statements associated to local labels are local or not. If they are local, the statement can be hierarchized since there is no goto from or to outside location.

Returns

true if the current statement isn't a structured control.

Get the statement to controlized from its control node owner. The invariant is that this statement remains in its control node through the controlizer process. Only the content of the statement may change.

print_statement(st);

Apply the controlizer on a statement sequence, basically by considering it as a control node sequence

Go on with a test:

Controlize a DO-loop à la Fortran:

Controlize a while() or do { } while() loop:

The hard case, the goto, that will add some trouble in this well structured world...

Controlize some function call (that hides many things in PIPS)

FI: IO calls may have control effects; they should be handled here!

PJ: controlize_call() controlize any "nice" statement, so even a C expression used as an instruction:

print_statement(st);

The declarations may be preserved at a lower level if(!ENDP(statement_declarations(st)) && ENDP(statement_declarations(control_statement(c_res)))) { pips_internal_error("Lost local declarations"); }

Update the association between the current statement and its label (the empty label is ignored by update_used_labels()):

Parameters

c_res	_res
succ	ucc
used_labels	sed_labels

Definition at line 2493 of file controlizer.c.

{
  /* Get the statement to controlized from its control node owner. The
     invariant is that this statement remains in its control node through
     the controlizer process. Only the content of the statement may
     change. */
  statement st = control_statement(c_res);
  instruction i = statement_instruction(st);
  bool controlized = false;
 
  ifdebug(5) {
    pips_debug(1,
               "Begin with (st = %p, c_res = %p, succ = %p)\n"
               "st at entry:\n",
               st, c_res, succ);
    statement_consistent_p(st);
    /* print_statement(st); */
    pips_debug(1, "Control list from c_res %p:\n", c_res);
    display_linked_control_nodes(c_res);
    check_control_coherency(succ);
    check_control_coherency(c_res);
  }
 
  switch(instruction_tag(i)) {
 
  case is_instruction_block:
    /* Apply the controlizer on a statement sequence, basically by
       considering it as a control node sequence */
    controlized = controlize_sequence(c_res, succ, used_labels);
    break;
 
  case is_instruction_test:
    /* Go on with a test: */
    controlized = controlize_test(c_res, succ, used_labels);
    break;
 
  case is_instruction_loop:
    /* Controlize a DO-loop à la Fortran: */
    controlized = controlize_loop(c_res, succ, used_labels);
    break;
 
  case is_instruction_whileloop: {
    /* Controlize a while() or do { } while() loop: */
    whileloop wl = instruction_whileloop(i);
    if(evaluation_before_p(whileloop_evaluation(wl)))
      controlized = controlize_whileloop(c_res, succ, used_labels);
    else
      controlized = controlize_repeatloop(c_res, succ, used_labels);
    statement_consistent_p(st);
    break;
  }
 
  case is_instruction_goto: {
    /* The hard case, the goto, that will add some trouble in this well
       structured world... */
    controlized = controlize_goto(c_res, succ, used_labels);
 
    break;
  }
 
  case is_instruction_call:
    /* Controlize some function call (that hides many things in PIPS) */
    /* FI: IO calls may have control effects; they should be handled here! */
    // FI: no specific handling of return? controlized = return_instruction_p(i)
    controlized = controlize_call(c_res, succ);
    statement_consistent_p(st);
    break;
 
  case is_instruction_forloop:
    pips_assert("We are really dealing with a for loop",
                instruction_forloop_p(statement_instruction(st)));
    controlized = controlize_forloop(c_res, succ, used_labels);
    statement_consistent_p(st);
    break;
 
  case is_instruction_expression: {
    expression e = instruction_expression(i);
    if(expression_reference_p(e)) {
      controlized = false;
    }
    else if(expression_call_p(e))
    /* PJ: controlize_call() controlize any "nice" statement, so even a C
       expression used as an instruction: */
      controlized = controlize_call(c_res, succ);
    statement_consistent_p(st);
    break;
  }
 
  default:
    pips_internal_error("Unknown instruction tag %d", instruction_tag(i));
  }
 
  statement_consistent_p(st);
  ifdebug(5) {
    pips_debug(1, "st %p at exit:\n", st);
    /* print_statement(st); */
    pips_debug(1, "Resulting Control c_res %p at exit:\n", c_res);
    display_linked_control_nodes(c_res);
    fprintf(stderr, "---\n");
    /* The declarations may be preserved at a lower level
       if(!ENDP(statement_declarations(st))
       && ENDP(statement_declarations(control_statement(c_res)))) {
       pips_internal_error("Lost local declarations");
       }
    */
 
    check_control_coherency(succ);
    check_control_coherency(c_res);
  }
 
  /* Update the association between the current statement and its
     label (the empty label is ignored by update_used_labels()):
   */
  string label = entity_name(statement_label(st));
  update_used_labels(used_labels, label, st);
 
  return controlized;
}

References check_control_coherency(), control_statement, controlize_call(), controlize_forloop(), controlize_goto(), controlize_loop(), controlize_repeatloop(), controlize_sequence(), controlize_test(), controlize_whileloop(), display_linked_control_nodes(), entity_name, evaluation_before_p, expression_call_p(), expression_reference_p(), fprintf(), ifdebug, instruction_expression, instruction_forloop_p, instruction_tag, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_whileloop, pips_assert, pips_debug, pips_internal_error, statement_consistent_p(), statement_instruction, statement_label, update_used_labels(), and whileloop_evaluation.

Referenced by controlize_forloop(), controlize_loop(), controlize_repeatloop(), controlize_sequence(), controlize_test(), controlize_whileloop(), and hcfg().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_test() [1/2]

static bool controlize_test ( control  c_res, control  succ, hash_table  used_labels  )

static

Builds the control node of a test statement.

Parameters

[in,out]	c_res	is the control node with the test statement (if/then/else)
[in,out]	succ	is the control node successor of c_res
[in,out]	used_labels	is a hash table mapping a label name to a list of statements that use it, as their label or because it is a goto to it

Returns

true if the control node generated is not structured.

The statements of each branch:

Create a control node for each branch of the test:

pips_debug(1, "THEN at entry:\n");

print_statement(s_t);

pips_debug(1, "c_then at entry:\n");

print_statement(control_statement(c_then));

pips_debug(1, "ELSE at entry:\n");

print_statement(s_f);

pips_debug(1, "c_else at entry:\n");

print_statement(control_statement(c_else));

Use 2 hash table to figure out the label references in each branch to know if we will able to restructure them later:

Insert the control nodes for the branch into the current control sequence:

First disconnect the sequence:

Then insert the 2 nodes for each branch, in the correct order since the "then" branch is the first successor of the test and the "else" branch is the second one:

Now we can controlize each branch statement to deal with some control flow fun:

If all the label jumped to from the THEN/ELSE statements are in their respective statement, we can replace the unstructured test by a structured one back:

FI: this test returns a wrong result for if02.c. The reason might be again controlize_goto() or a consequence of the two calls to controlize_statement() above.

Remove the old unstructured control graph:

c_then & c_else are no longer useful:

The test statement is a structured test:

Keep the unstructured test. Normalize the unstructured test where in the control node of the test, the branch statements must be empty since the real code is in the 2 control node successors:

Warn we have an unstructured test:

Update the used labels hash map from the 2 test branches

The local hash tables are no longer useful:

pips_debug(1, "IF at exit:\n");

print_statement(st);

Definition at line 2238 of file controlizer.c.

{
  bool controlized;
  statement st = control_statement(c_res);
  test t = statement_test(st);
  /* The statements of each branch: */
  statement s_t = test_true(t);
  statement s_f = test_false(t);
  /* Create a control node for each branch of the test: */
  control c_then = make_conditional_control(s_t);
  control c_else = make_conditional_control(s_f);
 
  pips_debug(5, "Entering (st = %p, c_res = %p, succ = %p)\n",
             st, c_res, succ);
 
  ifdebug(5) {
    /* pips_debug(1, "THEN at entry:\n"); */
    /* print_statement(s_t); */
    /* pips_debug(1, "c_then at entry:\n"); */
    /* print_statement(control_statement(c_then)); */
    /* pips_debug(1, "ELSE at entry:\n"); */
    /* print_statement(s_f); */
    /* pips_debug(1, "c_else at entry:\n"); */
    /* print_statement(control_statement(c_else)); */
    check_control_coherency(succ);
    check_control_coherency(c_res);
  }
 
  /* Use 2 hash table to figure out the label references in each branch to
     know if we will able to restructure them later: */
  hash_table t_used_labels = hash_table_make(hash_string, 0);
  hash_table f_used_labels = hash_table_make(hash_string, 0);
 
  /* Insert the control nodes for the branch into the current control
     sequence: */
  /* First disconnect the sequence: */
  unlink_2_control_nodes(c_res, succ);
 
  /* Then insert the 2 nodes for each branch, in the correct order since
     the "then" branch is the first successor of the test and the "else"
     branch is the second one: */
  // Correct order: link_2_control_nodes add the new arc in the
  // first slot; so reverse linking of c_else and c_then
  link_3_control_nodes(c_res, c_then, c_else);
  link_2_control_nodes(c_else, succ);
  //link_2_control_nodes(c_res, c_then);
  link_2_control_nodes(c_then, succ);
 
  /* Now we can controlize each branch statement to deal with some control
     flow fun: */
  controlize_statement(c_then, succ, t_used_labels);
  controlize_statement(c_else, succ, f_used_labels);
 
  /* If all the label jumped to from the THEN/ELSE statements are in their
     respective statement, we can replace the unstructured test by a
     structured one back: */
  /* FI: this test returns a wrong result for if02.c. The reason
     might be again controlize_goto() or a consequence of the two
     calls to controlize_statement() above. */
  if(covers_labels_p(s_t, t_used_labels)
     && covers_labels_p(s_f, f_used_labels)) {
    pips_debug(5, "Restructure the IF at control %p\n", c_res);
    test_true(t) = control_statement(c_then);
    test_false(t) = control_statement(c_else);
    /* Remove the old unstructured control graph: */
    control_statement(c_then) = statement_undefined;
    control_statement(c_else) = statement_undefined;
    /* c_then & c_else are no longer useful: */
    remove_a_control_from_an_unstructured_without_relinking(c_then);
    remove_a_control_from_an_unstructured_without_relinking(c_else);
    // You do not want to relink too much, but you should relink a minimum
    link_2_control_nodes(c_res, succ);
 
    /* The test statement is a structured test: */
    controlized = false;
  }
  else {
    pips_debug(5, "Destructure the IF at control %p\n", c_res);
    /* Keep the unstructured test. Normalize the unstructured test where
       in the control node of the test, the branch statements must be
       empty since the real code is in the 2 control node successors: */
    test_true(t) = make_plain_continue_statement();
    test_false(t) = make_plain_continue_statement();
    /* Warn we have an unstructured test: */
    controlized = true;
  }
 
  /* Update the used labels hash map from the 2 test branches */
  union_used_labels(used_labels,
                    union_used_labels(t_used_labels, f_used_labels));
 
  /* The local hash tables are no longer useful: */
  hash_table_free(t_used_labels);
  hash_table_free(f_used_labels);
 
  ifdebug(5) {
    /* pips_debug(1, "IF at exit:\n"); */
    /* print_statement(st); */
    display_linked_control_nodes(c_res);
    check_control_coherency(succ);
    check_control_coherency(c_res);
  }
  pips_debug(5, "Exiting\n");
 
  return controlized;
}

References check_control_coherency(), control_statement, controlize_statement(), covers_labels_p(), display_linked_control_nodes(), hash_string, hash_table_free(), hash_table_make(), ifdebug, link_2_control_nodes(), link_3_control_nodes(), make_conditional_control(), make_plain_continue_statement(), pips_debug, remove_a_control_from_an_unstructured_without_relinking(), statement_test(), statement_undefined, test_false, test_true, union_used_labels(), and unlink_2_control_nodes().

Referenced by controlize_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_test() [2/2]

static bool controlize_test ( statement  st, test  t, control  pred, control  succ, control  c_res, hash_table  used_labels  )

static

Builds the control node of a statement st in c_res which is a test statement t.

Returns

true if the control node generated is not structured_.

pips_debug(1, "THEN at entry:\n");

print_statement(s_t);

pips_debug(1, "c1 at entry:\n");

print_statement(control_statement(c1));

pips_debug(1, "ELSE at entry:\n");

print_statement(s_f);

pips_debug(1, "c2 at entry:\n");

print_statement(control_statement(c2));

Just put the IF statement in c_res so that add_proper_successor_to_predecessor() that may be called from the next controlize() here behave correctly:

If all the label jumped to from the THEN/ELSE statements are in their respecive statement, we can replace the unstructured test by a structured one:

c1 & c2 are no longer useful:

Be very careful when chaining c_res as successor of pred: if pred is associated to a test, the position of c_res as first or second successor of c_res is unknown. It should have been set by the caller.

You might survive, using the fact that the true branch has been processed first because of the order of the two recursive calls to controlize(). The false branch whill be linked as second successor. But another controlize_xxx might have decided to link pred and c_res before calling controlize() and controlize_test(). Too much guessing IMHO (FI).

control_successors(pred) = ADD_SUCC(c_res, pred);

pips_debug(1, "IF at exit:\n");

print_statement(st);

Definition at line 1651 of file old_controlizer.c.

{
  hash_table
    t_used_labels = hash_table_make(hash_string, 0),
    f_used_labels = hash_table_make(hash_string, 0);
  control c1 = make_conditional_control(test_true(t));
  control c2 = make_conditional_control(test_false(t));
  control c_join = make_control(make_plain_continue_statement(), NIL, NIL);
  statement s_t = test_true(t);
  statement s_f = test_false(t);
  bool controlized;
 
  pips_debug(5, "Entering (st = %p, pred = %p, succ = %p, c_res = %p)\n",
             st, pred, succ, c_res);
 
  ifdebug(5) {
    /* pips_debug(1, "THEN at entry:\n"); */
    /* print_statement(s_t); */
    /* pips_debug(1, "c1 at entry:\n"); */
    /* print_statement(control_statement(c1)); */
    /* pips_debug(1, "ELSE at entry:\n"); */
    /* print_statement(s_f); */
    /* pips_debug(1, "c2 at entry:\n"); */
    /* print_statement(control_statement(c2)); */
    check_control_coherency(pred);
    check_control_coherency(succ);
    check_control_coherency(c_res);
  }
 
  controlize(s_t, c_res, c_join, c1, t_used_labels);
  /* Just put the IF statement in c_res so that
     add_proper_successor_to_predecessor() that may be called from the
     next controlize() here behave correctly: */
  control_statement(c_res) = st;
  controlize(s_f, c_res, c_join, c2, f_used_labels);
 
  if(covers_labels_p(s_t, t_used_labels) &&
     covers_labels_p(s_f, f_used_labels)) {
    /* If all the label jumped to from the THEN/ELSE statements are in
       their respecive statement, we can replace the unstructured test by
       a structured one: */
    test it = make_test(test_condition(t),
                        control_statement(c1),
                        control_statement(c2));
    /* c1 & c2 are no longer useful: */
    free_a_control_without_its_statement(c1);
    free_a_control_without_its_statement(c2);
 
    st = normalize_statement(st);
    UPDATE_CONTROL(c_res,
                   make_statement(statement_label(st),
                                  statement_number(st),
                                  STATEMENT_ORDERING_UNDEFINED,
                                  strdup(statement_comments(st)),
                                  make_instruction(is_instruction_test, it),
                                  gen_copy_seq(statement_declarations(st)),
                                  strdup(statement_decls_text(st)),
                                  copy_extensions(statement_extensions(st)), make_synchronization_none()),
                   ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE(pred, c_res),
                   CONS(CONTROL, succ, NIL));
    control_predecessors(succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_res, succ);
    controlized = false;
  }
  else {
    // Keep the unstructured test:
    UPDATE_CONTROL(c_res, st,
                   ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE(pred, c_res),
                   CONS(CONTROL, c1, CONS(CONTROL, c2, NIL)));
    test_true(t) = make_plain_continue_statement();
    test_false(t) = make_plain_continue_statement();
    control_predecessors(succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_join, succ);
    control_successors(c_join) = CONS(CONTROL, succ, NIL);
    controlized = true;
  }
 
  /* Be very careful when chaining c_res as successor of pred: if pred is
     associated to a test, the position of c_res as first or second
     successor of c_res is unknown. It should have been set by the
     caller.
 
     You might survive, using the fact that the true branch has been
     processed first because of the order of the two recursive calls to
     controlize(). The false branch whill be linked as second
     successor. But another controlize_xxx might have decided to link pred
     and c_res before calling controlize() and controlize_test(). Too much
     guessing IMHO (FI). */
 
  /* control_successors(pred) = ADD_SUCC(c_res, pred); */
  add_proper_successor_to_predecessor(pred, c_res);
 
  union_used_labels(used_labels,
                    union_used_labels(t_used_labels, f_used_labels));
 
  hash_table_free(t_used_labels);
  hash_table_free(f_used_labels);
 
  ifdebug(5) {
    /* pips_debug(1, "IF at exit:\n"); */
    /* print_statement(st); */
    display_linked_control_nodes(c_res);
    check_control_coherency(pred);
    check_control_coherency(succ);
    check_control_coherency(c_res);
  }
  pips_debug(5, "Exiting\n");
 
  return(controlized);
}

References ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE, ADD_PRED_IF_NOT_ALREADY_HERE, add_proper_successor_to_predecessor(), check_control_coherency(), CONS, CONTROL, control_predecessors, control_statement, control_successors, controlize(), copy_extensions(), covers_labels_p(), display_linked_control_nodes(), free_a_control_without_its_statement(), gen_copy_seq(), hash_string, hash_table_free(), hash_table_make(), ifdebug, is_instruction_test, make_conditional_control(), make_control(), make_instruction(), make_plain_continue_statement(), make_statement(), make_synchronization_none(), make_test(), NIL, normalize_statement(), pips_debug, statement_comments, statement_declarations, statement_decls_text, statement_extensions, statement_label, statement_number, STATEMENT_ORDERING_UNDEFINED, strdup(), test_condition, test_false, test_true, union_used_labels(), and UPDATE_CONTROL.

Referenced by controlize().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_whileloop() [1/2]

static bool controlize_whileloop ( control  c_res, control  succ, hash_table  used_labels  )

static

Computes the control graph of a Fortran or C while loop statement.

Parameters

[in,out]	c_res	is the entry control node with the do-loop statement to controlize. If the do-loop has complex control code such as some goto to outside, it is transformed into an equivalent control graph.
[in,out]	succ	must be the control node successor of c_res that will be the current end of the control node sequence and an exit node
[in,out]	used_labels	is a hash table mapping a label name to a list of statements that use it, as their label or because it is a goto to it

Returns

true if the code is not a structured control.

To track the statement related to labels inside the loop body:

Remove the loop body from the loop just in case we want to prettyprint our work in progress:

Create a control node to host the loop body and insert it in the control graph:

TODO switch(get_prettyprint_language_tag()) { case is_language_fortran: case is_language_fortran95: cs = strdup(concatenate(prev_comm, get_comment_sentinel(), " DO loop ", lab, " with exit had to be desugared\n", NULL)); break; case is_language_c: cs = prev_comm; break; default: pips_internal_error("This language is not handled !"); break; }

Recurse by controlizing inside the loop:

First the easy way. We have a kindly control-localized loop body, revert to the original code

Remove the control node from the control graph by carefully relinking around:

Remove also the dummy increment node that has not been used either:

Move the loop body into its own loop:

We are in trouble since the loop body is not locally structured, there are goto from inside or outside the loop body. So we replace the while loop with a desugared version with an equivalent control graph.

Update the increment control node with the real computation:

First remove the dummy statement added above:

And put "i = i + s" instead:

Now build the desugared loop:

We can replace the former loop statement by the new header. That means that all pragma, comment, extensions, label on the previous loop stay on this.

Add the continuation test between the header and the body that are already connected:

Detach succ from the loop body exit

And reconnect it to the test node to make the loop:

Add the else branch of the test toward the loop exit: arc ordering matters

Keep track of labels that were used by the statements of the loop:

Definition at line 847 of file controlizer.c.

{
  /* To track the statement related to labels inside the loop body: */
  hash_table loop_used_labels = hash_table_make(hash_string, 0);
  statement sl = control_statement(c_res);
 
  pips_debug(5, "(st = %p, c_res = %p, succ = %p)\n", sl, c_res, succ);
 
  whileloop wl = statement_whileloop(sl);
  statement body_s = whileloop_body(wl);
 
  /* Remove the loop body from the loop just in case we want to
     prettyprint our work in progress: */
  // incompatible with debugging code
  //whileloop_body(wl) = statement_undefined;
  whileloop_body(wl) = make_plain_continue_statement();
 
  /* Create a control node to host the loop body and insert it in the
     control graph: */
  control c_body = make_conditional_control(body_s);
  // FI: if c_test were already available, it should be used instead
  // of succ
  // insert_control_in_arc(c_body, c_res, succ);
 
  // FI: this should be language neutral. The prettyprinter is
  // supposed to fix comments according to language rules...
  /* TODO
  switch(get_prettyprint_language_tag()) {
    case is_language_fortran:
    case is_language_fortran95:
      cs = strdup(concatenate(prev_comm,
                              get_comment_sentinel(),
                              "     DO loop ",
                              lab,
                              " with exit had to be desugared\n",
                              NULL));
      break;
    case is_language_c:
      cs = prev_comm;
      break;
    default:
      pips_internal_error("This language is not handled !");
      break;
  }
  */
 
  control c_test = make_control(unsugared_whileloop_test(sl), NIL, NIL);
  /* Recurse by controlizing inside the loop: */
  link_2_control_nodes(c_body, c_test);
  bool controlized = controlize_statement(c_body, c_test, loop_used_labels);
 
  if (!controlized) {
    /* First the easy way. We have a kindly control-localized loop body,
       revert to the original code */
    pips_debug(6, "Since we can keep the  whileloop, remove the useless control node %p that was allocated for the loop_body.\n", c_body);
    control_statement(c_body) = statement_undefined;
    /* Remove the control node from the control graph by carefully
       relinking around: */
    remove_a_control_from_an_unstructured(c_body);
    /* Remove also the dummy increment node that has not been used
       either: */
    //remove_a_control_from_an_unstructured(c_inc);
    /* Move the loop body into its own loop: */
    whileloop_body(wl) = body_s;
  }
  else {
    /* We are in trouble since the loop body is not locally structured,
       there are goto from inside or outside the loop body. So we
       replace the  while loop with a desugared version with an equivalent
       control graph. */
    /* Update the increment control node with the real computation: */
    /* First remove the dummy statement added above: */
    //free_statement(control_statement(c_inc));
    /* And put "i = i + s" instead: */
    //control_statement(c_inc) = unsugared_loop_inc(sl);
    /* Now build the desugared loop: */
    /* We can replace the former loop statement by the new header. That
       means that all pragma, comment, extensions, label on the previous
       loop stay on this. */
    //control_statement(c_res) = unsugared_loop_header(sl);
    // FI: c_res is useless and should be identified with c_test
    control_statement(c_res) = unsugared_whileloop_header(sl);
    /* Add the continuation test between the header and the body that are
       already connected: */
    //control c_test = make_control(unsugared_loop_test(sl), NIL, NIL);
    unlink_2_control_nodes(c_res, succ);
    link_2_control_nodes(c_res, c_test);
    //insert_control_in_arc(c_test, c_res, c_body);
    /* Detach succ from the loop body exit */
    //unlink_2_control_nodes(c_body, succ);
    /* And reconnect it to the test node to make the loop: */
    //link_2_control_nodes(c_body, c_test);
    /* Add the else branch of the test toward the loop exit: arc
       ordering matters */
    unlink_2_control_nodes(c_test, c_body);
    //link_2_control_nodes(c_test, succ);
    //link_2_control_nodes(c_test, c_body);
    link_3_control_nodes(c_test, c_body, succ);
    // link_2_control_nodes(c_test, c_res);
    //unlink_2_control_nodes(c_res, succ);
 
    pips_assert("c_test is a test with two successors",
                gen_length(control_successors(c_test))==2
                && statement_test_p(control_statement(c_test)));
    pips_assert("c_body may have two successors if it is a test",
                ( gen_length(control_successors(c_body))==2
                  && statement_test_p(control_statement(c_body)) )
                ||
                ( gen_length(control_successors(c_body))==1
                  && !statement_test_p(control_statement(c_body)) )
                );
    pips_assert("c_res should not be a test",
                gen_length(control_successors(c_res))==1
                && !statement_test_p(control_statement(c_res)) );
  }
 
  /* Keep track of labels that were used by the statements of the loop: */
  union_used_labels( used_labels, loop_used_labels);
  hash_table_free(loop_used_labels);
 
  pips_debug(5, "Exiting\n");
 
  return controlized;
}

References c_test(), control_statement, control_successors, controlize_statement(), gen_length(), hash_string, hash_table_free(), hash_table_make(), link_2_control_nodes(), link_3_control_nodes(), make_conditional_control(), make_control(), make_plain_continue_statement(), NIL, pips_assert, pips_debug, remove_a_control_from_an_unstructured(), statement_test_p(), statement_undefined, statement_whileloop(), union_used_labels(), unlink_2_control_nodes(), unsugared_whileloop_header(), unsugared_whileloop_test(), and whileloop_body.

Referenced by controlize_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

controlize_whileloop() [2/2]

static bool controlize_whileloop ( statement  st, whileloop  l, control  pred, control  succ, control  c_res, hash_table  used_labels  )

static

CONTROLIZE_WHILELOOP computes in C_RES the control graph of the loop L (of statement ST) with PREDecessor and SUCCessor.

Derived by FI from controlize_loop() NN : What about other kind of whileloop, evaluation = after ? TO BE IMPLEMENTED

The edges between c_res and c_body, created by the above call to controlize are useless. The edge succ from c_res to c_body is erased by the UPDATE_CONTROL macro.

control_predecessors(c_res) = CONS(CONTROL, pred, control_predecessors(c_res));

ADD_PRED(pred, c_res);

Cannot be consistent yet!

ifdebug(5) check_control_coherency(c_res);

control_successors(pred) = ADD_SUCC(c_res, pred);

Definition at line 692 of file old_controlizer.c.

{
    hash_table loop_used_labels = hash_table_make(hash_string, 0);
    control c_body = make_conditional_control(whileloop_body(l));
    bool controlized;
 
    pips_debug(5, "(st = %p, pred = %p, succ = %p, c_res = %p)\n",
               st, pred, succ, c_res);
 
    controlize(whileloop_body(l), c_res, c_res, c_body, loop_used_labels);
 
    if(covers_labels_p(whileloop_body(l),loop_used_labels)) {
        whileloop new_l = make_whileloop(whileloop_condition(l),
                                         control_statement(c_body),
                                         whileloop_label(l),
                                         whileloop_evaluation(l));
 
        /* The edges between c_res and c_body, created by the above call to
         * controlize are useless. The edge succ
         * from c_res to c_body is erased by the UPDATE_CONTROL macro.
         */
        gen_remove(&control_successors(c_body), c_res);
        gen_remove(&control_predecessors(c_body), c_res);
        gen_remove(&control_predecessors(c_res), c_body);
 
        st = normalize_statement(st);
        UPDATE_CONTROL(c_res,
                       make_statement(statement_label(st),
                                      statement_number(st),
                                      STATEMENT_ORDERING_UNDEFINED,
                                      strdup(statement_comments(st)),
                                      make_instruction(is_instruction_whileloop,
                                                       new_l),
                                      gen_copy_seq(statement_declarations(st)),
                                      strdup(statement_decls_text(st)),
                                      copy_extensions(statement_extensions(st)), make_synchronization_none()),
                       ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE(pred, c_res),
                       CONS(CONTROL, succ, NIL));
        controlized = false;
    }
    else {
        control_statement(c_res) = whileloop_test(st);
        /* control_predecessors(c_res) =
           CONS(CONTROL, pred, control_predecessors(c_res)); */
        /* ADD_PRED(pred, c_res); */
        control_predecessors(c_res) =
           gen_once(pred, control_predecessors(c_res));
        control_successors(c_res) =
                CONS(CONTROL, succ, control_successors(c_res));
        controlized = true ;
        /* Cannot be consistent yet! */
        /* ifdebug(5) check_control_coherency(c_res); */
    }
    control_predecessors(succ) = ADD_PRED_IF_NOT_ALREADY_HERE(c_res, succ);
    add_proper_successor_to_predecessor(pred, c_res);
    /* control_successors(pred) = ADD_SUCC(c_res, pred); */
 
    ifdebug(5) check_control_coherency(c_res);
 
    union_used_labels( used_labels, loop_used_labels);
    hash_table_free(loop_used_labels);
 
    pips_debug(5, "Exiting\n");
 
    return(controlized);
}

References ADD_PRED_AND_COPY_IF_NOT_ALREADY_HERE, ADD_PRED_IF_NOT_ALREADY_HERE, add_proper_successor_to_predecessor(), check_control_coherency(), CONS, CONTROL, control_predecessors, control_statement, control_successors, controlize(), copy_extensions(), covers_labels_p(), gen_copy_seq(), gen_once(), gen_remove(), hash_string, hash_table_free(), hash_table_make(), ifdebug, is_instruction_whileloop, make_conditional_control(), make_instruction(), make_statement(), make_synchronization_none(), make_whileloop(), NIL, normalize_statement(), pips_debug, statement_comments, statement_declarations, statement_decls_text, statement_extensions, statement_label, statement_number, STATEMENT_ORDERING_UNDEFINED, strdup(), true, union_used_labels(), UPDATE_CONTROL, whileloop_body, whileloop_condition, whileloop_evaluation, whileloop_label, and whileloop_test().

Referenced by controlize().

Here is the call graph for this function:

Here is the caller graph for this function:

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 local mapping.

Parameters

	st[in]	is the statement we want to check if it owns all allusions to the given label name in the used_labels mapping
[in]	used_labels	is a hash table mapping a label name to a list of statements that use it (à la Label_statements), as their own label or because it is a goto to it

Returns

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

print_statement(st);

For all the labels in used_labels:

The statements using a label name in used_labels:

For all the statements associated to this label name:

In one special case, def may have lost its use of a label: if it is a goto to the next statement (see controlize_goto()). Then it is a simple continue. This special configuration never happens, except in code generated by the inlining pass... or written by a weird programmer. It seems easier to keep Label_statements consistent rather than fix the problem here.

Verify that def is in all the statements associated globally to the label name according to module-level Label_statements.

Not useful to go on:

Definition at line 294 of file controlizer.c.

                                                    {
  ifdebug(5) {
    pips_debug(5, "Statement %td (%p): \n ", statement_number(st), st);
    /* print_statement(st); */
  }
  /* For all the labels in used_labels: */
  void * cl = NULL;
  list stats = NIL;
  string name = string_undefined;
  while((cl=hash_table_scan(used_labels, cl, (void **) &name, (void **) &stats))) {
      // HASH_MAP(name, sts, {
      /* The statements using a label name in used_labels: */
      //list stats = (list) sts;
 
      /* For all the statements associated to this label name: */
    list sl = (list) hash_get_default_empty_list(Label_statements, (void *) name);
      FOREACH(STATEMENT, def, sl) {
        /* In one special case, def may have lost its use of a label:
           if it is a goto to the next statement (see
           controlize_goto()). Then it is a simple
           continue. This special configuration never happens, except
           in code generated by the inlining pass... or written by a
           weird programmer. It seems easier to keep Label_statements
           consistent rather than fix the problem here. */
        bool found = false;
        /* Verify that def is in all the statements associated globally to
           the label name according to module-level Label_statements. */
        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_table_scan(), ifdebug, Label_statements, NIL, pips_debug, STATEMENT, statement_number, and string_undefined.

Referenced by controlize_sequence(), and controlize_test().

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

Update the global module-level Label_statements table according to the labels a statement references.

It also creates a control node for this statement if it has a label and register it to the module-global Label_control table.

A statement can reference a label if it is its own label or if the statement is indeed a goto to this label.

Label found in Fortran do-loop to set loop boundary or in Fortran IO using some FORMAT through its label are not considered here since it is not related to control flow.

Parameters

[in]

st

is the statement to look at for labels

Add the statement to its own label reference, if needed:

Associate globally the statement to its own label:

Create the control node with the statement inside:

If the statement is a goto, add to the target label a reference to this statement:

Associate the statement to the target label:

Do nothing special for other kind of instructions

Definition at line 398 of file controlizer.c.

                                                     {
  instruction i;
 
  /* Add the statement to its own label reference, if needed: */
  string name = entity_name(statement_label(st));
  if (!empty_global_label_p(name)) {
    /* Associate globally the statement to its own label: */
    update_used_labels(Label_statements, name, st);
    /* Create the control node with the statement inside: */
    control c = make_control(st, NIL, NIL);
    pips_debug(8, "control %p allocated for label \"%s\"", c, name);
    hash_put(Label_control, name, (char *)c);
  }
 
  switch(instruction_tag(i = statement_instruction(st))) {
    /* If the statement is a goto, add to the target label a reference to
       this statement: */
  case is_instruction_goto: {
    string where = entity_name(statement_label(instruction_goto(i)));
    /* Associate the statement to the target label: */
    update_used_labels(Label_statements, where, st);
    break;
  }
 
  case is_instruction_unstructured:
    pips_internal_error("Found unstructured", "");
 
  default:
    /* Do nothing special for other kind of instructions */
    ;
  }
}

References empty_global_label_p(), entity_name, hash_put(), instruction_goto, instruction_tag, is_instruction_goto, is_instruction_unstructured, Label_control, Label_statements, make_control(), NIL, pips_debug, pips_internal_error, statement_instruction, statement_label, and update_used_labels().

Referenced by create_statements_of_labels().

Here is the call graph for this function:

Here is the caller graph for this function:

create_statements_of_labels() [1/2]

static void create_statements_of_labels ( st  )

static

Definition at line 1822 of file old_controlizer.c.

{
    gen_recurse(st,
                statement_domain,
                gen_true,
                create_statements_of_label);
}

References create_statements_of_label(), gen_recurse, gen_true(), and statement_domain.

Referenced by control_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

create_statements_of_labels() [2/2]

static void create_statements_of_labels ( statement  st )

static

Initialize the global Label_statements mapping for the module that associates for any label in the module the statements that refer to it.

Parameters

[in]

st

is the module (top) statement

Apply create_statements_of_label() on all the module statements

Definition at line 437 of file controlizer.c.

                                                      {
  /* Apply create_statements_of_label() on all the module statements */
  gen_recurse(st,
              statement_domain,
              gen_true,
              create_statements_of_label);
}

References create_statements_of_label(), gen_recurse, gen_true(), and statement_domain.

Referenced by hcfg().

Here is the call graph for this function:

Here is the caller graph for this function:

find_exit_control_node()

control find_exit_control_node	(	list	ctls,
		control	succ
	)

Find the exit node of a sub-CFG defined by the list of nodes ctls and by the first node to execute when finished.

The entry node of the sub-CFG is the last node of the ctls list, because it is built backwards.

RK: ctls is built backwards: hence its exit node is the first node in the list.

FI: in fact, it's a bit more complicated...

The underlying purpose of this function only called from controlize_sequence(() is to help separate a sub CFG with only one entry and one exit point from the global graph. The entry node is easy to find as CONTROL(CAR(gen_last(ctls))). The exit node may be anywhere because of the goto statements. The succ node is the first node executed after the CFG defined by ctls. But it may have no predecessor or only some of its predecessors belong to the global graph but not to the local graph. So we are interested in predecessors of succ that are reachable from the entry node. Unless we are lucky because succ has only one predecessor and this predecessor has only one successor, succ. In that case, the predecessor of succ is the exit node.

The control graph may be altered with a newly allocated node or not.

Parameters

ctls	list of the control nodes belonging to the subgraph to isolate
	succ is the first control node not in ctls to be executed after the nodes in ctls.

Returns

exit, the existing or newly allocated exit node. The subgraph defined by ctls is updated when a new node is allocated.

Two algorithms at least are possible: we can either start from the predecessors of succ and check that a backward control path to the entry of ctls exists, or we can start from entry and look for control paths reaching succ. The second approach is implemented here. tatic

look for a successor of entry that is a predecessor of succ

succ may be unreachable because ctls loops on itself

Parameters

ctls	tls
succ	ucc

Definition at line 1739 of file controlizer.c.

{
  control exit = CONTROL(CAR(ctls));
  control entry = CONTROL(CAR(gen_last(ctls)));
 
  ifdebug(8) {
    FOREACH(CONTROL, c, ctls) {
      check_control_coherency(c);
    }
    check_control_coherency(succ);
  }
 
  if(!(ENDP(control_successors(exit))
       || (gen_length(control_successors(exit))==1
           && CONTROL(CAR(control_successors(exit)))==succ))) {
    /* look for a successor of entry that is a predecessor of succ */
    list visited = NIL;
    list to_be_visited = gen_copy_seq(control_successors(entry));
    bool found_p = false;
    exit = control_undefined;
 
    while(!ENDP(to_be_visited)) {
      FOREACH(CONTROL, c, to_be_visited) {
        if(gen_in_list_p(succ, control_successors(c))) {
          if(control_undefined_p(exit))
            exit = make_control(make_plain_continue_statement(), NIL, NIL);
 
          insert_control_in_arc(exit, c, succ);
          found_p = true;
        }
        if(c!=succ) { // Should always be true...
          visited = CONS(CONTROL, c, visited);
          gen_remove(&to_be_visited, c);
          FOREACH(CONTROL, s, control_successors(c)) {
            if(!gen_in_list_p(s, visited)
               && !gen_in_list_p(s, to_be_visited)
               && s!=succ && s!=exit)
              // update the loop variable... within the two nested loops
              to_be_visited = CONS(CONTROL, s, to_be_visited);
          }
        }
        else {
          pips_internal_error("design error\n.");
        }
      }
    }
 
    gen_free_list(visited);
    gen_free_list(to_be_visited);
 
    if(!found_p) {
    /* succ may be unreachable because ctls loops on itself*/
      exit = make_control(make_plain_continue_statement(), NIL, NIL);
    }
  }
 
  ifdebug(8) {
    FOREACH(CONTROL, c, ctls) {
      check_control_coherency(c);
    }
    check_control_coherency(exit);
  }
 
return exit;
}

References CAR, check_control_coherency(), CONS, CONTROL, control_successors, control_undefined, control_undefined_p, ENDP, exit, FOREACH, gen_copy_seq(), gen_free_list(), gen_in_list_p(), gen_last(), gen_length(), gen_remove(), ifdebug, insert_control_in_arc(), make_control(), make_plain_continue_statement(), NIL, and pips_internal_error.

Referenced by controlize_sequence().

Here is the call graph for this function:

Here is the caller graph for this function:

find_or_create_exit_control_node()

control find_or_create_exit_control_node	(	list	ctls,
		control	succ
	)

FI: remake of function above, incomplete backward approach, now obsolete because the forward approach works.

But who knows? The complexity of the backward approach might be lower than the complexity of the forward approach?

Because of the recursive descent in the AST...

Let's try to use an existing node as exit node

A new node is needed as exit node

The CFG contains an infinite loop and succ is never reached?

FI: we might need to check that the predecessor is not still c_res?

Why would we link it to succ to have it unlinked by the caller?

succ must be removed from the current CFG. Its predecessors within the current CFG must be moved onto the new exit node

Is c in the current CFG or in anoter one at a higher level? Typical case: the current sequence is a test branch and hence succ has two predecessors at the higher level

orward_control_path_p(entry, c)

hpftest62b.f: the sequence below pulls an extra statement in the unstructured that is being built

Parameters

ctls	tls
succ	ucc

Definition at line 1809 of file controlizer.c.

{
  control exit = control_undefined;
  //control entry = CONTROL(CAR(gen_last(ctls)));
 
  ifdebug(8) {
    FOREACH(CONTROL, c, ctls) {
      check_control_coherency(c);
    }
    check_control_coherency(succ);
  }
 
  /* Because of the recursive descent in the AST... */
  pips_assert("succ has only one successor or none",
              gen_length(control_successors(succ))<=1);
 
  /* Let's try to use an existing node as exit node */
  if(gen_length(control_predecessors(succ))==1) {
    control c = CONTROL(CAR(control_predecessors(succ)));
    if(gen_length(control_successors(c))==1) {
      pips_debug(8, "succ has a fitting predecessor as exit.\n");
      exit = c;
    }
  }
 
  if(control_undefined_p(exit)) {
    /* A new node is needed as exit node */
    exit = make_control(make_plain_continue_statement(), NIL, NIL);
    if(gen_length(control_predecessors(succ))==0) {
      /* The CFG contains an infinite loop and succ is never reached? */
      /* FI: we might need to check that the predecessor is not still
         c_res? */
      /* Why would we link it to succ to have it unlinked by the
         caller? */
      pips_debug(8, "succ is unreachable and a new exit node %p is created.\n",
                 exit);
    }
    else {
      /* succ must be removed from the current CFG. Its predecessors within
         the current CFG must be moved onto the new exit node */
      FOREACH(CONTROL, c, control_predecessors(succ)) {
        /* Is c in the current CFG or in anoter one at a higher
           level? Typical case: the current sequence is a test branch
           and hence succ has two predecessors at the higher level */
        if(1 /*forward_control_path_p(entry, c)*/) {
          // FI: could we use link and unlink of control nodes?
          list pcl = list_undefined;
          for(pcl = control_successors(c); !ENDP(pcl); POP(pcl)) {
            control cc = CONTROL(CAR(pcl));
            if(cc==succ)
              CONTROL_(CAR(pcl))=exit;
          }
          control_predecessors(exit) = gen_nconc(control_predecessors(exit),
                                                 CONS(CONTROL, c, NIL));
        }
      }
      //control_predecessors(exit) = control_predecessors(succ);
      //control_predecessors(succ) = CONS(CONTROL, exit, NIL);
      /* hpftest62b.f: the sequence below pulls an extra statement in
         the unstructured that is being built */
      /*
      statement fs = control_statement(succ);
      statement es = control_statement(exit);
      control_statement(exit) = fs;
      control_statement(succ) = es;
      */
      pips_debug(8, "succ is reachable thru %d control paths "
                 "but a new exit node %p is created.\n",
                 (int) gen_length(control_predecessors(exit)), exit);
    }
  }
 
  ifdebug(8) {
    FOREACH(CONTROL, c, ctls) {
      check_control_coherency(c);
    }
    check_control_coherency(exit);
  }
 
return exit;
}

References CAR, check_control_coherency(), CONS, CONTROL, CONTROL_, control_predecessors, control_successors, control_undefined, control_undefined_p, ENDP, exit, FOREACH, gen_length(), gen_nconc(), ifdebug, list_undefined, make_control(), make_plain_continue_statement(), NIL, pips_assert, pips_debug, and POP.

Here is the call graph for this function:

forloop_header()

statement forloop_header

(

statement

sl

)

Parameters

sl

l

Definition at line 765 of file old_controlizer.c.

{
  forloop l = instruction_forloop(statement_instruction(sl));
  statement hs = instruction_to_statement(make_instruction_expression(forloop_initialization(l)));
  statement_number(hs) = statement_number(sl);
 
  return hs;
}

References forloop_initialization, instruction_forloop, instruction_to_statement(), make_instruction_expression(), statement_instruction, and statement_number.

Referenced by controlize_forloop().

Here is the call graph for this function:

Here is the caller graph for this function:

forloop_inc()

statement forloop_inc

(

statement

sl

)

ifdebug(8) {

pips_debug(8, "Increment expression: ");

print_expression(inc);

}

Parameters

sl

l

Definition at line 806 of file old_controlizer.c.

{
  forloop l = instruction_forloop(statement_instruction(sl));
  expression inc = forloop_increment(l);
  statement is = instruction_to_statement(make_instruction_expression(inc));
  statement_number(is) = statement_number(sl);
 
  /* ifdebug(8) { */
  /*   pips_debug(8, "Increment expression: "); */
  /*   print_expression(inc); */
  /* } */
 
  return is;
}

References forloop_increment, instruction_forloop, instruction_to_statement(), make_instruction_expression(), statement_instruction, and statement_number.

Referenced by controlize_forloop().

Here is the call graph for this function:

Here is the caller graph for this function:

forloop_test()

statement forloop_test

(

statement

sl

)

strdup("")

ifdebug(8) {

pips_debug(8, "Condition expression: ");

print_expression(cond);

}

Parameters

sl

l

Definition at line 775 of file old_controlizer.c.

{
  forloop l = instruction_forloop(statement_instruction(sl));
  expression cond = forloop_condition(l);
  call c =  make_call(entity_intrinsic(C_NOT_OPERATOR_NAME),
                      CONS(EXPRESSION,
                           copy_expression(cond),
                           NIL));
  test t = make_test(make_expression(make_syntax(is_syntax_call, c),
                                     normalized_undefined),
                     make_plain_continue_statement(),
                     make_plain_continue_statement());
  string csl = statement_comments(sl);
  string cs = empty_comments_p(csl)? empty_comments /* strdup("") */ : strdup(csl);
 
  statement ts = make_statement(entity_empty_label(),
                                statement_number(sl),
                                STATEMENT_ORDERING_UNDEFINED,
                                cs,
                                make_instruction(is_instruction_test, t),NIL,NULL,
                                copy_extensions(statement_extensions(sl)), make_synchronization_none());
 
  /* ifdebug(8) { */
  /*   pips_debug(8, "Condition expression: "); */
  /*   print_expression(cond); */
  /* } */
 
  return ts;
}

References C_NOT_OPERATOR_NAME, CONS, copy_expression(), copy_extensions(), empty_comments, empty_comments_p(), entity_empty_label(), entity_intrinsic(), EXPRESSION, forloop_condition, instruction_forloop, is_instruction_test, is_syntax_call, make_call(), make_expression(), make_instruction(), make_plain_continue_statement(), make_statement(), make_synchronization_none(), make_syntax(), make_test(), NIL, normalized_undefined, statement_comments, statement_extensions, statement_instruction, statement_number, STATEMENT_ORDERING_UNDEFINED, and strdup().

Referenced by controlize_forloop().

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

[in]

name

is the string name of the label entity

The label must exist in the table.

Returns

the associated control node.

Definition at line 207 of file 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 controlize_goto().

Here is the call graph for this function:

Here is the caller graph for this function:

hcfg()

statement hcfg

(

statement

st

)

Compute the hierarchical control flow graph (HCFG) of a statement.

Parameters

st	is the statement we want to "controlize"

Returns

the unstructured with the control graph

To help debugging, force some properties:

Initialize an empty association from label to the statements using them:

Initialize global tables:

Build the global table associating for any label all the statements that refer to it:

Construct the entry and exit control node of the unstructured to generate. First get the control node for all the code:

And make a successor node that is an empty instruction at first:

By default the entry is just connected to the exit that is the successor:

To track declaration scoping independently of control structure:

Build the HCFG from the module statement:

Since this HCFG computation is quite general, we may have really an unstructured at the top level, which is not possible when dealing from the parser output.

The 2 control nodes are indeed still a simple sequence, so it is a structured statement at the top level and it is useless to build an unstructured to store it.

Really remove the useless by contruction statement too:

For all the other case, it is not structured code at top level, so build an unstructured statement to represent it:

Clean up scoping stack:

Reset the tables used

Since the controlizer is a sensitive pass, avoid leaking basic errors...

Parameters

st

t

Definition at line 2621 of file controlizer.c.

{
  statement result;
 
  pips_assert("Statement should be OK.", statement_consistent_p(st));
  ifdebug(1) {
    /* To help debugging, force some properties: */
    set_bool_property("PRETTYPRINT_BLOCKS", true);
    set_bool_property("PRETTYPRINT_EMPTY_BLOCKS", true);
  }
 
  /* Initialize an empty association from label to the statements using
     them: */
  hash_table used_labels = hash_table_make(hash_string, 0);
 
  /* Initialize global tables: */
  Label_statements = hash_table_make(hash_string, LABEL_TABLES_SIZE);
  Label_control = hash_table_make(hash_string, LABEL_TABLES_SIZE);
  /* Build the global table associating for any label all the statements
     that refer to it: */
  create_statements_of_labels(st);
 
  /* Construct the entry and exit control node of the unstructured to
     generate. First get the control node for all the code: */
  control entry = make_conditional_control(st);
  /* And make a successor node that is an empty instruction at first: */
  control exit = make_control(make_plain_continue_statement(), NIL, NIL);
  /* By default the entry is just connected to the exit that is the
     successor: */
  link_2_control_nodes(entry, exit);
 
  /* To track declaration scoping independently of control structure: */
  make_scoping_statement_stack();
 
  /* Build the HCFG from the module statement: */
  (void) controlize_statement(entry, exit, used_labels);
 
  /* Since this HCFG computation is quite general, we may have really an
     unstructured at the top level, which is not possible when dealing
     from the parser output. */
  if (gen_length(control_successors(entry)) == 1
      && CONTROL(CAR(control_successors(entry))) == exit) {
    /* The 2 control nodes are indeed still a simple sequence, so it is
       a structured statement at the top level and it is useless to
       build an unstructured to store it. */
    result = control_statement(entry);
    free_a_control_without_its_statement(entry);
    /* Really remove the useless by contruction statement too: */
    free_a_control_without_its_statement(exit);
  }
  else {
    /* For all the other case, it is not structured code at top level, so
       build an unstructured statement to represent it: */
    unstructured u = make_unstructured(entry, exit);
    result = instruction_to_statement(make_instruction_unstructured(u));
  }
 
  /* Clean up scoping stack: */
  free_scoping_statement_stack();
 
  /* Reset the tables used */
  hash_table_free(Label_statements);
  hash_table_free(Label_control);
  hash_table_free(used_labels);
 
  /* Since the controlizer is a sensitive pass, avoid leaking basic
     errors... */
  pips_assert("Statement should be OK.", statement_consistent_p(result));
 
  return result;
}

init_label()

static void init_label ( string  name, statement  st  )

static

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.

Just append st to the list of statements pointing to this label.

Definition at line 1769 of file old_controlizer.c.

{
    if(!empty_global_label_p(name)) {
        list used = (list) hash_get_default_empty_list(Label_statements, name);
        list sts = CONS(STATEMENT, st, used);
        /* Just append st to the list of statements pointing to
           this label. */
        if (hash_defined_p(Label_statements, name))
            hash_update(Label_statements, name,  sts);
        else
            hash_put(Label_statements, name,  sts);
 
        if (! hash_defined_p(Label_control, name)) {
            statement new_st = make_continue_statement(statement_label(st)) ;
            control c = make_control( new_st, NIL, NIL);
            pips_debug(8, "control %p allocated for label \"%s\"", c, name);
            hash_put(Label_control, name, c);
        }
    }
}

References CONS, empty_global_label_p(), hash_defined_p(), hash_get_default_empty_list(), hash_put(), hash_update(), Label_control, Label_statements, make_continue_statement(), make_control(), NIL, pips_debug, STATEMENT, and statement_label.

Referenced by create_statements_of_label().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_header()

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).

Parameters

sl

l

Definition at line 446 of file old_controlizer.c.

{
  loop l = statement_loop(sl);
  statement hs = statement_undefined;
 
  expression i = make_entity_expression(loop_index(l), NIL);
 
  hs = make_assign_statement(i, range_lower(loop_range(l)));
  statement_number(hs) = statement_number(sl);
 
  return hs;
}

References loop_index, loop_range, make_assign_statement(), make_entity_expression(), NIL, range_lower, statement_loop(), statement_number, and statement_undefined.

Referenced by controlize_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_inc()

statement loop_inc

(

statement

sl

)

Parameters

sl

l

Definition at line 511 of file old_controlizer.c.

{
  loop l = statement_loop(sl);
  expression I = make_entity_expression(loop_index(l), NIL);
  expression II = make_entity_expression(loop_index(l), NIL);
  call c = make_call(entity_intrinsic(PLUS_OPERATOR_NAME), // Even for C code?
                     CONS(EXPRESSION,
                          I,
                          CONS(EXPRESSION,
                               range_increment(loop_range(l)),
                               NIL)));
  expression I_plus_one =
    make_expression(make_syntax(is_syntax_call, c),
                    normalized_undefined);
  statement is = statement_undefined;
 
  is = make_assign_statement(II, I_plus_one);
  statement_number(is) = statement_number(sl);
 
  return is;
}

References CONS, entity_intrinsic(), EXPRESSION, is_syntax_call, loop_index, loop_range, make_assign_statement(), make_call(), make_entity_expression(), make_expression(), make_syntax(), NIL, normalized_undefined, PLUS_OPERATOR_NAME, range_increment, statement_loop(), statement_number, and statement_undefined.

Referenced by controlize_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_test()

statement loop_test

(

statement

sl

)

empty_comments

Parameters

sl

l

Definition at line 459 of file old_controlizer.c.

{
  loop l = statement_loop(sl);
  statement ts = statement_undefined;
  string cs = string_undefined;
  call c = make_call(entity_intrinsic(GREATER_THAN_OPERATOR_NAME),
                     CONS(EXPRESSION,
                          make_entity_expression(loop_index(l), NIL),
                          CONS(EXPRESSION,
                               range_upper(loop_range(l)),
                               NIL)));
  test t = make_test(make_expression(make_syntax(is_syntax_call, c),
                                     normalized_undefined),
                     make_plain_continue_statement(),
                     make_plain_continue_statement());
  string csl = statement_comments(sl);
  string prev_comm = empty_comments_p(csl)? /* empty_comments */ strdup("")  : strdup(csl);
  const char* lab;
 
  if(entity_empty_label_p(loop_label(l)))
    lab = ""; // FI: to be replaced by a symbolic constant
  else
    lab = label_local_name(loop_label(l));
 
  tag lt = get_prettyprint_language_tag();
  switch(lt) {
    case is_language_fortran:
    case is_language_fortran95:
      cs = strdup(concatenate(prev_comm,
                              comment_sentinel(lt),
                              "     DO loop ",
                              lab,
                              " with exit had to be desugared\n",
                              NULL));
      break;
    case is_language_c:
      cs = prev_comm;
      break;
    default:
      pips_internal_error("This language is not handled !");
      break;
  }
 
  ts = make_statement(entity_empty_label(),
                      statement_number(sl),
                      STATEMENT_ORDERING_UNDEFINED,
                      cs,
                      make_instruction(is_instruction_test, t),NIL,NULL,
                      copy_extensions (statement_extensions(sl)), make_synchronization_none());
  return ts;
}

References comment_sentinel(), concatenate(), CONS, copy_extensions(), empty_comments_p(), entity_empty_label(), entity_empty_label_p(), entity_intrinsic(), EXPRESSION, get_prettyprint_language_tag(), GREATER_THAN_OPERATOR_NAME, is_instruction_test, is_language_c, is_language_fortran, is_language_fortran95, is_syntax_call, label_local_name(), loop_index, loop_label, loop_range, make_call(), make_entity_expression(), make_expression(), make_instruction(), make_plain_continue_statement(), make_statement(), make_synchronization_none(), make_syntax(), make_test(), NIL, normalized_undefined, pips_internal_error, range_upper, statement_comments, statement_extensions, statement_loop(), statement_number, STATEMENT_ORDERING_UNDEFINED, statement_undefined, strdup(), and string_undefined.

Referenced by controlize_loop().

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

In C, we can have some "goto" inside a block from outside, that translates as any complex control graph into an "unstructured" in the PIPS jargon.

Unfortunately, that means it break the structured block nesting that may carry declarations with the scoping information.

So we need to track this scope information independently of the control graph. This is the aim of this declaration scope stack that is used to track scoping during visiting the RI. Make a control node around a statement if not already done

It is like the make_control() constructor except when the statement st has a label and is already referenced in Label_control. Thus return the control node that already owns this statement.

Parameters

[in]

st

is the statement we want a control node around

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 inside.

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

FI: the call sites do not seem to check if c==NULL...

No label, so there cannot be a control already associated to 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 173 of file controlizer.c.

                                                      {
  string label = entity_name(statement_label(st));
  control c = control_undefined;
 
  if (empty_global_label_p(label))
    /* No label, so there cannot be a control already associated to a
       label */
  c = 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... */
    c = (control) hash_get_default_empty_list(Label_control, label);
 
  pips_assert("c==0 || control_consistent_p(c)",
              c==0 || control_consistent_p(c));
 
  return c;
}

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

Referenced by controlize_forloop(), controlize_loop(), controlize_repeatloop(), controlize_sequence(), controlize_test(), controlize_whileloop(), and hcfg().

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.

Maintain the initializations where they belong. See Control/block_scope5n.

@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()/pop_declarations() before to track where to put the declarations.

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 without inserting a new statement declaration which is likely to be lost because s_above is currently represented as a list of control nodes not as a standard sequence.

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 preserve the order:

Replace initializations in declarations by assignment statements, when possible; see split_initializations(); do not worry about variable renaming yet

If old is declared in s, its declaration must be removed and replaced if necessary by an assignment with its initial value... It seems tricky at first if many variables are declared simultaneously but is does not matter if all have to be substituted. Oops for functional declarations...

FI: it would be better to use a comma expression in order to replace a statement by a unique statement

chain icl to c, assume ctls is a list over a control sequence...

The nodes in icl must be linked together

They should be added into ctls too... because the initialization expressions may require some renaming... but nctls probably takes care of that.

Replace all references to 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 1506 of file controlizer.c.

                                                                   {
  statement s = scoping_statement_head();
  list declarations = statement_declarations(s);
  statement s_above = scoping_statement_nth(2);
  list nctls = NIL; // build a new list of controls to include the
                    // initialization statements that are derived from
                    // the declaration statements
 
  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 without
         inserting a new statement declaration which is likely to be
         lost because s_above is currently represented as a list of
         control nodes not as a standard sequence. */
      v = generic_clone_variable_with_unique_name(e,
                                                  s_above,
                                                  "",
                                                  "_",
                                                  entity_to_module_entity(e),
                                                  false);
      new_variables = gen_entity_cons(v , new_variables);
      hash_put_or_update(old_to_new_variables, e, v);
      // FI: I do not understand how v can already be in
      // new_declarations since v has just been cloned!
      // if(!gen_in_list_p(v, new_declarations))
      // new_declarations = gen_entity_cons(v , new_declarations);
      // The new variable v has already been added to the declarations
      // of s_above. The code would be easuer to understand if e were
      // added to these declarations in the else clause.
    }
    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
      preserve the order: */
  new_declarations = gen_nreverse(new_declarations);
  statement_declarations(s_above) = gen_nconc(declarations_above,
                                              new_declarations);
  FOREACH(ENTITY, dv, new_variables) {
    // This does not seem to work because the above statement is being
    // controlized. Hence, the new declaration statements are simply
    // ignored... It might be better to rely on the block declaration
    // list and to fix the declarations a posteriori, maybe at the end
    // of controlize_statement(). The other option is to generate C99
    // code with declarations anywhere in the execution flow
    //add_declaration_statement(s_above, dv);
    ;
  }
 
  // Even with C99 code, the initializations should not be moved,
  // even when the initial value is numerically known. See
  // Control/block_scope5n. Unless the variable is static. See
  // Control/block_scope13.c
  if(true || get_bool_property("C89_CODE_GENERATION")) {
    /* Replace initializations in declarations by assignment
       statements, when possible; see split_initializations(); do not
       worry about variable renaming yet */
    FOREACH(CONTROL, c, ctls) {
      statement s = control_statement(c);
      nctls = gen_nconc(nctls, CONS(CONTROL, c, NIL));
      // FI: the entity must also be substituted in the
      // initializations contained by the declarations. Also old
      // declarations must be transformed into assignments.
      if(declaration_statement_p(s)) {
        int sn = statement_number(s);
        list icl = NIL;
        /* If old is declared in s, its declaration must be removed
           and replaced if necessary by an assignment with its
           initial value... It seems tricky at first if many
           variables are declared simultaneously but is does not
           matter if all have to be substituted. Oops for
           functional declarations... */
        list dvl = statement_declarations(s);
        //list il = NIL; // initialization list
        FOREACH(ENTITY, dv, dvl) {
          if(!entity_static_variable_p(dv)) {
            value iv = entity_initial(dv);
            if(!value_unknown_p(iv)) {
              expression ie = variable_initial_expression(dv);
              expression lhs= entity_to_expression(dv);
              statement is = make_assign_statement(lhs, ie);
              statement_number(is) = sn;
              control ic = make_control(is, NIL, NIL);
              /* FI: it would be better to use a comma expression in
                 order to replace a statement by a unique statement */
              nctls = gen_nconc(nctls, CONS(CONTROL, ic, NIL));
              icl = gen_nconc(icl, CONS(CONTROL, ic, NIL));
              entity n = (entity) hash_get(old_to_new_variables, (void *) dv);
              n = HASH_UNDEFINED_VALUE==n? dv : n;
              free_value(entity_initial(n));
              entity_initial(n) = make_value_unknown();
            }
          }
        }
        /* chain icl to c, assume ctls is a list over a control sequence... */
        if(!ENDP(icl)) {
          pips_assert("c has one successor (but may be zero with"
                      " dead code behind declarations:-(",
                      gen_length(control_successors(c))==1);
          control succ = CONTROL(CAR(control_successors(c)));
          control fic = CONTROL(CAR(icl));
          control cic = fic;
          control lic = CONTROL(CAR(gen_last(icl)));
          FOREACH(CONTROL, nc, CDR(icl)) {
            /* The nodes in icl must be linked together */
            link_2_control_nodes(cic, nc);
            cic = nc;
          }
          unlink_2_control_nodes(c, succ);
          link_2_control_nodes(c, fic);
          link_2_control_nodes(lic, succ);
          /* They should be added into ctls too... because the
             initialization expressions may require some
             renaming... but nctls probably takes care of that. */
          gen_free_list(icl);
        }
        statement_declarations(s) = NIL;
      }
    }
  }
  else
    nctls = gen_copy_seq(ctls);
 
  /* Replace all references to old variables to references to the new
     ones in all the corresponding control nodes by in the code */
  void * ccp = NULL; // current couple pointer
  entity old, new;
  while((ccp = hash_table_scan(old_to_new_variables, ccp, (void *) &old, (void *) &new))) {
  //HASH_MAP(old, new, {
      FOREACH(CONTROL, c, nctls) {
        statement s = control_statement(c);
        if(true || !get_bool_property("C89_CODE_GENERATION")) { // C99 assumed
          if(declaration_statement_p(s)) {
            list dl = statement_declarations(s);
            list cl;
            for(cl=dl; !ENDP(cl); POP(cl)) {
              entity dv = ENTITY(CAR(cl));
              if(dv==old)
                ENTITY_(CAR(cl)) = new;
            }
          }
        }
        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);
 
  return;
}

References CAR, CDR, CONS, CONTROL, control_statement, control_successors, declaration_statement_p(), ENDP, ENTITY, ENTITY_, entity_initial, entity_name, entity_static_variable_p(), entity_to_expression(), entity_to_module_entity(), entity_user_name(), FOREACH, free_value(), gen_copy_seq(), gen_entity_cons(), gen_free_list(), gen_last(), gen_length(), gen_nconc(), gen_nreverse(), generic_clone_variable_with_unique_name(), get_bool_property(), hash_chunk, hash_get(), hash_put_or_update, hash_table_free(), hash_table_make(), hash_table_scan(), HASH_UNDEFINED_VALUE, link_2_control_nodes(), make_assign_statement(), make_control(), make_value_unknown(), NIL, pips_assert, pips_debug, POP, replace_entity(), statement_declarations, statement_number, unlink_2_control_nodes(), value_unknown_p, and variable_initial_expression().

Referenced by controlize_sequence().

Here is the call graph for this function:

Here is the caller graph for this function:

patch_references()

static void patch_references ( int  how, control  fnode, control  tnode  )

static

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).

Move all the connection of:

• the predecessors of FNODE to point to TNODE
• or the successors of FNODE to point from TNODE

Definition at line 185 of file old_controlizer.c.

{
    MAPL(preds, {
        control pred = CONTROL(CAR(preds));
 
        MAPL(succs, {
            if(CONTROL(CAR(succs)) == fnode)
                    CONTROL_(CAR(succs)) = tnode;
        }, (how == SUCCS_OF_PREDS) ?
             control_successors(pred) :
             control_predecessors(pred));
    }, (how == SUCCS_OF_PREDS) ?
         control_predecessors(fnode) :
         control_successors(fnode));
}

References CAR, CONTROL, CONTROL_, control_predecessors, control_successors, MAPL, and SUCCS_OF_PREDS.

Referenced by controlize_list(), and controlize_list_1().

Here is the caller graph for this function:

simplified_unstructured()

static unstructured simplified_unstructured ( control  top, control  bottom, control  res  )

static

SIMPLIFIED_UNSTRUCTURED tries to get rid of top-level and useless unstructured nodes.

top is the entry node, bottom the exit node. result is ? (see assert below... Looks like it is the second node. RK)

All the comments below are from RK who is reverse engineering all that stuff... :-(

Looks like there are many memory leaks.

There are goto on the entry node:

The entry node is not a simple node sequence:

The second node has more than 1 goto on it:

Second node is not a simple node sequence:

The third node is not the exit node:

The exit node has more than 1 goto on it:

The exit node has a successor:

Here we have a sequence of 3 control node: top, res and bottom.

If the second node is an unstructured, just return it instead of top and bottom: (??? Lot of assumptions. RK)

Just keep the second node as an unstructured with only 1 control node:

Definition at line 1843 of file old_controlizer.c.

{
    list succs;
    statement st;
    unstructured u;
    instruction i;
 
    ifdebug(4) {
        pips_debug(4, "Accessible nodes from top:\n");
        display_linked_control_nodes(top);
        check_control_coherency(top);
        pips_debug(1, "Accessible nodes from bottom:\n");
        display_linked_control_nodes(bottom);
        check_control_coherency(bottom);
        pips_debug(1, "Accessible nodes from res:\n");
        display_linked_control_nodes(res);
        check_control_coherency(res);
    }
 
    ifdebug(1) {
      control_consistent_p(top);
 
      control_consistent_p(bottom);
    }
 
    u = make_unstructured(top, bottom);
 
    ifdebug(1) {
      unstructured_consistent_p(u);
    }
 
    if(!ENDP(control_predecessors(top))) {
    free_control(res);
        /* There are goto on the entry node: */
        return(u);
    }
 
    if(gen_length(succs=control_successors(top)) != 1) {
    free_control(res);
        /* The entry node is not a simple node sequence: */
        return(u);
    }
 
    pips_assert("The successor of \"top\" is \"res\"",
                CONTROL(CAR(succs)) == res);
 
    if(gen_length(control_predecessors(res)) != 1) {
    free_control(res);
        /* The second node has more than 1 goto on it: */
        return(u);
    }
 
    if(gen_length(succs=control_successors(res)) != 1) {
    free_control(res);
        /* Second node is not a simple node sequence: */
        return(u);
    }
 
    if(CONTROL(CAR(succs)) != bottom) {
        /* The third node is not the exit node: */
        return(u);
    }
 
    if(gen_length(control_predecessors(bottom)) != 1) {
    free_control(res);
        /* The exit node has more than 1 goto on it: */
        return(u);
    }
 
    if(!ENDP(control_successors(bottom))) {
    free_control(res);
        /* The exit node has a successor: */
        return(u);
    }
 
    /* Here we have a sequence of 3 control node: top, res and
       bottom. */
    gen_free_list(control_predecessors(res));
    gen_free_list(control_successors(res));
    control_predecessors(res) = control_successors(res) = NIL;
    st = control_statement(res);
 
    if(instruction_unstructured_p(i=statement_instruction(st))) {
        /* If the second node is an unstructured, just return it
           instead of top and bottom: (??? Lot of assumptions. RK) */
      ifdebug(1) {
        unstructured_consistent_p(instruction_unstructured(i));
      }
      unstructured iu = instruction_unstructured(i);
      instruction_unstructured(i)=unstructured_undefined;
      free_statement(st);
        return iu;
    }
 
    /* Just keep the second node as an unstructured with only 1
       control node: */
    unstructured_control(u) = unstructured_exit(u) = res;
    ifdebug(1) {
      unstructured_consistent_p(u);
    }
    return(u);
}

References CAR, check_control_coherency(), CONTROL, control_consistent_p(), control_predecessors, control_statement, control_successors, display_linked_control_nodes(), ENDP, free_control(), free_statement(), gen_free_list(), gen_length(), ifdebug, instruction_unstructured, instruction_unstructured_p, make_unstructured(), NIL, pips_assert, pips_debug, statement_instruction, unstructured_consistent_p(), unstructured_control, unstructured_exit, and unstructured_undefined.

Referenced by control_graph().

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 hash maps that list statements referencing labels into one.

Parameters

[in,out]	l1	is the hash map used as source and target
[in]	l2	is the other hash map

Returns

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

Definition at line 270 of file 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_loop(), controlize_repeatloop(), controlize_sequence(), 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

Mark a statement as related to a label.

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

A statement can appear many times for a given label

Parameters

used_labels[in,out]	is the hash table used to record the statements related to a label. It is not updated for empty labels.
name[in]	is the label entity name. It may be the empty label.
st[in]	is the statement to be recorded as related to the label

Do something only if there is a label:

Get a previous list of statements related to 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:

FI: This debug message happens a lot after inlining? In spite of the source parsing, line numbers are not assigned?

Definition at line 235 of file controlizer.c.

                                             {
  list sts ;
 
  /* Do something only if there is a label: */
  if (!empty_global_label_p(name)) {
    list new_sts;
    /* Get a previous list of statements related to 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);
    /* FI: This debug message happens a lot after inlining? In spite
       of the source parsing, line numbers are not assigned? */
    pips_debug(5, "Reference to statement %d seen\n",
               (int) statement_number( st )) ;
  }
}

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

Referenced by controlize_goto(), controlize_statement(), create_statements_of_label(), and union_used_labels().

Here is the call graph for this function:

Here is the caller graph for this function:

whileloop_test()

static statement whileloop_test ( statement  sl )

static

Generate a test statement ts for exiting loop sl.

There should be no sharing between sl and ts.

string prev_comm = empty_comments_p(csl)? "" : strdup(csl);

strdup("")

Definition at line 607 of file old_controlizer.c.

{
    whileloop l = instruction_whileloop(statement_instruction(sl));
    statement ts = statement_undefined;
    string cs = string_undefined;
    call c = call_undefined;
 
    switch (get_prettyprint_language_tag()) {
      case is_language_fortran:
        c = make_call(entity_intrinsic(NOT_OPERATOR_NAME),
          CONS(EXPRESSION,
         copy_expression(whileloop_condition(l)),
         NIL));
        break;
      case is_language_c:
        c = make_call(entity_intrinsic(C_NOT_OPERATOR_NAME),
          CONS(EXPRESSION,
         copy_expression(whileloop_condition(l)),
         NIL));
        break;
      case is_language_fortran95:
        pips_internal_error("Need to update F95 case");
        break;
      default:
        pips_internal_error("Language unknown !");
        break;
    }
 
    test t = make_test(make_expression(make_syntax(is_syntax_call, c),
                                     normalized_undefined),
                     make_plain_continue_statement(),
                     make_plain_continue_statement());
    string csl = statement_comments(sl);
    /* string prev_comm = empty_comments_p(csl)? "" : strdup(csl); */
    string prev_comm = empty_comments_p(csl)? empty_comments /* strdup("") */ : strdup(csl);
    const char* lab ;
 
    tag lt = get_prettyprint_language_tag();
    switch (lt) {
      case is_language_fortran:
      case is_language_fortran95:
        if(entity_empty_label_p(whileloop_label(l))) {
          cs = strdup(concatenate(prev_comm,
                                  comment_sentinel(lt),
                                  "     DO WHILE loop ",
                                  "with GO TO exit had to be desugared\n",
                                  NULL));
        } else {
          lab = label_local_name(whileloop_label(l));
          cs = strdup(concatenate(prev_comm,
                                  comment_sentinel(lt),
                                  "     DO WHILE loop ",
                                  lab,
                                  " with GO TO exit had to be desugared\n",
                                  NULL));
        }
        break;
      case is_language_c:
        cs = prev_comm;
        break;
      default:
        pips_internal_error("Language unknown !");
        break;
    }
 
 
    ts = make_statement(entity_empty_label(),
                        statement_number(sl),
                        STATEMENT_ORDERING_UNDEFINED,
                        cs,
                        make_instruction(is_instruction_test, t),NIL,NULL,
                        copy_extensions (statement_extensions(sl)), make_synchronization_none());
 
    return ts;
}

References C_NOT_OPERATOR_NAME, call_undefined, comment_sentinel(), concatenate(), CONS, copy_expression(), copy_extensions(), empty_comments, empty_comments_p(), entity_empty_label(), entity_empty_label_p(), entity_intrinsic(), EXPRESSION, get_prettyprint_language_tag(), instruction_whileloop, is_instruction_test, is_language_c, is_language_fortran, is_language_fortran95, is_syntax_call, label_local_name(), make_call(), make_expression(), make_instruction(), make_plain_continue_statement(), make_statement(), make_synchronization_none(), make_syntax(), make_test(), NIL, normalized_undefined, NOT_OPERATOR_NAME, pips_internal_error, statement_comments, statement_extensions, statement_instruction, statement_number, STATEMENT_ORDERING_UNDEFINED, statement_undefined, strdup(), string_undefined, whileloop_condition, and whileloop_label.

Referenced by controlize_whileloop().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

Label_control [1/2]

hash_table Label_control

static

This maps label names to their (possible forward) control nodes.

That is each statement with a label target is in a control that owns this statement.

Since the code is analyzed from the beginning, we may have some labels that map to control node with no statement if their target statement has not been encountered yet, in the case of forward gotos for example.

Definition at line 139 of file controlizer.c.

Referenced by create_statements_of_label(), get_label_control(), hcfg(), and make_conditional_control().

Label_control [2/2]

hash_table Label_control

static

LABEL_CONTROL maps label names to their (possible forward) control nodes.

Definition at line 119 of file old_controlizer.c.

Referenced by control_graph(), get_label_control(), init_label(), and make_conditional_control().

Label_statements [1/2]

hash_table Label_statements

static

This maps label names to the list of statements where they appear (either as definition or reference).

This is a global table to all the module.

There are some other local tables used elsewhere in the code to have a more hierarchical owning information

Definition at line 126 of file controlizer.c.

Referenced by controlize_goto(), covers_labels_p(), create_statements_of_label(), and hcfg().

Label_statements [2/2]

hash_table Label_statements

static

LABEL_STATEMENTS maps label names to the list of statements where they appear (either as definition or reference).

Definition at line 114 of file old_controlizer.c.

Referenced by control_graph(), covers_labels_p(), and init_label().

Unreachable

list Unreachable

static

UNREACHABLE is the hook used as a predecessor of statements that are following a goto.

The list of unreachable statements is kept in the successors list.

Definition at line 109 of file old_controlizer.c.

Referenced by control_graph(), and controlize_list_1().