lib/CodeGen/MachineOutliner.cpp

   1 //===---- MachineOutliner.cpp - Outline instructions -----------*- 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 /// Replaces repeated sequences of instructions with function calls.
  12 ///
  13 /// This works by placing every instruction from every basic block in a
  14 /// suffix tree, and repeatedly querying that tree for repeated sequences of
  15 /// instructions. If a sequence of instructions appears often, then it ought
  16 /// to be beneficial to pull out into a function.
  17 ///
  18 /// The MachineOutliner communicates with a given target using hooks defined in
  19 /// TargetInstrInfo.h. The target supplies the outliner with information on how
  20 /// a specific sequence of instructions should be outlined. This information
  21 /// is used to deduce the number of instructions necessary to
  22 ///
  23 /// * Create an outlined function
  24 /// * Call that outlined function
  25 ///
  26 /// Targets must implement
  27 ///   * getOutliningCandidateInfo
  28 ///   * insertOutlinerEpilogue
  29 ///   * insertOutlinedCall
  30 ///   * insertOutlinerPrologue
  31 ///   * isFunctionSafeToOutlineFrom
  32 ///
  33 /// in order to make use of the MachineOutliner.
  34 ///
  35 /// This was originally presented at the 2016 LLVM Developers' Meeting in the
  36 /// talk "Reducing Code Size Using Outlining". For a high-level overview of
  37 /// how this pass works, the talk is available on YouTube at
  38 ///
  39 /// https://www.youtube.com/watch?v=yorld-WSOeU
  40 ///
  41 /// The slides for the talk are available at
  42 ///
  43 /// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
  44 ///
  45 /// The talk provides an overview of how the outliner finds candidates and
  46 /// ultimately outlines them. It describes how the main data structure for this
  47 /// pass, the suffix tree, is queried and purged for candidates. It also gives
  48 /// a simplified suffix tree construction algorithm for suffix trees based off
  49 /// of the algorithm actually used here, Ukkonen's algorithm.
  50 ///
  51 /// For the original RFC for this pass, please see
  52 ///
  53 /// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
  54 ///
  55 /// For more information on the suffix tree data structure, please see
  56 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
  57 ///
  58 //===----------------------------------------------------------------------===//
  59 #include "llvm/ADT/DenseMap.h"
  60 #include "llvm/ADT/Statistic.h"
  61 #include "llvm/ADT/Twine.h"
  62 #include "llvm/CodeGen/MachineFrameInfo.h"
  63 #include "llvm/CodeGen/MachineFunction.h"
  64 #include "llvm/CodeGen/MachineInstrBuilder.h"
  65 #include "llvm/CodeGen/MachineModuleInfo.h"
  66 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  67 #include "llvm/CodeGen/Passes.h"
  68 #include "llvm/CodeGen/TargetInstrInfo.h"
  69 #include "llvm/CodeGen/TargetRegisterInfo.h"
  70 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  71 #include "llvm/IR/IRBuilder.h"
  72 #include "llvm/Support/Allocator.h"
  73 #include "llvm/Support/Debug.h"
  74 #include "llvm/Support/raw_ostream.h"
  75 #include "llvm/Target/TargetMachine.h"
  76 #include <functional>
  77 #include <map>
  78 #include <sstream>
  79 #include <tuple>
  80 #include <vector>
  81
  82 #define DEBUG_TYPE "machine-outliner"
  83
  84 using namespace llvm;
  85 using namespace ore;
  86
  87 STATISTIC(NumOutlined, "Number of candidates outlined");
  88 STATISTIC(FunctionsCreated, "Number of functions created");
  89
  90 namespace {
  91
  92 /// \brief An individual sequence of instructions to be replaced with a call to
  93 /// an outlined function.
  94 struct Candidate {
  95 private:
  96   /// The start index of this \p Candidate in the instruction list.
  97   unsigned StartIdx;
  98
  99   /// The number of instructions in this \p Candidate.
 100   unsigned Len;
 101
 102 public:
 103   /// Set to false if the candidate overlapped with another candidate.
 104   bool InCandidateList = true;
 105
 106   /// \brief The index of this \p Candidate's \p OutlinedFunction in the list of
 107   /// \p OutlinedFunctions.
 108   unsigned FunctionIdx;
 109
 110   /// Contains all target-specific information for this \p Candidate.
 111   TargetInstrInfo::MachineOutlinerInfo MInfo;
 112
 113   /// Return the number of instructions in this Candidate.
 114   unsigned getLength() const { return Len; }
 115
 116   /// Return the start index of this candidate.
 117   unsigned getStartIdx() const { return StartIdx; }
 118
 119   // Return the end index of this candidate.
 120   unsigned getEndIdx() const { return StartIdx + Len - 1; }
 121
 122   /// \brief The number of instructions that would be saved by outlining every
 123   /// candidate of this type.
 124   ///
 125   /// This is a fixed value which is not updated during the candidate pruning
 126   /// process. It is only used for deciding which candidate to keep if two
 127   /// candidates overlap. The true benefit is stored in the OutlinedFunction
 128   /// for some given candidate.
 129   unsigned Benefit = 0;
 130
 131   Candidate(unsigned StartIdx, unsigned Len, unsigned FunctionIdx)
 132       : StartIdx(StartIdx), Len(Len), FunctionIdx(FunctionIdx) {}
 133
 134   Candidate() {}
 135
 136   /// \brief Used to ensure that \p Candidates are outlined in an order that
 137   /// preserves the start and end indices of other \p Candidates.
 138   bool operator<(const Candidate &RHS) const {
 139     return getStartIdx() > RHS.getStartIdx();
 140   }
 141 };
 142
 143 /// \brief The information necessary to create an outlined function for some
 144 /// class of candidate.
 145 struct OutlinedFunction {
 146
 147 private:
 148   /// The number of candidates for this \p OutlinedFunction.
 149   unsigned OccurrenceCount = 0;
 150
 151 public:
 152   std::vector<std::shared_ptr<Candidate>> Candidates;
 153
 154   /// The actual outlined function created.
 155   /// This is initialized after we go through and create the actual function.
 156   MachineFunction *MF = nullptr;
 157
 158   /// A number assigned to this function which appears at the end of its name.
 159   unsigned Name;
 160
 161   /// \brief The sequence of integers corresponding to the instructions in this
 162   /// function.
 163   std::vector<unsigned> Sequence;
 164
 165   /// Contains all target-specific information for this \p OutlinedFunction.
 166   TargetInstrInfo::MachineOutlinerInfo MInfo;
 167
 168   /// Return the number of candidates for this \p OutlinedFunction.
 169   unsigned getOccurrenceCount() { return OccurrenceCount; }
 170
 171   /// Decrement the occurrence count of this OutlinedFunction and return the
 172   /// new count.
 173   unsigned decrement() {
 174     assert(OccurrenceCount > 0 && "Can't decrement an empty function!");
 175     OccurrenceCount--;
 176     return getOccurrenceCount();
 177   }
 178
 179   /// \brief Return the number of instructions it would take to outline this
 180   /// function.
 181   unsigned getOutliningCost() {
 182     return (OccurrenceCount * MInfo.CallOverhead) + Sequence.size() +
 183            MInfo.FrameOverhead;
 184   }
 185
 186   /// \brief Return the number of instructions that would be saved by outlining
 187   /// this function.
 188   unsigned getBenefit() {
 189     unsigned NotOutlinedCost = OccurrenceCount * Sequence.size();
 190     unsigned OutlinedCost = getOutliningCost();
 191     return (NotOutlinedCost < OutlinedCost) ? 0
 192                                             : NotOutlinedCost - OutlinedCost;
 193   }
 194
 195   OutlinedFunction(unsigned Name, unsigned OccurrenceCount,
 196                    const std::vector<unsigned> &Sequence,
 197                    TargetInstrInfo::MachineOutlinerInfo &MInfo)
 198       : OccurrenceCount(OccurrenceCount), Name(Name), Sequence(Sequence),
 199         MInfo(MInfo) {}
 200 };
 201
 202 /// Represents an undefined index in the suffix tree.
 203 const unsigned EmptyIdx = -1;
 204
 205 /// A node in a suffix tree which represents a substring or suffix.
 206 ///
 207 /// Each node has either no children or at least two children, with the root
 208 /// being a exception in the empty tree.
 209 ///
 210 /// Children are represented as a map between unsigned integers and nodes. If
 211 /// a node N has a child M on unsigned integer k, then the mapping represented
 212 /// by N is a proper prefix of the mapping represented by M. Note that this,
 213 /// although similar to a trie is somewhat different: each node stores a full
 214 /// substring of the full mapping rather than a single character state.
 215 ///
 216 /// Each internal node contains a pointer to the internal node representing
 217 /// the same string, but with the first character chopped off. This is stored
 218 /// in \p Link. Each leaf node stores the start index of its respective
 219 /// suffix in \p SuffixIdx.
 220 struct SuffixTreeNode {
 221
 222   /// The children of this node.
 223   ///
 224   /// A child existing on an unsigned integer implies that from the mapping
 225   /// represented by the current node, there is a way to reach another
 226   /// mapping by tacking that character on the end of the current string.
 227   DenseMap<unsigned, SuffixTreeNode *> Children;
 228
 229   /// A flag set to false if the node has been pruned from the tree.
 230   bool IsInTree = true;
 231
 232   /// The start index of this node's substring in the main string.
 233   unsigned StartIdx = EmptyIdx;
 234
 235   /// The end index of this node's substring in the main string.
 236   ///
 237   /// Every leaf node must have its \p EndIdx incremented at the end of every
 238   /// step in the construction algorithm. To avoid having to update O(N)
 239   /// nodes individually at the end of every step, the end index is stored
 240   /// as a pointer.
 241   unsigned *EndIdx = nullptr;
 242
 243   /// For leaves, the start index of the suffix represented by this node.
 244   ///
 245   /// For all other nodes, this is ignored.
 246   unsigned SuffixIdx = EmptyIdx;
 247
 248   /// \brief For internal nodes, a pointer to the internal node representing
 249   /// the same sequence with the first character chopped off.
 250   ///
 251   /// This acts as a shortcut in Ukkonen's algorithm. One of the things that
 252   /// Ukkonen's algorithm does to achieve linear-time construction is
 253   /// keep track of which node the next insert should be at. This makes each
 254   /// insert O(1), and there are a total of O(N) inserts. The suffix link
 255   /// helps with inserting children of internal nodes.
 256   ///
 257   /// Say we add a child to an internal node with associated mapping S. The
 258   /// next insertion must be at the node representing S - its first character.
 259   /// This is given by the way that we iteratively build the tree in Ukkonen's
 260   /// algorithm. The main idea is to look at the suffixes of each prefix in the
 261   /// string, starting with the longest suffix of the prefix, and ending with
 262   /// the shortest. Therefore, if we keep pointers between such nodes, we can
 263   /// move to the next insertion point in O(1) time. If we don't, then we'd
 264   /// have to query from the root, which takes O(N) time. This would make the
 265   /// construction algorithm O(N^2) rather than O(N).
 266   SuffixTreeNode *Link = nullptr;
 267
 268   /// The parent of this node. Every node except for the root has a parent.
 269   SuffixTreeNode *Parent = nullptr;
 270
 271   /// The number of times this node's string appears in the tree.
 272   ///
 273   /// This is equal to the number of leaf children of the string. It represents
 274   /// the number of suffixes that the node's string is a prefix of.
 275   unsigned OccurrenceCount = 0;
 276
 277   /// The length of the string formed by concatenating the edge labels from the
 278   /// root to this node.
 279   unsigned ConcatLen = 0;
 280
 281   /// Returns true if this node is a leaf.
 282   bool isLeaf() const { return SuffixIdx != EmptyIdx; }
 283
 284   /// Returns true if this node is the root of its owning \p SuffixTree.
 285   bool isRoot() const { return StartIdx == EmptyIdx; }
 286
 287   /// Return the number of elements in the substring associated with this node.
 288   size_t size() const {
 289
 290     // Is it the root? If so, it's the empty string so return 0.
 291     if (isRoot())
 292       return 0;
 293
 294     assert(*EndIdx != EmptyIdx && "EndIdx is undefined!");
 295
 296     // Size = the number of elements in the string.
 297     // For example, [0 1 2 3] has length 4, not 3. 3-0 = 3, so we have 3-0+1.
 298     return *EndIdx - StartIdx + 1;
 299   }
 300
 301   SuffixTreeNode(unsigned StartIdx, unsigned *EndIdx, SuffixTreeNode *Link,
 302                  SuffixTreeNode *Parent)
 303       : StartIdx(StartIdx), EndIdx(EndIdx), Link(Link), Parent(Parent) {}
 304
 305   SuffixTreeNode() {}
 306 };
 307
 308 /// A data structure for fast substring queries.
 309 ///
 310 /// Suffix trees represent the suffixes of their input strings in their leaves.
 311 /// A suffix tree is a type of compressed trie structure where each node
 312 /// represents an entire substring rather than a single character. Each leaf
 313 /// of the tree is a suffix.
 314 ///
 315 /// A suffix tree can be seen as a type of state machine where each state is a
 316 /// substring of the full string. The tree is structured so that, for a string
 317 /// of length N, there are exactly N leaves in the tree. This structure allows
 318 /// us to quickly find repeated substrings of the input string.
 319 ///
 320 /// In this implementation, a "string" is a vector of unsigned integers.
 321 /// These integers may result from hashing some data type. A suffix tree can
 322 /// contain 1 or many strings, which can then be queried as one large string.
 323 ///
 324 /// The suffix tree is implemented using Ukkonen's algorithm for linear-time
 325 /// suffix tree construction. Ukkonen's algorithm is explained in more detail
 326 /// in the paper by Esko Ukkonen "On-line construction of suffix trees. The
 327 /// paper is available at
 328 ///
 329 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
 330 class SuffixTree {
 331 public:
 332   /// Stores each leaf node in the tree.
 333   ///
 334   /// This is used for finding outlining candidates.
 335   std::vector<SuffixTreeNode *> LeafVector;
 336
 337   /// Each element is an integer representing an instruction in the module.
 338   ArrayRef<unsigned> Str;
 339
 340 private:
 341   /// Maintains each node in the tree.
 342   SpecificBumpPtrAllocator<SuffixTreeNode> NodeAllocator;
 343
 344   /// The root of the suffix tree.
 345   ///
 346   /// The root represents the empty string. It is maintained by the
 347   /// \p NodeAllocator like every other node in the tree.
 348   SuffixTreeNode *Root = nullptr;
 349
 350   /// Maintains the end indices of the internal nodes in the tree.
 351   ///
 352   /// Each internal node is guaranteed to never have its end index change
 353   /// during the construction algorithm; however, leaves must be updated at
 354   /// every step. Therefore, we need to store leaf end indices by reference
 355   /// to avoid updating O(N) leaves at every step of construction. Thus,
 356   /// every internal node must be allocated its own end index.
 357   BumpPtrAllocator InternalEndIdxAllocator;
 358
 359   /// The end index of each leaf in the tree.
 360   unsigned LeafEndIdx = -1;
 361
 362   /// \brief Helper struct which keeps track of the next insertion point in
 363   /// Ukkonen's algorithm.
 364   struct ActiveState {
 365     /// The next node to insert at.
 366     SuffixTreeNode *Node;
 367
 368     /// The index of the first character in the substring currently being added.
 369     unsigned Idx = EmptyIdx;
 370
 371     /// The length of the substring we have to add at the current step.
 372     unsigned Len = 0;
 373   };
 374
 375   /// \brief The point the next insertion will take place at in the
 376   /// construction algorithm.
 377   ActiveState Active;
 378
 379   /// Allocate a leaf node and add it to the tree.
 380   ///
 381   /// \param Parent The parent of this node.
 382   /// \param StartIdx The start index of this node's associated string.
 383   /// \param Edge The label on the edge leaving \p Parent to this node.
 384   ///
 385   /// \returns A pointer to the allocated leaf node.
 386   SuffixTreeNode *insertLeaf(SuffixTreeNode &Parent, unsigned StartIdx,
 387                              unsigned Edge) {
 388
 389     assert(StartIdx <= LeafEndIdx && "String can't start after it ends!");
 390
 391     SuffixTreeNode *N = new (NodeAllocator.Allocate())
 392         SuffixTreeNode(StartIdx, &LeafEndIdx, nullptr, &Parent);
 393     Parent.Children[Edge] = N;
 394
 395     return N;
 396   }
 397
 398   /// Allocate an internal node and add it to the tree.
 399   ///
 400   /// \param Parent The parent of this node. Only null when allocating the root.
 401   /// \param StartIdx The start index of this node's associated string.
 402   /// \param EndIdx The end index of this node's associated string.
 403   /// \param Edge The label on the edge leaving \p Parent to this node.
 404   ///
 405   /// \returns A pointer to the allocated internal node.
 406   SuffixTreeNode *insertInternalNode(SuffixTreeNode *Parent, unsigned StartIdx,
 407                                      unsigned EndIdx, unsigned Edge) {
 408
 409     assert(StartIdx <= EndIdx && "String can't start after it ends!");
 410     assert(!(!Parent && StartIdx != EmptyIdx) &&
 411            "Non-root internal nodes must have parents!");
 412
 413     unsigned *E = new (InternalEndIdxAllocator) unsigned(EndIdx);
 414     SuffixTreeNode *N = new (NodeAllocator.Allocate())
 415         SuffixTreeNode(StartIdx, E, Root, Parent);
 416     if (Parent)
 417       Parent->Children[Edge] = N;
 418
 419     return N;
 420   }
 421
 422   /// \brief Set the suffix indices of the leaves to the start indices of their
 423   /// respective suffixes. Also stores each leaf in \p LeafVector at its
 424   /// respective suffix index.
 425   ///
 426   /// \param[in] CurrNode The node currently being visited.
 427   /// \param CurrIdx The current index of the string being visited.
 428   void setSuffixIndices(SuffixTreeNode &CurrNode, unsigned CurrIdx) {
 429
 430     bool IsLeaf = CurrNode.Children.size() == 0 && !CurrNode.isRoot();
 431
 432     // Store the length of the concatenation of all strings from the root to
 433     // this node.
 434     if (!CurrNode.isRoot()) {
 435       if (CurrNode.ConcatLen == 0)
 436         CurrNode.ConcatLen = CurrNode.size();
 437
 438       if (CurrNode.Parent)
 439         CurrNode.ConcatLen += CurrNode.Parent->ConcatLen;
 440     }
 441
 442     // Traverse the tree depth-first.
 443     for (auto &ChildPair : CurrNode.Children) {
 444       assert(ChildPair.second && "Node had a null child!");
 445       setSuffixIndices(*ChildPair.second, CurrIdx + ChildPair.second->size());
 446     }
 447
 448     // Is this node a leaf?
 449     if (IsLeaf) {
 450       // If yes, give it a suffix index and bump its parent's occurrence count.
 451       CurrNode.SuffixIdx = Str.size() - CurrIdx;
 452       assert(CurrNode.Parent && "CurrNode had no parent!");
 453       CurrNode.Parent->OccurrenceCount++;
 454
 455       // Store the leaf in the leaf vector for pruning later.
 456       LeafVector[CurrNode.SuffixIdx] = &CurrNode;
 457     }
 458   }
 459
 460   /// \brief Construct the suffix tree for the prefix of the input ending at
 461   /// \p EndIdx.
 462   ///
 463   /// Used to construct the full suffix tree iteratively. At the end of each
 464   /// step, the constructed suffix tree is either a valid suffix tree, or a
 465   /// suffix tree with implicit suffixes. At the end of the final step, the
 466   /// suffix tree is a valid tree.
 467   ///
 468   /// \param EndIdx The end index of the current prefix in the main string.
 469   /// \param SuffixesToAdd The number of suffixes that must be added
 470   /// to complete the suffix tree at the current phase.
 471   ///
 472   /// \returns The number of suffixes that have not been added at the end of
 473   /// this step.
 474   unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd) {
 475     SuffixTreeNode *NeedsLink = nullptr;
 476
 477     while (SuffixesToAdd > 0) {
 478
 479       // Are we waiting to add anything other than just the last character?
 480       if (Active.Len == 0) {
 481         // If not, then say the active index is the end index.
 482         Active.Idx = EndIdx;
 483       }
 484
 485       assert(Active.Idx <= EndIdx && "Start index can't be after end index!");
 486
 487       // The first character in the current substring we're looking at.
 488       unsigned FirstChar = Str[Active.Idx];
 489
 490       // Have we inserted anything starting with FirstChar at the current node?
 491       if (Active.Node->Children.count(FirstChar) == 0) {
 492         // If not, then we can just insert a leaf and move too the next step.
 493         insertLeaf(*Active.Node, EndIdx, FirstChar);
 494
 495         // The active node is an internal node, and we visited it, so it must
 496         // need a link if it doesn't have one.
 497         if (NeedsLink) {
 498           NeedsLink->Link = Active.Node;
 499           NeedsLink = nullptr;
 500         }
 501       } else {
 502         // There's a match with FirstChar, so look for the point in the tree to
 503         // insert a new node.
 504         SuffixTreeNode *NextNode = Active.Node->Children[FirstChar];
 505
 506         unsigned SubstringLen = NextNode->size();
 507
 508         // Is the current suffix we're trying to insert longer than the size of
 509         // the child we want to move to?
 510         if (Active.Len >= SubstringLen) {
 511           // If yes, then consume the characters we've seen and move to the next
 512           // node.
 513           Active.Idx += SubstringLen;
 514           Active.Len -= SubstringLen;
 515           Active.Node = NextNode;
 516           continue;
 517         }
 518
 519         // Otherwise, the suffix we're trying to insert must be contained in the
 520         // next node we want to move to.
 521         unsigned LastChar = Str[EndIdx];
 522
 523         // Is the string we're trying to insert a substring of the next node?
 524         if (Str[NextNode->StartIdx + Active.Len] == LastChar) {
 525           // If yes, then we're done for this step. Remember our insertion point
 526           // and move to the next end index. At this point, we have an implicit
 527           // suffix tree.
 528           if (NeedsLink && !Active.Node->isRoot()) {
 529             NeedsLink->Link = Active.Node;
 530             NeedsLink = nullptr;
 531           }
 532
 533           Active.Len++;
 534           break;
 535         }
 536
 537         // The string we're trying to insert isn't a substring of the next node,
 538         // but matches up to a point. Split the node.
 539         //
 540         // For example, say we ended our search at a node n and we're trying to
 541         // insert ABD. Then we'll create a new node s for AB, reduce n to just
 542         // representing C, and insert a new leaf node l to represent d. This
 543         // allows us to ensure that if n was a leaf, it remains a leaf.
 544         //
 545         //   | ABC  ---split--->  | AB
 546         //   n                    s
 547         //                     C / \ D
 548         //                      n   l
 549
 550         // The node s from the diagram
 551         SuffixTreeNode *SplitNode =
 552             insertInternalNode(Active.Node, NextNode->StartIdx,
 553                                NextNode->StartIdx + Active.Len - 1, FirstChar);
 554
 555         // Insert the new node representing the new substring into the tree as
 556         // a child of the split node. This is the node l from the diagram.
 557         insertLeaf(*SplitNode, EndIdx, LastChar);
 558
 559         // Make the old node a child of the split node and update its start
 560         // index. This is the node n from the diagram.
 561         NextNode->StartIdx += Active.Len;
 562         NextNode->Parent = SplitNode;
 563         SplitNode->Children[Str[NextNode->StartIdx]] = NextNode;
 564
 565         // SplitNode is an internal node, update the suffix link.
 566         if (NeedsLink)
 567           NeedsLink->Link = SplitNode;
 568
 569         NeedsLink = SplitNode;
 570       }
 571
 572       // We've added something new to the tree, so there's one less suffix to
 573       // add.
 574       SuffixesToAdd--;
 575
 576       if (Active.Node->isRoot()) {
 577         if (Active.Len > 0) {
 578           Active.Len--;
 579           Active.Idx = EndIdx - SuffixesToAdd + 1;
 580         }
 581       } else {
 582         // Start the next phase at the next smallest suffix.
 583         Active.Node = Active.Node->Link;
 584       }
 585     }
 586
 587     return SuffixesToAdd;
 588   }
 589
 590 public:
 591   /// Construct a suffix tree from a sequence of unsigned integers.
 592   ///
 593   /// \param Str The string to construct the suffix tree for.
 594   SuffixTree(const std::vector<unsigned> &Str) : Str(Str) {
 595     Root = insertInternalNode(nullptr, EmptyIdx, EmptyIdx, 0);
 596     Root->IsInTree = true;
 597     Active.Node = Root;
 598     LeafVector = std::vector<SuffixTreeNode *>(Str.size());
 599
 600     // Keep track of the number of suffixes we have to add of the current
 601     // prefix.
 602     unsigned SuffixesToAdd = 0;
 603     Active.Node = Root;
 604
 605     // Construct the suffix tree iteratively on each prefix of the string.
 606     // PfxEndIdx is the end index of the current prefix.
 607     // End is one past the last element in the string.
 608     for (unsigned PfxEndIdx = 0, End = Str.size(); PfxEndIdx < End;
 609          PfxEndIdx++) {
 610       SuffixesToAdd++;
 611       LeafEndIdx = PfxEndIdx; // Extend each of the leaves.
 612       SuffixesToAdd = extend(PfxEndIdx, SuffixesToAdd);
 613     }
 614
 615     // Set the suffix indices of each leaf.
 616     assert(Root && "Root node can't be nullptr!");
 617     setSuffixIndices(*Root, 0);
 618   }
 619 };
 620
 621 /// \brief Maps \p MachineInstrs to unsigned integers and stores the mappings.
 622 struct InstructionMapper {
 623
 624   /// \brief The next available integer to assign to a \p MachineInstr that
 625   /// cannot be outlined.
 626   ///
 627   /// Set to -3 for compatability with \p DenseMapInfo<unsigned>.
 628   unsigned IllegalInstrNumber = -3;
 629
 630   /// \brief The next available integer to assign to a \p MachineInstr that can
 631   /// be outlined.
 632   unsigned LegalInstrNumber = 0;
 633
 634   /// Correspondence from \p MachineInstrs to unsigned integers.
 635   DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>
 636       InstructionIntegerMap;
 637
 638   /// Corresponcence from unsigned integers to \p MachineInstrs.
 639   /// Inverse of \p InstructionIntegerMap.
 640   DenseMap<unsigned, MachineInstr *> IntegerInstructionMap;
 641
 642   /// The vector of unsigned integers that the module is mapped to.
 643   std::vector<unsigned> UnsignedVec;
 644
 645   /// \brief Stores the location of the instruction associated with the integer
 646   /// at index i in \p UnsignedVec for each index i.
 647   std::vector<MachineBasicBlock::iterator> InstrList;
 648
 649   /// \brief Maps \p *It to a legal integer.
 650   ///
 651   /// Updates \p InstrList, \p UnsignedVec, \p InstructionIntegerMap,
 652   /// \p IntegerInstructionMap, and \p LegalInstrNumber.
 653   ///
 654   /// \returns The integer that \p *It was mapped to.
 655   unsigned mapToLegalUnsigned(MachineBasicBlock::iterator &It) {
 656
 657     // Get the integer for this instruction or give it the current
 658     // LegalInstrNumber.
 659     InstrList.push_back(It);
 660     MachineInstr &MI = *It;
 661     bool WasInserted;
 662     DenseMap<MachineInstr *, unsigned, MachineInstrExpressionTrait>::iterator
 663         ResultIt;
 664     std::tie(ResultIt, WasInserted) =
 665         InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));
 666     unsigned MINumber = ResultIt->second;
 667
 668     // There was an insertion.
 669     if (WasInserted) {
 670       LegalInstrNumber++;
 671       IntegerInstructionMap.insert(std::make_pair(MINumber, &MI));
 672     }
 673
 674     UnsignedVec.push_back(MINumber);
 675
 676     // Make sure we don't overflow or use any integers reserved by the DenseMap.
 677     if (LegalInstrNumber >= IllegalInstrNumber)
 678       report_fatal_error("Instruction mapping overflow!");
 679
 680     assert(LegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
 681            "Tried to assign DenseMap tombstone or empty key to instruction.");
 682     assert(LegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
 683            "Tried to assign DenseMap tombstone or empty key to instruction.");
 684
 685     return MINumber;
 686   }
 687
 688   /// Maps \p *It to an illegal integer.
 689   ///
 690   /// Updates \p InstrList, \p UnsignedVec, and \p IllegalInstrNumber.
 691   ///
 692   /// \returns The integer that \p *It was mapped to.
 693   unsigned mapToIllegalUnsigned(MachineBasicBlock::iterator &It) {
 694     unsigned MINumber = IllegalInstrNumber;
 695
 696     InstrList.push_back(It);
 697     UnsignedVec.push_back(IllegalInstrNumber);
 698     IllegalInstrNumber--;
 699
 700     assert(LegalInstrNumber < IllegalInstrNumber &&
 701            "Instruction mapping overflow!");
 702
 703     assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getEmptyKey() &&
 704            "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
 705
 706     assert(IllegalInstrNumber != DenseMapInfo<unsigned>::getTombstoneKey() &&
 707            "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");
 708
 709     return MINumber;
 710   }
 711
 712   /// \brief Transforms a \p MachineBasicBlock into a \p vector of \p unsigneds
 713   /// and appends it to \p UnsignedVec and \p InstrList.
 714   ///
 715   /// Two instructions are assigned the same integer if they are identical.
 716   /// If an instruction is deemed unsafe to outline, then it will be assigned an
 717   /// unique integer. The resulting mapping is placed into a suffix tree and
 718   /// queried for candidates.
 719   ///
 720   /// \param MBB The \p MachineBasicBlock to be translated into integers.
 721   /// \param TRI \p TargetRegisterInfo for the module.
 722   /// \param TII \p TargetInstrInfo for the module.
 723   void convertToUnsignedVec(MachineBasicBlock &MBB,
 724                             const TargetRegisterInfo &TRI,
 725                             const TargetInstrInfo &TII) {
 726     for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et;
 727          It++) {
 728
 729       // Keep track of where this instruction is in the module.
 730       switch (TII.getOutliningType(*It)) {
 731       case TargetInstrInfo::MachineOutlinerInstrType::Illegal:
 732         mapToIllegalUnsigned(It);
 733         break;
 734
 735       case TargetInstrInfo::MachineOutlinerInstrType::Legal:
 736         mapToLegalUnsigned(It);
 737         break;
 738
 739       case TargetInstrInfo::MachineOutlinerInstrType::Invisible:
 740         break;
 741       }
 742     }
 743
 744     // After we're done every insertion, uniquely terminate this part of the
 745     // "string". This makes sure we won't match across basic block or function
 746     // boundaries since the "end" is encoded uniquely and thus appears in no
 747     // repeated substring.
 748     InstrList.push_back(MBB.end());
 749     UnsignedVec.push_back(IllegalInstrNumber);
 750     IllegalInstrNumber--;
 751   }
 752
 753   InstructionMapper() {
 754     // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
 755     // changed.
 756     assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
 757            "DenseMapInfo<unsigned>'s empty key isn't -1!");
 758     assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
 759            "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
 760   }
 761 };
 762
 763 /// \brief An interprocedural pass which finds repeated sequences of
 764 /// instructions and replaces them with calls to functions.
 765 ///
 766 /// Each instruction is mapped to an unsigned integer and placed in a string.
 767 /// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
 768 /// is then repeatedly queried for repeated sequences of instructions. Each
 769 /// non-overlapping repeated sequence is then placed in its own
 770 /// \p MachineFunction and each instance is then replaced with a call to that
 771 /// function.
 772 struct MachineOutliner : public ModulePass {
 773
 774   static char ID;
 775
 776   /// \brief Set to true if the outliner should consider functions with
 777   /// linkonceodr linkage.
 778   bool OutlineFromLinkOnceODRs = false;
 779
 780   StringRef getPassName() const override { return "Machine Outliner"; }
 781
 782   void getAnalysisUsage(AnalysisUsage &AU) const override {
 783     AU.addRequired<MachineModuleInfo>();
 784     AU.addPreserved<MachineModuleInfo>();
 785     AU.setPreservesAll();
 786     ModulePass::getAnalysisUsage(AU);
 787   }
 788
 789   MachineOutliner(bool OutlineFromLinkOnceODRs = false)
 790       : ModulePass(ID), OutlineFromLinkOnceODRs(OutlineFromLinkOnceODRs) {
 791     initializeMachineOutlinerPass(*PassRegistry::getPassRegistry());
 792   }
 793
 794   /// Find all repeated substrings that satisfy the outlining cost model.
 795   ///
 796   /// If a substring appears at least twice, then it must be represented by
 797   /// an internal node which appears in at least two suffixes. Each suffix is
 798   /// represented by a leaf node. To do this, we visit each internal node in
 799   /// the tree, using the leaf children of each internal node. If an internal
 800   /// node represents a beneficial substring, then we use each of its leaf
 801   /// children to find the locations of its substring.
 802   ///
 803   /// \param ST A suffix tree to query.
 804   /// \param TII TargetInstrInfo for the target.
 805   /// \param Mapper Contains outlining mapping information.
 806   /// \param[out] CandidateList Filled with candidates representing each
 807   /// beneficial substring.
 808   /// \param[out] FunctionList Filled with a list of \p OutlinedFunctions each
 809   /// type of candidate.
 810   ///
 811   /// \returns The length of the longest candidate found.
 812   unsigned
 813   findCandidates(SuffixTree &ST, const TargetInstrInfo &TII,
 814                  InstructionMapper &Mapper,
 815                  std::vector<std::shared_ptr<Candidate>> &CandidateList,
 816                  std::vector<OutlinedFunction> &FunctionList);
 817
 818   /// \brief Replace the sequences of instructions represented by the
 819   /// \p Candidates in \p CandidateList with calls to \p MachineFunctions
 820   /// described in \p FunctionList.
 821   ///
 822   /// \param M The module we are outlining from.
 823   /// \param CandidateList A list of candidates to be outlined.
 824   /// \param FunctionList A list of functions to be inserted into the module.
 825   /// \param Mapper Contains the instruction mappings for the module.
 826   bool outline(Module &M,
 827                const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
 828                std::vector<OutlinedFunction> &FunctionList,
 829                InstructionMapper &Mapper);
 830
 831   /// Creates a function for \p OF and inserts it into the module.
 832   MachineFunction *createOutlinedFunction(Module &M, const OutlinedFunction &OF,
 833                                           InstructionMapper &Mapper);
 834
 835   /// Find potential outlining candidates and store them in \p CandidateList.
 836   ///
 837   /// For each type of potential candidate, also build an \p OutlinedFunction
 838   /// struct containing the information to build the function for that
 839   /// candidate.
 840   ///
 841   /// \param[out] CandidateList Filled with outlining candidates for the module.
 842   /// \param[out] FunctionList Filled with functions corresponding to each type
 843   /// of \p Candidate.
 844   /// \param ST The suffix tree for the module.
 845   /// \param TII TargetInstrInfo for the module.
 846   ///
 847   /// \returns The length of the longest candidate found. 0 if there are none.
 848   unsigned
 849   buildCandidateList(std::vector<std::shared_ptr<Candidate>> &CandidateList,
 850                      std::vector<OutlinedFunction> &FunctionList,
 851                      SuffixTree &ST, InstructionMapper &Mapper,
 852                      const TargetInstrInfo &TII);
 853
 854   /// Helper function for pruneOverlaps.
 855   /// Removes \p C from the candidate list, and updates its \p OutlinedFunction.
 856   void prune(Candidate &C, std::vector<OutlinedFunction> &FunctionList);
 857
 858   /// \brief Remove any overlapping candidates that weren't handled by the
 859   /// suffix tree's pruning method.
 860   ///
 861   /// Pruning from the suffix tree doesn't necessarily remove all overlaps.
 862   /// If a short candidate is chosen for outlining, then a longer candidate
 863   /// which has that short candidate as a suffix is chosen, the tree's pruning
 864   /// method will not find it. Thus, we need to prune before outlining as well.
 865   ///
 866   /// \param[in,out] CandidateList A list of outlining candidates.
 867   /// \param[in,out] FunctionList A list of functions to be outlined.
 868   /// \param Mapper Contains instruction mapping info for outlining.
 869   /// \param MaxCandidateLen The length of the longest candidate.
 870   /// \param TII TargetInstrInfo for the module.
 871   void pruneOverlaps(std::vector<std::shared_ptr<Candidate>> &CandidateList,
 872                      std::vector<OutlinedFunction> &FunctionList,
 873                      InstructionMapper &Mapper, unsigned MaxCandidateLen,
 874                      const TargetInstrInfo &TII);
 875
 876   /// Construct a suffix tree on the instructions in \p M and outline repeated
 877   /// strings from that tree.
 878   bool runOnModule(Module &M) override;
 879 };
 880
 881 } // Anonymous namespace.
 882
 883 char MachineOutliner::ID = 0;
 884
 885 namespace llvm {
 886 ModulePass *createMachineOutlinerPass(bool OutlineFromLinkOnceODRs) {
 887   return new MachineOutliner(OutlineFromLinkOnceODRs);
 888 }
 889
 890 } // namespace llvm
 891
 892 INITIALIZE_PASS(MachineOutliner, DEBUG_TYPE, "Machine Function Outliner", false,
 893                 false)
 894
 895 unsigned MachineOutliner::findCandidates(
 896     SuffixTree &ST, const TargetInstrInfo &TII, InstructionMapper &Mapper,
 897     std::vector<std::shared_ptr<Candidate>> &CandidateList,
 898     std::vector<OutlinedFunction> &FunctionList) {
 899   CandidateList.clear();
 900   FunctionList.clear();
 901   unsigned MaxLen = 0;
 902
 903   // FIXME: Visit internal nodes instead of leaves.
 904   for (SuffixTreeNode *Leaf : ST.LeafVector) {
 905     assert(Leaf && "Leaves in LeafVector cannot be null!");
 906     if (!Leaf->IsInTree)
 907       continue;
 908
 909     assert(Leaf->Parent && "All leaves must have parents!");
 910     SuffixTreeNode &Parent = *(Leaf->Parent);
 911
 912     // If it doesn't appear enough, or we already outlined from it, skip it.
 913     if (Parent.OccurrenceCount < 2 || Parent.isRoot() || !Parent.IsInTree)
 914       continue;
 915
 916     // Figure out if this candidate is beneficial.
 917     unsigned StringLen = Leaf->ConcatLen - (unsigned)Leaf->size();
 918
 919     // Too short to be beneficial; skip it.
 920     // FIXME: This isn't necessarily true for, say, X86. If we factor in
 921     // instruction lengths we need more information than this.
 922     if (StringLen < 2)
 923       continue;
 924
 925     // If this is a beneficial class of candidate, then every one is stored in
 926     // this vector.
 927     std::vector<Candidate> CandidatesForRepeatedSeq;
 928
 929     // Describes the start and end point of each candidate. This allows the
 930     // target to infer some information about each occurrence of each repeated
 931     // sequence.
 932     // FIXME: CandidatesForRepeatedSeq and this should be combined.
 933     std::vector<
 934         std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>>
 935         RepeatedSequenceLocs;
 936
 937     // Figure out the call overhead for each instance of the sequence.
 938     for (auto &ChildPair : Parent.Children) {
 939       SuffixTreeNode *M = ChildPair.second;
 940
 941       if (M && M->IsInTree && M->isLeaf()) {
 942         // Never visit this leaf again.
 943         M->IsInTree = false;
 944         unsigned StartIdx = M->SuffixIdx;
 945         unsigned EndIdx = StartIdx + StringLen - 1;
 946
 947         // Trick: Discard some candidates that would be incompatible with the
 948         // ones we've already found for this sequence. This will save us some
 949         // work in candidate selection.
 950         //
 951         // If two candidates overlap, then we can't outline them both. This
 952         // happens when we have candidates that look like, say
 953         //
 954         // AA (where each "A" is an instruction).
 955         //
 956         // We might have some portion of the module that looks like this:
 957         // AAAAAA (6 A's)
 958         //
 959         // In this case, there are 5 different copies of "AA" in this range, but
 960         // at most 3 can be outlined. If only outlining 3 of these is going to
 961         // be unbeneficial, then we ought to not bother.
 962         //
 963         // Note that two things DON'T overlap when they look like this:
 964         // start1...end1 .... start2...end2
 965         // That is, one must either
 966         // * End before the other starts
 967         // * Start after the other ends
 968         if (std::all_of(CandidatesForRepeatedSeq.begin(),
 969                         CandidatesForRepeatedSeq.end(),
 970                         [&StartIdx, &EndIdx](const Candidate &C) {
 971                           return (EndIdx < C.getStartIdx() ||
 972                                   StartIdx > C.getEndIdx());
 973                         })) {
 974           // It doesn't overlap with anything, so we can outline it.
 975           // Each sequence is over [StartIt, EndIt].
 976           MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
 977           MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
 978
 979           // Save the candidate and its location.
 980           CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen,
 981                                                 FunctionList.size());
 982           RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt));
 983         }
 984       }
 985     }
 986
 987     // We've found something we might want to outline.
 988     // Create an OutlinedFunction to store it and check if it'd be beneficial
 989     // to outline.
 990     TargetInstrInfo::MachineOutlinerInfo MInfo =
 991         TII.getOutlininingCandidateInfo(RepeatedSequenceLocs);
 992     std::vector<unsigned> Seq;
 993     for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
 994       Seq.push_back(ST.Str[i]);
 995     OutlinedFunction OF(FunctionList.size(), CandidatesForRepeatedSeq.size(),
 996                         Seq, MInfo);
 997     unsigned Benefit = OF.getBenefit();
 998
 999     // Is it better to outline this candidate than not?
