[MachineCombiner] [NFC]Add MustReduceRegisterPressure goal

[shchenz]

Summary

add a new goal MustReduceRegisterPressure for machine combiner pass. This is an NFC patch.

PowerPC will use this new goal to do some register pressure related optimization. https://reviews.llvm.org/D92071

[shchenz]

1: fix lint warning messages
2: fix x86 CodeGen/X86/coalescer-dce.ll verify error after liveintervals introduced in machine combiner pass

and gentle ping...

[spatel]

I'm not too familiar with MIR and I have not worked on MachineCombiner in a long time, so someone else should probably have a look too.

1. Why are the killed and dead flags changing in the tests?
2. Is there compile-time increase from having the extra passes (Slot index numbering, Live Interval Analysis, Machine Trace Metrics) even for targets that do not enable the MustReduceRegisterPressure objective?

[shchenz]

@spatel Very much appreciate your comments. It is a good start for this patch to move on.

1. Why are the killed and dead flags changing in the tests?

For the dead flag in case test/DebugInfo/X86/machinecse-wrongdebug-hoist.ll, I think now it is more accurate. It should be an improvement.
For the kill flags in other cases, it caused by Liveintervals pass cleaning the killed flag for uses. See https://github.com/llvm/llvm-project/blob/5b9fc44d8128717ef2f219b061c018abb85c717f/llvm/lib/CodeGen/LiveIntervalCalc.cpp#L157-L160.
I am guessing this code can be improved because now Liveintervals is used in many places except before register allocation, such as MachineScheduler, Machinepipeliner, and some other target-specific passes. Fortunately, before RA, we have data flow analysis, so it is easy for us to check if a register/operand is killed without depending on the kill flag. For example in MachineLICM pass, we check kill operand like:

static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {
  return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
}

yeah, sure, if this is a must fix degradation, I will fix this in follow up patches.

2. Is there compile-time increase from having the extra passes (Slot index numbering, Live Interval Analysis, Machine Trace Metrics) even for targets that do not enable the MustReduceRegisterPressure objective?

Compile-time diff: https://llvm-compile-time-tracker.com/compare.php?from=1bb79875e4b8f9018142a5155ca3f7df37778419&to=16f8136e47fdf13a05a27bbd0829d670f3baacb1&stat=instructions
I am not sure which target is for above testing, but I think it must be not PowerPC ^^.
GEO increases 0.53%, and biggest increase is 0.7%, do you think this is an acceptable increase after I add these new passes to machine combiner?
I think LiveIntervals pass can not only be used for this patch but it can also be used for later register pressure track for ILP related reassociations. I knew we used to plan a register estimation model in this pass to prevent too many reassociations from causing too big register pressures.

Thanks again.

llvm/test/DebugInfo/X86/machinecse-wrongdebug-hoist.ll

3

This should be a positive change. register %5 has no user below.

[spatel]

In D92068#2433227, @shchenz wrote:

1. Why are the killed and dead flags changing in the tests?

For the dead flag in case test/DebugInfo/X86/machinecse-wrongdebug-hoist.ll, I think now it is more accurate. It should be an improvement.
For the kill flags in other cases, it caused by Liveintervals pass cleaning the killed flag for uses. See https://github.com/llvm/llvm-project/blob/5b9fc44d8128717ef2f219b061c018abb85c717f/llvm/lib/CodeGen/LiveIntervalCalc.cpp#L157-L160.
I am guessing this code can be improved because now Liveintervals is used in many places except before register allocation, such as MachineScheduler, Machinepipeliner, and some other target-specific passes. Fortunately, before RA, we have data flow analysis, so it is easy for us to check if a register/operand is killed without depending on the kill flag. For example in MachineLICM pass, we check kill operand like:

static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {
  return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());
}

yeah, sure, if this is a must fix degradation, I will fix this in follow up patches.

I don't know the answer to that question - does it potentially harm other passes if the kill flag was dropped, or can we assume it does not matter? Adding more potential reviewers.

2. Is there compile-time increase from having the extra passes (Slot index numbering, Live Interval Analysis, Machine Trace Metrics) even for targets that do not enable the MustReduceRegisterPressure objective?

Compile-time diff: https://llvm-compile-time-tracker.com/compare.php?from=1bb79875e4b8f9018142a5155ca3f7df37778419&to=16f8136e47fdf13a05a27bbd0829d670f3baacb1&stat=instructions
I am not sure which target is for above testing, but I think it must be not PowerPC ^^.

I assume it's an x86 machine, but @nikic can confirm.

GEO increases 0.53%, and biggest increase is 0.7%, do you think this is an acceptable increase after I add these new passes to machine combiner?
I think LiveIntervals pass can not only be used for this patch but it can also be used for later register pressure track for ILP related reassociations. I knew we used to plan a register estimation model in this pass to prevent too many reassociations from causing too big register pressures.

We have tried to avoid changes that can cost that much compile-time without any benefit. If every target will have that loss even if there is no chance of run-time improvement, we should look for ways to hide it. Again, I'm not very familiar with how things work here - is it possible to make the extra analysis conditional on some flags internal to the machine combiner pass?

[lebedev.ri]

I agree, this shouldn't incur compile-time cost for targets on which this won't even be run.
I'm going to guess that pretty much all extra cost comes from requiring LiveIntervals,
in which case i'd guess you'd want to compute it lazily only when actually needed.

[shchenz]

Thanks for your comments @spatel @lebedev.ri

