Coverage Report

Created: 2018-11-16 02:38

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