diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h
--- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h
+++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h
@@ -37,6 +37,7 @@
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
@@ -56,6 +57,21 @@
 
 namespace test {
 
+/// Returns the environment at the program point marked with `Annotation` from
+/// the mapping of annotated program points to analysis state.
+///
+/// Requirements:
+///
+///   `Annotation` must be present as a key in `AnnotationStates`.
+template <typename LatticeT>
+const Environment &getEnvironmentAtAnnotation(
+    const llvm::StringMap<DataflowAnalysisState<LatticeT>> &AnnotationStates,
+    llvm::StringRef Annotation) {
+  auto It = AnnotationStates.find(Annotation);
+  assert(It != AnnotationStates.end());
+  return It->getValue().Env;
+}
+
 /// Contains data structures required and produced by a dataflow analysis run.
 struct AnalysisOutputs {
   /// Input code that is analyzed. Points within the code may be marked with
@@ -96,6 +112,11 @@
 
   /// Optional fields can be set with methods of the form `withFieldName(...)`.
   AnalysisInputs<AnalysisT> &&
+  withSetupTest(std::function<llvm::Error(AnalysisOutputs &)> Arg) && {
+    SetupTest = std::move(Arg);
+    return std::move(*this);
+  }
+  AnalysisInputs<AnalysisT> &&
   withPostVisitCFG(std::function<void(ASTContext &, const CFGElement &,
                                       const TypeErasedDataflowAnalysisState &)>
                        Arg) && {
@@ -120,6 +141,11 @@
   /// takes as argument the AST generated from the code being analyzed and the
   /// initial state from which the analysis starts with.
   std::function<AnalysisT(ASTContext &, Environment &)> MakeAnalysis;
+  /// Optional. If provided, this function is executed immediately before
+  /// running the dataflow analysis to allow for additional setup. All fields in
+  /// the `AnalysisOutputs` argument will be initialized except for the
+  /// `BlockStates` field which is only computed later during the analysis.
+  std::function<llvm::Error(AnalysisOutputs &)> SetupTest = nullptr;
   /// Optional. If provided, this function is applied on each CFG element after
   /// the analysis has been run.
   std::function<void(ASTContext &, const CFGElement &,
@@ -138,54 +164,10 @@
 buildStatementToAnnotationMapping(const FunctionDecl *Func,
                                   llvm::Annotations AnnotatedCode);
 
-/// Returns line numbers and content of the annotations in `AO.Code`.
+/// Returns line numbers and content of the annotations in `AnnotatedCode`.
 llvm::DenseMap<unsigned, std::string>
-getAnnotationLinesAndContent(const AnalysisOutputs &AO);
-
-// FIXME: Return a string map instead of a vector of pairs.
-//
-/// Returns the analysis states at each annotated statement in `AO.Code`.
-template <typename AnalysisT>
-llvm::Expected<std::vector<
-    std::pair<std::string, DataflowAnalysisState<typename AnalysisT::Lattice>>>>
-getAnnotationStates(const AnalysisOutputs &AO) {
-  using StateT = DataflowAnalysisState<typename AnalysisT::Lattice>;
-  // FIXME: Extend to annotations on non-statement constructs.
-  // Get annotated statements.
-  llvm::Expected<llvm::DenseMap<const Stmt *, std::string>>
-      MaybeStmtToAnnotations =
-          buildStatementToAnnotationMapping(AO.Target, AO.Code);
-  if (!MaybeStmtToAnnotations)
-    return MaybeStmtToAnnotations.takeError();
-  auto &StmtToAnnotations = *MaybeStmtToAnnotations;
-
-  // Compute a map from statement annotations to the state computed
-  // for the program point immediately after the annotated statement.
-  std::vector<std::pair<std::string, StateT>> Results;
-  for (const CFGBlock *Block : AO.CFCtx.getCFG()) {
-    // Skip blocks that were not evaluated.
-    if (!AO.BlockStates[Block->getBlockID()])
-      continue;
-
-    transferBlock(
-        AO.CFCtx, AO.BlockStates, *Block, AO.InitEnv, AO.Analysis,
-        [&Results,
-         &StmtToAnnotations](const clang::CFGElement &Element,
-                             const TypeErasedDataflowAnalysisState &State) {
-          auto Stmt = Element.getAs<CFGStmt>();
-          if (!Stmt)
-            return;
-          auto It = StmtToAnnotations.find(Stmt->getStmt());
-          if (It == StmtToAnnotations.end())
-            return;
-          auto *Lattice =
-              llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
-          Results.emplace_back(It->second, StateT{*Lattice, State.Env});
-        });
-  }
-
-  return Results;
-}
+buildLineToAnnotationMapping(SourceManager &SM,
+                             llvm::Annotations AnnotatedCode);
 
 /// Runs dataflow specified from `AI.MakeAnalysis` and `AI.PostVisitCFG` on the
 /// body of the function that matches `AI.TargetFuncMatcher` in `AI.Code`.
@@ -200,9 +182,9 @@
 ///
 ///   `VerifyResults` must be provided.
 template <typename AnalysisT>
-llvm::Error checkDataflow(
-    AnalysisInputs<AnalysisT> AI,
-    std::function<llvm::Error(const AnalysisOutputs &)> VerifyResults) {
+llvm::Error
+checkDataflow(AnalysisInputs<AnalysisT> AI,
+              std::function<void(const AnalysisOutputs &)> VerifyResults) {
   // Build AST context from code.
   llvm::Annotations AnnotatedCode(AI.Code);
   auto Unit = tooling::buildASTFromCodeWithArgs(
@@ -236,7 +218,7 @@
     return MaybeCFCtx.takeError();
   auto &CFCtx = *MaybeCFCtx;
 
-  // Initialize states and run dataflow analysis.
+  // Initialize states for running dataflow analysis.
   DataflowAnalysisContext DACtx(std::make_unique<WatchedLiteralsSolver>());
   Environment InitEnv(DACtx, *Target);
   auto Analysis = AI.MakeAnalysis(Context, InitEnv);
@@ -251,19 +233,26 @@
         };
   }
 
-  // If successful, the run returns a mapping from block IDs to the
-  // post-analysis states for the CFG blocks that have been evaluated.
+  // Additional test setup.
+  AnalysisOutputs AO{AnnotatedCode, Context, Target, CFCtx,
+                     Analysis,      InitEnv, {}};
+  if (AI.SetupTest) {
+    if (auto Error = AI.SetupTest(AO))
+      return Error;
+  }
+
+  // If successful, the dataflow analysis returns a mapping from block IDs to
+  // the post-analysis states for the CFG blocks that have been evaluated.
   llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
       MaybeBlockStates = runTypeErasedDataflowAnalysis(CFCtx, Analysis, InitEnv,
                                                        PostVisitCFGClosure);
   if (!MaybeBlockStates)
     return MaybeBlockStates.takeError();
-  auto &BlockStates = *MaybeBlockStates;
+  AO.BlockStates = *MaybeBlockStates;
 
   // Verify dataflow analysis outputs.
-  AnalysisOutputs AO{AnnotatedCode, Context, Target,     CFCtx,
-                     Analysis,      InitEnv, BlockStates};
-  return VerifyResults(AO);
+  VerifyResults(AO);
+  return llvm::Error::success();
 }
 
 /// Runs dataflow specified from `AI.MakeAnalysis` and `AI.PostVisitCFG` on the
@@ -285,11 +274,10 @@
                                  const AnalysisOutputs &)>
                   VerifyResults) {
   return checkDataflow<AnalysisT>(
-      std::move(AI),
-      [&VerifyResults](const AnalysisOutputs &AO) -> llvm::Error {
-        auto AnnotationLinesAndContent = getAnnotationLinesAndContent(AO);
+      std::move(AI), [&VerifyResults](const AnalysisOutputs &AO) {
+        auto AnnotationLinesAndContent =
+            buildLineToAnnotationMapping(AO.ASTCtx.getSourceManager(), AO.Code);
         VerifyResults(AnnotationLinesAndContent, AO);
-        return llvm::Error::success();
       });
 }
 
@@ -312,23 +300,59 @@
 ///
 ///   Annotations must not be repeated.
 template <typename AnalysisT>
-llvm::Error checkDataflow(
-    AnalysisInputs<AnalysisT> AI,
-    std::function<void(
-        llvm::ArrayRef<std::pair<
-            std::string, DataflowAnalysisState<typename AnalysisT::Lattice>>>,
-        const AnalysisOutputs &)>
-        VerifyResults) {
+llvm::Error
+checkDataflow(AnalysisInputs<AnalysisT> AI,
+              std::function<void(const llvm::StringMap<DataflowAnalysisState<
+                                     typename AnalysisT::Lattice>> &,
+                                 const AnalysisOutputs &)>
+                  VerifyResults) {
+  // Compute mapping from nodes of annotated statements to the content in the
+  // annotation.
+  llvm::DenseMap<const Stmt *, std::string> StmtToAnnotations;
+  auto SetupTest = [&StmtToAnnotations,
+                    PrevSetupTest = std::move(AI.SetupTest)](
+                       AnalysisOutputs &AO) -> llvm::Error {
+    auto MaybeStmtToAnnotations = buildStatementToAnnotationMapping(
+        cast<FunctionDecl>(AO.InitEnv.getDeclCtx()), AO.Code);
+    if (!MaybeStmtToAnnotations) {
+      return MaybeStmtToAnnotations.takeError();
+    }
+    StmtToAnnotations = std::move(*MaybeStmtToAnnotations);
+    return PrevSetupTest ? PrevSetupTest(AO) : llvm::Error::success();
+  };
+
+  using StateT = DataflowAnalysisState<typename AnalysisT::Lattice>;
+
+  // Save the states computed for program points immediately following annotated
+  // statements. The saved states are keyed by the content of the annotation.
+  llvm::StringMap<StateT> AnnotationStates;
+  auto PostVisitCFG = [&StmtToAnnotations, &AnnotationStates,
+                       PrevPostVisitCFG = std::move(AI.PostVisitCFG)](
+                          ASTContext &Ctx, const CFGElement &Elt,
+                          const TypeErasedDataflowAnalysisState &State) {
+    if (PrevPostVisitCFG) {
+      PrevPostVisitCFG(Ctx, Elt, State);
+    }
+    // FIXME: Extend retrieval of state for non statement constructs.
+    auto Stmt = Elt.getAs<CFGStmt>();
+    if (!Stmt)
+      return;
+    auto It = StmtToAnnotations.find(Stmt->getStmt());
+    if (It == StmtToAnnotations.end())
+      return;
+    auto *Lattice =
+        llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
+    auto [_, InsertSuccess] =
+        AnnotationStates.insert({It->second, StateT{*Lattice, State.Env}});
+    (void)InsertSuccess;
+    assert(InsertSuccess);
+  };
   return checkDataflow<AnalysisT>(
-      std::move(AI),
-      [&VerifyResults](const AnalysisOutputs &AO) -> llvm::Error {
-        auto MaybeAnnotationStates = getAnnotationStates<AnalysisT>(AO);
-        if (!MaybeAnnotationStates) {
-          return MaybeAnnotationStates.takeError();
-        }
-        auto &AnnotationStates = *MaybeAnnotationStates;
+      std::move(AI)
+          .withSetupTest(std::move(SetupTest))
+          .withPostVisitCFG(std::move(PostVisitCFG)),
+      [&VerifyResults, &AnnotationStates](const AnalysisOutputs &AO) {
         VerifyResults(AnnotationStates, AO);
-        return llvm::Error::success();
       });
 }
 
@@ -370,12 +394,20 @@
                                 std::move(MakeAnalysis))
           .withASTBuildArgs(std::move(Args))
           .withASTBuildVirtualMappedFiles(std::move(VirtualMappedFiles)),
-      [&VerifyResults](
-          llvm::ArrayRef<std::pair<
-              std::string, DataflowAnalysisState<typename AnalysisT::Lattice>>>
-              AnnotationStates,
-          const AnalysisOutputs &AO) {
-        VerifyResults(AnnotationStates, AO.ASTCtx);
+      [&VerifyResults](const llvm::StringMap<DataflowAnalysisState<
+                           typename AnalysisT::Lattice>> &AnnotationStates,
+                       const AnalysisOutputs &AO) {
+        std::vector<std::pair<
+            std::string, DataflowAnalysisState<typename AnalysisT::Lattice>>>
+            AnnotationStatesAsVector;
+        for (const auto &P : AnnotationStates) {
+          AnnotationStatesAsVector.push_back(
+              std::make_pair(P.first().str(), std::move(P.second)));
+        }
+        llvm::sort(AnnotationStatesAsVector,
+                   [](auto a, auto b) { return a.first < b.first; });
+
+        VerifyResults(AnnotationStatesAsVector, AO.ASTCtx);
       });
 }
 
diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp b/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp
--- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp
@@ -19,6 +19,7 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Testing/Support/Annotations.h"
 #include <cassert>
@@ -53,11 +54,11 @@
 }
 
 llvm::DenseMap<unsigned, std::string>
-test::getAnnotationLinesAndContent(const AnalysisOutputs &AO) {
+test::buildLineToAnnotationMapping(SourceManager &SM,
+                                   llvm::Annotations AnnotatedCode) {
   llvm::DenseMap<unsigned, std::string> LineNumberToContent;
-  auto Code = AO.Code.code();
-  auto Annotations = AO.Code.ranges();
-  auto &SM = AO.ASTCtx.getSourceManager();
+  auto Code = AnnotatedCode.code();
+  auto Annotations = AnnotatedCode.ranges();
   for (auto &AnnotationRange : Annotations) {
     auto LineNumber =
         SM.getPresumedLineNumber(SM.getLocForStartOfFile(SM.getMainFileID())
@@ -72,6 +73,7 @@
 test::buildStatementToAnnotationMapping(const FunctionDecl *Func,
                                         llvm::Annotations AnnotatedCode) {
   llvm::DenseMap<const Stmt *, std::string> Result;
+  llvm::StringSet<> ExistingAnnotations;
 
   auto StmtMatcher =
       findAll(stmt(unless(anyOf(hasParent(expr()), hasParent(returnStmt()))))
@@ -113,7 +115,14 @@
                 .data());
       }
 
-      Result[Stmt] = Code.slice(Range.Begin, Range.End).str();
+      auto Annotation = Code.slice(Range.Begin, Range.End).str();
+      if (!ExistingAnnotations.insert(Annotation).second) {
+        return llvm::createStringError(
+            std::make_error_code(std::errc::invalid_argument),
+            "Repeated use of annotation: %s", Annotation.data());
+      }
+      Result[Stmt] = std::move(Annotation);
+
       I++;
 
       if (I < Annotations.size() && Annotations[I].Begin >= Offset) {
diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
--- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -649,8 +649,8 @@
                            std::string, DataflowAnalysisState<NoopLattice>>>
                            Results,
                        ASTContext &ASTCtx) {
-    ASSERT_THAT(Results, ElementsAre(Pair("p4", _), Pair("p3", _),
-                                     Pair("p2", _), Pair("p1", _)));
+    ASSERT_THAT(Results, ElementsAre(Pair("p1", _), Pair("p2", _),
+                                     Pair("p3", _), Pair("p4", _)));
     const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
     ASSERT_THAT(FooDecl, NotNull());
 
@@ -660,24 +660,24 @@
     const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
     ASSERT_THAT(BazDecl, NotNull());
 
-    const Environment &Env1 = Results[3].second.Env;
+    const Environment &Env1 = Results[0].second.Env;
     const StorageLocation *FooLoc =
         Env1.getStorageLocation(*FooDecl, SkipPast::None);
     EXPECT_THAT(FooLoc, NotNull());
     EXPECT_THAT(Env1.getStorageLocation(*BarDecl, SkipPast::None), IsNull());
     EXPECT_THAT(Env1.getStorageLocation(*BazDecl, SkipPast::None), IsNull());
 
-    const Environment &Env2 = Results[2].second.Env;
+    const Environment &Env2 = Results[1].second.Env;
     EXPECT_EQ(Env2.getStorageLocation(*FooDecl, SkipPast::None), FooLoc);
     EXPECT_THAT(Env2.getStorageLocation(*BarDecl, SkipPast::None), NotNull());
     EXPECT_THAT(Env2.getStorageLocation(*BazDecl, SkipPast::None), IsNull());
 
-    const Environment &Env3 = Results[1].second.Env;
+    const Environment &Env3 = Results[2].second.Env;
     EXPECT_EQ(Env3.getStorageLocation(*FooDecl, SkipPast::None), FooLoc);
     EXPECT_THAT(Env3.getStorageLocation(*BarDecl, SkipPast::None), IsNull());
     EXPECT_THAT(Env3.getStorageLocation(*BazDecl, SkipPast::None), NotNull());
 
-    const Environment &Env4 = Results[0].second.Env;
+    const Environment &Env4 = Results[3].second.Env;
     EXPECT_EQ(Env4.getStorageLocation(*FooDecl, SkipPast::None), FooLoc);
     EXPECT_THAT(Env4.getStorageLocation(*BarDecl, SkipPast::None), IsNull());
     EXPECT_THAT(Env4.getStorageLocation(*BazDecl, SkipPast::None), IsNull());
@@ -3305,8 +3305,8 @@
         ASSERT_THAT(CDecl, NotNull());
 
         {
-          ASSERT_THAT(Results[2], Pair("p0", _));
-          const Environment &Env = Results[2].second.Env;
+          ASSERT_THAT(Results[0], Pair("p0", _));
+          const Environment &Env = Results[0].second.Env;
           const ValueDecl *BDecl = findValueDecl(ASTCtx, "B");
           ASSERT_THAT(BDecl, NotNull());
           auto &BVal = *cast<BoolValue>(Env.getValue(*BDecl, SkipPast::None));
@@ -3322,8 +3322,8 @@
         }
 
         {
-          ASSERT_THAT(Results[0], Pair("p2", _));
-          const Environment &Env = Results[0].second.Env;
+          ASSERT_THAT(Results[2], Pair("p2", _));
+          const Environment &Env = Results[2].second.Env;
           auto &CVal = *cast<BoolValue>(Env.getValue(*CDecl, SkipPast::None));
           EXPECT_TRUE(Env.flowConditionImplies(CVal));
         }
@@ -3422,9 +3422,9 @@
                    Results,
                ASTContext &ASTCtx) {
         ASSERT_THAT(Results,
-                    ElementsAre(Pair("p-outer", _), Pair("p-inner", _)));
-        const Environment &OuterEnv = Results[0].second.Env;
-        const Environment &InnerEnv = Results[1].second.Env;
+                    ElementsAre(Pair("p-inner", _), Pair("p-outer", _)));
+        const Environment &InnerEnv = Results[0].second.Env;
+        const Environment &OuterEnv = Results[1].second.Env;
 
         const ValueDecl *ValDecl = findValueDecl(ASTCtx, "val");
         ASSERT_THAT(ValDecl, NotNull());
diff --git a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
--- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -24,8 +24,10 @@
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Testing/ADT/StringMapEntry.h"
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
@@ -42,12 +44,10 @@
 using namespace dataflow;
 using namespace test;
 using namespace ast_matchers;
-using ::testing::_;
-using ::testing::ElementsAre;
+using llvm::IsStringMapEntry;
+using ::testing::DescribeMatcher;
 using ::testing::IsEmpty;
-using ::testing::IsNull;
 using ::testing::NotNull;
-using ::testing::Pair;
 using ::testing::Test;
 using ::testing::UnorderedElementsAre;
 
@@ -129,7 +129,8 @@
 }
 
 struct FunctionCallLattice {
-  llvm::SmallSet<std::string, 8> CalledFunctions;
+  using FunctionSet = llvm::SmallSet<std::string, 8>;
+  FunctionSet CalledFunctions;
 
   bool operator==(const FunctionCallLattice &Other) const {
     return CalledFunctions == Other.CalledFunctions;
@@ -195,16 +196,20 @@
 
     ASSERT_THAT_ERROR(
         test::checkDataflow<FunctionCallAnalysis>(
-            Code, "target",
-            [](ASTContext &C, Environment &) {
-              return FunctionCallAnalysis(C);
-            },
+            AnalysisInputs<FunctionCallAnalysis>(
+                Code, ast_matchers::hasName("target"),
+                [](ASTContext &C, Environment &) {
+                  return FunctionCallAnalysis(C);
+                })
+                .withASTBuildArgs({"-fsyntax-only", "-std=c++17"})
+                .withASTBuildVirtualMappedFiles(std::move(FilesContents)),
+            /*VerifyResults=*/
             [&Expectations](
-                llvm::ArrayRef<std::pair<
-                    std::string, DataflowAnalysisState<FunctionCallLattice>>>
-                    Results,
-                ASTContext &) { EXPECT_THAT(Results, Expectations); },
-            {"-fsyntax-only", "-std=c++17"}, FilesContents),
+                const llvm::StringMap<
+                    DataflowAnalysisState<FunctionCallLattice>> &Results,
+                const AnalysisOutputs &) {
+              EXPECT_THAT(Results, Expectations);
+            }),
         llvm::Succeeded());
   }
 };
@@ -212,12 +217,16 @@
 MATCHER_P(HoldsFunctionCallLattice, m,
           ((negation ? "doesn't hold" : "holds") +
            llvm::StringRef(" a lattice element that ") +
-           ::testing::DescribeMatcher<FunctionCallLattice>(m, negation))
+           DescribeMatcher<FunctionCallLattice>(m))
               .str()) {
   return ExplainMatchResult(m, arg.Lattice, result_listener);
 }
 
-MATCHER_P(HasCalledFunctions, m, "") {
+MATCHER_P(HasCalledFunctions, m,
+          ((negation ? "doesn't hold" : "holds") +
+           llvm::StringRef(" a set of called functions that ") +
+           DescribeMatcher<FunctionCallLattice::FunctionSet>(m))
+              .str()) {
   return ExplainMatchResult(m, arg.CalledFunctions, result_listener);
 }
 
@@ -231,9 +240,9 @@
       // [[p]]
     }
   )";
-  runDataflow(Code, UnorderedElementsAre(
-                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
-                                      UnorderedElementsAre("foo", "bar"))))));
+  runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
+                        "p", HoldsFunctionCallLattice(HasCalledFunctions(
+                                 UnorderedElementsAre("foo", "bar"))))));
 }
 
 TEST_F(NoreturnDestructorTest, ConditionalOperatorLeftBranchReturns) {
@@ -246,9 +255,9 @@
       // [[p]]
     }
   )";
