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