Page MenuHomePhabricator

[AVR] Optimize int16 airthmetic right shift for shift amount 7/14/15
ClosedPublic

Authored by benshi001 on Dec 13 2021, 2:58 AM.

Diff Detail

Event Timeline

benshi001 created this revision.Dec 13 2021, 2:58 AM
benshi001 requested review of this revision.Dec 13 2021, 2:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 13 2021, 2:58 AM
benshi001 updated this revision to Diff 393822.Dec 13 2021, 2:58 AM
benshi001 retitled this revision from [AVR] Optimize int16 airthmetic right shift for shift amount 7/14/15 to [AVR] Optimize int16 airthmetic right shift for shift amount 7/14/15.
benshi001 updated this revision to Diff 393837.Dec 13 2021, 3:38 AM
benshi001 updated this revision to Diff 393854.Dec 13 2021, 4:53 AM
benshi001 updated this revision to Diff 397464.Jan 4 2022, 11:51 PM
benshi001 updated this revision to Diff 397509.Jan 5 2022, 3:41 AM

Can you please add some .mir tests? As an example, I have created one for ASRW7Rd and ASRW8Rd:

# RUN: llc -O0 -run-pass=avr-expand-pseudo %s -o - | FileCheck %s

--- |
  target triple = "avr--"
  define void @test() {
  entry:
    ret void
  }
...

---
name:            test
body: |
  bb.0.entry:
    liveins: $r15r14

    ; CHECK-LABEL: test

    ; CHECK:      $r14 = ADDRdRr $r14, $r14, implicit-def undef $sreg
    ; CHECK-NEXT: $r14 = MOVRdRr $r15
    ; CHECK-NEXT: $r14 = ADCRdRr $r14, $r14, implicit-def $sreg, implicit $sreg
    ; CHECK-NEXT: $r15 = SBCRdRr $r15, $r15, implicit-def $sreg, implicit killed $sreg
    $r15r14 = ASRWNRd $r15r14, 7, implicit-def $sreg

    ; CHECK:      $r14 = MOVRdRr $r15
    ; CHECK-NEXT: $r15 = ADDRdRr $r15, $r15, implicit-def $sreg
    ; CHECK-NEXT: $r15 = SBCRdRr $r15, $r15, implicit-def $sreg, implicit killed $sreg
    $r15r14 = ASRWNRd $r15r14, 8, implicit-def $sreg
...

Here you can easily see the register states (undef, dead, kill, etc).

Also, I have found that ASRWNRd has DLDREGS as the output register, but I think the whole range (DREGS) is supported? DLDREGS are only the upper wide register (R17r16 to r31r3). That's perhaps a missed optimization.

While running this test locally, I also found the following error which I haven't investigated yet but is probably due to an incorrect kill flag ($r20 = MOVRdRr killed $r21):

FAIL: LLVM :: CodeGen/AVR/sign-extension.ll (11 of 144)
******************** TEST 'LLVM :: CodeGen/AVR/sign-extension.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   llc -verify-machineinstrs -march=avr < /home/ayke/src/github.com/tinygo-org/tinygo/llvm-project.main/llvm/test/CodeGen/AVR/sign-extension.ll | /home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/FileCheck /home/ayke/src/github.com/tinygo-org/tinygo/llvm-project.main/llvm/test/CodeGen/AVR/sign-extension.ll
--
Exit Code: 2

Command Output (stderr):
--

# After AVR pseudo instruction expansion pass
# Machine code for function sign_extended_8_to_64: NoPHIs, TracksLiveness, NoVRegs, TiedOpsRewritten, TracksDebugUserValues
Function Live Ins: $r24

bb.0.entry-block:
  liveins: $r24
  $r18 = MOVRdRr $r24
  $r19 = MOVRdRr killed $r24
  $r19 = ADDRdRr $r19(tied-def 0), killed $r19, implicit-def $sreg
  $r19 = SBCRdRr killed $r19(tied-def 0), killed $r19, implicit-def dead $sreg, implicit killed $sreg
  $r20 = MOVRdRr $r18
  $r21 = MOVRdRr $r19
  $r21 = ADDRdRr killed $r21(tied-def 0), killed $r21, implicit-def undef $sreg
  $r21 = SBCRdRr killed $r21(tied-def 0), killed $r21, implicit-def dead $sreg, implicit killed $sreg
  $r20 = MOVRdRr killed $r21
  $r22 = MOVRdRr $r20
  $r23 = MOVRdRr $r21
  $r24 = MOVRdRr $r20
  $r25 = MOVRdRr $r21
  RET implicit $r19r18, implicit $r21r20, implicit killed $r23r22, implicit $r25r24, implicit $r1

# End machine code for function sign_extended_8_to_64.

