Re: Integration of ISL code generator into Graphite
Hi Mircea. Sorry, I've been missing for a while. Thank you for your ideas! I agree that reusing of the existing code (especially code using tree-SSA related information) is important for this project. I'm considering the current code in graphite_clast_to_gimple.c, and want to ask a few questions about it. I'll send them in a new message. – Cheers, Roman Gareev
[GSoC] questions about graphite_clast_to_gimple.c
Hi Tobias, I'm considering the current code in graphite_clast_to_gimple.c, and want to ask a few questions about it. 1. Where can I find the definitions of basic_block_def and edge from coretypes.h? 2. Why are recompute_all_dominators() and graphite_verify() called before initialization of if_region in gloog? Does it happen just in case (since the SSA form hasn't been modified)? 3. Why doesn't clast_guard have “else” statements? 4. Why is compute_bounds_for_param (it's from add_names_to_union_domain) called after save_clast_name_index? 5. I've considered practically all the code of a CLAST generation through GLooG and started consideration of translate_clast. However, I don't understand the idea behind if_region creation. Do you know something about it? -- Cheers, Roman Gareev
[GSoC] “Integration of ISL code generator into Graphite” project announcement
Dear gcc contributors, I am very happy to announce that my proposal was accepted. Thank you very much for allowing me to work on this project! I've started a blog to post the updates of the project after reaching my mile stones. It also contains my proposal. My blog can be found at the following link http://romangareev.blogspot.com -- Cheers, Roman Gareev
Re: [GSoC] questions about graphite_clast_to_gimple.c
Hi Tobias,
thank you for your reply! I have questions about types. Could you
please answer them?
Questions related to “type_for_interval”:
1. What happens in these lines?
int precision = MAX (mpz_sizeinbase (bound_one, 2),
mpz_sizeinbase (bound_two, 2));
if (precision > BITS_PER_WORD)
{
gloog_error = true;
return integer_type_node;
}
Do we try to count maximum number of value bits in bound_one and
bound_two? Why can't it be greater than BITS_PER_WORD?
2. Why do we want to generate signed types as much as possible?
3. Why do we always have enough precision in case of precision <
wider_precision?
Questions related to “clast_to_gcc_expression”:
4. What is the idea behind this code?
if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
name = convert_to_ptrofftype (name);
5. Why do we check POINTER_TYPE_P(type)? (“type” has tree type and the
manual says that a tree is a pointer type)
Questions related to “max_precision_type”:
6. Why is type1, for example, is the maximal precision type in case of
truth of POINTER_TYPE_P (type1)?
7. Why do we have enough precision for p2 in case of p1 > p2 and signed type1?
8. Why do we always build signed integer type in the line: “type =
build_nonstandard_integer_type (precision, false);”?
Questions related to “type_for_clast_red”:
9. Why do we use this code in case of clast_red_sum?
value_min (m1, bound_one, bound_two);
value_min (m2, b1, b2);
mpz_add (bound_one, m1, m2);
Can bound_one be greater then bound_two? (We also consider two cases
in “type_for_interval”)
10. Why do we assume that new bounds are min(bound_one, bound_two) and
min(b1, b2) in case of clast_red_min?
--
Cheers, Roman Gareev
[GSoC] a wiki page on the gcc wiki
Dear administration of GCC Wiki, I've created an account on the gcc wiki but I don't allowed to create and edit any page. I would like to set up a wiki page to post the updates of the project after reaching my mile stones. Could you please advise me how to get appropriate rights? (I've registered as RomanGareev) -- Cheers, Roman Gareev
Re: [GSoC] questions about graphite_clast_to_gimple.c
Thank you for your answers! They saved me the time of code consideration. -- Cheers, Roman Gareev
Re: [GSoC] How to get started with the isl code generation
Hi Tobias, thank you for your advice! > On the other side, I think it is a good idea to simultaneously keep track of > the design you have in mind and the first steps you are planning to take. > Even though the full design may still need some time, > some basic decisions can probably already be taken and maybe even > implemented. Staying in some way close to the coding you will do, > may be helpful to direct your code inspections to areas of code that > will be important for your implementation. > > E.g. just setting up a second code generation in parallel that does > minimal work (generates no code at all), but that can be enabled by a > command line flag might be a first start. I agree with this. I'll start setting up a second code generation as soon as I achieve success with separate ISL AST generation. P.S.: It's still not writable. I've asked about this issue. -- Cheers, Roman Gareev
Re: [GSoC] a wiki page on the gcc wiki
Thank you! -- Cheers, Roman Gareev
Re: [GSoC] How to get started with the isl code generation
Hi Tobias, > what is the difference you see between ISL AST generation and code > generation? By “ISL AST generation”, I mean ISL AST generation without generation of GIMPLE code. > What are your plans to separate the ISL AST generation? Do you foresee any > difficulties/problems? According to the plan mentioned in my proposal, I wanted to get more familiar with ISL AST generation by generation of ISL AST in a file, which is separate from the GCC sources. This could help to avoid problems with interpretation and verification of results, because I worked with my own input to ISL AST generator instead of the input built by Graphite from GIMPLE code. This could also help to avoid rebuilding of GCC in the process of debugging. However, I've come to the conclusion that the way you advised me is better, because it helps to save the time of integration of ISL AST generation in GCC. I've set up a second code generation in parallel that generates ISL AST and can be enabled by a command line flag. Could you please advise me how to verify the results of this generation? Below is the code of this generation. -- Cheers, Roman Gareev code Description: Binary data
Re: [GSoC] How to get started with the isl code generation
Hi Tobias, I tried to incorporate all your comments in the following patch. It also contains traversing of ISL AST and its dump to a file. You can find out more about this at the following link http://romangareev.blogspot.ru/2014/05/gsoc-report-i.html -- Cheers, Roman Gareev patch Description: Binary data
Re: [GSoC] How to get started with the isl code generation
Hi Tobias, > Allright. It seems you understood the tree traversel. For the actual > patch that we want to commit, let's leave it out for now. Instead, > let's try to get a minimal patch that only adds the flag and the new > file for the isl_ast stuff. In case the isl is choosen as code > generation option, the cloog pass is disabled (they would otherwise get > into their way later) and we dump the ast. We also need a simple test case > that checks that the dump is generated. What do you mean by simple test case that checks that the dump is generated? Is it checking of the dump_flags? > Instead of adding this functionality to gloog() I would create a > semilar function that provides the functionality gloog has for the isl > codegen counterpart. -fgraphite-code-generator switches then between > these two functions. To start with the isl counterpart is almost empty. > It just contains the parts of this patch needed for printing. When we > add more functionality and we encounter reuse opportunities, we can move > parts of graphite-clast-to-gimple.c into a generic codegen file. > > What do you think? I think that it's good. It would help to begin removing of CLooG dependency and make the file with generation of ISL AST easier to maintain. I implemented it in the patch, which can be found below. You can also find my post about my second task of the proposal at the following link http://romangareev.blogspot.com/2014/05/gsoc-report-ii.html -- Cheers, Roman Gareev patch Description: Binary data
Re: [GSoC] How to get started with the isl code generation
Hi Tobias,
> This file is empty. It seems to be the perfect place for gloog_isl,
> maybe give it a more descriptive name. E.g.,
>
> graphite_regenerate_ast_isl()
>
> We could then rename gloog, to graphite_regenerate_ast_cloog().
>
> gloog comes from graphite + cloog and does not make sense in the context
> of isl.
Would it be better to rename gloog in a separate patch (because it
could cause renaming of gloog_error, for eaxmple, and increase the
size of the patch)?
I tried to incorporate all your comments in the following patch. I
also attach the change log to this message.
--
Cheers, Roman Gareev
patch
Description: Binary data
ChangeLog_entry
Description: Binary data
Re: [GSoC] How to get started with the isl code generation
Hi Tobias,
I made a separate patch and rebased the previous one. They are
attached to this letter.
> I am surprised. Are all these includes really needed to get _this_ patch
> compile? (I asked this before).
I saw your previous comment related to this and the following includes
were removed: isl/list.h, isl/constraint.h, isl/ilp.h, isl/aff.h,
diagnostic-core.h, tree-ssa-loop-manip.h, tree-into-ssa.h,
tree-chrec.h, tree-scalar-evolution.h.
However, it seems that if we want to use the struct scop_p from
graphite-poly.h, we have to include sese.h, which requires
tree-data-ref.h, cfgloop.h, tree-ssa-loop.h, gimple-iterator.h,
gimple.h, is-a.h, gimple-expr.h, internal-fn.h, tree-ssa-alias.h,
basic-block.h, tree.h, coretypes.h, system.h, config.h
We also have to include tree-pass.h, if we want to use timevar_push,
timevar_pop to to measure elapsed time (it was used previously by
graphite-clast-to-gimple.c).
> This is ugly, but there is little we can do about it. Maybe you can ask
> on the mailing list if there is a way to write this in multiple lines?
The patch was reduced, but I didn't found out how to make the regexp
easier to read. I wrote about this to the community.
--
Cheers, Roman Gareev
ChangeLog_entry1
Description: Binary data
ChangeLog_entry2
Description: Binary data
patch1
Description: Binary data
patch2
Description: Binary data
[GSoC] question about regular expressions
Dear gcc contributors,
could you please advise how to better write the following testcase?
After the compilation with -O2 -fdump-tree-graphite-all
-fgraphite-identity -fgraphite-code-generator=isl the dump file should
contain the following text
ISL AST generated by ISL:
for (int c1 = 0; c1 < n - 1; c1 += 1)
for (int c3 = 0; c3 < n; c3 += 1)
S_5(c1, c3);" 1 "graphite"}
}
I am using the following code to check it:
diff --git a/gcc/testsuite/gcc.dg/graphite/isl-codegen-loop-dumping.c
b/gcc/testsuite/gcc.dg/graphite/isl-codegen-loop-dumping.c
new file mode 100644
index 000..1bb0349
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/isl-codegen-loop-dumping.c
@@ -0,0 +1,16 @@
+/* { dg-options "-O2 -fdump-tree-graphite-all -fgraphite-identity
-fgraphite-code-generator=isl" } */
+
+int
+main (int n, int *a)
+{
+ int i, j;
+
+ for (i = 0; i < n - 1; i++)
+for (j = 0; j < n; j++)
+ a[j] = i + n;
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "ISL AST generated by ISL: \nfor
\\(int c1 = 0; c1 < n - 1; c1 \\+= 1\\)\n for \\(int c3 = 0; c3 < n;
c3 \\+= 1\\)\nS_5\\(c1, c3\\);" 1 "graphite"} } */
+/* { dg-final { cleanup-tree-dump "graphite" } } */
However, I want to make the regular expression easier to read and
similar to the following multiline form:
+/* { dg-final { scan-tree-dump-times "ISL AST generated by ISL: \n
? for \\(int c1 = 0; c1 < n - 1; c1 \\+= 1\\)\n
? for \\(int c3 = 0; c3 < n; c3 \\+= 1\\)\n
?S_5\\(c1, c3\\);" 1 "graphite"}
? } */
Is it possible? Where can I find the description of regular
expressions used in scan-tree-dump-times? I would be very grateful for
your comments.
--
Cheers, Roman Gareev
Re: [GSoC] How to get started with the isl code generation
I used trunk and compiled these patches only with isl 0.12 and ClooG 0.18.1. Which versions of these libraries are need to be checked for compatibility? -- Cheers, Roman Gareev
[GSoC] generation of GCC expression trees from isl ast expressions
Hi Tobias,
I'm currently working on generation of GCC expression trees from isl
ast expressions . Could you please answer a few questions about it?
1. How is it better to generate tree from isl_ast_expr_int? In the
temporary variant I call isl_ast_expr_get_int to get isl_int from
isl_ast_expr. After this, gmp_cst_to_tree (it was used in
graphite-clast-to-gimple.c) is called to generate tree frome isl_int.
It is possible now, because isl_int is mpz_t. However, it can be
changed in the future, according to comments from its source code.
+/* 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);
+}
+/* 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);
+}
+
2. As you said in previous messages, we can always use signed 64/128,
until isl is able to give information about types. I haven't found
them in types of Generic
(https://gcc.gnu.org/onlinedocs/gccint/Types.html#Types). Could they
be declared using build_nonstandard_integer_type (128, 1)?
3. If I am not mistaken, the structure ivs_params from
graphite-clast-to-gimple.c is used to store induction variables and
parameters, rename them according to SSA form. Could it be used in
graphite-isl-ast-to-gimple.c, too?
4. Should we transform all isl_ast_expr_op types of isl ast
expressions to GCC expression tree? For example, the following types
are not transformed at all in Polly project: isl_ast_op_cond,
isl_ast_op_and_then, isl_ast_op_or_else, isl_ast_op_call,
isl_ast_op_member, isl_ast_op_access, isl_ast_op_pdiv_q,
isl_ast_op_pdiv_r, isl_ast_op_div, isl_ast_op_fdiv_q.
The first draft of generation of GCC expression trees from isl ast
expressions can be found below:
--
Cheers, Roman Gareev
patch
Description: Binary data
Re: [GSoC] generation of GCC expression trees from isl ast expressions
> I assume so. However, we always want signed types, so the second > argument should be zero, no? Yes, you are right. > How did you verify that the semantics of the GCC and isl expressions are > identical? I haven't tested it on examples yet. I've only matched their semantics from the isl manual and the documentation of gcc internals (https://gcc.gnu.org/onlinedocs/gccint/Unary-and-Binary-Expressions.html#Unary-and-Binary-Expressions). > The kind of code you write looks very good. Now, the only question is > how can we commit it as quickly as possible. This means we need to add > just enough functionality such that we create a working subset that is > testable. Testing in gcc is a little difficult, as we commonly work > from C output to a testable executable. Maybe we should have a look at > the existing graphite test cases for -fgraphite-identify and identify > the simplest ones. Or we can even create simpler ones. > > I assume the easiest one is a single loop: > > for (i = 0; i < 100; i++) > A[i] = i; > > Alternatively, we could try create unit tests for the expressions. > However, I am not sure if there exists a unit-test infrastructure in > gcc. Yes, I've started to working on simple DejaGnu test cases for these expressions, which will possibly use the previous ones. -- Cheers, Roman Gareev
[GSoC] Question about unit tests
Dear gcc contributors, could you please answer a few questions about unit tests? Is it possible to use them in gcc? Or maybe there is some analogue? I would be very grateful for your comments. -- Cheers, Roman Gareev
Re: [GSoC] generation of GCC expression trees from isl ast expressions
> Are you saying we should better not do unit testing at the moment? (This is > perfectly fine with me, I am just verifying what you said) Yes, I think we should better not to do it. It seems that unit-testing isn't supported in gcc. > If we don't have a convenient way to do unit-testing, we need to do testing > for larger programs (at least empty loop bodies). This is what we did > previously and even though not ideal should work as well. I agree that generation of loops with empty bodies is required functionality for testing (I wrote about this in previous message. Sorry for being unclear.) > I did not fully understand them. Are you comparing the resulting GIMPLE > trees or are you statically evaluating the isl and gimple trees to check > if the computed value is the same? I'm statically evaluating gimple tree expressions, which are generated from isl ast expressions. After this the result of the evaluation is being compared with assumed result. I haven't found functions, which evaluate isl ast expressions. That is why it compares results of evaluations with assumed result. Maybe there is a better way to compare the semantics of the GCC and isl expressions. -- Cheers, Roman Gareev
Re: [GSoC] generation of GCC expression trees from isl ast expressions
Hi Tobias,
could you please advise me how to verify the results of gimple code
generation? I've written the first draft of the generation of loops
with empty bodies and tried to verify gimple code using the
representation, which is dumped at the end of the generation of the
dump_file. If we consider the following example, we'll see that cloog
and isl code generator generate similar representation (representation
generated by isl code generator doesn't have body of the loop, as was
expected).
int
main (int n, int *a)
{
int i;
for (i = 0; i < 100; i++)
a[i] = i;
return 0;
}
gcc/graphite-isl-ast-to-gimple.c
loop_0 (header = 0, latch = 1, niter = )
{
bb_2 (preds = {bb_0 }, succs = {bb_3 })
{
:
}
bb_5 (preds = {bb_3 }, succs = {bb_1 })
{
:
# .MEM_10 = PHI <.MEM_3(D)(3)>
# VUSE <.MEM_10>
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)>
graphite_IV.3_14 = graphite_IV.3_1 + 1;
if (graphite_IV.3_1 < 99)
goto ;
else
goto ;
}
bb_4 (preds = {bb_3 }, succs = {bb_3 })
{
:
goto ;
}
}
}
graphite-clast-to-gimple.c
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)(2), .MEM_11(4)>
_2 = (sizetype) graphite_IV.3_1;
_15 = _2 * 4;
_16 = a_6(D) + _15;
_17 = (int) graphite_IV.3_1;
# .MEM_11 = VDEF <.MEM_19>
*_16 = _17;
graphite_IV.3_14 = graphite_IV.3_1 + 1;
if (graphite_IV.3_1 < 99)
goto ;
else
goto ;
}
bb_4 (preds = {bb_3 }, succs = {bb_3 })
{
:
goto ;
}
}
}
However, this form doesn't have loop guards which are generated by
graphite_create_new_loop_guard in gcc/graphite-isl-ast-to-gimple.c and
by graphite_create_new_loop_guard in graphite-clast-to-gimple.c.
Below is the code of this generation (It still uses isl_int for
generation of isl_expr_int, because the error related to isl/val_gmp.h
still arises. I've tried to use isl 0.12.2 and 0.13, but gotten the
same error).
--
Cheers, Roman Gareev
Index: gcc/graphite-isl-ast-to-gimple.c
===
--- gcc/graphite-isl-ast-to-gimple.c(revision 212194)
+++ gcc/graphite-isl-ast-to-gimple.c(working copy)
@@ -42,16 +42,620 @@
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "sese.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-scalar-evolution.h"
#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;
+/* 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
+}
+
+/* Stores the INDEX in a vector and the loop nesting LEVEL for a given
+ isl_id NAME. BOUND_ONE and BOUND_TWO represent the exact lower and
+ upper bounds that can be inferred from the polyhedral representation. */
+
+typedef struct ast_isl_name_index {
+ int index;
+ int level;
+ const char *name;
+ /* If free_name is set, the content of name was allocated by us and needs
+ to be freed. */
+ char *free_name;
+} *ast_isl_name_index_p;
+
+/* Helper for hashing ast_isl_name_index. */
+
+struct ast_isl_index_hasher
+{
+ typedef ast_isl_name_index value_type;
+ typedef ast_isl_name_index compare_type;
+ static inline hashval_t hash (const value_type *);
+ static inline bool equal (const value_type *, const compare_type *);
+ static inline void remove (value_type *);
+};
+
+/* Computes a hash function for database element E. */
+
+inline hashval_t
+ast_isl_index_hasher::hash (const value_type *e)
+{
+ hashval_t hash = 0;
+
+ int length = strlen (e->name);
+ int i;
+
+ for (i = 0; i < length; ++i)
+hash = hash
Re: [GSoC] Question about unit tests
Thank you for the answer! -- Cheers, Roman Gareev
[GSoC] Question about std::map
Dear gcc contributors, could you please answer a few questions about std::map? Does gcc have a policy that forbids using of map in the source code of gcc? Can this using create a new installation dependency, which requires libstdc++? I would be very grateful for your comments. -- Cheers, Roman Gareev
Re: [GSoC] generation of GCC expression trees from isl ast expressions
ivs.
Yes, this is redundant and removed in the new version. I wanted to
write the code, which reuses the code from graphite-clast-to-gimple.c
as much as possible, to reduce a number of errors. After this, I
planned to eliminate redundant parts.
> Please explain why we need a special function to get the upper bound.
> Specifically, explain that isl in some configurations can generate loop
> exit conditions such as:
>
> for (i = ?; i + 2 >= 3 && 3 <= i + m; i++)
> ;
>
> This get upper bound assumes a certain shape of loop exit condition(
>
> for (i = ?; i < expr; i++)
>
> Also, you need to set the option --no-isl-ast-build-atomic-upper-bound
> in isl_ast_build to be able to rely on this behavior.
> (You did this below)
>
> Do you have a specific motivation, why you don't want to support
> arbitrary expressions? I assume this is necessary for the if - do-while
> optimization. If this is the case please state this.
I haven't found another function for generation loops in Gimple form.
The create_empty_loop_on_edge needs, which is being used now, requires
upper bound.
/* create_empty_loop_on_edge
|
|- pred_bb - pred_bb --
| | | | iv0 = initial_value |
|-|- --|---
| |___| entry_edge
| | entry_edge / ||
| | > / -V---V- loop_header -
| V || iv_before = phi (iv0, iv_after) |
|- succ_bb - |
|-
| | || |
|---| ---V--- loop_body
| | | iv_after = iv_before + stride |
| | | if (iv_before < upper_bound) |
| |
---|--\--
| | |
\ exit_e
| | V \
| | - loop_latch -
---V- succ_bb -
| | | |
||
| | /-
-
|\ _ /
Furthermore, at the moment of loop generation we don't have the
induction variable, which is need for generation of a loop condition
in case of the option –no-isl-ast-build-atomic-upper-bound is unset.
The induction variable is returned by create_empty_loop_on_edge. Could
you please advise me another function to generate them?
> Please explain why we do not just generate a loop that has the loop
> bound at the top, but instead create a structure of the form
>
> if (lb > ub)
> do {
>
> } while (lb ..)
>
> (Such a figure, but completed might help).
>
> (I think the original motivation was that later we may be able to prove
> that a loop is executed at least once which allows us to remove the if
> which again enables better loop invariant code motion)
I didn't have special intentions for this. As was mentioned above, I
haven't found another way for generation of loops.
> Why are the previous two functions necessary?
Yes, they are unimportant. I've replaced them with
add_parameters_to_ivs_params, which add tree representations and names
of parameters to ivs_param
> Why did you switch back to an isl_map?
> This seems incorrect for scops with more than two statements.
Yes, this is a mistake. I've fixed it.
> P.S.: I just wanted to let you know that your work is amazing. Almost
> fully unsupervised you are always providing high-quality patches! I am
> very impressed.
Thank you!
--
Cheers, Roman Gareev
Index: gcc/graphite-isl-ast-to-gimple.c
===
--- gcc/graphite-isl-ast-to-gimple.c(revision 212194)
+++ gcc/graphite-isl-ast-to-gimple.c(working copy)
@@ -42,16 +42,610 @@
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "sese.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-scalar-evolution.h"
#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 the isl is able to give information about
+types */
+
+static tree *graphite_temporary_tree_type = &int128_integer_type_node;
+
[GSoC] generation from isl_ast_node_user
Hi Tobias,
I think that, according to the std::map feedback, we could use
std::map now and replace it with hash_map later, if its performance is
better. However, I propose to temporary postpone this and work on
gimple code generation from isl_ast_node_user, because we already have
generation of loops with empty bodies and generation from
isl_ast_node_user can be a problem. What do you think about this?
Could you please advise me an algorithm for computation of
substitutions? (ClooG uses its own algorithm for this and stores
substitutions in clast_user_stmt. There is an algorithm, which is used
in polly, but, honestly, I don't understand it.)
Could you please advise me how is it better to bind polly basic blocks
to a isl_ast_node_user? I'm using the following code now, but I'm not
sure if it is the right way:
bb_schedule = isl_map_intersect_domain (bb_schedule,
isl_set_copy (pbb->domain));
isl_id *dim_in_id = isl_map_get_tuple_id (bb_schedule, isl_dim_in);
isl_id *new_dim_in_id = isl_id_alloc (isl_id_get_ctx (dim_in_id),
isl_id_get_name (dim_in_id), pbb);
bb_schedule = isl_map_set_tuple_id (bb_schedule, isl_dim_in,
new_dim_in_id);
(I'm allocating an isl_id, which contains pointer to polly basic
blocks, while we're generating a isl_schedule.)
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);
(I'm getting this information, while we're handling isl_ast_node_user)
--
Cheers, Roman Gareev
Re: [GSoC] generation from isl_ast_node_user
>You may want to take a look at polly commit r212186, where I reworked
>and documented how this works.
It is much easier for understanding. Thank you! I've tried to consider
an older version.
>Is this necessary? The id should already be set in
>(graphite-sese-to-poly.c):
>
>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);
>
>}
Thank you! I haven't known about this function. Should its declaration
be moved to graphite-sese-to-poly.h or it is better to redefine it in
the graphite-isl-ast-to-gimple.c?
>Perfect! (or at least that's the same approach I have choosen for Polly)
>
>Do you have any problems with this approach? From my perspective it
>looks like a good solution.
No, I don't (at least for now).
--
Cheers, Roman Gareev
[GSoC] Question about the implementation of vec.h
Dear gcc contributors, could you please answer a few questions about the implementation of vec.h? Should we always use “create” to initialize, for example, vec or is it possible to do it using “safe_grow_cleared” or a similar function? There is "vec_safe_grow_cleared", which works with vec. Is there a way to use it with vec? I would be very grateful for your comments. -- Cheers, Roman Gareev.
[GSoC] generation of Gimple code from isl_ast_node_block
= res_20;
_22 = n.0_9 > 0;
if (_22 != 0)
goto ;
else
goto ;
}
bb_4 (preds = {bb_3 }, succs = {bb_5 })
{
:
_23 = (signed long) n.0_9;
_24 = _23 + -1;
}
bb_7 (preds = {bb_5 bb_3 }, succs = {bb_8 })
{
:
# .MEM_32 = PHI <.MEM_31(5), .MEM_21(3)>
# VUSE <.MEM_32>
res_17 = Cross_BB_scalar_dependence.7[0];
_16 = res_17;
}
bb_8 (preds = {bb_7 bb_2 }, succs = {bb_1 })
{
:
# res_12 = PHI <_16(7), 0(2)>
# .MEM_2 = PHI <.MEM_32(7), .MEM_3(D)(2)>
# VUSE <.MEM_2>
return res_12;
}
loop_2 (header = 5, latch = 6, niter = (unsigned long) ((signed
long) n.0_9 + -1), upper_bound = 9223372036854775806)
{
bb_5 (preds = {bb_4 bb_6 }, succs = {bb_6 bb_7 })
{
:
# graphite_IV.8_25 = PHI <0(4), graphite_IV.8_26(6)>
# .MEM_33 = PHI <.MEM_21(4), .MEM_31(6)>
# VUSE <.MEM_33>
res_27 = phi_out_of_ssa.5[0];
_29 = (int) graphite_IV.8_25;
res_28 = res_27 + _29;
# .MEM_30 = VDEF <.MEM_33>
Close_Phi.6[0] = res_28;
# .MEM_31 = VDEF <.MEM_30>
phi_out_of_ssa.5[0] = res_28;
graphite_IV.8_26 = graphite_IV.8_25 + 1;
if (graphite_IV.8_25 < _24)
goto ;
else
goto ;
}
bb_6 (preds = {bb_5 }, succs = {bb_5 })
{
:
goto ;
}
}
}
It seems that isl produce some illegal transformation, because in the
last case it uses the old version of variable res:
bb_7 (preds = {bb_5 bb_3 }, succs = {bb_8 })
{
:
# .MEM_32 = PHI <.MEM_31(5), .MEM_21(3)>
# VUSE <.MEM_32>
res_17 = Cross_BB_scalar_dependence.7[0];
_16 = res_17;
}
The original Gimple code for the second example is similar to the first one:
loop_0 (header = 0, latch = 1, niter = )
{
bb_2 (preds = {bb_0 }, succs = {bb_3 bb_8 })
{
:
# VUSE <.MEM_3(D)>
n.0_9 = n;
if (n.0_9 > 0)
goto ;
else
goto ;
}
bb_3 (preds = {bb_2 }, succs = {bb_5 })
{
:
# .MEM_8 = VDEF <.MEM_3(D)>
phi_out_of_ssa.5[0] = 0;
goto ;
}
bb_4 (preds = {bb_7 }, succs = {bb_8 })
{
:
# .MEM_19 = PHI <.MEM_18(7)>
# VUSE <.MEM_19>
res_17 = Cross_BB_scalar_dependence.7[0];
_16 = res_17;
goto ;
}
bb_7 (preds = {bb_5 }, succs = {bb_4 })
{
:
# VUSE <.MEM_13>
res_4 = Close_Phi.6[0];
# .MEM_18 = VDEF <.MEM_13>
Cross_BB_scalar_dependence.7[0] = res_4;
goto ;
}
bb_8 (preds = {bb_4 bb_2 }, succs = {bb_1 })
{
:
# res_12 = PHI <_16(4), 0(2)>
# .MEM_2 = PHI <.MEM_19(4), .MEM_3(D)(2)>
# VUSE <.MEM_2>
return res_12;
}
loop_1 (header = 5, latch = 6, niter = , upper_bound = 2147483646)
{
bb_5 (preds = {bb_3 bb_6 }, succs = {bb_6 bb_7 })
{
:
# i_10 = PHI <0(3), i_6(6)>
# .MEM_1 = PHI <.MEM_8(3), .MEM_13(6)>
# VUSE <.MEM_1>
res_11 = phi_out_of_ssa.5[0];
res_5 = res_11 + i_10;
# .MEM_7 = VDEF <.MEM_1>
Close_Phi.6[0] = res_5;
# .MEM_13 = VDEF <.MEM_7>
phi_out_of_ssa.5[0] = res_5;
i_6 = i_10 + 1;
if (i_6 < n.0_9)
goto ;
else
goto ;
}
bb_6 (preds = {bb_5 }, succs = {bb_5 })
{
:
goto ;
}
}
}
Do you know anything about this issue? Should we use some options to
avoid illegal transformations (I haven't fount them)? Is it possible
to manually update SSA form to use the last versions of variables (I
haven't found such possibilities)?
P.S. There are other examples of wrong generations, but it is
difficult to find the reason of errors in them.
P.S. CLooG generates the same code for both examples:
CLAST generated by CLooG:
for (scat_1=0;scat_1<=k.0_9-1;scat_1++) {
(scat_1);
}
();
--
Cheers, Roman Gareev.
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)
@@ -547,6 +547,26 @@
return last_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. */
@@ -570,7 +590,8 @@
return next_e;
case isl_ast_node_block:
- return next_e;
+ return translate_isl_ast_node_block (context_loop, node,
+ next_e, ip);
default:
gcc_unreachable ();
Re: [GSoC] generation of Gimple code from isl_ast_node_block
> It seems S_6 is now scheduled before S_4 which is surprising, as
> dependences from S_4 to S_6 should prevent us from generating a schedule
> that yields such a result. What is the schedule that you give to the isl ast
> generator?
The schedule generated by the code, which uses variable k (It executes
without errors):
[k.0] -> { S_6[] -> [1] : exists (e0 = [(-1 + k.0)/4294967296]:
4294967296e0 <= -1 + k.0 and 4294967296e0 >= -2147483647 + k.0);
S_4[i0] -> [0, i0, 0] : exists (e0 = [(-1 + k.0)/4294967296]: i0 >= 0
and 4294967296e0 <= -1 + k.0 and 4294967296e0 >= -4294967296 + k.0 and
4294967296e0 <= -1 + k.0 - i0 and i0 <= 2147483646) }
The schedule generated by the code, which uses variable n:
[n.0] -> { S_6[] -> [1] : exists (e0 = [(-1 + n.0)/4294967296]:
4294967296e0 <= -1 + n.0 and 4294967296e0 >= -2147483647 + n.0);
S_4[i0] -> [0, i0, 0] : exists (e0 = [(-1 + n.0)/4294967296]: i0 >= 0
and 4294967296e0 <= -1 + n.0 and 4294967296e0 >= -4294967296 + n.0 and
4294967296e0 <= -1 + n.0 - i0 and i0 <= 2147483646) }
--
Cheers, Roman Gareev.
Re: [GSoC] generation of Gimple code from isl_ast_node_block
It seems that the problem is solved now. Thank you! I've sent corresponding patches to gcc-patches. -- Cheers, Roman Gareev.
Re: [GSoC] Question about the implementation of vec.h
> Yes, you need to use .create() to initialize vec instances. Thank you for the answer! -- Cheers, Roman Gareev.
[GSoC] checking for the loop parallelism
Tobias, could you please advise me how is it better to determine a depth for loop (it is necessary for loop_is_parallel_p)? In graphite-clast-to-gimple.c. it is done by using the number of dimensions of a domain, which is attached to clast_for. As far as I know, isl doesn't give such a opportunity. If I'm not mistaken “2 * ( level + 1) “ is also not suitable for all cases. -- Cheers, Roman Gareev.
"Integration of ISL code generator into Graphite” moves to the phase of testing
Dear gcc contributors, I am very happy to announce that “Integration of ISL code generator into Graphite” project moves to the phase of testing! I would be very grateful for your comments and feedback about its new isl support, which can be activated by the flag: “ -fgraphite-code-generator=isl" -- Cheers, Roman Gareev.
[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] Status - 20140901 FINAL
> Hi Community! > > Google Summer of Code 2014 has come to an end. We've got some very good > results this year -- with code from 4 out of 5 projects checked in to either > GCC trunk or topic branch. Congratulations to students and mentors for their > great work! > > Even more impressive is the fact that [according to student self-evaluations] > most of the students intend to continue GCC development outside of the > program. > > I encourage both mentors and students to echo their feedback about GCC's GSoC > in this thread. The evaluations you posted on the GSoC website is visible to > only a few people, and there are good comments and thoughts there that > deserve a wider audience. I participated in GSoC 2014, working on «Integration of ISL code generator into Graphite». I would like to thank Tobias Grosser, Richard Biener, Maxim Kuvyrkov and gcc community for your advices, ideas, comments, reviews and the opportunity to work on this project! You can find the description of the project on the following link https://gcc.gnu.org/wiki/ISLCodeGenerator. I’m very happy to announce that all the required deliverables from my proposal were implemented: «Graphite must become fully independent of CLooG library", "GCC should be able to bootstrap", "Pass regression tests", "Add new tests to testsuite». It also should be noted that the number of code lines decreased by 41.42 per cent compared with the previous version of generator. The amount of comments account for 20.6349 per cent of the text of the generator (by comparison, this number is 15,8073 for the previous version). I’m planning to continue working on this project. We have the following goals: 1) Finish the computation of types (in case of completion of its integration into ISL). 2) Profile the generator. 3) Make execution-time and compile-time performance comparisons between CLooG and ISL code generation in Graphite. 4) Use the full/partial tile separation for the tiles generated by the isl scheduler. -- Cheers, Roman Gareev.
Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?
> CLooG is not necessarily needed. You can run graphite just with ISL. The
> main reason that ISL code generation is not enabled by default is that we
> did not yet get extensive testing and it was unclear who will have the time
> to fix possible bugs.
Could you please advise me which test suites should be used to make
performance comparison between CLooG and ISL generator? (I would like
to do this, even though the old generator is removed).
> @Mircae, Roman: Would you have time to help with bug-fixing if we do the
> switch now? (I am happy to review patches and give advice, but can not do
> the full move myself)
I could find time for this. What do you mean by ‘switch’? If I’m not
mistaken, ISL generator is already used by default. Should we remove
support of CLooG generator and all files related to it?
--
Cheers, Roman Gareev.
Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?
> As the ISL code generator has been default since a while and we did not get
> many bug reports, the actual switch seems to have worked well. We could
> probably still need some testing, but in this case it is most likely time to
> drop the CLooG support entirely. Are you interested to provide the relevant
> patches?
>
> Also, as Tobias suggested we should raise the minimal supported isl level to
> 0.14 to be sure PR 62289 is fixed.
Yes, if you don’t mind, I’ll try to provide them by the end of the
week. I’m planning to make two patches: the first one removes files
related to CLooG code generator, the second one removes support of
CLooG library from configure and make files. What do you think about
this?
--
Cheers, Roman Gareev.
Re: RFC: Update ISL under gcc/infrastructure/ ? // Remove CLooG?
> Sounds good as long as they will compile and pass tests independently.
> Please also remember updating the documentation.
I’m trying to build Graphite without CLooG, but I get the following error:
libbackend.a(graphite-optimize-isl.o): In function `getScheduleForBandList':
/home/roman/sec_trunk/gcc/gcc/graphite-optimize-isl.c:357: undefined
reference to `isl_band_member_is_zero_distance'
collect2: error: ld returned 1 exit status
make[3]: *** [lto1] Error 1
make[3]: *** Waiting for unfinished jobs
libbackend.a(graphite-optimize-isl.o): In function `getScheduleForBandList':
/home/roman/sec_trunk/gcc/gcc/graphite-optimize-isl.c:357: undefined
reference to `isl_band_member_is_zero_distance'
collect2: error: ld returned 1 exit status
make[3]: *** [cc1] Error 1
libbackend.a(graphite-optimize-isl.o): In function `getScheduleForBandList':
/home/roman/sec_trunk/gcc/gcc/graphite-optimize-isl.c:357: undefined
reference to `isl_band_member_is_zero_distance'
collect2: error: ld returned 1 exit status
make[3]: *** [cc1plus] Error 1
rm gcov-tool.pod gfdl.pod fsf-funding.pod gcc.pod cpp.pod gcov.pod
make[3]: Leaving directory `/home/roman/compiled/build_graphite_sec/gcc'
make[2]: *** [all-stage1-gcc] Error 2
make[2]: Leaving directory `/home/roman/compiled/build_graphite_sec'
make[1]: *** [stage1-bubble] Error 2
make[1]: Leaving directory `/home/roman/compiled/build_graphite_sec'
make: *** [all] Error 2
Could you please advise me how to fix this? If I’m not mistaken,
r216735 is the only commit related to graphite-optimize-isl.c which
has been made since my latest patch.
--
Cheers, Roman Gareev.
Integration of ISL code generator into Graphite
Dear gcc contributors, I am going to try to participate in Google Summer of Code 2014. My project is "Integration of ISL code generator into Graphite". My proposal can be found at on the following link https://drive.google.com/file/d/0B2Wloo-931AoTWlkMzRobmZKT1U/edit?usp=sharing . I would be very grateful for your comments, feedback and ideas about its improvement. - Roman Gareev
Re: Integration of ISL code generator into Graphite
Hi Mircea, thank you for your comment! I wanted to say, that this AST-like representation is an ISL AST containing only loops, conditions, and statements (basic blocks). It will be differ from a CLooG AST in representation of AST and, possibly, additional options of ISL AST generation. I'll try to eliminate this ambiguity in an improved version of the proposal. 2014-03-17 21:47 GMT+06:00 Mircea Namolaru : > Hi, > > First, I fully agree that integration of the ISL code generator into Graphite > will be an > important step forward for Graphite development. > > Regarding the implementation I have a question - why a new AST-like > representation is needed ? > It is not possible to generate the code directly from the ISL AST (with > possible addition of > new attributes/transformations) ? > > Regards, Mircea > > - Original Message - >> From: "Roman Gareev" >> To: gcc@gcc.gnu.org >> Cc: "Tobias Grosser" , "Albert Cohen" >> , "Mircea Namolaru" >> >> Sent: Friday, March 14, 2014 9:18:40 PM >> Subject: Integration of ISL code generator into Graphite >> >> Dear gcc contributors, >> >> I am going to try to participate in Google Summer of Code 2014. My project >> is "Integration of ISL code generator into Graphite". >> >> My proposal can be found at on the following link >> https://drive.google.com/file/d/0B2Wloo-931AoTWlkMzRobmZKT1U/edit?usp=sharing. >> I would be very grateful for your comments, feedback and ideas about >> its >> improvement. >> >> P.S. Sorry for the copy of this message, the previous one was declined by >> the MAILER-DAEMON. >> >> - >> >> Roman Gareev >> -- Cheers, Roman Gareev.
Re: Integration of ISL code generator into Graphite
Hi Tobias, thank you for all your comments! I've tried to consider them in the improved version of my proposal, which can be found at the following link https://drive.google.com/file/d/0B2Wloo-931AoeUlYOHhETVBvY3M/edit?usp=sharing . > - In unreleased isl 0.13.0, support for compute out feature I haven't found information about this feature and isl 0.13.0. Could you please give me a link to be referred to in the proposal? > - Improved code generation quality I also haven't found code quality comparison between CLooG and ISL code generator. Do you mean, that ISL code generator can improve code quality with unrolling, full/partial tile separation, fine-grained code size adjustments? > - "New internal representaion will be generated by ISL. Its structure is > planned to be similar to the CLAST tree, but can be changed ..." > > What does this mean? The isl_ast representation is already defined. Are you > saying that isl may generate an ast that is different in structure to the > clast tree currently generated? Or are you saying we > still need to define the isl_ast and its nodes itself? I wanted to say that ISL will generate ISL AST from the polyhedral representation. This ISL AST (with pointers to original basic blocks instead of statments) will be internal representation for Graphite, that should be traversed and transformed into the GIMPLE CFG. I eliminated the mention of this internal representation in the improved version of the proposal. -- Cheers, Roman Gareev
