PIPS
|
#include <stdio.h>
#include <strings.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "ri-util.h"
#include "control.h"
#include "properties.h"
#include "pipsdbm.h"
#include "misc.h"
Go to the source code of this file.
Functions | |
static void | reset_dfn (control c) |
static void | copy_dfn (control new_c, control old_c) |
static _int | get_dfn (control c) |
static void | update_dfn (control c, _int d) |
static control | make_meaningless_control (list preds, list succs) |
With non-deterministic graph, the outcome of a test may be known in advance. More... | |
bool | meaningless_control_p (control c) |
Is exported to exploit non-deterministic control flow graphs. More... | |
static void | free_meaningless_control (control c) |
bool | control_test_p (control c) |
Check that a node is used as a test in a CFG. More... | |
static void | print_control_node_without_check (control) |
Code partly replicated from semantics/unstructured.c to be able to taylor it to the exact needs. More... | |
static bool | check_control_statement (control c) |
static void | print_and_check_control_node (control c, bool check_p) |
static void | print_control_node_b (control c) |
static void | print_control_nodes_without_check (list l) |
Was moved into ri-util/control, minus the check_control_statement() More... | |
static void | print_unstructured (unstructured u) |
static void | davinci_print_control_node (control c, FILE *f, bool entry_p, bool exit_p, bool fix_point_p) |
Output CFG in daVinci format. More... | |
static int | control_cons_compare (list l1, list l2) |
static void | set_davinci_count () |
static void | davinci_print_control_nodes (list l, string msg) |
static void | davinci_print_non_deterministic_unstructured (unstructured u, string msg, hash_table scc_map, hash_table ancestor_map) |
void | add_control_to_embedding_control_list (control c) |
static void | print_embedding_graph (control c, string msg) |
static list | node_to_linked_nodes (control c) |
Allocate a list of control nodes transitively linked to control c. More... | |
static int | clean_up_control_test (control c) |
Take care of two problems: meaningless control nodes may end up shared by effective nodes and they may end up uselessly numerous. More... | |
static void | clean_up_embedding_graph (control c) |
static void | print_control_to_control_mapping (string message, hash_table map) |
static bool | ancestor_control_p (hash_table ancestor_map, control c) |
Functions to deal with the ancestor_map. More... | |
control | control_to_ancestor (control vertex, hash_table ancestor_map) |
If vertex is an ancestor control node from the input control graph, return vertex, else return its ancestor. More... | |
static bool | registered_controls_p (hash_table ancestor_map, list l) |
static bool | ancestor_map_consistent_p (hash_table ancestor_map) |
No control can be an ancestor and a child. More... | |
static void | add_child_parent_pair (hash_table ancestor_map, control child, control parent) |
static void | print_replicate_map () |
control | control_shallow_copy (control c) |
static void | control_translate_arcs (control c) |
static control | control_to_replicate (control old_c) |
unstructured | unstructured_shallow_copy (unstructured u, hash_table ancestor_map) |
unstructured | partition_to_unstructured (control vertex, list partition) |
Build a new unstructured (CFG) for partition. More... | |
static bool | entry_or_exit_control_p (control c, list partition, bool check_entry) |
static bool | entry_control_p (control c, list partition) |
static bool | exit_control_p (control c, list partition) |
void | intersect_successors_with_partition_or_complement (control c, list partition, bool complement_p) |
If complement_p, preserve successors in the complement of partition. More... | |
void | intersect_successors_with_partition (control c, list partition) |
void | intersect_successors_with_partition_complement (control c, list partition) |
static void | __attribute__ ((unused)) |
static void | update_successors_of_predecessor (control pred, control new_c, control old_c) |
new_c is not consistent on entry and might not be on exit because it is called from within a loop More... | |
static void | update_predecessors_of_successor (control succ, control new_c, control old_c) |
static void | add_test_successor (control t, control new_s, bool is_true_successor) |
Called from within a loop where neither t nor new_s are consistent. More... | |
static void | update_successor_in_copy (control new_pred, control pred, control c, control new_c) |
Make new_c a successor of new_pred, the same way c is a successor of pred. More... | |
static unstructured | scc_to_dag (control root, list partition, hash_table ancestor_map) |
The nodes in scc partition but root must be removed. More... | |
static void | replicate_cycles (unstructured u_main, hash_table scc_map, hash_table ancestor_map) |
list | bourdoncle_partition (unstructured u, unstructured *p_ndu, hash_table *p_ancestor_map, hash_table *p_scc_map) |
static bool | partition_successor_p (control b, control e, list partition) |
FUNCTIONS FOR BOURDONCLE_COMPONENT() More... | |
static void | update_partition (control root, list partition, hash_table ancestor_map) |
list | bourdoncle_component (control vertex, hash_table ancestor_map, hash_table scc_map) |
int | bourdoncle_visit (control vertex, list *ppartition, hash_table ancestor_map, hash_table scc_map) |
unstructured | ancestor_cycle_head_to_scc (control a, hash_table scc_map) |
scc_map maps either the ancestor node to its scc if the transformers are computed without context, or the call site node to its scc if cycles are replicated to compute transformers within their context. More... | |
unstructured | proper_cycle_head_to_scc (control h, hash_table scc_map) |
Retrieve a scc_u from its head. More... | |
bool | cycle_head_p (control c, hash_table ancestor_map, hash_table scc_map) |
This node is a cycle call site. More... | |
bool | proper_cycle_head_p (control c, hash_table scc_map) |
This node is really the head of a cycle (red on daVinci pictures). More... | |
bool | direct_cycle_head_p (control c, hash_table scc_map) |
This node is directly associated to a specific cycle. More... | |
unstructured | cycle_head_to_scc (control c, hash_table ancestor_map, hash_table scc_map) |
The ancestor of this node is associated to a specific cycle. More... | |
bool | one_successor_kind_only_p (control c, bool true_p) |
useful for non-deterministic control flow graph only More... | |
bool | true_successors_only_p (control c) |
bool | false_successors_only_p (control c) |
static void | suppress_statement_reference (control c) |
static void | bourdoncle_unstructured_free (unstructured u) |
void | bourdoncle_free (unstructured ndu, hash_table ancestor_map, hash_table scc_map) |
Variables | |
static hash_table | dfn = hash_table_undefined |
bourdoncle.c More... | |
static int | num = 0 |
static int | davinci_count = 0 |
This counter is pre-incremented each time a new graph is stored to generate a new file name. More... | |
static list | embedding_control_list = NIL |
static hash_table | replicate_map = hash_table_undefined |
Replication of unstructured (i.e. More... | |
|
static |
Can we do without a extra-node?
Definition at line 1236 of file bourdoncle.c.
References CAR, CONS, CONTROL, CONTROL_, control_predecessors, entity_empty_label(), gen_list_patch(), make_continue_statement(), make_control(), NIL, pips_assert, and pips_debug.
|
static |
The child will inherit the parent's ancestor, if any
The child should not already be in ancestor_map
The child cannot be an ancestor
Definition at line 934 of file bourdoncle.c.
References ancestor_control_p(), control_undefined, hash_get(), hash_put(), HASH_UNDEFINED_VALUE, ifdebug, and pips_assert.
Referenced by scc_to_dag(), and unstructured_shallow_copy().
void add_control_to_embedding_control_list | ( | control | c | ) |
Definition at line 535 of file bourdoncle.c.
References CONS, CONTROL, and embedding_control_list.
Referenced by node_to_linked_nodes(), and print_embedding_graph().
Called from within a loop where neither t nor new_s are consistent.
Allocate a meaningless control
t may not be consistent because of the caller ifdebug(1) { pips_assert("t is consistent", check_control_statement(t)); }
Definition at line 1318 of file bourdoncle.c.
References bool_to_string(), CAR, CONS, CONTROL, CONTROL_, control_successors, control_test_p(), free_meaningless_control(), gen_length(), gen_nconc(), make_meaningless_control(), MAPL, meaningless_control_p(), NIL, pips_assert, pips_debug, and rank.
Referenced by update_successor_in_copy().
|
static |
Functions to deal with the ancestor_map.
Definition at line 837 of file bourdoncle.c.
References HASH_MAP.
Referenced by add_child_parent_pair(), control_to_ancestor(), and registered_controls_p().
unstructured ancestor_cycle_head_to_scc | ( | control | a, |
hash_table | scc_map | ||
) |
scc_map maps either the ancestor node to its scc if the transformers are computed without context, or the call site node to its scc if cycles are replicated to compute transformers within their context.
In spite of the name, this function can be call with ANY control, ancestor or not. An ancestor or a call site are mapped to a defined value.
scc_map | cc_map |
Definition at line 2356 of file bourdoncle.c.
References hash_get(), HASH_UNDEFINED_VALUE, and unstructured_undefined.
Referenced by cycle_head_p(), cycle_head_to_scc(), cycle_to_flow_sensitive_preconditions(), dag_to_flow_sensitive_preconditions(), direct_cycle_head_p(), load_control_fix_point(), and replicate_cycles().
|
static |
No control can be an ancestor and a child.
Definition at line 905 of file bourdoncle.c.
References CONS, CONTROL, ENDP, gen_free_list(), gen_list_and(), gen_once(), HASH_MAP, ifdebug, NIL, pips_debug, print_control_nodes(), and print_control_to_control_mapping().
Referenced by scc_to_dag().
list bourdoncle_component | ( | control | vertex, |
hash_table | ancestor_map, | ||
hash_table | scc_map | ||
) |
bourdoncle partition
Build sub-unstructured associated to vertex and partition
Re-use copying performed in scc_to_dag() instead u = partition_to_unstructured(vertex, partition); vertex_ancestor = control_to_ancestor(vertex, ancestor_map); hash_put(scc_map, vertex_ancestor, u);
The partition may have to be refreshed because of the previous recursive descent and its graph restructuring action. It is assumed that vertex is still good because heads are not: however vertex is not an ancestor because the input unstructured is copied right away by bourdoncle_partition().
It might be better to recompute the smallest scc including vertex...
Update parent unstructured containing vertex and partition, remove partition and return a new unstructured with the partition inside, except for the initial vertex node which is left in the embedding graph
Build sub-unstructured associated to vertex and partition
u = unlink_partition_and build_unstructured(vertex, partition);
Do not go down into nested unstructured
vertex | ertex |
ancestor_map | ncestor_map |
scc_map | cc_map |
Definition at line 2218 of file bourdoncle.c.
References bourdoncle_visit(), CONS, CONTROL, control_domain, control_successors, control_to_ancestor(), control_undefined, gen_copy_seq(), gen_false(), gen_free_list(), gen_multi_recurse(), gen_null(), gen_true(), get_dfn(), hash_put(), ifdebug, list_undefined, MAP, NIL, pips_debug, print_control_node_b(), print_control_nodes(), scc_to_dag(), statement_domain, unstructured_control, unstructured_exit, unstructured_undefined, and update_partition().
Referenced by bourdoncle_visit().
void bourdoncle_free | ( | unstructured | ndu, |
hash_table | ancestor_map, | ||
hash_table | scc_map | ||
) |
Do not free the statements pointed by the nodes in ndu or in the scc
ndu | du |
ancestor_map | ncestor_map |
scc_map | cc_map |
Definition at line 2506 of file bourdoncle.c.
References bourdoncle_unstructured_free(), HASH_MAP, and hash_table_free().
Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().
list bourdoncle_partition | ( | unstructured | u, |
unstructured * | p_ndu, | ||
hash_table * | p_ancestor_map, | ||
hash_table * | p_scc_map | ||
) |
DAG derived from u by elimination all cycles
mapping from nodes in the new unstructured to the node in the input unstructured
mapping from nodes in u, used as cycle breakers, to the corresponding scc represented as an unstructured
Initialize dfn to 0
Start from the entry point
Should the partition be translated?
Should the cycles be replicated to refine the analyses? If yes, replicate them.
Control nodes associated to a fix point
The hierarchy of fix points is/seems to be lost by scc_map...
We also need the final embedding graph... which might be lost? Or hanging from the first node in partition, the entry point, and hence from new_u.
p_ndu | _ndu |
p_ancestor_map | _ancestor_map |
p_scc_map | _scc_map |
Definition at line 1902 of file bourdoncle.c.
References bourdoncle_visit(), control_domain, control_undefined, davinci_print_non_deterministic_unstructured(), dfn, fprintf(), gen_false(), gen_multi_recurse(), gen_null(), gen_true(), get_bool_property(), hash_get(), HASH_MAP, hash_pointer, hash_table_free(), hash_table_make(), HASH_UNDEFINED_VALUE, ifdebug, NIL, num, pips_debug, print_control_nodes(), print_unstructured(), replicate_cycles(), reset_dfn(), set_davinci_count(), statement_domain, unstructured_control, unstructured_shallow_copy(), and unstructured_undefined.
Referenced by unstructured_to_flow_sensitive_postconditions_or_transformers().
|
static |
Suppress references to statements, but do not go down recursively into nested unstructured.
Definition at line 2495 of file bourdoncle.c.
References control_domain, free_unstructured(), gen_false(), gen_multi_recurse(), gen_null(), gen_true(), statement_domain, and suppress_statement_reference().
Referenced by bourdoncle_free().
int bourdoncle_visit | ( | control | vertex, |
list * | ppartition, | ||
hash_table | ancestor_map, | ||
hash_table | scc_map | ||
) |
vertex | ertex |
ppartition | partition |
ancestor_map | ncestor_map |
scc_map | cc_map |
Definition at line 2293 of file bourdoncle.c.
References bourdoncle_component(), CONS, CONTROL, control_successors, gen_nconc(), get_dfn(), MAP, min, num, and update_dfn().
Referenced by bourdoncle_component(), and bourdoncle_partition().
The true and false branches should be empty most of the time. But a structured test used a non-deterministic node might very well have two successors or more. The assert below is too strong.
Since some test statements are left structured and since structure and unstructured test statements may be non-deterministic here, nothing can be said.
Non-deterministic environment
Non-deterministic environment
A meaningless control can be shared in intermediate states
It should not be shared, not only because memory management would be impossible locally but also because gen_recurse() would follow forbidden paths.
Definition at line 198 of file bourdoncle.c.
References CONTROL, control_predecessors, control_statement, control_successors, gen_in_list_p(), gen_length(), ifdebug, MAP, meaningless_control_p(), pips_assert, print_control_node_without_check(), and statement_test_p().
Referenced by davinci_print_control_node(), print_and_check_control_node(), print_embedding_graph(), and scc_to_dag().
Take care of two problems: meaningless control nodes may end up shared by effective nodes and they may end up uselessly numerous.
FI: Two more problems could be tackled. The same node should not be twice a true or twice a false successor, although a given node can be a true and a false successor. gen_once() should be used to build t_succs and f_succs but the assertions and the memory management should then be updated. Duplicate could be chained to the u_succs(), the useless successors
true branch successors
false branch successors
empty successors
Number of eliminations
Partition the successors
Rebuild the successor list if it can be useful
new successor list
FI: I do not see why you are sure not to need all meaningless controls... There might be no meaningless control at all. The next two assertions seem too strong.
Courageously, free the remaining meaningless successors
Update the successor list of c
Free the partition lists
Definition at line 655 of file bourdoncle.c.
References CAR, CONS, CONTROL, control_successors, ENDP, fprintf(), free_meaningless_control(), gen_free_list(), gen_length(), gen_nconc(), ifdebug, MAP, meaningless_control_p(), NIL, nts, pips_assert, POP, and rank.
Referenced by clean_up_embedding_graph().
|
static |
number of replications
number of eliminations
FI: A level of 1 makes more sense, but it is very slow on large graphs. The same nodes are checked several times because the cache managed by control_consistent_p() is lost between iterations.
A meaningless control must have only one predecessor and no successor.
A non-deterministic test does not need too many meaningless successors. A new list must be built first because clean_up_control_test() destroys elements of el, which cannot be scanned any longer.
Definition at line 747 of file bourdoncle.c.
References CAR, CDR, clean_up_control_test(), CONS, CONTROL, control_consistent_p(), control_predecessors, control_successors, control_test_p(), ENDP, fprintf(), gen_free_list(), gen_length(), gen_list_patch(), ifdebug, list_undefined, make_meaningless_control(), MAP, meaningless_control_p(), NIL, node_to_linked_nodes(), pips_assert, pips_debug, and POP.
Referenced by scc_to_dag().
Definition at line 402 of file bourdoncle.c.
References CAR, CONTROL, control_statement, meaningless_control_p(), s1, and statement_ordering.
Referenced by davinci_print_control_nodes(), and davinci_print_non_deterministic_unstructured().
Definition at line 970 of file bourdoncle.c.
References control_predecessors, control_statement, control_successors, control_undefined, gen_copy_seq(), hash_put(), make_control(), and replicate_map.
Referenced by partition_to_unstructured(), and unstructured_shallow_copy().
Check that a node is used as a test in a CFG.
The associated statement must be a test, the number of successors must be two and the true and false branches must be empty. Exported for user of ND CFG's.
Definition at line 175 of file bourdoncle.c.
References control_statement, control_successors, empty_statement_or_labelless_continue_p(), gen_length(), meaningless_control_p(), statement_test(), statement_test_p(), test_false, and test_true.
Referenced by add_test_successor(), clean_up_embedding_graph(), dag_to_flow_sensitive_preconditions(), davinci_print_control_node(), intersect_successors_with_partition_or_complement(), load_arc_precondition(), one_successor_kind_only_p(), process_ready_node(), update_successor_in_copy(), and update_successors_of_predecessor().
control control_to_ancestor | ( | control | vertex, |
hash_table | ancestor_map | ||
) |
If vertex is an ancestor control node from the input control graph, return vertex, else return its ancestor.
Is used in other libraries.
This assert may be too strong, but all control nodes are copied when just after entering bourdoncle_partition which should make it correct.
Theoretically only useful when HASH_UNDEFINED_VALUE has been returned, i.e. when ancestor==vertex
vertex | ertex |
ancestor_map | ncestor_map |
Definition at line 854 of file bourdoncle.c.
References ancestor_control_p(), control_statement, control_undefined, hash_get(), HASH_UNDEFINED_VALUE, ifdebug, pips_assert, pips_debug, and statement_identification().
Referenced by bourdoncle_component(), cycle_head_p(), cycle_head_to_scc(), cycle_to_flow_sensitive_preconditions(), dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), dag_to_flow_sensitive_preconditions(), load_control_fix_point(), load_cycle_temporary_precondition(), replicate_cycles(), and update_partition().
Definition at line 1002 of file bourdoncle.c.
References hash_get(), HASH_UNDEFINED_VALUE, pips_assert, and replicate_map.
Referenced by partition_to_unstructured(), and unstructured_shallow_copy().
|
static |
Definition at line 982 of file bourdoncle.c.
References CAR, CONTROL, CONTROL_, control_predecessors, control_successors, hash_get(), HASH_UNDEFINED_VALUE, MAPL, pips_assert, and replicate_map.
Referenced by unstructured_shallow_copy().
Definition at line 111 of file bourdoncle.c.
References dfn, hash_get(), hash_put(), HASH_UNDEFINED_VALUE, and pips_internal_error.
Referenced by scc_to_dag().
bool cycle_head_p | ( | control | c, |
hash_table | ancestor_map, | ||
hash_table | scc_map | ||
) |
This node is a cycle call site.
This is correct whether the actual scc associated to c is scc_u or not. If a copy of a control is associated to a scc, its ancestors and all the others copies also are associated to a scc.
we may be in the context sensitive transformer mode
ancestor_map | ncestor_map |
scc_map | cc_map |
Definition at line 2385 of file bourdoncle.c.
References ancestor_cycle_head_to_scc(), control_to_ancestor(), and unstructured_undefined_p.
Referenced by cycle_to_flow_sensitive_preconditions(), dag_to_flow_sensitive_preconditions(), davinci_print_non_deterministic_unstructured(), process_ready_node(), replicate_cycles(), and unstructured_to_effects().
unstructured cycle_head_to_scc | ( | control | c, |
hash_table | ancestor_map, | ||
hash_table | scc_map | ||
) |
The ancestor of this node is associated to a specific cycle.
either we have a direct connection, or we need to go thru the ancestor node
ancestor_map | ncestor_map |
scc_map | cc_map |
Definition at line 2433 of file bourdoncle.c.
References ancestor_cycle_head_to_scc(), control_to_ancestor(), and unstructured_undefined_p.
Referenced by dag_to_flow_sensitive_preconditions(), process_ready_node(), and unstructured_to_effects().
|
static |
Output CFG in daVinci format.
The same node can be an entry and an exit node.
Declare arcs
Definition at line 344 of file bourdoncle.c.
References CAR, CDR, check_control_statement(), CONTROL, control_statement, control_successors, control_test_p(), ENDP, f(), fprintf(), MAPL, meaningless_control_p(), ORDERING_NUMBER, ORDERING_STATEMENT, and statement_ordering.
Referenced by davinci_print_control_nodes(), and davinci_print_non_deterministic_unstructured().
Definition at line 433 of file bourdoncle.c.
References CAR, CDR, concatenate(), CONTROL, control_cons_compare(), davinci_count, davinci_print_control_node(), db_get_current_workspace_directory(), ENDP, f(), fprintf(), free(), gen_copy_seq(), gen_free_list(), gen_sort_list(), get_current_module_name(), i2a(), MAPL, safe_fclose(), and safe_fopen().
Referenced by print_embedding_graph().
|
static |
It may be called with an empty ancestor and scc maps.
Definition at line 472 of file bourdoncle.c.
References CAR, CDR, concatenate(), CONTROL, control_cons_compare(), control_undefined, cycle_head_p(), davinci_count, davinci_print_control_node(), db_get_current_workspace_directory(), ENDP, f(), forward_control_map_get_blocs(), fprintf(), free(), gen_copy_seq(), gen_free_list(), gen_in_list_p(), gen_sort_list(), get_current_module_name(), hash_get(), hash_table_entry_count(), HASH_UNDEFINED_VALUE, i2a(), list_undefined, MAPL, meaningless_control_p(), NIL, pips_debug, safe_fclose(), safe_fopen(), unstructured_control, and unstructured_exit.
Referenced by bourdoncle_partition().
bool direct_cycle_head_p | ( | control | c, |
hash_table | scc_map | ||
) |
This node is directly associated to a specific cycle.
scc_map | cc_map |
Definition at line 2422 of file bourdoncle.c.
References ancestor_cycle_head_to_scc(), and unstructured_undefined_p.
Referenced by replicate_cycles().
Definition at line 1167 of file bourdoncle.c.
References entry_or_exit_control_p().
Referenced by scc_to_dag().
Definition at line 1149 of file bourdoncle.c.
References CONTROL, control_predecessors, control_successors, gen_in_list_p(), MAP, and meaningless_control_p().
Referenced by entry_control_p(), and exit_control_p().
Definition at line 1172 of file bourdoncle.c.
References entry_or_exit_control_p().
Referenced by scc_to_dag().
Definition at line 2481 of file bourdoncle.c.
References one_successor_kind_only_p().
Referenced by dag_to_flow_sensitive_preconditions(), and process_ready_node().
|
static |
free_control() cannot be used because you do not want to free the successors and the predecessors
Definition at line 159 of file bourdoncle.c.
References control_predecessors, control_statement, control_successors, free_control(), gen_free_list(), list_undefined, pips_assert, and statement_undefined_p.
Referenced by add_test_successor(), and clean_up_control_test().
Definition at line 121 of file bourdoncle.c.
References dfn, hash_get(), HASH_UNDEFINED_VALUE, and pips_internal_error.
Referenced by bourdoncle_component(), bourdoncle_visit(), and scc_to_dag().
partition | artition |
Definition at line 1224 of file bourdoncle.c.
References intersect_successors_with_partition_or_complement().
Referenced by scc_to_dag().
partition | artition |
Definition at line 1230 of file bourdoncle.c.
References intersect_successors_with_partition_or_complement().
Referenced by scc_to_dag().
void intersect_successors_with_partition_or_complement | ( | control | c, |
list | partition, | ||
bool | complement_p | ||
) |
If complement_p, preserve successors in the complement of partition.
Else preserve successors in partition. Take care of test nodes wich must keep two successors no matter what.
The CFG may not be connexe or the exit path may be hidden by a STOP statement
Let's boldy assume the parent control node is used as a CFG test statement and preserve the number of successors.
It is not a CFG test node: get rid of useless
Not true: you may have non-connexe CFG and loops with no exit.
pips_assert("We still have at least one successor", gen_length(*succs)>0);
partition | artition |
complement_p | omplement_p |
Definition at line 1181 of file bourdoncle.c.
References CAR, CONS, CONTROL, CONTROL_, control_successors, control_test_p(), gen_in_list_p(), gen_length(), gen_list_and(), gen_list_and_not(), make_meaningless_control(), MAPL, NIL, and pips_assert.
Referenced by intersect_successors_with_partition(), and intersect_successors_with_partition_complement().
With non-deterministic graph, the outcome of a test may be known in advance.
Never taken branches are filled in with meaningless nodes.
Definition at line 146 of file bourdoncle.c.
References ENDP, make_control(), pips_assert, and statement_undefined.
Referenced by add_test_successor(), clean_up_embedding_graph(), intersect_successors_with_partition_or_complement(), partition_to_unstructured(), and update_successors_of_predecessor().
Is exported to exploit non-deterministic control flow graphs.
Definition at line 154 of file bourdoncle.c.
References control_statement, and statement_undefined_p.
Referenced by add_test_successor(), check_control_statement(), clean_up_control_test(), clean_up_embedding_graph(), control_cons_compare(), control_test_p(), cycle_to_flow_sensitive_preconditions(), dag_or_cycle_to_flow_sensitive_postconditions_or_transformers(), dag_to_flow_sensitive_preconditions(), davinci_print_control_node(), davinci_print_non_deterministic_unstructured(), entry_or_exit_control_p(), get_control_precondition(), node_to_path_transformer_or_postcondition(), one_successor_kind_only_p(), print_embedding_graph(), process_ready_node(), process_unreachable_node(), registered_controls_p(), replicate_cycles(), store_control_fix_point(), store_control_postcondition(), unstructured_to_effects(), update_control_postcondition(), and update_partition().
Allocate a list of control nodes transitively linked to control c.
Definition at line 626 of file bourdoncle.c.
References add_control_to_embedding_control_list(), control_domain, embedding_control_list, gen_false(), gen_multi_recurse(), gen_null(), gen_true(), ifdebug, list_undefined, NIL, pips_assert, pips_debug, print_control_nodes(), and statement_domain.
Referenced by clean_up_embedding_graph(), scc_to_dag(), and update_partition().
useful for non-deterministic control flow graph only
There exists at least one real successor of the requested kind and only meaningless successors of the other kind.
true_p | rue_p |
Definition at line 2451 of file bourdoncle.c.
References CONTROL, control_successors, control_test_p(), MAP, meaningless_control_p(), and pips_assert.
Referenced by false_successors_only_p(), and true_successors_only_p().
FUNCTIONS FOR BOURDONCLE_COMPONENT()
Check the existence of a path from b to e with all its element in partition
You might be interested in the existence of a cycle from b to b
pips_assert("b is not e", b!=e);
Definition at line 2015 of file bourdoncle.c.
References bool_to_string(), CONS, CONTROL, control_successors, end, ENDP, gen_copy_seq(), gen_free_list(), gen_in_list_p(), gen_remove(), ifdebug, MAP, NIL, pips_assert, and pips_debug.
Referenced by update_partition().
unstructured partition_to_unstructured | ( | control | vertex, |
list | partition | ||
) |
Build a new unstructured (CFG) for partition.
vertex is the entry and exit point. New nodes must be allocated because the parent graph is untouched. vertex is supposed to be included into partition.
Create the translation table replicate_map
Generate new unstructured with relevant entry and exit node vertex
Update arcs
Update predecessors
The only predecessors that are useful are in partition
This predecessor is irrelevant
Handle successors
This successor is irrelevant but irrelevant true branches must be preserved
A second irrelevant successor is not needed. But are we ready to have IF nodes with only one successor?
useless = CONS(CONTROL, old_c, useless);
vertex | ertex |
partition | artition |
Definition at line 1053 of file bourdoncle.c.
References CAR, CDR, CONS, CONTROL, CONTROL_, control_predecessors, control_shallow_copy(), control_successors, control_to_replicate(), control_undefined, control_undefined_p, gen_free_list(), gen_in_list_p(), gen_length(), gen_list_and_not(), hash_get(), hash_pointer, hash_table_free(), hash_table_make(), hash_table_undefined, HASH_UNDEFINED_VALUE, make_meaningless_control(), make_unstructured(), MAP, MAPL, NIL, pips_assert, replicate_map, unstructured_undefined, and useless().
Definition at line 276 of file bourdoncle.c.
References check_control_statement(), CONTROL, control_predecessors, control_statement, control_successors, fprintf(), gen_length(), MAP, and safe_statement_identification().
Referenced by print_control_node_b(), and print_control_node_without_check().
|
static |
Definition at line 299 of file bourdoncle.c.
References print_and_check_control_node().
Referenced by bourdoncle_component(), print_embedding_graph(), print_unstructured(), registered_controls_p(), scc_to_dag(), and update_successor_in_copy().
|
static |
Code partly replicated from semantics/unstructured.c to be able to taylor it to the exact needs.
Definition at line 304 of file bourdoncle.c.
References print_and_check_control_node().
Referenced by check_control_statement(), and update_successor_in_copy().
|
static |
Was moved into ri-util/control, minus the check_control_statement()
Definition at line 322 of file bourdoncle.c.
References CONTROL, control_statement, fprintf(), MAP, and safe_statement_identification().
Referenced by update_successors_of_predecessor().
|
static |
Definition at line 823 of file bourdoncle.c.
References fprintf(), and HASH_MAP.
Referenced by ancestor_map_consistent_p(), and scc_to_dag().
Do not go down into nested unstructured
Check its structure: make sure that each node is a successor of its predecessors and a predecessor of all its successors
Make sure that no meaningful node only has meaningless successors
Make sure that no node has any meaningless predecessor
Make sure that destructured test statements always have two successors... not ture anymore with non-determinacy.
Definition at line 540 of file bourdoncle.c.
References add_control_to_embedding_control_list(), check_control_statement(), CONTROL, control_domain, control_predecessors, control_successors, davinci_print_control_nodes(), embedding_control_list, ENDP, fprintf(), gen_false(), gen_free_list(), gen_in_list_p(), gen_multi_recurse(), gen_null(), gen_true(), ifdebug, MAP, meaningless_control_p(), NIL, pips_assert, pips_debug, print_control_node_b(), and statement_domain.
Referenced by scc_to_dag().
|
static |
Definition at line 959 of file bourdoncle.c.
References fprintf(), HASH_MAP, and replicate_map.
Referenced by unstructured_shallow_copy().
|
static |
Do not go down into nested unstructured
Definition at line 331 of file bourdoncle.c.
References control_domain, gen_false(), gen_multi_recurse(), gen_null(), gen_true(), pips_debug, print_control_node_b(), statement_domain, unstructured_control, and unstructured_exit.
Referenced by bourdoncle_partition().
bool proper_cycle_head_p | ( | control | c, |
hash_table | scc_map | ||
) |
This node is really the head of a cycle (red on daVinci pictures).
scc_map | cc_map |
Definition at line 2405 of file bourdoncle.c.
References HASH_MAP, and unstructured_control.
Referenced by replicate_cycles().
unstructured proper_cycle_head_to_scc | ( | control | h, |
hash_table | scc_map | ||
) |
Retrieve a scc_u from its head.
scc_map | cc_map |
Definition at line 2368 of file bourdoncle.c.
References HASH_MAP, unstructured_control, and unstructured_undefined.
Referenced by dag_to_flow_sensitive_preconditions().
|
static |
Definition at line 882 of file bourdoncle.c.
References ancestor_control_p(), CONTROL, hash_get(), HASH_UNDEFINED_VALUE, ifdebug, MAP, meaningless_control_p(), pips_debug, and print_control_node_b().
Referenced by scc_to_dag().
|
static |
Only the head of the main unstructured can be a pointer to a cycle. The head of a scc cannot point to another scc as they would be the same by construction: all their cycles would be cut off by the head of each scc.
Only live scc are useful
we really need a shallow_free_unstructured()
free_unstructured(u_u);
Definition at line 1803 of file bourdoncle.c.
References ancestor_cycle_head_to_scc(), CONS, control_to_ancestor(), cycle_head_p(), direct_cycle_head_p(), ENDP, FORWARD_CONTROL_MAP, gen_free_list(), gen_in_list_p(), gen_nconc(), hash_delget(), HASH_MAP, hash_put(), hash_table_entry_count(), ifdebug, MAP, meaningless_control_p(), NIL, pips_assert, pips_debug, pips_internal_error, proper_cycle_head_p(), UNSTRUCTURED, unstructured_control, unstructured_shallow_copy(), unstructured_undefined, and unstructured_undefined_p.
Referenced by bourdoncle_partition().
|
static |
Definition at line 106 of file bourdoncle.c.
References dfn, and hash_put().
Referenced by bourdoncle_partition().
|
static |
The nodes in scc partition but root must be removed.
Replicated nodes must be added to build all input and output paths to and from root using control nodes in partition.
This is the key change to Bourdoncle's algorithm. When moving back up in the recursion, the CFG is altered to obtain pure cycles with only one entry and one exit nodes.
The cycle head must be a non-deterministic control node. Hence it cannot be a test since tests stay deterministics (thanks to Pierre's data structure). Another node in the partition could be chosen as new cycle head, but the partition may only contain tests with side effects. Instead we choose to insert a non-deterministic node in front in case it is needed. The initial CFG is less disturbed.
Well, I changed my mind again because inserting new control nodes does not make it easy to stay compatible with Bourdoncle's algorithm and previous assumptions made about the cycle head. Instead, tests can become non-deterministic. The number of successors must be even or odd. Odd successors are true successors. Even successors are false successors.
Look for new input nodes in partition
c cannot have been replicated earlier or it would not be in partition
Keep only predecessors out of partition for new_c1.
Make sure that new_c1 is a successor of its predecessors... Oupss, there is a problem with test to encode the fact that is is a true or a false successor?
Keep only c's predecessors in partition.
That's probably wrong and damaging because we need them for paths crossing directly the SCC and useless because these nodes will be destroyed in parent graph.
Update the successor of its predecessors
Update successors of new_c1 which have already been replicated
Add new_c1 as predecessor of new_succ
Look for new output nodes
c cannot have been replicated earlier or it would not be in partition
Keep only successors out of partition for new_c2.
A true branch successor may have to be replaced to preserve the position of the false branch successor.
gen_list_and_not(&control_successors(new_c2), partition);
Update reverse arcs
Keep only c's succcessors in partition. Wise or not? See above...
gen_list_and(&control_successors(c), partition);
Reverse arcs have already been correctly updated
Update predecessors of new_c2 which have already been replicated
gen_list_patch() has no effect because new_pred's successors have already been updated and c does not appear there.
gen_list_patch(control_successors(new_pred), c, new_c2);
Update reverse edges of predecessors... which may be tough if you end up with more than one true and/or more than one false successor.
Remove cycle partition but its head
We do not want to free these nodes because they are part of partition. We should not have duplicated partition earlier to make a new unstructured. We only need a copy of the head, root. This should be dealt with after scc_to_dag is called and not before.
MAP(CONTROL, c, { if(c!=root) { shallow_free_control(c); } } , partition);
Unlink partition from its head. We could keep an arc from root to root...
This unlinking would better be performed at the caller level, even though this would make the name scc_to_dag() imprecise.
replicate root and unlink the cycles defined by partition from the embedding graph
new_root does not belong to partition and must be processed too.
All nodes are linked to an ancestor node or are an ancestor or are meaningless
Definition at line 1465 of file bourdoncle.c.
References add_child_parent_pair(), ancestor_map_consistent_p(), CAR, check_control_statement(), clean_up_embedding_graph(), CONTROL, CONTROL_, control_predecessors, control_statement, control_successors, control_undefined, copy_dfn(), ENDP, entry_control_p(), exit_control_p(), fprintf(), gen_copy_seq(), gen_free_list(), gen_list_and(), gen_list_and_not(), gen_list_patch(), gen_once(), get_dfn(), hash_get(), hash_pointer, hash_put(), hash_table_free(), hash_table_make(), HASH_UNDEFINED_VALUE, ifdebug, intersect_successors_with_partition(), intersect_successors_with_partition_complement(), list_undefined, make_control(), make_unstructured(), MAP, MAPL, node_to_linked_nodes(), pips_assert, pips_debug, POP, print_control_node_b(), print_control_nodes(), print_control_to_control_mapping(), print_embedding_graph(), registered_controls_p(), unstructured_undefined, update_predecessors_of_successor(), update_successor_in_copy(), and update_successors_of_predecessor().
Referenced by bourdoncle_component().
|
static |
Definition at line 427 of file bourdoncle.c.
References davinci_count.
Referenced by bourdoncle_partition().
|
static |
The statements were not replicated and are still pointed to by the initial unstructured.
Definition at line 2488 of file bourdoncle.c.
References control_statement, and statement_undefined.
Referenced by bourdoncle_unstructured_free().
Definition at line 2474 of file bourdoncle.c.
References one_successor_kind_only_p().
Referenced by dag_to_flow_sensitive_preconditions(), and process_ready_node().
unstructured unstructured_shallow_copy | ( | unstructured | u, |
hash_table | ancestor_map | ||
) |
Do not go down into nested unstructured and replicate all control nodes
Update predecessor and successor arcs of the new control nodes to point to the new control nodes using the global conversion mapping replicate_map
Generate new unstructured with relevant entry and exit nodes
Generate ancestor_map as the inverse function of replicate_map
ancestor_map | ncestor_map |
Definition at line 1009 of file bourdoncle.c.
References add_child_parent_pair(), control_domain, control_shallow_copy(), control_to_replicate(), control_translate_arcs(), gen_false(), gen_multi_recurse(), gen_null(), gen_true(), HASH_MAP, hash_pointer, hash_table_free(), hash_table_make(), hash_table_undefined, hash_table_undefined_p, ifdebug, make_unstructured(), pips_assert, print_replicate_map(), replicate_map, statement_domain, unstructured_control, unstructured_exit, and unstructured_undefined.
Referenced by bourdoncle_partition(), and replicate_cycles().
Definition at line 131 of file bourdoncle.c.
References dfn, and hash_update().
Referenced by bourdoncle_visit().
|
static |
Controls in partition may have been copied and may not appear anymore in the graph embedding root. The input graph is modified to separate clean cycles with one entry-exit node, but Bourdoncle's algorithm is not aware of this.
Find a replacement for c, and hope to find only one!
pips_internal_error("No replacement for node %p", c);
This node must be eliminated since it is no longer part of the partition, probably because it has disappeared in an inner cycle.
Many possible replacements... Keep them all.
Some nodes may no longer be part of the partition because they only belonged to an inner cycle which has already been eliminated.
Unreachable controls have been found
It does not make sense to use &partition but...
Definition at line 2066 of file bourdoncle.c.
References CAR, CDR, CONS, CONTROL, CONTROL_, control_to_ancestor(), gen_free_list(), gen_in_list_p(), gen_length(), gen_list_and_not(), gen_nconc(), gen_once(), ifdebug, MAP, MAPL, meaningless_control_p(), NIL, node_to_linked_nodes(), partition_successor_p(), pips_assert, pips_debug, and print_control_nodes().
Referenced by bourdoncle_component().
These asserts might become wrong when intermediate CONTINUE nodes are used to carry many true and/or false successors
Definition at line 1305 of file bourdoncle.c.
References CONS, CONTROL, control_predecessors, gen_in_list_p(), and pips_assert.
Referenced by scc_to_dag().
|
static |
Make new_c a successor of new_pred, the same way c is a successor of pred.
new_c is not consistent on entry: it points towards pred but is not a successor of pred. Also, this function is called from within a loop and new_c is onsistent only on loop exit.
new_c is not consistent, this is why this function is called!
c and new_c have pred as predecessor
new_c must have new_pred as predecessor instead
Definition at line 1381 of file bourdoncle.c.
References add_test_successor(), CONS, CONTROL, control_predecessors, control_statement, control_successors, control_test_p(), gen_in_list_p(), gen_list_patch(), gen_nconc(), gen_position(), ifdebug, NIL, pips_assert, pips_debug, print_control_node_b(), and print_control_node_without_check().
Referenced by scc_to_dag().
new_c is not consistent on entry and might not be on exit because it is called from within a loop
A meaningless control node must be inserted?
true successor
r%2==0
No problem this kind of node may have several successors
Definition at line 1263 of file bourdoncle.c.
References CONS, CONTROL, control_successors, control_test_p(), gen_in_list_p(), gen_length(), gen_nconc(), gen_position(), ifdebug, make_meaningless_control(), NIL, pips_assert, pips_debug, pips_internal_error, and print_control_nodes_without_check().
Referenced by scc_to_dag().
|
static |
This counter is pre-incremented each time a new graph is stored to generate a new file name.
Definition at line 425 of file bourdoncle.c.
Referenced by davinci_print_control_nodes(), davinci_print_non_deterministic_unstructured(), and set_davinci_count().
|
static |
Decomposition of a CFG into SCC's and sub-SCC's. Algorithm 3.9, Page 43, Francois Bourdoncle's PhD. Define heuristically SCC and sub-SCC heads.
Build a set of new data structures to represent any CFG as a recursive structure of CFG's (scc_map) and one parent DAG (ndu) and one node traversal order (partition list) and a correspondance between the new nodes and the original nodes (ancestor_map).
Some predecessors or successors must be deleted in the recursive descent. These vertices are given a statement_undefined statement and empty lists of predecessors and successors. Empty successors must be maintained so as to know if they are true or false successors. I suppose that we do not really care about irrelevant predecessors and that we might as well delete them. In fact, only the true branch successor absolutely must be preserved.
Since the new CFG's are not deterministic, the number of successors is not bounded to two and any statement can have more than one successor. Standard consistency check are likely to fail if applied to the unstructured produced by this decomposition.
When a node pointing to a scc is replicated, two options are available. Either all copies point to a unique scc (initial implementation) or each control copy points towards its own copy of the scc. In the initial implementation and first option, only ancestor control nodes can point to a scc, and ancestor_map is used to reach the scc_associated to a node. In the second case, any control node, replicated or not, can point to a scc. The first option makes sense when transformers are not context dependent: all identical cycles can be analyzed as one cycle, although I do not understand the miracle for the preconditions, since they clearly are context-sensitive. The second option is useful when transformers are computed in context, since all replicates of a cycle can operate in diferrent contexts. This is performed as a post-processing step conditional to property SEMANTICS_COMPUTE_TRANSFORMERS_IN_CONTEXT.
Structure of the code: bourdoncle_partition() bourdoncle_visit() bourdoncle_component() bourdoncle_visit() recursively update_partition() scc_to_dag() [Not part of Bourdoncle's algorithm: transforms a scc into a non-deterministic while loop] replicate_cycles() [Not part of Bourdoncle's algorithm: allocate a copy of each scc, i.e. cycle, i.e. while loop for each of its "call" sites] Data structures for Bourdoncle's heuristics:
dfn = depth first number
num = current vertex number
vertex_stack = stack of visited nodes
Definition at line 104 of file bourdoncle.c.
Referenced by bourdoncle_partition(), copy_dfn(), get_dfn(), reset_dfn(), and update_dfn().
Definition at line 533 of file bourdoncle.c.
Referenced by add_control_to_embedding_control_list(), node_to_linked_nodes(), and print_embedding_graph().
|
static |
Definition at line 137 of file bourdoncle.c.
Referenced by adg_get_integer_entity(), adg_rename_entities(), adg_reorder_statement_number(), bourdoncle_partition(), bourdoncle_visit(), build_new_ref(), cmf_layout_align(), config_vecteur(), craft_layout_align(), creer_nom_entite(), ensure_comment_consistency(), find_or_create_coeff(), float_to_entity(), gen_make_array(), get_nlc_number(), gfc2pips_assign_gfc_code_to_num_comments(), gfc2pips_comment_num_exists(), gfc2pips_push_comment(), int_to_entity(), make_array_bounds(), make_coeff(), make_HRE_empty_module(), make_integer_constant_entity(), make_new_module_variable(), make_new_simd_vector_with_prefix(), make_nlc_entity(), make_nsp_entity(), make_nub_entity(), my_build_new_ref(), number_replaces_var(), pips_signal_handler(), read_new_entities_from_eole(), sc_min(), sc_simplex_feasibility_ofl_ctrl_fixprec(), and text_unstructured().
|
static |
Replication of unstructured (i.e.
CFG) and control nodes (i.e. vertices)
Definition at line 957 of file bourdoncle.c.
Referenced by control_shallow_copy(), control_to_replicate(), control_translate_arcs(), partition_to_unstructured(), print_replicate_map(), and unstructured_shallow_copy().