RegAllocBasic.h

Go to the documentation of this file.

//===-- RegAllocBasic.h - Basic Register Allocator Header -----------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file declares the RABasic class, which provides a minimal
/// implementation of the basic register allocator.
///
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_CODEGEN_REGALLOCBASIC_H
#define LLVM_CODEGEN_REGALLOCBASIC_H
 
#include "RegAllocBase.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/Spiller.h"
#include <queue>
#include <tuple>
 
namespace llvm {
 
struct CompSpillWeight {
  bool operator()(const LiveInterval *A, const LiveInterval *B) const {
    // Compare by weight first, then use register number as a stable tie-breaker
    // to ensure deterministic ordering when the weights are equal.
    return std::tuple(A->weight(), A->reg()) <
           std::tuple(B->weight(), B->reg());
  }
};
 
/// RABasic provides a minimal implementation of the basic register allocation
/// algorithm. It prioritizes live virtual registers by spill weight and spills
/// whenever a register is unavailable. This is not practical in production but
/// provides a useful baseline both for measuring other allocators and comparing
/// the speed of the basic algorithm against other styles of allocators.
class LLVM_LIBRARY_VISIBILITY RABasic : public MachineFunctionPass,
                                        public RegAllocBase,
                                        private LiveRangeEdit::Delegate {
  // context
  MachineFunction *MF = nullptr;
 
  // state
  std::unique_ptr<Spiller> SpillerInstance;
  std::priority_queue<const LiveInterval *, std::vector<const LiveInterval *>,
                      CompSpillWeight>
      Queue;
 
  // Scratch space.  Allocated here to avoid repeated malloc calls in
  // selectOrSplit().
  BitVector UsableRegs;
 
  bool LRE_CanEraseVirtReg(Register) override;
  void LRE_WillShrinkVirtReg(Register) override;
 
public:
  RABasic(const RegAllocFilterFunc F = nullptr);
 
  /// Return the pass name.
  StringRef getPassName() const override { return "Basic Register Allocator"; }
 
  /// RABasic analysis usage.
  void getAnalysisUsage(AnalysisUsage &AU) const override;
 
  void releaseMemory() override;
 
  Spiller &spiller() override { return *SpillerInstance; }
 
  void enqueueImpl(const LiveInterval *LI) override { Queue.push(LI); }
 
  const LiveInterval *dequeue() override {
    if (Queue.empty())
      return nullptr;
    const LiveInterval *LI = Queue.top();
    Queue.pop();
    return LI;
  }
 
  MCRegister selectOrSplit(const LiveInterval &VirtReg,
                           SmallVectorImpl<Register> &SplitVRegs) override;
 
  /// Perform register allocation.
  bool runOnMachineFunction(MachineFunction &mf) override;
 
  MachineFunctionProperties getRequiredProperties() const override {
    return MachineFunctionProperties().set(
        MachineFunctionProperties::Property::NoPHIs);
  }
 
  MachineFunctionProperties getClearedProperties() const override {
    return MachineFunctionProperties().set(
        MachineFunctionProperties::Property::IsSSA);
  }
 
  // Helper for spilling all live virtual registers currently unified under preg
  // that interfere with the most recently queried lvr.  Return true if spilling
  // was successful, and append any new spilled/split intervals to splitLVRs.
  bool spillInterferences(const LiveInterval &VirtReg, MCRegister PhysReg,
                          SmallVectorImpl<Register> &SplitVRegs);
 
  static char ID;
};
} // namespace llvm
#endif