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 "llvm/Support/Automaton.h"
  32 #include <cstdint>
  33 #include <map>
  34 #include <memory>
  35 #include <utility>
  36 #include <vector>
  37
  38 namespace llvm {
  39
  40 class DefaultVLIWScheduler;
  41 class InstrItineraryData;
  42 class MachineFunction;
  43 class MachineInstr;
  44 class MachineLoopInfo;
  45 class MCInstrDesc;
  46 class SUnit;
  47 class TargetInstrInfo;
  48
  49 // --------------------------------------------------------------------
  50 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
  51
  52 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
  53 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
  54 //
  55 // e.g. terms x resource bit combinations that fit in uint32_t:
  56 //      4 terms x 8  bits = 32 bits
  57 //      3 terms x 10 bits = 30 bits
  58 //      2 terms x 16 bits = 32 bits
  59 //
  60 // e.g. terms x resource bit combinations that fit in uint64_t:
  61 //      8 terms x 8  bits = 64 bits
  62 //      7 terms x 9  bits = 63 bits
  63 //      6 terms x 10 bits = 60 bits
  64 //      5 terms x 12 bits = 60 bits
  65 //      4 terms x 16 bits = 64 bits <--- current
  66 //      3 terms x 21 bits = 63 bits
  67 //      2 terms x 32 bits = 64 bits
  68 //
  69 #define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
  70 #define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.
  71
  72 using DFAInput = uint64_t;
  73 using DFAStateInput = int64_t;
  74
  75 #define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
  76 // --------------------------------------------------------------------
  77
  78 class DFAPacketizer {
  79 private:
  80   const InstrItineraryData *InstrItins;
  81   Automaton<DFAInput> A;
  82
  83 public:
  84   DFAPacketizer(const InstrItineraryData *InstrItins, Automaton<uint64_t> a) :
  85       InstrItins(InstrItins), A(std::move(a)) {
  86     // Start off with resource tracking disabled.
  87     A.enableTranscription(false);
  88   }
  89
  90   // Reset the current state to make all resources available.
  91   void clearResources() {
  92     A.reset();
  93   }
  94
  95   // Set whether this packetizer should track not just whether instructions
  96   // can be packetized, but also which functional units each instruction ends up
  97   // using after packetization.
  98   void setTrackResources(bool Track) {
  99     A.enableTranscription(Track);
 100   }
 101
 102   // Return the DFAInput for an instruction class.
 103   DFAInput getInsnInput(unsigned InsnClass);
 104
 105   // Return the DFAInput for an instruction class input vector.
 106   static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);
 107
 108   // Check if the resources occupied by a MCInstrDesc are available in
 109   // the current state.
 110   bool canReserveResources(const MCInstrDesc *MID);
 111
 112   // Reserve the resources occupied by a MCInstrDesc and change the current
 113   // state to reflect that change.
 114   void reserveResources(const MCInstrDesc *MID);
 115
 116   // Check if the resources occupied by a machine instruction are available
 117   // in the current state.
 118   bool canReserveResources(MachineInstr &MI);
 119
 120   // Reserve the resources occupied by a machine instruction and change the
 121   // current state to reflect that change.
 122   void reserveResources(MachineInstr &MI);
 123
 124   // Return the resources used by the InstIdx'th instruction added to this
 125   // packet. The resources are returned as a bitvector of functional units.
 126   //
 127   // Note that a bundle may be packed in multiple valid ways. This function
 128   // returns one arbitary valid packing.
 129   //
 130   // Requires setTrackResources(true) to have been called.
 131   unsigned getUsedResources(unsigned InstIdx);
 132
 133   const InstrItineraryData *getInstrItins() const { return InstrItins; }
 134 };
 135
 136 // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
 137 // packetizer works on machine basic blocks. For each instruction I in BB,
 138 // the packetizer consults the DFA to see if machine resources are available
 139 // to execute I. If so, the packetizer checks if I depends on any instruction
 140 // in the current packet. If no dependency is found, I is added to current
 141 // packet and the machine resource is marked as taken. If any dependency is
 142 // found, a target API call is made to prune the dependence.
 143 class VLIWPacketizerList {
 144 protected:
 145   MachineFunction &MF;
 146   const TargetInstrInfo *TII;
 147   AAResults *AA;
 148
 149   // The VLIW Scheduler.
 150   DefaultVLIWScheduler *VLIWScheduler;
 151   // Vector of instructions assigned to the current packet.
 152   std::vector<MachineInstr*> CurrentPacketMIs;
 153   // DFA resource tracker.
 154   DFAPacketizer *ResourceTracker;
 155   // Map: MI -> SU.
 156   std::map<MachineInstr*, SUnit*> MIToSUnit;
 157
 158 public:
 159   // The AAResults parameter can be nullptr.
 160   VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
 161                      AAResults *AA);
 162
 163   virtual ~VLIWPacketizerList();
 164
 165   // Implement this API in the backend to bundle instructions.
 166   void PacketizeMIs(MachineBasicBlock *MBB,
 167                     MachineBasicBlock::iterator BeginItr,
 168                     MachineBasicBlock::iterator EndItr);
 169
 170   // Return the ResourceTracker.
 171   DFAPacketizer *getResourceTracker() {return ResourceTracker;}
 172
 173   // addToPacket - Add MI to the current packet.
 174   virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) {
 175     CurrentPacketMIs.push_back(&MI);
 176     ResourceTracker->reserveResources(MI);
 177     return MI;
 178   }
 179
 180   // End the current packet and reset the state of the packetizer.
 181   // Overriding this function allows the target-specific packetizer
 182   // to perform custom finalization.
 183   virtual void endPacket(MachineBasicBlock *MBB,
 184                          MachineBasicBlock::iterator MI);
 185
 186   // Perform initialization before packetizing an instruction. This
 187   // function is supposed to be overrided by the target dependent packetizer.
 188   virtual void initPacketizerState() {}
 189
 190   // Check if the given instruction I should be ignored by the packetizer.
 191   virtual bool ignorePseudoInstruction(const MachineInstr &I,
 192                                        const MachineBasicBlock *MBB) {
 193     return false;
 194   }
 195
 196   // Return true if instruction MI can not be packetized with any other
 197   // instruction, which means that MI itself is a packet.
 198   virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
 199
 200   // Check if the packetizer should try to add the given instruction to
 201   // the current packet. One reasons for which it may not be desirable
 202   // to include an instruction in the current packet could be that it
 203   // would cause a stall.
 204   // If this function returns "false", the current packet will be ended,
 205   // and the instruction will be added to the next packet.
 206   virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
 207
 208   // Check if it is legal to packetize SUI and SUJ together.
 209   virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
 210     return false;
 211   }
 212
 213   // Check if it is legal to prune dependece between SUI and SUJ.
 214   virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
 215     return false;
 216   }
 217
 218   // Add a DAG mutation to be done before the packetization begins.
 219   void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
 220
 221   bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
 222              bool UseTBAA = true) const;
 223
 224 private:
 225   bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
 226              bool UseTBAA = true) const;
 227 };
 228
 229 } // end namespace llvm
 230
 231 #endif // LLVM_CODEGEN_DFAPACKETIZER_H