Re: [GSoC] generation of GCC expression trees from isl ast expressions
On 23/06/2014 08:34, Roman Gareev wrote:
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.
I think a better approach is to use isl_ast_expr_get_val() and to then
use isl_val_get_num_gmp() (see val_gmp.h). isl_int will be removed in
newer versions of isl and the above functions are the new interface to
get gmp values.
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)?
I assume so. However, we always want signed types, so the second
argument should be zero, no?
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?
May be. Feel free to reuse it if you feel you need it, but don't worry
if you need different data structures. I will review its use in case you
add it.
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.
We should support all that can occur. isl_ast_op_access won't ever be
built for the input we provide, similarly isl_ast_op_call, and possibly
isl_ast_op_member. The others may just be missing in Polly or may not be
needed for certain options.
For now, let's start with a basic set that we can test and extend later.
The first draft of generation of GCC expression trees from isl ast
expressions can be found below:
Comments inline.
+/* 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);
+}
OK.
+static tree
+gcc_expression_from_isl_expression (tree type, __isl_keep isl_ast_expr *);
+
+/* 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);
+}
As discussed above avoid the use of isl_int.
+/* 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)
+{
+ 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);
+ 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);
+ 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);
How did you verify that the semantics of the GCC and isl expressions are
identical?
+case isl_ast_op_eq:
+ return fold_build2 (EQ_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+case isl_ast_op_le:
+ return fold_build2 (LE_EXPR, type, tree_lhs_expr, tree_rhs_expr);
+
+case isl_ast_op_lt:
+ return fold_build2 (LT
Re: [GSoC] commutative patterns
On Sun, Jun 22, 2014 at 9:52 PM, Prathamesh Kulkarni
wrote:
> On Sun, Jun 22, 2014 at 3:09 AM, Prathamesh Kulkarni
> wrote:
>> On Fri, Jun 20, 2014 at 3:02 AM, Prathamesh Kulkarni
>> wrote:
>>>
>>> On Fri, Jun 20, 2014 at 2:53 AM, Prathamesh Kulkarni
>>> wrote:
>>> > Hi,
>>> > The attached patch attempts to generate commutative variants for
>>> > a given expression.
>>> >
>>> > Example:
>>> > For the AST: (PLUS_EXPR (PLUS_EXPR @0 @1) @2),
>>> >
>>> > the commutative variants are:
>>> > (PLUS_EXPR (PLUS_EXPR @0 @1 ) @2 )
>>> > (PLUS_EXPR (PLUS_EXPR @1 @0 ) @2 )
>>> > (PLUS_EXPR @2 (PLUS_EXPR @0 @1 ) )
>>> > (PLUS_EXPR @2 (PLUS_EXPR @1 @0 ) )
>>> >
>>> >
>>> > * Basic Idea:
>>> > Consider expression e with two operands o0, and o1,
>>> > and expr-code denoting expression's code (plus/mult, etc.)
>>> >
>>> > Commutative variants are stored in vector (vec).
>>> >
>>> > vec
>>> > commutative (e)
>>> > {
>>> > if (e is not commutative)
>>> > return [e]; // vector with only one expression
>>> >
>>> > v1 = commutative (o0);
>>> > v2 = commutative (o1);
>>> > ret = []
>>> >
>>> > for i = 0 ... v1.length ()
>>> > for j = 0 ... v2.length ()
>>> > {
>>> > ne = new expr with and operands: v1[i], v2[j];
>>> > append ne to ret;
>>> > }
>>> >
>>> > for i = 0 ... v2.length ()
>>> > for j = 0 ... v1.length ()
>>> > {
>>> > ne = new expr with and operand: v2[i], v1[j];
>>> > append ne to ret
>>> > }
>>> >
>>> > return ret;
>>> > }
>>> >
>>> > Example:
>>> > (plus (plus @0 @1) (plus @2 @3))
>>> > generates following commutative variants:
>>> oops.
>>> the pattern given to genmatch was (bogus):
>>> (plus (plus @0 @1) (plus @0 @3))
>>> >
>>> > (PLUS_EXPR (PLUS_EXPR @0 @1 ) (PLUS_EXPR @0 @3 ) )
>>> > (PLUS_EXPR (PLUS_EXPR @0 @1 ) (PLUS_EXPR @3 @0 ) )
>>> > (PLUS_EXPR (PLUS_EXPR @1 @0 ) (PLUS_EXPR @0 @3 ) )
>>> > (PLUS_EXPR (PLUS_EXPR @1 @0 ) (PLUS_EXPR @3 @0 ) )
>>> > (PLUS_EXPR (PLUS_EXPR @0 @3 ) (PLUS_EXPR @0 @1 ) )
>>> > (PLUS_EXPR (PLUS_EXPR @0 @3 ) (PLUS_EXPR @1 @0 ) )
>>> > (PLUS_EXPR (PLUS_EXPR @3 @0 ) (PLUS_EXPR @0 @1 ) )
>>> > (PLUS_EXPR (PLUS_EXPR @3 @0 ) (PLUS_EXPR @1 @0 ) )
>>> >
>>> >
>>> > * Decide which operators are commutative.
>>> > Currently I assume all PLUS_EXPR and MULT_EXPR are true.
>>> s/true/commutative
>> There's a bug in the previous patch - if the operator is not
>> commutative, it does not try
>> for generating commutative variants of it's operands, and does not
>> commutate captured
>> expression (.what).
>> example:
>> (negate (plus @0 @1)) has two commutative variants (including the
>> original pattern),
>> but the patch does not generate them, since negate is not commutative.
>>
>> The attached patch fixes that. As a quick hack i handled each operator
>> class (unary, binary, ternary)
>> specially (commutate_unary, commutate_binary, commutate_ternary).
>> Ideally it should be unified
>> (I tried that way, but it was segfaulting). I will try and come up
>> with a better way.
>> Also the current patch won't work for built-in functions/operators
>> having more than 3 operands.
>> (max we have 3 so far in match.pd for cond, I hope this doesn't come
>> "in the way").
>>
>> With the current patch,
>> for the expression (negate (plus @0 @1))
>> it generates following commutative variants:
>> (negate (plus @0 @1))
>> (negate (plus @1 @0))
>>
>> and for the following pattern (involving captured expression):
>> (negate (plus@0 @1 @2))
>> it generates following variants:
>> (negate (plus@0 @1 @2))
>> (negate (plus@0 @2 @1))
>>
>> * generates multiple matching patterns
>> Since at AST-level we do not test for captures equality (true/match),
>> it treats both of the captures
>> as different, even though they are same.
>> example: the following also expression has 2 variants generated
>> (BUILT_IN_SQRT (mult @0 @0))
>> commutative variants:
>> (BUILT_IN_SQRT (mult @0 @0))
>> (BUILT_IN_SQRT (mult @0 @0))
>> I guess this won't really be a problem with decision tree. If we decide to
>> emit
>> warning, we should warn only for user defined patterns, and not generated
>> ones.
>>
>> * syntax for commutative operators
>> Currently, I assume any PLUS_EXPR / MULT_EXPR to be commutative.
>> I guess we should have syntax for users marking an operator to be
>> commutative.
>>
>> sth like:
>> a) op:c
>> b) op "c"
>> c) op!
>> d) op "commutative"
>>
>> Or any other, that you would like -:)
>>
>> * cloning AST nodes
>> Currently I do not do a deep-copy of the AST for each distinct
>> commutative variant, so the nodes
>> are shared for different expressions, which are commutative variants
>> of the original expression.
>> Is this OK, or should we clone each AST node, so that each expression
>> is represented by a distinct AST ?
>> cloning shall eat up space, while sharing shall require more careful
>> memory management (freeing one ast, may also
>> free nodes of other expression).
> This patch removes the hack of special handling
Re: [GSoC] decision tree first steps
On Mon, Jun 23, 2014 at 10:26 AM, Prathamesh Kulkarni
wrote:
> On Thu, Jun 19, 2014 at 7:53 PM, Prathamesh Kulkarni
> wrote:
>> On Thu, Jun 19, 2014 at 4:12 PM, Prathamesh Kulkarni
>> wrote:
>>> On Thu, Jun 19, 2014 at 2:37 PM, Prathamesh Kulkarni
>>> wrote:
Replying to the last mail in the thread.
The attached patch separates decision tree from AST, (removes the
"parent bug") and attempts to
add support for special case patterns requiring GENERIC (however it
fails one test in match-1.c, I am looking
into that). Code-gen for matching is off the decision tree and
code-gen for transform is off the AST.
* Representation of decision tree
dt_operand is used for representing AST operand / true / match in the
decision tree,
dt_operand::parent points to the decision tree node, the AST parent is
mapped to, not the pre-order predecessor.
dt_operand::pos gives the operand number (0th operand, 1st operand,
etc. of parent etc.)
I have also clubbed true and match in the same class, because true
does not require additional fields,
and match has only one additional field (unsigned m_level).
For the following pairs of (bogus) patterns:
(plus @0 (bit_not@2 @1))
(plus @1 (bit_not@3 @0))
It builds following decision tree:
(type, address, level, n_kids)
root (0x1513550), 0, 1
|--PLUS_EXPR (0x1502370), 1, 1
|true (0x15023f0), 2, 1
|--BIT_NOT_EXPR (0x1502470), 3, 1
|true (0x15024f0), 4, 2
|--simplify_0 { 2, 4, 3, 4294967295, } (0x1512540), 5, 0
|--simplify_1 { 4, 2, 4294967295, 3, } (0x15125c0), 5, 0
and for the following pairs of (bogus) patterns:
(plus (minus@0 @1 @2) @3)
(plus (minus @0 @1) @2)
It builds following tree:
root (0x10e2520), 0, 1
|--PLUS_EXPR (0x10d1370), 1, 1
|MINUS_EXPR (0x10d13f0), 2, 1
|--true (0x10d1470), 3, 1
|true (0x10d14f0), 4, 1
|--true (0x10e1540), 5, 2
|simplify_0 { 2, 3, 4, 5, } (0x10e15c0), 6, 0
|simplify_1 { 3, 4, 5, 4294967295, } (0x10e1640), 6, 0
Is that correct ?
Yes, that looks correct.
* Code-gen
The code-gen is mostly same, with following changes:
a) Generation of expressions:
At expr-node, the children are immediately assigned in temporaries
(t0, t1 ,...),
and when we come at child node, the temporary is assigned to child
node (o = t).
Temporary names are stored in dt_operand::temps vector.
b) Is the following condition correct (considering for convert) ?:
if (is_gimple_assign (def_stmt) &&
(gimple_assign_rhs_code (def_stmt) ==
|| CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
{
// generated code for operands
}
>>> oops, that's only for CONVERT_EXPR and NOP_EXPR.
>>> Fixed in the current patch
Looking at dt8.patch it still seems wrong:
+ if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
+fprintf (f, "if (is_gimple_assign (def_stmt) &&\n"
+" (gimple_assign_rhs_code (def_stmt) == %s\n"
+ " || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code
(def_stmt\n", op_id->id);
should be simply generate
if (is_gimple_assign (def_stmt) && CONVERT_EXPR_CODE_P
(gimple_assign_rhs_code (def_stmt)))
that is, the == %s check is superfluous.
>> This patch fixes some more mistakes of the previous patch, and removes
>> .gen_gimple_match functions.
Good. Btw, the patch doesn't apply on the unpatched svn branch for me
(maybe because I applied the commutative patch with some adjustments).
Can you re-diff it for me so I can apply it?
>> It now passes all tests from match-1.c
>> The test-case was failing because I didn't generate valueize code correctly.
>> It should have been:
>> if ((t = do_valueize (valueize, t)) != 0)
>> and the code getting generated was:
>> if (do_valueize (valueize, t))
>>
>> This patch supports all the patterns in match.pd. What changes would I
>> need to make to make it a commit-ready patch ?
I'm looking through the patch right now.
> Added line directives in this patch.
> I am not sure where to output line directives for match operands
> since, they are interleaved in the decision tree.
> I put line directives of respecitve patterns,on top of
> if (code == ), for all patterns having root as
I think the match part cannot be easily annotated with line-directives
(as you found out). I'd simply not emit any - it should be easy enough
to back-track from the ifexpr and code-gen line-directives.
So simply remove them again.
@@ -29,7 +29,8 @@ along with GCC; see the file COPYING3.
#include "hashtab.h"
#include "hash-table.h"
#include "vec.h"
-
+#include
+#include
those headers should already be included via system.h (in general
system headers need to be included by system.h).
Otherwise
Re: [GSoC] decision tree first steps
On Mon, Jun 23, 2014 at 1:51 PM, Prathamesh Kulkarni
wrote:
> On Mon, Jun 23, 2014 at 3:38 PM, Richard Biener
> wrote:
>> On Mon, Jun 23, 2014 at 10:26 AM, Prathamesh Kulkarni
>> wrote:
>>> On Thu, Jun 19, 2014 at 7:53 PM, Prathamesh Kulkarni
>>> wrote:
On Thu, Jun 19, 2014 at 4:12 PM, Prathamesh Kulkarni
wrote:
> On Thu, Jun 19, 2014 at 2:37 PM, Prathamesh Kulkarni
> wrote:
>>
>> Replying to the last mail in the thread.
>>
>> The attached patch separates decision tree from AST, (removes the
>> "parent bug") and attempts to
>> add support for special case patterns requiring GENERIC (however it
>> fails one test in match-1.c, I am looking
>> into that). Code-gen for matching is off the decision tree and
>> code-gen for transform is off the AST.
>>
>> * Representation of decision tree
>> dt_operand is used for representing AST operand / true / match in the
>> decision tree,
>> dt_operand::parent points to the decision tree node, the AST parent is
>> mapped to, not the pre-order predecessor.
>> dt_operand::pos gives the operand number (0th operand, 1st operand,
>> etc. of parent etc.)
>> I have also clubbed true and match in the same class, because true
>> does not require additional fields,
>> and match has only one additional field (unsigned m_level).
>>
>> For the following pairs of (bogus) patterns:
>> (plus @0 (bit_not@2 @1))
>> (plus @1 (bit_not@3 @0))
>>
>> It builds following decision tree:
>> (type, address, level, n_kids)
>>
>> root (0x1513550), 0, 1
>> |--PLUS_EXPR (0x1502370), 1, 1
>> |true (0x15023f0), 2, 1
>> |--BIT_NOT_EXPR (0x1502470), 3, 1
>> |true (0x15024f0), 4, 2
>> |--simplify_0 { 2, 4, 3, 4294967295, } (0x1512540), 5, 0
>> |--simplify_1 { 4, 2, 4294967295, 3, } (0x15125c0), 5, 0
>>
>> and for the following pairs of (bogus) patterns:
>> (plus (minus@0 @1 @2) @3)
>> (plus (minus @0 @1) @2)
>>
>> It builds following tree:
>> root (0x10e2520), 0, 1
>> |--PLUS_EXPR (0x10d1370), 1, 1
>> |MINUS_EXPR (0x10d13f0), 2, 1
>> |--true (0x10d1470), 3, 1
>> |true (0x10d14f0), 4, 1
>> |--true (0x10e1540), 5, 2
>> |simplify_0 { 2, 3, 4, 5, } (0x10e15c0), 6, 0
>> |simplify_1 { 3, 4, 5, 4294967295, } (0x10e1640), 6, 0
>>
>> Is that correct ?
>>
>> Yes, that looks correct.
>>
>> * Code-gen
>> The code-gen is mostly same, with following changes:
>>
>> a) Generation of expressions:
>> At expr-node, the children are immediately assigned in temporaries
>> (t0, t1 ,...),
>> and when we come at child node, the temporary is assigned to child
>> node (o = t).
>> Temporary names are stored in dt_operand::temps vector.
>>
>> b) Is the following condition correct (considering for convert) ?:
>>
>> if (is_gimple_assign (def_stmt) &&
>> (gimple_assign_rhs_code (def_stmt) ==
>> || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
>> {
>> // generated code for operands
>> }
> oops, that's only for CONVERT_EXPR and NOP_EXPR.
> Fixed in the current patch
>>
>> Looking at dt8.patch it still seems wrong:
>>
>> + if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
>> +fprintf (f, "if (is_gimple_assign (def_stmt) &&\n"
>> +" (gimple_assign_rhs_code (def_stmt) == %s\n"
>> + " || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code
>> (def_stmt\n", op_id->id);
>>
>> should be simply generate
>>
>> if (is_gimple_assign (def_stmt) && CONVERT_EXPR_CODE_P
>> (gimple_assign_rhs_code (def_stmt)))
>>
>> that is, the == %s check is superfluous.
> Thanks, removed it.
>>
This patch fixes some more mistakes of the previous patch, and removes
.gen_gimple_match functions.
>>
>> Good. Btw, the patch doesn't apply on the unpatched svn branch for me
>> (maybe because I applied the commutative patch with some adjustments).
>> Can you re-diff it for me so I can apply it?
>>
It now passes all tests from match-1.c
The test-case was failing because I didn't generate valueize code
correctly.
It should have been:
if ((t = do_valueize (valueize, t)) != 0)
and the code getting generated was:
if (do_valueize (valueize, t))
This patch supports all the patterns in match.pd. What changes would I
need to make to make it a commit-ready patch ?
>>
>> I'm looking through the patch right now.
>>
>>> Added line directives in this patch.
>>> I am not sure where to output line directives for match operands
>>> since, they are interleaved in the decision tree.
>>> I put line directives of respecitve patterns,on top of
>>> if (code == ), for all patterns having root as
>>
>> I think the match part cannot be easily annotated with line-directives
>> (as you found o
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
Re: [GSoC] decision tree first steps
On Mon, Jun 23, 2014 at 5:58 PM, Richard Biener
wrote:
> On Mon, Jun 23, 2014 at 1:51 PM, Prathamesh Kulkarni
> wrote:
>> On Mon, Jun 23, 2014 at 3:38 PM, Richard Biener
>> wrote:
>>> On Mon, Jun 23, 2014 at 10:26 AM, Prathamesh Kulkarni
>>> wrote:
On Thu, Jun 19, 2014 at 7:53 PM, Prathamesh Kulkarni
wrote:
> On Thu, Jun 19, 2014 at 4:12 PM, Prathamesh Kulkarni
> wrote:
>> On Thu, Jun 19, 2014 at 2:37 PM, Prathamesh Kulkarni
>> wrote:
>>>
>>> Replying to the last mail in the thread.
>>>
>>> The attached patch separates decision tree from AST, (removes the
>>> "parent bug") and attempts to
>>> add support for special case patterns requiring GENERIC (however it
>>> fails one test in match-1.c, I am looking
>>> into that). Code-gen for matching is off the decision tree and
>>> code-gen for transform is off the AST.
>>>
>>> * Representation of decision tree
>>> dt_operand is used for representing AST operand / true / match in the
>>> decision tree,
>>> dt_operand::parent points to the decision tree node, the AST parent is
>>> mapped to, not the pre-order predecessor.
>>> dt_operand::pos gives the operand number (0th operand, 1st operand,
>>> etc. of parent etc.)
>>> I have also clubbed true and match in the same class, because true
>>> does not require additional fields,
>>> and match has only one additional field (unsigned m_level).
>>>
>>> For the following pairs of (bogus) patterns:
>>> (plus @0 (bit_not@2 @1))
>>> (plus @1 (bit_not@3 @0))
>>>
>>> It builds following decision tree:
>>> (type, address, level, n_kids)
>>>
>>> root (0x1513550), 0, 1
>>> |--PLUS_EXPR (0x1502370), 1, 1
>>> |true (0x15023f0), 2, 1
>>> |--BIT_NOT_EXPR (0x1502470), 3, 1
>>> |true (0x15024f0), 4, 2
>>> |--simplify_0 { 2, 4, 3, 4294967295, } (0x1512540), 5, 0
>>> |--simplify_1 { 4, 2, 4294967295, 3, } (0x15125c0), 5, 0
>>>
>>> and for the following pairs of (bogus) patterns:
>>> (plus (minus@0 @1 @2) @3)
>>> (plus (minus @0 @1) @2)
>>>
>>> It builds following tree:
>>> root (0x10e2520), 0, 1
>>> |--PLUS_EXPR (0x10d1370), 1, 1
>>> |MINUS_EXPR (0x10d13f0), 2, 1
>>> |--true (0x10d1470), 3, 1
>>> |true (0x10d14f0), 4, 1
>>> |--true (0x10e1540), 5, 2
>>> |simplify_0 { 2, 3, 4, 5, } (0x10e15c0), 6, 0
>>> |simplify_1 { 3, 4, 5, 4294967295, } (0x10e1640), 6, 0
>>>
>>> Is that correct ?
>>>
>>> Yes, that looks correct.
>>>
>>> * Code-gen
>>> The code-gen is mostly same, with following changes:
>>>
>>> a) Generation of expressions:
>>> At expr-node, the children are immediately assigned in temporaries
>>> (t0, t1 ,...),
>>> and when we come at child node, the temporary is assigned to child
>>> node (o = t).
>>> Temporary names are stored in dt_operand::temps vector.
>>>
>>> b) Is the following condition correct (considering for convert) ?:
>>>
>>> if (is_gimple_assign (def_stmt) &&
>>> (gimple_assign_rhs_code (def_stmt) ==
>>> || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
>>> {
>>> // generated code for operands
>>> }
>> oops, that's only for CONVERT_EXPR and NOP_EXPR.
>> Fixed in the current patch
>>>
>>> Looking at dt8.patch it still seems wrong:
>>>
>>> + if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
>>> +fprintf (f, "if (is_gimple_assign (def_stmt) &&\n"
>>> +" (gimple_assign_rhs_code (def_stmt) == %s\n"
>>> + " || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code
>>> (def_stmt\n", op_id->id);
>>>
>>> should be simply generate
>>>
>>> if (is_gimple_assign (def_stmt) && CONVERT_EXPR_CODE_P
>>> (gimple_assign_rhs_code (def_stmt)))
>>>
>>> that is, the == %s check is superfluous.
>> Thanks, removed it.
>>>
> This patch fixes some more mistakes of the previous patch, and removes
> .gen_gimple_match functions.
>>>
>>> Good. Btw, the patch doesn't apply on the unpatched svn branch for me
>>> (maybe because I applied the commutative patch with some adjustments).
>>> Can you re-diff it for me so I can apply it?
>>>
> It now passes all tests from match-1.c
> The test-case was failing because I didn't generate valueize code
> correctly.
> It should have been:
> if ((t = do_valueize (valueize, t)) != 0)
> and the code getting generated was:
> if (do_valueize (valueize, t))
>
> This patch supports all the patterns in match.pd. What changes would I
> need to make to make it a commit-ready patch ?
>>>
>>> I'm looking through the patch right now.
>>>
Added line directives in this patch.
I am not sure where to output line directives for match operands
since, they are interleaved in the decision tree.
I put line direct
Re: [GSoC] decision tree first steps
On Mon, Jun 23, 2014 at 3:01 PM, Prathamesh Kulkarni
wrote:
> On Mon, Jun 23, 2014 at 5:58 PM, Richard Biener
> wrote:
>> On Mon, Jun 23, 2014 at 1:51 PM, Prathamesh Kulkarni
>> wrote:
>>> On Mon, Jun 23, 2014 at 3:38 PM, Richard Biener
>>> wrote:
On Mon, Jun 23, 2014 at 10:26 AM, Prathamesh Kulkarni
wrote:
> On Thu, Jun 19, 2014 at 7:53 PM, Prathamesh Kulkarni
> wrote:
>> On Thu, Jun 19, 2014 at 4:12 PM, Prathamesh Kulkarni
>> wrote:
>>> On Thu, Jun 19, 2014 at 2:37 PM, Prathamesh Kulkarni
>>> wrote:
Replying to the last mail in the thread.
The attached patch separates decision tree from AST, (removes the
"parent bug") and attempts to
add support for special case patterns requiring GENERIC (however it
fails one test in match-1.c, I am looking
into that). Code-gen for matching is off the decision tree and
code-gen for transform is off the AST.
* Representation of decision tree
dt_operand is used for representing AST operand / true / match in the
decision tree,
dt_operand::parent points to the decision tree node, the AST parent is
mapped to, not the pre-order predecessor.
dt_operand::pos gives the operand number (0th operand, 1st operand,
etc. of parent etc.)
I have also clubbed true and match in the same class, because true
does not require additional fields,
and match has only one additional field (unsigned m_level).
For the following pairs of (bogus) patterns:
(plus @0 (bit_not@2 @1))
(plus @1 (bit_not@3 @0))
It builds following decision tree:
(type, address, level, n_kids)
root (0x1513550), 0, 1
|--PLUS_EXPR (0x1502370), 1, 1
|true (0x15023f0), 2, 1
|--BIT_NOT_EXPR (0x1502470), 3, 1
|true (0x15024f0), 4, 2
|--simplify_0 { 2, 4, 3, 4294967295, } (0x1512540), 5, 0
|--simplify_1 { 4, 2, 4294967295, 3, } (0x15125c0), 5, 0
and for the following pairs of (bogus) patterns:
(plus (minus@0 @1 @2) @3)
(plus (minus @0 @1) @2)
It builds following tree:
root (0x10e2520), 0, 1
|--PLUS_EXPR (0x10d1370), 1, 1
|MINUS_EXPR (0x10d13f0), 2, 1
|--true (0x10d1470), 3, 1
|true (0x10d14f0), 4, 1
|--true (0x10e1540), 5, 2
|simplify_0 { 2, 3, 4, 5, } (0x10e15c0), 6, 0
|simplify_1 { 3, 4, 5, 4294967295, } (0x10e1640), 6, 0
Is that correct ?
Yes, that looks correct.
* Code-gen
The code-gen is mostly same, with following changes:
a) Generation of expressions:
At expr-node, the children are immediately assigned in temporaries
(t0, t1 ,...),
and when we come at child node, the temporary is assigned to child
node (o = t).
Temporary names are stored in dt_operand::temps vector.
b) Is the following condition correct (considering for convert) ?:
if (is_gimple_assign (def_stmt) &&
(gimple_assign_rhs_code (def_stmt) ==
|| CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
{
// generated code for operands
}
>>> oops, that's only for CONVERT_EXPR and NOP_EXPR.
>>> Fixed in the current patch
Looking at dt8.patch it still seems wrong:
+ if (op_id->code == NOP_EXPR || op_id->code == CONVERT_EXPR)
+fprintf (f, "if (is_gimple_assign (def_stmt) &&\n"
+" (gimple_assign_rhs_code (def_stmt) == %s\n"
+ " || CONVERT_EXPR_CODE_P (gimple_assign_rhs_code
(def_stmt\n", op_id->id);
should be simply generate
if (is_gimple_assign (def_stmt) && CONVERT_EXPR_CODE_P
(gimple_assign_rhs_code (def_stmt)))
that is, the == %s check is superfluous.
>>> Thanks, removed it.
>> This patch fixes some more mistakes of the previous patch, and removes
>> .gen_gimple_match functions.
Good. Btw, the patch doesn't apply on the unpatched svn branch for me
(maybe because I applied the commutative patch with some adjustments).
Can you re-diff it for me so I can apply it?
>> It now passes all tests from match-1.c
>> The test-case was failing because I didn't generate valueize code
>> correctly.
>> It should have been:
>> if ((t = do_valueize (valueize, t)) != 0)
>> and the code getting generated was:
>> if (do_valueize (valueize, t))
>>
>> This patch supports all the patterns in match.pd. What changes would I
>> need to make to make it a commit-ready patch ?
I'm looking through the patch right now.
>