-  runDataflow(Code, UnorderedElementsAre(
-                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
-                                      UnorderedElementsAre("foo"))))));
+  runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
+                        "p", HoldsFunctionCallLattice(HasCalledFunctions(
+                                 UnorderedElementsAre("foo"))))));
 }
 
 TEST_F(NoreturnDestructorTest, ConditionalOperatorRightBranchReturns) {
@@ -261,9 +270,9 @@
       // [[p]]
     }
   )";
-  runDataflow(Code, UnorderedElementsAre(
-                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
-                                      UnorderedElementsAre("foo"))))));
+  runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
+                        "p", HoldsFunctionCallLattice(HasCalledFunctions(
+                                 UnorderedElementsAre("foo"))))));
 }
 
 TEST_F(NoreturnDestructorTest, ConditionalOperatorNestedBranchesDoNotReturn) {
@@ -290,9 +299,9 @@
       // [[p]]
     }
   )";
-  runDataflow(Code, UnorderedElementsAre(
-                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
-                                      UnorderedElementsAre("baz", "foo"))))));
+  runDataflow(Code, UnorderedElementsAre(IsStringMapEntry(
+                        "p", HoldsFunctionCallLattice(HasCalledFunctions(
+                                 UnorderedElementsAre("baz", "foo"))))));
   // FIXME: Called functions at point `p` should contain only "foo".
 }
 