Do you have any idea to run the LiveIntervals pass only on the target that MustReduceRegisterPressure is enabled?
Some considerations:
1: PowerPC uses LiveIntervals in class PPCInstrInfo which is not inherited from class Pass, so I can not call getAnalysis<LiveIntervals>() there.
2: I tried to guard getAnalysis<LiveIntervals>() in MachineCombiner pass under a new condition like enableReduceRegisterPressureGoal(), it also does not work. If we add AU.addRequired<LiveIntervals>() in MachineCombiner::getAnalysisUsage, we will need to add the required passes before machine combiner pass.

[shchenz]

1: don't require LiveIntervals analysis
2: revert the test case change as now this should be NFC

[shchenz]

Hi @spatel @lebedev.ri , I changed the patch not requiring LiveIntervals pass. Now this patch is NFC.

New compiling time diff is: https://llvm-compile-time-tracker.com/compare.php?from=5bb28fa0f51e94522644fe5633877b441b9ad8d3&to=73b8523c4c149866690257f58bc678be20a4991b&stat=instructions
In summary, at -O3 GEO increases 0.01%; at ReleaseThinLTO config, GEO decreases 0.01%. I assume this patch now has no compiling time regression.

Could you help to have another look? Thanks.

[spatel]

If this is NFC now, no objections from me - I just noted minor errors.
So we do not need LiveIntervals analysis at all now to reduce pressure, or that will be dealt with separately?

llvm/include/llvm/CodeGen/TargetInstrInfo.h

1068

typo: "if target supports reassociation of instructions"

1076

Make a complete sentence for code comments:

/// Fix up the placeholder we may add in genAlternativeCodeSequence().

1078

typo: "finalize"

llvm/lib/CodeGen/MachineCombiner.cpp

320

typo: PressureTracker

481

typo:

// even if InsInstrs is not the better pattern.

639

typo (also in original code):
"threshold"

644

InInstrs -> InsInstrs

649

back -> Go back ?

[shchenz]

1: address @spatel comments

[shchenz]

In D92068#2446159, @spatel wrote:

If this is NFC now, no objections from me - I just noted minor errors.
So we do not need LiveIntervals analysis at all now to reduce pressure, or that will be dealt with separately?

Thanks for your careful review. Updated accordingly.
Now I only handle two patterns in PowerPC patch https://reviews.llvm.org/D92071. The left patterns hit in our internal tests don't need live intervals analysis to decide the specific blocks are in high register pressure.
And yes, I will handle the other two deleted patterns which require live intervals analysis in following patches. I will keep in mind live intervals analysis should only be run on targets that use this newly added goal. ^^

Thanks again for making this patch go so far.

[spatel]

LGTM

llvm/include/llvm/CodeGen/TargetInstrInfo.h

1068

Spelling is still wrong here:
ressociation -> reassociation
instrucitons -> instructions

llvm/lib/CodeGen/MachineCombiner.cpp

481

bettern -> better

[shchenz]

Thank you! @spatel

llvm/include/llvm/CodeGen/TargetInstrInfo.h

 #include "llvm/CodeGen/MIRFormatter.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineCombinerPattern.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineOutliner.h"
+#include "llvm/CodeGen/RegisterClassInfo.h"
 #include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <utility>
public:
 
   /// Return true when there is potentially a faster code sequence
   /// for an instruction chain ending in \p Root. All potential patterns are
   /// returned in the \p Pattern vector. Pattern should be sorted in priority
   /// order since the pattern evaluator stops checking as soon as it finds a
   /// faster sequence.
   /// \param Root - Instruction that could be combined with one of its operands
   /// \param Patterns - Vector of possible combination patterns
-  virtual bool getMachineCombinerPatterns(
-      MachineInstr &Root,
-      SmallVectorImpl<MachineCombinerPattern> &Patterns) const;
+  virtual bool
+  getMachineCombinerPatterns(MachineInstr &Root,
+                             SmallVectorImpl<MachineCombinerPattern> &Patterns,
+                             bool DoRegPressureReduce) const;
+
+  /// Return true if target supports to ressociate instrucitons in machine
+  /// combiner pass to reduce register pressure for a given BB.
+  virtual bool
+  shouldReduceRegisterPressure(MachineBasicBlock *MBB, LiveIntervals *LIS,
+                               RegisterClassInfo *RegClassInfo) const {
+    return false;
+  }
+
+  /// fix up the placeholder we may add in genAlternativeCodeSequence()
+  virtual void
+  finilizeInsInstrs(MachineInstr &Root, MachineCombinerPattern &P,
+                    SmallVectorImpl<MachineInstr *> &InsInstrs) const {}
 
   /// Return true when a code sequence can improve throughput. It
   /// should be called only for instructions in loops.
   /// \param Pattern - combiner pattern
   virtual bool isThroughputPattern(MachineCombinerPattern Pattern) const;
 
   /// Return true if the input \P Inst is part of a chain of dependent ops
   /// that are suitable for reassociation, otherwise return false.

llvm/lib/CodeGen/MachineCombiner.cpp

 //===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // The machine combiner pass uses machine trace metrics to ensure the combined
 // instructions do not lengthen the critical path or the resource depth.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h"
+#include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/MachineSizeOpts.h"
 #include "llvm/CodeGen/MachineTraceMetrics.h"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/RegisterClassInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
