LCOV - code coverage report
Current view: top level - lib/CodeGen - TargetSchedule.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 170 178 95.5 %
Date: 2017-09-14 15:23:50 Functions: 18 19 94.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/Target/TargetSchedule.cpp - Sched Machine Model ---------------===//
       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             : // This file implements a wrapper around MCSchedModel that allows the interface
      11             : // to benefit from information currently only available in TargetInstrInfo.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "llvm/CodeGen/TargetSchedule.h"
      16             : #include "llvm/CodeGen/MachineFunction.h"
      17             : #include "llvm/CodeGen/MachineInstr.h"
      18             : #include "llvm/CodeGen/MachineOperand.h"
      19             : #include "llvm/MC/MCInstrDesc.h"
      20             : #include "llvm/MC/MCInstrItineraries.h"
      21             : #include "llvm/MC/MCSchedule.h"
      22             : #include "llvm/Support/CommandLine.h"
      23             : #include "llvm/Support/ErrorHandling.h"
      24             : #include "llvm/Support/raw_ostream.h"
      25             : #include "llvm/Target/TargetInstrInfo.h"
      26             : #include "llvm/Target/TargetRegisterInfo.h"
      27             : #include "llvm/Target/TargetSubtargetInfo.h"
      28             : #include <algorithm>
      29             : #include <cassert>
      30             : #include <cstdint>
      31             : 
      32             : using namespace llvm;
      33             : 
      34      289224 : static cl::opt<bool> EnableSchedModel("schedmodel", cl::Hidden, cl::init(true),
      35      289224 :   cl::desc("Use TargetSchedModel for latency lookup"));
      36             : 
      37      289224 : static cl::opt<bool> EnableSchedItins("scheditins", cl::Hidden, cl::init(true),
      38      289224 :   cl::desc("Use InstrItineraryData for latency lookup"));
      39             : 
      40    48336967 : bool TargetSchedModel::hasInstrSchedModel() const {
      41    48336967 :   return EnableSchedModel && SchedModel.hasInstrSchedModel();
      42             : }
      43             : 
      44    19377840 : bool TargetSchedModel::hasInstrItineraries() const {
      45    19377840 :   return EnableSchedItins && !InstrItins.isEmpty();
      46             : }
      47             : 
      48             : static unsigned gcd(unsigned Dividend, unsigned Divisor) {
      49             :   // Dividend and Divisor will be naturally swapped as needed.
      50     6403931 :   while (Divisor) {
      51     3308534 :     unsigned Rem = Dividend % Divisor;
      52     3308534 :     Dividend = Divisor;
      53     3308534 :     Divisor = Rem;
      54             :   };
      55             :   return Dividend;
      56             : }
      57             : 
      58             : static unsigned lcm(unsigned A, unsigned B) {
      59     6190794 :   unsigned LCM = (uint64_t(A) * B) / gcd(A, B);
      60             :   assert((LCM >= A && LCM >= B) && "LCM overflow");
      61             :   return LCM;
      62             : }
      63             : 
      64      763010 : void TargetSchedModel::init(const MCSchedModel &sm,
      65             :                             const TargetSubtargetInfo *sti,
      66             :                             const TargetInstrInfo *tii) {
      67      763010 :   SchedModel = sm;
      68      763010 :   STI = sti;
      69      763010 :   TII = tii;
      70      763010 :   STI->initInstrItins(InstrItins);
      71             : 
      72      763010 :   unsigned NumRes = SchedModel.getNumProcResourceKinds();
      73      763010 :   ResourceFactors.resize(NumRes);
      74      763010 :   ResourceLCM = SchedModel.IssueWidth;
      75     4102414 :   for (unsigned Idx = 0; Idx < NumRes; ++Idx) {
      76     6678808 :     unsigned NumUnits = SchedModel.getProcResource(Idx)->NumUnits;
      77     3339404 :     if (NumUnits > 0)
      78     6190794 :       ResourceLCM = lcm(ResourceLCM, NumUnits);
      79             :   }
      80      763010 :   MicroOpFactor = ResourceLCM / SchedModel.IssueWidth;
      81     4102414 :   for (unsigned Idx = 0; Idx < NumRes; ++Idx) {
      82     6678808 :     unsigned NumUnits = SchedModel.getProcResource(Idx)->NumUnits;
      83     6678808 :     ResourceFactors[Idx] = NumUnits ? (ResourceLCM / NumUnits) : 0;
      84             :   }
      85      763010 : }
      86             : 
      87             : /// Returns true only if instruction is specified as single issue.
      88     1985095 : bool TargetSchedModel::mustBeginGroup(const MachineInstr *MI,
      89             :                                      const MCSchedClassDesc *SC) const {
      90     1985095 :   if (hasInstrSchedModel()) {
      91      877954 :     if (!SC)
      92      877954 :       SC = resolveSchedClass(MI);
      93      877954 :     if (SC->isValid())
      94      649769 :       return SC->BeginGroup;
      95             :   }
      96             :   return false;
      97             : }
      98             : 
      99     6207476 : bool TargetSchedModel::mustEndGroup(const MachineInstr *MI,
     100             :                                      const MCSchedClassDesc *SC) const {
     101     6207476 :   if (hasInstrSchedModel()) {
     102     2076021 :     if (!SC)
     103     2076021 :       SC = resolveSchedClass(MI);
     104     2076021 :     if (SC->isValid())
     105     1856907 :       return SC->EndGroup;
     106             :   }
     107             :   return false;
     108             : }
     109             : 
     110    11813126 : unsigned TargetSchedModel::getNumMicroOps(const MachineInstr *MI,
     111             :                                           const MCSchedClassDesc *SC) const {
     112    11813126 :   if (hasInstrItineraries()) {
     113      246774 :     int UOps = InstrItins.getNumMicroOps(MI->getDesc().getSchedClass());
     114      123387 :     return (UOps >= 0) ? UOps : TII->getNumMicroOps(&InstrItins, *MI);
     115             :   }
     116    11689739 :   if (hasInstrSchedModel()) {
     117     5294641 :     if (!SC)
     118     4382389 :       SC = resolveSchedClass(MI);
     119     5294641 :     if (SC->isValid())
     120     4360605 :       return SC->NumMicroOps;
     121             :   }
     122       13457 :   return MI->isTransient() ? 0 : 1;
     123             : }
     124             : 
     125             : // The machine model may explicitly specify an invalid latency, which
     126             : // effectively means infinite latency. Since users of the TargetSchedule API
     127             : // don't know how to handle this, we convert it to a very large latency that is
     128             : // easy to distinguish when debugging the DAG but won't induce overflow.
     129             : static unsigned capLatency(int Cycles) {
     130     2034070 :   return Cycles >= 0 ? Cycles : 1000;
     131             : }
     132             : 
     133             : /// Return the MCSchedClassDesc for this instruction. Some SchedClasses require
     134             : /// evaluation of predicates that depend on instruction operands or flags.
     135    12065061 : const MCSchedClassDesc *TargetSchedModel::
     136             : resolveSchedClass(const MachineInstr *MI) const {
     137             :   // Get the definition's scheduling class descriptor from this machine model.
     138    24130122 :   unsigned SchedClass = MI->getDesc().getSchedClass();
     139    24130122 :   const MCSchedClassDesc *SCDesc = SchedModel.getSchedClassDesc(SchedClass);
     140    12065061 :   if (!SCDesc->isValid())
     141             :     return SCDesc;
     142             : 
     143             : #ifndef NDEBUG
     144             :   unsigned NIter = 0;
     145             : #endif
     146    10838797 :   while (SCDesc->isVariant()) {
     147             :     assert(++NIter < 6 && "Variants are nested deeper than the magic number");
     148             : 
     149      388544 :     SchedClass = STI->resolveSchedClass(SchedClass, MI, this);
     150      777088 :     SCDesc = SchedModel.getSchedClassDesc(SchedClass);
     151             :   }
     152             :   return SCDesc;
     153             : }
     154             : 
     155             : /// Find the def index of this operand. This index maps to the machine model and
     156             : /// is independent of use operands. Def operands may be reordered with uses or
     157             : /// merged with uses without affecting the def index (e.g. before/after
     158             : /// regalloc). However, an instruction's def operands must never be reordered
     159             : /// with respect to each other.
     160             : static unsigned findDefIdx(const MachineInstr *MI, unsigned DefOperIdx) {
     161     1391847 :   unsigned DefIdx = 0;
     162     1594444 :   for (unsigned i = 0; i != DefOperIdx; ++i) {
     163      405194 :     const MachineOperand &MO = MI->getOperand(i);
     164      367651 :     if (MO.isReg() && MO.isDef())
     165       63463 :       ++DefIdx;
     166             :   }
     167             :   return DefIdx;
     168             : }
     169             : 
     170             : /// Find the use index of this operand. This is independent of the instruction's
     171             : /// def operands.
     172             : ///
     173             : /// Note that uses are not determined by the operand's isUse property, which
     174             : /// is simply the inverse of isDef. Here we consider any readsReg operand to be
     175             : /// a "use". The machine model allows an operand to be both a Def and Use.
     176        3252 : static unsigned findUseIdx(const MachineInstr *MI, unsigned UseOperIdx) {
     177        3252 :   unsigned UseIdx = 0;
     178        8362 :   for (unsigned i = 0; i != UseOperIdx; ++i) {
     179       10220 :     const MachineOperand &MO = MI->getOperand(i);
     180        6678 :     if (MO.isReg() && MO.readsReg() && !MO.isDef())
     181        1537 :       ++UseIdx;
     182             :   }
     183        3252 :   return UseIdx;
     184             : }
     185             : 
     186             : // Top-level API for clients that know the operand indices.
     187     3584336 : unsigned TargetSchedModel::computeOperandLatency(
     188             :   const MachineInstr *DefMI, unsigned DefOperIdx,
     189             :   const MachineInstr *UseMI, unsigned UseOperIdx) const {
     190             : 
     191     3584336 :   if (!hasInstrSchedModel() && !hasInstrItineraries())
     192     1841117 :     return TII->defaultDefLatency(SchedModel, *DefMI);
     193             : 
     194     1743219 :   if (hasInstrItineraries()) {
     195      351372 :     int OperLatency = 0;
     196      351372 :     if (UseMI) {
     197      598776 :       OperLatency = TII->getOperandLatency(&InstrItins, *DefMI, DefOperIdx,
     198      299388 :                                            *UseMI, UseOperIdx);
     199             :     }
     200             :     else {
     201       51984 :       unsigned DefClass = DefMI->getDesc().getSchedClass();
     202       82401 :       OperLatency = InstrItins.getOperandCycle(DefClass, DefOperIdx);
     203             :     }
     204      329805 :     if (OperLatency >= 0)
     205      122540 :       return OperLatency;
     206             : 
     207             :     // No operand latency was found.
     208      228832 :     unsigned InstrLatency = TII->getInstrLatency(&InstrItins, *DefMI);
     209             : 
     210             :     // Expected latency is the max of the stage latency and itinerary props.
     211             :     // Rather than directly querying InstrItins stage latency, we call a TII
     212             :     // hook to allow subtargets to specialize latency. This hook is only
     213             :     // applicable to the InstrItins model. InstrSchedModel should model all
     214             :     // special cases without TII hooks.
     215             :     InstrLatency =
     216      457664 :         std::max(InstrLatency, TII->defaultDefLatency(SchedModel, *DefMI));
     217      228832 :     return InstrLatency;
     218             :   }
     219             :   // hasInstrSchedModel()
     220     1391847 :   const MCSchedClassDesc *SCDesc = resolveSchedClass(DefMI);
     221     1391847 :   unsigned DefIdx = findDefIdx(DefMI, DefOperIdx);
     222     1391847 :   if (DefIdx < SCDesc->NumWriteLatencyEntries) {
     223             :     // Lookup the definition's write latency in SubtargetInfo.
     224             :     const MCWriteLatencyEntry *WLEntry =
     225     2161718 :       STI->getWriteLatencyEntry(SCDesc, DefIdx);
     226     1080859 :     unsigned WriteID = WLEntry->WriteResourceID;
     227     2161718 :     unsigned Latency = capLatency(WLEntry->Cycles);
     228     1080859 :     if (!UseMI)
     229             :       return Latency;
     230             : 
     231             :     // Lookup the use's latency adjustment in SubtargetInfo.
     232      955574 :     const MCSchedClassDesc *UseDesc = resolveSchedClass(UseMI);
     233      955574 :     if (UseDesc->NumReadAdvanceEntries == 0)
     234             :       return Latency;
     235        3252 :     unsigned UseIdx = findUseIdx(UseMI, UseOperIdx);
     236        6504 :     int Advance = STI->getReadAdvanceCycles(UseDesc, UseIdx, WriteID);
     237        3252 :     if (Advance > 0 && (unsigned)Advance > Latency) // unsigned wrap
     238             :       return 0;
     239        2331 :     return Latency - Advance;
     240             :   }
     241             :   // If DefIdx does not exist in the model (e.g. implicit defs), then return
     242             :   // unit latency (defaultDefLatency may be too conservative).
     243             : #ifndef NDEBUG
     244             :   if (SCDesc->isValid() && !DefMI->getOperand(DefOperIdx).isImplicit()
     245             :       && !DefMI->getDesc().OpInfo[DefOperIdx].isOptionalDef()
     246             :       && SchedModel.isComplete()) {
     247             :     errs() << "DefIdx " << DefIdx << " exceeds machine model writes for "
     248             :            << *DefMI << " (Try with MCSchedModel.CompleteModel set to false)";
     249             :     llvm_unreachable("incomplete machine model");
     250             :   }
     251             : #endif
     252             :   // FIXME: Automatically giving all implicit defs defaultDefLatency is
     253             :   // undesirable. We should only do it for defs that are known to the MC
     254             :   // desc like flags. Truly implicit defs should get 1 cycle latency.
     255       88783 :   return DefMI->isTransient() ? 0 : TII->defaultDefLatency(SchedModel, *DefMI);
     256             : }
     257             : 
     258             : unsigned
     259      910540 : TargetSchedModel::computeInstrLatency(const MCSchedClassDesc &SCDesc) const {
     260      910540 :   unsigned Latency = 0;
     261     1863751 :   for (unsigned DefIdx = 0, DefEnd = SCDesc.NumWriteLatencyEntries;
     262     1863751 :        DefIdx != DefEnd; ++DefIdx) {
     263             :     // Lookup the definition's write latency in SubtargetInfo.
     264             :     const MCWriteLatencyEntry *WLEntry =
     265     1906422 :       STI->getWriteLatencyEntry(&SCDesc, DefIdx);
     266     2859633 :     Latency = std::max(Latency, capLatency(WLEntry->Cycles));
     267             :   }
     268      910540 :   return Latency;
     269             : }
     270             : 
     271       18997 : unsigned TargetSchedModel::computeInstrLatency(unsigned Opcode) const {
     272             :   assert(hasInstrSchedModel() && "Only call this function with a SchedModel");
     273             : 
     274       37994 :   unsigned SCIdx = TII->get(Opcode).getSchedClass();
     275       37994 :   const MCSchedClassDesc *SCDesc = SchedModel.getSchedClassDesc(SCIdx);
     276             : 
     277       18997 :   if (SCDesc->isValid() && !SCDesc->isVariant())
     278       18967 :     return computeInstrLatency(*SCDesc);
     279             : 
     280          30 :   if (SCDesc->isValid()) {
     281             :     assert (!SCDesc->isVariant() && "No MI sched latency: SCDesc->isVariant()");
     282           0 :     return computeInstrLatency(*SCDesc);
     283             :   }
     284             :   return 0;
     285             : }
     286             : 
     287             : unsigned
     288     3230817 : TargetSchedModel::computeInstrLatency(const MachineInstr *MI,
     289             :                                       bool UseDefaultDefLatency) const {
     290             :   // For the itinerary model, fall back to the old subtarget hook.
     291             :   // Allow subtargets to compute Bundle latencies outside the machine model.
     292     9032571 :   if (hasInstrItineraries() || MI->isBundle() ||
     293     4674116 :       (!hasInstrSchedModel() && !UseDefaultDefLatency))
     294      338968 :     return TII->getInstrLatency(&InstrItins, *MI);
     295             : 
     296     2891849 :   if (hasInstrSchedModel()) {
     297     1127098 :     const MCSchedClassDesc *SCDesc = resolveSchedClass(MI);
     298     1127098 :     if (SCDesc->isValid())
     299      891573 :       return computeInstrLatency(*SCDesc);
     300             :   }
     301     2000276 :   return TII->defaultDefLatency(SchedModel, *MI);
     302             : }
     303             : 
     304     1111052 : unsigned TargetSchedModel::
     305             : computeOutputLatency(const MachineInstr *DefMI, unsigned DefOperIdx,
     306             :                      const MachineInstr *DepMI) const {
     307     1111052 :   if (!SchedModel.isOutOfOrder())
     308             :     return 1;
     309             : 
     310             :   // Out-of-order processor can dispatch WAW dependencies in the same cycle.
     311             : 
     312             :   // Treat predication as a data dependency for out-of-order cpus. In-order
     313             :   // cpus do not need to treat predicated writes specially.
     314             :   //
     315             :   // TODO: The following hack exists because predication passes do not
     316             :   // correctly append imp-use operands, and readsReg() strangely returns false
     317             :   // for predicated defs.
     318     1621298 :   unsigned Reg = DefMI->getOperand(DefOperIdx).getReg();
     319      810649 :   const MachineFunction &MF = *DefMI->getParent()->getParent();
     320      810649 :   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
     321      810649 :   if (!DepMI->readsRegister(Reg, TRI) && TII->isPredicated(*DepMI))
     322           1 :     return computeInstrLatency(DefMI);
     323             : 
     324             :   // If we have a per operand scheduling model, check if this def is writing
     325             :   // an unbuffered resource. If so, it treated like an in-order cpu.
     326      810648 :   if (hasInstrSchedModel()) {
     327      128079 :     const MCSchedClassDesc *SCDesc = resolveSchedClass(DefMI);
     328      128079 :     if (SCDesc->isValid()) {
     329      464848 :       for (const MCWriteProcResEntry *PRI = STI->getWriteProcResBegin(SCDesc),
     330      229564 :              *PRE = STI->getWriteProcResEnd(SCDesc); PRI != PRE; ++PRI) {
     331      471528 :         if (!SchedModel.getProcResource(PRI->ProcResourceIdx)->BufferSize)
     332             :           return 1;
     333             :       }
     334             :     }
     335             :   }
     336             :   return 0;
     337             : }
     338             : 
     339             : static Optional<double>
     340        1207 : getRThroughputFromItineraries(unsigned schedClass,
     341             :                               const InstrItineraryData *IID){
     342        2414 :   Optional<double> Throughput;
     343             : 
     344        3622 :   for (const InstrStage *IS = IID->beginStage(schedClass),
     345        2414 :                         *E = IID->endStage(schedClass);
     346        2415 :        IS != E; ++IS) {
     347        1208 :     if (IS->getCycles()) {
     348        2416 :       double Temp = countPopulation(IS->getUnits()) * 1.0 / IS->getCycles();
     349        3624 :       Throughput = Throughput.hasValue()
     350          15 :                         ? std::min(Throughput.getValue(), Temp)
     351        1208 :                         : Temp;
     352             :     }
     353             :   }
     354        1207 :   if (Throughput.hasValue())
     355             :     // We need reciprocal throughput that's why we return such value.
     356        2386 :     return 1 / Throughput.getValue();
     357             :   return Throughput;
     358             : }
     359             : 
     360             : static Optional<double>
     361       15790 : getRThroughputFromInstrSchedModel(const MCSchedClassDesc *SCDesc,
     362             :                                   const TargetSubtargetInfo *STI,
     363             :                                   const MCSchedModel &SchedModel) {
     364       31580 :   Optional<double> Throughput;
     365             : 
     366      106395 :   for (const MCWriteProcResEntry *WPR = STI->getWriteProcResBegin(SCDesc),
     367       31580 :                                  *WEnd = STI->getWriteProcResEnd(SCDesc);
     368       90605 :        WPR != WEnd; ++WPR) {
     369       74815 :     if (WPR->Cycles) {
     370             :       unsigned NumUnits =
     371      149630 :           SchedModel.getProcResource(WPR->ProcResourceIdx)->NumUnits;
     372       74815 :       double Temp = NumUnits * 1.0 / WPR->Cycles;
     373      224445 :       Throughput = Throughput.hasValue()
     374       59479 :                        ? std::min(Throughput.getValue(), Temp)
     375       74815 :                        : Temp;
     376             :     }
     377             :   }
     378       15790 :   if (Throughput.hasValue())
     379             :     // We need reciprocal throughput that's why we return such value.
     380       30672 :     return 1 / Throughput.getValue();
     381             :   return Throughput;
     382             : }
     383             : 
     384             : Optional<double>
     385           0 : TargetSchedModel::computeInstrRThroughput(const MachineInstr *MI) const {
     386           0 :   if (hasInstrItineraries())
     387           0 :     return getRThroughputFromItineraries(MI->getDesc().getSchedClass(),
     388           0 :                                          getInstrItineraries());
     389           0 :   if (hasInstrSchedModel())
     390           0 :     return getRThroughputFromInstrSchedModel(resolveSchedClass(MI), STI,
     391           0 :                                              SchedModel);
     392             :   return Optional<double>();
     393             : }
     394             : 
     395             : Optional<double>
     396       17027 : TargetSchedModel::computeInstrRThroughput(unsigned Opcode) const {
     397       51081 :   unsigned SchedClass = TII->get(Opcode).getSchedClass();
     398       17027 :   if (hasInstrItineraries())
     399        1207 :     return getRThroughputFromItineraries(SchedClass, getInstrItineraries());
     400       15820 :   if (hasInstrSchedModel()) {
     401       31640 :     const MCSchedClassDesc *SCDesc = SchedModel.getSchedClassDesc(SchedClass);
     402       15820 :     if (SCDesc->isValid() && !SCDesc->isVariant())
     403       15790 :       return getRThroughputFromInstrSchedModel(SCDesc, STI, SchedModel);
     404             :   }
     405             :   return Optional<double>();
     406      216918 : }

Generated by: LCOV version 1.13