Fix the side effect of outlined function when the register is implicit use and implicit-def in the same instruction.

[DianQK]

Summary

This is the diff associated with D95267: Add the use of register r for outlined function when register r is live in and defined later., and we need to mark $x0 as live whether or not $x0 is dead.

The compiler also needs to mark register $x0 as live in for the following case.

$x1 = ADDXri $sp, 16, 0
BL @spam, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit-def $sp, implicit-def $x0

This change fixes an issue where the wrong registers were used when -machine-outliner-reruns>0.
As an example:

typedef struct {
    double v1;
    double v2;
} D16;

typedef struct {
    D16 v1;
    D16 v2;
} D32;

typedef long long LL8;
typedef struct {
    long long v1;
    long long v2;
} LL16;
typedef struct {
    LL16 v1;
    LL16 v2;
} LL32;

typedef struct {
    LL32 v1;
    LL32 v2;
} LL64;

LL8 needx0(LL8 v0, LL8 v1);

void bar(LL64 v1, LL32 v2, LL16 v3, LL32 v4, LL8 v5, D16 v6, D16 v7, D16 v8);

LL8 foo(LL8 v0, LL64 v1, LL32 v2, LL16 v3, LL32 v4, LL8 v5, D16 v6, D16 v7, D16 v8)
{
  LL8 result = needx0(v0, 0);
  bar(v1, v2, v3, v4, v5, v6, v7, v8);
  return result + 1;
}

As you can see from the foo function, we should not modify the value of x0 until we call needx0.
This code is compiled to give the following instruction MIR code.

$sp = frame-setup SUBXri $sp, 256, 0
frame-setup STPDi killed $d13, killed $d12, $sp, 16
frame-setup STPDi killed $d11, killed $d10, $sp, 18
frame-setup STPDi killed $d9, killed $d8, $sp, 20

frame-setup STPXi killed $x26, killed $x25, $sp, 22
frame-setup STPXi killed $x24, killed $x23, $sp, 24
frame-setup STPXi killed $x22, killed $x21, $sp, 26
frame-setup STPXi killed $x20, killed $x19, $sp, 28
...
$x1 = MOVZXi 0, 0
BL @needx0, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit $x1, implicit-def $sp, implicit-def $x0
...

Since there are some other instruction sequences that duplicate foo, after the first execution of Machine Outliner you will get:

$sp = frame-setup SUBXri $sp, 256, 0
frame-setup STPDi killed $d13, killed $d12, $sp, 16
frame-setup STPDi killed $d11, killed $d10, $sp, 18
frame-setup STPDi killed $d9, killed $d8, $sp, 20

$x7 = ORRXrs $xzr, $lr, 0
BL @OUTLINED_FUNCTION_0, implicit-def $lr, implicit $sp, implicit-def $lr, implicit $sp, implicit $xzr, implicit $x7, implicit $x19, implicit $x20, implicit $x21, implicit $x22, implicit $x23, implicit $x24, implicit $x25, implicit $x26
$lr = ORRXrs $xzr, $x7, 0
...
BL @OUTLINED_FUNCTION_1, implicit-def $lr, implicit $sp, implicit-def $lr, implicit-def $sp, implicit-def $x0, implicit-def $x1, implicit $sp
...

For the first time we outlined the following sequence:

frame-setup STPXi killed $x26, killed $x25, $sp, 22
frame-setup STPXi killed $x24, killed $x23, $sp, 24
frame-setup STPXi killed $x22, killed $x21, $sp, 26
frame-setup STPXi killed $x20, killed $x19, $sp, 28

and

$x1 = MOVZXi 0, 0
BL @needx0, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit $x1, implicit-def $sp, implicit-def $x0

When we execute the outline again, we will get:

$x0 = ORRXrs $xzr, $lr, 0 <---- here
BL @OUTLINED_FUNCTION_2_0, implicit-def $lr, implicit $sp, implicit-def $sp, implicit-def $lr, implicit $sp, implicit $xzr, implicit $d8, implicit $d9, implicit $d10, implicit $d11, implicit $d12, implicit $d13, implicit $x0
$lr = ORRXrs $xzr, $x0, 0

$x7 = ORRXrs $xzr, $lr, 0
BL @OUTLINED_FUNCTION_0, implicit-def $lr, implicit $sp, implicit-def $lr, implicit $sp, implicit $xzr, implicit $x7, implicit $x19, implicit $x20, implicit $x21, implicit $x22, implicit $x23, implicit $x24, implicit $x25, implicit $x26
$lr = ORRXrs $xzr, $x7, 0
...
BL @OUTLINED_FUNCTION_1, implicit-def $lr, implicit $sp, implicit-def $lr, implicit-def $sp, implicit-def $x0, implicit-def $x1, implicit $sp

