You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by "Xiaoming Gu (JIRA)" <ji...@apache.org> on 2008/07/08 08:50:36 UTC
[jira] Created: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
------------------------------------------------------------------------------------------------------
Key: HARMONY-5901
URL: https://issues.apache.org/jira/browse/HARMONY-5901
Project: Harmony
Issue Type: Improvement
Components: DRLVM
Reporter: Xiaoming Gu
1. Mulitiplication replacement
a. It's about integer multiplication.
b. One of two multipliers is a power of 2.
c. The power of 2 could be negative.
For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
2. Division replacement
a. It's about integer division.
b. The divisor is a power of 2.
c. The power of 2 could be negative.
d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
Baseline: q = a / (1 << d);
Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
3. Comments for SAR and SHR swapped
The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
Re: [jira] Commented: (HARMONY-5901) replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
Posted by Xiao-Feng Li <xi...@gmail.com>.
On Thu, Aug 21, 2008 at 12:30 PM, Xiaoming Gu (JIRA) <ji...@apache.org> wrote:
>
> [ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12624249#action_12624249 ]
>
> Xiaoming Gu commented on HARMONY-5901:
> --------------------------------------
>
> Hi, guys. I'm working on the strength reduction for MUL & DIV these days.
>
> I found the optimization is available in simplify.cpp and multiplybyconstant.cpp but it is not turned on. Then I turned on it by simply changing "simplify" to "latesimplify" in .emconf files. To turn on DIV reduction, it needs to delete #ifdef __IPF__ around the related code. I did some tests with the benchmarks by Stefan Krause (http://www.stefankrause.net/wp/?m=200807) yesterday and following are the details.
>
> ++++++++++++Using latest version of Harmony, -Xem:opt++++++++++
> mandelbrot_long 2547(msec)
> fannkuch_long 5437
> himeno_bench2 26518
> nbody_long 8468
> spectralnorm_long 14967
>
> As mentioned before there is an opportunity for DIV reduction in spectralnorm_long.
> ++++++++++++Manually transformed spectralnorm_long using latest version of Harmony, -Xem:opt++++++++++
> spectralnorm_long 8905(msec)
>
> Then I turned on the available MUL and DIV reduction
> ++++++++++++Using latest version of Harmony, -Xem:opt but MUL & DIV reduction turned on++++++++++
> mandelbrot_long 2547(msec)
> fannkuch_long 5453
> himeno_bench2 26987
> nbody_long 19342
> spectralnorm_long 8765
>
> The inputs for these tests are
> +++++++++++++Input++++++++++++++
> mandelbrot_long 4000
> fannkuch_long 11
> himeno_bench2 M (more options "-Xmx1024m -Xms1024m" needed)
> nbody_long 19900001
> spectralnorm_long 5501
>
> From the above results, spectralnorm_long is improved a lot by the available reduction even better than the manual transformation. But fannkuch_long and himeno_bench2 are degraded a little and nbody_long is degraded a lot. After breifly reading the reduction code, I find the cost model for reduction is missing and the reduction is always done if it's turned on. Maybe that's why the available reduction is turned off in all emconf files. Does anyone know about this available reduction? Why it is turned off by default? Thanks.
Thanks for the experiments and the discovery. I think you can decide
if we want to improve the cost model or have a butter solution.
Thanks.
-xiaofeng
>
>> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
>> ------------------------------------------------------------------------------------------------------
>>
>> Key: HARMONY-5901
>> URL: https://issues.apache.org/jira/browse/HARMONY-5901
>> Project: Harmony
>> Issue Type: Improvement
>> Components: DRLVM
>> Reporter: Xiaoming Gu
>> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch
>>
>>
>> 1. Mulitiplication replacement
>> a. It's about integer multiplication.
>> b. One of two multipliers is a power of 2.
>> c. The power of 2 could be negative.
>> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
>> 2. Division replacement
>> a. It's about integer division.
>> b. The divisor is a power of 2.
>> c. The power of 2 could be negative.
>> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
>> Baseline: q = a / (1 << d);
>> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
>> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
>> 3. Comments for SAR and SHR swapped
>> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
>
--
http://xiao-feng.blogspot.com
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Comment: was deleted
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12611582#action_12611582 ]
Aleksey Shipilev commented on HARMONY-5901:
-------------------------------------------
There's really the bug in the patch.
You should handle the divOp when remainder is requested, see corresponding boolean parameter in argument list.
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12611525#action_12611525 ]
Aleksey Shipilev commented on HARMONY-5901:
-------------------------------------------
Xiaoming, I have problems with your patch:
$ patch -p0 < ../patches/5901.patch
patching file working_vm/vm/port/src/encoder/ia32_em64t/enc_defs.h
patching file working_vm/vm/jitrino/src/codegenerator/ia32/Ia32InstCodeSelector.cpp
patch: **** unexpected end of file in patch
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Aleksey Shipilev updated HARMONY-5901:
--------------------------------------
Attachment: H5901-V2.patch
H5901-V2.patch
- Reformatted and reformulated patch.
- Fixes bug with the remainder calculation (falls back to IDIV generation)
Still generates faulty MulOps:
$ ../../builds/shade.1/bin/java -Xem:opt spectralnorm_long 100 100 100
Uncaught exception in main:
java.lang.ExceptionInInitializerError
Caused by: java.lang.ArrayIndexOutOfBoundsException
at com.ibm.icu.impl.ICUResourceBundle.getInt(ICUResourceBundle.java:1031)
at com.ibm.icu.impl.ICUResourceBundle.getStringValue(ICUResourceBundle.java:1047)
at com.ibm.icu.impl.ICUResourceBundleImpl$ResourceString.<init>(ICUResourceBundleImpl.java:122)
at com.ibm.icu.impl.ICUResourceBundle.createBundleObject(ICUResourceBundle.java)
at com.ibm.icu.impl.ICUResourceBundleImpl$ResourceArray.handleGet(ICUResourceBundleImpl.java:58)
at com.ibm.icu.util.UResourceBundle.get(UResourceBundle.java)
at com.ibm.icu.util.UResourceBundleIterator.next(UResourceBundleIterator.java)
at com.ibm.icu.impl.ICUResourceBundleImpl$ResourceArray.handleGetStringArray(ICUResourceBundleImpl.java)
at com.ibm.icu.util.UResourceBundle.resolveObject(UResourceBundle.java)
at com.ibm.icu.util.UResourceBundle.handleGetObjectImpl(UResourceBundle.java:1007)
at com.ibm.icu.util.UResourceBundle.handleGetObjectImpl(UResourceBundle.java:1011)
at com.ibm.icu.util.UResourceBundle.handleGetObject(UResourceBundle.java:994)
at java.util.ResourceBundle.getObject(ResourceBundle.java)
at java.util.ResourceBundle.getStringArray(ResourceBundle.java:235)
at com.ibm.icu.text.DecimalFormatSymbols.initialize(DecimalFormatSymbols.java)
at com.ibm.icu.text.DecimalFormatSymbols.<init>(DecimalFormatSymbols.java:59)
at java.text.DecimalFormat.<init>(DecimalFormat.java)
at spectralnorm_long.<clinit>(spectralnorm_long.java:16)
FAILED to invoke JVM.
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) [drlvm][jit]integer MUL, DIV and REM
strength reduction
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: H5901-V9.patch
This message is for V9 patch.
In this patch, some changes are added for the bugs in 64-bit systems.
> [drlvm][jit]integer MUL, DIV and REM strength reduction
> -------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch, H5901-V8.patch, H5901-V9.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) [drlvm][jit]integer MUL & DIV
strength reduction
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Summary: [drlvm][jit]integer MUL & DIV strength reduction (was: replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2)
> [drlvm][jit]integer MUL & DIV strength reduction
> ------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5901) [drlvm][jit]integer MUL, DIV and
REM strength reduction
Posted by "Chunrong Lai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12676700#action_12676700 ]
Chunrong Lai commented on HARMONY-5901:
---------------------------------------
Committed in r747857. Xiaoming, please help to verify it.
> [drlvm][jit]integer MUL, DIV and REM strength reduction
> -------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Assignee: Chunrong Lai
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch, H5901-V8.patch, H5901-V9.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: H5901-V3.patch
Most recent patch including replacment for mod op. In this version, I8 (long) case is ignored. And there is still a bug with using NumberFormat class.
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: (was: 5901.patch)
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) [drlvm][jit]integer MUL, DIV and REM
strength reduction
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: H5901-V8.patch
This message is for V8 patch.
1. Turn on MUL strength reduction even in a simplify pass.
It was only turned on in a latesimplify pass.
2. Only do MUL strength reduction for the following two cases.
a) constant multiplier d is positive and less than 32
b) d is a power of 2
3. Some reductions for the above a) case are changed to another way to get improvement.
The available MUL strength reduction in multiplybyconstant.cpp is too complex without any cost model. This version is conservative but guarantees reduction always brings improvement. I find a problem on register allocation in the testings (see https://issues.apache.org/jira/browse/HARMONY-5992), which makes hard to evaluate reductions. I'll fix that problem first then relax the conservative reduction policy later.
> [drlvm][jit]integer MUL, DIV and REM strength reduction
> -------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch, H5901-V8.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Closed: (HARMONY-5901) [drlvm][jit]integer MUL, DIV and REM
strength reduction
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tim Ellison closed HARMONY-5901.
--------------------------------
Resolution: Fixed
Fix Version/s: 5.0M9
Was verified by Xiaoming.
> [drlvm][jit]integer MUL, DIV and REM strength reduction
> -------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Assignee: Chunrong Lai
> Fix For: 5.0M9
>
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch, H5901-V8.patch, H5901-V9.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12619805#action_12619805 ]
Aleksey Shipilev commented on HARMONY-5901:
-------------------------------------------
That's good, Xiaoming!
A couple of little "polishing" comments:
a. eliminate "&& true" from if conditions, that was introduced by me for debugging purposes and I forgot to sweep them out
b. move out common blocks from switch cases
After that the patch can be committed, if it passes VM/Classlib tests.
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) [drlvm][jit]integer MUL, DIV and REM
strength reduction
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Summary: [drlvm][jit]integer MUL, DIV and REM strength reduction (was: [drlvm][jit]integer MUL & DIV strength reduction)
> [drlvm][jit]integer MUL, DIV and REM strength reduction
> -------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5901) [drlvm][jit]integer MUL, DIV and
REM strength reduction
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12676843#action_12676843 ]
Xiaoming Gu commented on HARMONY-5901:
--------------------------------------
Good job, Chunrong. Thanks.
> [drlvm][jit]integer MUL, DIV and REM strength reduction
> -------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Assignee: Chunrong Lai
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch, H5901-V8.patch, H5901-V9.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (HARMONY-5901) [drlvm][jit]integer MUL, DIV and
REM strength reduction
Posted by "Chunrong Lai (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Chunrong Lai reassigned HARMONY-5901:
-------------------------------------
Assignee: Chunrong Lai
> [drlvm][jit]integer MUL, DIV and REM strength reduction
> -------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Assignee: Chunrong Lai
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch, H5901-V8.patch, H5901-V9.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12611577#action_12611577 ]
Xiaoming Gu commented on HARMONY-5901:
--------------------------------------
With the patch, nbody_long and spectralnorm_long in the benchmarks by Stefan
Krause couldn't pass. I'm investigating the bug.
Xiaoming
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: H5901-V5.patch
cleaned patch
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: H5901-V6.patch
This message is for V6 patch. In this version, I turn on the available DIV generalized strength reduction for int32 and add DIV strength reduction for int64 when the constant divisor is a power of 2. The available MUL generalized strength reduction for int32 and int64 is NOT turned on because its benefit is unstable. Following are the details of MUL & DIV strength reduction in Harmony.
1. MUL
a. one of multipliers is constant and a power of 2
I. done in simplifier but not turned on
II. done in peephole and turned on
b. generalized strength reduction
done in simplifier but not turned on
(You may turn it on by changing "simplify" to "latesimplify" in the emconf files.)
2. DIV
a. the divisor is an int32 constant
done in simplifier and turned on including generalized strength reduction
b. the divisor is an int64 constant
done only when the divisor is a power of 2
(Generalized is not done because there is no support for 128-bit.)
I find in HIR2LIR, shladd HIR is NOT translated to LEA LIR. If we use LEA, we may do more study on MUL generalized strength reduction. I'm working on this now.
With this patch, there is no significant change in the five benchmarks by Stefan Krause except that the speedup of spectralnorm_long is more than 1.7 (from 14970ms to 8766ms).
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: 5901.patch
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12611581#action_12611581 ]
Aleksey Shipilev commented on HARMONY-5901:
-------------------------------------------
Hold on, Xiaoming :)
There are compilation errors on Windows/MSVC, I would submit the corrected patch in half an hour.
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) [drlvm][jit]integer MUL, DIV and REM
strength reduction
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: H5901-V8.patch
This message is for V8 patch.
1. Turn on MUL strength reduction even in a simplify pass.
It was only turned on in a latesimplify pass.
2. Only do MUL strength reduction for the following two cases.
a) constant multiplier d is positive and less than 32
b) d is a power of 2
3. Some reductions for the above a) case are changed to another way to get improvement.
The available MUL strength reduction in multiplybyconstant.cpp is too complex without any cost model. This version is conservative but guarantees reduction always brings improvement. I find a problem on register allocation in the testings (see https://issues.apache.org/jira/browse/HARMONY-5992), which makes hard to evaluate reductions. I'll fix that problem first then relax the conservative policy later.
> [drlvm][jit]integer MUL, DIV and REM strength reduction
> -------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch, H5901-V8.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12624249#action_12624249 ]
Xiaoming Gu commented on HARMONY-5901:
--------------------------------------
Hi, guys. I'm working on the strength reduction for MUL & DIV these days.
I found the optimization is available in simplify.cpp and multiplybyconstant.cpp but it is not turned on. Then I turned on it by simply changing "simplify" to "latesimplify" in .emconf files. To turn on DIV reduction, it needs to delete #ifdef __IPF__ around the related code. I did some tests with the benchmarks by Stefan Krause (http://www.stefankrause.net/wp/?m=200807) yesterday and following are the details.
++++++++++++Using latest version of Harmony, -Xem:opt++++++++++
mandelbrot_long 2547(msec)
fannkuch_long 5437
himeno_bench2 26518
nbody_long 8468
spectralnorm_long 14967
As mentioned before there is an opportunity for DIV reduction in spectralnorm_long.
++++++++++++Manually transformed spectralnorm_long using latest version of Harmony, -Xem:opt++++++++++
spectralnorm_long 8905(msec)
Then I turned on the available MUL and DIV reduction
++++++++++++Using latest version of Harmony, -Xem:opt but MUL & DIV reduction turned on++++++++++
mandelbrot_long 2547(msec)
fannkuch_long 5453
himeno_bench2 26987
nbody_long 19342
spectralnorm_long 8765
The inputs for these tests are
+++++++++++++Input++++++++++++++
mandelbrot_long 4000
fannkuch_long 11
himeno_bench2 M (more options "-Xmx1024m -Xms1024m" needed)
nbody_long 19900001
spectralnorm_long 5501
>From the above results, spectralnorm_long is improved a lot by the available reduction even better than the manual transformation. But fannkuch_long and himeno_bench2 are degraded a little and nbody_long is degraded a lot. After breifly reading the reduction code, I find the cost model for reduction is missing and the reduction is always done if it's turned on. Maybe that's why the available reduction is turned off in all emconf files. Does anyone know about this available reduction? Why it is turned off by default? Thanks.
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: 5901.patch
cleaned patch
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) [drlvm][jit]integer MUL, DIV and REM
strength reduction
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: (was: H5901-V8.patch)
> [drlvm][jit]integer MUL, DIV and REM strength reduction
> -------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: H5901-V4.patch
The bug happened in spectralnorm_long is fixed. And a series of simple testcases about the replacement effect are passed. With the result tested on my workstation, spectralnorm_long is improved more than 29%, which is the benchmark dragging the total performance of Harmony most in http://www.stefankrause.net/wp/?p=9#more-9.
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: (was: 5901.patch)
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) [drlvm][jit]integer MUL & DIV
strength reduction
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: H5901-V7.patch
This message is for H5901-V7.patch.
In this patch, I fixed some bugs for REM (remainder) strength reduction and merged H5965 to H5901.
The first bug in REM reduction is that the code forgot to take absolute before calling whichPowerOf2. But even with this bug fixed, it's not correct. The formula behind the reduction when with negative divisor is src1%X=(src1&((1<<k)-1)) | (-1^((1<<k)-1)) assuming X=-2^k. We get -9%-8=-1 and 9%-8=-7. Tha latter is wrong. It's changed to use src1%X=src1-(src1/X)*X to get the correct result. Thanks for Ian Rogers pointing out the bugs.
I'm working on the left work for MUL strength reduction.
> [drlvm][jit]integer MUL & DIV strength reduction
> ------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch, H5901-V2.patch, H5901-V3.patch, H5901-V4.patch, H5901-V5.patch, H5901-V6.patch, H5901-V7.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Xiaoming Gu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Xiaoming Gu updated HARMONY-5901:
---------------------------------
Attachment: 5901.patch
This file comes from "svn diff" with no manual modification.
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5901) replace integer multiplication or
division with shift if one of multipliers or divisor is a power of 2
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5901?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12611479#action_12611479 ]
Aleksey Shipilev commented on HARMONY-5901:
-------------------------------------------
Good work, Xiaoming, but you need to clean up the patch a bit:
a. fold I4/I8 branches - set the optype in switch and proceed to common code block
b. replace <TAB>s with 4 spaces
> replace integer multiplication or division with shift if one of multipliers or divisor is a power of 2
> ------------------------------------------------------------------------------------------------------
>
> Key: HARMONY-5901
> URL: https://issues.apache.org/jira/browse/HARMONY-5901
> Project: Harmony
> Issue Type: Improvement
> Components: DRLVM
> Reporter: Xiaoming Gu
> Attachments: 5901.patch
>
>
> 1. Mulitiplication replacement
> a. It's about integer multiplication.
> b. One of two multipliers is a power of 2.
> c. The power of 2 could be negative.
> For example, 23*4 is transformed to 23<<2 and 23*(-4) is transformed to (23<<2)*(-1).
> 2. Division replacement
> a. It's about integer division.
> b. The divisor is a power of 2.
> c. The power of 2 could be negative.
> d. Because of round-up difference between division and shift right, the following equations from Aleksey are used.
> Baseline: q = a / (1 << d);
> Optimized: q = (a + [(1 << d) - 1] & (a >> 31)) >> d;
> For example, 23/4 is transformed to (23+((1<<2)-1)&(23>>31))>>2. and (-23)/(-4) is transformed to ((-23+((1<<2)-1)&(-23>>31))>>2)*(-1).
> 3. Comments for SAR and SHR swapped
> The comments for the two similar operations were misplaced in working_vm/vm/port/src/encoder/ia32_em64t.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.