diff options
Diffstat (limited to 'omegalib/codegen')
21 files changed, 0 insertions, 6039 deletions
diff --git a/omegalib/codegen/CMakeLists.txt b/omegalib/codegen/CMakeLists.txt deleted file mode 100644 index 79bdcb4..0000000 --- a/omegalib/codegen/CMakeLists.txt +++ /dev/null @@ -1,30 +0,0 @@ -set(CG_SRC - src/codegen.cc - src/CG.cc - src/CG_stringBuilder.cc - src/CG_utils.cc - - src/rose_attributes.cc - src/CG_roseBuilder.cc - src/CG_roseRepr.cc - ) - -set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-write-strings") - -include_directories( - include - ${OMEGAROOT}/omega/include - ${ROSEHOME}/include/rose - ${BOOSTHOME}/include - ) - -add_library(codegen - ${CG_SRC} - ) - -add_dependencies(codegen omega) - -install(TARGETS codegen - ARCHIVE DESTINATION lib) -install(DIRECTORY include - DESTINATION .) diff --git a/omegalib/codegen/include/code_gen/CG.h b/omegalib/codegen/include/code_gen/CG.h deleted file mode 100644 index ce56768..0000000 --- a/omegalib/codegen/include/code_gen/CG.h +++ /dev/null @@ -1,118 +0,0 @@ -#ifndef _CG_H -#define _CG_H - -#include <omega/Relation.h> -#include <basic/BoolSet.h> -#include <code_gen/CG_outputBuilder.h> -#include <vector> - -namespace omega { - -class CodeGen; - -struct CG_result { - CodeGen *codegen_; - BoolSet<> active_; - - CG_result() { codegen_ = NULL; } - virtual ~CG_result() { /* not responsible for codegen_ */ } - - virtual CG_result *recompute(const BoolSet<> &parent_active, const Relation &known, const Relation &restriction) = 0; - virtual int populateDepth() = 0; - virtual std::pair<CG_result *, Relation> liftOverhead(int depth, bool propagate_up) = 0; - virtual Relation hoistGuard() = 0; - virtual void removeGuard(const Relation &guard) = 0; - virtual CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const = 0; - CG_outputRepr *printRepr(CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts) const; - std::string printString() const; - int num_level() const; - virtual CG_result *clone() const = 0; - virtual void dump(int indent) const {} - void dump() { dump(0); } -}; - - -struct CG_split: public CG_result { - std::vector<Relation> restrictions_; - std::vector<CG_result *> clauses_; - - CG_split(CodeGen *codegen, const BoolSet<> &active, const std::vector<Relation> &restrictions, const std::vector<CG_result *> &clauses) { - codegen_ = codegen; - active_ = active; - restrictions_ = restrictions; - clauses_ = clauses; - } - ~CG_split() { - for (int i = 0; i < clauses_.size(); i++) - delete clauses_[i]; - } - - CG_result *recompute(const BoolSet<> &parent_active, const Relation &known, const Relation &restriction); - int populateDepth(); - std::pair<CG_result *, Relation> liftOverhead(int depth, bool propagate_up); - Relation hoistGuard(); - void removeGuard(const Relation &guard); - CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const; - CG_result *clone() const; - void dump(int indent) const; - -private: - std::vector<CG_result *> findNextLevel() const; -}; - - -struct CG_loop: public CG_result { - int level_; - CG_result *body_; - - Relation known_; - Relation restriction_; - Relation bounds_; - Relation guard_; - bool needLoop_; - int depth_; - - CG_loop(CodeGen *codegen, const BoolSet<> &active, int level, CG_result *body) { - codegen_ = codegen; - active_ = active; - level_ = level; - body_ = body; - } - ~CG_loop() { delete body_; } - - CG_result *recompute(const BoolSet<> &parent_active, const Relation &known, const Relation &restriction); - int populateDepth(); - std::pair<CG_result *, Relation> liftOverhead(int depth, bool propagate_up); - Relation hoistGuard(); - void removeGuard(const Relation &guard); - CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const; - CG_outputRepr *printRepr(bool do_print_guard, int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const; - CG_result *clone() const; - void dump(int indent) const; -}; - - - -struct CG_leaf: public CG_result { - Relation known_; - std::map<int, Relation> guards_; - - CG_leaf(CodeGen *codegen, const BoolSet<> &active) { - codegen_ = codegen; - active_ = active; - } - ~CG_leaf() {} - - CG_result *recompute(const BoolSet<> &parent_active, const Relation &known, const Relation &restriction); - int populateDepth() { return 0; } - std::pair<CG_result *, Relation> liftOverhead(int depth, bool propagate_up); - Relation hoistGuard(); - void removeGuard(const Relation &guard); - CG_outputRepr *printRepr(int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const; - CG_result *clone() const; - void dump(int indent) const; -}; - -} - -#endif diff --git a/omegalib/codegen/include/code_gen/CG_outputBuilder.h b/omegalib/codegen/include/code_gen/CG_outputBuilder.h deleted file mode 100644 index 19dc440..0000000 --- a/omegalib/codegen/include/code_gen/CG_outputBuilder.h +++ /dev/null @@ -1,161 +0,0 @@ -/***************************************************************************** - Copyright (C) 1994-2000 the Omega Project Team - Copyright (C) 2005-2011 Chun Chen - All Rights Reserved. - - Purpose: - abstract base class of comiler IR code builder - - Notes: - All "CG_outputRepr *" parameters are consumed inside the the function - unless explicitly stated otherwise, i.e., not valid after the call. - Parameter "indent" normally not used except it is used in unstructured - string output for correct indentation. - - History: - 04/17/96 created - Lei Zhou - 05/02/08 clarify integer floor/mod/ceil definitions, -chen - 05/31/08 use virtual clone to implement CreateCopy, -chun - 08/05/10 clarify NULL parameter allowance, -chun -*****************************************************************************/ - -#ifndef _CG_OUTPUTBUILDER_H -#define _CG_OUTPUTBUILDER_H - -#include <code_gen/CG_outputRepr.h> - -#include <string> -#include <vector> - -namespace omega { - -//! abstract base class of comiler IR code builder -class CG_outputBuilder { -public: - CG_outputBuilder() {} - virtual ~CG_outputBuilder() {} - - //! substitute variables in stmt - virtual CG_outputRepr *CreateSubstitutedStmt(int indent, CG_outputRepr *stmt, - const std::vector<std::string> &vars, - std::vector<CG_outputRepr *> &subs) const = 0; - - //! assignment stmt generation - virtual CG_outputRepr *CreateAssignment(int indent, CG_outputRepr *lhs, - CG_outputRepr *rhs) const = 0; - - //! function invocation generation - virtual CG_outputRepr *CreateInvoke(const std::string &funcName, - std::vector<CG_outputRepr *> &argList) const = 0; - - //! comment generation - virtual CG_outputRepr *CreateComment(int indent, - const std::string &commentText) const = 0; - - //! Attribute generation - virtual CG_outputRepr* CreateAttribute(CG_outputRepr *control, - const std::string &commentText) const = 0; - //! Pragma Attribute - virtual CG_outputRepr* CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const = 0; - - //! Prefetch Attribute - virtual CG_outputRepr* CreatePrefetchAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &arrName, int hint) const = 0; - - //! generate if stmt, true/false stmt can be NULL but not the condition - virtual CG_outputRepr *CreateIf(int indent, CG_outputRepr *guardCondition, - CG_outputRepr *true_stmtList, - CG_outputRepr *false_stmtList) const = 0; - - //! generate loop inductive variable (loop control structure) - virtual CG_outputRepr *CreateInductive(CG_outputRepr *index, - CG_outputRepr *lower, - CG_outputRepr *upper, - CG_outputRepr *step) const = 0; - - //! generate loop stmt from loop control and loop body, NULL parameter allowed - virtual CG_outputRepr *CreateLoop(int indent, CG_outputRepr *control, - CG_outputRepr *stmtList) const = 0; - - //! copy operation, NULL parameter allowed. - /*! - * this function makes pointer handling uniform regardless NULL status - */ - virtual CG_outputRepr *CreateCopy(CG_outputRepr *original) const { - if (original == NULL) - return NULL; - else - return original->clone(); - } - - //! basic integer number creation - virtual CG_outputRepr *CreateInt(int num) const = 0; - virtual bool isInteger(CG_outputRepr *op) const = 0; - - - //! basic identity/variable creation - virtual CG_outputRepr *CreateIdent(const std::string &varName) const = 0; - - //! Addition operations, NULL parameter means 0, - virtual CG_outputRepr *CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const = 0; - //! Subtraction operations, NULL parameter means 0, - virtual CG_outputRepr *CreateMinus(CG_outputRepr *lop, CG_outputRepr *rop) const = 0; - //! Multiplication operations, NULL parameter means 0, - virtual CG_outputRepr *CreateTimes(CG_outputRepr *lop, CG_outputRepr *rop) const = 0; - //! Division operations, NULL parameter means 0, - /*! - * integer division truncation method undefined, only use when lop is known - * to be multiple of rop, otherwise use integer floor instead - */ - virtual CG_outputRepr *CreateDivide(CG_outputRepr *lop, CG_outputRepr *rop) const { - return CreateIntegerFloor(lop, rop); - } - - //! integer floor functions, NULL parameter means 0 - /*! - * second parameter must be postive (i.e. b > 0 below), otherwise function undefined - * - * floor(a, b) - * * = a/b if a >= 0 - * * = (a-b+1)/b if a < 0 - */ - virtual CG_outputRepr *CreateIntegerFloor(CG_outputRepr *lop, CG_outputRepr *rop) const = 0; - //! integer mod functions, NULL parameter means 0 - /*! - * second parameter must be postive (i.e. b > 0 below), otherwise function undefined - * - * mod(a, b) = a-b*floor(a, b) where result must lie in range [0,b) - */ - virtual CG_outputRepr *CreateIntegerMod(CG_outputRepr *lop, CG_outputRepr *rop) const { - CG_outputRepr *lop2 = CreateCopy(lop); - CG_outputRepr *rop2 = CreateCopy(rop); - return CreateMinus(lop2, CreateTimes(rop2, CreateIntegerFloor(lop, rop))); - } - //! integer ceil functions, NULL parameter means 0 - /*! - * second parameter must be postive (i.e. b > 0 below), otherwise function undefined - * - * ceil(a, b) = -floor(-a, b) or floor(a+b-1, b) or floor(a-1, b)+1 - */ - virtual CG_outputRepr *CreateIntegerCeil(CG_outputRepr *lop, CG_outputRepr *rop) const { - return CreateMinus(NULL, CreateIntegerFloor(CreateMinus(NULL, lop), rop)); - } - - //! binary logical operation, NULL parameter means TRUE - virtual CG_outputRepr *CreateAnd(CG_outputRepr *lop, CG_outputRepr *rop) const = 0; - - //! binary conditional Greater than or equal to - virtual CG_outputRepr *CreateGE(CG_outputRepr *lop, CG_outputRepr *rop) const { - return CreateLE(rop, lop); - } - //! binary conditional Less than or equal to - virtual CG_outputRepr *CreateLE(CG_outputRepr *lop, CG_outputRepr *rop) const = 0; - //! binary conditional equal to - virtual CG_outputRepr *CreateEQ(CG_outputRepr *lop, CG_outputRepr *rop) const = 0; - - //! join stmts together, NULL parameter allowed - virtual CG_outputRepr *StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const = 0; -}; - -} - -#endif diff --git a/omegalib/codegen/include/code_gen/CG_outputRepr.h b/omegalib/codegen/include/code_gen/CG_outputRepr.h deleted file mode 100644 index 0897007..0000000 --- a/omegalib/codegen/include/code_gen/CG_outputRepr.h +++ /dev/null @@ -1,33 +0,0 @@ -/***************************************************************************** - Copyright (C) 1994-2000 the Omega Project Team - Copyright (C) 2005-2011 Chun Chen - All Rights Reserved. - - Purpose: - abstract base class of compiler IR code wrapper - - Notes: - - History: - 04/17/96 - Lei Zhou - created -*****************************************************************************/ - -#ifndef _CG_OUTPUTREPR_H -#define _CG_OUTPUTREPR_H - -namespace omega { - -class CG_outputRepr { -public: - CG_outputRepr() {} - //! shallow delete - virtual ~CG_outputRepr() { } - virtual CG_outputRepr *clone() const = 0; - //! delete actual IR code wrapped inside - virtual void clear() { } - virtual void dump() const {} -}; - -} - -#endif diff --git a/omegalib/codegen/include/code_gen/CG_roseBuilder.h b/omegalib/codegen/include/code_gen/CG_roseBuilder.h deleted file mode 100644 index 5dad663..0000000 --- a/omegalib/codegen/include/code_gen/CG_roseBuilder.h +++ /dev/null @@ -1,108 +0,0 @@ -#ifndef CG_roseBuilder_h -#define CG_roseBuilder_h - -#include <basic/Tuple.h> -#include <code_gen/rose_attributes.h> -#include <code_gen/CG_outputBuilder.h> -#include <code_gen/CG_roseRepr.h> -#include <string> - -namespace omega { - -class CG_roseBuilder : public CG_outputBuilder { -public: - CG_roseBuilder(int isFortran, SgGlobal* global, SgGlobal* global_scope, SgSymbolTable* symtab1, SgSymbolTable* symtab2, SgNode* root); - ~CG_roseBuilder(); - - //! substitute variables in stmt - CG_outputRepr *CreateSubstitutedStmt(int indent, CG_outputRepr *stmt, - const std::vector<std::string> &vars, - std::vector<CG_outputRepr *> &subs) const; - - - - //! assignment generation - CG_outputRepr* CreateAssignment(int indent, CG_outputRepr* lhs, - CG_outputRepr* rhs) const; - - //! function invocation generation - CG_outputRepr* CreateInvoke(const std::string &funcName, - std::vector<CG_outputRepr *> &argList) const; - - //! comment generation - CG_outputRepr* CreateComment(int indent, const std::string &commentText) const; - //! Attribute generation - CG_outputRepr* CreateAttribute(CG_outputRepr *control, - const std::string &commentText) const; - //! Pragma Attribute - CG_outputRepr* CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, - const std::string &pragmaText) const; - - //! Prefetch Attribute - CG_outputRepr* CreatePrefetchAttribute(CG_outputRepr *scopeStmt, int looplevel, - const std::string &arrName, int hint) const; - - //! if stmt gen operations - CG_outputRepr* CreateIf(int indent, CG_outputRepr* guardCondition, - CG_outputRepr* true_stmtList, CG_outputRepr* false_stmtList) const; - - //! inductive variable generation, to be used in CreateLoop as control - CG_outputRepr* CreateInductive(CG_outputRepr* index, - CG_outputRepr* lower, - CG_outputRepr* upper, - CG_outputRepr* step) const; - - //! loop stmt generation - CG_outputRepr* CreateLoop(int indent, CG_outputRepr* control, - CG_outputRepr* stmtList) const; - - CG_outputRepr* CreateInt(int num ) const; - bool isInteger(CG_outputRepr *op) const; - CG_outputRepr* CreateIdent(const std::string &varName) const; - - //! binary arithmetic operations - CG_outputRepr* CreatePlus(CG_outputRepr* lop, CG_outputRepr* rop) const; - CG_outputRepr* CreateMinus(CG_outputRepr* lop, CG_outputRepr* rop) const; - CG_outputRepr* CreateTimes(CG_outputRepr* lop, CG_outputRepr* rop) const; - CG_outputRepr* CreateIntegerFloor(CG_outputRepr* lop, CG_outputRepr* rop) const; - CG_outputRepr* CreateIntegerMod(CG_outputRepr* lop, CG_outputRepr* rop) const; - - //! binary logical operations - CG_outputRepr* CreateAnd(CG_outputRepr* lop, CG_outputRepr* rop) const; - - //--------------------------------------------------------------------------- - // binary relational operations - //--------------------------------------------------------------------------- - // CG_outputRepr* CreateGE(CG_outputRepr*, CG_outputRepr*) const; - CG_outputRepr* CreateLE(CG_outputRepr* lop, CG_outputRepr* rop) const; - CG_outputRepr* CreateEQ(CG_outputRepr* lop, CG_outputRepr* rop) const; - - //--------------------------------------------------------------------------- - // stmt list gen operations - //--------------------------------------------------------------------------- - CG_outputRepr* - StmtListAppend(CG_outputRepr* list1, CG_outputRepr* list2) const; - - CG_outputRepr* CreateDim3(const char* varName, CG_outputRepr* arg1, CG_outputRepr* arg2, CG_outputRepr* arg3 = NULL) const; - - // Manu:: added for fortran support - bool isInputFortran() const; - -private: - SgSymbolTable *symtab_; - SgSymbolTable *symtab2_; - SgNode* root_; - SgGlobal* global_; - SgGlobal* global_scope; - int isFortran; // Manu:: added for fortran support -}; - -extern char *k_ocg_comment; -std::vector<SgVarRefExp *>substitute(SgNode *tnl, const SgVariableSymbol *sym, SgExpression *expr,SgNode* root) ; - - - - -} // namespace - -#endif diff --git a/omegalib/codegen/include/code_gen/CG_roseRepr.h b/omegalib/codegen/include/code_gen/CG_roseRepr.h deleted file mode 100644 index 28553e7..0000000 --- a/omegalib/codegen/include/code_gen/CG_roseRepr.h +++ /dev/null @@ -1,46 +0,0 @@ -#ifndef CG_roseRepr_h -#define CG_roseRepr_h - -#include <code_gen/CG_outputRepr.h> -#include "rose.h" - -namespace omega { - -class CG_roseRepr : public CG_outputRepr { - friend class CG_roseBuilder; -public: - CG_roseRepr(); - CG_roseRepr(SgNode *tnl); - CG_roseRepr(SgExpression *exp); - CG_roseRepr(SgStatementPtrList* stmtlist); - - ~CG_roseRepr(); - CG_outputRepr *clone() const; - void clear(); - - SgNode* GetCode() const; - SgStatementPtrList* GetList() const; - SgExpression *GetExpression() const; - - - - - //--------------------------------------------------------------------------- - // Dump operations - //--------------------------------------------------------------------------- - void Dump() const; -private: - // only one of _tnl and _op would be active at any time, depending on - // whether it is building a statement list or an expression tree - SgNode *tnl_; - SgExpression *op_; - SgStatementPtrList *list_; - void DumpFileHelper(SgNode* node, FILE* fp) const; - //operand op_; -}; - - - -} // namespace - -#endif diff --git a/omegalib/codegen/include/code_gen/CG_stringBuilder.h b/omegalib/codegen/include/code_gen/CG_stringBuilder.h deleted file mode 100644 index 09d3503..0000000 --- a/omegalib/codegen/include/code_gen/CG_stringBuilder.h +++ /dev/null @@ -1,44 +0,0 @@ -#ifndef _CG_STRINGBUILDER_H -#define _CG_STRINGBUILDER_H - -#include <code_gen/CG_outputBuilder.h> -#include <code_gen/CG_stringRepr.h> - -namespace omega { - -class CG_stringBuilder: public CG_outputBuilder { -public: - CG_stringBuilder() {} - ~CG_stringBuilder() {} - bool isInteger(CG_outputRepr *op) const; - CG_stringRepr *CreateSubstitutedStmt(int indent, CG_outputRepr *stmt, const std::vector<std::string> &vars, std::vector<CG_outputRepr *> &subs) const; - CG_stringRepr *CreateAssignment(int indent, CG_outputRepr *lhs, CG_outputRepr *rhs) const; - CG_stringRepr *CreateInvoke(const std::string &funcName, std::vector<CG_outputRepr *> &argList) const; - CG_stringRepr *CreateComment(int indent, const std::string &commentText) const; - CG_stringRepr* CreateAttribute(CG_outputRepr *control, - const std::string &commentText) const; - CG_outputRepr *CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const; - CG_outputRepr *CreatePrefetchAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &arrName, int hint) const; - CG_stringRepr *CreateIf(int indent, CG_outputRepr *guardCondition, CG_outputRepr *true_stmtList, CG_outputRepr *false_stmtList) const; - CG_stringRepr *CreateInductive(CG_outputRepr *index, CG_outputRepr *lower, CG_outputRepr *upper, CG_outputRepr *step) const; - CG_stringRepr *CreateLoop(int indent, CG_outputRepr *control, CG_outputRepr *stmtList) const; - CG_stringRepr *CreateInt(int num) const; - CG_stringRepr *CreateIdent(const std::string &varName) const; - CG_stringRepr *CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateMinus(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateTimes(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateDivide(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateIntegerFloor(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateIntegerMod(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateIntegerCeil(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateAnd(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateGE(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateLE(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *CreateEQ(CG_outputRepr *lop, CG_outputRepr *rop) const; - CG_stringRepr *StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const; -}; - - -} - -#endif diff --git a/omegalib/codegen/include/code_gen/CG_stringRepr.h b/omegalib/codegen/include/code_gen/CG_stringRepr.h deleted file mode 100644 index a6df85d..0000000 --- a/omegalib/codegen/include/code_gen/CG_stringRepr.h +++ /dev/null @@ -1,43 +0,0 @@ -/***************************************************************************** - Copyright (C) 1994-2000 the Omega Project Team - Copyright (C) 2005-2011 Chun Chen - All Rights Reserved. - - Purpose: - pseudo string code wrapper - - Notes: - - History: - 04/17/96 - Lei Zhou - created -*****************************************************************************/ - -#ifndef _CG_STRINGREPR_H -#define _CG_STRINGREPR_H - -#include <code_gen/CG_outputRepr.h> -#include <string> -#include <iostream> - -namespace omega { - -class CG_stringRepr: public CG_outputRepr { -private: - std::string s_; - -public: - CG_stringRepr() {} - CG_stringRepr(const std::string &s) { s_ = s; } - ~CG_stringRepr() {} - CG_outputRepr *clone() const { return new CG_stringRepr(s_); } - void dump() const { std::cout << s_ << std::endl; } - - //--------------------------------------------------------------------------- - // basic operation - //--------------------------------------------------------------------------- - std::string GetString() const { return s_; } -}; - -} - -#endif diff --git a/omegalib/codegen/include/code_gen/CG_utils.h b/omegalib/codegen/include/code_gen/CG_utils.h deleted file mode 100755 index a6128bc..0000000 --- a/omegalib/codegen/include/code_gen/CG_utils.h +++ /dev/null @@ -1,45 +0,0 @@ -#ifndef _CG_UTILS_H -#define _CG_UTILS_H - -#include <omega.h> -#include <code_gen/CG_outputBuilder.h> -#include <basic/BoolSet.h> -#include <vector> -#include <set> -#include <map> - -namespace omega { - -class CG_loop; - -CG_outputRepr *output_inequality_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, std::set<Variable_ID> excluded_floor_vars = std::set<Variable_ID>()); -CG_outputRepr *output_substitution_repr(CG_outputBuilder *ocg, const EQ_Handle &equality, Variable_ID v, bool apply_v_coef, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); -CG_outputRepr *output_upper_bound_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); -CG_outputRepr *output_lower_bound_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const EQ_Handle &stride_eq, Variable_ID wc, const Relation &R, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); - -CG_outputRepr *output_ident(CG_outputBuilder *ocg, const Relation &R, Variable_ID v, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); -std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > output_assignment(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); -CG_outputRepr *output_loop(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); -CG_outputRepr *output_guard(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); -std::vector<CG_outputRepr *> output_substitutions(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); - -bool bound_must_hit_stride(const GEQ_Handle &inequality, Variable_ID v, const EQ_Handle &stride_eq, Variable_ID wc, const Relation &bounds, const Relation &known); -std::pair<EQ_Handle, int> find_simplest_assignment(const Relation &R, Variable_ID v, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly = std::vector<std::pair<CG_outputRepr *, int> >()); -std::pair<bool, GEQ_Handle> find_floor_definition(const Relation &R, Variable_ID v, std::set<Variable_ID> excluded_floor_vars = std::set<Variable_ID>()); -std::pair<EQ_Handle, Variable_ID> find_simplest_stride(const Relation &R, Variable_ID v); -Variable_ID replicate_floor_definition(const Relation &R, const Variable_ID floor_var, Relation &r, F_Exists *f_exists, F_And *f_root, std::map<Variable_ID, Variable_ID> &exists_mapping); - -Relation pick_one_guard(const Relation &R, int level = 0); -CG_outputRepr *leaf_print_repr(BoolSet<> active, const std::map<int, Relation> &guards, - CG_outputRepr *guard_repr, const Relation &known, - int indent, CG_outputBuilder *ocg, const std::vector<int> &remap, - const std::vector<Relation> &xforms, const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); -CG_outputRepr *loop_print_repr(const std::vector<CG_loop *> &loops, int start, int end, - const Relation &guard, CG_outputRepr *guard_repr, - int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly); - -} - -#endif diff --git a/omegalib/codegen/include/code_gen/code_gen.h b/omegalib/codegen/include/code_gen/code_gen.h deleted file mode 100644 index abfab7c..0000000 --- a/omegalib/codegen/include/code_gen/code_gen.h +++ /dev/null @@ -1,47 +0,0 @@ -#if !defined(Already_Included_code_gen) -#define Already_Included_code_gen - -#include <basic/Tuple.h> -#include <omega/Relation.h> -#include <code_gen/CG.h> -#include <code_gen/CG_outputRepr.h> -#include <code_gen/CG_outputBuilder.h> - -namespace omega { - -typedef Tuple<int> IntTuple; -typedef Tuple<Relation> SetTuple; -typedef Tuple<SetTuple> SetTupleTuple; -typedef Tuple<Relation> RelTuple; -typedef Tuple<RelTuple> RelTupleTuple; - -CG_outputRepr *MMGenerateCode(CG_outputBuilder* ocg, - Tuple<Relation> &T, Tuple<Relation> &old_IS, - const Tuple<CG_outputRepr *> &stmt_content, - Relation &known, int effort=1); -std::string MMGenerateCode(Tuple<Relation> &T, Tuple<Relation> &old_IS, Relation &known, - int effort=1); - -//protonu-adding a new variant to keep Gabe's code happy -CG_outputRepr* MMGenerateCode(CG_outputBuilder* ocg, RelTuple &T, SetTuple &old_IS, - const Tuple<CG_outputRepr *> &stmt_content, Relation &known, - Tuple< IntTuple >& smtNonSplitLevels_, - std::vector< std::pair<int, std::string> > syncs_, - const Tuple< Tuple<std::string> >& loopIdxNames_, - int effort=1); -//end-protonu - -struct Polyhedra { - int last_level; - Tuple<Relation> transformations; - Relation known; - - Tuple<int> remap; // after initial iteration space's disjoint set splitting, the new statement number maps to old statement number - Tuple<Tuple<Relation> > projected_nIS; - - Polyhedra(const Tuple<Relation> &T, const Tuple<Relation> &old_IS, const Relation &known = Relation::Null()); - ~Polyhedra() {} -}; - -} -#endif diff --git a/omegalib/codegen/include/code_gen/codegen.h b/omegalib/codegen/include/code_gen/codegen.h deleted file mode 100755 index cb63bfd..0000000 --- a/omegalib/codegen/include/code_gen/codegen.h +++ /dev/null @@ -1,48 +0,0 @@ -#ifndef _CODEGEN_H -#define _CODEGEN_H - -#include <omega/Relation.h> -#include <code_gen/CG.h> -#include <code_gen/CG_outputBuilder.h> -#include <vector> -#include <string> - -namespace omega { - -class CodeGen { -public: - static const std::string loop_var_name_prefix; - static const int var_substitution_threshold; - -protected: - //! projected_IS_[level-1][new stmt#] - std::vector<std::vector<Relation> > projected_IS_; - //! transformations[original stmt#] - std::vector<Relation> xforms_; - //! no need to generate code for constraints satisfied in known - Relation known_; - //! map new stmt# to original stmt# - std::vector<int> remap_; - -public: - CodeGen(const std::vector<Relation> &xforms, const std::vector<Relation> &IS, const Relation &known = Relation::Null(), - std::vector< std::vector<int > > smtNonSplitLevels_ = std::vector< std::vector<int > >(), - std::vector< std::vector<std::string> > loopIdxNames_ = std::vector< std::vector<std::string> >(), - std::vector< std::pair<int, std::string> > syncs_ = std::vector< std::pair<int, std::string> >() - ); - ~CodeGen() {} - - CG_result *buildAST(int effort = 1); - int num_level() const { return projected_IS_.size(); } - -private: - CG_result *buildAST(int level, const BoolSet<> &active, bool split_on_const, const Relation &restriction); - - friend class CG_result; - friend class CG_split; - friend class CG_loop; - friend class CG_leaf; -}; - -} -#endif diff --git a/omegalib/codegen/include/code_gen/codegen_error.h b/omegalib/codegen/include/code_gen/codegen_error.h deleted file mode 100755 index 06ecc2b..0000000 --- a/omegalib/codegen/include/code_gen/codegen_error.h +++ /dev/null @@ -1,15 +0,0 @@ -#ifndef _CODEGEN_ERROR_H -#define _CODEGEN_ERROR_H - -#include <stdexcept> - -namespace omega { - -struct codegen_error: public std::runtime_error { - codegen_error(const std::string &msg): std::runtime_error("codegen error: " + msg) {} -}; - - -} -#endif - diff --git a/omegalib/codegen/include/code_gen/output_repr.h b/omegalib/codegen/include/code_gen/output_repr.h deleted file mode 100644 index 254e71b..0000000 --- a/omegalib/codegen/include/code_gen/output_repr.h +++ /dev/null @@ -1,46 +0,0 @@ -#ifndef OUTPUT_REPR_H -#define OUTPUT_REPR_H - -#include <omega.h> -#include <code_gen/CG_outputBuilder.h> -#include <code_gen/CG_outputRepr.h> -#include <vector> -#include <set> - -namespace omega { -extern int last_level; - -CG_outputRepr* outputIdent(CG_outputBuilder* ocg, const Relation &R, Variable_ID v, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -std::pair<CG_outputRepr *, bool> outputAssignment(CG_outputBuilder *ocg, const Relation &R_, Variable_ID v, Relation &enforced, CG_outputRepr *&if_repr, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -std::pair<CG_outputRepr *, bool> outputBounds(CG_outputBuilder* ocg, const Relation &bounds, Variable_ID v, int indent, Relation &enforced, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -Tuple<CG_outputRepr*> outputSubstitution(CG_outputBuilder* ocg, const Relation &R, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -CG_outputRepr* outputStatement(CG_outputBuilder* ocg, CG_outputRepr *stmt, int indent, const Relation &mapping, const Relation &known, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -CG_outputRepr* outputGuard(CG_outputBuilder* ocg, const Relation &guards_in, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -CG_outputRepr* output_as_guard(CG_outputBuilder* ocg, const Relation &guards_in, Constraint_Handle e, bool is_equality, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -CG_outputRepr* output_EQ_strides(CG_outputBuilder* ocg, const Relation &guards_in, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -CG_outputRepr* output_GEQ_strides(CG_outputBuilder* ocg, const Relation &guards_in, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -CG_outputRepr *outputLBasRepr(CG_outputBuilder* ocg, const GEQ_Handle &g, Relation &bounds, Variable_ID v, coef_t stride, const EQ_Handle &strideEQ, Relation known, const std::vector<CG_outputRepr *> &assigned_on_the_fly); -CG_outputRepr *outputUBasRepr(CG_outputBuilder* ocg, const GEQ_Handle &g, Relation & bounds, Variable_ID v, - coef_t /*stride*/, // currently unused - const EQ_Handle &/*strideEQ*/, - const std::vector<CG_outputRepr *> &assigned_on_the_fly = std::vector<CG_outputRepr *>(last_level, static_cast<CG_outputRepr *>(NULL))); -CG_outputRepr* outputEasyBoundAsRepr(CG_outputBuilder* ocg, Relation &bounds, const Constraint_Handle &g, Variable_ID v, bool ignoreWC, int ceiling, const std::vector<CG_outputRepr *> &assigned_on_the_fly); - - -bool boundHitsStride(const GEQ_Handle &g, Variable_ID v, const EQ_Handle &strideEQ, coef_t /*stride, currently unused*/, Relation known); -Relation greatest_common_step(const Tuple<Relation> &I, const Tuple<int> &active, int level, const Relation &known = Relation::Null()); -bool findFloorInequality(Relation &r, Variable_ID v, GEQ_Handle &h, Variable_ID excluded); -Relation project_onto_levels(Relation R, int last_level, bool wildcards); -bool isSimpleStride(const EQ_Handle &g, Variable_ID v); -int countStrides(Conjunct *c, Variable_ID v, EQ_Handle &strideEQ, bool &simple); -bool hasBound(Relation r, int level, int UB); -bool find_any_constraint(int s, int level, Relation &kr, int direction, Relation &S, bool approx); -bool has_nonstride_EQ(Relation r, int level); -Relation pickOverhead(Relation r, int liftTo); -Relation minMaxOverhead(Relation r, int level); -int max_fs_arity(const Constraint_Handle &c); - - -} - -#endif diff --git a/omegalib/codegen/include/code_gen/rose_attributes.h b/omegalib/codegen/include/code_gen/rose_attributes.h deleted file mode 100644 index 9766f52..0000000 --- a/omegalib/codegen/include/code_gen/rose_attributes.h +++ /dev/null @@ -1,91 +0,0 @@ -#ifndef ROSE_ATTRIBUTES_HH -#define ROSE_ATTRIBUTES_HH - -#include "rose.h" -#include <algorithm> -#include <string> -#include <vector> - -namespace omega { - -class CodeInsertion; - -typedef std::vector<CodeInsertion*> CodeInsertionPtrList; -typedef std::vector<CodeInsertion*>::iterator CodeInsertionPtrListItr; - -class CodeInsertion { -public: - int loop_level; - bool marked; - CodeInsertion(int looplevel) { this->loop_level = looplevel; marked = false; } - ~CodeInsertion() {} - virtual SgStatement* getStatement(SgScopeStatement* scopeStmt = NULL) = 0; -}; - -class PragmaInsertion : public CodeInsertion { -private: - std::string name; -public: - PragmaInsertion(int loop_level, const std::string &pragma) : CodeInsertion(loop_level) { this->name = std::string(pragma); } - ~PragmaInsertion() { } - virtual SgStatement* getStatement(SgScopeStatement* scopeStmt = NULL); -}; - -class MMPrefetchInsertion : public CodeInsertion { -private: - std::string arrName; - std::vector<std::string*> indecies; - std::vector<int> offsets; - int indexCount; - int cacheHint; - void initialize(const std::string& arrName, int hint); - void addDim(int offset); - void addDim(int offset, const std::string& indexer); - SgExpression* buildArrArg(SgScopeStatement* scopeStmt); - SgExpression* makeIndexExp(int dim, SgScopeStatement* scopeStmt); -public: - MMPrefetchInsertion(int loop_level, const std::string &arr, int hint) : CodeInsertion(loop_level) - { this->initialize(arr, hint); } - ~MMPrefetchInsertion() { } - virtual SgStatement* getStatement(SgScopeStatement* scopeStmt = NULL); -}; - -class CodeInsertionAttribute : public AstAttribute { -private: - std::vector<CodeInsertion*> code_insertions; -public: - CodeInsertionAttribute() { code_insertions = std::vector<CodeInsertion*>(); } - ~CodeInsertionAttribute() {} - - void add(CodeInsertion* ci) { code_insertions.push_back(ci); } - CodeInsertionPtrListItr begin() { return code_insertions.begin(); } - CodeInsertionPtrListItr end() { return code_insertions.end(); } - void remove(CodeInsertion* ci) { std::remove(code_insertions.begin(), code_insertions.end(), ci); } - int countCodeInsertions() { return code_insertions.size(); } -}; - -struct CodeInsertionMark { -public: - SgStatement* stmt; - CodeInsertion* ci; -}; - -class CodeInsertionVisitor : public AstPrePostProcessing { -private: - int loop_level; - std::vector<CodeInsertionMark*> ci_marks; - void markStmt(SgStatement* stmt, CodeInsertion* ci); -public: - void initialize(); - virtual void preOrderVisit(SgNode* n); - virtual void postOrderVisit(SgNode* n); - void insertCode(); -}; - -void postProcessRoseCodeInsertion(SgProject* proj); -void copyAttributes(SgNode* s, SgNode* d); -CodeInsertionAttribute* getOrCreateCodeInsertionAttribute(SgNode* node); - -} - -#endif diff --git a/omegalib/codegen/src/CG.cc b/omegalib/codegen/src/CG.cc deleted file mode 100644 index 42bd172..0000000 --- a/omegalib/codegen/src/CG.cc +++ /dev/null @@ -1,1163 +0,0 @@ -/***************************************************************************** - Copyright (C) 1994-2000 the Omega Project Team - Copyright (C) 2005-2011 Chun Chen - All Rights Reserved. - - Purpose: - CG node classes, used to build AST tree from polyhedra scanning. - - Notes: - Parameter "restriction" is always tighter than "known" since CG_split - node does not correspond to any code for enforcement. This property is - destroyed after hoistGuard since "restriction" is not used anymore. - CG node's children are guaranteed not to be NULL, either NULL child is - removed from the children or the parent node itself becomes NULL. - - History: - 04/20/96 printRepr added by D people. Lei Zhou - 10/24/06 hoistGuard added by chun - 08/03/10 collect CG classes into one place, by Chun Chen - 08/04/10 track dynamically substituted variables in printRepr, by chun - 04/02/11 rewrite the CG node classes, by chun - *****************************************************************************/ - -#include <typeinfo> -#include <assert.h> -#include <omega.h> -#include <code_gen/codegen.h> -#include <code_gen/CG.h> -#include <code_gen/CG_outputBuilder.h> -#include <code_gen/CG_stringBuilder.h> -#include <code_gen/CG_utils.h> -#include <code_gen/codegen_error.h> -#include <stack> -#include <string.h> - -namespace omega { - -extern std::vector<std::vector<int> > smtNonSplitLevels; -extern std::vector<std::vector<std::string> > loopIdxNames; //per stmt -extern std::vector<std::pair<int, std::string> > syncs; - -extern int checkLoopLevel; -extern int stmtForLoopCheck; -extern int upperBoundForLevel; -extern int lowerBoundForLevel; -extern bool fillInBounds; - -//----------------------------------------------------------------------------- -// Class: CG_result -//----------------------------------------------------------------------------- - -CG_outputRepr *CG_result::printRepr(CG_outputBuilder *ocg, - const std::vector<CG_outputRepr *> &stmts) const { - return printRepr(1, ocg, stmts, - std::vector<std::pair<CG_outputRepr *, int> >(num_level(), - std::make_pair(static_cast<CG_outputRepr *>(NULL), 0))); -} - -std::string CG_result::printString() const { - CG_stringBuilder ocg; - std::vector<CG_outputRepr *> stmts(codegen_->xforms_.size()); - for (int i = 0; i < stmts.size(); i++) - stmts[i] = new CG_stringRepr("s" + to_string(i)); - CG_stringRepr *repr = static_cast<CG_stringRepr *>(printRepr(&ocg, stmts)); - for (int i = 0; i < stmts.size(); i++) - delete stmts[i]; - - if (repr != NULL) { - std::string s = repr->GetString(); - delete repr; - return s; - } else - return std::string(); -} - -int CG_result::num_level() const { - return codegen_->num_level(); -} - -//----------------------------------------------------------------------------- -// Class: CG_split -//----------------------------------------------------------------------------- - -CG_result *CG_split::recompute(const BoolSet<> &parent_active, - const Relation &known, const Relation &restriction) { - active_ &= parent_active; - if (active_.empty()) { - delete this; - return NULL; - } - - - int i = 0; - while (i < restrictions_.size()) { - Relation new_restriction = Intersection(copy(restrictions_[i]), - copy(restriction)); - - new_restriction.simplify(2, 4); - //new_restriction.simplify(); - clauses_[i] = clauses_[i]->recompute(active_, copy(known), - new_restriction); - if (clauses_[i] == NULL) { - restrictions_.erase(restrictions_.begin() + i); - clauses_.erase(clauses_.begin() + i); - } else - i++; - } - - - if (restrictions_.size() == 0) { - delete this; - return NULL; - } else - return this; -} - -int CG_split::populateDepth() { - int max_depth = 0; - for (int i = 0; i < clauses_.size(); i++) { - int t = clauses_[i]->populateDepth(); - if (t > max_depth) - max_depth = t; - } - return max_depth; -} - -std::pair<CG_result *, Relation> CG_split::liftOverhead(int depth, - bool propagate_up) { - for (int i = 0; i < clauses_.size();) { - std::pair<CG_result *, Relation> result = clauses_[i]->liftOverhead( - depth, propagate_up); - if (result.first == NULL) - clauses_.erase(clauses_.begin() + i); - else { - clauses_[i] = result.first; - if (!result.second.is_obvious_tautology()) - return std::make_pair(this, result.second); - i++; - } - - } - - if (clauses_.size() == 0) { - delete this; - return std::make_pair(static_cast<CG_result *>(NULL), - Relation::True(num_level())); - } else - return std::make_pair(this, Relation::True(num_level())); -} - -Relation CG_split::hoistGuard() { - std::vector<Relation> guards; - for (int i = 0; i < clauses_.size(); i++) - guards.push_back(clauses_[i]->hoistGuard()); - - return SimpleHull(guards, true, true); -} - -void CG_split::removeGuard(const Relation &guard) { - for (int i = 0; i < clauses_.size(); i++) - clauses_[i]->removeGuard(guard); -} - -std::vector<CG_result *> CG_split::findNextLevel() const { - std::vector<CG_result *> result; - for (int i = 0; i < clauses_.size(); i++) { - CG_split *splt = dynamic_cast<CG_split *>(clauses_[i]); - if (splt != NULL) { - std::vector<CG_result *> t = splt->findNextLevel(); - result.insert(result.end(), t.begin(), t.end()); - } else - result.push_back(clauses_[i]); - } - - return result; -} - -CG_outputRepr *CG_split::printRepr(int indent, CG_outputBuilder *ocg, - const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const { - CG_outputRepr *stmtList = NULL; - std::vector<CG_result *> next_level = findNextLevel(); - - std::vector<CG_loop *> cur_loops; - for (int i = 0; i < next_level.size(); i++) { - CG_loop *lp = dynamic_cast<CG_loop *>(next_level[i]); - if (lp != NULL) { - cur_loops.push_back(lp); - } else { - stmtList = ocg->StmtListAppend(stmtList, - loop_print_repr(cur_loops, 0, cur_loops.size(), - Relation::True(num_level()), NULL, indent, ocg, - stmts, assigned_on_the_fly)); - stmtList = ocg->StmtListAppend(stmtList, - next_level[i]->printRepr(indent, ocg, stmts, - assigned_on_the_fly)); - cur_loops.clear(); - } - } - - stmtList = ocg->StmtListAppend(stmtList, - loop_print_repr(cur_loops, 0, cur_loops.size(), - Relation::True(num_level()), NULL, indent, ocg, stmts, - assigned_on_the_fly)); - return stmtList; -} - -CG_result *CG_split::clone() const { - std::vector<CG_result *> clauses(clauses_.size()); - for (int i = 0; i < clauses_.size(); i++) - clauses[i] = clauses_[i]->clone(); - return new CG_split(codegen_, active_, restrictions_, clauses); -} - -void CG_split::dump(int indent) const { - std::string prefix; - for (int i = 0; i < indent; i++) - prefix += " "; - std::cout << prefix << "SPLIT: " << active_ << std::endl; - for (int i = 0; i < restrictions_.size(); i++) { - std::cout << prefix << "restriction: "; - const_cast<CG_split *>(this)->restrictions_[i].print(); - clauses_[i]->dump(indent + 1); - } - -} - -//----------------------------------------------------------------------------- -// Class: CG_loop -//----------------------------------------------------------------------------- - -CG_result *CG_loop::recompute(const BoolSet<> &parent_active, - const Relation &known, const Relation &restriction) { - known_ = copy(known); - restriction_ = copy(restriction); - active_ &= parent_active; - - std::vector<Relation> Rs; - for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { - Relation r = Intersection(copy(restriction), - copy(codegen_->projected_IS_[level_ - 1][*i])); - - //r.simplify(2, 4); - r.simplify(); - if (!r.is_upper_bound_satisfiable()) { - active_.unset(*i); - continue; - } - Rs.push_back(copy(r)); - } - - if (active_.empty()) { - delete this; - return NULL; - } - - Relation hull = SimpleHull(Rs, true, true); - - //hull.simplify(2,4); - - // check if actual loop is needed - std::pair<EQ_Handle, int> result = find_simplest_assignment(hull, - hull.set_var(level_)); - if (result.second < INT_MAX) { - needLoop_ = false; - - bounds_ = Relation(hull.n_set()); - F_Exists *f_exists = bounds_.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(bounds_.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2 = replicate_floor_definition(hull, v, bounds_, - f_exists, f_root, exists_mapping); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = bounds_.get_local(g); - else - v2 = bounds_.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const(result.first.get_const()); - bounds_.simplify(); - } - // loop iterates more than once, extract bounds now - else { - needLoop_ = true; - - bounds_ = Relation(hull.n_set()); - F_Exists *f_exists = bounds_.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - - Relation b = Gist(copy(hull), copy(known), 1); - bool has_unresolved_bound = false; - - std::set<Variable_ID> excluded_floor_vars; - excluded_floor_vars.insert(b.set_var(level_)); - for (GEQ_Iterator e(b.single_conjunct()->GEQs()); e; e++) - if ((*e).get_coef(b.set_var(level_)) != 0) { - bool is_bound = true; - for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) { - std::pair<bool, GEQ_Handle> result = find_floor_definition( - b, cvi.curr_var(), excluded_floor_vars); - if (!result.first) { - is_bound = false; - has_unresolved_bound = true; - break; - } - } - - if (!is_bound) - continue; - - GEQ_Handle h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(bounds_.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2 = replicate_floor_definition(b, v, - bounds_, f_exists, f_root, exists_mapping); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = bounds_.get_local(g); - else - v2 = bounds_.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const((*e).get_const()); - } - - if (has_unresolved_bound) { - b = Approximate(b); - b.simplify(2, 4); - //Simplification of Hull - hull = Approximate(hull); - hull.simplify(2, 4); - //end : Anand - for (GEQ_Iterator e(b.single_conjunct()->GEQs()); e; e++) - if ((*e).get_coef(b.set_var(level_)) != 0) - f_root->add_GEQ(*e); - } - bounds_.simplify(); - hull.simplify(2,4); - // Since current SimpleHull does not support max() upper bound or min() lower bound, - // we have to forcefully split the loop when hull approximation does not return any bound. - bool has_lb = false; - bool has_ub = false; - for (GEQ_Iterator e = bounds_.single_conjunct()->GEQs(); e; e++) { - if ((*e).get_coef(bounds_.set_var(level_)) > 0) - has_lb = true; - else if ((*e).get_coef(bounds_.set_var(level_)) < 0) - has_ub = true; - if (has_lb && has_ub) - break; - } - - if (!has_lb) { - for (int i = 0; i < Rs.size(); i++) { - Relation r = Approximate(copy(Rs[i])); - r.simplify(2, 4); - for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++) - if ((*e).get_coef(r.input_var(level_)) > 0) { - Relation r2 = Relation::True(num_level()); - r2.and_with_GEQ(*e); - r2.simplify(); - std::vector<Relation> restrictions(2); - restrictions[0] = Complement(copy(r2)); - restrictions[0].simplify(); - restrictions[1] = r2; - std::vector<CG_result *> clauses(2); - clauses[0] = this; - clauses[1] = this->clone(); - CG_result *cgr = new CG_split(codegen_, active_, - restrictions, clauses); - cgr = cgr->recompute(active_, copy(known), - copy(restriction)); - return cgr; - } - } - for (int i = 0; i < Rs.size(); i++) { - Relation r = Approximate(copy(Rs[i])); - r.simplify(2, 4); - for (EQ_Iterator e = r.single_conjunct()->EQs(); e; e++) - if ((*e).get_coef(r.input_var(level_)) != 0) { - Relation r2 = Relation::True(num_level()); - r2.and_with_GEQ(*e); - r2.simplify(); - std::vector<Relation> restrictions(2); - if ((*e).get_coef(r.input_var(level_)) > 0) { - restrictions[0] = Complement(copy(r2)); - restrictions[0].simplify(); - restrictions[1] = r2; - } else { - restrictions[0] = r2; - restrictions[1] = Complement(copy(r2)); - restrictions[1].simplify(); - } - std::vector<CG_result *> clauses(2); - clauses[0] = this; - clauses[1] = this->clone(); - CG_result *cgr = new CG_split(codegen_, active_, - restrictions, clauses); - cgr = cgr->recompute(active_, copy(known), - copy(restriction)); - return cgr; - } - } - } else if (!has_ub) { - for (int i = 0; i < Rs.size(); i++) { - Relation r = Approximate(copy(Rs[i])); - r.simplify(2, 4); - for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++) - if ((*e).get_coef(r.input_var(level_)) < 0) { - Relation r2 = Relation::True(num_level()); - r2.and_with_GEQ(*e); - r2.simplify(); - std::vector<Relation> restrictions(2); - restrictions[1] = Complement(copy(r2)); - restrictions[1].simplify(); - restrictions[0] = r2; - std::vector<CG_result *> clauses(2); - clauses[0] = this; - clauses[1] = this->clone(); - CG_result *cgr = new CG_split(codegen_, active_, - restrictions, clauses); - cgr = cgr->recompute(active_, copy(known), - copy(restriction)); - return cgr; - } - } - for (int i = 0; i < Rs.size(); i++) { - Relation r = Approximate(copy(Rs[i])); - r.simplify(2, 4); - for (EQ_Iterator e = r.single_conjunct()->EQs(); e; e++) - if ((*e).get_coef(r.input_var(level_)) != 0) { - Relation r2 = Relation::True(num_level()); - r2.and_with_GEQ(*e); - r2.simplify(); - std::vector<Relation> restrictions(2); - if ((*e).get_coef(r.input_var(level_)) > 0) { - restrictions[0] = Complement(copy(r2)); - restrictions[0].simplify(); - restrictions[1] = r2; - } else { - restrictions[0] = r2; - restrictions[1] = Complement(copy(r2)); - restrictions[1].simplify(); - } - std::vector<CG_result *> clauses(2); - clauses[0] = this; - clauses[1] = this->clone(); - CG_result *cgr = new CG_split(codegen_, active_, - restrictions, clauses); - cgr = cgr->recompute(active_, copy(known), - copy(restriction)); - return cgr; - } - } - } - - if (!has_lb && !has_ub) - throw codegen_error( - "can't find any bound at loop level " + to_string(level_)); - else if (!has_lb) - throw codegen_error( - "can't find lower bound at loop level " - + to_string(level_)); - else if (!has_ub) - throw codegen_error( - "can't find upper bound at loop level " - + to_string(level_)); - } - bounds_.copy_names(hull); - bounds_.setup_names(); - - // additional guard/stride condition extraction - if (needLoop_) { - Relation cur_known = Intersection(copy(bounds_), copy(known_)); - cur_known.simplify(); - hull = Gist(hull, copy(cur_known), 1); - - std::pair<EQ_Handle, Variable_ID> result = find_simplest_stride(hull, - hull.set_var(level_)); - if (result.second != NULL) - if (abs(result.first.get_coef(hull.set_var(level_))) == 1) { - F_Exists *f_exists = bounds_.and_with_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(bounds_.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2; - if (v == result.second) - v2 = f_exists->declare(); - else - v2 = replicate_floor_definition(hull, v, bounds_, - f_exists, f_root, exists_mapping); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = bounds_.get_local(g); - else - v2 = bounds_.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const(result.first.get_const()); - } else { - // since gist is not powerful enough on modular constraints for now, - // make an educated guess - coef_t stride = abs(result.first.get_coef(result.second)) - / gcd(abs(result.first.get_coef(result.second)), - abs( - result.first.get_coef( - hull.set_var(level_)))); - - Relation r1(hull.n_inp()); - F_Exists *f_exists = r1.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(r1.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2; - if (v == result.second) - v2 = f_exists->declare(); - else - v2 = replicate_floor_definition(hull, v, r1, - f_exists, f_root, exists_mapping); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r1.get_local(g); - else - v2 = r1.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const(result.first.get_const()); - r1.simplify(); - - bool guess_success = false; - for (GEQ_Iterator e(bounds_.single_conjunct()->GEQs()); e; e++) - if ((*e).get_coef(bounds_.set_var(level_)) == 1) { - Relation r2(hull.n_inp()); - F_Exists *f_exists = r2.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - EQ_Handle h = f_root->add_EQ(); - h.update_coef(f_exists->declare(), stride); - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h.update_coef(r2.input_var(v->get_position()), - cvi.curr_coef()); - break; - case Wildcard_Var: { - Variable_ID v2 = replicate_floor_definition( - hull, v, r2, f_exists, f_root, - exists_mapping); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r2.get_local(g); - else - v2 = r2.get_local(g, v->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const((*e).get_const()); - r2.simplify(); - - if (Gist(copy(r1), - Intersection(copy(cur_known), copy(r2)), 1).is_obvious_tautology() - && Gist(copy(r2), - Intersection(copy(cur_known), copy(r1)), - 1).is_obvious_tautology()) { - bounds_ = Intersection(bounds_, r2); - bounds_.simplify(); - guess_success = true; - break; - } - } - - // this is really a stride with non-unit coefficient for this loop variable - if (!guess_success) { - // TODO: for stride ax = b mod n it might be beneficial to - // generate modular linear equation solver code for - // runtime to get the starting position in printRepr, - // and stride would be n/gcd(|a|,n), thus this stride - // can be put into bounds_ too. - } - - } - - hull = Project(hull, hull.set_var(level_)); - hull.simplify(2, 4); - guard_ = Gist(hull, Intersection(copy(bounds_), copy(known_)), 1); - } - // don't generate guard for non-actual loop, postpone it. otherwise - // redundant if-conditions might be generated since for-loop semantics - // includes implicit comparison checking. -- by chun 09/14/10 - else - guard_ = Relation::True(num_level()); - guard_.copy_names(bounds_); - guard_.setup_names(); - - //guard_.simplify(); - // recursively down the AST - Relation new_known = Intersection(copy(known), - Intersection(copy(bounds_), copy(guard_))); - new_known.simplify(2, 4); - Relation new_restriction = Intersection(copy(restriction), - Intersection(copy(bounds_), copy(guard_))); - new_restriction.simplify(2, 4); - body_ = body_->recompute(active_, new_known, new_restriction); - if (body_ == NULL) { - delete this; - return NULL; - } else - return this; -} - -int CG_loop::populateDepth() { - int depth = body_->populateDepth(); - if (needLoop_) - depth_ = depth + 1; - else - depth_ = depth; - return depth_; -} - -std::pair<CG_result *, Relation> CG_loop::liftOverhead(int depth, - bool propagate_up) { - if (depth_ > depth) { - assert(propagate_up == false); - std::pair<CG_result *, Relation> result = body_->liftOverhead(depth, - false); - body_ = result.first; - return std::make_pair(this, Relation::True(num_level())); - } else { // (depth_ <= depth) - if (propagate_up) { - Relation r = pick_one_guard(guard_, level_); - if (!r.is_obvious_tautology()) - return std::make_pair(this, r); - } - - std::pair<CG_result *, Relation> result; - if (propagate_up || needLoop_) - result = body_->liftOverhead(depth, true); - else - result = body_->liftOverhead(depth, false); - body_ = result.first; - if (result.second.is_obvious_tautology()) - return std::make_pair(this, result.second); - - // loop is an assignment, replace this loop variable in overhead condition - if (!needLoop_) { - result.second = Intersection(result.second, copy(bounds_)); - result.second = Project(result.second, - result.second.set_var(level_)); - result.second.simplify(2, 4); - } - - - int max_level = 0; - bool has_wildcard = false; - bool direction = true; - for (EQ_Iterator e(result.second.single_conjunct()->EQs()); e; e++) - if ((*e).has_wildcards()) { - if (has_wildcard) - assert(false); - else - has_wildcard = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - } else - assert(false); - - if (!has_wildcard) { - int num_simple_geq = 0; - for (GEQ_Iterator e(result.second.single_conjunct()->GEQs()); e; - e++) - if (!(*e).has_wildcards()) { - num_simple_geq++; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) { - max_level = cvi.curr_var()->get_position(); - direction = (cvi.curr_coef() < 0) ? true : false; - } - } else { - has_wildcard = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) { - max_level = cvi.curr_var()->get_position(); - } - } - assert( - (has_wildcard && num_simple_geq == 0) || (!has_wildcard && num_simple_geq == 1)); - } - - // check if this is the top loop level for splitting for this overhead - if (!propagate_up || (has_wildcard && max_level == level_ - 1) - || (!has_wildcard && max_level == level_)) { - std::vector<Relation> restrictions(2); - std::vector<CG_result *> clauses(2); - int saved_num_level = num_level(); - if (has_wildcard || direction) { - restrictions[1] = Complement(copy(result.second)); - restrictions[1].simplify(); - clauses[1] = this->clone(); - restrictions[0] = result.second; - clauses[0] = this; - } else { - restrictions[0] = Complement(copy(result.second)); - restrictions[0].simplify(); - clauses[0] = this->clone(); - restrictions[1] = result.second; - clauses[1] = this; - } - CG_result *cgr = new CG_split(codegen_, active_, restrictions, - clauses); - CG_result *new_cgr = cgr->recompute(active_, copy(known_), - copy(restriction_)); - new_cgr->populateDepth(); - assert(new_cgr==cgr); - if (static_cast<CG_split *>(new_cgr)->clauses_.size() == 1) - // infinite recursion detected, bail out - return std::make_pair(new_cgr, Relation::True(saved_num_level)); - else - return cgr->liftOverhead(depth, propagate_up); - } else - return std::make_pair(this, result.second); - } -} - -Relation CG_loop::hoistGuard() { - - Relation r = body_->hoistGuard(); - - // TODO: should bookkeep catched contraints in loop output as enforced and check if anything missing - // if (!Gist(copy(b), copy(enforced)).is_obvious_tautology()) { - // fprintf(stderr, "need to generate extra guard inside the loop\n"); - // } - - if (!needLoop_) - r = Intersection(r, copy(bounds_)); - r = Project(r, r.set_var(level_)); - r = Gist(r, copy(known_), 1); - - Relation eliminate_existentials_r; - Relation eliminate_existentials_known; - - eliminate_existentials_r = copy(r); - if (!r.is_obvious_tautology()) { - eliminate_existentials_r = Approximate(copy(r)); - eliminate_existentials_r.simplify(2,4); - eliminate_existentials_known = Approximate(copy(known_)); - eliminate_existentials_known.simplify(2,4); - - eliminate_existentials_r = Gist( eliminate_existentials_r, eliminate_existentials_known, 1); - } - - - if (!eliminate_existentials_r.is_obvious_tautology()) { - // if (!r.is_obvious_tautology()) { - body_->removeGuard(r); - guard_ = Intersection(guard_, copy(r)); - guard_.simplify(); - } - - return guard_; - - // return ifList; - // } - - -} - -void CG_loop::removeGuard(const Relation &guard) { - known_ = Intersection(known_, copy(guard)); - known_.simplify(); - - guard_ = Gist(guard_, copy(known_), 1); - guard_.copy_names(known_); - guard_.setup_names(); -} - -CG_outputRepr *CG_loop::printRepr(int indent, CG_outputBuilder *ocg, - const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const { - return printRepr(true, indent, ocg, stmts, assigned_on_the_fly); -} - -CG_outputRepr *CG_loop::printRepr(bool do_print_guard, int indent, - CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const { - CG_outputRepr *guardRepr; - if (do_print_guard) - guardRepr = output_guard(ocg, guard_, assigned_on_the_fly); - else - guardRepr = NULL; - - Relation cur_known = Intersection(copy(known_), copy(guard_)); - cur_known.simplify(); - if (needLoop_) { - - if (checkLoopLevel) - if (level_ == checkLoopLevel) - if (active_.get(stmtForLoopCheck)) - fillInBounds = true; - - CG_outputRepr *ctrlRepr = output_loop(ocg, bounds_, level_, cur_known, - assigned_on_the_fly); - - fillInBounds = false; - - CG_outputRepr *bodyRepr = body_->printRepr( - (guardRepr == NULL) ? indent + 1 : indent + 2, ocg, stmts, - assigned_on_the_fly); - CG_outputRepr * loopRepr; - - if (guardRepr == NULL) - loopRepr = ocg->CreateLoop(indent, ctrlRepr, bodyRepr); - else - loopRepr = ocg->CreateLoop(indent + 1, ctrlRepr, bodyRepr); - - if (!smtNonSplitLevels.empty()) { - bool blockLoop = false; - bool threadLoop = false; - bool sync = false; - int firstActiveStmt = -1; - for (int s = 0; s < active_.size(); s++) { - if (active_.get(s)) { - if (firstActiveStmt < 0) - firstActiveStmt = s; - //We assume smtNonSplitLevels is only used to mark the first of - //the block or thread loops to be reduced in CUDA-CHiLL. Here we - //place some comments to help with final code generation. - //int idx = smtNonSplitLevels[s].index(level_); - - if (s < smtNonSplitLevels.size()) { - if (smtNonSplitLevels[s].size() > 0) - if (smtNonSplitLevels[s][0] == level_) { - blockLoop = true; - } - //Assume every stmt marked with a thread loop index also has a block loop idx - if (smtNonSplitLevels[s].size() > 1) - if (smtNonSplitLevels[s][1] == level_) { - threadLoop = true; - } - } - } - } - if (blockLoop && threadLoop) { - fprintf(stderr, - "Warning, have %d level more than once in smtNonSplitLevels\n", - level_); - threadLoop = false; - } - std::string preferredIdx; - if (loopIdxNames.size() - && (level_ / 2) - 1 < loopIdxNames[firstActiveStmt].size()) - preferredIdx = loopIdxNames[firstActiveStmt][(level_ / 2) - 1]; - for (int s = 0; s < active_.size(); s++) { - if (active_.get(s)) { - for (int i = 0; i < syncs.size(); i++) { - if (syncs[i].first == s - && strcmp(syncs[i].second.c_str(), - preferredIdx.c_str()) == 0) { - sync = true; - //printf("FOUND SYNC\n"); - } - - } - } - - } - if (threadLoop || blockLoop || preferredIdx.length() != 0) { - char buf[1024]; - std::string loop; - if (blockLoop) - loop = "blockLoop "; - if (threadLoop) - loop = "threadLoop "; - if (preferredIdx.length() != 0 && sync) { - sprintf(buf, "~cuda~ %spreferredIdx: %s sync", loop.c_str(), - preferredIdx.c_str()); - } else if (preferredIdx.length() != 0) { - sprintf(buf, "~cuda~ %spreferredIdx: %s", loop.c_str(), - preferredIdx.c_str()); - } else { - sprintf(buf, "~cuda~ %s", loop.c_str()); - } - - - loopRepr = ocg->CreateAttribute(loopRepr, buf); - } - - } - if (guardRepr == NULL) - return loopRepr; - else - return ocg->CreateIf(indent, guardRepr, loopRepr, NULL); - } else { - std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > result = - output_assignment(ocg, bounds_, level_, cur_known, - assigned_on_the_fly); - guardRepr = ocg->CreateAnd(guardRepr, result.first); - - if (result.second.second < CodeGen::var_substitution_threshold) { - std::vector<std::pair<CG_outputRepr *, int> > atof = - assigned_on_the_fly; - atof[level_ - 1] = result.second; - CG_outputRepr *bodyRepr = body_->printRepr( - (guardRepr == NULL) ? indent : indent + 1, ocg, stmts, - atof); - delete atof[level_ - 1].first; - if (guardRepr == NULL) - return bodyRepr; - else - return ocg->CreateIf(indent, guardRepr, bodyRepr, NULL); - } else { - CG_outputRepr *assignRepr = ocg->CreateAssignment( - (guardRepr == NULL) ? indent : indent + 1, - output_ident(ocg, bounds_, - const_cast<CG_loop *>(this)->bounds_.set_var( - level_), assigned_on_the_fly), - result.second.first); - CG_outputRepr *bodyRepr = body_->printRepr( - (guardRepr == NULL) ? indent : indent + 1, ocg, stmts, - assigned_on_the_fly); - if (guardRepr == NULL) - return ocg->StmtListAppend(assignRepr, bodyRepr); - else - return ocg->CreateIf(indent, guardRepr, - ocg->StmtListAppend(assignRepr, bodyRepr), NULL); - } - - } -} - -CG_result *CG_loop::clone() const { - return new CG_loop(codegen_, active_, level_, body_->clone()); -} - -void CG_loop::dump(int indent) const { - std::string prefix; - for (int i = 0; i < indent; i++) - prefix += " "; - std::cout << prefix << "LOOP (level " << level_ << "): " << active_ - << std::endl; - std::cout << prefix << "known: "; - const_cast<CG_loop *>(this)->known_.print(); - std::cout << prefix << "restriction: "; - const_cast<CG_loop *>(this)->restriction_.print(); - std::cout << prefix << "bounds: "; - const_cast<CG_loop *>(this)->bounds_.print(); - std::cout << prefix << "guard: "; - const_cast<CG_loop *>(this)->guard_.print(); - body_->dump(indent + 1); -} - -//----------------------------------------------------------------------------- -// Class: CG_leaf -//----------------------------------------------------------------------------- - -CG_result* CG_leaf::recompute(const BoolSet<> &parent_active, - const Relation &known, const Relation &restriction) { - active_ &= parent_active; - known_ = copy(known); - - guards_.clear(); - for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { - Relation r = Intersection( - copy(codegen_->projected_IS_[num_level() - 1][*i]), - copy(restriction)); - r.simplify(2, 4); - if (!r.is_upper_bound_satisfiable()) - active_.unset(*i); - else { - r = Gist(r, copy(known), 1); - if (!r.is_obvious_tautology()) { - guards_[*i] = r; - guards_[*i].copy_names(known); - guards_[*i].setup_names(); - } - } - } - - - if (active_.empty()) { - delete this; - return NULL; - } else - return this; -} - -std::pair<CG_result *, Relation> CG_leaf::liftOverhead(int depth, bool) { - if (depth == 0) - return std::make_pair(this, Relation::True(num_level())); - - for (std::map<int, Relation>::iterator i = guards_.begin(); - i != guards_.end(); i++) { - Relation r = pick_one_guard(i->second); - if (!r.is_obvious_tautology()) { - bool has_wildcard = false; - int max_level = 0; - for (EQ_Iterator e(r.single_conjunct()->EQs()); e; e++) { - if ((*e).has_wildcards()) - has_wildcard = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - } - for (GEQ_Iterator e(r.single_conjunct()->GEQs()); e; e++) { - if ((*e).has_wildcards()) - has_wildcard = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var()->kind() == Input_Var - && cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - } - - if (!(has_wildcard && max_level == codegen_->num_level())) - return std::make_pair(this, r); - } - } - - return std::make_pair(this, Relation::True(num_level())); -} - -Relation CG_leaf::hoistGuard() { - std::vector<Relation> guards; - for (BoolSet<>::iterator i = active_.begin(); i != active_.end(); i++) { - std::map<int, Relation>::iterator j = guards_.find(*i); - if (j == guards_.end()) { - Relation r = Relation::True(num_level()); - r.copy_names(known_); - r.setup_names(); - return r; - } else { - guards.push_back(j->second); - } - } - - return SimpleHull(guards, true, true); -} - -void CG_leaf::removeGuard(const Relation &guard) { - known_ = Intersection(known_, copy(guard)); - known_.simplify(); - - std::map<int, Relation>::iterator i = guards_.begin(); - while (i != guards_.end()) { - i->second = Gist(i->second, copy(known_), 1); - if (i->second.is_obvious_tautology()) - guards_.erase(i++); - else - ++i; - } -} - -CG_outputRepr *CG_leaf::printRepr(int indent, CG_outputBuilder *ocg, - const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) const { - return leaf_print_repr(active_, guards_, NULL, known_, indent, ocg, - codegen_->remap_, codegen_->xforms_, stmts, assigned_on_the_fly); -} - -CG_result *CG_leaf::clone() const { - return new CG_leaf(codegen_, active_); -} - -void CG_leaf::dump(int indent) const { - std::string prefix; - for (int i = 0; i < indent; i++) - prefix += " "; - std::cout << prefix << "LEAF: " << active_ << std::endl; - std::cout << prefix << "known: "; - const_cast<CG_leaf *>(this)->known_.print(); - for (std::map<int, Relation>::const_iterator i = guards_.begin(); - i != guards_.end(); i++) { - std::cout << prefix << "guard #" << i->first << ":"; - const_cast<Relation &>(i->second).print(); - } -} - -} diff --git a/omegalib/codegen/src/CG_roseBuilder.cc b/omegalib/codegen/src/CG_roseBuilder.cc deleted file mode 100644 index 7e12634..0000000 --- a/omegalib/codegen/src/CG_roseBuilder.cc +++ /dev/null @@ -1,1093 +0,0 @@ -/***************************************************************************** - Copyright (C) 2008 University of Southern California - Copyright (C) 2009-2010 University of Utah - All Rights Reserved. - - Purpose: - generate suif code for omega - - Notes: - - History: - 02/01/06 created by Chun Chen - *****************************************************************************/ - -#include <stack> -#include <code_gen/CG_roseBuilder.h> -#include <string> - -struct ir_error: public std::runtime_error { - ir_error(const std::string &msg) : - std::runtime_error(msg) { - } -}; - -using namespace SageBuilder; -using namespace SageInterface; -using namespace OmpSupport; - -namespace omega { - -//----------------------------------------------------------------------------- -// make suif initilization happy -//----------------------------------------------------------------------------- -char *k_ocg_comment; - -CG_roseBuilder::CG_roseBuilder(int is_fortran, SgGlobal* global, SgGlobal* firstScope, - SgSymbolTable* symtab, SgSymbolTable* symtab2, SgNode* root) : - isFortran(is_fortran), global_(global), global_scope(firstScope), symtab_(symtab), symtab2_( - symtab2), root_(root) { -} - - -CG_roseBuilder::~CG_roseBuilder() { -} - -// Manu:: returns true if input is in fortran, else returns false -bool CG_roseBuilder::isInputFortran() const{ - if (isFortran) - return true; - else - return false; -} - -//----------------------------------------------------------------------------- -// place holder generation -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateSubstitutedStmt(int, CG_outputRepr *stmt, - const std::vector<std::string> &vars, std::vector<CG_outputRepr*> &subs) const { - - SgStatementPtrList* list = static_cast<CG_roseRepr *>(stmt)->list_; - SgNode *tnl; - SgStatement* statement; - if (list != NULL) { - delete stmt; - for (int i = 0; i < subs.size(); i++) { - if (subs[i] == NULL) - continue; - - CG_roseRepr *repr = static_cast<CG_roseRepr*>(subs[i]); - SgExpression* op = repr->op_; - - for (SgStatementPtrList::iterator it = (*list).begin(); - it != (*list).end(); it++) { - statement = (*it); - tnl = isSgNode(statement); - - int j; - int not_in_symtab_; - - not_in_symtab_ = 0; - - SgVariableSymbol *vs = symtab_->find_variable( - SgName(vars[i].c_str())); - - if (vs == NULL) { - - not_in_symtab_ = 1; - - vs = symtab2_->find_variable(SgName(vars[i].c_str())); - } - if (vs != NULL) { - - std::vector<SgVarRefExp *> array = substitute(tnl, - (const SgVariableSymbol*) vs, op, root_); - for (std::vector<SgVarRefExp *>::iterator it = - array.begin(); it != array.end(); it++) { - - if (isSgVarRefExp(op)) { - if (strcmp( - isSgVarRefExp(op)->get_symbol()->get_name().getString().c_str(), - vs->get_name().getString().c_str())) { - - (*it)->set_symbol( - isSgVarRefExp(op)->get_symbol()); - - } - } else if (isSgExpression(op)) { - - if (isSgBinaryOp((*it)->get_parent())) - isSgBinaryOp((*it)->get_parent())->replace_expression( - *it, op); - else if (isSgUnaryOp((*it)->get_parent())) - isSgUnaryOp((*it)->get_parent())->replace_expression( - *it, op); - else if (isSgExprListExp((*it)->get_parent())) - isSgExprListExp((*it)->get_parent())->replace_expression( - *it, op); - else - throw ir_error("unrecognized expression type"); - } - - } - } - - } - - delete repr; - subs[i] = NULL; - - if (subs[i] != NULL) - throw ir_error("not freed properly"); - - } - - return new CG_roseRepr(list); - - } else { - tnl = static_cast<CG_roseRepr *>(stmt)->tnl_; - - if (tnl == NULL) - throw ir_error("both list and tnl are null!!"); - - delete stmt; - int j; - int not_in_symtab_; - for (int i = 0; i < subs.size(); i++) { - if (subs[i] == NULL) - continue; - not_in_symtab_ = 0; - - - CG_roseRepr *repr = static_cast<CG_roseRepr*>(subs[i]); - SgExpression* op = repr->op_; - delete repr; - subs[i] = NULL; - - SgVariableSymbol *vs = symtab_->find_variable( - SgName(vars[i].c_str())); - - if (vs == NULL) { - - not_in_symtab_ = 1; - - vs = symtab2_->find_variable(SgName(vars[i].c_str())); - } - if (vs != NULL) { - std::vector<SgVarRefExp *> array = substitute(tnl, vs, op, - root_); - - if (not_in_symtab_ && isSgVarRefExp(op)) { - if (strcmp( - isSgVarRefExp(op)->get_symbol()->get_name().getString().c_str(), - vs->get_name().getString().c_str())) { - } - } - - for (std::vector<SgVarRefExp *>::iterator j = array.begin(); - j != array.end(); j++) { - - if (isSgVarRefExp(op)) { - if (strcmp( - isSgVarRefExp(op)->get_symbol()->get_name().getString().c_str(), - vs->get_name().getString().c_str())) { - (*j)->set_symbol(isSgVarRefExp(op)->get_symbol()); - - } - } else if (isSgExpression(op)) { - - if (isSgBinaryOp((*j)->get_parent())) - isSgBinaryOp((*j)->get_parent())->replace_expression( - *j, op); - else if (isSgUnaryOp((*j)->get_parent())) - isSgUnaryOp((*j)->get_parent())->replace_expression( - *j, op); - else if (isSgExprListExp((*j)->get_parent())) { // Manu:: fortran indices are stored this way - isSgExprListExp((*j)->get_parent())->replace_expression(*j, op); - } - else - throw ir_error("unrecognized expression type"); - - } - - } - } - } - return new CG_roseRepr(tnl); - } - -} - -//----------------------------------------------------------------------------- -// assignment generation -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateAssignment(int, CG_outputRepr *lhs, - CG_outputRepr *rhs) const { - if (lhs == NULL || rhs == NULL) { - fprintf(stderr, "Code generation: Missing lhs or rhs\n"); - return NULL; - } - - SgExpression* src = static_cast<CG_roseRepr*>(rhs)->op_; - SgExpression* dst = static_cast<CG_roseRepr*>(lhs)->op_; - - SgExprStatement* ins = buildAssignStatement(dst, src); - src->set_parent(ins); - dst->set_parent(ins); - - SgStatementPtrList* new_list = new SgStatementPtrList; - - (*new_list).push_back(isSgStatement(ins)); - - delete lhs; - delete rhs; - - return new CG_roseRepr(new_list); - -} - -//----------------------------------------------------------------------------- -// function invocation generation -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateInvoke(const std::string &fname, - std::vector<CG_outputRepr *> &list) const { - - if (fname == std::string("max") || fname == std::string("min")) { - if (list.size() == 0) { - return NULL; - } else if (list.size() == 1) { - return list[0]; - } else { - int last = list.size() - 1; - SgExpression* op2 = static_cast<CG_roseRepr*>(list[last])->op_; - delete list[last]; - list.erase(list.end()-1); - CG_roseRepr *repr = static_cast<CG_roseRepr*>(CreateInvoke(fname, - list)); - SgExpression* op1 = repr->op_; - - - SgExpression *ins; - SgExprListExp* arg_list = buildExprListExp(); - appendExpression(arg_list, op1); - appendExpression(arg_list, op2); - SgVarRefExp* opaque_var; - - - if (fname == std::string("max")) { - opaque_var = buildOpaqueVarRefExp("__rose_gt", global_); - ins = isSgExpression(buildFunctionCallExp(opaque_var, arg_list)); - - // Manu:: fortran support - if (isInputFortran()) { - SgName fName("merge"); - SgTypeInt *retType = buildIntType(); - - SgExpression *cond = static_cast<CG_roseRepr *>(CreateLE(new CG_roseRepr(op2), new CG_roseRepr(op1)))->op_; - appendExpression(arg_list, cond); - ins = isSgExpression(buildFunctionCallExp(fName, retType, arg_list, global_)); - } - - } else { - opaque_var = buildOpaqueVarRefExp("__rose_lt", global_); - ins = isSgExpression(buildFunctionCallExp(opaque_var, arg_list)); - - // Manu:: fortran support - if (isInputFortran()) { - SgName fName("merge"); - SgTypeInt *retType = buildIntType(); - - SgExpression *cond = static_cast<CG_roseRepr *>(CreateLE(new CG_roseRepr(op1), new CG_roseRepr(op2)))->op_; - appendExpression(arg_list, cond); - ins = isSgExpression(buildFunctionCallExp(fName, retType, arg_list, global_)); - } - - } - - repr->op_ = ins; - return repr; - } - } else { - fprintf(stderr, - "Code generation: invoke function io_call not implemented\n"); - return NULL; - } - -} - -//----------------------------------------------------------------------------- -// comment generation -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateComment(int, - const std::string &commentText) const { - if (commentText == std::string("")) { - return NULL; - } - - SgLocatedNode *tnl = new SgLocatedNode(); - buildComment(tnl, "//omega_comment: " + commentText); - - return new CG_roseRepr(isSgNode(tnl)); - -} - -//----------------------------------------------------------------------------- -// if stmt gen operations -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateIf(int, CG_outputRepr *guardList, - CG_outputRepr *true_stmtList, CG_outputRepr *false_stmtList) const { - - if (true_stmtList == NULL && false_stmtList == NULL) { - delete guardList; - return NULL; - } else if (guardList == NULL) { - return StmtListAppend(true_stmtList, false_stmtList); - } - - SgExpression* header = static_cast<CG_roseRepr*>(guardList)->op_; - - SgStatementPtrList *then_part1, *else_part1; - SgStatement* then_part; - SgStatement* else_part; - SgBasicBlock* then_part2; - SgBasicBlock* else_part2; - if (true_stmtList != NULL) { - then_part1 = static_cast<CG_roseRepr*>(true_stmtList)->list_; - if (then_part1 != NULL) { - then_part = *((*then_part1).begin()); - - if ((*then_part1).size() > 1) { - then_part2 = buildBasicBlock(); - for (SgStatementPtrList::iterator it = (*then_part1).begin(); - it != (*then_part1).end(); it++) { - then_part2->append_statement(*it); - - } - then_part = isSgStatement(then_part2); - - } - } else { - // Manu:: fortran support (if part) - if (isInputFortran()) { - then_part2 = buildBasicBlock(); - then_part2->append_statement(isSgStatement(static_cast<CG_roseRepr*>(true_stmtList)->tnl_)); - then_part = isSgStatement(then_part2); - } else - then_part = isSgStatement(static_cast<CG_roseRepr*>(true_stmtList)->tnl_); - } - } else { - then_part = NULL; - } - if (false_stmtList != NULL) { - else_part1 = static_cast<CG_roseRepr*>(false_stmtList)->list_; - if (else_part1 != NULL) { - else_part = *((*else_part1).begin()); - if ((*else_part1).size() > 1) { - else_part2 = buildBasicBlock(); - for (SgStatementPtrList::iterator it2 = (*else_part1).begin(); - it2 != (*else_part1).end(); it2++) { - else_part2->append_statement(*it2); - - } - else_part = isSgStatement(else_part2); - - } - } else { - // Manu:: fortran support (if part) - if (isInputFortran()) { - else_part2 = buildBasicBlock(); - else_part2->append_statement(isSgStatement(static_cast<CG_roseRepr*>(false_stmtList)->tnl_)); - else_part = isSgStatement(else_part2); - } else - else_part = isSgStatement(static_cast<CG_roseRepr*>(false_stmtList)->tnl_); - } - } else { - else_part = NULL; - } - - SgIfStmt* ti = buildIfStmt(header, isSgStatement(then_part), - isSgStatement(else_part)); - - delete guardList; - delete true_stmtList; - delete false_stmtList; - - return new CG_roseRepr(isSgNode(ti)); - -} - -//----------------------------------------------------------------------------- -// inductive variable generation, to be used in CreateLoop as control -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateInductive(CG_outputRepr *index, - CG_outputRepr *lower, CG_outputRepr *upper, CG_outputRepr *step) const { - - if (index == NULL || lower == NULL || upper == NULL) { - fprintf(stderr, - "Code generation: something wrong in CreateInductive\n"); - return NULL; - } - - if (step == NULL) - step = new CG_roseRepr(isSgExpression(buildIntVal(1))); - - SgVarRefExp *index_sym = isSgVarRefExp( - static_cast<CG_roseRepr*>(index)->op_); - SgExpression* lower_bound = static_cast<CG_roseRepr*>(lower)->op_; - SgExpression* upper_bound = static_cast<CG_roseRepr*>(upper)->op_; - SgExpression* step_size = static_cast<CG_roseRepr*>(step)->op_; - - SgStatement* for_init_stmt = buildAssignStatement(index_sym, lower_bound); - SgLessOrEqualOp* cond = buildLessOrEqualOp(index_sym, upper_bound); - SgExprStatement* test = buildExprStatement(cond); - SgPlusAssignOp* increment = buildPlusAssignOp(index_sym, step_size); - SgForStatement *for_stmt = buildForStatement(for_init_stmt, - isSgStatement(test), increment, NULL); - - delete index; - delete lower; - delete upper; - delete step; - - - // Manu - if (isInputFortran()) { - SgFortranDo * forStmt=new SgFortranDo(Sg_File_Info::generateDefaultFileInfoForTransformationNode()); - forStmt->set_has_end_statement(true); - forStmt->set_bound(upper_bound); - forStmt->set_increment(step_size); - forStmt->set_initialization(isSgExprStatement(for_init_stmt)->get_expression()); - return new CG_roseRepr(isSgNode(forStmt)); - } else { - - return new CG_roseRepr(isSgNode(for_stmt)); - - } - -} - -//----------------------------------------------------------------------------- -// Attribute Creation -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateAttribute(CG_outputRepr *control, - const std::string &commentText) const { - - SgNode *tnl = static_cast<CG_roseRepr*>(control)->tnl_; - - tnl->setAttribute("omega_comment", new AstTextAttribute(commentText)); - - return static_cast<CG_roseRepr*>(control); - -} - -//----------------------------------------------------------------------------- -// Pragma Attribute -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreatePragmaAttribute(CG_outputRepr *stmt, int looplevel, const std::string &pragmaText) const { - SgNode *tnl = static_cast<CG_roseRepr*>(stmt)->tnl_; - CodeInsertionAttribute* attr = NULL; - if (!tnl->attributeExists("code_insertion")) { - attr = new CodeInsertionAttribute(); - tnl->setAttribute("code_insertion", attr); - } - else { - attr = static_cast<CodeInsertionAttribute*>(tnl->getAttribute("code_insertion")); - } - attr->add(new PragmaInsertion(looplevel, pragmaText)); - return stmt; -} - -//----------------------------------------------------------------------------- -// Prefetch Attribute -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreatePrefetchAttribute(CG_outputRepr* stmt, int looplevel, const std::string &arrName, int hint) const { - SgNode *tnl = static_cast<CG_roseRepr*>(stmt)->tnl_; - CodeInsertionAttribute *attr = getOrCreateCodeInsertionAttribute(tnl); - attr->add(new MMPrefetchInsertion(looplevel, arrName, hint)); -} - -//----------------------------------------------------------------------------- -// loop stmt generation -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateLoop(int, CG_outputRepr *control, - CG_outputRepr *stmtList) const { - if (stmtList == NULL) { - delete control; - return NULL; - } else if (control == NULL) { - fprintf(stderr, "Code generation: no inductive for this loop\n"); - return stmtList; - } - - SgNode *tnl = static_cast<CG_roseRepr*>(control)->tnl_; - SgForStatement *tf = isSgForStatement(tnl); - - // Manu :: fortran support - SgFortranDo *tfd = NULL; - if (isInputFortran()) { - tfd = isSgFortranDo(tnl); - } - SgStatementPtrList * body = static_cast<CG_roseRepr*>(stmtList)->list_; - - if (body != NULL) { - if (!((*body).empty())) { - if ((*body).size() == 1) { - if (!isInputFortran()) { // Manu:: added if-else for fortran support - tf->set_loop_body(*((*body).begin())); - (*((*body).begin()))->set_parent(tf); - } else { - SgBasicBlock* bb1 = buildBasicBlock(); - bb1->set_parent(tfd); - bb1->append_statement(*((*body).begin())); - tfd->set_body(bb1); - } - } else { - // Manu:: support for fortran label (do - continue) - SgName *sname = NULL; - - SgBasicBlock* bb = buildBasicBlock(); - if (!isInputFortran()) - bb->set_parent(tf); - else - bb->set_parent(tfd); - for (SgStatementPtrList::iterator it = (*body).begin(); - it != (*body).end(); it++) { - bb->append_statement(*it); - (*it)->set_parent(bb); - } - if (!isInputFortran()) - tf->set_loop_body(bb); - else { - tfd->set_body(bb); - } - } - } - } else { - SgNode* tnl2 = static_cast<CG_roseRepr*>(stmtList)->tnl_; - - if (tnl2 != NULL) { - if (!isInputFortran()) { - tf->set_loop_body(isSgStatement(tnl2)); - tnl2->set_parent(tf); - } else { - SgBasicBlock* bb1 = buildBasicBlock(); - bb1->set_parent(tfd); - bb1->append_statement(isSgStatement(tnl2)); - tfd->set_body(bb1); - tnl2->set_parent(bb1); - } - } - } - - delete stmtList; - - return control; -} - -//----------------------------------------------------------------------------- -// basic int, identifier gen operations -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateInt(int _i) const { - return new CG_roseRepr(isSgExpression(buildIntVal(_i))); -} -bool CG_roseBuilder::isInteger(CG_outputRepr *op) const{ - - SgExpression *op1 = static_cast<CG_roseRepr *>(op)->op_; - - if(op1) - if(isSgIntVal(op1)) - return true; - - return false; -} -CG_outputRepr* CG_roseBuilder::CreateIdent(const std::string &_s) const { - - SgVariableSymbol *vs = symtab_->find_variable(SgName(_s.c_str())); - SgVariableSymbol *vs2 = symtab2_->find_variable(SgName(_s.c_str())); - - if (vs == NULL && vs2 == NULL) { - - SgVariableDeclaration* defn = buildVariableDeclaration( - SgName(_s.c_str()), buildIntType()); - SgInitializedNamePtrList& variables = defn->get_variables(); - SgInitializedNamePtrList::const_iterator i = variables.begin(); - SgInitializedName* initializedName = *i; - vs = new SgVariableSymbol(initializedName); - prependStatement(defn, isSgScopeStatement(root_)); - - vs->set_parent(symtab2_); - symtab2_->insert(SgName(_s.c_str()), vs); - return new CG_roseRepr(isSgExpression(buildVarRefExp(vs))); - - } - - /* May have problem */ - - if (!isSgExpression(buildVarRefExp(SgName(_s.c_str())))) - throw ir_error("error in Create ident!!"); - if (vs2 != NULL) - return new CG_roseRepr(isSgExpression(buildVarRefExp(vs2))); - - return new CG_roseRepr(isSgExpression(buildVarRefExp(vs))); - -} - -//----------------------------------------------------------------------------- -// binary arithmetic operations -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreatePlus(CG_outputRepr *lop, - CG_outputRepr *rop) const { - if (rop == NULL) { - return lop; - } else if (lop == NULL) { - return rop; - } - - SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; - SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; - - SgAddOp *ins = buildAddOp(op1, op2); - op1->set_parent(ins); - op2->set_parent(ins); - delete lop; - delete rop; - - return new CG_roseRepr(isSgExpression(ins)); - -} - -CG_outputRepr* CG_roseBuilder::CreateMinus(CG_outputRepr *lop, - CG_outputRepr *rop) const { - if (rop == NULL) { - return lop; /* May Cause Problem */ - } else if (lop == NULL) { - SgExpression *op = static_cast<CG_roseRepr*>(rop)->op_; - SgMinusOp *ins = buildMinusOp(op); - - delete rop; - - return new CG_roseRepr(isSgExpression(ins)); - } else { - SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; - SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; - - SgSubtractOp *ins = buildSubtractOp(op1, op2); - op1->set_parent(ins); - op2->set_parent(ins); - delete lop; - delete rop; - return new CG_roseRepr(isSgExpression(ins)); - } - -} - -CG_outputRepr* CG_roseBuilder::CreateTimes(CG_outputRepr *lop, - CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) { - if (rop != NULL) { - rop->clear(); - delete rop; - } - if (lop != NULL) { - lop->clear(); - delete lop; - } - return NULL; - } - - SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; - SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; - - SgMultiplyOp *ins = buildMultiplyOp(op1, op2); - op1->set_parent(ins); - op2->set_parent(ins); - delete lop; - delete rop; - - return new CG_roseRepr(isSgExpression(ins)); - -} - -CG_outputRepr* CG_roseBuilder::CreateIntegerFloor(CG_outputRepr *lop, - CG_outputRepr *rop) const { - if (rop == NULL) { - fprintf(stderr, "Code generation: divide by NULL\n"); - return NULL; - } else if (lop == NULL) { - delete rop; - return NULL; - } - - // (6+5)*10 / 4 - SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; - SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; - - // bugs in SUIF prevent use of correct io_divfloor - SgDivideOp *ins = buildDivideOp(op1, op2); - - delete lop; - delete rop; - - return new CG_roseRepr(isSgExpression(ins)); - -} - -CG_outputRepr* CG_roseBuilder::CreateIntegerMod(CG_outputRepr *lop, - CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) { - return NULL; - } - - SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; - SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; - - // bugs in SUIF prevent use of correct io_mod - SgModOp *ins; - if (!isInputFortran()) { - ins = buildModOp(op1, op2); - delete lop; - delete rop; - - return new CG_roseRepr(isSgExpression(ins)); - } else { // Manu:: fortran mod is a function call and not an operator (f77 and f90) - SgExpression *fins; - SgName fName("MOD"); - SgExprListExp* arg_list = buildExprListExp(); - appendExpression(arg_list, op1); - appendExpression(arg_list, op2); - SgTypeInt *retType = buildIntType(); - fins = isSgExpression(buildFunctionCallExp(fName, retType, arg_list, global_)); - return new CG_roseRepr(isSgExpression(fins)); - } - -} - -//----------------------------------------------------------------------------- -// binary logical operations -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateAnd(CG_outputRepr *lop, - CG_outputRepr *rop) const { - - if (rop == NULL) - return lop; - else if (lop == NULL) - return rop; - - SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; - SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; - - SgAndOp *ins = buildAndOp(op1, op2); - - delete lop; - delete rop; - - return new CG_roseRepr(isSgExpression(ins)); - -} - -//----------------------------------------------------------------------------- -// binary relational operations -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::CreateLE(CG_outputRepr *lop, - CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) { - return NULL; - } - - SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; - SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; - - SgLessOrEqualOp *ins = buildLessOrEqualOp(op1, op2); - - delete lop; - delete rop; - - return new CG_roseRepr(isSgExpression(ins)); - -} - -CG_outputRepr* CG_roseBuilder::CreateEQ(CG_outputRepr *lop, - CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) { - return NULL; - } - - SgExpression* op1 = static_cast<CG_roseRepr*>(lop)->op_; - SgExpression* op2 = static_cast<CG_roseRepr*>(rop)->op_; - - SgEqualityOp *ins = buildEqualityOp(op1, op2); - - delete lop; - delete rop; - - return new CG_roseRepr(isSgExpression(ins)); - -} - -//----------------------------------------------------------------------------- -// stmt list gen operations -//----------------------------------------------------------------------------- -CG_outputRepr* CG_roseBuilder::StmtListAppend(CG_outputRepr *list1, - CG_outputRepr *list2) const { - - if (list2 == NULL) { - return list1; - } else if (list1 == NULL) { - return list2; - } - - SgStatementPtrList* new_list; - - SgStatementPtrList* tnl1 = static_cast<CG_roseRepr *>(list1)->list_; - SgStatementPtrList* tnl2 = static_cast<CG_roseRepr *>(list2)->list_; - SgNode* one = static_cast<CG_roseRepr *>(list1)->tnl_; - SgNode* two = static_cast<CG_roseRepr *>(list2)->tnl_; - - SgExpression* exp1 = static_cast<CG_roseRepr *>(list1)->op_; - SgExpression* exp2 = static_cast<CG_roseRepr *>(list2)->op_; - - if (exp1 || exp2) - throw ir_error("error in stmtlistappend!!"); - - if (tnl1 && one) - throw ir_error("error in stmtlistappend!!"); - - if (tnl2 && two) - throw ir_error("error in stmtlistappend!!"); - if ((tnl1 == NULL) && (tnl2 == NULL)) { - - if ((one != NULL) && (two != NULL)) { - - new_list = new SgStatementPtrList; - - (*new_list).push_back(isSgStatement(one)); - (*new_list).push_back(isSgStatement(two)); - - CG_roseRepr* new_rep = new CG_roseRepr(new_list); - - return static_cast<CG_outputRepr *>(new_rep); - - } else if ((one != NULL) && (two == NULL)) { - - return static_cast<CG_outputRepr *>(new CG_roseRepr(one)); - - } else if ((two != NULL) && (one == NULL)) { - return static_cast<CG_outputRepr *>(new CG_roseRepr(two)); - - } - - } else { - if ((tnl2 != NULL) && (tnl1 == NULL)) { - if (one == NULL) - return list2; - else { - new_list = new SgStatementPtrList; - (*new_list).push_back(isSgStatement(one)); - - for (SgStatementPtrList::iterator it = (*tnl2).begin(); - it != (*tnl2).end(); it++) { - (*new_list).push_back(*it); - - } - return static_cast<CG_outputRepr *>(new CG_roseRepr(new_list)); - } - } else if ((tnl1 != NULL) && (tnl2 == NULL)) { - if (two == NULL) - return list1; - else { - - (*tnl1).push_back(isSgStatement(two)); - return static_cast<CG_outputRepr *>(new CG_roseRepr(tnl1)); - - } - - } else if ((tnl1 != NULL) && (tnl2 != NULL)) { - - for (SgStatementPtrList::iterator it = (*tnl2).begin(); - it != (*tnl2).end(); it++) { - (*tnl1).push_back(*it); - - } - - return static_cast<CG_outputRepr *>(new CG_roseRepr(tnl1)); - } - - } - -} - - -CG_outputRepr* CG_roseBuilder::CreateDim3(const char* varName, CG_outputRepr* arg1, - CG_outputRepr* arg2, CG_outputRepr* arg3) const { - - SgFunctionSymbol * ctor_symbol = global_scope->lookup_function_symbol( - SgName("dim3")); - - SgExprListExp * ctor_args; - if(arg3 != NULL) - ctor_args = buildExprListExp(static_cast<CG_roseRepr*>(arg1)->op_, - static_cast<CG_roseRepr*>(arg2)->op_, static_cast<CG_roseRepr*>(arg3)->op_); - else - ctor_args = buildExprListExp(static_cast<CG_roseRepr*>(arg1)->op_, - static_cast<CG_roseRepr*>(arg2)->op_); - SgFunctionCallExp * dim3_func_call = buildFunctionCallExp( - buildFunctionRefExp(ctor_symbol->get_declaration()), ctor_args); - - char joined_str[20]; - - strcpy(joined_str, "dim3 "); - strcat(joined_str, varName); - - SgExprStatement* decl = buildAssignStatement( - buildOpaqueVarRefExp(joined_str, isSgScopeStatement(root_)), - dim3_func_call); - - SgStatementPtrList *tnl2 = new SgStatementPtrList; - - (*tnl2).push_back(decl); - return new CG_roseRepr(tnl2); - -} - -std::vector<SgVarRefExp *> substitute(SgNode *in, const SgVariableSymbol *sym, - SgExpression* expr, SgNode* root) { - - SgStatement* stmt; - SgExpression* op; - std::vector<SgVarRefExp *> arrays; - - if (in != NULL) { - if (stmt = isSgStatement(in)) { - if (isSgBasicBlock(stmt)) { - SgStatementPtrList& stmts = - isSgBasicBlock(stmt)->get_statements(); - for (int i = 0; i < stmts.size(); i++) { - stmts[i]->set_parent(stmt); - std::vector<SgVarRefExp *> a = substitute( - isSgNode(stmts[i]), sym, expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - } - } else if (isSgForStatement(stmt)) { - SgForStatement *tnf = isSgForStatement(stmt); - tnf->get_for_init_stmt()->set_parent(tnf); - tnf->get_test()->set_parent(tnf); - tnf->get_increment()->set_parent(tnf); - tnf->get_loop_body()->set_parent(tnf); - std::vector<SgVarRefExp *> a = substitute( - isSgNode(tnf->get_for_init_stmt()), sym, expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - std::vector<SgVarRefExp *> a1 = substitute( - isSgNode(tnf->get_test()), sym, expr, root); - std::copy(a1.begin(), a1.end(), back_inserter(arrays)); - std::vector<SgVarRefExp *> a2 = substitute( - isSgNode(tnf->get_increment()), sym, expr, root); - std::copy(a2.begin(), a2.end(), back_inserter(arrays)); - std::vector<SgVarRefExp *> a3 = substitute( - isSgNode(tnf->get_loop_body()), sym, expr, root); - std::copy(a3.begin(), a3.end(), back_inserter(arrays)); - } else if (isSgFortranDo(stmt)) { // Manu:: fortran support - SgFortranDo *tnf = isSgFortranDo(stmt); - tnf->get_initialization()->set_parent(tnf); - tnf->get_bound()->set_parent(tnf); - tnf->get_increment()->set_parent(tnf); - tnf->get_body()->set_parent(tnf); - std::vector<SgVarRefExp *> a = substitute( - isSgNode(tnf->get_initialization()), sym, expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - std::vector<SgVarRefExp *> a1 = substitute( - isSgNode(tnf->get_bound()), sym, expr, root); - std::copy(a1.begin(), a1.end(), back_inserter(arrays)); - std::vector<SgVarRefExp *> a2 = substitute( - isSgNode(tnf->get_increment()), sym, expr, root); - std::copy(a2.begin(), a2.end(), back_inserter(arrays)); - std::vector<SgVarRefExp *> a3 = substitute( - isSgNode(tnf->get_body()), sym, expr, root); - std::copy(a3.begin(), a3.end(), back_inserter(arrays)); - } else if (isSgForInitStatement(stmt)) { - - SgStatementPtrList& stmts = - isSgForInitStatement(stmt)->get_init_stmt(); - - for (SgStatementPtrList::iterator it = stmts.begin(); - it != stmts.end(); it++) { - std::vector<SgVarRefExp *> a = substitute(isSgNode(*it), - sym, expr, root); - - std::copy(a.begin(), a.end(), back_inserter(arrays)); - } - } - else if (isSgVariableDeclaration(stmt)) { - if (SgExpression *init = - isSgVariableDeclaration(stmt)->get_variables().front()->get_initializer()) { - if (isSgAssignInitializer(init)) { - std::vector<SgVarRefExp *> a = substitute( - isSgAssignInitializer(init)->get_operand(), sym, - expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - } - } - } else if (isSgIfStmt(stmt)) { - SgIfStmt* tni = isSgIfStmt(stmt); - std::vector<SgVarRefExp *> a = substitute( - isSgNode(tni->get_conditional()), sym, expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - std::vector<SgVarRefExp *> a1 = substitute( - isSgNode(tni->get_true_body()), sym, expr, root); - std::copy(a1.begin(), a1.end(), back_inserter(arrays)); - std::vector<SgVarRefExp *> a2 = substitute( - isSgNode(tni->get_false_body()), sym, expr, root); - std::copy(a2.begin(), a2.end(), back_inserter(arrays)); - } else if (isSgExprStatement(stmt)) { - (isSgExprStatement(stmt)->get_expression())->set_parent( - isSgExprStatement(stmt)); - std::vector<SgVarRefExp *> a = substitute( - isSgNode(isSgExprStatement(stmt)->get_expression()), - sym, expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - } - } - else { - op = isSgExpression(in); - std::string y = sym->get_name().getString(); - - if (isSgBinaryOp(op)) { - - isSgBinaryOp(op)->get_lhs_operand()->set_parent(op); - isSgBinaryOp(op)->get_rhs_operand()->set_parent(op); - - std::vector<SgVarRefExp *> a = substitute( - isSgBinaryOp(op)->get_lhs_operand(), sym, expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - std::vector<SgVarRefExp *> a1 = substitute( - isSgBinaryOp(op)->get_rhs_operand(), sym, expr, root); - std::copy(a1.begin(), a1.end(), back_inserter(arrays)); - } else if (isSgUnaryOp(op)) { - std::vector<SgVarRefExp *> a = substitute( - isSgUnaryOp(op)->get_operand(), sym, expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - } else if (isSgVarRefExp(op)) { - std::string z = - isSgVarRefExp(op)->get_symbol()->get_name().getString(); - if (!strcmp(z.c_str(), y.c_str())) { - arrays.push_back(isSgVarRefExp(op)); - } - } - else if (isSgCallExpression(op)) { - SgExprListExp* exprs = isSgCallExpression(op)->get_args(); - SgExpressionPtrList &expr_list = exprs->get_expressions(); - - for (SgExpressionPtrList::iterator it = expr_list.begin(); - it != expr_list.end(); it++) { - std::vector<SgVarRefExp *> a = substitute(isSgNode(*it), - sym, expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - } - } else if (isSgExprListExp(op)) { // Manu:: fortran indices are stored this way - SgExpressionPtrList &expr_list = isSgExprListExp(op)->get_expressions(); - - for (SgExpressionPtrList::iterator it = expr_list.begin(); - it != expr_list.end(); it++) { - std::vector<SgVarRefExp *> a = substitute(isSgNode(*it), - sym, expr, root); - std::copy(a.begin(), a.end(), back_inserter(arrays)); - } - - } - - } - } - - return arrays; -} - -} // namespace diff --git a/omegalib/codegen/src/CG_roseRepr.cc b/omegalib/codegen/src/CG_roseRepr.cc deleted file mode 100644 index 9265ab0..0000000 --- a/omegalib/codegen/src/CG_roseRepr.cc +++ /dev/null @@ -1,125 +0,0 @@ -/***************************************************************************** - Copyright (C) 2008 University of Southern California. - All Rights Reserved. - - Purpose: - omega holder for suif implementaion - - Notes: - - History: - 02/01/06 - Chun Chen - created -*****************************************************************************/ - -#include <code_gen/CG_roseRepr.h> -#include <code_gen/rose_attributes.h> -#include <stdio.h> -#include <string.h> -#include <cstring> -namespace omega { - - - - -CG_roseRepr::CG_roseRepr(): tnl_(NULL), op_(NULL), list_(NULL){ - -} - -CG_roseRepr::CG_roseRepr(SgNode *tnl): tnl_(tnl), op_(NULL),list_(NULL) { -} - -CG_roseRepr::CG_roseRepr(SgExpression* op): tnl_(NULL), op_(op),list_(NULL){ -} -CG_roseRepr::CG_roseRepr(SgStatementPtrList* stmtlist):tnl_(NULL), op_(NULL), list_(stmtlist){ -} - -CG_roseRepr::~CG_roseRepr() { - // delete nothing here. operand or tree_node_list should already be - // grafted to other expression tree or statement list -} - -CG_outputRepr* CG_roseRepr::clone() const { - - if( tnl_ != NULL) { - SgTreeCopy tc; - SgNode *tnl = tnl_->copy(tc); - copyAttributes(tnl_, tnl); - - tnl->set_parent(tnl_->get_parent()); - return new CG_roseRepr(tnl); - } - else if(op_ != NULL) - { - SgTreeCopy tc1; - SgNode* op = isSgNode(op_)->copy(tc1); - copyAttributes(op_, op); - - op->set_parent(isSgNode(op_)->get_parent()); - return new CG_roseRepr(isSgExpression(op)); - } - else if(list_ != NULL) - { - SgStatementPtrList* list2 = new SgStatementPtrList; - - for(SgStatementPtrList::iterator it = (*list_).begin(); it != (*list_).end(); it++){ - SgTreeCopy tc3; - SgNode *tnl2 = isSgNode(*it)->copy(tc3); - copyAttributes(*it, tnl2); - - tnl2->set_parent(isSgNode(*it)->get_parent()); - - (*list2).push_back(isSgStatement(tnl2)); - } - return new CG_roseRepr(list2); - } - - return NULL; -} - -void CG_roseRepr::clear() { - if(tnl_ != NULL) { - delete tnl_; - tnl_ = NULL; - } -} - -SgNode* CG_roseRepr::GetCode() const { - return tnl_; -} - -SgStatementPtrList* CG_roseRepr::GetList() const { - return list_; -} - -SgExpression* CG_roseRepr::GetExpression() const { - return op_; -} -void CG_roseRepr::Dump() const { -SgNode* tnl = tnl_; -SgExpression* op = op_ ; - if(tnl != NULL) - DumpFileHelper(tnl, stdout); - else if(op != NULL) - DumpFileHelper(isSgNode(op), stdout); - -} - -void CG_roseRepr::DumpFileHelper(SgNode* node, FILE *fp) const{ - std::string x; - size_t numberOfSuccessors = node->get_numberOfTraversalSuccessors(); - if(numberOfSuccessors == 0){ - x = node->unparseToString (); - fprintf(fp, "%s", x.c_str()); - } - else{ - for (size_t idx = 0; idx < numberOfSuccessors; idx++) - { - SgNode *child = NULL; - child = node->get_traversalSuccessorByIndex(idx); - DumpFileHelper(child, fp); - } - -} -} - -} // namespace diff --git a/omegalib/codegen/src/CG_stringBuilder.cc b/omegalib/codegen/src/CG_stringBuilder.cc deleted file mode 100644 index 2f9286f..0000000 --- a/omegalib/codegen/src/CG_stringBuilder.cc +++ /dev/null @@ -1,487 +0,0 @@ -/***************************************************************************** - Copyright (C) 1994-2000 the Omega Project Team - Copyright (C) 2005-2011 Chun Chen - All Rights Reserved. - - Purpose: - generate pseudo string code - - Notes: - There is no need to check illegal NULL parameter and throw invalid_argument - in other IR interface implementation. They are for debugging purpose. - intMod implements modular function that returns positve remainder no matter - lop is postive or nagative and rop is guranteed to be positive here. - - History: - 04/17/96 - Lei Zhou - created - 08/31/09 add parenthesis to string operands, Chun Chen -*****************************************************************************/ - -#include <code_gen/CG_stringBuilder.h> -#include <code_gen/codegen_error.h> -#include <basic/util.h> -#include <string> -#include <stdexcept> -#include <ctype.h> -#include <string.h> - -namespace { - -std::string SafeguardString(const std::string &s, char op) { - int len = s.length(); - int paren_level = 0; - int num_plusminus = 0; - int num_mul = 0; - int num_div = 0; - for (int i = 0; i < len; i++) - switch (s[i]) { - case '(': - paren_level++; - break; - case ')': - paren_level--; - break; - case '+': - case '-': - if (paren_level == 0) - num_plusminus++; - break; - case '*': - if (paren_level == 0) - num_mul++; - break; - case '/': - if (paren_level == 0) - num_div++; - break; - default: - break; - } - - bool need_paren = false; - switch (op) { - case '-': - if (num_plusminus > 0) - need_paren = true; - break; - case '*': - if (num_plusminus > 0 || num_div > 0) - need_paren = true; - break; - case '/': - if (num_plusminus > 0 || num_div > 0 || num_mul > 0) - need_paren = true; - break; - default: - break; - } - - if (need_paren) - return "(" + s + ")"; - else - return s; -} - - -std::string GetIndentSpaces(int indent) { - std::string indentStr; - for (int i = 1; i < indent; i++) { - indentStr += " "; - } - return indentStr; -} - - -// A shortcut to extract the string enclosed in the CG_outputRepr and delete -// the original holder. -std::string GetString(omega::CG_outputRepr *repr) { - std::string result = static_cast<omega::CG_stringRepr *>(repr)->GetString(); - delete repr; - return result; -} - -} - - -namespace omega { - - - -//----------------------------------------------------------------------------- -// Class: CG_stringBuilder -//----------------------------------------------------------------------------- - -CG_stringRepr *CG_stringBuilder::CreateSubstitutedStmt(int indent, CG_outputRepr *stmt, - const std::vector<std::string> &vars, - std::vector<CG_outputRepr *> &subs) const { - std::string listStr = ""; - - for (int i = 0; i < subs.size(); i++) { - if (subs[i] == NULL) - listStr += "N/A"; - else - listStr += GetString(subs[i]); - if (i < subs.size() - 1) - listStr += ","; - } - - std::string stmtName = GetString(stmt); - std::string indentStr = GetIndentSpaces(indent); - - return new CG_stringRepr(indentStr + stmtName + "(" + listStr + ");\n"); -} - -CG_stringRepr *CG_stringBuilder::CreateAssignment(int indent, - CG_outputRepr *lhs, - CG_outputRepr *rhs) const { - if (lhs == NULL || rhs == NULL) - throw std::invalid_argument("missing lhs or rhs in assignment"); - - std::string lhsStr = GetString(lhs); - std::string rhsStr = GetString(rhs); - - std::string indentStr = GetIndentSpaces(indent); - - return new CG_stringRepr(indentStr + lhsStr + "=" + rhsStr + ";\n"); -} - - -CG_stringRepr *CG_stringBuilder::CreateInvoke(const std::string &funcName, - std::vector<CG_outputRepr *> &list) const { - std::string listStr = ""; - - for (int i = 0; i < list.size(); i++) { - listStr += GetString(list[i]); - if ( i < list.size()-1) - listStr += ","; - } - - return new CG_stringRepr(funcName + "(" + listStr + ")"); -} - - -CG_stringRepr *CG_stringBuilder::CreateComment(int indent, const std::string &commentText) const { - if (commentText == std::string("")) { - return NULL; - } - - std::string indentStr = GetIndentSpaces(indent); - - return new CG_stringRepr(indentStr + "// " + commentText + "\n"); -} - -CG_stringRepr* CG_stringBuilder::CreateAttribute(CG_outputRepr *control, - const std::string &commentText) const { - if (commentText == std::string("")) { - return static_cast<CG_stringRepr *> (control); - } - - std::string controlString = GetString(control); - - return new CG_stringRepr("// " + commentText + "\n" + controlString); - -} - -CG_outputRepr* CG_stringBuilder::CreatePragmaAttribute(CG_outputRepr *scopeStmt, int looplevel, const std::string &pragmaText) const { - // -- Not Implemented - return scopeStmt; -} - -CG_outputRepr* CG_stringBuilder::CreatePrefetchAttribute(CG_outputRepr* scopeStmt, int looplevel, const std::string& arrName, int hint) const { - // -- Not Implemented - return scopeStmt; -} - -CG_stringRepr *CG_stringBuilder::CreateIf(int indent, CG_outputRepr *guardList, - CG_outputRepr *true_stmtList, CG_outputRepr *false_stmtList) const { - if (guardList == NULL) - throw std::invalid_argument("missing if condition"); - - if (true_stmtList == NULL && false_stmtList == NULL) { - delete guardList; - return NULL; - } - - std::string guardListStr = GetString(guardList); - std::string indentStr = GetIndentSpaces(indent); - std::string s; - if (true_stmtList != NULL && false_stmtList == NULL) { - s = indentStr + "if (" + guardListStr + ") {\n" - + GetString(true_stmtList) - + indentStr + "}\n"; - } - else if (true_stmtList == NULL && false_stmtList != NULL) { - s = indentStr + "if !(" + guardListStr + ") {\n" - + GetString(false_stmtList) - + indentStr + "}\n"; - } - else { - s = indentStr + "if (" + guardListStr + ") {\n" - + GetString(true_stmtList) - + indentStr + "}\n" - + indentStr + "else {\n" - + GetString(false_stmtList) - + indentStr + "}\n"; - } - - return new CG_stringRepr(s); -} - - - -CG_stringRepr *CG_stringBuilder::CreateInductive(CG_outputRepr *index, - CG_outputRepr *lower, CG_outputRepr *upper, - CG_outputRepr *step) const { - if (index == NULL) - throw std::invalid_argument("missing loop index"); - if (lower == NULL) - throw std::invalid_argument("missing loop lower bound"); - if (upper == NULL) - throw std::invalid_argument("missing loop upper bound"); - if (step == NULL) - throw std::invalid_argument("missing loop step size"); - - std::string indexStr = GetString(index); - std::string lowerStr = GetString(lower); - std::string upperStr = GetString(upper); - - std::string doStr = "for(" + indexStr + " = " + lowerStr + "; " - + indexStr + " <= " + upperStr + "; " - + indexStr; - - std::string stepStr = GetString(step); - if (stepStr == to_string(1)) - doStr += "++"; - else - doStr += " += " + stepStr; - - doStr += ")"; - - return new CG_stringRepr(doStr); -} - - -CG_stringRepr *CG_stringBuilder::CreateLoop(int indent, CG_outputRepr *control, - CG_outputRepr *stmtList) const { - if (stmtList == NULL) { - delete control; - return NULL; - } - else if (control == NULL) - return static_cast<CG_stringRepr *>(stmtList); - - std::string ctrlStr = GetString(control); - std::string stmtStr = GetString(stmtList); - - std::string indentStr = GetIndentSpaces(indent); - - std::string s = indentStr + ctrlStr + " {\n" - + stmtStr - + indentStr + "}\n"; - - return new CG_stringRepr(s); -} - - - -CG_stringRepr *CG_stringBuilder::CreateInt(int num) const { - std::string s = to_string(num); - return new CG_stringRepr(s); -} - - - -bool CG_stringBuilder::isInteger(CG_outputRepr *op) const { - - char * cstr; - std::string s = GetString(op); - cstr = new char [s.size()+1]; - strcpy (cstr, s.c_str()); - int count = 0; - while(cstr[count] != '\n' && cstr[count] != '\0' ) - if( !isdigit(cstr[count])) - return false; - - - return true; -} - - - -CG_stringRepr *CG_stringBuilder::CreateIdent(const std::string &varName) const { - if (varName == std::string("")) { - return NULL; - } - - return new CG_stringRepr(varName); -} - - -CG_stringRepr *CG_stringBuilder::CreatePlus(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) { - return static_cast<CG_stringRepr *>(lop); - } - else if (lop == NULL) { - return static_cast<CG_stringRepr *>(rop); - } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + "+" + ropStr); -} - - -CG_stringRepr *CG_stringBuilder::CreateMinus(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) { - return static_cast<CG_stringRepr *>(lop); - } - else if (lop == NULL) { - std::string ropStr = GetString(rop); - return new CG_stringRepr("-" + SafeguardString(ropStr, '-')); - } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + "-" + SafeguardString(ropStr, '-')); -} - - -CG_stringRepr *CG_stringBuilder::CreateTimes(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) { - delete rop; - delete lop; - return NULL; - } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(SafeguardString(lopStr, '*') + "*" + SafeguardString(ropStr, '*')); -} - - -CG_stringRepr *CG_stringBuilder::CreateDivide(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) - throw codegen_error("integer division by zero"); - else if (lop == NULL) { - delete rop; - return NULL; - } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(SafeguardString(lopStr, '/') + "/" + SafeguardString(ropStr, '/')); -} - - -CG_stringRepr *CG_stringBuilder::CreateIntegerFloor(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) - throw codegen_error("integer division by zero"); - else if (lop == NULL) { - delete rop; - return NULL; - } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr("intFloor(" + lopStr + "," + ropStr + ")"); -} - - -CG_stringRepr *CG_stringBuilder::CreateIntegerMod(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) - throw codegen_error("integer modulo by zero"); - else if (lop == NULL) { - delete rop; - return NULL; - } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr("intMod(" + lopStr + "," + ropStr + ")"); -} - -CG_stringRepr *CG_stringBuilder::CreateIntegerCeil(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == 0) - throw codegen_error("integer ceiling by zero"); - else if (lop == NULL) { - delete rop; - return NULL; - } - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr("intCeil(" + lopStr + "," + ropStr + ")"); -} - - -CG_stringRepr *CG_stringBuilder::CreateAnd(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL) - return static_cast<CG_stringRepr *>(lop); - else if (lop == NULL) - return static_cast<CG_stringRepr *>(rop); - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + " && " + ropStr); -} - - -CG_stringRepr *CG_stringBuilder::CreateGE(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) - throw std::invalid_argument("missing operand in greater than equal comparison condition"); - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + " >= " + ropStr); -} - - - -CG_stringRepr *CG_stringBuilder::CreateLE(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) - throw std::invalid_argument("missing operand in less than equal comparison condition"); - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + " <= " + ropStr); -} - - - -CG_stringRepr *CG_stringBuilder::CreateEQ(CG_outputRepr *lop, CG_outputRepr *rop) const { - if (rop == NULL || lop == NULL) - throw std::invalid_argument("missing operand in equal comparison condition"); - - std::string lopStr = GetString(lop); - std::string ropStr = GetString(rop); - - return new CG_stringRepr(lopStr + " == " + ropStr); -} - - - -CG_stringRepr *CG_stringBuilder::StmtListAppend(CG_outputRepr *list1, CG_outputRepr *list2) const { - if (list2 == NULL) { - return static_cast<CG_stringRepr *>(list1); - } - else if (list1 == NULL) { - return static_cast<CG_stringRepr *>(list2); - } - - std::string list1Str = GetString(list1); - std::string list2Str = GetString(list2); - - return new CG_stringRepr(list1Str + list2Str); -} - -} diff --git a/omegalib/codegen/src/CG_utils.cc b/omegalib/codegen/src/CG_utils.cc deleted file mode 100755 index d3a5f71..0000000 --- a/omegalib/codegen/src/CG_utils.cc +++ /dev/null @@ -1,1735 +0,0 @@ -/***************************************************************************** - Copyright (C) 1994-2000 the Omega Project Team - Copyright (C) 2005-2011 Chun Chen - All Rights Reserved. - - Purpose: - Utility functions for processing CG tree. - - Notes: - - History: - 07/19/07 when generating output variable substitutions for a mapping - relation, map it to each output to get correct equality, -chun - 07/29/10 when translating equality to assignment, generate appropriate - if-condition when necesssary, -chun -*****************************************************************************/ - -#include <typeinfo> -#include <omega.h> -#include <code_gen/CG.h> -#include <code_gen/CG_utils.h> -#include <code_gen/codegen_error.h> -#include <math.h> -#include <stack> - -namespace omega { - -int checkLoopLevel; -int stmtForLoopCheck; -int upperBoundForLevel; -int lowerBoundForLevel; -bool fillInBounds; - -//trick to static init checkLoopLevel to 0 -class JunkStaticInit{ public: JunkStaticInit(){ checkLoopLevel=0; fillInBounds=false;} }; -static JunkStaticInit junkInitInstance__; - - - - -namespace { - -Relation find_best_guard(const Relation &R, const BoolSet<> &active, const std::map<int, Relation> &guards) { - std::pair<int, int> best_cost = std::make_pair(0, 0); - Relation best_cond = Relation::True(R.n_set()); - - Relation r = copy(R); - int max_iter_count = 2*(r.single_conjunct()->n_EQs()) + r.single_conjunct()->n_GEQs(); - int iter_count = 0; - while (!r.is_obvious_tautology()) { - std::pair<int, int> cost = std::make_pair(0, 0); - Relation cond = pick_one_guard(r); - Relation complement_cond = Complement(copy(cond)); - complement_cond.simplify(); - for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) { - std::map<int, Relation>::const_iterator j = guards.find(*i); - if (j == guards.end()) - continue; - if (Must_Be_Subset(copy(j->second), copy(cond))) - cost.first++; - else if (Must_Be_Subset(copy(j->second), copy(complement_cond))) - cost.second++; - } - if (cost > best_cost) { - best_cost = cost; - best_cond = copy(cond); - } - r = Gist(r, cond, 1); - - if (iter_count > max_iter_count) - throw codegen_error("guard condition too complex to handle"); - - iter_count++; - } - - return best_cond; -} - - -Relation find_best_guard(const Relation &R, const std::vector<CG_loop *> &loops, int start, int end) { - std::pair<int, int> best_cost = std::make_pair(0, 0); - Relation best_cond = Relation::True(R.n_set()); - - Relation r = copy(R); - int max_iter_count = 2*(r.single_conjunct()->n_EQs()) + r.single_conjunct()->n_GEQs(); - int iter_count = 0; - while (!r.is_obvious_tautology()) { - std::pair<int, int> cost = std::make_pair(0, 0); - Relation cond = pick_one_guard(r); - int i = start; - for ( ; i < end; i++) { - if (Must_Be_Subset(copy(loops[i]->guard_), copy(cond))) - cost.first++; - else - break; - } - Relation complement_cond = Complement(copy(cond)); - complement_cond.simplify(); - for (int j = i; j < end; j++) - if (Must_Be_Subset(copy(loops[j]->guard_), copy(complement_cond))) - cost.second++; - else - break; - - if (cost > best_cost) { - best_cost = cost; - best_cond = copy(cond); - } - r = Gist(r, cond, 1); - - if (iter_count > max_iter_count) - throw codegen_error("guard condition too complex to handle"); - - iter_count++; - } - - return best_cond; -} - -} - -bool bound_must_hit_stride(const GEQ_Handle &inequality, Variable_ID v, const EQ_Handle &stride_eq, Variable_ID wc, const Relation &bounds, const Relation &known) { - assert(inequality.get_coef(v) != 0 && abs(stride_eq.get_coef(v)) == 1 && wc->kind() == Wildcard_Var && abs(stride_eq.get_coef(wc)) > 1); - - // if bound expression uses floor operation, bail out for now - // TODO: in the future, handle this - if (abs(inequality.get_coef(v)) != 1) - return false; - - coef_t stride = abs(stride_eq.get_coef(wc)); - - Relation r1(known.n_set()); - F_Exists *f_exists1 = r1.add_and()->add_exists(); - F_And *f_root1 = f_exists1->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping1; - EQ_Handle h1 = f_root1->add_EQ(); - Relation r2(known.n_set()); - F_Exists *f_exists2 = r2.add_and()->add_exists(); - F_And *f_root2 = f_exists2->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping2; - EQ_Handle h2 = f_root2->add_EQ(); - for (Constr_Vars_Iter cvi(inequality); cvi; cvi++) { - Variable_ID v = cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h1.update_coef(r1.input_var(v->get_position()), cvi.curr_coef()); - h2.update_coef(r2.input_var(v->get_position()), cvi.curr_coef()); - break; - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v1, v2; - if (g->arity() == 0) { - v1 = r1.get_local(g); - v2 = r2.get_local(g); - } - else { - v1 = r1.get_local(g, v->function_of()); - v2 = r2.get_local(g, v->function_of()); - } - h1.update_coef(v1, cvi.curr_coef()); - h2.update_coef(v2, cvi.curr_coef()); - break; - } - case Wildcard_Var: { - Variable_ID v1 = replicate_floor_definition(bounds, v, r1, f_exists1, f_root1, exists_mapping1); - Variable_ID v2 = replicate_floor_definition(bounds, v, r2, f_exists2, f_root2, exists_mapping2); - h1.update_coef(v1, cvi.curr_coef()); - h2.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h1.update_const(inequality.get_const()); - h1.update_coef(f_exists1->declare(), stride); - h2.update_const(inequality.get_const()); - r1.simplify(); - r2.simplify(); - - Relation all_known = Intersection(copy(bounds), copy(known)); - all_known.simplify(); - - if (Gist(r1, copy(all_known), 1).is_obvious_tautology()) { - Relation r3(known.n_set()); - F_Exists *f_exists3 = r3.add_and()->add_exists(); - F_And *f_root3 = f_exists3->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping3; - EQ_Handle h3 = f_root3->add_EQ(); - for (Constr_Vars_Iter cvi(stride_eq); cvi; cvi++) { - Variable_ID v= cvi.curr_var(); - switch (v->kind()) { - case Input_Var: - h3.update_coef(r3.input_var(v->get_position()), cvi.curr_coef()); - break; - case Global_Var: { - Global_Var_ID g = v->get_global_var(); - Variable_ID v3; - if (g->arity() == 0) - v3 = r3.get_local(g); - else - v3 = r3.get_local(g, v->function_of()); - h3.update_coef(v3, cvi.curr_coef()); - break; - } - case Wildcard_Var: - if (v == wc) - h3.update_coef(f_exists3->declare(), cvi.curr_coef()); - else { - Variable_ID v3 = replicate_floor_definition(bounds, v, r3, f_exists3, f_root3, exists_mapping3); - h3.update_coef(v3, cvi.curr_coef()); - } - break; - default: - assert(false); - } - } - h3.update_const(stride_eq.get_const()); - r3.simplify(); - - if (Gist(r3, Intersection(r2, all_known), 1).is_obvious_tautology()) - return true; - else - return false; - } - else - return false; -} - - -// -// output variable by its name, however if this variable need to be substituted, -// return the substitution. -// -CG_outputRepr *output_ident(CG_outputBuilder *ocg, const Relation &R, Variable_ID v, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - const_cast<Relation &>(R).setup_names(); // hack - - if (v->kind() == Input_Var) { - int pos = v->get_position(); - if (assigned_on_the_fly[pos-1].first != NULL) - return assigned_on_the_fly[pos-1].first->clone(); - else - return ocg->CreateIdent(v->name()); - } - else if (v->kind() == Global_Var) { - if (v->get_global_var()->arity() == 0) - return ocg->CreateIdent(v->name()); - else { - /* This should be improved to take into account the possible elimination - of the set variables. */ - int arity = v->get_global_var()->arity(); - std::vector<CG_outputRepr *> argList; - for(int i = 1; i <= arity; i++) - argList.push_back(ocg->CreateIdent(const_cast<Relation &>(R).input_var(i)->name())); - CG_outputRepr *call = ocg->CreateInvoke(v->get_global_var()->base_name(), argList); - return call; - } - } - else - assert(false); -} - - -// -// return pair<if condition, <assignment rhs, assignment cost> > -// -std::pair<CG_outputRepr *, std::pair<CG_outputRepr *, int> > output_assignment(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - Variable_ID v = const_cast<Relation &>(R).set_var(level); - Conjunct *c = const_cast<Relation &>(R).single_conjunct(); - - std::pair<EQ_Handle, int> result = find_simplest_assignment(R, v, assigned_on_the_fly); - - if (result.second == INT_MAX) - return std::make_pair(static_cast<CG_outputRepr *>(NULL), std::make_pair(static_cast<CG_outputRepr *>(NULL), INT_MAX)); - - CG_outputRepr *if_repr = NULL; - CG_outputRepr *assign_repr = NULL; - // check whether to generate if-conditions from equality constraints - if (abs(result.first.get_coef(v)) != 1) { - Relation r(R.n_set()); - F_Exists *f_exists = r.add_and()->add_exists(); - F_And *f_root = f_exists->add_and(); - std::map<Variable_ID, Variable_ID> exists_mapping; - exists_mapping[v] = f_exists->declare(); - - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(result.first); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Input_Var: { - if (cvi.curr_var() == v) - h.update_coef(exists_mapping[v], cvi.curr_coef()); - else - h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = cvi.curr_var()->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r.get_local(g); - else - v2 = r.get_local(g, cvi.curr_var()->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var()); - Variable_ID v2; - if (p == exists_mapping.end()) { - v2 = f_exists->declare(); - exists_mapping[cvi.curr_var()] = v2; - } - else - v2 = p->second; - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(0); - } - h.update_const(result.first.get_const()); - - for (EQ_Iterator e(c->EQs()); e; e++) - if (!((*e) == result.first)) { - EQ_Handle h = f_root->add_EQ(); - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Input_Var: { - assert(cvi.curr_var() != v); - h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = cvi.curr_var()->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r.get_local(g); - else - v2 = r.get_local(g, cvi.curr_var()->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var()); - Variable_ID v2; - if (p == exists_mapping.end()) { - v2 = f_exists->declare(); - exists_mapping[cvi.curr_var()] = v2; - } - else - v2 = p->second; - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(0); - } - h.update_const((*e).get_const()); - } - - for (GEQ_Iterator e(c->GEQs()); e; e++) { - GEQ_Handle h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Input_Var: { - h.update_coef(r.set_var(cvi.curr_var()->get_position()), cvi.curr_coef()); - break; - } - case Global_Var: { - Global_Var_ID g = cvi.curr_var()->get_global_var(); - Variable_ID v2; - if (g->arity() == 0) - v2 = r.get_local(g); - else - v2 = r.get_local(g, cvi.curr_var()->function_of()); - h.update_coef(v2, cvi.curr_coef()); - break; - } - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(cvi.curr_var()); - Variable_ID v2; - if (p == exists_mapping.end()) { - v2 = f_exists->declare(); - exists_mapping[cvi.curr_var()] = v2; - } - else - v2 = p->second; - h.update_coef(v2, cvi.curr_coef()); - break; - } - default: - assert(0); - } - h.update_const((*e).get_const()); - } - - r.simplify(); - if (!Gist(r, copy(known), 1).is_obvious_tautology()) { - CG_outputRepr *lhs = output_substitution_repr(ocg, result.first, v, false, R, assigned_on_the_fly); - if_repr = ocg->CreateEQ(ocg->CreateIntegerMod(lhs->clone(), ocg->CreateInt(abs(result.first.get_coef(v)))), ocg->CreateInt(0)); - assign_repr = ocg->CreateDivide(lhs, ocg->CreateInt(abs(result.first.get_coef(v)))); - } - else - assign_repr = output_substitution_repr(ocg, result.first, v, true, R, assigned_on_the_fly); - } - else - assign_repr = output_substitution_repr(ocg, result.first, v, true, R, assigned_on_the_fly); - - if (assign_repr == NULL) - assign_repr = ocg->CreateInt(0); - - return std::make_pair(if_repr, std::make_pair(assign_repr, result.second)); -} - - -// -// return NULL if 0 -// -CG_outputRepr *output_substitution_repr(CG_outputBuilder *ocg, const EQ_Handle &equality, Variable_ID v, bool apply_v_coef, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - const_cast<Relation &>(R).setup_names(); // hack - - coef_t a = equality.get_coef(v); - assert(a != 0); - - CG_outputRepr *repr = NULL; - for (Constr_Vars_Iter cvi(equality); cvi; cvi++) - if (cvi.curr_var() != v) { - CG_outputRepr *t; - if (cvi.curr_var()->kind() == Wildcard_Var) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var()); - if (!result.first) { - delete repr; - throw codegen_error("can't output non floor defined wildcard"); - } - t = output_inequality_repr(ocg, result.second, cvi.curr_var(), R, assigned_on_the_fly); - } - else - t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - - if (a > 0) { - if (coef > 0) { - if (coef == 1) - repr = ocg->CreateMinus(repr, t); - else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); - } - else { // coef < 0 - if (coef == -1) - repr = ocg->CreatePlus(repr, t); - else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); - } - } - else { - if (coef > 0) { - if (coef == 1) - repr = ocg->CreatePlus(repr, t); - else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); - } - else { // coef < 0 - if (coef == -1) - repr = ocg->CreateMinus(repr, t); - else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); - } - } - } - - int c = equality.get_const(); - if (a > 0) { - if (c > 0) - repr = ocg->CreateMinus(repr, ocg->CreateInt(c)); - else if (c < 0) - repr = ocg->CreatePlus(repr, ocg->CreateInt(-c)); - } - else { - if (c > 0) - repr = ocg->CreatePlus(repr, ocg->CreateInt(c)); - else if (c < 0) - repr = ocg->CreateMinus(repr, ocg->CreateInt(-c)); - } - - if (apply_v_coef && abs(a) != 1) - repr = ocg->CreateDivide(repr, ocg->CreateInt(abs(a))); - - return repr; -} - - -// -// original Substitutions class from omega can't handle integer -// division, this is new way. -// -std::vector<CG_outputRepr*> output_substitutions(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - std::vector<CG_outputRepr *> subs; - - for (int i = 1; i <= R.n_out(); i++) { - Relation mapping(R.n_out(), 1); - F_And *f_root = mapping.add_and(); - EQ_Handle h = f_root->add_EQ(); - h.update_coef(mapping.output_var(1), 1); - h.update_coef(mapping.input_var(i), -1); - Relation r = Composition(mapping, copy(R)); - r.simplify(); - - Variable_ID v = r.output_var(1); - CG_outputRepr *repr = NULL; - std::pair<EQ_Handle, int> result = find_simplest_assignment(r, v, assigned_on_the_fly); - if (result.second < INT_MAX) - repr = output_substitution_repr(ocg, result.first, v, true, r, assigned_on_the_fly); - else { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v); - if (result.first) - try { - repr = output_inequality_repr(ocg, result.second, v, R, assigned_on_the_fly); - } - catch (const codegen_error &) { - } - } - - subs.push_back(repr); - } - - return subs; -} - - -// -// handle floor definition wildcards in equality, the second in returned pair -// is the cost. -// -std::pair<EQ_Handle, int> find_simplest_assignment(const Relation &R, Variable_ID v, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - Conjunct *c = const_cast<Relation &>(R).single_conjunct(); - - int min_cost = INT_MAX; - EQ_Handle eq; - for (EQ_Iterator e(c->EQs()); e; e++) - if (!(*e).has_wildcards() && (*e).get_coef(v) != 0) { - int cost = 0; - - if (abs((*e).get_coef(v)) != 1) - cost += 4; // divide cost - - int num_var = 0; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var() != v) { - num_var++; - if (abs(cvi.curr_coef()) != 1) - cost += 2; // multiply cost - if (cvi.curr_var()->kind() == Global_Var && cvi.curr_var()->get_global_var()->arity() > 0) - cost += 10; // function cost - else if (cvi.curr_var()->kind() == Input_Var && - assigned_on_the_fly.size() >= cvi.curr_var()->get_position() && - assigned_on_the_fly[cvi.curr_var()->get_position()-1].first != NULL) - cost += assigned_on_the_fly[cvi.curr_var()->get_position()-1].second; // substitution cost on record - } - if ((*e).get_const() != 0) - num_var++; - if (num_var > 1) - cost += num_var - 1; // addition cost - - if (cost < min_cost) { - min_cost = cost; - eq = *e; - } - } - - if (min_cost < INT_MAX) - return std::make_pair(eq, min_cost); - - for (EQ_Iterator e(c->EQs()); e; e++) - if ((*e).has_wildcards() && (*e).get_coef(v) != 0) { - bool is_assignment = true; - for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v); - if (!result.first) { - is_assignment = false; - break; - } - } - if (!is_assignment) - continue; - - int cost = 0; - - if (abs((*e).get_coef(v)) != 1) - cost += 4; // divide cost - - int num_var = 0; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if (cvi.curr_var() != v) { - num_var++; - if (abs(cvi.curr_coef()) != 1) - cost += 2; // multiply cost - if (cvi.curr_var()->kind() == Wildcard_Var) - cost += 10; // floor operation cost - else if (cvi.curr_var()->kind() == Global_Var && cvi.curr_var()->get_global_var()->arity() > 0) - cost += 20; // function cost - else if (cvi.curr_var()->kind() == Input_Var && - assigned_on_the_fly.size() >= cvi.curr_var()->get_position() && - assigned_on_the_fly[cvi.curr_var()->get_position()-1].first != NULL) - cost += assigned_on_the_fly[cvi.curr_var()->get_position()-1].second; // substitution cost on record - } - if ((*e).get_const() != 0) - num_var++; - if (num_var > 1) - cost += num_var - 1; // addition cost - - if (cost < min_cost) { - min_cost = cost; - eq = *e; - } - } - - return std::make_pair(eq, min_cost); -} - - -// -// find floor definition for variable v, e.g. m-c <= 4v <= m, (c is -// constant and 0 <= c < 4). this translates to v = floor(m, 4) and -// return 4v<=m in this case. All wildcards in such inequality are -// also floor defined. -// -std::pair<bool, GEQ_Handle> find_floor_definition(const Relation &R, Variable_ID v, std::set<Variable_ID> excluded_floor_vars) { - Conjunct *c = const_cast<Relation &>(R).single_conjunct(); - - excluded_floor_vars.insert(v); - for (GEQ_Iterator e = c->GEQs(); e; e++) { - coef_t a = (*e).get_coef(v); - if (a >= -1) - continue; - a = -a; - - bool interested = true; - for (std::set<Variable_ID>::const_iterator i = excluded_floor_vars.begin(); i != excluded_floor_vars.end(); i++) - if ((*i) != v && (*e).get_coef(*i) != 0) { - interested = false; - break; - } - if (!interested) - continue; - - // check if any wildcard is floor defined - bool has_undefined_wc = false; - for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) - if (excluded_floor_vars.find(cvi.curr_var()) == excluded_floor_vars.end()) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var(), excluded_floor_vars); - if (!result.first) { - has_undefined_wc = true; - break; - } - } - if (has_undefined_wc) - continue; - - // find the matching upper bound for floor definition - for (GEQ_Iterator e2 = c->GEQs(); e2; e2++) - if ((*e2).get_coef(v) == a && (*e).get_const() + (*e2).get_const() < a) { - bool match = true; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - if ((*e2).get_coef(cvi.curr_var()) != -cvi.curr_coef()) { - match = false; - break; - } - if (!match) - continue; - for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) - if ((*e).get_coef(cvi.curr_var()) != -cvi.curr_coef()) { - match = false; - break; - } - if (match) - return std::make_pair(true, *e); - } - } - - return std::make_pair(false, GEQ_Handle()); -} - -// -// find the stride involving the specified variable, the stride -// equality can have other wildcards as long as they are defined as -// floor variables. -// -std::pair<EQ_Handle, Variable_ID> find_simplest_stride(const Relation &R, Variable_ID v) { - int best_num_var = INT_MAX; - coef_t best_coef; - EQ_Handle best_eq; - Variable_ID best_stride_wc; - for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++) - if ((*e).has_wildcards() && (*e).get_coef(v) != 0) { - bool is_stride = true; - bool found_free = false; - int num_var = 0; - int num_floor = 0; - Variable_ID stride_wc; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: { - bool is_free = true; - for (GEQ_Iterator e2(const_cast<Relation &>(R).single_conjunct()->GEQs()); e2; e2++) - if ((*e2).get_coef(cvi.curr_var()) != 0) { - is_free = false; - break; - } - if (is_free) { - if (found_free) - is_stride = false; - else { - found_free = true; - stride_wc = cvi.curr_var(); - } - } - else { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var()); - if (result.first) - num_floor++; - else - is_stride = false; - } - break; - } - case Input_Var: - num_var++; - break; - default: - ; - } - - if (!is_stride) - break; - } - - if (is_stride) { - coef_t coef = abs((*e).get_coef(v)); - if (best_num_var == INT_MAX || coef < best_coef || - (coef == best_coef && num_var < best_num_var)) { - best_coef = coef; - best_num_var = num_var; - best_eq = *e; - best_stride_wc = stride_wc; - } - } - } - - if (best_num_var != INT_MAX) - return std::make_pair(best_eq, best_stride_wc); - else - return std::make_pair(EQ_Handle(), static_cast<Variable_ID>(NULL)); -} - -// -// convert relation to if-condition -// -CG_outputRepr *output_guard(CG_outputBuilder *ocg, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - assert(R.n_out()==0); - - CG_outputRepr *result = NULL; - Conjunct *c = const_cast<Relation &>(R).single_conjunct(); - - // e.g. 4i=5*j - for (EQ_Iterator e = c->EQs(); e; e++) - if (!(*e).has_wildcards()) { - CG_outputRepr *lhs = NULL; - CG_outputRepr *rhs = NULL; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); - } - else { // coef < 0 - if (coef == -1) - rhs = ocg->CreatePlus(rhs, v); - else - rhs = ocg->CreatePlus(rhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); - } - } - coef_t c = (*e).get_const(); - - CG_outputRepr *term; - if (lhs == NULL) - term = ocg->CreateEQ(rhs, ocg->CreateInt(c)); - else { - if (c > 0) - rhs = ocg->CreateMinus(rhs, ocg->CreateInt(c)); - else if (c < 0) - rhs = ocg->CreatePlus(rhs, ocg->CreateInt(-c)); - else if (rhs == NULL) - rhs = ocg->CreateInt(0); - term = ocg->CreateEQ(lhs, rhs); - } - result = ocg->CreateAnd(result, term); - } - - // e.g. i>5j - for (GEQ_Iterator e = c->GEQs(); e; e++) - if (!(*e).has_wildcards()) { - CG_outputRepr *lhs = NULL; - CG_outputRepr *rhs = NULL; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); - } - else { // coef < 0 - if (coef == -1) - rhs = ocg->CreatePlus(rhs, v); - else - rhs = ocg->CreatePlus(rhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); - } - } - coef_t c = (*e).get_const(); - - CG_outputRepr *term; - if (lhs == NULL) - term = ocg->CreateLE(rhs, ocg->CreateInt(c)); - else { - if (c > 0) - rhs = ocg->CreateMinus(rhs, ocg->CreateInt(c)); - else if (c < 0) - rhs = ocg->CreatePlus(rhs, ocg->CreateInt(-c)); - else if (rhs == NULL) - rhs = ocg->CreateInt(0); - term = ocg->CreateGE(lhs, rhs); - } - result = ocg->CreateAnd(result, term); - } - - // e.g. 4i=5j+4alpha - for (EQ_Iterator e = c->EQs(); e; e++) - if ((*e).has_wildcards()) { - Variable_ID wc; - int num_wildcard = 0; - int num_positive = 0; - int num_negative = 0; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - if (cvi.curr_var()->kind() == Wildcard_Var) { - num_wildcard++; - wc = cvi.curr_var(); - } - else { - if (cvi.curr_coef() > 0) - num_positive++; - else - num_negative++; - } - } - - if (num_wildcard > 1) { - delete result; - throw codegen_error("Can't generate equality condition with multiple wildcards"); - } - int sign = (num_positive>=num_negative)?1:-1; - - CG_outputRepr *lhs = NULL; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - if (cvi.curr_var() != wc) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - if (sign == 1) { - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); - } - else { // coef < 0 - if (coef == -1) - lhs = ocg->CreateMinus(lhs, v); - else - lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); - } - } - else { - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreateMinus(lhs, v); - else - lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); - } - else { // coef < 0 - if (coef == -1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); - } - } - } - } - coef_t c = (*e).get_const(); - if (sign == 1) { - if (c > 0) - lhs = ocg->CreatePlus(lhs, ocg->CreateInt(c)); - else if (c < 0) - lhs = ocg->CreateMinus(lhs, ocg->CreateInt(-c)); - } - else { - if (c > 0) - lhs = ocg->CreateMinus(lhs, ocg->CreateInt(c)); - else if (c < 0) - lhs = ocg->CreatePlus(lhs, ocg->CreateInt(-c)); - } - - lhs = ocg->CreateIntegerMod(lhs, ocg->CreateInt(abs((*e).get_coef(wc)))); - CG_outputRepr *term = ocg->CreateEQ(lhs, ocg->CreateInt(0)); - result = ocg->CreateAnd(result, term); - } - - // e.g. 4alpha<=i<=5alpha - for (GEQ_Iterator e = c->GEQs(); e; e++) - if ((*e).has_wildcards()) { - Variable_ID wc; - int num_wildcard = 0; - for (Constr_Vars_Iter cvi(*e, true); cvi; cvi++) - if (num_wildcard == 0) { - wc = cvi.curr_var(); - num_wildcard = 1; - } - else - num_wildcard++; - - if (num_wildcard > 1) { - delete result; - // e.g. c*alpha - x >= 0 (*) - // -d*alpha + y >= 0 (*) - // e1*alpha + f1*beta + g1 >= 0 (**) - // e2*alpha + f2*beta + g2 >= 0 (**) - // ... - // TODO: should generate a testing loop for alpha using its lower and - // upper bounds from (*) constraints and do the same if-condition test - // for beta from each pair of opposite (**) constraints as above, - // and exit the loop when if-condition satisfied. - throw codegen_error("Can't generate multiple wildcard GEQ guards right now"); - } - - coef_t c = (*e).get_coef(wc); - int sign = (c>0)?1:-1; - - GEQ_Iterator e2 = e; - e2++; - for ( ; e2; e2++) { - coef_t c2 = (*e2).get_coef(wc); - if (c2 == 0) - continue; - int sign2 = (c2>0)?1:-1; - if (sign != -sign2) - continue; - int num_wildcard2 = 0; - for (Constr_Vars_Iter cvi(*e2, true); cvi; cvi++) - num_wildcard2++; - if (num_wildcard2 > 1) - continue; - - GEQ_Handle lb, ub; - if (sign == 1) { - lb = (*e); - ub = (*e2); - } - else { - lb = (*e2); - ub = (*e); - } - - CG_outputRepr *lhs = NULL; - for (Constr_Vars_Iter cvi(lb); cvi; cvi++) - if (cvi.curr_var() != wc) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - if (coef > 0) { - if (coef == 1) - lhs = ocg->CreateMinus(lhs, v); - else - lhs = ocg->CreateMinus(lhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); - } - else { // coef < 0 - if (coef == -1) - lhs = ocg->CreatePlus(lhs, v); - else - lhs = ocg->CreatePlus(lhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); - } - } - coef_t c = lb.get_const(); - if (c > 0) - lhs = ocg->CreateMinus(lhs, ocg->CreateInt(c)); - else if (c < 0) - lhs = ocg->CreatePlus(lhs, ocg->CreateInt(-c)); - - CG_outputRepr *rhs = NULL; - for (Constr_Vars_Iter cvi(ub); cvi; cvi++) - if (cvi.curr_var() != wc) { - CG_outputRepr *v = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - coef_t coef = cvi.curr_coef(); - if (coef > 0) { - if (coef == 1) - rhs = ocg->CreatePlus(rhs, v); - else - rhs = ocg->CreatePlus(rhs, ocg->CreateTimes(ocg->CreateInt(coef), v)); - } - else { // coef < 0 - if (coef == -1) - rhs = ocg->CreateMinus(rhs, v); - else - rhs = ocg->CreateMinus(rhs, ocg->CreateTimes(ocg->CreateInt(-coef), v)); - } - } - c = ub.get_const(); - if (c > 0) - rhs = ocg->CreatePlus(rhs, ocg->CreateInt(c)); - else if (c < 0) - rhs = ocg->CreateMinus(rhs, ocg->CreateInt(-c)); - - rhs = ocg->CreateIntegerFloor(rhs, ocg->CreateInt(-ub.get_coef(wc))); - rhs = ocg->CreateTimes(ocg->CreateInt(lb.get_coef(wc)), rhs); - CG_outputRepr *term = ocg->CreateLE(lhs, rhs); - result = ocg->CreateAnd(result, term); - } - } - - return result; -} - - -// -// return NULL if 0 -// -CG_outputRepr *output_inequality_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly, std::set<Variable_ID> excluded_floor_vars) { - const_cast<Relation &>(R).setup_names(); // hack - - coef_t a = inequality.get_coef(v); - assert(a != 0); - excluded_floor_vars.insert(v); - - CG_outputRepr *repr = NULL; - for (Constr_Vars_Iter cvi(inequality); cvi; cvi++) - if (cvi.curr_var() != v) { - CG_outputRepr *t; - if (cvi.curr_var()->kind() == Wildcard_Var) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, cvi.curr_var(), excluded_floor_vars); - if (!result.first) { - delete repr; - throw codegen_error("Can't generate bound expression with wildcard not involved in floor definition"); - } - try { - t = output_inequality_repr(ocg, result.second, cvi.curr_var(), R, assigned_on_the_fly, excluded_floor_vars); - } - catch (const std::exception &e) { - delete repr; - throw e; - } - } - else - t = output_ident(ocg, R, cvi.curr_var(), assigned_on_the_fly); - - coef_t coef = cvi.curr_coef(); - if (a > 0) { - if (coef > 0) { - if (coef == 1) - repr = ocg->CreateMinus(repr, t); - else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); - } - else { - if (coef == -1) - repr = ocg->CreatePlus(repr, t); - else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); - } - } - else { - if (coef > 0) { - if (coef == 1) - repr = ocg->CreatePlus(repr, t); - else - repr = ocg->CreatePlus(repr, ocg->CreateTimes(ocg->CreateInt(coef), t)); - } - else { - if (coef == -1) - repr = ocg->CreateMinus(repr, t); - else - repr = ocg->CreateMinus(repr, ocg->CreateTimes(ocg->CreateInt(-coef), t)); - } - } - } - coef_t c = inequality.get_const(); - if (c > 0) { - if (a > 0) - repr = ocg->CreateMinus(repr, ocg->CreateInt(c)); - else - repr = ocg->CreatePlus(repr, ocg->CreateInt(c)); - } - else if (c < 0) { - if (a > 0) - repr = ocg->CreatePlus(repr, ocg->CreateInt(-c)); - else - repr = ocg->CreateMinus(repr, ocg->CreateInt(-c)); - } - - if (abs(a) == 1) - return repr; - else if (a > 0) - return ocg->CreateIntegerCeil(repr, ocg->CreateInt(a)); - else // a < 0 - return ocg->CreateIntegerFloor(repr, ocg->CreateInt(-a)); -} - - -// -// nothing special, just an alias -// -CG_outputRepr *output_upper_bound_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const Relation &R, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - assert(inequality.get_coef(v) < 0); - CG_outputRepr* zero_; - - zero_ = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly); - - if(!zero_) - zero_ = ocg->CreateInt(0); - - return zero_; - -} - - -// -// output lower bound with respect to lattice -// -CG_outputRepr *output_lower_bound_repr(CG_outputBuilder *ocg, const GEQ_Handle &inequality, Variable_ID v, const EQ_Handle &stride_eq, Variable_ID wc, const Relation &R, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - assert(inequality.get_coef(v) > 0); - CG_outputRepr* zero_; - if (wc == NULL || bound_must_hit_stride(inequality, v, stride_eq, wc, R, known)){ - zero_ = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly); - if(!zero_) - zero_ = ocg->CreateInt(0); - - return zero_; - } - CG_outputRepr *strideBoundRepr = NULL; - int sign = (stride_eq.get_coef(v)>0)?1:-1; - for (Constr_Vars_Iter cvi(stride_eq); cvi; cvi++) { - Variable_ID v2 = cvi.curr_var(); - if (v2 == v || v2 == wc) - continue; - - CG_outputRepr *v_repr; - if (v2->kind() == Input_Var || v2->kind() == Global_Var) - v_repr = output_ident(ocg, R, v2, assigned_on_the_fly); - else if (v2->kind() == Wildcard_Var) { - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v2); - assert(result.first); - v_repr = output_inequality_repr(ocg, result.second, v2, R, assigned_on_the_fly); - } - - coef_t coef = cvi.curr_coef(); - if (sign < 0) { - if (coef > 0) { - if (coef == 1) - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr); - else - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(coef), v_repr)); - } - else { // coef < 0 - if (coef == -1) - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr); - else - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(-coef), v_repr)); - } - } - else { - if (coef > 0) { - if (coef == 1) - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, v_repr); - else - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(coef), v_repr)); - } - else { // coef < 0 - if (coef == -1) - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, v_repr); - else - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateTimes(ocg->CreateInt(-coef), v_repr)); - } - } - } - coef_t c = stride_eq.get_const(); - if (c > 0) { - if (sign < 0) - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateInt(c)); - else - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateInt(c)); - } - else if (c < 0) { - if (sign < 0) - strideBoundRepr = ocg->CreateMinus(strideBoundRepr, ocg->CreateInt(-c)); - else - strideBoundRepr = ocg->CreatePlus(strideBoundRepr, ocg->CreateInt(-c)); - } - - CG_outputRepr *repr = output_inequality_repr(ocg, inequality, v, R, assigned_on_the_fly); - CG_outputRepr *repr2 = ocg->CreateCopy(repr); - repr = ocg->CreatePlus(repr2, ocg->CreateIntegerMod(ocg->CreateMinus(strideBoundRepr, repr), ocg->CreateInt(abs(stride_eq.get_coef(wc))))); - - return repr; -} - - -// -// return loop control structure only -// -CG_outputRepr *output_loop(CG_outputBuilder *ocg, const Relation &R, int level, const Relation &known, const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - std::pair<EQ_Handle, Variable_ID> result = find_simplest_stride(R, const_cast<Relation &>(R).set_var(level)); - if (result.second != NULL) - assert(abs(result.first.get_coef(const_cast<Relation &>(R).set_var(level))) == 1); - - std::vector<CG_outputRepr *> lbList, ubList; - try { - - coef_t const_lb = negInfinity, const_ub = posInfinity; - - for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); e; e++) { - coef_t coef = (*e).get_coef(const_cast<Relation &>(R).set_var(level)); - - if (coef > 0) { - CG_outputRepr *repr = output_lower_bound_repr(ocg, *e, const_cast<Relation &>(R).set_var(level), result.first, result.second, R, known, assigned_on_the_fly); - if (repr == NULL) - repr = ocg->CreateInt(0); - lbList.push_back(repr); - - if ((*e).is_const(const_cast<Relation &>(R).set_var(level))){ - if(!result.second) { - - //no variables but v in constr - coef_t L,m; - L = -((*e).get_const()); - - m = (*e).get_coef(const_cast<Relation &>(R).set_var(level)); - coef_t sb = (int) (ceil(((float) L) /m)); - set_max(const_lb, sb); - } - else{ - - coef_t L,m,s,c; - L = -((*e).get_const()); - m = (*e).get_coef(const_cast<Relation &>(R).set_var(level)); - s = abs(result.first.get_coef(result.second)); - c = result.first.get_const(); - coef_t sb = (s * (int) (ceil( (float) (L - (c * m)) /(s*m))))+ c; - set_max(const_lb, sb); - - } - } - - } - else if (coef < 0) { - CG_outputRepr *repr = output_upper_bound_repr(ocg, *e, const_cast<Relation &>(R).set_var(level), R, assigned_on_the_fly); - if (repr == NULL) - repr = ocg->CreateInt(0); - ubList.push_back(repr); - - if ((*e).is_const(const_cast<Relation &>(R).set_var(level))) { - // no variables but v in constraint - set_min(const_ub,-(*e).get_const()/(*e).get_coef(const_cast<Relation &>(R).set_var(level))); - } - - } - } - - if(fillInBounds && lbList.size() == 1 && const_lb != negInfinity) - lowerBoundForLevel = const_lb; - - if(fillInBounds && const_ub != posInfinity) - upperBoundForLevel = const_ub; - if (lbList.size() == 0) - throw codegen_error("missing lower bound at loop level " + to_string(level)); - if (ubList.size() == 0) - throw codegen_error("missing upper bound at loop level " + to_string(level)); - } - catch (const std::exception &e) { - for (int i = 0; i < lbList.size(); i++) - delete lbList[i]; - for (int i = 0; i < ubList.size(); i++) - delete ubList[i]; - throw e; - } - - CG_outputRepr *lbRepr = NULL; - if (lbList.size() > 1) - lbRepr = ocg->CreateInvoke("max", lbList); - else // (lbList.size() == 1) - lbRepr = lbList[0]; - - CG_outputRepr *ubRepr = NULL; - if (ubList.size() > 1) - ubRepr = ocg->CreateInvoke("min", ubList); - else // (ubList.size() == 1) - ubRepr = ubList[0]; - - CG_outputRepr *stRepr; - if (result.second == NULL) - stRepr = ocg->CreateInt(1); - else - stRepr = ocg->CreateInt(abs(result.first.get_coef(result.second))); - CG_outputRepr *indexRepr = output_ident(ocg, R, const_cast<Relation &>(R).set_var(level), assigned_on_the_fly); - return ocg->CreateInductive(indexRepr, lbRepr, ubRepr, stRepr); -} - - -// -// parameter f_root is inside f_exists, not the other way around. -// return replicated variable in new relation, with all cascaded floor definitions -// using wildcards defined in the same way as in the original relation. -// -Variable_ID replicate_floor_definition(const Relation &R, const Variable_ID floor_var, - Relation &r, F_Exists *f_exists, F_And *f_root, - std::map<Variable_ID, Variable_ID> &exists_mapping) { - assert(R.n_out() == 0 && r.n_out() == 0 && R.n_inp() == r.n_inp()); - - std::set<Variable_ID> excluded_floor_vars; - std::stack<Variable_ID> to_fill; - to_fill.push(floor_var); - - while (!to_fill.empty()) { - Variable_ID v = to_fill.top(); - to_fill.pop(); - if (excluded_floor_vars.find(v) != excluded_floor_vars.end()) - continue; - - std::pair<bool, GEQ_Handle> result = find_floor_definition(R, v, excluded_floor_vars); - assert(result.first); - excluded_floor_vars.insert(v); - - GEQ_Handle h1 = f_root->add_GEQ(); - GEQ_Handle h2 = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(result.second); cvi; cvi++) { - Variable_ID v2 = cvi.curr_var(); - switch (v2->kind()) { - case Input_Var: { - int pos = v2->get_position(); - h1.update_coef(r.input_var(pos), cvi.curr_coef()); - h2.update_coef(r.input_var(pos), -cvi.curr_coef()); - break; - } - case Wildcard_Var: { - std::map<Variable_ID, Variable_ID>::iterator p = exists_mapping.find(v2); - Variable_ID v3; - if (p == exists_mapping.end()) { - v3 = f_exists->declare(); - exists_mapping[v2] = v3; - } - else - v3 = p->second; - h1.update_coef(v3, cvi.curr_coef()); - h2.update_coef(v3, -cvi.curr_coef()); - if (v2 != v) - to_fill.push(v2); - break; - } - case Global_Var: { - Global_Var_ID g = v2->get_global_var(); - Variable_ID v3; - if (g->arity() == 0) - v3 = r.get_local(g); - else - v3 = r.get_local(g, v2->function_of()); - h1.update_coef(v3, cvi.curr_coef()); - h2.update_coef(v3, -cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h1.update_const(result.second.get_const()); - h2.update_const(-result.second.get_const()-result.second.get_coef(v)-1); - } - - if (floor_var->kind() == Input_Var) - return r.input_var(floor_var->get_position()); - else if (floor_var->kind() == Wildcard_Var) - return exists_mapping[floor_var]; - else - assert(false); -} - - -// -// pick one guard condition from relation. it can involve multiple -// constraints when involving wildcards, as long as its complement -// is a single conjunct. -// -Relation pick_one_guard(const Relation &R, int level) { - assert(R.n_out()==0); - - Relation r = Relation::True(R.n_set()); - - for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); e; e++) - if (!(*e).has_wildcards()) { - r.and_with_GEQ(*e); - r.simplify(); - r.copy_names(R); - r.setup_names(); - return r; - } - - for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++) - if (!(*e).has_wildcards()) { - r.and_with_GEQ(*e); - r.simplify(); - r.copy_names(R); - r.setup_names(); - return r; - } - - for (EQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->EQs()); e; e++) - if ((*e).has_wildcards()) { - int num_wildcard = 0; - int max_level = 0; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: - num_wildcard++; - break; - case Input_Var: - if (cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - break; - default: - ; - } - - if (num_wildcard == 1 && max_level != level-1) { - r.and_with_EQ(*e); - r.simplify(); - r.copy_names(R); - r.setup_names(); - return r; - } - } - - for (GEQ_Iterator e(const_cast<Relation &>(R).single_conjunct()->GEQs()); e; e++) - if ((*e).has_wildcards()) { - int num_wildcard = 0; - int max_level = 0; - bool direction; - Variable_ID wc; - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: - num_wildcard++; - wc = cvi.curr_var(); - direction = cvi.curr_coef()>0?true:false; - break; - case Input_Var: - if (cvi.curr_var()->get_position() > max_level) - max_level = cvi.curr_var()->get_position(); - break; - default: - ; - } - - if (num_wildcard == 1 && max_level != level-1) { - // find the pairing inequality - GEQ_Iterator e2 = e; - e2++; - for ( ; e2; e2++) { - int num_wildcard2 = 0; - int max_level2 = 0; - bool direction2; - Variable_ID wc2; - for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: - num_wildcard2++; - wc2 = cvi.curr_var(); - direction2 = cvi.curr_coef()>0?true:false; - break; - case Input_Var: - if (cvi.curr_var()->get_position() > max_level2) - max_level2 = cvi.curr_var()->get_position(); - break; - default: - ; - } - - if (num_wildcard2 == 1 && max_level2 != level-1 && wc2 == wc && direction2 == not direction) { - F_Exists *f_exists = r.and_with_and()->add_exists(); - Variable_ID wc3 = f_exists->declare(); - F_And *f_root = f_exists->add_and(); - GEQ_Handle h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*e); cvi; cvi++) { - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: - h.update_coef(wc3, cvi.curr_coef()); - break; - case Input_Var: - h.update_coef(r.input_var(cvi.curr_var()->get_position()), cvi.curr_coef()); - break; - case Global_Var: { - Global_Var_ID g = cvi.curr_var()->get_global_var(); - Variable_ID v; - if (g->arity() == 0) - v = r.get_local(g); - else - v = r.get_local(g, cvi.curr_var()->function_of()); - h.update_coef(v, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const((*e).get_const()); - - h = f_root->add_GEQ(); - for (Constr_Vars_Iter cvi(*e2); cvi; cvi++) { - switch (cvi.curr_var()->kind()) { - case Wildcard_Var: - h.update_coef(wc3, cvi.curr_coef()); - break; - case Input_Var: - h.update_coef(r.input_var(cvi.curr_var()->get_position()), cvi.curr_coef()); - break; - case Global_Var: { - Global_Var_ID g = cvi.curr_var()->get_global_var(); - Variable_ID v; - if (g->arity() == 0) - v = r.get_local(g); - else - v = r.get_local(g, cvi.curr_var()->function_of()); - h.update_coef(v, cvi.curr_coef()); - break; - } - default: - assert(false); - } - } - h.update_const((*e2).get_const()); - - r.simplify(); - r.copy_names(R); - r.setup_names(); - return r; - } - } - } - } -} - - -// -// heavy lifting for code output for one leaf node -// -CG_outputRepr *leaf_print_repr(BoolSet<> active, const std::map<int, Relation> &guards, - CG_outputRepr *guard_repr, const Relation &known, - int indent, CG_outputBuilder *ocg, const std::vector<int> &remap, - const std::vector<Relation> &xforms, const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - if (active.num_elem() == 0) - return NULL; - - CG_outputRepr *stmt_list = NULL; - for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) { - std::map<int, Relation>::const_iterator j = guards.find(*i); - if (j == guards.end() || Must_Be_Subset(copy(known), copy(j->second))) { - Relation mapping = Inverse(copy((xforms[remap[*i]]))); - mapping.simplify(); - mapping.setup_names(); - std::vector<std::string> loop_vars; - for (int k = 1; k <= mapping.n_out(); k++) { - loop_vars.push_back(mapping.output_var(k)->name()); -// std::cout << "CG_Utils:: " << k << ", " << mapping.output_var(k)->name().c_str() << "\n"; - } - std::vector<CG_outputRepr *> sList = output_substitutions(ocg, mapping, assigned_on_the_fly); - stmt_list = ocg->StmtListAppend(stmt_list, ocg->CreateSubstitutedStmt((guard_repr==NULL)?indent:indent+1, stmts[remap[*i]]->clone(), loop_vars, sList)); - active.unset(*i); - } - } - - if (stmt_list != NULL) { - if (active.num_elem() != 0) - stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(active, guards, NULL, known, (guard_repr==NULL)?indent:indent+1, ocg, remap, xforms, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); - } - else { - Relation then_cond = find_best_guard(const_cast<std::map<int, Relation> &>(guards)[*(active.begin())], active, guards); - assert(!then_cond.is_obvious_tautology()); - Relation new_then_known = Intersection(copy(known), copy(then_cond)); - new_then_known.simplify(); - Relation else_cond = Complement(copy(then_cond)); - else_cond.simplify(); - Relation new_else_known = Intersection(copy(known), copy(else_cond)); - new_else_known.simplify(); - - BoolSet<> then_active(active.size()), else_active(active.size()), indep_active(active.size()); - std::map<int, Relation> then_guards, else_guards; - for (BoolSet<>::iterator i = active.begin(); i != active.end(); i++) { - Relation &r = const_cast<std::map<int, Relation> &>(guards)[*i]; - if (Must_Be_Subset(copy(r), copy(then_cond))) { - Relation r2 = Gist(copy(r), copy(then_cond), 1); - if (!r2.is_obvious_tautology()) - then_guards[*i] = r2; - then_active.set(*i); - } - else if (Must_Be_Subset(copy(r), copy(else_cond))) { - Relation r2 = Gist(copy(r), copy(else_cond), 1); - if (!r2.is_obvious_tautology()) - else_guards[*i] = r2; - else_active.set(*i); - } - else - indep_active.set(*i); - } - assert(!then_active.empty()); - - CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, assigned_on_the_fly); - if (else_active.empty() && indep_active.empty()) { - guard_repr = ocg->CreateAnd(guard_repr, new_guard_repr); - return leaf_print_repr(then_active, then_guards, guard_repr, new_then_known, indent, ocg, remap, xforms, stmts, assigned_on_the_fly); - } - else if (else_active.empty() && !indep_active.empty()) { - int new_indent = (guard_repr==NULL)?indent:indent+1; - stmt_list = leaf_print_repr(then_active, then_guards, new_guard_repr, new_then_known, new_indent, ocg, remap, xforms, stmts, assigned_on_the_fly); - stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(indep_active, guards, NULL, known, new_indent, ocg, remap, xforms, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); - } - else { // (!else_active.empty()) - int new_indent = (guard_repr==NULL)?indent:indent+1; - CG_outputRepr *then_stmt_list = leaf_print_repr(then_active, then_guards, NULL, new_then_known, new_indent+1, ocg, remap, xforms, stmts, assigned_on_the_fly); - CG_outputRepr *else_stmt_list = leaf_print_repr(else_active, else_guards, NULL, new_else_known, new_indent+1, ocg, remap, xforms, stmts, assigned_on_the_fly); - stmt_list = ocg->CreateIf(new_indent, new_guard_repr, then_stmt_list, else_stmt_list); - if (!indep_active.empty()) - stmt_list = ocg->StmtListAppend(stmt_list, leaf_print_repr(indep_active, guards, NULL, known, new_indent, ocg, remap, xforms, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); - } - } -} - - -// -// heavy lifting for code output for one level of loop nodes -// -CG_outputRepr *loop_print_repr(const std::vector<CG_loop *> &loops, int start, int end, - const Relation &guard, CG_outputRepr *guard_repr, - int indent, CG_outputBuilder *ocg, const std::vector<CG_outputRepr *> &stmts, - const std::vector<std::pair<CG_outputRepr *, int> > &assigned_on_the_fly) { - if (start >= end) - return NULL; - - Relation R = Gist(copy(loops[start]->guard_), copy(guard), 1); - if (Must_Be_Subset(Intersection(copy(loops[start]->known_), copy(guard)), copy(R))) { - int new_indent = (guard_repr==NULL)?indent:indent+1; - int i = start+1; - for ( ; i < end; i++) - if (!Gist(copy(loops[i]->guard_), copy(guard), 1).is_obvious_tautology()) - break; - CG_outputRepr *stmt_list = NULL; - for (int j = start; j < i; j++) - stmt_list = ocg->StmtListAppend(stmt_list, loops[j]->printRepr(false, new_indent, ocg, stmts, assigned_on_the_fly)); - stmt_list = ocg->StmtListAppend(stmt_list, loop_print_repr(loops, i, end, guard, NULL, new_indent, ocg, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); - } - - Relation then_cond = find_best_guard(R, loops, start, end); - assert(!then_cond.is_obvious_tautology()); - Relation else_cond = Complement(copy(then_cond)); - else_cond.simplify(); - - std::vector<CG_loop *> then_loops, else_loops, indep_loops; - int i = start; - for ( ; i < end; i++) - if (!Must_Be_Subset(copy(loops[i]->guard_), copy(then_cond))) - break; - int j = i; - for ( ; j < end; j++) - if (!Must_Be_Subset(copy(loops[j]->guard_), copy(else_cond))) - break; - assert(i>start); - - CG_outputRepr *new_guard_repr = output_guard(ocg, then_cond, assigned_on_the_fly); - if (j == i && end == j) { - guard_repr = ocg->CreateAnd(guard_repr, new_guard_repr); - Relation new_guard = Intersection(copy(guard), copy(then_cond)); - new_guard.simplify(); - return loop_print_repr(loops, start, end, new_guard, guard_repr, indent, ocg, stmts, assigned_on_the_fly); - } - else if (j == i && end > j) { - int new_indent = (guard_repr==NULL)?indent:indent+1; - Relation new_guard = Intersection(copy(guard), copy(then_cond)); - new_guard.simplify(); - CG_outputRepr *stmt_list = loop_print_repr(loops, start, i, new_guard, new_guard_repr, new_indent, ocg, stmts, assigned_on_the_fly); - stmt_list = ocg->StmtListAppend(stmt_list, loop_print_repr(loops, j, end, guard, NULL, new_indent, ocg, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); - } - else { // (j > i) - int new_indent = (guard_repr==NULL)?indent:indent+1; - Relation then_new_guard = Intersection(copy(guard), copy(then_cond)); - then_new_guard.simplify(); - CG_outputRepr *then_stmt_list = loop_print_repr(loops, start, i, then_new_guard, NULL, new_indent+1, ocg, stmts, assigned_on_the_fly); - Relation else_new_guard = Intersection(copy(guard), copy(else_cond)); - else_new_guard.simplify(); - CG_outputRepr *else_stmt_list = loop_print_repr(loops, i, j, else_new_guard, NULL, new_indent+1, ocg, stmts, assigned_on_the_fly); - CG_outputRepr *stmt_list = ocg->CreateIf(new_indent, new_guard_repr, then_stmt_list, else_stmt_list); - stmt_list = ocg->StmtListAppend(stmt_list, loop_print_repr(loops, j, end, guard, NULL, new_indent, ocg, stmts, assigned_on_the_fly)); - if (guard_repr == NULL) - return stmt_list; - else - return ocg->CreateIf(indent, guard_repr, stmt_list, NULL); - } -} - -} diff --git a/omegalib/codegen/src/codegen.cc b/omegalib/codegen/src/codegen.cc deleted file mode 100755 index 92ca702..0000000 --- a/omegalib/codegen/src/codegen.cc +++ /dev/null @@ -1,378 +0,0 @@ -/***************************************************************************** - Copyright (C) 1994-2000 the Omega Project Team - Copyright (C) 2005-2011 Chun Chen - All Rights Reserved. - - Purpose: - CodeGen class as entry point for code generation. - - Notes: - Loop variable name prefix should not cause any possible name conflicts - with original loop variables wrapped in statement holder. This guarantees - that variable substitution done correctly in the generated code. - - History: - 04/24/96 MMGenerateCode, added by Fortran D people. Lei Zhou - 09/17/08 loop overhead removal based on actual nesting depth -- by chun - 03/05/11 fold MMGenerateCode into CodeGen class, Chun Chen -*****************************************************************************/ - -#include <typeinfo> -#include <omega.h> -#include <basic/util.h> -#include <math.h> -#include <vector> -#include <algorithm> - -#include <code_gen/CG.h> -#include <code_gen/codegen.h> -#include <code_gen/CG_outputBuilder.h> -#include <code_gen/codegen_error.h> - -namespace omega { - -const std::string CodeGen::loop_var_name_prefix = "t"; -const int CodeGen::var_substitution_threshold = 10; - -//Anand--adding stuff to make Chun's code work with Gabe's -std::vector< std::vector<int> > smtNonSplitLevels; -std::vector< std::vector<std::string> > loopIdxNames;//per stmt -std::vector< std::pair<int, std::string> > syncs; - - - -CodeGen::CodeGen(const std::vector<Relation> &xforms, const std::vector<Relation> &IS, const Relation &known, std::vector< std::vector<int> > smtNonSplitLevels_ , std::vector< std::vector<std::string> > loopIdxNames_, std::vector< std::pair<int, std::string> > syncs_) { - // check for sanity of parameters - int num_stmt = IS.size(); - if (xforms.size() != num_stmt) - throw std::invalid_argument("number of iteration spaces does not match number of transformations"); - known_ = copy(known); - if (known_.n_out() != 0) - throw std::invalid_argument("known condition must be a set relation"); - if (known_.is_null()) - known_ = Relation::True(0); - else - known_.simplify(2, 4); - if (!known_.is_upper_bound_satisfiable()) - return; - if (known_.number_of_conjuncts() > 1) - throw std::invalid_argument("only one conjunct allowed in known condition"); - xforms_ = xforms; - for (int i = 0; i < num_stmt; i++) { - xforms_[i].simplify(); - if (!xforms_[i].has_single_conjunct()) - throw std::invalid_argument("mapping relation must have only one conjunct"); - if (xforms_[i].n_inp() != IS[i].n_inp() || IS[i].n_out() != 0) - throw std::invalid_argument("illegal iteration space or transformation arity"); - } - - - //protonu-- - //easier to handle this as a global - smtNonSplitLevels = smtNonSplitLevels_; - syncs = syncs_; - loopIdxNames = loopIdxNames_; - //end-protonu - - - - // find the maximum iteration space dimension we are going to operate on - int num_level = known_.n_inp(); - for (int i = 0; i < num_stmt; i++) - if (xforms_[i].n_out() > num_level) - num_level = xforms_[i].n_out(); - known_ = Extend_Set(known_, num_level-known_.n_inp()); - for (int i = 1; i <= num_level; i++) - known_.name_set_var(i, loop_var_name_prefix + to_string(i)); - known_.setup_names(); - - // split disjoint conjunctions in original iteration spaces - std::vector<Relation> new_IS; - for (int i = 0; i < num_stmt; i++) { - for (int j = 1; j <= IS[i].n_inp(); j++) - xforms_[i].name_input_var(j, const_cast<std::vector<Relation> &>(IS)[i].input_var(j)->name()); - for (int j = 1; j <= xforms_[i].n_out(); j++) - xforms_[i].name_output_var(j, loop_var_name_prefix + to_string(j)); - xforms_[i].setup_names(); - - Relation R = Range(Restrict_Domain(copy(xforms_[i]), copy(IS[i]))); - R = Intersection(Extend_Set(R, num_level-R.n_inp()), copy(known_)); - R.simplify(2, 4); - if (R.is_inexact()) - throw codegen_error("cannot generate code for inexact iteration spaces"); - - while(R.is_upper_bound_satisfiable()) { - DNF *dnf = R.query_DNF(); - DNF_Iterator c(dnf); - Relation R2 = Relation(R, *c); - R2.simplify(); - new_IS.push_back(copy(R2)); - remap_.push_back(i); - c.next(); - if (!c.live()) - break; - Relation remainder(R, *c); - c.next(); - while (c.live()) { - remainder = Union(remainder, Relation(R, *c)); - c.next(); - } - R = Difference(remainder, R2); - R.simplify(2, 4); - } - } - - // number of new statements after splitting - num_stmt = new_IS.size(); - if(!smtNonSplitLevels.empty()) - smtNonSplitLevels.resize(num_stmt); - // assign a dummy value to loops created for the purpose of expanding to maximum dimension - for (int i = 0; i < num_stmt; i++) { - if (xforms[remap_[i]].n_out() < num_level) { - F_And *f_root = new_IS[i].and_with_and(); - for (int j = xforms[remap_[i]].n_out()+1; j <= num_level; j++) { - EQ_Handle h = f_root->add_EQ(); - h.update_coef(new_IS[i].set_var(j), 1); - h.update_const(posInfinity); - } - new_IS[i].simplify(); - } - } - - // calculate projected subspaces for each loop level once and save for CG tree manipulation later - projected_IS_ = std::vector<std::vector<Relation> >(num_level); - for (int i = 0; i < num_level; i++) - projected_IS_[i] = std::vector<Relation>(num_stmt); - for (int i = 0; i < num_stmt; i++) { - if (num_level > 0) - projected_IS_[num_level-1][i] = new_IS[i]; - for (int j = num_level-1; j >= 1; j--) { - projected_IS_[j-1][i] = Project(copy(projected_IS_[j][i]), j+1, Set_Var); - projected_IS_[j-1][i].simplify(2, 4); - } - } -} - - -CG_result *CodeGen::buildAST(int level, const BoolSet<> &active, bool split_on_const, const Relation &restriction) { - if (level > num_level()) - return new CG_leaf(this, active); - - int num_active_stmt = active.num_elem(); - if (num_active_stmt == 0) - return NULL; - else if (num_active_stmt == 1) - return new CG_loop(this, active, level, buildAST(level+1, active, true, restriction)); - - // use estimated constant bounds for fast non-overlap iteration space splitting - if (split_on_const) { - std::vector<std::pair<std::pair<coef_t, coef_t>, int> > bounds; - - for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) { - Relation r = Intersection(copy(projected_IS_[level-1][*i]), copy(restriction)); - r.simplify(2, 4); - if (!r.is_upper_bound_satisfiable()) - continue; - coef_t lb, ub; - r.single_conjunct()->query_variable_bounds(r.set_var(level),lb,ub); - bounds.push_back(std::make_pair(std::make_pair(lb, ub), *i)); - } - sort(bounds.begin(), bounds.end()); - - std::vector<Relation> split_cond; - std::vector<CG_result *> split_child; - - coef_t prev_val = -posInfinity; - coef_t next_val = bounds[0].first.second; - BoolSet<> next_active(active.size()); - int i = 0; - while (i < bounds.size()) { - if (bounds[i].first.first <= next_val) { - next_active.set(bounds[i].second); - next_val = max(next_val, bounds[i].first.second); - i++; - } - else { - Relation r(num_level()); - F_And *f_root = r.add_and(); - if (prev_val != -posInfinity) { - GEQ_Handle h = f_root->add_GEQ(); - h.update_coef(r.set_var(level), 1); - h.update_const(-prev_val-1); - } - if (next_val != posInfinity) { - GEQ_Handle h = f_root->add_GEQ(); - h.update_coef(r.set_var(level), -1); - h.update_const(next_val); - } - r.simplify(); - - Relation new_restriction = Intersection(copy(r), copy(restriction)); - new_restriction.simplify(2, 4); - CG_result *child = buildAST(level, next_active, false, new_restriction); - if (child != NULL) { - split_cond.push_back(copy(r)); - split_child.push_back(child); - } - next_active.unset_all(); - prev_val = next_val; - next_val = bounds[i].first.second; - } - } - if (!next_active.empty()) { - Relation r = Relation::True(num_level()); - if (prev_val != -posInfinity) { - F_And *f_root = r.and_with_and(); - GEQ_Handle h = f_root->add_GEQ(); - h.update_coef(r.set_var(level), 1); - h.update_const(-prev_val-1); - r.simplify(); - } - Relation new_restriction = Intersection(copy(r), copy(restriction)); - new_restriction.simplify(2, 4); - CG_result *child = buildAST(level, next_active, false, new_restriction); - if (child != NULL) { - split_cond.push_back(copy(r)); - split_child.push_back(child); - } - } - - if (split_child.size() == 0) - return NULL; - else if (split_child.size() == 1) - return split_child[0]; - else - return new CG_split(this, active, split_cond, split_child); - } - // check bound conditions exhaustively for non-overlap iteration space splitting - else { - std::vector<Relation> Rs(active.size()); - for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) { - Rs[*i] = Intersection(Approximate(copy(projected_IS_[level-1][*i])), copy(restriction)); - Rs[*i].simplify(2, 4); - } - Relation hull = SimpleHull(Rs); - - //protonu-warn Chun about this change - //This does some fancy splitting of statements into loops with the - //fewest dimentions, but that's not necessarily what we want when - //code-gening for CUDA. smtNonSplitLevels keeps track per-statment of - //the levels that should not be split on. - bool checkForSplits = true; - for (BoolSet<>::const_iterator i = active.begin(); i != active.end(); i++) { - if(*i < smtNonSplitLevels.size()) - for(int k = 0; k <smtNonSplitLevels[*i].size(); k++) - if(smtNonSplitLevels[*i][k] == (level-2)){ - checkForSplits = false; - break; - } - } - - - - - for (BoolSet<>::const_iterator i = active.begin(); i != active.end() && checkForSplits; i++) { - Relation r = Gist(copy(Rs[*i]), copy(hull), 1); - if (r.is_obvious_tautology()) - continue; - r = EQs_to_GEQs(r); - - for (GEQ_Iterator e = r.single_conjunct()->GEQs(); e; e++) { - if ((*e).has_wildcards()) - continue; - - Relation cond = Relation::True(num_level()); - BoolSet<> first_chunk(active.size()); - BoolSet<> second_chunk(active.size()); - - if ((*e).get_coef(hull.set_var(level)) > 0) { - cond.and_with_GEQ(*e); - cond = Complement(cond);; - cond.simplify(); - second_chunk.set(*i); - } - else if ((*e).get_coef(hull.set_var(level)) < 0) { - cond.and_with_GEQ(*e); - cond.simplify(); - first_chunk.set(*i); - } - else - continue; - - bool is_proper_split_cond = true; - for (BoolSet<>::const_iterator j = active.begin(); j != active.end(); j++) - if ( *j != *i) { - bool in_first = Intersection(copy(Rs[*j]), copy(cond)).is_upper_bound_satisfiable(); - bool in_second = Difference(copy(Rs[*j]), copy(cond)).is_upper_bound_satisfiable(); - - if (in_first && in_second) { - is_proper_split_cond = false; - break; - } - - if (in_first) - first_chunk.set(*j); - else if (in_second) - second_chunk.set(*j); - } - - if (is_proper_split_cond && first_chunk.num_elem() != 0 && second_chunk.num_elem() != 0) { - CG_result *first_cg = buildAST(level, first_chunk, false, copy(cond)); - CG_result *second_cg = buildAST(level, second_chunk, false, Complement(copy(cond))); - if (first_cg == NULL) - return second_cg; - else if (second_cg == NULL) - return first_cg; - else { - std::vector<Relation> split_cond; - std::vector<CG_result *> split_child; - split_cond.push_back(copy(cond)); - split_child.push_back(first_cg); - split_cond.push_back(Complement(copy(cond))); - split_child.push_back(second_cg); - - return new CG_split(this, active, split_cond, split_child); - } - } - } - } - return new CG_loop(this, active, level, buildAST(level+1, active, true, restriction)); - } -} - - -CG_result *CodeGen::buildAST(int effort) { - if (remap_.size() == 0) - return NULL; - - CG_result *cgr = buildAST(1, ~BoolSet<>(remap_.size()), true, Relation::True(num_level())); - if (cgr == NULL) - return NULL; - - - // break down the complete iteration space condition to levels of bound/guard condtions - cgr = cgr->recompute(cgr->active_, copy(known_), copy(known_)); - - - - if (cgr == NULL) - return NULL; - - // calculate each loop's nesting depth - int depth = cgr->populateDepth(); - - - // redistribute guard condition locations by additional splittings - std::pair<CG_result *, Relation> result = cgr->liftOverhead(min(effort,depth), false); - - // since guard conditions are postponed for non-loop levels, hoist them now. - // this enables proper if-condition simplication when outputting actual code. - result.first->hoistGuard(); - - - - - return result.first; -} - -} diff --git a/omegalib/codegen/src/rose_attributes.cc b/omegalib/codegen/src/rose_attributes.cc deleted file mode 100644 index bb9681c..0000000 --- a/omegalib/codegen/src/rose_attributes.cc +++ /dev/null @@ -1,183 +0,0 @@ -#include <code_gen/rose_attributes.h> - -namespace omega { - -CodeInsertionAttribute* getOrCreateCodeInsertionAttribute(SgNode* node) { - CodeInsertionAttribute* attr; - if(node->attributeExists("code_insertion")) - return static_cast<CodeInsertionAttribute*>(node->getAttribute("code_insertion")); - attr = new CodeInsertionAttribute(); - node->setAttribute("code_insertion", attr); - return attr; -} - -void postProcessRoseCodeInsertion(SgProject* proj) { - //generatePDF(*proj); - CodeInsertionVisitor visitor = CodeInsertionVisitor(); - visitor.initialize(); - visitor.traverseInputFiles(proj); - visitor.insertCode(); -} - -// Swap a code insertion from one node (sn) to another (dn) -// -- note that this function does not currently remove the insertion from the sn node -void moveCodeInsertion(SgNode* sn, CodeInsertion* ci, SgNode* dn) { - CodeInsertionAttribute* new_attr; - // TODO in the near future: replace the above statement with 'new_attr = getOrCreateCodeInsertionAttribute(...)' - CodeInsertionAttribute* old_attr = static_cast<CodeInsertionAttribute*>(sn->getAttribute("code_insertion")); - if(dn->attributeExists("code_insertion")) { - new_attr = static_cast<CodeInsertionAttribute*>(dn->getAttribute("code_insertion")); - } - else { - new_attr = new CodeInsertionAttribute(); - dn->setAttribute("code_insertion", new_attr); - } - new_attr->add(ci); -} - -// A function that copies a specific attribute from one node to another -// this function exists to get around a ROSE limitation that does not -// copy attributes -void copyAttribute(std::string attr_name, SgNode* s, SgNode* d) { - if(s->attributeExists(attr_name)) { - d->setAttribute(attr_name,s->getAttribute(attr_name)); - } -} - -// TODO: find all existng attributes and iterate over them instead of doing them -// individually -void copyAttributes(SgNode* s, SgNode* d) { - copyAttribute("code_insertion", s, d); - //...any other attributes... -} - -void CodeInsertionVisitor::initialize() { - this->loop_level = 0; - this->ci_marks = std::vector<CodeInsertionMark*>(); -} - -void CodeInsertionVisitor::markStmt(SgStatement* stmt, CodeInsertion* ci) { - // this check prevents multiple copies of stmts - // -- may be changed in the future - if(!ci->marked) { - CodeInsertionMark* pos = new CodeInsertionMark(); - pos->stmt = stmt; - pos->ci = ci; - this->ci_marks.push_back(pos); - ci->marked = true; - } -} - -// increase loop_level as the visitor descends -void CodeInsertionVisitor::preOrderVisit(SgNode* n) { - if (isSgForStatement(n)) { - this->loop_level++; - } -} - -void CodeInsertionVisitor::postOrderVisit(SgNode* n) { - if(isSgForStatement(n)) { - this->loop_level--; - } - if(isSgStatement(n)) { - if(n->attributeExists("code_insertion")) { - CodeInsertionAttribute *attr = static_cast<CodeInsertionAttribute*>(n->getAttribute("code_insertion")); - for(CodeInsertionPtrListItr itr = attr->begin(); itr != attr->end(); ++itr) { - CodeInsertion *insertion = *itr; - // check loop level -- if it is equivelent, mark statement for insertion - // -- else, move attribute up to parent - if(insertion->loop_level != this->loop_level) { - moveCodeInsertion(n, insertion, n->get_parent()); - } - else { - this->markStmt(isSgStatement(n), insertion); - } - } - } - } -} - -// final stage of algorithm that inserts marked statements -void CodeInsertionVisitor::insertCode() { - for(std::vector<CodeInsertionMark*>::iterator itr = this->ci_marks.begin(); itr != this->ci_marks.end(); ++itr) { - CodeInsertionMark* mark = *itr; - SgScopeStatement* scope = static_cast<SgScopeStatement*>(mark->stmt->get_parent()); - SageInterface::insertStatementBefore(mark->stmt, mark->ci->getStatement(scope)); - } -} - -SgStatement* PragmaInsertion::getStatement(SgScopeStatement* scopeStmt) { - SgStatement* stmt = SageBuilder::buildPragmaDeclaration(this->name); - return stmt; -} - -//SgStatement* MMPrefetchInsertion::getStatement(SgScopeStatement* scopeStmt) { -// const SgName& name = SgName("_mm_prefetch"); -// SgType* rtype = SageBuilder::buildVoidType(); -// SgExpression* arr_arg = SageBuilder::buildVarRefExp(this->arrName); -// SgExpression* hint_arg = SageBuilder::buildShortVal(this->cacheHint); -// SgExprListExp* args = SageBuilder::buildExprListExp(arr_arg,hint_arg); -// SgStatement* stmt = SageBuilder::buildFunctionCallStmt(name, rtype, args, scopeStmt); -// return stmt; -//} - -SgStatement* MMPrefetchInsertion::getStatement(SgScopeStatement* scopeStmt) { - const SgName fname = SgName("_mm_prefetch"); - SgType* rtype = SageBuilder::buildVoidType(); - SgExpression* arr_arg = this->buildArrArg(scopeStmt); - SgExpression* hint_arg = SageBuilder::buildShortVal(this->cacheHint); - SgExprListExp* args = SageBuilder::buildExprListExp(arr_arg, hint_arg); - return SageBuilder::buildFunctionCallStmt(fname, rtype, args, scopeStmt); -} - -SgExpression* MMPrefetchInsertion::buildArrArg(SgScopeStatement* scopeStmt) { - // if there are no index arguments given, just return a variable reference - if(this->indexCount == 0) { - const SgName aname = SgName(this->arrName); - return SageBuilder::buildVarRefExp(aname, scopeStmt); - } - std::vector<SgExpression*> argList = std::vector<SgExpression*>(); - // foreach dimension - for(int i = 0; i < this->indexCount; i++) { - argList.push_back(this->makeIndexExp(i, scopeStmt)); - } - return SageBuilder::buildExprListExp(argList); -} - -SgExpression* MMPrefetchInsertion::makeIndexExp(int dim, SgScopeStatement* scopeStmt) { - //(i + offset) or (offset) or (i) - std::string* indexer = this->indecies.at(dim); - int offset = this->offsets.at(dim); - if(indexer == NULL) { - return SageBuilder::buildIntVal(offset); - } - else { - const SgName name = SgName(*indexer); - SgVarRefExp* iref = SageBuilder::buildVarRefExp(name, scopeStmt); - if(offset == 0) { - return iref; - } - else { - return SageBuilder::buildAddOp(iref, SageBuilder::buildIntVal(offset)); - } - } -} - -void MMPrefetchInsertion::initialize(const std::string& arrName, int hint) { - this->arrName = std::string(arrName); - this->cacheHint = hint; - this->indecies = std::vector<std::string*>(); - this->offsets = std::vector<int>(); - this->indexCount = 0; -} -void MMPrefetchInsertion::addDim(int offset) { - this->offsets.push_back(offset); - this->indecies.push_back(NULL); - this->indexCount++; -} -void MMPrefetchInsertion::addDim(int offset, const std::string& indexer) { - this->offsets.push_back(offset); - this->indecies.push_back(new std::string(indexer)); - this->indexCount++; -} -} |