include/llvm/CodeGen/DFAPacketizer.h

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