This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Conditionally emitting nsw/nuw flags when combining two add operations
ClosedPublic

Authored by MehrHeidar on Apr 8 2021, 3:13 AM.

Details

Summary

Currently, the InstCombineCompare is combining two add operations into a single add operation which always has a nsw flag, without checking the conditions to see if this flag should be present according to the original two add operations or not. This flag can cause future passes in the pipeline to apply incorrect optimization and generate an incorrect IR.
The following figure shows the IR before, on the right, and after, on the left, this wrong optimization and is the main motivation for this patch:


As we can see non of the add operations have the nsw falg and it was added incorrectly by InstCombine pass. A correct IR for this combined add should be %2 = add i8 %m, 2.

With the wrong IR presented in previous figure, later on the pipeline because of the misleading nsw the conditional branch instruction has changed to an unconditional branch and causing the InstCombine to delete the instructions inside a BasicBlock that contains load and store instructions. This can be seen in the following figure:

This patch will change the InstCombineCompare to emit the nsw or nuw only when these flags are allowed to be generated according to the original add operations and delete the possibility of applying wrong optimization with passes that will perform on the IR later in the pipeline.

To confirm that the current results are buggy and the results after proposed patch are the correct IR the following examples from Alive2 are attached; the same results can be seen in the case of nuw flag and nsw is just used as an example. The following link shows that the generated IR with current LLVM is a buggy IR when non of the original add operations have nsw flag.
https://alive2.llvm.org/ce/z/WGaDrm
The following link proves that the generated IR after the patch in the former case is the correct IR.
https://alive2.llvm.org/ce/z/wQ7G_e

Diff Detail

Event Timeline

MehrHeidar created this revision.Apr 8 2021, 3:13 AM
MehrHeidar requested review of this revision.Apr 8 2021, 3:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 8 2021, 3:13 AM
MehrHeidar added a reviewer: craig.topper.
nikic added a subscriber: nikic.
nikic added inline comments.
llvm/test/Transforms/InstCombine/icmp-emit-nsw-nuw.ll
1 ↗(On Diff #336042)

Please use llvm/utils/update_test_checks.py.

spatel added a comment.Apr 8 2021, 5:44 AM

These transforms appear to be untested, so I pushed the tests here:
6fccfd7cbdca

So now you can rebase, run llvm/utils/update_test_checks.py on that file, and we'll see the diffs.
It would also be good to use Alive2 to confirm that the current results are buggy and the updated results are as expected. For example:
https://alive2.llvm.org/ce/z/c3BeYv

MehrHeidar edited the summary of this revision. (Show Details)Apr 9 2021, 7:28 AM
MehrHeidar edited the summary of this revision. (Show Details)Apr 9 2021, 1:04 PM
MehrHeidar edited the summary of this revision. (Show Details)
nikic requested changes to this revision.Apr 11 2021, 8:31 AM
nikic added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3911

I don't think the nuw preservation is correct if the numbers are negative. Consider this case: https://alive2.llvm.org/ce/z/r3s3bw

This revision now requires changes to proceed.Apr 11 2021, 8:31 AM
MehrHeidar added inline comments.Apr 12 2021, 7:25 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3911

I guess that if I change the condition for emitting nuw as follows:

C3.isPositive() && BO1->hasNoUnsignedWrap()

the preservation for nuw will be correct. Will it satisfy all the cases?

MehrHeidar added inline comments.Apr 12 2021, 7:27 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3911

I guess that if I change the condition for emitting nuw as follows:

C3.isNegative() && BO1->hasNoUnsignedWrap()

the preservation for nuw will be correct. Will it satisfy all the cases?

MehrHeidar marked an inline comment as not done.Apr 12 2021, 7:30 AM
MehrHeidar planned changes to this revision.Apr 12 2021, 7:32 AM
MehrHeidar added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3911

I guess that if I change the condition for emitting nuw as follows:

!C3.isNegative() && BO1->hasNoUnsignedWrap()

the preservation for nuw will be correct. Will it satisfy all the cases?

MehrHeidar marked an inline comment as not done.Apr 12 2021, 7:33 AM
MehrHeidar marked an inline comment as done.Apr 12 2021, 8:01 AM
MehrHeidar updated this revision to Diff 336969.EditedApr 12 2021, 2:46 PM

I have updated the condition for preserving the nuw flag.
@nikic Do you think it looks good now?

Yeah, the implementation looks good to me now. Could you please also add a test for this case (that shows nuw is not preserved for negative numbers)?

If you don't have commit access, please also share your Name <and@email> to use when landing this change.

MehrHeidar updated this revision to Diff 337397.EditedApr 14 2021, 4:10 AM

The test case for negative values with nuw flag is added.

Mehrnoosh Heidarpour
email: mehrnoosh.heidarpour@huawei.com

nikic added inline comments.Apr 14 2021, 5:55 AM
llvm/test/Transforms/InstCombine/icmp-add.ll
747

These should be %t2, %t1 (this causes the build failure).

nikic accepted this revision.Apr 14 2021, 11:47 AM

LGTM

This revision is now accepted and ready to land.Apr 14 2021, 11:47 AM
This revision was landed with ongoing or failed builds.Apr 14 2021, 11:53 AM
This revision was automatically updated to reflect the committed changes.