Fix interaction of CFI instructions with MachineOutliner.

[efriedma]

Summary

Fix interaction of CFI instructions with MachineOutliner.

1. When checking if a candidate contains a CFI instruction, actually iterate over all of the instructions, instead of stopping halfway through.
2. Make sure copied CFI instructions refer to the correct instruction.

Fixes https://github.com/llvm/llvm-project/issues/55842

[smeenai]

Thank you!

Is it possible or worthwhile to have a test case?

[efriedma]

Should be possible to add a testcase, I think. Testcases are a bit tricky to write, though.

Need to think about the MachineOutliner.cpp change a bit more; it's broken.

I guess if we're tail-calling, and we grab all the CFI instructions, it should be okay to just clone all of them? But that's making me doubt the way CFI instructions are being counted; I don't think it's safe to say that getFrameInstructions().size() is actually the number of CFI instructions in the function. It is if you're writing MIR testcases for MachineOutliner, because of the way serialization works, but I don't think that works in general.

If we fix that check, and fix MachineOutliner.cpp to properly clone the instructions, then I guess everything works? But I'd have to spend a day writing testcases.

[efriedma]

Updated according to my best understanding of how this is supposed to work. Not really confident I'm actually getting this right, but seems like an improvement. Modified some tests to cover the new changes.

[kyulee]

llvm/lib/CodeGen/MachineOutliner.cpp

674–680

I think it's somewhat inefficient by cloning the entire instruction, removing this and then adding one back.
CFIIndex should be reassigned for the new function (because the old function might optimize or shuffle it), so we will create new CFI instruction while adding CFIIndex to the new function. Can we just do this way?

// Don't keep debug information for outlined instructions.
auto DL = DebugLoc();
if (I->isCFIInstruction()) {
  unsigned CFIIndex = I->getOperand(0).getCFIIndex();
  MCCFIInstruction CFI = Instrs[CFIIndex];
  BuildMI(MBB, MBB.end(), DL, TII.get(TargetOpcode::CFI_INSTRUCTION))
       .addCFIIndex(MF.addFrameInst(CFI));
} else {
  MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
  NewMI->dropMemRefs(MF);
  NewMI->setDebugLoc(DL);
  MBB.insert(MBB.end(), NewMI);
}

llvm/lib/Target/AArch64/AArch64InstrInfo.cpp

7016

I think this is a nice catch. We should check the entire instructions of the candidate which will be outlined, instead of looking the range of index to the hashes.

7030

I'm just a bit confused about this code. Are you checking a function with a single block?
Even that, I don't think walking all the instruction in the block adds value -- do you see more outlining or improvement by doing this?
The existing logic that just checks the size of CFIInstructions might be enough conservatively although it might include dead CFIs.
If you see the following logic later, the machine outliner actually outlines a tail case only if CFIs are outlined.

[efriedma]

llvm/lib/CodeGen/MachineOutliner.cpp

674–680

The efficiency difference is unlikely to matter, but sure, this is probably more clear.

llvm/lib/Target/AArch64/AArch64InstrInfo.cpp

7030

