--- a/lib/CodeGen/MachineOutliner.cpp	Fri Feb 16 19:10:49 2018 +0900
+++ b/lib/CodeGen/MachineOutliner.cpp	Sat Feb 17 09:57:20 2018 +0900
@@ -59,20 +59,20 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Twine.h"
-#include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetRegisterInfo.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
+#include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Mangler.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/Target/TargetSubtargetInfo.h"
 #include <functional>
 #include <map>
 #include <sstream>
@@ -99,6 +99,9 @@
   /// The number of instructions in this \p Candidate.
   unsigned Len;
 
+  /// The MachineFunction containing this \p Candidate.
+  MachineFunction *MF = nullptr;
+
 public:
   /// Set to false if the candidate overlapped with another candidate.
   bool InCandidateList = true;
@@ -110,6 +113,15 @@
   /// Contains all target-specific information for this \p Candidate.
   TargetInstrInfo::MachineOutlinerInfo MInfo;
 
+  /// If there is a DISubprogram associated with the function that this
+  /// Candidate lives in, return it.
+  DISubprogram *getSubprogramOrNull() const {
+    assert(MF && "Candidate has no MF!");
+    if (DISubprogram *SP = MF->getFunction().getSubprogram())
+      return SP;
+    return nullptr;
+  }
+
   /// Return the number of instructions in this Candidate.
   unsigned getLength() const { return Len; }
 
@@ -128,8 +140,9 @@
   /// for some given candidate.
   unsigned Benefit = 0;
 
-  Candidate(unsigned StartIdx, unsigned Len, unsigned FunctionIdx)
-      : StartIdx(StartIdx), Len(Len), FunctionIdx(FunctionIdx) {}
+  Candidate(unsigned StartIdx, unsigned Len, unsigned FunctionIdx,
+            MachineFunction *MF)
+      : StartIdx(StartIdx), Len(Len), MF(MF), FunctionIdx(FunctionIdx) {}
 
   Candidate() {}
 
@@ -165,6 +178,15 @@
   /// Contains all target-specific information for this \p OutlinedFunction.
   TargetInstrInfo::MachineOutlinerInfo MInfo;
 
+  /// If there is a DISubprogram for any Candidate for this outlined function,
+  /// then return it. Otherwise, return nullptr.
+  DISubprogram *getSubprogramOrNull() const {
+    for (const auto &C : Candidates)
+      if (DISubprogram *SP = C->getSubprogramOrNull())
+        return SP;
+    return nullptr;
+  }
+
   /// Return the number of candidates for this \p OutlinedFunction.
   unsigned getOccurrenceCount() { return OccurrenceCount; }
 
