From b23c47bab37248ebc13e01b410701b1b033811c1 Mon Sep 17 00:00:00 2001 From: Colin LeMahieu Date: Sun, 31 May 2015 21:57:09 +0000 Subject: [PATCH] [Hexagon] Adding MC packet shuffler. llvm-svn: 238692 --- llvm/lib/Target/Hexagon/Hexagon.h | 3 + .../lib/Target/Hexagon/MCTargetDesc/CMakeLists.txt | 2 + .../Hexagon/MCTargetDesc/HexagonMCInstrInfo.cpp | 82 ++++- .../Hexagon/MCTargetDesc/HexagonMCInstrInfo.h | 27 +- .../Hexagon/MCTargetDesc/HexagonMCShuffler.cpp | 181 ++++++++++ .../Hexagon/MCTargetDesc/HexagonMCShuffler.h | 65 ++++ .../Hexagon/MCTargetDesc/HexagonMCTargetDesc.h | 4 + .../Hexagon/MCTargetDesc/HexagonShuffler.cpp | 385 +++++++++++++++++++++ .../Target/Hexagon/MCTargetDesc/HexagonShuffler.h | 139 ++++++++ 9 files changed, 882 insertions(+), 6 deletions(-) create mode 100644 llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCShuffler.cpp create mode 100644 llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCShuffler.h create mode 100644 llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp create mode 100644 llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.h diff --git a/llvm/lib/Target/Hexagon/Hexagon.h b/llvm/lib/Target/Hexagon/Hexagon.h index ce3f1b9..6e2ecaf 100644 --- a/llvm/lib/Target/Hexagon/Hexagon.h +++ b/llvm/lib/Target/Hexagon/Hexagon.h @@ -79,5 +79,8 @@ namespace llvm { // Minimum number of instructions in an end-loop packet. #define HEXAGON_PACKET_INNER_SIZE 2 #define HEXAGON_PACKET_OUTER_SIZE 3 +// Maximum number of instructions in a packet before shuffling, +// including a compound one or a duplex or an extender. +#define HEXAGON_PRESHUFFLE_PACKET_SIZE (HEXAGON_PACKET_SIZE + 3) #endif diff --git a/llvm/lib/Target/Hexagon/MCTargetDesc/CMakeLists.txt b/llvm/lib/Target/Hexagon/MCTargetDesc/CMakeLists.txt index 4c987ed..90b34d3 100644 --- a/llvm/lib/Target/Hexagon/MCTargetDesc/CMakeLists.txt +++ b/llvm/lib/Target/Hexagon/MCTargetDesc/CMakeLists.txt @@ -5,7 +5,9 @@ add_llvm_library(LLVMHexagonDesc HexagonMCAsmInfo.cpp HexagonMCCodeEmitter.cpp HexagonMCInstrInfo.cpp + HexagonMCShuffler.cpp HexagonMCTargetDesc.cpp + HexagonShuffler.cpp ) add_dependencies(LLVMHexagonDesc HexagonCommonTableGen) diff --git a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCInstrInfo.cpp b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCInstrInfo.cpp index 5ea00d3..7b0760e 100644 --- a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCInstrInfo.cpp +++ b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCInstrInfo.cpp @@ -11,9 +11,12 @@ // //===----------------------------------------------------------------------===// +#include "HexagonMCInstrInfo.h" + #include "Hexagon.h" #include "HexagonBaseInfo.h" -#include "HexagonMCInstrInfo.h" + +#include "llvm/MC/MCSubtargetInfo.h" namespace llvm { iterator_range @@ -140,6 +143,21 @@ MCOperand const &HexagonMCInstrInfo::getNewValueOperand(MCInstrInfo const &MCII, return (MCO); } +int HexagonMCInstrInfo::getSubTarget(MCInstrInfo const &MCII, + MCInst const &MCI) { + const uint64_t F = HexagonMCInstrInfo::getDesc(MCII, MCI).TSFlags; + + HexagonII::SubTarget Target = static_cast( + (F >> HexagonII::validSubTargetPos) & HexagonII::validSubTargetMask); + + switch (Target) { + default: + return Hexagon::ArchV4; + case HexagonII::HasV5SubT: + return Hexagon::ArchV5; + } +} + // Return the Hexagon ISA class for the insn. unsigned HexagonMCInstrInfo::getType(MCInstrInfo const &MCII, MCInst const &MCI) { @@ -148,6 +166,28 @@ unsigned HexagonMCInstrInfo::getType(MCInstrInfo const &MCII, return ((F >> HexagonII::TypePos) & HexagonII::TypeMask); } +unsigned HexagonMCInstrInfo::getUnits(MCInstrInfo const &MCII, + MCSubtargetInfo const &STI, + MCInst const &MCI) { + + const InstrItinerary *II = STI.getSchedModel().InstrItineraries; + int SchedClass = HexagonMCInstrInfo::getDesc(MCII, MCI).getSchedClass(); + return ((II[SchedClass].FirstStage + HexagonStages)->getUnits()); +} + +bool HexagonMCInstrInfo::hasImmExt(MCInst const &MCI) { + if (!HexagonMCInstrInfo::isBundle(MCI)) + return false; + + for (const auto &I : HexagonMCInstrInfo::bundleInstructions(MCI)) { + auto MI = I.getInst(); + if (isImmext(*MI)) + return true; + } + + return false; +} + // Return whether the instruction is a legal new-value producer. bool HexagonMCInstrInfo::hasNewValue(MCInstrInfo const &MCII, MCInst const &MCI) { @@ -212,20 +252,23 @@ bool HexagonMCInstrInfo::isConstExtended(MCInstrInfo const &MCII, return (ImmValue < MinValue || ImmValue > MaxValue); } -// Return true if the instruction may be extended based on the operand value. bool HexagonMCInstrInfo::isExtendable(MCInstrInfo const &MCII, MCInst const &MCI) { uint64_t const F = HexagonMCInstrInfo::getDesc(MCII, MCI).TSFlags; return (F >> HexagonII::ExtendablePos) & HexagonII::ExtendableMask; } -// Return whether the instruction must be always extended. bool HexagonMCInstrInfo::isExtended(MCInstrInfo const &MCII, MCInst const &MCI) { uint64_t const F = HexagonMCInstrInfo::getDesc(MCII, MCI).TSFlags; return (F >> HexagonII::ExtendedPos) & HexagonII::ExtendedMask; } +bool HexagonMCInstrInfo::isFloat(MCInstrInfo const &MCII, MCInst const &MCI) { + const uint64_t F = HexagonMCInstrInfo::getDesc(MCII, MCI).TSFlags; + return ((F >> HexagonII::FPPos) & HexagonII::FPMask); +} + bool HexagonMCInstrInfo::isImmext(MCInst const &MCI) { auto Op = MCI.getOpcode(); return (Op == Hexagon::A4_ext_b || Op == Hexagon::A4_ext_c || @@ -273,17 +316,26 @@ bool HexagonMCInstrInfo::isPredicatedTrue(MCInstrInfo const &MCII, !((F >> HexagonII::PredicatedFalsePos) & HexagonII::PredicatedFalseMask)); } -// Return whether the insn is a prefix. bool HexagonMCInstrInfo::isPrefix(MCInstrInfo const &MCII, MCInst const &MCI) { return (HexagonMCInstrInfo::getType(MCII, MCI) == HexagonII::TypePREFIX); } -// Return whether the insn is solo, i.e., cannot be in a packet. bool HexagonMCInstrInfo::isSolo(MCInstrInfo const &MCII, MCInst const &MCI) { const uint64_t F = HexagonMCInstrInfo::getDesc(MCII, MCI).TSFlags; return ((F >> HexagonII::SoloPos) & HexagonII::SoloMask); } +bool HexagonMCInstrInfo::isSoloAX(MCInstrInfo const &MCII, MCInst const &MCI) { + const uint64_t F = HexagonMCInstrInfo::getDesc(MCII, MCI).TSFlags; + return ((F >> HexagonII::SoloAXPos) & HexagonII::SoloAXMask); +} + +bool HexagonMCInstrInfo::isSoloAin1(MCInstrInfo const &MCII, + MCInst const &MCI) { + const uint64_t F = HexagonMCInstrInfo::getDesc(MCII, MCI).TSFlags; + return ((F >> HexagonII::SoloAin1Pos) & HexagonII::SoloAin1Mask); +} + void HexagonMCInstrInfo::padEndloop(MCInst &MCB) { MCInst Nop; Nop.setOpcode(Hexagon::A2_nop); @@ -295,6 +347,26 @@ void HexagonMCInstrInfo::padEndloop(MCInst &MCB) { MCB.addOperand(MCOperand::createInst(new MCInst(Nop))); } +bool HexagonMCInstrInfo::prefersSlot3(MCInstrInfo const &MCII, + MCInst const &MCI) { + if (HexagonMCInstrInfo::getType(MCII, MCI) == HexagonII::TypeCR) + return false; + + unsigned SchedClass = HexagonMCInstrInfo::getDesc(MCII, MCI).getSchedClass(); + switch (SchedClass) { + case Hexagon::Sched::ALU32_3op_tc_2_SLOT0123: + case Hexagon::Sched::ALU64_tc_2_SLOT23: + case Hexagon::Sched::ALU64_tc_3x_SLOT23: + case Hexagon::Sched::M_tc_2_SLOT23: + case Hexagon::Sched::M_tc_3x_SLOT23: + case Hexagon::Sched::S_2op_tc_2_SLOT23: + case Hexagon::Sched::S_3op_tc_2_SLOT23: + case Hexagon::Sched::S_3op_tc_3x_SLOT23: + return true; + } + return false; +} + void HexagonMCInstrInfo::setInnerLoop(MCInst &MCI) { assert(isBundle(MCI)); MCOperand &Operand = MCI.getOperand(0); diff --git a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCInstrInfo.h b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCInstrInfo.h index 5522a03..99970e2 100644 --- a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCInstrInfo.h +++ b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCInstrInfo.h @@ -1,4 +1,4 @@ -//===- HexagonMCInstrInfo.cpp - Hexagon sub-class of MCInst ---------------===// +//===- HexagonMCInstrInfo.cpp - Utility functions on Hexagon MCInsts ------===// // // The LLVM Compiler Infrastructure // @@ -27,6 +27,12 @@ class MCOperand; namespace HexagonII { enum class MemAccessSize; } +class DuplexCandidate { +public: + unsigned packetIndexI, packetIndexJ, iClass; + DuplexCandidate(unsigned i, unsigned j, unsigned iClass) + : packetIndexI(i), packetIndexJ(j), iClass(iClass) {} +}; namespace HexagonMCInstrInfo { size_t const innerLoopOffset = 0; int64_t const innerLoopMask = 1 << innerLoopOffset; @@ -84,9 +90,17 @@ unsigned short getNewValueOp(MCInstrInfo const &MCII, MCInst const &MCI); // Return the operand that consumes or produces a new value. MCOperand const &getNewValueOperand(MCInstrInfo const &MCII, MCInst const &MCI); +int getSubTarget(MCInstrInfo const &MCII, MCInst const &MCI); + // Return the Hexagon ISA class for the insn. unsigned getType(MCInstrInfo const &MCII, MCInst const &MCI); +/// Return the slots used by the insn. +unsigned getUnits(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, + MCInst const &MCI); + +bool hasImmExt(MCInst const &MCI); + // Return whether the instruction is a legal new-value producer. bool hasNewValue(MCInstrInfo const &MCII, MCInst const &MCI); @@ -108,6 +122,9 @@ bool isExtendable(MCInstrInfo const &MCII, MCInst const &MCI); // Return whether the instruction must be always extended. bool isExtended(MCInstrInfo const &MCII, MCInst const &MCI); +/// Return whether it is a floating-point insn. +bool isFloat(MCInstrInfo const &MCII, MCInst const &MCI); + // Returns whether this instruction is an immediate extender bool isImmext(MCInst const &MCI); @@ -136,9 +153,17 @@ bool isPrefix(MCInstrInfo const &MCII, MCInst const &MCI); // Return whether the insn is solo, i.e., cannot be in a packet. bool isSolo(MCInstrInfo const &MCII, MCInst const &MCI); +/// Return whether the insn can be packaged only with A and X-type insns. +bool isSoloAX(MCInstrInfo const &MCII, MCInst const &MCI); + +/// Return whether the insn can be packaged only with an A-type insn in slot #1. +bool isSoloAin1(MCInstrInfo const &MCII, MCInst const &MCI); + // Pad the bundle with nops to satisfy endloop requirements void padEndloop(MCInst &MCI); +bool prefersSlot3(MCInstrInfo const &MCII, MCInst const &MCI); + // Marks a bundle as endloop0 void setInnerLoop(MCInst &MCI); diff --git a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCShuffler.cpp b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCShuffler.cpp new file mode 100644 index 0000000..1d38761 --- /dev/null +++ b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCShuffler.cpp @@ -0,0 +1,181 @@ +//===----- HexagonMCShuffler.cpp - MC bundle shuffling --------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This implements the shuffling of insns inside a bundle according to the +// packet formation rules of the Hexagon ISA. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "hexagon-shuffle" + +#include "Hexagon.h" +#include "MCTargetDesc/HexagonMCInstrInfo.h" +#include "MCTargetDesc/HexagonMCShuffler.h" +#include "MCTargetDesc/HexagonMCTargetDesc.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; + +static cl::opt + DisableShuffle("disable-hexagon-shuffle", cl::Hidden, cl::init(false), + cl::desc("Disable Hexagon instruction shuffling")); + +void HexagonMCShuffler::init(MCInst &MCB) { + if (HexagonMCInstrInfo::isBundle(MCB)) { + MCInst const *Extender = nullptr; + // Copy the bundle for the shuffling. + for (const auto &I : HexagonMCInstrInfo::bundleInstructions(MCB)) { + assert(!HexagonMCInstrInfo::getDesc(MCII, *I.getInst()).isPseudo()); + MCInst *MI = const_cast(I.getInst()); + + if (!HexagonMCInstrInfo::isImmext(*MI)) { + append(MI, Extender, HexagonMCInstrInfo::getUnits(MCII, STI, *MI), + false); + Extender = nullptr; + } else + Extender = MI; + } + } + + BundleFlags = MCB.getOperand(0).getImm(); +} + +void HexagonMCShuffler::init(MCInst &MCB, MCInst const *AddMI, + bool bInsertAtFront) { + if (HexagonMCInstrInfo::isBundle(MCB)) { + if (bInsertAtFront && AddMI) + append(AddMI, nullptr, HexagonMCInstrInfo::getUnits(MCII, STI, *AddMI), + false); + MCInst const *Extender = nullptr; + // Copy the bundle for the shuffling. + for (auto const &I : HexagonMCInstrInfo::bundleInstructions(MCB)) { + assert(!HexagonMCInstrInfo::getDesc(MCII, *I.getInst()).isPseudo()); + MCInst *MI = const_cast(I.getInst()); + if (!HexagonMCInstrInfo::isImmext(*MI)) { + append(MI, Extender, HexagonMCInstrInfo::getUnits(MCII, STI, *MI), + false); + Extender = nullptr; + } else + Extender = MI; + } + if (!bInsertAtFront && AddMI) + append(AddMI, nullptr, HexagonMCInstrInfo::getUnits(MCII, STI, *AddMI), + false); + } + + BundleFlags = MCB.getOperand(0).getImm(); +} + +void HexagonMCShuffler::copyTo(MCInst &MCB) { + MCB.clear(); + MCB.addOperand(MCOperand::createImm(BundleFlags)); + // Copy the results into the bundle. + for (HexagonShuffler::iterator I = begin(); I != end(); ++I) { + + MCInst const *MI = I->getDesc(); + MCInst const *Extender = I->getExtender(); + if (Extender) + MCB.addOperand(MCOperand::createInst(Extender)); + MCB.addOperand(MCOperand::createInst(MI)); + } +} + +bool HexagonMCShuffler::reshuffleTo(MCInst &MCB) { + if (shuffle()) { + // Copy the results into the bundle. + copyTo(MCB); + } else + DEBUG(MCB.dump()); + + return (!getError()); +} + +bool llvm::HexagonMCShuffle(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, + MCInst &MCB) { + HexagonMCShuffler MCS(MCII, STI, MCB); + + if (DisableShuffle) + // Ignore if user chose so. + return false; + + if (!HexagonMCInstrInfo::bundleSize(MCB)) { + // There once was a bundle: + // BUNDLE %D2, %R4, %R5, %D7, ... + // * %D2 = IMPLICIT_DEF; flags: + // * %D7 = IMPLICIT_DEF; flags: + // After the IMPLICIT_DEFs were removed by the asm printer, the bundle + // became empty. + DEBUG(dbgs() << "Skipping empty bundle"); + return false; + } else if (!HexagonMCInstrInfo::isBundle(MCB)) { + DEBUG(dbgs() << "Skipping stand-alone insn"); + return false; + } + + // Reorder the bundle and copy the result. + if (!MCS.reshuffleTo(MCB)) { + // Unless there is any error, which should not happen at this point. + unsigned shuffleError = MCS.getError(); + switch (shuffleError) { + default: + llvm_unreachable("unknown error"); + case HexagonShuffler::SHUFFLE_ERROR_INVALID: + llvm_unreachable("invalid packet"); + case HexagonShuffler::SHUFFLE_ERROR_STORES: + llvm_unreachable("too many stores"); + case HexagonShuffler::SHUFFLE_ERROR_LOADS: + llvm_unreachable("too many loads"); + case HexagonShuffler::SHUFFLE_ERROR_BRANCHES: + llvm_unreachable("too many branches"); + case HexagonShuffler::SHUFFLE_ERROR_NOSLOTS: + llvm_unreachable("no suitable slot"); + case HexagonShuffler::SHUFFLE_ERROR_SLOTS: + llvm_unreachable("over-subscribed slots"); + case HexagonShuffler::SHUFFLE_SUCCESS: // Single instruction case. + return true; + } + } + + return true; +} + +bool llvm::HexagonMCShuffle(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, + MCInst &MCB, MCInst const *AddMI, int fixupCount) { + if (!HexagonMCInstrInfo::isBundle(MCB) || !AddMI) + return false; + + // if fixups present, make sure we don't insert too many nops that would + // later prevent an extender from being inserted. + unsigned int bundleSize = HexagonMCInstrInfo::bundleSize(MCB); + if (bundleSize >= HEXAGON_PACKET_SIZE) + return false; + if (fixupCount >= 2) { + return false; + } else { + if (bundleSize == HEXAGON_PACKET_SIZE - 1 && fixupCount) + return false; + } + + if (DisableShuffle) + return false; + + HexagonMCShuffler MCS(MCII, STI, MCB, AddMI); + if (!MCS.reshuffleTo(MCB)) { + unsigned shuffleError = MCS.getError(); + switch (shuffleError) { + default: + return false; + case HexagonShuffler::SHUFFLE_SUCCESS: // single instruction case + return true; + } + } + + return true; +} diff --git a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCShuffler.h b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCShuffler.h new file mode 100644 index 0000000..a21cce1 --- /dev/null +++ b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCShuffler.h @@ -0,0 +1,65 @@ +//=-- HexagonMCShuffler.h ---------------------------------------------------=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This declares the shuffling of insns inside a bundle according to the +// packet formation rules of the Hexagon ISA. +// +//===----------------------------------------------------------------------===// + +#ifndef HEXAGONMCSHUFFLER_H +#define HEXAGONMCSHUFFLER_H + +#include "MCTargetDesc/HexagonShuffler.h" + +namespace llvm { + +class MCInst; + +// Insn bundle shuffler. +class HexagonMCShuffler : public HexagonShuffler { + bool immext_present; + bool duplex_present; + +public: + HexagonMCShuffler(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, + MCInst &MCB) + : HexagonShuffler(MCII, STI) { + init(MCB); + }; + HexagonMCShuffler(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, + MCInst &MCB, const MCInst *AddMI, + bool bInsertAtFront = false) + : HexagonShuffler(MCII, STI) { + init(MCB, AddMI, bInsertAtFront); + }; + + // Copy reordered bundle to another. + void copyTo(MCInst &MCB); + // Reorder and copy result to another. + bool reshuffleTo(MCInst &MCB); + + bool immextPresent() const { return immext_present; }; + bool duplexPresent() const { return duplex_present; }; + +private: + void init(MCInst &MCB); + void init(MCInst &MCB, const MCInst *AddMI, bool bInsertAtFront = false); +}; + +// Invocation of the shuffler. +bool HexagonMCShuffle(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, + MCInst &); +bool HexagonMCShuffle(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, + MCInst &, const MCInst *, int); +unsigned HexagonMCShuffle(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, + MCContext &Context, MCInst &, + SmallVector); +} + +#endif // HEXAGONMCSHUFFLER_H diff --git a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCTargetDesc.h b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCTargetDesc.h index de63fd2..bce8422 100644 --- a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCTargetDesc.h +++ b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonMCTargetDesc.h @@ -17,6 +17,8 @@ #include namespace llvm { +class InstrItinerary; +class InstrStage; class MCAsmBackend; class MCCodeEmitter; class MCContext; @@ -31,6 +33,8 @@ class raw_pwrite_stream; extern Target TheHexagonTarget; +extern const InstrStage HexagonStages[]; + MCInstrInfo *createHexagonMCInstrInfo(); MCCodeEmitter *createHexagonMCCodeEmitter(MCInstrInfo const &MCII, diff --git a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp new file mode 100644 index 0000000..feaaa4f --- /dev/null +++ b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp @@ -0,0 +1,385 @@ +//===----- HexagonShuffler.cpp - Instruction bundle shuffling -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This implements the shuffling of insns inside a bundle according to the +// packet formation rules of the Hexagon ISA. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "hexagon-shuffle" + +#include +#include +#include "Hexagon.h" +#include "MCTargetDesc/HexagonBaseInfo.h" +#include "MCTargetDesc/HexagonMCTargetDesc.h" +#include "MCTargetDesc/HexagonMCInstrInfo.h" +#include "HexagonShuffler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +// Insn shuffling priority. +class HexagonBid { + // The priority is directly proportional to how restricted the insn is based + // on its flexibility to run on the available slots. So, the fewer slots it + // may run on, the higher its priority. + enum { MAX = 360360 }; // LCD of 1/2, 1/3, 1/4,... 1/15. + unsigned Bid; + +public: + HexagonBid() : Bid(0){}; + HexagonBid(unsigned B) { Bid = B ? MAX / countPopulation(B) : 0; }; + + // Check if the insn priority is overflowed. + bool isSold() const { return (Bid >= MAX); }; + + HexagonBid &operator+=(const HexagonBid &B) { + Bid += B.Bid; + return *this; + }; +}; + +// Slot shuffling allocation. +class HexagonUnitAuction { + HexagonBid Scores[HEXAGON_PACKET_SIZE]; + // Mask indicating which slot is unavailable. + unsigned isSold : HEXAGON_PACKET_SIZE; + +public: + HexagonUnitAuction() : isSold(0){}; + + // Allocate slots. + bool bid(unsigned B) { + // Exclude already auctioned slots from the bid. + unsigned b = B & ~isSold; + if (b) { + for (unsigned i = 0; i < HEXAGON_PACKET_SIZE; ++i) + if (b & (1 << i)) { + // Request candidate slots. + Scores[i] += HexagonBid(b); + isSold |= Scores[i].isSold() << i; + } + return true; + ; + } else + // Error if the desired slots are already full. + return false; + }; +}; + +unsigned HexagonResource::setWeight(unsigned s) { + const unsigned SlotWeight = 8; + const unsigned MaskWeight = SlotWeight - 1; + bool Key = (1 << s) & getUnits(); + + // Calculate relative weight of the insn for the given slot, weighing it the + // heavier the more restrictive the insn is and the lowest the slots that the + // insn may be executed in. + Weight = + (Key << (SlotWeight * s)) * ((MaskWeight - countPopulation(getUnits())) + << countTrailingZeros(getUnits())); + return (Weight); +} + +HexagonShuffler::HexagonShuffler(MCInstrInfo const &MCII, + MCSubtargetInfo const &STI) + : MCII(MCII), STI(STI) { + reset(); +} + +void HexagonShuffler::reset() { + Packet.clear(); + BundleFlags = 0; + Error = SHUFFLE_SUCCESS; +} + +void HexagonShuffler::append(MCInst const *ID, MCInst const *Extender, + unsigned S, bool X) { + HexagonInstr PI(ID, Extender, S, X); + + Packet.push_back(PI); +} + +/// Check that the packet is legal and enforce relative insn order. +bool HexagonShuffler::check() { + // Descriptive slot masks. + const unsigned slotSingleLoad = 0x1, slotSingleStore = 0x1, slotOne = 0x2, + slotThree = 0x8, slotFirstJump = 0x8, slotLastJump = 0x4, + slotFirstLoadStore = 0x2, slotLastLoadStore = 0x1; + // Highest slots for branches and stores used to keep their original order. + unsigned slotJump = slotFirstJump; + unsigned slotLoadStore = slotFirstLoadStore; + // Number of branches, solo branches, indirect branches. + unsigned jumps = 0, jump1 = 0, jumpr = 0; + // Number of memory operations, loads, solo loads, stores, solo stores, single + // stores. + unsigned memory = 0, loads = 0, load0 = 0, stores = 0, store0 = 0, store1 = 0; + // Number of duplex insns, solo insns. + unsigned duplex = 0, solo = 0; + // Number of insns restricting other insns in the packet to A and X types, + // which is neither A or X types. + unsigned onlyAX = 0, neitherAnorX = 0; + // Number of insns restricting other insns in slot #1 to A type. + unsigned onlyAin1 = 0; + // Number of insns restricting any insn in slot #1, except A2_nop. + unsigned onlyNo1 = 0; + unsigned xtypeFloat = 0; + unsigned pSlot3Cnt = 0; + iterator slot3ISJ = end(); + + // Collect information from the insns in the packet. + for (iterator ISJ = begin(); ISJ != end(); ++ISJ) { + MCInst const *ID = ISJ->getDesc(); + + if (HexagonMCInstrInfo::isSolo(MCII, *ID)) + solo += !ISJ->isSoloException(); + else if (HexagonMCInstrInfo::isSoloAX(MCII, *ID)) + onlyAX += !ISJ->isSoloException(); + else if (HexagonMCInstrInfo::isSoloAin1(MCII, *ID)) + onlyAin1 += !ISJ->isSoloException(); + if (HexagonMCInstrInfo::getType(MCII, *ID) != HexagonII::TypeALU32 && + HexagonMCInstrInfo::getType(MCII, *ID) != HexagonII::TypeXTYPE) + ++neitherAnorX; + if (HexagonMCInstrInfo::prefersSlot3(MCII, *ID)) { + ++pSlot3Cnt; + slot3ISJ = ISJ; + } + + switch (HexagonMCInstrInfo::getType(MCII, *ID)) { + case HexagonII::TypeXTYPE: + if (HexagonMCInstrInfo::isFloat(MCII, *ID)) + ++xtypeFloat; + break; + case HexagonII::TypeJR: + ++jumpr; + // Fall-through. + case HexagonII::TypeJ: + ++jumps; + break; + case HexagonII::TypeLD: + ++loads; + ++memory; + if (ISJ->Core.getUnits() == slotSingleLoad) + ++load0; + if (HexagonMCInstrInfo::getDesc(MCII, *ID).isReturn()) + ++jumps, ++jump1; // DEALLOC_RETURN is of type LD. + break; + case HexagonII::TypeST: + ++stores; + ++memory; + if (ISJ->Core.getUnits() == slotSingleStore) + ++store0; + break; + case HexagonII::TypeMEMOP: + ++loads; + ++stores; + ++store1; + ++memory; + break; + case HexagonII::TypeNV: + ++memory; // NV insns are memory-like. + if (HexagonMCInstrInfo::getDesc(MCII, *ID).isBranch()) + ++jumps, ++jump1; + break; + case HexagonII::TypeCR: + // Legacy conditional branch predicated on a register. + case HexagonII::TypeSYSTEM: + if (HexagonMCInstrInfo::getDesc(MCII, *ID).mayLoad()) + ++loads; + break; + } + } + + // Check if the packet is legal. + if ((load0 > 1 || store0 > 1) || (duplex > 1 || (duplex && memory)) || + (solo && size() > 1) || (onlyAX && neitherAnorX > 1) || + (onlyAX && xtypeFloat)) { + Error = SHUFFLE_ERROR_INVALID; + return false; + } + + if (jump1 && jumps > 1) { + // Error if single branch with another branch. + Error = SHUFFLE_ERROR_BRANCHES; + return false; + } + + // Modify packet accordingly. + // TODO: need to reserve slots #0 and #1 for duplex insns. + bool bOnlySlot3 = false; + for (iterator ISJ = begin(); ISJ != end(); ++ISJ) { + MCInst const *ID = ISJ->getDesc(); + + if (!ISJ->Core.getUnits()) { + // Error if insn may not be executed in any slot. + Error = SHUFFLE_ERROR_UNKNOWN; + return false; + } + + // Exclude from slot #1 any insn but A2_nop. + if (HexagonMCInstrInfo::getDesc(MCII, *ID).getOpcode() != Hexagon::A2_nop) + if (onlyNo1) + ISJ->Core.setUnits(ISJ->Core.getUnits() & ~slotOne); + + // Exclude from slot #1 any insn but A-type. + if (HexagonMCInstrInfo::getType(MCII, *ID) != HexagonII::TypeALU32) + if (onlyAin1) + ISJ->Core.setUnits(ISJ->Core.getUnits() & ~slotOne); + + // Branches must keep the original order. + if (HexagonMCInstrInfo::getDesc(MCII, *ID).isBranch() || + HexagonMCInstrInfo::getDesc(MCII, *ID).isCall()) + if (jumps > 1) { + if (jumpr || slotJump < slotLastJump) { + // Error if indirect branch with another branch or + // no more slots available for branches. + Error = SHUFFLE_ERROR_BRANCHES; + return false; + } + // Pin the branch to the highest slot available to it. + ISJ->Core.setUnits(ISJ->Core.getUnits() & slotJump); + // Update next highest slot available to branches. + slotJump >>= 1; + } + + // A single load must use slot #0. + if (HexagonMCInstrInfo::getDesc(MCII, *ID).mayLoad()) { + if (loads == 1 && loads == memory) + // Pin the load to slot #0. + ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleLoad); + } + + // A single store must use slot #0. + if (HexagonMCInstrInfo::getDesc(MCII, *ID).mayStore()) { + if (!store0) { + if (stores == 1) + ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleStore); + else if (stores > 1) { + if (slotLoadStore < slotLastLoadStore) { + // Error if no more slots available for stores. + Error = SHUFFLE_ERROR_STORES; + return false; + } + // Pin the store to the highest slot available to it. + ISJ->Core.setUnits(ISJ->Core.getUnits() & slotLoadStore); + // Update the next highest slot available to stores. + slotLoadStore >>= 1; + } + } + if (store1 && stores > 1) { + // Error if a single store with another store. + Error = SHUFFLE_ERROR_STORES; + return false; + } + } + + // flag if an instruction can only be executed in slot 3 + if (ISJ->Core.getUnits() == slotThree) + bOnlySlot3 = true; + + if (!ISJ->Core.getUnits()) { + // Error if insn may not be executed in any slot. + Error = SHUFFLE_ERROR_NOSLOTS; + return false; + } + } + + bool validateSlots = true; + if (bOnlySlot3 == false && pSlot3Cnt == 1 && slot3ISJ != end()) { + // save off slot mask of instruction marked with A_PREFER_SLOT3 + // and then pin it to slot #3 + unsigned saveUnits = slot3ISJ->Core.getUnits(); + slot3ISJ->Core.setUnits(saveUnits & slotThree); + + HexagonUnitAuction AuctionCore; + std::sort(begin(), end(), HexagonInstr::lessCore); + + // see if things ok with that instruction being pinned to slot #3 + bool bFail = false; + for (iterator I = begin(); I != end() && bFail != true; ++I) + if (!AuctionCore.bid(I->Core.getUnits())) + bFail = true; + + // if yes, great, if not then restore original slot mask + if (!bFail) + validateSlots = false; // all good, no need to re-do auction + else + for (iterator ISJ = begin(); ISJ != end(); ++ISJ) { + MCInst const *ID = ISJ->getDesc(); + if (HexagonMCInstrInfo::prefersSlot3(MCII, *ID)) + ISJ->Core.setUnits(saveUnits); + } + } + + // Check if any slot, core, is over-subscribed. + // Verify the core slot subscriptions. + if (validateSlots) { + HexagonUnitAuction AuctionCore; + + std::sort(begin(), end(), HexagonInstr::lessCore); + + for (iterator I = begin(); I != end(); ++I) + if (!AuctionCore.bid(I->Core.getUnits())) { + Error = SHUFFLE_ERROR_SLOTS; + return false; + } + } + + Error = SHUFFLE_SUCCESS; + return true; +} + +bool HexagonShuffler::shuffle() { + if (size() > HEXAGON_PACKET_SIZE) { + // Ignore a packet with with more than what a packet can hold + // or with compound or duplex insns for now. + Error = SHUFFLE_ERROR_INVALID; + return false; + } + + // Check and prepare packet. + if (size() > 1 && check()) + // Reorder the handles for each slot. + for (unsigned nSlot = 0, emptySlots = 0; nSlot < HEXAGON_PACKET_SIZE; + ++nSlot) { + iterator ISJ, ISK; + unsigned slotSkip, slotWeight; + + // Prioritize the handles considering their restrictions. + for (ISJ = ISK = Packet.begin(), slotSkip = slotWeight = 0; + ISK != Packet.end(); ++ISK, ++slotSkip) + if (slotSkip < nSlot - emptySlots) + // Note which handle to begin at. + ++ISJ; + else + // Calculate the weight of the slot. + slotWeight += ISK->Core.setWeight(HEXAGON_PACKET_SIZE - nSlot - 1); + + if (slotWeight) + // Sort the packet, favoring source order, + // beginning after the previous slot. + std::sort(ISJ, Packet.end()); + else + // Skip unused slot. + ++emptySlots; + } + + for (iterator ISJ = begin(); ISJ != end(); ++ISJ) + DEBUG(dbgs().write_hex(ISJ->Core.getUnits()); + dbgs() << ':' + << HexagonMCInstrInfo::getDesc(MCII, *ISJ->getDesc()) + .getOpcode(); + dbgs() << '\n'); + DEBUG(dbgs() << '\n'); + + return (!getError()); +} diff --git a/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.h b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.h new file mode 100644 index 0000000..9218fd3 --- /dev/null +++ b/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.h @@ -0,0 +1,139 @@ +//===----- HexagonShuffler.h - Instruction bundle shuffling ---------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This implements the shuffling of insns inside a bundle according to the +// packet formation rules of the Hexagon ISA. +// +//===----------------------------------------------------------------------===// + +#ifndef HEXAGONSHUFFLER_H +#define HEXAGONSHUFFLER_H + +#include "Hexagon.h" +#include "MCTargetDesc/HexagonMCInstrInfo.h" + +#include "llvm/ADT/SmallVector.h" +#include "llvm/MC/MCInstrInfo.h" + +using namespace llvm; + +namespace llvm { +// Insn resources. +class HexagonResource { + // Mask of the slots or units that may execute the insn and + // the weight or priority that the insn requires to be assigned a slot. + unsigned Slots, Weight; + +public: + HexagonResource(unsigned s) { setUnits(s); }; + + void setUnits(unsigned s) { + Slots = s & ~(-1 << HEXAGON_PACKET_SIZE); + setWeight(s); + }; + unsigned setWeight(unsigned s); + + unsigned getUnits() const { return (Slots); }; + unsigned getWeight() const { return (Weight); }; + + // Check if the resources are in ascending slot order. + static bool lessUnits(const HexagonResource &A, const HexagonResource &B) { + return (countPopulation(A.getUnits()) < countPopulation(B.getUnits())); + }; + // Check if the resources are in ascending weight order. + static bool lessWeight(const HexagonResource &A, const HexagonResource &B) { + return (A.getWeight() < B.getWeight()); + }; +}; + +// Handle to an insn used by the shuffling algorithm. +class HexagonInstr { + friend class HexagonShuffler; + + MCInst const *ID; + MCInst const *Extender; + HexagonResource Core; + bool SoloException; + +public: + HexagonInstr(MCInst const *id, MCInst const *Extender, unsigned s, + bool x = false) + : ID(id), Extender(Extender), Core(s), SoloException(x){}; + + MCInst const *getDesc() const { return (ID); }; + + MCInst const *getExtender() const { return Extender; } + + unsigned isSoloException() const { return (SoloException); }; + + // Check if the handles are in ascending order for shuffling purposes. + bool operator<(const HexagonInstr &B) const { + return (HexagonResource::lessWeight(B.Core, Core)); + }; + // Check if the handles are in ascending order by core slots. + static bool lessCore(const HexagonInstr &A, const HexagonInstr &B) { + return (HexagonResource::lessUnits(A.Core, B.Core)); + }; +}; + +// Bundle shuffler. +class HexagonShuffler { + typedef SmallVector + HexagonPacket; + + // Insn handles in a bundle. + HexagonPacket Packet; + + // Shuffling error code. + unsigned Error; + +protected: + int64_t BundleFlags; + MCInstrInfo const &MCII; + MCSubtargetInfo const &STI; + +public: + typedef HexagonPacket::iterator iterator; + + enum { + SHUFFLE_SUCCESS = 0, ///< Successful operation. + SHUFFLE_ERROR_INVALID, ///< Invalid bundle. + SHUFFLE_ERROR_STORES, ///< No free slots for store insns. + SHUFFLE_ERROR_LOADS, ///< No free slots for load insns. + SHUFFLE_ERROR_BRANCHES, ///< No free slots for branch insns. + SHUFFLE_ERROR_NOSLOTS, ///< No free slots for other insns. + SHUFFLE_ERROR_SLOTS, ///< Over-subscribed slots. + SHUFFLE_ERROR_UNKNOWN ///< Unknown error. + }; + + explicit HexagonShuffler(MCInstrInfo const &MCII, MCSubtargetInfo const &STI); + + // Reset to initial state. + void reset(); + // Check if the bundle may be validly shuffled. + bool check(); + // Reorder the insn handles in the bundle. + bool shuffle(); + + unsigned size() const { return (Packet.size()); }; + + iterator begin() { return (Packet.begin()); }; + iterator end() { return (Packet.end()); }; + + // Add insn handle to the bundle . + void append(MCInst const *ID, MCInst const *Extender, unsigned S, + bool X = false); + + // Return the error code for the last check or shuffling of the bundle. + void setError(unsigned Err) { Error = Err; }; + unsigned getError() const { return (Error); }; +}; +} + +#endif // HEXAGONSHUFFLER_H -- 2.7.4