@@ -386,16 +395,17 @@
   void runDataflow(llvm::StringRef Code, Matcher Match) {
     ASSERT_THAT_ERROR(
         test::checkDataflow<SpecialBoolAnalysis>(
-            Code, "target",
-            [](ASTContext &Context, Environment &Env) {
-              return SpecialBoolAnalysis(Context);
-            },
-            [&Match](
-                llvm::ArrayRef<
-                    std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                    Results,
-                ASTContext &ASTCtx) { Match(Results, ASTCtx); },
-            {"-fsyntax-only", "-std=c++17"}),
+            AnalysisInputs<SpecialBoolAnalysis>(
+                Code, ast_matchers::hasName("target"),
+                [](ASTContext &Context, Environment &Env) {
+                  return SpecialBoolAnalysis(Context);
+                })
+                .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
+            /*VerifyResults=*/[&Match](const llvm::StringMap<
+                                           DataflowAnalysisState<NoopLattice>>
+                                           &Results,
+                                       const AnalysisOutputs
+                                           &AO) { Match(Results, AO.ASTCtx); }),
         llvm::Succeeded());
   }
 };
@@ -422,16 +432,15 @@
     }
   )";
   runDataflow(
-      Code, [](llvm::ArrayRef<
-                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                   Results,
-               ASTContext &ASTCtx) {
-        ASSERT_THAT(Results, ElementsAre(Pair("p4", _), Pair("p3", _),
-                                         Pair("p2", _), Pair("p1", _)));
-        const Environment &Env1 = Results[3].second.Env;
-        const Environment &Env2 = Results[2].second.Env;
-        const Environment &Env3 = Results[1].second.Env;
-        const Environment &Env4 = Results[0].second.Env;
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(),
+                    UnorderedElementsAre("p1", "p2", "p3", "p4"));
+        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
+        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
+        const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
+        const Environment &Env4 = getEnvironmentAtAnnotation(Results, "p4");
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
@@ -537,20 +546,22 @@
       };
     )"));
     ASSERT_THAT_ERROR(
-        test::checkDataflow<OptionalIntAnalysis>(
-            Code, "target",
-            [this](ASTContext &Context, Environment &Env) {
-              assert(HasValueTop == nullptr);
-              HasValueTop =
-                  &Env.takeOwnership(std::make_unique<AtomicBoolValue>());
-              return OptionalIntAnalysis(Context, *HasValueTop);
-            },
-            [&Match](
-                llvm::ArrayRef<
-                    std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                    Results,
-                ASTContext &ASTCtx) { Match(Results, ASTCtx); },
-            {"-fsyntax-only", "-std=c++17"}, FilesContents),
+        checkDataflow<OptionalIntAnalysis>(
+            AnalysisInputs<OptionalIntAnalysis>(
+                Code, ast_matchers::hasName("target"),
+                [this](ASTContext &Context, Environment &Env) {
+                  assert(HasValueTop == nullptr);
+                  HasValueTop =
+                      &Env.takeOwnership(std::make_unique<AtomicBoolValue>());
+                  return OptionalIntAnalysis(Context, *HasValueTop);
+                })
+                .withASTBuildArgs({"-fsyntax-only", "-std=c++17"})
+                .withASTBuildVirtualMappedFiles(std::move(FilesContents)),
+            /*VerifyResults=*/[&Match](const llvm::StringMap<
+                                           DataflowAnalysisState<NoopLattice>>
+                                           &Results,
+                                       const AnalysisOutputs
+                                           &AO) { Match(Results, AO.ASTCtx); }),
         llvm::Succeeded());
   }
 
