/* A data reference can write or read some memory or we
just know it may write some memory. */
-enum POLY_DR_TYPE
+enum poly_dr_type
{
PDR_READ,
- /* PDR_MAY_READs are represented using PDR_READS. This does not limit the
- expressiveness. */
+ /* PDR_MAY_READs are represented using PDR_READS. This does not
+ limit the expressiveness. */
PDR_WRITE,
PDR_MAY_WRITE
};
struct poly_dr
{
+ /* An identifier for this PDR. */
+ int id;
+
+ /* The number of data refs identical to this one in the PBB. */
+ int nb_refs;
+
/* A pointer to compiler's data reference description. */
void *compiler_dr;
/* A pointer to the PBB that contains this data reference. */
poly_bb_p pbb;
- enum POLY_DR_TYPE type;
+ enum poly_dr_type type;
/* The access polyhedron contains the polyhedral space this data
reference will access.
The polyhedron contains these dimensions:
- - The alias set (a):
- Every memory access is classified in at least one alias set.
+ - The alias set (a):
+ Every memory access is classified in at least one alias set.
- - The subscripts (s_0, ..., s_n):
- The memory is accessed using zero or more subscript dimensions.
+ - The subscripts (s_0, ..., s_n):
+ The memory is accessed using zero or more subscript dimensions.
- - The iteration domain (variables and parameters)
+ - The iteration domain (variables and parameters)
Do not hardcode the dimensions. Use the following accessor functions:
- pdr_alias_set_dim
| p = A;
| ... = p[?][?];
| for j
- | A[i][j+b] = m;
+ | A[i][j+k] = m;
| }
The data access A[i][j+k] in alias set "5" is described like this:
- | i j k a s0 s1 1
+ | i j k a s0 s1 1
| 0 0 0 1 0 0 -5 = 0
|-1 0 0 0 1 0 0 = 0
| 0 -1 -1 0 0 1 0 = 0
-
- The constraints on the data container A[1335][123] are:
-
- | i j k a s0 s1 1
- | 0 0 0 0 1 0 0 >= 0
- | 0 0 0 0 0 1 0 >= 0
+ | 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
+ | 0 0 0 0 0 1 0 >= 0 # array size.
| 0 0 0 0 -1 0 1335 >= 0
| 0 0 0 0 0 -1 123 >= 0
polyhedron:
- | i k a s0 1
+ | i k a s0 1
| 0 0 1 0 -5 = 0
| 0 0 0 1 0 >= 0
"or"
- | i k a s0 1
+ | i k a s0 1
| 0 0 1 0 -7 = 0
| 0 0 0 1 0 >= 0
| i j k a 1
| 0 0 0 -1 15 = 0 */
ppl_Pointset_Powerset_C_Polyhedron_t accesses;
- ppl_Pointset_Powerset_C_Polyhedron_t data_container;
+
+ /* Data reference's base object set number, we must assure 2 pdrs are in the
+ same base object set before dependency checking. */
+ int dr_base_object_set;
+
+ /* The number of subscripts. */
+ graphite_dim_t nb_subscripts;
};
+#define PDR_ID(PDR) (PDR->id)
+#define PDR_NB_REFS(PDR) (PDR->nb_refs)
#define PDR_CDR(PDR) (PDR->compiler_dr)
#define PDR_PBB(PDR) (PDR->pbb)
#define PDR_TYPE(PDR) (PDR->type)
#define PDR_ACCESSES(PDR) (PDR->accesses)
-#define PDR_DATA_CONTAINER(PDR) (PDR->data_container)
+#define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set)
+#define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
-void new_poly_dr (poly_bb_p, ppl_Pointset_Powerset_C_Polyhedron_t,
- ppl_Pointset_Powerset_C_Polyhedron_t,
- enum POLY_DR_TYPE, void *);
+void new_poly_dr (poly_bb_p, int, ppl_Pointset_Powerset_C_Polyhedron_t,
+ enum poly_dr_type, void *, graphite_dim_t);
void free_poly_dr (poly_dr_p);
void debug_pdr (poly_dr_p);
void print_pdr (FILE *, poly_dr_p);
static inline scop_p pdr_scop (poly_dr_p pdr);
-/* The number of subscripts of the PDR. */
+/* The dimension of the PDR_ACCESSES polyhedron of PDR. */
-static inline graphite_dim_t
-pdr_nb_subscripts (poly_dr_p pdr)
+static inline ppl_dimension_type
+pdr_dim (poly_dr_p pdr)
{
- poly_bb_p pbb = PDR_PBB (pdr);
ppl_dimension_type dim;
-
ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr),
&dim);
- return dim - pbb_dim_iter_domain (pbb) - pbb_nb_params (pbb) - 1;
+ return dim;
}
/* The dimension of the iteration domain of the scop of PDR. */
return scop_nb_params (pdr_scop (pdr));
}
-/* The dimension of the accesses polyhedron of PDR. */
-
-static inline graphite_dim_t
-pdr_dim (poly_dr_p pdr)
-{
- graphite_dim_t alias_nb_dimensions = 1;
-
- return pbb_dim_iter_domain (PDR_PBB (pdr)) + alias_nb_dimensions
- + pdr_nb_subscripts (pdr) + scop_nb_params (pdr_scop (pdr));
-}
-
/* The dimension of the alias set in PDR. */
static inline ppl_dimension_type
return pbb_dim_iter_domain (pbb) + param;
}
+/* Returns true when PDR is a "read". */
+
+static inline bool
+pdr_read_p (poly_dr_p pdr)
+{
+ return PDR_TYPE (pdr) == PDR_READ;
+}
+
+/* Returns true when PDR is a "write". */
+
+static inline bool
+pdr_write_p (poly_dr_p pdr)
+{
+ return PDR_TYPE (pdr) == PDR_WRITE;
+}
+
+/* Returns true when PDR is a "may write". */
+
+static inline bool
+pdr_may_write_p (poly_dr_p pdr)
+{
+ return PDR_TYPE (pdr) == PDR_MAY_WRITE;
+}
+
+/* Return true when PDR1 and PDR2 are similar data accesses: they have
+ the same base array, and the same access functions. */
+
+static inline bool
+same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2)
+{
+ return PDR_TYPE (pdr1) == PDR_TYPE (pdr2)
+ && PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
+ && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2);
+}
+
typedef struct poly_scattering *poly_scattering_p;
struct poly_scattering
/* A copy of the transformed scattering. */
poly_scattering_p saved;
+
+ /* True when the PDR duplicates have already been removed. */
+ bool pdr_duplicates_removed;
+
+ /* True when this PBB contains only a reduction statement. */
+ bool is_reduction;
};
#define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
#define PBB_SAVED(PBB) (PBB->saved)
#define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
#define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
+#define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed)
+#define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
-extern void new_poly_bb (scop_p, void *);
+extern void new_poly_bb (scop_p, void *, bool);
extern void free_poly_bb (poly_bb_p);
extern void debug_loop_vec (poly_bb_p);
extern void schedule_to_scattering (poly_bb_p, int);
extern bool scop_do_interchange (scop_p);
extern bool scop_do_strip_mine (scop_p);
extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, Value);
+extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, Value);
+extern void pbb_remove_duplicate_pdrs (poly_bb_p);
+
+/* Return the number of write data references in PBB. */
+
+static inline int
+number_of_write_pdrs (poly_bb_p pbb)
+{
+ int res = 0;
+ int i;
+ poly_dr_p pdr;
+
+ for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
+ if (PDR_TYPE (pdr) == PDR_WRITE)
+ res++;
+
+ return res;
+}
+
+/* The index of the PBB. */
+
+static inline int
+pbb_index (poly_bb_p pbb)
+{
+ return GBB_BB (PBB_BLACK_BOX (pbb))->index;
+}
+
+/* The loop of the PBB. */
+
+static inline loop_p
+pbb_loop (poly_bb_p pbb)
+{
+ return gbb_loop (PBB_BLACK_BOX (pbb));
+}
/* The scop that contains the PDR. */
-static inline scop_p pdr_scop (poly_dr_p pdr)
+static inline scop_p
+pdr_scop (poly_dr_p pdr)
{
return PBB_SCOP (PDR_PBB (pdr));
}
return PBB_NB_SCATTERING_TRANSFORM (pbb);
}
+/* The number of dynamic scattering dimensions in PBB. */
+
+static inline graphite_dim_t
+pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb)
+{
+ /* This function requires the 2d + 1 scattering format to be
+ invariant during all transformations. */
+ gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2);
+ return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2;
+}
+
/* Returns the number of local variables used in the transformed
scattering polyhedron of PBB. */
+ pbb_dim_iter_domain (pbb);
}
+/* The scattering dimension of PBB corresponding to the dynamic level
+ LEVEL. */
+
+static inline ppl_dimension_type
+psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level)
+{
+ graphite_dim_t result;
+ result = 1 + 2 * level;
+
+ gcc_assert (result < pbb_nb_scattering_transform (pbb));
+ return result;
+}
+
/* Adds to the transformed scattering polyhedron of PBB a new local
variable and returns its index. */
PBB_NB_SCATTERING_TRANSFORM (pbb) += 1;
}
+typedef struct lst *lst_p;
+DEF_VEC_P(lst_p);
+DEF_VEC_ALLOC_P (lst_p, heap);
+
+/* Loops and Statements Tree. */
+struct lst {
+
+ /* LOOP_P is true when an LST node is a loop. */
+ bool loop_p;
+
+ /* A pointer to the loop that contains this node. */
+ lst_p loop_father;
+
+ /* Loop nodes contain a sequence SEQ of LST nodes, statements
+ contain a pointer to their polyhedral representation PBB. */
+ union {
+ poly_bb_p pbb;
+ VEC (lst_p, heap) *seq;
+ } node;
+};
+
+#define LST_LOOP_P(LST) ((LST)->loop_p)
+#define LST_LOOP_FATHER(LST) ((LST)->loop_father)
+#define LST_PBB(LST) ((LST)->node.pbb)
+#define LST_SEQ(LST) ((LST)->node.seq)
+
+void scop_to_lst (scop_p);
+void print_lst (FILE *, lst_p, int);
+void debug_lst (lst_p);
+void dot_lst (lst_p);
+
+/* Creates a new LST loop with SEQ. */
+
+static inline lst_p
+new_lst_loop (VEC (lst_p, heap) *seq)
+{
+ lst_p lst = XNEW (struct lst);
+ int i;
+ lst_p l;
+
+ LST_LOOP_P (lst) = true;
+ LST_SEQ (lst) = seq;
+ LST_LOOP_FATHER (lst) = NULL;
+
+ for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
+ LST_LOOP_FATHER (l) = lst;
+
+ return lst;
+}
+
+/* Creates a new LST statement with PBB. */
+
+static inline lst_p
+new_lst_stmt (poly_bb_p pbb)
+{
+ lst_p lst = XNEW (struct lst);
+
+ LST_LOOP_P (lst) = false;
+ LST_PBB (lst) = pbb;
+ LST_LOOP_FATHER (lst) = NULL;
+ return lst;
+}
+
+/* Returns a copy of LST. */
+
+static inline lst_p
+copy_lst (lst_p lst)
+{
+ if (!lst)
+ return NULL;
+
+ if (LST_LOOP_P (lst))
+ {
+ int i;
+ lst_p l;
+ VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
+
+ for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
+ VEC_safe_push (lst_p, heap, seq, copy_lst (l));
+
+ return new_lst_loop (seq);
+ }
+
+ return new_lst_stmt (LST_PBB (lst));
+}
+
+/* Returns the loop depth of LST. */
+
+static inline int
+lst_depth (lst_p lst)
+{
+ if (!lst)
+ return -1;
+
+ return lst_depth (LST_LOOP_FATHER (lst)) + 1;
+}
+
+/* Returns the Dewey number for LST. */
+
+static inline int
+lst_dewey_number (lst_p lst)
+{
+ int i;
+ lst_p l;
+
+ if (!lst)
+ return -1;
+
+ if (!LST_LOOP_FATHER (lst))
+ return 0;
+
+ for (i = 0; VEC_iterate (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l); i++)
+ if (l == lst)
+ return i;
+
+ return -1;
+}
+
+/* Return the LST node corresponding to PBB. */
+
+static inline lst_p
+lst_find_pbb (lst_p lst, poly_bb_p pbb)
+{
+ int i;
+ lst_p l;
+
+ if (!lst)
+ return NULL;
+
+ if (LST_LOOP_P (lst))
+ for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
+ {
+ lst_p res = lst_find_pbb (l, pbb);
+ if (res)
+ return res;
+ }
+ else if (pbb == LST_PBB (lst))
+ return lst;
+
+ return NULL;
+}
+
+/* Return the LST node corresponding to the loop around STMT at depth
+ LOOP_DEPTH. */
+
+static inline lst_p
+find_lst_loop (lst_p stmt, int loop_depth)
+{
+ lst_p loop = LST_LOOP_FATHER (stmt);
+
+ gcc_assert (loop_depth >= 0);
+
+ while (loop_depth < lst_depth (loop))
+ loop = LST_LOOP_FATHER (loop);
+
+ return loop;
+}
+
+
/* A SCOP is a Static Control Part of the program, simple enough to be
represented in polyhedral form. */
struct scop
representation. */
VEC (poly_bb_p, heap) *bbs;
- /* Data dependence graph for this SCoP. */
- struct graph *dep_graph;
+ /* Original and transformed schedules. */
+ lst_p original_schedule, transformed_schedule;
/* The context describes known restrictions concerning the parameters
and relations in between the parameters.
c = 2a + b */
ppl_Pointset_Powerset_C_Polyhedron_t context;
- /* A hashtable of the original pairs of dependent data references.
- For each pair of dependent data references, the dependence
- polyhedron is stored also. */
- htab_t original_pdr_pairs;
+ /* A hashtable of the data dependence relations for the original
+ scattering. */
+ htab_t original_pddrs;
};
#define SCOP_BBS(S) (S->bbs)
#define SCOP_REGION(S) ((sese) S->region)
-#define SCOP_DEP_GRAPH(S) (S->dep_graph)
#define SCOP_CONTEXT(S) (S->context)
-#define SCOP_ORIGINAL_PDR_PAIRS(S) (S->original_pdr_pairs)
+#define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
+#define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
+#define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
extern scop_p new_scop (void *);
extern void free_scop (scop_p);
OSDN Git Service
