contrib/llvm/include/llvm/CodeGen/MachineOutliner.h

   1 //===---- MachineOutliner.h - Outliner data structures ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// Contains all data structures shared between the outliner implemented in
  12 /// MachineOutliner.cpp and target implementations of the outliner.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_MACHINEOUTLINER_H
  17 #define LLVM_MACHINEOUTLINER_H
  18
  19 #include "llvm/CodeGen/LiveRegUnits.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/TargetRegisterInfo.h"
  22 #include "llvm/CodeGen/LivePhysRegs.h"
  23
  24 namespace llvm {
  25 namespace outliner {
  26
  27 /// Represents how an instruction should be mapped by the outliner.
  28 /// \p Legal instructions are those which are safe to outline.
  29 /// \p LegalTerminator instructions are safe to outline, but only as the
  30 /// last instruction in a sequence.
  31 /// \p Illegal instructions are those which cannot be outlined.
  32 /// \p Invisible instructions are instructions which can be outlined, but
  33 /// shouldn't actually impact the outlining result.
  34 enum InstrType { Legal, LegalTerminator, Illegal, Invisible };
  35
  36 /// An individual sequence of instructions to be replaced with a call to
  37 /// an outlined function.
  38 struct Candidate {
  39 private:
  40   /// The start index of this \p Candidate in the instruction list.
  41   unsigned StartIdx;
  42
  43   /// The number of instructions in this \p Candidate.
  44   unsigned Len;
  45
  46   // The first instruction in this \p Candidate.
  47   MachineBasicBlock::iterator FirstInst;
  48
  49   // The last instruction in this \p Candidate.
  50   MachineBasicBlock::iterator LastInst;
  51
  52   // The basic block that contains this Candidate.
  53   MachineBasicBlock *MBB;
  54
  55   /// Cost of calling an outlined function from this point as defined by the
  56   /// target.
  57   unsigned CallOverhead;
  58
  59 public:
  60   /// The index of this \p Candidate's \p OutlinedFunction in the list of
  61   /// \p OutlinedFunctions.
  62   unsigned FunctionIdx;
  63
  64   /// Set to false if the candidate overlapped with another candidate.
  65   bool InCandidateList = true;
  66
  67   /// Identifier denoting the instructions to emit to call an outlined function
  68   /// from this point. Defined by the target.
  69   unsigned CallConstructionID;
  70
  71   /// Contains physical register liveness information for the MBB containing
  72   /// this \p Candidate.
  73   ///
  74   /// This is optionally used by the target to calculate more fine-grained
  75   /// cost model information.
  76   LiveRegUnits LRU;
  77
  78   /// Contains the accumulated register liveness information for the
  79   /// instructions in this \p Candidate.
  80   ///
  81   /// This is optionally used by the target to determine which registers have
  82   /// been used across the sequence.
  83   LiveRegUnits UsedInSequence;
  84
  85   /// Return the number of instructions in this Candidate.
  86   unsigned getLength() const { return Len; }
  87
  88   /// Return the start index of this candidate.
  89   unsigned getStartIdx() const { return StartIdx; }
  90
  91   /// Return the end index of this candidate.
  92   unsigned getEndIdx() const { return StartIdx + Len - 1; }
  93
  94   /// Set the CallConstructionID and CallOverhead of this candidate to CID and
  95   /// CO respectively.
  96   void setCallInfo(unsigned CID, unsigned CO) {
  97     CallConstructionID = CID;
  98     CallOverhead = CO;
  99   }
 100
 101   /// Returns the call overhead of this candidate if it is in the list.
 102   unsigned getCallOverhead() const {
 103     return InCandidateList ? CallOverhead : 0;
 104   }
 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)
 124       : StartIdx(StartIdx), Len(Len), FirstInst(FirstInst), LastInst(LastInst),
 125         MBB(MBB), FunctionIdx(FunctionIdx) {}
 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     LRU.init(TRI);
 142     LRU.addLiveOuts(*MBB);
 143
 144     // Compute liveness from the end of the block up to the beginning of the
 145     // outlining candidate.
 146     std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(),
 147                   [this](MachineInstr &MI) { LRU.stepBackward(MI); });
 148
 149     // Walk over the sequence itself and figure out which registers were used
 150     // in the sequence.
 151     UsedInSequence.init(TRI);
 152     std::for_each(front(), std::next(back()),
 153                   [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
 154   }
 155 };
 156
 157 /// The information necessary to create an outlined function for some
 158 /// class of candidate.
 159 struct OutlinedFunction {
 160
 161 private:
 162   /// The number of candidates for this \p OutlinedFunction.
 163   unsigned OccurrenceCount = 0;
 164
 165 public:
 166   std::vector<std::shared_ptr<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   /// A number assigned to this function which appears at the end of its name.
 173   unsigned Name;
 174
 175   /// The sequence of integers corresponding to the instructions in this
 176   /// function.
 177   std::vector<unsigned> Sequence;
 178
 179   /// Represents the size of a sequence in bytes. (Some instructions vary
 180   /// widely in size, so just counting the instructions isn't very useful.)
 181   unsigned SequenceSize;
 182
 183   /// Target-defined overhead of constructing a frame for this function.
 184   unsigned FrameOverhead;
 185
 186   /// Target-defined identifier for constructing a frame for this function.
 187   unsigned FrameConstructionID;
 188
 189   /// Return the number of candidates for this \p OutlinedFunction.
 190   unsigned getOccurrenceCount() { return OccurrenceCount; }
 191
 192   /// Decrement the occurrence count of this OutlinedFunction and return the
 193   /// new count.
 194   unsigned decrement() {
 195     assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
 196     OccurrenceCount--;
 197     return getOccurrenceCount();
 198   }
 199
 200   /// Return the number of bytes it would take to outline this
 201   /// function.
 202   unsigned getOutliningCost() {
 203     unsigned CallOverhead = 0;
 204     for (std::shared_ptr<Candidate> &C : Candidates)
 205       CallOverhead += C->getCallOverhead();
 206     return CallOverhead + SequenceSize + FrameOverhead;
 207   }
 208
 209   /// Return the size in bytes of the unoutlined sequences.
 210   unsigned getNotOutlinedCost() { return OccurrenceCount * SequenceSize; }
 211
 212   /// Return the number of instructions that would be saved by outlining
 213   /// this function.
 214   unsigned getBenefit() {
 215     unsigned NotOutlinedCost = getNotOutlinedCost();
 216     unsigned OutlinedCost = getOutliningCost();
 217     return (NotOutlinedCost < OutlinedCost) ? 0
 218                                             : NotOutlinedCost - OutlinedCost;
 219   }
 220
 221   OutlinedFunction(std::vector<Candidate> &Cands,
 222                    unsigned SequenceSize, unsigned FrameOverhead,
 223                    unsigned FrameConstructionID)
 224       : SequenceSize(SequenceSize), FrameOverhead(FrameOverhead),
 225         FrameConstructionID(FrameConstructionID) {
 226     OccurrenceCount = Cands.size();
 227     for (Candidate &C : Cands)
 228       Candidates.push_back(std::make_shared<outliner::Candidate>(C));
 229
 230     unsigned B = getBenefit();
 231     for (std::shared_ptr<Candidate> &C : Candidates)
 232       C->Benefit = B;
 233   }
 234
 235   OutlinedFunction() {}
 236 };
 237 } // namespace outliner
 238 } // namespace llvm
 239
 240 #endif