File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/CodeGen

usr / src / contrib / llvm-project / llvm / lib / CodeGen /

📁 ..
📄 AggressiveAntiDepBreaker.cpp(37.23 KB)
📄 AggressiveAntiDepBreaker.h(6.8 KB)
📄 AllocationOrder.cpp(1.96 KB)
📄 AllocationOrder.h(2.96 KB)
📄 Analysis.cpp(32.62 KB)
📁 AsmPrinter
📄 AtomicExpandPass.cpp(71.86 KB)
📄 BBSectionsPrepare.cpp(18.8 KB)
📄 BasicTargetTransformInfo.cpp(1.53 KB)
📄 BranchFolding.cpp(77.92 KB)
📄 BranchFolding.h(7.36 KB)
📄 BranchRelaxation.cpp(19.45 KB)
📄 BreakFalseDeps.cpp(9.79 KB)
📄 BuiltinGCs.cpp(4.88 KB)
📄 CFGuardLongjmp.cpp(3.73 KB)
📄 CFIInstrInserter.cpp(17.53 KB)
📄 CalcSpillWeights.cpp(10.22 KB)
📄 CallingConvLower.cpp(10.4 KB)
📄 CodeGen.cpp(5.28 KB)
📄 CodeGenPrepare.cpp(295.01 KB)
📄 CommandFlags.cpp(24.89 KB)
📄 CriticalAntiDepBreaker.cpp(27.91 KB)
📄 CriticalAntiDepBreaker.h(4.22 KB)
📄 DFAPacketizer.cpp(10.91 KB)
📄 DeadMachineInstructionElim.cpp(6.52 KB)
📄 DetectDeadLanes.cpp(20.74 KB)
📄 DwarfEHPrepare.cpp(9.01 KB)
📄 EarlyIfConversion.cpp(37.51 KB)
📄 EdgeBundles.cpp(3.21 KB)
📄 ExecutionDomainFix.cpp(14.67 KB)
📄 ExpandMemCmp.cpp(33.66 KB)
📄 ExpandPostRAPseudos.cpp(7.28 KB)
📄 ExpandReductions.cpp(7.23 KB)
📄 FEntryInserter.cpp(1.81 KB)
📄 FaultMaps.cpp(4.99 KB)
📄 FinalizeISel.cpp(2.65 KB)
📄 FixupStatepointCallerSaved.cpp(11.06 KB)
📄 FuncletLayout.cpp(2.21 KB)
📄 GCMetadata.cpp(5.1 KB)
📄 GCMetadataPrinter.cpp(748 B)
📄 GCRootLowering.cpp(11.46 KB)
📄 GCStrategy.cpp(708 B)
📁 GlobalISel
📄 GlobalMerge.cpp(24.52 KB)
📄 HardwareLoops.cpp(18.44 KB)
📄 IfConversion.cpp(89.43 KB)
📄 ImplicitNullChecks.cpp(25.14 KB)
📄 IndirectBrExpandPass.cpp(7.79 KB)
📄 InlineSpiller.cpp(58.24 KB)
📄 InterferenceCache.cpp(8.83 KB)
📄 InterferenceCache.h(7.22 KB)
📄 InterleavedAccessPass.cpp(16.59 KB)
📄 InterleavedLoadCombinePass.cpp(42.35 KB)
📄 IntrinsicLowering.cpp(17.08 KB)
📄 LLVMTargetMachine.cpp(10.25 KB)
📄 LatencyPriorityQueue.cpp(5.64 KB)
📄 LazyMachineBlockFrequencyInfo.cpp(3.36 KB)
📄 LexicalScopes.cpp(12.16 KB)
📄 LiveDebugValues.cpp(78.98 KB)
📄 LiveDebugVariables.cpp(51.79 KB)
📄 LiveDebugVariables.h(2.15 KB)
📄 LiveInterval.cpp(46.67 KB)
📄 LiveIntervalCalc.cpp(7.62 KB)
📄 LiveIntervalUnion.cpp(6.36 KB)
📄 LiveIntervals.cpp(64.59 KB)
📄 LivePhysRegs.cpp(11.08 KB)
📄 LiveRangeCalc.cpp(15.72 KB)
📄 LiveRangeEdit.cpp(17.03 KB)
📄 LiveRangeShrink.cpp(8.69 KB)
📄 LiveRangeUtils.h(2.12 KB)
📄 LiveRegMatrix.cpp(7.47 KB)
📄 LiveRegUnits.cpp(4.72 KB)
📄 LiveStacks.cpp(2.95 KB)
📄 LiveVariables.cpp(30.26 KB)
📄 LocalStackSlotAllocation.cpp(17.26 KB)
📄 LoopTraversal.cpp(2.89 KB)
📄 LowLevelType.cpp(1.93 KB)
📄 LowerEmuTLS.cpp(5.66 KB)
📄 MBFIWrapper.cpp(1.57 KB)
📄 MIRCanonicalizerPass.cpp(12.46 KB)
📄 MIRNamerPass.cpp(2.16 KB)
📁 MIRParser
📄 MIRPrinter.cpp(32.67 KB)
📄 MIRPrintingPass.cpp(1.99 KB)
📄 MIRVRegNamerUtils.cpp(6.04 KB)
📄 MIRVRegNamerUtils.h(3.25 KB)
📄 MachineBasicBlock.cpp(50.47 KB)
📄 MachineBlockFrequencyInfo.cpp(10.13 KB)
📄 MachineBlockPlacement.cpp(137.61 KB)
📄 MachineBranchProbabilityInfo.cpp(3.5 KB)
📄 MachineCSE.cpp(31.82 KB)
📄 MachineCombiner.cpp(28.13 KB)
📄 MachineCopyPropagation.cpp(29.21 KB)
📄 MachineDebugify.cpp(6.47 KB)
📄 MachineDominanceFrontier.cpp(1.83 KB)
📄 MachineDominators.cpp(4.86 KB)
📄 MachineFrameInfo.cpp(9.77 KB)
📄 MachineFunction.cpp(42.97 KB)
📄 MachineFunctionPass.cpp(4.78 KB)
📄 MachineFunctionPrinterPass.cpp(2.3 KB)
📄 MachineInstr.cpp(76.39 KB)
📄 MachineInstrBundle.cpp(11.49 KB)
📄 MachineLICM.cpp(57.05 KB)
📄 MachineLoopInfo.cpp(4.98 KB)
📄 MachineLoopUtils.cpp(5.16 KB)
📄 MachineModuleInfo.cpp(9.9 KB)
📄 MachineModuleInfoImpls.cpp(1.5 KB)
📄 MachineOperand.cpp(39.6 KB)
📄 MachineOptimizationRemarkEmitter.cpp(3.29 KB)
📄 MachineOutliner.cpp(42.13 KB)
📄 MachinePipeliner.cpp(111.33 KB)
📄 MachinePostDominators.cpp(2.42 KB)
📄 MachineRegionInfo.cpp(4.75 KB)
📄 MachineRegisterInfo.cpp(22.97 KB)
📄 MachineSSAUpdater.cpp(12.99 KB)
📄 MachineScheduler.cpp(136.89 KB)
📄 MachineSink.cpp(51.94 KB)
📄 MachineSizeOpts.cpp(8.76 KB)
📄 MachineStripDebug.cpp(3.76 KB)
📄 MachineTraceMetrics.cpp(49.58 KB)
📄 MachineVerifier.cpp(107.98 KB)
📄 MacroFusion.cpp(7.55 KB)
📄 ModuloSchedule.cpp(85.09 KB)
📄 NonRelocatableStringpool.cpp(1.65 KB)
📄 OptimizePHIs.cpp(6.7 KB)
📄 PHIElimination.cpp(27.73 KB)
📄 PHIEliminationUtils.cpp(2.56 KB)
📄 PHIEliminationUtils.h(972 B)
📄 ParallelCG.cpp(3.71 KB)
📄 PatchableFunction.cpp(3.44 KB)
📄 PeepholeOptimizer.cpp(78.41 KB)
📄 PostRAHazardRecognizer.cpp(3.5 KB)
📄 PostRASchedulerList.cpp(24.31 KB)
📄 PreISelIntrinsicLowering.cpp(7.91 KB)
📄 ProcessImplicitDefs.cpp(5.4 KB)
📄 PrologEpilogInserter.cpp(50.45 KB)
📄 PseudoSourceValue.cpp(4.71 KB)
📄 RDFGraph.cpp(58.39 KB)
📄 RDFLiveness.cpp(40.7 KB)
📄 RDFRegisters.cpp(11.29 KB)
📄 ReachingDefAnalysis.cpp(21.74 KB)
📄 RegAllocBase.cpp(6.31 KB)
📄 RegAllocBase.h(4.63 KB)
📄 RegAllocBasic.cpp(11.33 KB)
📄 RegAllocFast.cpp(45.78 KB)
📄 RegAllocGreedy.cpp(123.32 KB)
📄 RegAllocPBQP.cpp(33.14 KB)
📄 RegUsageInfoCollector.cpp(7.39 KB)
📄 RegUsageInfoPropagate.cpp(5.07 KB)
📄 RegisterClassInfo.cpp(6.62 KB)
📄 RegisterCoalescer.cpp(151.71 KB)
📄 RegisterCoalescer.h(4.04 KB)
📄 RegisterPressure.cpp(48.86 KB)
📄 RegisterScavenging.cpp(27.48 KB)
📄 RegisterUsageInfo.cpp(3.18 KB)
📄 RenameIndependentSubregs.cpp(14.79 KB)
📄 ResetMachineFunctionPass.cpp(3.48 KB)
📄 SafeStack.cpp(34.12 KB)
📄 SafeStackLayout.cpp(5.3 KB)
📄 SafeStackLayout.h(2.41 KB)
📄 ScalarizeMaskedMemIntrin.cpp(31.46 KB)
📄 ScheduleDAG.cpp(21.34 KB)
📄 ScheduleDAGInstrs.cpp(54.59 KB)
📄 ScheduleDAGPrinter.cpp(3.21 KB)
📄 ScoreboardHazardRecognizer.cpp(7.96 KB)
📁 SelectionDAG
📄 ShadowStackGCLowering.cpp(14.16 KB)
📄 ShrinkWrap.cpp(23.03 KB)
📄 SjLjEHPrepare.cpp(18.93 KB)
📄 SlotIndexes.cpp(9.35 KB)
📄 SpillPlacement.cpp(12.58 KB)
📄 SpillPlacement.h(6.67 KB)
📄 SplitKit.cpp(66.39 KB)
📄 SplitKit.h(23.7 KB)
📄 StackColoring.cpp(49.03 KB)
📄 StackMapLivenessAnalysis.cpp(6.16 KB)
📄 StackMaps.cpp(19.74 KB)
📄 StackProtector.cpp(22.94 KB)
📄 StackSlotColoring.cpp(17.12 KB)
📄 SwiftErrorValueTracking.cpp(11.37 KB)
📄 SwitchLoweringUtils.cpp(18.33 KB)
📄 TailDuplication.cpp(3.32 KB)
📄 TailDuplicator.cpp(38.29 KB)
📄 TargetFrameLoweringImpl.cpp(6.24 KB)
📄 TargetInstrInfo.cpp(51.1 KB)
📄 TargetLoweringBase.cpp(82.53 KB)
📄 TargetLoweringObjectFileImpl.cpp(80.52 KB)
📄 TargetOptionsImpl.cpp(2 KB)
📄 TargetPassConfig.cpp(48.89 KB)
📄 TargetRegisterInfo.cpp(19.15 KB)
📄 TargetSchedule.cpp(13.16 KB)
📄 TargetSubtargetInfo.cpp(1.89 KB)
📄 TwoAddressInstructionPass.cpp(62.08 KB)
📄 TypePromotion.cpp(32.46 KB)
📄 UnreachableBlockElim.cpp(7.48 KB)
📄 ValueTypes.cpp(19.87 KB)
📄 VirtRegMap.cpp(21.4 KB)
📄 WasmEHPrepare.cpp(17.48 KB)
📄 WinEHPrepare.cpp(51.16 KB)
📄 XRayInstrumentation.cpp(9.66 KB)

