BranchFolding: Use LivePhysReg to update live in lists.

[MatzeB]

Summary

Use LivePhysRegs with a backwards walking algorithm to update live in
lists, this way the results do not depend on the presence of kill flags
anymore.

This patch also reduces the number of registers added as live-in. Previously all pristine registers as well as all sub registers of a super register were added resulting in unnecessarily large live in lists (the block noticed in the discussion of http://reviews.llvm.org/D20907 may have been caused by this).

[mcrosier]

Minor nit.

lib/CodeGen/BranchFolding.cpp

415

Pre-increment of I is preferred.

[MatzeB]

Address nitpicks, add a comment to explain the purpose of the loop over the super registers.

[ab]

lib/CodeGen/BranchFolding.cpp

412

Unnecessary braces?

415–428

Would it make sense to iterate on the LivePhysRegs set instead?

lib/CodeGen/BranchFolding.h

106

Maybe remove LiveRegs from here, and only create it in computeLiveIns? It's cleared anyway, and looks cheap to construct.

[MatzeB]

Thanks for the review!

lib/CodeGen/BranchFolding.cpp

415–428

good idea.

lib/CodeGen/BranchFolding.h

106

It is still a bigger heap allocation for the Sparse memory of the SparseSet. Heap allocations are not completely free. We probably won't notice the difference in this case, but keeping a member in the enclosing pass isn't a big thing either.

I did however move the initialization into the computeLiveIn() function as I realized that there is a good chance that for simpler function we will never end up calling it.

[MatzeB]

Address review comments.

[ab]

LGTM

lib/CodeGen/BranchFolding.cpp

25

Since it's in the .h already, remove it from here?

418

false -> /*IncludeSelf=*/ false, or even remove it?

438

stale comment (here and later)

lib/CodeGen/BranchFolding.h

106

Sounds good; I thought init() re-did the allocation, but that's not true.

lib/CodeGen/BranchFolding.h

 //===-- BranchFolding.h - Fold machine code branch instructions -*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H
 #define LLVM_LIB_CODEGEN_BRANCHFOLDING_H
 
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/Support/BlockFrequency.h"
 #include <vector>
 
 namespace llvm {
   class MachineBlockFrequencyInfo;
   class MachineBranchProbabilityInfo;
   class MachineFunction;
   class MachineModuleInfo;
   class MachineLoopInfo;
-  class RegScavenger;
   class TargetInstrInfo;
   class TargetRegisterInfo;
 
   class LLVM_LIBRARY_VISIBILITY BranchFolder {
   public:
     class MBFIWrapper;
 
     explicit BranchFolder(bool defaultEnableTailMerge, bool CommonHoist,
public:
         TailStartPos = Pos;
       }
     };
     std::vector<SameTailElt> SameTails;
 
     bool AfterBlockPlacement;
     bool EnableTailMerge;
     bool EnableHoistCommonCode;
+    bool UpdateLiveIns;
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
     MachineModuleInfo *MMI;
     MachineLoopInfo *MLI;
-    RegScavenger *RS;
+    LivePhysRegs LiveRegs;
 
   public:
     /// \brief This class keeps track of branch frequencies of newly created
     /// blocks and tail-merged blocks.
     class MBFIWrapper {
     public:
       MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
       BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
namespace llvm {
   private:
     MBFIWrapper &MBBFreqInfo;
     const MachineBranchProbabilityInfo &MBPI;
 
     bool TailMergeBlocks(MachineFunction &MF);
     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
                        MachineBasicBlock* PredBB);
     void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
-    void MaintainLiveIns(MachineBasicBlock *CurMBB,
-                         MachineBasicBlock *NewMBB);
+    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

 //
 //===----------------------------------------------------------------------===//
 
 #include "BranchFolding.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
-#include "llvm/CodeGen/RegisterScavenging.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
bool BranchFolder::OptimizeFunction(MachineFunction &MF,
 
   TriedMerging.clear();
 
   AfterBlockPlacement = AfterPlacement;
   TII = tii;
   TRI = tri;
   MMI = mmi;
   MLI = mli;
-  RS = nullptr;
 
-  // Use a RegScavenger to help update liveness when required.
   MachineRegisterInfo &MRI = MF.getRegInfo();
-  if (MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF))
-    RS = new RegScavenger();
-  else
+  if (MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF)) {
+    UpdateLiveIns = true;
+    LiveRegs.init(TRI);
+  } else {
+    UpdateLiveIns = false;
     MRI.invalidateLiveness();
+  }
 
   // Fix CFG.  The later algorithms expect it to be right.
   bool MadeChange = false;
   for (MachineBasicBlock &MBB : MF) {
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     SmallVector<MachineOperand, 4> Cond;
     if (!TII->AnalyzeBranch(MBB, TBB, FBB, Cond, true))
       MadeChange |= MBB.CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
while (MadeChangeThisIteration) {
     if (EnableHoistCommonCode)
       MadeChangeThisIteration |= HoistCommonCode(MF);
     MadeChange |= MadeChangeThisIteration;
   }
 
   // See if any jump tables have become dead as the code generator
   // did its thing.
   MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
-  if (!JTI) {
-    delete RS;
+  if (!JTI)
     return MadeChange;
-  }
 
   // Walk the function to find jump tables that are live.
   BitVector JTIsLive(JTI->getJumpTables().size());
   for (const MachineBasicBlock &BB : MF) {
     for (const MachineInstr &I : BB)
       for (const MachineOperand &Op : I.operands()) {
         if (!Op.isJTI()) continue;
 
         // Remember that this JT is live.
         JTIsLive.set(Op.getIndex());
       }
   }
 
   // Finally, remove dead jump tables.  This happens when the
   // indirect jump was unreachable (and thus deleted).
   for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
     if (!JTIsLive.test(i)) {
       JTI->RemoveJumpTable(i);
       MadeChange = true;
     }
 
-  delete RS;
   return MadeChange;
 }
 
 //===----------------------------------------------------------------------===//
 //  Tail Merging of Blocks
 //===----------------------------------------------------------------------===//
 
 /// HashMachineInstr - Compute a hash value for MI and its operands.
while (I1->isDebugValue()) {
         return TailLen;
       --I1;
     }
     ++I1;
   }
   return TailLen;
 }
 
