[DebugInfo] Avoid a quadratic-complexity corner case in LiveDebugValues

[jmorse]

Summary

Long ago [0], it was identified that part of LiveDebugValues had worst-case quadratic complexity. We test [1] whether a variable location would still be in scope when propagated into a block, to avoid needlessly propagating locations. If you have a block of DBG_VALUEs, all for different variables, then the LexicalScopes::dominates method will scan each instruction for each variable location, which is O(n^2). It doesn't appear to have been judged a high risk at the time.

We've run into a circumstance where this happens, once again with large amounts of inlining into a large basic block. To avoid the quadratic complexity, I think we can rely on the scope ranges that are computed in each LexicalScope object [2]. These identify spans of the function that the lexical scope contains. Crucially, these spans cover all subscopes [3] as well. This patch changes the LexicalScopes::dominates method to, rather than testing each instruction in a block to see if it's dominated, instead test whether this block is in the set of dominated instructions blocks. (Which is a mouthful). This also involves fixing the getMachineBasicBlocks method, which didn't seem to be aware that each span could cover multiple blocks.

This patch eliminates the performance problem we encountered, and the complexity of LexicalScopes::dominates becomes linear with the size of the scope (measured in blocks), rather than the number of instructions in this block. The worst case would now be a circumstance where there are a large number of variable locations in a lexical scope that covers a large number of blocks (meaning we had to iterate over many blocks on each call to dominates). This, I believe, is not a circumstance that the inliner tries to create, as opposed to "many inlined scopes in one large block", which it does.

