diff options
Diffstat (limited to 'contrib/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp')
| -rw-r--r-- | contrib/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp | 385 |
1 files changed, 385 insertions, 0 deletions
diff --git a/contrib/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp b/contrib/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp new file mode 100644 index 0000000..feaaa4f --- /dev/null +++ b/contrib/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 <algorithm> +#include <utility> +#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()); +} |
