Re: Exploiting dual mode operation

Re: Exploiting dual mode operation

[Leehod Baruch]

Hello,

Thank you for your message.

We see redundant sign extension removal as a partial 
redundancy problem. This will give us not only the redundant 
sign extensions, but also better placement for the 
remaining ones. As a result sign extension instructions 
may be moved and instructions that uses the highpart
may be replaced with others that doesn't use it.

This is not equivalent with live information for the highest 
part of the registers. 

Our approach will not require changes in the description file 
(which in our opinion is a major problem with your code) and will 
limit the changes to much fewer files.

Leehod and Mircea 






Joern Rennecke <joern.rennecke@superh.com>
21/04/2004 09:26 PM
 
        To:     Mircea Namolaru/Haifa/IBM@IBMIL
        cc:     gcc@gcc.gnu.org, Leehod Baruch/Haifa/IBM@IBMIL
        Subject:        Re: Exploiting dual mode operation


> We are working on an optimization for eliminating redundant sign 
extension
> instructions by making use of this duality. Currently this is done only 
in 
> very 
> simple cases.

I have already submitted a patch for this:
http://gcc.gnu.org/ml/gcc-patches/2004-01/msg03259.html

It is still waiting for review.

Re: Exploiting dual mode operation

[Joern Rennecke]

> We see redundant sign extension removal as a partial 
> redundancy problem. This will give us not only the redundant 
> sign extensions, but also better placement for the 
> remaining ones. As a result sign extension instructions 
> may be moved and instructions that uses the highpart
> may be replaced with others that doesn't use it.

Why would you be using the highpart if you don't need to in the
first place?

Or are you saying that the port will have to duplicate patterns
that manipulate the highpart, to have a variant that uses and sets
only a smaller SUBREG, so that you can avoid tracking the lifeness
of the highpart separately?  That would be much more intrusive than
adding an attribute.

> This is not equivalent with live information for the highest 
> part of the registers. 
> 
> Our approach will not require changes in the description file 
> (which in our opinion is a major problem with your code) and will 
> limit the changes to much fewer files.

Without a special attribute in the machine description, or new code
that analyzes the md rtl to automatically generate this information,
you will have only scant information to feed into PRE computations.

And when you fix this problem, you will find that you need low-level
rtl to feed this pass, and then you don't want to push up the register
pressure with PRE.

Re: Exploiting dual mode operation

[Mircea Namolaru]

Hello,

1. Trying to solve the sign extension removal problem using the live 
highpart 
information has some limitations. For instance in the following case 
(which
appears during computation of array addresses):

i = sign extension i1;
....
index = 64-bit shift of i  // the target and the source are 64 bits 

In some architectures we may get the same result without using an explicit 
sign
extension. As we understand it, your algorithm will found that the 
highpart  of 
"i" is live and the sign extension will not be discarded.

Another example is:
 
int i, s;
for (i = 0; i < N; i++)
{
   s1 = s + i;
   s = sign extend s1;
}
return s;
The sign extension is required for the return only, so the sign extension 
can be 
removed from the loop and placed before the return. The highpart of "s" is 
live,
but this information alone will not help to improve the code. 

2. To exploit the dual mode operation, for instructions that uses the 
result of 
explicit sign extensions we need to found if it is possible to get the 
same result 
via an instruction that doesn't require explicit sign extensions. 
Basically we 
need to found if: 

s1 = sign extend s
t1 = sign extend  t
result = inst s1, t1 

can be replaced by an instruction inst1:

result = inst1 s, t.

But this seems similar with what combine does, so the information 
from the description file should suffice.

3. One possible way for implementation is to use reaching definitions
to propagate the sign extensions forward right before the uses. This will 
create 
opportunities for combine and gcse to do the rest of the work afterward.

Another possible way is to extend gcse (but there are some issues that 
we still need to clarify).

Maybe there is a way to use your code (or part of it) ? 

Mircea and Leehod 

Re: Exploiting dual mode operation

[Joern Rennecke]

> 1. Trying to solve the sign extension removal problem using the live 
> highpart 
> information has some limitations. For instance in the following case 
> (which
> appears during computation of array addresses):
> 
> i = sign extension i1;
> ....
> index = 64-bit shift of i  // the target and the source are 64 bits 
> 
> In some architectures we may get the same result without using an explicit 
> sign
> extension. As we understand it, your algorithm will found that the 
> highpart  of 
> "i" is live and the sign extension will not be discarded.

