MachineFrameInfo: Simplify pristine register calculation.

[MatzeB]

Summary

About pristine regsiters:
Pristine registers "hold a value that is useless to the current
function, but that must be preserved - they are callee saved registers
that have not been saved." This concept saves compile time as it frees
the prologue/epilogue inserter from adding every such register to every
basic blocks live-in list.

However the current code in getPristineRegs is formulated in a
complicated way: Inside the function prologue and epilogue all callee
saves are considered pristine, while in the rest of the code only the
non-saved ones are considered pristine. This requires logic to
differentiate between prologue/epilogue and the rest and in the presence
of shrink-wrapping this even becomes complicated/expensive. It's also
unnecessary because the prologue epilogue inserters already mark
callee-save registers that are saved/restores properly in the respective
blocks in the prologue/epilogue (see updateLiveness() in
PrologueEpilogueInserter.cpp). So only declaring non-saved/restored
callee saved registers as pristine just works.

[qcolombet]

Hi Matthias,

It's also unnecessary because the prologue epilogue inserters already mark callee-save registers that are saved/restores properly in the respective blocks in the prologue/epilogue.

This assumes that everybody uses the live-in information.

That being said, the new semantic works for me. Just make sure to send a “Heads-up” email to llvm-dev to emphasize the change for out-of-tree targets.

The bottom line LGTM.

Thanks,
-Quentin

[MatzeB]

Thanks for the review.

I think heads-up message is not necessary: The previous semantics just allowed us to have fewer registers in the live-in sets in theory. There is no change for code that does not rely on live-in sets. For code relying on the live-in sets we won't have a change as well because the live-in sets are not changed by this commit.

llvm/trunk/include/llvm/CodeGen/MachineFrameInfo.h

class MachineFrameInfo {
   /// stack objects like arguments so we can't treat them as immutable.
   bool HasTailCall;
 
   /// Not null, if shrink-wrapping found a better place for the prologue.
   MachineBasicBlock *Save;
   /// Not null, if shrink-wrapping found a better place for the epilogue.
   MachineBasicBlock *Restore;
 
-  /// Check if it exists a path from \p MBB leading to the basic
-  /// block with a SavePoint (a.k.a. prologue).
-  bool isBeforeSavePoint(const MachineFunction &MF,
-                         const MachineBasicBlock &MBB) const;
-
 public:
   explicit MachineFrameInfo(unsigned StackAlign, bool isStackRealign,
                             bool RealignOpt)
       : StackAlignment(StackAlign), StackRealignable(isStackRealign),
         RealignOption(RealignOpt) {
     StackSize = NumFixedObjects = OffsetAdjustment = MaxAlignment = 0;
     HasVarSizedObjects = false;
     FrameAddressTaken = false;
public:
 
   void setCalleeSavedInfoValid(bool v) { CSIValid = v; }
 
   MachineBasicBlock *getSavePoint() const { return Save; }
   void setSavePoint(MachineBasicBlock *NewSave) { Save = NewSave; }
   MachineBasicBlock *getRestorePoint() const { return Restore; }
   void setRestorePoint(MachineBasicBlock *NewRestore) { Restore = NewRestore; }
 
-  /// getPristineRegs - Return a set of physical registers that are pristine on
-  /// entry to the MBB.
+  /// Return a set of physical registers that are pristine.
   ///
   /// Pristine registers hold a value that is useless to the current function,
-  /// but that must be preserved - they are callee saved registers that have not
-  /// been saved yet.
+  /// but that must be preserved - they are callee saved registers that are not
+  /// saved.
   ///
   /// Before the PrologueEpilogueInserter has placed the CSR spill code, this
   /// method always returns an empty set.
-  BitVector getPristineRegs(const MachineBasicBlock *MBB) const;
+  BitVector getPristineRegs(const MachineFunction &MF) const;
 
   /// print - Used by the MachineFunction printer to print information about
   /// stack objects. Implemented in MachineFunction.cpp
   ///
   void print(const MachineFunction &MF, raw_ostream &OS) const;
 
   /// dump - Print the function to stderr.
   void dump(const MachineFunction &MF) const;
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/lib/CodeGen/AggressiveAntiDepBreaker.cpp

for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
         DefIndices[Reg] = ~0u;
       }
     }
 
   // Mark live-out callee-saved registers. In a return block this is
   // all callee-saved registers. In non-return this is any
   // callee-saved register that is not saved in the prolog.
   const MachineFrameInfo *MFI = MF.getFrameInfo();
-  BitVector Pristine = MFI->getPristineRegs(BB);
+  BitVector Pristine = MFI->getPristineRegs(MF);
   for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) {
     unsigned Reg = *I;
     if (!IsReturnBlock && !Pristine.test(Reg)) continue;
     for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
       unsigned AliasReg = *AI;
       State->UnionGroups(AliasReg, 0);
       KillIndices[AliasReg] = BB->size();
       DefIndices[AliasReg] = ~0u;

llvm/trunk/lib/CodeGen/CriticalAntiDepBreaker.cpp

for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
         DefIndices[Reg] = ~0u;
       }
     }
 
   // Mark live-out callee-saved registers. In a return block this is
   // all callee-saved registers. In non-return this is any
   // callee-saved register that is not saved in the prolog.
   const MachineFrameInfo *MFI = MF.getFrameInfo();
