13 files changed, 1391 insertions, 0 deletions
diff --git a/chill/include/chill_error.hh b/chill/include/chill_error.hh
new file mode 100644
index 0000000..dc7432f
--- /dev/null
+++ b/chill/include/chill_error.hh
@@ -0,0 +1,19 @@
+#ifndef CHILL_ERROR_HH
+#define CHILL_ERROR_HH
+
+// for loop transformation problem
+struct loop_error: public std::runtime_error {
+  loop_error(const std::string &msg): std::runtime_error(msg){}
+};
+
+// for generic compiler intermediate code handling problem
+struct ir_error: public std::runtime_error {
+  ir_error(const std::string &msg): std::runtime_error(msg){}
+};
+
+// specific for expression to preburger math translation problem
+struct ir_exp_error: public ir_error {
+  ir_exp_error(const std::string &msg): ir_error(msg){}
+};
+
+#endif
diff --git a/chill/include/chill_run_util.hh b/chill/include/chill_run_util.hh
new file mode 100644
index 0000000..8df5871
--- /dev/null
+++ b/chill/include/chill_run_util.hh
@@ -0,0 +1,29 @@
+#ifndef CHILL_RUN_UTIL_HH
+#define CHILL_RUN_UTIL_HH
+
+#include <vector>
+#include <map>
+#include <string>
+
+typedef std::map<std::string, int>               simap_t;
+typedef std::vector<std::map<std::string, int> > simap_vec_t;
+
+// in chill_run_util.cc
+simap_vec_t* make_prog(simap_vec_t* cond);
+simap_vec_t* make_cond_gt(simap_t* lhs, simap_t* rhs);
+simap_vec_t* make_cond_lt(simap_t* lhs, simap_t* rhs);
+simap_vec_t* make_cond_ge(simap_t* lhs, simap_t* rhs);
+simap_vec_t* make_cond_le(simap_t* lhs, simap_t* rhs);
+simap_vec_t* make_cond_eq(simap_t* lhs, simap_t* rhs);
+simap_t* make_cond_item_add(simap_t* lhs, simap_t* rhs);
+simap_t* make_cond_item_sub(simap_t* lhs, simap_t* rhs);
+simap_t* make_cond_item_mul(simap_t* lhs, simap_t* rhs);
+simap_t* make_cond_item_neg(simap_t* expr);
+simap_t* make_cond_item_number(int n);
+simap_t* make_cond_item_variable(const char* var);
+simap_t* make_cond_item_level(int n);
+
+// in parse_expr.yy
+simap_vec_t* parse_relation_vector(const char* expr);
+
+#endif
diff --git a/chill/include/chilldebug.h b/chill/include/chilldebug.h
new file mode 100644
index 0000000..4abbb82
--- /dev/null
+++ b/chill/include/chilldebug.h
@@ -0,0 +1,11 @@
+
+// a central place to turn on debugging messages
+
+// enable the next line to get lots of output 
+//#define DEBUGCHILL
+
+#ifdef DEBUGCHILL 
+#define DEBUG_PRINT(args...) fprintf(stderr, args )
+#else
+#define DEBUG_PRINT(args...)    /* Don't do anything  */
+#endif
diff --git a/chill/include/chillmodule.hh b/chill/include/chillmodule.hh
new file mode 100644
index 0000000..a64ad1b
--- /dev/null
+++ b/chill/include/chillmodule.hh
@@ -0,0 +1,21 @@
+#ifndef BASIC_CHILLMODULE_HH
+#define BASIC_CHILLMODULE_HH
+// TODO    Python.h defines these and something else does too 
+#undef _POSIX_C_SOURCE
+#undef _XOPEN_SOURCE
+
+#include <Python.h>
+
+// a C routine that will be called from python
+//static PyObject * chill_print_code(PyObject *self, PyObject *args);
+
+//static PyMethodDef ChillMethods[] ; 
+
+#ifndef CUDACHILL
+void finalize_loop(int loop_num_start, int loop_num_end);
+int get_loop_num_start();
+int get_loop_num_end();
+#endif
+
+PyMODINIT_FUNC initchill() ;   // pass C methods to python
+#endif
diff --git a/chill/include/config.h.in b/chill/include/config.h.in
new file mode 100644
index 0000000..77e32da
--- /dev/null
+++ b/chill/include/config.h.in
@@ -0,0 +1,32 @@
+/* include/config.h.in.  Generated from configure.ac by autoheader.  */
+
+/* Use ROSE */
+#undef BUILD_ROSE
+
+/* Name of package */
+#undef PACKAGE
+
+/* Define to the address where bug reports for this package should be sent. */
+#undef PACKAGE_BUGREPORT
+
+/* Define to the full name of this package. */
+#undef PACKAGE_NAME
+
+/* Define to the full name and version of this package. */
+#undef PACKAGE_STRING
+
+/* Define to the one symbol short name of this package. */
+#undef PACKAGE_TARNAME
+
+/* Define to the home page for this package. */
+#undef PACKAGE_URL
+
+/* Define to the version of this package. */
+#undef PACKAGE_VERSION
+
+/* Version number of package */
+#undef VERSION
+
+/* Define to 1 if `lex' declares `yytext' as a `char *' by default, not a
+   `char[]'. */
+#undef YYTEXT_POINTER
diff --git a/chill/include/dep.hh b/chill/include/dep.hh
new file mode 100644
index 0000000..1fa1280
--- /dev/null
+++ b/chill/include/dep.hh
@@ -0,0 +1,85 @@
+#ifndef DEP_HH
+#define DEP_HH
+
+#include <omega.h>
+#include "graph.hh"
+#include "ir_code.hh"
+#include "chill_error.hh"
+
+enum DependenceType { DEP_W2R, DEP_R2W, DEP_W2W, DEP_R2R, DEP_CONTROL, DEP_UNKNOWN };
+
+class DependenceVector;
+typedef std::vector<DependenceVector> DependenceList;
+
+struct DependenceVector {
+  DependenceType type;
+  IR_Symbol *sym;
+  
+  bool is_reduction; // used to identify a class of flow dependence
+                     // that can be broken
+  std::vector<omega::coef_t> lbounds;
+  std::vector<omega::coef_t> ubounds;
+  
+  bool quasi;
+  bool is_scalar_dependence;
+  DependenceVector() {
+    type = DEP_UNKNOWN;
+    sym = NULL;
+    is_reduction = false;
+    quasi = false;
+    is_scalar_dependence = false;
+  }
+  // DependenceVector(int size);
+  DependenceVector(const DependenceVector &that);
+  ~DependenceVector() {delete sym;}
+  DependenceVector &operator=(const DependenceVector &that);
+  
+  bool is_data_dependence() const;
+  bool is_control_dependence() const;
+  bool has_negative_been_carried_at(int dim) const;
+  bool has_been_carried_at(int dim) const;
+  bool has_been_carried_before(int dim) const;
+  
+  // the following functions will be cleaned up or removed later
+  bool isZero() const;
+  bool isPositive() const;
+  bool isNegative() const;
+  bool isAllPositive() const;
+  bool isAllNegative() const;
+  bool isZero(int dim) const;
+  bool hasPositive(int dim) const;
+  bool hasNegative(int dim) const;
+  bool isCarried(int dim, omega::coef_t distance = posInfinity) const;
+  bool canPermute(const std::vector<int> &pi) const;
+  
+  std::vector<DependenceVector> normalize() const;
+  std::vector<DependenceVector> permute(const std::vector<int> &pi) const;
+  DependenceVector reverse() const;
+  // std::vector<DependenceVector> matrix(const std::vector<std::vector<int> > &M) const;
+  DependenceType getType() const;
+  friend std::ostream& operator<<(std::ostream &os, const DependenceVector &d);
+};
+
+
+
+class DependenceGraph: public Graph<Empty, DependenceVector> {
+  
+protected:
+  int num_dim_;
+  
+public:
+  DependenceGraph(int n) { num_dim_ = n; }
+  DependenceGraph() { num_dim_ = 0; }
+  ~DependenceGraph() {}
+  int num_dim() const { return num_dim_; }
+//   DependenceGraph permute(const std::vector<int> &pi) const;
+  DependenceGraph permute(const std::vector<int> &pi,
+                          const std::set<int> &active = std::set<int>()) const;
+  // DependenceGraph matrix(const std::vector<std::vector<int> > &M) const;
+  DependenceGraph subspace(int dim) const;
+  bool isPositive() const;
+  bool hasPositive(int dim) const;
+  bool hasNegative(int dim) const;
+};
+
+#endif
diff --git a/chill/include/graph.hh b/chill/include/graph.hh
new file mode 100644
index 0000000..f8471df
--- /dev/null
+++ b/chill/include/graph.hh
@@ -0,0 +1,319 @@
+/*****************************************************************************
+ Copyright (C) 2008 University of Southern California
+ Copyright (C) 2010 University of Utah
+ All Rights Reserved.
+
+ Purpose:
+   Graph<VertexType, EdgeType> template class supports topological sort
+ with return result observing strongly connected component.
+
+ Notes:
+   The result of topologically sorting a graph V={1,2,3,4} and E={1->2, 1->3,
+ 2->3, 3->2, 3->4} is ({1}, {2,3}, {4}).
+ 
+ History:
+   01/2006 Created by Chun Chen.
+   07/2010 add a new topological order, -chun
+*****************************************************************************/
+
+#ifndef GRAPH_HH
+#define GRAPH_HH
+
+#include <set>
+#include <vector>
+#include <map>
+#include <iostream>
+#include <stack>
+#include <algorithm>
+#include <assert.h>
+
+struct Empty {
+  Empty() {};
+  bool operator<(const Empty &) const { return true; };
+  bool operator==(const Empty &) const { return false; };
+  friend std::ostream& operator<<(std::ostream &os, const Empty &) { return os; };
+};
+
+namespace {
+  enum GraphColorType {WHITE, GREY, BLACK};
+}
+
+template<typename VertexType, typename EdgeType> struct Graph;
+template<typename VertexType, typename EdgeType> std::ostream& operator<<(std::ostream &os, const Graph<VertexType, EdgeType> &g);
+
+template<typename VertexType = Empty, typename EdgeType = Empty>
+struct Graph {
+  typedef std::map<int, std::vector<EdgeType> > EdgeList;
+  typedef std::vector<std::pair<VertexType, EdgeList> > VertexList;
+
+  VertexList vertex;
+  bool directed;
+
+  Graph(bool directed = true);
+  
+  int vertexCount() const;
+  int edgeCount() const;
+  bool isEmpty() const;
+  bool isDirected() const;
+  int insert(const VertexType &v = VertexType());
+  void connect(int v1, int v2, const EdgeType &e = EdgeType());
+  void connect(int v1, int v2, const std::vector<EdgeType> &e);
+  void disconnect(int v1, int v2);
+  bool hasEdge(int v1, int v2) const;
+  std::vector<EdgeType> getEdge(int v1, int v2) const;
+  
+  std::vector<std::set<int> > topoSort() const;
+  std::vector<std::set<int> > packed_topoSort() const;
+
+  void dump() {
+    std::cout << *this;
+  }
+  
+  friend std::ostream& operator<< <>(std::ostream &os, const Graph<VertexType, EdgeType> &g);
+};
+
+template<typename VertexType, typename EdgeType>
+std::ostream& operator<<(std::ostream &os, const Graph<VertexType, EdgeType> &g) {
+  for (int i = 0; i < g.vertex.size(); i++)
+    for (typename Graph<VertexType,EdgeType>::EdgeList::const_iterator j = g.vertex[i].second.begin(); j != g.vertex[i].second.end(); j++) {
+	//      os << i+1 << "->" << j->first+1 << ":";
+	os << "s" << i << "->" << "s" << j->first << ":";
+      for (typename std::vector<EdgeType>::const_iterator k = j->second.begin(); k != j->second.end(); k++)
+        os << " " << *k;
+      os << std::endl;
+    }
+
+  return os;
+}
+
+
+template<typename VertexType, typename EdgeType>
+Graph<VertexType, EdgeType>::Graph(bool directed_):
+  directed(directed_) {
+}
+
+template<typename VertexType, typename EdgeType>
+int Graph<VertexType, EdgeType>::vertexCount() const {
+  return vertex.size();
+}
+
+template<typename VertexType, typename EdgeType>
+int Graph<VertexType, EdgeType>::edgeCount() const {
+  int result = 0;
+
+  for (int i = 0; i < vertex.size(); i++)
+    for (typename EdgeList::const_iterator j = vertex[i].second.begin(); j != vertex[i].second.end(); j++)
+      result += j->second.size();
+
+  if (!directed)
+    result = result/2;
+  
+  return result;
+}
+
+template<typename VertexType, typename EdgeType>
+bool Graph<VertexType, EdgeType>::isEmpty() const {
+  return vertex.size() == 0;
+}
+
+template<typename VertexType, typename EdgeType>
+bool Graph<VertexType, EdgeType>::isDirected() const {
+  return directed;
+}
+
+template<typename VertexType, typename EdgeType>
+int Graph<VertexType, EdgeType>::insert(const VertexType & v) {
+  for (int i = 0; i < vertex.size(); i++)
+    if (vertex[i].first == v)
+      return i;
+
+  vertex.push_back(std::make_pair(v, EdgeList()));
+  return vertex.size() - 1;
+}
+  
+  
+template<typename VertexType, typename EdgeType>
+void Graph<VertexType, EdgeType>::connect(int v1, int v2, const EdgeType &e)  {
+  assert(v1 < vertex.size() && v2 < vertex.size());
+
+  vertex[v1].second[v2].push_back(e);;
+  if (!directed)
+    vertex[v2].second[v1].push_back(e);
+}
+
+template<typename VertexType, typename EdgeType>
+void Graph<VertexType, EdgeType>::connect(int v1, int v2, const std::vector<EdgeType> &e)  {
+  assert(v1 < vertex.size() && v2 < vertex.size());
+
+  if (e.size() == 0)
+    return;
+  
+  copy(e.begin(), e.end(), back_inserter(vertex[v1].second[v2]));
+  if (!directed)
+    copy(e.begin(), e.end(), back_inserter(vertex[v2].second[v1]));
+}
+
+template<typename VertexType, typename EdgeType>
+void Graph<VertexType, EdgeType>::disconnect(int v1, int v2)  {
+  assert(v1 < vertex.size() && v2 < vertex.size());
+
+  vertex[v1].second.erase(v2);
+  if (!directed)
+    vertex[v2].second.erase(v1);
+}
+
+template<typename VertexType, typename EdgeType>
+bool Graph<VertexType,EdgeType>::hasEdge(int v1, int v2) const {
+  return vertex[v1].second.find(v2) != vertex[v1].second.end();
+}
+
+template<typename VertexType, typename EdgeType>
+std::vector<EdgeType> Graph<VertexType,EdgeType>::getEdge(int v1, int v2) const {
+  if (!hasEdge(v1, v2))
+    return std::vector<EdgeType>();
+
+  return vertex[v1].second.find(v2)->second;
+}
+
+// This topological sort does handle SCC in graph.
+template<typename VertexType, typename EdgeType>
+std::vector<std::set<int> > Graph<VertexType, EdgeType>::topoSort() const {
+  const int n = vertex.size();
+  std::vector<GraphColorType> color(n, WHITE);
+  std::stack<int> S;
+
+  std::vector<int> order(n);
+  int c = n;
+  
+  // first DFS
+  for (int i = n-1; i >= 0; i--)
+    if (color[i] == WHITE) {
+      S.push(i);
+      while (!S.empty()) {
+        int v = S.top();
+
+        if (color[v] == WHITE) {
+          for (typename EdgeList::const_iterator j = vertex[v].second.begin(); j != vertex[v].second.end(); j++)
+            if (color[j->first] == WHITE)
+              S.push(j->first);
+
+          color[v] = GREY;
+        }
+        else if (color[v] == GREY) {
+          color[v] = BLACK;
+          S.pop();
+          order[--c] = v;
+        }
+        else {
+          S.pop();
+        }
+      }
+    }
+
+  // transpose edge
+  std::vector<std::set<int> > edgeT(n);
+  for (int i = 0; i < n; i++)
+    for (typename EdgeList::const_iterator j = vertex[i].second.begin(); j != vertex[i].second.end(); j++)
+      edgeT[j->first].insert(i);
+  
+  // second DFS in transposed graph starting from last finished vertex
+  fill(color.begin(), color.end(), WHITE);
+  std::vector<std::set<int> > result;
+  for (int i = 0; i < n; i++)
+    if (color[order[i]] == WHITE) {
+      std::set<int> s;
+      
+      S.push(order[i]);
+      while (!S.empty()) {
+        int v = S.top();
+      
+        if(color[v] == WHITE) {
+          for (std::set<int>::const_iterator j = edgeT[v].begin(); j != edgeT[v].end(); j++)
+            if (color[*j] == WHITE)
+              S.push(*j);
+
+          color[v] = GREY;
+        }
+        else if (color[v] == GREY) {
+          color[v] = BLACK;
+          S.pop();
+          s.insert(v);
+        }
+        else {
+          S.pop();
+        }
+      }
+
+      result.push_back(s);
+    }
+
+  return result;
+}
+
+// This topological sort does not handle SCC in graph.
+template<typename VertexType, typename EdgeType>
+std::vector<std::set<int> > Graph<VertexType, EdgeType>::packed_topoSort() const {
+  const int n = vertex.size();
+  std::vector<GraphColorType> color(n, WHITE);
+  std::stack<int> S;
+
+  std::vector<bool> is_root(n, false);
+  std::vector<std::set<int> > edges(n);
+  
+  // first DFS
+  for (int i = n-1; i >= 0; i--)
+    if (color[i] == WHITE) {
+      S.push(i);
+      is_root[i] = true;
+      while (!S.empty()) {
+        int v = S.top();
+
+        if (color[v] == WHITE) {
+          for (typename EdgeList::const_iterator j = vertex[v].second.begin(); j != vertex[v].second.end(); j++)
+            if (color[j->first] == WHITE) {
+              S.push(j->first);
+              edges[v].insert(j->first);
+            }
+            else if (color[j->first] == BLACK) {
+              if (is_root[j->first]) {
+                is_root[j->first] = false;
+                edges[v].insert(j->first);
+              }
+            }
+
+          color[v] = GREY;
+        }
+        else if (color[v] == GREY) {
+          color[v] = BLACK;
+          S.pop();
+        }
+        else {
+          S.pop();
+        }
+      }
+    }
+
+
+  // second BFS in DFS tree starting from roots
+  std::vector<std::set<int> > result;
+  std::set<int> s;
+  for (int i = 0; i < n; i++)
+    if (is_root[i])
+      s.insert(i);
+  if (s.size() != 0) {
+    result.push_back(s);
+    while (true) {
+      std::set<int> s;
+      for (std::set<int>::iterator i = result[result.size()-1].begin(); i != result[result.size()-1].end(); i++)
+        s.insert(edges[*i].begin(), edges[*i].end());
+      if (s.size() != 0)
+        result.push_back(s);
+      else
+        break;
+    }
+  }
+
+  return result;
+}
+
+#endif
diff --git a/chill/include/ir_code.hh b/chill/include/ir_code.hh
new file mode 100644
index 0000000..1f853fa
--- /dev/null
+++ b/chill/include/ir_code.hh
@@ -0,0 +1,263 @@
+/*****************************************************************************
+ Copyright (C) 2009-2010 University of Utah
+ All Rights Reserved.
+
+ Purpose:
+   CHiLL's compiler intermediate representation interface that extends
+ Omega's builder interface to accomodate compiler analyses and
+ extra code generation.
+.
+ Notes:
+   Unlike CG_outputRepr, IR_Symbol,IR_Ref and IR_Control are place holders
+ to the underlying code, thus deleting or duplicating them does not affect
+ the actual code.  Similar to Omega builder's memory allocation strategy,
+ all non-const pointer parameters of CG_outputRepr/IR_Symbol/IR_Ref/IR_Control
+ are destroyed after the call.
+
+ History:
+   02/2009 Created by Chun Chen.
+   06/2010 Add IR_Control interface, by chun.  
+*****************************************************************************/
+
+#ifndef IR_CODE_HH
+#define IR_CODE_HH
+
+#include <code_gen/CG_outputRepr.h>
+#include <code_gen/CG_outputBuilder.h>
+#include <vector>
+
+enum IR_OPERATION_TYPE    {IR_OP_CONSTANT, IR_OP_VARIABLE,
+                           IR_OP_PLUS, IR_OP_MINUS, IR_OP_MULTIPLY, IR_OP_DIVIDE,
+                           IR_OP_POSITIVE, IR_OP_NEGATIVE,
+                           IR_OP_MIN, IR_OP_MAX,
+                           IR_OP_ASSIGNMENT,
+                           IR_OP_NULL, IR_OP_UNKNOWN};
+enum IR_CONTROL_TYPE      {IR_CONTROL_LOOP, IR_CONTROL_IF, IR_CONTROL_WHILE, IR_CONTROL_BLOCK};
+enum IR_CONSTANT_TYPE     {IR_CONSTANT_INT, IR_CONSTANT_FLOAT,
+                           IR_CONSTANT_UNKNOWN};
+enum IR_CONDITION_TYPE    {IR_COND_LT, IR_COND_LE,
+                           IR_COND_GT, IR_COND_GE,
+                           IR_COND_EQ, IR_COND_NE,
+                           IR_COND_UNKNOWN};
+enum IR_ARRAY_LAYOUT_TYPE {IR_ARRAY_LAYOUT_ROW_MAJOR,
+                           IR_ARRAY_LAYOUT_COLUMN_MAJOR,
+                           IR_ARRAY_LAYOUT_SPACE_FILLING};
+
+class IR_Code;
+
+
+// Base abstract class for scalar and array symbols.  This is a place
+// holder for related declaration in IR code.
+struct IR_Symbol {
+  const IR_Code *ir_;
+  
+  virtual ~IR_Symbol() {/* ir_ is not the responsibility of this object */}
+  virtual int n_dim() const = 0;
+  virtual std::string name() const = 0;
+  virtual bool operator==(const IR_Symbol &that) const = 0;
+  virtual bool operator!=(const IR_Symbol &that) const {return !(*this == that);}
+  virtual IR_Symbol *clone() const = 0;  /* shallow copy */
+};
+
+
+struct IR_ScalarSymbol: public IR_Symbol {
+  virtual ~IR_ScalarSymbol() {}
+  int n_dim() const {return 0;}
+  virtual int size() const = 0;
+};
+
+
+struct IR_ArraySymbol: public IR_Symbol {
+  virtual ~IR_ArraySymbol() {}
+  virtual int elem_size() const = 0;
+  virtual omega::CG_outputRepr *size(int dim) const = 0;
+  virtual IR_ARRAY_LAYOUT_TYPE layout_type() const = 0;
+};
+
+
+// Base abstract class for scalar and array references.  This is a
+// place holder for related code in IR code.
+struct IR_Ref {
+  const IR_Code *ir_;
+  
+  virtual ~IR_Ref() {/* ir_ is not the responsibility of this object */}
+  virtual int n_dim() const = 0;
+  virtual bool is_write() const = 0;
+  virtual std::string name() const = 0;
+  virtual bool operator==(const IR_Ref &that) const = 0;
+  virtual bool operator!=(const IR_Ref &that) const {return !(*this == that);}
+  virtual omega::CG_outputRepr *convert() = 0;
+  virtual IR_Ref *clone() const = 0;  /* shallow copy */
+};
+
+
+struct IR_ConstantRef: public IR_Ref {
+  IR_CONSTANT_TYPE type_;
+
+  virtual ~IR_ConstantRef() {}
+  int n_dim() const {return 0;}
+  bool is_write() const {return false;}
+  std::string name() const {return std::string();}
+  virtual bool is_integer() const {return type_ == IR_CONSTANT_INT;}
+  virtual omega::coef_t integer() const = 0;
+};
+  
+
+struct IR_ScalarRef: public IR_Ref {
+  virtual ~IR_ScalarRef() {}
+  int n_dim() const {return 0;}
+  virtual IR_ScalarSymbol *symbol() const = 0;
+  std::string name() const {
+    IR_ScalarSymbol *sym = symbol();
+    std::string s = sym->name();
+    delete sym;
+    return s;
+  }
+  virtual int size() const {
+    IR_ScalarSymbol *sym = symbol();
+    int s = sym->size();
+    delete sym;
+    return s;
+  }
+};
+
+
+struct IR_ArrayRef: public IR_Ref {
+  virtual ~IR_ArrayRef() {}
+  int n_dim() const {
+    IR_ArraySymbol *sym = symbol();
+    int n = sym->n_dim();
+    delete sym;
+    return n;
+  }
+  virtual omega::CG_outputRepr *index(int dim) const = 0;
+  virtual IR_ArraySymbol *symbol() const = 0;
+  std::string name() const {
+    IR_ArraySymbol *sym = symbol();
+    std::string s = sym->name();
+    delete sym;
+    return s;
+  }
+  virtual int elem_size() const {
+    IR_ArraySymbol *sym = symbol();
+    int s = sym->elem_size();
+    delete sym;
+    return s;
+  }
+  virtual IR_ARRAY_LAYOUT_TYPE layout_type() const {
+    IR_ArraySymbol *sym = symbol();
+    IR_ARRAY_LAYOUT_TYPE t = sym->layout_type();
+    delete sym;
+    return t;
+  }
+};
+
+
+struct IR_Block;
+
+// Base abstract class for code structures.  This is a place holder
+// for the actual structure in the IR code.  However, in cases that
+// original source code may be transformed during loop initialization
+// such as converting a while loop to a for loop or reconstructing the
+// loop from low level IR code, the helper loop class (NOT
+// IMPLEMENTED) must contain the transformed code that needs to be
+// freed when out of service.
+struct IR_Control {
+  const IR_Code *ir_;
+
+  virtual ~IR_Control() {/* ir_ is not the responsibility of this object */}
+  virtual IR_CONTROL_TYPE type() const = 0;
+  virtual IR_Block *convert() = 0;
+  virtual IR_Control *clone() const = 0;  /* shallow copy */
+};
+
+
+struct IR_Loop: public IR_Control {  
+  virtual ~IR_Loop() {}
+  virtual IR_ScalarSymbol *index() const = 0;
+  virtual omega::CG_outputRepr *lower_bound() const = 0;
+  virtual omega::CG_outputRepr *upper_bound() const = 0;
+  virtual IR_CONDITION_TYPE stop_cond() const = 0;
+  virtual IR_Block *body() const = 0;
+  virtual int step_size() const = 0;
+  IR_CONTROL_TYPE type() const { return IR_CONTROL_LOOP; }
+};
+
+
+struct IR_Block: public IR_Control {
+  virtual ~IR_Block() {}
+  virtual omega::CG_outputRepr *extract() const = 0;
+  IR_Block *convert() {return this;}
+  IR_CONTROL_TYPE type() const { return IR_CONTROL_BLOCK; }
+  virtual omega::CG_outputRepr *original() const = 0;
+};
+
+
+struct IR_If: public IR_Control {
+  virtual ~IR_If() {}
+  virtual omega::CG_outputRepr *condition() const = 0;
+  virtual IR_Block *then_body() const = 0;
+  virtual IR_Block *else_body() const = 0;
+  IR_CONTROL_TYPE type() const { return IR_CONTROL_IF; }
+};
+
+
+  
+struct IR_While: public IR_Control {
+  // NOT IMPLEMENTED
+};
+
+
+// Abstract class for compiler IR.
+class IR_Code {
+protected:
+  omega::CG_outputBuilder *ocg_;
+  omega::CG_outputRepr *init_code_;
+  omega::CG_outputRepr *cleanup_code_;
+
+public:
+  IR_Code() {ocg_ = NULL; init_code_ = cleanup_code_ = NULL;}
+  virtual ~IR_Code() { delete ocg_; delete init_code_; delete cleanup_code_; } /* the content of init and cleanup code have already been released in derived classes */
+  
+  // memory_type is for differentiating the location of where the new memory is allocated.
+  // this is useful for processors with heterogeneous memory hierarchy.
+  virtual IR_ScalarSymbol *CreateScalarSymbol(const IR_Symbol *sym, int memory_type) = 0;
+  virtual IR_ArraySymbol *CreateArraySymbol(const IR_Symbol *sym, std::vector<omega::CG_outputRepr *> &size, int memory_type) = 0;
+  
+  virtual IR_ScalarRef *CreateScalarRef(const IR_ScalarSymbol *sym) = 0;
+  virtual IR_ArrayRef *CreateArrayRef(const IR_ArraySymbol *sym, std::vector<omega::CG_outputRepr *> &index) = 0;
+  virtual int ArrayIndexStartAt() {return 0;}
+
+  // Array references should be returned in their accessing order.
+  // e.g. s1: A[i] = A[i-1]
+  //      s2: B[C[i]] = D[i] + E[i]
+  // return A[i-1], A[i], D[i], E[i], C[i], B[C[i]] in this order.
+  virtual std::vector<IR_ArrayRef *> FindArrayRef(const omega::CG_outputRepr *repr) const = 0;
+  virtual std::vector<IR_ScalarRef *> FindScalarRef(const omega::CG_outputRepr *repr) const = 0;
+
+  // If there is no sub structure interesting inside the block, return empty,
+  // so we know when to stop looking inside.
+  virtual std::vector<IR_Control *> FindOneLevelControlStructure(const IR_Block *block) const = 0;
+
+  // All controls must be in the same block, at the same level and in
+  // contiguous lexical order as appeared in parameter vector.
+  virtual IR_Block *MergeNeighboringControlStructures(const std::vector<IR_Control *> &controls) const = 0;
+  
+  virtual IR_Block *GetCode() const = 0;
+  virtual void ReplaceCode(IR_Control *old, omega::CG_outputRepr *repr) = 0;
+  virtual void ReplaceExpression(IR_Ref *old, omega::CG_outputRepr *repr) = 0;
+  
+  virtual IR_OPERATION_TYPE QueryExpOperation(const omega::CG_outputRepr *repr) const = 0;
+  virtual IR_CONDITION_TYPE QueryBooleanExpOperation(const omega::CG_outputRepr *repr) const = 0;
+  virtual std::vector<omega::CG_outputRepr *> QueryExpOperand(const omega::CG_outputRepr *repr) const = 0;
+  virtual IR_Ref *Repr2Ref(const omega::CG_outputRepr *repr) const = 0;
+  
+  //---------------------------------------------------------------------------
+  // CC Omega code builder interface here
+  //---------------------------------------------------------------------------
+  omega::CG_outputBuilder *builder() const {return ocg_;}
+
+};
+
+#endif  
+  
diff --git a/chill/include/ir_rose.hh b/chill/include/ir_rose.hh
new file mode 100644
index 0000000..0c0417a
--- /dev/null
+++ b/chill/include/ir_rose.hh
@@ -0,0 +1,289 @@
+#ifndef IR_ROSE_HH
+#define IR_ROSE_HH
+
+#include <omega.h>
+#include "ir_code.hh"
+#include "ir_rose_utils.hh"
+#include <AstInterface_ROSE.h>
+#include "chill_error.hh"
+#include "staticSingleAssignment.h"
+#include "VariableRenaming.h"
+#include "ssaUnfilteredCfg.h"
+#include "virtualCFG.h"
+#include <omega.h>
+
+struct IR_roseScalarSymbol: public IR_ScalarSymbol {
+  SgVariableSymbol* vs_;
+  
+  IR_roseScalarSymbol(const IR_Code *ir, SgVariableSymbol *vs) {
+    ir_ = ir;
+    vs_ = vs;
+  }
+  
+  std::string name() const;
+  int size() const;
+  bool operator==(const IR_Symbol &that) const;
+  IR_Symbol *clone() const;
+};
+
+struct IR_roseArraySymbol: public IR_ArraySymbol {
+  
+  SgVariableSymbol* vs_;
+  
+  IR_roseArraySymbol(const IR_Code *ir, SgVariableSymbol* vs) {
+    ir_ = ir;
+    vs_ = vs;
+  }
+  std::string name() const;
+  int elem_size() const;
+  int n_dim() const;
+  omega::CG_outputRepr *size(int dim) const;
+  bool operator==(const IR_Symbol &that) const;
+  IR_ARRAY_LAYOUT_TYPE layout_type() const;
+  IR_Symbol *clone() const;
+  
+};
+
+struct IR_roseConstantRef: public IR_ConstantRef {
+  union {
+    omega::coef_t i_;
+    double f_;
+  };
+  
+  IR_roseConstantRef(const IR_Code *ir, omega::coef_t i) {
+    ir_ = ir;
+    type_ = IR_CONSTANT_INT;
+    i_ = i;
+  }
+  IR_roseConstantRef(const IR_Code *ir, double f) {
+    ir_ = ir;
+    type_ = IR_CONSTANT_FLOAT;
+    f_ = f;
+  }
+  omega::coef_t integer() const {
+    assert(is_integer());
+    return i_;
+  }
+  bool operator==(const IR_Ref &that) const;
+  omega::CG_outputRepr *convert();
+  IR_Ref *clone() const;
+  
+};
+
+struct IR_roseScalarRef: public IR_ScalarRef {
+  SgAssignOp *ins_pos_;
+  int op_pos_; // -1 means destination operand, otherwise source operand
+  SgVarRefExp *vs_;
+  int is_write_;
+  IR_roseScalarRef(const IR_Code *ir, SgVarRefExp *sym) {
+    ir_ = ir;
+    ins_pos_ = isSgAssignOp(sym->get_parent());
+    op_pos_ = 0;
+    if (ins_pos_ != NULL)
+      if (sym == isSgVarRefExp(ins_pos_->get_lhs_operand()))
+        op_pos_ = -1;
+    
+    vs_ = sym;
+  }
+  IR_roseScalarRef(const IR_Code *ir, SgVarRefExp *ins, int pos) {
+    ir_ = ir;
+    /*  ins_pos_ = ins;
+        op_pos_ = pos;
+        SgExpression* op;
+        if (pos == -1)
+        op = ins->get_lhs_operand();
+        else
+        op = ins->get_rhs_operand();
+        
+    */
+    
+    is_write_ = pos;
+    
+    /*  if (vs_ == NULL || pos > 0)
+        throw ir_error(
+        "Src operand not a variable or more than one src operand!!");
+    */
+    
+    vs_ = ins;
+    
+  }
+  bool is_write() const;
+  IR_ScalarSymbol *symbol() const;
+  bool operator==(const IR_Ref &that) const;
+  omega::CG_outputRepr *convert();
+  IR_Ref *clone() const;
+};
+
+struct IR_roseArrayRef: public IR_ArrayRef {
+  
+  SgPntrArrRefExp *ia_;
+  
+  int is_write_;
+  IR_roseArrayRef(const IR_Code *ir, SgPntrArrRefExp *ia, int write) {
+    ir_ = ir;
+    ia_ = ia;
+    is_write_ = write;
+  }
+  bool is_write() const;
+  omega::CG_outputRepr *index(int dim) const;
+  IR_ArraySymbol *symbol() const;
+  bool operator==(const IR_Ref &that) const;
+  omega::CG_outputRepr *convert();
+  IR_Ref *clone() const;
+};
+
+struct IR_roseLoop: public IR_Loop {
+  SgNode *tf_;
+  
+  IR_roseLoop(const IR_Code *ir, SgNode *tf) {
+    ir_ = ir;
+    tf_ = tf;
+  }
+  
+  IR_ScalarSymbol *index() const;
+  omega::CG_outputRepr *lower_bound() const;
+  omega::CG_outputRepr *upper_bound() const;
+  IR_CONDITION_TYPE stop_cond() const;
+  IR_Block *body() const;
+  IR_Block *convert();
+  int step_size() const;
+  IR_Control *clone() const;
+};
+
+struct IR_roseBlock: public IR_Block {
+  SgNode* tnl_;
+  SgNode *start_, *end_;
+  
+  IR_roseBlock(const IR_Code *ir, SgNode *tnl, SgNode *start, SgNode *end) {
+    ir_ = ir;
+    tnl_ = tnl;
+    start_ = start;
+    end_ = end;
+  }
+  
+  IR_roseBlock(const IR_Code *ir, SgNode *tnl) {
+    ir_ = ir;
+    tnl_ = tnl;
+    start_ = tnl_->get_traversalSuccessorByIndex(0);
+    end_ = tnl_->get_traversalSuccessorByIndex(
+      (tnl_->get_numberOfTraversalSuccessors()) - 1);
+  }
+  omega::CG_outputRepr *extract() const;
+  omega::CG_outputRepr *original() const;
+  IR_Control *clone() const;
+};
+
+struct IR_roseIf: public IR_If {
+  SgNode *ti_;
+  
+  IR_roseIf(const IR_Code *ir, SgNode *ti) {
+    ir_ = ir;
+    ti_ = ti;
+  }
+  ~IR_roseIf() {
+  }
+  omega::CG_outputRepr *condition() const;
+  IR_Block *then_body() const;
+  IR_Block *else_body() const;
+  IR_Block *convert();
+  IR_Control *clone() const;
+};
+
+class IR_roseCode_Global_Init {
+private:
+  static IR_roseCode_Global_Init *pinstance;
+public:
+  SgProject* project;
+  static IR_roseCode_Global_Init *Instance(char** argv);
+};
+
+class IR_roseCode: public IR_Code {
+protected:
+  SgSourceFile* file;
+  SgGlobal *root;
+  SgGlobal *firstScope;
+  SgSymbolTable* symtab_;
+  SgSymbolTable* symtab2_;
+  SgSymbolTable* symtab3_;
+  SgDeclarationStatementPtrList::iterator p;
+  SgFunctionDeclaration *func;
+  bool is_fortran_;
+  int i_;
+  StaticSingleAssignment *ssa_for_scalar;
+  ssa_unfiltered_cfg::SSA_UnfilteredCfg *main_ssa;
+  VariableRenaming *varRenaming_for_scalar;
+public:
+  IR_roseCode(const char *filename, const char* proc_name);
+  ~IR_roseCode();
+  
+  IR_ScalarSymbol *CreateScalarSymbol(const IR_Symbol *sym, int memory_type =
+                                      0);
+  IR_ArraySymbol *CreateArraySymbol(const IR_Symbol *sym,
+                                    std::vector<omega::CG_outputRepr *> &size, int memory_type = 0);
+  IR_ScalarRef *CreateScalarRef(const IR_ScalarSymbol *sym);
+  IR_ArrayRef *CreateArrayRef(const IR_ArraySymbol *sym,
+                              std::vector<omega::CG_outputRepr *> &index);
+  int ArrayIndexStartAt() {
+    if (is_fortran_)
+      return 1;
+    else
+      return 0;
+  }
+  
+  void populateLists(SgNode* tnl_1, SgStatementPtrList* list_1,
+                     SgStatementPtrList& output_list_1);
+  void populateScalars(const omega::CG_outputRepr *repr1,
+                       std::map<SgVarRefExp*, IR_ScalarRef*> &read_scalars_1,
+                       std::map<SgVarRefExp*, IR_ScalarRef*> &write_scalars_1,
+                       std::set<std::string> &indices, std::vector<std::string> &index);
+  //        std::set<std::string> &def_vars);
+  /*void findDefinitions(SgStatementPtrList &list_1,
+    std::set<VirtualCFG::CFGNode> &reaching_defs_1,
+    std::map<SgVarRefExp*, IR_ScalarRef*> &write_scalars_1,
+    std::set<std::string> &def_vars);
+  */
+  /*    void checkDependency(SgStatementPtrList &output_list_1,
+        std::vector<DependenceVector> &dvs1,
+        std::map<SgVarRefExp*, IR_ScalarRef*> &read_scalars_1,
+        std::map<SgVarRefExp*, IR_ScalarRef*> &write_scalars_1,
+        std::vector<std::string> &index, int i, int j);
+        void checkSelfDependency(SgStatementPtrList &output_list_1,
+        std::vector<DependenceVector> &dvs1,
+        std::map<SgVarRefExp*, IR_ScalarRef*> &read_scalars_1,
+        std::map<SgVarRefExp*, IR_ScalarRef*> &write_scalars_1,
+        std::vector<std::string> &index, int i, int j);
+        void checkWriteDependency(SgStatementPtrList &output_list_1,
+        std::vector<DependenceVector> &dvs1,
+        std::map<SgVarRefExp*, IR_ScalarRef*> &read_scalars_1,
+        std::map<SgVarRefExp*, IR_ScalarRef*> &write_scalars_1,
+        std::vector<std::string> &index, int i, int j);
+  */
+  std::vector<IR_ArrayRef *> FindArrayRef(
+    const omega::CG_outputRepr *repr) const;
+  std::vector<IR_ScalarRef *> FindScalarRef(
+    const omega::CG_outputRepr *repr) const;
+  std::vector<IR_Control *> FindOneLevelControlStructure(
+    const IR_Block *block) const;
+  IR_Block *MergeNeighboringControlStructures(
+    const std::vector<IR_Control *> &controls) const;
+  IR_Block *GetCode() const;
+  void ReplaceCode(IR_Control *old, omega::CG_outputRepr *repr);
+  void ReplaceExpression(IR_Ref *old, omega::CG_outputRepr *repr);
+  
+  IR_OPERATION_TYPE QueryExpOperation(const omega::CG_outputRepr *repr) const;
+  IR_CONDITION_TYPE QueryBooleanExpOperation(
+    const omega::CG_outputRepr *repr) const;
+  std::vector<omega::CG_outputRepr *> QueryExpOperand(
+    const omega::CG_outputRepr *repr) const;
+  IR_Ref *Repr2Ref(const omega::CG_outputRepr *) const;
+  /*    std::pair<std::vector<DependenceVector>, std::vector<DependenceVector> >
+        FindScalarDeps(const omega::CG_outputRepr *repr1,
+        const omega::CG_outputRepr *repr2, std::vector<std::string> index,
+        int i, int j);
+  */
+  void finalizeRose();
+  friend class IR_roseArraySymbol;
+  friend class IR_roseArrayRef;
+};
+
+#endif
diff --git a/chill/include/ir_rose_utils.hh b/chill/include/ir_rose_utils.hh
new file mode 100644
index 0000000..9e98aee
--- /dev/null
+++ b/chill/include/ir_rose_utils.hh
@@ -0,0 +1,18 @@
+#ifndef IR_ROSE_UTILS_HH
+#define IR_ROSE_UTILS_HH
+#include <vector>
+#include <rose.h>
+#include "sageBuilder.h"
+
+
+
+std::vector<SgForStatement *> find_deepest_loops(SgNode *tnl);
+std::vector<SgForStatement *> find_loops(SgNode *tnl);
+
+
+
+SgNode* loop_body_at_level(SgNode* tnl, int level);
+SgNode* loop_body_at_level(SgForStatement* loop, int level);
+void swap_node_for_node_list(SgNode* tn, SgNode* new_tnl);
+
+#endif
diff --git a/chill/include/irtools.hh b/chill/include/irtools.hh
new file mode 100644
index 0000000..8dc8e28
--- /dev/null
+++ b/chill/include/irtools.hh
@@ -0,0 +1,40 @@
+#ifndef IRTOOLS_HH
+#define IRTOOLS_HH
+
+#include <vector>
+#include <omega.h>
+#include <code_gen/CG_outputRepr.h>
+#include "ir_code.hh"
+#include "dep.hh"
+
+// IR tree is used to initialize a loop. For a loop node, payload is
+// its mapped iteration space dimension. For a simple block node,
+// payload is its mapped statement number. Normal if-else is splitted
+// into two nodes where the one with odd payload represents then-part and
+// the one with even payload represents else-part.
+struct ir_tree_node {
+  IR_Control *content;
+  ir_tree_node *parent;
+  std::vector<ir_tree_node *> children;
+  int payload;
+  
+  ~ir_tree_node() {
+    for (int i = 0; i < children.size(); i++)
+      delete children[i];
+    delete content;
+  }
+};
+
+std::vector<ir_tree_node *> build_ir_tree(IR_Control *control,
+                                          ir_tree_node *parent = NULL);
+std::vector<ir_tree_node *> extract_ir_stmts(
+  const std::vector<ir_tree_node *> &ir_tree);
+bool is_dependence_valid(ir_tree_node *src_node, ir_tree_node *dst_node,
+                         const DependenceVector &dv, bool before);
+std::pair<std::vector<DependenceVector>, std::vector<DependenceVector> > test_data_dependences(
+  IR_Code *ir, const omega::CG_outputRepr *repr1,
+  const omega::Relation &IS1, const omega::CG_outputRepr *repr2,
+  const omega::Relation &IS2, std::vector<omega::Free_Var_Decl*> &freevar,
+  std::vector<std::string> index, int i, int j);
+
+#endif
diff --git a/chill/include/loop.hh b/chill/include/loop.hh
new file mode 100644
index 0000000..c3366ef
--- /dev/null
+++ b/chill/include/loop.hh
@@ -0,0 +1,168 @@
+#ifndef LOOP_HH
+#define LOOP_HH
+
+#include <omega.h>
+#include <codegen.h>
+#include <code_gen/CG.h>
+#include <vector>
+#include <map>
+#include <set>
+#include "dep.hh"
+#include "ir_code.hh"
+#include "irtools.hh"
+
+class IR_Code;
+
+enum TilingMethodType { StridedTile, CountedTile };
+enum LoopLevelType { LoopLevelOriginal, LoopLevelTile, LoopLevelUnknown };
+
+
+// Describes properties of each loop level of a statement. "payload"
+// for LoopLevelOriginal means iteration space dimension, for
+// LoopLevelTile means tiled loop level.  Special value -1 for
+// LoopLevelTile means purely derived loop. For dependence dimension
+// payloads, the values must be in an increasing order.
+// "parallel_level" will be used by code generation to support
+// multi-level parallelization (default 0 means sequential loop under
+// the current parallelization level).
+struct LoopLevel {
+  LoopLevelType type;
+  int payload;  
+  int parallel_level;
+};
+
+struct Statement {
+  omega::CG_outputRepr *code;
+  omega::Relation IS;
+  omega::Relation xform;
+  std::vector<LoopLevel> loop_level;
+  ir_tree_node *ir_stmt_node;
+  //protonu--temporarily putting this back here
+  //omega::Tuple<int> nonSplitLevels;
+  //end--protonu.
+};
+
+
+class Loop {
+protected:
+  int tmp_loop_var_name_counter;
+  static const std::string tmp_loop_var_name_prefix;
+  int overflow_var_name_counter;
+  static const std::string overflow_var_name_prefix;
+  std::vector<int> stmt_nesting_level_;
+  std::vector<std::string> index;
+  std::map<int, omega::CG_outputRepr *> replace;
+  
+public:
+  IR_Code *ir;
+  std::vector<omega::Free_Var_Decl*> freevar;
+  std::vector<Statement> stmt;
+  std::vector<ir_tree_node *> ir_stmt;
+  std::vector<ir_tree_node *> ir_tree;
+  DependenceGraph dep;
+  int num_dep_dim;
+  omega::Relation known;
+  omega::CG_outputRepr *init_code;
+  omega::CG_outputRepr *cleanup_code;
+  std::map<int, std::vector<omega::Free_Var_Decl *> > overflow;
+  
+  
+protected:
+  mutable omega::CodeGen *last_compute_cg_;
+  mutable omega::CG_result *last_compute_cgr_;
+  mutable int last_compute_effort_;
+  
+protected:
+  bool init_loop(std::vector<ir_tree_node *> &ir_tree, std::vector<ir_tree_node *> &ir_stmt);
+  int get_dep_dim_of(int stmt, int level) const;
+  int get_last_dep_dim_before(int stmt, int level) const;
+  std::vector<omega::Relation> getNewIS() const;
+  omega::Relation getNewIS(int stmt_num) const;
+  std::vector<int> getLexicalOrder(int stmt_num) const;
+  int getLexicalOrder(int stmt_num, int level) const;
+  std::set<int> getStatements(const std::vector<int> &lex, int dim) const;
+  void shiftLexicalOrder(const std::vector<int> &lex, int dim, int amount);
+  void setLexicalOrder(int dim, const std::set<int> &active, int starting_order = 0, std::vector< std::vector<std::string> >idxNames= std::vector< std::vector<std::string> >());
+  void apply_xform(int stmt_num);
+  void apply_xform(std::set<int> &active);
+  void apply_xform();
+  std::set<int> getSubLoopNest(int stmt_num, int level) const;
+  
+  
+public:
+  Loop() { ir = NULL; tmp_loop_var_name_counter = 1; init_code = NULL; }
+  Loop(const IR_Control *control);
+  ~Loop();
+  
+  omega::CG_outputRepr *getCode(int effort = 1) const;
+  void printCode(int effort = 1) const;
+  void addKnown(const omega::Relation &cond);
+  void print_internal_loop_structure() const;
+  bool isInitialized() const;
+  int num_statement() const { return stmt.size(); }
+  void printIterationSpace() const;
+  void printDependenceGraph() const;
+  void removeDependence(int stmt_num_from, int stmt_num_to);
+  void dump() const;
+  
+  std::vector<std::set <int > > sort_by_same_loops(std::set<int > active, int level);
+  //
+  // legacy unimodular transformations for perfectly nested loops
+  // e.g. M*(i,j)^T = (i',j')^T or M*(i,j,1)^T = (i',j')^T
+  //
+  bool nonsingular(const std::vector<std::vector<int> > &M);
+  
+  //
+  // high-level loop transformations
+  //
+  void permute(const std::set<int> &active, const std::vector<int> &pi);
+  void permute(int stmt_num, int level, const std::vector<int> &pi);
+  void permute(const std::vector<int> &pi);
+  void original();
+  
+  void tile(int stmt_num, int level, int tile_size, int outer_level = 1, TilingMethodType method = StridedTile, int alignment_offset = 0, int alignment_multiple = 1);
+  std::set<int> split(int stmt_num, int level, const omega::Relation &cond);
+  std::set<int> unroll(int stmt_num, int level, int unroll_amount, std::vector< std::vector<std::string> >idxNames= std::vector< std::vector<std::string> >(), int cleanup_split_level = 0);
+  
+  bool datacopy(const std::vector<std::pair<int, std::vector<int> > > &array_ref_nums, int level, bool allow_extra_read = false, int fastest_changing_dimension = -1, int padding_stride = 1, int padding_alignment = 4, int memory_type = 0);
+  bool datacopy(int stmt_num, int level, const std::string &array_name, bool allow_extra_read = false, int fastest_changing_dimension = -1, int padding_stride = 1, int padding_alignment = 4, int memory_type = 0);
+  bool datacopy_privatized(int stmt_num, int level, const std::string &array_name, const std::vector<int> &privatized_levels, bool allow_extra_read = false, int fastest_changing_dimension = -1, int padding_stride = 1, int padding_alignment = 1, int memory_type = 0);
+  bool datacopy_privatized(const std::vector<std::pair<int, std::vector<int> > > &array_ref_nums, int level, const std::vector<int> &privatized_levels, bool allow_extra_read = false, int fastest_changing_dimension = -1, int padding_stride = 1, int padding_alignment = 1, int memory_type = 0);
+  bool datacopy_privatized(const std::vector<std::pair<int, std::vector<IR_ArrayRef *> > > &stmt_refs, int level, const std::vector<int> &privatized_levels, bool allow_extra_read, int fastest_changing_dimension, int padding_stride, int padding_alignment, int memory_type = 0);
+  //std::set<int> scalar_replacement_inner(int stmt_num);
+  
+  
+  
+  Graph<std::set<int>, bool> construct_induced_graph_at_level(std::vector<std::set<int> > s, DependenceGraph dep, int dep_dim);
+  std::vector<std::set<int> > typed_fusion(Graph<std::set<int>, bool> g);
+  void fuse(const std::set<int> &stmt_nums, int level);
+  void distribute(const std::set<int> &stmt_nums, int level);
+  void skew(const std::set<int> &stmt_nums, int level, const std::vector<int> &skew_amount);
+  void shift(const std::set<int> &stmt_nums, int level, int shift_amount);
+  void scale(const std::set<int> &stmt_nums, int level, int scale_amount);
+  void reverse(const std::set<int> &stmt_nums, int level);
+  void peel(int stmt_num, int level, int peel_amount = 1);
+  //
+  // more fancy loop transformations
+  //
+  void modular_shift(int stmt_num, int level, int shift_amount) {}
+  void diagonal_map(int stmt_num, const std::pair<int, int> &levels, int offset) {}
+  void modular_partition(int stmt_num, int level, int stride) {}
+  
+  //
+  // derived loop transformations
+  //
+  void shift_to(int stmt_num, int level, int absolute_position);
+  std::set<int> unroll_extra(int stmt_num, int level, int unroll_amount, int cleanup_split_level = 0);
+  bool is_dependence_valid_based_on_lex_order(int i, int j,
+			const DependenceVector &dv, bool before);
+  //
+  // other public operations
+  //
+  void pragma(int stmt_num, int level, const std::string &pragmaText);
+  void prefetch(int stmt_num, int level, const std::string &arrName, int hint);
+  //void prefetch(int stmt_num, int level, const std::string &arrName, const std::string &indexName, int offset, int hint);
+};
+
+
+#endif
diff --git a/chill/include/omegatools.hh b/chill/include/omegatools.hh
new file mode 100644
index 0000000..206079c
--- /dev/null
+++ b/chill/include/omegatools.hh
@@ -0,0 +1,97 @@
+#ifndef OMEGATOOLS_HH
+#define OMEGATOOLS_HH
+
+#include <string>
+#include <omega.h>
+#include "dep.hh"
+#include "ir_code.hh"
+
+std::string tmp_e();
+
+void exp2formula(IR_Code *ir, omega::Relation &r, omega::F_And *f_root,
+                 std::vector<omega::Free_Var_Decl *> &freevars,
+                 omega::CG_outputRepr *repr, omega::Variable_ID lhs, char side,
+                 IR_CONDITION_TYPE rel, bool destroy);
+omega::Relation arrays2relation(IR_Code *ir, std::vector<omega::Free_Var_Decl*> &freevars,
+                                const IR_ArrayRef *ref_src, const omega::Relation &IS_w,
+                                const IR_ArrayRef *ref_dst, const omega::Relation &IS_r);
+std::pair<std::vector<DependenceVector>, std::vector<DependenceVector> > relation2dependences(
+  const IR_ArrayRef *ref_src, const IR_ArrayRef *ref_dst, const omega::Relation &r);
+
+void exp2constraint(IR_Code *ir, omega::Relation &r, omega::F_And *f_root,
+                    std::vector<omega::Free_Var_Decl *> &freevars,
+                    omega::CG_outputRepr *repr, bool destroy);
+
+// suif legacy code
+// void suif2formula(Relation &r, F_And *f_root,
+//                   std::vector<Free_Var_Decl*> &freevars,
+//                   operand op, Variable_ID lhs,
+//                   char side, char rel);
+// void suif2formula(Relation &r, F_And *f_root,
+//                   std::vector<Free_Var_Decl*> &freevars,
+//                   instruction *ins, Variable_ID lhs,
+//                   char side, char rel);
+// void add_loop_stride_constraints(omega::Relation &r, omega::F_And *f_root,
+//                                  std::vector<omega::Free_Var_Decl*> &freevars,
+//                                  tree_for *tnf, char side);
+// void add_loop_bound_constraints(IR_Code *ir, omega::Relation &r, omega::F_And *f_root,
+//                                 std::vector<omega::Free_Var_Decl*> &freevars,
+//                                 tree_for *tnf,
+//                                 char upper_or_lower, char side, IR_CONDITION_TYPE rel);
+// Relation loop_iteration_space(std::vector<Free_Var_Decl*> &freevars,
+//                               tree_node *tn, std::vector<tree_for*> &loops);
+
+// Relation arrays2relation(std::vector<Free_Var_Decl*> &freevars,
+//                          in_array *ia_w, const Relation &IS1,
+//                          in_array *ia_r, const Relation &IS2);
+// std::vector<DependenceVector> relation2dependences(IR_Code *ir, in_array *ia_w,
+//                                                    in_array *ia_r, const Relation &r);
+
+// end of suif legacy code
+
+bool is_single_iteration(const omega::Relation &r, int dim);
+void assign_const(omega::Relation &r, int dim, int val);
+int get_const(const omega::Relation &r, int dim, omega::Var_Kind type);
+omega::Variable_ID find_index(omega::Relation &r, const std::string &s, char side);
+omega::Relation permute_relation(const std::vector<int> &pi);
+omega::Relation get_loop_bound(const omega::Relation &r, int dim);
+bool is_single_loop_iteration(const omega::Relation &r, int level, const omega::Relation &known);
+omega::Relation get_loop_bound(const omega::Relation &r, int level, const omega::Relation &known);
+omega::Relation get_max_loop_bound(const std::vector<omega::Relation> &r, int dim);
+omega::Relation get_min_loop_bound(const std::vector<omega::Relation> &r, int dim);
+void add_loop_stride(omega::Relation &r, const omega::Relation &bound, int dim, int stride);
+bool is_inner_loop_depend_on_level(const omega::Relation &r, int level, const omega::Relation &known);
+// void adjust_loop_bound(omega::Relation &r, int dim, int adjustment, std::vector<omega::Free_Var_Decl *> globals = std::vector<omega::Free_Var_Decl *>());
+omega::Relation adjust_loop_bound(const omega::Relation &r, int level, int adjustment);
+// void adjust_loop_bound(Relation &r, int dim, int adjustment);
+// void adjust_loop_bound(Relation &r, int dim, Free_Var_Decl *global_var, int adjustment);
+// boolean is_private_statement(const omega::Relation &r, int dim);
+
+// coef_t mod(const Relation &r, Variable_ID v, int dividend);
+
+
+enum LexicalOrderType {LEX_MATCH, LEX_BEFORE, LEX_AFTER, LEX_UNKNOWN};
+
+// template <typename T>
+// LexicalOrderType lexical_order(const std::vector<T> &a, const std::vector<T> &b) {
+//   int size = min(a.size(), b.size());
+//   for (int i = 0; i < size; i++) {
+//     if (a[i] < b[i])
+//       return LEX_BEFORE;
+//     else if (b[i] < a[i])
+//       return LEX_AFTER;
+//   }
+//   if (a.size() < b.size())
+//     return LEX_BEFORE;
+//   else if (b.size() < a.size())
+//     return LEX_AFTER;
+//   else
+//     return LEX_MATCH;
+// }
+
+// struct LoopException {
+//   std::string descr;
+//   LoopException(const std::string &s): descr(s) {};
+// };
+
+#endif