Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===---- 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