Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/SystemZ/SystemZMachineScheduler.cpp
Line
Count
Source (jump to first uncovered line)
1
//-- SystemZMachineScheduler.cpp - SystemZ Scheduler Interface -*- 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
// -------------------------- Post RA scheduling ---------------------------- //
10
// SystemZPostRASchedStrategy is a scheduling strategy which is plugged into
11
// the MachineScheduler. It has a sorted Available set of SUs and a pickNode()
12
// implementation that looks to optimize decoder grouping and balance the
13
// usage of processor resources. Scheduler states are saved for the end
14
// region of each MBB, so that a successor block can learn from it.
15
//===----------------------------------------------------------------------===//
16
17
#include "SystemZMachineScheduler.h"
18
19
using namespace llvm;
20
21
#define DEBUG_TYPE "machine-scheduler"
22
23
#ifndef NDEBUG
24
// Print the set of SUs
25
void SystemZPostRASchedStrategy::SUSet::
26
dump(SystemZHazardRecognizer &HazardRec) const {
27
  dbgs() << "{";
28
  for (auto &SU : *this) {
29
    HazardRec.dumpSU(SU, dbgs());
30
    if (SU != *rbegin())
31
      dbgs() << ",  ";
32
  }
33
  dbgs() << "}\n";
34
}
35
#endif
36
37
// Try to find a single predecessor that would be interesting for the
38
// scheduler in the top-most region of MBB.
39
static MachineBasicBlock *getSingleSchedPred(MachineBasicBlock *MBB,
40
4.17k
                                             const MachineLoop *Loop) {
41
4.17k
  MachineBasicBlock *PredMBB = nullptr;
42
4.17k
  if (MBB->pred_size() == 1)
43
311
    PredMBB = *MBB->pred_begin();
44
4.17k
45
4.17k
  // The loop header has two predecessors, return the latch, but not for a
46
4.17k
  // single block loop.
47
4.17k
  if (MBB->pred_size() == 2 && 
Loop != nullptr155
&&
Loop->getHeader() == MBB83
) {
48
237
    for (auto I = MBB->pred_begin(); I != MBB->pred_end(); 
++I158
)
49
158
      if (Loop->contains(*I))
50
79
        PredMBB = (*I == MBB ? 
nullptr67
:
*I12
);
51
79
  }
52
4.17k
53
4.17k
  assert ((PredMBB == nullptr || !Loop || Loop->contains(PredMBB))
54
4.17k
          && "Loop MBB should not consider predecessor outside of loop.");
55
4.17k
56
4.17k
  return PredMBB;
57
4.17k
}
58
59
void SystemZPostRASchedStrategy::
60
8.65k
advanceTo(MachineBasicBlock::iterator NextBegin) {
61
8.65k
  MachineBasicBlock::iterator LastEmittedMI = HazardRec->getLastEmittedMI();
62
8.65k
  MachineBasicBlock::iterator I =
63
8.65k
    ((LastEmittedMI != nullptr && 
LastEmittedMI->getParent() == MBB2.75k
) ?
64
6.33k
     
std::next(LastEmittedMI)2.32k
: MBB->begin());
65
8.65k
66
12.4k
  for (; I != NextBegin; 
++I3.78k
) {
67
3.78k
    if (I->isPosition() || 
I->isDebugInstr()2.72k
)
68
1.05k
      continue;
69
2.72k
    HazardRec->emitInstruction(&*I);
70
2.72k
  }
71
8.65k
}
72
73
2.28k
void SystemZPostRASchedStrategy::initialize(ScheduleDAGMI *dag) {
74
2.28k
  LLVM_DEBUG(HazardRec->dumpState(););
75
2.28k
}
76
77
4.17k
void SystemZPostRASchedStrategy::enterMBB(MachineBasicBlock *NextMBB) {
78
4.17k
  assert ((SchedStates.find(NextMBB) == SchedStates.end()) &&
79
4.17k
          "Entering MBB twice?");
80
4.17k
  LLVM_DEBUG(dbgs() << "** Entering " << printMBBReference(*NextMBB));
81
4.17k
82
4.17k
  MBB = NextMBB;
83
4.17k
84
4.17k
  /// Create a HazardRec for MBB, save it in SchedStates and set HazardRec to
85
4.17k
  /// point to it.
86
4.17k
  HazardRec = SchedStates[MBB] = new SystemZHazardRecognizer(TII, &SchedModel);
87
4.17k
  LLVM_DEBUG(const MachineLoop *Loop = MLI->getLoopFor(MBB);
88
4.17k
             if (Loop && Loop->getHeader() == MBB) dbgs() << " (Loop header)";
89
4.17k
             dbgs() << ":\n";);
90
4.17k
91
4.17k
  // Try to take over the state from a single predecessor, if it has been
92
4.17k
  // scheduled. If this is not possible, we are done.
93
4.17k
  MachineBasicBlock *SinglePredMBB =
94
4.17k
    getSingleSchedPred(MBB, MLI->getLoopFor(MBB));
95
4.17k
  if (SinglePredMBB == nullptr ||
96
4.17k
      
SchedStates.find(SinglePredMBB) == SchedStates.end()323
)
97
3.86k
    return;
98
311
99
311
  LLVM_DEBUG(dbgs() << "** Continued scheduling from "
100
311
                    << printMBBReference(*SinglePredMBB) << "\n";);
101
311
102
311
  HazardRec->copyState(SchedStates[SinglePredMBB]);
103
311
  LLVM_DEBUG(HazardRec->dumpState(););
104
311
105
311
  // Emit incoming terminator(s). Be optimistic and assume that branch
106
311
  // prediction will generally do "the right thing".
107
311
  for (MachineBasicBlock::iterator I = SinglePredMBB->getFirstTerminator();
108
598
       I != SinglePredMBB->end(); 
I++287
) {
109
310
    LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; I->dump(););
110
310
    bool TakenBranch = (I->isBranch() &&
111
310
      
(184
TII->getBranchInfo(*I).Target->isReg()184
|| // Relative branch
112
184
       
TII->getBranchInfo(*I).Target->getMBB() == MBB173
));
113
310
    HazardRec->emitInstruction(&*I, TakenBranch);
114
310
    if (TakenBranch)
115
23
      break;
116
310
  }
