Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/DFAPacketizer.cpp
Line
Count
Source (jump to first uncovered line)
1
//=- llvm/CodeGen/DFAPacketizer.cpp - DFA Packetizer for VLIW -*- 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
// This class implements a deterministic finite automaton (DFA) based
10
// packetizing mechanism for VLIW architectures. It provides APIs to
11
// determine whether there exists a legal mapping of instructions to
12
// functional unit assignments in a packet. The DFA is auto-generated from
13
// the target's Schedule.td file.
14
//
15
// A DFA consists of 3 major elements: states, inputs, and transitions. For
16
// the packetizing mechanism, the input is the set of instruction classes for
17
// a target. The state models all possible combinations of functional unit
18
// consumption for a given set of instructions in a packet. A transition
19
// models the addition of an instruction to a packet. In the DFA constructed
20
// by this class, if an instruction can be added to a packet, then a valid
21
// transition exists from the corresponding state. Invalid transitions
22
// indicate that the instruction cannot be added to the current packet.
23
//
24
//===----------------------------------------------------------------------===//
25
26
#include "llvm/CodeGen/DFAPacketizer.h"
27
#include "llvm/CodeGen/MachineFunction.h"
28
#include "llvm/CodeGen/MachineInstr.h"
29
#include "llvm/CodeGen/MachineInstrBundle.h"
30
#include "llvm/CodeGen/ScheduleDAG.h"
31
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
32
#include "llvm/MC/MCInstrDesc.h"
33
#include "llvm/MC/MCInstrItineraries.h"
34
#include "llvm/Support/CommandLine.h"
35
#include "llvm/Support/Debug.h"
36
#include "llvm/Support/raw_ostream.h"
37
#include "llvm/Target/TargetInstrInfo.h"
38
#include "llvm/Target/TargetSubtargetInfo.h"
39
#include <algorithm>
40
#include <cassert>
41
#include <iterator>
42
#include <memory>
43
#include <vector>
44
45
using namespace llvm;
46
47
#define DEBUG_TYPE "packets"
48
49
static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,
50
  cl::init(0), cl::desc("If present, stops packetizing after N instructions"));
51
52
static unsigned InstrCount = 0;
53
54
// --------------------------------------------------------------------
55
// Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
56
57
311k
static DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
58
311k
  return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
59
311k
}
60
61
/// Return the DFAInput for an instruction class input vector.
62
/// This function is used in both DFAPacketizer.cpp and in
63
/// DFAPacketizerEmitter.cpp.
64
0
static DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
65
0
  DFAInput InsnInput = 0;
66
0
  assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
67
0
         "Exceeded maximum number of DFA terms");
68
0
  for (auto U : InsnClass)
69
0
    InsnInput = addDFAFuncUnits(InsnInput, U);
70
0
  return InsnInput;
71
0
}
72
73
// --------------------------------------------------------------------
74
75
DFAPacketizer::DFAPacketizer(const InstrItineraryData *I,
76
                             const DFAStateInput (*SIT)[2],
77
                             const unsigned *SET):
78
7.52k
  InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET) {
79
7.52k
  // Make sure DFA types are large enough for the number of terms & resources.
80
7.52k
  static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <=
81
7.52k
                    (8 * sizeof(DFAInput)),
82
7.52k
                "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput");
83
7.52k
  static_assert(
84
7.52k
      (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)),
85
7.52k
      "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput");
86
7.52k
}
87
88
// Read the DFA transition table and update CachedTable.
89
//
90
// Format of the transition tables:
91
// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
92
//                           transitions
93
// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable
94
//                         for the ith state
95
//
96
283k
void DFAPacketizer::ReadTable(unsigned int state) {
97
283k
  unsigned ThisState = DFAStateEntryTable[state];
98
283k
  unsigned NextStateInTable = DFAStateEntryTable[state+1];
99
283k
  // Early exit in case CachedTable has already contains this
100
283k
  // state's transitions.
101
283k
  if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0])))
102
263k
    return;
103
19.7k
104
328k
  
for (unsigned i = ThisState; 19.7k
i < NextStateInTable328k
;
i++308k
)
105
308k
    CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] =
106
308k
      DFAStateInputTable[i][1];
