[Greedy RA] Do not split interval on tied-def

[skatkov]

Summary

If end of interval for overlap utility is a use which has tied-def we
should not split interval on this instruction due to in this case use
and def may have different registers and it breaks tied-def property.

[qcolombet]

Could you add dedicated test case?

It is unclear from the test change that this is covering what you've just added.

[reames]

llvm/test/CodeGen/X86/statepoint-invoke-ra1.ll

2

Please use an autogen test here to check the output and put a comment here explaining the two things this is testing. I think the comment will probably address Quentin's concerns as well, though he should confirm.

[skatkov]

Update with mir test

[skatkov]

llvm/lib/CodeGen/SplitKit.cpp

822

Generally, we cannot set end of OpenIdx to End if it is a statepoint instruction and register represents tied-def on this instructions.

Setting end we split tied-use and tied-def in different live intervals allowing to assign them to different registers breaking the tied-ness property.

[reames]

LGTM w/comment addressed

llvm/test/CodeGen/X86/statepoint-invoke-ra.mir

3 ↗

(On Diff #341452)

This comment is now stale, please update.

[skatkov]

Test description is updated.

[skatkov]

Landed as a part of https://reviews.llvm.org/D101150.

llvm/lib/CodeGen/SplitKit.h

public:
   SlotIndex leaveIntvBefore(SlotIndex Idx);
 
   /// leaveIntvAtTop - Leave the interval at the top of MBB.
   /// Add liveness from the MBB top to the copy.
   /// Return the end of the live range.
   SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB);
 
   /// overlapIntv - Indicate that all instructions in range should use the open
-  /// interval, but also let the complement interval be live.
+  /// interval if End does not have tied-def usage of the register and in this
+  /// case compliment interval is used. Let the complement interval be live.
   ///
   /// This doubles the register pressure, but is sometimes required to deal with
   /// register uses after the last valid split point.
   ///
   /// The Start index should be a return value from a leaveIntv* call, and End
   /// should be in the same basic block. The parent interval must have the same
   /// value across the range.
   ///

llvm/lib/CodeGen/SplitKit.cpp

SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
 
   VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
                               MBB.SkipPHIsLabelsAndDebug(MBB.begin()));
   RegAssign.insert(Start, VNI->def, OpenIdx);
   LLVM_DEBUG(dump());
   return VNI->def;
 }
 
+static bool hasTiedUseOf(MachineInstr &MI, unsigned Reg) {
+  return any_of(MI.defs(), [Reg](const MachineOperand &MO) {
+    return MO.isReg() && MO.isTied() && MO.getReg() == Reg;
+  });
+}
+
 void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
   assert(OpenIdx && "openIntv not called before overlapIntv");
   const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
   assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
          "Parent changes value in extended range");
   assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
          "Range cannot span basic blocks");
 
   // The complement interval will be extended as needed by LICalc.extend().
   if (ParentVNI)
     forceRecompute(0, *ParentVNI);
+
+  // If the last use is tied to a def, we can't mark it as live for the
+  // interval which includes only the use.  That would cause the tied pair
+  // to end up in two different intervals.
+  if (auto *MI = LIS.getInstructionFromIndex(End))
+    if (hasTiedUseOf(*MI, Edit->getReg())) {
+      LLVM_DEBUG(dbgs() << "skip overlap due to tied def at end\n");
+      return;
+    }
+
   LLVM_DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
   RegAssign.insert(Start, End, OpenIdx);
   LLVM_DEBUG(dump());
 }
 
 //===----------------------------------------------------------------------===//
 //                                  Spill modes
 //===----------------------------------------------------------------------===//
 
 void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {

llvm/test/CodeGen/X86/statepoint-invoke-ra1.ll

 ; REQUIRES: asserts
-; RUN: not  --crash llc -o /dev/null %s -max-registers-for-gc-values=15 -use-registers-for-gc-values-in-landing-pad=true -verify-regalloc 2>&1 | FileCheck %s
+; RUN: llc -o - %s -max-registers-for-gc-values=15 -use-registers-for-gc-values-in-landing-pad=true -verify-regalloc 2>&1 | FileCheck %s
 
-; The test checks the verification catch the case when RA splits live interval in the
-; way the def is located after invoke statepoint while use is in landing pad.
-
-; CHECK: *** Bad machine code: Two-address instruction operands must be identical ***
+; CHECK-NOT: *** Bad machine code
+; CHECK: wombat
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @wombat(i8 addrspace(1)* %arg, i32 %arg1, i32 addrspace(1)* %arg2) gc "statepoint-example" personality i32* ()* @widget {
 bb:
   %tmp = load i8 addrspace(1)*, i8 addrspace(1)* addrspace(1)* null, align 8
   %tmp3 = load i32, i32 addrspace(1)* null, align 4