Polaris: loop_util.cc Source File

loop_util.cc Go to the documentation of this file. /// #include "../ProgramUnit.h" #include "../Collection/Mutator.h" #include "../Directive/Assertion.h" #include "../Directive/AssertLoopLabel.h" #include "../Expression/Expression.h" #include "../Expression/StringConstExpr.h" #include "../Statement/AssignmentStmt.h" #include "../Statement/Statement.h" #include "../Symbol/FunctionSymbol.h" #include "../Symbol/VariableSymbol.h" #include "../Symbol/Symbol.h" #include "../Traverser.h" #include "../Collection/KeyDatabase.h" #include "../Collection/RefSet.h" #include "../p-assert.h" #include "expression_util.h" #include "invariant_util.h" #include "loop_util.h" #include "precalc_util.h" static Expression * _icall_id( const char *fn, ProgramUnit &pgm ) { return id( pgm.symtab().ins_intrinsic(fn) ); } static Expression * _loop_range( Statement &do_stmt ) { return simplify( div( add ( sub( do_stmt.limit().clone(), do_stmt.init().clone() ), do_stmt.step().clone() ), do_stmt.step().clone() ) ); } static Boolean is_ID_OP (const Expression & expr) { if (expr.op() == ID_OP) { return True; } else { return False; } } static void _subst_var_in_assert(Statement &stmt, const Symbol &var, const Expression &replacement) { /// ... Substitute the variable in the assertions of the statement. for (Iterator<Assertion> ass_iter = stmt.assertions(); ass_iter.valid(); ++ass_iter) { if (ass_iter.current().arg_list_valid()) { List<Expression> new_vars; for (Mutator<Expression> aexpr_iter = ass_iter.current().arg_list_guarded(); aexpr_iter.valid(); ++aexpr_iter) { if (is_var_in_expr(aexpr_iter.current(), var)) { /// ... For RANGEWRITTEN, substitute only when the /// ... variable to be replaced is found inside an expression. if ((ass_iter.current().type() == AS_RANGEWRITTEN) && (aexpr_iter.current().op() == ID_OP)) { /// ... 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. } else if ((ass_iter.current().type() == AS_FIRSTVALUE) && (aexpr_iter.current().op() == ID_OP)) { Traverser trav (replacement, is_ID_OP); for ( ; trav.valid(); ++trav) { new_vars.ins_last(trav.current().clone()); } } else { Assign<Expression> aexpr_as(aexpr_iter.assign()); aexpr_as = substitute_var(aexpr_iter.pull(), var, replacement); } } } for (Iterator<Expression> new_iter = new_vars; new_iter.valid(); ++new_iter) { ass_iter.current().arg_list_guarded().ins_last( new_iter.current().clone() ); } } } } static void _subst_var_in_outer_assert(Statement &stmt, const Symbol &var, const Expression &replacement) { /// ... Substitute the variable in the assertions of the statement /// ... and all statements enclosing the statement (via the outer() field.) for (Statement *enclosing_stmt = &stmt; enclosing_stmt; enclosing_stmt = enclosing_stmt->outer_ref()) _subst_var_in_assert(*enclosing_stmt, var, replacement); } static void _subst_var_in_stmt(Statement &stmt, const Symbol &var, const Expression &replacement) { /// ... Substitute the variable in the expression arguments of the statement. Boolean modified_stmt_expr = False; for ( Mutator<Expression> mutr = stmt.iterate_expressions(); mutr.valid(); ++mutr) { if (is_var_in_expr(mutr.current(), var)) { Assign<Expression> expr_as(mutr.assign()); expr_as = simplify(substitute_var(mutr.pull(), var, replacement)); modified_stmt_expr = True; } } if (modified_stmt_expr) stmt.build_refs(); /// ... Substitute the variable in the assertions of the statement. _subst_var_in_assert(stmt, var, replacement); } void simplify_control_flow( ProgramUnit &pgm, Statement & s ) { if ( s.stmt_class() == IF_STMT && s.follow_ref()->stmt_class() == ENDIF_STMT) { Expression *expr = simplify( s.expr().clone() ); if (expr->op() == LOGICAL_CONSTANT_OP) { if (expr->str_data() == ".TRUE.") { /// ... Delete the IF statement and leave everything else. pgm.stmts().del( s ); } else if (expr->str_data() == ".FALSE.") { /// ... Delete everything in the IF statement. pgm.stmts().del( s, *s.follow_ref() ); } } delete expr; } } Boolean coalese_loop(ProgramUnit & pgm, Statement & outer_do_stmt, Statement & inner_do_stmt) { p_assert(outer_do_stmt.stmt_class() == DO_STMT, "outer not a DO loop"); p_assert(inner_do_stmt.stmt_class() == DO_STMT, "outer not a DO loop"); precalc_loop( pgm, outer_do_stmt ); precalc_loop( pgm, inner_do_stmt ); if (outer_do_stmt.next_ref() != & inner_do_stmt) return False; /// ... Get a reference to the index variables Symbol & outer_index_var = outer_do_stmt.index().symbol(); Symbol & inner_index_var = inner_do_stmt.index().symbol(); /// ... Create a new index variable for the new loop. Symbol & new_index_var = pgm.symtab().rename_and_ins( outer_index_var.clone() ); /// ... Get copies of all the expressions. Expression * outer_init = outer_do_stmt.init().clone(); /// Expression * outer_limit = outer_do_stmt.limit().clone(); /// Expression * outer_step = outer_do_stmt.step().clone(); Expression * inner_init = inner_do_stmt.init().clone(); /// Expression * inner_limit = inner_do_stmt.limit().clone(); /// Expression * inner_step = inner_do_stmt.step().clone(); /// ... Calculate the ranges. Expression *outer_range = _loop_range( outer_do_stmt ); Expression *inner_range = _loop_range( inner_do_stmt ); /// ... Remove the inner DO loop, it is no longer needed. pgm.stmts().del( inner_do_stmt ); /// ... Calculate the new expressions for the OLD index variables. Expression * outer_do_expr = simplify( add( div( id(new_index_var), inner_range->clone() ), outer_init )); Expression * inner_do_expr = simplify( add( intrinsic_call( _icall_id("MOD", pgm), comma( id(new_index_var), inner_range->clone() )), inner_init)); pgm.stmts().ins_after( new AssignmentStmt( pgm.stmts().new_tag(), id(inner_index_var), inner_do_expr ), &outer_do_stmt ); pgm.stmts().ins_after( new AssignmentStmt( pgm.stmts().new_tag(), id(outer_index_var), outer_do_expr ), &outer_do_stmt ); /// ... Calculate the new limit. Expression * new_limit = simplify( sub( mul( outer_range, inner_range ), constant(1) )); /// ... Rebuild the single DO loop. outer_do_stmt.index( id(new_index_var) ); outer_do_stmt.init( constant(0) ); outer_do_stmt.limit( new_limit ); outer_do_stmt.step( constant(1) ); return True; } /// determine if there are any escaping goto statements. returns True if there are. static Boolean _any_escaping_gotos(ProgramUnit &pgm, Statement &loop) { for (Iterator<Statement> scan = pgm.stmts().iterate_loop_body(&loop); scan.valid(); ++scan) { switch (scan.current().stmt_class()) { case GOTO_STMT: { Statement *outer_scan = scan.current().target_ref(); /// ... check to see if target is inside of the loop by looking /// ... for our loop in it's containing loop list while ((outer_scan != NULL) && (outer_scan != &loop)) { outer_scan = outer_scan->outer_ref(); } if (outer_scan == NULL) { /// ... scan left procedure without hitting our loop return True; } } break; case COMPUTED_GOTO_STMT: case ARITHMETIC_IF_STMT: { for (Iterator<Statement> chk = scan.current().label_list(); chk.valid(); ++chk) { Statement *outer_scan = chk.current().outer_ref(); /// ... check to see if target is inside of the loop by looking /// ... for our loop in it's containing loop list while ((outer_scan != NULL) && (outer_scan != &loop)) { outer_scan = outer_scan->outer_ref(); } if (outer_scan == NULL) { /// ... scan left procedure without hitting our loop return True; } } } break; case RETURN_STMT: case ASSIGN_STMT: case ASSIGNED_GOTO_STMT: return True; default: return False; } } return False; } /// compute loop index last value static void _loop_index_last_val(ProgramUnit &pgm, Symbol &index_var, Statement &do_stmt, Statement &after_me) { /// ... obtain the intrinsic MAX Symbol *max = pgm.symtab().find_ref("MAX"); if (max == NULL) { max = new FunctionSymbol("MAX",INTEGER_TYPE,NOT_EXTERNAL,IS_INTRINSIC,NOT_FORMAL); pgm.symtab().ins(max); } else { p_assert((max->sym_class() == FUNCTION_CLASS) && (max->intrinsic() == IS_INTRINSIC), "_loop_index_last_val: MAX intrinsic used for some other purpose"); } /// ... obtain the intrinsic INT Symbol *inte = pgm.symtab().find_ref("INT"); if (inte == NULL) { inte = new FunctionSymbol("INT",INTEGER_TYPE,NOT_EXTERNAL,IS_INTRINSIC,NOT_FORMAL); pgm.symtab().ins(inte); } else { p_assert((inte->sym_class() == FUNCTION_CLASS) && (inte->intrinsic() == IS_INTRINSIC), "_loop_index_last_val: INT intrinsic used for some other purpose"); } // step * max(int((limit - init + step)/step),0) Statement *set_lastval = new AssignmentStmt(pgm.stmts().new_tag(), id(index_var), simplify( add( do_stmt.init().clone(), mul( do_stmt.step().clone(), intrinsic_call( id(*max), comma( intrinsic_call( id(*inte), comma( div( add( sub( do_stmt.limit().clone(), do_stmt.init().clone()), do_stmt.step().clone()), do_stmt.step().clone()))), constant(0))))))); pgm.stmts().ins_after(set_lastval,&after_me); } /// 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. static Boolean _any_reached_uses(ProgramUnit & NOTUSED(pgm), Symbol &var, Statement &stmt) { p_assert(!var.is_array(),"normalize_loop: _any_reached_uses: only handles scalars"); /// ... if the variable isn't local, then don't bother continuing /// ... we may be able to do better with equivalences. if ((var.saved() == IS_SAVED) || (var.external() == IS_EXTERNAL) || (var.common_ref() != NULL) || (var.equivalence_ref() != NULL) || (var.formal() == IS_FORMAL)) { return True; } /// ... list of statements that have already been visited, so we don't get /// ... stuck on flow-graph cycles RefSet<Statement> visited; /// ... list of statements that need to be inspected RefSet<Statement> worklist; /// ... initialize the worklist worklist.ins(stmt); /// ... iterate until there are no more statements in the worklist to deal with while (worklist.entries() != 0) { /// ... grab a guy Statement &scan_me = worklist.grab(); /// ... worklist.del(scan_me); /// ... see if we should bother looking at him if (!visited.member(scan_me)) { /// ... add this guy to the visited list visited.ins(scan_me); /// ... flag keeping track if search has been pruned or not /// ... True = not pruned, so check successors Boolean follow_flow = True; /// ... check reads for (Iterator<Expression> inrefs = scan_me.in_refs(); inrefs.valid(); ++inrefs) { Expression &inref = inrefs.current(); if ((inref.op() == ID_OP) && (inref.base_variable_ref() == &var)) { /// ... found a use return True; } } /// ... check modifications switch (scan_me.stmt_class()) { /// ... generic statements read all subexpressions default: break; /// ... do loop writes it's index, reads all others case DO_STMT: if (scan_me.index().base_variable_ref() == &var) { /// ... the variable is killed here follow_flow = False; } break; /// ... assignment writes lhs top-level and reads other crud case ASSIGNMENT_STMT: if (scan_me.lhs().base_variable_ref() == &var) { /// ... the variable is killed here follow_flow = False; } break; } /// ... add successors to the worklist if (follow_flow) { for (Iterator<Statement> succs = scan_me.succ(); succs.valid(); ++succs) { if (!visited.member(succs.current()) && !worklist.member(succs.current())) { worklist.ins(succs.current()); } } } } // visited IF } /// ... well, we didn't find anything return False; } void normalize_loop(ProgramUnit & pgm, Statement & do_stmt, int origin GIV(1)) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); /// ... Normalize loop do_stmt to have a lower bound of <origin> and a step of 1 if (is_integer_constant(do_stmt.init()) && is_integer_constant(do_stmt.step()) ) { if (do_stmt.init().value() == origin && do_stmt.step().value() == 1) return; } /// ... Get new copies of the DO's init, limit and step expressions, Expression *init = do_stmt.init().clone(); Expression *limit = do_stmt.limit().clone(); Expression *step = do_stmt.step().clone(); Expression *range = _loop_range( do_stmt ); Expression *new_init = constant(origin); Expression *new_limit = simplify( add( sub( range, constant(1) ), constant(origin) )); Expression *new_step = constant(1); /// ... Get a reference to the index variable Symbol & index_var = do_stmt.index().symbol(); /// ... First we need to specify the replacement expression Expression *replacement = simplify( add( mul( sub( id(index_var), new_init->clone() ), step->clone() ), init->clone() ) ); /// ... determine if zero trip is definitely not the case Boolean no_zero_trip = ((is_integer_constant(do_stmt.init()) && is_integer_constant(do_stmt.limit()) && is_integer_constant(do_stmt.step())) && (0 < (do_stmt.limit().value() - do_stmt.init().value() + do_stmt.step().value()) / do_stmt.step().value())); /// ... determine if loop index is not local Boolean non_local_loop_index = ((do_stmt.index().symbol().formal() != NOT_FORMAL) || (do_stmt.index().symbol().saved() != NOT_SAVED) || (do_stmt.index().symbol().global() != NOT_GLOBAL) || (do_stmt.index().symbol().equivalence_ref() != NULL) || (do_stmt.index().symbol().common_ref() != NULL)); precalc_loop( pgm, do_stmt ); /// ... Replace the init expression with the constant // CC 09/20/96 - we want to postpone the assignment of the new initial expression /// ... 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 ); // Replace limit expression with (limit - init) / step /// ... 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 Iterator<Statement> stmts = pgm.stmts().iterate_loop_body(&do_stmt); /// ... Skip over the DO statement itself. for ( ++stmts; stmts.valid(); ++stmts) _subst_var_in_stmt(stmts.current(), index_var, *replacement); /// ... Now, replace the index variable with the expresion above in /// ... the assertion statements for the loop. _subst_var_in_assert(do_stmt, index_var, *replacement); /// ... if the loop is possibly zero trip, then put an initial assignment to the /// ... original variable if (!no_zero_trip) { Statement *initassign = new AssignmentStmt(pgm.stmts().new_tag(), id(index_var),init->clone()); pgm.stmts().ins_before(initassign,&do_stmt); } /// ... are there any escaping gotos in the loop Boolean escaping_gotos = _any_escaping_gotos(pgm,do_stmt); /// ... 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. if (escaping_gotos) { Symbol *new_loop_var = new VariableSymbol(index_var.name_ref(), index_var.type(),NOT_FORMAL,NOT_SAVED); pgm.symtab().rename_and_ins(new_loop_var); /// ... convert all old symbols to new ones Expression *myreplacement = id(*new_loop_var); for (Iterator<Statement> stmtscn = pgm.stmts().iterate_loop_body(&do_stmt); stmtscn.valid(); ++stmtscn) { Statement &stmt = stmtscn.current(); _subst_var_in_stmt(stmt,index_var,*myreplacement); } _subst_var_in_assert(do_stmt,index_var,*myreplacement); /// ... add iteration assignment of loop value Statement *assigner = new AssignmentStmt(pgm.stmts().new_tag(), id(index_var),replacement->clone()); _subst_var_in_stmt(*assigner,index_var,*myreplacement); assigner->lhs(id(index_var)); pgm.stmts().ins_after(assigner,&do_stmt); delete myreplacement; } else { /// ... if there are no escaping gotos, then we only need a last value at the end if (non_local_loop_index || _any_reached_uses(pgm,index_var,*do_stmt.follow_ref()->next_ref())) { _loop_index_last_val(pgm,index_var,do_stmt,*do_stmt.follow_ref()); } } do_stmt.init(new_init); do_stmt.limit( new_limit ); do_stmt.step( new_step ); /// ... Delete the copies. delete init; delete limit; delete step; /// ... We don't need this expression anymore--garbage collect it delete replacement; } /// 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 void eliminate_loop(ProgramUnit & pgm, Statement & do_stmt ) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); precalc_loop( pgm, do_stmt ); /// Expression *init = do_stmt.init().clone(); /// Expression *limit = do_stmt.limit().clone(); /// Expression *step = do_stmt.step().clone(); Expression *range = _loop_range( do_stmt ); if ((is_integer_constant(*range)) && (range->value() <= 1)) { Boolean zero_trip = (range->value() < 1); /// ... Get a reference to the index variable Symbol & index_var = do_stmt.index().symbol(); Statement *s; Expression *lhs, *rhs; /// ... Maybe needed if the index variable is used after the loop. lhs = id(index_var); if (zero_trip) rhs = do_stmt.init().clone(); else { rhs = simplify( add( do_stmt.init().clone(), do_stmt.step().clone() )); } s = new AssignmentStmt( pgm.stmts().new_tag(), lhs, rhs ); /// ... Add lastvalue assignment. pgm.stmts().ins_after( s, do_stmt.follow_ref() ); if (zero_trip) { /// ... Remove the DO loop and the statements inside of it since it is /// ... never executed. pgm.stmts().del( do_stmt, *do_stmt.follow_ref() ); } else { Expression *replacement = do_stmt.init().clone(); /// ... Loop through all statements within the loop body Iterator<Statement> stmts = pgm.stmts().iterate_loop_body(&do_stmt); /// ... Skip over the DO statement itself. for ( ++stmts; stmts.valid(); ++stmts) _subst_var_in_stmt(stmts.current(), index_var, *replacement); /// ... Delete the copies. delete replacement; /// ... Remove the DO loop, since it is only executed once. pgm.stmts().del( do_stmt ); } } delete range; } void peel_loop_first(ProgramUnit & pgm, Statement & do_stmt) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); /// ... Precalculate the DO loop if needed. precalc_loop( pgm, do_stmt ); if (!is_integer_constant(do_stmt.step()) || do_stmt.step().value() < 0) normalize_loop( pgm, do_stmt ); /// ... Get a copy of the lower bound of the loop. Expression *init = do_stmt.init().clone(); Expression *limit = do_stmt.limit().clone(); Expression *step = do_stmt.step().clone(); Expression *range = _loop_range( do_stmt ); Statement & if_stmt = pgm.stmts().ins_IF_after( gt( range, constant(0) ), do_stmt.prev_ref(), do_stmt.follow_ref() ); /// ... Modify the bounds to insure that the loops do not overlap. Expression *new_init = simplify( add( step->clone(), init->clone()) ); Expression *new_limit = init->clone(); /// ... Get a copy of the DO loop. List<Statement> *stmt_block; stmt_block = clone_loop(pgm, do_stmt, "PF"); /// ... Get a pointer to the new copy of the DO loop header. Statement *new_do = stmt_block->first_ref(); /// ... Put them back into the program in front of the original loop. pgm.stmts().ins_before(stmt_block, &do_stmt); new_do->limit( new_limit ); do_stmt.init( new_init ); delete init; delete limit; delete step; if (pgm.stmts().member(if_stmt)) simplify_control_flow( pgm, if_stmt ); if (pgm.stmts().member(*new_do)) eliminate_loop( pgm, *new_do ); if (pgm.stmts().member(do_stmt)) eliminate_loop( pgm, do_stmt ); } void peel_loop_first(ProgramUnit & pgm, Statement & do_stmt, int count) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); p_assert( count > 0, "amount to peel must be positive" ); /// ... Precalculate the DO loop if needed. precalc_loop( pgm, do_stmt ); if (!is_integer_constant(do_stmt.step()) || do_stmt.step().value() < 0) normalize_loop( pgm, do_stmt ); /// ... Perform special peeling if we only want the first iteration. if (count == 1) { peel_loop_first( pgm, do_stmt ); return; } List<Statement> *stmt_block; /// ... Get a copy of the DO loop. stmt_block = clone_loop (pgm, do_stmt, "PF"); /// ... Get a pointer to the new copy of the DO loop header. Statement *new_do = stmt_block->first_ref(); /// ... Put them back into the program in front of the original loop. pgm.stmts().ins_before(stmt_block, &do_stmt); /// ... Get a copy of the lower bound of the loop. Expression *init = do_stmt.init().clone(); Expression *limit = do_stmt.limit().clone(); Expression *step = do_stmt.step().clone(); /// ... Modify the bounds to insure that the loops do not overlap. Expression *new_init = simplify( add( mul( step->clone(), constant(count)), init->clone()) ); Expression *new_limit = simplify( intrinsic_call( _icall_id("MIN", pgm), comma( sub( add( constant(count), init->clone() ), constant(1) ), limit->clone() ))); new_do->limit( new_limit ); do_stmt.init( new_init ); delete init; delete limit; } /// Peel the last iteration off the loop void peel_loop_last(ProgramUnit & pgm, Statement & do_stmt) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); /// ... Precalculate the DO loop if needed. precalc_loop( pgm, do_stmt ); normalize_loop( pgm, do_stmt ); /// ... Get a copy of the DO loop. List<Statement> *stmt_block; stmt_block = clone_loop (pgm, do_stmt, "PL"); /// ... Get a pointer to the new copy of the DO loop header. Statement *new_do = stmt_block->first_ref(); /// ... Put them back into the program in front of the original loop. Statement *enddo_stmt = do_stmt.follow_ref(); pgm.stmts().ins_after(stmt_block, enddo_stmt); /// ... Get a copy of the lower bound of the loop. Expression *init = do_stmt.init().clone(); Expression *limit = do_stmt.limit().clone(); Expression *step = do_stmt.step().clone(); Symbol &index = do_stmt.index().symbol(); Expression *range = _loop_range( do_stmt ); Statement & if_stmt = pgm.stmts().ins_IF_after( gt( range, constant(0) ), enddo_stmt, new_do->follow_ref() ); /// ... Get the loop label of the peeled loop String loop_label = new_do->get_loop_name(); /// ... Change references to the loop index into usages of the upper loop bound Iterator<Statement> stmts = pgm.stmts().iterate_loop_body(new_do); /// ... 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 for ( ++stmts; stmts.valid(); ++stmts) { Statement & peel_st = stmts.current(); _subst_var_in_stmt(peel_st, index, *range); for (Mutator<Assertion> peel_aiter = peel_st.assertions(); peel_aiter.valid(); ++peel_aiter) { Assertion & el_assert = peel_aiter.current(); if (((el_assert.type() == AS_PRIVATEREFS) || (el_assert.type() == AS_READONLYREFS)) && (el_assert.arg_list_valid())) { /// ... list of parenthesized comma exprs for (Mutator<Expression> el_assert_eiter = el_assert.arg_list_guarded(); el_assert_eiter.valid(); ++el_assert_eiter) { p_assert(el_assert_eiter.current().op() == PAREN_OP, "PrivateRefs needs list of parenthesized COMMA_OPs"); /// ... Each is a PAREN_OP if (el_assert_eiter.current().expr_valid()) { Expression &e = el_assert_eiter.current().expr_guarded(); /// ... The parenthesized expr should be a CommaExpr: p_assert(e.op() == COMMA_OP, "PrivateRefs needs parenthesized COMMA_OPs"); const String & asrt_str = e.arg_list()[0].str_data(); /* String asrt_loop_name(asrt_str, 1, asrt_str.len() - 2); if (asrt_loop_name == loop_label) { */ if (asrt_str == loop_label) { el_assert_eiter.del(); } } if (el_assert.arg_list_guarded().entries() == 0) { peel_st.assertions().del(el_assert); } } } } } Expression *new_limit = simplify( sub( limit->clone(), constant(1) )); do_stmt.limit( new_limit ); // Delete the DO/END DO of the 1-iteration loop pgm.stmts().del(*new_do); delete init; delete limit; delete step; if (pgm.stmts().member(if_stmt)) simplify_control_flow( pgm, if_stmt ); } void peel_loop_last(ProgramUnit & pgm, Statement & do_stmt, int count) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); p_assert( count > 0, "count must be positive" ); if (count == 1) { peel_loop_last( pgm, do_stmt ); return; } /// ... Precalculate the DO loop if needed. precalc_loop( pgm, do_stmt ); normalize_loop( pgm, do_stmt ); List<Statement> *stmt_block; /// ... Get a copy of the DO loop. stmt_block = clone_loop (pgm, do_stmt, "PF"); /// ... Get a pointer to the new copy of the DO loop header. Statement *new_do = stmt_block->first_ref(); /// ... Put them back into the program in front of the original loop. pgm.stmts().ins_before(stmt_block, &do_stmt); /// ... Get a copy of the lower bound of the loop. Expression *init = do_stmt.init().clone(); Expression *limit = do_stmt.limit().clone(); /// ... Modify the bounds to insure that the loops do not overlap. Expression *new_init = simplify( intrinsic_call( _icall_id("MAX", pgm), comma( add( sub( limit->clone(), constant(count) ), constant(1) ), init->clone() ))); Expression *new_limit = simplify( sub( limit->clone(), constant(count) )); new_do->limit( new_limit ); do_stmt.init( new_init ); delete init; delete limit; } void precalc_loop(ProgramUnit & pgm, Statement & do_stmt) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); /// ... Get a reference to the index variable Symbol & index_var = do_stmt.index().symbol(); /// ... Get new copies of the DO's init, limit and step expressions. Expression *init = do_stmt.init().clone(); Expression *limit = do_stmt.limit().clone(); Expression *step = do_stmt.step().clone(); /// ... Coerce init, limit and step to the type of the loop index /// ... by applying intrinsic functions to the expressions /// ... (only if necessary) init = coerce(init, index_var.type().data_type(), pgm); limit = coerce(limit, index_var.type().data_type(), pgm); step = coerce(step, index_var.type().data_type(), pgm); /// ... If the bound expressions could have side effects, they must /// ... be precalculated. init = get_precalc(init, pgm, do_stmt, PRECALC_IF_SIDE_EFFECTS, "INIT"); limit = get_precalc(limit, pgm, do_stmt, PRECALC_IF_SIDE_EFFECTS, "LIMIT"); step = get_precalc(step, pgm, do_stmt, PRECALC_IF_SIDE_EFFECTS, "STEP"); /// ... Put them back into the statement. do_stmt.init( init ); do_stmt.limit( limit ); do_stmt.step( step ); RefSet<Symbol> *variant = loop_variant_vars( pgm, do_stmt ); RefSet<Symbol> *invariant = loop_invariant_vars( pgm, *variant ); if (! invariant_expression( do_stmt.init(), *invariant )) { do_stmt.init( get_precalc( do_stmt.init().clone(), pgm, do_stmt, PRECALC_ALWAYS, "INIT" )); } if (! invariant_expression( do_stmt.limit(), *invariant )) { do_stmt.limit( get_precalc( do_stmt.limit().clone(), pgm, do_stmt, PRECALC_ALWAYS, "LIMIT" )); } if (! invariant_expression( do_stmt.step(), *invariant )) { do_stmt.step( get_precalc( do_stmt.step().clone(), pgm, do_stmt, PRECALC_ALWAYS, "STEP" )); } delete variant; delete invariant; } void stripmine_horiz_loop(ProgramUnit & pgm, Statement & do_stmt, Expression *strip) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); precalc_loop( pgm, do_stmt ); if (!is_integer_constant(do_stmt.step()) || do_stmt.step().value() < 0) normalize_loop( pgm, do_stmt ); Expression *limit = do_stmt.limit().clone(); Expression *step = do_stmt.step().clone(); /// ... Get a reference to the index variable Symbol & index_var = do_stmt.index().symbol(); /// ... Get the index variable for the second loop. Symbol & new_index_var = pgm.symtab().rename_and_ins( index_var.clone() ); /// ... Calculate the new limit. Expression * new_limit = simplify( intrinsic_call( _icall_id("MIN", pgm), comma( sub( add( id(new_index_var), mul( strip->clone(), step->clone() )), constant(1)), limit ))); /// ... Build a new DO loop to be nested inside of the current loop. /// ... Statement & new_do_stmt = pgm.stmts().ins_DO_after( id(index_var), id(new_index_var), new_limit, step->clone(), &do_stmt, do_stmt.follow_ref()->prev_ref() ); do_stmt.index( id(new_index_var) ); do_stmt.step( simplify( mul( step, strip ))); } void stripmine_vert_loop(ProgramUnit & pgm, Statement & do_stmt, Expression *strip) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); precalc_loop( pgm, do_stmt ); if (!is_integer_constant(do_stmt.step()) || do_stmt.step().value() < 0) normalize_loop( pgm, do_stmt ); 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 Symbol & index_var = do_stmt.index().symbol(); /// ... Get the index variable for the second loop. Symbol & new_index_var = pgm.symtab().rename_and_ins( index_var.clone() ); /// ... Calculate the inner strip size. Expression *range = _loop_range( do_stmt ); Expression *inner_strip = simplify( intrinsic_call( _icall_id( "MAX", pgm ), comma( constant(1), div( range->clone(), strip->clone() )))); /// ... Compute the initial value and limit for the new DO loop. Expression * new_init = simplify( add( init->clone(), mul( id(new_index_var), inner_strip->clone() ))); Expression * new_limit = simplify( intrinsic_call( _icall_id("MIN", pgm), comma( limit->clone(), sub( add( new_init->clone(), inner_strip->clone() ), constant(1) )))); /// ... Build a new DO loop to be nested inside of the current loop. /// ... Statement & new_do_stmt = pgm.stmts().ins_DO_after( id(index_var), new_init, new_limit, step, &do_stmt, do_stmt.follow_ref()->prev_ref() ); do_stmt.index( id(new_index_var) ); do_stmt.init( constant(0) ); do_stmt.limit( simplify( sub( strip, constant(1) ) )); do_stmt.step( constant(1) ); } void unroll_loop(ProgramUnit & pgm, Statement & do_stmt, int count) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); /// ... Unroll the loop, maybe we need to normalize first. if (!is_integer_constant(do_stmt.step()) || do_stmt.step().value() != 1) return; Statement *first = do_stmt.next_ref(); Statement *last = do_stmt.follow_ref()->prev_ref(); /// ... If there are no statements in the loop body then this is a NO-OP. if (&do_stmt == last) return; precalc_loop( pgm, do_stmt ); /// ... Get a copy of the old step expression. Expression *step = do_stmt.step().clone(); /// ... Get a reference to the index variable Symbol & index_var = do_stmt.index().symbol(); for (int i = 1; i < count; ++i) { /// ... Get a copy of the DO loop body. List<Statement> *stmt_block = clone_loop (pgm, do_stmt, "UR"); cout<<"The loop body is"<<endl; stmt_block->print(cout); cout<<endl; Expression *replacement = simplify( add( id(index_var), mul( step->clone(), constant(i) ))); for (Iterator<Statement> stmts = *stmt_block; stmts.valid(); ++stmts) _subst_var_in_stmt(stmts.current(), index_var, *replacement); delete replacement; pgm.stmts().ins_before( stmt_block, do_stmt.follow_ref() ); } do_stmt.step( simplify( mul( step, constant(count) ) )); } void preroll_loop(ProgramUnit & pgm, Statement & do_stmt, int count) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); p_assert( count > 0, "count must be positive" ); /// ... Precalculate the DO loop if needed. precalc_loop( pgm, do_stmt ); if (!is_integer_constant(do_stmt.step()) || do_stmt.step().value() < 0) normalize_loop( pgm, do_stmt ); /// ... Get a copy of the lower bound of the loop. Expression *init = do_stmt.init().clone(); Expression *limit = do_stmt.limit().clone(); Expression *step = do_stmt.step().clone(); Expression *range = _loop_range( do_stmt ); /// ... Modify the bounds to insure that the loops do not overlap. Expression *new_limit = simplify( sub( add( init->clone(), intrinsic_call( _icall_id( "MOD", pgm ), comma( range->clone(), constant(count) ))), constant(1) )); Expression *new_init = simplify( add( step->clone(), new_limit->clone()) ); /// ... Get a copy of the DO loop. List<Statement> *stmt_block; stmt_block = clone_loop (pgm, do_stmt, "PR"); /// ... Get a pointer to the new copy of the DO loop header. Statement *new_do = stmt_block->first_ref(); /// ... Put them back into the program in front of the original loop. pgm.stmts().ins_before(stmt_block, &do_stmt); new_do->limit( new_limit ); do_stmt.init( new_init ); delete init; delete limit; delete step; Expression *new_range = _loop_range( *new_do ); if (is_integer_constant(*new_range) && new_range->value() > 0 && new_range->value() < 8) unroll_loop( pgm, *new_do, new_range->value() ); if (pgm.stmts().member(*new_do)) eliminate_loop( pgm, *new_do ); if (pgm.stmts().member(do_stmt)) eliminate_loop( pgm, do_stmt ); delete new_range; } void reverse_loop(ProgramUnit & pgm, Statement & do_stmt) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); /// ... Brute force approach, make sure we are stride 1, and precalc'd normalize_loop( pgm, do_stmt ); /// ... Get new copies of the DO's init, limit and step expressions, Expression *init = do_stmt.init().clone(); Expression *limit = do_stmt.limit().clone(); do_stmt.init( limit ); do_stmt.limit( init ); do_stmt.step( simplify( unary_minus( do_stmt.step().clone()))); } /// 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. List<Statement> * clone_loop(ProgramUnit & pgm, Statement & do_stmt, const String & suffix) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); /// ... Build suffix strings for later use const char * suffix_ptr(suffix); int suffix_len = strlen(suffix_ptr) + 3; char * suffix_buf = new char[suffix_len]; p_assert(suffix_buf, "Out of space in clone_loop"); suffix_buf[0] = '_'; /// ... Copy over suffix strcpy(suffix_buf + 1, suffix_ptr); /// ... Null out last character of buffer --suffix_len; suffix_buf[suffix_len] = '\0'; /// ... Build suffix1 in buffer --suffix_len; suffix_buf[suffix_len] = '1'; String suffix1(suffix_buf); /// ... Build suffix2 in buffer suffix_buf[suffix_len] = '2'; String suffix2(suffix_buf); delete [] suffix_buf; List<Statement> *stmt_block; KeyDatabase<String,StringElem> label_map; KeyDatabase<String,StringElem> new_label_map; stmt_block = pgm.stmts().copy(do_stmt, *(do_stmt.follow_ref())); Iterator<Statement> stmts = pgm.stmts().iterate_loop_body(&do_stmt); for ( ; stmts.valid(); ++stmts) { Statement & stmt = stmts.current(); if (stmt.stmt_class() == DO_STMT) { /// ... Find the first looplabel assertion (then later delete all that may exist) String* orig_name = new String(stmt.get_loop_name()); StringElem *new_name = new StringElem( *orig_name); *new_name += suffix1; label_map.ins(orig_name, new_name); for (Iterator<Assertion> a_iter = stmt.assertions(); a_iter.valid(); ++a_iter) { Assertion & assert = a_iter.current(); if (assert.type() == AS_LOOPLABEL) { stmt.assertions().del( assert ); } /// ... Replace the old loop name with new loop names if ((assert.type() == AS_PRIVATEREFS) || (assert.type() == AS_READONLYREFS)) { if (assert.arg_list_valid()) { Mutator<Expression> item_iter = assert.arg_list_guarded(); for ( ; item_iter.valid(); ++item_iter) { Expression & asrt_expr = item_iter.current(); String & asrt_str = asrt_expr.expr_guarded().arg_list()[0].str_data(); /* String label(asrt_str, 1, asrt_str.len()-2); String * flabel = label_map.find_ref(label); */ String * flabel = label_map.find_ref(asrt_str); if (flabel) { /* String xlabel = "'" + *flabel + "'"; StringConstExpr * new_label = new StringConstExpr ((const char *) xlabel); */ StringConstExpr * new_label = new StringConstExpr ((const char *) *flabel); asrt_expr.expr_guarded().arg_list().modify(0,new_label); } } } } } /// ... Make new loop name for this DO: original + <suffix>1 AssertLoopLabel *as = new AssertLoopLabel; as->string_arg_list_guarded().ins_last(new StringElem(*new_name)); stmt.assertions().ins_last(as); } } /// ... Now, append _<suffix>2 to the labels of the loops in the new nest Iterator<Statement> newstmts = stmt_block; for ( ; newstmts.valid(); ++newstmts) { Statement & stmt = newstmts.current(); if (stmt.stmt_class() == DO_STMT) { /// ... Find the first looplabel assertion (then later delete them all) String * orig_name = new String(stmt.get_loop_name()); StringElem *new_name = new StringElem( *orig_name); *new_name += suffix2; new_label_map.ins(orig_name, new_name); for (Iterator<Assertion> a_iter = stmt.assertions(); a_iter.valid(); ++a_iter) { Assertion & assert = a_iter.current(); if (assert.type() == AS_LOOPLABEL) { stmt.assertions().del( assert ); } /// ... Replace the old loop name with new loop names if ((assert.type() == AS_PRIVATEREFS) || (assert.type() == AS_READONLYREFS)) { if (assert.arg_list_valid()) { Mutator<Expression> item_iter = assert.arg_list_guarded(); for ( ; item_iter.valid(); ++item_iter) { Expression & asrt_expr = item_iter.current(); String & asrt_str = asrt_expr.expr_guarded().arg_list()[0].str_data(); /* String label(asrt_str, 1, asrt_str.len()-2); String * flabel = new_label_map.find_ref(label); */ String * flabel = new_label_map.find_ref(asrt_str); if (flabel) { /* String xlabel = "'" + *flabel + "'"; StringConstExpr * new_label = new StringConstExpr ((const char *) xlabel); */ StringConstExpr * new_label = new StringConstExpr ((const char *) *flabel); asrt_expr.expr_guarded().arg_list().modify(0,new_label); } } } } } /// ... Make new loop name for this DO: original + <suffix>2 AssertLoopLabel *as = new AssertLoopLabel; StringElem * as_elem = new StringElem(*orig_name); *as_elem += suffix2; as->string_arg_list_guarded().ins_last(as_elem); stmt.assertions().ins_last(as); } } return stmt_block; } List<Statement> * clone_loop_body(ProgramUnit & pgm, Statement & do_stmt, const String & suffix) { p_assert(do_stmt.stmt_class() == DO_STMT, "not a DO loop"); /// ... Build suffix strings for later use const char * suffix_ptr(suffix); int suffix_len = strlen(suffix_ptr) + 3; char * suffix_buf = new char[suffix_len]; p_assert(suffix_buf, "Out of space in clone_loop"); suffix_buf[0] = '_'; /// ... Copy over suffix strcpy(suffix_buf + 1, suffix_ptr); /// ... Null out last character of buffer --suffix_len; suffix_buf[suffix_len] = '\0'; /// ... Build suffix1 in buffer --suffix_len; suffix_buf[suffix_len] = '1'; String suffix1(suffix_buf); /// ... Build suffix2 in buffer suffix_buf[suffix_len] = '2'; String suffix2(suffix_buf); delete [] suffix_buf; List<Statement> *stmt_block; KeyDatabase<String,StringElem> label_map; KeyDatabase<String,StringElem> new_label_map; stmt_block = pgm.stmts().copy(*(do_stmt.next_ref()), *(do_stmt.follow_ref()->prev_ref())); Iterator<Statement> stmts = pgm.stmts().iterate_loop_body(&do_stmt); for ( ++stmts; /// ... Skip the DO stmt stmts.valid(); ++stmts) { Statement & stmt = stmts.current(); if (stmt.stmt_class() == DO_STMT) { /// ... Find the first looplabel assertion (then later delete all that may exist) String* orig_name = new String(stmt.get_loop_name()); StringElem *new_name = new StringElem( *orig_name); *new_name += suffix1; label_map.ins(orig_name, new_name); for (Iterator<Assertion> a_iter = stmt.assertions(); a_iter.valid(); ++a_iter) { Assertion & assert = a_iter.current(); if (assert.type() == AS_LOOPLABEL) { stmt.assertions().del( assert ); } /// ... Replace the old loop name with new loop names if ((assert.type() == AS_PRIVATEREFS) || (assert.type() == AS_READONLYREFS)) { if (assert.arg_list_valid()) { Mutator<Expression> item_iter = assert.arg_list_guarded(); for ( ; item_iter.valid(); ++item_iter) { Expression & asrt_expr = item_iter.current(); String & asrt_str = asrt_expr.expr_guarded().arg_list()[0].str_data(); /* String label(asrt_str, 1, asrt_str.len()-2); String * flabel = label_map.find_ref(label); */ String * flabel = label_map.find_ref(asrt_str); if (flabel) { /* String xlabel = "'" + *flabel + "'"; StringConstExpr * new_label = new StringConstExpr ((const char *) xlabel); */ StringConstExpr * new_label = new StringConstExpr ((const char *) *flabel); asrt_expr.expr_guarded().arg_list().modify(0,new_label); } } } } } /// ... Make new loop name for this DO: original + <suffix>1 AssertLoopLabel *as = new AssertLoopLabel; as->string_arg_list_guarded().ins_last(new StringElem(*new_name)); stmt.assertions().ins_last(as); } } /// ... Now, append _<suffix>2 to the labels of the loops in the new nest Iterator<Statement> newstmts = stmt_block; for ( ; newstmts.valid(); ++newstmts) { Statement & stmt = newstmts.current(); if (stmt.stmt_class() == DO_STMT) { /// ... Find the first looplabel assertion (then later delete them all) String * orig_name = new String(stmt.get_loop_name()); StringElem *new_name = new StringElem( *orig_name); *new_name += suffix2; new_label_map.ins(orig_name, new_name); for (Iterator<Assertion> a_iter = stmt.assertions(); a_iter.valid(); ++a_iter) { Assertion & assert = a_iter.current(); if (assert.type() == AS_LOOPLABEL) { stmt.assertions().del( assert ); } /// ... Replace the old loop name with new loop names if ((assert.type() == AS_PRIVATEREFS) || (assert.type() == AS_READONLYREFS)) { if (assert.arg_list_valid()) { Mutator<Expression> item_iter = assert.arg_list_guarded(); for ( ; item_iter.valid(); ++item_iter) { Expression & asrt_expr = item_iter.current(); String & asrt_str = asrt_expr.expr_guarded().arg_list()[0].str_data(); /* String label(asrt_str, 1, asrt_str.len()-2); String * flabel = new_label_map.find_ref(label); */ String * flabel = new_label_map.find_ref(asrt_str); if (flabel) { /* String xlabel = "'" + *flabel + "'"; StringConstExpr * new_label = new StringConstExpr ((const char *) xlabel); */ StringConstExpr * new_label = new StringConstExpr ((const char *) *flabel); asrt_expr.expr_guarded().arg_list().modify(0,new_label); } } } } } /// ... Make new loop name for this DO: original + <suffix>2 AssertLoopLabel *as = new AssertLoopLabel; StringElem * as_elem = new StringElem(*orig_name); *as_elem += suffix2; as->string_arg_list_guarded().ins_last(as_elem); stmt.assertions().ins_last(as); } } return stmt_block; } /// Begin OpenMP Modification Boolean is_perfect_nest(Statement * do_stmt) { Statement *start,*current; Statement *stop,*end; start = current = do_stmt; stop = end = do_stmt->follow_ref(); while( (current->stmt_class() == DO_STMT) &&(current->follow_ref() == end)) { current = current->next_ref(); end = end->prev_ref(); while (end->stmt_class() == LABEL_STMT) end = end->prev_ref(); } while( (current != stop) && (end != start)) { if (current->stmt_class() == DO_STMT) return False; if (end->stmt_class() == ENDDO_STMT) return False; current = current->next_ref(); end = end->prev_ref(); } return True; } /// End OpenMP Modification

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:05:58 2005