class MachineCombiner : public MachineFunctionPass {
   const TargetRegisterInfo *TRI;
   MCSchedModel SchedModel;
   MachineRegisterInfo *MRI;
   MachineLoopInfo *MLI; // Current MachineLoopInfo
   MachineTraceMetrics *Traces;
   MachineTraceMetrics::Ensemble *MinInstr;
   MachineBlockFrequencyInfo *MBFI;
   ProfileSummaryInfo *PSI;
+  RegisterClassInfo RegClassInfo;
+  LiveIntervals *LIS;
 
   TargetSchedModel TSchedModel;
 
   /// True if optimizing for code size.
   bool OptSize;
 
 public:
   static char ID;
unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
                       MachineTraceMetrics::Trace BlockTrace);
   bool
   improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
                           MachineTraceMetrics::Trace BlockTrace,
                           SmallVectorImpl<MachineInstr *> &InsInstrs,
                           SmallVectorImpl<MachineInstr *> &DelInstrs,
                           DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
                           MachineCombinerPattern Pattern, bool SlackIsAccurate);
+  bool reduceRegisterPressure(MachineInstr &Root, MachineBasicBlock *MBB,
+                              SmallVectorImpl<MachineInstr *> &InsInstrs,
+                              SmallVectorImpl<MachineInstr *> &DelInstrs,
+                              MachineCombinerPattern Pattern);
   bool preservesResourceLen(MachineBasicBlock *MBB,
                             MachineTraceMetrics::Trace BlockTrace,
                             SmallVectorImpl<MachineInstr *> &InsInstrs,
                             SmallVectorImpl<MachineInstr *> &DelInstrs);
   void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
                      SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
   std::pair<unsigned, unsigned>
   getLatenciesForInstrSequences(MachineInstr &MI,
INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
                       "Machine InstCombiner", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
 INITIALIZE_PASS_END(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner",
                     false, false)
 
 void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
+  AU.addRequired<LiveIntervals>();
   AU.addPreserved<MachineDominatorTree>();
   AU.addRequired<MachineLoopInfo>();
   AU.addPreserved<MachineLoopInfo>();
   AU.addRequired<MachineTraceMetrics>();
   AU.addPreserved<MachineTraceMetrics>();
   AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
   AU.addRequired<ProfileSummaryInfoWrapperPass>();
   MachineFunctionPass::getAnalysisUsage(AU);
for (const MachineOperand &MO : NewRoot->operands()) {
     NewRootLatency = std::max(NewRootLatency, LatencyOp);
   }
   return NewRootLatency;
 }
 
 /// The combiner's goal may differ based on which pattern it is attempting
 /// to optimize.
 enum class CombinerObjective {
-  MustReduceDepth, // The data dependency chain must be improved.
-  Default          // The critical path must not be lengthened.
+  MustReduceDepth,            // The data dependency chain must be improved.
+  MustReduceRegisterPressure, // The register pressure must be reduced.
+  Default                     // The critical path must not be lengthened.
 };
 
 static CombinerObjective getCombinerObjective(MachineCombinerPattern P) {
   // TODO: If C++ ever gets a real enum class, make this part of the
   // MachineCombinerPattern class.
   switch (P) {
   case MachineCombinerPattern::REASSOC_AX_BY:
   case MachineCombinerPattern::REASSOC_AX_YB:
std::pair<unsigned, unsigned> MachineCombiner::getLatenciesForInstrSequences(
 
   unsigned RootLatency = 0;
   for (auto I : DelInstrs)
     RootLatency += TSchedModel.computeInstrLatency(I);
 
   return {NewRootLatency, RootLatency};
 }
 
+bool MachineCombiner::reduceRegisterPressure(
+    MachineInstr &Root, MachineBasicBlock *MBB,
+    SmallVectorImpl<MachineInstr *> &InsInstrs,
+    SmallVectorImpl<MachineInstr *> &DelInstrs,
+    MachineCombinerPattern Pattern) {
+  // FIXME: for now, we don't do any check for the register pressure patterns.
+  // We treat them as always profitable. But we can do better if we make
+  // RressureTracker class be aware of TIE attribute. Then we can get an
+  // accurate compare of register pressure with DelInstrs or InsInstrs.
+  return true;
+}
+
 /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
 /// The new code sequence ends in MI NewRoot. A necessary condition for the new
 /// sequence to replace the old sequence is that it cannot lengthen the critical
 /// path. The definition of "improve" may be restricted by specifying that the
 /// new path improves the data dependency chain (MustReduceDepth).
 bool MachineCombiner::improvesCriticalPathLen(
     MachineBasicBlock *MBB, MachineInstr *Root,
     MachineTraceMetrics::Trace BlockTrace,

 /// depths if requested.
 ///
 /// \param MBB basic block to insert instructions in
 /// \param MI current machine instruction
 /// \param InsInstrs new instructions to insert in \p MBB
 /// \param DelInstrs instruction to delete from \p MBB
 /// \param MinInstr is a pointer to the machine trace information
 /// \param RegUnits set of live registers, needed to compute instruction depths
+/// \param TII is target instruction info, used to call target hook
+/// \param Pattern is used to call target hook finilizeInsInstrs
 /// \param IncrementalUpdate if true, compute instruction depths incrementally,
 ///                          otherwise invalidate the trace
 static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
                                      SmallVector<MachineInstr *, 16> InsInstrs,
                                      SmallVector<MachineInstr *, 16> DelInstrs,
                                      MachineTraceMetrics::Ensemble *MinInstr,
                                      SparseSet<LiveRegUnit> &RegUnits,
+                                     const TargetInstrInfo *TII,
+                                     MachineCombinerPattern Pattern,
                                      bool IncrementalUpdate) {
+  // If we want to fix up some placeholder for some target, do it now.
+  // We need this because in genAlternativeCodeSequence, we have not decided the
+  // better pattern InsInstrs or DelInstrs, so we don't want generate some
+  // sideeffect to the function. For example we need to delay the constant pool
+  // entry creation here after InsInstrs is selected as better pattern.
+  // Otherwise the constant pool entry created for InsInstrs will not be deleted
+  // even InsInstrs is not the bettern pattern.
+  TII->finilizeInsInstrs(MI, Pattern, InsInstrs);
+
   for (auto *InstrPtr : InsInstrs)
     MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
 
   for (auto *InstrPtr : DelInstrs) {
     InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
     // Erase all LiveRegs defined by the removed instruction
     for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
       if (I->MI == InstrPtr)
bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
   if (!MinInstr)
     MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
 
   SparseSet<LiveRegUnit> RegUnits;
   RegUnits.setUniverse(TRI->getNumRegUnits());
 
   bool OptForSize = OptSize || llvm::shouldOptimizeForSize(MBB, PSI, MBFI);
 
+  bool DoRegPressureReduce =
+      TII->shouldReduceRegisterPressure(MBB, LIS, &RegClassInfo);
+
   while (BlockIter != MBB->end()) {
     auto &MI = *BlockIter++;
     SmallVector<MachineCombinerPattern, 16> Patterns;
     // The motivating example is:
     //
     //     MUL  Other        MUL_op1 MUL_op2  Other
     //      \    /               \      |    /
     //      ADD/SUB      =>        MADD/MSUB
while (BlockIter != MBB->end()) {
     //
     // The algorithm does not try to evaluate all patterns and pick the best.
     // This is only an artificial restriction though. In practice there is
     // mostly one pattern, and getMachineCombinerPatterns() can order patterns
     // based on an internal cost heuristic. If
     // machine-combiner-verify-pattern-order is enabled, all patterns are
     // checked to ensure later patterns do not provide better latency savings.
 
-    if (!TII->getMachineCombinerPatterns(MI, Patterns))
+    if (!TII->getMachineCombinerPatterns(MI, Patterns, DoRegPressureReduce))
       continue;
 
     if (VerifyPatternOrder)
       verifyPatternOrder(MBB, MI, Patterns);
 
     for (auto P : Patterns) {
       SmallVector<MachineInstr *, 16> InsInstrs;
       SmallVector<MachineInstr *, 16> DelInstrs;
for (auto P : Patterns) {
           InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,
                           /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);
       });
 
       bool SubstituteAlways = false;
       if (ML && TII->isThroughputPattern(P))
         SubstituteAlways = true;
 
-      if (IncrementalUpdate) {
+      if (IncrementalUpdate && LastUpdate != BlockIter) {
         // Update depths since the last incremental update.
         MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
         LastUpdate = BlockIter;
       }
 
+      if (DoRegPressureReduce &&
+          getCombinerObjective(P) ==
+              CombinerObjective::MustReduceRegisterPressure) {
+        if (MBB->size() > inc_threshold) {
+          // Use incremental depth updates for basic blocks above treshold
+          IncrementalUpdate = true;
+          LastUpdate = BlockIter;
+        }
+        if (reduceRegisterPressure(MI, MBB, InsInstrs, DelInstrs, P)) {
+          // Replace DelInstrs with InInstrs.
+          insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
+                                   RegUnits, TII, P, IncrementalUpdate);
+          Changed |= true;
+
+          // back to previous instruction as it may have ILP reassociation
+          // opportunity.
+          BlockIter--;
+          break;
+        }
+      }
+
       // Substitute when we optimize for codesize and the new sequence has
       // fewer instructions OR
       // the new sequence neither lengthens the critical path nor increases
       // resource pressure.
       if (SubstituteAlways ||
           doSubstitute(NewInstCount, OldInstCount, OptForSize)) {
         insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
-                                 RegUnits, IncrementalUpdate);
+                                 RegUnits, TII, P, IncrementalUpdate);
         // Eagerly stop after the first pattern fires.
         Changed = true;
         break;
       } else {
         // For big basic blocks, we only compute the full trace the first time
         // we hit this. We do not invalidate the trace, but instead update the
         // instruction depths incrementally.
         // NOTE: Only the instruction depths up to MI are accurate. All other
         // trace information is not updated.
         MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
         Traces->verifyAnalysis();
         if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
                                     InstrIdxForVirtReg, P,
                                     !IncrementalUpdate) &&
             preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
           if (MBB->size() > inc_threshold) {
             // Use incremental depth updates for basic blocks above treshold
             IncrementalUpdate = true;
             LastUpdate = BlockIter;
           }
 
           insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
-                                   RegUnits, IncrementalUpdate);
+                                   RegUnits, TII, P, IncrementalUpdate);
 
           // Eagerly stop after the first pattern fires.
           Changed = true;
           break;
         }
         // Cleanup instructions of the alternative code sequence. There is no
         // use for them.
         MachineFunction *MF = MBB->getParent();
bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
   MLI = &getAnalysis<MachineLoopInfo>();
   Traces = &getAnalysis<MachineTraceMetrics>();
   PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
   MBFI = (PSI && PSI->hasProfileSummary()) ?
          &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() :
          nullptr;
   MinInstr = nullptr;
   OptSize = MF.getFunction().hasOptSize();
+  RegClassInfo.runOnMachineFunction(MF);
+  LIS = &getAnalysis<LiveIntervals>();
 
   LLVM_DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
   if (!TII->useMachineCombiner()) {
     LLVM_DEBUG(
         dbgs()
         << "  Skipping pass: Target does not support machine combiner\n");
     return false;
   }

llvm/lib/CodeGen/TargetInstrInfo.cpp

 // FIXME: This has the potential to be expensive (compile time) while not
 // improving the code at all. Some ways to limit the overhead:
 // 1. Track successful transforms; bail out if hit rate gets too low.
 // 2. Only enable at -O3 or some other non-default optimization level.
 // 3. Pre-screen pattern candidates here: if an operand of the previous
 //    instruction is known to not increase the critical path, then don't match
 //    that pattern.
 bool TargetInstrInfo::getMachineCombinerPatterns(
-    MachineInstr &Root,
-    SmallVectorImpl<MachineCombinerPattern> &Patterns) const {
+    MachineInstr &Root, SmallVectorImpl<MachineCombinerPattern> &Patterns,
+    bool DoRegPressureReduce) const {
   bool Commute;
   if (isReassociationCandidate(Root, Commute)) {
     // We found a sequence of instructions that may be suitable for a
     // reassociation of operands to increase ILP. Specify each commutation
     // possibility for the Prev instruction in the sequence and let the
     // machine combiner decide if changing the operands is worthwhile.
     if (Commute) {
       Patterns.push_back(MachineCombinerPattern::REASSOC_AX_YB);

llvm/lib/Target/AArch64/AArch64InstrInfo.h

public:
 
   /// Return true when a code sequence can improve throughput. It
   /// should be called only for instructions in loops.
   /// \param Pattern - combiner pattern
   bool isThroughputPattern(MachineCombinerPattern Pattern) const override;
   /// Return true when there is potentially a faster code sequence
   /// for an instruction chain ending in ``Root``. All potential patterns are
   /// listed in the ``Patterns`` array.
-  bool getMachineCombinerPatterns(
-      MachineInstr &Root,
-      SmallVectorImpl<MachineCombinerPattern> &Patterns) const override;
+  bool
+  getMachineCombinerPatterns(MachineInstr &Root,
+                             SmallVectorImpl<MachineCombinerPattern> &Patterns,
+                             bool DoRegPressureReduce) const override;
   /// Return true when Inst is associative and commutative so that it can be
   /// reassociated.
   bool isAssociativeAndCommutative(const MachineInstr &Inst) const override;
   /// When getMachineCombinerPatterns() finds patterns, this function generates
   /// the instructions that could replace the original code sequence
   void genAlternativeCodeSequence(
       MachineInstr &Root, MachineCombinerPattern Pattern,
       SmallVectorImpl<MachineInstr *> &InsInstrs,

llvm/lib/Target/AArch64/AArch64InstrInfo.cpp

bool AArch64InstrInfo::isThroughputPattern(
   return false;
 }
 /// Return true when there is potentially a faster code sequence for an
 /// instruction chain ending in \p Root. All potential patterns are listed in
 /// the \p Pattern vector. Pattern should be sorted in priority order since the
 /// pattern evaluator stops checking as soon as it finds a faster sequence.
 
 bool AArch64InstrInfo::getMachineCombinerPatterns(
-    MachineInstr &Root,
-    SmallVectorImpl<MachineCombinerPattern> &Patterns) const {
+    MachineInstr &Root, SmallVectorImpl<MachineCombinerPattern> &Patterns,
+    bool DoRegPressureReduce) const {
   // Integer patterns
   if (getMaddPatterns(Root, Patterns))
     return true;
   // Floating point patterns
   if (getFMAPatterns(Root, Patterns))
     return true;
 
-  return TargetInstrInfo::getMachineCombinerPatterns(Root, Patterns);
+  return TargetInstrInfo::getMachineCombinerPatterns(Root, Patterns,
+                                                     DoRegPressureReduce);
 }
 
 enum class FMAInstKind { Default, Indexed, Accumulator };
 /// genFusedMultiply - Generate fused multiply instructions.
 /// This function supports both integer and floating point instructions.
 /// A typical example:
 ///  F|MUL I=A,B,0
 ///  F|ADD R,I,C

llvm/lib/Target/PowerPC/PPCInstrInfo.h

public:
   /// chain ending in \p Root. All potential patterns are output in the \p
   /// P array.
   bool getFMAPatterns(MachineInstr &Root,
                       SmallVectorImpl<MachineCombinerPattern> &P) const;
 
   /// Return true when there is potentially a faster code sequence
   /// for an instruction chain ending in <Root>. All potential patterns are
   /// output in the <Pattern> array.
-  bool getMachineCombinerPatterns(
-      MachineInstr &Root,
-      SmallVectorImpl<MachineCombinerPattern> &P) const override;
+  bool
+  getMachineCombinerPatterns(MachineInstr &Root,
+                             SmallVectorImpl<MachineCombinerPattern> &P,
+                             bool DoRegPressureReduce) const override;
 
   bool isAssociativeAndCommutative(const MachineInstr &Inst) const override;
 
   /// On PowerPC, we try to reassociate FMA chain which will increase
   /// instruction size. Set extension resource length limit to 1 for edge case.
   /// Resource Length is calculated by scaled resource usage in getCycles().
   /// Because of the division in getCycles(), it returns different cycles due to
   /// legacy scaled resource usage. So new resource length may be same with

llvm/lib/Target/PowerPC/PPCInstrInfo.cpp

bool PPCInstrInfo::getFMAPatterns(
   if (IsReassociableAdd(*Leaf)) {
     Patterns.push_back(MachineCombinerPattern::REASSOC_XY_AMM_BMM);
     return true;
   }
   return false;
 }
 
 bool PPCInstrInfo::getMachineCombinerPatterns(
-    MachineInstr &Root,
-    SmallVectorImpl<MachineCombinerPattern> &Patterns) const {
+    MachineInstr &Root, SmallVectorImpl<MachineCombinerPattern> &Patterns,
+    bool DoRegPressureReduce) const {
   // Using the machine combiner in this way is potentially expensive, so
   // restrict to when aggressive optimizations are desired.
   if (Subtarget.getTargetMachine().getOptLevel() != CodeGenOpt::Aggressive)
     return false;
 
   if (getFMAPatterns(Root, Patterns))
     return true;
 
-  return TargetInstrInfo::getMachineCombinerPatterns(Root, Patterns);
+  return TargetInstrInfo::getMachineCombinerPatterns(Root, Patterns,
+                                                     DoRegPressureReduce);
 }
 
 void PPCInstrInfo::genAlternativeCodeSequence(
     MachineInstr &Root, MachineCombinerPattern Pattern,
     SmallVectorImpl<MachineInstr *> &InsInstrs,
     SmallVectorImpl<MachineInstr *> &DelInstrs,
     DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const {
   switch (Pattern) {

llvm/test/CodeGen/AArch64/O3-pipeline.ll

 ; CHECK-NEXT:       Merge disjoint stack slots
 ; CHECK-NEXT:       Local Stack Slot Allocation
 ; CHECK-NEXT:       Remove dead machine instructions
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       AArch64 Condition Optimizer
 ; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       Machine Trace Metrics
 ; CHECK-NEXT:       AArch64 Conditional Compares
+; CHECK-NEXT:       Slot index numbering
+; CHECK-NEXT:       Live Interval Analysis
+; CHECK-NEXT:       Machine Trace Metrics
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine InstCombiner
 ; CHECK-NEXT:       AArch64 Conditional Branch Tuning
 ; CHECK-NEXT:       Machine Trace Metrics
 ; CHECK-NEXT:       Early If-Conversion
 ; CHECK-NEXT:       AArch64 Store Pair Suppression
 ; CHECK-NEXT:       AArch64 SIMD instructions optimization pass
 ; CHECK-NEXT:       AArch64 Stack Tagging PreRA

llvm/test/CodeGen/AArch64/aarch64-combine-fmul-fsub.mir

bb.0.entry:
     %3:fpr64 = FMULv2f32 %0, %1
     %4:fpr64 = FSUBv2f32 killed %3, %2
     $d0 = COPY %4
     RET_ReallyLR implicit $d0
 
 ...
 # UNPROFITABLE-LABEL: name: f1_2s
 # UNPROFITABLE: %3:fpr64 = FMULv2f32 %0, %1
-# UNPROFITABLE-NEXT: FSUBv2f32 killed %3, %2
+# UNPROFITABLE-NEXT: FSUBv2f32 %3, %2
 #
 # PROFITABLE-LABEL: name: f1_2s
 # PROFITABLE: [[R1:%[0-9]+]]:fpr64 = FNEGv2f32 %2
 # PROFITABLE-NEXT: FMLAv2f32 killed [[R1]], %0, %1
 ---
 name:            f1_4s
 registers:
   - { id: 0, class: fpr128 }
bb.0.entry:
     %3:fpr128 = FMULv4f32 %0, %1
     %4:fpr128 = FSUBv4f32 killed %3, %2
     $q0 = COPY %4
     RET_ReallyLR implicit $q0
 
 ...
 # UNPROFITABLE-LABEL: name: f1_4s
 # UNPROFITABLE: %3:fpr128 = FMULv4f32 %0, %1
-# UNPROFITABLE-NEXT: FSUBv4f32 killed %3, %2
+# UNPROFITABLE-NEXT: FSUBv4f32 %3, %2
 #
 # PROFITABLE-LABEL: name: f1_4s
 # PROFITABLE: [[R1:%[0-9]+]]:fpr128 = FNEGv4f32 %2
 # PROFITABLE-NEXT: FMLAv4f32 killed [[R1]], %0, %1
 ---
 name:            f1_2d
 registers:
   - { id: 0, class: fpr128 }
bb.0.entry:
     %3:fpr128 = FMULv2f64 %0, %1
     %4:fpr128 = FSUBv2f64 killed %3, %2
     $q0 = COPY %4
     RET_ReallyLR implicit $q0
 
 ...
 # UNPROFITABLE-LABEL: name: f1_2d
 # UNPROFITABLE: %3:fpr128 = FMULv2f64 %0, %1
-# UNPROFITABLE-NEXT: FSUBv2f64 killed %3, %2
+# UNPROFITABLE-NEXT: FSUBv2f64 %3, %2
 #
 # PROFITABLE-LABEL: name: f1_2d
 # PROFITABLE: [[R1:%[0-9]+]]:fpr128 = FNEGv2f64 %2
 # PROFITABLE-NEXT: FMLAv2f64 killed [[R1]], %0, %1
 ---
 name:            f1_both_fmul_2s
 registers:
   - { id: 0, class: fpr64 }
bb.0.entry:
     %5:fpr64 = FMULv2f32 %2, %3
     %6:fpr64 = FSUBv2f32 killed %4, %5
     $q0 = COPY %6
     RET_ReallyLR implicit $q0
 
 ...
 # ALL-LABEL: name: f1_both_fmul_2s
 # ALL: %4:fpr64 = FMULv2f32 %0, %1
-# ALL-NEXT: FMLSv2f32 killed %4, %2, %3
+# ALL-NEXT: FMLSv2f32 %4, %2, %3
 ---
 name:            f1_both_fmul_4s
 registers:
   - { id: 0, class: fpr128 }
   - { id: 1, class: fpr128 }
   - { id: 2, class: fpr128 }
   - { id: 3, class: fpr128 }
   - { id: 4, class: fpr128 }
bb.0.entry:
     %5:fpr128 = FMULv4f32 %2, %3
     %6:fpr128 = FSUBv4f32 killed %4, %5
     $q0 = COPY %6
     RET_ReallyLR implicit $q0
 
 ...
 # ALL-LABEL: name: f1_both_fmul_4s
 # ALL: %4:fpr128 = FMULv4f32 %0, %1
-# ALL-NEXT: FMLSv4f32 killed %4, %2, %3
+# ALL-NEXT: FMLSv4f32 %4, %2, %3
 ---
 name:            f1_both_fmul_2d
 registers:
   - { id: 0, class: fpr128 }
   - { id: 1, class: fpr128 }
   - { id: 2, class: fpr128 }
   - { id: 3, class: fpr128 }
   - { id: 4, class: fpr128 }
bb.0.entry:
     %5:fpr128 = FMULv2f64 %2, %3
     %6:fpr128 = FSUBv2f64 killed %4, %5
     $q0 = COPY %6
     RET_ReallyLR implicit $q0
 
 ...
 # ALL-LABEL: name: f1_both_fmul_2d
 # ALL: %4:fpr128 = FMULv2f64 %0, %1
-# ALL-NEXT: FMLSv2f64 killed %4, %2, %3
+# ALL-NEXT: FMLSv2f64 %4, %2, %3
 

llvm/test/CodeGen/AArch64/machine-combiner-instr-fmf.mir

 
 # Do not create FMADD, because we don't have the contract flag on the FADD.
 
 # CHECK-LABEL: name: scalar_fmadd_contract_op0
 # CHECK:        [[C:%.*]]:fpr32 = COPY $s2
 # CHECK-NEXT:   [[B:%.*]]:fpr32 = COPY $s1
 # CHECK-NEXT:   [[A:%.*]]:fpr32 = COPY $s0
 # CHECK-NEXT:   [[MUL:%.*]]:fpr32 = contract FMULSrr [[B]], [[A]]
-# CHECK-NEXT:   fpr32 = FADDSrr killed [[MUL]], [[C]]
+# CHECK-NEXT:   fpr32 = FADDSrr [[MUL]], [[C]]
 ---
 name:            scalar_fmadd_contract_op0
 alignment:       4
 tracksRegLiveness: true
 registers:
   - { id: 0, class: fpr32 }
   - { id: 1, class: fpr32 }
   - { id: 2, class: fpr32 }

 
 # Do not create FMADD, as nsz flag does not allow it.
 #
 # CHECK-LABEL: name: scalar_fmadd_nsz
 # CHECK:        [[C:%.*]]:fpr32 = COPY $s2
 # CHECK-NEXT:   [[B:%.*]]:fpr32 = COPY $s1
 # CHECK-NEXT:   [[A:%.*]]:fpr32 = COPY $s0
 # CHECK-NEXT:   [[MUL:%.*]]:fpr32 = nsz FMULSrr [[B]], [[A]]
-# CHECK-NEXT:   fpr32 = nsz FADDSrr killed [[MUL]], [[C]]
+# CHECK-NEXT:   fpr32 = nsz FADDSrr [[MUL]], [[C]]
 
 ---
 name:            scalar_fmadd_nsz
 alignment:       4
 tracksRegLiveness: true
 registers:
   - { id: 0, class: fpr32 }
   - { id: 1, class: fpr32 }

 
 # Do not create FMLA, because we don't have the contract flag on the FADD.
 #
 # CHECK-LABEL: name: vector_fmadd_contract_op0
 # CHECK:       [[C:%.*]]:fpr128 = COPY $q2
 # CHECK-NEXT:  [[B:%.*]]:fpr128 = COPY $q1
 # CHECK-NEXT:  [[A:%.*]]:fpr128 = COPY $q0
 # CHECK-NEXT:  [[MUL:%.*]]:fpr128 = contract FMULv2f64 [[B]], [[A]]
-# CHECK-NEXT:  fpr128 = FADDv2f64 killed [[MUL]], [[C]]
+# CHECK-NEXT:  fpr128 = FADDv2f64 [[MUL]], [[C]]
 ---
 name:            vector_fmadd_contract_op0
 alignment:       4
 tracksRegLiveness: true
 registers:
   - { id: 0, class: fpr128 }
   - { id: 1, class: fpr128 }
   - { id: 2, class: fpr128 }

 
 # Do not create FMLA, as nsz flag does not allow it.
 #
 # CHECK-LABEL: name: vector_fmadd_nsz
 # CHECK:       [[C:%.*]]:fpr128 = COPY $q2
 # CHECK-NEXT:  [[B:%.*]]:fpr128 = COPY $q1
 # CHECK-NEXT:  [[A:%.*]]:fpr128 = COPY $q0
 # CHECK-NEXT:  [[MUL:%.*]]:fpr128 = nsz FMULv2f64 [[B]], [[A]]
-# CHECK-NEXT:  fpr128 = nsz FADDv2f64 killed [[MUL]], [[C]]
+# CHECK-NEXT:  fpr128 = nsz FADDv2f64 [[MUL]], [[C]]
 ---
 name:            vector_fmadd_nsz
 alignment:       4
 tracksRegLiveness: true
 registers:
   - { id: 0, class: fpr128 }
   - { id: 1, class: fpr128 }
   - { id: 2, class: fpr128 }

llvm/test/CodeGen/PowerPC/opt-cmp-inst-cr0-live.ll

 ; RUN: llc -verify-machineinstrs -print-before=peephole-opt -print-after=peephole-opt -mtriple=powerpc64-unknown-linux-gnu -o /dev/null 2>&1 < %s | FileCheck %s
 ; RUN: llc -verify-machineinstrs -print-before=peephole-opt -print-after=peephole-opt -mtriple=powerpc64le-unknown-linux-gnu -o /dev/null 2>&1 < %s | FileCheck %s
 
 ; CHECK-LABEL: fn1
 define signext i32 @fn1(i32 %baz) {
   %1 = mul nsw i32 %baz, 208
   %2 = zext i32 %1 to i64
   %3 = shl i64 %2, 48
   %4 = ashr exact i64 %3, 48
-; CHECK: RLWINM8 killed {{[^,]+}}, 0, 16, 27
+; CHECK: RLWINM8 {{[^,]+}}, 0, 16, 27
 ; CHECK: CMPLDI
 ; CHECK: BCC
 
 ; CHECK: ANDI8_rec {{[^,]+}}, 65520, implicit-def $cr0
 ; CHECK: COPY killed $cr0
 ; CHECK: BCC
   %5 = icmp eq i64 %4, 0
   br i1 %5, label %foo, label %bar
 
 foo:
   ret i32 1
 
 bar:
   ret i32 0
 }
 
 ; CHECK-LABEL: fn2
 define signext i32 @fn2(i64 %a, i64 %b) {
 ; CHECK: OR8_rec {{[^, ]+}}, {{[^, ]+}}, implicit-def $cr0
 ; CHECK: [[CREG:[^, ]+]]:crrc = COPY killed $cr
-; CHECK: BCC 12, killed [[CREG]]
+; CHECK: BCC 12, [[CREG]]
   %1 = or i64 %b, %a
   %2 = icmp sgt i64 %1, -1
   br i1 %2, label %foo, label %bar
 
 foo:
   ret i32 1
 
 bar:
   ret i32 0
 }
 
 ; CHECK-LABEL: fn3
 define signext i32 @fn3(i32 %a) {
-; CHECK: ANDI_rec killed {{[%0-9]+}}{{[^,]*}}, 10, implicit-def $cr0
+; CHECK: ANDI_rec {{[%0-9]+}}{{[^,]*}}, 10, implicit-def $cr0
 ; CHECK: [[CREG:[^, ]+]]:crrc = COPY $cr0
-; CHECK: BCC 76, killed [[CREG]]
+; CHECK: BCC 76, [[CREG]]
   %1 = and i32 %a, 10
   %2 = icmp ne i32 %1, 0
   br i1 %2, label %foo, label %bar
 
 foo:
   ret i32 1
 
 bar:

llvm/test/CodeGen/X86/opt-pipeline.ll

 ; CHECK-NEXT:       Slot index numbering
 ; CHECK-NEXT:       Merge disjoint stack slots
 ; CHECK-NEXT:       Local Stack Slot Allocation
 ; CHECK-NEXT:       Remove dead machine instructions
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       Machine Trace Metrics
 ; CHECK-NEXT:       Early If-Conversion
+; CHECK-NEXT:       Slot index numbering
+; CHECK-NEXT:       Live Interval Analysis
+; CHECK-NEXT:       Machine Trace Metrics
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine InstCombiner
 ; CHECK-NEXT:       X86 cmov Conversion
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Machine Natural Loop Construction
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Early Machine Loop Invariant Code Motion
 ; CHECK-NEXT:       MachineDominator Tree Construction

llvm/test/DebugInfo/X86/machinecse-wrongdebug-hoist.ll

 ; RUN: llc %s -o - -print-after=machine-cse -mtriple=x86_64-- 2>&1 | FileCheck %s --match-full-lines
 
-; CHECK: %5:gr32 = SUB32ri8 %0:gr32(tied-def 0), 1, implicit-def $eflags, debug-location !24; a.c:3:13
+; CHECK: dead %5:gr32 = SUB32ri8 %0:gr32(tied-def 0), 1, implicit-def $eflags, debug-location !24; a.c:3:13
 ; CHECK-NEXT: %10:gr32 = MOVSX32rr8 %4:gr8
 ; CHECK-NEXT: JCC_1 %bb.2, 15, implicit $eflags, debug-location !25; a.c:3:18
 
 target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.15.0"
 
 @a = local_unnamed_addr global i32 0, align 4, !dbg !0