Graph builder implementation.

[hctim]

Summary

Implement a localised graph builder for indirect control flow instructions. Main interface is through GraphBuilder::buildFlowGraph, which will build a flow graph around an indirect CF instruction. Various modifications to FileVerifier are also made to const-expose some members needed for machine code analysis done by the graph builder.

[hctim]

Removed comments from CMakeLists.txt

[hctim]

Update to only diff the prev in stack.

[hctim]

Fix various warnings.

[vlad.tsyrklevich]

I'm having difficulty following this because you document what the GraphBuilder methods do but you never say how and I get lost before I figure that out. Maybe that could go in the GraphBuilder.cpp file header comments?

tools/llvm-cfi-verify/GraphBuilder.cpp

1 ↗

(On Diff #117450)

Missing header

tools/llvm-cfi-verify/GraphBuilder.h

49 ↗

(On Diff #117450)

Do these need to be externally visible?

67 ↗

(On Diff #117450)

Should be a method of ConditionalBranchNode (also, prefer to accept a raw_ostream& instead of hardcoding outs() for print methods, dump() typically writes to dbgs() I think)

68 ↗

(On Diff #117450)

ditto

76 ↗

(On Diff #117450)

Why are these pointers?

[hctim]

Merged changes from previous in stack, updated for vlad.tsyrklevich's comments.

[hctim]

Merged wrong CL, putting this back to the way it should be.

[hctim]

Merged changes from upstream.

[hctim]

Updated to fix vlad's comments.

[hctim]

tools/llvm-cfi-verify/GraphBuilder.h

49 ↗

(On Diff #117450)

They're modified by the tests in order to guarantee behaviour, even if the default change.

76 ↗

(On Diff #117450)

Don't want to mix storage (stack/heap) of nodes. Intermediate nodes cannot be stored on stack, as they are neither a branch node or an orphaned node. Consider the following:

[0x0: jmp 2]
       \
  [0x2: jmpq %rax]

0x2 is neither a branch node, nor an orphaned node. The only reference to it is via 0x0, which is a branch node.

Having all these nodes be heap-allocated makes the clean up much easier.

[hctim]

Added header to GraphBuilder.cpp

[hctim]

Backported D38564

[hctim]

format was from prev in stack, put it down there.

[vlad.tsyrklevich]

tools/llvm-cfi-verify/GraphBuilder.cpp

232 ↗

(On Diff #117881)

Reword this.

293 ↗

(On Diff #117881)

Since the if() statement continue;s as the end, place the below without an else statement to avoid nesting (makes it a bit easier to read and understand.)

310 ↗

(On Diff #117881)

Reword 'fall back on itself'

313 ↗

(On Diff #117881)

Replace with std::find_if() ?

326 ↗

(On Diff #117881)

Why not use createParentNode() here?

335 ↗

(On Diff #117881)

Place the error first, and also avoid the nesting here as well.

tools/llvm-cfi-verify/GraphBuilder.h

53 ↗

(On Diff #117881)

just print(

54 ↗

(On Diff #117881)

just flatten(

62 ↗

(On Diff #117881)

just print(

66 ↗

(On Diff #117881)

instrument CFI protection?

104 ↗

(On Diff #117881)

Would be nice to have a comment here that briefly explains the approach (e.g. there are some bits that build the graph backwards and some that build it forwards)

76 ↗

(On Diff #117450)

Would it make sense to just place ConditionalBranchNodes in a vector without dynamically allocating them so they don't have to be manually freed?

[hctim]

Updated with Vlad's comments.

tools/llvm-cfi-verify/GraphBuilder.h

76 ↗

(On Diff #117450)

Yep, done :)

[hctim]

Backported usesRegisterOperand.

[hctim]

Merged updates from stack.

[vlad.tsyrklevich]

tools/llvm-cfi-verify/GraphBuilder.h

75 ↗

(On Diff #118255)

Could we represent this as (1) a uint64_t SrcAddr -> uint64_t DstAddr mapping and (2) a std::vector<uint64_t> of orphaned nodes? Then you would not need the Next pointers, and presumably FlowLength can simply be maintained as an argument to buildFlowGraphImpl(). You could maintain O(1) lookup by using llvm::DenseMap which is hash-table based and lighter-weight than std::map (see http://llvm.org/docs/ProgrammersManual.html#llvm-adt-densemap-h) and that seems cleaner to me than the current structure, WDYT?

[hctim]

Patched in previous changes to unit tests.

[hctim]

Made GraphResult's members automatic storage duration.

[vlad.tsyrklevich]

tools/llvm-cfi-verify/lib/GraphBuilder.cpp

96 ↗

(On Diff #118988)

Why not just pass this in?

108 ↗

(On Diff #118988)

s/chain/basic block/?

152 ↗

(On Diff #118988)

ditto s/chain/basic block/?

154 ↗

(On Diff #118988)

ditto

176 ↗

(On Diff #118988)

ditto

196 ↗

(On Diff #118988)

nit: eliminate braces

227 ↗

(On Diff #118988)

This is executed here, 240, 253, 260, and 270. Any reason it can't just be done once above? Is it to avoid the ConditionalBranchNode case?

tools/llvm-cfi-verify/lib/GraphBuilder.h

57 ↗

(On Diff #118988)

Could this be reworded? I'm still not sure what it means.

86 ↗

(On Diff #118988)

Sentence cuts off

94 ↗

(On Diff #118988)

fully evaluated, or enumerated? Not sure what evaluated might refer to in this context.

108 ↗

(On Diff #118988)

s/acyclic/cycle/

[vlad.tsyrklevich]

tools/llvm-cfi-verify/lib/GraphBuilder.h

62 ↗

(On Diff #118988)

type: posible

68 ↗

(On Diff #118988)

It's not all keys, just keys for all valid instructions in that range right?

unittests/tools/llvm-cfi-verify/GraphBuilder.cpp

60 ↗

(On Diff #118988)

Why template it just for std::vector?

131 ↗

(On Diff #118988)

This is never reached since an unhandled Error (e.g. at destruction time) cause an immediate failure.

453 ↗

(On Diff #118988)

???

+----------+     +--------------+
|    20    | <-- |      0       |
+----------+     +--------------+
  |                |
  |                |
  v                v
+----------+     +--------------+
|    21    |     |      2       |
+----------+     +--------------+
  |                |
  |                |
  v                v
+----------+     +--------------+
| 22 (ud2) |  +> |      7       |
+----------+  |  +--------------+
  ^           |    |
  |           |    |
  |           |    v
+----------+  |  +--------------+
|    4     |  |  |      8       |
+----------+  |  +--------------+
  |           |    |
  |           |    |
  v           |    v
+----------+  |  +--------------+     +------------+
|    6     | -+  | 9 (indirect) | <-- |     13     |
+----------+     +--------------+     +------------+
                   ^                    |
                   |                    |
                   |                    v
                 +--------------+     +------------+
                 |      11      |     | 15 (error) |
                 +--------------+     +------------+

[hctim]

Updated with Vlad's comments. Also patched the unit tests to succeed when x86 targets are not built, instead of not compiling.

tools/llvm-cfi-verify/lib/GraphBuilder.cpp

108 ↗

(On Diff #118988)

I've changed them all /s/chain/block. These blocks may contain direct unconditional branches as well :)

227 ↗

(On Diff #118988)

Yep, don't want to add a conditional branch to IntermediateNodes. I can't really see a good way to not repeat this LOC without introcuding a status variable which results in the same reuse.

tools/llvm-cfi-verify/lib/GraphBuilder.h

68 ↗

(On Diff #118988)

I think it's all keys, each key-value pair is built from the cross-references to the value. Invalid instructions (e.g. an indirect branch) will be an entry in OrphanedNodes, with a key-value pair between the invalid instruction -> its child.

unittests/tools/llvm-cfi-verify/GraphBuilder.cpp

60 ↗

(On Diff #118988)

Was initially using it to print IntermediateNodes (type: DenseMap) as well, now it's just printing vector's I'll remove the templating. Thanks!

453 ↗

(On Diff #118988)

It's beautiful!

[hctim]

Rebased over master. Forgot to add the unit test patches to this CL.

[vlad.tsyrklevich]

unittests/tools/llvm-cfi-verify/FileAnalysis.cpp

68 ↗

(On Diff #119725)

Could we (1) break the x86 test changes out into a follow-up CL and (2) check the error message to make sure we only skip tests for the specific error message we expect to see? I want to make sure we don't break something else in the future that accidentally disables unit tests without us realizing.

[hctim]

Patched out x86 test changes.

[skatkov]

This patch causes the same unittest compilation failure which was fixed in https://reviews.llvm.org/D39020.

Please fix it asap or revert the patch.

llvm/trunk/unittests/tools/llvm-cfi-verify/CMakeLists.txt

17

what is the reason you removed this line?

[skatkov]

Actually I took a liberty to submit https://reviews.llvm.org/rL316422 to unblock myself. Feel free to re-write it as you need but please ensure that it does not restore the issue.

llvm/trunk/tools/llvm-cfi-verify/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   AllTargetsAsmPrinters
   AllTargetsAsmParsers
   AllTargetsDescs
   AllTargetsDisassemblers
   AllTargetsInfos
+  CFIVerify
   MC
   MCParser
   Object
   Support
   )
 
 add_llvm_tool(llvm-cfi-verify
-  llvm-cfi-verify.cpp
-  lib/FileAnalysis.cpp
-  )
+  llvm-cfi-verify.cpp)
 
 add_subdirectory(lib)

llvm/trunk/tools/llvm-cfi-verify/lib/CMakeLists.txt

 add_library(LLVMCFIVerify
   STATIC
   FileAnalysis.cpp
-  FileAnalysis.h)
+  FileAnalysis.h
+  GraphBuilder.cpp
+  GraphBuilder.h)
 
 llvm_update_compile_flags(LLVMCFIVerify)
 llvm_map_components_to_libnames(libs
   MC
   MCParser
   Object
   Support)
 target_link_libraries(LLVMCFIVerify ${libs})

llvm/trunk/tools/llvm-cfi-verify/lib/FileAnalysis.h

 //===- 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/ADT/DenseMap.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"
private:
   std::unique_ptr<MCInstPrinter> Printer;
 
   // A mapping between the virtual memory address to the instruction metadata
   // struct.
   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;
+  DenseMap<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;

llvm/trunk/tools/llvm-cfi-verify/lib/GraphBuilder.h

+//===- 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/ADT/DenseMap.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 ConditionalBranchNode {
+  uint64_t Address;
+  uint64_t Target;
+  uint64_t Fallthrough;
+  // Does this conditional branch look like it's used for CFI protection? i.e.
+  //  - The exit point of a basic block whos entry point is {target|fallthrough}
+  //    is a CFI trap, and...
+  //  - The exit point of the other basic block is an undirect CF instruction.
+  bool CFIProtection;
+};
+
+// The canonical graph result structure returned by GraphBuilder. The members
+// in this structure encapsulate all possible code paths to the instruction
+// located at `BaseAddress`.
+struct GraphResult {
+  uint64_t BaseAddress;
+
+  // Map between an instruction address, and the address of the next instruction
+  // that will be executed. This map will contain all keys in the range:
+  //   - [orphaned node, base address)
+  //   - [conditional branch node {target|fallthrough}, base address)
+  DenseMap<uint64_t, uint64_t> IntermediateNodes;
+
+  // A list of orphaned nodes. A node is an 'orphan' if it meets any of the
+  // following criteria:
+  //   - The length of the path from the base to this node has exceeded
+  //     `SearchLengthForConditionalBranch`.
+  //   - The node has no cross references to it.
+  //   - The path from the base to this node is cyclic.
+  std::vector<uint64_t> OrphanedNodes;
+
+  // A list of top-level conditional branches that exist at the top of any
+  // non-orphan paths from the base.
+  std::vector<ConditionalBranchNode> ConditionalBranchNodes;
+
+  // Returns an in-order list of the path between the address provided and the
+  // base. The provided address must be part of this graph, and must not be a
+  // conditional branch.
+  std::vector<uint64_t> flattenAddress(uint64_t Address) const;
+};
+
+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 place them
+  // into GraphResult::ConditionalBranchNodes. It will also provide any orphaned
+  // (i.e. the upwards traversal 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 `Address`. 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 `Address` in the recursive call
+  // is now the XRef. If any XRef is an orphan, it is added to
+  // `Result.OrphanedNodes`. `OpenedNodes` keeps track of the list of nodes
+  // in the current path and is used for cycle-checking. If the path is found
+  // to be cyclic, it will be added to `Result.OrphanedNodes`.
+  static void buildFlowGraphImpl(const FileAnalysis &Analysis,
+                                 DenseSet<uint64_t> &OpenedNodes,
+                                 GraphResult &Result, uint64_t Address,
+                                 uint64_t Depth);
+
+  // 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,
+                                    GraphResult &Result,
+                                    ConditionalBranchNode &BranchNode,
+                                    const Instr &BranchInstrMeta);
+};
+
+} // end namespace cfi_verify
+} // end namespace llvm
+
+#endif // LLVM_CFI_VERIFY_GRAPH_BUILDER_H

llvm/trunk/tools/llvm-cfi-verify/lib/GraphBuilder.cpp

+//===- 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));
+
+std::vector<uint64_t> GraphResult::flattenAddress(uint64_t Address) const {
+  std::vector<uint64_t> Addresses;
+
+  auto It = IntermediateNodes.find(Address);
+  Addresses.push_back(Address);
+
+  while (It != IntermediateNodes.end()) {
+    Addresses.push_back(It->second);
+    It = IntermediateNodes.find(It->second);
+  }
+  return Addresses;
+}
+
+GraphResult GraphBuilder::buildFlowGraph(const FileAnalysis &Analysis,
+                                         uint64_t Address) {
+  GraphResult Result;
+  Result.BaseAddress = Address;
+  DenseSet<uint64_t> OpenedNodes;
+
+  const auto &IndirectInstructions = Analysis.getIndirectInstructions();
+
+  if (IndirectInstructions.find(Address) == IndirectInstructions.end())
+    return Result;
+
+  buildFlowGraphImpl(Analysis, OpenedNodes, Result, Address, 0);
+  return Result;
+}
+
+void GraphBuilder::buildFlowsToUndefined(const FileAnalysis &Analysis,
+                                         GraphResult &Result,
+                                         ConditionalBranchNode &BranchNode,
+                                         const Instr &BranchInstrMeta) {
+  assert(SearchLengthForUndef > 0 &&
+         "Search length for undefined flow must be greater than zero.");
+
+  // Start setting up the next node in the block.
+  uint64_t NextAddress = 0;
+  const Instr *NextMetaPtr;
+
+  // Find out the next instruction in the block 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.Address, 2) << ".\n";
+      return;
+    }
+
+    NextAddress = NextMetaPtr->VMAddress;
+    BranchNode.Fallthrough =
+        NextMetaPtr->VMAddress; // 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";
+      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";
+      return;
+    }
+
+    NextAddress = Target;
+    BranchNode.Target =
+        NextMetaPtr->VMAddress; // Add the new node to the branch head.
+  } else {
+    errs() << "ControlBranchNode supplied to buildFlowsToUndefined should "
+              "provide Target xor Fallthrough.\n";
+    return;
+  }
+
+  uint64_t CurrentAddress = NextAddress;
+  const Instr *CurrentMetaPtr = NextMetaPtr;
+
+  // Now the branch head has been set properly, complete the rest of the block.
+  for (uint64_t i = 1; i < SearchLengthForUndef; ++i) {
+    // Check to see whether the block 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.
+    NextAddress = NextMetaPtr->VMAddress;
+
+    // Add this as an intermediate.
+    Result.IntermediateNodes[CurrentAddress] = NextAddress;
+
+    // Move the 'current' pointers to the new tail of the block.
+    CurrentMetaPtr = NextMetaPtr;
+    CurrentAddress = NextAddress;
+  }
+
+  // Final check of the last thing we added to the block.
+  if (Analysis.isCFITrap(*CurrentMetaPtr))
+    BranchNode.CFIProtection = true;
+}
+
+void GraphBuilder::buildFlowGraphImpl(const FileAnalysis &Analysis,
+                                      DenseSet<uint64_t> &OpenedNodes,
+                                      GraphResult &Result, uint64_t Address,
+                                      uint64_t Depth) {
+  // If we've exceeded the flow length, terminate.
+  if (Depth >= SearchLengthForConditionalBranch) {
+    Result.OrphanedNodes.push_back(Address);
+    return;
+  }
+
+  // Ensure this flow is acyclic.
+  if (OpenedNodes.count(Address))
+    Result.OrphanedNodes.push_back(Address);
+
+  // If this flow is already explored, stop here.
+  if (Result.IntermediateNodes.count(Address))
+    return;
+
+  // Get the metadata for the node instruction.
+  const auto &InstrMetaPtr = Analysis.getInstruction(Address);
+  if (!InstrMetaPtr) {
+    errs() << "Failed to build flow graph for instruction at address "
+           << format_hex(Address, 2) << ".\n";
+    Result.OrphanedNodes.push_back(Address);
+    return;
+  }
+  const auto &ChildMeta = *InstrMetaPtr;
+
+  OpenedNodes.insert(Address);
+  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, OpenedNodes, Result, ParentMeta.VMAddress,
+                         Depth + 1);
+      Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
+      HasValidCrossRef = true;
+      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";
+      Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
+      Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
+      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 != Address) {
+        errs() << "Control flow to " << format_hex(Address, 2)
+               << ", but target resolution of "
+               << format_hex(ParentMeta.VMAddress, 2)
+               << " is not this address?\n";
+        Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
+        Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
+        continue;
+      }
+
+      buildFlowGraphImpl(Analysis, OpenedNodes, Result, ParentMeta.VMAddress,
+                         Depth + 1);
+      Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
+      HasValidCrossRef = true;
+      continue;
+    }
+
+    // Ensure that any unknown CFs are caught.
+    if (!ParentDesc.isConditionalBranch()) {
+      errs() << "Unknown control flow encountered when building graph at "
+             << format_hex(Address, 2) << "\n.";
+      Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
+      Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
+      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.Address = ParentMeta.VMAddress;
+    BranchNode.Target = 0;
+    BranchNode.Fallthrough = 0;
+    BranchNode.CFIProtection = false;
+
+    if (BranchTarget == Address)
+      BranchNode.Target = Address;
+    else
+      BranchNode.Fallthrough = Address;
+
+    HasValidCrossRef = true;
+    buildFlowsToUndefined(Analysis, Result, BranchNode, ParentMeta);
+    Result.ConditionalBranchNodes.push_back(BranchNode);
+  }
+
+  if (!HasValidCrossRef)
+    Result.OrphanedNodes.push_back(Address);
+
+  OpenedNodes.erase(Address);
+}
+
+} // namespace cfi_verify
+} // namespace llvm

llvm/trunk/unittests/tools/llvm-cfi-verify/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   AllTargetsAsmPrinters
   AllTargetsAsmParsers
   AllTargetsDescs
   AllTargetsDisassemblers
   AllTargetsInfos
+  CFIVerify
   MC
   MCParser
   Object
   Support
   )
 
 list(FIND LLVM_TARGETS_TO_BUILD "X86" x86_idx)
 if (NOT x86_idx LESS 0)
   add_llvm_unittest(CFIVerifyTests
-    FileAnalysis.cpp)
-  target_link_libraries(CFIVerifyTests LLVMCFIVerify)
+    FileAnalysis.cpp
+    GraphBuilder.cpp)
 endif()

llvm/trunk/unittests/tools/llvm-cfi-verify/GraphBuilder.cpp

+//===- llvm/unittests/llvm-cfi-verify/GraphBuilder.cpp --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../tools/llvm-cfi-verify/lib/GraphBuilder.h"
+#include "../tools/llvm-cfi-verify/lib/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>
+#include <sstream>
+
+using Instr = ::llvm::cfi_verify::FileAnalysis::Instr;
+using ::testing::AllOf;
+using ::testing::Each;
+using ::testing::ElementsAre;
+using ::testing::Eq;
+using ::testing::Field;
+using ::testing::IsEmpty;
+using ::testing::Matches;
+using ::testing::Pair;
+using ::testing::PrintToString;
+using ::testing::Property;
+using ::testing::SizeIs;
+using ::testing::UnorderedElementsAre;
+using ::testing::Value;
+
+namespace llvm {
+namespace cfi_verify {
+// Printing helpers for gtest.
+std::string HexStringifyContainer(const std::vector<uint64_t> &C) {
+  std::stringstream Stream;
+  if (C.empty()) {
+    return "{ }";
+  }
+
+  Stream << "{ ";
+  const auto &LastElemIt = std::end(C) - 1;
+
+  for (auto It = std::begin(C); It != LastElemIt; ++It) {
+    Stream << "0x" << std::hex << *It << ", ";
+  }
+  Stream << "0x" << std::hex << *LastElemIt << " }";
+  return Stream.str();
+}
+
+void PrintTo(const ConditionalBranchNode &BranchNode, ::std::ostream *os) {
+  *os << "ConditionalBranchNode<Address: 0x" << std::hex << BranchNode.Address
+      << ", Target: 0x" << BranchNode.Target << ", Fallthrough: 0x"
+      << BranchNode.Fallthrough
+      << ", CFIProtection: " << BranchNode.CFIProtection << ">";
+}
+
+void PrintTo(const GraphResult &Result, ::std::ostream *os) {
+  *os << "Result BaseAddress: 0x" << std::hex << Result.BaseAddress << "\n";
+
+  if (Result.ConditionalBranchNodes.empty())
+    *os << "  (No conditional branch nodes)\n";
+
+  for (const auto &Node : Result.ConditionalBranchNodes) {
+    *os << "  ";
+    PrintTo(Node, os);
+    *os << "\n    Fallthrough Path: " << std::hex
+        << HexStringifyContainer(Result.flattenAddress(Node.Fallthrough))
+        << "\n";
+    *os << "    Target Path: " << std::hex
+        << HexStringifyContainer(Result.flattenAddress(Node.Target)) << "\n";
+  }
+
+  if (Result.OrphanedNodes.empty())
+    *os << "  (No orphaned nodes)";
+
+  for (const auto &Orphan : Result.OrphanedNodes) {
+    *os << "  Orphan (0x" << std::hex << Orphan
+        << ") Path: " << HexStringifyContainer(Result.flattenAddress(Orphan))
+        << "\n";
+  }
+}
+
+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()) {
+      FAIL() << "Failed to initialise FileAnalysis.";
+    }
+  }
+
+  ELFx86TestFileAnalysis Analysis;
+};
+
+MATCHER_P2(HasPath, Result, Matcher, "has path " + PrintToString(Matcher)) {
+  const auto &Path = Result.flattenAddress(arg);
+  *result_listener << "the path is " << PrintToString(Path);
+  return Matches(Matcher)(Path);
+}
+
+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.ConditionalBranchNodes, SizeIs(1));
+  EXPECT_THAT(Result.ConditionalBranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
+                     Field(&ConditionalBranchNode::Target,
+                           HasPath(Result, ElementsAre(0xDEADBEEF + 4))),
+                     Field(&ConditionalBranchNode::Fallthrough,
+                           HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
+      << PrintToString(Result);
+}
+
+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.ConditionalBranchNodes, SizeIs(1));
+  EXPECT_THAT(Result.ConditionalBranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
+                     Field(&ConditionalBranchNode::Target,
+                           HasPath(Result, ElementsAre(0xDEADBEEF + 4))),
+                     Field(&ConditionalBranchNode::Fallthrough,
+                           HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
+      << PrintToString(Result);
+}
+
+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.ConditionalBranchNodes, SizeIs(2));
+  EXPECT_THAT(Result.ConditionalBranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
+          Field(&ConditionalBranchNode::Target,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 5))))))
+      << PrintToString(Result);
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 7)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 9))),
+          Field(&ConditionalBranchNode::Target,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
+      << PrintToString(Result);
+}
+
+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.ConditionalBranchNodes, SizeIs(2));
+  EXPECT_THAT(Result.ConditionalBranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
+          Field(&ConditionalBranchNode::Target,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
+      << PrintToString(Result);
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
+          Field(&ConditionalBranchNode::Target,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
+      << PrintToString(Result);
+}
+
+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.ConditionalBranchNodes, IsEmpty());
+
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 1);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty());
+
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADC0DE);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.ConditionalBranchNodes, 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.ConditionalBranchNodes, IsEmpty());
+  EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 2));
+  EXPECT_THAT(Result.IntermediateNodes, IsEmpty());
+}
+
+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.ConditionalBranchNodes, SizeIs(1));
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Each(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+                 Field(&ConditionalBranchNode::Target,
+                       HasPath(Result, ElementsAre(0xDEADBEEF))),
+                 Field(&ConditionalBranchNode::Fallthrough,
+                       HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
+      << PrintToString(Result);
+}
+
+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.ConditionalBranchNodes, SizeIs(1));
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(
+          AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
+                Field(&ConditionalBranchNode::Fallthrough,
+                      HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))),
+                Field(&ConditionalBranchNode::Target,
+                      HasPath(Result, ElementsAre(0xDEADBEEF + 4))))))
+      << PrintToString(Result);
+}
+
+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, ElementsAre(0xDEADBEEF + 4));
+  EXPECT_THAT(Result.ConditionalBranchNodes, 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(HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5,
+                                               0xDEADBEEF + 6))))
+      << PrintToString(Result);
+  EXPECT_THAT(Result.ConditionalBranchNodes, 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.ConditionalBranchNodes,
+      Each(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+          Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Target,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 2))))))
+      << PrintToString(Result);
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+// This test ensures when avoiding doing repeated work we still generate the
+// paths correctly. We don't need to recalculate the flow from 0x2 -> 0x3 as it
+// should only need to be generated once.
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphWithRepeatedWork) {
+  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.ConditionalBranchNodes, SizeIs(2));
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+          Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Target,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 7))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))))
+      << PrintToString(Result);
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+          Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)),
+          Field(&ConditionalBranchNode::Target,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                HasPath(Result, ElementsAre(0xDEADBEEF + 7))))))
+      << PrintToString(Result);
+  EXPECT_THAT(Result.IntermediateNodes, SizeIs(1));
+  EXPECT_THAT(Result.IntermediateNodes,
+              UnorderedElementsAre(Pair(0xDEADBEEF + 2, 0xDEADBEEF + 3)));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) {
+  // The following code has this graph:
+  //  +----------+      +--------------+
+  //  |    20    | <--- |      0       |
+  //  +----------+      +--------------+
+  //    |                 |
+  //    v                 v
+  //  +----------+      +--------------+
+  //  |    21    |      |      2       |
+  //  +----------+      +--------------+
+  //    |                 |
+  //    v                 v
+  //  +----------+      +--------------+
+  //  | 22 (ud2) |  +-> |      7       |
+  //  +----------+  |   +--------------+
+  //    ^           |     |
+  //    |           |     v
+  //  +----------+  |   +--------------+
+  //  |    4     |  |   |      8       |
+  //  +----------+  |   +--------------+
+  //    |           |     |
+  //    v           |     v
+  //  +----------+  |   +--------------+    +------------+
+  //  |    6     | -+   | 9 (indirect) | <- |     13     |
+  //  +----------+      +--------------+    +------------+
+  //                      ^                   |
+  //                      |                   v
+  //                    +--------------+    +------------+
+  //                    |      11      |    | 15 (error) |
+  //                    +--------------+    +------------+
+  // 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.ConditionalBranchNodes, SizeIs(3));
+
+  EXPECT_THAT(
+      Result.OrphanedNodes,
+      Each(AllOf(Eq(0x1000u + 11),
+                 HasPath(Result, ElementsAre(0x1000 + 11, 0x1000 + 9)))))
+      << PrintToString(Result);
+
+  EXPECT_THAT(Result.ConditionalBranchNodes,
+              Contains(AllOf(
+                  Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+                  Field(&ConditionalBranchNode::Address, Eq(0x1000u)),
+                  Field(&ConditionalBranchNode::Target,
+                        HasPath(Result, ElementsAre(0x1000 + 20, 0x1000 + 21,
+                                                    0x1000 + 22))),
+                  Field(&ConditionalBranchNode::Fallthrough,
+                        HasPath(Result, ElementsAre(0x1000 + 2, 0x1000 + 7,
+                                                    0x1000 + 8, 0x1000 + 9))))))
+      << PrintToString(Result);
+
+  EXPECT_THAT(Result.ConditionalBranchNodes,
+              Contains(AllOf(
+                  Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+                  Field(&ConditionalBranchNode::Address, Eq(0x1000u + 4)),
+                  Field(&ConditionalBranchNode::Target,
+                        HasPath(Result, ElementsAre(0x1000 + 22))),
+                  Field(&ConditionalBranchNode::Fallthrough,
+                        HasPath(Result, ElementsAre(0x1000 + 6, 0x1000 + 7,
+                                                    0x1000 + 8, 0x1000 + 9))))))
+      << PrintToString(Result);
+
+  EXPECT_THAT(
+      Result.ConditionalBranchNodes,
+      Contains(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+                     Field(&ConditionalBranchNode::Address, Eq(0x1000u + 13)),
+                     Field(&ConditionalBranchNode::Target,
+                           HasPath(Result, ElementsAre(0x1000 + 9))),
+                     Field(&ConditionalBranchNode::Fallthrough,
+                           HasPath(Result, ElementsAre(0x1000 + 15))))))
+      << PrintToString(Result);
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+} // anonymous namespace
+} // end namespace cfi_verify
+} // end namespace llvm