SplitKit.cpp | Explore in Territory

//===- SplitKit.cpp - Toolkit for splitting live ranges -------------------===//
//
// 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 contains the SplitAnalysis class as well as mutator functions for
// live range splitting.
//
//===----------------------------------------------------------------------===//

#include "SplitKit.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.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/DebugLoc.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>
#include <tuple>

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<bool>
    EnableLoopIVHeuristic("enable-split-loopiv-heuristic",
                          cl::desc("Enable loop iv regalloc heuristic"),
                          cl::init(true));

STATISTIC(NumFinished, "Number of splits finished");
STATISTIC(NumSimple,   "Number of splits that were simple");
STATISTIC(NumCopies,   "Number of copies inserted for splitting");
STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");

//===----------------------------------------------------------------------===//
//                     Last Insert Point Analysis
//===----------------------------------------------------------------------===//

InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,
                                         unsigned BBNum)
    : … { … }

SlotIndex
InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,
                                            const MachineBasicBlock &MBB) { … }

MachineBasicBlock::iterator
InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI,
                                            MachineBasicBlock &MBB) { … }

//===----------------------------------------------------------------------===//
//                                 Split Analysis
//===----------------------------------------------------------------------===//

SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
                             const MachineLoopInfo &mli)
    : … { … }

void SplitAnalysis::clear() { … }

/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
void SplitAnalysis::analyzeUses() { … }

/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
/// where CurLI is live.
void SplitAnalysis::calcLiveBlockInfo() { … }

unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { … }

bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { … }

void SplitAnalysis::analyze(const LiveInterval *li) { … }

//===----------------------------------------------------------------------===//
//                               Split Editor
//===----------------------------------------------------------------------===//

/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
SplitEditor::SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM,
                         MachineDominatorTree &MDT,
                         MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI)
    : … { … }

void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void SplitEditor::dump() const {
  if (RegAssign.empty()) {
    dbgs() << " empty\n";
    return;
  }

  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
    dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
  dbgs() << '\n';
}
#endif

/// Find a subrange corresponding to the exact lane mask @p LM in the live
/// interval @p LI. The interval @p LI is assumed to contain such a subrange.
/// This function is used to find corresponding subranges between the
/// original interval and the new intervals.
template <typename T> auto &getSubrangeImpl(LaneBitmask LM, T &LI) { … }

LiveInterval::SubRange &getSubRangeForMaskExact(LaneBitmask LM,
                                                LiveInterval &LI) { … }

const LiveInterval::SubRange &getSubRangeForMaskExact(LaneBitmask LM,
                                                      const LiveInterval &LI) { … }

/// Find a subrange corresponding to the lane mask @p LM, or a superset of it,
/// in the live interval @p LI. The interval @p LI is assumed to contain such
/// a subrange.  This function is used to find corresponding subranges between
/// the original interval and the new intervals.
const LiveInterval::SubRange &getSubRangeForMask(LaneBitmask LM,
                                                 const LiveInterval &LI) { … }

void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) { … }

VNInfo *SplitEditor::defValue(unsigned RegIdx,
                              const VNInfo *ParentVNI,
                              SlotIndex Idx,
                              bool Original) { … }

void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) { … }

SlotIndex SplitEditor::buildSingleSubRegCopy(
    Register FromReg, Register ToReg, MachineBasicBlock &MBB,
    MachineBasicBlock::iterator InsertBefore, unsigned SubIdx,
    LiveInterval &DestLI, bool Late, SlotIndex Def, const MCInstrDesc &Desc) { … }

SlotIndex SplitEditor::buildCopy(Register FromReg, Register ToReg,
    LaneBitmask LaneMask, MachineBasicBlock &MBB,
    MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) { … }

VNInfo *SplitEditor::defFromParent(unsigned RegIdx, const VNInfo *ParentVNI,
                                   SlotIndex UseIdx, MachineBasicBlock &MBB,
                                   MachineBasicBlock::iterator I) { … }

/// Create a new virtual register and live interval.
unsigned SplitEditor::openIntv() { … }

void SplitEditor::selectIntv(unsigned Idx) { … }

SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { … }

SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { … }

SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { … }

/// useIntv - indicate that all instructions in MBB should use OpenLI.
void SplitEditor::useIntv(const MachineBasicBlock &MBB) { … }

void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { … }

SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { … }

SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { … }

SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { … }

static bool hasTiedUseOf(MachineInstr &MI, unsigned Reg) { … }

void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { … }

//===----------------------------------------------------------------------===//
//                                  Spill modes
//===----------------------------------------------------------------------===//

void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) { … }

MachineBasicBlock*
SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
                                  MachineBasicBlock *DefMBB) { … }

void SplitEditor::computeRedundantBackCopies(
    DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) { … }

/// For SM_Size mode, find a common dominator for all the back-copies for
/// the same ParentVNI and hoist the backcopies to the dominator BB.
/// For SM_Speed mode, if the common dominator is hot and it is not beneficial
/// to do the hoisting, simply remove the dominated backcopies for the same
/// ParentVNI.
void SplitEditor::hoistCopies() { … }

/// transferValues - Transfer all possible values to the new live ranges.
/// Values that were rematerialized are left alone, they need LICalc.extend().
bool SplitEditor::transferValues() { … }

static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) { … }

void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC,
                                 LiveRange &LR, LaneBitmask LM,
                                 ArrayRef<SlotIndex> Undefs) { … }

void SplitEditor::extendPHIKillRanges() { … }

/// rewriteAssigned - Rewrite all uses of Edit->getReg().
void SplitEditor::rewriteAssigned(bool ExtendRanges) { … }

void SplitEditor::deleteRematVictims() { … }

void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) { … }

void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { … }

//===----------------------------------------------------------------------===//
//                            Single Block Splitting
//===----------------------------------------------------------------------===//

bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI,
                                           bool SingleInstrs) const { … }

void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { … }

//===----------------------------------------------------------------------===//
//                    Global Live Range Splitting Support
//===----------------------------------------------------------------------===//

// These methods support a method of global live range splitting that uses a
// global algorithm to decide intervals for CFG edges. They will insert split
// points and color intervals in basic blocks while avoiding interference.
//
// Note that splitSingleBlock is also useful for blocks where both CFG edges
// are on the stack.

void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,
                                        unsigned IntvIn, SlotIndex LeaveBefore,
                                        unsigned IntvOut, SlotIndex EnterAfter){ … }

void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
                                  unsigned IntvIn, SlotIndex LeaveBefore) { … }

void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
                                   unsigned IntvOut, SlotIndex EnterAfter) { … }

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

void SplitAnalysis::BlockInfo::dump() const { … }
llvm/llvm/lib/CodeGen/SplitKit.cpp
