105 lines · c
1//===-- RegAllocBasic.h - Basic Register Allocator Header -----------------===//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///9/// \file10/// This file declares the RABasic class, which provides a minimal11/// implementation of the basic register allocator.12///13//===----------------------------------------------------------------------===//14 15#ifndef LLVM_CODEGEN_REGALLOCBASIC_H16#define LLVM_CODEGEN_REGALLOCBASIC_H17 18#include "RegAllocBase.h"19#include "llvm/CodeGen/LiveRangeEdit.h"20#include "llvm/CodeGen/MachineFunctionPass.h"21#include "llvm/CodeGen/Spiller.h"22#include <queue>23 24namespace llvm {25 26struct CompSpillWeight {27 bool operator()(const LiveInterval *A, const LiveInterval *B) const {28 return A->weight() < B->weight();29 }30};31 32/// RABasic provides a minimal implementation of the basic register allocation33/// algorithm. It prioritizes live virtual registers by spill weight and spills34/// whenever a register is unavailable. This is not practical in production but35/// provides a useful baseline both for measuring other allocators and comparing36/// the speed of the basic algorithm against other styles of allocators.37class LLVM_LIBRARY_VISIBILITY RABasic : public MachineFunctionPass,38 public RegAllocBase,39 private LiveRangeEdit::Delegate {40 // context41 MachineFunction *MF = nullptr;42 43 // state44 std::unique_ptr<Spiller> SpillerInstance;45 std::priority_queue<const LiveInterval *, std::vector<const LiveInterval *>,46 CompSpillWeight>47 Queue;48 49 // Scratch space. Allocated here to avoid repeated malloc calls in50 // selectOrSplit().51 BitVector UsableRegs;52 53 bool LRE_CanEraseVirtReg(Register) override;54 void LRE_WillShrinkVirtReg(Register) override;55 56public:57 RABasic(const RegAllocFilterFunc F = nullptr);58 59 /// Return the pass name.60 StringRef getPassName() const override { return "Basic Register Allocator"; }61 62 /// RABasic analysis usage.63 void getAnalysisUsage(AnalysisUsage &AU) const override;64 65 void releaseMemory() override;66 67 Spiller &spiller() override { return *SpillerInstance; }68 69 void enqueueImpl(const LiveInterval *LI) override { Queue.push(LI); }70 71 const LiveInterval *dequeue() override {72 if (Queue.empty())73 return nullptr;74 const LiveInterval *LI = Queue.top();75 Queue.pop();76 return LI;77 }78 79 MCRegister selectOrSplit(const LiveInterval &VirtReg,80 SmallVectorImpl<Register> &SplitVRegs) override;81 82 /// Perform register allocation.83 bool runOnMachineFunction(MachineFunction &mf) override;84 85 MachineFunctionProperties getRequiredProperties() const override {86 return MachineFunctionProperties().set(87 MachineFunctionProperties::Property::NoPHIs);88 }89 90 MachineFunctionProperties getClearedProperties() const override {91 return MachineFunctionProperties().set(92 MachineFunctionProperties::Property::IsSSA);93 }94 95 // Helper for spilling all live virtual registers currently unified under preg96 // that interfere with the most recently queried lvr. Return true if spilling97 // was successful, and append any new spilled/split intervals to splitLVRs.98 bool spillInterferences(const LiveInterval &VirtReg, MCRegister PhysReg,99 SmallVectorImpl<Register> &SplitVRegs);100 101 static char ID;102};103} // namespace llvm104#endif105