Page MenuHomePhabricator

[TargetLowering] Combine known bits for icmp in SimplifySetCC (PR41182)
Needs ReviewPublic

Authored by darcangelo.matthew on Aug 25 2020, 3:51 PM.

Details

Summary

Early review for folding integer comparisons where the known bits of the operands allows the result to be determined - still have some regressions to address

  1. Changes in TargetLowering.SimplifySetCC handle each integer comparison, added X86 tests combine-known-bits*.ll
  2. Added two APIs to KnownBits to handle the signed min/max values
  3. Folded constant bool branches and updated CFG in DAGCombiner.visitBRCOND
  4. Added API to the SelectionDAG to retrieve the current MachineBasicBlock
  5. Updated test-shrink.ll as a sample for how to move forward on updating the additional tests

I am not sure how best to deal with (3) and (4), and if there is somewhere else that updating the CFG should take place, or if there is another way to get the current MBB. I do think this is the right place to collapse the branches, but please let me know if that's not the case.

For (5), this test is an example of failures that I've been hitting because the result of one of the instructions can be determined from the known bits. I plan to update these by making the result indeterminable for each case, but wanted to know if this is the right direction.

Diff Detail

Unit TestsFailed

TimeTest
460 mswindows > Clang.CodeGenCUDA::link-device-bitcode.cu
Script: -- : 'RUN: at line 7'; c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\clang.exe -cc1 -internal-isystem c:\ws\w16c2-1\llvm-project\premerge-checks\build\lib\clang\12.0.0\include -nostdsysteminc -triple nvptx-unknown-cuda -emit-llvm-bc -disable-llvm-passes -o C:\ws\w16c2-1\llvm-project\premerge-checks\build\tools\clang\test\CodeGenCUDA\Output\link-device-bitcode.cu.tmp.bc C:\ws\w16c2-1\llvm-project\premerge-checks\clang\test\CodeGenCUDA/Inputs/device-code.ll
160 mswindows > Clang.CodeGenCXX::ubsan-coroutines.cpp
Script: -- : 'RUN: at line 5'; c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\clang.exe -cc1 -internal-isystem c:\ws\w16c2-1\llvm-project\premerge-checks\build\lib\clang\12.0.0\include -nostdsysteminc -fno-experimental-new-pass-manager -emit-obj -std=c++2a -fsanitize=null C:\ws\w16c2-1\llvm-project\premerge-checks\clang\test\CodeGenCXX\ubsan-coroutines.cpp -o C:\ws\w16c2-1\llvm-project\premerge-checks\build\tools\clang\test\CodeGenCXX\Output\ubsan-coroutines.cpp.tmp.o
200 mswindows > LLVM.CodeGen/AArch64::arm64-bitfield-extract.ll
Script: -- : 'RUN: at line 2'; c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\opt.exe -codegenprepare -mtriple=arm64-apple=ios -S -o - C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\AArch64\arm64-bitfield-extract.ll | c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\filecheck.exe --check-prefix=OPT C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\AArch64\arm64-bitfield-extract.ll
70 mswindows > LLVM.CodeGen/AArch64::arm64-call-tailcalls.ll
Script: -- : 'RUN: at line 1'; c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\llc.exe < C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\AArch64\arm64-call-tailcalls.ll -mtriple=arm64-apple-ios7.0 | c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\AArch64\arm64-call-tailcalls.ll
180 mswindows > LLVM.CodeGen/AArch64::arm64-collect-loh.ll
Script: -- : 'RUN: at line 1'; c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\llc.exe -o - C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\AArch64\arm64-collect-loh.ll -mtriple=arm64-apple-ios -O2 | c:\ws\w16c2-1\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w16c2-1\llvm-project\premerge-checks\llvm\test\CodeGen\AArch64\arm64-collect-loh.ll
View Full Test Results (191 Failed)

Event Timeline

darcangelo.matthew requested review of this revision.Aug 25 2020, 3:51 PM

Removed the Signed argument from getMinValue

You need to upload the diff between the master branch and your branch, not the last commit in your branch.

RKSimon retitled this revision from [TargetLowering] Combine known bits for icmp in SimplifySetCC - https://bugs.llvm.org/ show_bug.cgi?id=41182 to [TargetLowering] Combine known bits for icmp in SimplifySetCC (PR41182).

Removed mistaken Signed argument

nikic added a comment.Aug 26 2020, 9:29 AM

What is the motivation for this patch? The added tests should already get folded before reaching the backend (by InstCombine). We should only add folds to DAGCombine if the folded pattern is created by legalization. What is the original context for this change?

What is the motivation for this patch? The added tests should already get folded before reaching the backend (by InstCombine). We should only add folds to DAGCombine if the folded pattern is created by legalization. What is the original context for this change?

This was an unassigned enhancement - https://bugs.llvm.org/show_bug.cgi?id=41182 - that I was interested in and wanted to have a go at. Unfortunately that's all I have for context on my end

craig.topper added inline comments.Aug 27 2020, 10:23 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
14134

I'm not sure if we can really do this from SelectionDAG. Is there anywhere else that does this in tree?

llvm/test/CodeGen/X86/test-shrink.ll
574 ↗(On Diff #288003)

Can we pre-commit the IR changes here?

@RKSimon Meant to say this before - Thank you for putting up additional reviewers Simon, I appreciate your help with this

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
14134

I'm not sure if we can really do this from SelectionDAG. Is there anywhere else that does this in tree?

I found the UnreachableMachineBlockElim pass which may be able to be enhanced for this, but I'm still looking

llvm/test/CodeGen/X86/test-shrink.ll
574 ↗(On Diff #288003)

Thank you for taking a look at the changes.

Can we pre-commit the IR changes here?

Sorry, would you be able to elaborate what you mean here? Do you mean separate these out into another pre-commit review?

craig.topper added inline comments.Aug 30 2020, 1:51 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
14134

Sorry, I meant is there anywhere else that does something like this while SelectionDAG exists?

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
3997–3998

Is this just a formatting change?

llvm/test/CodeGen/X86/test-shrink.ll
574 ↗(On Diff #288003)

I went ahead and modified the tests in trunk. Can you rebase this patch?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
14134

Thanks for elaborating, sorry for the confusion. I don't believe there is another place that does something like this while SelectionDAG exists. It seems like BranchFolding might be a good place for me to handle this?

For some additional context, without this change if we have

define i32 @simple(i32 %x) nounwind {
  %1 = and i32 %x, 2147483648
  %2 = icmp sle i32 %1, 0
  br i1 %2, label %yes, label %no

yes:                    ; will always get here
  ret i32 1
no:
  ret i32 2
}

we get

## %bb.0:
         xorl %eax, %eax
         testb %al, %al
	 jne	LBB0_2
## %bb.1:                               ## %yes
	movl	$1, %eax
	retq
LBB0_2:                                 ## %no
	movl	$2, %eax
	retq

so jne will never be taken instead of just removing the branch completely

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
3997–3998

Yes this is just formatting, I must have messed up the merge when I rebased and missed this. Sorry about that, should be fixed now

llvm/test/CodeGen/X86/test-shrink.ll
574 ↗(On Diff #288003)

I went ahead and modified the tests in trunk. Can you rebase this patch?

Sure can, thanks for updating them. Sorry for the confusion