You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@harmony.apache.org by xiaoming gu <xi...@gmail.com> on 2008/08/06 16:06:32 UTC
generalized multiplication replacement
Hi, all. Previously, Harmony Jira 5901 brought some benefits. Now I'm
working on generalized multiplication replacement with shift and addition.
Today I checked with gcc and found whether a multiplication is replaced or
not in gcc mainly (not strictly) depends on the number of the replaced
operations. There are some exceptions in gcc and I couldn't summarize the
rule without reading the source code. So I'm planning to round it to a
simple decision as following: if it needs >=4 shift/add operations, don't do
replacement; Otherwise, replace it with a combination of shift/add.
For example x*20 (20=00010100) is replaced by (x<<2+x)<<2 and x*56
(56=00111000) is replaced by (x<<3-x)<<3 but x*29 (29=00011101) is not
optimized by ((x<<3)-x)<<2+x.
Any comments?
Another question - may I read the source code of gcc since it is opensource
in GPL? Thanks.
Xiaoming
Re: generalized multiplication replacement
Posted by xiaoming gu <xi...@gmail.com>.
There is a section "Signed division quotient rounded towards 0" in the
PLDI94 paper for the division in
Java. I'm going to implement the algorithm in peephole pass. Thanks for your
kindful help, Ian.
Xiaoming
On Wed, Aug 6, 2008 at 10:40 PM, Ian Rogers <ro...@gmail.com> wrote:
> xiaoming gu wrote:
>
>> Hi, all. Previously, Harmony Jira 5901 brought some benefits. Now I'm
>> working on generalized multiplication replacement with shift and addition.
>>
>> Today I checked with gcc and found whether a multiplication is replaced or
>> not in gcc mainly (not strictly) depends on the number of the replaced
>> operations. There are some exceptions in gcc and I couldn't summarize the
>> rule without reading the source code. So I'm planning to round it to a
>> simple decision as following: if it needs >=4 shift/add operations, don't
>> do
>> replacement; Otherwise, replace it with a combination of shift/add.
>>
>> For example x*20 (20=00010100) is replaced by (x<<2+x)<<2 and x*56
>> (56=00111000) is replaced by (x<<3-x)<<3 but x*29 (29=00011101) is not
>> optimized by ((x<<3)-x)<<2+x.
>>
>> Any comments?
>>
>> Another question - may I read the source code of gcc since it is
>> opensource
>> in GPL? Thanks.
>>
>> Xiaoming
>>
>>
> Hi Xiaoming,
>
> IANAL but I guess it's not allowed to base your implementation on GCC. I
> wrote the same code for Jikes RVM [1] and I'd be happy for this CPL code
> also to be available under the ASF. This code doesn't handle the use of
> subtraction and partially computed results from earlier stages, I would very
> much like to improve it to do this. There is a tracker for Jikes RVM for
> this [2], there are also papers/programs explaining how to do the better
> approach [3][4] and some other considerations are mentioned in [5].
>
> Regards,
> Ian Rogers
>
> [1]
> http://jikesrvm.svn.sourceforge.net/viewvc/jikesrvm/rvmroot/trunk/rvm/src/org/jikesrvm/compilers/opt/Simplifier.java?revision=14704&view=markup#l_1385
> [2] http://jira.codehaus.org/browse/RVM-256
> [3] http://portal.acm.org/citation.cfm?id=178249
> [4]
> http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDFpages 160 and 186
> [5] http://www.intel.com/design/processor/manuals/248966.pdf
> --
> http://www.cs.man.ac.uk/~irogers <http://www.cs.man.ac.uk/%7Eirogers>
>
Re: generalized multiplication replacement
Posted by Xiao-Feng Li <xi...@gmail.com>.
Ian, thanks for the pointers, which are useful.
Thanks,
xiaofeng
On Wed, Aug 6, 2008 at 10:40 PM, Ian Rogers <ro...@gmail.com> wrote:
> xiaoming gu wrote:
>>
>> Hi, all. Previously, Harmony Jira 5901 brought some benefits. Now I'm
>> working on generalized multiplication replacement with shift and addition.
>>
>> Today I checked with gcc and found whether a multiplication is replaced or
>> not in gcc mainly (not strictly) depends on the number of the replaced
>> operations. There are some exceptions in gcc and I couldn't summarize the
>> rule without reading the source code. So I'm planning to round it to a
>> simple decision as following: if it needs >=4 shift/add operations, don't
>> do
>> replacement; Otherwise, replace it with a combination of shift/add.
>>
>> For example x*20 (20=00010100) is replaced by (x<<2+x)<<2 and x*56
>> (56=00111000) is replaced by (x<<3-x)<<3 but x*29 (29=00011101) is not
>> optimized by ((x<<3)-x)<<2+x.
>>
>> Any comments?
>>
>> Another question - may I read the source code of gcc since it is
>> opensource
>> in GPL? Thanks.
>>
>> Xiaoming
>>
>
> Hi Xiaoming,
>
> IANAL but I guess it's not allowed to base your implementation on GCC. I
> wrote the same code for Jikes RVM [1] and I'd be happy for this CPL code
> also to be available under the ASF. This code doesn't handle the use of
> subtraction and partially computed results from earlier stages, I would very
> much like to improve it to do this. There is a tracker for Jikes RVM for
> this [2], there are also papers/programs explaining how to do the better
> approach [3][4] and some other considerations are mentioned in [5].
>
> Regards,
> Ian Rogers
>
> [1]
> http://jikesrvm.svn.sourceforge.net/viewvc/jikesrvm/rvmroot/trunk/rvm/src/org/jikesrvm/compilers/opt/Simplifier.java?revision=14704&view=markup#l_1385
> [2] http://jira.codehaus.org/browse/RVM-256
> [3] http://portal.acm.org/citation.cfm?id=178249
> [4]
> http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF
> pages 160 and 186
> [5] http://www.intel.com/design/processor/manuals/248966.pdf
> --
> http://www.cs.man.ac.uk/~irogers
>
--
http://xiao-feng.blogspot.com
Re: generalized multiplication replacement
Posted by Ian Rogers <ro...@gmail.com>.
xiaoming gu wrote:
> Hi, all. Previously, Harmony Jira 5901 brought some benefits. Now I'm
> working on generalized multiplication replacement with shift and addition.
>
> Today I checked with gcc and found whether a multiplication is replaced or
> not in gcc mainly (not strictly) depends on the number of the replaced
> operations. There are some exceptions in gcc and I couldn't summarize the
> rule without reading the source code. So I'm planning to round it to a
> simple decision as following: if it needs >=4 shift/add operations, don't do
> replacement; Otherwise, replace it with a combination of shift/add.
>
> For example x*20 (20=00010100) is replaced by (x<<2+x)<<2 and x*56
> (56=00111000) is replaced by (x<<3-x)<<3 but x*29 (29=00011101) is not
> optimized by ((x<<3)-x)<<2+x.
>
> Any comments?
>
> Another question - may I read the source code of gcc since it is opensource
> in GPL? Thanks.
>
> Xiaoming
>
Hi Xiaoming,
IANAL but I guess it's not allowed to base your implementation on GCC. I
wrote the same code for Jikes RVM [1] and I'd be happy for this CPL code
also to be available under the ASF. This code doesn't handle the use of
subtraction and partially computed results from earlier stages, I would
very much like to improve it to do this. There is a tracker for Jikes
RVM for this [2], there are also papers/programs explaining how to do
the better approach [3][4] and some other considerations are mentioned
in [5].
Regards,
Ian Rogers
[1]
http://jikesrvm.svn.sourceforge.net/viewvc/jikesrvm/rvmroot/trunk/rvm/src/org/jikesrvm/compilers/opt/Simplifier.java?revision=14704&view=markup#l_1385
[2] http://jira.codehaus.org/browse/RVM-256
[3] http://portal.acm.org/citation.cfm?id=178249
[4]
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF
pages 160 and 186
[5] http://www.intel.com/design/processor/manuals/248966.pdf
--
http://www.cs.man.ac.uk/~irogers