llvm/llvm/include/llvm/CodeGen/LiveInterval.h

//===- llvm/CodeGen/LiveInterval.h - Interval representation ----*- C++ -*-===//
//
// 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.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_LIVEINTERVAL_H
#define LLVM_CODEGEN_LIVEINTERVAL_H

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/IntEqClasses.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/CodeGen/Register.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/MathExtras.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <memory>
#include <set>
#include <tuple>
#include <utility>

namespace llvm {

  class CoalescerPair;
  class LiveIntervals;
  class MachineRegisterInfo;
  class raw_ostream;

  /// VNInfo - Value Number Information.
  /// This class holds information about a machine level values, including
  /// definition and use points.
  ///
  class VNInfo { … };

  /// Result of a LiveRange query. This class hides the implementation details
  /// of live ranges, and it should be used as the primary interface for
  /// examining live ranges around instructions.
  class LiveQueryResult { … };

  /// This class represents the liveness of a register, stack slot, etc.
  /// It manages an ordered list of Segment objects.
  /// The Segments are organized in a static single assignment form: At places
  /// where a new value is defined or different values reach a CFG join a new
  /// segment with a new value number is used.
  class LiveRange { … };

  inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { … }

  /// LiveInterval - This class represents the liveness of a register,
  /// or stack slot.
  class LiveInterval : public LiveRange { … };

  inline raw_ostream &operator<<(raw_ostream &OS,
                                 const LiveInterval::SubRange &SR) { … }

  inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { … }

  raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S);

  inline bool operator<(SlotIndex V, const LiveRange::Segment &S) { … }

  inline bool operator<(const LiveRange::Segment &S, SlotIndex V) { … }

  /// Helper class for performant LiveRange bulk updates.
  ///
  /// Calling LiveRange::addSegment() repeatedly can be expensive on large
  /// live ranges because segments after the insertion point may need to be
  /// shifted. The LiveRangeUpdater class can defer the shifting when adding
  /// many segments in order.
  ///
  /// The LiveRange will be in an invalid state until flush() is called.
  class LiveRangeUpdater { … };

  inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) { … }

  /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a
  /// LiveInterval into equivalence clases of connected components. A
  /// LiveInterval that has multiple connected components can be broken into
  /// multiple LiveIntervals.
  ///
  /// Given a LiveInterval that may have multiple connected components, run:
  ///
  ///   unsigned numComps = ConEQ.Classify(LI);
  ///   if (numComps > 1) {
  ///     // allocate numComps-1 new LiveIntervals into LIS[1..]
  ///     ConEQ.Distribute(LIS);
  /// }

  class ConnectedVNInfoEqClasses { … };

} // end namespace llvm

#endif // LLVM_CODEGEN_LIVEINTERVAL_H