/* Gimple Represented as Polyhedra.
- Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
+ Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
This file is part of GCC.
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
+#ifndef GCC_GRAPHITE_H
+#define GCC_GRAPHITE_H
+
#include "tree-data-ref.h"
+int ref_nb_loops (data_reference_p);
+
typedef struct graphite_bb *graphite_bb_p;
DEF_VEC_P(graphite_bb_p);
DEF_VEC_ALLOC_P (graphite_bb_p, heap);
static inline unsigned scop_nb_params (scop_p scop);
static inline bool scop_contains_loop (scop_p scop, struct loop *loop);
-struct graphite_bb
+typedef struct graphite_bb
{
basic_block bb;
scop_p scop;
CloogMatrix *domain;
/* Lists containing the restrictions of the conditional statements
- dominating this bb. This bb can only be executed, if all conditions
+ dominating this bb. This bb can only be executed, if all conditions
are true.
Example:
B
}
- So for B there is a additional condition (2i <= 8).
+ So for B there is an additional condition (2i <= 8).
- TODO: Add this restrictions to the domain matrix.
+ TODO: Add these restrictions to the domain matrix.
- List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
- corresponding element in CONDITION_CASES is not NULL_TREE. For a
- SWITCH_EXPR the corresponding element in CONDITION_CASES is a
+ List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
+ corresponding element in CONDITION_CASES is not NULL_TREE. For a
+ SWITCH_EXPR the corresponding element in CONDITION_CASES is a
CASE_LABEL_EXPR. */
VEC (gimple, heap) *conditions;
VEC (gimple, heap) *condition_cases;
lambda_vector compressed_alpha_matrix;
CloogMatrix *dynamic_schedule;
VEC (data_reference_p, heap) *data_refs;
-};
+ htab_t cloog_iv_types;
+} *gbb_p;
#define GBB_BB(GBB) GBB->bb
#define GBB_SCOP(GBB) GBB->scop
#define GBB_CONDITIONS(GBB) GBB->conditions
#define GBB_CONDITION_CASES(GBB) GBB->condition_cases
#define GBB_LOOPS(GBB) GBB->loops
+#define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
/* Return the loop that contains the basic block GBB. */
return GBB_BB (gbb)->loop_father;
}
+int nb_loops_around_gb (graphite_bb_p);
+
/* Calculate the number of loops around GB in the current SCOP. Only
works if GBB_DOMAIN is built. */
return VEC_index (loop_p, GBB_LOOPS (gb), index);
}
-/* Returns the corresponding loop iterator index for a gimple loop. */
+/* Returns the index of LOOP in the loop nest around GB. */
static inline int
gbb_loop_index (graphite_bb_p gb, loop_p loop)
CloogLoop *cloog_loop;
};
-typedef struct name_tree
+typedef struct name_tree_d
{
tree t;
const char *name;
/* A Single Entry, Single Exit region is a part of the CFG delimited
by two edges. */
-typedef struct sese
+typedef struct sese_d
{
+ /* Single ENTRY and single EXIT from the SESE region. */
edge entry, exit;
+
+ /* REGION_BASIC_BLOCKS contains the set of all the basic blocks
+ belonging to the SESE region. */
+ struct pointer_set_t *region_basic_blocks;
+
+ /* An SSA_NAME version is flagged in the LIVEOUT bitmap if the
+ SSA_NAME is defined inside and used outside the SESE region. */
+ bitmap liveout;
+
+ /* The overall number of SSA_NAME versions used to index LIVEIN. */
+ int num_ver;
+
+ /* For each SSA_NAME version VER in LIVEOUT, LIVEIN[VER] contains
+ the set of basic blocks indices that contain a use of VER. */
+ bitmap *livein;
} *sese;
#define SESE_ENTRY(S) (S->entry)
#define SESE_EXIT(S) (S->exit)
+#define SESE_REGION_BBS(S) (S->region_basic_blocks)
+#define SESE_LIVEOUT(S) (S->liveout)
+#define SESE_LIVEIN(S) (S->livein)
+#define SESE_LIVEIN_VER(S, I) (S->livein[I])
+#define SESE_NUM_VER(S) (S->num_ver)
+
+extern sese new_sese (edge, edge);
+extern void free_sese (sese);
+extern void sese_build_livein_liveouts (sese);
/* A SCOP is a Static Control Part of the program, simple enough to be
represented in polyhedral form. */
/* A SCOP is defined as a SESE region. */
sese region;
- /* All the basic blocks in this scop. They have extra information
- attached to them, in the graphite_bb structure. */
+ /* All the basic blocks in this scop that contain memory references
+ and that will be represented as statements in the polyhedral
+ representation. */
VEC (graphite_bb_p, heap) *bbs;
- /* Set for a basic block index when it belongs to this SCOP. */
- bitmap bbs_b;
-
lambda_vector static_schedule;
/* Parameters used within the SCOP. */
/* ??? It looks like a global mapping loop_id -> cloog_loop would work. */
htab_t loop2cloog_loop;
- /* CLooG representation of this SCOP. */
+ /* Cloog representation of this scop. */
CloogProgram *program;
+
+ /* Are we allowed to add more params? This is for debugging purpose. We
+ can only add new params before generating the bb domains, otherwise they
+ become invalid. */
+ bool add_params;
+
+ /* LIVEOUT_RENAMES registers the rename mapping that has to be
+ applied after code generation. */
+ htab_t liveout_renames;
};
#define SCOP_BBS(S) S->bbs
-#define SCOP_BBS_B(S) S->bbs_b
#define SCOP_REGION(S) S->region
/* SCOP_ENTRY bb dominates all the bbs of the scop. SCOP_EXIT bb
post-dominates all the bbs of the scop. SCOP_EXIT potentially
but just a boundary. SCOP_ENTRY is considered part of the scop. */
#define SCOP_ENTRY(S) (SESE_ENTRY (SCOP_REGION (S))->dest)
#define SCOP_EXIT(S) (SESE_EXIT (SCOP_REGION (S))->dest)
+#define SCOP_REGION_BBS(S) (SESE_REGION_BBS (SCOP_REGION (S)))
#define SCOP_STATIC_SCHEDULE(S) S->static_schedule
#define SCOP_LOOPS(S) S->loops
#define SCOP_LOOP_NEST(S) S->loop_nest
+#define SCOP_ADD_PARAMS(S) S->add_params
#define SCOP_PARAMS(S) S->params
#define SCOP_OLDIVS(S) S->old_ivs
#define SCOP_PROG(S) S->program
#define SCOP_LOOP2CLOOG_LOOP(S) S->loop2cloog_loop
#define SCOP_LOOPS_MAPPING(S) S->loops_mapping
+#define SCOP_LIVEOUT_RENAMES(S) S->liveout_renames
extern void debug_scop (scop_p, int);
extern void debug_scops (int);
extern void dot_scop (scop_p);
extern void dot_all_scops (void);
extern void debug_clast_stmt (struct clast_stmt *);
-
-
-extern void debug_loop_vec (graphite_bb_p gb);
+extern void debug_rename_map (htab_t);
+extern void debug_ivtype_map (htab_t);
+extern void debug_loop_vec (graphite_bb_p);
extern void debug_oldivs (scop_p);
/* Describes the type of an iv stack entry. */
typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack;
extern void debug_loop_iv_stack (loop_iv_stack);
+/* Return the old induction variable of the LOOP that is in normal
+ form in SCOP. */
+
+static inline tree
+oldiv_for_loop (scop_p scop, loop_p loop)
+{
+ int i;
+ name_tree iv;
+
+ if (!loop)
+ return NULL_TREE;
+
+ for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
+ if (iv->loop == loop)
+ return iv->t;
+
+ return NULL_TREE;
+}
/* Return the number of gimple loops contained in SCOP. */
return cloog_domain_dim (cloog_loop_domain (slot->cloog_loop)) + 2;
}
-/* Returns the dimensionality of an enclosing loop iteration domain
- with respect to enclosing SCoP for a given data reference REF. */
-
-static inline int
-ref_nb_loops (data_reference_p ref)
-{
- return loop_domain_dim (loop_containing_stmt (DR_STMT (ref))->num, DR_SCOP (ref));
-}
-
/* Returns the dimensionality of a loop iteration vector in a loop
iteration domain for a given loop (identified by LOOP_NUM) with
respect to SCOP. */
return depth;
}
-/* Associate a POLYHEDRON dependence description to two data
- references A and B. */
-struct data_dependence_polyhedron
-{
- struct data_reference *a;
- struct data_reference *b;
- bool reversed_p;
- bool loop_carried; /*TODO:konrad get rid of this, make level signed */
- signed level;
- CloogDomain *polyhedron;
-};
-
-#define RDGE_DDP(E) ((struct data_dependence_polyhedron*) ((E)->data))
-
-typedef struct data_dependence_polyhedron *ddp_p;
-
-DEF_VEC_P(ddp_p);
-DEF_VEC_ALLOC_P(ddp_p,heap);
-
+#endif /* GCC_GRAPHITE_H */