I tried building clang-3.4 with this patch applied, and there was no observable change in compile time (I guess it doesn't hit the worst case). I also tried building a stage2 build of clang with itself, with both implementations of LexicalScopes::dominates, comparing their answers. This showed up that the (current) implementation of dominates will interpret a metainstruction as being dominated , instead of ignoring it like the rest of LexicalScopes [4]. Aside from that, both implementations of dominates agreed in all their results.

No test because this is a performance patch, although I can add one for the "don't consider metainstructions in scope dominance queries" matter if that's important.

[0] https://reviews.llvm.org/D24994#inline-215341
[1] https://github.com/llvm/llvm-project/blob/3ae11b42818363f70b3c6b0246bb617e35709c58/llvm/lib/CodeGen/LiveDebugValues.cpp#L1328
[2] https://github.com/llvm/llvm-project/blob/3ae11b42818363f70b3c6b0246bb617e35709c58/llvm/include/llvm/CodeGen/LexicalScopes.h#L129
[3] https://github.com/llvm/llvm-project/blob/3ae11b42818363f70b3c6b0246bb617e35709c58/llvm/include/llvm/CodeGen/LexicalScopes.h#L76
[4] https://github.com/llvm/llvm-project/blob/3ae11b42818363f70b3c6b0246bb617e35709c58/llvm/lib/CodeGen/LexicalScopes.cpp#L92

[aprantl]

We don't have an existing unit test for LexicalScopes that generates IR manually and tests a few common queries, do we?

llvm/lib/CodeGen/LexicalScopes.cpp

300

Perhaps I'm missing something, but this looks like a really complicated way of writing a for(;;) loop?

322

return Set.count(MBB);

is idiomatic, I think.

[vsk]

llvm/lib/CodeGen/LexicalScopes.cpp

322

Does a LexicalScope always start at a MachineBasicBlock boundary? I.e. can Set.count(MBB) be non-zero even if no instruction in MBB has a location dominated by Scope?

[jmorse]

Adrian wrote:

We don't have an existing unit test for LexicalScopes that generates IR manually and tests a few common queries, do we?

Alas no, there doesn't appear to be any testing of LexicalScopes at all.

llvm/lib/CodeGen/LexicalScopes.cpp

300

It looks like I was missing caffeine at the time; I'll switch this to a for loop,

322

LexicalScopes don't always start at block boundaries; but the ranges only ever cover those instructions that are definitely part of the scope, and are inclusive, so if one had:

entry:
  // instructions in scope 1
  b %someblock
unrelated:
  // instructions in scope 2
  b %another block
someblock:
  // instructions in scope 1
  ret

And scope 2 was not a child of scope 1, then there would be two instruction ranges covering the "entry" and "someblock" block. The beginning and end of the ranges would point at instructions entirely in those two blocks, and "unrelated" wouldn't be reported as being in scope 1.

[aprantl]

In D73725#1851836, @jmorse wrote:

Adrian wrote:

We don't have an existing unit test for LexicalScopes that generates IR manually and tests a few common queries, do we?

Alas no, there doesn't appear to be any testing of LexicalScopes at all.

I'm not going to make you write one, but this would be a great opportunity ;-)

[jmorse]

In D73725#1852265, @aprantl wrote:

I'm not going to make you write one, but this would be a great opportunity ;-)

Well, I've never written any LLVM unit tests before, so "how hard can it be" :), I'll give it a shot.

[jmorse]

I've added some unit tests; without the patch to LexicalScopes.cpp, these failures occur:

[ RUN      ] LexicalScopesTest.TestGetBlocks
/fast/fs/llvm-project/llvm/unittests/CodeGen/LexicalScopesTest.cpp:410: Failure
      Expected: NotNestedBlockBlocks.count(MBB3)
      Which is: 0
To be equal to: 1u
      Which is: 1
[  FAILED  ] LexicalScopesTest.TestGetBlocks (1 ms)
[ RUN      ] LexicalScopesTest.TestMetaInst
/fast/fs/llvm-project/llvm/unittests/CodeGen/LexicalScopesTest.cpp:452: Failure
Value of: LS.dominates(InBlockLoc.get(), MBB2)
  Actual: true
Expected: false
/fast/fs/llvm-project/llvm/unittests/CodeGen/LexicalScopesTest.cpp:453: Failure
Value of: LS.dominates(InBlockLoc.get(), MBB3)
  Actual: true
Expected: false
[  FAILED  ] LexicalScopesTest.TestMetaInst (0 ms)

Which pass with the patch applied. The other tests are in for just general good coverage. It's generally unclear to me how much bogus / fake / mock implementation to rely on, it might be that manipulating MCInstrDesc structs directly isn't clever. I couldn't see another way of generating instructions without a backend though.

I've also split out some boilerplate code for generating machine functions into MFCommon.inc from the machine instruction tests.

[aprantl]

Thanks!

llvm/lib/CodeGen/LexicalScopes.cpp

302

And now that it's simplified, this looks like we should use something like std::copy() instead of a loop :-)

llvm/unittests/CodeGen/LexicalScopesTest.cpp

2

Super-nit: expand this to column 80?

54

Very cool! Should we fire up artist-mode and put the CFG into an ASCII art comment? (mostly joking)

113

.

[jmorse]

llvm/lib/CodeGen/LexicalScopes.cpp

302

I don't think std::copy can be used, there needs to be some conversion between MBB references to MBB pointers. There might be some way of doing this automagically, possibly using std::decay, however my C++-fu is weak.

llvm/lib/CodeGen/LexicalScopes.cpp

if (!Scope)
     return;
 
   if (Scope == CurrentFnLexicalScope) {
     for (const auto &MBB : *MF)
       MBBs.insert(&MBB);
     return;
   }
 
+  // The scope ranges can cover multiple basic blocks in each span. Iterate over
+  // all blocks (in the order they are in the function) until we reach the one
+  // containing the end of the span.
   SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
   for (auto &R : InsnRanges)
-    MBBs.insert(R.first->getParent());
+    for (auto CurMBBIt = R.first->getParent()->getIterator(),
+              EndBBIt = std::next(R.second->getParent()->getIterator());
+         CurMBBIt != EndBBIt; CurMBBIt++)
+      MBBs.insert(&*CurMBBIt);
 }
 
 /// dominates - Return true if DebugLoc's lexical scope dominates at least one
 /// machine instruction's lexical scope in a given machine basic block.
 bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) {
   assert(MF && "Unexpected uninitialized LexicalScopes object!");
   LexicalScope *Scope = getOrCreateLexicalScope(DL);
   if (!Scope)
     return false;
 
   // Current function scope covers all basic blocks in the function.
   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
     return true;
 
-  bool Result = false;
-  for (auto &I : *MBB) {
-    if (const DILocation *IDL = I.getDebugLoc())
-      if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
-        if (Scope->dominates(IScope))
-          return true;
-  }
-  return Result;
+  // Fetch all the blocks in DLs scope. Because the range / block list also
+  // contain any subscopes, any instruction that DL dominates can be found
+  // in the block set.
+  SmallPtrSet<const MachineBasicBlock *, 32> Set;
+  getMachineBasicBlocks(DL, Set);
+  return Set.count(MBB) != 0;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {
   raw_ostream &err = dbgs();
   err.indent(Indent);
   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
   const MDNode *N = Desc;

llvm/unittests/CodeGen/CMakeLists.txt

set(LLVM_LINK_COMPONENTS
   Support
   Target
   )
 
 add_llvm_unittest(CodeGenTests
   AArch64SelectionDAGTest.cpp
   DIEHashTest.cpp
   LowLevelTypeTest.cpp
+  LexicalScopesTest.cpp
   MachineInstrBundleIteratorTest.cpp
   MachineInstrTest.cpp
   MachineOperandTest.cpp
   ScalableVectorMVTsTest.cpp
   TypeTraitsTest.cpp
   TargetOptionsTest.cpp
   )
 
 add_subdirectory(GlobalISel)

llvm/unittests/CodeGen/LexicalScopesTest.cpp

+//===----------- llvm/unittest/CodeGen/LexicalScopesTest.cpp --------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/LexicalScopes.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineMemOperand.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/TargetFrameLowering.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/CodeGen/TargetLowering.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
+#include "llvm/IR/DIBuilder.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/ModuleSlotTracker.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCSymbol.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetOptions.h"
+
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+// Include helper functions to ease the manipulation of MachineFunctions
+#include "MFCommon.inc"
+
+class LexicalScopesTest : public testing::Test {
+public:
+  // Boilerplate,
+  LLVMContext Ctx;
+  Module Mod;
+  std::unique_ptr<MachineFunction> MF;
+  DICompileUnit *OurCU;
+  DIFile *OurFile;
+  DISubprogram *OurFunc;
+  DILexicalBlock *OurBlock, *AnotherBlock;
+  DISubprogram *ToInlineFunc;
+  DILexicalBlock *ToInlineBlock;
+  // DebugLocs that we'll used to create test environments.
+  DebugLoc OutermostLoc, InBlockLoc, NotNestedBlockLoc, InlinedLoc;
+
+  // Test environment blocks -- these form a diamond control flow pattern,
+  // MBB1 being the entry block, blocks two and three being the branches, and
+  // block four joining the branches and being an exit block.
+  MachineBasicBlock *MBB1, *MBB2, *MBB3, *MBB4;
+
+  // Some meaningless instructions -- the first is fully meaningless,
+  // while the second is supposed to impersonate DBG_VALUEs through its
+  // opcode.
+  MCInstrDesc BeanInst;
+  MCInstrDesc DbgValueInst;
+
+  LexicalScopesTest() : Ctx(), Mod("beehives", Ctx) {
+    memset(&BeanInst, 0, sizeof(BeanInst));
+    BeanInst.Opcode = 1;
+    BeanInst.Size = 1;
+
+    memset(&DbgValueInst, 0, sizeof(DbgValueInst));
+    DbgValueInst.Opcode = TargetOpcode::DBG_VALUE;
+    DbgValueInst.Size = 1;
+
+    // Boilerplate that creates a MachineFunction and associated blocks.
+    MF = createMachineFunction(Ctx, Mod);
+    llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
+    auto BB1 = BasicBlock::Create(Ctx, "a", &F);
+    auto BB2 = BasicBlock::Create(Ctx, "b", &F);
+    auto BB3 = BasicBlock::Create(Ctx, "c", &F);
+    auto BB4 = BasicBlock::Create(Ctx, "d", &F);
+    IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4);
+    IRB1.CreateBr(BB2);
+    IRB2.CreateBr(BB3);
+    IRB3.CreateBr(BB4);
+    IRB4.CreateRetVoid();
+    MBB1 = MF->CreateMachineBasicBlock(BB1);
+    MF->insert(MF->end(), MBB1);
+    MBB2 = MF->CreateMachineBasicBlock(BB2);
+    MF->insert(MF->end(), MBB2);
+    MBB3 = MF->CreateMachineBasicBlock(BB3);
+    MF->insert(MF->end(), MBB3);
+    MBB4 = MF->CreateMachineBasicBlock(BB4);
+    MF->insert(MF->end(), MBB4);
+    MBB1->addSuccessor(MBB2);
+    MBB1->addSuccessor(MBB3);
+    MBB2->addSuccessor(MBB4);
+    MBB3->addSuccessor(MBB4);
+
+    // Create metadata: CU, subprogram, some blocks and an inline function
+    // scope.
+    DIBuilder DIB(Mod);
+    OurFile = DIB.createFile("xyzzy.c", "/cave");
+    OurCU =
+        DIB.createCompileUnit(dwarf::DW_LANG_C99, OurFile, "nou", false, "", 0);
+    auto OurSubT = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None));
+    OurFunc =
+        DIB.createFunction(OurCU, "bees", "", OurFile, 1, OurSubT, 1,
+                           DINode::FlagZero, DISubprogram::SPFlagDefinition);
+    F.setSubprogram(OurFunc);
+    OurBlock = DIB.createLexicalBlock(OurFunc, OurFile, 2, 3);
+    AnotherBlock = DIB.createLexicalBlock(OurFunc, OurFile, 2, 6);
+    ToInlineFunc =
+        DIB.createFunction(OurFile, "shoes", "", OurFile, 10, OurSubT, 10,
+                           DINode::FlagZero, DISubprogram::SPFlagDefinition);
+
+    // Make some nested scopes.
+    OutermostLoc = DebugLoc::get(3, 1, OurFunc);
+    InBlockLoc = DebugLoc::get(4, 1, OurBlock);
+    InlinedLoc = DebugLoc::get(10, 1, ToInlineFunc, InBlockLoc.get());
+
+    // Make a scope that isn't nested within the others.
+    NotNestedBlockLoc = DebugLoc::get(4, 1, AnotherBlock);
+
+    DIB.finalize();
+  }
+};
+
+// Fill blocks with dummy instructions, test some base lexical scope
+// functionaliy.
+TEST_F(LexicalScopesTest, FlatLayout) {
+  BuildMI(*MBB1, MBB1->end(), OutermostLoc, BeanInst);
+  BuildMI(*MBB2, MBB2->end(), OutermostLoc, BeanInst);
+  BuildMI(*MBB3, MBB3->end(), OutermostLoc, BeanInst);
+  BuildMI(*MBB4, MBB4->end(), OutermostLoc, BeanInst);
+
+  LexicalScopes LS;
+  EXPECT_TRUE(LS.empty());
+  LS.reset();
+  EXPECT_EQ(LS.getCurrentFunctionScope(), nullptr);
+
+  LS.initialize(*MF);
+  EXPECT_FALSE(LS.empty());
+  LexicalScope *FuncScope = LS.getCurrentFunctionScope();
+  EXPECT_EQ(FuncScope->getParent(), nullptr);
+  EXPECT_EQ(FuncScope->getDesc(), OurFunc);
+  EXPECT_EQ(FuncScope->getInlinedAt(), nullptr);
+  EXPECT_EQ(FuncScope->getScopeNode(), OurFunc);
+  EXPECT_FALSE(FuncScope->isAbstractScope());
+  EXPECT_EQ(FuncScope->getChildren().size(), 0u);
+
+  // There should be one range, covering the whole function. Test that it
+  // points at the correct instructions.
+  auto &Ranges = FuncScope->getRanges();
+  ASSERT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges.front().first, &*MF->begin()->begin());
+  auto BBIt = MF->end();
+  BBIt = std::prev(BBIt);
+  EXPECT_EQ(Ranges.front().second, &*BBIt->begin());
+
+  EXPECT_TRUE(FuncScope->dominates(FuncScope));
+  SmallPtrSet<const MachineBasicBlock *, 4> MBBVec;
+  LS.getMachineBasicBlocks(OutermostLoc.get(), MBBVec);
+
+  EXPECT_EQ(MBBVec.size(), 4u);
+  // All the blocks should be in that set; the outermost loc should dominate
+  // them; and no other scope should.
+  for (auto &MBB : *MF) {
+    EXPECT_EQ(MBBVec.count(&MBB), 1u);
+    EXPECT_TRUE(LS.dominates(OutermostLoc.get(), &MBB));
+    EXPECT_FALSE(LS.dominates(InBlockLoc.get(), &MBB));
+    EXPECT_FALSE(LS.dominates(InlinedLoc.get(), &MBB));
+  }
+}
+
+// Examine relationship between two nested scopes inside the function, the
+// outer function and the lexical block within it.
+TEST_F(LexicalScopesTest, BlockScopes) {
+  BuildMI(*MBB1, MBB1->end(), InBlockLoc, BeanInst);
+  BuildMI(*MBB2, MBB2->end(), InBlockLoc, BeanInst);
+  BuildMI(*MBB3, MBB3->end(), InBlockLoc, BeanInst);
+  BuildMI(*MBB4, MBB4->end(), InBlockLoc, BeanInst);
+
+  LexicalScopes LS;
+  LS.initialize(*MF);
+  LexicalScope *FuncScope = LS.getCurrentFunctionScope();
+  EXPECT_EQ(FuncScope->getDesc(), OurFunc);
+  auto &Children = FuncScope->getChildren();
+  ASSERT_EQ(Children.size(), 1u);
+  auto *BlockScope = Children[0];
+  EXPECT_EQ(LS.findLexicalScope(InBlockLoc.get()), BlockScope);
+  EXPECT_EQ(BlockScope->getDesc(), InBlockLoc->getScope());
+  EXPECT_FALSE(BlockScope->isAbstractScope());
+
+  EXPECT_TRUE(FuncScope->dominates(BlockScope));
+  EXPECT_FALSE(BlockScope->dominates(FuncScope));
+  EXPECT_EQ(FuncScope->getParent(), nullptr);
+  EXPECT_EQ(BlockScope->getParent(), FuncScope);
+
+  SmallPtrSet<const MachineBasicBlock *, 4> MBBVec;
+  LS.getMachineBasicBlocks(OutermostLoc.get(), MBBVec);
+
+  EXPECT_EQ(MBBVec.size(), 4u);
+  for (auto &MBB : *MF) {
+    EXPECT_EQ(MBBVec.count(&MBB), 1u);
+    EXPECT_TRUE(LS.dominates(OutermostLoc.get(), &MBB));
+    EXPECT_TRUE(LS.dominates(InBlockLoc.get(), &MBB));
+    EXPECT_FALSE(LS.dominates(InlinedLoc.get(), &MBB));
+  }
+}
+
+// Test inlined scopes functionality and relationship with the outer scopes.
+TEST_F(LexicalScopesTest, InlinedScopes) {
+  BuildMI(*MBB1, MBB1->end(), InlinedLoc, BeanInst);
+  BuildMI(*MBB2, MBB2->end(), InlinedLoc, BeanInst);
+  BuildMI(*MBB3, MBB3->end(), InlinedLoc, BeanInst);
+  BuildMI(*MBB4, MBB4->end(), InlinedLoc, BeanInst);
+
+  LexicalScopes LS;
+  LS.initialize(*MF);
+  LexicalScope *FuncScope = LS.getCurrentFunctionScope();
+  auto &Children = FuncScope->getChildren();
+  ASSERT_EQ(Children.size(), 1u);
+  auto *BlockScope = Children[0];
+  auto &BlockChildren = BlockScope->getChildren();
+  ASSERT_EQ(BlockChildren.size(), 1u);
+  auto *InlinedScope = BlockChildren[0];
+
+  EXPECT_FALSE(InlinedScope->isAbstractScope());
+  EXPECT_EQ(InlinedScope->getInlinedAt(), InlinedLoc.getInlinedAt());
+  EXPECT_EQ(InlinedScope->getDesc(), InlinedLoc.getScope());
+  EXPECT_EQ(InlinedScope->getChildren().size(), 0u);
+
+  EXPECT_EQ(FuncScope->getParent(), nullptr);
+  EXPECT_EQ(BlockScope->getParent(), FuncScope);
+  EXPECT_EQ(InlinedScope->getParent(), BlockScope);
+
+  const auto &AbstractScopes = LS.getAbstractScopesList();
+  ASSERT_EQ(AbstractScopes.size(), 1u);
+  const auto &AbstractScope = *AbstractScopes[0];
+  EXPECT_TRUE(AbstractScope.isAbstractScope());
+  EXPECT_EQ(AbstractScope.getDesc(), InlinedLoc.getScope());
+  EXPECT_EQ(AbstractScope.getInlinedAt(), nullptr);
+  EXPECT_EQ(AbstractScope.getParent(), nullptr);
+}
+
+// Test behaviour in a function that has empty DebugLocs.
+TEST_F(LexicalScopesTest, FuncWithEmptyGap) {
+  BuildMI(*MBB1, MBB1->end(), OutermostLoc, BeanInst);
+  BuildMI(*MBB2, MBB2->end(), DebugLoc(), BeanInst);
+  BuildMI(*MBB3, MBB3->end(), DebugLoc(), BeanInst);
+  BuildMI(*MBB4, MBB4->end(), OutermostLoc, BeanInst);
+
+  LexicalScopes LS;
+  LS.initialize(*MF);
+  LexicalScope *FuncScope = LS.getCurrentFunctionScope();
+
+  // A gap in a range that contains no other location, is not actually a
+  // gap as far as lexical scopes are concerned.
+  auto &Ranges = FuncScope->getRanges();
+  ASSERT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges[0].first, &*MF->begin()->begin());
+  auto BBIt = MF->end();
+  BBIt = std::prev(BBIt);
+  EXPECT_EQ(Ranges[0].second, &*BBIt->begin());
+}
+
+// Now a function with intervening not-in-scope instructions.
+TEST_F(LexicalScopesTest, FuncWithRealGap) {
+  MachineInstr *FirstI = BuildMI(*MBB1, MBB1->end(), InBlockLoc, BeanInst);
+  BuildMI(*MBB2, MBB2->end(), OutermostLoc, BeanInst);
+  BuildMI(*MBB3, MBB3->end(), OutermostLoc, BeanInst);
+  MachineInstr *LastI = BuildMI(*MBB4, MBB4->end(), InBlockLoc, BeanInst);
+
+  LexicalScopes LS;
+  LS.initialize(*MF);
+  LexicalScope *BlockScope = LS.findLexicalScope(InBlockLoc.get());
+  ASSERT_NE(BlockScope, nullptr);
+
+  // Within the block scope, there's a gap between the first and last
+  // block / instruction, where it's only the outermost scope.
+  auto &Ranges = BlockScope->getRanges();
+  ASSERT_EQ(Ranges.size(), 2u);
+  EXPECT_EQ(Ranges[0].first, FirstI);
+  EXPECT_EQ(Ranges[0].second, FirstI);
+  EXPECT_EQ(Ranges[1].first, LastI);
+  EXPECT_EQ(Ranges[1].second, LastI);
+
+  // The outer function scope should cover the whole function, including
+  // blocks the lexicalblock covers.
+  LexicalScope *FuncScope = LS.getCurrentFunctionScope();
+  auto &FuncRanges = FuncScope->getRanges();
+  ASSERT_EQ(FuncRanges.size(), 1u);
+  EXPECT_NE(FuncRanges[0].first, FuncRanges[0].second);
+  EXPECT_EQ(FuncRanges[0].first, FirstI);
+  EXPECT_EQ(FuncRanges[0].second, LastI);
+}
+
+// Examine the relationship between two scopes that don't nest (are siblings).
+TEST_F(LexicalScopesTest, NotNested) {
+  MachineInstr *FirstI = BuildMI(*MBB1, MBB1->end(), InBlockLoc, BeanInst);
+  MachineInstr *SecondI =
+      BuildMI(*MBB2, MBB2->end(), NotNestedBlockLoc, BeanInst);
+  MachineInstr *ThirdI =
+      BuildMI(*MBB3, MBB3->end(), NotNestedBlockLoc, BeanInst);
+  MachineInstr *FourthI = BuildMI(*MBB4, MBB4->end(), InBlockLoc, BeanInst);
+
+  LexicalScopes LS;
+  LS.initialize(*MF);
+  LexicalScope *FuncScope = LS.getCurrentFunctionScope();
+  LexicalScope *BlockScope = LS.findLexicalScope(InBlockLoc.get());
+  LexicalScope *OtherBlockScope = LS.findLexicalScope(NotNestedBlockLoc.get());
+  ASSERT_NE(FuncScope, nullptr);
+  ASSERT_NE(BlockScope, nullptr);
+  ASSERT_NE(OtherBlockScope, nullptr);
+
+  // The function should cover everything; the two blocks are distinct and
+  // should not.
+  auto &FuncRanges = FuncScope->getRanges();
+  ASSERT_EQ(FuncRanges.size(), 1u);
+  EXPECT_EQ(FuncRanges[0].first, FirstI);
+  EXPECT_EQ(FuncRanges[0].second, FourthI);
+
+  // Two ranges, start and end instructions.
+  auto &BlockRanges = BlockScope->getRanges();
+  ASSERT_EQ(BlockRanges.size(), 2u);
+  EXPECT_EQ(BlockRanges[0].first, FirstI);
+  EXPECT_EQ(BlockRanges[0].second, FirstI);
+  EXPECT_EQ(BlockRanges[1].first, FourthI);
+  EXPECT_EQ(BlockRanges[1].second, FourthI);
+
+  // One inner range, covering the two inner blocks.
+  auto &OtherBlockRanges = OtherBlockScope->getRanges();
+  ASSERT_EQ(OtherBlockRanges.size(), 1u);
+  EXPECT_EQ(OtherBlockRanges[0].first, SecondI);
+  EXPECT_EQ(OtherBlockRanges[0].second, ThirdI);
+}
+
+// Test the scope-specific and block-specific dominates methods.
+TEST_F(LexicalScopesTest, TestDominates) {
+  BuildMI(*MBB1, MBB1->end(), InBlockLoc, BeanInst);
+  BuildMI(*MBB2, MBB2->end(), NotNestedBlockLoc, BeanInst);
+  BuildMI(*MBB3, MBB3->end(), NotNestedBlockLoc, BeanInst);
+  BuildMI(*MBB4, MBB4->end(), InBlockLoc, BeanInst);
+
+  LexicalScopes LS;
+  LS.initialize(*MF);
+  LexicalScope *FuncScope = LS.getCurrentFunctionScope();
+  LexicalScope *BlockScope = LS.findLexicalScope(InBlockLoc.get());
+  LexicalScope *OtherBlockScope = LS.findLexicalScope(NotNestedBlockLoc.get());
+  ASSERT_NE(FuncScope, nullptr);
+  ASSERT_NE(BlockScope, nullptr);
+  ASSERT_NE(OtherBlockScope, nullptr);
+
+  EXPECT_TRUE(FuncScope->dominates(BlockScope));
+  EXPECT_TRUE(FuncScope->dominates(OtherBlockScope));
+  EXPECT_FALSE(BlockScope->dominates(FuncScope));
+  EXPECT_FALSE(BlockScope->dominates(OtherBlockScope));
+  EXPECT_FALSE(OtherBlockScope->dominates(FuncScope));
+  EXPECT_FALSE(OtherBlockScope->dominates(BlockScope));
+
+  // Outermost scope dominates everything, as all insts are within it.
+  EXPECT_TRUE(LS.dominates(OutermostLoc.get(), MBB1));
+  EXPECT_TRUE(LS.dominates(OutermostLoc.get(), MBB2));
+  EXPECT_TRUE(LS.dominates(OutermostLoc.get(), MBB3));
+  EXPECT_TRUE(LS.dominates(OutermostLoc.get(), MBB4));
+
+  // One inner block dominates the outer pair of blocks,
+  EXPECT_TRUE(LS.dominates(InBlockLoc.get(), MBB1));
+  EXPECT_FALSE(LS.dominates(InBlockLoc.get(), MBB2));
+  EXPECT_FALSE(LS.dominates(InBlockLoc.get(), MBB3));
+  EXPECT_TRUE(LS.dominates(InBlockLoc.get(), MBB4));
+
+  // While the other dominates the inner two blocks.
+  EXPECT_FALSE(LS.dominates(NotNestedBlockLoc.get(), MBB1));
+  EXPECT_TRUE(LS.dominates(NotNestedBlockLoc.get(), MBB2));
+  EXPECT_TRUE(LS.dominates(NotNestedBlockLoc.get(), MBB3));
+  EXPECT_FALSE(LS.dominates(NotNestedBlockLoc.get(), MBB4));
+}
+
+// Test getMachineBasicBlocks returns all dominated blocks.
+TEST_F(LexicalScopesTest, TestGetBlocks) {
+  BuildMI(*MBB1, MBB1->end(), InBlockLoc, BeanInst);
+  BuildMI(*MBB2, MBB2->end(), NotNestedBlockLoc, BeanInst);
+  BuildMI(*MBB3, MBB3->end(), NotNestedBlockLoc, BeanInst);
+  BuildMI(*MBB4, MBB4->end(), InBlockLoc, BeanInst);
+
+  LexicalScopes LS;
+  LS.initialize(*MF);
+  LexicalScope *FuncScope = LS.getCurrentFunctionScope();
+  LexicalScope *BlockScope = LS.findLexicalScope(InBlockLoc.get());
+  LexicalScope *OtherBlockScope = LS.findLexicalScope(NotNestedBlockLoc.get());
+  ASSERT_NE(FuncScope, nullptr);
+  ASSERT_NE(BlockScope, nullptr);
+  ASSERT_NE(OtherBlockScope, nullptr);
+
+  SmallPtrSet<const MachineBasicBlock *, 4> OutermostBlocks, InBlockBlocks,
+      NotNestedBlockBlocks;
+  LS.getMachineBasicBlocks(OutermostLoc.get(), OutermostBlocks);
+  LS.getMachineBasicBlocks(InBlockLoc.get(), InBlockBlocks);
+  LS.getMachineBasicBlocks(NotNestedBlockLoc.get(), NotNestedBlockBlocks);
+
+  EXPECT_EQ(OutermostBlocks.count(MBB1), 1u);
+  EXPECT_EQ(OutermostBlocks.count(MBB2), 1u);
+  EXPECT_EQ(OutermostBlocks.count(MBB3), 1u);
+  EXPECT_EQ(OutermostBlocks.count(MBB4), 1u);
+
+  EXPECT_EQ(InBlockBlocks.count(MBB1), 1u);
+  EXPECT_EQ(InBlockBlocks.count(MBB2), 0u);
+  EXPECT_EQ(InBlockBlocks.count(MBB3), 0u);
+  EXPECT_EQ(InBlockBlocks.count(MBB4), 1u);
+
+  EXPECT_EQ(NotNestedBlockBlocks.count(MBB1), 0u);
+  EXPECT_EQ(NotNestedBlockBlocks.count(MBB2), 1u);
+  EXPECT_EQ(NotNestedBlockBlocks.count(MBB3), 1u);
+  EXPECT_EQ(NotNestedBlockBlocks.count(MBB4), 0u);
+}
+
+TEST_F(LexicalScopesTest, TestMetaInst) {
+  // Instruction Layout looks like this, where 'F' means funcscope, and
+  // 'B' blockscope:
+  // bb1:
+  //   F: bean
+  //   B: bean
+  // bb2:
+  //   F: bean
+  //   B: DBG_VALUE
+  // bb3:
+  //   F: bean
+  //   B: DBG_VALUE
+  // bb4:
+  //   F: bean
+  //   B: bean
+  // The block / 'B' should only dominate bb1 and bb4. DBG_VALUE is a meta
+  // instruction, and shouldn't contribute to scopes.
+  BuildMI(*MBB1, MBB1->end(), OutermostLoc, BeanInst);
+  BuildMI(*MBB1, MBB1->end(), InBlockLoc, BeanInst);
+  BuildMI(*MBB2, MBB2->end(), OutermostLoc, BeanInst);
+  BuildMI(*MBB2, MBB2->end(), InBlockLoc, DbgValueInst);
+  BuildMI(*MBB3, MBB3->end(), OutermostLoc, BeanInst);
+  BuildMI(*MBB3, MBB3->end(), InBlockLoc, DbgValueInst);
+  BuildMI(*MBB4, MBB4->end(), OutermostLoc, BeanInst);
+  BuildMI(*MBB4, MBB4->end(), InBlockLoc, BeanInst);
+
+  LexicalScopes LS;
+  LS.initialize(*MF);
+  LexicalScope *FuncScope = LS.getCurrentFunctionScope();
+  LexicalScope *BlockScope = LS.findLexicalScope(InBlockLoc.get());
+  ASSERT_NE(FuncScope, nullptr);
+  ASSERT_NE(BlockScope, nullptr);
+
+  EXPECT_TRUE(LS.dominates(OutermostLoc.get(), MBB1));
+  EXPECT_TRUE(LS.dominates(OutermostLoc.get(), MBB2));
+  EXPECT_TRUE(LS.dominates(OutermostLoc.get(), MBB3));
+  EXPECT_TRUE(LS.dominates(OutermostLoc.get(), MBB4));
+  EXPECT_TRUE(LS.dominates(InBlockLoc.get(), MBB1));
+  EXPECT_FALSE(LS.dominates(InBlockLoc.get(), MBB2));
+  EXPECT_FALSE(LS.dominates(InBlockLoc.get(), MBB3));
+  EXPECT_TRUE(LS.dominates(InBlockLoc.get(), MBB4));
+}
+
+} // anonymous namespace

