@@ -257,11 +257,72 @@ debug_pdr (poly_dr_p pdr, int verbosity)
print_pdr (stderr, pdr, verbosity);
}
-/* Creates a new SCOP containing REGION. */
+/* Store the GRAPHITE representation of BB. */
+
+gimple_poly_bb_p
+new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs)
+{
+ gimple_poly_bb_p gbb;
+
+ gbb = XNEW (struct gimple_poly_bb);
+ bb->aux = gbb;
+ GBB_BB (gbb) = bb;
+ GBB_DATA_REFS (gbb) = drs;
+ GBB_CONDITIONS (gbb).create (0);
+ GBB_CONDITION_CASES (gbb).create (0);
+
+ return gbb;
+}
+
+static void
+free_data_refs_aux (vec<data_reference_p> datarefs)
+{
+ unsigned int i;
+ data_reference_p dr;
+
+ FOR_EACH_VEC_ELT (datarefs, i, dr)
+ if (dr->aux)
+ {
+ base_alias_pair_p bap = (base_alias_pair_p)(dr->aux);
+
+ free (bap->alias_set);
+
+ free (bap);
+ dr->aux = NULL;
+ }
+}
+/* Frees GBB. */
+
+void
+free_gimple_poly_bb (gimple_poly_bb_p gbb)
+{
+ free_data_refs_aux (GBB_DATA_REFS (gbb));
+ free_data_refs (GBB_DATA_REFS (gbb));
+
+ GBB_CONDITIONS (gbb).release ();
+ GBB_CONDITION_CASES (gbb).release ();
+ GBB_BB (gbb)->aux = 0;
+ XDELETE (gbb);
+}
+
+/* Deletes all gimple bbs in SCOP. */
+
+static void
+remove_gbbs_in_scop (scop_p scop)
+{
+ int i;
+ poly_bb_p pbb;
+
+ FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
+ free_gimple_poly_bb (PBB_BLACK_BOX (pbb));
+}
+
+/* Creates a new SCOP containing the region (ENTRY, EXIT). */
scop_p
-new_scop (sese region)
+new_scop (edge entry, edge exit)
{
+ sese region = new_sese (entry, exit);
scop_p scop = XNEW (struct scop);
scop->context = NULL;
@@ -292,6 +353,9 @@ free_scop (scop_p scop)
int i;
poly_bb_p pbb;
+ remove_gbbs_in_scop (scop);
+ free_sese (SCOP_REGION (scop));
+
FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
free_poly_bb (pbb);
@@ -422,9 +422,16 @@ struct scop
#define SCOP_CONTEXT(S) (NULL)
#define POLY_SCOP_P(S) (S->poly_scop_p)
-extern scop_p new_scop (sese);
+typedef struct base_alias_pair
+{
+ int base_obj_set;
+ int *alias_set;
+} *base_alias_pair_p;
+
+extern scop_p new_scop (edge, edge);
extern void free_scop (scop_p);
-extern void free_scops (vec<scop_p> );
+extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>);
+extern void free_gimple_poly_bb (gimple_poly_bb_p);
extern void print_generated_program (FILE *, scop_p);
extern void debug_generated_program (scop_p);
extern int unify_scattering_dimensions (scop_p);
@@ -149,23 +149,6 @@ same_close_phi_node (gphi *p1, gphi *p2)
gimple_phi_arg_def (p2, 0), 0);
}
-/* Store the GRAPHITE representation of BB. */
-
-static gimple_poly_bb_p
-new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs)
-{
- gimple_poly_bb_p gbb;
-
- gbb = XNEW (struct gimple_poly_bb);
- bb->aux = gbb;
- GBB_BB (gbb) = bb;
- GBB_DATA_REFS (gbb) = drs;
- GBB_CONDITIONS (gbb).create (0);
- GBB_CONDITION_CASES (gbb).create (0);
-
- return gbb;
-}
-
/* Compare the depth of two basic_block's P1 and P2. */
static int
@@ -1670,6 +1653,171 @@ scop_detection::nb_pbbs_in_loops (scop_p scop)
return res;
}
+/* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
+ Otherwise returns -1. */
+
+static inline int
+parameter_index_in_region_1 (tree name, sese region)
+{
+ int i;
+ tree p;
+
+ gcc_assert (TREE_CODE (name) == SSA_NAME);
+
+ FOR_EACH_VEC_ELT (SESE_PARAMS (region), i, p)
+ if (p == name)
+ return i;
+
+ return -1;
+}
+
+/* When the parameter NAME is in REGION, returns its index in
+ SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
+ and returns the index of NAME. */
+
+static int
+parameter_index_in_region (tree name, sese region)
+{
+ int i;
+
+ gcc_assert (TREE_CODE (name) == SSA_NAME);
+
+ /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
+ if (TREE_CODE (TREE_TYPE (name)) != INTEGER_TYPE)
+ return -1;
+
+ if (!invariant_in_sese_p_rec (name, region))
+ return -1;
+
+ i = parameter_index_in_region_1 (name, region);
+ if (i != -1)
+ return i;
+
+ gcc_assert (SESE_ADD_PARAMS (region));
+
+ i = SESE_PARAMS (region).length ();
+ SESE_PARAMS (region).safe_push (name);
+ return i;
+}
+
+/* In the context of sese S, scan the expression E and translate it to
+ a linear expression C. When parsing a symbolic multiplication, K
+ represents the constant multiplier of an expression containing
+ parameters. */
+
+static void
+scan_tree_for_params (sese s, tree e)
+{
+ if (e == chrec_dont_know)
+ return;
+
+ switch (TREE_CODE (e))
+ {
+ case POLYNOMIAL_CHREC:
+ scan_tree_for_params (s, CHREC_LEFT (e));
+ break;
+
+ case MULT_EXPR:
+ if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
+ scan_tree_for_params (s, TREE_OPERAND (e, 0));
+ else
+ scan_tree_for_params (s, TREE_OPERAND (e, 1));
+ break;
+
+ case PLUS_EXPR:
+ case POINTER_PLUS_EXPR:
+ case MINUS_EXPR:
+ scan_tree_for_params (s, TREE_OPERAND (e, 0));
+ scan_tree_for_params (s, TREE_OPERAND (e, 1));
+ break;
+
+ case NEGATE_EXPR:
+ case BIT_NOT_EXPR:
+ CASE_CONVERT:
+ case NON_LVALUE_EXPR:
+ scan_tree_for_params (s, TREE_OPERAND (e, 0));
+ break;
+
+ case SSA_NAME:
+ parameter_index_in_region (e, s);
+ break;
+
+ case INTEGER_CST:
+ case ADDR_EXPR:
+ case REAL_CST:
+ case COMPLEX_CST:
+ case VECTOR_CST:
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+}
+
+/* Find parameters with respect to REGION in BB. We are looking in memory
+ access functions, conditions and loop bounds. */
+
+static void
+find_params_in_bb (sese region, gimple_poly_bb_p gbb)
+{
+ int i;
+ unsigned j;
+ data_reference_p dr;
+ gimple *stmt;
+ loop_p loop = GBB_BB (gbb)->loop_father;
+
+ /* Find parameters in the access functions of data references. */
+ FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
+ for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
+ scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
+
+ /* Find parameters in conditional statements. */
+ FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
+ {
+ tree lhs = scalar_evolution_in_region (region, loop,
+ gimple_cond_lhs (stmt));
+ tree rhs = scalar_evolution_in_region (region, loop,
+ gimple_cond_rhs (stmt));
+
+ scan_tree_for_params (region, lhs);
+ scan_tree_for_params (region, rhs);
+ }
+}
+
+/* Record the parameters used in the SCOP. A variable is a parameter
+ in a scop if it does not vary during the execution of that scop. */
+
+static void
+find_scop_parameters (scop_p scop)
+{
+ poly_bb_p pbb;
+ unsigned i;
+ sese region = SCOP_REGION (scop);
+ struct loop *loop;
+ int nbp;
+
+ /* Find the parameters used in the loop bounds. */
+ FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop)
+ {
+ tree nb_iters = number_of_latch_executions (loop);
+
+ if (!chrec_contains_symbols (nb_iters))
+ continue;
+
+ nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
+ scan_tree_for_params (region, nb_iters);
+ }
+
+ /* Find the parameters used in data accesses. */
+ FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
+ find_params_in_bb (region, PBB_BLACK_BOX (pbb));
+
+ nbp = sese_nb_params (region);
+ scop_set_nb_params (scop, nbp);
+ SESE_ADD_PARAMS (region) = false;
+}
+
class sese_dom_walker : public dom_walker
{
public:
@@ -1759,14 +1907,33 @@ build_scops (vec<scop_p> *scops)
sese_l s (0);
FOR_EACH_VEC_ELT (scops_l, i, s)
{
- sese sese_reg = new_sese (s.entry, s.exit);
- scop_p scop = new_scop (sese_reg);
+ scop_p scop = new_scop (s.entry, s.exit);
+ sb.build_scop_bbs (scop);
/* Do not optimize a scop containing only PBBs that do not belong
to any loops. */
if (sb.nb_pbbs_in_loops (scop) == 0)
{
- free_sese (sese_reg);
+ DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
+ free_scop (scop);
+ continue;
+ }
+
+ build_sese_loop_nests (scop->region);
+ /* Record all conditions in REGION. */
+ sese_dom_walker (CDI_DOMINATORS, scop->region).walk
+ (cfun->cfg->x_entry_block_ptr);
+
+ find_scop_parameters (scop);
+ graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
+
+ if (scop_nb_params (scop) > max_dim)
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
+ << scop_nb_params (scop)
+ << " larger than --param graphite-max-nb-scop-params="
+ << max_dim << ".\n");
+
free_scop (scop);
continue;
}
@@ -1774,16 +1941,6 @@ build_scops (vec<scop_p> *scops)
scops->safe_push (scop);
}
- scop_p scop;
- FOR_EACH_VEC_ELT (*scops, i, scop)
- {
- sb.build_scop_bbs (scop);
- sese region = SCOP_REGION (scop);
- build_sese_loop_nests (region);
- /* Record all conditions in REGION. */
- sese_dom_walker (CDI_DOMINATORS, region).walk (cfun->cfg->x_entry_block_ptr);
- }
-
DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
}
@@ -196,84 +196,6 @@ reduction_phi_p (sese region, gphi_iterator *psi)
return true;
}
-/* Store the GRAPHITE representation of BB. */
-
-static gimple_poly_bb_p
-new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs)
-{
- gimple_poly_bb_p gbb;
-
- gbb = XNEW (struct gimple_poly_bb);
- bb->aux = gbb;
- GBB_BB (gbb) = bb;
- GBB_DATA_REFS (gbb) = drs;
- GBB_CONDITIONS (gbb).create (0);
- GBB_CONDITION_CASES (gbb).create (0);
-
- return gbb;
-}
-
-static void
-free_data_refs_aux (vec<data_reference_p> datarefs)
-{
- unsigned int i;
- data_reference_p dr;
-
- FOR_EACH_VEC_ELT (datarefs, i, dr)
- if (dr->aux)
- {
- base_alias_pair_p bap = (base_alias_pair_p)(dr->aux);
-
- free (bap->alias_set);
-
- free (bap);
- dr->aux = NULL;
- }
-}
-/* Frees GBB. */
-
-static void
-free_gimple_poly_bb (gimple_poly_bb_p gbb)
-{
- free_data_refs_aux (GBB_DATA_REFS (gbb));
- free_data_refs (GBB_DATA_REFS (gbb));
-
- GBB_CONDITIONS (gbb).release ();
- GBB_CONDITION_CASES (gbb).release ();
- GBB_BB (gbb)->aux = 0;
- XDELETE (gbb);
-}
-
-/* Deletes all gimple bbs in SCOP. */
-
-static void
-remove_gbbs_in_scop (scop_p scop)
-{
- int i;
- poly_bb_p pbb;
-
- FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
- free_gimple_poly_bb (PBB_BLACK_BOX (pbb));
-}
-
-/* Deletes all scops in SCOPS. */
-
-void
-free_scops (vec<scop_p> scops)
-{
- int i;
- scop_p scop;
-
- FOR_EACH_VEC_ELT (scops, i, scop)
- {
- remove_gbbs_in_scop (scop);
- free_sese (SCOP_REGION (scop));
- free_scop (scop);
- }
-
- scops.release ();
-}
-
/* Return an ISL identifier for the polyhedral basic block PBB. */
static isl_id *
@@ -587,35 +509,6 @@ parameter_index_in_region_1 (tree name, sese region)
return -1;
}
-/* When the parameter NAME is in REGION, returns its index in
- SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
- and returns the index of NAME. */
-
-static int
-parameter_index_in_region (tree name, sese region)
-{
- int i;
-
- gcc_assert (TREE_CODE (name) == SSA_NAME);
-
- /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
- if (TREE_CODE (TREE_TYPE (name)) != INTEGER_TYPE)
- return -1;
-
- if (!invariant_in_sese_p_rec (name, region))
- return -1;
-
- i = parameter_index_in_region_1 (name, region);
- if (i != -1)
- return i;
-
- gcc_assert (SESE_ADD_PARAMS (region));
-
- i = SESE_PARAMS (region).length ();
- SESE_PARAMS (region).safe_push (name);
- return i;
-}
-
/* Extract an affine expression from the tree E in the scop S. */
static isl_pw_aff *
@@ -687,124 +580,6 @@ extract_affine (scop_p s, tree e, __isl_take isl_space *space)
return res;
}
-/* In the context of sese S, scan the expression E and translate it to
- a linear expression C. When parsing a symbolic multiplication, K
- represents the constant multiplier of an expression containing
- parameters. */
-
-static void
-scan_tree_for_params (sese s, tree e)
-{
- if (e == chrec_dont_know)
- return;
-
- switch (TREE_CODE (e))
- {
- case POLYNOMIAL_CHREC:
- scan_tree_for_params (s, CHREC_LEFT (e));
- break;
-
- case MULT_EXPR:
- if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
- scan_tree_for_params (s, TREE_OPERAND (e, 0));
- else
- scan_tree_for_params (s, TREE_OPERAND (e, 1));
- break;
-
- case PLUS_EXPR:
- case POINTER_PLUS_EXPR:
- case MINUS_EXPR:
- scan_tree_for_params (s, TREE_OPERAND (e, 0));
- scan_tree_for_params (s, TREE_OPERAND (e, 1));
- break;
-
- case NEGATE_EXPR:
- case BIT_NOT_EXPR:
- CASE_CONVERT:
- case NON_LVALUE_EXPR:
- scan_tree_for_params (s, TREE_OPERAND (e, 0));
- break;
-
- case SSA_NAME:
- parameter_index_in_region (e, s);
- break;
-
- case INTEGER_CST:
- case ADDR_EXPR:
- case REAL_CST:
- case COMPLEX_CST:
- case VECTOR_CST:
- break;
-
- default:
- gcc_unreachable ();
- break;
- }
-}
-
-/* Find parameters with respect to REGION in BB. We are looking in memory
- access functions, conditions and loop bounds. */
-
-static void
-find_params_in_bb (sese region, gimple_poly_bb_p gbb)
-{
- int i;
- unsigned j;
- data_reference_p dr;
- gimple *stmt;
- loop_p loop = GBB_BB (gbb)->loop_father;
-
- /* Find parameters in the access functions of data references. */
- FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
- for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
- scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
-
- /* Find parameters in conditional statements. */
- FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
- {
- tree lhs = scalar_evolution_in_region (region, loop,
- gimple_cond_lhs (stmt));
- tree rhs = scalar_evolution_in_region (region, loop,
- gimple_cond_rhs (stmt));
-
- scan_tree_for_params (region, lhs);
- scan_tree_for_params (region, rhs);
- }
-}
-
-/* Record the parameters used in the SCOP. A variable is a parameter
- in a scop if it does not vary during the execution of that scop. */
-
-static void
-find_scop_parameters (scop_p scop)
-{
- poly_bb_p pbb;
- unsigned i;
- sese region = SCOP_REGION (scop);
- struct loop *loop;
- int nbp;
-
- /* Find the parameters used in the loop bounds. */
- FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop)
- {
- tree nb_iters = number_of_latch_executions (loop);
-
- if (!chrec_contains_symbols (nb_iters))
- continue;
-
- nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
- scan_tree_for_params (region, nb_iters);
- }
-
- /* Find the parameters used in data accesses. */
- FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
- find_params_in_bb (region, PBB_BLACK_BOX (pbb));
-
- nbp = sese_nb_params (region);
- scop_set_nb_params (scop, nbp);
- SESE_ADD_PARAMS (region) = false;
-}
-
/* Assign dimension for each parameter in SCOP. */
static void
@@ -1057,100 +832,6 @@ add_conditions_to_constraints (scop_p scop)
add_conditions_to_domain (pbb);
}
-/* Returns a COND_EXPR statement when BB has a single predecessor, the
- edge between BB and its predecessor is not a loop exit edge, and
- the last statement of the single predecessor is a COND_EXPR. */
-
-static gcond *
-single_pred_cond_non_loop_exit (basic_block bb)
-{
- if (single_pred_p (bb))
- {
- edge e = single_pred_edge (bb);
- basic_block pred = e->src;
- gimple *stmt;
-
- if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
- return NULL;
-
- stmt = last_stmt (pred);
-
- if (stmt && gimple_code (stmt) == GIMPLE_COND)
- return as_a <gcond *> (stmt);
- }
-
- return NULL;
-}
-
-class sese_dom_walker : public dom_walker
-{
-public:
- sese_dom_walker (cdi_direction, sese);
-
- virtual void before_dom_children (basic_block);
- virtual void after_dom_children (basic_block);
-
-private:
- auto_vec<gimple *, 3> m_conditions, m_cases;
- sese m_region;
-};
-
-sese_dom_walker::sese_dom_walker (cdi_direction direction, sese region)
- : dom_walker (direction), m_region (region)
-{
-}
-
-/* Call-back for dom_walk executed before visiting the dominated
- blocks. */
-
-void
-sese_dom_walker::before_dom_children (basic_block bb)
-{
- gimple_poly_bb_p gbb;
- gcond *stmt;
-
- if (!bb_in_sese_p (bb, m_region))
- return;
-
- stmt = single_pred_cond_non_loop_exit (bb);
-
- if (stmt)
- {
- edge e = single_pred_edge (bb);
-
- m_conditions.safe_push (stmt);
-
- if (e->flags & EDGE_TRUE_VALUE)
- m_cases.safe_push (stmt);
- else
- m_cases.safe_push (NULL);
- }
-
- gbb = gbb_from_bb (bb);
-
- if (gbb)
- {
- GBB_CONDITIONS (gbb) = m_conditions.copy ();
- GBB_CONDITION_CASES (gbb) = m_cases.copy ();
- }
-}
-
-/* Call-back for dom_walk executed after visiting the dominated
- blocks. */
-
-void
-sese_dom_walker::after_dom_children (basic_block bb)
-{
- if (!bb_in_sese_p (bb, m_region))
- return;
-
- if (single_pred_cond_non_loop_exit (bb))
- {
- m_conditions.pop ();
- m_cases.pop ();
- }
-}
-
/* Add constraints on the possible values of parameter P from the type
of P. */
@@ -2338,11 +2019,6 @@ rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
void
build_poly_scop (scop_p scop)
{
- find_scop_parameters (scop);
-
- graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
- if (scop_nb_params (scop) > max_dim)
- return;
set_scop_parameter_dim (scop);
build_scop_iteration_domain (scop);
build_scop_context (scop);
@@ -21,12 +21,6 @@ along with GCC; see the file COPYING3. If not see
#ifndef GCC_GRAPHITE_SESE_TO_POLY_H
#define GCC_GRAPHITE_SESE_TO_POLY_H
-typedef struct base_alias_pair
-{
- int base_obj_set;
- int *alias_set;
-} *base_alias_pair_p;
-
void build_poly_scop (scop_p);
#endif
@@ -278,6 +278,20 @@ graphite_finalize (bool need_cfg_cleanup_p)
print_loops (dump_file, 3);
}
+/* Deletes all scops in SCOPS. */
+
+static void
+free_scops (vec<scop_p> scops)
+{
+ int i;
+ scop_p scop;
+
+ FOR_EACH_VEC_ELT (scops, i, scop)
+ free_scop (scop);
+
+ scops.release ();
+}
+
isl_ctx *the_isl_ctx;
/* Perform a set of linear transforms on the loops of the current
@@ -14,4 +14,5 @@ void sor(int N1, int N2){
#pragma endscop
}
-/* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite" } } */
+/* This requires more than 3 parameters. */
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 0" 1 "graphite" } } */