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