llvm/unittests/CodeGen/MFCommon.inc

+// Add a few Bogus backend classes so we can create MachineInstrs without
+// depending on a real target.
+class BogusTargetLowering : public TargetLowering {
+public:
+  BogusTargetLowering(TargetMachine &TM) : TargetLowering(TM) {}
+};
+
+class BogusFrameLowering : public TargetFrameLowering {
+public:
+  BogusFrameLowering()
+      : TargetFrameLowering(TargetFrameLowering::StackGrowsDown, Align(4), 4) {}
+
+  void emitPrologue(MachineFunction &MF,
+                    MachineBasicBlock &MBB) const override {}
+  void emitEpilogue(MachineFunction &MF,
+                    MachineBasicBlock &MBB) const override {}
+  bool hasFP(const MachineFunction &MF) const override { return false; }
+};
+
+static TargetRegisterClass *const BogusRegisterClasses[] = {nullptr};
+
+class BogusRegisterInfo : public TargetRegisterInfo {
+public:
+  BogusRegisterInfo()
+      : TargetRegisterInfo(nullptr, BogusRegisterClasses, BogusRegisterClasses,
+                           nullptr, nullptr, LaneBitmask(~0u), nullptr) {
+    InitMCRegisterInfo(nullptr, 0, 0, 0, nullptr, 0, nullptr, 0, nullptr,
+                       nullptr, nullptr, nullptr, nullptr, 0, nullptr, nullptr);
+  }
+
+  const MCPhysReg *
+  getCalleeSavedRegs(const MachineFunction *MF) const override {
+    return nullptr;
+  }
+  ArrayRef<const uint32_t *> getRegMasks() const override { return None; }
+  ArrayRef<const char *> getRegMaskNames() const override { return None; }
+  BitVector getReservedRegs(const MachineFunction &MF) const override {
+    return BitVector();
+  }
+  const RegClassWeight &
+  getRegClassWeight(const TargetRegisterClass *RC) const override {
+    static RegClassWeight Bogus{1, 16};
+    return Bogus;
+  }
+  unsigned getRegUnitWeight(unsigned RegUnit) const override { return 1; }
+  unsigned getNumRegPressureSets() const override { return 0; }
+  const char *getRegPressureSetName(unsigned Idx) const override {
+    return "bogus";
+  }
+  unsigned getRegPressureSetLimit(const MachineFunction &MF,
+                                  unsigned Idx) const override {
+    return 0;
+  }
+  const int *
+  getRegClassPressureSets(const TargetRegisterClass *RC) const override {
+    static const int Bogus[] = {0, -1};
+    return &Bogus[0];
+  }
+  const int *getRegUnitPressureSets(unsigned RegUnit) const override {
+    static const int Bogus[] = {0, -1};
+    return &Bogus[0];
+  }
+
+  Register getFrameRegister(const MachineFunction &MF) const override {
+    return 0;
+  }
+  void eliminateFrameIndex(MachineBasicBlock::iterator MI, int SPAdj,
+                           unsigned FIOperandNum,
+                           RegScavenger *RS = nullptr) const override {}
+};
+
+class BogusSubtarget : public TargetSubtargetInfo {
+public:
+  BogusSubtarget(TargetMachine &TM)
+      : TargetSubtargetInfo(Triple(""), "", "", {}, {}, nullptr, nullptr,
+                            nullptr, nullptr, nullptr, nullptr),
+        FL(), TL(TM) {}
+  ~BogusSubtarget() override {}
+
+  const TargetFrameLowering *getFrameLowering() const override { return &FL; }
+
+  const TargetLowering *getTargetLowering() const override { return &TL; }
+
+  const TargetInstrInfo *getInstrInfo() const override { return &TII; }
+
+  const TargetRegisterInfo *getRegisterInfo() const override { return &TRI; }
+
+private:
+  BogusFrameLowering FL;
+  BogusRegisterInfo TRI;
+  BogusTargetLowering TL;
+  TargetInstrInfo TII;
+};
+
+class BogusTargetMachine : public LLVMTargetMachine {
+public:
+  BogusTargetMachine()
+      : LLVMTargetMachine(Target(), "", Triple(""), "", "", TargetOptions(),
+                          Reloc::Static, CodeModel::Small, CodeGenOpt::Default),
+        ST(*this) {}
+
+  ~BogusTargetMachine() override {}
+
+  const TargetSubtargetInfo *getSubtargetImpl(const Function &) const override {
+    return &ST;
+  }
+
+private:
+  BogusSubtarget ST;
+};
+
+std::unique_ptr<BogusTargetMachine> createTargetMachine() {
+  return std::make_unique<BogusTargetMachine>();
+}
+
+std::unique_ptr<MachineFunction> createMachineFunction(LLVMContext &Ctx,
+                                                       Module &M) {
+  auto Type = FunctionType::get(Type::getVoidTy(Ctx), false);
+  auto F = Function::Create(Type, GlobalValue::ExternalLinkage, "Test", &M);
+
+  auto TM = createTargetMachine();
+  unsigned FunctionNum = 42;
+  MachineModuleInfo MMI(TM.get());
+  const TargetSubtargetInfo &STI = *TM->getSubtargetImpl(*F);
+
+  return std::make_unique<MachineFunction>(*F, *TM, STI, FunctionNum, MMI);
+}
+