Editing: RegAllocBasic.cpp

//===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file defines the RABasic function pass, which provides a minimal
// implementation of the basic register allocator.
//
//===----------------------------------------------------------------------===//

#include "AllocationOrder.h"
#include "LiveDebugVariables.h"
#include "RegAllocBase.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/LiveRegMatrix.h"
#include "llvm/CodeGen/LiveStacks.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/Spiller.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cstdlib>
#include <queue>

using namespace llvm;

#define DEBUG_TYPE "regalloc"

static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
                                      createBasicRegisterAllocator);

namespace {
  struct CompSpillWeight {
    bool operator()(LiveInterval *A, LiveInterval *B) const {
      return A->weight < B->weight;
    }
  };
}

namespace {
/// 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 RABasic : public MachineFunctionPass,
                public RegAllocBase,
                private LiveRangeEdit::Delegate {
  // context
  MachineFunction *MF;

// state
  std::unique_ptr<Spiller> SpillerInstance;
  std::priority_queue<LiveInterval*, std::vector<LiveInterval*>,
                      CompSpillWeight> Queue;

// Scratch space.  Allocated here to avoid repeated malloc calls in
  // selectOrSplit().
  BitVector UsableRegs;

bool LRE_CanEraseVirtReg(unsigned) override;
  void LRE_WillShrinkVirtReg(unsigned) override;

public:
  RABasic();

/// 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 enqueue(LiveInterval *LI) override {
    Queue.push(LI);
  }

LiveInterval *dequeue() override {
    if (Queue.empty())
      return nullptr;
    LiveInterval *LI = Queue.top();
    Queue.pop();
    return LI;
  }

/// Perform register allocation.
  bool runOnMachineFunction(MachineFunction &mf) override;

MachineFunctionProperties getRequiredProperties() const override {
    return MachineFunctionProperties().set(
        MachineFunctionProperties::Property::NoPHIs);
  }

// 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(LiveInterval &VirtReg, Register PhysReg,
                          SmallVectorImpl<Register> &SplitVRegs);

