Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/DFAPacketizer.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/CodeGen/DFAPacketizer.h - 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
#ifndef LLVM_CODEGEN_DFAPACKETIZER_H
26
#define LLVM_CODEGEN_DFAPACKETIZER_H
27
28
#include "llvm/ADT/DenseMap.h"
29
#include "llvm/CodeGen/MachineBasicBlock.h"
30
#include "llvm/CodeGen/ScheduleDAGMutation.h"
31
#include <cstdint>
32
#include <map>
33
#include <memory>
34
#include <utility>
35
#include <vector>
36
37
namespace llvm {
38
39
class DefaultVLIWScheduler;
40
class InstrItineraryData;
41
class MachineFunction;
42
class MachineInstr;
43
class MachineLoopInfo;
44
class MCInstrDesc;
45
class SUnit;
46
class TargetInstrInfo;
47
48
// --------------------------------------------------------------------
49
// Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
50
51
// DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
52
// This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
53
//
54
// e.g. terms x resource bit combinations that fit in uint32_t:
55
//      4 terms x 8  bits = 32 bits
56
//      3 terms x 10 bits = 30 bits
57
//      2 terms x 16 bits = 32 bits
58
//
59
// e.g. terms x resource bit combinations that fit in uint64_t:
60
//      8 terms x 8  bits = 64 bits
61
//      7 terms x 9  bits = 63 bits
62
//      6 terms x 10 bits = 60 bits
63
//      5 terms x 12 bits = 60 bits
64
//      4 terms x 16 bits = 64 bits <--- current
65
//      3 terms x 21 bits = 63 bits
66
//      2 terms x 32 bits = 64 bits
67
//
68
#define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
69
489k
#define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.
70
71
using DFAInput = uint64_t;
72
using DFAStateInput = int64_t;
73
74
#define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
75
// --------------------------------------------------------------------
76
77
class DFAPacketizer {
78
private:
79
  using UnsignPair = std::pair<unsigned, DFAInput>;
80
81
  const InstrItineraryData *InstrItins;
82
  int CurrentState = 0;
83
  const DFAStateInput (*DFAStateInputTable)[2];
84
  const unsigned *DFAStateEntryTable;
85
86
  // CachedTable is a map from <FromState, Input> to ToState.
87
  DenseMap<UnsignPair, unsigned> CachedTable;
88
89
  // Read the DFA transition table and update CachedTable.
90
  void ReadTable(unsigned state);
91
92
public:
93
  DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
94
                const unsigned *SET);
95
96
  // Reset the current state to make all resources available.
97
108k
  void clearResources() {
98
108k
    CurrentState = 0;
99
108k
  }
100
101
  // Return the DFAInput for an instruction class.
102
  DFAInput getInsnInput(unsigned InsnClass);
103
104
  // Return the DFAInput for an instruction class input vector.
105
  static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);
106
107
  // Check if the resources occupied by a MCInstrDesc are available in
108
  // the current state.
109
  bool canReserveResources(const MCInstrDesc *MID);
110
111
  // Reserve the resources occupied by a MCInstrDesc and change the current
112
  // state to reflect that change.
113
  void reserveResources(const MCInstrDesc *MID);
114
115
  // Check if the resources occupied by a machine instruction are available
116
  // in the current state.
117
  bool canReserveResources(MachineInstr &MI);
118
119
  // Reserve the resources occupied by a machine instruction and change the
120
  // current state to reflect that change.
121
  void reserveResources(MachineInstr &MI);
122
123
35.7k
  const InstrItineraryData *getInstrItins() const { return InstrItins; }
124
};
125
126
// VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
127
// packetizer works on machine basic blocks. For each instruction I in BB,
128
// the packetizer consults the DFA to see if machine resources are available
129
// to execute I. If so, the packetizer checks if I depends on any instruction
130
// in the current packet. If no dependency is found, I is added to current
131
// packet and the machine resource is marked as taken. If any dependency is
132
// found, a target API call is made to prune the dependence.
133
class VLIWPacketizerList {
134
protected:
135
  MachineFunction &MF;
136
  const TargetInstrInfo *TII;
137
  AliasAnalysis *AA;
138
139
  // The VLIW Scheduler.
140
  DefaultVLIWScheduler *VLIWScheduler;
141
  // Vector of instructions assigned to the current packet.
142
  std::vector<MachineInstr*> CurrentPacketMIs;
143
  // DFA resource tracker.
144
  DFAPacketizer *ResourceTracker;
145
  // Map: MI -> SU.
146
  std::map<MachineInstr*, SUnit*> MIToSUnit;
147
148
public:
149
  // The AliasAnalysis parameter can be nullptr.
150
  VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
151
                     AliasAnalysis *AA);
152
153
  virtual ~VLIWPacketizerList();
154
155
  // Implement this API in the backend to bundle instructions.
156
  void PacketizeMIs(MachineBasicBlock *MBB,
157
                    MachineBasicBlock::iterator BeginItr,
158
                    MachineBasicBlock::iterator EndItr);
159
160
  // Return the ResourceTracker.
161
2.29k
  DFAPacketizer *getResourceTracker() {return ResourceTracker;}
162
163
  // addToPacket - Add MI to the current packet.
164
46.6k
  virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) {
165
46.6k
    CurrentPacketMIs.push_back(&MI);
166
46.6k
    ResourceTracker->reserveResources(MI);
167
46.6k
    return MI;
168
46.6k
  }
169
170
  // End the current packet and reset the state of the packetizer.
171
  // Overriding this function allows the target-specific packetizer
172
  // to perform custom finalization.
173
  virtual void endPacket(MachineBasicBlock *MBB,
174
                         MachineBasicBlock::iterator MI);
175
176
  // Perform initialization before packetizing an instruction. This
177
  // function is supposed to be overrided by the target dependent packetizer.
178
0
  virtual void initPacketizerState() {}
179
180
  // Check if the given instruction I should be ignored by the packetizer.
181
  virtual bool ignorePseudoInstruction(const MachineInstr &I,
182
0
                                       const MachineBasicBlock *MBB) {
183
0
    return false;
184
0
  }
185
186
  // Return true if instruction MI can not be packetized with any other
187
  // instruction, which means that MI itself is a packet.
188
0
  virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
189
190
  // Check if the packetizer should try to add the given instruction to
191
  // the current packet. One reasons for which it may not be desirable
192
  // to include an instruction in the current packet could be that it
193
  // would cause a stall.
194
  // If this function returns "false", the current packet will be ended,
195
  // and the instruction will be added to the next packet.
196
46.5k
  virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
197
198
  // Check if it is legal to packetize SUI and SUJ together.
199
0
  virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
200
0
    return false;
201
0
  }
202
203
  // Check if it is legal to prune dependece between SUI and SUJ.
204
0
  virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
205
0
    return false;
206
0
  }
207
208
  // Add a DAG mutation to be done before the packetization begins.
209
  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
210
211
  bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
212
             bool UseTBAA = true) const;
213
214
private:
215
  bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
216
             bool UseTBAA = true) const;
217
};
218
219
} // end namespace llvm
220
221
#endif // LLVM_CODEGEN_DFAPACKETIZER_H