diff options
Diffstat (limited to 'lib/codegen/src/CG.cc')
| -rwxr-xr-x[-rw-r--r--] | lib/codegen/src/CG.cc | 2790 |
1 files changed, 1664 insertions, 1126 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(); + } + } + } |