You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by "Naveen Neelakantam (JIRA)" <ji...@apache.org> on 2008/11/04 16:08:46 UTC
[jira] Created: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass
fixes
[drlvm][jit][abcd] classic abcd pass fixes
------------------------------------------
Key: HARMONY-6007
URL: https://issues.apache.org/jira/browse/HARMONY-6007
Project: Harmony
Issue Type: Bug
Environment: RHEL4, 32-bit x86, gcc 4.1.2
Reporter: Naveen Neelakantam
The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
>java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-6007) [drlvm][jit][abcd] classic abcd
pass fixes
Posted by "Naveen Neelakantam (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12644986#action_12644986 ]
Naveen Neelakantam commented on HARMONY-6007:
---------------------------------------------
Can someone who understands the ABCD pass check my patch?
Egor if you still follow the list, could you please take a look?
Thanks,
Naveen
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Attachments: classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass
fixes
Posted by "Naveen Neelakantam (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Naveen Neelakantam updated HARMONY-6007:
----------------------------------------
Attachment: classic_abcd.patch.txt
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Attachments: classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass
fixes
Posted by "Egor Pasko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Egor Pasko updated HARMONY-6007:
--------------------------------
Attachment: 0001-more-constrained-operands-and-new-pi-operand-renamin.patch
new patch: 0001-more-constrained-operands-and-new-pi-operand-renamin.patch, find comments in the dev@ list shortly.
against r751765.
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Assignee: Egor Pasko
> Attachments: 0001-more-constrained-operands-and-new-pi-operand-renamin.patch, classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-6007) [drlvm][jit][abcd] classic abcd
pass fixes
Posted by "Egor Pasko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12700007#action_12700007 ]
Egor Pasko commented on HARMONY-6007:
-------------------------------------
thanks, Naveen! if you need some details about parts of the patch, I'll be glad to comment
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Assignee: Egor Pasko
> Attachments: 0001-more-constrained-operands-and-new-pi-operand-renamin.patch, classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass
fixes
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tim Ellison updated HARMONY-6007:
---------------------------------
Fix Version/s: 5.0M10
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Assignee: Egor Pasko
> Fix For: 5.0M10
>
> Attachments: 0001-more-constrained-operands-and-new-pi-operand-renamin.patch, classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (HARMONY-6007) [drlvm][jit][abcd] classic abcd
pass fixes
Posted by "Egor Pasko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Egor Pasko reassigned HARMONY-6007:
-----------------------------------
Assignee: Egor Pasko
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Assignee: Egor Pasko
> Attachments: classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-6007) [drlvm][jit][abcd] classic abcd
pass fixes
Posted by "Naveen Neelakantam (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12698316#action_12698316 ]
Naveen Neelakantam commented on HARMONY-6007:
---------------------------------------------
Sorry I haven't been able to take a look at your patch in detail yet. It is a non-trivial patch, and I want to spend some time to understand it. However, I haven't been able to make the time to do so yet...
Glad you've committed it in the meantime.
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Assignee: Egor Pasko
> Attachments: 0001-more-constrained-operands-and-new-pi-operand-renamin.patch, classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass
fixes
Posted by "Naveen Neelakantam (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Naveen Neelakantam updated HARMONY-6007:
----------------------------------------
Comment: was deleted
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Attachments: classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-6007) [drlvm][jit][abcd] classic abcd pass
fixes
Posted by "Naveen Neelakantam (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Naveen Neelakantam updated HARMONY-6007:
----------------------------------------
Component/s: DRLVM
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Attachments: classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Resolved: (HARMONY-6007) [drlvm][jit][abcd] classic abcd
pass fixes
Posted by "Egor Pasko (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-6007?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Egor Pasko resolved HARMONY-6007.
---------------------------------
Resolution: Fixed
should be fixed now, would appreciate any verification :)
> [drlvm][jit][abcd] classic abcd pass fixes
> ------------------------------------------
>
> Key: HARMONY-6007
> URL: https://issues.apache.org/jira/browse/HARMONY-6007
> Project: Harmony
> Issue Type: Bug
> Components: DRLVM
> Environment: RHEL4, 32-bit x86, gcc 4.1.2
> Reporter: Naveen Neelakantam
> Assignee: Egor Pasko
> Attachments: 0001-more-constrained-operands-and-new-pi-operand-renamin.patch, classic_abcd.patch.txt
>
> Original Estimate: 1h
> Remaining Estimate: 1h
>
> The ABCD pass has effectively been crippled by changes that have been made to DRLVM over the past year (I haven't been able to narrow down when the change happened).
> The good news is that with two simple fixes, ABCD works again. The attached patch adds the necessary fixes.
> To see the problem however you can try running the bi-directional bubble sort from HARMONY-1564. It is well-known that ABCD should be able to eliminate all the bounds checks from the sort algorithm. However, if you run drlvm without this patch, none of the bounds checks are eliminated. You can examine the logs by doing the following:
> >java -XX:jit.p.filter=BidirectionalBubbleSort.sort -XX:jit.p.arg.log=ct,irdump -Xem:server_static BidirectionalBubbleSort
> After applying the patch, all the bounds checks will once again be eliminated. There were two separate problems to blame, which this patch addresses:
> 1) Harmony now inserts multiple "arraylen" operations when translating from bytecode, even if the operation is redundant (because it post-dominates an earlier "arraylen" operation for the same array). This redundancy must be eliminated before running ABCD otherwise the inequality graph that ABCD generates for its proofs will have unnecessary discontinuity. Thankfully, solving the problem is as simple as running the following passes before ABCD: "hvn,simplify,dce,uce,memopt,dce,uce".
> 2) Our implementation of ABCD includes a novel design by Egor Pasko where both the upper-bound and lower-bound problems can be solved using the same inequality graph. In addition the implementation adds more constraints to the graph than the original ABCD authors specified. Both improvements are correct, except that they can prevent the ABCD solver from finding valid solutions because pi-renamed variables appear to be different. The patch modifies the solver so that it treats pi-renamed variables as equivalent when checking for termination conditions.
> I've verified that HARMONY-2141, HARMONY-2144, and HARMONY-2147 still pass with these changes.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.