[M68k] Instruction selection to choose neg x when mul x -1 (Fix issue 48588)

[dougpuob]

Summary

This patch is trying to fix issue 48588(https://github.com/llvm/llvm-project/issues/48588)

I found the results of Instruction Selection between SelectionDAG and FastISEL for the %mul = mul i32 %A, 4294967295:
(seldag-isel) mul --> sub --> SUB32dp
(fast-isel) mul --> sub --> NEG32d

My patch to fix this issue is by overriding a virtual function M68kDAGToDAGISel::IsProfitableToFold(). Return false when it was trying to match with SUB, then it will match with NEG.

[dougpuob]

• Apply only the dividend value is zero and revert *.ll files.

[dougpuob]

Hi @myhsu
Even though the instruction selection is focused on sub 0 x only, I still want to build a simple function with clang and run it with QEMU user emulator (qemu-m68k). But I have no idea how to cross-compile it with GCC runtime, do you have any document for it or could you show me a brief instruction.

[dougpuob]

• Remove braces for single line if statements.

[RKSimon]

llvm/lib/Target/M68k/M68kISelDAGToDAG.cpp

326

Any reason why you can't just use llvm::isNullConstant(U->getOperand(0)) ?

llvm/test/CodeGen/M68k/Arith/imul-neg.ll

26

Should we have i16/i8 test coverage as well?

[dougpuob]

llvm/lib/Target/M68k/M68kISelDAGToDAG.cpp

326

Thank you for the reminder. It makes the code cleaner.

llvm/test/CodeGen/M68k/Arith/imul-neg.ll

26

Sure. Increase test coverage is good.

[dougpuob]

• Refine the code and increase test coverage. (Suggestions from RKSimon)

[RKSimon]

llvm/lib/Target/M68k/M68kISelDAGToDAG.cpp

327

(style) Add a break - even though its the last case in the switch() its good practice to use them.

[dougpuob]

llvm/lib/Target/M68k/M68kISelDAGToDAG.cpp

327

Agree with you. Thank you for your careful found.

[dougpuob]

• Add a break to the case of switch statement. (Suggestions from RKSimon)

[myhsu]

LGTM
Thank you!

llvm/lib/Target/M68k/M68kISelDAGToDAG.cpp

326

it will be great to add a short description here to explain why you do this.

[0x59616e]

In D116886#3229948, @dougpuob wrote:

Hi @myhsu
Even though the instruction selection is focused on sub 0 x only, I still want to build a simple function with clang and run it with QEMU user emulator (qemu-m68k). But I have no idea how to cross-compile it with GCC runtime, do you have any document for it or could you show me a brief instruction.

FYI, You can build it with
clang --target=m68k $(SOURCE_FILE) -c -o
and then
m68k-linux-gnu-gcc $(SOURCE_OBJECT) -o $(FILE_NAME)

or
clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -ccc-gcc-name linux-gnu-gcc

Currently lld doesn't have M68k support, but I'm trying on it.
In the future, you may use lld to link m68k object with:
`clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -fuse-ld=lld

[myhsu]

In D116886#3240566, @0x59616e wrote:

In D116886#3229948, @dougpuob wrote:

Hi @myhsu
Even though the instruction selection is focused on sub 0 x only, I still want to build a simple function with clang and run it with QEMU user emulator (qemu-m68k). But I have no idea how to cross-compile it with GCC runtime, do you have any document for it or could you show me a brief instruction.

FYI, You can build it with
clang --target=m68k $(SOURCE_FILE) -c -o
and then
m68k-linux-gnu-gcc $(SOURCE_OBJECT) -o $(FILE_NAME)

or
clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -ccc-gcc-name linux-gnu-gcc

Currently lld doesn't have M68k support, but I'm trying on it.
In the future, you may use lld to link m68k object with:
`clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -fuse-ld=lld

LLD is not required, you can use m68k-linux-gnu-ld to link. The key is using the correct target triple: m68k-linux-gnu rather than just m68k. Such that the compiler driver can find the right tools (in this case m68k-linux-gnu-ld) and libraries to use.
Actually, I just put up a document regarding m68k cross-compiling: https://m680x0.github.io/doc/cross-compile-how-to

[0x59616e]

In D116886#3242621, @myhsu wrote:

In D116886#3240566, @0x59616e wrote:

In D116886#3229948, @dougpuob wrote:

Hi @myhsu
Even though the instruction selection is focused on sub 0 x only, I still want to build a simple function with clang and run it with QEMU user emulator (qemu-m68k). But I have no idea how to cross-compile it with GCC runtime, do you have any document for it or could you show me a brief instruction.

FYI, You can build it with
clang --target=m68k $(SOURCE_FILE) -c -o
and then
m68k-linux-gnu-gcc $(SOURCE_OBJECT) -o $(FILE_NAME)

or
clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -ccc-gcc-name linux-gnu-gcc

Currently lld doesn't have M68k support, but I'm trying on it.
In the future, you may use lld to link m68k object with:
`clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -fuse-ld=lld

LLD is not required, you can use m68k-linux-gnu-ld to link. The key is using the correct target triple: m68k-linux-gnu rather than just m68k. Such that the compiler driver can find the right tools (in this case m68k-linux-gnu-ld) and libraries to use.
Actually, I just put up a document regarding m68k cross-compiling: https://m680x0.github.io/doc/cross-compile-how-to

That makes sense. Thanks

[dougpuob]

In D116886#3242633, @0x59616e wrote:

In D116886#3242621, @myhsu wrote:

In D116886#3240566, @0x59616e wrote:

In D116886#3229948, @dougpuob wrote:

Hi @myhsu
Even though the instruction selection is focused on sub 0 x only, I still want to build a simple function with clang and run it with QEMU user emulator (qemu-m68k). But I have no idea how to cross-compile it with GCC runtime, do you have any document for it or could you show me a brief instruction.

FYI, You can build it with
clang --target=m68k $(SOURCE_FILE) -c -o
and then
m68k-linux-gnu-gcc $(SOURCE_OBJECT) -o $(FILE_NAME)

or
clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -ccc-gcc-name linux-gnu-gcc

Currently lld doesn't have M68k support, but I'm trying on it.
In the future, you may use lld to link m68k object with:
`clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -fuse-ld=lld

LLD is not required, you can use m68k-linux-gnu-ld to link. The key is using the correct target triple: m68k-linux-gnu rather than just m68k. Such that the compiler driver can find the right tools (in this case m68k-linux-gnu-ld) and libraries to use.
Actually, I just put up a document regarding m68k cross-compiling: https://m680x0.github.io/doc/cross-compile-how-to

That makes sense. Thanks

Hi @0x59616e and @myhsu,
Thank your reply. Now I can compile a hello program as an elf executable binary for m68k and execute it in Debian (qemu-system-m68k).

But I still cannot build the hello program with -static. My sample program just call print("Hello M68K!!! \n") in main(). Is it an issue?

❯ bin/clang++ --target=m68k-linux-gnu -static hello.cpp -o hello.m68k.out
/tmp/hello-a7168e.o: in function `main':
hello.cpp:(.text+0x14): relocation truncated to fit: R_68K_PC16 against `.rodata.str1.1'
clang-14: error: linker command failed with exit code 1 (use -v to see invocation)

[dougpuob]

llvm/lib/Target/M68k/M68kISelDAGToDAG.cpp

326

Sure! it is good.

[dougpuob]

• Add a descriptive comment.

[0x59616e]

In D116886#3246562, @dougpuob wrote:

In D116886#3242633, @0x59616e wrote:

In D116886#3242621, @myhsu wrote:

In D116886#3240566, @0x59616e wrote:

In D116886#3229948, @dougpuob wrote:

Hi @myhsu
Even though the instruction selection is focused on sub 0 x only, I still want to build a simple function with clang and run it with QEMU user emulator (qemu-m68k). But I have no idea how to cross-compile it with GCC runtime, do you have any document for it or could you show me a brief instruction.

FYI, You can build it with
clang --target=m68k $(SOURCE_FILE) -c -o
and then
m68k-linux-gnu-gcc $(SOURCE_OBJECT) -o $(FILE_NAME)

or
clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -ccc-gcc-name linux-gnu-gcc

Currently lld doesn't have M68k support, but I'm trying on it.
In the future, you may use lld to link m68k object with:
`clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -fuse-ld=lld

LLD is not required, you can use m68k-linux-gnu-ld to link. The key is using the correct target triple: m68k-linux-gnu rather than just m68k. Such that the compiler driver can find the right tools (in this case m68k-linux-gnu-ld) and libraries to use.
Actually, I just put up a document regarding m68k cross-compiling: https://m680x0.github.io/doc/cross-compile-how-to

That makes sense. Thanks

Hi @0x59616e and @myhsu,
Thank your reply. Now I can compile a hello program as an elf executable binary for m68k and execute it in Debian (qemu-system-m68k).

But I still cannot build the hello program with -static. My sample program just call print("Hello M68K!!! \n") in main(). Is it an issue?

❯ bin/clang++ --target=m68k-linux-gnu -static hello.cpp -o hello.m68k.out
/tmp/hello-a7168e.o: in function `main':
hello.cpp:(.text+0x14): relocation truncated to fit: R_68K_PC16 against `.rodata.str1.1'
clang-14: error: linker command failed with exit code 1 (use -v to see invocation)

Hi,

I haven't dived into the problem, so this just my guess.

It seems that the address of the string (.rodata.str.1, I guess it's the string in your printf) is too far from the instruction itself, PC16 addressing mode is not enough, it needs (maybe ?) PC32.

I guess this issue may have something to do with the code model ?

[dougpuob]

• Rebase against trunk.

[dougpuob]

In D116886#3246619, @0x59616e wrote:

In D116886#3246562, @dougpuob wrote:

In D116886#3242633, @0x59616e wrote:

In D116886#3242621, @myhsu wrote:

In D116886#3240566, @0x59616e wrote:

In D116886#3229948, @dougpuob wrote:

Hi @myhsu
Even though the instruction selection is focused on sub 0 x only, I still want to build a simple function with clang and run it with QEMU user emulator (qemu-m68k). But I have no idea how to cross-compile it with GCC runtime, do you have any document for it or could you show me a brief instruction.

FYI, You can build it with
clang --target=m68k $(SOURCE_FILE) -c -o
and then
m68k-linux-gnu-gcc $(SOURCE_OBJECT) -o $(FILE_NAME)

or
clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -ccc-gcc-name linux-gnu-gcc

Currently lld doesn't have M68k support, but I'm trying on it.
In the future, you may use lld to link m68k object with:
`clang --target=m68k $(SOURCE_FILE) -o $(FILE_NAME) -fuse-ld=lld

LLD is not required, you can use m68k-linux-gnu-ld to link. The key is using the correct target triple: m68k-linux-gnu rather than just m68k. Such that the compiler driver can find the right tools (in this case m68k-linux-gnu-ld) and libraries to use.
Actually, I just put up a document regarding m68k cross-compiling: https://m680x0.github.io/doc/cross-compile-how-to

That makes sense. Thanks

Hi @0x59616e and @myhsu,
Thank your reply. Now I can compile a hello program as an elf executable binary for m68k and execute it in Debian (qemu-system-m68k).

But I still cannot build the hello program with -static. My sample program just call print("Hello M68K!!! \n") in main(). Is it an issue?

❯ bin/clang++ --target=m68k-linux-gnu -static hello.cpp -o hello.m68k.out
/tmp/hello-a7168e.o: in function `main':
hello.cpp:(.text+0x14): relocation truncated to fit: R_68K_PC16 against `.rodata.str1.1'
clang-14: error: linker command failed with exit code 1 (use -v to see invocation)

Hi,

I haven't dived into the problem, so this just my guess.

It seems that the address of the string (.rodata.str.1, I guess it's the string in your printf) is too far from the instruction itself, PC16 addressing mode is not enough, it needs (maybe ?) PC32.

I guess this issue may have something to do with the code model ?

Hi @0x59616e:
Thanks for your idea. It works with -mcmodel=large option.

❯ bin/clang++ hello.cpp --target=m68k-linux-gnu -static -mcmodel=large -o hello.m68k.out
❯ qemu-m68k  hello.m68k.out
Hello M68K!!!

I dumped the sections of the elf, the distance between .text and .rodata is possible greater than 16 bits (0x80047ca8-0x80000168=0x47B40).

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .note.ABI-tag     NOTE            80000114 000114 000020 00   A  0   0  4
  [ 2] .init             PROGBITS        80000134 000134 000032 00  AX  0   0  2
  [ 3] .text             PROGBITS        80000168 000168 0471f8 00  AX  0   0  4 <--+ code
  [ 4] __libc_freeres_fn PROGBITS        80047360 047360 00092c 00  AX  0   0  2    |
  [ 5] .fini             PROGBITS        80047c8c 047c8c 00001c 00  AX  0   0  2    |
  [ 6] .rodata           PROGBITS        80047ca8 047ca8 019354 00   A  0   0  2 <--+ .rodata.str1.1
  [ 7] __libc_subfreeres PROGBITS        80060ffc 060ffc 000024 00   A  0   0  2
  [ 8] __libc_IO_vtables PROGBITS        80061020 061020 0002f4 00   A  0   0  2
  [ 9] __libc_atexit     PROGBITS        80061314 061314 000004 00   A  0   0  2

[dougpuob]

Hi @myhsu,

About the error message, "relocation truncated to fit: R_68K_PC16 against '.rodata.str1.1'" when compile with -static option. I traced the source code. M68K doesn't support CodeModel::Large and CodeModel::Kernel. So, to build a static executable binary via clang, adding -mcmodel=medium is a suitable choice at this moment.

I try to compare the object files (before linker) generated by gcc and clang, the following is my result:

[1/2] compile with clang++ (result: default is R_68K_PC16)

❯ bin/clang++ -static -c --target=m68k-linux-gnu ./hello.cpp
❯ m68k-linux-gnu-readelf -r ./hello.o

Relocation section '.rela.text' at offset 0x180 contains 2 entries:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
00000014  00000305 R_68K_PC16        00000000   .rodata.str1.1 + 0
0000001c  00000501 R_68K_32          00000000   printf + 0

Relocation section '.rela.eh_frame' at offset 0x198 contains 1 entry:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
00000024  00000204 R_68K_PC32        00000000   .text + 0

[2/2] compile with g++ (result: default is R_68K_32)

❯ m68k-linux-gnu-g++ -static -c ./hello.cpp
❯ m68k-linux-gnu-readelf -r ./hello.o

Relocation section '.rela.text' at offset 0x180 contains 2 entries:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
00000006  00000501 R_68K_32          00000000   .rodata + 0
0000000c  00000a01 R_68K_32          00000000   puts + 0

Relocation section '.rela.eh_frame' at offset 0x198 contains 1 entry:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
00000020  00000204 R_68K_PC32        00000000   .text + 0

Summary the result for their default:

• clang: R_68K_PC16
• gcc : R_68K_32

I am not sure that is it an issue or a limitation requiring to build -mcmodel=medium option? Seems you did it for some purpose because of the exclusive getEffectiveCodeModel() function for M68K. If it is not a limitation, I plan to fix it with another patch.

Another doubt about the function. More precisely, its second parameter, bool JIT (https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/M68k/M68kTargetMachine.cpp#L83). Could I know more about it?

[glaubitz]

Any news on this?

[0x59616e]

May I land this ?

[myhsu]

In D116886#3549232, @0x59616e wrote:

May I land this ?

I almost forgot about this patch, I think we can land this patch.
Thank you for your help!

(In case you don't know how to commit on somebody's behalf: git commit --author="name <email>" ...)

[0x59616e]

In D116886#3553981, @myhsu wrote:

In D116886#3549232, @0x59616e wrote:

May I land this ?

I almost forgot about this patch, I think we can land this patch.
Thank you for your help!

(In case you don't know how to commit on somebody's behalf: git commit --author="name <email>" ...)

Got it, Thanks ;)

llvm/lib/Target/M68k/M68kISelDAGToDAG.cpp

public:
   explicit M68kDAGToDAGISel(M68kTargetMachine &TM)
       : SelectionDAGISel(TM), Subtarget(nullptr) {}
 
   StringRef getPassName() const override {
     return "M68k DAG->DAG Pattern Instruction Selection";
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
+  bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const override;
 
 private:
   /// Keep a pointer to the M68kSubtarget around so that we can
   /// make the right decision when generating code for different targets.
   const M68kSubtarget *Subtarget;
 
 // Include the pieces autogenerated from the target description.
 #include "M68kGenDAGISel.inc"
#include "M68kGenDAGISel.inc"
 
   /// Return an SDNode that returns the value of the global base register.
   /// Output instructions required to initialize the global base register,
   /// if necessary.
   SDNode *getGlobalBaseReg();
 };
 } // namespace
 
+bool M68kDAGToDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
+                                          SDNode *Root) const {
+  if (OptLevel == CodeGenOpt::None)
+    return false;
+
+  if (U == Root) {
+    switch (U->getOpcode()) {
+    default:
+      return true;
+    case M68kISD::SUB:
+    case ISD::SUB:
+      // Prefer NEG instruction when zero subtracts a value.
+      // e.g.
+      //   move.l #0, %d0
+      //   sub.l  (4,%sp), %d0
+      // vs.
+      //   move.l (4,%sp), %d0
+      //   neg.l  %d0
+      if (llvm::isNullConstant(U->getOperand(0)))
+        return false;
+      break;
+    }
+  }
+
+  return true;
+}
+
 bool M68kDAGToDAGISel::runOnMachineFunction(MachineFunction &MF) {
   Subtarget = &MF.getSubtarget<M68kSubtarget>();
   return SelectionDAGISel::runOnMachineFunction(MF);
 }
 
 /// This pass converts a legalized DAG into a M68k-specific DAG,
 /// ready for instruction scheduling.
 FunctionPass *llvm::createM68kISelDag(M68kTargetMachine &TM) {

llvm/test/CodeGen/M68k/Arith/imul-neg.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=m68k-linux | FileCheck %s
-; FIXME: When using SelectionDAGISel, the following cases use
-; `sub` rather than the expected `neg`
+
+define i8 @mul255_8(i8 %A) {
+; CHECK-LABEL: mul255_8:
+; CHECK:         .cfi_startproc
+; CHECK-NEXT:  ; %bb.0:
+; CHECK-NEXT:    move.b (7,%sp), %d0
+; CHECK-NEXT:    neg.b  %d0
+; CHECK-NEXT:    rts
+    %mul = mul i8 %A, 255
+    ret i8 %mul
+}
+
+define i16 @mul65535_16(i16 %A) {
+; CHECK-LABEL: mul65535_16:
+; CHECK:         .cfi_startproc
+; CHECK-NEXT:  ; %bb.0:
+; CHECK-NEXT:    move.w (6,%sp), %d0
+; CHECK-NEXT:    neg.w  %d0
+; CHECK-NEXT:    rts
+    %mul = mul i16 %A, 65535
+    ret i16 %mul
+}
 
 define i32 @mul4294967295_32(i32 %A) {
 ; CHECK-LABEL: mul4294967295_32:
 ; CHECK:         .cfi_startproc
 ; CHECK-NEXT:  ; %bb.0:
-; CHECK-NEXT:    move.l #0, %d0
-; CHECK-NEXT:    sub.l (4,%sp), %d0
+; CHECK-NEXT:    move.l (4,%sp), %d0
+; CHECK-NEXT:    neg.l  %d0
 ; CHECK-NEXT:    rts
     %mul = mul i32 %A, 4294967295
     ret i32 %mul
 }
 
 ; NOTE: If returning a 64-bit integer, d0 will be the higher 32-bit!
 define i64 @mul18446744073709551615_64(i64 %A) {
 ; CHECK-LABEL: mul18446744073709551615_64:
 ; CHECK:         .cfi_startproc
 ; CHECK-NEXT:  ; %bb.0:
-; CHECK-NEXT:    move.l (4,%sp), %d0
-; CHECK-NEXT:    move.l #0, %d1
-; CHECK-NEXT:    sub.l (8,%sp), %d1
-; CHECK-NEXT:    negx.l %d0
+; CHECK-NEXT:    move.l (4,%sp), %d0
+; CHECK-NEXT:    move.l (8,%sp), %d1
+; CHECK-NEXT:    neg.l  %d1
+; CHECK-NEXT:    negx.l %d0
 ; CHECK-NEXT:    rts
     %mul = mul i64 %A, 18446744073709551615
     ret i64 %mul
 }