1 //=- llvm/CodeGen/DFAPacketizer.h - 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 #ifndef LLVM_CODEGEN_DFAPACKETIZER_H
27 #define LLVM_CODEGEN_DFAPACKETIZER_H
29 #include "llvm/CodeGen/MachineBasicBlock.h"
30 #include "llvm/ADT/DenseMap.h"
36 class MachineLoopInfo;
37 class MachineDominatorTree;
38 class InstrItineraryData;
39 class ScheduleDAGInstrs;
44 typedef std::pair<unsigned, unsigned> UnsignPair;
45 const InstrItineraryData *InstrItins;
47 const int (*DFAStateInputTable)[2];
48 const unsigned *DFAStateEntryTable;
50 // CachedTable is a map from <FromState, Input> to ToState.
51 DenseMap<UnsignPair, unsigned> CachedTable;
53 // ReadTable - Read the DFA transition table and update CachedTable.
54 void ReadTable(unsigned int state);
57 DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2],
60 // Reset the current state to make all resources available.
61 void clearResources() {
65 // canReserveResources - Check if the resources occupied by a MCInstrDesc
66 // are available in the current state.
67 bool canReserveResources(const llvm::MCInstrDesc *MID);
69 // reserveResources - Reserve the resources occupied by a MCInstrDesc and
70 // change the current state to reflect that change.
71 void reserveResources(const llvm::MCInstrDesc *MID);
73 // canReserveResources - Check if the resources occupied by a machine
74 // instruction are available in the current state.
75 bool canReserveResources(llvm::MachineInstr *MI);
77 // reserveResources - Reserve the resources occupied by a machine
78 // instruction and change the current state to reflect that change.
79 void reserveResources(llvm::MachineInstr *MI);
82 // VLIWPacketizerList - Implements a simple VLIW packetizer using DFA. The
83 // packetizer works on machine basic blocks. For each instruction I in BB, the
84 // packetizer consults the DFA to see if machine resources are available to
85 // execute I. If so, the packetizer checks if I depends on any instruction J in
86 // the current packet. If no dependency is found, I is added to current packet
87 // and machine resource is marked as taken. If any dependency is found, a target
88 // API call is made to prune the dependence.
89 class VLIWPacketizerList {
90 const TargetMachine &TM;
91 const MachineFunction &MF;
92 const TargetInstrInfo *TII;
94 // Encapsulate data types not exposed to the target interface.
95 ScheduleDAGInstrs *SchedulerImpl;
98 // Vector of instructions assigned to the current packet.
99 std::vector<MachineInstr*> CurrentPacketMIs;
100 // DFA resource tracker.
101 DFAPacketizer *ResourceTracker;
103 std::vector<SUnit> SUnits;
107 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT,
110 virtual ~VLIWPacketizerList();
112 // PacketizeMIs - Implement this API in the backend to bundle instructions.
113 void PacketizeMIs(MachineBasicBlock *MBB,
114 MachineBasicBlock::iterator BeginItr,
115 MachineBasicBlock::iterator EndItr);
117 // getResourceTracker - return ResourceTracker
118 DFAPacketizer *getResourceTracker() {return ResourceTracker;}
120 // addToPacket - Add MI to the current packet.
121 void addToPacket(MachineInstr *MI);
123 // endPacket - End the current packet.
124 void endPacket(MachineBasicBlock *MBB, MachineInstr *I);
126 // ignorePseudoInstruction - Ignore bundling of pseudo instructions.
127 bool ignorePseudoInstruction(MachineInstr *I, MachineBasicBlock *MBB);
129 // isSoloInstruction - return true if instruction I must end previous
131 bool isSoloInstruction(MachineInstr *I);
133 // isLegalToPacketizeTogether - Is it legal to packetize SUI and SUJ
135 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
139 // isLegalToPruneDependencies - Is it legal to prune dependece between SUI
141 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {