chill doc

1 files changed, 0 insertions, 1127 deletions

diff --git a/chill/src/omegatools.cc b/chill/src/omegatools.cc
index cab66d4..3aac404 100644
--- a/chill/src/omegatools.cc
+++ b/chill/src/omegatools.cc
@@ -14,7 +14,6 @@
 *****************************************************************************/
 
 #include <code_gen/codegen.h>
-// #include <code_gen/output_repr.h>
 #include "omegatools.hh"
 #include "ir_code.hh"
 #include "chill_error.hh"
@@ -42,18 +41,9 @@ std::string tmp_e() {
   return std::string("e")+to_string(counter++);
 }
 
-
-
-//-----------------------------------------------------------------------------
-// Convert expression tree to omega relation.  "destroy" means shallow
-// deallocation of "repr", not freeing the actual code inside.
-// -----------------------------------------------------------------------------
 void exp2formula(IR_Code *ir, Relation &r, F_And *f_root, std::vector<Free_Var_Decl*> &freevars,
                  CG_outputRepr *repr, Variable_ID lhs, char side, IR_CONDITION_TYPE rel, bool destroy) {
   
-// void exp2formula(IR_Code *ir, Relation &r, F_And *f_root, std::vector<Free_Var_Decl*> &freevars,
-//                   CG_outputRepr *repr, Variable_ID lhs, char side, char rel, bool destroy) {
-  
   switch (ir->QueryExpOperation(repr)) {
   case IR_OP_CONSTANT:
   {
@@ -509,10 +499,6 @@ void exp2formula(IR_Code *ir, Relation &r, F_And *f_root, std::vector<Free_Var_D
   }
 }
 
-
-//-----------------------------------------------------------------------------
-// Build dependence relation for two array references.
-// -----------------------------------------------------------------------------
 Relation arrays2relation(IR_Code *ir, std::vector<Free_Var_Decl*> &freevars,
                          const IR_ArrayRef *ref_src, const Relation &IS_w,
                          const IR_ArrayRef *ref_dst, const Relation &IS_r) {
@@ -583,11 +569,6 @@ Relation arrays2relation(IR_Code *ir, std::vector<Free_Var_Decl*> &freevars,
   return r;
 }
 
-
-//-----------------------------------------------------------------------------
-// Convert array dependence relation into set of dependence vectors, assuming
-// ref_w is lexicographically before ref_r in the source code.
-// -----------------------------------------------------------------------------
 std::pair<std::vector<DependenceVector>, std::vector<DependenceVector> > relation2dependences (const IR_ArrayRef *ref_src, const IR_ArrayRef *ref_dst, const Relation &r) {
   assert(r.n_inp() == r.n_out());
   
@@ -815,11 +796,6 @@ std::pair<std::vector<DependenceVector>, std::vector<DependenceVector> > relatio
   return std::make_pair(dependences1, dependences2);
 }
 
-
-//-----------------------------------------------------------------------------
-// Convert a boolean expression to omega relation.  "destroy" means shallow
-// deallocation of "repr", not freeing the actual code inside.
-//-----------------------------------------------------------------------------
 void exp2constraint(IR_Code *ir, Relation &r, F_And *f_root,
                     std::vector<Free_Var_Decl *> &freevars,
                     CG_outputRepr *repr, bool destroy) {
@@ -862,739 +838,6 @@ void exp2constraint(IR_Code *ir, Relation &r, F_And *f_root,
   }
 }
 
-
-
-
-
-// inline void exp2formula(IR_Code *ir, Relation &r, F_And *f_root,
-//                         std::vector<Free_Var_Decl*> &freevars,
-//                         const CG_outputRepr *repr, Variable_ID lhs, char side, char rel) {
-//   exp2formula(ir, r, f_root, freevars, const_cast<CG_outputRepr *>(repr), lhs, side, rel, false);
-// }
-
-
-
-
-
-
-
-//-----------------------------------------------------------------------------
-// Convert suif expression tree to omega relation.
-//-----------------------------------------------------------------------------
-
-// void suif2formula(Relation &r, F_And *f_root,
-//                   std::vector<Free_Var_Decl*> &freevars,
-//                   operand op, Variable_ID lhs,
-//                   char side, char rel) {
-//   if (op.is_immed()) {
-//     immed im = op.immediate();
-
-//     if (im.is_integer()) {
-//       int c = im.integer();
-
-//       if (rel == '>') {
-//         GEQ_Handle h = f_root->add_GEQ();
-//         h.update_coef(lhs, 1);
-//         h.update_const(-1*c);
-//       }
-//       else if (rel == '<') {
-//         GEQ_Handle h = f_root->add_GEQ();
-//         h.update_coef(lhs, -1);
-//         h.update_const(c);
-//       }
-//       else { // '='
-//         EQ_Handle h = f_root->add_EQ();
-//         h.update_coef(lhs, 1);
-//         h.update_const(-1*c);
-//       }
-//     }
-//     else {
-//       return;  //add Function in the future
-//     }
-//   }
-//   else if (op.is_symbol()) {
-//     String s = op.symbol()->name();
-//     Variable_ID e = find_index(r, s, side);
-
-//     if (e == NULL) { // must be free variable
-//       Free_Var_Decl *t = NULL;
-//       for (unsigned i = 0; i < freevars.size(); i++) {
-//         String ss = freevars[i]->base_name();
-//         if (s == ss) {
-//           t = freevars[i];
-//           break;
-//         }
-//       }
-
-//       if (t == NULL) {
-//         t = new Free_Var_Decl(s);
-//         freevars.insert(freevars.end(), t);
-//       }
-
-//       e = r.get_local(t);
-//     }
-
-//     if (rel == '>') {
-//       GEQ_Handle h = f_root->add_GEQ();
-//       h.update_coef(lhs, 1);
-//       h.update_coef(e, -1);
-//     }
-//     else if (rel == '<') {
-//       GEQ_Handle h = f_root->add_GEQ();
-//       h.update_coef(lhs, -1);
-//       h.update_coef(e, 1);
-//     }
-//     else { // '='
-//       EQ_Handle h = f_root->add_EQ();
-//       h.update_coef(lhs, 1);
-//       h.update_coef(e, -1);
-//     }
-//   }
-//   else if (op.is_instr())
-//     suif2formula(r, f_root, freevars, op.instr(), lhs, side, rel);
-// }
-
-
-// void suif2formula(Relation &r, F_And *f_root,
-//                   std::vector<Free_Var_Decl*> &freevars,
-//                   instruction *ins, Variable_ID lhs,
-//                   char side, char rel) {
-//   if (ins->opcode() == io_cpy) {
-//     suif2formula(r, f_root, freevars, ins->src_op(0), lhs, side, rel);
-//   }
-//   else if (ins->opcode() == io_add || ins->opcode() == io_sub) {
-//     F_Exists *f_exists = f_root->add_exists();
-//     Variable_ID e1 = f_exists->declare(tmp_e());
-//     Variable_ID e2 = f_exists->declare(tmp_e());
-//     F_And *f_and = f_exists->add_and();
-
-//     int add_or_sub = ins->opcode() == io_add ? 1 : -1;
-//     if (rel == '>') {
-//       GEQ_Handle h = f_and->add_GEQ();
-//       h.update_coef(lhs, 1);
-//       h.update_coef(e1, -1);
-//       h.update_coef(e2, -1 * add_or_sub);
-//     }
-//     else if (rel == '<') {
-//       GEQ_Handle h = f_and->add_GEQ();
-//       h.update_coef(lhs, -1);
-//       h.update_coef(e1, 1);
-//       h.update_coef(e2, 1 * add_or_sub);
-//     }
-//     else { // '='
-//       EQ_Handle h = f_and->add_EQ();
-//       h.update_coef(lhs, 1);
-//       h.update_coef(e1, -1);
-//       h.update_coef(e2, -1 * add_or_sub);
-//     }
-
-//     suif2formula(r, f_and, freevars, ins->src_op(0), e1, side, '=');
-//     suif2formula(r, f_and, freevars, ins->src_op(1), e2, side, '=');
-//   }
-//   else if (ins->opcode() == io_mul) {
-//     operand op1 = ins->src_op(0);
-//     operand op2 = ins->src_op(1);
-
-//     if (!op1.is_immed() && !op2.is_immed())
-//       return;  // add Function in the future
-//     else {
-//       operand op;
-//       immed im;
-//       if (op1.is_immed()) {
-//         im = op1.immediate();
-//         op = op2;
-//       }
-//       else {
-//         im = op2.immediate();
-//         op = op1;
-//       }
-
-//       if (!im.is_integer())
-//         return; //add Function in the future
-//       else {
-//         int c = im.integer();
-
-//         F_Exists *f_exists = f_root->add_exists();
-//         Variable_ID e = f_exists->declare(tmp_e());
-//         F_And *f_and = f_exists->add_and();
-
-//         if (rel == '>') {
-//           GEQ_Handle h = f_and->add_GEQ();
-//           h.update_coef(lhs, 1);
-//           h.update_coef(e, -c);
-//         }
-//         else if (rel == '<') {
-//           GEQ_Handle h = f_and->add_GEQ();
-//           h.update_coef(lhs, -1);
-//           h.update_coef(e, c);
-//         }
-//         else {
-//           EQ_Handle h = f_and->add_EQ();
-//           h.update_coef(lhs, 1);
-//           h.update_coef(e, -c);
-//         }
-
-//         suif2formula(r, f_and, freevars, op, e, side, '=');
-//       }
-//     }
-//   }
-//   else if (ins->opcode() == io_div) {
-//     operand op1 = ins->src_op(0);
-//     operand op2 = ins->src_op(1);
-
-//     if (!op2.is_immed())
-//       return;  //add Function in the future
-//     else {
-//       immed im = op2.immediate();
-
-//       if (!im.is_integer())
-//         return;  //add Function in the future
-//       else {
-//         int c = im.integer();
-
-//         F_Exists *f_exists = f_root->add_exists();
-//         Variable_ID e = f_exists->declare(tmp_e());
-//         F_And *f_and = f_exists->add_and();
-
-//         if (rel == '>') {
-//           GEQ_Handle h = f_and->add_GEQ();
-//           h.update_coef(lhs, c);
-//           h.update_coef(e, -1);
-//         }
-//         else if (rel == '<') {
-//           GEQ_Handle h = f_and->add_GEQ();
-//           h.update_coef(lhs, -c);
-//           h.update_coef(e, 1);
-//         }
-//         else {
-//           EQ_Handle h = f_and->add_EQ();
-//           h.update_coef(lhs, c);
-//           h.update_coef(e, -1);
-//         }
-
-//         suif2formula(r, f_and, freevars, op1, e, side, '=');
-//       }
-//     }
-//   }       
-//   else if (ins->opcode() == io_neg) {    
-//     F_Exists *f_exists = f_root->add_exists();
-//     Variable_ID e = f_exists->declare(tmp_e());
-//     F_And *f_and = f_exists->add_and();
-
-//     if (rel == '>') {
-//       GEQ_Handle h = f_and->add_GEQ();
-//       h.update_coef(lhs, 1);
-//       h.update_coef(e, 1);
-//     }
-//     else if (rel == '<') {
-//       GEQ_Handle h = f_and->add_GEQ();
-//       h.update_coef(lhs, -1);
-//       h.update_coef(e, -1);
-//     }
-//     else {
-//       EQ_Handle h = f_and->add_EQ();
-//       h.update_coef(lhs, 1);
-//       h.update_coef(e, 1);
-//     }
-
-//     suif2formula(r, f_and, freevars, ins->src_op(0), e, side, '=');
-//   }
-//   else if (ins->opcode() == io_min) {
-//     operand op1 = ins->src_op(0);
-//     operand op2 = ins->src_op(1);
-
-//     F_Exists *f_exists = f_root->add_exists();
-//     Variable_ID e1 = f_exists->declare(tmp_e());
-//     Variable_ID e2 = f_exists->declare(tmp_e());
-//     F_And *f_and = f_exists->add_and();
-
-//     if (rel == '>') {
-//       F_Or *f_or = f_and->add_or();
-//       F_And *f_and1 = f_or->add_and();
-//       GEQ_Handle h1 = f_and1->add_GEQ();
-//       h1.update_coef(lhs, 1);
-//       h1.update_coef(e1, -1);
-//       F_And *f_and2 = f_or->add_and();
-//       GEQ_Handle h2 = f_and2->add_GEQ();
-//       h2.update_coef(lhs, 1);
-//       h2.update_coef(e2, -1);
-//     }
-//     else if (rel == '<') {
-//       GEQ_Handle h1 = f_and->add_GEQ();
-//       h1.update_coef(lhs, -1);
-//       h1.update_coef(e1, 1);
-//       GEQ_Handle h2 = f_and->add_GEQ();
-//       h2.update_coef(lhs, -1);
-//       h2.update_coef(e2, 1);
-//     }
-//     else {
-//       F_Or *f_or = f_and->add_or();
-//       F_And *f_and1 = f_or->add_and();
-//       EQ_Handle h1 = f_and1->add_EQ();
-//       h1.update_coef(lhs, 1);
-//       h1.update_coef(e1, -1);
-//       GEQ_Handle h2 = f_and1->add_GEQ();
-//       h2.update_coef(e1, -1);
-//       h2.update_coef(e2, 1);
-//       F_And *f_and2 = f_or->add_and();
-//       EQ_Handle h3 = f_and2->add_EQ();
-//       h3.update_coef(lhs, 1);
-//       h3.update_coef(e2, -1);
-//       GEQ_Handle h4 = f_and2->add_GEQ();
-//       h4.update_coef(e1, 1);
-//       h4.update_coef(e2, -1);
-//     }
-
-//     suif2formula(r, f_and, freevars, op1, e1, side, '=');
-//     suif2formula(r, f_and, freevars, op2, e2, side, '=');
-//   }
-//   else if (ins->opcode() == io_max) {
-//     operand op1 = ins->src_op(0);
-//     operand op2 = ins->src_op(1);
-
-//     F_Exists *f_exists = f_root->add_exists();
-//     Variable_ID e1 = f_exists->declare(tmp_e());
-//     Variable_ID e2 = f_exists->declare(tmp_e());
-//     F_And *f_and = f_exists->add_and();
-
-//     if (rel == '>') {
-//       GEQ_Handle h1 = f_and->add_GEQ();
-//       h1.update_coef(lhs, 1);
-//       h1.update_coef(e1, -1);
-//       GEQ_Handle h2 = f_and->add_GEQ();
-//       h2.update_coef(lhs, 1);
-//       h2.update_coef(e2, -1);
-//     }
-//     else if (rel == '<') {
-//       F_Or *f_or = f_and->add_or();
-//       F_And *f_and1 = f_or->add_and();
-//       GEQ_Handle h1 = f_and1->add_GEQ();
-//       h1.update_coef(lhs, -1);
-//       h1.update_coef(e1, 1);
-//       F_And *f_and2 = f_or->add_and();
-//       GEQ_Handle h2 = f_and2->add_GEQ();
-//       h2.update_coef(lhs, -1);
-//       h2.update_coef(e2, 1);
-//     }
-//     else {
-//       F_Or *f_or = f_and->add_or();
-//       F_And *f_and1 = f_or->add_and();
-//       EQ_Handle h1 = f_and1->add_EQ();
-//       h1.update_coef(lhs, 1);
-//       h1.update_coef(e1, -1);
-//       GEQ_Handle h2 = f_and1->add_GEQ();
-//       h2.update_coef(e1, 1);
-//       h2.update_coef(e2, -1);
-//       F_And *f_and2 = f_or->add_and();
-//       EQ_Handle h3 = f_and2->add_EQ();
-//       h3.update_coef(lhs, 1);
-//       h3.update_coef(e2, -1);
-//       GEQ_Handle h4 = f_and2->add_GEQ();
-//       h4.update_coef(e1, -1);
-//       h4.update_coef(e2, 1);
-//     }
-
-//     suif2formula(r, f_and, freevars, op1, e1, side, '=');
-//     suif2formula(r, f_and, freevars, op2, e2, side, '=');
-//   }      
-// }
-
-//-----------------------------------------------------------------------------
-// Generate iteration space constraints
-//-----------------------------------------------------------------------------
-
-// void add_loop_stride_constraints(Relation &r, F_And *f_root,
-//                                  std::vector<Free_Var_Decl*> &freevars,
-//                                  tree_for *tnf, char side) {
-
-//   std::string name(tnf->index()->name());
-//   int dim = 0;
-//   for (;dim < r.n_set(); dim++)
-//     if (r.set_var(dim+1)->name() == name)
-//       break;
-
-//   Relation bound = get_loop_bound(r, dim);
-
-//   operand op = tnf->step_op();
-//   if (!op.is_null()) {
-//     if (op.is_immed()) {
-//       immed im = op.immediate();
-//       if (im.is_integer()) {
-//         int c = im.integer();
-
-//         if (c != 1 && c != -1)
-//           add_loop_stride(r, bound, dim, c);
-//       }
-//       else
-//         assert(0); // messy stride
-//     }
-//     else
-//       assert(0);  // messy stride
-//   }
-// }
-
-// void add_loop_bound_constraints(IR_Code *ir, Relation &r, F_And *f_root,
-//                                 std::vector<Free_Var_Decl*> &freevars,
-//                                 tree_for *tnf,
-//                                 char upper_or_lower, char side, IR_CONDITION_TYPE rel) {
-//   Variable_ID v = find_index(r, tnf->index()->name(), side);
-
-//   tree_node_list *tnl;
-
-//   if (upper_or_lower == 'u')
-//     tnl = tnf->ub_list();
-//   else
-//     tnl = tnf->lb_list();
-
-//   tree_node_list_iter iter(tnl);
-//   while (!iter.is_empty()) {
-//     tree_node *tn = iter.step();
-//     if (tn->kind() != TREE_INSTR)
-//       break; // messy bounds
-
-//     instruction *ins = static_cast<tree_instr *>(tn)->instr();
-
-
-//     if (upper_or_lower == 'u' && (tnf->test() == FOR_SLT || tnf->test() == FOR_ULT)) {
-//       operand op1(ins->clone());
-//       operand op2(new in_ldc(type_s32, operand(), immed(1)));
-//       instruction *t = new in_rrr(io_sub, op1.type(), operand(), op1, op2);
-
-//       CG_suifRepr *repr = new CG_suifRepr(operand(t));
-//       exp2formula(ir, r, f_root, freevars, repr, v, side, rel, true);
-//       delete t;
-//     }
-//     else if (tnf->test() == FOR_SLT || tnf->test() == FOR_SLTE || tnf->test() == FOR_ULT || tnf->test() == FOR_ULTE) {
-//       CG_suifRepr *repr = new CG_suifRepr(operand(ins));
-//       exp2formula(ir, r, f_root, freevars, repr, v, side, rel, true);
-//     }
-//     else
-//       assert(0);
-//   }
-// } 
-
-
-// Relation loop_iteration_space(std::vector<Free_Var_Decl*> &freevars,
-//                               tree_node *tn, std::vector<tree_for*> &loops) {
-//   Relation r(loops.size());
-//   for (unsigned i = 0; i < loops.size(); i++) {
-//     String s = loops[i]->index()->name();
-//     r.name_set_var(i+1, s);
-//   }
-
-//   F_And *f_root = r.add_and();
-
-//   std::vector<tree_for *> outer = find_outer_loops(tn);
-//   std::vector<LexicalOrderType> loops_lex(loops.size(), LEX_UNKNOWN);
-
-//   for (unsigned i = 0; i < outer.size(); i++) {
-//     unsigned j;
-
-//     for (j = 0; j < loops.size(); j++) {
-//       if (outer[i] == loops[j]) {
-//         loops_lex[j] = LEX_MATCH;
-//         break;
-//       } else if (outer[i]->index() == loops[j]->index()) {
-//         loops_lex[j] = lexical_order(outer[i],loops[j]);
-//         break;
-//       }
-//     }
-
-//     if (j != loops.size()) {
-//       add_loop_bound_constraints(r, f_root, freevars, outer[i], 'l', 's', '>');
-//       add_loop_bound_constraints(r, f_root, freevars, outer[i], 'u', 's', '<');
-//       add_loop_stride_constraints(r,f_root, freevars, outer[i], 's');
-//     }
-//   }
-
-//   // Add degenerated constraints for non-enclosing loops for this
-//   // statement. We treat low-dim space as part of whole
-//   // iteration space.
-//   LexicalOrderType lex = LEX_MATCH;
-//   for (unsigned i = 0; i < loops.size(); i++) {
-//     if (loops_lex[i] != 0) {
-//       if (lex == LEX_MATCH)
-//         lex = loops_lex[i];
-//       continue;
-//     }
-
-//     if (lex == LEX_MATCH) {
-//       for (unsigned j = i+1; j < loops.size(); j++) {
-//         if (loops_lex[j] == LEX_BEFORE || loops_lex[j] == LEX_AFTER) {
-//           lex = loops_lex[j];
-//           break;
-//         }
-//       }
-//     }
-
-//     if (lex == LEX_MATCH)
-//       lex = lexical_order(tn, loops[i]);
-
-//     if (lex == LEX_BEFORE)
-//       add_loop_bound_constraints(r, f_root, freevars, loops[i], 'l', 's', '=');
-//     else
-//       add_loop_bound_constraints(r, f_root, freevars, loops[i], 'u', 's', '=');
-//   }
-
-//   return r;
-// }
-
-// Relation arrays2relation(std::vector<Free_Var_Decl*> &freevars,
-//                          in_array *ia_w, const Relation &IS1_,
-//                          in_array *ia_r, const Relation &IS2_) {
-//   Relation &IS1 = const_cast<Relation &>(IS1_);
-//   Relation &IS2 = const_cast<Relation &>(IS2_);
-
-//   Relation r(IS1.n_set(), IS2.n_set());
-
-//   for (int i = 1; i <= IS1.n_set(); i++)
-//     r.name_input_var(i, IS1.set_var(i)->name());
-
-//   for (int i = 1; i <= IS2.n_set(); i++)
-//     r.name_output_var(i, IS2.set_var(i)->name()+"'");
-
-//   if (get_sym_of_array(ia_w) != get_sym_of_array(ia_r)) {
-//     r.add_or(); // False Relation
-//     return r;
-//   }
-
-//   F_And *f_root = r.add_and();
-
-//   for (unsigned i = 0; i < ia_w->dims(); i++) {
-//     F_Exists *f_exists = f_root->add_exists();
-//     Variable_ID e = f_exists->declare(tmp_e());
-//     F_And *f_and = f_exists->add_and();
-
-//     suif2formula(r, f_and, freevars, ia_w->index(i), e, 'w', '=');
-//     suif2formula(r, f_and, freevars, ia_r->index(i), e, 'r', '=');
-//   }
-
-//   // add iteration space restriction
-//   r = Restrict_Domain(r, copy(IS1));
-//   r = Restrict_Range(r, copy(IS2));
-
-//   // reset the output variable names lost in restriction
-//   for (int i = 1; i <= IS2.n_set(); i++)
-//     r.name_output_var(i, IS2.set_var(i)->name()+"'");
-
-//   return r;
-// }
-
-
-// std::vector<DependenceVector> relation2dependences (IR_Code *ir, in_array *ia_w, in_array *ia_r, const Relation &r) {
-//   assert(r.n_inp() == r.n_out());
-
-//   std::vector<DependenceVector> dependences;
-
-//   std::stack<DependenceLevel> working;
-//   working.push(DependenceLevel(r, r.n_inp()));
-
-//   while (!working.empty()) {
-//     DependenceLevel dep = working.top();
-//     working.pop();
-
-//     // No dependence exists, move on.
-//     if (!dep.r.is_satisfiable())
-//       continue;
-
-//     if (dep.level == r.n_inp()) {
-//       DependenceVector dv;
-
-//       // for loop independent dependence, use lexical order to
-//       // determine the correct source and destination
-//       if (dep.dir == 0) {
-//         LexicalOrderType order = lexical_order(ia_w->parent(), ia_r->parent());
-
-//         if (order == LEX_MATCH)
-//           continue; //trivial self zero-dependence
-//         else if (order == LEX_AFTER) {
-//           dv.src = new IR_suifArrayRef(ir, ia_r);
-//           dv.dst = new IR_suifArrayRef(ir, ia_w);
-//         }
-//         else {
-//           dv.src = new IR_suifArrayRef(ir, ia_w);
-//           dv.dst = new IR_suifArrayRef(ir,ia_r);
-//         }
-//       }
-//       else if (dep.dir == 1) {
-//         dv.src = new IR_suifArrayRef(ir, ia_w);
-//         dv.dst = new IR_suifArrayRef(ir, ia_r);
-//       }
-//       else { // dep.dir == -1
-//         dv.src = new IR_suifArrayRef(ir, ia_r);
-//         dv.dst = new IR_suifArrayRef(ir, ia_w);
-//       }
-
-//       dv.lbounds = dep.lbounds;
-//       dv.ubounds = dep.ubounds;
-
-//  //      // set the dependence type
-// //       if (is_lhs(dv.source) && is_lhs(dv.dest))
-// //         dv.type = 'o';
-// //       else if (!is_lhs(dv.source) && ! is_lhs(dv.dest))
-// //         dv.type = 'i';
-// //       else if (is_lhs(dv.source))
-// //         dv.type = 'f';
-// //       else
-// //         dv.type = 'a';
-
-//       dependences.push_back(dv);
-//     }
-//     else {
-//       // now work on the next dimension level
-//       int level = ++dep.level;
-
-//       coef_t lbound, ubound;
-//       Relation delta = Deltas(copy(dep.r));
-//       delta.query_variable_bounds(delta.set_var(level), lbound, ubound);
-
-//       if (dep.dir == 0) {
-//         if (lbound > 0) {
-//           dep.dir = 1;
-//           dep.lbounds[level-1] = lbound;
-//           dep.ubounds[level-1] = ubound;
-
-//           working.push(dep);
-//         }
-//         else if (ubound < 0) {
-//           dep.dir = -1;
-//           dep.lbounds[level-1] = -ubound;
-//           dep.ubounds[level-1] = -lbound;
-
-//           working.push(dep);
-//         }
-//         else {
-//           // split the dependence vector into flow- and anti-dependence
-//           // for the first non-zero distance, also separate zero distance
-//           // at this level.
-//           {
-//             DependenceLevel dep2 = dep;
-
-//             dep2.lbounds[level-1] =  0;
-//             dep2.ubounds[level-1] =  0;
-
-//             F_And *f_root = dep2.r.and_with_and();
-//             EQ_Handle h = f_root->add_EQ();
-//             h.update_coef(dep2.r.input_var(level), 1);
-//             h.update_coef(dep2.r.output_var(level), -1);
-
-//             working.push(dep2);
-//           }
-
-//           if (lbound < 0 && ia_w != ia_r) {
-//             DependenceLevel dep2 = dep;
-
-//             F_And *f_root = dep2.r.and_with_and();
-//             GEQ_Handle h = f_root->add_GEQ();
-//             h.update_coef(dep2.r.input_var(level), 1);
-//             h.update_coef(dep2.r.output_var(level), -1);
-//             h.update_const(-1);
-
-//             // get tighter bounds under new constraints
-//             coef_t lbound, ubound;
-//             delta = Deltas(copy(dep2.r));
-//             delta.query_variable_bounds(delta.set_var(level),
-//                                         lbound, ubound);
-
-//             dep2.dir = -1;            
-//             dep2.lbounds[level-1] = max(-ubound,static_cast<coef_t>(1)); // use max() to avoid Omega retardness
-//             dep2.ubounds[level-1] = -lbound;
-
-//             working.push(dep2);
-//           }
-
-//           if (ubound > 0) {
-//             DependenceLevel dep2 = dep;
-
-//             F_And *f_root = dep2.r.and_with_and();
-//             GEQ_Handle h = f_root->add_GEQ();
-//             h.update_coef(dep2.r.input_var(level), -1);
-//             h.update_coef(dep2.r.output_var(level), 1);
-//             h.update_const(-1);
-
-//             // get tighter bonds under new constraints
-//             coef_t lbound, ubound;
-//             delta = Deltas(copy(dep2.r));
-//             delta.query_variable_bounds(delta.set_var(level),
-//                                         lbound, ubound);
-//             dep2.dir = 1;
-//             dep2.lbounds[level-1] = max(lbound,static_cast<coef_t>(1)); // use max() to avoid Omega retardness
-//             dep2.ubounds[level-1] = ubound;
-
-//             working.push(dep2);
-//           }
-//         }
-//       }
-//       // now deal with dependence vector with known direction
-//       // determined at previous levels
-//       else {
-//         // For messy bounds, further test to see if the dependence distance
-//         // can be reduced to positive/negative.  This is an omega hack.
-//         if (lbound == negInfinity && ubound == posInfinity) {
-//           {
-//             Relation t = dep.r;
-//             F_And *f_root = t.and_with_and();
-//             GEQ_Handle h = f_root->add_GEQ();
-//             h.update_coef(t.input_var(level), 1);
-//             h.update_coef(t.output_var(level), -1);
-//             h.update_const(-1);
-
-//             if (!t.is_satisfiable()) {
-//               lbound = 0;
-//             }
-//           }
-//           {
-//             Relation t = dep.r;
-//             F_And *f_root = t.and_with_and();
-//             GEQ_Handle h = f_root->add_GEQ();
-//             h.update_coef(t.input_var(level), -1);
-//             h.update_coef(t.output_var(level), 1);
-//             h.update_const(-1);
-
-//             if (!t.is_satisfiable()) {
-//               ubound = 0;
-//             }
-//           }
-//         }
-
-//         // Same thing as above, test to see if zero dependence
-//         // distance possible.
-//         if (lbound == 0 || ubound == 0) {
-//           Relation t = dep.r;
-//           F_And *f_root = t.and_with_and();
-//           EQ_Handle h = f_root->add_EQ();
-//           h.update_coef(t.input_var(level), 1);
-//           h.update_coef(t.output_var(level), -1);
-
-//           if (!t.is_satisfiable()) {
-//             if (lbound == 0)
-//               lbound = 1;
-//             if (ubound == 0)
-//               ubound = -1;
-//           }
-//         }
-
-//         if (dep.dir == -1) {
-//           dep.lbounds[level-1] = -ubound;
-//           dep.ubounds[level-1] = -lbound;
-//         }
-//         else { // dep.dir == 1
-//           dep.lbounds[level-1] = lbound;
-//           dep.ubounds[level-1] = ubound;
-//         }
-
-//         working.push(dep);
-//       }
-//     }
-//   }
-
-//   return dependences;
-// }
-
-//-----------------------------------------------------------------------------
-// Determine whether the loop (starting from 0) in the iteration space
-// has only one iteration.
-//-----------------------------------------------------------------------------
 bool is_single_loop_iteration(const Relation &r, int level, const Relation &known) {
   int n = r.n_set();
   Relation r1 = Intersection(copy(r), Extend_Set(copy(known), n-known.n_set()));
@@ -1626,8 +869,6 @@ bool is_single_loop_iteration(const Relation &r, int level, const Relation &know
 }
 
 
-
-
 bool is_single_iteration(const Relation &r, int dim) {
   assert(r.is_set());
   const int n = r.n_set();
@@ -1637,11 +878,6 @@ bool is_single_iteration(const Relation &r, int dim) {
   
   Relation bound = get_loop_bound(r, dim);
   
-//   if (!bound.has_single_conjunct())
-//     return false;
-  
-//   Conjunct *c = bound.query_DNF()->single_conjunct();
-  
   for (DNF_Iterator di(bound.query_DNF()); di; di++) {
     bool is_single = false;
     for (EQ_Iterator ei((*di)->EQs()); ei; ei++)
@@ -1655,78 +891,8 @@ bool is_single_iteration(const Relation &r, int dim) {
   }
   
   return true;
-  
-  
-  
-  
-//   Relation r = copy(r_);
-//   const int n = r.n_set();
-  
-//   if (dim >= n)
-//     return true;
-  
-//   Relation bound = get_loop_bound(r, dim);
-//   bound = Approximate(bound);
-//   Conjunct *c = bound.query_DNF()->single_conjunct();
-  
-//   return c->n_GEQs() == 0;
-  
-  
-  
-  
-  
-//   Relation r = copy(r_);
-//   r.simplify();
-//   const int n = r.n_set();
-  
-//   if (dim >= n)
-//     return true;
-  
-//   for (DNF_Iterator i(r.query_DNF()); i; i++) {
-//     std::vector<bool> is_single(n);
-//     for (int j = 0; j < dim; j++)
-//       is_single[j] = true;
-//     for (int j = dim; j < n; j++)
-//       is_single[j] = false;
-  
-//     bool found_new_single = true;
-//     while (found_new_single) {
-//       found_new_single = false;
-  
-//       for (EQ_Iterator j = (*i)->EQs(); j; j++) {
-//         int saved_pos = -1;
-//         for (Constr_Vars_Iter k(*j); k; k++)
-//           if ((*k).var->kind() == Set_Var || (*k).var->kind() == Input_Var) {
-//             int pos = (*k).var->get_position() - 1;
-//             if (!is_single[pos])
-//               if (saved_pos == -1)
-//                 saved_pos = pos;
-//               else {
-//                 saved_pos = -1;
-//                 break;
-//               }
-//           }
-  
-//         if (saved_pos != -1) {
-//           is_single[saved_pos] = true;
-//           found_new_single = true;
-//         }
-//       }
-  
-//       if (is_single[dim])
-//         break;
-//     }
-  
-//     if (!is_single[dim])
-//       return false;
-//   }
-  
-//   return true;
 }
 
-//-----------------------------------------------------------------------------
-// Set/get the value of a variable which is know to be constant.
-//-----------------------------------------------------------------------------
 void assign_const(Relation &r, int dim, int val) {
   const int n = r.n_out();
   
@@ -1751,14 +917,10 @@ void assign_const(Relation &r, int dim, int val) {
 
 
 int get_const(const Relation &r, int dim, Var_Kind type) {
-//  Relation rr = copy(r);
   Relation &rr = const_cast<Relation &>(r);
   
   Variable_ID v;
   switch (type) {
-    // case Set_Var:
-    //   v = rr.set_var(dim+1);
-    //   break;
   case Input_Var:
     v = rr.input_var(dim+1);
     break;
@@ -1777,19 +939,10 @@ int get_const(const Relation &r, int dim, Var_Kind type) {
   throw std::runtime_error("cannot get variable's constant value");
 }
 
-
-
-
-
-
-//---------------------------------------------------------------------------
-// Get the bound for a specific loop.
-//---------------------------------------------------------------------------
 Relation get_loop_bound(const Relation &r, int dim) {
   assert(r.is_set());
   const int n = r.n_set();
   
-//  Relation r1 = project_onto_levels(copy(r), dim+1, true);
   Relation mapping(n,n);
   F_And *f_root = mapping.add_and();
   for (int i = 1; i <= dim+1; i++) {
@@ -1864,12 +1017,6 @@ Relation get_min_loop_bound(const std::vector<Relation> &r, int dim) {
   return res;
 }
 
-//-----------------------------------------------------------------------------
-// Add strident to a loop.
-// Issues:
-// - Don't work with relations with multiple disjuncts.
-// - Omega's dealing with max lower bound is awkward.
-//-----------------------------------------------------------------------------
 void add_loop_stride(Relation &r, const Relation &bound_, int dim, int stride) {
   F_And *f_root = r.and_with_and();
   Relation &bound = const_cast<Relation &>(bound_);
@@ -1953,15 +1100,6 @@ bool is_inner_loop_depend_on_level(const Relation &r, int level, const Relation
   return false;
 }
 
-
-//-----------------------------------------------------------------------------
-// Suppose loop dim is i. Replace i with i+adjustment in loop bounds.
-// e.g. do i = 1, n
-//        do j = i, n
-// after call with dim = 0 and adjustment = 1:
-//      do i = 1, n
-//        do j = i+1, n
-// -----------------------------------------------------------------------------
 Relation adjust_loop_bound(const Relation &r, int level, int adjustment) {
   if (adjustment == 0)
     return copy(r);
@@ -1998,236 +1136,6 @@ Relation adjust_loop_bound(const Relation &r, int level, int adjustment) {
   return r1;
 }
 
-
-// commented out on 07/14/2010
-// void adjust_loop_bound(Relation &r, int dim, int adjustment, std::vector<Free_Var_Decl *> globals) {
-//   assert(r.is_set());
-
-//   if (adjustment == 0)
-//     return;
-
-//   const int n = r.n_set();
-//   Tuple<std::string> name(n);
-//   for (int i = 1; i <= n; i++)
-//     name[i] = r.set_var(i)->name();
-
-//   Relation r1 = project_onto_levels(copy(r), dim+1, true);
-//   Relation r2 = Gist(copy(r), copy(r1));
-
-//   // remove old bogus global variable conditions since we are going to
-//   // update the value.
-//   if (globals.size() > 0)
-//     r1 = Gist(r1, project_onto_levels(copy(r), 0, true));
-
-//   Relation r4 = Relation::True(n);
-
-//     for (DNF_Iterator di(r2.query_DNF()); di; di++) {
-//       for (EQ_Iterator ei = (*di)->EQs(); ei; ei++) {
-//         EQ_Handle h = r4.and_with_EQ(*ei);
-
-//         Variable_ID v = r2.set_var(dim+1);
-//         coef_t c = (*ei).get_coef(v);
-//         if (c != 0)
-//           h.update_const(c*adjustment);
-
-//         for (int i = 0; i < globals.size(); i++) {  
-//           Variable_ID v = r2.get_local(globals[i]);
-//           coef_t c = (*ei).get_coef(v);
-//           if (c != 0)
-//             h.update_const(c*adjustment);
-//         }
-//       }
-
-//       for (GEQ_Iterator gi = (*di)->GEQs(); gi; gi++) {
-//         GEQ_Handle h = r4.and_with_GEQ(*gi);
-
-//         Variable_ID v = r2.set_var(dim+1);
-//         coef_t c = (*gi).get_coef(v);
-//         if (c != 0)
-//           h.update_const(c*adjustment);
-
-//         for (int i = 0; i < globals.size(); i++) {  
-//           Variable_ID v = r2.get_local(globals[i]);
-//           coef_t c = (*gi).get_coef(v);
-//           if (c != 0)
-//             h.update_const(c*adjustment);
-//         }
-//       }
-//     }
-//     r = Intersection(r1, r4);
-// //   }
-// //   else
-// //     r = Intersection(r1, r2);
-
-//   for (int i = 1; i <= n; i++)
-//     r.name_set_var(i, name[i]);
-//   r.setup_names();
-// }
-
-
-// void adjust_loop_bound(Relation &r, int dim, int adjustment) {
-//   assert(r.is_set());
-//   const int n = r.n_set();
-//   Tuple<String> name(n);
-//   for (int i = 1; i <= n; i++)
-//     name[i] = r.set_var(i)->name();
-
-//   Relation r1 = project_onto_levels(copy(r), dim+1, true);
-//   Relation r2 = Gist(r, copy(r1));
-
-//   Relation r3(n, n);
-//   F_And *f_root = r3.add_and();
-//   for (int i = 0; i < n; i++) {
-//     EQ_Handle h = f_root->add_EQ();
-//     h.update_coef(r3.output_var(i+1), 1);
-//     h.update_coef(r3.input_var(i+1), -1);
-//     if (i == dim)
-//       h.update_const(adjustment);
-//   }
-
-//   r2 = Range(Restrict_Domain(r3, r2));
-//   r = Intersection(r1, r2);
-
-//   for (int i = 1; i <= n; i++)
-//     r.name_set_var(i, name[i]);
-//   r.setup_names();
-// }  
-
-// void adjust_loop_bound(Relation &r, int dim, Free_Var_Decl *global_var, int adjustment) {
-//   assert(r.is_set());
-//   const int n = r.n_set();
-//   Tuple<String> name(n);
-//   for (int i = 1; i <= n; i++)
-//     name[i] = r.set_var(i)->name();
-
-//   Relation r1 = project_onto_levels(copy(r), dim+1, true);
-//   Relation r2 = Gist(r, copy(r1));
-
-//   Relation r3(n);
-//   Variable_ID v = r2.get_local(global_var);
-
-//   for (DNF_Iterator di(r2.query_DNF()); di; di++) {
-//     for (EQ_Iterator ei = (*di)->EQs(); ei; ei++) {
-//       coef_t c = (*ei).get_coef(v);
-//       EQ_Handle h = r3.and_with_EQ(*ei);
-//       if (c != 0)
-//         h.update_const(c*adjustment);
-//     }
-//     for (GEQ_Iterator gi = (*di)->GEQs(); gi; gi++) {
-//       coef_t c = (*gi).get_coef(v);
-//       GEQ_Handle h = r3.and_with_GEQ(*gi);
-//       if (c != 0)
-//         h.update_const(c*adjustment);
-//     }
-//   }
-
-//   r = Intersection(r1, r3);
-//   for (int i = 1; i <= n; i++)
-//     r.name_set_var(i, name[i]);
-//   r.setup_names();
-// }
-
-
-
-//------------------------------------------------------------------------------
-// If the dimension has value posInfinity, the statement should be privatized
-// at this dimension.
-//------------------------------------------------------------------------------
-// boolean is_private_statement(const Relation &r, int dim) {
-//   int n;
-//   if (r.is_set())
-//     n = r.n_set();
-//   else
-//     n = r.n_out();
-
-//   if (dim >= n)
-//     return false;
-
-//   try {
-//     coef_t c;
-//     if (r.is_set())
-//       c = get_const(r, dim, Set_Var);
-//     else
-//       c = get_const(r, dim, Output_Var);
-//     if (c == posInfinity)
-//       return true;
-//     else
-//       return false;
-//   }
-//   catch (loop_error e){
-//   }
-
-//   return false;
-// }
-
-
-
-// // ----------------------------------------------------------------------------
-// // Calculate v mod dividend based on equations inside relation r.
-// // Return posInfinity if it is not a constant.
-// // ----------------------------------------------------------------------------
-// static coef_t mod_(const Relation &r_, Variable_ID v, int dividend, std::set<Variable_ID> &working_on) {
-//   assert(dividend > 0);
-//   if (v->kind() == Forall_Var || v->kind() == Exists_Var || v->kind() == Wildcard_Var)
-//     return posInfinity;
-
-//   working_on.insert(v);
-
-//   Relation &r = const_cast<Relation &>(r_);
-//   Conjunct *c = r.query_DNF()->single_conjunct();
-
-//   for (EQ_Iterator ei(c->EQs()); ei; ei++) {
-//     int coef = mod((*ei).get_coef(v), dividend);
-//     if (coef != 1 && coef != dividend - 1 )
-//       continue;
-
-//     coef_t result = 0;
-//     for (Constr_Vars_Iter cvi(*ei); cvi; cvi++)
-//       if ((*cvi).var != v) {
-//         int p = mod((*cvi).coef, dividend);
-
-//         if (p == 0)
-//           continue;
-
-//         if (working_on.find((*cvi).var) != working_on.end()) {
-//           result = posInfinity;
-//           break;
-//         }
-
-//         coef_t q = mod_(r, (*cvi).var, dividend, working_on);
-//         if (q == posInfinity) {
-//           result = posInfinity;
-//           break;
-//         }
-//         result += p * q;
-//       }
-
-//     if (result != posInfinity) {
-//       result += (*ei).get_const();
-//       if (coef == 1)
-//         result = -result;
-//       working_on.erase(v);
-
-//       return mod(result, dividend);
-//     }
-//   }
-
-//   working_on.erase(v);
-//   return posInfinity;
-// }
-
-
-// coef_t mod(const Relation &r, Variable_ID v, int dividend) {
-//   std::set<Variable_ID> working_on = std::set<Variable_ID>();
-
-//   return mod_(r, v, dividend, working_on);
-// }
-
-
-
-//-----------------------------------------------------------------------------
-// Generate mapping relation for permuation.
-//-----------------------------------------------------------------------------
 Relation permute_relation(const std::vector<int> &pi) {
   const int n = pi.size();
   
@@ -2243,11 +1151,6 @@ Relation permute_relation(const std::vector<int> &pi) {
   return r;
 }
 
-
-
-//---------------------------------------------------------------------------
-// Find the position index variable in a Relation by name.
-//---------------------------------------------------------------------------
 Variable_ID find_index(Relation &r, const std::string &s, char side) {
   // Omega quirks: assure the names are propagated inside the relation
   r.setup_names();
@@ -2280,33 +1183,3 @@ Variable_ID find_index(Relation &r, const std::string &s, char side) {
   return NULL;
 }
 
-// EQ_Handle get_eq(const Relation &r, int dim, Var_Kind type) {
-//   Variable_ID v;
-//   switch (type) {
-//   case Set_Var:
-//     v = r.set_var(dim+1);
-//     break;
-//   case Input_Var:
-//     v = r.input_var(dim+1);
-//     break;
-//   case Output_Var:
-//     v = r.output_var(dim+1);
-//     break;
-//   default:
-//     return NULL;
-//   }
-//   for (DNF_iterator di(r.query_DNF()); di; di++)
-//     for (EQ_Iterator ei = (*di)->EQs(); ei; ei++)
-//       if ((*ei).get_coef(v) != 0)
-//         return (*ei);
-
-//   return NULL;
-// }
-
-
-// std::Pair<Relation, Relation> split_loop(const Relation &r, const Relation &cond) {
-//   Relation r1 = Intersection(copy(r), copy(cond));
-//   Relation r2 = Intersection(copy(r), Complement(copy(cond)));
-
-//   return std::Pair<Relation, Relation>(r1, r2);
-// }