From 2fce43d484e4148ae858f410d51dcd9951d34374 Mon Sep 17 00:00:00 2001
From: Tuowen Zhao <ztuowen@gmail.com>
Date: Sun, 18 Sep 2016 15:45:13 +0000
Subject: remove include & rename
---
omegalib/codegen/src/CG.cc | 1163 ++++++++++++++++++++
omegalib/codegen/src/CG_roseBuilder.cc | 1533 ++++++++++++++++++++++++++
omegalib/codegen/src/CG_roseRepr.cc | 125 +++
omegalib/codegen/src/CG_stringBuilder.cc | 487 +++++++++
omegalib/codegen/src/CG_utils.cc | 1735 ++++++++++++++++++++++++++++++
omegalib/codegen/src/codegen.cc | 378 +++++++
omegalib/codegen/src/rose_attributes.cc | 183 ++++
7 files changed, 5604 insertions(+)
create mode 100644 omegalib/codegen/src/CG.cc
create mode 100644 omegalib/codegen/src/CG_roseBuilder.cc
create mode 100644 omegalib/codegen/src/CG_roseRepr.cc
create mode 100644 omegalib/codegen/src/CG_stringBuilder.cc
create mode 100755 omegalib/codegen/src/CG_utils.cc
create mode 100755 omegalib/codegen/src/codegen.cc
create mode 100644 omegalib/codegen/src/rose_attributes.cc
(limited to 'omegalib/codegen/src')
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++;
+}
+}
--
cgit v1.2.3-70-g09d2