doc

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