Page MenuHomePhabricator

[EarlyCSE] Equivalent SELECTs should hash equally
ClosedPublic

Authored by bryanpkc on Aug 29 2020, 3:39 PM.

Details

Summary

DenseMap<SimpleValue> assumes that, if its isEqual method returns true
for two elements, then its getHashValue method must return the same value
for them. This invariant is broken when one SELECT node is a min/max
operation, and the other can be transformed into an equivalent min/max by
inverting its predicate and swapping its operands. This patch adds logic
to getHashValueImpl to ensure that the same value is returned for both
elements in this case, and fixes an assertion failure that would occur
intermittently while compiling the following IR:

define i32 @t(i32 %i) {
  %cmp = icmp sle i32 0, %i
  %twin1 = select i1 %cmp, i32 %i, i32 0
  %cmpinv = icmp sgt i32 0, %i
  %twin2 = select i1 %cmpinv,  i32 0, i32 %i
  %sink = add i32 %twin1, %twin2
  ret i32 %sink
}

Diff Detail

Unit TestsFailed

TimeTest
330 mslinux > LLVM.CodeGen/AMDGPU::sad.ll
Script: -- : 'RUN: at line 1'; /mnt/disks/ssd0/agent/llvm-project/build/bin/llc -mtriple=amdgcn-amd-amdhsa -mcpu=kaveri -verify-machineinstrs < /mnt/disks/ssd0/agent/llvm-project/llvm/test/CodeGen/AMDGPU/sad.ll | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck -check-prefix=GCN /mnt/disks/ssd0/agent/llvm-project/llvm/test/CodeGen/AMDGPU/sad.ll
400 mswindows > LLVM.CodeGen/AMDGPU::sad.ll
Script: -- : 'RUN: at line 1'; c:\ws\w16n2-1\llvm-project\premerge-checks\build\bin\llc.exe -mtriple=amdgcn-amd-amdhsa -mcpu=kaveri -verify-machineinstrs < C:\ws\w16n2-1\llvm-project\premerge-checks\llvm\test\CodeGen\AMDGPU\sad.ll | c:\ws\w16n2-1\llvm-project\premerge-checks\build\bin\filecheck.exe -check-prefix=GCN C:\ws\w16n2-1\llvm-project\premerge-checks\llvm\test\CodeGen\AMDGPU\sad.ll

Event Timeline

bryanpkc created this revision.Aug 29 2020, 3:39 PM
bryanpkc requested review of this revision.Aug 29 2020, 3:39 PM
bryanpkc updated this revision to Diff 288823.Aug 29 2020, 7:11 PM

Moved the fix into matchSelectWithOptionalNotCond instead of duplicating code.

bryanpkc updated this revision to Diff 288824.Aug 29 2020, 7:13 PM

Cleaned up unused code.

lebedev.ri added a subscriber: lebedev.ri.

Two comments:

  1. As a preparatory patch, we should adjust every test that uses EarlyCSE to also specify -earlycse-debug-hash, at least to those where it doesn't result in an assertion
  2. This should be adding a test, either to a existing file, or to the new one, with -earlycse-debug-hash.
bryanpkc updated this revision to Diff 288861.Aug 30 2020, 11:00 AM

Added a regression test using the -earlycse-debug-hash option.

lebedev.ri added inline comments.Aug 30 2020, 11:04 AM
llvm/lib/Transforms/Scalar/EarlyCSE.cpp
87

Not for this patch, but i think we clearly should change the default.

  1. As a preparatory patch, we should adjust every test that uses EarlyCSE to also specify -earlycse-debug-hash, at least to those where it doesn't result in an assertion

Thanks for your suggestions, Roman. I have added the reproducer to the EarlyCSE tests, next to other similar test cases. Regarding your first suggestion, do you mean that we should enable -earlycse-debug-hash in all tests under llvm/test/Transforms/EarlyCSE/, or even all tests under llvm/test/ that may implicitly use EarlyCSE? That seems like overkill.

  1. As a preparatory patch, we should adjust every test that uses EarlyCSE to also specify -earlycse-debug-hash, at least to those where it doesn't result in an assertion

Thanks for your suggestions, Roman. I have added the reproducer to the EarlyCSE tests, next to other similar test cases. Regarding your first suggestion, do you mean that we should enable -earlycse-debug-hash in all tests under llvm/test/Transforms/EarlyCSE/, or even all tests under llvm/test/ that may implicitly use EarlyCSE?

At least for every test that explicitly uses -early-cse.

That seems like overkill.

OTOH these bugs aren't fun, and they should be trivially caught by existing tests, since the test coverage should be good anyways.

bryanpkc added inline comments.Aug 30 2020, 11:12 AM
llvm/lib/Transforms/Scalar/EarlyCSE.cpp
87

Oh, that makes sense.

  1. As a preparatory patch, we should adjust every test that uses EarlyCSE to also specify -earlycse-debug-hash, at least to those where it doesn't result in an assertion

Thanks for your suggestions, Roman. I have added the reproducer to the EarlyCSE tests, next to other similar test cases. Regarding your first suggestion, do you mean that we should enable -earlycse-debug-hash in all tests under llvm/test/Transforms/EarlyCSE/, or even all tests under llvm/test/ that may implicitly use EarlyCSE?

At least for every test that explicitly uses -early-cse.

That seems like overkill.

OTOH these bugs aren't fun, and they should be trivially caught by existing tests, since the test coverage should be good anyways.

OK, I will submit a second patch to do that, as well as the EXPENSIVE_CHECKS change.

bryanpkc updated this revision to Diff 288862.Aug 30 2020, 11:15 AM

Fixed linter warning.

Pinging reviewers.

spatel accepted this revision.Sep 8 2020, 10:36 AM

LGTM

This revision is now accepted and ready to land.Sep 8 2020, 10:36 AM

Thanks Sanjay.

This revision was landed with ongoing or failed builds.Sep 10 2020, 2:00 PM
This revision was automatically updated to reflect the committed changes.
hliao added a subscriber: hliao.Sep 10 2020, 8:31 PM

Basically, the logic is wrong as we only canonicalize the condition and operands in the select. But, we also need to inverse the flavor to match the original logic. The original change plus inversing flavor is committed in 41e68f7ee7b

Apologies for the bug and thanks @hliao for the quick fix.