diff options
Diffstat (limited to 'src/loop.cc')
| -rw-r--r-- | src/loop.cc | 640 |
1 files changed, 205 insertions, 435 deletions
diff --git a/src/loop.cc b/src/loop.cc index f187a50..19378a4 100644 --- a/src/loop.cc +++ b/src/loop.cc @@ -69,7 +69,7 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, stmt_nesting_level_[i] = t; stmt_nesting_level[i] = t; } - + stmt = std::vector<Statement>(ir_stmt.size()); int n_dim = -1; int max_loc; @@ -82,14 +82,14 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, max_nesting_level = stmt_nesting_level[j]; loc = j; } - + // most deeply nested statement acting as a reference point if (n_dim == -1) { n_dim = max_nesting_level; max_loc = loc; - + index = std::vector<std::string>(n_dim); - + ir_tree_node *itn = ir_stmt[loc]; int cur_dim = n_dim - 1; while (itn->parent != NULL) { @@ -101,42 +101,28 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, } } } - + // align loops by names, temporary solution ir_tree_node *itn = ir_stmt[loc]; int depth = stmt_nesting_level_[loc] - 1; - /* while (itn->parent != NULL) { - itn = itn->parent; - if (itn->content->type() == IR_CONTROL_LOOP && itn->payload == -1) { - std::string name = static_cast<IR_Loop *>(itn->content)->index()->name(); - for (int j = 0; j < n_dim; j++) - if (index[j] == name) { - itn->payload = j; - break; - } - if (itn->payload == -1) - throw loop_error("no complex alignment yet"); - } - } - */ for (int t = depth; t >= 0; t--) { int y = t; ir_tree_node *itn = ir_stmt[loc]; - + while ((itn->parent != NULL) && (y >= 0)) { itn = itn->parent; if (itn->content->type() == IR_CONTROL_LOOP) y--; } - + if (itn->content->type() == IR_CONTROL_LOOP && itn->payload == -1) { CG_outputBuilder *ocg = ir->builder(); - + itn->payload = depth - t; - + CG_outputRepr *code = static_cast<IR_Block *>(ir_stmt[loc]->content)->extract(); - + std::vector<CG_outputRepr *> index_expr; std::vector<std::string> old_index; CG_outputRepr *repl = ocg->CreateIdent(index[itn->payload]); @@ -145,48 +131,39 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, static_cast<IR_Loop *>(itn->content)->index()->name()); code = ocg->CreateSubstitutedStmt(0, code, old_index, index_expr); - + replace.insert(std::pair<int, CG_outputRepr*>(loc, code)); - //stmt[loc].code = code; - } } - + // set relation variable names Relation r(n_dim); F_And *f_root = r.add_and(); itn = ir_stmt[loc]; int temp_depth = depth; while (itn->parent != NULL) { - + itn = itn->parent; if (itn->content->type() == IR_CONTROL_LOOP) { r.name_set_var(itn->payload + 1, index[temp_depth]); - + temp_depth--; } - //static_cast<IR_Loop *>(itn->content)->index()->name()); } - - /*while (itn->parent != NULL) { - itn = itn->parent; - if (itn->content->type() == IR_CONTROL_LOOP) - r.name_set_var(itn->payload+1, static_cast<IR_Loop *>(itn->content)->index()->name()); - }*/ - + // extract information from loop/if structures std::vector<bool> processed(n_dim, false); std::vector<std::string> vars_to_be_reversed; itn = ir_stmt[loc]; while (itn->parent != NULL) { itn = itn->parent; - + switch (itn->content->type()) { case IR_CONTROL_LOOP: { IR_Loop *lp = static_cast<IR_Loop *>(itn->content); Variable_ID v = r.set_var(itn->payload + 1); int c; - + try { c = lp->step_size(); if (c > 0) { @@ -200,7 +177,7 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, cond, true); else throw ir_error("loop condition not supported"); - + } else if (c < 0) { CG_outputBuilder *ocg = ir->builder(); CG_outputRepr *lb = lp->lower_bound(); @@ -218,7 +195,7 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, IR_COND_LT, true); else throw ir_error("loop condition not supported"); - + vars_to_be_reversed.push_back(lp->index()->name()); } else throw ir_error("loop step size zero"); @@ -229,7 +206,7 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, itn->content = itn->content->convert(); return false; } - + if (abs(c) != 1) { F_Exists *f_exists = f_root->add_exists(); Variable_ID e = f_exists->declare(); @@ -244,7 +221,7 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, exp2formula(ir, r, f_and, freevar, lb, e, 's', IR_COND_EQ, true); } - + processed[itn->payload] = true; break; } @@ -281,7 +258,7 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, } return false; } - + break; } default: @@ -292,7 +269,7 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, return false; } } - + // add information for missing loops for (int j = 0; j < n_dim; j++) if (!processed[j]) { @@ -303,89 +280,32 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, && itn->payload == j) break; } - + Variable_ID v = r.set_var(j + 1); if (loc < max_loc) { - + CG_outputBuilder *ocg = ir->builder(); - + CG_outputRepr *lb = static_cast<IR_Loop *>(itn->content)->lower_bound(); - + exp2formula(ir, r, f_root, freevar, lb, v, 's', IR_COND_EQ, false); - - /* if (ir->QueryExpOperation( - static_cast<IR_Loop *>(itn->content)->lower_bound()) - == IR_OP_VARIABLE) { - IR_ScalarRef *ref = - static_cast<IR_ScalarRef *>(ir->Repr2Ref( - static_cast<IR_Loop *>(itn->content)->lower_bound())); - std::string name_ = ref->name(); - - for (int i = 0; i < index.size(); i++) - if (index[i] == name_) { - exp2formula(ir, r, f_root, freevar, lb, v, 's', - IR_COND_GE, false); - - CG_outputRepr *ub = - static_cast<IR_Loop *>(itn->content)->upper_bound(); - IR_CONDITION_TYPE cond = - static_cast<IR_Loop *>(itn->content)->stop_cond(); - if (cond == IR_COND_LT || cond == IR_COND_LE) - exp2formula(ir, r, f_root, freevar, ub, v, - 's', cond, false); - - - - } - - } - */ - + } else { // loc > max_loc - + CG_outputBuilder *ocg = ir->builder(); CG_outputRepr *ub = static_cast<IR_Loop *>(itn->content)->upper_bound(); - + exp2formula(ir, r, f_root, freevar, ub, v, 's', IR_COND_EQ, false); - /*if (ir->QueryExpOperation( - static_cast<IR_Loop *>(itn->content)->upper_bound()) - == IR_OP_VARIABLE) { - IR_ScalarRef *ref = - static_cast<IR_ScalarRef *>(ir->Repr2Ref( - static_cast<IR_Loop *>(itn->content)->upper_bound())); - std::string name_ = ref->name(); - - for (int i = 0; i < index.size(); i++) - if (index[i] == name_) { - - CG_outputRepr *lb = - static_cast<IR_Loop *>(itn->content)->lower_bound(); - - exp2formula(ir, r, f_root, freevar, lb, v, 's', - IR_COND_GE, false); - - CG_outputRepr *ub = - static_cast<IR_Loop *>(itn->content)->upper_bound(); - IR_CONDITION_TYPE cond = - static_cast<IR_Loop *>(itn->content)->stop_cond(); - if (cond == IR_COND_LT || cond == IR_COND_LE) - exp2formula(ir, r, f_root, freevar, ub, v, - 's', cond, false); - - - } - } - */ } } - + r.setup_names(); r.simplify(); - + // insert the statement CG_outputBuilder *ocg = ir->builder(); std::vector<CG_outputRepr *> reverse_expr; @@ -407,10 +327,10 @@ bool Loop::init_loop(std::vector<ir_tree_node *> &ir_tree, stmt[loc].loop_level[i].payload = i; stmt[loc].loop_level[i].parallel_level = 0; } - + stmt_nesting_level[loc] = -1; } - + return true; } @@ -418,31 +338,27 @@ Loop::Loop(const IR_Control *control) { last_compute_cgr_ = NULL; last_compute_cg_ = NULL; - + ir = const_cast<IR_Code *>(control->ir_); init_code = NULL; cleanup_code = NULL; tmp_loop_var_name_counter = 1; overflow_var_name_counter = 1; known = Relation::True(0); - + ir_tree = build_ir_tree(control->clone(), NULL); - // std::vector<ir_tree_node *> ir_stmt; - while (!init_loop(ir_tree, ir_stmt)) { } - - for (int i = 0; i < stmt.size(); i++) { std::map<int, CG_outputRepr*>::iterator it = replace.find(i); - + if (it != replace.end()) stmt[i].code = it->second; else stmt[i].code = stmt[i].code; } - + if (stmt.size() != 0) dep = DependenceGraph(stmt[0].IS.n_set()); else @@ -450,7 +366,7 @@ Loop::Loop(const IR_Control *control) { // init the dependence graph for (int i = 0; i < stmt.size(); i++) dep.insert(); - + for (int i = 0; i < stmt.size(); i++) for (int j = i; j < stmt.size(); j++) { std::pair<std::vector<DependenceVector>, @@ -458,7 +374,7 @@ Loop::Loop(const IR_Control *control) { ir, stmt[i].code, stmt[i].IS, stmt[j].code, stmt[j].IS, freevar, index, stmt_nesting_level_[i], stmt_nesting_level_[j]); - + for (int k = 0; k < dv.first.size(); k++) { if (is_dependence_valid(ir_stmt[i], ir_stmt[j], dv.first[k], true)) @@ -466,7 +382,7 @@ Loop::Loop(const IR_Control *control) { else { dep.connect(j, i, dv.first[k].reverse()); } - + } for (int k = 0; k < dv.second.size(); k++) if (is_dependence_valid(ir_stmt[j], ir_stmt[i], dv.second[k], @@ -475,11 +391,8 @@ Loop::Loop(const IR_Control *control) { else { dep.connect(i, j, dv.second[k].reverse()); } - // std::pair<std::vector<DependenceVector>, - // std::vector<DependenceVector> > dv_ = test_data_dependences( - } - + // init dumb transformation relations e.g. [i, j] -> [ 0, i, 0, j, 0] @@ -487,49 +400,48 @@ Loop::Loop(const IR_Control *control) { int n = stmt[i].IS.n_set(); stmt[i].xform = Relation(n, 2 * n + 1); F_And *f_root = stmt[i].xform.add_and(); - + for (int j = 1; j <= n; j++) { EQ_Handle h = f_root->add_EQ(); h.update_coef(stmt[i].xform.output_var(2 * j), 1); h.update_coef(stmt[i].xform.input_var(j), -1); } - + for (int j = 1; j <= 2 * n + 1; j += 2) { EQ_Handle h = f_root->add_EQ(); h.update_coef(stmt[i].xform.output_var(j), 1); } stmt[i].xform.simplify(); } - + if (stmt.size() != 0) num_dep_dim = stmt[0].IS.n_set(); else num_dep_dim = 0; - // debug - /*for (int i = 0; i < stmt.size(); i++) { - std::cout << i << ": "; - //stmt[i].xform.print(); - stmt[i].IS.print(); - std::cout << std::endl; - - }*/ - //end debug +// Debug output +// for (int i = 0; i < stmt.size(); i++) { +// std::cout << i << ": "; +// stmt[i].xform.print(); +// stmt[i].IS.print(); +// std::cout << std::endl; +// +// } } Loop::~Loop() { - + delete last_compute_cgr_; delete last_compute_cg_; - + for (int i = 0; i < stmt.size(); i++) if (stmt[i].code != NULL) { stmt[i].code->clear(); delete stmt[i].code; } - + for (int i = 0; i < ir_tree.size(); i++) delete ir_tree[i]; - + if (init_code != NULL) { init_code->clear(); delete init_code; @@ -543,10 +455,10 @@ Loop::~Loop() { int Loop::get_dep_dim_of(int stmt_num, int level) const { if (stmt_num < 0 || stmt_num >= stmt.size()) throw std::invalid_argument("invaid statement " + to_string(stmt_num)); - + if (level < 1 || level > stmt[stmt_num].loop_level.size()) return -1; - + int trip_count = 0; while (true) { switch (stmt[stmt_num].loop_level[level - 1].type) { @@ -577,16 +489,16 @@ int Loop::get_dep_dim_of(int stmt_num, int level) const { int Loop::get_last_dep_dim_before(int stmt_num, int level) const { if (stmt_num < 0 || stmt_num >= stmt.size()) throw std::invalid_argument("invaid statement " + to_string(stmt_num)); - + if (level < 1) return -1; if (level > stmt[stmt_num].loop_level.size()) level = stmt[stmt_num].loop_level.size() + 1; - + for (int i = level - 1; i >= 1; i--) if (stmt[stmt_num].loop_level[i - 1].type == LoopLevelOriginal) return stmt[stmt_num].loop_level[i - 1].payload; - + return -1; } @@ -623,7 +535,7 @@ CG_outputRepr *Loop::getCode(int effort) const { if (m == 0) return NULL; const int n = stmt[0].xform.n_out(); - + if (last_compute_cg_ == NULL) { std::vector<Relation> IS(m); std::vector<Relation> xforms(m); @@ -632,29 +544,29 @@ CG_outputRepr *Loop::getCode(int effort) const { xforms[i] = stmt[i].xform; } Relation known = Extend_Set(copy(this->known), n - this->known.n_set()); - + last_compute_cg_ = new CodeGen(xforms, IS, known); delete last_compute_cgr_; last_compute_cgr_ = NULL; } - + if (last_compute_cgr_ == NULL || last_compute_effort_ != effort) { delete last_compute_cgr_; last_compute_cgr_ = last_compute_cg_->buildAST(effort); last_compute_effort_ = effort; } - + std::vector<CG_outputRepr *> stmts(m); for (int i = 0; i < m; i++) stmts[i] = stmt[i].code; CG_outputBuilder *ocg = ir->builder(); CG_outputRepr *repr = last_compute_cgr_->printRepr(ocg, stmts); - + if (init_code != NULL) repr = ocg->StmtListAppend(init_code->clone(), repr); if (cleanup_code != NULL) repr = ocg->StmtListAppend(repr, cleanup_code->clone()); - + return repr; } @@ -663,7 +575,7 @@ void Loop::printCode(int effort) const { if (m == 0) return; const int n = stmt[0].xform.n_out(); - + if (last_compute_cg_ == NULL) { std::vector<Relation> IS(m); std::vector<Relation> xforms(m); @@ -672,18 +584,18 @@ void Loop::printCode(int effort) const { xforms[i] = stmt[i].xform; } Relation known = Extend_Set(copy(this->known), n - this->known.n_set()); - + last_compute_cg_ = new CodeGen(xforms, IS, known); delete last_compute_cgr_; last_compute_cgr_ = NULL; } - + if (last_compute_cgr_ == NULL || last_compute_effort_ != effort) { delete last_compute_cgr_; last_compute_cgr_ = last_compute_cg_->buildAST(effort); last_compute_effort_ = effort; } - + std::string repr = last_compute_cgr_->printString(); std::cout << repr << std::endl; } @@ -710,7 +622,7 @@ void Loop::printDependenceGraph() const { Relation Loop::getNewIS(int stmt_num) const { Relation result; - + if (stmt[stmt_num].xform.is_null()) { Relation known = Extend_Set(copy(this->known), stmt[stmt_num].IS.n_set() - this->known.n_set()); @@ -723,19 +635,19 @@ Relation Loop::getNewIS(int stmt_num) const { Restrict_Domain(copy(stmt[stmt_num].xform), copy(stmt[stmt_num].IS))), known); } - + result.simplify(2, 4); - + return result; } std::vector<Relation> Loop::getNewIS() const { const int m = stmt.size(); - + std::vector<Relation> new_IS(m); for (int i = 0; i < m; i++) new_IS[i] = getNewIS(i); - + return new_IS; } @@ -743,7 +655,7 @@ void Loop::pragma(int stmt_num, int level, const std::string &pragmaText) { // check sanity of parameters if(stmt_num < 0) throw std::invalid_argument("invalid statement " + to_string(stmt_num)); - + CG_outputBuilder *ocg = ir->builder(); CG_outputRepr *code = stmt[stmt_num].code; ocg->CreatePragmaAttribute(code, level, pragmaText); @@ -761,13 +673,13 @@ void Loop::prefetch(int stmt_num, int level, const std::string &arrName, int hin std::vector<int> Loop::getLexicalOrder(int stmt_num) const { assert(stmt_num < stmt.size()); - + const int n = stmt[stmt_num].xform.n_out(); std::vector<int> lex(n, 0); - + for (int i = 0; i < n; i += 2) lex[i] = get_const(stmt[stmt_num].xform, i, Output_Var); - + return lex; } @@ -776,13 +688,13 @@ std::vector<int> Loop::getLexicalOrder(int stmt_num) const { std::set<int> Loop::getSubLoopNest(int stmt_num, int level) const { assert(stmt_num >= 0 && stmt_num < stmt.size()); assert(level > 0 && level <= stmt[stmt_num].loop_level.size()); - + std::set<int> working; for (int i = 0; i < stmt.size(); i++) if (const_cast<Loop *>(this)->stmt[i].IS.is_upper_bound_satisfiable() && stmt[i].loop_level.size() >= level) working.insert(i); - + for (int i = 1; i <= level; i++) { int a = getLexicalOrder(stmt_num, i); for (std::set<int>::iterator j = working.begin(); j != working.end();) { @@ -793,14 +705,14 @@ std::set<int> Loop::getSubLoopNest(int stmt_num, int level) const { ++j; } } - + return working; } int Loop::getLexicalOrder(int stmt_num, int level) const { assert(stmt_num >= 0 && stmt_num < stmt.size()); assert(level > 0 && level <= stmt[stmt_num].loop_level.size()+1); - + Relation &r = const_cast<Loop *>(this)->stmt[stmt_num].xform; for (EQ_Iterator e(r.single_conjunct()->EQs()); e; e++) if (abs((*e).get_coef(r.output_var(2 * level - 1))) == 1) { @@ -815,7 +727,7 @@ int Loop::getLexicalOrder(int stmt_num, int level) const { return (*e).get_coef(r.output_var(2 * level - 1)) > 0 ? -t : t; } } - + throw loop_error( "can't find lexical order for statement " + to_string(stmt_num) + "'s loop level " + to_string(level)); @@ -823,7 +735,7 @@ int Loop::getLexicalOrder(int stmt_num, int level) const { std::set<int> Loop::getStatements(const std::vector<int> &lex, int dim) const { const int m = stmt.size(); - + std::set<int> same_loops; for (int i = 0; i < m; i++) { if (dim < 0) @@ -837,32 +749,32 @@ std::set<int> Loop::getStatements(const std::vector<int> &lex, int dim) const { if (j > dim) same_loops.insert(i); } - + } - + return same_loops; } void Loop::shiftLexicalOrder(const std::vector<int> &lex, int dim, int amount) { const int m = stmt.size(); - + if (amount == 0) return; - + for (int i = 0; i < m; i++) { std::vector<int> lex2 = getLexicalOrder(i); - + bool need_shift = true; - + for (int j = 0; j < dim; j++) if (lex2[j] != lex[j]) { need_shift = false; break; } - + if (!need_shift) continue; - + if (amount > 0) { if (lex2[dim] < lex[dim]) continue; @@ -870,14 +782,14 @@ void Loop::shiftLexicalOrder(const std::vector<int> &lex, int dim, int amount) { if (lex2[dim] > lex[dim]) continue; } - + assign_const(stmt[i].xform, dim, lex2[dim] + amount); } } std::vector<std::set<int> > Loop::sort_by_same_loops(std::set<int> active, int level) { - + std::set<int> not_nested_at_this_level; std::map<ir_tree_node*, std::set<int> > sorted_by_loop; std::map<int, std::set<int> > sorted_by_lex_order; @@ -885,73 +797,73 @@ std::vector<std::set<int> > Loop::sort_by_same_loops(std::set<int> active, bool lex_order_already_set = false; for (std::set<int>::iterator it = active.begin(); it != active.end(); it++) { - + if (stmt[*it].ir_stmt_node == NULL) lex_order_already_set = true; } - + if (lex_order_already_set) { - + for (std::set<int>::iterator it = active.begin(); it != active.end(); it++) { std::map<int, std::set<int> >::iterator it2 = sorted_by_lex_order.find( get_const(stmt[*it].xform, 2 * (level - 1), Output_Var)); - + if (it2 != sorted_by_lex_order.end()) it2->second.insert(*it); else { - + std::set<int> to_insert; - + to_insert.insert(*it); - + sorted_by_lex_order.insert( std::pair<int, std::set<int> >( get_const(stmt[*it].xform, 2 * (level - 1), Output_Var), to_insert)); - + } - + } - + for (std::map<int, std::set<int> >::iterator it2 = sorted_by_lex_order.begin(); it2 != sorted_by_lex_order.end(); it2++) to_return.push_back(it2->second); - + } else { - + for (std::set<int>::iterator it = active.begin(); it != active.end(); it++) { - + ir_tree_node* itn = stmt[*it].ir_stmt_node; itn = itn->parent; while ((itn != NULL) && (itn->payload != level - 1)) itn = itn->parent; - + if (itn == NULL) not_nested_at_this_level.insert(*it); else { std::map<ir_tree_node*, std::set<int> >::iterator it2 = sorted_by_loop.find(itn); - + if (it2 != sorted_by_loop.end()) it2->second.insert(*it); else { std::set<int> to_insert; - + to_insert.insert(*it); - + sorted_by_loop.insert( std::pair<ir_tree_node*, std::set<int> >(itn, to_insert)); - + } - + } - + } if (not_nested_at_this_level.size() > 0) { for (std::set<int>::iterator it = not_nested_at_this_level.begin(); @@ -959,7 +871,7 @@ std::vector<std::set<int> > Loop::sort_by_same_loops(std::set<int> active, std::set<int> temp; temp.insert(*it); to_return.push_back(temp); - + } } for (std::map<ir_tree_node*, std::set<int> >::iterator it2 = @@ -971,17 +883,17 @@ std::vector<std::set<int> > Loop::sort_by_same_loops(std::set<int> active, void update_successors(int n, int node_num[], int cant_fuse_with[], Graph<std::set<int>, bool> &g, std::list<int> &work_list) { - + std::set<int> disconnect; for (Graph<std::set<int>, bool>::EdgeList::iterator i = g.vertex[n].second.begin(); i != g.vertex[n].second.end(); i++) { int m = i->first; - + if (node_num[m] != -1) throw loop_error("Graph input for fusion has cycles not a DAG!!"); - + std::vector<bool> check_ = g.getEdge(n, m); - + bool has_bad_edge_path = false; for (int i = 0; i < check_.size(); i++) if (!check_[i]) { @@ -994,12 +906,12 @@ void update_successors(int n, int node_num[], int cant_fuse_with[], cant_fuse_with[m] = std::max(cant_fuse_with[m], cant_fuse_with[n]); disconnect.insert(m); } - - + + for (std::set<int>::iterator i = disconnect.begin(); i != disconnect.end(); i++) { g.disconnect(n, *i); - + bool no_incoming_edges = true; for (int j = 0; j < g.vertex.size(); j++) if (j != *i) @@ -1007,23 +919,23 @@ void update_successors(int n, int node_num[], int cant_fuse_with[], no_incoming_edges = false; break; } - - + + if (no_incoming_edges) work_list.push_back(*i); } - + } Graph<std::set<int>, bool> Loop::construct_induced_graph_at_level( std::vector<std::set<int> > s, DependenceGraph dep, int dep_dim) { Graph<std::set<int>, bool> g; - + for (int i = 0; i < s.size(); i++) g.insert(s[i]); - + for (int i = 0; i < s.size(); i++) { - + for (int j = i + 1; j < s.size(); j++) { bool has_true_edge_i_to_j = false; bool has_true_edge_j_to_i = false; @@ -1031,16 +943,16 @@ Graph<std::set<int>, bool> Loop::construct_induced_graph_at_level( bool is_connected_j_to_i = false; for (std::set<int>::iterator ii = s[i].begin(); ii != s[i].end(); ii++) { - + for (std::set<int>::iterator jj = s[j].begin(); jj != s[j].end(); jj++) { - + std::vector<DependenceVector> dvs = dep.getEdge(*ii, *jj); for (int k = 0; k < dvs.size(); k++) if (dvs[k].is_control_dependence() || (dvs[k].is_data_dependence() && dvs[k].has_been_carried_at(dep_dim))) { - + if (dvs[k].is_data_dependence() && dvs[k].has_negative_been_carried_at( dep_dim)) { @@ -1049,14 +961,14 @@ Graph<std::set<int>, bool> Loop::construct_induced_graph_at_level( break; } else { //g.connect(i, j, true); - + has_true_edge_i_to_j = true; //break } } - + //if (is_connected) - + // break; // if (has_true_edge_i_to_j && !is_connected_i_to_j) // g.connect(i, j, true); @@ -1065,76 +977,63 @@ Graph<std::set<int>, bool> Loop::construct_induced_graph_at_level( if (dvs[k].is_control_dependence() || (dvs[k].is_data_dependence() && dvs[k].has_been_carried_at(dep_dim))) { - + if (is_connected_i_to_j || has_true_edge_i_to_j) throw loop_error( "Graph input for fusion has cycles not a DAG!!"); - + if (dvs[k].is_data_dependence() && dvs[k].has_negative_been_carried_at( dep_dim)) { - //g.connect(i, j, false); is_connected_j_to_i = true; break; } else { - //g.connect(i, j, true); - has_true_edge_j_to_i = true; - //break; } } - - // if (is_connected) - //break; - // if (is_connected) - //break; } - - - //if (is_connected) - // break; } - - + + if (is_connected_i_to_j) g.connect(i, j, false); else if (has_true_edge_i_to_j) g.connect(i, j, true); - + if (is_connected_j_to_i) g.connect(j, i, false); else if (has_true_edge_j_to_i) g.connect(j, i, true); - - + + } } return g; } std::vector<std::set<int> > Loop::typed_fusion(Graph<std::set<int>, bool> g) { - + bool roots[g.vertex.size()]; - + for (int i = 0; i < g.vertex.size(); i++) roots[i] = true; - + for (int i = 0; i < g.vertex.size(); i++) for (int j = i + 1; j < g.vertex.size(); j++) { - + if (g.hasEdge(i, j)) roots[j] = false; - + if (g.hasEdge(j, i)) roots[i] = false; - + } - + std::list<int> work_list; int cant_fuse_with[g.vertex.size()]; std::vector<std::set<int> > s; //Each Fused set's representative node - + int node_to_fused_nodes[g.vertex.size()]; int node_num[g.vertex.size()]; for (int i = 0; i < g.vertex.size(); i++) { @@ -1145,61 +1044,54 @@ std::vector<std::set<int> > Loop::typed_fusion(Graph<std::set<int>, bool> g) { node_num[i] = -1; } // topological sort according to chun's permute algorithm - // std::vector<std::set<int> > s = g.topoSort(); std::vector<std::set<int> > s2 = g.topoSort(); if (work_list.empty() || (s2.size() != g.vertex.size())) { - std::cout << s2.size() << "\t" << g.vertex.size() << std::endl; throw loop_error("Input for fusion not a DAG!!"); - - } int fused_nodes_counter = 0; while (!work_list.empty()) { int n = work_list.front(); - //int n_ = g.vertex[n].first; work_list.pop_front(); int node; if (cant_fuse_with[n] == 0) node = 0; else node = cant_fuse_with[n]; - + if ((fused_nodes_counter != 0) && (node != fused_nodes_counter)) { int rep_node = node_to_fused_nodes[node]; node_num[n] = node_num[rep_node]; - + try { update_successors(n, node_num, cant_fuse_with, g, work_list); } catch (const loop_error &e) { - + throw loop_error( "statements cannot be fused together due to negative dependence"); - - + + } for (std::set<int>::iterator it = g.vertex[n].first.begin(); it != g.vertex[n].first.end(); it++) s[node].insert(*it); } else { - //std::set<int> new_node; - //new_node.insert(n_); s.push_back(g.vertex[n].first); node_to_fused_nodes[node] = n; node_num[n] = ++node; try { update_successors(n, node_num, cant_fuse_with, g, work_list); } catch (const loop_error &e) { - + throw loop_error( "statements cannot be fused together due to negative dependence"); - - + + } fused_nodes_counter++; } } - + return s; } @@ -1207,7 +1099,7 @@ void Loop::setLexicalOrder(int dim, const std::set<int> &active, int starting_order, std::vector<std::vector<std::string> > idxNames) { if (active.size() == 0) return; - + // check for sanity of parameters if (dim < 0 || dim % 2 != 0) throw std::invalid_argument( @@ -1232,7 +1124,7 @@ void Loop::setLexicalOrder(int dim, const std::set<int> &active, "statements are not in the same sub loop nest"); } } - + // sepearate statements by current loop level types int level = (dim + 2) / 2; std::map<std::pair<LoopLevelType, int>, std::set<int> > active_by_level_type; @@ -1245,7 +1137,7 @@ void Loop::setLexicalOrder(int dim, const std::set<int> &active, stmt[*i].loop_level[level - 1].type, stmt[*i].loop_level[level - 1].payload)].insert(*i); } - + // further separate statements due to control dependences std::vector<std::set<int> > active_by_level_type_splitted; for (std::map<std::pair<LoopLevelType, int>, std::set<int> >::iterator i = @@ -1277,11 +1169,11 @@ void Loop::setLexicalOrder(int dim, const std::set<int> &active, active_by_level_type_splitted.push_back(not_controlled); } } - + // set lexical order separating loops with different loop types first if (active_by_level_type_splitted.size() + active_by_no_level.size() > 1) { int dep_dim = get_last_dep_dim_before(ref_stmt_num, level) + 1; - + Graph<std::set<int>, Empty> g; for (std::vector<std::set<int> >::iterator i = active_by_level_type_splitted.begin(); @@ -1342,13 +1234,13 @@ void Loop::setLexicalOrder(int dim, const std::set<int> &active, break; } } - + std::vector<std::set<int> > s = g.topoSort(); if (s.size() != g.vertex.size()) throw loop_error( "cannot separate statements with different loop types at loop level " + to_string(level)); - + // assign lexical order int order = starting_order; for (int i = 0; i < s.size(); i++) { @@ -1372,7 +1264,7 @@ void Loop::setLexicalOrder(int dim, const std::set<int> &active, std::set<int> nonsingles; std::map<coef_t, std::set<int> > fake_singles; std::set<int> fake_singles_; - + // sort out statements that do not require loops for (std::set<int>::iterator i = active.begin(); i != active.end(); i++) { @@ -1398,176 +1290,55 @@ void Loop::setLexicalOrder(int dim, const std::set<int> &active, } else nonsingles.insert(*i); } - - + + // split nonsingles forcibly according to negative dependences present (loop unfusible) int dep_dim = get_dep_dim_of(ref_stmt_num, level); - + if (dim < stmt[ref_stmt_num].xform.n_out() - 1) { - - bool dummy_level_found = false; - + std::vector<std::set<int> > s; - + s = sort_by_same_loops(active, level); bool further_levels_exist = false; - + if (!idxNames.empty()) if (level <= idxNames[ref_stmt_num].size()) if (idxNames[ref_stmt_num][level - 1].length() == 0) { - // && s.size() == 1) { + // Dummy level found int order1 = 0; - dummy_level_found = true; - + for (int i = level; i < idxNames[ref_stmt_num].size(); i++) if (idxNames[ref_stmt_num][i].length() > 0) further_levels_exist = true; - + } - - //if (!dummy_level_found) { - + if (s.size() > 1) { - + Graph<std::set<int>, bool> g = construct_induced_graph_at_level( s, dep, dep_dim); s = typed_fusion(g); } int order = 0; for (int i = 0; i < s.size(); i++) { - + for (std::set<int>::iterator it = s[i].begin(); it != s[i].end(); it++) assign_const(stmt[*it].xform, dim, order); - + if ((dim + 2) <= (stmt[ref_stmt_num].xform.n_out() - 1)) setLexicalOrder(dim + 2, s[i], order, idxNames); - + order++; } - //} - /* else { - - int order1 = 0; - int order = 0; - for (std::set<int>::iterator i = active.begin(); - i != active.end(); i++) { - if (!further_levels_exist) - assign_const(stmt[*i].xform, dim, order1++); - else - assign_const(stmt[*i].xform, dim, order1); - - } - - if ((dim + 2) <= (stmt[ref_stmt_num].xform.n_out() - 1) && further_levels_exist) - setLexicalOrder(dim + 2, active, order, idxNames); - } - */ } else { int dummy_order = 0; for (std::set<int>::iterator i = active.begin(); i != active.end(); i++) assign_const(stmt[*i].xform, dim, dummy_order++); } - /*for (int i = 0; i < g2.vertex.size(); i++) - for (int j = i+1; j < g2.vertex.size(); j++) { - std::vector<DependenceVector> dvs = dep.getEdge(g2.vertex[i].first, g2.vertex[j].first); - for (int k = 0; k < dvs.size(); k++) - if (dvs[k].is_control_dependence() || - (dvs[k].is_data_dependence() && dvs[k].has_negative_been_carried_at(dep_dim))) { - g2.connect(i, j); - break; - } - dvs = dep.getEdge(g2.vertex[j].first, g2.vertex[i].first); - for (int k = 0; k < dvs.size(); k++) - if (dvs[k].is_control_dependence() || - (dvs[k].is_data_dependence() && dvs[k].has_negative_been_carried_at(dep_dim))) { - g2.connect(j, i); - break; - } - } - - std::vector<std::set<int> > s2 = g2.packed_topoSort(); - - std::vector<std::set<int> > splitted_nonsingles; - for (int i = 0; i < s2.size(); i++) { - std::set<int> cur_scc; - for (std::set<int>::iterator j = s2[i].begin(); j != s2[i].end(); j++) - cur_scc.insert(g2.vertex[*j].first); - splitted_nonsingles.push_back(cur_scc); - } - */ - //convert to dependence graph for grouped statements - //dep_dim = get_last_dep_dim_before(ref_stmt_num, level) + 1; - /*int order = 0; - for (std::set<int>::iterator j = active.begin(); j != active.end(); - j++) { - std::set<int> continuous; - std::cout<< active.size()<<std::endl; - while (nonsingles.find(*j) != nonsingles.end() && j != active.end()) { - continuous.insert(*j); - j++; - } - - printf("continuous size is %d\n", continuous.size()); - - - - if (continuous.size() > 0) { - std::vector<std::set<int> > s = typed_fusion(continuous, dep, - dep_dim); - - for (int i = 0; i < s.size(); i++) { - for (std::set<int>::iterator l = s[i].begin(); - l != s[i].end(); l++) { - assign_const(stmt[*l].xform, dim + 2, order); - setLexicalOrder(dim + 2, s[i]); - } - order++; - } - } - - if (j != active.end()) { - assign_const(stmt[*j].xform, dim + 2, order); - - for (int k = dim + 4; k < stmt[*j].xform.n_out(); k += 2) - assign_const(stmt[*j].xform, k, 0); - order++; - } - - if( j == active.end()) - break; - } - */ - - - // assign lexical order - /*int order = starting_order; - for (int i = 0; i < s.size(); i++) { - // translate each SCC into original statements - std::set<int> cur_scc; - for (std::set<int>::iterator j = s[i].begin(); j != s[i].end(); j++) - copy(s[i].begin(), s[i].end(), - inserter(cur_scc, cur_scc.begin())); - - // now assign the constant - for (std::set<int>::iterator j = cur_scc.begin(); - j != cur_scc.end(); j++) - assign_const(stmt[*j].xform, dim, order); - - if (cur_scc.size() > 1) - setLexicalOrder(dim + 2, cur_scc); - else if (cur_scc.size() == 1) { - int cur_stmt = *(cur_scc.begin()); - for (int j = dim + 2; j < stmt[cur_stmt].xform.n_out(); j += 2) - assign_const(stmt[cur_stmt].xform, j, 0); - } - - if (cur_scc.size() > 0) - order++; - } - */ } } @@ -1586,15 +1357,15 @@ void Loop::apply_xform(int stmt_num) { void Loop::apply_xform(std::set<int> &active) { int max_n = 0; - + CG_outputBuilder *ocg = ir->builder(); for (std::set<int>::iterator i = active.begin(); i != active.end(); i++) { int n = stmt[*i].loop_level.size(); if (n > max_n) max_n = n; - + std::vector<int> lex = getLexicalOrder(*i); - + Relation mapping(2 * n + 1, n); F_And *f_root = mapping.add_and(); for (int j = 1; j <= n; j++) { @@ -1604,7 +1375,7 @@ void Loop::apply_xform(std::set<int> &active) { } mapping = Composition(mapping, stmt[*i].xform); mapping.simplify(); - + // match omega input/output variables to variable names in the code for (int j = 1; j <= stmt[*i].IS.n_set(); j++) mapping.name_input_var(j, stmt[*i].IS.set_var(j)->name()); @@ -1613,10 +1384,9 @@ void Loop::apply_xform(std::set<int> &active) { tmp_loop_var_name_prefix + to_string(tmp_loop_var_name_counter + j - 1)); mapping.setup_names(); - + Relation known = Extend_Set(copy(this->known), mapping.n_out() - this->known.n_set()); - //stmt[*i].code = outputStatement(ocg, stmt[*i].code, 0, mapping, known, std::vector<CG_outputRepr *>(mapping.n_out(), NULL)); std::vector<std::string> loop_vars; for (int j = 1; j <= stmt[*i].IS.n_set(); j++) loop_vars.push_back(stmt[*i].IS.set_var(j)->name()); @@ -1628,7 +1398,7 @@ void Loop::apply_xform(std::set<int> &active) { subs); stmt[*i].IS = Range(Restrict_Domain(mapping, stmt[*i].IS)); stmt[*i].IS.simplify(); - + // replace original transformation relation with straight 1-1 mapping mapping = Relation(n, 2 * n + 1); f_root = mapping.add_and(); @@ -1644,28 +1414,28 @@ void Loop::apply_xform(std::set<int> &active) { } stmt[*i].xform = mapping; } - + tmp_loop_var_name_counter += max_n; } void Loop::addKnown(const Relation &cond) { - + // invalidate saved codegen computation delete last_compute_cgr_; last_compute_cgr_ = NULL; delete last_compute_cg_; last_compute_cg_ = NULL; - + int n1 = this->known.n_set(); - + Relation r = copy(cond); int n2 = r.n_set(); - + if (n1 < n2) this->known = Extend_Set(this->known, n2 - n1); else if (n1 > n2) r = Extend_Set(r, n1 - n2); - + this->known = Intersection(this->known, r); } @@ -1677,7 +1447,7 @@ void Loop::removeDependence(int stmt_num_from, int stmt_num_to) { if (stmt_num_to >= stmt.size()) throw std::invalid_argument( "invalid statement number " + to_string(stmt_num_to)); - + dep.disconnect(stmt_num_from, stmt_num_to); } @@ -1712,7 +1482,7 @@ void Loop::dump() const { bool Loop::nonsingular(const std::vector<std::vector<int> > &T) { if (stmt.size() == 0) return true; - + // check for sanity of parameters for (int i = 0; i < stmt.size(); i++) { if (stmt[i].loop_level.size() != num_dep_dim) @@ -1750,11 +1520,11 @@ bool Loop::nonsingular(const std::vector<std::vector<int> > &T) { h.update_coef(mapping.output_var(i), -1); h.update_coef(mapping.input_var(i), 1); } - + // update transformation relations for (int i = 0; i < stmt.size(); i++) stmt[i].xform = Composition(copy(mapping), stmt[i].xform); - + // update dependence graph for (int i = 0; i < dep.vertex.size(); i++) for (DependenceGraph::EdgeList::iterator j = @@ -1809,7 +1579,7 @@ bool Loop::nonsingular(const std::vector<std::vector<int> > &T) { } dv.lbounds = lbounds; dv.ubounds = ubounds; - + break; } default: @@ -1818,13 +1588,13 @@ bool Loop::nonsingular(const std::vector<std::vector<int> > &T) { } j->second = dvs; } - + // set constant loop values std::set<int> active; for (int i = 0; i < stmt.size(); i++) active.insert(i); setLexicalOrder(0, active); - + return true; } @@ -1842,7 +1612,7 @@ bool Loop::is_dependence_valid_based_on_lex_order(int i, int j, last_dim = last_dim / 2; if (last_dim == 0) return true; - + for (int i = 0; i < last_dim; i++) { if (dv.lbounds[i] > 0) return true; @@ -1852,8 +1622,8 @@ bool Loop::is_dependence_valid_based_on_lex_order(int i, int j, } if (before) return true; - + return false; - + } |