@@ -574,15 +585,12 @@
   )";
   runDataflow(
       Code,
-      [this](llvm::ArrayRef<
-                 std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                 Results,
+      [this](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
              ASTContext &ASTCtx) {
-        ASSERT_THAT(Results,
-                    ElementsAre(Pair("p3", _), Pair("p2", _), Pair("p1", _)));
-        const Environment &Env1 = Results[2].second.Env;
-        const Environment &Env2 = Results[1].second.Env;
-        const Environment &Env3 = Results[0].second.Env;
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2", "p3"));
+        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
+        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
+        const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
@@ -617,34 +625,33 @@
       /*[[p4]]*/
     }
   )";
-  runDataflow(Code,
-              [](llvm::ArrayRef<
-                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                     Results,
-                 ASTContext &ASTCtx) {
-                ASSERT_THAT(Results, ElementsAre(Pair("p4", _), Pair("p3", _),
-                                                 Pair("p2", _), Pair("p1", _)));
-                const Environment &Env1 = Results[3].second.Env;
-                const Environment &Env2 = Results[2].second.Env;
-                const Environment &Env3 = Results[1].second.Env;
-                const Environment &Env4 = Results[0].second.Env;
-
-                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
-                ASSERT_THAT(FooDecl, NotNull());
-
-                auto GetFooValue = [FooDecl](const Environment &Env) {
-                  return Env.getValue(*FooDecl, SkipPast::None);
-                };
-
-                EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
-                          &Env1.getBoolLiteralValue(false));
-                EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
-                          &Env2.getBoolLiteralValue(true));
-                EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"),
-                          &Env3.getBoolLiteralValue(true));
-                EXPECT_EQ(GetFooValue(Env4)->getProperty("has_value"),
-                          &Env4.getBoolLiteralValue(true));
-              });
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(),
+                    UnorderedElementsAre("p1", "p2", "p3", "p4"));
+        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
+        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
+        const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3");
+        const Environment &Env4 = getEnvironmentAtAnnotation(Results, "p4");
+
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        auto GetFooValue = [FooDecl](const Environment &Env) {
+          return Env.getValue(*FooDecl, SkipPast::None);
+        };
+
+        EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
+                  &Env1.getBoolLiteralValue(false));
+        EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
+                  &Env2.getBoolLiteralValue(true));
+        EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"),
+                  &Env3.getBoolLiteralValue(true));
+        EXPECT_EQ(GetFooValue(Env4)->getProperty("has_value"),
+                  &Env4.getBoolLiteralValue(true));
+      });
 }
 
 TEST_F(WideningTest, DistinctPointersToTheSameLocationAreEquivalent) {
@@ -658,26 +665,25 @@
       // [[p]]
     }
   )";