Probably the size of CFIInstructions is greater than or equal to the number of CFI instructions in the function (unless we clone a CFI instruction, which probably shouldn't happen).

That said, I don't really want to trust the size of CFIInstructions. Any heuristic that depends on it will be very confusing to anyone looking at MIR dumps (since we print CFI instructions inline).

The single basic block restriction isn't strictly necessary; I'll try to come up with a better way to write this.

[kyulee]

llvm/lib/Target/AArch64/AArch64InstrInfo.cpp

7030

Probably the size of CFIInstructions is greater than or equal to the number of CFI instructions in the function

I think this is conservatively safe to use it in this context if that happens -- we're likely to bail-out outlining due to mis-matches in # of CFI instructions. I wonder how many cases we have, in practice.

Any heuristic that depends on it will be very confusing to anyone looking at MIR dumps (since we print CFI instructions inline).

Can you elaborate it? Probably I don't understand the problem clearly. Let say we have N as CFIInstructions' size while there are actually M CFI instructions in the function body (M <= N). Didn't M instances still have valid CFI Index, assigned to the function? Do you have an example to show this is the problem?

[efriedma]

llvm/lib/Target/AArch64/AArch64InstrInfo.cpp

7030

See the changed llvm/test/CodeGen/AArch64/machine-outliner-cfi-tail.mir ; without this change, we don't transform.

[kyulee]

llvm/test/CodeGen/AArch64/machine-outliner-cfi-tail.mir

37 ↗

(On Diff #433932)

I understand this will make a difference to outline it if we can prove this is dead and thus safely ignore it -- probably at the cost of walking IRs or blocks for all parent functions of candidates.
Do you see this case often in practice or is it just synthesized for this testing purpose?
Even if that is the case, I think this is irrelevant for this fix, and probably suggest another patch as an optimization (or improving it).

[efriedma]

Address review comments.

I don't have any evidence the CFIInstructions.size() thing can cause a miscompile, so leaving out for now.

[kyulee]

Thanks for fixing this!
LGTM.

[smeenai]

LGTM, thank you!

llvm/lib/CodeGen/MachineVerifier.cpp

2216

Unfortunately, this doesn't appear to be enough to catch this issue. If I undo the other changes in this diff and remove the assertion I added in D126919, the test case from https://github.com/llvm/llvm-project/issues/55842 still crashes with an unexpected instruction error instead of hitting this check.

[smeenai]

llvm/lib/CodeGen/MachineVerifier.cpp

2216

NVM, this was PEBKAC – I forgot to pass -verify-machineinstrs to llc. I imagine Clang does that automatically.

[efriedma]

llvm/lib/CodeGen/MachineVerifier.cpp

2216

verify-machineinstrs is expensive because it checks after every pass. So it's off by default in all tools.

llvm/lib/CodeGen/MachineOutliner.cpp

MachineFunction *MachineOutliner::createOutlinedFunction(
 
   MachineFunction *OriginalMF = FirstCand.front()->getMF();
   const std::vector<MCCFIInstruction> &Instrs =
       OriginalMF->getFrameInstructions();
   for (auto I = FirstCand.front(), E = std::next(FirstCand.back()); I != E;
        ++I) {
     if (I->isDebugInstr())
       continue;
-    MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
+
+    // Don't keep debug information for outlined instructions.
+    auto DL = DebugLoc();
     if (I->isCFIInstruction()) {
-      unsigned CFIIndex = NewMI->getOperand(0).getCFIIndex();
+      unsigned CFIIndex = I->getOperand(0).getCFIIndex();
       MCCFIInstruction CFI = Instrs[CFIIndex];
-      (void)MF.addFrameInst(CFI);
-    }
+      BuildMI(MBB, MBB.end(), DL, TII.get(TargetOpcode::CFI_INSTRUCTION))
+          .addCFIIndex(MF.addFrameInst(CFI));
+    } else {
+      MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
       NewMI->dropMemRefs(MF);
-
-    // Don't keep debug information for outlined instructions.
-    NewMI->setDebugLoc(DebugLoc());
+      NewMI->setDebugLoc(DL);
       MBB.insert(MBB.end(), NewMI);
     }
+  }
 
   // Set normal properties for a late MachineFunction.
   MF.getProperties().reset(MachineFunctionProperties::Property::IsSSA);
   MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
   MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
   MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
   MF.getRegInfo().freezeReservedRegs(MF);
 

llvm/lib/CodeGen/MachineVerifier.cpp

 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/MC/LaneBitmask.h"
 #include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCDwarf.h"
 #include "llvm/MC/MCInstrDesc.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/MC/MCTargetOptions.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/LowLevelTypeImpl.h"
 #include "llvm/Support/MathExtras.h"
if (LiveStks && LiveStks->hasInterval(MO->getIndex()) &&
       }
       if (stores && !LI.liveAt(Idx.getRegSlot())) {
         report("Instruction stores to dead spill slot", MO, MONum);
         errs() << "Live stack: " << LI << '\n';
       }
     }
     break;
 
+  case MachineOperand::MO_CFIIndex:
+    if (MO->getCFIIndex() >= MF->getFrameInstructions().size())
+      report("CFI instruction has invalid index", MO, MONum);
+    break;
+
   default:
     break;
   }
 }
 
 void MachineVerifier::checkLivenessAtUse(const MachineOperand *MO,
                                          unsigned MONum, SlotIndex UseIdx,
                                          const LiveRange &LR,

llvm/lib/Target/AArch64/AArch64InstrInfo.cpp

outliner::OutlinedFunction AArch64InstrInfo::getOutliningCandidateInfo(
 
   bool HasBTI = any_of(RepeatedSequenceLocs, [](outliner::Candidate &C) {
     return C.getMF()->getInfo<AArch64FunctionInfo>()->branchTargetEnforcement();
   });
 
   // We check to see if CFI Instructions are present, and if they are
   // we find the number of CFI Instructions in the candidates.
   unsigned CFICount = 0;
-  MachineBasicBlock::iterator MBBI = RepeatedSequenceLocs[0].front();
-  for (unsigned Loc = RepeatedSequenceLocs[0].getStartIdx();
-       Loc < RepeatedSequenceLocs[0].getEndIdx() + 1; Loc++) {
-    if (MBBI->isCFIInstruction())
+  for (auto &I : make_range(RepeatedSequenceLocs[0].front(),
+                            std::next(RepeatedSequenceLocs[0].back()))) {
+    if (I.isCFIInstruction())
       CFICount++;
-    MBBI++;
   }
 
   // We compare the number of found CFI Instructions to  the number of CFI
   // instructions in the parent function for each candidate.  We must check this
   // since if we outline one of the CFI instructions in a function, we have to
   // outline them all for correctness. If we do not, the address offsets will be
   // incorrect between the two sections of the program.
   for (outliner::Candidate &C : RepeatedSequenceLocs) {
     std::vector<MCCFIInstruction> CFIInstructions =
         C.getMF()->getFrameInstructions();
 
     if (CFICount > 0 && CFICount != CFIInstructions.size())
       return outliner::OutlinedFunction();
   }
 
   // Returns true if an instructions is safe to fix up, false otherwise.
   auto IsSafeToFixup = [this, &TRI](MachineInstr &MI) {
     if (MI.isCall())
       return true;
 

llvm/lib/Target/X86/X86InstrInfo.cpp

unsigned SequenceSize =
                         if (MI.isDebugInstr() || MI.isKill())
                           return Sum;
                         return Sum + 1;
                       });
 
   // We check to see if CFI Instructions are present, and if they are
   // we find the number of CFI Instructions in the candidates.
   unsigned CFICount = 0;
-  MachineBasicBlock::iterator MBBI = RepeatedSequenceLocs[0].front();
-  for (unsigned Loc = RepeatedSequenceLocs[0].getStartIdx();
-       Loc < RepeatedSequenceLocs[0].getEndIdx() + 1; Loc++) {
-    if (MBBI->isCFIInstruction())
+  for (auto &I : make_range(RepeatedSequenceLocs[0].front(),
+                            std::next(RepeatedSequenceLocs[0].back()))) {
+    if (I.isCFIInstruction())
       CFICount++;
-    MBBI++;
   }
 
   // We compare the number of found CFI Instructions to  the number of CFI
   // instructions in the parent function for each candidate.  We must check this
   // since if we outline one of the CFI instructions in a function, we have to
   // outline them all for correctness. If we do not, the address offsets will be
   // incorrect between the two sections of the program.
   for (outliner::Candidate &C : RepeatedSequenceLocs) {

llvm/test/CodeGen/AArch64/machine-outliner-cfi.mir

 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
-# RUN: llc -mtriple=aarch64-apple-unknown -run-pass=machine-outliner -verify-machineinstrs %s -o - | FileCheck %s
+# RUN: llc -mtriple=aarch64-apple-unknown -run-pass=machine-outliner -verify-machineinstrs -enable-machine-outliner=always %s -o - | FileCheck %s
 
 # Outlining CFI instructions is unsafe if it is not tail called, but otherwise,
 # it requires fixups. Show that we don't include CFI instructions in non
-# tail call outlined sequences right now.
+# tail call outlined sequences right now. Show that we count CFI instructions
+# correctly in the presence of debug info.
 
 --- |
   define void @foo() #0 { ret void }
   define void @bar() #0 { ret void }
   define void @baz() #0 { ret void }
   attributes #0 = { noredzone }
+
 ...
 ---
 name:            foo
 tracksRegLiveness: true
 body:             |
   bb.0:
   liveins: $lr
     ; CHECK-LABEL: name: foo
     ; CHECK: liveins: $lr
-    ; CHECK: $w9 = ORRWri $wzr, 1
-    ; CHECK: $w10 = ORRWri $wzr, 2
-    ; CHECK: $w11 = ORRWri $wzr, 3
-    ; CHECK: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
-    ; CHECK: $w20 = ORRWri $wzr, 1
-    ; CHECK: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: $w9 = ORRWri $wzr, 1
+    ; CHECK-NEXT: $w10 = ORRWri $wzr, 2
+    ; CHECK-NEXT: $w11 = ORRWri $wzr, 3
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
+    ; CHECK-NEXT: $w20 = ORRWri $wzr, 1
+    ; CHECK-NEXT: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
     $w9 = ORRWri $wzr, 1
     $w10 = ORRWri $wzr, 2
     $w11 = ORRWri $wzr, 3
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
     frame-setup CFI_INSTRUCTION def_cfa $w29, 16
     $w20 = ORRWri $wzr, 1
     $w12 = ORRWri $wzr, 1
     $w13 = ORRWri $wzr, 2
     $w14 = ORRWri $wzr, 3
     $w15 = ORRWri $wzr, 4
     RET undef $lr
 ...
 ---
 name:            bar
 tracksRegLiveness: true
 body:             |
   bb.0:
   liveins: $lr
     ; CHECK-LABEL: name: bar
     ; CHECK: liveins: $lr
-    ; CHECK: $w9 = ORRWri $wzr, 1
-    ; CHECK: $w10 = ORRWri $wzr, 2
-    ; CHECK: $w11 = ORRWri $wzr, 3
-    ; CHECK: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
-    ; CHECK: $w21 = ORRWri $wzr, 1
-    ; CHECK: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: $w9 = ORRWri $wzr, 1
+    ; CHECK-NEXT: $w10 = ORRWri $wzr, 2
+    ; CHECK-NEXT: $w11 = ORRWri $wzr, 3
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
+    ; CHECK-NEXT: $w21 = ORRWri $wzr, 1
+    ; CHECK-NEXT: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
     $w9 = ORRWri $wzr, 1
     $w10 = ORRWri $wzr, 2
     $w11 = ORRWri $wzr, 3
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
     frame-setup CFI_INSTRUCTION def_cfa $w29, 16
     $w21 = ORRWri $wzr, 1
     $w12 = ORRWri $wzr, 1
     $w13 = ORRWri $wzr, 2
     $w14 = ORRWri $wzr, 3
     $w15 = ORRWri $wzr, 4
     RET undef $lr
 ...
 ---
 name:            baz
 tracksRegLiveness: true
 body:             |
   bb.0:
   liveins: $lr
     ; CHECK-LABEL: name: baz
     ; CHECK: liveins: $lr
-    ; CHECK: $w9 = ORRWri $wzr, 1
-    ; CHECK: $w10 = ORRWri $wzr, 2
-    ; CHECK: $w11 = ORRWri $wzr, 3
-    ; CHECK: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
-    ; CHECK: $w22 = ORRWri $wzr, 1
-    ; CHECK: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: $w9 = ORRWri $wzr, 1
+    ; CHECK-NEXT: $w10 = ORRWri $wzr, 2
+    ; CHECK-NEXT: $w11 = ORRWri $wzr, 3
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
+    ; CHECK-NEXT: $w22 = ORRWri $wzr, 1
+    ; CHECK-NEXT: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
     $w9 = ORRWri $wzr, 1
     $w10 = ORRWri $wzr, 2
     $w11 = ORRWri $wzr, 3
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
     frame-setup CFI_INSTRUCTION def_cfa $w29, 16
     $w22 = ORRWri $wzr, 1
     $w12 = ORRWri $wzr, 1
     $w13 = ORRWri $wzr, 2
     $w14 = ORRWri $wzr, 3
     $w15 = ORRWri $wzr, 4
     RET undef $lr