LLVM 17.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
30#include <cstdint>
31#include <map>
32#include <memory>
33#include <utility>
34#include <vector>
35
36namespace llvm {
37
38class DefaultVLIWScheduler;
39class ScheduleDAGMutation;
40class InstrItineraryData;
41class MachineFunction;
42class MachineInstr;
43class MachineLoopInfo;
44class MCInstrDesc;
45class SUnit;
46class TargetInstrInfo;
47
49private:
50 const InstrItineraryData *InstrItins;
52 /// For every itinerary, an "action" to apply to the automaton. This removes
53 /// the redundancy in actions between itinerary classes.
54 ArrayRef<unsigned> ItinActions;
55
56public:
58 ArrayRef<unsigned> ItinActions)
59 : InstrItins(InstrItins), A(std::move(a)), ItinActions(ItinActions) {
60 // Start off with resource tracking disabled.
61 A.enableTranscription(false);
62 }
63
64 // Reset the current state to make all resources available.
66 A.reset();
67 }
68
69 // Set whether this packetizer should track not just whether instructions
70 // can be packetized, but also which functional units each instruction ends up
71 // using after packetization.
72 void setTrackResources(bool Track) {
73 A.enableTranscription(Track);
74 }
75
76 // Check if the resources occupied by a MCInstrDesc are available in
77 // the current state.
78 bool canReserveResources(const MCInstrDesc *MID);
79
80 // Reserve the resources occupied by a MCInstrDesc and change the current
81 // state to reflect that change.
82 void reserveResources(const MCInstrDesc *MID);
83
84 // Check if the resources occupied by a machine instruction are available
85 // in the current state.
87
88 // Reserve the resources occupied by a machine instruction and change the
89 // current state to reflect that change.
91
92 // Return the resources used by the InstIdx'th instruction added to this
93 // packet. The resources are returned as a bitvector of functional units.
94 //
95 // Note that a bundle may be packed in multiple valid ways. This function
96 // returns one arbitary valid packing.
97 //
98 // Requires setTrackResources(true) to have been called.
99 unsigned getUsedResources(unsigned InstIdx);
100
101 const InstrItineraryData *getInstrItins() const { return InstrItins; }
102};
103
104// VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
105// packetizer works on machine basic blocks. For each instruction I in BB,
106// the packetizer consults the DFA to see if machine resources are available
107// to execute I. If so, the packetizer checks if I depends on any instruction
108// in the current packet. If no dependency is found, I is added to current
109// packet and the machine resource is marked as taken. If any dependency is
110// found, a target API call is made to prune the dependence.
112protected:
116
117 // The VLIW Scheduler.
119 // Vector of instructions assigned to the current packet.
120 std::vector<MachineInstr*> CurrentPacketMIs;
121 // DFA resource tracker.
123 // Map: MI -> SU.
124 std::map<MachineInstr*, SUnit*> MIToSUnit;
125
126public:
127 // The AAResults parameter can be nullptr.
129 AAResults *AA);
130
131 virtual ~VLIWPacketizerList();
132
133 // Implement this API in the backend to bundle instructions.
137
138 // Return the ResourceTracker.
140
141 // addToPacket - Add MI to the current packet.
143 CurrentPacketMIs.push_back(&MI);
145 return MI;
146 }
147
148 // End the current packet and reset the state of the packetizer.
149 // Overriding this function allows the target-specific packetizer
150 // to perform custom finalization.
151 virtual void endPacket(MachineBasicBlock *MBB,
153
154 // Perform initialization before packetizing an instruction. This
155 // function is supposed to be overrided by the target dependent packetizer.
156 virtual void initPacketizerState() {}
157
158 // Check if the given instruction I should be ignored by the packetizer.
160 const MachineBasicBlock *MBB) {
161 return false;
162 }
163
164 // Return true if instruction MI can not be packetized with any other
165 // instruction, which means that MI itself is a packet.
166 virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
167
168 // Check if the packetizer should try to add the given instruction to
169 // the current packet. One reasons for which it may not be desirable
170 // to include an instruction in the current packet could be that it
171 // would cause a stall.
172 // If this function returns "false", the current packet will be ended,
173 // and the instruction will be added to the next packet.
174 virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
175
176 // Check if it is legal to packetize SUI and SUJ together.
177 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
178 return false;
179 }
180
181 // Check if it is legal to prune dependece between SUI and SUJ.
182 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
183 return false;
184 }
185
186 // Add a DAG mutation to be done before the packetization begins.
187 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
188
189 bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
190 bool UseTBAA = true) const;
191
192private:
193 bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
194 bool UseTBAA = true) const;
195};
196
197} // end namespace llvm
198
199#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:162
unsigned getUsedResources(unsigned InstIdx)
DFAPacketizer(const InstrItineraryData *InstrItins, Automaton< uint64_t > a, ArrayRef< unsigned > ItinActions)
Definition: DFAPacketizer.h:57
const InstrItineraryData * getInstrItins() const
bool canReserveResources(const MCInstrDesc *MID)
void reserveResources(const MCInstrDesc *MID)
void setTrackResources(bool Track)
Definition: DFAPacketizer.h:72
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
TargetInstrInfo - Interface to description of machine instruction set.
MachineFunction & MF
virtual bool isSoloInstruction(const MachineInstr &MI)
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
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
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:1862
Definition: BitVector.h:851