*** Bad machine code: Using an undefined physical register ***
- function:    sign_extended_8_to_64
- basic block: %bb.0 entry-block (0x556ea4da46f0)
- instruction: $r23 = MOVRdRr $r21
- operand 1:   $r21

*** Bad machine code: Using an undefined physical register ***
- function:    sign_extended_8_to_64
- basic block: %bb.0 entry-block (0x556ea4da46f0)
- instruction: $r25 = MOVRdRr $r21
- operand 1:   $r21
LLVM ERROR: Found 2 machine code errors.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0.	Program arguments: llc -verify-machineinstrs -march=avr
1.	Running pass 'Function Pass Manager' on module '<stdin>'.
2.	Running pass 'Verify generated machine code' on function '@sign_extended_8_to_64'
 #0 0x0000556ea28279cf PrintStackTraceSignalHandler(void*) Signals.cpp:0:0
 #1 0x0000556ea282519e SignalHandler(int) Signals.cpp:0:0
 #2 0x00007ff051608730 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12730)
 #3 0x00007ff05113a7bb raise (/lib/x86_64-linux-gnu/libc.so.6+0x377bb)
 #4 0x00007ff051125535 abort (/lib/x86_64-linux-gnu/libc.so.6+0x22535)
 #5 0x0000556ea2768435 llvm::report_fatal_error(llvm::Twine const&, bool) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x3f9c435)
 #6 0x0000556ea1b5f3e0 (anonymous namespace)::MachineVerifierPass::runOnMachineFunction(llvm::MachineFunction&) MachineVerifier.cpp:0:0
 #7 0x0000556ea1b5f40c (anonymous namespace)::MachineVerifierPass::runOnMachineFunction(llvm::MachineFunction&) MachineVerifier.cpp:0:0
 #8 0x0000556ea1a67420 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x329b420)
 #9 0x0000556ea1f215f0 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x37555f0)
#10 0x0000556ea1f21811 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x3755811)
#11 0x0000556ea1f222f5 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x37562f5)
#12 0x0000556ea0bac6bb compileModule(char**, llvm::LLVMContext&) llc.cpp:0:0
#13 0x0000556ea0bad69a main (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x23e169a)
#14 0x00007ff05112709b __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2409b)
#15 0x0000556ea0ba018a _start (/home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/llc+0x23d418a)
FileCheck error: '<stdin>' is empty.
FileCheck command line:  /home/ayke/src/github.com/tinygo-org/tinygo/llvm-build.main/bin/FileCheck /home/ayke/src/github.com/tinygo-org/tinygo/llvm-project.main/llvm/test/CodeGen/AVR/sign-extension.ll

You can reproduce this with the following command:

llvm-build/bin/llc -verify-machineinstrs -march=avr < path/to/llvm/test/CodeGen/AVR/sign-extension.ll
llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp
1844

This register is always dead. It's overwritten (killed) by the mov instruction on the next line.

1845–1846

These two input operands are always killed: they are the last use of this input value.

1847–1848

You are setting the output operand SREG to undef? I don't think that's correct. AFAIK only input operands can be set to undef. Also, you are going to use the output of the SREG later, so I don't think it should be set to undef.

aykevl requested changes to this revision.Jan 17 2022, 4:29 AM

(just so that this doesn't appear in my review queue anymore)

This revision now requires changes to proceed.Jan 17 2022, 4:29 AM
benshi001 marked 3 inline comments as done.

(just so that this doesn't appear in my review queue anymore)

Thanks for your suggestion. I have done

  1. Add a new MIR test to show register state changes.
  2. Corrent wrong register state when expanding the ASRW7/ASRW14/ASRW15 pseudo instructions.
  3. Add -verify-machineinstrs option to the /llvm/test/CodeGen/AVR/sign-extension.ll
  4. Change the register class of ASRWNRd from DLDREGS to DREGS.
benshi001 updated this revision to Diff 412301.Mar 1 2022, 6:35 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 1 2022, 6:35 PM
benshi001 updated this revision to Diff 412307.Mar 1 2022, 7:27 PM
benshi001 updated this revision to Diff 412312.Mar 1 2022, 8:06 PM
benshi001 updated this revision to Diff 414547.Mar 10 2022, 6:23 PM
aykevl accepted this revision.Mar 25 2022, 7:28 AM
aykevl added inline comments.
llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp
1849

You could use the following instead, which is a bit shorter (but has the same effect):

buildMI(MBB, MBBI, AVR::MOVRdRr, DstLoReg)
  .addReg(DstHiReg);

(The same change can be applied in other places in this patch).

This revision is now accepted and ready to land.Mar 25 2022, 7:28 AM
This revision was landed with ongoing or failed builds.Mar 25 2022, 11:53 PM
This revision was automatically updated to reflect the committed changes.