LiveInterval.cpp | Explore in Territory

//===- LiveInterval.cpp - Live Interval Representation --------------------===//
//
// 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 implements the LiveRange and LiveInterval classes.  Given some
// numbering of each the machine instructions an interval [i, j) is said to be a
// live range for register v if there is no instruction with number j' >= j
// such that v is live at j' and there is no instruction with number i' < i such
// that v is live at i'. In this implementation ranges can have holes,
// i.e. a range might look like [1,20), [50,65), [1000,1001).  Each
// individual segment is represented as an instance of LiveRange::Segment,
// and the whole range is represented as an instance of LiveRange.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/LiveInterval.h"
#include "LiveRangeUtils.h"
#include "RegisterCoalescer.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <utility>

usingnamespacellvm;

namespace {

//===----------------------------------------------------------------------===//
// Implementation of various methods necessary for calculation of live ranges.
// The implementation of the methods abstracts from the concrete type of the
// segment collection.
//
// Implementation of the class follows the Template design pattern. The base
// class contains generic algorithms that call collection-specific methods,
// which are provided in concrete subclasses. In order to avoid virtual calls
// these methods are provided by means of C++ template instantiation.
// The base class calls the methods of the subclass through method impl(),
// which casts 'this' pointer to the type of the subclass.
//
//===----------------------------------------------------------------------===//

template <typename ImplT, typename IteratorT, typename CollectionT>
class CalcLiveRangeUtilBase { … };

//===----------------------------------------------------------------------===//
//   Instantiation of the methods for calculation of live ranges
//   based on a segment vector.
//===----------------------------------------------------------------------===//

class CalcLiveRangeUtilVector;
CalcLiveRangeUtilVectorBase;

class CalcLiveRangeUtilVector : public CalcLiveRangeUtilVectorBase { … };

//===----------------------------------------------------------------------===//
//   Instantiation of the methods for calculation of live ranges
//   based on a segment set.
//===----------------------------------------------------------------------===//

class CalcLiveRangeUtilSet;
CalcLiveRangeUtilSetBase;

class CalcLiveRangeUtilSet : public CalcLiveRangeUtilSetBase { … };

} // end anonymous namespace

//===----------------------------------------------------------------------===//
//   LiveRange methods
//===----------------------------------------------------------------------===//

LiveRange::iterator LiveRange::find(SlotIndex Pos) { … }

VNInfo *LiveRange::createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc) { … }

VNInfo *LiveRange::createDeadDef(VNInfo *VNI) { … }

// overlaps - Return true if the intersection of the two live ranges is
// not empty.
//
// An example for overlaps():
//
// 0: A = ...
// 4: B = ...
// 8: C = A + B ;; last use of A
//
// The live ranges should look like:
//
// A = [3, 11)
// B = [7, x)
// C = [11, y)
//
// A->overlaps(C) should return false since we want to be able to join
// A and C.
//
bool LiveRange::overlapsFrom(const LiveRange& other,
                             const_iterator StartPos) const { … }

bool LiveRange::overlaps(const LiveRange &Other, const CoalescerPair &CP,
                         const SlotIndexes &Indexes) const { … }

/// overlaps - Return true if the live range overlaps an interval specified
/// by [Start, End).
bool LiveRange::overlaps(SlotIndex Start, SlotIndex End) const { … }

bool LiveRange::covers(const LiveRange &Other) const { … }

/// ValNo is dead, remove it.  If it is the largest value number, just nuke it
/// (and any other deleted values neighboring it), otherwise mark it as ~1U so
/// it can be nuked later.
void LiveRange::markValNoForDeletion(VNInfo *ValNo) { … }

/// RenumberValues - Renumber all values in order of appearance and delete the
/// remaining unused values.
void LiveRange::RenumberValues() { … }

void LiveRange::addSegmentToSet(Segment S) { … }

LiveRange::iterator LiveRange::addSegment(Segment S) { … }

void LiveRange::append(const Segment S) { … }

