PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "linear.h"
#include "genC.h"
#include "ri.h"
#include "interval_graph.h"
#include "graph.h"
#include "ri-util.h"
#include "misc.h"
#include "control.h"
Go to the source code of this file.
Macros | |
#define | vertex_predecessors vertex_successors |
#define | predecessor_vertex successor_vertex |
#define | make_predecessor make_successor |
#define | free_predecessor free_successor |
#define | PREDECESSOR SUCCESSOR |
#define | PREDECESSOR_TYPE SUCCESSOR_TYPE |
#define | PREDECESSOR_NEWGEN_DOMAIN (-1) |
#define | SUCCESSOR_NEWGEN_DOMAIN (-1) |
#define | gen_SUCCESSOR_cons gen_cons |
#define | gen_PREDECESSOR_cons gen_cons |
#define | gen_successor_cons gen_cons |
#define | gen_predecessor_cons gen_cons |
Typedefs | |
typedef interval_vertex_label | vertex_label |
Instantiation of the interval graph: More... | |
typedef interval_vertex_label | arc_label |
Since the arc are not used, just put a dummy type for arc_label. More... | |
typedef successor | predecessor |
Functions | |
static void | remove_interval_predecessors (vertex interval) |
Remove all the predecessors of an interval: More... | |
static bool | remove_interval_predecessor (vertex interval, vertex pred) |
Remove all the instances of a predecessor pred of an interval. More... | |
static void | add_node_to_interval (graph intervals, vertex interval, vertex node) |
Add an interval node to an interval and remove the node. More... | |
static void | __attribute__ ((unused)) |
Add the interval from (node, intervals) to interval graph intervals and update selected_nodes accordingly if : More... | |
static void | display_interval_graph (graph intervals) |
static bool | interval_graph (graph intervals) |
Build an interval graph from an older interval graph and put it in the older one. More... | |
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. More... | |
static graph | control_graph_to_interval_graph_format (control entry_node) |
Duplicate the control graph in a format suitable to deal with intervals later. More... | |
static list | interval_exit_nodes (vertex interval, control exit_node) |
Return the list of control nodes exiting an interval. More... | |
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 the outer unstructured. More... | |
void | control_graph_recursive_decomposition (unstructured u) |
Use an interval graph partitionning method to recursively decompose the control graph. More... | |
#define free_predecessor free_successor |
Definition at line 70 of file hierarchize.c.
#define gen_PREDECESSOR_cons gen_cons |
Definition at line 79 of file hierarchize.c.
#define gen_predecessor_cons gen_cons |
Definition at line 81 of file hierarchize.c.
#define gen_SUCCESSOR_cons gen_cons |
Definition at line 78 of file hierarchize.c.
#define gen_successor_cons gen_cons |
Definition at line 80 of file hierarchize.c.
#define make_predecessor make_successor |
Definition at line 69 of file hierarchize.c.
#define PREDECESSOR SUCCESSOR |
Definition at line 71 of file hierarchize.c.
#define PREDECESSOR_NEWGEN_DOMAIN (-1) |
Definition at line 74 of file hierarchize.c.
#define PREDECESSOR_TYPE SUCCESSOR_TYPE |
Definition at line 72 of file hierarchize.c.
#define predecessor_vertex successor_vertex |
Definition at line 68 of file hierarchize.c.
#define SUCCESSOR_NEWGEN_DOMAIN (-1) |
Definition at line 76 of file hierarchize.c.
#define vertex_predecessors vertex_successors |
Definition at line 67 of file hierarchize.c.
typedef interval_vertex_label arc_label |
Since the arc are not used, just put a dummy type for arc_label.
It will be initialized to interval_vertex_label_undefined anyway:
Definition at line 51 of file hierarchize.c.
typedef successor predecessor |
Definition at line 82 of file hierarchize.c.
typedef interval_vertex_label vertex_label |
Instantiation of the interval graph:
Definition at line 48 of file hierarchize.c.
|
static |
Add the interval from (node, intervals) to interval graph intervals and update selected_nodes accordingly if :
Since we modify in place the current interval graph, do not perturbate the do/MAP loop on intervals below. Just keep the list of interval to be removed later.
The new interval will be the node itself, begin of the new interval. Just select it and keep it:
Find a candidate through all the intervals:
Test that the candidate has all its predecessors in the interval we are building:
Ok, this node belong to the new interval:
add_node_to_interval(candidate, node, intervals, selected_nodes, &intervals_to_be_removed);
Look for the next appliant:
Definition at line 181 of file hierarchize.c.
References gen_full_free_list(), graph_vertices, MAP, NIL, node(), PREDECESSOR, predecessor_vertex, set_add_element(), set_belong_p(), VERTEX, and vertex_predecessors.
Add an interval node to an interval and remove the node.
Replace every allusion to node by interval in the interval graph.
The main issue is that the interval graph must remain a graph, that is it cannot have more than one edge from a vertex to another one:
There is at least an interval that must appear ONLY ONCE in the predecessors. Thus it is easier to delete any reference an create an unique instance of it:
I guess there is memory leak here...
Add the lacking interval in the predecessors:
Concatenate the control nodes to the interval and preserve the order to keep the entry node first:
Protect the control nodes from later deletion (useless to free the list since it is still lived via gen_nconc. Thanks to Purify... :-)
Detach the node:
Clean up the useless old node:
Definition at line 128 of file hierarchize.c.
References CAR, CONS, free_vertex(), gen_list_and_not(), gen_nconc(), gen_remove(), graph_vertices, interval_vertex_label_controls, interval_vertex_label_undefined, make_predecessor, MAP, MAPL, NIL, node(), PREDECESSOR, predecessor_vertex, remove_interval_predecessors(), VERTEX, vertex_predecessors, and vertex_vertex_label.
Referenced by interval_graph().
void control_graph_recursive_decomposition | ( | unstructured | u | ) |
Use an interval graph partitionning method to recursively decompose the control graph.
Have a look to paper "A Control-Flow Normalization Algorithm and Its Complexity" (1994) from Zahira Ammarguellat for a bibliography of the domain.
An interval graph is represented by a graph with interval_vertex_label decorations embedding control nodes. The first interval of the graph is the entry interval of the interval graph and the first control node of an interval is the entry control node of the interval:
The seed interval graph is indeed the control graph itself:
Apply recursively interval graph decomposition:
For all intervals of the graph:
If this interval has at most one exit it should be put in its own unstructured:
Useless to restructure the exit node...
If a single node, only useful if there is a loop inside (in order to detect these loops, hierarchize_control_list() is called before interval_graph() but then we need to add more guards...):
If an interval has at most one exit, the underlaying control graph can be hierachized by an unstructured.
Put all the controls in their own unstructured to hierarchize the graph:
Skip the entry interval
Stop if the interval graph does no longer change : it is only one node or an irreductible graph:
Construct the interval graph from the previous one:
Do not forget to detach control nodes from interval before sweeping:
Definition at line 563 of file hierarchize.c.
References CAR, CDR, CONTROL, control_graph_to_interval_graph_format(), control_successors, control_undefined, debug_off, debug_on, display_interval_graph(), display_linked_control_nodes(), free_graph(), gen_free_list(), gen_length(), graph_vertices, hierarchize_control_list(), ifdebug, interval_exit_nodes(), interval_graph(), interval_vertex_label_controls, MAP, NIL, pips_assert, pips_debug, unstructured_consistent_p(), unstructured_control, unstructured_exit, VERTEX, and vertex_vertex_label.
Referenced by unspaghettify_or_restructure_statement().
Duplicate the control graph in a format suitable to deal with intervals later.
The interval graph format is the predecessor control graph in fact.
Add the predeccessor only if it is not already in the predecessor list:
Definition at line 335 of file hierarchize.c.
References CAR, CONS, CONTROL, CONTROL_MAP, control_predecessors, create_or_get_an_interval_node(), gen_free_list(), hash_pointer, hash_table_free(), hash_table_make(), interval_vertex_label_undefined, make_graph(), make_predecessor, MAP, MAPL, NIL, pips_debug, PREDECESSOR, predecessor_vertex, and vertex_predecessors.
Referenced by control_graph_recursive_decomposition().
|
static |
Get the interval node of a control or create it if it does not exist and add it to the interval graph.
This control has never been seen before: allocate the peering interval node with no successor:
Use gen_nconc since the entry interval must be the first one:
Definition at line 305 of file hierarchize.c.
References CONS, CONTROL, gen_nconc(), graph_vertices, hash_defined_p(), hash_get(), hash_put(), make_interval_vertex_label(), make_vertex(), NIL, and VERTEX.
Referenced by control_graph_to_interval_graph_format().
|
static |
Definition at line 229 of file hierarchize.c.
References display_address_of_control_nodes(), graph_vertices, interval_vertex_label_controls, MAP, node(), pips_debug, predecessor_vertex, SUCCESSOR, VERTEX, vertex_predecessors, and vertex_vertex_label.
Referenced by control_graph_recursive_decomposition().
Put all the controls in their own unstructured to hierarchize the graph and link the unstructured to the outer unstructured.
The exit_node is the exit control node, either control_undefined if it there is no exit : it is a true endless loop (assume it is not the exit node).
The list of all reachable controls of the new unstructured:
Create the new control nodes with the new unstructured:
Now the hard work: replace carefully the old control nodes by new one in the spaghetti plate...
First clone the graph structure:
Add the new_exit_node in the new_controls list:
Correct the nodes to reflect the new nodes:
Detach the new unstructured from the old one:
If there was a goto from exit_node to entry_node, there is an artefact one between new_exit_node and new_entry_node. Remove it:
Detach the old unstructured from the new one:
Unlink an eventual loop around entry_node that has been captured anyway in the new unstructured:
When a single node loop has been hierarchize, this link already exist
Now the exit_node becomes a successor of the entry_node:
Update the control list of the interval that owns only entry_node after hierarchization:
print_statement(control_statement(entry_node));
Definition at line 428 of file hierarchize.c.
References CAR, check_control_coherency(), CONS, CONTROL, control_consistent_p(), control_list_patch(), control_predecessors, control_statement, control_successors, control_undefined, display_address_of_control_nodes(), display_linked_control_nodes(), gen_copy_seq(), gen_free_list(), gen_list_and(), gen_list_and_not(), ifdebug, instruction_to_statement(), interval_vertex_label_controls, is_instruction_unstructured, link_2_control_nodes(), make_control(), make_instruction(), make_nop_statement, make_unstructured(), MAP, NIL, pips_assert, pips_debug, unlink_2_control_nodes(), and vertex_vertex_label.
Referenced by control_graph_recursive_decomposition().
Return the list of control nodes exiting an interval.
Note that if a node of the control list is in fact the exit_node of an unstructured, it is really an exit node at an upper level.
A successor that is not in the interval is an exit node... Add it to the exit nodes list if not already in it:
The current exit_node of the unstructured is clearly an exit node even if it does not have any successor:
Definition at line 384 of file hierarchize.c.
References CONS, CONTROL, control_successors, display_address_of_control_nodes(), gen_in_list_p(), ifdebug, interval_vertex_label_controls, MAP, NIL, pips_debug, and vertex_vertex_label.
Referenced by control_graph_recursive_decomposition().
Build an interval graph from an older interval graph and put it in the older one.
An interval is a subgraph whose header dominate all its nodes. It can be seen as a natural loop plus an acyclic structure that dangles from the nodes of that loop.
Algorithm use the T1/T2 analysis that can be found from pages 665 to 670 of:
@book{dragon-1986, author = {Alfred V. Aho and Ravi Sethi and Jeffrey D. Ullman}, title = {Compilers Principles, Techniques and Tools}, publisher = {Addison-Wesley Publishing Company}, year = 1986 }
It looks like it is from Hecht and Ullman according to Zahira Ammarguellat.
Apply the T2 transformation, that is equivalent to my fuse_sequences_in_unstructured elsewhere. Just use a less optimized algorithm here:
The entry interval is kept untouched
Fuse a node with its only predecessor:
Let's go to find a new interval to fuse:
T1 transformation on page 668: Remove the eventual arcs to itself:
If a loop around a interval node is removed, it considered as a graph modification:
Definition at line 261 of file hierarchize.c.
References add_node_to_interval(), CAR, gen_length(), graph_vertices, MAP, node(), pips_debug, PREDECESSOR, predecessor_vertex, remove_interval_predecessor(), VERTEX, and vertex_predecessors.
Referenced by control_graph_recursive_decomposition().
Remove all the instances of a predecessor pred of an interval.
Return true if pred was really in the predecessor list:
Detach the predecessor vertex:
And now remove the predecessors than own pred:
Definition at line 103 of file hierarchize.c.
References CONS, free_predecessor, gen_remove(), MAP, NIL, PREDECESSOR, predecessor_vertex, vertex_predecessors, and vertex_undefined.
Referenced by interval_graph().
|
static |
Remove all the predecessors of an interval:
Detach the predecessor vertex:
And remove all the predecessors:
Definition at line 87 of file hierarchize.c.
References gen_full_free_list(), MAP, NIL, PREDECESSOR, predecessor_vertex, vertex_predecessors, and vertex_undefined.
Referenced by add_node_to_interval().