RegAlloc: do not consider liveins to EH-pad successors as liveout.

[t.p.northover]

Summary

RegAllocFast is looking at the successors' liveins to determine the initial liveouts of the block being allocated. Unfortunately if the block ends with an invoke, one of these is the landingpad which really gets its liveins from the runtime, not us.

This leads to registers being reserved in the block until they're fully clobbered by an instruction in reverse-order. In particularly tight situations on x86 (base pointer, lots of arg registers, and al used for varargs purposes, a _NOREX regclass being allocated) we can end up with nothing spillable and fail to allocate.

Also, it turns out that RegUnit 0 is valid, which threw me for a while when I was relying on dumpState and AH was nowhere to be found. So this fixes the dumper too.

[qcolombet]

LGTM

[t.p.northover]

Thanks, committed as 438a63e13bf8.

[t.p.northover]

And now I've reverted it. I was musing some more and it occurred that some values can come from this block (e.g. any SSA value we produce except from the call). It's only the landingpad defs that are from the runtime. I'll work on a more targeted patch.

[qcolombet]

I was musing some more and it occurred that some values can come from this block

Good point, I should have thought of this!

[t.p.northover]

Right, second try. I think the TargetLowering functions return 0 (which is never a real register) when they're not set, so this should do the trick.

[efriedma]

llvm/lib/CodeGen/RegAllocFast.cpp

1460

Calling getExceptionPointerRegister() directly from fast regalloc seems hacky. We don't want to copy-paste this code everywhere that cares about physical register live-outs.

[t.p.northover]

llvm/lib/CodeGen/RegAllocFast.cpp

1460

I could add a MachineBasicBlock::liveouts that does the iteration. Simplest would probably be to return a SmallSet because of the potential issue with duplicates, but that doesn't quite fit with the liveins iterator-based interface. Otherwise it's probably an iterator adapter containing that SmallSet.

[efriedma]

llvm/lib/CodeGen/RegAllocFast.cpp

1460

Probably most places that would use this can handle duplicates, so it would be fine to just implement an iterator over the raw list including duplicates.

I spent a bit of time trying to come up with some way to represent this that's a bit cleaner, but I didn't really have any good ideas. Maybe we could partition the "liveins" list in MachineBasicBlock to distinguish between registers that are live-out from a predecessor, and ones that are set by the unwinder? The advantages would just be that we don't have to query TLI, and MIR dumps would be a bit easier to understand.

[t.p.northover]

Moved the iteration logic into a new MachineBasicBlock::livout_iterator, fairly ugly but not terrible.

[t.p.northover]

llvm/lib/CodeGen/RegAllocFast.cpp

1460

Probably most places that would use this can handle duplicates, so it would be fine to just implement an iterator over the raw list including duplicates.

I suppose so, there may well be subregisters or overlapping ones floating about in the list anyway.

Maybe we could partition the "liveins" list in MachineBasicBlock to distinguish between registers that are live-out from a predecessor, and ones that are set by the unwinder?

I can't really think of a place that would be a useful distinction except when backcalculating liveouts as here, so I'm still inclined to keep the logic here.

[t.p.northover]

Hang on, this one isn't quite right. Back with a revision soon.

[t.p.northover]

Fixed the iterator logic to actually advance the BB, and skip over exception registers during construction. Tests had been infinite looping before, making it look a lot greener than it was.

[efriedma]

LGTM

[t.p.northover]

Switch to -1 as a sentinel for when the caller pops the stack (i.e. C calling conv situation).

[t.p.northover]

Ooops, uploaded a diff to wrong review. I'll put the diff back to how it was in case anyone finds this later and gets confused.

What I meant to say here was thanks! I've committed it as c1dc267258e0.

llvm/include/llvm/CodeGen/MachineBasicBlock.h

#endif
   bool            livein_empty() const { return LiveIns.empty(); }
   iterator_range<livein_iterator> liveins() const {
     return make_range(livein_begin(), livein_end());
   }
 
   /// Remove entry from the livein set and return iterator to the next.
   livein_iterator removeLiveIn(livein_iterator I);
 
