aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm16/lib/CodeGen/DFAPacketizer.cpp
blob: 34fb1d286a5829433059be77ce970c3ab834838a (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
//=- llvm/CodeGen/DFAPacketizer.cpp - DFA Packetizer for VLIW -*- C++ -*-=====//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
// This class implements a deterministic finite automaton (DFA) based
// packetizing mechanism for VLIW architectures. It provides APIs to
// determine whether there exists a legal mapping of instructions to
// functional unit assignments in a packet. The DFA is auto-generated from
// the target's Schedule.td file.
//
// A DFA consists of 3 major elements: states, inputs, and transitions. For
// the packetizing mechanism, the input is the set of instruction classes for
// a target. The state models all possible combinations of functional unit
// consumption for a given set of instructions in a packet. A transition
// models the addition of an instruction to a packet. In the DFA constructed
// by this class, if an instruction can be added to a packet, then a valid
// transition exists from the corresponding state. Invalid transitions
// indicate that the instruction cannot be added to the current packet.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/DFAPacketizer.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBundle.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
#include "llvm/CodeGen/ScheduleDAGMutation.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <vector>

using namespace llvm;

#define DEBUG_TYPE "packets"

static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,
  cl::init(0), cl::desc("If present, stops packetizing after N instructions"));

static unsigned InstrCount = 0;

// Check if the resources occupied by a MCInstrDesc are available in the
// current state.
bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) {
  unsigned Action = ItinActions[MID->getSchedClass()];
  if (MID->getSchedClass() == 0 || Action == 0)
    return false;
  return A.canAdd(Action);
}

// Reserve the resources occupied by a MCInstrDesc and change the current
// state to reflect that change.
void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {
  unsigned Action = ItinActions[MID->getSchedClass()];
  if (MID->getSchedClass() == 0 || Action == 0)
    return;
  A.add(Action);
}

// Check if the resources occupied by a machine instruction are available
// in the current state.
bool DFAPacketizer::canReserveResources(MachineInstr &MI) {
  const MCInstrDesc &MID = MI.getDesc();
  return canReserveResources(&MID);
}

// Reserve the resources occupied by a machine instruction and change the
// current state to reflect that change.
void DFAPacketizer::reserveResources(MachineInstr &MI) {
  const MCInstrDesc &MID = MI.getDesc();
  reserveResources(&MID);
}

unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) {
  ArrayRef<NfaPath> NfaPaths = A.getNfaPaths();
  assert(!NfaPaths.empty() && "Invalid bundle!");
  const NfaPath &RS = NfaPaths.front();

  // RS stores the cumulative resources used up to and including the I'th
  // instruction. The 0th instruction is the base case.
  if (InstIdx == 0)
    return RS[0];
  // Return the difference between the cumulative resources used by InstIdx and
  // its predecessor.
  return RS[InstIdx] ^ RS[InstIdx - 1];
}

namespace llvm {

// This class extends ScheduleDAGInstrs and overrides the schedule method
// to build the dependence graph.
class DefaultVLIWScheduler : public ScheduleDAGInstrs {
private:
  AAResults *AA;
  /// Ordered list of DAG postprocessing steps.
  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;

public:
  DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI,
                       AAResults *AA);

  // Actual scheduling work.
  void schedule() override;

  /// DefaultVLIWScheduler takes ownership of the Mutation object.
  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
    Mutations.push_back(std::move(Mutation));
  }

protected:
  void postprocessDAG();
};

} // end namespace llvm

DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF,
                                           MachineLoopInfo &MLI,
                                           AAResults *AA)
    : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
  CanHandleTerminators = true;
}

/// Apply each ScheduleDAGMutation step in order.
void DefaultVLIWScheduler::postprocessDAG() {
  for (auto &M : Mutations)
    M->apply(this);
}

void DefaultVLIWScheduler::schedule() {
  // Build the scheduling graph.
  buildSchedGraph(AA);
  postprocessDAG();
}

VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf,
                                       MachineLoopInfo &mli, AAResults *aa)
    : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
  ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget());
  ResourceTracker->setTrackResources(true);
  VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA);
}

VLIWPacketizerList::~VLIWPacketizerList() {
  delete VLIWScheduler;
  delete ResourceTracker;
}

// End the current packet, bundle packet instructions and reset DFA state.
void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,
                                   MachineBasicBlock::iterator MI) {
  LLVM_DEBUG({
    if (!CurrentPacketMIs.empty()) {
      dbgs() << "Finalizing packet:\n";
      unsigned Idx = 0;
      for (MachineInstr *MI : CurrentPacketMIs) {
        unsigned R = ResourceTracker->getUsedResources(Idx++);
        dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
      }
    }
  });
  if (CurrentPacketMIs.size() > 1) {
    MachineInstr &MIFirst = *CurrentPacketMIs.front();
    finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
  }
  CurrentPacketMIs.clear();
  ResourceTracker->clearResources();
  LLVM_DEBUG(dbgs() << "End packet\n");
}

