Cannot get Bit test RTL to cooperate with Combine.

Cannot get Bit test RTL to cooperate with Combine.

[Andrew Hutchinson]

All,

I have been debugging AVR port to see why we fail to match so many bit 
test opportunities.

When dealing with longer modes I have come across a problem I can not solve.

Expansion in RTL for a bit test can produce two styles.

STYLE 1  Bit to be tested is NOT LSB (e.g. if ( longthing & 0x10)),  the 
expanded code contains the test as:

(and:SI (reg:SI 45 [ lx.1 ])
    (const_int 16 [0x10]))

Bit tests are matched by combine. Combine has no problems with this and 
eventually creates a matching pattern based on the conversion of the AND 
to a zero extraction

(set (pc)
    (if_then_else (ne (zero_extract:SI (subreg:QI (reg:SI 45 [ lx.1 ]) 0)
                (const_int 1 [0x1])
                (const_int 4 [0x4]))
            (const_int 0 [0x0]))
        (label_ref:HI 133)
        (pc)))

This will match Bit test patterns and produces optimal code. :-)

STYLE 2 Bit to be tested is LSB (e.g. if ( longthing & 1)), the expanded 
RTL code uses SUBREG to lower width (apparently from SImode to word size).

 (and:HI (subreg:HI (reg:SI 45 [ lx.1 ]) 0)
    (const_int 1 [0x1]))

This seems to occur regardless of -f(no)split-wide-types for size > 
HImode (which is integer mode). This RTL becomes a problem for combine

Combine  uses  subst(), combine_simplify_rtx() and eventually  
simplify_comparison()  where it attempts to WIDEN the AND and take the 
lowpart.

ge_low_part(HImode,
(and:SI (reg:SI 45 [ lx.1 ])
    (const_int 1 [0x1]))
)
However, gen_lowpart_for_combine() FAILS  as it will reject taking 
lowpart of SImode expression  because  size>UNITS_PER_WORD.
So no test pattern can be  matched. :-(

Style 2 is hugely problematic. The substitution works fine, but the 
simplification will always fail - making it apparently  impossible to 
create matching patterns for bit tests of  the LSB of SImode or DImode 
values.

Any clues how I might get around this?

Andy

Re: Cannot get Bit test RTL to cooperate with Combine.

[Joern Rennecke]

On Sun, Sep 20, 2009 at 01:49:39PM -0400, Andrew Hutchinson wrote:
> All,
>
> I have been debugging AVR port to see why we fail to match so many bit
> test opportunities.
>
> When dealing with longer modes I have come across a problem I can not solve.
>
> Expansion in RTL for a bit test can produce two styles.
>
> STYLE 1  Bit to be tested is NOT LSB (e.g. if ( longthing & 0x10)),  the
> expanded code contains the test as:
>
> (and:SI (reg:SI 45 [ lx.1 ])
>    (const_int 16 [0x10]))
>
> Bit tests are matched by combine. Combine has no problems with this and
> eventually creates a matching pattern based on the conversion of the AND
> to a zero extraction
>
> (set (pc)
>    (if_then_else (ne (zero_extract:SI (subreg:QI (reg:SI 45 [ lx.1 ]) 0)
>                (const_int 1 [0x1])
>                (const_int 4 [0x4]))
>            (const_int 0 [0x0]))
>        (label_ref:HI 133)
>        (pc)))
>
> This will match Bit test patterns and produces optimal code. :-)

Unfortunately, when combine knows about upper bits that are zero, it
will generate an lshiftrt instead, which can't be legitimately matched
by a bit test.

I have a patch for this which I haven't gotten around yet to test it
separately in trunk and formally submit to the patches list, but you can
extract it from arc-20081210-branch:

2008-12-02  J"orn Rennecke  <joern.rennecke@arc.com>

         * combine.c (undo_since): New function, broken out of:
         (undo_all).
         (combine_simplify_bittest): New function.
         (combine_simplify_rtx, simplify_if_then_else): Use it.
         * config/arc/arc.c (arc_rtx_costs): Check for bbit test.

svn diff -r144651:144652  
svn://gcc.gnu.org/svn/gcc/branches/arc-20081210-branch/gcc/combine.c

Re: Cannot get Bit test RTL to cooperate with Combine.

[Andrew Hutchinson]

Thank you so much for your information!

I will investigate your patch.
(I just hacked lowpart_for_combine to allow lowering something larger 
than word and the subreg matched no problem.)

It looks like RTL generation is somewhat odd and not helping.
My test used
extern long x;
if (x & 1)....

If there is only a single reference to x then (x &1), is lowered to HI 
mode and does not included any subregs (nosplit-wide-types). So my 
patterns match.

If my test code included two bit tests -  I get HI mode subregs on the x 
&1  (which will not match) but not on x & 2  the latter is  in the wider 
SI mode and will match.
If I turn on split-wide-types, the  subregs are not removed by subreg 
lowering since there is now mixed mode usage!

Something seem backwards in expansion, regarding lowering and references.

Andy


