On Thu, May 15, 2014 at 12:30 AM, Prathamesh Kulkarni
<bilbotheelffri...@gmail.com> wrote:
> On Wed, May 14, 2014 at 3:54 PM, Richard Biener
> <richard.guent...@gmail.com> wrote:
>> On Tue, May 13, 2014 at 11:06 PM, Prathamesh Kulkarni
>> <bilbotheelffri...@gmail.com> wrote:
>>> On Tue, May 13, 2014 at 2:36 PM, Richard Biener
>>> <richard.guent...@gmail.com> wrote:
>>>> On Sun, May 11, 2014 at 5:00 PM, Prathamesh Kulkarni
>>>> <bilbotheelffri...@gmail.com> wrote:
>>>>> On Sun, May 11, 2014 at 8:10 PM, Andreas Schwab <sch...@linux-m68k.org>
>>>>> wrote:
>>>>>> Prathamesh Kulkarni <bilbotheelffri...@gmail.com> writes:
>>>>>>
>>>>>>> a) I am not able to follow why 3 slashes are required here
>>>>>>> in x_.\\\(D\\\) ? Why does x_.\(D\) not work ?
>>>>>>
>>>>>> Two of the three backslashes are eaten by the tcl parser. But actually
>>>>>> only two backslashes are needed, since the parens are not special to tcl
>>>>>> (but are special to the regexp engine, so you want a single backslash
>>>>>> surviving the tcl parser).
>>>>>>
>>>>>>> b) The expression after folding would be of the form:
>>>>>>> t2_<digit> = x_<digit>(D) - y_<digit>(D)
>>>>>>> I have used the operator "." in the pattern to match digit.
>>>>>>> While that works in the above case, I think a better
>>>>>>> idea would be to match using [0-9].
>>>>>>> I tried the following but it does not work:
>>>>>>> t_[0-9] = x_[0-9]\\\(D\\\) - y_[0-9]\\\(D\\\)
>>>>>>> Neither does \\\[ and \\\] work.
>>>>>>
>>>>>> Brackets are special in tcl (including inside double quotes), so they
>>>>>> need to be quoted. But you want the brackets to appear unquoted to the
>>>>>> regexp engine, so a single backslash will do the Right Thing.
>>>>>>
>>>>>> See tcl(n) for the tcl parsing rules.
>>>>>>
>>>>> Thanks. Now I get it, the double backslash \\ is an escape sequence
>>>>> for \, and special characters like (, [
>>>>> retain their meaning in quotes, so to match input text: (D), the
>>>>> pattern has to be written as: "\\(D\\)".
>>>>> I believe "\(D\)" would only match D in the input ?
>>>>> I have modified the test-case. Is this version correct ?
>>>>
>>>> I usually verify that by running the testcase in isolation on a GCC version
>>>> that should FAIL it and on one that should PASS it (tcl quoting is also
>>>> try-and-error for me most of the time...).
>>>>
>>>> Thus I do
>>>>
>>>> gcc/> make check-gcc RUNTESTFLAGS="tree-ssa.exp=match-2.c"
>>>> <test should FAIL>
>>>> <patch source tree>
>>>> gcc/> make cc1
>>>> ... compiles cc1 ...
>>>> gcc/> make check-gcc RUNTESTFLAGS="tree-ssa.exp=match-2.c"
>>>> <test should PASS>
>>>>
>>>> A more complete matching for an SSA name would be (allowing
>>>> for SSA name versions > 9) _\\d\+ with \\(D\\) appended if
>>>> suitable (that's usually known from the testcase). \\d\+ should match
>>>> at least one decimal digit.
>>> I thought that SSA name version wouldn't exceed 9 for that test-case,
>>> so I decided for matching only one digit. I will change it to match
>>> one or more digits.
>>>
>>> * I have written test-cases for patterns in match.pd (attached patch), which
>>> result in PASS. Could you review them for me ?
>>> I couldn't write for following ones:
>>>
>>> 1] Patterns involving COMPLEX_EXPR, REALPART_EXPR, IMAGPART_EXPR
>>> (match_and_simplify
>>> (complex (realpart @0) (imagpart @0))
>>> @0)
>>> (match_and_simplify
>>> (realpart (complex @0 @1))
>>> @0)
>>> (match_and_simplify
>>> (imagpart (complex @0 @1))
>>> @1)
>>>
>>> Sorry to be daft, but I couldn't understand what these patterns meant
>>> (I know complex numbers).
>>> Could you give an example that matches one of these patterns ?
>>> Thanks.
>>
>> The existing match-1.c testcase has some ideas. For the first
>> pattern I'd do
>>
>> _Complex double foo (_Complex double z)
>> {
>> double r = __real z;
>> double i = __imag z;
>> return r + 1.0iF * i;
>> }
>>
>> where the return expression is folded (yeah ...) to a COMPLEX_EXPR.
>>
>> For the other two patterns sth like
>>
>> double foo (double r)
>> {
>> _Complex double z = r;
>> return __real z;
>> }
>>
>> and
>>
>> double foo (double i)
>> {
>> _Complex double z = 1.0iF * i;
>> return __imag z;
>> }
>>
>> should work.
>>
> Thanks. Now I understood the meaning of patterns.
> The first pattern should return z instead of returning a new complex
> number from r and i.
> however the test-case doesn't appear to work.
It probably needs building with -ffast-math, the building of the
COMPLEX_EXPR with r + 1.0iF * i triggers interesting corner-cases
otherwise. An alternative is to write
_Complex double foo (_Complex double z)
{
double r = __real z;
double i = __imag z;
_Complex double tem;
__real tem = r;
__imag tem = i;
return tem;
}
> The other two transforms real (complex x) -> real x and imag (complex
> x) -> imag x were simplified.
>
>>> 2] Test-case for FMA_EXPR. I am not sure how to generate FMA_EXPR from C
>>> code.
>>> (match_and_simplify
>>> (fma INTEGER_CST_P@0 INTEGER_CST_P@1 @3)
>>> (plus (mult @0 @1) @3))
>>
>> I believe it's not possible. FMA is matched by the optimize_widen_mult
>> pass which runs quite late, after the last forwprop pass. So I don't think
>> it's possible to write a testcase that triggers with the existing compiler.
>>
> I was wondering if we could possibly use Gimple front-end to write test cases
> ?
> If that's not possible, should we write c-extensions (only for
> testing) that can generate the required pattern ?
> For example something like:
> int f(int x)
> {
> return __fma_expr (3, 4, x); // transform to x + 12 ?
> }
It turns out you can use __builtin_fma (3, 4, x) here. On targets that
have CPU support for fma this will fold to FMA_EXPR (so on x86_64
for example if you build with -mfma).
>>> 3] Test-case for COND_EXPR
>>> (match_and_simplify
>>> (cond (bit_not @0) @1 @2)
>>> (cond @0 @2 @1))
>>>
>>> I believe cond corresponds to C's ternary operator ?
>>> However c-expression of the form:
>>> t2 = (x ? y : z)
>>> gets translated to gimple as an if-else statement, with "x" being condition,
>>> "y" being then-statement, and "z" being else-statement.
>>> So I guess we need to handle this case specially in genmatch ?
>>> Or am I mistaken ?
>>
>> One idea was to also match if-then-else as COND_EXPR (something
>> to explore later), but you can also see COND_EXPRs in the GIMPLE IL,
>> for example they are created by if-conversion which runs before
>> vectorization. But as above, it's difficult to create a testcase to
>> match on a forwprop transform (those patterns are more likely to
>> match from the various passes code-generation which need to be
>> updated to use the gimple_build interface provided on the breanch).
>>
>> As of the if-then-else idea, for example
>>
>> int foo (int x)
>> {
>> return x ? 3 : 5;
>> }
>>
>> is seen as
>>
>> <bb 2>:
>> if (x_2(D) != 0)
>> goto <bb 4>;
>> else
>> goto <bb 3>;
>>
>> <bb 3>:
>>
>> <bb 4>:
>> # iftmp_1 = PHI <1(2), 0(3)>
>> return iftmp_1;
>>
>> in GIMPLE SSA form. Thus the COND_EXPR is translated
>> to a PHI node and a controling predicate.
>>
>> But as said, I'd say we should defer this to a later stage if
>> time permits.
> Matching if-else to COND_EXPR looks interesting -:)
Yeah ;) Research topic for a GSOC followup.
>>
>>> * I added few patterns from TODO list in match.pd. I am
>>> not sure how to write pattern for the following transform:
>>> (T) (P + A) - (T) P -> (T) A
>>
>> This tries to match C pointer difference GIMPLE which is carried
>> out using integer types. You'd write sth like
>>
>> (match_and_simplify
>> (minus (convert (pointer_plus @0 @1))
>> (convert @0))
>> (convert @1))
>>
> For P + A - P, why would we need convert ? Why won't the following work:
> (match_and_simplify
> (minus (pointer_plus @0 @1) @0)
> @1)
Because the IL we are trying to match looks like
_2 = (sizetype) offset_1(D);
t1_4 = p_3(D) + _2;
t1.0_5 = (long int) t1_4;
p.1_6 = (long int) p_3(D);
_7 = t1.0_5 - p.1_6;
so we need to match the conversions. As I said above conversions
are odd as there are both NOP_EXPR and CONVERT_EXPR used
interchangably, so the code generator needs to not check for
what we write literally (nop or convert - I prefer convert), but always
check for both, NOP_EXPR and CONVERT_EXPR. It doesn't do
that yet. The following fixes that and makes the pattern work:
Index: genmatch.c
===================================================================
--- genmatch.c (revision 210414)
+++ genmatch.c (working copy)
@@ -282,8 +282,12 @@ expr::gen_gimple_match (FILE *f, const c
fprintf (f, "if (TREE_CODE (%s) == SSA_NAME)\n", name);
fprintf (f, " {\n");
fprintf (f, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", name);
- fprintf (f, "if (!is_gimple_assign (def_stmt)\n"
- " || gimple_assign_rhs_code (def_stmt) != %s) ", op->id);
+ fprintf (f, "if (!is_gimple_assign (def_stmt)\n");
+ if (op->code == NOP_EXPR
+ || op->code == CONVERT_EXPR)
+ fprintf (f, " || !CONVERT_EXPR_CODE_P
(gimple_assign_rhs_code (def_stmt))) ");
+ else
+ fprintf (f, " || gimple_assign_rhs_code (def_stmt) != %s)
", op->id);
gen_gimple_match_fail (f, label);
if (op->code == REALPART_EXPR
|| op->code == IMAGPART_EXPR
I'll check it in shortly.
Richard.
> I tried both the patters (with and without convert) with the following
> test-case, however it doesn't get simplified:
> int foo(char *p, int offset)
> {
> char *t1 = p + offset;
> return t1 - p;
> }
>
>> where a few issues show up.
>>
>> First, in GIMPLE we can
>> have both NOP_EXPR and CONVERT_EXPR which mean the
>> same (and are generally tested with CONVERT_EXRP_P).
>> So the in the patterns we should prefer one of both (I'd say
>> convert) but the code generator has to match both (actually
>> NOP_EXPR appears way more often).
>>
>> Second, for the simplified pattern we generate a convert - but
>> generally we'd want to supply a type to convert to (the current
>> code will simply pick the type of the original expression which
>> is the correct one in this case). So for other cases I would
>> expect we'd need to write
>>
>> (match_and_simplify
>> (minus (convert@2 (pointer_plus @0 @1))
>> (convert @0))
>> { fold_convert (TREE_TYPE (@2), @1); })
>>
>> thus use C code because there isn't (yet) a way to specify a
>> type for a to generate expression. I don't expect this to
>> show up very often and thus I didn't look after a syntax
>> to specify types for expression generation or matching
>> as there exists a workaround (by using C expressions for
>> the generation part and an appropriate if-expression for the
>> matching part).
>>
>>> * ICE for transform sqrt (x * x) -> x
>>> The following pattern results in ICE (gimple-match-head.c:546)
>>> (match_and_simplify
>>> (built_in_sqrt (mult @0 @0))
>>> @0)
>>>
>>> I triggered the pattern with this test-case:
>>> double foo(double x)
>>> {
>>> double t1, t2;
>>> t1 = x * x;
>>> t2 = sqrt (t1);
>>> return t2;
>>> }
>>>
>>> This happens because the following assert fails in
>>> bool gimple_match_and_simplify (gimple_stmt_iterator *gsi, tree
>>> (*valueize)(tree)): line 546:
>>> gcc_assert (gimple_seq_singleton_p (tail));
>>>
>>> I guess that happens because for the above pattern
>>> maybe_push_res_to_seq() returns ops[0], and tail remains NULL.
>>>
>>> if (TREE_CODE_LENGTH ((tree_code) rcode) == 0
>>> && is_gimple_val (ops[0]))
>>> return ops[0];
>>>
>>> Unfortunately, I couldn't find a fix.
>>
>> Ah, at this point we have a call which we'd like to replace with
>> a SSA name result. But maybe_push_res_to_seq only pushes
>> if necessary (and for an SSA name or a constant it is not so),
>> but here it's always necessary.
>>
>>> I have a couple of questions regarding gimple-match-head.c
>>>
>>> a) Why do we return if the above condition is true ?
>>> I mean why don't we want gimple_build_assign_with_ops to be called
>>> if that's true ?
>>
>> Because in all other callers this results in more optimal code.
>>
>>> Removing that condition in maybe_push_res_to_seq or calling
>>> gimple_build_assign_with_ops (rcode, lhs, ops[0], NULL_TREE, NULL_TREE,
>>> NULL_TREE);
>>> from gimple_match_and_simplify (if maybe_push_res_to_seq returns ops[0]),
>>> resulted in verify_ssa failed: missing definition.
>>
>> Yeah, I have a fix for that as well. The call handling code is pretty
>> new and likely needs some fixes. I'll be available to fix up the
>> details there (they can be tricky).
>>
>> Fix in svn now, btw.
>>
>>> b) In
>>> static bool
>>> gimple_match_and_simplify (gimple stmt,
>>> code_helper *rcode, tree *ops,
>>> gimple_seq *seq, tree (*valueize)(tree))
>>>
>>> why do we return false by default (line 491), if number of args is
>>> greater than 1 ?
>>
>> Because I didn't implement support for that yet ;) Support for
>> two arguments is the case 1 cut&pasted and all code handling
>> arg1 duplicated for arg2 as well (and the call to
>> gimple_match_and_simplify gets an additional argument).
>> Not sure if the code generation part is in place yet though.
>>
>> As said above - call handling was written quickly and only late.
>>
>> I'll see to add the two-argument case.
>>
>> I'll review the testcase patch separately.
>>
>> Thanks,
>> Richard.
>>
>>> Thanks and Regards,
>>> Prathamesh
>>>>
>>>> Richard.
>>>>
>>>>> Thanks and Regards,
>>>>> Prathamesh
>>>>>
>>>>>
>>>>>> Andreas.
>>>>>>
>>>>>> --
>>>>>> Andreas Schwab, sch...@linux-m68k.org
>>>>>> GPG Key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5
>>>>>> "And now for something completely different."
