RegAllocFast.cpp | Explore in Territory

//===- RegAllocFast.cpp - A fast register allocator for debug code --------===//
//
// 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 register allocator allocates registers to a basic block at a
/// time, attempting to keep values in registers and reusing registers as
/// appropriate.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/RegAllocFast.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegAllocCommon.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <tuple>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumStores, "Number of stores added");
STATISTIC(NumLoads, "Number of loads added");
STATISTIC(NumCoalesced, "Number of copies coalesced");

// FIXME: Remove this switch when all testcases are fixed!
static cl::opt<bool> IgnoreMissingDefs("rafast-ignore-missing-defs",
                                       cl::Hidden);

static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator",
                                     createFastRegisterAllocator);

namespace {

/// Assign ascending index for instructions in machine basic block. The index
/// can be used to determine dominance between instructions in same MBB.
class InstrPosIndexes { … };

class RegAllocFastImpl { … };

class RegAllocFast : public MachineFunctionPass { … };

} // end anonymous namespace

char RegAllocFast::ID = …;

INITIALIZE_PASS(…)

bool RegAllocFastImpl::shouldAllocateRegister(const Register Reg) const { … }

void RegAllocFastImpl::setPhysRegState(MCPhysReg PhysReg, unsigned NewState) { … }

bool RegAllocFastImpl::isPhysRegFree(MCPhysReg PhysReg) const { … }

/// This allocates space for the specified virtual register to be held on the
/// stack.
int RegAllocFastImpl::getStackSpaceFor(Register VirtReg) { … }

static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A,
                      const MachineInstr &B) { … }

/// Returns false if \p VirtReg is known to not live out of the current block.
bool RegAllocFastImpl::mayLiveOut(Register VirtReg) { … }

/// Returns false if \p VirtReg is known to not be live into the current block.
bool RegAllocFastImpl::mayLiveIn(Register VirtReg) { … }

/// Insert spill instruction for \p AssignedReg before \p Before. Update
/// DBG_VALUEs with \p VirtReg operands with the stack slot.
void RegAllocFastImpl::spill(MachineBasicBlock::iterator Before,
                             Register VirtReg, MCPhysReg AssignedReg, bool Kill,
                             bool LiveOut) { … }

/// Insert reload instruction for \p PhysReg before \p Before.
void RegAllocFastImpl::reload(MachineBasicBlock::iterator Before,
                              Register VirtReg, MCPhysReg PhysReg) { … }

/// Get basic block begin insertion point.
/// This is not just MBB.begin() because surprisingly we have EH_LABEL
/// instructions marking the begin of a basic block. This means we must insert
/// new instructions after such labels...
MachineBasicBlock::iterator RegAllocFastImpl::getMBBBeginInsertionPoint(
    MachineBasicBlock &MBB, SmallSet<Register, 2> &PrologLiveIns) const { … }

/// Reload all currently assigned virtual registers.
void RegAllocFastImpl::reloadAtBegin(MachineBasicBlock &MBB) { … }

/// Handle the direct use of a physical register.  Check that the register is
/// not used by a virtreg. Kill the physreg, marking it free. This may add
/// implicit kills to MO->getParent() and invalidate MO.
bool RegAllocFastImpl::usePhysReg(MachineInstr &MI, MCPhysReg Reg) { … }

bool RegAllocFastImpl::definePhysReg(MachineInstr &MI, MCPhysReg Reg) { … }

/// Mark PhysReg as reserved or free after spilling any virtregs. This is very
/// similar to defineVirtReg except the physreg is reserved instead of
/// allocated.
bool RegAllocFastImpl::displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg) { … }

void RegAllocFastImpl::freePhysReg(MCPhysReg PhysReg) { … }

/// Return the cost of spilling clearing out PhysReg and aliases so it is free
/// for allocation. Returns 0 when PhysReg is free or disabled with all aliases
/// disabled - it can be allocated directly.
/// \returns spillImpossible when PhysReg or an alias can't be spilled.
unsigned RegAllocFastImpl::calcSpillCost(MCPhysReg PhysReg) const { … }

void RegAllocFastImpl::assignDanglingDebugValues(MachineInstr &Definition,
                                                 Register VirtReg,
                                                 MCPhysReg Reg) { … }

/// This method updates local state so that we know that PhysReg is the
/// proper container for VirtReg now.  The physical register must not be used
/// for anything else when this is called.
void RegAllocFastImpl::assignVirtToPhysReg(MachineInstr &AtMI, LiveReg &LR,
                                           MCPhysReg PhysReg) { … }

static bool isCoalescable(const MachineInstr &MI) { … }

Register RegAllocFastImpl::traceCopyChain(Register Reg) const { … }

/// Check if any of \p VirtReg's definitions is a copy. If it is follow the
/// chain of copies to check whether we reach a physical register we can
/// coalesce with.
Register RegAllocFastImpl::traceCopies(Register VirtReg) const { … }

