* [patch][graphite] Rewrite of "out of graphite"
@ 2008-12-03 7:55 Sebastian Pop
2008-12-03 10:23 ` Richard Guenther
0 siblings, 1 reply; 14+ messages in thread
From: Sebastian Pop @ 2008-12-03 7:55 UTC (permalink / raw)
To: GCC Patches, Richard Guenther, Diego Novillo, Daniel Berlin
Cc: Sjodin, Jan, Jagasia, Harsha, Christophe Harle, Tobias Grosser,
Albert Cohen, Konrad Trifunovic
[-- Attachment #1: Type: text/plain, Size: 6641 bytes --]
Hi,
I committed the attached patch to the graphite branch: it fixes all
the problems that were reported against the graphite code generation:
PR middle-end/37852
PR middle-end/37883
PR middle-end/37928
PR middle-end/37980
PR middle-end/38038
PR middle-end/38039
PR middle-end/38073
PR middle-end/38083
PR middle-end/38125
I have reduced all the bugs left in the polyhedron benchmarks: they do
not occur in the code generation part. I separately committed all the
reduced testcases to the graphite branch such that we can address them
more easily. These are the following testcases:
* testsuite/gcc.dg/graphite/pr38084.c: New.
* testsuite/gfortran.dg/graphite/id-1.f90: New.
* testsuite/gfortran.dg/graphite/id-2.f90: New.
* testsuite/gfortran.dg/graphite/id-3.f90: New.
* testsuite/gfortran.dg/graphite/id-4.f90: New.
* testsuite/gfortran.dg/graphite/pr37857.f90: New.
I'm testing the attached patch on amd64-linux. Okay to commit to
trunk without splitting the patch into smaller pieces: all the pieces
are interconnected, and splitting the patch in smaller pieces is
a painful experience already (yes, I have tried).
Thanks,
Sebastian Pop
--
AMD - GNU Tools
2008-12-02 Sebastian Pop <sebastian.pop@amd.com>
Jan Sjodin <jan.sjodin@amd.com>
Harsha Jagasia <harsha.jagasia@amd.com>
PR middle-end/37852
PR middle-end/37883
PR middle-end/37928
PR middle-end/37980
PR middle-end/38038
PR middle-end/38039
PR middle-end/38073
PR middle-end/38083
PR middle-end/38125
* testsuite/gcc.dg/graphite/pr38073.c: New.
* testsuite/gcc.dg/graphite/pr37928.c: New.
* testsuite/gcc.dg/graphite/pr37883.c: New.
* testsuite/gcc.dg/graphite/pr38125.c: New.
* testsuite/gfortran.dg/graphite/pr38083.f90: New.
* testsuite/gfortran.dg/graphite/pr37852.f90: New.
* testsuite/gfortran.dg/graphite/pr37980.f90: New.
* testsuite/gcc.dg/graphite/scop-18.c: Remove reduction, test for
the number of detected scops. Copy exact same test for loop blocking...
* testsuite/gcc.dg/graphite/block-1.c: Fix the number of expected loops
to be blocked as reductions are not handled.
* testsuite/gcc.dg/graphite/block-4.c: ...here. New.
* tree-phinodes.c (remove_phi_nodes): New, extracted from...
* tree-cfg.c (remove_phi_nodes_and_edges_for_unreachable_block): ...here.
* tree-flow.h (remove_phi_nodes, canonicalize_loop_ivs): Declared.
* Makefile.in (graphite.o): Depend on value-prof.h.
(graphite.o-warn): Removed -Wno-error.
* tree-parloops.c (canonicalize_loop_ivs): Allow reduction_list
to be a NULL pointer. Call update_stmt. Return the newly created
cannonical induction variable.
* graphite.h (debug_rename_map): Declared. Fix some comments.
* graphite.c: Reimplement the code generation from graphite to gimple.
Include value-prof.h.
(loop_iv_stack_get_iv): Do not return NULL for constant substitutions.
(get_old_iv_from_ssa_name): Removed.
(graphite_stmt_p): New.
(new_graphite_bb): Test for useful statements before building a
graphite statement for the basic block.
(free_graphite_bb): Do not free GBB_DATA_REFS: this is a bug
in free_data_ref that calls BITMAP_FREE (DR_VOPS (dr)) without
reason.
(recompute_all_dominators, graphite_verify,
nb_reductions_in_loop, graphite_loop_normal_form): New.
(scop_record_loop): Call graphite_loop_normal_form.
(build_scop_loop_nests): Iterate over all the blocks of the
function instead of relying on the incomplete information from
SCOP_BBS. Return the success of the operation.
(find_params_in_bb): Use the data from GBB_DATA_REFS.
(add_bb_domains): Removed.
(build_loop_iteration_domains): Don't call add_bb_domains.
Add the iteration domain only to the basic blocks that have been
translated to graphite.
(build_scop_conditions_1): Add constraints only if the basic
block have been translated to graphite.
(build_scop_data_accesses): Completely disabled until data
dependence is correctly implemented.
(debug_rename_elt, debug_rename_map_1, debug_rename_map): New.
(remove_all_edges_1, remove_all_edges): Removed.
(get_new_name_from_old_name): New.
(graphite_rename_variables_in_stmt): Renamed
rename_variables_in_stmt. Call get_new_name_from_old_name.
Use replace_exp and update_stmt.
(is_old_iv): Renamed is_iv.
(expand_scalar_variables_stmt): Extra parameter for renaming map.
Use replace_exp and update_stmt.
(expand_scalar_variables_expr): Same. Use the map to get the
new names for the renaming of induction variables and for the
renaming of variables after a basic block has been copied.
(expand_scalar_variables): Same.
(graphite_rename_variables): Renamed rename_variables.
(move_phi_nodes): Removed.
(get_false_edge_from_guard_bb): New.
(build_iv_mapping): Do not insert the induction variable of a
loop in the renaming iv map if the basic block does not belong
to that loop.
(register_old_new_names, graphite_copy_stmts_from_block,
copy_bb_and_scalar_dependences): New.
(translate_clast): Heavily reimplemented: copy basic blocks,
do not move them. Finally, in call cleanup_tree_cfg in gloog.
At each translation step call graphite_verify ensuring the
consistency of the SSA, loops and dominators information.
(collect_virtual_phis, find_vdef_for_var_in_bb,
find_vdef_for_var_1, find_vdef_for_var,
patch_phis_for_virtual_defs): Removed huge hack.
(mark_old_loops, remove_dead_loops, skip_phi_defs,
collect_scop_exit_phi_args, patch_scop_exit_phi_args,
gbb_can_be_ignored, scop_remove_ignoreable_gbbs, ): Removed.
(remove_sese_region, ifsese, if_region_entry, if_region_exit,
if_region_get_condition_block, if_region_set_false_region,
create_if_region_on_edge, move_sese_in_condition, bb_in_sese_p,
sese_find_uses_to_rename_use, sese_find_uses_to_rename_bb,
sese_add_exit_phis_edge, sese_add_exit_phis_var,
rewrite_into_sese_closed_ssa): New.
(gloog): Remove dead code. Early return if code cannot be
generated. Call cleanup_tree_cfg once the scop has been code
generated.
(graphite_trans_scop_block, graphite_trans_loop_block): Do not
block loops with less than two loops.
(graphite_apply_transformations): Remove the call to
scop_remove_ignoreable_gbbs.
(limit_scops): When build_scop_loop_nests fails, continue on next scop.
Fix open_scop.entry.
(graphite_transform_loops): Call recompute_all_dominators: force the
recomputation of correct CDI_DOMINATORS and CDI_POST_DOMINATORS.
Call initialize_original_copy_tables and free_original_copy_tables
to be able to copy basic blocks during code generation.
When build_scop_loop_nests fails, continue on next scop.
(value_clast): New union.
(clast_to_gcc_expression): Fix type cast warning.
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 1288_copy_bb.diff --]
[-- Type: text/x-patch; name=1288_copy_bb.diff, Size: 74725 bytes --]
2008-12-02 Sebastian Pop <sebastian.pop@amd.com>
Jan Sjodin <jan.sjodin@amd.com>
Harsha Jagasia <harsha.jagasia@amd.com>
PR middle-end/37852
PR middle-end/37883
PR middle-end/37928
PR middle-end/37980
PR middle-end/38038
PR middle-end/38039
PR middle-end/38073
PR middle-end/38083
PR middle-end/38125
* testsuite/gcc.dg/graphite/pr38073.c: New.
* testsuite/gcc.dg/graphite/pr37928.c: New.
* testsuite/gcc.dg/graphite/pr37883.c: New.
* testsuite/gcc.dg/graphite/pr38125.c: New.
* testsuite/gfortran.dg/graphite/pr38083.f90: New.
* testsuite/gfortran.dg/graphite/pr37852.f90: New.
* testsuite/gfortran.dg/graphite/pr37980.f90: New.
* testsuite/gcc.dg/graphite/scop-18.c: Remove reduction, test for
the number of detected scops. Copy exact same test for loop blocking...
* testsuite/gcc.dg/graphite/block-1.c: Fix the number of expected loops
to be blocked as reductions are not handled.
* testsuite/gcc.dg/graphite/block-4.c: ...here. New.
* tree-phinodes.c (remove_phi_nodes): New, extracted from...
* tree-cfg.c (remove_phi_nodes_and_edges_for_unreachable_block): ...here.
* tree-flow.h (remove_phi_nodes, canonicalize_loop_ivs): Declared.
* Makefile.in (graphite.o): Depend on value-prof.h.
(graphite.o-warn): Removed -Wno-error.
* tree-parloops.c (canonicalize_loop_ivs): Allow reduction_list
to be a NULL pointer. Call update_stmt. Return the newly created
cannonical induction variable.
* graphite.h (debug_rename_map): Declared. Fix some comments.
* graphite.c: Reimplement the code generation from graphite to gimple.
Include value-prof.h.
(loop_iv_stack_get_iv): Do not return NULL for constant substitutions.
(get_old_iv_from_ssa_name): Removed.
(graphite_stmt_p): New.
(new_graphite_bb): Test for useful statements before building a
graphite statement for the basic block.
(free_graphite_bb): Do not free GBB_DATA_REFS: this is a bug
in free_data_ref that calls BITMAP_FREE (DR_VOPS (dr)) without
reason.
(recompute_all_dominators, graphite_verify,
nb_reductions_in_loop, graphite_loop_normal_form): New.
(scop_record_loop): Call graphite_loop_normal_form.
(build_scop_loop_nests): Iterate over all the blocks of the
function instead of relying on the incomplete information from
SCOP_BBS. Return the success of the operation.
(find_params_in_bb): Use the data from GBB_DATA_REFS.
(add_bb_domains): Removed.
(build_loop_iteration_domains): Don't call add_bb_domains.
Add the iteration domain only to the basic blocks that have been
translated to graphite.
(build_scop_conditions_1): Add constraints only if the basic
block have been translated to graphite.
(build_scop_data_accesses): Completely disabled until data
dependence is correctly implemented.
(debug_rename_elt, debug_rename_map_1, debug_rename_map): New.
(remove_all_edges_1, remove_all_edges): Removed.
(get_new_name_from_old_name): New.
(graphite_rename_variables_in_stmt): Renamed
rename_variables_in_stmt. Call get_new_name_from_old_name.
Use replace_exp and update_stmt.
(is_old_iv): Renamed is_iv.
(expand_scalar_variables_stmt): Extra parameter for renaming map.
Use replace_exp and update_stmt.
(expand_scalar_variables_expr): Same. Use the map to get the
new names for the renaming of induction variables and for the
renaming of variables after a basic block has been copied.
(expand_scalar_variables): Same.
(graphite_rename_variables): Renamed rename_variables.
(move_phi_nodes): Removed.
(get_false_edge_from_guard_bb): New.
(build_iv_mapping): Do not insert the induction variable of a
loop in the renaming iv map if the basic block does not belong
to that loop.
(register_old_new_names, graphite_copy_stmts_from_block,
copy_bb_and_scalar_dependences): New.
(translate_clast): Heavily reimplemented: copy basic blocks,
do not move them. Finally, in call cleanup_tree_cfg in gloog.
At each translation step call graphite_verify ensuring the
consistency of the SSA, loops and dominators information.
(collect_virtual_phis, find_vdef_for_var_in_bb,
find_vdef_for_var_1, find_vdef_for_var,
patch_phis_for_virtual_defs): Removed huge hack.
(mark_old_loops, remove_dead_loops, skip_phi_defs,
collect_scop_exit_phi_args, patch_scop_exit_phi_args,
gbb_can_be_ignored, scop_remove_ignoreable_gbbs, ): Removed.
(remove_sese_region, ifsese, if_region_entry, if_region_exit,
if_region_get_condition_block, if_region_set_false_region,
create_if_region_on_edge, move_sese_in_condition, bb_in_sese_p,
sese_find_uses_to_rename_use, sese_find_uses_to_rename_bb,
sese_add_exit_phis_edge, sese_add_exit_phis_var,
rewrite_into_sese_closed_ssa): New.
(gloog): Remove dead code. Early return if code cannot be
generated. Call cleanup_tree_cfg once the scop has been code
generated.
(graphite_trans_scop_block, graphite_trans_loop_block): Do not
block loops with less than two loops.
(graphite_apply_transformations): Remove the call to
scop_remove_ignoreable_gbbs.
(limit_scops): When build_scop_loop_nests fails, continue on next scop.
Fix open_scop.entry.
(graphite_transform_loops): Call recompute_all_dominators: force the
recomputation of correct CDI_DOMINATORS and CDI_POST_DOMINATORS.
Call initialize_original_copy_tables and free_original_copy_tables
to be able to copy basic blocks during code generation.
When build_scop_loop_nests fails, continue on next scop.
(value_clast): New union.
(clast_to_gcc_expression): Fix type cast warning.
Index: tree-phinodes.c
===================================================================
--- tree-phinodes.c (revision 141730)
+++ tree-phinodes.c (working copy)
@@ -474,4 +474,17 @@ remove_phi_node (gimple_stmt_iterator *g
release_ssa_name (gimple_phi_result (phi));
}
+/* Remove all the phi nodes from BB. */
+
+void
+remove_phi_nodes (basic_block bb)
+{
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
+ remove_phi_node (&gsi, true);
+
+ set_phi_nodes (bb, NULL);
+}
+
#include "gt-tree-phinodes.h"
Index: testsuite/gcc.dg/graphite/pr38073.c
===================================================================
--- testsuite/gcc.dg/graphite/pr38073.c (revision 0)
+++ testsuite/gcc.dg/graphite/pr38073.c (revision 0)
@@ -0,0 +1,9 @@
+/* { dg-options "-O3 -fgraphite-identity" } */
+
+test_seg(int a, int b)
+{
+ int i,r=1;
+ for(i=0; i<b ;i++)
+ r*=a;
+ return r;
+}
Index: testsuite/gcc.dg/graphite/scop-18.c
===================================================================
--- testsuite/gcc.dg/graphite/scop-18.c (revision 141730)
+++ testsuite/gcc.dg/graphite/scop-18.c (working copy)
@@ -1,4 +1,4 @@
-/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+/* { dg-options "-O2 -fgraphite -fdump-tree-graphite-all" } */
#define N 24
#define M 1000
@@ -13,14 +13,14 @@ void test (void)
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];
+ 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];
+ A[i][j] = B[i][k] * C[k][j];
}
-/* { dg-final { scan-tree-dump-times "Strip Mining is not profitable" 3 "graphite" } } */
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 2" 1 "graphite"} } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: testsuite/gcc.dg/graphite/pr37928.c
===================================================================
--- testsuite/gcc.dg/graphite/pr37928.c (revision 0)
+++ testsuite/gcc.dg/graphite/pr37928.c (revision 0)
@@ -0,0 +1,33 @@
+/* { dg-options "-O3 -floop-block" } */
+
+int get_state(int size, int *node, int *hash)
+{
+ int i=0;
+ while(hash[i])
+ {
+ if(node[hash[i]] == 0)
+ return hash[i]-1;
+ i++;
+ if(i==5)
+ i=0;
+ }
+ return -1;
+}
+
+void foo (int);
+
+int gate1(int size, int *node, int *hash)
+{
+ int i, j ;
+ int add_size=0;
+ for(i=0; i<size; i++)
+ {
+ j = get_state(size,node, hash);
+ if(j == -1)
+ {
+ add_size++;
+ }
+ }
+
+ foo (size+add_size);
+}
Index: testsuite/gcc.dg/graphite/pr37883.c
===================================================================
--- testsuite/gcc.dg/graphite/pr37883.c (revision 0)
+++ testsuite/gcc.dg/graphite/pr37883.c (revision 0)
@@ -0,0 +1,11 @@
+/* { dg-options "-O3 -floop-block" } */
+
+void test_sort()
+{
+ char *base;
+ register char c, *i, *hi;
+
+ for (i = base; i < hi; i++)
+ *i++ = c;
+}
+
Index: testsuite/gcc.dg/graphite/pr38125.c
===================================================================
--- testsuite/gcc.dg/graphite/pr38125.c (revision 0)
+++ testsuite/gcc.dg/graphite/pr38125.c (revision 0)
@@ -0,0 +1,32 @@
+/* { dg-options "-O3 -fgraphite-identity" } */
+
+typedef struct sv TEST_SV;
+typedef struct av TEST_AV;
+typedef struct magic TEST_MAGIC;
+typedef struct xpvav TEST_XPVAV;
+struct sv
+{
+ void* sv_any;
+};
+struct av
+{
+ TEST_XPVAV* sv_any;
+};
+struct xpvav
+{
+ char* xav_array;
+ long int xav_fill;
+ long int xav_max;
+};
+struct magic {
+ TEST_SV* mg_obj;
+};
+extern TEST_SV PL_sv_undef;
+Perl_av_fill( register TEST_AV *av, int fill)
+{
+ TEST_MAGIC *mg;
+ int key = ((TEST_XPVAV*) (av)->sv_any)->xav_fill;
+ TEST_SV** ary = ((TEST_SV**)((TEST_XPVAV*) (av)->sv_any)->xav_array);
+ while (key < fill)
+ ary[++key] = &PL_sv_undef;
+}
Index: testsuite/gcc.dg/graphite/block-1.c
===================================================================
--- testsuite/gcc.dg/graphite/block-1.c (revision 141730)
+++ testsuite/gcc.dg/graphite/block-1.c (working copy)
@@ -2,6 +2,8 @@
#define MAX 8192
+void bar (void);
+
int main()
{
int i, j;
@@ -9,6 +11,8 @@ int main()
int A[MAX * MAX];
int B[MAX * MAX];
+ bar ();
+
for (i = 0; i < MAX; i++)
for (j = 0; j < MAX; j++)
{
@@ -20,6 +24,11 @@ int main()
for (j = 0; j < MAX; j++)
A[i*MAX + j] += B[j*MAX + i];
+ bar ();
+
+ /* FIXME: For now, reductions are not handled by the code generation
+ of graphite. We have to bound the scop to the above loops. */
+
for(i = 0; i < MAX; i++)
for(j = 0; j < MAX; j++)
sum += A[i*MAX + j];
@@ -27,5 +36,5 @@ int main()
return sum;
}
-/* { dg-final { scan-tree-dump-times "Loop blocked" 3 "graphite"} } */
+/* { dg-final { scan-tree-dump-times "Loop blocked" 2 "graphite"} } */
/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: testsuite/gcc.dg/graphite/block-4.c
===================================================================
--- testsuite/gcc.dg/graphite/block-4.c (revision 0)
+++ testsuite/gcc.dg/graphite/block-4.c (revision 0)
@@ -0,0 +1,26 @@
+/* { dg-options "-O2 -floop-block -fdump-tree-graphite-all" } */
+
+#define N 24
+#define M 1000
+
+float A[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] = 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" } } */
Index: testsuite/gfortran.dg/graphite/pr38083.f90
===================================================================
--- testsuite/gfortran.dg/graphite/pr38083.f90 (revision 0)
+++ testsuite/gfortran.dg/graphite/pr38083.f90 (revision 0)
@@ -0,0 +1,16 @@
+! { dg-options "-O3 -floop-block" }
+
+SUBROUTINE IVSORT (IL,IH,NSEGS,IOUNIT)
+ INTEGER IOUNIT
+
+ INTEGER, PARAMETER :: MAXGS = 32
+
+10 IF (IL .GE. IH) GO TO 80
+20 NSEGS = (IH + IL) / 2
+ IF (NSEGS .GT. MAXSGS) THEN
+ WRITE (IOUNIT),MAXSGS
+ ENDIF
+80 NSEGS = NSEGS - 1
+90 IF (IH - IL .GE. 11) GO TO 20
+110 IF (IL .EQ. IH) GO TO 80
+END SUBROUTINE IVSORT
Index: testsuite/gfortran.dg/graphite/pr37852.f90
===================================================================
--- testsuite/gfortran.dg/graphite/pr37852.f90 (revision 0)
+++ testsuite/gfortran.dg/graphite/pr37852.f90 (revision 0)
@@ -0,0 +1,13 @@
+! { dg-options "-O2 -floop-block" }
+
+PROGRAM TEST_FPU
+CHARACTER (LEN=36) :: invert_id(1) = &
+ (/ 'Test1 - Gauss 2000 (101x101) inverts'/)
+END PROGRAM TEST_FPU
+
+SUBROUTINE Gauss (a,n)
+INTEGER, PARAMETER :: RK8 = SELECTED_REAL_KIND(15, 300)
+REAL(RK8) :: a(n,n)
+INTEGER :: ipvt(n)
+a(:,ipvt) = b
+END SUBROUTINE Gauss
Index: testsuite/gfortran.dg/graphite/pr37980.f90
===================================================================
--- testsuite/gfortran.dg/graphite/pr37980.f90 (revision 0)
+++ testsuite/gfortran.dg/graphite/pr37980.f90 (revision 0)
@@ -0,0 +1,11 @@
+! { dg-options "-O2 -floop-block" }
+
+module INT_MODULE
+contains
+ pure function spher_cartesians(in1) result(out1)
+ integer(kind=kind(1)) :: in1
+ intent(in) :: in1
+ real(kind=kind(1.0d0)), dimension(0:in1,0:in1,0:in1) :: mat0
+ mat0 = 0.0d0
+ end function spher_cartesians
+end module INT_MODULE
Index: tree-parloops.c
===================================================================
--- tree-parloops.c (revision 141730)
+++ tree-parloops.c (working copy)
@@ -1324,9 +1324,10 @@ create_loop_fn (void)
/* Bases all the induction variables in LOOP on a single induction variable
(unsigned with base 0 and step 1), whose final value is compared with
NIT. The induction variable is incremented in the loop latch.
- REDUCTION_LIST describes the reductions in LOOP. */
+ REDUCTION_LIST describes the reductions in LOOP. Return the induction
+ variable that was created. */
-static void
+tree
canonicalize_loop_ivs (struct loop *loop, htab_t reduction_list, tree nit)
{
unsigned precision = TYPE_PRECISION (TREE_TYPE (nit));
@@ -1367,7 +1368,12 @@ canonicalize_loop_ivs (struct loop *loop
}
ok = simple_iv (loop, phi, res, &iv, true);
- red = reduction_phi (reduction_list, phi);
+
+ if (reduction_list)
+ red = reduction_phi (reduction_list, phi);
+ else
+ red = NULL;
+
/* We preserve the reduction phi nodes. */
if (!ok && red)
{
@@ -1405,6 +1411,9 @@ canonicalize_loop_ivs (struct loop *loop
gimple_cond_set_code (stmt, LT_EXPR);
gimple_cond_set_lhs (stmt, var_before);
gimple_cond_set_rhs (stmt, nit);
+ update_stmt (stmt);
+
+ return var_before;
}
/* Moves the exit condition of LOOP to the beginning of its header, and
Index: graphite.c
===================================================================
--- graphite.c (revision 141731)
+++ graphite.c (working copy)
@@ -51,6 +51,7 @@ along with GCC; see the file COPYING3.
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "domwalk.h"
+#include "value-prof.h"
#include "pointer-set.h"
#include "gimple.h"
@@ -167,12 +168,9 @@ static tree
loop_iv_stack_get_iv (loop_iv_stack stack, int index)
{
iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index);
- tree result = NULL;
+ iv_stack_entry_data data = entry->data;
- if (entry->kind != iv_stack_entry_const)
- result = entry->data.iv->t;
-
- return result;
+ return iv_stack_entry_is_iv (entry) ? data.iv->t : data.constant;
}
/* Get the IV from its NAME in STACK. */
@@ -292,33 +290,6 @@ loop_iv_stack_remove_constants (loop_iv_
}
}
-/* In SCOP, get the induction variable from NAME. OLD is the original
- loop that contained the definition of NAME. */
-
-static name_tree
-get_old_iv_from_ssa_name (scop_p scop, loop_p old, tree name)
-{
- tree var = SSA_NAME_VAR (name);
- int i;
- name_tree oldiv;
-
- for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
- {
- loop_p current = old;
-
- while (current)
- {
- if (var == oldiv->t
- && oldiv->loop == current)
- return oldiv;
-
- current = loop_outer (current);
- }
- }
- return NULL;
-
-}
-
/* Returns a new loop_to_cloog_loop_str structure. */
static inline struct loop_to_cloog_loop_str *
@@ -1014,23 +985,85 @@ harmful_stmt_in_bb (basic_block scop_ent
return NULL;
}
+/* Returns true when BB will be represented in graphite. Return false
+ for the basic blocks that contain code eliminated in the code
+ generation pass: i.e. induction variables and exit conditions. */
+
+static bool
+graphite_stmt_p (scop_p scop, basic_block bb,
+ VEC (data_reference_p, heap) *drs)
+{
+ gimple_stmt_iterator gsi;
+ loop_p loop = bb->loop_father;
+
+ if (VEC_length (data_reference_p, drs) > 0)
+ return true;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+
+ switch (gimple_code (stmt))
+ {
+ /* Control flow expressions can be ignored, as they are
+ represented in the iteration domains and will be
+ regenerated by graphite. */
+ case GIMPLE_COND:
+ case GIMPLE_GOTO:
+ case GIMPLE_SWITCH:
+ break;
+
+ case GIMPLE_ASSIGN:
+ {
+ tree var = gimple_assign_lhs (stmt);
+ var = analyze_scalar_evolution (loop, var);
+ var = instantiate_scev (block_before_scop (scop), loop, var);
+
+ if (chrec_contains_undetermined (var))
+ return true;
+
+ break;
+ }
+
+ default:
+ return true;
+ }
+ }
+
+ return false;
+}
+
/* Store the GRAPHITE representation of BB. */
static void
new_graphite_bb (scop_p scop, basic_block bb)
{
- struct graphite_bb *gbb = XNEW (struct graphite_bb);
+ struct graphite_bb *gbb;
+ VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
+ struct loop *nest = outermost_loop_in_scop (scop, bb);
+ gimple_stmt_iterator gsi;
+
+ bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
+
+ if (!graphite_stmt_p (scop, bb, drs))
+ {
+ free_data_refs (drs);
+ return;
+ }
+
+ gbb = XNEW (struct graphite_bb);
bb->aux = gbb;
GBB_BB (gbb) = bb;
GBB_SCOP (gbb) = scop;
- GBB_DATA_REFS (gbb) = NULL;
+ GBB_DATA_REFS (gbb) = drs;
GBB_DOMAIN (gbb) = NULL;
GBB_CONDITIONS (gbb) = NULL;
GBB_CONDITION_CASES (gbb) = NULL;
GBB_LOOPS (gbb) = NULL;
VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
- bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
}
/* Frees GBB. */
@@ -1041,11 +1074,9 @@ free_graphite_bb (struct graphite_bb *gb
if (GBB_DOMAIN (gbb))
cloog_matrix_free (GBB_DOMAIN (gbb));
- free_data_refs (GBB_DATA_REFS (gbb));
VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
VEC_free (loop_p, heap, GBB_LOOPS (gbb));
-
GBB_BB (gbb)->aux = 0;
XDELETE (gbb);
}
@@ -1790,6 +1821,29 @@ mark_exit_edges (VEC (sd_region, heap) *
e->aux = s;
}
+/* Free and compute again all the dominators information. */
+
+static inline void
+recompute_all_dominators (void)
+{
+ free_dominance_info (CDI_DOMINATORS);
+ free_dominance_info (CDI_POST_DOMINATORS);
+ calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+}
+
+/* Verifies properties that GRAPHITE should maintain during translation. */
+
+static inline void
+graphite_verify (void)
+{
+#ifdef ENABLE_CHECKING
+ verify_loop_structure ();
+ verify_dominators (CDI_DOMINATORS);
+ verify_dominators (CDI_POST_DOMINATORS);
+ verify_ssa (false);
+#endif
+}
/* Create for all scop regions a single entry and a single exit edge. */
@@ -1928,64 +1982,108 @@ build_scop_bbs (scop_p scop)
sbitmap_free (visited);
}
+/* Returns the number of reduction phi nodes in LOOP. */
-/* Record LOOP as occuring in SCOP. */
+static int
+nb_reductions_in_loop (loop_p loop)
+{
+ int res = 0;
+ gimple_stmt_iterator gsi;
-static void
-scop_record_loop (scop_p scop, struct loop *loop)
+ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+ tree scev;
+
+ if (!is_gimple_reg (PHI_RESULT (phi)))
+ continue;
+
+ scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
+ scev = instantiate_parameters (loop, scev);
+ if (chrec_contains_undetermined (scev))
+ res++;
+ }
+
+ return res;
+}
+
+/* A LOOP is in normal form when it contains only one scalar phi node
+ that defines the main induction variable of the loop, only one
+ increment of the IV, and only one exit condition. */
+
+static tree
+graphite_loop_normal_form (loop_p loop)
{
- loop_p parent;
- tree induction_var;
+ struct tree_niter_desc niter;
+ tree nit;
+ gimple_seq stmts;
+ edge exit = single_dom_exit (loop);
- if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
- return;
+ if (!number_of_iterations_exit (loop, exit, &niter, false))
+ gcc_unreachable ();
- parent = loop_outer (loop);
- induction_var = find_induction_var_from_exit_cond (loop);
+ nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
+ NULL_TREE);
+ if (stmts)
+ gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
- if (!bb_in_scop_p (parent->latch, scop))
- parent = NULL;
+ /* One IV per loop. */
+ if (nb_reductions_in_loop (loop) > 0)
+ return NULL_TREE;
- if (induction_var != NULL_TREE)
- {
- name_tree oldiv = XNEW (struct name_tree);
- oldiv->t = SSA_NAME_VAR (induction_var);
- if (DECL_NAME (oldiv->t))
- oldiv->name = IDENTIFIER_POINTER (DECL_NAME (oldiv->t));
- else
- {
- int len = 2 + 16;
- char *n = XNEWVEC (char, len);
- snprintf (n, len, "D.%u", DECL_UID (oldiv->t));
- oldiv->name = n;
- }
- oldiv->loop = loop;
+ return canonicalize_loop_ivs (loop, NULL, nit);
+}
- VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
- }
+/* Record LOOP as occuring in SCOP. Returns true when the operation
+ was successful. */
+
+static bool
+scop_record_loop (scop_p scop, loop_p loop)
+{
+ tree induction_var;
+ name_tree oldiv;
+
+ if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
+ return true;
bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
+
+ induction_var = graphite_loop_normal_form (loop);
+ if (!induction_var)
+ return false;
+
+ oldiv = XNEW (struct name_tree);
+ oldiv->t = induction_var;
+ oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
+ oldiv->loop = loop;
+ VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
+ return true;
}
-/* Build the loop nests contained in SCOP. */
+/* Build the loop nests contained in SCOP. Returns true when the
+ operation was successful. */
-static void
+static bool
build_scop_loop_nests (scop_p scop)
{
unsigned i;
- graphite_bb_p gb;
+ basic_block bb;
struct loop *loop0, *loop1;
- for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
- {
- struct loop *loop = gbb_loop (gb);
+ FOR_EACH_BB (bb)
+ if (bb_in_scop_p (bb, scop))
+ {
+ struct loop *loop = bb->loop_father;
- /* Only add loops, if they are completely contained in the SCoP. */
- if (loop->header == GBB_BB (gb)
- && bb_in_scop_p (loop->latch, scop))
- scop_record_loop (scop, gbb_loop (gb));
- }
+ /* Only add loops if they are completely contained in the SCoP. */
+ if (loop->header == bb
+ && bb_in_scop_p (loop->latch, scop))
+ {
+ if (!scop_record_loop (scop, loop))
+ return false;
+ }
+ }
/* Make sure that the loops in the SCOP_LOOP_NEST are ordered. It
can be the case that an inner loop is inserted before an outer
@@ -2002,6 +2100,8 @@ build_scop_loop_nests (scop_p scop)
VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
}
}
+
+ return true;
}
/* Build dynamic schedules for all the BBs. */
@@ -2353,33 +2453,25 @@ idx_record_params (tree base, tree *idx,
access functions, conditions and loop bounds. */
static void
-find_params_in_bb (scop_p scop, basic_block bb)
+find_params_in_bb (scop_p scop, graphite_bb_p gb)
{
int i;
data_reference_p dr;
- VEC (data_reference_p, heap) *drs;
gimple_stmt_iterator gsi;
- struct loop *nest = outermost_loop_in_scop (scop, bb);
+ loop_p father = GBB_BB (gb)->loop_father;
- /* Find the parameters used in the memory access functions. */
- drs = VEC_alloc (data_reference_p, heap, 5);
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
-
- for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++)
+ for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
{
struct irp_data irp;
- irp.loop = bb->loop_father;
+ irp.loop = father;
irp.scop = scop;
for_each_index (&dr->ref, idx_record_params, &irp);
free_data_ref (dr);
}
- VEC_free (data_reference_p, heap, drs);
-
/* Find parameters in conditional statements. */
- gsi = gsi_last_bb (bb);
+ gsi = gsi_last_bb (GBB_BB (gb));
if (!gsi_end_p (gsi))
{
gimple stmt = gsi_stmt (gsi);
@@ -2387,7 +2479,7 @@ find_params_in_bb (scop_p scop, basic_bl
if (gimple_code (stmt) == GIMPLE_COND)
{
Value one;
- loop_p loop = bb->loop_father;
+ loop_p loop = father;
tree lhs, rhs;
@@ -2528,7 +2620,7 @@ find_scop_parameters (scop_p scop)
/* Find the parameters used in data accesses. */
for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
- find_params_in_bb (scop, GBB_BB (gb));
+ find_params_in_bb (scop, gb);
}
/* Build the context constraints for SCOP: constraints and relations
@@ -2560,24 +2652,6 @@ gbb_from_bb (basic_block bb)
return (graphite_bb_p) bb->aux;
}
-/* Add DOMAIN to all the basic blocks in LOOP. */
-
-static void
-add_bb_domains (struct loop *loop, CloogMatrix *domain)
-{
- basic_block *bbs = get_loop_body (loop);
- unsigned i;
-
- for (i = 0; i < loop->num_nodes; i++)
- if (bbs[i]->loop_father == loop)
- {
- graphite_bb_p gbb = gbb_from_bb (bbs[i]);
- GBB_DOMAIN (gbb) = cloog_matrix_copy (domain);
- }
-
- free (bbs);
-}
-
/* Builds the constraint matrix for LOOP in SCOP. NB_OUTER_LOOPS is the
number of loops surrounding LOOP in SCOP. OUTER_CSTR gives the
constraints matrix for the surrounding loops. */
@@ -2588,6 +2662,7 @@ build_loop_iteration_domains (scop_p sco
{
int i, j, row;
CloogMatrix *cstr;
+ graphite_bb_p gb;
int nb_rows = outer_cstr->NbRows + 1;
int nb_cols = outer_cstr->NbColumns + 1;
@@ -2668,7 +2743,9 @@ build_loop_iteration_domains (scop_p sco
if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop))
build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
- add_bb_domains (loop, cstr);
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ if (gbb_loop (gb) == loop)
+ GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
cloog_matrix_free (cstr);
}
@@ -2890,10 +2967,12 @@ build_scop_conditions_1 (VEC (gimple, he
/* Record conditions in graphite_bb. */
gbb = gbb_from_bb (bb);
- GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
- GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
-
- add_conditions_to_domain (gbb);
+ if (gbb)
+ {
+ GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
+ GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
+ add_conditions_to_domain (gbb);
+ }
dom = get_dominated_by (CDI_DOMINATORS, bb);
@@ -3158,23 +3237,14 @@ build_scop_data_accesses (scop_p scop)
int i;
graphite_bb_p gb;
+ /* FIXME: Construction of access matrix is disabled until some
+ pass, like the data dependence analysis, is using it. */
+ return;
+
for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
{
int j;
- gimple_stmt_iterator gsi;
data_reference_p dr;
- struct loop *nest = outermost_loop_in_scop (scop, GBB_BB (gb));
-
- /* On each statement of the basic block, gather all the occurences
- to read/write memory. */
- GBB_DATA_REFS (gb) = VEC_alloc (data_reference_p, heap, 5);
- for (gsi = gsi_start_bb (GBB_BB (gb)); !gsi_end_p (gsi); gsi_next (&gsi))
- find_data_references_in_stmt (nest, gsi_stmt (gsi),
- &GBB_DATA_REFS (gb));
-
- /* FIXME: Construction of access matrix is disabled until some
- pass, like the data dependence analysis, is using it. */
- continue;
/* Construct the access matrix for each data ref, with respect to
the loop nest of the current BB in the considered SCOP. */
@@ -3224,6 +3294,13 @@ clast_name_to_gcc (const char *name, VEC
gcc_unreachable ();
}
+/* A union needed to convert from CLAST expressions to GMP values. */
+
+typedef union {
+ struct clast_expr *c;
+ Value v;
+} value_clast;
+
/* Converts a Cloog AST expression E back to a GCC expression tree. */
static tree
@@ -3324,15 +3401,12 @@ clast_to_gcc_expression (struct clast_ex
{
struct clast_binary *b = (struct clast_binary *) e;
struct clast_expr *lhs = (struct clast_expr *) b->LHS;
- struct clast_expr *rhs = (struct clast_expr *) b->RHS;
tree tl = clast_to_gcc_expression (lhs, params, ivstack);
+ value_clast r;
+ tree tr;
- /* FIXME: The next statement produces a warning: Cloog assumes
- that the RHS is a constant, but this is a "void *" pointer
- that should be casted into a Value, but this cast cannot be
- done as Value is a GMP type, that is an array. Cloog must
- be fixed for removing this warning. */
- tree tr = gmp_cst_to_tree (rhs);
+ r.c = (struct clast_expr *) b->RHS;
+ tr = gmp_cst_to_tree (r.v);
switch (b->type)
{
@@ -3451,41 +3525,43 @@ graphite_create_new_loop (scop_p scop, e
return loop;
}
-/* Remove all the edges from EDGES except the edge KEEP. */
+/* Structure containing the mapping between the old names and the new
+ names used after block copy in the new loop context. */
+typedef struct rename_map_elt
+{
+ tree old_name, new_name;
+} *rename_map_elt;
+
+
+/* Print to stderr the element ELT. */
static void
-remove_all_edges_1 (VEC (edge, gc) *edges, edge keep)
+debug_rename_elt (rename_map_elt elt)
{
- edge e;
- edge_iterator ei;
-
- for (ei = ei_start (edges); (e = ei_safe_edge (ei)); )
- {
- if (e != keep)
- {
- remove_edge (e);
- e = ei_safe_edge (ei);
- }
- else
- ei_next (&ei);
- }
+ fprintf (stderr, "(");
+ print_generic_expr (stderr, elt->old_name, 0);
+ fprintf (stderr, ", ");
+ print_generic_expr (stderr, elt->new_name, 0);
+ fprintf (stderr, ")\n");
}
-/* Remove all the edges from BB except the edge KEEP. */
+/* Helper function for debug_rename_map. */
-static void
-remove_all_edges (basic_block bb, edge keep)
+static int
+debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
{
- remove_all_edges_1 (bb->succs, keep);
- remove_all_edges_1 (bb->preds, keep);
+ struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
+ debug_rename_elt (entry);
+ return 1;
}
-/* Structure containing the mapping between the old names and the new
- names used after block copy in the new loop context. */
-typedef struct rename_map_elt
+/* Print to stderr all the elements of MAP. */
+
+void
+debug_rename_map (htab_t map)
{
- tree old_name, new_name;
-} *rename_map_elt;
+ htab_traverse (map, debug_rename_map_1, NULL);
+}
/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
@@ -3520,10 +3596,27 @@ eq_rename_map_elts (const void *e1, cons
return (elt1->old_name == elt2->old_name);
}
+/* Returns the new name associated to OLD_NAME in MAP. */
+
+static tree
+get_new_name_from_old_name (htab_t map, tree old_name)
+{
+ struct rename_map_elt tmp;
+ PTR *slot;
+
+ tmp.old_name = old_name;
+ slot = htab_find_slot (map, &tmp, NO_INSERT);
+
+ if (slot && *slot)
+ return ((rename_map_elt) *slot)->new_name;
+
+ return old_name;
+}
+
/* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */
static void
-graphite_rename_variables_in_stmt (gimple stmt, htab_t map)
+rename_variables_in_stmt (gimple stmt, htab_t map)
{
ssa_op_iter iter;
use_operand_p use_p;
@@ -3531,15 +3624,12 @@ graphite_rename_variables_in_stmt (gimpl
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
tree use = USE_FROM_PTR (use_p);
- struct rename_map_elt tmp;
- PTR *slot;
-
- tmp.old_name = SSA_NAME_VAR (use);
- slot = htab_find_slot (map, &tmp, NO_INSERT);
+ tree new_name = get_new_name_from_old_name (map, use);
- if (slot && *slot)
- SET_USE (use_p, ((rename_map_elt) *slot)->new_name);
+ replace_exp (use_p, new_name);
}
+
+ update_stmt (stmt);
}
/* Returns true if SSA_NAME is a parameter of SCOP. */
@@ -3558,27 +3648,26 @@ is_parameter (scop_p scop, tree ssa_name
return false;
}
-/* Returns true if NAME is an old induction variable in SCOP. OLD is
- the original loop that contained the definition of NAME. */
+/* Returns true if NAME is an induction variable. */
static bool
-is_old_iv (scop_p scop, loop_p old, tree name)
+is_iv (tree name)
{
- return get_old_iv_from_ssa_name (scop, old, name) != NULL;
-
+ return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
}
-static void expand_scalar_variables_stmt (gimple, graphite_bb_p, scop_p, loop_p);
+static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
+ loop_p, htab_t);
/* Constructs a tree which only contains old_ivs and parameters. Any
- other variables that are defined outside GBB will be eliminated by
+ other variables that are defined outside BB will be eliminated by
using their definitions in the constructed tree. OLD_LOOP_FATHER
- is the original loop that contained GBB. */
+ is the original loop that contained BB. */
static tree
expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
- tree op1, graphite_bb_p gbb, scop_p scop,
- loop_p old_loop_father)
+ tree op1, basic_block bb, scop_p scop,
+ loop_p old_loop_father, htab_t map)
{
if ((TREE_CODE_CLASS (code) == tcc_constant
&& code == INTEGER_CST)
@@ -3591,7 +3680,7 @@ expand_scalar_variables_expr (tree type,
enum tree_code op0_code = TREE_CODE (op0);
tree op0_expr =
expand_scalar_variables_expr (op0_type, op0, op0_code,
- NULL, gbb, scop, old_loop_father);
+ NULL, bb, scop, old_loop_father, map);
return fold_build1 (code, type, op0_expr);
}
@@ -3602,12 +3691,12 @@ expand_scalar_variables_expr (tree type,
enum tree_code op0_code = TREE_CODE (op0);
tree op0_expr =
expand_scalar_variables_expr (op0_type, op0, op0_code,
- NULL, gbb, scop, old_loop_father);
+ NULL, bb, scop, old_loop_father, map);
tree op1_type = TREE_TYPE (op1);
enum tree_code op1_code = TREE_CODE (op1);
tree op1_expr =
expand_scalar_variables_expr (op1_type, op1, op1_code,
- NULL, gbb, scop, old_loop_father);
+ NULL, bb, scop, old_loop_father, map);
return fold_build2 (code, type, op0_expr, op1_expr);
}
@@ -3618,33 +3707,34 @@ expand_scalar_variables_expr (tree type,
gimple def_stmt;
enum tree_code subcode;
- if(is_parameter (scop, op0) ||
- is_old_iv (scop, old_loop_father, op0))
- return op0;
+ if (is_parameter (scop, op0)
+ || is_iv (op0))
+ return get_new_name_from_old_name (map, op0);
def_stmt = SSA_NAME_DEF_STMT (op0);
- if (gimple_bb (def_stmt) == GBB_BB (gbb))
+ if (gimple_bb (def_stmt) == bb)
{
/* If the defining statement is in the basic block already
we do not need to create a new expression for it, we
only need to ensure its operands are expanded. */
- expand_scalar_variables_stmt (def_stmt, gbb, scop,
- old_loop_father);
- return op0;
+ 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)
- return op0;
+ 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,
- gbb, scop, old_loop_father);
+ bb, scop, old_loop_father, map);
}
}
@@ -3653,89 +3743,66 @@ expand_scalar_variables_expr (tree type,
}
/* Replicates any uses of non-parameters and non-old-ivs variablesthat
- are defind outside GBB with code that is inserted in GBB.
+ are defind outside BB with code that is inserted in BB.
OLD_LOOP_FATHER is the original loop that contained STMT. */
static void
-expand_scalar_variables_stmt (gimple stmt, graphite_bb_p gbb, scop_p scop,
- loop_p old_loop_father)
+expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
+ loop_p old_loop_father, htab_t map)
{
ssa_op_iter iter;
use_operand_p use_p;
- basic_block bb = GBB_BB (gbb);
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
tree use = USE_FROM_PTR (use_p);
tree type = TREE_TYPE (use);
enum tree_code code = TREE_CODE (use);
- tree use_expr = expand_scalar_variables_expr (type, use, code, NULL,
- gbb, scop, old_loop_father);
+ tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
+ scop, old_loop_father, map);
if (use_expr != use)
{
gimple_stmt_iterator gsi = gsi_after_labels (bb);
tree new_use =
force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
true, GSI_NEW_STMT);
- SET_USE (use_p, new_use);
+ replace_exp (use_p, new_use);
}
}
+
+ update_stmt (stmt);
}
-/* Copies the definitions outside of GBB of variables that are not
- induction variables nor parameters. GBB must only contain
+/* Copies the definitions outside of BB of variables that are not
+ induction variables nor parameters. BB must only contain
"external" references to these types of variables. OLD_LOOP_FATHER
- is the original loop that contained GBB. */
+ is the original loop that contained BB. */
static void
-expand_scalar_variables (graphite_bb_p gbb, scop_p scop,
- loop_p old_loop_father)
+expand_scalar_variables (basic_block bb, scop_p scop,
+ loop_p old_loop_father, htab_t map)
{
- basic_block bb = GBB_BB (gbb);
gimple_stmt_iterator gsi;
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
{
gimple stmt = gsi_stmt (gsi);
- expand_scalar_variables_stmt (stmt, gbb, scop, old_loop_father);
+ expand_scalar_variables_stmt (stmt, bb, scop, old_loop_father, map);
gsi_next (&gsi);
}
}
-/* Rename all the SSA_NAMEs from block GBB that appear in IVSTACK in
+/* Rename all the SSA_NAMEs from block BB that appear in IVSTACK in
terms of new induction variables. OLD is the original loop that
- contained GBB. */
+ contained BB. */
static void
-graphite_rename_variables (basic_block bb, htab_t map)
+rename_variables (basic_block bb, htab_t map)
{
gimple_stmt_iterator gsi;
for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- graphite_rename_variables_in_stmt (gsi_stmt (gsi), map);
-}
-
-/* Move all the PHI nodes from block FROM to block TO.
- OLD_LOOP_FATHER is the original loop that contained FROM. */
-
-static void
-move_phi_nodes (scop_p scop, loop_p old_loop_father, basic_block from,
- basic_block to)
-{
- gimple_stmt_iterator gsi;
-
- for (gsi = gsi_start_phis (from); !gsi_end_p (gsi);)
- {
- gimple phi = gsi_stmt (gsi);
- tree op = gimple_phi_result (phi);
-
- if (get_old_iv_from_ssa_name (scop, old_loop_father, op) == NULL)
- {
- gimple new_phi = make_phi_node (op, 0);
- add_phi_node_to_bb (new_phi, to);
- }
- remove_phi_node (&gsi, false);
- }
+ rename_variables_in_stmt (gsi_stmt (gsi), map);
}
/* Remove condition from BB. */
@@ -3768,6 +3835,22 @@ get_true_edge_from_guard_bb (basic_block
return NULL;
}
+/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
+
+static edge
+get_false_edge_from_guard_bb (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!(e->flags & EDGE_TRUE_VALUE))
+ return e;
+
+ gcc_unreachable ();
+ return NULL;
+}
+
/* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
NEW_NAME is obtained from IVSTACK. IVSTACK has the same stack
@@ -3784,6 +3867,9 @@ build_iv_mapping (loop_iv_stack ivstack,
{
struct rename_map_elt tmp;
+ if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
+ continue;
+
tmp.old_name = iv->t;
slot = htab_find_slot (map, &tmp, INSERT);
@@ -3795,6 +3881,85 @@ build_iv_mapping (loop_iv_stack ivstack,
}
}
}
+
+/* Register in MAP the tuple (old_name, new_name). */
+
+static void
+register_old_new_names (htab_t map, tree old_name, tree new_name)
+{
+ struct rename_map_elt tmp;
+ PTR *slot;
+
+ tmp.old_name = old_name;
+ slot = htab_find_slot (map, &tmp, INSERT);
+
+ if (!*slot)
+ *slot = new_rename_map_elt (old_name, new_name);
+}
+
+/* Create a duplicate of the basic block BB. NOTE: This does not
+ preserve SSA form. */
+
+static void
+graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
+{
+ gimple_stmt_iterator gsi, gsi_tgt;
+
+ gsi_tgt = gsi_start_bb (new_bb);
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ def_operand_p def_p;
+ ssa_op_iter op_iter;
+ int region;
+ gimple stmt = gsi_stmt (gsi);
+ gimple copy;
+
+ if (gimple_code (stmt) == GIMPLE_LABEL)
+ continue;
+
+ /* Create a new copy of STMT and duplicate STMT's virtual
+ operands. */
+ copy = gimple_copy (stmt);
+ gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
+ mark_symbols_for_renaming (copy);
+
+ region = lookup_stmt_eh_region (stmt);
+ if (region >= 0)
+ add_stmt_to_eh_region (copy, region);
+ gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
+
+ /* Create new names for all the definitions created by COPY and
+ add replacement mappings for each new name. */
+ FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
+ {
+ tree old_name = DEF_FROM_PTR (def_p);
+ tree new_name = create_new_def_for (old_name, copy, def_p);
+ register_old_new_names (map, old_name, new_name);
+ }
+ }
+}
+
+/* Copies BB and includes in the copied BB all the statements that can
+ be reached following the use-def chains from the memory accesses,
+ and returns the next edge following this new block. */
+
+static edge
+copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
+ loop_p context_loop,
+ edge next_e, htab_t map)
+{
+ basic_block new_bb = split_edge (next_e);
+
+ next_e = single_succ_edge (new_bb);
+ graphite_copy_stmts_from_block (bb, new_bb, map);
+ remove_condition (new_bb);
+ rename_variables (new_bb, map);
+ remove_phi_nodes (new_bb);
+ expand_scalar_variables (new_bb, scop, context_loop, map);
+
+ return next_e;
+}
+
/* Translates a CLAST statement STMT to GCC representation. NEXT_E is
the edge where new generated code should be attached. BB_EXIT is the last
basic block that defines the scope of code generation. CONTEXT_LOOP is the
@@ -3815,38 +3980,20 @@ translate_clast (scop_p scop, struct loo
htab_t map;
CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
- basic_block bb = gbb->bb;
- loop_p old_loop_father = bb->loop_father;
- if (bb == ENTRY_BLOCK_PTR)
+ if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
return next_e;
- remove_condition (bb);
- expand_scalar_variables (gbb, scop, old_loop_father);
- remove_all_edges (bb, next_e);
- move_phi_nodes (scop, old_loop_father, bb, next_e->src);
- redirect_edge_succ_nodup (next_e, bb);
-
- if (context_loop)
- {
- remove_bb_from_loops (bb);
- add_bb_to_loop (bb, context_loop);
- }
-
- set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
- mark_virtual_ops_in_bb (bb);
- next_e = make_edge (bb,
- context_loop ? context_loop->latch : EXIT_BLOCK_PTR,
- EDGE_FALLTHRU);
-
- loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
-
map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
+ loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
build_iv_mapping (ivstack, map, gbb, scop);
- graphite_rename_variables (GBB_BB (gbb), map);
+ next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
+ context_loop, next_e, map);
htab_delete (map);
loop_iv_stack_remove_constants (ivstack);
-
+ update_ssa (TODO_update_ssa);
+ recompute_all_dominators ();
+ graphite_verify ();
return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
}
@@ -3864,7 +4011,9 @@ translate_clast (scop_p scop, struct loo
set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
loop_iv_stack_pop (ivstack);
-
+ last_e = single_succ_edge (split_edge (last_e));
+ recompute_all_dominators ();
+ graphite_verify ();
return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
}
@@ -3877,7 +4026,7 @@ translate_clast (scop_p scop, struct loo
next_e = translate_clast (scop, context_loop,
((struct clast_guard *) stmt)->then,
true_e, ivstack);
- redirect_edge_succ_nodup (next_e, last_e->src);
+ graphite_verify ();
return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
}
@@ -3886,6 +4035,7 @@ translate_clast (scop_p scop, struct loo
next_e = translate_clast (scop, context_loop,
((struct clast_block *) stmt)->body,
next_e, ivstack);
+ graphite_verify ();
return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
}
@@ -4100,183 +4250,6 @@ find_transform (scop_p scop)
return stmt;
}
-/* Return a vector of all the virtual phi nodes in the current
- function. */
-
-static VEC (gimple, heap) *
-collect_virtual_phis (void)
-{
- gimple_stmt_iterator si;
- gimple_vec phis = VEC_alloc (gimple, heap, 3);
- basic_block bb;
-
- FOR_EACH_BB (bb)
- for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
- /* The phis we moved will have 0 arguments because the
- original edges were removed. */
- if (gimple_phi_num_args (gsi_stmt (si)) == 0)
- VEC_safe_push (gimple, heap, phis, gsi_stmt (si));
-
- /* Deallocate if we did not find any. */
- if (VEC_length (gimple, phis) == 0)
- {
- VEC_free (gimple, heap, phis);
- phis = NULL;
- }
-
- return phis;
-}
-
-/* Find a virtual definition for variable VAR in BB. */
-
-static tree
-find_vdef_for_var_in_bb (basic_block bb, tree var)
-{
- gimple_stmt_iterator gsi;
- gimple phi;
- def_operand_p def_var;
- vuse_vec_p vv;
- ssa_op_iter op_iter;
-
- for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
- FOR_EACH_SSA_VDEF_OPERAND (def_var, vv, gsi_stmt (gsi), op_iter)
- if (SSA_NAME_VAR (*def_var) == var)
- return *def_var;
-
- for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
- FOR_EACH_SSA_DEF_OPERAND (def_var, gsi_stmt (gsi), op_iter, SSA_OP_DEF)
- if (SSA_NAME_VAR (*def_var) == var)
- return *def_var;
-
- for (gsi = gsi_start_phis (bb); !gsi_end_p(gsi); gsi_next (&gsi))
- {
- phi = gsi_stmt (gsi);
- if (SSA_NAME_VAR (PHI_RESULT (phi)) == var)
- return PHI_RESULT (phi);
- }
-
- return NULL;
-}
-
-/* Recursive helper. */
-
-static tree
-find_vdef_for_var_1 (basic_block bb, struct pointer_set_t *visited, tree var)
-{
- tree result = NULL;
- edge_iterator ei;
- edge pred_edge;
-
- if (pointer_set_contains (visited, bb))
- return NULL;
-
- pointer_set_insert (visited, bb);
- result = find_vdef_for_var_in_bb (bb, var);
-
- if (!result)
- FOR_EACH_EDGE (pred_edge, ei, bb->preds)
- if (!result)
- result = find_vdef_for_var_1 (pred_edge->src, visited, var);
-
- return result;
-}
-
-/* Finds a virtual definition for variable VAR. */
-
-static tree
-find_vdef_for_var (basic_block bb, tree var)
-{
- struct pointer_set_t *visited = pointer_set_create ();
- tree def = find_vdef_for_var_1 (bb, visited, var);
-
- pointer_set_destroy (visited);
- return def;
-}
-
-/* Update the virtual phis after loop bodies are moved to new
- loops. */
-
-static void
-patch_phis_for_virtual_defs (void)
-{
- int i;
- gimple phi;
- VEC (gimple, heap) *virtual_phis = collect_virtual_phis ();
-
- for (i = 0; VEC_iterate (gimple, virtual_phis, i, phi); i++)
- {
- basic_block bb = gimple_bb (phi);
- edge_iterator ei;
- edge pred_edge;
- gimple_stmt_iterator gsi;
- gimple new_phi;
- tree phi_result = PHI_RESULT (phi);
- tree var = SSA_NAME_VAR (phi_result);
-
- new_phi = create_phi_node (phi_result, bb);
- SSA_NAME_DEF_STMT (phi_result) = new_phi;
-
- FOR_EACH_EDGE (pred_edge, ei, bb->preds)
- {
- tree def = find_vdef_for_var (pred_edge->src, var);
-
- if (def)
- add_phi_arg (new_phi, def, pred_edge);
- else
- add_phi_arg (new_phi, gimple_default_def (cfun, var), pred_edge);
- }
-
- gsi = gsi_for_stmt (phi);
- remove_phi_node (&gsi, false);
- }
-
- VEC_free (gimple, heap, virtual_phis);
-}
-
-/* Mark the original loops of SCOP for removal, replacing their header
- field with NULL. */
-
-static void
-mark_old_loops (scop_p scop)
-{
- int i;
- struct loop *loop;
-
- for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
- {
- loop->header = NULL;
- loop->latch = NULL;
- }
-}
-
-/* Scan the loops and remove the ones that have been marked for
- removal. */
-
-static void
-remove_dead_loops (void)
-{
- struct loop *loop, *ploop;
- loop_iterator li;
-
- FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
- {
- /* Remove only those loops that we marked to be removed with
- mark_old_loops. */
- if (loop->header)
- continue;
-
- while (loop->inner)
- {
- ploop = loop->inner;
- flow_loop_tree_node_remove (ploop);
- flow_loop_tree_node_add (loop_outer (loop), ploop);
- }
-
- /* Remove the loop and free its data. */
- delete_loop (loop);
- }
-}
-
/* Returns true when it is possible to generate code for this STMT.
For the moment we cannot generate code when Cloog decides to
duplicate a statement, as we do not do a copy, but a move.
@@ -4335,231 +4308,326 @@ can_generate_code (struct clast_stmt *st
return result;
}
-/* Skip any definition that is a phi node with a single phi def. */
+/* Remove from the CFG the REGION. */
-static tree
-skip_phi_defs (tree ssa_name)
+static inline void
+remove_sese_region (sese region)
{
- tree result = ssa_name;
- gimple def_stmt = SSA_NAME_DEF_STMT (ssa_name);
+ VEC (basic_block, heap) *bbs = NULL;
+ basic_block entry_bb = SESE_ENTRY (region)->dest;
+ basic_block exit_bb = SESE_EXIT (region)->dest;
+ basic_block bb;
+ int i;
- if (gimple_code (def_stmt) == GIMPLE_PHI
- && gimple_phi_num_args (def_stmt) == 1)
- result = skip_phi_defs (gimple_phi_arg(def_stmt,0)->def);
+ VEC_safe_push (basic_block, heap, bbs, entry_bb);
+ gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
- return result;
+ for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ delete_basic_block (bb);
+
+ VEC_free (basic_block, heap, bbs);
}
-/* Returns a VEC containing the phi-arg defs coming from SCOP_EXIT in
- the destination block of SCOP_EXIT. */
+typedef struct ifsese {
+ sese region;
+ sese true_region;
+ sese false_region;
+} *ifsese;
-static VEC (tree, heap) *
-collect_scop_exit_phi_args (edge scop_exit)
+static inline edge
+if_region_entry (ifsese if_region)
{
- VEC (tree, heap) *phi_args = VEC_alloc (tree, heap, 1);
- gimple_stmt_iterator gsi;
-
- for (gsi = gsi_start_phis (scop_exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple phi = gsi_stmt (gsi);
- tree phi_arg = skip_phi_defs(PHI_ARG_DEF_FROM_EDGE (phi, scop_exit));
-
- VEC_safe_push (tree, heap, phi_args, phi_arg);
- }
+ return SESE_ENTRY (if_region->region);
+}
- return phi_args;
+static inline edge
+if_region_exit (ifsese if_region)
+{
+ return SESE_EXIT (if_region->region);
}
-/* Patches (adds) PHI_ARGS to the phi nodes in SCOP_EXIT destination. */
+static inline basic_block
+if_region_get_condition_block (ifsese if_region)
+{
+ return if_region_entry (if_region)->dest;
+}
-static void
-patch_scop_exit_phi_args (edge scop_exit,
- VEC (tree, heap) *phi_args)
+static inline void
+if_region_set_false_region (ifsese if_region, sese region)
{
- int i = 0;
- gimple_stmt_iterator gsi;
+ basic_block condition = if_region_get_condition_block (if_region);
+ edge false_edge = get_false_edge_from_guard_bb (condition);
+ edge entry_region = SESE_ENTRY (region);
+ edge exit_region = SESE_EXIT (region);
+ basic_block before_region = entry_region->src;
+ basic_block last_in_region = exit_region->src;
+ void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
+ htab_hash_pointer (exit_region),
+ NO_INSERT);
- for (gsi = gsi_start_phis (scop_exit->dest); !gsi_end_p (gsi);
- gsi_next (&gsi), i++)
+ entry_region->flags = false_edge->flags;
+ false_edge->flags = exit_region->flags;
+
+ redirect_edge_pred (entry_region, condition);
+ redirect_edge_pred (exit_region, before_region);
+ redirect_edge_pred (false_edge, last_in_region);
+
+ exit_region->flags = EDGE_FALLTHRU;
+ recompute_all_dominators ();
+
+ SESE_EXIT (region) = single_succ_edge (false_edge->dest);
+ if_region->false_region = region;
+
+ if (slot)
{
- tree def = VEC_index (tree, phi_args, i);
- gimple phi = gsi_stmt (gsi);
+ struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
- gcc_assert (PHI_ARG_DEF_FROM_EDGE (phi, scop_exit) == NULL);
+ memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
+ htab_clear_slot (current_loops->exits, slot);
- add_phi_arg (phi, def, scop_exit);
+ slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
+ htab_hash_pointer (false_edge),
+ INSERT);
+ loop_exit->e = false_edge;
+ *slot = loop_exit;
+ false_edge->src->loop_father->exits->next = loop_exit;
}
}
-/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
- the given SCOP. */
-
-static void
-gloog (scop_p scop, struct clast_stmt *stmt)
+static ifsese
+create_if_region_on_edge (edge entry, tree condition)
{
- edge new_scop_exit_edge = NULL;
- basic_block scop_exit = SCOP_EXIT (scop);
- VEC (tree, heap) *phi_args =
- collect_scop_exit_phi_args (SESE_EXIT (SCOP_REGION (scop)));
- VEC (iv_stack_entry_p, heap) *ivstack =
- VEC_alloc (iv_stack_entry_p, heap, 10);
- edge construction_edge = SESE_ENTRY (SCOP_REGION (scop));
- basic_block old_scop_exit_idom = get_immediate_dominator (CDI_DOMINATORS,
- scop_exit);
+ edge e;
+ edge_iterator ei;
+ sese sese_region = GGC_NEW (struct sese);
+ sese true_region = GGC_NEW (struct sese);
+ sese false_region = GGC_NEW (struct sese);
+ ifsese if_region = GGC_NEW (struct ifsese);
+ edge exit = create_empty_if_region_on_edge (entry, condition);
+
+ if_region->region = sese_region;
+ if_region->region->entry = entry;
+ if_region->region->exit = exit;
- if (!can_generate_code (stmt))
+ FOR_EACH_EDGE (e, ei, entry->dest->succs)
{
- cloog_clast_free (stmt);
- return;
+ if (e->flags & EDGE_TRUE_VALUE)
+ {
+ true_region->entry = e;
+ true_region->exit = single_succ_edge (e->dest);
+ if_region->true_region = true_region;
+ }
+ else if (e->flags & EDGE_FALSE_VALUE)
+ {
+ false_region->entry = e;
+ false_region->exit = single_succ_edge (e->dest);
+ if_region->false_region = false_region;
+ }
}
- redirect_edge_succ_nodup (construction_edge,
- SESE_EXIT (SCOP_REGION (scop))->dest);
- new_scop_exit_edge = translate_clast (scop,
- construction_edge->src->loop_father,
- stmt, construction_edge, &ivstack);
- free_loop_iv_stack (&ivstack);
- redirect_edge_succ (new_scop_exit_edge, scop_exit);
+ return if_region;
+}
- if (!old_scop_exit_idom
- || !dominated_by_p (CDI_DOMINATORS, SCOP_ENTRY (scop),
- old_scop_exit_idom)
- || SCOP_ENTRY (scop) == old_scop_exit_idom)
- set_immediate_dominator (CDI_DOMINATORS,
- new_scop_exit_edge->dest,
- new_scop_exit_edge->src);
+/* Moves REGION in a condition expression:
+ | if (1)
+ | ;
+ | else
+ | REGION;
+*/
- cloog_clast_free (stmt);
+static ifsese
+move_sese_in_condition (sese region)
+{
+ basic_block pred_block = split_edge (SESE_ENTRY (region));
+ ifsese if_region = NULL;
- if (new_scop_exit_edge->dest == EXIT_BLOCK_PTR)
- new_scop_exit_edge->flags = 0;
-
- delete_unreachable_blocks ();
- patch_phis_for_virtual_defs ();
- patch_scop_exit_phi_args (new_scop_exit_edge, phi_args);
- VEC_free (tree, heap, phi_args);
- mark_old_loops (scop);
- remove_dead_loops ();
- rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+ SESE_ENTRY (region) = single_succ_edge (pred_block);
+ if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
+ if_region_set_false_region (if_region, region);
-#ifdef ENABLE_CHECKING
- verify_loop_structure ();
- verify_dominators (CDI_DOMINATORS);
- verify_ssa (false);
-#endif
+ return if_region;
}
-/* Returns the number of data references in SCOP. */
+/* Returns true when BB is in REGION. */
-static int
-nb_data_refs_in_scop (scop_p scop)
+static bool
+bb_in_sese_p (basic_block bb, sese region)
{
- int i;
- graphite_bb_p gbb;
- int res = 0;
+ return (dominated_by_p (CDI_DOMINATORS, bb, SESE_ENTRY (region)->src)
+ && dominated_by_p (CDI_POST_DOMINATORS, bb, SESE_EXIT (region)->dest));
+}
- for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
- res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
+/* For USE in BB, if it is used outside of the REGION it is defined in,
+ mark it for rewrite. Record basic block BB where it is used
+ to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */
- return res;
+static void
+sese_find_uses_to_rename_use (sese region, basic_block bb, tree use,
+ bitmap *use_blocks, bitmap need_phis)
+{
+ unsigned ver;
+ basic_block def_bb;
+
+ if (TREE_CODE (use) != SSA_NAME)
+ return;
+
+ ver = SSA_NAME_VERSION (use);
+ def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
+ if (!def_bb
+ || !bb_in_sese_p (def_bb, region)
+ || bb_in_sese_p (bb, region))
+ return;
+
+ if (!use_blocks[ver])
+ use_blocks[ver] = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (use_blocks[ver], bb->index);
+
+ bitmap_set_bit (need_phis, ver);
}
-/* Check if a graphite bb can be ignored in graphite. We ignore all
- bbs, that only contain code, that will be eliminated later.
+/* Marks names that are used in BB and outside of the loop they are
+ defined in for rewrite. Records the set of blocks in that the ssa
+ names are defined to USE_BLOCKS. Record the SSA names that will
+ need exit PHIs in NEED_PHIS. */
+
+static void
+sese_find_uses_to_rename_bb (sese region, basic_block bb,
+ bitmap *use_blocks, bitmap need_phis)
+{
+ gimple_stmt_iterator bsi;
+ edge e;
+ edge_iterator ei;
+ ssa_op_iter iter;
+ tree var;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
+ sese_find_uses_to_rename_use (region, bb,
+ PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e),
+ use_blocks, need_phis);
+
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
+ sese_find_uses_to_rename_use (region, bb, var, use_blocks, need_phis);
+}
- TODO: - Move PHI nodes and scalar variables out of these bbs, that only
- remain conditions and induction variables. */
+/* Add exit phis for the USE on EXIT. */
-static bool
-gbb_can_be_ignored (graphite_bb_p gb)
+static void
+sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
{
- gimple_stmt_iterator gsi;
- scop_p scop = GBB_SCOP (gb);
- loop_p loop = GBB_BB (gb)->loop_father;
+ gimple phi = create_phi_node (use, exit);
- if (VEC_length (data_reference_p, GBB_DATA_REFS(gb)))
- return false;
+ create_new_def_for (gimple_phi_result (phi), phi,
+ gimple_phi_result_ptr (phi));
+ add_phi_arg (phi, use, false_e);
+ add_phi_arg (phi, integer_zero_node, true_e);
+}
- /* Check statements. */
- for (gsi = gsi_start_bb (GBB_BB (gb)); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
- switch (gimple_code (stmt))
- {
- /* Control flow expressions can be ignored, as they are
- represented in the iteration domains and will be
- regenerated by graphite. */
- case GIMPLE_COND:
- case GIMPLE_GOTO:
- case GIMPLE_SWITCH:
- break;
+/* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are
+ inserted in block WHERE. */
- /* Scalar variables can be ignored, if we can regenerate
- them later using their scalar evolution function.
- XXX: Just a heuristic, that needs further investigation. */
- case GIMPLE_ASSIGN:
- {
- tree var = gimple_assign_lhs (stmt);
- var = analyze_scalar_evolution (loop, var);
- var = instantiate_scev (block_before_scop (scop), loop, var);
+static void
+sese_add_exit_phis_var (basic_block where, tree var, bitmap livein,
+ edge false_e, edge true_e)
+{
+ bitmap def;
+ basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
- if (TREE_CODE (var) == SCEV_NOT_KNOWN)
- return false;
+ if (is_gimple_reg (var))
+ bitmap_clear_bit (livein, def_bb->index);
+ else
+ bitmap_set_bit (livein, def_bb->index);
- break;
- }
- /* Otherwise not ignoreable. */
- default:
- return false;
- }
- }
+ def = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (def, def_bb->index);
+ compute_global_livein (livein, def);
+ BITMAP_FREE (def);
- return true;
+ sese_add_exit_phis_edge (where, var, false_e, true_e);
}
-/* Remove all ignoreable gbbs from SCOP. */
+/* Insert in the block WHERE phi nodes for variables defined in REGION
+ and used outside the REGION. */
static void
-scop_remove_ignoreable_gbbs (scop_p scop)
+rewrite_into_sese_closed_ssa (sese region, basic_block where,
+ edge false_e, edge true_e)
{
- graphite_bb_p gb;
- int i;
+ unsigned i;
+ basic_block bb;
+ bitmap_iterator bi;
+ bitmap names_to_rename = BITMAP_ALLOC (NULL);
+ unsigned old_num_ssa_names = num_ssa_names;
+ bitmap *use_blocks = XCNEWVEC (bitmap, old_num_ssa_names);
- int max_schedule = scop_max_loop_depth (scop) + 1;
- lambda_vector last_schedule = lambda_vector_new (max_schedule);
- lambda_vector_clear (last_schedule, max_schedule);
+ update_ssa (TODO_update_ssa);
- /* Update schedules. */
- for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
- {
- int nb_loops = gbb_nb_loops (gb);
+ FOR_EACH_BB (bb)
+ sese_find_uses_to_rename_bb (region, bb, use_blocks, names_to_rename);
- if (GBB_STATIC_SCHEDULE (gb) [nb_loops] == 0)
- last_schedule [nb_loops] = 0;
+ EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
+ sese_add_exit_phis_var (where, ssa_name (i), use_blocks[i],
+ false_e, true_e);
- if (gbb_can_be_ignored (gb))
- {
- /* Mark gbb for remove. */
- bitmap_clear_bit (SCOP_BBS_B (scop), gb->bb->index);
- GBB_SCOP (gb) = NULL;
- last_schedule [nb_loops]--;
- }
- else
- lambda_vector_add (GBB_STATIC_SCHEDULE (gb), last_schedule,
- GBB_STATIC_SCHEDULE (gb), nb_loops + 1);
+ update_ssa (TODO_update_ssa);
+
+ for (i = 0; i < old_num_ssa_names; i++)
+ BITMAP_FREE (use_blocks[i]);
+
+ free (use_blocks);
+ BITMAP_FREE (names_to_rename);
+}
+
+/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
+ the given SCOP. */
+
+static void
+gloog (scop_p scop, struct clast_stmt *stmt)
+{
+ edge new_scop_exit_edge = NULL;
+ VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
+ 10);
+ loop_p context_loop;
+ ifsese if_region = NULL;
+
+ if (!can_generate_code (stmt))
+ {
+ cloog_clast_free (stmt);
+ return;
}
- /* Remove gbbs. */
- for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
- if (GBB_SCOP (gb) == NULL)
- {
- VEC_unordered_remove (graphite_bb_p, SCOP_BBS (scop), i);
- free_graphite_bb (gb);
- /* XXX: Hackish? But working. */
- i--;
- }
+ if_region = move_sese_in_condition (SCOP_REGION (scop));
+ rewrite_into_sese_closed_ssa (SCOP_REGION (scop),
+ if_region->region->exit->src,
+ if_region->false_region->exit,
+ if_region->true_region->exit);
+ graphite_verify ();
+ context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
+ new_scop_exit_edge = translate_clast (scop, context_loop,
+ stmt, if_region->true_region->entry,
+ &ivstack);
+ graphite_verify ();
+ cleanup_tree_cfg ();
+ recompute_all_dominators ();
+ graphite_verify ();
+ free_loop_iv_stack (&ivstack);
+ cloog_clast_free (stmt);
+}
- graphite_sort_gbbs (scop);
+/* Returns the number of data references in SCOP. */
+
+static int
+nb_data_refs_in_scop (scop_p scop)
+{
+ int i;
+ graphite_bb_p gbb;
+ int res = 0;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
+ res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
+
+ return res;
}
/* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
@@ -5037,11 +5105,6 @@ graphite_trans_loop_block (VEC (graphite
/* TODO: - Calculate the stride size automatically. */
int stride_size = 64;
- /* It makes no sense to block a single loop. */
- for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
- if (gbb_nb_loops (gb) < 2)
- return false;
-
for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
@@ -5124,7 +5187,7 @@ graphite_trans_scop_block (scop_p scop)
j++;
/* Found perfect loop nest. */
- if (perfect && last_nb_loops - j > 0)
+ if (perfect && last_nb_loops - j >= 2)
transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
/* Check if we start with a new loop.
@@ -5183,7 +5246,6 @@ graphite_apply_transformations (scop_p s
/* Sort the list of bbs. Keep them always sorted. */
graphite_sort_gbbs (scop);
- scop_remove_ignoreable_gbbs (scop);
if (flag_loop_block)
transform_done = graphite_trans_scop_block (scop);
@@ -5232,13 +5294,15 @@ limit_scops (void)
int j;
loop_p loop;
build_scop_bbs (scop);
- build_scop_loop_nests (scop);
+
+ if (!build_scop_loop_nests (scop))
+ continue;
for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
if (!loop_in_scop_p (loop_outer (loop), scop))
{
sd_region open_scop;
- open_scop.entry = loop_preheader_edge (loop)->dest;
+ open_scop.entry = loop->header;
open_scop.exit = single_exit (loop)->dest;
VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
}
@@ -5265,13 +5329,12 @@ graphite_transform_loops (void)
return;
current_scops = VEC_alloc (scop_p, heap, 3);
-
- calculate_dominance_info (CDI_DOMINATORS);
- calculate_dominance_info (CDI_POST_DOMINATORS);
+ recompute_all_dominators ();
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Graphite loop transformations \n");
+ initialize_original_copy_tables ();
cloog_initialize ();
build_scops ();
limit_scops ();
@@ -5283,7 +5346,9 @@ graphite_transform_loops (void)
for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
{
build_scop_bbs (scop);
- build_scop_loop_nests (scop);
+ if (!build_scop_loop_nests (scop))
+ continue;
+
build_scop_canonical_schedules (scop);
build_bb_loops (scop);
find_scop_parameters (scop);
@@ -5321,6 +5386,7 @@ graphite_transform_loops (void)
/* Cleanup. */
free_scops (current_scops);
cloog_finalize ();
+ free_original_copy_tables ();
}
#else /* If Cloog is not available: #ifndef HAVE_cloog. */
Index: graphite.h
===================================================================
--- graphite.h (revision 141731)
+++ graphite.h (working copy)
@@ -119,7 +119,7 @@ typedef struct graphite_bb
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:
@@ -132,13 +132,13 @@ typedef struct graphite_bb
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;
@@ -237,7 +237,7 @@ gbb_loop_at_index (graphite_bb_p gb, int
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)
@@ -342,8 +342,7 @@ extern void debug_gbb (graphite_bb_p, in
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_loop_vec (graphite_bb_p gb);
extern void debug_oldivs (scop_p);
@@ -522,8 +521,7 @@ scop_gimple_loop_depth (scop_p scop, loo
static inline unsigned scop_nb_params (scop_p scop);
-/* Static inline function definitions. Graphite BB
- manipulation functions. */
+/* Returns true when BB is in SCOP. */
static inline bool
bb_in_scop_p (basic_block bb, scop_p scop)
Index: tree-flow.h
===================================================================
--- tree-flow.h (revision 141731)
+++ tree-flow.h (working copy)
@@ -787,6 +787,7 @@ extern gimple create_phi_node (tree, bas
extern void add_phi_arg (gimple, tree, edge);
extern void remove_phi_args (edge);
extern void remove_phi_node (gimple_stmt_iterator *, bool);
+extern void remove_phi_nodes (basic_block);
extern void init_phinodes (void);
extern void fini_phinodes (void);
extern void release_phi_node (gimple);
@@ -988,6 +989,7 @@ unsigned int tree_ssa_prefetch_arrays (v
unsigned int remove_empty_loops (void);
void tree_ssa_iv_optimize (void);
unsigned tree_predictive_commoning (void);
+tree canonicalize_loop_ivs (struct loop *, htab_t, tree);
bool parallelize_loops (void);
bool loop_only_exit_p (const struct loop *, const_edge);
Index: Makefile.in
===================================================================
--- Makefile.in (revision 141731)
+++ Makefile.in (working copy)
@@ -183,8 +183,6 @@ dfp.o-warn = -Wno-error
bitmap.o-warn = -Wno-error
# dominance.c contains a -Wc++compat warning.
dominance.o-warn = -Wno-error
-# graphite.c contains code calling cloog that has problems.
-graphite.o-warn = -Wno-error
# mips-tfile.c contains -Wcast-qual warnings.
mips-tfile.o-warn = -Wno-error
@@ -2376,7 +2374,8 @@ tree-data-ref.o: tree-data-ref.c $(CONFI
graphite.o: graphite.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) $(TOPLEV_H) \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) $(GIMPLE_H) domwalk.h \
- $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h graphite.h pointer-set.h
+ $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h graphite.h pointer-set.h \
+ value-prof.h
graphite-data-ref.o: graphite-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) $(TOPLEV_H) \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) $(GIMPLE_H) domwalk.h \
Index: tree-cfg.c
===================================================================
--- tree-cfg.c (revision 141731)
+++ tree-cfg.c (working copy)
@@ -2072,14 +2072,9 @@ struct gimple_opt_pass pass_remove_usele
static void
remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
{
- gimple_stmt_iterator gsi;
-
/* Since this block is no longer reachable, we can just delete all
of its PHI nodes. */
- for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
- remove_phi_node (&gsi, true);
-
- set_phi_nodes (bb, NULL);
+ remove_phi_nodes (bb);
/* Remove edges to BB's successors. */
while (EDGE_COUNT (bb->succs) > 0)
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-03 7:55 [patch][graphite] Rewrite of "out of graphite" Sebastian Pop
@ 2008-12-03 10:23 ` Richard Guenther
2008-12-03 18:45 ` Sebastian Pop
0 siblings, 1 reply; 14+ messages in thread
From: Richard Guenther @ 2008-12-03 10:23 UTC (permalink / raw)
To: Sebastian Pop
Cc: GCC Patches, Diego Novillo, Daniel Berlin, Sjodin, Jan, Jagasia,
Harsha, Christophe Harle, Tobias Grosser, Albert Cohen,
Konrad Trifunovic
On Wed, 3 Dec 2008, Sebastian Pop wrote:
> Hi,
>
> I committed the attached patch to the graphite branch: it fixes all
> the problems that were reported against the graphite code generation:
>
> PR middle-end/37852
> PR middle-end/37883
> PR middle-end/37928
> PR middle-end/37980
> PR middle-end/38038
> PR middle-end/38039
> PR middle-end/38073
> PR middle-end/38083
> PR middle-end/38125
>
> I have reduced all the bugs left in the polyhedron benchmarks: they do
> not occur in the code generation part. I separately committed all the
> reduced testcases to the graphite branch such that we can address them
> more easily. These are the following testcases:
>
> * testsuite/gcc.dg/graphite/pr38084.c: New.
> * testsuite/gfortran.dg/graphite/id-1.f90: New.
> * testsuite/gfortran.dg/graphite/id-2.f90: New.
> * testsuite/gfortran.dg/graphite/id-3.f90: New.
> * testsuite/gfortran.dg/graphite/id-4.f90: New.
> * testsuite/gfortran.dg/graphite/pr37857.f90: New.
>
> I'm testing the attached patch on amd64-linux. Okay to commit to
> trunk without splitting the patch into smaller pieces: all the pieces
> are interconnected, and splitting the patch in smaller pieces is
> a painful experience already (yes, I have tried).
The middle-end parts could have been splitted ;) The middle-end parts
are ok, the graphite parts as well, but you may want to wait for more
comments from other graphite reviewers.
Thanks,
Richard.
>
> Thanks,
> Sebastian Pop
> --
> AMD - GNU Tools
>
>
> 2008-12-02 Sebastian Pop <sebastian.pop@amd.com>
> Jan Sjodin <jan.sjodin@amd.com>
> Harsha Jagasia <harsha.jagasia@amd.com>
>
> PR middle-end/37852
> PR middle-end/37883
> PR middle-end/37928
> PR middle-end/37980
> PR middle-end/38038
> PR middle-end/38039
> PR middle-end/38073
> PR middle-end/38083
> PR middle-end/38125
>
> * testsuite/gcc.dg/graphite/pr38073.c: New.
> * testsuite/gcc.dg/graphite/pr37928.c: New.
> * testsuite/gcc.dg/graphite/pr37883.c: New.
> * testsuite/gcc.dg/graphite/pr38125.c: New.
> * testsuite/gfortran.dg/graphite/pr38083.f90: New.
> * testsuite/gfortran.dg/graphite/pr37852.f90: New.
> * testsuite/gfortran.dg/graphite/pr37980.f90: New.
>
> * testsuite/gcc.dg/graphite/scop-18.c: Remove reduction, test for
> the number of detected scops. Copy exact same test for loop blocking...
> * testsuite/gcc.dg/graphite/block-1.c: Fix the number of expected loops
> to be blocked as reductions are not handled.
> * testsuite/gcc.dg/graphite/block-4.c: ...here. New.
>
> * tree-phinodes.c (remove_phi_nodes): New, extracted from...
> * tree-cfg.c (remove_phi_nodes_and_edges_for_unreachable_block): ...here.
> * tree-flow.h (remove_phi_nodes, canonicalize_loop_ivs): Declared.
> * Makefile.in (graphite.o): Depend on value-prof.h.
> (graphite.o-warn): Removed -Wno-error.
> * tree-parloops.c (canonicalize_loop_ivs): Allow reduction_list
> to be a NULL pointer. Call update_stmt. Return the newly created
> cannonical induction variable.
>
> * graphite.h (debug_rename_map): Declared. Fix some comments.
>
> * graphite.c: Reimplement the code generation from graphite to gimple.
> Include value-prof.h.
> (loop_iv_stack_get_iv): Do not return NULL for constant substitutions.
> (get_old_iv_from_ssa_name): Removed.
> (graphite_stmt_p): New.
> (new_graphite_bb): Test for useful statements before building a
> graphite statement for the basic block.
> (free_graphite_bb): Do not free GBB_DATA_REFS: this is a bug
> in free_data_ref that calls BITMAP_FREE (DR_VOPS (dr)) without
> reason.
> (recompute_all_dominators, graphite_verify,
> nb_reductions_in_loop, graphite_loop_normal_form): New.
> (scop_record_loop): Call graphite_loop_normal_form.
> (build_scop_loop_nests): Iterate over all the blocks of the
> function instead of relying on the incomplete information from
> SCOP_BBS. Return the success of the operation.
> (find_params_in_bb): Use the data from GBB_DATA_REFS.
> (add_bb_domains): Removed.
> (build_loop_iteration_domains): Don't call add_bb_domains.
> Add the iteration domain only to the basic blocks that have been
> translated to graphite.
> (build_scop_conditions_1): Add constraints only if the basic
> block have been translated to graphite.
> (build_scop_data_accesses): Completely disabled until data
> dependence is correctly implemented.
> (debug_rename_elt, debug_rename_map_1, debug_rename_map): New.
> (remove_all_edges_1, remove_all_edges): Removed.
> (get_new_name_from_old_name): New.
> (graphite_rename_variables_in_stmt): Renamed
> rename_variables_in_stmt. Call get_new_name_from_old_name.
> Use replace_exp and update_stmt.
> (is_old_iv): Renamed is_iv.
> (expand_scalar_variables_stmt): Extra parameter for renaming map.
> Use replace_exp and update_stmt.
> (expand_scalar_variables_expr): Same. Use the map to get the
> new names for the renaming of induction variables and for the
> renaming of variables after a basic block has been copied.
> (expand_scalar_variables): Same.
> (graphite_rename_variables): Renamed rename_variables.
> (move_phi_nodes): Removed.
> (get_false_edge_from_guard_bb): New.
> (build_iv_mapping): Do not insert the induction variable of a
> loop in the renaming iv map if the basic block does not belong
> to that loop.
> (register_old_new_names, graphite_copy_stmts_from_block,
> copy_bb_and_scalar_dependences): New.
> (translate_clast): Heavily reimplemented: copy basic blocks,
> do not move them. Finally, in call cleanup_tree_cfg in gloog.
> At each translation step call graphite_verify ensuring the
> consistency of the SSA, loops and dominators information.
> (collect_virtual_phis, find_vdef_for_var_in_bb,
> find_vdef_for_var_1, find_vdef_for_var,
> patch_phis_for_virtual_defs): Removed huge hack.
> (mark_old_loops, remove_dead_loops, skip_phi_defs,
> collect_scop_exit_phi_args, patch_scop_exit_phi_args,
> gbb_can_be_ignored, scop_remove_ignoreable_gbbs, ): Removed.
> (remove_sese_region, ifsese, if_region_entry, if_region_exit,
> if_region_get_condition_block, if_region_set_false_region,
> create_if_region_on_edge, move_sese_in_condition, bb_in_sese_p,
> sese_find_uses_to_rename_use, sese_find_uses_to_rename_bb,
> sese_add_exit_phis_edge, sese_add_exit_phis_var,
> rewrite_into_sese_closed_ssa): New.
> (gloog): Remove dead code. Early return if code cannot be
> generated. Call cleanup_tree_cfg once the scop has been code
> generated.
> (graphite_trans_scop_block, graphite_trans_loop_block): Do not
> block loops with less than two loops.
> (graphite_apply_transformations): Remove the call to
> scop_remove_ignoreable_gbbs.
> (limit_scops): When build_scop_loop_nests fails, continue on next scop.
> Fix open_scop.entry.
> (graphite_transform_loops): Call recompute_all_dominators: force the
> recomputation of correct CDI_DOMINATORS and CDI_POST_DOMINATORS.
> Call initialize_original_copy_tables and free_original_copy_tables
> to be able to copy basic blocks during code generation.
> When build_scop_loop_nests fails, continue on next scop.
> (value_clast): New union.
> (clast_to_gcc_expression): Fix type cast warning.
>
--
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-03 10:23 ` Richard Guenther
@ 2008-12-03 18:45 ` Sebastian Pop
2008-12-03 18:58 ` Jack Howarth
2008-12-04 10:30 ` Richard Guenther
0 siblings, 2 replies; 14+ messages in thread
From: Sebastian Pop @ 2008-12-03 18:45 UTC (permalink / raw)
To: Richard Guenther
Cc: GCC Patches, Diego Novillo, Daniel Berlin, Sjodin, Jan, Jagasia,
Harsha, Christophe Harle, Tobias Grosser, Albert Cohen,
Konrad Trifunovic
[-- Attachment #1: Type: text/plain, Size: 726 bytes --]
Hi,
On Wed, Dec 3, 2008 at 4:22 AM, Richard Guenther <rguenther@suse.de> wrote:
> The middle-end parts could have been splitted ;) The middle-end parts
> are ok, the graphite parts as well, but you may want to wait for more
> comments from other graphite reviewers.
>
Thanks for the review Richi. Other Graphite reviewers, if you have
time, please send me comments on the patches. I plan to commit
the previous patch to trunk on Friday or Monday to let you enough
time to review.
Here is another patch fixing id-1.f90 that is a type conversion
problem arising when expanding to RTL. I committed this to the
graphite branch. Okay for trunk after regtest passes on amd64-linux?
Thanks,
Sebastian Pop
--
AMD - GNU Tools
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 1290_id1.diff --]
[-- Type: text/x-patch; name=1290_id1.diff, Size: 8035 bytes --]
2008-12-03 Sebastian Pop <sebastian.pop@amd.com>
Fix testsuite/gfortran.dg/graphite/id-1.f90.
* graphite.c (gmp_cst_to_tree): Pass the type in parameter.
(loop_iv_stack_patch_for_consts): Update use of gmp_cst_to_tree.
(max_precision_type): New.
(value_clast): Removed.
(clast_to_gcc_expression): Be more careful to types of expressions.
Use max_precision_type and update use of gmp_cst_to_tree.
(graphite_translate_clast_equation): Use max_precision_type.
(graphite_create_guard_cond_expr): Do not use integer_type_node,
use the type of the condition.
(graphite_create_new_loop): Do not use integer_type_node, use the
max_precision_type of lb and ub.
Index: graphite.c
===================================================================
--- graphite.c (revision 142400)
+++ graphite.c (working copy)
@@ -64,9 +64,9 @@ static VEC (scop_p, heap) *current_scops
/* Converts a GMP constant V to a tree and returns it. */
static tree
-gmp_cst_to_tree (Value v)
+gmp_cst_to_tree (tree type, Value v)
{
- return build_int_cst (integer_type_node, value_get_si (v));
+ return build_int_cst (type, value_get_si (v));
}
/* Debug the list of old induction variables for this SCOP. */
@@ -263,7 +263,7 @@ loop_iv_stack_patch_for_consts (loop_iv_
if (((struct clast_assignment *)t)->RHS->type == expr_term
&& !term->var)
{
- tree value = gmp_cst_to_tree (term->val);
+ tree value = gmp_cst_to_tree (integer_type_node, term->val);
loop_iv_stack_insert_constant (stack, index, value);
}
index = index + 1;
@@ -1521,7 +1521,6 @@ scopdet_basic_block_info (basic_block bb
static struct scopdet_info
build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
{
-
bool in_scop = false;
sd_region open_scop;
struct scopdet_info sinfo;
@@ -3296,12 +3295,15 @@ clast_name_to_gcc (const char *name, VEC
gcc_unreachable ();
}
-/* A union needed to convert from CLAST expressions to GMP values. */
+/* Returns the maximal precision type for expressions E1 and E2. */
-typedef union {
- struct clast_expr *c;
- Value v;
-} value_clast;
+static inline tree
+max_precision_type (tree e1, tree e2)
+{
+ tree type1 = TREE_TYPE (e1);
+ tree type2 = TREE_TYPE (e2);
+ return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
+}
/* Converts a Cloog AST expression E back to a GCC expression tree. */
@@ -3310,10 +3312,6 @@ clast_to_gcc_expression (struct clast_ex
VEC (name_tree, heap) *params,
loop_iv_stack ivstack)
{
- tree type = integer_type_node;
-
- gcc_assert (e);
-
switch (e->type)
{
case expr_term:
@@ -3326,21 +3324,26 @@ clast_to_gcc_expression (struct clast_ex
return clast_name_to_gcc (t->var, params, ivstack);
else if (value_mone_p (t->val))
- return fold_build1 (NEGATE_EXPR, type,
- clast_name_to_gcc (t->var, params, ivstack));
+ {
+ tree name = clast_name_to_gcc (t->var, params, ivstack);
+ tree type = TREE_TYPE (name);
+ return fold_build1 (NEGATE_EXPR, type, name);
+ }
else
- return fold_build2 (MULT_EXPR, type,
- gmp_cst_to_tree (t->val),
- clast_name_to_gcc (t->var, params, ivstack));
+ {
+ tree name = clast_name_to_gcc (t->var, params, ivstack);
+ tree type = TREE_TYPE (name);
+ tree cst = gmp_cst_to_tree (type, t->val);
+ return fold_build2 (MULT_EXPR, type, cst, name);
+ }
}
else
- return gmp_cst_to_tree (t->val);
+ return gmp_cst_to_tree (integer_type_node, t->val);
}
case expr_red:
{
struct clast_reduction *r = (struct clast_reduction *) e;
- tree left, right;
switch (r->type)
{
@@ -3350,13 +3353,15 @@ clast_to_gcc_expression (struct clast_ex
else
{
+ tree tl = clast_to_gcc_expression (r->elts[0], params, ivstack);
+ tree tr = clast_to_gcc_expression (r->elts[1], params, ivstack);
+ tree type = max_precision_type (tl, tr);
+
gcc_assert (r->n >= 1
&& r->elts[0]->type == expr_term
&& r->elts[1]->type == expr_term);
- left = clast_to_gcc_expression (r->elts[0], params, ivstack);
- right = clast_to_gcc_expression (r->elts[1], params, ivstack);
- return fold_build2 (PLUS_EXPR, type, left, right);
+ return fold_build2 (PLUS_EXPR, type, tl, tr);
}
break;
@@ -3367,9 +3372,10 @@ clast_to_gcc_expression (struct clast_ex
else if (r->n == 2)
{
- left = clast_to_gcc_expression (r->elts[0], params, ivstack);
- right = clast_to_gcc_expression (r->elts[1], params, ivstack);
- return fold_build2 (MIN_EXPR, type, left, right);
+ tree tl = clast_to_gcc_expression (r->elts[0], params, ivstack);
+ tree tr = clast_to_gcc_expression (r->elts[1], params, ivstack);
+ tree type = max_precision_type (tl, tr);
+ return fold_build2 (MIN_EXPR, type, tl, tr);
}
else
@@ -3383,9 +3389,10 @@ clast_to_gcc_expression (struct clast_ex
else if (r->n == 2)
{
- left = clast_to_gcc_expression (r->elts[0], params, ivstack);
- right = clast_to_gcc_expression (r->elts[1], params, ivstack);
- return fold_build2 (MAX_EXPR, type, left, right);
+ tree tl = clast_to_gcc_expression (r->elts[0], params, ivstack);
+ tree tr = clast_to_gcc_expression (r->elts[1], params, ivstack);
+ tree type = max_precision_type (tl, tr);
+ return fold_build2 (MAX_EXPR, type, tl, tr);
}
else
@@ -3404,11 +3411,8 @@ clast_to_gcc_expression (struct clast_ex
struct clast_binary *b = (struct clast_binary *) e;
struct clast_expr *lhs = (struct clast_expr *) b->LHS;
tree tl = clast_to_gcc_expression (lhs, params, ivstack);
- value_clast r;
- tree tr;
-
- r.c = (struct clast_expr *) b->RHS;
- tr = gmp_cst_to_tree (r.v);
+ tree type = TREE_TYPE (tl);
+ tree tr = gmp_cst_to_tree (type, b->RHS);
switch (b->type)
{
@@ -3446,6 +3450,7 @@ graphite_translate_clast_equation (scop_
enum tree_code comp;
tree lhs = clast_to_gcc_expression (cleq->LHS, SCOP_PARAMS (scop), ivstack);
tree rhs = clast_to_gcc_expression (cleq->RHS, SCOP_PARAMS (scop), ivstack);
+ tree type = max_precision_type (lhs, rhs);
if (cleq->sign == 0)
comp = EQ_EXPR;
@@ -3456,7 +3461,7 @@ graphite_translate_clast_equation (scop_
else
comp = LE_EXPR;
- return fold_build2 (comp, integer_type_node, lhs, rhs);
+ return fold_build2 (comp, type, lhs, rhs);
}
/* Creates the test for the condition in STMT. */
@@ -3473,7 +3478,7 @@ graphite_create_guard_cond_expr (scop_p
tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
if (cond)
- cond = fold_build2 (TRUTH_AND_EXPR, integer_type_node, cond, eq);
+ cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
else
cond = eq;
}
@@ -3504,26 +3509,17 @@ graphite_create_new_loop (scop_p scop, e
struct clast_for *stmt, loop_iv_stack ivstack,
loop_p outer)
{
- struct loop *loop;
- tree ivvar;
- tree stride, lowb, upb;
+ tree lb = clast_to_gcc_expression (stmt->LB, SCOP_PARAMS (scop), ivstack);
+ tree ub = clast_to_gcc_expression (stmt->UB, SCOP_PARAMS (scop), ivstack);
+ tree type = max_precision_type (lb, ub);
+ tree stride = gmp_cst_to_tree (type, stmt->stride);
+ tree ivvar = create_tmp_var (type, "graphiteIV");
tree iv_before;
-
- gcc_assert (stmt->LB
- && stmt->UB);
-
- stride = gmp_cst_to_tree (stmt->stride);
- lowb = clast_to_gcc_expression (stmt->LB, SCOP_PARAMS (scop), ivstack);
- ivvar = create_tmp_var (integer_type_node, "graphiteIV");
+ loop_p loop = create_empty_loop_on_edge (entry_edge, lb, stride, ub, ivvar,
+ &iv_before, outer ? outer
+ : entry_edge->src->loop_father);
add_referenced_var (ivvar);
-
- upb = clast_to_gcc_expression (stmt->UB, SCOP_PARAMS (scop), ivstack);
- loop = create_empty_loop_on_edge (entry_edge, lowb, stride, upb, ivvar,
- &iv_before, outer ? outer
- : entry_edge->src->loop_father);
-
loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
-
return loop;
}
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-03 18:45 ` Sebastian Pop
@ 2008-12-03 18:58 ` Jack Howarth
2008-12-03 19:14 ` Tobias Grosser
2008-12-03 19:34 ` Sebastian Pop
2008-12-04 10:30 ` Richard Guenther
1 sibling, 2 replies; 14+ messages in thread
From: Jack Howarth @ 2008-12-03 18:58 UTC (permalink / raw)
To: Sebastian Pop
Cc: Richard Guenther, GCC Patches, Diego Novillo, Daniel Berlin,
Sjodin, Jan, Jagasia, Harsha, Christophe Harle, Tobias Grosser,
Albert Cohen, Konrad Trifunovic
On Wed, Dec 03, 2008 at 12:44:27PM -0600, Sebastian Pop wrote:
> Hi,
>
> On Wed, Dec 3, 2008 at 4:22 AM, Richard Guenther <rguenther@suse.de> wrote:
> > The middle-end parts could have been splitted ;) The middle-end parts
> > are ok, the graphite parts as well, but you may want to wait for more
> > comments from other graphite reviewers.
> >
>
> Thanks for the review Richi. Other Graphite reviewers, if you have
> time, please send me comments on the patches. I plan to commit
> the previous patch to trunk on Friday or Monday to let you enough
> time to review.
>
> Here is another patch fixing id-1.f90 that is a type conversion
> problem arising when expanding to RTL. I committed this to the
> graphite branch. Okay for trunk after regtest passes on amd64-linux?
>
> Thanks,
> Sebastian Pop
> --
> AMD - GNU Tools
> 2008-12-03 Sebastian Pop <sebastian.pop@amd.com>
>
> Fix testsuite/gfortran.dg/graphite/id-1.f90.
> * graphite.c (gmp_cst_to_tree): Pass the type in parameter.
> (loop_iv_stack_patch_for_consts): Update use of gmp_cst_to_tree.
> (max_precision_type): New.
> (value_clast): Removed.
> (clast_to_gcc_expression): Be more careful to types of expressions.
> Use max_precision_type and update use of gmp_cst_to_tree.
> (graphite_translate_clast_equation): Use max_precision_type.
> (graphite_create_guard_cond_expr): Do not use integer_type_node,
> use the type of the condition.
> (graphite_create_new_loop): Do not use integer_type_node, use the
> max_precision_type of lb and ub.
>
> Index: graphite.c
> ===================================================================
> --- graphite.c (revision 142400)
> +++ graphite.c (working copy)
> @@ -64,9 +64,9 @@ static VEC (scop_p, heap) *current_scops
> /* Converts a GMP constant V to a tree and returns it. */
>
> static tree
> -gmp_cst_to_tree (Value v)
> +gmp_cst_to_tree (tree type, Value v)
> {
> - return build_int_cst (integer_type_node, value_get_si (v));
> + return build_int_cst (type, value_get_si (v));
> }
>
> /* Debug the list of old induction variables for this SCOP. */
> @@ -263,7 +263,7 @@ loop_iv_stack_patch_for_consts (loop_iv_
> if (((struct clast_assignment *)t)->RHS->type == expr_term
> && !term->var)
> {
> - tree value = gmp_cst_to_tree (term->val);
> + tree value = gmp_cst_to_tree (integer_type_node, term->val);
> loop_iv_stack_insert_constant (stack, index, value);
> }
> index = index + 1;
> @@ -1521,7 +1521,6 @@ scopdet_basic_block_info (basic_block bb
> static struct scopdet_info
> build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
> {
> -
> bool in_scop = false;
> sd_region open_scop;
> struct scopdet_info sinfo;
> @@ -3296,12 +3295,15 @@ clast_name_to_gcc (const char *name, VEC
> gcc_unreachable ();
> }
>
> -/* A union needed to convert from CLAST expressions to GMP values. */
> +/* Returns the maximal precision type for expressions E1 and E2. */
>
> -typedef union {
> - struct clast_expr *c;
> - Value v;
> -} value_clast;
> +static inline tree
> +max_precision_type (tree e1, tree e2)
> +{
> + tree type1 = TREE_TYPE (e1);
> + tree type2 = TREE_TYPE (e2);
> + return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
> +}
>
> /* Converts a Cloog AST expression E back to a GCC expression tree. */
>
> @@ -3310,10 +3312,6 @@ clast_to_gcc_expression (struct clast_ex
> VEC (name_tree, heap) *params,
> loop_iv_stack ivstack)
> {
> - tree type = integer_type_node;
> -
> - gcc_assert (e);
> -
> switch (e->type)
> {
> case expr_term:
> @@ -3326,21 +3324,26 @@ clast_to_gcc_expression (struct clast_ex
> return clast_name_to_gcc (t->var, params, ivstack);
>
> else if (value_mone_p (t->val))
> - return fold_build1 (NEGATE_EXPR, type,
> - clast_name_to_gcc (t->var, params, ivstack));
> + {
> + tree name = clast_name_to_gcc (t->var, params, ivstack);
> + tree type = TREE_TYPE (name);
> + return fold_build1 (NEGATE_EXPR, type, name);
> + }
> else
> - return fold_build2 (MULT_EXPR, type,
> - gmp_cst_to_tree (t->val),
> - clast_name_to_gcc (t->var, params, ivstack));
> + {
> + tree name = clast_name_to_gcc (t->var, params, ivstack);
> + tree type = TREE_TYPE (name);
> + tree cst = gmp_cst_to_tree (type, t->val);
> + return fold_build2 (MULT_EXPR, type, cst, name);
> + }
> }
> else
> - return gmp_cst_to_tree (t->val);
> + return gmp_cst_to_tree (integer_type_node, t->val);
> }
>
> case expr_red:
> {
> struct clast_reduction *r = (struct clast_reduction *) e;
> - tree left, right;
>
> switch (r->type)
> {
> @@ -3350,13 +3353,15 @@ clast_to_gcc_expression (struct clast_ex
>
> else
> {
> + tree tl = clast_to_gcc_expression (r->elts[0], params, ivstack);
> + tree tr = clast_to_gcc_expression (r->elts[1], params, ivstack);
> + tree type = max_precision_type (tl, tr);
> +
> gcc_assert (r->n >= 1
> && r->elts[0]->type == expr_term
> && r->elts[1]->type == expr_term);
>
> - left = clast_to_gcc_expression (r->elts[0], params, ivstack);
> - right = clast_to_gcc_expression (r->elts[1], params, ivstack);
> - return fold_build2 (PLUS_EXPR, type, left, right);
> + return fold_build2 (PLUS_EXPR, type, tl, tr);
> }
>
> break;
> @@ -3367,9 +3372,10 @@ clast_to_gcc_expression (struct clast_ex
>
> else if (r->n == 2)
> {
> - left = clast_to_gcc_expression (r->elts[0], params, ivstack);
> - right = clast_to_gcc_expression (r->elts[1], params, ivstack);
> - return fold_build2 (MIN_EXPR, type, left, right);
> + tree tl = clast_to_gcc_expression (r->elts[0], params, ivstack);
> + tree tr = clast_to_gcc_expression (r->elts[1], params, ivstack);
> + tree type = max_precision_type (tl, tr);
> + return fold_build2 (MIN_EXPR, type, tl, tr);
> }
>
> else
> @@ -3383,9 +3389,10 @@ clast_to_gcc_expression (struct clast_ex
>
> else if (r->n == 2)
> {
> - left = clast_to_gcc_expression (r->elts[0], params, ivstack);
> - right = clast_to_gcc_expression (r->elts[1], params, ivstack);
> - return fold_build2 (MAX_EXPR, type, left, right);
> + tree tl = clast_to_gcc_expression (r->elts[0], params, ivstack);
> + tree tr = clast_to_gcc_expression (r->elts[1], params, ivstack);
> + tree type = max_precision_type (tl, tr);
> + return fold_build2 (MAX_EXPR, type, tl, tr);
> }
>
> else
> @@ -3404,11 +3411,8 @@ clast_to_gcc_expression (struct clast_ex
> struct clast_binary *b = (struct clast_binary *) e;
> struct clast_expr *lhs = (struct clast_expr *) b->LHS;
> tree tl = clast_to_gcc_expression (lhs, params, ivstack);
> - value_clast r;
> - tree tr;
> -
> - r.c = (struct clast_expr *) b->RHS;
> - tr = gmp_cst_to_tree (r.v);
> + tree type = TREE_TYPE (tl);
> + tree tr = gmp_cst_to_tree (type, b->RHS);
>
> switch (b->type)
> {
> @@ -3446,6 +3450,7 @@ graphite_translate_clast_equation (scop_
> enum tree_code comp;
> tree lhs = clast_to_gcc_expression (cleq->LHS, SCOP_PARAMS (scop), ivstack);
> tree rhs = clast_to_gcc_expression (cleq->RHS, SCOP_PARAMS (scop), ivstack);
> + tree type = max_precision_type (lhs, rhs);
>
> if (cleq->sign == 0)
> comp = EQ_EXPR;
> @@ -3456,7 +3461,7 @@ graphite_translate_clast_equation (scop_
> else
> comp = LE_EXPR;
>
> - return fold_build2 (comp, integer_type_node, lhs, rhs);
> + return fold_build2 (comp, type, lhs, rhs);
> }
>
> /* Creates the test for the condition in STMT. */
> @@ -3473,7 +3478,7 @@ graphite_create_guard_cond_expr (scop_p
> tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
>
> if (cond)
> - cond = fold_build2 (TRUTH_AND_EXPR, integer_type_node, cond, eq);
> + cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
> else
> cond = eq;
> }
> @@ -3504,26 +3509,17 @@ graphite_create_new_loop (scop_p scop, e
> struct clast_for *stmt, loop_iv_stack ivstack,
> loop_p outer)
> {
> - struct loop *loop;
> - tree ivvar;
> - tree stride, lowb, upb;
> + tree lb = clast_to_gcc_expression (stmt->LB, SCOP_PARAMS (scop), ivstack);
> + tree ub = clast_to_gcc_expression (stmt->UB, SCOP_PARAMS (scop), ivstack);
> + tree type = max_precision_type (lb, ub);
> + tree stride = gmp_cst_to_tree (type, stmt->stride);
> + tree ivvar = create_tmp_var (type, "graphiteIV");
> tree iv_before;
> -
> - gcc_assert (stmt->LB
> - && stmt->UB);
> -
> - stride = gmp_cst_to_tree (stmt->stride);
> - lowb = clast_to_gcc_expression (stmt->LB, SCOP_PARAMS (scop), ivstack);
> - ivvar = create_tmp_var (integer_type_node, "graphiteIV");
> + loop_p loop = create_empty_loop_on_edge (entry_edge, lb, stride, ub, ivvar,
> + &iv_before, outer ? outer
> + : entry_edge->src->loop_father);
> add_referenced_var (ivvar);
> -
> - upb = clast_to_gcc_expression (stmt->UB, SCOP_PARAMS (scop), ivstack);
> - loop = create_empty_loop_on_edge (entry_edge, lowb, stride, upb, ivvar,
> - &iv_before, outer ? outer
> - : entry_edge->src->loop_father);
> -
> loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
> -
> return loop;
> }
>
Sebastian,
Does graphite branch now build all of the polyhedron 2005 benchmarks
at -O2 fgraphite-identity without compilation or execution problems? If so
that's great.
Jack
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-03 18:58 ` Jack Howarth
@ 2008-12-03 19:14 ` Tobias Grosser
2008-12-03 19:34 ` Sebastian Pop
1 sibling, 0 replies; 14+ messages in thread
From: Tobias Grosser @ 2008-12-03 19:14 UTC (permalink / raw)
To: Jack Howarth
Cc: Sebastian Pop, Richard Guenther, GCC Patches, Diego Novillo,
Daniel Berlin, Sjodin, Jan, Jagasia, Harsha, Christophe Harle,
Albert Cohen, Konrad Trifunovic
On Wed, 2008-12-03 at 13:57 -0500, Jack Howarth wrote:
> On Wed, Dec 03, 2008 at 12:44:27PM -0600, Sebastian Pop wrote:
> > Hi,
> >
> > On Wed, Dec 3, 2008 at 4:22 AM, Richard Guenther <rguenther@suse.de> wrote:
> > > The middle-end parts could have been splitted ;) The middle-end parts
> > > are ok, the graphite parts as well, but you may want to wait for more
> > > comments from other graphite reviewers.
> > >
> >
> > Thanks for the review Richi. Other Graphite reviewers, if you have
> > time, please send me comments on the patches. I plan to commit
> > the previous patch to trunk on Friday or Monday to let you enough
> > time to review.
> >
> > Here is another patch fixing id-1.f90 that is a type conversion
> > problem arising when expanding to RTL. I committed this to the
> > graphite branch. Okay for trunk after regtest passes on amd64-linux?
> >
> > Thanks,
> > Sebastian Pop
Hey Sebastian,
I just tried it. There is one bug in build_scops_1 (I will work on it)
left, but is seems otherwise we build polyhedron!
That looks like really great work! Thanks a lot.
Tobi
P.S.: I will look at it over the weekend. But it definitely seems like a
big step forward.
> Sebastian,
> Does graphite branch now build all of the polyhedron 2005 benchmarks
> at -O2 fgraphite-identity without compilation or execution problems? If so
> that's great.
> Jack
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-03 18:58 ` Jack Howarth
2008-12-03 19:14 ` Tobias Grosser
@ 2008-12-03 19:34 ` Sebastian Pop
2008-12-03 19:48 ` Sebastian Pop
2008-12-04 1:09 ` Jack Howarth
1 sibling, 2 replies; 14+ messages in thread
From: Sebastian Pop @ 2008-12-03 19:34 UTC (permalink / raw)
To: Jack Howarth
Cc: Richard Guenther, GCC Patches, Diego Novillo, Daniel Berlin,
Sjodin, Jan, Jagasia, Harsha, Christophe Harle, Tobias Grosser,
Albert Cohen, Konrad Trifunovic
On Wed, Dec 3, 2008 at 12:57 PM, Jack Howarth <howarth@bromo.med.uc.edu> wrote:
> Does graphite branch now build all of the polyhedron 2005 benchmarks
> at -O2 fgraphite-identity without compilation or execution problems? If so
> that's great.
There are still 3 bugs left for building polyhedron benchmarks:
id-{2,3,4}.f90. I'm working on id-4.f90, Tobias and Dwarak are going
to work on id-3.f90 that is a fail in the scop detection: sd_region.
Sebastian Pop
--
AMD - GNU Tools
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-03 19:34 ` Sebastian Pop
@ 2008-12-03 19:48 ` Sebastian Pop
2008-12-04 10:31 ` Richard Guenther
2008-12-04 1:09 ` Jack Howarth
1 sibling, 1 reply; 14+ messages in thread
From: Sebastian Pop @ 2008-12-03 19:48 UTC (permalink / raw)
To: Jack Howarth
Cc: Richard Guenther, GCC Patches, Diego Novillo, Daniel Berlin,
Sjodin, Jan, Jagasia, Harsha, Christophe Harle, Tobias Grosser,
Albert Cohen, Konrad Trifunovic
[-- Attachment #1: Type: text/plain, Size: 418 bytes --]
On Wed, Dec 3, 2008 at 1:33 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> There are still 3 bugs left for building polyhedron benchmarks:
> id-{2,3,4}.f90. I'm working on id-4.f90, Tobias and Dwarak are going
> to work on id-3.f90 that is a fail in the scop detection: sd_region.
>
Here is the fix for id-4.f90. Committed to graphite branch, waiting for review
to commit to trunk.
Sebastian Pop
--
AMD - GNU Tools
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 1291_id4.diff --]
[-- Type: text/x-patch; name=1291_id4.diff, Size: 1611 bytes --]
2008-12-03 Sebastian Pop <sebastian.pop@amd.com>
Fix testsuite/gfortran.dg/graphite/id-4.f90.
* graphite.c (scan_tree_for_params): Do not compute the multiplicand
when not needed.
Index: graphite.c
===================================================================
--- graphite.c (revision 142403)
+++ graphite.c (working copy)
@@ -2324,26 +2324,28 @@ scan_tree_for_params (scop_p s, tree e,
case MULT_EXPR:
if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
{
- Value val;
-
- gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
-
- value_init (val);
- value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
- value_multiply (k, k, val);
- value_clear (val);
+ if (c)
+ {
+ Value val;
+ gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
+ value_init (val);
+ value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
+ value_multiply (k, k, val);
+ value_clear (val);
+ }
scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
}
else
{
- Value val;
-
- gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
-
- value_init (val);
- value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
- value_multiply (k, k, val);
- value_clear (val);
+ if (c)
+ {
+ Value val;
+ gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
+ value_init (val);
+ value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
+ value_multiply (k, k, val);
+ value_clear (val);
+ }
scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
}
break;
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-03 19:34 ` Sebastian Pop
2008-12-03 19:48 ` Sebastian Pop
@ 2008-12-04 1:09 ` Jack Howarth
2008-12-04 1:19 ` Sebastian Pop
1 sibling, 1 reply; 14+ messages in thread
From: Jack Howarth @ 2008-12-04 1:09 UTC (permalink / raw)
To: Sebastian Pop
Cc: Richard Guenther, GCC Patches, Diego Novillo, Daniel Berlin,
Sjodin, Jan, Jagasia, Harsha, Christophe Harle, Tobias Grosser,
Albert Cohen, Konrad Trifunovic
On Wed, Dec 03, 2008 at 01:33:44PM -0600, Sebastian Pop wrote:
> On Wed, Dec 3, 2008 at 12:57 PM, Jack Howarth <howarth@bromo.med.uc.edu> wrote:
> > Does graphite branch now build all of the polyhedron 2005 benchmarks
> > at -O2 fgraphite-identity without compilation or execution problems? If so
> > that's great.
>
> There are still 3 bugs left for building polyhedron benchmarks:
> id-{2,3,4}.f90. I'm working on id-4.f90, Tobias and Dwarak are going
> to work on id-3.f90 that is a fail in the scop detection: sd_region.
>
> Sebastian Pop
> --
> AMD - GNU Tools
Sebastian,
Has anyone tried building and running the SPEC benchmarks with
-O2 -fgraphite-identity? After the polyhedron benchmark related
fixes are in gcc trunk, it would be interesting to know how that
works out.
Jack
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-04 1:09 ` Jack Howarth
@ 2008-12-04 1:19 ` Sebastian Pop
2008-12-04 1:39 ` Jack Howarth
0 siblings, 1 reply; 14+ messages in thread
From: Sebastian Pop @ 2008-12-04 1:19 UTC (permalink / raw)
To: Jack Howarth
Cc: Richard Guenther, GCC Patches, Diego Novillo, Daniel Berlin,
Sjodin, Jan, Jagasia, Harsha, Christophe Harle, Tobias Grosser,
Albert Cohen, Konrad Trifunovic, Thakkar, Mitul
On Wed, Dec 3, 2008 at 7:08 PM, Jack Howarth <howarth@bromo.med.uc.edu> wrote:
> Has anyone tried building and running the SPEC benchmarks with
> -O2 -fgraphite-identity?
Mitul is trying cpu2k6 and will reduce testcases for the remaining
fails. I suspect the same error as for id-2.f90 will be quite
frequent. The fix for this bug seems to be quite tricky: the problem
occurs in the middle-end of graphite in the construction of the
polyhedral representation.
Sebastian
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-04 1:19 ` Sebastian Pop
@ 2008-12-04 1:39 ` Jack Howarth
0 siblings, 0 replies; 14+ messages in thread
From: Jack Howarth @ 2008-12-04 1:39 UTC (permalink / raw)
To: Sebastian Pop
Cc: Richard Guenther, GCC Patches, Diego Novillo, Daniel Berlin,
Sjodin, Jan, Jagasia, Harsha, Christophe Harle, Tobias Grosser,
Albert Cohen, Konrad Trifunovic, Thakkar, Mitul
On Wed, Dec 03, 2008 at 07:18:51PM -0600, Sebastian Pop wrote:
> On Wed, Dec 3, 2008 at 7:08 PM, Jack Howarth <howarth@bromo.med.uc.edu> wrote:
> > Has anyone tried building and running the SPEC benchmarks with
> > -O2 -fgraphite-identity?
>
> Mitul is trying cpu2k6 and will reduce testcases for the remaining
> fails. I suspect the same error as for id-2.f90 will be quite
> frequent. The fix for this bug seems to be quite tricky: the problem
> occurs in the middle-end of graphite in the construction of the
> polyhedral representation.
>
> Sebastian
Nice. At this rate, perhaps -fgraphite could be made an alias for -fgraphite-identity
in the gcc 4.4 release. After all, using -fgraphite without -fgraphite-identity
is pretty much a waste of cpu cycles.
Jack
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-03 18:45 ` Sebastian Pop
2008-12-03 18:58 ` Jack Howarth
@ 2008-12-04 10:30 ` Richard Guenther
2008-12-04 18:20 ` Sebastian Pop
1 sibling, 1 reply; 14+ messages in thread
From: Richard Guenther @ 2008-12-04 10:30 UTC (permalink / raw)
To: Sebastian Pop
Cc: GCC Patches, Diego Novillo, Daniel Berlin, Sjodin, Jan, Jagasia,
Harsha, Christophe Harle, Tobias Grosser, Albert Cohen,
Konrad Trifunovic
On Wed, 3 Dec 2008, Sebastian Pop wrote:
> Hi,
>
> On Wed, Dec 3, 2008 at 4:22 AM, Richard Guenther <rguenther@suse.de> wrote:
> > The middle-end parts could have been splitted ;) The middle-end parts
> > are ok, the graphite parts as well, but you may want to wait for more
> > comments from other graphite reviewers.
> >
>
> Thanks for the review Richi. Other Graphite reviewers, if you have
> time, please send me comments on the patches. I plan to commit
> the previous patch to trunk on Friday or Monday to let you enough
> time to review.
>
> Here is another patch fixing id-1.f90 that is a type conversion
> problem arising when expanding to RTL. I committed this to the
> graphite branch. Okay for trunk after regtest passes on amd64-linux?
The following (and similar cases) are clearly bogus:
else if (r->n == 2)
{
- left = clast_to_gcc_expression (r->elts[0], params,
ivstack);
- right = clast_to_gcc_expression (r->elts[1], params,
ivstack);
- return fold_build2 (MIN_EXPR, type, left, right);
+ tree tl = clast_to_gcc_expression (r->elts[0], params,
ivstack);
+ tree tr = clast_to_gcc_expression (r->elts[1], params,
ivstack);
+ tree type = max_precision_type (tl, tr);
+ return fold_build2 (MIN_EXPR, type, tl, tr);
}
you are inserting promotions (well, you are not - you miss
fold_converts to type for both arguments), but this is not your job
but the frontends.
Try the following patch to see if there are type issues with the
graphite.
Richard.
2008-09-11 Richard Guenther <rguenther@suse.de>
* tree-cfg.c (remove_useless_stmts): Verify stmts afterwards.
(verify_stmts): Dispatch to gimple/type verification code.
Index: trunk/gcc/tree-cfg.c
===================================================================
*** trunk.orig/gcc/tree-cfg.c
--- trunk/gcc/tree-cfg.c
*************** remove_useless_stmts (void)
*** 2024,2029 ****
--- 2024,2034 ----
remove_useless_stmts_1 (&gsi, &data);
}
while (data.repeat);
+
+ #ifdef ENABLE_TYPES_CHECKING
+ verify_types_in_gimple_seq (gimple_body (current_function_decl));
+ #endif
+
return 0;
}
*************** verify_stmts (void)
*** 4153,4158 ****
--- 4210,4221 ----
err |= true;
}
}
+
+ if (verify_gimple_phi (phi))
+ {
+ debug_gimple_stmt (phi);
+ err |= true;
+ }
}
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
*************** verify_stmts (void)
*** 4189,4194 ****
--- 4252,4263 ----
}
err |= verify_stmt (&gsi);
+
+ if (verify_types_in_gimple_stmt (gsi_stmt (gsi)))
+ {
+ debug_gimple_stmt (stmt);
+ err |= true;
+ }
addr = walk_gimple_op (gsi_stmt (gsi), verify_node_sharing, &wi);
if (addr)
{
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-03 19:48 ` Sebastian Pop
@ 2008-12-04 10:31 ` Richard Guenther
0 siblings, 0 replies; 14+ messages in thread
From: Richard Guenther @ 2008-12-04 10:31 UTC (permalink / raw)
To: Sebastian Pop
Cc: Jack Howarth, GCC Patches, Diego Novillo, Daniel Berlin, Sjodin,
Jan, Jagasia, Harsha, Christophe Harle, Tobias Grosser,
Albert Cohen, Konrad Trifunovic
On Wed, 3 Dec 2008, Sebastian Pop wrote:
> On Wed, Dec 3, 2008 at 1:33 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> > There are still 3 bugs left for building polyhedron benchmarks:
> > id-{2,3,4}.f90. I'm working on id-4.f90, Tobias and Dwarak are going
> > to work on id-3.f90 that is a fail in the scop detection: sd_region.
> >
>
> Here is the fix for id-4.f90. Committed to graphite branch, waiting for review
> to commit to trunk.
This is ok for trunk.
Richard.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-04 10:30 ` Richard Guenther
@ 2008-12-04 18:20 ` Sebastian Pop
2008-12-05 11:03 ` Richard Guenther
0 siblings, 1 reply; 14+ messages in thread
From: Sebastian Pop @ 2008-12-04 18:20 UTC (permalink / raw)
To: Richard Guenther
Cc: GCC Patches, Diego Novillo, Daniel Berlin, Sjodin, Jan, Jagasia,
Harsha, Christophe Harle, Tobias Grosser, Albert Cohen,
Konrad Trifunovic
On Thu, Dec 4, 2008 at 4:29 AM, Richard Guenther <rguenther@suse.de> wrote:
> Try the following patch to see if there are type issues with the
> graphite.
Yes this patch fails most of the testcases with graphite code gen.
I'm fixing these problems.
Why isn't this patch that makes the checker more strict in trunk right now?
Sebastian
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [patch][graphite] Rewrite of "out of graphite"
2008-12-04 18:20 ` Sebastian Pop
@ 2008-12-05 11:03 ` Richard Guenther
0 siblings, 0 replies; 14+ messages in thread
From: Richard Guenther @ 2008-12-05 11:03 UTC (permalink / raw)
To: Sebastian Pop
Cc: Richard Guenther, GCC Patches, Diego Novillo, Daniel Berlin,
Sjodin, Jan, Jagasia, Harsha, Christophe Harle, Tobias Grosser,
Albert Cohen, Konrad Trifunovic
On Thu, Dec 4, 2008 at 7:19 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Thu, Dec 4, 2008 at 4:29 AM, Richard Guenther <rguenther@suse.de> wrote:
>> Try the following patch to see if there are type issues with the
>> graphite.
>
> Yes this patch fails most of the testcases with graphite code gen.
> I'm fixing these problems.
>
> Why isn't this patch that makes the checker more strict in trunk right now?
Because it breaks too much ;) I plan do put it in for stage1.
Richard.
> Sebastian
>
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2008-12-05 11:03 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-12-03 7:55 [patch][graphite] Rewrite of "out of graphite" Sebastian Pop
2008-12-03 10:23 ` Richard Guenther
2008-12-03 18:45 ` Sebastian Pop
2008-12-03 18:58 ` Jack Howarth
2008-12-03 19:14 ` Tobias Grosser
2008-12-03 19:34 ` Sebastian Pop
2008-12-03 19:48 ` Sebastian Pop
2008-12-04 10:31 ` Richard Guenther
2008-12-04 1:09 ` Jack Howarth
2008-12-04 1:19 ` Sebastian Pop
2008-12-04 1:39 ` Jack Howarth
2008-12-04 10:30 ` Richard Guenther
2008-12-04 18:20 ` Sebastian Pop
2008-12-05 11:03 ` Richard Guenther
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).