107
283k
}
108
109
// Return the DFAInput for an instruction class.
110
283k
DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) {
111
283k
  // Note: this logic must match that in DFAPacketizerDefs.h for input vectors.
112
283k
  DFAInput InsnInput = 0;
113
283k
  unsigned i = 0;
114
283k
  (void)i;
115
283k
  for (const InstrStage *IS = InstrItins->beginStage(InsnClass),
116
594k
       *IE = InstrItins->endStage(InsnClass); 
IS != IE594k
;
++IS311k
) {
117
311k
    InsnInput = addDFAFuncUnits(InsnInput, IS->getUnits());
118
311k
    assert((i++ < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs");
119
311k
  }
120
283k
  return InsnInput;
121
283k
}
122
123
// Return the DFAInput for an instruction class input vector.
124
0
DFAInput DFAPacketizer::getInsnInput(const std::vector<unsigned> &InsnClass) {
125
0
  return getDFAInsnInput(InsnClass);
126
0
}
127
128
// Check if the resources occupied by a MCInstrDesc are available in the
129
// current state.
130
206k
bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) {
131
206k
  unsigned InsnClass = MID->getSchedClass();
132
206k
  DFAInput InsnInput = getInsnInput(InsnClass);
133
206k
  UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
134
206k
  ReadTable(CurrentState);
135
206k
  return CachedTable.count(StateTrans) != 0;
136
206k
}
137
138
// Reserve the resources occupied by a MCInstrDesc and change the current
139
// state to reflect that change.
140
76.6k
void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {
141
76.6k
  unsigned InsnClass = MID->getSchedClass();
142
76.6k
  DFAInput InsnInput = getInsnInput(InsnClass);
143
76.6k
  UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
144
76.6k
  ReadTable(CurrentState);
145
76.6k
  assert(CachedTable.count(StateTrans) != 0);
146
76.6k
  CurrentState = CachedTable[StateTrans];
147
76.6k
}
148
149
// Check if the resources occupied by a machine instruction are available
150
// in the current state.
151
206k
bool DFAPacketizer::canReserveResources(MachineInstr &MI) {
152
206k
  const MCInstrDesc &MID = MI.getDesc();
153
206k
  return canReserveResources(&MID);
154
206k
}
155
156
// Reserve the resources occupied by a machine instruction and change the
157
// current state to reflect that change.
158
76.6k
void DFAPacketizer::reserveResources(MachineInstr &MI) {
159
76.6k
  const MCInstrDesc &MID = MI.getDesc();
160
76.6k
  reserveResources(&MID);
161
76.6k
}
162
163
namespace llvm {
164
165
// This class extends ScheduleDAGInstrs and overrides the schedule method
166
// to build the dependence graph.
167
class DefaultVLIWScheduler : public ScheduleDAGInstrs {
168
private:
169
  AliasAnalysis *AA;
170
  /// Ordered list of DAG postprocessing steps.
171
  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
172
173
public:
174
  DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI,
175
                       AliasAnalysis *AA);
176
177
  // Actual scheduling work.
178
  void schedule() override;
179
180
  /// DefaultVLIWScheduler takes ownership of the Mutation object.
181
2.59k
  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
182
2.59k
    Mutations.push_back(std::move(Mutation));
183
2.59k
  }
184
185
protected:
186
  void postprocessDAG();
187
};
188
189
} // end namespace llvm
190
191
DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF,
192
                                           MachineLoopInfo &MLI,
193
                                           AliasAnalysis *AA)
194
2.92k
    : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
195
2.92k
  CanHandleTerminators = true;
196
2.92k
}
197
198
/// Apply each ScheduleDAGMutation step in order.
199
3.59k
void DefaultVLIWScheduler::postprocessDAG() {
200
3.59k
  for (auto &M : Mutations)
201
4.65k
    M->apply(this);
202
3.59k
}
203
204
3.59k
void DefaultVLIWScheduler::schedule() {
205
3.59k
  // Build the scheduling graph.
206
3.59k
  buildSchedGraph(AA);
207
3.59k
  postprocessDAG();
208
3.59k
}
209
210
VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf,
211
                                       MachineLoopInfo &mli, AliasAnalysis *aa)
212
2.92k
    : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
213
2.92k
  ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget());
214
2.92k
  VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA);
215
2.92k
}
216
217
2.92k
VLIWPacketizerList::~VLIWPacketizerList() {
218
2.92k
  delete VLIWScheduler;
219
2.92k
  delete ResourceTracker;
220
2.92k
}
221
222
// End the current packet, bundle packet instructions and reset DFA state.
223
void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,
224
39.3k
                                   MachineBasicBlock::iterator MI) {
225
39.3k
  DEBUG({
226
39.3k
    if (!CurrentPacketMIs.empty()) {
227
39.3k
      dbgs() << "Finalizing packet:\n";
228
39.3k
      for (MachineInstr *MI : CurrentPacketMIs)
229
39.3k
        dbgs() << " * " << *MI;
230
39.3k
    }
231
39.3k
  });
232
39.3k
  if (
CurrentPacketMIs.size() > 139.3k
) {
233
16.9k
    MachineInstr &MIFirst = *CurrentPacketMIs.front();
234
16.9k
    finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
235
16.9k
  }
236
39.3k
  CurrentPacketMIs.clear();
237
39.3k
  ResourceTracker->clearResources();
238
39.3k
  DEBUG(dbgs() << "End packet\n");
239
39.3k
}
240
241
// Bundle machine instructions into packets.
242
void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,
243
                                      MachineBasicBlock::iterator BeginItr,
244
3.59k
                                      MachineBasicBlock::iterator EndItr) {
245
3.59k
  assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
246
3.59k
  VLIWScheduler->startBlock(MBB);
247
3.59k
  VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
248
3.59k
                             std::distance(BeginItr, EndItr));