// Bundle machine instructions into packets.
void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,
                                      MachineBasicBlock::iterator BeginItr,
                                      MachineBasicBlock::iterator EndItr) {
  assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
  VLIWScheduler->startBlock(MBB);
  VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
                             std::distance(BeginItr, EndItr));
  VLIWScheduler->schedule();

  LLVM_DEBUG({
    dbgs() << "Scheduling DAG of the packetize region\n";
    VLIWScheduler->dump();
  });

  // Generate MI -> SU map.
  MIToSUnit.clear();
  for (SUnit &SU : VLIWScheduler->SUnits)
    MIToSUnit[SU.getInstr()] = &SU;

  bool LimitPresent = InstrLimit.getPosition();

  // The main packetizer loop.
  for (; BeginItr != EndItr; ++BeginItr) {
    if (LimitPresent) {
      if (InstrCount >= InstrLimit) {
        EndItr = BeginItr;
        break;
      }
      InstrCount++;
    }
    MachineInstr &MI = *BeginItr;
    initPacketizerState();

    // End the current packet if needed.
    if (isSoloInstruction(MI)) {
      endPacket(MBB, MI);
      continue;
    }

    // Ignore pseudo instructions.
    if (ignorePseudoInstruction(MI, MBB))
      continue;

    SUnit *SUI = MIToSUnit[&MI];
    assert(SUI && "Missing SUnit Info!");

    // Ask DFA if machine resource is available for MI.
    LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);

    bool ResourceAvail = ResourceTracker->canReserveResources(MI);
    LLVM_DEBUG({
      if (ResourceAvail)
        dbgs() << "  Resources are available for adding MI to packet\n";
      else
        dbgs() << "  Resources NOT available\n";
    });
    if (ResourceAvail && shouldAddToPacket(MI)) {
      // Dependency check for MI with instructions in CurrentPacketMIs.
      for (auto *MJ : CurrentPacketMIs) {
        SUnit *SUJ = MIToSUnit[MJ];
        assert(SUJ && "Missing SUnit Info!");

        LLVM_DEBUG(dbgs() << "  Checking against MJ " << *MJ);
        // Is it legal to packetize SUI and SUJ together.
        if (!isLegalToPacketizeTogether(SUI, SUJ)) {
          LLVM_DEBUG(dbgs() << "  Not legal to add MI, try to prune\n");
          // Allow packetization if dependency can be pruned.
          if (!isLegalToPruneDependencies(SUI, SUJ)) {
            // End the packet if dependency cannot be pruned.
            LLVM_DEBUG(dbgs()
                       << "  Could not prune dependencies for adding MI\n");
            endPacket(MBB, MI);
            break;
          }
          LLVM_DEBUG(dbgs() << "  Pruned dependence for adding MI\n");
        }
      }
    } else {
      LLVM_DEBUG(if (ResourceAvail) dbgs()
                 << "Resources are available, but instruction should not be "
                    "added to packet\n  "
                 << MI);
      // End the packet if resource is not available, or if the instruction
      // shoud not be added to the current packet.
      endPacket(MBB, MI);
    }

    // Add MI to the current packet.
    LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
    BeginItr = addToPacket(MI);
  } // For all instructions in the packetization range.

  // End any packet left behind.
  endPacket(MBB, EndItr);
  VLIWScheduler->exitRegion();
  VLIWScheduler->finishBlock();
}

bool VLIWPacketizerList::alias(const MachineMemOperand &Op1,
                               const MachineMemOperand &Op2,
                               bool UseTBAA) const {
  if (!Op1.getValue() || !Op2.getValue())
    return true;

  int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
  int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
  int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;

  AliasResult AAResult =
      AA->alias(MemoryLocation(Op1.getValue(), Overlapa,
                               UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
                MemoryLocation(Op2.getValue(), Overlapb,
                               UseTBAA ? Op2.getAAInfo() : AAMDNodes()));

  return AAResult != AliasResult::NoAlias;
}

bool VLIWPacketizerList::alias(const MachineInstr &MI1,
                               const MachineInstr &MI2,
                               bool UseTBAA) const {
  if (MI1.memoperands_empty() || MI2.memoperands_empty())
    return true;

  for (const MachineMemOperand *Op1 : MI1.memoperands())
    for (const MachineMemOperand *Op2 : MI2.memoperands())
      if (alias(*Op1, *Op2, UseTBAA))
        return true;
  return false;
}

// Add a DAG mutation object to the ordered list.
void VLIWPacketizerList::addMutation(
      std::unique_ptr<ScheduleDAGMutation> Mutation) {
  VLIWScheduler->addMutation(std::move(Mutation));
}