PIPS
|
lint More...
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... | |
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 .Ker yell@ hpc- proje ct.c 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
#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.
#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.
#define LABEL_TABLES_SIZE 10 |
Definition at line 115 of file controlizer.c.
#define LABEL_TABLES_SIZE 10 |
Definition at line 101 of file old_controlizer.c.
#define PREDS_OF_SUCCS 1 |
Definition at line 171 of file old_controlizer.c.
#define SUCCS_OF_PREDS 2 |
Definition at line 172 of file old_controlizer.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.
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.
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.
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().
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).
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.
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().
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...
st | t |
Definition at line 2190 of file old_controlizer.c.
|
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.
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.
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().
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.
[in] | c_res | is the control node with a call statement to controlize |
[in] | succ | is the control node successor of c_res |
Definition at line 2455 of file controlizer.c.
References control_statement, and pips_debug.
Referenced by controlize_statement().
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.
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().
|
static |
Computes the control graph of a C for loop statement.
[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 |
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.
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().
|
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.
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().
|
static |
Deal with "goto" when building the HCFG.
[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.
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().
|
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.
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.
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().
|
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:
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.
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().
|
static |
Computes the control graph of a Fortran do-loop statement.
[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 |
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.
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().
|
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.
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().
|
static |
Computes the control graph of a C repeat until loop statement.
[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 |
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.
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().
|
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.
[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 |
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:
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.
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().
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).
[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. |
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()):
c_res | _res |
succ | ucc |
used_labels | sed_labels |
Definition at line 2493 of file controlizer.c.
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().
|
static |
Builds the control node of a test statement.
[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 |
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.
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().
|
static |
Builds the control node of a statement st
in c_res
which is a test statement t
.
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.
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().
|
static |
Computes the control graph of a Fortran or C while loop statement.
[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 |
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.
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().
|
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.
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().
|
static |
Compute whether all the label references in a statement are in a given label name to statement list local mapping.
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 |
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.
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().
|
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.
[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.
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().
|
static |
Definition at line 1822 of file old_controlizer.c.
References create_statements_of_label(), gen_recurse, gen_true(), and statement_domain.
Referenced by control_graph().
|
static |
Initialize the global Label_statements mapping for the module that associates for any label in the module the statements that refer to it.
[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.
References create_statements_of_label(), gen_recurse, gen_true(), and statement_domain.
Referenced by hcfg().
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.
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. |
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
ctls | tls |
succ | ucc |
Definition at line 1739 of file controlizer.c.
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().
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
ctls | tls |
succ | ucc |
Definition at line 1809 of file controlizer.c.
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.
sl | l |
Definition at line 765 of file old_controlizer.c.
References forloop_initialization, instruction_forloop, instruction_to_statement(), make_instruction_expression(), statement_instruction, and statement_number.
Referenced by controlize_forloop().
pips_debug(8, "Increment expression: ");
print_expression(inc);
}
sl | l |
Definition at line 806 of file old_controlizer.c.
References forloop_increment, instruction_forloop, instruction_to_statement(), make_instruction_expression(), statement_instruction, and statement_number.
Referenced by controlize_forloop().
strdup("")
pips_debug(8, "Condition expression: ");
print_expression(cond);
}
sl | l |
Definition at line 775 of file old_controlizer.c.
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().
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.
[in] | name | is the string name of the label entity |
The label must exist in the table.
Definition at line 207 of file controlizer.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().
Compute the hierarchical control flow graph (HCFG) of a statement.
st | is the statement we want to "controlize" |
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...
st | t |
Definition at line 2621 of file controlizer.c.
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.
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().
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).
sl | l |
Definition at line 446 of file old_controlizer.c.
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().
sl | l |
Definition at line 511 of file old_controlizer.c.
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().
empty_comments
sl | l |
Definition at line 459 of file old_controlizer.c.
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().
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.
[in] | st | is the statement we want a control node around |
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.
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().
|
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.
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().
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:
Definition at line 185 of file old_controlizer.c.
References CAR, CONTROL, CONTROL_, control_predecessors, control_successors, MAPL, and SUCCS_OF_PREDS.
Referenced by controlize_list(), and controlize_list_1().
|
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.
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().
|
static |
Unions 2 hash maps that list statements referencing labels into one.
[in,out] | l1 | is the hash map used as source and target |
[in] | l2 | is the other hash map |
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.
References FOREACH, HASH_MAP, STATEMENT, and update_used_labels().
Referenced by controlize_forloop(), controlize_loop(), controlize_repeatloop(), controlize_sequence(), controlize_test(), and controlize_whileloop().
|
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
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.
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().
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.
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().
|
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().
|
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().
|
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().
|
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().
|
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().