[CodeGen] print max throughput for 0-latency insts

[spatel]

Summary

This is a fix for the problem arising in D47374 (PR37678):
https://bugs.llvm.org/show_bug.cgi?id=37678

We don't have throughput info for instructions with variant scheduling, so assume that a zero latency inst can execute/complete at max-issue-width.

[andreadb]

Hey Sanjay,

what if instead we change method MCSchedModel::getReciprocalThroughput?
If we decide to always return a meaningful value for instructions that don't consume processor resources, then I think that we can get rid of Optional<>.
If an instruction is associated with an invalid scheduling class (i.e. !SCDesc->isValid()), then we should just return 1/IssueWidth.
If an instruction doesn't consume resources, then we should return N/IssueWidth (where N is the NumMicroOpcodes).

I also prefer that we don't touch getSchedInfoStr(). My opinion is that adding extra logic to that method is going to make it difficult to get rid of it in the next future. Strictly speaking, the idea of adding that method to the subtarget was bad; there is no reason why the "profile string" should be returned by the subtarget!... My wish is that we get rid of getSchedInfoStr() (as well as function createSchedInfoStr) in the near future.

Not sure if this makes sense.

-Andrea

[spatel]

In D47723#1121109, @andreadb wrote:

Hey Sanjay,

what if instead we change method MCSchedModel::getReciprocalThroughput?
If we decide to always return a meaningful value for instructions that don't consume processor resources, then I think that we can get rid of Optional<>.
If an instruction is associated with an invalid scheduling class (i.e. !SCDesc->isValid()), then we should just return 1/IssueWidth.
If an instruction doesn't consume resources, then we should return N/IssueWidth (where N is the NumMicroOpcodes).

I also prefer that we don't touch getSchedInfoStr(). My opinion is that adding extra logic to that method is going to make it difficult to get rid of it in the next future. Strictly speaking, the idea of adding that method to the subtarget was bad; there is no reason why the "profile string" should be returned by the subtarget!... My wish is that we get rid of getSchedInfoStr() (as well as function createSchedInfoStr) in the near future.

Not sure if this makes sense.

Yes, I think that all makes sense. I actually looked at the higher-level change first to remove the Optional<>, but I wasn't sure if we wanted to do that or just go with the quick hack for now. I'll have a look at fixing this better.

[spatel]

Patch updated:
Please have a close look at the diffs because I'm not sure how to test all of these paths.

The cases that I see behaving as intended via tests are the recent variant scheduled "xorps %xmm0, %xmm0" and existing non-zero latency cases like:
; ZNVER1-SSE-NEXT: ldmxcsr -{{[0-9]+}}(%rsp) # sched: [100:?]
(those cases are all unchanged, as I think is expected for this patch...but let me know if we want to treat that differently)

The big logical difference in this patch is that instead of using an Optional, we rely on FP NaN to represent the unknown state. Then, we modify the throughput calcs to account for the cases where no execution resources are specified by using default/max issue widths.

[andreadb]

In D47723#1121600, @spatel wrote:

Patch updated:
Please have a close look at the diffs because I'm not sure how to test all of these paths.

The cases that I see behaving as intended via tests are the recent variant scheduled "xorps %xmm0, %xmm0" and existing non-zero latency cases like:
; ZNVER1-SSE-NEXT: ldmxcsr -{{[0-9]+}}(%rsp) # sched: [100:?]
(those cases are all unchanged, as I think is expected for this patch...but let me know if we want to treat that differently)

I think that IssueWidth/NumMicroOps should always be the upper bound for the throughput. So, I am of the opinion that we should not restrict this change to zero latency instructions.

The big logical difference in this patch is that instead of using an Optional, we rely on FP NaN to represent the unknown state. Then, we modify the throughput calcs to account for the cases where no execution resources are specified by using default/max issue widths.

I think it is easier to use 0.0 as the default "unknown" value.
The reciprocal throughput can never be 0.0; a RThrougput of zero effectively means that the throughput tends to infinite. This is an impossible scenario since we don't have infinite parallelism in hardware (i.e. we cannot model infinite resources), and we cannot execute an infinite number of instructions per cycle. Essentially, 0.0 is our asymptote.
So, it is safe to use 0.0 as the special "unknown" throughput. For instructions that don't consume resource cycles we would still return N/IssueWidth.
Also, you don't need to use the "unknown" value in any max computation (see comments below).

lib/CodeGen/TargetSchedule.cpp

336

I would just return 0.0 instead of NaN.

351

Same.

lib/CodeGen/TargetSubtargetInfo.cpp

74

If we use 0.0 as the unknown value, then this would become:

IF (Rthroughput != 0.0)

