BranchRelaxation: Compute live-ins when splitting a block

[MatzeB]

Summary

Factors out and reuses live-in computation code from BranchFolding.

[arsenm]

LGTM

include/llvm/CodeGen/LivePhysRegs.h

private:
   void addBlockLiveIns(const MachineBasicBlock &MBB);
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) {
   LR.print(OS);
   return OS;
 }
 
+/// Compute the live-in list for \p MBB assuming all of its successors live-in
+/// lists are up-to-date. Uses the given LivePhysReg instance \p LiveRegs; This
+/// is just here to avoid repeated heap allocations when calling this multiple
+/// times in a pass.
+void computeLiveIns(LivePhysRegs &LiveRegs, const TargetRegisterInfo &TRI,
+                    MachineBasicBlock &MBB);
+
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H

include/llvm/CodeGen/MachineBasicBlock.h

void addLiveIn(const RegisterMaskPair &RegMaskPair) {
     LiveIns.push_back(RegMaskPair);
   }
 
   /// Sorts and uniques the LiveIns vector. It can be significantly faster to do
   /// this than repeatedly calling isLiveIn before calling addLiveIn for every
   /// LiveIn insertion.
   void sortUniqueLiveIns();
 
+  /// Clear live in list.
+  void clearLiveIns();
+
   /// Add PhysReg as live in to this block, and ensure that there is a copy of
   /// PhysReg to a virtual register of class RC. Return the virtual register
   /// that is a copy of the live in PhysReg.
   unsigned addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC);
 
   /// Remove the specified register from the live in set.
   void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask = ~0u);
 

lib/CodeGen/BranchFolding.h

private:
     MBFIWrapper &MBBFreqInfo;
     const MachineBranchProbabilityInfo &MBPI;
 
     bool TailMergeBlocks(MachineFunction &MF);
     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
                        MachineBasicBlock* PredBB,
                        unsigned MinCommonTailLength);
     void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
-    void computeLiveIns(MachineBasicBlock &MBB);
     void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
                                  MachineBasicBlock *NewDest);
     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
                                   MachineBasicBlock::iterator BBI1,
                                   const BasicBlock *BB);
     unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
                               MachineBasicBlock *SuccBB,
                               MachineBasicBlock *PredBB);

lib/CodeGen/BranchFolding.cpp

while (I1->isDebugValue()) {
         return TailLen;
       --I1;
     }
     ++I1;
   }
   return TailLen;
 }
 
-void BranchFolder::computeLiveIns(MachineBasicBlock &MBB) {
-  if (!UpdateLiveIns)
-    return;
-
-  LiveRegs.init(*TRI);
-  LiveRegs.addLiveOutsNoPristines(MBB);
-  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
-    LiveRegs.stepBackward(MI);
-
-  for (unsigned Reg : LiveRegs) {
-    // Skip the register if we are about to add one of its super registers.
-    bool ContainsSuperReg = false;
-    for (MCSuperRegIterator SReg(Reg, TRI); SReg.isValid(); ++SReg) {
-      if (LiveRegs.contains(*SReg)) {
-        ContainsSuperReg = true;
-        break;
-      }
-    }
-    if (ContainsSuperReg)
-      continue;
-    MBB.addLiveIn(Reg);
-  }
-}
-
 /// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything
 /// after it, replacing it with an unconditional branch to NewDest.
 void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
                                            MachineBasicBlock *NewDest) {
   TII->ReplaceTailWithBranchTo(OldInst, NewDest);
 
-  computeLiveIns(*NewDest);
+  if (UpdateLiveIns) {
+    NewDest->clearLiveIns();
+    computeLiveIns(LiveRegs, *TRI, *NewDest);
+  }
 
   ++NumTailMerge;
 }
 
 /// SplitMBBAt - Given a machine basic block and an iterator into it, split the
 /// MBB so that the part before the iterator falls into the part starting at the
 /// iterator.  This returns the new MBB.
 MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
   // NewMBB belongs to the same loop as CurMBB.
   if (MLI) 
     if (MachineLoop *ML = MLI->getLoopFor(&CurMBB))
       ML->addBasicBlockToLoop(NewMBB, MLI->getBase());
 
   // NewMBB inherits CurMBB's block frequency.
   MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB));
 
-  computeLiveIns(*NewMBB);
+  if (UpdateLiveIns)
+    computeLiveIns(LiveRegs, *TRI, *NewMBB);
 
   // Add the new block to the funclet.
   const auto &FuncletI = FuncletMembership.find(&CurMBB);
   if (FuncletI != FuncletMembership.end()) {
     auto n = FuncletI->second;
     FuncletMembership[NewMBB] = n;
   }
 

lib/CodeGen/BranchRelaxation.cpp

 //===-- BranchRelaxation.cpp ----------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/RegisterScavenging.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 
