Moved most modules into lib

10 files changed, 600 insertions, 0 deletions

diff --git a/lib/codegen/include/code_gen/CG.h b/lib/codegen/include/code_gen/CG.h
new file mode 100644
index 0000000..ce56768
--- /dev/null
+++ b/lib/codegen/include/code_gen/CG.h
@@ -0,0 +1,118 @@
+#ifndef _CG_H
+#define _CG_H
+
+#include <omega/Relation.h>
+#include <basic/BoolSet.h>
+#include <code_gen/CG_outputBuilder.h>
+#include <vector>
+
+namespace omega {
+
+class CodeGen;
+
+struct CG_result {
+  CodeGen *codegen_;
+  BoolSet<> active_;
+
+  CG_result() { codegen_ = NULL; }
+  virtual ~CG_result() { /* not responsible for codegen_ */ }
+  
+  virtual CG_result *recompute(const BoolSet<> &parent_active, const Relation &known, const Relation &restriction) = 0;
+  virtual int populateDepth() = 0;
+  virtual std::pair<CG_result *, Relation> liftOverhead(int depth, bool propagate_up) = 0;
+  virtual Relation hoistGuard() = 0;
+  virtual void removeGuard(const Relation &guard) = 0;
+  virtual CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const = 0;
+  CG_outputRepr *printRepr(CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts) const;
+  std::string printString() const;
+  int num_level() const;
+  virtual CG_result *clone() const = 0;
+  virtual void dump(int indent) const {}
+  void dump() { dump(0); }
+};
+
+
+struct CG_split: public CG_result {
+  std::vector<Relation> restrictions_;
+  std::vector<CG_result *> clauses_;
+
+  CG_split(CodeGen *codegen, const BoolSet<> &active, const std::vector<Relation> &restrictions, const std::vector<CG_result *> &clauses) {
+    codegen_ = codegen;
+    active_ = active;
+    restrictions_ = restrictions;
+    clauses_ = clauses;
+  } 
+  ~CG_split() {
+    for (int i = 0; i < clauses_.size(); i++)
+      delete clauses_[i];
+  } 
+  
+  CG_result *recompute(const BoolSet<> &parent_active, const Relation &known, const Relation &restriction);
+  int populateDepth();
+  std::pair<CG_result *, Relation> liftOverhead(int depth, bool propagate_up);
+  Relation hoistGuard();
+  void removeGuard(const Relation &guard);
+  CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const;
+  CG_result *clone() const;
+  void dump(int indent) const;
+
+private:
+  std::vector<CG_result *> findNextLevel() const;
+};
+
+
+struct CG_loop: public CG_result {
+  int level_;
+  CG_result *body_;
+
+  Relation known_;
+  Relation restriction_;
+  Relation bounds_;
+  Relation guard_;
+  bool needLoop_;
+  int depth_;
+
+  CG_loop(CodeGen *codegen, const BoolSet<> &active, int level, CG_result *body) {
+    codegen_ = codegen;
+    active_ = active;
+    level_ = level;
+    body_ = body;
+  }
+  ~CG_loop() { delete body_; }
+  
+  CG_result *recompute(const BoolSet<> &parent_active, const Relation &known, const Relation &restriction);
+  int populateDepth();
+  std::pair<CG_result *, Relation> liftOverhead(int depth, bool propagate_up);
+  Relation hoistGuard();
+  void removeGuard(const Relation &guard);
+  CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const;
+  CG_outputRepr *printRepr(bool do_print_guard, int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const;
+  CG_result *clone() const;
+  void dump(int indent) const;
+};
+
+
+
+struct CG_leaf: public CG_result {
+  Relation known_;
+  std::map<int, Relation> guards_;
+  
+  CG_leaf(CodeGen *codegen, const BoolSet<> &active) {
+    codegen_ = codegen;
+    active_ = active;
+  }
+  ~CG_leaf() {}
+  
+  CG_result *recompute(const BoolSet<> &parent_active, const Relation &known, const Relation &restriction);
+  int populateDepth() { return 0; }
+  std::pair<CG_result *, Relation> liftOverhead(int depth, bool propagate_up);
+  Relation hoistGuard();
+  void removeGuard(const Relation &guard);
+  CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const;
+  CG_result *clone() const;
+  void dump(int indent) const;
+};
+
+}
+
+#endif
diff --git a/lib/codegen/include/code_gen/CG_outputBuilder.h b/lib/codegen/include/code_gen/CG_outputBuilder.h
new file mode 100644
index 0000000..19dc440
--- /dev/null
+++ b/lib/codegen/include/code_gen/CG_outputBuilder.h
@@ -0,0 +1,161 @@
+/*****************************************************************************
+ Copyright (C) 1994-2000 the Omega Project Team
+ Copyright (C) 2005-2011 Chun Chen
+ All Rights Reserved.
+
+ Purpose:
+   abstract base class of comiler IR code builder
+
+ Notes:
+   All "CG_outputRepr *" parameters are consumed inside the the function
+ unless explicitly stated otherwise, i.e., not valid after the call.
+   Parameter "indent" normally not used except it is used in unstructured
+ string output for correct indentation.
+ 
+ History:
+   04/17/96 created - Lei Zhou
+   05/02/08 clarify integer floor/mod/ceil definitions, -chen
+   05/31/08 use virtual clone to implement CreateCopy, -chun
+   08/05/10 clarify NULL parameter allowance, -chun
+*****************************************************************************/
+
+#ifndef _CG_OUTPUTBUILDER_H
+#define _CG_OUTPUTBUILDER_H
+
+#include <code_gen/CG_outputRepr.h>
+
+#include <string>
+#include <vector>
+
+namespace omega {
+
+//! abstract base class of comiler IR code builder
+class CG_outputBuilder {
+public:
+  CG_outputBuilder() {}
+  virtual ~CG_outputBuilder() {}
+
+  //! substitute variables in stmt
+  virtual CG_outputRepr *CreateSubstitutedStmt(int indent, CG_outputRepr *stmt,
+                                               const std::vector<std::string> &vars,
+                                               std::vector<CG_outputRepr *> &subs) const = 0;
+
+  //! assignment stmt generation
+  virtual CG_outputRepr *CreateAssignment(int indent, CG_outputRepr *lhs,
+                                          CG_outputRepr *rhs) const = 0;
+
+  //! function invocation generation
+  virtual CG_outputRepr *CreateInvoke(const std::string &funcName,
+                                      std::vector<CG_outputRepr *> &argList) const = 0;
+
+  //! comment generation
+  virtual CG_outputRepr *CreateComment(int indent,
+                                       const std::string &commentText) const = 0;
+
+  //! Attribute generation
+  virtual CG_outputRepr* CreateAttribute(CG_outputRepr  *control,
+                                           const std::string &commentText) const = 0;
+  //! Pragma Attribute
+  virtual CG_outputRepr* CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const = 0;
+  
+  //! Prefetch Attribute
+  virtual CG_outputRepr* CreatePrefetchAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &arrName, int hint) const = 0;
+
+  //! generate if stmt, true/false stmt can be NULL but not the condition
+  virtual CG_outputRepr *CreateIf(int indent, CG_outputRepr *guardCondition,
+                                  CG_outputRepr *true_stmtList,
+                                  CG_outputRepr *false_stmtList) const = 0;
+
+  //! generate loop inductive variable (loop control structure)
+  virtual CG_outputRepr *CreateInductive(CG_outputRepr *index,
+                                         CG_outputRepr *lower,
+                                         CG_outputRepr *upper,
+                                         CG_outputRepr *step) const = 0;
+
+  //! generate loop stmt from loop control and loop body, NULL parameter allowed
+  virtual CG_outputRepr *CreateLoop(int indent, CG_outputRepr *control,
+                                    CG_outputRepr *stmtList) const = 0;
+
+  //! copy operation, NULL parameter allowed.
+  /*!
+   * this function makes pointer handling uniform regardless NULL status
+   */
+  virtual CG_outputRepr *CreateCopy(CG_outputRepr *original) const {
+    if (original == NULL)
+      return NULL;
+    else
+      return original->clone();
+  }
+
+  //! basic integer number creation
+  virtual CG_outputRepr *CreateInt(int num) const = 0;
+  virtual bool isInteger(CG_outputRepr *op) const = 0;
+
+
+  //! basic identity/variable creation
+  virtual CG_outputRepr *CreateIdent(const std::string &varName) const = 0;
+
+  //! Addition operations, NULL parameter means 0,
+  virtual CG_outputRepr *CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const = 0;
+  //! Subtraction operations, NULL parameter means 0,
+  virtual CG_outputRepr *CreateMinus(CG_outputRepr *lop, CG_outputRepr *rop) const = 0;
+  //! Multiplication operations, NULL parameter means 0,
+  virtual CG_outputRepr *CreateTimes(CG_outputRepr *lop, CG_outputRepr *rop) const = 0;
+  //! Division operations, NULL parameter means 0,
+  /*!
+   * integer division truncation method undefined, only use when lop is known
+   * to be multiple of rop, otherwise use integer floor instead
+   */
+  virtual CG_outputRepr *CreateDivide(CG_outputRepr *lop, CG_outputRepr *rop) const {
+    return CreateIntegerFloor(lop, rop);
+  }
+  
+  //! integer floor functions, NULL parameter means 0
+  /*! 
+   * second parameter must be postive (i.e. b > 0 below), otherwise function undefined
+   * 
+   * floor(a, b)
+   * * = a/b if a >= 0
+   * * = (a-b+1)/b if a < 0
+   */
+  virtual CG_outputRepr *CreateIntegerFloor(CG_outputRepr *lop, CG_outputRepr *rop) const = 0;
+  //! integer mod functions, NULL parameter means 0
+  /*! 
+   * second parameter must be postive (i.e. b > 0 below), otherwise function undefined
+   *
+   * mod(a, b) = a-b*floor(a, b) where result must lie in range [0,b)
+   */
+  virtual CG_outputRepr *CreateIntegerMod(CG_outputRepr *lop, CG_outputRepr *rop) const {
+    CG_outputRepr *lop2 = CreateCopy(lop);
+    CG_outputRepr *rop2 = CreateCopy(rop);
+    return CreateMinus(lop2, CreateTimes(rop2, CreateIntegerFloor(lop, rop)));
+  }
+  //! integer ceil functions, NULL parameter means 0
+  /*! 
+   * second parameter must be postive (i.e. b > 0 below), otherwise function undefined
+   *
+   * ceil(a, b) = -floor(-a, b) or floor(a+b-1, b) or floor(a-1, b)+1
+   */
+  virtual CG_outputRepr *CreateIntegerCeil(CG_outputRepr *lop, CG_outputRepr *rop) const {
+    return CreateMinus(NULL, CreateIntegerFloor(CreateMinus(NULL, lop), rop));
+  }
+
+  //! binary logical operation, NULL parameter means TRUE
+  virtual CG_outputRepr *CreateAnd(CG_outputRepr *lop, CG_outputRepr *rop) const = 0;
+
+  //! binary conditional Greater than or equal to
+  virtual CG_outputRepr *CreateGE(CG_outputRepr *lop, CG_outputRepr *rop) const {
+    return CreateLE(rop, lop);
+  } 
+  //! binary conditional Less than or equal to
+  virtual CG_outputRepr *CreateLE(CG_outputRepr *lop, CG_outputRepr *rop) const = 0;
+  //! binary conditional equal to
+  virtual CG_outputRepr *CreateEQ(CG_outputRepr *lop, CG_outputRepr *rop) const = 0;
+ 
+  //! join stmts together, NULL parameter allowed
+  virtual CG_outputRepr *StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const = 0;
+};
+
+}
+
+#endif
diff --git a/lib/codegen/include/code_gen/CG_outputRepr.h b/lib/codegen/include/code_gen/CG_outputRepr.h
new file mode 100644
index 0000000..0897007
--- /dev/null
+++ b/lib/codegen/include/code_gen/CG_outputRepr.h
@@ -0,0 +1,33 @@
+/*****************************************************************************
+ Copyright (C) 1994-2000 the Omega Project Team
+ Copyright (C) 2005-2011 Chun Chen
+ All Rights Reserved.
+
+ Purpose:
+   abstract base class of compiler IR code wrapper
+
+ Notes:
+
+ History:
+   04/17/96 - Lei Zhou - created
+*****************************************************************************/
+
+#ifndef _CG_OUTPUTREPR_H
+#define _CG_OUTPUTREPR_H
+
+namespace omega {
+
+class CG_outputRepr {
+public:
+  CG_outputRepr() {}
+  //! shallow delete
+  virtual ~CG_outputRepr() { }
+  virtual CG_outputRepr *clone() const = 0;
+  //! delete actual IR code wrapped inside
+  virtual void clear() { }
+  virtual void dump() const {}
+};
+
+}
+
+#endif
diff --git a/lib/codegen/include/code_gen/CG_stringBuilder.h b/lib/codegen/include/code_gen/CG_stringBuilder.h
new file mode 100644
index 0000000..09d3503
--- /dev/null
+++ b/lib/codegen/include/code_gen/CG_stringBuilder.h
@@ -0,0 +1,44 @@
+#ifndef _CG_STRINGBUILDER_H
+#define _CG_STRINGBUILDER_H
+
+#include <code_gen/CG_outputBuilder.h>
+#include <code_gen/CG_stringRepr.h>
+
+namespace omega {
+
+class CG_stringBuilder: public CG_outputBuilder { 
+public:
+  CG_stringBuilder() {}
+  ~CG_stringBuilder() {}
+  bool isInteger(CG_outputRepr *op) const;
+  CG_stringRepr *CreateSubstitutedStmt(int indent, CG_outputRepr *stmt, const std::vector<std::string> &vars, std::vector<CG_outputRepr *> &subs) const;
+  CG_stringRepr *CreateAssignment(int indent, CG_outputRepr *lhs, CG_outputRepr *rhs) const;
+  CG_stringRepr *CreateInvoke(const std::string &funcName, std::vector<CG_outputRepr *> &argList) const;
+  CG_stringRepr *CreateComment(int indent, const std::string &commentText) const;
+  CG_stringRepr* CreateAttribute(CG_outputRepr *control,
+                                          const std::string &commentText) const;
+  CG_outputRepr *CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const;
+  CG_outputRepr *CreatePrefetchAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &arrName, int hint) const;
+  CG_stringRepr *CreateIf(int indent, CG_outputRepr *guardCondition, CG_outputRepr *true_stmtList, CG_outputRepr *false_stmtList) const;
+  CG_stringRepr *CreateInductive(CG_outputRepr *index, CG_outputRepr *lower, CG_outputRepr *upper, CG_outputRepr *step) const;
+  CG_stringRepr *CreateLoop(int indent, CG_outputRepr *control, CG_outputRepr *stmtList) const;
+  CG_stringRepr *CreateInt(int num) const;
+  CG_stringRepr *CreateIdent(const std::string &varName) const;
+  CG_stringRepr *CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateMinus(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateTimes(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateDivide(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateIntegerFloor(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateIntegerMod(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateIntegerCeil(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateAnd(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateGE(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateLE(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *CreateEQ(CG_outputRepr *lop, CG_outputRepr *rop) const;
+  CG_stringRepr *StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const;
+};
+
+
+}
+
+#endif
diff --git a/lib/codegen/include/code_gen/CG_stringRepr.h b/lib/codegen/include/code_gen/CG_stringRepr.h
new file mode 100644
index 0000000..a6df85d
--- /dev/null
+++ b/lib/codegen/include/code_gen/CG_stringRepr.h
@@ -0,0 +1,43 @@
+/*****************************************************************************
+ Copyright (C) 1994-2000 the Omega Project Team
+ Copyright (C) 2005-2011 Chun Chen
+ All Rights Reserved.
+
+ Purpose:
+   pseudo string code wrapper
+
+ Notes:
+
+ History:
+   04/17/96 - Lei Zhou - created
+*****************************************************************************/
+
+#ifndef _CG_STRINGREPR_H
+#define _CG_STRINGREPR_H
+
+#include <code_gen/CG_outputRepr.h>
+#include <string>
+#include <iostream>
+
+namespace omega {
+
+class CG_stringRepr: public CG_outputRepr {
+private:
+  std::string s_;
+
+public:
+  CG_stringRepr() {}
+  CG_stringRepr(const std::string &s) { s_ = s; }
+  ~CG_stringRepr() {}
+  CG_outputRepr *clone() const { return new CG_stringRepr(s_); }
+  void dump() const { std::cout << s_ << std::endl; }
+
+  //---------------------------------------------------------------------------
+  // basic operation
+  //---------------------------------------------------------------------------
+  std::string GetString() const { return s_; }
+};
+
+}
+
+#endif
diff --git a/lib/codegen/include/code_gen/CG_utils.h b/lib/codegen/include/code_gen/CG_utils.h
new file mode 100755
index 0000000..a6128bc
--- /dev/null
+++ b/lib/codegen/include/code_gen/CG_utils.h
@@ -0,0 +1,45 @@
+#ifndef _CG_UTILS_H
+#define _CG_UTILS_H
+
+#include <omega.h>
+#include <code_gen/CG_outputBuilder.h>
+#include <basic/BoolSet.h>
+#include <vector>
+#include <set>
+#include <map>
+
+namespace omega {
+
+class CG_loop;
+
+CG_outputRepr *output_inequality_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, std::set<Variable_ID> excluded_floor_vars = std::set<Variable_ID>());
+CG_outputRepr *output_substitution_repr(CG_outputBuilder *ocg, const EQ_Handle &equality, Variable_ID v, bool apply_v_coef, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+CG_outputRepr *output_upper_bound_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+CG_outputRepr *output_lower_bound_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const EQ_Handle &stride_eq, Variable_ID wc, const Relation &R, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+
+CG_outputRepr *output_ident(CG_outputBuilder *ocg, const Relation &R, Variable_ID v, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > output_assignment(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+CG_outputRepr *output_loop(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+CG_outputRepr *output_guard(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+std::vector<CG_outputRepr *> output_substitutions(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+
+bool bound_must_hit_stride(const GEQ_Handle &inequality, Variable_ID v, const EQ_Handle &stride_eq, Variable_ID wc, const Relation &bounds, const Relation &known);
+std::pair<EQ_Handle, int> find_simplest_assignment(const Relation &R, Variable_ID v, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly = std::vector<std::pair<CG_outputRepr *, int> >());
+std::pair<bool, GEQ_Handle> find_floor_definition(const Relation &R, Variable_ID v, std::set<Variable_ID> excluded_floor_vars = std::set<Variable_ID>());
+std::pair<EQ_Handle, Variable_ID> find_simplest_stride(const Relation &R, Variable_ID v);
+Variable_ID replicate_floor_definition(const Relation &R, const Variable_ID floor_var, Relation &r, F_Exists *f_exists, F_And *f_root, std::map<Variable_ID, Variable_ID> &exists_mapping);
+
+Relation pick_one_guard(const Relation &R, int level = 0);
+CG_outputRepr *leaf_print_repr(BoolSet<> active, const std::map<int, Relation> &guards,
+                               CG_outputRepr *guard_repr, const Relation &known,
+                               int indent, CG_outputBuilder *ocg, const std::vector<int> &remap,
+                               const std::vector<Relation> &xforms, const std::vector<CG_outputRepr *> &stmts,
+                               const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+CG_outputRepr *loop_print_repr(const std::vector<CG_loop *> &loops, int start, int end,
+                               const Relation &guard, CG_outputRepr *guard_repr,
+                               int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts,
+                               const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly);
+
+}
+
+#endif
diff --git a/lib/codegen/include/code_gen/code_gen.h b/lib/codegen/include/code_gen/code_gen.h
new file mode 100644
index 0000000..abfab7c
--- /dev/null
+++ b/lib/codegen/include/code_gen/code_gen.h
@@ -0,0 +1,47 @@
+#if !defined(Already_Included_code_gen)
+#define Already_Included_code_gen
+
+#include <basic/Tuple.h>
+#include <omega/Relation.h>
+#include <code_gen/CG.h>
+#include <code_gen/CG_outputRepr.h>
+#include <code_gen/CG_outputBuilder.h>
+
+namespace omega {
+
+typedef Tuple<int> IntTuple;
+typedef Tuple<Relation> SetTuple;
+typedef Tuple<SetTuple> SetTupleTuple;
+typedef Tuple<Relation> RelTuple;
+typedef Tuple<RelTuple> RelTupleTuple;
+
+CG_outputRepr *MMGenerateCode(CG_outputBuilder* ocg,
+                              Tuple<Relation> &T, Tuple<Relation> &old_IS,
+                              const Tuple<CG_outputRepr *> &stmt_content,
+                              Relation &known, int effort=1);
+std::string MMGenerateCode(Tuple<Relation> &T, Tuple<Relation> &old_IS, Relation &known,
+                           int effort=1);
+
+//protonu-adding a new variant to keep Gabe's code happy
+CG_outputRepr* MMGenerateCode(CG_outputBuilder* ocg, RelTuple &T, SetTuple &old_IS, 
+		const Tuple<CG_outputRepr *> &stmt_content, Relation &known,
+		Tuple< IntTuple >& smtNonSplitLevels_,
+	       	std::vector< std::pair<int, std::string> > syncs_,
+	       	const Tuple< Tuple<std::string> >& loopIdxNames_, 
+	       	int effort=1);
+//end-protonu
+
+struct Polyhedra {
+  int last_level;
+  Tuple<Relation> transformations;
+  Relation known;
+
+  Tuple<int> remap;  // after initial iteration space's disjoint set splitting, the new statement number maps to old statement number
+  Tuple<Tuple<Relation> > projected_nIS;
+ 
+  Polyhedra(const Tuple<Relation> &T, const Tuple<Relation> &old_IS, const Relation &known = Relation::Null());
+  ~Polyhedra() {}
+};
+
+}
+#endif
diff --git a/lib/codegen/include/code_gen/codegen.h b/lib/codegen/include/code_gen/codegen.h
new file mode 100755
index 0000000..cb63bfd
--- /dev/null
+++ b/lib/codegen/include/code_gen/codegen.h
@@ -0,0 +1,48 @@
+#ifndef _CODEGEN_H
+#define _CODEGEN_H
+
+#include <omega/Relation.h>
+#include <code_gen/CG.h>
+#include <code_gen/CG_outputBuilder.h>
+#include <vector>
+#include <string>
+
+namespace omega {
+
+class CodeGen {
+public:
+  static const std::string loop_var_name_prefix;
+  static const int var_substitution_threshold;
+  
+protected:
+  //! projected_IS_[level-1][new stmt#]
+  std::vector<std::vector<Relation> > projected_IS_;
+  //! transformations[original stmt#]
+  std::vector<Relation> xforms_;
+  //! no need to generate code for constraints satisfied in known
+  Relation known_;
+  //! map new stmt# to original stmt#
+  std::vector<int> remap_;
+
+public:
+  CodeGen(const std::vector<Relation> &xforms, const std::vector<Relation> &IS, const Relation &known = Relation::Null(),
+		                 std::vector< std::vector<int > > smtNonSplitLevels_ =   std::vector< std::vector<int > >(),
+		                 std::vector< std::vector<std::string> > loopIdxNames_ =  std::vector< std::vector<std::string> >(),
+		                 std::vector< std::pair<int, std::string> >  syncs_ =    std::vector< std::pair<int, std::string> >()
+		         );
+  ~CodeGen() {}
+  
+  CG_result *buildAST(int effort = 1);
+  int num_level() const { return projected_IS_.size(); }
+  
+private:
+  CG_result *buildAST(int level, const BoolSet<> &active, bool split_on_const, const Relation &restriction);
+
+  friend class CG_result;
+  friend class CG_split;
+  friend class CG_loop;
+  friend class CG_leaf;
+};
+
+}
+#endif
diff --git a/lib/codegen/include/code_gen/codegen_error.h b/lib/codegen/include/code_gen/codegen_error.h
new file mode 100755
index 0000000..06ecc2b
--- /dev/null
+++ b/lib/codegen/include/code_gen/codegen_error.h
@@ -0,0 +1,15 @@
+#ifndef _CODEGEN_ERROR_H
+#define _CODEGEN_ERROR_H
+
+#include <stdexcept>
+
+namespace omega {
+
+struct codegen_error: public std::runtime_error {
+  codegen_error(const std::string &msg): std::runtime_error("codegen error: " + msg) {}
+};
+
+
+}
+#endif
+
diff --git a/lib/codegen/include/code_gen/output_repr.h b/lib/codegen/include/code_gen/output_repr.h
new file mode 100644
index 0000000..254e71b
--- /dev/null
+++ b/lib/codegen/include/code_gen/output_repr.h
@@ -0,0 +1,46 @@
+#ifndef OUTPUT_REPR_H
+#define OUTPUT_REPR_H
+
+#include <omega.h>
+#include <code_gen/CG_outputBuilder.h>
+#include <code_gen/CG_outputRepr.h>
+#include <vector>
+#include <set>
+
+namespace omega {
+extern int last_level;
+
+CG_outputRepr* outputIdent(CG_outputBuilder* ocg, const Relation &R, Variable_ID v, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+std::pair<CG_outputRepr *, bool> outputAssignment(CG_outputBuilder *ocg, const Relation &R_, Variable_ID v, Relation &enforced, CG_outputRepr *&if_repr, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+std::pair<CG_outputRepr *, bool> outputBounds(CG_outputBuilder* ocg, const Relation &bounds, Variable_ID v, int indent, Relation &enforced, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+Tuple<CG_outputRepr*> outputSubstitution(CG_outputBuilder* ocg, const Relation &R, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+CG_outputRepr* outputStatement(CG_outputBuilder* ocg, CG_outputRepr *stmt, int indent,  const Relation &mapping, const Relation &known, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+CG_outputRepr* outputGuard(CG_outputBuilder* ocg, const Relation &guards_in, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+CG_outputRepr* output_as_guard(CG_outputBuilder* ocg, const Relation &guards_in, Constraint_Handle e, bool is_equality, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+CG_outputRepr* output_EQ_strides(CG_outputBuilder* ocg, const Relation &guards_in, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+CG_outputRepr* output_GEQ_strides(CG_outputBuilder* ocg, const Relation &guards_in, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+CG_outputRepr *outputLBasRepr(CG_outputBuilder* ocg, const GEQ_Handle &g, Relation &bounds, Variable_ID v, coef_t stride, const EQ_Handle &strideEQ, Relation known, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+CG_outputRepr *outputUBasRepr(CG_outputBuilder* ocg, const GEQ_Handle &g,  Relation & bounds, Variable_ID v,
+                              coef_t /*stride*/, // currently unused
+                              const EQ_Handle &/*strideEQ*/,
+                              const std::vector<CG_outputRepr *> &assigned_on_the_fly = std::vector<CG_outputRepr *>(last_level, static_cast<CG_outputRepr *>(NULL)));
+CG_outputRepr* outputEasyBoundAsRepr(CG_outputBuilder* ocg, Relation &bounds, const Constraint_Handle &g, Variable_ID v, bool ignoreWC, int ceiling, const std::vector<CG_outputRepr *> &assigned_on_the_fly);
+
+
+bool boundHitsStride(const GEQ_Handle &g, Variable_ID v, const EQ_Handle &strideEQ, coef_t /*stride, currently unused*/, Relation known);
+Relation greatest_common_step(const Tuple<Relation> &I, const Tuple<int> &active, int level, const Relation &known = Relation::Null());
+bool findFloorInequality(Relation &r, Variable_ID v, GEQ_Handle &h, Variable_ID excluded);
+Relation project_onto_levels(Relation R, int last_level, bool wildcards);
+bool isSimpleStride(const EQ_Handle &g, Variable_ID v);
+int countStrides(Conjunct *c, Variable_ID v, EQ_Handle &strideEQ, bool &simple);
+bool hasBound(Relation r, int level, int UB);
+bool find_any_constraint(int s, int level, Relation &kr, int direction, Relation &S, bool approx);
+bool has_nonstride_EQ(Relation r, int level);
+Relation pickOverhead(Relation r, int liftTo);
+Relation minMaxOverhead(Relation r, int level);
+int max_fs_arity(const Constraint_Handle &c);
+
+
+}
+
+#endif