llvm/lib/CodeGen/DFAPacketizer.cpp

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