LLVM  13.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 
28 #include "llvm/ADT/DenseMap.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 
50 private:
51  const InstrItineraryData *InstrItins;
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:
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.
88 
89  // Reserve the resources occupied by a machine instruction and change the
90  // current state to reflect that change.
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.
113 protected:
117 
118  // The VLIW Scheduler.
120  // Vector of instructions assigned to the current packet.
121  std::vector<MachineInstr*> CurrentPacketMIs;
122  // DFA resource tracker.
124  // Map: MI -> SU.
125  std::map<MachineInstr*, SUnit*> MIToSUnit;
126 
127 public:
128  // The AAResults parameter can be nullptr.
130  AAResults *AA);
131 
132  virtual ~VLIWPacketizerList();
133 
134  // Implement this API in the backend to bundle instructions.
138 
139  // Return the ResourceTracker.
141 
142  // addToPacket - Add MI to the current packet.
144  CurrentPacketMIs.push_back(&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,
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.
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
llvm::VLIWPacketizerList::VLIWScheduler
DefaultVLIWScheduler * VLIWScheduler
Definition: DFAPacketizer.h:119
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
llvm
Definition: AllocatorList.h:23
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:160
llvm::VLIWPacketizerList::shouldAddToPacket
virtual bool shouldAddToPacket(const MachineInstr &MI)
Definition: DFAPacketizer.h:175
llvm::DFAPacketizer::canReserveResources
bool canReserveResources(const MCInstrDesc *MID)
Definition: DFAPacketizer.cpp:57
llvm::VLIWPacketizerList::getResourceTracker
DFAPacketizer * getResourceTracker()
Definition: DFAPacketizer.h:140
MachineBasicBlock.h
DenseMap.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:183
llvm::VLIWPacketizerList::VLIWPacketizerList
VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, AAResults *AA)
Definition: DFAPacketizer.cpp:148
llvm::VLIWPacketizerList::ResourceTracker
DFAPacketizer * ResourceTracker
Definition: DFAPacketizer.h:123
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
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:97
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::DFAPacketizer::getUsedResources
unsigned getUsedResources(unsigned InstIdx)
Definition: DFAPacketizer.cpp:87
llvm::DFAPacketizer
Definition: DFAPacketizer.h:49
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:195
llvm::VLIWPacketizerList::MF
MachineFunction & MF
Definition: DFAPacketizer.h:114
llvm::VLIWPacketizerList::addToPacket
virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI)
Definition: DFAPacketizer.h:143
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::VLIWPacketizerList
Definition: DFAPacketizer.h:112
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::VLIWPacketizerList::isSoloInstruction
virtual bool isSoloInstruction(const MachineInstr &MI)
Definition: DFAPacketizer.h:167
llvm::DFAPacketizer::setTrackResources
void setTrackResources(bool Track)
Definition: DFAPacketizer.h:73
llvm::VLIWPacketizerList::AA
AAResults * AA
Definition: DFAPacketizer.h:116
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::DFAPacketizer::getInstrItins
const InstrItineraryData * getInstrItins() const
Definition: DFAPacketizer.h:102
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:1540
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:66
llvm::MachineFunction
Definition: MachineFunction.h:230
ScheduleDAGMutation.h
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:391
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::DFAPacketizer::DFAPacketizer
DFAPacketizer(const InstrItineraryData *InstrItins, Automaton< uint64_t > a, ArrayRef< unsigned > ItinActions)
Definition: DFAPacketizer.h:58
std
Definition: BitVector.h:838
llvm::VLIWPacketizerList::MIToSUnit
std::map< MachineInstr *, SUnit * > MIToSUnit
Definition: DFAPacketizer.h:125
llvm::VLIWPacketizerList::initPacketizerState
virtual void initPacketizerState()
Definition: DFAPacketizer.h:157
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:115
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::VLIWPacketizerList::isLegalToPacketizeTogether
virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ)
Definition: DFAPacketizer.h:178
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:121