LCOV - code coverage report
Current view: top level - lib/CodeGen - TargetSchedule.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 147 150 98.0 %
Date: 2018-02-18 03:11:45 Functions: 19 19 100.0 %
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/CodeGen/TargetInstrInfo.h"
      20             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      21             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      22             : #include "llvm/MC/MCInstrDesc.h"
      23             : #include "llvm/MC/MCInstrItineraries.h"
      24             : #include "llvm/MC/MCSchedule.h"
      25             : #include "llvm/Support/CommandLine.h"
      26             : #include "llvm/Support/ErrorHandling.h"
      27             : #include "llvm/Support/raw_ostream.h"
      28             : #include <algorithm>
      29             : #include <cassert>
      30             : #include <cstdint>
      31             : 
      32             : using namespace llvm;
      33             : 
      34      291951 : static cl::opt<bool> EnableSchedModel("schedmodel", cl::Hidden, cl::init(true),
      35      194634 :   cl::desc("Use TargetSchedModel for latency lookup"));
      36             : 
      37      291951 : static cl::opt<bool> EnableSchedItins("scheditins", cl::Hidden, cl::init(true),
      38      194634 :   cl::desc("Use InstrItineraryData for latency lookup"));
      39             : 
      40    52809343 : bool TargetSchedModel::hasInstrSchedModel() const {
      41    52809343 :   return EnableSchedModel && SchedModel.hasInstrSchedModel();
      42             : }
      43             : 
      44    21165003 : bool TargetSchedModel::hasInstrItineraries() const {
      45    21165003 :   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     9783732 :   while (Divisor) {
      51     5049356 :     unsigned Rem = Dividend % Divisor;
      52             :     Dividend = Divisor;
      53             :     Divisor = Rem;
      54             :   };
      55             :   return Dividend;
      56             : }
      57             : 
      58             : static unsigned lcm(unsigned A, unsigned B) {
      59     9468752 :   unsigned LCM = (uint64_t(A) * B) / gcd(A, B);
      60             :   assert((LCM >= A && LCM >= B) && "LCM overflow");
      61             :   return LCM;
      62             : }
      63             : 
      64      951461 : void TargetSchedModel::init(const MCSchedModel &sm,
      65             :                             const TargetSubtargetInfo *sti,
      66             :                             const TargetInstrInfo *tii) {
      67      951461 :   SchedModel = sm;
      68      951461 :   STI = sti;
      69      951461 :   TII = tii;
      70      951461 :   STI->initInstrItins(InstrItins);
      71             : 
      72             :   unsigned NumRes = SchedModel.getNumProcResourceKinds();
      73      951461 :   ResourceFactors.resize(NumRes);
      74      951461 :   ResourceLCM = SchedModel.IssueWidth;
      75    11078089 :   for (unsigned Idx = 0; Idx < NumRes; ++Idx) {
      76     5063314 :     unsigned NumUnits = SchedModel.getProcResource(Idx)->NumUnits;
      77     5063314 :     if (NumUnits > 0)
      78     9468752 :       ResourceLCM = lcm(ResourceLCM, NumUnits);
      79             :   }
      80      951461 :   MicroOpFactor = ResourceLCM / SchedModel.IssueWidth;
      81    11078089 :   for (unsigned Idx = 0; Idx < NumRes; ++Idx) {
      82     5063314 :     unsigned NumUnits = SchedModel.getProcResource(Idx)->NumUnits;
      83    10126628 :     ResourceFactors[Idx] = NumUnits ? (ResourceLCM / NumUnits) : 0;
      84             :   }
      85      951461 : }
      86             : 
      87             : /// Returns true only if instruction is specified as single issue.
      88     2166785 : bool TargetSchedModel::mustBeginGroup(const MachineInstr *MI,
      89             :                                      const MCSchedClassDesc *SC) const {
      90     2166785 :   if (hasInstrSchedModel()) {
      91      940207 :     if (!SC)
      92      940207 :       SC = resolveSchedClass(MI);
      93      940207 :     if (SC->isValid())
      94      934467 :       return SC->BeginGroup;
      95             :   }
      96             :   return false;
      97             : }
      98             : 
      99     6891851 : bool TargetSchedModel::mustEndGroup(const MachineInstr *MI,
     100             :                                      const MCSchedClassDesc *SC) const {
     101     6891851 :   if (hasInstrSchedModel()) {
     102     2216915 :     if (!SC)
     103     2216915 :       SC = resolveSchedClass(MI);
     104     2216915 :     if (SC->isValid())
     105     2214367 :       return SC->EndGroup;
     106             :   }
     107             :   return false;
     108             : }
     109             : 
     110    12966774 : unsigned TargetSchedModel::getNumMicroOps(const MachineInstr *MI,
     111             :                                           const MCSchedClassDesc *SC) const {
     112    12966774 :   if (hasInstrItineraries()) {
     113             :     int UOps = InstrItins.getNumMicroOps(MI->getDesc().getSchedClass());
     114      151462 :     return (UOps >= 0) ? UOps : TII->getNumMicroOps(&InstrItins, *MI);
     115             :   }
     116    12815312 :   if (hasInstrSchedModel()) {
     117     5651898 :     if (!SC)
     118     4676723 :       SC = resolveSchedClass(MI);
     119     5651898 :     if (SC->isValid())
     120     5631431 :       return SC->NumMicroOps;
     121             :   }
     122             :   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     2365871 :   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    12913346 : const MCSchedClassDesc *TargetSchedModel::
     136             : resolveSchedClass(const MachineInstr *MI) const {
     137             :   // Get the definition's scheduling class descriptor from this machine model.
     138             :   unsigned SchedClass = MI->getDesc().getSchedClass();
     139             :   const MCSchedClassDesc *SCDesc = SchedModel.getSchedClassDesc(SchedClass);
     140    12913346 :   if (!SCDesc->isValid())
     141             :     return SCDesc;
     142             : 
     143             : #ifndef NDEBUG
     144             :   unsigned NIter = 0;
     145             : #endif
     146    13716412 :   while (SCDesc->isVariant()) {
     147             :     assert(++NIter < 6 && "Variants are nested deeper than the magic number");
     148             : 
     149      429534 :     SchedClass = STI->resolveSchedClass(SchedClass, MI, this);
     150             :     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             :   unsigned DefIdx = 0;
     162     1896572 :   for (unsigned i = 0; i != DefOperIdx; ++i) {
     163             :     const MachineOperand &MO = MI->getOperand(i);
     164      380598 :     if (MO.isReg() && MO.isDef())
     165       71410 :       ++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        5841 : static unsigned findUseIdx(const MachineInstr *MI, unsigned UseOperIdx) {
     177             :   unsigned UseIdx = 0;
     178       24721 :   for (unsigned i = 0; i != UseOperIdx; ++i) {
     179             :     const MachineOperand &MO = MI->getOperand(i);
     180       12747 :     if (MO.isReg() && MO.readsReg() && !MO.isDef())
     181        3253 :       ++UseIdx;
     182             :   }
     183        5841 :   return UseIdx;
     184             : }
     185             : 
     186             : // Top-level API for clients that know the operand indices.
     187     3858984 : unsigned TargetSchedModel::computeOperandLatency(
     188             :   const MachineInstr *DefMI, unsigned DefOperIdx,
     189             :   const MachineInstr *UseMI, unsigned UseOperIdx) const {
     190             : 
     191     3858984 :   if (!hasInstrSchedModel() && !hasInstrItineraries())
     192     1993346 :     return TII->defaultDefLatency(SchedModel, *DefMI);
     193             : 
     194     1865638 :   if (hasInstrItineraries()) {
     195             :     int OperLatency = 0;
     196      386814 :     if (UseMI) {
     197      656456 :       OperLatency = TII->getOperandLatency(&InstrItins, *DefMI, DefOperIdx,
     198      328228 :                                            *UseMI, UseOperIdx);
     199             :     }
     200             :     else {
     201             :       unsigned DefClass = DefMI->getDesc().getSchedClass();
     202             :       OperLatency = InstrItins.getOperandCycle(DefClass, DefOperIdx);
     203             :     }
     204      362381 :     if (OperLatency >= 0)
     205      139844 :       return OperLatency;
     206             : 
     207             :     // No operand latency was found.
     208      246970 :     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      493940 :         std::max(InstrLatency, TII->defaultDefLatency(SchedModel, *DefMI));
     217      246970 :     return InstrLatency;
     218             :   }
     219             :   // hasInstrSchedModel()
     220     1478824 :   const MCSchedClassDesc *SCDesc = resolveSchedClass(DefMI);
     221             :   unsigned DefIdx = findDefIdx(DefMI, DefOperIdx);
     222     1478824 :   if (DefIdx < SCDesc->NumWriteLatencyEntries) {
     223             :     // Lookup the definition's write latency in SubtargetInfo.
     224             :     const MCWriteLatencyEntry *WLEntry =
     225     1208204 :       STI->getWriteLatencyEntry(SCDesc, DefIdx);
     226     1208204 :     unsigned WriteID = WLEntry->WriteResourceID;
     227     1208204 :     unsigned Latency = capLatency(WLEntry->Cycles);
     228     1208204 :     if (!UseMI)
     229             :       return Latency;
     230             : 
     231             :     // Lookup the use's latency adjustment in SubtargetInfo.
     232     1058191 :     const MCSchedClassDesc *UseDesc = resolveSchedClass(UseMI);
     233     1058191 :     if (UseDesc->NumReadAdvanceEntries == 0)
     234             :       return Latency;
     235        5841 :     unsigned UseIdx = findUseIdx(UseMI, UseOperIdx);
     236        5841 :     int Advance = STI->getReadAdvanceCycles(UseDesc, UseIdx, WriteID);
     237        5841 :     if (Advance > 0 && (unsigned)Advance > Latency) // unsigned wrap
     238             :       return 0;
     239        4140 :     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       51376 :   return DefMI->isTransient() ? 0 : TII->defaultDefLatency(SchedModel, *DefMI);
     256             : }
     257             : 
     258             : unsigned
     259     1257457 : TargetSchedModel::computeInstrLatency(const MCSchedClassDesc &SCDesc) const {
     260     1257457 :   unsigned Latency = 0;
     261     2415124 :   for (unsigned DefIdx = 0, DefEnd = SCDesc.NumWriteLatencyEntries;
     262     2415124 :        DefIdx != DefEnd; ++DefIdx) {
     263             :     // Lookup the definition's write latency in SubtargetInfo.
     264             :     const MCWriteLatencyEntry *WLEntry =
     265     1157667 :       STI->getWriteLatencyEntry(&SCDesc, DefIdx);
     266     3473001 :     Latency = std::max(Latency, capLatency(WLEntry->Cycles));
     267             :   }
     268     1257457 :   return Latency;
     269             : }
     270             : 
     271       64904 : unsigned TargetSchedModel::computeInstrLatency(unsigned Opcode) const {
     272             :   assert(hasInstrSchedModel() && "Only call this function with a SchedModel");
     273             : 
     274       64904 :   unsigned SCIdx = TII->get(Opcode).getSchedClass();
     275             :   const MCSchedClassDesc *SCDesc = SchedModel.getSchedClassDesc(SCIdx);
     276             : 
     277       64904 :   if (SCDesc->isValid() && !SCDesc->isVariant())
     278       64904 :     return computeInstrLatency(*SCDesc);
     279             : 
     280           0 :   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     3469928 : 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     9678801 :   if (hasInstrItineraries() || MI->isBundle() ||
     293     5005229 :       (!hasInstrSchedModel() && !UseDefaultDefLatency))
     294      374739 :     return TII->getInstrLatency(&InstrItins, *MI);
     295             : 
     296     3095189 :   if (hasInstrSchedModel()) {
     297     1203111 :     const MCSchedClassDesc *SCDesc = resolveSchedClass(MI);
     298     1203111 :     if (SCDesc->isValid())
     299     1192553 :       return computeInstrLatency(*SCDesc);
     300             :   }
     301     1902636 :   return TII->defaultDefLatency(SchedModel, *MI);
     302             : }
     303             : 
     304     1142432 : unsigned TargetSchedModel::
     305             : computeOutputLatency(const MachineInstr *DefMI, unsigned DefOperIdx,
     306             :                      const MachineInstr *DepMI) const {
     307     1142432 :   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             :   unsigned Reg = DefMI->getOperand(DefOperIdx).getReg();
     319      845028 :   const MachineFunction &MF = *DefMI->getMF();
     320      845028 :   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
     321      845028 :   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      845027 :   if (hasInstrSchedModel()) {
     327      138889 :     const MCSchedClassDesc *SCDesc = resolveSchedClass(DefMI);
     328      138889 :     if (SCDesc->isValid()) {
     329      394851 :       for (const MCWriteProcResEntry *PRI = STI->getWriteProcResBegin(SCDesc),
     330      394851 :              *PRE = STI->getWriteProcResEnd(SCDesc); PRI != PRE; ++PRI) {
     331      515408 :         if (!SchedModel.getProcResource(PRI->ProcResourceIdx)->BufferSize)
     332             :           return 1;
     333             :       }
     334             :     }
     335             :   }
     336             :   return 0;
     337             : }
     338             : 
     339             : static Optional<double>
     340        3034 : getRThroughputFromItineraries(unsigned schedClass,
     341             :                               const InstrItineraryData *IID){
     342             :   Optional<double> Throughput;
     343             : 
     344        2988 :   for (const InstrStage *IS = IID->beginStage(schedClass),
     345             :                         *E = IID->endStage(schedClass);
     346        6022 :        IS != E; ++IS) {
     347        2988 :     if (IS->getCycles()) {
     348        2988 :       double Temp = countPopulation(IS->getUnits()) * 1.0 / IS->getCycles();
     349             :       Throughput = Throughput.hasValue()
     350             :                         ? std::min(Throughput.getValue(), Temp)
     351        2988 :                         : Temp;
     352             :     }
     353             :   }
     354        3034 :   if (Throughput.hasValue())
     355             :     // We need reciprocal throughput that's why we return such value.
     356        2948 :     return 1 / Throughput.getValue();
     357             :   return Throughput;
     358             : }
     359             : 
     360             : static Optional<double>
     361       49013 : getRThroughputFromInstrSchedModel(const MCSchedClassDesc *SCDesc,
     362             :                                   const TargetSubtargetInfo *STI,
     363             :                                   const MCSchedModel &SchedModel) {
     364             :   Optional<double> Throughput;
     365             : 
     366      244852 :   for (const MCWriteProcResEntry *WPR = STI->getWriteProcResBegin(SCDesc),
     367             :                                  *WEnd = STI->getWriteProcResEnd(SCDesc);
     368      293865 :        WPR != WEnd; ++WPR) {
     369      244852 :     if (WPR->Cycles) {
     370             :       unsigned NumUnits =
     371      489704 :           SchedModel.getProcResource(WPR->ProcResourceIdx)->NumUnits;
     372      244852 :       double Temp = NumUnits * 1.0 / WPR->Cycles;
     373             :       Throughput = Throughput.hasValue()
     374             :                        ? std::min(Throughput.getValue(), Temp)
     375      244852 :                        : Temp;
     376             :     }
     377             :   }
     378       49013 :   if (Throughput.hasValue())
     379             :     // We need reciprocal throughput that's why we return such value.
     380       48596 :     return 1 / Throughput.getValue();
     381             :   return Throughput;
     382             : }
     383             : 
     384             : Optional<double>
     385           8 : TargetSchedModel::computeInstrRThroughput(const MachineInstr *MI) const {
     386           8 :   if (hasInstrItineraries())
     387             :     return getRThroughputFromItineraries(MI->getDesc().getSchedClass(),
     388           0 :                                          getInstrItineraries());
     389           8 :   if (hasInstrSchedModel())
     390           8 :     return getRThroughputFromInstrSchedModel(resolveSchedClass(MI), STI,
     391          16 :                                              SchedModel);
     392             :   return Optional<double>();
     393             : }
     394             : 
     395             : Optional<double>
     396       52039 : TargetSchedModel::computeInstrRThroughput(unsigned Opcode) const {
     397       52039 :   unsigned SchedClass = TII->get(Opcode).getSchedClass();
     398       52039 :   if (hasInstrItineraries())
     399        3034 :     return getRThroughputFromItineraries(SchedClass, getInstrItineraries());
     400       49005 :   if (hasInstrSchedModel()) {
     401             :     const MCSchedClassDesc *SCDesc = SchedModel.getSchedClassDesc(SchedClass);
     402       49005 :     if (SCDesc->isValid() && !SCDesc->isVariant())
     403       49005 :       return getRThroughputFromInstrSchedModel(SCDesc, STI, SchedModel);
     404             :   }
     405             :   return Optional<double>();
     406      291951 : }

Generated by: LCOV version 1.13