LLVM  16.0.0git
DFAPacketizer.h
Go to the documentation of this file.
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 
29 #include "llvm/Support/Automaton.h"
30 #include <cstdint>
31 #include <map>
32 #include <memory>
33 #include <utility>
34 #include <vector>
35 
36 namespace llvm {
37 
38 class DefaultVLIWScheduler;
39 class ScheduleDAGMutation;
40 class InstrItineraryData;
41 class MachineFunction;
42 class MachineInstr;
43 class MachineLoopInfo;
44 class MCInstrDesc;
45 class SUnit;
46 class TargetInstrInfo;
47 
49 private:
50  const InstrItineraryData *InstrItins;
52  /// For every itinerary, an "action" to apply to the automaton. This removes
53  /// the redundancy in actions between itinerary classes.
54  ArrayRef<unsigned> ItinActions;
55 
56 public:
58  ArrayRef<unsigned> ItinActions)
59  : InstrItins(InstrItins), A(std::move(a)), ItinActions(ItinActions) {
60  // Start off with resource tracking disabled.
61  A.enableTranscription(false);
62  }
63 
64  // Reset the current state to make all resources available.
65  void clearResources() {
66  A.reset();
67  }
68 
69  // Set whether this packetizer should track not just whether instructions
70  // can be packetized, but also which functional units each instruction ends up
71  // using after packetization.
72  void setTrackResources(bool Track) {
73  A.enableTranscription(Track);
74  }
75 
76  // Check if the resources occupied by a MCInstrDesc are available in
77  // the current state.
78  bool canReserveResources(const MCInstrDesc *MID);
79 
80  // Reserve the resources occupied by a MCInstrDesc and change the current
81  // state to reflect that change.
82  void reserveResources(const MCInstrDesc *MID);
83 
84  // Check if the resources occupied by a machine instruction are available
85  // in the current state.
87 
88  // Reserve the resources occupied by a machine instruction and change the
89  // current state to reflect that change.
91 
92  // Return the resources used by the InstIdx'th instruction added to this
93  // packet. The resources are returned as a bitvector of functional units.
94  //
95  // Note that a bundle may be packed in multiple valid ways. This function
96  // returns one arbitary valid packing.
97  //
98  // Requires setTrackResources(true) to have been called.
99  unsigned getUsedResources(unsigned InstIdx);
100 
101  const InstrItineraryData *getInstrItins() const { return InstrItins; }
102 };
103 
104 // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
105 // packetizer works on machine basic blocks. For each instruction I in BB,
106 // the packetizer consults the DFA to see if machine resources are available
107 // to execute I. If so, the packetizer checks if I depends on any instruction
108 // in the current packet. If no dependency is found, I is added to current
109 // packet and the machine resource is marked as taken. If any dependency is
110 // found, a target API call is made to prune the dependence.
112 protected:
116 
117  // The VLIW Scheduler.
119  // Vector of instructions assigned to the current packet.
120  std::vector<MachineInstr*> CurrentPacketMIs;
121  // DFA resource tracker.
123  // Map: MI -> SU.
124  std::map<MachineInstr*, SUnit*> MIToSUnit;
125 
126 public:
127  // The AAResults parameter can be nullptr.
129  AAResults *AA);
130 
131  virtual ~VLIWPacketizerList();
132 
133  // Implement this API in the backend to bundle instructions.
137 
138  // Return the ResourceTracker.
140 
141  // addToPacket - Add MI to the current packet.
143  CurrentPacketMIs.push_back(&MI);
145  return MI;
146  }
147 
148  // End the current packet and reset the state of the packetizer.
149  // Overriding this function allows the target-specific packetizer
150  // to perform custom finalization.
151  virtual void endPacket(MachineBasicBlock *MBB,
153 
154  // Perform initialization before packetizing an instruction. This
155  // function is supposed to be overrided by the target dependent packetizer.
156  virtual void initPacketizerState() {}
157 
158  // Check if the given instruction I should be ignored by the packetizer.
160  const MachineBasicBlock *MBB) {
161  return false;
162  }
163 
164  // Return true if instruction MI can not be packetized with any other
165  // instruction, which means that MI itself is a packet.
166  virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
167 
168  // Check if the packetizer should try to add the given instruction to
169  // the current packet. One reasons for which it may not be desirable
170  // to include an instruction in the current packet could be that it
171  // would cause a stall.
172  // If this function returns "false", the current packet will be ended,
173  // and the instruction will be added to the next packet.
174  virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
175 
176  // Check if it is legal to packetize SUI and SUJ together.
177  virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
178  return false;
179  }
180 
181  // Check if it is legal to prune dependece between SUI and SUJ.
182  virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
183  return false;
184  }
185 
186  // Add a DAG mutation to be done before the packetization begins.
187  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
188 
189  bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
190  bool UseTBAA = true) const;
191 
192 private:
193  bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
194  bool UseTBAA = true) const;
195 };
196 
197 } // end namespace llvm
198 
199 #endif // LLVM_CODEGEN_DFAPACKETIZER_H
llvm::VLIWPacketizerList::VLIWScheduler
DefaultVLIWScheduler * VLIWScheduler
Definition: DFAPacketizer.h:118
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::VLIWPacketizerList::addMutation
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
Definition: DFAPacketizer.cpp:315
llvm::VLIWPacketizerList::alias
bool alias(const MachineInstr &MI1, const MachineInstr &MI2, bool UseTBAA=true) const
Definition: DFAPacketizer.cpp:301
llvm::VLIWPacketizerList::ignorePseudoInstruction
virtual bool ignorePseudoInstruction(const MachineInstr &I, const MachineBasicBlock *MBB)
Definition: DFAPacketizer.h:159
llvm::VLIWPacketizerList::shouldAddToPacket
virtual bool shouldAddToPacket(const MachineInstr &MI)
Definition: DFAPacketizer.h:174
llvm::DFAPacketizer::canReserveResources
bool canReserveResources(const MCInstrDesc *MID)
Definition: DFAPacketizer.cpp:57
llvm::VLIWPacketizerList::getResourceTracker
DFAPacketizer * getResourceTracker()
Definition: DFAPacketizer.h:139
MachineBasicBlock.h
llvm::MachineMemOperand
A description of a memory reference used in the backend.
Definition: MachineMemOperand.h:127
llvm::VLIWPacketizerList::endPacket
virtual void endPacket(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI)
Definition: DFAPacketizer.cpp:162
llvm::VLIWPacketizerList::isLegalToPruneDependencies
virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ)
Definition: DFAPacketizer.h:182
llvm::VLIWPacketizerList::VLIWPacketizerList
VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, AAResults *AA)
Definition: DFAPacketizer.cpp:148
llvm::VLIWPacketizerList::ResourceTracker
DFAPacketizer * ResourceTracker
Definition: DFAPacketizer.h:122
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
Automaton.h
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::AAResults
Definition: AliasAnalysis.h:518
llvm::DFAPacketizer::getUsedResources
unsigned getUsedResources(unsigned InstIdx)
Definition: DFAPacketizer.cpp:87
llvm::DFAPacketizer
Definition: DFAPacketizer.h:48
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
llvm::VLIWPacketizerList::MF
MachineFunction & MF
Definition: DFAPacketizer.h:113
llvm::VLIWPacketizerList::addToPacket
virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI)
Definition: DFAPacketizer.h:142
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::VLIWPacketizerList
Definition: DFAPacketizer.h:111
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::VLIWPacketizerList::isSoloInstruction
virtual bool isSoloInstruction(const MachineInstr &MI)
Definition: DFAPacketizer.h:166
llvm::DFAPacketizer::setTrackResources
void setTrackResources(bool Track)
Definition: DFAPacketizer.h:72
llvm::VLIWPacketizerList::AA
AAResults * AA
Definition: DFAPacketizer.h:115
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::DFAPacketizer::getInstrItins
const InstrItineraryData * getInstrItins() const
Definition: DFAPacketizer.h:101
llvm::VLIWPacketizerList::~VLIWPacketizerList
virtual ~VLIWPacketizerList()
Definition: DFAPacketizer.cpp:156
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1666
UseTBAA
static cl::opt< bool > UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"))
llvm::DFAPacketizer::clearResources
void clearResources()
Definition: DFAPacketizer.h:65
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::ArrayRef< unsigned >
llvm::VLIWPacketizerList::PacketizeMIs
void PacketizeMIs(MachineBasicBlock *MBB, MachineBasicBlock::iterator BeginItr, MachineBasicBlock::iterator EndItr)
Definition: DFAPacketizer.cpp:184
Mutation
PowerPC VSX FMA Mutation
Definition: PPCVSXFMAMutate.cpp:387
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::DFAPacketizer::DFAPacketizer
DFAPacketizer(const InstrItineraryData *InstrItins, Automaton< uint64_t > a, ArrayRef< unsigned > ItinActions)
Definition: DFAPacketizer.h:57
std
Definition: BitVector.h:851
AA
llvm::VLIWPacketizerList::MIToSUnit
std::map< MachineInstr *, SUnit * > MIToSUnit
Definition: DFAPacketizer.h:124
llvm::VLIWPacketizerList::initPacketizerState
virtual void initPacketizerState()
Definition: DFAPacketizer.h:156
llvm::DefaultVLIWScheduler
Definition: DFAPacketizer.cpp:105
llvm::Automaton< uint64_t >
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
llvm::VLIWPacketizerList::TII
const TargetInstrInfo * TII
Definition: DFAPacketizer.h:114
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::VLIWPacketizerList::isLegalToPacketizeTogether
virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ)
Definition: DFAPacketizer.h:177
llvm::DFAPacketizer::reserveResources
void reserveResources(const MCInstrDesc *MID)
Definition: DFAPacketizer.cpp:66
llvm::InstrItineraryData
Itinerary data supplied by a subtarget to be used by a target.
Definition: MCInstrItineraries.h:109
llvm::VLIWPacketizerList::CurrentPacketMIs
std::vector< MachineInstr * > CurrentPacketMIs
Definition: DFAPacketizer.h:120