This is an archive of the discontinued LLVM Phabricator instance.

[TargetLowering][DAGCombine][MSP430] Shift Amount Threshold in DAGCombine
AbandonedPublic

Authored by joanlluch on Oct 15 2019, 4:22 AM.

Details

Summary

This is a proposal of a TLI hook to allow targets to relax the emission of shifts (Replaces D68957)

Contributes to a Fix for https://bugs.llvm.org/show_bug.cgi?id=43559

(please note that the diff is from Release/9.x)

Provides codegen improvements on current and future targets with no multiple shift instructions and cheap selects or branches.

For example for the MSP430, the following IR:

; Function Attrs: norecurse nounwind readnone
define dso_local i16 @test2(i16 %a) local_unnamed_addr #0 {
entry:
  %cmp = icmp slt i16 %a, 0
  %cond = select i1 %cmp, i16 2, i16 0
  ret i16 %cond
}

; Function Attrs: norecurse nounwind readnone
define dso_local i16 @test3(i16 %a) local_unnamed_addr #0 {
entry:
  %cmp = icmp slt i16 %a, 0
  %cond = select i1 %cmp, i16 3, i16 0
  ret i16 %cond
}

; Function Attrs: norecurse nounwind readnone
define dso_local i16 @test4(i16 %a, i16 %b) local_unnamed_addr #0 {
entry:
  %cmp = icmp sgt i16 %a, %b
  %cond = select i1 %cmp, i16 32, i16 0
  ret i16 %cond
}

gets translated into this before the patch:

	.globl	test2
	.p2align	1
	.type	test2,@function
test2:
	swpb	r12
	mov.b	r12, r12
	clrc
	rrc	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	and	#2, r12
	ret
.Lfunc_end0:
	.size	test2, .Lfunc_end0-test2

	.globl	test3
	.p2align	1
	.type	test3,@function
test3:
	swpb	r12
	sxt	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	and	#3, r12
	ret
.Lfunc_end1:
	.size	test3, .Lfunc_end1-test3

	.globl	test4
	.p2align	1
	.type	test4,@function
test4:
	mov	r12, r14
	mov	#1, r12
	cmp	r14, r13
	jl	.LBB2_2
	clr	r12
.LBB2_2:
	add	r12, r12
	add	r12, r12
	add	r12, r12
	add	r12, r12
	add	r12, r12
	ret
.Lfunc_end2:
	.size	test4, .Lfunc_end2-test4

After applying the patch, the above code turns into:

	.globl	test2
	.p2align	1
	.type	test2,@function
test2:
	mov	r12, r13
	mov	#1, r12
	tst	r13
	jl	.LBB0_2
	clr	r12
.LBB0_2:
	add	r12, r12
	ret
.Lfunc_end0:
	.size	test2, .Lfunc_end0-test2

	.globl	test3
	.p2align	1
	.type	test3,@function
test3:
	mov	r12, r13
	mov	#3, r12
	tst	r13
	jl	.LBB1_2
	clr	r12
.LBB1_2:
	ret
.Lfunc_end1:
	.size	test3, .Lfunc_end1-test3

	.globl	test4
	.p2align	1
	.type	test4,@function
test4:
	mov	r12, r14
	mov	#32, r12
	cmp	r14, r13
	jl	.LBB2_2
	clr	r12
.LBB2_2:
	ret
.Lfunc_end2:
	.size	test4, .Lfunc_end2-test4

Diff Detail

Event Timeline

joanlluch created this revision.Oct 15 2019, 4:22 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 15 2019, 4:22 AM

I understand the direction, and I think there's general agreement on it (adding some more potential reviewers based on the bug report and llvm-dev thread), but:

  1. Add the tests in the patch description to a file in test/CodeGen/MSP430 as an NFC commit *before* applying this patch. Generate baseline test assertions for current asm using utils/update_llc_test_checks.py.
  2. Split this patch up. In the 1st step, we can add the TLI hook and 1-2 usages of that hook that show a test diff for MSP430. Ideally, we can add small tests for each proposed usage of the TLI hook.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
9496

Formatting: extra space after parenthesis here.
Several places below have the same problem.

spatel added subscribers: krisb, asl.Oct 15 2019, 8:54 AM

Also, I have no knowledge of MSP430, and I don't see a code owner for this target. cc @asl @krisb based on D54623.

