1 //=- llvm/CodeGen/DFAPacketizer.cpp - DFA Packetizer for VLIW -*- C++ -*-=====//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
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.
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.
24 //===----------------------------------------------------------------------===//
26 #include "llvm/CodeGen/DFAPacketizer.h"
27 #include "llvm/CodeGen/MachineInstr.h"
28 #include "llvm/CodeGen/MachineInstrBundle.h"
29 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
30 #include "llvm/MC/MCInstrItineraries.h"
31 #include "llvm/Target/TargetInstrInfo.h"
34 DFAPacketizer::DFAPacketizer(const InstrItineraryData
*I
, const int (*SIT
)[2],
36 InstrItins(I
), CurrentState(0), DFAStateInputTable(SIT
),
37 DFAStateEntryTable(SET
) {}
41 // ReadTable - Read the DFA transition table and update CachedTable.
43 // Format of the transition tables:
44 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
46 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable
49 void DFAPacketizer::ReadTable(unsigned int state
) {
50 unsigned ThisState
= DFAStateEntryTable
[state
];
51 unsigned NextStateInTable
= DFAStateEntryTable
[state
+1];
52 // Early exit in case CachedTable has already contains this
53 // state's transitions.
54 if (CachedTable
.count(UnsignPair(state
,
55 DFAStateInputTable
[ThisState
][0])))
58 for (unsigned i
= ThisState
; i
< NextStateInTable
; i
++)
59 CachedTable
[UnsignPair(state
, DFAStateInputTable
[i
][0])] =
60 DFAStateInputTable
[i
][1];
64 // canReserveResources - Check if the resources occupied by a MCInstrDesc
65 // are available in the current state.
66 bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc
*MID
) {
67 unsigned InsnClass
= MID
->getSchedClass();
68 const llvm::InstrStage
*IS
= InstrItins
->beginStage(InsnClass
);
69 unsigned FuncUnits
= IS
->getUnits();
70 UnsignPair StateTrans
= UnsignPair(CurrentState
, FuncUnits
);
71 ReadTable(CurrentState
);
72 return (CachedTable
.count(StateTrans
) != 0);
76 // reserveResources - Reserve the resources occupied by a MCInstrDesc and
77 // change the current state to reflect that change.
78 void DFAPacketizer::reserveResources(const llvm::MCInstrDesc
*MID
) {
79 unsigned InsnClass
= MID
->getSchedClass();
80 const llvm::InstrStage
*IS
= InstrItins
->beginStage(InsnClass
);
81 unsigned FuncUnits
= IS
->getUnits();
82 UnsignPair StateTrans
= UnsignPair(CurrentState
, FuncUnits
);
83 ReadTable(CurrentState
);
84 assert(CachedTable
.count(StateTrans
) != 0);
85 CurrentState
= CachedTable
[StateTrans
];
89 // canReserveResources - Check if the resources occupied by a machine
90 // instruction are available in the current state.
91 bool DFAPacketizer::canReserveResources(llvm::MachineInstr
*MI
) {
92 const llvm::MCInstrDesc
&MID
= MI
->getDesc();
93 return canReserveResources(&MID
);
96 // reserveResources - Reserve the resources occupied by a machine
97 // instruction and change the current state to reflect that change.
98 void DFAPacketizer::reserveResources(llvm::MachineInstr
*MI
) {
99 const llvm::MCInstrDesc
&MID
= MI
->getDesc();
100 reserveResources(&MID
);
104 // DefaultVLIWScheduler - This class extends ScheduleDAGInstrs and overrides
105 // Schedule method to build the dependence graph.
106 class DefaultVLIWScheduler
: public ScheduleDAGInstrs
{
108 DefaultVLIWScheduler(MachineFunction
&MF
, MachineLoopInfo
&MLI
);
109 // Schedule - Actual scheduling work.
110 void schedule() override
;
114 DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction
&MF
,
115 MachineLoopInfo
&MLI
)
116 : ScheduleDAGInstrs(MF
, &MLI
) {
117 CanHandleTerminators
= true;
120 void DefaultVLIWScheduler::schedule() {
121 // Build the scheduling graph.
122 buildSchedGraph(nullptr);
125 // VLIWPacketizerList Ctor
126 VLIWPacketizerList::VLIWPacketizerList(MachineFunction
&MF
,
127 MachineLoopInfo
&MLI
)
129 TII
= MF
.getSubtarget().getInstrInfo();
130 ResourceTracker
= TII
->CreateTargetScheduleState(MF
.getSubtarget());
131 VLIWScheduler
= new DefaultVLIWScheduler(MF
, MLI
);
134 // VLIWPacketizerList Dtor
135 VLIWPacketizerList::~VLIWPacketizerList() {
137 delete VLIWScheduler
;
140 delete ResourceTracker
;
143 // endPacket - End the current packet, bundle packet instructions and reset
145 void VLIWPacketizerList::endPacket(MachineBasicBlock
*MBB
,
147 if (CurrentPacketMIs
.size() > 1) {
148 MachineInstr
*MIFirst
= CurrentPacketMIs
.front();
149 finalizeBundle(*MBB
, MIFirst
->getIterator(), MI
->getIterator());
151 CurrentPacketMIs
.clear();
152 ResourceTracker
->clearResources();
155 // PacketizeMIs - Bundle machine instructions into packets.
156 void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock
*MBB
,
157 MachineBasicBlock::iterator BeginItr
,
158 MachineBasicBlock::iterator EndItr
) {
159 assert(VLIWScheduler
&& "VLIW Scheduler is not initialized!");
160 VLIWScheduler
->startBlock(MBB
);
161 VLIWScheduler
->enterRegion(MBB
, BeginItr
, EndItr
,
162 std::distance(BeginItr
, EndItr
));
163 VLIWScheduler
->schedule();
165 // Generate MI -> SU map.
167 for (unsigned i
= 0, e
= VLIWScheduler
->SUnits
.size(); i
!= e
; ++i
) {
168 SUnit
*SU
= &VLIWScheduler
->SUnits
[i
];
169 MIToSUnit
[SU
->getInstr()] = SU
;
172 // The main packetizer loop.
173 for (; BeginItr
!= EndItr
; ++BeginItr
) {
174 MachineInstr
*MI
= BeginItr
;
176 this->initPacketizerState();
178 // End the current packet if needed.
179 if (this->isSoloInstruction(MI
)) {
184 // Ignore pseudo instructions.
185 if (this->ignorePseudoInstruction(MI
, MBB
))
188 SUnit
*SUI
= MIToSUnit
[MI
];
189 assert(SUI
&& "Missing SUnit Info!");
191 // Ask DFA if machine resource is available for MI.
192 bool ResourceAvail
= ResourceTracker
->canReserveResources(MI
);
194 // Dependency check for MI with instructions in CurrentPacketMIs.
195 for (std::vector
<MachineInstr
*>::iterator VI
= CurrentPacketMIs
.begin(),
196 VE
= CurrentPacketMIs
.end(); VI
!= VE
; ++VI
) {
197 MachineInstr
*MJ
= *VI
;
198 SUnit
*SUJ
= MIToSUnit
[MJ
];
199 assert(SUJ
&& "Missing SUnit Info!");
201 // Is it legal to packetize SUI and SUJ together.
202 if (!this->isLegalToPacketizeTogether(SUI
, SUJ
)) {
203 // Allow packetization if dependency can be pruned.
204 if (!this->isLegalToPruneDependencies(SUI
, SUJ
)) {
205 // End the packet if dependency cannot be pruned.
208 } // !isLegalToPruneDependencies.
209 } // !isLegalToPacketizeTogether.
210 } // For all instructions in CurrentPacketMIs.
212 // End the packet if resource is not available.
216 // Add MI to the current packet.
217 BeginItr
= this->addToPacket(MI
);
218 } // For all instructions in BB.
220 // End any packet left behind.
221 endPacket(MBB
, EndItr
);
222 VLIWScheduler
->exitRegion();
223 VLIWScheduler
->finishBlock();