+  class liveout_iterator {
+  public:
+    using iterator_category = std::input_iterator_tag;
+    using difference_type = std::ptrdiff_t;
+    using value_type = RegisterMaskPair;
+    using pointer = const RegisterMaskPair *;
+    using reference = const RegisterMaskPair &;
+
+    liveout_iterator(const MachineBasicBlock &MBB, MCPhysReg ExceptionPointer,
+                     MCPhysReg ExceptionSelector, bool End)
+        : ExceptionPointer(ExceptionPointer),
+          ExceptionSelector(ExceptionSelector), BlockI(MBB.succ_begin()),
+          BlockEnd(MBB.succ_end()) {
+      if (End)
+        BlockI = BlockEnd;
+      else if (BlockI != BlockEnd) {
+        LiveRegI = (*BlockI)->livein_begin();
+        if (!advanceToValidPosition())
+          return;
+        if (LiveRegI->PhysReg == ExceptionPointer ||
+            LiveRegI->PhysReg == ExceptionSelector)
+          ++(*this);
+      }
+    }
+
+    liveout_iterator &operator++() {
+      do {
+        ++LiveRegI;
+        if (!advanceToValidPosition())
+          return *this;
+      } while ((*BlockI)->isEHPad() &&
+               (LiveRegI->PhysReg == ExceptionPointer ||
+                LiveRegI->PhysReg == ExceptionSelector));
+      return *this;
+    }
+
+    liveout_iterator operator++(int) {
+      liveout_iterator Tmp = *this;
+      ++(*this);
+      return Tmp;
+    }
+
+    reference operator*() const {
+      return *LiveRegI;
+    }
+
+    pointer operator->() const {
+      return &*LiveRegI;
+    }
+
+    bool operator==(const liveout_iterator &RHS) const {
+      if (BlockI != BlockEnd)
+        return BlockI == RHS.BlockI && LiveRegI == RHS.LiveRegI;
+      return RHS.BlockI == BlockEnd;
+    }
+
+    bool operator!=(const liveout_iterator &RHS) const {
+      return !(*this == RHS);
+    }
+  private:
+    bool advanceToValidPosition() {
+      if (LiveRegI != (*BlockI)->livein_end())
+        return true;
+
+      do {
+        ++BlockI;
+      } while (BlockI != BlockEnd && (*BlockI)->livein_empty());
+      if (BlockI == BlockEnd)
+        return false;
+
+      LiveRegI = (*BlockI)->livein_begin();
+      return true;
+    }
+
+    MCPhysReg ExceptionPointer, ExceptionSelector;
+    const_succ_iterator BlockI;
+    const_succ_iterator BlockEnd;
+    livein_iterator LiveRegI;
+  };
+
+  /// Iterator scanning successor basic blocks' liveins to determine the
+  /// registers potentially live at the end of this block. There may be
+  /// duplicates or overlapping registers in the list returned.
+  liveout_iterator liveout_begin() const;
+  liveout_iterator liveout_end() const {
+    return liveout_iterator(*this, 0, 0, true);
+  }
+  iterator_range<liveout_iterator> liveouts() const {
+    return make_range(liveout_begin(), liveout_end());
+  }
+
   /// Get the clobber mask for the start of this basic block. Funclets use this
   /// to prevent register allocation across funclet transitions.
   const uint32_t *getBeginClobberMask(const TargetRegisterInfo *TRI) const;
 
   /// Get the clobber mask for the end of the basic block.
   /// \see getBeginClobberMask()
   const uint32_t *getEndClobberMask(const TargetRegisterInfo *TRI) const;
 

llvm/lib/CodeGen/MachineBasicBlock.cpp

 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/ModuleSlotTracker.h"
 #include "llvm/MC/MCAsmInfo.h"

 
 MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
   assert(getParent()->getProperties().hasProperty(
       MachineFunctionProperties::Property::TracksLiveness) &&
       "Liveness information is accurate");
   return LiveIns.begin();
 }
 
+MachineBasicBlock::liveout_iterator MachineBasicBlock::liveout_begin() const {
+  const MachineFunction &MF = *getParent();
+  assert(MF.getProperties().hasProperty(
+      MachineFunctionProperties::Property::TracksLiveness) &&
+      "Liveness information is accurate");
+
+  const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();
+  MCPhysReg ExceptionPointer = 0, ExceptionSelector = 0;
+  if (MF.getFunction().hasPersonalityFn()) {
+    auto PersonalityFn = MF.getFunction().getPersonalityFn();
+    ExceptionPointer = TLI.getExceptionPointerRegister(PersonalityFn);
+    ExceptionSelector = TLI.getExceptionSelectorRegister(PersonalityFn);
+  }
+
+  return liveout_iterator(*this, ExceptionPointer, ExceptionSelector, false);
+}
+
 const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold);
 const MBBSectionID
     MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception);

llvm/lib/CodeGen/RegAllocFast.cpp

 
 void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
   this->MBB = &MBB;
   LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
 
   RegUnitStates.assign(TRI->getNumRegUnits(), regFree);
   assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
 
