Index: llvm/trunk/include/llvm/XRay/BlockVerifier.h
===================================================================
--- llvm/trunk/include/llvm/XRay/BlockVerifier.h
+++ llvm/trunk/include/llvm/XRay/BlockVerifier.h
@@ -0,0 +1,69 @@
+//===- BlockVerifier.h - FDR Block Verifier -------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// An implementation of the RecordVisitor which verifies a sequence of records
+// associated with a block, following the FDR mode log format's specifications.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_INCLUDE_LLVM_XRAY_BLOCKVERIFIER_H_
+#define LLVM_INCLUDE_LLVM_XRAY_BLOCKVERIFIER_H_
+
+#include "llvm/XRay/FDRRecords.h"
+#include <array>
+#include <bitset>
+
+namespace llvm {
+namespace xray {
+
+class BlockVerifier : public RecordVisitor {
+public:
+  // We force State elements to be size_t, to be used as indices for containers.
+  enum class State : std::size_t {
+    Unknown,
+    BufferExtents,
+    NewBuffer,
+    WallClockTime,
+    PIDEntry,
+    NewCPUId,
+    TSCWrap,
+    CustomEvent,
+    Function,
+    CallArg,
+    EndOfBuffer,
+    StateMax,
+  };
+
+private:
+  // We keep track of the current record seen by the verifier.
+  State CurrentRecord = State::Unknown;
+
+  // Transitions the current record to the new record, records an error on
+  // invalid transitions.
+  Error transition(State To);
+
+public:
+  Error visit(BufferExtents &) override;
+  Error visit(WallclockRecord &) override;
+  Error visit(NewCPUIDRecord &) override;
+  Error visit(TSCWrapRecord &) override;
+  Error visit(CustomEventRecord &) override;
+  Error visit(CallArgRecord &) override;
+  Error visit(PIDRecord &) override;
+  Error visit(NewBufferRecord &) override;
+  Error visit(EndBufferRecord &) override;
+  Error visit(FunctionRecord &) override;
+
+  Error verify();
+  void reset();
+};
+
+} // namespace xray
+} // namespace llvm
+
+#endif // LLVM_INCLUDE_LLVM_XRAY_BLOCKVERIFIER_H_
Index: llvm/trunk/lib/XRay/BlockVerifier.cpp
===================================================================
--- llvm/trunk/lib/XRay/BlockVerifier.cpp
+++ llvm/trunk/lib/XRay/BlockVerifier.cpp
@@ -0,0 +1,187 @@
+//===- BlockVerifier.cpp - FDR Block Verifier -----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/XRay/BlockVerifier.h"
+#include "llvm/Support/Error.h"
+
+namespace llvm {
+namespace xray {
+namespace {
+
+constexpr unsigned long long mask(BlockVerifier::State S) {
+  return 1uLL << static_cast<std::size_t>(S);
+}
+
+constexpr std::size_t number(BlockVerifier::State S) {
+  return static_cast<std::size_t>(S);
+}
+
+StringRef recordToString(BlockVerifier::State R) {
+  switch (R) {
+  case BlockVerifier::State::BufferExtents:
+    return "BufferExtents";
+  case BlockVerifier::State::NewBuffer:
+    return "NewBuffer";
+  case BlockVerifier::State::WallClockTime:
+    return "WallClockTime";
+  case BlockVerifier::State::PIDEntry:
+    return "PIDEntry";
+  case BlockVerifier::State::NewCPUId:
+    return "NewCPUId";
+  case BlockVerifier::State::TSCWrap:
+    return "TSCWrap";
+  case BlockVerifier::State::CustomEvent:
+    return "CustomEvent";
+  case BlockVerifier::State::Function:
+    return "Function";
+  case BlockVerifier::State::CallArg:
+    return "CallArg";
+  case BlockVerifier::State::EndOfBuffer:
+    return "EndOfBuffer";
+  case BlockVerifier::State::StateMax:
+  case BlockVerifier::State::Unknown:
+    return "Unknown";
+  }
+  llvm_unreachable("Unkown state!");
+}
+
+struct Transition {
+  BlockVerifier::State From;
+  std::bitset<number(BlockVerifier::State::StateMax)> ToStates;
+};
+
+} // namespace
+
+Error BlockVerifier::transition(State To) {
+  using ToSet = std::bitset<number(State::StateMax)>;
+  static constexpr std::array<const Transition, number(State::StateMax)>
+      TransitionTable{{{State::Unknown,
+                        {mask(State::BufferExtents) | mask(State::NewBuffer)}},
+
+                       {State::BufferExtents, {mask(State::NewBuffer)}},
+
+                       {State::NewBuffer, {mask(State::WallClockTime)}},
+
+                       {State::WallClockTime,
+                        {mask(State::PIDEntry) | mask(State::NewCPUId)}},
+
+                       {State::PIDEntry, {mask(State::NewCPUId)}},
+
+                       {State::NewCPUId,
+                        {mask(State::NewCPUId) | mask(State::TSCWrap) |
+                         mask(State::CustomEvent) | mask(State::Function) |
+                         mask(State::EndOfBuffer)}},
+
+                       {State::TSCWrap,
+                        {mask(State::TSCWrap) | mask(State::NewCPUId) |
+                         mask(State::CustomEvent) | mask(State::Function) |
+                         mask(State::EndOfBuffer)}},
+
+                       {State::CustomEvent,
+                        {mask(State::CustomEvent) | mask(State::TSCWrap) |
+                         mask(State::NewCPUId) | mask(State::Function) |
+                         mask(State::EndOfBuffer)}},
+
+                       {State::Function,
+                        {mask(State::Function) | mask(State::TSCWrap) |
+                         mask(State::NewCPUId) | mask(State::CustomEvent) |
+                         mask(State::CallArg) | mask(State::EndOfBuffer)}},
+
+                       {State::CallArg,
+                        {mask(State::CallArg) | mask(State::Function) |
+                         mask(State::TSCWrap) | mask(State::NewCPUId) |
+                         mask(State::CustomEvent) | mask(State::EndOfBuffer)}},
+
+                       {State::EndOfBuffer, {}}}};
+
+  if (CurrentRecord >= State::StateMax)
+    return createStringError(
+        std::make_error_code(std::errc::executable_format_error),
+        "BUG (BlockVerifier): Cannot find transition table entry for %s, "
+        "transitioning to %s.",
+        recordToString(CurrentRecord).data(), recordToString(To).data());
+
+  // If we're at an EndOfBuffer record, we ignore anything that follows that
+  // isn't a NewBuffer record.
+  if (CurrentRecord == State::EndOfBuffer && To != State::NewBuffer)
+    return Error::success();
+
+  auto &Mapping = TransitionTable[number(CurrentRecord)];
+  auto &From = Mapping.From;
+  auto &Destinations = Mapping.ToStates;
+  assert(From == CurrentRecord && "BUG: Wrong index for record mapping.");
+  if ((Destinations & ToSet(mask(To))) == 0)
+    return createStringError(
+        std::make_error_code(std::errc::executable_format_error),
+        "BlockVerifier: Invalid transition from %s to %s.",
+        recordToString(CurrentRecord).data(), recordToString(To).data());
+
+  CurrentRecord = To;
+  return Error::success();
+} // namespace xray
+
+Error BlockVerifier::visit(BufferExtents &) {
+  return transition(State::BufferExtents);
+}
+
+Error BlockVerifier::visit(WallclockRecord &) {
+  return transition(State::WallClockTime);
+}
+
+Error BlockVerifier::visit(NewCPUIDRecord &) {
+  return transition(State::NewCPUId);
+}
+
+Error BlockVerifier::visit(TSCWrapRecord &) {
+  return transition(State::TSCWrap);
+}
+
+Error BlockVerifier::visit(CustomEventRecord &) {
+  return transition(State::CustomEvent);
+}
+
+Error BlockVerifier::visit(CallArgRecord &) {
+  return transition(State::CallArg);
+}
+
+Error BlockVerifier::visit(PIDRecord &) { return transition(State::PIDEntry); }
+
+Error BlockVerifier::visit(NewBufferRecord &) {
+  return transition(State::NewBuffer);
+}
+
+Error BlockVerifier::visit(EndBufferRecord &) {
+  return transition(State::EndOfBuffer);
+}
+
+Error BlockVerifier::visit(FunctionRecord &) {
+  return transition(State::Function);
+}
+
+Error BlockVerifier::verify() {
+  // The known terminal conditions are the following:
+  switch (CurrentRecord) {
+  case State::EndOfBuffer:
+  case State::NewCPUId:
+  case State::CustomEvent:
+  case State::Function:
+  case State::CallArg:
+  case State::TSCWrap:
+    return Error::success();
+  default:
+    return createStringError(
+        std::make_error_code(std::errc::executable_format_error),
+        "BlockVerifier: Invalid terminal condition %s, malformed block.",
+        recordToString(CurrentRecord).data());
+  }
+}
+
+void BlockVerifier::reset() { CurrentRecord = State::Unknown; }
+
+} // namespace xray
+} // namespace llvm
Index: llvm/trunk/lib/XRay/CMakeLists.txt
===================================================================
--- llvm/trunk/lib/XRay/CMakeLists.txt
+++ llvm/trunk/lib/XRay/CMakeLists.txt
@@ -1,5 +1,6 @@
 add_llvm_library(LLVMXRay
   BlockIndexer.cpp
+  BlockVerifier.cpp
   FDRRecordProducer.cpp
   FDRRecords.cpp
   FDRTraceWriter.cpp
Index: llvm/trunk/unittests/XRay/CMakeLists.txt
===================================================================
--- llvm/trunk/unittests/XRay/CMakeLists.txt
+++ llvm/trunk/unittests/XRay/CMakeLists.txt
@@ -1,11 +1,13 @@
 set(LLVM_LINK_COMPONENTS
   Support
   XRay
+  TestingSupport
   )
 
 add_llvm_unittest(XRayTests
   ProfileTest.cpp
   FDRBlockIndexerTest.cpp
+  FDRBlockVerifierTest.cpp
   FDRProducerConsumerTest.cpp
   FDRRecordPrinterTest.cpp
   FDRTraceWriterTest.cpp
Index: llvm/trunk/unittests/XRay/FDRBlockVerifierTest.cpp
===================================================================
--- llvm/trunk/unittests/XRay/FDRBlockVerifierTest.cpp
+++ llvm/trunk/unittests/XRay/FDRBlockVerifierTest.cpp
@@ -0,0 +1,139 @@
+//===- llvm/unittest/XRay/FDRBlockVerifierTest.cpp --------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/Testing/Support/Error.h"
+#include "llvm/XRay/BlockIndexer.h"
+#include "llvm/XRay/BlockVerifier.h"
+#include "llvm/XRay/FDRLogBuilder.h"
+#include "llvm/XRay/FDRRecords.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace xray {
+namespace {
+
+using ::testing::ElementsAre;
+using ::testing::Not;
+using ::testing::SizeIs;
+
+TEST(FDRBlockVerifierTest, ValidBlocksV3) {
+  auto Block0 = LogBuilder()
+                    .add<BufferExtents>(80)
+                    .add<NewBufferRecord>(1)
+                    .add<WallclockRecord>(1, 2)
+                    .add<PIDRecord>(1)
+                    .add<NewCPUIDRecord>(1)
+                    .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                    .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                    .consume();
+  auto Block1 = LogBuilder()
+                    .add<BufferExtents>(80)
+                    .add<NewBufferRecord>(1)
+                    .add<WallclockRecord>(1, 2)
+                    .add<PIDRecord>(1)
+                    .add<NewCPUIDRecord>(1)
+                    .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                    .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                    .consume();
+  auto Block2 = LogBuilder()
+                    .add<BufferExtents>(80)
+                    .add<NewBufferRecord>(2)
+                    .add<WallclockRecord>(1, 2)
+                    .add<PIDRecord>(1)
+                    .add<NewCPUIDRecord>(2)
+                    .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                    .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                    .consume();
+  BlockIndexer::Index Index;
+  BlockIndexer Indexer(Index);
+  for (auto B : {std::ref(Block0), std::ref(Block1), std::ref(Block2)}) {
+    for (auto &R : B.get())
+      ASSERT_FALSE(errorToBool(R->apply(Indexer)));
+    ASSERT_FALSE(errorToBool(Indexer.flush()));
+  }
+
+  BlockVerifier Verifier;
+  for (auto &ProcessThreadBlocks : Index) {
+    auto &Blocks = ProcessThreadBlocks.second;
+    for (auto &B : Blocks) {
+      for (auto *R : B.Records)
+        ASSERT_FALSE(errorToBool(R->apply(Verifier)));
+      ASSERT_FALSE(errorToBool(Verifier.verify()));
+      Verifier.reset();
+    }
+  }
+}
+
+TEST(FDRBlockVerifierTest, MissingPIDRecord) {
+  auto Block = LogBuilder()
+                   .add<BufferExtents>(20)
+                   .add<NewBufferRecord>(1)
+                   .add<WallclockRecord>(1, 2)
+                   .add<NewCPUIDRecord>(1)
+                   .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                   .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                   .consume();
+  BlockVerifier Verifier;
+  for (auto &R : Block)
+    ASSERT_FALSE(errorToBool(R->apply(Verifier)));
+  ASSERT_FALSE(errorToBool(Verifier.verify()));
+}
+
+TEST(FDRBlockVerifierTest, MissingBufferExtents) {
+  auto Block = LogBuilder()
+                   .add<NewBufferRecord>(1)
+                   .add<WallclockRecord>(1, 2)
+                   .add<NewCPUIDRecord>(1)
+                   .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                   .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                   .consume();
+  BlockVerifier Verifier;
+  for (auto &R : Block)
+    ASSERT_FALSE(errorToBool(R->apply(Verifier)));
+  ASSERT_FALSE(errorToBool(Verifier.verify()));
+}
+
+TEST(FDRBlockVerifierTest, IgnoreRecordsAfterEOB) {
+  auto Block = LogBuilder()
+                   .add<NewBufferRecord>(1)
+                   .add<WallclockRecord>(1, 2)
+                   .add<NewCPUIDRecord>(1)
+                   .add<EndBufferRecord>()
+                   .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                   .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                   .consume();
+  BlockVerifier Verifier;
+  for (auto &R : Block)
+    ASSERT_FALSE(errorToBool(R->apply(Verifier)));
+  ASSERT_FALSE(errorToBool(Verifier.verify()));
+}
+
+TEST(FDRBlockVerifierTest, MalformedV2) {
+  auto Block = LogBuilder()
+                   .add<NewBufferRecord>(1)
+                   .add<WallclockRecord>(1, 2)
+                   .add<NewCPUIDRecord>(1)
+                   .add<FunctionRecord>(RecordTypes::ENTER, 1, 1)
+                   .add<FunctionRecord>(RecordTypes::EXIT, 1, 100)
+                   .add<NewBufferRecord>(2)
+                   .consume();
+  BlockVerifier Verifier;
+
+  ASSERT_THAT(Block, SizeIs(6u));
+  EXPECT_THAT_ERROR(Block[0]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[1]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[2]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[3]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[4]->apply(Verifier), Succeeded());
+  EXPECT_THAT_ERROR(Block[5]->apply(Verifier), Failed());
+}
+
+} // namespace
+} // namespace xray
+} // namespace llvm