asl added a comment.Oct 16 2019, 1:25 AM

The MSP430 changes / overall direction looks extremely useful to me. We just need to ensure everything is done properly. This is exactly what @spatel proposed.

I will be happy to review all MSP430 stuff :)

Hi @spatel
Thank you for your support. I'll try to do what you suggest regarding generating of baseline tests and splitting the patch.

My primary interest is proposing LLVM improvements that will benefit targets of the MSP430 kind, but -just to clarify- I only know what I learned online about that particular target. In fact, I have little practical interest on it, except that it allows me to show the validity of my proposed patches. The same can be said about the 'experimental' AVR target. The AVR is even more benefited from this patch, but I am not even showing it. It would be REALLY nice to get some involvement (or just feedback) from people who implemented or worked on these targets in the past, because I am not able to work on them.

So, given the above, I want to ask whether there would be a generic (or target independent) way to show the effects of this patch. Ideally, given some IR input, demonstrate that the output will minimise the generation of expensive shifts, which some targets will benefit of. It's understandable that showing this in the context of a particular trunk target makes it easier to get approval, but as I am relatively new to LLVM development, I still wonder if there's a target independent way to show the same. Any help would be appreciated.

Thanks.

asl added a comment.Oct 16 2019, 2:24 AM

@joanlluch There are two things here. We understand that there might be some out-of-tree targets that would benefit from changes in the mainline. However, it is still important to add tests that utilize mainline targets as this ensures that the proposed changes won't e.g. break during some refactoring, etc. So, using MSP430 (probably the smallest) / AVR is perfectly fine for tests, etc.!

In D68982#1710529, @asl wrote:

The MSP430 changes / overall direction looks extremely useful to me. We just need to ensure everything is done properly. This is exactly what @spatel proposed.

I will be happy to review all MSP430 stuff :)

Hi,
Sorry, I somehow missed your post before I posted my last one. Thanks for that.

In D68982#1710606, @asl wrote:

@joanlluch There are two things here. We understand that there might be some out-of-tree targets that would benefit from changes in the mainline. However, it is still important to add tests that utilize mainline targets as this ensures that the proposed changes won't e.g. break during some refactoring, etc. So, using MSP430 (probably the smallest) / AVR is perfectly fine for tests, etc.!

I fully understand and agree on that, and I will adhere to it. Still, I found some few cases of LLVM improvements regarding the direction of this patch, that will not fully show on MSP430 because of reversals implemented in the target itself, but I will try to make mentions of them in due term. Thanks again for your support.

asl added a comment.Oct 16 2019, 3:09 AM

If they are not necessary, then it would make sense to undo them. At least partially.

I know this is possibly not the right place to ask this particular question, but I thought that I would get a more focused reply by asking here:

I am stuck now on how to create test files. I created a file shift-amount-threshold.ll with the IR code to test, that compiles fine with llc. Tried to run update_llc_test_checks.py on that file, like this:

/Users/joan/LLVM-9/llvm-project/llvm/utils/update_llc_test_checks.py --llc-binary /Users/joan/LLVM-9/llvm-project/build/Debug/bin/llc /Users/joan/Documents-Local/Relay/RelayNouTest/shift-amount-threshold.ll

but I get the following error:

Traceback (most recent call last):
  File "/Users/joan/LLVM-9/llvm-project/llvm/utils/update_llc_test_checks.py", line 187, in <module>
    main()
  File "/Users/joan/LLVM-9/llvm-project/llvm/utils/update_llc_test_checks.py", line 128, in main
    triple, prefixes, func_dict)
  File "/Users/joan/LLVM-9/llvm-project/llvm/utils/UpdateTestChecks/asm.py", line 335, in build_function_body_dictionary_for_triple
    raise KeyError('Triple %r is not supported' % (triple))
KeyError: "Triple 'msp430' is not supported"

Looked at llvm/utils/UpdateTestChecks/asm.py line 335, and found that "msp430" is not listed there (?).

It's the first time for me at this. What am doing wrong?.
Thanks in advance for any help.

You need to work on svn trunk.

You need to work on svn trunk.

That would be best/easiest. See here for preliminary steps/example commits:
https://bugs.llvm.org/show_bug.cgi?id=43542#c3

joanlluch abandoned this revision.Oct 17 2019, 10:40 AM

Follow ups in D69099 , D69116 and D69120