Cleanup register pressure calculation in MachineLICM

[djasper]

Summary

There were four almost identical implementations of calculating/updating the register pressure for a certain MachineInstr. Cleanup to have a single implementation (well, actually two, as bool flag now controls whether or not RegSeen should be considered).

Not functional changes intended.

[qcolombet]

lib/CodeGen/MachineLICM.cpp

896

I believe you meant -=

905

I believe taking a DenseMap as argument would be more appropriate.

The small vector is usually not small (about 80 reg classes on X86 and 50 reg classes on AArch for instance IIRC).

1127

Keep the DenseMap signature here.

[djasper]

lib/CodeGen/MachineLICM.cpp

896

Yes, thanks for catching.. I am a little frightened that this didn't break a single test ..

905

Ah, I assumed there was only a handful of classes usually. I should have checked. Thanks for explaining.

1127

Done.

[qcolombet]

lib/CodeGen/MachineLICM.cpp

896

Could you try a llvm test-suite run to see if anything changes and if yes, extract a small test-case to add in this commit.

905

I would prefer a reference on the DenseMap.
Copying it around may not be efficient.

1127

This part of the patch is unrelated to this change (i.e., constify + for-range).
Please commit that separately.

[djasper]

lib/CodeGen/MachineLICM.cpp

897

Turns out, the + was actually correct, but I need to compare against -ClassAndCost.second above.

905

I think this is exactly what RVO was designed for and think that the code is cleaner and nicer with it.

Even if RVO should fail one day (which I don't think it will), I doubt the performance difference could be measured.

1127

Yeah, this was actually change when I was using a SmallVector, now it is just cleanup. Submitted separately in r234018.

[djasper]

Regression testing has revealed that there is actually one more distinction to be made to avoid functional changes in this refactoring: Whether to count unseen registers as defs. Now, there are no regressions in the LLVM test suite.

[qcolombet]

Regression testing has revealed that there is actually one more distinction to be made to avoid functional changes in this refactoring: Whether to count unseen registers as defs. Now, there are no regressions in the LLVM test suite.

Could you add the related test to make check?
I like to improve our code coverage in make check when we get the chance :).

Other than that LGTM.

Thanks,
-Quentin

[djasper]

Submitted as r234325.

lib/CodeGen/MachineLICM.cpp

void getRegisterClassIDAndCost(const MachineInstr *MI,
                                    unsigned Reg, unsigned OpIdx,
                                    unsigned &RCId, unsigned &RCCost) const;
 
     /// InitRegPressure - Find all virtual register references that are liveout
     /// of the preheader to initialize the starting "register pressure". Note
     /// this does not count live through (livein but not used) registers.
     void InitRegPressure(MachineBasicBlock *BB);
 
+    /// calcRegisterCost - Calculate the additional register pressure that the
+    /// registers used in MI cause.
+    ///
+    /// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to
+    /// figure out which usages are live-ins.
+    /// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
+    DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,
+                                             bool ConsiderSeen,
+                                             bool ConsiderUnseenAsDef);
+
     /// UpdateRegPressure - Update estimate of register pressure after the
     /// specified instruction.
-    void UpdateRegPressure(const MachineInstr *MI);
+    void UpdateRegPressure(const MachineInstr *MI,
+                           bool ConsiderUnseenAsDef = false);
 
     /// ExtractHoistableLoad - Unfold a load from the given machineinstr if
     /// the load itself could be hoisted. Return the unfolded and hoistable
     /// load, or null if the load couldn't be unfolded or if it wouldn't
     /// be hoistable.
     MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
 
     /// LookForDuplicate - Find an instruction amount PrevMIs that is a
void MachineLICM::InitRegPressure(MachineBasicBlock *BB) {
   // the critical edge from the loop predecessor to the loop header.
   if (BB->pred_size() == 1) {
     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
     SmallVector<MachineOperand, 4> Cond;
     if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty())
       InitRegPressure(*BB->pred_begin());
   }
 