Joern Rennecke wrote:
> On Sun, Sep 20, 2009 at 01:49:39PM -0400, Andrew Hutchinson wrote:
>> All,
>>
>> I have been debugging AVR port to see why we fail to match so many bit
>> test opportunities.
>>
>> When dealing with longer modes I have come across a problem I can not 
>> solve.
>>
>> Expansion in RTL for a bit test can produce two styles.
>>
>> STYLE 1  Bit to be tested is NOT LSB (e.g. if ( longthing & 0x10)),  the
>> expanded code contains the test as:
>>
>> (and:SI (reg:SI 45 [ lx.1 ])
>>    (const_int 16 [0x10]))
>>
>> Bit tests are matched by combine. Combine has no problems with this and
>> eventually creates a matching pattern based on the conversion of the AND
>> to a zero extraction
>>
>> (set (pc)
>>    (if_then_else (ne (zero_extract:SI (subreg:QI (reg:SI 45 [ lx.1 ]) 0)
>>                (const_int 1 [0x1])
>>                (const_int 4 [0x4]))
>>            (const_int 0 [0x0]))
>>        (label_ref:HI 133)
>>        (pc)))
>>
>> This will match Bit test patterns and produces optimal code. :-)
>
> Unfortunately, when combine knows about upper bits that are zero, it
> will generate an lshiftrt instead, which can't be legitimately matched
> by a bit test.
>
> I have a patch for this which I haven't gotten around yet to test it
> separately in trunk and formally submit to the patches list, but you can
> extract it from arc-20081210-branch:
>
> 2008-12-02  J"orn Rennecke  <joern.rennecke@arc.com>
>
>         * combine.c (undo_since): New function, broken out of:
>         (undo_all).
>         (combine_simplify_bittest): New function.
>         (combine_simplify_rtx, simplify_if_then_else): Use it.
>         * config/arc/arc.c (arc_rtx_costs): Check for bbit test.
>
> svn diff -r144651:144652 
> svn://gcc.gnu.org/svn/gcc/branches/arc-20081210-branch/gcc/combine.c
>

Re: Cannot get Bit test RTL to cooperate with Combine.

[Andrew Hutchinson]

Why doesn't combine try matching "unsimplified" expressions when it fails?

This would at least permit creating patterns based on explicit format 
of  input RTL without the added vagaries of simplification

Andy



Joern Rennecke wrote:
> On Sun, Sep 20, 2009 at 01:49:39PM -0400, Andrew Hutchinson wrote:
>> All,
>>
>> I have been debugging AVR port to see why we fail to match so many bit
>> test opportunities.
>>
>> When dealing with longer modes I have come across a problem I can not 
>> solve.
>>
>> Expansion in RTL for a bit test can produce two styles.
>>
>> STYLE 1  Bit to be tested is NOT LSB (e.g. if ( longthing & 0x10)),  the
>> expanded code contains the test as:
>>
>> (and:SI (reg:SI 45 [ lx.1 ])
>>    (const_int 16 [0x10]))
>>
>> Bit tests are matched by combine. Combine has no problems with this and
>> eventually creates a matching pattern based on the conversion of the AND
>> to a zero extraction
>>
>> (set (pc)
>>    (if_then_else (ne (zero_extract:SI (subreg:QI (reg:SI 45 [ lx.1 ]) 0)
>>                (const_int 1 [0x1])
>>                (const_int 4 [0x4]))
>>            (const_int 0 [0x0]))
>>        (label_ref:HI 133)
>>        (pc)))
>>
>> This will match Bit test patterns and produces optimal code. :-)
>
> Unfortunately, when combine knows about upper bits that are zero, it
> will generate an lshiftrt instead, which can't be legitimately matched
> by a bit test.
>
> I have a patch for this which I haven't gotten around yet to test it
> separately in trunk and formally submit to the patches list, but you can
> extract it from arc-20081210-branch:
>
> 2008-12-02  J"orn Rennecke  <joern.rennecke@arc.com>
>
>         * combine.c (undo_since): New function, broken out of:
>         (undo_all).
>         (combine_simplify_bittest): New function.
>         (combine_simplify_rtx, simplify_if_then_else): Use it.
>         * config/arc/arc.c (arc_rtx_costs): Check for bbit test.
>
> svn diff -r144651:144652 
> svn://gcc.gnu.org/svn/gcc/branches/arc-20081210-branch/gcc/combine.c
>

Re: Cannot get Bit test RTL to cooperate with Combine.

[Joern Rennecke]

Quoting Andrew Hutchinson <andrewhutchinson@cox.net>:

> Why doesn't combine try matching "unsimplified" expressions when it fails?
>
> This would at least permit creating patterns based on explicit format
> of  input RTL without the added vagaries of simplification

Actually, that was my first attempt to approach the issue, but the
trouble with this is that it is ill-defined what the simplifications
are you want to loose versus what necessary canonicalisations are.

Ultimatively, the search space is infinite, and the patterns that combine
creates are shaped by the preconceptions of the programmers who hack it
on what patterns are good to match.  So it makes sense to try multiple
patterns for a single combination and test the cost, but we couldn't
afford an exhaustive search of all combinatorial possibilities.