std::pair<VNInfo*,bool> LiveRange::extendInBlock(ArrayRef<SlotIndex> Undefs,
    SlotIndex StartIdx, SlotIndex Kill) { … }

VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { … }

void LiveRange::removeSegment(SlotIndex Start, SlotIndex End,
                              bool RemoveDeadValNo) { … }

LiveRange::iterator LiveRange::removeSegment(iterator I, bool RemoveDeadValNo) { … }

void LiveRange::removeValNoIfDead(VNInfo *ValNo) { … }

/// removeValNo - Remove all the segments defined by the specified value#.
/// Also remove the value# from value# list.
void LiveRange::removeValNo(VNInfo *ValNo) { … }

void LiveRange::join(LiveRange &Other,
                     const int *LHSValNoAssignments,
                     const int *RHSValNoAssignments,
                     SmallVectorImpl<VNInfo *> &NewVNInfo) { … }

/// Merge all of the segments in RHS into this live range as the specified
/// value number.  The segments in RHS are allowed to overlap with segments in
/// the current range, but only if the overlapping segments have the
/// specified value number.
void LiveRange::MergeSegmentsInAsValue(const LiveRange &RHS,
                                       VNInfo *LHSValNo) { … }

/// MergeValueInAsValue - Merge all of the live segments of a specific val#
/// in RHS into this live range as the specified value number.
/// The segments in RHS are allowed to overlap with segments in the
/// current range, it will replace the value numbers of the overlaped
/// segments with the specified value number.
void LiveRange::MergeValueInAsValue(const LiveRange &RHS,
                                    const VNInfo *RHSValNo,
                                    VNInfo *LHSValNo) { … }

/// MergeValueNumberInto - This method is called when two value nubmers
/// are found to be equivalent.  This eliminates V1, replacing all
/// segments with the V1 value number with the V2 value number.  This can
/// cause merging of V1/V2 values numbers and compaction of the value space.
VNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { … }

void LiveRange::flushSegmentSet() { … }

bool LiveRange::isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const { … }

void LiveInterval::freeSubRange(SubRange *S) { … }

void LiveInterval::removeEmptySubRanges() { … }

void LiveInterval::clearSubRanges() { … }

/// For each VNI in \p SR, check whether or not that value defines part
/// of the mask describe by \p LaneMask and if not, remove that value
/// from \p SR.
static void stripValuesNotDefiningMask(unsigned Reg, LiveInterval::SubRange &SR,
                                       LaneBitmask LaneMask,
                                       const SlotIndexes &Indexes,
                                       const TargetRegisterInfo &TRI,
                                       unsigned ComposeSubRegIdx) { … }

void LiveInterval::refineSubRanges(
    BumpPtrAllocator &Allocator, LaneBitmask LaneMask,
    std::function<void(LiveInterval::SubRange &)> Apply,
    const SlotIndexes &Indexes, const TargetRegisterInfo &TRI,
    unsigned ComposeSubRegIdx) { … }

unsigned LiveInterval::getSize() const { … }

void LiveInterval::computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs,
                                         LaneBitmask LaneMask,
                                         const MachineRegisterInfo &MRI,
                                         const SlotIndexes &Indexes) const { … }

