PIPS
|
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "ri-util.h"
#include "control.h"
#include "misc.h"
#include "pipsdbm.h"
#include "resources.h"
Go to the source code of this file.
Data Structures | |
struct | guesser_param |
parameter of effect guesser More... | |
Functions | |
static bool | condition_expression_to_final_bound (expression cond, entity li, bool *is_upper_p, expression *pub) |
Some passes to transform for-loops into do-loops or while-loops that may be easier to analyze by PIPS. More... | |
static bool | incrementation_expression_to_increment (expression incr, entity li, bool *is_increasing_p, expression *pincrement) |
static bool | guess_write_effect_on_entity_walker (call c, guesser_param *p) |
Try hard to guess wether the call. More... | |
static bool | guess_write_effect_on_entity_stmt_walker (statement st, guesser_param *p) |
classical statement walker, gen_recurse does not dive into statement declarations More... | |
static bool | guess_write_effect_on_entity (void *exp, entity loop_index) |
call guess_write_effect_on_entity_walker on each call of More... | |
bool | guess_late_read_effect_on_entity (expression init, entity loop_index) |
Check comma expressions used for initialization. More... | |
static expression | guess_loop_increment_walker (expression e, entity loop_index, statement body) |
guess the increment of a loop the condition is: the increment must be a reference that is constant in the loop body More... | |
static expression | guess_loop_increment (expression incr, entity loop_index, statement body) |
iterate over More... | |
static expression | guess_loop_lower_bound (expression init, entity loop_index) |
iterate over the comma-separeted expression More... | |
static void | remove_expression_from_comma_list (expression comma_list, expression seed) |
given an expression More... | |
sequence | for_to_do_loop_conversion (forloop theloop, statement parent) |
Try to convert a C-like for-loop into a Fortran-like do-loop. More... | |
void | try_to_transform_a_for_loop_into_a_do_loop (forloop f) |
Try to to transform the C-like for-loops into Fortran-like do-loops. More... | |
bool | for_loop_to_do_loop (const string module_name) |
For-loop to do-loop transformation phase. More... | |
sequence | for_to_while_loop_conversion (expression init, expression cond, expression incr, statement body, extensions exts) |
Build a sequence with a while-loop from for-loop parameters. More... | |
void | transform_a_for_loop_into_a_while_loop (forloop f) |
Try to to transform the C-like for-loops into Fortran-like do-loops. More... | |
void | transform_a_for_loop_statement_into_a_while_loop (statement st) |
Same as above, but with no calls to ancestors. More... | |
bool | for_loop_to_while_loop (const string module_name) |
For-loop to while-loop transformation phase. More... | |
|
static |
Some passes to transform for-loops into do-loops or while-loops that may be easier to analyze by PIPS.
Test if the final value
li | of a for-loop is static. |
Depending on cond, the so-called upper bound may end up being a lower bound with a decreasing step loop.
pips_debug(5, "Begin with expression\n");
print_expression(cond);
}
Five operators are accepted
pips_debug(5, "Static final value found!\n"
"\tEnd with expression:\n");
print_expression(*pub);
Definition at line 57 of file for_to_do_or_while_loops.c.
References bool_to_string(), call_arguments, call_function, CAR, CDR, convert_bound_expression(), ENTITY_GREATER_OR_EQUAL_P, ENTITY_GREATER_THAN_P, ENTITY_LESS_OR_EQUAL_P, ENTITY_LESS_THAN_P, ENTITY_NON_EQUAL_P, EXPRESSION, expression_syntax, ifdebug, pips_debug, reference_variable, syntax_call, syntax_call_p, syntax_reference, and syntax_reference_p.
Referenced by for_to_do_loop_conversion().
For-loop to do-loop transformation phase.
This transformation transform for example a \begin{lstlisting} for (i = lb; i < ub; i += stride) body; \end{lstlisting} into a \begin{lstlisting}[language=fortran] do i = lb, ub - 1, stride body end do \end{lstlisting}
Now use pure local analysis on the code but we could imagine further use of semantics analysis some day...
Get the true ressource, not a copy, since we modify it in place.
We need to access to the instruction containing the current for-loops, so ask NewGen gen_recurse to keep this informations for us:
Iterate on all the for-loops:
Reorder the module, because some statements have been replaced.
Should have worked:
module_name | odule_name |
Definition at line 779 of file for_to_do_or_while_loops.c.
References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, forloop_domain, gen_recurse, gen_true(), module_name(), module_name_to_entity(), module_reorder(), module_statement, pips_assert, pips_debug, reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), statement_consistent_p(), and try_to_transform_a_for_loop_into_a_do_loop().
For-loop to while-loop transformation phase.
This transformation transforms a \begin{lstlisting} for (init; cond; update) body; \end{lstlisting} into a \begin{lstlisting} { init; while(cond) { body; update; } } \end{lstlisting}
Get the true ressource, not a copy, since we modify it in place.
We need to access to the instruction containing the current for-loops, so ask NewGen gen_recurse to keep this informations for us:
Iterate on all the for-loops:
Reorder the module, because some statements have been replaced.
Should have worked:
module_name | odule_name |
Definition at line 1001 of file for_to_do_or_while_loops.c.
References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, gen_recurse, gen_true(), module_name(), module_name_to_entity(), module_reorder(), module_statement, pips_assert, pips_debug, reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), statement_consistent_p(), statement_domain, and transform_a_for_loop_statement_into_a_while_loop().
Try to convert a C-like for-loop into a Fortran-like do-loop.
Assume to match what is done in the prettyprinter C_loop_range().
This does not filter scalar integers...
Consider only scalar integer variables as loop indices
&& type_depth(lit)==1
We got a candidate loop index and final bound, let's check the increment
We have found a do-loop compatible for-loop:
guess lower bound
try hard to reproduce statement content
theloop | heloop |
parent | arent |
Definition at line 614 of file for_to_do_or_while_loops.c.
References call_arguments, CAR, CDR, condition_expression_to_final_bound(), CONS, empty_comments, empty_extensions(), entity_empty_label(), entity_local_name(), entity_to_expression(), entity_type, EXPRESSION, expression_call(), expression_undefined_p, forloop_body, forloop_condition, forloop_increment, forloop_initialization, gen_append(), get_referenced_entities(), guess_late_read_effect_on_entity(), guess_loop_increment(), guess_loop_lower_bound(), guess_write_effect_on_entity(), incrementation_expression_to_increment(), init, insert_statement(), instruction_to_statement(), loop_index, make_execution_sequential(), make_instruction_call(), make_instruction_expression(), make_instruction_loop(), make_loop(), make_range(), make_sequence(), make_statement(), make_synchronization_none(), NIL, pips_user_warning, remove_expression_from_comma_list(), scalar_integer_type_p(), sequence_statements, sequence_undefined, SET_FOREACH, set_free(), set_intersection(), set_make(), set_pointer, STATEMENT, statement_comments, statement_declarations, statement_decls_text, statement_extensions, statement_label, statement_number, STATEMENT_NUMBER_UNDEFINED, statement_ordering, STATEMENT_ORDERING_UNDEFINED, and ultimate_type().
Referenced by controlize_forloop(), and try_to_transform_a_for_loop_into_a_do_loop().
sequence for_to_while_loop_conversion | ( | expression | init, |
expression | cond, | ||
expression | incr, | ||
statement | body, | ||
extensions | exts | ||
) |
Build a sequence with a while-loop from for-loop parameters.
The API is a little weird to comply with the controlizer implementation...
Build the loop body of the while with { body; incr_st; } :
Build the while(cond) { n_body } statement:
pips_debug(5, "Initialization statement:\n");
print_statement(init_st);
pips_debug(5, "Incrementation statement:\n");
print_statement(incr_st);
pips_debug(5, "New body statement with incrementation:\n");
print_statement(n_body);
pips_debug(5, "New whileloop statement:\n");
print_statement(wl_st);
}
init | nit |
cond | ond |
incr | ncr |
body | ody |
exts | xts |
Definition at line 826 of file for_to_do_or_while_loops.c.
References CONS, copy_extensions(), empty_extensions_p(), free_extensions(), init, make_expression_statement(), make_sequence(), make_statement_from_statement_varargs_list(), make_whileloop_statement(), NIL, pips_debug, sequence_undefined, STATEMENT, statement_extensions, and STATEMENT_NUMBER_UNDEFINED.
Referenced by controlize_forloop(), transform_a_for_loop_into_a_while_loop(), and transform_a_for_loop_statement_into_a_while_loop().
bool guess_late_read_effect_on_entity | ( | expression | init, |
entity | loop_index | ||
) |
Check comma expressions used for initialization.
Assuming loop_index is a potential do loop index, and init a comma expression, do we have subexpressions after the loop_index initialization that may use this index? If yes, the loop cannot be transformed into a DO loop, because this subexpression will be moved before the loop index initialization. Or the loop index initialization should be replicated before the loop.
Example (SPEC2006, milc):
for (i = parity==0x01?even_sites_on_node:0, s = &lattice[i]; i<(parity==0x02?even_sites_on_node:sites_on_node); i++, s++) {
s = &lattice[i] is going to be placed ahead of i's own initialization.
In other words, the loop can be changed in different ways:
init | nit |
loop_index | oop_index |
Definition at line 412 of file for_to_do_or_while_loops.c.
References call_arguments, call_function, ENTITY_COMMA_P, EXPRESSION, expression_call(), expression_call_p(), expression_to_reference_list(), f(), FOREACH, gen_free_list(), guess_write_effect_on_entity(), init, loop_index, NIL, REFERENCE, and reference_variable.
Referenced by for_to_do_loop_conversion().
|
static |
iterate over
incr,a | comma separated expression and checks for an (in|de)crement of |
loop_index | if |
loop_index | is written twice in |
incr,the | result is expression_undefined |
Definition at line 511 of file for_to_do_or_while_loops.c.
References call_arguments, call_function, CAR, CDR, ENTITY_COMMA_P, EXPRESSION, expression_call(), expression_call_p(), expression_undefined, expression_undefined_p, guess_loop_increment_walker(), guess_write_effect_on_entity(), and loop_index.
Referenced by for_to_do_loop_conversion().
|
static |
guess the increment of a loop the condition is: the increment must be a reference that is constant in the loop body
e | candidate expression |
loop_index | entity guessed as index |
body | loop body |
this one needs further processing
Definition at line 453 of file for_to_do_or_while_loops.c.
References call_arguments, call_function, CAR, CDR, ENTITY_ASSIGN_P, ENTITY_MINUS_C_P, ENTITY_MINUS_P, ENTITY_MINUS_UPDATE_P, ENTITY_PLUS_C_P, ENTITY_PLUS_P, ENTITY_PLUS_UPDATE_P, ENTITY_POST_DECREMENT_P, ENTITY_POST_INCREMENT_P, ENTITY_PRE_DECREMENT_P, ENTITY_PRE_INCREMENT_P, EXPRESSION, expression_call(), expression_call_p(), expression_reference(), expression_reference_p(), expression_undefined, guess_write_effect_on_entity(), loop_index, reference_variable, and same_entity_p().
Referenced by guess_loop_increment().
|
static |
iterate over the comma-separeted expression
init | and look for an initialization of |
loop_index |
Definition at line 545 of file for_to_do_or_while_loops.c.
References call_arguments, call_function, CAR, CDR, ENTITY_ASSIGN_P, ENTITY_COMMA_P, EXPRESSION, expression_call(), expression_call_p(), expression_reference(), expression_reference_p(), expression_undefined, expression_undefined_p, init, loop_index, reference_variable, and same_entity_p().
Referenced by for_to_do_loop_conversion().
call guess_write_effect_on_entity_walker on each call of
exp | in order to guess write effect on |
loop_index |
Definition at line 372 of file for_to_do_or_while_loops.c.
References call_domain, exp, gen_context_multi_recurse(), gen_null(), guess_write_effect_on_entity_stmt_walker(), guess_write_effect_on_entity_walker(), loop_index, statement_domain, and guesser_param::written.
Referenced by for_to_do_loop_conversion(), guess_late_read_effect_on_entity(), guess_loop_increment(), and guess_loop_increment_walker().
|
static |
classical statement walker, gen_recurse does not dive into statement declarations
Definition at line 357 of file for_to_do_or_while_loops.c.
References call_domain, ENTITY, entity_initial, FOREACH, gen_context_recurse, gen_null2(), guess_write_effect_on_entity_walker(), statement_declarations, and value_undefined_p.
Referenced by guess_write_effect_on_entity().
|
static |
Try hard to guess wether the call.
c | writes |
p | Note that it is just a guess and may be wwrong |
This function only exists because effects are not available in the controlizer moreover, no aliasing information is available, so the guess may be wrong
Definition at line 329 of file for_to_do_or_while_loops.c.
References call_arguments, call_function, CAR, ENTITY_ADDRESS_OF_P, ENTITY_ASSIGN_P, ENTITY_BITWISE_AND_UPDATE_P, ENTITY_BITWISE_OR_UPDATE_P, ENTITY_BITWISE_XOR_UPDATE_P, ENTITY_DIVIDE_UPDATE_P, ENTITY_LEFT_SHIFT_UPDATE_P, ENTITY_MINUS_UPDATE_P, ENTITY_MODULO_UPDATE_P, ENTITY_MULTIPLY_UPDATE_P, ENTITY_PLUS_UPDATE_P, ENTITY_POST_DECREMENT_P, ENTITY_POST_INCREMENT_P, ENTITY_PRE_DECREMENT_P, ENTITY_PRE_INCREMENT_P, ENTITY_RIGHT_SHIFT_UPDATE_P, EXPRESSION, expression_reference(), expression_reference_p(), gen_recurse_stop(), reference_variable, same_entity_p(), guesser_param::target, and guesser_param::written.
Referenced by guess_write_effect_on_entity(), and guess_write_effect_on_entity_stmt_walker().
|
static |
The expression should concern the loop index:
Look for i++ or ++i:
Look for i– or –i:
Look for stuff like "i += integer". Get the rhs:
This fails with floating point indices as found in industrial code and with symbolic increments as in "for(t=0.0; t<t_max; t += delta_t). Floating point indices should be taken into account. The iteration direction of the loop should be derived from the bound expression, using the comparison operator.
SG: we checked the no-write-effect-on-increment earlier, we can go on safely, but we will not know if the increment is positive or not, assume yes ?
Look for "i = i + v" (only for v positive here...) or "i = v + i":
SG: we checked the no-write-effect-on-increment earlier, we can go on safely, but we will not know if the increment is positive or not, assume yes ?
SG: i am duplicating code, next generation of phd will clean it
SG: we checked the no-write-effect-on-increment earlier, we can go on safely, but we will not know if the increment is positive or not, assume yes ?
Definition at line 141 of file for_to_do_or_while_loops.c.
References add_expression_p(), call_arguments, call_function, CAR, CDR, copy_expression(), ENDP, entity_intrinsic(), ENTITY_MINUS_UPDATE_P, ENTITY_PLUS_UPDATE_P, ENTITY_POST_DECREMENT_P, ENTITY_POST_INCREMENT_P, ENTITY_PRE_DECREMENT_P, ENTITY_PRE_INCREMENT_P, EXPRESSION, expression_constant_p(), expression_syntax, expression_to_int(), expression_undefined, expression_verbose_reduction_p_and_return_increment(), extended_integer_constant_expression_p(), int_to_expression(), is_expression_reference_to_entity_p(), MakeUnaryCall(), negative_expression_p(), pips_debug, positive_expression_p(), sub_expression_p(), syntax_call, syntax_call_p, uminus, and UNARY_MINUS_OPERATOR_NAME.
Referenced by for_to_do_loop_conversion().
|
static |
given an expression
seed | that can be found in |
comma_list | iterate over |
comma_list | and remove |
seed | from the list, updating pointers properly |
Definition at line 580 of file for_to_do_or_while_loops.c.
References call_arguments, call_function, CAR, CDR, ENTITY_COMMA_P, EXPRESSION, expression_call(), expression_call_p(), expression_normalized, expression_syntax, and normalized_undefined.
Referenced by for_to_do_loop_conversion().
void transform_a_for_loop_into_a_while_loop | ( | forloop | f | ) |
Try to to transform the C-like for-loops into Fortran-like do-loops.
Assume we are in a gen_recurse since we use gen_get_recurse_ancestor(f).
The forloop is freed and replaced by a while loop in the statement owning the for-loop
Get the instruction owning the forloop:
Get the statement owning instruction owning the forloop:
Get a sequence with a while-loop instead:
These fields have been re-used, so protect them from memory recycling:
We need to replace the for-loop instruction by the sequence instruction. The cleaner way should be to delete the first one and make the other one, but since we are in a gen_recurse() and we iterate on the first one, it is dangerous. Well, I've tried and it works, but valgrind complains a bit. :-)
So change the type of the instruction on the fly instead:
And discard the old for:
Since we have replaced a statement that may have comments and labels by a sequence, do not forget to forward them where they can be:
FI: one issue: st is an ancestor of the current object and some of its pointers are going to be modified although they are being processed by gen_recurse()...
Removed useless instructions that may remain:
print_statement(st);
pips_debug(5, "Exiting with statement\n");
}
Definition at line 876 of file for_to_do_or_while_loops.c.
References clean_up_sequences(), expression_undefined, f(), fix_sequence_statement_attributes(), for_to_while_loop_conversion(), forloop_body, forloop_condition, forloop_increment, forloop_initialization, free_forloop(), gen_get_recurse_ancestor(), instruction_sequence, instruction_tag, is_instruction_sequence, pips_debug, statement_extensions, and statement_undefined.
void transform_a_for_loop_statement_into_a_while_loop | ( | statement | st | ) |
Same as above, but with no calls to ancestors.
Get the instruction owning the forloop:
Get the statement owning instruction owning the forloop:
Get a sequence with a while-loop instead:
These fields have been re-used, so protect them from memory recycling:
We need to replace the for-loop instruction by the sequence instruction. The cleaner way should be to delete the first one and make the other one, but since we are in a gen_recurse() and we iterate on the first one, it is dangerous. Well, I've tried and it works, but valgrind complains a bit. :-)
So change the type of the instruction on the fly instead:
And discard the old for:
Since we have replaced a statement that may have comments and labels by a sequence, do not forget to forward them where they can be:
FI: one issue: st is an ancestor of the current object and some of its pointers are going to be modified although they are being processed by gen_recurse()...
Removed useless instructions that may remain:
print_statement(st);
pips_debug(5, "Exiting with statement\n");
}
st | t |
Definition at line 928 of file for_to_do_or_while_loops.c.
References clean_up_sequences(), expression_undefined, f(), fix_sequence_statement_attributes(), for_to_while_loop_conversion(), forloop_body, forloop_condition, forloop_increment, forloop_initialization, forloop_statement_p(), free_forloop(), instruction_forloop, instruction_sequence, instruction_tag, is_instruction_sequence, pips_debug, statement_extensions, statement_instruction, and statement_undefined.
Referenced by for_loop_to_while_loop(), and new_controlizer().
void try_to_transform_a_for_loop_into_a_do_loop | ( | forloop | f | ) |
Try to to transform the C-like for-loops into Fortran-like do-loops.
Assume we are in a gen_recurse since we use gen_get_recurse_ancestor(f).
Get the englobing statement of the "for" assuming we are called from a gen_recurse()-like function:
Definition at line 740 of file for_to_do_or_while_loops.c.
References expression_undefined, f(), for_to_do_loop_conversion(), forloop_body, forloop_condition, forloop_increment, forloop_initialization, free_forloop(), gen_get_recurse_ancestor(), make_instruction_sequence(), pips_debug, sequence_undefined_p, statement_instruction, and statement_undefined.
Referenced by for_loop_to_do_loop(), and new_controlizer().