llvm/unittests/CodeGen/MachineInstrTest.cpp

 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/TargetFrameLowering.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/ModuleSlotTracker.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCSymbol.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
-// Add a few Bogus backend classes so we can create MachineInstrs without
-// depending on a real target.
-class BogusTargetLowering : public TargetLowering {
-public:
-  BogusTargetLowering(TargetMachine &TM) : TargetLowering(TM) {}
-};
-
-class BogusFrameLowering : public TargetFrameLowering {
-public:
-  BogusFrameLowering()
-      : TargetFrameLowering(TargetFrameLowering::StackGrowsDown, Align(4), 4) {}
-
-  void emitPrologue(MachineFunction &MF,
-                    MachineBasicBlock &MBB) const override {}
-  void emitEpilogue(MachineFunction &MF,
-                    MachineBasicBlock &MBB) const override {}
-  bool hasFP(const MachineFunction &MF) const override { return false; }
-};
-
-static TargetRegisterClass *const BogusRegisterClasses[] = {nullptr};
-
-class BogusRegisterInfo : public TargetRegisterInfo {
-public:
-  BogusRegisterInfo()
-      : TargetRegisterInfo(nullptr, BogusRegisterClasses, BogusRegisterClasses,
-                           nullptr, nullptr, LaneBitmask(~0u), nullptr) {
-    InitMCRegisterInfo(nullptr, 0, 0, 0, nullptr, 0, nullptr, 0, nullptr,
-                       nullptr, nullptr, nullptr, nullptr, 0, nullptr, nullptr);
-  }
-
-  const MCPhysReg *
-  getCalleeSavedRegs(const MachineFunction *MF) const override {
-    return nullptr;
-  }
-  ArrayRef<const uint32_t *> getRegMasks() const override { return None; }
-  ArrayRef<const char *> getRegMaskNames() const override { return None; }
-  BitVector getReservedRegs(const MachineFunction &MF) const override {
-    return BitVector();
-  }
-  const RegClassWeight &
-  getRegClassWeight(const TargetRegisterClass *RC) const override {
-    static RegClassWeight Bogus{1, 16};
-    return Bogus;
-  }
-  unsigned getRegUnitWeight(unsigned RegUnit) const override { return 1; }
-  unsigned getNumRegPressureSets() const override { return 0; }
-  const char *getRegPressureSetName(unsigned Idx) const override {
-    return "bogus";
-  }
-  unsigned getRegPressureSetLimit(const MachineFunction &MF,
-                                  unsigned Idx) const override {
-    return 0;
-  }
-  const int *
-  getRegClassPressureSets(const TargetRegisterClass *RC) const override {
-    static const int Bogus[] = {0, -1};
-    return &Bogus[0];
-  }
-  const int *getRegUnitPressureSets(unsigned RegUnit) const override {
-    static const int Bogus[] = {0, -1};
-    return &Bogus[0];
-  }
-
-  Register getFrameRegister(const MachineFunction &MF) const override {
-    return 0;
-  }
-  void eliminateFrameIndex(MachineBasicBlock::iterator MI, int SPAdj,
-                           unsigned FIOperandNum,
-                           RegScavenger *RS = nullptr) const override {}
-};
-
-class BogusSubtarget : public TargetSubtargetInfo {
-public:
-  BogusSubtarget(TargetMachine &TM)
-      : TargetSubtargetInfo(Triple(""), "", "", {}, {}, nullptr, nullptr,
-                            nullptr, nullptr, nullptr, nullptr),
-        FL(), TL(TM) {}
-  ~BogusSubtarget() override {}
-
-  const TargetFrameLowering *getFrameLowering() const override { return &FL; }
-
-  const TargetLowering *getTargetLowering() const override { return &TL; }
-
-  const TargetInstrInfo *getInstrInfo() const override { return &TII; }
-
-  const TargetRegisterInfo *getRegisterInfo() const override { return &TRI; }
-
-private:
-  BogusFrameLowering FL;
-  BogusRegisterInfo TRI;
-  BogusTargetLowering TL;
-  TargetInstrInfo TII;
-};
-
-class BogusTargetMachine : public LLVMTargetMachine {
-public:
-  BogusTargetMachine()
-      : LLVMTargetMachine(Target(), "", Triple(""), "", "", TargetOptions(),
-                          Reloc::Static, CodeModel::Small, CodeGenOpt::Default),
-        ST(*this) {}
-
-  ~BogusTargetMachine() override {}
-
-  const TargetSubtargetInfo *getSubtargetImpl(const Function &) const override {
-    return &ST;
-  }
-
-private:
-  BogusSubtarget ST;
-};
+// Include helper functions to ease the manipulation of MachineFunctions.
+#include "MFCommon.inc"
 
 std::unique_ptr<MCContext> createMCContext(MCAsmInfo *AsmInfo) {
   return std::make_unique<MCContext>(
       AsmInfo, nullptr, nullptr, nullptr, nullptr, false);
 }
 
