LLVM 19.0.0git
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
32#include <cstdint>
33#include <map>
34#include <memory>
35#include <utility>
36#include <vector>
37
38namespace llvm {
39
40class ScheduleDAGMutation;
41class InstrItineraryData;
42class MachineFunction;
43class MachineInstr;
44class MachineLoopInfo;
45class MCInstrDesc;
46class SUnit;
47class TargetInstrInfo;
48
49// This class extends ScheduleDAGInstrs and overrides the schedule method
50// to build the dependence graph.
52private:
53 AAResults *AA;
54 /// Ordered list of DAG postprocessing steps.
55 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
56
57public:
59 AAResults *AA);
60
61 // Actual scheduling work.
62 void schedule() override;
63
64 /// DefaultVLIWScheduler takes ownership of the Mutation object.
65 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
66 Mutations.push_back(std::move(Mutation));
67 }
68
69protected:
70 void postProcessDAG();
71};
72
74private:
75 const InstrItineraryData *InstrItins;
77 /// For every itinerary, an "action" to apply to the automaton. This removes
78 /// the redundancy in actions between itinerary classes.
79 ArrayRef<unsigned> ItinActions;
80
81public:
83 ArrayRef<unsigned> ItinActions)
84 : InstrItins(InstrItins), A(std::move(a)), ItinActions(ItinActions) {
85 // Start off with resource tracking disabled.
86 A.enableTranscription(false);
87 }
88
89 // Reset the current state to make all resources available.
91 A.reset();
92 }
93
94 // Set whether this packetizer should track not just whether instructions
95 // can be packetized, but also which functional units each instruction ends up
96 // using after packetization.
97 void setTrackResources(bool Track) {
98 A.enableTranscription(Track);
99 }
100
101 // Check if the resources occupied by a MCInstrDesc are available in
102 // the current state.
103 bool canReserveResources(const MCInstrDesc *MID);
104
105 // Reserve the resources occupied by a MCInstrDesc and change the current
106 // state to reflect that change.
107 void reserveResources(const MCInstrDesc *MID);
108
109 // Check if the resources occupied by a machine instruction are available
110 // in the current state.
112
113 // Reserve the resources occupied by a machine instruction and change the
114 // current state to reflect that change.
116
117 // Return the resources used by the InstIdx'th instruction added to this
118 // packet. The resources are returned as a bitvector of functional units.
119 //
120 // Note that a bundle may be packed in multiple valid ways. This function
121 // returns one arbitary valid packing.
122 //
123 // Requires setTrackResources(true) to have been called.
124 unsigned getUsedResources(unsigned InstIdx);
125
126 const InstrItineraryData *getInstrItins() const { return InstrItins; }
127};
128
129// VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
130// packetizer works on machine basic blocks. For each instruction I in BB,
131// the packetizer consults the DFA to see if machine resources are available
132// to execute I. If so, the packetizer checks if I depends on any instruction
133// in the current packet. If no dependency is found, I is added to current
134// packet and the machine resource is marked as taken. If any dependency is
135// found, a target API call is made to prune the dependence.
137protected:
141
142 // The VLIW Scheduler.
144 // Vector of instructions assigned to the current packet.
145 std::vector<MachineInstr*> CurrentPacketMIs;
146 // DFA resource tracker.
148 // Map: MI -> SU.
149 std::map<MachineInstr*, SUnit*> MIToSUnit;
150
151public:
152 // The AAResults parameter can be nullptr.
154 AAResults *AA);
157 virtual ~VLIWPacketizerList();
158
159 // Implement this API in the backend to bundle instructions.
163
164 // Return the ResourceTracker.
166
167 // addToPacket - Add MI to the current packet.
169 CurrentPacketMIs.push_back(&MI);
171 return MI;
172 }
173
174 // End the current packet and reset the state of the packetizer.
175 // Overriding this function allows the target-specific packetizer
176 // to perform custom finalization.
177 virtual void endPacket(MachineBasicBlock *MBB,
179
180 // Perform initialization before packetizing an instruction. This
181 // function is supposed to be overrided by the target dependent packetizer.
182 virtual void initPacketizerState() {}
183
184 // Check if the given instruction I should be ignored by the packetizer.
186 const MachineBasicBlock *MBB) {
187 return false;
188 }
189
190 // Return true if instruction MI can not be packetized with any other
191 // instruction, which means that MI itself is a packet.
192 virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
193
194 // Check if the packetizer should try to add the given instruction to
195 // the current packet. One reasons for which it may not be desirable
196 // to include an instruction in the current packet could be that it
197 // would cause a stall.
198 // If this function returns "false", the current packet will be ended,
199 // and the instruction will be added to the next packet.
200 virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
201
202 // Check if it is legal to packetize SUI and SUJ together.
203 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
204 return false;
205 }
206
207 // Check if it is legal to prune dependece between SUI and SUJ.
208 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
209 return false;
210 }
211
212 // Add a DAG mutation to be done before the packetization begins.
213 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
214
215 bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
216 bool UseTBAA = true) const;
217
218private:
219 bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
220 bool UseTBAA = true) const;
221};
222
223} // end namespace llvm
224
225#endif // LLVM_CODEGEN_DFAPACKETIZER_H
MachineBasicBlock & MBB
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
PowerPC VSX FMA Mutation
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"))
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A deterministic finite-state automaton.
Definition: Automaton.h:160
unsigned getUsedResources(unsigned InstIdx)
DFAPacketizer(const InstrItineraryData *InstrItins, Automaton< uint64_t > a, ArrayRef< unsigned > ItinActions)
Definition: DFAPacketizer.h:82
const InstrItineraryData * getInstrItins() const
bool canReserveResources(const MCInstrDesc *MID)
void reserveResources(const MCInstrDesc *MID)
void setTrackResources(bool Track)
Definition: DFAPacketizer.h:97
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
DefaultVLIWScheduler takes ownership of the Mutation object.
Definition: DFAPacketizer.h:65
void postProcessDAG()
Apply each ScheduleDAGMutation step in order.
void schedule() override
Orders nodes according to selected style.
Itinerary data supplied by a subtarget to be used by a target.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
Representation of each machine instruction.
Definition: MachineInstr.h:68
A description of a memory reference used in the backend.
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
A ScheduleDAG for scheduling lists of MachineInstr.
const MachineLoopInfo * MLI
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:559
TargetInstrInfo - Interface to description of machine instruction set.
MachineFunction & MF
virtual bool isSoloInstruction(const MachineInstr &MI)
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
VLIWPacketizerList(const VLIWPacketizerList &other)=delete
virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ)
const TargetInstrInfo * TII
bool alias(const MachineInstr &MI1, const MachineInstr &MI2, bool UseTBAA=true) const
std::vector< MachineInstr * > CurrentPacketMIs
std::map< MachineInstr *, SUnit * > MIToSUnit
VLIWPacketizerList & operator=(const VLIWPacketizerList &other)=delete
DefaultVLIWScheduler * VLIWScheduler
virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ)
DFAPacketizer * ResourceTracker
virtual void initPacketizerState()
virtual void endPacket(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI)
virtual bool ignorePseudoInstruction(const MachineInstr &I, const MachineBasicBlock *MBB)
DFAPacketizer * getResourceTracker()
void PacketizeMIs(MachineBasicBlock *MBB, MachineBasicBlock::iterator BeginItr, MachineBasicBlock::iterator EndItr)
virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI)
virtual bool shouldAddToPacket(const MachineInstr &MI)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1858
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858