@@ -723,11 +745,13 @@
   void convertToUnsignedVec(MachineBasicBlock &MBB,
                             const TargetRegisterInfo &TRI,
                             const TargetInstrInfo &TII) {
+    unsigned Flags = TII.getMachineOutlinerMBBFlags(MBB);
+
     for (MachineBasicBlock::iterator It = MBB.begin(), Et = MBB.end(); It != Et;
          It++) {
 
       // Keep track of where this instruction is in the module.
-      switch (TII.getOutliningType(*It)) {
+      switch (TII.getOutliningType(It, Flags)) {
       case TargetInstrInfo::MachineOutlinerInstrType::Illegal:
         mapToIllegalUnsigned(It);
         break;
@@ -777,6 +801,9 @@
   /// linkonceodr linkage.
   bool OutlineFromLinkOnceODRs = false;
 
+  // Collection of IR functions created by the outliner.
+  std::vector<Function *> CreatedIRFunctions;
+
   StringRef getPassName() const override { return "Machine Outliner"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
@@ -939,17 +966,52 @@
       SuffixTreeNode *M = ChildPair.second;
 
       if (M && M->IsInTree && M->isLeaf()) {
-        // Each sequence is over [StartIt, EndIt].
-        MachineBasicBlock::iterator StartIt = Mapper.InstrList[M->SuffixIdx];
-        MachineBasicBlock::iterator EndIt =
-            Mapper.InstrList[M->SuffixIdx + StringLen - 1];
-
-        CandidatesForRepeatedSeq.emplace_back(M->SuffixIdx, StringLen,
-                                              FunctionList.size());
-        RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt));
-
         // Never visit this leaf again.
         M->IsInTree = false;
+        unsigned StartIdx = M->SuffixIdx;
+        unsigned EndIdx = StartIdx + StringLen - 1;
+
+        // Trick: Discard some candidates that would be incompatible with the
+        // ones we've already found for this sequence. This will save us some
+        // work in candidate selection.
+        //
+        // If two candidates overlap, then we can't outline them both. This
+        // happens when we have candidates that look like, say
+        //
+        // AA (where each "A" is an instruction).
+        //
+        // We might have some portion of the module that looks like this:
+        // AAAAAA (6 A's) 
+        //
+        // In this case, there are 5 different copies of "AA" in this range, but
+        // at most 3 can be outlined. If only outlining 3 of these is going to
+        // be unbeneficial, then we ought to not bother.
+        //
+        // Note that two things DON'T overlap when they look like this:
+        // start1...end1 .... start2...end2
+        // That is, one must either
+        // * End before the other starts
+        // * Start after the other ends
+        if (std::all_of(CandidatesForRepeatedSeq.begin(),
+                        CandidatesForRepeatedSeq.end(),
+                        [&StartIdx, &EndIdx](const Candidate &C) {
+                          return (EndIdx < C.getStartIdx() ||
+                                  StartIdx > C.getEndIdx()); 
+                        })) {
+          // It doesn't overlap with anything, so we can outline it.
+          // Each sequence is over [StartIt, EndIt].
+          MachineBasicBlock::iterator StartIt = Mapper.InstrList[StartIdx];
+          MachineBasicBlock::iterator EndIt = Mapper.InstrList[EndIdx];
+
+          // Save the MachineFunction containing the Candidate.
+          MachineFunction *MF = StartIt->getParent()->getParent();
+          assert(MF && "Candidate doesn't have a MF?");
+
+          // Save the candidate and its location.
+          CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen,
+                                                FunctionList.size(), MF);
+          RepeatedSequenceLocs.emplace_back(std::make_pair(StartIt, EndIt));
+        }
       }
     }
 
@@ -961,8 +1023,8 @@
     std::vector<unsigned> Seq;
     for (unsigned i = Leaf->SuffixIdx; i < Leaf->SuffixIdx + StringLen; i++)
       Seq.push_back(ST.Str[i]);
-    OutlinedFunction OF(FunctionList.size(), Parent.OccurrenceCount, Seq,
-                        MInfo);
+    OutlinedFunction OF(FunctionList.size(), CandidatesForRepeatedSeq.size(),
+                        Seq, MInfo);
     unsigned Benefit = OF.getBenefit();
 
     // Is it better to outline this candidate than not?
@@ -1091,7 +1153,7 @@
     if (C1.getStartIdx() > MaxCandidateLen)
       FarthestPossibleIdx = C1.getStartIdx() - MaxCandidateLen;
 
-    // Compare against the candidates in the list that start at at most
+    // Compare against the candidates in the list that start at most
     // FarthestPossibleIdx indices away from C1. There are at most
     // MaxCandidateLen of these.
     for (auto Sit = It + 1; Sit != Et; Sit++) {
@@ -1180,6 +1242,9 @@
   F->setLinkage(GlobalValue::PrivateLinkage);
   F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 
+  // Save F so that we can add debug info later if we need to.
+  CreatedIRFunctions.push_back(F);
+
   BasicBlock *EntryBB = BasicBlock::Create(C, "entry", F);
   IRBuilder<> Builder(EntryBB);
   Builder.CreateRetVoid();
@@ -1203,13 +1268,51 @@
     NewMI->dropMemRefs();
 
     // Don't keep debug information for outlined instructions.
-    // FIXME: This means outlined functions are currently undebuggable.
     NewMI->setDebugLoc(DebugLoc());
     MBB.insert(MBB.end(), NewMI);
   }
 
   TII.insertOutlinerEpilogue(MBB, MF, OF.MInfo);
 
+  // If there's a DISubprogram associated with this outlined function, then
+  // emit debug info for the outlined function.
+  if (DISubprogram *SP = OF.getSubprogramOrNull()) {
+    // We have a DISubprogram. Get its DICompileUnit.
+    DICompileUnit *CU = SP->getUnit();
+    DIBuilder DB(M, true, CU);
+    DIFile *Unit = SP->getFile();
+    Mangler Mg;
+
+    // Walk over each IR function we created in the outliner and create
+    // DISubprograms for each function.
+    for (Function *F : CreatedIRFunctions) {
+      // Get the mangled name of the function for the linkage name.
+      std::string Dummy;
+      llvm::raw_string_ostream MangledNameStream(Dummy);
+      Mg.getNameWithPrefix(MangledNameStream, F, false);
+
+      DISubprogram *SP = DB.createFunction(
+          Unit /* Context */, F->getName(), StringRef(MangledNameStream.str()),
+          Unit /* File */,
+          0 /* Line 0 is reserved for compiler-generated code. */,
+          DB.createSubroutineType(
+              DB.getOrCreateTypeArray(None)), /* void type */
+          false, true, 0, /* Line 0 is reserved for compiler-generated code. */
+          DINode::DIFlags::FlagArtificial /* Compiler-generated code. */,
+          true /* Outlined code is optimized code by definition. */);
+
+      // Don't add any new variables to the subprogram.
+      DB.finalizeSubprogram(SP);
+
+      // Attach subprogram to the function.
+      F->setSubprogram(SP);
+    }
+
+    // We're done with the DIBuilder.
+    DB.finalize();
+  }
+
+  MF.getRegInfo().freezeReservedRegs(MF);
   return &MF;
 }
 
@@ -1313,7 +1416,7 @@
       MMI.getOrCreateMachineFunction(*M.begin()).getSubtarget();
   const TargetRegisterInfo *TRI = STI.getRegisterInfo();
   const TargetInstrInfo *TII = STI.getInstrInfo();
-
+  
   InstructionMapper Mapper;
 
   // Build instruction mappings for each function in the module.
@@ -1328,8 +1431,8 @@
     // If it is, look at each MachineBasicBlock in the function.
     for (MachineBasicBlock &MBB : MF) {
 
-      // Is there anything in MBB?
-      if (MBB.empty())
+      // Is there anything in MBB? And is it the target of an indirect branch?
+      if (MBB.empty() || MBB.hasAddressTaken())
         continue;
 
       // If yes, map it.
@@ -1350,5 +1453,7 @@
   pruneOverlaps(CandidateList, FunctionList, Mapper, MaxCandidateLen, *TII);
 
   // Outline each of the candidates and return true if something was outlined.
-  return outline(M, CandidateList, FunctionList, Mapper);
+  bool OutlinedSomething = outline(M, CandidateList, FunctionList, Mapper);
+
+  return OutlinedSomething;
 }