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#include <map>
32
33namespace llvm {
34
35class MCInstrDesc;
36class MachineInstr;
37class MachineLoopInfo;
38class MachineDominatorTree;
39class InstrItineraryData;
40class DefaultVLIWScheduler;
41class SUnit;
42
43class DFAPacketizer {
44private:
45  typedef std::pair<unsigned, unsigned> UnsignPair;
46  const InstrItineraryData *InstrItins;
47  int CurrentState;
48  const int (*DFAStateInputTable)[2];
49  const unsigned *DFAStateEntryTable;
50
51  // CachedTable is a map from <FromState, Input> to ToState.
52  DenseMap<UnsignPair, unsigned> CachedTable;
53
54  // ReadTable - Read the DFA transition table and update CachedTable.
55  void ReadTable(unsigned int state);
56
57public:
58  DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2],
59                const unsigned *SET);
60
61  // Reset the current state to make all resources available.
62  void clearResources() {
63    CurrentState = 0;
64  }
65
66  // canReserveResources - Check if the resources occupied by a MCInstrDesc
67  // are available in the current state.
68  bool canReserveResources(const llvm::MCInstrDesc *MID);
69
70  // reserveResources - Reserve the resources occupied by a MCInstrDesc and
71  // change the current state to reflect that change.
72  void reserveResources(const llvm::MCInstrDesc *MID);
73
74  // canReserveResources - Check if the resources occupied by a machine
75  // instruction are available in the current state.
76  bool canReserveResources(llvm::MachineInstr *MI);
77
78  // reserveResources - Reserve the resources occupied by a machine
79  // instruction and change the current state to reflect that change.
80  void reserveResources(llvm::MachineInstr *MI);
81
82  const InstrItineraryData *getInstrItins() const { return InstrItins; }
83};
84
85// VLIWPacketizerList - Implements a simple VLIW packetizer using DFA. The
86// packetizer works on machine basic blocks. For each instruction I in BB, the
87// packetizer consults the DFA to see if machine resources are available to
88// execute I. If so, the packetizer checks if I depends on any instruction J in
89// the current packet. If no dependency is found, I is added to current packet
90// and machine resource is marked as taken. If any dependency is found, a target
91// API call is made to prune the dependence.
92class VLIWPacketizerList {
93protected:
94  const TargetMachine &TM;
95  const MachineFunction &MF;
96  const TargetInstrInfo *TII;
97
98  // The VLIW Scheduler.
99  DefaultVLIWScheduler *VLIWScheduler;
100
101  // Vector of instructions assigned to the current packet.
102  std::vector<MachineInstr*> CurrentPacketMIs;
103  // DFA resource tracker.
104  DFAPacketizer *ResourceTracker;
105
106  // Generate MI -> SU map.
107  std::map<MachineInstr*, SUnit*> MIToSUnit;
108
109public:
110  VLIWPacketizerList(
111    MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT,
112    bool IsPostRA);
113
114  virtual ~VLIWPacketizerList();
115
116  // PacketizeMIs - Implement this API in the backend to bundle instructions.
117  void PacketizeMIs(MachineBasicBlock *MBB,
118                    MachineBasicBlock::iterator BeginItr,
119                    MachineBasicBlock::iterator EndItr);
120
121  // getResourceTracker - return ResourceTracker
122  DFAPacketizer *getResourceTracker() {return ResourceTracker;}
123
124  // addToPacket - Add MI to the current packet.
125  virtual MachineBasicBlock::iterator addToPacket(MachineInstr *MI) {
126    MachineBasicBlock::iterator MII = MI;
127    CurrentPacketMIs.push_back(MI);
128    ResourceTracker->reserveResources(MI);
129    return MII;
130  }
131
132  // endPacket - End the current packet.
133  void endPacket(MachineBasicBlock *MBB, MachineInstr *MI);
134
135  // initPacketizerState - perform initialization before packetizing
136  // an instruction. This function is supposed to be overrided by
137  // the target dependent packetizer.
138  virtual void initPacketizerState(void) { return; }
139
140  // ignorePseudoInstruction - Ignore bundling of pseudo instructions.
141  virtual bool ignorePseudoInstruction(MachineInstr *I,
142                                       MachineBasicBlock *MBB) {
143    return false;
144  }
145
146  // isSoloInstruction - return true if instruction MI can not be packetized
147  // with any other instruction, which means that MI itself is a packet.
148  virtual bool isSoloInstruction(MachineInstr *MI) {
149    return true;
150  }
151
152  // isLegalToPacketizeTogether - Is it legal to packetize SUI and SUJ
153  // together.
154  virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
155    return false;
156  }
157
158  // isLegalToPruneDependencies - Is it legal to prune dependece between SUI
159  // and SUJ.
160  virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
161    return false;
162  }
163
164};
165}
166
167#endif
168