//===---- MachineOutliner.h - Outliner data structures ------*- 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
//
//===----------------------------------------------------------------------===//
///
/// \file
/// Contains all data structures shared between the outliner implemented in
/// MachineOutliner.cpp and target implementations of the outliner.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_MACHINEOUTLINER_H
#define LLVM_CODEGEN_MACHINEOUTLINER_H

#include "llvm/CodeGen/LiveRegUnits.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include <initializer_list>

namespace llvm {
namespace outliner {

/// Represents how an instruction should be mapped by the outliner.
/// \p Legal instructions are those which are safe to outline.
/// \p LegalTerminator instructions are safe to outline, but only as the
/// last instruction in a sequence.
/// \p Illegal instructions are those which cannot be outlined.
/// \p Invisible instructions are instructions which can be outlined, but
/// shouldn't actually impact the outlining result.
enum InstrType { Legal, LegalTerminator, Illegal, Invisible };

/// An individual sequence of instructions to be replaced with a call to
/// an outlined function.
struct Candidate {
private:
  /// The start index of this \p Candidate in the instruction list.
  unsigned StartIdx = 0;

  /// The number of instructions in this \p Candidate.
  unsigned Len = 0;

  // The first instruction in this \p Candidate.
  MachineBasicBlock::iterator FirstInst;

  // The last instruction in this \p Candidate.
  MachineBasicBlock::iterator LastInst;

  // The basic block that contains this Candidate.
  MachineBasicBlock *MBB = nullptr;

  /// Cost of calling an outlined function from this point as defined by the
  /// target.
  unsigned CallOverhead = 0;

  /// Liveness information for this Candidate. Tracks from the end of the
  /// block containing this Candidate to the beginning of its sequence.
  ///
  /// Optional. Can be used to fine-tune the cost model, or fine-tune legality
  /// decisions.
  LiveRegUnits FromEndOfBlockToStartOfSeq;

  /// Liveness information restricted to this Candidate's instruction sequence.
  ///
  /// Optional. Can be used to fine-tune the cost model, or fine-tune legality
  /// decisions.
  LiveRegUnits InSeq;

  /// True if FromEndOfBlockToStartOfSeq has been initialized.
  bool FromEndOfBlockToStartOfSeqWasSet = false;

  /// True if InSeq has been initialized.
  bool InSeqWasSet = false;

  /// Populate FromEndOfBlockToStartOfSeq with liveness information.
  void initFromEndOfBlockToStartOfSeq(const TargetRegisterInfo &TRI) {
    assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
           "Candidate's Machine Function must track liveness");
    // Only initialize once.
    if (FromEndOfBlockToStartOfSeqWasSet)
      return;
    FromEndOfBlockToStartOfSeqWasSet = true;
    FromEndOfBlockToStartOfSeq.init(TRI);
    FromEndOfBlockToStartOfSeq.addLiveOuts(*MBB);
    // Compute liveness from the end of the block up to the beginning of the
    // outlining candidate.
    for (auto &MI : make_range(MBB->rbegin(),
                               (MachineBasicBlock::reverse_iterator)front()))
      FromEndOfBlockToStartOfSeq.stepBackward(MI);
  }

  /// Populate InSeq with liveness information.
  void initInSeq(const TargetRegisterInfo &TRI) {
    assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
           "Candidate's Machine Function must track liveness");
    // Only initialize once.
    if (InSeqWasSet)
      return;
    InSeqWasSet = true;
    InSeq.init(TRI);
    for (auto &MI : make_range(front(), std::next(back())))
      InSeq.accumulate(MI);
  }

public:
  /// The index of this \p Candidate's \p OutlinedFunction in the list of
  /// \p OutlinedFunctions.
  unsigned FunctionIdx = 0;

  /// Identifier denoting the instructions to emit to call an outlined function
  /// from this point. Defined by the target.
  unsigned CallConstructionID = 0;

  /// Target-specific flags for this Candidate's MBB.
  unsigned Flags = 0x0;

  /// Return the number of instructions in this Candidate.
  unsigned getLength() const { return Len; }

  /// Return the start index of this candidate.
  unsigned getStartIdx() const { return StartIdx; }

  /// Return the end index of this candidate.
  unsigned getEndIdx() const { return StartIdx + Len - 1; }

  /// Set the CallConstructionID and CallOverhead of this candidate to CID and
  /// CO respectively.
  void setCallInfo(unsigned CID, unsigned CO) {
    CallConstructionID = CID;
    CallOverhead = CO;
  }

  /// Returns the call overhead of this candidate if it is in the list.
  unsigned getCallOverhead() const { return CallOverhead; }

