【TwoAddressInstructionPass】 Put all new instructions into DistanceMap

[Carrot]

Summary

In function convertInstTo3Addr, after converting a two address instruction into three address instruction, only the last new instruction is inserted into DistanceMap. This is wrong, DistanceMap should track all instructions from the beginning of current MBB to the working instruction. When a two address instruction is converted to three address instruction, multiple instructions may be generated (usually an extra COPY is generated), all of them should be inserted into DistanceMap.

Similarly when unfolding memory operand in function tryInstructionTransform DistanceMap is not maintained correctly.

[pengfei]

The tests affected are all trivial. Is this patch a NFC or fixing some real problem. If it is the latter, can we add a test for that?

[Carrot]

I encountered this problem when I was working on a different optimization. It causes real problem in my work, but I can't find a test case for current code base.

[pengfei]

How about adding a mir test?

[Carrot]

Add a mir test.

[pengfei]

llvm/test/CodeGen/X86/distancemap.mir

71

This does seem correct to me. The input in line 88 is
%10:gr16 = ADD16rr killed %3:gr16($di), killed %5:gr16, ...
But the output turns into add [[COPY4]]($esi)?

[Carrot]

llvm/test/CodeGen/X86/distancemap.mir

71

The operands are commuted. This is the exact difference caused by this patch.

Function isProfitableToCommute calls noUseAfterLastDef with argument [[COPY3]] when processing this ADD instruction, DistanceMap is used in noUseAfterLastDef to decide MI's position. When the LEA instruction was generated, several COPY and IMPLICIT_DEF instructions are generated. If they are not added to DistanceMap, noUseAfterLastDef misses the use of [[COPY3]] and returns wrong value. With this patch noUseAfterLastDef can correctly find the use of [[COPY3]] and returns correct value, causes isProfitableToCommute to return different commute decision.

[pengfei]

llvm/test/CodeGen/X86/distancemap.mir

71

Oh, I was misled by the name COPY6. The VR names are nonsense here. This should be bug for update script.
Unfortunately, this test doesn't reveal the intent of the patch either. The swapped COPY3 and COPY4 doesn't show the necessity, which is the same as other tests. I'd suggest to remove it due to the misleading output.
Besides, both COPY3 and COPY4 are used in LEA. The explanation here doesn't persuasive.
I'd like to keep the code as is until we see a functional failure. But I'm neutral :)

[Carrot]

llvm/test/CodeGen/X86/distancemap.mir

71

I have already commented in my previous reply that I can't find a test to show the problem in current code base, so this test just shows the difference, not a real problem.

But the usage of DistanceMap is not very complex. For every processed MI we insert it into DistanceMap, then we can easily find the position of an MI if it is already processed. In this case noUseAfterLastDef returns false for [[COPY3]] at the position of later ADD is obviously wrong since it is actually used in a COPY instruction. Luckily the wrong result of noUseAfterLastDef is only used to guide commuting, so it doesn't cause errors in generated code.

In my optimization, I also use DistanceMap to find if an MI has been processed. I want to change registers in unprocessed MIs. Because DistanceMap doesn't contains COPY instructions generated together with LEA, so my code thinks the COPY has not been processed and changed the COPY instruction, this time it causes wrong code generated.

So the conclusion is:

1. There is a logic error in the usage of DistanceMap, it is not difficult to point out by analyzing the source code.
2. We can see the difference of the bug fixing, but can't see anything wrong with this problem because it is only used to guide commuting in current code base. So you'll never see a functional failure.
3. In my code I use DistanceMap to find if an MI need to be changed, this time the bug can cause wrong code generated.

[pengfei]

llvm/test/CodeGen/X86/distancemap.mir

71

I didn't dig deep into the code, just some general questions:

1. The distances in DistanceMap seem to be the order of input. What's the mean with this change? I don't think you counted all new COPY MI. E.g. the one in line 56, right?
2. DistanceMap uses insert and erase methods in other places, do you need to do the same thing for the insert and remove the inserted COPYs together when erase?

[Carrot]

llvm/test/CodeGen/X86/distancemap.mir

71

I didn't dig deep into the code, just some general questions:

1. The distances in DistanceMap seem to be the order of input. What's the mean with this change? I don't think you counted all new COPY MI. E.g. the one in line 56, right?

Line 56 has been correctly inserted into DistanceMap in function processTiedPairs. Lines 59..63 are missed, only line 64 is added in function convertInstTo3Addr. It is fixed by this patch.

2. DistanceMap uses insert and erase methods in other places, do you need to do the same thing for the insert and remove the inserted COPYs together when erase?

