LiveIntervals.cpp | Explore in Territory

//===- LiveIntervals.cpp - Live Interval Analysis -------------------------===//
//
// 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 implements the LiveInterval analysis pass which is used
/// by the Linear Scan Register allocator. This pass linearizes the
/// basic blocks of the function in DFS order and computes live intervals for
/// each virtual and physical register.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalCalc.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBundle.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/StackMaps.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/MC/LaneBitmask.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/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <tuple>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

AnalysisKey LiveIntervalsAnalysis::Key;

LiveIntervalsAnalysis::Result
LiveIntervalsAnalysis::run(MachineFunction &MF,
                           MachineFunctionAnalysisManager &MFAM) { … }

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

char LiveIntervalsWrapperPass::ID = …;
char &llvm::LiveIntervalsID = …;
INITIALIZE_PASS_BEGIN(LiveIntervalsWrapperPass, "liveintervals",
                      "Live Interval Analysis", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)
INITIALIZE_PASS_END(LiveIntervalsWrapperPass, "liveintervals",
                    "Live Interval Analysis", false, false)

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

#ifndef NDEBUG
static cl::opt<bool> EnablePrecomputePhysRegs(
  "precompute-phys-liveness", cl::Hidden,
  cl::desc("Eagerly compute live intervals for all physreg units."));
#else
static bool EnablePrecomputePhysRegs = …;
#endif // NDEBUG

namespace llvm {

cl::opt<bool> UseSegmentSetForPhysRegs(
    "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
    cl::desc(
        "Use segment set for the computation of the live ranges of physregs."));

} // end namespace llvm

void LiveIntervalsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

LiveIntervalsWrapperPass::LiveIntervalsWrapperPass() : … { … }

LiveIntervals::~LiveIntervals() { … }

void LiveIntervals::clear() { … }

void LiveIntervals::analyze(MachineFunction &fn) { … }

void LiveIntervals::print(raw_ostream &OS) const { … }

void LiveIntervals::printInstrs(raw_ostream &OS) const { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {
  printInstrs(dbgs());
}
#endif

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LiveIntervals::dump() const { print(dbgs()); }
#endif

LiveInterval *LiveIntervals::createInterval(Register reg) { … }

/// Compute the live interval of a virtual register, based on defs and uses.
bool LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { … }

void LiveIntervals::computeVirtRegs() { … }

void LiveIntervals::computeRegMasks() { … }

//===----------------------------------------------------------------------===//
//                           Register Unit Liveness
//===----------------------------------------------------------------------===//
//
// Fixed interference typically comes from ABI boundaries: Function arguments
// and return values are passed in fixed registers, and so are exception
// pointers entering landing pads. Certain instructions require values to be
// present in specific registers. That is also represented through fixed
// interference.
//

/// Compute the live range of a register unit, based on the uses and defs of
/// aliasing registers.  The range should be empty, or contain only dead
/// phi-defs from ABI blocks.
void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { … }

/// Precompute the live ranges of any register units that are live-in to an ABI
/// block somewhere. Register values can appear without a corresponding def when
/// entering the entry block or a landing pad.
void LiveIntervals::computeLiveInRegUnits() { … }

static void createSegmentsForValues(LiveRange &LR,
    iterator_range<LiveInterval::vni_iterator> VNIs) { … }

void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,
                                         ShrinkToUsesWorkList &WorkList,
                                         Register Reg, LaneBitmask LaneMask) { … }

bool LiveIntervals::shrinkToUses(LiveInterval *li,
                                 SmallVectorImpl<MachineInstr*> *dead) { … }

bool LiveIntervals::computeDeadValues(LiveInterval &LI,
                                      SmallVectorImpl<MachineInstr*> *dead) { … }

void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, Register Reg) { … }

void LiveIntervals::extendToIndices(LiveRange &LR,
                                    ArrayRef<SlotIndex> Indices,
                                    ArrayRef<SlotIndex> Undefs) { … }

void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
                               SmallVectorImpl<SlotIndex> *EndPoints) { … }

//===----------------------------------------------------------------------===//
// Register allocator hooks.
//

void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { … }

MachineBasicBlock*
LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { … }

bool
LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { … }

float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
                                    const MachineBlockFrequencyInfo *MBFI,
                                    const MachineInstr &MI) { … }

float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
                                    const MachineBlockFrequencyInfo *MBFI,
                                    const MachineBasicBlock *MBB) { … }

LiveRange::Segment
LiveIntervals::addSegmentToEndOfBlock(Register Reg, MachineInstr &startInst) { … }

//===----------------------------------------------------------------------===//
//                          Register mask functions
//===----------------------------------------------------------------------===//
/// Check whether use of reg in MI is live-through. Live-through means that
/// the value is alive on exit from Machine instruction. The example of such
/// use is a deopt value in statepoint instruction.
static bool hasLiveThroughUse(const MachineInstr *MI, Register Reg) { … }

bool LiveIntervals::checkRegMaskInterference(const LiveInterval &LI,
                                             BitVector &UsableRegs) { … }

//===----------------------------------------------------------------------===//
//                         IntervalUpdate class.
//===----------------------------------------------------------------------===//

/// Toolkit used by handleMove to trim or extend live intervals.
class LiveIntervals::HMEditor { … };

void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) { … }

void LiveIntervals::handleMoveIntoNewBundle(MachineInstr &BundleStart,
                                            bool UpdateFlags) { … }

void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
                                        const MachineBasicBlock::iterator End,
                                        const SlotIndex EndIdx, LiveRange &LR,
                                        const Register Reg,
                                        LaneBitmask LaneMask) { … }

void
LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
                                      MachineBasicBlock::iterator Begin,
                                      MachineBasicBlock::iterator End,
                                      ArrayRef<Register> OrigRegs) { … }

void LiveIntervals::removePhysRegDefAt(MCRegister Reg, SlotIndex Pos) { … }

void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) { … }

void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
    SmallVectorImpl<LiveInterval*> &SplitLIs) { … }

void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) { … }
llvm/llvm/lib/CodeGen/LiveIntervals.cpp