117
311
}
118
119
4.17k
void SystemZPostRASchedStrategy::leaveMBB() {
120
4.17k
  LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);
121
4.17k
122
4.17k
  // Advance to first terminator. The successor block will handle terminators
123
4.17k
  // dependent on CFG layout (T/NT branch etc).
124
4.17k
  advanceTo(MBB->getFirstTerminator());
125
4.17k
}
126
127
SystemZPostRASchedStrategy::
128
SystemZPostRASchedStrategy(const MachineSchedContext *C)
129
  : MLI(C->MLI),
130
    TII(static_cast<const SystemZInstrInfo *>
131
        (C->MF->getSubtarget().getInstrInfo())),
132
3.68k
    MBB(nullptr), HazardRec(nullptr) {
133
3.68k
  const TargetSubtargetInfo *ST = &C->MF->getSubtarget();
134
3.68k
  SchedModel.init(ST);
135
3.68k
}
136
137
3.68k
SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() {
138
3.68k
  // Delete hazard recognizers kept around for each MBB.
139
4.17k
  for (auto I : SchedStates) {
140
4.17k
    SystemZHazardRecognizer *hazrec = I.second;
141
4.17k
    delete hazrec;
142
4.17k
  }
143
3.68k
}
144
145
void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,
146
                                            MachineBasicBlock::iterator End,
147
4.47k
                                            unsigned NumRegionInstrs) {
148
4.47k
  // Don't emit the terminators.
149
4.47k
  if (Begin->isTerminator())
150
0
    return;
151
4.47k
152
4.47k
  // Emit any instructions before start of region.
153
4.47k
  advanceTo(Begin);
154
4.47k
}
155
156
// Pick the next node to schedule.
157
23.9k
SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) {
158
23.9k
  // Only scheduling top-down.
159
23.9k
  IsTopNode = true;
160
23.9k
161
23.9k
  if (Available.empty())
162
2.28k
    return nullptr;
163
21.6k
164
21.6k
  // If only one choice, return it.
165
21.6k
  if (Available.size() == 1) {
166
15.0k
    LLVM_DEBUG(dbgs() << "** Only one: ";
167
15.0k
               HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
168
15.0k
    return *Available.begin();
169
15.0k
  }
170
6.58k
171
6.58k
  // All nodes that are possible to schedule are stored in the Available set.
172
6.58k
  LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec););
173
6.58k
174
6.58k
  Candidate Best;