lib/MC/MCSchedule.cpp

91–111

My opinion is that we should not limit this to zero-latency instructions.

Here, you could have just reused the original code which computes the Throughput as a Optional<double>.

If Throughput is not defined, then simply return SCDesc.NumMicroOps / SM.IssueWidth.
Basically, you should be able to only change the return statement.

149

You can simply return 1/DefaultIssueWidth.
This computation may not accurate; ideally, we should use the actual IssueWidth from the scheduling model. In practice, this code is not used: x86 models don't use itineraries, and - as far as I know - x86 is the only target that enables the -print-schedule functionality.
Fixing this would probably require a change to this API, which is probably outside of the scope of this patch. For now, I think that returning a default 1/DefaultIssueWidth is good enough.

[spatel]

Patch updated:
Calculate throughput for non-zero-latency instructions with no throughput specified.
This is a smaller code change than the last rev, but as shown, it results in a large amount of test diffs.
I was trying to avoid this in previous versions of the patch, but I think it makes sense given that the code change is smaller if we jump directly to this step.

[andreadb]

Thanks Sanjay.
It looks good to me.
I agree that this affects a lot of tests. However it looks like most of the diffs are for znver1, which apparently assigns an arbitrary 100cy latency , 1 uOp and no processor resource cycles to all microcoded instructions. So I am not particularly worried about it.
In the absence of extra/accurate schedule information, I think that computing an optimistic reciprocal throughput based on the number of opcodes and IssueWidth is the best that we can do.

include/llvm/CodeGen/TargetSchedule.h

#endif
 
   /// Output dependency latency of a pair of defs of the same register.
   ///
   /// This is typically one cycle.
   unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefIdx,
                                 const MachineInstr *DepMI) const;
 
   /// Compute the reciprocal throughput of the given instruction.
-  Optional<double> computeReciprocalThroughput(const MachineInstr *MI) const;
-  Optional<double> computeReciprocalThroughput(const MCInst &MI) const;
-  Optional<double> computeReciprocalThroughput(unsigned Opcode) const;
+  double computeReciprocalThroughput(const MachineInstr *MI) const;
+  double computeReciprocalThroughput(const MCInst &MI) const;
+  double computeReciprocalThroughput(unsigned Opcode) const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_TARGETSCHEDULE_H

include/llvm/MC/MCSchedule.h

struct MCSchedModel {
   static int computeInstrLatency(const MCSubtargetInfo &STI,
                                  const MCSchedClassDesc &SCDesc);
 
   int computeInstrLatency(const MCSubtargetInfo &STI, unsigned SClass) const;
   int computeInstrLatency(const MCSubtargetInfo &STI, const MCInstrInfo &MCII,
                           const MCInst &Inst) const;
 
   // Returns the reciprocal throughput information from a MCSchedClassDesc.
-  static Optional<double>
+  static double
   getReciprocalThroughput(const MCSubtargetInfo &STI,
                           const MCSchedClassDesc &SCDesc);
 
-  static Optional<double>
+  static double
   getReciprocalThroughput(unsigned SchedClass, const InstrItineraryData &IID);
 
-  Optional<double>
+  double
   getReciprocalThroughput(const MCSubtargetInfo &STI, const MCInstrInfo &MCII,
                           const MCInst &Inst) const;
 
   /// Returns the default initialized model.
   static const MCSchedModel &GetDefaultSchedModel() { return Default; }
   static const MCSchedModel Default;
 };
 
 } // namespace llvm
 
 #endif

lib/CodeGen/TargetSchedule.cpp

if (SCDesc->isValid()) {
         if (!SchedModel.getProcResource(PRI->ProcResourceIdx)->BufferSize)
           return 1;
       }
     }
   }
   return 0;
 }
 
-Optional<double>
+double
 TargetSchedModel::computeReciprocalThroughput(const MachineInstr *MI) const {
   if (hasInstrItineraries()) {
     unsigned SchedClass = MI->getDesc().getSchedClass();
     return MCSchedModel::getReciprocalThroughput(SchedClass,
                                                  *getInstrItineraries());
   }
 
   if (hasInstrSchedModel())
     return MCSchedModel::getReciprocalThroughput(*STI, *resolveSchedClass(MI));
-  return Optional<double>();
+
+  return std::nan("");
 }
 
