Index: tools/llvm-cfi-verify/CMakeLists.txt
===================================================================
--- tools/llvm-cfi-verify/CMakeLists.txt
+++ tools/llvm-cfi-verify/CMakeLists.txt
@@ -9,8 +9,11 @@
   MCParser
   Object
   Support
+  DebugInfoDWARF
   )
 
 add_llvm_tool(llvm-cfi-verify
   llvm-cfi-verify.cpp
+  GraphBuilder.cpp
+  FileAnalysis.cpp
   )
Index: tools/llvm-cfi-verify/FileAnalysis.h
===================================================================
--- /dev/null
+++ tools/llvm-cfi-verify/FileAnalysis.h
@@ -0,0 +1,196 @@
+//===- FileAnalysis.h -------------------------------------------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CFI_VERIFY_FILE_ANALYSIS_H
+#define LLVM_CFI_VERIFY_FILE_ANALYSIS_H
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <functional>
+#include <set>
+#include <string>
+#include <unordered_map>
+
+namespace llvm {
+namespace cfi_verify {
+
+extern bool IgnoreDWARF;
+
+// Disassembler and analysis tool for machine code files. Keeps track of non-
+// sequential control flows, including indirect control flow instructions.
+class FileAnalysis {
+public:
+  // A metadata struct for an instruction.
+  struct Instr {
+    uint64_t VMAddress;       // Virtual memory address of this instruction.
+    MCInst Instruction;       // Instruction.
+    uint64_t InstructionSize; // Size of this instruction.
+    bool Valid; // Is this a valid instruction? If false, Instr::Instruction is
+                // undefined.
+  };
+
+  // Construct a FileAnalysis from a file path.
+  static Expected<FileAnalysis> Create(StringRef Filename);
+
+  // Construct and take ownership of the supplied object. Do not use this
+  // constructor, prefer to use FileAnalysis::Create instead.
+  FileAnalysis(object::OwningBinary<object::Binary> Binary);
+  FileAnalysis() = delete;
+  FileAnalysis(const FileAnalysis &) = delete;
+  FileAnalysis(FileAnalysis &&Other) = default;
+
+  // Check whether the provided instruction is CFI protected in this file.
+  // Returns false if this instruction doesn't exist in this file, if it's not
+  // an indirect control flow instruction, or isn't CFI protected. Returns true
+  // otherwise.
+  bool isCFIProtected(uint64_t Address) const;
+
+  // Returns the instruction at the provided address. Returns nullptr if there
+  // is no instruction at the provided address.
+  const Instr *getInstruction(uint64_t Address) const;
+
+  // Returns the instruction at the provided adress, dying if the instruction is
+  // not found.
+  const Instr &getInstructionOrDie(uint64_t Address) const;
+
+  // Returns a pointer to the previous/next instruction in sequence,
+  // respectively. Returns nullptr if the next/prev instruction doesn't exist,
+  // or if the provided instruction doesn't exist.
+  const Instr *getPrevInstructionSequential(const Instr &InstrMeta) const;
+  const Instr *getNextInstructionSequential(const Instr &InstrMeta) const;
+
+  // Returns whether this instruction is used by CFI to trap the program.
+  bool isCFITrap(const Instr &InstrMeta) const;
+
+  // Returns whether this function can fall through to the next instruction.
+  // Undefined (and bad) instructions cannot fall through, and instruction that
+  // modify the control flow can only fall through if they are conditional
+  // branches or calls.
+  bool canFallThrough(const Instr &InstrMeta) const;
+
+  // Returns whether this instruction uses a register operand.
+  bool usesRegisterOperand(const Instr &InstrMeta) const;
+
+  // Returns the definitive next instruction. This is different from the next
+  // instruction sequentially as it will follow unconditional branches (assuming
+  // they can be resolved at compile time, i.e. not indirect). This method
+  // returns nullptr if the provided instruction does not transfer control flow
+  // to exactly one instruction that is known deterministically at compile time.
+  // Also returns nullptr if the deterministic target does not exist in this
+  // file.
+  const Instr *getDefiniteNextInstruction(const Instr &InstrMeta) const;
+
+  // Get a list of deterministic control flows that lead to the provided
+  // instruction. This list includes all static control flow cross-references as
+  // well as the previous instruction if it can fall through.
+  std::set<const Instr *>
+  getDirectControlFlowXRefs(const Instr &InstrMeta) const;
+
+  // Returns the list of indirect instructions.
+  const std::set<uint64_t> &getIndirectInstructions() const;
+
+  const MCRegisterInfo *getRegisterInfo() const;
+  const MCInstrInfo *getMCInstrInfo() const;
+  const MCInstrAnalysis *getMCInstrAnalysis() const;
+
+  DWARFContext *getDWARF();
+
+protected:
+  // Construct a blank object with the provided triple and features. Used in
+  // testing, where a sub class will dependency inject protected methods to
+  // allow analysis of raw binary, without requiring a fully valid ELF file.
+  FileAnalysis(const Triple &ObjectTriple, const SubtargetFeatures &Features);
+
+  // Add an instruction to this object.
+  void addInstruction(const Instr &Instruction);
+
+  // Disassemble and parse the provided bytes into this object. Instruction
+  // address calculation is done relative to the provided SectionAddress.
+  void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                            uint64_t SectionAddress);
+
+  // Constructs and initialises members required for disassembly.
+  Error initialiseDisassemblyMembers();
+
+  // Parses code sections from the internal object file. Saves them into the
+  // internal members. Should only be called once by Create().
+  Error parseCodeSections();
+
+private:
+  // Members that describe the input file.
+  object::OwningBinary<object::Binary> Binary;
+  const object::ObjectFile *Object = nullptr;
+  Triple ObjectTriple;
+  std::string ArchName;
+  std::string MCPU;
+  const Target *ObjectTarget = nullptr;
+  SubtargetFeatures Features;
+
+  // Members required for disassembly.
+  std::unique_ptr<const MCRegisterInfo> RegisterInfo;
+  std::unique_ptr<const MCAsmInfo> AsmInfo;
+  std::unique_ptr<MCSubtargetInfo> SubtargetInfo;
+  std::unique_ptr<const MCInstrInfo> MII;
+  MCObjectFileInfo MOFI;
+  std::unique_ptr<MCContext> Context;
+  std::unique_ptr<const MCDisassembler> Disassembler;
+  std::unique_ptr<const MCInstrAnalysis> MIA;
+  std::unique_ptr<MCInstPrinter> Printer;
+
+  // DWARF debug information.
+  std::unique_ptr<DWARFContext> DWARF;
+
+  // A mapping between the virtual memory address to the instruction metadata
+  // struct. TODO(hctim): Reimplement this as a sorted vector to avoid per-
+  // insertion allocation.
+  std::map<uint64_t, Instr> Instructions;
+
+  // Contains a mapping between a specific address, and a list of instructions
+  // that use this address as a branch target (including call instructions).
+  std::unordered_map<uint64_t, std::vector<uint64_t>> StaticBranchTargetings;
+
+  // A list of addresses of indirect control flow instructions.
+  std::set<uint64_t> IndirectInstructions;
+};
+
+class UnsupportedDisassembly : public ErrorInfo<UnsupportedDisassembly> {
+public:
+  static char ID;
+
+  void log(raw_ostream &OS) const override;
+  std::error_code convertToErrorCode() const override;
+};
+
+} // namespace cfi_verify
+} // namespace llvm
+
+#endif // LLVM_CFI_VERIFY_FILE_ANALYSIS_H
Index: tools/llvm-cfi-verify/FileAnalysis.cpp
===================================================================
--- /dev/null
+++ tools/llvm-cfi-verify/FileAnalysis.cpp
@@ -0,0 +1,434 @@
+//===- FileAnalysis.cpp -----------------------------------------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "FileAnalysis.h"
+#include "GraphBuilder.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <functional>
+
+using Instr = llvm::cfi_verify::FileAnalysis::Instr;
+
+namespace llvm {
+namespace cfi_verify {
+
+bool IgnoreDWARF;
+
+static cl::opt<bool, true> IgnoreDWARFArg(
+    "ignore-dwarf",
+    cl::desc("Ignore all DWARF data (warning: may generate false positives)."),
+    cl::location(IgnoreDWARF), cl::init(false));
+
+cl::opt<uint64_t> DWARFSearchRange(
+    "dwarf-search-range",
+    cl::desc("Address search range used to determine if instruction is valid."),
+    cl::init(0x10));
+
+Expected<FileAnalysis> FileAnalysis::Create(StringRef Filename) {
+  // Open the filename provided.
+  Expected<object::OwningBinary<object::Binary>> BinaryOrErr =
+      object::createBinary(Filename);
+  if (!BinaryOrErr)
+    return BinaryOrErr.takeError();
+
+  // Construct the object and allow it to take ownership of the binary.
+  object::OwningBinary<object::Binary> Binary = std::move(BinaryOrErr.get());
+  FileAnalysis Analysis(std::move(Binary));
+
+  Analysis.Object = dyn_cast<object::ObjectFile>(Analysis.Binary.getBinary());
+  if (!Analysis.Object)
+    return make_error<UnsupportedDisassembly>();
+
+  Analysis.ObjectTriple = Analysis.Object->makeTriple();
+  Analysis.Features = Analysis.Object->getFeatures();
+
+  // Init the rest of the object.
+  if (auto InitResponse = Analysis.initialiseDisassemblyMembers())
+    return std::move(InitResponse);
+
+  if (auto SectionParseResponse = Analysis.parseCodeSections())
+    return std::move(SectionParseResponse);
+
+  return std::move(Analysis);
+}
+
+FileAnalysis::FileAnalysis(object::OwningBinary<object::Binary> Binary)
+    : Binary(std::move(Binary)) {}
+
+FileAnalysis::FileAnalysis(const Triple &ObjectTriple,
+                           const SubtargetFeatures &Features)
+    : ObjectTriple(ObjectTriple), Features(Features) {}
+
+bool FileAnalysis::isCFIProtected(uint64_t Address) const {
+  const Instr *InstrMetaPtr = getInstruction(Address);
+  if (!InstrMetaPtr)
+    return false;
+
+  const auto &InstrDesc = MII->get(InstrMetaPtr->Instruction.getOpcode());
+
+  if (!InstrDesc.mayAffectControlFlow(InstrMetaPtr->Instruction, *RegisterInfo))
+    return false;
+
+  if (!usesRegisterOperand(*InstrMetaPtr))
+    return false;
+
+  auto Flows = GraphBuilder::buildFlowGraph(*this, Address);
+
+  if (!Flows.OrphanedNodes.empty())
+    return false;
+
+  for (const auto &BranchNode : Flows.BranchNodes) {
+    if (!BranchNode.CFIProtection)
+      return false;
+  }
+
+  return true;
+}
+
+const Instr *
+FileAnalysis::getPrevInstructionSequential(const Instr &InstrMeta) const {
+  std::map<uint64_t, Instr>::const_iterator KV =
+      Instructions.find(InstrMeta.VMAddress);
+  if (KV == Instructions.end() || KV == Instructions.begin())
+    return nullptr;
+
+  if (!(--KV)->second.Valid)
+    return nullptr;
+
+  return &KV->second;
+}
+
+const Instr *
+FileAnalysis::getNextInstructionSequential(const Instr &InstrMeta) const {
+  std::map<uint64_t, Instr>::const_iterator KV =
+      Instructions.find(InstrMeta.VMAddress);
+  if (KV == Instructions.end() || ++KV == Instructions.end())
+    return nullptr;
+
+  if (!KV->second.Valid)
+    return nullptr;
+
+  return &KV->second;
+}
+
+bool FileAnalysis::usesRegisterOperand(const Instr &InstrMeta) const {
+  for (const auto &Operand : InstrMeta.Instruction) {
+    if (Operand.isReg())
+      return true;
+  }
+  return false;
+}
+
+const Instr *FileAnalysis::getInstruction(uint64_t Address) const {
+  const auto &InstrKV = Instructions.find(Address);
+  if (InstrKV == Instructions.end())
+    return nullptr;
+
+  return &InstrKV->second;
+}
+
+const Instr &FileAnalysis::getInstructionOrDie(uint64_t Address) const {
+  const auto &InstrKV = Instructions.find(Address);
+  assert(InstrKV != Instructions.end() && "Address doesn't exist.");
+  return InstrKV->second;
+}
+
+bool FileAnalysis::isCFITrap(const Instr &InstrMeta) const {
+  return MII->getName(InstrMeta.Instruction.getOpcode()) == "TRAP";
+}
+
+bool FileAnalysis::canFallThrough(const Instr &InstrMeta) const {
+  if (!InstrMeta.Valid)
+    return false;
+
+  if (isCFITrap(InstrMeta))
+    return false;
+
+  const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
+  if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo))
+    return InstrDesc.isConditionalBranch();
+
+  return true;
+}
+
+const Instr *
+FileAnalysis::getDefiniteNextInstruction(const Instr &InstrMeta) const {
+  if (!InstrMeta.Valid)
+    return nullptr;
+
+  if (isCFITrap(InstrMeta))
+    return nullptr;
+
+  const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
+  const Instr *NextMetaPtr;
+  if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo)) {
+    if (InstrDesc.isConditionalBranch())
+      return nullptr;
+
+    uint64_t Target;
+    if (!MIA->evaluateBranch(InstrMeta.Instruction, InstrMeta.VMAddress,
+                             InstrMeta.InstructionSize, Target))
+      return nullptr;
+
+    NextMetaPtr = getInstruction(Target);
+  } else {
+    NextMetaPtr =
+        getInstruction(InstrMeta.VMAddress + InstrMeta.InstructionSize);
+  }
+
+  if (!NextMetaPtr || !NextMetaPtr->Valid)
+    return nullptr;
+
+  return NextMetaPtr;
+}
+
+std::set<const Instr *>
+FileAnalysis::getDirectControlFlowXRefs(const Instr &InstrMeta) const {
+  std::set<const Instr *> CFCrossReferences;
+  const Instr *PrevInstruction = getPrevInstructionSequential(InstrMeta);
+
+  if (PrevInstruction && canFallThrough(*PrevInstruction))
+    CFCrossReferences.insert(PrevInstruction);
+
+  const auto &TargetRefsKV = StaticBranchTargetings.find(InstrMeta.VMAddress);
+  if (TargetRefsKV == StaticBranchTargetings.end())
+    return CFCrossReferences;
+
+  for (uint64_t SourceInstrAddress : TargetRefsKV->second) {
+    const auto &SourceInstrKV = Instructions.find(SourceInstrAddress);
+    if (SourceInstrKV == Instructions.end()) {
+      errs() << "Failed to find source instruction at address "
+             << format_hex(SourceInstrAddress, 2)
+             << " for the cross-reference to instruction at address "
+             << format_hex(InstrMeta.VMAddress, 2) << ".\n";
+      continue;
+    }
+
+    CFCrossReferences.insert(&SourceInstrKV->second);
+  }
+
+  return CFCrossReferences;
+}
+
+const std::set<uint64_t> &FileAnalysis::getIndirectInstructions() const {
+  return IndirectInstructions;
+}
+
+const MCRegisterInfo *FileAnalysis::getRegisterInfo() const {
+  return RegisterInfo.get();
+}
+
+const MCInstrInfo *FileAnalysis::getMCInstrInfo() const { return MII.get(); }
+
+const MCInstrAnalysis *FileAnalysis::getMCInstrAnalysis() const {
+  return MIA.get();
+}
+
+DWARFContext *FileAnalysis::getDWARF() { return DWARF.get(); }
+
+Error FileAnalysis::initialiseDisassemblyMembers() {
+  std::string TripleName = ObjectTriple.getTriple();
+  ArchName = "";
+  MCPU = "";
+  std::string ErrorString;
+
+  ObjectTarget =
+      TargetRegistry::lookupTarget(ArchName, ObjectTriple, ErrorString);
+  if (!ObjectTarget)
+    return make_error<StringError>(Twine("Couldn't find target \"") +
+                                       ObjectTriple.getTriple() +
+                                       "\", failed with error: " + ErrorString,
+                                   inconvertibleErrorCode());
+
+  RegisterInfo.reset(ObjectTarget->createMCRegInfo(TripleName));
+  if (!RegisterInfo)
+    return make_error<StringError>("Failed to initialise RegisterInfo.",
+                                   inconvertibleErrorCode());
+
+  AsmInfo.reset(ObjectTarget->createMCAsmInfo(*RegisterInfo, TripleName));
+  if (!AsmInfo)
+    return make_error<StringError>("Failed to initialise AsmInfo.",
+                                   inconvertibleErrorCode());
+
+  SubtargetInfo.reset(ObjectTarget->createMCSubtargetInfo(
+      TripleName, MCPU, Features.getString()));
+  if (!SubtargetInfo)
+    return make_error<StringError>("Failed to initialise SubtargetInfo.",
+                                   inconvertibleErrorCode());
+
+  MII.reset(ObjectTarget->createMCInstrInfo());
+  if (!MII)
+    return make_error<StringError>("Failed to initialise MII.",
+                                   inconvertibleErrorCode());
+
+  Context.reset(new MCContext(AsmInfo.get(), RegisterInfo.get(), &MOFI));
+
+  Disassembler.reset(
+      ObjectTarget->createMCDisassembler(*SubtargetInfo, *Context));
+
+  if (!Disassembler)
+    return make_error<StringError>("No disassembler available for target",
+                                   inconvertibleErrorCode());
+
+  MIA.reset(ObjectTarget->createMCInstrAnalysis(MII.get()));
+
+  Printer.reset(ObjectTarget->createMCInstPrinter(
+      ObjectTriple, AsmInfo->getAssemblerDialect(), *AsmInfo, *MII,
+      *RegisterInfo));
+
+  return Error::success();
+}
+
+Error FileAnalysis::parseCodeSections() {
+  if (!IgnoreDWARF) {
+    DWARF.reset(DWARFContext::create(*Object).release());
+    if (!DWARF)
+      return make_error<StringError>("Could not create DWARF information.",
+                                     inconvertibleErrorCode());
+
+    bool LineInfoValid = false;
+
+    for (auto &Unit : DWARF->compile_units()) {
+      const auto &LineTable = DWARF->getLineTableForUnit(Unit.get());
+      if (LineTable && !LineTable->Rows.empty()) {
+        LineInfoValid = true;
+        break;
+      }
+    }
+
+    if (!LineInfoValid) {
+      for (auto &Range : DWARF->type_unit_sections()) {
+        for (auto &Unit : Range) {
+          const auto &LineTable = DWARF->getLineTableForUnit(Unit.get());
+          if (LineTable && !LineTable->Rows.empty()) {
+            LineInfoValid = true;
+            break;
+          }
+        }
+      }
+    }
+
+    if (!LineInfoValid)
+      return make_error<StringError>(
+          "DWARF line information missing. Did you compile with '-g'?",
+          inconvertibleErrorCode());
+  }
+
+  for (const object::SectionRef &Section : Object->sections()) {
+    // Ensure only executable sections get analysed.
+    if (!(object::ELFSectionRef(Section).getFlags() & ELF::SHF_EXECINSTR))
+      continue;
+
+    StringRef SectionContents;
+    if (Section.getContents(SectionContents))
+      return make_error<StringError>("Failed to retrieve section contents",
+                                     inconvertibleErrorCode());
+
+    ArrayRef<uint8_t> SectionBytes((const uint8_t *)SectionContents.data(),
+                                   Section.getSize());
+    parseSectionContents(SectionBytes, Section.getAddress());
+  }
+  return Error::success();
+}
+
+void FileAnalysis::parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                                        uint64_t SectionAddress) {
+  MCInst Instruction;
+  Instr InstrMeta;
+  uint64_t InstructionSize;
+
+  for (uint64_t Byte = 0; Byte < SectionBytes.size();) {
+    bool ValidInstruction =
+        Disassembler->getInstruction(Instruction, InstructionSize,
+                                     SectionBytes.drop_front(Byte), 0, nulls(),
+                                     outs()) == MCDisassembler::Success;
+
+    Byte += InstructionSize;
+
+    uint64_t VMAddress = SectionAddress + Byte - InstructionSize;
+    InstrMeta.Instruction = Instruction;
+    InstrMeta.VMAddress = VMAddress;
+    InstrMeta.InstructionSize = InstructionSize;
+    InstrMeta.Valid = ValidInstruction;
+
+    // Check if this instruction exists in the range of the DWARF metadata.
+    if (DWARF &&
+        DWARF->getLineInfoForAddressRange(InstrMeta.VMAddress, DWARFSearchRange)
+            .empty())
+      continue;
+
+    addInstruction(InstrMeta);
+
+    if (!ValidInstruction)
+      continue;
+
+    // Skip additional parsing for instructions that do not affect the control
+    // flow.
+    const auto &InstrDesc = MII->get(Instruction.getOpcode());
+    if (!InstrDesc.mayAffectControlFlow(Instruction, *RegisterInfo))
+      continue;
+
+    uint64_t Target;
+    if (MIA->evaluateBranch(Instruction, VMAddress, InstructionSize, Target)) {
+      // If the target can be evaluated, it's not indirect.
+      StaticBranchTargetings[Target].push_back(VMAddress);
+      continue;
+    }
+
+    if (!usesRegisterOperand(InstrMeta))
+      continue;
+
+    IndirectInstructions.insert(VMAddress);
+  }
+}
+
+void FileAnalysis::addInstruction(const Instr &Instruction) {
+  const auto &KV =
+      Instructions.insert(std::make_pair(Instruction.VMAddress, Instruction));
+  assert(
+      KV.second &&
+      "Failed to add instruction, instruction at this address already exists.");
+}
+
+char UnsupportedDisassembly::ID;
+void UnsupportedDisassembly::log(raw_ostream &OS) const {
+  OS << "Dissassembling of non-objects not currently supported.\n";
+}
+
+std::error_code UnsupportedDisassembly::convertToErrorCode() const {
+  return std::error_code();
+}
+
+} // namespace cfi_verify
+} // namespace llvm
Index: tools/llvm-cfi-verify/GraphBuilder.h
===================================================================
--- /dev/null
+++ tools/llvm-cfi-verify/GraphBuilder.h
@@ -0,0 +1,123 @@
+//===- GraphBuilder.h -------------------------------------------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CFI_VERIFY_GRAPH_BUILDER_H
+#define LLVM_CFI_VERIFY_GRAPH_BUILDER_H
+
+#include "FileAnalysis.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <functional>
+#include <set>
+#include <string>
+#include <unordered_map>
+
+using Instr = llvm::cfi_verify::FileAnalysis::Instr;
+
+namespace llvm {
+namespace cfi_verify {
+
+extern uint64_t SearchLengthForUndef;
+extern uint64_t SearchLengthForConditionalBranch;
+
+struct ControlFlowNode {
+  void print(unsigned depth, raw_ostream &os) const;
+  std::vector<uint64_t> flatten() const;
+
+  ControlFlowNode *Next;
+  uint64_t InstructionAddress;
+  uint64_t FlowLength;
+};
+
+struct ConditionalBranchNode {
+  void print(raw_ostream &os) const;
+  ControlFlowNode *Target;
+  ControlFlowNode *Fallthrough;
+  uint64_t InstructionAddress;
+  // Does this conditional branch implement CFI successfully?
+  bool CFIProtection;
+};
+
+struct GraphResult {
+  ~GraphResult();
+
+  uint64_t BaseInstructionAddress;
+  std::vector<ConditionalBranchNode> BranchNodes;
+  std::vector<ControlFlowNode *> OrphanedNodes;
+};
+
+class GraphBuilder {
+public:
+  // Build the control flow graph for a provided control flow node. This method
+  // will enumerate all branch nodes that can lead to this node, and provide
+  // them, fully evaulated, in GraphResult::BranchNodes. It will also provide
+  // any orphaned (i.e. did not make it to a branch node) flows to the provided
+  // node in GraphResult::OrphanedNodes.
+  static GraphResult buildFlowGraph(const FileAnalysis &Analysis,
+                                    uint64_t Address);
+
+private:
+  // Implementation function that actually builds the flow graph. Retrieves a
+  // list of cross references to instruction referenced in `Node`. If any of
+  // these XRefs are conditional branches, it will build the other potential
+  // path (fallthrough or target) using `buildFlowsToUndefined`. Otherwise,
+  // this function will recursively call itself where `Node` in the recursive
+  // call is now the XRef. If any XRef results in an error, the XRef in question
+  // is added to `OrphanedNodes`. An error is defined as any of the following:
+  //   - The maximum search length `SearchLengthForConditionalBranch` has been
+  //     reached.
+  //   - The XRef cannot be calculated (e.g. it doesn't exist in the Analysis
+  //     object).
+  //   - The graph is cyclic.
+  static void
+  buildFlowGraphImpl(const FileAnalysis &Analysis, ControlFlowNode *Node,
+                     std::vector<ConditionalBranchNode> *BranchNodes,
+                     std::vector<ControlFlowNode *> *OrphanedNodes);
+
+  // Utilised by buildFlowGraphImpl to build the tree out from the provided
+  // conditional branch node to an undefined instruction. The provided
+  // conditional branch node must have exactly one of its subtrees set, and will
+  // update the node's CFIProtection field if a deterministic flow can be found
+  // to an undefined instruction.
+  static void buildFlowsToUndefined(const FileAnalysis &Analysis,
+                                    ConditionalBranchNode &BranchNode);
+
+  // Creates a control flow node with the information from the parent, and links
+  // it to the provided child.
+  static ControlFlowNode *createParentNode(const Instr &ParentMeta,
+                                           ControlFlowNode *ChildNode);
+};
+
+} // end namespace cfi_verify
+} // end namespace llvm
+
+#endif // LLVM_CFI_VERIFY_GRAPH_BUILDER_H
Index: tools/llvm-cfi-verify/GraphBuilder.cpp
===================================================================
--- /dev/null
+++ tools/llvm-cfi-verify/GraphBuilder.cpp
@@ -0,0 +1,368 @@
+//===- GraphBuilder.cpp -----------------------------------------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "GraphBuilder.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <functional>
+
+using Instr = llvm::cfi_verify::FileAnalysis::Instr;
+
+namespace llvm {
+namespace cfi_verify {
+
+uint64_t SearchLengthForUndef;
+uint64_t SearchLengthForConditionalBranch;
+
+static cl::opt<uint64_t, true> SearchLengthForUndefArg(
+    "search-length-undef",
+    cl::desc("Specify the maximum amount of instructions "
+             "to inspect when searching for an undefined "
+             "instruction from a conditional branch."),
+    cl::location(SearchLengthForUndef), cl::init(2));
+
+static cl::opt<uint64_t, true> SearchLengthForConditionalBranchArg(
+    "search-length-cb",
+    cl::desc("Specify the maximum amount of instructions "
+             "to inspect when searching for a conditional "
+             "branch from an indirect control flow."),
+    cl::location(SearchLengthForConditionalBranch), cl::init(20));
+
+void ControlFlowNode::print(unsigned depth, raw_ostream &os) const {
+  for (unsigned i = 0; i < depth; ++i)
+    os << "  ";
+
+  os << "[" << FlowLength << "] " << format_hex(InstructionAddress, 2) << "\n";
+  if (Next)
+    Next->print(depth + 1, os);
+}
+
+void ConditionalBranchNode::print(raw_ostream &os) const {
+  os << format_hex(InstructionAddress, 2) << "\n";
+  os << " Target:\n";
+  if (Target)
+    Target->print(1, os);
+  else
+    os << "  ???\n";
+
+  os << " Fallthrough:\n";
+  if (Fallthrough)
+    Fallthrough->print(1, os);
+  else
+    os << "  ???\n";
+}
+
+std::vector<uint64_t> ControlFlowNode::flatten() const {
+  std::vector<uint64_t> Addresses;
+  const ControlFlowNode *Node = this;
+  while (Node != nullptr) {
+    Addresses.push_back(Node->InstructionAddress);
+    Node = Node->Next;
+  }
+  return Addresses;
+}
+
+GraphResult::~GraphResult() {
+  std::set<ControlFlowNode *> CFNs;
+  for (const auto &BranchNode : BranchNodes) {
+    for (ControlFlowNode *FlowNode = BranchNode.Target; FlowNode;
+         FlowNode = FlowNode->Next)
+      CFNs.insert(FlowNode);
+
+    for (ControlFlowNode *FlowNode = BranchNode.Fallthrough; FlowNode;
+         FlowNode = FlowNode->Next)
+      CFNs.insert(FlowNode);
+  }
+
+  for (auto &FlowNode : OrphanedNodes) {
+    while (FlowNode) {
+      CFNs.insert(FlowNode);
+      FlowNode = FlowNode->Next;
+    }
+  }
+
+  for (const auto &Node : CFNs)
+    delete Node;
+}
+
+GraphResult GraphBuilder::buildFlowGraph(const FileAnalysis &Analysis,
+                                         uint64_t Address) {
+  GraphResult Result;
+  Result.BaseInstructionAddress = Address;
+
+  const auto &IndirectInstructions = Analysis.getIndirectInstructions();
+
+  if (IndirectInstructions.find(Address) == IndirectInstructions.end())
+    return Result;
+
+  ControlFlowNode *Node = new ControlFlowNode();
+  Node->Next = nullptr;
+  Node->InstructionAddress = Address;
+  Node->FlowLength = 0;
+
+  buildFlowGraphImpl(Analysis, Node, &Result.BranchNodes,
+                     &Result.OrphanedNodes);
+  return Result;
+}
+
+void GraphBuilder::buildFlowsToUndefined(const FileAnalysis &Analysis,
+                                         ConditionalBranchNode &BranchNode) {
+  assert(SearchLengthForUndef > 0 &&
+         "Search length for undefined flow must be greater than zero.");
+
+  // Resolve the metadata for the provided node.
+  const auto &BranchInstrMetaPtr =
+      Analysis.getInstruction(BranchNode.InstructionAddress);
+  if (!BranchInstrMetaPtr) {
+    errs() << "Failed to build flows from instruction with address"
+           << format_hex(BranchNode.InstructionAddress, 2) << ".\n";
+    return;
+  }
+  const auto &BranchInstrMeta = *BranchInstrMetaPtr;
+
+  // Start setting up the next node in the chain.
+  const Instr *NextMetaPtr;
+  ControlFlowNode *NextNode = new ControlFlowNode();
+  NextNode->Next = nullptr;
+  NextNode->FlowLength = 1;
+
+  // Find out the next instruction in the chain and add it to the new node.
+  if (BranchNode.Target && !BranchNode.Fallthrough) {
+    // We know the target of the branch, find the fallthrough.
+    NextMetaPtr = Analysis.getNextInstructionSequential(BranchInstrMeta);
+    if (!NextMetaPtr) {
+      errs() << "Failed to get next instruction from "
+             << format_hex(BranchNode.InstructionAddress, 2) << ".\n";
+      delete NextNode;
+      return;
+    }
+
+    NextNode->InstructionAddress = NextMetaPtr->VMAddress;
+    BranchNode.Fallthrough = NextNode; // Add the new node to the branch head.
+  } else if (BranchNode.Fallthrough && !BranchNode.Target) {
+    // We already know the fallthrough, evaluate the target.
+    uint64_t Target;
+    if (!Analysis.getMCInstrAnalysis()->evaluateBranch(
+            BranchInstrMeta.Instruction, BranchInstrMeta.VMAddress,
+            BranchInstrMeta.InstructionSize, Target)) {
+      errs() << "Failed to get branch target for conditional branch at address "
+             << format_hex(BranchInstrMeta.VMAddress, 2) << ".\n";
+      delete NextNode;
+      return;
+    }
+
+    // Resolve the meta pointer for the target of this branch.
+    NextMetaPtr = Analysis.getInstruction(Target);
+    if (!NextMetaPtr) {
+      errs() << "Failed to find instruction at address "
+             << format_hex(Target, 2) << ".\n";
+      delete NextNode;
+      return;
+    }
+
+    NextNode->InstructionAddress = Target;
+    BranchNode.Target = NextNode; // Add the new node to the branch head.
+  } else {
+    errs() << "ControlBranchNode supplied to buildFlowsToUndefined should "
+              "provide Target xor Fallthrough.\n";
+    delete NextNode;
+    return;
+  }
+
+  ControlFlowNode *CurrentNode = NextNode;
+  const Instr *CurrentMetaPtr = NextMetaPtr;
+
+  // Now the branch head has been set properly, complete the rest of the chain.
+  for (uint64_t i = 1; i < SearchLengthForUndef; ++i) {
+    // Check to see whether the chain should die.
+    if (Analysis.isCFITrap(*CurrentMetaPtr)) {
+      BranchNode.CFIProtection = true;
+      return;
+    }
+
+    // Find the metadata of the next instruction.
+    NextMetaPtr = Analysis.getDefiniteNextInstruction(*CurrentMetaPtr);
+    if (!NextMetaPtr)
+      return;
+
+    // Setup the next node.
+    NextNode = new ControlFlowNode();
+    NextNode->Next = nullptr;
+    NextNode->InstructionAddress = NextMetaPtr->VMAddress;
+    NextNode->FlowLength = CurrentNode->FlowLength + 1;
+    CurrentNode->Next = NextNode;
+
+    // Move the 'current' pointers to the new tail of the chain.
+    CurrentMetaPtr = NextMetaPtr;
+    CurrentNode = NextNode;
+  }
+
+  // Final check of the last thing we added to the chain.
+  if (Analysis.isCFITrap(*CurrentMetaPtr))
+    BranchNode.CFIProtection = true;
+}
+
+ControlFlowNode *GraphBuilder::createParentNode(const Instr &ParentMeta,
+                                                ControlFlowNode *ChildNode) {
+  assert(ChildNode && "Null pointer provided to createParentNode");
+  ControlFlowNode *ParentNode = new ControlFlowNode();
+  ParentNode->Next = ChildNode;
+  ParentNode->InstructionAddress = ParentMeta.VMAddress;
+  ParentNode->FlowLength = ChildNode->FlowLength + 1;
+  return ParentNode;
+}
+
+void GraphBuilder::buildFlowGraphImpl(
+    const FileAnalysis &Analysis, ControlFlowNode *ChildNode,
+    std::vector<ConditionalBranchNode> *BranchNodes,
+    std::vector<ControlFlowNode *> *OrphanedNodes) {
+  assert(ChildNode && BranchNodes && OrphanedNodes &&
+         "Null pointer provided to buildFlowGraphImpl.");
+
+  // If we've exceeded the flow length, terminate.
+  if (ChildNode->FlowLength >= SearchLengthForConditionalBranch) {
+    OrphanedNodes->push_back(ChildNode);
+    return;
+  }
+
+  // Get the metadata for the node instruction.
+  const auto &InstrMetaPtr =
+      Analysis.getInstruction(ChildNode->InstructionAddress);
+  if (!InstrMetaPtr) {
+    errs() << "Failed to build flow graph for instruction at address "
+           << format_hex(ChildNode->InstructionAddress, 2) << ".\n";
+    OrphanedNodes->push_back(ChildNode);
+    return;
+  }
+  const auto &ChildMeta = *InstrMetaPtr;
+
+  std::set<const Instr *> CFCrossRefs =
+      Analysis.getDirectControlFlowXRefs(ChildMeta);
+
+  bool HasValidCrossRef = false;
+
+  for (const auto *ParentMetaPtr : CFCrossRefs) {
+    assert(ParentMetaPtr && "CFCrossRefs returned nullptr.");
+    const auto &ParentMeta = *ParentMetaPtr;
+    const auto &ParentDesc =
+        Analysis.getMCInstrInfo()->get(ParentMeta.Instruction.getOpcode());
+
+    if (!ParentDesc.mayAffectControlFlow(ParentMeta.Instruction,
+                                         *Analysis.getRegisterInfo())) {
+      // If this cross reference doesn't affect CF, continue the graph.
+      buildFlowGraphImpl(Analysis, createParentNode(ParentMeta, ChildNode),
+                         BranchNodes, OrphanedNodes);
+      HasValidCrossRef = true;
+      continue;
+    }
+
+    // Call instructions are not valid in the upwards traversal.
+    if (ParentDesc.isCall()) {
+      OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+      continue;
+    }
+
+    // Evaluate the branch target to ascertain whether this XRef is the result
+    // of a fallthrough or the target of a branch.
+    uint64_t BranchTarget;
+    if (!Analysis.getMCInstrAnalysis()->evaluateBranch(
+            ParentMeta.Instruction, ParentMeta.VMAddress,
+            ParentMeta.InstructionSize, BranchTarget)) {
+      errs() << "Failed to evaluate branch target for instruction at address "
+             << format_hex(ParentMeta.VMAddress, 2) << ".\n";
+      OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+      continue;
+    }
+
+    // Allow unconditional branches to be part of the upwards traversal.
+    if (ParentDesc.isUnconditionalBranch()) {
+      // Ensures that the unconditional branch is actually an XRef to the child.
+      if (BranchTarget != ChildMeta.VMAddress) {
+        errs() << "Control flow to " << format_hex(ChildMeta.VMAddress, 2)
+               << ", but target resolution of "
+               << format_hex(ParentMeta.VMAddress, 2)
+               << " is not this address?\n";
+        OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+        continue;
+      }
+
+      // Stop if this graph is cyclic.
+      const auto &FlattenedList = ChildNode->flatten();
+      if (std::find_if(FlattenedList.begin(), FlattenedList.end(),
+                       [&ParentMeta](const uint64_t &Address) {
+                         return Address == ParentMeta.VMAddress;
+                       }) != FlattenedList.end()) {
+        OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+        continue;
+      }
+
+      buildFlowGraphImpl(Analysis, createParentNode(ParentMeta, ChildNode),
+                         BranchNodes, OrphanedNodes);
+      HasValidCrossRef = true;
+      continue;
+    }
+
+    // Ensure that any unknown CFs are caught.
+    if (!ParentDesc.isConditionalBranch()) {
+      errs() << "Unknown control flow encountered when building graph at "
+             << format_hex(ParentMeta.VMAddress, 2) << ".\n";
+      const auto& ParentNode = createParentNode(ParentMeta, ChildNode);
+      OrphanedNodes->push_back(ParentNode);
+      ParentNode->print(1, errs());
+      continue;
+    }
+
+    // Only direct conditional branches should be present at this point. Setup
+    // a conditional branch node and build flows to the ud2.
+    ConditionalBranchNode BranchNode;
+    BranchNode.InstructionAddress = ParentMeta.VMAddress;
+    BranchNode.Target = nullptr;
+    BranchNode.Fallthrough = nullptr;
+    BranchNode.CFIProtection = false;
+
+    if (BranchTarget == ChildMeta.VMAddress)
+      BranchNode.Target = ChildNode;
+    else
+      BranchNode.Fallthrough = ChildNode;
+
+    HasValidCrossRef = true;
+    buildFlowsToUndefined(Analysis, BranchNode);
+    BranchNodes->push_back(BranchNode);
+  }
+
+  if (!HasValidCrossRef)
+    OrphanedNodes->push_back(ChildNode);
+}
+
+} // namespace cfi_verify
+} // namespace llvm
Index: tools/llvm-cfi-verify/LLVMBuild.txt
===================================================================
--- tools/llvm-cfi-verify/LLVMBuild.txt
+++ tools/llvm-cfi-verify/LLVMBuild.txt
@@ -19,4 +19,4 @@
 type = Tool
 name = llvm-cfi-verify
 parent = Tools