1000     if (Benefit < 1) {
1001       // Outlining this candidate would take more instructions than not
1002       // outlining.
1003       // Emit a remark explaining why we didn't outline this candidate.
1004       std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator> C =
1005           RepeatedSequenceLocs[0];
1006       MachineOptimizationRemarkEmitter MORE(
1007           *(C.first->getParent()->getParent()), nullptr);
1008       MORE.emit([&]() {
1009         MachineOptimizationRemarkMissed R(DEBUG_TYPE, "NotOutliningCheaper",
1010                                           C.first->getDebugLoc(),
1011                                           C.first->getParent());
1012         R << "Did not outline " << NV("Length", StringLen) << " instructions"
1013           << " from " << NV("NumOccurrences", RepeatedSequenceLocs.size())
1014           << " locations."
1015           << " Instructions from outlining all occurrences ("
1016           << NV("OutliningCost", OF.getOutliningCost()) << ")"
1017           << " >= Unoutlined instruction count ("
1018           << NV("NotOutliningCost", StringLen * OF.getOccurrenceCount()) << ")"
1019           << " (Also found at: ";
1020
1021         // Tell the user the other places the candidate was found.
1022         for (unsigned i = 1, e = RepeatedSequenceLocs.size(); i < e; i++) {
1023           R << NV((Twine("OtherStartLoc") + Twine(i)).str(),
1024                   RepeatedSequenceLocs[i].first->getDebugLoc());
1025           if (i != e - 1)
1026             R << ", ";
1027         }
1028
1029         R << ")";
1030         return R;
1031       });
1032
1033       // Move to the next candidate.
1034       continue;
1035     }
1036
1037     if (StringLen > MaxLen)
1038       MaxLen = StringLen;
1039
1040     // At this point, the candidate class is seen as beneficial. Set their
1041     // benefit values and save them in the candidate list.
1042     std::vector<std::shared_ptr<Candidate>> CandidatesForFn;
1043     for (Candidate &C : CandidatesForRepeatedSeq) {
1044       C.Benefit = Benefit;
1045       C.MInfo = MInfo;
1046       std::shared_ptr<Candidate> Cptr = std::make_shared<Candidate>(C);
1047       CandidateList.push_back(Cptr);
1048       CandidatesForFn.push_back(Cptr);
1049     }
1050
1051     FunctionList.push_back(OF);
1052     FunctionList.back().Candidates = CandidatesForFn;
1053
1054     // Move to the next function.
1055     Parent.IsInTree = false;
1056   }
1057
1058   return MaxLen;
1059 }
1060
1061 // Remove C from the candidate space, and update its OutlinedFunction.
1062 void MachineOutliner::prune(Candidate &C,
1063                             std::vector<OutlinedFunction> &FunctionList) {
1064   // Get the OutlinedFunction associated with this Candidate.
1065   OutlinedFunction &F = FunctionList[C.FunctionIdx];
1066
1067   // Update C's associated function's occurrence count.
1068   F.decrement();
1069
1070   // Remove C from the CandidateList.
1071   C.InCandidateList = false;
1072
1073   DEBUG(dbgs() << "- Removed a Candidate \n";
1074         dbgs() << "--- Num fns left for candidate: " << F.getOccurrenceCount()
1075                << "\n";
1076         dbgs() << "--- Candidate's functions's benefit: " << F.getBenefit()
1077                << "\n";);
1078 }
1079
1080 void MachineOutliner::pruneOverlaps(
1081     std::vector<std::shared_ptr<Candidate>> &CandidateList,
1082     std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper,
1083     unsigned MaxCandidateLen, const TargetInstrInfo &TII) {
1084
1085   // Return true if this candidate became unbeneficial for outlining in a
1086   // previous step.
1087   auto ShouldSkipCandidate = [&FunctionList, this](Candidate &C) {
1088
1089     // Check if the candidate was removed in a previous step.
1090     if (!C.InCandidateList)
1091       return true;
1092
1093     // C must be alive. Check if we should remove it.
1094     if (FunctionList[C.FunctionIdx].getBenefit() < 1) {
1095       prune(C, FunctionList);
1096       return true;
1097     }
1098
1099     // C is in the list, and F is still beneficial.
1100     return false;
1101   };
1102
1103   // TODO: Experiment with interval trees or other interval-checking structures
1104   // to lower the time complexity of this function.
1105   // TODO: Can we do better than the simple greedy choice?
1106   // Check for overlaps in the range.
1107   // This is O(MaxCandidateLen * CandidateList.size()).
1108   for (auto It = CandidateList.begin(), Et = CandidateList.end(); It != Et;
1109        It++) {
1110     Candidate &C1 = **It;
1111
1112     // If C1 was already pruned, or its function is no longer beneficial for
1113     // outlining, move to the next candidate.
1114     if (ShouldSkipCandidate(C1))
1115       continue;
1116
1117     // The minimum start index of any candidate that could overlap with this
1118     // one.
1119     unsigned FarthestPossibleIdx = 0;
1120
1121     // Either the index is 0, or it's at most MaxCandidateLen indices away.
1122     if (C1.getStartIdx() > MaxCandidateLen)
1123       FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen;
1124
1125     // Compare against the candidates in the list that start at at most
1126     // FarthestPossibleIdx indices away from C1. There are at most
1127     // MaxCandidateLen of these.
1128     for (auto Sit = It + 1; Sit != Et; Sit++) {
1129       Candidate &C2 = **Sit;
1130
1131       // Is this candidate too far away to overlap?
1132       if (C2.getStartIdx() < FarthestPossibleIdx)
1133         break;
1134
1135       // If C2 was already pruned, or its function is no longer beneficial for
1136       // outlining, move to the next candidate.
1137       if (ShouldSkipCandidate(C2))
1138         continue;
1139
1140       // Do C1 and C2 overlap?
1141       //
1142       // Not overlapping:
1143       // High indices... [C1End ... C1Start][C2End ... C2Start] ...Low indices
1144       //
1145       // We sorted our candidate list so C2Start <= C1Start. We know that
1146       // C2End > C2Start since each candidate has length >= 2. Therefore, all we
1147       // have to check is C2End < C2Start to see if we overlap.
1148       if (C2.getEndIdx() < C1.getStartIdx())
1149         continue;
1150
1151       // C1 and C2 overlap.
1152       // We need to choose the better of the two.
1153       //
1154       // Approximate this by picking the one which would have saved us the
1155       // most instructions before any pruning.
1156
1157       // Is C2 a better candidate?
1158       if (C2.Benefit > C1.Benefit) {
1159         // Yes, so prune C1. Since C1 is dead, we don't have to compare it
1160         // against anything anymore, so break.
1161         prune(C1, FunctionList);
1162         break;
1163       }
1164
1165       // Prune C2 and move on to the next candidate.
1166       prune(C2, FunctionList);
1167     }
1168   }
1169 }
1170
1171 unsigned MachineOutliner::buildCandidateList(
1172     std::vector<std::shared_ptr<Candidate>> &CandidateList,
1173     std::vector<OutlinedFunction> &FunctionList, SuffixTree &ST,
1174     InstructionMapper &Mapper, const TargetInstrInfo &TII) {
1175
1176   std::vector<unsigned> CandidateSequence; // Current outlining candidate.
1177   unsigned MaxCandidateLen = 0;            // Length of the longest candidate.
1178
1179   MaxCandidateLen =
1180       findCandidates(ST, TII, Mapper, CandidateList, FunctionList);
1181
1182   // Sort the candidates in decending order. This will simplify the outlining
1183   // process when we have to remove the candidates from the mapping by
1184   // allowing us to cut them out without keeping track of an offset.
1185   std::stable_sort(
1186       CandidateList.begin(), CandidateList.end(),
1187       [](const std::shared_ptr<Candidate> &LHS,
1188          const std::shared_ptr<Candidate> &RHS) { return *LHS < *RHS; });
1189
1190   return MaxCandidateLen;
1191 }
1192
1193 MachineFunction *
1194 MachineOutliner::createOutlinedFunction(Module &M, const OutlinedFunction &OF,
1195                                         InstructionMapper &Mapper) {
1196
1197   // Create the function name. This should be unique. For now, just hash the
1198   // module name and include it in the function name plus the number of this
1199   // function.
1200   std::ostringstream NameStream;
1201   NameStream << "OUTLINED_FUNCTION_" << OF.Name;
1202
1203   // Create the function using an IR-level function.
1204   LLVMContext &C = M.getContext();
1205   Function *F = dyn_cast<Function>(
1206       M.getOrInsertFunction(NameStream.str(), Type::getVoidTy(C)));
1207   assert(F && "Function was null!");
1208
1209   // NOTE: If this is linkonceodr, then we can take advantage of linker deduping
1210   // which gives us better results when we outline from linkonceodr functions.
1211   F->setLinkage(GlobalValue::PrivateLinkage);
1212   F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
1213
1214   BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
1215   IRBuilder<> Builder(EntryBB);
1216   Builder.CreateRetVoid();
1217
1218   MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1219   MachineFunction &MF = MMI.getOrCreateMachineFunction(*F);
1220   MachineBasicBlock &MBB = *MF.CreateMachineBasicBlock();
1221   const TargetSubtargetInfo &STI = MF.getSubtarget();
1222   const TargetInstrInfo &TII = *STI.getInstrInfo();
1223
1224   // Insert the new function into the module.
1225   MF.insert(MF.begin(), &MBB);
1226
1227   TII.insertOutlinerPrologue(MBB, MF, OF.MInfo);
1228
1229   // Copy over the instructions for the function using the integer mappings in
1230   // its sequence.
1231   for (unsigned Str : OF.Sequence) {
1232     MachineInstr *NewMI =
1233         MF.CloneMachineInstr(Mapper.IntegerInstructionMap.find(Str)->second);
1234     NewMI->dropMemRefs();
1235
1236     // Don't keep debug information for outlined instructions.
1237     // FIXME: This means outlined functions are currently undebuggable.
1238     NewMI->setDebugLoc(DebugLoc());
1239     MBB.insert(MBB.end(), NewMI);
1240   }
1241
1242   TII.insertOutlinerEpilogue(MBB, MF, OF.MInfo);
1243
1244   return &MF;
1245 }
1246
1247 bool MachineOutliner::outline(
1248     Module &M, const ArrayRef<std::shared_ptr<Candidate>> &CandidateList,
1249     std::vector<OutlinedFunction> &FunctionList, InstructionMapper &Mapper) {
1250
1251   bool OutlinedSomething = false;
1252   // Replace the candidates with calls to their respective outlined functions.
1253   for (const std::shared_ptr<Candidate> &Cptr : CandidateList) {
1254     Candidate &C = *Cptr;
1255     // Was the candidate removed during pruneOverlaps?
1256     if (!C.InCandidateList)
1257       continue;
1258
1259     // If not, then look at its OutlinedFunction.
1260     OutlinedFunction &OF = FunctionList[C.FunctionIdx];
1261
1262     // Was its OutlinedFunction made unbeneficial during pruneOverlaps?
1263     if (OF.getBenefit() < 1)
1264       continue;
1265
1266     // If not, then outline it.
1267     assert(C.getStartIdx() < Mapper.InstrList.size() &&
1268            "Candidate out of bounds!");
1269     MachineBasicBlock *MBB = (*Mapper.InstrList[C.getStartIdx()]).getParent();
1270     MachineBasicBlock::iterator StartIt = Mapper.InstrList[C.getStartIdx()];
1271     unsigned EndIdx = C.getEndIdx();
1272
1273     assert(EndIdx < Mapper.InstrList.size() && "Candidate out of bounds!");
1274     MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
1275     assert(EndIt != MBB->end() && "EndIt out of bounds!");
1276
1277     EndIt++; // Erase needs one past the end index.
1278
1279     // Does this candidate have a function yet?
1280     if (!OF.MF) {
1281       OF.MF = createOutlinedFunction(M, OF, Mapper);
1282       MachineBasicBlock *MBB = &*OF.MF->begin();
1283
1284       // Output a remark telling the user that an outlined function was created,
1285       // and explaining where it came from.
1286       MachineOptimizationRemarkEmitter MORE(*OF.MF, nullptr);
1287       MachineOptimizationRemark R(DEBUG_TYPE, "OutlinedFunction",
1288                                   MBB->findDebugLoc(MBB->begin()), MBB);
1289       R << "Saved " << NV("OutliningBenefit", OF.getBenefit())
1290         << " instructions by "
1291         << "outlining " << NV("Length", OF.Sequence.size()) << " instructions "
1292         << "from " << NV("NumOccurrences", OF.getOccurrenceCount())
1293         << " locations. "
1294         << "(Found at: ";
1295
1296       // Tell the user the other places the candidate was found.
1297       for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {
1298
1299         // Skip over things that were pruned.
1300         if (!OF.Candidates[i]->InCandidateList)
1301           continue;
1302
1303         R << NV(
1304             (Twine("StartLoc") + Twine(i)).str(),
1305             Mapper.InstrList[OF.Candidates[i]->getStartIdx()]->getDebugLoc());
1306         if (i != e - 1)
1307           R << ", ";
1308       }
1309
1310       R << ")";
1311
1312       MORE.emit(R);
1313       FunctionsCreated++;
1314     }
1315
1316     MachineFunction *MF = OF.MF;
1317     const TargetSubtargetInfo &STI = MF->getSubtarget();
1318     const TargetInstrInfo &TII = *STI.getInstrInfo();
1319
1320     // Insert a call to the new function and erase the old sequence.
1321     TII.insertOutlinedCall(M, *MBB, StartIt, *MF, C.MInfo);
1322     StartIt = Mapper.InstrList[C.getStartIdx()];
1323     MBB->erase(StartIt, EndIt);
1324
1325     OutlinedSomething = true;
1326
1327     // Statistics.
1328     NumOutlined++;
1329   }
1330
1331   DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n";);
1332
1333   return OutlinedSomething;
1334 }
1335
1336 bool MachineOutliner::runOnModule(Module &M) {
1337
1338   // Is there anything in the module at all?
1339   if (M.empty())
1340     return false;
1341
1342   MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
1343   const TargetSubtargetInfo &STI =
1344       MMI.getOrCreateMachineFunction(*M.begin()).getSubtarget();
1345   const TargetRegisterInfo *TRI = STI.getRegisterInfo();
1346   const TargetInstrInfo *TII = STI.getInstrInfo();
1347
1348   InstructionMapper Mapper;
1349
1350   // Build instruction mappings for each function in the module.
1351   for (Function &F : M) {
1352     MachineFunction &MF = MMI.getOrCreateMachineFunction(F);
1353
1354     // Is the function empty? Safe to outline from?
1355     if (F.empty() ||
1356         !TII->isFunctionSafeToOutlineFrom(MF, OutlineFromLinkOnceODRs))
1357       continue;
1358
1359     // If it is, look at each MachineBasicBlock in the function.
1360     for (MachineBasicBlock &MBB : MF) {
1361
1362       // Is there anything in MBB?
1363       if (MBB.empty())
1364         continue;
1365
1366       // If yes, map it.
1367       Mapper.convertToUnsignedVec(MBB, *TRI, *TII);
1368     }
1369   }
1370
1371   // Construct a suffix tree, use it to find candidates, and then outline them.
1372   SuffixTree ST(Mapper.UnsignedVec);
1373   std::vector<std::shared_ptr<Candidate>> CandidateList;
1374   std::vector<OutlinedFunction> FunctionList;
1375
1376   // Find all of the outlining candidates.
1377   unsigned MaxCandidateLen =
1378       buildCandidateList(CandidateList, FunctionList, ST, Mapper, *TII);
1379
1380   // Remove candidates that overlap with other candidates.
1381   pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen, *TII);
1382
1383   // Outline each of the candidates and return true if something was outlined.
1384   return outline(M, CandidateList, FunctionList, Mapper);
1385 }