25 #include "pips_config.h"
67 #define vertex_predecessors vertex_successors
68 #define predecessor_vertex successor_vertex
69 #define make_predecessor make_successor
70 #define free_predecessor free_successor
71 #define PREDECESSOR SUCCESSOR
72 #define PREDECESSOR_TYPE SUCCESSOR_TYPE
73 #undef PREDECESSOR_NEWGEN_DOMAIN
74 #define PREDECESSOR_NEWGEN_DOMAIN (-1)
75 #undef SUCCESSOR_NEWGEN_DOMAIN
76 #define SUCCESSOR_NEWGEN_DOMAIN (-1)
77 #undef gen_SUCCESSOR_cons
78 #define gen_SUCCESSOR_cons gen_cons
79 #define gen_PREDECESSOR_cons gen_cons
80 #define gen_successor_cons gen_cons
81 #define gen_predecessor_cons gen_cons
106 bool pred_has_been_found_p =
false;
107 list predecessors_to_remove =
NIL;
113 pred_has_been_found_p =
true;
120 }, predecessors_to_remove);
122 return pred_has_been_found_p;
138 list predecessors_to_change =
NIL;
139 bool interval_already_in_predecessors =
false;
144 predecessors_to_change);
146 interval_already_in_predecessors =
true;
148 if (predecessors_to_change !=
NIL) {
154 if (! interval_already_in_predecessors)
182 add_to_interval_or_create_new_interval(
vertex node,
186 bool a_node_has_been_added;
190 list intervals_to_be_removed =
NIL;
196 a_node_has_been_added =
false;
199 if (!
set_belong_p(selected_nodes, (
char *) candidate)) {
200 bool all_predecessors_are_in_current_interval =
true;
205 all_predecessors_are_in_current_interval =
false;
209 if (all_predecessors_are_in_current_interval) {
217 a_node_has_been_added =
true;
222 }
while(a_node_has_been_added);
263 bool a_node_has_been_fused;
264 bool the_interval_graph_has_been_modified =
false;
271 a_node_has_been_fused =
false;
274 if (
node != entry_interval
279 pips_debug(8,
"\tonly one vertex predecessor %p.\n", p_v);
282 a_node_has_been_fused =
true;
286 the_interval_graph_has_been_modified |= a_node_has_been_fused;
287 }
while (a_node_has_been_fused);
294 the_interval_graph_has_been_modified
298 return the_interval_graph_has_been_modified;
320 hash_put(control_to_interval_node, (
char *) c, (
char *) interval);
323 interval = (
vertex)
hash_get(control_to_interval_node, (
char *) c);
341 pips_debug(5,
"Control entry node %p:\n", entry_node);
346 control_to_interval_node);
347 pips_debug(6,
"\tControl %p -> interval %p\n", c, interval);
349 bool interval_already_in_predecessors =
false;
350 vertex vertex_predecessor =
353 control_to_interval_node);
358 interval_already_in_predecessors =
true;
362 if (! interval_already_in_predecessors) {
368 pips_debug(7,
"\t\tControl predecessor %p -> interval %p\n",
369 p, vertex_predecessor);
371 }, entry_node, blocs);
388 pips_debug(6,
"Interval %p with controls ", interval);
417 return exit_controls;
452 pips_debug(6,
"New unstructured %p: new_entry_node = %p, new_exit_node = %p\n",
453 new_unstructured, new_entry_node, new_exit_node);
470 new_controls =
CONS(
CONTROL, new_exit_node, new_controls);
534 pips_debug(6,
"\nNodes from new_entry_node: ");
536 pips_debug(6,
"\nNodes from new_exit_node: ");
545 pips_assert(
"Control should be consistent from entry_node)...",
548 pips_assert(
"new_exit_node cannot have a successor.",
574 debug_on(
"RECURSIVE_DECOMPOSITION_DEBUG_LEVEL");
582 pips_debug(3,
"Entering with unstructured %p (%p, %p)\n",
583 u, entry_node, exit_node);
604 interval_entry != exit_node
653 pips_assert(
"Unstructured should be consistent here...",
static void node(FILE *out, string name)
Build for module name a node and link to its successors.
void free_vertex(vertex p)
vertex make_vertex(vertex_label a1, list a2)
interval_vertex_label make_interval_vertex_label(list a)
unstructured make_unstructured(control a1, control a2)
bool unstructured_consistent_p(unstructured p)
instruction make_instruction(enum instruction_utype tag, void *val)
bool control_consistent_p(control p)
control make_control(statement a1, list a2, list a3)
struct _newgen_struct_vertex_ * vertex
void gen_full_free_list(list l)
#define vertex_vertex_label(x)
#define SUCCESSOR(x)
SUCCESSOR.
#define graph_vertices(x)
statement instruction_to_statement(instruction)
Build a statement from a give instruction.
void unlink_2_control_nodes(control source, control target)
Remove all edged between 2 control nodes.
void display_linked_control_nodes(control c)
Display all the control nodes reached or reachable from c for debugging purpose.
void display_address_of_control_nodes(list cs)
Display the adresses a list of control nodes.
void link_2_control_nodes(control source, control target)
Add an edge between 2 control nodes.
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.
void check_control_coherency(control c)
Test the coherency of a control node network from a control node.
#define CONTROL_MAP(ctl, code, c, list)
Macro to walk through all the controls reachable from a given control node of an unstructured.
void gen_remove(list *cpp, const void *o)
remove all occurences of item o from list *cpp, which is thus modified.
void gen_list_and(list *a, const list b)
Compute A = A inter B: complexity in O(n2)
#define NIL
The empty list (nil in Lisp)
list gen_copy_seq(list l)
Copy a list structure.
size_t gen_length(const list l)
void gen_list_and_not(list *a, const list b)
Compute A = A inter non B:
#define CONS(_t_, _i_, _l_)
List element cell constructor (insert an element at the beginning of a list)
list gen_nconc(list cp1, list cp2)
physically concatenates CP1 and CP2 but do not duplicates the elements
#define CAR(pcons)
Get the value of the first element of a list.
void gen_free_list(list l)
free the spine of the list
bool gen_in_list_p(const void *vo, const list lx)
tell whether vo belongs to lx
#define CDR(pcons)
Get the list less its first element.
#define MAPL(_map_list_cp, _code, _l)
Apply some code on the addresses of all the elements of a list.
#define MAP(_map_CASTER, _map_item, _map_code, _map_list)
Apply/map an instruction block on all the elements of a list (old fashioned)
hash_table hash_table_make(hash_key_type key_type, size_t size)
void * hash_get(const hash_table htp, const void *key)
this function retrieves in the hash table pointed to by htp the couple whose key is equal to key.
void hash_put(hash_table htp, const void *key, const void *val)
This functions stores a couple (key,val) in the hash table pointed to by htp.
void hash_table_free(hash_table htp)
this function deletes a hash table that is no longer useful.
bool hash_defined_p(const hash_table htp, const void *key)
true if key has e value in htp.
interval_vertex_label arc_label
Since the arc are not used, just put a dummy type for arc_label.
static bool remove_interval_predecessor(vertex interval, vertex pred)
Remove all the instances of a predecessor pred of an interval.
static void remove_interval_predecessors(vertex interval)
Remove all the predecessors of an interval:
static vertex create_or_get_an_interval_node(control c, graph intervals, hash_table control_to_interval_node)
Get the interval node of a control or create it if it does not exist and add it to the interval graph...
static void hierarchize_control_list(vertex interval, list controls, control exit_node)
Put all the controls in their own unstructured to hierarchize the graph and link the unstructured to ...
static list interval_exit_nodes(vertex interval, control exit_node)
Return the list of control nodes exiting an interval.
static void __attribute__((unused))
Add the interval from (node, intervals) to interval graph intervals and update selected_nodes accordi...
#define predecessor_vertex
interval_vertex_label vertex_label
Instantiation of the interval graph:
static void display_interval_graph(graph intervals)
void control_graph_recursive_decomposition(unstructured u)
Use an interval graph partitionning method to recursively decompose the control graph.
static bool interval_graph(graph intervals)
Build an interval graph from an older interval graph and put it in the older one.
static graph control_graph_to_interval_graph_format(control entry_node)
Duplicate the control graph in a format suitable to deal with intervals later.
static void add_node_to_interval(graph intervals, vertex interval, vertex node)
Add an interval node to an interval and remove the node.
#define vertex_predecessors
#define interval_vertex_label_controls(x)
#define interval_vertex_label_undefined
#define pips_debug
these macros use the GNU extensions that allow variadic macros, including with an empty list.
#define pips_assert(what, predicate)
common macros, two flavors depending on NDEBUG
bool set_belong_p(const set, const void *)
set set_add_element(set, const set, const void *)
#define make_nop_statement
An alias for make_empty_block_statement.
#define unstructured_control
After the modification in Newgen: unstructured = entry:control x exit:control we have create a macro ...
#define control_undefined
#define control_predecessors(x)
#define CONTROL(x)
CONTROL.
@ is_instruction_unstructured
#define control_successors(x)
#define unstructured_exit(x)
#define control_statement(x)
FI: I do not understand why the type is duplicated at the set level.
The structure used to build lists in NewGen.