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