Polaris: lambda_util.cc Source File

lambda_util.cc Go to the documentation of this file. /// /// #include "../ProgramUnit.h" #include "../Collection/List.h" #include "../Collection/RefDatabase.h" #include "../Expression/LambdaCallExpr.h" #include "../Expression/UnaryExpr.h" #include "../Expression/replace.h" #include "../Info.h" #include "../macros.h" #include "../Wildcard/AnyOfType.h" #include "../Wildcard/WildcardOr.h" #include "precalc_util.h" #include "lambda_util.h" template class Info<int>; template class Info<LambdaInfo *>; /// Definitions for lambda call replacement code enum ARG_EVAL_TYPE { NON_STRICT, /// ... Argument need not be evaluated STRICT /// ... Argument must be evaluated }; enum STRICT_BOOL { PRESERVE_TYPE = 0, MAKE_NON_STRICT = 1 }; typedef RefDatabase<int, Expression>ArgDatabase; template class Info<ArgDatabase *>; /// An ArgExprElem points to an ArgNumberExpr for a formal reference. /// It also contains the type of evaluation for this reference. /// /// If an ArgExprElem is marked LAZY, it means that this formal reference /// need not be evaluated. /// /// If an ArgExprElem is marked STRICT, it means that this formal reference /// must be evaluated. class ArgExprElem : public Listable { private: Expression * _e; /// ... Pointer to expression ARG_EVAL_TYPE _eval_type; /// ... Type of argument evaluation friend inline ostream & operator << (ostream & o, const ArgExprElem & h) { h.print(o); return o; } public: ArgExprElem(); ArgExprElem(Expression & e, ARG_EVAL_TYPE eval_type); ArgExprElem(const ArgExprElem & other); ArgExprElem & operator = (const ArgExprElem & other); virtual ~ArgExprElem(); Expression & expr() const; ARG_EVAL_TYPE eval_type() const; void eval_type(ARG_EVAL_TYPE change_type); virtual void print(ostream & o) const; virtual Listable *listable_clone() const; }; ArgExprElem::ArgExprElem() { /// ... nothing to do } ArgExprElem::ArgExprElem(Expression & e, ARG_EVAL_TYPE eval_type) { _e = &e; _eval_type = eval_type; } ArgExprElem::ArgExprElem(const ArgExprElem & other) { *this = other; } ArgExprElem & ArgExprElem::operator = (const ArgExprElem & other) { _e = other._e; _eval_type = other._eval_type; return *this; } ArgExprElem::~ArgExprElem() { /// ... nothing to do } Expression & ArgExprElem::expr() const { return *_e; } ARG_EVAL_TYPE ArgExprElem::eval_type() const { return _eval_type; } void ArgExprElem::eval_type(ARG_EVAL_TYPE change_type) { _eval_type = change_type; } void ArgExprElem::print(ostream & o) const { _e->print(o); o << ": "; if (_eval_type == NON_STRICT) o << "Non-Strict"; else o << "Strict"; } Listable * ArgExprElem::listable_clone() const { return new ArgExprElem(*this); } template class TypedCollection<ArgExprElem>; template class List<ArgExprElem>; template ostream & operator << (ostream &, const List<ArgExprElem> &); template class Assign<ArgExprElem>; template class Iterator<ArgExprElem>; template class Mutator<ArgExprElem>; /// A CollectPair is a pair of an owned list of formal expression /// references and a replacement pattern. class CollectPair { public: Expression &pattern; List<ArgExprElem> list; CollectPair(Expression & replacement_pattern); void absorb(CollectPair * absorbed, STRICT_BOOL lazy = PRESERVE_TYPE); }; CollectPair::CollectPair(Expression & replacement_pattern) :pattern(replacement_pattern) { /// ... Nothing to do } /// Miscellaneous class functions /// Absorb a CollectPair into this object void CollectPair::absorb(CollectPair * absorbed, STRICT_BOOL lazy GIV(PRESERVE_TYPE)) { /// ... Grab each ArgExprElem from the CollectPair to be absorbed for (Mutator<ArgExprElem> list_iter = absorbed->list; list_iter.valid(); ++list_iter) { /// ... Grab current element from list ArgExprElem *grabbed = list_iter.grab(); /// ... Override grabbed element to be evaluated non-strictly if /// ... requested if (lazy == MAKE_NON_STRICT) grabbed->eval_type(NON_STRICT); /// ... Insert grabbed element into this object's formal list list.ins_last(grabbed); } /// ... Delete other object delete absorbed; } template class Info<CollectPair *>; /* collect_lambda_formals summarizes the formal/actual substitutions needed to evaluate an expression wherever those subtitutions arise due to calls to statement functions. A close reading of F77 sections 6.6, 10.1,2,4, and 15.4 is recommended before tinkering (Jaxon)... and a sanity check (Grout). A LambdaCallExpr contains a lambda expression (the pattern into which substitution is made) and a parameter expression (a list of arguments which are substituted into the pattern). collect_lambda_formals is originally passed the lambda expression of the LambdaCallExpr currently being replaced. All the formal expressions, represented by ArgNumberExprs, which correspond to the LambdaCallExpr currently being replaced are precisely those within the lambda expression which are not hidden from view by a nested LambdaCallExpr. A LambdaCallExpr hides any ArgNumberExprs found in its lambda expression from view (all these must correspond to that or a more deeply nested LambdaCallExpr), but does not hide any unhidden ArgNumberExprs found in its parameter expression from view (all those must correspond to the LambdaCallExpr currently being evaluated). Treatment of non-strict operators is discussed in the F77 sections mentioned above. */ /// (Note: This function is a traverse_action_func_t function) void collect_lambda_formals(const Expression & e, ExtraInfo & extra_info) { /// ... Point to CollectPair CollectPair & collect_pair = *((Info<CollectPair * >&) extra_info).data(); switch (e.op()) { case ARG_OP: { /// ... Create an argument expression element ArgExprElem *arg_e = new ArgExprElem( CASTAWAY(Expression &) e, STRICT); /// ... Insert the argument expression element into formal_list collect_pair.list.ins_last(arg_e); break; } case LAMBDA_CALL_OP: { /// ... Create a new collect pair CollectPair *new_collect_pair = new CollectPair(collect_pair.pattern); /// ... Recursively invoke collect_lambda_formals on parameter /// ... subexpression (whose unhidden lambda call args, if any, /// ... are ours) Info<CollectPair *> inf(new_collect_pair); traverse(CASTAWAY(Expression &) e.arg_list()[1], new_collect_pair->pattern, collect_lambda_formals, inf, NON_RECURSIVE_REPLACE, PREORDER_REPLACE); /// ... Absorb the new collect_pair into the existing one collect_pair.absorb(new_collect_pair); break; } case MULT_OP: case OR_OP: case AND_OP: { /// ... Create a new collect pair CollectPair *new_collect_pair = new CollectPair(collect_pair.pattern); /// ... Recursively invoke collect_lambda_formals on subexpressions for (Iterator<Expression> expr_iter = e.arg_list(); expr_iter.valid(); ++expr_iter) { Info<CollectPair *> inf(new_collect_pair); traverse(expr_iter.current(), new_collect_pair->pattern, collect_lambda_formals, inf, NON_RECURSIVE_REPLACE, PREORDER_REPLACE); } /// ... Absorb the new collect_pair into the existing one, making /// ... the new variable references NON_STRICT collect_pair.absorb(new_collect_pair, MAKE_NON_STRICT); } break; default: break; } return; } /// Replace an ArgNumberExpr with a clone from the corresponding data /// in the RefDatabase. /// Replace a LambdaCallExpr with itself to prevent further checking of its /// subexpressions Expression * replace_lambda_call_expr(Expression * e, ExtraInfo & extra_info) { static AnyOfType *lambda_pattern = new AnyOfType(LAMBDA_CALL_OP); static AnyOfType *arg_pattern = new AnyOfType(ARG_OP); static WildcardOr *replace_pattern = new WildcardOr(lambda_pattern, arg_pattern); Expression * return_expr; /// ... If lambda call, recursively examine its parameter expression switch(e->op()) { case LAMBDA_CALL_OP: { Assign<Expression> expr_as(e->arg_list().assign(1)); expr_as = replace(e->arg_list().pull(1), *replace_pattern, replace_lambda_call_expr, extra_info, NON_RECURSIVE_REPLACE, PREORDER_REPLACE); return_expr = e; break; } default: { /// ... Point at argument map ArgDatabase & argument_map = *((Info<ArgDatabase *>&) extra_info).data(); Expression *reference_ptr = argument_map.find_ref(e->value()); p_assert(reference_ptr, "Missing argument in replace_lambda_call_expr"); /// ... Delete the old expression delete e; /// ... Return a clone to caller return_expr = reference_ptr->clone(); } } return return_expr; } /// replace_lambda_call returns the fully-substituted lambda expression /// from LAMBDA_CALL expression e. Expression * replace_lambda_call(Expression * e, ExtraInfo & extra_info) { /// ... patterns for LAMBDA_CALL replacement static AnyOfType *lambda_pattern = new AnyOfType(LAMBDA_CALL_OP); static AnyOfType *arg_pattern = new AnyOfType(ARG_OP); static AnyOfType *mult_pattern = new AnyOfType(MULT_OP); static AnyOfType *OR_pattern = new AnyOfType(OR_OP); static AnyOfType *AND_pattern = new AnyOfType(AND_OP); static WildcardOr *logical_pattern = new WildcardOr(OR_pattern, AND_pattern); static WildcardOr *non_strict_pattern = new WildcardOr(mult_pattern, logical_pattern); static WildcardOr *replace_pattern = new WildcardOr(lambda_pattern, arg_pattern); static WildcardOr *collect_pattern = new WildcardOr(replace_pattern, non_strict_pattern); /// ... Retrieve parameters from argument LambdaInfo & arg_map = *((Info<LambdaInfo * >&) extra_info).data(); ProgramUnit & pgm = *arg_map.program_ref; Statement & s = *arg_map.stmt_ref; LC_TYPE lc_type = arg_map.lc_type; LambdaCallExpr & lambda_call_expr = *(LambdaCallExpr *) e; /// ... Reinvoke recursive search on the parameter expression if (lambda_call_expr.parameters_valid()) { Assign<Expression> lambda_as(lambda_call_expr.arg_list().assign(1)); lambda_as = replace(lambda_call_expr.arg_list().pull(1), *lambda_pattern, replace_lambda_call, extra_info, RECURSIVE_REPLACE, PREORDER_REPLACE); } /// ... Set up list to collect data CollectPair collect_pair(*collect_pattern); /// ... Collect lambda formals from lambda expression, grabbing lambda /// ... expression out of its containing list Expression *repl_lambda_expr = lambda_call_expr.arg_list().pull(0); Info<CollectPair *> inf(&collect_pair); traverse(*repl_lambda_expr, collect_pair.pattern, collect_lambda_formals, inf, NON_RECURSIVE_REPLACE, PREORDER_REPLACE); /// ... Define the argument map ArgDatabase argument_map; /// ... Define the list of precalculated ID node prototypes List<Expression>ID_prototype_list; /// ... Set the initial argument reference number int arg_num = 1; if (lambda_call_expr.parameters_valid()) /// ... Iterate over the LAMBDA_CALL's parameter expression (which may /// ... have been changed by earlier LAMBDA_CALLs) for (Iterator<Expression> expr_iter = lambda_call_expr.parameters_guarded().arg_list(); expr_iter.valid(); ++expr_iter) { /// ... Grab corresponding arguments from collect_pair to /// ... formal_list List<ArgExprElem> formal_list; for (Mutator<ArgExprElem> elem_iter = collect_pair.list; elem_iter.valid(); ++elem_iter) { if (elem_iter.current_valid()) { if (elem_iter.current().expr().value() == arg_num) formal_list.ins_last(elem_iter.pull()); } } /// ... Find correct actual parameter Expression *actual_parm = &expr_iter.current(); while (actual_parm->op() == PAREN_OP) actual_parm = &actual_parm->expr_guarded(); /// ... Handle actual parameter cases switch (actual_parm->op()) { case INTEGER_CONSTANT_OP: case REAL_CONSTANT_OP: case COMPLEX_OP: case ID_OP: { /// ... Handle constant and ID actual parameters. Insert /// ... reference to actual parameter into argument map argument_map.ins(arg_num, *actual_parm); break; } default: { /// ... If there is more than one formal reference to /// ... parameter, or there is only one non-strict /// ... reference which is not side-effect free, /// ... precalculate parameter. if ((formal_list.entries()>1) || ((formal_list.entries() == 1) && ((formal_list[0].eval_type() == NON_STRICT) && (!actual_parm->is_side_effect_free())))) { /// ... Precalculate parameter, getting an ID node in /// ... return Expression *ID_prototype = get_precalc(actual_parm->clone(), pgm, s); /// ... Put ID node on owning list (for later cleanup) ID_prototype_list.ins_last(ID_prototype); /// ... Insert reference to ID node prototype into /// ... argument map. argument_map.ins(arg_num, *ID_prototype); } else { /// ... Insert reference to actual parameter into /// ... argument map. argument_map.ins(arg_num, *actual_parm); } } } /// ... Increment argument number ++arg_num; } /// ... Substitute all arguments in lambda expression. Use preorder search, /// ... a wildcard which matches on ArgNumberExprs and LambdaCallExprs, and /// ... non-recursion. { Info<ArgDatabase *> inf(&argument_map); repl_lambda_expr = replace(repl_lambda_expr, *replace_pattern, replace_lambda_call_expr, inf, NON_RECURSIVE_REPLACE, PREORDER_REPLACE); } /// ... Simplification is too dangerous here when inlining (where not /// ... all variables with the same name are the same!) /// ... If this is a statement function call, simplify fully-substituted /// ... lambda expression before return and put parentheses around the /// ... expression to prevent inadvertant call-by-reference access if (lc_type == STMT_FUNCTION_CALL) { repl_lambda_expr = simplify(repl_lambda_expr); repl_lambda_expr = new UnaryExpr(PAREN_OP, repl_lambda_expr->type(), repl_lambda_expr); } return repl_lambda_expr; } /// remove_lambda_calls removes all LAMBDA_CALL expressions in expression /// tree e, possibly inserting assignment(s) to precalc_variable(s) before /// stmt of pgm. Precalculation is avoided for constant expressions (IDs /// are constant thanks to F77 pg 6-15 ln 55!) and for formals referenced /// once or not at all. Expression * remove_lambda_calls(Expression * e, LambdaInfo & lambda) { /// ... pattern for LAMBDA_CALL replacement static AnyOfType lambda_pattern(LAMBDA_CALL_OP); /// ... Call replace to recursively replace LAMBDA_CALL expressions Info<LambdaInfo *> inf(&lambda); return replace(e, lambda_pattern, replace_lambda_call, inf, RECURSIVE_REPLACE, PREORDER_REPLACE); } /// The scanner turns statement function references into LAMBDA_CALLs to a /// copy of the statement function definition. The bound variables have /// no names; they are identified positionally. A LAMBDA_CALL node /// resembles a FUNCTION_CALL node, with the function ID replaced by the /// statement function definition. /// Remove all statement functions from program and rebuild in-out refs void remove_all_statement_functions(ProgramUnit & pgm) { /// ... Initialize LambdaInfo object LambdaInfo lambda(NULL, NULL, STMT_FUNCTION_CALL); lambda.program_ref = &pgm; /// ... Iterate over statements for (Iterator<Statement> stmt_iter = pgm.stmts().iterator(); stmt_iter.valid(); ++stmt_iter) { Statement *stmt_ref = &stmt_iter.current(); lambda.stmt_ref = stmt_ref; /// ... Iterate over expressions and remove statement functions for (Mutator<Expression> expr_mutr = stmt_ref->iterate_expressions(); expr_mutr.valid(); ++expr_mutr) { if (expr_mutr.current_valid()) { Assign<Expression> expr_as(expr_mutr.assign()); expr_as = remove_lambda_calls(expr_mutr.pull(), lambda); } } /// ... Rebuild statement references stmt_ref->build_refs(); } }

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