summaryrefslogtreecommitdiff
path: root/lib/codegen
diff options
context:
space:
mode:
Diffstat (limited to 'lib/codegen')
-rw-r--r--lib/codegen/CMakeLists.txt24
-rw-r--r--lib/codegen/include/code_gen/CG.h118
-rw-r--r--lib/codegen/include/code_gen/CG_outputBuilder.h161
-rw-r--r--lib/codegen/include/code_gen/CG_outputRepr.h33
-rw-r--r--lib/codegen/include/code_gen/CG_stringBuilder.h44
-rw-r--r--lib/codegen/include/code_gen/CG_stringRepr.h43
-rwxr-xr-xlib/codegen/include/code_gen/CG_utils.h45
-rw-r--r--lib/codegen/include/code_gen/code_gen.h47
-rwxr-xr-xlib/codegen/include/code_gen/codegen.h48
-rwxr-xr-xlib/codegen/include/code_gen/codegen_error.h15
-rw-r--r--lib/codegen/include/code_gen/output_repr.h46
-rw-r--r--lib/codegen/src/CG.cc1163
-rw-r--r--lib/codegen/src/CG_stringBuilder.cc487
-rwxr-xr-xlib/codegen/src/CG_utils.cc1735
-rwxr-xr-xlib/codegen/src/codegen.cc378
15 files changed, 4387 insertions, 0 deletions
diff --git a/lib/codegen/CMakeLists.txt b/lib/codegen/CMakeLists.txt
new file mode 100644
index 0000000..13bf0fe
--- /dev/null
+++ b/lib/codegen/CMakeLists.txt
@@ -0,0 +1,24 @@
+set(CG_SRC
+ src/codegen.cc
+ src/CG.cc
+ src/CG_stringBuilder.cc
+ src/CG_utils.cc
+ )
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-write-strings")
+
+include_directories(
+ include
+ ${OMEGAROOT}/include
+ )
+
+add_library(codegen
+ ${CG_SRC}
+ )
+
+add_dependencies(codegen omega)
+
+install(TARGETS codegen
+ ARCHIVE DESTINATION lib)
+install(DIRECTORY include
+ DESTINATION .)
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
diff --git a/lib/codegen/src/CG.cc b/lib/codegen/src/CG.cc
new file mode 100644
index 0000000..42bd172
--- /dev/null
+++ b/lib/codegen/src/CG.cc
@@ -0,0 +1,1163 @@
+/*****************************************************************************
+ Copyright (C) 1994-2000 the Omega Project Team
+ Copyright (C) 2005-2011 Chun Chen
+ All Rights Reserved.
+
+ Purpose:
+ CG node classes, used to build AST tree from polyhedra scanning.
+
+ Notes:
+ Parameter "restriction" is always tighter than "known" since CG_split
+ node does not correspond to any code for enforcement. This property is
+ destroyed after hoistGuard since "restriction" is not used anymore.
+ CG node's children are guaranteed not to be NULL, either NULL child is
+ removed from the children or the parent node itself becomes NULL.
+
+ History:
+ 04/20/96 printRepr added by D people. Lei Zhou
+ 10/24/06 hoistGuard added by chun
+ 08/03/10 collect CG classes into one place, by Chun Chen
+ 08/04/10 track dynamically substituted variables in printRepr, by chun
+ 04/02/11 rewrite the CG node classes, by chun
+ *****************************************************************************/
+
+#include <typeinfo>
+#include <assert.h>
+#include <omega.h>
+#include <code_gen/codegen.h>
+#include <code_gen/CG.h>
+#include <code_gen/CG_outputBuilder.h>
+#include <code_gen/CG_stringBuilder.h>
+#include <code_gen/CG_utils.h>
+#include <code_gen/codegen_error.h>
+#include <stack>
+#include <string.h>
+
+namespace omega {
+
+extern std::vector<std::vector<int> > smtNonSplitLevels;
+extern std::vector<std::vector<std::string> > loopIdxNames; //per stmt
+extern std::vector<std::pair<int, std::string> > syncs;
+
+extern int checkLoopLevel;
+extern int stmtForLoopCheck;
+extern int upperBoundForLevel;
+extern int lowerBoundForLevel;
+extern bool fillInBounds;
+
+//-----------------------------------------------------------------------------
+// Class: CG_result
+//-----------------------------------------------------------------------------
+
+CG_outputRepr *CG_result::printRepr(CG_outputBuilder *ocg,
+ const std::vector<CG_outputRepr *> &stmts) const {
+ return printRepr(1, ocg, stmts,
+ std::vector<std::pair<CG_outputRepr *, int> >(num_level(),
+ std::make_pair(static_cast<CG_outputRepr *>(NULL), 0)));
+}
+
+std::string CG_result::printString() const {
+ CG_stringBuilder ocg;
+ std::vector<CG_outputRepr *> stmts(codegen_->xforms_.size());
+ for (int i = 0; i < stmts.size(); i++)
+ stmts[i] = new CG_stringRepr("s" + to_string(i));
+ CG_stringRepr *repr = static_cast<CG_stringRepr *>(printRepr(&ocg, stmts));
+ for (int i = 0; i < stmts.size(); i++)
+ delete stmts[i];
+
+ if (repr != NULL) {
+ std::string s = repr->GetString();
+ delete repr;
+ return s;
+ } else
+ return std::string();
+}
+
+int CG_result::num_level() const {
+ return codegen_->num_level();
+}
+
+//-----------------------------------------------------------------------------
+// Class: CG_split
+//-----------------------------------------------------------------------------
+
+CG_result *CG_split::recompute(const BoolSet<> &parent_active,
+ const Relation &known, const Relation &restriction) {
+ active_ &= parent_active;
+ if (active_.empty()) {
+ delete this;
+ return NULL;
+ }
+
+
+ int i = 0;
+ while (i < restrictions_.size()) {
+ Relation new_restriction = Intersection(copy(restrictions_[i]),
+ copy(restriction));
+
+ new_restriction.simplify(2, 4);
+ //new_restriction.simplify();
+ clauses_[i] = clauses_[i]->recompute(active_, copy(known),
+ new_restriction);
+ if (clauses_[i] == NULL) {
+ restrictions_.erase(restrictions_.begin() + i);
+ clauses_.erase(clauses_.begin() + i);
+ } else
+ i++;
+ }
+
+
+ if (restrictions_.size() == 0) {
+ delete this;
+ return NULL;
+ } else
+ return this;
+}
+
+int CG_split::populateDepth() {
+ int max_depth = 0;
+ for (int i = 0; i < clauses_.size(); i++) {
+ int t = clauses_[i]->populateDepth();
+ if (t > max_depth)
+ max_depth = t;
+ }
+ return max_depth;
+}
+
+std::pair<CG_result *, Relation> CG_split::liftOverhead(int depth,
+ bool propagate_up) {
+ for (int i = 0; i < clauses_.size();) {
+ std::pair<CG_result *, Relation> result = clauses_[i]->liftOverhead(
+ depth, propagate_up);
+ if (result.first == NULL)
+ clauses_.erase(clauses_.begin() + i);
+ else {
+ clauses_[i] = result.first;
+ if (!result.second.is_obvious_tautology())
+ return std::make_pair(this, result.second);
+ i++;
+ }
+
+ }
+
+ if (clauses_.size() == 0) {
+ delete this;
+ return std::make_pair(static_cast<CG_result *>(NULL),
+ Relation::True(num_level()));
+ } else
+ return std::make_pair(this, Relation::True(num_level()));
+}
+
+Relation CG_split::hoistGuard() {
+ std::vector<Relation> guards;
+ for (int i = 0; i < clauses_.size(); i++)
+ guards.push_back(clauses_[i]->hoistGuard());
+
+ return SimpleHull(guards, true, true);
+}
+
+void CG_split::removeGuard(const Relation &guard) {
+ for (int i = 0; i < clauses_.size(); i++)
+ clauses_[i]->removeGuard(guard);
+}
+
+std::vector<CG_result *> CG_split::findNextLevel() const {
+ std::vector<CG_result *> result;
+ for (int i = 0; i < clauses_.size(); i++) {
+ CG_split *splt = dynamic_cast<CG_split *>(clauses_[i]);
+ if (splt != NULL) {
+ std::vector<CG_result *> t = splt->findNextLevel();
+ result.insert(result.end(), t.begin(), t.end());
+ } else
+ result.push_back(clauses_[i]);
+ }
+
+ return result;
+}
+
+CG_outputRepr *CG_split::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 *stmtList = NULL;
+ std::vector<CG_result *> next_level = findNextLevel();
+
+ std::vector<CG_loop *> cur_loops;
+ for (int i = 0; i < next_level.size(); i++) {
+ CG_loop *lp = dynamic_cast<CG_loop *>(next_level[i]);
+ if (lp != NULL) {
+ cur_loops.push_back(lp);
+ } else {
+ stmtList = ocg->StmtListAppend(stmtList,
+ loop_print_repr(cur_loops, 0, cur_loops.size(),
+ Relation::True(num_level()), NULL, indent, ocg,
+ stmts, assigned_on_the_fly));
+ stmtList = ocg->StmtListAppend(stmtList,
+ next_level[i]->printRepr(indent, ocg, stmts,
+ assigned_on_the_fly));
+ cur_loops.clear();
+ }
+ }
+
+ stmtList = ocg->StmtListAppend(stmtList,
+ loop_print_repr(cur_loops, 0, cur_loops.size(),
+ Relation::True(num_level()), NULL, indent, ocg, stmts,
+ assigned_on_the_fly));
+ return stmtList;
+}
+
+CG_result *CG_split::clone() const {
+ std::vector<CG_result *> clauses(clauses_.size());
+ for (int i = 0; i < clauses_.size(); i++)
+ clauses[i] = clauses_[i]->clone();
+ return new CG_split(codegen_, active_, restrictions_, clauses);
+}
+
+void CG_split::dump(int indent) const {
+ std::string prefix;
+ for (int i = 0; i < indent; i++)
+ prefix += " ";
+ std::cout << prefix << "SPLIT: " << active_ << std::endl;
+ for (int i = 0; i < restrictions_.size(); i++) {
+ std::cout << prefix << "restriction: ";
+ const_cast<CG_split *>(this)->restrictions_[i].print();
+ clauses_[i]->dump(indent + 1);
+ }
+
+}
+
+//-----------------------------------------------------------------------------
+// Class: CG_loop
+//-----------------------------------------------------------------------------
+
+CG_result *CG_loop::recompute(const BoolSet<> &parent_active,
+ const Relation &known, const Relation &restriction) {
+ known_ = copy(known);
+ restriction_ = copy(restriction);
+ active_ &= parent_active;
+
+ std::vector<Relation> Rs;
+ for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) {
+ Relation r = Intersection(copy(restriction),
+ copy(codegen_->projected_IS_[level_ - 1][*i]));
+
+ //r.simplify(2, 4);
+ r.simplify();
+ if (!r.is_upper_bound_satisfiable()) {
+ active_.unset(*i);
+ continue;
+ }
+ Rs.push_back(copy(r));
+ }
+
+ if (active_.empty()) {
+ delete this;
+ return NULL;
+ }
+
+ Relation hull = SimpleHull(Rs, true, true);
+
+ //hull.simplify(2,4);
+
+ // check if actual loop is needed
+ std::pair<EQ_Handle, int> result = find_simplest_assignment(hull,
+ hull.set_var(level_));
+ if (result.second < INT_MAX) {
+ needLoop_ = false;
+
+ bounds_ = Relation(hull.n_set());
+ F_Exists *f_exists = bounds_.add_and()->add_exists();
+ F_And *f_root = f_exists->add_and();
+ std::map<Variable_ID, Variable_ID> exists_mapping;
+ EQ_Handle h = f_root->add_EQ();
+ for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) {
+ Variable_ID v = cvi.curr_var();
+ switch (v->kind()) {
+ case Input_Var:
+ h.update_coef(bounds_.input_var(v->get_position()),
+ cvi.curr_coef());
+ break;
+ case Wildcard_Var: {
+ Variable_ID v2 = replicate_floor_definition(hull, v, bounds_,
+ f_exists, f_root, exists_mapping);
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ case Global_Var: {
+ Global_Var_ID g = v->get_global_var();
+ Variable_ID v2;
+ if (g->arity() == 0)
+ v2 = bounds_.get_local(g);
+ else
+ v2 = bounds_.get_local(g, v->function_of());
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(false);
+ }
+ }
+ h.update_const(result.first.get_const());
+ bounds_.simplify();
+ }
+ // loop iterates more than once, extract bounds now
+ else {
+ needLoop_ = true;
+
+ bounds_ = Relation(hull.n_set());
+ F_Exists *f_exists = bounds_.add_and()->add_exists();
+ F_And *f_root = f_exists->add_and();
+ std::map<Variable_ID, Variable_ID> exists_mapping;
+
+ Relation b = Gist(copy(hull), copy(known), 1);
+ bool has_unresolved_bound = false;
+
+ std::set<Variable_ID> excluded_floor_vars;
+ excluded_floor_vars.insert(b.set_var(level_));
+ for (GEQ_Iterator e(b.single_conjunct()->GEQs()); e; e++)
+ if ((*e).get_coef(b.set_var(level_)) != 0) {
+ bool is_bound = true;
+ for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) {
+ std::pair<bool, GEQ_Handle> result = find_floor_definition(
+ b, cvi.curr_var(), excluded_floor_vars);
+ if (!result.first) {
+ is_bound = false;
+ has_unresolved_bound = true;
+ break;
+ }
+ }
+
+ if (!is_bound)
+ continue;
+
+ GEQ_Handle h = f_root->add_GEQ();
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++) {
+ Variable_ID v = cvi.curr_var();
+ switch (v->kind()) {
+ case Input_Var:
+ h.update_coef(bounds_.input_var(v->get_position()),
+ cvi.curr_coef());
+ break;
+ case Wildcard_Var: {
+ Variable_ID v2 = replicate_floor_definition(b, v,
+ bounds_, f_exists, f_root, exists_mapping);
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ case Global_Var: {
+ Global_Var_ID g = v->get_global_var();
+ Variable_ID v2;
+ if (g->arity() == 0)
+ v2 = bounds_.get_local(g);
+ else
+ v2 = bounds_.get_local(g, v->function_of());
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(false);
+ }
+ }
+ h.update_const((*e).get_const());
+ }
+
+ if (has_unresolved_bound) {
+ b = Approximate(b);
+ b.simplify(2, 4);
+ //Simplification of Hull
+ hull = Approximate(hull);
+ hull.simplify(2, 4);
+ //end : Anand
+ for (GEQ_Iterator e(b.single_conjunct()->GEQs()); e; e++)
+ if ((*e).get_coef(b.set_var(level_)) != 0)
+ f_root->add_GEQ(*e);
+ }
+ bounds_.simplify();
+ hull.simplify(2,4);
+ // Since current SimpleHull does not support max() upper bound or min() lower bound,
+ // we have to forcefully split the loop when hull approximation does not return any bound.
+ bool has_lb = false;
+ bool has_ub = false;
+ for (GEQ_Iterator e = bounds_.single_conjunct()->GEQs(); e; e++) {
+ if ((*e).get_coef(bounds_.set_var(level_)) > 0)
+ has_lb = true;
+ else if ((*e).get_coef(bounds_.set_var(level_)) < 0)
+ has_ub = true;
+ if (has_lb && has_ub)
+ break;
+ }
+
+ if (!has_lb) {
+ for (int i = 0; i < Rs.size(); i++) {
+ Relation r = Approximate(copy(Rs[i]));
+ r.simplify(2, 4);
+ for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++)
+ if ((*e).get_coef(r.input_var(level_)) > 0) {
+ Relation r2 = Relation::True(num_level());
+ r2.and_with_GEQ(*e);
+ r2.simplify();
+ std::vector<Relation> restrictions(2);
+ restrictions[0] = Complement(copy(r2));
+ restrictions[0].simplify();
+ restrictions[1] = r2;
+ std::vector<CG_result *> clauses(2);
+ clauses[0] = this;
+ clauses[1] = this->clone();
+ CG_result *cgr = new CG_split(codegen_, active_,
+ restrictions, clauses);
+ cgr = cgr->recompute(active_, copy(known),
+ copy(restriction));
+ return cgr;
+ }
+ }
+ for (int i = 0; i < Rs.size(); i++) {
+ Relation r = Approximate(copy(Rs[i]));
+ r.simplify(2, 4);
+ for (EQ_Iterator e = r.single_conjunct()->EQs(); e; e++)
+ if ((*e).get_coef(r.input_var(level_)) != 0) {
+ Relation r2 = Relation::True(num_level());
+ r2.and_with_GEQ(*e);
+ r2.simplify();
+ std::vector<Relation> restrictions(2);
+ if ((*e).get_coef(r.input_var(level_)) > 0) {
+ restrictions[0] = Complement(copy(r2));
+ restrictions[0].simplify();
+ restrictions[1] = r2;
+ } else {
+ restrictions[0] = r2;
+ restrictions[1] = Complement(copy(r2));
+ restrictions[1].simplify();
+ }
+ std::vector<CG_result *> clauses(2);
+ clauses[0] = this;
+ clauses[1] = this->clone();
+ CG_result *cgr = new CG_split(codegen_, active_,
+ restrictions, clauses);
+ cgr = cgr->recompute(active_, copy(known),
+ copy(restriction));
+ return cgr;
+ }
+ }
+ } else if (!has_ub) {
+ for (int i = 0; i < Rs.size(); i++) {
+ Relation r = Approximate(copy(Rs[i]));
+ r.simplify(2, 4);
+ for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++)
+ if ((*e).get_coef(r.input_var(level_)) < 0) {
+ Relation r2 = Relation::True(num_level());
+ r2.and_with_GEQ(*e);
+ r2.simplify();
+ std::vector<Relation> restrictions(2);
+ restrictions[1] = Complement(copy(r2));
+ restrictions[1].simplify();
+ restrictions[0] = r2;
+ std::vector<CG_result *> clauses(2);
+ clauses[0] = this;
+ clauses[1] = this->clone();
+ CG_result *cgr = new CG_split(codegen_, active_,
+ restrictions, clauses);
+ cgr = cgr->recompute(active_, copy(known),
+ copy(restriction));
+ return cgr;
+ }
+ }
+ for (int i = 0; i < Rs.size(); i++) {
+ Relation r = Approximate(copy(Rs[i]));
+ r.simplify(2, 4);
+ for (EQ_Iterator e = r.single_conjunct()->EQs(); e; e++)
+ if ((*e).get_coef(r.input_var(level_)) != 0) {
+ Relation r2 = Relation::True(num_level());
+ r2.and_with_GEQ(*e);
+ r2.simplify();
+ std::vector<Relation> restrictions(2);
+ if ((*e).get_coef(r.input_var(level_)) > 0) {
+ restrictions[0] = Complement(copy(r2));
+ restrictions[0].simplify();
+ restrictions[1] = r2;
+ } else {
+ restrictions[0] = r2;
+ restrictions[1] = Complement(copy(r2));
+ restrictions[1].simplify();
+ }
+ std::vector<CG_result *> clauses(2);
+ clauses[0] = this;
+ clauses[1] = this->clone();
+ CG_result *cgr = new CG_split(codegen_, active_,
+ restrictions, clauses);
+ cgr = cgr->recompute(active_, copy(known),
+ copy(restriction));
+ return cgr;
+ }
+ }
+ }
+
+ if (!has_lb && !has_ub)
+ throw codegen_error(
+ "can't find any bound at loop level " + to_string(level_));
+ else if (!has_lb)
+ throw codegen_error(
+ "can't find lower bound at loop level "
+ + to_string(level_));
+ else if (!has_ub)
+ throw codegen_error(
+ "can't find upper bound at loop level "
+ + to_string(level_));
+ }
+ bounds_.copy_names(hull);
+ bounds_.setup_names();
+
+ // additional guard/stride condition extraction
+ if (needLoop_) {
+ Relation cur_known = Intersection(copy(bounds_), copy(known_));
+ cur_known.simplify();
+ hull = Gist(hull, copy(cur_known), 1);
+
+ std::pair<EQ_Handle, Variable_ID> result = find_simplest_stride(hull,
+ hull.set_var(level_));
+ if (result.second != NULL)
+ if (abs(result.first.get_coef(hull.set_var(level_))) == 1) {
+ F_Exists *f_exists = bounds_.and_with_and()->add_exists();
+ F_And *f_root = f_exists->add_and();
+ std::map<Variable_ID, Variable_ID> exists_mapping;
+ EQ_Handle h = f_root->add_EQ();
+ for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) {
+ Variable_ID v = cvi.curr_var();
+ switch (v->kind()) {
+ case Input_Var:
+ h.update_coef(bounds_.input_var(v->get_position()),
+ cvi.curr_coef());
+ break;
+ case Wildcard_Var: {
+ Variable_ID v2;
+ if (v == result.second)
+ v2 = f_exists->declare();
+ else
+ v2 = replicate_floor_definition(hull, v, bounds_,
+ f_exists, f_root, exists_mapping);
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ case Global_Var: {
+ Global_Var_ID g = v->get_global_var();
+ Variable_ID v2;
+ if (g->arity() == 0)
+ v2 = bounds_.get_local(g);
+ else
+ v2 = bounds_.get_local(g, v->function_of());
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(false);
+ }
+ }
+ h.update_const(result.first.get_const());
+ } else {
+ // since gist is not powerful enough on modular constraints for now,
+ // make an educated guess
+ coef_t stride = abs(result.first.get_coef(result.second))
+ / gcd(abs(result.first.get_coef(result.second)),
+ abs(
+ result.first.get_coef(
+ hull.set_var(level_))));
+
+ Relation r1(hull.n_inp());
+ F_Exists *f_exists = r1.add_and()->add_exists();
+ F_And *f_root = f_exists->add_and();
+ std::map<Variable_ID, Variable_ID> exists_mapping;
+ EQ_Handle h = f_root->add_EQ();
+ for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) {
+ Variable_ID v = cvi.curr_var();
+ switch (v->kind()) {
+ case Input_Var:
+ h.update_coef(r1.input_var(v->get_position()),
+ cvi.curr_coef());
+ break;
+ case Wildcard_Var: {
+ Variable_ID v2;
+ if (v == result.second)
+ v2 = f_exists->declare();
+ else
+ v2 = replicate_floor_definition(hull, v, r1,
+ f_exists, f_root, exists_mapping);
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ case Global_Var: {
+ Global_Var_ID g = v->get_global_var();
+ Variable_ID v2;
+ if (g->arity() == 0)
+ v2 = r1.get_local(g);
+ else
+ v2 = r1.get_local(g, v->function_of());
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(false);
+ }
+ }
+ h.update_const(result.first.get_const());
+ r1.simplify();
+
+ bool guess_success = false;
+ for (GEQ_Iterator e(bounds_.single_conjunct()->GEQs()); e; e++)
+ if ((*e).get_coef(bounds_.set_var(level_)) == 1) {
+ Relation r2(hull.n_inp());
+ F_Exists *f_exists = r2.add_and()->add_exists();
+ F_And *f_root = f_exists->add_and();
+ std::map<Variable_ID, Variable_ID> exists_mapping;
+ EQ_Handle h = f_root->add_EQ();
+ h.update_coef(f_exists->declare(), stride);
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++) {
+ Variable_ID v = cvi.curr_var();
+ switch (v->kind()) {
+ case Input_Var:
+ h.update_coef(r2.input_var(v->get_position()),
+ cvi.curr_coef());
+ break;
+ case Wildcard_Var: {
+ Variable_ID v2 = replicate_floor_definition(
+ hull, v, r2, f_exists, f_root,
+ exists_mapping);
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ case Global_Var: {
+ Global_Var_ID g = v->get_global_var();
+ Variable_ID v2;
+ if (g->arity() == 0)
+ v2 = r2.get_local(g);
+ else
+ v2 = r2.get_local(g, v->function_of());
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(false);
+ }
+ }
+ h.update_const((*e).get_const());
+ r2.simplify();
+
+ if (Gist(copy(r1),
+ Intersection(copy(cur_known), copy(r2)), 1).is_obvious_tautology()
+ && Gist(copy(r2),
+ Intersection(copy(cur_known), copy(r1)),
+ 1).is_obvious_tautology()) {
+ bounds_ = Intersection(bounds_, r2);
+ bounds_.simplify();
+ guess_success = true;
+ break;
+ }
+ }
+
+ // this is really a stride with non-unit coefficient for this loop variable
+ if (!guess_success) {
+ // TODO: for stride ax = b mod n it might be beneficial to
+ // generate modular linear equation solver code for
+ // runtime to get the starting position in printRepr,
+ // and stride would be n/gcd(|a|,n), thus this stride
+ // can be put into bounds_ too.
+ }
+
+ }
+
+ hull = Project(hull, hull.set_var(level_));
+ hull.simplify(2, 4);
+ guard_ = Gist(hull, Intersection(copy(bounds_), copy(known_)), 1);
+ }
+ // don't generate guard for non-actual loop, postpone it. otherwise
+ // redundant if-conditions might be generated since for-loop semantics
+ // includes implicit comparison checking. -- by chun 09/14/10
+ else
+ guard_ = Relation::True(num_level());
+ guard_.copy_names(bounds_);
+ guard_.setup_names();
+
+ //guard_.simplify();
+ // recursively down the AST
+ Relation new_known = Intersection(copy(known),
+ Intersection(copy(bounds_), copy(guard_)));
+ new_known.simplify(2, 4);
+ Relation new_restriction = Intersection(copy(restriction),
+ Intersection(copy(bounds_), copy(guard_)));
+ new_restriction.simplify(2, 4);
+ body_ = body_->recompute(active_, new_known, new_restriction);
+ if (body_ == NULL) {
+ delete this;
+ return NULL;
+ } else
+ return this;
+}
+
+int CG_loop::populateDepth() {
+ int depth = body_->populateDepth();
+ if (needLoop_)
+ depth_ = depth + 1;
+ else
+ depth_ = depth;
+ return depth_;
+}
+
+std::pair<CG_result *, Relation> CG_loop::liftOverhead(int depth,
+ bool propagate_up) {
+ if (depth_ > depth) {
+ assert(propagate_up == false);
+ std::pair<CG_result *, Relation> result = body_->liftOverhead(depth,
+ false);
+ body_ = result.first;
+ return std::make_pair(this, Relation::True(num_level()));
+ } else { // (depth_ <= depth)
+ if (propagate_up) {
+ Relation r = pick_one_guard(guard_, level_);
+ if (!r.is_obvious_tautology())
+ return std::make_pair(this, r);
+ }
+
+ std::pair<CG_result *, Relation> result;
+ if (propagate_up || needLoop_)
+ result = body_->liftOverhead(depth, true);
+ else
+ result = body_->liftOverhead(depth, false);
+ body_ = result.first;
+ if (result.second.is_obvious_tautology())
+ return std::make_pair(this, result.second);
+
+ // loop is an assignment, replace this loop variable in overhead condition
+ if (!needLoop_) {
+ result.second = Intersection(result.second, copy(bounds_));
+ result.second = Project(result.second,
+ result.second.set_var(level_));
+ result.second.simplify(2, 4);
+ }
+
+
+ int max_level = 0;
+ bool has_wildcard = false;
+ bool direction = true;
+ for (EQ_Iterator e(result.second.single_conjunct()->EQs()); e; e++)
+ if ((*e).has_wildcards()) {
+ if (has_wildcard)
+ assert(false);
+ else
+ has_wildcard = true;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ if (cvi.curr_var()->kind() == Input_Var
+ && cvi.curr_var()->get_position() > max_level)
+ max_level = cvi.curr_var()->get_position();
+ } else
+ assert(false);
+
+ if (!has_wildcard) {
+ int num_simple_geq = 0;
+ for (GEQ_Iterator e(result.second.single_conjunct()->GEQs()); e;
+ e++)
+ if (!(*e).has_wildcards()) {
+ num_simple_geq++;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ if (cvi.curr_var()->kind() == Input_Var
+ && cvi.curr_var()->get_position() > max_level) {
+ max_level = cvi.curr_var()->get_position();
+ direction = (cvi.curr_coef() < 0) ? true : false;
+ }
+ } else {
+ has_wildcard = true;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ if (cvi.curr_var()->kind() == Input_Var
+ && cvi.curr_var()->get_position() > max_level) {
+ max_level = cvi.curr_var()->get_position();
+ }
+ }
+ assert(
+ (has_wildcard && num_simple_geq == 0) || (!has_wildcard && num_simple_geq == 1));
+ }
+
+ // check if this is the top loop level for splitting for this overhead
+ if (!propagate_up || (has_wildcard && max_level == level_ - 1)
+ || (!has_wildcard && max_level == level_)) {
+ std::vector<Relation> restrictions(2);
+ std::vector<CG_result *> clauses(2);
+ int saved_num_level = num_level();
+ if (has_wildcard || direction) {
+ restrictions[1] = Complement(copy(result.second));
+ restrictions[1].simplify();
+ clauses[1] = this->clone();
+ restrictions[0] = result.second;
+ clauses[0] = this;
+ } else {
+ restrictions[0] = Complement(copy(result.second));
+ restrictions[0].simplify();
+ clauses[0] = this->clone();
+ restrictions[1] = result.second;
+ clauses[1] = this;
+ }
+ CG_result *cgr = new CG_split(codegen_, active_, restrictions,
+ clauses);
+ CG_result *new_cgr = cgr->recompute(active_, copy(known_),
+ copy(restriction_));
+ new_cgr->populateDepth();
+ assert(new_cgr==cgr);
+ if (static_cast<CG_split *>(new_cgr)->clauses_.size() == 1)
+ // infinite recursion detected, bail out
+ return std::make_pair(new_cgr, Relation::True(saved_num_level));
+ else
+ return cgr->liftOverhead(depth, propagate_up);
+ } else
+ return std::make_pair(this, result.second);
+ }
+}
+
+Relation CG_loop::hoistGuard() {
+
+ Relation r = body_->hoistGuard();
+
+ // TODO: should bookkeep catched contraints in loop output as enforced and check if anything missing
+ // if (!Gist(copy(b), copy(enforced)).is_obvious_tautology()) {
+ // fprintf(stderr, "need to generate extra guard inside the loop\n");
+ // }
+
+ if (!needLoop_)
+ r = Intersection(r, copy(bounds_));
+ r = Project(r, r.set_var(level_));
+ r = Gist(r, copy(known_), 1);
+
+ Relation eliminate_existentials_r;
+ Relation eliminate_existentials_known;
+
+ eliminate_existentials_r = copy(r);
+ if (!r.is_obvious_tautology()) {
+ eliminate_existentials_r = Approximate(copy(r));
+ eliminate_existentials_r.simplify(2,4);
+ eliminate_existentials_known = Approximate(copy(known_));
+ eliminate_existentials_known.simplify(2,4);
+
+ eliminate_existentials_r = Gist( eliminate_existentials_r, eliminate_existentials_known, 1);
+ }
+
+
+ if (!eliminate_existentials_r.is_obvious_tautology()) {
+ // if (!r.is_obvious_tautology()) {
+ body_->removeGuard(r);
+ guard_ = Intersection(guard_, copy(r));
+ guard_.simplify();
+ }
+
+ return guard_;
+
+ // return ifList;
+ // }
+
+
+}
+
+void CG_loop::removeGuard(const Relation &guard) {
+ known_ = Intersection(known_, copy(guard));
+ known_.simplify();
+
+ guard_ = Gist(guard_, copy(known_), 1);
+ guard_.copy_names(known_);
+ guard_.setup_names();
+}
+
+CG_outputRepr *CG_loop::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 {
+ return printRepr(true, indent, ocg, stmts, assigned_on_the_fly);
+}
+
+CG_outputRepr *CG_loop::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_outputRepr *guardRepr;
+ if (do_print_guard)
+ guardRepr = output_guard(ocg, guard_, assigned_on_the_fly);
+ else
+ guardRepr = NULL;
+
+ Relation cur_known = Intersection(copy(known_), copy(guard_));
+ cur_known.simplify();
+ if (needLoop_) {
+
+ if (checkLoopLevel)
+ if (level_ == checkLoopLevel)
+ if (active_.get(stmtForLoopCheck))
+ fillInBounds = true;
+
+ CG_outputRepr *ctrlRepr = output_loop(ocg, bounds_, level_, cur_known,
+ assigned_on_the_fly);
+
+ fillInBounds = false;
+
+ CG_outputRepr *bodyRepr = body_->printRepr(
+ (guardRepr == NULL) ? indent + 1 : indent + 2, ocg, stmts,
+ assigned_on_the_fly);
+ CG_outputRepr * loopRepr;
+
+ if (guardRepr == NULL)
+ loopRepr = ocg->CreateLoop(indent, ctrlRepr, bodyRepr);
+ else
+ loopRepr = ocg->CreateLoop(indent + 1, ctrlRepr, bodyRepr);
+
+ if (!smtNonSplitLevels.empty()) {
+ bool blockLoop = false;
+ bool threadLoop = false;
+ bool sync = false;
+ int firstActiveStmt = -1;
+ for (int s = 0; s < active_.size(); s++) {
+ if (active_.get(s)) {
+ if (firstActiveStmt < 0)
+ firstActiveStmt = s;
+ //We assume smtNonSplitLevels is only used to mark the first of
+ //the block or thread loops to be reduced in CUDA-CHiLL. Here we
+ //place some comments to help with final code generation.
+ //int idx = smtNonSplitLevels[s].index(level_);
+
+ if (s < smtNonSplitLevels.size()) {
+ if (smtNonSplitLevels[s].size() > 0)
+ if (smtNonSplitLevels[s][0] == level_) {
+ blockLoop = true;
+ }
+ //Assume every stmt marked with a thread loop index also has a block loop idx
+ if (smtNonSplitLevels[s].size() > 1)
+ if (smtNonSplitLevels[s][1] == level_) {
+ threadLoop = true;
+ }
+ }
+ }
+ }
+ if (blockLoop && threadLoop) {
+ fprintf(stderr,
+ "Warning, have %d level more than once in smtNonSplitLevels\n",
+ level_);
+ threadLoop = false;
+ }
+ std::string preferredIdx;
+ if (loopIdxNames.size()
+ && (level_ / 2) - 1 < loopIdxNames[firstActiveStmt].size())
+ preferredIdx = loopIdxNames[firstActiveStmt][(level_ / 2) - 1];
+ for (int s = 0; s < active_.size(); s++) {
+ if (active_.get(s)) {
+ for (int i = 0; i < syncs.size(); i++) {
+ if (syncs[i].first == s
+ && strcmp(syncs[i].second.c_str(),
+ preferredIdx.c_str()) == 0) {
+ sync = true;
+ //printf("FOUND SYNC\n");
+ }
+
+ }
+ }
+
+ }
+ if (threadLoop || blockLoop || preferredIdx.length() != 0) {
+ char buf[1024];
+ std::string loop;
+ if (blockLoop)
+ loop = "blockLoop ";
+ if (threadLoop)
+ loop = "threadLoop ";
+ if (preferredIdx.length() != 0 && sync) {
+ sprintf(buf, "~cuda~ %spreferredIdx: %s sync", loop.c_str(),
+ preferredIdx.c_str());
+ } else if (preferredIdx.length() != 0) {
+ sprintf(buf, "~cuda~ %spreferredIdx: %s", loop.c_str(),
+ preferredIdx.c_str());
+ } else {
+ sprintf(buf, "~cuda~ %s", loop.c_str());
+ }
+
+
+ loopRepr = ocg->CreateAttribute(loopRepr, buf);
+ }
+
+ }
+ if (guardRepr == NULL)
+ return loopRepr;
+ else
+ return ocg->CreateIf(indent, guardRepr, loopRepr, NULL);
+ } else {
+ std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > result =
+ output_assignment(ocg, bounds_, level_, cur_known,
+ assigned_on_the_fly);
+ guardRepr = ocg->CreateAnd(guardRepr, result.first);
+
+ if (result.second.second < CodeGen::var_substitution_threshold) {
+ std::vector<std::pair<CG_outputRepr *, int> > atof =
+ assigned_on_the_fly;
+ atof[level_ - 1] = result.second;
+ CG_outputRepr *bodyRepr = body_->printRepr(
+ (guardRepr == NULL) ? indent : indent + 1, ocg, stmts,
+ atof);
+ delete atof[level_ - 1].first;
+ if (guardRepr == NULL)
+ return bodyRepr;
+ else
+ return ocg->CreateIf(indent, guardRepr, bodyRepr, NULL);
+ } else {
+ CG_outputRepr *assignRepr = ocg->CreateAssignment(
+ (guardRepr == NULL) ? indent : indent + 1,
+ output_ident(ocg, bounds_,
+ const_cast<CG_loop *>(this)->bounds_.set_var(
+ level_), assigned_on_the_fly),
+ result.second.first);
+ CG_outputRepr *bodyRepr = body_->printRepr(
+ (guardRepr == NULL) ? indent : indent + 1, ocg, stmts,
+ assigned_on_the_fly);
+ if (guardRepr == NULL)
+ return ocg->StmtListAppend(assignRepr, bodyRepr);
+ else
+ return ocg->CreateIf(indent, guardRepr,
+ ocg->StmtListAppend(assignRepr, bodyRepr), NULL);
+ }
+
+ }
+}
+
+CG_result *CG_loop::clone() const {
+ return new CG_loop(codegen_, active_, level_, body_->clone());
+}
+
+void CG_loop::dump(int indent) const {
+ std::string prefix;
+ for (int i = 0; i < indent; i++)
+ prefix += " ";
+ std::cout << prefix << "LOOP (level " << level_ << "): " << active_
+ << std::endl;
+ std::cout << prefix << "known: ";
+ const_cast<CG_loop *>(this)->known_.print();
+ std::cout << prefix << "restriction: ";
+ const_cast<CG_loop *>(this)->restriction_.print();
+ std::cout << prefix << "bounds: ";
+ const_cast<CG_loop *>(this)->bounds_.print();
+ std::cout << prefix << "guard: ";
+ const_cast<CG_loop *>(this)->guard_.print();
+ body_->dump(indent + 1);
+}
+
+//-----------------------------------------------------------------------------
+// Class: CG_leaf
+//-----------------------------------------------------------------------------
+
+CG_result* CG_leaf::recompute(const BoolSet<> &parent_active,
+ const Relation &known, const Relation &restriction) {
+ active_ &= parent_active;
+ known_ = copy(known);
+
+ guards_.clear();
+ for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) {
+ Relation r = Intersection(
+ copy(codegen_->projected_IS_[num_level() - 1][*i]),
+ copy(restriction));
+ r.simplify(2, 4);
+ if (!r.is_upper_bound_satisfiable())
+ active_.unset(*i);
+ else {
+ r = Gist(r, copy(known), 1);
+ if (!r.is_obvious_tautology()) {
+ guards_[*i] = r;
+ guards_[*i].copy_names(known);
+ guards_[*i].setup_names();
+ }
+ }
+ }
+
+
+ if (active_.empty()) {
+ delete this;
+ return NULL;
+ } else
+ return this;
+}
+
+std::pair<CG_result *, Relation> CG_leaf::liftOverhead(int depth, bool) {
+ if (depth == 0)
+ return std::make_pair(this, Relation::True(num_level()));
+
+ for (std::map<int, Relation>::iterator i = guards_.begin();
+ i != guards_.end(); i++) {
+ Relation r = pick_one_guard(i->second);
+ if (!r.is_obvious_tautology()) {
+ bool has_wildcard = false;
+ int max_level = 0;
+ for (EQ_Iterator e(r.single_conjunct()->EQs()); e; e++) {
+ if ((*e).has_wildcards())
+ has_wildcard = true;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ if (cvi.curr_var()->kind() == Input_Var
+ && cvi.curr_var()->get_position() > max_level)
+ max_level = cvi.curr_var()->get_position();
+ }
+ for (GEQ_Iterator e(r.single_conjunct()->GEQs()); e; e++) {
+ if ((*e).has_wildcards())
+ has_wildcard = true;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ if (cvi.curr_var()->kind() == Input_Var
+ && cvi.curr_var()->get_position() > max_level)
+ max_level = cvi.curr_var()->get_position();
+ }
+
+ if (!(has_wildcard && max_level == codegen_->num_level()))
+ return std::make_pair(this, r);
+ }
+ }
+
+ return std::make_pair(this, Relation::True(num_level()));
+}
+
+Relation CG_leaf::hoistGuard() {
+ std::vector<Relation> guards;
+ for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) {
+ std::map<int, Relation>::iterator j = guards_.find(*i);
+ if (j == guards_.end()) {
+ Relation r = Relation::True(num_level());
+ r.copy_names(known_);
+ r.setup_names();
+ return r;
+ } else {
+ guards.push_back(j->second);
+ }
+ }
+
+ return SimpleHull(guards, true, true);
+}
+
+void CG_leaf::removeGuard(const Relation &guard) {
+ known_ = Intersection(known_, copy(guard));
+ known_.simplify();
+
+ std::map<int, Relation>::iterator i = guards_.begin();
+ while (i != guards_.end()) {
+ i->second = Gist(i->second, copy(known_), 1);
+ if (i->second.is_obvious_tautology())
+ guards_.erase(i++);
+ else
+ ++i;
+ }
+}
+
+CG_outputRepr *CG_leaf::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 {
+ return leaf_print_repr(active_, guards_, NULL, known_, indent, ocg,
+ codegen_->remap_, codegen_->xforms_, stmts, assigned_on_the_fly);
+}
+
+CG_result *CG_leaf::clone() const {
+ return new CG_leaf(codegen_, active_);
+}
+
+void CG_leaf::dump(int indent) const {
+ std::string prefix;
+ for (int i = 0; i < indent; i++)
+ prefix += " ";
+ std::cout << prefix << "LEAF: " << active_ << std::endl;
+ std::cout << prefix << "known: ";
+ const_cast<CG_leaf *>(this)->known_.print();
+ for (std::map<int, Relation>::const_iterator i = guards_.begin();
+ i != guards_.end(); i++) {
+ std::cout << prefix << "guard #" << i->first << ":";
+ const_cast<Relation &>(i->second).print();
+ }
+}
+
+}
diff --git a/lib/codegen/src/CG_stringBuilder.cc b/lib/codegen/src/CG_stringBuilder.cc
new file mode 100644
index 0000000..2f9286f
--- /dev/null
+++ b/lib/codegen/src/CG_stringBuilder.cc
@@ -0,0 +1,487 @@
+/*****************************************************************************
+ Copyright (C) 1994-2000 the Omega Project Team
+ Copyright (C) 2005-2011 Chun Chen
+ All Rights Reserved.
+
+ Purpose:
+ generate pseudo string code
+
+ Notes:
+ There is no need to check illegal NULL parameter and throw invalid_argument
+ in other IR interface implementation. They are for debugging purpose.
+ intMod implements modular function that returns positve remainder no matter
+ lop is postive or nagative and rop is guranteed to be positive here.
+
+ History:
+ 04/17/96 - Lei Zhou - created
+ 08/31/09 add parenthesis to string operands, Chun Chen
+*****************************************************************************/
+
+#include <code_gen/CG_stringBuilder.h>
+#include <code_gen/codegen_error.h>
+#include <basic/util.h>
+#include <string>
+#include <stdexcept>
+#include <ctype.h>
+#include <string.h>
+
+namespace {
+
+std::string SafeguardString(const std::string &s, char op) {
+ int len = s.length();
+ int paren_level = 0;
+ int num_plusminus = 0;
+ int num_mul = 0;
+ int num_div = 0;
+ for (int i = 0; i < len; i++)
+ switch (s[i]) {
+ case '(':
+ paren_level++;
+ break;
+ case ')':
+ paren_level--;
+ break;
+ case '+':
+ case '-':
+ if (paren_level == 0)
+ num_plusminus++;
+ break;
+ case '*':
+ if (paren_level == 0)
+ num_mul++;
+ break;
+ case '/':
+ if (paren_level == 0)
+ num_div++;
+ break;
+ default:
+ break;
+ }
+
+ bool need_paren = false;
+ switch (op) {
+ case '-':
+ if (num_plusminus > 0)
+ need_paren = true;
+ break;
+ case '*':
+ if (num_plusminus > 0 || num_div > 0)
+ need_paren = true;
+ break;
+ case '/':
+ if (num_plusminus > 0 || num_div > 0 || num_mul > 0)
+ need_paren = true;
+ break;
+ default:
+ break;
+ }
+
+ if (need_paren)
+ return "(" + s + ")";
+ else
+ return s;
+}
+
+
+std::string GetIndentSpaces(int indent) {
+ std::string indentStr;
+ for (int i = 1; i < indent; i++) {
+ indentStr += " ";
+ }
+ return indentStr;
+}
+
+
+// A shortcut to extract the string enclosed in the CG_outputRepr and delete
+// the original holder.
+std::string GetString(omega::CG_outputRepr *repr) {
+ std::string result = static_cast<omega::CG_stringRepr *>(repr)->GetString();
+ delete repr;
+ return result;
+}
+
+}
+
+
+namespace omega {
+
+
+
+//-----------------------------------------------------------------------------
+// Class: CG_stringBuilder
+//-----------------------------------------------------------------------------
+
+CG_stringRepr *CG_stringBuilder::CreateSubstitutedStmt(int indent, CG_outputRepr *stmt,
+ const std::vector<std::string> &vars,
+ std::vector<CG_outputRepr *> &subs) const {
+ std::string listStr = "";
+
+ for (int i = 0; i < subs.size(); i++) {
+ if (subs[i] == NULL)
+ listStr += "N/A";
+ else
+ listStr += GetString(subs[i]);
+ if (i < subs.size() - 1)
+ listStr += ",";
+ }
+
+ std::string stmtName = GetString(stmt);
+ std::string indentStr = GetIndentSpaces(indent);
+
+ return new CG_stringRepr(indentStr + stmtName + "(" + listStr + ");\n");
+}
+
+CG_stringRepr *CG_stringBuilder::CreateAssignment(int indent,
+ CG_outputRepr *lhs,
+ CG_outputRepr *rhs) const {
+ if (lhs == NULL || rhs == NULL)
+ throw std::invalid_argument("missing lhs or rhs in assignment");
+
+ std::string lhsStr = GetString(lhs);
+ std::string rhsStr = GetString(rhs);
+
+ std::string indentStr = GetIndentSpaces(indent);
+
+ return new CG_stringRepr(indentStr + lhsStr + "=" + rhsStr + ";\n");
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateInvoke(const std::string &funcName,
+ std::vector<CG_outputRepr *> &list) const {
+ std::string listStr = "";
+
+ for (int i = 0; i < list.size(); i++) {
+ listStr += GetString(list[i]);
+ if ( i < list.size()-1)
+ listStr += ",";
+ }
+
+ return new CG_stringRepr(funcName + "(" + listStr + ")");
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateComment(int indent, const std::string &commentText) const {
+ if (commentText == std::string("")) {
+ return NULL;
+ }
+
+ std::string indentStr = GetIndentSpaces(indent);
+
+ return new CG_stringRepr(indentStr + "// " + commentText + "\n");
+}
+
+CG_stringRepr* CG_stringBuilder::CreateAttribute(CG_outputRepr *control,
+ const std::string &commentText) const {
+ if (commentText == std::string("")) {
+ return static_cast<CG_stringRepr *> (control);
+ }
+
+ std::string controlString = GetString(control);
+
+ return new CG_stringRepr("// " + commentText + "\n" + controlString);
+
+}
+
+CG_outputRepr* CG_stringBuilder::CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const {
+ // -- Not Implemented
+ return scopeStmt;
+}
+
+CG_outputRepr* CG_stringBuilder::CreatePrefetchAttribute(CG_outputRepr* scopeStmt, int looplevel, const std::string& arrName, int hint) const {
+ // -- Not Implemented
+ return scopeStmt;
+}
+
+CG_stringRepr *CG_stringBuilder::CreateIf(int indent, CG_outputRepr *guardList,
+ CG_outputRepr *true_stmtList, CG_outputRepr *false_stmtList) const {
+ if (guardList == NULL)
+ throw std::invalid_argument("missing if condition");
+
+ if (true_stmtList == NULL && false_stmtList == NULL) {
+ delete guardList;
+ return NULL;
+ }
+
+ std::string guardListStr = GetString(guardList);
+ std::string indentStr = GetIndentSpaces(indent);
+ std::string s;
+ if (true_stmtList != NULL && false_stmtList == NULL) {
+ s = indentStr + "if (" + guardListStr + ") {\n"
+ + GetString(true_stmtList)
+ + indentStr + "}\n";
+ }
+ else if (true_stmtList == NULL && false_stmtList != NULL) {
+ s = indentStr + "if !(" + guardListStr + ") {\n"
+ + GetString(false_stmtList)
+ + indentStr + "}\n";
+ }
+ else {
+ s = indentStr + "if (" + guardListStr + ") {\n"
+ + GetString(true_stmtList)
+ + indentStr + "}\n"
+ + indentStr + "else {\n"
+ + GetString(false_stmtList)
+ + indentStr + "}\n";
+ }
+
+ return new CG_stringRepr(s);
+}
+
+
+
+CG_stringRepr *CG_stringBuilder::CreateInductive(CG_outputRepr *index,
+ CG_outputRepr *lower, CG_outputRepr *upper,
+ CG_outputRepr *step) const {
+ if (index == NULL)
+ throw std::invalid_argument("missing loop index");
+ if (lower == NULL)
+ throw std::invalid_argument("missing loop lower bound");
+ if (upper == NULL)
+ throw std::invalid_argument("missing loop upper bound");
+ if (step == NULL)
+ throw std::invalid_argument("missing loop step size");
+
+ std::string indexStr = GetString(index);
+ std::string lowerStr = GetString(lower);
+ std::string upperStr = GetString(upper);
+
+ std::string doStr = "for(" + indexStr + " = " + lowerStr + "; "
+ + indexStr + " <= " + upperStr + "; "
+ + indexStr;
+
+ std::string stepStr = GetString(step);
+ if (stepStr == to_string(1))
+ doStr += "++";
+ else
+ doStr += " += " + stepStr;
+
+ doStr += ")";
+
+ return new CG_stringRepr(doStr);
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateLoop(int indent, CG_outputRepr *control,
+ CG_outputRepr *stmtList) const {
+ if (stmtList == NULL) {
+ delete control;
+ return NULL;
+ }
+ else if (control == NULL)
+ return static_cast<CG_stringRepr *>(stmtList);
+
+ std::string ctrlStr = GetString(control);
+ std::string stmtStr = GetString(stmtList);
+
+ std::string indentStr = GetIndentSpaces(indent);
+
+ std::string s = indentStr + ctrlStr + " {\n"
+ + stmtStr
+ + indentStr + "}\n";
+
+ return new CG_stringRepr(s);
+}
+
+
+
+CG_stringRepr *CG_stringBuilder::CreateInt(int num) const {
+ std::string s = to_string(num);
+ return new CG_stringRepr(s);
+}
+
+
+
+bool CG_stringBuilder::isInteger(CG_outputRepr *op) const {
+
+ char * cstr;
+ std::string s = GetString(op);
+ cstr = new char [s.size()+1];
+ strcpy (cstr, s.c_str());
+ int count = 0;
+ while(cstr[count] != '\n' && cstr[count] != '\0' )
+ if( !isdigit(cstr[count]))
+ return false;
+
+
+ return true;
+}
+
+
+
+CG_stringRepr *CG_stringBuilder::CreateIdent(const std::string &varName) const {
+ if (varName == std::string("")) {
+ return NULL;
+ }
+
+ return new CG_stringRepr(varName);
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL) {
+ return static_cast<CG_stringRepr *>(lop);
+ }
+ else if (lop == NULL) {
+ return static_cast<CG_stringRepr *>(rop);
+ }
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr(lopStr + "+" + ropStr);
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateMinus(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL) {
+ return static_cast<CG_stringRepr *>(lop);
+ }
+ else if (lop == NULL) {
+ std::string ropStr = GetString(rop);
+ return new CG_stringRepr("-" + SafeguardString(ropStr, '-'));
+ }
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr(lopStr + "-" + SafeguardString(ropStr, '-'));
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateTimes(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL || lop == NULL) {
+ delete rop;
+ delete lop;
+ return NULL;
+ }
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr(SafeguardString(lopStr, '*') + "*" + SafeguardString(ropStr, '*'));
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateDivide(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL)
+ throw codegen_error("integer division by zero");
+ else if (lop == NULL) {
+ delete rop;
+ return NULL;
+ }
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr(SafeguardString(lopStr, '/') + "/" + SafeguardString(ropStr, '/'));
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateIntegerFloor(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL)
+ throw codegen_error("integer division by zero");
+ else if (lop == NULL) {
+ delete rop;
+ return NULL;
+ }
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr("intFloor(" + lopStr + "," + ropStr + ")");
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateIntegerMod(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL)
+ throw codegen_error("integer modulo by zero");
+ else if (lop == NULL) {
+ delete rop;
+ return NULL;
+ }
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr("intMod(" + lopStr + "," + ropStr + ")");
+}
+
+CG_stringRepr *CG_stringBuilder::CreateIntegerCeil(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == 0)
+ throw codegen_error("integer ceiling by zero");
+ else if (lop == NULL) {
+ delete rop;
+ return NULL;
+ }
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr("intCeil(" + lopStr + "," + ropStr + ")");
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateAnd(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL)
+ return static_cast<CG_stringRepr *>(lop);
+ else if (lop == NULL)
+ return static_cast<CG_stringRepr *>(rop);
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr(lopStr + " && " + ropStr);
+}
+
+
+CG_stringRepr *CG_stringBuilder::CreateGE(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL || lop == NULL)
+ throw std::invalid_argument("missing operand in greater than equal comparison condition");
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr(lopStr + " >= " + ropStr);
+}
+
+
+
+CG_stringRepr *CG_stringBuilder::CreateLE(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL || lop == NULL)
+ throw std::invalid_argument("missing operand in less than equal comparison condition");
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr(lopStr + " <= " + ropStr);
+}
+
+
+
+CG_stringRepr *CG_stringBuilder::CreateEQ(CG_outputRepr *lop, CG_outputRepr *rop) const {
+ if (rop == NULL || lop == NULL)
+ throw std::invalid_argument("missing operand in equal comparison condition");
+
+ std::string lopStr = GetString(lop);
+ std::string ropStr = GetString(rop);
+
+ return new CG_stringRepr(lopStr + " == " + ropStr);
+}
+
+
+
+CG_stringRepr *CG_stringBuilder::StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const {
+ if (list2 == NULL) {
+ return static_cast<CG_stringRepr *>(list1);
+ }
+ else if (list1 == NULL) {
+ return static_cast<CG_stringRepr *>(list2);
+ }
+
+ std::string list1Str = GetString(list1);
+ std::string list2Str = GetString(list2);
+
+ return new CG_stringRepr(list1Str + list2Str);
+}
+
+}
diff --git a/lib/codegen/src/CG_utils.cc b/lib/codegen/src/CG_utils.cc
new file mode 100755
index 0000000..d3a5f71
--- /dev/null
+++ b/lib/codegen/src/CG_utils.cc
@@ -0,0 +1,1735 @@
+/*****************************************************************************
+ Copyright (C) 1994-2000 the Omega Project Team
+ Copyright (C) 2005-2011 Chun Chen
+ All Rights Reserved.
+
+ Purpose:
+ Utility functions for processing CG tree.
+
+ Notes:
+
+ History:
+ 07/19/07 when generating output variable substitutions for a mapping
+ relation, map it to each output to get correct equality, -chun
+ 07/29/10 when translating equality to assignment, generate appropriate
+ if-condition when necesssary, -chun
+*****************************************************************************/
+
+#include <typeinfo>
+#include <omega.h>
+#include <code_gen/CG.h>
+#include <code_gen/CG_utils.h>
+#include <code_gen/codegen_error.h>
+#include <math.h>
+#include <stack>
+
+namespace omega {
+
+int checkLoopLevel;
+int stmtForLoopCheck;
+int upperBoundForLevel;
+int lowerBoundForLevel;
+bool fillInBounds;
+
+//trick to static init checkLoopLevel to 0
+class JunkStaticInit{ public: JunkStaticInit(){ checkLoopLevel=0; fillInBounds=false;} };
+static JunkStaticInit junkInitInstance__;
+
+
+
+
+namespace {
+
+Relation find_best_guard(const Relation &R, const BoolSet<> &active, const std::map<int, Relation> &guards) {
+ std::pair<int, int> best_cost = std::make_pair(0, 0);
+ Relation best_cond = Relation::True(R.n_set());
+
+ Relation r = copy(R);
+ int max_iter_count = 2*(r.single_conjunct()->n_EQs()) + r.single_conjunct()->n_GEQs();
+ int iter_count = 0;
+ while (!r.is_obvious_tautology()) {
+ std::pair<int, int> cost = std::make_pair(0, 0);
+ Relation cond = pick_one_guard(r);
+ Relation complement_cond = Complement(copy(cond));
+ complement_cond.simplify();
+ for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) {
+ std::map<int, Relation>::const_iterator j = guards.find(*i);
+ if (j == guards.end())
+ continue;
+ if (Must_Be_Subset(copy(j->second), copy(cond)))
+ cost.first++;
+ else if (Must_Be_Subset(copy(j->second), copy(complement_cond)))
+ cost.second++;
+ }
+ if (cost > best_cost) {
+ best_cost = cost;
+ best_cond = copy(cond);
+ }
+ r = Gist(r, cond, 1);
+
+ if (iter_count > max_iter_count)
+ throw codegen_error("guard condition too complex to handle");
+
+ iter_count++;
+ }
+
+ return best_cond;
+}
+
+
+Relation find_best_guard(const Relation &R, const std::vector<CG_loop *> &loops, int start, int end) {
+ std::pair<int, int> best_cost = std::make_pair(0, 0);
+ Relation best_cond = Relation::True(R.n_set());
+
+ Relation r = copy(R);
+ int max_iter_count = 2*(r.single_conjunct()->n_EQs()) + r.single_conjunct()->n_GEQs();
+ int iter_count = 0;
+ while (!r.is_obvious_tautology()) {
+ std::pair<int, int> cost = std::make_pair(0, 0);
+ Relation cond = pick_one_guard(r);
+ int i = start;
+ for ( ; i < end; i++) {
+ if (Must_Be_Subset(copy(loops[i]->guard_), copy(cond)))
+ cost.first++;
+ else
+ break;
+ }
+ Relation complement_cond = Complement(copy(cond));
+ complement_cond.simplify();
+ for (int j = i; j < end; j++)
+ if (Must_Be_Subset(copy(loops[j]->guard_), copy(complement_cond)))
+ cost.second++;
+ else
+ break;
+
+ if (cost > best_cost) {
+ best_cost = cost;
+ best_cond = copy(cond);
+ }
+ r = Gist(r, cond, 1);
+
+ if (iter_count > max_iter_count)
+ throw codegen_error("guard condition too complex to handle");
+
+ iter_count++;
+ }
+
+ return best_cond;
+}
+
+}
+
+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) {
+ assert(inequality.get_coef(v) != 0 && abs(stride_eq.get_coef(v)) == 1 && wc->kind() == Wildcard_Var && abs(stride_eq.get_coef(wc)) > 1);
+
+ // if bound expression uses floor operation, bail out for now
+ // TODO: in the future, handle this
+ if (abs(inequality.get_coef(v)) != 1)
+ return false;
+
+ coef_t stride = abs(stride_eq.get_coef(wc));
+
+ Relation r1(known.n_set());
+ F_Exists *f_exists1 = r1.add_and()->add_exists();
+ F_And *f_root1 = f_exists1->add_and();
+ std::map<Variable_ID, Variable_ID> exists_mapping1;
+ EQ_Handle h1 = f_root1->add_EQ();
+ Relation r2(known.n_set());
+ F_Exists *f_exists2 = r2.add_and()->add_exists();
+ F_And *f_root2 = f_exists2->add_and();
+ std::map<Variable_ID, Variable_ID> exists_mapping2;
+ EQ_Handle h2 = f_root2->add_EQ();
+ for (Constr_Vars_Iter cvi(inequality); cvi; cvi++) {
+ Variable_ID v = cvi.curr_var();
+ switch (v->kind()) {
+ case Input_Var:
+ h1.update_coef(r1.input_var(v->get_position()), cvi.curr_coef());
+ h2.update_coef(r2.input_var(v->get_position()), cvi.curr_coef());
+ break;
+ case Global_Var: {
+ Global_Var_ID g = v->get_global_var();
+ Variable_ID v1, v2;
+ if (g->arity() == 0) {
+ v1 = r1.get_local(g);
+ v2 = r2.get_local(g);
+ }
+ else {
+ v1 = r1.get_local(g, v->function_of());
+ v2 = r2.get_local(g, v->function_of());
+ }
+ h1.update_coef(v1, cvi.curr_coef());
+ h2.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ case Wildcard_Var: {
+ Variable_ID v1 = replicate_floor_definition(bounds, v, r1, f_exists1, f_root1, exists_mapping1);
+ Variable_ID v2 = replicate_floor_definition(bounds, v, r2, f_exists2, f_root2, exists_mapping2);
+ h1.update_coef(v1, cvi.curr_coef());
+ h2.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(false);
+ }
+ }
+ h1.update_const(inequality.get_const());
+ h1.update_coef(f_exists1->declare(), stride);
+ h2.update_const(inequality.get_const());
+ r1.simplify();
+ r2.simplify();
+
+ Relation all_known = Intersection(copy(bounds), copy(known));
+ all_known.simplify();
+
+ if (Gist(r1, copy(all_known), 1).is_obvious_tautology()) {
+ Relation r3(known.n_set());
+ F_Exists *f_exists3 = r3.add_and()->add_exists();
+ F_And *f_root3 = f_exists3->add_and();
+ std::map<Variable_ID, Variable_ID> exists_mapping3;
+ EQ_Handle h3 = f_root3->add_EQ();
+ for (Constr_Vars_Iter cvi(stride_eq); cvi; cvi++) {
+ Variable_ID v= cvi.curr_var();
+ switch (v->kind()) {
+ case Input_Var:
+ h3.update_coef(r3.input_var(v->get_position()), cvi.curr_coef());
+ break;
+ case Global_Var: {
+ Global_Var_ID g = v->get_global_var();
+ Variable_ID v3;
+ if (g->arity() == 0)
+ v3 = r3.get_local(g);
+ else
+ v3 = r3.get_local(g, v->function_of());
+ h3.update_coef(v3, cvi.curr_coef());
+ break;
+ }
+ case Wildcard_Var:
+ if (v == wc)
+ h3.update_coef(f_exists3->declare(), cvi.curr_coef());
+ else {
+ Variable_ID v3 = replicate_floor_definition(bounds, v, r3, f_exists3, f_root3, exists_mapping3);
+ h3.update_coef(v3, cvi.curr_coef());
+ }
+ break;
+ default:
+ assert(false);
+ }
+ }
+ h3.update_const(stride_eq.get_const());
+ r3.simplify();
+
+ if (Gist(r3, Intersection(r2, all_known), 1).is_obvious_tautology())
+ return true;
+ else
+ return false;
+ }
+ else
+ return false;
+}
+
+
+//
+// output variable by its name, however if this variable need to be substituted,
+// return the substitution.
+//
+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) {
+ const_cast<Relation &>(R).setup_names(); // hack
+
+ if (v->kind() == Input_Var) {
+ int pos = v->get_position();
+ if (assigned_on_the_fly[pos-1].first != NULL)
+ return assigned_on_the_fly[pos-1].first->clone();
+ else
+ return ocg->CreateIdent(v->name());
+ }
+ else if (v->kind() == Global_Var) {
+ if (v->get_global_var()->arity() == 0)
+ return ocg->CreateIdent(v->name());
+ else {
+ /* This should be improved to take into account the possible elimination
+ of the set variables. */
+ int arity = v->get_global_var()->arity();
+ std::vector<CG_outputRepr *> argList;
+ for(int i = 1; i <= arity; i++)
+ argList.push_back(ocg->CreateIdent(const_cast<Relation &>(R).input_var(i)->name()));
+ CG_outputRepr *call = ocg->CreateInvoke(v->get_global_var()->base_name(), argList);
+ return call;
+ }
+ }
+ else
+ assert(false);
+}
+
+
+//
+// return pair<if condition, <assignment rhs, assignment cost> >
+//
+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) {
+ Variable_ID v = const_cast<Relation &>(R).set_var(level);
+ Conjunct *c = const_cast<Relation &>(R).single_conjunct();
+
+ std::pair<EQ_Handle, int> result = find_simplest_assignment(R, v, assigned_on_the_fly);
+
+ if (result.second == INT_MAX)
+ return std::make_pair(static_cast<CG_outputRepr *>(NULL), std::make_pair(static_cast<CG_outputRepr *>(NULL), INT_MAX));
+
+ CG_outputRepr *if_repr = NULL;
+ CG_outputRepr *assign_repr = NULL;
+ // check whether to generate if-conditions from equality constraints
+ if (abs(result.first.get_coef(v)) != 1) {
+ Relation r(R.n_set());
+ F_Exists *f_exists = r.add_and()->add_exists();
+ F_And *f_root = f_exists->add_and();
+ std::map<Variable_ID, Variable_ID> exists_mapping;
+ exists_mapping[v] = f_exists->declare();
+
+ EQ_Handle h = f_root->add_EQ();
+ for (Constr_Vars_Iter cvi(result.first); cvi; cvi++)
+ switch (cvi.curr_var()->kind()) {
+ case Input_Var: {
+ if (cvi.curr_var() == v)
+ h.update_coef(exists_mapping[v], cvi.curr_coef());
+ else
+ h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef());
+ break;
+ }
+ case Global_Var: {
+ Global_Var_ID g = cvi.curr_var()->get_global_var();
+ Variable_ID v2;
+ if (g->arity() == 0)
+ v2 = r.get_local(g);
+ else
+ v2 = r.get_local(g, cvi.curr_var()->function_of());
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ case Wildcard_Var: {
+ std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var());
+ Variable_ID v2;
+ if (p == exists_mapping.end()) {
+ v2 = f_exists->declare();
+ exists_mapping[cvi.curr_var()] = v2;
+ }
+ else
+ v2 = p->second;
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(0);
+ }
+ h.update_const(result.first.get_const());
+
+ for (EQ_Iterator e(c->EQs()); e; e++)
+ if (!((*e) == result.first)) {
+ EQ_Handle h = f_root->add_EQ();
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ switch (cvi.curr_var()->kind()) {
+ case Input_Var: {
+ assert(cvi.curr_var() != v);
+ h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef());
+ break;
+ }
+ case Global_Var: {
+ Global_Var_ID g = cvi.curr_var()->get_global_var();
+ Variable_ID v2;
+ if (g->arity() == 0)
+ v2 = r.get_local(g);
+ else
+ v2 = r.get_local(g, cvi.curr_var()->function_of());
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ case Wildcard_Var: {
+ std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var());
+ Variable_ID v2;
+ if (p == exists_mapping.end()) {
+ v2 = f_exists->declare();
+ exists_mapping[cvi.curr_var()] = v2;
+ }
+ else
+ v2 = p->second;
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(0);
+ }
+ h.update_const((*e).get_const());
+ }
+
+ for (GEQ_Iterator e(c->GEQs()); e; e++) {
+ GEQ_Handle h = f_root->add_GEQ();
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ switch (cvi.curr_var()->kind()) {
+ case Input_Var: {
+ h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef());
+ break;
+ }
+ case Global_Var: {
+ Global_Var_ID g = cvi.curr_var()->get_global_var();
+ Variable_ID v2;
+ if (g->arity() == 0)
+ v2 = r.get_local(g);
+ else
+ v2 = r.get_local(g, cvi.curr_var()->function_of());
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ case Wildcard_Var: {
+ std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var());
+ Variable_ID v2;
+ if (p == exists_mapping.end()) {
+ v2 = f_exists->declare();
+ exists_mapping[cvi.curr_var()] = v2;
+ }
+ else
+ v2 = p->second;
+ h.update_coef(v2, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(0);
+ }
+ h.update_const((*e).get_const());
+ }
+
+ r.simplify();
+ if (!Gist(r, copy(known), 1).is_obvious_tautology()) {
+ CG_outputRepr *lhs = output_substitution_repr(ocg, result.first, v, false, R, assigned_on_the_fly);
+ if_repr = ocg->CreateEQ(ocg->CreateIntegerMod(lhs->clone(), ocg->CreateInt(abs(result.first.get_coef(v)))), ocg->CreateInt(0));
+ assign_repr = ocg->CreateDivide(lhs, ocg->CreateInt(abs(result.first.get_coef(v))));
+ }
+ else
+ assign_repr = output_substitution_repr(ocg, result.first, v, true, R, assigned_on_the_fly);
+ }
+ else
+ assign_repr = output_substitution_repr(ocg, result.first, v, true, R, assigned_on_the_fly);
+
+ if (assign_repr == NULL)
+ assign_repr = ocg->CreateInt(0);
+
+ return std::make_pair(if_repr, std::make_pair(assign_repr, result.second));
+}
+
+
+//
+// return NULL if 0
+//
+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) {
+ const_cast<Relation &>(R).setup_names(); // hack
+
+ coef_t a = equality.get_coef(v);
+ assert(a != 0);
+
+ CG_outputRepr *repr = NULL;
+ for (Constr_Vars_Iter cvi(equality); cvi; cvi++)
+ if (cvi.curr_var() != v) {
+ CG_outputRepr *t;
+ if (cvi.curr_var()->kind() == Wildcard_Var) {
+ std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var());
+ if (!result.first) {
+ delete repr;
+ throw codegen_error("can't output non floor defined wildcard");
+ }
+ t = output_inequality_repr(ocg, result.second, cvi.curr_var(), R, assigned_on_the_fly);
+ }
+ else
+ t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly);
+ coef_t coef = cvi.curr_coef();
+
+ if (a > 0) {
+ if (coef > 0) {
+ if (coef == 1)
+ repr = ocg->CreateMinus(repr, t);
+ else
+ repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ repr = ocg->CreatePlus(repr, t);
+ else
+ repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t));
+ }
+ }
+ else {
+ if (coef > 0) {
+ if (coef == 1)
+ repr = ocg->CreatePlus(repr, t);
+ else
+ repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ repr = ocg->CreateMinus(repr, t);
+ else
+ repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t));
+ }
+ }
+ }
+
+ int c = equality.get_const();
+ if (a > 0) {
+ if (c > 0)
+ repr = ocg->CreateMinus(repr, ocg->CreateInt(c));
+ else if (c < 0)
+ repr = ocg->CreatePlus(repr, ocg->CreateInt(-c));
+ }
+ else {
+ if (c > 0)
+ repr = ocg->CreatePlus(repr, ocg->CreateInt(c));
+ else if (c < 0)
+ repr = ocg->CreateMinus(repr, ocg->CreateInt(-c));
+ }
+
+ if (apply_v_coef && abs(a) != 1)
+ repr = ocg->CreateDivide(repr, ocg->CreateInt(abs(a)));
+
+ return repr;
+}
+
+
+//
+// original Substitutions class from omega can't handle integer
+// division, this is new way.
+//
+std::vector<CG_outputRepr*> output_substitutions(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) {
+ std::vector<CG_outputRepr *> subs;
+
+ for (int i = 1; i <= R.n_out(); i++) {
+ Relation mapping(R.n_out(), 1);
+ F_And *f_root = mapping.add_and();
+ EQ_Handle h = f_root->add_EQ();
+ h.update_coef(mapping.output_var(1), 1);
+ h.update_coef(mapping.input_var(i), -1);
+ Relation r = Composition(mapping, copy(R));
+ r.simplify();
+
+ Variable_ID v = r.output_var(1);
+ CG_outputRepr *repr = NULL;
+ std::pair<EQ_Handle, int> result = find_simplest_assignment(r, v, assigned_on_the_fly);
+ if (result.second < INT_MAX)
+ repr = output_substitution_repr(ocg, result.first, v, true, r, assigned_on_the_fly);
+ else {
+ std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v);
+ if (result.first)
+ try {
+ repr = output_inequality_repr(ocg, result.second, v, R, assigned_on_the_fly);
+ }
+ catch (const codegen_error &) {
+ }
+ }
+
+ subs.push_back(repr);
+ }
+
+ return subs;
+}
+
+
+//
+// handle floor definition wildcards in equality, the second in returned pair
+// is the cost.
+//
+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) {
+ Conjunct *c = const_cast<Relation &>(R).single_conjunct();
+
+ int min_cost = INT_MAX;
+ EQ_Handle eq;
+ for (EQ_Iterator e(c->EQs()); e; e++)
+ if (!(*e).has_wildcards() && (*e).get_coef(v) != 0) {
+ int cost = 0;
+
+ if (abs((*e).get_coef(v)) != 1)
+ cost += 4; // divide cost
+
+ int num_var = 0;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ if (cvi.curr_var() != v) {
+ num_var++;
+ if (abs(cvi.curr_coef()) != 1)
+ cost += 2; // multiply cost
+ if (cvi.curr_var()->kind() == Global_Var && cvi.curr_var()->get_global_var()->arity() > 0)
+ cost += 10; // function cost
+ else if (cvi.curr_var()->kind() == Input_Var &&
+ assigned_on_the_fly.size() >= cvi.curr_var()->get_position() &&
+ assigned_on_the_fly[cvi.curr_var()->get_position()-1].first != NULL)
+ cost += assigned_on_the_fly[cvi.curr_var()->get_position()-1].second; // substitution cost on record
+ }
+ if ((*e).get_const() != 0)
+ num_var++;
+ if (num_var > 1)
+ cost += num_var - 1; // addition cost
+
+ if (cost < min_cost) {
+ min_cost = cost;
+ eq = *e;
+ }
+ }
+
+ if (min_cost < INT_MAX)
+ return std::make_pair(eq, min_cost);
+
+ for (EQ_Iterator e(c->EQs()); e; e++)
+ if ((*e).has_wildcards() && (*e).get_coef(v) != 0) {
+ bool is_assignment = true;
+ for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) {
+ std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v);
+ if (!result.first) {
+ is_assignment = false;
+ break;
+ }
+ }
+ if (!is_assignment)
+ continue;
+
+ int cost = 0;
+
+ if (abs((*e).get_coef(v)) != 1)
+ cost += 4; // divide cost
+
+ int num_var = 0;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ if (cvi.curr_var() != v) {
+ num_var++;
+ if (abs(cvi.curr_coef()) != 1)
+ cost += 2; // multiply cost
+ if (cvi.curr_var()->kind() == Wildcard_Var)
+ cost += 10; // floor operation cost
+ else if (cvi.curr_var()->kind() == Global_Var && cvi.curr_var()->get_global_var()->arity() > 0)
+ cost += 20; // function cost
+ else if (cvi.curr_var()->kind() == Input_Var &&
+ assigned_on_the_fly.size() >= cvi.curr_var()->get_position() &&
+ assigned_on_the_fly[cvi.curr_var()->get_position()-1].first != NULL)
+ cost += assigned_on_the_fly[cvi.curr_var()->get_position()-1].second; // substitution cost on record
+ }
+ if ((*e).get_const() != 0)
+ num_var++;
+ if (num_var > 1)
+ cost += num_var - 1; // addition cost
+
+ if (cost < min_cost) {
+ min_cost = cost;
+ eq = *e;
+ }
+ }
+
+ return std::make_pair(eq, min_cost);
+}
+
+
+//
+// find floor definition for variable v, e.g. m-c <= 4v <= m, (c is
+// constant and 0 <= c < 4). this translates to v = floor(m, 4) and
+// return 4v<=m in this case. All wildcards in such inequality are
+// also floor defined.
+//
+std::pair<bool, GEQ_Handle> find_floor_definition(const Relation &R, Variable_ID v, std::set<Variable_ID> excluded_floor_vars) {
+ Conjunct *c = const_cast<Relation &>(R).single_conjunct();
+
+ excluded_floor_vars.insert(v);
+ for (GEQ_Iterator e = c->GEQs(); e; e++) {
+ coef_t a = (*e).get_coef(v);
+ if (a >= -1)
+ continue;
+ a = -a;
+
+ bool interested = true;
+ for (std::set<Variable_ID>::const_iterator i = excluded_floor_vars.begin(); i != excluded_floor_vars.end(); i++)
+ if ((*i) != v && (*e).get_coef(*i) != 0) {
+ interested = false;
+ break;
+ }
+ if (!interested)
+ continue;
+
+ // check if any wildcard is floor defined
+ bool has_undefined_wc = false;
+ for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++)
+ if (excluded_floor_vars.find(cvi.curr_var()) == excluded_floor_vars.end()) {
+ std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var(), excluded_floor_vars);
+ if (!result.first) {
+ has_undefined_wc = true;
+ break;
+ }
+ }
+ if (has_undefined_wc)
+ continue;
+
+ // find the matching upper bound for floor definition
+ for (GEQ_Iterator e2 = c->GEQs(); e2; e2++)
+ if ((*e2).get_coef(v) == a && (*e).get_const() + (*e2).get_const() < a) {
+ bool match = true;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ if ((*e2).get_coef(cvi.curr_var()) != -cvi.curr_coef()) {
+ match = false;
+ break;
+ }
+ if (!match)
+ continue;
+ for (Constr_Vars_Iter cvi(*e2); cvi; cvi++)
+ if ((*e).get_coef(cvi.curr_var()) != -cvi.curr_coef()) {
+ match = false;
+ break;
+ }
+ if (match)
+ return std::make_pair(true, *e);
+ }
+ }
+
+ return std::make_pair(false, GEQ_Handle());
+}
+
+//
+// find the stride involving the specified variable, the stride
+// equality can have other wildcards as long as they are defined as
+// floor variables.
+//
+std::pair<EQ_Handle, Variable_ID> find_simplest_stride(const Relation &R, Variable_ID v) {
+ int best_num_var = INT_MAX;
+ coef_t best_coef;
+ EQ_Handle best_eq;
+ Variable_ID best_stride_wc;
+ for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++)
+ if ((*e).has_wildcards() && (*e).get_coef(v) != 0) {
+ bool is_stride = true;
+ bool found_free = false;
+ int num_var = 0;
+ int num_floor = 0;
+ Variable_ID stride_wc;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++) {
+ switch (cvi.curr_var()->kind()) {
+ case Wildcard_Var: {
+ bool is_free = true;
+ for (GEQ_Iterator e2(const_cast<Relation &>(R).single_conjunct()->GEQs()); e2; e2++)
+ if ((*e2).get_coef(cvi.curr_var()) != 0) {
+ is_free = false;
+ break;
+ }
+ if (is_free) {
+ if (found_free)
+ is_stride = false;
+ else {
+ found_free = true;
+ stride_wc = cvi.curr_var();
+ }
+ }
+ else {
+ std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var());
+ if (result.first)
+ num_floor++;
+ else
+ is_stride = false;
+ }
+ break;
+ }
+ case Input_Var:
+ num_var++;
+ break;
+ default:
+ ;
+ }
+
+ if (!is_stride)
+ break;
+ }
+
+ if (is_stride) {
+ coef_t coef = abs((*e).get_coef(v));
+ if (best_num_var == INT_MAX || coef < best_coef ||
+ (coef == best_coef && num_var < best_num_var)) {
+ best_coef = coef;
+ best_num_var = num_var;
+ best_eq = *e;
+ best_stride_wc = stride_wc;
+ }
+ }
+ }
+
+ if (best_num_var != INT_MAX)
+ return std::make_pair(best_eq, best_stride_wc);
+ else
+ return std::make_pair(EQ_Handle(), static_cast<Variable_ID>(NULL));
+}
+
+//
+// convert relation to if-condition
+//
+CG_outputRepr *output_guard(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) {
+ assert(R.n_out()==0);
+
+ CG_outputRepr *result = NULL;
+ Conjunct *c = const_cast<Relation &>(R).single_conjunct();
+
+ // e.g. 4i=5*j
+ for (EQ_Iterator e = c->EQs(); e; e++)
+ if (!(*e).has_wildcards()) {
+ CG_outputRepr *lhs = NULL;
+ CG_outputRepr *rhs = NULL;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++) {
+ CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly);
+ coef_t coef = cvi.curr_coef();
+ if (coef > 0) {
+ if (coef == 1)
+ lhs = ocg->CreatePlus(lhs, v);
+ else
+ lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ rhs = ocg->CreatePlus(rhs, v);
+ else
+ rhs = ocg->CreatePlus(rhs, ocg->CreateTimes(ocg->CreateInt(-coef), v));
+ }
+ }
+ coef_t c = (*e).get_const();
+
+ CG_outputRepr *term;
+ if (lhs == NULL)
+ term = ocg->CreateEQ(rhs, ocg->CreateInt(c));
+ else {
+ if (c > 0)
+ rhs = ocg->CreateMinus(rhs, ocg->CreateInt(c));
+ else if (c < 0)
+ rhs = ocg->CreatePlus(rhs, ocg->CreateInt(-c));
+ else if (rhs == NULL)
+ rhs = ocg->CreateInt(0);
+ term = ocg->CreateEQ(lhs, rhs);
+ }
+ result = ocg->CreateAnd(result, term);
+ }
+
+ // e.g. i>5j
+ for (GEQ_Iterator e = c->GEQs(); e; e++)
+ if (!(*e).has_wildcards()) {
+ CG_outputRepr *lhs = NULL;
+ CG_outputRepr *rhs = NULL;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++) {
+ CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly);
+ coef_t coef = cvi.curr_coef();
+ if (coef > 0) {
+ if (coef == 1)
+ lhs = ocg->CreatePlus(lhs, v);
+ else
+ lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ rhs = ocg->CreatePlus(rhs, v);
+ else
+ rhs = ocg->CreatePlus(rhs, ocg->CreateTimes(ocg->CreateInt(-coef), v));
+ }
+ }
+ coef_t c = (*e).get_const();
+
+ CG_outputRepr *term;
+ if (lhs == NULL)
+ term = ocg->CreateLE(rhs, ocg->CreateInt(c));
+ else {
+ if (c > 0)
+ rhs = ocg->CreateMinus(rhs, ocg->CreateInt(c));
+ else if (c < 0)
+ rhs = ocg->CreatePlus(rhs, ocg->CreateInt(-c));
+ else if (rhs == NULL)
+ rhs = ocg->CreateInt(0);
+ term = ocg->CreateGE(lhs, rhs);
+ }
+ result = ocg->CreateAnd(result, term);
+ }
+
+ // e.g. 4i=5j+4alpha
+ for (EQ_Iterator e = c->EQs(); e; e++)
+ if ((*e).has_wildcards()) {
+ Variable_ID wc;
+ int num_wildcard = 0;
+ int num_positive = 0;
+ int num_negative = 0;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++) {
+ if (cvi.curr_var()->kind() == Wildcard_Var) {
+ num_wildcard++;
+ wc = cvi.curr_var();
+ }
+ else {
+ if (cvi.curr_coef() > 0)
+ num_positive++;
+ else
+ num_negative++;
+ }
+ }
+
+ if (num_wildcard > 1) {
+ delete result;
+ throw codegen_error("Can't generate equality condition with multiple wildcards");
+ }
+ int sign = (num_positive>=num_negative)?1:-1;
+
+ CG_outputRepr *lhs = NULL;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++) {
+ if (cvi.curr_var() != wc) {
+ CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly);
+ coef_t coef = cvi.curr_coef();
+ if (sign == 1) {
+ if (coef > 0) {
+ if (coef == 1)
+ lhs = ocg->CreatePlus(lhs, v);
+ else
+ lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ lhs = ocg->CreateMinus(lhs, v);
+ else
+ lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(-coef), v));
+ }
+ }
+ else {
+ if (coef > 0) {
+ if (coef == 1)
+ lhs = ocg->CreateMinus(lhs, v);
+ else
+ lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ lhs = ocg->CreatePlus(lhs, v);
+ else
+ lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(-coef), v));
+ }
+ }
+ }
+ }
+ coef_t c = (*e).get_const();
+ if (sign == 1) {
+ if (c > 0)
+ lhs = ocg->CreatePlus(lhs, ocg->CreateInt(c));
+ else if (c < 0)
+ lhs = ocg->CreateMinus(lhs, ocg->CreateInt(-c));
+ }
+ else {
+ if (c > 0)
+ lhs = ocg->CreateMinus(lhs, ocg->CreateInt(c));
+ else if (c < 0)
+ lhs = ocg->CreatePlus(lhs, ocg->CreateInt(-c));
+ }
+
+ lhs = ocg->CreateIntegerMod(lhs, ocg->CreateInt(abs((*e).get_coef(wc))));
+ CG_outputRepr *term = ocg->CreateEQ(lhs, ocg->CreateInt(0));
+ result = ocg->CreateAnd(result, term);
+ }
+
+ // e.g. 4alpha<=i<=5alpha
+ for (GEQ_Iterator e = c->GEQs(); e; e++)
+ if ((*e).has_wildcards()) {
+ Variable_ID wc;
+ int num_wildcard = 0;
+ for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++)
+ if (num_wildcard == 0) {
+ wc = cvi.curr_var();
+ num_wildcard = 1;
+ }
+ else
+ num_wildcard++;
+
+ if (num_wildcard > 1) {
+ delete result;
+ // e.g. c*alpha - x >= 0 (*)
+ // -d*alpha + y >= 0 (*)
+ // e1*alpha + f1*beta + g1 >= 0 (**)
+ // e2*alpha + f2*beta + g2 >= 0 (**)
+ // ...
+ // TODO: should generate a testing loop for alpha using its lower and
+ // upper bounds from (*) constraints and do the same if-condition test
+ // for beta from each pair of opposite (**) constraints as above,
+ // and exit the loop when if-condition satisfied.
+ throw codegen_error("Can't generate multiple wildcard GEQ guards right now");
+ }
+
+ coef_t c = (*e).get_coef(wc);
+ int sign = (c>0)?1:-1;
+
+ GEQ_Iterator e2 = e;
+ e2++;
+ for ( ; e2; e2++) {
+ coef_t c2 = (*e2).get_coef(wc);
+ if (c2 == 0)
+ continue;
+ int sign2 = (c2>0)?1:-1;
+ if (sign != -sign2)
+ continue;
+ int num_wildcard2 = 0;
+ for (Constr_Vars_Iter cvi(*e2, true); cvi; cvi++)
+ num_wildcard2++;
+ if (num_wildcard2 > 1)
+ continue;
+
+ GEQ_Handle lb, ub;
+ if (sign == 1) {
+ lb = (*e);
+ ub = (*e2);
+ }
+ else {
+ lb = (*e2);
+ ub = (*e);
+ }
+
+ CG_outputRepr *lhs = NULL;
+ for (Constr_Vars_Iter cvi(lb); cvi; cvi++)
+ if (cvi.curr_var() != wc) {
+ CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly);
+ coef_t coef = cvi.curr_coef();
+ if (coef > 0) {
+ if (coef == 1)
+ lhs = ocg->CreateMinus(lhs, v);
+ else
+ lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ lhs = ocg->CreatePlus(lhs, v);
+ else
+ lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(-coef), v));
+ }
+ }
+ coef_t c = lb.get_const();
+ if (c > 0)
+ lhs = ocg->CreateMinus(lhs, ocg->CreateInt(c));
+ else if (c < 0)
+ lhs = ocg->CreatePlus(lhs, ocg->CreateInt(-c));
+
+ CG_outputRepr *rhs = NULL;
+ for (Constr_Vars_Iter cvi(ub); cvi; cvi++)
+ if (cvi.curr_var() != wc) {
+ CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly);
+ coef_t coef = cvi.curr_coef();
+ if (coef > 0) {
+ if (coef == 1)
+ rhs = ocg->CreatePlus(rhs, v);
+ else
+ rhs = ocg->CreatePlus(rhs, ocg->CreateTimes(ocg->CreateInt(coef), v));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ rhs = ocg->CreateMinus(rhs, v);
+ else
+ rhs = ocg->CreateMinus(rhs, ocg->CreateTimes(ocg->CreateInt(-coef), v));
+ }
+ }
+ c = ub.get_const();
+ if (c > 0)
+ rhs = ocg->CreatePlus(rhs, ocg->CreateInt(c));
+ else if (c < 0)
+ rhs = ocg->CreateMinus(rhs, ocg->CreateInt(-c));
+
+ rhs = ocg->CreateIntegerFloor(rhs, ocg->CreateInt(-ub.get_coef(wc)));
+ rhs = ocg->CreateTimes(ocg->CreateInt(lb.get_coef(wc)), rhs);
+ CG_outputRepr *term = ocg->CreateLE(lhs, rhs);
+ result = ocg->CreateAnd(result, term);
+ }
+ }
+
+ return result;
+}
+
+
+//
+// return NULL if 0
+//
+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) {
+ const_cast<Relation &>(R).setup_names(); // hack
+
+ coef_t a = inequality.get_coef(v);
+ assert(a != 0);
+ excluded_floor_vars.insert(v);
+
+ CG_outputRepr *repr = NULL;
+ for (Constr_Vars_Iter cvi(inequality); cvi; cvi++)
+ if (cvi.curr_var() != v) {
+ CG_outputRepr *t;
+ if (cvi.curr_var()->kind() == Wildcard_Var) {
+ std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var(), excluded_floor_vars);
+ if (!result.first) {
+ delete repr;
+ throw codegen_error("Can't generate bound expression with wildcard not involved in floor definition");
+ }
+ try {
+ t = output_inequality_repr(ocg, result.second, cvi.curr_var(), R, assigned_on_the_fly, excluded_floor_vars);
+ }
+ catch (const std::exception &e) {
+ delete repr;
+ throw e;
+ }
+ }
+ else
+ t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly);
+
+ coef_t coef = cvi.curr_coef();
+ if (a > 0) {
+ if (coef > 0) {
+ if (coef == 1)
+ repr = ocg->CreateMinus(repr, t);
+ else
+ repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t));
+ }
+ else {
+ if (coef == -1)
+ repr = ocg->CreatePlus(repr, t);
+ else
+ repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t));
+ }
+ }
+ else {
+ if (coef > 0) {
+ if (coef == 1)
+ repr = ocg->CreatePlus(repr, t);
+ else
+ repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t));
+ }
+ else {
+ if (coef == -1)
+ repr = ocg->CreateMinus(repr, t);
+ else
+ repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t));
+ }
+ }
+ }
+ coef_t c = inequality.get_const();
+ if (c > 0) {
+ if (a > 0)
+ repr = ocg->CreateMinus(repr, ocg->CreateInt(c));
+ else
+ repr = ocg->CreatePlus(repr, ocg->CreateInt(c));
+ }
+ else if (c < 0) {
+ if (a > 0)
+ repr = ocg->CreatePlus(repr, ocg->CreateInt(-c));
+ else
+ repr = ocg->CreateMinus(repr, ocg->CreateInt(-c));
+ }
+
+ if (abs(a) == 1)
+ return repr;
+ else if (a > 0)
+ return ocg->CreateIntegerCeil(repr, ocg->CreateInt(a));
+ else // a < 0
+ return ocg->CreateIntegerFloor(repr, ocg->CreateInt(-a));
+}
+
+
+//
+// nothing special, just an alias
+//
+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) {
+ assert(inequality.get_coef(v) < 0);
+ CG_outputRepr* zero_;
+
+ zero_ = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly);
+
+ if(!zero_)
+ zero_ = ocg->CreateInt(0);
+
+ return zero_;
+
+}
+
+
+//
+// output lower bound with respect to lattice
+//
+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) {
+ assert(inequality.get_coef(v) > 0);
+ CG_outputRepr* zero_;
+ if (wc == NULL || bound_must_hit_stride(inequality, v, stride_eq, wc, R, known)){
+ zero_ = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly);
+ if(!zero_)
+ zero_ = ocg->CreateInt(0);
+
+ return zero_;
+ }
+ CG_outputRepr *strideBoundRepr = NULL;
+ int sign = (stride_eq.get_coef(v)>0)?1:-1;
+ for (Constr_Vars_Iter cvi(stride_eq); cvi; cvi++) {
+ Variable_ID v2 = cvi.curr_var();
+ if (v2 == v || v2 == wc)
+ continue;
+
+ CG_outputRepr *v_repr;
+ if (v2->kind() == Input_Var || v2->kind() == Global_Var)
+ v_repr = output_ident(ocg, R, v2, assigned_on_the_fly);
+ else if (v2->kind() == Wildcard_Var) {
+ std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v2);
+ assert(result.first);
+ v_repr = output_inequality_repr(ocg, result.second, v2, R, assigned_on_the_fly);
+ }
+
+ coef_t coef = cvi.curr_coef();
+ if (sign < 0) {
+ if (coef > 0) {
+ if (coef == 1)
+ strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr);
+ else
+ strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(coef), v_repr));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr);
+ else
+ strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(-coef), v_repr));
+ }
+ }
+ else {
+ if (coef > 0) {
+ if (coef == 1)
+ strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr);
+ else
+ strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(coef), v_repr));
+ }
+ else { // coef < 0
+ if (coef == -1)
+ strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr);
+ else
+ strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(-coef), v_repr));
+ }
+ }
+ }
+ coef_t c = stride_eq.get_const();
+ if (c > 0) {
+ if (sign < 0)
+ strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateInt(c));
+ else
+ strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateInt(c));
+ }
+ else if (c < 0) {
+ if (sign < 0)
+ strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateInt(-c));
+ else
+ strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateInt(-c));
+ }
+
+ CG_outputRepr *repr = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly);
+ CG_outputRepr *repr2 = ocg->CreateCopy(repr);
+ repr = ocg->CreatePlus(repr2, ocg->CreateIntegerMod(ocg->CreateMinus(strideBoundRepr, repr), ocg->CreateInt(abs(stride_eq.get_coef(wc)))));
+
+ return repr;
+}
+
+
+//
+// return loop control structure only
+//
+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) {
+ std::pair<EQ_Handle, Variable_ID> result = find_simplest_stride(R, const_cast<Relation &>(R).set_var(level));
+ if (result.second != NULL)
+ assert(abs(result.first.get_coef(const_cast<Relation &>(R).set_var(level))) == 1);
+
+ std::vector<CG_outputRepr *> lbList, ubList;
+ try {
+
+ coef_t const_lb = negInfinity, const_ub = posInfinity;
+
+ for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); e; e++) {
+ coef_t coef = (*e).get_coef(const_cast<Relation &>(R).set_var(level));
+
+ if (coef > 0) {
+ CG_outputRepr *repr = output_lower_bound_repr(ocg, *e, const_cast<Relation &>(R).set_var(level), result.first, result.second, R, known, assigned_on_the_fly);
+ if (repr == NULL)
+ repr = ocg->CreateInt(0);
+ lbList.push_back(repr);
+
+ if ((*e).is_const(const_cast<Relation &>(R).set_var(level))){
+ if(!result.second) {
+
+ //no variables but v in constr
+ coef_t L,m;
+ L = -((*e).get_const());
+
+ m = (*e).get_coef(const_cast<Relation &>(R).set_var(level));
+ coef_t sb = (int) (ceil(((float) L) /m));
+ set_max(const_lb, sb);
+ }
+ else{
+
+ coef_t L,m,s,c;
+ L = -((*e).get_const());
+ m = (*e).get_coef(const_cast<Relation &>(R).set_var(level));
+ s = abs(result.first.get_coef(result.second));
+ c = result.first.get_const();
+ coef_t sb = (s * (int) (ceil( (float) (L - (c * m)) /(s*m))))+ c;
+ set_max(const_lb, sb);
+
+ }
+ }
+
+ }
+ else if (coef < 0) {
+ CG_outputRepr *repr = output_upper_bound_repr(ocg, *e, const_cast<Relation &>(R).set_var(level), R, assigned_on_the_fly);
+ if (repr == NULL)
+ repr = ocg->CreateInt(0);
+ ubList.push_back(repr);
+
+ if ((*e).is_const(const_cast<Relation &>(R).set_var(level))) {
+ // no variables but v in constraint
+ set_min(const_ub,-(*e).get_const()/(*e).get_coef(const_cast<Relation &>(R).set_var(level)));
+ }
+
+ }
+ }
+
+ if(fillInBounds && lbList.size() == 1 && const_lb != negInfinity)
+ lowerBoundForLevel = const_lb;
+
+ if(fillInBounds && const_ub != posInfinity)
+ upperBoundForLevel = const_ub;
+ if (lbList.size() == 0)
+ throw codegen_error("missing lower bound at loop level " + to_string(level));
+ if (ubList.size() == 0)
+ throw codegen_error("missing upper bound at loop level " + to_string(level));
+ }
+ catch (const std::exception &e) {
+ for (int i = 0; i < lbList.size(); i++)
+ delete lbList[i];
+ for (int i = 0; i < ubList.size(); i++)
+ delete ubList[i];
+ throw e;
+ }
+
+ CG_outputRepr *lbRepr = NULL;
+ if (lbList.size() > 1)
+ lbRepr = ocg->CreateInvoke("max", lbList);
+ else // (lbList.size() == 1)
+ lbRepr = lbList[0];
+
+ CG_outputRepr *ubRepr = NULL;
+ if (ubList.size() > 1)
+ ubRepr = ocg->CreateInvoke("min", ubList);
+ else // (ubList.size() == 1)
+ ubRepr = ubList[0];
+
+ CG_outputRepr *stRepr;
+ if (result.second == NULL)
+ stRepr = ocg->CreateInt(1);
+ else
+ stRepr = ocg->CreateInt(abs(result.first.get_coef(result.second)));
+ CG_outputRepr *indexRepr = output_ident(ocg, R, const_cast<Relation &>(R).set_var(level), assigned_on_the_fly);
+ return ocg->CreateInductive(indexRepr, lbRepr, ubRepr, stRepr);
+}
+
+
+//
+// parameter f_root is inside f_exists, not the other way around.
+// return replicated variable in new relation, with all cascaded floor definitions
+// using wildcards defined in the same way as in the original relation.
+//
+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) {
+ assert(R.n_out() == 0 && r.n_out() == 0 && R.n_inp() == r.n_inp());
+
+ std::set<Variable_ID> excluded_floor_vars;
+ std::stack<Variable_ID> to_fill;
+ to_fill.push(floor_var);
+
+ while (!to_fill.empty()) {
+ Variable_ID v = to_fill.top();
+ to_fill.pop();
+ if (excluded_floor_vars.find(v) != excluded_floor_vars.end())
+ continue;
+
+ std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v, excluded_floor_vars);
+ assert(result.first);
+ excluded_floor_vars.insert(v);
+
+ GEQ_Handle h1 = f_root->add_GEQ();
+ GEQ_Handle h2 = f_root->add_GEQ();
+ for (Constr_Vars_Iter cvi(result.second); cvi; cvi++) {
+ Variable_ID v2 = cvi.curr_var();
+ switch (v2->kind()) {
+ case Input_Var: {
+ int pos = v2->get_position();
+ h1.update_coef(r.input_var(pos), cvi.curr_coef());
+ h2.update_coef(r.input_var(pos), -cvi.curr_coef());
+ break;
+ }
+ case Wildcard_Var: {
+ std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(v2);
+ Variable_ID v3;
+ if (p == exists_mapping.end()) {
+ v3 = f_exists->declare();
+ exists_mapping[v2] = v3;
+ }
+ else
+ v3 = p->second;
+ h1.update_coef(v3, cvi.curr_coef());
+ h2.update_coef(v3, -cvi.curr_coef());
+ if (v2 != v)
+ to_fill.push(v2);
+ break;
+ }
+ case Global_Var: {
+ Global_Var_ID g = v2->get_global_var();
+ Variable_ID v3;
+ if (g->arity() == 0)
+ v3 = r.get_local(g);
+ else
+ v3 = r.get_local(g, v2->function_of());
+ h1.update_coef(v3, cvi.curr_coef());
+ h2.update_coef(v3, -cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(false);
+ }
+ }
+ h1.update_const(result.second.get_const());
+ h2.update_const(-result.second.get_const()-result.second.get_coef(v)-1);
+ }
+
+ if (floor_var->kind() == Input_Var)
+ return r.input_var(floor_var->get_position());
+ else if (floor_var->kind() == Wildcard_Var)
+ return exists_mapping[floor_var];
+ else
+ assert(false);
+}
+
+
+//
+// pick one guard condition from relation. it can involve multiple
+// constraints when involving wildcards, as long as its complement
+// is a single conjunct.
+//
+Relation pick_one_guard(const Relation &R, int level) {
+ assert(R.n_out()==0);
+
+ Relation r = Relation::True(R.n_set());
+
+ for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); e; e++)
+ if (!(*e).has_wildcards()) {
+ r.and_with_GEQ(*e);
+ r.simplify();
+ r.copy_names(R);
+ r.setup_names();
+ return r;
+ }
+
+ for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++)
+ if (!(*e).has_wildcards()) {
+ r.and_with_GEQ(*e);
+ r.simplify();
+ r.copy_names(R);
+ r.setup_names();
+ return r;
+ }
+
+ for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++)
+ if ((*e).has_wildcards()) {
+ int num_wildcard = 0;
+ int max_level = 0;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ switch (cvi.curr_var()->kind()) {
+ case Wildcard_Var:
+ num_wildcard++;
+ break;
+ case Input_Var:
+ if (cvi.curr_var()->get_position() > max_level)
+ max_level = cvi.curr_var()->get_position();
+ break;
+ default:
+ ;
+ }
+
+ if (num_wildcard == 1 && max_level != level-1) {
+ r.and_with_EQ(*e);
+ r.simplify();
+ r.copy_names(R);
+ r.setup_names();
+ return r;
+ }
+ }
+
+ for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); e; e++)
+ if ((*e).has_wildcards()) {
+ int num_wildcard = 0;
+ int max_level = 0;
+ bool direction;
+ Variable_ID wc;
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++)
+ switch (cvi.curr_var()->kind()) {
+ case Wildcard_Var:
+ num_wildcard++;
+ wc = cvi.curr_var();
+ direction = cvi.curr_coef()>0?true:false;
+ break;
+ case Input_Var:
+ if (cvi.curr_var()->get_position() > max_level)
+ max_level = cvi.curr_var()->get_position();
+ break;
+ default:
+ ;
+ }
+
+ if (num_wildcard == 1 && max_level != level-1) {
+ // find the pairing inequality
+ GEQ_Iterator e2 = e;
+ e2++;
+ for ( ; e2; e2++) {
+ int num_wildcard2 = 0;
+ int max_level2 = 0;
+ bool direction2;
+ Variable_ID wc2;
+ for (Constr_Vars_Iter cvi(*e2); cvi; cvi++)
+ switch (cvi.curr_var()->kind()) {
+ case Wildcard_Var:
+ num_wildcard2++;
+ wc2 = cvi.curr_var();
+ direction2 = cvi.curr_coef()>0?true:false;
+ break;
+ case Input_Var:
+ if (cvi.curr_var()->get_position() > max_level2)
+ max_level2 = cvi.curr_var()->get_position();
+ break;
+ default:
+ ;
+ }
+
+ if (num_wildcard2 == 1 && max_level2 != level-1 && wc2 == wc && direction2 == not direction) {
+ F_Exists *f_exists = r.and_with_and()->add_exists();
+ Variable_ID wc3 = f_exists->declare();
+ F_And *f_root = f_exists->add_and();
+ GEQ_Handle h = f_root->add_GEQ();
+ for (Constr_Vars_Iter cvi(*e); cvi; cvi++) {
+ switch (cvi.curr_var()->kind()) {
+ case Wildcard_Var:
+ h.update_coef(wc3, cvi.curr_coef());
+ break;
+ case Input_Var:
+ h.update_coef(r.input_var(cvi.curr_var()->get_position()), cvi.curr_coef());
+ break;
+ case Global_Var: {
+ Global_Var_ID g = cvi.curr_var()->get_global_var();
+ Variable_ID v;
+ if (g->arity() == 0)
+ v = r.get_local(g);
+ else
+ v = r.get_local(g, cvi.curr_var()->function_of());
+ h.update_coef(v, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(false);
+ }
+ }
+ h.update_const((*e).get_const());
+
+ h = f_root->add_GEQ();
+ for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) {
+ switch (cvi.curr_var()->kind()) {
+ case Wildcard_Var:
+ h.update_coef(wc3, cvi.curr_coef());
+ break;
+ case Input_Var:
+ h.update_coef(r.input_var(cvi.curr_var()->get_position()), cvi.curr_coef());
+ break;
+ case Global_Var: {
+ Global_Var_ID g = cvi.curr_var()->get_global_var();
+ Variable_ID v;
+ if (g->arity() == 0)
+ v = r.get_local(g);
+ else
+ v = r.get_local(g, cvi.curr_var()->function_of());
+ h.update_coef(v, cvi.curr_coef());
+ break;
+ }
+ default:
+ assert(false);
+ }
+ }
+ h.update_const((*e2).get_const());
+
+ r.simplify();
+ r.copy_names(R);
+ r.setup_names();
+ return r;
+ }
+ }
+ }
+ }
+}
+
+
+//
+// heavy lifting for code output for one leaf node
+//
+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) {
+ if (active.num_elem() == 0)
+ return NULL;
+
+ CG_outputRepr *stmt_list = NULL;
+ for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) {
+ std::map<int, Relation>::const_iterator j = guards.find(*i);
+ if (j == guards.end() || Must_Be_Subset(copy(known), copy(j->second))) {
+ Relation mapping = Inverse(copy((xforms[remap[*i]])));
+ mapping.simplify();
+ mapping.setup_names();
+ std::vector<std::string> loop_vars;
+ for (int k = 1; k <= mapping.n_out(); k++) {
+ loop_vars.push_back(mapping.output_var(k)->name());
+// std::cout << "CG_Utils:: " << k << ", " << mapping.output_var(k)->name().c_str() << "\n";
+ }
+ std::vector<CG_outputRepr *> sList = output_substitutions(ocg, mapping, assigned_on_the_fly);
+ stmt_list = ocg->StmtListAppend(stmt_list, ocg->CreateSubstitutedStmt((guard_repr==NULL)?indent:indent+1, stmts[remap[*i]]->clone(), loop_vars, sList));
+ active.unset(*i);
+ }
+ }
+
+ if (stmt_list != NULL) {
+ if (active.num_elem() != 0)
+ stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(active, guards, NULL, known, (guard_repr==NULL)?indent:indent+1, ocg, remap, xforms, stmts, assigned_on_the_fly));
+ if (guard_repr == NULL)
+ return stmt_list;
+ else
+ return ocg->CreateIf(indent, guard_repr, stmt_list, NULL);
+ }
+ else {
+ Relation then_cond = find_best_guard(const_cast<std::map<int, Relation> &>(guards)[*(active.begin())], active, guards);
+ assert(!then_cond.is_obvious_tautology());
+ Relation new_then_known = Intersection(copy(known), copy(then_cond));
+ new_then_known.simplify();
+ Relation else_cond = Complement(copy(then_cond));
+ else_cond.simplify();
+ Relation new_else_known = Intersection(copy(known), copy(else_cond));
+ new_else_known.simplify();
+
+ BoolSet<> then_active(active.size()), else_active(active.size()), indep_active(active.size());
+ std::map<int, Relation> then_guards, else_guards;
+ for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) {
+ Relation &r = const_cast<std::map<int, Relation> &>(guards)[*i];
+ if (Must_Be_Subset(copy(r), copy(then_cond))) {
+ Relation r2 = Gist(copy(r), copy(then_cond), 1);
+ if (!r2.is_obvious_tautology())
+ then_guards[*i] = r2;
+ then_active.set(*i);
+ }
+ else if (Must_Be_Subset(copy(r), copy(else_cond))) {
+ Relation r2 = Gist(copy(r), copy(else_cond), 1);
+ if (!r2.is_obvious_tautology())
+ else_guards[*i] = r2;
+ else_active.set(*i);
+ }
+ else
+ indep_active.set(*i);
+ }
+ assert(!then_active.empty());
+
+ CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, assigned_on_the_fly);
+ if (else_active.empty() && indep_active.empty()) {
+ guard_repr = ocg->CreateAnd(guard_repr, new_guard_repr);
+ return leaf_print_repr(then_active, then_guards, guard_repr, new_then_known, indent, ocg, remap, xforms, stmts, assigned_on_the_fly);
+ }
+ else if (else_active.empty() && !indep_active.empty()) {
+ int new_indent = (guard_repr==NULL)?indent:indent+1;
+ stmt_list = leaf_print_repr(then_active, then_guards, new_guard_repr, new_then_known, new_indent, ocg, remap, xforms, stmts, assigned_on_the_fly);
+ stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(indep_active, guards, NULL, known, new_indent, ocg, remap, xforms, stmts, assigned_on_the_fly));
+ if (guard_repr == NULL)
+ return stmt_list;
+ else
+ return ocg->CreateIf(indent, guard_repr, stmt_list, NULL);
+ }
+ else { // (!else_active.empty())
+ int new_indent = (guard_repr==NULL)?indent:indent+1;
+ CG_outputRepr *then_stmt_list = leaf_print_repr(then_active, then_guards, NULL, new_then_known, new_indent+1, ocg, remap, xforms, stmts, assigned_on_the_fly);
+ CG_outputRepr *else_stmt_list = leaf_print_repr(else_active, else_guards, NULL, new_else_known, new_indent+1, ocg, remap, xforms, stmts, assigned_on_the_fly);
+ stmt_list = ocg->CreateIf(new_indent, new_guard_repr, then_stmt_list, else_stmt_list);
+ if (!indep_active.empty())
+ stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(indep_active, guards, NULL, known, new_indent, ocg, remap, xforms, stmts, assigned_on_the_fly));
+ if (guard_repr == NULL)
+ return stmt_list;
+ else
+ return ocg->CreateIf(indent, guard_repr, stmt_list, NULL);
+ }
+ }
+}
+
+
+//
+// heavy lifting for code output for one level of loop nodes
+//
+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) {
+ if (start >= end)
+ return NULL;
+
+ Relation R = Gist(copy(loops[start]->guard_), copy(guard), 1);
+ if (Must_Be_Subset(Intersection(copy(loops[start]->known_), copy(guard)), copy(R))) {
+ int new_indent = (guard_repr==NULL)?indent:indent+1;
+ int i = start+1;
+ for ( ; i < end; i++)
+ if (!Gist(copy(loops[i]->guard_), copy(guard), 1).is_obvious_tautology())
+ break;
+ CG_outputRepr *stmt_list = NULL;
+ for (int j = start; j < i; j++)
+ stmt_list = ocg->StmtListAppend(stmt_list, loops[j]->printRepr(false, new_indent, ocg, stmts, assigned_on_the_fly));
+ stmt_list = ocg->StmtListAppend(stmt_list, loop_print_repr(loops, i, end, guard, NULL, new_indent, ocg, stmts, assigned_on_the_fly));
+ if (guard_repr == NULL)
+ return stmt_list;
+ else
+ return ocg->CreateIf(indent, guard_repr, stmt_list, NULL);
+ }
+
+ Relation then_cond = find_best_guard(R, loops, start, end);
+ assert(!then_cond.is_obvious_tautology());
+ Relation else_cond = Complement(copy(then_cond));
+ else_cond.simplify();
+
+ std::vector<CG_loop *> then_loops, else_loops, indep_loops;
+ int i = start;
+ for ( ; i < end; i++)
+ if (!Must_Be_Subset(copy(loops[i]->guard_), copy(then_cond)))
+ break;
+ int j = i;
+ for ( ; j < end; j++)
+ if (!Must_Be_Subset(copy(loops[j]->guard_), copy(else_cond)))
+ break;
+ assert(i>start);
+
+ CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, assigned_on_the_fly);
+ if (j == i && end == j) {
+ guard_repr = ocg->CreateAnd(guard_repr, new_guard_repr);
+ Relation new_guard = Intersection(copy(guard), copy(then_cond));
+ new_guard.simplify();
+ return loop_print_repr(loops, start, end, new_guard, guard_repr, indent, ocg, stmts, assigned_on_the_fly);
+ }
+ else if (j == i && end > j) {
+ int new_indent = (guard_repr==NULL)?indent:indent+1;
+ Relation new_guard = Intersection(copy(guard), copy(then_cond));
+ new_guard.simplify();
+ CG_outputRepr *stmt_list = loop_print_repr(loops, start, i, new_guard, new_guard_repr, new_indent, ocg, stmts, assigned_on_the_fly);
+ stmt_list = ocg->StmtListAppend(stmt_list, loop_print_repr(loops, j, end, guard, NULL, new_indent, ocg, stmts, assigned_on_the_fly));
+ if (guard_repr == NULL)
+ return stmt_list;
+ else
+ return ocg->CreateIf(indent, guard_repr, stmt_list, NULL);
+ }
+ else { // (j > i)
+ int new_indent = (guard_repr==NULL)?indent:indent+1;
+ Relation then_new_guard = Intersection(copy(guard), copy(then_cond));
+ then_new_guard.simplify();
+ CG_outputRepr *then_stmt_list = loop_print_repr(loops, start, i, then_new_guard, NULL, new_indent+1, ocg, stmts, assigned_on_the_fly);
+ Relation else_new_guard = Intersection(copy(guard), copy(else_cond));
+ else_new_guard.simplify();
+ CG_outputRepr *else_stmt_list = loop_print_repr(loops, i, j, else_new_guard, NULL, new_indent+1, ocg, stmts, assigned_on_the_fly);
+ CG_outputRepr *stmt_list = ocg->CreateIf(new_indent, new_guard_repr, then_stmt_list, else_stmt_list);
+ stmt_list = ocg->StmtListAppend(stmt_list, loop_print_repr(loops, j, end, guard, NULL, new_indent, ocg, stmts, assigned_on_the_fly));
+ if (guard_repr == NULL)
+ return stmt_list;
+ else
+ return ocg->CreateIf(indent, guard_repr, stmt_list, NULL);
+ }
+}
+
+}
diff --git a/lib/codegen/src/codegen.cc b/lib/codegen/src/codegen.cc
new file mode 100755
index 0000000..92ca702
--- /dev/null
+++ b/lib/codegen/src/codegen.cc
@@ -0,0 +1,378 @@
+/*****************************************************************************
+ Copyright (C) 1994-2000 the Omega Project Team
+ Copyright (C) 2005-2011 Chun Chen
+ All Rights Reserved.
+
+ Purpose:
+ CodeGen class as entry point for code generation.
+
+ Notes:
+ Loop variable name prefix should not cause any possible name conflicts
+ with original loop variables wrapped in statement holder. This guarantees
+ that variable substitution done correctly in the generated code.
+
+ History:
+ 04/24/96 MMGenerateCode, added by Fortran D people. Lei Zhou
+ 09/17/08 loop overhead removal based on actual nesting depth -- by chun
+ 03/05/11 fold MMGenerateCode into CodeGen class, Chun Chen
+*****************************************************************************/
+
+#include <typeinfo>
+#include <omega.h>
+#include <basic/util.h>
+#include <math.h>
+#include <vector>
+#include <algorithm>
+
+#include <code_gen/CG.h>
+#include <code_gen/codegen.h>
+#include <code_gen/CG_outputBuilder.h>
+#include <code_gen/codegen_error.h>
+
+namespace omega {
+
+const std::string CodeGen::loop_var_name_prefix = "t";
+const int CodeGen::var_substitution_threshold = 10;
+
+//Anand--adding stuff to make Chun's code work with Gabe's
+std::vector< std::vector<int> > smtNonSplitLevels;
+std::vector< std::vector<std::string> > loopIdxNames;//per stmt
+std::vector< std::pair<int, std::string> > syncs;
+
+
+
+CodeGen::CodeGen(const std::vector<Relation> &xforms, const std::vector<Relation> &IS, const Relation &known, std::vector< std::vector<int> > smtNonSplitLevels_ , std::vector< std::vector<std::string> > loopIdxNames_, std::vector< std::pair<int, std::string> > syncs_) {
+ // check for sanity of parameters
+ int num_stmt = IS.size();
+ if (xforms.size() != num_stmt)
+ throw std::invalid_argument("number of iteration spaces does not match number of transformations");
+ known_ = copy(known);
+ if (known_.n_out() != 0)
+ throw std::invalid_argument("known condition must be a set relation");
+ if (known_.is_null())
+ known_ = Relation::True(0);
+ else
+ known_.simplify(2, 4);
+ if (!known_.is_upper_bound_satisfiable())
+ return;
+ if (known_.number_of_conjuncts() > 1)
+ throw std::invalid_argument("only one conjunct allowed in known condition");
+ xforms_ = xforms;
+ for (int i = 0; i < num_stmt; i++) {
+ xforms_[i].simplify();
+ if (!xforms_[i].has_single_conjunct())
+ throw std::invalid_argument("mapping relation must have only one conjunct");
+ if (xforms_[i].n_inp() != IS[i].n_inp() || IS[i].n_out() != 0)
+ throw std::invalid_argument("illegal iteration space or transformation arity");
+ }
+
+
+ //protonu--
+ //easier to handle this as a global
+ smtNonSplitLevels = smtNonSplitLevels_;
+ syncs = syncs_;
+ loopIdxNames = loopIdxNames_;
+ //end-protonu
+
+
+
+ // find the maximum iteration space dimension we are going to operate on
+ int num_level = known_.n_inp();
+ for (int i = 0; i < num_stmt; i++)
+ if (xforms_[i].n_out() > num_level)
+ num_level = xforms_[i].n_out();
+ known_ = Extend_Set(known_, num_level-known_.n_inp());
+ for (int i = 1; i <= num_level; i++)
+ known_.name_set_var(i, loop_var_name_prefix + to_string(i));
+ known_.setup_names();
+
+ // split disjoint conjunctions in original iteration spaces
+ std::vector<Relation> new_IS;
+ for (int i = 0; i < num_stmt; i++) {
+ for (int j = 1; j <= IS[i].n_inp(); j++)
+ xforms_[i].name_input_var(j, const_cast<std::vector<Relation> &>(IS)[i].input_var(j)->name());
+ for (int j = 1; j <= xforms_[i].n_out(); j++)
+ xforms_[i].name_output_var(j, loop_var_name_prefix + to_string(j));
+ xforms_[i].setup_names();
+
+ Relation R = Range(Restrict_Domain(copy(xforms_[i]), copy(IS[i])));
+ R = Intersection(Extend_Set(R, num_level-R.n_inp()), copy(known_));
+ R.simplify(2, 4);
+ if (R.is_inexact())
+ throw codegen_error("cannot generate code for inexact iteration spaces");
+
+ while(R.is_upper_bound_satisfiable()) {
+ DNF *dnf = R.query_DNF();
+ DNF_Iterator c(dnf);
+ Relation R2 = Relation(R, *c);
+ R2.simplify();
+ new_IS.push_back(copy(R2));
+ remap_.push_back(i);
+ c.next();
+ if (!c.live())
+ break;
+ Relation remainder(R, *c);
+ c.next();
+ while (c.live()) {
+ remainder = Union(remainder, Relation(R, *c));
+ c.next();
+ }
+ R = Difference(remainder, R2);
+ R.simplify(2, 4);
+ }
+ }
+
+ // number of new statements after splitting
+ num_stmt = new_IS.size();
+ if(!smtNonSplitLevels.empty())
+ smtNonSplitLevels.resize(num_stmt);
+ // assign a dummy value to loops created for the purpose of expanding to maximum dimension
+ for (int i = 0; i < num_stmt; i++) {
+ if (xforms[remap_[i]].n_out() < num_level) {
+ F_And *f_root = new_IS[i].and_with_and();
+ for (int j = xforms[remap_[i]].n_out()+1; j <= num_level; j++) {
+ EQ_Handle h = f_root->add_EQ();
+ h.update_coef(new_IS[i].set_var(j), 1);
+ h.update_const(posInfinity);
+ }
+ new_IS[i].simplify();
+ }
+ }
+
+ // calculate projected subspaces for each loop level once and save for CG tree manipulation later
+ projected_IS_ = std::vector<std::vector<Relation> >(num_level);
+ for (int i = 0; i < num_level; i++)
+ projected_IS_[i] = std::vector<Relation>(num_stmt);
+ for (int i = 0; i < num_stmt; i++) {
+ if (num_level > 0)
+ projected_IS_[num_level-1][i] = new_IS[i];
+ for (int j = num_level-1; j >= 1; j--) {
+ projected_IS_[j-1][i] = Project(copy(projected_IS_[j][i]), j+1, Set_Var);
+ projected_IS_[j-1][i].simplify(2, 4);
+ }
+ }
+}
+
+
+CG_result *CodeGen::buildAST(int level, const BoolSet<> &active, bool split_on_const, const Relation &restriction) {
+ if (level > num_level())
+ return new CG_leaf(this, active);
+
+ int num_active_stmt = active.num_elem();
+ if (num_active_stmt == 0)
+ return NULL;
+ else if (num_active_stmt == 1)
+ return new CG_loop(this, active, level, buildAST(level+1, active, true, restriction));
+
+ // use estimated constant bounds for fast non-overlap iteration space splitting
+ if (split_on_const) {
+ std::vector<std::pair<std::pair<coef_t, coef_t>, int> > bounds;
+
+ for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) {
+ Relation r = Intersection(copy(projected_IS_[level-1][*i]), copy(restriction));
+ r.simplify(2, 4);
+ if (!r.is_upper_bound_satisfiable())
+ continue;
+ coef_t lb, ub;
+ r.single_conjunct()->query_variable_bounds(r.set_var(level),lb,ub);
+ bounds.push_back(std::make_pair(std::make_pair(lb, ub), *i));
+ }
+ sort(bounds.begin(), bounds.end());
+
+ std::vector<Relation> split_cond;
+ std::vector<CG_result *> split_child;
+
+ coef_t prev_val = -posInfinity;
+ coef_t next_val = bounds[0].first.second;
+ BoolSet<> next_active(active.size());
+ int i = 0;
+ while (i < bounds.size()) {
+ if (bounds[i].first.first <= next_val) {
+ next_active.set(bounds[i].second);
+ next_val = max(next_val, bounds[i].first.second);
+ i++;
+ }
+ else {
+ Relation r(num_level());
+ F_And *f_root = r.add_and();
+ if (prev_val != -posInfinity) {
+ GEQ_Handle h = f_root->add_GEQ();
+ h.update_coef(r.set_var(level), 1);
+ h.update_const(-prev_val-1);
+ }
+ if (next_val != posInfinity) {
+ GEQ_Handle h = f_root->add_GEQ();
+ h.update_coef(r.set_var(level), -1);
+ h.update_const(next_val);
+ }
+ r.simplify();
+
+ Relation new_restriction = Intersection(copy(r), copy(restriction));
+ new_restriction.simplify(2, 4);
+ CG_result *child = buildAST(level, next_active, false, new_restriction);
+ if (child != NULL) {
+ split_cond.push_back(copy(r));
+ split_child.push_back(child);
+ }
+ next_active.unset_all();
+ prev_val = next_val;
+ next_val = bounds[i].first.second;
+ }
+ }
+ if (!next_active.empty()) {
+ Relation r = Relation::True(num_level());
+ if (prev_val != -posInfinity) {
+ F_And *f_root = r.and_with_and();
+ GEQ_Handle h = f_root->add_GEQ();
+ h.update_coef(r.set_var(level), 1);
+ h.update_const(-prev_val-1);
+ r.simplify();
+ }
+ Relation new_restriction = Intersection(copy(r), copy(restriction));
+ new_restriction.simplify(2, 4);
+ CG_result *child = buildAST(level, next_active, false, new_restriction);
+ if (child != NULL) {
+ split_cond.push_back(copy(r));
+ split_child.push_back(child);
+ }
+ }
+
+ if (split_child.size() == 0)
+ return NULL;
+ else if (split_child.size() == 1)
+ return split_child[0];
+ else
+ return new CG_split(this, active, split_cond, split_child);
+ }
+ // check bound conditions exhaustively for non-overlap iteration space splitting
+ else {
+ std::vector<Relation> Rs(active.size());
+ for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) {
+ Rs[*i] = Intersection(Approximate(copy(projected_IS_[level-1][*i])), copy(restriction));
+ Rs[*i].simplify(2, 4);
+ }
+ Relation hull = SimpleHull(Rs);
+
+ //protonu-warn Chun about this change
+ //This does some fancy splitting of statements into loops with the
+ //fewest dimentions, but that's not necessarily what we want when
+ //code-gening for CUDA. smtNonSplitLevels keeps track per-statment of
+ //the levels that should not be split on.
+ bool checkForSplits = true;
+ for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) {
+ if(*i < smtNonSplitLevels.size())
+ for(int k = 0; k <smtNonSplitLevels[*i].size(); k++)
+ if(smtNonSplitLevels[*i][k] == (level-2)){
+ checkForSplits = false;
+ break;
+ }
+ }
+
+
+
+
+ for (BoolSet<>::const_iterator i = active.begin(); i != active.end() && checkForSplits; i++) {
+ Relation r = Gist(copy(Rs[*i]), copy(hull), 1);
+ if (r.is_obvious_tautology())
+ continue;
+ r = EQs_to_GEQs(r);
+
+ for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++) {
+ if ((*e).has_wildcards())
+ continue;
+
+ Relation cond = Relation::True(num_level());
+ BoolSet<> first_chunk(active.size());
+ BoolSet<> second_chunk(active.size());
+
+ if ((*e).get_coef(hull.set_var(level)) > 0) {
+ cond.and_with_GEQ(*e);
+ cond = Complement(cond);;
+ cond.simplify();
+ second_chunk.set(*i);
+ }
+ else if ((*e).get_coef(hull.set_var(level)) < 0) {
+ cond.and_with_GEQ(*e);
+ cond.simplify();
+ first_chunk.set(*i);
+ }
+ else
+ continue;
+
+ bool is_proper_split_cond = true;
+ for (BoolSet<>::const_iterator j = active.begin(); j != active.end(); j++)
+ if ( *j != *i) {
+ bool in_first = Intersection(copy(Rs[*j]), copy(cond)).is_upper_bound_satisfiable();
+ bool in_second = Difference(copy(Rs[*j]), copy(cond)).is_upper_bound_satisfiable();
+
+ if (in_first && in_second) {
+ is_proper_split_cond = false;
+ break;
+ }
+
+ if (in_first)
+ first_chunk.set(*j);
+ else if (in_second)
+ second_chunk.set(*j);
+ }
+
+ if (is_proper_split_cond && first_chunk.num_elem() != 0 && second_chunk.num_elem() != 0) {
+ CG_result *first_cg = buildAST(level, first_chunk, false, copy(cond));
+ CG_result *second_cg = buildAST(level, second_chunk, false, Complement(copy(cond)));
+ if (first_cg == NULL)
+ return second_cg;
+ else if (second_cg == NULL)
+ return first_cg;
+ else {
+ std::vector<Relation> split_cond;
+ std::vector<CG_result *> split_child;
+ split_cond.push_back(copy(cond));
+ split_child.push_back(first_cg);
+ split_cond.push_back(Complement(copy(cond)));
+ split_child.push_back(second_cg);
+
+ return new CG_split(this, active, split_cond, split_child);
+ }
+ }
+ }
+ }
+ return new CG_loop(this, active, level, buildAST(level+1, active, true, restriction));
+ }
+}
+
+
+CG_result *CodeGen::buildAST(int effort) {
+ if (remap_.size() == 0)
+ return NULL;
+
+ CG_result *cgr = buildAST(1, ~BoolSet<>(remap_.size()), true, Relation::True(num_level()));
+ if (cgr == NULL)
+ return NULL;
+
+
+ // break down the complete iteration space condition to levels of bound/guard condtions
+ cgr = cgr->recompute(cgr->active_, copy(known_), copy(known_));
+
+
+
+ if (cgr == NULL)
+ return NULL;
+
+ // calculate each loop's nesting depth
+ int depth = cgr->populateDepth();
+
+
+ // redistribute guard condition locations by additional splittings
+ std::pair<CG_result *, Relation> result = cgr->liftOverhead(min(effort,depth), false);
+
+ // since guard conditions are postponed for non-loop levels, hoist them now.
+ // this enables proper if-condition simplication when outputting actual code.
+ result.first->hoistGuard();
+
+
+
+
+ return result.first;
+}
+
+}
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2025-02-02 02:58:18 +0000