[GSoC] Addition of __isl_give to declarations
This patch adds __isl_give to declarations of the following funcions: generate_isl_context, generate_isl_schedule, scop_to_isl_ast Is it fine for trunk? -- Cheers, Roman Gareev ChangeLog_entry Description: Binary data patch Description: Binary data
Re: [GSoC] Addition of ISL AST generation to Graphite
Sorry, I was going to fix this. Thank you very much! -- Cheers, Roman Gareev
Re: [GSoC] generation of Gimple loops with empty bodies
> Surprising. Is the symbol defined in libisl.so? You could use objdump to > check? If I am not mistaken, objdump shows that libisl.so contains it. objdump -d libisl.so.10.2.2 | grep isl_ast_expr_get_val 00060380 : 60383: 74 4b je 603d0 60389: 75 0d jne60398 Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212294) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -42,16 +42,549 @@ #include "cfgloop.h" #include "tree-data-ref.h" #include "sese.h" +#include "tree-ssa-loop-manip.h" +#include "tree-scalar-evolution.h" +#include #ifdef HAVE_cloog #include "graphite-poly.h" #include "graphite-isl-ast-to-gimple.h" +#include "graphite-htab.h" /* This flag is set when an error occurred during the translation of ISL AST to Gimple. */ static bool graphite_regenerate_error; +/* We always use signed 128, until isl is able to give information about +types */ + +static tree *graphite_expression_size_type = &int128_integer_type_node; + +/* Converts a GMP constant VAL to a tree and returns it. */ + +static tree +gmp_cst_to_tree (tree type, mpz_t val) +{ + tree t = type ? type : integer_type_node; + mpz_t tmp; + + mpz_init (tmp); + mpz_set (tmp, val); + wide_int wi = wi::from_mpz (t, tmp, true); + mpz_clear (tmp); + + return wide_int_to_tree (t, wi); +} + +/* Verifies properties that GRAPHITE should maintain during translation. */ + +static inline void +graphite_verify (void) +{ +#ifdef ENABLE_CHECKING + verify_loop_structure (); + verify_loop_closed_ssa (true); +#endif +} + +/* The comparison function for ivs_params_map */ + +struct id_comp +{ + bool operator()(isl_id *id1, isl_id *id2) const + { +const char *name1 = isl_id_get_name (id1); +const char *name2 = isl_id_get_name (id2); +return strcmp (name1, name2) == 0; + } +}; + +/* IVS_PARAMS_MAP maps ISL's scattering and parameter identifiers + to corresponding trees. */ + +typedef struct ivs_params { + std::map ivs_params_map; + sese region; +} *ivs_params_p; + +/* Free all memory allocated for ISL's identifiers. */ + +void ivs_params_clear (ivs_params_p ip) +{ + std::map::iterator it; + for (it = ip->ivs_params_map.begin (); it != ip->ivs_params_map.end (); it++) +{ + isl_id_free (it->first); +} +} + +static tree +gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *, + ivs_params_p ip); + +/* Returns the tree variable from the name of isl_id, which is stored + in the isl_ast_expr EXPR_ID that was given in ISL representation. */ + +static tree +gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id, +ivs_params_p ip) +{ + gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id); + isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id); + std::map::iterator res; + res = ip->ivs_params_map.find (tmp_isl_id); + isl_id_free (tmp_isl_id); + gcc_assert (res != ip->ivs_params_map.end ()); + return res->second; +} + +/* Converts a isl_ast_expr_int expression E to a GCC expression tree of + type TYPE. */ + +static tree +gcc_expression_from_isl_expr_int (tree type, __isl_keep isl_ast_expr *expr) +{ + gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int); + isl_int val; + isl_int_init (val); + if (isl_ast_expr_get_int (expr, &val) == -1) +{ + isl_int_clear (val); + return NULL_TREE; +} + else +return gmp_cst_to_tree (type, val); +} + +/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of + type TYPE. */ + +static tree +binary_op_to_tree (tree type, __isl_keep isl_ast_expr *expr, ivs_params_p ip) +{ + isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); + tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); + isl_ast_expr_free (arg_expr); + arg_expr = isl_ast_expr_get_op_arg (expr, 1); + tree tree_rhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); + isl_ast_expr_free (arg_expr); + switch (isl_ast_expr_get_op_type (expr)) +{ +case isl_ast_op_add: + return fold_build2 (PLUS_EXPR, type, tree_lhs_expr, tree_rhs_expr); + +case isl_ast_op_sub: + return fold_build2 (MINUS_EXPR, type, tree_lhs_expr, tree_rhs_expr); + +case isl_ast_op_mul: + return fold_build2 (MULT_EXPR, type, tree_lhs_expr, tree_rhs_expr); + +case isl_ast_op_div: + return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); + +case isl_ast_op_fdiv_q: + return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); + +case isl_ast_op_and: + return fold_build2 (TRUTH_ANDIF_EXPR, type, + tree_lhs_expr, tree_rhs_expr); + +case isl_ast_op_or: + return fold_build2 (TRUTH_ORIF_EXPR, type, tree_lhs_expr, tree_rhs_expr); + +case isl_ast_op_e
Re: [GSoC] Addition of __isl_give to declarations
> The ChangeLog should be per-function. Otherwise LGTM. I've fixed this. -- Cheers, Roman Gareev 2014-07-04 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c (generate_isl_context): Add __isl_give to the declaration. (generate_isl_schedule): Likewise. (scop_to_isl_ast): Likewise.
Re: [GSoC] generation of Gimple loops with empty bodies
> I would use -x to see the headers. This should tell you if it is defined > or only used there. It gives the following output: roman@roman-System-Product-Name:~/isl-0.12.2/lib$ objdump -x libisl.so.10.2.2 | grep isl_ast_expr_get_val 00060380 g F .text 0053 isl_ast_expr_get_val > Sorry, but this still needs to be debugged. :-( I am too busy to do it > myself, so i am afraid you may just need to dig into it yourself. :-( I've found the reason of this error. Somehow cc1 used an older version of isl provided by the package from the standard repository in spite of manually selected paths to isl 0.12.2. I think it is better to move on and not to concentrate on this. >> +#include "graphite-htab.h" > > Is this still needed? No, this is redundant. >> +/* IVS_PARAMS_MAP maps ISL's scattering and parameter identifiers >> + to corresponding trees. */ >> +typedef struct ivs_params { >> + std::map ivs_params_map; > > What about calling it isl_id_to_tree? Maybe it would be better to call it tree_from_isl_id (because it would help to avoid confusion with definitions from isl)? >> + sese region; > > Is this region needed? No, this is redundant. >> + We create a new if region protecting the loop to be executed, if >> + the execution count is zero (lower bound > upper bound). In this case, >> + it is subsequently removed by dead code elimination. */ > > > The last sentence is unclear. Are you saying the loop will be removed or > that the condition will be removed in case it is always true. Also, what > about cases where the condition remains? I wanted to say that the loop will be removed. Maybe it would be better to remove the last sentence at all (because the previous sentence already explains the motivation)? > Those changes are unrelated and are part of the other patch, right? Yes, these changes were made in the revision under No. 212361. >> + ip.region = region; > > Is this needed? ip.region seems unused. Yes, this is redundant. I tried to incorporate all your comments in the attached patch. -- Cheers, Roman Gareev. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212361) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -25,7 +25,14 @@ #include #include #include +#if defined(__cplusplus) +extern "C" { #endif +#include +#if defined(__cplusplus) +} +#endif +#endif #include "system.h" #include "coretypes.h" @@ -42,6 +49,9 @@ #include "cfgloop.h" #include "tree-data-ref.h" #include "sese.h" +#include "tree-ssa-loop-manip.h" +#include "tree-scalar-evolution.h" +#include #ifdef HAVE_cloog #include "graphite-poly.h" @@ -52,6 +62,517 @@ static bool graphite_regenerate_error; +/* We always use signed 128, until isl is able to give information about +types */ + +static tree *graphite_expression_size_type = &int128_integer_type_node; + +/* Converts a GMP constant VAL to a tree and returns it. */ + +static tree +gmp_cst_to_tree (tree type, mpz_t val) +{ + tree t = type ? type : integer_type_node; + mpz_t tmp; + + mpz_init (tmp); + mpz_set (tmp, val); + wide_int wi = wi::from_mpz (t, tmp, true); + mpz_clear (tmp); + + return wide_int_to_tree (t, wi); +} + +/* Verifies properties that GRAPHITE should maintain during translation. */ + +static inline void +graphite_verify (void) +{ +#ifdef ENABLE_CHECKING + verify_loop_structure (); + verify_loop_closed_ssa (true); +#endif +} + +/* TREE_FROM_ISL_ID maps ISL's scattering and parameter identifiers + to corresponding trees. */ + +typedef struct ivs_params { + std::map tree_from_isl_id; +} *ivs_params_p; + +/* Free all memory allocated for ISL's identifiers. */ + +void ivs_params_clear (ivs_params_p ip) +{ + std::map::iterator it; + for (it = ip->tree_from_isl_id.begin (); + it != ip->tree_from_isl_id.end (); it++) +{ + isl_id_free (it->first); +} +} + +static tree +gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *, + ivs_params_p ip); + +/* Return the tree variable that corresponds to the given isl ast identifier + expression (an isl_ast_expr of type isl_ast_expr_id). */ + +static tree +gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id, +ivs_params_p ip) +{ + gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id); + isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id); + std::map::iterator res; + res = ip->tree_from_isl_id.find (tmp_isl_id); + isl_id_free (tmp_isl_id); + gcc_assert (res != ip->tree_from_isl_id.end () && +
Re: [GSoC] generation of Gimple loops with empty bodies
> The struct now contains only a single element such that there seems to be no > need for it anymore. Should we remove it? (We could still use a typedef if > you believe the datatype is too long). I don't mind removing it. However I think that we should choose the way of transferring of sese region, which is used for translation of an isl_ast_node_user to Gimple code. Should we transfer it separately or restore ivs_params later? What do you think? -- Cheers, Roman Gareev.
Re: [GSoC] generation of Gimple loops with empty bodies
I've attached an improved version of the patch and the ChangeLog entry. Are they fine for trunk? -- Cheers, Roman Gareev. 2014-07-11 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c (gmp_cst_to_tree): New function. (graphite_verify): New function. (ivs_params_clear): New function. (gcc_expression_from_isl_ast_expr_id): New function. (gcc_expression_from_isl_expr_int): New function. (binary_op_to_tree): New function. (ternary_op_to_tree): New function. (unary_op_to_tree): New function. (nary_op_to_tree): New function. (gcc_expression_from_isl_expr_op): New function. (gcc_expression_from_isl_expression): New function. (graphite_create_new_loop): New function. (translate_isl_ast_for_loop): New function. (get_upper_bound): New function. (graphite_create_new_loop_guard): New function. (translate_isl_ast_node_for): New function. (translate_isl_ast): New function. (add_parameters_to_ivs_params): New function. (scop_to_isl_ast): New parameter ip. (graphite_regenerate_ast_isl): Add generation of GIMPLE code. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212450) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -25,7 +25,14 @@ #include #include #include +#if defined(__cplusplus) +extern "C" { #endif +#include +#if defined(__cplusplus) +} +#endif +#endif #include "system.h" #include "coretypes.h" @@ -42,6 +49,9 @@ #include "cfgloop.h" #include "tree-data-ref.h" #include "sese.h" +#include "tree-ssa-loop-manip.h" +#include "tree-scalar-evolution.h" +#include #ifdef HAVE_cloog #include "graphite-poly.h" @@ -52,6 +62,515 @@ static bool graphite_regenerate_error; +/* We always use signed 128, until isl is able to give information about +types */ + +static tree *graphite_expression_size_type = &int128_integer_type_node; + +/* Converts a GMP constant VAL to a tree and returns it. */ + +static tree +gmp_cst_to_tree (tree type, mpz_t val) +{ + tree t = type ? type : integer_type_node; + mpz_t tmp; + + mpz_init (tmp); + mpz_set (tmp, val); + wide_int wi = wi::from_mpz (t, tmp, true); + mpz_clear (tmp); + + return wide_int_to_tree (t, wi); +} + +/* Verifies properties that GRAPHITE should maintain during translation. */ + +static inline void +graphite_verify (void) +{ +#ifdef ENABLE_CHECKING + verify_loop_structure (); + verify_loop_closed_ssa (true); +#endif +} + +/* IVS_PARAMS maps ISL's scattering and parameter identifiers + to corresponding trees. */ + +typedef std::map ivs_params; + +/* Free all memory allocated for ISL's identifiers. */ + +void ivs_params_clear (ivs_params &ip) +{ + std::map::iterator it; + for (it = ip.begin (); + it != ip.end (); it++) +{ + isl_id_free (it->first); +} +} + +static tree +gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *, + ivs_params &ip); + +/* Return the tree variable that corresponds to the given isl ast identifier + expression (an isl_ast_expr of type isl_ast_expr_id). */ + +static tree +gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id, +ivs_params &ip) +{ + gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id); + isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id); + std::map::iterator res; + res = ip.find (tmp_isl_id); + isl_id_free (tmp_isl_id); + gcc_assert (res != ip.end () && + "Could not map isl_id to tree expression"); + isl_ast_expr_free (expr_id); + return res->second; +} + +/* Converts an isl_ast_expr_int expression E to a GCC expression tree of + type TYPE. */ + +static tree +gcc_expression_from_isl_expr_int (tree type, __isl_take isl_ast_expr *expr) +{ + gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_int); + isl_val *val = isl_ast_expr_get_val (expr); + mpz_t val_mpz_t; + mpz_init (val_mpz_t); + tree res; + if (isl_val_get_num_gmp (val, val_mpz_t) == -1) +res = NULL_TREE; + else +res = gmp_cst_to_tree (type, val_mpz_t); + isl_val_free (val); + isl_ast_expr_free (expr); + mpz_clear (val_mpz_t); + return res; +} + +/* Converts a binary isl_ast_expr_op expression E to a GCC expression tree of + type TYPE. */ + +static tree +binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) +{ + isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); + tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); + arg_expr = isl_ast_expr_get_op_arg (expr, 1); + tree tree_rhs_expr = gcc_expression_from_isl_expression (type, ar
[GSoC] generation of Gimple code from isl_ast_node_user
I've attached the patch, which contains generation of Gimple code from isl_ast_node_user. I think that it would be better to add motivation for the following line from the original source: if (GBB_BB (gbb) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) { isl_ast_expr_free (user_expr); return next_e; } Do you know anything about this? -- Cheers, Roman Gareev. 2014-07-12 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: Add inclusion of gimple-ssa.h, tree-into-ssa.h. (ivs_params_clear): Pass ivs_params_p ip instead of ivs_params &ip. (gcc_expression_from_isl_expression): Likewise. (gcc_expression_from_isl_ast_expr_id): Likewise. (binary_op_to_tree): Likewise. (ternary_op_to_tree): Likewise. (unary_op_to_tree): Likewise. (nary_op_to_tree): Likewise. (gcc_expression_from_isl_expr_op): Likewise. (graphite_create_new_loop): Likewise. (translate_isl_ast_for_loop): Pass ivs_params_p ip instead of ivs_params &ip. Add passing of bb_pbb_htab_type *bb_pbb_mapping. (translate_isl_ast_node_for): Likewise. (build_iv_mapping): New function. (mark_bb_with_pbb): Likewise. (translate_isl_ast_node_user): Likewise. (translate_isl_ast): Pass ivs_params_p ip instead of ivs_params &ip. Add passing of bb_pbb_htab_type *bb_pbb_mapping. (add_parameters_to_ivs_params): Pass ivs_params_p ip instead of ivs_params &ip. (scop_to_isl_ast): Likewise. (graphite_regenerate_ast_isl): Add passing of bb_pbb_htab_type *bb_pbb_mapping. * graphite-isl-ast-to-gimple.h: Add inclusion of the graphite-htab.h. * graphite.c (graphite_transform_loops): Add passing of &bb_pbb_mapping to graphite_regenerate_ast_isl. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212455) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -51,11 +51,14 @@ #include "sese.h" #include "tree-ssa-loop-manip.h" #include "tree-scalar-evolution.h" +#include "gimple-ssa.h" +#include "tree-into-ssa.h" #include #ifdef HAVE_cloog #include "graphite-poly.h" #include "graphite-isl-ast-to-gimple.h" +#include "graphite-htab.h" /* This flag is set when an error occurred during the translation of ISL AST to Gimple. */ @@ -94,18 +97,21 @@ #endif } -/* IVS_PARAMS maps ISL's scattering and parameter identifiers +/* TREE_FROM_ISL_ID maps ISL's scattering and parameter identifiers to corresponding trees. */ -typedef std::map ivs_params; +typedef struct ivs_params { + std::map tree_from_isl_id; + sese region; +} *ivs_params_p; /* Free all memory allocated for ISL's identifiers. */ -void ivs_params_clear (ivs_params &ip) +void ivs_params_clear (ivs_params_p ip) { std::map::iterator it; - for (it = ip.begin (); - it != ip.end (); it++) + for (it = ip->tree_from_isl_id.begin (); + it != ip->tree_from_isl_id.end (); it++) { isl_id_free (it->first); } @@ -113,21 +119,21 @@ static tree gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *, - ivs_params &ip); + ivs_params_p ip); /* Return the tree variable that corresponds to the given isl ast identifier expression (an isl_ast_expr of type isl_ast_expr_id). */ static tree gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id, -ivs_params &ip) +ivs_params_p ip) { gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id); isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id); std::map::iterator res; - res = ip.find (tmp_isl_id); + res = ip->tree_from_isl_id.find (tmp_isl_id); isl_id_free (tmp_isl_id); - gcc_assert (res != ip.end () && + gcc_assert (res != ip->tree_from_isl_id.end () && "Could not map isl_id to tree expression"); isl_ast_expr_free (expr_id); return res->second; @@ -158,7 +164,7 @@ type TYPE. */ static tree -binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) +binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip) { isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); @@ -214,7 +220,7 @@ type TYPE. */ static tree -ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) +ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip) { gcc_assert (isl_ast_expr_get_op_type (expr) == isl_a
Re: [GSoC] generation of Gimple loops with empty bodies
Hi Dominique, thank you for the message! I've attached a patch, that may fix the issue. Please report back if it fixes the problem. -- Cheers, Roman Gareev. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212491) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -65,7 +65,9 @@ /* We always use signed 128, until isl is able to give information about types */ -static tree *graphite_expression_size_type = &int128_integer_type_node; +static tree *graphite_expression_size_type = int128_integer_type_node ? +&int128_integer_type_node : +&long_long_integer_type_node; /* Converts a GMP constant VAL to a tree and returns it. */
Re: [GSoC] generation of Gimple code from isl_ast_node_user
> No, no idea. To my understanding the entry block should not even appear > within a scop (see build_scops, where we only start detecting scops at > the successor of the entry_block). Maybe we replace this with an assert > to get a good error message in case I have missed something. Yes, I think this would be a good solution at this moment. > I think this region is actually not needed. At the place where you need > it, you have a pbb available, from which you can obtain a pointer to the > surrounding scop and from this you can obtain this region itself. Yes, this is redundant. > This is a pure style change which seems unrelated. Also, is the original > line really too long? I may have miscounted, but it seems to fit > exactly. If I am not mistaken, lines should be limited to 80 characters, according to conventions, which are mentioned here https://gcc.gnu.org/wiki/CppConventions. This line contains 81 characters. > In polly we just create an iv_map from [0, max-loop-depth-within-scop], so > it contains at most as many elements as the maximal loop depth. Your map > is unnecessarily large, as it contains all loops in the function. > > If we can avoid this immediately, e.g. by indexing according to the > loop-depths that would be great. On the other side, if the existing > functions require this, I propose to not touch this area, but to add a > fixme that documents this issue. We can solve it after having removed > the CLooG codegen. If I am not mistaken, the existing function doesn't require that iv_map contains at most as many elements as the maximal loop depth. (If we consider chrec_apply_map (I think that it is the only function, which works with iv_map), we'll see that it calls chrec_apply when the expression is not NULL. In our case, we push NULL_TREEs into iv_map to extend its size to the maximal loop depth. They aren't considered, because tree NULL_TREE is equivalent to NULL, according to tree.h) Maybe we could use a number of the innermost loop that contains the basic block gbb. If I am not mistaken, outer loops considered in build_iv_mapping have smaller numbers than it. What do you think about this? > I was just briefly looking the code to remind me what this > bb_pbb_mapping hash table is about, but could not find the reason it is > needed. Do you know why it is needed? > > Is it necessary for this patch? Or did you just copy it from the > previous code generation? Yes, I've forgotten to remove this. If I am not mistaken, bb_pbb_mapping is used for checking for the loop parallelism in graphite-clast-to-gimple.c. > Why do you need to first push NULL_TREEs into this vec, which will be > overwritten right after? In the current implementation, we'll get the error “internal compiler error: in operator[], at vec.h:736”, if we try to assign a value to iv_map via [] and remove initial pushing of NULL_TREEs. We could push new values into iv_map in build_iv_mapping, but I am not sure if there are cases, which require special processing (for example, NULL_TREEs should be pushed into iv_map before the next old_loop->num. Possibly, there are no such cases.). > It is unclear how this patches have been tested. Can you elaborate? I've compared the result of Gimple code generation (I've attached them to the letter) for the following examples: int main (int n, int *a) { int i; for (i = n; i < 100; i++) a[i] = i; return 0; } int main (int 0, int *a) { int i; for (i = n; i < 100; i++) a[i] = i; return 0; } > Also, we need to find a way to test this in gcc itself, possibly by > running test cases that already work with both the cloog and the isl ast > generator. Maybe we could choose the strategy, which was used in /gcc/testsuite/gcc.dg/graphite/interchange-1.c, /gcc/testsuite/gcc.dg/graphite/interchange-mvt.c, /gcc/testsuite/gcc.dg/graphite/run-id-5.c? (The result of the transformed function is compared to the assumed value and the abort function is called in case of inequality.) What do you think about this? -- Cheers, Roman Gareev. 2014-07-12 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: Add inclusion of gimple-ssa.h, tree-into-ssa.h. (ivs_params_clear): (build_iv_mapping): New function. (translate_isl_ast_node_user): Likewise. (translate_isl_ast): Add calling of translate_isl_ast_node_user. loop_0 (header = 0, latch = 1, niter = ) { bb_2 (preds = {bb_0 }, succs = {bb_3 }) { : } bb_5 (preds = {bb_3 }, succs = {bb_1 }) { : # .MEM_18 = PHI <.MEM_11(3)> # VUSE <.MEM_18> return 0; } loop_2 (header = 3, latch = 4, niter = ) { bb_3 (preds = {bb_2 bb_4 }, succs = {bb_4 bb_5 }) { : # graphite_IV.3_1 = PHI <0(2), graphite_IV.3_14(4)> # .MEM_19 = PHI <.MEM_3(D)(
Re: [GSoC] Addition of ISL AST generation to Graphite
> I'm seeing the error: > > gcc/graphite-isl-ast-to-gimple.c:31:25: warning: isl/val_gmp.h: No such file > or directory > > when building for aarch64. > > isl/val_gmp.h is included in 0.12 AFAICS so perhaps we should demand 0.12 > instead of 0.11 ? According to isl's ChangeLog, isl_val abstraction was added in version 0.12. Therefore, I think it would be right to demand on 0.12. Tobias, what do you think about this? Is this fine for the backend, which uses CLooG to generate Gimple code? -- Cheers, Roman Gareev
Re: [GSoC] generation of Gimple loops with empty bodies
I've found out that int128_integer_type_node and long_long_integer_type_node are NULL at the moment of definition of the graphite_expression_size_type. Maybe we should use long_long_integer_type_node, because, as you said before, using of signed 64 has also been proved to be very robust. What do you think about this? -- Cheers, Roman Gareev.
Re: [GSoC] Addition of ISL AST generation to Graphite
> Could you prepare such a patch? Yes, I've started working on it. I have a question about isl. Can we require that isl is always compiled with GMP support? -- Cheers, Roman Gareev
Re: [GSoC] generation of Gimple code from isl_ast_node_user
> I see. Could you use vec_safe_grow_cleared(iv_map, loop_num) instead? > This shows probably better that you zero initialize the vector. If I am not mistaken, vec_safe_grow_cleared has the following declaration: vec_safe_grow_cleared (vec *&v, unsigned len CXX_MEM_STAT_INFO) Should we rewrite all the functions, which interact with iv_map? I've added test cases, which produce the following ISL code: isl-ast-gen-single-loop-1.c for (int c1 = 0; c1 <= 49; c1 += 1) S_3(c1); isl-ast-gen-single-loop-2.c for (int c1 = 0; c1 <= -n.0 + 69; c1 += 1) S_5(c1); isl-ast-gen-single-loop-3.c for (int c1 = 0; c1 < n.0; c1 += 1) S_5(c1); The second and the third one use arrays. I wanted to make them similar to the first one, but inability to handle blocks prevented this. For example, /* { dg-do run } */ /* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ int n = 25; int foo () { int i, res; for (i = n, res = 0; i < 50; i++) res += i; return res; } extern void abort (); int main (void) { int res = foo (); if (res != 1225) abort (); return 0; } produces the following code: { S_6(); for (int c1 = 0; c1 <= -i + 49; c1 += 1) S_4(c1); } 2014-07-12 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: Add inclusion of gimple-ssa.h, tree-into-ssa.h. (ivs_params_clear): (build_iv_mapping): New function. (translate_isl_ast_node_user): Likewise. (translate_isl_ast): Add calling of translate_isl_ast_node_user. gcc/testsuite/gcc.dg/graphite/ * isl-ast-gen-single-loop-1.c: New testcase. * isl-ast-gen-single-loop-2.c: New testcase. * isl-ast-gen-single-loop-3.c: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212756) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -51,6 +51,8 @@ #include "sese.h" #include "tree-ssa-loop-manip.h" #include "tree-scalar-evolution.h" +#include "gimple-ssa.h" +#include "tree-into-ssa.h" #include #ifdef HAVE_cloog @@ -541,6 +543,72 @@ return last_e; } +/* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction + variables of the loops around GBB in SESE. + + FIXME: Instead of using a vec that maps each loop id to a possible + chrec, we could consider using a map that maps loop ids to the + corresponding tree expressions. */ + +static void +build_iv_mapping (vec iv_map, gimple_bb_p gbb, + __isl_keep isl_ast_expr *user_expr, ivs_params &ip, + sese region) +{ + gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op && + isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call); + int i; + isl_ast_expr *arg_expr; + for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++) +{ + arg_expr = isl_ast_expr_get_op_arg (user_expr, i); + tree type = *graphite_expression_size_type; + tree t = gcc_expression_from_isl_expression (type, arg_expr, ip); + loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1); + iv_map[old_loop->num] = t; +} + +} + +/* Translates an isl_ast_node_user to Gimple. */ + +static edge +translate_isl_ast_node_user (__isl_keep isl_ast_node *node, +edge next_e, ivs_params &ip) +{ + gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user); + isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node); + isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0); + gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id); + isl_id *name_id = isl_ast_expr_get_id (name_expr); + poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id); + gcc_assert (pbb); + gimple_bb_p gbb = PBB_BLACK_BOX (pbb); + vec iv_map; + isl_ast_expr_free (name_expr); + isl_id_free (name_id); + + gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) && + "The entry block should not even appear within a scop"); + + loop_p loop = gbb_loop (gbb); + iv_map.create (loop->num + 1); + int i; + for (i = 0; i < loop->num + 1; i++) +iv_map.quick_push (NULL_TREE); + + build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop)); + isl_ast_expr_free (user_expr); + next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), + SCOP_REGION (pbb->scop), next_e, + iv_map, + &graphite_regenerate_error); + iv_map.release (); + mark_virtual_operands_for_renaming (cfun); + update_ssa (TODO_update_ssa); + return next_e; +} + /* Translates an ISL AST node NODE to GCC representation in the context of a SESE. */ @@ -561,7 +629,7 @@ return n
Re: [GSoC] Addition of ISL AST generation to Graphite
I've attached the patch, which adds the requirement for isl 0.12. Tobias, is it important to accept only 0.12.1, 0.12.2 and forbid 0.12? -- Cheers, Roman Gareev 2014-07-12 Roman Gareev * configure.ac: Don't accept isl 0.11. * configure: Regenerate. Index: configure === --- configure (revision 212756) +++ configure (working copy) @@ -5898,54 +5898,6 @@ LDFLAGS="${_isl_saved_LDFLAGS} ${isllibs}" LIBS="${_isl_saved_LIBS} -lisl" -{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for version 0.11 of ISL" >&5 -$as_echo_n "checking for version 0.11 of ISL... " >&6; } -if test "$cross_compiling" = yes; then : - gcc_cv_isl=yes -else - cat confdefs.h - <<_ACEOF >conftest.$ac_ext -/* end confdefs.h. */ -#include - #include -int -main () -{ -if (strncmp (isl_version (), "isl-0.11", strlen ("isl-0.11")) != 0) - return 1; - - ; - return 0; -} -_ACEOF -if ac_fn_c_try_run "$LINENO"; then : - gcc_cv_isl=yes -else - gcc_cv_isl=no -fi -rm -f core *.core core.conftest.* gmon.out bb.out conftest$ac_exeext \ - conftest.$ac_objext conftest.beam conftest.$ac_ext -fi - -{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $gcc_cv_isl" >&5 -$as_echo "$gcc_cv_isl" >&6; } - -CFLAGS=$_isl_saved_CFLAGS -LDFLAGS=$_isl_saved_LDFLAGS -LIBS=$_isl_saved_LIBS - fi - - - if test "${gcc_cv_isl}" = no ; then - - if test "${ENABLE_ISL_CHECK}" = yes ; then -_isl_saved_CFLAGS=$CFLAGS -_isl_saved_LDFLAGS=$LDFLAGS -_isl_saved_LIBS=$LIBS - -CFLAGS="${_isl_saved_CFLAGS} ${islinc} ${gmpinc}" -LDFLAGS="${_isl_saved_LDFLAGS} ${isllibs}" -LIBS="${_isl_saved_LIBS} -lisl" - { $as_echo "$as_me:${as_lineno-$LINENO}: checking for version 0.12 of ISL" >&5 $as_echo_n "checking for version 0.12 of ISL... " >&6; } if test "$cross_compiling" = yes; then : @@ -5983,7 +5935,6 @@ fi - fi Index: configure.ac === --- configure.ac(revision 212756) +++ configure.ac(working copy) @@ -1650,10 +1650,7 @@ dnl with user input. ISL_INIT_FLAGS dnl The versions of ISL that work for Graphite - ISL_CHECK_VERSION(0,11) - if test "${gcc_cv_isl}" = no ; then -ISL_CHECK_VERSION(0,12) - fi + ISL_CHECK_VERSION(0,12) dnl Only execute fail-action, if ISL has been requested. ISL_IF_FAILED([ AC_MSG_ERROR([Unable to find a usable ISL. See config.log for details.])])
Re: [GSoC] generation of Gimple code from isl_ast_node_user
> Can you explain why all functions would need to be rewritten? I proposed > this function as an easier way to NULL initialize the vector and did not > expect any rewrite to be necessary. > > If there is no such thing, please just add a comment that your loop NULL > initializes the vector. We can later improve this. Sorry, I, probably, mixed something up. This function was used in the attached patch without rewriting of other functions. -- Cheers, Roman Gareev. 2014-07-12 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: Add inclusion of gimple-ssa.h, tree-into-ssa.h. (ivs_params_clear): (build_iv_mapping): New function. (translate_isl_ast_node_user): Likewise. (translate_isl_ast): Add calling of translate_isl_ast_node_user. gcc/testsuite/gcc.dg/graphite/ * isl-ast-gen-single-loop-1.c: New testcase. * isl-ast-gen-single-loop-2.c: New testcase. * isl-ast-gen-single-loop-3.c: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212807) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -51,6 +51,8 @@ #include "sese.h" #include "tree-ssa-loop-manip.h" #include "tree-scalar-evolution.h" +#include "gimple-ssa.h" +#include "tree-into-ssa.h" #include #ifdef HAVE_cloog @@ -541,6 +543,70 @@ return last_e; } +/* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction + variables of the loops around GBB in SESE. + + FIXME: Instead of using a vec that maps each loop id to a possible + chrec, we could consider using a map that maps loop ids to the + corresponding tree expressions. */ + +static void +build_iv_mapping (vec iv_map, gimple_bb_p gbb, + __isl_keep isl_ast_expr *user_expr, ivs_params &ip, + sese region) +{ + gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op && + isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call); + int i; + isl_ast_expr *arg_expr; + for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++) +{ + arg_expr = isl_ast_expr_get_op_arg (user_expr, i); + tree type = *graphite_expression_size_type; + tree t = gcc_expression_from_isl_expression (type, arg_expr, ip); + loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1); + iv_map[old_loop->num] = t; +} + +} + +/* Translates an isl_ast_node_user to Gimple. */ + +static edge +translate_isl_ast_node_user (__isl_keep isl_ast_node *node, +edge next_e, ivs_params &ip) +{ + gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user); + isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node); + isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0); + gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id); + isl_id *name_id = isl_ast_expr_get_id (name_expr); + poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id); + gcc_assert (pbb); + gimple_bb_p gbb = PBB_BLACK_BOX (pbb); + vec iv_map; + isl_ast_expr_free (name_expr); + isl_id_free (name_id); + + gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) && + "The entry block should not even appear within a scop"); + + loop_p loop = gbb_loop (gbb); + iv_map.create (loop->num + 1); + iv_map.safe_grow_cleared (loop->num + 1); + + build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop)); + isl_ast_expr_free (user_expr); + next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), + SCOP_REGION (pbb->scop), next_e, + iv_map, + &graphite_regenerate_error); + iv_map.release (); + mark_virtual_operands_for_renaming (cfun); + update_ssa (TODO_update_ssa); + return next_e; +} + /* Translates an ISL AST node NODE to GCC representation in the context of a SESE. */ @@ -561,7 +627,7 @@ return next_e; case isl_ast_node_user: - return next_e; + return translate_isl_ast_node_user (node, next_e, ip); case isl_ast_node_block: return next_e; Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-single-loop-1.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-single-loop-1.c (revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-single-loop-1.c (working copy) @@ -0,0 +1,28 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +int n = 25; + +int +foo () +{ + int i, res; + + for (i = n, res = 0; i < 50; i++) + res += i; + + return res; +} + +extern void abort (); + +int +main (void) +{
Re: [GSoC] generation of Gimple loops with empty bodies
> I suggest you use the largest available integer mode via > mode = mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0); > type = build_nonstandard_integer_type (GET_MODE_PRECISION (mode), [01]); Thank you for the suggestion! > Roman, can you give this a shot? Maybe, we could use the following code: static int max_mode_int_precision = GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0)); static int graphite_expression_type_precision = 128 <= max_mode_int_precision ? 128 : max_mode_int_precision; This allows us to change the size during debugging and avoid using unacceptable mode size. Tobias, what do you think about this? -- Cheers, Roman Gareev 2014-07-08 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: Add using of build_nonstandard_integer_type instead of int128_integer_type_node. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212804) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -62,10 +62,13 @@ static bool graphite_regenerate_error; -/* We always use signed 128, until isl is able to give information about -types */ +/* We always use signed 128, until it is not accpeted or isl is able to give + information about types. */ -static tree *graphite_expression_size_type = &int128_integer_type_node; +static int max_mode_int_precision = + GET_MODE_PRECISION (mode_for_size (MAX_FIXED_MODE_SIZE, MODE_INT, 0)); +static int graphite_expression_type_precision = 128 <= max_mode_int_precision ? + 128 : max_mode_int_precision; /* Converts a GMP constant VAL to a tree and returns it. */ @@ -494,7 +497,8 @@ tree cond_expr; edge exit_edge; - *type = *graphite_expression_size_type; + *type = +build_nonstandard_integer_type (graphite_expression_type_precision, 0); isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for); *lb = gcc_expression_from_isl_expression (*type, for_init, ip); isl_ast_expr *upper_bound = get_upper_bound (node_for);
Re: [GSoC] generation of Gimple code from isl_ast_node_user
> One of these two seems redundant. I get the following error without “iv_map.create (loop->num + 1);”: "/home/roman/sec_trunk/gcc/gcc/vec.h:1184:39: error: ‘iv_map’ may be used uninitialized in this function [-Werror=maybe-uninitialized] { return m_vec ? m_vec->length () : 0; }" >Can you explain why all functions would need to be rewritten? I proposed this >function as an easier way to NULL initialize the vector and did not expect any >rewrite to be necessary. When I'm trying to pass iv_map to vec_safe_grow_cleared I get the following error: "/home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:596:47: note: mismatched types ‘vec*’ and ‘vec’ vec_safe_grow_cleared (iv_map, loop->num + 1);" In case of passing of iv_map*, I get the following error: "/home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:596:47: error: no matching function for call to ‘vec_safe_grow_cleared(vec*&, int)’ vec_safe_grow_cleared (iv_map, loop->num + 1); /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:596:47: note: candidate is: In file included from /home/roman/sec_trunk/gcc/gcc/tree-core.h:27:0, from /home/roman/sec_trunk/gcc/gcc/tree.h:23, from /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:39: /home/roman/sec_trunk/gcc/gcc/vec.h:627:1: note: template void vec_safe_grow_cleared(vec*&, unsigned int) vec_safe_grow_cleared (vec *&v, unsigned len CXX_MEM_STAT_INFO) /home/roman/sec_trunk/gcc/gcc/vec.h:627:1: note: template argument deduction/substitution failed: /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:596:47: note: mismatched types ‘vl_embed’ and ‘vl_ptr’ vec_safe_grow_cleared (iv_map, loop->num + 1); /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:596:47: note: ‘vec’ is not derived from ‘vec’" If we use vec as a type for iv_map, we'll have to rewrite declarations of the following functions, which are working with vec:copy_bb_and_scalar_dependences, graphite_copy_stmts_from_block, rename_uses, chrec_apply_map. We'll also have to rewrite declarations of iv_map in graphite-clast-to-gimple.c in this case. Please correct me, if I am wrong. -- Cheers, Roman Gareev.
Re: [GSoC] Addition of ISL AST generation to Graphite
> I am not aware of any problems with isl 0.12 and would be surprised if such > problems exist. Are you? I'm not aware of them, too. > P.S: As Richard suggested, we may also want to forbid CLooG 0.17. I've attached the patch, which adds the requirement for ClooG 0.18.1. Is it fine for trunk? -- Cheers, Roman Gareev. 2014-07-20 Roman Gareev * configure.ac: Accept only CLooG 0.18.1. * configure: Regenerate. Index: configure === --- configure (revision 212861) +++ configure (working copy) @@ -6031,8 +6031,8 @@ CFLAGS="${_cloog_saved_CFLAGS} ${clooginc} ${islinc} ${gmpinc}" LDFLAGS="${_cloog_saved_LDFLAGS} ${clooglibs} ${isllibs} ${gmplib}" -{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for version 0.17.0 of CLooG" >&5 -$as_echo_n "checking for version 0.17.0 of CLooG... " >&6; } +{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for version 0.18.1 of CLooG" >&5 +$as_echo_n "checking for version 0.18.1 of CLooG... " >&6; } cat confdefs.h - <<_ACEOF >conftest.$ac_ext /* end confdefs.h. */ #include "cloog/version.h" @@ -6040,50 +6040,8 @@ main () { #if CLOOG_VERSION_MAJOR != 0 \ -|| CLOOG_VERSION_MINOR != 17 \ -|| CLOOG_VERSION_REVISION < 0 -choke me - #endif - ; - return 0; -} -_ACEOF -if ac_fn_c_try_compile "$LINENO"; then : - gcc_cv_cloog=yes -else - gcc_cv_cloog=no -fi -rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext -{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $gcc_cv_cloog" >&5 -$as_echo "$gcc_cv_cloog" >&6; } - -CFLAGS=$_cloog_saved_CFLAGS -LDFLAGS=$_cloog_saved_LDFLAGS - fi - - -if test "${gcc_cv_cloog}" = no ; then - - - - if test "${ENABLE_CLOOG_CHECK}" = yes ; then -_cloog_saved_CFLAGS=$CFLAGS -_cloog_saved_LDFLAGS=$LDFLAGS - -CFLAGS="${_cloog_saved_CFLAGS} ${clooginc} ${islinc} ${gmpinc}" -LDFLAGS="${_cloog_saved_LDFLAGS} ${clooglibs} ${isllibs} ${gmplib}" - -{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for version 0.18.0 of CLooG" >&5 -$as_echo_n "checking for version 0.18.0 of CLooG... " >&6; } -cat confdefs.h - <<_ACEOF >conftest.$ac_ext -/* end confdefs.h. */ -#include "cloog/version.h" -int -main () -{ -#if CLOOG_VERSION_MAJOR != 0 \ || CLOOG_VERSION_MINOR != 18 \ -|| CLOOG_VERSION_REVISION < 0 +|| CLOOG_VERSION_REVISION < 1 choke me #endif ; @@ -6104,7 +6062,6 @@ fi -fi Index: configure.ac === --- configure.ac(revision 212861) +++ configure.ac(working copy) @@ -1661,10 +1661,7 @@ dnl with user input. CLOOG_INIT_FLAGS dnl The versions of CLooG that work for Graphite. -CLOOG_CHECK_VERSION(0,17,0) -if test "${gcc_cv_cloog}" = no ; then - CLOOG_CHECK_VERSION(0,18,0) -fi +CLOOG_CHECK_VERSION(0,18,1) dnl Only execute fail-action, if CLooG has been requested. CLOOG_IF_FAILED([
[GSoC] A formatting issue.
This patch fixes a formatting issue related to the number of characters in the line. Is it fine for trunk? -- Cheers, Roman Gareev. 2014-07-20 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: Fixes a formatting issue related to the number of characters in the line. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212863) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -464,7 +464,8 @@ case isl_ast_op_lt: { // (iterator < ub) => (iterator <= ub - 1) -isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1); +isl_val *one = + isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1); isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1); res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one)); break;
Re: [GSoC] generation of Gimple code from isl_ast_node_user
Maybe we should temporary postpone this and add a FIXME that says: “We should remove iv_map.create (loop->num + 1), if it is possible.” What do you think about this? -- Cheers, Roman Gareev.
Re: [GSoC] generation of Gimple code from isl_ast_node_user
I've asked the community about this. The patch below contains the FIXME. -- Cheers, Roman Gareev. 2014-07-12 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: Add inclusion of gimple-ssa.h, tree-into-ssa.h. (ivs_params_clear): (build_iv_mapping): New function. (translate_isl_ast_node_user): Likewise. (translate_isl_ast): Add calling of translate_isl_ast_node_user. gcc/testsuite/gcc.dg/graphite/ * isl-ast-gen-single-loop-1.c: New testcase. * isl-ast-gen-single-loop-2.c: New testcase. * isl-ast-gen-single-loop-3.c: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212888) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -51,6 +51,8 @@ #include "sese.h" #include "tree-ssa-loop-manip.h" #include "tree-scalar-evolution.h" +#include "gimple-ssa.h" +#include "tree-into-ssa.h" #include #ifdef HAVE_cloog @@ -547,6 +549,73 @@ return last_e; } +/* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the induction + variables of the loops around GBB in SESE. + + FIXME: Instead of using a vec that maps each loop id to a possible + chrec, we could consider using a map that maps loop ids to the + corresponding tree expressions. */ + +static void +build_iv_mapping (vec iv_map, gimple_bb_p gbb, + __isl_keep isl_ast_expr *user_expr, ivs_params &ip, + sese region) +{ + gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op && + isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call); + int i; + isl_ast_expr *arg_expr; + for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++) +{ + arg_expr = isl_ast_expr_get_op_arg (user_expr, i); + tree type = +build_nonstandard_integer_type (graphite_expression_type_precision, 0); + tree t = gcc_expression_from_isl_expression (type, arg_expr, ip); + loop_p old_loop = gbb_loop_at_index (gbb, region, i - 1); + iv_map[old_loop->num] = t; +} + +} + +/* Translates an isl_ast_node_user to Gimple. + + FIXME: We should remove iv_map.create (loop->num + 1), if it is possible. */ + +static edge +translate_isl_ast_node_user (__isl_keep isl_ast_node *node, +edge next_e, ivs_params &ip) +{ + gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user); + isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node); + isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0); + gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id); + isl_id *name_id = isl_ast_expr_get_id (name_expr); + poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id); + gcc_assert (pbb); + gimple_bb_p gbb = PBB_BLACK_BOX (pbb); + vec iv_map; + isl_ast_expr_free (name_expr); + isl_id_free (name_id); + + gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) && + "The entry block should not even appear within a scop"); + + loop_p loop = gbb_loop (gbb); + iv_map.create (loop->num + 1); + iv_map.safe_grow_cleared (loop->num + 1); + + build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop)); + isl_ast_expr_free (user_expr); + next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), + SCOP_REGION (pbb->scop), next_e, + iv_map, + &graphite_regenerate_error); + iv_map.release (); + mark_virtual_operands_for_renaming (cfun); + update_ssa (TODO_update_ssa); + return next_e; +} + /* Translates an ISL AST node NODE to GCC representation in the context of a SESE. */ @@ -567,7 +636,7 @@ return next_e; case isl_ast_node_user: - return next_e; + return translate_isl_ast_node_user (node, next_e, ip); case isl_ast_node_block: return next_e; Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-single-loop-1.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-single-loop-1.c (revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-single-loop-1.c (working copy) @@ -0,0 +1,26 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +int +foo () +{ + int i, res; + + for (i = 0, res = 0; i < 50; i++) + res += i; + + return res; +} + +extern void abort (); + +int +main (void) +{ + int res = foo (); + + if (res != 1225) +abort (); + + return 0; +} Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-single-loop-2.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-single-loop-2.c (revisio
[GSoC] generation of Gimple code from isl_ast_node_block
I've attached the patch, which contains generation of Gimple code from isl_ast_node_block. Is it fine for trunk? -- Cheers, Roman Gareev. 2014-07-22 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: (translate_isl_ast_node_block): New function. (translate_isl_ast): Add calling of translate_isl_ast_node_block. gcc/testsuite/gcc.dg/graphite/ * isl-ast-gen-blocks-1.c: New testcase. * isl-ast-gen-blocks-2.c: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212913) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -616,6 +616,26 @@ return next_e; } +/* Translates an isl_ast_node_block to Gimple. */ + +static edge +translate_isl_ast_node_block (loop_p context_loop, + __isl_keep isl_ast_node *node, + edge next_e, ivs_params &ip) +{ + gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_block); + isl_ast_node_list *node_list = isl_ast_node_block_get_children (node); + int i; + for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++) +{ + isl_ast_node *tmp_node = isl_ast_node_list_get_ast_node (node_list, i); + next_e = translate_isl_ast (context_loop, tmp_node, next_e, ip); + isl_ast_node_free (tmp_node); +} + isl_ast_node_list_free (node_list); + return next_e; +} + /* Translates an ISL AST node NODE to GCC representation in the context of a SESE. */ @@ -639,7 +659,8 @@ return translate_isl_ast_node_user (node, next_e, ip); case isl_ast_node_block: - return next_e; + return translate_isl_ast_node_block (context_loop, node, + next_e, ip); default: gcc_unreachable (); Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-1.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-1.c(revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-1.c(working copy) @@ -0,0 +1,27 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +int n = 50; +static int __attribute__((noinline)) +foo () +{ + int i, res; + for (i = 0, res = 0; i < n; i++) +res += i; + + return res; +} + +extern void abort (); + +int +main (void) +{ + int res = foo (); + + + if (res != 1225) +abort (); + + return 0; +} Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-2.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-2.c(revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-2.c(working copy) @@ -0,0 +1,27 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +int k = 50; +static int __attribute__((noinline)) +foo () +{ + int i, res; + for (i = 0, res = 0; i < k; i++) +res += i; + + return res; +} + +extern void abort (); + +int +main (void) +{ + int res = foo (); + + + if (res != 1225) +abort (); + + return 0; +}
[GSoC] extend schedules
I've attached the patch, which adds the extension of all schedules to the maximal number of schedule dimensions. It is necessary for the proper work of the isl AST generator. Is it fine for trunk? -- Cheers, Roman Gareev. 2014-07-22 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: (get_max_schedule_dimensions): New function. (extend_schedule): Likewise. (generate_isl_schedule): Add calling of extend_schedule. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212913) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -685,12 +685,57 @@ return isl_ast_build_from_context (context_isl); } +/* Get the maximal number of schedule dimensions in the scop SCOP. */ + +static +int get_max_schedule_dimensions (scop_p scop) +{ + int i; + poly_bb_p pbb; + int schedule_dims = 0; + + FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) +{ + int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out); + if (pbb_schedule_dims > schedule_dims) + schedule_dims = pbb_schedule_dims; +} + + return schedule_dims; +} + +/* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions. + + For schedules with different dimensionality, the isl AST generator can not + define an order and just randomly chooses an order. The solution to this + problem is to extend all schedules to the maximal number of schedule + dimensions (using '0's for the remaining values). */ + +static __isl_give isl_map * +extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims) +{ + int tmp_dims = isl_map_dim (schedule, isl_dim_out); + schedule = +isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims); + isl_val *zero = +isl_val_int_from_si (isl_map_get_ctx (schedule), 0); + int i; + for (i = tmp_dims; i < nb_schedule_dims; i++) +{ + schedule = +isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero)); +} + isl_val_free (zero); + return schedule; +} + /* Generates a schedule, which specifies an order used to visit elements in a domain. */ static __isl_give isl_union_map * generate_isl_schedule (scop_p scop) { + int nb_schedule_dims = get_max_schedule_dimensions (scop); int i; poly_bb_p pbb; isl_union_map *schedule_isl = @@ -706,6 +751,7 @@ isl_map *bb_schedule = isl_map_copy (pbb->transformed); bb_schedule = isl_map_intersect_domain (bb_schedule, isl_set_copy (pbb->domain)); + bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims); schedule_isl = isl_union_map_union (schedule_isl, isl_union_map_from_map (bb_schedule));
[GSoC] Handling of isl_ast_op_pdiv_q and isl_ast_op_pdiv_r
I've attached the patch, which adds handling of isl_ast_op_pdiv_q and isl_ast_op_pdiv_r. It also contains a corresponding test case, which generates the following ISL AST: { for (int c1 = 0; c1 < -((-k.0 + i + 4294967296) % 4294967296) + 4294967296; c1 += 1) S_4(c1); S_6(); } Is it fine for trunk? -- Cheers, Roman Gareev. 2014-07-23 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (binary_op_to_tree): Add new cases. (gcc_expression_from_isl_expr_op): Move isl_ast_op_pdiv_q, isl_ast_op_pdiv_r to different cases. [gcc/testsuite] * gcc.dg/graphite/isl-ast-gen-blocks-3.c: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212922) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -186,6 +186,12 @@ case isl_ast_op_div: return fold_build2 (EXACT_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); +case isl_ast_op_pdiv_q: + return fold_build2 (TRUNC_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); + +case isl_ast_op_pdiv_r: + return fold_build2 (TRUNC_MOD_EXPR, type, tree_lhs_expr, tree_rhs_expr); + case isl_ast_op_fdiv_q: return fold_build2 (FLOOR_DIV_EXPR, type, tree_lhs_expr, tree_rhs_expr); @@ -299,8 +305,6 @@ case isl_ast_op_call: case isl_ast_op_and_then: case isl_ast_op_or_else: -case isl_ast_op_pdiv_q: -case isl_ast_op_pdiv_r: case isl_ast_op_select: gcc_unreachable (); @@ -312,6 +316,8 @@ case isl_ast_op_sub: case isl_ast_op_mul: case isl_ast_op_div: +case isl_ast_op_pdiv_q: +case isl_ast_op_pdiv_r: case isl_ast_op_fdiv_q: case isl_ast_op_and: case isl_ast_op_or: Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-3.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-3.c(revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-3.c(working copy) @@ -0,0 +1,27 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +int k = 50; +static int __attribute__((noinline)) +foo () +{ + int i, res; + for (i = k/2, res = 0; i < k; i++) +res += i; + + return res; +} + +extern void abort (); + +int +main (void) +{ + int res = foo (); + + + if (res != 925) +abort (); + + return 0; +}
[GSoC] A bug related to induction variables and blocks
If we try to generate code from the following ISL AST: { for (int c1 = 0; c1 < k.3; c1 += 1) { S_21(c1); S_21(c1); S_4(c1); for (int c3 = 0; c3 < pretmp; c3 += 1) S_5(c1, c3); S_7(c1); S_26(c1); S_8(c1); S_8(c1); S_9(c1); for (int c3 = 0; c3 < pretmp; c3 += 1) S_10(c1, c3); S_11(c1); S_25(c1); S_13(c1); S_13(c1); S_14(c1); for (int c3 = 0; c3 < pretmp; c3 += 1) S_15(c1, c3); S_16(c1); S_24(c1); S_18(c1); } S_19(); } we'll get the following error: isl_ctx.c:172: isl_ctx freed, but some objects still reference it If I'm not mistaken, it is caused by missing of isl_id_free functions, which should be called in the same quantity as isl_ast_expr_get_id because of the implementation of ISL. I've attached the patch, which may fix the problem. It also contains a corresponding test case. Is it fine for trunk? -- Cheers, Roman Gareev. 2014-07-23 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (graphite_create_new_loop): Add calling of isl_id_free. [gcc/testsuite] * gcc.dg/graphite/isl-ast-gen-blocks-4.c: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212922) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -383,6 +383,10 @@ isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for); isl_id *id = isl_ast_expr_get_id (for_iterator); + std::map::iterator res; + res = ip.find (id); + if (res != ip.end ()) +isl_id_free (res->first); ip[id] = iv; isl_ast_expr_free (for_iterator); return loop; Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-4.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-4.c(revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-4.c(working copy) @@ -0,0 +1,37 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +int k = 4; +int n1 = 50; +int n2 = 50; +int n3 = 50; + +static int __attribute__((noinline)) +foo () +{ + int j, res = 0; + for (j = 0, res = 0; j < k; j++) +{ + int i; + for (i = 0; i < n1; i++) +res += i; + for (i = 0; i < n2; i++) +res += i; + for (i = 0; i < n3; i++) +res += i; +} + + return res; +} + +extern void abort (); + +int +main (void) +{ + int res = foo (); + if (res != 14700) +abort (); + + return 0; +}
Re: [GSoC] generation of Gimple code from isl_ast_node_block
> gcc/ > * graphite-isl-ast-to-gimple.c: > (translate_isl_ast_node_block): New function. > (translate_isl_ast): Add calling of translate_isl_ast_node_block. > > gcc/testsuite/gcc.dg/graphite/ > * isl-ast-gen-blocks-1.c: New testcase. > * isl-ast-gen-blocks-2.c: New testcase. > > The second part of the ChangeLog entry is wrong: it should go into > gcc/testsuite/ChangeLog as > > * gcc.dg/graphite/isl-ast-gen-blocks-1.c: New testcase. > * gcc.dg/graphite/isl-ast-gen-blocks-2.c: New testcase. > > Please fix the ChangeLog entries; no need to add another one for that > change or ask for approval: such a fix is obvious. Thank you for the comment! -- Cheers, Roman Gareev.
Re: [GSoC] Handling of isl_ast_op_pdiv_q and isl_ast_op_pdiv_r
> Any reason you don't make 'k' a function parameter? Yes, ISL'll generate the following code, if 'k' a function parameter: for (int c1 = 0; c1 <= 24; c1 += 1) S_3(c1); However, we could use -fno-ipa-cp to get the ISL AST, which contains isl_ast_op_pdiv_r. What do you think about this? > Can you initialize res outside of the loop? Yes, I've implemented this in the improved version. -- Cheers, Roman Gareev.
[GSoC] generation of Gimple code from isl_ast_node_if
I've attached the patch, which contains generation of Gimple code from isl_ast_node_if. However, I've found out a problem. When I'm trying to generate Gimple code from, for example, the following ISL AST: { for (int c1 = 0; c1 <= 49; c1 += 1) { S_6(c1); if (c1 <= 48) { S_3(c1); if (c1 >= 24) S_4(c1); S_5(c1); } } S_7(); } the pointer to Gimple basic block of S_3's poly basic block is NULL. Could you please advise me possible reasons of this issue? The source code of the example: int foo () { int i, res = 0; for (i = 0; i < 50; i++) { if (i >= 25) res += i; } return res; } extern void abort (); int main (void) { int res = foo (); if (res != 1225) abort (); return 0; } -- Cheers, Roman Gareev. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212922) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -636,6 +636,42 @@ return next_e; } +/* Creates a new if region corresponding to ISL's cond. */ + +static edge +graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond, + ivs_params &ip) +{ + tree type = +build_nonstandard_integer_type (graphite_expression_type_precision, 0); + tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip); + edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); + return exit_edge; +} + +/* Translates an isl_ast_node_if to Gimple. */ + +static edge +translate_isl_ast_node_if (loop_p context_loop, + __isl_keep isl_ast_node *node, + edge next_e, ivs_params &ip) +{ + gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if); + isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node); + edge last_e = graphite_create_new_guard (next_e, if_cond, ip); + + edge true_e = get_true_edge_from_guard_bb (next_e->dest); + isl_ast_node *then_node = isl_ast_node_if_get_then (node); + translate_isl_ast (context_loop, then_node, true_e, ip); + isl_ast_node_free (then_node); + + edge false_e = get_false_edge_from_guard_bb (next_e->dest); + isl_ast_node *else_node = isl_ast_node_if_get_else (node); + translate_isl_ast (context_loop, else_node, false_e, ip); + isl_ast_node_free (else_node); + return last_e; +} + /* Translates an ISL AST node NODE to GCC representation in the context of a SESE. */ @@ -653,7 +689,8 @@ next_e, ip); case isl_ast_node_if: - return next_e; + return translate_isl_ast_node_if (context_loop, node, + next_e, ip); case isl_ast_node_user: return translate_isl_ast_node_user (node, next_e, ip);
Re: [GSoC] A bug related to induction variables and blocks
> Is there a reason you have those global values? To my understanding they > could possibly just be function parameters? Yes, it would be fine for this test case. I've implemented this in the improved version. -- Cheers, Roman Gareev. 2014-07-23 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (graphite_create_new_loop): Add calling of isl_id_free to properly decrement reference counts. [gcc/testsuite] * gcc.dg/graphite/isl-ast-gen-blocks-4.c: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212922) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -383,6 +383,10 @@ isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for); isl_id *id = isl_ast_expr_get_id (for_iterator); + std::map::iterator res; + res = ip.find (id); + if (ip.count (id)) +isl_id_free (res->first); ip[id] = iv; isl_ast_expr_free (for_iterator); return loop; Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-4.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-4.c(revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-blocks-4.c(working copy) @@ -0,0 +1,32 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +static int __attribute__((noinline)) +foo (int k, int n1, int n2, int n3) +{ + int j, res = 0; + for (j = 0; j < k; j++) +{ + int i; + for (i = 0; i < n1; i++) +res += i; + for (i = 0; i < n2; i++) +res += i; + for (i = 0; i < n3; i++) +res += i; +} + + return res; +} + +extern void abort (); + +int +main (void) +{ + int res = foo (4, 50, 50, 50); + if (res != 14700) +abort (); + + return 0; +}
Re: [GSoC] generation of Gimple code from isl_ast_node_if
> I have no idea. Is the Gimple basic block of S_3 never set, or is it set and > deleted on the way? I think, that it is deleted on the way. I've found out, that the Gimple basic block will be set, if we add the following code to the generate_isl_schedule: bb_schedule = isl_map_set_tuple_id (bb_schedule, isl_dim_in, isl_id_for_pbb (scop, pbb)); where isl_id_for_pbb is static isl_id * isl_id_for_pbb (scop_p s, poly_bb_p pbb) { char name[50]; snprintf (name, sizeof (name), "S_%d", pbb_index (pbb)); return isl_id_alloc (s->ctx, name, pbb); } > What code does S_3 correspond to? If I'm not mistaken, it is corresponds to: res_18 = Cross_BB_scalar_dependence.7[0]; phi_out_of_ssa.4[0] = res_18; I used the following code from https://gcc.gnu.org/onlinedocs/gccint/Basic-Blocks.html to dump basic block of the Gimple basic block: gimple_stmt_iterator si; for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) { gimple phi = gsi_stmt (si); print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); } for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) { gimple stmt = gsi_stmt (si); print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } Could you please advise me possible functions from graphite-sese-to-poly.c, which can delete this? P.S.: Only S_3 has this problem in the example. -- Cheers, Roman Gareev.
Re: [GSoC] generation of Gimple code from isl_ast_node_if
If I'm not mistaken, the reason of this bug is incorrect creation of a poly_bb_p for basic_block from the existing pbb in new_pbb_from_pbb (It is located in graphite-sese-to-poly.c). I think, that we should set a new id of pbb1->domain (instead of using the id of the pbb), which contains pointer to the pbb1. I found out this after dumping of an index of pbb in the user statement S_3. Its index is 9. It is created in rewrite_reduction_out_of_ssa using new_pbb_from_pbb and the pbb with index 3. After that the user statement S_3 is removed in build_scop_drs, but the id of the pbb->domain and the pbb->transformed point to the old pbb with index 3. I've attached the patch, which may fix this. -- Cheers, Roman Gareev. Index: gcc/graphite-sese-to-poly.c === --- gcc/graphite-sese-to-poly.c (revision 212995) +++ gcc/graphite-sese-to-poly.c (working copy) @@ -2044,6 +2044,10 @@ break; pbb1->domain = isl_set_copy (pbb->domain); + char name[50]; + snprintf (name, sizeof (name), "S_%d", pbb_index (pbb1)); + pbb1->domain = isl_set_set_tuple_id (pbb1->domain, + isl_id_alloc (scop->ctx, name, pbb1)); GBB_PBB (gbb1) = pbb1; GBB_CONDITIONS (gbb1) = GBB_CONDITIONS (gbb).copy ();
Re: [GSoC] generation of Gimple code from isl_ast_node_if
> Any reason you don't use isl_id_for_pbb() to create this isl_id? Yes, it is redundant. I've used isl_id_for_pbb() in the improved version. > Otherwise, the patch looks good to me. You can commit it if the graphite > tests still pass and you add an appropriate ChangeLog entry. I haven't found out regression during testing with the graphite tests. > This patch looks also good. Can you quickly repost with the two test cases as > well as the appropriate ChangeLog, before I give the final OK. If I'm not mistaken, I sent you only one test case. Should we create another one? -- Cheers, Roman Gareev. 2014-07-26 Roman Gareev [gcc/] * graphite-sese-to-poly.c: (new_pbb_from_pbb): Set a new id of pbb1->domain (instead of using the id of the pbb), which contains pointer to the pbb1. 2014-07-26 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (graphite_create_new_guard): New function. (translate_isl_ast_node_if): New function. (translate_isl_ast): Add calling of translate_isl_ast_node_if. [gcc/testsuite] * gcc.dg/graphite/isl-ast-gen-if-1.c: New testcase. Index: gcc/graphite-sese-to-poly.c === --- gcc/graphite-sese-to-poly.c (revision 212995) +++ gcc/graphite-sese-to-poly.c (working copy) @@ -2044,7 +2044,8 @@ break; pbb1->domain = isl_set_copy (pbb->domain); - + pbb1->domain = isl_set_set_tuple_id (pbb1->domain, + isl_id_for_pbb (scop, pbb1)); GBB_PBB (gbb1) = pbb1; GBB_CONDITIONS (gbb1) = GBB_CONDITIONS (gbb).copy (); GBB_CONDITION_CASES (gbb1) = GBB_CONDITION_CASES (gbb).copy (); Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212995) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -646,6 +646,43 @@ return next_e; } +/* Creates a new if region corresponding to ISL's cond. */ + +static edge +graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond, + ivs_params &ip) +{ + tree type = +build_nonstandard_integer_type (graphite_expression_type_precision, 0); + tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip); + edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); + return exit_edge; +} + +/* Translates an isl_ast_node_if to Gimple. */ + +static edge +translate_isl_ast_node_if (loop_p context_loop, + __isl_keep isl_ast_node *node, + edge next_e, ivs_params &ip) +{ + gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if); + isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node); + edge last_e = graphite_create_new_guard (next_e, if_cond, ip); + + edge true_e = get_true_edge_from_guard_bb (next_e->dest); + isl_ast_node *then_node = isl_ast_node_if_get_then (node); + translate_isl_ast (context_loop, then_node, true_e, ip); + isl_ast_node_free (then_node); + + edge false_e = get_false_edge_from_guard_bb (next_e->dest); + isl_ast_node *else_node = isl_ast_node_if_get_else (node); + if (isl_ast_node_get_type (else_node) != isl_ast_node_error) +translate_isl_ast (context_loop, else_node, false_e, ip); + isl_ast_node_free (else_node); + return last_e; +} + /* Translates an ISL AST node NODE to GCC representation in the context of a SESE. */ @@ -663,7 +700,8 @@ next_e, ip); case isl_ast_node_if: - return next_e; + return translate_isl_ast_node_if (context_loop, node, + next_e, ip); case isl_ast_node_user: return translate_isl_ast_node_user (node, next_e, ip); Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c(revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c(working copy) @@ -0,0 +1,29 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +static int __attribute__((noinline)) +foo () +{ + int i, res = 0; + + for (i = 0; i < 50; i++) +{ + if (i >= 25) +res += i; +} + + return res; +} + +extern void abort (); + +int +main (void) +{ + int res = foo (); + + if (res != 925) +abort (); + + return 0; +}
Re: [GSoC] generation of Gimple code from isl_ast_node_if
I've tried to compile your example and had the similar problem. It generates the following ISL AST { for (int c1 = 0; c1 <= 49; c1 += 1) { S_6(c1); if (c1 <= 48) { S_3(c1); S_9(c1); if (c1 >= 24) S_4(c1); S_5(c1); } } S_7(); } where S_9 has pbb->domain and pbb->transformed of S_3. A pointer to a Gimple basic block is not NULL now, but it leads to the wrong answer. I've tried different examples, which generate ISL AST, but they have same problems. Could you please advise me another one? -- Cheers, Roman Gareev.
Re: [GSoC] generation of Gimple code from isl_ast_node_if
> What do you mean by wrong answer? Is there still a bug in the code > generation or the AST is just more complex as expected. I mean that the value of res is wrong. I think it is because of the wrong id of pbb->domain and pbb->transformed inherited from S_3 by S_9 (It was correct for S_3, but it is incorrect for S_9). > To my understanding bb copies are introduced in case reductions are seen. > You could try to just initialize an array (maybe a little bit more complex, > but without += statements): > > for i: > A[i] = ... > > You could do the summation/verfication outside of the scop e.g. in the main > function. It seems that it doesn't help (at least for now). However, I've found out the following example: static int __attribute__((noinline)) foo () { int i, res = 0; for (i = 0; i < 50; i++) { if (i < 5) res += 1; } return res; } extern void abort (); int main (void) { int res = foo (); if (res != 5) abort (); return 0; } It gives the correct result, inspite of duplicating of pbbs and generates the following ISL AST { for (int c1 = 0; c1 <= 49; c1 += 1) { for (int c2 = 0; c2 <= 1; c2 += 1) S_3(c1); if (c1 <= 4) S_4(c1); S_5(c1); } S_7(); } Maybe we could use it. What do you think about this? -- Cheers, Roman Gareev.
Re: [GSoC] generation of Gimple code from isl_ast_node_if
> I would still add a test case which does not contain a reduction (+=) > and where graphite is not duplicating pbbs. > Help for what? I was looking to create a simple test case. Is there still an > open bug? Sorry, I thought, we should add this test case to be able to test graphite without patch related to graphite-sese-to-poly.c (patch1). > Sorry Roman. I am still confused. Are we looking for a test case or are we > still trying to understand an issue. Specifically, do we still incorrectly > transform the code even after your isl_id_for_pbb() patch? I gives a wrong answer without patch1. The code is transformed correctly with this patch. -- Cheers, Roman Gareev.
Re: [GSoC] generation of Gimple code from isl_ast_node_if
> Can you explain why you believe it is hard/impossible to generate a test > case without reduction? I don't believe this. I only know that all the test cases considered by me have the same problem. Could you please explain what is 'reduction'? I've found out that, according to the comment of the rewrite_reductions_out_of_ssa (this function duplicates pbbs), the rewrite_reductions_out_of_ssa rewrite out of SSA all the reduction phi nodes of SCOP. What are reduction phi nodes? How are they related to 'reduction'? -- Cheers, Roman Gareev.
Re: [GSoC] generation of Gimple code from isl_ast_node_if
Thank you! I've attached patches with a test case (it is located in patch1.txt), which generates the following ISL AST: for (int c1 = 0; c1 <= 49; c1 += 1) { if (c1 <= 24) S_4(c1); S_5(c1); } I think that it doesn't contain reduction and doesn't yield several bbs. I've also checked that pbbs correspond to pbbs of pbb->domain and pbb->transformed. -- Cheers, Roman Gareev. 2014-07-23 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (graphite_create_new_guard): New function. (translate_isl_ast_node_if): New function. (translate_isl_ast): Add calling of translate_isl_ast_node_if. [gcc/testsuite] * gcc.dg/graphite/isl-ast-gen-if-1.c: New testcase. 2014-07-23 Roman Gareev [gcc/] * graphite-sese-to-poly.c: (new_pbb_from_pbb): Set a new id of pbb1->domain (instead of using the id of the pbb), which contains pointer to the pbb1. [gcc/testsuite] * gcc.dg/graphite/isl-ast-gen-if-2.c: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 212995) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -646,6 +646,43 @@ return next_e; } +/* Creates a new if region corresponding to ISL's cond. */ + +static edge +graphite_create_new_guard (edge entry_edge, __isl_take isl_ast_expr *if_cond, + ivs_params &ip) +{ + tree type = +build_nonstandard_integer_type (graphite_expression_type_precision, 0); + tree cond_expr = gcc_expression_from_isl_expression (type, if_cond, ip); + edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); + return exit_edge; +} + +/* Translates an isl_ast_node_if to Gimple. */ + +static edge +translate_isl_ast_node_if (loop_p context_loop, + __isl_keep isl_ast_node *node, + edge next_e, ivs_params &ip) +{ + gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_if); + isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node); + edge last_e = graphite_create_new_guard (next_e, if_cond, ip); + + edge true_e = get_true_edge_from_guard_bb (next_e->dest); + isl_ast_node *then_node = isl_ast_node_if_get_then (node); + translate_isl_ast (context_loop, then_node, true_e, ip); + isl_ast_node_free (then_node); + + edge false_e = get_false_edge_from_guard_bb (next_e->dest); + isl_ast_node *else_node = isl_ast_node_if_get_else (node); + if (isl_ast_node_get_type (else_node) != isl_ast_node_error) +translate_isl_ast (context_loop, else_node, false_e, ip); + isl_ast_node_free (else_node); + return last_e; +} + /* Translates an ISL AST node NODE to GCC representation in the context of a SESE. */ @@ -663,7 +700,8 @@ next_e, ip); case isl_ast_node_if: - return next_e; + return translate_isl_ast_node_if (context_loop, node, + next_e, ip); case isl_ast_node_user: return translate_isl_ast_node_user (node, next_e, ip); Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c(revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-1.c(working copy) @@ -0,0 +1,37 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +int st = 1; +static void __attribute__((noinline)) +foo (int a[], int n) +{ + int i; + for (i = 0; i < n; i++) +{ + if (i < 25) +a[i] = i; + a[n - i] = 1; +} +} + +static int __attribute__((noinline)) +array_sum (int a[]) +{ + int i, res = 0; + for(i = 0; i < 50; i += st) +res += a[i]; + return res; +} + +extern void abort (); + +int +main (void) +{ + int a[50]; + foo (a, 50); + int res = array_sum (a); + if (res != 49) +abort (); + return 0; +} Index: gcc/graphite-sese-to-poly.c === --- gcc/graphite-sese-to-poly.c (revision 212995) +++ gcc/graphite-sese-to-poly.c (working copy) @@ -2044,7 +2044,8 @@ break; pbb1->domain = isl_set_copy (pbb->domain); - + pbb1->domain = isl_set_set_tuple_id (pbb1->domain, + isl_id_for_pbb (scop, pbb1)); GBB_PBB (gbb1) = pbb1; GBB_CONDITIONS (gbb1) = GBB_CONDITIONS (gbb).copy (); GBB_CONDITION_CASES (gbb1) = GBB_CONDITION_CASES (gbb).copy (); Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-2.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-2.c(revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-if-2.c(working copy) @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-options &q
[GSoC] type of an isl_ast_expr_id
I've tested Graphite with the ISL AST generator as the main code generator and found out the following problem: in the current implementation the gcc_expression_from_isl_ast_expr_id can return a tree of a type, which doesn't correspond to the type chosen for graphite expressions. If we try, for example, to generate Gimple code from the following ISL AST: if (J >= 1) { for (int c1 = 0; c1 < min(N, J); c1 += 1) { for (int c3 = 0; c3 < min(J, N); c3 += 1) S_10(c1, c3); for (int c3 = J + 1; c3 < N; c3 += 1) S_10(c1, c3); } for (int c1 = J + 1; c1 < N; c1 += 1) { for (int c3 = 0; c3 < J; c3 += 1) S_10(c1, c3); for (int c3 = J + 1; c3 < N; c3 += 1) S_10(c1, c3); } } else for (int c1 = 1; c1 < N; c1 += 1) for (int c3 = 1; c3 < N; c3 += 1) S_10(c1, c3); (It's generated from id-10.c) we'll get the following error: id-10.c: In function ‘foo’: id-10.c:4:1: internal compiler error: in fold_binary_loc, at fold-const.c:10692 foo (int N, unsigned int J) ^ 0x7cff3a fold_binary_loc(unsigned int, tree_code, tree_node*, tree_node*, tree_node*) /home/roman/sec_trunk/gcc/gcc/fold-const.c:10692 0x7d646a fold_build2_stat_loc(unsigned int, tree_code, tree_node*, tree_node*, tree_node*) /home/roman/sec_trunk/gcc/gcc/fold-const.c:15023 0xf010e8 nary_op_to_tree /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:290 0xf010e8 gcc_expression_from_isl_expr_op /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:317 0xf010e8 gcc_expression_from_isl_expression /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:364 0xf00f57 binary_op_to_tree /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:170 0xf00f57 gcc_expression_from_isl_expr_op /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:333 0xf00f57 gcc_expression_from_isl_expression /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:364 0xf018d0 graphite_create_new_loop_guard /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:523 0xf018d0 translate_isl_ast_node_for /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:558 0xf018d0 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:704 0xf017b0 translate_isl_ast_node_block /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:646 0xf017b0 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:715 0xf01702 translate_isl_ast_node_if /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:679 0xf01702 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:708 0xf027d7 graphite_regenerate_ast_isl(scop*) /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:893 0xefce8f graphite_transform_loops() /home/roman/sec_trunk/gcc/gcc/graphite.c:304 0xefcf10 graphite_transforms /home/roman/sec_trunk/gcc/gcc/graphite.c:333 0xefcf10 execute /home/roman/sec_trunk/gcc/gcc/graphite.c:413 It is caused by difference in precisions of arguments in the min expression. The attached patch may fix this. I've also found out that pr35356-2.c is no longer suitable for testing. The following CLooG AST for (scat_1=0;scat_1<=min(k_6-1,n_5-1);scat_1++) { (scat_1); } if ((k_6 >= 0) && (n_5 >= k_6+1)) { (k_6); } for (scat_1=max(0,k_6+1);scat_1<=n_5-1;scat_1++) { (scat_1); } is generated from its source code int a[100]; int foo (int bar, int n, int k) { int i; for (i = 0; i < n; i++) if (i == k) a[i] = 1; else a[i] = i; return a[bar]; } The test checks that the dump file contains four MIN_EXPR and four MAX_EXPR /* { dg-final { scan-tree-dump-times "MIN_EXPR\[^\\n\\r]*;" 4 "graphite" } } */ /* { dg-final { scan-tree-dump-times "MAX_EXPR\[^\\n\\r]*;" 4 "graphite" } } */ However, the ISL AST generated from this code if (k >= 1) { for (int c1 = 0; c1 < n; c1 += 1) if (c1 >= k + 1) { S_7(c1); } else if (k >= c1 + 1) { S_7(c1); } else S_6(k); } else { if (k == 0) S_6(0); for (int c1 = max(k + 1, 0); c1 < n; c1 += 1) S_7(c1); } doesn't contain min expression at all. Should we remove /* { dg-final { scan-tree-dump-times "MIN_EXPR\[^\\n\\r]*;" 4 "graphite" } } */ from this test case? P.S.: The other graphite tests (except vect-pr43423.c) are passed by graphite in case we run it with the ISL AST generator. -- Cheers, Roman Gareev. 2014-07-29 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (gcc_expression_from_isl_ast_expr_id): Add calling of fold_convert. (gcc_expression_from_isl_expression): Pass type to gcc_expression_from_isl_ast_expr_id. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 213109) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @
Re: [GSoC] type of an isl_ast_expr_id
> Blindly converting type sizes is not a good idea and may be problematic when > we switch to smaller types. As we can obviously only improve this when we > have the appropriate support in isl, I think the attached patch is fine. > However, please add a fixme that states that this should > be looked at again at the moment when we get isl support to derive the > optimal types. I've attached a patch, which contains the fixme. > Please have a look at the original bug report: > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35356 > > The isl ast generator should produce something like: > > for (i = 0; i < min (n, k); i++) > a[i] = i; > if (k >= 0 && k < n) > a[k] = 1; > for (i = max(k+1,0); i < n; i++) > a[i] = i; > > CLooG does not generate optimal code either, but the code generated by isl > is a regression compared to CLooG. > > Can you generate an isl_codegen input for this test case and verify that the > latest public version of isl does not generate this optimal code either. If > it does not, please report this as an optimization bug to the isl mailing > list. > > After you got feedback, I think it is OK to disable this test and to > add a FIXME explaining why this test is disabled and if we can expect a fix > in later versions of isl. I've generated the code using the isl-0.13 if (n >= k + 1) { for (int c1 = 0; c1 < n; c1 += 1) { if (c1 >= k + 1) { S_7(c1); } else if (k >= c1 + 1) { S_7(c1); } else S_6(k); } } else for (int c1 = 0; c1 < n; c1 += 1) S_7(c1); If I'm not mistaken it's also a regression compared to ClooG and it's better to report this to the isl mailing list. > What is the problem with this last test case? It is related to checking for the loop parallelism, which is not yet implemented in the current version of graphite-isl-ast-to-gimple.c. -- Cheers, Roman Gareev. 2014-07-30 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (gcc_expression_from_isl_ast_expr_id): Add calling of fold_convert. (gcc_expression_from_isl_expression): Pass type to gcc_expression_from_isl_ast_expr_id. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 213109) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -122,10 +122,14 @@ ivs_params &ip); /* Return the tree variable that corresponds to the given isl ast identifier - expression (an isl_ast_expr of type isl_ast_expr_id). */ + expression (an isl_ast_expr of type isl_ast_expr_id). + FIXME: We should replace blind conversation of id's type with derivation + of the optimal type when we get the corresponding isl support. */ + static tree -gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id, +gcc_expression_from_isl_ast_expr_id (tree type, +__isl_keep isl_ast_expr *expr_id, ivs_params &ip) { gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id); @@ -136,7 +140,7 @@ gcc_assert (res != ip.end () && "Could not map isl_id to tree expression"); isl_ast_expr_free (expr_id); - return res->second; + return fold_convert (type, res->second); } /* Converts an isl_ast_expr_int expression E to a GCC expression tree of @@ -351,7 +355,7 @@ switch (isl_ast_expr_get_type (expr)) { case isl_ast_expr_id: - return gcc_expression_from_isl_ast_expr_id (expr, ip); + return gcc_expression_from_isl_ast_expr_id (type, expr, ip); case isl_ast_expr_int: return gcc_expression_from_isl_expr_int (type, expr);
Re: [GSoC] type of an isl_ast_expr_id
> OK. I proposed a slightly longer description. With the updated description, > you can commit this patch. I've fixed the fixme. FIXME: We should replace blind conversation of id's type with derivation of the optimal type when we get the corresponding isl support. Blindly converting type sizes may be problematic when we switch to smaller types. Would you add anything to it? > That's what I suggested earlier, no? The only thing I would like you to > check beforehand is if the very same problem still exists with isl trunk. > For this you need to generate an input file for the 'isl_codegen' tool as it > comes with isl that allows to reproduce the bug. The very same input file > can then be submitted to the isl mailing list as a bug report. Could you do > the reporting (and CC me)? Yes, I wanted to make sure that the code generated by the isl-0.13 is also not optimal (I sent you the code generated by isl-0.12.2 before). The report has been sent to the isl mailing list and CC you. -- Cheers, Roman Gareev.
Re: [GSoC] type of an isl_ast_expr_id
Could you please advise me how is it better to answer the following questions of Sven: > In what way is it "not optimal"? > That is, what are your optimality criteria? (I could answer them, but I don't want to miss anything) -- Cheers, Roman Gareev.
Re: [GSoC] checking for the loop parallelism
> Hi Roman, > > you can get this information from the isl_ast_build that was used when > generating a certain loop (you can access this isl_ast_build from the > callbacks isl_ast_build_set_before_each_for and > isl_ast_build_set_after_each_for). With isl_ast_build_get_schedule, you can > get an incomplete schedule (less dimensions then the schedule that you gave > to the isl ast generator). Specifically, it only contains the dimensions of > the current loop and all surrounding ones. Consequently the last dimension > in this incomplete schedule is the dimension you want to check for > parallelism. Hi Tobias, thank you! I've attached a patch, which contains the first draft of checking for the loop parallelism. If I'm not mistaken, the depth, which can be obtained from isl_ast_build, is only suitable for the incomplete schedule, which can be obtained using isl_ast_build_get_schedule. That's why the temporary implementation works with the incomplete schedule instead of the result from scop_get_transformed_schedule. I have a question about vect-pr43423.c. CLooG generates the following code from this example: vect-pr43423.c for (scat_1=0;scat_1<=min(mid_6-1,n_5-1);scat_1++) { (scat_1); (scat_1); } for (scat_1=max(0,mid_6);scat_1<=n_5-1;scat_1++) { (scat_1); (scat_1); } This loops can be parallelized, according to the description of pr43423: "... void foo(int n, int mid) { int i; for(i=0; i= c1 + 1) { S_6(c1); } else S_7(c1); S_8(c1); } I think it can't be parallelized. Maybe this example is no more suitable. What do you think about this? -- Cheers, Roman Gareev. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 213262) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -435,7 +435,14 @@ redirect_edge_succ_nodup (next_e, after); set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); - /* TODO: Add checking for the loop parallelism. */ + if (flag_loop_parallelize_all) + { +isl_id *id = isl_ast_node_get_annotation (node_for); +gcc_assert (id); +if (isl_id_get_user (id) != NULL) + loop->can_be_parallel = true; +isl_id_free (id); + } return last_e; } @@ -834,6 +841,97 @@ return schedule_isl; } +/* Applies SCHEDULE to the in and out dimensions of the dependences + DEPS and return the resulting relation. */ + +static __isl_give isl_map * +apply_schedule_on_deps (__isl_keep isl_union_map *schedule, + __isl_keep isl_union_map *deps) +{ + isl_map *x; + isl_union_map *ux, *trans; + + trans = isl_union_map_copy (schedule); + trans = extend_schedule (trans); + ux = isl_union_map_copy (deps); + ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans)); + ux = isl_union_map_apply_range (ux, trans); + if (isl_union_map_is_empty (ux)) +{ + isl_union_map_free (ux); + return NULL; +} + x = isl_map_from_union_map (ux); + + return x; +} + +/* Return true when DEPS is non empty and the intersection of LEX with + the DEPS transformed by SCHEDULE is non empty. LEX is the relation + in which all the inputs before DEPTH occur at the same time as the + output, and the input at DEPTH occurs before output. */ + +static bool +carries_deps (__isl_keep isl_union_map *schedule, + __isl_keep isl_union_map *deps, + int depth) +{ + bool res; + int i; + isl_space *space; + isl_map *lex, *x; + isl_constraint *ineq; + + if (isl_union_map_is_empty (deps)) +return false; + + x = apply_schedule_on_deps (schedule, deps); + if (x == NULL) +return false; + space = isl_map_get_space (x); + space = isl_space_range (space); + lex = isl_map_lex_le (space); + space = isl_map_get_space (x); + ineq = isl_inequality_alloc (isl_local_space_from_space (space)); + + for (i = 0; i < depth - 1; i++) +lex = isl_map_equate (lex, isl_dim_in, i, isl_dim_out, i); + + /* in + 1 <= out */ + ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_out, depth - 1, 1); + ineq = isl_constraint_set_coefficient_si (ineq, isl_dim_in, depth - 1, -1); + ineq = isl_constraint_set_constant_si (ineq, -1); + lex = isl_map_add_constraint (lex, ineq); + x = isl_map_intersect (x, lex); + res = !isl_map_is_empty (x); + + isl_map_free (x); + return res; +} + +/* This method is executed before the construction of a for node. */ +static __isl_give isl_id * +ast_build_before_for (__isl_keep isl_ast_build *build, void *user) +{ + scop_p scop = (scop_p) user; + isl_ast_build *pointer = NULL; + isl_union_map *schedule = isl_ast_build_get_schedule (build); + isl_space *schedule_space = isl_ast_build_get_schedule_space (build); + int dimension = isl_space_dim (schedule_space, isl_dim_out) - 1; + int res = (carries_deps (schedule, scop->mus
Re: [GSoC] checking for the loop parallelism
> This looks very similar to what we reported to the isl mailing list. It is > definitely not the best test case for the parallelism patch. In fact, I > doubt this requires the parallelism test at all. I've found out, that Graphite generates the expected code using the separate option for all dimensions: { for (int c1 = 0; c1 < min(n, mid); c1 += 1) { S_6(c1); S_8(c1); } for (int c1 = max(mid, 0); c1 < n; c1 += 1) { S_7(c1); S_8(c1); } } However, there are problems in vectorization of this code (I've attached .vect files generated by versions, which use CLooG and ISL). It seems that it is related to inappropriate type sizes. Do you know anything about it? > You should have a look at the following test case for openmp tests: > libgomp/testsuite/libgomp.graphite Graphite successfully passes all the tests from libgomp/testsuite/libgomp.graphite except graphite-isl-ast-to-gimple.c and graphite-poly.h. If we consider the code generated by ISL and by CLooG from force-parallel-5.c, we'll see, that they are similar: the code generated by ISL: for (int c1 = 0; c1 <= 1499; c1 += 1) S_3(c1); for (int c1 = 0; c1 <= 497; c1 += 1) for (int c3 = 0; c3 <= c1; c3 += 1) S_7(c1, c3); the code generated by ClooG: for (scat_1=0;scat_1<=1499;scat_1++) { (scat_1); } for (scat_1=0;scat_1<=497;scat_1++) { for (scat_3=0;scat_3<=scat_1;scat_3++) { (scat_1,scat_3); } } the source code: void abort (void); #define N 500 void foo(void) { int i,j; int A[3*N], B[3*N]; for (i = 0; i < 3*N; i++) B[i] = A[i] = i; for (i = 1; i < N; i++) for (j = 1; j < i; j++) /* This loop carried no dependency, it fails at code generation part.*/ A[j+N] = A[j] + j; for (i = 1; i < N; i++) for (j = 1; j < i; j++) if (A[j+N] != B[j] + j) abort(); } int main(void) { foo(); return 0; } The previous implementation of dependence analysis marks “for (scat_1=0;scat_1<=497;scat_1++) {“ as parallelizable. However, the current dependence analysis finds must_waw dependence: { [i0] -> [1 + i0] : i0 >= 1 and i0 <= 496 } (schedule: { S_7[i0, i1] -> [i0] : exists (e0 = [(i0)/4294967296]: i0 >= 0 and i0 <= 497 and i1 >= 0 and 4294967296e0 <= i0 and 4294967296e0 >= -4294967295 + i0 and 4294967296e0 <= i0 - i1 and i1 <= 498) } dependence: { S_7[i0, i1] -> S_7[1 + i0, i1] : exists (e0 = [(1 + i0)/4294967296], e1 = [(i0)/4294967296]: i1 >= 0 and i1 <= 498 and i0 >= 0 and i0 <= 496 and 4294967296e0 <= 1 + i0 - i1 and 4294967296e0 <= 1 + i0 and 4294967296e0 >= -4294967294 + i0 and i1 <= i0 and 4294967296e1 <= i0 - i1 and 4294967296e1 >= -4294967295 + i0 and 4294967296e1 <= i0) }) Could you please advise me what can be improved in the the current analysis? > Why did you copy this code, instead of exposing the carries_deps functions > from graphite-dependences? If I'm not mistaken, the carries_deps functions can't be called in graphite-isl-ast-to-gimple.c. Should we add its declaration to graphite-poly.h to allow this? -- Cheers, Roman Gareev. vect-pr43423.c.114t.vect(cloog) Description: Binary data vect-pr43423.c.114t.vect(isl) Description: Binary data
Re: [GSoC] checking for the loop parallelism
Sorry for misprints > Graphite successfully passes all the tests from > libgomp/testsuite/libgomp.graphite except graphite-isl-ast-to-gimple.c > and graphite-poly.h except force-parallel-5.c and force-parallel-8.c -- Cheers, Roman Gareev.
Re: [GSoC] checking for the loop parallelism
> Those waw dependences seem to be correct. Should even the previous analysis > only mark the j-loop as parallel? The previous and the current analysis mark the j-loop as nonparallelizable. (Possibly, I don't fully understand the question. Could you please reformulate it?) -- Cheers, Roman Gareev.
[GSoC] Addition of ISL AST generation to Graphite
These patches add ISL AST generation to graphite, which can be chosen by the fgraphite-code-generator=[isl|cloog] switch. The first patch makes initial renaming of gloog and gloog_error to graphite_regenerate_ast_cloog and graphite_regenerate_error, respectively. The second one adds new files with generation of ISL AST, new switch, new testcase that checks that the dump is generated. Is it fine for trunk? P.S. My copyright assignment has been already processed. -- Cheers, Roman Gareev ChangeLog_entry1 Description: Binary data ChangeLog_entry2 Description: Binary data patch1 Description: Binary data patch2 Description: Binary data
Re: [GSoC] Addition of ISL AST generation to Graphite
Thank you for the review! -- Cheers, Roman Gareev ChangeLog_entry1 Description: Binary data ChangeLog_entry2 Description: Binary data patch1 Description: Binary data patch2 Description: Binary data
Re: [GSoC] Addition of ISL AST generation to Graphite
.h +++ b/gcc/graphite-htab.h @@ -22,7 +22,14 @@ along with GCC; see the file COPYING3. If not see #define GCC_GRAPHITE_HTAB_H #include "hash-table.h" -#include "graphite-clast-to-gimple.h" + +/* Stores BB's related PBB. */ + +struct bb_pbb_def +{ + basic_block bb; + poly_bb_p pbb; +}; /* Hashtable helpers. */ @@ -52,7 +59,6 @@ bb_pbb_hasher::equal (const value_type *bp1, const compare_type *bp2) typedef hash_table bb_pbb_htab_type; -extern bool gloog (scop_p, bb_pbb_htab_type); poly_bb_p find_pbb_via_hash (bb_pbb_htab_type, basic_block); bool loop_is_parallel_p (loop_p, bb_pbb_htab_type, int); scop_p get_loop_body_pbbs (loop_p, bb_pbb_htab_type, vec *); diff --git a/gcc/graphite.c b/gcc/graphite.c index 2e1f439..28909ca 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -301,7 +301,7 @@ graphite_transform_loops (void) if (POLY_SCOP_P (scop) && apply_poly_transforms (scop) - && gloog (scop, bb_pbb_mapping)) + && graphite_regenerate_ast_cloog (scop, bb_pbb_mapping)) need_cfg_cleanup_p = true; } ChangeLog_entry1 Description: Binary data ChangeLog_entry2 Description: Binary data diff --git a/gcc/Makefile.in b/gcc/Makefile.in index e74bb67..39cb7bd 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1250,6 +1250,7 @@ OBJS = \ graphite.o \ graphite-blocking.o \ graphite-clast-to-gimple.o \ + graphite-isl-ast-to-gimple.o \ graphite-dependences.o \ graphite-interchange.o \ graphite-optimize-isl.o \ diff --git a/gcc/common.opt b/gcc/common.opt index 5c3f834..731aaf5 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1250,6 +1250,19 @@ fgraphite-identity Common Report Var(flag_graphite_identity) Optimization Enable Graphite Identity transformation +fgraphite-code-generator= +Common Report RejectNegative Joined Optimization Enum(fgraphite_generator) Var(flag_graphite_code_gen) Init(FGRAPHITE_CODE_GEN_CLOOG) +Choose code generator of Graphite + +Enum +Name(fgraphite_generator) Type(enum fgraphite_generator) UnknownError(unknown code generator of graphite %qs) + +EnumValue +Enum(fgraphite_generator) String(isl) Value(FGRAPHITE_CODE_GEN_ISL) + +EnumValue +Enum(fgraphite_generator) String(cloog) Value(FGRAPHITE_CODE_GEN_CLOOG) + fhoist-adjacent-loads Common Report Var(flag_hoist_adjacent_loads) Optimization Enable hoisting adjacent loads to encourage generating conditional move diff --git a/gcc/flag-types.h b/gcc/flag-types.h index ed00046..5aa8b36 100644 --- a/gcc/flag-types.h +++ b/gcc/flag-types.h @@ -252,4 +252,10 @@ enum lto_partition_model { LTO_PARTITION_MAX = 4 }; +/* The code generator used by graphite */ +enum fgraphite_generator { + FGRAPHITE_CODE_GEN_ISL = 0, + FGRAPHITE_CODE_GEN_CLOOG = 1 +}; + #endif /* ! GCC_FLAG_TYPES_H */ diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c new file mode 100644 index 000..6ddaa28 --- /dev/null +++ b/gcc/graphite-isl-ast-to-gimple.c @@ -0,0 +1,134 @@ +/* Translation of ISL AST to Gimple. + Copyright (C) 2014 Free Software Foundation, Inc. + Contributed by Roman Gareev . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" + +#include +#include +#include +#include + +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "basic-block.h" +#include "tree-ssa-alias.h" +#include "internal-fn.h" +#include "gimple-expr.h" +#include "is-a.h" +#include "gimple.h" +#include "gimple-iterator.h" +#include "tree-ssa-loop.h" +#include "tree-pass.h" +#include "cfgloop.h" +#include "tree-data-ref.h" +#include "sese.h" + +#include "graphite-poly.h" +#include "graphite-isl-ast-to-gimple.h" + +/* This flag is set when an error occurred during the translation of + ISL AST to Gimple. */ + +static bool graphite_regenerate_error; + +/* Prints NODE to FILE. */ + +void +print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node, + __isl_keep isl_ctx *ctx) +{ + isl_printer *prn = isl_printer_to_file (ctx, file); + prn = isl_printer_set_output_format (prn, ISL_FORMAT_C); + prn = isl_printer_print_ast_node (prn, node);
Fwd: [PATCH] fix PR testsuite/64145
Looks good to me. Thank you. 2014-12-03 2:09 GMT+05:00 Jack Howarth : > The attached patch fixes the regression in the > gcc/testsuite/gcc.dg/graphite/isl-codegen-loop-dumping.c testcase > caused by the accidental removal of -fgraphite-identity from > dg-options at r217315. Okay for gcc trunk? > Jack -- Cheers, Roman Gareev.
Re: changing a collision resolution strategy of the symbol table of identifiers
These are statistically significant differences: increasing by 0.23% for the version 4.8.0, increasing by 0.21% for the version 4.8.1, decreasing by 0.686% for trunk. These are new row numbers: 2013-11-05 Roman Gareev : > 2013/10/31 Florian Weimer : >> On 10/20/2013 02:55 PM, Roman Gareev wrote: >>> >>> During testing of the linux kernel (3.8.8) compilation time, the >>> acquired results were the following: increasing by 0.17% for the >>> version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing >>> by 0.598% for trunk (this are average values). >> >> >> Can you share the raw numbers? Are the differences statistically >> significant? >> >> -- >> Florian Weimer / Red Hat Product Security Team > > These are the row numbers. I'll share results of checking for > statistical significance as soon as more compilations are made. -- C уважением, Гареев Роман. trunk_original Description: Binary data trunk Description: Binary data 4.8.1_original Description: Binary data 4.8.1_modified Description: Binary data 4.8.0_original Description: Binary data 4.8.0_modified Description: Binary data
[PATCH] Fix bug 59586
This patch fixes the following bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59586. The segfault is caused by NULL arguments passed to compute_deps by loop_level_carries_dependences. This causes an assignment of NULL values to the no_source parameters of compute_deps. They are passed to subtract_commutative_associative_deps and dereferenced. However, this NULL arguments are appropriate for the algorithm used in loop_level_carries_dependences. It uses compute_deps for finding RAW, WAR and WAW dependences of all basic blocks in the body of the given loop. Subsequently, it tries to determine presence of these dependences at the given level. Therefore it maps the relation of the dependences to the relation of the corresponding time-stamps and intersects the result with the relation in which all the inputs before the DEPTH occur at the same time as the output, and the input at the DEPTH occurs before output. If the intersection is not empty, some dependences are carried by the DEPTH we currently check and the loop is consequently not parallel. This patch tries to avoid the problem by addition to subtract_commutative_associative_deps of NULL checking of the no_source statements. Tested x86_64-unknown-linux-gnu, applying to 4.8.3 and trunk. 2014-03-07 Roman Gareev gcc/ * graphite-dependences.c (subtract_commutative_associative_deps): Add NULL checking of the following variables: must_raw_no_source, may_raw_no_source, must_war_no_source, may_war_no_source, must_waw_no_source, may_waw_no_source. gcc/testsuite/gfortran.dg/graphite/graphite.exp: Run corresponding tests in new mode. gcc/testsuite/gfortran.dg/graphite/parallelize-all-1.f: New testcase. diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c index b0f8680..f382233 100644 --- a/gcc/graphite-dependences.c +++ b/gcc/graphite-dependences.c @@ -426,22 +426,48 @@ subtract_commutative_associative_deps (scop_p scop, *must_raw = isl_union_map_subtract (*must_raw, x_must_raw); *may_raw = isl_union_map_subtract (*may_raw, x_may_raw); - *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source, - x_must_raw_no_source); - *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source, - x_may_raw_no_source); + + if (must_raw_no_source) + *must_raw_no_source = isl_union_map_subtract (*must_raw_no_source, + x_must_raw_no_source); + else + isl_union_map_free (x_must_raw_no_source); + + if (may_raw_no_source) + *may_raw_no_source = isl_union_map_subtract (*may_raw_no_source, + x_may_raw_no_source); + else + isl_union_map_free (x_may_raw_no_source); + *must_war = isl_union_map_subtract (*must_war, x_must_war); *may_war = isl_union_map_subtract (*may_war, x_may_war); - *must_war_no_source = isl_union_map_subtract (*must_war_no_source, - x_must_war_no_source); - *may_war_no_source = isl_union_map_subtract (*may_war_no_source, - x_may_war_no_source); + + if (must_war_no_source) + *must_war_no_source = isl_union_map_subtract (*must_war_no_source, + x_must_war_no_source); + else + isl_union_map_free (x_must_war_no_source); + + if (may_war_no_source) + *may_war_no_source = isl_union_map_subtract (*may_war_no_source, + x_may_war_no_source); + else + isl_union_map_free (x_may_war_no_source); + *must_waw = isl_union_map_subtract (*must_waw, x_must_waw); *may_waw = isl_union_map_subtract (*may_waw, x_may_waw); - *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source, - x_must_waw_no_source); - *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source, - x_may_waw_no_source); + + if (must_waw_no_source) + *must_waw_no_source = isl_union_map_subtract (*must_waw_no_source, + x_must_waw_no_source); + else + isl_union_map_free (x_must_waw_no_source); + + if (may_waw_no_source) + *may_waw_no_source = isl_union_map_subtract (*may_waw_no_source, + x_may_waw_no_source); + else + isl_union_map_free (x_may_waw_no_source); } isl_union_map_free (original); diff --git a/gcc/testsuite/gfortran.dg/graphite/graphite.exp b/gcc/testsuite/gfortran.dg/graphite/graphite.exp index c3aad13..3833e43 100644 --- a/gcc/testsuite/gfortran.dg/graphite/graphite.exp +++ b/gcc/testsuite/gfortran.dg/graphite/graphite.exp @@ -44,6 +44,7 @@ set interchange_files [lsort [glob -nocomplain $srcdir/$subdir/interchange-*.\[f set scop_files[lsort [glob -nocomplain $srcdir/$subdir/scop-*.\[fF\]{,90,95,03,08} ] ] set run_id_files [lsort [glob -nocomplain $srcdir/$subdir/run-id-*.\[fF\]{,90,95,03,08} ] ] set vect_files[lsort [glob -nocomplain $srcdir/$subdir/vect-*.\[fF\]{,90,95,03,08} ] ] +set parallelize_files [lsort [glob -nocomplain $srcdir/$subdir/parallelize-all-*.\[fF\]{,90,95,03,08} ] ] # Tests to be compiled. set dg-do-what-default compile @@ -51,6 +52,7 @@ gfortran-dg-runtest $scop_files"-O2 -fgra
Re: [PATCH] Fix bug 59586
Sorry, an error occurred somewhere. Below is an attachment with the patch and ChangeLog entry. > This patch fixes the following bug: > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59586. > The segfault is caused by NULL arguments passed to compute_deps by > loop_level_carries_dependences. > This causes an assignment of NULL values to the no_source parameters > of compute_deps. > They are passed to subtract_commutative_associative_deps and dereferenced. > > However, this NULL arguments are appropriate for the algorithm used > in loop_level_carries_dependences. It uses compute_deps > for finding RAW, WAR and WAW dependences of all basic blocks > in the body of the given loop. Subsequently, it tries to > determine presence of these dependences at the given level. > Therefore it maps the relation of the dependences to the relation > of the corresponding time-stamps and intersects the result with > the relation in which all the inputs before the DEPTH occur at the > same time as the output, and the input at the DEPTH occurs before output. > If the intersection is not empty, some dependences are carried > by the DEPTH we currently check and the loop is consequently not parallel. > > This patch tries to avoid the problem by addition to > subtract_commutative_associative_deps > of NULL checking of the no_source statements. > > Tested x86_64-unknown-linux-gnu, applying to 4.8.3 and trunk. patch Description: Binary data ChangeLog_entry Description: Binary data
Re: [PATCH] Fix bug 59586
> I am slightly surprised why this change is necessary. Roman, can you shade > some light on this change. > > >> # Vectorizer tests, to be run or compiled, depending on target >> capabilities. >> if [check_vect_support_and_set_flags] { >> diff --git a/gcc/testsuite/gfortran.dg/graphite/parallelize-all-1.f >> b/gcc/testsuite/gfortran.dg/graphite/parallelize-all-1.f >> new file mode 100644 >> index 000..e1156f8 >> --- /dev/null >> +++ b/gcc/testsuite/gfortran.dg/graphite/parallelize-all-1.f >> @@ -0,0 +1,9 @@ >> + subroutine subsm ( n, x, xp, xx) >> + integern, m, x(n),xp(n), xx(n), gg(n), dd_p >> + do 55 i=1, n >> + dd_p = dd_p + (x(i) - xx(i))*gg(i) >> + 55 continue >> + if ( dd_p .gt. 0 ) then >> + call dcopy( n, xp, 1, x, 1 ) >> + endif >> + end >> > I tried to add a testcase, which uses example introduced in bug report. Sorry for making an error in encoding options. -- Roman Gareev
Re: [PATCH] Fix bug 59586
Thank you for your comment! 2014-03-10 20:26 GMT+06:00 Jakub Jelinek : > On Mon, Mar 10, 2014 at 03:23:22PM +0100, Tobias Grosser wrote: >> >+++ b/gcc/testsuite/gfortran.dg/graphite/graphite.exp >> >@@ -44,6 +44,7 @@ set interchange_files [lsort [glob -nocomplain >> >$srcdir/$subdir/interchange-*.\[f >> > set scop_files[lsort [glob -nocomplain >> >$srcdir/$subdir/scop-*.\[fF\]{,90,95,03,08} ] ] >> > set run_id_files [lsort [glob -nocomplain >> >$srcdir/$subdir/run-id-*.\[fF\]{,90,95,03,08} ] ] >> > set vect_files[lsort [glob -nocomplain >> >$srcdir/$subdir/vect-*.\[fF\]{,90,95,03,08} ] ] >> >+set parallelize_files [lsort [glob -nocomplain >> >$srcdir/$subdir/parallelize-all-*.\[fF\]{,90,95,03,08} ] ] >> > >> > # Tests to be compiled. >> > set dg-do-what-default compile >> >@@ -51,6 +52,7 @@ gfortran-dg-runtest $scop_files"-O2 -fgraphite >> >-fdump-tree-graphite-all" >> > gfortran-dg-runtest $id_files "-O2 -fgraphite-identity >> >-ffast-math" >> > gfortran-dg-runtest $interchange_files "-O2 -floop-interchange >> >-fno-loop-block -fno-loop-strip-mine -ffast-math -fdump-tree-graphite-all" >> > gfortran-dg-runtest $block_files "-O2 -floop-block >> >-fno-loop-strip-mine -fno-loop-interchange -ffast-math >> >-fdump-tree-graphite-all" >> >+gfortran-dg-runtest $parallelize_files "-Ofast -floop-parallelize-all" >> >> I am slightly surprised why this change is necessary. Roman, can you >> shade some light on this change. > > I agree this is really horribly ugly. Can't you just use > ! { dg-additional-options "-Ofast -floop-parallelize-all" } > in the testcase? > I thought the ugliness of encoding options in test filenames was */vect/ > only, apparently it affects also */graphite/ :(. > > Jakub -- Roman Gareev
Fix PR59586
This patch fixes PR59586. The segfault is caused by NULL arguments passed to compute_deps by loop_level_carries_dependences. This causes an assignment of NULL values to the no_source parameters of compute_deps. They are passed to subtract_commutative_associative_deps and dereferenced. However, this NULL arguments are appropriate for the algorithm used in loop_level_carries_dependences. It uses compute_deps for finding RAW, WAR and WAW dependences of all basic blocks in the body of the given loop. Subsequently, it tries to determine presence of these dependences at the given level. Therefore it maps the relation of the dependences to the relation of the corresponding time-stamps and intersects the result with the relation in which all the inputs before the DEPTH occur at the same time as the output, and the input at the DEPTH occurs before output. If the intersection is not empty, some dependences are carried by the DEPTH we currently check and the loop is consequently not parallel. This patch tries to avoid the problem by adding NULL checking of the no_source statements to subtract_commutative_associative_deps. Tested x86_64-unknown-linux-gnu, applying to 4.8.3 and trunk. ChangeLog_entry Description: Binary data patch Description: Binary data
Re: Fix PR59586
Hi Mircea, sorry for making you wait. -- Roman Gareev patch Description: Binary data ChangeLog_entry Description: Binary data
Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?
Hi Tobias, I've attached a patch which removes using of CLooG library from Graphite. Is it fine for trunk? -- Cheers, Roman Gareev. Index: gcc/Makefile.in === --- gcc/Makefile.in (revision 217264) +++ gcc/Makefile.in (working copy) @@ -1244,7 +1244,6 @@ graphds.o \ graphite.o \ graphite-blocking.o \ - graphite-clast-to-gimple.o \ graphite-isl-ast-to-gimple.o \ graphite-dependences.o \ graphite-interchange.o \ Index: gcc/graphite-blocking.c === --- gcc/graphite-blocking.c (revision 217264) +++ gcc/graphite-blocking.c (working copy) @@ -28,11 +28,7 @@ #include #include #include -#ifdef HAVE_cloog -#include -#include #endif -#endif #include "system.h" #include "coretypes.h" Index: gcc/graphite-clast-to-gimple.c === --- gcc/graphite-clast-to-gimple.c (revision 217264) +++ gcc/graphite-clast-to-gimple.c (working copy) @@ -1,1736 +0,0 @@ -/* Translation of CLAST (CLooG AST) to Gimple. - Copyright (C) 2009-2014 Free Software Foundation, Inc. - Contributed by Sebastian Pop . - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 3, or (at your option) -any later version. - -GCC is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -<http://www.gnu.org/licenses/>. */ - -#include "config.h" - -#ifdef HAVE_cloog -#include -#include -#include -#include -#include -#include -#include -#include -#if defined(__cplusplus) -extern "C" { -#endif -#include -#if defined(__cplusplus) -} -#endif -#include -#include -#endif - -#include "system.h" -#include "coretypes.h" -#include "diagnostic-core.h" -#include "tree.h" -#include "predict.h" -#include "vec.h" -#include "hashtab.h" -#include "hash-set.h" -#include "machmode.h" -#include "tm.h" -#include "hard-reg-set.h" -#include "input.h" -#include "function.h" -#include "dominance.h" -#include "cfg.h" -#include "basic-block.h" -#include "tree-ssa-alias.h" -#include "internal-fn.h" -#include "gimple-expr.h" -#include "is-a.h" -#include "gimple.h" -#include "gimple-iterator.h" -#include "gimplify-me.h" -#include "gimple-ssa.h" -#include "tree-ssa-loop-manip.h" -#include "tree-ssa-loop.h" -#include "tree-into-ssa.h" -#include "tree-pass.h" -#include "cfgloop.h" -#include "tree-chrec.h" -#include "tree-data-ref.h" -#include "tree-scalar-evolution.h" -#include "sese.h" - -#ifdef HAVE_cloog -#include "cloog/cloog.h" -#include "graphite-poly.h" -#include "graphite-clast-to-gimple.h" -#include "graphite-htab.h" - -typedef const struct clast_expr *clast_name_p; - -#ifndef CLOOG_LANGUAGE_C -#define CLOOG_LANGUAGE_C LANGUAGE_C -#endif - - -/* Converts a GMP constant VAL to a tree and returns it. */ - -static tree -gmp_cst_to_tree (tree type, mpz_t val) -{ - tree t = type ? type : integer_type_node; - mpz_t tmp; - - mpz_init (tmp); - mpz_set (tmp, val); - wide_int wi = wi::from_mpz (t, tmp, true); - mpz_clear (tmp); - - return wide_int_to_tree (t, wi); -} - -/* Sets RES to the min of V1 and V2. */ - -static void -value_min (mpz_t res, mpz_t v1, mpz_t v2) -{ - if (mpz_cmp (v1, v2) < 0) -mpz_set (res, v1); - else -mpz_set (res, v2); -} - -/* Sets RES to the max of V1 and V2. */ - -static void -value_max (mpz_t res, mpz_t v1, mpz_t v2) -{ - if (mpz_cmp (v1, v2) < 0) -mpz_set (res, v2); - else -mpz_set (res, v1); -} - - -/* This flag is set when an error occurred during the translation of - CLAST to Gimple. */ -static bool graphite_regenerate_error; - -/* Verifies properties that GRAPHITE should maintain during translation. */ - -static inline void -graphite_verify (void) -{ -#ifdef ENABLE_CHECKING - verify_loop_structure (); - verify_loop_closed_ssa (true); -#endif -} - -/* Stores the INDEX in a vector and the loop nesting LEVEL for a given - clast NAME. BOUND_ONE and BOUND_TWO represent the exact lower and - upper bounds that can be inferred from the polyhedral
Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?
> The patch looks great. The only piece I think we missed is the > fgraphite-code-generator flag. I would propose to remove it as well in this > commit, as it does not have any effect any more. In this case, we’ll also have to change tests which use fgraphite-code-generator flag (isl-ast-gen-blocks-1.c, isl-ast-gen-blocks-2.c, isl-ast-gen-blocks-3.c, isl-ast-gen-blocks-4.c, isl-ast-gen-if-1.c, isl-ast-gen-if-2.c, isl-ast-gen-single-loop-1.c, isl-ast-gen-single-loop-2.c, isl-ast-gen-user-1.c, isl-codegen-loop-dumping.c). Maybe we should do this in the next patch? -- Cheers, Roman Gareev.
Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?
> Sure. We should drop the flag in these test cases. > > This seems to make sense, as they now test something different and the flag > removal would reflect this. > > I personally would include this in the same patch. Would this be difficult? I don’t think that it could be difficult. I just wanted to reduce the size of a patch which can be found below. -- Cheers, Roman Gareev. 2014-11-9 Roman Gareev [gcc/] * Makefile.in: Remove the compilation of graphite-clast-to-gimple.o. * common.opt: Remove using of fgraphite-code-generator flag. * flag-types.h: Likewise. * graphite.c: Remove using of CLooG. * graphite-blocking.c: Likewise. * graphite-dependences.c: Likewise. * graphite-poly.c: Likewise. * graphite-poly.h: Likewise. * graphite-scop-detection.c: Likewise. * graphite-sese-to-poly.c: Likewise. * graphite-clast-to-gimple.c: Removed. * graphite-clast-to-gimple.h: Likewise. * graphite-htab.h: Likewise. [gcc/testsuite] * gcc.dg/graphite/isl-ast-gen-blocks-1.c: Remove using of fgraphite-code-generator flag. * gcc.dg/graphite/isl-ast-gen-blocks-2.c: * gcc.dg/graphite/isl-ast-gen-blocks-3.c: * gcc.dg/graphite/isl-ast-gen-user-1.c: * gcc.dg/graphite/isl-codegen-loop-dumping.c: * gcc.dg/graphite/pr35356-2.c: Index: gcc/Makefile.in === --- gcc/Makefile.in (revision 217264) +++ gcc/Makefile.in (working copy) @@ -1244,7 +1244,6 @@ graphds.o \ graphite.o \ graphite-blocking.o \ - graphite-clast-to-gimple.o \ graphite-isl-ast-to-gimple.o \ graphite-dependences.o \ graphite-interchange.o \ Index: gcc/common.opt === --- gcc/common.opt (revision 217264) +++ gcc/common.opt (working copy) @@ -1293,20 +1293,7 @@ fgraphite-identity Common Report Var(flag_graphite_identity) Optimization Enable Graphite Identity transformation - -fgraphite-code-generator= -Common Report RejectNegative Joined Optimization Enum(fgraphite_generator) Var(flag_graphite_code_gen) Init(FGRAPHITE_CODE_GEN_ISL) -Choose code generator of Graphite -Enum -Name(fgraphite_generator) Type(enum fgraphite_generator) UnknownError(unknown code generator of graphite %qs) - -EnumValue -Enum(fgraphite_generator) String(isl) Value(FGRAPHITE_CODE_GEN_ISL) - -EnumValue -Enum(fgraphite_generator) String(cloog) Value(FGRAPHITE_CODE_GEN_CLOOG) - fhoist-adjacent-loads Common Report Var(flag_hoist_adjacent_loads) Optimization Enable hoisting adjacent loads to encourage generating conditional move Index: gcc/flag-types.h === --- gcc/flag-types.h(revision 217264) +++ gcc/flag-types.h(working copy) @@ -263,10 +263,4 @@ LTO_PARTITION_MAX = 4 }; -/* The code generator used by graphite */ -enum fgraphite_generator { - FGRAPHITE_CODE_GEN_ISL = 0, - FGRAPHITE_CODE_GEN_CLOOG = 1 -}; - #endif /* ! GCC_FLAG_TYPES_H */ Index: gcc/graphite-blocking.c === --- gcc/graphite-blocking.c (revision 217264) +++ gcc/graphite-blocking.c (working copy) @@ -28,11 +28,7 @@ #include #include #include -#ifdef HAVE_cloog -#include -#include #endif -#endif #include "system.h" #include "coretypes.h" Index: gcc/graphite-clast-to-gimple.c === --- gcc/graphite-clast-to-gimple.c (revision 217264) +++ gcc/graphite-clast-to-gimple.c (working copy) @@ -1,1736 +0,0 @@ -/* Translation of CLAST (CLooG AST) to Gimple. - Copyright (C) 2009-2014 Free Software Foundation, Inc. - Contributed by Sebastian Pop . - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 3, or (at your option) -any later version. - -GCC is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING3. If not see -<http://www.gnu.org/licenses/>. */ - -#include "config.h" - -#ifdef HAVE_cloog -#include -#include -#include -#include -#include -#include -#include -#include -#if defined(__cplusplus) -extern "C" { -#endif -#include -#if defined(__cplusplus) -} -#endif -#include -#include -#endif - -#include "system.h" -#include "coretypes.h" -#include "diagnostic-core.h" -#includ
Re: [GSoC] checking for the loop parallelism
> I would expect the to mark the i loop as non-parallel, but the j-loop > as parallel. What is the partial schedule, the set of dependences and > the dimension you check for both the i and the j loop? Yes, you are right. The i loop is non-parallel and j-loop is parallel. I've found that this substraction “ int dimension = isl_space_dim (schedule_space, isl_dim_out) – 1;” was wrong. The attached patch contains the improved version of checking for the loop parallelism, which passes all the tests from libgomp/testsuite/libgomp.graphite except graphite-isl-ast-to-gimple.c. P.S.: I've added checking of the ux's emptiness and of the x's value, because ux is empty for specific test cases and produces the following error: “/home/roman/graphite_stuff/isl-0.12.2/isl_union_map.c:418: union map needs to contain elements in exactly one space” -- Cheers, Roman Gareev. 2014-08-4 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: Add a new struct ast_build_info. (translate_isl_ast_for_loop): Add checking of the flag_loop_parallelize_all. (ast_build_before_for): New function. (scop_to_isl_ast): Add checking of the flag_loop_parallelize_all. * graphite-dependences.c: Move the defenition of the scop_get_dependences from graphite-optimize-isl.c to this file. (apply_schedule_on_deps): Add checking of the ux's emptiness. (carries_deps): Add checking of the x's value. * graphite-optimize-isl.c: Move the defenition of the scop_get_dependences to graphite-dependences.c. * graphite-poly.h: Add declarations of scop_get_dependences and carries_deps. Index: gcc/graphite-dependences.c === --- gcc/graphite-dependences.c (revision 213256) +++ gcc/graphite-dependences.c (working copy) @@ -53,6 +53,35 @@ #include "graphite-poly.h" #include "graphite-htab.h" +isl_union_map * +scop_get_dependences (scop_p scop) +{ + isl_union_map *dependences; + + if (!scop->must_raw) +compute_deps (scop, SCOP_BBS (scop), + &scop->must_raw, &scop->may_raw, + &scop->must_raw_no_source, &scop->may_raw_no_source, + &scop->must_war, &scop->may_war, + &scop->must_war_no_source, &scop->may_war_no_source, + &scop->must_waw, &scop->may_waw, + &scop->must_waw_no_source, &scop->may_waw_no_source); + + dependences = isl_union_map_copy (scop->must_raw); + dependences = isl_union_map_union (dependences, +isl_union_map_copy (scop->must_war)); + dependences = isl_union_map_union (dependences, +isl_union_map_copy (scop->must_waw)); + dependences = isl_union_map_union (dependences, +isl_union_map_copy (scop->may_raw)); + dependences = isl_union_map_union (dependences, +isl_union_map_copy (scop->may_war)); + dependences = isl_union_map_union (dependences, +isl_union_map_copy (scop->may_waw)); + + return dependences; +} + /* Add the constraints from the set S to the domain of MAP. */ static isl_map * @@ -263,6 +292,11 @@ ux = isl_union_map_copy (deps); ux = isl_union_map_apply_domain (ux, isl_union_map_copy (trans)); ux = isl_union_map_apply_range (ux, trans); + if (isl_union_map_is_empty (ux)) +{ + isl_union_map_free (ux); + return NULL; +} x = isl_map_from_union_map (ux); return x; @@ -300,7 +334,7 @@ in which all the inputs before DEPTH occur at the same time as the output, and the input at DEPTH occurs before output. */ -static bool +bool carries_deps (__isl_keep isl_union_map *schedule, __isl_keep isl_union_map *deps, int depth) @@ -315,6 +349,8 @@ return false; x = apply_schedule_on_deps (schedule, deps); + if (x == NULL) +return false; space = isl_map_get_space (x); space = isl_space_range (space); lex = isl_map_lex_le (space); Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 213262) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -73,6 +73,14 @@ static int graphite_expression_type_precision = 128 <= max_mode_int_precision ? 128 : max_mode_int_precision; +struct ast_build_info +{ + ast_build_info() +: is_parallelizable(false) + { }; + bool is_parallelizable; +}; + /* Converts a GMP constant VAL to a tree and returns it. */ static tree @@ -435,7 +443,15 @@ redirect_edge_succ_nodup (next_e, after); set_immed
Re: [GSoC] checking for the loop parallelism
Sorry for misprint. It passes all the tests from libgomp/testsuite/libgomp.graphite > The attached patch contains the improved version of checking for the > loop parallelism, which passes all the tests from > libgomp/testsuite/libgomp.graphite except > graphite-isl-ast-to-gimple.c. -- Cheers, Roman Gareev.
[GSoC] the separate option for all dimensions
I've attached the patch, which sets the separate option for all dimensions. Is it fine for trunk? -- Cheers, Roman Gareev. 2014-08-05 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (set_options): New function. (scop_to_isl_ast): Add calling of set_options. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 213619) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -867,6 +867,25 @@ return id; } +/* Set the separate option for all dimensions. + This helps to reduce control overhead. */ + +static __isl_give isl_ast_build * +set_options (__isl_take isl_ast_build *control, +__isl_keep isl_union_map *schedule) +{ + isl_ctx *ctx = isl_union_map_get_ctx (schedule); + isl_space *range_space = isl_space_set_alloc (ctx, 0, 1); + range_space = +isl_space_set_tuple_name (range_space, isl_dim_set, "separate"); + isl_union_set *range = +isl_union_set_from_set (isl_set_universe (range_space)); + isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule)); + domain = isl_union_set_universe (domain); + isl_union_map *options = isl_union_map_from_domain_and_range (domain, range); + return isl_ast_build_set_options (control, options); +} + static __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop, ivs_params &ip) { @@ -879,6 +898,7 @@ add_parameters_to_ivs_params (scop, ip); isl_union_map *schedule_isl = generate_isl_schedule (scop); isl_ast_build *context_isl = generate_isl_context (scop); + context_isl = set_options (context_isl, schedule_isl); isl_union_map *dependences = NULL; if (flag_loop_parallelize_all) {
Re: [GSoC] the separate option for all dimensions
I've tested the modified version of Graphite using the gcc test suite and haven't found out new failed tests. However, pr35356-2.c is still not suitable for testing. The ISL AST generated from its source code doesn't contain MIN or MAX. if (k <= -1) { for (int c1 = 0; c1 < n; c1 += 1) S_7(c1); } else if (k >= n) { for (int c1 = 0; c1 < n; c1 += 1) S_7(c1); } else { for (int c1 = 0; c1 < k; c1 += 1) S_7(c1); S_6(k); for (int c1 = k + 1; c1 < n; c1 += 1) S_7(c1); } Should we make pr35356-2.c to be similar to isl-codegen-loop-dumping.c by replacing “MIN_EXPR\[^\\n\\r]*;" and "MAX_EXPR\[^\\n\\r]*;" with the regexp, which contains the the above-mentioned isl ast? -- Cheers, Roman Gareev.
[GSoC] Elimination of CLooG library installation dependency
Hi Tobias, I've attached the patch, which should eliminate CLooG library installation dependency from GCC. The CLooG AST generator is still the main code generator, but the isl ast generator will be chosen in case of nonavailability of CLooG library. However, I've found out a problem. Almost all the functions of the ISL cannot be used without installed CLooG. (I get errors which contain “undefined reference to...”). Maybe I missed something. What do you think about this? I also have a few questions about gcc. Could you please answer them? Should Makefile.in be regenerated or manually changed? (I haven't found out how to regenerate it.) I've used printf to print “The CLooG code generator cannot be used +(CLooG is not available). The ISL code generator was chosen.\n”. Should another function be used for this purpose? -- Cheers, Roman Gareev. Index: Makefile.in === --- Makefile.in (revision 213622) +++ Makefile.in (working copy) @@ -219,6 +219,7 @@ HOST_LIBS="$(STAGE1_LIBS)"; export HOST_LIBS; \ GMPLIBS="$(HOST_GMPLIBS)"; export GMPLIBS; \ GMPINC="$(HOST_GMPINC)"; export GMPINC; \ + ISLLIBS="$(HOST_ISLLIBS)"; export ISLLIBS; \ ISLINC="$(HOST_ISLINC)"; export ISLINC; \ CLOOGLIBS="$(HOST_CLOOGLIBS)"; export CLOOGLIBS; \ CLOOGINC="$(HOST_CLOOGINC)"; export CLOOGINC; \ @@ -310,6 +311,7 @@ HOST_GMPINC = @gmpinc@ # Where to find ISL +HOST_ISLLIBS = @isllibs@ HOST_ISLINC = @islinc@ # Where to find CLOOG Index: Makefile.tpl === --- Makefile.tpl(revision 213622) +++ Makefile.tpl(working copy) @@ -222,6 +222,7 @@ HOST_LIBS="$(STAGE1_LIBS)"; export HOST_LIBS; \ GMPLIBS="$(HOST_GMPLIBS)"; export GMPLIBS; \ GMPINC="$(HOST_GMPINC)"; export GMPINC; \ + ISLLIBS="$(HOST_ISLLIBS)"; export ISLLIBS; \ ISLINC="$(HOST_ISLINC)"; export ISLINC; \ CLOOGLIBS="$(HOST_CLOOGLIBS)"; export CLOOGLIBS; \ CLOOGINC="$(HOST_CLOOGINC)"; export CLOOGINC; \ @@ -313,6 +314,7 @@ HOST_GMPINC = @gmpinc@ # Where to find ISL +HOST_ISLLIBS = @isllibs@ HOST_ISLINC = @islinc@ # Where to find CLOOG Index: gcc/config.in === --- gcc/config.in (revision 213622) +++ gcc/config.in (working copy) @@ -1705,6 +1705,10 @@ #undef HAVE_cloog #endif +/* Define if isl is in use. */ +#ifndef USED_FOR_TARGET +#undef HAVE_isl +#endif /* Define if F_SETLKW supported by fcntl. */ #ifndef USED_FOR_TARGET Index: gcc/configure === --- gcc/configure (revision 213622) +++ gcc/configure (working copy) @@ -27888,9 +27888,14 @@ +if test "x${ISLLIBS}" != "x" ; then +$as_echo "#define HAVE_isl 1" >>confdefs.h +fi + + if test "x${CLOOGLIBS}" != "x" ; then $as_echo "#define HAVE_cloog 1" >>confdefs.h Index: gcc/configure.ac === --- gcc/configure.ac(revision 213622) +++ gcc/configure.ac(working copy) @@ -5514,6 +5514,9 @@ AC_ARG_VAR(ISLLIBS,[How to link ISL]) AC_ARG_VAR(ISLINC,[How to find ISL include files]) +if test "x${ISLLIBS}" != "x" ; then + AC_DEFINE(HAVE_isl, 1, [Define if isl is in use.]) +fi AC_ARG_VAR(CLOOGLIBS,[How to link CLOOG]) AC_ARG_VAR(CLOOGINC,[How to find CLOOG include files]) Index: gcc/graphite-blocking.c === --- gcc/graphite-blocking.c (revision 213622) +++ gcc/graphite-blocking.c (working copy) @@ -23,14 +23,16 @@ #include "config.h" -#ifdef HAVE_cloog +#ifdef HAVE_isl #include #include #include #include +#ifdef HAVE_cloog #include #include #endif +#endif #include "system.h" #include "coretypes.h" @@ -49,7 +51,7 @@ #include "tree-data-ref.h" #include "sese.h" -#ifdef HAVE_cloog +#ifdef HAVE_isl #include "graphite-poly.h" Index: gcc/graphite-dependences.c === --- gcc/graphite-dependences.c (revision 213622) +++ gcc/graphite-dependences.c (working copy) @@ -21,15 +21,17 @@ #include "config.h" -#ifdef HAVE_cloog +#ifdef HAVE_isl #include #include #include #include #include +#ifdef HAVE_cloog #include #include #endif +#endif #include "system.h" #include "coretypes.h" @@ -49,7 +51,7 @@ #include "tree-scalar-evolution.h" #include "sese.h" -#ifdef HAVE_cloog +#
Re: [GSoC] Elimination of CLooG library installation dependency
> To commit 2), I would like you to run a wider set of tests (e.g., the LLVM > test suite). If this passes successful, we should give a headsup on the GCC > mailing list and ask other people to try the new isl support. > If now bugs have found, we switch. I've tested the modified version of Graphite using the LLVM test suite and found out regression only in two test cases: /llvm-test-suite/MultiSource/Benchmarks/ASC_Sequoia/CrystalMk/Crystal_Cholesky.c, /llvm-test suite/MultiSource/Benchmarks/Bullet Compilation of /llvm-test-suite/MultiSource/Benchmarks/ASC_Sequoia/CrystalMk/Crystal_Cholesky.c produces the following error message: /home/roman/llvm-test-suite/MultiSource/Benchmarks/ASC_Sequoia/CrystalMk/Crystal_Cholesky.c /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet Crystal_Cholesky.c: In function ‘Crystal_Cholesky’: Crystal_Cholesky.c:16:6: internal compiler error: in operator[], at vec.h:736 void Crystal_Cholesky(int nSlip, ^ 0xf1d080 vec::operator[](unsigned int) /home/roman/sec_trunk/gcc/gcc/vec.h:736 0xf1d080 vec::operator[](unsigned int) /home/roman/sec_trunk/gcc/gcc/vec.h:1202 0xf1d080 build_iv_mapping /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:608 0xf1d080 translate_isl_ast_node_user /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:644 0xf1d080 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:734 0xf1c7d0 translate_isl_ast_for_loop /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:441 0xf1c7d0 translate_isl_ast_node_for /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:580 0xf1c7d0 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:727 0xf1c3e0 translate_isl_ast_node_block /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:669 0xf1c3e0 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:738 0xf1c3e0 translate_isl_ast_node_block /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:669 0xf1c3e0 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:738 0xf1c3e0 translate_isl_ast_node_block /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:669 0xf1c3e0 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:738 0xf1c3e0 translate_isl_ast_node_block /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:669 0xf1c3e0 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:738 0xf1c3e0 translate_isl_ast_node_block /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:669 0xf1c3e0 translate_isl_ast /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:738 0xf1c7d0 translate_isl_ast_for_loop /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:441 0xf1c7d0 translate_isl_ast_node_for /home/roman/sec_trunk/gcc/gcc/graphite-isl-ast-to-gimple.c:580 It is caused by the wrong index of the iv_map (its value is 12), which is greater than its size (its value is equal to loop->num = 8 plus one). I think that we should use the value of number_of_loops for the size of the iv_map (the attached patch implements this), because it is proven to be robust. What do you think about this? The second error is produced by the executable, which is successfully compiled by /llvm-test-suite/MultiSource/Benchmarks/Bullet: “Segmentation fault (core dumped)”. I've used gdb to print stack trace: Segmentation fault (core dumped) ore was generated by `./bullet.simple'. Program terminated with signal 11, Segmentation fault. #0 upcast (colObj=0x0) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/include/BulletDynamics/Dynamics/btRigidBody.h:170 170 if (colObj->getInternalType()==btCollisionObject::CO_RIGID_BODY) (gdb) bt #0 upcast (colObj=0x0) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/include/BulletDynamics/Dynamics/btRigidBody.h:170 #1 saveKinematicState (timeStep=, this=) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/btDiscreteDynamicsWorld.cpp:113 #2 btDiscreteDynamicsWorld::stepSimulation (this=0x14a6ca0, timeStep=0.016675, maxSubSteps=1, fixedTimeStep=0.016675) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/btDiscreteDynamicsWorld.cpp:333 #3 0x00401ed8 in BenchmarkDemo::clientMoveAndDisplay ( this=0x7fff90475840) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/BenchmarkDemo.cpp:232 #4 0x00401bd2 in main (argc=, argv=) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/main.cpp:63 The executable is produced by compilation of 317 files. That's why I think that it is be better to temporary postpone the consideration. What do you think about this? -- Cheers, Roman Gareev. 2014-08-07 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (translate_isl_ast_node_user): Use nb_loops instead of loop->num + 1. [gcc/testsuite] * gcc.dg/gr
Re: [GSoC] Elimination of CLooG library installation dependency
3709551616e1 >= -18446744073709551615 + P_45 + 8i0 and 18446744073709551616e1 <= -1 + P_45 + 8i0) } [P_46, P_45] -> { : exists (e0 = floor((-1 + P_46)/4294967296): 4294967296e0 <= -1 + P_46 and 4294967296e0 >= -2147483647 + P_46 and P_46 >= -2147483648 and P_46 <= 2147483647 and P_45 >= 0 and P_45 <= 18446744073709551615) } [P_46, P_45] -> { [i0, i1, i2] -> separate[o0] } ISL AST generated by ISL: for (int c1 = 0; c1 < P_46; c1 += 1) if ((P_45 + 8 * c1) % 18446744073709551616 >= 1) S_16(c1); CLAST generated by CLooG: if (8*T_18 >= -T_17+9) { for (scat_1=0;scat_1<=T_18-1;scat_1++) { if ((8*scat_1+T_17+18446744073709551615)%18446744073709551616 <= 18446744073709551614) { (scat_1); } } } isl_codegen: [P_18, P_17] -> { S_12[i0] -> [0, i0, 0] : exists (e0 = floor((-1 + P_18)/4294967296), e1 = floor((P_17 + 8i0)/18446744073709551616): i0 >= 0 and 4294967296e0 <= -1 + P_18 and 4294967296e0 >= -4294967296 + P_18 and 4294967296e0 <= -1 + P_18 - i0 and i0 <= 2147483646 and 18446744073709551616e1 >= -18446744073709551615 + P_17 + 8i0 and 18446744073709551616e1 <= -1 + P_17 + 8i0) } [P_18, P_17] -> { : exists (e0 = floor((-1 + P_18)/4294967296): 4294967296e0 <= -1 + P_18 and 4294967296e0 >= -2147483647 + P_18 and P_18 >= -2147483648 and P_18 <= 2147483647 and P_17 >= 0 and P_17 <= 18446744073709551615) } [P_18, P_17] -> { [i0, i1, i2] -> separate[o0] } ISL AST generated by ISL: for (int c1 = 0; c1 < P_18; c1 += 1) if ((P_17 + 8 * c1) % 18446744073709551616 >= 1) S_12(c1); I think that, for example, the following code if (8*T_45 >= -T_44+9) { for (scat_1=0;scat_1<=T_45-1;scat_1++) { if ((8*scat_1+T_44+18446744073709551615)%18446744073709551616 <= 18446744073709551614) { (scat_1); } } } is equivalent to if (8*T_45 >= -T_44+9) { for (scat_1=0;scat_1<=T_45-1;scat_1++) { if ((8*scat_1+T_44)%18446744073709551616 <= -1) { (scat_1); } } } If I'm not mistaken it's not equivalent to for (int c1 = 0; c1 < P_45; c1 += 1) if ((P_44 + 8 * c1) % 18446744073709551616 >= 1) S_12(c1); Maybe the ISL generator generates wrong code. What do you think about this? -- Cheers, Roman Gareev. 2014-08-07 Roman Gareev [gcc/] * graphite-isl-ast-to-gimple.c: (translate_isl_ast_node_user): Use nb_loops instead of loop->num + 1. [gcc/testsuite] * gcc.dg/graphite/isl-ast-gen-user-1.c: New testcase. Index: gcc/graphite-isl-ast-to-gimple.c === --- gcc/graphite-isl-ast-to-gimple.c(revision 213690) +++ gcc/graphite-isl-ast-to-gimple.c(working copy) @@ -632,9 +632,9 @@ gcc_assert (GBB_BB (gbb) != ENTRY_BLOCK_PTR_FOR_FN (cfun) && "The entry block should not even appear within a scop"); - loop_p loop = gbb_loop (gbb); - iv_map.create (loop->num + 1); - iv_map.safe_grow_cleared (loop->num + 1); + int nb_loops = number_of_loops (cfun); + iv_map.create (nb_loops); + iv_map.safe_grow_cleared (nb_loops); build_iv_mapping (iv_map, gbb, user_expr, ip, SCOP_REGION (pbb->scop)); isl_ast_expr_free (user_expr); Index: gcc/testsuite/gcc.dg/graphite/isl-ast-gen-user-1.c === --- gcc/testsuite/gcc.dg/graphite/isl-ast-gen-user-1.c (revision 0) +++ gcc/testsuite/gcc.dg/graphite/isl-ast-gen-user-1.c (working copy) @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fgraphite-identity -fgraphite-code-generator=isl" } */ + +#include +#include + +static const int N = 12; + +void Crystal_Cholesky (int nSlip, int a[N][N]) +{ + int i, j, k, fdot = 0; + + for ( i = 1; i < nSlip; i++) +{ + for ( j = i+1; j < nSlip; j++) +{ + for ( k = 0; k < i; k++) +fdot += a[i][k] * a[k][j]; + a[i][j] = a[i][j] - fdot; +} + } +} + + +
Re: [GSoC] Elimination of CLooG library installation dependency
> Is this segmentation fault at compile time or at run-time? I believe it was > a segfault at run-time due to a miscompile. Yes, it's a segfault at run-time. These source codes produce wrong object files. > Possibly. Can you split the .cpp files such that you only compile a single > function with graphite and that compiling this function causes the > miscompile. This allows us to look at less code. I've tried to reduce btCollisionWorld.cpp and btCollisionDispatcher.cpp (They can be found attached). Should we ask Sven? -- Cheers, Roman Gareev. void *btAlignedAlloc (int size, int alignment); template class btAlignedAllocator { typedef btAlignedAllocator< T, Alignment> self_type; public: T *allocate (int n, const T** hint = 0) { (void) hint; return reinterpret_cast(btAlignedAlloc(sizeof (T) * n, Alignment)); } }; #include template class btAlignedObjectArray { btAlignedAllocator m_allocator; int m_size; T *m_data; public: void push_back () { T *s = (T*) m_allocator.allocate (m_size * 2); int i; for (i=0; i m_manifoldsPtr; virtual void getNewManifold (); }; void btCollisionDispatcher::getNewManifold () { m_manifoldsPtr.push_back (); } void* btAlignedAlloc (int size, int alignment); template class btAlignedAllocator { typedef btAlignedAllocator self_type; public: template btAlignedAllocator (const btAlignedAllocator& ) {} T *allocate (int n, const T **hint = 0) { (void) hint; return reinterpret_cast (btAlignedAlloc (sizeof (T) * n , Alignment)); } }; #include template class btAlignedObjectArray { btAlignedAllocator m_allocator; int m_size; T *m_data; public: void push_back (const T& _Val) { T *s = (T*) m_allocator.allocate (m_size * 2); int i; for (i=0; i btCollisionObjectArray; class btCollisionObject; class btCollisionWorld { protected: btAlignedObjectArray m_collisionObjects; public: virtual void addCollisionObject(btCollisionObject* collisionObject); }; void btCollisionWorld::addCollisionObject(btCollisionObject* collisionObject) { m_collisionObjects.push_back(collisionObject); }
Re: [GSoC] Elimination of CLooG library installation dependency
> With just C++ code, Sven can help little. He has no knowledge about graphite > internals. I want to ask him about correctness of ISL ASTs generated from mentioned isl_codegens. > Do you now have a setup where you can just compile one of the attached files > with graphite and everything else without and the code crashes? No, I don't. As I mentioned earlier, all the files from this test case individually produce object files which linked into the one executable, which cause “Segmentation fault (core dumped)” (It'll cause “Segmentation fault (core dumped)”, if we try to run it). I think that it's very difficult to detach the code, which would produce the executable and save the semantics of this big OOP project. Furthermore, there is a possibility that the detached code can produce no new useful information. I've found that if we try to compile any of the btCollisionWorld.cpp, btCollisionDispatcher.cpp and btDiscreteDynamicsWorld.llvm.cpp by modified Graphite, the produced object file will lead to creation of the wrong executable (after linking with other object files generated by origin Graphite). That's why I think that we could consider only, for example, btCollisionDispatcher.cpp. It contains only one scope, which is incorrectly processed by Graphite with the ISL code generator as the main generator. > Why did you provide two files. I assume one should be sufficient to > reproduce the crash, no? I've detached the code, which is used by Graphite to produce similar AST's. > I think for the one file you choose, it would be interesting to look > at the code generation input as well as the kernels generated by CLooG and > isl. Maybe we can understand what is going on. What do you mean by the kernels generated by CLooG and isl? btCollisionDispatcher.cpp: isl_codegen: [P_2, P_11] -> { S_6[i0] -> [0, i0, 0] : exists (e0 = floor((-1 + P_2)/4294967296), e1 = floor((P_11 + 8i0)/18446744073709551616): i0 >= 0 and 4294967296e0 <= -1 + P_2 and 4294967296e0 >= -4294967296 + P_2 and 4294967296e0 <= -1 + P_2 - i0 and i0 <= 2147483646 and 18446744073709551616e1 >= -18446744073709551615 + P_11 + 8i0 and 18446744073709551616e1 <= -1 + P_11 + 8i0) } [P_2, P_11] -> { : exists (e0 = floor((-1 + P_2)/4294967296): 4294967296e0 <= -1 + P_2 and 4294967296e0 >= -2147483647 + P_2 and P_2 >= -2147483648 and P_2 <= 2147483647 and P_11 >= 0 and P_11 <= 18446744073709551615) } [P_2, P_11] -> { [i0, i1, i2] -> separate[o0] } ISL AST generated by ISL: for (int c1 = 0; c1 < P_2; c1 += 1) if ((P_11 + 8 * c1) % 18446744073709551616 >= 1) S_6(c1); cloog_input: # CLooG -> CLooG # This is an automatic dump of a CLooG input file from a CloogInput data # structure. # Language: C c # Context: 1 4 4 0 0 0 2 1 1 0-1 1-1 0 2147483647 1 0-1 18446744073709551615 1 0 1 0 1 # Parameter name(s) T_2 T_11 # Statement number: 1 # Iteration domain of statement 1 (). 1 7 7 1 0 2 2 1 1 0 0 0 0 0 1 0 -4294967296 0 1 0-1 1 0 4294967296 0-1 0 4294967296 1-1 -4294967296 0 1 0-1 1-1 0 0 0 0 2147483646 1-8 0 18446744073709551616 0-1 18446744073709551615 1 8 0 -18446744073709551616 0 1-1 0 0 0 # For future options. 1 # Iterator name(s) git_0 # - SCATTERING 1 # Scattering functions # Scattering of statement 1 (). 1 3 8 3 1 0 2 0 0 0 1 0 0 0 0 0 0 1 0-1 0 0 0 0 1 0 0 0 0 0 0 1 # Scattering dimension name(s) scat_0 scat_1 scat_2 CLAST generated by ClooG: if (8*T_2 >= -T_11+9) { for (scat_1=0;scat_1<=T_2-1;scat_1++) { if ((8*scat_1+T_11+18446744073709551615)%18446744073709551616 <= 18446744073709551614) { (scat_1); } } } -- Cheers, Roman Gareev.
Re: [GSoC] Elimination of CLooG library installation dependency
> I am confused. It seems you attached some kind of reduced version of > btCollisionWorld.cpp? How did you obtain it? Did you compile and test > with these versions? I’ve manually selected parts of code, which produce the scope. I’ve found out that this bug is most probably caused by absence of pointer handling. The tree, which is corresponding to P_11 has pointer type. Furthermore, if we consider the transformed gimple code for (it can be found attached), we’ll see that it contains wrong parts: The code produced by modified version of Graphite: ... _35 = (signed long) _11; _36 = _34 + _35; _37 = _36 % 0; _38 = _37 > 0; _39 = (signed long) _38; ... The code produced by origin version of Graphite: ... _36 = (sizetype) _11; _37 = _36 + 18446744073709551615; _38 = 8B + _37; _39 = _38 % 0B; _40 = _39 != -1B; ... (If I’m not mistaken, 0B, for example, corresponds to (void *). It can be seen here: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50712) I’ve tried to implement pointer handling in the attached patch, but it is wrong. I get the following error instead of seagfault now: Floating point exception (core dumped) back trace: Program terminated with signal 8, Arithmetic exception. #0 0x004204c5 in allocSize (this=, size=) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/include/LinearMath/btAlignedObjectArray.h:59 59 return (size ? size*2 : 1); (gdb) bt #0 0x004204c5 in allocSize (this=, size=) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/include/LinearMath/btAlignedObjectArray.h:59 #1 push_back (_Val=, this=0x1125600) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/include/LinearMath/btAlignedObjectArray.h:220 #2 btCollisionDispatcher::getNewManifold (this=0x11255f0, b0=, b1=) at btCollisionDispatcher.llvm.cpp:100 #3 0x0044e764 in btConvexPlaneCollisionAlgorithm::btConvexPlaneCollisionAlgorithm (this=0x7f665ca6b0c0, mf=0x0, ci=..., col0=, col1=, isSwapped=, numPerturbationIterations=1, minimumPointsPerturbationThreshold=1) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/btConvexPlaneCollisionAlgorithm.cpp:38 #4 0x0046281b in btConvexPlaneCollisionAlgorithm::CreateFunc::CreateCollisionAlgorithm (this=0x11254e0, ci=..., body0=0x113d040, body1=0x113d810) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/include/BulletCollision/CollisionDispatch/btConvexPlaneCollisionAlgorithm.h:76 #5 0x004205ac in btCollisionDispatcher::findAlgorithm ( this=, body0=, body1=, sharedManifold=) at btCollisionDispatcher.llvm.cpp:145 #6 0x004202e2 in btCollisionDispatcher::defaultNearCallback ( ---Type to continue, or q to quit--- collisionPair=..., dispatcher=..., dispatchInfo=...) at btCollisionDispatcher.llvm.cpp:258 #7 0x0042083b in btCollisionPairCallback::processOverlap ( this=, pair=...) at btCollisionDispatcher.llvm.cpp:224 #8 0x004acff2 in btHashedOverlappingPairCache::processAllOverlappingPairs (this=0x1127f80, callback=0x7fff0d1af790, dispatcher=0x11255f0) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/btOverlappingPairCache.cpp:387 #9 0x004200c9 in btCollisionDispatcher::dispatchAllCollisionPairs ( this=, pairCache=, dispatchInfo=..., dispatcher=) at btCollisionDispatcher.llvm.cpp:238 #10 0x00421bd4 in btCollisionWorld::performDiscreteCollisionDetection() () #11 0x00464d9a in btDiscreteDynamicsWorld::internalSingleStepSimulation(float) () #12 0x0046473f in btDiscreteDynamicsWorld::stepSimulation(float, int, float) () #13 0x00401e08 in BenchmarkDemo::clientMoveAndDisplay ( this=0x7fff0d1af980) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/BenchmarkDemo.cpp:232 #14 0x00401b12 in main (argc=, argv=) at /home/roman/llvm-test-suite/MultiSource/Benchmarks/Bullet/main.cpp:63 Could you please advise me an algorithm for pointer handling? -- Cheers, Roman Gareev. loop_0 (header = 0, latch = 1, niter = ) { bb_2 (preds = {bb_0 }, succs = {bb_4 bb_3 }) { : # DEBUG D#5 => &this_1(D)->m_manifoldsPtr # DEBUG this => D#5 # VUSE <.MEM_3(D)> _5 = MEM[(struct btAlignedObjectArray *)this_1(D) + 8B].m_size; _6 = _5 * 2; # DEBUG D#4 => &D#5->m_allocator # DEBUG D#2 => D#4 # DEBUG D#3 => 0B # DEBUG n => _6 # DEBUG this => D#2 # DEBUG hint => D#3 _7 = (long unsigned int) _6; _8 = (unsigned int) _7; _9 = _8 * 8; _10 = (int) _9; # .MEM_22 = VDEF <.MEM_3(D)> _11 = btAlignedAlloc (_10, 16); # DEBUG s => _11 # DEBUG i => 0 # DEBUG i => 0 # VUSE <.MEM_22> _2 = MEM[(struct btAlignedObjectArray *)this_1(D) + 8B].m_size; if (_2 > 0)
Re: [GSoC] Elimination of CLooG library installation dependency
> Did you try your code with 64bit pointer types? Yes. It seems that the result is the same. > In any case, I don't think it is worth spending time on this. I would check > in the scop detection that we disable the handling of unsigned and pointer > types. It is a complex thing to model and the approach currently taking of > always model their wrapping behaviour seems wrong. I’ve attached a patch, which disables the handling SSA_NAME nodes in case they are pointers to object types. Which nodes should also be disabled? (I’ve found that this disabling helps to avoid the error and can be a temporary solution) Is the graphite_can_represent_scev an appropriate place for the disabling of type handling? -- Cheers, Roman Gareev. Index: gcc/graphite-scop-detection.c === --- gcc/graphite-scop-detection.c (revision 213773) +++ gcc/graphite-scop-detection.c (working copy) @@ -54,6 +54,7 @@ #include "tree-pass.h" #include "sese.h" #include "tree-ssa-propagate.h" +#include "cp/cp-tree.h" #ifdef HAVE_cloog #include "graphite-poly.h" @@ -217,6 +218,9 @@ if (chrec_contains_undetermined (scev)) return false; + if (TYPE_PTROB_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME) +return false; + switch (TREE_CODE (scev)) { case NEGATE_EXPR:
Re: [GSoC] the separate option for all dimensions
> Checking for this specific AST may cause failures with future versions of > isl that choose a different schedule. Could you write a regular expression > that checks that there is no if-condition contained in a for loop? I think > this best models the issue that was addressed in the original bug report. I’ve implemented this in the attached patch. Is it fine for trunk? -- Cheers, Roman Gareev. 2014-08-12 Roman Gareev [gcc/testsuite] * gcc.dg/graphite/pr35356-2.c: Update according to the ISL code generator. Index: gcc/testsuite/gcc.dg/graphite/pr35356-2.c === --- gcc/testsuite/gcc.dg/graphite/pr35356-2.c (revision 213773) +++ gcc/testsuite/gcc.dg/graphite/pr35356-2.c (working copy) @@ -1,4 +1,4 @@ -/* { dg-options "-O2 -fgraphite-identity -fdump-tree-graphite-all" } */ +/* { dg-options "-O2 -fgraphite-identity -fdump-tree-graphite-all -fgraphite-code-generator=isl" } */ int a[100]; @@ -38,7 +38,5 @@ */ - -/* { dg-final { scan-tree-dump-times "MIN_EXPR\[^\\n\\r]*;" 4 "graphite" } } */ -/* { dg-final { scan-tree-dump-times "MAX_EXPR\[^\\n\\r]*;" 4 "graphite" } } */ +/* { dg-final { scan-tree-dump-times "for\[^\n\]+\n\[^\n\]+if" 0 "graphite" } } */ /* { dg-final { cleanup-tree-dump "graphite" } } */
Re: [GSoC] Elimination of CLooG library installation dependency
If I’m not mistaken all tree nodes, which have pointer type, can be divided into two groups: the type is a is a pointer to data member (TYPE_PTRMEM_P is true for it), the type is a pointer type, and the pointee is not a data member (TYPE_PTR_P is true for it). I think that we’re interested in disabling of the second group handling. It can also be divided into two groups: the type is a pointer to function type (TYPE_PTRFN_P is true for it), the type is a pointer to object type (TYPE_PTROB_P is true for it). In my opinion, the second one is worth to be considered. It contains, for example, nop_expr (these nodes are used to represent conversions that do not require any code-generation) integer_cst (these nodes represent integer constants), ssa_name. I haven’t found all types, which are contained in it. However, I think that we could disable other types, if it is necessary in the future. > What we should do later is to build a run-time check that ensures > no pointer overflow is happening and then just create code without it. I think that it is better to do this when the pointer handling is completed. I’ve attached a Change_Log, which corresponds to the previous patch. Are they fine for trunk? Could we give a headsup on the GCC mailing list and ask other people to try the new isl support in case this patch is committed? -- Cheers, Roman Gareev. 2014-07-12 Roman Gareev gcc/ * graphite-scop-detection.c: Add inclusion of cp-tree.h. (graphite_can_represent_scev): Disables the handling of SSA_NAME nodes in case they are pointers to object types.
Re: [GSoC] Elimination of CLooG library installation dependency
> - I assume you verified this passes all graphite tests. Yes, I’ve found out that there is no regression. > - Please add a brief comment in the source code regarding why we >do not want to detect such SCoPs. Would you add anything to the following comment: “We disable the handling of pointer types, because it’s currently not supported by Graphite with the ISL AST generator. SSA_NAME nodes are the only nodes, which are disabled in case they are pointers to object types, but this can be changed.” ? -- Cheers, Roman Gareev.
Re: [GSoC] Elimination of CLooG library installation dependency
Thank you for the comment! 2014-08-13 15:55 GMT+06:00 Richard Biener : > On Wed, Aug 13, 2014 at 10:07 AM, Roman Gareev wrote: >> If I’m not mistaken all tree nodes, which have pointer type, can be >> divided into two groups: the type is a is a pointer to data member >> (TYPE_PTRMEM_P is true for it), the type is a pointer type, and the >> pointee is not a data member (TYPE_PTR_P is true for it). > > Both are C++ frontend concepts and not relevant for the middle-end > and thus GRAPHITE. > > I think that >> we’re interested in disabling of the second group handling. It can >> also be divided into two groups: the type is a pointer to function >> type (TYPE_PTRFN_P is true for it), the type is a pointer to object >> type (TYPE_PTROB_P is true for it). In my opinion, the second one is >> worth to be considered. It contains, for example, nop_expr (these >> nodes are used to represent conversions that do not require any >> code-generation) integer_cst (these nodes represent integer >> constants), ssa_name. I haven’t found all types, which are contained >> in it. However, I think that we could disable other types, if it is >> necessary in the future. >> >>> What we should do later is to build a run-time check that ensures >>> no pointer overflow is happening and then just create code without it. > > I think you can assume that pointers don't overflow. > > Richard. > >> I think that it is better to do this when the pointer handling is completed. >> >> I’ve attached a Change_Log, which corresponds to the previous patch. >> Are they fine for trunk? Could we give a headsup on the GCC mailing >> list and ask other people to try the new isl support in case this >> patch is committed? >> >> -- >> Cheers, Roman Gareev. -- Cheers, Roman Gareev.
Re: [GSoC] Elimination of CLooG library installation dependency
> I've attached the patch, which should eliminate CLooG library > installation dependency from GCC. The CLooG AST generator is still the > main code generator, but the isl ast generator will be chosen in case > of nonavailability of CLooG library. > > However, I've found out a problem. Almost all the functions of the ISL > cannot be used without installed CLooG. (I get errors which contain > “undefined reference to...”). Maybe I missed something. What do you > think about this? I’ve attached a patch, which contains mentioned changes and doesn’t cause the error. I want to commit it in coming days. What do you think about it? Maybe we should make the ISL AST generator to be the main code generator of Graphite (the patch1 implements this). What do you think about it? -- Cheers, Roman Gareev. 2014-08-15 Roman Gareev * configure.ac: Eliminate ClooG installation dependency. * configure: Regenerate. * Makefile.tpl: Add definition of ISLLIBS and HOST_ISLLIBS. * Makefile.in: Regenerate. [config/] * cloog.m4: Remove the path to isllibs from clooglibs. * isl.m4: Add paths to islinc, isllibs. [gcc/] * Makefile.in: Add definition of ISLLIBS. Update LIBS. * config.in: Add undef of HAVE_isl. * configure: Regenerate. * configure.ac: Add definition of HAVE_isl. * graphite-blocking.c: Add checking of HAVE_isl. * graphite-dependences.c: Likewise. * graphite-interchange.c: Likewise. * graphite-isl-ast-to-gimple.c: Likewise. * graphite-optimize-isl.c: Likewise. * graphite-poly.c: Likewise. * graphite-scop-detection.c: Likewise. * graphite-sese-to-poly.c: Likewise. * graphite.c: * toplev.c: Replace the checking of HAVE_cloog with the checking of HAVE_isl. 2014-08-15 Roman Gareev [gcc/] * common.opt: Make the ISL AST generator to be the main code generator of Graphite. Index: Makefile.in === --- Makefile.in (revision 214008) +++ Makefile.in (working copy) @@ -219,6 +219,7 @@ HOST_LIBS="$(STAGE1_LIBS)"; export HOST_LIBS; \ GMPLIBS="$(HOST_GMPLIBS)"; export GMPLIBS; \ GMPINC="$(HOST_GMPINC)"; export GMPINC; \ + ISLLIBS="$(HOST_ISLLIBS)"; export ISLLIBS; \ ISLINC="$(HOST_ISLINC)"; export ISLINC; \ CLOOGLIBS="$(HOST_CLOOGLIBS)"; export CLOOGLIBS; \ CLOOGINC="$(HOST_CLOOGINC)"; export CLOOGINC; \ @@ -310,6 +311,7 @@ HOST_GMPINC = @gmpinc@ # Where to find ISL +HOST_ISLLIBS = @isllibs@ HOST_ISLINC = @islinc@ # Where to find CLOOG Index: Makefile.tpl === --- Makefile.tpl(revision 214008) +++ Makefile.tpl(working copy) @@ -222,6 +222,7 @@ HOST_LIBS="$(STAGE1_LIBS)"; export HOST_LIBS; \ GMPLIBS="$(HOST_GMPLIBS)"; export GMPLIBS; \ GMPINC="$(HOST_GMPINC)"; export GMPINC; \ + ISLLIBS="$(HOST_ISLLIBS)"; export ISLLIBS; \ ISLINC="$(HOST_ISLINC)"; export ISLINC; \ CLOOGLIBS="$(HOST_CLOOGLIBS)"; export CLOOGLIBS; \ CLOOGINC="$(HOST_CLOOGINC)"; export CLOOGINC; \ @@ -313,6 +314,7 @@ HOST_GMPINC = @gmpinc@ # Where to find ISL +HOST_ISLLIBS = @isllibs@ HOST_ISLINC = @islinc@ # Where to find CLOOG Index: config/cloog.m4 === --- config/cloog.m4 (revision 214008) +++ config/cloog.m4 (working copy) @@ -69,7 +69,7 @@ fi clooginc="-DCLOOG_INT_GMP ${clooginc}" - clooglibs="${clooglibs} -lcloog-isl ${isllibs} -lisl" + clooglibs="${clooglibs} -lcloog-isl" ] ) Index: config/isl.m4 === --- config/isl.m4 (revision 214008) +++ config/isl.m4 (working copy) @@ -68,6 +68,9 @@ ENABLE_ISL_CHECK=no AC_MSG_WARN([using in-tree ISL, disabling version check]) fi + + islinc="-DCLOOG_INT_GMP ${islinc}" + isllibs="${isllibs} -lisl" ] ) Index: configure === --- configure (revision 214008) +++ configure (working copy) @@ -649,6 +649,7 @@ clooginc clooglibs islinc +isllibs poststage1_ldflags poststage1_libs stage1_ldflags @@ -2760,7 +2761,7 @@ build_tools="build-texinfo build-flex build-bison build-m4 build-fixincludes" # these libraries are used by various programs built for the host environment -# +#f host_libs="intl libiberty opcodes bfd readline tcl tk itcl libgui zlib libbacktrace libcpp libdecnumber gmp mpfr mpc isl cloog libelf libiconv" # these tools are built for the h
Re: [GSoC] Elimination of CLooG library installation dependency
Richard, could you please review these patches? We would be very glad for your comments. P.S: I’ve attached an improved ChangeLog_entry. 2014-08-15 17:44 GMT+06:00 Richard Biener : > On Fri, Aug 15, 2014 at 1:13 PM, Roman Gareev wrote: >>> I've attached the patch, which should eliminate CLooG library >>> installation dependency from GCC. The CLooG AST generator is still the >>> main code generator, but the isl ast generator will be chosen in case >>> of nonavailability of CLooG library. >>> >>> However, I've found out a problem. Almost all the functions of the ISL >>> cannot be used without installed CLooG. (I get errors which contain >>> “undefined reference to...”). Maybe I missed something. What do you >>> think about this? >> >> I’ve attached a patch, which contains mentioned changes and doesn’t >> cause the error. I want to commit it in coming days. What do you think >> about it? >> Maybe we should make the ISL AST generator to be the main code >> generator of Graphite (the patch1 implements this). What do you think >> about it? > > We definitely should do that (and rip out the cloog code after a while). > > Richard. -- Cheers, Roman Gareev. 2014-08-15 Roman Gareev * configure.ac: Eliminate ClooG installation dependency. * configure: Regenerate. * Makefile.tpl: Add definition of ISLLIBS and HOST_ISLLIBS. * Makefile.in: Regenerate. [config/] * cloog.m4: Remove the path to isllibs from clooglibs. * isl.m4: Add paths to islinc, isllibs. [gcc/] * Makefile.in: Add definition of ISLLIBS, HOST_ISLLIBS. * config.in: Add undef of HAVE_isl. * configure: Regenerate. * configure.ac: Add definition of HAVE_isl. * graphite-blocking.c: Add checking of HAVE_isl. * graphite-dependences.c: Likewise. * graphite-interchange.c: Likewise. * graphite-isl-ast-to-gimple.c: Likewise. * graphite-optimize-isl.c: Likewise. * graphite-poly.c: Likewise. * graphite-scop-detection.c: Likewise. * graphite-sese-to-poly.c: Likewise. * graphite.c: Likewise. * toplev.c: Replace the checking of HAVE_cloog with the checking of HAVE_isl.
[GSoC] the last code review
Dear gcc contributors, The removing of CLooG library installation dependency is almost finished. The code review of these patches (https://gcc.gnu.org/ml/gcc-patches/2014-08/msg01564.html) is the only thing, which prevents it. Could you please review them? My mentor’s already accepted them, but we still still need a non-graphite reviewer oking the changes (https://gcc.gnu.org/ml/gcc-patches/2014-08/msg01655.html). I shall not be able to commit this patch after “18 August: 19:00 UTC” because of GSoC’s 'pencils down'. We would be very glad for your comments. -- Cheers, Roman Gareev.
Re: [GSoC] Elimination of CLooG library installation dependency
> This patch is ok. I assume you have tested compiling with/without cloog > and isl. Yes, I’ve tested compiling with/without cloog and isl. Thank you very much for review! -- Cheers, Roman Gareev.
Re: [GSoC] Elimination of CLooG library installation dependency
Which configure options do you use? Have you tried to bootstrap r214105 with same configure options? Have you tried to manually export the path to isl to LD_RUN_PATH? (You’ve probably tried. I just want to make sure.) 2014-08-20 9:28 GMT+06:00 Bin.Cheng : > I suspect this causes arm/aarch64 native bootstrap failure with below > messages. > > aarch64-none-linux-gnu-g++ -c -g -O2 -DIN_GCC-fno-exceptions > -fno-rtti -fasynchronous-unwind-tables -W -Wall -Wno-narrowing > -Wwrite-strings -Wcast-qual -Wmissing-format-attribute > -Woverloaded-virtual -pedantic -Wno-long-long -Wno-variadic-macros > -Wno-overlength-strings -fno-common -DHAVE_CONFIG_H -I. -I. > -I/projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/src/gcc/gcc > -I/projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/src/gcc/gcc/. > -I/projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/src/gcc/gcc/../include > -I/projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/src/gcc/gcc/../libcpp/include > -I/projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/workdir/aarch64-none-linux-gnu/sysroot//usr/include > -I/projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/workdir/aarch64-none-linux-gnu/sysroot//usr/include > > -I/projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/src/gcc/gcc/../libdecnumber > -I/projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/src/gcc/gcc/../libdecnumber/dpd > -I../libdecnumber > -I/projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/src/gcc/gcc/../libbacktrace > -DCLOOG_INT_GMP -o graphite.o -MT graphite.o -MMD -MP -MF > ./.deps/graphite.TPo > /projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/src/gcc/gcc/graphite.c > /projects/pd/pdsw-infrastructure/production-builds/bld-root/channels/fsf-trunk/builds/502/src/gcc/gcc/graphite.c:38:21: > fatal error: isl/set.h: No such file or directory > compilation terminated. > make[1]: *** [graphite.o] Error 1 > make[1]: Leaving directory > `/arm/scratch/pdtltest/bld-temporary/builds/fsf-trunk/502/workdir/aarch64-none-linux-gnu/obj/build-gcc/gcc' > make: *** [all-gcc] Error 2 > > Thanks, > bin -- Cheers, Roman Gareev.
Re: [GSoC] Elimination of CLooG library installation dependency
Thank you for the report! > (1) FAIL: gcc.dg/graphite/vect-pr43423.c scan-tree-dump-times vect > "vectorized 2 loops" 1 > > before I saw > > [Book15] f90/bug% grep vectorized vect-pr43423.c.114t.vect > /opt/gcc/p_work/gcc/testsuite/gcc.dg/graphite/vect-pr43423.c:14:17: note: === > vect_mark_stmts_to_be_vectorized === > /opt/gcc/p_work/gcc/testsuite/gcc.dg/graphite/vect-pr43423.c:14:17: note: > loop vectorized > /opt/gcc/p_work/gcc/testsuite/gcc.dg/graphite/vect-pr43423.c:12:17: note: === > vect_mark_stmts_to_be_vectorized === > /opt/gcc/p_work/gcc/testsuite/gcc.dg/graphite/vect-pr43423.c:12:17: note: > loop vectorized > /opt/gcc/p_work/gcc/testsuite/gcc.dg/graphite/vect-pr43423.c:6:6: note: > vectorized 2 loops in function. > > after I see > > [Book15] f90/bug% grep vectorized vect-pr43423.c.115t.vect > > /opt/gcc/p_work/gcc/testsuite/gcc.dg/graphite/vect-pr43423.c:14:17: note: not > vectorized: not suitable for gather load _55 = a[_56]; > /opt/gcc/p_work/gcc/testsuite/gcc.dg/graphite/vect-pr43423.c:12:17: note: not > vectorized: not suitable for gather load _36 = a[_37]; > /opt/gcc/p_work/gcc/testsuite/gcc.dg/graphite/vect-pr43423.c:6:6: note: > vectorized 0 loops in function. We’ve already met with this problem. https://gcc.gnu.org/ml/gcc-patches/2014-08/msg00118.html https://gcc.gnu.org/ml/gcc-patches/2014-08/msg00155.html https://gcc.gnu.org/ml/gcc-patches/2014-08/msg00173.html In our opinion, it requires help of the vectorizer people. Maybe it’ll disappear by itself, when the computation of types is finished. > (2) FAIL: gfortran.dg/graphite/pr42393.f90 -O (internal compiler error) > FAIL: gfortran.dg/graphite/pr42393.f90 -O (test for excess errors) > > The backtrace is > > * thread #1: tid = 0x13bd91f, 0x7fff8621aca0 > libsystem_malloc.dylib`tiny_malloc_from_free_list + 12, queue = > 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, > address=0x7fff5bc00ff8) > frame #0: 0x7fff8621aca0 > libsystem_malloc.dylib`tiny_malloc_from_free_list + 12 > libsystem_malloc.dylib`tiny_malloc_from_free_list + 12: > -> 0x7fff8621aca0: pushq %rbx >0x7fff8621aca1: pushq %rax >0x7fff8621aca2: movl %edx, %r12d >0x7fff8621aca5: movq %rsi, %r14 > (lldb) bt > * thread #1: tid = 0x13bd91f, 0x7fff8621aca0 > libsystem_malloc.dylib`tiny_malloc_from_free_list + 12, queue = > 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, > address=0x7fff5bc00ff8) > * frame #0: 0x7fff8621aca0 > libsystem_malloc.dylib`tiny_malloc_from_free_list + 12 > frame #1: 0x7fff8621b3c3 > libsystem_malloc.dylib`szone_malloc_should_clear + 320 > frame #2: 0x7fff8621d868 libsystem_malloc.dylib`malloc_zone_malloc + > 71 > frame #3: 0x7fff8621e27c libsystem_malloc.dylib`malloc + 42 > frame #4: 0x000141dbdc79 libgmp.10.dylib`__gmp_default_allocate + 9 > frame #5: 0x000141dd0148 libgmp.10.dylib`__gmpz_init + 24 > frame #6: 0x000141c180ef > libisl.10.dylib`isl_basic_map_normalize_constraints + 47 > frame #7: 0x000141c18f04 libisl.10.dylib`isl_basic_map_simplify + 68 > frame #8: 0x000141c2509b libisl.10.dylib`isl_basic_set_preimage + 619 > frame #9: 0x000141c4e146 > libisl.10.dylib`isl_basic_set_sample_with_cone + 150 > frame #10: 0x000141c4ea88 libisl.10.dylib`basic_set_sample + 744 > frame #11: 0x000141c4e849 libisl.10.dylib`basic_set_sample + 169 > frame #12: 0x000141c09978 libisl.10.dylib`isl_basic_map_is_empty + 136 > frame #13: 0x000141bb2870 libisl.10.dylib`domain_follows_at_depth + > 112 > frame #14: 0x000141c7cdba libisl.10.dylib`isl_tarjan_components + 154 > > getting to the ICE take ~19s compared to less than a second before r214069. This is a bug in ISL. They’ll fix it in a new version of ISL. https://groups.google.com/forum/#!topic/isl-development/SeNZf5IA-Lk -- Cheers, Roman Gareev.
changing a collision resolution strategy of the symbol table of identifiers
Dear gcc contributors, Recently I came across the list of "ideas for speeding up GCC" (http://gcc.gnu.org/wiki/Speedup_areas). Among others, there was suggested to replace identifier hash table with other data structure. Please find attached a patch, that switches the resolution strategy of a hash table used in the symbol table of identifiers from open addressing to separate chaining with linked list. I would be very grateful for your comments, feedback and ideas about further enhancements to gcc, in which I could take a part. I am pursuing master of science and looking for thesis theme, that is compiler related. Below are results of testing and the patch. During testing of the linux kernel (3.8.8) compilation time, the acquired results were the following: increasing by 0.17% for the version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing by 0.598% for trunk (this are average values). Tested x86_64-unknown-linux-gnu, applying to 4.8.0, 4.8.1 and trunk. diff --git a/gcc/stringpool.c b/gcc/stringpool.c index f4d0dae..cc696f7 100644 --- a/gcc/stringpool.c +++ b/gcc/stringpool.c @@ -241,12 +241,8 @@ gt_pch_nx (unsigned char *x, gt_pointer_operator op, void *cookie) /* SPD is saved in the PCH file and holds the information needed to restore the string pool. */ -struct GTY(()) string_pool_data { - ht_identifier_ptr * - GTY((length ("%h.nslots"), - nested_ptr (union tree_node, "%h ? GCC_IDENT_TO_HT_IDENT (%h) : NULL", - "%h ? HT_IDENT_TO_GCC_IDENT (%h) : NULL"))) - entries; +struct GTY((user)) string_pool_data { + ht_identifier_ptr * entries; unsigned int nslots; unsigned int nelements; }; @@ -284,4 +280,113 @@ gt_pch_restore_stringpool (void) spd = NULL; } +/* User-provided GC marking routines for the struct ht_identifier. They are using + only in GC marking routines for the struct string_pool_data. */ + +extern void ht_identifier_ggc_mx (void *x_p); +extern void ht_identifier_pch_nx (void *x_p); +extern void ht_identifier_pch_nx (void *this_obj, void *x_p, gt_pointer_operator op, void *cookie); + +void +ht_identifier_ggc_mx (void *x_p) +{ + struct ht_identifier * x = (struct ht_identifier *)x_p; + struct ht_identifier * xlimit = x; + while (ggc_test_and_set_mark (xlimit)) + xlimit = ((*xlimit).next); + while (x != xlimit) + { + union tree_node * const x0 = ((*x).next) ? HT_IDENT_TO_GCC_IDENT (((*x).next)) : NULL; + gt_ggc_m_9tree_node (x0); + x = ((*x).next); + } +} + +void +ht_identifier_pch_nx (void *x_p) +{ + struct ht_identifier * x = (struct ht_identifier *)x_p; + struct ht_identifier * xlimit = x; + while (gt_pch_note_object (xlimit, xlimit, ht_identifier_pch_nx)) + xlimit = ((*xlimit).next); + while (x != xlimit) + { + union tree_node * const x0 = ((*x).next) ? HT_IDENT_TO_GCC_IDENT (((*x).next)) : NULL; + gt_pch_n_9tree_node (x0); + x = ((*x).next); + } +} + +void +ht_identifier_pch_nx (void *this_obj, void *x_p, gt_pointer_operator op, void *cookie) +{ + struct ht_identifier * x = (struct ht_identifier *)x_p; + op (&((*x).str), cookie); + union tree_node * x0 = ((*x).next) ? HT_IDENT_TO_GCC_IDENT (((*x).next)) : NULL; + op (&(x0), cookie); + (*x).next = (x0) ? (GCC_IDENT_TO_HT_IDENT ((x0))) : NULL; +} + +/* A pointer walker for entries of the struct string_pool_data. */ + +void +string_pool_data_pch_entries_walker (void *this_obj, void *x_p, gt_pointer_operator op, void *cookie) +{ + struct string_pool_data * x ATTRIBUTE_UNUSED = (struct string_pool_data *)x_p; + size_t l0 = (size_t)(((*x)).nslots); + if ((*x).entries != NULL) + { + size_t i0; + for (i0 = 0; i0 != (size_t)(l0); i0++) + { + union tree_node * x0 = ((*x).entries[i0]) ? HT_IDENT_TO_GCC_IDENT (((*x).entries[i0])) : NULL; + op (&(x0), cookie); + (*x).entries[i0] = (x0) ? (GCC_IDENT_TO_HT_IDENT ((x0))) : NULL; + } + } +} + +/* User-provided GC marking routines for the struct string_pool_data. */ + +void +gt_ggc_mx (string_pool_data *x) +{ + size_t l0 = (size_t)(((*x)).nslots); + if ((*x).entries != NULL) + { + size_t i0; + for (i0 = 0; i0 != (size_t)(l0); i0++) + { + ht_identifier_ggc_mx ((*x).entries[i0]); + union tree_node * const x0 = ((*x).entries[i0]) ? HT_IDENT_TO_GCC_IDENT (((*x).entries[i0])) : NULL; + gt_ggc_m_9tree_node (x0); + } + ggc_mark ((*x).entries); + } +} + +void +gt_pch_nx (string_pool_data *x) +{ + size_t l0 = (size_t)(((*x)).nslots); + if ((*x).entries != NULL) + { + size_t i0; + for (i0 = 0; i0 != (size_t)(l0); i0++) + { + union tree_node * const x1 = ((*x).entries[i0]) ? HT_IDENT_TO_GCC_IDENT (((*x).entries[i0])) : NULL; + gt_pch_n_9tree_node (x1); + ht_identifier_pch_nx ((*x).entries[i0]); + } + gt_pch_note_object ((*x).entries, x, string_pool_data_pch_entries_walker); + } +} + +void +gt_pch_nx (string_pool_data *x, gt_pointer_operator op, void *cookie) +{ + if ((*x).entries != NULL) + op (&((*x).entries), cookie); +} + #include "gt-stringpool.h" diff --git a/libcpp/inc
Re: changing a collision resolution strategy of the symbol table of identifiers
2013/10/20 Ondřej Bílka : > On Sun, Oct 20, 2013 at 06:55:40PM +0600, Roman Gareev wrote: >> Dear gcc contributors, >> >> Recently I came across the list of "ideas for speeding up GCC" >> (http://gcc.gnu.org/wiki/Speedup_areas). Among others, there was >> suggested to replace identifier hash table with other data structure. >> >> Please find attached a patch, that switches the resolution strategy of >> a hash table used in the symbol table of identifiers from open >> addressing to separate chaining with linked list. I would be very >> grateful for your comments, feedback and ideas about further >> enhancements to gcc, in which I could take a part. I am pursuing >> master of science and looking for thesis theme, that is compiler >> related. >> >> Below are results of testing and the patch. >> >> During testing of the linux kernel (3.8.8) compilation time, the >> acquired results were the following: increasing by 0.17% for the >> version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing >> by 0.598% for trunk (this are average values). >> >> >> Tested x86_64-unknown-linux-gnu, applying to 4.8.0, 4.8.1 and trunk. >> >> >> diff --git a/gcc/stringpool.c b/gcc/stringpool.c >> >> index f4d0dae..cc696f7 100644 >> >> --- a/gcc/stringpool.c >> >> +++ b/gcc/stringpool.c >> >> @@ -241,12 +241,8 @@ gt_pch_nx (unsigned char *x, gt_pointer_operator >> op, void *cookie) >> >> /* SPD is saved in the PCH file and holds the information needed >> >> to restore the string pool. */ >> >> -struct GTY(()) string_pool_data { >> >> - ht_identifier_ptr * >> >> - GTY((length ("%h.nslots"), >> > Mail client broke it? Sorry, an error occurred somewhere. Below is an attachment with the patch. patch Description: Binary data
Re: changing a collision resolution strategy of the symbol table of identifiers
2013/10/31 Florian Weimer : > On 10/20/2013 02:55 PM, Roman Gareev wrote: >> >> During testing of the linux kernel (3.8.8) compilation time, the >> acquired results were the following: increasing by 0.17% for the >> version 4.8.0, increasing by 1.12% for the version 4.8.1, decreasing >> by 0.598% for trunk (this are average values). > > > Can you share the raw numbers? Are the differences statistically > significant? > > -- > Florian Weimer / Red Hat Product Security Team These are the row numbers. I'll share results of checking for statistical significance as soon as more compilations are made. results Description: Binary data