unsigned postOffset(const MachineBasicBlock &MBB) const {
       // The alignment of this MBB is larger than the function's alignment, so we
       // can't tell whether or not it will insert nops. Assume that it will.
       return PO + AlignAmt + OffsetToAlignment(PO, AlignAmt);
     }
   };
 
   SmallVector<BasicBlockInfo, 16> BlockInfo;
   std::unique_ptr<RegScavenger> RS;
+  LivePhysRegs LiveRegs;
 
   MachineFunction *MF;
+  const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
 
   bool relaxBranchInstructions();
   void scanFunction();
 
   MachineBasicBlock *createNewBlockAfter(MachineBasicBlock &BB);
 
   MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI,
MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
 
   // Figure out how large the NewMBB is. As the second half of the original
   // block, it may contain a tablejump.
   BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
 
   // All BBOffsets following these blocks must be modified.
   adjustBlockOffsets(*OrigBB);
 
+  // Need to fix live-in lists if we track liveness.
+  if (TRI->trackLivenessAfterRegAlloc(*MF))
+    computeLiveIns(LiveRegs, *TRI, *NewBB);
+
   ++NumSplit;
 
   return NewBB;
 }
 
 /// isBlockInRange - Returns true if the distance between specific MI and
 /// specific BB can fit in MI's displacement field.
 bool BranchRelaxation::isBlockInRange(

 bool BranchRelaxation::relaxBranchInstructions() {
   bool Changed = false;
 
   // Relaxing branches involves creating new basic blocks, so re-eval
   // end() for termination.
   for (MachineFunction::iterator I = MF->begin(); I != MF->end(); ++I) {
     MachineBasicBlock &MBB = *I;
 
-    auto Last = MBB.rbegin();
-    if (Last == MBB.rend()) // Empty block.
+    // Empty block?
+    MachineBasicBlock::iterator Last = MBB.getLastNonDebugInstr();
+    if (Last == MBB.end())
       continue;
 
     // Expand the unconditional branch first if necessary. If there is a
     // conditional branch, this will end up changing the branch destination of
     // it to be over the newly inserted indirect branch block, which may avoid
     // the need to try expanding the conditional branch first, saving an extra
     // jump.
     if (Last->isUnconditionalBranch()) {

 bool BranchRelaxation::runOnMachineFunction(MachineFunction &mf) {
   MF = &mf;
 
   DEBUG(dbgs() << "***** BranchRelaxation *****\n");
 
   const TargetSubtargetInfo &ST = MF->getSubtarget();
   TII = ST.getInstrInfo();
 
-  const TargetRegisterInfo *TRI = ST.getRegisterInfo();
+  TRI = ST.getRegisterInfo();
   if (TRI->trackLivenessAfterRegAlloc(*MF))
     RS.reset(new RegScavenger());
 
   // Renumber all of the machine basic blocks in the function, guaranteeing that
   // the numbers agree with the position of the block in the function.
   MF->RenumberBlocks();
 
   // Do the initial scan of the function, building up information about the

lib/CodeGen/LivePhysRegs.cpp

 
 void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
   const MachineFunction &MF = *MBB.getParent();
   const MachineFrameInfo &MFI = MF.getFrameInfo();
   if (MFI.isCalleeSavedInfoValid())
     addPristines(*this, MF, MFI, *TRI);
   addBlockLiveIns(MBB);
 }
+
+void llvm::computeLiveIns(LivePhysRegs &LiveRegs, const TargetRegisterInfo &TRI,
+                          MachineBasicBlock &MBB) {
+  assert(MBB.livein_empty());
+  LiveRegs.init(TRI);
+  LiveRegs.addLiveOutsNoPristines(MBB);
+  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
+    LiveRegs.stepBackward(MI);
+
+  for (unsigned Reg : LiveRegs) {
+    // Skip the register if we are about to add one of its super registers.
+    bool ContainsSuperReg = false;
+    for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
+      if (LiveRegs.contains(*SReg)) {
+        ContainsSuperReg = true;
+        break;
+      }
+    }
+    if (ContainsSuperReg)
+      continue;
+    MBB.addLiveIn(Reg);
+  }
+}

lib/CodeGen/MachineBasicBlock.cpp

 const uint32_t *
 MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
   // If we see a return block with successors, this must be a funclet return,
   // which does not preserve any registers. If there are no successors, we don't
   // care what kind of return it is, putting a mask after it is a no-op.
   return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
 }
 
+void MachineBasicBlock::clearLiveIns() {
+  LiveIns.clear();
+}
+
 iterator_range<MachineBasicBlock::livein_iterator>
 MachineBasicBlock::liveins() const {
   assert(getParent()->getProperties().hasProperty(
       MachineFunctionProperties::Property::TracksLiveness) &&
       "Liveness information is accurate");
   return make_range(livein_begin(), livein_end());
 }