diff options
Diffstat (limited to 'omegalib/codegen/src')
| -rw-r--r-- | omegalib/codegen/src/CG.cc | 1163 | ||||
| -rw-r--r-- | omegalib/codegen/src/CG_roseBuilder.cc | 1533 | ||||
| -rw-r--r-- | omegalib/codegen/src/CG_roseRepr.cc | 125 | ||||
| -rw-r--r-- | omegalib/codegen/src/CG_stringBuilder.cc | 487 | ||||
| -rwxr-xr-x | omegalib/codegen/src/CG_utils.cc | 1735 | ||||
| -rwxr-xr-x | omegalib/codegen/src/codegen.cc | 378 | ||||
| -rw-r--r-- | omegalib/codegen/src/rose_attributes.cc | 183 |
7 files changed, 5604 insertions, 0 deletions
diff --git a/omegalib/codegen/src/CG.cc b/omegalib/codegen/src/CG.cc new file mode 100644 index 0000000..42bd172 --- /dev/null +++ b/omegalib/codegen/src/CG.cc @@ -0,0 +1,1163 @@ +/***************************************************************************** + Copyright (C) 1994-2000 the Omega Project Team + Copyright (C) 2005-2011 Chun Chen + All Rights Reserved. + + Purpose: + CG node classes, used to build AST tree from polyhedra scanning. + + Notes: + Parameter "restriction" is always tighter than "known" since CG_split + node does not correspond to any code for enforcement. This property is + destroyed after hoistGuard since "restriction" is not used anymore. + CG node's children are guaranteed not to be NULL, either NULL child is + removed from the children or the parent node itself becomes NULL. + + History: + 04/20/96 printRepr added by D people. Lei Zhou + 10/24/06 hoistGuard added by chun + 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> +#include <omega.h> +#include <code_gen/codegen.h> +#include <code_gen/CG.h> +#include <code_gen/CG_outputBuilder.h> +#include <code_gen/CG_stringBuilder.h> +#include <code_gen/CG_utils.h> +#include <code_gen/codegen_error.h> +#include <stack> +#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); + } + + + 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(); + } +} + +} diff --git a/omegalib/codegen/src/CG_roseBuilder.cc b/omegalib/codegen/src/CG_roseBuilder.cc new file mode 100644 index 0000000..eb16830 --- /dev/null +++ b/omegalib/codegen/src/CG_roseBuilder.cc @@ -0,0 +1,1533 @@ +/***************************************************************************** + Copyright (C) 2008 University of Southern California + Copyright (C) 2009-2010 University of Utah + All Rights Reserved. + + Purpose: + generate suif code for omega + + Notes: + + History: + 02/01/06 created by Chun Chen + *****************************************************************************/ + +#include <stack> +#include <code_gen/CG_roseBuilder.h> +#include <string> + +struct ir_error: public std::runtime_error { + ir_error(const std::string &msg) : + std::runtime_error(msg) { + } +}; + +using namespace SageBuilder; +using namespace SageInterface; +using namespace OmpSupport; + +namespace omega { + +//----------------------------------------------------------------------------- +// make suif initilization happy +//----------------------------------------------------------------------------- +char *k_ocg_comment; + +// void __attribute__ ((constructor)) my_init(void) { +// ANNOTE(k_ocg_comment, "omega_comment", TRUE); +// } + +/* + const char *libcode_gen_ver_string = ""; + const char *libcode_gen_who_string = ""; + const char *libcode_gen_suif_string = ""; + + void init_code_gen(int&, char* []) { + ANNOTE(k_ocg_comment, "omega_comment", TRUE); + } + + void exit_code_gen(void) { + } + */ +CG_roseBuilder::CG_roseBuilder(int is_fortran, SgGlobal* global, SgGlobal* firstScope, + SgSymbolTable* symtab, SgSymbolTable* symtab2, SgNode* root) : + isFortran(is_fortran), global_(global), global_scope(firstScope), symtab_(symtab), symtab2_( + symtab2), root_(root) { +} + + +CG_roseBuilder::~CG_roseBuilder() { +} + +// Manu:: returns true if input is in fortran, else returns false +bool CG_roseBuilder::isInputFortran() const{ + if (isFortran) + return true; + else + return false; +} + +//----------------------------------------------------------------------------- +// place holder generation +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateSubstitutedStmt(int, CG_outputRepr *stmt, + const std::vector<std::string> &vars, std::vector<CG_outputRepr*> &subs) const { + + SgStatementPtrList* list = static_cast<CG_roseRepr *>(stmt)->list_; + SgNode *tnl; + SgStatement* statement; + if (list != NULL) { + //statement = *((*list).begin()); + //tnl = isSgNode(statement); + delete stmt; + for (int i = 0; i < subs.size(); i++) { + if (subs[i] == NULL) + continue; + + CG_roseRepr *repr = static_cast<CG_roseRepr*>(subs[i]); + SgExpression* op = repr->op_; + + for (SgStatementPtrList::iterator it = (*list).begin(); + it != (*list).end(); it++) { + statement = (*it); + tnl = isSgNode(statement); + + // std::string master = tnl->unparseToString(); + + int j; + int not_in_symtab_; + + not_in_symtab_ = 0; + + SgVariableSymbol *vs = symtab_->find_variable( + SgName(vars[i].c_str())); + + if (vs == NULL) { + + not_in_symtab_ = 1; + + vs = symtab2_->find_variable(SgName(vars[i].c_str())); + } + if (vs != NULL) { + //std::string x = vars[i].c_str() ; + //std::string y = isSgNode(op)->unparseToString(); + + std::vector<SgVarRefExp *> array = substitute(tnl, + (const SgVariableSymbol*) vs, op, root_); + for (std::vector<SgVarRefExp *>::iterator it = + array.begin(); it != array.end(); it++) { + + // std::string z = isSgNode(array[j])->unparseToString(); + if (isSgVarRefExp(op)) { + if (strcmp( + isSgVarRefExp(op)->get_symbol()->get_name().getString().c_str(), + vs->get_name().getString().c_str())) { + + (*it)->set_symbol( + isSgVarRefExp(op)->get_symbol()); + // std::string z = isSgNode(array[j])->unparseToString(); + + // isSgBinaryOp(array[j]->get_parent())->replace_expression(array[j], op); + + } + } else if (isSgExpression(op)) { + + if (isSgBinaryOp((*it)->get_parent())) + isSgBinaryOp((*it)->get_parent())->replace_expression( + *it, op); + else if (isSgUnaryOp((*it)->get_parent())) + isSgUnaryOp((*it)->get_parent())->replace_expression( + *it, op); + else if (isSgExprListExp((*it)->get_parent())) + isSgExprListExp((*it)->get_parent())->replace_expression( + *it, op); + else + throw ir_error("unrecognized expression type"); + } + + } + /* std::vector<SgVarRefExp *> array2 = substitute (tnl,(const SgVariableSymbol*) vs, op, root_); + if(array2.size() != 0) + throw ir_error("variable replacement unsuccessful"); + */ + } + + } + + delete repr; + subs[i] = NULL; + + if (subs[i] != NULL) + throw ir_error("not freed properly"); + + } + + return new CG_roseRepr(list); + + } else { + tnl = static_cast<CG_roseRepr *>(stmt)->tnl_; + //std::string master = tnl->unparseToString(); + + if (tnl == NULL) + throw ir_error("both list and tnl are null!!"); + + delete stmt; + int j; + int not_in_symtab_; + for (int i = 0; i < subs.size(); i++) { + if (subs[i] == NULL) + continue; + not_in_symtab_ = 0; + + + CG_roseRepr *repr = static_cast<CG_roseRepr*>(subs[i]); + SgExpression* op = repr->op_; + delete repr; + subs[i] = NULL; + + SgVariableSymbol *vs = symtab_->find_variable( + SgName(vars[i].c_str())); + + if (vs == NULL) { + + not_in_symtab_ = 1; + + vs = symtab2_->find_variable(SgName(vars[i].c_str())); + } + if (vs != NULL) { + //std::string x = vars[i].c_str() ; + //std::string y = isSgNode(op)->unparseToString(); + std::vector<SgVarRefExp *> array = substitute(tnl, vs, op, + root_); + + if (not_in_symtab_ && isSgVarRefExp(op)) { + if (strcmp( + isSgVarRefExp(op)->get_symbol()->get_name().getString().c_str(), + vs->get_name().getString().c_str())) { + // symtab2_->remove(vs); + } + } + /* else if(not_in_symtab_ && isSgVarRefExp(isSgAddOp(op)->get_lhs_operand())){ + if(strcmp(isSgVarRefExp(isSgAddOp(op)->get_lhs_operand())->get_symbol()->get_name().getString().c_str(),\ + vs->get_name().getString().c_str())){ + symtab2_->remove(vs); + } + }*/ + //symtab2_->remove(vs); + for (std::vector<SgVarRefExp *>::iterator j = array.begin(); + j != array.end(); j++) { + // std::string z = isSgNode(array[j])->unparseToString(); + + if (isSgVarRefExp(op)) { + if (strcmp( + isSgVarRefExp(op)->get_symbol()->get_name().getString().c_str(), + vs->get_name().getString().c_str())) { + (*j)->set_symbol(isSgVarRefExp(op)->get_symbol()); + //isSgBinaryOp(array[j]->get_parent())->replace_expression(array[j], op); + // std::string z = isSgNode(array[j])->unparseToString(); + + } + } else if (isSgExpression(op)) { + + if (isSgBinaryOp((*j)->get_parent())) + isSgBinaryOp((*j)->get_parent())->replace_expression( + *j, op); + else if (isSgUnaryOp((*j)->get_parent())) + isSgUnaryOp((*j)->get_parent())->replace_expression( + *j, op); + else if (isSgExprListExp((*j)->get_parent())) { // Manu:: fortran indices are stored this way + isSgExprListExp((*j)->get_parent())->replace_expression(*j, op); + } + else + throw ir_error("unrecognized expression type"); + /* if(strcmp(isSgVarRefExp(isSgAddOp(op)->get_lhs_operand())->get_symbol()->get_name().getString().c_str(),\ + vs->get_name().getString().c_str() )){ + array[j]->set_symbol(isSgVarRefExp(isSgAddOp(op)->get_lhs_operand())->get_symbol()); + + */ + + } + + } + /* std::vector<SgVarRefExp *> array2 = substitute (tnl,(const SgVariableSymbol*) vs, op, root_); + if(array2.size() != 0) + throw ir_error("variable replacement unsuccessful"); + */ + } + /* SgExpression* exp = NULL; + + if(stmt1 = isSgStatement(tnl)){ + if (SgExprStatement* expr_stmt = isSgExprStatement(stmt1)) + exp = expr_stmt->get_expression(); + else if( block = isSgBasicBlock(tnl)){ + SgStatementPtrList& stmts = block->get_statements(); + SgExpression* exp2; + for(int i =0; i < stmts.size(); i++){ + if(isSgExprStatement(stmts[i])){ + exp2 = isSgExprStatement(stmts[i])->get_expression(); + if(exp2 != NULL){ + + if(isSgBinaryOp(exp2)) { + substitute(isSgBinaryOp(exp2)->get_lhs_operand(), vs, op, root_, exp2); + substitute(isSgBinaryOp(exp2)->get_rhs_operand(), vs, op, root_, exp2); + } + else if (isSgUnaryOp(exp2)) + substitute(isSgUnaryOp(exp2)->get_operand(), vs, op, root_, exp2); + + + }//end if + + }//end if + }//end for + + }//end else + else if(SgForStatement* for_stmt = isSgForStatement(tnl)){ + SgForStatement* temp = for_stmt; + while(isSgForStatement(temp)){ + + + + } + + + + + } + + + }//end if + else + exp = isSgExpression(tnl); + + if(exp != NULL){ + if(isSgBinaryOp(exp)) { + substitute(isSgBinaryOp(exp)->get_lhs_operand(), vs, op, root_, exp); + substitute(isSgBinaryOp(exp)->get_rhs_operand(), vs, op, root_, exp); + } + else if (isSgUnaryOp(exp)) + substitute(isSgUnaryOp(exp)->get_operand(), vs, op, root_, exp); + + } + // if (op.is_instr()) + // delete op.instr(); + } + */ + } + return new CG_roseRepr(tnl); + } + +} + +//----------------------------------------------------------------------------- +// assignment generation +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateAssignment(int, CG_outputRepr *lhs, + CG_outputRepr *rhs) const { + if (lhs == NULL || rhs == NULL) { + fprintf(stderr, "Code generation: Missing lhs or rhs\n"); + return NULL; + } + + SgExpression* src = static_cast<CG_roseRepr*>(rhs)->op_; + SgExpression* dst = static_cast<CG_roseRepr*>(lhs)->op_; + + SgExprStatement* ins = buildAssignStatement(dst, src); + src->set_parent(ins); + dst->set_parent(ins); + + SgStatementPtrList* new_list = new SgStatementPtrList; + + (*new_list).push_back(isSgStatement(ins)); + + delete lhs; + delete rhs; + + return new CG_roseRepr(new_list); + +} + +//----------------------------------------------------------------------------- +// function invocation generation +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateInvoke(const std::string &fname, + std::vector<CG_outputRepr *> &list) const { + + // Manu:: debug +// std::cout << "--------- CreateInvoke --------- \n"; + + if (fname == std::string("max") || fname == std::string("min")) { + if (list.size() == 0) { + return NULL; + } else if (list.size() == 1) { + return list[0]; + } else { + int last = list.size() - 1; + SgExpression* op2 = static_cast<CG_roseRepr*>(list[last])->op_; + delete list[last]; + list.erase(list.end()-1); + CG_roseRepr *repr = static_cast<CG_roseRepr*>(CreateInvoke(fname, + list)); + SgExpression* op1 = repr->op_; + + + SgExpression *ins; + SgExprListExp* arg_list = buildExprListExp(); + appendExpression(arg_list, op1); + appendExpression(arg_list, op2); + SgVarRefExp* opaque_var; + + + if (fname == std::string("max")) { + opaque_var = buildOpaqueVarRefExp("__rose_gt", global_); + ins = isSgExpression(buildFunctionCallExp(opaque_var, arg_list)); + + // Manu:: fortran support + if (isInputFortran()) { + SgName fName("merge"); + SgTypeInt *retType = buildIntType(); + + SgExpression *cond = static_cast<CG_roseRepr *>(CreateLE(new CG_roseRepr(op2), new CG_roseRepr(op1)))->op_; + appendExpression(arg_list, cond); + ins = isSgExpression(buildFunctionCallExp(fName, retType, arg_list, global_)); +// std::cout << "--------- CreateInvoke:: " << isSgNode(ins)->unparseToString().c_str() << "\n"; + } + + } else { + opaque_var = buildOpaqueVarRefExp("__rose_lt", global_); + ins = isSgExpression(buildFunctionCallExp(opaque_var, arg_list)); + + // Manu:: fortran support + if (isInputFortran()) { + SgName fName("merge"); + SgTypeInt *retType = buildIntType(); + + SgExpression *cond = static_cast<CG_roseRepr *>(CreateLE(new CG_roseRepr(op1), new CG_roseRepr(op2)))->op_; + appendExpression(arg_list, cond); + ins = isSgExpression(buildFunctionCallExp(fName, retType, arg_list, global_)); +// std::cout << "--------- CreateInvoke:: " << isSgNode(ins)->unparseToString().c_str() << "\n"; + } + + } + + repr->op_ = ins; + return repr; + } + } else { + fprintf(stderr, + "Code generation: invoke function io_call not implemented\n"); + return NULL; + } + +} + +//----------------------------------------------------------------------------- +// comment generation +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateComment(int, + const std::string &commentText) const { + if (commentText == std::string("")) { + return NULL; + } + + SgLocatedNode *tnl = new SgLocatedNode(); + buildComment(tnl, "//omega_comment: " + commentText); + + return new CG_roseRepr(isSgNode(tnl)); + +} + +//----------------------------------------------------------------------------- +// if stmt gen operations +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateIf(int, CG_outputRepr *guardList, + CG_outputRepr *true_stmtList, CG_outputRepr *false_stmtList) const { + + // static int if_counter = 1; + // std::string s = std::string("omegaif_")+to_string(if_counter++); + // SgLabelStatement* label =buildLabelStatement(SgName(const_cast<char *>(s.c_str()))); + + if (true_stmtList == NULL && false_stmtList == NULL) { + delete guardList; + return NULL; + } else if (guardList == NULL) { + return StmtListAppend(true_stmtList, false_stmtList); + } + + SgExpression* header = static_cast<CG_roseRepr*>(guardList)->op_; + + SgStatementPtrList *then_part1, *else_part1; + SgStatement* then_part; + SgStatement* else_part; + SgBasicBlock* then_part2; + SgBasicBlock* else_part2; + if (true_stmtList != NULL) { + then_part1 = static_cast<CG_roseRepr*>(true_stmtList)->list_; + if (then_part1 != NULL) { + then_part = *((*then_part1).begin()); + + if ((*then_part1).size() > 1) { + then_part2 = buildBasicBlock(); + for (SgStatementPtrList::iterator it = (*then_part1).begin(); + it != (*then_part1).end(); it++) { + then_part2->append_statement(*it); + + } + then_part = isSgStatement(then_part2); + + } + } else { + // Manu:: fortran support (if part) + if (isInputFortran()) { + then_part2 = buildBasicBlock(); + then_part2->append_statement(isSgStatement(static_cast<CG_roseRepr*>(true_stmtList)->tnl_)); + then_part = isSgStatement(then_part2); + } else + then_part = isSgStatement(static_cast<CG_roseRepr*>(true_stmtList)->tnl_); + } + } else { + then_part = NULL; + } + if (false_stmtList != NULL) { + else_part1 = static_cast<CG_roseRepr*>(false_stmtList)->list_; + if (else_part1 != NULL) { + else_part = *((*else_part1).begin()); + if ((*else_part1).size() > 1) { + else_part2 = buildBasicBlock(); + for (SgStatementPtrList::iterator it2 = (*else_part1).begin(); + it2 != (*else_part1).end(); it2++) { + else_part2->append_statement(*it2); + + } + else_part = isSgStatement(else_part2); + + } + } else { + // Manu:: fortran support (if part) + if (isInputFortran()) { + else_part2 = buildBasicBlock(); + else_part2->append_statement(isSgStatement(static_cast<CG_roseRepr*>(false_stmtList)->tnl_)); + else_part = isSgStatement(else_part2); + } else + else_part = isSgStatement(static_cast<CG_roseRepr*>(false_stmtList)->tnl_); + } + } else { + else_part = NULL; + } + + SgIfStmt* ti = buildIfStmt(header, isSgStatement(then_part), + isSgStatement(else_part)); + +// label->set_scope(ti);//may have to be shifted to after symbol table insertion +// SgLabelSymbol* if_label = isSgLabelSymbol(label->get_symbol_from_symbol_table()); + +// symtab_->insert( SgName(const_cast<char *>(s.c_str())) , isSgSymbol(if_label)); + + delete guardList; + delete true_stmtList; + delete false_stmtList; + + return new CG_roseRepr(isSgNode(ti)); + +} + +//----------------------------------------------------------------------------- +// inductive variable generation, to be used in CreateLoop as control +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateInductive(CG_outputRepr *index, + CG_outputRepr *lower, CG_outputRepr *upper, CG_outputRepr *step) const { + + if (index == NULL || lower == NULL || upper == NULL) { + fprintf(stderr, + "Code generation: something wrong in CreateInductive\n"); + return NULL; + } + + if (step == NULL) + step = new CG_roseRepr(isSgExpression(buildIntVal(1))); + + SgVarRefExp *index_sym = isSgVarRefExp( + static_cast<CG_roseRepr*>(index)->op_); + SgExpression* lower_bound = static_cast<CG_roseRepr*>(lower)->op_; + SgExpression* upper_bound = static_cast<CG_roseRepr*>(upper)->op_; + SgExpression* step_size = static_cast<CG_roseRepr*>(step)->op_; + + /* label_sym *contLabel = new label_sym(""); + label_sym *brkLabel = new label_sym(""); may not be required on rose?! + */ + + SgStatement* for_init_stmt = buildAssignStatement(index_sym, lower_bound); + SgLessOrEqualOp* cond = buildLessOrEqualOp(index_sym, upper_bound); + SgExprStatement* test = buildExprStatement(cond); + SgPlusAssignOp* increment = buildPlusAssignOp(index_sym, step_size); + SgForStatement *for_stmt = buildForStatement(for_init_stmt, + isSgStatement(test), increment, NULL); + + delete index; + delete lower; + delete upper; + delete step; + + + // Manu + if (isInputFortran()) { + // std::cout << "CG_roseBuilder:: need to construct a fortran do statement\n"; + SgFortranDo * forStmt=new SgFortranDo(Sg_File_Info::generateDefaultFileInfoForTransformationNode()); + forStmt->set_has_end_statement(true); + forStmt->set_bound(upper_bound); + forStmt->set_increment(step_size); + forStmt->set_initialization(isSgExprStatement(for_init_stmt)->get_expression()); + return new CG_roseRepr(isSgNode(forStmt)); + } else { +// std::cout << "CG_roseBuilder:: for statement is fine\n"; + + return new CG_roseRepr(isSgNode(for_stmt)); + + } + +} + +//----------------------------------------------------------------------------- +// Attribute Creation +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateAttribute(CG_outputRepr *control, + const std::string &commentText) const { + + SgNode *tnl = static_cast<CG_roseRepr*>(control)->tnl_; + + tnl->setAttribute("omega_comment", new AstTextAttribute(commentText)); + + return static_cast<CG_roseRepr*>(control); + +} + +//----------------------------------------------------------------------------- +// Pragma Attribute +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreatePragmaAttribute(CG_outputRepr *stmt, int looplevel, const std::string &pragmaText) const { + SgNode *tnl = static_cast<CG_roseRepr*>(stmt)->tnl_; + CodeInsertionAttribute* attr = NULL; + if (!tnl->attributeExists("code_insertion")) { + attr = new CodeInsertionAttribute(); + tnl->setAttribute("code_insertion", attr); + } + else { + attr = static_cast<CodeInsertionAttribute*>(tnl->getAttribute("code_insertion")); + } + attr->add(new PragmaInsertion(looplevel, pragmaText)); + return stmt; +} + +//----------------------------------------------------------------------------- +// Prefetch Attribute +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreatePrefetchAttribute(CG_outputRepr* stmt, int looplevel, const std::string &arrName, int hint) const { + SgNode *tnl = static_cast<CG_roseRepr*>(stmt)->tnl_; + CodeInsertionAttribute *attr = getOrCreateCodeInsertionAttribute(tnl); + attr->add(new MMPrefetchInsertion(looplevel, arrName, hint)); +} + +//----------------------------------------------------------------------------- +// loop stmt generation +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateLoop(int, CG_outputRepr *control, + CG_outputRepr *stmtList) const { + if (stmtList == NULL) { + delete control; + return NULL; + } else if (control == NULL) { + fprintf(stderr, "Code generation: no inductive for this loop\n"); + return stmtList; + } + + SgNode *tnl = static_cast<CG_roseRepr*>(control)->tnl_; + SgForStatement *tf = isSgForStatement(tnl); + + // Manu :: fortran support + SgFortranDo *tfd = NULL; + if (isInputFortran()) { + tfd = isSgFortranDo(tnl); + } + // Manu:: debug +/* if (!tf) { + std::cout << "CreateLoop:: Not a for loop\n"; + if (isSgFortranDo(tnl)) + std::cout << "CreateLoop:: It is a fortran do loop\n"; + } +*/ + + SgStatementPtrList * body = static_cast<CG_roseRepr*>(stmtList)->list_; + + if (body != NULL) { + if (!((*body).empty())) { + if ((*body).size() == 1) { + // if(isSgBasicBlock(*((*body).begin()))){ + if (!isInputFortran()) { // Manu:: added if-else for fortran support + tf->set_loop_body(*((*body).begin())); + (*((*body).begin()))->set_parent(tf); + } else { + SgBasicBlock* bb1 = buildBasicBlock(); + bb1->set_parent(tfd); + bb1->append_statement(*((*body).begin())); + tfd->set_body(bb1); + } + // } + /* else{ + SgBasicBlock* bb1 = buildBasicBlock(); + bb1->set_parent(tf); + bb1->append_statement(*((*body).begin())); + tf->set_loop_body(bb1); + + }*/ + } else { + // Manu:: support for fortran label (do - continue) + SgName *sname = NULL; + + SgBasicBlock* bb = buildBasicBlock(); + if (!isInputFortran()) + bb->set_parent(tf); + else + bb->set_parent(tfd); + for (SgStatementPtrList::iterator it = (*body).begin(); + it != (*body).end(); it++) { + bb->append_statement(*it); + (*it)->set_parent(bb); + } + if (!isInputFortran()) + tf->set_loop_body(bb); + else { + tfd->set_body(bb); + } + } + } + } else { + SgNode* tnl2 = static_cast<CG_roseRepr*>(stmtList)->tnl_; + + if (tnl2 != NULL) { + if (!isInputFortran()) { + tf->set_loop_body(isSgStatement(tnl2)); + tnl2->set_parent(tf); + } else { + SgBasicBlock* bb1 = buildBasicBlock(); + bb1->set_parent(tfd); + bb1->append_statement(isSgStatement(tnl2)); + tfd->set_body(bb1); + tnl2->set_parent(bb1); + } + } + } + + delete stmtList; + + return control; +} + +//----------------------------------------------------------------------------- +// basic int, identifier gen operations +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateInt(int _i) const { + return new CG_roseRepr(isSgExpression(buildIntVal(_i))); +} +bool CG_roseBuilder::isInteger(CG_outputRepr *op) const{ + + SgExpression *op1 = static_cast<CG_roseRepr *>(op)->op_; + + if(op1) + if(isSgIntVal(op1)) + return true; + + return false; +} +CG_outputRepr* CG_roseBuilder::CreateIdent(const std::string &_s) const { + + SgVariableSymbol *vs = symtab_->find_variable(SgName(_s.c_str())); + SgVariableSymbol *vs2 = symtab2_->find_variable(SgName(_s.c_str())); + + if (vs == NULL && vs2 == NULL) { + + SgVariableDeclaration* defn = buildVariableDeclaration( + SgName(_s.c_str()), buildIntType()); + SgInitializedNamePtrList& variables = defn->get_variables(); + SgInitializedNamePtrList::const_iterator i = variables.begin(); + SgInitializedName* initializedName = *i; + vs = new SgVariableSymbol(initializedName); + prependStatement(defn, isSgScopeStatement(root_)); + + vs->set_parent(symtab2_); + symtab2_->insert(SgName(_s.c_str()), vs); + return new CG_roseRepr(isSgExpression(buildVarRefExp(vs))); + + } + + /* May have problem */ + + if (!isSgExpression(buildVarRefExp(SgName(_s.c_str())))) + throw ir_error("error in Create ident!!"); + if (vs2 != NULL) + return new CG_roseRepr(isSgExpression(buildVarRefExp(vs2))); + + return new CG_roseRepr(isSgExpression(buildVarRefExp(vs))); + +} + +//----------------------------------------------------------------------------- +// binary arithmetic operations +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreatePlus(CG_outputRepr *lop, + CG_outputRepr *rop) const { + if (rop == NULL) { + return lop; + } else if (lop == NULL) { + return rop; + } + + SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; + SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; + + SgAddOp *ins = buildAddOp(op1, op2); + op1->set_parent(ins); + op2->set_parent(ins); + delete lop; + delete rop; + + return new CG_roseRepr(isSgExpression(ins)); + +} + +CG_outputRepr* CG_roseBuilder::CreateMinus(CG_outputRepr *lop, + CG_outputRepr *rop) const { + if (rop == NULL) { + return lop; /* May Cause Problem */ + } else if (lop == NULL) { + SgExpression *op = static_cast<CG_roseRepr*>(rop)->op_; + SgMinusOp *ins = buildMinusOp(op); + + delete rop; + + return new CG_roseRepr(isSgExpression(ins)); + } else { + SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; + SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; + + SgSubtractOp *ins = buildSubtractOp(op1, op2); + op1->set_parent(ins); + op2->set_parent(ins); + delete lop; + delete rop; + return new CG_roseRepr(isSgExpression(ins)); + } + +} + +CG_outputRepr* CG_roseBuilder::CreateTimes(CG_outputRepr *lop, + CG_outputRepr *rop) const { + if (rop == NULL || lop == NULL) { + if (rop != NULL) { + rop->clear(); + delete rop; + } + if (lop != NULL) { + lop->clear(); + delete lop; + } + return NULL; + } + + SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; + SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; + + SgMultiplyOp *ins = buildMultiplyOp(op1, op2); + op1->set_parent(ins); + op2->set_parent(ins); + delete lop; + delete rop; + + return new CG_roseRepr(isSgExpression(ins)); + +} + +CG_outputRepr* CG_roseBuilder::CreateIntegerFloor(CG_outputRepr *lop, + CG_outputRepr *rop) const { + if (rop == NULL) { + fprintf(stderr, "Code generation: divide by NULL\n"); + return NULL; + } else if (lop == NULL) { + delete rop; + return NULL; + } + + // (6+5)*10 / 4 + SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; + SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; + + // bugs in SUIF prevent use of correct io_divfloor + SgDivideOp *ins = buildDivideOp(op1, op2); + + delete lop; + delete rop; + + return new CG_roseRepr(isSgExpression(ins)); + +} + +CG_outputRepr* CG_roseBuilder::CreateIntegerMod(CG_outputRepr *lop, + CG_outputRepr *rop) const { + if (rop == NULL || lop == NULL) { + return NULL; + } + + SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; + SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; + + // bugs in SUIF prevent use of correct io_mod + SgModOp *ins; + if (!isInputFortran()) { + ins = buildModOp(op1, op2); + delete lop; + delete rop; + + return new CG_roseRepr(isSgExpression(ins)); + } else { // Manu:: fortran mod is a function call and not an operator (f77 and f90) + SgExpression *fins; + SgName fName("MOD"); + SgExprListExp* arg_list = buildExprListExp(); + appendExpression(arg_list, op1); + appendExpression(arg_list, op2); + SgTypeInt *retType = buildIntType(); + fins = isSgExpression(buildFunctionCallExp(fName, retType, arg_list, global_)); + return new CG_roseRepr(isSgExpression(fins)); + } + +} + +//----------------------------------------------------------------------------- +// binary logical operations +//----------------------------------------------------------------------------- +CG_outputRepr* CG_roseBuilder::CreateAnd(CG_outputRepr *lop, + CG_outputRepr *rop) const { + /*if (rop == NULL || lop == NULL) { + return NULL; + }*/ + + if (rop == NULL) + return lop; + else if (lop == NULL) + return rop; + + SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; + SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; + + SgAndOp *ins = buildAndOp(op1, op2); + + delete lop; + delete rop; + + return new CG_roseRepr(isSgExpression(ins)); + +} + +//----------------------------------------------------------------------------- +// binary relational operations +//----------------------------------------------------------------------------- +/*CG_outputRepr* CG_roseBuilder::CreateGE(CG_outputRepr *lop, + CG_outputRepr *rop) const { + return CreateLE(rop, lop); +}*/ + +CG_outputRepr* CG_roseBuilder::CreateLE(CG_outputRepr *lop, + CG_outputRepr *rop) const { + if (rop == NULL || lop == NULL) { + return NULL; + } + + SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; + SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; + + SgLessOrEqualOp *ins = buildLessOrEqualOp(op1, op2); + + delete lop; + delete rop; + + return new CG_roseRepr(isSgExpression(ins)); + +} + +CG_outputRepr* CG_roseBuilder::CreateEQ(CG_outputRepr *lop, + CG_outputRepr *rop) const { + if (rop == NULL || lop == NULL) { + return NULL; + } + + SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; + SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; + + SgEqualityOp *ins = buildEqualityOp(op1, op2); + + delete lop; + delete rop; + + return new CG_roseRepr(isSgExpression(ins)); + +} + +//----------------------------------------------------------------------------- +// stmt list gen operations +//----------------------------------------------------------------------------- +/*CG_outputRepr* CG_roseBuilder::CreateStmtList(CG_outputRepr *singleton) const { + + if (singleton == NULL) { + return new CG_roseRepr(new SgStatementPtrList); + } + + SgStatementPtrList *tnl = static_cast<CG_roseRepr *>(singleton)->list_; + SgNode* sgn = static_cast<CG_roseRepr *>(singleton)->tnl_; + + if (tnl == NULL) + tnl = new SgStatementPtrList; + + if (sgn == NULL) { + SgExpression* op = static_cast<CG_roseRepr *>(singleton)->op_; + + if (op != NULL) + (*tnl).push_back( + buildExprStatement( + static_cast<CG_roseRepr *>(singleton)->op_)); + + } else + (*tnl).push_back(isSgStatement(sgn)); + + delete singleton; + return new CG_roseRepr(tnl); + +// tnl = isSgNode(buildBasicBlock(buildExprStatement(static_cast<CG_roseRepr *>(singleton)->op_))); + +// delete singleton; +// return new CG_roseRepr(tnl); + +} + +CG_outputRepr* CG_roseBuilder::StmtListInsertLast(CG_outputRepr *list, + CG_outputRepr *node) const { + return StmtListAppend(list, node); +} +*/ +CG_outputRepr* CG_roseBuilder::StmtListAppend(CG_outputRepr *list1, + CG_outputRepr *list2) const { + + if (list2 == NULL) { + return list1; + } else if (list1 == NULL) { + return list2; + } + + // SgStatement* parent; + // SgStatement* stmt1; + // SgStatement* stmt2; + + SgStatementPtrList* new_list; + + SgStatementPtrList* tnl1 = static_cast<CG_roseRepr *>(list1)->list_; + SgStatementPtrList* tnl2 = static_cast<CG_roseRepr *>(list2)->list_; + SgNode* one = static_cast<CG_roseRepr *>(list1)->tnl_; + SgNode* two = static_cast<CG_roseRepr *>(list2)->tnl_; + + SgExpression* exp1 = static_cast<CG_roseRepr *>(list1)->op_; + SgExpression* exp2 = static_cast<CG_roseRepr *>(list2)->op_; + + if (exp1 || exp2) + throw ir_error("error in stmtlistappend!!"); + + if (tnl1 && one) + throw ir_error("error in stmtlistappend!!"); + + if (tnl2 && two) + throw ir_error("error in stmtlistappend!!"); +// SgNode* sg1 = static_cast<CG_roseRepr *>(list1)->tnl_; + +//if((*tnl1).empty()){ + +// if(SgStatement* stmt = isSgStatement(sg1)) +// (*tnl1).push_back(stmt); +//else if(isSgScopeStatement(sg1)){ +// SgStatementPtrList scopeStmtPtrLst = isSgScopeStatement(sg1)->generateStatementList(); + +// for(SgStatementPtrList::iterator it1 = scopeStmtPtrLst.begin();it1 != scopeStmtPtrLst.end(); it1++) +// (*tnl1).push_back(*it1); +//} +//} + + if ((tnl1 == NULL) && (tnl2 == NULL)) { + + if ((one != NULL) && (two != NULL)) { + + new_list = new SgStatementPtrList; + + (*new_list).push_back(isSgStatement(one)); + (*new_list).push_back(isSgStatement(two)); + + CG_roseRepr* new_rep = new CG_roseRepr(new_list); + + return static_cast<CG_outputRepr *>(new_rep); + + } else if ((one != NULL) && (two == NULL)) { + + return static_cast<CG_outputRepr *>(new CG_roseRepr(one)); + + } else if ((two != NULL) && (one == NULL)) { + return static_cast<CG_outputRepr *>(new CG_roseRepr(two)); + + } + + } else { + if ((tnl2 != NULL) && (tnl1 == NULL)) { + /* for(SgStatementPtrList::iterator it = (*tnl2).begin(); it != (*tnl2).end(); it++) + { + (*tnl1).push_back(*it); + + } + */ + if (one == NULL) + return list2; + else { + new_list = new SgStatementPtrList; + (*new_list).push_back(isSgStatement(one)); + + for (SgStatementPtrList::iterator it = (*tnl2).begin(); + it != (*tnl2).end(); it++) { + (*new_list).push_back(*it); + + } + //delete list2; + return static_cast<CG_outputRepr *>(new CG_roseRepr(new_list)); + } + } else if ((tnl1 != NULL) && (tnl2 == NULL)) { + if (two == NULL) + return list1; + else { + + (*tnl1).push_back(isSgStatement(two)); + // delete list1; + return static_cast<CG_outputRepr *>(new CG_roseRepr(tnl1)); + + } + + } else if ((tnl1 != NULL) && (tnl2 != NULL)) { + + for (SgStatementPtrList::iterator it = (*tnl2).begin(); + it != (*tnl2).end(); it++) { + (*tnl1).push_back(*it); + + } + + // delete list2; + // delete list1; + return static_cast<CG_outputRepr *>(new CG_roseRepr(tnl1)); + } +//else{ +// SgNode* tnll2 = static_cast<CG_roseRepr *>(list2)->tnl_; +// if(tnll2 != NULL){ +// if(isSgStatement(tnll2)) +// (*tnl1).push_back(isSgStatement(tnll2)); +// else if(isSgScopeStatement(tnll2)){ +// SgStatementPtrList scopeStmtPtrLst1 = isSgScopeStatement(tnll2)->generateStatementList(); + +// for(SgStatementPtrList::iterator it2 = scopeStmtPtrLst1.begin();it2 != scopeStmtPtrLst1.end(); it2++) +// (*tnl1).push_back(*it2); + +// } +//} +// else{ +// SgStatement* stmt2 = isSgStatement(buildExprStatement(static_cast<CG_roseRepr *>(list2)->op_)); +// (*tnl1).push_back(stmt2); + +// } + +//} + // stmt2 = isSgStatement(tnl2); + +// std::string c = tnl1->unparseToString(); + +// std::string d = isSgNode(stmt2)->unparseToString(); + +// if(isSgForStatement(tnl1) || isSgBasicBlock(tnl1)) +// isSgScopeStatement(tnl1)->append_statement(stmt2); +// else +// { + // stmt1 = isSgStatement(tnl1); + // parent = isSgStatement(tnl1->get_parent()); + // if(isSgForStatement(tnl1->get_parent()) || isSgBasicBlock(tnl1->get_parent())) + // isSgScopeStatement(tnl1->get_parent())->append_statement(stmt2); + // else if (isSgStatement(tnl1->get_parent())) + // isSgStatement(tnl1->get_parent())->insert_statement(stmt1, stmt2, false); + +// } + + } +// delete list2; + +// return list1; + +} + + +CG_outputRepr* CG_roseBuilder::CreateDim3(const char* varName, CG_outputRepr* arg1, + CG_outputRepr* arg2, CG_outputRepr* arg3) const { + + //SgName type_name("dim3"); + //SgClassSymbol * type_symbol = global_scope->lookup_class_symbol(type_name); + // SgClassDeclaration * type_decl = isSgClassDeclaration( + // type_symbol->get_declaration()); + + //SgVariableDeclaration * var_decl = buildVariableDeclaration(varName, type_symbol->get_type()); + + SgFunctionSymbol * ctor_symbol = global_scope->lookup_function_symbol( + SgName("dim3")); + + SgExprListExp * ctor_args; + if(arg3 != NULL) + ctor_args = buildExprListExp(static_cast<CG_roseRepr*>(arg1)->op_, + static_cast<CG_roseRepr*>(arg2)->op_, static_cast<CG_roseRepr*>(arg3)->op_); + else + ctor_args = buildExprListExp(static_cast<CG_roseRepr*>(arg1)->op_, + static_cast<CG_roseRepr*>(arg2)->op_); + SgFunctionCallExp * dim3_func_call = buildFunctionCallExp( + buildFunctionRefExp(ctor_symbol->get_declaration()), ctor_args); + + char joined_str[20]; + + strcpy(joined_str, "dim3 "); + strcat(joined_str, varName); + + SgExprStatement* decl = buildAssignStatement( + buildOpaqueVarRefExp(joined_str, isSgScopeStatement(root_)), + dim3_func_call); + + SgStatementPtrList *tnl2 = new SgStatementPtrList; + + // (*tnl2).push_back(var_decl); + (*tnl2).push_back(decl); + return new CG_roseRepr(tnl2); + +} + +/*CG_outputRepr* CG_roseBuilder::CreateDim3(const char* varName, int arg1, + int arg2) const { + + SgName type_name("dim3"); + SgClassSymbol * type_symbol = global_scope->lookup_class_symbol(type_name); + SgClassDeclaration * type_decl = isSgClassDeclaration( + type_symbol->get_declaration()); + + //SgVariableDeclaration * var_decl = buildVariableDeclaration(varName, type_symbol->get_type()); + + SgFunctionSymbol * ctor_symbol = global_scope->lookup_function_symbol( + SgName("dim3")); + + SgExprListExp * ctor_args = buildExprListExp(buildIntVal(arg1), + buildIntVal(arg2)); + + SgFunctionCallExp * dim3_func_call = buildFunctionCallExp( + buildFunctionRefExp(ctor_symbol->get_declaration()), ctor_args); + + char joined_str[20]; + + strcpy(joined_str, "dim3 "); + strcat(joined_str, varName); + + SgExprStatement* decl = buildAssignStatement( + buildOpaqueVarRefExp(joined_str, isSgScopeStatement(root_)), + dim3_func_call); + + SgStatementPtrList *tnl2 = new SgStatementPtrList; + + // (*tnl2).push_back(var_decl); + (*tnl2).push_back(decl); + return new CG_roseRepr(tnl2); +} + +CG_outputRepr* CG_roseBuilder::CreateDim3(const char* varName, int arg1, + int arg2, int arg3) const { + + SgName type_name("dim3"); + SgClassSymbol * type_symbol = global_scope->lookup_class_symbol(type_name); + SgClassDeclaration * type_decl = isSgClassDeclaration( + type_symbol->get_declaration()); + + //SgVariableDeclaration * var_decl = buildVariableDeclaration(varName, type_symbol->get_type()); + + SgFunctionSymbol * ctor_symbol = global_scope->lookup_function_symbol( + SgName("dim3")); + + SgExprListExp * ctor_args = buildExprListExp(buildIntVal(arg1), + buildIntVal(arg2), buildIntVal(arg3)); + + SgFunctionCallExp * dim3_func_call = buildFunctionCallExp( + buildFunctionRefExp(ctor_symbol->get_declaration()), ctor_args); + + char joined_str[20]; + + strcpy(joined_str, "dim3 "); + strcat(joined_str, varName); + + SgExprStatement* decl = buildAssignStatement( + buildOpaqueVarRefExp(joined_str, isSgScopeStatement(root_)), + dim3_func_call); + + SgStatementPtrList *tnl2 = new SgStatementPtrList; + + // (*tnl2).push_back(var_decl); + (*tnl2).push_back(decl); + return new CG_roseRepr(tnl2); + + + +} +*/ + +/*CG_outputRepr* CG_suifBuilder::CreateKernel(immed_list* iml) const { + instruction *ins = new in_rrr(io_mrk); + ins->append_annote(k_cuda_kernel, iml); + tree_node_list *tnl = new tree_node_list; + tnl->append(new tree_instr(ins)); + return new CG_suifRepr(tnl); + } + + type_node* CG_suifBuilder::ModifyType(type_node* base, const char* modifier) const { + modifier_type* result = new modifier_type(TYPE_NULL, base); + immed_list *iml = new immed_list; + iml->append(immed((char*)modifier)); + result->append_annote(k_cuda_modifier, iml); + return result; + } + */ + +std::vector<SgVarRefExp *> substitute(SgNode *in, const SgVariableSymbol *sym, + SgExpression* expr, SgNode* root) { + + SgStatement* stmt; + SgExpression* op; + std::vector<SgVarRefExp *> arrays; + + if (in != NULL) { + if (stmt = isSgStatement(in)) { + if (isSgBasicBlock(stmt)) { + SgStatementPtrList& stmts = + isSgBasicBlock(stmt)->get_statements(); + for (int i = 0; i < stmts.size(); i++) { + stmts[i]->set_parent(stmt); + std::vector<SgVarRefExp *> a = substitute( + isSgNode(stmts[i]), sym, expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + } + } else if (isSgForStatement(stmt)) { + SgForStatement *tnf = isSgForStatement(stmt); + tnf->get_for_init_stmt()->set_parent(tnf); + tnf->get_test()->set_parent(tnf); + tnf->get_increment()->set_parent(tnf); + tnf->get_loop_body()->set_parent(tnf); + std::vector<SgVarRefExp *> a = substitute( + isSgNode(tnf->get_for_init_stmt()), sym, expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + std::vector<SgVarRefExp *> a1 = substitute( + isSgNode(tnf->get_test()), sym, expr, root); + std::copy(a1.begin(), a1.end(), back_inserter(arrays)); + std::vector<SgVarRefExp *> a2 = substitute( + isSgNode(tnf->get_increment()), sym, expr, root); + std::copy(a2.begin(), a2.end(), back_inserter(arrays)); + std::vector<SgVarRefExp *> a3 = substitute( + isSgNode(tnf->get_loop_body()), sym, expr, root); + std::copy(a3.begin(), a3.end(), back_inserter(arrays)); + } else if (isSgFortranDo(stmt)) { // Manu:: fortran support + SgFortranDo *tnf = isSgFortranDo(stmt); + tnf->get_initialization()->set_parent(tnf); + tnf->get_bound()->set_parent(tnf); + tnf->get_increment()->set_parent(tnf); + tnf->get_body()->set_parent(tnf); + std::vector<SgVarRefExp *> a = substitute( + isSgNode(tnf->get_initialization()), sym, expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + std::vector<SgVarRefExp *> a1 = substitute( + isSgNode(tnf->get_bound()), sym, expr, root); + std::copy(a1.begin(), a1.end(), back_inserter(arrays)); + std::vector<SgVarRefExp *> a2 = substitute( + isSgNode(tnf->get_increment()), sym, expr, root); + std::copy(a2.begin(), a2.end(), back_inserter(arrays)); + std::vector<SgVarRefExp *> a3 = substitute( + isSgNode(tnf->get_body()), sym, expr, root); + std::copy(a3.begin(), a3.end(), back_inserter(arrays)); + } else if (isSgForInitStatement(stmt)) { + + SgStatementPtrList& stmts = + isSgForInitStatement(stmt)->get_init_stmt(); + + for (SgStatementPtrList::iterator it = stmts.begin(); + it != stmts.end(); it++) { + std::vector<SgVarRefExp *> a = substitute(isSgNode(*it), + sym, expr, root); + + std::copy(a.begin(), a.end(), back_inserter(arrays)); + } + } + /*else if(isSgFortranDo(stmt)){ + SgFortranDo *tfortran = isSgFortranDo(stmt); + omega::CG_roseRepr *r = new omega::CG_roseRepr(isSgStatement(tfortran->get_body())); + std::vector<IR_ArrayRef *> a = FindArrayRef(r); + delete r; + std::copy(a.begin(), a.end(), back_inserter(arrays)); + }*/ + else if (isSgVariableDeclaration(stmt)) { + if (SgExpression *init = + isSgVariableDeclaration(stmt)->get_variables().front()->get_initializer()) { + if (isSgAssignInitializer(init)) { + std::vector<SgVarRefExp *> a = substitute( + isSgAssignInitializer(init)->get_operand(), sym, + expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + } + } + } else if (isSgIfStmt(stmt)) { + SgIfStmt* tni = isSgIfStmt(stmt); + //tni->get_conditional()->set_parent(tni); + //tni->get_true_body()->set_parent(tni); + //tni->get_false_body()->set_parent(tni); + std::vector<SgVarRefExp *> a = substitute( + isSgNode(tni->get_conditional()), sym, expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + std::vector<SgVarRefExp *> a1 = substitute( + isSgNode(tni->get_true_body()), sym, expr, root); + std::copy(a1.begin(), a1.end(), back_inserter(arrays)); + std::vector<SgVarRefExp *> a2 = substitute( + isSgNode(tni->get_false_body()), sym, expr, root); + std::copy(a2.begin(), a2.end(), back_inserter(arrays)); + } else if (isSgExprStatement(stmt)) { + (isSgExprStatement(stmt)->get_expression())->set_parent( + isSgExprStatement(stmt)); + std::vector<SgVarRefExp *> a = substitute( + isSgNode(isSgExprStatement(stmt)->get_expression()), + sym, expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + } //end else if + } //end if + else { + op = isSgExpression(in); + // std::string x = isSgNode(op)->unparseToString(); + std::string y = sym->get_name().getString(); +// std::cout << "------substitute else:: " << in->unparseToString().c_str() << ", " << y.c_str() << "\n"; + + if (isSgBinaryOp(op)) { + + isSgBinaryOp(op)->get_lhs_operand()->set_parent(op); + isSgBinaryOp(op)->get_rhs_operand()->set_parent(op); + + std::vector<SgVarRefExp *> a = substitute( + isSgBinaryOp(op)->get_lhs_operand(), sym, expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + std::vector<SgVarRefExp *> a1 = substitute( + isSgBinaryOp(op)->get_rhs_operand(), sym, expr, root); + std::copy(a1.begin(), a1.end(), back_inserter(arrays)); + } else if (isSgUnaryOp(op)) { + //isSgUnaryOp(op)->get_operand()->set_parent(op); + //std::string x = isSgNode(op)->unparseToString(); + //std::cout<<x<<std::endl; + std::vector<SgVarRefExp *> a = substitute( + isSgUnaryOp(op)->get_operand(), sym, expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + } else if (isSgVarRefExp(op)) { + std::string z = + isSgVarRefExp(op)->get_symbol()->get_name().getString(); + if (!strcmp(z.c_str(), y.c_str())) { + //isSgVarRefExp(op)->set_symbol(isSgVarRefExp(expr)->get_symbol()); + arrays.push_back(isSgVarRefExp(op)); + //replaceVariableReferences(root, isSgVarRefExp(in)->get_symbol(), temp); + //r = true; + } //end if + } //end else if + else if (isSgCallExpression(op)) { + SgExprListExp* exprs = isSgCallExpression(op)->get_args(); + SgExpressionPtrList &expr_list = exprs->get_expressions(); + + for (SgExpressionPtrList::iterator it = expr_list.begin(); + it != expr_list.end(); it++) { + std::vector<SgVarRefExp *> a = substitute(isSgNode(*it), + sym, expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + } + } else if (isSgExprListExp(op)) { // Manu:: fortran indices are stored this way + SgExpressionPtrList &expr_list = isSgExprListExp(op)->get_expressions(); + + for (SgExpressionPtrList::iterator it = expr_list.begin(); + it != expr_list.end(); it++) { + std::vector<SgVarRefExp *> a = substitute(isSgNode(*it), + sym, expr, root); + std::copy(a.begin(), a.end(), back_inserter(arrays)); + } + + } + + //end else if + //else if(!isSgValueExp(op)) + // throw ir_error("unrecognized expression type"); + } //end else + } //end if + + /* bool r = false; + if (isSgVarRefExp(in) && (isSgVarRefExp(in)->get_symbol() == sym)) { + omega::CG_roseRepr *result = new omega::CG_roseRepr(expr); + SgExpression* expr1 = result->GetExpression(); + delete result; + SgVariableSymbol* temp = isSgVarRefExp(expr1)->get_symbol(); + parent->replace_expression(in, expr1); + replaceVariableReferences(root, isSgVarRefExp(in)->get_symbol(), temp); + r = true; + } + else if(isSgBinaryOp(in)){ + substitute(isSgBinaryOp(in)->get_lhs_operand(), sym, expr, root, in); + substitute(isSgBinaryOp(in)->get_rhs_operand(), sym, expr, root, in); + } + else if(isSgUnaryOp(in)) + substitute(isSgUnaryOp(in)->get_operand(), sym, expr, root, in); + + */ + + return arrays; +} + +/*bool substitute(SgStatement *tn, SgVariableSymbol *sym, SgExpression* expr, SgNode* root, SgSymbolTable* symtab) { + if (tn == NULL) + return false; + + bool r = false; + if( tn != NULL){ + if(isSgExpression(tn)){ + r = substitute(isSgExpression(tn), sym, expr, root, isSgExpression(tn)) || r; + + } + else { + omega::CG_roseRepr *result = new omega::CG_roseRepr(expr); + SgExpression* expr1 = result->GetExpression(); + tn->replace_expression(buildVarRefExp(sym), expr1); + for (unsigned i = 0; i < tn->get_numberOfTraversalSuccessors(); i++) + r = substitute(isSgStatement(tn->get_traversalSuccessorByIndex(i)), sym, expr, root, symtab) || r; + + } + } + return r; + } + + bool substitute(SgNode *tnl, SgVariableSymbol *sym, SgExpression* expr, SgNode* root, SgSymbolTable* symtab) { + if (tnl == NULL) + return false; + + bool r = false; + + for(int i=0; i < tnl->get_numberOfTraversalSuccessors(); i++){ + + SgNode* tn = tnl->get_traversalSuccessorByIndex(i); + r = substitute(isSgStatement(tn), sym, expr, root, symtab) || r; + } + + + return r; + } + */ + +} // namespace diff --git a/omegalib/codegen/src/CG_roseRepr.cc b/omegalib/codegen/src/CG_roseRepr.cc new file mode 100644 index 0000000..9265ab0 --- /dev/null +++ b/omegalib/codegen/src/CG_roseRepr.cc @@ -0,0 +1,125 @@ +/***************************************************************************** + Copyright (C) 2008 University of Southern California. + All Rights Reserved. + + Purpose: + omega holder for suif implementaion + + Notes: + + History: + 02/01/06 - Chun Chen - created +*****************************************************************************/ + +#include <code_gen/CG_roseRepr.h> +#include <code_gen/rose_attributes.h> +#include <stdio.h> +#include <string.h> +#include <cstring> +namespace omega { + + + + +CG_roseRepr::CG_roseRepr(): tnl_(NULL), op_(NULL), list_(NULL){ + +} + +CG_roseRepr::CG_roseRepr(SgNode *tnl): tnl_(tnl), op_(NULL),list_(NULL) { +} + +CG_roseRepr::CG_roseRepr(SgExpression* op): tnl_(NULL), op_(op),list_(NULL){ +} +CG_roseRepr::CG_roseRepr(SgStatementPtrList* stmtlist):tnl_(NULL), op_(NULL), list_(stmtlist){ +} + +CG_roseRepr::~CG_roseRepr() { + // delete nothing here. operand or tree_node_list should already be + // grafted to other expression tree or statement list +} + +CG_outputRepr* CG_roseRepr::clone() const { + + if( tnl_ != NULL) { + SgTreeCopy tc; + SgNode *tnl = tnl_->copy(tc); + copyAttributes(tnl_, tnl); + + tnl->set_parent(tnl_->get_parent()); + return new CG_roseRepr(tnl); + } + else if(op_ != NULL) + { + SgTreeCopy tc1; + SgNode* op = isSgNode(op_)->copy(tc1); + copyAttributes(op_, op); + + op->set_parent(isSgNode(op_)->get_parent()); + return new CG_roseRepr(isSgExpression(op)); + } + else if(list_ != NULL) + { + SgStatementPtrList* list2 = new SgStatementPtrList; + + for(SgStatementPtrList::iterator it = (*list_).begin(); it != (*list_).end(); it++){ + SgTreeCopy tc3; + SgNode *tnl2 = isSgNode(*it)->copy(tc3); + copyAttributes(*it, tnl2); + + tnl2->set_parent(isSgNode(*it)->get_parent()); + + (*list2).push_back(isSgStatement(tnl2)); + } + return new CG_roseRepr(list2); + } + + return NULL; +} + +void CG_roseRepr::clear() { + if(tnl_ != NULL) { + delete tnl_; + tnl_ = NULL; + } +} + +SgNode* CG_roseRepr::GetCode() const { + return tnl_; +} + +SgStatementPtrList* CG_roseRepr::GetList() const { + return list_; +} + +SgExpression* CG_roseRepr::GetExpression() const { + return op_; +} +void CG_roseRepr::Dump() const { +SgNode* tnl = tnl_; +SgExpression* op = op_ ; + if(tnl != NULL) + DumpFileHelper(tnl, stdout); + else if(op != NULL) + DumpFileHelper(isSgNode(op), stdout); + +} + +void CG_roseRepr::DumpFileHelper(SgNode* node, FILE *fp) const{ + std::string x; + size_t numberOfSuccessors = node->get_numberOfTraversalSuccessors(); + if(numberOfSuccessors == 0){ + x = node->unparseToString (); + fprintf(fp, "%s", x.c_str()); + } + else{ + for (size_t idx = 0; idx < numberOfSuccessors; idx++) + { + SgNode *child = NULL; + child = node->get_traversalSuccessorByIndex(idx); + DumpFileHelper(child, fp); + } + +} +} + +} // namespace diff --git a/omegalib/codegen/src/CG_stringBuilder.cc b/omegalib/codegen/src/CG_stringBuilder.cc new file mode 100644 index 0000000..2f9286f --- /dev/null +++ b/omegalib/codegen/src/CG_stringBuilder.cc @@ -0,0 +1,487 @@ +/***************************************************************************** + Copyright (C) 1994-2000 the Omega Project Team + Copyright (C) 2005-2011 Chun Chen + All Rights Reserved. + + Purpose: + generate pseudo string code + + Notes: + There is no need to check illegal NULL parameter and throw invalid_argument + 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 +*****************************************************************************/ + +#include <code_gen/CG_stringBuilder.h> +#include <code_gen/codegen_error.h> +#include <basic/util.h> +#include <string> +#include <stdexcept> +#include <ctype.h> +#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 '+': + 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 (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; +} + + +std::string GetIndentSpaces(int indent) { + std::string indentStr; + for (int i = 1; i < indent; i++) { + 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; +} + +} + + +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 += ","; + } + + 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_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); + + return new CG_stringRepr("// " + commentText + "\n" + controlString); + +} + +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::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); +} + + + +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; + } + + 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); + } + 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::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, '-')); +} + + +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, '*')); +} + + +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, '/')); +} + + +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 + ")"); +} + + +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 + ")"); +} + +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::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); +} + +} diff --git a/omegalib/codegen/src/CG_utils.cc b/omegalib/codegen/src/CG_utils.cc new file mode 100755 index 0000000..d3a5f71 --- /dev/null +++ b/omegalib/codegen/src/CG_utils.cc @@ -0,0 +1,1735 @@ +/***************************************************************************** + Copyright (C) 1994-2000 the Omega Project Team + Copyright (C) 2005-2011 Chun Chen + All Rights Reserved. + + Purpose: + 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 + 07/29/10 when translating equality to assignment, generate appropriate + if-condition when necesssary, -chun +*****************************************************************************/ + +#include <typeinfo> +#include <omega.h> +#include <code_gen/CG.h> +#include <code_gen/CG_utils.h> +#include <code_gen/codegen_error.h> +#include <math.h> +#include <stack> + +namespace omega { + +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()); + + 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()); + } + 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); + } + } + 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(); + 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; +} + + +// +// 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; + } + } + 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; + } + 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 (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: { + 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)))); + } + 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); + + 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"); + } + 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 { // 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)); + } + else { // coef < 0 + if (coef == -1) + repr = ocg->CreateMinus(repr, t); + else + repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); + } + } + } + + 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; +} + + +// +// 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 &) { + } + } + + subs.push_back(repr); + } + + 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) { + 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 ((*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 (!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 (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); +} + + +// +// 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; + 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; + 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()); +} + +// +// 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; + } + if (is_free) { + if (found_free) + is_stride = false; + else { + found_free = true; + stride_wc = cvi.curr_var(); + } + } + else { + std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var()); + if (result.first) + num_floor++; + else + is_stride = false; + } + break; + } + case Input_Var: + num_var++; + break; + default: + ; + } + + 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 (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)); + } + 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); + } + + // 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)); + } + 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); + } + 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(); + } + 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); + 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 (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); + } + + // 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; + } + 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); + } + 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)); + } + } + 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)); + } + } + 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); + } + } + + 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::set<Variable_ID> excluded_floor_vars) { + const_cast<Relation &>(R).setup_names(); // hack + + 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; + } + } + 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 { + 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)); + } + else { + if (coef == -1) + repr = ocg->CreateMinus(repr, t); + else + repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); + } + } + } + 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); + } + + 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)); + } + + 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; + + 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 (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); + } + 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))); + } + + } + } + + 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; + } + + 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); + + 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); + + 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; + } + 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(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); +} + + +// +// 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); + 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: + ; + } + + 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++) { + 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((*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; + } + } + } + } +} + + +// +// 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) { + 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"; + } + 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); + } + } + + 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); + } + 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()), 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()); + + CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, assigned_on_the_fly); + 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); + } + 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); + stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(indep_active, guards, NULL, known, new_indent, 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); + } + 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); + 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)); + if (guard_repr == NULL) + return stmt_list; + else + 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); + } +} + +} diff --git a/omegalib/codegen/src/codegen.cc b/omegalib/codegen/src/codegen.cc new file mode 100755 index 0000000..92ca702 --- /dev/null +++ b/omegalib/codegen/src/codegen.cc @@ -0,0 +1,378 @@ +/***************************************************************************** + Copyright (C) 1994-2000 the Omega Project Team + Copyright (C) 2005-2011 Chun Chen + All Rights Reserved. + + Purpose: + CodeGen class as entry point for code generation. + + Notes: + Loop variable name prefix should not cause any possible name conflicts + with original loop variables wrapped in statement holder. This guarantees + that variable substitution done correctly in the generated code. + + History: + 04/24/96 MMGenerateCode, added by Fortran D people. Lei Zhou + 09/17/08 loop overhead removal based on actual nesting depth -- by chun + 03/05/11 fold MMGenerateCode into CodeGen class, Chun Chen +*****************************************************************************/ + +#include <typeinfo> +#include <omega.h> +#include <basic/util.h> +#include <math.h> +#include <vector> +#include <algorithm> + +#include <code_gen/CG.h> +#include <code_gen/codegen.h> +#include <code_gen/CG_outputBuilder.h> +#include <code_gen/codegen_error.h> + +namespace omega { + +const std::string CodeGen::loop_var_name_prefix = "t"; +const int CodeGen::var_substitution_threshold = 10; + +//Anand--adding stuff to make Chun's code work with Gabe's +std::vector< std::vector<int> > smtNonSplitLevels; +std::vector< std::vector<std::string> > loopIdxNames;//per stmt +std::vector< std::pair<int, std::string> > syncs; + + + +CodeGen::CodeGen(const std::vector<Relation> &xforms, const std::vector<Relation> &IS, const Relation &known, std::vector< std::vector<int> > smtNonSplitLevels_ , std::vector< std::vector<std::string> > loopIdxNames_, std::vector< std::pair<int, std::string> > syncs_) { + // check for sanity of parameters + int num_stmt = IS.size(); + if (xforms.size() != num_stmt) + throw std::invalid_argument("number of iteration spaces does not match number of transformations"); + known_ = copy(known); + if (known_.n_out() != 0) + throw std::invalid_argument("known condition must be a set relation"); + if (known_.is_null()) + known_ = Relation::True(0); + else + known_.simplify(2, 4); + if (!known_.is_upper_bound_satisfiable()) + return; + if (known_.number_of_conjuncts() > 1) + throw std::invalid_argument("only one conjunct allowed in known condition"); + xforms_ = xforms; + for (int i = 0; i < num_stmt; i++) { + xforms_[i].simplify(); + if (!xforms_[i].has_single_conjunct()) + throw std::invalid_argument("mapping relation must have only one conjunct"); + if (xforms_[i].n_inp() != IS[i].n_inp() || IS[i].n_out() != 0) + throw std::invalid_argument("illegal iteration space or transformation arity"); + } + + + //protonu-- + //easier to handle this as a global + smtNonSplitLevels = smtNonSplitLevels_; + syncs = syncs_; + loopIdxNames = loopIdxNames_; + //end-protonu + + + + // find the maximum iteration space dimension we are going to operate on + int num_level = known_.n_inp(); + for (int i = 0; i < num_stmt; i++) + if (xforms_[i].n_out() > num_level) + num_level = xforms_[i].n_out(); + known_ = Extend_Set(known_, num_level-known_.n_inp()); + for (int i = 1; i <= num_level; i++) + known_.name_set_var(i, loop_var_name_prefix + to_string(i)); + known_.setup_names(); + + // split disjoint conjunctions in original iteration spaces + std::vector<Relation> new_IS; + for (int i = 0; i < num_stmt; i++) { + for (int j = 1; j <= IS[i].n_inp(); j++) + xforms_[i].name_input_var(j, const_cast<std::vector<Relation> &>(IS)[i].input_var(j)->name()); + for (int j = 1; j <= xforms_[i].n_out(); j++) + xforms_[i].name_output_var(j, loop_var_name_prefix + to_string(j)); + xforms_[i].setup_names(); + + Relation R = Range(Restrict_Domain(copy(xforms_[i]), copy(IS[i]))); + R = Intersection(Extend_Set(R, num_level-R.n_inp()), copy(known_)); + R.simplify(2, 4); + if (R.is_inexact()) + throw codegen_error("cannot generate code for inexact iteration spaces"); + + while(R.is_upper_bound_satisfiable()) { + DNF *dnf = R.query_DNF(); + DNF_Iterator c(dnf); + Relation R2 = Relation(R, *c); + R2.simplify(); + new_IS.push_back(copy(R2)); + remap_.push_back(i); + c.next(); + if (!c.live()) + break; + Relation remainder(R, *c); + c.next(); + while (c.live()) { + remainder = Union(remainder, Relation(R, *c)); + c.next(); + } + R = Difference(remainder, R2); + R.simplify(2, 4); + } + } + + // number of new statements after splitting + num_stmt = new_IS.size(); + if(!smtNonSplitLevels.empty()) + smtNonSplitLevels.resize(num_stmt); + // assign a dummy value to loops created for the purpose of expanding to maximum dimension + for (int i = 0; i < num_stmt; i++) { + if (xforms[remap_[i]].n_out() < num_level) { + F_And *f_root = new_IS[i].and_with_and(); + for (int j = xforms[remap_[i]].n_out()+1; j <= num_level; j++) { + EQ_Handle h = f_root->add_EQ(); + h.update_coef(new_IS[i].set_var(j), 1); + h.update_const(posInfinity); + } + new_IS[i].simplify(); + } + } + + // calculate projected subspaces for each loop level once and save for CG tree manipulation later + projected_IS_ = std::vector<std::vector<Relation> >(num_level); + for (int i = 0; i < num_level; i++) + projected_IS_[i] = std::vector<Relation>(num_stmt); + for (int i = 0; i < num_stmt; i++) { + if (num_level > 0) + projected_IS_[num_level-1][i] = new_IS[i]; + for (int j = num_level-1; j >= 1; j--) { + projected_IS_[j-1][i] = Project(copy(projected_IS_[j][i]), j+1, Set_Var); + projected_IS_[j-1][i].simplify(2, 4); + } + } +} + + +CG_result *CodeGen::buildAST(int level, const BoolSet<> &active, bool split_on_const, const Relation &restriction) { + if (level > num_level()) + return new CG_leaf(this, active); + + int num_active_stmt = active.num_elem(); + if (num_active_stmt == 0) + return NULL; + else if (num_active_stmt == 1) + return new CG_loop(this, active, level, buildAST(level+1, active, true, restriction)); + + // use estimated constant bounds for fast non-overlap iteration space splitting + if (split_on_const) { + std::vector<std::pair<std::pair<coef_t, coef_t>, int> > bounds; + + for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) { + Relation r = Intersection(copy(projected_IS_[level-1][*i]), copy(restriction)); + r.simplify(2, 4); + if (!r.is_upper_bound_satisfiable()) + continue; + coef_t lb, ub; + r.single_conjunct()->query_variable_bounds(r.set_var(level),lb,ub); + bounds.push_back(std::make_pair(std::make_pair(lb, ub), *i)); + } + sort(bounds.begin(), bounds.end()); + + std::vector<Relation> split_cond; + std::vector<CG_result *> split_child; + + coef_t prev_val = -posInfinity; + coef_t next_val = bounds[0].first.second; + BoolSet<> next_active(active.size()); + int i = 0; + while (i < bounds.size()) { + if (bounds[i].first.first <= next_val) { + next_active.set(bounds[i].second); + next_val = max(next_val, bounds[i].first.second); + i++; + } + else { + Relation r(num_level()); + F_And *f_root = r.add_and(); + if (prev_val != -posInfinity) { + GEQ_Handle h = f_root->add_GEQ(); + h.update_coef(r.set_var(level), 1); + h.update_const(-prev_val-1); + } + if (next_val != posInfinity) { + GEQ_Handle h = f_root->add_GEQ(); + h.update_coef(r.set_var(level), -1); + h.update_const(next_val); + } + r.simplify(); + + Relation new_restriction = Intersection(copy(r), copy(restriction)); + new_restriction.simplify(2, 4); + CG_result *child = buildAST(level, next_active, false, new_restriction); + if (child != NULL) { + split_cond.push_back(copy(r)); + split_child.push_back(child); + } + next_active.unset_all(); + prev_val = next_val; + next_val = bounds[i].first.second; + } + } + if (!next_active.empty()) { + Relation r = Relation::True(num_level()); + if (prev_val != -posInfinity) { + F_And *f_root = r.and_with_and(); + GEQ_Handle h = f_root->add_GEQ(); + h.update_coef(r.set_var(level), 1); + h.update_const(-prev_val-1); + r.simplify(); + } + Relation new_restriction = Intersection(copy(r), copy(restriction)); + new_restriction.simplify(2, 4); + CG_result *child = buildAST(level, next_active, false, new_restriction); + if (child != NULL) { + split_cond.push_back(copy(r)); + split_child.push_back(child); + } + } + + if (split_child.size() == 0) + return NULL; + else if (split_child.size() == 1) + return split_child[0]; + else + return new CG_split(this, active, split_cond, split_child); + } + // check bound conditions exhaustively for non-overlap iteration space splitting + else { + std::vector<Relation> Rs(active.size()); + for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) { + Rs[*i] = Intersection(Approximate(copy(projected_IS_[level-1][*i])), copy(restriction)); + Rs[*i].simplify(2, 4); + } + Relation hull = SimpleHull(Rs); + + //protonu-warn Chun about this change + //This does some fancy splitting of statements into loops with the + //fewest dimentions, but that's not necessarily what we want when + //code-gening for CUDA. smtNonSplitLevels keeps track per-statment of + //the levels that should not be split on. + bool checkForSplits = true; + for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) { + if(*i < smtNonSplitLevels.size()) + for(int k = 0; k <smtNonSplitLevels[*i].size(); k++) + if(smtNonSplitLevels[*i][k] == (level-2)){ + checkForSplits = false; + break; + } + } + + + + + for (BoolSet<>::const_iterator i = active.begin(); i != active.end() && checkForSplits; i++) { + Relation r = Gist(copy(Rs[*i]), copy(hull), 1); + if (r.is_obvious_tautology()) + continue; + r = EQs_to_GEQs(r); + + for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++) { + if ((*e).has_wildcards()) + continue; + + Relation cond = Relation::True(num_level()); + BoolSet<> first_chunk(active.size()); + BoolSet<> second_chunk(active.size()); + + if ((*e).get_coef(hull.set_var(level)) > 0) { + cond.and_with_GEQ(*e); + cond = Complement(cond);; + cond.simplify(); + second_chunk.set(*i); + } + else if ((*e).get_coef(hull.set_var(level)) < 0) { + cond.and_with_GEQ(*e); + cond.simplify(); + first_chunk.set(*i); + } + else + continue; + + bool is_proper_split_cond = true; + for (BoolSet<>::const_iterator j = active.begin(); j != active.end(); j++) + if ( *j != *i) { + bool in_first = Intersection(copy(Rs[*j]), copy(cond)).is_upper_bound_satisfiable(); + bool in_second = Difference(copy(Rs[*j]), copy(cond)).is_upper_bound_satisfiable(); + + if (in_first && in_second) { + is_proper_split_cond = false; + break; + } + + if (in_first) + first_chunk.set(*j); + else if (in_second) + second_chunk.set(*j); + } + + if (is_proper_split_cond && first_chunk.num_elem() != 0 && second_chunk.num_elem() != 0) { + CG_result *first_cg = buildAST(level, first_chunk, false, copy(cond)); + CG_result *second_cg = buildAST(level, second_chunk, false, Complement(copy(cond))); + if (first_cg == NULL) + return second_cg; + else if (second_cg == NULL) + return first_cg; + else { + std::vector<Relation> split_cond; + std::vector<CG_result *> split_child; + split_cond.push_back(copy(cond)); + split_child.push_back(first_cg); + split_cond.push_back(Complement(copy(cond))); + split_child.push_back(second_cg); + + return new CG_split(this, active, split_cond, split_child); + } + } + } + } + return new CG_loop(this, active, level, buildAST(level+1, active, true, restriction)); + } +} + + +CG_result *CodeGen::buildAST(int effort) { + if (remap_.size() == 0) + return NULL; + + CG_result *cgr = buildAST(1, ~BoolSet<>(remap_.size()), true, Relation::True(num_level())); + if (cgr == NULL) + return NULL; + + + // break down the complete iteration space condition to levels of bound/guard condtions + cgr = cgr->recompute(cgr->active_, copy(known_), copy(known_)); + + + + if (cgr == NULL) + return NULL; + + // calculate each loop's nesting depth + int depth = cgr->populateDepth(); + + + // redistribute guard condition locations by additional splittings + std::pair<CG_result *, Relation> result = cgr->liftOverhead(min(effort,depth), false); + + // since guard conditions are postponed for non-loop levels, hoist them now. + // this enables proper if-condition simplication when outputting actual code. + result.first->hoistGuard(); + + + + + return result.first; +} + +} diff --git a/omegalib/codegen/src/rose_attributes.cc b/omegalib/codegen/src/rose_attributes.cc new file mode 100644 index 0000000..bb9681c --- /dev/null +++ b/omegalib/codegen/src/rose_attributes.cc @@ -0,0 +1,183 @@ +#include <code_gen/rose_attributes.h> + +namespace omega { + +CodeInsertionAttribute* getOrCreateCodeInsertionAttribute(SgNode* node) { + CodeInsertionAttribute* attr; + if(node->attributeExists("code_insertion")) + return static_cast<CodeInsertionAttribute*>(node->getAttribute("code_insertion")); + attr = new CodeInsertionAttribute(); + node->setAttribute("code_insertion", attr); + return attr; +} + +void postProcessRoseCodeInsertion(SgProject* proj) { + //generatePDF(*proj); + CodeInsertionVisitor visitor = CodeInsertionVisitor(); + visitor.initialize(); + visitor.traverseInputFiles(proj); + visitor.insertCode(); +} + +// Swap a code insertion from one node (sn) to another (dn) +// -- note that this function does not currently remove the insertion from the sn node +void moveCodeInsertion(SgNode* sn, CodeInsertion* ci, SgNode* dn) { + CodeInsertionAttribute* new_attr; + // TODO in the near future: replace the above statement with 'new_attr = getOrCreateCodeInsertionAttribute(...)' + CodeInsertionAttribute* old_attr = static_cast<CodeInsertionAttribute*>(sn->getAttribute("code_insertion")); + if(dn->attributeExists("code_insertion")) { + new_attr = static_cast<CodeInsertionAttribute*>(dn->getAttribute("code_insertion")); + } + else { + new_attr = new CodeInsertionAttribute(); + dn->setAttribute("code_insertion", new_attr); + } + new_attr->add(ci); +} + +// A function that copies a specific attribute from one node to another +// this function exists to get around a ROSE limitation that does not +// copy attributes +void copyAttribute(std::string attr_name, SgNode* s, SgNode* d) { + if(s->attributeExists(attr_name)) { + d->setAttribute(attr_name,s->getAttribute(attr_name)); + } +} + +// TODO: find all existng attributes and iterate over them instead of doing them +// individually +void copyAttributes(SgNode* s, SgNode* d) { + copyAttribute("code_insertion", s, d); + //...any other attributes... +} + +void CodeInsertionVisitor::initialize() { + this->loop_level = 0; + this->ci_marks = std::vector<CodeInsertionMark*>(); +} + +void CodeInsertionVisitor::markStmt(SgStatement* stmt, CodeInsertion* ci) { + // this check prevents multiple copies of stmts + // -- may be changed in the future + if(!ci->marked) { + CodeInsertionMark* pos = new CodeInsertionMark(); + pos->stmt = stmt; + pos->ci = ci; + this->ci_marks.push_back(pos); + ci->marked = true; + } +} + +// increase loop_level as the visitor descends +void CodeInsertionVisitor::preOrderVisit(SgNode* n) { + if (isSgForStatement(n)) { + this->loop_level++; + } +} + +void CodeInsertionVisitor::postOrderVisit(SgNode* n) { + if(isSgForStatement(n)) { + this->loop_level--; + } + if(isSgStatement(n)) { + if(n->attributeExists("code_insertion")) { + CodeInsertionAttribute *attr = static_cast<CodeInsertionAttribute*>(n->getAttribute("code_insertion")); + for(CodeInsertionPtrListItr itr = attr->begin(); itr != attr->end(); ++itr) { + CodeInsertion *insertion = *itr; + // check loop level -- if it is equivelent, mark statement for insertion + // -- else, move attribute up to parent + if(insertion->loop_level != this->loop_level) { + moveCodeInsertion(n, insertion, n->get_parent()); + } + else { + this->markStmt(isSgStatement(n), insertion); + } + } + } + } +} + +// final stage of algorithm that inserts marked statements +void CodeInsertionVisitor::insertCode() { + for(std::vector<CodeInsertionMark*>::iterator itr = this->ci_marks.begin(); itr != this->ci_marks.end(); ++itr) { + CodeInsertionMark* mark = *itr; + SgScopeStatement* scope = static_cast<SgScopeStatement*>(mark->stmt->get_parent()); + SageInterface::insertStatementBefore(mark->stmt, mark->ci->getStatement(scope)); + } +} + +SgStatement* PragmaInsertion::getStatement(SgScopeStatement* scopeStmt) { + SgStatement* stmt = SageBuilder::buildPragmaDeclaration(this->name); + return stmt; +} + +//SgStatement* MMPrefetchInsertion::getStatement(SgScopeStatement* scopeStmt) { +// const SgName& name = SgName("_mm_prefetch"); +// SgType* rtype = SageBuilder::buildVoidType(); +// SgExpression* arr_arg = SageBuilder::buildVarRefExp(this->arrName); +// SgExpression* hint_arg = SageBuilder::buildShortVal(this->cacheHint); +// SgExprListExp* args = SageBuilder::buildExprListExp(arr_arg,hint_arg); +// SgStatement* stmt = SageBuilder::buildFunctionCallStmt(name, rtype, args, scopeStmt); +// return stmt; +//} + +SgStatement* MMPrefetchInsertion::getStatement(SgScopeStatement* scopeStmt) { + const SgName fname = SgName("_mm_prefetch"); + SgType* rtype = SageBuilder::buildVoidType(); + SgExpression* arr_arg = this->buildArrArg(scopeStmt); + SgExpression* hint_arg = SageBuilder::buildShortVal(this->cacheHint); + SgExprListExp* args = SageBuilder::buildExprListExp(arr_arg, hint_arg); + return SageBuilder::buildFunctionCallStmt(fname, rtype, args, scopeStmt); +} + +SgExpression* MMPrefetchInsertion::buildArrArg(SgScopeStatement* scopeStmt) { + // if there are no index arguments given, just return a variable reference + if(this->indexCount == 0) { + const SgName aname = SgName(this->arrName); + return SageBuilder::buildVarRefExp(aname, scopeStmt); + } + std::vector<SgExpression*> argList = std::vector<SgExpression*>(); + // foreach dimension + for(int i = 0; i < this->indexCount; i++) { + argList.push_back(this->makeIndexExp(i, scopeStmt)); + } + return SageBuilder::buildExprListExp(argList); +} + +SgExpression* MMPrefetchInsertion::makeIndexExp(int dim, SgScopeStatement* scopeStmt) { + //(i + offset) or (offset) or (i) + std::string* indexer = this->indecies.at(dim); + int offset = this->offsets.at(dim); + if(indexer == NULL) { + return SageBuilder::buildIntVal(offset); + } + else { + const SgName name = SgName(*indexer); + SgVarRefExp* iref = SageBuilder::buildVarRefExp(name, scopeStmt); + if(offset == 0) { + return iref; + } + else { + return SageBuilder::buildAddOp(iref, SageBuilder::buildIntVal(offset)); + } + } +} + +void MMPrefetchInsertion::initialize(const std::string& arrName, int hint) { + this->arrName = std::string(arrName); + this->cacheHint = hint; + this->indecies = std::vector<std::string*>(); + this->offsets = std::vector<int>(); + this->indexCount = 0; +} +void MMPrefetchInsertion::addDim(int offset) { + this->offsets.push_back(offset); + this->indecies.push_back(NULL); + this->indexCount++; +} +void MMPrefetchInsertion::addDim(int offset, const std::string& indexer) { + this->offsets.push_back(offset); + this->indecies.push_back(new std::string(indexer)); + this->indexCount++; +} +} |