LLVM  10.0.0svn
DFAPacketizer.h
Go to the documentation of this file.
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"
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 #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 
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  const unsigned (*DFAResourceTransitionTable)[2];
86  const unsigned *DFAResourceTransitionEntryTable;
87 
88  // CachedTable is a map from <FromState, Input> to ToState.
90  // CachedResourceTransitions is a map from <FromState, Input> to a list of
91  // resource transitions.
93  CachedResourceTransitions;
94 
95  // Read the DFA transition table and update CachedTable.
96  void ReadTable(unsigned state);
97 
98  bool TrackResources = false;
99  // State for the current packet. Every entry is a possible packing of the
100  // bundle, indexed by cumulative resource state. Each entry is a list of the
101  // cumulative resource states after packing each instruction. For example if
102  // we pack I0: [0x4] and I1: [0x2] we will end up with:
103  // ResourceStates[0x6] = [0x4, 0x6]
105 
106 public:
107  DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
108  const unsigned *SET,
109  const unsigned (*RTT)[2] = nullptr,
110  const unsigned *RTET = nullptr);
111 
112  // Reset the current state to make all resources available.
113  void clearResources() {
114  CurrentState = 0;
115  ResourceStates.clear();
116  ResourceStates[0] = {};
117  }
118 
119  // Set whether this packetizer should track not just whether instructions
120  // can be packetized, but also which functional units each instruction ends up
121  // using after packetization.
122  void setTrackResources(bool Track) {
123  if (Track != TrackResources) {
124  TrackResources = Track;
125  if (Track) {
126  CachedTable.clear();
127  assert(DFAResourceTransitionEntryTable);
128  assert(DFAResourceTransitionTable);
129  }
130  }
131  assert(CurrentState == 0 && "Can only change TrackResources on an empty packetizer!");
132  }
133 
134  // Return the DFAInput for an instruction class.
135  DFAInput getInsnInput(unsigned InsnClass);
136 
137  // Return the DFAInput for an instruction class input vector.
138  static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);
139 
140  // Check if the resources occupied by a MCInstrDesc are available in
141  // the current state.
142  bool canReserveResources(const MCInstrDesc *MID);
143 
144  // Reserve the resources occupied by a MCInstrDesc and change the current
145  // state to reflect that change.
146  void reserveResources(const MCInstrDesc *MID);
147 
148  // Check if the resources occupied by a machine instruction are available
149  // in the current state.
151 
152  // Reserve the resources occupied by a machine instruction and change the
153  // current state to reflect that change.
154  void reserveResources(MachineInstr &MI);
155 
156  // Return the resources used by the InstIdx'th instruction added to this
157  // packet. The resources are returned as a bitvector of functional units.
158  //
159  // Note that a bundle may be packed in multiple valid ways. This function
160  // returns one arbitary valid packing.
161  //
162  // Requires setTrackResources(true) to have been called.
163  unsigned getUsedResources(unsigned InstIdx);
164 
165  const InstrItineraryData *getInstrItins() const { return InstrItins; }
166 };
167 
168 // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
169 // packetizer works on machine basic blocks. For each instruction I in BB,
170 // the packetizer consults the DFA to see if machine resources are available
171 // to execute I. If so, the packetizer checks if I depends on any instruction
172 // in the current packet. If no dependency is found, I is added to current
173 // packet and the machine resource is marked as taken. If any dependency is
174 // found, a target API call is made to prune the dependence.
176 protected:
180 
181  // The VLIW Scheduler.
183  // Vector of instructions assigned to the current packet.
184  std::vector<MachineInstr*> CurrentPacketMIs;
185  // DFA resource tracker.
187  // Map: MI -> SU.
188  std::map<MachineInstr*, SUnit*> MIToSUnit;
189 
190 public:
191  // The AliasAnalysis parameter can be nullptr.
193  AliasAnalysis *AA);
194 
195  virtual ~VLIWPacketizerList();
196 
197  // Implement this API in the backend to bundle instructions.
198  void PacketizeMIs(MachineBasicBlock *MBB,
201 
202  // Return the ResourceTracker.
203  DFAPacketizer *getResourceTracker() {return ResourceTracker;}
204 
205  // addToPacket - Add MI to the current packet.
207  CurrentPacketMIs.push_back(&MI);
208  ResourceTracker->reserveResources(MI);
209  return MI;
210  }
211 
212  // End the current packet and reset the state of the packetizer.
213  // Overriding this function allows the target-specific packetizer
214  // to perform custom finalization.
215  virtual void endPacket(MachineBasicBlock *MBB,
217 
218  // Perform initialization before packetizing an instruction. This
219  // function is supposed to be overrided by the target dependent packetizer.
220  virtual void initPacketizerState() {}
221 
222  // Check if the given instruction I should be ignored by the packetizer.
224  const MachineBasicBlock *MBB) {
225  return false;
226  }
227 
228  // Return true if instruction MI can not be packetized with any other
229  // instruction, which means that MI itself is a packet.
230  virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
231 
232  // Check if the packetizer should try to add the given instruction to
233  // the current packet. One reasons for which it may not be desirable
234  // to include an instruction in the current packet could be that it
235  // would cause a stall.
236  // If this function returns "false", the current packet will be ended,
237  // and the instruction will be added to the next packet.
238  virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
239 
240  // Check if it is legal to packetize SUI and SUJ together.
241  virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
242  return false;
243  }
244 
245  // Check if it is legal to prune dependece between SUI and SUJ.
246  virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
247  return false;
248  }
249 
250  // Add a DAG mutation to be done before the packetization begins.
251  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
252 
253  bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
254  bool UseTBAA = true) const;
255 
256 private:
257  bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
258  bool UseTBAA = true) const;
259 };
260 
261 } // end namespace llvm
262 
263 #endif // LLVM_CODEGEN_DFAPACKETIZER_H
std::vector< MachineInstr * > CurrentPacketMIs
virtual void initPacketizerState()
This class represents lattice values for constants.
Definition: AllocatorList.h:23
DFAInput getInsnInput(unsigned InsnClass)
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:179
void setTrackResources(bool Track)
virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ)
virtual bool ignorePseudoInstruction(const MachineInstr &I, const MachineBasicBlock *MBB)
DFAPacketizer(const InstrItineraryData *I, const DFAStateInput(*SIT)[2], const unsigned *SET, const unsigned(*RTT)[2]=nullptr, const unsigned *RTET=nullptr)
int64_t DFAStateInput
Definition: DFAPacketizer.h:72
std::map< MachineInstr *, SUnit * > MIToSUnit
A description of a memory reference used in the backend.
uint64_t DFAInput
Definition: DFAPacketizer.h:71
MachineFunction & MF
PowerPC VSX FMA Mutation
DFAPacketizer * ResourceTracker
virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI)
Itinerary data supplied by a subtarget to be used by a target.
TargetInstrInfo - Interface to description of machine instruction set.
const InstrItineraryData * getInstrItins() const
#define SET(n)
Definition: MD5.cpp:68
virtual bool shouldAddToPacket(const MachineInstr &MI)
virtual bool isSoloInstruction(const MachineInstr &MI)
const TargetInstrInfo * TII
bool canReserveResources(const MCInstrDesc *MID)
virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ)
Representation of each machine instruction.
Definition: MachineInstr.h:64
static cl::opt< bool > UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"))
#define I(x, y, z)
Definition: MD5.cpp:58
DFAPacketizer * getResourceTracker()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
unsigned getUsedResources(unsigned InstIdx)
DefaultVLIWScheduler * VLIWScheduler
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
void reserveResources(const MCInstrDesc *MID)