-required_libraries = MC MCDisassembler MCParser Support all-targets
+required_libraries = MC MCDisassembler MCParser Support all-targets DebugInfoDWARF
Index: tools/llvm-cfi-verify/llvm-cfi-verify.cpp
===================================================================
--- tools/llvm-cfi-verify/llvm-cfi-verify.cpp
+++ tools/llvm-cfi-verify/llvm-cfi-verify.cpp
@@ -17,66 +17,65 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/MC/MCAsmInfo.h"
-#include "llvm/MC/MCContext.h"
-#include "llvm/MC/MCDisassembler/MCDisassembler.h"
-#include "llvm/MC/MCInst.h"
-#include "llvm/MC/MCInstPrinter.h"
-#include "llvm/MC/MCInstrAnalysis.h"
-#include "llvm/MC/MCInstrDesc.h"
-#include "llvm/MC/MCInstrInfo.h"
-#include "llvm/MC/MCObjectFileInfo.h"
-#include "llvm/MC/MCRegisterInfo.h"
-#include "llvm/MC/MCSubtargetInfo.h"
-#include "llvm/Object/Binary.h"
-#include "llvm/Object/COFF.h"
-#include "llvm/Object/ObjectFile.h"
-#include "llvm/Support/Casting.h"
+#include "FileAnalysis.h"
+
+#include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/CommandLine.h"
-#include "llvm/Support/MemoryBuffer.h"
-#include "llvm/Support/TargetRegistry.h"
-#include "llvm/Support/TargetSelect.h"
-#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FormatVariadic.h"
 