When calling OUTLINED_FUNCTION_2_0, we used x0 to save the lr register.
The reason for the above error appears to be that:

BL @OUTLINED_FUNCTION_1, implicit-def $lr, implicit $sp, implicit-def $lr, implicit-def $sp, implicit-def $x0, implicit-def $x1, implicit $sp

should be:

BL @OUTLINED_FUNCTION_1, implicit-def $lr, implicit $sp, implicit-def $lr, implicit-def $sp, implicit-def $x0, implicit-def $x1, implicit $sp, implicit $x0

When processing the same instruction with both implicit-def $x0 and implicit $x0 we should keep implicit $x0.
A reproducible demo is available at: https://github.com/DianQK/reproduce_outlined_function_use_live_x0.

[DianQK]

remove !MOP.isDead() && and machine-outliner-side-effect-3.mir

[DianQK]

reformat

[DianQK]

rebase

[DianQK]

rebased

[jinlin]

Here is the output of first iteration machine outliner.
llc -march=arm64 -run-pass=machine-outliner -machine-outliner-reruns=0 --simplify-mir -verify-machineinstrs build/example.mir -o build/example.outlined.mir0

The implicit use of $x0 for outlined function OUTLINED_FUNCTION_1 is missing in this case. What we should do is to check whether implict-def and implict use of $x0 are in the same instruction or not. If so, we should ignore the implict-def. So the fix does serve this purpose.

before:

$x1 = MOVZXi 0, 0
BL @needx0, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit-def $sp, implicit-def $x0
renamable $w0 = nsw ADDWri renamable $w0, 2, 0, implicit killed $x0

After:

frame-setup CFI_INSTRUCTION offset $w29, -16 
BL @OUTLINED_FUNCTION_1, implicit-def $lr, implicit $sp, implicit-def $lr, implicit-def $sp, implicit-def $x0, implicit-def $x1, implicit $sp
renamable $x0 = nsw ADDXri killed renamable $x0, 1, 0

name: OUTLINED_FUNCTION_1

body: |

bb.0:
  liveins: $d15, $x19, $x20, $x21, $x22, $x23, $x24, $x25, $x26, $x27, $x28, $d8, $d9, $d10, $d11, $d12, $d13, $d14, $x0
 
  $x1 = MOVZXi 0, 0
  TCRETURNdi @needx0, 0, implicit $sp

[jinlin]

llvm/test/CodeGen/AArch64/machine-outliner-side-effect-2.mir

20–21

Why do you need to change this test file? With this fix, $x0 should be marked as use.

[DianQK]

remove unnecessary contents

[DianQK]

In D112911#3128737, @jinlin wrote:

Here is the output of first iteration machine outliner.
llc -march=arm64 -run-pass=machine-outliner -machine-outliner-reruns=0 --simplify-mir -verify-machineinstrs build/example.mir -o build/example.outlined.mir0

The implicit use of $x0 for outlined function OUTLINED_FUNCTION_1 is missing in this case. What we should do is to check whether implict-def and implict use of $x0 are in the same instruction or not. If so, we should ignore the implict-def. So the fix does serve this purpose.

before:

$x1 = MOVZXi 0, 0
BL @needx0, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit-def $sp, implicit-def $x0
renamable $w0 = nsw ADDWri renamable $w0, 2, 0, implicit killed $x0

After:

frame-setup CFI_INSTRUCTION offset $w29, -16 
BL @OUTLINED_FUNCTION_1, implicit-def $lr, implicit $sp, implicit-def $lr, implicit-def $sp, implicit-def $x0, implicit-def $x1, implicit $sp
renamable $x0 = nsw ADDXri killed renamable $x0, 1, 0

name: OUTLINED_FUNCTION_1

body: |

bb.0:
  liveins: $d15, $x19, $x20, $x21, $x22, $x23, $x24, $x25, $x26, $x27, $x28, $d8, $d9, $d10, $d11, $d12, $d13, $d14, $x0
 
  $x1 = MOVZXi 0, 0
  TCRETURNdi @needx0, 0, implicit $sp

Yes, we should do is to check whether implict-def and implict use of $x0 are in the same instruction or not.

llvm/test/CodeGen/AArch64/machine-outliner-side-effect-2.mir

20–21

I wanted to show that this has nothing to do with the dead attribute, which is unnecessary and has been removed.

20–21

Why do you need to change this test file? With this fix, $x0 should be marked as use.

[jinlin]

I have got your point. Please still keep your changes in file machine-outliner-side-effect-2.mir. Please update the comment in that file to state that the case of implict-def and implict use of $x0 in the same instruction are handled correctly.

