loop_util.cc File Reference
Go to the source code of this file.
|
Functions |
| static Expression * | _icall_id (const char *fn, ProgramUnit &pgm) |
| static Expression * | _loop_range (Statement &do_stmt) |
| static Boolean | is_ID_OP (const Expression &expr) |
| static void | _subst_var_in_assert (Statement &stmt, const Symbol &var, const Expression &replacement) |
| static void | _subst_var_in_outer_assert (Statement &stmt, const Symbol &var, const Expression &replacement) |
| static void | _subst_var_in_stmt (Statement &stmt, const Symbol &var, const Expression &replacement) |
| void | simplify_control_flow (ProgramUnit &pgm, Statement &s) |
| Boolean | coalese_loop (ProgramUnit &pgm, Statement &outer_do_stmt, Statement &inner_do_stmt) |
| static Boolean | _any_escaping_gotos (ProgramUnit &pgm, Statement &loop) |
| | determine if there are any escaping goto statements. returns True if there are.
|
| static void | _loop_index_last_val (ProgramUnit &pgm, Symbol &index_var, Statement &do_stmt, Statement &after_me) |
| | compute loop index last value
|
| static Boolean | _any_reached_uses (ProgramUnit &NOTUSED(pgm), Symbol &var, Statement &stmt) |
| | this function finds out if there are any uses of scalar "var" that can be reached from the statement "stmt".
|
| void | normalize_loop (ProgramUnit &pgm, Statement &do_stmt, int origin GIV(1)) |
| void | eliminate_loop (ProgramUnit &pgm, Statement &do_stmt) |
| | Change DO I = LOWER, UPPER, STEP S1 END DO.
|
| void | peel_loop_first (ProgramUnit &pgm, Statement &do_stmt) |
| void | peel_loop_first (ProgramUnit &pgm, Statement &do_stmt, int count) |
| void | peel_loop_last (ProgramUnit &pgm, Statement &do_stmt) |
| | Peel the last iteration off the loop.
|
| void | peel_loop_last (ProgramUnit &pgm, Statement &do_stmt, int count) |
| void | precalc_loop (ProgramUnit &pgm, Statement &do_stmt) |
| void | stripmine_horiz_loop (ProgramUnit &pgm, Statement &do_stmt, Expression *strip) |
| void | stripmine_vert_loop (ProgramUnit &pgm, Statement &do_stmt, Expression *strip) |
| void | unroll_loop (ProgramUnit &pgm, Statement &do_stmt, int count) |
| void | preroll_loop (ProgramUnit &pgm, Statement &do_stmt, int count) |
| void | reverse_loop (ProgramUnit &pgm, Statement &do_stmt) |
| List< Statement > * | clone_loop (ProgramUnit &pgm, Statement &do_stmt, const String &suffix) |
| | This routine copies a whole loop nest and returns it as a List<Statement> to the caller.
|
| List< Statement > * | clone_loop_body (ProgramUnit &pgm, Statement &do_stmt, const String &suffix) |
| | Begin OpenMP Modification.
|
| Boolean | is_perfect_nest (Statement *do_stmt) |
| | End OpenMP Modification.
|
Function Documentation
|
|
Definition at line 30 of file loop_util.cc.
References add(), Expression::clone(), div(), simplify(), and sub().
Referenced by coalese_loop(), eliminate_loop(), normalize_loop(), peel_loop_first(), peel_loop_last(), preroll_loop(), and stripmine_vert_loop(). |
|
|
... Substitute the variable in the assertions of the statement.
... For RANGEWRITTEN, substitute only when the ... variable to be replaced is found inside an expression.
... Do nothing!
... For FIRSTVALUE, substitute only when the ... variable to be replaced is found inside an expression. ... When the variable is found by itself, add all variables ... from the replacement expression are to be added to the ... assertion.
Definition at line 49 of file loop_util.cc.
References AS_FIRSTVALUE, AS_RANGEWRITTEN, ID_OP, List< T >::ins_last(), is_ID_OP(), is_var_in_expr(), substitute_var(), and List< T >::valid().
Referenced by _subst_var_in_outer_assert(), _subst_var_in_stmt(), and normalize_loop(). |
|
|
... Get a reference to the index variables
... Create a new index variable for the new loop.
... Get copies of all the expressions.
Expression * outer_limit = outer_do_stmt.limit().clone(); Expression * outer_step = outer_do_stmt.step().clone();
Expression * inner_limit = inner_do_stmt.limit().clone(); Expression * inner_step = inner_do_stmt.step().clone();
... Calculate the ranges.
... Remove the inner DO loop, it is no longer needed.
... Calculate the new expressions for the OLD index variables.
... Calculate the new limit.
... Rebuild the single DO loop.
Definition at line 166 of file loop_util.cc.
References _icall_id(), _loop_range(), add(), Symbol::clone(), Expression::clone(), comma(), constant(), div(), DO_STMT, False, id(), intrinsic_call(), mul(), precalc_loop(), simplify(), sub(), and True.
Referenced by coalese_loop_pu(). |
|
|
compute loop index last value
... obtain the intrinsic MAX
... obtain the intrinsic INT
Definition at line 312 of file loop_util.cc.
References add(), Expression::clone(), comma(), constant(), div(), FUNCTION_CLASS, id(), INTEGER_TYPE, Symbol::intrinsic(), intrinsic_call(), IS_INTRINSIC, mul(), NOT_EXTERNAL, NOT_FORMAL, simplify(), sub(), and Symbol::sym_class().
Referenced by normalize_loop(). |
|
|
this function finds out if there are any uses of scalar "var" that can be reached from the statement "stmt".
it returns True if so, or False if not.
... if the variable isn't local, then don't bother continuing ... we may be able to do better with equivalences.
... list of statements that have already been visited, so we don't get ... stuck on flow-graph cycles
... list of statements that need to be inspected
... initialize the worklist
... iterate until there are no more statements in the worklist to deal with
... grab a guy
... worklist.del(scan_me); ... see if we should bother looking at him
... add this guy to the visited list
... flag keeping track if search has been pruned or not ... True = not pruned, so check successors
... check reads
... found a use
... check modifications
... generic statements read all subexpressions
... do loop writes it's index, reads all others
... the variable is killed here
... assignment writes lhs top-level and reads other crud
... the variable is killed here
... add successors to the worklist
... well, we didn't find anything
Definition at line 371 of file loop_util.cc.
References ASSIGNMENT_STMT, Expression::base_variable_ref(), DO_STMT, RefSet< T >::entries(), False, RefSet< T >::grab(), ID_OP, Statement::in_refs(), Statement::index(), RefSet< T >::ins(), IS_EXTERNAL, IS_FORMAL, IS_SAVED, Statement::lhs(), RefSet< T >::member(), Expression::op(), Statement::stmt_class(), Statement::succ(), True, and RefSet< T >::valid().
Referenced by normalize_loop(). |
|
|
... Normalize loop do_stmt to have a lower bound of <origin> and a step of 1
... Get new copies of the DO's init, limit and step expressions,
... Get a reference to the index variable
... First we need to specify the replacement expression
... determine if zero trip is definitely not the case
... determine if loop index is not local
... Replace the init expression with the constant
... until we compute the last value of the index. In case of a zero_trip loop which ... goes undetected we want to make sure the last value of the index is correct. ... do_stmt.init( new_init );
... do_stmt.limit( new_limit ); ... Replace the step expression with the constant 1 ... do_stmt.step( new_step );
... Now find all occurrences of the use of the index variable ... inside the loop and replace them with the expression ... (((index_variable-new_init)*step) + old_init)
... Loop through all statements within the loop body
... Skip over the DO statement itself.
... Now, replace the index variable with the expresion above in ... the assertion statements for the loop.
... if the loop is possibly zero trip, then put an initial assignment to the ... original variable
... are there any escaping gotos in the loop
... if there are escaping gotos, then we rename the loop index variable so we can ... assign the proper value to the real loop index variable at the beginning of each ... iteration so it is valid at the escape point. ... if the loop may also be zero-trip, then we assign the first value to the real index ... before the loop so it is valid if the loop is skipped.
... convert all old symbols to new ones
... add iteration assignment of loop value
... if there are no escaping gotos, then we only need a last value at the end
... Delete the copies.
... We don't need this expression anymore--garbage collect it
Definition at line 471 of file loop_util.cc.
References _any_escaping_gotos(), _any_reached_uses(), _loop_index_last_val(), _loop_range(), _subst_var_in_assert(), _subst_var_in_stmt(), add(), Expression::clone(), constant(), Iterator< T >::current(), DO_STMT, id(), Statement::init(), is_integer_constant(), Statement::lhs(), mul(), NOT_FORMAL, NOT_GLOBAL, NOT_SAVED, precalc_loop(), simplify(), sub(), Expression::symbol(), and Iterator< T >::valid().
Referenced by normalize_loop_pu(), peel_loop_first(), peel_loop_last(), preroll_loop(), reverse_loop(), reverse_loop_pu(), stripmine_horiz_loop(), and stripmine_vert_loop(). |
|
|
Change DO I = LOWER, UPPER, STEP S1 END DO.
into the following if we can prove the loop is one trip.:
I = LOWER S1 I = LOWER+STEP
Expression *init = do_stmt.init().clone(); Expression *limit = do_stmt.limit().clone(); Expression *step = do_stmt.step().clone();
... Get a reference to the index variable
... Maybe needed if the index variable is used after the loop.
... Add lastvalue assignment.
... Remove the DO loop and the statements inside of it since it is ... never executed.
... Loop through all statements within the loop body
... Skip over the DO statement itself.
... Delete the copies.
... Remove the DO loop, since it is only executed once.
Definition at line 635 of file loop_util.cc.
References _loop_range(), _subst_var_in_stmt(), add(), Expression::clone(), Iterator< T >::current(), DO_STMT, Statement::follow_ref(), id(), Statement::init(), is_integer_constant(), precalc_loop(), simplify(), Expression::symbol(), Iterator< T >::valid(), and Expression::value().
Referenced by peel_loop_first(), and preroll_loop(). |
|
|
... Precalculate the DO loop if needed.
... Get a copy of the lower bound of the loop.
... Modify the bounds to insure that the loops do not overlap.
... Get a copy of the DO loop.
... Get a pointer to the new copy of the DO loop header.
... Put them back into the program in front of the original loop.
Definition at line 701 of file loop_util.cc.
Referenced by peel_first_loop_pu(), and peel_loop_first(). |
|
|
... Precalculate the DO loop if needed.
... Perform special peeling if we only want the first iteration.
... Get a copy of the DO loop.
... Get a pointer to the new copy of the DO loop header.
... Put them back into the program in front of the original loop.
... Get a copy of the lower bound of the loop.
... Modify the bounds to insure that the loops do not overlap.
Definition at line 764 of file loop_util.cc.
References _icall_id(), add(), Expression::clone(), clone_loop(), comma(), constant(), DO_STMT, List< T >::first_ref(), Statement::init(), intrinsic_call(), is_integer_constant(), Statement::limit(), mul(), normalize_loop(), peel_loop_first(), precalc_loop(), simplify(), and sub(). |
|
|
Peel the last iteration off the loop.
... Precalculate the DO loop if needed.
... Get a copy of the DO loop.
... Get a pointer to the new copy of the DO loop header.
... Put them back into the program in front of the original loop.
... Get a copy of the lower bound of the loop.
... Get the loop label of the peeled loop
... Change references to the loop index into usages of the upper loop bound
... Skip over the DO statement itself. ... Replace the loop index by the limit expression from the original loop and ... remove all references to the original outer loop for PRIVATEREFS ... and READONLYREFS assertions in the peeled part
... list of parenthesized comma exprs
... Each is a PAREN_OP
... The parenthesized expr should be a CommaExpr:
Definition at line 826 of file loop_util.cc.
Referenced by peel_last_loop_pu(), and peel_loop_last(). |
|
|
... Precalculate the DO loop if needed.
... Get a copy of the DO loop.
... Get a pointer to the new copy of the DO loop header.
... Put them back into the program in front of the original loop.
... Get a copy of the lower bound of the loop.
... Modify the bounds to insure that the loops do not overlap.
Definition at line 944 of file loop_util.cc.
References _icall_id(), add(), Expression::clone(), clone_loop(), comma(), constant(), DO_STMT, List< T >::first_ref(), Statement::init(), intrinsic_call(), Statement::limit(), normalize_loop(), peel_loop_last(), precalc_loop(), simplify(), and sub(). |
|
|
... Get a reference to the index variable
... Get new copies of the DO's init, limit and step expressions.
... Coerce init, limit and step to the type of the loop index ... by applying intrinsic functions to the expressions ... (only if necessary)
... If the bound expressions could have side effects, they must ... be precalculated.
... Put them back into the statement.
Definition at line 997 of file loop_util.cc.
References Symbol::clone(), coerce(), Type::data_type(), DO_STMT, get_precalc(), invariant_expression(), loop_invariant_vars(), loop_variant_vars(), PRECALC_ALWAYS, PRECALC_IF_SIDE_EFFECTS, Expression::symbol(), and Symbol::type().
Referenced by coalese_loop(), eliminate_loop(), normalize_loop(), peel_loop_first(), peel_loop_last(), preroll_loop(), stripmine_horiz_loop(), stripmine_vert_loop(), and unroll_loop(). |
|
|
... Get a reference to the index variable
... Get the index variable for the second loop.
... Calculate the new limit.
... Build a new DO loop to be nested inside of the current loop. ... Statement & new_do_stmt =
Definition at line 1055 of file loop_util.cc.
References _icall_id(), add(), Symbol::clone(), Expression::clone(), comma(), constant(), DO_STMT, intrinsic_call(), is_integer_constant(), mul(), normalize_loop(), precalc_loop(), Listable::prev_ref(), simplify(), and sub().
Referenced by strip_horiz_loop_pu(). |
|
|
... Get a reference to the index variable
... Get the index variable for the second loop.
... Calculate the inner strip size.
... Compute the initial value and limit for the new DO loop.
... Build a new DO loop to be nested inside of the current loop. ... Statement & new_do_stmt =
Definition at line 1098 of file loop_util.cc.
References _icall_id(), _loop_range(), add(), Expression::clone(), Symbol::clone(), comma(), constant(), div(), DO_STMT, intrinsic_call(), is_integer_constant(), mul(), normalize_loop(), precalc_loop(), Listable::prev_ref(), simplify(), sub(), and Expression::symbol().
Referenced by main(), and strip_vert_loop_pu(). |
|
|
... Unroll the loop, maybe we need to normalize first.
... If there are no statements in the loop body then this is a NO-OP.
... Get a copy of the old step expression.
... Get a reference to the index variable
... Get a copy of the DO loop body.
Definition at line 1157 of file loop_util.cc.
References _subst_var_in_stmt(), add(), Expression::clone(), clone_loop(), constant(), DO_STMT, is_integer_constant(), mul(), Listable::next_ref(), precalc_loop(), Listable::prev_ref(), List< T >::print(), simplify(), and List< T >::valid().
Referenced by preroll_loop(), and unroll_loop_pu(). |
|
|
... Precalculate the DO loop if needed.
... Get a copy of the lower bound of the loop.
... Modify the bounds to insure that the loops do not overlap.
... Get a copy of the DO loop.
... Get a pointer to the new copy of the DO loop header.
... Put them back into the program in front of the original loop.
Definition at line 1204 of file loop_util.cc.
References _icall_id(), _loop_range(), add(), Expression::clone(), clone_loop(), comma(), constant(), DO_STMT, eliminate_loop(), List< T >::first_ref(), intrinsic_call(), is_integer_constant(), Statement::limit(), normalize_loop(), precalc_loop(), simplify(), sub(), unroll_loop(), and Expression::value().
Referenced by preroll_loop_pu(). |
|
|
This routine copies a whole loop nest and returns it as a List<Statement> to the caller.
It adds _<suffix>1 to the original loop nest's loop labels and _<suffix>2 to the copy's loop labels.
... Build suffix strings for later use
... Copy over suffix
... Null out last character of buffer
... Build suffix1 in buffer
... Build suffix2 in buffer
... Find the first looplabel assertion (then later delete all that may exist)
... Replace the old loop name with new loop names
... Make new loop name for this DO: original + <suffix>1
... Now, append _<suffix>2 to the labels of the loops in the new nest
... Find the first looplabel assertion (then later delete them all)
... Replace the old loop name with new loop names
... Make new loop name for this DO: original + <suffix>2
Definition at line 1297 of file loop_util.cc.
References Expression::arg_list(), Assertion::arg_list_guarded(), Assertion::arg_list_valid(), AS_LOOPLABEL, AS_PRIVATEREFS, AS_READONLYREFS, Statement::assertions(), Iterator< T >::current(), List< T >::del(), DO_STMT, Expression::expr_guarded(), ProtoDatabase< S, T >::find_ref(), Statement::get_loop_name(), KeyDatabase< S, T >::ins(), List< T >::ins_last(), List< T >::modify(), Statement::stmt_class(), StringAssertion::string_arg_list_guarded(), Assertion::type(), Iterator< T >::valid(), and List< T >::valid().
Referenced by peel_loop_first(), peel_loop_last(), preroll_loop(), and unroll_loop(). |
|
|
Begin OpenMP Modification.
... Build suffix strings for later use
... Copy over suffix
... Null out last character of buffer
... Build suffix1 in buffer
... Build suffix2 in buffer
... Skip the DO stmt
... Find the first looplabel assertion (then later delete all that may exist)
... Replace the old loop name with new loop names
... Make new loop name for this DO: original + <suffix>1
... Now, append _<suffix>2 to the labels of the loops in the new nest
... Find the first looplabel assertion (then later delete them all)
... Replace the old loop name with new loop names
... Make new loop name for this DO: original + <suffix>2
Definition at line 1443 of file loop_util.cc.
References Expression::arg_list(), Assertion::arg_list_guarded(), Assertion::arg_list_valid(), AS_LOOPLABEL, AS_PRIVATEREFS, AS_READONLYREFS, Statement::assertions(), Iterator< T >::current(), List< T >::del(), DO_STMT, Expression::expr_guarded(), ProtoDatabase< S, T >::find_ref(), Statement::get_loop_name(), KeyDatabase< S, T >::ins(), List< T >::ins_last(), List< T >::modify(), Statement::stmt_class(), StringAssertion::string_arg_list_guarded(), Assertion::type(), Iterator< T >::valid(), and List< T >::valid(). |
|