249
3.59k
  VLIWScheduler->schedule();
250
3.59k
251
3.59k
  DEBUG({
252
3.59k
    dbgs() << "Scheduling DAG of the packetize region\n";
253
3.59k
    for (SUnit &SU : VLIWScheduler->SUnits)
254
3.59k
      SU.dumpAll(VLIWScheduler);
255
3.59k
  });
256
3.59k
257
3.59k
  // Generate MI -> SU map.
258
3.59k
  MIToSUnit.clear();
259
3.59k
  for (SUnit &SU : VLIWScheduler->SUnits)
260
69.4k
    MIToSUnit[SU.getInstr()] = &SU;
261
3.59k
262
3.59k
  bool LimitPresent = InstrLimit.getPosition();
263
3.59k
264
3.59k
  // The main packetizer loop.
265
73.0k
  for (; 
BeginItr != EndItr73.0k
;
++BeginItr69.4k
) {
266
69.4k
    if (
LimitPresent69.4k
) {
267
0
      if (
InstrCount >= InstrLimit0
) {
268
0
        EndItr = BeginItr;
269
0
        break;
270
0
      }
271
0
      InstrCount++;
272
0
    }
273
69.4k
    MachineInstr &MI = *BeginItr;
274
69.4k
    initPacketizerState();
275
69.4k
276
69.4k
    // End the current packet if needed.
277
69.4k
    if (
isSoloInstruction(MI)69.4k
) {
278
13.9k
      endPacket(MBB, MI);
279
13.9k
      continue;
280
13.9k
    }
281
55.4k
282
55.4k
    // Ignore pseudo instructions.
283
55.4k
    
if (55.4k
ignorePseudoInstruction(MI, MBB)55.4k
)
284
12
      continue;
285
55.4k
286
55.4k
    SUnit *SUI = MIToSUnit[&MI];
287
55.4k
    assert(SUI && "Missing SUnit Info!");
288
55.4k
289
55.4k
    // Ask DFA if machine resource is available for MI.
290
55.4k
    DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);
291
55.4k
292
55.4k
    bool ResourceAvail = ResourceTracker->canReserveResources(MI);
293
55.4k
    DEBUG({
294
55.4k
      if (ResourceAvail)
295
55.4k
        dbgs() << "  Resources are available for adding MI to packet\n";
296
55.4k
      else
297
55.4k
        dbgs() << "  Resources NOT available\n";
298
55.4k
    });
299
55.4k
    if (
ResourceAvail && 55.4k
shouldAddToPacket(MI)53.1k
) {
300
53.0k
      // Dependency check for MI with instructions in CurrentPacketMIs.
301
61.6k
      for (auto MJ : CurrentPacketMIs) {
302
61.6k
        SUnit *SUJ = MIToSUnit[MJ];
303
61.6k
        assert(SUJ && "Missing SUnit Info!");
304
61.6k
305
61.6k
        DEBUG(dbgs() << "  Checking against MJ " << *MJ);
306
61.6k
        // Is it legal to packetize SUI and SUJ together.
307
61.6k
        if (
!isLegalToPacketizeTogether(SUI, SUJ)61.6k
) {
308
6.89k
          DEBUG(dbgs() << "  Not legal to add MI, try to prune\n");
309
6.89k
          // Allow packetization if dependency can be pruned.
310
6.89k
          if (
!isLegalToPruneDependencies(SUI, SUJ)6.89k
) {
311
6.89k
            // End the packet if dependency cannot be pruned.
312
6.89k
            DEBUG(dbgs() << "  Could not prune dependencies for adding MI\n");
313
6.89k
            endPacket(MBB, MI);
314
6.89k
            break;
315
6.89k
          }
316
0
          
DEBUG0
(dbgs() << " Pruned dependence for adding MI\n");
317
0
        }
318
61.6k
      }
319
55.4k
    } else {
320
2.37k
      DEBUG(if (ResourceAvail)
321
2.37k
        dbgs() << "Resources are available, but instruction should not be "
322
2.37k
                  "added to packet\n  " << MI);
323
2.37k
      // End the packet if resource is not available, or if the instruction
324
2.37k
      // shoud not be added to the current packet.
325
2.37k
      endPacket(MBB, MI);
326
2.37k
    }
327
55.4k
328
55.4k
    // Add MI to the current packet.
329
55.4k
    DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
330
69.4k
    BeginItr = addToPacket(MI);
331
69.4k
  } // For all instructions in the packetization range.
332
3.59k
333
3.59k
  // End any packet left behind.
334
3.59k
  endPacket(MBB, EndItr);
335
3.59k
  VLIWScheduler->exitRegion();
336
3.59k
  VLIWScheduler->finishBlock();
337
3.59k
}
338
339
// Add a DAG mutation object to the ordered list.
340
void VLIWPacketizerList::addMutation(
341
2.59k
      std::unique_ptr<ScheduleDAGMutation> Mutation) {
342
2.59k
  VLIWScheduler->addMutation(std::move(Mutation));
343
2.59k
}