PIPS
|
#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "sc.h"
#include "polyedre.h"
#include "union.h"
#include "matrice.h"
#include "matrix.h"
#include "ri.h"
#include "constants.h"
#include "ri-util.h"
#include "misc.h"
#include "complexity_ri.h"
#include "database.h"
#include "graph.h"
#include "dg.h"
#include "paf_ri.h"
#include "parser_private.h"
#include "property.h"
#include "reduction.h"
#include "text.h"
#include "text-util.h"
#include "tiling.h"
#include "pipsdbm.h"
#include "resources.h"
#include "static_controlize.h"
#include "paf-util.h"
#include "pip.h"
#include "array_dfg.h"
#include "reindexing.h"
Go to the source code of this file.
Macros | |
#define | FIRST 1 |
Name : single_assign.c Package : reindexing Author : Alexis Platonoff Date : febuary 1994 Historic : More... | |
#define | SECOND 2 |
#define | THIRD 3 |
Typedefs | |
typedef dfg_vertex_label | vertex_label |
Local defines. More... | |
typedef dfg_arc_label | arc_label |
Functions | |
void | rhs_subs_in_ins (instruction ins, reference r1, reference r2) |
========================================================================= More... | |
vertex | my_dfg_in_vertex_list (list l, vertex v) |
================================================================= More... | |
graph | my_dfg_reverse_graph (graph g) |
====================================================================== More... | |
entity | create_entity (string name, variable v) |
========================================================================= More... | |
list | dims_of_nest (int n) |
========================================================================= More... | |
reference | build_new_ref (int kind, int n, list subscripts, reference old_r) |
========================================================================= More... | |
void | lhs_subs_in_ins (instruction ins, string SA, int n, list subscripts) |
========================================================================= More... | |
list | references_of_expression (expression exp) |
========================================================================= More... | |
list | get_rhs_of_instruction (instruction ins) |
========================================================================= More... | |
list | build_associate_temp (list lr) |
========================================================================= More... | |
list | build_successors_with_rhs (list ls, reference r) |
========================================================================= More... | |
int | count_dataflows_on_ref (list ls, reference r, dataflow *df, int *m) |
========================================================================= More... | |
list | dataflows_on_ref (successor suc, reference r) |
========================================================================= More... | |
void | ref_subs_in_exp (expression exp, reference r1, reference r2) |
========================================================================= More... | |
expression | predicate_to_expression (predicate pred) |
========================================================================= More... | |
void | add_test (statement s, predicate cond, reference lhs, reference rhs, int how) |
========================================================================= More... | |
void | sa_print_ins (FILE *fp, instruction i) |
========================================================================= More... | |
bool | full_predicate_p (predicate p) |
========================================================================= More... | |
void | sa_do_it (graph the_dfg) |
========================================================================= More... | |
void | single_assign (char *mod_name) |
========================================================================= More... | |
Variables | |
static int | tc |
Internal variables More... | |
#define FIRST 1 |
Name : single_assign.c Package : reindexing Author : Alexis Platonoff Date : febuary 1994 Historic :
Documents: Comments : This file contains the functions for the transformation of a program to a single assignment form. Ansi includes
Newgen includes
C3 includes
Pips includes
Macro functions
Definition at line 90 of file single_assign.c.
#define SECOND 2 |
Definition at line 91 of file single_assign.c.
#define THIRD 3 |
Definition at line 92 of file single_assign.c.
typedef dfg_arc_label arc_label |
Definition at line 101 of file single_assign.c.
typedef dfg_vertex_label vertex_label |
Local defines.
Definition at line 100 of file single_assign.c.
=========================================================================
We construct the statement "lhs = rhs"
Then, we find where to put it...
This means that "bl" is empty
... and how.
This means that "bl" has only one instruction
bad value
Definition at line 736 of file single_assign.c.
References ASSIGN_OPERATOR_NAME, CAR, CDR, CONS, ENDP, entity_domain, entity_empty_label(), EXPRESSION, FIRST, gen_find_tabulated(), instruction_block, instruction_tag, instruction_test, is_instruction_block, is_instruction_call, is_instruction_test, is_syntax_reference, make_call(), make_empty_statement, make_entity_fullname(), make_expression(), make_instruction(), make_statement(), make_syntax(), make_test(), NIL, normalized_undefined, pips_internal_error, POP, predicate_to_expression(), SECOND, STATEMENT, statement_instruction, STATEMENT_NUMBER_UNDEFINED, STATEMENT_ORDERING_UNDEFINED, statement_undefined, string_undefined, test_false, THIRD, and TOP_LEVEL_MODULE_NAME.
Referenced by sa_do_it().
=========================================================================
Definition at line 477 of file single_assign.c.
References build_new_ref(), CAR, CONS, ENDP, gen_nconc(), IS_TEMP, NIL, POP, REFERENCE, and tc.
Referenced by sa_do_it().
=========================================================================
we duplicate this list
Definition at line 301 of file single_assign.c.
References basic_of_reference(), concatenate(), create_entity(), dims_of_nest(), entity_domain, entity_local_name(), entity_undefined, fprint_list_of_exp(), fprintf(), gen_find_tabulated(), get_debug_level(), IS_NEW_ARRAY, IS_TEMP, make_reference(), make_variable(), malloc(), MODULE_SEP_STRING, NIL, num, pips_internal_error, SA_MODULE_NAME, SAI, SAT, and strdup().
Referenced by build_associate_temp(), lhs_subs_in_ins(), and sa_do_it().
=========================================================================
true equality, not on pointers
Definition at line 504 of file single_assign.c.
References CAR, CONS, DATAFLOW, dataflow_reference, dfg_arc_label_dataflows, ENDP, gen_nconc(), NIL, POP, reference_equal_p(), SUCCESSOR, and successor_arc_label.
=========================================================================
Definition at line 537 of file single_assign.c.
References CAR, count, DATAFLOW, dataflow_reference, dataflow_undefined, dfg_arc_label_dataflows, dfg_vertex_label_statement, ENDP, fprint_dataflow(), fprintf(), get_debug_level(), POP, reference_equal_p(), reference_to_string(), SUCCESSOR, successor_arc_label, successor_vertex, and vertex_vertex_label.
Referenced by sa_do_it().
=========================================================================
Definition at line 244 of file single_assign.c.
References is_storage_rom, is_type_variable, is_value_unknown, make_entity, make_storage(), make_type(), make_value(), and UU.
Referenced by build_new_ref(), and my_build_new_ref().
=========================================================================
Definition at line 589 of file single_assign.c.
References CAR, CONS, DATAFLOW, dataflow_reference, dfg_arc_label_dataflows, ENDP, gen_nconc(), NIL, POP, reference_equal_p(), and successor_arc_label.
Referenced by sa_do_it().
=========================================================================
Definition at line 262 of file single_assign.c.
References adg_number_to_statement(), CAR, CONS, DIMENSION, ENDP, gen_nconc(), get_stco_from_current_map(), LOOP, loop_range, make_dimension(), NIL, POP, range_lower, range_upper, and static_control_loops.
Referenced by build_new_ref(), and my_build_new_ref().
=========================================================================
Definition at line 911 of file single_assign.c.
References Ssysteme::egalites, Ssysteme::inegalites, predicate_system, and predicate_undefined.
Referenced by sa_do_it().
list get_rhs_of_instruction | ( | instruction | ins | ) |
=========================================================================
There are two args: lhs = rhs, we want the references of the rhs
Definition at line 436 of file single_assign.c.
References call_arguments, call_function, CAR, CDR, ENTITY_ASSIGN_P, EXPRESSION, gen_length(), gen_nconc(), instruction_call, instruction_tag, is_instruction_block, is_instruction_call, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, NIL, pips_internal_error, and references_of_expression().
Referenced by build_first_comb(), and sa_do_it().
void lhs_subs_in_ins | ( | instruction | ins, |
string | SA, | ||
int | n, | ||
list | subscripts | ||
) |
=========================================================================
Definition at line 358 of file single_assign.c.
References build_new_ref(), call_arguments, call_function, CAR, entities_to_expressions(), ENTITY_ASSIGN_P, EXPRESSION, expression_syntax, fprintf(), get_debug_level(), instruction_call, instruction_tag, is_instruction_block, is_instruction_call, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, IS_NEW_ARRAY, pips_internal_error, reference_to_string(), syntax_reference, and syntax_reference_p.
Referenced by sa_do_it().
=================================================================
vertex my_dfg_in_vertex_list( (list) l, (vertex) v ) Input : A list l of vertices. A vertex v of a dataflow graph. Returns vertex_undefined if v is not in list l. Returns v' that has the same statement_ordering than v.
AC 93/10/19
Definition at line 146 of file single_assign.c.
References CAR, dfg_vertex_label_statement, ENDP, POP, VERTEX, vertex_undefined, and vertex_vertex_label.
Referenced by my_dfg_reverse_graph().
======================================================================
graph my_dfg_reverse_graph( (graph) g ) This function is used to reverse Pips's graph in order to have all possible sources directly (Feautrier's dependance graph).
AC 93/10/19
Definition at line 176 of file single_assign.c.
References ADD_ELEMENT_TO_LIST, CAR, graph_undefined, graph_vertices, make_graph(), make_successor(), make_vertex(), MAPL, my_dfg_in_vertex_list(), NIL, SUCCESSOR, successor_arc_label, successor_vertex, verlist, VERTEX, vertex_successors, vertex_undefined, and vertex_vertex_label.
Referenced by re_do_it(), and sa_do_it().
expression predicate_to_expression | ( | predicate | pred | ) |
=========================================================================
Definition at line 640 of file single_assign.c.
References AND_OPERATOR_NAME, Ssysteme::egalites, entity_domain, entity_undefined, EQUAL_OPERATOR_NAME, exp, expression_to_string(), expression_undefined, fprint_pred(), fprintf(), gen_find_tabulated(), get_debug_level(), ifdebug, Ssysteme::inegalites, int_to_expression(), LESS_OR_EQUAL_OPERATOR_NAME, make_entity_fullname(), make_vecteur_expression(), MakeBinaryCall(), pips_internal_error, predicate_system, pu_vect_fprint(), Scontrainte::succ, TOP_LEVEL_MODULE_NAME, and Scontrainte::vecteur.
Referenced by add_test().
void ref_subs_in_exp | ( | expression | exp, |
reference | r1, | ||
reference | r2 | ||
) |
=========================================================================
Definition at line 612 of file single_assign.c.
References call_arguments, CAR, ENDP, exp, EXPRESSION, expression_syntax, is_syntax_call, is_syntax_range, is_syntax_reference, pips_internal_error, POP, reference_equal_p(), syntax_call, syntax_reference, and syntax_tag.
Referenced by rhs_subs_in_ins().
list references_of_expression | ( | expression | exp | ) |
=========================================================================
Definition at line 404 of file single_assign.c.
References call_arguments, CAR, CONS, ENDP, exp, EXPRESSION, expression_syntax, gen_nconc(), is_syntax_call, is_syntax_range, is_syntax_reference, NIL, pips_internal_error, POP, REFERENCE, syntax_call, syntax_reference, and syntax_tag.
Referenced by get_rhs_of_instruction().
void rhs_subs_in_ins | ( | instruction | ins, |
reference | r1, | ||
reference | r2 | ||
) |
=========================================================================
Definition at line 110 of file single_assign.c.
References call_arguments, call_function, CAR, CDR, ENTITY_ASSIGN_P, EXPRESSION, instruction_call, instruction_tag, is_instruction_block, is_instruction_call, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, pips_internal_error, and ref_subs_in_exp().
Referenced by build_third_comb(), build_third_subcomb(), and sa_do_it().
void sa_do_it | ( | graph | the_dfg | ) |
=========================================================================
let's have a reverse DFG, i.e. the "successors" of an instruction i are the instructions that may write the values used by i;
loop over the vertices of the DFG
cv is the current vertex, cn is its number, cs is the associate statement
cls is the list of successors of cv
change the lhs of cs to a new array indexed by the englobing loop indices: SAIn(i1,...ip) (i1,...,ip) are the indices of the englobing loops of cs
construct the list of rhs
construct the associated list of temporaries
in the code, replace ci by a block new_i containing ci
We create a new instruction with an empty block of instructions
Then, we put the instruction "ci" in the block.
loop over the list of rhs
crhs is the current ref and ct is the associate temp
We count the number of dataflows in "cls" that contains "crhs", and we then consider three cases: 0 dataflow, 1 dataflow, 2 or more dataflows.
Nothing is changed concerning this rhs
pred is the cond of df, L is the transformation of df
change in ci the occurrences of crhs by SAIm[L]
number of tests currently added
pred is the cond of df, L is the transformation of df
change in ci the occurrences of crhs by ct;
First test
"if(pred) ct = SAIm[L(i1,...,ip)]", just before ci in cs
"else if(pred) ct = SAIm[L(i1,...,ip)]", just before ci in cs
"else ct = crhs", just before ci in cs
Definition at line 933 of file single_assign.c.
References add_test(), adg_number_to_statement(), assignment_statement_p(), build_associate_temp(), build_new_ref(), CAR, CONS, count_dataflows_on_ref(), DATAFLOW, dataflow_governing_pred, dataflow_transformation, dataflows_on_ref(), dfg_vertex_label_statement, ENDP, entity_empty_label(), FIRST, fprint_dfg(), fprintf(), full_predicate_p(), get_debug_level(), get_rhs_of_instruction(), get_stco_from_current_map(), graph_vertices, instruction_block, instruction_tag, is_instruction_block, IS_NEW_ARRAY, lhs_subs_in_ins(), make_instruction_block(), make_statement(), my_dfg_reverse_graph(), NIL, POP, predicate_undefined, REFERENCE, reference_to_string(), rhs_subs_in_ins(), sa_print_ins(), SAI, SECOND, STATEMENT, statement_comments, statement_instruction, statement_label, statement_number, STATEMENT_NUMBER_UNDEFINED, statement_ordering, STATEMENT_ORDERING_UNDEFINED, static_control_to_indices(), string_undefined, SUCCESSOR, successor_vertex, the_dfg, THIRD, VERTEX, vertex_successors, and vertex_vertex_label.
Referenced by single_assign().
void sa_print_ins | ( | FILE * | fp, |
instruction | i | ||
) |
=========================================================================
Definition at line 848 of file single_assign.c.
References call_arguments, call_function, CAR, ENDP, entity_local_name(), EXPRESSION, expression_to_string(), fprintf(), instruction_block, instruction_call, instruction_goto, instruction_loop, instruction_tag, instruction_test, is_instruction_block, is_instruction_call, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, loop_body, loop_index, loop_range, pips_internal_error, POP, range_increment, range_lower, range_upper, STATEMENT, statement_instruction, statement_ordering, statement_undefined, test_condition, test_false, and test_true.
Referenced by build_first_comb(), build_third_comb(), fprint_list_of_ins(), fprint_loop(), fprint_mytest(), print_detailed_ins(), re_do_it(), and sa_do_it().
void single_assign | ( | char* | mod_name | ) |
=========================================================================
Initialize debugging functions
We get the required data: module entity, code, static_control, dataflow graph.
The DFG
The temporaries counter
Definition at line 1154 of file single_assign.c.
References adg_pure_dfg(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, fprint_dfg(), get_current_module_entity(), get_debug_level(), get_stco_from_current_map(), local_name_to_top_level_entity(), mod_stat, pips_internal_error, reset_current_module_entity(), reset_current_stco_map(), sa_do_it(), set_current_module_entity(), set_current_stco_map(), static_control_undefined, static_control_yes, strdup(), STS, tc, the_dfg, and user_log().
|
static |
Internal variables
Global variables
Definition at line 97 of file single_assign.c.
Referenced by build_associate_temp(), and single_assign().