Polaris: expression_util.cc Source File

expression_util.cc Go to the documentation of this file. /// /// #include "expression_util.h" #include "../Expression/Expression.h" #include "../Expression/UnaryExpr.h" #include "../Symbol/Symbol.h" #include "../Symbol/VariableSymbol.h" #include "../ArrayDims.h" #include "../Monotonicity.h" #include "../Range/StmtRanges.h" #include "../Range/Relation.h" #include "../Statement/Statement.h" #include "../Traverser.h" #include "../macros.h" /// is_expr_variable /// /// This routine returns True if a variable appears somewhere in the /// given expression. Boolean is_expr_variable(const Expression & e) { if (e.op() == ID_OP) return True; for (Iterator<Expression> iter = e.arg_list(); iter.valid(); ++iter) { if (is_expr_variable(iter.current())) return True; } return False; } /// is_var_in_expr /// Return true if the given variable occurs somewhere within the given /// expression. Boolean is_var_in_expr(const Expression & e, const Symbol & var) { if (e.op() == ID_OP) return (&e.symbol() == &var); for (Iterator<Expression> iter = e.arg_list(); iter.valid(); ++iter) { if (is_var_in_expr(iter.current(), var)) return True; } return False; } /// contains_func_call /// Return TRUE if the given statement contains a function call Boolean contains_func_call(const Statement & stmt) { Iterator<Expression> iter = (CASTAWAY(Statement &) stmt).iterate_expressions(); for (; iter.valid(); ++iter) if (!iter.current().is_side_effect_free()) return True; return False; } /// is_int_scalar /// Return true if the given symbol is an integer scalar variable. Boolean is_int_scalar(const Symbol & sym) { return (sym.sym_class() == VARIABLE_CLASS && sym.type().data_type() == INTEGER_TYPE && !sym.is_array()); } /// replace_parameters /// Return an expression will all parameter replaced by there values. /// The function takes ownership of the expression and give ownership /// of the resulting expression. Expression * replace_parameters(Expression *expr) { if (! expr) return 0; if (expr->op() == ID_OP) { if (expr->symbol().sym_class() == SYMBOLIC_CONSTANT_CLASS) { Expression *old_subst = expr->symbol().expr_ref()->clone(); Expression *new_subst = replace_parameters(old_subst); delete expr; return new_subst; } } else { List<Expression> & args = expr->arg_list(); for (Mutator<Expression> mutr = args; mutr.valid(); ++mutr) { Assign<Expression> expr_as(mutr.assign()); expr_as = replace_parameters( mutr.pull() ); } } return expr; } /// Return the expression which is the stride due to the given /// identifier (given as an IDExpr). This is the stride assuming /// the index value advances by 1. Assuming the index is "I", /// the method is to substitute "I+1" for "I" in the expression /// and subtract. Note that if the result is a function of I, /// then the stride is not constant, but varies with the value /// of I. Expression * extract_stride( Expression * expr, const Expression & index_id ) { Expression * plus_one = substitute_var( expr->clone(), *(index_id.base_variable_ref()), *add( index_id.clone(), constant(1) ) ); return simplify( sub( plus_one, expr->clone() ) ); } /// Linearize the given expression, and offset the subscript /// expression so that subscript 0 represents the first element /// of the array. Expression * linearize_zero_registered( Expression * expr, VariableSymbol & sym ) { /// ... Get the dimension information for the symbol ArrayDims & src_dim = sym.dim(); int src_dims = src_dim.entries(); List<Expression> & src_subs_list = expr->arg_list(); /// ... Calculate initial offset Expression *src_exl; Expression *src_exu; Expression *offset; if (src_dims>1) { src_exl = src_dim[src_dims - 1].lower_ref(); if (src_exl) src_exl = src_exl->clone(); else src_exl = constant(1); /// ... Absorb src_exl as subexpression of offset offset = sub(src_subs_list[src_dims - 1].clone(), src_exl); for (int i = src_dims - 2; i>0; --i) { src_exl = src_dim[i].lower_ref(); if (src_exl) src_exl = src_exl->clone(); else src_exl = constant(1); src_exu = src_dim[i].upper_ref(); if (src_exu) src_exu = src_exu->clone(); else src_exu = constant(1); /// ... Absorb src_exl and src_exu as subexpressions of offset offset = add(mul(add(sub(src_exu, src_exl), constant(1)), offset), sub(src_subs_list[i].clone(), src_exl->clone())); } } else { offset = constant(0); } src_exl = src_dim[0].lower_ref(); if (src_exl) src_exl = src_exl->clone(); else src_exl = constant(1); src_exu = src_dim[0].upper_ref(); if (src_exu) src_exu = src_exu->clone(); else src_exu = constant(1); /// ... Absorb src_exl and src_exu as subexpressions of offset offset = add(mul(add(sub(src_exu, src_exl), constant(1)), offset), sub(src_subs_list[0].clone(), src_exl->clone())); return simplify(offset); } /// Give the offset in elements (translated to making zero the first /// element) of the last array element Expression * last_element_offset ( VariableSymbol & sym ) { /// ... Get the dimension information for the symbol ArrayDims & src_dim = sym.dim(); int src_dims = src_dim.entries(); /// ... Calculate initial offset Expression *src_exl; Expression *src_exu; Expression *offset; if (src_dims>1) { src_exu = src_dim[src_dims - 1].upper_ref(); /// ... If the upper bound of the array is unknown, /// ... pass along that fact to the caller. if (src_exu == 0) return omega(); src_exl = src_dim[src_dims - 1].lower_ref(); if (src_exl) src_exl = src_exl->clone(); else src_exl = constant(1); /// ... Absorb src_exl as subexpression of offset offset = sub(src_exu->clone(), src_exl); for (int i = src_dims - 2; i>0; --i) { src_exl = src_dim[i].lower_ref(); if (src_exl) src_exl = src_exl->clone(); else src_exl = constant(1); src_exu = src_dim[i].upper_ref(); if (src_exu) src_exu = src_exu->clone(); else src_exu = constant(1); /// ... Absorb src_exl and src_exu as subexpressions of offset offset = add(mul(add(sub(src_exu, src_exl), constant(1)), offset), sub(src_exu->clone(), src_exl->clone())); } } else { offset = constant(0); } src_exl = src_dim[0].lower_ref(); if (src_exl) src_exl = src_exl->clone(); else src_exl = constant(1); src_exu = src_dim[0].upper_ref(); if (src_exu) src_exu = src_exu->clone(); else src_exu = constant(1); /// ... Absorb src_exl and src_exu as subexpressions of offset offset = add(mul(add(sub(src_exu, src_exl), constant(1)), offset), sub(src_exu->clone(), src_exl->clone())); return simplify(offset); } /// Given an expr which is (-1)*a, change into -a Expression * _replace_mul_minus_one (Expression *expr) { /// ... First, get rid of the -1 for (Mutator<Expression> mutexpr = expr->arg_list(); mutexpr.valid(); ++mutexpr) { if ((mutexpr.current().op() == INTEGER_CONSTANT_OP) && (mutexpr.current().value() == -1)) { mutexpr.del(); } } /// ... Now, pull the first sub-expression of expr /// ... so that we can replace it with "UnaryMinus(expr)" Mutator<Expression> mutexpr2 = expr->arg_list(); Assign<Expression> asexpr2(mutexpr2.assign()); Expression *expr2 = mutexpr2.pull(); Expression *new_expr = new UnaryExpr(U_MINUS_OP, expr2->type(), expr2); asexpr2 = new_expr; return expr; } /// Boolean function used for Traverser in replace_mul_minus_one( expr ) /// below. Boolean _is_mul_minus_one (const Expression & expr) { if (expr.op() == MULT_OP) { for (Iterator<Expression> ex_iter = expr.arg_list(); ex_iter.valid(); ++ex_iter) { if ((ex_iter.current().op() == INTEGER_CONSTANT_OP) && (ex_iter.current().value() == -1)) { /// ... Multiplying by -1 return True; } } return False; } else { return False; } } /// Replace (-1)*expr with -expr wherever it appears in the expr Expression * replace_mul_minus_one( Expression * expr ) { Expression * newexpr; for (Traverser trav(*expr, _is_mul_minus_one); trav.valid(); ++trav) { /// ... Found a MULTIPLY by -1 if (!trav.top_level()) { Assign<Expression> asexpr(trav.assign()); asexpr = _replace_mul_minus_one(trav.pull()); } else { newexpr = _replace_mul_minus_one(expr); return replace_mul_minus_one( newexpr ); } } return expr; } Monotonicity * test_monotonicity (RangeAccessor & range_acc, Symbol & index, Expression * stride, Expression * expr) { Monotonicity * mono = new Monotonicity( ); if (is_var_in_expr( *expr, index )) { mono->set_varying(); /// ... Form the possible new stride expression /// ... new_stride = start(I = I+loop_stride) - start(I) Expression *index_plus_stride = add(id(index), stride->clone()); Expression * expr_stride = simplify(sub(substitute_var(expr->clone(), index, *index_plus_stride), expr->clone())); /// ... Do a cheap comparison, if possible if (expr_stride->op() == INTEGER_CONSTANT_OP) { int val = expr_stride->value(); if (val < 0) { mono->set_negative(); } else if (val > 0) { mono->set_positive(); } else { /// ... val == 0 mono->set_constant(); } return mono; } /// ... Compare the expression with 0 Relation rel = range_acc.compare(*expr_stride, *constant(0)); delete index_plus_stride; delete expr_stride; if (rel.is_less_than()) { mono->set_negative(); } else if (rel.is_greater_than()) { mono->set_positive(); } else { mono->set_unknown_dir(); } // /// ... monotonicity unknown - try recursive approach // List<Monotonicity> mono_list; // for (Iterator<Expression> iter = expr.arg_list(); // iter.valid(); // ++iter) { /// // /// ... Make a list of the monotonicity of each sub-expression // mono_list.ins_last(test_monotonic(range_acc, // index, // stride, // &(iter.current()))); // } // switch (expr->op()) // { // case DIV_OP: // case MUL_OP: // { // bool constant = true; // bool pos = true; // bool unknown_dir = false; // for (Iterator<Monotonicity> m_iter = mono_list; // m_iter.valid(); // ++m_iter) { /// // Monotonicity & mv = m_iter.current(); /// // if (mv.varying() || mv.unknown_mov()) { // constant = false; // } // if (mv.negative()) positive = !positive; // if (mv.unknown_dir()) unknown_dir = true; // } // if (constant) { // mono->set_constant(); // } // if (unknown_dir) { // mono->set_unknown_dir(); // } else { // if (positive) { // mono->set_positive(); // } else { // mono->set_negative(); // } // } // break; // } // case ADD_OP: // { // int pos = 0; // int neg = 0; // bool constant = true; // bool unknown_dir = false; // for (Iterator<Monotonicity> m_iter = mono_list; // m_iter.valid(); // ++m_iter) { /// // Monotonicity & mv = m_iter.current(); /// // if (mv.varying() || mv.unknown_mov()) { // constant = false; // } // if (mv.negative()) ++neg; // if (mv.positive()) ++pos; // if (mv.unknown_dir()) unknown_dir = true; // } // if (constant) { // mono->set_constant(); // } // if (unknown_dir) { // mono->set_unknown_dir(); // } else { // if ((pos == 0) && (neg > 0)) { // mono->set_negative(); // } else if ((neg == 0) && (pos > 0)) { // mono->set_positive(); // } else { /// ... Combination of pos and neg // mono->set_unknown_dir(); // } // } // break; // } // case SUB_OP: // { // Monotonicity & mv0 = mono_list[0]; // Monotonicity & mv1 = mono_list[1]; /// // if (mv0.varying() || mv0.unknown_mov() || // mv1.varying() || mv1.unknown_mov()) { // constant = false; // } // if (mv0.negative() && mv1.positive()) { // mono->set_negative(); // } else if (mv0.positive() && mv1.negative()) { // mono->set_positive(); // } else { // mono->set_unknown_dir(); // } // if (constant) { // mono->set_constant(); // } // if (unknown_dir) { // mono->set_unknown_dir(); // } else { // if ((pos == 0) && (neg > 0)) { // mono->set_negative(); // } else if ((neg == 0) && (pos > 0)) { // mono->set_positive(); // } else { /// ... Combination of pos and neg // mono->set_unknown_dir(); // } // } // break; // } // case : // // } /// /// } else { mono->set_constant(); // /// ... Compare the expression with 0 // Relation rel = range_d_acc.compare(*expr, *constant(0)); /// // if (rel.is_less_than()) { // mono->set_negative(); // } else if (rel.is_greater_than()) { // mono->set_positive(); // } else { // mono->set_unknown_dir(); // } } return mono; } /// Test the divides property by dividing, simplifying and checking /// if it's a constant, then it divides if the value is non-zero. /// if it's not a constant, then it divides as long as the top-level /// operator is not a DIV_OP. AR_CERTAINTY expr_divides ( Expression & divide_by, Expression & divide_into ) { bool divi=false; if (_ar_logging && _ar_logging % 11 == 0) { arlog << ">>expr_divides-- Does " << divide_by << " DIVIDE " << divide_into << " ??"; } if (is_integer_one(divide_by)) { divi = true; } else { if (is_integer_constant(divide_by) && is_integer_constant(divide_into)) { if (divide_into.value() % divide_by.value() == 0) { if (_ar_logging && _ar_logging % 11 == 0) { arlog << ": YES!" << endl; } return AR_YES; } else { if (_ar_logging && _ar_logging % 11 == 0) { arlog << ": NO!" << endl; } return AR_NO; } } else { Expression * expr = simplify ( div(divide_into.clone(), divide_by.clone() ) ); if (expr->op() == INTEGER_CONSTANT_OP) { divi = (expr->value() != 0); } else { if (expr->op() == EXP_OP) { if ((expr->arg_list()[1].op() == INTEGER_CONSTANT_OP) && (expr->arg_list()[1].value() >= 0)) { divi = true; } else { divi = false; } } else { divi = expr->op() != DIV_OP; } } delete expr; } } if (divi) { if (_ar_logging && _ar_logging % 11 == 0) { arlog << ": YES!" << endl; } return AR_YES; } else { if (_ar_logging && _ar_logging % 11 == 0) { arlog << ": NOT SURE" << endl; } return AR_UNSURE; } }

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