-  BitVector Pristine = MFI->getPristineRegs(BB);
+  BitVector Pristine = MFI->getPristineRegs(MF);
   for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) {
     if (!IsReturnBlock && !Pristine.test(*I)) continue;
     for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) {
       unsigned Reg = *AI;
       Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1);
       KillIndices[Reg] = BBSize;
       DefIndices[Reg] = ~0u;
     }

llvm/trunk/lib/CodeGen/MachineFunction.cpp

int MachineFrameInfo::CreateFixedSpillStackObject(uint64_t Size,
   Objects.insert(Objects.begin(), StackObject(Size, Align, SPOffset,
                                               /*Immutable*/ true,
                                               /*isSS*/ true,
                                               /*Alloca*/ nullptr,
                                               /*isAliased*/ false));
   return -++NumFixedObjects;
 }
 
-BitVector
-MachineFrameInfo::getPristineRegs(const MachineBasicBlock *MBB) const {
-  assert(MBB && "MBB must be valid");
-  const MachineFunction *MF = MBB->getParent();
-  assert(MF && "MBB must be part of a MachineFunction");
-  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
+BitVector MachineFrameInfo::getPristineRegs(const MachineFunction &MF) const {
+  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
   BitVector BV(TRI->getNumRegs());
 
   // Before CSI is calculated, no registers are considered pristine. They can be
   // freely used and PEI will make sure they are saved.
   if (!isCalleeSavedInfoValid())
     return BV;
 
-  for (const MCPhysReg *CSR = TRI->getCalleeSavedRegs(MF); CSR && *CSR; ++CSR)
+  for (const MCPhysReg *CSR = TRI->getCalleeSavedRegs(&MF); CSR && *CSR; ++CSR)
     BV.set(*CSR);
 
-  // Each MBB before the save point has all CSRs pristine.
-  if (isBeforeSavePoint(*MF, *MBB))
-    return BV;
-
-  // On other MBBs the saved CSRs are not pristine.
+  // Saved CSRs are not pristine.
   const std::vector<CalleeSavedInfo> &CSI = getCalleeSavedInfo();
   for (std::vector<CalleeSavedInfo>::const_iterator I = CSI.begin(),
          E = CSI.end(); I != E; ++I)
     BV.reset(I->getReg());
 
   return BV;
 }
 
-// Note: We could use some sort of caching mecanism, but we lack the ability
-// to know when the cache is invalid, i.e., the CFG changed.
-// Assuming we have that, we can simply compute all the set of MBBs
-// that are before the save point.
-bool MachineFrameInfo::isBeforeSavePoint(const MachineFunction &MF,
-                                         const MachineBasicBlock &MBB) const {
-  // Early exit if shrink-wrapping did not kick.
-  if (!Save)
-    return &MBB == &MF.front();
-
-  // Starting from MBB, check if there is a path leading to Save that do
-  // not cross Restore.
-  SmallPtrSet<const MachineBasicBlock *, 8> Visited;
-  SmallVector<const MachineBasicBlock *, 8> WorkList;
-  WorkList.push_back(&MBB);
-  Visited.insert(&MBB);
-  do {
-    const MachineBasicBlock *CurBB = WorkList.pop_back_val();
-    // By construction, the region that is after the save point is
-    // dominated by the Save and post-dominated by the Restore.
-    // If we do not reach Restore and still reach Save, this
-    // means MBB is before Save.
-    if (CurBB == Save)
-      return true;
-    if (CurBB == Restore)
-      continue;
-    // Enqueue all the successors not already visited.
-    for (MachineBasicBlock *SuccBB : CurBB->successors())
-      if (Visited.insert(SuccBB).second)
-        WorkList.push_back(SuccBB);
-  } while (!WorkList.empty());
-  return false;
-}
-
 unsigned MachineFrameInfo::estimateStackSize(const MachineFunction &MF) const {
   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
   const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo();
   unsigned MaxAlign = getMaxAlignment();
   int Offset = 0;
 
   // This code is very, very similar to PEI::calculateFrameObjectOffsets().
   // It really should be refactored to share code. Until then, changes

llvm/trunk/lib/CodeGen/MachineVerifier.cpp

for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
     for (MCSubRegIterator SubRegs(*I, TRI, /*IncludeSelf=*/true);
          SubRegs.isValid(); ++SubRegs)
       regsLive.insert(*SubRegs);
   }
   regsLiveInButUnused = regsLive;
 
   const MachineFrameInfo *MFI = MF->getFrameInfo();
   assert(MFI && "Function has no frame info");
-  BitVector PR = MFI->getPristineRegs(MBB);
+  BitVector PR = MFI->getPristineRegs(*MF);
   for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
     for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
          SubRegs.isValid(); ++SubRegs)
       regsLive.insert(*SubRegs);
   }
 
   regsKilled.clear();
   regsDefined.clear();

llvm/trunk/lib/CodeGen/RegisterScavenging.cpp

if (!MBB)
     return;
 
   // Live-in registers are in use.
   for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
          E = MBB->livein_end(); I != E; ++I)
     setRegUsed(*I);
 
   // Pristine CSRs are also unavailable.
-  BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB);
+  const MachineFunction &MF = *MBB->getParent();
+  BitVector PR = MF.getFrameInfo()->getPristineRegs(MF);
   for (int I = PR.find_first(); I>0; I = PR.find_next(I))
     setRegUsed(I);
 }
 
 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
   MachineFunction &MF = *mbb->getParent();
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();