It depends. If you have a static right shift such that the highpart of the
value being shifted does not actually influence the result, the highpart
attribute can be 'ignore', and the sign extension can be eliminated.

But sign extension / shift combination can actually be handled generally
and much simpler in the combiner.  You only have to make sure that your
machine description contains the matching patterns, and it will just work -
no patches to the machine independent code required.

> Another example is:
>  
> int i, s;
> for (i = 0; i < N; i++)
> {
>    s1 = s + i;
>    s = sign extend s1;
> }
> return s;
> The sign extension is required for the return only, so the sign extension 
> can be 
> removed from the loop and placed before the return. The highpart of "s" is 
> live,
> but this information alone will not help to improve the code. 

Yes, this is not covered by the highpart liveness optimization.
The SHmedia intruction set has (among others) an addition instruction
that does a 32->64 bit sign extension of the result, so again this
can be handled by the combiner.
I have some across some code that uses short or unsigned short basic
induction variables, though.
I've written some patches for the loop optimizer to pre-condition the loop
so that it stops at the end or at the signed overflow, whichever is earlier,
and then use an outer loop to handle the sign extend.
If vector addition is available, that is also used to do a zero-extending
increment of a value that has been pre-conditioned to be zero-extended.

> 2. To exploit the dual mode operation, for instructions that uses the 
> result of 
> explicit sign extensions we need to found if it is possible to get the 
> same result 
> via an instruction that doesn't require explicit sign extensions. 
> Basically we 
> need to found if: 
> 
> s1 = sign extend s
> t1 = sign extend  t
> result = inst s1, t1 
> 
> can be replaced by an instruction inst1:
> 
> result = inst1 s, t.
> 
> But this seems similar with what combine does, so the information 
> from the description file should suffice.

Yes.  Just write a testcase, start gdb on cc1, set a breakpoint at
combine_instructions, start cc1 on your testcase, look for the patterns
you want combined, then set a breakpoint at try_combine with a condition
that the uids of i2 and i3 are your two patterns.
Then step through it to see if there is any snag that prevents the pattern
from being combined, or if not, look what pattern it generates.
Than add a matching pattern to your machine description.

> 3. One possible way for implementation is to use reaching definitions
> to propagate the sign extensions forward right before the uses. This will 
> create 
> opportunities for combine and gcse to do the rest of the work afterward.

Do you mean putting the sign extended values into new pseudo registers?
That seems to have about as much potential for harm as good, since it
can leave you with extra register-register copies, and you might
loose strength reduction unless you change the loop optimizer to grok
these new copies too.

> Another possible way is to extend gcse (but there are some issues that 
> we still need to clarify).

gcse works by computing the values in separate pseudos, thus creating new
register-register copies as discussed above.
> 
> Maybe there is a way to use your code (or part of it) ? 

Would you like a unidiff of all our patches against
gcc 3.4.0 20040414 (prerelease) ?
It's 736615 bytes raw, or 216022 bytes gzipped & uuencoded.

Re: Exploiting dual mode operation

[Mircea Namolaru]

> Would you like a unidiff of all our patches against
> gcc 3.4.0 20040414 (prerelease) ?
> It's 736615 bytes raw, or 216022 bytes gzipped & uuencoded.

We are looking at the patches submitted by you to FSF.

Mircea and Leehod

Exploiting dual mode operation

[Mircea Namolaru]

Hello,

