1 //=- llvm/CodeGen/ScoreboardHazardRecognizer.h - Schedule Support -*- C++ -*-=//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the ScoreboardHazardRecognizer class, which
10 // encapsulates hazard-avoidance heuristics for scheduling, based on the
11 // scheduling itineraries specified for the target.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CODEGEN_SCOREBOARDHAZARDRECOGNIZER_H
16 #define LLVM_CODEGEN_SCOREBOARDHAZARDRECOGNIZER_H
17 
18 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
19 #include "llvm/MC/MCInstrItineraries.h"
20 #include <cassert>
21 #include <cstddef>
22 #include <cstring>
23 
24 namespace llvm {
25 
26 class ScheduleDAG;
27 class SUnit;
28 
29 class ScoreboardHazardRecognizer : public ScheduleHazardRecognizer {
30   // Scoreboard to track function unit usage. Scoreboard[0] is a
31   // mask of the FUs in use in the cycle currently being
32   // schedule. Scoreboard[1] is a mask for the next cycle. The
33   // Scoreboard is used as a circular buffer with the current cycle
34   // indicated by Head.
35   //
36   // Scoreboard always counts cycles in forward execution order. If used by a
37   // bottom-up scheduler, then the scoreboard cycles are the inverse of the
38   // scheduler's cycles.
39   class Scoreboard {
40     InstrStage::FuncUnits *Data = nullptr;
41 
42     // The maximum number of cycles monitored by the Scoreboard. This
43     // value is determined based on the target itineraries to ensure
44     // that all hazards can be tracked.
45     size_t Depth = 0;
46 
47     // Indices into the Scoreboard that represent the current cycle.
48     size_t Head = 0;
49 
50   public:
51     Scoreboard() = default;
52 
53     ~Scoreboard() {
54       delete[] Data;
55     }
56 
57     size_t getDepth() const { return Depth; }
58 
59     InstrStage::FuncUnits& operator[](size_t idx) const {
60       // Depth is expected to be a power-of-2.
61       assert(Depth && !(Depth & (Depth - 1)) &&
62              "Scoreboard was not initialized properly!");
63 
64       return Data[(Head + idx) & (Depth-1)];
65     }
66 
67     void reset(size_t d = 1) {
68       if (!Data) {
69         Depth = d;
70         Data = new InstrStage::FuncUnits[Depth];
71       }
72 
73       memset(Data, 0, Depth * sizeof(Data[0]));
74       Head = 0;
75     }
76 
77     void advance() {
78       Head = (Head + 1) & (Depth-1);
79     }
80 
81     void recede() {
82       Head = (Head - 1) & (Depth-1);
83     }
84 
85     // Print the scoreboard.
86     void dump() const;
87   };
88 
89   // Support for tracing ScoreboardHazardRecognizer as a component within
90   // another module.
91   const char *DebugType;
92 
93   // Itinerary data for the target.
94   const InstrItineraryData *ItinData;
95 
96   const ScheduleDAG *DAG;
97 
98   /// IssueWidth - Max issue per cycle. 0=Unknown.
99   unsigned IssueWidth = 0;
100 
101   /// IssueCount - Count instructions issued in this cycle.
102   unsigned IssueCount = 0;
103 
104   Scoreboard ReservedScoreboard;
105   Scoreboard RequiredScoreboard;
106 
107 public:
108   ScoreboardHazardRecognizer(const InstrItineraryData *II,
109                              const ScheduleDAG *DAG,
110                              const char *ParentDebugType = "");
111 
112   /// atIssueLimit - Return true if no more instructions may be issued in this
113   /// cycle.
114   bool atIssueLimit() const override;
115 
116   // Stalls provides an cycle offset at which SU will be scheduled. It will be
117   // negative for bottom-up scheduling.
118   HazardType getHazardType(SUnit *SU, int Stalls) override;
119   void Reset() override;
120   void EmitInstruction(SUnit *SU) override;
121   void AdvanceCycle() override;
122   void RecedeCycle() override;
123 };
124 
125 } // end namespace llvm
126 
127 #endif // LLVM_CODEGEN_SCOREBOARDHAZARDRECOGNIZER_H
128