-std::unique_ptr<BogusTargetMachine> createTargetMachine() {
-  return std::make_unique<BogusTargetMachine>();
-}
-
-std::unique_ptr<MachineFunction> createMachineFunction() {
-  LLVMContext Ctx;
-  Module M("Module", Ctx);
-  auto Type = FunctionType::get(Type::getVoidTy(Ctx), false);
-  auto F = Function::Create(Type, GlobalValue::ExternalLinkage, "Test", &M);
-
-  auto TM = createTargetMachine();
-  unsigned FunctionNum = 42;
-  MachineModuleInfo MMI(TM.get());
-  const TargetSubtargetInfo &STI = *TM->getSubtargetImpl(*F);
-
-  return std::make_unique<MachineFunction>(*F, *TM, STI, FunctionNum, MMI);
-}
-
 // This test makes sure that MachineInstr::isIdenticalTo handles Defs correctly
 // for various combinations of IgnoreDefs, and also that it is symmetrical.
 TEST(IsIdenticalToTest, DifferentDefs) {
-  auto MF = createMachineFunction();
+  LLVMContext Ctx;
+  Module Mod("Module", Ctx);
+  auto MF = createMachineFunction(Ctx, Mod);
 
   unsigned short NumOps = 2;
   unsigned char NumDefs = 1;
   MCOperandInfo OpInfo[] = {
       {0, 0, MCOI::OPERAND_REGISTER, 0},
       {0, 1 << MCOI::OptionalDef, MCOI::OPERAND_REGISTER, 0}};
   MCInstrDesc MCID = {
       0, NumOps,  NumDefs, 0,      0, 1ULL << MCID::HasOptionalDef,
void checkHashAndIsEqualMatch(MachineInstr *MI1, MachineInstr *MI2) {
   auto Hash2 = MachineInstrExpressionTrait::getHashValue(MI2);
 
   ASSERT_EQ(IsEqual1, Hash1 == Hash2);
 }
 
 // This test makes sure that MachineInstrExpressionTraits::isEqual is in sync
 // with MachineInstrExpressionTraits::getHashValue.
 TEST(MachineInstrExpressionTraitTest, IsEqualAgreesWithGetHashValue) {
-  auto MF = createMachineFunction();
+  LLVMContext Ctx;
+  Module Mod("Module", Ctx);
+  auto MF = createMachineFunction(Ctx, Mod);
 
   unsigned short NumOps = 2;
   unsigned char NumDefs = 1;
   MCOperandInfo OpInfo[] = {
       {0, 0, MCOI::OPERAND_REGISTER, 0},
       {0, 1 << MCOI::OptionalDef, MCOI::OPERAND_REGISTER, 0}};
   MCInstrDesc MCID = {
       0, NumOps,  NumDefs, 0,      0, 1ULL << MCID::HasOptionalDef,
TEST(MachineInstrExpressionTraitTest, IsEqualAgreesWithGetHashValue) {
 
   checkHashAndIsEqualMatch(VD1SD, VD2PU);
   checkHashAndIsEqualMatch(VD1SD, VD2PD);
 
   checkHashAndIsEqualMatch(VD2PU, VD2PD);
 }
 
 TEST(MachineInstrPrintingTest, DebugLocPrinting) {
-  auto MF = createMachineFunction();
+  LLVMContext Ctx;
+  Module Mod("Module", Ctx);
+  auto MF = createMachineFunction(Ctx, Mod);
 
   MCOperandInfo OpInfo{0, 0, MCOI::OPERAND_REGISTER, 0};
   MCInstrDesc MCID = {0, 1,       1,       0,       0, 0,
                       0, nullptr, nullptr, &OpInfo, 0, nullptr};
 
-  LLVMContext Ctx;
   DIFile *DIF = DIFile::getDistinct(Ctx, "filename", "");
   DISubprogram *DIS = DISubprogram::getDistinct(
       Ctx, nullptr, "", "", DIF, 0, nullptr, 0, nullptr, 0, 0, DINode::FlagZero,
       DISubprogram::SPFlagZero, nullptr);
   DILocation *DIL = DILocation::get(Ctx, 1, 5, DIS);
   DebugLoc DL(DIL);
   MachineInstr *MI = MF->CreateMachineInstr(MCID, DL);
   MI->addOperand(*MF, MachineOperand::CreateReg(0, /*isDef*/ true));
 
   std::string str;
   raw_string_ostream OS(str);
   MI->print(OS, /*IsStandalone*/true, /*SkipOpers*/false, /*SkipDebugLoc*/false,
             /*AddNewLine*/false);
   ASSERT_TRUE(
       StringRef(OS.str()).startswith("$noreg = UNKNOWN debug-location "));
   ASSERT_TRUE(
       StringRef(OS.str()).endswith("filename:1:5"));
 }
 
 TEST(MachineInstrSpan, DistanceBegin) {
-  auto MF = createMachineFunction();
+  LLVMContext Ctx;
+  Module Mod("Module", Ctx);
+  auto MF = createMachineFunction(Ctx, Mod);
   auto MBB = MF->CreateMachineBasicBlock();
 
   MCInstrDesc MCID = {0, 0,       0,       0,       0, 0,
                       0, nullptr, nullptr, nullptr, 0, nullptr};
 
   auto MII = MBB->begin();
   MachineInstrSpan MIS(MII, MBB);
   ASSERT_TRUE(MIS.empty());
 
   auto MI = MF->CreateMachineInstr(MCID, DebugLoc());
   MBB->insert(MII, MI);
   ASSERT_TRUE(std::distance(MIS.begin(), MII) == 1);
 }
 
 TEST(MachineInstrSpan, DistanceEnd) {
-  auto MF = createMachineFunction();
+  LLVMContext Ctx;
+  Module Mod("Module", Ctx);
+  auto MF = createMachineFunction(Ctx, Mod);
   auto MBB = MF->CreateMachineBasicBlock();
 
   MCInstrDesc MCID = {0, 0,       0,       0,       0, 0,
                       0, nullptr, nullptr, nullptr, 0, nullptr};
 
   auto MII = MBB->end();
   MachineInstrSpan MIS(MII, MBB);
   ASSERT_TRUE(MIS.empty());
 
   auto MI = MF->CreateMachineInstr(MCID, DebugLoc());
   MBB->insert(MII, MI);
   ASSERT_TRUE(std::distance(MIS.begin(), MII) == 1);
 }
 
 TEST(MachineInstrExtraInfo, AddExtraInfo) {
-  auto MF = createMachineFunction();
+  LLVMContext Ctx;
+  Module Mod("Module", Ctx);
+  auto MF = createMachineFunction(Ctx, Mod);
   MCInstrDesc MCID = {0, 0,       0,       0,       0, 0,
                       0, nullptr, nullptr, nullptr, 0, nullptr};
 
   auto MI = MF->CreateMachineInstr(MCID, DebugLoc());
   auto MAI = MCAsmInfo();
   auto MC = createMCContext(&MAI);
   auto MMO = MF->getMachineMemOperand(MachinePointerInfo(),
                                       MachineMemOperand::MOLoad, 8, 8);
   SmallVector<MachineMemOperand *, 2> MMOs;
   MMOs.push_back(MMO);
   MCSymbol *Sym1 = MC->createTempSymbol("pre_label", false);
   MCSymbol *Sym2 = MC->createTempSymbol("post_label", false);
-  LLVMContext Ctx;
   MDNode *MDN = MDNode::getDistinct(Ctx, None);
 
   ASSERT_TRUE(MI->memoperands_empty());
   ASSERT_FALSE(MI->getPreInstrSymbol());
   ASSERT_FALSE(MI->getPostInstrSymbol());
   ASSERT_FALSE(MI->getHeapAllocMarker());
 
   MI->setMemRefs(*MF, MMOs);
TEST(MachineInstrExtraInfo, AddExtraInfo) {
   MI->setHeapAllocMarker(*MF, MDN);
   ASSERT_TRUE(MI->memoperands().size() == 1);
   ASSERT_TRUE(MI->getPreInstrSymbol() == Sym1);
   ASSERT_TRUE(MI->getPostInstrSymbol() == Sym2);
   ASSERT_TRUE(MI->getHeapAllocMarker() == MDN);
 }
 
 TEST(MachineInstrExtraInfo, ChangeExtraInfo) {
-  auto MF = createMachineFunction();
+  LLVMContext Ctx;
+  Module Mod("Module", Ctx);
+  auto MF = createMachineFunction(Ctx, Mod);
   MCInstrDesc MCID = {0, 0,       0,       0,       0, 0,
                       0, nullptr, nullptr, nullptr, 0, nullptr};
 
   auto MI = MF->CreateMachineInstr(MCID, DebugLoc());
   auto MAI = MCAsmInfo();
   auto MC = createMCContext(&MAI);
   auto MMO = MF->getMachineMemOperand(MachinePointerInfo(),
                                       MachineMemOperand::MOLoad, 8, 8);
   SmallVector<MachineMemOperand *, 2> MMOs;
   MMOs.push_back(MMO);
   MCSymbol *Sym1 = MC->createTempSymbol("pre_label", false);
   MCSymbol *Sym2 = MC->createTempSymbol("post_label", false);
-  LLVMContext Ctx;
   MDNode *MDN = MDNode::getDistinct(Ctx, None);
 
   MI->setMemRefs(*MF, MMOs);
   MI->setPreInstrSymbol(*MF, Sym1);
   MI->setPostInstrSymbol(*MF, Sym2);
   MI->setHeapAllocMarker(*MF, MDN);
 
   MMOs.push_back(MMO);
 
   MI->setMemRefs(*MF, MMOs);
   ASSERT_TRUE(MI->memoperands().size() == 2);
   ASSERT_TRUE(MI->getPreInstrSymbol() == Sym1);
   ASSERT_TRUE(MI->getPostInstrSymbol() == Sym2);
   ASSERT_TRUE(MI->getHeapAllocMarker() == MDN);
 
   MI->setPostInstrSymbol(*MF, Sym1);
   ASSERT_TRUE(MI->memoperands().size() == 2);
   ASSERT_TRUE(MI->getPreInstrSymbol() == Sym1);
   ASSERT_TRUE(MI->getPostInstrSymbol() == Sym1);
   ASSERT_TRUE(MI->getHeapAllocMarker() == MDN);
 }
 
 TEST(MachineInstrExtraInfo, RemoveExtraInfo) {
-  auto MF = createMachineFunction();
+  LLVMContext Ctx;
+  Module Mod("Module", Ctx);
+  auto MF = createMachineFunction(Ctx, Mod);
   MCInstrDesc MCID = {0, 0,       0,       0,       0, 0,
                       0, nullptr, nullptr, nullptr, 0, nullptr};
 
   auto MI = MF->CreateMachineInstr(MCID, DebugLoc());
   auto MAI = MCAsmInfo();
   auto MC = createMCContext(&MAI);
   auto MMO = MF->getMachineMemOperand(MachinePointerInfo(),
                                       MachineMemOperand::MOLoad, 8, 8);
   SmallVector<MachineMemOperand *, 2> MMOs;
   MMOs.push_back(MMO);
   MMOs.push_back(MMO);
   MCSymbol *Sym1 = MC->createTempSymbol("pre_label", false);
   MCSymbol *Sym2 = MC->createTempSymbol("post_label", false);
-  LLVMContext Ctx;
   MDNode *MDN = MDNode::getDistinct(Ctx, None);
 
   MI->setMemRefs(*MF, MMOs);
   MI->setPreInstrSymbol(*MF, Sym1);
   MI->setPostInstrSymbol(*MF, Sym2);
   MI->setHeapAllocMarker(*MF, MDN);
 
   MI->setPostInstrSymbol(*MF, nullptr);