-  for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end();
-       MII != E; ++MII) {
-    MachineInstr *MI = &*MII;
-    for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
-      const MachineOperand &MO = MI->getOperand(i);
-      if (!MO.isReg() || MO.isImplicit())
-        continue;
-      unsigned Reg = MO.getReg();
-      if (!TargetRegisterInfo::isVirtualRegister(Reg))
-        continue;
+  for (const MachineInstr &MI : *BB)
+    UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true);
+}
+
+/// UpdateRegPressure - Update estimate of register pressure after the
+/// specified instruction.
+void MachineLICM::UpdateRegPressure(const MachineInstr *MI,
+                                    bool ConsiderUnseenAsDef) {
+  auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef);
+  for (const auto &ClassAndCost : Cost) {
+    unsigned Class = ClassAndCost.first;
+    if (static_cast<int>(RegPressure[Class]) < -ClassAndCost.second)
+      RegPressure[Class] = 0;
+    else
+      RegPressure[Class] += ClassAndCost.second;
+  }
+}
+
+DenseMap<unsigned, int>
+MachineLICM::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
+                              bool ConsiderUnseenAsDef) {
+  DenseMap<unsigned, int> Cost;
+  if (MI->isImplicitDef())
+    return Cost;
 
-      bool isNew = RegSeen.insert(Reg).second;
-      unsigned RCId, RCCost;
-      getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost);
-      if (MO.isDef())
-        RegPressure[RCId] += RCCost;
-      else {
-        bool isKill = isOperandKill(MO, MRI);
-        if (isNew && !isKill)
-          // Haven't seen this, it must be a livein.
-          RegPressure[RCId] += RCCost;
-        else if (!isNew && isKill)
-          RegPressure[RCId] -= RCCost;
-      }
+    // FIXME: It seems bad to use RegSeen only for some of these calculations.
+    bool isNew = ConsiderSeen ? RegSeen.insert(Reg).second : false;
+    int PriorCost = 0;
+    if (Cost.find(RCId) != Cost.end())
+      PriorCost = Cost[RCId];
+      Cost[RCId] = PriorCost + RCCost;
+      if (isNew && !isKill && ConsiderUnseenAsDef)
+        Cost[RCId] = PriorCost + RCCost;
+        Cost[RCId] = PriorCost - RCCost;
     }
   }