static char ID;
};

char RABasic::ID = 0;

} // end anonymous namespace

char &llvm::RABasicID = RABasic::ID;

INITIALIZE_PASS_BEGIN(RABasic, "regallocbasic", "Basic Register Allocator",
                      false, false)
INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer)
INITIALIZE_PASS_DEPENDENCY(MachineScheduler)
INITIALIZE_PASS_DEPENDENCY(LiveStacks)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix)
INITIALIZE_PASS_END(RABasic, "regallocbasic", "Basic Register Allocator", false,
                    false)

bool RABasic::LRE_CanEraseVirtReg(unsigned VirtReg) {
  LiveInterval &LI = LIS->getInterval(VirtReg);
  if (VRM->hasPhys(VirtReg)) {
    Matrix->unassign(LI);
    aboutToRemoveInterval(LI);
    return true;
  }
  // Unassigned virtreg is probably in the priority queue.
  // RegAllocBase will erase it after dequeueing.
  // Nonetheless, clear the live-range so that the debug
  // dump will show the right state for that VirtReg.
  LI.clear();
  return false;
}

void RABasic::LRE_WillShrinkVirtReg(unsigned VirtReg) {
  if (!VRM->hasPhys(VirtReg))
    return;

// Register is assigned, put it back on the queue for reassignment.
  LiveInterval &LI = LIS->getInterval(VirtReg);
  Matrix->unassign(LI);
  enqueue(&LI);
}