raw_ostream& llvm::operator<<(raw_ostream& OS, const LiveRange::Segment &S) { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LiveRange::Segment::dump() const {
  dbgs() << *this << '\n';
}
#endif

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

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

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

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LiveRange::dump() const {
  dbgs() << *this << '\n';
}

LLVM_DUMP_METHOD void LiveInterval::SubRange::dump() const {
  dbgs() << *this << '\n';
}

LLVM_DUMP_METHOD void LiveInterval::dump() const {
  dbgs() << *this << '\n';
}
#endif

#ifndef NDEBUG
bool LiveRange::verify() const {
  for (const_iterator I = begin(), E = end(); I != E; ++I) {
    if (!I->start.isValid())
      return false;
    if (!I->end.isValid())
      return false;
    if (I->start >= I->end)
      return false;
    if (I->valno == nullptr)
      return false;
    if (I->valno->id >= valnos.size())
      return false;
    if (I->valno != valnos[I->valno->id])
      return false;
    if (std::next(I) != E) {
      if (I->end > std::next(I)->start)
        return false;
      if (I->end == std::next(I)->start) {
        if (I->valno == std::next(I)->valno)
          return false;
      }
    }
  }

  return true;
}

bool LiveInterval::verify(const MachineRegisterInfo *MRI) const {
  if (!super::verify())
    return false;

  // Make sure SubRanges are fine and LaneMasks are disjunct.
  LaneBitmask Mask;
  LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg())
                                       : LaneBitmask::getAll();
  for (const SubRange &SR : subranges()) {
    // Subrange lanemask should be disjunct to any previous subrange masks.
    if ((Mask & SR.LaneMask).any())
      return false;

    Mask |= SR.LaneMask;

    // subrange mask should not contained in maximum lane mask for the vreg.
    if ((Mask & ~MaxMask).any())
      return false;

    // empty subranges must be removed.
    if (SR.empty())
      return false;

    if (!SR.verify())
      return false;

    // Main liverange should cover subrange.
    if (!covers(SR))
      return false;
  }

  return true;
}
#endif

//===----------------------------------------------------------------------===//
//                           LiveRangeUpdater class
//===----------------------------------------------------------------------===//
//
// The LiveRangeUpdater class always maintains these invariants:
//
// - When LastStart is invalid, Spills is empty and the iterators are invalid.
//   This is the initial state, and the state created by flush().
//   In this state, isDirty() returns false.
//
// Otherwise, segments are kept in three separate areas:
//
// 1. [begin; WriteI) at the front of LR.
// 2. [ReadI; end) at the back of LR.
// 3. Spills.
//
// - LR.begin() <= WriteI <= ReadI <= LR.end().
// - Segments in all three areas are fully ordered and coalesced.
// - Segments in area 1 precede and can't coalesce with segments in area 2.
// - Segments in Spills precede and can't coalesce with segments in area 2.
// - No coalescing is possible between segments in Spills and segments in area
//   1, and there are no overlapping segments.
//
// The segments in Spills are not ordered with respect to the segments in area
// 1. They need to be merged.
//
// When they exist, Spills.back().start <= LastStart,
//                 and WriteI[-1].start <= LastStart.

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void LiveRangeUpdater::print(raw_ostream &OS) const {
  if (!isDirty()) {
    if (LR)
      OS << "Clean updater: " << *LR << '\n';
    else
      OS << "Null updater.\n";
    return;
  }
  assert(LR && "Can't have null LR in dirty updater.");
  OS << " updater with gap = " << (ReadI - WriteI)
     << ", last start = " << LastStart
     << ":\n  Area 1:";
  for (const auto &S : make_range(LR->begin(), WriteI))
    OS << ' ' << S;
  OS << "\n  Spills:";
  for (unsigned I = 0, E = Spills.size(); I != E; ++I)
    OS << ' ' << Spills[I];
  OS << "\n  Area 2:";
  for (const auto &S : make_range(ReadI, LR->end()))
    OS << ' ' << S;
  OS << '\n';
}

LLVM_DUMP_METHOD void LiveRangeUpdater::dump() const {
  print(errs());
}
#endif

// Determine if A and B should be coalesced.
static inline bool coalescable(const LiveRange::Segment &A,
                               const LiveRange::Segment &B) { … }

void LiveRangeUpdater::add(LiveRange::Segment Seg) { … }

// Merge as many spilled segments as possible into the gap between WriteI
// and ReadI. Advance WriteI to reflect the inserted instructions.
void LiveRangeUpdater::mergeSpills() { … }

void LiveRangeUpdater::flush() { … }

unsigned ConnectedVNInfoEqClasses::Classify(const LiveRange &LR) { … }

void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[],
                                          MachineRegisterInfo &MRI) { … }
llvm/llvm/lib/CodeGen/LiveInterval.cpp