If there are missed entries in DistanceMap, they should be added, otherwise noUseAfterLastDef doesn't work correctly. If there are extra entries in DistanceMap, they may not hurt current code, they are just garbage, it's better to remove them to prevent unintended future use.

[Carrot]

Thank pengfei's question, I did find another case that DistanceMap is not maintained correctly when unfolding memory operand.

[pengfei]

LGTM.

llvm/lib/CodeGen/TwoAddressInstructionPass.cpp

class TwoAddressInstructionPass : public MachineFunctionPass {
 
   bool commuteInstruction(MachineInstr *MI, unsigned DstIdx,
                           unsigned RegBIdx, unsigned RegCIdx, unsigned Dist);
 
   bool isProfitableToConv3Addr(Register RegA, Register RegB);
 
   bool convertInstTo3Addr(MachineBasicBlock::iterator &mi,
                           MachineBasicBlock::iterator &nmi, Register RegA,
-                          Register RegB, unsigned Dist);
+                          Register RegB, unsigned &Dist);
 
   bool isDefTooClose(Register Reg, unsigned Dist, MachineInstr *MI);
 
   bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
                              MachineBasicBlock::iterator &nmi, Register Reg);
   bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
                              MachineBasicBlock::iterator &nmi, Register Reg);
 
   bool tryInstructionTransform(MachineBasicBlock::iterator &mi,
                                MachineBasicBlock::iterator &nmi,
                                unsigned SrcIdx, unsigned DstIdx,
-                               unsigned Dist, bool shouldOnlyCommute);
+                               unsigned &Dist, bool shouldOnlyCommute);
 
   bool tryInstructionCommute(MachineInstr *MI,
                              unsigned DstOpIdx,
                              unsigned BaseOpIdx,
                              bool BaseOpKilled,
                              unsigned Dist);
   void scanUses(Register DstReg);
 
