include/llvm/CodeGen/MachineOutliner.h

   1 //===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// \file
  10 /// Contains all data structures shared between the outliner implemented in
  11 /// MachineOutliner.cpp and target implementations of the outliner.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_MACHINEOUTLINER_H
  16 #define LLVM_MACHINEOUTLINER_H
  17
  18 #include "llvm/CodeGen/LiveRegUnits.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/TargetRegisterInfo.h"
  21 #include "llvm/CodeGen/LivePhysRegs.h"
  22
  23 namespace llvm {
  24 namespace outliner {
  25
  26 /// Represents how an instruction should be mapped by the outliner.
  27 /// \p Legal instructions are those which are safe to outline.
  28 /// \p LegalTerminator instructions are safe to outline, but only as the
  29 /// last instruction in a sequence.
  30 /// \p Illegal instructions are those which cannot be outlined.
  31 /// \p Invisible instructions are instructions which can be outlined, but
  32 /// shouldn't actually impact the outlining result.
  33 enum InstrType { Legal, LegalTerminator, Illegal, Invisible };
  34
  35 /// An individual sequence of instructions to be replaced with a call to
  36 /// an outlined function.
  37 struct Candidate {
  38 private:
  39   /// The start index of this \p Candidate in the instruction list.
  40   unsigned StartIdx;
  41
  42   /// The number of instructions in this \p Candidate.
  43   unsigned Len;
  44
  45   // The first instruction in this \p Candidate.
  46   MachineBasicBlock::iterator FirstInst;
  47
  48   // The last instruction in this \p Candidate.
  49   MachineBasicBlock::iterator LastInst;
  50
  51   // The basic block that contains this Candidate.
  52   MachineBasicBlock *MBB;
  53
  54   /// Cost of calling an outlined function from this point as defined by the
  55   /// target.
  56   unsigned CallOverhead;
  57
  58 public:
  59   /// The index of this \p Candidate's \p OutlinedFunction in the list of
  60   /// \p OutlinedFunctions.
  61   unsigned FunctionIdx;
  62
  63   /// Identifier denoting the instructions to emit to call an outlined function
  64   /// from this point. Defined by the target.
  65   unsigned CallConstructionID;
  66
  67   /// Contains physical register liveness information for the MBB containing
  68   /// this \p Candidate.
  69   ///
  70   /// This is optionally used by the target to calculate more fine-grained
  71   /// cost model information.
  72   LiveRegUnits LRU;
  73
  74   /// Contains the accumulated register liveness information for the
  75   /// instructions in this \p Candidate.
  76   ///
  77   /// This is optionally used by the target to determine which registers have
  78   /// been used across the sequence.
  79   LiveRegUnits UsedInSequence;
  80
  81   /// Target-specific flags for this Candidate's MBB.
  82   unsigned Flags = 0x0;
  83
  84   /// True if initLRU has been called on this Candidate.
  85   bool LRUWasSet = false;
  86
  87   /// Return the number of instructions in this Candidate.
  88   unsigned getLength() const { return Len; }
  89
  90   /// Return the start index of this candidate.
  91   unsigned getStartIdx() const { return StartIdx; }
  92
  93   /// Return the end index of this candidate.
  94   unsigned getEndIdx() const { return StartIdx + Len - 1; }
  95
  96   /// Set the CallConstructionID and CallOverhead of this candidate to CID and
  97   /// CO respectively.
  98   void setCallInfo(unsigned CID, unsigned CO) {
  99     CallConstructionID = CID;
 100     CallOverhead = CO;
 101   }
 102
 103   /// Returns the call overhead of this candidate if it is in the list.
 104   unsigned getCallOverhead() const { return CallOverhead; }
 105
 106   MachineBasicBlock::iterator &front() { return FirstInst; }
 107   MachineBasicBlock::iterator &back() { return LastInst; }
 108   MachineFunction *getMF() const { return MBB->getParent(); }
 109   MachineBasicBlock *getMBB() const { return MBB; }
 110
 111   /// The number of instructions that would be saved by outlining every
 112   /// candidate of this type.
 113   ///
 114   /// This is a fixed value which is not updated during the candidate pruning
 115   /// process. It is only used for deciding which candidate to keep if two
 116   /// candidates overlap. The true benefit is stored in the OutlinedFunction
 117   /// for some given candidate.
 118   unsigned Benefit = 0;
 119
 120   Candidate(unsigned StartIdx, unsigned Len,
 121             MachineBasicBlock::iterator &FirstInst,
 122             MachineBasicBlock::iterator &LastInst, MachineBasicBlock *MBB,
 123             unsigned FunctionIdx, unsigned Flags)
 124       : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
 125         MBB(MBB), FunctionIdx(FunctionIdx), Flags(Flags) {}
 126   Candidate() {}
 127
 128   /// Used to ensure that \p Candidates are outlined in an order that
 129   /// preserves the start and end indices of other \p Candidates.
 130   bool operator<(const Candidate &RHS) const {
 131     return getStartIdx() > RHS.getStartIdx();
 132   }
 133
 134   /// Compute the registers that are live across this Candidate.
 135   /// Used by targets that need this information for cost model calculation.
 136   /// If a target does not need this information, then this should not be
 137   /// called.
 138   void initLRU(const TargetRegisterInfo &TRI) {
 139     assert(MBB->getParent()->getRegInfo().tracksLiveness() &&
 140            "Candidate's Machine Function must track liveness");
 141     // Only initialize once.
 142     if (LRUWasSet)
 143       return;
 144     LRUWasSet = true;
 145     LRU.init(TRI);
 146     LRU.addLiveOuts(*MBB);
 147
 148     // Compute liveness from the end of the block up to the beginning of the
 149     // outlining candidate.
 150     std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(),
 151                   [this](MachineInstr &MI) { LRU.stepBackward(MI); });
 152
 153     // Walk over the sequence itself and figure out which registers were used
 154     // in the sequence.
 155     UsedInSequence.init(TRI);
 156     std::for_each(front(), std::next(back()),
 157                   [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
 158   }
 159 };
 160
 161 /// The information necessary to create an outlined function for some
 162 /// class of candidate.
 163 struct OutlinedFunction {
 164
 165 public:
 166   std::vector<Candidate> Candidates;
 167
 168   /// The actual outlined function created.
 169   /// This is initialized after we go through and create the actual function.
 170   MachineFunction *MF = nullptr;
 171
 172   /// Represents the size of a sequence in bytes. (Some instructions vary
 173   /// widely in size, so just counting the instructions isn't very useful.)
 174   unsigned SequenceSize = 0;
 175
 176   /// Target-defined overhead of constructing a frame for this function.
 177   unsigned FrameOverhead = 0;
 178
 179   /// Target-defined identifier for constructing a frame for this function.
 180   unsigned FrameConstructionID = 0;
 181
 182   /// Return the number of candidates for this \p OutlinedFunction.
 183   unsigned getOccurrenceCount() const { return Candidates.size(); }
 184
 185   /// Return the number of bytes it would take to outline this
 186   /// function.
 187   unsigned getOutliningCost() const {
 188     unsigned CallOverhead = 0;
 189     for (const Candidate &C : Candidates)
 190       CallOverhead += C.getCallOverhead();
 191     return CallOverhead + SequenceSize + FrameOverhead;
 192   }
 193
 194   /// Return the size in bytes of the unoutlined sequences.
 195   unsigned getNotOutlinedCost() const {
 196     return getOccurrenceCount() * SequenceSize;
 197   }
 198
 199   /// Return the number of instructions that would be saved by outlining
 200   /// this function.
 201   unsigned getBenefit() const {
 202     unsigned NotOutlinedCost = getNotOutlinedCost();
 203     unsigned OutlinedCost = getOutliningCost();
 204     return (NotOutlinedCost < OutlinedCost) ? 0
 205                                             : NotOutlinedCost - OutlinedCost;
 206   }
 207
 208   /// Return the number of instructions in this sequence.
 209   unsigned getNumInstrs() const { return Candidates[0].getLength(); }
 210
 211   OutlinedFunction(std::vector<Candidate> &Candidates, unsigned SequenceSize,
 212                    unsigned FrameOverhead, unsigned FrameConstructionID)
 213       : Candidates(Candidates), SequenceSize(SequenceSize),
 214         FrameOverhead(FrameOverhead), FrameConstructionID(FrameConstructionID) {
 215     const unsigned B = getBenefit();
 216     for (Candidate &C : Candidates)
 217       C.Benefit = B;
 218   }
 219
 220   OutlinedFunction() {}
 221 };
 222 } // namespace outliner
 223 } // namespace llvm
 224
 225 #endif