Moved most modules into lib

12 files changed, 1423 insertions, 0 deletions

diff --git a/include/chill_error.hh b/include/chill_error.hh
new file mode 100644
index 0000000..88e49fc
--- /dev/null
+++ b/include/chill_error.hh
@@ -0,0 +1,24 @@
+#ifndef CHILL_ERROR_HH
+#define CHILL_ERROR_HH
+
+/*!
+ * \file
+ * \brief CHiLL runtime exceptions
+ */
+
+//! 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){}
+};
+
+//! for 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/include/chill_run_util.hh b/include/chill_run_util.hh
new file mode 100644
index 0000000..8df5871
--- /dev/null
+++ b/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/include/chilldebug.h b/include/chilldebug.h
new file mode 100644
index 0000000..865f1f6
--- /dev/null
+++ b/include/chilldebug.h
@@ -0,0 +1,15 @@
+
+// a central place to turn on debugging messages
+
+// enable the next line to get lots of output 
+//#define DEBUGCHILL
+#ifndef DEBUGCHILL_H
+#define DEBUGCHILL_H
+
+#ifdef DEBUGCHILL 
+#define DEBUG_PRINT(args...) fprintf(stderr, args )
+#else
+#define DEBUG_PRINT(args...) do {} while(0) /* Don't do anything  */
+#endif
+
+#endif
diff --git a/include/chillmodule.hh b/include/chillmodule.hh
new file mode 100644
index 0000000..e83119f
--- /dev/null
+++ b/include/chillmodule.hh
@@ -0,0 +1,17 @@
+#ifndef CHILLMODULE_HH
+#define CHILLMODULE_HH
+
+/*!
+ * \file
+ * \brief chill interface to python
+ */
+
+#include <Python.h>
+
+void finalize_loop(int loop_num_start, int loop_num_end);
+int get_loop_num_start();
+int get_loop_num_end();
+//! pass C methods to python
+PyMODINIT_FUNC initchill();
+
+#endif
diff --git a/include/dep.hh b/include/dep.hh
new file mode 100644
index 0000000..6c535ce
--- /dev/null
+++ b/include/dep.hh
@@ -0,0 +1,94 @@
+#ifndef DEP_HH
+#define DEP_HH
+
+/*!
+ * \file 
+ * \brief Data dependence vector and graph.
+ *
+ * All dependence vectors are normalized, i.e., the first non-zero distance
+ * must be positve. Thus the correct dependence meaning can be given based on
+ * source/destination pair's read/write type. Suppose for a dependence vector
+ * 1, 0~5, -3), we want to permute the first and the second dimension,
+ * the result would be two dependence vectors (0, 1, -3) and (1~5, 1, -3).
+ * All operations on dependence vectors are non-destructive, i.e., new
+ * dependence vectors are returned.
+ */
+
+#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(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;
+  
+  // TODO 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;
+  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 std::set<int> &active = std::set<int>()) const;
+  DependenceGraph subspace(int dim) const;
+  bool isPositive() const;
+  bool hasPositive(int dim) const;
+  bool hasNegative(int dim) const;
+};
+
+#endif
diff --git a/include/graph.hh b/include/graph.hh
new file mode 100644
index 0000000..211444a
--- /dev/null
+++ b/include/graph.hh
@@ -0,0 +1,328 @@
+/*****************************************************************************
+ 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
+
+/*!
+ * \file
+ * \brief  Graph<VertexType, EdgeType> template class supports topological sort
+ *
+ * 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}).
+ */
+
+#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;
+  
+  //! Topological sort
+  /*! This topological sort does handle SCC in graph. */
+  std::vector<std::set<int> > topoSort() const;
+  //! Topological sort
+  /*! This topological sort does not handle SCC in graph. */
+  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 << "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;
+}
+
+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;
+}
+
+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/include/ir_code.hh b/include/ir_code.hh
new file mode 100644
index 0000000..d695474
--- /dev/null
+++ b/include/ir_code.hh
@@ -0,0 +1,289 @@
+/*****************************************************************************
+ 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
+
+/*!
+ * \file
+ * \brief CHiLL's compiler intermediate representation interface that extends Omega's builder interface to accomodate compiler analyses and extra code generation.
+ * 
+ * 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.
+ */
+
+
+#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;
+  //! shallow copy
+  virtual IR_Ref *clone() const = 0;
+};
+
+
+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;
+  //! shallow copy
+  virtual IR_Control *clone() const = 0;
+};
+
+
+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 */
+  
+  /*! 
+   * \param 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;
+  
+  //! Codegen Omega code builder interface
+  omega::CG_outputBuilder *builder() const {return ocg_;}
+
+};
+
+#endif  
diff --git a/include/ir_rose.hh b/include/ir_rose.hh
new file mode 100644
index 0000000..03ea50d
--- /dev/null
+++ b/include/ir_rose.hh
@@ -0,0 +1,267 @@
+#ifndef IR_ROSE_HH
+#define IR_ROSE_HH
+
+/*!
+ * \file
+ * \brief CHiLL's rose interface.
+ */
+
+#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::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;
+  void finalizeRose();
+  friend class IR_roseArraySymbol;
+  friend class IR_roseArrayRef;
+};
+
+#endif
diff --git a/include/ir_rose_utils.hh b/include/ir_rose_utils.hh
new file mode 100644
index 0000000..350aa24
--- /dev/null
+++ b/include/ir_rose_utils.hh
@@ -0,0 +1,19 @@
+#ifndef IR_ROSE_UTILS_HH
+#define IR_ROSE_UTILS_HH
+
+/*!
+ * \file
+ * \brief ROSE interface utilities
+ */
+#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/include/irtools.hh b/include/irtools.hh
new file mode 100644
index 0000000..a3b552a
--- /dev/null
+++ b/include/irtools.hh
@@ -0,0 +1,48 @@
+#ifndef IRTOOLS_HH
+#define IRTOOLS_HH
+
+/*!
+ * \file
+ * \brief Useful tools to analyze code in compiler IR format.
+ */
+
+#include <vector>
+#include <omega.h>
+#include <code_gen/CG_outputRepr.h>
+#include "ir_code.hh"
+#include "dep.hh"
+
+//! It is used to initialize a loop.
+struct ir_tree_node {
+  IR_Control *content;
+  ir_tree_node *parent;
+  std::vector<ir_tree_node *> children;
+/*! 
+ * * 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
+ *   * the one with odd payload represents then-part and
+ *   * the one with even payload represents else-part.
+ */
+  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/include/loop.hh b/include/loop.hh
new file mode 100644
index 0000000..9620489
--- /dev/null
+++ b/include/loop.hh
@@ -0,0 +1,200 @@
+#ifndef LOOP_HH
+#define LOOP_HH
+
+/*!
+ * \file 
+ * \brief Core loop transformation functionality.
+ *
+ * "level" (starting from 1) means loop level and it corresponds to "dim"
+ * (starting from 0) in transformed iteration space [c_1,l_1,c_2,l_2,....,
+ * c_n,l_n,c_(n+1)], e.g., l_2 is loop level 2 in generated code, dim 3
+ * in transformed iteration space, and variable 4 in Omega relation.
+ * All c's are constant numbers only and they will not show up as actual loops.
+ * 
+ * Formula:
+ *
+ * ~~~
+ *   dim = 2*level - 1
+ *   var = dim + 1
+ * ~~~
+ */
+ 
+
+#include <omega.h>
+#include <code_gen/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. 
+struct LoopLevel {
+  LoopLevelType type;
+/*! 
+ * 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.
+ */
+  int payload;  
+/*!
+ * Used by code generation to support
+ * multi-level parallelization (default 0 means sequential loop under
+ * the current parallelization level).
+ */
+  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. \f$M*(i,j)^T = (i',j')^T or M*(i,j,1)^T = (i',j')^T\f$
+   */
+  bool nonsingular(const std::vector<std::vector<int> > &M);
+  
+  /*!
+   * \defgroup hltrans 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);
+  
+  
+  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);
+  /*!
+   * \defgroup hlfancy 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) {}
+  /*! @} */
+  
+  /*! 
+   * \defgroup hlderived 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);
+  /*! @} */
+
+  /*! 
+   * \defgroup hlother 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);
+  /*! @} */
+
+  /*! @} */
+};
+
+
+#endif
diff --git a/include/omegatools.hh b/include/omegatools.hh
new file mode 100644
index 0000000..b51b2bd
--- /dev/null
+++ b/include/omegatools.hh
@@ -0,0 +1,93 @@
+#ifndef OMEGATOOLS_HH
+#define OMEGATOOLS_HH
+
+/*!
+ * \file
+ * \brief Useful tools involving Omega manipulation.
+ */
+
+#include <string>
+#include <omega.h>
+#include "dep.hh"
+#include "ir_code.hh"
+
+std::string tmp_e();
+
+//! Convert expression tree to omega relation.
+/*!
+ * \param destroy shallow deallocation of "repr", not freeing the actual code inside.
+ */
+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);
+
+//! Build dependence relation for two array references.
+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);
+//! 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 omega::Relation &r);
+
+//! Convert a boolean expression to omega relation.  
+/*!
+ * \param destroy shallow deallocation of "repr", not freeing the actual code inside.
+ */
+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);
+
+bool is_single_iteration(const omega::Relation &r, int dim);
+//!  Set/get the value of a variable which is know to be constant.
+void assign_const(omega::Relation &r, int dim, int val);
+
+int get_const(const omega::Relation &r, int dim, omega::Var_Kind type);
+
+//! Find the position index variable in a Relation by name.
+omega::Variable_ID find_index(omega::Relation &r, const std::string &s, char side);
+
+//! Generate mapping relation for permuation.
+omega::Relation permute_relation(const std::vector<int> &pi);
+
+omega::Relation get_loop_bound(const omega::Relation &r, int dim);
+
+//!  Determine whether the loop (starting from 0) in the iteration space has only one iteration.
+bool is_single_loop_iteration(const omega::Relation &r, int level, const omega::Relation &known);
+//! Get the bound for a specific loop.
+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);
+
+//! 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(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);
+/*!
+ * Suppose loop dim is i. Replace i with i+adjustment in loop bounds.
+ *
+ * ~~~
+ * 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
+ * ~~~
+ */
+omega::Relation adjust_loop_bound(const omega::Relation &r, int level, int adjustment);
+
+enum LexicalOrderType {LEX_MATCH, LEX_BEFORE, LEX_AFTER, LEX_UNKNOWN};
+
+#endif