From ab016596602a4c6bdc27adf01c308b325af221f0 Mon Sep 17 00:00:00 2001 From: Tuowen Zhao Date: Wed, 21 Sep 2016 22:35:47 -0600 Subject: something that only builds ... --- lib/codegen/include/code_gen/CG.h | 23 +- lib/codegen/include/code_gen/CG_outputBuilder.h | 171 +- lib/codegen/include/code_gen/CG_outputRepr.h | 10 +- lib/codegen/include/code_gen/CG_stringBuilder.h | 37 +- lib/codegen/include/code_gen/CG_stringRepr.h | 12 +- lib/codegen/include/code_gen/CG_utils.h | 40 +- lib/codegen/src/CG.cc | 2790 +++++++++------- lib/codegen/src/CG_stringBuilder.cc | 1001 +++--- lib/codegen/src/CG_stringRepr.cc | 32 + lib/codegen/src/CG_utils.cc | 3983 ++++++++++++++--------- 10 files changed, 5017 insertions(+), 3082 deletions(-) mode change 100644 => 100755 lib/codegen/src/CG.cc mode change 100644 => 100755 lib/codegen/src/CG_stringBuilder.cc create mode 100755 lib/codegen/src/CG_stringRepr.cc (limited to 'lib/codegen') diff --git a/lib/codegen/include/code_gen/CG.h b/lib/codegen/include/code_gen/CG.h index ce56768..4dd629c 100644 --- a/lib/codegen/include/code_gen/CG.h +++ b/lib/codegen/include/code_gen/CG.h @@ -22,9 +22,13 @@ struct CG_result { virtual std::pair 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 &stmts, const std::vector > &assigned_on_the_fly) const = 0; - CG_outputRepr *printRepr(CG_outputBuilder *ocg, const std::vector &stmts) const; - std::string printString() const; + virtual CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly,std::vector > > unin, bool printString = false) const = 0; + CG_outputRepr *printRepr(CG_outputBuilder *ocg, const std::vector &stmts, std::vector > >uninterpreted_symbols, bool printString = false) const; + std::string printString(std::vector > >uninterpreted_symbols = std::vector > >()) const; + + //virtual CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly) const = 0; + //CG_outputRepr *printRepr(CG_outputBuilder *ocg, const std::vector &stmts) const; + //std::string printString() const; int num_level() const; virtual CG_result *clone() const = 0; virtual void dump(int indent) const {} @@ -52,7 +56,8 @@ struct CG_split: public CG_result { std::pair liftOverhead(int depth, bool propagate_up); Relation hoistGuard(); void removeGuard(const Relation &guard); - CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly) const; + CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly, std::vector > > unin, bool printString=false) const; + // CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly) const; CG_result *clone() const; void dump(int indent) const; @@ -85,8 +90,11 @@ struct CG_loop: public CG_result { std::pair liftOverhead(int depth, bool propagate_up); Relation hoistGuard(); void removeGuard(const Relation &guard); - CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly) const; - CG_outputRepr *printRepr(bool do_print_guard, int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly) const; + CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly,std::vector > >unin, bool printString = false) const; + CG_outputRepr *printRepr(bool do_print_guard, int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly, std::vector > > unin, bool printString = false) const; + + // CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly) const; + //CG_outputRepr *printRepr(bool do_print_guard, int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly) const; CG_result *clone() const; void dump(int indent) const; }; @@ -108,7 +116,8 @@ struct CG_leaf: public CG_result { std::pair liftOverhead(int depth, bool propagate_up); Relation hoistGuard(); void removeGuard(const Relation &guard); - CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly) const; + CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly, std::vector > > unin, bool printString = false) const; + // CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector &stmts, const std::vector > &assigned_on_the_fly) const; CG_result *clone() const; void dump(int indent) const; }; diff --git a/lib/codegen/include/code_gen/CG_outputBuilder.h b/lib/codegen/include/code_gen/CG_outputBuilder.h index 19dc440..ce86c91 100644 --- a/lib/codegen/include/code_gen/CG_outputBuilder.h +++ b/lib/codegen/include/code_gen/CG_outputBuilder.h @@ -4,7 +4,7 @@ All Rights Reserved. Purpose: - abstract base class of comiler IR code builder + abstract base class of compiler IR code builder Notes: All "CG_outputRepr *" parameters are consumed inside the the function @@ -29,57 +29,98 @@ namespace omega { -//! abstract base class of comiler IR code builder class CG_outputBuilder { +private: + public: + CG_outputBuilder() {} virtual ~CG_outputBuilder() {} - //! substitute variables in stmt - virtual CG_outputRepr *CreateSubstitutedStmt(int indent, CG_outputRepr *stmt, - const std::vector &vars, - std::vector &subs) const = 0; - //! assignment stmt generation - virtual CG_outputRepr *CreateAssignment(int indent, CG_outputRepr *lhs, + virtual CG_outputRepr *CreateStruct(const std::string class_name, + std::vector class_data_members, // why not just vector< CG_outputRepr> subparts; + std::vector class_data_types )=0; + virtual CG_outputRepr *CreateClassInstance(std::string name , CG_outputRepr *class_def)=0; + virtual CG_outputRepr *lookup_member_data(CG_outputRepr* scope, std::string varName, CG_outputRepr *instance)=0; + virtual CG_outputRepr* CreatePointer(std::string &name) const = 0; + virtual CG_outputRepr* ObtainInspectorRange(const std::string &_s, const std::string &_name) const=0; + + + + //--------------------------------------------------------------------------- + // substitute variables in stmt + //--------------------------------------------------------------------------- + virtual CG_outputRepr *CreateSubstitutedStmt(int indent, + CG_outputRepr *stmt, + const std::vector &vars, + std::vector &subs, + bool actuallyPrint =true) 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 *CreatePlusAssignment(int indent, + CG_outputRepr *lhs, + CG_outputRepr *rhs) const = 0; + + //--------------------------------------------------------------------------- + // function invocation generation + //--------------------------------------------------------------------------- virtual CG_outputRepr *CreateInvoke(const std::string &funcName, - std::vector &argList) const = 0; + std::vector &argList, + bool is_array=false) const = 0; - //! comment generation + //--------------------------------------------------------------------------- + // comment generation + //--------------------------------------------------------------------------- virtual CG_outputRepr *CreateComment(int indent, const std::string &commentText) const = 0; - //! Attribute generation + //--------------------------------------------------------------------------- + // Attribute generation + //--------------------------------------------------------------------------- virtual CG_outputRepr* CreateAttribute(CG_outputRepr *control, const std::string &commentText) const = 0; - //! Pragma Attribute + //--------------------------------------------------------------------------- + // Pragma Attribute + // -------------------------------------------------------------------------- virtual CG_outputRepr* CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const = 0; - //! Prefetch Attribute + //--------------------------------------------------------------------------- + // 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 + //--------------------------------------------------------------------------- + // 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) + //--------------------------------------------------------------------------- + // 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 + //--------------------------------------------------------------------------- + // 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 - */ + //--------------------------------------------------------------------------- + // 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; @@ -87,73 +128,87 @@ public: return original->clone(); } - //! basic integer number creation + //--------------------------------------------------------------------------- + // basic integer number creation + //--------------------------------------------------------------------------- virtual CG_outputRepr *CreateInt(int num) const = 0; - virtual bool isInteger(CG_outputRepr *op) const = 0; + virtual CG_outputRepr *CreateFloat(float num) const = 0; + virtual CG_outputRepr *CreateDouble(double num) const = 0; + virtual bool isInteger(CG_outputRepr *op) const = 0; + virtual bool QueryInspectorType(const std::string &varName) const = 0; - //! basic identity/variable creation + //--------------------------------------------------------------------------- + // basic identity/variable creation + //--------------------------------------------------------------------------- virtual CG_outputRepr *CreateIdent(const std::string &varName) const = 0; - - //! Addition operations, NULL parameter means 0, + virtual CG_outputRepr* CreateDotExpression(CG_outputRepr *lop, + CG_outputRepr *rop) const =0; + virtual CG_outputRepr* CreateArrayRefExpression(const std::string &_s, + CG_outputRepr *rop) const =0; + virtual CG_outputRepr* CreateArrayRefExpression(CG_outputRepr *lop, + CG_outputRepr *rop) const=0; + virtual CG_outputRepr* ObtainInspectorData(const std::string &_s, const std::string &member_name) const=0; + virtual CG_outputRepr* CreateNullStatement() const=0; + + //--------------------------------------------------------------------------- + // binary arithmetic operations, NULL parameter means 0, + // Note: + // integer division truncation method undefined, only use when lop is known + // to be multiple of rop, otherwise use integer floor instead + //--------------------------------------------------------------------------- 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 - */ + //--------------------------------------------------------------------------- + // integer arithmetic functions, NULL parameter means 0, second parameter + // must be postive (i.e. b > 0 below), otherwise function undefined + // Note: + // ceil(a, b) = -floor(-a, b) or floor(a+b-1, b) or floor(a-1, b)+1 + // mod(a, b) = a-b*floor(a, b) + // where result must lie in range [0,b) + // floor(a, b) = a/b if a >= 0 + // (a-b+1)/b if a < 0 + // where native '/' operator behaves as 5/2 = 2, (-5)/2 = -2 + //--------------------------------------------------------------------------- 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 + //--------------------------------------------------------------------------- + // 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 + //--------------------------------------------------------------------------- + // binary condition operations + //--------------------------------------------------------------------------- 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; + virtual CG_outputRepr *CreateNEQ(CG_outputRepr *lop, CG_outputRepr *rop) const = 0; + virtual CG_outputRepr *CreateAddressOf(CG_outputRepr *op) const = 0; + virtual CG_outputRepr *CreateBreakStatement(void) const = 0; - //! join stmts together, NULL parameter allowed + //--------------------------------------------------------------------------- + // join stmts together, NULL parameter allowed + //--------------------------------------------------------------------------- virtual CG_outputRepr *StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const = 0; + virtual CG_outputRepr *CreateStatementFromExpression(CG_outputRepr *exp) const = 0; + + virtual const char *ClassName() { return "UNKNOWN"; } }; } diff --git a/lib/codegen/include/code_gen/CG_outputRepr.h b/lib/codegen/include/code_gen/CG_outputRepr.h index 0897007..d72ae6f 100644 --- a/lib/codegen/include/code_gen/CG_outputRepr.h +++ b/lib/codegen/include/code_gen/CG_outputRepr.h @@ -15,17 +15,19 @@ #ifndef _CG_OUTPUTREPR_H #define _CG_OUTPUTREPR_H +#include + namespace omega { class CG_outputRepr { public: + CG_outputRepr() {} - //! shallow delete - virtual ~CG_outputRepr() { } + virtual ~CG_outputRepr() { /* shallow delete */ } virtual CG_outputRepr *clone() const = 0; - //! delete actual IR code wrapped inside - virtual void clear() { } + virtual void clear() { /* delete actual IR code wrapped inside */ } virtual void dump() const {} + virtual char *type() const = 0; }; } diff --git a/lib/codegen/include/code_gen/CG_stringBuilder.h b/lib/codegen/include/code_gen/CG_stringBuilder.h index 09d3503..390039a 100644 --- a/lib/codegen/include/code_gen/CG_stringBuilder.h +++ b/lib/codegen/include/code_gen/CG_stringBuilder.h @@ -8,22 +8,39 @@ 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 &vars, std::vector &subs) const; + bool QueryInspectorType(const std::string &varName) const; + + CG_stringRepr *CreateInt(int num) const; + CG_stringRepr *CreateFloat(float num) const; + CG_stringRepr *CreateDouble(double num) const; + + CG_stringRepr *CreateSubstitutedStmt(int indent, CG_outputRepr *stmt, const std::vector &vars, std::vector &subs, bool actuallyPrint) const; CG_stringRepr *CreateAssignment(int indent, CG_outputRepr *lhs, CG_outputRepr *rhs) const; - CG_stringRepr *CreateInvoke(const std::string &funcName, std::vector &argList) const; + CG_stringRepr *CreatePlusAssignment(int indent, CG_outputRepr *lhs, CG_outputRepr *rhs) const; + CG_stringRepr *CreateInvoke(const std::string &funcName, std::vector &argList,bool is_array=false) 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* CreateNullStatement() 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 *CreateAddressOf(CG_outputRepr *op) const ; CG_stringRepr *CreateIdent(const std::string &varName) const; + CG_stringRepr *CreateDotExpression(CG_outputRepr *lop, + CG_outputRepr *rop) const; + CG_stringRepr *CreateArrayRefExpression(const std::string &_s, + CG_outputRepr *rop) const; + CG_stringRepr* CreateArrayRefExpression(CG_outputRepr *lop, + CG_outputRepr *rop) const; + CG_stringRepr *ObtainInspectorData(const std::string &_s, const std::string &member_name) 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; @@ -35,7 +52,21 @@ public: 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 *CreateNEQ(CG_outputRepr *lop, CG_outputRepr *rop) const; + CG_stringRepr *CreateBreakStatement(void) const; CG_stringRepr *StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const; + CG_stringRepr *CreateStatementFromExpression(CG_outputRepr *exp) const; + + CG_outputRepr *CreateStruct(const std::string struct_name, + std::vector data_members, + std::vector data_types); + + CG_outputRepr *CreateClassInstance(std::string name , CG_outputRepr *class_def); + CG_outputRepr *lookup_member_data(CG_outputRepr* scope, std::string varName, CG_outputRepr *instance); + const char *ClassName() { return "stringBuilder"; }; + CG_outputRepr* CreatePointer(std::string &name) const; + CG_outputRepr* ObtainInspectorRange(const std::string &_s, const std::string &_name) const; + }; diff --git a/lib/codegen/include/code_gen/CG_stringRepr.h b/lib/codegen/include/code_gen/CG_stringRepr.h index a6df85d..b483bdb 100644 --- a/lib/codegen/include/code_gen/CG_stringRepr.h +++ b/lib/codegen/include/code_gen/CG_stringRepr.h @@ -18,6 +18,7 @@ #include #include #include +#include namespace omega { @@ -26,11 +27,16 @@ private: std::string s_; public: - CG_stringRepr() {} - CG_stringRepr(const std::string &s) { s_ = s; } - ~CG_stringRepr() {} + char *type() const { return strdup("string"); }; + + + 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; } + void Dump() const; + void DumpToFile(FILE *fp = stderr) const; //--------------------------------------------------------------------------- // basic operation diff --git a/lib/codegen/include/code_gen/CG_utils.h b/lib/codegen/include/code_gen/CG_utils.h index a6128bc..c0995d1 100755 --- a/lib/codegen/include/code_gen/CG_utils.h +++ b/lib/codegen/include/code_gen/CG_utils.h @@ -12,20 +12,29 @@ 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 > &assigned_on_the_fly, std::set excluded_floor_vars = std::set()); -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 > &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 > &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 > &assigned_on_the_fly); +CG_outputRepr *output_inequality_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector > &assigned_on_the_fly, std::map > unin,std::set excluded_floor_vars = std::set()); +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 > &assigned_on_the_fly,std::map > unin); -CG_outputRepr *output_ident(CG_outputBuilder *ocg, const Relation &R, Variable_ID v, const std::vector > &assigned_on_the_fly); -std::pair > output_assignment(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector > &assigned_on_the_fly); -CG_outputRepr *output_loop(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector > &assigned_on_the_fly); -CG_outputRepr *output_guard(CG_outputBuilder *ocg, const Relation &R, const std::vector > &assigned_on_the_fly); -std::vector output_substitutions(CG_outputBuilder *ocg, const Relation &R, const std::vector > &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 > &assigned_on_the_fly, + std::map > unin); + +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 > &assigned_on_the_fly,std::map > unin); + +CG_outputRepr *output_ident(CG_outputBuilder *ocg, const Relation &R, Variable_ID v, const std::vector > &assigned_on_the_fly,std::map > unin); +std::pair > output_assignment(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector > &assigned_on_the_fly,std::map > unin); +CG_outputRepr *output_loop(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector > &assigned_on_the_fly,std::map > unin); +CG_outputRepr *output_guard(CG_outputBuilder *ocg, const Relation &R, const std::vector > &assigned_on_the_fly,std::map > unin); +std::vector output_substitutions(CG_outputBuilder *ocg, const Relation &R, const std::vector > &assigned_on_the_fly,std::map > unin); 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 find_simplest_assignment(const Relation &R, Variable_ID v, const std::vector > &assigned_on_the_fly = std::vector >()); +std::pair find_simplest_assignment(const Relation &R, Variable_ID v, const std::vector > &assigned_on_the_fly = std::vector >(), bool *has_global_inspector= NULL); std::pair find_floor_definition(const Relation &R, Variable_ID v, std::set excluded_floor_vars = std::set()); +//Anand: 07/31/2013 -- Added the followinng temporary function needs cleanup +std::vector > find_floor_definition_temp(const Relation &R, Variable_ID v, std::set excluded_floor_vars = std::set()); std::pair 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 &exists_mapping); @@ -34,12 +43,15 @@ CG_outputRepr *leaf_print_repr(BoolSet<> active, const std::map & CG_outputRepr *guard_repr, const Relation &known, int indent, CG_outputBuilder *ocg, const std::vector &remap, const std::vector &xforms, const std::vector &stmts, - const std::vector > &assigned_on_the_fly); -CG_outputRepr *loop_print_repr(const std::vector &loops, int start, int end, + const std::vector > &assigned_on_the_fly, std::vector > > unin); +CG_outputRepr *loop_print_repr(BoolSet<> active,const std::vector &loops, int start, int end, const Relation &guard, CG_outputRepr *guard_repr, - int indent, CG_outputBuilder *ocg, const std::vector &stmts, - const std::vector > &assigned_on_the_fly); + int indent, const std::vector &remap, const std::vector &xforms,CG_outputBuilder *ocg, const std::vector &stmts, + const std::vector > &assigned_on_the_fly, std::vector > > unin); +Relation checkAndRestoreIfProjectedByGlobal(const Relation &R1, const Relation &R2, Variable_ID v); +//Relation addInequalitiesToRelation( const Relation &R, std::vector &inequalities); +std::string print_to_iegen_string(Relation &R); } #endif diff --git a/lib/codegen/src/CG.cc b/lib/codegen/src/CG.cc old mode 100644 new mode 100755 index 42bd172..5d903c4 --- a/lib/codegen/src/CG.cc +++ b/lib/codegen/src/CG.cc @@ -1,4 +1,6 @@ + /***************************************************************************** + Copyright (C) 1994-2000 the Omega Project Team Copyright (C) 2005-2011 Chun Chen All Rights Reserved. @@ -19,7 +21,7 @@ 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 #include @@ -34,1130 +36,1666 @@ #include namespace omega { - -extern std::vector > smtNonSplitLevels; -extern std::vector > loopIdxNames; //per stmt -extern std::vector > 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 &stmts) const { - return printRepr(1, ocg, stmts, - std::vector >(num_level(), - std::make_pair(static_cast(NULL), 0))); -} - -std::string CG_result::printString() const { - CG_stringBuilder ocg; - std::vector 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(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_split::liftOverhead(int depth, - bool propagate_up) { - for (int i = 0; i < clauses_.size();) { - std::pair 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(NULL), - Relation::True(num_level())); - } else - return std::make_pair(this, Relation::True(num_level())); -} - -Relation CG_split::hoistGuard() { - std::vector 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_split::findNextLevel() const { - std::vector result; - for (int i = 0; i < clauses_.size(); i++) { - CG_split *splt = dynamic_cast(clauses_[i]); - if (splt != NULL) { - std::vector 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 &stmts, - const std::vector > &assigned_on_the_fly) const { - CG_outputRepr *stmtList = NULL; - std::vector next_level = findNextLevel(); - - std::vector cur_loops; - for (int i = 0; i < next_level.size(); i++) { - CG_loop *lp = dynamic_cast(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 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(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 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 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 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 exists_mapping; - - Relation b = Gist(copy(hull), copy(known), 1); - bool has_unresolved_bound = false; - - std::set 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 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 restrictions(2); - restrictions[0] = Complement(copy(r2)); - restrictions[0].simplify(); - restrictions[1] = r2; - std::vector 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 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 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 restrictions(2); - restrictions[1] = Complement(copy(r2)); - restrictions[1].simplify(); - restrictions[0] = r2; - std::vector 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 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 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 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 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 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 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_loop::liftOverhead(int depth, - bool propagate_up) { - if (depth_ > depth) { - assert(propagate_up == false); - std::pair 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 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 restrictions(2); - std::vector 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(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); - } + + extern std::vector > smtNonSplitLevels; + extern std::vector > loopIdxNames; //per stmt + extern std::vector > 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 &stmts, + std::vector > > uninterpreted_symbols, + bool printString) const { + fprintf(stderr, "\nCG_result::printRepr(ocg, stmts) \n"); + //Anand: making a tweak to allocate twice the original number of dynamically allocated variables + //for use with Uninterpreted function symbols + + //Anand: adding support for Replacing substituted variables within + //Uninterpreted function symbols or global variables with arity > 0 here + //--begin + + // check for an error that happened once + int num_unin = uninterpreted_symbols.size(); + int num_active = active_.size(); + if (num_unin < num_active) { + fprintf(stderr, "CG.cc CG_result::printRepr(), not enough uninterpreted symbols (%d) for active statements (5d)\n", num_unin, num_active); + exit(-1); + } + + std::vector > aotf = std::vector< + std::pair >(2 * num_level(), + std::make_pair(static_cast(NULL), 0)); + +#define DYINGHERE +#ifdef DYINGHERE + int num_levels = num_level(); + + for (int s = 0; s < active_.size(); s++) { + fprintf(stderr, "\ns %d\n", s); + std::vector loop_vars; + if (active_.get(s)) { + + Relation mapping = Inverse( + copy((codegen_->xforms_[codegen_->remap_[s]]))); + + mapping.simplify(); + mapping.setup_names(); + + for (int i = 1; i <= mapping.n_out(); i++) + loop_vars.push_back(mapping.output_var(i)->name()); + + std::vector subs_; + for (int i = 1; i <= mapping.n_out(); i++) { + Relation mapping1(mapping.n_out(), 1); + F_And *f_root = mapping1.add_and(); + EQ_Handle h = f_root->add_EQ(); + h.update_coef(mapping1.output_var(1), 1); + h.update_coef(mapping1.input_var(i), -1); + Relation r = Composition(mapping1, copy(mapping)); + r.simplify(); - - 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 &stmts, - const std::vector > &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 &stmts, - const std::vector > &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 > 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 > 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(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(this)->known_.print(); - std::cout << prefix << "restriction: "; - const_cast(this)->restriction_.print(); - std::cout << prefix << "bounds: "; - const_cast(this)->bounds_.print(); - std::cout << prefix << "guard: "; - const_cast(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_leaf::liftOverhead(int depth, bool) { - if (depth == 0) - return std::make_pair(this, Relation::True(num_level())); - - for (std::map::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 guards; - for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { - std::map::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::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 &stmts, - const std::vector > &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(this)->known_.print(); - for (std::map::const_iterator i = guards_.begin(); - i != guards_.end(); i++) { - std::cout << prefix << "guard #" << i->first << ":"; - const_cast(i->second).print(); - } -} - + //Relation r = copy(mapping); + + Variable_ID v = r.output_var(1); + loop_vars.push_back(mapping.output_var(i)->name()); + + std::pair result = find_simplest_assignment(r, + v, aotf); + + std::string hand = result.first.print_to_string(); + //fprintf(stderr, "result: %s, %d\n", hand.c_str(), result.second); + if (result.second < INT_MAX) { + + CG_outputRepr *subs = output_substitution_repr(ocg, + result.first, + v, + true, + r, + aotf, + uninterpreted_symbols[s]); + + subs_.push_back(subs->clone()); + + aotf[num_levels + i - 1] = std::make_pair(subs, 999); + + } else { + CG_outputRepr* repr = NULL; + + aotf[num_levels + i - 1] = std::make_pair(repr, 999); + } + } + if(!printString) + for (std::map >::iterator it = + uninterpreted_symbols[s].begin(); + it != uninterpreted_symbols[s].end(); it++) { + std::vector reprs_ = it->second; + std::vector reprs_2; + + for (int k = 0; k < reprs_.size(); k++) { + std::vector subs2; + for (int l = 0; l < subs_.size(); l++) { + + subs2.push_back(subs_[l]->clone()); + } + CG_outputRepr * temp = + ocg->CreateSubstitutedStmt(0, reprs_[k]->clone(), + loop_vars, subs2, false); + + if (temp != NULL) + reprs_2.push_back(temp); + // reprs_2.push_back(subs_[k]->clone()); + + } + if(reprs_2.size() > 0) + it->second = reprs_2; + } + + //break; + } + } + +//--end + +#endif + + fprintf(stderr, "\n\n\n\nprintRepr recursing ??? return printRepr( ... )\n"); + return printRepr(1, ocg, stmts, aotf, uninterpreted_symbols, printString); + } + + + + std::string CG_result::printString( + std::vector > > uninterpreted_symbols) const { + + fprintf(stderr, "CG.cc line 164, CG_result::printString()\n"); + CG_stringBuilder ocg; + std::vector stmts(codegen_->xforms_.size()); + + fprintf(stderr, "stmts.size() %d\n", stmts.size()); + for (int i = 0; i < stmts.size(); i++) + stmts[i] = new CG_stringRepr("s" + to_string(i)); + + CG_stringRepr *repr = static_cast(printRepr(&ocg, + stmts, + uninterpreted_symbols, + true)); + + for (int i = 0; i < stmts.size(); i++) + delete stmts[i]; + + if (repr != NULL) { + std::string s = repr->GetString(); + //fprintf(stderr, "\nCG.cc L197 repr->GetString() = '%s'\n\n\n", s.c_str()); + 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_split::liftOverhead(int depth, + bool propagate_up) { + for (int i = 0; i < clauses_.size();) { + std::pair 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(NULL), + Relation::True(num_level())); + } else + return std::make_pair(this, Relation::True(num_level())); + } + + Relation CG_split::hoistGuard() { + std::vector 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_split::findNextLevel() const { + std::vector result; + for (int i = 0; i < clauses_.size(); i++) { + CG_split *splt = dynamic_cast(clauses_[i]); + if (splt != NULL) { + std::vector 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 &stmts, + const std::vector > &assigned_on_the_fly, + std::vector > > unin, + bool printString) const { + + fprintf(stderr, "CG_split::printRepr()\n"); + int numfly = assigned_on_the_fly.size(); + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + //for (int i=0; ip = assigned_on_the_fly[i]; + // CG_outputRepr *tr = NULL; + // if (p.first != NULL) tr = p.first->clone(); + // int val = p.second; + // fprintf(stderr, "0x%x %d\n", tr, val); + //} + + CG_outputRepr *stmtList = NULL; + std::vector next_level = findNextLevel(); + + std::vector cur_loops; + for (int i = 0; i < next_level.size(); i++) { + CG_loop *lp = dynamic_cast(next_level[i]); + if (lp != NULL) { + cur_loops.push_back(lp); + } else { + stmtList = ocg->StmtListAppend(stmtList, + loop_print_repr(active_, + cur_loops, + 0, + cur_loops.size(), + Relation::True(num_level()), + NULL, + indent, + codegen_->remap_, + codegen_->xforms_, + ocg, + stmts, + assigned_on_the_fly, + unin)); + stmtList = ocg->StmtListAppend(stmtList, + next_level[i]->printRepr(indent, + ocg, + stmts, + assigned_on_the_fly, + unin, + printString)); + cur_loops.clear(); + } + } + + stmtList = ocg->StmtListAppend(stmtList, + loop_print_repr(active_, + cur_loops, + 0, + cur_loops.size(), + Relation::True(num_level()), + NULL, + indent, + codegen_->remap_, + codegen_->xforms_, + ocg, + stmts, + assigned_on_the_fly, + unin)); + return stmtList; + } + + CG_result *CG_split::clone() const { + //fprintf(stderr, "CG_split::clone()\n"); + std::vector 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(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 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); + //Anand:Variables for inspector constraint check + bool has_insp = false; + bool found_insp = false; + + //Global_Var_ID global_insp; + //Argument_Tuple arg; + // check if actual loop is needed + std::pair 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 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 { + fprintf(stderr, "loop iterates more than once, extract bounds now\n"); + 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 exists_mapping; + + Relation b = Gist(copy(hull), copy(known), 1); + bool has_unresolved_bound = false; + + std::set 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 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) { + std::vector > result = + find_floor_definition_temp(b, cvi.curr_var(), + excluded_floor_vars); + + if (result.size() != 2) + break; + + has_unresolved_bound = false; + for (int i = 0; i < result.size(); i++) { + + GEQ_Handle h = f_root->add_GEQ(); + + for (Constr_Vars_Iter cvi(result[i].second); 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; + + 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((result[i].second).get_const()); + } + 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 restrictions(2); + restrictions[0] = Complement(copy(r2)); + restrictions[0].simplify(); + restrictions[1] = r2; + std::vector 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 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 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 restrictions(2); + restrictions[1] = Complement(copy(r2)); + restrictions[1].simplify(); + restrictions[0] = r2; + std::vector 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 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 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 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 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 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 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_))); + //Anand: IF inspector present in equality and GEQ add the equality constraint to known + //So as to avoid unnecessary IF condition + 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_loop::liftOverhead(int depth, + bool propagate_up) { + if (depth_ > depth) { + assert(propagate_up == false); + std::pair 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 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 restrictions(2); + std::vector 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(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_; + } + + + + 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 &stmts, + const std::vector > &assigned_on_the_fly, + std::vector > > unin, bool printString) const { + + fprintf(stderr, "CG_loop::printRepr() w assigned_on_the_fly gonna call printRepr with more arguments\n"); + //int numfly = assigned_on_the_fly.size(); + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + //for (int i=0; ip = assigned_on_the_fly[i]; + // CG_outputRepr *tr = NULL; + // if (p.first != NULL) tr = p.first->clone(); + // int val = p.second; + // //fprintf(stderr, "0x%x %d\n", tr, val); + //} + + return printRepr(true, indent, ocg, stmts, assigned_on_the_fly, unin, printString); + } + + + + + + CG_outputRepr *CG_loop::printRepr(bool do_print_guard, + int indent, + CG_outputBuilder *ocg, const std::vector &stmts, + const std::vector > &assigned_on_the_fly, + std::vector > > unin, bool printString) const { + fprintf(stderr, "\n*** CG.cc CG_loop printrepr with more arguments\n"); + + + // debugging output + int numfly = assigned_on_the_fly.size(); + fprintf(stderr, "assigned on the fly %d\n", numfly ); // Anand makes twice as many + for (int i=0; ip = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + + //Anand: adding support for Replacing substituted variables within + //Uninterpreted function symbols or global variables with arity > 0 here + //--begin + std::vector > aotf = assigned_on_the_fly; + int stmt_num = -1; + for (int s = 0; s < active_.size(); s++) + if (active_.get(s)) + stmt_num = s; + + assert(stmt_num != -1); + + CG_outputRepr *guardRepr; + if (do_print_guard) + guardRepr = output_guard(ocg, guard_, aotf, unin[stmt_num]); + else + guardRepr = NULL; + + fprintf(stderr, "after guard assigned on the fly %d\n", numfly ); + for (int i=0; ip = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + fprintf(stderr, "done flying\n"); + + Relation cur_known = Intersection(copy(known_), copy(guard_)); + + cur_known.simplify(); + fprintf(stderr, "checking needloop\n"); + if (needLoop_) { + fprintf(stderr, "needLoop_\n"); + + if (checkLoopLevel) + if (level_ == checkLoopLevel) + if (active_.get(stmtForLoopCheck)) + fillInBounds = true; + + fprintf(stderr, "ctrlRepr = output_loop()\n"); + CG_outputRepr *ctrlRepr = output_loop(ocg, bounds_, level_, cur_known, + aotf, unin[stmt_num]); + + fillInBounds = false; + + fprintf(stderr, "in needLoop_ bodyrepr = \n"); + int ind = (guardRepr == NULL) ? indent + 1 : indent + 2; + CG_outputRepr *bodyRepr = body_->printRepr(ind, + ocg, + stmts, + aotf, + unin, + printString); + CG_outputRepr * loopRepr; + + if (guardRepr == NULL) + loopRepr = ocg->CreateLoop(indent, ctrlRepr, bodyRepr); + else + loopRepr = ocg->CreateLoop(indent + 1, ctrlRepr, bodyRepr); + + + if (!smtNonSplitLevels.empty()) { + fprintf(stderr, "!smtNonSplitLevels.empty()\n"); + 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; + + fprintf(stderr, "loopIdxNames.size() %d\n", loopIdxNames.size()); + for (int i=0; iCreateAttribute(loopRepr, buf); + } + + } + if (guardRepr == NULL) + return loopRepr; + else + return ocg->CreateIf(indent, guardRepr, loopRepr, NULL); + } + else { + fprintf(stderr, "NOT needloop_\n"); + + std::pair > result = + output_assignment(ocg, bounds_, level_, cur_known, aotf, unin[stmt_num]); + + //fprintf(stderr, "RESULT 0x%x 0x%x %d\n", result.first, result.second.first, result.second.second ); + + + guardRepr = ocg->CreateAnd(guardRepr, result.first); + //fprintf(stderr, "RESULT 0x%x 0x%x %d\n", result.first, result.second.first, result.second.second ); + + //fprintf(stderr, "after guardRepr assigned on the fly %d\n", numfly ); + for (int i=0; ip = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + + + if (result.second.second < CodeGen::var_substitution_threshold) { + //fprintf(stderr, "var_substitution_threshold %d < %d level_ = %d\n", result.second.second, CodeGen::var_substitution_threshold, level_); + std::vector > aotf = + assigned_on_the_fly; + aotf[level_ - 1] = result.second; + //fprintf(stderr, "RESULT 0x%x second 0x%x %d\n", result.first, result.second.first, result.second.second ); + + if(!printString) { + for (std::map >::iterator i = + unin[stmt_num].begin(); i != unin[stmt_num].end(); i++) { + + + std::vector to_push; + for (int j = 0; j < i->second.size(); j++) { + std::string index = + const_cast(this)->bounds_.set_var(level_)->name(); + std::vector loop_vars; + loop_vars.push_back(index); + std::vector subs; + subs.push_back(result.second.first->clone()); + CG_outputRepr * new_repr = ocg->CreateSubstitutedStmt(0, + i->second[j]->clone(), loop_vars, subs); + to_push.push_back(new_repr); + } + i->second = to_push; + } // for + } // if + + //fprintf(stderr, "aotf !!\n"); + for (int i=0; ip = aotf[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) { tr = p.first->clone(); } + int val = p.second; + } + + //fprintf(stderr, "\nbodyRepr =\n"); + //body_->dump(); // this dies + int ind = (guardRepr == NULL) ? indent : indent + 1; + CG_outputRepr *bodyRepr = body_->printRepr(ind, ocg, stmts, aotf, unin, + printString); + + delete aotf[level_ - 1].first; + if (guardRepr == NULL) + return bodyRepr; + else + return ocg->CreateIf(indent, guardRepr, bodyRepr, NULL); + } else { + //fprintf(stderr, "NOT var_substitution_threshold gonna call output_ident()\n"); + int ind = (guardRepr == NULL) ? indent : indent + 1; + CG_outputRepr *assignRepr = ocg->CreateAssignment( + ind, + output_ident(ocg, bounds_, + const_cast(this)->bounds_.set_var( + level_), aotf, unin[stmt_num]), + result.second.first); + + CG_outputRepr *bodyRepr = body_->printRepr(ind, ocg, stmts, aotf, unin, + printString); + + if (guardRepr == NULL) + return ocg->StmtListAppend(assignRepr, bodyRepr); + else + return ocg->CreateIf(indent, guardRepr, + ocg->StmtListAppend(assignRepr, bodyRepr), NULL); + + /* DEAD CODE + std::pair result_ = find_simplest_assignment( + copy(bounds_), copy(bounds_).set_var(level_), + assigned_on_the_fly); + bool found_func = false; + Variable_ID v2; + int arity; + for (Constr_Vars_Iter cvi(result_.first); cvi; cvi++) + if (cvi.curr_var()->kind() == Global_Var) { + Global_Var_ID g = cvi.curr_var()->get_global_var(); + if ((g->arity() > 0)) { + + found_func = true; + arity = g->arity(); + //copy(R).print(); + v2 = copy(bounds_).get_local(g, + cvi.curr_var()->function_of()); + + break; + } + } + + bool is_array = false; + if (found_func) { + + is_array = ocg->QueryInspectorType( + v2->get_global_var()->base_name()); + + } + if (!found_func || !is_array) { + + CG_outputRepr *assignRepr = ocg->CreateAssignment( + (guardRepr == NULL) ? indent : indent + 1, + output_ident(ocg, bounds_, + const_cast(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); + + } else { + + std::vector index_expr; + + CG_outputRepr* lb = ocg->CreateArrayRefExpression( + v2->get_global_var()->base_name(), + output_ident(ocg, bounds_, + const_cast(this)->bounds_.set_var(2), + assigned_on_the_fly)); + + for (int i = arity; i > 1; i--) { + + index_expr.push_back( + ocg->CreateArrayRefExpression( + v2->get_global_var()->base_name(), + output_ident(ocg, bounds_, + const_cast(this)->bounds_.set_var( + 2 * i), + assigned_on_the_fly))); + + //} + + } + + CG_outputRepr *ub; + if (index_expr.size() > 1) + ub = ocg->CreateInvoke("max", index_expr); + else + ub = index_expr[0]; + CG_outputRepr *le = ocg->CreateMinus(ub, ocg->CreateInt(1)); + CG_outputRepr *inductive = ocg->CreateInductive( + output_ident(ocg, bounds_, + const_cast(this)->bounds_.set_var( + level_), assigned_on_the_fly), lb, le, + NULL); + + CG_outputRepr *bodyRepr = body_->printRepr( + (guardRepr == NULL) ? indent : indent + 1, ocg, stmts, + assigned_on_the_fly); + + if (guardRepr == NULL) { + return ocg->CreateLoop(indent, inductive, bodyRepr); + } else + return ocg->CreateIf(indent, guardRepr, + ocg->CreateLoop(indent + 1, inductive, bodyRepr), + NULL); + } + */ + } + } + } + + +/* +//Protonu--adding a helper function to get the ids of the nested loops +//to help with OpenMP code generation + std::vector get_idxs( CG_result * cgl, std::vector& idxs) + { + CG_loop * _lp; + CG_split *_sp; + + _lp = dynamic_cast(cgl); + _sp = dynamic_cast(cgl); + + if(_lp){ + if (_lp->needLoop_) + idxs.push_back((copy(_lp->bounds_).set_var(_lp->level_))->name()); + if (_lp->depth() > 0 ){ + cgl = _lp->body_; + get_idxs(cgl, idxs); + } + if (_lp->depth() == 0) + return idxs; + } + if(_sp){ + for(int i=0; i<_sp->clauses_.size(); i++) + { + get_idxs(_sp->clauses_[i], idxs); + } + } + + return idxs; + + } +//end. +*/ + + + CG_result *CG_loop::clone() const { + //fprintf(stderr, "CG_loop::clone()\n"); + 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(this)->known_.print(); + std::cout << prefix << "restriction: "; + const_cast(this)->restriction_.print(); + std::cout << prefix << "bounds: "; + const_cast(this)->bounds_.print(); + std::cout << prefix << "guard: "; + const_cast(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_leaf::liftOverhead(int depth, bool) { + if (depth == 0) + return std::make_pair(this, Relation::True(num_level())); + + for (std::map::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 guards; + for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { + std::map::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::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 &stmts, + const std::vector > &assigned_on_the_fly, + std::vector > > unin, + bool printString) const { + fprintf(stderr, "CG_leaf::printRepr()\n"); + int numfly = assigned_on_the_fly.size(); + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + for (int i=0; ip = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + + return leaf_print_repr(active_, guards_, NULL, known_, indent, ocg, + codegen_->remap_, codegen_->xforms_, stmts, + assigned_on_the_fly, unin); + } + + + + CG_result *CG_leaf::clone() const { + //fprintf(stderr, "CG_leaf::clone()\n"); + 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: "; + std::cout.flush(); + const_cast(this)->known_.print(); + for (std::map::const_iterator i = guards_.begin(); + i != guards_.end(); i++) { + std::cout << prefix << "guard #" << i->first << ":"; + const_cast(i->second).print(); + } + } + } diff --git a/lib/codegen/src/CG_stringBuilder.cc b/lib/codegen/src/CG_stringBuilder.cc old mode 100644 new mode 100755 index 2f9286f..d0f6693 --- a/lib/codegen/src/CG_stringBuilder.cc +++ b/lib/codegen/src/CG_stringBuilder.cc @@ -11,7 +11,7 @@ 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 @@ -26,462 +26,641 @@ #include 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 '+': + + 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 (paren_level == 0) - num_plusminus++; + if (num_plusminus > 0) + need_paren = true; break; case '*': - if (paren_level == 0) - num_mul++; + if (num_plusminus > 0 || num_div > 0) + need_paren = true; break; case '/': - if (paren_level == 0) - num_div++; + if (num_plusminus > 0 || num_div > 0 || num_mul > 0) + need_paren = true; 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; } - - if (need_paren) - return "(" + s + ")"; - else - return s; -} - - -std::string GetIndentSpaces(int indent) { - std::string indentStr; - for (int i = 1; i < indent; i++) { - indentStr += " "; + + + std::string GetIndentSpaces(int indent) { + std::string indentStr; + for (int i = 1; i < indent; i++) { + indentStr += " "; + } + return 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(repr)->GetString(); - delete repr; - return result; -} - + + + // 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(repr)->GetString(); + delete repr; + return result; + } + } namespace omega { - - - -//----------------------------------------------------------------------------- -// Class: CG_stringBuilder -//----------------------------------------------------------------------------- - -CG_stringRepr *CG_stringBuilder::CreateSubstitutedStmt(int indent, CG_outputRepr *stmt, - const std::vector &vars, - std::vector &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 &list) const { - std::string listStr = ""; - - for (int i = 0; i < list.size(); i++) { - listStr += GetString(list[i]); - if ( i < list.size()-1) - listStr += ","; + + + + //----------------------------------------------------------------------------- + // Class: CG_stringBuilder + //----------------------------------------------------------------------------- + + CG_stringRepr *CG_stringBuilder::CreateSubstitutedStmt(int indent, + CG_outputRepr *stmt, + const std::vector &vars, + std::vector &subs, + bool actuallyPrint) 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"); } - - return new CG_stringRepr(funcName + "(" + listStr + ")"); -} + + + CG_stringRepr *CG_stringBuilder::CreateStatementFromExpression(CG_outputRepr *exp) const { + std::string expStr = GetString(exp); + return new CG_stringRepr(expStr + ";\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"); - -CG_stringRepr *CG_stringBuilder::CreateComment(int indent, const std::string &commentText) const { - if (commentText == std::string("")) { - return NULL; + 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::CreatePlusAssignment(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::CreateAddressOf(CG_outputRepr *op) const { + if (op == NULL) + throw std::invalid_argument("missining op in create address of"); + + std::string opStr = GetString(op); + + + return new CG_stringRepr( "&" + opStr); + } + + + CG_stringRepr *CG_stringBuilder::CreateInvoke(const std::string &funcName, + std::vector &list, + bool is_array) const { + fprintf(stderr, "CG_stringBuilder::CreateInvoke( %s, ..., is_array ", funcName.c_str()); + if (is_array) fprintf(stderr, " true )\n"); + else fprintf(stderr, " false )\n"); - 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 (control); - } - std::string controlString = GetString(control); + std::string listStr = ""; + + fprintf(stderr, "list has %d elements\n", list.size()); - return new CG_stringRepr("// " + commentText + "\n" + controlString); + for (int i = 0; i < list.size(); i++) { + fprintf(stderr, "accessing list[%d]\n", i); + listStr += GetString(list[i]); + if ( i < list.size()-1) + listStr += ","; + } -} + fprintf(stderr, "returning %s\n", (funcName + "(" + listStr + ")").c_str()); + 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_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::CreateAttribute(CG_outputRepr *control, + const std::string &commentText) const { + + //fprintf(stderr, "CG_stringBuilder::CreateAttribute( jkadskjh, '%s')\n", commentText.c_str()); -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 (commentText == std::string("")) { + return static_cast (control); + } + + std::string controlString = GetString(control); + + std::string spaces = ""; + const char *con = controlString.c_str(); + const char *ptr = con; + while (*ptr++ == ' ') spaces = spaces + " "; + return new CG_stringRepr(spaces + "// " + commentText + "\n" + controlString); + + } - if (true_stmtList == NULL && false_stmtList == NULL) { - delete guardList; - return NULL; + CG_outputRepr* CG_stringBuilder::CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const { + // -- Not Implemented + return scopeStmt; } - - 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"; + + CG_outputRepr* CG_stringBuilder::CreatePrefetchAttribute(CG_outputRepr* scopeStmt, int looplevel, const std::string& arrName, int hint) const { + // -- Not Implemented + return scopeStmt; } - else if (true_stmtList == NULL && false_stmtList != NULL) { - s = indentStr + "if !(" + guardListStr + ") {\n" - + GetString(false_stmtList) - + indentStr + "}\n"; + + + + + CG_stringRepr *CG_stringBuilder::CreateBreakStatement(void) const { + std::string s= "break;\n"; + return new CG_stringRepr(s); + } + + + + 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); } - else { - s = indentStr + "if (" + guardListStr + ") {\n" - + GetString(true_stmtList) - + indentStr + "}\n" - + indentStr + "else {\n" - + GetString(false_stmtList) + + + + 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; + + if (step != NULL) { + std::string stepStr = GetString(step); + if (stepStr == to_string(1)) + doStr += "++"; + else + doStr += " += " + stepStr; + } + else + doStr += "++"; // a default ?? + 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(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); } - 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(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; + + + CG_stringRepr *CG_stringBuilder::CreateInt(int num) const { + std::string s = to_string(num); + return new CG_stringRepr(s); } - - return new CG_stringRepr(varName); -} - - -CG_stringRepr *CG_stringBuilder::CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) { - return static_cast(lop); + + CG_stringRepr *CG_stringBuilder::CreateFloat(float num) const { + std::string s = to_string(num); + return new CG_stringRepr(s); } - else if (lop == NULL) { - return static_cast(rop); + + CG_stringRepr *CG_stringBuilder::CreateDouble(double num) const { + std::string s = to_string(num); + return new CG_stringRepr(s); } - - 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(lop); + + + + 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; + } + + bool CG_stringBuilder::QueryInspectorType(const std::string &varName) const{ + if (varName == std::string("index")) { // special cased? ?????? TODO + return true; + } + return false; + } + + CG_stringRepr* CG_stringBuilder::ObtainInspectorData(const std::string &_s, const std::string &member_name) const { + return new CG_stringRepr(_s); + } + + + + 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::CreateDotExpression(CG_outputRepr *lop, + CG_outputRepr *rop) const { + + std::string op1 = GetString(lop); + std::string op2 = GetString(rop); + + std::string s = op1 + "." + op2; + return new CG_stringRepr(s); + } + + + + CG_stringRepr* CG_stringBuilder::CreateNullStatement() const{ + return new CG_stringRepr(""); + } + + + + CG_stringRepr* CG_stringBuilder::CreateArrayRefExpression(const std::string &_s, + CG_outputRepr *rop) const { + if (_s == std::string("")) { + return NULL; + } + + std::string refStr = GetString(rop); + //std::string s = _s + "[" + refStr + "]"; + + return new CG_stringRepr( _s + "[" + refStr + "]"); } - else if (lop == NULL) { + + + + CG_stringRepr* CG_stringBuilder::CreateArrayRefExpression(CG_outputRepr *lop, + CG_outputRepr *rop) const { + + std::string refStr1 = GetString(lop); + std::string refStr2 = GetString(rop); + //std::string s = _s + "[" + refStr + "]"; + + return new CG_stringRepr( refStr1 + "[" + refStr2 + "]"); + + } + + + + CG_stringRepr *CG_stringBuilder::CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL) { + return static_cast(lop); + } + else if (lop == NULL) { + return static_cast(rop); + } + + std::string lopStr = GetString(lop); std::string ropStr = GetString(rop); - return new CG_stringRepr("-" + SafeguardString(ropStr, '-')); + + return new CG_stringRepr(lopStr + "+" + 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; + + + CG_stringRepr *CG_stringBuilder::CreateMinus(CG_outputRepr *lop, CG_outputRepr *rop) const { + if (rop == NULL) { + return static_cast(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, '-')); } - - 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; + + + 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, '*')); } - - 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; + + + 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, '/')); } - - 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; + + + 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 + ")"); } - - 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; + + + 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 + ")"); } - - 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(lop); - else if (lop == NULL) - return static_cast(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(list1); + + 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(lop); + else if (lop == NULL) + return static_cast(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::CreateNEQ(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(list1); + } + else if (list1 == NULL) { + return static_cast(list2); + } + + std::string list1Str = GetString(list1); + std::string list2Str = GetString(list2); + + return new CG_stringRepr(list1Str + list2Str); } - else if (list1 == NULL) { - return static_cast(list2); + + CG_outputRepr *CG_stringBuilder::CreateStruct(const std::string struct_name, + std::vector data_members, + std::vector data_types) + { + fprintf(stderr, "CG_stringBuilder::CreateStruct( %s )\n", struct_name.c_str()); + fprintf(stderr, "that makes no sense\n"); + exit(0); + } + + CG_outputRepr *CG_stringBuilder::CreateClassInstance(std::string name , + CG_outputRepr *class_def){ + fprintf(stderr, "CG_stringBuilder::CreateClassInstance( %s )\n", name.c_str()); + exit(0); + + } + + CG_outputRepr *CG_stringBuilder::lookup_member_data(CG_outputRepr* scope, + std::string varName, + CG_outputRepr *instance) { + fprintf(stderr, "CG_stringBuilder::lookup_member_data( )\n"); + exit(0); + } + + CG_outputRepr* CG_stringBuilder::CreatePointer(std::string &name) const { + fprintf(stderr, "CG_chillBuilder::CreatePointer( %s )\n", name.c_str()); + exit(0); } - std::string list1Str = GetString(list1); - std::string list2Str = GetString(list2); + CG_outputRepr* CG_stringBuilder::ObtainInspectorRange(const std::string &_s, const std::string &_name) const { + fprintf(stderr, "CG_stringBuilder::ObtainInspectorRange(%s, %s )\n", _s.c_str(), _name.c_str()); + exit(0); + } - return new CG_stringRepr(list1Str + list2Str); -} + } diff --git a/lib/codegen/src/CG_stringRepr.cc b/lib/codegen/src/CG_stringRepr.cc new file mode 100755 index 0000000..f1a7cad --- /dev/null +++ b/lib/codegen/src/CG_stringRepr.cc @@ -0,0 +1,32 @@ +/***************************************************************************** + Copyright (C) 1994-2000 University of Maryland + Copyright (C) 2008 University of Southern California + Copyright (C) 2009 University of Utah + All Rights Reserved. + + Purpose: + omega holder for string implementation. + + Notes: + + History: + 04/17/96 - Lei Zhou - created +*****************************************************************************/ + + +#include +#include +#include + +namespace omega { + + //----------------------------------------------------------------------------- + // Dump operations + //----------------------------------------------------------------------------- + void CG_stringRepr::Dump() const { dump(); } // TODO combine dump() and Dump() + + void CG_stringRepr::DumpToFile(FILE *fp) const { + fprintf(fp,"%s", s_.c_str()); + } + +} // namespace diff --git a/lib/codegen/src/CG_utils.cc b/lib/codegen/src/CG_utils.cc index d3a5f71..19bb6c9 100755 --- a/lib/codegen/src/CG_utils.cc +++ b/lib/codegen/src/CG_utils.cc @@ -7,7 +7,7 @@ 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 @@ -24,309 +24,456 @@ #include namespace omega { - -int checkLoopLevel; -int stmtForLoopCheck; -int upperBoundForLevel; -int lowerBoundForLevel; -bool fillInBounds; - + + 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 &guards) { - std::pair best_cost = std::make_pair(0, 0); - Relation best_cond = Relation::True(R.n_set()); + class JunkStaticInit{ + public: + JunkStaticInit(){ checkLoopLevel=0; fillInBounds=false;} + }; + static JunkStaticInit junkInitInstance__; - 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 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::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 &loops, int start, int end) { - std::pair 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 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 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 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()); + namespace { + + Relation find_best_guard(const Relation &R, const BoolSet<> &active, const std::map &guards) { + std::pair 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 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::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) { + //Relation s = copy(R); + //s.simplify(2,4); + //return s; + throw codegen_error("guard condition too complex to handle"); + } + + iter_count++; } - 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; + + return best_cond; } - default: - assert(false); + + + Relation find_best_guard(const Relation &R, const std::vector &loops, int start, int end) { + std::pair 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 cost = std::make_pair(0, 0); + + // was Relation cond = pick_one_guard(r); + Relation cond = pick_one_guard(r,loops[start]->level_); + 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; } + } - 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 exists_mapping3; - EQ_Handle h3 = f_root3->add_EQ(); - for (Constr_Vars_Iter cvi(stride_eq); cvi; cvi++) { - Variable_ID v= cvi.curr_var(); + + 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 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 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: - h3.update_coef(r3.input_var(v->get_position()), cvi.curr_coef()); + 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: { + 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()); + Variable_ID v1, v2; + if (g->arity() == 0) { + v1 = r1.get_local(g); + v2 = r2.get_local(g); + } else { - Variable_ID v3 = replicate_floor_definition(bounds, v, r3, f_exists3, f_root3, exists_mapping3); - h3.update_coef(v3, cvi.curr_coef()); + 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); } } - h3.update_const(stride_eq.get_const()); - r3.simplify(); + h1.update_const(inequality.get_const()); + h1.update_coef(f_exists1->declare(), stride); + h2.update_const(inequality.get_const()); + r1.simplify(); + r2.simplify(); - if (Gist(r3, Intersection(r2, all_known), 1).is_obvious_tautology()) - return true; - else + 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 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; + } } - 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 > &assigned_on_the_fly) { - const_cast(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 argList; - for(int i = 1; i <= arity; i++) - argList.push_back(ocg->CreateIdent(const_cast(R).input_var(i)->name())); - CG_outputRepr *call = ocg->CreateInvoke(v->get_global_var()->base_name(), argList); - return call; + CG_outputRepr *output_ident(CG_outputBuilder *ocg, + const Relation &R, + Variable_ID v, + const std::vector > &assigned_on_the_fly, + std::map > unin) { + fprintf(stderr, "output_ident( %s )\n", v->name().c_str()); + + const_cast(R).setup_names(); // hack + + if (v->kind() == Input_Var) { + int pos = v->get_position(); + if (assigned_on_the_fly[pos - 1].first != NULL) { + //fprintf(stderr, "on the fly pos=%d\n", pos); + CG_outputRepr *tmp = assigned_on_the_fly[pos-1].first->clone(); + //fprintf(stderr, "tmp on the fly (0x%x)\n", tmp); + return tmp; + } + else { + //fprintf(stderr, "creating Ident for %s\n", v->name().c_str()); + CG_outputRepr *tmp = ocg->CreateIdent(v->name()); + //fprintf(stderr, "ident created for %s\n", v->name().c_str()); + return tmp; + } + } + else if (v->kind() == Global_Var) { + //fprintf(stderr, "CG_utils.cc output_ident() Global_Var\n"); + if (v->get_global_var()->arity() == 0) { + //fprintf(stderr, "arity 0\n"); + 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(); + //fprintf(stderr, "arity %dn", arity ); + std::vector argList; + if (unin.find(v->get_global_var()->base_name()) != unin.end()) { + + std::vector argList_ = unin.find( + v->get_global_var()->base_name())->second; + + for (int l = 0; l < argList_.size(); l++) + argList.push_back(argList_[l]->clone()); + + } + else { + for (int i = 1; i <= arity; i++) { + + /* + */ + if (assigned_on_the_fly.size() > (R.n_inp() + i - 1)) { + if (assigned_on_the_fly[R.n_inp() + i - 1].first != NULL) + argList.push_back( + assigned_on_the_fly[R.n_inp() + i - 1].first->clone()); + else + argList.push_back( + ocg->CreateIdent( + const_cast(R).input_var( + 2 * i)->name())); + } else + argList.push_back( + ocg->CreateIdent( + const_cast(R).input_var( + 2 * i)->name())); + + /*if (assigned_on_the_fly[2*i - 1].first == NULL) + argList.push_back( + ocg->CreateIdent( + const_cast(R).input_var(2 * i)->name())); + else + argList.push_back(assigned_on_the_fly[2*i - 1].first->clone()); + */ + } + } + CG_outputRepr *call = ocg->CreateInvoke( + v->get_global_var()->base_name(), argList); + return call; + } } + else + assert(false); } - else - assert(false); -} - + + // // return pair > // -std::pair > output_assignment(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector > &assigned_on_the_fly) { - Variable_ID v = const_cast(R).set_var(level); - Conjunct *c = const_cast(R).single_conjunct(); - - std::pair result = find_simplest_assignment(R, v, assigned_on_the_fly); - - if (result.second == INT_MAX) - return std::make_pair(static_cast(NULL), std::make_pair(static_cast(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 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::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; + std::pair > output_assignment( + CG_outputBuilder *ocg, const Relation &R, int level, + const Relation &known, + const std::vector > &assigned_on_the_fly, + std::map > unin) { + + //fprintf(stderr, "output_assignment( )\n"); + int numfly = assigned_on_the_fly.size(); + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + for (int i=0; ip = assigned_on_the_fly[i]; + CG_outputRepr *tr = NULL; + if (p.first != NULL) tr = p.first->clone(); + int val = p.second; + //fprintf(stderr, "0x%x %d\n", tr, val); + } + + + Variable_ID v = const_cast(R).set_var(level); + Conjunct *c = const_cast(R).single_conjunct(); + + std::pair result = find_simplest_assignment(R, v, assigned_on_the_fly); + + if (result.second == INT_MAX) + return std::make_pair(static_cast(NULL), std::make_pair(static_cast(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 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; } - else - v2 = p->second; - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(0); - } - h.update_const(result.first.get_const()); + 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::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 (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::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: { - assert(cvi.curr_var() != v); h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef()); break; } @@ -357,1379 +504,2303 @@ std::pair > output_assignment(C } 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::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)))); + 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, unin); + 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, unin); + } } - 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, unin); + } + + if (assign_repr == NULL) { + assign_repr = ocg->CreateInt(0); + } + + //fprintf(stderr, "assigned on the fly %d\n", numfly ); + //for (int i=0; ip = assigned_on_the_fly[i]; + // CG_outputRepr *tr = NULL; + // if (p.first != NULL) tr = p.first->clone(); + // int val = p.second; + // //fprintf(stderr, "0x%x %d\n", tr, val); + //} + + return std::make_pair(if_repr, std::make_pair(assign_repr, result.second)); } - 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 > &assigned_on_the_fly) { - const_cast(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 result = find_floor_definition(R, cvi.curr_var()); - if (!result.first) { - delete repr; - throw codegen_error("can't output non floor defined wildcard"); + 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 > &assigned_on_the_fly, + std::map > unin) { + //fprintf(stderr, "output_substitution_repr( v = '%s' )\n", v->char_name()); + const_cast(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) { + //fprintf(stderr, "cvi\n"); + CG_outputRepr *t; + if (cvi.curr_var()->kind() == Wildcard_Var) { + std::pair 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, unin); } - 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 { + //fprintf(stderr, "else t = output_ident()\n"); + t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly, unin); + //if (t== NULL) fprintf(stderr, "t NULL\n"); } - 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)); + coef_t coef = cvi.curr_coef(); + //fprintf(stderr, "coef %d\n", coef); + + //fprintf(stderr, "a %d\n", a); + 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) { + //fprintf(stderr, "repr = ocg->CreatePlus(repr, t);\n"); + repr = ocg->CreatePlus(repr, t); + //if (repr == NULL) fprintf(stderr, "repr NULL\n"); + //else fprintf(stderr, "repr NOT NULL\n"); + } + 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)); + } } - else { // coef < 0 - if (coef == -1) - repr = ocg->CreateMinus(repr, t); - else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); - } + } + + //if (repr == NULL) fprintf(stderr, "before inequality, repr == NULL\n"); + 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)); } } - - 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; -} - - + if (apply_v_coef && abs(a) != 1) + repr = ocg->CreateDivide(repr, ocg->CreateInt(abs(a))); + + //if (repr == NULL) fprintf(stderr, "at end, repr == NULL\n"); + //fprintf(stderr, "leaving output_substitution_repr()\n"); + return repr; + } + + // // original Substitutions class from omega can't handle integer // division, this is new way. // -std::vector output_substitutions(CG_outputBuilder *ocg, const Relation &R, const std::vector > &assigned_on_the_fly) { - std::vector 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 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 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 &) { - } + std::vector output_substitutions(CG_outputBuilder *ocg, + const Relation &R, + const std::vector > &assigned_on_the_fly, + std::map > unin) { + std::vector subs; + + fprintf(stderr, "CG_utils.cc output_substitutions()\n"); + + 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; + + fprintf(stderr, "v %s\n", v->char_name()); + std::pair result = find_simplest_assignment(r, v, assigned_on_the_fly); + if (result.second < INT_MAX) { + //fprintf(stderr, "output_substitutions() calling output_substitution_repr()\n"); + repr = output_substitution_repr(ocg, result.first, v, true, r, + assigned_on_the_fly, unin); + if (repr == NULL) fprintf(stderr, "IN IF, repr for %s assigned NULL\n", v->char_name()); + } + else { + //fprintf(stderr, "else\n"); + std::pair result = find_floor_definition(R, v); + if (result.first) + try { + repr = output_inequality_repr(ocg, result.second, v, R, + assigned_on_the_fly, unin); + } + catch (const codegen_error &) { + } + } + + if (repr == NULL) fprintf(stderr, "repr NULL\n"); + if (repr != NULL) { + subs.push_back(repr); + } + else { + //Anand:Add additional checks for variables that have been mapped to inspector/global variables + for (int k = 1; k <= R.n_out(); k++) { + //Relation mapping1(mapping.n_out(), 1); + //F_And *f_root = mapping1.add_and(); + //EQ_Handle h = f_root->add_EQ(); + //h.update_coef(mapping1.output_var(1), 1); + //h.update_coef(mapping1.input_var(i), -1); + //Relation r = Composition(mapping1, copy(mapping)); + //r.simplify(); + + Relation r = copy(R); + + Variable_ID v = r.output_var(k); + CG_outputRepr* inspector = NULL; + bool has_insp = false; + Global_Var_ID global_insp; + + std::pair result = find_simplest_assignment( + copy(r), v, assigned_on_the_fly); + CG_outputRepr *repr_ = NULL; + if (result.second < INT_MAX) { + /*std::vector variables; + //Anand: commenting this out as well : 05/29/2013 + variables.push_back(r.input_var(2 * k)); + for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { + Variable_ID v1 = cvi.curr_var(); + if (v1->kind() == Input_Var) + variables.push_back(v1); + + } + */ + repr_ = output_substitution_repr(ocg, result.first, v, true, + copy(r), assigned_on_the_fly, unin); + + for (DNF_Iterator di(copy(r).query_DNF()); di; di++) + for (GEQ_Iterator ci = (*di)->GEQs(); ci; ci++) { + + //Anand: temporarily commenting this out as it causes problems 5/28/2013 + /*int j; + for (j = 0; j < variables.size(); j++) + if ((*ci).get_coef(variables[j]) == 0) + break; + if (j != variables.size()) + continue; + */ + for (Constr_Vars_Iter cvi(*ci); cvi; cvi++) { + Variable_ID v1 = cvi.curr_var(); + if (v1->kind() == Global_Var) + if (v1->get_global_var()->arity() > 0) { + + if (i + <= v1->get_global_var()->arity()) { + + /* std::pair result = + find_simplest_assignment( + copy(r), v, + assigned_on_the_fly); + + if (result.second < INT_MAX) { + CG_outputRepr *repr = + output_substitution_repr( + ocg, + result.first, v, + true, copy(r), + assigned_on_the_fly); + + inspector = + ocg->CreateArrayRefExpression( + ocg->CreateDotExpression( + ocg->ObtainInspectorData( + v1->get_global_var()->base_name()), + ocg->CreateIdent( + copy( + R).output_var( + i)->name())), + repr); + } else + */ + inspector = + /* ocg->CreateArrayRefExpression( + ocg->CreateDotExpression( + ocg->ObtainInspectorData( + v1->get_global_var()->base_name()), + ocg->CreateIdent( + copy( + R).output_var( + i)->name())), + repr);*/ + + ocg->CreateArrayRefExpression( + + ocg->ObtainInspectorData( + v1->get_global_var()->base_name(), + + copy(R).output_var( + i)->name()), + repr_); + //ocg->CreateIdent( + // v->name())); + + } + } + + } + } + } + + if (inspector != NULL) { + subs.push_back(inspector); + break; + } else if (k == i && repr_ != NULL) { + subs.push_back(repr_); + + } + + //std::pair result = find_simplest_assignment(r, + // v, assigned_on_the_fly, &has_insp); + + /*if (has_insp) { + + bool found_insp = false; + //Anand: check if inspector constraint present in equality + for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); + if (v->kind() == Global_Var) + if (v->get_global_var()->arity() > 0) { + global_insp = v->get_global_var(); + found_insp = true; + } + + } + if (found_insp) + if (i <= global_insp->arity()) + inspector = + ocg->CreateArrayRefExpression( + ocg->CreateDotExpression( + ocg->ObtainInspectorData( + global_insp->base_name()), + ocg->CreateIdent( + copy(R).output_var( + i)->name())), + ocg->CreateIdent(v->name())); + + + } + */ + } // for int k + } } - - subs.push_back(repr); - } - - return subs; -} - + fprintf(stderr, "CG_utils.cc output_substitutions() DONE\n\n"); + return subs; + } + + // // handle floor definition wildcards in equality, the second in returned pair // is the cost. // -std::pair find_simplest_assignment(const Relation &R, Variable_ID v, const std::vector > &assigned_on_the_fly) { - Conjunct *c = const_cast(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) { + std::pair find_simplest_assignment(const Relation &R, + Variable_ID v, + const std::vector > &assigned_on_the_fly, + bool *found_inspector_global) { + Conjunct *c = const_cast(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) { + //Anand --start: Check for Global Variable not being involved in any GEQ + Conjunct *d = + const_cast(R).single_conjunct(); + bool found = false; + for (GEQ_Iterator g(d->GEQs()); g; g++) + if ((*g).get_coef(v) != 0) { + found = true; + break; + } + if (!found) + cost += 10; // function cost + else { + cost = INT_MAX; + eq = *e; + if (found_inspector_global != NULL) + *found_inspector_global = true; + return std::make_pair(eq, cost); + } //Anand --end: Check for Global Variable not being involved in any GEQ + } + 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 (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 (num_var > 1) + cost += num_var - 1; // addition cost + + if (cost < min_cost) { + min_cost = cost; + eq = *e; + if (found_inspector_global != NULL) + *found_inspector_global = true; } - 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 result = find_floor_definition(R, v); - if (!result.first) { - is_assignment = false; - break; + 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 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) { + 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 (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 (num_var > 1) + cost += num_var - 1; // addition cost + + if (cost < min_cost) { + min_cost = cost; + eq = *e; + if (found_inspector_global != NULL) + *found_inspector_global = true; } - 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); -} - - + + 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 find_floor_definition(const Relation &R, Variable_ID v, std::set excluded_floor_vars) { - Conjunct *c = const_cast(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::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 result = find_floor_definition(R, cvi.curr_var(), excluded_floor_vars); - if (!result.first) { - has_undefined_wc = true; + std::pair find_floor_definition(const Relation &R, + Variable_ID v, + std::set excluded_floor_vars) { + Conjunct *c = const_cast(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::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 (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; + 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 result = find_floor_definition(R, + cvi.curr_var(), + excluded_floor_vars); + if (!result.first) { + has_undefined_wc = true; break; } - if (!match) - continue; - for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) - if ((*e).get_coef(cvi.curr_var()) != -cvi.curr_coef()) { - match = false; + } + 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()); + } + + //Anand- adding the following just for debug + std::vector > find_floor_definition_temp( + const Relation &R, Variable_ID v, + std::set excluded_floor_vars) { + Conjunct *c = const_cast(R).single_conjunct(); + std::vector > to_return; + 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; + + //Anand: commenting out the following for debug 7/28/2013 + bool interested = true; + Variable_ID possibly_interfering; + for (std::set::const_iterator i = + excluded_floor_vars.begin(); i != excluded_floor_vars.end(); + i++) + if ((*i) != v && (*e).get_coef(*i) != 0) { + possibly_interfering = *i; + interested = false; + break; + } + + // 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 result = find_floor_definition(R, + cvi.curr_var(), excluded_floor_vars); + if (!result.first) { + has_undefined_wc = true; break; } - if (match) - return std::make_pair(true, *e); - } + } + 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 (v == cvi.curr_var() + && (*e2).get_coef(cvi.curr_var()) + != -cvi.curr_coef()) { + match = false; + break; + } + if (!match) + continue; + for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) + if (v == cvi.curr_var() + && (*e).get_coef(cvi.curr_var()) + != -cvi.curr_coef()) { + match = false; + break; + } + if (match) { + to_return.push_back(std::make_pair(true, *e)); + if (!interested) + to_return.push_back(std::make_pair(true, *e2)); + return to_return; + + } + } + } + + to_return.push_back(std::make_pair(false, GEQ_Handle())); + + return to_return; } - 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 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(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(R).single_conjunct()->GEQs()); e2; e2++) - if ((*e2).get_coef(cvi.curr_var()) != 0) { - is_free = false; - break; + std::pair 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(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(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(); + } } - if (is_free) { - if (found_free) - is_stride = false; else { - found_free = true; - stride_wc = cvi.curr_var(); + std::pair result = find_floor_definition(R, cvi.curr_var()); + if (result.first) + num_floor++; + else + is_stride = false; } + break; } - else { - std::pair result = find_floor_definition(R, cvi.curr_var()); - if (result.first) - num_floor++; - else - is_stride = false; + case Input_Var: + num_var++; + break; + default: + ; } - break; - } - case Input_Var: - num_var++; - break; - default: - ; + + if (!is_stride) + break; } - 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 (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(NULL)); -} - + + if (best_num_var != INT_MAX) + return std::make_pair(best_eq, best_stride_wc); + else + return std::make_pair(EQ_Handle(), static_cast(NULL)); + } + // // convert relation to if-condition // -CG_outputRepr *output_guard(CG_outputBuilder *ocg, const Relation &R, const std::vector > &assigned_on_the_fly) { - assert(R.n_out()==0); - - CG_outputRepr *result = NULL; - Conjunct *c = const_cast(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)); + CG_outputRepr *output_guard(CG_outputBuilder *ocg, + const Relation &R, + const std::vector > &assigned_on_the_fly, + std::map > unin) { + fprintf(stderr, "output_guard()\n"); + assert(R.n_out()==0); + + CG_outputRepr *result = NULL; + Conjunct *c = const_cast(R).single_conjunct(); + + // e.g. 4i=5*j + for (EQ_Iterator e = c->EQs(); e; e++) + if (!(*e).has_wildcards()) { + //fprintf(stderr, "EQ\n"); + 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, unin); + 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)); + } } - 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); } - 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)); + + // e.g. i>5j + for (GEQ_Iterator e = c->GEQs(); e; e++) + if (!(*e).has_wildcards()) { + //fprintf(stderr, "GEQ\n"); + 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, + unin); + 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); + } + //fprintf(stderr, "result = ocg->CreateAnd(result, term);\n"); + result = ocg->CreateAnd(result, term); } - 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(); + + // e.g. 4i=5j+4alpha + for (EQ_Iterator e = c->EQs(); e; e++) + if ((*e).has_wildcards()) { + //fprintf(stderr, "EQ ??\n"); + 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, unin); + 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 (cvi.curr_coef() > 0) - num_positive++; - else - num_negative++; + 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); } - - 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(); + + // e.g. 4alpha<=i<=5alpha + for (GEQ_Iterator e = c->GEQs(); e; e++) + if ((*e).has_wildcards()) { + //fprintf(stderr, "GEQ ??\n"); + 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) { - 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)); - } + lb = (*e); + ub = (*e2); } else { - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreateMinus(lhs, v); - else - lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); + 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, unin); + 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)); + } } - 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, unin); + 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); } } - 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); - } + + //fprintf(stderr, "output_guard returning at bottom 0x%x\n", result); + 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 > &assigned_on_the_fly, + std::map > unin, + std::set excluded_floor_vars) { + fprintf(stderr, "output_inequality_repr() v %s\n", v->name().c_str()); + + const_cast(R).setup_names(); // hack + + coef_t a = inequality.get_coef(v); + assert(a != 0); + excluded_floor_vars.insert(v); + + std::vector > result2; + 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 result = find_floor_definition(R, + cvi.curr_var(), + excluded_floor_vars); + if (!result.first) { + fprintf(stderr, "\n\n*** heading into NEW CODE\n"); + + coef_t coef_ = cvi.curr_coef(); + result2 = find_floor_definition_temp(R, cvi.curr_var(), + excluded_floor_vars); + + for (Constr_Vars_Iter cvi_( + result2[result2.size() - 1].second); cvi_; cvi_++) { + if (cvi_.curr_var()->kind() != Wildcard_Var + && cvi_.curr_var()->kind() != Set_Var) { + t = output_ident(ocg, R, cvi_.curr_var(), + assigned_on_the_fly, unin); + coef_t coef2 = cvi_.curr_coef(); + assert(cvi_.curr_coef() == -1 && a == 1); + repr = ocg->CreateIntegerFloor(t, + ocg->CreateInt(-coef_)); + repr = ocg->CreateTimes(ocg->CreateInt(-coef_), + repr); + + fprintf(stderr, "returning a TIMES\n"); + return repr; + + } + + } + + }; - // 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; + 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, + unin, + excluded_floor_vars); + } + catch (const std::exception &e) { + delete repr; + throw e; + } } 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); + t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly, unin); + + 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 { - 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)); - } + if (coef > 0) { + if (coef == 1) + repr = ocg->CreatePlus(repr, t); + else + repr = ocg->CreatePlus(repr, + ocg->CreateTimes(ocg->CreateInt(coef),t)); } - 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)); - } + else { + if (coef == -1) + repr = ocg->CreateMinus(repr, t); + else + repr = ocg->CreateMinus(repr, + ocg->CreateTimes(ocg->CreateInt(-coef),t)); } - 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); + } } + 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)); + } + - return result; -} - - // -// return NULL if 0 +// nothing special, just an alias // -CG_outputRepr *output_inequality_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector > &assigned_on_the_fly, std::set excluded_floor_vars) { - const_cast(R).setup_names(); // hack + CG_outputRepr *output_upper_bound_repr(CG_outputBuilder *ocg, + const GEQ_Handle &inequality, + Variable_ID v, + const Relation &R, + const std::vector > &assigned_on_the_fly, + std::map > unin) { + assert(inequality.get_coef(v) < 0); + CG_outputRepr* zero_; + + zero_ = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly, + unin); + + if(!zero_) + zero_ = ocg->CreateInt(0); + + return zero_; + } - 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 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; - } +// +// 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 > &assigned_on_the_fly, + std::map > unin) { + + fprintf(stderr, "output_lower_bound_repr()\n"); + 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, unin); + 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,unin); + else if (v2->kind() == Wildcard_Var) { + std::pair result = find_floor_definition(R, v2); + assert(result.first); + v_repr = output_inequality_repr(ocg, result.second, v2, R, + assigned_on_the_fly, unin); } - else - t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - + coef_t coef = cvi.curr_coef(); - if (a > 0) { + if (sign < 0) { if (coef > 0) { if (coef == 1) - repr = ocg->CreateMinus(repr, t); + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr); else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, + ocg->CreateTimes(ocg->CreateInt(coef), v_repr)); } - else { + else { // coef < 0 if (coef == -1) - repr = ocg->CreatePlus(repr, t); + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr); else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, + ocg->CreateTimes(ocg->CreateInt(-coef), v_repr)); } } else { if (coef > 0) { if (coef == 1) - repr = ocg->CreatePlus(repr, t); + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr); else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, + ocg->CreateTimes(ocg->CreateInt(coef), v_repr)); } - else { + else { // coef < 0 if (coef == -1) - repr = ocg->CreateMinus(repr, t); + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr); else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, + ocg->CreateTimes(ocg->CreateInt(-coef), v_repr)); } } + } + coef_t c = stride_eq.get_const(); + fprintf(stderr, "stride eq const %d\n", c); + fprintf(stderr, "sign %d\n", sign ); + if (c > 0) { + if (sign < 0) + strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateInt(c)); + else + strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateInt(c)); } - 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)); - } + 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, unin); + //fprintf(stderr, "inequality repr %p\n", repr); + CG_outputRepr *repr2 = ocg->CreateCopy(repr); + + fprintf(stderr, "stride_eq.get_coef(wc) %d\n", stride_eq.get_coef(wc)); + fprintf(stderr, "repr + mod( strideBoundRepr - repr, %d )\n", stride_eq.get_coef(wc)); - if (abs(a) == 1) + repr = ocg->CreatePlus(repr2, + ocg->CreateIntegerMod(ocg->CreateMinus(strideBoundRepr, repr), + ocg->CreateInt(abs(stride_eq.get_coef(wc))))); + 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 +// return loop control structure only // -CG_outputRepr *output_upper_bound_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector > &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); + CG_outputRepr *output_loop(CG_outputBuilder *ocg, + const Relation &R, + int level, + const Relation &known, + const std::vector > &assigned_on_the_fly, + std::map > unin) { + + fprintf(stderr, "CG_utils.cc output_loop()\n"); + std::pair result = find_simplest_stride(R, const_cast(R).set_var(level)); + fprintf(stderr, "found stride\n"); - if(!zero_) - zero_ = ocg->CreateInt(0); + if (result.second != NULL) + assert(abs(result.first.get_coef(const_cast(R).set_var(level))) == 1); + + std::vector lbList, ubList; + try { + + coef_t const_lb = negInfinity, const_ub = posInfinity; + + for (GEQ_Iterator e(const_cast(R).single_conjunct()->GEQs()); + e; + e++) { + fprintf(stderr, "new e\n"); + coef_t coef = (*e).get_coef(const_cast(R).set_var(level)); + + fprintf(stderr, "coef %d\n", coef); + if (coef > 0) { + CG_outputRepr *repr = output_lower_bound_repr(ocg, *e, const_cast(R).set_var(level), result.first, result.second, R, known, assigned_on_the_fly, unin); + fprintf(stderr, "got a repr\n"); + if (repr == NULL) fprintf(stderr, "repr NULL\n"); - return zero_; + if (repr == NULL) + repr = ocg->CreateInt(0); + lbList.push_back(repr); + + if ((*e).is_const(const_cast(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(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(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(R).set_var(level), + R, + assigned_on_the_fly, + unin); + if (repr == NULL) + repr = ocg->CreateInt(0); + ubList.push_back(repr); + + if ((*e).is_const(const_cast(R).set_var(level))) { + // no variables but v in constraint + set_min(const_ub,-(*e).get_const()/(*e).get_coef(const_cast(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) { + fprintf(stderr, "CG_utils.cc output_loop() createInvoke( max )\n"); + lbRepr = ocg->CreateInvoke("max", lbList); + } + else { // (lbList.size() == 1) + lbRepr = lbList[0]; + } -} + CG_outputRepr *ubRepr = NULL; + if (ubList.size() > 1) { + fprintf(stderr, "CG_utils.cc output_loop() createInvoke( min )\n"); + 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(R).set_var(level), + assigned_on_the_fly, + unin); + //fprintf(stderr,"CG_utils.cc output_loop() returning CreateInductive()\n"); + 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 &exists_mapping) { + //Anand: commenting the assertion out 8/4/2013 + //assert(R.n_out() == 0 && r.n_out() == 0 && R.n_inp() == r.n_inp()); + bool is_mapping = false; + if (r.n_out() > 0) + is_mapping = true; + + std::set excluded_floor_vars; + std::set excluded_floor_vars2; + std::stack 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 result = find_floor_definition(R, v, + excluded_floor_vars); + std::vector > result2; + + if (!result.first) { + + result2 = find_floor_definition_temp(R, v, excluded_floor_vars2); + assert(result2.size() >= 1); + result = result2[0]; + } + else + result2.push_back(result); + assert(result.first); + excluded_floor_vars.insert(v); + excluded_floor_vars2.insert(v); + + for (int i = 0; i < result2.size(); i++) { + GEQ_Handle h1 = f_root->add_GEQ(); + GEQ_Handle h2 = f_root->add_GEQ(); + for (Constr_Vars_Iter cvi(result2[i].second); cvi; cvi++) { + Variable_ID v2 = cvi.curr_var(); + switch (v2->kind()) { + case Input_Var: { + int pos = v2->get_position(); + if (!is_mapping) { + h1.update_coef(r.input_var(pos), cvi.curr_coef()); + h2.update_coef(r.input_var(pos), -cvi.curr_coef()); + } + else { + h1.update_coef(r.output_var(pos), cvi.curr_coef()); + h2.update_coef(r.output_var(pos), -cvi.curr_coef()); + } + break; + } + case Wildcard_Var: { + std::map::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(result2[i].second.get_const()); + h2.update_const( + -result2[i].second.get_const() + - result2[i].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); + } + + // -// output lower bound with respect to lattice +// pick one guard condition from relation. it can involve multiple +// constraints when involving wildcards, as long as its complement +// is a single conjunct. // -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 > &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_; + Relation pick_one_guard(const Relation &R, int level) { + //fprintf(stderr, "pick_one_guard()\n"); + assert(R.n_out()==0); + + Relation r = Relation::True(R.n_set()); + + for (GEQ_Iterator e(const_cast(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(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(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(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; + } + } + } + } } - 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 result = find_floor_definition(R, v2); - assert(result.first); - v_repr = output_inequality_repr(ocg, result.second, v2, R, assigned_on_the_fly); + + +// +// heavy lifting for code output for one leaf node +// + CG_outputRepr *leaf_print_repr(BoolSet<> active, + const std::map &guards, + CG_outputRepr *guard_repr, + const Relation &known, + int indent, + CG_outputBuilder *ocg, + const std::vector &remap, + const std::vector &xforms, + const std::vector &stmts, + const std::vector > &assigned_on_the_fly, + std::vector > > unin) { + //fprintf(stderr, "\n\nleaf_print_repr()\n"); + + if (active.num_elem() == 0) + return NULL; + + CG_outputRepr *stmt_list = NULL; + for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) { + std::map::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 loop_vars; + for (int k = 1; k <= mapping.n_out(); k++) + loop_vars.push_back(mapping.output_var(k)->name()); + + + std::vector sList = output_substitutions(ocg, + mapping, + assigned_on_the_fly, + unin[*i]); + + 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, + unin)); - 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)); + if (guard_repr == NULL) + return stmt_list; + else { + fprintf(stderr, "CG_utils.cc leaf_print_repr() CreateIf()\n"); + return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); } } 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); + Relation then_cond = + find_best_guard( + const_cast &>(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()); + BoolSet<> else_active(active.size()); + BoolSet<> indep_active(active.size()); + std::map then_guards, else_guards; + for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) { + Relation &r = const_cast &>(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 - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(-coef), v_repr)); + indep_active.set(*i); } - } - } - 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 > &assigned_on_the_fly) { - std::pair result = find_simplest_stride(R, const_cast(R).set_var(level)); - if (result.second != NULL) - assert(abs(result.first.get_coef(const_cast(R).set_var(level))) == 1); - - std::vector lbList, ubList; - try { - - coef_t const_lb = negInfinity, const_ub = posInfinity; - - for (GEQ_Iterator e(const_cast(R).single_conjunct()->GEQs()); e; e++) { - coef_t coef = (*e).get_coef(const_cast(R).set_var(level)); - - if (coef > 0) { - CG_outputRepr *repr = output_lower_bound_repr(ocg, *e, const_cast(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(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(R).set_var(level)); - coef_t sb = (int) (ceil(((float) L) /m)); - set_max(const_lb, sb); - } - else{ + assert(!then_active.empty()); + + //Anand: adding support for Replacing substituted variables within + //Uninterpreted function symbols or global variables with arity > 0 here + //--begin + std::vector > aotf = assigned_on_the_fly; + + CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, aotf, + unin[*(active.begin())]); + 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, + unin); - coef_t L,m,s,c; - L = -((*e).get_const()); - m = (*e).get_coef(const_cast(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 (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, + unin); + + stmt_list = ocg->StmtListAppend(stmt_list, + leaf_print_repr(indep_active, + guards, + NULL, + known, + new_indent, + ocg, + remap, + xforms, + stmts, + assigned_on_the_fly, + unin)); + + if (guard_repr == NULL) + return stmt_list; + else { + fprintf(stderr, "CG_utils.cc leaf_print_repr() CreateIf() 2\n"); + return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); } - } - else if (coef < 0) { - CG_outputRepr *repr = output_upper_bound_repr(ocg, *e, const_cast(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(R).set_var(level))) { - // no variables but v in constraint - set_min(const_ub,-(*e).get_const()/(*e).get_coef(const_cast(R).set_var(level))); + 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, + unin); + + 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, + unin); + + fprintf(stderr, "CG_utils.cc leaf_print_repr() CreateIf() 3\n"); + 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, + unin)); + + if (guard_repr == NULL) + return stmt_list; + else { + fprintf(stderr, "CG_utils.cc leaf_print_repr() CreateIf() 4\n"); + return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); } - } } - - 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(R).set_var(level), assigned_on_the_fly); - return ocg->CreateInductive(indexRepr, lbRepr, ubRepr, stRepr); -} + std::string print_to_iegen_string(Relation &R) { + std::string s = ""; + for (GEQ_Iterator e(R.single_conjunct()->GEQs()); e; e++) { + if (s != "") + s += " && "; + s += (*e).print_to_string(); + } + + for (EQ_Iterator e(R.single_conjunct()->EQs()); e; e++) { + if (s != "") + s += " && "; + s += (*e).print_to_string(); + } + return s; + } + // -// 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. +// Check if a set/input var is projected out of a inequality by a global variable with arity > 0 // -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 &exists_mapping) { - assert(R.n_out() == 0 && r.n_out() == 0 && R.n_inp() == r.n_inp()); - - std::set excluded_floor_vars; - std::stack 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 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::iterator p = exists_mapping.find(v2); - Variable_ID v3; - if (p == exists_mapping.end()) { - v3 = f_exists->declare(); - exists_mapping[v2] = v3; + Relation checkAndRestoreIfProjectedByGlobal(const Relation &R1, + const Relation &R2, Variable_ID v) { + + Relation to_return(R2.n_set()); + +//1. detect if a variable is not involved in a GEQ. + for (DNF_Iterator di(copy(R1).query_DNF()); di; di++) + for (GEQ_Iterator ci = (*di)->GEQs(); ci; ci++) + if ((*ci).get_coef(v) != 0) + return copy(R2); + + bool found_global_eq = false; + Global_Var_ID g1; + EQ_Handle e; +//2. detect if its involved in an eq involving a global with arity >= 1 + for (DNF_Iterator di(copy(R1).query_DNF()); di; di++) + for (EQ_Iterator ci = (*di)->EQs(); ci; ci++) + if ((*ci).get_coef(v) != 0) + for (Constr_Vars_Iter cvi(*ci); cvi; cvi++) { + v = cvi.curr_var(); + if (v->kind() == Global_Var) + if (v->get_global_var()->arity() > 0) { + found_global_eq = true; + g1 = v->get_global_var(); + e = (*ci); + } + } + + if (!found_global_eq) + return copy(R2); + +//3. check if the global is involved in a geq + + bool found_global_lb = false; + bool found_global_ub = false; + + std::vector ub; + std::vector lb; + for (DNF_Iterator di(copy(R1).query_DNF()); di; di++) + for (GEQ_Iterator ci = (*di)->GEQs(); ci; ci++) + for (Constr_Vars_Iter cvi(*ci); cvi; cvi++) { + Variable_ID v = cvi.curr_var(); + if (v->kind() == Global_Var) + if (v->get_global_var()->arity() > 0 + && v->get_global_var() == g1) { + if (cvi.curr_coef() > 0) { + found_global_lb = true; + + lb.push_back(*ci); + } + else if (cvi.curr_coef() < 0) { + found_global_ub = true; + + ub.push_back(*ci); + } + + } } + + if (!found_global_lb || !found_global_ub) + return copy(R2); + +// + + F_And *root = to_return.add_and(); + + for (int i = 0; i < lb.size(); i++) { + GEQ_Handle lower = root->add_GEQ(); + for (Constr_Vars_Iter cvi(lb[i]); cvi; cvi++) { + Variable_ID v2 = cvi.curr_var(); + + if (v2->kind() == Wildcard_Var) + return copy(R2); + if (v2->kind() != Global_Var + || (v2->kind() == Global_Var && v2->get_global_var() != g1)) { + if (v2->kind() != Global_Var) + lower.update_coef(v2, cvi.curr_coef()); + else { + Variable_ID lb1 = to_return.get_local(v2->get_global_var(), + Input_Tuple); + lower.update_coef(lb1, cvi.curr_coef()); + } + + } 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; + lower.update_coef(v, cvi.curr_coef()); } - case Global_Var: { - Global_Var_ID g = v2->get_global_var(); - Variable_ID v3; - if (g->arity() == 0) - v3 = r.get_local(g); + + lower.update_const(lb[i].get_const()); + } + + for (int i = 0; i < ub.size(); i++) { + GEQ_Handle upper = root->add_GEQ(); + for (Constr_Vars_Iter cvi(ub[i]); cvi; cvi++) { + Variable_ID v2 = cvi.curr_var(); + + if (v2->kind() == Wildcard_Var) + return copy(R2); + if (v2->kind() != Global_Var + || (v2->kind() == Global_Var && v2->get_global_var() != g1)) { + if (v2->kind() != Global_Var) + upper.update_coef(v2, cvi.curr_coef()); + else { + Variable_ID ub1 = to_return.get_local(v2->get_global_var(), + Input_Tuple); + upper.update_coef(ub1, cvi.curr_coef()); + } + + } else - v3 = r.get_local(g, v2->function_of()); - h1.update_coef(v3, cvi.curr_coef()); - h2.update_coef(v3, -cvi.curr_coef()); - break; + upper.update_coef(v, cvi.curr_coef()); } - default: - assert(false); + + upper.update_const(ub[i].get_const()); + } + +//Relation to_return2 = copy(R2); + + for (EQ_Iterator g(const_cast(R2).single_conjunct()->EQs()); g; + g++) + to_return.and_with_EQ(*g); + + for (GEQ_Iterator g(const_cast(R2).single_conjunct()->GEQs()); + g; g++) { + bool found_glob = false; + for (Constr_Vars_Iter cvi(*g); cvi; cvi++) { + Variable_ID v2 = cvi.curr_var(); + if (v2->kind() == Global_Var && v2->get_global_var() == g1) { + found_glob = true; + break; + } } + if (!found_glob) + to_return.and_with_GEQ(*g); + } - h1.update_const(result.second.get_const()); - h2.update_const(-result.second.get_const()-result.second.get_coef(v)-1); +//to_return.and_with_EQ(e); + + to_return.copy_names(copy(R2)); + to_return.setup_names(); + to_return.finalize(); + return to_return; } - - 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 addInequalitiesToRelation(const Relation &R, + std::vector &inequalities) { + Relation to_return(R.n_set()); - Relation r = Relation::True(R.n_set()); - - for (GEQ_Iterator e(const_cast(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; - } + return to_return; + } - for (EQ_Iterator e(const_cast(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(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(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 +// heavy lifting for code output for one level of loop nodes // -CG_outputRepr *leaf_print_repr(BoolSet<> active, const std::map &guards, - CG_outputRepr *guard_repr, const Relation &known, - int indent, CG_outputBuilder *ocg, const std::vector &remap, - const std::vector &xforms, const std::vector &stmts, - const std::vector > &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::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 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"; + CG_outputRepr *loop_print_repr(BoolSet<> active, + const std::vector &loops, + int start, + int end, + const Relation &guard, + CG_outputRepr *guard_repr, + int indent, + const std::vector &remap, + const std::vector &xforms, + CG_outputBuilder *ocg, + const std::vector &stmts, + const std::vector > &assigned_on_the_fly, + std::vector > > unin) { + + fprintf(stderr, "loop_print_repr() guard_repr "); + if (guard_repr == NULL) fprintf(stderr, "NULL\n"); + else fprintf(stderr, "NOT NULL\n"); + + 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, + unin)); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive\n"); + stmt_list = ocg->StmtListAppend(stmt_list, + loop_print_repr(active, + loops, + i, + end, + guard, + NULL, + new_indent, + remap, + xforms, + ocg, + stmts, + assigned_on_the_fly, + unin)); + + //fprintf(stderr, "guard_repr 0x%x\n", guard_repr); + if (guard_repr == NULL) + return stmt_list; + else { + fprintf(stderr, "CG_utils.cc loop_print_repr() CreateIf()\n"); + return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); } - std::vector 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 &>(guards)[*(active.begin())], active, guards); + + Relation then_cond = find_best_guard(R, loops, start, end); + fprintf(stderr, "then_cond "); then_cond.print(stderr); 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 then_guards, else_guards; - for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) { - Relation &r = const_cast &>(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()); + std::vector 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 (else_active.empty() && indep_active.empty()) { + //Anand: adding support for Replacing substituted variables within + //Uninterpreted function symbols or global variables with arity > 0 here + //--begin + std::vector > aotf = assigned_on_the_fly; + CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, aotf, unin[*(active.begin())]); + + //fprintf(stderr, "new_guard_repr 0x%x\n", new_guard_repr); + if (j == i && end == j) { 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); + Relation new_guard = Intersection(copy(guard), copy(then_cond)); + new_guard.simplify(); + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 2\n"); + return loop_print_repr(active, loops, start, end, new_guard, guard_repr, + indent, remap, xforms, ocg, stmts, aotf, unin); } - else if (else_active.empty() && !indep_active.empty()) { + else if (j == i && end > j) { 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)); + Relation new_guard = Intersection(copy(guard), copy(then_cond)); + new_guard.print(stderr); + new_guard.print_with_subs(stderr); + new_guard.simplify(); + new_guard.print(stderr); + new_guard.print_with_subs(stderr); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 3\n"); + CG_outputRepr *stmt_list = loop_print_repr(active, + loops, + start, + i, + new_guard, + new_guard_repr, + new_indent, + remap, + xforms, + ocg, + stmts, + aotf, + unin); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 4\n"); + stmt_list = ocg->StmtListAppend(stmt_list, + loop_print_repr(active, + loops, + j, + end, + guard, + NULL, + new_indent, + remap, + xforms, + ocg, + stmts, + aotf, + unin)); + if (guard_repr == NULL) return stmt_list; - else + else { + fprintf(stderr, "CG_utils.cc loop_print_repr() CreateIf() 2\n"); return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); + } } - else { // (!else_active.empty()) + else { // (j > i) 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)); + Relation then_new_guard = Intersection(copy(guard), copy(then_cond)); + then_new_guard.simplify(); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 5\n"); + CG_outputRepr *then_stmt_list = loop_print_repr(active, + loops, + start, + i, + then_new_guard, + NULL, + new_indent+1, + remap, + xforms, + ocg, + stmts, + aotf, + unin); + + Relation else_new_guard = Intersection(copy(guard), copy(else_cond)); + else_new_guard.simplify(); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 6\n"); + CG_outputRepr *else_stmt_list = loop_print_repr(active, + loops, + i, + j, + else_new_guard, + NULL, + new_indent+1, + remap, + xforms, + ocg, + stmts, + aotf, + unin); + + fprintf(stderr, "CG_utils.cc loop_print_repr() CreateIf() 3\n"); + CG_outputRepr *stmt_list = ocg->CreateIf(new_indent, + new_guard_repr, + then_stmt_list, + else_stmt_list); + + fprintf(stderr,"CG_utils.cc loop_print_repr recursive 7\n"); + stmt_list = ocg->StmtListAppend(stmt_list, + loop_print_repr(active, + loops, + j, + end, + guard, + NULL, + new_indent, + remap, + xforms, + ocg, + stmts, + aotf, + unin)); + + if (guard_repr == NULL) return stmt_list; - else + else { + fprintf(stderr, "CG_utils.cc loop_print_repr() CreateIf() 4\n"); 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 &loops, int start, int end, - const Relation &guard, CG_outputRepr *guard_repr, - int indent, CG_outputBuilder *ocg, const std::vector &stmts, - const std::vector > &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 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); - } -} - } -- cgit v1.2.3-70-g09d2