RABasic::RABasic(): MachineFunctionPass(ID) {
}

void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesCFG();
  AU.addRequired<AAResultsWrapperPass>();
  AU.addPreserved<AAResultsWrapperPass>();
  AU.addRequired<LiveIntervals>();
  AU.addPreserved<LiveIntervals>();
  AU.addPreserved<SlotIndexes>();
  AU.addRequired<LiveDebugVariables>();
  AU.addPreserved<LiveDebugVariables>();
  AU.addRequired<LiveStacks>();
  AU.addPreserved<LiveStacks>();
  AU.addRequired<MachineBlockFrequencyInfo>();
  AU.addPreserved<MachineBlockFrequencyInfo>();
  AU.addRequiredID(MachineDominatorsID);
  AU.addPreservedID(MachineDominatorsID);
  AU.addRequired<MachineLoopInfo>();
  AU.addPreserved<MachineLoopInfo>();
  AU.addRequired<VirtRegMap>();
  AU.addPreserved<VirtRegMap>();
  AU.addRequired<LiveRegMatrix>();
  AU.addPreserved<LiveRegMatrix>();
  MachineFunctionPass::getAnalysisUsage(AU);
}

void RABasic::releaseMemory() {
  SpillerInstance.reset();
}

// Spill or split all live virtual registers currently unified under PhysReg
// that interfere with VirtReg. The newly spilled or split live intervals are
// returned by appending them to SplitVRegs.
bool RABasic::spillInterferences(LiveInterval &VirtReg, Register PhysReg,
                                 SmallVectorImpl<Register> &SplitVRegs) {
  // Record each interference and determine if all are spillable before mutating
  // either the union or live intervals.
  SmallVector<LiveInterval*, 8> Intfs;

// Collect interferences assigned to any alias of the physical register.
  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
    LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
    Q.collectInterferingVRegs();
    for (unsigned i = Q.interferingVRegs().size(); i; --i) {
      LiveInterval *Intf = Q.interferingVRegs()[i - 1];
      if (!Intf->isSpillable() || Intf->weight > VirtReg.weight)
        return false;
      Intfs.push_back(Intf);
    }
  }
  LLVM_DEBUG(dbgs() << "spilling " << printReg(PhysReg, TRI)
                    << " interferences with " << VirtReg << "\n");
  assert(!Intfs.empty() && "expected interference");