-  runDataflow(Code,
-              [](llvm::ArrayRef<
-                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                     Results,
-                 ASTContext &ASTCtx) {
-                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
-                const Environment &Env = Results[0].second.Env;
-
-                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
-                ASSERT_THAT(FooDecl, NotNull());
-
-                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
-                ASSERT_THAT(BarDecl, NotNull());
-
-                const auto *FooLoc = cast<ScalarStorageLocation>(
-                    Env.getStorageLocation(*FooDecl, SkipPast::None));
-                const auto *BarVal =
-                    cast<PointerValue>(Env.getValue(*BarDecl, SkipPast::None));
-                EXPECT_EQ(&BarVal->getPointeeLoc(), FooLoc);
-              });
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
+        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
+
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+        ASSERT_THAT(BarDecl, NotNull());
+
+        const auto *FooLoc = cast<ScalarStorageLocation>(
+            Env.getStorageLocation(*FooDecl, SkipPast::None));
+        const auto *BarVal =
+            cast<PointerValue>(Env.getValue(*BarDecl, SkipPast::None));
+        EXPECT_EQ(&BarVal->getPointeeLoc(), FooLoc);
+      });
 }
 
 TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) {
@@ -694,21 +700,20 @@
       /*[[p]]*/
     }
   )";
-  runDataflow(Code,
-              [](llvm::ArrayRef<
-                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                     Results,
-                 ASTContext &ASTCtx) {
-                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
-                const Environment &Env = Results[0].second.Env;
-
-                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
-                ASSERT_THAT(FooDecl, NotNull());
-
-                const auto *FooVal = Env.getValue(*FooDecl, SkipPast::None);
-                EXPECT_EQ(FooVal->getProperty("has_value"),
-                          &Env.getBoolLiteralValue(true));
-              });
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
+        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
+
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        const auto *FooVal = Env.getValue(*FooDecl, SkipPast::None);
+        EXPECT_EQ(FooVal->getProperty("has_value"),
+                  &Env.getBoolLiteralValue(true));
+      });
 }
 
 class FlowConditionTest : public Test {
@@ -716,17 +721,18 @@
   template <typename Matcher>
   void runDataflow(llvm::StringRef Code, Matcher Match) {
     ASSERT_THAT_ERROR(
-        test::checkDataflow<NoopAnalysis>(
-            Code, "target",
-            [](ASTContext &Context, Environment &Env) {
-              return NoopAnalysis(Context, true);
-            },
-            [&Match](
-                llvm::ArrayRef<
-                    std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                    Results,
-                ASTContext &ASTCtx) { Match(Results, ASTCtx); },
-            {"-fsyntax-only", "-std=c++17"}),
+        checkDataflow<NoopAnalysis>(
+            AnalysisInputs<NoopAnalysis>(
+                Code, ast_matchers::hasName("target"),
+                [](ASTContext &Context, Environment &Env) {
+                  return NoopAnalysis(Context, true);
+                })
+                .withASTBuildArgs({"-fsyntax-only", "-std=c++17"}),
+            /*VerifyResults=*/[&Match](const llvm::StringMap<
+                                           DataflowAnalysisState<NoopLattice>>
+                                           &Results,
+                                       const AnalysisOutputs
+                                           &AO) { Match(Results, AO.ASTCtx); }),
         llvm::Succeeded());
   }
 };
@@ -743,26 +749,25 @@
       }
     }
   )";
-  runDataflow(Code,
-              [](llvm::ArrayRef<
-                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                     Results,
-                 ASTContext &ASTCtx) {
-                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
-                ASSERT_THAT(FooDecl, NotNull());
-
-                ASSERT_THAT(Results, ElementsAre(Pair("p2", _), Pair("p1", _)));
-
-                const Environment &Env1 = Results[1].second.Env;
-                auto *FooVal1 =
-                    cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
-                EXPECT_TRUE(Env1.flowConditionImplies(*FooVal1));
-
-                const Environment &Env2 = Results[0].second.Env;
-                auto *FooVal2 =
-                    cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
-                EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
-              });
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
+
+        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
+        auto *FooVal1 =
+            cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
+        EXPECT_TRUE(Env1.flowConditionImplies(*FooVal1));
+
+        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
+        auto *FooVal2 =
+            cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
+        EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
+      });
 }
 
 TEST_F(FlowConditionTest, IfStmtSingleNegatedVar) {
@@ -777,26 +782,25 @@
       }
     }
   )";
-  runDataflow(Code,
-              [](llvm::ArrayRef<
-                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                     Results,
-                 ASTContext &ASTCtx) {
-                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
-                ASSERT_THAT(FooDecl, NotNull());
-
-                ASSERT_THAT(Results, ElementsAre(Pair("p2", _), Pair("p1", _)));
-
-                const Environment &Env1 = Results[1].second.Env;
-                auto *FooVal1 =
-                    cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
-                EXPECT_FALSE(Env1.flowConditionImplies(*FooVal1));
-
-                const Environment &Env2 = Results[0].second.Env;
-                auto *FooVal2 =
-                    cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
-                EXPECT_TRUE(Env2.flowConditionImplies(*FooVal2));
-              });
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
+
+        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
+        auto *FooVal1 =
+            cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
+        EXPECT_FALSE(Env1.flowConditionImplies(*FooVal1));
+
+        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
+        auto *FooVal2 =
+            cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
+        EXPECT_TRUE(Env2.flowConditionImplies(*FooVal2));
+      });
 }
 
 TEST_F(FlowConditionTest, WhileStmt) {
@@ -809,15 +813,14 @@
     }
   )";
   runDataflow(
-      Code, [](llvm::ArrayRef<
-                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                   Results,
-               ASTContext &ASTCtx) {
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
 
-        ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
-        const Environment &Env = Results[0].second.Env;
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
+        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 
         auto *FooVal = cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
         EXPECT_TRUE(Env.flowConditionImplies(*FooVal));
@@ -836,35 +839,29 @@
       }
     }
   )";
-  runDataflow(Code,
-              [](llvm::ArrayRef<
-                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                     Results,
-                 ASTContext &ASTCtx) {
-                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
-                ASSERT_THAT(FooDecl, NotNull());
-
-                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
-                ASSERT_THAT(BarDecl, NotNull());
-
-                ASSERT_THAT(Results, ElementsAre(Pair("p2", _), Pair("p1", _)));
-
-                const Environment &Env1 = Results[1].second.Env;
-                auto *FooVal1 =
-                    cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
-                auto *BarVal1 =
-                    cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
-                EXPECT_TRUE(Env1.flowConditionImplies(*FooVal1));
-                EXPECT_TRUE(Env1.flowConditionImplies(*BarVal1));
-
-                const Environment &Env2 = Results[0].second.Env;
-                auto *FooVal2 =
-                    cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
-                auto *BarVal2 =
-                    cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
-                EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
-                EXPECT_FALSE(Env2.flowConditionImplies(*BarVal2));
-              });
+  runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
+                           &Results,
+                       ASTContext &ASTCtx) {
+    const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+    ASSERT_THAT(FooDecl, NotNull());
+
+    const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+    ASSERT_THAT(BarDecl, NotNull());
+
+    ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
+
+    const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
+    auto *FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
+    auto *BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
+    EXPECT_TRUE(Env1.flowConditionImplies(*FooVal1));
+    EXPECT_TRUE(Env1.flowConditionImplies(*BarVal1));
+
+    const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
+    auto *FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
+    auto *BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
+    EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
+    EXPECT_FALSE(Env2.flowConditionImplies(*BarVal2));
+  });
 }
 
 TEST_F(FlowConditionTest, Disjunction) {
@@ -879,35 +876,29 @@
       }
     }
   )";