-#include <cassert>
 #include <cstdlib>
 
 using namespace llvm;
 using namespace llvm::object;
+using namespace llvm::cfi_verify;
 
-cl::opt<bool> ArgDumpSymbols("sym", cl::desc("Dump the symbol table."));
 cl::opt<std::string> InputFilename(cl::Positional, cl::desc("<input file>"),
                                    cl::Required);
 
-static void printSymbols(const ObjectFile *Object) {
-  for (const SymbolRef &Symbol : Object->symbols()) {
-    outs() << "Symbol [" << format_hex_no_prefix(Symbol.getValue(), 2)
-           << "] = ";
-
-    auto SymbolName = Symbol.getName();
-    if (SymbolName)
-      outs() << *SymbolName;
-    else
-      outs() << "UNKNOWN";
-
-    if (Symbol.getFlags() & SymbolRef::SF_Hidden)
-      outs() << " .hidden";
-
-    outs() << " (Section = ";
-
-    auto SymbolSection = Symbol.getSection();
-    if (SymbolSection) {
-      StringRef SymbolSectionName;
-      if ((*SymbolSection)->getName(SymbolSectionName))
-        outs() << "UNKNOWN)";
-      else
-        outs() << SymbolSectionName << ")";
+ExitOnError ExitOnErr;
+
+void printIndirectCFInstructions(FileAnalysis &Analysis) {
+  uint64_t ProtectedCount = 0;
+  uint64_t UnprotectedCount = 0;
+  DWARFContext *DWARF = Analysis.getDWARF();
+
+  for (uint64_t Address : Analysis.getIndirectInstructions()) {
+    const auto &InstrMeta = Analysis.getInstructionOrDie(Address);
+
+    if (Analysis.isCFIProtected(Address)) {
+      outs() << "P ";
+      ProtectedCount++;
     } else {
-      outs() << "N/A)";
+      outs() << "U ";
+      UnprotectedCount++;
     }
 
+    outs() << format_hex(Address, 2) << " | "
+           << Analysis.getMCInstrInfo()->getName(
+                  InstrMeta.Instruction.getOpcode())
+           << " ";
     outs() << "\n";
+
+    if (DWARF) {
+      for (const auto &LineKV :
+           DWARF->getLineInfoForAddressRange(Address, 0x10)) {
+        outs() << "  " << format_hex(LineKV.first, 2) << " = "
+               << LineKV.second.FileName << ":" << LineKV.second.Line << ":"
+               << LineKV.second.Column << " ("
+               << LineKV.second.FunctionName << ")\n";
+      }
+    }
   }
+
+  if (ProtectedCount || UnprotectedCount)
+    outs() << formatv(
+        "Unprotected: {0} ({1:P}), Protected: {2} ({3:P})\n", UnprotectedCount,
+        (((double)UnprotectedCount) / (UnprotectedCount + ProtectedCount)),
+        ProtectedCount,
+        (((double)ProtectedCount) / (UnprotectedCount + ProtectedCount)));
+  else
+    outs() << "No indirect CF instructions found.\n";
 }
 
 int main(int argc, char **argv) {
@@ -87,155 +86,8 @@
   InitializeAllAsmParsers();
   InitializeAllDisassemblers();
 
-  Expected<OwningBinary<Binary>> BinaryOrErr = createBinary(InputFilename);
-  if (!BinaryOrErr) {
-    errs() << "Failed to open file.\n";
-    return EXIT_FAILURE;
-  }
-
-  Binary &Binary = *BinaryOrErr.get().getBinary();
-  ObjectFile *Object = dyn_cast<ObjectFile>(&Binary);
-  if (!Object) {
-    errs() << "Disassembling of non-objects not currently supported.\n";
-    return EXIT_FAILURE;
-  }
-
-  Triple TheTriple = Object->makeTriple();
-  std::string TripleName = TheTriple.getTriple();
-  std::string ArchName = "";
-  std::string ErrorString;
-
-  const Target *TheTarget =
-      TargetRegistry::lookupTarget(ArchName, TheTriple, ErrorString);
-
-  if (!TheTarget) {
-    errs() << "Couldn't find target \"" << TheTriple.getTriple()
-           << "\", failed with error: " << ErrorString << ".\n";
-    return EXIT_FAILURE;
-  }
-
-  SubtargetFeatures Features = Object->getFeatures();
-
-  std::unique_ptr<const MCRegisterInfo> RegisterInfo(
-      TheTarget->createMCRegInfo(TripleName));
-  if (!RegisterInfo) {
-    errs() << "Failed to initialise RegisterInfo.\n";
-    return EXIT_FAILURE;
-  }
-
-  std::unique_ptr<const MCAsmInfo> AsmInfo(
-      TheTarget->createMCAsmInfo(*RegisterInfo, TripleName));
-  if (!AsmInfo) {
-    errs() << "Failed to initialise AsmInfo.\n";
-    return EXIT_FAILURE;
-  }
-
-  std::string MCPU = "";
-  std::unique_ptr<MCSubtargetInfo> SubtargetInfo(
-      TheTarget->createMCSubtargetInfo(TripleName, MCPU, Features.getString()));
-  if (!SubtargetInfo) {
-    errs() << "Failed to initialise SubtargetInfo.\n";
-    return EXIT_FAILURE;
-  }
-
-  std::unique_ptr<const MCInstrInfo> MII(TheTarget->createMCInstrInfo());
-  if (!MII) {
-    errs() << "Failed to initialise MII.\n";
-    return EXIT_FAILURE;
-  }
-
-  MCObjectFileInfo MOFI;
-  MCContext Context(AsmInfo.get(), RegisterInfo.get(), &MOFI);
-
-  std::unique_ptr<const MCDisassembler> Disassembler(
-      TheTarget->createMCDisassembler(*SubtargetInfo, Context));
-
-  if (!Disassembler) {
-    errs() << "No disassembler available for target.";
-    return EXIT_FAILURE;
-  }
-
-  std::unique_ptr<const MCInstrAnalysis> MIA(
-      TheTarget->createMCInstrAnalysis(MII.get()));
-
-  std::unique_ptr<MCInstPrinter> Printer(
-      TheTarget->createMCInstPrinter(TheTriple, AsmInfo->getAssemblerDialect(),
-                                     *AsmInfo, *MII, *RegisterInfo));
-
-  if (ArgDumpSymbols)
-    printSymbols(Object);
-
-  for (const SectionRef &Section : Object->sections()) {
-    outs() << "Section [" << format_hex_no_prefix(Section.getAddress(), 2)
-           << "] = ";
-    StringRef SectionName;
-
-    if (Section.getName(SectionName))
-      outs() << "UNKNOWN.\n";
-    else
-      outs() << SectionName << "\n";
-
-    StringRef SectionContents;
-    if (Section.getContents(SectionContents)) {
-      errs() << "Failed to retrieve section contents.\n";
-      return EXIT_FAILURE;
-    }
-
-    MCInst Instruction;
-    uint64_t InstructionSize;
-
-    ArrayRef<uint8_t> SectionBytes((const uint8_t *)SectionContents.data(),
-                                   Section.getSize());
-
-    for (uint64_t Byte = 0; Byte < Section.getSize();) {
-      bool BadInstruction = false;
-
-      // Disassemble the instruction.
-      if (Disassembler->getInstruction(
-              Instruction, InstructionSize, SectionBytes.drop_front(Byte), 0,
-              nulls(), outs()) != MCDisassembler::Success) {
-        BadInstruction = true;
-      }
-
-      Byte += InstructionSize;
-
-      if (BadInstruction)
-        continue;
-
-      // Skip instructions that do not affect the control flow.
-      const auto &InstrDesc = MII->get(Instruction.getOpcode());
-      if (!InstrDesc.mayAffectControlFlow(Instruction, *RegisterInfo))
-        continue;
-
-      // Skip instructions that do not operate on register operands.
-      bool UsesRegisterOperand = false;
-      for (const auto &Operand : Instruction) {
-        if (Operand.isReg())
-          UsesRegisterOperand = true;
-      }
-
-      if (!UsesRegisterOperand)
-        continue;
-
-      // Print the instruction address.
-      outs() << "    "
-             << format_hex(Section.getAddress() + Byte - InstructionSize, 2)
-             << ": ";
-
-      // Print the instruction bytes.
-      for (uint64_t i = 0; i < InstructionSize; ++i) {
-        outs() << format_hex_no_prefix(SectionBytes[Byte - InstructionSize + i],
-                                       2)
-               << " ";
-      }
-
-      // Print the instruction.
-      outs() << " | " << MII->getName(Instruction.getOpcode()) << " ";
-      Instruction.dump_pretty(outs(), Printer.get());
-
-      outs() << "\n";
-    }
-  }
+  FileAnalysis Analysis = ExitOnErr(FileAnalysis::Create(InputFilename));
+  printIndirectCFInstructions(Analysis);
 
   return EXIT_SUCCESS;
 }
Index: tools/llvm-cfi-verify/unittests/CMakeLists.txt
===================================================================
--- tools/llvm-cfi-verify/unittests/CMakeLists.txt
+++ tools/llvm-cfi-verify/unittests/CMakeLists.txt
@@ -9,8 +9,11 @@
   MCParser
   Object
   Support
+  DebugInfoDWARF
   )
 
-add_llvm_tool(llvm-cfi-verify
-  llvm-cfi-verify.cpp
-  )
+add_llvm_unittest(CFIVerifyTests
+  FileAnalysis.cpp
+  GraphBuilder.cpp
+  ../GraphBuilder.cpp
+  ../FileAnalysis.cpp)
Index: tools/llvm-cfi-verify/unittests/FileAnalysis.cpp
===================================================================
--- /dev/null
+++ tools/llvm-cfi-verify/unittests/FileAnalysis.cpp
@@ -0,0 +1,631 @@
+//===- llvm/tools/llvm-cfi-verify/unittests/FileAnalysis.cpp --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../FileAnalysis.h"
+#include "../GraphBuilder.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <cstdlib>
+
+using Instr = ::llvm::cfi_verify::FileAnalysis::Instr;
+using ::testing::Eq;
+using ::testing::Field;
+
+namespace llvm {
+namespace cfi_verify {
+namespace {
+class ELFx86TestFileAnalysis : public FileAnalysis {
+public:
+  ELFx86TestFileAnalysis()
+      : FileAnalysis(Triple("x86_64--"), SubtargetFeatures()) {}
+
+  // Expose this method publicly for testing.
+  void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                            uint64_t SectionAddress) {
+    FileAnalysis::parseSectionContents(SectionBytes, SectionAddress);
+  }
+
+  Error initialiseDisassemblyMembers() {
+    return FileAnalysis::initialiseDisassemblyMembers();
+  }
+};
+
+class BasicFileAnalysisTest : public ::testing::Test {
+protected:
+  virtual void SetUp() {
+    if (Analysis.initialiseDisassemblyMembers()) {
+      FAIL() << "Failed to initialise FileAnalysis.";
+    }
+  }
+
+  ELFx86TestFileAnalysis Analysis;
+};
+
+TEST_F(BasicFileAnalysisTest, BasicDisassemblyTraversalTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                   // 0: nop
+          0xb0, 0x00,             // 1: mov $0x0, %al
+          0x48, 0x89, 0xe5,       // 3: mov %rsp, %rbp
+          0x48, 0x83, 0xec, 0x18, // 6: sub $0x18, %rsp
+          0x48, 0xbe, 0xc4, 0x07, 0x40,
+          0x00, 0x00, 0x00, 0x00, 0x00, // 10: movabs $0x4007c4, %rsi
+          0x2f,                         // 20: (bad)
+          0x41, 0x0e,                   // 21: rex.B (bad)
+          0x62, 0x72, 0x65, 0x61, 0x6b, // 23: (bad) {%k1}
+      },
+      0xDEADBEEF);
+
+  EXPECT_EQ(nullptr, Analysis.getInstruction(0x0));
+  EXPECT_EQ(nullptr, Analysis.getInstruction(0x1000));
+
+  // 0xDEADBEEF: nop
+  const auto *InstrMeta = Analysis.getInstruction(0xDEADBEEF);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF, InstrMeta->VMAddress);
+  EXPECT_EQ(1u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  const auto *NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta));
+  const auto *PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 1: mov $0x0, %al
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 1);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 1, InstrMeta->VMAddress);
+  EXPECT_EQ(2u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 3: mov %rsp, %rbp
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 3);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 3, InstrMeta->VMAddress);
+  EXPECT_EQ(3u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 6: sub $0x18, %rsp
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 6);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 6, InstrMeta->VMAddress);
+  EXPECT_EQ(4u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 10: movabs $0x4007c4, %rsi
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 10);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 10, InstrMeta->VMAddress);
+  EXPECT_EQ(10u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 20: (bad)
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 20);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 20, InstrMeta->VMAddress);
+  EXPECT_EQ(1u, InstrMeta->InstructionSize);
+  EXPECT_FALSE(InstrMeta->Valid);
+
+  EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+
+  // 0xDEADBEEF + 21: rex.B (bad)
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 21);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 21, InstrMeta->VMAddress);
+  EXPECT_EQ(2u, InstrMeta->InstructionSize);
+  EXPECT_FALSE(InstrMeta->Valid);
+
+  EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta));
+
+  // 0xDEADBEEF + 6: (bad) {%k1}
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 23);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 23, InstrMeta->VMAddress);
+  EXPECT_EQ(5u, InstrMeta->InstructionSize);
+  EXPECT_FALSE(InstrMeta->Valid);
+
+  EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta));
+}
+
+TEST_F(BasicFileAnalysisTest, PrevAndNextFromBadInst) {
+  Analysis.parseSectionContents(
+      {
+          0x90, // 0: nop
+          0x2f, // 1: (bad)
+          0x90  // 2: nop
+      },
+      0xDEADBEEF);
+  const auto &BadInstrMeta = Analysis.getInstructionOrDie(0xDEADBEEF + 1);
+  const auto *GoodInstrMeta =
+      Analysis.getPrevInstructionSequential(BadInstrMeta);
+  EXPECT_NE(nullptr, GoodInstrMeta);
+  EXPECT_EQ(0xDEADBEEF, GoodInstrMeta->VMAddress);
+  EXPECT_EQ(1u, GoodInstrMeta->InstructionSize);
+
+  GoodInstrMeta = Analysis.getNextInstructionSequential(BadInstrMeta);
+  EXPECT_NE(nullptr, GoodInstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 2, GoodInstrMeta->VMAddress);
+  EXPECT_EQ(1u, GoodInstrMeta->InstructionSize);
+}
+
+TEST_F(BasicFileAnalysisTest, CFITrapTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                   // 0: nop
+          0xb0, 0x00,             // 1: mov $0x0, %al
+          0x48, 0x89, 0xe5,       // 3: mov %rsp, %rbp
+          0x48, 0x83, 0xec, 0x18, // 6: sub $0x18, %rsp
+          0x48, 0xbe, 0xc4, 0x07, 0x40,
+          0x00, 0x00, 0x00, 0x00, 0x00, // 10: movabs $0x4007c4, %rsi
+          0x2f,                         // 20: (bad)
+          0x41, 0x0e,                   // 21: rex.B (bad)
+          0x62, 0x72, 0x65, 0x61, 0x6b, // 23: (bad) {%k1}
+          0x0f, 0x0b                    // 28: ud2
+      },
+      0xDEADBEEF);
+
+  EXPECT_FALSE(Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 3)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 6)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 10)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 20)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 21)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 23)));
+  EXPECT_TRUE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 28)));
+}
+
+TEST_F(BasicFileAnalysisTest, FallThroughTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                         // 0: nop
+          0xb0, 0x00,                   // 1: mov $0x0, %al
+          0x2f,                         // 3: (bad)
+          0x0f, 0x0b,                   // 4: ud2
+          0xff, 0x20,                   // 6: jmpq *(%rax)
+          0xeb, 0x00,                   // 8: jmp +0
+          0xe8, 0x45, 0xfe, 0xff, 0xff, // 10: callq [some loc]
+          0xff, 0x10,                   // 15: callq *(rax)
+          0x75, 0x00,                   // 17: jne +0
+          0xc3,                         // 19: retq
+      },
+      0xDEADBEEF);
+
+  EXPECT_TRUE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF)));
+  EXPECT_TRUE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 1)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 3)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 4)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 6)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 8)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 10)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 15)));
+  EXPECT_TRUE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 17)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 19)));
+}
+
+TEST_F(BasicFileAnalysisTest, DefiniteNextInstructionTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                         // 0: nop
+          0xb0, 0x00,                   // 1: mov $0x0, %al
+          0x2f,                         // 3: (bad)
+          0x0f, 0x0b,                   // 4: ud2
+          0xff, 0x20,                   // 6: jmpq *(%rax)
+          0xeb, 0x00,                   // 8: jmp 10 [+0]
+          0xeb, 0x05,                   // 10: jmp 17 [+5]
+          0xe8, 0x00, 0x00, 0x00, 0x00, // 12: callq 17 [+0]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 17: callq 0x1234569f [+0x12345678]
+          0xe8, 0x04, 0x00, 0x00, 0x00, // 22: callq 31 [+4]
+          0xff, 0x10,                   // 27: callq *(rax)
+          0x75, 0x00,                   // 29: jne 31 [+0]
+          0x75, 0xe0,                   // 31: jne 1 [-32]
+          0xc3,                         // 33: retq
+          0xeb, 0xdd,                   // 34: jmp 1 [-35]
+          0xeb, 0xdd,                   // 36: jmp 3 [-35]
+          0xeb, 0xdc,                   // 38: jmp 4 [-36]
+      },
+      0xDEADBEEF);
+
+  const auto *Current = Analysis.getInstruction(0xDEADBEEF);
+  const auto *Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 1);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 3);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 4);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 6);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 8);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 10, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 10);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 12);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 17);
+  // Note, definite next instruction address is out of range and should fail.
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 22);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 31, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 27);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+  Current = Analysis.getInstruction(0xDEADBEEF + 29);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+  Current = Analysis.getInstruction(0xDEADBEEF + 31);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+  Current = Analysis.getInstruction(0xDEADBEEF + 33);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 34);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 36);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 38);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 4, Next->VMAddress);
+}
+
+TEST_F(BasicFileAnalysisTest, ControlFlowXRefsTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                         // 0: nop
+          0xb0, 0x00,                   // 1: mov $0x0, %al
+          0x2f,                         // 3: (bad)
+          0x0f, 0x0b,                   // 4: ud2
+          0xff, 0x20,                   // 6: jmpq *(%rax)
+          0xeb, 0x00,                   // 8: jmp 10 [+0]
+          0xeb, 0x05,                   // 10: jmp 17 [+5]
+          0xe8, 0x00, 0x00, 0x00, 0x00, // 12: callq 17 [+0]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 17: callq 0x1234569f [+0x12345678]
+          0xe8, 0x04, 0x00, 0x00, 0x00, // 22: callq 31 [+4]
+          0xff, 0x10,                   // 27: callq *(rax)
+          0x75, 0x00,                   // 29: jne 31 [+0]
+          0x75, 0xe0,                   // 31: jne 1 [-32]
+          0xc3,                         // 33: retq
+          0xeb, 0xdd,                   // 34: jmp 1 [-35]
+          0xeb, 0xdd,                   // 36: jmp 3 [-35]
+          0xeb, 0xdc,                   // 38: jmp 4 [-36]
+      },
+      0xDEADBEEF);
+  const auto *InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF);
+  std::set<const Instr *> XRefs =
+      Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(XRefs.empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 1);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 34))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 3);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 1)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 36))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 4);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 38))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 6);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 8);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 10);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 8))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 12);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 17);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 10)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 12))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 22);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 27);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 29);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 31);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 22)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 29))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 33);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 34);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 36);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 38);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionInvalidTargets) {
+  Analysis.parseSectionContents(
+      {
+          0x90,       // 0: nop
+          0x0f, 0x0b, // 1: ud2
+          0x75, 0x00, // 3: jne 5 [+0]
+      },
+      0xDEADBEEF);
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF));
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 1));
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 3));
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADC0DE));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionBasicFallthroughToUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0x0f, 0x0b, // 2: ud2
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionBasicJumpToUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x0f, 0x0b, // 4: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 2));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x03, // 0: jne 5 [+3]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x0f, 0x0b, // 5: ud2
+          0x75, 0xf9, // 7: jne 2 [-7]
+          0x0f, 0x0b, // 9: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathSingleUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x05, // 0: jne 7 [+5]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x75, 0xfb, // 5: jne 2 [-5]
+          0x0f, 0x0b, // 7: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualFailLimitUpwards) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x06, // 0: jne 8 [+6]
+          0x90,       // 2: nop
+          0x90,       // 3: nop
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0xff, 0x10, // 6: callq *(%rax)
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForConditionalBranch =
+      SearchLengthForConditionalBranch;
+  SearchLengthForConditionalBranch = 2;
+
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 6));
+
+  SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualFailLimitDownwards) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0x90,       // 6: nop
+          0x90,       // 7: nop
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 2;
+
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 2));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionGoodAndBadPaths) {
+  Analysis.parseSectionContents(
+      {
+          0xeb, 0x02, // 0: jmp 4 [+2]
+          0x75, 0x02, // 2: jne 6 [+2]
+          0xff, 0x10, // 4: callq *(%rax)
+          0x0f, 0x0b, // 6: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionWithUnconditionalJumpInFallthrough) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x04, // 0: jne 6 [+4]
+          0xeb, 0x00, // 2: jmp 4 [+0]
+          0xff, 0x10, // 4: callq *(%rax)
+          0x0f, 0x0b, // 6: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionComplexExample) {
+  // See unittests/GraphBuilder.cpp::BuildFlowGraphComplexExample for this
+  // graph.
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x12,                   // 0: jne 20 [+18]
+          0xeb, 0x03,                   // 2: jmp 7 [+3]
+          0x75, 0x10,                   // 4: jne 22 [+16]
+          0x90,                         // 6: nop
+          0x90,                         // 7: nop
+          0x90,                         // 8: nop
+          0xff, 0x10,                   // 9: callq *(%rax)
+          0xeb, 0xfc,                   // 11: jmp 9 [-4]
+          0x75, 0xfa,                   // 13: jne 9 [-6]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
+          0x90,                         // 20: nop
+          0x90,                         // 21: nop
+          0x0f, 0x0b,                   // 22: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 9));
+}
+
+} // anonymous namespace
+} // end namespace cfi_verify
+} // end namespace llvm
+
+int main(int argc, char **argv) {
+  ::testing::InitGoogleTest(&argc, argv);
+  llvm::cl::ParseCommandLineOptions(argc, argv);
+
+  llvm::InitializeAllTargetInfos();
+  llvm::InitializeAllTargetMCs();
+  llvm::InitializeAllAsmParsers();
+  llvm::InitializeAllDisassemblers();
+
+  return RUN_ALL_TESTS();
+}
Index: tools/llvm-cfi-verify/unittests/GraphBuilder.cpp
===================================================================
--- /dev/null
+++ tools/llvm-cfi-verify/unittests/GraphBuilder.cpp
@@ -0,0 +1,502 @@
+//===- llvm/tools/llvm-cfi-verify/unittests/GraphBuilder.cpp --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../GraphBuilder.h"
+#include "../FileAnalysis.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <cstdlib>
+
+using Instr = ::llvm::cfi_verify::FileAnalysis::Instr;
+using ::testing::Each;
+using ::testing::ElementsAre;
+using ::testing::Eq;
+using ::testing::Field;
+using ::testing::IsEmpty;
+using ::testing::Property;
+using ::testing::SizeIs;
+
+namespace llvm {
+namespace cfi_verify {
+// Custom node printers for gtest.
+void PrintControlFlowNode(ControlFlowNode *Node, unsigned depth,
+                          ::std::ostream *os) {
+  for (unsigned i = 0; i < depth; ++i)
+    *os << "  ";
+
+  if (Node == nullptr) {
+    *os << "nullptr";
+    return;
+  }
+
+  *os << "[" << Node->FlowLength << "] 0x" << std::hex
+      << Node->InstructionAddress << std::dec;
+  if (Node->Next) {
+    *os << "\n";
+    PrintControlFlowNode(Node->Next, depth + 1, os);
+  }
+}
+
+void PrintTo(ControlFlowNode *Node, ::std::ostream *os) {
+  *os << "\nControl Flow Node:\n";
+  PrintControlFlowNode(Node, 0, os);
+}
+
+void PrintTo(ConditionalBranchNode *Node, ::std::ostream *os) {
+  *os << "\nConditional Branch Node:\n";
+  if (Node == nullptr) {
+    *os << "nullptr";
+    return;
+  }
+
+  *os << "0x" << std::hex << Node->InstructionAddress << std::dec << "\n";
+  *os << " Target:\n";
+  if (Node->Target) {
+    PrintControlFlowNode(Node->Target, 1, os);
+    *os << "\n";
+  } else {
+    *os << "  ???\n";
+  }
+
+  *os << " Fallthrough:\n";
+  if (Node->Fallthrough) {
+    PrintControlFlowNode(Node->Fallthrough, 1, os);
+  } else {
+    *os << "  ???";
+  }
+}
+
+namespace {
+class ELFx86TestFileAnalysis : public FileAnalysis {
+public:
+  ELFx86TestFileAnalysis()
+      : FileAnalysis(Triple("x86_64--"), SubtargetFeatures()) {}
+
+  // Expose this method publicly for testing.
+  void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                            uint64_t SectionAddress) {
+    FileAnalysis::parseSectionContents(SectionBytes, SectionAddress);
+  }
+
+  Error initialiseDisassemblyMembers() {
+    return FileAnalysis::initialiseDisassemblyMembers();
+  }
+};
+
+class BasicGraphBuilderTest : public ::testing::Test {
+protected:
+  virtual void SetUp() {
+    if (Analysis.initialiseDisassemblyMembers()) {
+      exit(EXIT_FAILURE);
+    }
+  }
+
+  ELFx86TestFileAnalysis Analysis;
+};
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathFallthroughUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0x0f, 0x0b, // 2: ud2
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF);
+  const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(Result.BranchNodes,
+              Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress,
+                                   Eq(0xDEADBEEF)),
+                             Field(&ConditionalBranchNode::Fallthrough,
+                                   Property(&ControlFlowNode::flatten,
+                                            ElementsAre(0xDEADBEEF + 2))),
+                             Field(&ConditionalBranchNode::Target,
+                                   Property(&ControlFlowNode::flatten,
+                                            ElementsAre(0xDEADBEEF + 4))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x0f, 0x0b, // 4: ud2
+      },
+      0xDEADBEEF);
+  const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(Result.BranchNodes,
+              Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress,
+                                   Eq(0xDEADBEEF)),
+                             Field(&ConditionalBranchNode::Fallthrough,
+                                   Property(&ControlFlowNode::flatten,
+                                            ElementsAre(0xDEADBEEF + 2))),
+                             Field(&ConditionalBranchNode::Target,
+                                   Property(&ControlFlowNode::flatten,
+                                            ElementsAre(0xDEADBEEF + 4))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x03, // 0: jne 5 [+3]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x0f, 0x0b, // 5: ud2
+          0x75, 0xf9, // 7: jne 2 [-7]
+          0x0f, 0x0b, // 9: ud2
+      },
+      0xDEADBEEF);
+  const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(2));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 5))))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 7)),
+          Field(
+              &ConditionalBranchNode::Fallthrough,
+              Property(&ControlFlowNode::flatten, ElementsAre(0xDEADBEEF + 9))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x05, // 0: jne 7 [+5]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x75, 0xfb, // 5: jne 2 [-5]
+          0x0f, 0x0b, // 7: ud2
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(2));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 7))))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 5)),
+          Field(
+              &ConditionalBranchNode::Fallthrough,
+              Property(&ControlFlowNode::flatten, ElementsAre(0xDEADBEEF + 7))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) {
+  Analysis.parseSectionContents(
+      {
+          0x90,       // 0: nop
+          0x75, 0xfe, // 1: jne 1 [-2]
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 1);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADC0DE);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) {
+  Analysis.parseSectionContents(
+      {
+          0xeb, 0xfe, // 0: jmp 0 [-2]
+          0xff, 0x10, // 2: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+  EXPECT_THAT(Result.OrphanedNodes,
+              Contains(AllOf(Field(&ControlFlowNode::InstructionAddress,
+                                   Eq(0xDEADBEEF + 2)),
+                             Field(&ControlFlowNode::Next, Eq(nullptr)))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0xfe, // 0: jne 0 [-2]
+          0xff, 0x10, // 2: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Each(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten, ElementsAre(0xDEADBEEF))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xeb, 0xfc, // 2: jmp 0 [-4]
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 4))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x00, // 0: jne 2 [+0]
+          0xeb, 0xfc, // 2: jmp 0 [-4]
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.OrphanedNodes,
+              Contains(AllOf(Field(&ControlFlowNode::InstructionAddress,
+                                   Eq(0xDEADBEEF + 4)),
+                             Field(&ControlFlowNode::Next, Eq(nullptr)))));
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x06, // 0: jne 8 [+6]
+          0x90,       // 2: nop
+          0x90,       // 3: nop
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0xff, 0x10, // 6: callq *(%rax)
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForConditionalBranch =
+      SearchLengthForConditionalBranch;
+  SearchLengthForConditionalBranch = 2;
+
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 6);
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.OrphanedNodes,
+              Each(Property(&ControlFlowNode::flatten,
+                            ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5,
+                                        0xDEADBEEF + 6))));
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+
+  SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0x90,       // 6: nop
+          0x90,       // 7: nop
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 2;
+
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Each(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2))))));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) {
+  // The following code has this graph (in DOT format):
+  //   digraph G {
+  //     "0" -> "20"
+  //     "0" -> "2"
+  //     "20" -> "21"
+  //     "4" -> "22 (ud2)"
+  //     "21" -> "22 (ud2)"
+  //     "4" -> "6"
+  //     "6" -> "7"
+  //     "2" -> "7"
+  //     "7" -> "8"
+  //     "8" -> "9 (indirect)"
+  //     "13" -> "15 (error)"
+  //     "13" -> "9 (indirect)"
+  //     "11" -> "9 (indirect)"
+  //   }
+  // Or, in image format: https://i.imgur.com/aX5fCoi.png
+
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x12,                   // 0: jne 20 [+18]
+          0xeb, 0x03,                   // 2: jmp 7 [+3]
+          0x75, 0x10,                   // 4: jne 22 [+16]
+          0x90,                         // 6: nop
+          0x90,                         // 7: nop
+          0x90,                         // 8: nop
+          0xff, 0x10,                   // 9: callq *(%rax)
+          0xeb, 0xfc,                   // 11: jmp 9 [-4]
+          0x75, 0xfa,                   // 13: jne 9 [-6]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
+          0x90,                         // 20: nop
+          0x90,                         // 21: nop
+          0x0f, 0x0b,                   // 22: ud2
+      },
+      0x1000);
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 5;
+
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0x1000 + 9);
+
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes, SizeIs(3));
+
+  EXPECT_THAT(
+      Result.OrphanedNodes,
+      Each(AllOf(Field(&ControlFlowNode::InstructionAddress, Eq(0x1000u + 11)),
+                 Property(&ControlFlowNode::flatten,
+                          ElementsAre(0x1000 + 11, 0x1000 + 9)))));
+
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0x1000 + 20, 0x1000 + 21, 0x1000 + 22))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0x1000 + 2, 0x1000 + 7, 0x1000 + 8,
+                                     0x1000 + 9))))));
+
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u + 4)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten, ElementsAre(0x1000 + 22))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0x1000 + 6, 0x1000 + 7, 0x1000 + 8,
+                                     0x1000 + 9))))));
+
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u + 13)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten, ElementsAre(0x1000 + 9))),
+          Field(
+              &ConditionalBranchNode::Fallthrough,
+              Property(&ControlFlowNode::flatten, ElementsAre(0x1000 + 15))))));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+} // anonymous namespace
+} // end namespace cfi_verify
+} // end namespace llvm
Index: unittests/CMakeLists.txt
===================================================================
--- unittests/CMakeLists.txt
+++ unittests/CMakeLists.txt
@@ -27,3 +27,4 @@
 add_subdirectory(Target)
 add_subdirectory(Transforms)
 add_subdirectory(XRay)
+add_subdirectory(../tools/llvm-cfi-verify/unittests ../tools/llvm-cfi-verify/unittests)