Coverage Report

Created: 2017-10-03 07:32

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