-  runDataflow(Code,
-              [](llvm::ArrayRef<
-                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                     Results,
-                 ASTContext &ASTCtx) {
-                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
-                ASSERT_THAT(FooDecl, NotNull());
-
-                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
-                ASSERT_THAT(BarDecl, NotNull());
-
-                ASSERT_THAT(Results, ElementsAre(Pair("p2", _), Pair("p1", _)));
-
-                const Environment &Env1 = Results[1].second.Env;
-                auto *FooVal1 =
-                    cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
-                auto *BarVal1 =
-                    cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
-                EXPECT_FALSE(Env1.flowConditionImplies(*FooVal1));
-                EXPECT_FALSE(Env1.flowConditionImplies(*BarVal1));
-
-                const Environment &Env2 = Results[0].second.Env;
-                auto *FooVal2 =
-                    cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
-                auto *BarVal2 =
-                    cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
-                EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
-                EXPECT_FALSE(Env2.flowConditionImplies(*BarVal2));
-              });
+  runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
+                           &Results,
+                       ASTContext &ASTCtx) {
+    const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+    ASSERT_THAT(FooDecl, NotNull());
+
+    const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+    ASSERT_THAT(BarDecl, NotNull());
+
+    ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
+
+    const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
+    auto *FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
+    auto *BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
+    EXPECT_FALSE(Env1.flowConditionImplies(*FooVal1));
+    EXPECT_FALSE(Env1.flowConditionImplies(*BarVal1));
+
+    const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
+    auto *FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
+    auto *BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
+    EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
+    EXPECT_FALSE(Env2.flowConditionImplies(*BarVal2));
+  });
 }
 
 TEST_F(FlowConditionTest, NegatedConjunction) {
@@ -922,35 +913,29 @@
       }
     }
   )";
-  runDataflow(Code,
-              [](llvm::ArrayRef<
-                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                     Results,
-                 ASTContext &ASTCtx) {
-                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
-                ASSERT_THAT(FooDecl, NotNull());
-
-                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
-                ASSERT_THAT(BarDecl, NotNull());
-
-                ASSERT_THAT(Results, ElementsAre(Pair("p2", _), Pair("p1", _)));
-
-                const Environment &Env1 = Results[1].second.Env;
-                auto *FooVal1 =
-                    cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
-                auto *BarVal1 =
-                    cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
-                EXPECT_FALSE(Env1.flowConditionImplies(*FooVal1));
-                EXPECT_FALSE(Env1.flowConditionImplies(*BarVal1));
-
-                const Environment &Env2 = Results[0].second.Env;
-                auto *FooVal2 =
-                    cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
-                auto *BarVal2 =
-                    cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
-                EXPECT_TRUE(Env2.flowConditionImplies(*FooVal2));
-                EXPECT_TRUE(Env2.flowConditionImplies(*BarVal2));
-              });
+  runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
+                           &Results,
+                       ASTContext &ASTCtx) {
+    const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+    ASSERT_THAT(FooDecl, NotNull());
+
+    const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+    ASSERT_THAT(BarDecl, NotNull());
+
+    ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
+
+    const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
+    auto *FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
+    auto *BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
+    EXPECT_FALSE(Env1.flowConditionImplies(*FooVal1));
+    EXPECT_FALSE(Env1.flowConditionImplies(*BarVal1));
+
+    const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
+    auto *FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
+    auto *BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
+    EXPECT_TRUE(Env2.flowConditionImplies(*FooVal2));
+    EXPECT_TRUE(Env2.flowConditionImplies(*BarVal2));
+  });
 }
 
 TEST_F(FlowConditionTest, DeMorgan) {
@@ -965,35 +950,29 @@
       }
     }
   )";
-  runDataflow(Code,
-              [](llvm::ArrayRef<
-                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                     Results,
-                 ASTContext &ASTCtx) {
-                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
-                ASSERT_THAT(FooDecl, NotNull());
-
-                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
-                ASSERT_THAT(BarDecl, NotNull());
-
-                ASSERT_THAT(Results, ElementsAre(Pair("p2", _), Pair("p1", _)));
-
-                const Environment &Env1 = Results[1].second.Env;
-                auto *FooVal1 =
-                    cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
-                auto *BarVal1 =
-                    cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
-                EXPECT_TRUE(Env1.flowConditionImplies(*FooVal1));
-                EXPECT_TRUE(Env1.flowConditionImplies(*BarVal1));
-
-                const Environment &Env2 = Results[0].second.Env;
-                auto *FooVal2 =
-                    cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
-                auto *BarVal2 =
-                    cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
-                EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
-                EXPECT_FALSE(Env2.flowConditionImplies(*BarVal2));
-              });
+  runDataflow(Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
+                           &Results,
+                       ASTContext &ASTCtx) {
+    const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+    ASSERT_THAT(FooDecl, NotNull());
+
+    const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+    ASSERT_THAT(BarDecl, NotNull());
+
+    ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
+
+    const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
+    auto *FooVal1 = cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::None));
+    auto *BarVal1 = cast<BoolValue>(Env1.getValue(*BarDecl, SkipPast::None));
+    EXPECT_TRUE(Env1.flowConditionImplies(*FooVal1));
+    EXPECT_TRUE(Env1.flowConditionImplies(*BarVal1));
+
+    const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
+    auto *FooVal2 = cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::None));
+    auto *BarVal2 = cast<BoolValue>(Env2.getValue(*BarDecl, SkipPast::None));
+    EXPECT_FALSE(Env2.flowConditionImplies(*FooVal2));
+    EXPECT_FALSE(Env2.flowConditionImplies(*BarVal2));
+  });
 }
 
 TEST_F(FlowConditionTest, Join) {
@@ -1011,16 +990,15 @@
     }
   )";
   runDataflow(
-      Code, [](llvm::ArrayRef<
-                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                   Results,
-               ASTContext &ASTCtx) {
-        ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
 
-        const Environment &Env = Results[0].second.Env;
+        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
         auto *FooVal = cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
         EXPECT_TRUE(Env.flowConditionImplies(*FooVal));
       });