[DianQK]

update machine-outliner-side-effect-2.mir

[jinlin]

This comment was removed by jinlin.

[DianQK]

Many thanks for your review @jinlin. I don’t have commit access, can you land this patch for me? Please use “DianQK [e-mail]” to commit the change.

[DianQK]

rebase the patch to make sure everything is based on an up-to-date origin/main.

llvm/lib/CodeGen/MachineOutliner.cpp

 //===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
for (Candidate &C : OF.Candidates) {
         // implicit Last inst in outlined range  <-- def to the call
         // instruction. Also remove call site information for outlined block
         // of code. The exposed uses need to be copied in the outlined range.
         for (MachineBasicBlock::reverse_iterator
                  Iter = EndIt.getReverse(),
                  Last = std::next(CallInst.getReverse());
              Iter != Last; Iter++) {
           MachineInstr *MI = &*Iter;
+          SmallSet<Register, 2> InstrUseRegs;
           for (MachineOperand &MOP : MI->operands()) {
             // Skip over anything that isn't a register.
             if (!MOP.isReg())
               continue;
 
             if (MOP.isDef()) {
               // Introduce DefRegs set to skip the redundant register.
               DefRegs.insert(MOP.getReg());
-              if (!MOP.isDead() && UseRegs.count(MOP.getReg()))
+              if (UseRegs.count(MOP.getReg()) &&
+                  !InstrUseRegs.count(MOP.getReg()))
                 // Since the regiester is modeled as defined,
                 // it is not necessary to be put in use register set.
                 UseRegs.erase(MOP.getReg());
             } else if (!MOP.isUndef()) {
               // Any register which is not undefined should
               // be put in the use register set.
               UseRegs.insert(MOP.getReg());
+              InstrUseRegs.insert(MOP.getReg());
             }
           }
           if (MI->isCandidateForCallSiteEntry())
             MI->getMF()->eraseCallSiteInfo(MI);
         }
 
         for (const Register &I : DefRegs)
           // If it's a def, add it to the call instruction.

llvm/test/CodeGen/AArch64/machine-outliner-side-effect-2.mir

 # RUN: llc -mtriple=aarch64 -run-pass=machine-outliner -verify-machineinstrs %s -o - | FileCheck %s
 
-# The test checks whether the compiler updates the side effect of function @OUTLINED_FUNCTION_0 by adding the use of register x0.
+# The test checks whether the compiler updates the side effect of function @OUTLINED_FUNCTION_0
+# when implict-def and implict use of $x0 in the same instruction.
 
 --- |
   declare void @spam() local_unnamed_addr
   define void @bax() optsize minsize noredzone { ret void }
   define void @bay() optsize minsize noredzone { ret void }
   define void @baz() optsize minsize noredzone { ret void }
 ...
 ---
 name:            bax
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x0, $lr
 
     $x1 = ADDXri $sp, 16, 0
-    BL @spam, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit-def $sp, implicit-def dead $x0
+    BL @spam, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit-def $sp, implicit-def $x0
+    renamable $x1 = COPY $x0
 
     RET_ReallyLR
 
 ...
 ---
 name:            bay
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x0, $lr
 
     $x1 = ADDXri $sp, 16, 0
-    BL @spam, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit-def $sp, implicit-def dead $x0
+    BL @spam, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit-def $sp, implicit-def $x0
+    renamable $x2 = COPY $x0
 
     RET_ReallyLR
 
 ...
 ---
 name:            baz
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $x0, $lr
 
     $x1 = ADDXri $sp, 16, 0
-    BL @spam, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit-def $sp, implicit-def dead $x0
+    BL @spam, csr_darwin_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit killed $x1, implicit-def $sp, implicit-def $x0
+    renamable $x3 = COPY $x0
 
     RET_ReallyLR
 
 ...
 
-# CHECK: BL @OUTLINED_FUNCTION_0, {{.*}}, implicit $x0
+# CHECK: BL @OUTLINED_FUNCTION_0, {{.*}}, implicit $x0{{.*}}

llvm/test/CodeGen/AArch64/machine-outliner-side-effect.mir

bb.0:
     $x0 = COPY killed renamable $x20
     BL @spam, csr_aarch64_aapcs, implicit-def dead $lr, implicit $sp, implicit $x0, implicit-def $sp, implicit-def $x0
     renamable $x3 = COPY $x0
 
     RET_ReallyLR
 
 ...
 
-# CHECK: BL @OUTLINED_FUNCTION_0, {{.*}}, implicit $x20, {{.*}}
+# CHECK: BL @OUTLINED_FUNCTION_0, {{.*}}, implicit $x20{{.*}}