-  for (MachineBasicBlock *Succ : MBB.successors()) {
-    for (const MachineBasicBlock::RegisterMaskPair &LI : Succ->liveins())
-      setPhysRegState(LI.PhysReg, regPreAssigned);
-  }
+  for (auto &LiveReg : MBB.liveouts())
+    setPhysRegState(LiveReg.PhysReg, regPreAssigned);
 
   Coalesced.clear();
 
   // Traverse block in reverse order allocating instructions one by one.
   for (MachineInstr &MI : reverse(MBB)) {
     LLVM_DEBUG(
       dbgs() << "\n>> " << MI << "Regs:";
       dumpState()
     );
 
     // Special handling for debug values. Note that they are not allowed to
     // affect codegen of the other instructions in any way.

llvm/lib/Target/X86/X86ISelLowering.cpp

if (classifyEHPersonality(PersonalityFn) == EHPersonality::CoreCLR)
     return Subtarget.isTarget64BitLP64() ? X86::RDX : X86::EDX;
 
   return Subtarget.isTarget64BitLP64() ? X86::RAX : X86::EAX;
 }
 
 Register X86TargetLowering::getExceptionSelectorRegister(
     const Constant *PersonalityFn) const {
   // Funclet personalities don't use selectors (the runtime does the selection).
-  assert(!isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)));
+  if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
+    return X86::NoRegister;
   return Subtarget.isTarget64BitLP64() ? X86::RDX : X86::EDX;
 }
 
 bool X86TargetLowering::needsFixedCatchObjects() const {
   return Subtarget.isTargetWin64();
 }
 
 SDValue X86TargetLowering::LowerEH_RETURN(SDValue Op, SelectionDAG &DAG) const {

llvm/test/CodeGen/X86/fast-isel-cmp-branch.ll

 }
 
 ; rdar://8337108
 
 ; Fast-isel shouldn't try to look through the compare because it's in a
 ; different basic block, so its operands aren't necessarily exported
 ; for cross-block usage.
 
-; CHECK: movb    %cl, [[OFS:[0-9]*]](%rsp)
+; CHECK: movb    %al, [[OFS:[0-9]*]](%rsp)
 ; CHECK: callq   {{_?}}bar
 ; CHECK: movb    [[OFS]](%rsp), %al
 
 declare void @bar()
 
 define void @foo(i32 %a, i32 %b) nounwind personality i32 (...)* @__gxx_personality_v0 {
 entry:
   %q = add i32 %a, 7

llvm/test/CodeGen/X86/regalloc-tight-invoke.ll

+; RUN: llc -O0 -mtriple=x86_64-apple-darwin %s -o - | FileCheck %s
+declare void @foo(i32, ...)
+
+declare i32 @__gxx_personality_v0(...)
+
+; We were running out of registers for this invoke, because:
+
+;     1. The lshr/and pattern gets matched to a no-REX MOV so that ah/bh/... can
+;        be used instead, cutting available registers for %b.arg down to eax, ebx,
+;        ecx, edx, esi, edi.
+;     2. We have a base pointer taking ebx out of contention.
+;     3. The landingpad block convinced us we should be defining rax here.
+;     3. The al fiddling for the varargs call only noted down that al was spillable,
+;        not ah or hax.
+;
+; So by the time we need to allocate a register for the call all registers are
+; tied up and unspillable.
+
+; CHECK-LABEL: bar:
+; CHECK: xorl %edi, %edi
+; CHECK: movb %dil, {{[0-9]+}}(%rbx)
+; CHECK: movb {{[0-9]+}}(%rbx), %al
+
+define i32 @bar(i32 %a, i32 %b, i32 %c, i32 %d, ...) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+  %mem = alloca i32, i32 %a, align 32   ; Force rbx to be used as a base pointer
+  %b.tmp = lshr i32 %b, 8
+  %b.arg = and i32 %b.tmp, 255
+  invoke void(i32, ...) @foo(i32 42, i32* %mem, i32 %c, i32 %d, i32 %b.arg) to label %success unwind label %fail
+
+success:
+  ret i32 0
+fail:
+  %exc = landingpad { i8*, i32 } cleanup
+  %res = extractvalue { i8*, i32 } %exc, 1
+  ret i32 %res
+}
+
+; CHECK-LABEL: live:
+; CHECK: movl {{%.*}}, %eax
+
+define i32 @live(i32 %a, i32 %b, i32 %c, i32 %d, ...) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+  %mem = alloca i32, i32 %a, align 32   ; Force rbx to be used as a base pointer
+  %b.tmp = lshr i32 %b, 8
+  %b.arg = and i32 %b.tmp, 255
+  invoke void(i32, ...) @foo(i32 42) to label %success unwind label %fail
+
+success:
+  ret i32 0
+fail:
+  %exc = landingpad { i8*, i32 } cleanup
+  %res = extractvalue { i8*, i32 } %exc, 1
+  ret i32 %b.arg
+}