New implementation of Graphite.

2009-07-30  Sebastian Pop  <sebastian.pop@amd.com>

	* Makefile.in (OBJS-common): Added dependence on graphite-blocking.o,
	graphite-clast-to-gimple.o, graphite-dependences.o,
	graphite-interchange.o, graphite-poly.o, graphite-ppl.o,
	graphite-scop-detection.o, graphite-sese-to-poly.o, and sese.o.
	(graphite-blocking.o,
	graphite-clast-to-gimple.o, graphite-dependences.o,
	graphite-interchange.o, graphite-poly.o, graphite-ppl.o,
	graphite-scop-detection.o, graphite-sese-to-poly.o, and sese.o): New.
	* cfgloop.c (alloc_loop): Set loop->can_be_parallel to false.
	* cfgloop.h (struct loop): Add can_be_parallel field.
	* common.opt (fgraphite-identity): Moved up.
	(fgraphite-force-parallel): New flag.
	* graphite.c: Rewrite.
	* graphite.h: Rewrite.
	* passes.c (init_optimization_passes): Schedule a pass of DCE and LIM
	after Graphite.
	* toplev.c (graphite_out_file): New file descriptor.
	(graphite_in_file): New.
	(process_options): flag_graphite_force_parallel cannot be used without
	Graphite.
	* tree-ssa-loop.c: Include toplev.h.
	(gate_graphite_transforms): Enable flag_graphite for
	flag_graphite_force_parallel.

From-SVN: r150301

1 files changed, 0 insertions, 552 deletions

diff --git a/gcc/graphite.h b/gcc/graphite.h
index e663c2d0fe5..1007e9af410 100644
--- a/gcc/graphite.h
+++ b/gcc/graphite.h
@@ -21,556 +21,4 @@ along with GCC; see the file COPYING3.  If not see
 #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);