-void BranchFolder::MaintainLiveIns(MachineBasicBlock *CurMBB,
-                                   MachineBasicBlock *NewMBB) {
-  if (RS) {
-    RS->enterBasicBlock(*CurMBB);
-    if (!CurMBB->empty())
-      RS->forward(std::prev(CurMBB->end()));
-    for (unsigned int i = 1, e = TRI->getNumRegs(); i != e; i++)
-      if (RS->isRegUsed(i, false))
-        NewMBB->addLiveIn(i);
+void BranchFolder::computeLiveIns(MachineBasicBlock &MBB) {
+  if (!UpdateLiveIns)
+    return;
+
+  LiveRegs.clear();
+  LiveRegs.addLiveOutsNoPristines(MBB);
+  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
+    LiveRegs.stepBackward(MI);
+  }
+  for (unsigned I = 1, E = TRI->getNumRegs(); I != E; ++I) {
+    if (!LiveRegs.contains(I))
+      continue;
+    // Skip the register if we are about to add one of its super registers.
+    bool ContainsSuperReg = false;
+    for (MCSuperRegIterator SReg(I, TRI, false); SReg.isValid(); ++SReg) {
+      if (LiveRegs.contains(*SReg)) {
+        ContainsSuperReg = true;
+        break;
+      }
+    }
+    if (ContainsSuperReg)
+      continue;
+    MBB.addLiveIn(I);
   }
 }
 
 /// 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) {
-  MachineBasicBlock *CurMBB = OldInst->getParent();
-
   TII->ReplaceTailWithBranchTo(OldInst, NewDest);
 
   // For targets that use the register scavenger, we must maintain LiveIns.
-  MaintainLiveIns(CurMBB, NewDest);
+  computeLiveIns(*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,
   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));
 
   // For targets that use the register scavenger, we must maintain LiveIns.
-  MaintainLiveIns(&CurMBB, NewMBB);
+  computeLiveIns(*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;
   }