Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonMachineScheduler.h
Line
Count
Source (jump to first uncovered line)
1
//===- HexagonMachineScheduler.h - Custom Hexagon MI scheduler --*- 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
// Custom Hexagon MI scheduler.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
14
#define LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
15
16
#include "llvm/ADT/STLExtras.h"
17
#include "llvm/ADT/Twine.h"
18
#include "llvm/CodeGen/DFAPacketizer.h"
19
#include "llvm/CodeGen/MachineScheduler.h"
20
#include "llvm/CodeGen/RegisterPressure.h"
21
#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
22
#include "llvm/CodeGen/TargetInstrInfo.h"
23
#include "llvm/CodeGen/TargetSchedule.h"
24
#include "llvm/CodeGen/TargetSubtargetInfo.h"
25
#include <algorithm>
26
#include <cassert>
27
#include <limits>
28
#include <memory>
29
#include <vector>
30
31
namespace llvm {
32
33
class SUnit;
34
35
class VLIWResourceModel {
36
  /// ResourcesModel - Represents VLIW state.
37
  /// Not limited to VLIW targets per se, but assumes
38
  /// definition of DFA by a target.
39
  DFAPacketizer *ResourcesModel;
40
41
  const TargetSchedModel *SchedModel;
42
43
  /// Local packet/bundle model. Purely
44
  /// internal to the MI schedulre at the time.
45
  std::vector<SUnit *> Packet;
46
47
  /// Total packets created.
48
  unsigned TotalPackets = 0;
49
50
public:
51
  VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
52
10.0k
      : SchedModel(SM) {
53
10.0k
    ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
54
10.0k
55
10.0k
    // This hard requirement could be relaxed,
56
10.0k
    // but for now do not let it proceed.
57
10.0k
    assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
58
10.0k
59
10.0k
    Packet.resize(SchedModel->getIssueWidth());
60
10.0k
    Packet.clear();
61
10.0k
    ResourcesModel->clearResources();
62
10.0k
  }
63
64
10.0k
  ~VLIWResourceModel() {
65
10.0k
    delete ResourcesModel;
66
10.0k
  }
67
68
0
  void resetPacketState() {
69
0
    Packet.clear();
70
0
  }
71
72
0
  void resetDFA() {
73
0
    ResourcesModel->clearResources();
74
0
  }
75
76
0
  void reset() {
77
0
    Packet.clear();
78
0
    ResourcesModel->clearResources();
79
0
  }
80
81
  bool isResourceAvailable(SUnit *SU, bool IsTop);
82
  bool reserveResources(SUnit *SU, bool IsTop);
83
0
  unsigned getTotalPackets() const { return TotalPackets; }
84
39.0k
  bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
85
};
86
87
/// Extend the standard ScheduleDAGMI to provide more context and override the
88
/// top-level schedule() driver.
89
class VLIWMachineScheduler : public ScheduleDAGMILive {
90
public:
91
  VLIWMachineScheduler(MachineSchedContext *C,
92
                       std::unique_ptr<MachineSchedStrategy> S)
93
3.34k
      : ScheduleDAGMILive(C, std::move(S)) {}
94
95
  /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
96
  /// time to do some work.
97
  void schedule() override;
98
99
40.1k
  RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
100
20.0k
  int getBBSize() { return BB->size(); }
101
};
102
103
//===----------------------------------------------------------------------===//
104
// ConvergingVLIWScheduler - Implementation of the standard
105
// MachineSchedStrategy.
106
//===----------------------------------------------------------------------===//
107
108
/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
109
/// to balance the schedule.
110
class ConvergingVLIWScheduler : public MachineSchedStrategy {
111
  /// Store the state used by ConvergingVLIWScheduler heuristics, required
112
  ///  for the lifetime of one invocation of pickNode().
113
  struct SchedCandidate {
114
    // The best SUnit candidate.
115
    SUnit *SU = nullptr;
116
117
    // Register pressure values for the best candidate.
118
    RegPressureDelta RPDelta;
119
120
    // Best scheduling cost.
121
    int SCost = 0;
122
123
21.6k
    SchedCandidate() = default;
124
  };
125
  /// Represent the type of SchedCandidate found within a single queue.
126
  enum CandResult {
127
    NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
128
    BestCost, Weak};
129
130
  /// Each Scheduling boundary is associated with ready queues. It tracks the
131
  /// current cycle in whichever direction at has moved, and maintains the state
132
  /// of "hazards" and other interlocks at the current cycle.
133
  struct VLIWSchedBoundary {
134
    VLIWMachineScheduler *DAG = nullptr;
135
    const TargetSchedModel *SchedModel = nullptr;
136
137
    ReadyQueue Available;
138
    ReadyQueue Pending;
139
    bool CheckPending = false;
140
141
    ScheduleHazardRecognizer *HazardRec = nullptr;
142
    VLIWResourceModel *ResourceModel = nullptr;
143
144
    unsigned CurrCycle = 0;
145
    unsigned IssueCount = 0;
146
    unsigned CriticalPathLength = 0;
147
148
    /// MinReadyCycle - Cycle of the soonest available instruction.
149
    unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();
150
151
    // Remember the greatest min operand latency.
152
    unsigned MaxMinLatency = 0;
153
154
    /// Pending queues extend the ready queues with the same ID and the
155
    /// PendingFlag set.
156
    VLIWSchedBoundary(unsigned ID, const Twine &Name)
157
        : Available(ID, Name+".A"),
158
6.69k
          Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {}
159
160
6.69k
    ~VLIWSchedBoundary() {
161
6.69k
      delete ResourceModel;
162
6.69k
      delete HazardRec;
163
6.69k
    }
164
165
10.0k
    void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
166
10.0k
      DAG = dag;
167
10.0k
      SchedModel = smodel;
168
10.0k
      CurrCycle = 0;
169
10.0k
      IssueCount = 0;
170
10.0k
      // Initialize the critical path length limit, which used by the scheduling
171
10.0k
      // cost model to determine the value for scheduling an instruction. We use
172
10.0k
      // a slightly different heuristic for small and large functions. For small
173
10.0k
      // functions, it's important to use the height/depth of the instruction.
174
10.0k
      // For large functions, prioritizing by height or depth increases spills.
175
10.0k
      CriticalPathLength = DAG->getBBSize() / SchedModel->getIssueWidth();
176
10.0k
      if (DAG->getBBSize() < 50)
177
9.55k
        // We divide by two as a cheap and simple heuristic to reduce the
178
9.55k
        // critcal path length, which increases the priority of using the graph
179
9.55k
        // height/depth in the scheduler's cost computation.
180
9.55k
        CriticalPathLength >>= 1;
181
476
      else {
182
476
        // For large basic blocks, we prefer a larger critical path length to
183
476
        // decrease the priority of using the graph height/depth.
184
476
        unsigned MaxPath = 0;
185
476
        for (auto &SU : DAG->SUnits)
186
9.33k
          MaxPath = std::max(MaxPath, isTop() ? 
SU.getHeight()4.66k
:
SU.getDepth()4.66k
);
187
476
        CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
188
476
      }
189
10.0k
    }
190
191
275k
    bool isTop() const {
192
275k
      return Available.getID() == ConvergingVLIWScheduler::TopQID;
193
275k
    }
194
195
    bool checkHazard(SUnit *SU);
196
197
    void releaseNode(SUnit *SU, unsigned ReadyCycle);
198
199
    void bumpCycle();
200
201
    void bumpNode(SUnit *SU);
202
203
    void releasePending();
204
205
    void removeReady(SUnit *SU);
206
207
    SUnit *pickOnlyChoice();
208
209
246k
    bool isLatencyBound(SUnit *SU) {
210
246k
      if (CurrCycle >= CriticalPathLength)
211
46.2k
        return true;
212
200k
      unsigned PathLength = isTop() ? 
SU->getHeight()118k
:
SU->getDepth()81.5k
;
213
200k
      return CriticalPathLength - CurrCycle <= PathLength;
214
200k
    }
215
  };
216
217
  VLIWMachineScheduler *DAG = nullptr;
218
  const TargetSchedModel *SchedModel = nullptr;
219
220
  // State of the top and bottom scheduled instruction boundaries.
221
  VLIWSchedBoundary Top;
222
  VLIWSchedBoundary Bot;
223
224
  /// List of pressure sets that have a high pressure level in the region.
225
  std::vector<bool> HighPressureSets;
226
227
public:
228
  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
229
  enum {
230
    TopQID = 1,
231
    BotQID = 2,
232
    LogMaxQID = 2
233
  };
234
235
3.34k
  ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
236
237
  void initialize(ScheduleDAGMI *dag) override;
238
239
  SUnit *pickNode(bool &IsTopNode) override;
240
241
  void schedNode(SUnit *SU, bool IsTopNode) override;
242
243
  void releaseTopNode(SUnit *SU) override;
244
245
  void releaseBottomNode(SUnit *SU) override;
246
247
0
  unsigned reportPackets() {
248
0
    return Top.ResourceModel->getTotalPackets() +
249
0
           Bot.ResourceModel->getTotalPackets();
250
0
  }
251
252
protected:
253
  SUnit *pickNodeBidrectional(bool &IsTopNode);
254
255
  int pressureChange(const SUnit *SU, bool isBotUp);
256
257
  int SchedulingCost(ReadyQueue &Q,
258
                     SUnit *SU, SchedCandidate &Candidate,
259
                     RegPressureDelta &Delta, bool verbose);
260
261
  CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone,
262
                               const RegPressureTracker &RPTracker,
263
                               SchedCandidate &Candidate);
264
#ifndef NDEBUG
265
  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
266
                      int Cost, PressureChange P = PressureChange());
267
268
  void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
269
                             SchedCandidate &Candidate, ReadyQueue &Q);
270
#endif
271
};
272
273
} // end namespace llvm
274
275
#endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H