@@ -1045,12 +1023,11 @@
     }
   )";
   runDataflow(
-      Code, [](llvm::ArrayRef<
-                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                   Results,
-               ASTContext &ASTCtx) {
-        ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
-        const Environment &Env = Results[0].second.Env;
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
+        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 
         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
         ASSERT_THAT(BarDecl, NotNull());
@@ -1088,12 +1065,11 @@
     }
   )";
   runDataflow(
-      Code, [](llvm::ArrayRef<
-                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                   Results,
-               ASTContext &ASTCtx) {
-        ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
-        const Environment &Env = Results[0].second.Env;
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
+        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 
         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
         ASSERT_THAT(BarDecl, NotNull());
@@ -1124,12 +1100,11 @@
     }
   )";
   runDataflow(
-      Code, [](llvm::ArrayRef<
-                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                   Results,
-               ASTContext &ASTCtx) {
-        ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
-        const Environment &Env = Results[0].second.Env;
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
+        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 
         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
         ASSERT_THAT(BarDecl, NotNull());
@@ -1155,20 +1130,20 @@
     }
   )";
   runDataflow(
-      Code, [](llvm::ArrayRef<
-                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                   Results,
-               ASTContext &ASTCtx) {
-        ASSERT_THAT(Results, ElementsAre(Pair("p2", _), Pair("p1", _)));
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2"));
+
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
 
-        const Environment &Env1 = Results[1].second.Env;
+        const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1");
         auto &FooVal1 =
             *cast<BoolValue>(Env1.getValue(*FooDecl, SkipPast::Reference));
         EXPECT_TRUE(Env1.flowConditionImplies(FooVal1));
 
-        const Environment &Env2 = Results[0].second.Env;
+        const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2");
         auto &FooVal2 =
             *cast<BoolValue>(Env2.getValue(*FooDecl, SkipPast::Reference));
         EXPECT_FALSE(Env2.flowConditionImplies(FooVal2));
diff --git a/llvm/include/llvm/ADT/StringMapEntry.h b/llvm/include/llvm/ADT/StringMapEntry.h
--- a/llvm/include/llvm/ADT/StringMapEntry.h
+++ b/llvm/include/llvm/ADT/StringMapEntry.h
@@ -102,6 +102,8 @@
 public:
   using StringMapEntryStorage<ValueTy>::StringMapEntryStorage;
 
+  using ValueType = ValueTy;
+
   StringRef getKey() const {
     return StringRef(getKeyData(), this->getKeyLength());
   }
diff --git a/llvm/include/llvm/Testing/ADT/StringMap.h b/llvm/include/llvm/Testing/ADT/StringMap.h
new file mode 100644
--- /dev/null
+++ b/llvm/include/llvm/Testing/ADT/StringMap.h
@@ -0,0 +1,46 @@
+//===- llvm/Testing/ADT/StringMap.h ---------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TESTING_ADT_STRINGMAP_H_
+#define LLVM_TESTING_ADT_STRINGMAP_H_
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Testing/ADT/StringMapEntry.h"
+#include <ostream>
+#include <sstream>
+
+namespace llvm {
+
+/// Support for printing to std::ostream, for use with e.g. producing more
+/// useful error messages with Google Test.
+template <typename T>
+std::ostream &operator<<(std::ostream &OS, const StringMap<T> &M) {
+  if (M.empty()) {
+    return OS << "{ }";
+  }
+
+  std::vector<std::string> Lines;
+  for (const auto &E : M) {
+    std::ostringstream SS;
+    SS << E << ",";
+    Lines.push_back(SS.str());
+  }
+  llvm::sort(Lines);
+  Lines.insert(Lines.begin(), "{");
+  Lines.insert(Lines.end(), "}");
+
+  return OS << llvm::formatv("{0:$[\n]}",
+                             make_range(Lines.begin(), Lines.end()))
+                   .str();
+}
+
+} // namespace llvm
+
+#endif
diff --git a/llvm/include/llvm/Testing/ADT/StringMapEntry.h b/llvm/include/llvm/Testing/ADT/StringMapEntry.h
new file mode 100644
--- /dev/null
+++ b/llvm/include/llvm/Testing/ADT/StringMapEntry.h
@@ -0,0 +1,129 @@
+//===- llvm/Testing/ADT/StringMapEntry.h ----------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TESTING_ADT_STRINGMAPENTRY_H_
+#define LLVM_TESTING_ADT_STRINGMAPENTRY_H_
+
+#include "llvm/ADT/StringMapEntry.h"
+#include "gmock/gmock.h"
+#include <ostream>
+#include <type_traits>
+
+namespace llvm {
+namespace detail {
+
+template <typename T, typename = std::void_t<>>
+struct CanOutputToOStream : std::false_type {};
+
+template <typename T>
+struct CanOutputToOStream<T, std::void_t<decltype(std::declval<std::ostream &>()
+                                                  << std::declval<T>())>>
+    : std::true_type {};
+
+} // namespace detail
+
+/// Support for printing to std::ostream, for use with e.g. producing more
+/// useful error messages with Google Test.
+template <typename T>
+std::ostream &operator<<(std::ostream &OS, const StringMapEntry<T> &E) {
+  OS << "{\"" << E.getKey().data() << "\": ";
+  if constexpr (detail::CanOutputToOStream<decltype(E.getValue())>::value) {
+    OS << E.getValue();
+  } else {
+    OS << "non-printable value";
+  }
+  return OS << "}";
+}
+
+namespace detail {
+
+template <typename StringMapEntryT>
+class StringMapEntryMatcherImpl
+    : public testing::MatcherInterface<StringMapEntryT> {
+public:
+  using ValueT = typename std::remove_reference_t<StringMapEntryT>::ValueType;
+
+  template <typename KeyMatcherT, typename ValueMatcherT>
+  StringMapEntryMatcherImpl(KeyMatcherT KeyMatcherArg,
+                            ValueMatcherT ValueMatcherArg)
+      : KeyMatcher(
+            testing::SafeMatcherCast<const std::string &>(KeyMatcherArg)),
+        ValueMatcher(
+            testing::SafeMatcherCast<const ValueT &>(ValueMatcherArg)) {}
+
+  void DescribeTo(std::ostream *OS) const override {
+    *OS << "has a string key that ";
+    KeyMatcher.DescribeTo(OS);
+    *OS << ", and has a value that ";
+    ValueMatcher.DescribeTo(OS);
+  }
+
+  void DescribeNegationTo(std::ostream *OS) const override {
+    *OS << "has a string key that ";
+    KeyMatcher.DescribeNegationTo(OS);
+    *OS << ", or has a value that ";
+    ValueMatcher.DescribeNegationTo(OS);
+  }
+
+  bool
+  MatchAndExplain(StringMapEntryT Entry,
+                  testing::MatchResultListener *ResultListener) const override {
+    testing::StringMatchResultListener KeyListener;
+    if (!KeyMatcher.MatchAndExplain(Entry.getKey().data(), &KeyListener)) {
+      *ResultListener << ("which has a string key " +
+                          (KeyListener.str().empty() ? "that doesn't match"
+                                                     : KeyListener.str()));
+      return false;
+    }
+    testing::StringMatchResultListener ValueListener;
+    if (!ValueMatcher.MatchAndExplain(Entry.getValue(), &ValueListener)) {
+      *ResultListener << ("which has a value " + (ValueListener.str().empty()
+                                                      ? "that doesn't match"
+                                                      : ValueListener.str()));
+      return false;
+    }
+    *ResultListener << "which is a match";
+    return true;
+  }
+
+private:
+  const testing::Matcher<const std::string &> KeyMatcher;
+  const testing::Matcher<const ValueT &> ValueMatcher;
+};
+
+template <typename KeyMatcherT, typename ValueMatcherT>
+class StringMapEntryMatcher {
+public:
+  StringMapEntryMatcher(KeyMatcherT KMArg, ValueMatcherT VMArg)
+      : KM(std::move(KMArg)), VM(std::move(VMArg)) {}
+
+  template <typename StringMapEntryT>
+  operator testing::Matcher<StringMapEntryT>() const { // NOLINT
+    return testing::Matcher<StringMapEntryT>(
+        new StringMapEntryMatcherImpl<const StringMapEntryT &>(KM, VM));
+  }
+
+private:
+  const KeyMatcherT KM;
+  const ValueMatcherT VM;
+};
+
+} // namespace detail
+
+/// Returns a gMock matcher that matches a `StringMapEntry` whose string key
+/// matches `KeyMatcher`, and whose value matches `ValueMatcher`.
+template <typename KeyMatcherT, typename ValueMatcherT>
+detail::StringMapEntryMatcher<KeyMatcherT, ValueMatcherT>
+IsStringMapEntry(KeyMatcherT KM, ValueMatcherT VM) {
+  return detail::StringMapEntryMatcher<KeyMatcherT, ValueMatcherT>(
+      std::move(KM), std::move(VM));
+}
+
+} // namespace llvm
+
+#endif
diff --git a/llvm/unittests/Testing/ADT/CMakeLists.txt b/llvm/unittests/Testing/ADT/CMakeLists.txt
new file mode 100644
--- /dev/null
+++ b/llvm/unittests/Testing/ADT/CMakeLists.txt
@@ -0,0 +1,8 @@
+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_llvm_unittest(TestingADTTests
+  StringMapEntryTest.cpp
+  StringMapTest.cpp
+  )
diff --git a/llvm/unittests/Testing/ADT/StringMapEntryTest.cpp b/llvm/unittests/Testing/ADT/StringMapEntryTest.cpp
new file mode 100644
--- /dev/null
+++ b/llvm/unittests/Testing/ADT/StringMapEntryTest.cpp
@@ -0,0 +1,88 @@
+//===- StringMapEntryTest.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/Testing/ADT/StringMapEntry.h"
+#include "llvm/ADT/StringMap.h"
+
+#include "gtest/gtest.h"
+#include <sstream>
+
+namespace llvm {
+namespace {
+
+using testing::Gt;
+using testing::Matcher;
+using testing::StrCaseEq;
+using testing::StringMatchResultListener;
+using testing::UnorderedElementsAre;
+
+template <typename T> std::string Describe(const Matcher<T> &M, bool Match) {
+  std::stringstream SS;
+  if (Match) {
+    M.DescribeTo(&SS);
+  } else {
+    M.DescribeNegationTo(&SS);
+  }
+  return SS.str();
+}
+
+template <typename T, typename V>
+std::string ExplainMatch(const Matcher<T> &Matcher, const V &Value) {
+  StringMatchResultListener Listener;
+  Matcher.MatchAndExplain(Value, &Listener);
+  return Listener.str();
+}
+
+TEST(IsStringMapEntryTest, InnerMatchersAreExactValues) {
+  llvm::StringMap<int> Map = {{"A", 1}};
+  EXPECT_THAT(*Map.find("A"), IsStringMapEntry("A", 1));
+}
+
+TEST(IsStringMapEntryTest, InnerMatchersAreOtherMatchers) {
+  llvm::StringMap<int> Map = {{"A", 1}};
+  EXPECT_THAT(*Map.find("A"), IsStringMapEntry(StrCaseEq("a"), Gt(0)));
+}
+
+TEST(IsStringMapEntryTest, UseAsInnerMatcher) {
+  llvm::StringMap<int> Map = {{"A", 1}, {"B", 2}};
+  EXPECT_THAT(Map, UnorderedElementsAre(IsStringMapEntry("A", 1),
+                                        IsStringMapEntry("B", 2)));
+}
+
+TEST(IsStringMapEntryTest, DescribeSelf) {
+  Matcher<llvm::StringMapEntry<int>> M = IsStringMapEntry("A", 1);
+  EXPECT_EQ(
+      R"(has a string key that is equal to "A", and has a value that is equal to 1)",
+      Describe(M, true));
+  EXPECT_EQ(
+      R"(has a string key that isn't equal to "A", or has a value that isn't equal to 1)",
+      Describe(M, false));
+}
+
+TEST(IsStringMapEntryTest, ExplainSelfMatchSuccess) {
+  llvm::StringMap<int> Map = {{"A", 1}};
+  Matcher<llvm::StringMapEntry<int>> M = IsStringMapEntry("A", 1);
+  EXPECT_EQ(R"(which is a match)", ExplainMatch(M, *Map.find("A")));
+}
+
+TEST(IsStringMapEntryTest, ExplainSelfMatchFailsOnKey) {
+  llvm::StringMap<int> Map = {{"B", 1}};
+  Matcher<llvm::StringMapEntry<int>> M = IsStringMapEntry("A", 1);
+  EXPECT_EQ(R"(which has a string key that doesn't match)",
+            ExplainMatch(M, *Map.find("B")));
+}
+
+TEST(IsStringMapEntryTest, ExplainSelfMatchFailsOnValue) {
+  llvm::StringMap<int> Map = {{"A", 2}};
+  Matcher<llvm::StringMapEntry<int>> M = IsStringMapEntry("A", 1);
+  EXPECT_EQ(R"(which has a value that doesn't match)",
+            ExplainMatch(M, *Map.find("A")));
+}
+
+} // namespace
+} // namespace llvm
diff --git a/llvm/unittests/Testing/ADT/StringMapTest.cpp b/llvm/unittests/Testing/ADT/StringMapTest.cpp
new file mode 100644
--- /dev/null
+++ b/llvm/unittests/Testing/ADT/StringMapTest.cpp
@@ -0,0 +1,55 @@
+//===- StringMapTest.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/Testing/ADT/StringMap.h"
+#include "llvm/ADT/StringMap.h"
+
+#include "gtest/gtest.h"
+#include <sstream>
+
+namespace llvm {
+namespace {
+
+TEST(StringMapTest, StringMapStream) {
+  std::ostringstream OS;
+  StringMap<int> Map;
+  Map["A"] = 42;
+  Map["Z"] = 35;
+  Map["B"] = 7;
+  OS << Map;
+
+  EXPECT_EQ(OS.str(), R"({
+{"A": 42},
+{"B": 7},
+{"Z": 35},
+})");
+}
+
+TEST(StringMapTest, NestedStringMapStream) {
+  std::ostringstream OS;
+  StringMap<StringMap<int>> Map;
+  Map["Z"];
+  Map["A"]["Apple"] = 5;
+  Map["B"]["Bee"] = 3;
+  Map["A"]["Axe"] = 3;
+  OS << Map;
+
+  EXPECT_EQ(OS.str(), R"({
+{"A": {
+{"Apple": 5},
+{"Axe": 3},
+}},
+{"B": {
+{"Bee": 3},
+}},
+{"Z": { }},
+})");
+}
+
+} // namespace
+} // namespace llvm
diff --git a/llvm/unittests/Testing/CMakeLists.txt b/llvm/unittests/Testing/CMakeLists.txt
--- a/llvm/unittests/Testing/CMakeLists.txt
+++ b/llvm/unittests/Testing/CMakeLists.txt
@@ -1 +1,2 @@
+add_subdirectory(ADT)
 add_subdirectory(Support)