Following our message ( http://gcc.gnu.org/ml/gcc/2004-04/msg00970.html )
regarding expoiting dual mode operations, we enclose an overview of our 
algorithm.

In order to support 32 bit computations on a 64 bit machine, sign 
extension
instructions are generated to ensure the correctness of the computation.
A possible policy (currently implemented in gcc) is to generate a sign
extension after each 32 bit computation. Depending on the instruction set 
of
the architecture some of these sign extension instructions may be 
redundant.

There are two cases:

Case1: 
The instruction using the 64bit operands (after they are sign-extended)
has a dual mode that works with 32bit operands.

For example:

int32 a, b;

a = ....                               a = ....
a = sign extend a          <-->
b = ....                               b = ....
b = sign extend a          <-->

cmpd a, b                              cmpw a, b  //half word compare

Case2:
The instruction defining the 64bit operand (which is later sign-extended)
has a dual mode that defines and sign-extends a 32bit operand.

For example:

int32 a;

ld a                                   lwa a     // load half and sign 
extend
a = sign extend a          <-->

return a                               return a


We'll present the algorithm on the following example:

Example:

We have two definitions of int32, and multiple uses as below:
Source:

                         def1           def2
                          | \           / |
                          |  \         /  |
                          |   \       /   |
                          |    \     /    |
                          |     \   /     |
                          |      \ /      |
                        use1    use12    use2

Assume that only a single sign extend (se) instruction is needed on the 
path
between def1 and use12 - for all other paths, the se can be combined with
either the def or the use.

0. Initial code, as currently generated by gcc.
   (There are sign extension after each definition)

                         def1           def2
                          se             se
                          | \           / |
                          |  \         /  |
                          |   \       /   |
                          |    \     /    |
                          |     \   /     |
                          |      \ /      |
                        use1    use12    use2

1. Combine
1.a prepare for combine 
   (Redundant) sign extensions generated also before uses.

                         def1           def2
                          se             se
                          | \           / |
                          |  \         /  |
                          |   \       /   |
                          |    \     /    |
                          |     \   /     |
                          |      \ /      |
                         se      se       se
                        use1    use12    use2


1.b combine
   - Combine tries to merge se's with defs and with uses.
   Assume it succeeds for def2 and use1:

                         def1           def2
                          se            [se removed]
                          | \           / |
                          |  \         /  |
                          |   \       /   |
                          |    \     /    |
                          |     \   /     |
                          |      \ /      |
                   [se removed]  se       se
                        use1    use12    use2

2. PRE
2.a  prepare for PRE
  - if combine did not remove an se after a def (as in def1), we remove it 
now
  (recall that it is redundant) - PRE should compute an optimal placement 
of
  se's which may or may not include this after-the-def location.
  - if combine did remove an se after a def (as in def2), we want PRE to 
know
  that the new def contains an se, so that it will remove other redundant 
se's.
  So we regenerate the se explicitly, and remove it eventually.

  - Note that if combine removed an se before a use, this use no longer 
requires
  an se, so PRE needs not consider this use any longer (and hence we do 
not
  regenerate the se).

                         def1           def2
                     [se removed]        se [regenerated]
                          | \           / |
                          |  \         /  |
                          |   \       /   |
                          |    \     /    |
                          |     \   /     |
                          |      \ /      |
                                 se       se
                        use1    use12    use2

2.b PRE
   An optimal placement is:

                         def1           def2
                                         se [regenerated]
                          | \           / |
                          |  \         /  |
                          |   se      /   |
                          |    \     /    |
                          |     \   /     |
                          |      \ /      |
                        use1    use12    use2

4. Cleanup
   - The regenerated sign extension after def2 is removed.

                         def1           def2
                                     [se removed] 
                          | \           / |
                          |  \         /  |
                          |   se      /   |
                          |    \     /    |
                          |     \   /     |
                          |      \ /      |
                        use1    use12    use2

Finally we got the best placement for the sign extensions as required.

We will soon post part of code for review. 

Comments welcomed. Thanks,

Mircea and Leehod

Re: Exploiting dual mode operation

[Joern Rennecke]

> We are working on an optimization for eliminating redundant sign extension
> instructions by making use of this duality. Currently this is done only in 
> very 
> simple cases.

I have already submitted a patch for this:
http://gcc.gnu.org/ml/gcc-patches/2004-01/msg03259.html

It is still waiting for review.

Exploiting dual mode operation

[Mircea Namolaru]

Hello,

For a 64-bit architecture, values defined as 32-bit values in a program 
must
be sign extended (or zero extended, in the case of unsigned values) to 
make 
them 64-bit values.
Some 64-bit architectures support certain operations in both 64-bit and 
32-bit form.
We are working on an optimization for eliminating redundant sign extension
instructions by making use of this duality. Currently this is done only in 
very 
simple cases.

For example in the following code there are explicit sign extension
instructions that could be eliminated :

i2 = extsw i1      //  i1, j1 are 32-bit integers in 64-bits architecture.
j2 = extsw j1
.......
cmpd i2, j2        // This compare is for double word (64-bits).

But, if a half-word compare instruction is available, we could use it and
remove the sign extensions:

cmpw i1, j1        // This compare is for single word (32-bits).

The sign extension instructions are generated after each definition of a
32-bit integer. By examining all the uses of a sign extension instruction
we can decide whether it is redundent or not.

Comments welcome. Thanks,

Leehod and Mircea