LCOV - code coverage report
Current view: top level - lib/CodeGen - MachineCombiner.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 181 181 100.0 %
Date: 2018-06-17 00:07:59 Functions: 20 20 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // The machine combiner pass uses machine trace metrics to ensure the combined
      11             : // instructions do not lengthen the critical path or the resource depth.
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/ADT/DenseMap.h"
      15             : #include "llvm/ADT/Statistic.h"
      16             : #include "llvm/CodeGen/MachineDominators.h"
      17             : #include "llvm/CodeGen/MachineFunction.h"
      18             : #include "llvm/CodeGen/MachineFunctionPass.h"
      19             : #include "llvm/CodeGen/MachineLoopInfo.h"
      20             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      21             : #include "llvm/CodeGen/MachineTraceMetrics.h"
      22             : #include "llvm/CodeGen/Passes.h"
      23             : #include "llvm/CodeGen/TargetInstrInfo.h"
      24             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      25             : #include "llvm/CodeGen/TargetSchedule.h"
      26             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      27             : #include "llvm/Support/CommandLine.h"
      28             : #include "llvm/Support/Debug.h"
      29             : #include "llvm/Support/raw_ostream.h"
      30             : 
      31             : using namespace llvm;
      32             : 
      33             : #define DEBUG_TYPE "machine-combiner"
      34             : 
      35             : STATISTIC(NumInstCombined, "Number of machineinst combined");
      36             : 
      37             : static cl::opt<unsigned>
      38      101169 : inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
      39      101169 :               cl::desc("Incremental depth computation will be used for basic "
      40      303507 :                        "blocks with more instructions."), cl::init(500));
      41             : 
      42      101169 : static cl::opt<bool> dump_intrs("machine-combiner-dump-subst-intrs", cl::Hidden,
      43      101169 :                                 cl::desc("Dump all substituted intrs"),
      44      303507 :                                 cl::init(false));
      45             : 
      46             : #ifdef EXPENSIVE_CHECKS
      47             : static cl::opt<bool> VerifyPatternOrder(
      48             :     "machine-combiner-verify-pattern-order", cl::Hidden,
      49             :     cl::desc(
      50             :         "Verify that the generated patterns are ordered by increasing latency"),
      51             :     cl::init(true));
      52             : #else
      53      101169 : static cl::opt<bool> VerifyPatternOrder(
      54             :     "machine-combiner-verify-pattern-order", cl::Hidden,
      55      101169 :     cl::desc(
      56             :         "Verify that the generated patterns are ordered by increasing latency"),
      57      303507 :     cl::init(false));
      58             : #endif
      59             : 
      60             : namespace {
      61       30723 : class MachineCombiner : public MachineFunctionPass {
      62             :   const TargetSubtargetInfo *STI;
      63             :   const TargetInstrInfo *TII;
      64             :   const TargetRegisterInfo *TRI;
      65             :   MCSchedModel SchedModel;
      66             :   MachineRegisterInfo *MRI;
      67             :   MachineLoopInfo *MLI; // Current MachineLoopInfo
      68             :   MachineTraceMetrics *Traces;
      69             :   MachineTraceMetrics::Ensemble *MinInstr;
      70             : 
      71             :   TargetSchedModel TSchedModel;
      72             : 
      73             :   /// True if optimizing for code size.
      74             :   bool OptSize;
      75             : 
      76             : public:
      77             :   static char ID;
      78       10281 :   MachineCombiner() : MachineFunctionPass(ID) {
      79       10281 :     initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
      80       10281 :   }
      81             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
      82             :   bool runOnMachineFunction(MachineFunction &MF) override;
      83       10248 :   StringRef getPassName() const override { return "Machine InstCombiner"; }
      84             : 
      85             : private:
      86             :   bool doSubstitute(unsigned NewSize, unsigned OldSize);
      87             :   bool combineInstructions(MachineBasicBlock *);
      88             :   MachineInstr *getOperandDef(const MachineOperand &MO);
      89             :   unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
      90             :                     DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
      91             :                     MachineTraceMetrics::Trace BlockTrace);
      92             :   unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
      93             :                       MachineTraceMetrics::Trace BlockTrace);
      94             :   bool
      95             :   improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
      96             :                           MachineTraceMetrics::Trace BlockTrace,
      97             :                           SmallVectorImpl<MachineInstr *> &InsInstrs,
      98             :                           SmallVectorImpl<MachineInstr *> &DelInstrs,
      99             :                           DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
     100             :                           MachineCombinerPattern Pattern, bool SlackIsAccurate);
     101             :   bool preservesResourceLen(MachineBasicBlock *MBB,
     102             :                             MachineTraceMetrics::Trace BlockTrace,
     103             :                             SmallVectorImpl<MachineInstr *> &InsInstrs,
     104             :                             SmallVectorImpl<MachineInstr *> &DelInstrs);
     105             :   void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
     106             :                      SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
     107             :   std::pair<unsigned, unsigned>
     108             :   getLatenciesForInstrSequences(MachineInstr &MI,
     109             :                                 SmallVectorImpl<MachineInstr *> &InsInstrs,
     110             :                                 SmallVectorImpl<MachineInstr *> &DelInstrs,
     111             :                                 MachineTraceMetrics::Trace BlockTrace);
     112             : 
     113             :   void verifyPatternOrder(MachineBasicBlock *MBB, MachineInstr &Root,
     114             :                           SmallVector<MachineCombinerPattern, 16> &Patterns);
     115             : };
     116             : }
     117             : 
     118             : char MachineCombiner::ID = 0;
     119             : char &llvm::MachineCombinerID = MachineCombiner::ID;
     120             : 
     121       26770 : INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
     122             :                       "Machine InstCombiner", false, false)
     123       26770 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
     124       26770 : INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
     125      168674 : INITIALIZE_PASS_END(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner",
     126             :                     false, false)
     127             : 
     128       10232 : void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
     129       10232 :   AU.setPreservesCFG();
     130             :   AU.addPreserved<MachineDominatorTree>();
     131             :   AU.addRequired<MachineLoopInfo>();
     132             :   AU.addPreserved<MachineLoopInfo>();
     133             :   AU.addRequired<MachineTraceMetrics>();
     134             :   AU.addPreserved<MachineTraceMetrics>();
     135       10232 :   MachineFunctionPass::getAnalysisUsage(AU);
     136       10232 : }
     137             : 
     138        2469 : MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
     139             :   MachineInstr *DefInstr = nullptr;
     140             :   // We need a virtual register definition.
     141        4938 :   if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
     142        2469 :     DefInstr = MRI->getUniqueVRegDef(MO.getReg());
     143             :   // PHI's have no depth etc.
     144        2469 :   if (DefInstr && DefInstr->isPHI())
     145             :     DefInstr = nullptr;
     146        2469 :   return DefInstr;
     147             : }
     148             : 
     149             : /// Computes depth of instructions in vector \InsInstr.
     150             : ///
     151             : /// \param InsInstrs is a vector of machine instructions
     152             : /// \param InstrIdxForVirtReg is a dense map of virtual register to index
     153             : /// of defining machine instruction in \p InsInstrs
     154             : /// \param BlockTrace is a trace of machine instructions
     155             : ///
     156             : /// \returns Depth of last instruction in \InsInstrs ("NewRoot")
     157             : unsigned
     158         823 : MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
     159             :                           DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
     160             :                           MachineTraceMetrics::Trace BlockTrace) {
     161             :   SmallVector<unsigned, 16> InstrDepth;
     162             :   assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
     163             :          "Missing machine model\n");
     164             : 
     165             :   // For each instruction in the new sequence compute the depth based on the
     166             :   // operands. Use the trace information when possible. For new operands which
     167             :   // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
     168        4055 :   for (auto *InstrPtr : InsInstrs) { // for each Use
     169        1616 :     unsigned IDepth = 0;
     170       12188 :     for (const MachineOperand &MO : InstrPtr->operands()) {
     171             :       // Check for virtual register operand.
     172       10572 :       if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
     173        2024 :         continue;
     174        4878 :       if (!MO.isUse())
     175             :         continue;
     176             :       unsigned DepthOp = 0;
     177             :       unsigned LatencyOp = 0;
     178             :       DenseMap<unsigned, unsigned>::iterator II =
     179        3262 :           InstrIdxForVirtReg.find(MO.getReg());
     180        3262 :       if (II != InstrIdxForVirtReg.end()) {
     181             :         // Operand is new virtual register not in trace
     182             :         assert(II->second < InstrDepth.size() && "Bad Index");
     183        1586 :         MachineInstr *DefInstr = InsInstrs[II->second];
     184             :         assert(DefInstr &&
     185             :                "There must be a definition for a new virtual register");
     186         793 :         DepthOp = InstrDepth[II->second];
     187         793 :         int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
     188         793 :         int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
     189         793 :         LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
     190             :                                                       InstrPtr, UseIdx);
     191             :       } else {
     192        2469 :         MachineInstr *DefInstr = getOperandDef(MO);
     193        2469 :         if (DefInstr) {
     194        2450 :           DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
     195        7350 :           LatencyOp = TSchedModel.computeOperandLatency(
     196        2450 :               DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
     197        2450 :               InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
     198             :         }
     199             :       }
     200        6524 :       IDepth = std::max(IDepth, DepthOp + LatencyOp);
     201             :     }
     202        1616 :     InstrDepth.push_back(IDepth);
     203             :   }
     204         823 :   unsigned NewRootIdx = InsInstrs.size() - 1;
     205        2469 :   return InstrDepth[NewRootIdx];
     206             : }
     207             : 
     208             : /// Computes instruction latency as max of latency of defined operands.
     209             : ///
     210             : /// \param Root is a machine instruction that could be replaced by NewRoot.
     211             : /// It is used to compute a more accurate latency information for NewRoot in
     212             : /// case there is a dependent instruction in the same trace (\p BlockTrace)
     213             : /// \param NewRoot is the instruction for which the latency is computed
     214             : /// \param BlockTrace is a trace of machine instructions
     215             : ///
     216             : /// \returns Latency of \p NewRoot
     217         400 : unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
     218             :                                      MachineTraceMetrics::Trace BlockTrace) {
     219             :   assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
     220             :          "Missing machine model\n");
     221             : 
     222             :   // Check each definition in NewRoot and compute the latency
     223         400 :   unsigned NewRootLatency = 0;
     224             : 
     225        3056 :   for (const MachineOperand &MO : NewRoot->operands()) {
     226             :     // Check for virtual register operand.
     227        2656 :     if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
     228         976 :       continue;
     229        1280 :     if (!MO.isDef())
     230         880 :       continue;
     231             :     // Get the first instruction that uses MO
     232         400 :     MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
     233             :     RI++;
     234         400 :     MachineInstr *UseMO = RI->getParent();
     235         400 :     unsigned LatencyOp = 0;
     236         400 :     if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
     237        1197 :       LatencyOp = TSchedModel.computeOperandLatency(
     238         399 :           NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
     239         399 :           UseMO->findRegisterUseOperandIdx(MO.getReg()));
     240             :     } else {
     241           1 :       LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
     242             :     }
     243         400 :     NewRootLatency = std::max(NewRootLatency, LatencyOp);
     244             :   }
     245         400 :   return NewRootLatency;
     246             : }
     247             : 
     248             : /// The combiner's goal may differ based on which pattern it is attempting
     249             : /// to optimize.
     250             : enum class CombinerObjective {
     251             :   MustReduceDepth, // The data dependency chain must be improved.
     252             :   Default          // The critical path must not be lengthened.
     253             : };
     254             : 
     255             : static CombinerObjective getCombinerObjective(MachineCombinerPattern P) {
     256             :   // TODO: If C++ ever gets a real enum class, make this part of the
     257             :   // MachineCombinerPattern class.
     258         823 :   switch (P) {
     259             :   case MachineCombinerPattern::REASSOC_AX_BY:
     260             :   case MachineCombinerPattern::REASSOC_AX_YB:
     261             :   case MachineCombinerPattern::REASSOC_XA_BY:
     262             :   case MachineCombinerPattern::REASSOC_XA_YB:
     263             :     return CombinerObjective::MustReduceDepth;
     264             :   default:
     265             :     return CombinerObjective::Default;
     266             :   }
     267             : }
     268             : 
     269             : /// Estimate the latency of the new and original instruction sequence by summing
     270             : /// up the latencies of the inserted and deleted instructions. This assumes
     271             : /// that the inserted and deleted instructions are dependent instruction chains,
     272             : /// which might not hold in all cases.
     273         400 : std::pair<unsigned, unsigned> MachineCombiner::getLatenciesForInstrSequences(
     274             :     MachineInstr &MI, SmallVectorImpl<MachineInstr *> &InsInstrs,
     275             :     SmallVectorImpl<MachineInstr *> &DelInstrs,
     276             :     MachineTraceMetrics::Trace BlockTrace) {
     277             :   assert(!InsInstrs.empty() && "Only support sequences that insert instrs.");
     278             :   unsigned NewRootLatency = 0;
     279             :   // NewRoot is the last instruction in the \p InsInstrs vector.
     280         400 :   MachineInstr *NewRoot = InsInstrs.back();
     281        1868 :   for (unsigned i = 0; i < InsInstrs.size() - 1; i++)
     282         712 :     NewRootLatency += TSchedModel.computeInstrLatency(InsInstrs[i]);
     283         400 :   NewRootLatency += getLatency(&MI, NewRoot, BlockTrace);
     284             : 
     285             :   unsigned RootLatency = 0;
     286        2000 :   for (auto I : DelInstrs)
     287         800 :     RootLatency += TSchedModel.computeInstrLatency(I);
     288             : 
     289         400 :   return {NewRootLatency, RootLatency};
     290             : }
     291             : 
     292             : /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
     293             : /// The new code sequence ends in MI NewRoot. A necessary condition for the new
     294             : /// sequence to replace the old sequence is that it cannot lengthen the critical
     295             : /// path. The definition of "improve" may be restricted by specifying that the
     296             : /// new path improves the data dependency chain (MustReduceDepth).
     297         823 : bool MachineCombiner::improvesCriticalPathLen(
     298             :     MachineBasicBlock *MBB, MachineInstr *Root,
     299             :     MachineTraceMetrics::Trace BlockTrace,
     300             :     SmallVectorImpl<MachineInstr *> &InsInstrs,
     301             :     SmallVectorImpl<MachineInstr *> &DelInstrs,
     302             :     DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
     303             :     MachineCombinerPattern Pattern,
     304             :     bool SlackIsAccurate) {
     305             :   assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
     306             :          "Missing machine model\n");
     307             :   // Get depth and latency of NewRoot and Root.
     308         823 :   unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
     309         823 :   unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
     310             : 
     311             :   LLVM_DEBUG(dbgs() << "  Dependence data for " << *Root << "\tNewRootDepth: "
     312             :                     << NewRootDepth << "\tRootDepth: " << RootDepth);
     313             : 
     314             :   // For a transform such as reassociation, the cost equation is
     315             :   // conservatively calculated so that we must improve the depth (data
     316             :   // dependency cycles) in the critical path to proceed with the transform.
     317             :   // Being conservative also protects against inaccuracies in the underlying
     318             :   // machine trace metrics and CPU models.
     319             :   if (getCombinerObjective(Pattern) == CombinerObjective::MustReduceDepth) {
     320             :     LLVM_DEBUG(dbgs() << "\tIt MustReduceDepth ");
     321             :     LLVM_DEBUG(NewRootDepth < RootDepth
     322             :                    ? dbgs() << "\t  and it does it\n"
     323             :                    : dbgs() << "\t  but it does NOT do it\n");
     324         781 :     return NewRootDepth < RootDepth;
     325             :   }
     326             : 
     327             :   // A more flexible cost calculation for the critical path includes the slack
     328             :   // of the original code sequence. This may allow the transform to proceed
     329             :   // even if the instruction depths (data dependency cycles) become worse.
     330             : 
     331             :   // Account for the latency of the inserted and deleted instructions by
     332             :   unsigned NewRootLatency, RootLatency;
     333             :   std::tie(NewRootLatency, RootLatency) =
     334          84 :       getLatenciesForInstrSequences(*Root, InsInstrs, DelInstrs, BlockTrace);
     335             : 
     336          42 :   unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
     337          42 :   unsigned NewCycleCount = NewRootDepth + NewRootLatency;
     338          42 :   unsigned OldCycleCount =
     339          42 :       RootDepth + RootLatency + (SlackIsAccurate ? RootSlack : 0);
     340             :   LLVM_DEBUG(dbgs() << "\n\tNewRootLatency: " << NewRootLatency
     341             :                     << "\tRootLatency: " << RootLatency << "\n\tRootSlack: "
     342             :                     << RootSlack << " SlackIsAccurate=" << SlackIsAccurate
     343             :                     << "\n\tNewRootDepth + NewRootLatency = " << NewCycleCount
     344             :                     << "\n\tRootDepth + RootLatency + RootSlack = "
     345             :                     << OldCycleCount;);
     346             :   LLVM_DEBUG(NewCycleCount <= OldCycleCount
     347             :                  ? dbgs() << "\n\t  It IMPROVES PathLen because"
     348             :                  : dbgs() << "\n\t  It DOES NOT improve PathLen because");
     349             :   LLVM_DEBUG(dbgs() << "\n\t\tNewCycleCount = " << NewCycleCount
     350             :                     << ", OldCycleCount = " << OldCycleCount << "\n");
     351             : 
     352          42 :   return NewCycleCount <= OldCycleCount;
     353             : }
     354             : 
     355             : /// helper routine to convert instructions into SC
     356         590 : void MachineCombiner::instr2instrSC(
     357             :     SmallVectorImpl<MachineInstr *> &Instrs,
     358             :     SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
     359        2890 :   for (auto *InstrPtr : Instrs) {
     360        1150 :     unsigned Opc = InstrPtr->getOpcode();
     361        2300 :     unsigned Idx = TII->get(Opc).getSchedClass();
     362        2300 :     const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
     363        1150 :     InstrsSC.push_back(SC);
     364             :   }
     365         590 : }
     366             : 
     367             : /// True when the new instructions do not increase resource length
     368         325 : bool MachineCombiner::preservesResourceLen(
     369             :     MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
     370             :     SmallVectorImpl<MachineInstr *> &InsInstrs,
     371             :     SmallVectorImpl<MachineInstr *> &DelInstrs) {
     372         325 :   if (!TSchedModel.hasInstrSchedModel())
     373             :     return true;
     374             : 
     375             :   // Compute current resource length
     376             : 
     377             :   //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
     378             :   SmallVector <const MachineBasicBlock *, 1> MBBarr;
     379         295 :   MBBarr.push_back(MBB);
     380         295 :   unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
     381             : 
     382             :   // Deal with SC rather than Instructions.
     383             :   SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
     384             :   SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
     385             : 
     386         295 :   instr2instrSC(InsInstrs, InsInstrsSC);
     387         295 :   instr2instrSC(DelInstrs, DelInstrsSC);
     388             : 
     389         295 :   ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
     390         295 :   ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
     391             : 
     392             :   // Compute new resource length.
     393             :   unsigned ResLenAfterCombine =
     394         295 :       BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
     395             : 
     396             :   LLVM_DEBUG(dbgs() << "\t\tResource length before replacement: "
     397             :                     << ResLenBeforeCombine
     398             :                     << " and after: " << ResLenAfterCombine << "\n";);
     399             :   LLVM_DEBUG(
     400             :       ResLenAfterCombine <= ResLenBeforeCombine
     401             :           ? dbgs() << "\t\t  As result it IMPROVES/PRESERVES Resource Length\n"
     402             :           : dbgs() << "\t\t  As result it DOES NOT improve/preserve Resource "
     403             :                       "Length\n");
     404             : 
     405         295 :   return ResLenAfterCombine <= ResLenBeforeCombine;
     406             : }
     407             : 
     408             : /// \returns true when new instruction sequence should be generated
     409             : /// independent if it lengthens critical path or not
     410             : bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
     411        3115 :   if (OptSize && (NewSize < OldSize))
     412             :     return true;
     413        3075 :   if (!TSchedModel.hasInstrSchedModelOrItineraries())
     414             :     return true;
     415             :   return false;
     416             : }
     417             : 
     418             : /// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
     419             : /// depths if requested.
     420             : ///
     421             : /// \param MBB basic block to insert instructions in
     422             : /// \param MI current machine instruction
     423             : /// \param InsInstrs new instructions to insert in \p MBB
     424             : /// \param DelInstrs instruction to delete from \p MBB
     425             : /// \param MinInstr is a pointer to the machine trace information
     426             : /// \param RegUnits set of live registers, needed to compute instruction depths
     427             : /// \param IncrementalUpdate if true, compute instruction depths incrementally,
     428             : ///                          otherwise invalidate the trace
     429        2641 : static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
     430             :                                      SmallVector<MachineInstr *, 16> InsInstrs,
     431             :                                      SmallVector<MachineInstr *, 16> DelInstrs,
     432             :                                      MachineTraceMetrics::Ensemble *MinInstr,
     433             :                                      SparseSet<LiveRegUnit> &RegUnits,
     434             :                                      bool IncrementalUpdate) {
     435       12747 :   for (auto *InstrPtr : InsInstrs)
     436             :     MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
     437             : 
     438       13205 :   for (auto *InstrPtr : DelInstrs) {
     439        5282 :     InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
     440             :     // Erase all LiveRegs defined by the removed instruction
     441        5576 :     for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
     442         294 :       if (I->MI == InstrPtr)
     443             :         I = RegUnits.erase(I);
     444             :       else
     445         294 :         I++;
     446             :     }
     447             :   }
     448             : 
     449        2641 :   if (IncrementalUpdate)
     450         566 :     for (auto *InstrPtr : InsInstrs)
     451         226 :       MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
     452             :   else
     453        2527 :     MinInstr->invalidate(MBB);
     454             : 
     455             :   NumInstCombined++;
     456        2641 : }
     457             : 
     458             : // Check that the difference between original and new latency is decreasing for
     459             : // later patterns. This helps to discover sub-optimal pattern orderings.
     460         186 : void MachineCombiner::verifyPatternOrder(
     461             :     MachineBasicBlock *MBB, MachineInstr &Root,
     462             :     SmallVector<MachineCombinerPattern, 16> &Patterns) {
     463             :   long PrevLatencyDiff = std::numeric_limits<long>::max();
     464             :   (void)PrevLatencyDiff; // Variable is used in assert only.
     465         902 :   for (auto P : Patterns) {
     466             :     SmallVector<MachineInstr *, 16> InsInstrs;
     467             :     SmallVector<MachineInstr *, 16> DelInstrs;
     468             :     DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
     469         716 :     TII->genAlternativeCodeSequence(Root, P, InsInstrs, DelInstrs,
     470         358 :                                     InstrIdxForVirtReg);
     471             :     // Found pattern, but did not generate alternative sequence.
     472             :     // This can happen e.g. when an immediate could not be materialized
     473             :     // in a single instruction.
     474         358 :     if (InsInstrs.empty() || !TSchedModel.hasInstrSchedModelOrItineraries())
     475             :       continue;
     476             : 
     477             :     unsigned NewRootLatency, RootLatency;
     478         716 :     std::tie(NewRootLatency, RootLatency) = getLatenciesForInstrSequences(
     479         358 :         Root, InsInstrs, DelInstrs, MinInstr->getTrace(MBB));
     480             :     long CurrentLatencyDiff = ((long)RootLatency) - ((long)NewRootLatency);
     481             :     assert(CurrentLatencyDiff <= PrevLatencyDiff &&
     482             :            "Current pattern is better than previous pattern.");
     483             :     PrevLatencyDiff = CurrentLatencyDiff;
     484             :   }
     485         186 : }
     486             : 
     487             : /// Substitute a slow code sequence with a faster one by
     488             : /// evaluating instruction combining pattern.
     489             : /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
     490             : /// combining based on machine trace metrics. Only combine a sequence of
     491             : /// instructions  when this neither lengthens the critical path nor increases
     492             : /// resource pressure. When optimizing for codesize always combine when the new
     493             : /// sequence is shorter.
     494      261616 : bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
     495             :   bool Changed = false;
     496             :   LLVM_DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
     497             : 
     498             :   bool IncrementalUpdate = false;
     499      261616 :   auto BlockIter = MBB->begin();
     500             :   decltype(BlockIter) LastUpdate;
     501             :   // Check if the block is in a loop.
     502      261616 :   const MachineLoop *ML = MLI->getLoopFor(MBB);
     503      261616 :   if (!MinInstr)
     504      122843 :     MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
     505             : 
     506      261616 :   SparseSet<LiveRegUnit> RegUnits;
     507      261616 :   RegUnits.setUniverse(TRI->getNumRegUnits());
     508             : 
     509     3397686 :   while (BlockIter != MBB->end()) {
     510             :     auto &MI = *BlockIter++;
     511             :     SmallVector<MachineCombinerPattern, 16> Patterns;
     512             :     // The motivating example is:
     513             :     //
     514             :     //     MUL  Other        MUL_op1 MUL_op2  Other
     515             :     //      \    /               \      |    /
     516             :     //      ADD/SUB      =>        MADD/MSUB
     517             :     //      (=Root)                (=NewRoot)
     518             : 
     519             :     // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
     520             :     // usually beneficial for code size it unfortunately can hurt performance
     521             :     // when the ADD is on the critical path, but the MUL is not. With the
     522             :     // substitution the MUL becomes part of the critical path (in form of the
     523             :     // MADD) and can lengthen it on architectures where the MADD latency is
     524             :     // longer than the ADD latency.
     525             :     //
     526             :     // For each instruction we check if it can be the root of a combiner
     527             :     // pattern. Then for each pattern the new code sequence in form of MI is
     528             :     // generated and evaluated. When the efficiency criteria (don't lengthen
     529             :     // critical path, don't use more resources) is met the new sequence gets
     530             :     // hooked up into the basic block before the old sequence is removed.
     531             :     //
     532             :     // The algorithm does not try to evaluate all patterns and pick the best.
     533             :     // This is only an artificial restriction though. In practice there is
     534             :     // mostly one pattern, and getMachineCombinerPatterns() can order patterns
     535             :     // based on an internal cost heuristic. If
     536             :     // machine-combiner-verify-pattern-order is enabled, all patterns are
     537             :     // checked to ensure later patterns do not provide better latency savings.
     538             : 
     539     3136070 :     if (!TII->getMachineCombinerPatterns(MI, Patterns))
     540             :       continue;
     541             : 
     542        2795 :     if (VerifyPatternOrder)
     543         186 :       verifyPatternOrder(MBB, MI, Patterns);
     544             : 
     545        3793 :     for (auto P : Patterns) {
     546             :       SmallVector<MachineInstr *, 16> InsInstrs;
     547             :       SmallVector<MachineInstr *, 16> DelInstrs;
     548             :       DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
     549        6280 :       TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
     550        3140 :                                       InstrIdxForVirtReg);
     551        3140 :       unsigned NewInstCount = InsInstrs.size();
     552        3140 :       unsigned OldInstCount = DelInstrs.size();
     553             :       // Found pattern, but did not generate alternative sequence.
     554             :       // This can happen e.g. when an immediate could not be materialized
     555             :       // in a single instruction.
     556        3140 :       if (!NewInstCount)
     557             :         continue;
     558             : 
     559             :       LLVM_DEBUG(if (dump_intrs) {
     560             :         dbgs() << "\tFor the Pattern (" << (int)P << ") these instructions could be removed\n";
     561             :         for (auto const *InstrPtr : DelInstrs) {
     562             :           dbgs() << "\t\t" << STI->getSchedInfoStr(*InstrPtr) << ": ";
     563             :           InstrPtr->print(dbgs(), false, false, false, TII);
     564             :         }
     565             :         dbgs() << "\tThese instructions could replace the removed ones\n";
     566             :         for (auto const *InstrPtr : InsInstrs) {
     567             :           dbgs() << "\t\t" << STI->getSchedInfoStr(*InstrPtr) << ": ";
     568             :           InstrPtr->print(dbgs(), false, false, false, TII);
     569             :         }
     570             :       });
     571             : 
     572             :       bool SubstituteAlways = false;
     573        3139 :       if (ML && TII->isThroughputPattern(P))
     574             :         SubstituteAlways = true;
     575             : 
     576        3139 :       if (IncrementalUpdate) {
     577             :         // Update depths since the last incremental update.
     578          68 :         MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
     579          68 :         LastUpdate = BlockIter;
     580             :       }
     581             : 
     582             :       // Substitute when we optimize for codesize and the new sequence has
     583             :       // fewer instructions OR
     584             :       // the new sequence neither lengthens the critical path nor increases
     585             :       // resource pressure.
     586        3139 :       if (SubstituteAlways || doSubstitute(NewInstCount, OldInstCount)) {
     587        9264 :         insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
     588             :                                  RegUnits, IncrementalUpdate);
     589             :         // Eagerly stop after the first pattern fires.
     590             :         Changed = true;
     591        2316 :         break;
     592             :       } else {
     593             :         // For big basic blocks, we only compute the full trace the first time
     594             :         // we hit this. We do not invalidate the trace, but instead update the
     595             :         // instruction depths incrementally.
     596             :         // NOTE: Only the instruction depths up to MI are accurate. All other
     597             :         // trace information is not updated.
     598         823 :         MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
     599         823 :         Traces->verifyAnalysis();
     600         823 :         if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
     601             :                                     InstrIdxForVirtReg, P,
     602        1971 :                                     !IncrementalUpdate) &&
     603         325 :             preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
     604         325 :           if (MBB->size() > inc_threshold) {
     605             :             // Use incremental depth updates for basic blocks above treshold
     606             :             IncrementalUpdate = true;
     607         114 :             LastUpdate = BlockIter;
     608             :           }
     609             : 
     610        1300 :           insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
     611             :                                    RegUnits, IncrementalUpdate);
     612             : 
     613             :           // Eagerly stop after the first pattern fires.
     614             :           Changed = true;
     615         325 :           break;
     616             :         }
     617             :         // Cleanup instructions of the alternative code sequence. There is no
     618             :         // use for them.
     619         498 :         MachineFunction *MF = MBB->getParent();
     620        2490 :         for (auto *InstrPtr : InsInstrs)
     621         996 :           MF->DeleteMachineInstr(InstrPtr);
     622             :       }
     623         498 :       InstrIdxForVirtReg.clear();
     624             :     }
     625             :   }
     626             : 
     627      261616 :   if (Changed && IncrementalUpdate)
     628          78 :     Traces->invalidate(MBB);
     629      261616 :   return Changed;
     630             : }
     631             : 
     632      122843 : bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
     633      122843 :   STI = &MF.getSubtarget();
     634      122843 :   TII = STI->getInstrInfo();
     635      122843 :   TRI = STI->getRegisterInfo();
     636      122843 :   SchedModel = STI->getSchedModel();
     637      122843 :   TSchedModel.init(STI);
     638      122843 :   MRI = &MF.getRegInfo();
     639      122843 :   MLI = &getAnalysis<MachineLoopInfo>();
     640      122843 :   Traces = &getAnalysis<MachineTraceMetrics>();
     641      122843 :   MinInstr = nullptr;
     642      122843 :   OptSize = MF.getFunction().optForSize();
     643             : 
     644             :   LLVM_DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
     645      122843 :   if (!TII->useMachineCombiner()) {
     646             :     LLVM_DEBUG(
     647             :         dbgs()
     648             :         << "  Skipping pass: Target does not support machine combiner\n");
     649             :     return false;
     650             :   }
     651             : 
     652             :   bool Changed = false;
     653             : 
     654             :   // Try to combine instructions.
     655      384459 :   for (auto &MBB : MF)
     656      261616 :     Changed |= combineInstructions(&MBB);
     657             : 
     658             :   return Changed;
     659      303507 : }

Generated by: LCOV version 1.13