PIPS
|
unstructured More...
Functions | |
bool | is_control_in_list_p (control c, list cs) |
Test if a control node is in a list of control nodes. More... | |
int | occurences_in_control_list (control c, list cs) |
Count the number of occurences of a control node in a list of control nodes. More... | |
void | control_list_patch (list l, control c_old, control c_new) |
Replace in a list of control nodes all the instance of a control node by another one. More... | |
void | transfer_control_predecessor (control old_node, control new_node, control c) |
Transfer a control node as a predecessor from one node to another one. More... | |
void | transfer_control_successor (control old_node, control new_node, control c) |
Transfer a control node as a successor of one node to another one. More... | |
void | replace_control_related_to_a_list (control old_node, control new_node, list controls) |
Replace all the references to a control node by a new one in the successors & predecessors of a list of controls. More... | |
void | check_control_coherency (control c) |
Test the coherency of a control node network from a control node. More... | |
void | print_control_node (control c) |
void | print_control_nodes (list l) |
Display identification of a list of control nodes. More... | |
void | display_address_of_control_nodes (list cs) |
Display the adresses a list of control nodes. More... | |
void | display_linked_control_nodes (control c) |
Display all the control nodes reached or reachable from c for debugging purpose. More... | |
void | remove_unreachable_following_control (control c, control do_not_delete_node, control do_not_delete_node_either) |
Remove all the control nodes (with their statements) from c in the successor tree of c up to the nodes with more than 1 predecessor, that is when it reach another flow. More... | |
void | remove_some_unreachable_controls_of_an_unstructured (unstructured u) |
Remove all the control sequences that are unreachable and that begin with a node without any predecessor. More... | |
void | remove_all_unreachable_controls_of_an_unstructured (unstructured u) |
Remove all control nodes that are not forward reachable from the entry node. More... | |
void | remove_a_control_from_a_list_and_relink (control c, list a_source_control_list_of_c, list a_dest_control_list_of_c, remove_a_control_from_a_list_and_relink_direction which_way) |
Replace each occurence of c in a_source_control_list_of_c with a a_dest_control_list_of_c: More... | |
void | remove_a_control_from_an_unstructured (control c) |
Remove a control node from a control graph. More... | |
void | remove_a_control_from_an_unstructured_without_relinking (control c) |
It removes a control node from its successor and predecessor. More... | |
void | discard_an_unstructured_without_its_statements (unstructured u) |
Used to discard an unstructured without touching its statements. More... | |
void | free_a_control_without_its_statement (control c) |
Remove a control node without touching its statement, its predecessors and successors, if any. More... | |
void | discard_a_control_sequence_without_its_statements (control begin, control end) |
Remove a control sequence without touching its statements. More... | |
list | generate_a_statement_list_from_a_control_sequence (control begin, control end) |
Take a control sequence and return a list of all the statements in the sequence (in the same order... More... | |
void | link_2_control_nodes (control source, control target) |
Add an edge between 2 control nodes. More... | |
void | link_3_control_nodes (control c_test, control c_then, control c_else) |
Add an edge between 2 control nodes. More... | |
void | unlink_2_control_nodes (control source, control target) |
Remove all edged between 2 control nodes. More... | |
void | insert_control_in_arc (control c, control before, control after) |
Insert a control node between 2 connected control nodes. More... | |
void | fuse_2_control_nodes (control first, control second) |
Fuse a 2 control nodes. More... | |
unstructured
void check_control_coherency | ( | control | c | ) |
Test the coherency of a control node network from a control node.
Do not verify the fact that nodes could appear twice in the case of unstructured tests.
c | is the control node we want to start the verification from |
Test the coherency of the successors
if (!is_control_in_list_p(ctl, control_predecessors(cc))) {
Test the coherency of the predecessors
if (!is_control_in_list_p(ctl, control_successors(cc))) {
Check that the statement are consistent
Check that two nodes do not point towards the same statement as this makes label resolution ambiguous
Definition at line 487 of file control.c.
References CONTROL, control_consistent_p(), CONTROL_MAP, control_predecessors, control_statement, control_successors, fprintf(), gen_free_list(), ifdebug, MAP, NIL, occurences_in_control_list(), pips_assert, pips_debug, set_add_element(), set_belong_p(), set_free(), set_make(), set_pointer, statement_consistent_p(), and statement_test_p().
Referenced by control_graph(), controlize(), controlize_forloop(), controlize_goto(), controlize_list(), controlize_list_1(), controlize_sequence(), controlize_statement(), controlize_test(), controlize_whileloop(), find_exit_control_node(), find_or_create_exit_control_node(), get_label_control(), hierarchize_control_list(), and simplified_unstructured().
Replace in a list of control nodes all the instance of a control node by another one.
l | is the list of control nodes |
c_old | is the control node to remove |
c_new | is the control node to put instead |
c_old | _old |
c_new | _new |
Definition at line 336 of file control.c.
References gen_list_patch().
Referenced by hierarchize_control_list(), transfer_control_predecessor(), and transfer_control_successor().
Remove a control sequence without touching its statements.
It also removes the reference to the sequence from the predecessors or the successors.
begin | is the control node we start from |
end | is the control node to stop at |
Of course, there should be a unique path from begin
to end
.
Unlink any extern reference to the control sequence:
To pass through the free:
begin | egin |
end | nd |
Definition at line 1111 of file control.c.
References CAR, CONTROL, control_predecessors, control_successors, end, free_a_control_without_its_statement(), gen_length(), gen_remove(), MAP, and pips_assert.
Referenced by __attribute__(), restructure_this_test(), and take_out_the_entry_node_of_the_unstructured().
void discard_an_unstructured_without_its_statements | ( | unstructured | u | ) |
Used to discard an unstructured without touching its statements.
The statements are assumed to be referenced in another way.
he | unstructured to free |
Protect the statements by unlinking them:
And then free the discard the unstructured:
Definition at line 1063 of file control.c.
References CONTROL_MAP, control_statement, free_unstructured(), gen_free_list(), NIL, statement_undefined, and unstructured_control.
Referenced by __attribute__().
void display_address_of_control_nodes | ( | list | cs | ) |
Display the adresses a list of control nodes.
cs | is the control node list |
cs | s |
Definition at line 612 of file control.c.
References CONTROL, fprintf(), and MAP.
Referenced by compact_list(), display_interval_graph(), display_linked_control_nodes(), hierarchize_control_list(), and interval_exit_nodes().
void display_linked_control_nodes | ( | control | c | ) |
Display all the control nodes reached or reachable from c for debugging purpose.
Display also the statement of each control node if the debug level is high enough
c | is the control node we start the visit from |
safe_print_statement(control_statement(ctl));
Definition at line 629 of file control.c.
References CONTROL_MAP, control_predecessors, control_statement, control_successors, display_address_of_control_nodes(), fprintf(), gen_free_list(), gen_length(), ifdebug, NIL, pips_debug, set_add_element(), set_belong_p(), set_free(), set_make(), and set_pointer.
Referenced by clean_up_control(), control_graph(), control_graph_recursive_decomposition(), controlize(), controlize_goto(), controlize_list(), controlize_list_1(), controlize_sequence(), controlize_statement(), controlize_test(), hierarchize_control_list(), recover_structured_while(), remove_all_unreachable_controls_of_an_unstructured(), remove_some_unreachable_controls_of_an_unstructured(), remove_unreachable_following_control(), simplified_unstructured(), unstructured_consistency_p(), and unstructured_while_p().
void free_a_control_without_its_statement | ( | control | c | ) |
Remove a control node without touching its statement, its predecessors and successors, if any.
c | is the control node to free |
Protect the statement:
Definition at line 1087 of file control.c.
References control_predecessors, control_statement, control_successors, free_control(), gen_free_list(), NIL, and statement_undefined.
Referenced by controlize_test(), discard_a_control_sequence_without_its_statements(), and hcfg().
Fuse a 2 control nodes.
It adds the statement of the second one to the statement of the first one. Assumes that the second node is the only successor of the first one.
The second control node is freed.
It does not update the entry or exit field of the unstructured.
first | is the first control node |
second | is the control node to fuse in the first one. It is precised because it is possible that there are not connected. |
If the second node has 2 successors, it is a test node. The fused node has 2 successors and must be a test too. So, the only thing I can do is to remove the first statement, just keeping its comments. And how about the label? It might be useful for syntactic reasons and only reachable via END=nnn after prettyprinting (see Validation/redlec2.f)
A return might be OK?!? What does the caller expect? The first label must be useless and is dropped.
pips_user_warning("Useless label %s\n", entity_name(first_label));
pips_internal_error("Two labels for one control node");
If not, build a block with the two statements:
Reconnect the new statement to the node to fuse:
Unlink the second node from the first one:
Link the first node with the successors of the second one in the forward direction:
Update all the predecessors of the successors:
Transfer the predecessors of the second node to the first one. Note that the original second -> first predecessor link has already been removed. But a loop from second to second appear at this point as a link from first to second. Nasty bug...
Now we remove the useless intermediate node "second":
Do not gen_free_list(control_successors(second)) since it is used as control_successors(first) now:
first | irst |
second | econd |
Definition at line 1391 of file control.c.
References CAR, CONS, CONTROL, CONTROL_, control_predecessors, control_statement, control_successors, cp, entity_empty_label_p(), entity_name, free_control(), gather_all_comments_of_a_statement(), gen_free_list(), gen_length(), gen_remove(), insert_comments_to_statement(), make_empty_statement, make_instruction_block(), MAP, MAPL, NIL, pips_user_warning, STATEMENT, statement_instruction, statement_label, statement_to_label(), and statement_undefined.
Referenced by fuse_sequences_in_unstructured().
Take a control sequence and return a list of all the statements in the sequence (in the same order...
:-) ).
begin | is the control node we start from |
end | is the control node to stop at |
Of course, there should be a unique path from begin
to end
.
Because of the way CONS is working, reversed the walk through the sequence.
Add the statement to the list:
begin | egin |
end | nd |
Definition at line 1156 of file control.c.
References CAR, CONS, CONTROL, control_predecessors, control_statement, end, gen_length(), NIL, pips_assert, and STATEMENT.
Referenced by __attribute__().
Insert a control node between 2 connected control nodes.
c | is the control node to insert |
before | is the control node before where c is to be inserted |
after | is the control node after where c is to be inserted |
Assume that c
is not already connected and that after
is the successor of before
.
Note: statements associated to nodes are not tested in case they are undefined.
If there is no ambiguity about the linking, use Ronan's technique
Let's try to preserve the true and false branch
before | efore |
after | fter |
Definition at line 1299 of file control.c.
References CAR, CONS, CONTROL, control_predecessors, control_successors, gen_length(), gen_nconc(), gen_remove(), gen_replace_in_list(), is_control_in_list_p(), link_2_control_nodes(), NIL, pips_assert, pips_debug, pips_internal_error, and unlink_2_control_nodes().
Referenced by controlize_forloop(), controlize_loop(), and find_exit_control_node().
Test if a control node is in a list of control nodes.
FI: is this different from gen_in_list_p(), but for the c type and the qualifiers?
c | control node to look for |
cs | is the list of control to search through |
cs | s |
Definition at line 299 of file control.c.
Referenced by insert_control_in_arc(), and wide_forward_control_map_get_blocs().
Add an edge between 2 control nodes.
Assume that this edge does not already exist or the source should be an unstructured IF. FI: I am still puzzled how this can work when tests are involved since the semantics of the first and second successor is not paid attention at at all.
source | is the control node the edge starts from |
target | is the control node the edge ends to |
source | ource |
target | arget |
Definition at line 1193 of file control.c.
References CONS, CONTROL, control_predecessors, control_successors, ENDP, gen_free_list(), and NIL.
Referenced by connect_unstructured(), controlize(), controlize_forloop(), controlize_goto(), controlize_list(), controlize_loop(), controlize_repeatloop(), controlize_sequence(), controlize_test(), controlize_whileloop(), full_spaghettify_module(), full_spaghettify_statement(), hcfg(), hierarchize_control_list(), insert_control_in_arc(), make_unstructured_from_forloop(), make_unstructured_from_loop(), make_unstructured_from_test(), move_declaration_control_node_declarations_to_statement(), recover_structured_while(), reduce_sequence(), replace_control_with_unstructured(), and restructure_this_test().
Add an edge between 2 control nodes.
Assume that this edge does not already exist or the source should be an unstructured IF. FI: I am still puzzled how this can work when tests are involved since the semantics of the first and second successor is not paid attention at at all.
source | is the control node the edge starts from |
target | is the control node the edge ends to |
c_test | _test |
c_then | _then |
c_else | _else |
Definition at line 1249 of file control.c.
References c_test(), CONS, CONTROL, control_predecessors, control_successors, ENDP, gen_free_list(), and NIL.
Referenced by controlize_repeatloop(), controlize_test(), controlize_whileloop(), make_unstructured_from_test(), and make_unstructured_from_whileloop().
Count the number of occurences of a control node in a list of control nodes.
c | control node to look for |
cs | is the list of control to count through |
cs | s |
Definition at line 319 of file control.c.
References gen_occurences().
Referenced by check_control_coherency().
void print_control_node | ( | control | c | ) |
Definition at line 566 of file control.c.
References CONTROL, control_predecessors, control_statement, control_successors, fprintf(), gen_length(), MAP, and safe_statement_identification().
void print_control_nodes | ( | list | l | ) |
Display identification of a list of control nodes.
Definition at line 589 of file control.c.
References CONTROL, control_statement, ENDP, fprintf(), MAP, and safe_statement_identification().
Referenced by ancestor_map_consistent_p(), bourdoncle_component(), bourdoncle_partition(), controlize_sequence(), node_to_linked_nodes(), scc_to_dag(), and update_partition().
void remove_a_control_from_a_list_and_relink | ( | control | c, |
list | a_source_control_list_of_c, | ||
list | a_dest_control_list_of_c, | ||
remove_a_control_from_a_list_and_relink_direction | which_way | ||
) |
Replace each occurence of c in a_source_control_list_of_c with a a_dest_control_list_of_c:
c | is the control node to unlink. It is not freed |
a_source_control_list_of_c | is the list of control nodes to be linked to the a_dest_control_list_of_c list of control nodes |
a_dest_control_list_of_c | is the list of control nodes to be linked from the a_source_control_list_of_c list of control nodes |
which_way | precise if we deal with successors or predecessors: |
a_source_control_list_of_c
is considered as predecessors of c
and a_dest_control_list_of_c
is considered as successors of c
-if it is source_is_successor_and_dest_is_predecessor: a_source_control_list_of_c
is considered as successors of c
and a_dest_control_list_of_c
is considered as predecessors of c
Now, find the corresponding dest in the source list with the same value as c:
Find the reference to c in the the_dest_of_a_source_list:
l is local to the MAPL...
And add the a_dest_control_list_of_c instead of c:
First concatenate (with copy) a_dest_control_list_of_c before what follow c in the list:
Then place this list instead of c in the_dest_of_a_source_list:
Modify the begin of the list:
Deallocate the cons that point to c:
c is now in the memory nowhere:
a_source_control_list_of_c | _source_control_list_of_c |
a_dest_control_list_of_c | _dest_control_list_of_c |
which_way | hich_way |
Definition at line 913 of file control.c.
References CAR, CDR, CONTROL, control_predecessors, control_successors, gen_append(), gen_free_list(), MAPL, NIL, pips_assert, source_is_predecessor_and_dest_is_successor, and source_is_successor_and_dest_is_predecessor.
Referenced by remove_a_control_from_an_unstructured().
void remove_a_control_from_an_unstructured | ( | control | c | ) |
Remove a control node from a control graph.
The control node is freed and its predecessors are relinked to its successor and relink the successor and the predecessor.
If you want to preserve the control statement, do a control_statement(c) = statement_undefined before calling this function.
[in,out] | c | is the control node to unlink and to free |
Assume that it cannot have more than 1 successor (so no test node)
If the graph is in an unstructured and c
is either the entry or exit node, do not forget to update the entry or exit node.
Unlink from the predecessor. Note that a node may have more than one predecessor. Since we cannot discard an IF this way, we have at most 1 successor:
Unlink from the successor:
Remove the control node:
Definition at line 992 of file control.c.
References control_predecessors, control_successors, free_control(), gen_length(), pips_assert, remove_a_control_from_a_list_and_relink(), source_is_predecessor_and_dest_is_successor, and source_is_successor_and_dest_is_predecessor.
Referenced by compact_list(), controlize_forloop(), controlize_loop(), controlize_repeatloop(), controlize_sequence(), controlize_whileloop(), and remove_useless_continue_or_empty_code_in_unstructured().
void remove_a_control_from_an_unstructured_without_relinking | ( | control | c | ) |
It removes a control node from its successor and predecessor.
It can be applied to an unstructured "IF".
c | is the control node to unlink and to free |
If the graph is in an unstructured and
c | is either the entry or exit node, do not forget to update the entry or exit node. |
Use a copy since we iterate and discard at the same time:
Remove the control node itself:
Definition at line 1031 of file control.c.
References CONTROL, control_predecessors, control_successors, free_control(), gen_copy_seq(), gen_free_list(), MAP, NIL, pips_assert, and unlink_2_control_nodes().
Referenced by controlize_sequence(), controlize_test(), recover_structured_while(), and remove_all_unreachable_controls_of_an_unstructured().
void remove_all_unreachable_controls_of_an_unstructured | ( | unstructured | u | ) |
Remove all control nodes that are not forward reachable from the entry node.
Warning: useful FORMAT that are unreachable are also discarded, so...
u | is the unstructured to clean |
The entry point of the unstructured:
Mark all the forward-reachable nodes:
Now build the remove list from all the non-marked nodes:
The same thing from the exit node that may be not reachable from the entry node:
And delete them:
Definition at line 812 of file control.c.
References CONTROL_MAP, control_statement, display_linked_control_nodes(), format_inside_statement_p(), FORWARD_CONTROL_MAP, gen_free_list(), ifdebug, NIL, pips_debug, pips_user_warning, remove_a_control_from_an_unstructured_without_relinking(), set_add_element(), set_belong_p(), set_free(), set_make(), SET_MAP, set_pointer, unstructured_control, and unstructured_exit.
Referenced by clean_up_control().
void remove_some_unreachable_controls_of_an_unstructured | ( | unstructured | u | ) |
Remove all the control sequences that are unreachable and that begin with a node without any predecessor.
It is an old version and a normal user should use remove_all_unreachable_controls_of_an_unstructured() instead.
It is still buggy on Validation/Syntax/asgoto.f...
The entry point of the unstructured:
Well, the entry node is guessed as reachable... :-)
A control without predecessor is unreachable, so it is dead code:
Note that we could have entry_node == exit_node...
Now remove all the marqued sequences from the entry_node:
Do not forget the unreachable exit part if it is not connex to the entry_node:
Do not remove the exit_node...
A control without predecessor is unreachable, so it is dead code:
Now remove all the marqued sequences from the entry_node:
Definition at line 730 of file control.c.
References CONS, CONTROL, CONTROL_MAP, control_predecessors, display_linked_control_nodes(), gen_free_list(), ifdebug, MAP, NIL, pips_debug, remove_unreachable_following_control(), unstructured_control, and unstructured_exit.
void remove_unreachable_following_control | ( | control | c, |
control | do_not_delete_node, | ||
control | do_not_delete_node_either | ||
) |
Remove all the control nodes (with their statements) from c
in the successor tree of c
up to the nodes with more than 1 predecessor, that is when it reach another flow.
The entry node of the unstructured is given to avoid removing it when there is an unreachable sequence pointing on it.
If a control node contains a FORMAT, assume that it is useful and stop removing.
The
do_not_delete_node | is expected to be the entry or the exit node for example in order not to delete them. |
c | is the control we start the deletion from. |
do_not_delete_node | is a control node we stop at when encountered |
do_not_delete_node_either | is another control node we stop at when encountered |
If this is the do_not_delete_node nodes: stop deleting:
If this is not or no more the begin of a sequence, stop deleting:
If there is a FORMAT inside a control node, just stop deleting the control nodes since we cannot decide locally if the FORMAT is useful or not:
Save the successor list since we iterate o it and discard it at the same time:
Ok, we can delete. For each successor of c:
Remove any predecessor reference of itself in this successor:
Discard the control node itself:
do_not_delete_node | o_not_delete_node |
do_not_delete_node_either | o_not_delete_node_either |
Definition at line 682 of file control.c.
References CONTROL, control_predecessors, control_statement, control_successors, display_linked_control_nodes(), format_inside_statement_p(), free_control(), gen_copy_seq(), gen_free_list(), ifdebug, MAP, NIL, pips_debug, and unlink_2_control_nodes().
Referenced by remove_some_unreachable_controls_of_an_unstructured().
Replace all the references to a control node by a new one in the successors & predecessors of a list of controls.
old_node | is the control node to replace |
new_node | is the control node to replace |
controls | is a list of controls we want to disconnect from old_node and reconnect to new_node instead |
Need a intermediate list since we cannot iterate on control_successors(old_node) for example and modifying it...
Since we need to keep successors order (to avoid for example IF/THEN/ELSE transformed in IF/ELSE/THEN), iterate directly on the links of old_node instead of on controls:
First transfer the successors in controls from old_node to new_node:
Use gen_nconc to keep test order:
And then do the modification:
Hmmm... We need to transfer a loop around old_node to a loop around new_node:
Create the new loop around new_node:
Delete the old one. Use gen_remove_once() instead of gen_remove() to deal with double loops around a node (See hierarchy02.f in validation):
And then transfer the predecessors in controls from old_node to new_node (the previous double loops have disappeared here):
Use gen_nconc to keep test order:
And then do the modification:
old_node | ld_node |
new_node | ew_node |
controls | ontrols |
Definition at line 419 of file control.c.
References CONS, CONTROL, control_predecessors, control_successors, gen_free_list(), gen_in_list_p(), gen_nconc(), gen_remove_once(), MAP, NIL, pips_debug, transfer_control_predecessor(), and transfer_control_successor().
Transfer a control node as a predecessor from one node to another one.
It disconnected a node c
that was pointing to (was a predecessor of) old_node
and reconnect it to new_node
that becomes its new successor instead.
old_node | the control node that was a successor of c |
new_node | the control node that will be a successor of c |
c | the control node that is disconnected of old_node and connected to new_node |
Add c as a predecessor of new_node:
Remove c as a predecessor of old_node:
Correct the reverse link c->old_node to c->new_node:
old_node | ld_node |
new_node | ew_node |
Definition at line 358 of file control.c.
References CONS, CONTROL, control_list_patch(), control_predecessors, control_successors, gen_nconc(), gen_remove(), MAP, and NIL.
Referenced by replace_control_related_to_a_list().
Transfer a control node as a successor of one node to another one.
It disconnected a node c
that was coming from (was a successor of) old_node
and reconnect it to new_node
that becomes its new predecessor instead.
old_node | the control node that was a predecessor of c |
new_node | the control node that will be a predecessor of c |
c | the control node that is disconnected of old_node and connected to new_node |
Add c as a predecessor of new_node:
Remove c as a successor of old_node:
Correct the reverse link c->old_node to c->new_node:
old_node | ld_node |
new_node | ew_node |
Definition at line 390 of file control.c.
References CONS, CONTROL, control_list_patch(), control_predecessors, control_successors, gen_nconc(), gen_remove(), MAP, and NIL.
Referenced by replace_control_related_to_a_list().
Remove all edged between 2 control nodes.
Note: if the source is a test, the false branch may be come the true branch if the true branch is unlinked
source | is the control node the edges start from |
target | is the control node the edges end to |
source | ource |
target | arget |
Definition at line 1276 of file control.c.
References control_predecessors, control_successors, and gen_remove().
Referenced by connect_unstructured(), controlize(), controlize_forloop(), controlize_goto(), controlize_list(), controlize_loop(), controlize_repeatloop(), controlize_sequence(), controlize_test(), controlize_whileloop(), full_spaghettify_statement(), hierarchize_control_list(), insert_control_in_arc(), move_declaration_control_node_declarations_to_statement(), recover_structured_while(), reduce_sequence(), remove_a_control_from_an_unstructured_without_relinking(), remove_unreachable_following_control(), replace_control_with_unstructured(), and restructure_this_test().