289 lines · 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-exception6//7//===----------------------------------------------------------------------===//8// This class implements a deterministic finite automaton (DFA) based9// packetizing mechanism for VLIW architectures. It provides APIs to10// determine whether there exists a legal mapping of instructions to11// functional unit assignments in a packet. The DFA is auto-generated from12// the target's Schedule.td file.13//14// A DFA consists of 3 major elements: states, inputs, and transitions. For15// the packetizing mechanism, the input is the set of instruction classes for16// a target. The state models all possible combinations of functional unit17// consumption for a given set of instructions in a packet. A transition18// models the addition of an instruction to a packet. In the DFA constructed19// by this class, if an instruction can be added to a packet, then a valid20// transition exists from the corresponding state. Invalid transitions21// 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 43using namespace llvm;44 45#define DEBUG_TYPE "packets"46 47static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,48 cl::init(0), cl::desc("If present, stops packetizing after N instructions"));49 50static unsigned InstrCount = 0;51 52// Check if the resources occupied by a MCInstrDesc are available in the53// current state.54bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) {55 unsigned Action = ItinActions[MID->getSchedClass()];56 if (MID->getSchedClass() == 0 || Action == 0)57 return false;58 return A.canAdd(Action);59}60 61// Reserve the resources occupied by a MCInstrDesc and change the current62// state to reflect that change.63void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {64 unsigned Action = ItinActions[MID->getSchedClass()];65 if (MID->getSchedClass() == 0 || Action == 0)66 return;67 A.add(Action);68}69 70// Check if the resources occupied by a machine instruction are available71// in the current state.72bool DFAPacketizer::canReserveResources(MachineInstr &MI) {73 const MCInstrDesc &MID = MI.getDesc();74 return canReserveResources(&MID);75}76 77// Reserve the resources occupied by a machine instruction and change the78// current state to reflect that change.79void DFAPacketizer::reserveResources(MachineInstr &MI) {80 const MCInstrDesc &MID = MI.getDesc();81 reserveResources(&MID);82}83 84unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) {85 ArrayRef<NfaPath> NfaPaths = A.getNfaPaths();86 assert(!NfaPaths.empty() && "Invalid bundle!");87 const NfaPath &RS = NfaPaths.front();88 89 // RS stores the cumulative resources used up to and including the I'th90 // instruction. The 0th instruction is the base case.91 if (InstIdx == 0)92 return RS[0];93 // Return the difference between the cumulative resources used by InstIdx and94 // its predecessor.95 return RS[InstIdx] ^ RS[InstIdx - 1];96}97 98DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF,99 MachineLoopInfo &MLI,100 AAResults *AA)101 : ScheduleDAGInstrs(MF, &MLI), AA(AA) {102 CanHandleTerminators = true;103}104 105/// Apply each ScheduleDAGMutation step in order.106void DefaultVLIWScheduler::postProcessDAG() {107 for (auto &M : Mutations)108 M->apply(this);109}110 111void DefaultVLIWScheduler::schedule() {112 // Build the scheduling graph.113 buildSchedGraph(AA);114 postProcessDAG();115}116 117VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf,118 MachineLoopInfo &mli, AAResults *aa)119 : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {120 ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget());121 ResourceTracker->setTrackResources(true);122 VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA);123}124 125VLIWPacketizerList::~VLIWPacketizerList() {126 delete VLIWScheduler;127 delete ResourceTracker;128}129 130// End the current packet, bundle packet instructions and reset DFA state.131void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,132 MachineBasicBlock::iterator MI) {133 LLVM_DEBUG({134 if (!CurrentPacketMIs.empty()) {135 dbgs() << "Finalizing packet:\n";136 unsigned Idx = 0;137 for (MachineInstr *MI : CurrentPacketMIs) {138 unsigned R = ResourceTracker->getUsedResources(Idx++);139 dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;140 }141 }142 });143 if (CurrentPacketMIs.size() > 1) {144 MachineInstr &MIFirst = *CurrentPacketMIs.front();145 finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());146 }147 CurrentPacketMIs.clear();148 ResourceTracker->clearResources();149 LLVM_DEBUG(dbgs() << "End packet\n");150}151 152// Bundle machine instructions into packets.153void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,154 MachineBasicBlock::iterator BeginItr,155 MachineBasicBlock::iterator EndItr) {156 assert(VLIWScheduler && "VLIW Scheduler is not initialized!");157 VLIWScheduler->startBlock(MBB);158 VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,159 std::distance(BeginItr, EndItr));160 VLIWScheduler->schedule();161 162 LLVM_DEBUG({163 dbgs() << "Scheduling DAG of the packetize region\n";164 VLIWScheduler->dump();165 });166 167 // Generate MI -> SU map.168 MIToSUnit.clear();169 for (SUnit &SU : VLIWScheduler->SUnits)170 MIToSUnit[SU.getInstr()] = &SU;171 172 bool LimitPresent = InstrLimit.getPosition();173 174 // The main packetizer loop.175 for (; BeginItr != EndItr; ++BeginItr) {176 if (LimitPresent) {177 if (InstrCount >= InstrLimit) {178 EndItr = BeginItr;179 break;180 }181 InstrCount++;182 }183 MachineInstr &MI = *BeginItr;184 initPacketizerState();185 186 // End the current packet if needed.187 if (isSoloInstruction(MI)) {188 endPacket(MBB, MI);189 continue;190 }191 192 // Ignore pseudo instructions.193 if (ignorePseudoInstruction(MI, MBB))194 continue;195 196 SUnit *SUI = MIToSUnit[&MI];197 assert(SUI && "Missing SUnit Info!");198 199 // Ask DFA if machine resource is available for MI.200 LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);201 202 bool ResourceAvail = ResourceTracker->canReserveResources(MI);203 LLVM_DEBUG({204 if (ResourceAvail)205 dbgs() << " Resources are available for adding MI to packet\n";206 else207 dbgs() << " Resources NOT available\n";208 });209 if (ResourceAvail && shouldAddToPacket(MI)) {210 // Dependency check for MI with instructions in CurrentPacketMIs.211 for (auto *MJ : CurrentPacketMIs) {212 SUnit *SUJ = MIToSUnit[MJ];213 assert(SUJ && "Missing SUnit Info!");214 215 LLVM_DEBUG(dbgs() << " Checking against MJ " << *MJ);216 // Is it legal to packetize SUI and SUJ together.217 if (!isLegalToPacketizeTogether(SUI, SUJ)) {218 LLVM_DEBUG(dbgs() << " Not legal to add MI, try to prune\n");219 // Allow packetization if dependency can be pruned.220 if (!isLegalToPruneDependencies(SUI, SUJ)) {221 // End the packet if dependency cannot be pruned.222 LLVM_DEBUG(dbgs()223 << " Could not prune dependencies for adding MI\n");224 endPacket(MBB, MI);225 break;226 }227 LLVM_DEBUG(dbgs() << " Pruned dependence for adding MI\n");228 }229 }230 } else {231 LLVM_DEBUG(if (ResourceAvail) dbgs()232 << "Resources are available, but instruction should not be "233 "added to packet\n "234 << MI);235 // End the packet if resource is not available, or if the instruction236 // should not be added to the current packet.237 endPacket(MBB, MI);238 }239 240 // Add MI to the current packet.241 LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');242 BeginItr = addToPacket(MI);243 } // For all instructions in the packetization range.244 245 // End any packet left behind.246 endPacket(MBB, EndItr);247 VLIWScheduler->exitRegion();248 VLIWScheduler->finishBlock();249}250 251bool VLIWPacketizerList::alias(const MachineMemOperand &Op1,252 const MachineMemOperand &Op2,253 bool UseTBAA) const {254 if (!Op1.getValue() || !Op2.getValue() || !Op1.getSize().hasValue() ||255 !Op2.getSize().hasValue())256 return true;257 258 int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());259 int64_t Overlapa = Op1.getSize().getValue() + Op1.getOffset() - MinOffset;260 int64_t Overlapb = Op2.getSize().getValue() + 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 271bool 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.285void VLIWPacketizerList::addMutation(286 std::unique_ptr<ScheduleDAGMutation> Mutation) {287 VLIWScheduler->addMutation(std::move(Mutation));288}289