DFAPacketizer.cpp revision 360784 
1//=- llvm/CodeGen/DFAPacketizer.cpp - 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#include "llvm/CodeGen/DFAPacketizer.h"
26#include "llvm/ADT/StringExtras.h"
27#include "llvm/Analysis/AliasAnalysis.h"
28#include "llvm/CodeGen/MachineFunction.h"
29#include "llvm/CodeGen/MachineInstr.h"
30#include "llvm/CodeGen/MachineInstrBundle.h"
31#include "llvm/CodeGen/ScheduleDAG.h"
32#include "llvm/CodeGen/ScheduleDAGInstrs.h"
33#include "llvm/CodeGen/TargetInstrInfo.h"
34#include "llvm/CodeGen/TargetSubtargetInfo.h"
35#include "llvm/MC/MCInstrDesc.h"
36#include "llvm/MC/MCInstrItineraries.h"
37#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/raw_ostream.h"
40#include <algorithm>
41#include <cassert>
42#include <iterator>
43#include <memory>
44#include <vector>
45
46using namespace llvm;
47
48#define DEBUG_TYPE "packets"
49
50static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,
51  cl::init(0), cl::desc("If present, stops packetizing after N instructions"));
52
53static unsigned InstrCount = 0;
54
55// Check if the resources occupied by a MCInstrDesc are available in the
56// current state.
57bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) {
58  unsigned Action = ItinActions[MID->getSchedClass()];
59  if (MID->getSchedClass() == 0 || Action == 0)
60    return false;
61  return A.canAdd(Action);
62}
63
64// Reserve the resources occupied by a MCInstrDesc and change the current
65// state to reflect that change.
66void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {
67  unsigned Action = ItinActions[MID->getSchedClass()];
68  if (MID->getSchedClass() == 0 || Action == 0)
69    return;
70  A.add(Action);
71}
72
73// Check if the resources occupied by a machine instruction are available
74// in the current state.
75bool DFAPacketizer::canReserveResources(MachineInstr &MI) {
76  const MCInstrDesc &MID = MI.getDesc();
77  return canReserveResources(&MID);
78}
79
80// Reserve the resources occupied by a machine instruction and change the
81// current state to reflect that change.
82void DFAPacketizer::reserveResources(MachineInstr &MI) {
83  const MCInstrDesc &MID = MI.getDesc();
84  reserveResources(&MID);
85}
86
87unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) {
88  ArrayRef<NfaPath> NfaPaths = A.getNfaPaths();
89  assert(!NfaPaths.empty() && "Invalid bundle!");
90  const NfaPath &RS = NfaPaths.front();
91
92  // RS stores the cumulative resources used up to and including the I'th
93  // instruction. The 0th instruction is the base case.
94  if (InstIdx == 0)
95    return RS[0];
96  // Return the difference between the cumulative resources used by InstIdx and
97  // its predecessor.
98  return RS[InstIdx] ^ RS[InstIdx - 1];
99}
100
101namespace llvm {
102
103// This class extends ScheduleDAGInstrs and overrides the schedule method
104// to build the dependence graph.
105class DefaultVLIWScheduler : public ScheduleDAGInstrs {
106private:
107  AAResults *AA;
108  /// Ordered list of DAG postprocessing steps.
109  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
110
111public:
112  DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI,
113                       AAResults *AA);
114
115  // Actual scheduling work.
116  void schedule() override;
117
118  /// DefaultVLIWScheduler takes ownership of the Mutation object.
119  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
120    Mutations.push_back(std::move(Mutation));
121  }
122
123protected:
124  void postprocessDAG();
125};
126
127} // end namespace llvm
128
129DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF,
130                                           MachineLoopInfo &MLI,
131                                           AAResults *AA)
132    : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
133  CanHandleTerminators = true;
134}
135
136/// Apply each ScheduleDAGMutation step in order.
137void DefaultVLIWScheduler::postprocessDAG() {
138  for (auto &M : Mutations)
139    M->apply(this);
140}
141
142void DefaultVLIWScheduler::schedule() {
143  // Build the scheduling graph.
144  buildSchedGraph(AA);
145  postprocessDAG();
146}
147
148VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf,
149                                       MachineLoopInfo &mli, AAResults *aa)
150    : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
151  ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget());
152  ResourceTracker->setTrackResources(true);
153  VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA);
154}
155
156VLIWPacketizerList::~VLIWPacketizerList() {
157  delete VLIWScheduler;
158  delete ResourceTracker;
159}
160
161// End the current packet, bundle packet instructions and reset DFA state.
162void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,
163                                   MachineBasicBlock::iterator MI) {
164  LLVM_DEBUG({
165    if (!CurrentPacketMIs.empty()) {
166      dbgs() << "Finalizing packet:\n";
167      unsigned Idx = 0;
168      for (MachineInstr *MI : CurrentPacketMIs) {
169        unsigned R = ResourceTracker->getUsedResources(Idx++);
170        dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
171      }
172    }
173  });
174  if (CurrentPacketMIs.size() > 1) {
175    MachineInstr &MIFirst = *CurrentPacketMIs.front();
176    finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
177  }
178  CurrentPacketMIs.clear();
179  ResourceTracker->clearResources();
180  LLVM_DEBUG(dbgs() << "End packet\n");
181}
182
183// Bundle machine instructions into packets.
184void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,
185                                      MachineBasicBlock::iterator BeginItr,
186                                      MachineBasicBlock::iterator EndItr) {
187  assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
188  VLIWScheduler->startBlock(MBB);
189  VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
190                             std::distance(BeginItr, EndItr));
191  VLIWScheduler->schedule();
192
193  LLVM_DEBUG({
194    dbgs() << "Scheduling DAG of the packetize region\n";
195    VLIWScheduler->dump();
196  });
197
198  // Generate MI -> SU map.
199  MIToSUnit.clear();
200  for (SUnit &SU : VLIWScheduler->SUnits)
201    MIToSUnit[SU.getInstr()] = &SU;
202
203  bool LimitPresent = InstrLimit.getPosition();
204
205  // The main packetizer loop.
206  for (; BeginItr != EndItr; ++BeginItr) {
207    if (LimitPresent) {
208      if (InstrCount >= InstrLimit) {
209        EndItr = BeginItr;
210        break;
211      }
212      InstrCount++;
213    }
214    MachineInstr &MI = *BeginItr;
215    initPacketizerState();
216
217    // End the current packet if needed.
218    if (isSoloInstruction(MI)) {
219      endPacket(MBB, MI);
220      continue;
221    }
222
223    // Ignore pseudo instructions.
224    if (ignorePseudoInstruction(MI, MBB))
225      continue;
226
227    SUnit *SUI = MIToSUnit[&MI];
228    assert(SUI && "Missing SUnit Info!");
229
230    // Ask DFA if machine resource is available for MI.
231    LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);
232
233    bool ResourceAvail = ResourceTracker->canReserveResources(MI);
234    LLVM_DEBUG({
235      if (ResourceAvail)
236        dbgs() << "  Resources are available for adding MI to packet\n";
237      else
238        dbgs() << "  Resources NOT available\n";
239    });
240    if (ResourceAvail && shouldAddToPacket(MI)) {
241      // Dependency check for MI with instructions in CurrentPacketMIs.
242      for (auto MJ : CurrentPacketMIs) {
243        SUnit *SUJ = MIToSUnit[MJ];
244        assert(SUJ && "Missing SUnit Info!");
245
246        LLVM_DEBUG(dbgs() << "  Checking against MJ " << *MJ);
247        // Is it legal to packetize SUI and SUJ together.
248        if (!isLegalToPacketizeTogether(SUI, SUJ)) {
249          LLVM_DEBUG(dbgs() << "  Not legal to add MI, try to prune\n");
250          // Allow packetization if dependency can be pruned.
251          if (!isLegalToPruneDependencies(SUI, SUJ)) {
252            // End the packet if dependency cannot be pruned.
253            LLVM_DEBUG(dbgs()
254                       << "  Could not prune dependencies for adding MI\n");
255            endPacket(MBB, MI);
256            break;
257          }
258          LLVM_DEBUG(dbgs() << "  Pruned dependence for adding MI\n");
259        }
260      }
261    } else {
262      LLVM_DEBUG(if (ResourceAvail) dbgs()
263                 << "Resources are available, but instruction should not be "
264                    "added to packet\n  "
265                 << MI);
266      // End the packet if resource is not available, or if the instruction
267      // shoud not be added to the current packet.
268      endPacket(MBB, MI);
269    }
270
271    // Add MI to the current packet.
272    LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
273    BeginItr = addToPacket(MI);
274  } // For all instructions in the packetization range.
275
276  // End any packet left behind.
277  endPacket(MBB, EndItr);
278  VLIWScheduler->exitRegion();
279  VLIWScheduler->finishBlock();
280}
281
282bool VLIWPacketizerList::alias(const MachineMemOperand &Op1,
283                               const MachineMemOperand &Op2,
284                               bool UseTBAA) const {
285  if (!Op1.getValue() || !Op2.getValue())
286    return true;
287
288  int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
289  int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
290  int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;
291
292  AliasResult AAResult =
293      AA->alias(MemoryLocation(Op1.getValue(), Overlapa,
294                               UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
295                MemoryLocation(Op2.getValue(), Overlapb,
296                               UseTBAA ? Op2.getAAInfo() : AAMDNodes()));
297
298  return AAResult != NoAlias;
299}
300
301bool VLIWPacketizerList::alias(const MachineInstr &MI1,
302                               const MachineInstr &MI2,
303                               bool UseTBAA) const {
304  if (MI1.memoperands_empty() || MI2.memoperands_empty())
305    return true;
306
307  for (const MachineMemOperand *Op1 : MI1.memoperands())
308    for (const MachineMemOperand *Op2 : MI2.memoperands())
309      if (alias(*Op1, *Op2, UseTBAA))
310        return true;
311  return false;
312}
313
314// Add a DAG mutation object to the ordered list.
315void VLIWPacketizerList::addMutation(
316      std::unique_ptr<ScheduleDAGMutation> Mutation) {
317  VLIWScheduler->addMutation(std::move(Mutation));
318}
319