diff --git a/utils/bazel/llvm-project-overlay/llvm/BUILD.bazel b/utils/bazel/llvm-project-overlay/llvm/BUILD.bazel
--- a/utils/bazel/llvm-project-overlay/llvm/BUILD.bazel
+++ b/utils/bazel/llvm-project-overlay/llvm/BUILD.bazel
@@ -4181,6 +4181,19 @@
     srcs = ["utils/lit/lit.py"] + glob(["utils/lit/lit/**/*.py"]),
 )
 
+cc_library(
+    name = "TestingADT",
+    testonly = True,
+    hdrs = glob([
+        "include/llvm/Testing/ADT/*.h",
+    ]),
+    copts = llvm_copts,
+    deps = [
+        ":Support",
+        ":gmock",
+    ],
+)
+
 cc_library(
     name = "TestingSupport",
     testonly = True,
diff --git a/utils/bazel/llvm-project-overlay/llvm/unittests/BUILD.bazel b/utils/bazel/llvm-project-overlay/llvm/unittests/BUILD.bazel
--- a/utils/bazel/llvm-project-overlay/llvm/unittests/BUILD.bazel
+++ b/utils/bazel/llvm-project-overlay/llvm/unittests/BUILD.bazel
@@ -644,6 +644,23 @@
     ],
 )
 
+cc_test(
+    name = "testing_adt_tests",
+    size = "small",
+    srcs = glob(
+        [
+            "Testing/ADT/*.cpp",
+        ],
+        allow_empty = False,
+    ),
+    deps = [
+        "//llvm:Support",
+        "//llvm:TestingADT",
+        "//llvm:gtest",
+        "//llvm:gtest_main",
+    ],
+)
+
 cc_test(
     name = "transforms_tests",
     size = "small",