175
12.7k
  for (auto *SU : Available) {
176
12.7k
177
12.7k
    // SU is the next candidate to be compared against current Best.
178
12.7k
    Candidate c(SU, *HazardRec);
179
12.7k
180
12.7k
    // Remeber which SU is the best candidate.
181
12.7k
    if (Best.SU == nullptr || 
c < Best6.15k
) {
182
7.38k
      Best = c;
183
7.38k
      LLVM_DEBUG(dbgs() << "** Best so far: ";);
184
7.38k
    } else
185
12.7k
      LLVM_DEBUG(dbgs() << "** Tried      : ";);
186
12.7k
    LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts();
187
12.7k
               dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";);
188
12.7k
189
12.7k
    // Once we know we have seen all SUs that affect grouping or use unbuffered
190
12.7k
    // resources, we can stop iterating if Best looks good.
191
12.7k
    if (!SU->isScheduleHigh && 
Best.noCost()12.4k
)
192
4.72k
      break;
193
12.7k
  }
194
6.58k
195
6.58k
  assert (Best.SU != nullptr);
196
6.58k
  return Best.SU;
197
6.58k
}
198
199
SystemZPostRASchedStrategy::Candidate::
200
12.7k
Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
201
12.7k
  SU = SU_;
202
12.7k
203
12.7k
  // Check the grouping cost. For a node that must begin / end a
204
12.7k
  // group, it is positive if it would do so prematurely, or negative
205
12.7k
  // if it would fit naturally into the schedule.
206
12.7k
  GroupingCost = HazardRec.groupingCost(SU);
207
12.7k
208
12.7k
  // Check the resources cost for this SU.
209
12.7k
  ResourcesCost = HazardRec.resourcesCost(SU);
210
12.7k
}
Unexecuted instantiation: llvm::SystemZPostRASchedStrategy::Candidate::Candidate(llvm::SUnit*, llvm::SystemZHazardRecognizer&)
llvm::SystemZPostRASchedStrategy::Candidate::Candidate(llvm::SUnit*, llvm::SystemZHazardRecognizer&)
Line
Count
Source
200
12.7k
Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
201
12.7k
  SU = SU_;
202
12.7k
203
12.7k
  // Check the grouping cost. For a node that must begin / end a
204
12.7k
  // group, it is positive if it would do so prematurely, or negative
205
12.7k
  // if it would fit naturally into the schedule.
206
12.7k
  GroupingCost = HazardRec.groupingCost(SU);
207
12.7k
208
12.7k
  // Check the resources cost for this SU.
209
12.7k
  ResourcesCost = HazardRec.resourcesCost(SU);
210
12.7k
}
211
212
bool SystemZPostRASchedStrategy::Candidate::
213
6.15k
operator<(const Candidate &other) {
214
6.15k
215
6.15k
  // Check decoder grouping.
216
6.15k
  if (GroupingCost < other.GroupingCost)
217
132
    return true;
218
6.02k
  if (GroupingCost > other.GroupingCost)
219
73
    return false;
220
5.94k
221
5.94k
  // Compare the use of resources.
222
5.94k
  if (ResourcesCost < other.ResourcesCost)
223
671
    return true;
224
5.27k
  if (ResourcesCost > other.ResourcesCost)
225
48
    return false;
226
5.22k
227
5.22k
  // Higher SU is otherwise generally better.
228
5.22k
  if (SU->getHeight() > other.SU->getHeight())
229
0
    return true;
230
5.22k
  if (SU->getHeight() < other.SU->getHeight())
231
3.72k
    return false;
232
1.50k
233
1.50k
  // If all same, fall back to original order.
234
1.50k
  if (SU->NodeNum < other.SU->NodeNum)
235
0
    return true;
236
1.50k
237
1.50k
  return false;
238
1.50k
}
239
240
21.6k
void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
241
21.6k
  LLVM_DEBUG(dbgs() << "** Scheduling SU(" << SU->NodeNum << ") ";
242
21.6k
             if (Available.size() == 1) dbgs() << "(only one) ";
243
21.6k
             Candidate c(SU, *HazardRec); c.dumpCosts(); dbgs() << "\n";);
244
21.6k
245
21.6k
  // Remove SU from Available set and update HazardRec.
246
21.6k
  Available.erase(SU);
247
21.6k
  HazardRec->EmitInstruction(SU);
248
21.6k
}
249
250
21.6k
void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) {
251
21.6k
  // Set isScheduleHigh flag on all SUs that we want to consider first in
252
21.6k
  // pickNode().
253
21.6k
  const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU);
254
21.6k
  bool AffectsGrouping = (SC->isValid() && 
(21.1k
SC->BeginGroup21.1k
||
SC->EndGroup20.6k
));
255
21.6k
  SU->isScheduleHigh = (AffectsGrouping || 
SU->isUnbuffered21.0k
);
256
21.6k
257
21.6k
  // Put all released SUs in the Available set.
258
21.6k
  Available.insert(SU);
259
21.6k
}