/// Allocates a physical register for VirtReg.
void RegAllocFastImpl::allocVirtReg(MachineInstr &MI, LiveReg &LR,
                                    Register Hint0, bool LookAtPhysRegUses) { … }

void RegAllocFastImpl::allocVirtRegUndef(MachineOperand &MO) { … }

/// Variation of defineVirtReg() with special handling for livethrough regs
/// (tied or earlyclobber) that may interfere with preassigned uses.
/// \return true if MI's MachineOperands were re-arranged/invalidated.
bool RegAllocFastImpl::defineLiveThroughVirtReg(MachineInstr &MI,
                                                unsigned OpNum,
                                                Register VirtReg) { … }

/// Allocates a register for VirtReg definition. Typically the register is
/// already assigned from a use of the virtreg, however we still need to
/// perform an allocation if:
/// - It is a dead definition without any uses.
/// - The value is live out and all uses are in different basic blocks.
///
/// \return true if MI's MachineOperands were re-arranged/invalidated.
bool RegAllocFastImpl::defineVirtReg(MachineInstr &MI, unsigned OpNum,
                                     Register VirtReg, bool LookAtPhysRegUses) { … }

/// Allocates a register for a VirtReg use.
/// \return true if MI's MachineOperands were re-arranged/invalidated.
bool RegAllocFastImpl::useVirtReg(MachineInstr &MI, MachineOperand &MO,
                                  Register VirtReg) { … }

/// Changes operand OpNum in MI the refer the PhysReg, considering subregs.
/// \return true if MI's MachineOperands were re-arranged/invalidated.
bool RegAllocFastImpl::setPhysReg(MachineInstr &MI, MachineOperand &MO,
                                  MCPhysReg PhysReg) { … }

#ifndef NDEBUG

void RegAllocFastImpl::dumpState() const {
  for (unsigned Unit = 1, UnitE = TRI->getNumRegUnits(); Unit != UnitE;
       ++Unit) {
    switch (unsigned VirtReg = RegUnitStates[Unit]) {
    case regFree:
      break;
    case regPreAssigned:
      dbgs() << " " << printRegUnit(Unit, TRI) << "[P]";
      break;
    case regLiveIn:
      llvm_unreachable("Should not have regLiveIn in map");
    default: {
      dbgs() << ' ' << printRegUnit(Unit, TRI) << '=' << printReg(VirtReg);
      LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
      assert(I != LiveVirtRegs.end() && "have LiveVirtRegs entry");
      if (I->LiveOut || I->Reloaded) {
        dbgs() << '[';
        if (I->LiveOut)
          dbgs() << 'O';
        if (I->Reloaded)
          dbgs() << 'R';
        dbgs() << ']';
      }
      assert(TRI->hasRegUnit(I->PhysReg, Unit) && "inverse mapping present");
      break;
    }
    }
  }
  dbgs() << '\n';
  // Check that LiveVirtRegs is the inverse.
  for (const LiveReg &LR : LiveVirtRegs) {
    Register VirtReg = LR.VirtReg;
    assert(VirtReg.isVirtual() && "Bad map key");
    MCPhysReg PhysReg = LR.PhysReg;
    if (PhysReg != 0) {
      assert(Register::isPhysicalRegister(PhysReg) && "mapped to physreg");
      for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
        assert(RegUnitStates[Unit] == VirtReg && "inverse map valid");
      }
    }
  }
}
#endif

/// Count number of defs consumed from each register class by \p Reg
void RegAllocFastImpl::addRegClassDefCounts(
    MutableArrayRef<unsigned> RegClassDefCounts, Register Reg) const { … }

/// Compute \ref DefOperandIndexes so it contains the indices of "def" operands
/// that are to be allocated. Those are ordered in a way that small classes,
/// early clobbers and livethroughs are allocated first.
void RegAllocFastImpl::findAndSortDefOperandIndexes(const MachineInstr &MI) { … }

// Returns true if MO is tied and the operand it's tied to is not Undef (not
// Undef is not the same thing as Def).
static bool isTiedToNotUndef(const MachineOperand &MO) { … }

void RegAllocFastImpl::allocateInstruction(MachineInstr &MI) { … }

void RegAllocFastImpl::handleDebugValue(MachineInstr &MI) { … }

void RegAllocFastImpl::handleBundle(MachineInstr &MI) { … }

void RegAllocFastImpl::allocateBasicBlock(MachineBasicBlock &MBB) { … }

bool RegAllocFastImpl::runOnMachineFunction(MachineFunction &MF) { … }

PreservedAnalyses RegAllocFastPass::run(MachineFunction &MF,
                                        MachineFunctionAnalysisManager &) { … }

void RegAllocFastPass::printPipeline(
    raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { … }

FunctionPass *llvm::createFastRegisterAllocator() { … }

FunctionPass *llvm::createFastRegisterAllocator(RegAllocFilterFunc Ftor,
                                                bool ClearVirtRegs) { … }
llvm/llvm/lib/CodeGen/RegAllocFast.cpp
