1 //=- llvm/CodeGen/DFAPacketizer.h - DFA Packetizer for VLIW ---*- C++ -*-=====//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
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.
14 //
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.
23 //
24 //===----------------------------------------------------------------------===//
25 
26 #ifndef LLVM_CODEGEN_DFAPACKETIZER_H
27 #define LLVM_CODEGEN_DFAPACKETIZER_H
28 
29 #include "llvm/CodeGen/MachineBasicBlock.h"
30 #include "llvm/ADT/DenseMap.h"
31 
32 namespace llvm {
33 
34 class MCInstrDesc;
35 class MachineInstr;
36 class MachineLoopInfo;
37 class MachineDominatorTree;
38 class InstrItineraryData;
39 class SUnit;
40 
41 class DFAPacketizer {
42 private:
43   typedef std::pair<unsigned, unsigned> UnsignPair;
44   const InstrItineraryData *InstrItins;
45   int CurrentState;
46   const int (*DFAStateInputTable)[2];
47   const unsigned *DFAStateEntryTable;
48 
49   // CachedTable is a map from <FromState, Input> to ToState.
50   DenseMap<UnsignPair, unsigned> CachedTable;
51 
52   // ReadTable - Read the DFA transition table and update CachedTable.
53   void ReadTable(unsigned int state);
54 
55 public:
56   DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2],
57                 const unsigned *SET);
58 
59   // Reset the current state to make all resources available.
60   void clearResources() {
61     CurrentState = 0;
62   }
63 
64   // canReserveResources - Check if the resources occupied by a MCInstrDesc
65   // are available in the current state.
66   bool canReserveResources(const llvm::MCInstrDesc *MID);
67 
68   // reserveResources - Reserve the resources occupied by a MCInstrDesc and
69   // change the current state to reflect that change.
70   void reserveResources(const llvm::MCInstrDesc *MID);
71 
72   // canReserveResources - Check if the resources occupied by a machine
73   // instruction are available in the current state.
74   bool canReserveResources(llvm::MachineInstr *MI);
75 
76   // reserveResources - Reserve the resources occupied by a machine
77   // instruction and change the current state to reflect that change.
78   void reserveResources(llvm::MachineInstr *MI);
79 };
80 
81 // VLIWPacketizerList - Implements a simple VLIW packetizer using DFA. The
82 // packetizer works on machine basic blocks. For each instruction I in BB, the
83 // packetizer consults the DFA to see if machine resources are available to
84 // execute I. If so, the packetizer checks if I depends on any instruction J in
85 // the current packet. If no dependency is found, I is added to current packet
86 // and machine resource is marked as taken. If any dependency is found, a target
87 // API call is made to prune the dependence.
88 class VLIWPacketizerList {
89   const TargetMachine &TM;
90   const MachineFunction &MF;
91   const TargetInstrInfo *TII;
92 
93   // Encapsulate data types not exposed to the target interface.
94   void *SchedulerImpl;
95 
96 protected:
97   // Vector of instructions assigned to the current packet.
98   std::vector<MachineInstr*> CurrentPacketMIs;
99   // DFA resource tracker.
100   DFAPacketizer *ResourceTracker;
101   // Scheduling units.
102   std::vector<SUnit> SUnits;
103 
104 public:
105   VLIWPacketizerList(
106     MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT,
107     bool IsPostRA);
108 
109   virtual ~VLIWPacketizerList();
110 
111   // PacketizeMIs - Implement this API in the backend to bundle instructions.
112   void PacketizeMIs(MachineBasicBlock *MBB,
113                     MachineBasicBlock::iterator BeginItr,
114                     MachineBasicBlock::iterator EndItr);
115 
116   // getResourceTracker - return ResourceTracker
117   DFAPacketizer *getResourceTracker() {return ResourceTracker;}
118 
119   // addToPacket - Add MI to the current packet.
120   void addToPacket(MachineInstr *MI);
121 
122   // endPacket - End the current packet.
123   void endPacket(MachineBasicBlock *MBB, MachineInstr *I);
124 
125   // ignorePseudoInstruction - Ignore bundling of pseudo instructions.
126   bool ignorePseudoInstruction(MachineInstr *I, MachineBasicBlock *MBB);
127 
128   // isSoloInstruction - return true if instruction I must end previous
129   // packet.
130   bool isSoloInstruction(MachineInstr *I);
131 
132   // isLegalToPacketizeTogether - Is it legal to packetize SUI and SUJ
133   // together.
134   virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
135     return false;
136   }
137 
138   // isLegalToPruneDependencies - Is it legal to prune dependece between SUI
139   // and SUJ.
140   virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
141     return false;
142   }
143 };
144 }
145 
146 #endif
147