diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp | 110 |
1 files changed, 70 insertions, 40 deletions
diff --git a/contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp b/contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp index 101b30b..9778103 100644 --- a/contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp +++ b/contrib/llvm/lib/CodeGen/RegAllocPBQP.cpp @@ -1,4 +1,4 @@ -//===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===// +//===- RegAllocPBQP.cpp ---- PBQP Register Allocator ----------------------===// // // The LLVM Compiler Infrastructure // @@ -32,30 +32,59 @@ #include "llvm/CodeGen/RegAllocPBQP.h" #include "RegisterCoalescer.h" #include "Spiller.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/CalcSpillWeights.h" +#include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveRangeEdit.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/PBQP/Graph.h" +#include "llvm/CodeGen/PBQP/Math.h" +#include "llvm/CodeGen/PBQP/Solution.h" +#include "llvm/CodeGen/PBQPRAConstraint.h" #include "llvm/CodeGen/RegAllocRegistry.h" +#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/IR/Function.h" #include "llvm/IR/Module.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/Pass.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/Printable.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" +#include <algorithm> +#include <cassert> +#include <cstddef> #include <limits> +#include <map> #include <memory> #include <queue> #include <set> #include <sstream> +#include <string> +#include <system_error> +#include <tuple> +#include <utility> #include <vector> using namespace llvm; @@ -86,7 +115,6 @@ namespace { /// Programming problems. class RegAllocPBQP : public MachineFunctionPass { public: - static char ID; /// Construct a PBQP register allocator. @@ -113,14 +141,13 @@ public: } private: - - typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; - typedef std::vector<const LiveInterval*> Node2LIMap; - typedef std::vector<unsigned> AllowedSet; - typedef std::vector<AllowedSet> AllowedSetMap; - typedef std::pair<unsigned, unsigned> RegPair; - typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; - typedef std::set<unsigned> RegSet; + using LI2NodeMap = std::map<const LiveInterval *, unsigned>; + using Node2LIMap = std::vector<const LiveInterval *>; + using AllowedSet = std::vector<unsigned>; + using AllowedSetMap = std::vector<AllowedSet>; + using RegPair = std::pair<unsigned, unsigned>; + using CoalesceMap = std::map<RegPair, PBQP::PBQPNum>; + using RegSet = std::set<unsigned>; char *customPassID; @@ -187,13 +214,12 @@ public: /// @brief Add interference edges between overlapping vregs. class Interference : public PBQPRAConstraint { private: - - typedef const PBQP::RegAlloc::AllowedRegVector* AllowedRegVecPtr; - typedef std::pair<AllowedRegVecPtr, AllowedRegVecPtr> IKey; - typedef DenseMap<IKey, PBQPRAGraph::MatrixPtr> IMatrixCache; - typedef DenseSet<IKey> DisjointAllowedRegsCache; - typedef std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId> IEdgeKey; - typedef DenseSet<IEdgeKey> IEdgeCache; + using AllowedRegVecPtr = const PBQP::RegAlloc::AllowedRegVector *; + using IKey = std::pair<AllowedRegVecPtr, AllowedRegVecPtr>; + using IMatrixCache = DenseMap<IKey, PBQPRAGraph::MatrixPtr>; + using DisjointAllowedRegsCache = DenseSet<IKey>; + using IEdgeKey = std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId>; + using IEdgeCache = DenseSet<IEdgeKey>; bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId, @@ -228,8 +254,8 @@ private: // for the fast interference graph construction algorithm. The last is there // to save us from looking up node ids via the VRegToNode map in the graph // metadata. - typedef std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId> - IntervalInfo; + using IntervalInfo = + std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>; static SlotIndex getStartPoint(const IntervalInfo &I) { return std::get<0>(I)->segments[std::get<1>(I)].start; @@ -276,7 +302,6 @@ private: } public: - void apply(PBQPRAGraph &G) override { // The following is loosely based on the linear scan algorithm introduced in // "Linear Scan Register Allocation" by Poletto and Sarkar. This version @@ -297,9 +322,10 @@ public: // Cache known disjoint allowed registers pairs DisjointAllowedRegsCache D; - typedef std::set<IntervalInfo, decltype(&lowestEndPoint)> IntervalSet; - typedef std::priority_queue<IntervalInfo, std::vector<IntervalInfo>, - decltype(&lowestStartPoint)> IntervalQueue; + using IntervalSet = std::set<IntervalInfo, decltype(&lowestEndPoint)>; + using IntervalQueue = + std::priority_queue<IntervalInfo, std::vector<IntervalInfo>, + decltype(&lowestStartPoint)>; IntervalSet Active(lowestEndPoint); IntervalQueue Inactive(lowestStartPoint); @@ -363,7 +389,6 @@ public: } private: - // Create an Interference edge and add it to the graph, unless it is // a null matrix, meaning the nodes' allowed registers do not have any // interference. This case occurs frequently between integer and floating @@ -372,7 +397,6 @@ private: bool createInterferenceEdge(PBQPRAGraph &G, PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId, IMatrixCache &C) { - const TargetRegisterInfo &TRI = *G.getMetadata().MF.getSubtarget().getRegisterInfo(); const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs(); @@ -409,7 +433,6 @@ private: } }; - class Coalescing : public PBQPRAConstraint { public: void apply(PBQPRAGraph &G) override { @@ -421,7 +444,6 @@ public: // gives the Ok. for (const auto &MBB : MF) { for (const auto &MI : MBB) { - // Skip not-coalescable or already coalesced copies. if (!CP.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg()) continue; @@ -479,7 +501,6 @@ public: } private: - void addVirtRegCoalesce( PBQPRAGraph::RawMatrix &CostMat, const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed1, @@ -496,14 +517,15 @@ private: } } } - }; -} // End anonymous namespace. +} // end anonymous namespace // Out-of-line destructor/anchor for PBQPRAConstraint. -PBQPRAConstraint::~PBQPRAConstraint() {} +PBQPRAConstraint::~PBQPRAConstraint() = default; + void PBQPRAConstraint::anchor() {} + void PBQPRAConstraintList::anchor() {} void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { @@ -554,7 +576,7 @@ void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF, static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI, const MachineFunction &MF) { - const MCPhysReg *CSR = TRI.getCalleeSavedRegs(&MF); + const MCPhysReg *CSR = MF.getRegInfo().getCalleeSavedRegs(); for (unsigned i = 0; CSR[i] != 0; ++i) if (TRI.regsOverlap(reg, CSR[i])) return true; @@ -639,7 +661,6 @@ void RegAllocPBQP::spillVReg(unsigned VReg, SmallVectorImpl<unsigned> &NewIntervals, MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM, Spiller &VRegSpiller) { - VRegsToAlloc.erase(VReg); LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM, nullptr, &DeadRemats); @@ -717,7 +738,15 @@ void RegAllocPBQP::finalizeAlloc(MachineFunction &MF, if (PReg == 0) { const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg); - PReg = RC.getRawAllocationOrder(MF).front(); + const ArrayRef<MCPhysReg> RawPRegOrder = RC.getRawAllocationOrder(MF); + for (unsigned CandidateReg : RawPRegOrder) { + if (!VRM.getRegInfo().isReserved(CandidateReg)) { + PReg = CandidateReg; + break; + } + } + assert(PReg && + "No un-reserved physical registers in this register class"); } VRM.assignVirt2Phys(LI.reg, PReg); @@ -777,7 +806,6 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { // If there are non-empty intervals allocate them using pbqp. if (!VRegsToAlloc.empty()) { - const TargetSubtargetInfo &Subtarget = MF.getSubtarget(); std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot = llvm::make_unique<PBQPRAConstraintList>(); @@ -840,7 +868,8 @@ static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId, }); } -void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const { +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const { for (auto NId : nodeIds()) { const Vector &Costs = getNodeCosts(NId); assert(Costs.getLength() != 0 && "Empty vector in graph."); @@ -861,7 +890,10 @@ void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const { } } -LLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump() const { dump(dbgs()); } +LLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump() const { + dump(dbgs()); +} +#endif void PBQP::RegAlloc::PBQPRAGraph::printDot(raw_ostream &OS) const { OS << "graph {\n"; @@ -892,5 +924,3 @@ FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) { FunctionPass* llvm::createDefaultPBQPRegisterAllocator() { return createPBQPRegisterAllocator(); } - -#undef DEBUG_TYPE |
