Coverage Report

Created: 2019-07-24 05:18

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