contrib/llvm-project/llvm/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 class DFAPacketizer {
  50 private:
  51   const InstrItineraryData *InstrItins;
  52   Automaton<uint64_t> A;
  53   /// For every itinerary, an "action" to apply to the automaton. This removes
  54   /// the redundancy in actions between itinerary classes.
  55   ArrayRef<unsigned> ItinActions;
  56
  57 public:
  58   DFAPacketizer(const InstrItineraryData *InstrItins, Automaton<uint64_t> a,
  59                 ArrayRef<unsigned> ItinActions)
  60       : InstrItins(InstrItins), A(std::move(a)), ItinActions(ItinActions) {
  61     // Start off with resource tracking disabled.
  62     A.enableTranscription(false);
  63   }
  64
  65   // Reset the current state to make all resources available.
  66   void clearResources() {
  67     A.reset();
  68   }
  69
  70   // Set whether this packetizer should track not just whether instructions
  71   // can be packetized, but also which functional units each instruction ends up
  72   // using after packetization.
  73   void setTrackResources(bool Track) {
  74     A.enableTranscription(Track);
  75   }
  76
  77   // Check if the resources occupied by a MCInstrDesc are available in
  78   // the current state.
  79   bool canReserveResources(const MCInstrDesc *MID);
  80
  81   // Reserve the resources occupied by a MCInstrDesc and change the current
  82   // state to reflect that change.
  83   void reserveResources(const MCInstrDesc *MID);
  84
  85   // Check if the resources occupied by a machine instruction are available
  86   // in the current state.
  87   bool canReserveResources(MachineInstr &MI);
  88
  89   // Reserve the resources occupied by a machine instruction and change the
  90   // current state to reflect that change.
  91   void reserveResources(MachineInstr &MI);
  92
  93   // Return the resources used by the InstIdx'th instruction added to this
  94   // packet. The resources are returned as a bitvector of functional units.
  95   //
  96   // Note that a bundle may be packed in multiple valid ways. This function
  97   // returns one arbitary valid packing.
  98   //
  99   // Requires setTrackResources(true) to have been called.
 100   unsigned getUsedResources(unsigned InstIdx);
 101
 102   const InstrItineraryData *getInstrItins() const { return InstrItins; }
 103 };
 104
 105 // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
 106 // packetizer works on machine basic blocks. For each instruction I in BB,
 107 // the packetizer consults the DFA to see if machine resources are available
 108 // to execute I. If so, the packetizer checks if I depends on any instruction
 109 // in the current packet. If no dependency is found, I is added to current
 110 // packet and the machine resource is marked as taken. If any dependency is
 111 // found, a target API call is made to prune the dependence.
 112 class VLIWPacketizerList {
 113 protected:
 114   MachineFunction &MF;
 115   const TargetInstrInfo *TII;
 116   AAResults *AA;
 117
 118   // The VLIW Scheduler.
 119   DefaultVLIWScheduler *VLIWScheduler;
 120   // Vector of instructions assigned to the current packet.
 121   std::vector<MachineInstr*> CurrentPacketMIs;
 122   // DFA resource tracker.
 123   DFAPacketizer *ResourceTracker;
 124   // Map: MI -> SU.
 125   std::map<MachineInstr*, SUnit*> MIToSUnit;
 126
 127 public:
 128   // The AAResults parameter can be nullptr.
 129   VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
 130                      AAResults *AA);
 131
 132   virtual ~VLIWPacketizerList();
 133
 134   // Implement this API in the backend to bundle instructions.
 135   void PacketizeMIs(MachineBasicBlock *MBB,
 136                     MachineBasicBlock::iterator BeginItr,
 137                     MachineBasicBlock::iterator EndItr);
 138
 139   // Return the ResourceTracker.
 140   DFAPacketizer *getResourceTracker() {return ResourceTracker;}
 141
 142   // addToPacket - Add MI to the current packet.
 143   virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) {
 144     CurrentPacketMIs.push_back(&MI);
 145     ResourceTracker->reserveResources(MI);
 146     return MI;
 147   }
 148
 149   // End the current packet and reset the state of the packetizer.
 150   // Overriding this function allows the target-specific packetizer
 151   // to perform custom finalization.
 152   virtual void endPacket(MachineBasicBlock *MBB,
 153                          MachineBasicBlock::iterator MI);
 154
 155   // Perform initialization before packetizing an instruction. This
 156   // function is supposed to be overrided by the target dependent packetizer.
 157   virtual void initPacketizerState() {}
 158
 159   // Check if the given instruction I should be ignored by the packetizer.
 160   virtual bool ignorePseudoInstruction(const MachineInstr &I,
 161                                        const MachineBasicBlock *MBB) {
 162     return false;
 163   }
 164
 165   // Return true if instruction MI can not be packetized with any other
 166   // instruction, which means that MI itself is a packet.
 167   virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
 168
 169   // Check if the packetizer should try to add the given instruction to
 170   // the current packet. One reasons for which it may not be desirable
 171   // to include an instruction in the current packet could be that it
 172   // would cause a stall.
 173   // If this function returns "false", the current packet will be ended,
 174   // and the instruction will be added to the next packet.
 175   virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
 176
 177   // Check if it is legal to packetize SUI and SUJ together.
 178   virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
 179     return false;
 180   }
 181
 182   // Check if it is legal to prune dependece between SUI and SUJ.
 183   virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
 184     return false;
 185   }
 186
 187   // Add a DAG mutation to be done before the packetization begins.
 188   void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
 189
 190   bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
 191              bool UseTBAA = true) const;
 192
 193 private:
 194   bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
 195              bool UseTBAA = true) const;
 196 };
 197
 198 } // end namespace llvm
 199
 200 #endif // LLVM_CODEGEN_DFAPACKETIZER_H