PIPS
|
#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "misc.h"
#include "properties.h"
#include "pipsdbm.h"
#include "ri.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "text-util.h"
#include "control.h"
#include "transformations.h"
Go to the source code of this file.
Macros | |
#define | NORMALIZED_UPPER_BOUND_NAME "LU_NUB" |
#define | INTERMEDIATE_BOUND_NAME "LU_IB" |
#define | INDEX_NAME "LU_IND" |
#define | FULL_UNROLL_PRAGMA "Cxxx" |
C must be a capital C... More... | |
Functions | |
static basic | basic_int_to_signed_basic (basic b) |
static void | do_loop_unroll_with_epilogue (statement loop_statement, int rate, void(*statement_post_processor)(statement)) |
db_get_current_module_name() unusable because module not set, and setting it causes previous current module to be closed! More... | |
static void | do_loop_unroll_with_prologue (statement loop_statement, int rate, void(*statement_post_processor)(statement)) |
This function unrolls any DO loop by a constant factor "rate". More... | |
void | do_loop_unroll (statement loop_statement, int rate, void(*statement_post_processor)(statement)) |
loop_unroll.c More... | |
void | loop_unroll (statement loop_statement, int rate) |
fallbacks on do_loop_unroll without statement post processing More... | |
bool | loop_fully_unrollable_p (loop l) |
void | full_loop_unroll (statement loop_statement) |
get rid of the loop by body replication; More... | |
bool | unroll (const string mod_name) |
Top-level functions. More... | |
static bool | apply_full_loop_unroll (struct _newgen_struct_statement_ *s) |
bool | full_unroll (const string mod_name) |
static void | find_unroll_pragma_and_fully_unroll (statement s) |
bool | full_unroll_pragma (const string mod_name) |
Variables | |
static int | number_of_unrolled_loops = 0 |
static int | number_of_requested_unrollings = 0 |
#define FULL_UNROLL_PRAGMA "Cxxx" |
C must be a capital C...
This should be improved with regular expressions, with a property to set the pragma or comment...
This algorithm is more efficient if we have far more loops than comments... :-)
Furthermore, people want to unroll only loops that are designated or all loops but those that are designated.
Loops can be tagged by the loop index, the loop label or a pragma.
A lot of improvement ahead before we can think of matching TSF flexibility...
Definition at line 1149 of file loop_unroll.c.
#define INDEX_NAME "LU_IND" |
Definition at line 56 of file loop_unroll.c.
#define INTERMEDIATE_BOUND_NAME "LU_IB" |
Definition at line 55 of file loop_unroll.c.
#define NORMALIZED_UPPER_BOUND_NAME "LU_NUB" |
Definition at line 54 of file loop_unroll.c.
|
static |
Definition at line 1064 of file loop_unroll.c.
References full_loop_unroll(), instruction_loop_p, and statement_instruction.
Referenced by full_unroll().
Definition at line 58 of file loop_unroll.c.
References basic_int, basic_int_p, and pips_assert.
Referenced by do_loop_unroll_with_prologue().
void do_loop_unroll | ( | statement | loop_statement, |
int | rate, | ||
void(*)(statement) | statement_post_processor | ||
) |
loop_statement | oop_statement |
rate | ate |
Definition at line 714 of file loop_unroll.c.
References do_loop_unroll_with_epilogue(), do_loop_unroll_with_prologue(), expression_integer_value(), get_bool_property(), instruction_loop, instruction_loop_p, intptr_t, loop_range, pips_assert, pips_debug, range_increment, and statement_instruction.
Referenced by loop_unroll(), and simd_loop_unroll().
|
static |
db_get_current_module_name() unusable because module not set, and setting it causes previous current module to be closed!
static string current_module_name = NULL; This function unrolls DO loop by a constant factor "rate" if their increment is statically known equal to 1. The initial loop is replaced by one unrolled loop followed by an epilogue loop:
DO I= LOW, UP
becomes
DO I = LOW, LOW + RATE * (UP-LOW+1)/RATE -1, RATE
DO I = LOW+ RATE * (UP-LOW+1)/RATE, UP
where (UP+LOW-1)/RATE is the number of iteration of the unrolled loop.
The initial index is reused to preserve as much readability as possible. The loop bounds are not simplified. This is left to other PIPS passes. Partial_eval can (hopefully) simplify the bounds and suppress_dead_code can eliminate the epilogue loop.
The upper and lower loop bound expressions are assumed side-effects free.
get rid of labels in loop body
Instruction block is created and will contain the two new loops
compute the new intermediate loop bounds, nlow and nup=nlow-1
span = up-low+1
count = span/rate
nlow = low + rate*count
nup = nlow -1
The first statement gets the label of the initial loop
The unrolled loop is generated first:
DO I = low, nup, rate BODY(I(I + 0)) BODY(I((I + 1)) ... BODY(I(I+(rate-1))) ENDDO
First, the loop range is generated
Create body of the loop, with updated index
Last transformated old loop added first
FI: beware of dependent types? 31/10/2014
Add the transformated old loop body (transformed_stmt) at the begining of the loop
For C code, be careful with local declarations and initializations
Create loop and insert it in the top block
?? Should execution be the same as initial loop?
The epilogue loop is generated last:
DO I = nlow, up BODY(I) ENDDO
Free old instruction and replace with block
FI: according to me, gen_copy_tree() does not create a copy sharing nothing with its actual parameter; if the free is executed, Pvecteur normalized_linear is destroyed (18 January 1993)
gen_free(statement_instruction(loop_statement));
Do not forget to move forbidden information associated with block:
Stop debug in Newgen
Definition at line 95 of file loop_unroll.c.
References clear_labels(), clone_statement(), CONS, copy_execution(), copy_expression(), count, DIVIDE_OPERATOR_NAME, ENDP, ENTITY, entity_empty_label(), entity_initial, entity_intrinsic(), entity_to_expression(), expression_consistent_p(), fix_sequence_statement_attributes(), FOREACH, free_clone_context(), free_expression(), GEN_DBG_CHECK, gen_debug, gen_nconc(), gen_nreverse(), get_bool_property(), get_current_module_entity(), get_current_module_statement(), ifdebug, instruction_block, instruction_block_p, instruction_consistent_p(), instruction_loop, instruction_to_statement(), int_to_expression(), is_instruction_loop, loop_body, loop_execution, loop_index, loop_range, make_assign_statement(), make_clone_context(), make_empty_block_statement(), make_instruction(), make_instruction_block(), make_loop(), make_new_loop_statement(), make_range(), make_ref_expr(), MakeBinaryCall(), MINUS_OPERATOR_NAME, MULTIPLY_OPERATOR_NAME, NIL, pips_assert, pips_debug, PLUS_OPERATOR_NAME, print_statement(), range_lower, range_undefined, range_upper, replace_entity_by_expression(), STATEMENT, statement_consistent_p(), statement_declarations, statement_instruction, statement_label, statement_undefined, value_expression, and value_expression_p.
Referenced by do_loop_unroll().
|
static |
This function unrolls any DO loop by a constant factor "rate".
If the iteration count n cannot statically determined to be a multiple of "rate", a first loop executes modulo(n,rate) iterations and then a second loop contains the unrolled body. To cope with all posible combinations of bounds and increments, the iteration count "n" is computed according to Fortran standard and the new iterations are numbered from 0 to n-1. The initial loop index is replaced by the proper expressions. The generated code is general. It must be simplified with passes partial_eval and/or suppress dead_code.
Khadija Imadoueddine experienced a slowdown with this unrolling scheme. She claims that it is due to the prologue loop which leads to unaligned accesses in the unrolled loop when the arrays accessed are aligned and accessed from the first element to the last.
Start debug in Newgen
Validity of transformation should be checked
ie.: - no side effects in replicated expressions
get rid of labels in loop body
Instruction block is created and will contain everything
Entity LU_NUB is created as well as its initializing statement. It contains the number of iterations according to Fortran standard:
LU_NUB = ((UB - LB) + INC)/INC
This should be OK with C for loops equivalent to a Fortran DO loop.
Warning: basic must be signed becuase LU_NUB may be negative
FI: Loop Unrolled New Upper Bound? In this code generation scheme the new lower bound is 0.
MakeBasic(is_basic_int)
The first statement gets the label of the initial loop
Entity LU_IB is created with its initializing statement
LU_IB = MOD(LU_NUB, rate)
and it is appended to the block
FI: Loop Unrolled Intermediate Bound?
MakeBasic(is_basic_int)
An index LU_IND and a loop for the first iterations are created to perform the prologue in case the number of iterations is not a multiple of the unrolling rate:
DO LU_IND = 0, LU_IB-1, 1 BODY(I(LU_IND*INC + LB)) ENDDO
FI: Loop Unrolled INDex
Loop range is created
Create body of the loop, with updated index
"gen_copy_tree returns bad statement\n");
Substitute the initial index by its value in the body
"gen_copy_tree returns bad expression(s)\n");
Create loop and insert it in top block. FI: parallelism could be preserved
The unrolled loop is generated:
DO LU_IND = LU_IB, LU_NUB-1, rate BODY(I(LU_IND*INC + LB)) BODY(I((LU_IND+1)*INC + LB)) ... BODY(I((LU_IND+(rate-1))*INC + LB)) ENDDO
First, the loop range is generated
Create body of the loop, with updated index
Last transformated old loop added first
Add the transformated old loop body (transformed_stmt) at the begining of the loop
For C code, be careful with local declarations and initializations
Create loop and insert it in the top block
?? Should execution be the same as initial loop?
Generate a statement to reinitialize old index IND = LB + MAX(NUB,0)*INC
Free old instruction and replace with block
FI: according to me, gen_copy_tree() does not create a copy sharing nothing with its actual parameter; if the free is executed, Pvecteur normalized_linear is destroyed (18 January 1993)
gen_free(statement_instruction(loop_statement));
Do not forget to move forbidden information associated with block:
Stop debug in Newgen
Definition at line 341 of file loop_unroll.c.
References AddEntityToCurrentModule(), basic_int_to_signed_basic(), clear_labels(), clone_statement(), CONS, copy_basic(), copy_expression(), DIVIDE_OPERATOR_NAME, ENDP, ENTITY, entity_empty_label(), entity_initial, entity_intrinsic(), entity_to_expression(), entity_type, expression_consistent_p(), expression_integer_value(), fix_sequence_statement_attributes(), FOREACH, FORTRAN_DIV, FORTRAN_MOD, free_clone_context(), free_expression(), GEN_DBG_CHECK, gen_debug, gen_nconc(), gen_nreverse(), get_bool_property(), get_current_module_entity(), get_current_module_statement(), ifdebug, INDEX_NAME, instruction_block, instruction_block_p, instruction_consistent_p(), instruction_loop, instruction_to_statement(), int_to_expression(), INTERMEDIATE_BOUND_NAME, intptr_t, is_execution_sequential, is_instruction_loop, is_syntax_reference, loop_body, loop_index, loop_range, make_assign_statement(), make_block_statement(), make_clone_context(), make_continue_statement(), make_empty_block_statement(), make_execution(), make_expression(), make_instruction(), make_instruction_block(), make_loop(), make_new_label(), make_new_scalar_variable_with_prefix(), make_range(), make_ref_expr(), make_reference(), make_statement_list, make_syntax(), MakeBinaryCall(), MAX0_OPERATOR_NAME, MINUS_OPERATOR_NAME, MULTIPLY_OPERATOR_NAME, NIL, normalized_undefined, NORMALIZED_UPPER_BOUND_NAME, pips_assert, pips_debug, PLUS_OPERATOR_NAME, print_statement(), range_consistent_p(), range_increment, range_lower, range_upper, replace_entity_by_expression(), STATEMENT, statement_consistent_p(), statement_declarations, statement_instruction, statement_label, type_variable, ultimate_type(), UU, value_expression, value_expression_p, and variable_basic.
Referenced by do_loop_unroll().
|
static |
full_loop_unroll() does not work all the time!
The full unroll pragma must comment a DO instruction
Definition at line 1151 of file loop_unroll.c.
References empty_comments_p(), full_loop_unroll(), FULL_UNROLL_PRAGMA, instruction_loop_p, number_of_requested_unrollings, number_of_unrolled_loops, pips_user_warning, statement_comments, and statement_instruction.
Referenced by full_unroll_pragma().
void full_loop_unroll | ( | statement | loop_statement | ) |
get rid of the loop by body replication;
the loop body is replicated as many times as there are iterations
FI: could be improved to handle symbolic lower bounds (18 January 1993)
final loop body label
Start debug in Newgen
Validity of transformation should be checked
ie.: - pas d'effets de bords dans les expressions duplique'es
Instruction block is created and will contain everything
get rid of labels in loop body: don't worry, useful labels have been transformed into arcs by controlizer, you just loose loop labels. However, the label of the last statement in the loop body might be used by an outer loop and, in doubt, should be preserved.
FI: clone_statement() has been used above to perform flatten_code. Hence the declarations are no longer accessible from "transformed_stmt". And when dependent types are used, they are not updated.
Try to update dependent types. Too bad the declarations are scanned again and again.
Add the transformated old loop body (transformed_stmt) at the end of the loop
Generate a CONTINUE to carry the final loop body label in case an outer loop uses it
Generate a statement to reinitialize old index
SG: only needed if index is not private
Free old instruction and replace with block
FI: according to me, gen_copy_tree() does not create a copy sharing nothing with its actual parameter; if the free is executed, Pvecteur normalized_linear is destroyed (18 January 1993)
Do not forget to move forbidden information associated with block:
?? Bad condition
Stop debug in Newgen
loop_statement | oop_statement |
Definition at line 788 of file loop_unroll.c.
References clean_up_sequences(), clear_labels(), clone_statement(), CONS, copy_expression(), ENDP, ENTITY, entity_empty_label_p(), entity_in_list_p(), entity_initial, entity_to_expression(), entity_type, entity_undefined, expression_consistent_p(), expression_integer_value(), find_final_statement_label(), fix_sequence_statement_attributes(), FOREACH, free_clone_context(), free_expression(), free_instruction(), GEN_DBG_CHECK, gen_debug, gen_nconc(), gen_nreverse(), get_bool_property(), get_current_module_entity(), get_current_module_statement(), get_debug_level(), ifdebug, instruction_block, instruction_loop, int_to_expression(), intptr_t, label_local_name(), loop_body, loop_index, loop_label, loop_locals, loop_range, make_assign_statement(), make_clone_context(), make_continue_statement(), make_instruction_block(), make_ref_expr(), NIL, pips_assert, pips_debug, pips_user_error, print_statement(), range_increment, range_lower, range_upper, replace_entity_by_expression(), STATEMENT, statement_block_p, statement_consistent_p(), statement_declarations, statement_instruction, value_expression, and value_expression_p.
Referenced by apply_full_loop_unroll(), find_unroll_pragma_and_fully_unroll(), full_unroll(), simd_loop_unroll(), terapixify_loops(), unroll_loops_in_statement(), and unroll_recursive().
user interaction
prelude
do the job
Reorder the module, because new statements have been generated.
ostlude
Reorder the module, because new statements have been generated.
mod_name | od_name |
Definition at line 1077 of file loop_unroll.c.
References apply_full_loop_unroll(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, empty_string_p(), entity_undefined, entity_undefined_p, find_label_entity(), find_loop_from_label(), full_loop_unroll(), gen_null(), gen_recurse, get_string_property_or_ask(), module_name_to_entity(), module_reorder(), pips_debug, pips_user_error, pips_user_warning, reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), statement_domain, statement_undefined, statement_undefined_p, string_undefined, and user_log().
Keep track of effects on code
Perform the loop unrollings
Perform the transformation bottom up to reduce the scanning and the number of unrollings
Reorder the module, because new statements have been generated.
Provide statistics about changes performed
mod_name | od_name |
Definition at line 1170 of file loop_unroll.c.
References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug(), debug_off, debug_on, find_unroll_pragma_and_fully_unroll(), gen_recurse, gen_true(), module_name_to_entity(), module_reorder(), number_of_requested_unrollings, number_of_unrolled_loops, reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), statement_domain, statement_undefined, and user_log().
Definition at line 753 of file loop_unroll.c.
References arguments_intersection(), ENDP, expression_integer_value(), gen_free_list(), get_string_property(), intptr_t, loop_body, loop_range, pips_debug, range_increment, range_lower, range_upper, statement_to_called_user_entities(), and string_to_user_modules().
Referenced by unroll_loops_in_statement().
fallbacks on do_loop_unroll without statement post processing
loop_statement | oop_statement |
rate | ate |
Definition at line 748 of file loop_unroll.c.
References do_loop_unroll().
Referenced by unroll().
Top-level functions.
Get the loop label form the user
Get the unrolling factor from the user
User asked to cancel:
Sets the current module to "mod_name".
current_module(module_name_to_entity(mod_name));
DBR_CODE will be changed: argument "pure" should take false but this would be useless since there is only one version of code; a new version will be put back in the data base after unrolling
prelude
Validity of transformation should be checked
ie.: - no side effects in replicated expressions
No dependent types in C
do the job
Reorder the module, because new statements have been generated.
ostlude
mod_name | od_name |
Definition at line 960 of file loop_unroll.c.
References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dependent_type_p(), empty_string_p(), ENTITY, entity_type, entity_undefined_p, find_label_entity(), find_loop_from_label(), FOREACH, get_int_property(), get_string_property_or_ask(), instruction_loop, loop_body, loop_unroll(), module_name_to_entity(), module_reorder(), pips_debug, pips_user_error, pips_user_warning, reset_current_module_entity(), reset_current_module_statement(), set_current_module_entity(), set_current_module_statement(), statement_declarations, statement_instruction, statement_undefined_p, user_error, user_log(), and user_request().
|
static |
Definition at line 1134 of file loop_unroll.c.
Referenced by find_unroll_pragma_and_fully_unroll(), and full_unroll_pragma().
|
static |
Definition at line 1133 of file loop_unroll.c.
Referenced by find_unroll_pragma_and_fully_unroll(), and full_unroll_pragma().