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/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