-}
-
-/// UpdateRegPressure - Update estimate of register pressure after the
-/// specified instruction.
-void MachineLICM::UpdateRegPressure(const MachineInstr *MI) {
-  if (MI->isImplicitDef())
-    return;
-
-  SmallVector<unsigned, 4> Defs;
-  for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
-    const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg() || MO.isImplicit())
-      continue;
-    unsigned Reg = MO.getReg();
-    if (!TargetRegisterInfo::isVirtualRegister(Reg))
-      continue;
-
-    bool isNew = RegSeen.insert(Reg).second;
-    if (MO.isDef())
-      Defs.push_back(Reg);
-    else if (!isNew && isOperandKill(MO, MRI)) {
-      unsigned RCId, RCCost;
-      getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost);
-      if (RCCost > RegPressure[RCId])
-        RegPressure[RCId] = 0;
-      else
-        RegPressure[RCId] -= RCCost;
-    }
-  }
-
-  unsigned Idx = 0;
-  while (!Defs.empty()) {
-    unsigned Reg = Defs.pop_back_val();
-    unsigned RCId, RCCost;
-    getRegisterClassIDAndCost(MI, Reg, Idx, RCId, RCCost);
-    RegPressure[RCId] += RCCost;
-    ++Idx;
-  }
+  return Cost;
 }
 
 /// isLoadFromGOTOrConstantPool - Return true if this machine instruction
 /// loads from global offset table or constant pool.
 static bool isLoadFromGOTOrConstantPool(MachineInstr &MI) {
   assert (MI.mayLoad() && "Expected MI that loads!");
   for (MachineInstr::mmo_iterator I = MI.memoperands_begin(),
          E = MI.memoperands_end(); I != E; ++I) {
bool MachineLICM::IsCheapInstruction(MachineInstr &MI) const {
   }
 
   return isCheap;
 }
 
 /// CanCauseHighRegPressure - Visit BBs from header to current BB, check
 /// if hoisting an instruction of the given cost matrix can cause high
 /// register pressure.
 bool MachineLICM::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost,
                                           bool CheapInstr) {
   for (const auto &ClassAndCost : Cost) {
     if (ClassAndCost.second <= 0)
       continue;
 
     unsigned Class = ClassAndCost.first;
     int Limit = RegLimit[Class];
 
bool MachineLICM::CanCauseHighRegPressure(const DenseMap<unsigned, int>& Cost,
 
   return false;
 }
 
 /// UpdateBackTraceRegPressure - Traverse the back trace from header to the
 /// current block and update their register pressures to reflect the effect
 /// of hoisting MI from the current block to the preheader.
 void MachineLICM::UpdateBackTraceRegPressure(const MachineInstr *MI) {
-  if (MI->isImplicitDef())
-    return;
-
   // First compute the 'cost' of the instruction, i.e. its contribution
   // to register pressure.
-  DenseMap<unsigned, int> Cost;
-  for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {
-    const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg() || MO.isImplicit())
-      continue;
-    unsigned Reg = MO.getReg();
-    if (!TargetRegisterInfo::isVirtualRegister(Reg))
-      continue;
-
-    unsigned RCId, RCCost;
-    getRegisterClassIDAndCost(MI, Reg, i, RCId, RCCost);
-    if (MO.isDef()) {
-      DenseMap<unsigned, int>::iterator CI = Cost.find(RCId);
-      if (CI != Cost.end())
-        CI->second += RCCost;
-      else
-        Cost.insert(std::make_pair(RCId, RCCost));
-    } else if (isOperandKill(MO, MRI)) {
-      DenseMap<unsigned, int>::iterator CI = Cost.find(RCId);
-      if (CI != Cost.end())
-        CI->second -= RCCost;
-      else
-        Cost.insert(std::make_pair(RCId, -RCCost));
-    }
-  }
+  auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false,
+                               /*ConsiderUnseenAsDef=*/false);
 
   // Update register pressure of blocks from loop header to current block.
-  for (unsigned i = 0, e = BackTrace.size(); i != e; ++i) {
-    SmallVectorImpl<unsigned> &RP = BackTrace[i];
-    for (DenseMap<unsigned, int>::iterator CI = Cost.begin(), CE = Cost.end();
-         CI != CE; ++CI) {
-      unsigned RCId = CI->first;
-      RP[RCId] += CI->second;
-    }
-  }
+  for (auto &RP : BackTrace)
+    for (const auto &ClassAndCost : Cost)
+      RP[ClassAndCost.first] += ClassAndCost.second;
 }
 
 /// IsProfitableToHoist - Return true if it is potentially profitable to hoist
 /// the given loop invariant.
 bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) {
   if (MI.isImplicitDef())
     return true;
 
if (CheapInstr && CreatesCopy) {
     return false;
   }
 
   // Rematerializable instructions should always be hoisted since the register
   // allocator can just pull them down again when needed.
   if (TII->isTriviallyReMaterializable(&MI, AA))
     return true;
 
-  // Estimate register pressure to determine whether to LICM the instruction.
-  // In low register pressure situation, we can be more aggressive about
-  // hoisting. Also, favors hoisting long latency instructions even in
-  // moderately high pressure situation.
-  // Cheap instructions will only be hoisted if they don't increase register
-  // pressure at all.
   // FIXME: If there are long latency loop-invariant instructions inside the
   // loop at this point, why didn't the optimizer's LICM hoist them?
-  DenseMap<unsigned, int> Cost;
   for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI.getOperand(i);
     if (!MO.isReg() || MO.isImplicit())
       continue;
     unsigned Reg = MO.getReg();
     if (!TargetRegisterInfo::isVirtualRegister(Reg))
       continue;
-
-    unsigned RCId, RCCost;
-    getRegisterClassIDAndCost(&MI, Reg, i, RCId, RCCost);
-    if (MO.isDef()) {
-      if (HasHighOperandLatency(MI, i, Reg)) {
-        DEBUG(dbgs() << "Hoist High Latency: " << MI);
-        ++NumHighLatency;
-        return true;
-      }
-      Cost[RCId] += RCCost;
-    } else if (isOperandKill(MO, MRI)) {
-      // Is a virtual register use is a kill, hoisting it out of the loop
-      // may actually reduce register pressure or be register pressure
-      // neutral.
-      Cost[RCId] -= RCCost;
-    }
+    if (MO.isDef() && HasHighOperandLatency(MI, i, Reg)) {
   }
 
+  // Estimate register pressure to determine whether to LICM the instruction.
+  // In low register pressure situation, we can be more aggressive about
+  // hoisting. Also, favors hoisting long latency instructions even in
+  // moderately high pressure situation.
+  // Cheap instructions will only be hoisted if they don't increase register
+  // pressure at all.
+  auto Cost = calcRegisterCost(&MI, /*ConsiderSeen=*/false,
+                               /*ConsiderUnseenAsDef=*/false);
+
   // Visit BBs from header to current BB, if hoisting this doesn't cause
   // high register pressure, then it's safe to proceed.
   if (!CanCauseHighRegPressure(Cost, CheapInstr)) {
     DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI);
     ++NumLowRP;
     return true;
   }