include/llvm/CodeGen/DFAPacketizer.h

   1 //===- llvm/CodeGen/DFAPacketizer.h - DFA Packetizer for VLIW ---*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // This class implements a deterministic finite automaton (DFA) based
   9 // packetizing mechanism for VLIW architectures. It provides APIs to
  10 // determine whether there exists a legal mapping of instructions to
  11 // functional unit assignments in a packet. The DFA is auto-generated from
  12 // the target's Schedule.td file.
  13 //
  14 // A DFA consists of 3 major elements: states, inputs, and transitions. For
  15 // the packetizing mechanism, the input is the set of instruction classes for
  16 // a target. The state models all possible combinations of functional unit
  17 // consumption for a given set of instructions in a packet. A transition
  18 // models the addition of an instruction to a packet. In the DFA constructed
  19 // by this class, if an instruction can be added to a packet, then a valid
  20 // transition exists from the corresponding state. Invalid transitions
  21 // indicate that the instruction cannot be added to the current packet.
  22 //
  23 //===----------------------------------------------------------------------===//
  24
  25 #ifndef LLVM_CODEGEN_DFAPACKETIZER_H
  26 #define LLVM_CODEGEN_DFAPACKETIZER_H
  27
  28 #include "llvm/ADT/DenseMap.h"
  29 #include "llvm/CodeGen/MachineBasicBlock.h"
  30 #include "llvm/CodeGen/ScheduleDAGMutation.h"
  31 #include <cstdint>
  32 #include <map>
  33 #include <memory>
  34 #include <utility>
  35 #include <vector>
  36
  37 namespace llvm {
  38
  39 class DefaultVLIWScheduler;
  40 class InstrItineraryData;
  41 class MachineFunction;
  42 class MachineInstr;
  43 class MachineLoopInfo;
  44 class MCInstrDesc;
  45 class SUnit;
  46 class TargetInstrInfo;
  47
  48 // --------------------------------------------------------------------
  49 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
  50
  51 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
  52 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
  53 //
  54 // e.g. terms x resource bit combinations that fit in uint32_t:
  55 //      4 terms x 8  bits = 32 bits
  56 //      3 terms x 10 bits = 30 bits
  57 //      2 terms x 16 bits = 32 bits
  58 //
  59 // e.g. terms x resource bit combinations that fit in uint64_t:
  60 //      8 terms x 8  bits = 64 bits
  61 //      7 terms x 9  bits = 63 bits
  62 //      6 terms x 10 bits = 60 bits
  63 //      5 terms x 12 bits = 60 bits
  64 //      4 terms x 16 bits = 64 bits <--- current
  65 //      3 terms x 21 bits = 63 bits
  66 //      2 terms x 32 bits = 64 bits
  67 //
  68 #define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
  69 #define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.
  70
  71 using DFAInput = uint64_t;
  72 using DFAStateInput = int64_t;
  73
  74 #define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
  75 // --------------------------------------------------------------------
  76
  77 class DFAPacketizer {
  78 private:
  79   using UnsignPair = std::pair<unsigned, DFAInput>;
  80
  81   const InstrItineraryData *InstrItins;
  82   int CurrentState = 0;
  83   const DFAStateInput (*DFAStateInputTable)[2];
  84   const unsigned *DFAStateEntryTable;
  85   const unsigned (*DFAResourceTransitionTable)[2];
  86   const unsigned *DFAResourceTransitionEntryTable;
  87
  88   // CachedTable is a map from <FromState, Input> to ToState.
  89   DenseMap<UnsignPair, unsigned> CachedTable;
  90   // CachedResourceTransitions is a map from <FromState, Input> to a list of
  91   // resource transitions.
  92   DenseMap<UnsignPair, ArrayRef<unsigned[2]>>
  93       CachedResourceTransitions;
  94
  95   // Read the DFA transition table and update CachedTable.
  96   void ReadTable(unsigned state);
  97
  98   bool TrackResources = false;
  99   // State for the current packet. Every entry is a possible packing of the
 100   // bundle, indexed by cumulative resource state. Each entry is a list of the
 101   // cumulative resource states after packing each instruction. For example if
 102   // we pack I0: [0x4] and I1: [0x2] we will end up with:
 103   //   ResourceStates[0x6] = [0x4, 0x6]
 104   DenseMap<unsigned, SmallVector<unsigned, 8>> ResourceStates;
 105
 106 public:
 107   DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
 108                 const unsigned *SET,
 109                 const unsigned (*RTT)[2] = nullptr,
 110                 const unsigned *RTET = nullptr);
 111
 112   // Reset the current state to make all resources available.
 113   void clearResources() {
 114     CurrentState = 0;
 115     ResourceStates.clear();
 116     ResourceStates[0] = {};
 117   }
 118
 119   // Set whether this packetizer should track not just whether instructions
 120   // can be packetized, but also which functional units each instruction ends up
 121   // using after packetization.
 122   void setTrackResources(bool Track) {
 123     if (Track != TrackResources) {
 124       TrackResources = Track;
 125       if (Track) {
 126         CachedTable.clear();
 127         assert(DFAResourceTransitionEntryTable);
 128         assert(DFAResourceTransitionTable);
 129       }
 130     }
 131     assert(CurrentState == 0 && "Can only change TrackResources on an empty packetizer!");
 132   }
 133
 134   // Return the DFAInput for an instruction class.
 135   DFAInput getInsnInput(unsigned InsnClass);
 136
 137   // Return the DFAInput for an instruction class input vector.
 138   static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);
 139
 140   // Check if the resources occupied by a MCInstrDesc are available in
 141   // the current state.
 142   bool canReserveResources(const MCInstrDesc *MID);
 143
 144   // Reserve the resources occupied by a MCInstrDesc and change the current
 145   // state to reflect that change.
 146   void reserveResources(const MCInstrDesc *MID);
 147
 148   // Check if the resources occupied by a machine instruction are available
 149   // in the current state.
 150   bool canReserveResources(MachineInstr &MI);
 151
 152   // Reserve the resources occupied by a machine instruction and change the
 153   // current state to reflect that change.
 154   void reserveResources(MachineInstr &MI);
 155
 156   // Return the resources used by the InstIdx'th instruction added to this
 157   // packet. The resources are returned as a bitvector of functional units.
 158   //
 159   // Note that a bundle may be packed in multiple valid ways. This function
 160   // returns one arbitary valid packing.
 161   //
 162   // Requires setTrackResources(true) to have been called.
 163   unsigned getUsedResources(unsigned InstIdx);
 164
 165   const InstrItineraryData *getInstrItins() const { return InstrItins; }
 166 };
 167
 168 // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
 169 // packetizer works on machine basic blocks. For each instruction I in BB,
 170 // the packetizer consults the DFA to see if machine resources are available
 171 // to execute I. If so, the packetizer checks if I depends on any instruction
 172 // in the current packet. If no dependency is found, I is added to current
 173 // packet and the machine resource is marked as taken. If any dependency is
 174 // found, a target API call is made to prune the dependence.
 175 class VLIWPacketizerList {
 176 protected:
 177   MachineFunction &MF;
 178   const TargetInstrInfo *TII;
 179   AliasAnalysis *AA;
 180
 181   // The VLIW Scheduler.
 182   DefaultVLIWScheduler *VLIWScheduler;
 183   // Vector of instructions assigned to the current packet.
 184   std::vector<MachineInstr*> CurrentPacketMIs;
 185   // DFA resource tracker.
 186   DFAPacketizer *ResourceTracker;
 187   // Map: MI -> SU.
 188   std::map<MachineInstr*, SUnit*> MIToSUnit;
 189
 190 public:
 191   // The AliasAnalysis parameter can be nullptr.
 192   VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
 193                      AliasAnalysis *AA);
 194
 195   virtual ~VLIWPacketizerList();
 196
 197   // Implement this API in the backend to bundle instructions.
 198   void PacketizeMIs(MachineBasicBlock *MBB,
 199                     MachineBasicBlock::iterator BeginItr,
 200                     MachineBasicBlock::iterator EndItr);
 201
 202   // Return the ResourceTracker.
 203   DFAPacketizer *getResourceTracker() {return ResourceTracker;}
 204
 205   // addToPacket - Add MI to the current packet.
 206   virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) {
 207     CurrentPacketMIs.push_back(&MI);
 208     ResourceTracker->reserveResources(MI);
 209     return MI;
 210   }
 211
 212   // End the current packet and reset the state of the packetizer.
 213   // Overriding this function allows the target-specific packetizer
 214   // to perform custom finalization.
 215   virtual void endPacket(MachineBasicBlock *MBB,
 216                          MachineBasicBlock::iterator MI);
 217
 218   // Perform initialization before packetizing an instruction. This
 219   // function is supposed to be overrided by the target dependent packetizer.
 220   virtual void initPacketizerState() {}
 221
 222   // Check if the given instruction I should be ignored by the packetizer.
 223   virtual bool ignorePseudoInstruction(const MachineInstr &I,
 224                                        const MachineBasicBlock *MBB) {
 225     return false;
 226   }
 227
 228   // Return true if instruction MI can not be packetized with any other
 229   // instruction, which means that MI itself is a packet.
 230   virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
 231
 232   // Check if the packetizer should try to add the given instruction to
 233   // the current packet. One reasons for which it may not be desirable
 234   // to include an instruction in the current packet could be that it
 235   // would cause a stall.
 236   // If this function returns "false", the current packet will be ended,
 237   // and the instruction will be added to the next packet.
 238   virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
 239
 240   // Check if it is legal to packetize SUI and SUJ together.
 241   virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
 242     return false;
 243   }
 244
 245   // Check if it is legal to prune dependece between SUI and SUJ.
 246   virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
 247     return false;
 248   }
 249
 250   // Add a DAG mutation to be done before the packetization begins.
 251   void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
 252
 253   bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
 254              bool UseTBAA = true) const;
 255
 256 private:
 257   bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
 258              bool UseTBAA = true) const;
 259 };
 260
 261 } // end namespace llvm
 262
 263 #endif // LLVM_CODEGEN_DFAPACKETIZER_H