-Optional<double>
+double
 TargetSchedModel::computeReciprocalThroughput(unsigned Opcode) const {
   unsigned SchedClass = TII->get(Opcode).getSchedClass();
   if (hasInstrItineraries())
     return MCSchedModel::getReciprocalThroughput(SchedClass,
                                                  *getInstrItineraries());
   if (hasInstrSchedModel()) {
     const MCSchedClassDesc &SCDesc = *SchedModel.getSchedClassDesc(SchedClass);
     if (SCDesc.isValid() && !SCDesc.isVariant())
       return MCSchedModel::getReciprocalThroughput(*STI, SCDesc);
   }
-  return Optional<double>();
+
+  return std::nan("");
 }
 
-Optional<double>
+double
 TargetSchedModel::computeReciprocalThroughput(const MCInst &MI) const {
   if (hasInstrSchedModel())
     return SchedModel.getReciprocalThroughput(*STI, *TII, MI);
   return computeReciprocalThroughput(MI.getOpcode());
 }
 

lib/CodeGen/TargetSubtargetInfo.cpp

 bool TargetSubtargetInfo::enablePostRAScheduler() const {
   return getSchedModel().PostRAScheduler;
 }
 
 bool TargetSubtargetInfo::useAA() const {
   return false;
 }
 
-static std::string createSchedInfoStr(unsigned Latency,
-                                      Optional<double> RThroughput) {
+static std::string createSchedInfoStr(unsigned Latency, double RThroughput) {
   static const char *SchedPrefix = " sched: [";
   std::string Comment;
   raw_string_ostream CS(Comment);
-  if (RThroughput.hasValue())
-    CS << SchedPrefix << Latency << format(":%2.2f", RThroughput.getValue())
+  if (!std::isnan(RThroughput))
+    CS << SchedPrefix << Latency << format(":%2.2f", RThroughput)
        << "]";
   else
     CS << SchedPrefix << Latency << ":?]";
   CS.flush();
   return Comment;
 }
 
 /// Returns string representation of scheduler comment
 std::string TargetSubtargetInfo::getSchedInfoStr(const MachineInstr &MI) const {
   if (MI.isPseudo() || MI.isTerminator())
     return std::string();
   // We don't cache TSchedModel because it depends on TargetInstrInfo
   // that could be changed during the compilation
   TargetSchedModel TSchedModel;
   TSchedModel.init(this);
   unsigned Latency = TSchedModel.computeInstrLatency(&MI);
-  Optional<double> RThroughput = TSchedModel.computeReciprocalThroughput(&MI);
+  double RThroughput = TSchedModel.computeReciprocalThroughput(&MI);
   return createSchedInfoStr(Latency, RThroughput);
 }
 
 /// Returns string representation of scheduler comment
 std::string TargetSubtargetInfo::getSchedInfoStr(MCInst const &MCI) const {
   // We don't cache TSchedModel because it depends on TargetInstrInfo
   // that could be changed during the compilation
   TargetSchedModel TSchedModel;
   TSchedModel.init(this);
   unsigned Latency;
   if (TSchedModel.hasInstrSchedModel())
     Latency = TSchedModel.computeInstrLatency(MCI);
   else if (TSchedModel.hasInstrItineraries()) {
     auto *ItinData = TSchedModel.getInstrItineraries();
     Latency = ItinData->getStageLatency(
         getInstrInfo()->get(MCI.getOpcode()).getSchedClass());
   } else
     return std::string();
-  Optional<double> RThroughput =
-      TSchedModel.computeReciprocalThroughput(MCI);
+  double RThroughput = TSchedModel.computeReciprocalThroughput(MCI);
   return createSchedInfoStr(Latency, RThroughput);
 }
 
 void TargetSubtargetInfo::mirFileLoaded(MachineFunction &MF) const {
 }

lib/MC/MCSchedule.cpp

int MCSchedModel::computeInstrLatency(const MCSubtargetInfo &STI,
   }
 
   if (SchedClass)
     return MCSchedModel::computeInstrLatency(STI, *SCDesc);
 
   llvm_unreachable("unsupported variant scheduling class");
 }
 
-Optional<double>
+double
 MCSchedModel::getReciprocalThroughput(const MCSubtargetInfo &STI,
                                       const MCSchedClassDesc &SCDesc) {
-  Optional<double> Throughput;
+  // fmin(NaN, number) returns number. But this function can return NaN if a
+  // schedule class specifies a latency without specifying a valid throughput.
+  double Throughput = std::numeric_limits<double>::quiet_NaN();
   const MCSchedModel &SM = STI.getSchedModel();
   const MCWriteProcResEntry *I = STI.getWriteProcResBegin(&SCDesc);
   const MCWriteProcResEntry *E = STI.getWriteProcResEnd(&SCDesc);
+
+  // If an instruction has no latency (consumes no execution resources), then
+  // assume that it can execute at the maximum issue width scaled by number of
+  // micro-ops for the schedule class.
+  if (!computeInstrLatency(STI, SCDesc))
+    Throughput = SM.IssueWidth / SCDesc.NumMicroOps;
+
   for (; I != E; ++I) {
     if (!I->Cycles)
       continue;
     unsigned NumUnits = SM.getProcResource(I->ProcResourceIdx)->NumUnits;
     double Temp = NumUnits * 1.0 / I->Cycles;
-    Throughput = Throughput ? std::min(Throughput.getValue(), Temp) : Temp;
+    Throughput = std::fmin(Throughput, Temp);
   }
-  return Throughput ? 1 / Throughput.getValue() : Throughput;
+  return 1.0 / Throughput;
 }
 