bool TwoAddressInstructionPass::isProfitableToConv3Addr(Register RegA,
   MCRegister ToRegA = getMappedReg(RegA, DstRegMap);
   return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI));
 }
 
 /// Convert the specified two-address instruction into a three address one.
 /// Return true if this transformation was successful.
 bool TwoAddressInstructionPass::convertInstTo3Addr(
     MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi,
-    Register RegA, Register RegB, unsigned Dist) {
+    Register RegA, Register RegB, unsigned &Dist) {
   MachineInstrSpan MIS(mi, MBB);
   MachineInstr *NewMI = TII->convertToThreeAddress(*mi, LV);
   if (!NewMI)
     return false;
 
   LLVM_DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
   LLVM_DEBUG(dbgs() << "2addr:         TO 3-ADDR: " << *NewMI);
 
if (LIS && !SingleInst) {
     LIS->RemoveMachineInstrFromMaps(*mi);
   }
 
   MBB->erase(mi); // Nuke the old inst.
 
   if (LIS && !SingleInst)
     LIS->repairIntervalsInRange(MBB, MIS.begin(), MIS.end(), OrigRegs);
 
-  DistanceMap.insert(std::make_pair(NewMI, Dist));
+  for (MachineInstr &MI : MIS)
+    DistanceMap.insert(std::make_pair(&MI, Dist++));
+  Dist--;
   mi = NewMI;
   nmi = std::next(mi);
 
   // Update source and destination register maps.
   SrcRegMap.erase(RegA);
   DstRegMap.erase(RegB);
   return true;
 }

 
 /// For the case where an instruction has a single pair of tied register
 /// operands, attempt some transformations that may either eliminate the tied
 /// operands or improve the opportunities for coalescing away the register copy.
 /// Returns true if no copy needs to be inserted to untie mi's operands
 /// (either because they were untied, or because mi was rescheduled, and will
 /// be visited again later). If the shouldOnlyCommute flag is true, only
 /// instruction commutation is attempted.
 bool TwoAddressInstructionPass::
 tryInstructionTransform(MachineBasicBlock::iterator &mi,
                         MachineBasicBlock::iterator &nmi,
                         unsigned SrcIdx, unsigned DstIdx,
-                        unsigned Dist, bool shouldOnlyCommute) {
+                        unsigned &Dist, bool shouldOnlyCommute) {
   if (OptLevel == CodeGenOpt::None)
     return false;
 
   MachineInstr &MI = *mi;
   Register regA = MI.getOperand(DstIdx).getReg();
   Register regB = MI.getOperand(SrcIdx).getReg();
 
   assert(regB.isVirtual() && "cannot make instruction into two-address form");

llvm/test/CodeGen/X86/addcarry.ll

 define i8 @e(i32* nocapture %a, i32 %b) nounwind {
 ; CHECK-LABEL: e:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    # kill: def $esi killed $esi def $rsi
 ; CHECK-NEXT:    movl (%rdi), %ecx
 ; CHECK-NEXT:    leal (%rsi,%rcx), %edx
 ; CHECK-NEXT:    addl %esi, %edx
 ; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    addl %esi, %ecx
+; CHECK-NEXT:    addl %ecx, %esi
 ; CHECK-NEXT:    movl %edx, (%rdi)
 ; CHECK-NEXT:    adcb $0, %al
 ; CHECK-NEXT:    retq
   %1 = load i32, i32* %a, align 4
   %2 = add i32 %1, %b
   %3 = icmp ult i32 %2, %b
   %4 = zext i1 %3 to i8
   %5 = add i32 %2, %b

llvm/test/CodeGen/X86/distancemap.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc %s -o - -mtriple=x86_64-unknown-linux -run-pass=twoaddressinstruction -verify-machineinstrs | FileCheck %s
+
+# In TwoAddressInstructionPass, new instructions should be added to DistanceMap.
+# In this case, function convertInstTo3Addr is called on the first ADD
+# instruction, extra COPY instructions are generated. If they are not added to
+# DistanceMap, function noUseAfterLastDef computes a wrong value for the later
+# ADD instruction, and a different commute decision is made.
+
+--- |
+  ; ModuleID = 't.ll'
+  source_filename = "t.ll"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux"
+
+  declare i16 @llvm.sadd.sat.i16(i16, i16)
+
+  define signext i16 @func16(i16 signext %x, i16 signext %y, i16 signext %z) nounwind {
+    %a = mul i16 %y, %z
+    %tmp = call i16 @llvm.sadd.sat.i16(i16 %x, i16 %a)
+    ret i16 %tmp
+  }
+
+...
+---
+name:            func16
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr32 }
+  - { id: 1, class: gr32 }
+  - { id: 2, class: gr32 }
+  - { id: 3, class: gr16 }
+  - { id: 4, class: gr32 }
+  - { id: 5, class: gr16 }
+  - { id: 6, class: gr16 }
+  - { id: 7, class: gr32 }
+  - { id: 8, class: gr32 }
+  - { id: 9, class: gr32 }
+  - { id: 10, class: gr16 }
+  - { id: 11, class: gr32 }
+  - { id: 13, class: gr32 }
+  - { id: 14, class: gr16 }
+frameInfo:
+  maxAlignment:    1
+body:             |
+  bb.0 :
+    liveins: $edi, $esi, $edx
+    ; CHECK-LABEL: name: func16
+    ; CHECK: liveins: $edi, $esi, $edx
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:gr32 = COPY killed $edx
+    ; CHECK-NEXT: [[COPY1:%[0-9]+]]:gr32 = COPY killed $esi
+    ; CHECK-NEXT: [[COPY2:%[0-9]+]]:gr32 = COPY killed $edi
+    ; CHECK-NEXT: [[COPY3:%[0-9]+]]:gr16 = COPY killed [[COPY2]].sub_16bit
+    ; CHECK-NEXT: [[COPY4:%[0-9]+]]:gr32 = COPY [[COPY1]]
+    ; CHECK-NEXT: [[IMUL32rr:%[0-9]+]]:gr32 = IMUL32rr [[IMUL32rr]], killed [[COPY]], implicit-def dead $eflags
+    ; CHECK-NEXT: [[COPY4:%[0-9]+]]:gr16 = COPY killed [[IMUL32rr]].sub_16bit
+    ; CHECK-NEXT: [[DEF:%[0-9]+]]:gr64_nosp = IMPLICIT_DEF
+    ; CHECK-NEXT: [[DEF]].sub_16bit:gr64_nosp = COPY [[COPY3]]
+    ; CHECK-NEXT: [[DEF1:%[0-9]+]]:gr64_nosp = IMPLICIT_DEF
+    ; CHECK-NEXT: [[DEF1]].sub_16bit:gr64_nosp = COPY [[COPY4]]
+    ; CHECK-NEXT: [[LEA64_32r:%[0-9]+]]:gr32 = LEA64_32r killed [[DEF]], 1, killed [[DEF1]], 0, $noreg
+    ; CHECK-NEXT: [[COPY5:%[0-9]+]]:gr16 = COPY killed [[LEA64_32r]].sub_16bit
+    ; CHECK-NEXT: [[MOVSX32rr16_:%[0-9]+]]:gr32 = MOVSX32rr16 killed [[COPY5]]
+    ; CHECK-NEXT: [[COPY6:%[0-9]+]]:gr32 = COPY [[MOVSX32rr16_]]
+    ; CHECK-NEXT: [[SAR32ri:%[0-9]+]]:gr32 = SAR32ri [[SAR32ri]], 15, implicit-def dead $eflags
+    ; CHECK-NEXT: [[COPY6:%[0-9]+]]:gr32 = COPY [[SAR32ri]]
+    ; CHECK-NEXT: [[XOR32ri:%[0-9]+]]:gr32 = XOR32ri [[XOR32ri]], -32768, implicit-def dead $eflags
+    ; CHECK-NEXT: [[COPY6:%[0-9]+]]:gr16 = COPY [[COPY3]]
+    ; CHECK-NEXT: [[ADD16rr:%[0-9]+]]:gr16 = ADD16rr [[ADD16rr]], killed [[COPY4]], implicit-def $eflags
+    ; CHECK-NEXT: undef %11.sub_16bit:gr32 = COPY killed [[ADD16rr]]
+    ; CHECK-NEXT: [[COPY6:%[0-9]+]]:gr32 = COPY [[XOR32ri]]
+    ; CHECK-NEXT: [[CMOV32rr:%[0-9]+]]:gr32 = CMOV32rr [[CMOV32rr]], killed %11, 1, implicit killed $eflags
+    ; CHECK-NEXT: [[COPY6:%[0-9]+]]:gr16 = COPY killed [[CMOV32rr]].sub_16bit
+    ; CHECK-NEXT: $ax = COPY killed [[COPY6]]
+    ; CHECK-NEXT: RET 0, killed $ax
+    %2:gr32 = COPY killed $edx
+    %1:gr32 = COPY killed $esi
+    %0:gr32 = COPY killed $edi
+    %3:gr16 = COPY killed %0.sub_16bit:gr32
+    %4:gr32 = IMUL32rr killed %1:gr32, killed %2:gr32, implicit-def dead $eflags
+    %5:gr16 = COPY killed %4.sub_16bit:gr32
+    %6:gr16 = ADD16rr %3:gr16, %5:gr16, implicit-def dead $eflags
+    %7:gr32 = MOVSX32rr16 killed %6:gr16
+    %8:gr32 = SAR32ri killed %7:gr32, 15, implicit-def dead $eflags
+    %9:gr32 = XOR32ri killed %8:gr32, -32768, implicit-def dead $eflags
+    %10:gr16 = ADD16rr killed %3:gr16, killed %5:gr16, implicit-def $eflags
+    %11:gr32 = INSERT_SUBREG undef %12:gr32, killed %10:gr16, %subreg.sub_16bit
+    %13:gr32 = CMOV32rr killed %11:gr32, killed %9:gr32, 0, implicit killed $eflags
+    %14:gr16 = COPY killed %13.sub_16bit:gr32
+    $ax = COPY killed %14:gr16
+    RET 0, killed $ax
+
+...

llvm/test/CodeGen/X86/sadd_sat_plus.ll

 ; X64:       # %bb.0:
 ; X64-NEXT:    # kill: def $esi killed $esi def $rsi
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
 ; X64-NEXT:    imull %edx, %esi
 ; X64-NEXT:    leal (%rdi,%rsi), %eax
 ; X64-NEXT:    cwtl
 ; X64-NEXT:    sarl $15, %eax
 ; X64-NEXT:    xorl $-32768, %eax # imm = 0x8000
-; X64-NEXT:    addw %di, %si
-; X64-NEXT:    cmovnol %esi, %eax
+; X64-NEXT:    addw %si, %di
+; X64-NEXT:    cmovnol %edi, %eax
 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
   %a = mul i16 %y, %z
   %tmp = call i16 @llvm.sadd.sat.i16(i16 %x, i16 %a)
   ret i16 %tmp
 }
 
 define signext i8 @func8(i8 signext %x, i8 signext %y, i8 signext %z) nounwind {

 ; X64-NEXT:    movl %esi, %eax
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
 ; X64-NEXT:    # kill: def $al killed $al killed $eax
 ; X64-NEXT:    mulb %dl
 ; X64-NEXT:    # kill: def $al killed $al def $rax
 ; X64-NEXT:    leal (%rdi,%rax), %ecx
 ; X64-NEXT:    sarb $7, %cl
 ; X64-NEXT:    xorb $-128, %cl
-; X64-NEXT:    addb %dil, %al
-; X64-NEXT:    movzbl %al, %edx
+; X64-NEXT:    addb %al, %dil
+; X64-NEXT:    movzbl %dil, %edx
 ; X64-NEXT:    movzbl %cl, %eax
 ; X64-NEXT:    cmovnol %edx, %eax
 ; X64-NEXT:    # kill: def $al killed $al killed $eax
 ; X64-NEXT:    retq
   %a = mul i8 %y, %z
   %tmp = call i8 @llvm.sadd.sat.i8(i8 %x, i8 %a)
   ret i8 %tmp
 }

