diff options
Diffstat (limited to 'omegalib/code_gen/src/output_repr.cc')
| -rw-r--r-- | omegalib/code_gen/src/output_repr.cc | 1931 |
1 files changed, 0 insertions, 1931 deletions
diff --git a/omegalib/code_gen/src/output_repr.cc b/omegalib/code_gen/src/output_repr.cc deleted file mode 100644 index 955cc14..0000000 --- a/omegalib/code_gen/src/output_repr.cc +++ /dev/null @@ -1,1931 +0,0 @@ -/***************************************************************************** - Copyright (C) 1994-2000 University of Maryland - Copyright (C) 2008 University of Southern California - Copyright (C) 2009-2010 University of Utah - All Rights Reserved. - - Purpose: - utility functions for outputing CG_outputReprs - - Notes: - - History: - 07/30/10 collect various code outputing into one place, by Chun Chen -*****************************************************************************/ - -#include <omega.h> -#include <code_gen/CG_stringBuilder.h> -#include <code_gen/output_repr.h> -#include <basic/omega_error.h> -#include <math.h> -#include <stack> -#include <typeinfo> - -namespace omega { - -extern Tuple<Tuple<Relation> > projected_nIS; -int var_substitution_threshold = 100; -//protonu. -extern int upperBoundForLevel; -extern int lowerBoundForLevel; -extern bool fillInBounds; -//end--protonu. - -} - - -namespace omega { - -std::pair<EQ_Handle, int> find_simplest_assignment(const Relation &R_, Variable_ID v, const std::vector<CG_outputRepr *> &assigned_on_the_fly); - - -namespace { - - - - -void get_stride(const Constraint_Handle &h, Variable_ID &wc, coef_t &step){ - wc = 0; - for(Constr_Vars_Iter i(h,true); i; i++) { - assert(wc == 0); - wc = (*i).var; - step = ((*i).coef); - } -} - -} - -CG_outputRepr* outputIdent(CG_outputBuilder* ocg, const Relation &R_, Variable_ID v, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation &R = const_cast<Relation &>(R_); - - switch (v->kind()) { - case Set_Var: { - int pos = v->get_position(); - if (assigned_on_the_fly[pos-1] != NULL) - return assigned_on_the_fly[pos-1]->clone(); - else - return ocg->CreateIdent(v->name()); - break; - } - case Global_Var: { - if (v->get_global_var()->arity() == 0) - return ocg->CreateIdent(v->name()); - else { - /* This should be improved to take into account the possible elimination - of the set variables. */ - int arity = v->get_global_var()->arity(); - //assert(arity <= last_level); - Tuple<CG_outputRepr *> argList; - // Relation R = Relation::True(arity); - - // name_codegen_vars(R); // easy way to make sure the names are correct. - for(int i = 1; i <= arity; i++) - argList.append(ocg->CreateIdent(R.set_var(i)->name())); - CG_outputRepr *call = ocg->CreateInvoke(v->get_global_var()->base_name(), argList); - return call; - } - break; - } - default: - throw std::invalid_argument("wrong variable type"); - } -} - - -//---------------------------------------------------------------------------- -// Translate equality constraints to if-condition and assignment. -// return.first is right-hand-side of assignment, return.second -// is true if assignment is required. -// -- by chun 07/29/2010 -// ---------------------------------------------------------------------------- -std::pair<CG_outputRepr *, bool> outputAssignment(CG_outputBuilder *ocg, const Relation &R_, Variable_ID v, Relation &enforced, CG_outputRepr *&if_repr, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation &R = const_cast<Relation &>(R_); - - Conjunct *c = R.query_DNF()->single_conjunct(); - - // check whether to generate if-conditions from equality constraints - for (EQ_Iterator ei(c); ei; ei++) - if (!(*ei).has_wildcards() && abs((*ei).get_coef(v)) > 1) { - Relation r(R.n_set()); - F_And *f_super_root = r.add_and(); - F_Exists *fe = f_super_root->add_exists(); - Variable_ID e = fe->declare(); - F_And *f_root = fe->add_and(); - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(*ei); cvi; cvi++) - switch ((*cvi).var->kind()) { - case Input_Var: { - if ((*cvi).var == v) - h.update_coef(e, (*cvi).coef); - else - h.update_coef(r.set_var((*cvi).var->get_position()), (*cvi).coef); - break; - } - case Global_Var: { - Global_Var_ID g = (*cvi).var->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r.get_local(g); - else - v2 = r.get_local(g, (*cvi).var->function_of()); - h.update_coef(v2, (*cvi).coef); - break; - } - default: - assert(0); - } - h.update_const((*ei).get_const()); - - r.copy_names(R); - r.setup_names(); - - // need if-condition to make sure this loop variable has integer value - if (!Gist(r, copy(enforced), 1).is_obvious_tautology()) { - coef_t coef = (*ei).get_coef(v); - coef_t sign = -((coef>0)?1:-1); - coef = abs(coef); - - CG_outputRepr *term = NULL; - for (Constr_Vars_Iter cvi(*ei); cvi; cvi++) - if ((*cvi).var != v) { - CG_outputRepr *varRepr = outputIdent(ocg, R, (*cvi).var, assigned_on_the_fly); - coef_t t = sign*(*cvi).coef; - if (t == 1) - term = ocg->CreatePlus(term, varRepr); - else if (t == -1) - term = ocg->CreateMinus(term, varRepr); - else if (t > 0) - term = ocg->CreatePlus(term, ocg->CreateTimes(ocg->CreateInt(t), varRepr)); - else if (t < 0) - term = ocg->CreateMinus(term, ocg->CreateTimes(ocg->CreateInt(-t), varRepr)); - } - coef_t t = sign*(*ei).get_const(); - if (t > 0) - term = ocg->CreatePlus(term, ocg->CreateInt(t)); - else if (t < 0) - term = ocg->CreateMinus(term, ocg->CreateInt(-t)); - - term = ocg->CreateIntegerMod(term, ocg->CreateInt(coef)); - term = ocg->CreateEQ(term, ocg->CreateInt(0)); - - if_repr = ocg->CreateAnd(if_repr, term); - } - - enforced.and_with_EQ(*ei); - enforced.simplify(); - } - - // find the simplest assignment - std::pair<EQ_Handle, int> a = find_simplest_assignment(R, v, assigned_on_the_fly); - - // now generate assignment - if (a.second < INT_MAX) { - EQ_Handle eq = a.first; - CG_outputRepr *rop_repr = NULL; - - coef_t divider = eq.get_coef(v); - int sign = 1; - if (divider < 0) { - divider = -divider; - sign = -1; - } - - for (Constr_Vars_Iter cvi(eq); cvi; cvi++) - if ((*cvi).var != v) { - CG_outputRepr *var_repr = outputIdent(ocg, R, (*cvi).var, assigned_on_the_fly); - coef_t coef = (*cvi).coef; - if (-sign * coef == -1) - rop_repr = ocg->CreateMinus(rop_repr, var_repr); - else if (-sign * coef < -1) - rop_repr = ocg->CreateMinus(rop_repr, ocg->CreateTimes(ocg->CreateInt(sign * coef), var_repr)); - else if (-sign * coef == 1) - rop_repr = ocg->CreatePlus(rop_repr, var_repr); - else // -sign * coef > 1 - rop_repr = ocg->CreatePlus(rop_repr, ocg->CreateTimes(ocg->CreateInt(-sign * coef), var_repr)); - } - - coef_t c_term = -(eq.get_const() * sign); - - if (c_term > 0) - rop_repr = ocg->CreatePlus(rop_repr, ocg->CreateInt(c_term)); - else if (c_term < 0) - rop_repr = ocg->CreateMinus(rop_repr, ocg->CreateInt(-c_term)); - else if (rop_repr == NULL) - rop_repr = ocg->CreateInt(0); - - if (divider != 1) - rop_repr = ocg->CreateIntegerDivide(rop_repr, ocg->CreateInt(divider)); - - enforced.and_with_EQ(eq); - enforced.simplify(); - - if (a.second > var_substitution_threshold) - return std::make_pair(rop_repr, true); - else - return std::make_pair(rop_repr, false); - } - else - return std::make_pair(static_cast<CG_outputRepr *>(NULL), false); -} - - -//---------------------------------------------------------------------------- -// Don't use Substitutions class since it can't handle integer -// division. Instead, use relation mapping to a single output -// variable to get substitution. -- by chun, 07/19/2007 -//---------------------------------------------------------------------------- -Tuple<CG_outputRepr*> outputSubstitution(CG_outputBuilder* ocg, const Relation &R_, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation &R = const_cast<Relation &>(R_); - - const int n = R.n_out(); - Tuple<CG_outputRepr*> oReprList; - - // Find substitution for each output variable - for (int i = 1; i <= n; i++) { - Relation mapping(n, 1); - F_And *f_root = mapping.add_and(); - EQ_Handle h = f_root->add_EQ(); - h.update_coef(mapping.output_var(1), 1); - h.update_coef(mapping.input_var(i), -1); - - Relation S = Composition(mapping, copy(R)); - - std::pair<EQ_Handle, int> a = find_simplest_assignment(S, S.output_var(1), assigned_on_the_fly); - - if (a.second < INT_MAX) { - while (a.second > 0) { - EQ_Handle eq = a.first; - std::set<int> candidates; - for (Constr_Vars_Iter cvi(eq); cvi; cvi++) - if ((*cvi).var->kind() == Input_Var) - candidates.insert((*cvi).var->get_position()); - - bool changed = false; - for (std::set<int>::iterator j = candidates.begin(); j != candidates.end(); j++) { - Relation S2 = Project(copy(S), *j, Input_Var); - std::pair<EQ_Handle, int> a2 = find_simplest_assignment(S2, S2.output_var(1), assigned_on_the_fly); - if (a2.second <= a.second) { - S = S2; - a = a2; - changed = true; - break; - } - } - if (!changed) - break; - } - } - - if (a.second < INT_MAX) { - CG_outputRepr *repr = NULL; - EQ_Handle eq = a.first; - Variable_ID v = S.output_var(1); - - for (int j = 1; j <= S.n_inp(); j++) - S.name_input_var(j, R.input_var(j)->name()); - S.setup_names(); - - int d = eq.get_coef(v); - assert(d != 0); - int sign = (d>0)?-1:1; - d = -sign * d; - for (Constr_Vars_Iter cvi(eq); cvi; cvi++) - if ((*cvi).var != v) { - int coef = sign * (*cvi).coef; - CG_outputRepr *op = outputIdent(ocg, S, (*cvi).var, assigned_on_the_fly); - if (coef > 1) - op = ocg->CreateTimes(ocg->CreateInt(coef), op); - else if (coef < -1) - op = ocg->CreateTimes(ocg->CreateInt(-coef), op); - if (coef > 0) - repr = ocg->CreatePlus(repr, op); - else if (coef < 0) - repr = ocg->CreateMinus(repr, op); - } - - int c = sign * eq.get_const(); - if (c > 0) - repr = ocg->CreatePlus(repr, ocg->CreateInt(c)); - else if (c < 0) - repr = ocg->CreateMinus(repr, ocg->CreateInt(-c)); - else if (repr == NULL) - repr = ocg->CreateInt(0); - - if (d != 1) - repr = ocg->CreateIntegerDivide(repr, ocg->CreateInt(d)); - - oReprList.append(repr); - } - else - oReprList.append(NULL); - } - - return oReprList; -} - -namespace { - -Relation create_stride_on_bound(int n, const std::map<Variable_ID, coef_t> &lb, coef_t stride) { - Relation result(n); - F_And *f_root = result.add_and(); - EQ_Handle h = f_root->add_stride(stride); - - for (std::map<Variable_ID, coef_t>::const_iterator i = lb.begin(); i != lb.end(); i++) { - if (i->first == NULL) - h.update_const(i->second); - else { - switch(i->first->kind()) { - case Input_Var: { - int pos = i->first->get_position(); - h.update_coef(result.set_var(pos), i->second); - break; - } - case Global_Var: { - Global_Var_ID g = i->first->get_global_var(); - Variable_ID v; - if (g->arity() == 0) - v = result.get_local(g); - else - v = result.get_local(g, i->first->function_of()); - h.update_coef(v, i->second); - break; - } - default: - assert(0); - } - } - } - - return result; -} - -} - -//---------------------------------------------------------------------------- -// Find the most restrictive common stride constraint for a set of -// relations. -- by chun, 05/20/09 -// ---------------------------------------------------------------------------- -Relation greatest_common_step(const Tuple<Relation> &I, const Tuple<int> &active, int level, const Relation &known) { - assert(I.size() == active.size()); - int n = 0; - - std::vector<Relation> I1, I2; - for (int i = 1; i <= I.size(); i++) - if (active[i]) { - if (n == 0) - n = I[i].n_set(); - - Relation r1; - if (known.is_null()) - r1 = copy(I[i]); - else { - r1 = Intersection(copy(I[i]), copy(known)); - r1.simplify(); - } - I1.push_back(r1); - Relation r2 = Gist(copy(I[i]), copy(known)); - assert(r2.is_upper_bound_satisfiable()); - if (r2.is_obvious_tautology()) - return Relation::True(n); - I2.push_back(r2); - } - - std::vector<bool> is_exact(I2.size(), true); - std::vector<coef_t> step(I2.size(), 0); - std::vector<coef_t> messy_step(I2.size(), 0); - Variable_ID t_col = set_var(level); - std::map<Variable_ID, coef_t> lb; - - // first check all clean strides: t_col = ... (mod step) - for (size_t i = 0; i < I2.size(); i++) { - Conjunct *c = I2[i].query_DNF()->single_conjunct(); - - bool is_degenerated = false; - for (EQ_Iterator e = c->EQs(); e; e++) { - coef_t coef = abs((*e).get_coef(t_col)); - if (coef != 0 && !(*e).has_wildcards()) { - is_degenerated = true; - break; - } - } - if (is_degenerated) - continue; - - for (EQ_Iterator e = c->EQs(); e; e++) { - if ((*e).has_wildcards()) { - coef_t coef = abs((*e).get_coef(t_col)); - if (coef == 0) - continue; - if (coef != 1) { - is_exact[i] = false; - continue; - } - - coef_t this_step = abs(Constr_Vars_Iter(*e, true).curr_coef()); - assert(this_step != 1); - - if (lb.size() != 0) { - Relation test = create_stride_on_bound(n, lb, this_step); - if (Gist(test, copy(I1[i])).is_obvious_tautology()) { - if (step[i] == 0) - step[i] = this_step; - else - step[i] = lcm(step[i], this_step); - } - else - is_exact[i] = false; - } - else { - // try to find a lower bound that hits on stride - Conjunct *c = I2[i].query_DNF()->single_conjunct(); - for (GEQ_Iterator ge = c->GEQs(); ge; ge++) { - if ((*ge).has_wildcards() || (*ge).get_coef(t_col) != 1) - continue; - - std::map<Variable_ID, coef_t> cur_lb; - for (Constr_Vars_Iter cv(*ge); cv; cv++) - cur_lb[cv.curr_var()] = cv.curr_coef(); - cur_lb[NULL] = (*ge).get_const(); - - Relation test = create_stride_on_bound(n, cur_lb, this_step); - if (Gist(test, copy(I1[i])).is_obvious_tautology()) { - if (step[i] == 0) - step[i] = this_step; - else - step[i] = lcm(step[i], this_step); - - lb = cur_lb; - break; - } - } - - // no clean lower bound, thus we use this modular constraint as is - if (lb.size() == 0) { - std::map<Variable_ID, coef_t> cur_lb; - int wild_count = 0; - for (Constr_Vars_Iter cv(*e); cv; cv++) - if (cv.curr_var()->kind() == Wildcard_Var) - wild_count++; - else - cur_lb[cv.curr_var()] = cv.curr_coef(); - cur_lb[NULL] = (*e).get_const(); - - if (wild_count == 1) { - lb = cur_lb; - if (step[i] == 0) - step[i] = this_step; - else - step[i] = lcm(step[i], this_step); - } - } - - if (lb.size() == 0) - is_exact[i] = false; - } - } - } - } - - // aggregate all exact steps - coef_t global_step = 0; - for (size_t i = 0; i < is_exact.size(); i++) - if (is_exact[i]) - global_step = gcd(global_step, step[i]); - if (global_step == 1) - return Relation::True(n); - - // now check all messy strides: a*t_col = ... (mod step) - for (size_t i = 0; i < I2.size(); i++) - if (!is_exact[i]) { - Conjunct *c = I2[i].query_DNF()->single_conjunct(); - for (EQ_Iterator e = c->EQs(); e; e++) { - coef_t coef = abs((*e).get_coef(t_col)); - if (coef == 0 || coef == 1) - continue; - - // make a guess for messy stride condition -- by chun 07/27/2007 - coef_t this_step = abs(Constr_Vars_Iter(*e, true).curr_coef()); - this_step /= gcd(this_step, coef); - this_step = gcd(global_step, this_step); - if (this_step == 1) - continue; - - if (lb.size() != 0) { - Relation test = create_stride_on_bound(n, lb, this_step); - if (Gist(test, copy(I1[i])).is_obvious_tautology()) { - if (step[i] == 0) - step[i] = this_step; - else - step[i] = lcm(step[i], this_step); - } - } - else { - // try to find a lower bound that hits on stride - Conjunct *c = I2[i].query_DNF()->single_conjunct(); - for (GEQ_Iterator ge = c->GEQs(); ge; ge++) { - if ((*ge).has_wildcards() || (*ge).get_coef(t_col) != 1) - continue; - - std::map<Variable_ID, coef_t> cur_lb; - - for (Constr_Vars_Iter cv(*ge); cv; cv++) - cur_lb[cv.curr_var()] = cv.curr_coef(); - - cur_lb[NULL] = (*ge).get_const(); - - Relation test = create_stride_on_bound(n, cur_lb, this_step); - if (Gist(test, copy(I1[i])).is_obvious_tautology()) { - if (step[i] == 0) - step[i] = this_step; - else - step[i] = lcm(step[i], this_step); - - lb = cur_lb; - break; - } - } - } - } - } - - // aggregate all non-exact steps - for (size_t i = 0; i < is_exact.size(); i++) - if (!is_exact[i]) - global_step = gcd(global_step, step[i]); - if (global_step == 1 || global_step == 0) - return Relation::True(n); - - Relation result = create_stride_on_bound(n, lb, global_step); - - // check for statements that haven't been factored into global step - for (size_t i = 0; i < I1.size(); i++) - if (step[i] == 0) { - if (!Gist(copy(result), copy(I1[i])).is_obvious_tautology()) - return Relation::True(n); - } - - return result; -} - - -//----------------------------------------------------------------------------- -// Substitute variables in a statement according to mapping function. -//----------------------------------------------------------------------------- -CG_outputRepr* outputStatement(CG_outputBuilder *ocg, CG_outputRepr *stmt, int indent, const Relation &mapping_, const Relation &known_, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation mapping = copy(mapping_); - Relation known = copy(known_); - Tuple<std::string> loop_vars; - - for (int i = 1; i <= mapping.n_inp(); i++) - loop_vars.append(mapping.input_var(i)->name()); - - // discard non-existant variables from iteration spaces -- by chun 12/31/2008 - if (known.n_set() > mapping.n_out()) { - Relation r(known.n_set(), mapping.n_out()); - F_And *f_root = r.add_and(); - for (int i = 1; i <= mapping.n_out(); i++) { - EQ_Handle h = f_root->add_EQ(); - h.update_coef(r.input_var(i), 1); - h.update_coef(r.output_var(i), -1); - } - known = Range(Restrict_Domain(r, known)); - known.simplify(); - } - - // remove modular constraints from known to simplify mapping process -- by chun 11/10/2008 - Relation k(known.n_set()); - F_And *f_root = k.add_and(); - Conjunct *c = known.query_DNF()->single_conjunct(); - for (EQ_Iterator e = c->EQs(); e; e++) { - if (!(*e).has_wildcards()) - f_root->add_EQ(*e); - } - k.simplify(); - - // get variable substituion list - Relation Inv_mapping = Restrict_Domain(Inverse(mapping), k); - Tuple<CG_outputRepr*> sList = outputSubstitution(ocg, Inv_mapping, assigned_on_the_fly); - - return ocg->CreatePlaceHolder(indent, stmt, sList, loop_vars); -} - - -// find floor definition for variable such as m-3 <= 4v <= m -bool findFloorInequality(Relation &r, Variable_ID v, GEQ_Handle &h, Variable_ID excluded) { - Conjunct *c = r.single_conjunct(); - - std::set<Variable_ID> var_checked; - std::stack<Variable_ID> var_checking; - var_checking.push(v); - - while (!var_checking.empty()) { - Variable_ID v2 = var_checking.top(); - var_checking.pop(); - - bool is_floor = false; - for (GEQ_Iterator gi(c); gi; gi++) { - if (excluded != NULL && (*gi).get_coef(excluded) != 0) - continue; - - coef_t a = (*gi).get_coef(v2); - if (a < 0) { - for (GEQ_Iterator gi2(c); gi2; gi2++) { - coef_t b = (*gi2).get_coef(v2); - if (b == -a && (*gi).get_const()+(*gi2).get_const() < -a) { - bool match = true; - for (Constr_Vars_Iter cvi(*gi); cvi; cvi++) - if ((*gi2).get_coef((*cvi).var) != -(*cvi).coef) { - match = false; - break; - } - if (!match) - continue; - for (Constr_Vars_Iter cvi(*gi2); cvi; cvi++) - if ((*gi).get_coef((*cvi).var) != -(*cvi).coef) { - match = false; - break; - } - if (match) { - var_checked.insert(v2); - is_floor = true; - if (v == v2) - h = *gi; - - for (Constr_Vars_Iter cvi(*gi); cvi; cvi++) - if (((*cvi).var->kind() == Exists_Var || (*cvi).var->kind() == Wildcard_Var) && - var_checked.find((*cvi).var) == var_checked.end()) - var_checking.push((*cvi).var); - - break; - } - } - } - if (is_floor) - break; - } - } - if (!is_floor) - return false; - } - return true; -} - - - - -//----------------------------------------------------------------------------- -// Output a reqular equality or inequality to conditions. -// e.g. (i=5*j) -//----------------------------------------------------------------------------- -CG_outputRepr* output_as_guard(CG_outputBuilder* ocg, const Relation &guards_in, Constraint_Handle e, bool is_equality, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation &guards = const_cast<Relation &>(guards_in); - if (e.has_wildcards()) - throw std::invalid_argument("constraint must not have wildcard"); - - Variable_ID v = (*Constr_Vars_Iter(e)).var; - - coef_t saved_coef = ((e).get_coef(v)); - int sign = saved_coef < 0 ? -1 : 1; - - (e).update_coef_during_simplify(v, -saved_coef+sign); - CG_outputRepr* rop = outputEasyBoundAsRepr(ocg, guards, e, v, false, 0, assigned_on_the_fly); - (e).update_coef_during_simplify(v,saved_coef-sign); - - CG_outputRepr* lop = outputIdent(ocg, guards, v, assigned_on_the_fly); - if (abs(saved_coef) != 1) - lop = ocg->CreateTimes(ocg->CreateInt(abs(saved_coef)), lop); - - - if (is_equality) { - return ocg->CreateEQ(lop, rop); - } - else { - if (saved_coef < 0) - return ocg->CreateLE(lop, rop); - else - return ocg->CreateGE(lop, rop); - } -} - - -//----------------------------------------------------------------------------- -// Output stride conditions from equalities. -// e.g. (exists alpha: i = 5*alpha) -//----------------------------------------------------------------------------- -CG_outputRepr *output_EQ_strides(CG_outputBuilder* ocg, const Relation &guards_in, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation guards = const_cast<Relation &>(guards_in); - Conjunct *c = guards.single_conjunct(); - - CG_outputRepr *eqRepr = NULL; - - for (EQ_Iterator ei(c->EQs()); ei; ei++) { - Variable_ID wc = NULL; - for (Constr_Vars_Iter cvi((*ei), true); cvi; cvi++) { - if (wc != NULL) - throw codegen_error("Can't generate equality condition with multiple wildcards"); - else - wc = (*cvi).var; - } - if (wc == NULL) - continue; - - coef_t step = (*ei).get_coef(wc); - - (*ei).update_coef_during_simplify(wc, 1-step); - CG_outputRepr* lop = outputEasyBoundAsRepr(ocg, guards, (*ei), wc, false, 0, assigned_on_the_fly); - (*ei).update_coef_during_simplify(wc, step-1); - - CG_outputRepr* rop = ocg->CreateInt(abs(step)); - CG_outputRepr* intMod = ocg->CreateIntegerMod(lop, rop); - CG_outputRepr* eqNode = ocg->CreateEQ(intMod, ocg->CreateInt(0)); - - eqRepr = ocg->CreateAnd(eqRepr, eqNode); - } - - return eqRepr; -} - - - -//----------------------------------------------------------------------------- -// Output hole conditions created by inequalities involving wildcards. -// e.g. (exists alpha: 4*alpha <= i <= 5*alpha) -// Collect wildcards -// For each whildcard -// collect lower and upper bounds in which wildcard appears -// For each lower bound -// create constraint with each upper bound -//----------------------------------------------------------------------------- -CG_outputRepr *output_GEQ_strides(CG_outputBuilder* ocg, const Relation &guards_in, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation guards = const_cast<Relation &>(guards_in); - Conjunct *c = guards.single_conjunct(); - - CG_outputRepr* geqRepr = NULL; - - std::set<Variable_ID> non_orphan_wildcard; - for (GEQ_Iterator gi(c); gi; gi++) { - int num_wild = 0; - Variable_ID first_one; - for (Constr_Vars_Iter cvi(*gi, true); cvi; cvi++) { - num_wild++; - if (num_wild == 1) - first_one = (*cvi).var; - else - non_orphan_wildcard.insert((*cvi).var); - } - if (num_wild > 1) - non_orphan_wildcard.insert(first_one); - } - - for (int i = 1; i <= (*(c->variables())).size(); i++) { - Variable_ID wc = (*(c->variables()))[i]; - if (wc->kind() == Wildcard_Var && non_orphan_wildcard.find(wc) == non_orphan_wildcard.end()) { - Tuple<GEQ_Handle> lower, upper; - for (GEQ_Iterator gi(c); gi; gi++) { - if((*gi).get_coef(wc) > 0) - lower.append(*gi); - else if((*gi).get_coef(wc) < 0) - upper.append(*gi); - } - - // low: c*alpha - x >= 0 - // up: -d*alpha + y >= 0 - for (Tuple_Iterator<GEQ_Handle> low(lower); low; low++) { - for (Tuple_Iterator<GEQ_Handle> up(upper); up; up++) { - coef_t low_coef = (*low).get_coef(wc); - coef_t up_coef = (*up).get_coef(wc); - - (*low).update_coef_during_simplify(wc, 1-low_coef); - CG_outputRepr* lowExpr = outputEasyBoundAsRepr(ocg, guards, *low, wc, false, 0, assigned_on_the_fly); - (*low).update_coef_during_simplify(wc, low_coef-1); - - (*up).update_coef_during_simplify(wc, -1-up_coef); - CG_outputRepr* upExpr = outputEasyBoundAsRepr(ocg, guards, *up, wc, false, 0, assigned_on_the_fly); - (*up).update_coef_during_simplify(wc, up_coef+1); - - CG_outputRepr* intDiv = ocg->CreateIntegerDivide(upExpr, ocg->CreateInt(-up_coef)); - CG_outputRepr* rop = ocg->CreateTimes(ocg->CreateInt(low_coef), intDiv); - CG_outputRepr* geqNode = ocg->CreateLE(lowExpr, rop); - - geqRepr = ocg->CreateAnd(geqRepr, geqNode); - } - } - } - } - - if (non_orphan_wildcard.size() > 0) { - // e.g. c*alpha - x >= 0 (*) - // -d*alpha + y >= 0 (*) - // e1*alpha + f1*beta + g1 >= 0 (**) - // e2*alpha + f2*beta + g2 >= 0 (**) - // ... - // TODO: should generate a testing loop for alpha using its lower and - // upper bounds from (*) constraints and do the same if-condition test - // for beta from each pair of opposite (**) constraints as above, - // and exit the loop when if-condition satisfied. - throw codegen_error("Can't generate multiple wildcard GEQ guards right now"); - } - - return geqRepr; -} - - -//----------------------------------------------------------------------------- -// Translate all constraints in a relation to guard conditions. -//----------------------------------------------------------------------------- -CG_outputRepr *outputGuard(CG_outputBuilder* ocg, const Relation &guards_in, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation &guards = const_cast<Relation &>(guards_in); - if (guards.is_null() || guards.is_obvious_tautology()) - return NULL; - - CG_outputRepr* nodeRepr = NULL; - - CG_outputRepr *eqStrideRepr = output_EQ_strides(ocg, guards, assigned_on_the_fly); - nodeRepr = ocg->CreateAnd(nodeRepr, eqStrideRepr); - - CG_outputRepr *geqStrideRepr = output_GEQ_strides(ocg, guards, assigned_on_the_fly); - nodeRepr = ocg->CreateAnd(nodeRepr, geqStrideRepr); - - Conjunct *c = guards.single_conjunct(); - for(EQ_Iterator ei(c->EQs()); ei; ei++) - if (!(*ei).has_wildcards()) { - CG_outputRepr *eqRepr = output_as_guard(ocg, guards, (*ei), true, assigned_on_the_fly); - nodeRepr = ocg->CreateAnd(nodeRepr, eqRepr); - } - for(GEQ_Iterator gi(c->GEQs()); gi; gi++) - if (!(*gi).has_wildcards()) { - CG_outputRepr *geqRepr = output_as_guard(ocg, guards, (*gi), false, assigned_on_the_fly); - nodeRepr = ocg->CreateAnd(nodeRepr, geqRepr); - } - - return nodeRepr; -} - - -//----------------------------------------------------------------------------- -// one is 1 for LB -// this function is overloaded should replace the original one -//----------------------------------------------------------------------------- -CG_outputRepr *outputLBasRepr(CG_outputBuilder* ocg, const GEQ_Handle &g, - Relation &bounds, Variable_ID v, - coef_t stride, const EQ_Handle &strideEQ, - Relation known, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { -#if ! defined NDEBUG - coef_t v_coef; - assert((v_coef = g.get_coef(v)) > 0); -#endif - - std::string s; - CG_outputRepr *lbRepr; - if (stride == 1) { - lbRepr = outputEasyBoundAsRepr(ocg, bounds, g, v, false, 1, assigned_on_the_fly); - } - else { - if (!boundHitsStride(g,v,strideEQ,stride,known)) { - bounds.setup_names(); // boundsHitsStride resets variable names - - CG_stringBuilder oscg; - std::string c = GetString(outputEasyBoundAsRepr(&oscg, bounds, strideEQ, v, true, 0, assigned_on_the_fly)); - CG_outputRepr *cRepr = NULL; - if (c != std::string("0")) - cRepr = outputEasyBoundAsRepr(ocg, bounds, strideEQ, v, true, 0, assigned_on_the_fly); - std::string LoverM = GetString(outputEasyBoundAsRepr(&oscg, bounds, g, v, false, 1, assigned_on_the_fly)); - CG_outputRepr *LoverMRepr = NULL; - if (LoverM != std::string("0")) - LoverMRepr = outputEasyBoundAsRepr(ocg, bounds, g, v, false, 1, assigned_on_the_fly); - - if (code_gen_debug > 2) { - fprintf(DebugFile,"::: LoverM is %s\n", LoverM.c_str()); - fprintf(DebugFile,"::: c is %s\n", c.c_str()); - } - - int complexity1 = 0, complexity2 = 0; - for (size_t i = 0; i < c.length(); i++) - if (c[i] == '+' || c[i] == '-' || c[i] == '*' || c[i] == '/') - complexity1++; - else if (c[i] == ',') - complexity1 += 2; - for (size_t i = 0; i < LoverM.length(); i++) - if (LoverM[i] == '+' || LoverM[i] == '-' || LoverM[i] == '*' || LoverM[i] == '/') - complexity2++; - else if (LoverM[i] == ',') - complexity2 += 2; - - if (complexity1 < complexity2) { - CG_outputRepr *idUp = LoverMRepr; - CG_outputRepr *c1Repr = ocg->CreateCopy(cRepr); - idUp = ocg->CreateMinus(idUp, c1Repr); - idUp = ocg->CreatePlus(idUp, ocg->CreateInt(stride-1)); - CG_outputRepr *idLow = ocg->CreateInt(stride); - lbRepr = ocg->CreateTimes(ocg->CreateInt(stride), - ocg->CreateIntegerDivide(idUp, idLow)); - lbRepr = ocg->CreatePlus(lbRepr, cRepr); - } - else { - CG_outputRepr *LoverM1Repr = ocg->CreateCopy(LoverMRepr); - CG_outputRepr *imUp = ocg->CreateMinus(cRepr, LoverM1Repr); - CG_outputRepr *imLow = ocg->CreateInt(stride); - CG_outputRepr *intMod = ocg->CreateIntegerMod(imUp, imLow); - lbRepr = ocg->CreatePlus(LoverMRepr, intMod); - } - } - else { - // boundsHitsStride resets variable names - bounds.setup_names(); - lbRepr = outputEasyBoundAsRepr(ocg, bounds, g, v, false, 0, assigned_on_the_fly); - } - } - - return lbRepr; -} - -//----------------------------------------------------------------------------- -// one is -1 for UB -// this function is overloaded should replace the original one -//----------------------------------------------------------------------------- -CG_outputRepr *outputUBasRepr(CG_outputBuilder* ocg, const GEQ_Handle &g, - Relation & bounds, - Variable_ID v, - coef_t /*stride*/, // currently unused - const EQ_Handle &/*strideEQ*/, //currently unused - const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - assert(g.get_coef(v) < 0); - CG_outputRepr* upRepr = outputEasyBoundAsRepr(ocg, bounds, g, v, false, 0, assigned_on_the_fly); - return upRepr; -} - -//----------------------------------------------------------------------------- -// Print the expression for the variable given as v. Works for both -// GEQ's and EQ's, but produces intDiv (not intMod) when v has a nonunit -// coefficient. So it is OK for loop bounds, but for checking stride -// constraints, you want to make sure the coef of v is 1, and insert the -// intMod yourself. -// -// original name is outputEasyBound -//----------------------------------------------------------------------------- -CG_outputRepr* outputEasyBoundAsRepr(CG_outputBuilder* ocg, Relation &bounds, - const Constraint_Handle &g, Variable_ID v, - bool ignoreWC, - int ceiling, - const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - // assert ignoreWC => g is EQ - // rewrite constraint as foo (== or <= or >=) v, return foo as string - - CG_outputRepr* easyBoundRepr = NULL; - - coef_t v_coef = g.get_coef(v); - int v_sign = v_coef > 0 ? 1 : -1; - v_coef *= v_sign; - assert(v_coef > 0); - // foo is (-constraint)/v_sign/v_coef - - int sign_adj = -v_sign; - - //---------------------------------------------------------------------- - // the following generates +- cf*varName - //---------------------------------------------------------------------- - for(Constr_Vars_Iter c2(g, false); c2; c2++) { - if ((*c2).var != v && (!ignoreWC || (*c2).var->kind()!=Wildcard_Var)) { - - coef_t cf = (*c2).coef*sign_adj; - assert(cf != 0); - - CG_outputRepr *varName; - if ((*c2).var->kind() == Wildcard_Var) { - GEQ_Handle h; - if (!findFloorInequality(bounds, (*c2).var, h, v)) { - if (easyBoundRepr != NULL) { - easyBoundRepr->clear(); - delete easyBoundRepr; - } - return NULL; - } - varName = outputEasyBoundAsRepr(ocg, bounds, h, (*c2).var, false, 0, assigned_on_the_fly); - } - else { - varName = outputIdent(ocg, bounds, (*c2).var, assigned_on_the_fly); - } - CG_outputRepr *cfRepr = NULL; - - if (cf > 1) { - cfRepr = ocg->CreateInt(cf); - CG_outputRepr* rbRepr = ocg->CreateTimes(cfRepr, varName); - easyBoundRepr = ocg->CreatePlus(easyBoundRepr, rbRepr); - } - else if (cf < -1) { - cfRepr = ocg->CreateInt(-cf); - CG_outputRepr* rbRepr = ocg->CreateTimes(cfRepr, varName); - easyBoundRepr = ocg->CreateMinus(easyBoundRepr, rbRepr); - } - else if (cf == 1) { - easyBoundRepr = ocg->CreatePlus(easyBoundRepr, varName); - } - else if (cf == -1) { - easyBoundRepr = ocg->CreateMinus(easyBoundRepr, varName); - } - } - } - - if (g.get_const()) { - coef_t cf = g.get_const()*sign_adj; - assert(cf != 0); - if (cf > 0) { - easyBoundRepr = ocg->CreatePlus(easyBoundRepr, ocg->CreateInt(cf)); - } - else { - easyBoundRepr = ocg->CreateMinus(easyBoundRepr, ocg->CreateInt(-cf)); - } - } - else { - if(easyBoundRepr == NULL) { - easyBoundRepr = ocg->CreateInt(0); - } - } - - if (v_coef > 1) { - assert(ceiling >= 0); - if (ceiling) { - easyBoundRepr= ocg->CreatePlus(easyBoundRepr, ocg->CreateInt(v_coef-1)); - } - easyBoundRepr = ocg->CreateIntegerDivide(easyBoundRepr, ocg->CreateInt(v_coef)); - } - - return easyBoundRepr; -} - - -//---------------------------------------------------------------------------- -// Translate inequality constraints to loop or assignment. -// if return.second is true, return.first is loop structure, -// otherwise it is assignment. -// ---------------------------------------------------------------------------- -std::pair<CG_outputRepr *, bool> outputBounds(CG_outputBuilder* ocg, const Relation &bounds, Variable_ID v, int indent, Relation &enforced, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation b = copy(bounds); - Conjunct *c = b.query_DNF()->single_conjunct(); - - // Elaborate stride simplification which is complementary to gist function - // since we further target the specific loop variable. -- by chun 08/07/2008 - Relation r1 = Relation::True(b.n_set()), r2 = Relation::True(b.n_set()); - for (EQ_Iterator ei(c); ei; ei++) { - if ((*ei).get_coef(v) != 0 && (*ei).has_wildcards()) { // stride condition found - coef_t sign; - if ((*ei).get_coef(v) > 0) - sign = 1; - else - sign = -1; - - coef_t stride = 0; - for (Constr_Vars_Iter cvi(*ei, true); cvi; cvi++) - if ((*cvi).var->kind() == Wildcard_Var) { - stride = abs((*cvi).coef); - break; - } - - // check if stride hits lower bound - bool found_match = false; - if (abs((*ei).get_coef(v)) != 1) { // expensive matching for non-clean stride condition - coef_t d = stride / gcd(abs((*ei).get_coef(v)), stride); - Relation r3 = Relation::True(b.n_set()); - r3.and_with_EQ(*ei); - - for (GEQ_Iterator gi(c); gi; gi++) { - if ((*gi).get_coef(v) == 1 && !(*gi).has_wildcards()) { - Relation r4(b.n_set()); - F_And *f_root = r4.add_and(); - Stride_Handle h = f_root->add_stride(d); - - for (Constr_Vars_Iter cvi(*gi); cvi; cvi++) - switch ((*cvi).var->kind()) { - case Input_Var: { - int pos = (*cvi).var->get_position(); - h.update_coef(r4.set_var(pos), (*cvi).coef); - break; - } - case Global_Var: { - Global_Var_ID g = (*cvi).var->get_global_var(); - Variable_ID v; - if (g->arity() == 0) - v = r4.get_local(g); - else - v = r4.get_local(g, (*cvi).var->function_of()); - h.update_coef(v, (*cvi).coef); - break; - } - default: - fprintf(DebugFile, "can't deal with the variable type in lower bound\n"); - return std::make_pair(static_cast<CG_outputRepr *>(NULL), false); - } - h.update_const((*gi).get_const()); - - Relation r5 = Gist(copy(r3), Intersection(copy(r4), copy(enforced))); - - // replace original stride condition with striding from this lower bound - if (r5.is_obvious_tautology()) { - r1 = Intersection(r1, r4); - found_match = true; - break; - } - } - } - } - else { - for (GEQ_Iterator gi(c); gi; gi++) { - if ((*gi).get_coef(v) == abs((*ei).get_coef(v)) && !(*gi).has_wildcards()) { // potential matching lower bound found - Relation r(b.n_set()); - Stride_Handle h = r.add_and()->add_stride(stride); - - for (Constr_Vars_Iter cvi(*gi); cvi; cvi++) - switch ((*cvi).var->kind()) { - case Input_Var: { - int pos = (*cvi).var->get_position(); - if ((*cvi).var != v) { - int t1 = int_mod((*cvi).coef, stride); - if (t1 != 0) { - coef_t t2 = enforced.query_variable_mod(enforced.set_var(pos), stride); - if (t2 != posInfinity) - h.update_const(t1*t2); - else - h.update_coef(r.set_var(pos), t1); - } - } - else - h.update_coef(r.set_var(pos), (*cvi).coef); - break; - } - case Global_Var: { - Global_Var_ID g = (*cvi).var->get_global_var(); - Variable_ID v; - if (g->arity() == 0) - v = enforced.get_local(g); - else - v = enforced.get_local(g, (*cvi).var->function_of()); - coef_t t = enforced.query_variable_mod(v, stride); - if (t != posInfinity) - h.update_const(t*(*cvi).coef); - else { - Variable_ID v2; - if (g->arity() == 0) - v2 = r.get_local(g); - else - v2 = r.get_local(g, (*cvi).var->function_of()); - h.update_coef(v2, (*cvi).coef); - } - break; - } - default: - fprintf(DebugFile, "can't deal with the variable type in lower bound\n"); - return std::make_pair(static_cast<CG_outputRepr *>(NULL), false); - } - h.update_const((*gi).get_const()); - - bool t = true; - { - Conjunct *c2 = r.query_DNF()->single_conjunct(); - EQ_Handle h2; - for (EQ_Iterator ei2(c2); ei2; ei2++) { - h2 = *ei2; - break; - } - - int sign; - if (h2.get_coef(v) == (*ei).get_coef(v)) - sign = 1; - else - sign = -1; - - t = int_mod(h2.get_const() - sign * (*ei).get_const(), stride) == 0; - - if (t != false) - for (Constr_Vars_Iter cvi(h2); cvi; cvi++) - if ((*cvi).var->kind() != Wildcard_Var && - int_mod((*cvi).coef - sign * (*ei).get_coef((*cvi).var), stride) != 0) { - t = false; - break; - } - - if (t != false) - for (Constr_Vars_Iter cvi(*ei); cvi; cvi++) - if ((*cvi).var->kind() != Wildcard_Var && - int_mod((*cvi).coef - sign * h2.get_coef((*cvi).var), stride) != 0) { - t = false; - break; - } - - } - - if (t) { - // replace original stride condition with striding from this lower bound - F_And *f_root = r1.and_with_and(); - Stride_Handle h = f_root->add_stride(stride); - for (Constr_Vars_Iter cvi(*gi); cvi; cvi++) - switch ((*cvi).var->kind()) { - case Input_Var: { - h.update_coef(r1.set_var((*cvi).var->get_position()), (*cvi).coef); - break; - } - case Global_Var: { - Global_Var_ID g = (*cvi).var->get_global_var(); - Variable_ID v; - if (g->arity() == 0) - v = r1.get_local(g); - else - v = r1.get_local(g, (*cvi).var->function_of()); - h.update_coef(v, (*cvi).coef); - break; - } - default: - fprintf(DebugFile, "can't deal with the variable type in lower bound\n"); - return std::make_pair(static_cast<CG_outputRepr *>(NULL), false); - } - h.update_const((*gi).get_const()); - - found_match = true; - break; - } - } - } - } - - if (!found_match) - r1.and_with_EQ(*ei); - } - else if ((*ei).get_coef(v) == 0) { - Relation r3 = Relation::True(b.n_set()); - r3.and_with_EQ(*ei); - Relation r4 = Gist(r3, copy(enforced)); - if (!r4.is_obvious_tautology()) - r2.and_with_EQ(*ei); - } - else - r2.and_with_EQ(*ei); - } - - // restore remaining inequalities - { - std::map<Variable_ID, Variable_ID> exists_mapping; - F_Exists *fe = r2.and_with_and()->add_exists(); - F_And *f_root = fe->add_and(); - for (GEQ_Iterator gi(c); gi; gi++) { - GEQ_Handle h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*gi); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: { - int pos = v->get_position(); - h.update_coef(r2.set_var(pos), cvi.curr_coef()); - break; - } - case Exists_Var: - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(v); - Variable_ID e; - if (p == exists_mapping.end()) { - e = fe->declare(); - exists_mapping[v] = e; - } - else - e = (*p).second; - h.update_coef(e, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r2.get_local(g); - else - v2 = r2.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(0); - } - } - h.update_const((*gi).get_const()); - } - } - - // overwrite original bounds - { - r1.simplify(); - r2.simplify(); - Relation b2 = Intersection(r1, r2); - b2.simplify(); - for (int i = 1; i <= b.n_set(); i++) - b2.name_set_var(i, b.set_var(i)->name()); - b2.setup_names(); - b = b2; - c = b.query_DNF()->single_conjunct(); - } - - - // get loop strides - EQ_Handle strideEQ; - bool foundStride = false; // stride that can be translated to loop - bool foundSimpleStride = false; // stride that starts from const value - coef_t step = 1; - int num_stride = 0; - - for (EQ_Iterator ei(c); ei; ei++) { - if ((*ei).get_coef(v) != 0 && (*ei).has_wildcards()) { - num_stride++; - - if (abs((*ei).get_coef(v)) != 1) - continue; - - bool t = true; - coef_t d = 1; - for (Constr_Vars_Iter cvi(*ei); cvi; cvi++) - if ((*cvi).var->kind() == Wildcard_Var) { - assert(d==1); - d = abs((*cvi).coef); - } - else if ((*cvi).var->kind() == Input_Var) { - if ((*cvi).var != v) - t = false; - } - else - t = false; - - if (d > step) { - step = d; - foundSimpleStride = t; - strideEQ = *ei; - foundStride = true; - } - } - } - - // More than one stride or complex stride found, we should move all - // but strideEQ to body's guard condition. alas, not implemented. - if (!(num_stride == 0 || (num_stride == 1 && foundStride))) - return std::make_pair(static_cast<CG_outputRepr *>(NULL), false); - - // get loop bounds - int lower_bounds = 0, upper_bounds = 0; - Tuple<CG_outputRepr *> lbList; - Tuple<CG_outputRepr *> ubList; - coef_t const_lb = negInfinity, const_ub = posInfinity; - for (GEQ_Iterator g(c); g; g++) { - coef_t coef = (*g).get_coef(v); - if (coef == 0) - continue; - else if (coef > 0) { // lower bound - lower_bounds++; - if ((*g).is_const(v) && !foundStride) { - //no variables but v in constr - coef_t L,m; - L = -((*g).get_const()); - - m = (*g).get_coef(v); - coef_t sb = (int) (ceil(((float) L) /m)); - set_max(const_lb, sb); - } - else if ((*g).is_const(v) && foundSimpleStride) { - // no variables but v in constr - //make LB fit the stride constraint - coef_t L,m,s,c; - L = -((*g).get_const()); - m = (*g).get_coef(v); - s = step; - c = strideEQ.get_const(); - coef_t sb = (s * (int) (ceil( (float) (L - (c * m)) /(s*m))))+ c; - set_max(const_lb, sb); - } - else - lbList.append(outputLBasRepr(ocg, *g, b, v, step, strideEQ, enforced, assigned_on_the_fly)); - } - else { // upper bound - upper_bounds++; - if ((*g).is_const(v)) { - // no variables but v in constraint - set_min(const_ub,-(*g).get_const()/(*g).get_coef(v)); - } - else - ubList.append(outputUBasRepr(ocg, *g, b, v, step, strideEQ, assigned_on_the_fly)); - } - } - - CG_outputRepr *lbRepr = NULL; - CG_outputRepr *ubRepr = NULL; - if (const_lb != negInfinity) - lbList.append(ocg->CreateInt(const_lb)); - if (lbList.size() > 1) - lbRepr = ocg->CreateInvoke("max", lbList); - else if (lbList.size() == 1) - lbRepr = lbList[1]; - - //protonu - if(fillInBounds && lbList.size() == 1 && const_lb != negInfinity) - lowerBoundForLevel = const_lb; - //end-protonu - - if (const_ub != posInfinity) - ubList.append(ocg->CreateInt(const_ub)); - if (ubList.size() > 1) - ubRepr = ocg->CreateInvoke("min", ubList); - else if (ubList.size() == 1) - ubRepr = ubList[1]; - - //protonu - if(fillInBounds && const_ub != posInfinity) - upperBoundForLevel = const_ub; - //end-protonu - - if (upper_bounds == 0 || lower_bounds == 0) { - return std::make_pair(static_cast<CG_outputRepr *>(NULL), false); - } - else { - // bookkeeping catched constraints in new_knwon - F_Exists *fe = enforced.and_with_and()->add_exists(); - F_And *f_root = fe->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - std::stack<std::pair<GEQ_Handle, Variable_ID> > floor_geq_stack; - std::set<Variable_ID> floor_var_set; - - if (foundStride) { - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(strideEQ); cvi; cvi++) - switch ((*cvi).var->kind()) { - case Input_Var: { - int pos = (*cvi).var->get_position(); - h.update_coef(enforced.set_var(pos), (*cvi).coef); - break; - } - case Exists_Var: - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find((*cvi).var); - Variable_ID e; - if (p == exists_mapping.end()) { - e = fe->declare(); - exists_mapping[(*cvi).var] = e; - } - else - e = (*p).second; - h.update_coef(e, (*cvi).coef); - break; - } - case Global_Var: { - Global_Var_ID g = (*cvi).var->get_global_var(); - Variable_ID e; - if (g->arity() == 0) - e = enforced.get_local(g); - else - e = enforced.get_local(g, (*cvi).var->function_of()); - h.update_coef(e, (*cvi).coef); - break; - } - default: - assert(0); - } - h.update_const(strideEQ.get_const()); - } - - for (GEQ_Iterator gi(c); gi; gi++) - if ((*gi).get_coef(v) != 0) { - GEQ_Handle h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*gi); cvi; cvi++) - switch ((*cvi).var->kind()) { - case Input_Var: { - int pos = (*cvi).var->get_position(); - h.update_coef(enforced.set_var(pos), (*cvi).coef); - break; - } - case Exists_Var: - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find((*cvi).var); - Variable_ID e; - if (p == exists_mapping.end()) { - e = fe->declare(); - exists_mapping[(*cvi).var] = e; - } - else - e = (*p).second; - h.update_coef(e, (*cvi).coef); - - if (floor_var_set.find((*cvi).var) == floor_var_set.end()) { - GEQ_Handle h2; - findFloorInequality(b, (*cvi).var, h2, v); - floor_geq_stack.push(std::make_pair(h2, (*cvi).var)); - floor_var_set.insert((*cvi).var); - } - break; - } - case Global_Var: { - Global_Var_ID g = (*cvi).var->get_global_var(); - Variable_ID e; - if (g->arity() == 0) - e = enforced.get_local(g); - else - e = enforced.get_local(g, (*cvi).var->function_of()); - h.update_coef(e, (*cvi).coef); - break; - } - default: - assert(0); - } - h.update_const((*gi).get_const()); - } - - // add floor definition involving variables appeared in bounds - while (!floor_geq_stack.empty()) { - std::pair<GEQ_Handle, Variable_ID> p = floor_geq_stack.top(); - floor_geq_stack.pop(); - - GEQ_Handle h1 = f_root->add_GEQ(); - GEQ_Handle h2 = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(p.first); cvi; cvi++) { - switch ((*cvi).var->kind()) { - case Input_Var: { - int pos = (*cvi).var->get_position(); - h1.update_coef(enforced.input_var(pos), (*cvi).coef); - h2.update_coef(enforced.input_var(pos), -(*cvi).coef); - break; - } - case Exists_Var: - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p2 = exists_mapping.find((*cvi).var); - Variable_ID e; - if (p2 == exists_mapping.end()) { - e = fe->declare(); - exists_mapping[(*cvi).var] = e; - } - else - e = (*p2).second; - h1.update_coef(e, (*cvi).coef); - h2.update_coef(e, -(*cvi).coef); - - if (floor_var_set.find((*cvi).var) == floor_var_set.end()) { - GEQ_Handle h3; - findFloorInequality(b, (*cvi).var, h3, v); - floor_geq_stack.push(std::make_pair(h3, (*cvi).var)); - floor_var_set.insert((*cvi).var); - } - break; - } - case Global_Var: { - Global_Var_ID g = (*cvi).var->get_global_var(); - Variable_ID e; - if (g->arity() == 0) - e = enforced.get_local(g); - else - e = enforced.get_local(g, (*cvi).var->function_of()); - h1.update_coef(e, (*cvi).coef); - h2.update_coef(e, -(*cvi).coef); - break; - } - default: - assert(0); - } - } - h1.update_const(p.first.get_const()); - h2.update_const(-p.first.get_const()); - h2.update_const(-p.first.get_coef(p.second)-1); - } - enforced.simplify(); - - CG_outputRepr *stRepr = NULL; - if (step != 1) - stRepr = ocg->CreateInt(abs(step)); - CG_outputRepr *indexRepr = outputIdent(ocg, b, v, assigned_on_the_fly); - CG_outputRepr *ctrlRepr = ocg->CreateInductive(indexRepr, lbRepr, ubRepr, stRepr); - - return std::make_pair(ctrlRepr, true); - } -} - - -Relation project_onto_levels(Relation R, int last_level, bool wildcards) { - assert(last_level >= 0 && R.is_set() && last_level <= R.n_set()); - if (last_level == R.n_set()) return R; - - int orig_vars = R.n_set(); - int num_projected = orig_vars - last_level; - R = Extend_Set(R,num_projected - ); // Project out vars numbered > last_level - Mapping m1 = Mapping::Identity(R.n_set()); // now orig_vars+num_proj - - for(int i=last_level+1; i <= orig_vars; i++) { - m1.set_map(Set_Var, i, Exists_Var, i); - m1.set_map(Set_Var, i+num_projected, Set_Var, i); - } - - MapRel1(R, m1, Comb_Id); - R.finalize(); - R.simplify(); - if (!wildcards) - R = Approximate(R,1); - assert(R.is_set()); - return R; -} - - -// Check if the lower bound already enforces the stride by -// (Where m is coef of v in g and L is the bound on m*v): -// Check if m divides L evenly and Check if this l.bound on v implies strideEQ -bool boundHitsStride(const GEQ_Handle &g, Variable_ID v, - const EQ_Handle &strideEQ, - coef_t /*stride*/, // currently unused - Relation known) { -/* m = coef of v in g; - L = bound on v part of g; -*/ - // Check if m divides L evenly - coef_t m = g.get_coef(v); - Relation test(known.n_set()); - F_Exists *e = test.add_exists(); // g is "L >= mv" - Variable_ID alpha = e->declare(); // want: "l = m alpha" - F_And *a = e->add_and(); - EQ_Handle h = a->add_EQ(); - for(Constr_Vars_Iter I(g,false); I; I++) - if((*I).var != v) { - if((*I).var->kind() != Global_Var) - h.update_coef((*I).var, (*I).coef); - else - h.update_coef(test.get_local((*I).var->get_global_var()), (*I).coef); - } - - h.update_const(g.get_const()); - h.update_coef(alpha,m); // set alpha's coef to m - if (!(Gist(test,copy(known)).is_obvious_tautology())) - return false; - // Check if this lower bound on v implies the strideEQ - Relation boundRel = known; // want: "known and l = m v" - boundRel.and_with_EQ(g); // add in l = mv - Relation strideRel(known.n_set()); - strideRel.and_with_EQ(strideEQ); - return Gist(strideRel, boundRel).is_obvious_tautology(); -} - - -// // Return true if there are no variables in g except wildcards & v -bool isSimpleStride(const EQ_Handle &g, Variable_ID v) { - EQ_Handle gg = g; // should not be necessary, but iterators are - // a bit brain-dammaged - bool is_simple=true; - for(Constr_Vars_Iter cvi(gg, false); cvi && is_simple; cvi++) - is_simple = ((*cvi).coef == 0 || (*cvi).var == v - || (*cvi).var->kind() == Wildcard_Var); - return is_simple; -} - - -int countStrides(Conjunct *c, Variable_ID v, EQ_Handle &strideEQ, - bool &simple) { - int strides=0; - for(EQ_Iterator G(c); G; G++) - for(Constr_Vars_Iter I(*G, true); I; I++) - if (((*I).coef != 0) && (*G).get_coef(v) != 0) { - strides++; - simple = isSimpleStride(*G,v); - strideEQ = *G; - break; - } - return strides; -} - -namespace { - -bool hasEQ(Relation r, int level) { - r.simplify(); - Variable_ID v = set_var(level); - Conjunct *s_conj = r.single_conjunct(); - for(EQ_Iterator G(s_conj); G; G++) - if ((*G).get_coef(v)) - return true; - return false; -} - - - -static Relation pickEQ(Relation r, int level) { - r.simplify(); - Variable_ID v = set_var(level); - Conjunct *s_conj = r.single_conjunct(); - for(EQ_Iterator E(s_conj); E; E++) - if ((*E).get_coef(v)) { - Relation test_rel(r.n_set()); - test_rel.and_with_EQ(*E); - return test_rel; - } - assert(0); - return r; -} - -/* pickBound will return an EQ as a GEQ if it finds one */ -Relation pickBound(Relation r, int level, int UB) { - r.simplify(); - Variable_ID v = set_var(level); - Conjunct *s_conj = r.single_conjunct(); - for(GEQ_Iterator G(s_conj); G; G++) { - if ((UB && (*G).get_coef(v) < 0) - || (!UB && (*G).get_coef(v) > 0) ) { - Relation test_rel(r.n_set()); - test_rel.and_with_GEQ(*G); - return test_rel; - } - } - for(EQ_Iterator E(s_conj); E; E++) { - if ((*E).get_coef(v)) { - Relation test_rel(r.n_set()); - test_rel.and_with_GEQ(*E); - if ((UB && (*E).get_coef(v) > 0) - || (!UB && (*E).get_coef(v) < 0) ) - test_rel = Complement(test_rel); - return test_rel; - } - } - assert(0); - return r; -} - -} - -Relation pickOverhead(Relation r, int liftTo) { - r.simplify(); - Conjunct *s_conj = r.single_conjunct(); - for(GEQ_Iterator G(s_conj); G; G++) { - Relation test_rel(r.n_set()); - test_rel.and_with_GEQ(*G); - Variable_ID v; - coef_t pos = -1; - coef_t c= 0; - for(Constr_Vars_Iter cvi(*G, false); cvi; cvi++) - if ((*cvi).coef && (*cvi).var->kind() == Input_Var - && (*cvi).var->get_position() > pos) { - v = (*cvi).var; - pos = (*cvi).var->get_position(); - c = (*cvi).coef; - } -#if 0 - fprintf(DebugFile,"Coef = %d, constraint = %s\n", - c,(const char *)test_rel.print_formula_to_string()); -#endif - return test_rel; - } - for(EQ_Iterator E(s_conj); E; E++) { - assert(liftTo >= 1); - int pos = max((*E).max_tuple_pos(),max_fs_arity(*E)+1); - -/* Pick stride constraints only when the variables with stride are outer - loop variables */ - if ((*E).has_wildcards() && pos < liftTo) { - Relation test_rel(r.n_set()); - test_rel.and_with_EQ(*E); - return test_rel; - } - else if (!(*E).has_wildcards() && pos <= liftTo) { - Relation test_rel(r.n_set()); - test_rel.and_with_EQ(*E); - test_rel.simplify(); - test_rel = EQs_to_GEQs(test_rel,true); - return pickOverhead(test_rel,liftTo); - } - } - if (code_gen_debug>1) { - fprintf(DebugFile,"Could not find overhead:\n"); - r.prefix_print(DebugFile); - } - return Relation::True(r.n_set()); -} - - - -bool hasBound(Relation r, int level, int UB) { - r.simplify(); - Variable_ID v = set_var(level); - Conjunct *s_conj = r.single_conjunct(); - for(GEQ_Iterator G(s_conj); G; G++) { - if (UB && (*G).get_coef(v) < 0) return true; - if (!UB && (*G).get_coef(v) > 0) return true; - } - for(EQ_Iterator E(s_conj); E; E++) { - if ((*E).get_coef(v)) return true; - } - return false; -} - -bool find_any_constraint(int s, int level, Relation &kr, int direction, - Relation &S, bool approx) { - /* If we don't intersect I with restrictions, the combination - of S and restrictions can be unsatisfiable, which means that - the new split node gets pruned away and we still don't have - finite bounds -> infinite recursion. */ - - Relation I = projected_nIS[level][s]; - I = Gist(I,copy(kr)); - if(approx) I = Approximate(I); - if (hasBound(I,level,direction)) { - Relation pickfrom; - if(has_nonstride_EQ(I,level)) - pickfrom = pickEQ(I,level); - else - pickfrom = pickBound(I,level,direction); - S = pickOverhead(pickfrom,level); - if(S.is_obvious_tautology()) S = Relation::Null(); - return !S.is_null(); - } - return false; -} - - -bool has_nonstride_EQ(Relation r, int level) { - r.simplify(); - Variable_ID v = set_var(level); - Conjunct *s_conj = r.single_conjunct(); - for(EQ_Iterator G(s_conj); G; G++) - if ((*G).get_coef(v) && !(*G).has_wildcards()) - return true; - return false; -} - - -Relation minMaxOverhead(Relation r, int level) { - r.finalize(); - r.simplify(); - Conjunct *s_conj = r.single_conjunct(); - GEQ_Handle LBs[50],UBs[50]; - int numLBs = 0; - int numUBs = 0; - Variable_ID v = set_var(level); - for(GEQ_Iterator G(s_conj); G; G++) if ((*G).get_coef(v)) { - GEQ_Handle g = *G; - if (g.get_coef(v) > 0) LBs[numLBs++] = g; - else UBs[numUBs++] = g; - } - if (numLBs <= 1 && numUBs <= 1) { - return Relation::True(r.n_set()); - } - Relation r1(r.n_set()); - Relation r2(r.n_set()); - if (numLBs > 1) { - // remove a max in lower bound - r1.and_with_GEQ(LBs[0]); - r2.and_with_GEQ(LBs[1]); - r1 = project_onto_levels(Difference(r1,r2),level-1,0); - } - else { - // remove a min in upper bound - r1.and_with_GEQ(UBs[0]); - r2.and_with_GEQ(UBs[1]); - r1 = project_onto_levels(Difference(r1,r2),level-1,0); - } -#if 0 - fprintf(DebugFile,"Testing %s\n",(const char *)r1.print_formula_to_string()); - fprintf(DebugFile,"will removed overhead on bounds of t%d: %s\n",level, - (const char *)r.print_formula_to_string()); -#endif - - return pickOverhead(r1, -1); -} - -std::pair<EQ_Handle, int> find_simplest_assignment(const Relation &R_, Variable_ID v, const std::vector<CG_outputRepr *> &assigned_on_the_fly) { - Relation &R = const_cast<Relation &>(R_); - Conjunct *c = R.single_conjunct(); - - int min_cost = INT_MAX; - EQ_Handle eq; - for (EQ_Iterator ei(c->EQs()); ei; ei++) - if (!(*ei).has_wildcards() && (*ei).get_coef(v) != 0) { - int cost = 0; - - if (abs((*ei).get_coef(v)) != 1) - cost += 4; // divide cost - - int num_var = 0; - for (Constr_Vars_Iter cvi(*ei); cvi; cvi++) - if ((*cvi).var != v) { - num_var++; - if ((*cvi).var->kind() == Global_Var && (*cvi).var->get_global_var()->arity() > 0) { - cost += 10; // function cost - } - if (abs((*cvi).coef) != 1) - cost += 2; // multiply cost - if ((*cvi).var->kind() == Input_Var && assigned_on_the_fly[(*cvi).var->get_position()-1] != NULL) { - cost += 5; // substituted variable cost - } - } - if ((*ei).get_const() != 0) - num_var++; - if (num_var > 1) - cost += num_var - 1; // addition cost - - if (cost < min_cost) { - min_cost = cost; - eq = *ei; - } - } - - return std::make_pair(eq, min_cost); -} - -int max_fs_arity(const Constraint_Handle &c) { - int max_arity=0; - for(Constr_Vars_Iter cv(c); cv; cv++) - if((*cv).var->kind() == Global_Var) - max_arity = max(max_arity,(*cv).var->get_global_var()->arity()); - return max_arity; -} - -} |