diff options
| -rw-r--r-- | gcc/ChangeLog | 24 | ||||
| -rw-r--r-- | gcc/graphite.c | 188 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 13 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/block-0.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/block-1.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/block-2.c | 1 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/block-3.c | 25 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/block-4.c | 3 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/graphite/pr38498.c | 19 | ||||
| -rw-r--r-- | gcc/tree-chrec.c | 61 | ||||
| -rw-r--r-- | gcc/tree-chrec.h | 1 |
11 files changed, 280 insertions, 59 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 96013c1335d..b379b1ba709 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,27 @@ +2009-01-07 Jan Sjodin <jan.sjodin@amd.com> + + PR tree-optimization/38492 + PR tree-optimization/38498 + * tree-check.c (operator_is_linear, scev_is_linear_expression): New. + * tree-chrec.h (scev_is_linear_expression): Declared. + * graphite.c (graphite_cannot_represent_loop_niter): New. + (scopdet_basic_block_info): Call graphite_cannot_represent_loop_niter. + (graphite_loop_normal_form): Use gcc_assert. + (scan_tree_for_params): Use CASE_CONVERT. + (phi_node_is_iv, bb_contains_non_iv_scalar_phi_nodes): New. + (build_scop_conditions_1): Call bb_contains_non_iv_scalar_phi_nodes. + Use gcc_assert. Discard scops that contain unhandled cases. + (build_scop_conditions): Return a boolean status for unhandled cases. + (strip_mine_profitable_p): Print the loop number, not its depth. + (is_interchange_valid): Pass the depth of the loop nest, don't + recompute it wrongly. + (graphite_trans_bb_block): Same. + (graphite_trans_bb_block): Print tentative of loop blocking. + (graphite_trans_scop_block): Do not print that the loop has been + blocked. + (graphite_transform_loops): Do not handle scops that contain condition + scalar phi nodes. + 2009-01-07 H.J. Lu <hongjiu.lu@intel.com> AVX Programming Reference (December, 2008) diff --git a/gcc/graphite.c b/gcc/graphite.c index b03e0619c5b..645def2b8a7 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -1579,6 +1579,17 @@ move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target) VEC_free (sd_region, heap, *source); } +/* Return true when it is not possible to represent the upper bound of + LOOP in the polyhedral representation. */ + +static bool +graphite_cannot_represent_loop_niter (loop_p loop) +{ + tree niter = number_of_latch_executions (loop); + + return chrec_contains_undetermined (niter) + || !scev_is_linear_expression (niter); +} /* Store information needed by scopdet_* functions. */ struct scopdet_info @@ -1650,8 +1661,7 @@ scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops, if (result.last->loop_father != loop) result.next = NULL; - if (TREE_CODE (number_of_latch_executions (loop)) - == SCEV_NOT_KNOWN) + if (graphite_cannot_represent_loop_niter (loop)) result.difficult = true; if (sinfo.difficult) @@ -2350,9 +2360,7 @@ graphite_loop_normal_form (loop_p loop) gimple_seq stmts; edge exit = single_dom_exit (loop); - if (!number_of_iterations_exit (loop, exit, &niter, false)) - gcc_unreachable (); - + gcc_assert (number_of_iterations_exit (loop, exit, &niter, false)); nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true, NULL_TREE); if (stmts) @@ -2732,8 +2740,7 @@ scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k, } break; - case NOP_EXPR: - case CONVERT_EXPR: + CASE_CONVERT: case NON_LVALUE_EXPR: scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract); break; @@ -3278,13 +3285,63 @@ add_conditions_to_domain (graphite_bb_p gb) } } -/* Helper recursive function. */ +/* Returns true when PHI defines an induction variable in the loop + containing the PHI node. */ -static void +static bool +phi_node_is_iv (gimple phi) +{ + loop_p loop = gimple_bb (phi)->loop_father; + tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi)); + + return tree_contains_chrecs (scev, NULL); +} + +/* Returns true when BB contains scalar phi nodes that are not an + induction variable of a loop. */ + +static bool +bb_contains_non_iv_scalar_phi_nodes (basic_block bb) +{ + gimple phi = NULL; + gimple_stmt_iterator si; + + for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) + if (is_gimple_reg (gimple_phi_result (gsi_stmt (si)))) + { + /* Store the unique scalar PHI node: at this point, loops + should be in cannonical form, so we expect to see at most + one scalar phi node in the loop header. */ + if (phi + || bb != bb->loop_father->header) + return true; + + phi = gsi_stmt (si); + } + + if (!phi + || phi_node_is_iv (phi)) + return false; + + return true; +} + +/* Helper recursive function. Record in CONDITIONS and CASES all + conditions from 'if's and 'switch'es occurring in BB from SCOP. + + Returns false when the conditions contain scalar computations that + depend on the condition, i.e. when there are scalar phi nodes on + the junction after the condition. Only the computations occurring + on memory can be handled in the polyhedral model: operations that + define scalar evolutions in conditions, that can potentially be + used to index memory, can't be handled by the polyhedral model. */ + +static bool build_scop_conditions_1 (VEC (gimple, heap) **conditions, VEC (gimple, heap) **cases, basic_block bb, scop_p scop) { + bool res = true; int i, j; graphite_bb_p gbb; gimple_stmt_iterator gsi; @@ -3293,9 +3350,11 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions, /* Make sure we are in the SCoP. */ if (!bb_in_scop_p (bb, scop)) - return; + return true; + + if (bb_contains_non_iv_scalar_phi_nodes (bb)) + return false; - /* Record conditions in graphite_bb. */ gbb = gbb_from_bb (bb); if (gbb) { @@ -3331,13 +3390,18 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions, /* Recursively scan the then or else part. */ if (e->flags & EDGE_TRUE_VALUE) VEC_safe_push (gimple, heap, *cases, stmt); - else if (e->flags & EDGE_FALSE_VALUE) - VEC_safe_push (gimple, heap, *cases, NULL); - else - gcc_unreachable (); + else + { + gcc_assert (e->flags & EDGE_FALSE_VALUE); + VEC_safe_push (gimple, heap, *cases, NULL); + } VEC_safe_push (gimple, heap, *conditions, stmt); - build_scop_conditions_1 (conditions, cases, e->dest, scop); + if (!build_scop_conditions_1 (conditions, cases, e->dest, scop)) + { + res = false; + goto done; + } VEC_pop (gimple, *conditions); VEC_pop (gimple, *cases); } @@ -3358,43 +3422,45 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions, bb_child = label_to_block (CASE_LABEL (gimple_switch_label (stmt, i))); - /* Do not handle multiple values for the same block. */ for (k = 0; k < n; k++) if (i != k && label_to_block (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child) break; - if (k != n) - continue; - - /* Switch cases with more than one predecessor are not - handled. */ - if (VEC_length (edge, bb_child->preds) != 1) - continue; + /* Switches with multiple case values for the same + block are not handled. */ + if (k != n + /* Switch cases with more than one predecessor are + not handled. */ + || VEC_length (edge, bb_child->preds) != 1) + { + res = false; + goto done; + } /* Recursively scan the corresponding 'case' block. */ - for (gsi_search_gimple_label = gsi_start_bb (bb_child); !gsi_end_p (gsi_search_gimple_label); gsi_next (&gsi_search_gimple_label)) { - gimple stmt_gimple_label - = gsi_stmt (gsi_search_gimple_label); + gimple label = gsi_stmt (gsi_search_gimple_label); - if (gimple_code (stmt_gimple_label) == GIMPLE_LABEL) + if (gimple_code (label) == GIMPLE_LABEL) { - tree t = gimple_label_label (stmt_gimple_label); + tree t = gimple_label_label (label); - if (t == gimple_switch_label (stmt, i)) - VEC_replace (gimple, *cases, n_cases, - stmt_gimple_label); - else - gcc_unreachable (); + gcc_assert (t == gimple_switch_label (stmt, i)); + VEC_replace (gimple, *cases, n_cases, label); + break; } } - build_scop_conditions_1 (conditions, cases, bb_child, scop); + if (!build_scop_conditions_1 (conditions, cases, bb_child, scop)) + { + res = false; + goto done; + } /* Remove the scanned block from the dominator successors. */ for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++) @@ -3402,13 +3468,14 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions, { VEC_unordered_remove (basic_block, dom, j); break; - } + } } VEC_pop (gimple, *conditions); VEC_pop (gimple, *cases); break; } + default: break; } @@ -3416,23 +3483,38 @@ build_scop_conditions_1 (VEC (gimple, heap) **conditions, /* Scan all immediate dominated successors. */ for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++) - build_scop_conditions_1 (conditions, cases, bb_child, scop); + if (!build_scop_conditions_1 (conditions, cases, bb_child, scop)) + { + res = false; + goto done; + } + done: VEC_free (basic_block, heap, dom); + return res; } -/* Record all 'if' and 'switch' conditions in each gbb of SCOP. */ +/* Record all conditions from SCOP. -static void + Returns false when the conditions contain scalar computations that + depend on the condition, i.e. when there are scalar phi nodes on + the junction after the condition. Only the computations occurring + on memory can be handled in the polyhedral model: operations that + define scalar evolutions in conditions, that can potentially be + used to index memory, can't be handled by the polyhedral model. */ + +static bool build_scop_conditions (scop_p scop) { + bool res; VEC (gimple, heap) *conditions = NULL; VEC (gimple, heap) *cases = NULL; - build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop); + res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop); VEC_free (gimple, heap, conditions); VEC_free (gimple, heap, cases); + return res; } /* Build the current domain matrix: the loops belonging to the current @@ -4064,18 +4146,17 @@ expand_scalar_variables_expr (tree type, tree op0, enum tree_code code, expand_scalar_variables_stmt (def_stmt, bb, scop, old_loop_father, map); return get_new_name_from_old_name (map, op0); - } else { if (gimple_code (def_stmt) != GIMPLE_ASSIGN || !bb_in_scop_p (gimple_bb (def_stmt), scop)) return get_new_name_from_old_name (map, op0); - + var0 = gimple_assign_rhs1 (def_stmt); subcode = gimple_assign_rhs_code (def_stmt); var1 = gimple_assign_rhs2 (def_stmt); - + return expand_scalar_variables_expr (type, var0, subcode, var1, bb, scop, old_loop_father, map); } @@ -4100,7 +4181,7 @@ expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop, { tree use = USE_FROM_PTR (use_p); tree type = TREE_TYPE (use); - enum tree_code code = TREE_CODE (use); + enum tree_code code = TREE_CODE (use); tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb, scop, old_loop_father, map); if (use_expr != use) @@ -5607,7 +5688,7 @@ strip_mine_profitable_p (graphite_bb_p gb, int stride, if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:", - loop_index); + loop->num); fprintf (dump_file, "number of iterations is too low.\n"); } } @@ -5616,17 +5697,16 @@ strip_mine_profitable_p (graphite_bb_p gb, int stride, } /* Determines when the interchange of LOOP_A and LOOP_B belonging to - SCOP is legal. */ + SCOP is legal. DEPTH is the number of loops around. */ static bool -is_interchange_valid (scop_p scop, int loop_a, int loop_b) +is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth) { bool res; VEC (ddr_p, heap) *dependence_relations; VEC (data_reference_p, heap) *datarefs; struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a); - int depth = perfect_loop_nest_depth (nest); lambda_trans_matrix trans; gcc_assert (loop_a < loop_b); @@ -5692,7 +5772,7 @@ graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops) for (i = start ; i < nb_loops; i++) for (j = i + 1; j < nb_loops; j++) - if (!is_interchange_valid (scop, i, j)) + if (!is_interchange_valid (scop, i, j, nb_loops)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, @@ -5716,6 +5796,10 @@ graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops) for (i = 1; i < nb_loops - start; i++) graphite_trans_bb_move_loop (gb, start + 2 * i, start + i); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n", + GBB_BB (gb)->index); + return true; } @@ -5858,9 +5942,6 @@ graphite_trans_scop_block (scop_p scop) transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j); VEC_free (graphite_bb_p, heap, bbs); - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\nLoop blocked.\n"); - return transform_done; } @@ -5978,7 +6059,8 @@ graphite_transform_loops (void) build_scop_canonical_schedules (scop); build_bb_loops (scop); - build_scop_conditions (scop); + if (!build_scop_conditions (scop)) + continue; find_scop_parameters (scop); build_scop_context (scop); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 125ae6192ee..4055cfcbcae 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,16 @@ +2009-01-07 Jan Sjodin <jan.sjodin@amd.com> + + PR tree-optimization/38492 + PR tree-optimization/38498 + * testsuite/gcc.dg/graphite/pr38500.c: Fixed warning as committed + in trunk. + * testsuite/gcc.dg/graphite/block-0.c: Update test. + * testsuite/gcc.dg/graphite/block-1.c: Same. + * testsuite/gcc.dg/graphite/block-2.c: Remove xfail and test for blocking. + * testsuite/gcc.dg/graphite/block-4.c: Remove test for strip mine. + * testsuite/gcc.dg/graphite/block-3.c: New. + * testsuite/gcc.dg/graphite/pr38498.c: New. + 2009-01-07 H.J. Lu <hongjiu.lu@intel.com> AVX Programming Reference (December, 2008) diff --git a/gcc/testsuite/gcc.dg/graphite/block-0.c b/gcc/testsuite/gcc.dg/graphite/block-0.c index f277f05fb06..627f044fc14 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-0.c +++ b/gcc/testsuite/gcc.dg/graphite/block-0.c @@ -21,5 +21,5 @@ main() return toto(); } -/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite"} } */ +/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite"} } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-1.c b/gcc/testsuite/gcc.dg/graphite/block-1.c index 857f8d54e8e..0a70e9e10a4 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-1.c +++ b/gcc/testsuite/gcc.dg/graphite/block-1.c @@ -36,5 +36,5 @@ int main() return sum; } -/* { dg-final { scan-tree-dump-times "Loop blocked" 2 "graphite"} } */ +/* { dg-final { scan-tree-dump-times "will be loop blocked" 2 "graphite"} } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-2.c b/gcc/testsuite/gcc.dg/graphite/block-2.c index cf0969bac1d..fc4e889e791 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-2.c +++ b/gcc/testsuite/gcc.dg/graphite/block-2.c @@ -28,5 +28,4 @@ void fallbackSort ( UInt32* fmap, } AssertH ( j < 256, 1005 ); } -/* { dg-final { scan-tree-dump-times "Loop blocked" 1 "graphite" { xfail *-*-* }} } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-3.c b/gcc/testsuite/gcc.dg/graphite/block-3.c new file mode 100644 index 00000000000..369df2fec7e --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/block-3.c @@ -0,0 +1,25 @@ +/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */ + +#define N 24 +#define M 1000 + +float A[1000][1000][1000], B[1000][1000], C[1000][1000]; + +void test (void) +{ + int i, j, k; + + /* These loops contain too few iterations for being strip-mined by 64. */ + for (i = 0; i < 24; i++) + for (j = 0; j < 24; j++) + for (k = 0; k < 24; k++) + A[i][j][k] = B[i][k] * C[k][j]; + + /* These loops should still be strip mined. */ + for (i = 0; i < 1000; i++) + for (j = 0; j < 1000; j++) + for (k = 0; k < 1000; k++) + A[i][j][k] = B[i][k] * C[k][j]; +} + +/* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-4.c b/gcc/testsuite/gcc.dg/graphite/block-4.c index 4b550b4e472..e3649f01d2d 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-4.c +++ b/gcc/testsuite/gcc.dg/graphite/block-4.c @@ -9,18 +9,15 @@ void test (void) { int i, j, k; - /* These loops contain too few iterations for being strip-mined by 64. */ for (i = 0; i < 24; i++) for (j = 0; j < 24; j++) for (k = 0; k < 24; k++) A[i][j] = B[i][k] * C[k][j]; - /* These loops should still be strip mined. */ for (i = 0; i < 1000; i++) for (j = 0; j < 1000; j++) for (k = 0; k < 1000; k++) A[i][j] = B[i][k] * C[k][j]; } -/* { dg-final { scan-tree-dump-times "Strip Mining is not profitable" 2 "graphite" } } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/pr38498.c b/gcc/testsuite/gcc.dg/graphite/pr38498.c new file mode 100644 index 00000000000..c79bbad554d --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/pr38498.c @@ -0,0 +1,19 @@ +/* { dg-options "-O2 -floop-block" } */ + +double test_vector (float **data, int rows, int cols, int vqrows,double epsilon, int maxiter,int **mean, int *map) +{ + int i, j, r, it; + double sqerr, prev_sqerr=0, t; + unsigned int *sel; + int *count; + for (it = 0;; it++) + { + if ((sqerr == 0.0) || (it >= maxiter-1) ||((it > 0) && ( ((prev_sqerr - sqerr) / prev_sqerr) < epsilon )) ) + for (i = 0; i < vqrows; i++) + { + for (j = 0; j < cols; j++) + mean[i][j] = 0.0; + count[i] = 0; + } + } +} diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index 26ae9b408a7..7a065b6b8b0 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -1430,3 +1430,64 @@ for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data) } } +/* Returns true when the operation can be part of a linear + expression. */ + +static inline bool +operator_is_linear (tree scev) +{ + switch (TREE_CODE (scev)) + { + case INTEGER_CST: + case POLYNOMIAL_CHREC: + case PLUS_EXPR: + case POINTER_PLUS_EXPR: + case MULT_EXPR: + case MINUS_EXPR: + case NEGATE_EXPR: + case SSA_NAME: + case NON_LVALUE_EXPR: + CASE_CONVERT: + return true; + + default: + return false; + } +} + +/* Return true when SCEV is a linear expression. Linear expressions + can contain additions, substractions and multiplications. + Multiplications are restricted to constant scaling: "cst * x". */ + +bool +scev_is_linear_expression (tree scev) +{ + if (scev == NULL + || !operator_is_linear (scev)) + return false; + + if (TREE_CODE (scev) == MULT_EXPR) + return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL) + && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL)); + + switch (TREE_CODE_LENGTH (TREE_CODE (scev))) + { + case 3: + return scev_is_linear_expression (TREE_OPERAND (scev, 0)) + && scev_is_linear_expression (TREE_OPERAND (scev, 1)) + && scev_is_linear_expression (TREE_OPERAND (scev, 2)); + + case 2: + return scev_is_linear_expression (TREE_OPERAND (scev, 0)) + && scev_is_linear_expression (TREE_OPERAND (scev, 1)); + + case 1: + return scev_is_linear_expression (TREE_OPERAND (scev, 0)); + + case 0: + return true; + + default: + return false; + } +} diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h index d35dcd3064c..fa372a2450b 100644 --- a/gcc/tree-chrec.h +++ b/gcc/tree-chrec.h @@ -84,6 +84,7 @@ extern bool evolution_function_is_affine_multivariate_p (const_tree, int); extern bool evolution_function_is_univariate_p (const_tree); extern unsigned nb_vars_in_chrec (tree); extern bool evolution_function_is_invariant_p (tree, int); +extern bool scev_is_linear_expression (tree); /* Determines whether CHREC is equal to zero. */ |