diff options
author | Tuowen Zhao <ztuowen@gmail.com> | 2016-09-21 22:35:47 -0600 |
---|---|---|
committer | Tuowen Zhao <ztuowen@gmail.com> | 2016-09-21 22:35:47 -0600 |
commit | ab016596602a4c6bdc27adf01c308b325af221f0 (patch) | |
tree | 4e86bfcf1f38fb00cc58082d540dc3570e0f126b /lib/codegen/src | |
parent | 6983c09937baac3ffb7d3a45c3c5009c0eba7e6c (diff) | |
download | chill-ab016596602a4c6bdc27adf01c308b325af221f0.tar.gz chill-ab016596602a4c6bdc27adf01c308b325af221f0.tar.bz2 chill-ab016596602a4c6bdc27adf01c308b325af221f0.zip |
something that only builds ...
Diffstat (limited to 'lib/codegen/src')
-rwxr-xr-x[-rw-r--r--] | lib/codegen/src/CG.cc | 2790 | ||||
-rwxr-xr-x[-rw-r--r--] | lib/codegen/src/CG_stringBuilder.cc | 1001 | ||||
-rwxr-xr-x | lib/codegen/src/CG_stringRepr.cc | 32 | ||||
-rwxr-xr-x | lib/codegen/src/CG_utils.cc | 3959 |
4 files changed, 4801 insertions, 2981 deletions
diff --git a/lib/codegen/src/CG.cc b/lib/codegen/src/CG.cc index 42bd172..5d903c4 100644..100755 --- a/lib/codegen/src/CG.cc +++ b/lib/codegen/src/CG.cc @@ -1,4 +1,6 @@ + /***************************************************************************** + Copyright (C) 1994-2000 the Omega Project Team Copyright (C) 2005-2011 Chun Chen All Rights Reserved. @@ -19,7 +21,7 @@ 08/03/10 collect CG classes into one place, by Chun Chen 08/04/10 track dynamically substituted variables in printRepr, by chun 04/02/11 rewrite the CG node classes, by chun - *****************************************************************************/ +*****************************************************************************/ #include <typeinfo> #include <assert.h> @@ -34,1130 +36,1666 @@ #include <string.h> namespace omega { - -extern std::vector<std::vector<int> > smtNonSplitLevels; -extern std::vector<std::vector<std::string> > loopIdxNames; //per stmt -extern std::vector<std::pair<int, std::string> > syncs; - -extern int checkLoopLevel; -extern int stmtForLoopCheck; -extern int upperBoundForLevel; -extern int lowerBoundForLevel; -extern bool fillInBounds; - -//----------------------------------------------------------------------------- -// Class: CG_result -//----------------------------------------------------------------------------- - -CG_outputRepr *CG_result::printRepr(CG_outputBuilder *ocg, - const std::vector<CG_outputRepr *> &stmts) const { - return printRepr(1, ocg, stmts, - std::vector<std::pair<CG_outputRepr *, int> >(num_level(), - std::make_pair(static_cast<CG_outputRepr *>(NULL), 0))); -} - -std::string CG_result::printString() const { - CG_stringBuilder ocg; - std::vector<CG_outputRepr *> stmts(codegen_->xforms_.size()); - for (int i = 0; i < stmts.size(); i++) - stmts[i] = new CG_stringRepr("s" + to_string(i)); - CG_stringRepr *repr = static_cast<CG_stringRepr *>(printRepr(&ocg, stmts)); - for (int i = 0; i < stmts.size(); i++) - delete stmts[i]; - - if (repr != NULL) { - std::string s = repr->GetString(); - delete repr; - return s; - } else - return std::string(); -} - -int CG_result::num_level() const { - return codegen_->num_level(); -} - -//----------------------------------------------------------------------------- -// Class: CG_split -//----------------------------------------------------------------------------- - -CG_result *CG_split::recompute(const BoolSet<> &parent_active, - const Relation &known, const Relation &restriction) { - active_ &= parent_active; - if (active_.empty()) { - delete this; - return NULL; - } - - - int i = 0; - while (i < restrictions_.size()) { - Relation new_restriction = Intersection(copy(restrictions_[i]), - copy(restriction)); - - new_restriction.simplify(2, 4); - //new_restriction.simplify(); - clauses_[i] = clauses_[i]->recompute(active_, copy(known), - new_restriction); - if (clauses_[i] == NULL) { - restrictions_.erase(restrictions_.begin() + i); - clauses_.erase(clauses_.begin() + i); - } else - i++; - } - - - if (restrictions_.size() == 0) { - delete this; - return NULL; - } else - return this; -} - -int CG_split::populateDepth() { - int max_depth = 0; - for (int i = 0; i < clauses_.size(); i++) { - int t = clauses_[i]->populateDepth(); - if (t > max_depth) - max_depth = t; - } - return max_depth; -} - -std::pair<CG_result *, Relation> CG_split::liftOverhead(int depth, - bool propagate_up) { - for (int i = 0; i < clauses_.size();) { - std::pair<CG_result *, Relation> result = clauses_[i]->liftOverhead( - depth, propagate_up); - if (result.first == NULL) - clauses_.erase(clauses_.begin() + i); - else { - clauses_[i] = result.first; - if (!result.second.is_obvious_tautology()) - return std::make_pair(this, result.second); - i++; - } - - } - - if (clauses_.size() == 0) { - delete this; - return std::make_pair(static_cast<CG_result *>(NULL), - Relation::True(num_level())); - } else - return std::make_pair(this, Relation::True(num_level())); -} - -Relation CG_split::hoistGuard() { - std::vector<Relation> guards; - for (int i = 0; i < clauses_.size(); i++) - guards.push_back(clauses_[i]->hoistGuard()); - - return SimpleHull(guards, true, true); -} - -void CG_split::removeGuard(const Relation &guard) { - for (int i = 0; i < clauses_.size(); i++) - clauses_[i]->removeGuard(guard); -} - -std::vector<CG_result *> CG_split::findNextLevel() const { - std::vector<CG_result *> result; - for (int i = 0; i < clauses_.size(); i++) { - CG_split *splt = dynamic_cast<CG_split *>(clauses_[i]); - if (splt != NULL) { - std::vector<CG_result *> t = splt->findNextLevel(); - result.insert(result.end(), t.begin(), t.end()); - } else - result.push_back(clauses_[i]); - } - - return result; -} - -CG_outputRepr *CG_split::printRepr(int indent, CG_outputBuilder *ocg, - const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const { - CG_outputRepr *stmtList = NULL; - std::vector<CG_result *> next_level = findNextLevel(); - - std::vector<CG_loop *> cur_loops; - for (int i = 0; i < next_level.size(); i++) { - CG_loop *lp = dynamic_cast<CG_loop *>(next_level[i]); - if (lp != NULL) { - cur_loops.push_back(lp); - } else { - stmtList = ocg->StmtListAppend(stmtList, - loop_print_repr(cur_loops, 0, cur_loops.size(), - Relation::True(num_level()), NULL, indent, ocg, - stmts, assigned_on_the_fly)); - stmtList = ocg->StmtListAppend(stmtList, - next_level[i]->printRepr(indent, ocg, stmts, - assigned_on_the_fly)); - cur_loops.clear(); - } - } - - stmtList = ocg->StmtListAppend(stmtList, - loop_print_repr(cur_loops, 0, cur_loops.size(), - Relation::True(num_level()), NULL, indent, ocg, stmts, - assigned_on_the_fly)); - return stmtList; -} - -CG_result *CG_split::clone() const { - std::vector<CG_result *> clauses(clauses_.size()); - for (int i = 0; i < clauses_.size(); i++) - clauses[i] = clauses_[i]->clone(); - return new CG_split(codegen_, active_, restrictions_, clauses); -} - -void CG_split::dump(int indent) const { - std::string prefix; - for (int i = 0; i < indent; i++) - prefix += " "; - std::cout << prefix << "SPLIT: " << active_ << std::endl; - for (int i = 0; i < restrictions_.size(); i++) { - std::cout << prefix << "restriction: "; - const_cast<CG_split *>(this)->restrictions_[i].print(); - clauses_[i]->dump(indent + 1); - } - -} - -//----------------------------------------------------------------------------- -// Class: CG_loop -//----------------------------------------------------------------------------- - -CG_result *CG_loop::recompute(const BoolSet<> &parent_active, - const Relation &known, const Relation &restriction) { - known_ = copy(known); - restriction_ = copy(restriction); - active_ &= parent_active; - - std::vector<Relation> Rs; - for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { - Relation r = Intersection(copy(restriction), - copy(codegen_->projected_IS_[level_ - 1][*i])); - - //r.simplify(2, 4); - r.simplify(); - if (!r.is_upper_bound_satisfiable()) { - active_.unset(*i); - continue; - } - Rs.push_back(copy(r)); - } - - if (active_.empty()) { - delete this; - return NULL; - } - - Relation hull = SimpleHull(Rs, true, true); - - //hull.simplify(2,4); - - // check if actual loop is needed - std::pair<EQ_Handle, int> result = find_simplest_assignment(hull, - hull.set_var(level_)); - if (result.second < INT_MAX) { - needLoop_ = false; - - bounds_ = Relation(hull.n_set()); - F_Exists *f_exists = bounds_.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(bounds_.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2 = replicate_floor_definition(hull, v, bounds_, - f_exists, f_root, exists_mapping); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = bounds_.get_local(g); - else - v2 = bounds_.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const(result.first.get_const()); - bounds_.simplify(); - } - // loop iterates more than once, extract bounds now - else { - needLoop_ = true; - - bounds_ = Relation(hull.n_set()); - F_Exists *f_exists = bounds_.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - - Relation b = Gist(copy(hull), copy(known), 1); - bool has_unresolved_bound = false; - - std::set<Variable_ID> excluded_floor_vars; - excluded_floor_vars.insert(b.set_var(level_)); - for (GEQ_Iterator e(b.single_conjunct()->GEQs()); e; e++) - if ((*e).get_coef(b.set_var(level_)) != 0) { - bool is_bound = true; - for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) { - std::pair<bool, GEQ_Handle> result = find_floor_definition( - b, cvi.curr_var(), excluded_floor_vars); - if (!result.first) { - is_bound = false; - has_unresolved_bound = true; - break; - } - } - - if (!is_bound) - continue; - - GEQ_Handle h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(bounds_.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2 = replicate_floor_definition(b, v, - bounds_, f_exists, f_root, exists_mapping); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = bounds_.get_local(g); - else - v2 = bounds_.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const((*e).get_const()); - } - - if (has_unresolved_bound) { - b = Approximate(b); - b.simplify(2, 4); - //Simplification of Hull - hull = Approximate(hull); - hull.simplify(2, 4); - //end : Anand - for (GEQ_Iterator e(b.single_conjunct()->GEQs()); e; e++) - if ((*e).get_coef(b.set_var(level_)) != 0) - f_root->add_GEQ(*e); - } - bounds_.simplify(); - hull.simplify(2,4); - // Since current SimpleHull does not support max() upper bound or min() lower bound, - // we have to forcefully split the loop when hull approximation does not return any bound. - bool has_lb = false; - bool has_ub = false; - for (GEQ_Iterator e = bounds_.single_conjunct()->GEQs(); e; e++) { - if ((*e).get_coef(bounds_.set_var(level_)) > 0) - has_lb = true; - else if ((*e).get_coef(bounds_.set_var(level_)) < 0) - has_ub = true; - if (has_lb && has_ub) - break; - } - - if (!has_lb) { - for (int i = 0; i < Rs.size(); i++) { - Relation r = Approximate(copy(Rs[i])); - r.simplify(2, 4); - for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++) - if ((*e).get_coef(r.input_var(level_)) > 0) { - Relation r2 = Relation::True(num_level()); - r2.and_with_GEQ(*e); - r2.simplify(); - std::vector<Relation> restrictions(2); - restrictions[0] = Complement(copy(r2)); - restrictions[0].simplify(); - restrictions[1] = r2; - std::vector<CG_result *> clauses(2); - clauses[0] = this; - clauses[1] = this->clone(); - CG_result *cgr = new CG_split(codegen_, active_, - restrictions, clauses); - cgr = cgr->recompute(active_, copy(known), - copy(restriction)); - return cgr; - } - } - for (int i = 0; i < Rs.size(); i++) { - Relation r = Approximate(copy(Rs[i])); - r.simplify(2, 4); - for (EQ_Iterator e = r.single_conjunct()->EQs(); e; e++) - if ((*e).get_coef(r.input_var(level_)) != 0) { - Relation r2 = Relation::True(num_level()); - r2.and_with_GEQ(*e); - r2.simplify(); - std::vector<Relation> restrictions(2); - if ((*e).get_coef(r.input_var(level_)) > 0) { - restrictions[0] = Complement(copy(r2)); - restrictions[0].simplify(); - restrictions[1] = r2; - } else { - restrictions[0] = r2; - restrictions[1] = Complement(copy(r2)); - restrictions[1].simplify(); - } - std::vector<CG_result *> clauses(2); - clauses[0] = this; - clauses[1] = this->clone(); - CG_result *cgr = new CG_split(codegen_, active_, - restrictions, clauses); - cgr = cgr->recompute(active_, copy(known), - copy(restriction)); - return cgr; - } - } - } else if (!has_ub) { - for (int i = 0; i < Rs.size(); i++) { - Relation r = Approximate(copy(Rs[i])); - r.simplify(2, 4); - for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++) - if ((*e).get_coef(r.input_var(level_)) < 0) { - Relation r2 = Relation::True(num_level()); - r2.and_with_GEQ(*e); - r2.simplify(); - std::vector<Relation> restrictions(2); - restrictions[1] = Complement(copy(r2)); - restrictions[1].simplify(); - restrictions[0] = r2; - std::vector<CG_result *> clauses(2); - clauses[0] = this; - clauses[1] = this->clone(); - CG_result *cgr = new CG_split(codegen_, active_, - restrictions, clauses); - cgr = cgr->recompute(active_, copy(known), - copy(restriction)); - return cgr; - } - } - for (int i = 0; i < Rs.size(); i++) { - Relation r = Approximate(copy(Rs[i])); - r.simplify(2, 4); - for (EQ_Iterator e = r.single_conjunct()->EQs(); e; e++) - if ((*e).get_coef(r.input_var(level_)) != 0) { - Relation r2 = Relation::True(num_level()); - r2.and_with_GEQ(*e); - r2.simplify(); - std::vector<Relation> restrictions(2); - if ((*e).get_coef(r.input_var(level_)) > 0) { - restrictions[0] = Complement(copy(r2)); - restrictions[0].simplify(); - restrictions[1] = r2; - } else { - restrictions[0] = r2; - restrictions[1] = Complement(copy(r2)); - restrictions[1].simplify(); - } - std::vector<CG_result *> clauses(2); - clauses[0] = this; - clauses[1] = this->clone(); - CG_result *cgr = new CG_split(codegen_, active_, - restrictions, clauses); - cgr = cgr->recompute(active_, copy(known), - copy(restriction)); - return cgr; - } - } - } - - if (!has_lb && !has_ub) - throw codegen_error( - "can't find any bound at loop level " + to_string(level_)); - else if (!has_lb) - throw codegen_error( - "can't find lower bound at loop level " - + to_string(level_)); - else if (!has_ub) - throw codegen_error( - "can't find upper bound at loop level " - + to_string(level_)); - } - bounds_.copy_names(hull); - bounds_.setup_names(); - - // additional guard/stride condition extraction - if (needLoop_) { - Relation cur_known = Intersection(copy(bounds_), copy(known_)); - cur_known.simplify(); - hull = Gist(hull, copy(cur_known), 1); - - std::pair<EQ_Handle, Variable_ID> result = find_simplest_stride(hull, - hull.set_var(level_)); - if (result.second != NULL) - if (abs(result.first.get_coef(hull.set_var(level_))) == 1) { - F_Exists *f_exists = bounds_.and_with_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(bounds_.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2; - if (v == result.second) - v2 = f_exists->declare(); - else - v2 = replicate_floor_definition(hull, v, bounds_, - f_exists, f_root, exists_mapping); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = bounds_.get_local(g); - else - v2 = bounds_.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const(result.first.get_const()); - } else { - // since gist is not powerful enough on modular constraints for now, - // make an educated guess - coef_t stride = abs(result.first.get_coef(result.second)) - / gcd(abs(result.first.get_coef(result.second)), - abs( - result.first.get_coef( - hull.set_var(level_)))); - - Relation r1(hull.n_inp()); - F_Exists *f_exists = r1.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(r1.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2; - if (v == result.second) - v2 = f_exists->declare(); - else - v2 = replicate_floor_definition(hull, v, r1, - f_exists, f_root, exists_mapping); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r1.get_local(g); - else - v2 = r1.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const(result.first.get_const()); - r1.simplify(); - - bool guess_success = false; - for (GEQ_Iterator e(bounds_.single_conjunct()->GEQs()); e; e++) - if ((*e).get_coef(bounds_.set_var(level_)) == 1) { - Relation r2(hull.n_inp()); - F_Exists *f_exists = r2.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - EQ_Handle h = f_root->add_EQ(); - h.update_coef(f_exists->declare(), stride); - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(r2.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2 = replicate_floor_definition( - hull, v, r2, f_exists, f_root, - exists_mapping); - h.update_coef(v2, 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(false); - } - } - h.update_const((*e).get_const()); - r2.simplify(); - - if (Gist(copy(r1), - Intersection(copy(cur_known), copy(r2)), 1).is_obvious_tautology() - && Gist(copy(r2), - Intersection(copy(cur_known), copy(r1)), - 1).is_obvious_tautology()) { - bounds_ = Intersection(bounds_, r2); - bounds_.simplify(); - guess_success = true; - break; - } - } - - // this is really a stride with non-unit coefficient for this loop variable - if (!guess_success) { - // TODO: for stride ax = b mod n it might be beneficial to - // generate modular linear equation solver code for - // runtime to get the starting position in printRepr, - // and stride would be n/gcd(|a|,n), thus this stride - // can be put into bounds_ too. - } - - } - - hull = Project(hull, hull.set_var(level_)); - hull.simplify(2, 4); - guard_ = Gist(hull, Intersection(copy(bounds_), copy(known_)), 1); - } - // don't generate guard for non-actual loop, postpone it. otherwise - // redundant if-conditions might be generated since for-loop semantics - // includes implicit comparison checking. -- by chun 09/14/10 - else - guard_ = Relation::True(num_level()); - guard_.copy_names(bounds_); - guard_.setup_names(); - - //guard_.simplify(); - // recursively down the AST - Relation new_known = Intersection(copy(known), - Intersection(copy(bounds_), copy(guard_))); - new_known.simplify(2, 4); - Relation new_restriction = Intersection(copy(restriction), - Intersection(copy(bounds_), copy(guard_))); - new_restriction.simplify(2, 4); - body_ = body_->recompute(active_, new_known, new_restriction); - if (body_ == NULL) { - delete this; - return NULL; - } else - return this; -} - -int CG_loop::populateDepth() { - int depth = body_->populateDepth(); - if (needLoop_) - depth_ = depth + 1; - else - depth_ = depth; - return depth_; -} - -std::pair<CG_result *, Relation> CG_loop::liftOverhead(int depth, - bool propagate_up) { - if (depth_ > depth) { - assert(propagate_up == false); - std::pair<CG_result *, Relation> result = body_->liftOverhead(depth, - false); - body_ = result.first; - return std::make_pair(this, Relation::True(num_level())); - } else { // (depth_ <= depth) - if (propagate_up) { - Relation r = pick_one_guard(guard_, level_); - if (!r.is_obvious_tautology()) - return std::make_pair(this, r); - } - - std::pair<CG_result *, Relation> result; - if (propagate_up || needLoop_) - result = body_->liftOverhead(depth, true); - else - result = body_->liftOverhead(depth, false); - body_ = result.first; - if (result.second.is_obvious_tautology()) - return std::make_pair(this, result.second); - - // loop is an assignment, replace this loop variable in overhead condition - if (!needLoop_) { - result.second = Intersection(result.second, copy(bounds_)); - result.second = Project(result.second, - result.second.set_var(level_)); - result.second.simplify(2, 4); - } - - - int max_level = 0; - bool has_wildcard = false; - bool direction = true; - for (EQ_Iterator e(result.second.single_conjunct()->EQs()); e; e++) - if ((*e).has_wildcards()) { - if (has_wildcard) - assert(false); - else - has_wildcard = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - } else - assert(false); - - if (!has_wildcard) { - int num_simple_geq = 0; - for (GEQ_Iterator e(result.second.single_conjunct()->GEQs()); e; - e++) - if (!(*e).has_wildcards()) { - num_simple_geq++; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) { - max_level = cvi.curr_var()->get_position(); - direction = (cvi.curr_coef() < 0) ? true : false; - } - } else { - has_wildcard = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) { - max_level = cvi.curr_var()->get_position(); - } - } - assert( - (has_wildcard && num_simple_geq == 0) || (!has_wildcard && num_simple_geq == 1)); - } - - // check if this is the top loop level for splitting for this overhead - if (!propagate_up || (has_wildcard && max_level == level_ - 1) - || (!has_wildcard && max_level == level_)) { - std::vector<Relation> restrictions(2); - std::vector<CG_result *> clauses(2); - int saved_num_level = num_level(); - if (has_wildcard || direction) { - restrictions[1] = Complement(copy(result.second)); - restrictions[1].simplify(); - clauses[1] = this->clone(); - restrictions[0] = result.second; - clauses[0] = this; - } else { - restrictions[0] = Complement(copy(result.second)); - restrictions[0].simplify(); - clauses[0] = this->clone(); - restrictions[1] = result.second; - clauses[1] = this; - } - CG_result *cgr = new CG_split(codegen_, active_, restrictions, - clauses); - CG_result *new_cgr = cgr->recompute(active_, copy(known_), - copy(restriction_)); - new_cgr->populateDepth(); - assert(new_cgr==cgr); - if (static_cast<CG_split *>(new_cgr)->clauses_.size() == 1) - // infinite recursion detected, bail out - return std::make_pair(new_cgr, Relation::True(saved_num_level)); - else - return cgr->liftOverhead(depth, propagate_up); - } else - return std::make_pair(this, result.second); - } -} - -Relation CG_loop::hoistGuard() { - - Relation r = body_->hoistGuard(); - - // TODO: should bookkeep catched contraints in loop output as enforced and check if anything missing - // if (!Gist(copy(b), copy(enforced)).is_obvious_tautology()) { - // fprintf(stderr, "need to generate extra guard inside the loop\n"); - // } - - if (!needLoop_) - r = Intersection(r, copy(bounds_)); - r = Project(r, r.set_var(level_)); - r = Gist(r, copy(known_), 1); - - Relation eliminate_existentials_r; - Relation eliminate_existentials_known; - - eliminate_existentials_r = copy(r); - if (!r.is_obvious_tautology()) { - eliminate_existentials_r = Approximate(copy(r)); - eliminate_existentials_r.simplify(2,4); - eliminate_existentials_known = Approximate(copy(known_)); - eliminate_existentials_known.simplify(2,4); - - eliminate_existentials_r = Gist( eliminate_existentials_r, eliminate_existentials_known, 1); - } + + extern std::vector<std::vector<int> > smtNonSplitLevels; + extern std::vector<std::vector<std::string> > loopIdxNames; //per stmt + extern std::vector<std::pair<int, std::string> > syncs; + + extern int checkLoopLevel; + extern int stmtForLoopCheck; + extern int upperBoundForLevel; + extern int lowerBoundForLevel; + extern bool fillInBounds; + + //----------------------------------------------------------------------------- + // Class: CG_result + //----------------------------------------------------------------------------- + + CG_outputRepr *CG_result::printRepr(CG_outputBuilder *ocg, + const std::vector<CG_outputRepr *> &stmts, + std::vector<std::map<std::string, std::vector<CG_outputRepr *> > > uninterpreted_symbols, + bool printString) const { + fprintf(stderr, "\nCG_result::printRepr(ocg, stmts) \n"); + //Anand: making a tweak to allocate twice the original number of dynamically allocated variables + //for use with Uninterpreted function symbols + + //Anand: adding support for Replacing substituted variables within + //Uninterpreted function symbols or global variables with arity > 0 here + //--begin + + // check for an error that happened once + int num_unin = uninterpreted_symbols.size(); + int num_active = active_.size(); + if (num_unin < num_active) { + fprintf(stderr, "CG.cc CG_result::printRepr(), not enough uninterpreted symbols (%d) for active statements (5d)\n", num_unin, num_active); + exit(-1); + } + + std::vector<std::pair<CG_outputRepr *, int> > aotf = std::vector< + std::pair<CG_outputRepr *, int> >(2 * num_level(), + std::make_pair(static_cast<CG_outputRepr *>(NULL), 0)); + +#define DYINGHERE +#ifdef DYINGHERE + int num_levels = num_level(); + + for (int s = 0; s < active_.size(); s++) { + fprintf(stderr, "\ns %d\n", s); + std::vector<std::string> loop_vars; + if (active_.get(s)) { + + Relation mapping = Inverse( + copy((codegen_->xforms_[codegen_->remap_[s]]))); + + mapping.simplify(); + mapping.setup_names(); + + for (int i = 1; i <= mapping.n_out(); i++) + loop_vars.push_back(mapping.output_var(i)->name()); + + std::vector<CG_outputRepr *> subs_; + for (int i = 1; i <= mapping.n_out(); i++) { + Relation mapping1(mapping.n_out(), 1); + F_And *f_root = mapping1.add_and(); + EQ_Handle h = f_root->add_EQ(); + h.update_coef(mapping1.output_var(1), 1); + h.update_coef(mapping1.input_var(i), -1); + Relation r = Composition(mapping1, copy(mapping)); + r.simplify(); - - if (!eliminate_existentials_r.is_obvious_tautology()) { - // if (!r.is_obvious_tautology()) { - body_->removeGuard(r); - guard_ = Intersection(guard_, copy(r)); - guard_.simplify(); - } - - return guard_; - - // return ifList; - // } - - -} - -void CG_loop::removeGuard(const Relation &guard) { - known_ = Intersection(known_, copy(guard)); - known_.simplify(); - - guard_ = Gist(guard_, copy(known_), 1); - guard_.copy_names(known_); - guard_.setup_names(); -} - -CG_outputRepr *CG_loop::printRepr(int indent, CG_outputBuilder *ocg, - const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const { - return printRepr(true, indent, ocg, stmts, assigned_on_the_fly); -} - -CG_outputRepr *CG_loop::printRepr(bool do_print_guard, int indent, - CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const { - CG_outputRepr *guardRepr; - if (do_print_guard) - guardRepr = output_guard(ocg, guard_, assigned_on_the_fly); - else - guardRepr = NULL; - - Relation cur_known = Intersection(copy(known_), copy(guard_)); - cur_known.simplify(); - if (needLoop_) { - - if (checkLoopLevel) - if (level_ == checkLoopLevel) - if (active_.get(stmtForLoopCheck)) - fillInBounds = true; - - CG_outputRepr *ctrlRepr = output_loop(ocg, bounds_, level_, cur_known, - assigned_on_the_fly); - - fillInBounds = false; - - CG_outputRepr *bodyRepr = body_->printRepr( - (guardRepr == NULL) ? indent + 1 : indent + 2, ocg, stmts, - assigned_on_the_fly); - CG_outputRepr * loopRepr; - - if (guardRepr == NULL) - loopRepr = ocg->CreateLoop(indent, ctrlRepr, bodyRepr); - else - loopRepr = ocg->CreateLoop(indent + 1, ctrlRepr, bodyRepr); - - if (!smtNonSplitLevels.empty()) { - bool blockLoop = false; - bool threadLoop = false; - bool sync = false; - int firstActiveStmt = -1; - for (int s = 0; s < active_.size(); s++) { - if (active_.get(s)) { - if (firstActiveStmt < 0) - firstActiveStmt = s; - //We assume smtNonSplitLevels is only used to mark the first of - //the block or thread loops to be reduced in CUDA-CHiLL. Here we - //place some comments to help with final code generation. - //int idx = smtNonSplitLevels[s].index(level_); - - if (s < smtNonSplitLevels.size()) { - if (smtNonSplitLevels[s].size() > 0) - if (smtNonSplitLevels[s][0] == level_) { - blockLoop = true; - } - //Assume every stmt marked with a thread loop index also has a block loop idx - if (smtNonSplitLevels[s].size() > 1) - if (smtNonSplitLevels[s][1] == level_) { - threadLoop = true; - } - } - } - } - if (blockLoop && threadLoop) { - fprintf(stderr, - "Warning, have %d level more than once in smtNonSplitLevels\n", - level_); - threadLoop = false; - } - std::string preferredIdx; - if (loopIdxNames.size() - && (level_ / 2) - 1 < loopIdxNames[firstActiveStmt].size()) - preferredIdx = loopIdxNames[firstActiveStmt][(level_ / 2) - 1]; - for (int s = 0; s < active_.size(); s++) { - if (active_.get(s)) { - for (int i = 0; i < syncs.size(); i++) { - if (syncs[i].first == s - && strcmp(syncs[i].second.c_str(), - preferredIdx.c_str()) == 0) { - sync = true; - //printf("FOUND SYNC\n"); - } - - } - } - - } - if (threadLoop || blockLoop || preferredIdx.length() != 0) { - char buf[1024]; - std::string loop; - if (blockLoop) - loop = "blockLoop "; - if (threadLoop) - loop = "threadLoop "; - if (preferredIdx.length() != 0 && sync) { - sprintf(buf, "~cuda~ %spreferredIdx: %s sync", loop.c_str(), - preferredIdx.c_str()); - } else if (preferredIdx.length() != 0) { - sprintf(buf, "~cuda~ %spreferredIdx: %s", loop.c_str(), - preferredIdx.c_str()); - } else { - sprintf(buf, "~cuda~ %s", loop.c_str()); - } - - - loopRepr = ocg->CreateAttribute(loopRepr, buf); - } - - } - if (guardRepr == NULL) - return loopRepr; - else - return ocg->CreateIf(indent, guardRepr, loopRepr, NULL); - } else { - std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > result = - output_assignment(ocg, bounds_, level_, cur_known, - assigned_on_the_fly); - guardRepr = ocg->CreateAnd(guardRepr, result.first); - - if (result.second.second < CodeGen::var_substitution_threshold) { - std::vector<std::pair<CG_outputRepr *, int> > atof = - assigned_on_the_fly; - atof[level_ - 1] = result.second; - CG_outputRepr *bodyRepr = body_->printRepr( - (guardRepr == NULL) ? indent : indent + 1, ocg, stmts, - atof); - delete atof[level_ - 1].first; - if (guardRepr == NULL) - return bodyRepr; - else - return ocg->CreateIf(indent, guardRepr, bodyRepr, NULL); - } else { - CG_outputRepr *assignRepr = ocg->CreateAssignment( - (guardRepr == NULL) ? indent : indent + 1, - output_ident(ocg, bounds_, - const_cast<CG_loop *>(this)->bounds_.set_var( - level_), assigned_on_the_fly), - result.second.first); - CG_outputRepr *bodyRepr = body_->printRepr( - (guardRepr == NULL) ? indent : indent + 1, ocg, stmts, - assigned_on_the_fly); - if (guardRepr == NULL) - return ocg->StmtListAppend(assignRepr, bodyRepr); - else - return ocg->CreateIf(indent, guardRepr, - ocg->StmtListAppend(assignRepr, bodyRepr), NULL); - } - - } -} - -CG_result *CG_loop::clone() const { - return new CG_loop(codegen_, active_, level_, body_->clone()); -} - -void CG_loop::dump(int indent) const { - std::string prefix; - for (int i = 0; i < indent; i++) - prefix += " "; - std::cout << prefix << "LOOP (level " << level_ << "): " << active_ - << std::endl; - std::cout << prefix << "known: "; - const_cast<CG_loop *>(this)->known_.print(); - std::cout << prefix << "restriction: "; - const_cast<CG_loop *>(this)->restriction_.print(); - std::cout << prefix << "bounds: "; - const_cast<CG_loop *>(this)->bounds_.print(); - std::cout << prefix << "guard: "; - const_cast<CG_loop *>(this)->guard_.print(); - body_->dump(indent + 1); -} - -//----------------------------------------------------------------------------- -// Class: CG_leaf -//----------------------------------------------------------------------------- - -CG_result* CG_leaf::recompute(const BoolSet<> &parent_active, - const Relation &known, const Relation &restriction) { - active_ &= parent_active; - known_ = copy(known); - - guards_.clear(); - for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { - Relation r = Intersection( - copy(codegen_->projected_IS_[num_level() - 1][*i]), - copy(restriction)); - r.simplify(2, 4); - if (!r.is_upper_bound_satisfiable()) - active_.unset(*i); - else { - r = Gist(r, copy(known), 1); - if (!r.is_obvious_tautology()) { - guards_[*i] = r; - guards_[*i].copy_names(known); - guards_[*i].setup_names(); - } - } - } - - - if (active_.empty()) { - delete this; - return NULL; - } else - return this; -} - -std::pair<CG_result *, Relation> CG_leaf::liftOverhead(int depth, bool) { - if (depth == 0) - return std::make_pair(this, Relation::True(num_level())); - - for (std::map<int, Relation>::iterator i = guards_.begin(); - i != guards_.end(); i++) { - Relation r = pick_one_guard(i->second); - if (!r.is_obvious_tautology()) { - bool has_wildcard = false; - int max_level = 0; - for (EQ_Iterator e(r.single_conjunct()->EQs()); e; e++) { - if ((*e).has_wildcards()) - has_wildcard = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - } - for (GEQ_Iterator e(r.single_conjunct()->GEQs()); e; e++) { - if ((*e).has_wildcards()) - has_wildcard = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - } - - if (!(has_wildcard && max_level == codegen_->num_level())) - return std::make_pair(this, r); - } - } - - return std::make_pair(this, Relation::True(num_level())); -} - -Relation CG_leaf::hoistGuard() { - std::vector<Relation> guards; - for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { - std::map<int, Relation>::iterator j = guards_.find(*i); - if (j == guards_.end()) { - Relation r = Relation::True(num_level()); - r.copy_names(known_); - r.setup_names(); - return r; - } else { - guards.push_back(j->second); - } - } - - return SimpleHull(guards, true, true); -} - -void CG_leaf::removeGuard(const Relation &guard) { - known_ = Intersection(known_, copy(guard)); - known_.simplify(); - - std::map<int, Relation>::iterator i = guards_.begin(); - while (i != guards_.end()) { - i->second = Gist(i->second, copy(known_), 1); - if (i->second.is_obvious_tautology()) - guards_.erase(i++); - else - ++i; - } -} - -CG_outputRepr *CG_leaf::printRepr(int indent, CG_outputBuilder *ocg, - const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const { - return leaf_print_repr(active_, guards_, NULL, known_, indent, ocg, - codegen_->remap_, codegen_->xforms_, stmts, assigned_on_the_fly); -} - -CG_result *CG_leaf::clone() const { - return new CG_leaf(codegen_, active_); -} - -void CG_leaf::dump(int indent) const { - std::string prefix; - for (int i = 0; i < indent; i++) - prefix += " "; - std::cout << prefix << "LEAF: " << active_ << std::endl; - std::cout << prefix << "known: "; - const_cast<CG_leaf *>(this)->known_.print(); - for (std::map<int, Relation>::const_iterator i = guards_.begin(); - i != guards_.end(); i++) { - std::cout << prefix << "guard #" << i->first << ":"; - const_cast<Relation &>(i->second).print(); - } -} - + //Relation r = copy(mapping); + + Variable_ID v = r.output_var(1); + loop_vars.push_back(mapping.output_var(i)->name()); + + std::pair<EQ_Handle, int> result = find_simplest_assignment(r, + v, aotf); + + std::string hand = result.first.print_to_string(); + //fprintf(stderr, "result: %s, %d\n", hand.c_str(), result.second); + if (result.second < INT_MAX) { + + CG_outputRepr *subs = output_substitution_repr(ocg, + result.first, + v, + true, + r, + aotf, + uninterpreted_symbols[s]); + + subs_.push_back(subs->clone()); + + aotf[num_levels + i - 1] = std::make_pair(subs, 999); + + } else { + CG_outputRepr* repr = NULL; + + aotf[num_levels + i - 1] = std::make_pair(repr, 999); + } + } + if(!printString) + for (std::map<std::string, std::vector<CG_outputRepr *> >::iterator it = + uninterpreted_symbols[s].begin(); + it != uninterpreted_symbols[s].end(); it++) { + std::vector<CG_outputRepr *> reprs_ = it->second; + std::vector<CG_outputRepr *> reprs_2; + + for (int k = 0; k < reprs_.size(); k++) { + std::vector<CG_outputRepr *> subs2; + for (int l = 0; l < subs_.size(); l++) { + + subs2.push_back(subs_[l]->clone()); + } + CG_outputRepr * temp = + ocg->CreateSubstitutedStmt(0, reprs_[k]->clone(), + loop_vars, subs2, false); + + if (temp != NULL) + reprs_2.push_back(temp); + // reprs_2.push_back(subs_[k]->clone()); + + } + if(reprs_2.size() > 0) + it->second = reprs_2; + } + + //break; + } + } + +//--end + +#endif + + fprintf(stderr, "\n\n\n\nprintRepr recursing ??? return printRepr( ... )\n"); + return printRepr(1, ocg, stmts, aotf, uninterpreted_symbols, printString); + } + + + + std::string CG_result::printString( + std::vector<std::map<std::string, std::vector<CG_outputRepr *> > > uninterpreted_symbols) const { + + fprintf(stderr, "CG.cc line 164, CG_result::printString()\n"); + CG_stringBuilder ocg; + std::vector<CG_outputRepr *> stmts(codegen_->xforms_.size()); + + fprintf(stderr, "stmts.size() %d\n", stmts.size()); + for (int i = 0; i < stmts.size(); i++) + stmts[i] = new CG_stringRepr("s" + to_string(i)); + + CG_stringRepr *repr = static_cast<CG_stringRepr *>(printRepr(&ocg, + stmts, + uninterpreted_symbols, + true)); + + for (int i = 0; i < stmts.size(); i++) + delete stmts[i]; + + if (repr != NULL) { + std::string s = repr->GetString(); + //fprintf(stderr, "\nCG.cc L197 repr->GetString() = '%s'\n\n\n", s.c_str()); + delete repr; + return s; + } else + return std::string(); + } + + int CG_result::num_level() const { + return codegen_->num_level(); + } + + //----------------------------------------------------------------------------- + // Class: CG_split + //----------------------------------------------------------------------------- + + CG_result *CG_split::recompute(const BoolSet<> &parent_active, + const Relation &known, const Relation &restriction) { + active_ &= parent_active; + if (active_.empty()) { + delete this; + return NULL; + } + + + int i = 0; + while (i < restrictions_.size()) { + Relation new_restriction = Intersection(copy(restrictions_[i]), + copy(restriction)); + + new_restriction.simplify(2, 4); + //new_restriction.simplify(); + clauses_[i] = clauses_[i]->recompute(active_, copy(known), + new_restriction); + if (clauses_[i] == NULL) { + restrictions_.erase(restrictions_.begin() + i); + clauses_.erase(clauses_.begin() + i); + } else + i++; + } + + + if (restrictions_.size() == 0) { + delete this; + return NULL; + } else + return this; + } + + int CG_split::populateDepth() { + int max_depth = 0; + for (int i = 0; i < clauses_.size(); i++) { + int t = clauses_[i]->populateDepth(); + if (t > max_depth) + max_depth = t; + } + return max_depth; + } + + std::pair<CG_result *, Relation> CG_split::liftOverhead(int depth, + bool propagate_up) { + for (int i = 0; i < clauses_.size();) { + std::pair<CG_result *, Relation> result = clauses_[i]->liftOverhead( + depth, propagate_up); + if (result.first == NULL) + clauses_.erase(clauses_.begin() + i); + else { + clauses_[i] = result.first; + if (!result.second.is_obvious_tautology()) + return std::make_pair(this, result.second); + i++; + } + + } + + if (clauses_.size() == 0) { + delete this; + return std::make_pair(static_cast<CG_result *>(NULL), + Relation::True(num_level())); + } else + return std::make_pair(this, Relation::True(num_level())); + } + + Relation CG_split::hoistGuard() { + std::vector<Relation> guards; + for (int i = 0; i < clauses_.size(); i++) + guards.push_back(clauses_[i]->hoistGuard()); + + return SimpleHull(guards, true, true); + } + + void CG_split::removeGuard(const Relation &guard) { + for (int i = 0; i < clauses_.size(); i++) + clauses_[i]->removeGuard(guard); + } + + std::vector<CG_result *> CG_split::findNextLevel() const { + std::vector<CG_result *> result; + for (int i = 0; i < clauses_.size(); i++) { + CG_split *splt = dynamic_cast<CG_split *>(clauses_[i]); + if (splt != NULL) { + std::vector<CG_result *> t = splt->findNextLevel(); + result.insert(result.end(), t.begin(), t.end()); + } else + result.push_back(clauses_[i]); + } + + return result; + } + + + + + CG_outputRepr *CG_split::printRepr(int indent, + CG_outputBuilder *ocg, + const std::vector<CG_outputRepr *> &stmts, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::vector<std::map<std::string, std::vector<CG_outputRepr *> > > unin, + bool printString) const { + + fprintf(stderr, "CG_split::printRepr()\n"); + int numfly = assigned_on_the_fly.size(); + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + //for (int i=0; i<numfly; i++) { + // fprintf(stderr, "i %d\n", i); + // std::pair<CG_outputRepr *, int>p = assigned_on_the_fly[i]; + // CG_outputRepr *tr = NULL; + // if (p.first != NULL) tr = p.first->clone(); + // int val = p.second; + // fprintf(stderr, "0x%x %d\n", tr, val); + //} + + CG_outputRepr *stmtList = NULL; + std::vector<CG_result *> next_level = findNextLevel(); + + std::vector<CG_loop *> cur_loops; + for (int i = 0; i < next_level.size(); i++) { + CG_loop *lp = dynamic_cast<CG_loop *>(next_level[i]); + if (lp != NULL) { + cur_loops.push_back(lp); + } else { + stmtList = ocg->StmtListAppend(stmtList, + loop_print_repr(active_, + cur_loops, + 0, + cur_loops.size(), + Relation::True(num_level()), + NULL, + indent, + codegen_->remap_, + codegen_->xforms_, + ocg, + stmts, + assigned_on_the_fly, + unin)); + stmtList = ocg->StmtListAppend(stmtList, + next_level[i]->printRepr(indent, + ocg, + stmts, + assigned_on_the_fly, + unin, + printString)); + cur_loops.clear(); + } + } + + stmtList = ocg->StmtListAppend(stmtList, + loop_print_repr(active_, + cur_loops, + 0, + cur_loops.size(), + Relation::True(num_level()), + NULL, + indent, + codegen_->remap_, + codegen_->xforms_, + ocg, + stmts, + assigned_on_the_fly, + unin)); + return stmtList; + } + + CG_result *CG_split::clone() const { + //fprintf(stderr, "CG_split::clone()\n"); + std::vector<CG_result *> clauses(clauses_.size()); + for (int i = 0; i < clauses_.size(); i++) + clauses[i] = clauses_[i]->clone(); + return new CG_split(codegen_, active_, restrictions_, clauses); + } + + void CG_split::dump(int indent) const { + std::string prefix; + for (int i = 0; i < indent; i++) + prefix += " "; + std::cout << prefix << "SPLIT: " << active_ << std::endl; + for (int i = 0; i < restrictions_.size(); i++) { + std::cout << prefix << "restriction: "; + const_cast<CG_split *>(this)->restrictions_[i].print(); + clauses_[i]->dump(indent + 1); + } + + } + + //----------------------------------------------------------------------------- + // Class: CG_loop + //----------------------------------------------------------------------------- + + CG_result *CG_loop::recompute(const BoolSet<> &parent_active, + const Relation &known, const Relation &restriction) { + known_ = copy(known); + restriction_ = copy(restriction); + active_ &= parent_active; + + std::vector<Relation> Rs; + for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { + Relation r = Intersection(copy(restriction), + copy(codegen_->projected_IS_[level_ - 1][*i])); + + //r.simplify(2, 4); + r.simplify(); + if (!r.is_upper_bound_satisfiable()) { + active_.unset(*i); + continue; + } + Rs.push_back(copy(r)); + } + + if (active_.empty()) { + delete this; + return NULL; + } + + Relation hull = SimpleHull(Rs, true, true); + + //hull.simplify(2,4); + //Anand:Variables for inspector constraint check + bool has_insp = false; + bool found_insp = false; + + //Global_Var_ID global_insp; + //Argument_Tuple arg; + // check if actual loop is needed + std::pair<EQ_Handle, int> result = find_simplest_assignment(hull, + hull.set_var(level_)); + if (result.second < INT_MAX) { + needLoop_ = false; + + bounds_ = Relation(hull.n_set()); + F_Exists *f_exists = bounds_.add_and()->add_exists(); + F_And *f_root = f_exists->add_and(); + std::map<Variable_ID, Variable_ID> exists_mapping; + EQ_Handle h = f_root->add_EQ(); + for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); + switch (v->kind()) { + case Input_Var: + h.update_coef(bounds_.input_var(v->get_position()), + cvi.curr_coef()); + break; + case Wildcard_Var: { + Variable_ID v2 = replicate_floor_definition(hull, v, bounds_, + f_exists, f_root, exists_mapping); + h.update_coef(v2, cvi.curr_coef()); + break; + } + case Global_Var: { + Global_Var_ID g = v->get_global_var(); + Variable_ID v2; + if (g->arity() == 0) + v2 = bounds_.get_local(g); + else + v2 = bounds_.get_local(g, v->function_of()); + h.update_coef(v2, cvi.curr_coef()); + break; + } + default: + assert(false); + } + } + h.update_const(result.first.get_const()); + bounds_.simplify(); + } + // loop iterates more than once, extract bounds now + else { + fprintf(stderr, "loop iterates more than once, extract bounds now\n"); + needLoop_ = true; + + bounds_ = Relation(hull.n_set()); + F_Exists *f_exists = bounds_.add_and()->add_exists(); + F_And *f_root = f_exists->add_and(); + std::map<Variable_ID, Variable_ID> exists_mapping; + + Relation b = Gist(copy(hull), copy(known), 1); + bool has_unresolved_bound = false; + + std::set<Variable_ID> excluded_floor_vars; + excluded_floor_vars.insert(b.set_var(level_)); + for (GEQ_Iterator e(b.single_conjunct()->GEQs()); e; e++) + if ((*e).get_coef(b.set_var(level_)) != 0) { + bool is_bound = true; + for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) { + std::pair<bool, GEQ_Handle> result = find_floor_definition( + b, cvi.curr_var(), excluded_floor_vars); + if (!result.first) { + is_bound = false; + has_unresolved_bound = true; + //break; + } + + if (!is_bound) { + std::vector<std::pair<bool, GEQ_Handle> > result = + find_floor_definition_temp(b, cvi.curr_var(), + excluded_floor_vars); + + if (result.size() != 2) + break; + + has_unresolved_bound = false; + for (int i = 0; i < result.size(); i++) { + + GEQ_Handle h = f_root->add_GEQ(); + + for (Constr_Vars_Iter cvi(result[i].second); cvi; + cvi++) { + Variable_ID v = cvi.curr_var(); + switch (v->kind()) { + case Input_Var: + h.update_coef( + bounds_.input_var( + v->get_position()), + cvi.curr_coef()); + break; + case Wildcard_Var: { + Variable_ID v2; + + v2 = replicate_floor_definition(b, v, + bounds_, f_exists, f_root, + exists_mapping); + + h.update_coef(v2, cvi.curr_coef()); + break; + } + case Global_Var: { + Global_Var_ID g = v->get_global_var(); + Variable_ID v2; + if (g->arity() == 0) + v2 = bounds_.get_local(g); + else + v2 = bounds_.get_local(g, + v->function_of()); + h.update_coef(v2, cvi.curr_coef()); + break; + } + default: + assert(false); + } + } + h.update_const((result[i].second).get_const()); + } + break; + } + } + + if (!is_bound) + continue; + + GEQ_Handle h = f_root->add_GEQ(); + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); + switch (v->kind()) { + case Input_Var: + h.update_coef(bounds_.input_var(v->get_position()), + cvi.curr_coef()); + break; + case Wildcard_Var: { + Variable_ID v2 = replicate_floor_definition(b, v, + bounds_, f_exists, f_root, exists_mapping); + h.update_coef(v2, cvi.curr_coef()); + break; + } + case Global_Var: { + Global_Var_ID g = v->get_global_var(); + Variable_ID v2; + if (g->arity() == 0) + v2 = bounds_.get_local(g); + else + v2 = bounds_.get_local(g, v->function_of()); + h.update_coef(v2, cvi.curr_coef()); + break; + } + default: + assert(false); + } + } + h.update_const((*e).get_const()); + } + + if (has_unresolved_bound) { + b = Approximate(b); + b.simplify(2, 4); + //Simplification of Hull + hull = Approximate(hull); + hull.simplify(2, 4); + //end : Anand + for (GEQ_Iterator e(b.single_conjunct()->GEQs()); e; e++) + if ((*e).get_coef(b.set_var(level_)) != 0) + f_root->add_GEQ(*e); + } + bounds_.simplify(); + hull.simplify(2,4); + // Since current SimpleHull does not support max() upper bound or min() lower bound, + // we have to forcefully split the loop when hull approximation does not return any bound. + bool has_lb = false; + bool has_ub = false; + for (GEQ_Iterator e = bounds_.single_conjunct()->GEQs(); e; e++) { + if ((*e).get_coef(bounds_.set_var(level_)) > 0) + has_lb = true; + else if ((*e).get_coef(bounds_.set_var(level_)) < 0) + has_ub = true; + if (has_lb && has_ub) + break; + } + + if (!has_lb) { + for (int i = 0; i < Rs.size(); i++) { + Relation r = Approximate(copy(Rs[i])); + r.simplify(2, 4); + for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++) + if ((*e).get_coef(r.input_var(level_)) > 0) { + Relation r2 = Relation::True(num_level()); + r2.and_with_GEQ(*e); + r2.simplify(); + std::vector<Relation> restrictions(2); + restrictions[0] = Complement(copy(r2)); + restrictions[0].simplify(); + restrictions[1] = r2; + std::vector<CG_result *> clauses(2); + clauses[0] = this; + clauses[1] = this->clone(); + CG_result *cgr = new CG_split(codegen_, active_, + restrictions, clauses); + cgr = cgr->recompute(active_, copy(known), + copy(restriction)); + return cgr; + } + } + for (int i = 0; i < Rs.size(); i++) { + Relation r = Approximate(copy(Rs[i])); + r.simplify(2, 4); + for (EQ_Iterator e = r.single_conjunct()->EQs(); e; e++) + if ((*e).get_coef(r.input_var(level_)) != 0) { + Relation r2 = Relation::True(num_level()); + r2.and_with_GEQ(*e); + r2.simplify(); + std::vector<Relation> restrictions(2); + if ((*e).get_coef(r.input_var(level_)) > 0) { + restrictions[0] = Complement(copy(r2)); + restrictions[0].simplify(); + restrictions[1] = r2; + } else { + restrictions[0] = r2; + restrictions[1] = Complement(copy(r2)); + restrictions[1].simplify(); + } + std::vector<CG_result *> clauses(2); + clauses[0] = this; + clauses[1] = this->clone(); + CG_result *cgr = new CG_split(codegen_, active_, + restrictions, clauses); + cgr = cgr->recompute(active_, copy(known), + copy(restriction)); + return cgr; + } + } + } else if (!has_ub) { + for (int i = 0; i < Rs.size(); i++) { + Relation r = Approximate(copy(Rs[i])); + r.simplify(2, 4); + for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++) + if ((*e).get_coef(r.input_var(level_)) < 0) { + Relation r2 = Relation::True(num_level()); + r2.and_with_GEQ(*e); + r2.simplify(); + std::vector<Relation> restrictions(2); + restrictions[1] = Complement(copy(r2)); + restrictions[1].simplify(); + restrictions[0] = r2; + std::vector<CG_result *> clauses(2); + clauses[0] = this; + clauses[1] = this->clone(); + CG_result *cgr = new CG_split(codegen_, active_, + restrictions, clauses); + cgr = cgr->recompute(active_, copy(known), + copy(restriction)); + return cgr; + } + } + for (int i = 0; i < Rs.size(); i++) { + Relation r = Approximate(copy(Rs[i])); + r.simplify(2, 4); + for (EQ_Iterator e = r.single_conjunct()->EQs(); e; e++) + if ((*e).get_coef(r.input_var(level_)) != 0) { + Relation r2 = Relation::True(num_level()); + r2.and_with_GEQ(*e); + r2.simplify(); + std::vector<Relation> restrictions(2); + if ((*e).get_coef(r.input_var(level_)) > 0) { + restrictions[0] = Complement(copy(r2)); + restrictions[0].simplify(); + restrictions[1] = r2; + } else { + restrictions[0] = r2; + restrictions[1] = Complement(copy(r2)); + restrictions[1].simplify(); + } + std::vector<CG_result *> clauses(2); + clauses[0] = this; + clauses[1] = this->clone(); + CG_result *cgr = new CG_split(codegen_, active_, + restrictions, clauses); + cgr = cgr->recompute(active_, copy(known), + copy(restriction)); + return cgr; + } + } + } + + if (!has_lb && !has_ub) + throw codegen_error( + "can't find any bound at loop level " + to_string(level_)); + else if (!has_lb) + throw codegen_error( + "can't find lower bound at loop level " + + to_string(level_)); + else if (!has_ub) + throw codegen_error( + "can't find upper bound at loop level " + + to_string(level_)); + } + bounds_.copy_names(hull); + bounds_.setup_names(); + + // additional guard/stride condition extraction + if (needLoop_) { + Relation cur_known = Intersection(copy(bounds_), copy(known_)); + cur_known.simplify(); + hull = Gist(hull, copy(cur_known), 1); + + std::pair<EQ_Handle, Variable_ID> result = find_simplest_stride(hull, + hull.set_var(level_)); + if (result.second != NULL) + if (abs(result.first.get_coef(hull.set_var(level_))) == 1) { + F_Exists *f_exists = bounds_.and_with_and()->add_exists(); + F_And *f_root = f_exists->add_and(); + std::map<Variable_ID, Variable_ID> exists_mapping; + EQ_Handle h = f_root->add_EQ(); + for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); + switch (v->kind()) { + case Input_Var: + h.update_coef(bounds_.input_var(v->get_position()), + cvi.curr_coef()); + break; + case Wildcard_Var: { + Variable_ID v2; + if (v == result.second) + v2 = f_exists->declare(); + else + v2 = replicate_floor_definition(hull, v, bounds_, + f_exists, f_root, exists_mapping); + h.update_coef(v2, cvi.curr_coef()); + break; + } + case Global_Var: { + Global_Var_ID g = v->get_global_var(); + Variable_ID v2; + if (g->arity() == 0) + v2 = bounds_.get_local(g); + else + v2 = bounds_.get_local(g, v->function_of()); + h.update_coef(v2, cvi.curr_coef()); + break; + } + default: + assert(false); + } + } + h.update_const(result.first.get_const()); + } else { + // since gist is not powerful enough on modular constraints for now, + // make an educated guess + coef_t stride = abs(result.first.get_coef(result.second)) + / gcd(abs(result.first.get_coef(result.second)), + abs( + result.first.get_coef( + hull.set_var(level_)))); + + Relation r1(hull.n_inp()); + F_Exists *f_exists = r1.add_and()->add_exists(); + F_And *f_root = f_exists->add_and(); + std::map<Variable_ID, Variable_ID> exists_mapping; + EQ_Handle h = f_root->add_EQ(); + for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); + switch (v->kind()) { + case Input_Var: + h.update_coef(r1.input_var(v->get_position()), + cvi.curr_coef()); + break; + case Wildcard_Var: { + Variable_ID v2; + if (v == result.second) + v2 = f_exists->declare(); + else + v2 = replicate_floor_definition(hull, v, r1, + f_exists, f_root, exists_mapping); + h.update_coef(v2, cvi.curr_coef()); + break; + } + case Global_Var: { + Global_Var_ID g = v->get_global_var(); + Variable_ID v2; + if (g->arity() == 0) + v2 = r1.get_local(g); + else + v2 = r1.get_local(g, v->function_of()); + h.update_coef(v2, cvi.curr_coef()); + break; + } + default: + assert(false); + } + } + h.update_const(result.first.get_const()); + r1.simplify(); + + bool guess_success = false; + for (GEQ_Iterator e(bounds_.single_conjunct()->GEQs()); e; e++) + if ((*e).get_coef(bounds_.set_var(level_)) == 1) { + Relation r2(hull.n_inp()); + F_Exists *f_exists = r2.add_and()->add_exists(); + F_And *f_root = f_exists->add_and(); + std::map<Variable_ID, Variable_ID> exists_mapping; + EQ_Handle h = f_root->add_EQ(); + h.update_coef(f_exists->declare(), stride); + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); + switch (v->kind()) { + case Input_Var: + h.update_coef(r2.input_var(v->get_position()), + cvi.curr_coef()); + break; + case Wildcard_Var: { + Variable_ID v2 = replicate_floor_definition( + hull, v, r2, f_exists, f_root, + exists_mapping); + h.update_coef(v2, 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(false); + } + } + h.update_const((*e).get_const()); + r2.simplify(); + + if (Gist(copy(r1), + Intersection(copy(cur_known), copy(r2)), 1).is_obvious_tautology() + && Gist(copy(r2), + Intersection(copy(cur_known), copy(r1)), + 1).is_obvious_tautology()) { + bounds_ = Intersection(bounds_, r2); + bounds_.simplify(); + guess_success = true; + break; + } + } + + // this is really a stride with non-unit coefficient for this loop variable + if (!guess_success) { + // TODO: for stride ax = b mod n it might be beneficial to + // generate modular linear equation solver code for + // runtime to get the starting position in printRepr, + // and stride would be n/gcd(|a|,n), thus this stride + // can be put into bounds_ too. + } + + } + + hull = Project(hull, hull.set_var(level_)); + hull.simplify(2, 4); + guard_ = Gist(hull, Intersection(copy(bounds_), copy(known_)), 1); + } + // don't generate guard for non-actual loop, postpone it. otherwise + // redundant if-conditions might be generated since for-loop semantics + // includes implicit comparison checking. -- by chun 09/14/10 + else + guard_ = Relation::True(num_level()); + guard_.copy_names(bounds_); + guard_.setup_names(); + + //guard_.simplify(); + // recursively down the AST + Relation new_known = Intersection(copy(known), + Intersection(copy(bounds_), copy(guard_))); + //Anand: IF inspector present in equality and GEQ add the equality constraint to known + //So as to avoid unnecessary IF condition + new_known.simplify(2, 4); + Relation new_restriction = Intersection(copy(restriction), + Intersection(copy(bounds_), copy(guard_))); + new_restriction.simplify(2, 4); + body_ = body_->recompute(active_, new_known, new_restriction); + if (body_ == NULL) { + delete this; + return NULL; + } else + return this; + } + + int CG_loop::populateDepth() { + int depth = body_->populateDepth(); + if (needLoop_) + depth_ = depth + 1; + else + depth_ = depth; + return depth_; + } + + std::pair<CG_result *, Relation> CG_loop::liftOverhead(int depth, + bool propagate_up) { + if (depth_ > depth) { + assert(propagate_up == false); + std::pair<CG_result *, Relation> result = body_->liftOverhead(depth, + false); + body_ = result.first; + return std::make_pair(this, Relation::True(num_level())); + } else { // (depth_ <= depth) + if (propagate_up) { + Relation r = pick_one_guard(guard_, level_); + if (!r.is_obvious_tautology()) + return std::make_pair(this, r); + } + + std::pair<CG_result *, Relation> result; + if (propagate_up || needLoop_) + result = body_->liftOverhead(depth, true); + else + result = body_->liftOverhead(depth, false); + body_ = result.first; + if (result.second.is_obvious_tautology()) + return std::make_pair(this, result.second); + + // loop is an assignment, replace this loop variable in overhead condition + if (!needLoop_) { + result.second = Intersection(result.second, copy(bounds_)); + result.second = Project(result.second, + result.second.set_var(level_)); + result.second.simplify(2, 4); + } + + int max_level = 0; + bool has_wildcard = false; + bool direction = true; + for (EQ_Iterator e(result.second.single_conjunct()->EQs()); e; e++) + if ((*e).has_wildcards()) { + if (has_wildcard) + assert(false); + else + has_wildcard = true; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + if (cvi.curr_var()->kind() == Input_Var + && cvi.curr_var()->get_position() > max_level) + max_level = cvi.curr_var()->get_position(); + } else + assert(false); + + if (!has_wildcard) { + int num_simple_geq = 0; + for (GEQ_Iterator e(result.second.single_conjunct()->GEQs()); e; + e++) + if (!(*e).has_wildcards()) { + num_simple_geq++; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + if (cvi.curr_var()->kind() == Input_Var + && cvi.curr_var()->get_position() > max_level) { + max_level = cvi.curr_var()->get_position(); + direction = (cvi.curr_coef() < 0) ? true : false; + } + } else { + has_wildcard = true; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + if (cvi.curr_var()->kind() == Input_Var + && cvi.curr_var()->get_position() > max_level) { + max_level = cvi.curr_var()->get_position(); + } + } + assert( + (has_wildcard && num_simple_geq == 0) + || (!has_wildcard && num_simple_geq == 1)); + } + + // check if this is the top loop level for splitting for this overhead + if (!propagate_up || (has_wildcard && max_level == level_ - 1) + || (!has_wildcard && max_level == level_)) { + std::vector<Relation> restrictions(2); + std::vector<CG_result *> clauses(2); + int saved_num_level = num_level(); + if (has_wildcard || direction) { + restrictions[1] = Complement(copy(result.second)); + restrictions[1].simplify(); + clauses[1] = this->clone(); + restrictions[0] = result.second; + clauses[0] = this; + } else { + restrictions[0] = Complement(copy(result.second)); + restrictions[0].simplify(); + clauses[0] = this->clone(); + restrictions[1] = result.second; + clauses[1] = this; + } + CG_result *cgr = new CG_split(codegen_, active_, restrictions, + clauses); + CG_result *new_cgr = cgr->recompute(active_, copy(known_), + copy(restriction_)); + new_cgr->populateDepth(); + assert(new_cgr==cgr); + if (static_cast<CG_split *>(new_cgr)->clauses_.size() == 1) + // infinite recursion detected, bail out + return std::make_pair(new_cgr, Relation::True(saved_num_level)); + else + return cgr->liftOverhead(depth, propagate_up); + } else + return std::make_pair(this, result.second); + } + } + + + + Relation CG_loop::hoistGuard() { + + Relation r = body_->hoistGuard(); + + // TODO: should bookkeep catched contraints in loop output as enforced and check if anything missing + // if (!Gist(copy(b), copy(enforced)).is_obvious_tautology()) { + // fprintf(stderr, "need to generate extra guard inside the loop\n"); + // } + + if (!needLoop_) + r = Intersection(r, copy(bounds_)); + r = Project(r, r.set_var(level_)); + r = Gist(r, copy(known_), 1); + + Relation eliminate_existentials_r; + Relation eliminate_existentials_known; + + eliminate_existentials_r = copy(r); + if (!r.is_obvious_tautology()) { + eliminate_existentials_r = Approximate(copy(r)); + eliminate_existentials_r.simplify(2,4); + eliminate_existentials_known = Approximate(copy(known_)); + eliminate_existentials_known.simplify(2,4); + + eliminate_existentials_r = Gist(eliminate_existentials_r, + eliminate_existentials_known, 1); + } + + + if (!eliminate_existentials_r.is_obvious_tautology()) { + // if (!r.is_obvious_tautology()) { + body_->removeGuard(r); + guard_ = Intersection(guard_, copy(r)); + guard_.simplify(); + } + + return guard_; + } + + + + void CG_loop::removeGuard(const Relation &guard) { + known_ = Intersection(known_, copy(guard)); + known_.simplify(); + + guard_ = Gist(guard_, copy(known_), 1); + guard_.copy_names(known_); + guard_.setup_names(); + } + + + + + CG_outputRepr *CG_loop::printRepr(int indent, + CG_outputBuilder *ocg, + const std::vector<CG_outputRepr *> &stmts, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::vector<std::map<std::string, std::vector<CG_outputRepr *> > > unin, bool printString) const { + + fprintf(stderr, "CG_loop::printRepr() w assigned_on_the_fly gonna call printRepr with more arguments\n"); + //int numfly = assigned_on_the_fly.size(); + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + //for (int i=0; i<numfly; i++) { + // //fprintf(stderr, "i %d\n", i); + // std::pair<CG_outputRepr *, int>p = assigned_on_the_fly[i]; + // CG_outputRepr *tr = NULL; + // if (p.first != NULL) tr = p.first->clone(); + // int val = p.second; + // //fprintf(stderr, "0x%x %d\n", tr, val); + //} + + return printRepr(true, indent, ocg, stmts, assigned_on_the_fly, unin, printString); + } + + + + + + CG_outputRepr *CG_loop::printRepr(bool do_print_guard, + int indent, + CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::vector<std::map<std::string, std::vector<CG_outputRepr *> > > unin, bool printString) const { + fprintf(stderr, "\n*** CG.cc CG_loop printrepr with more arguments\n"); + + + // debugging output + int numfly = assigned_on_the_fly.size(); + fprintf(stderr, "assigned on the fly %d\n", numfly ); // Anand makes twice as many + for (int i=0; i<numfly; i++) { + //fprintf(stderr, "i %d\n", i); + std::pair<CG_outputRepr *, int>p = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + + //Anand: adding support for Replacing substituted variables within + //Uninterpreted function symbols or global variables with arity > 0 here + //--begin + std::vector<std::pair<CG_outputRepr *, int> > aotf = assigned_on_the_fly; + int stmt_num = -1; + for (int s = 0; s < active_.size(); s++) + if (active_.get(s)) + stmt_num = s; + + assert(stmt_num != -1); + + CG_outputRepr *guardRepr; + if (do_print_guard) + guardRepr = output_guard(ocg, guard_, aotf, unin[stmt_num]); + else + guardRepr = NULL; + + fprintf(stderr, "after guard assigned on the fly %d\n", numfly ); + for (int i=0; i<numfly; i++) { + //fprintf(stderr, "i %d\n", i); + std::pair<CG_outputRepr *, int>p = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + fprintf(stderr, "done flying\n"); + + Relation cur_known = Intersection(copy(known_), copy(guard_)); + + cur_known.simplify(); + fprintf(stderr, "checking needloop\n"); + if (needLoop_) { + fprintf(stderr, "needLoop_\n"); + + if (checkLoopLevel) + if (level_ == checkLoopLevel) + if (active_.get(stmtForLoopCheck)) + fillInBounds = true; + + fprintf(stderr, "ctrlRepr = output_loop()\n"); + CG_outputRepr *ctrlRepr = output_loop(ocg, bounds_, level_, cur_known, + aotf, unin[stmt_num]); + + fillInBounds = false; + + fprintf(stderr, "in needLoop_ bodyrepr = \n"); + int ind = (guardRepr == NULL) ? indent + 1 : indent + 2; + CG_outputRepr *bodyRepr = body_->printRepr(ind, + ocg, + stmts, + aotf, + unin, + printString); + CG_outputRepr * loopRepr; + + if (guardRepr == NULL) + loopRepr = ocg->CreateLoop(indent, ctrlRepr, bodyRepr); + else + loopRepr = ocg->CreateLoop(indent + 1, ctrlRepr, bodyRepr); + + + if (!smtNonSplitLevels.empty()) { + fprintf(stderr, "!smtNonSplitLevels.empty()\n"); + bool blockLoop = false; + bool threadLoop = false; + bool sync = false; + int firstActiveStmt = -1; + for (int s = 0; s < active_.size(); s++) { + if (active_.get(s)) { + if (firstActiveStmt < 0) + firstActiveStmt = s; + //We assume smtNonSplitLevels is only used to mark the first of + //the block or thread loops to be reduced in CUDA-CHiLL. Here we + //place some comments to help with final code generation. + //int idx = smtNonSplitLevels[s].index(level_); + + if (s < smtNonSplitLevels.size()) { + if (smtNonSplitLevels[s].size() > 0) + if (smtNonSplitLevels[s][0] == level_) { + blockLoop = true; + } + //Assume every stmt marked with a thread loop index also has a block loop idx + if (smtNonSplitLevels[s].size() > 1) + if (smtNonSplitLevels[s][1] == level_) { + threadLoop = true; + } + } + } + } + if (blockLoop && threadLoop) { + fprintf(stderr, + "Warning, have %d level more than once in smtNonSplitLevels\n", + level_); + threadLoop = false; + } + std::string preferredIdx; + + fprintf(stderr, "loopIdxNames.size() %d\n", loopIdxNames.size()); + for (int i=0; i<loopIdxNames.size(); i++) { + fprintf(stderr, "\n"); + for (int j=0; j<loopIdxNames[i].size(); j++) { + fprintf(stderr, "i %d j %d %s\n", i, j,loopIdxNames[i][j].c_str() ); + } + } + + fprintf(stderr, "firstActiveStmt %d\n", firstActiveStmt); + fprintf(stderr, "loopIdxNames[firstActiveStmt].size() %d\n", loopIdxNames[firstActiveStmt].size()); + fprintf(stderr, "level_ %d /2 %d\n", level_, level_/2); + + if (loopIdxNames.size() + && (level_ / 2) - 1 < loopIdxNames[firstActiveStmt].size()) { + + preferredIdx = loopIdxNames[firstActiveStmt][(level_ / 2) - 1]; + } + for (int s = 0; s < active_.size(); s++) { + if (active_.get(s)) { + for (int ii = 0; ii < syncs.size(); ii++) { + if (syncs[ii].first == s + && strcmp(syncs[ii].second.c_str(), + preferredIdx.c_str()) == 0) { + sync = true; + //printf("FOUND SYNC\n"); + } + + } + } + } + + if ( preferredIdx.length() != 0) { + fprintf(stderr, "CG.cc preferredIdx %s\n", preferredIdx.c_str()); + } + + if (threadLoop || blockLoop || preferredIdx.length() != 0) { + char buf[1024]; + std::string loop; + if (blockLoop) + loop = "blockLoop "; + if (threadLoop) + loop = "threadLoop "; + + if ( preferredIdx.length() != 0) { + fprintf(stderr, "CG.cc adding comment with preferredIdx %s\n", preferredIdx.c_str()); + } + + if (preferredIdx.length() != 0 && sync) { + sprintf(buf, "~cuda~ %spreferredIdx: %s sync", loop.c_str(), + preferredIdx.c_str()); + } else if (preferredIdx.length() != 0) { + sprintf(buf, "~cuda~ %spreferredIdx: %s", loop.c_str(), + preferredIdx.c_str()); + } else { + sprintf(buf, "~cuda~ %s", loop.c_str()); + } + + + loopRepr = ocg->CreateAttribute(loopRepr, buf); + } + + } + if (guardRepr == NULL) + return loopRepr; + else + return ocg->CreateIf(indent, guardRepr, loopRepr, NULL); + } + else { + fprintf(stderr, "NOT needloop_\n"); + + std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > result = + output_assignment(ocg, bounds_, level_, cur_known, aotf, unin[stmt_num]); + + //fprintf(stderr, "RESULT 0x%x 0x%x %d\n", result.first, result.second.first, result.second.second ); + + + guardRepr = ocg->CreateAnd(guardRepr, result.first); + //fprintf(stderr, "RESULT 0x%x 0x%x %d\n", result.first, result.second.first, result.second.second ); + + //fprintf(stderr, "after guardRepr assigned on the fly %d\n", numfly ); + for (int i=0; i<numfly; i++) { + //fprintf(stderr, "i %d\n", i); + std::pair<CG_outputRepr *, int>p = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + + + if (result.second.second < CodeGen::var_substitution_threshold) { + //fprintf(stderr, "var_substitution_threshold %d < %d level_ = %d\n", result.second.second, CodeGen::var_substitution_threshold, level_); + std::vector<std::pair<CG_outputRepr *, int> > aotf = + assigned_on_the_fly; + aotf[level_ - 1] = result.second; + //fprintf(stderr, "RESULT 0x%x second 0x%x %d\n", result.first, result.second.first, result.second.second ); + + if(!printString) { + for (std::map<std::string, std::vector<CG_outputRepr *> >::iterator i = + unin[stmt_num].begin(); i != unin[stmt_num].end(); i++) { + + + std::vector<CG_outputRepr *> to_push; + for (int j = 0; j < i->second.size(); j++) { + std::string index = + const_cast<CG_loop *>(this)->bounds_.set_var(level_)->name(); + std::vector<std::string> loop_vars; + loop_vars.push_back(index); + std::vector<CG_outputRepr *> subs; + subs.push_back(result.second.first->clone()); + CG_outputRepr * new_repr = ocg->CreateSubstitutedStmt(0, + i->second[j]->clone(), loop_vars, subs); + to_push.push_back(new_repr); + } + i->second = to_push; + } // for + } // if + + //fprintf(stderr, "aotf !!\n"); + for (int i=0; i<numfly; i++) { + //fprintf(stderr, "i %d\n", i); + std::pair<CG_outputRepr *, int>p = aotf[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) { tr = p.first->clone(); } + int val = p.second; + } + + //fprintf(stderr, "\nbodyRepr =\n"); + //body_->dump(); // this dies + int ind = (guardRepr == NULL) ? indent : indent + 1; + CG_outputRepr *bodyRepr = body_->printRepr(ind, ocg, stmts, aotf, unin, + printString); + + delete aotf[level_ - 1].first; + if (guardRepr == NULL) + return bodyRepr; + else + return ocg->CreateIf(indent, guardRepr, bodyRepr, NULL); + } else { + //fprintf(stderr, "NOT var_substitution_threshold gonna call output_ident()\n"); + int ind = (guardRepr == NULL) ? indent : indent + 1; + CG_outputRepr *assignRepr = ocg->CreateAssignment( + ind, + output_ident(ocg, bounds_, + const_cast<CG_loop *>(this)->bounds_.set_var( + level_), aotf, unin[stmt_num]), + result.second.first); + + CG_outputRepr *bodyRepr = body_->printRepr(ind, ocg, stmts, aotf, unin, + printString); + + if (guardRepr == NULL) + return ocg->StmtListAppend(assignRepr, bodyRepr); + else + return ocg->CreateIf(indent, guardRepr, + ocg->StmtListAppend(assignRepr, bodyRepr), NULL); + + /* DEAD CODE + std::pair<EQ_Handle, int> result_ = find_simplest_assignment( + copy(bounds_), copy(bounds_).set_var(level_), + assigned_on_the_fly); + bool found_func = false; + Variable_ID v2; + int arity; + for (Constr_Vars_Iter cvi(result_.first); cvi; cvi++) + if (cvi.curr_var()->kind() == Global_Var) { + Global_Var_ID g = cvi.curr_var()->get_global_var(); + if ((g->arity() > 0)) { + + found_func = true; + arity = g->arity(); + //copy(R).print(); + v2 = copy(bounds_).get_local(g, + cvi.curr_var()->function_of()); + + break; + } + } + + bool is_array = false; + if (found_func) { + + is_array = ocg->QueryInspectorType( + v2->get_global_var()->base_name()); + + } + if (!found_func || !is_array) { + + CG_outputRepr *assignRepr = ocg->CreateAssignment( + (guardRepr == NULL) ? indent : indent + 1, + output_ident(ocg, bounds_, + const_cast<CG_loop *>(this)->bounds_.set_var( + level_), assigned_on_the_fly), + result.second.first); + + CG_outputRepr *bodyRepr = body_->printRepr( + (guardRepr == NULL) ? indent : indent + 1, ocg, stmts, + assigned_on_the_fly); + if (guardRepr == NULL) + return ocg->StmtListAppend(assignRepr, bodyRepr); + else + return ocg->CreateIf(indent, guardRepr, + ocg->StmtListAppend(assignRepr, bodyRepr), NULL); + + } else { + + std::vector<CG_outputRepr *> index_expr; + + CG_outputRepr* lb = ocg->CreateArrayRefExpression( + v2->get_global_var()->base_name(), + output_ident(ocg, bounds_, + const_cast<CG_loop *>(this)->bounds_.set_var(2), + assigned_on_the_fly)); + + for (int i = arity; i > 1; i--) { + + index_expr.push_back( + ocg->CreateArrayRefExpression( + v2->get_global_var()->base_name(), + output_ident(ocg, bounds_, + const_cast<CG_loop *>(this)->bounds_.set_var( + 2 * i), + assigned_on_the_fly))); + + //} + + } + + CG_outputRepr *ub; + if (index_expr.size() > 1) + ub = ocg->CreateInvoke("max", index_expr); + else + ub = index_expr[0]; + CG_outputRepr *le = ocg->CreateMinus(ub, ocg->CreateInt(1)); + CG_outputRepr *inductive = ocg->CreateInductive( + output_ident(ocg, bounds_, + const_cast<CG_loop *>(this)->bounds_.set_var( + level_), assigned_on_the_fly), lb, le, + NULL); + + CG_outputRepr *bodyRepr = body_->printRepr( + (guardRepr == NULL) ? indent : indent + 1, ocg, stmts, + assigned_on_the_fly); + + if (guardRepr == NULL) { + return ocg->CreateLoop(indent, inductive, bodyRepr); + } else + return ocg->CreateIf(indent, guardRepr, + ocg->CreateLoop(indent + 1, inductive, bodyRepr), + NULL); + } + */ + } + } + } + + +/* +//Protonu--adding a helper function to get the ids of the nested loops +//to help with OpenMP code generation + std::vector<std::string> get_idxs( CG_result * cgl, std::vector<std::string>& idxs) + { + CG_loop * _lp; + CG_split *_sp; + + _lp = dynamic_cast<CG_loop *>(cgl); + _sp = dynamic_cast<CG_split *>(cgl); + + if(_lp){ + if (_lp->needLoop_) + idxs.push_back((copy(_lp->bounds_).set_var(_lp->level_))->name()); + if (_lp->depth() > 0 ){ + cgl = _lp->body_; + get_idxs(cgl, idxs); + } + if (_lp->depth() == 0) + return idxs; + } + if(_sp){ + for(int i=0; i<_sp->clauses_.size(); i++) + { + get_idxs(_sp->clauses_[i], idxs); + } + } + + return idxs; + + } +//end. +*/ + + + CG_result *CG_loop::clone() const { + //fprintf(stderr, "CG_loop::clone()\n"); + return new CG_loop(codegen_, active_, level_, body_->clone()); + } + + void CG_loop::dump(int indent) const { + std::string prefix; + for (int i = 0; i < indent; i++) + prefix += " "; + std::cout << prefix << "LOOP (level " << level_ << "): " << active_ + << std::endl; + std::cout << prefix << "known: "; + const_cast<CG_loop *>(this)->known_.print(); + std::cout << prefix << "restriction: "; + const_cast<CG_loop *>(this)->restriction_.print(); + std::cout << prefix << "bounds: "; + const_cast<CG_loop *>(this)->bounds_.print(); + std::cout << prefix << "guard: "; + const_cast<CG_loop *>(this)->guard_.print(); + body_->dump(indent + 1); + } + + //----------------------------------------------------------------------------- + // Class: CG_leaf + //----------------------------------------------------------------------------- + + CG_result* CG_leaf::recompute(const BoolSet<> &parent_active, + const Relation &known, const Relation &restriction) { + active_ &= parent_active; + known_ = copy(known); + + guards_.clear(); + for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { + Relation r = Intersection( + copy(codegen_->projected_IS_[num_level() - 1][*i]), + copy(restriction)); + r.simplify(2, 4); + if (!r.is_upper_bound_satisfiable()) + active_.unset(*i); + else { + r = Gist(r, copy(known), 1); + if (!r.is_obvious_tautology()) { + guards_[*i] = r; + guards_[*i].copy_names(known); + guards_[*i].setup_names(); + } + } + } + + + if (active_.empty()) { + delete this; + return NULL; + } else + return this; + } + + std::pair<CG_result *, Relation> CG_leaf::liftOverhead(int depth, bool) { + if (depth == 0) + return std::make_pair(this, Relation::True(num_level())); + + for (std::map<int, Relation>::iterator i = guards_.begin(); + i != guards_.end(); i++) { + Relation r = pick_one_guard(i->second); + if (!r.is_obvious_tautology()) { + bool has_wildcard = false; + int max_level = 0; + for (EQ_Iterator e(r.single_conjunct()->EQs()); e; e++) { + if ((*e).has_wildcards()) + has_wildcard = true; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + if (cvi.curr_var()->kind() == Input_Var + && cvi.curr_var()->get_position() > max_level) + max_level = cvi.curr_var()->get_position(); + } + for (GEQ_Iterator e(r.single_conjunct()->GEQs()); e; e++) { + if ((*e).has_wildcards()) + has_wildcard = true; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + if (cvi.curr_var()->kind() == Input_Var + && cvi.curr_var()->get_position() > max_level) + max_level = cvi.curr_var()->get_position(); + } + + if (!(has_wildcard && max_level == codegen_->num_level())) + return std::make_pair(this, r); + } + } + + return std::make_pair(this, Relation::True(num_level())); + } + + Relation CG_leaf::hoistGuard() { + std::vector<Relation> guards; + for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { + std::map<int, Relation>::iterator j = guards_.find(*i); + if (j == guards_.end()) { + Relation r = Relation::True(num_level()); + r.copy_names(known_); + r.setup_names(); + return r; + } else { + guards.push_back(j->second); + } + } + + return SimpleHull(guards, true, true); + } + + void CG_leaf::removeGuard(const Relation &guard) { + known_ = Intersection(known_, copy(guard)); + known_.simplify(); + + std::map<int, Relation>::iterator i = guards_.begin(); + while (i != guards_.end()) { + i->second = Gist(i->second, copy(known_), 1); + if (i->second.is_obvious_tautology()) + guards_.erase(i++); + else + ++i; + } + } + + CG_outputRepr *CG_leaf::printRepr(int indent, CG_outputBuilder *ocg, + const std::vector<CG_outputRepr *> &stmts, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::vector<std::map<std::string, std::vector<CG_outputRepr *> > > unin, + bool printString) const { + fprintf(stderr, "CG_leaf::printRepr()\n"); + int numfly = assigned_on_the_fly.size(); + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + for (int i=0; i<numfly; i++) { + //fprintf(stderr, "i %d\n", i); + std::pair<CG_outputRepr *, int>p = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + + return leaf_print_repr(active_, guards_, NULL, known_, indent, ocg, + codegen_->remap_, codegen_->xforms_, stmts, + assigned_on_the_fly, unin); + } + + + + CG_result *CG_leaf::clone() const { + //fprintf(stderr, "CG_leaf::clone()\n"); + return new CG_leaf(codegen_, active_); + } + + void CG_leaf::dump(int indent) const { + + std::string prefix; + for (int i = 0; i < indent; i++) + prefix += " "; + std::cout << prefix << "LEAF: " << active_ << std::endl; + std::cout << prefix << "known: "; + std::cout.flush(); + const_cast<CG_leaf *>(this)->known_.print(); + for (std::map<int, Relation>::const_iterator i = guards_.begin(); + i != guards_.end(); i++) { + std::cout << prefix << "guard #" << i->first << ":"; + const_cast<Relation &>(i->second).print(); + } + } + } diff --git a/lib/codegen/src/CG_stringBuilder.cc b/lib/codegen/src/CG_stringBuilder.cc index 2f9286f..d0f6693 100644..100755 --- a/lib/codegen/src/CG_stringBuilder.cc +++ b/lib/codegen/src/CG_stringBuilder.cc @@ -11,7 +11,7 @@ in other IR interface implementation. They are for debugging purpose. intMod implements modular function that returns positve remainder no matter lop is postive or nagative and rop is guranteed to be positive here. - + History: 04/17/96 - Lei Zhou - created 08/31/09 add parenthesis to string operands, Chun Chen @@ -26,462 +26,641 @@ #include <string.h> namespace { - -std::string SafeguardString(const std::string &s, char op) { - int len = s.length(); - int paren_level = 0; - int num_plusminus = 0; - int num_mul = 0; - int num_div = 0; - for (int i = 0; i < len; i++) - switch (s[i]) { - case '(': - paren_level++; - break; - case ')': - paren_level--; - break; - case '+': + + std::string SafeguardString(const std::string &s, char op) { + int len = s.length(); + int paren_level = 0; + int num_plusminus = 0; + int num_mul = 0; + int num_div = 0; + for (int i = 0; i < len; i++) + switch (s[i]) { + case '(': + paren_level++; + break; + case ')': + paren_level--; + break; + case '+': + case '-': + if (paren_level == 0) + num_plusminus++; + break; + case '*': + if (paren_level == 0) + num_mul++; + break; + case '/': + if (paren_level == 0) + num_div++; + break; + default: + break; + } + + bool need_paren = false; + switch (op) { case '-': - if (paren_level == 0) - num_plusminus++; + if (num_plusminus > 0) + need_paren = true; break; case '*': - if (paren_level == 0) - num_mul++; + if (num_plusminus > 0 || num_div > 0) + need_paren = true; break; case '/': - if (paren_level == 0) - num_div++; + if (num_plusminus > 0 || num_div > 0 || num_mul > 0) + need_paren = true; break; default: break; } - - bool need_paren = false; - switch (op) { - case '-': - if (num_plusminus > 0) - need_paren = true; - break; - case '*': - if (num_plusminus > 0 || num_div > 0) - need_paren = true; - break; - case '/': - if (num_plusminus > 0 || num_div > 0 || num_mul > 0) - need_paren = true; - break; - default: - break; + + if (need_paren) + return "(" + s + ")"; + else + return s; } - - if (need_paren) - return "(" + s + ")"; - else - return s; -} - - -std::string GetIndentSpaces(int indent) { - std::string indentStr; - for (int i = 1; i < indent; i++) { - indentStr += " "; + + + std::string GetIndentSpaces(int indent) { + std::string indentStr; + for (int i = 1; i < indent; i++) { + indentStr += " "; + } + return indentStr; } - return indentStr; -} - - -// A shortcut to extract the string enclosed in the CG_outputRepr and delete -// the original holder. -std::string GetString(omega::CG_outputRepr *repr) { - std::string result = static_cast<omega::CG_stringRepr *>(repr)->GetString(); - delete repr; - return result; -} - + + + // A shortcut to extract the string enclosed in the CG_outputRepr and delete + // the original holder. + std::string GetString(omega::CG_outputRepr *repr) { + std::string result = static_cast<omega::CG_stringRepr *>(repr)->GetString(); + delete repr; + return result; + } + } namespace omega { - - - -//----------------------------------------------------------------------------- -// Class: CG_stringBuilder -//----------------------------------------------------------------------------- - -CG_stringRepr *CG_stringBuilder::CreateSubstitutedStmt(int indent, CG_outputRepr *stmt, - const std::vector<std::string> &vars, - std::vector<CG_outputRepr *> &subs) const { - std::string listStr = ""; - - for (int i = 0; i < subs.size(); i++) { - if (subs[i] == NULL) - listStr += "N/A"; - else - listStr += GetString(subs[i]); - if (i < subs.size() - 1) - listStr += ","; - } - - std::string stmtName = GetString(stmt); - std::string indentStr = GetIndentSpaces(indent); - - return new CG_stringRepr(indentStr + stmtName + "(" + listStr + ");\n"); -} - -CG_stringRepr *CG_stringBuilder::CreateAssignment(int indent, - CG_outputRepr *lhs, - CG_outputRepr *rhs) const { - if (lhs == NULL || rhs == NULL) - throw std::invalid_argument("missing lhs or rhs in assignment"); - - std::string lhsStr = GetString(lhs); - std::string rhsStr = GetString(rhs); - - std::string indentStr = GetIndentSpaces(indent); - - return new CG_stringRepr(indentStr + lhsStr + "=" + rhsStr + ";\n"); -} - - -CG_stringRepr *CG_stringBuilder::CreateInvoke(const std::string &funcName, - std::vector<CG_outputRepr *> &list) const { - std::string listStr = ""; - - for (int i = 0; i < list.size(); i++) { - listStr += GetString(list[i]); - if ( i < list.size()-1) - listStr += ","; + + + + //----------------------------------------------------------------------------- + // Class: CG_stringBuilder + //----------------------------------------------------------------------------- + + CG_stringRepr *CG_stringBuilder::CreateSubstitutedStmt(int indent, + CG_outputRepr *stmt, + const std::vector<std::string> &vars, + std::vector<CG_outputRepr *> &subs, + bool actuallyPrint) const { + std::string listStr = ""; + + for (int i = 0; i < subs.size(); i++) { + if (subs[i] == NULL) + listStr += "N/A"; + else + listStr += GetString(subs[i]); + if (i < subs.size() - 1) + listStr += ","; + } + + std::string stmtName = GetString(stmt); + std::string indentStr = GetIndentSpaces(indent); + + return new CG_stringRepr(indentStr + stmtName + "(" + listStr + ");\n"); } - - return new CG_stringRepr(funcName + "(" + listStr + ")"); -} + + + CG_stringRepr *CG_stringBuilder::CreateStatementFromExpression(CG_outputRepr *exp) const { + std::string expStr = GetString(exp); + return new CG_stringRepr(expStr + ";\n"); + } + + CG_stringRepr *CG_stringBuilder::CreateAssignment(int indent, + CG_outputRepr *lhs, + CG_outputRepr *rhs) const { + if (lhs == NULL || rhs == NULL) + throw std::invalid_argument("missing lhs or rhs in assignment"); - -CG_stringRepr *CG_stringBuilder::CreateComment(int indent, const std::string &commentText) const { - if (commentText == std::string("")) { - return NULL; + std::string lhsStr = GetString(lhs); + std::string rhsStr = GetString(rhs); + + std::string indentStr = GetIndentSpaces(indent); + + return new CG_stringRepr(indentStr + lhsStr + "=" + rhsStr + ";\n"); } + + + CG_stringRepr *CG_stringBuilder::CreatePlusAssignment(int indent, + CG_outputRepr *lhs, + CG_outputRepr *rhs) const { + if (lhs == NULL || rhs == NULL) + throw std::invalid_argument("missing lhs or rhs in assignment"); + + std::string lhsStr = GetString(lhs); + std::string rhsStr = GetString(rhs); + + std::string indentStr = GetIndentSpaces(indent); + + return new CG_stringRepr(indentStr + lhsStr + "+=" + rhsStr + ";\n"); + } + + + + CG_stringRepr *CG_stringBuilder::CreateAddressOf(CG_outputRepr *op) const { + if (op == NULL) + throw std::invalid_argument("missining op in create address of"); + + std::string opStr = GetString(op); + + + return new CG_stringRepr( "&" + opStr); + } + + + CG_stringRepr *CG_stringBuilder::CreateInvoke(const std::string &funcName, + std::vector<CG_outputRepr *> &list, + bool is_array) const { + fprintf(stderr, "CG_stringBuilder::CreateInvoke( %s, ..., is_array ", funcName.c_str()); + if (is_array) fprintf(stderr, " true )\n"); + else fprintf(stderr, " false )\n"); - std::string indentStr = GetIndentSpaces(indent); - - return new CG_stringRepr(indentStr + "// " + commentText + "\n"); -} - -CG_stringRepr* CG_stringBuilder::CreateAttribute(CG_outputRepr *control, - const std::string &commentText) const { - if (commentText == std::string("")) { - return static_cast<CG_stringRepr *> (control); - } - std::string controlString = GetString(control); + std::string listStr = ""; + + fprintf(stderr, "list has %d elements\n", list.size()); - return new CG_stringRepr("// " + commentText + "\n" + controlString); + for (int i = 0; i < list.size(); i++) { + fprintf(stderr, "accessing list[%d]\n", i); + listStr += GetString(list[i]); + if ( i < list.size()-1) + listStr += ","; + } -} + fprintf(stderr, "returning %s\n", (funcName + "(" + listStr + ")").c_str()); + return new CG_stringRepr(funcName + "(" + listStr + ")"); + } + + + CG_stringRepr *CG_stringBuilder::CreateComment(int indent, const std::string &commentText) const { + if (commentText == std::string("")) { + return NULL; + } + + std::string indentStr = GetIndentSpaces(indent); + + return new CG_stringRepr(indentStr + "// " + commentText + "\n"); + } + -CG_outputRepr* CG_stringBuilder::CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const { - // -- Not Implemented - return scopeStmt; -} -CG_outputRepr* CG_stringBuilder::CreatePrefetchAttribute(CG_outputRepr* scopeStmt, int looplevel, const std::string& arrName, int hint) const { - // -- Not Implemented - return scopeStmt; -} + CG_stringRepr* CG_stringBuilder::CreateAttribute(CG_outputRepr *control, + const std::string &commentText) const { + + //fprintf(stderr, "CG_stringBuilder::CreateAttribute( jkadskjh, '%s')\n", commentText.c_str()); -CG_stringRepr *CG_stringBuilder::CreateIf(int indent, CG_outputRepr *guardList, - CG_outputRepr *true_stmtList, CG_outputRepr *false_stmtList) const { - if (guardList == NULL) - throw std::invalid_argument("missing if condition"); + if (commentText == std::string("")) { + return static_cast<CG_stringRepr *> (control); + } + + std::string controlString = GetString(control); + + std::string spaces = ""; + const char *con = controlString.c_str(); + const char *ptr = con; + while (*ptr++ == ' ') spaces = spaces + " "; + return new CG_stringRepr(spaces + "// " + commentText + "\n" + controlString); + + } - if (true_stmtList == NULL && false_stmtList == NULL) { - delete guardList; - return NULL; + CG_outputRepr* CG_stringBuilder::CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const { + // -- Not Implemented + return scopeStmt; } - - std::string guardListStr = GetString(guardList); - std::string indentStr = GetIndentSpaces(indent); - std::string s; - if (true_stmtList != NULL && false_stmtList == NULL) { - s = indentStr + "if (" + guardListStr + ") {\n" - + GetString(true_stmtList) - + indentStr + "}\n"; + + CG_outputRepr* CG_stringBuilder::CreatePrefetchAttribute(CG_outputRepr* scopeStmt, int looplevel, const std::string& arrName, int hint) const { + // -- Not Implemented + return scopeStmt; } - else if (true_stmtList == NULL && false_stmtList != NULL) { - s = indentStr + "if !(" + guardListStr + ") {\n" - + GetString(false_stmtList) - + indentStr + "}\n"; + + + + + CG_stringRepr *CG_stringBuilder::CreateBreakStatement(void) const { + std::string s= "break;\n"; + return new CG_stringRepr(s); + } + + + + CG_stringRepr *CG_stringBuilder::CreateIf(int indent, CG_outputRepr *guardList, + CG_outputRepr *true_stmtList, CG_outputRepr *false_stmtList) const { + if (guardList == NULL) + throw std::invalid_argument("missing if condition"); + + if (true_stmtList == NULL && false_stmtList == NULL) { + delete guardList; + return NULL; + } + + std::string guardListStr = GetString(guardList); + std::string indentStr = GetIndentSpaces(indent); + std::string s; + if (true_stmtList != NULL && false_stmtList == NULL) { + s = indentStr + "if (" + guardListStr + ") {\n" + + GetString(true_stmtList) + + indentStr + "}\n"; + } + else if (true_stmtList == NULL && false_stmtList != NULL) { + s = indentStr + "if !(" + guardListStr + ") {\n" + + GetString(false_stmtList) + + indentStr + "}\n"; + } + else { + s = indentStr + "if (" + guardListStr + ") {\n" + + GetString(true_stmtList) + + indentStr + "}\n" + + indentStr + "else {\n" + + GetString(false_stmtList) + + indentStr + "}\n"; + } + + return new CG_stringRepr(s); } - else { - s = indentStr + "if (" + guardListStr + ") {\n" - + GetString(true_stmtList) - + indentStr + "}\n" - + indentStr + "else {\n" - + GetString(false_stmtList) + + + + CG_stringRepr *CG_stringBuilder::CreateInductive(CG_outputRepr *index, + CG_outputRepr *lower, CG_outputRepr *upper, + CG_outputRepr *step) const { + if (index == NULL) + throw std::invalid_argument("missing loop index"); + if (lower == NULL) + throw std::invalid_argument("missing loop lower bound"); + if (upper == NULL) + throw std::invalid_argument("missing loop upper bound"); + //if (step == NULL) + // throw std::invalid_argument("missing loop step size"); + + std::string indexStr = GetString(index); + std::string lowerStr = GetString(lower); + std::string upperStr = GetString(upper); + + std::string doStr = "for(" + indexStr + " = " + lowerStr + "; " + + indexStr + " <= " + upperStr + "; " + + indexStr; + + if (step != NULL) { + std::string stepStr = GetString(step); + if (stepStr == to_string(1)) + doStr += "++"; + else + doStr += " += " + stepStr; + } + else + doStr += "++"; // a default ?? + doStr += ")"; + + return new CG_stringRepr(doStr); + } + + + CG_stringRepr *CG_stringBuilder::CreateLoop(int indent, CG_outputRepr *control, + CG_outputRepr *stmtList) const { + if (stmtList == NULL) { + delete control; + return NULL; + } + else if (control == NULL) + return static_cast<CG_stringRepr *>(stmtList); + + std::string ctrlStr = GetString(control); + std::string stmtStr = GetString(stmtList); + + std::string indentStr = GetIndentSpaces(indent); + + std::string s = indentStr + ctrlStr + " {\n" + + stmtStr + indentStr + "}\n"; + + return new CG_stringRepr(s); } - return new CG_stringRepr(s); -} - - - -CG_stringRepr *CG_stringBuilder::CreateInductive(CG_outputRepr *index, - CG_outputRepr *lower, CG_outputRepr *upper, - CG_outputRepr *step) const { - if (index == NULL) - throw std::invalid_argument("missing loop index"); - if (lower == NULL) - throw std::invalid_argument("missing loop lower bound"); - if (upper == NULL) - throw std::invalid_argument("missing loop upper bound"); - if (step == NULL) - throw std::invalid_argument("missing loop step size"); - - std::string indexStr = GetString(index); - std::string lowerStr = GetString(lower); - std::string upperStr = GetString(upper); - - std::string doStr = "for(" + indexStr + " = " + lowerStr + "; " - + indexStr + " <= " + upperStr + "; " - + indexStr; - - std::string stepStr = GetString(step); - if (stepStr == to_string(1)) - doStr += "++"; - else - doStr += " += " + stepStr; - - doStr += ")"; - - return new CG_stringRepr(doStr); -} - - -CG_stringRepr *CG_stringBuilder::CreateLoop(int indent, CG_outputRepr *control, - CG_outputRepr *stmtList) const { - if (stmtList == NULL) { - delete control; - return NULL; - } - else if (control == NULL) - return static_cast<CG_stringRepr *>(stmtList); - - std::string ctrlStr = GetString(control); - std::string stmtStr = GetString(stmtList); - - std::string indentStr = GetIndentSpaces(indent); - - std::string s = indentStr + ctrlStr + " {\n" - + stmtStr - + indentStr + "}\n"; - - return new CG_stringRepr(s); -} - - - -CG_stringRepr *CG_stringBuilder::CreateInt(int num) const { - std::string s = to_string(num); - return new CG_stringRepr(s); -} - - - -bool CG_stringBuilder::isInteger(CG_outputRepr *op) const { - - char * cstr; - std::string s = GetString(op); - cstr = new char [s.size()+1]; - strcpy (cstr, s.c_str()); - int count = 0; - while(cstr[count] != '\n' && cstr[count] != '\0' ) - if( !isdigit(cstr[count])) - return false; - - - return true; -} - - - -CG_stringRepr *CG_stringBuilder::CreateIdent(const std::string &varName) const { - if (varName == std::string("")) { - return NULL; + + + CG_stringRepr *CG_stringBuilder::CreateInt(int num) const { + std::string s = to_string(num); + return new CG_stringRepr(s); } - - return new CG_stringRepr(varName); -} - - -CG_stringRepr *CG_stringBuilder::CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) { - return static_cast<CG_stringRepr *>(lop); + + CG_stringRepr *CG_stringBuilder::CreateFloat(float num) const { + std::string s = to_string(num); + return new CG_stringRepr(s); } - else if (lop == NULL) { - return static_cast<CG_stringRepr *>(rop); + + CG_stringRepr *CG_stringBuilder::CreateDouble(double num) const { + std::string s = to_string(num); + return new CG_stringRepr(s); } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + "+" + ropStr); -} - - -CG_stringRepr *CG_stringBuilder::CreateMinus(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) { - return static_cast<CG_stringRepr *>(lop); + + + + bool CG_stringBuilder::isInteger(CG_outputRepr *op) const { + + char * cstr; + std::string s = GetString(op); + cstr = new char [s.size()+1]; + strcpy (cstr, s.c_str()); + int count = 0; + while(cstr[count] != '\n' && cstr[count] != '\0' ) + if( !isdigit(cstr[count])) + return false; + + + return true; + } + + bool CG_stringBuilder::QueryInspectorType(const std::string &varName) const{ + if (varName == std::string("index")) { // special cased? ?????? TODO + return true; + } + return false; + } + + CG_stringRepr* CG_stringBuilder::ObtainInspectorData(const std::string &_s, const std::string &member_name) const { + return new CG_stringRepr(_s); + } + + + + CG_stringRepr *CG_stringBuilder::CreateIdent(const std::string &varName) const { + if (varName == std::string("")) { + return NULL; + } + + return new CG_stringRepr(varName); + } + + + CG_stringRepr* CG_stringBuilder::CreateDotExpression(CG_outputRepr *lop, + CG_outputRepr *rop) const { + + std::string op1 = GetString(lop); + std::string op2 = GetString(rop); + + std::string s = op1 + "." + op2; + return new CG_stringRepr(s); + } + + + + CG_stringRepr* CG_stringBuilder::CreateNullStatement() const{ + return new CG_stringRepr(""); + } + + + + CG_stringRepr* CG_stringBuilder::CreateArrayRefExpression(const std::string &_s, + CG_outputRepr *rop) const { + if (_s == std::string("")) { + return NULL; + } + + std::string refStr = GetString(rop); + //std::string s = _s + "[" + refStr + "]"; + + return new CG_stringRepr( _s + "[" + refStr + "]"); } - else if (lop == NULL) { + + + + CG_stringRepr* CG_stringBuilder::CreateArrayRefExpression(CG_outputRepr *lop, + CG_outputRepr *rop) const { + + std::string refStr1 = GetString(lop); + std::string refStr2 = GetString(rop); + //std::string s = _s + "[" + refStr + "]"; + + return new CG_stringRepr( refStr1 + "[" + refStr2 + "]"); + + } + + + + CG_stringRepr *CG_stringBuilder::CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL) { + return static_cast<CG_stringRepr *>(lop); + } + else if (lop == NULL) { + return static_cast<CG_stringRepr *>(rop); + } + + std::string lopStr = GetString(lop); std::string ropStr = GetString(rop); - return new CG_stringRepr("-" + SafeguardString(ropStr, '-')); + + return new CG_stringRepr(lopStr + "+" + ropStr); } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + "-" + SafeguardString(ropStr, '-')); -} - - -CG_stringRepr *CG_stringBuilder::CreateTimes(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) { - delete rop; - delete lop; - return NULL; + + + CG_stringRepr *CG_stringBuilder::CreateMinus(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL) { + return static_cast<CG_stringRepr *>(lop); + } + else if (lop == NULL) { + std::string ropStr = GetString(rop); + return new CG_stringRepr("-" + SafeguardString(ropStr, '-')); + } + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr(lopStr + "-" + SafeguardString(ropStr, '-')); } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(SafeguardString(lopStr, '*') + "*" + SafeguardString(ropStr, '*')); -} - - -CG_stringRepr *CG_stringBuilder::CreateDivide(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) - throw codegen_error("integer division by zero"); - else if (lop == NULL) { - delete rop; - return NULL; + + + CG_stringRepr *CG_stringBuilder::CreateTimes(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL || lop == NULL) { + delete rop; + delete lop; + return NULL; + } + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr(SafeguardString(lopStr, '*') + "*" + SafeguardString(ropStr, '*')); } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(SafeguardString(lopStr, '/') + "/" + SafeguardString(ropStr, '/')); -} - - -CG_stringRepr *CG_stringBuilder::CreateIntegerFloor(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) - throw codegen_error("integer division by zero"); - else if (lop == NULL) { - delete rop; - return NULL; + + + CG_stringRepr *CG_stringBuilder::CreateDivide(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL) + throw codegen_error("integer division by zero"); + else if (lop == NULL) { + delete rop; + return NULL; + } + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr(SafeguardString(lopStr, '/') + "/" + SafeguardString(ropStr, '/')); } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr("intFloor(" + lopStr + "," + ropStr + ")"); -} - - -CG_stringRepr *CG_stringBuilder::CreateIntegerMod(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) - throw codegen_error("integer modulo by zero"); - else if (lop == NULL) { - delete rop; - return NULL; + + + CG_stringRepr *CG_stringBuilder::CreateIntegerFloor(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL) + throw codegen_error("integer division by zero"); + else if (lop == NULL) { + delete rop; + return NULL; + } + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr("intFloor(" + lopStr + "," + ropStr + ")"); } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr("intMod(" + lopStr + "," + ropStr + ")"); -} - -CG_stringRepr *CG_stringBuilder::CreateIntegerCeil(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == 0) - throw codegen_error("integer ceiling by zero"); - else if (lop == NULL) { - delete rop; - return NULL; + + + CG_stringRepr *CG_stringBuilder::CreateIntegerMod(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL) + throw codegen_error("integer modulo by zero"); + else if (lop == NULL) { + delete rop; + return NULL; + } + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr("intMod(" + lopStr + "," + ropStr + ")"); } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr("intCeil(" + lopStr + "," + ropStr + ")"); -} - - -CG_stringRepr *CG_stringBuilder::CreateAnd(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) - return static_cast<CG_stringRepr *>(lop); - else if (lop == NULL) - return static_cast<CG_stringRepr *>(rop); - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + " && " + ropStr); -} - - -CG_stringRepr *CG_stringBuilder::CreateGE(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) - throw std::invalid_argument("missing operand in greater than equal comparison condition"); - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + " >= " + ropStr); -} - - - -CG_stringRepr *CG_stringBuilder::CreateLE(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) - throw std::invalid_argument("missing operand in less than equal comparison condition"); - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + " <= " + ropStr); -} - - - -CG_stringRepr *CG_stringBuilder::CreateEQ(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) - throw std::invalid_argument("missing operand in equal comparison condition"); - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + " == " + ropStr); -} - - - -CG_stringRepr *CG_stringBuilder::StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const { - if (list2 == NULL) { - return static_cast<CG_stringRepr *>(list1); + + CG_stringRepr *CG_stringBuilder::CreateIntegerCeil(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == 0) + throw codegen_error("integer ceiling by zero"); + else if (lop == NULL) { + delete rop; + return NULL; + } + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr("intCeil(" + lopStr + "," + ropStr + ")"); + } + + + CG_stringRepr *CG_stringBuilder::CreateAnd(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL) + return static_cast<CG_stringRepr *>(lop); + else if (lop == NULL) + return static_cast<CG_stringRepr *>(rop); + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr(lopStr + " && " + ropStr); + } + + + CG_stringRepr *CG_stringBuilder::CreateGE(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL || lop == NULL) + throw std::invalid_argument("missing operand in greater than equal comparison condition"); + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr(lopStr + " >= " + ropStr); + } + + + + CG_stringRepr *CG_stringBuilder::CreateLE(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL || lop == NULL) + throw std::invalid_argument("missing operand in less than equal comparison condition"); + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr(lopStr + " <= " + ropStr); + } + + + + CG_stringRepr *CG_stringBuilder::CreateEQ(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL || lop == NULL) + throw std::invalid_argument("missing operand in equal comparison condition"); + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr(lopStr + " == " + ropStr); + } + + + CG_stringRepr *CG_stringBuilder::CreateNEQ(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL || lop == NULL) + throw std::invalid_argument("missing operand in equal comparison condition"); + + std::string lopStr = GetString(lop); + std::string ropStr = GetString(rop); + + return new CG_stringRepr(lopStr + " != " + ropStr); + } + + + + CG_stringRepr *CG_stringBuilder::StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const { + if (list2 == NULL) { + return static_cast<CG_stringRepr *>(list1); + } + else if (list1 == NULL) { + return static_cast<CG_stringRepr *>(list2); + } + + std::string list1Str = GetString(list1); + std::string list2Str = GetString(list2); + + return new CG_stringRepr(list1Str + list2Str); } - else if (list1 == NULL) { - return static_cast<CG_stringRepr *>(list2); + + CG_outputRepr *CG_stringBuilder::CreateStruct(const std::string struct_name, + std::vector<std::string> data_members, + std::vector<CG_outputRepr *> data_types) + { + fprintf(stderr, "CG_stringBuilder::CreateStruct( %s )\n", struct_name.c_str()); + fprintf(stderr, "that makes no sense\n"); + exit(0); + } + + CG_outputRepr *CG_stringBuilder::CreateClassInstance(std::string name , + CG_outputRepr *class_def){ + fprintf(stderr, "CG_stringBuilder::CreateClassInstance( %s )\n", name.c_str()); + exit(0); + + } + + CG_outputRepr *CG_stringBuilder::lookup_member_data(CG_outputRepr* scope, + std::string varName, + CG_outputRepr *instance) { + fprintf(stderr, "CG_stringBuilder::lookup_member_data( )\n"); + exit(0); + } + + CG_outputRepr* CG_stringBuilder::CreatePointer(std::string &name) const { + fprintf(stderr, "CG_chillBuilder::CreatePointer( %s )\n", name.c_str()); + exit(0); } - std::string list1Str = GetString(list1); - std::string list2Str = GetString(list2); + CG_outputRepr* CG_stringBuilder::ObtainInspectorRange(const std::string &_s, const std::string &_name) const { + fprintf(stderr, "CG_stringBuilder::ObtainInspectorRange(%s, %s )\n", _s.c_str(), _name.c_str()); + exit(0); + } - return new CG_stringRepr(list1Str + list2Str); -} + } diff --git a/lib/codegen/src/CG_stringRepr.cc b/lib/codegen/src/CG_stringRepr.cc new file mode 100755 index 0000000..f1a7cad --- /dev/null +++ b/lib/codegen/src/CG_stringRepr.cc @@ -0,0 +1,32 @@ +/***************************************************************************** + Copyright (C) 1994-2000 University of Maryland + Copyright (C) 2008 University of Southern California + Copyright (C) 2009 University of Utah + All Rights Reserved. + + Purpose: + omega holder for string implementation. + + Notes: + + History: + 04/17/96 - Lei Zhou - created +*****************************************************************************/ + + +#include <code_gen/CG_stringRepr.h> +#include <stdio.h> +#include <string.h> + +namespace omega { + + //----------------------------------------------------------------------------- + // Dump operations + //----------------------------------------------------------------------------- + void CG_stringRepr::Dump() const { dump(); } // TODO combine dump() and Dump() + + void CG_stringRepr::DumpToFile(FILE *fp) const { + fprintf(fp,"%s", s_.c_str()); + } + +} // namespace diff --git a/lib/codegen/src/CG_utils.cc b/lib/codegen/src/CG_utils.cc index d3a5f71..19bb6c9 100755 --- a/lib/codegen/src/CG_utils.cc +++ b/lib/codegen/src/CG_utils.cc @@ -7,7 +7,7 @@ Utility functions for processing CG tree. Notes: - + History: 07/19/07 when generating output variable substitutions for a mapping relation, map it to each output to get correct equality, -chun @@ -24,309 +24,456 @@ #include <stack> namespace omega { - -int checkLoopLevel; -int stmtForLoopCheck; -int upperBoundForLevel; -int lowerBoundForLevel; -bool fillInBounds; - + + int checkLoopLevel; + int stmtForLoopCheck; + int upperBoundForLevel; + int lowerBoundForLevel; + bool fillInBounds; + //trick to static init checkLoopLevel to 0 -class JunkStaticInit{ public: JunkStaticInit(){ checkLoopLevel=0; fillInBounds=false;} }; -static JunkStaticInit junkInitInstance__; - - - - -namespace { - -Relation find_best_guard(const Relation &R, const BoolSet<> &active, const std::map<int, Relation> &guards) { - std::pair<int, int> best_cost = std::make_pair(0, 0); - Relation best_cond = Relation::True(R.n_set()); + class JunkStaticInit{ + public: + JunkStaticInit(){ checkLoopLevel=0; fillInBounds=false;} + }; + static JunkStaticInit junkInitInstance__; - Relation r = copy(R); - int max_iter_count = 2*(r.single_conjunct()->n_EQs()) + r.single_conjunct()->n_GEQs(); - int iter_count = 0; - while (!r.is_obvious_tautology()) { - std::pair<int, int> cost = std::make_pair(0, 0); - Relation cond = pick_one_guard(r); - Relation complement_cond = Complement(copy(cond)); - complement_cond.simplify(); - for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) { - std::map<int, Relation>::const_iterator j = guards.find(*i); - if (j == guards.end()) - continue; - if (Must_Be_Subset(copy(j->second), copy(cond))) - cost.first++; - else if (Must_Be_Subset(copy(j->second), copy(complement_cond))) - cost.second++; - } - if (cost > best_cost) { - best_cost = cost; - best_cond = copy(cond); - } - r = Gist(r, cond, 1); - - if (iter_count > max_iter_count) - throw codegen_error("guard condition too complex to handle"); - - iter_count++; - } - - return best_cond; -} - - -Relation find_best_guard(const Relation &R, const std::vector<CG_loop *> &loops, int start, int end) { - std::pair<int, int> best_cost = std::make_pair(0, 0); - Relation best_cond = Relation::True(R.n_set()); - Relation r = copy(R); - int max_iter_count = 2*(r.single_conjunct()->n_EQs()) + r.single_conjunct()->n_GEQs(); - int iter_count = 0; - while (!r.is_obvious_tautology()) { - std::pair<int, int> cost = std::make_pair(0, 0); - Relation cond = pick_one_guard(r); - int i = start; - for ( ; i < end; i++) { - if (Must_Be_Subset(copy(loops[i]->guard_), copy(cond))) - cost.first++; - else - break; - } - Relation complement_cond = Complement(copy(cond)); - complement_cond.simplify(); - for (int j = i; j < end; j++) - if (Must_Be_Subset(copy(loops[j]->guard_), copy(complement_cond))) - cost.second++; - else - break; - - if (cost > best_cost) { - best_cost = cost; - best_cond = copy(cond); - } - r = Gist(r, cond, 1); - - if (iter_count > max_iter_count) - throw codegen_error("guard condition too complex to handle"); - - iter_count++; - } - - return best_cond; -} - -} - -bool bound_must_hit_stride(const GEQ_Handle &inequality, Variable_ID v, const EQ_Handle &stride_eq, Variable_ID wc, const Relation &bounds, const Relation &known) { - assert(inequality.get_coef(v) != 0 && abs(stride_eq.get_coef(v)) == 1 && wc->kind() == Wildcard_Var && abs(stride_eq.get_coef(wc)) > 1); - - // if bound expression uses floor operation, bail out for now - // TODO: in the future, handle this - if (abs(inequality.get_coef(v)) != 1) - return false; - coef_t stride = abs(stride_eq.get_coef(wc)); - Relation r1(known.n_set()); - F_Exists *f_exists1 = r1.add_and()->add_exists(); - F_And *f_root1 = f_exists1->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping1; - EQ_Handle h1 = f_root1->add_EQ(); - Relation r2(known.n_set()); - F_Exists *f_exists2 = r2.add_and()->add_exists(); - F_And *f_root2 = f_exists2->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping2; - EQ_Handle h2 = f_root2->add_EQ(); - for (Constr_Vars_Iter cvi(inequality); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h1.update_coef(r1.input_var(v->get_position()), cvi.curr_coef()); - h2.update_coef(r2.input_var(v->get_position()), cvi.curr_coef()); - break; - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v1, v2; - if (g->arity() == 0) { - v1 = r1.get_local(g); - v2 = r2.get_local(g); - } - else { - v1 = r1.get_local(g, v->function_of()); - v2 = r2.get_local(g, v->function_of()); + namespace { + + Relation find_best_guard(const Relation &R, const BoolSet<> &active, const std::map<int, Relation> &guards) { + std::pair<int, int> best_cost = std::make_pair(0, 0); + Relation best_cond = Relation::True(R.n_set()); + + Relation r = copy(R); + int max_iter_count = 2*(r.single_conjunct()->n_EQs()) + r.single_conjunct()->n_GEQs(); + int iter_count = 0; + while (!r.is_obvious_tautology()) { + std::pair<int, int> cost = std::make_pair(0, 0); + Relation cond = pick_one_guard(r); + Relation complement_cond = Complement(copy(cond)); + complement_cond.simplify(); + for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) { + std::map<int, Relation>::const_iterator j = guards.find(*i); + if (j == guards.end()) + continue; + if (Must_Be_Subset(copy(j->second), copy(cond))) + cost.first++; + else if (Must_Be_Subset(copy(j->second), copy(complement_cond))) + cost.second++; + } + if (cost > best_cost) { + best_cost = cost; + best_cond = copy(cond); + } + r = Gist(r, cond, 1); + + if (iter_count > max_iter_count) { + //Relation s = copy(R); + //s.simplify(2,4); + //return s; + throw codegen_error("guard condition too complex to handle"); + } + + iter_count++; } - h1.update_coef(v1, cvi.curr_coef()); - h2.update_coef(v2, cvi.curr_coef()); - break; - } - case Wildcard_Var: { - Variable_ID v1 = replicate_floor_definition(bounds, v, r1, f_exists1, f_root1, exists_mapping1); - Variable_ID v2 = replicate_floor_definition(bounds, v, r2, f_exists2, f_root2, exists_mapping2); - h1.update_coef(v1, cvi.curr_coef()); - h2.update_coef(v2, cvi.curr_coef()); - break; + + return best_cond; } - default: - assert(false); + + + Relation find_best_guard(const Relation &R, const std::vector<CG_loop *> &loops, int start, int end) { + std::pair<int, int> best_cost = std::make_pair(0, 0); + Relation best_cond = Relation::True(R.n_set()); + + Relation r = copy(R); + int max_iter_count = 2*(r.single_conjunct()->n_EQs()) + + r.single_conjunct()->n_GEQs(); + int iter_count = 0; + while (!r.is_obvious_tautology()) { + std::pair<int, int> cost = std::make_pair(0, 0); + + // was Relation cond = pick_one_guard(r); + Relation cond = pick_one_guard(r,loops[start]->level_); + int i = start; + for ( ; i < end; i++) { + if (Must_Be_Subset(copy(loops[i]->guard_), copy(cond))) + cost.first++; + else + break; + } + Relation complement_cond = Complement(copy(cond)); + complement_cond.simplify(); + for (int j = i; j < end; j++) + if (Must_Be_Subset(copy(loops[j]->guard_), copy(complement_cond))) + cost.second++; + else + break; + + if (cost > best_cost) { + best_cost = cost; + best_cond = copy(cond); + } + r = Gist(r, cond, 1); + + if (iter_count > max_iter_count) + throw codegen_error("guard condition too complex to handle"); + + iter_count++; + } + + return best_cond; } + } - h1.update_const(inequality.get_const()); - h1.update_coef(f_exists1->declare(), stride); - h2.update_const(inequality.get_const()); - r1.simplify(); - r2.simplify(); + - Relation all_known = Intersection(copy(bounds), copy(known)); - all_known.simplify(); - if (Gist(r1, copy(all_known), 1).is_obvious_tautology()) { - Relation r3(known.n_set()); - F_Exists *f_exists3 = r3.add_and()->add_exists(); - F_And *f_root3 = f_exists3->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping3; - EQ_Handle h3 = f_root3->add_EQ(); - for (Constr_Vars_Iter cvi(stride_eq); cvi; cvi++) { - Variable_ID v= cvi.curr_var(); + + bool bound_must_hit_stride(const GEQ_Handle &inequality, + Variable_ID v, + const EQ_Handle &stride_eq, + Variable_ID wc, + const Relation &bounds, + const Relation &known) { + assert(inequality.get_coef(v) != 0 + && abs(stride_eq.get_coef(v)) == 1 + && wc->kind() == Wildcard_Var + && abs(stride_eq.get_coef(wc)) > 1); + + // if bound expression uses floor operation, bail out for now + // TODO: in the future, handle this + if (abs(inequality.get_coef(v)) != 1) + return false; + + coef_t stride = abs(stride_eq.get_coef(wc)); + + Relation r1(known.n_set()); + F_Exists *f_exists1 = r1.add_and()->add_exists(); + F_And *f_root1 = f_exists1->add_and(); + std::map<Variable_ID, Variable_ID> exists_mapping1; + EQ_Handle h1 = f_root1->add_EQ(); + Relation r2(known.n_set()); + F_Exists *f_exists2 = r2.add_and()->add_exists(); + F_And *f_root2 = f_exists2->add_and(); + std::map<Variable_ID, Variable_ID> exists_mapping2; + EQ_Handle h2 = f_root2->add_EQ(); + for (Constr_Vars_Iter cvi(inequality); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); switch (v->kind()) { - case Input_Var: - h3.update_coef(r3.input_var(v->get_position()), cvi.curr_coef()); + case Input_Var: + h1.update_coef(r1.input_var(v->get_position()), cvi.curr_coef()); + h2.update_coef(r2.input_var(v->get_position()), cvi.curr_coef()); break; - case Global_Var: { + case Global_Var: { Global_Var_ID g = v->get_global_var(); - Variable_ID v3; - if (g->arity() == 0) - v3 = r3.get_local(g); - else - v3 = r3.get_local(g, v->function_of()); - h3.update_coef(v3, cvi.curr_coef()); - break; - } - case Wildcard_Var: - if (v == wc) - h3.update_coef(f_exists3->declare(), cvi.curr_coef()); + Variable_ID v1, v2; + if (g->arity() == 0) { + v1 = r1.get_local(g); + v2 = r2.get_local(g); + } else { - Variable_ID v3 = replicate_floor_definition(bounds, v, r3, f_exists3, f_root3, exists_mapping3); - h3.update_coef(v3, cvi.curr_coef()); + v1 = r1.get_local(g, v->function_of()); + v2 = r2.get_local(g, v->function_of()); } + h1.update_coef(v1, cvi.curr_coef()); + h2.update_coef(v2, cvi.curr_coef()); break; + } + case Wildcard_Var: { + Variable_ID v1 = replicate_floor_definition(bounds, + v, + r1, + f_exists1, + f_root1, + exists_mapping1); + Variable_ID v2 = replicate_floor_definition(bounds, + v, + r2, + f_exists2, + f_root2, + exists_mapping2); + h1.update_coef(v1, cvi.curr_coef()); + h2.update_coef(v2, cvi.curr_coef()); + break; + } default: assert(false); } } - h3.update_const(stride_eq.get_const()); - r3.simplify(); + h1.update_const(inequality.get_const()); + h1.update_coef(f_exists1->declare(), stride); + h2.update_const(inequality.get_const()); + r1.simplify(); + r2.simplify(); - if (Gist(r3, Intersection(r2, all_known), 1).is_obvious_tautology()) - return true; - else + Relation all_known = Intersection(copy(bounds), copy(known)); + all_known.simplify(); + + if (Gist(r1, copy(all_known), 1).is_obvious_tautology()) { + Relation r3(known.n_set()); + F_Exists *f_exists3 = r3.add_and()->add_exists(); + F_And *f_root3 = f_exists3->add_and(); + std::map<Variable_ID, Variable_ID> exists_mapping3; + EQ_Handle h3 = f_root3->add_EQ(); + for (Constr_Vars_Iter cvi(stride_eq); cvi; cvi++) { + Variable_ID v= cvi.curr_var(); + switch (v->kind()) { + case Input_Var: + h3.update_coef(r3.input_var(v->get_position()), cvi.curr_coef()); + break; + case Global_Var: { + Global_Var_ID g = v->get_global_var(); + Variable_ID v3; + if (g->arity() == 0) + v3 = r3.get_local(g); + else + v3 = r3.get_local(g, v->function_of()); + h3.update_coef(v3, cvi.curr_coef()); + break; + } + case Wildcard_Var: + if (v == wc) + h3.update_coef(f_exists3->declare(), cvi.curr_coef()); + else { + Variable_ID v3 = replicate_floor_definition(bounds, + v, + r3, + f_exists3, + f_root3, + exists_mapping3); + h3.update_coef(v3, cvi.curr_coef()); + } + break; + default: + assert(false); + } + } + h3.update_const(stride_eq.get_const()); + r3.simplify(); + + if (Gist(r3, Intersection(r2, all_known), 1).is_obvious_tautology()) + return true; + else + return false; + } + else { return false; + } } - else - return false; -} - - + + // // output variable by its name, however if this variable need to be substituted, // return the substitution. // -CG_outputRepr *output_ident(CG_outputBuilder *ocg, const Relation &R, Variable_ID v, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - const_cast<Relation &>(R).setup_names(); // hack - - if (v->kind() == Input_Var) { - int pos = v->get_position(); - if (assigned_on_the_fly[pos-1].first != NULL) - return assigned_on_the_fly[pos-1].first->clone(); - else - return ocg->CreateIdent(v->name()); - } - else if (v->kind() == 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(); - std::vector<CG_outputRepr *> argList; - for(int i = 1; i <= arity; i++) - argList.push_back(ocg->CreateIdent(const_cast<Relation &>(R).input_var(i)->name())); - CG_outputRepr *call = ocg->CreateInvoke(v->get_global_var()->base_name(), argList); - return call; + CG_outputRepr *output_ident(CG_outputBuilder *ocg, + const Relation &R, + Variable_ID v, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::map<std::string, std::vector<CG_outputRepr *> > unin) { + fprintf(stderr, "output_ident( %s )\n", v->name().c_str()); + + const_cast<Relation &>(R).setup_names(); // hack + + if (v->kind() == Input_Var) { + int pos = v->get_position(); + if (assigned_on_the_fly[pos - 1].first != NULL) { + //fprintf(stderr, "on the fly pos=%d\n", pos); + CG_outputRepr *tmp = assigned_on_the_fly[pos-1].first->clone(); + //fprintf(stderr, "tmp on the fly (0x%x)\n", tmp); + return tmp; + } + else { + //fprintf(stderr, "creating Ident for %s\n", v->name().c_str()); + CG_outputRepr *tmp = ocg->CreateIdent(v->name()); + //fprintf(stderr, "ident created for %s\n", v->name().c_str()); + return tmp; + } } + else if (v->kind() == Global_Var) { + //fprintf(stderr, "CG_utils.cc output_ident() Global_Var\n"); + if (v->get_global_var()->arity() == 0) { + //fprintf(stderr, "arity 0\n"); + 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(); + //fprintf(stderr, "arity %dn", arity ); + std::vector<CG_outputRepr *> argList; + if (unin.find(v->get_global_var()->base_name()) != unin.end()) { + + std::vector<CG_outputRepr *> argList_ = unin.find( + v->get_global_var()->base_name())->second; + + for (int l = 0; l < argList_.size(); l++) + argList.push_back(argList_[l]->clone()); + + } + else { + for (int i = 1; i <= arity; i++) { + + /* + */ + if (assigned_on_the_fly.size() > (R.n_inp() + i - 1)) { + if (assigned_on_the_fly[R.n_inp() + i - 1].first != NULL) + argList.push_back( + assigned_on_the_fly[R.n_inp() + i - 1].first->clone()); + else + argList.push_back( + ocg->CreateIdent( + const_cast<Relation &>(R).input_var( + 2 * i)->name())); + } else + argList.push_back( + ocg->CreateIdent( + const_cast<Relation &>(R).input_var( + 2 * i)->name())); + + /*if (assigned_on_the_fly[2*i - 1].first == NULL) + argList.push_back( + ocg->CreateIdent( + const_cast<Relation &>(R).input_var(2 * i)->name())); + else + argList.push_back(assigned_on_the_fly[2*i - 1].first->clone()); + */ + } + } + CG_outputRepr *call = ocg->CreateInvoke( + v->get_global_var()->base_name(), argList); + return call; + } + } + else + assert(false); } - else - assert(false); -} - + + // // return pair<if condition, <assignment rhs, assignment cost> > // -std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > output_assignment(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - Variable_ID v = const_cast<Relation &>(R).set_var(level); - Conjunct *c = const_cast<Relation &>(R).single_conjunct(); - - std::pair<EQ_Handle, int> result = find_simplest_assignment(R, v, assigned_on_the_fly); - - if (result.second == INT_MAX) - return std::make_pair(static_cast<CG_outputRepr *>(NULL), std::make_pair(static_cast<CG_outputRepr *>(NULL), INT_MAX)); - - CG_outputRepr *if_repr = NULL; - CG_outputRepr *assign_repr = NULL; - // check whether to generate if-conditions from equality constraints - if (abs(result.first.get_coef(v)) != 1) { - Relation r(R.n_set()); - F_Exists *f_exists = r.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - exists_mapping[v] = f_exists->declare(); - - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Input_Var: { - if (cvi.curr_var() == v) - h.update_coef(exists_mapping[v], cvi.curr_coef()); - else - h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = cvi.curr_var()->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r.get_local(g); - else - v2 = r.get_local(g, cvi.curr_var()->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var()); - Variable_ID v2; - if (p == exists_mapping.end()) { - v2 = f_exists->declare(); - exists_mapping[cvi.curr_var()] = v2; + std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > output_assignment( + CG_outputBuilder *ocg, const Relation &R, int level, + const Relation &known, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::map<std::string, std::vector<CG_outputRepr *> > unin) { + + //fprintf(stderr, "output_assignment( )\n"); + int numfly = assigned_on_the_fly.size(); + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + for (int i=0; i<numfly; i++) { + //fprintf(stderr, "i %d\n", i); + std::pair<CG_outputRepr *, int>p = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + + + Variable_ID v = const_cast<Relation &>(R).set_var(level); + Conjunct *c = const_cast<Relation &>(R).single_conjunct(); + + std::pair<EQ_Handle, int> result = find_simplest_assignment(R, v, assigned_on_the_fly); + + if (result.second == INT_MAX) + return std::make_pair(static_cast<CG_outputRepr *>(NULL), std::make_pair(static_cast<CG_outputRepr *>(NULL), INT_MAX)); + + CG_outputRepr *if_repr = NULL; + CG_outputRepr *assign_repr = NULL; + // check whether to generate if-conditions from equality constraints + if (abs(result.first.get_coef(v)) != 1) { + Relation r(R.n_set()); + F_Exists *f_exists = r.add_and()->add_exists(); + F_And *f_root = f_exists->add_and(); + std::map<Variable_ID, Variable_ID> exists_mapping; + exists_mapping[v] = f_exists->declare(); + + EQ_Handle h = f_root->add_EQ(); + for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) + switch (cvi.curr_var()->kind()) { + case Input_Var: { + if (cvi.curr_var() == v) + h.update_coef(exists_mapping[v], cvi.curr_coef()); + else + h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef()); + break; } - else - v2 = p->second; - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(0); - } - h.update_const(result.first.get_const()); + case Global_Var: { + Global_Var_ID g = cvi.curr_var()->get_global_var(); + Variable_ID v2; + if (g->arity() == 0) + v2 = r.get_local(g); + else + v2 = r.get_local(g, cvi.curr_var()->function_of()); + h.update_coef(v2, cvi.curr_coef()); + break; + } + case Wildcard_Var: { + std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var()); + Variable_ID v2; + if (p == exists_mapping.end()) { + v2 = f_exists->declare(); + exists_mapping[cvi.curr_var()] = v2; + } + else + v2 = p->second; + h.update_coef(v2, cvi.curr_coef()); + break; + } + default: + assert(0); + } + h.update_const(result.first.get_const()); - for (EQ_Iterator e(c->EQs()); e; e++) - if (!((*e) == result.first)) { - EQ_Handle h = f_root->add_EQ(); + for (EQ_Iterator e(c->EQs()); e; e++) + if (!((*e) == result.first)) { + EQ_Handle h = f_root->add_EQ(); + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + switch (cvi.curr_var()->kind()) { + case Input_Var: { + assert(cvi.curr_var() != v); + h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef()); + break; + } + case Global_Var: { + Global_Var_ID g = cvi.curr_var()->get_global_var(); + Variable_ID v2; + if (g->arity() == 0) + v2 = r.get_local(g); + else + v2 = r.get_local(g, cvi.curr_var()->function_of()); + h.update_coef(v2, cvi.curr_coef()); + break; + } + case Wildcard_Var: { + std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var()); + Variable_ID v2; + if (p == exists_mapping.end()) { + v2 = f_exists->declare(); + exists_mapping[cvi.curr_var()] = v2; + } + else + v2 = p->second; + h.update_coef(v2, cvi.curr_coef()); + break; + } + default: + assert(0); + } + h.update_const((*e).get_const()); + } + + for (GEQ_Iterator e(c->GEQs()); e; e++) { + GEQ_Handle h = f_root->add_GEQ(); for (Constr_Vars_Iter cvi(*e); cvi; cvi++) switch (cvi.curr_var()->kind()) { case Input_Var: { - assert(cvi.curr_var() != v); h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef()); break; } @@ -357,1379 +504,2303 @@ std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > output_assignment(C } h.update_const((*e).get_const()); } - - for (GEQ_Iterator e(c->GEQs()); e; e++) { - GEQ_Handle h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Input_Var: { - h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = cvi.curr_var()->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r.get_local(g); - else - v2 = r.get_local(g, cvi.curr_var()->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var()); - Variable_ID v2; - if (p == exists_mapping.end()) { - v2 = f_exists->declare(); - exists_mapping[cvi.curr_var()] = v2; - } - else - v2 = p->second; - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(0); - } - h.update_const((*e).get_const()); - } - r.simplify(); - if (!Gist(r, copy(known), 1).is_obvious_tautology()) { - CG_outputRepr *lhs = output_substitution_repr(ocg, result.first, v, false, R, assigned_on_the_fly); - if_repr = ocg->CreateEQ(ocg->CreateIntegerMod(lhs->clone(), ocg->CreateInt(abs(result.first.get_coef(v)))), ocg->CreateInt(0)); - assign_repr = ocg->CreateDivide(lhs, ocg->CreateInt(abs(result.first.get_coef(v)))); + r.simplify(); + if (!Gist(r, copy(known), 1).is_obvious_tautology()) { + CG_outputRepr *lhs = output_substitution_repr(ocg, result.first, v, + false, R, assigned_on_the_fly, unin); + if_repr = ocg->CreateEQ(ocg->CreateIntegerMod(lhs->clone(), + ocg->CreateInt(abs(result.first.get_coef(v)))), + ocg->CreateInt(0)); + assign_repr = ocg->CreateDivide(lhs, ocg->CreateInt(abs(result.first.get_coef(v)))); + } + else { + assign_repr = output_substitution_repr(ocg, result.first, v, true, R, + assigned_on_the_fly, unin); + } } - else - assign_repr = output_substitution_repr(ocg, result.first, v, true, R, assigned_on_the_fly); + else { + assign_repr = output_substitution_repr(ocg, result.first, v, true, R, + assigned_on_the_fly, unin); + } + + if (assign_repr == NULL) { + assign_repr = ocg->CreateInt(0); + } + + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + //for (int i=0; i<numfly; i++) { + // //fprintf(stderr, "i %d\n", i); + // std::pair<CG_outputRepr *, int>p = assigned_on_the_fly[i]; + // CG_outputRepr *tr = NULL; + // if (p.first != NULL) tr = p.first->clone(); + // int val = p.second; + // //fprintf(stderr, "0x%x %d\n", tr, val); + //} + + return std::make_pair(if_repr, std::make_pair(assign_repr, result.second)); } - else - assign_repr = output_substitution_repr(ocg, result.first, v, true, R, assigned_on_the_fly); - - if (assign_repr == NULL) - assign_repr = ocg->CreateInt(0); + - return std::make_pair(if_repr, std::make_pair(assign_repr, result.second)); -} - - // // return NULL if 0 // -CG_outputRepr *output_substitution_repr(CG_outputBuilder *ocg, const EQ_Handle &equality, Variable_ID v, bool apply_v_coef, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - const_cast<Relation &>(R).setup_names(); // hack - - coef_t a = equality.get_coef(v); - assert(a != 0); - - CG_outputRepr *repr = NULL; - for (Constr_Vars_Iter cvi(equality); cvi; cvi++) - if (cvi.curr_var() != v) { - CG_outputRepr *t; - if (cvi.curr_var()->kind() == Wildcard_Var) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var()); - if (!result.first) { - delete repr; - throw codegen_error("can't output non floor defined wildcard"); + CG_outputRepr *output_substitution_repr(CG_outputBuilder *ocg, + const EQ_Handle &equality, + Variable_ID v, + bool apply_v_coef, + const Relation &R, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::map<std::string, std::vector<CG_outputRepr *> > unin) { + //fprintf(stderr, "output_substitution_repr( v = '%s' )\n", v->char_name()); + const_cast<Relation &>(R).setup_names(); // hack + + coef_t a = equality.get_coef(v); + assert(a != 0); + + CG_outputRepr *repr = NULL; + for (Constr_Vars_Iter cvi(equality); cvi; cvi++) + if (cvi.curr_var() != v) { + //fprintf(stderr, "cvi\n"); + CG_outputRepr *t; + if (cvi.curr_var()->kind() == Wildcard_Var) { + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var()); + if (!result.first) { + delete repr; + throw codegen_error("can't output non floor defined wildcard"); + } + t = output_inequality_repr(ocg, result.second, cvi.curr_var(), R, assigned_on_the_fly, unin); } - t = output_inequality_repr(ocg, result.second, cvi.curr_var(), R, assigned_on_the_fly); - } - else - t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - - if (a > 0) { - if (coef > 0) { - if (coef == 1) - repr = ocg->CreateMinus(repr, t); - else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); + else { + //fprintf(stderr, "else t = output_ident()\n"); + t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly, unin); + //if (t== NULL) fprintf(stderr, "t NULL\n"); } - else { // coef < 0 - if (coef == -1) - repr = ocg->CreatePlus(repr, t); - else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); - } - } - else { - if (coef > 0) { - if (coef == 1) - repr = ocg->CreatePlus(repr, t); - else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); + coef_t coef = cvi.curr_coef(); + //fprintf(stderr, "coef %d\n", coef); + + //fprintf(stderr, "a %d\n", a); + if (a > 0) { + if (coef > 0) { + if (coef == 1) + repr = ocg->CreateMinus(repr, t); + else + repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); + } + else { // coef < 0 + if (coef == -1) { + //fprintf(stderr, "repr = ocg->CreatePlus(repr, t);\n"); + repr = ocg->CreatePlus(repr, t); + //if (repr == NULL) fprintf(stderr, "repr NULL\n"); + //else fprintf(stderr, "repr NOT NULL\n"); + } + else { + repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); + } + } + } + else { + if (coef > 0) { + if (coef == 1) + repr = ocg->CreatePlus(repr, t); + else + repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); + } + else { // coef < 0 + if (coef == -1) + repr = ocg->CreateMinus(repr, t); + else + repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); + } } - else { // coef < 0 - if (coef == -1) - repr = ocg->CreateMinus(repr, t); - else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); - } + } + + //if (repr == NULL) fprintf(stderr, "before inequality, repr == NULL\n"); + int c = equality.get_const(); + if (a > 0) { + if (c > 0) + repr = ocg->CreateMinus(repr, ocg->CreateInt(c)); + else if (c < 0) + repr = ocg->CreatePlus(repr, ocg->CreateInt(-c)); + } + else { + if (c > 0) { + repr = ocg->CreatePlus(repr, ocg->CreateInt(c)); + } + else if (c < 0) { + repr = ocg->CreateMinus(repr, ocg->CreateInt(-c)); } } - - int c = equality.get_const(); - if (a > 0) { - if (c > 0) - repr = ocg->CreateMinus(repr, ocg->CreateInt(c)); - else if (c < 0) - repr = ocg->CreatePlus(repr, ocg->CreateInt(-c)); - } - else { - if (c > 0) - repr = ocg->CreatePlus(repr, ocg->CreateInt(c)); - else if (c < 0) - repr = ocg->CreateMinus(repr, ocg->CreateInt(-c)); - } - if (apply_v_coef && abs(a) != 1) - repr = ocg->CreateDivide(repr, ocg->CreateInt(abs(a))); - - return repr; -} - - + if (apply_v_coef && abs(a) != 1) + repr = ocg->CreateDivide(repr, ocg->CreateInt(abs(a))); + + //if (repr == NULL) fprintf(stderr, "at end, repr == NULL\n"); + //fprintf(stderr, "leaving output_substitution_repr()\n"); + return repr; + } + + // // original Substitutions class from omega can't handle integer // division, this is new way. // -std::vector<CG_outputRepr*> output_substitutions(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - std::vector<CG_outputRepr *> subs; - - for (int i = 1; i <= R.n_out(); i++) { - Relation mapping(R.n_out(), 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 r = Composition(mapping, copy(R)); - r.simplify(); - - Variable_ID v = r.output_var(1); - CG_outputRepr *repr = NULL; - std::pair<EQ_Handle, int> result = find_simplest_assignment(r, v, assigned_on_the_fly); - if (result.second < INT_MAX) - repr = output_substitution_repr(ocg, result.first, v, true, r, assigned_on_the_fly); - else { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v); - if (result.first) - try { - repr = output_inequality_repr(ocg, result.second, v, R, assigned_on_the_fly); - } - catch (const codegen_error &) { - } + std::vector<CG_outputRepr*> output_substitutions(CG_outputBuilder *ocg, + const Relation &R, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::map<std::string, std::vector<CG_outputRepr *> > unin) { + std::vector<CG_outputRepr *> subs; + + fprintf(stderr, "CG_utils.cc output_substitutions()\n"); + + for (int i = 1; i <= R.n_out(); i++) { + Relation mapping(R.n_out(), 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 r = Composition(mapping, copy(R)); + r.simplify(); + + Variable_ID v = r.output_var(1); + CG_outputRepr *repr = NULL; + + fprintf(stderr, "v %s\n", v->char_name()); + std::pair<EQ_Handle, int> result = find_simplest_assignment(r, v, assigned_on_the_fly); + if (result.second < INT_MAX) { + //fprintf(stderr, "output_substitutions() calling output_substitution_repr()\n"); + repr = output_substitution_repr(ocg, result.first, v, true, r, + assigned_on_the_fly, unin); + if (repr == NULL) fprintf(stderr, "IN IF, repr for %s assigned NULL\n", v->char_name()); + } + else { + //fprintf(stderr, "else\n"); + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v); + if (result.first) + try { + repr = output_inequality_repr(ocg, result.second, v, R, + assigned_on_the_fly, unin); + } + catch (const codegen_error &) { + } + } + + if (repr == NULL) fprintf(stderr, "repr NULL\n"); + if (repr != NULL) { + subs.push_back(repr); + } + else { + //Anand:Add additional checks for variables that have been mapped to inspector/global variables + for (int k = 1; k <= R.n_out(); k++) { + //Relation mapping1(mapping.n_out(), 1); + //F_And *f_root = mapping1.add_and(); + //EQ_Handle h = f_root->add_EQ(); + //h.update_coef(mapping1.output_var(1), 1); + //h.update_coef(mapping1.input_var(i), -1); + //Relation r = Composition(mapping1, copy(mapping)); + //r.simplify(); + + Relation r = copy(R); + + Variable_ID v = r.output_var(k); + CG_outputRepr* inspector = NULL; + bool has_insp = false; + Global_Var_ID global_insp; + + std::pair<EQ_Handle, int> result = find_simplest_assignment( + copy(r), v, assigned_on_the_fly); + CG_outputRepr *repr_ = NULL; + if (result.second < INT_MAX) { + /*std::vector<Variable_ID> variables; + //Anand: commenting this out as well : 05/29/2013 + variables.push_back(r.input_var(2 * k)); + for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { + Variable_ID v1 = cvi.curr_var(); + if (v1->kind() == Input_Var) + variables.push_back(v1); + + } + */ + repr_ = output_substitution_repr(ocg, result.first, v, true, + copy(r), assigned_on_the_fly, unin); + + for (DNF_Iterator di(copy(r).query_DNF()); di; di++) + for (GEQ_Iterator ci = (*di)->GEQs(); ci; ci++) { + + //Anand: temporarily commenting this out as it causes problems 5/28/2013 + /*int j; + for (j = 0; j < variables.size(); j++) + if ((*ci).get_coef(variables[j]) == 0) + break; + if (j != variables.size()) + continue; + */ + for (Constr_Vars_Iter cvi(*ci); cvi; cvi++) { + Variable_ID v1 = cvi.curr_var(); + if (v1->kind() == Global_Var) + if (v1->get_global_var()->arity() > 0) { + + if (i + <= v1->get_global_var()->arity()) { + + /* std::pair<EQ_Handle, int> result = + find_simplest_assignment( + copy(r), v, + assigned_on_the_fly); + + if (result.second < INT_MAX) { + CG_outputRepr *repr = + output_substitution_repr( + ocg, + result.first, v, + true, copy(r), + assigned_on_the_fly); + + inspector = + ocg->CreateArrayRefExpression( + ocg->CreateDotExpression( + ocg->ObtainInspectorData( + v1->get_global_var()->base_name()), + ocg->CreateIdent( + copy( + R).output_var( + i)->name())), + repr); + } else + */ + inspector = + /* ocg->CreateArrayRefExpression( + ocg->CreateDotExpression( + ocg->ObtainInspectorData( + v1->get_global_var()->base_name()), + ocg->CreateIdent( + copy( + R).output_var( + i)->name())), + repr);*/ + + ocg->CreateArrayRefExpression( + + ocg->ObtainInspectorData( + v1->get_global_var()->base_name(), + + copy(R).output_var( + i)->name()), + repr_); + //ocg->CreateIdent( + // v->name())); + + } + } + + } + } + } + + if (inspector != NULL) { + subs.push_back(inspector); + break; + } else if (k == i && repr_ != NULL) { + subs.push_back(repr_); + + } + + //std::pair<EQ_Handle, int> result = find_simplest_assignment(r, + // v, assigned_on_the_fly, &has_insp); + + /*if (has_insp) { + + bool found_insp = false; + //Anand: check if inspector constraint present in equality + for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); + if (v->kind() == Global_Var) + if (v->get_global_var()->arity() > 0) { + global_insp = v->get_global_var(); + found_insp = true; + } + + } + if (found_insp) + if (i <= global_insp->arity()) + inspector = + ocg->CreateArrayRefExpression( + ocg->CreateDotExpression( + ocg->ObtainInspectorData( + global_insp->base_name()), + ocg->CreateIdent( + copy(R).output_var( + i)->name())), + ocg->CreateIdent(v->name())); + + + } + */ + } // for int k + } } - - subs.push_back(repr); - } - - return subs; -} - + fprintf(stderr, "CG_utils.cc output_substitutions() DONE\n\n"); + return subs; + } + + // // handle floor definition wildcards in equality, the second in returned pair // is the cost. // -std::pair<EQ_Handle, int> find_simplest_assignment(const Relation &R, Variable_ID v, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - Conjunct *c = const_cast<Relation &>(R).single_conjunct(); - - int min_cost = INT_MAX; - EQ_Handle eq; - for (EQ_Iterator e(c->EQs()); e; e++) - if (!(*e).has_wildcards() && (*e).get_coef(v) != 0) { - int cost = 0; - - if (abs((*e).get_coef(v)) != 1) - cost += 4; // divide cost - - int num_var = 0; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var() != v) { + std::pair<EQ_Handle, int> find_simplest_assignment(const Relation &R, + Variable_ID v, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + bool *found_inspector_global) { + Conjunct *c = const_cast<Relation &>(R).single_conjunct(); + + int min_cost = INT_MAX; + EQ_Handle eq; + for (EQ_Iterator e(c->EQs()); e; e++) + if (!(*e).has_wildcards() && (*e).get_coef(v) != 0) { + int cost = 0; + + if (abs((*e).get_coef(v)) != 1) + cost += 4; // divide cost + + int num_var = 0; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + if (cvi.curr_var() != v) { + num_var++; + if (abs(cvi.curr_coef()) != 1) + cost += 2; // multiply cost + if (cvi.curr_var()->kind() == Global_Var && cvi.curr_var()->get_global_var()->arity() > 0) { + //Anand --start: Check for Global Variable not being involved in any GEQ + Conjunct *d = + const_cast<Relation &>(R).single_conjunct(); + bool found = false; + for (GEQ_Iterator g(d->GEQs()); g; g++) + if ((*g).get_coef(v) != 0) { + found = true; + break; + } + if (!found) + cost += 10; // function cost + else { + cost = INT_MAX; + eq = *e; + if (found_inspector_global != NULL) + *found_inspector_global = true; + return std::make_pair(eq, cost); + } //Anand --end: Check for Global Variable not being involved in any GEQ + } + else if (cvi.curr_var()->kind() + == Input_Var&& + assigned_on_the_fly.size() >= cvi.curr_var()->get_position() && + assigned_on_the_fly[cvi.curr_var()->get_position()-1].first != NULL) { + cost += assigned_on_the_fly[cvi.curr_var()->get_position()-1].second; // substitution cost on record + } + } + if ((*e).get_const() != 0) num_var++; - if (abs(cvi.curr_coef()) != 1) - cost += 2; // multiply cost - if (cvi.curr_var()->kind() == Global_Var && cvi.curr_var()->get_global_var()->arity() > 0) - cost += 10; // function cost - else if (cvi.curr_var()->kind() == Input_Var && - assigned_on_the_fly.size() >= cvi.curr_var()->get_position() && - assigned_on_the_fly[cvi.curr_var()->get_position()-1].first != NULL) - cost += assigned_on_the_fly[cvi.curr_var()->get_position()-1].second; // substitution cost on record + if (num_var > 1) + cost += num_var - 1; // addition cost + + if (cost < min_cost) { + min_cost = cost; + eq = *e; + if (found_inspector_global != NULL) + *found_inspector_global = true; } - if ((*e).get_const() != 0) - num_var++; - if (num_var > 1) - cost += num_var - 1; // addition cost - - if (cost < min_cost) { - min_cost = cost; - eq = *e; } - } - if (min_cost < INT_MAX) - return std::make_pair(eq, min_cost); - - for (EQ_Iterator e(c->EQs()); e; e++) - if ((*e).has_wildcards() && (*e).get_coef(v) != 0) { - bool is_assignment = true; - for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v); - if (!result.first) { - is_assignment = false; - break; + if (min_cost < INT_MAX) + return std::make_pair(eq, min_cost); + + for (EQ_Iterator e(c->EQs()); e; e++) + if ((*e).has_wildcards() && (*e).get_coef(v) != 0) { + bool is_assignment = true; + for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) { + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v); + if (!result.first) { + is_assignment = false; + break; + } } - } - if (!is_assignment) - continue; - - int cost = 0; - - if (abs((*e).get_coef(v)) != 1) - cost += 4; // divide cost - - int num_var = 0; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var() != v) { + if (!is_assignment) + continue; + + int cost = 0; + + if (abs((*e).get_coef(v)) != 1) + cost += 4; // divide cost + + int num_var = 0; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + if (cvi.curr_var() != v) { + num_var++; + if (abs(cvi.curr_coef()) != 1) + cost += 2; // multiply cost + if (cvi.curr_var()->kind() == Wildcard_Var) + cost += 10; // floor operation cost + else if (cvi.curr_var()->kind() == Global_Var && + cvi.curr_var()->get_global_var()->arity() > 0) { + cost += 20; // function cost + } + else if (cvi.curr_var()->kind() == Input_Var && + assigned_on_the_fly.size() >= cvi.curr_var()->get_position() && + assigned_on_the_fly[cvi.curr_var()->get_position()-1].first != NULL) { + cost += assigned_on_the_fly[cvi.curr_var()->get_position()-1].second; // substitution cost on record + } + } + if ((*e).get_const() != 0) num_var++; - if (abs(cvi.curr_coef()) != 1) - cost += 2; // multiply cost - if (cvi.curr_var()->kind() == Wildcard_Var) - cost += 10; // floor operation cost - else if (cvi.curr_var()->kind() == Global_Var && cvi.curr_var()->get_global_var()->arity() > 0) - cost += 20; // function cost - else if (cvi.curr_var()->kind() == Input_Var && - assigned_on_the_fly.size() >= cvi.curr_var()->get_position() && - assigned_on_the_fly[cvi.curr_var()->get_position()-1].first != NULL) - cost += assigned_on_the_fly[cvi.curr_var()->get_position()-1].second; // substitution cost on record + if (num_var > 1) + cost += num_var - 1; // addition cost + + if (cost < min_cost) { + min_cost = cost; + eq = *e; + if (found_inspector_global != NULL) + *found_inspector_global = true; } - if ((*e).get_const() != 0) - num_var++; - if (num_var > 1) - cost += num_var - 1; // addition cost - - if (cost < min_cost) { - min_cost = cost; - eq = *e; } - } - - return std::make_pair(eq, min_cost); -} - - + + return std::make_pair(eq, min_cost); + } + + // // find floor definition for variable v, e.g. m-c <= 4v <= m, (c is // constant and 0 <= c < 4). this translates to v = floor(m, 4) and // return 4v<=m in this case. All wildcards in such inequality are // also floor defined. // -std::pair<bool, GEQ_Handle> find_floor_definition(const Relation &R, Variable_ID v, std::set<Variable_ID> excluded_floor_vars) { - Conjunct *c = const_cast<Relation &>(R).single_conjunct(); - - excluded_floor_vars.insert(v); - for (GEQ_Iterator e = c->GEQs(); e; e++) { - coef_t a = (*e).get_coef(v); - if (a >= -1) - continue; - a = -a; - - bool interested = true; - for (std::set<Variable_ID>::const_iterator i = excluded_floor_vars.begin(); i != excluded_floor_vars.end(); i++) - if ((*i) != v && (*e).get_coef(*i) != 0) { - interested = false; - break; - } - if (!interested) - continue; - - // check if any wildcard is floor defined - bool has_undefined_wc = false; - for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) - if (excluded_floor_vars.find(cvi.curr_var()) == excluded_floor_vars.end()) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var(), excluded_floor_vars); - if (!result.first) { - has_undefined_wc = true; + std::pair<bool, GEQ_Handle> find_floor_definition(const Relation &R, + Variable_ID v, + std::set<Variable_ID> excluded_floor_vars) { + Conjunct *c = const_cast<Relation &>(R).single_conjunct(); + + excluded_floor_vars.insert(v); + for (GEQ_Iterator e = c->GEQs(); e; e++) { + coef_t a = (*e).get_coef(v); + if (a >= -1) + continue; + a = -a; + + bool interested = true; + for (std::set<Variable_ID>::const_iterator i = excluded_floor_vars.begin(); + i != excluded_floor_vars.end(); + i++) { + if ((*i) != v && (*e).get_coef(*i) != 0) { + interested = false; break; } } - if (has_undefined_wc) - continue; - - // find the matching upper bound for floor definition - for (GEQ_Iterator e2 = c->GEQs(); e2; e2++) - if ((*e2).get_coef(v) == a && (*e).get_const() + (*e2).get_const() < a) { - bool match = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if ((*e2).get_coef(cvi.curr_var()) != -cvi.curr_coef()) { - match = false; + if (!interested) + continue; + + // check if any wildcard is floor defined + bool has_undefined_wc = false; + for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) + if (excluded_floor_vars.find(cvi.curr_var()) == excluded_floor_vars.end()) { + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, + cvi.curr_var(), + excluded_floor_vars); + if (!result.first) { + has_undefined_wc = true; break; } - if (!match) - continue; - for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) - if ((*e).get_coef(cvi.curr_var()) != -cvi.curr_coef()) { - match = false; + } + if (has_undefined_wc) + continue; + + // find the matching upper bound for floor definition + for (GEQ_Iterator e2 = c->GEQs(); e2; e2++) + if ((*e2).get_coef(v) == a && (*e).get_const() + (*e2).get_const() < a) { + bool match = true; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + if ((*e2).get_coef(cvi.curr_var()) != -cvi.curr_coef()) { + match = false; + break; + } + if (!match) + continue; + for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) + if ((*e).get_coef(cvi.curr_var()) != -cvi.curr_coef()) { + match = false; + break; + } + if (match) + return std::make_pair(true, *e); + } + } + + return std::make_pair(false, GEQ_Handle()); + } + + //Anand- adding the following just for debug + std::vector<std::pair<bool, GEQ_Handle> > find_floor_definition_temp( + const Relation &R, Variable_ID v, + std::set<Variable_ID> excluded_floor_vars) { + Conjunct *c = const_cast<Relation &>(R).single_conjunct(); + std::vector<std::pair<bool, GEQ_Handle> > to_return; + excluded_floor_vars.insert(v); + for (GEQ_Iterator e = c->GEQs(); e; e++) { + coef_t a = (*e).get_coef(v); + if (a >= -1) + continue; + a = -a; + + //Anand: commenting out the following for debug 7/28/2013 + bool interested = true; + Variable_ID possibly_interfering; + for (std::set<Variable_ID>::const_iterator i = + excluded_floor_vars.begin(); i != excluded_floor_vars.end(); + i++) + if ((*i) != v && (*e).get_coef(*i) != 0) { + possibly_interfering = *i; + interested = false; + break; + } + + // continue; + + // check if any wildcard is floor defined + bool has_undefined_wc = false; + for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) + if (excluded_floor_vars.find(cvi.curr_var()) + == excluded_floor_vars.end()) { + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, + cvi.curr_var(), excluded_floor_vars); + if (!result.first) { + has_undefined_wc = true; break; } - if (match) - return std::make_pair(true, *e); - } + } + if (has_undefined_wc) + continue; + +// find the matching upper bound for floor definition + for (GEQ_Iterator e2 = c->GEQs(); e2; e2++) + if ((*e2).get_coef(v) == a + && (*e).get_const() + (*e2).get_const() < a) { + bool match = true; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + if (v == cvi.curr_var() + && (*e2).get_coef(cvi.curr_var()) + != -cvi.curr_coef()) { + match = false; + break; + } + if (!match) + continue; + for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) + if (v == cvi.curr_var() + && (*e).get_coef(cvi.curr_var()) + != -cvi.curr_coef()) { + match = false; + break; + } + if (match) { + to_return.push_back(std::make_pair(true, *e)); + if (!interested) + to_return.push_back(std::make_pair(true, *e2)); + return to_return; + + } + } + } + + to_return.push_back(std::make_pair(false, GEQ_Handle())); + + return to_return; } - return std::make_pair(false, GEQ_Handle()); -} - // // find the stride involving the specified variable, the stride // equality can have other wildcards as long as they are defined as // floor variables. // -std::pair<EQ_Handle, Variable_ID> find_simplest_stride(const Relation &R, Variable_ID v) { - int best_num_var = INT_MAX; - coef_t best_coef; - EQ_Handle best_eq; - Variable_ID best_stride_wc; - for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++) - if ((*e).has_wildcards() && (*e).get_coef(v) != 0) { - bool is_stride = true; - bool found_free = false; - int num_var = 0; - int num_floor = 0; - Variable_ID stride_wc; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: { - bool is_free = true; - for (GEQ_Iterator e2(const_cast<Relation &>(R).single_conjunct()->GEQs()); e2; e2++) - if ((*e2).get_coef(cvi.curr_var()) != 0) { - is_free = false; - break; + std::pair<EQ_Handle, Variable_ID> find_simplest_stride(const Relation &R, + Variable_ID v) { + int best_num_var = INT_MAX; + coef_t best_coef; + EQ_Handle best_eq; + Variable_ID best_stride_wc; + for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++) + if ((*e).has_wildcards() && (*e).get_coef(v) != 0) { + bool is_stride = true; + bool found_free = false; + int num_var = 0; + int num_floor = 0; + Variable_ID stride_wc; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { + switch (cvi.curr_var()->kind()) { + case Wildcard_Var: { + bool is_free = true; + for (GEQ_Iterator e2(const_cast<Relation &>(R).single_conjunct()->GEQs()); + e2; + e2++) + if ((*e2).get_coef(cvi.curr_var()) != 0) { + is_free = false; + break; + } + if (is_free) { + if (found_free) + is_stride = false; + else { + found_free = true; + stride_wc = cvi.curr_var(); + } } - if (is_free) { - if (found_free) - is_stride = false; else { - found_free = true; - stride_wc = cvi.curr_var(); + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var()); + if (result.first) + num_floor++; + else + is_stride = false; } + break; } - else { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var()); - if (result.first) - num_floor++; - else - is_stride = false; + case Input_Var: + num_var++; + break; + default: + ; } - break; - } - case Input_Var: - num_var++; - break; - default: - ; + + if (!is_stride) + break; } - if (!is_stride) - break; - } - - if (is_stride) { - coef_t coef = abs((*e).get_coef(v)); - if (best_num_var == INT_MAX || coef < best_coef || - (coef == best_coef && num_var < best_num_var)) { - best_coef = coef; - best_num_var = num_var; - best_eq = *e; - best_stride_wc = stride_wc; + if (is_stride) { + coef_t coef = abs((*e).get_coef(v)); + if (best_num_var == INT_MAX || coef < best_coef || + (coef == best_coef && num_var < best_num_var)) { + best_coef = coef; + best_num_var = num_var; + best_eq = *e; + best_stride_wc = stride_wc; + } } } - } - - if (best_num_var != INT_MAX) - return std::make_pair(best_eq, best_stride_wc); - else - return std::make_pair(EQ_Handle(), static_cast<Variable_ID>(NULL)); -} - + + if (best_num_var != INT_MAX) + return std::make_pair(best_eq, best_stride_wc); + else + return std::make_pair(EQ_Handle(), static_cast<Variable_ID>(NULL)); + } + // // convert relation to if-condition // -CG_outputRepr *output_guard(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - assert(R.n_out()==0); - - CG_outputRepr *result = NULL; - Conjunct *c = const_cast<Relation &>(R).single_conjunct(); - - // e.g. 4i=5*j - for (EQ_Iterator e = c->EQs(); e; e++) - if (!(*e).has_wildcards()) { - CG_outputRepr *lhs = NULL; - CG_outputRepr *rhs = NULL; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); + CG_outputRepr *output_guard(CG_outputBuilder *ocg, + const Relation &R, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::map<std::string, std::vector<CG_outputRepr *> > unin) { + fprintf(stderr, "output_guard()\n"); + assert(R.n_out()==0); + + CG_outputRepr *result = NULL; + Conjunct *c = const_cast<Relation &>(R).single_conjunct(); + + // e.g. 4i=5*j + for (EQ_Iterator e = c->EQs(); e; e++) + if (!(*e).has_wildcards()) { + //fprintf(stderr, "EQ\n"); + CG_outputRepr *lhs = NULL; + CG_outputRepr *rhs = NULL; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { + CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly, unin); + coef_t coef = cvi.curr_coef(); + if (coef > 0) { + if (coef == 1) + lhs = ocg->CreatePlus(lhs, v); + else + lhs = ocg->CreatePlus(lhs, + ocg->CreateTimes(ocg->CreateInt(coef), v)); + } + else { // coef < 0 + if (coef == -1) + rhs = ocg->CreatePlus(rhs, v); + else + rhs = ocg->CreatePlus(rhs, + ocg->CreateTimes(ocg->CreateInt(-coef), v)); + } } - else { // coef < 0 - if (coef == -1) - rhs = ocg->CreatePlus(rhs, v); - else - rhs = ocg->CreatePlus(rhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); + coef_t c = (*e).get_const(); + + CG_outputRepr *term; + if (lhs == NULL) + term = ocg->CreateEQ(rhs, ocg->CreateInt(c)); + else { + if (c > 0) + rhs = ocg->CreateMinus(rhs, ocg->CreateInt(c)); + else if (c < 0) + rhs = ocg->CreatePlus(rhs, ocg->CreateInt(-c)); + else if (rhs == NULL) + rhs = ocg->CreateInt(0); + term = ocg->CreateEQ(lhs, rhs); } + result = ocg->CreateAnd(result, term); } - coef_t c = (*e).get_const(); - - CG_outputRepr *term; - if (lhs == NULL) - term = ocg->CreateEQ(rhs, ocg->CreateInt(c)); - else { - if (c > 0) - rhs = ocg->CreateMinus(rhs, ocg->CreateInt(c)); - else if (c < 0) - rhs = ocg->CreatePlus(rhs, ocg->CreateInt(-c)); - else if (rhs == NULL) - rhs = ocg->CreateInt(0); - term = ocg->CreateEQ(lhs, rhs); - } - result = ocg->CreateAnd(result, term); - } - - // e.g. i>5j - for (GEQ_Iterator e = c->GEQs(); e; e++) - if (!(*e).has_wildcards()) { - CG_outputRepr *lhs = NULL; - CG_outputRepr *rhs = NULL; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); + + // e.g. i>5j + for (GEQ_Iterator e = c->GEQs(); e; e++) + if (!(*e).has_wildcards()) { + //fprintf(stderr, "GEQ\n"); + CG_outputRepr *lhs = NULL; + CG_outputRepr *rhs = NULL; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { + CG_outputRepr *v = output_ident(ocg, + R, + cvi.curr_var(), + assigned_on_the_fly, + unin); + coef_t coef = cvi.curr_coef(); + if (coef > 0) { + if (coef == 1) + lhs = ocg->CreatePlus(lhs, v); + else + lhs = ocg->CreatePlus(lhs, + ocg->CreateTimes(ocg->CreateInt(coef), v)); + } + else { // coef < 0 + if (coef == -1) + rhs = ocg->CreatePlus(rhs, v); + else + rhs = ocg->CreatePlus(rhs, + ocg->CreateTimes(ocg->CreateInt(-coef), v)); + } } - else { // coef < 0 - if (coef == -1) - rhs = ocg->CreatePlus(rhs, v); - else - rhs = ocg->CreatePlus(rhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); + coef_t c = (*e).get_const(); + + CG_outputRepr *term; + if (lhs == NULL) + term = ocg->CreateLE(rhs, ocg->CreateInt(c)); + else { + if (c > 0) + rhs = ocg->CreateMinus(rhs, ocg->CreateInt(c)); + else if (c < 0) + rhs = ocg->CreatePlus(rhs, ocg->CreateInt(-c)); + else if (rhs == NULL) + rhs = ocg->CreateInt(0); + term = ocg->CreateGE(lhs, rhs); } + //fprintf(stderr, "result = ocg->CreateAnd(result, term);\n"); + result = ocg->CreateAnd(result, term); } - coef_t c = (*e).get_const(); - - CG_outputRepr *term; - if (lhs == NULL) - term = ocg->CreateLE(rhs, ocg->CreateInt(c)); - else { - if (c > 0) - rhs = ocg->CreateMinus(rhs, ocg->CreateInt(c)); - else if (c < 0) - rhs = ocg->CreatePlus(rhs, ocg->CreateInt(-c)); - else if (rhs == NULL) - rhs = ocg->CreateInt(0); - term = ocg->CreateGE(lhs, rhs); - } - result = ocg->CreateAnd(result, term); - } - - // e.g. 4i=5j+4alpha - for (EQ_Iterator e = c->EQs(); e; e++) - if ((*e).has_wildcards()) { - Variable_ID wc; - int num_wildcard = 0; - int num_positive = 0; - int num_negative = 0; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - if (cvi.curr_var()->kind() == Wildcard_Var) { - num_wildcard++; - wc = cvi.curr_var(); + + // e.g. 4i=5j+4alpha + for (EQ_Iterator e = c->EQs(); e; e++) + if ((*e).has_wildcards()) { + //fprintf(stderr, "EQ ??\n"); + Variable_ID wc; + int num_wildcard = 0; + int num_positive = 0; + int num_negative = 0; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { + if (cvi.curr_var()->kind() == Wildcard_Var) { + num_wildcard++; + wc = cvi.curr_var(); + } + else { + if (cvi.curr_coef() > 0) + num_positive++; + else + num_negative++; + } + } + + if (num_wildcard > 1) { + delete result; + throw codegen_error( + "Can't generate equality condition with multiple wildcards"); + } + int sign = (num_positive>=num_negative)?1:-1; + + CG_outputRepr *lhs = NULL; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { + if (cvi.curr_var() != wc) { + CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), + assigned_on_the_fly, unin); + coef_t coef = cvi.curr_coef(); + if (sign == 1) { + if (coef > 0) { + if (coef == 1) + lhs = ocg->CreatePlus(lhs, v); + else + lhs = ocg->CreatePlus(lhs, + ocg->CreateTimes(ocg->CreateInt(coef), v)); + } + else { // coef < 0 + if (coef == -1) + lhs = ocg->CreateMinus(lhs, v); + else + lhs = ocg->CreateMinus(lhs, + ocg->CreateTimes(ocg->CreateInt(-coef), v)); + } + } + else { + if (coef > 0) { + if (coef == 1) + lhs = ocg->CreateMinus(lhs, v); + else + lhs = ocg->CreateMinus(lhs, + ocg->CreateTimes(ocg->CreateInt(coef), v)); + } + else { // coef < 0 + if (coef == -1) + lhs = ocg->CreatePlus(lhs, v); + else + lhs = ocg->CreatePlus(lhs, + ocg->CreateTimes(ocg->CreateInt(-coef), v)); + } + } + } + } + coef_t c = (*e).get_const(); + if (sign == 1) { + if (c > 0) + lhs = ocg->CreatePlus(lhs, ocg->CreateInt(c)); + else if (c < 0) + lhs = ocg->CreateMinus(lhs, ocg->CreateInt(-c)); } else { - if (cvi.curr_coef() > 0) - num_positive++; - else - num_negative++; + if (c > 0) + lhs = ocg->CreateMinus(lhs, ocg->CreateInt(c)); + else if (c < 0) + lhs = ocg->CreatePlus(lhs, ocg->CreateInt(-c)); } + + lhs = ocg->CreateIntegerMod(lhs, + ocg->CreateInt(abs((*e).get_coef(wc)))); + CG_outputRepr *term = ocg->CreateEQ(lhs, ocg->CreateInt(0)); + result = ocg->CreateAnd(result, term); } - - if (num_wildcard > 1) { - delete result; - throw codegen_error("Can't generate equality condition with multiple wildcards"); - } - int sign = (num_positive>=num_negative)?1:-1; - - CG_outputRepr *lhs = NULL; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - if (cvi.curr_var() != wc) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); + + // e.g. 4alpha<=i<=5alpha + for (GEQ_Iterator e = c->GEQs(); e; e++) + if ((*e).has_wildcards()) { + //fprintf(stderr, "GEQ ??\n"); + Variable_ID wc; + int num_wildcard = 0; + for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) + if (num_wildcard == 0) { + wc = cvi.curr_var(); + num_wildcard = 1; + } + else + num_wildcard++; + + if (num_wildcard > 1) { + delete result; + // 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"); + } + + coef_t c = (*e).get_coef(wc); + int sign = (c>0)?1:-1; + + GEQ_Iterator e2 = e; + e2++; + for ( ; e2; e2++) { + coef_t c2 = (*e2).get_coef(wc); + if (c2 == 0) + continue; + int sign2 = (c2>0)?1:-1; + if (sign != -sign2) + continue; + int num_wildcard2 = 0; + for (Constr_Vars_Iter cvi(*e2, true); cvi; cvi++) + num_wildcard2++; + if (num_wildcard2 > 1) + continue; + + GEQ_Handle lb, ub; if (sign == 1) { - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); - } - else { // coef < 0 - if (coef == -1) - lhs = ocg->CreateMinus(lhs, v); - else - lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); - } + lb = (*e); + ub = (*e2); } else { - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreateMinus(lhs, v); - else - lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); + lb = (*e2); + ub = (*e); + } + + CG_outputRepr *lhs = NULL; + for (Constr_Vars_Iter cvi(lb); cvi; cvi++) + if (cvi.curr_var() != wc) { + CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), + assigned_on_the_fly, unin); + coef_t coef = cvi.curr_coef(); + if (coef > 0) { + if (coef == 1) + lhs = ocg->CreateMinus(lhs, v); + else + lhs = ocg->CreateMinus(lhs, + ocg->CreateTimes(ocg->CreateInt(coef), v)); + } + else { // coef < 0 + if (coef == -1) + lhs = ocg->CreatePlus(lhs, v); + else + lhs = ocg->CreatePlus(lhs, + ocg->CreateTimes(ocg->CreateInt(-coef), v)); + } } - else { // coef < 0 - if (coef == -1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); + coef_t c = lb.get_const(); + if (c > 0) + lhs = ocg->CreateMinus(lhs, ocg->CreateInt(c)); + else if (c < 0) + lhs = ocg->CreatePlus(lhs, ocg->CreateInt(-c)); + + CG_outputRepr *rhs = NULL; + for (Constr_Vars_Iter cvi(ub); cvi; cvi++) + if (cvi.curr_var() != wc) { + CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), + assigned_on_the_fly, unin); + coef_t coef = cvi.curr_coef(); + if (coef > 0) { + if (coef == 1) + rhs = ocg->CreatePlus(rhs, v); + else + rhs = ocg->CreatePlus(rhs, + ocg->CreateTimes(ocg->CreateInt(coef), v)); + } + else { // coef < 0 + if (coef == -1) + rhs = ocg->CreateMinus(rhs, v); + else + rhs = ocg->CreateMinus(rhs, + ocg->CreateTimes(ocg->CreateInt(-coef), v)); + } } - } + c = ub.get_const(); + if (c > 0) + rhs = ocg->CreatePlus(rhs, ocg->CreateInt(c)); + else if (c < 0) + rhs = ocg->CreateMinus(rhs, ocg->CreateInt(-c)); + + rhs = ocg->CreateIntegerFloor(rhs, ocg->CreateInt(-ub.get_coef(wc))); + rhs = ocg->CreateTimes(ocg->CreateInt(lb.get_coef(wc)), rhs); + CG_outputRepr *term = ocg->CreateLE(lhs, rhs); + result = ocg->CreateAnd(result, term); } } - coef_t c = (*e).get_const(); - if (sign == 1) { - if (c > 0) - lhs = ocg->CreatePlus(lhs, ocg->CreateInt(c)); - else if (c < 0) - lhs = ocg->CreateMinus(lhs, ocg->CreateInt(-c)); - } - else { - if (c > 0) - lhs = ocg->CreateMinus(lhs, ocg->CreateInt(c)); - else if (c < 0) - lhs = ocg->CreatePlus(lhs, ocg->CreateInt(-c)); - } - - lhs = ocg->CreateIntegerMod(lhs, ocg->CreateInt(abs((*e).get_coef(wc)))); - CG_outputRepr *term = ocg->CreateEQ(lhs, ocg->CreateInt(0)); - result = ocg->CreateAnd(result, term); - } + + //fprintf(stderr, "output_guard returning at bottom 0x%x\n", result); + return result; + } + + +// +// return NULL if 0 +// + CG_outputRepr *output_inequality_repr(CG_outputBuilder *ocg, + const GEQ_Handle &inequality, + Variable_ID v, + const Relation &R, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::map<std::string, std::vector<CG_outputRepr *> > unin, + std::set<Variable_ID> excluded_floor_vars) { + fprintf(stderr, "output_inequality_repr() v %s\n", v->name().c_str()); + + const_cast<Relation &>(R).setup_names(); // hack + + coef_t a = inequality.get_coef(v); + assert(a != 0); + excluded_floor_vars.insert(v); + + std::vector<std::pair<bool, GEQ_Handle> > result2; + CG_outputRepr *repr = NULL; + for (Constr_Vars_Iter cvi(inequality); cvi; cvi++) + if (cvi.curr_var() != v) { + CG_outputRepr *t; + if (cvi.curr_var()->kind() == Wildcard_Var) { + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, + cvi.curr_var(), + excluded_floor_vars); + if (!result.first) { + fprintf(stderr, "\n\n*** heading into NEW CODE\n"); + + coef_t coef_ = cvi.curr_coef(); + result2 = find_floor_definition_temp(R, cvi.curr_var(), + excluded_floor_vars); + + for (Constr_Vars_Iter cvi_( + result2[result2.size() - 1].second); cvi_; cvi_++) { + if (cvi_.curr_var()->kind() != Wildcard_Var + && cvi_.curr_var()->kind() != Set_Var) { + t = output_ident(ocg, R, cvi_.curr_var(), + assigned_on_the_fly, unin); + coef_t coef2 = cvi_.curr_coef(); + assert(cvi_.curr_coef() == -1 && a == 1); + repr = ocg->CreateIntegerFloor(t, + ocg->CreateInt(-coef_)); + repr = ocg->CreateTimes(ocg->CreateInt(-coef_), + repr); + + fprintf(stderr, "returning a TIMES\n"); + return repr; + + } + + } + + }; - // e.g. 4alpha<=i<=5alpha - for (GEQ_Iterator e = c->GEQs(); e; e++) - if ((*e).has_wildcards()) { - Variable_ID wc; - int num_wildcard = 0; - for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) - if (num_wildcard == 0) { - wc = cvi.curr_var(); - num_wildcard = 1; + if (!result.first) { + delete repr; + throw codegen_error("Can't generate bound expression with wildcard not involved in floor definition"); + } + try { + t = output_inequality_repr(ocg, + result.second, + cvi.curr_var(), + R, + assigned_on_the_fly, + unin, + excluded_floor_vars); + } + catch (const std::exception &e) { + delete repr; + throw e; + } } else - num_wildcard++; - - if (num_wildcard > 1) { - delete result; - // 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"); - } - - coef_t c = (*e).get_coef(wc); - int sign = (c>0)?1:-1; - - GEQ_Iterator e2 = e; - e2++; - for ( ; e2; e2++) { - coef_t c2 = (*e2).get_coef(wc); - if (c2 == 0) - continue; - int sign2 = (c2>0)?1:-1; - if (sign != -sign2) - continue; - int num_wildcard2 = 0; - for (Constr_Vars_Iter cvi(*e2, true); cvi; cvi++) - num_wildcard2++; - if (num_wildcard2 > 1) - continue; - - GEQ_Handle lb, ub; - if (sign == 1) { - lb = (*e); - ub = (*e2); + t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly, unin); + + coef_t coef = cvi.curr_coef(); + if (a > 0) { + if (coef > 0) { + if (coef == 1) + repr = ocg->CreateMinus(repr, t); + else + repr = ocg->CreateMinus(repr, + ocg->CreateTimes(ocg->CreateInt(coef),t)); + } + else { + if (coef == -1) + repr = ocg->CreatePlus(repr, t); + else + repr = ocg->CreatePlus(repr, + ocg->CreateTimes(ocg->CreateInt(-coef),t)); + } } else { - lb = (*e2); - ub = (*e); - } - - CG_outputRepr *lhs = NULL; - for (Constr_Vars_Iter cvi(lb); cvi; cvi++) - if (cvi.curr_var() != wc) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreateMinus(lhs, v); - else - lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); - } - else { // coef < 0 - if (coef == -1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); - } + if (coef > 0) { + if (coef == 1) + repr = ocg->CreatePlus(repr, t); + else + repr = ocg->CreatePlus(repr, + ocg->CreateTimes(ocg->CreateInt(coef),t)); } - coef_t c = lb.get_const(); - if (c > 0) - lhs = ocg->CreateMinus(lhs, ocg->CreateInt(c)); - else if (c < 0) - lhs = ocg->CreatePlus(lhs, ocg->CreateInt(-c)); - - CG_outputRepr *rhs = NULL; - for (Constr_Vars_Iter cvi(ub); cvi; cvi++) - if (cvi.curr_var() != wc) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - if (coef > 0) { - if (coef == 1) - rhs = ocg->CreatePlus(rhs, v); - else - rhs = ocg->CreatePlus(rhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); - } - else { // coef < 0 - if (coef == -1) - rhs = ocg->CreateMinus(rhs, v); - else - rhs = ocg->CreateMinus(rhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); - } + else { + if (coef == -1) + repr = ocg->CreateMinus(repr, t); + else + repr = ocg->CreateMinus(repr, + ocg->CreateTimes(ocg->CreateInt(-coef),t)); } - c = ub.get_const(); - if (c > 0) - rhs = ocg->CreatePlus(rhs, ocg->CreateInt(c)); - else if (c < 0) - rhs = ocg->CreateMinus(rhs, ocg->CreateInt(-c)); - - rhs = ocg->CreateIntegerFloor(rhs, ocg->CreateInt(-ub.get_coef(wc))); - rhs = ocg->CreateTimes(ocg->CreateInt(lb.get_coef(wc)), rhs); - CG_outputRepr *term = ocg->CreateLE(lhs, rhs); - result = ocg->CreateAnd(result, term); + } } + coef_t c = inequality.get_const(); + if (c > 0) { + if (a > 0) + repr = ocg->CreateMinus(repr, ocg->CreateInt(c)); + else + repr = ocg->CreatePlus(repr, ocg->CreateInt(c)); } + else if (c < 0) { + if (a > 0) + repr = ocg->CreatePlus(repr, ocg->CreateInt(-c)); + else + repr = ocg->CreateMinus(repr, ocg->CreateInt(-c)); + } + + if (abs(a) == 1) + return repr; + else if (a > 0) + return ocg->CreateIntegerCeil(repr, ocg->CreateInt(a)); + else // a < 0 + return ocg->CreateIntegerFloor(repr, ocg->CreateInt(-a)); + } + - return result; -} - - // -// return NULL if 0 +// nothing special, just an alias // -CG_outputRepr *output_inequality_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, std::set<Variable_ID> excluded_floor_vars) { - const_cast<Relation &>(R).setup_names(); // hack + CG_outputRepr *output_upper_bound_repr(CG_outputBuilder *ocg, + const GEQ_Handle &inequality, + Variable_ID v, + const Relation &R, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::map<std::string, std::vector<CG_outputRepr *> > unin) { + assert(inequality.get_coef(v) < 0); + CG_outputRepr* zero_; + + zero_ = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly, + unin); + + if(!zero_) + zero_ = ocg->CreateInt(0); + + return zero_; + } - coef_t a = inequality.get_coef(v); - assert(a != 0); - excluded_floor_vars.insert(v); - CG_outputRepr *repr = NULL; - for (Constr_Vars_Iter cvi(inequality); cvi; cvi++) - if (cvi.curr_var() != v) { - CG_outputRepr *t; - if (cvi.curr_var()->kind() == Wildcard_Var) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var(), excluded_floor_vars); - if (!result.first) { - delete repr; - throw codegen_error("Can't generate bound expression with wildcard not involved in floor definition"); - } - try { - t = output_inequality_repr(ocg, result.second, cvi.curr_var(), R, assigned_on_the_fly, excluded_floor_vars); - } - catch (const std::exception &e) { - delete repr; - throw e; - } +// +// output lower bound with respect to lattice +// + CG_outputRepr *output_lower_bound_repr(CG_outputBuilder *ocg, + const GEQ_Handle &inequality, + Variable_ID v, + const EQ_Handle &stride_eq, + Variable_ID wc, + const Relation &R, + const Relation &known, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::map<std::string, std::vector<CG_outputRepr *> > unin) { + + fprintf(stderr, "output_lower_bound_repr()\n"); + assert(inequality.get_coef(v) > 0); + CG_outputRepr* zero_; + if (wc == NULL + || bound_must_hit_stride(inequality, v, stride_eq, wc, R, known)){ + zero_ = output_inequality_repr(ocg, inequality, v, R, + assigned_on_the_fly, unin); + if(!zero_) + zero_ = ocg->CreateInt(0); + + return zero_; + } + CG_outputRepr *strideBoundRepr = NULL; + int sign = (stride_eq.get_coef(v)>0)?1:-1; + for (Constr_Vars_Iter cvi(stride_eq); cvi; cvi++) { + Variable_ID v2 = cvi.curr_var(); + if (v2 == v || v2 == wc) + continue; + + CG_outputRepr *v_repr; + if (v2->kind() == Input_Var || v2->kind() == Global_Var) + v_repr = output_ident(ocg, R, v2, assigned_on_the_fly,unin); + else if (v2->kind() == Wildcard_Var) { + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v2); + assert(result.first); + v_repr = output_inequality_repr(ocg, result.second, v2, R, + assigned_on_the_fly, unin); } - else - t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - + coef_t coef = cvi.curr_coef(); - if (a > 0) { + if (sign < 0) { if (coef > 0) { if (coef == 1) - repr = ocg->CreateMinus(repr, t); + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr); else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, + ocg->CreateTimes(ocg->CreateInt(coef), v_repr)); } - else { + else { // coef < 0 if (coef == -1) - repr = ocg->CreatePlus(repr, t); + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr); else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, + ocg->CreateTimes(ocg->CreateInt(-coef), v_repr)); } } else { if (coef > 0) { if (coef == 1) - repr = ocg->CreatePlus(repr, t); + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr); else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, + ocg->CreateTimes(ocg->CreateInt(coef), v_repr)); } - else { + else { // coef < 0 if (coef == -1) - repr = ocg->CreateMinus(repr, t); + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr); else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, + ocg->CreateTimes(ocg->CreateInt(-coef), v_repr)); } } + } + coef_t c = stride_eq.get_const(); + fprintf(stderr, "stride eq const %d\n", c); + fprintf(stderr, "sign %d\n", sign ); + if (c > 0) { + if (sign < 0) + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateInt(c)); + else + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateInt(c)); } - coef_t c = inequality.get_const(); - if (c > 0) { - if (a > 0) - repr = ocg->CreateMinus(repr, ocg->CreateInt(c)); - else - repr = ocg->CreatePlus(repr, ocg->CreateInt(c)); - } - else if (c < 0) { - if (a > 0) - repr = ocg->CreatePlus(repr, ocg->CreateInt(-c)); - else - repr = ocg->CreateMinus(repr, ocg->CreateInt(-c)); - } - - if (abs(a) == 1) - return repr; - else if (a > 0) - return ocg->CreateIntegerCeil(repr, ocg->CreateInt(a)); - else // a < 0 - return ocg->CreateIntegerFloor(repr, ocg->CreateInt(-a)); -} - - -// -// nothing special, just an alias -// -CG_outputRepr *output_upper_bound_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - assert(inequality.get_coef(v) < 0); - CG_outputRepr* zero_; - - zero_ = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly); - - if(!zero_) - zero_ = ocg->CreateInt(0); - - return zero_; - -} - - -// -// output lower bound with respect to lattice -// -CG_outputRepr *output_lower_bound_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const EQ_Handle &stride_eq, Variable_ID wc, const Relation &R, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - assert(inequality.get_coef(v) > 0); - CG_outputRepr* zero_; - if (wc == NULL || bound_must_hit_stride(inequality, v, stride_eq, wc, R, known)){ - zero_ = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly); - if(!zero_) - zero_ = ocg->CreateInt(0); - - return zero_; - } - CG_outputRepr *strideBoundRepr = NULL; - int sign = (stride_eq.get_coef(v)>0)?1:-1; - for (Constr_Vars_Iter cvi(stride_eq); cvi; cvi++) { - Variable_ID v2 = cvi.curr_var(); - if (v2 == v || v2 == wc) - continue; - - CG_outputRepr *v_repr; - if (v2->kind() == Input_Var || v2->kind() == Global_Var) - v_repr = output_ident(ocg, R, v2, assigned_on_the_fly); - else if (v2->kind() == Wildcard_Var) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v2); - assert(result.first); - v_repr = output_inequality_repr(ocg, result.second, v2, R, assigned_on_the_fly); + else if (c < 0) { + if (sign < 0) + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateInt(-c)); + else + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateInt(-c)); } + + CG_outputRepr *repr = output_inequality_repr(ocg, inequality, v, R, + assigned_on_the_fly, unin); + //fprintf(stderr, "inequality repr %p\n", repr); + CG_outputRepr *repr2 = ocg->CreateCopy(repr); + + fprintf(stderr, "stride_eq.get_coef(wc) %d\n", stride_eq.get_coef(wc)); + fprintf(stderr, "repr + mod( strideBoundRepr - repr, %d )\n", stride_eq.get_coef(wc)); - coef_t coef = cvi.curr_coef(); - if (sign < 0) { - if (coef > 0) { - if (coef == 1) - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr); - else - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(coef), v_repr)); - } - else { // coef < 0 - if (coef == -1) - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr); - else - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(-coef), v_repr)); - } - } - else { - if (coef > 0) { - if (coef == 1) - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr); - else - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(coef), v_repr)); - } - else { // coef < 0 - if (coef == -1) - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr); - else - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(-coef), v_repr)); - } - } - } - coef_t c = stride_eq.get_const(); - if (c > 0) { - if (sign < 0) - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateInt(c)); - else - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateInt(c)); - } - else if (c < 0) { - if (sign < 0) - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateInt(-c)); - else - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateInt(-c)); + repr = ocg->CreatePlus(repr2, + ocg->CreateIntegerMod(ocg->CreateMinus(strideBoundRepr, repr), + ocg->CreateInt(abs(stride_eq.get_coef(wc))))); + + return repr; } - - CG_outputRepr *repr = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly); - CG_outputRepr *repr2 = ocg->CreateCopy(repr); - repr = ocg->CreatePlus(repr2, ocg->CreateIntegerMod(ocg->CreateMinus(strideBoundRepr, repr), ocg->CreateInt(abs(stride_eq.get_coef(wc))))); - - return repr; -} - + // // return loop control structure only // -CG_outputRepr *output_loop(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - std::pair<EQ_Handle, Variable_ID> result = find_simplest_stride(R, const_cast<Relation &>(R).set_var(level)); - if (result.second != NULL) - assert(abs(result.first.get_coef(const_cast<Relation &>(R).set_var(level))) == 1); - - std::vector<CG_outputRepr *> lbList, ubList; - try { - - coef_t const_lb = negInfinity, const_ub = posInfinity; + CG_outputRepr *output_loop(CG_outputBuilder *ocg, + const Relation &R, + int level, + const Relation &known, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::map<std::string, std::vector<CG_outputRepr *> > unin) { + + fprintf(stderr, "CG_utils.cc output_loop()\n"); + std::pair<EQ_Handle, Variable_ID> result = find_simplest_stride(R, const_cast<Relation &>(R).set_var(level)); + fprintf(stderr, "found stride\n"); - for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); e; e++) { - coef_t coef = (*e).get_coef(const_cast<Relation &>(R).set_var(level)); + if (result.second != NULL) + assert(abs(result.first.get_coef(const_cast<Relation &>(R).set_var(level))) == 1); + + std::vector<CG_outputRepr *> lbList, ubList; + try { + + coef_t const_lb = negInfinity, const_ub = posInfinity; + + for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); + e; + e++) { + fprintf(stderr, "new e\n"); + coef_t coef = (*e).get_coef(const_cast<Relation &>(R).set_var(level)); + + fprintf(stderr, "coef %d\n", coef); + if (coef > 0) { + CG_outputRepr *repr = output_lower_bound_repr(ocg, *e, const_cast<Relation &>(R).set_var(level), result.first, result.second, R, known, assigned_on_the_fly, unin); + fprintf(stderr, "got a repr\n"); + if (repr == NULL) fprintf(stderr, "repr NULL\n"); - if (coef > 0) { - CG_outputRepr *repr = output_lower_bound_repr(ocg, *e, const_cast<Relation &>(R).set_var(level), result.first, result.second, R, known, assigned_on_the_fly); if (repr == NULL) - repr = ocg->CreateInt(0); - lbList.push_back(repr); - - if ((*e).is_const(const_cast<Relation &>(R).set_var(level))){ - if(!result.second) { - - //no variables but v in constr - coef_t L,m; - L = -((*e).get_const()); - - m = (*e).get_coef(const_cast<Relation &>(R).set_var(level)); - coef_t sb = (int) (ceil(((float) L) /m)); - set_max(const_lb, sb); + repr = ocg->CreateInt(0); + lbList.push_back(repr); + + if ((*e).is_const(const_cast<Relation &>(R).set_var(level))){ + if(!result.second) { + + //no variables but v in constr + coef_t L,m; + L = -((*e).get_const()); + + m = (*e).get_coef(const_cast<Relation &>(R).set_var(level)); + coef_t sb = (int) (ceil(((float) L) /m)); + set_max(const_lb, sb); } - else{ - - coef_t L,m,s,c; - L = -((*e).get_const()); - m = (*e).get_coef(const_cast<Relation &>(R).set_var(level)); - s = abs(result.first.get_coef(result.second)); - c = result.first.get_const(); - coef_t sb = (s * (int) (ceil( (float) (L - (c * m)) /(s*m))))+ c; - set_max(const_lb, sb); - - } + else{ + + coef_t L,m,s,c; + L = -((*e).get_const()); + m = (*e).get_coef(const_cast<Relation &>(R).set_var(level)); + s = abs(result.first.get_coef(result.second)); + c = result.first.get_const(); + coef_t sb = (s * (int) (ceil( (float) (L - (c * m)) /(s*m))))+ c; + set_max(const_lb, sb); + + } + } + } - - } - else if (coef < 0) { - CG_outputRepr *repr = output_upper_bound_repr(ocg, *e, const_cast<Relation &>(R).set_var(level), R, assigned_on_the_fly); - if (repr == NULL) - repr = ocg->CreateInt(0); - ubList.push_back(repr); - - if ((*e).is_const(const_cast<Relation &>(R).set_var(level))) { - // no variables but v in constraint - set_min(const_ub,-(*e).get_const()/(*e).get_coef(const_cast<Relation &>(R).set_var(level))); + else if (coef < 0) { + CG_outputRepr *repr = output_upper_bound_repr(ocg, + *e, + const_cast<Relation &>(R).set_var(level), + R, + assigned_on_the_fly, + unin); + if (repr == NULL) + repr = ocg->CreateInt(0); + ubList.push_back(repr); + + if ((*e).is_const(const_cast<Relation &>(R).set_var(level))) { + // no variables but v in constraint + set_min(const_ub,-(*e).get_const()/(*e).get_coef(const_cast<Relation &>(R).set_var(level))); + } + } - } + + if(fillInBounds && lbList.size() == 1 && const_lb != negInfinity) + lowerBoundForLevel = const_lb; + + if(fillInBounds && const_ub != posInfinity) { + upperBoundForLevel = const_ub; + } + if (lbList.size() == 0) + throw codegen_error( + "missing lower bound at loop level " + to_string(level)); + if (ubList.size() == 0) + throw codegen_error( + "missing upper bound at loop level " + to_string(level)); + } + catch (const std::exception &e) { + for (int i = 0; i < lbList.size(); i++) + delete lbList[i]; + for (int i = 0; i < ubList.size(); i++) + delete ubList[i]; + throw e; } - if(fillInBounds && lbList.size() == 1 && const_lb != negInfinity) - lowerBoundForLevel = const_lb; + CG_outputRepr *lbRepr = NULL; + if (lbList.size() > 1) { + fprintf(stderr, "CG_utils.cc output_loop() createInvoke( max )\n"); + lbRepr = ocg->CreateInvoke("max", lbList); + } + else { // (lbList.size() == 1) + lbRepr = lbList[0]; + } - if(fillInBounds && const_ub != posInfinity) - upperBoundForLevel = const_ub; - if (lbList.size() == 0) - throw codegen_error("missing lower bound at loop level " + to_string(level)); - if (ubList.size() == 0) - throw codegen_error("missing upper bound at loop level " + to_string(level)); - } - catch (const std::exception &e) { - for (int i = 0; i < lbList.size(); i++) - delete lbList[i]; - for (int i = 0; i < ubList.size(); i++) - delete ubList[i]; - throw e; + CG_outputRepr *ubRepr = NULL; + if (ubList.size() > 1) { + fprintf(stderr, "CG_utils.cc output_loop() createInvoke( min )\n"); + ubRepr = ocg->CreateInvoke("min", ubList); + } + else { // (ubList.size() == 1) + ubRepr = ubList[0]; + } + + CG_outputRepr *stRepr; + if (result.second == NULL) + stRepr = ocg->CreateInt(1); + else + stRepr = ocg->CreateInt(abs(result.first.get_coef(result.second))); + CG_outputRepr *indexRepr = output_ident(ocg, + R, + const_cast<Relation &>(R).set_var(level), + assigned_on_the_fly, + unin); + //fprintf(stderr,"CG_utils.cc output_loop() returning CreateInductive()\n"); + return ocg->CreateInductive(indexRepr, lbRepr, ubRepr, stRepr); } - - CG_outputRepr *lbRepr = NULL; - if (lbList.size() > 1) - lbRepr = ocg->CreateInvoke("max", lbList); - else // (lbList.size() == 1) - lbRepr = lbList[0]; - - CG_outputRepr *ubRepr = NULL; - if (ubList.size() > 1) - ubRepr = ocg->CreateInvoke("min", ubList); - else // (ubList.size() == 1) - ubRepr = ubList[0]; - - CG_outputRepr *stRepr; - if (result.second == NULL) - stRepr = ocg->CreateInt(1); - else - stRepr = ocg->CreateInt(abs(result.first.get_coef(result.second))); - CG_outputRepr *indexRepr = output_ident(ocg, R, const_cast<Relation &>(R).set_var(level), assigned_on_the_fly); - return ocg->CreateInductive(indexRepr, lbRepr, ubRepr, stRepr); -} - - + + // // parameter f_root is inside f_exists, not the other way around. // return replicated variable in new relation, with all cascaded floor definitions // using wildcards defined in the same way as in the original relation. // -Variable_ID replicate_floor_definition(const Relation &R, const Variable_ID floor_var, - Relation &r, F_Exists *f_exists, F_And *f_root, - std::map<Variable_ID, Variable_ID> &exists_mapping) { - assert(R.n_out() == 0 && r.n_out() == 0 && R.n_inp() == r.n_inp()); - - std::set<Variable_ID> excluded_floor_vars; - std::stack<Variable_ID> to_fill; - to_fill.push(floor_var); + Variable_ID replicate_floor_definition(const Relation &R, + const Variable_ID floor_var, + Relation &r, + F_Exists *f_exists, + F_And *f_root, + std::map<Variable_ID, Variable_ID> &exists_mapping) { + //Anand: commenting the assertion out 8/4/2013 + //assert(R.n_out() == 0 && r.n_out() == 0 && R.n_inp() == r.n_inp()); + bool is_mapping = false; + if (r.n_out() > 0) + is_mapping = true; + + std::set<Variable_ID> excluded_floor_vars; + std::set<Variable_ID> excluded_floor_vars2; + std::stack<Variable_ID> to_fill; + to_fill.push(floor_var); + + while (!to_fill.empty()) { + Variable_ID v = to_fill.top(); + to_fill.pop(); + if (excluded_floor_vars.find(v) != excluded_floor_vars.end()) + continue; + + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v, + excluded_floor_vars); + std::vector<std::pair<bool, GEQ_Handle> > result2; + + if (!result.first) { + + result2 = find_floor_definition_temp(R, v, excluded_floor_vars2); + assert(result2.size() >= 1); + result = result2[0]; + } + else + result2.push_back(result); - while (!to_fill.empty()) { - Variable_ID v = to_fill.top(); - to_fill.pop(); - if (excluded_floor_vars.find(v) != excluded_floor_vars.end()) - continue; - - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v, excluded_floor_vars); - assert(result.first); - excluded_floor_vars.insert(v); + assert(result.first); + excluded_floor_vars.insert(v); + excluded_floor_vars2.insert(v); - GEQ_Handle h1 = f_root->add_GEQ(); - GEQ_Handle h2 = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(result.second); cvi; cvi++) { - Variable_ID v2 = cvi.curr_var(); - switch (v2->kind()) { - case Input_Var: { - int pos = v2->get_position(); - h1.update_coef(r.input_var(pos), cvi.curr_coef()); - h2.update_coef(r.input_var(pos), -cvi.curr_coef()); - break; - } - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(v2); - Variable_ID v3; - if (p == exists_mapping.end()) { - v3 = f_exists->declare(); - exists_mapping[v2] = v3; + for (int i = 0; i < result2.size(); i++) { + + GEQ_Handle h1 = f_root->add_GEQ(); + GEQ_Handle h2 = f_root->add_GEQ(); + for (Constr_Vars_Iter cvi(result2[i].second); cvi; cvi++) { + Variable_ID v2 = cvi.curr_var(); + switch (v2->kind()) { + case Input_Var: { + int pos = v2->get_position(); + if (!is_mapping) { + h1.update_coef(r.input_var(pos), cvi.curr_coef()); + h2.update_coef(r.input_var(pos), -cvi.curr_coef()); + } + else { + h1.update_coef(r.output_var(pos), cvi.curr_coef()); + h2.update_coef(r.output_var(pos), -cvi.curr_coef()); + } + break; + } + case Wildcard_Var: { + std::map<Variable_ID, Variable_ID>::iterator p=exists_mapping.find(v2); + Variable_ID v3; + if (p == exists_mapping.end()) { + v3 = f_exists->declare(); + exists_mapping[v2] = v3; + } + else + v3 = p->second; + h1.update_coef(v3, cvi.curr_coef()); + h2.update_coef(v3, -cvi.curr_coef()); + if (v2 != v) + to_fill.push(v2); + break; + } + case Global_Var: { + Global_Var_ID g = v2->get_global_var(); + Variable_ID v3; + if (g->arity() == 0) + v3 = r.get_local(g); + else + v3 = r.get_local(g, v2->function_of()); + h1.update_coef(v3, cvi.curr_coef()); + h2.update_coef(v3, -cvi.curr_coef()); + break; + } + default: + assert(false); + } } - else - v3 = p->second; - h1.update_coef(v3, cvi.curr_coef()); - h2.update_coef(v3, -cvi.curr_coef()); - if (v2 != v) - to_fill.push(v2); - break; - } - case Global_Var: { - Global_Var_ID g = v2->get_global_var(); - Variable_ID v3; - if (g->arity() == 0) - v3 = r.get_local(g); - else - v3 = r.get_local(g, v2->function_of()); - h1.update_coef(v3, cvi.curr_coef()); - h2.update_coef(v3, -cvi.curr_coef()); - break; - } - default: - assert(false); + h1.update_const(result2[i].second.get_const()); + h2.update_const( + -result2[i].second.get_const() + - result2[i].second.get_coef(v) - 1); } } - h1.update_const(result.second.get_const()); - h2.update_const(-result.second.get_const()-result.second.get_coef(v)-1); + if (floor_var->kind() == Input_Var) + return r.input_var(floor_var->get_position()); + else if (floor_var->kind() == Wildcard_Var) + return exists_mapping[floor_var]; + else + assert(false); } - - if (floor_var->kind() == Input_Var) - return r.input_var(floor_var->get_position()); - else if (floor_var->kind() == Wildcard_Var) - return exists_mapping[floor_var]; - else - assert(false); -} - - + + // // pick one guard condition from relation. it can involve multiple // constraints when involving wildcards, as long as its complement // is a single conjunct. // -Relation pick_one_guard(const Relation &R, int level) { - assert(R.n_out()==0); - - Relation r = Relation::True(R.n_set()); - - for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); e; e++) - if (!(*e).has_wildcards()) { - r.and_with_GEQ(*e); - r.simplify(); - r.copy_names(R); - r.setup_names(); - return r; - } - - for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++) - if (!(*e).has_wildcards()) { - r.and_with_GEQ(*e); - r.simplify(); - r.copy_names(R); - r.setup_names(); - return r; - } - - for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++) - if ((*e).has_wildcards()) { - int num_wildcard = 0; - int max_level = 0; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: - num_wildcard++; - break; - case Input_Var: - if (cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - break; - default: - ; - } - - if (num_wildcard == 1 && max_level != level-1) { - r.and_with_EQ(*e); + Relation pick_one_guard(const Relation &R, int level) { + //fprintf(stderr, "pick_one_guard()\n"); + assert(R.n_out()==0); + + Relation r = Relation::True(R.n_set()); + + for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); + e; + e++) + if (!(*e).has_wildcards()) { + r.and_with_GEQ(*e); r.simplify(); r.copy_names(R); r.setup_names(); return r; } - } - - for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); e; e++) - if ((*e).has_wildcards()) { - int num_wildcard = 0; - int max_level = 0; - bool direction; - Variable_ID wc; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: - num_wildcard++; - wc = cvi.curr_var(); - direction = cvi.curr_coef()>0?true:false; - break; - case Input_Var: - if (cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - break; - default: - ; + + for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); + e; + e++) + if (!(*e).has_wildcards()) { + r.and_with_GEQ(*e); + r.simplify(); + r.copy_names(R); + r.setup_names(); + return r; + } + + for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); + e; + e++) + if ((*e).has_wildcards()) { + int num_wildcard = 0; + int max_level = 0; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + switch (cvi.curr_var()->kind()) { + case Wildcard_Var: + num_wildcard++; + break; + case Input_Var: + if (cvi.curr_var()->get_position() > max_level) + max_level = cvi.curr_var()->get_position(); + break; + default: + ; + } + + if (num_wildcard == 1 && max_level != level-1) { + r.and_with_EQ(*e); + r.simplify(); + r.copy_names(R); + r.setup_names(); + return r; } - - if (num_wildcard == 1 && max_level != level-1) { - // find the pairing inequality - GEQ_Iterator e2 = e; - e2++; - for ( ; e2; e2++) { - int num_wildcard2 = 0; - int max_level2 = 0; - bool direction2; - Variable_ID wc2; - for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: - num_wildcard2++; - wc2 = cvi.curr_var(); - direction2 = cvi.curr_coef()>0?true:false; - break; - case Input_Var: - if (cvi.curr_var()->get_position() > max_level2) - max_level2 = cvi.curr_var()->get_position(); - break; - default: - ; - } - - if (num_wildcard2 == 1 && max_level2 != level-1 && wc2 == wc && direction2 == not direction) { - F_Exists *f_exists = r.and_with_and()->add_exists(); - Variable_ID wc3 = f_exists->declare(); - F_And *f_root = f_exists->add_and(); - GEQ_Handle h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { + } + + for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); + e; + e++) + if ((*e).has_wildcards()) { + int num_wildcard = 0; + int max_level = 0; + bool direction; + Variable_ID wc; + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) + switch (cvi.curr_var()->kind()) { + case Wildcard_Var: + num_wildcard++; + wc = cvi.curr_var(); + direction = cvi.curr_coef()>0?true:false; + break; + case Input_Var: + if (cvi.curr_var()->get_position() > max_level) + max_level = cvi.curr_var()->get_position(); + break; + default: + ; + } + + if (num_wildcard == 1 && max_level != level-1) { + // find the pairing inequality + GEQ_Iterator e2 = e; + e2++; + for ( ; e2; e2++) { + int num_wildcard2 = 0; + int max_level2 = 0; + bool direction2; + Variable_ID wc2; + for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) switch (cvi.curr_var()->kind()) { case Wildcard_Var: - h.update_coef(wc3, cvi.curr_coef()); + num_wildcard2++; + wc2 = cvi.curr_var(); + direction2 = cvi.curr_coef()>0?true:false; break; case Input_Var: - h.update_coef(r.input_var(cvi.curr_var()->get_position()), cvi.curr_coef()); - break; - case Global_Var: { - Global_Var_ID g = cvi.curr_var()->get_global_var(); - Variable_ID v; - if (g->arity() == 0) - v = r.get_local(g); - else - v = r.get_local(g, cvi.curr_var()->function_of()); - h.update_coef(v, cvi.curr_coef()); + if (cvi.curr_var()->get_position() > max_level2) + max_level2 = cvi.curr_var()->get_position(); break; - } default: - assert(false); + ; } - } - h.update_const((*e).get_const()); - h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) { - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: - h.update_coef(wc3, cvi.curr_coef()); - break; - case Input_Var: - h.update_coef(r.input_var(cvi.curr_var()->get_position()), cvi.curr_coef()); - break; - case Global_Var: { - Global_Var_ID g = cvi.curr_var()->get_global_var(); - Variable_ID v; - if (g->arity() == 0) - v = r.get_local(g); - else - v = r.get_local(g, cvi.curr_var()->function_of()); - h.update_coef(v, cvi.curr_coef()); - break; + if (num_wildcard2 == 1 + && max_level2 != level-1 + && wc2 == wc + && direction2 == not direction) { + F_Exists *f_exists = r.and_with_and()->add_exists(); + Variable_ID wc3 = f_exists->declare(); + F_And *f_root = f_exists->add_and(); + GEQ_Handle h = f_root->add_GEQ(); + for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { + switch (cvi.curr_var()->kind()) { + case Wildcard_Var: + h.update_coef(wc3, cvi.curr_coef()); + break; + case Input_Var: + h.update_coef(r.input_var(cvi.curr_var()->get_position()), + cvi.curr_coef()); + break; + case Global_Var: { + Global_Var_ID g = cvi.curr_var()->get_global_var(); + Variable_ID v; + if (g->arity() == 0) + v = r.get_local(g); + else + v = r.get_local(g, cvi.curr_var()->function_of()); + h.update_coef(v, cvi.curr_coef()); + break; + } + default: + assert(false); + } } - default: - assert(false); + h.update_const((*e).get_const()); + + h = f_root->add_GEQ(); + for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) { + switch (cvi.curr_var()->kind()) { + case Wildcard_Var: + h.update_coef(wc3, cvi.curr_coef()); + break; + case Input_Var: + h.update_coef(r.input_var(cvi.curr_var()->get_position()), + cvi.curr_coef()); + break; + case Global_Var: { + Global_Var_ID g = cvi.curr_var()->get_global_var(); + Variable_ID v; + if (g->arity() == 0) + v = r.get_local(g); + else + v = r.get_local(g, cvi.curr_var()->function_of()); + h.update_coef(v, cvi.curr_coef()); + break; + } + default: + assert(false); + } } + h.update_const((*e2).get_const()); + + r.simplify(); + r.copy_names(R); + r.setup_names(); + return r; } - h.update_const((*e2).get_const()); - - r.simplify(); - r.copy_names(R); - r.setup_names(); - return r; } } } + } + + +// +// heavy lifting for code output for one leaf node +// + CG_outputRepr *leaf_print_repr(BoolSet<> active, + const std::map<int, + Relation> &guards, + CG_outputRepr *guard_repr, + const Relation &known, + int indent, + CG_outputBuilder *ocg, + const std::vector<int> &remap, + const std::vector<Relation> &xforms, + const std::vector<CG_outputRepr *> &stmts, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::vector<std::map<std::string, std::vector<CG_outputRepr *> > > unin) { + //fprintf(stderr, "\n\nleaf_print_repr()\n"); + + if (active.num_elem() == 0) + return NULL; + + CG_outputRepr *stmt_list = NULL; + for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) { + std::map<int, Relation>::const_iterator j = guards.find(*i); + if (j == guards.end() || Must_Be_Subset(copy(known), copy(j->second))) { + Relation mapping = Inverse(copy((xforms[remap[*i]]))); + mapping.simplify(); + mapping.setup_names(); + std::vector<std::string> loop_vars; + for (int k = 1; k <= mapping.n_out(); k++) + loop_vars.push_back(mapping.output_var(k)->name()); + + + std::vector<CG_outputRepr *> sList = output_substitutions(ocg, + mapping, + assigned_on_the_fly, + unin[*i]); + + stmt_list = ocg->StmtListAppend(stmt_list, + ocg->CreateSubstitutedStmt( + (guard_repr==NULL)?indent:indent+1, + stmts[remap[*i]]->clone(), + loop_vars, + sList)); + active.unset(*i); + } } -} + + if (stmt_list != NULL) { + if (active.num_elem() != 0) + stmt_list = ocg->StmtListAppend(stmt_list, + leaf_print_repr(active, + guards, + NULL, + known, + (guard_repr==NULL)?indent:indent+1, + ocg, + remap, + xforms, + stmts, + assigned_on_the_fly, + unin)); + + if (guard_repr == NULL) + return stmt_list; + else { + fprintf(stderr, "CG_utils.cc leaf_print_repr() CreateIf()\n"); + return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); + } + } + else { + Relation then_cond = + find_best_guard( + const_cast<std::map<int, Relation> &>(guards)[*(active.begin())], + active, guards); + + assert(!then_cond.is_obvious_tautology()); + Relation new_then_known = Intersection(copy(known), copy(then_cond)); + new_then_known.simplify(); + Relation else_cond = Complement(copy(then_cond)); + else_cond.simplify(); + Relation new_else_known = Intersection(copy(known), copy(else_cond)); + new_else_known.simplify(); + + BoolSet<> then_active(active.size()); + BoolSet<> else_active(active.size()); + BoolSet<> indep_active(active.size()); + std::map<int, Relation> then_guards, else_guards; + for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) { + Relation &r = const_cast<std::map<int, Relation> &>(guards)[*i]; + if (Must_Be_Subset(copy(r), copy(then_cond))) { + Relation r2 = Gist(copy(r), copy(then_cond), 1); + if (!r2.is_obvious_tautology()) + then_guards[*i] = r2; + then_active.set(*i); + } + else if (Must_Be_Subset(copy(r), copy(else_cond))) { + Relation r2 = Gist(copy(r), copy(else_cond), 1); + if (!r2.is_obvious_tautology()) + else_guards[*i] = r2; + else_active.set(*i); + } + else + indep_active.set(*i); + } + assert(!then_active.empty()); + + //Anand: adding support for Replacing substituted variables within + //Uninterpreted function symbols or global variables with arity > 0 here + //--begin + std::vector<std::pair<CG_outputRepr *, int> > aotf = assigned_on_the_fly; + + CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, aotf, + unin[*(active.begin())]); + if (else_active.empty() && indep_active.empty()) { + guard_repr = ocg->CreateAnd(guard_repr, new_guard_repr); + return leaf_print_repr(then_active, + then_guards, + guard_repr, + new_then_known, + indent, + ocg, + remap, + xforms, + stmts, + assigned_on_the_fly, + unin); + + + } + else if (else_active.empty() && !indep_active.empty()) { + int new_indent = (guard_repr==NULL)?indent:indent+1; + stmt_list = leaf_print_repr(then_active, + then_guards, + new_guard_repr, + new_then_known, + new_indent, + ocg, + remap, + xforms, + stmts, + assigned_on_the_fly, + unin); + + stmt_list = ocg->StmtListAppend(stmt_list, + leaf_print_repr(indep_active, + guards, + NULL, + known, + new_indent, + ocg, + remap, + xforms, + stmts, + assigned_on_the_fly, + unin)); + + if (guard_repr == NULL) + return stmt_list; + else { + fprintf(stderr, "CG_utils.cc leaf_print_repr() CreateIf() 2\n"); + return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); + } + } + else { // (!else_active.empty()) + int new_indent = (guard_repr==NULL)?indent:indent+1; + + CG_outputRepr *then_stmt_list = leaf_print_repr(then_active, + then_guards, + NULL, + new_then_known, + new_indent+1, + ocg, + remap, + xforms, + stmts, + assigned_on_the_fly, + unin); + + CG_outputRepr *else_stmt_list = leaf_print_repr(else_active, + else_guards, + NULL, + new_else_known, + new_indent+1, + ocg, + remap, + xforms, + stmts, + assigned_on_the_fly, + unin); + + fprintf(stderr, "CG_utils.cc leaf_print_repr() CreateIf() 3\n"); + stmt_list = ocg->CreateIf(new_indent, + new_guard_repr, + then_stmt_list, + else_stmt_list); + + if (!indep_active.empty()) + stmt_list = ocg->StmtListAppend(stmt_list, + leaf_print_repr(indep_active, + guards, + NULL, + known, + new_indent, + ocg, + remap, + xforms, + stmts, + assigned_on_the_fly, + unin)); + + if (guard_repr == NULL) + return stmt_list; + else { + fprintf(stderr, "CG_utils.cc leaf_print_repr() CreateIf() 4\n"); + return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); + } + } + } + } + + + + + + std::string print_to_iegen_string(Relation &R) { + std::string s = ""; + for (GEQ_Iterator e(R.single_conjunct()->GEQs()); e; e++) { + if (s != "") + s += " && "; + s += (*e).print_to_string(); + } + + for (EQ_Iterator e(R.single_conjunct()->EQs()); e; e++) { + if (s != "") + s += " && "; + s += (*e).print_to_string(); + } + return s; + } + // -// heavy lifting for code output for one leaf node +// Check if a set/input var is projected out of a inequality by a global variable with arity > 0 // -CG_outputRepr *leaf_print_repr(BoolSet<> active, const std::map<int, Relation> &guards, - CG_outputRepr *guard_repr, const Relation &known, - int indent, CG_outputBuilder *ocg, const std::vector<int> &remap, - const std::vector<Relation> &xforms, const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - if (active.num_elem() == 0) - return NULL; - - CG_outputRepr *stmt_list = NULL; - for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) { - std::map<int, Relation>::const_iterator j = guards.find(*i); - if (j == guards.end() || Must_Be_Subset(copy(known), copy(j->second))) { - Relation mapping = Inverse(copy((xforms[remap[*i]]))); - mapping.simplify(); - mapping.setup_names(); - std::vector<std::string> loop_vars; - for (int k = 1; k <= mapping.n_out(); k++) { - loop_vars.push_back(mapping.output_var(k)->name()); -// std::cout << "CG_Utils:: " << k << ", " << mapping.output_var(k)->name().c_str() << "\n"; + Relation checkAndRestoreIfProjectedByGlobal(const Relation &R1, + const Relation &R2, Variable_ID v) { + + Relation to_return(R2.n_set()); + +//1. detect if a variable is not involved in a GEQ. + for (DNF_Iterator di(copy(R1).query_DNF()); di; di++) + for (GEQ_Iterator ci = (*di)->GEQs(); ci; ci++) + if ((*ci).get_coef(v) != 0) + return copy(R2); + + bool found_global_eq = false; + Global_Var_ID g1; + EQ_Handle e; +//2. detect if its involved in an eq involving a global with arity >= 1 + for (DNF_Iterator di(copy(R1).query_DNF()); di; di++) + for (EQ_Iterator ci = (*di)->EQs(); ci; ci++) + if ((*ci).get_coef(v) != 0) + for (Constr_Vars_Iter cvi(*ci); cvi; cvi++) { + v = cvi.curr_var(); + if (v->kind() == Global_Var) + if (v->get_global_var()->arity() > 0) { + found_global_eq = true; + g1 = v->get_global_var(); + e = (*ci); + } + } + + if (!found_global_eq) + return copy(R2); + +//3. check if the global is involved in a geq + + bool found_global_lb = false; + bool found_global_ub = false; + + std::vector<GEQ_Handle> ub; + std::vector<GEQ_Handle> lb; + for (DNF_Iterator di(copy(R1).query_DNF()); di; di++) + for (GEQ_Iterator ci = (*di)->GEQs(); ci; ci++) + for (Constr_Vars_Iter cvi(*ci); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); + if (v->kind() == Global_Var) + if (v->get_global_var()->arity() > 0 + && v->get_global_var() == g1) { + if (cvi.curr_coef() > 0) { + found_global_lb = true; + + lb.push_back(*ci); + } + else if (cvi.curr_coef() < 0) { + found_global_ub = true; + + ub.push_back(*ci); + } + + } + } + + if (!found_global_lb || !found_global_ub) + return copy(R2); + +// + + F_And *root = to_return.add_and(); + + for (int i = 0; i < lb.size(); i++) { + GEQ_Handle lower = root->add_GEQ(); + for (Constr_Vars_Iter cvi(lb[i]); cvi; cvi++) { + Variable_ID v2 = cvi.curr_var(); + + if (v2->kind() == Wildcard_Var) + return copy(R2); + if (v2->kind() != Global_Var + || (v2->kind() == Global_Var && v2->get_global_var() != g1)) { + if (v2->kind() != Global_Var) + lower.update_coef(v2, cvi.curr_coef()); + else { + Variable_ID lb1 = to_return.get_local(v2->get_global_var(), + Input_Tuple); + lower.update_coef(lb1, cvi.curr_coef()); + } + + } + else + lower.update_coef(v, cvi.curr_coef()); } - std::vector<CG_outputRepr *> sList = output_substitutions(ocg, mapping, assigned_on_the_fly); - stmt_list = ocg->StmtListAppend(stmt_list, ocg->CreateSubstitutedStmt((guard_repr==NULL)?indent:indent+1, stmts[remap[*i]]->clone(), loop_vars, sList)); - active.unset(*i); + + lower.update_const(lb[i].get_const()); } + + for (int i = 0; i < ub.size(); i++) { + GEQ_Handle upper = root->add_GEQ(); + for (Constr_Vars_Iter cvi(ub[i]); cvi; cvi++) { + Variable_ID v2 = cvi.curr_var(); + + if (v2->kind() == Wildcard_Var) + return copy(R2); + if (v2->kind() != Global_Var + || (v2->kind() == Global_Var && v2->get_global_var() != g1)) { + if (v2->kind() != Global_Var) + upper.update_coef(v2, cvi.curr_coef()); + else { + Variable_ID ub1 = to_return.get_local(v2->get_global_var(), + Input_Tuple); + upper.update_coef(ub1, cvi.curr_coef()); + } + + } + else + upper.update_coef(v, cvi.curr_coef()); + } + + upper.update_const(ub[i].get_const()); + } + +//Relation to_return2 = copy(R2); + + for (EQ_Iterator g(const_cast<Relation &>(R2).single_conjunct()->EQs()); g; + g++) + to_return.and_with_EQ(*g); + + for (GEQ_Iterator g(const_cast<Relation &>(R2).single_conjunct()->GEQs()); + g; g++) { + bool found_glob = false; + for (Constr_Vars_Iter cvi(*g); cvi; cvi++) { + Variable_ID v2 = cvi.curr_var(); + if (v2->kind() == Global_Var && v2->get_global_var() == g1) { + found_glob = true; + break; + } + } + if (!found_glob) + to_return.and_with_GEQ(*g); + + } +//to_return.and_with_EQ(e); + + to_return.copy_names(copy(R2)); + to_return.setup_names(); + to_return.finalize(); + return to_return; } - - if (stmt_list != NULL) { - if (active.num_elem() != 0) - stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(active, guards, NULL, known, (guard_repr==NULL)?indent:indent+1, ocg, remap, xforms, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); +/*Relation addInequalitiesToRelation(const Relation &R, + std::vector<GEQ_Handle> &inequalities) { + Relation to_return(R.n_set()); + + return to_return; } - else { - Relation then_cond = find_best_guard(const_cast<std::map<int, Relation> &>(guards)[*(active.begin())], active, guards); + +*/ + + + + + +// +// heavy lifting for code output for one level of loop nodes +// + CG_outputRepr *loop_print_repr(BoolSet<> active, + const std::vector<CG_loop *> &loops, + int start, + int end, + const Relation &guard, + CG_outputRepr *guard_repr, + int indent, + const std::vector<int> &remap, + const std::vector<Relation> &xforms, + CG_outputBuilder *ocg, + const std::vector<CG_outputRepr *> &stmts, + const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, + std::vector<std::map<std::string, std::vector<CG_outputRepr *> > > unin) { + + fprintf(stderr, "loop_print_repr() guard_repr "); + if (guard_repr == NULL) fprintf(stderr, "NULL\n"); + else fprintf(stderr, "NOT NULL\n"); + + if (start >= end) + return NULL; + + Relation R = Gist(copy(loops[start]->guard_), copy(guard), 1); + if (Must_Be_Subset(Intersection(copy(loops[start]->known_), copy(guard)), + copy(R))) { + int new_indent = (guard_repr==NULL)?indent:indent+1; + int i = start+1; + for ( ; i < end; i++) + if (!Gist(copy(loops[i]->guard_), copy(guard), 1).is_obvious_tautology()) + break; + CG_outputRepr *stmt_list = NULL; + for (int j = start; j < i; j++) + stmt_list = ocg->StmtListAppend(stmt_list, + loops[j]->printRepr(false, + new_indent, + ocg, + stmts, + assigned_on_the_fly, + unin)); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive\n"); + stmt_list = ocg->StmtListAppend(stmt_list, + loop_print_repr(active, + loops, + i, + end, + guard, + NULL, + new_indent, + remap, + xforms, + ocg, + stmts, + assigned_on_the_fly, + unin)); + + //fprintf(stderr, "guard_repr 0x%x\n", guard_repr); + if (guard_repr == NULL) + return stmt_list; + else { + fprintf(stderr, "CG_utils.cc loop_print_repr() CreateIf()\n"); + return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); + } + } + + Relation then_cond = find_best_guard(R, loops, start, end); + fprintf(stderr, "then_cond "); then_cond.print(stderr); assert(!then_cond.is_obvious_tautology()); - Relation new_then_known = Intersection(copy(known), copy(then_cond)); - new_then_known.simplify(); Relation else_cond = Complement(copy(then_cond)); else_cond.simplify(); - Relation new_else_known = Intersection(copy(known), copy(else_cond)); - new_else_known.simplify(); - BoolSet<> then_active(active.size()), else_active(active.size()), indep_active(active.size()); - std::map<int, Relation> then_guards, else_guards; - for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) { - Relation &r = const_cast<std::map<int, Relation> &>(guards)[*i]; - if (Must_Be_Subset(copy(r), copy(then_cond))) { - Relation r2 = Gist(copy(r), copy(then_cond), 1); - if (!r2.is_obvious_tautology()) - then_guards[*i] = r2; - then_active.set(*i); - } - else if (Must_Be_Subset(copy(r), copy(else_cond))) { - Relation r2 = Gist(copy(r), copy(else_cond), 1); - if (!r2.is_obvious_tautology()) - else_guards[*i] = r2; - else_active.set(*i); - } - else - indep_active.set(*i); - } - assert(!then_active.empty()); + std::vector<CG_loop *> then_loops, else_loops, indep_loops; + int i = start; + for ( ; i < end; i++) + if (!Must_Be_Subset(copy(loops[i]->guard_), copy(then_cond))) + break; + int j = i; + for ( ; j < end; j++) + if (!Must_Be_Subset(copy(loops[j]->guard_), copy(else_cond))) + break; + assert(i>start); - CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, assigned_on_the_fly); - if (else_active.empty() && indep_active.empty()) { + //Anand: adding support for Replacing substituted variables within + //Uninterpreted function symbols or global variables with arity > 0 here + //--begin + std::vector<std::pair<CG_outputRepr *, int> > aotf = assigned_on_the_fly; + CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, aotf, unin[*(active.begin())]); + + //fprintf(stderr, "new_guard_repr 0x%x\n", new_guard_repr); + if (j == i && end == j) { guard_repr = ocg->CreateAnd(guard_repr, new_guard_repr); - return leaf_print_repr(then_active, then_guards, guard_repr, new_then_known, indent, ocg, remap, xforms, stmts, assigned_on_the_fly); + Relation new_guard = Intersection(copy(guard), copy(then_cond)); + new_guard.simplify(); + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 2\n"); + return loop_print_repr(active, loops, start, end, new_guard, guard_repr, + indent, remap, xforms, ocg, stmts, aotf, unin); } - else if (else_active.empty() && !indep_active.empty()) { + else if (j == i && end > j) { int new_indent = (guard_repr==NULL)?indent:indent+1; - stmt_list = leaf_print_repr(then_active, then_guards, new_guard_repr, new_then_known, new_indent, ocg, remap, xforms, stmts, assigned_on_the_fly); - stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(indep_active, guards, NULL, known, new_indent, ocg, remap, xforms, stmts, assigned_on_the_fly)); + Relation new_guard = Intersection(copy(guard), copy(then_cond)); + new_guard.print(stderr); + new_guard.print_with_subs(stderr); + new_guard.simplify(); + new_guard.print(stderr); + new_guard.print_with_subs(stderr); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 3\n"); + CG_outputRepr *stmt_list = loop_print_repr(active, + loops, + start, + i, + new_guard, + new_guard_repr, + new_indent, + remap, + xforms, + ocg, + stmts, + aotf, + unin); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 4\n"); + stmt_list = ocg->StmtListAppend(stmt_list, + loop_print_repr(active, + loops, + j, + end, + guard, + NULL, + new_indent, + remap, + xforms, + ocg, + stmts, + aotf, + unin)); + if (guard_repr == NULL) return stmt_list; - else + else { + fprintf(stderr, "CG_utils.cc loop_print_repr() CreateIf() 2\n"); return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); + } } - else { // (!else_active.empty()) + else { // (j > i) int new_indent = (guard_repr==NULL)?indent:indent+1; - CG_outputRepr *then_stmt_list = leaf_print_repr(then_active, then_guards, NULL, new_then_known, new_indent+1, ocg, remap, xforms, stmts, assigned_on_the_fly); - CG_outputRepr *else_stmt_list = leaf_print_repr(else_active, else_guards, NULL, new_else_known, new_indent+1, ocg, remap, xforms, stmts, assigned_on_the_fly); - stmt_list = ocg->CreateIf(new_indent, new_guard_repr, then_stmt_list, else_stmt_list); - if (!indep_active.empty()) - stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(indep_active, guards, NULL, known, new_indent, ocg, remap, xforms, stmts, assigned_on_the_fly)); + Relation then_new_guard = Intersection(copy(guard), copy(then_cond)); + then_new_guard.simplify(); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 5\n"); + CG_outputRepr *then_stmt_list = loop_print_repr(active, + loops, + start, + i, + then_new_guard, + NULL, + new_indent+1, + remap, + xforms, + ocg, + stmts, + aotf, + unin); + + Relation else_new_guard = Intersection(copy(guard), copy(else_cond)); + else_new_guard.simplify(); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 6\n"); + CG_outputRepr *else_stmt_list = loop_print_repr(active, + loops, + i, + j, + else_new_guard, + NULL, + new_indent+1, + remap, + xforms, + ocg, + stmts, + aotf, + unin); + + fprintf(stderr, "CG_utils.cc loop_print_repr() CreateIf() 3\n"); + CG_outputRepr *stmt_list = ocg->CreateIf(new_indent, + new_guard_repr, + then_stmt_list, + else_stmt_list); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 7\n"); + stmt_list = ocg->StmtListAppend(stmt_list, + loop_print_repr(active, + loops, + j, + end, + guard, + NULL, + new_indent, + remap, + xforms, + ocg, + stmts, + aotf, + unin)); + + if (guard_repr == NULL) return stmt_list; - else + else { + fprintf(stderr, "CG_utils.cc loop_print_repr() CreateIf() 4\n"); return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); + } } } -} - - -// -// heavy lifting for code output for one level of loop nodes -// -CG_outputRepr *loop_print_repr(const std::vector<CG_loop *> &loops, int start, int end, - const Relation &guard, CG_outputRepr *guard_repr, - int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - if (start >= end) - return NULL; - - Relation R = Gist(copy(loops[start]->guard_), copy(guard), 1); - if (Must_Be_Subset(Intersection(copy(loops[start]->known_), copy(guard)), copy(R))) { - int new_indent = (guard_repr==NULL)?indent:indent+1; - int i = start+1; - for ( ; i < end; i++) - if (!Gist(copy(loops[i]->guard_), copy(guard), 1).is_obvious_tautology()) - break; - CG_outputRepr *stmt_list = NULL; - for (int j = start; j < i; j++) - stmt_list = ocg->StmtListAppend(stmt_list, loops[j]->printRepr(false, new_indent, ocg, stmts, assigned_on_the_fly)); - stmt_list = ocg->StmtListAppend(stmt_list, loop_print_repr(loops, i, end, guard, NULL, new_indent, ocg, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); - } - - Relation then_cond = find_best_guard(R, loops, start, end); - assert(!then_cond.is_obvious_tautology()); - Relation else_cond = Complement(copy(then_cond)); - else_cond.simplify(); - std::vector<CG_loop *> then_loops, else_loops, indep_loops; - int i = start; - for ( ; i < end; i++) - if (!Must_Be_Subset(copy(loops[i]->guard_), copy(then_cond))) - break; - int j = i; - for ( ; j < end; j++) - if (!Must_Be_Subset(copy(loops[j]->guard_), copy(else_cond))) - break; - assert(i>start); - - CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, assigned_on_the_fly); - if (j == i && end == j) { - guard_repr = ocg->CreateAnd(guard_repr, new_guard_repr); - Relation new_guard = Intersection(copy(guard), copy(then_cond)); - new_guard.simplify(); - return loop_print_repr(loops, start, end, new_guard, guard_repr, indent, ocg, stmts, assigned_on_the_fly); - } - else if (j == i && end > j) { - int new_indent = (guard_repr==NULL)?indent:indent+1; - Relation new_guard = Intersection(copy(guard), copy(then_cond)); - new_guard.simplify(); - CG_outputRepr *stmt_list = loop_print_repr(loops, start, i, new_guard, new_guard_repr, new_indent, ocg, stmts, assigned_on_the_fly); - stmt_list = ocg->StmtListAppend(stmt_list, loop_print_repr(loops, j, end, guard, NULL, new_indent, ocg, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); - } - else { // (j > i) - int new_indent = (guard_repr==NULL)?indent:indent+1; - Relation then_new_guard = Intersection(copy(guard), copy(then_cond)); - then_new_guard.simplify(); - CG_outputRepr *then_stmt_list = loop_print_repr(loops, start, i, then_new_guard, NULL, new_indent+1, ocg, stmts, assigned_on_the_fly); - Relation else_new_guard = Intersection(copy(guard), copy(else_cond)); - else_new_guard.simplify(); - CG_outputRepr *else_stmt_list = loop_print_repr(loops, i, j, else_new_guard, NULL, new_indent+1, ocg, stmts, assigned_on_the_fly); - CG_outputRepr *stmt_list = ocg->CreateIf(new_indent, new_guard_repr, then_stmt_list, else_stmt_list); - stmt_list = ocg->StmtListAppend(stmt_list, loop_print_repr(loops, j, end, guard, NULL, new_indent, ocg, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); - } -} - } |