llvm/test/CodeGen/X86/sadd_sat_vec.ll

 define void @v1i8(<1 x i8>* %px, <1 x i8>* %py, <1 x i8>* %pz) nounwind {
 ; SSE-LABEL: v1i8:
 ; SSE:       # %bb.0:
 ; SSE-NEXT:    movb (%rdi), %al
 ; SSE-NEXT:    movb (%rsi), %cl
 ; SSE-NEXT:    leal (%rax,%rcx), %esi
 ; SSE-NEXT:    sarb $7, %sil
 ; SSE-NEXT:    xorb $-128, %sil
-; SSE-NEXT:    addb %al, %cl
-; SSE-NEXT:    movzbl %cl, %eax
+; SSE-NEXT:    addb %cl, %al
+; SSE-NEXT:    movzbl %al, %eax
 ; SSE-NEXT:    movzbl %sil, %ecx
 ; SSE-NEXT:    cmovnol %eax, %ecx
 ; SSE-NEXT:    movb %cl, (%rdx)
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: v1i8:
 ; AVX:       # %bb.0:
 ; AVX-NEXT:    movb (%rdi), %al
 ; AVX-NEXT:    movb (%rsi), %cl
 ; AVX-NEXT:    leal (%rax,%rcx), %esi
 ; AVX-NEXT:    sarb $7, %sil
 ; AVX-NEXT:    xorb $-128, %sil
-; AVX-NEXT:    addb %al, %cl
-; AVX-NEXT:    movzbl %cl, %eax
+; AVX-NEXT:    addb %cl, %al
+; AVX-NEXT:    movzbl %al, %eax
 ; AVX-NEXT:    movzbl %sil, %ecx
 ; AVX-NEXT:    cmovnol %eax, %ecx
 ; AVX-NEXT:    movb %cl, (%rdx)
 ; AVX-NEXT:    retq
   %x = load <1 x i8>, <1 x i8>* %px
   %y = load <1 x i8>, <1 x i8>* %py
   %z = call <1 x i8> @llvm.sadd.sat.v1i8(<1 x i8> %x, <1 x i8> %y)
   store <1 x i8> %z, <1 x i8>* %pz
   ret void
 }
 
 define void @v1i16(<1 x i16>* %px, <1 x i16>* %py, <1 x i16>* %pz) nounwind {
 ; SSE-LABEL: v1i16:
 ; SSE:       # %bb.0:
 ; SSE-NEXT:    movzwl (%rdi), %eax
 ; SSE-NEXT:    movzwl (%rsi), %ecx
 ; SSE-NEXT:    leal (%rax,%rcx), %esi
 ; SSE-NEXT:    movswl %si, %esi
 ; SSE-NEXT:    sarl $15, %esi
 ; SSE-NEXT:    xorl $-32768, %esi # imm = 0x8000
-; SSE-NEXT:    addw %ax, %cx
-; SSE-NEXT:    cmovol %esi, %ecx
-; SSE-NEXT:    movw %cx, (%rdx)
+; SSE-NEXT:    addw %cx, %ax
+; SSE-NEXT:    cmovol %esi, %eax
+; SSE-NEXT:    movw %ax, (%rdx)
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: v1i16:
 ; AVX:       # %bb.0:
 ; AVX-NEXT:    movzwl (%rdi), %eax
 ; AVX-NEXT:    movzwl (%rsi), %ecx
 ; AVX-NEXT:    leal (%rax,%rcx), %esi
 ; AVX-NEXT:    movswl %si, %esi
 ; AVX-NEXT:    sarl $15, %esi
 ; AVX-NEXT:    xorl $-32768, %esi # imm = 0x8000
-; AVX-NEXT:    addw %ax, %cx
-; AVX-NEXT:    cmovol %esi, %ecx
-; AVX-NEXT:    movw %cx, (%rdx)
+; AVX-NEXT:    addw %cx, %ax
+; AVX-NEXT:    cmovol %esi, %eax
+; AVX-NEXT:    movw %ax, (%rdx)
 ; AVX-NEXT:    retq
   %x = load <1 x i16>, <1 x i16>* %px
   %y = load <1 x i16>, <1 x i16>* %py
   %z = call <1 x i16> @llvm.sadd.sat.v1i16(<1 x i16> %x, <1 x i16> %y)
   store <1 x i16> %z, <1 x i16>* %pz
   ret void
 }