summaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/dep.hh19
-rw-r--r--include/ir_code.hh124
-rw-r--r--include/irtools.hh57
-rw-r--r--include/loop.hh109
4 files changed, 207 insertions, 102 deletions
diff --git a/include/dep.hh b/include/dep.hh
index ffd2db5..035d382 100644
--- a/include/dep.hh
+++ b/include/dep.hh
@@ -6,6 +6,19 @@
#include "ir_code.hh"
#include "chill_error.hh"
+/*!
+ * \file
+ * \brief Data dependence vector and graph.
+ *
+ * All dependence vectors are normalized, i.e., the first non-zero distance
+ * must be positve. Thus the correct dependence meaning can be given based on
+ * source/destination pair's read/write type. Suppose for a dependence vector
+ * 1, 0~5, -3), we want to permute the first and the second dimension,
+ * the result would be two dependence vectors (0, 1, -3) and (1~5, 1, -3).
+ * All operations on dependence vectors are non-destructive, i.e., new
+ * dependence vectors are returned.
+ */
+
enum DependenceType {
DEP_W2R, DEP_R2W, DEP_W2W, DEP_R2R, DEP_CONTROL, DEP_UNKNOWN
};
@@ -21,8 +34,8 @@ struct DependenceVector {
bool from_same_stmt; // Manu
bool is_reduction_cand; // Manu
- bool is_reduction; // used to identify a class of flow dependence
- // that can be broken
+ bool is_reduction; //!< used to identify a class of flow dependencies that can be broken
+
std::vector<omega::coef_t> lbounds;
std::vector<omega::coef_t> ubounds;
@@ -54,7 +67,7 @@ struct DependenceVector {
bool has_been_carried_before(int dim) const;
- // the following functions will be cleaned up or removed later
+ // TODO the following functions will be cleaned up or removed later
bool isZero() const;
bool isPositive() const;
diff --git a/include/ir_code.hh b/include/ir_code.hh
index 8de0f01..b56ce41 100644
--- a/include/ir_code.hh
+++ b/include/ir_code.hh
@@ -23,40 +23,48 @@
#define IR_CODE_HH
#include <ir_enums.hh>
-
#include <chillAST/chillASTs.hh>
-
#include <vector>
-
-// needed for omega::coef_t below
-#include <basic/util.h> // in omega ... why is this not in CG_output*.h?
-
#include <code_gen/CG_outputRepr.h>
#include <code_gen/CG_outputBuilder.h>
+/*!
+ * \file
+ * \brief CHiLL's compiler intermediate representation interface that extends Omega's builder interface to accomodate compiler analyses and extra code generation.
+ *
+ * Unlike CG_outputRepr, IR_Symbol,IR_Ref and IR_Control are place holders
+ * to the underlying code, thus deleting or duplicating them does not affect
+ * the actual code. Similar to Omega builder's memory allocation strategy,
+ * all non-const pointer parameters of CG_outputRepr/IR_Symbol/IR_Ref/IR_Control
+ * are destroyed after the call.
+ */
class IR_Code; // forward declaration
-
-// Base abstract class for scalar and array symbols. This is a place
-// holder for related declaration in IR code.
+/*!
+ * @brief Base abstract class for scalar and array symbols.
+ *
+ * This is a place holder for related declaration in IR code.
+ */
struct IR_Symbol {
const IR_Code *ir_;
- virtual ~IR_Symbol() {/* ir_ is not the responsibility of this object */}
+ //! ir_ is not the responsibility of this object
+ virtual ~IR_Symbol() { }
- virtual int n_dim() const = 0; // IR_Symbol
+ virtual int n_dim() const = 0;
virtual std::string name() const = 0;
virtual bool operator==(const IR_Symbol &that) const = 0;
virtual bool operator!=(const IR_Symbol &that) const { return !(*this == that); }
- virtual IR_Symbol *clone() const = 0; /* shallow copy */
+ //! shallow copy
+ virtual IR_Symbol *clone() const = 0;
- virtual bool isScalar() const { return false; } // default
- virtual bool isArray() const { return false; } // default
- virtual bool isPointer() const { return false; } // default
+ virtual bool isScalar() const { return false; }
+ virtual bool isArray() const { return false; }
+ virtual bool isPointer() const { return false; }
//IR_SYMBOL_TYPE symtype; // base type: int, float, double, struct, .... typedef'd something
//IR_SYMBOL_TYPE getDatatype() ;
@@ -87,7 +95,6 @@ struct IR_ArraySymbol : public IR_Symbol {
bool isArray() const { return true; }
};
-
struct IR_PointerSymbol : public IR_Symbol {
virtual ~IR_PointerSymbol() {}
@@ -100,14 +107,18 @@ struct IR_PointerSymbol : public IR_Symbol {
bool isPointer() const { return true; }
};
-// Base abstract class for scalar and array references. This is a
-// place holder for related code in IR code.
+
+/*!
+ * @brief Base abstract class for scalar and array references.
+ *
+ * This is a place holder for related code in IR code.
+ */
struct IR_Ref {
const IR_Code *ir_;
+ //! ir_ is not the responsibility of this object
+ virtual ~IR_Ref() { }
- virtual ~IR_Ref() {/* ir_ is not the responsibility of this object */}
-
- virtual int n_dim() const = 0; // IR_Ref
+ virtual int n_dim() const = 0;
virtual bool is_write() const = 0;
virtual std::string name() const = 0;
@@ -118,7 +129,8 @@ struct IR_Ref {
virtual omega::CG_outputRepr *convert() = 0;
- virtual IR_Ref *clone() const = 0; /* shallow copy */
+ //! shallow copy
+ virtual IR_Ref *clone() const = 0;
virtual void Dump() const {
fprintf(stderr, "some IR_*Ref needs to implement Dump()\n");
int *i = 0;
@@ -236,15 +248,17 @@ struct IR_PointerArrayRef : public IR_Ref {
struct IR_Block;
-// Base abstract class for code structures. This is a place holder
-// for the actual structure in the IR code. However, in cases that
-// original source code may be transformed during loop initialization
-// such as converting a while loop to a for loop or reconstructing the
-// loop from low level IR code, the helper loop class (NOT
-// IMPLEMENTED) must contain the transformed code that needs to be
-// freed when out of service.
+//! Base abstract class for code structures.
+/*!
+ * This is a place holder for the actual structure in the IR code.
+ * However, in cases that original source code may be transformed during
+ * loop initialization such as converting a while loop to a for loop or
+ * reconstructing the loop from low level IR code, the helper loop class (NOT
+ * IMPLEMENTED) must contain the transformed code that needs to be
+ * freed when out of service.
+ */
struct IR_Control {
- const IR_Code *ir_; // hate this
+ const IR_Code *ir_;
virtual ~IR_Control() {/* ir_ is not the responsibility of this object */}
@@ -306,16 +320,14 @@ struct IR_While : public IR_Control {
};
-// Abstract class for compiler IR.
// TODO made a lot of definition to pass instantiation for IR_clangCode
+//! Abstract class for compiler IR.
class IR_Code {
protected:
- // the only data members in IR_Code are Omega classes
- omega::CG_outputBuilder *ocg_; // Omega Code Gen
+ omega::CG_outputBuilder *ocg_;
omega::CG_outputRepr *init_code_;
omega::CG_outputRepr *cleanup_code_;
- // OK, I lied
static int ir_pointer_counter;
static int ir_array_counter;
@@ -338,8 +350,7 @@ public:
return ir_array_counter - 1;
}
- // if all flavors of ir_code use chillAST internally ...
- chillAST_FunctionDecl *func_defn; // the function we're modifying
+ chillAST_FunctionDecl *func_defn; //!< the function we're modifying
chillAST_FunctionDecl *GetChillFuncDefinition() { return func_defn; };
IR_Code() {
@@ -355,8 +366,11 @@ public:
omega::CG_outputRepr *init_code() { return init_code_; }
- // memory_type is for differentiating the location of where the new memory is allocated.
- // this is useful for processors with heterogeneous memory hierarchy.
+ /*!
+ * \param memory_type is for differentiating the location of
+ * where the new memory is allocated. this is useful for
+ * processors with heterogeneous memory hierarchy.
+ */
virtual IR_ScalarSymbol *CreateScalarSymbol(const IR_Symbol *sym, int memory_type) = 0;
virtual IR_ScalarSymbol *CreateScalarSymbol(IR_CONSTANT_TYPE type, int memory_type, std::string name = "") {
@@ -441,11 +455,15 @@ public:
CHILL_ERROR("NOT IMPLEMENTED\n");
return NULL;
}
-
- // Array references should be returned in their accessing order.
- // e.g. s1: A[i] = A[i-1]
- // s2: B[C[i]] = D[i] + E[i]
- // return A[i-1], A[i], D[i], E[i], C[i], B[C[i]] in this order.
+ /*!
+ * Array references should be returned in their accessing order.
+ *
+ * ~~~
+ * e.g. s1: A[i] = A[i-1]
+ * s2: B[C[i]] = D[i] + E[i]
+ * return A[i-1], A[i], D[i], E[i], C[i], B[C[i]] in this order.
+ * ~~~
+ */
virtual std::vector<IR_ArrayRef *> FindArrayRef(const omega::CG_outputRepr *repr) const = 0;
virtual std::vector<IR_PointerArrayRef *> FindPointerArrayRef(const omega::CG_outputRepr *repr) const {
@@ -461,13 +479,15 @@ public:
CHILL_ERROR("NOT IMPLEMENTED\n");
return false;
}
-
- // If there is no sub structure interesting inside the block, return empty,
- // so we know when to stop looking inside.
+ /*!
+ * If there is no sub structure interesting inside the block, return empty,
+ * so we know when to stop looking inside.
+ */
virtual std::vector<IR_Control *> FindOneLevelControlStructure(const IR_Block *block) const = 0;
-
- // All controls must be in the same block, at the same level and in
- // contiguous lexical order as appeared in parameter vector.
+ /*!
+ * All controls must be in the same block, at the same level and in
+ * contiguous lexical order as appeared in parameter vector.
+ */
virtual IR_Block *MergeNeighboringControlStructures(const std::vector<IR_Control *> &controls) const = 0;
virtual IR_Block *GetCode() const = 0;
@@ -552,11 +572,7 @@ public:
return NULL;
}
- //void Dump() { ocg_->Dump(); };
- //---------------------------------------------------------------------------
- // CC Omega code builder interface here
-
- //---------------------------------------------------------------------------
+ //! Codegen Omega code builder interface
omega::CG_outputBuilder *builder() const { return ocg_; }
};
diff --git a/include/irtools.hh b/include/irtools.hh
index c4a78ed..66b3144 100644
--- a/include/irtools.hh
+++ b/include/irtools.hh
@@ -9,15 +9,23 @@
#define DEP_DEBUG 0
-// IR tree is used to initialize a loop. For a loop node, payload is
-// its mapped iteration space dimension. For a simple block node,
-// payload is its mapped statement number. Normal if-else is split
-// into two nodes where the one with odd payload represents then-part and
-// the one with even payload represents else-part.
+/*!
+ * \file
+ * \brief Useful tools to analyze code in compiler IR format.
+ */
+
+//! It is used to initialize a loop.
struct ir_tree_node {
IR_Control *content;
ir_tree_node *parent;
std::vector<ir_tree_node *> children;
+ /*!
+ * * For a loop node, payload is its mapped iteration space dimension.
+ * * For a simple block node, payload is its mapped statement number.
+ * * Normal if-else is splitted into two nodes
+ * * the one with odd payload represents then-part and
+ * * the one with even payload represents else-part.
+ */
int payload;
~ir_tree_node() {
@@ -26,16 +34,49 @@ struct ir_tree_node {
delete content;
}
};
-
+/*!
+ * @brief Build IR tree from the source code
+ *
+ * Block type node can only be leaf, i.e., there is no further stuctures inside a block allowed
+ *
+ * @param control
+ * @param parent
+ * @return
+ */
std::vector<ir_tree_node *> build_ir_tree(IR_Control *control,
ir_tree_node *parent = NULL);
-
+/*!
+ * @brief Extract statements from IR tree
+ *
+ * Statements returned are ordered in lexical order in the source code
+ *
+ * @param ir_tree
+ * @return
+ */
std::vector<ir_tree_node *> extract_ir_stmts(
const std::vector<ir_tree_node *> &ir_tree);
bool is_dependence_valid(ir_tree_node *src_node, ir_tree_node *dst_node,
const DependenceVector &dv, bool before);
-
+/*!
+ * @brief test data dependeces between two statements
+ *
+ * The first statement in parameter must be lexically before the second statement in parameter.
+ * Returned dependences are all lexicographically positive
+ *
+ * @param ir
+ * @param repr1
+ * @param IS1
+ * @param repr2
+ * @param IS2
+ * @param freevar
+ * @param index
+ * @param i
+ * @param j
+ * @param uninterpreted_symbols
+ * @param uninterpreted_symbols_stringrepr
+ * @return
+ */
std::pair<std::vector<DependenceVector>, std::vector<DependenceVector> > test_data_dependences(
IR_Code *ir, const omega::CG_outputRepr *repr1,
const omega::Relation &IS1, const omega::CG_outputRepr *repr2,
diff --git a/include/loop.hh b/include/loop.hh
index 554b005..7c746f6 100644
--- a/include/loop.hh
+++ b/include/loop.hh
@@ -15,24 +15,44 @@
#include "stencil.hh"
+/*!
+ * \file
+ * \brief Core loop transformation functionality.
+ *
+ * "level" (starting from 1) means loop level and it corresponds to "dim"
+ * (starting from 0) in transformed iteration space [c_1,l_1,c_2,l_2,....,
+ * c_n,l_n,c_(n+1)], e.g., l_2 is loop level 2 in generated code, dim 3
+ * in transformed iteration space, and variable 4 in Omega relation.
+ * All c's are constant numbers only and they will not show up as actual loops.
+ *
+ * Formula:
+ *
+ * ~~~
+ * dim = 2*level - 1
+ * var = dim + 1
+ * ~~~
+ */
class IR_Code;
enum TilingMethodType { StridedTile, CountedTile };
enum LoopLevelType { LoopLevelOriginal, LoopLevelTile, LoopLevelUnknown };
-
-// Describes properties of each loop level of a statement. "payload"
-// for LoopLevelOriginal means iteration space dimension, for
-// LoopLevelTile means tiled loop level. Special value -1 for
-// LoopLevelTile means purely derived loop. For dependence dimension
-// payloads, the values must be in an increasing order.
-// "parallel_level" will be used by code generation to support
-// multi-level parallelization (default 0 means sequential loop under
-// the current parallelization level).
+//! Describes properties of each loop level of a statement.
struct LoopLevel {
LoopLevelType type;
- int payload;
+ /*!
+ * For LoopLevelOriginal means iteration space dimension
+ * For LoopLevelTile means tiled loop level. Special value -1 for
+ * LoopLevelTile means purely derived loop. For dependence dimension
+ * payloads, the values must be in an increasing order.
+ */
+ int payload;
+ /*!
+ * Used by code generation to support
+ * multi-level parallelization (default 0 means sequential loop under
+ * the current parallelization level).
+ */
int parallel_level;
bool segreducible;
std::string segment_descriptor;
@@ -46,14 +66,15 @@ struct Statement {
std::vector<LoopLevel> loop_level;
ir_tree_node *ir_stmt_node;
bool has_inspector;
- int reduction; // Manu:: 0 == reduction not possible, 1 == reduction possible, 2 == reduction with some processing
+ /*!
+ * @brief Whether reduction is possible
+ *
+ * 0 == reduction not possible, 1 == reduction possible, 2 == reduction with some processing
+ */
+ int reduction;
IR_OPERATION_TYPE reductionOp; // Manu
class stencilInfo *statementStencil;
-
- //protonu--temporarily putting this back here
- //omega::Tuple<int> nonSplitLevels;
- //end--protonu.
};
@@ -118,7 +139,6 @@ public:
~Loop();
omega::CG_outputRepr *getCode(int effort = 1) const; // TODO was 1
- //chillAST_Node* getCode(int effort, std::set<int> stmts) const;
void stencilASEPadded(int stmt_num);
@@ -133,15 +153,12 @@ public:
void dump() const;
std::vector<std::set <int > > sort_by_same_loops(std::set<int > active, int level);
- //
- // legacy unimodular transformations for perfectly nested loops
- // e.g. M*(i,j)^T = (i',j')^T or M*(i,j,1)^T = (i',j')^T
- //
+ //! legacy unimodular transformations for perfectly nested loops
+ /*!
+ * e.g. \f$M*(i,j)^T = (i',j')^T or M*(i,j,1)^T = (i',j')^T\f$
+ */
bool nonsingular(const std::vector<std::vector<int> > &M);
- //
- // high-level loop transformations
- //
void permute(const std::set<int> &active, const std::vector<int> &pi);
void permute(int stmt_num, int level, const std::vector<int> &pi);
void permute(const std::vector<int> &pi);
@@ -150,14 +167,43 @@ public:
void tile(int stmt_num, int level, int tile_size, int outer_level = 1, TilingMethodType method = StridedTile, int alignment_offset = 0, int alignment_multiple = 1);
std::set<int> split(int stmt_num, int level, const omega::Relation &cond);
std::set<int> unroll(int stmt_num, int level, int unroll_amount, std::vector< std::vector<std::string> >idxNames= std::vector< std::vector<std::string> >(), int cleanup_split_level = 0);
-
+
+ //! Datacopy function by reffering arrays by numbers
+ /*!
+ * for example
+ * ~~~
+ * A[i] = A[i-1] + B[i];
+ * ~~~
+ * parameter array_ref_num=[0,2] means to copy data touched by A[i-1] and A[i]
+ *
+ * @param array_ref_nums
+ * @param level
+ * @param allow_extra_read
+ * @param fastest_changing_dimension
+ * @param padding_stride
+ * @param padding_alignment
+ * @param memory_type
+ * @return
+ */
bool datacopy(const std::vector<std::pair<int, std::vector<int> > > &array_ref_nums, int level, bool allow_extra_read = false, int fastest_changing_dimension = -1, int padding_stride = 1, int padding_alignment = 4, int memory_type = 0);
+ //! Datacopy function by reffering arrays by name
+ /*!
+ * parameter array_name=A means to copy data touched by A[i-1] and A[i]
+ * @param stmt_num
+ * @param level
+ * @param array_name
+ * @param allow_extra_read
+ * @param fastest_changing_dimension
+ * @param padding_stride
+ * @param padding_alignment
+ * @param memory_type
+ * @return
+ */
bool datacopy(int stmt_num, int level, const std::string &array_name, bool allow_extra_read = false, int fastest_changing_dimension = -1, int padding_stride = 1, int padding_alignment = 4, int memory_type = 0);
bool datacopy_privatized(int stmt_num, int level, const std::string &array_name, const std::vector<int> &privatized_levels, bool allow_extra_read = false, int fastest_changing_dimension = -1, int padding_stride = 1, int padding_alignment = 1, int memory_type = 0);
bool datacopy_privatized(const std::vector<std::pair<int, std::vector<int> > > &array_ref_nums, int level, const std::vector<int> &privatized_levels, bool allow_extra_read = false, int fastest_changing_dimension = -1, int padding_stride = 1, int padding_alignment = 1, int memory_type = 0);
bool datacopy_privatized(const std::vector<std::pair<int, std::vector<IR_ArrayRef *> > > &stmt_refs, int level, const std::vector<int> &privatized_levels, bool allow_extra_read, int fastest_changing_dimension, int padding_stride, int padding_alignment, int memory_type = 0);
- //std::set<int> scalar_replacement_inner(int stmt_num);
- bool find_stencil_shape( int stmt_num );
+ bool find_stencil_shape( int stmt_num );
Graph<std::set<int>, bool> construct_induced_graph_at_level(std::vector<std::set<int> > s, DependenceGraph dep, int dep_dim);
@@ -170,9 +216,6 @@ public:
void scale(const std::set<int> &stmt_nums, int level, int scale_amount);
void reverse(const std::set<int> &stmt_nums, int level);
void peel(int stmt_num, int level, int peel_amount = 1);
- //
- // more fancy loop transformations
- //
void modular_shift(int stmt_num, int level, int shift_amount) {}
void diagonal_map(int stmt_num, const std::pair<int, int> &levels, int offset) {}
void modular_partition(int stmt_num, int level, int stride) {}
@@ -183,9 +226,6 @@ public:
- //
- // derived loop transformations
- //
void shift_to(int stmt_num, int level, int absolute_position);
std::set<int> unroll_extra(int stmt_num, int level, int unroll_amount, int cleanup_split_level = 0);
bool is_dependence_valid_based_on_lex_order(int i, int j,
@@ -193,7 +233,6 @@ public:
void split_with_alignment(int stmt_num, int level, int alignment,
int direction=0);
- // Manu:: reduction operation
void reduce(int stmt_num, std::vector<int> &level, int param, std::string func_name, std::vector<int> &seq_levels, std::vector<int> cudaized_levels = std::vector<int>(), int bound_level = -1);
void scalar_expand(int stmt_num, const std::vector<int> &levels, std::string arrName, int memory_type =0, int padding_alignment=0, int assign_then_accumulate = 1, int padding_stride = 0);
void ELLify(int stmt_num, std::vector<std::string> arrays_to_pad, int pad_to, bool dense_pad = false, std::string dense_pad_pos_array = "");
@@ -203,11 +242,7 @@ public:
void set_array_size(std::string name, int size );
omega::CG_outputRepr * iegen_parser(std::string &str, std::vector<std::string> &index_names);
- //
- // other public operations
- //
void pragma(int stmt_num, int level, const std::string &pragmaText);
void prefetch(int stmt_num, int level, const std::string &arrName, int hint);
- //void prefetch(int stmt_num, int level, const std::string &arrName, const std::string &indexName, int offset, int hint);
};
#endif
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2025-02-02 00:35:50 +0000