-
-DEF_VEC_P(scop_p);
-DEF_VEC_ALLOC_P (scop_p, heap);
-
-static inline int scop_nb_loops (scop_p scop);
-static inline unsigned scop_nb_params (scop_p scop);
-static inline bool scop_contains_loop (scop_p scop, struct loop *loop);
-
-typedef struct graphite_bb
-{
-  basic_block bb;
-  scop_p scop;
-
-  /* The static schedule contains the textual order for every loop layer.
-    
-     Example:
-
-     S0
-     for (i ...)
-       {
-         S1
-         for (j ...)
-           {
-             S2
-             S3
-           }
-         S4
-       }
-     S5
-     for (k ...)
-       {
-         S6
-         S7
-         for (l ...)
-           {
-             S8
-           }
-         S9
-       }
-     S10
-
-     Schedules:
-  
-        | Depth       
-     BB | 0  1  2 
-     ------------
-     S0 | 0
-     S1 | 1, 0
-     S2 | 1, 1, 0
-     S3 | 1, 1, 1
-     S4 | 1, 2
-     S5 | 2
-     S6 | 3, 0
-     S7 | 3, 1
-     S8 | 3, 2, 0
-     S9 | 3, 3
-     S10| 4
-
-   Normalization rules:
-     - One SCoP can never contain two bbs with the same schedule timestamp.
-     - All bbs at the same loop depth have a consecutive ordering (no gaps). */
-  lambda_vector static_schedule;
-
-  /* The iteration domain of this bb. It contains this columns:
-     - In/Eq: If this line is a equation or inequation.
-     - For every loop iterator one column.
-     - One column for every parameter in this SCoP.
-     - The constant column to add integers to the (in)equations.
-
-     Example:
-
-     for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
-       for (j = 2; j <= 2*i + 5; j++)
-         for (k = 0; k <= 5; k++)
-           S (i,j,k)
-
-     Loop iterators: i, j, k 
-     Parameters: a, b
-      
-     (I)eq   i   j   k   a   b   1
-  
-     1       1   0   0  -1   7   -8    #  i >=  a -  7b +  8
-     1      -1   0   0   3   13  20    #  i <= 3a + 13b + 20
-     1       0   1   0   0   0   -2    #  j >= 2
-     1       2  -1   0   0   0    5    #  j <= 2i + 5
-     1       0   0   1   0   0    0    #  k >= 0 
-     1       0   0  -1   0   0    5    #  k <= 5
-
-     The number of loop iterators may change and is not connected to the
-     number of loops, that surrounded this bb in the gimple code. */
-   CloogMatrix *domain;
-
-  /* Lists containing the restrictions of the conditional statements
-     dominating this bb.  This bb can only be executed, if all conditions
-     are true.
- 
-     Example:
- 
-     for (i = 0; i <= 20; i++)
-     {
-       A
- 
-       if (2i <= 8)
-         B
-     }
- 
-     So for B there is an additional condition (2i <= 8).
- 
-     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
-     CASE_LABEL_EXPR.  */
-  VEC (gimple, heap) *conditions;
-  VEC (gimple, heap) *condition_cases;
-
-  /* LOOPS contains for every column in the graphite domain the corresponding
-     gimple loop. If there exists no corresponding gimple loop LOOPS contains
-     NULL. 
-  
-     Example:
-
-     Original code:
-
-     for (i = 0; i <= 20; i++) 
-       for (j = 5; j <= 10; j++)
-         A
-
-     Original domain:
-
-     (I)eq  i  j  1
-     1      1  0  0   # i >= 0
-     1     -1  0  20  # i <= 20
-     1      0  1  0   # j >= 0
-     1      0 -1  10  # j <= 10
-
-     Original loops vector:
-     0         1 
-     Loop i    Loop j
-
-     After some changes (Exchange i and j, strip-mine i):
-     
-     Domain:
-
-     (I)eq  j  ii i  k  1
-     1      0  0  1  0  0   # i >= 0
-     1      0  0 -1  0  20  # i <= 20
-     1      1  0  0  0  0   # j >= 0
-     1     -1  0  0  0  10  # j <= 10
-     1      0 -1  1  0  0   # ii <= i
-     1      0  1 -1  0  1   # ii + 1 >= i 
-     1      0 -1  0  2  0   # ii <= 2k
-     1      0  1  0 -2  0   # ii >= 2k 
-
-     Iterator vector:
-     0        1        2         3
-     Loop j   NULL     Loop i    NULL
-    
-     Means the original loop i is now at column two of the domain and
-     loop j in the original loop nest is now at column 0.  Column 1 and
-     3 are emtpy.  */
-  VEC (loop_p, heap) *loops;
-
-  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_STATIC_SCHEDULE(GBB) GBB->static_schedule
-#define GBB_DATA_REFS(GBB) GBB->data_refs
-#define GBB_ALPHA(GBB) GBB->compressed_alpha_matrix
-#define GBB_DYNAMIC_SCHEDULE(GBB) GBB->dynamic_schedule
-#define GBB_DOMAIN(GBB) GBB->domain
-#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.  */
-
-static inline struct loop *
-gbb_loop (struct graphite_bb *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.  */
-
-static inline int
-gbb_nb_loops (const struct graphite_bb *gb)
-{
-  scop_p scop = GBB_SCOP (gb);
-
-  if (GBB_DOMAIN (gb) == NULL)
-    return 0;
-  
-  return GBB_DOMAIN (gb)->NbColumns - scop_nb_params (scop) - 2;
-}
-
-/* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.  
-   If there is no corresponding gimple loop, we return NULL.  */
-
-static inline loop_p
-gbb_loop_at_index (graphite_bb_p gb, int index)
-{
-  return VEC_index (loop_p, GBB_LOOPS (gb), index);
-}
-
-/* Returns the index of LOOP in the loop nest around GB.  */
-
-static inline int
-gbb_loop_index (graphite_bb_p gb, loop_p loop)
-{
-  int i;
-  loop_p l;
-
-  for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, l); i++)
-    if (loop == l)
-      return i;
-
-  gcc_unreachable();
-}
-
-struct loop_to_cloog_loop_str
-{
-  unsigned int loop_num;
-  unsigned int loop_position; /* The column that represents this loop.  */
-  CloogLoop *cloog_loop;
-};
-
-typedef struct name_tree_d
-{
-  tree t;
-  const char *name;
-  struct loop *loop;
-} *name_tree;
-
-DEF_VEC_P(name_tree);
-DEF_VEC_ALLOC_P (name_tree, heap);
-
-/* A Single Entry, Single Exit region is a part of the CFG delimited
-   by two edges.  */
-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.  */
-struct scop
-{
-  /* A SCOP is defined as a SESE region.  */
-  sese region;
-
-  /* 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;
-
-  lambda_vector static_schedule;
-
-  /* Parameters used within the SCOP.  */
-  VEC (name_tree, heap) *params;
-
-  /* A collection of old induction variables*/ 
-  VEC (name_tree, heap) *old_ivs;
-
-  /* Loops completely contained in the SCOP.  */
-  bitmap loops;
-  VEC (loop_p, heap) *loop_nest;
-
-  /* ???  It looks like a global mapping loop_id -> cloog_loop would work.  */
-  htab_t loop2cloog_loop;
-
-  /* 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_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
-   contains non affine data accesses, side effect statements or
-   difficult constructs, and thus is not considered part of the scop,
-   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 print_graphite_bb (FILE *, graphite_bb_p, int, int);
-extern void debug_gbb (graphite_bb_p, int);
-extern void dot_scop (scop_p);
-extern void dot_all_scops (void);
-extern void debug_clast_stmt (struct clast_stmt *);
-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 enum {
-  iv_stack_entry_unknown = 0,
-  iv_stack_entry_iv,
-  iv_stack_entry_const
-} iv_stack_entry_kind;
-
-/* Data contained in an iv stack entry.  */
-typedef union iv_stack_entry_data_union
-{
-  name_tree iv;
-  tree constant;
-} iv_stack_entry_data;
-
-/* Datatype for loop iv stack entry.  */
-typedef struct iv_stack_entry_struct
-{
-  iv_stack_entry_kind kind;
-  iv_stack_entry_data data;
-} iv_stack_entry;
-
-typedef iv_stack_entry *iv_stack_entry_p;
-
-DEF_VEC_P(iv_stack_entry_p);
-DEF_VEC_ALLOC_P(iv_stack_entry_p,heap);
-
-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.  */
-
-static inline int
-scop_nb_loops (scop_p scop)
-{
-  return VEC_length (loop_p, SCOP_LOOP_NEST (scop));
-}
-
-/* Returns the number of parameters for SCOP.  */
-
-static inline unsigned
-scop_nb_params (scop_p scop)
-{
-  return VEC_length (name_tree, SCOP_PARAMS (scop));
-}
-
-/* Return the dimension of the domains for SCOP.  */
-
-static inline int
-scop_dim_domain (scop_p scop)
-{
-  return scop_nb_loops (scop) + scop_nb_params (scop) + 1;
-}
-
-/* Return the dimension of the domains for GB.  */
-
-static inline int
-gbb_dim_domain (graphite_bb_p gb)
-{
-  return scop_dim_domain (GBB_SCOP (gb));
-}
-
-/* Returns the dimensionality of a loop iteration domain for a given
-   loop, identified by LOOP_NUM, with respect to SCOP.  */
-
-static inline int
-loop_domain_dim (unsigned int loop_num, scop_p scop)
-{
-  struct loop_to_cloog_loop_str tmp, *slot; 
-  htab_t tab = SCOP_LOOP2CLOOG_LOOP (scop);
-
-  tmp.loop_num = loop_num;
-  slot = (struct loop_to_cloog_loop_str *) htab_find (tab, &tmp);
-
-  /* The loop containing the entry of the scop is not always part of
-     the SCoP, and it is not registered in SCOP_LOOP2CLOOG_LOOP.  */
-  if (!slot)
-    return scop_nb_params (scop) + 2;
-
-  return cloog_domain_dim (cloog_loop_domain (slot->cloog_loop)) + 2;
-}
-
-/* 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.  */
-
-static inline int
-loop_iteration_vector_dim (unsigned int loop_num, scop_p scop)
-{
-  return loop_domain_dim (loop_num, scop) - 2 - scop_nb_params (scop);
-}
-
-/* Checks, if SCOP contains LOOP.  */
-
-static inline bool
-scop_contains_loop (scop_p scop, struct loop *loop)
-{
-  return bitmap_bit_p (SCOP_LOOPS (scop), loop->num);
-}
-
-/* Returns the index of LOOP in the domain matrix for the SCOP.  */
-
-static inline int
-scop_loop_index (scop_p scop, struct loop *loop)
-{
-  unsigned i;
-  struct loop *l;
-
-  gcc_assert (scop_contains_loop (scop, loop));
-
-  for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, l); i++)
-    if (l == loop)
-      return i;
-
-  gcc_unreachable();
-}
-
-/* Return the index of innermost loop that contains the basic block
-   GBB.  */
-
-static inline int
-gbb_inner_most_loop_index (scop_p scop, graphite_bb_p gb)
-{
-  return scop_loop_index(scop, gbb_loop (gb));
-}
-
-/* Return the outermost loop that contains the loop LOOP.  The outer
-   loops are searched until a sibling for the outer loop is found.  */
-
-static struct loop *
-outer_most_loop_1 (scop_p scop, struct loop* loop, struct loop* current_outer)
-{
-  return (!scop_contains_loop (scop, loop)) ? current_outer :
-    (loop->next != NULL) ? loop :
-    outer_most_loop_1 (scop, loop_outer (loop), loop);
-}
-
-/* Return the outermost loop that contains the loop LOOP.  */
-
-static struct loop *
-outer_most_loop (scop_p scop, struct loop *loop)
-{
-  return outer_most_loop_1 (scop, loop, NULL);
-}
-
-/* Return the index of the outermost loop that contains the basic
-   block BB.  */
-
-static inline int
-gbb_outer_most_loop_index (scop_p scop, graphite_bb_p gb)
-{
-  return scop_loop_index (scop, outer_most_loop (scop, gbb_loop (gb)));
-}
-
-/* Return the loop depth of LOOP in SCOP.  */
-
-static inline unsigned int
-scop_gimple_loop_depth (scop_p scop, loop_p loop)
-{
-  unsigned int depth = 0;
-
-  loop = loop_outer (loop);
-
-  while (scop_contains_loop (scop, loop))
-    {
-      depth++;
-      loop = loop_outer (loop);
-    }
-
-  return depth;
-}
-
 #endif  /* GCC_GRAPHITE_H  */