  MachineBasicBlock::iterator &front() { return FirstInst; }
  MachineBasicBlock::iterator &back() { return LastInst; }
  MachineFunction *getMF() const { return MBB->getParent(); }
  MachineBasicBlock *getMBB() const { return MBB; }

  /// \returns True if \p Reg is available from the end of the block to the
  /// beginning of the sequence.
  ///
  /// This query considers the following range:
  ///
  /// in_seq_1
  /// in_seq_2
  /// ...
  /// in_seq_n
  /// not_in_seq_1
  /// ...
  /// <end of block>
  bool isAvailableAcrossAndOutOfSeq(Register Reg,
                                    const TargetRegisterInfo &TRI) {
    if (!FromEndOfBlockToStartOfSeqWasSet)
      initFromEndOfBlockToStartOfSeq(TRI);
    return FromEndOfBlockToStartOfSeq.available(Reg);
  }

  /// \returns True if `isAvailableAcrossAndOutOfSeq` fails for any register
  /// in \p Regs.
  bool isAnyUnavailableAcrossOrOutOfSeq(std::initializer_list<Register> Regs,
                                        const TargetRegisterInfo &TRI) {
    if (!FromEndOfBlockToStartOfSeqWasSet)
      initFromEndOfBlockToStartOfSeq(TRI);
    return any_of(Regs, [&](Register Reg) {
      return !FromEndOfBlockToStartOfSeq.available(Reg);
    });
  }

  /// \returns True if \p Reg is available within the sequence itself.
  ///
  /// This query considers the following range:
  ///
  /// in_seq_1
  /// in_seq_2
  /// ...
  /// in_seq_n
  bool isAvailableInsideSeq(Register Reg, const TargetRegisterInfo &TRI) {
    if (!InSeqWasSet)
      initInSeq(TRI);
    return InSeq.available(Reg);
  }

  /// The number of instructions that would be saved by outlining every
  /// candidate of this type.
  ///
  /// This is a fixed value which is not updated during the candidate pruning
  /// process. It is only used for deciding which candidate to keep if two
  /// candidates overlap. The true benefit is stored in the OutlinedFunction
  /// for some given candidate.
  unsigned Benefit = 0;

  Candidate(unsigned StartIdx, unsigned Len,
            MachineBasicBlock::iterator &FirstInst,
            MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB,
            unsigned FunctionIdx, unsigned Flags)
      : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
        MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
  Candidate() = default;

  /// Used to ensure that \p Candidates are outlined in an order that
  /// preserves the start and end indices of other \p Candidates.
  bool operator<(const Candidate &RHS) const {
    return getStartIdx() > RHS.getStartIdx();
  }

};

/// The information necessary to create an outlined function for some
/// class of candidate.
struct OutlinedFunction {

public:
  std::vector<Candidate> Candidates;

  /// The actual outlined function created.
  /// This is initialized after we go through and create the actual function.
  MachineFunction *MF = nullptr;

  /// Represents the size of a sequence in bytes. (Some instructions vary
  /// widely in size, so just counting the instructions isn't very useful.)
  unsigned SequenceSize = 0;

  /// Target-defined overhead of constructing a frame for this function.
  unsigned FrameOverhead = 0;

  /// Target-defined identifier for constructing a frame for this function.
  unsigned FrameConstructionID = 0;

  /// Return the number of candidates for this \p OutlinedFunction.
  unsigned getOccurrenceCount() const { return Candidates.size(); }

  /// Return the number of bytes it would take to outline this
  /// function.
  unsigned getOutliningCost() const {
    unsigned CallOverhead = 0;
    for (const Candidate &C : Candidates)
      CallOverhead += C.getCallOverhead();
    return CallOverhead + SequenceSize + FrameOverhead;
  }

  /// Return the size in bytes of the unoutlined sequences.
  unsigned getNotOutlinedCost() const {
    return getOccurrenceCount() * SequenceSize;
  }

  /// Return the number of instructions that would be saved by outlining
  /// this function.
  unsigned getBenefit() const {
    unsigned NotOutlinedCost = getNotOutlinedCost();
    unsigned OutlinedCost = getOutliningCost();
    return (NotOutlinedCost < OutlinedCost) ? 0
                                            : NotOutlinedCost - OutlinedCost;
  }

  /// Return the number of instructions in this sequence.
  unsigned getNumInstrs() const { return Candidates[0].getLength(); }

  OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize,
                   unsigned FrameOverhead, unsigned FrameConstructionID)
      : Candidates(Candidates), SequenceSize(SequenceSize),
        FrameOverhead(FrameOverhead), FrameConstructionID(FrameConstructionID) {
    const unsigned B = getBenefit();
    for (Candidate &C : Candidates)
      C.Benefit = B;
  }

  OutlinedFunction() = default;
};
} // namespace outliner
} // namespace llvm

#endif