// Spill each interfering vreg allocated to PhysReg or an alias.
  for (unsigned i = 0, e = Intfs.size(); i != e; ++i) {
    LiveInterval &Spill = *Intfs[i];

// Skip duplicates.
    if (!VRM->hasPhys(Spill.reg))
      continue;

// Deallocate the interfering vreg by removing it from the union.
    // A LiveInterval instance may not be in a union during modification!
    Matrix->unassign(Spill);

// Spill the extracted interval.
    LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
    spiller().spill(LRE);
  }
  return true;
}

// Driver for the register assignment and splitting heuristics.
// Manages iteration over the LiveIntervalUnions.
//
// This is a minimal implementation of register assignment and splitting that
// spills whenever we run out of registers.
//
// selectOrSplit can only be called once per live virtual register. We then do a
// single interference test for each register the correct class until we find an
// available register. So, the number of interference tests in the worst case is
// |vregs| * |machineregs|. And since the number of interference tests is
// minimal, there is no value in caching them outside the scope of
// selectOrSplit().
Register RABasic::selectOrSplit(LiveInterval &VirtReg,
                                SmallVectorImpl<Register> &SplitVRegs) {
  // Populate a list of physical register spill candidates.
  SmallVector<Register, 8> PhysRegSpillCands;

// Check for an available register in this class.
  AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
  while (Register PhysReg = Order.next()) {
    // Check for interference in PhysReg
    switch (Matrix->checkInterference(VirtReg, PhysReg)) {
    case LiveRegMatrix::IK_Free:
      // PhysReg is available, allocate it.
      return PhysReg;

case LiveRegMatrix::IK_VirtReg:
      // Only virtual registers in the way, we may be able to spill them.
      PhysRegSpillCands.push_back(PhysReg);
      continue;

default:
      // RegMask or RegUnit interference.
      continue;
    }
  }

// Try to spill another interfering reg with less spill weight.
  for (SmallVectorImpl<Register>::iterator PhysRegI = PhysRegSpillCands.begin(),
       PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
    if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs))
      continue;

assert(!Matrix->checkInterference(VirtReg, *PhysRegI) &&
           "Interference after spill.");
    // Tell the caller to allocate to this newly freed physical register.
    return *PhysRegI;
  }

// No other spill candidates were found, so spill the current VirtReg.
  LLVM_DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
  if (!VirtReg.isSpillable())
    return ~0u;
  LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
  spiller().spill(LRE);

// The live virtual register requesting allocation was spilled, so tell
  // the caller not to allocate anything during this round.
  return 0;
}

bool RABasic::runOnMachineFunction(MachineFunction &mf) {
  LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
                    << "********** Function: " << mf.getName() << '\n');

MF = &mf;
  RegAllocBase::init(getAnalysis<VirtRegMap>(),
                     getAnalysis<LiveIntervals>(),
                     getAnalysis<LiveRegMatrix>());

calculateSpillWeightsAndHints(*LIS, *MF, VRM,
                                getAnalysis<MachineLoopInfo>(),
                                getAnalysis<MachineBlockFrequencyInfo>());

SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));

allocatePhysRegs();
  postOptimization();

// Diagnostic output before rewriting
  LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");

releaseMemory();
  return true;
}

FunctionPass* llvm::createBasicRegisterAllocator()
{
  return new RABasic();
}

003 File Manager

Editing: RegAllocBasic.cpp

Upload File

Create Folder