-Optional<double>
+double
 MCSchedModel::getReciprocalThroughput(const MCSubtargetInfo &STI,
                                       const MCInstrInfo &MCII,
                                       const MCInst &Inst) const {
-  Optional<double> Throughput;
   unsigned SchedClass = MCII.get(Inst.getOpcode()).getSchedClass();
   const MCSchedClassDesc *SCDesc = getSchedClassDesc(SchedClass);
+
+  // If there's no valid class, assume that the instruction executes/completes
+  // at the maximum issue width.
   if (!SCDesc->isValid())
-    return Throughput;
+    return 1.0 / IssueWidth;
 
   unsigned CPUID = getProcessorID();
   while (SCDesc->isVariant()) {
     SchedClass = STI.resolveVariantSchedClass(SchedClass, &Inst, CPUID);
     SCDesc = getSchedClassDesc(SchedClass);
   }
 
   if (SchedClass)
     return MCSchedModel::getReciprocalThroughput(STI, *SCDesc);
 
   llvm_unreachable("unsupported variant scheduling class");
 }
 
-Optional<double>
+double
 MCSchedModel::getReciprocalThroughput(unsigned SchedClass,
                                       const InstrItineraryData &IID) {
-  Optional<double> Throughput;
+  // fmin(NaN, number) returns number, so this function always returns a number.
+  double Throughput = std::numeric_limits<double>::quiet_NaN();
   const InstrStage *I = IID.beginStage(SchedClass);
   const InstrStage *E = IID.endStage(SchedClass);
+
+  // If there are no execution resources for this class, then assume that it can
+  // execute at the maximum default issue width.
+  if (I == E)
+    Throughput = DefaultIssueWidth;
+
   for (; I != E; ++I) {
     if (!I->getCycles())
       continue;
     double Temp = countPopulation(I->getUnits()) * 1.0 / I->getCycles();
-    Throughput = Throughput ? std::min(Throughput.getValue(), Temp) : Temp;
+    Throughput = std::fmin(Throughput, Temp);
   }
-  return Throughput ? 1 / Throughput.getValue() : Throughput;
+  return 1.0 / Throughput;
 }

test/CodeGen/X86/sse-schedule.ll

 ; SKX-NEXT:    #APP
 ; SKX-NEXT:    nop # sched: [1:0.25]
 ; SKX-NEXT:    #NO_APP
 ; SKX-NEXT:    vxorps %xmm0, %xmm0, %xmm0 # sched: [1:0.33]
 ; SKX-NEXT:    retq # sched: [7:1.00]
 ;
 ; BTVER2-SSE-LABEL: test_fnop:
 ; BTVER2-SSE:       # %bb.0:
-; BTVER2-SSE-NEXT:    xorps %xmm0, %xmm0 # sched: [0:?]
+; BTVER2-SSE-NEXT:    xorps %xmm0, %xmm0 # sched: [0:0.50]
 ; BTVER2-SSE-NEXT:    #APP
 ; BTVER2-SSE-NEXT:    nop # sched: [1:0.50]
 ; BTVER2-SSE-NEXT:    #NO_APP
 ; BTVER2-SSE-NEXT:    retq # sched: [4:1.00]
 ;
 ; BTVER2-LABEL: test_fnop:
 ; BTVER2:       # %bb.0:
-; BTVER2-NEXT:    vxorps %xmm0, %xmm0, %xmm0 # sched: [0:?]
+; BTVER2-NEXT:    vxorps %xmm0, %xmm0, %xmm0 # sched: [0:0.50]
 ; BTVER2-NEXT:    #APP
 ; BTVER2-NEXT:    nop # sched: [1:0.50]
 ; BTVER2-NEXT:    #NO_APP
 ; BTVER2-NEXT:    retq # sched: [4:1.00]
 ;
 ; ZNVER1-SSE-LABEL: test_fnop:
 ; ZNVER1-SSE:       # %bb.0:
 ; ZNVER1-SSE-NEXT:    xorps %xmm0, %xmm0 # sched: [1:0.25]