diff --git a/compiler/compiler.h b/compiler/compiler.h
index 07e2fd6..d688ead 100644
--- a/compiler/compiler.h
+++ b/compiler/compiler.h
@@ -41,7 +41,7 @@
 
   static Compiler* Create(CompilerDriver* driver, Kind kind);
 
-  virtual void Init() const = 0;
+  virtual void Init() = 0;
 
   virtual void UnInit() const = 0;
 
diff --git a/compiler/dex/quick/quick_compiler.cc b/compiler/dex/quick/quick_compiler.cc
index c14e22e..102ce17 100644
--- a/compiler/dex/quick/quick_compiler.cc
+++ b/compiler/dex/quick/quick_compiler.cc
@@ -41,7 +41,7 @@
  public:
   explicit QuickCompiler(CompilerDriver* driver) : Compiler(driver, 100) {}
 
-  void Init() const OVERRIDE;
+  void Init() OVERRIDE;
 
   void UnInit() const OVERRIDE;
 
@@ -574,7 +574,7 @@
   cu.disable_opt |= kDisabledOptimizationsPerISA[cu.instruction_set];
 }
 
-void QuickCompiler::Init() const {
+void QuickCompiler::Init() {
   CHECK(GetCompilerDriver()->GetCompilerContext() == nullptr);
 }
 
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 5d1703e..b14b0a7 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -167,6 +167,15 @@
       }
       output_ << "]";
     }
+    if (instruction->IsIntConstant()) {
+      output_ << " " << instruction->AsIntConstant()->GetValue();
+    } else if (instruction->IsLongConstant()) {
+      output_ << " " << instruction->AsLongConstant()->GetValue();
+    } else if (instruction->IsFloatConstant()) {
+      output_ << " " << instruction->AsFloatConstant()->GetValue();
+    } else if (instruction->IsDoubleConstant()) {
+      output_ << " " << instruction->AsDoubleConstant()->GetValue();
+    }
     if (pass_name_ == kLivenessPassName && instruction->GetLifetimePosition() != kNoLifetime) {
       output_ << " (liveness: " << instruction->GetLifetimePosition();
       if (instruction->HasLiveInterval()) {
@@ -270,7 +279,7 @@
                                    const char* string_filter,
                                    const CodeGenerator& codegen,
                                    const char* method_name)
-    : output_(output), graph_(graph), codegen_(codegen), is_enabled_(false) {
+  : output_(output), graph_(graph), codegen_(codegen), is_enabled_(false) {
   if (output == nullptr) {
     return;
   }
@@ -279,7 +288,7 @@
   }
 
   is_enabled_ = true;
-  HGraphVisualizerPrinter printer(graph, *output_, "", codegen_);
+  HGraphVisualizerPrinter printer(graph_, *output_, "", codegen_);
   printer.StartTag("compilation");
   printer.PrintProperty("name", method_name);
   printer.PrintProperty("method", method_name);
@@ -287,12 +296,12 @@
   printer.EndTag("compilation");
 }
 
-void HGraphVisualizer::DumpGraph(const char* pass_name) const {
-  if (!is_enabled_) {
-    return;
+void HGraphVisualizer::DumpGraph(const char* pass_name, bool is_after_pass) const {
+  if (is_enabled_) {
+    std::string pass_desc = std::string(pass_name) + (is_after_pass ? " (after)" : " (before)");
+    HGraphVisualizerPrinter printer(graph_, *output_, pass_desc.c_str(), codegen_);
+    printer.Run();
   }
-  HGraphVisualizerPrinter printer(graph_, *output_, pass_name, codegen_);
-  printer.Run();
 }
 
 }  // namespace art
diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h
index b5baed9..b90d15e 100644
--- a/compiler/optimizing/graph_visualizer.h
+++ b/compiler/optimizing/graph_visualizer.h
@@ -32,28 +32,18 @@
 static const char* kRegisterAllocatorPassName = "register";
 
 /**
- * If enabled, emits compilation information suitable for the c1visualizer tool
- * and IRHydra.
- * Currently only works if the compiler is single threaded.
+ * This class outputs the HGraph in the C1visualizer format.
+ * Note: Currently only works if the compiler is single threaded.
  */
 class HGraphVisualizer : public ValueObject {
  public:
-  /**
-   * If output is not null, and the method name of the dex compilation
-   * unit contains `string_filter`, the compilation information will be
-   * emitted.
-   */
   HGraphVisualizer(std::ostream* output,
                    HGraph* graph,
                    const char* string_filter,
                    const CodeGenerator& codegen,
                    const char* method_name);
 
-  /**
-   * If this visualizer is enabled, emit the compilation information
-   * in `output_`.
-   */
-  void DumpGraph(const char* pass_name) const;
+  void DumpGraph(const char* pass_name, bool is_after_pass = true) const;
 
  private:
   std::ostream* const output_;
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index deebaf7..94751f8 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -68,13 +68,8 @@
 };
 
 /**
- * If set to true, generates a file suitable for the c1visualizer tool and IRHydra.
- */
-static bool kIsVisualizerEnabled = false;
-
-/**
  * Filter to apply to the visualizer. Methods whose name contain that filter will
- * be in the file.
+ * be dumped.
  */
 static const char* kStringFilter = "";
 
@@ -114,7 +109,7 @@
 
   void InitCompilationUnit(CompilationUnit& cu ATTRIBUTE_UNUSED) const OVERRIDE {}
 
-  void Init() const OVERRIDE {}
+  void Init() OVERRIDE;
 
   void UnInit() const OVERRIDE {}
 
@@ -136,8 +131,16 @@
     : Compiler(driver, kMaximumCompilationTimeBeforeWarning),
       run_optimizations_(
           driver->GetCompilerOptions().GetCompilerFilter() != CompilerOptions::kTime),
-      compilation_stats_() {
-  if (kIsVisualizerEnabled) {
+      compilation_stats_() {}
+
+void OptimizingCompiler::Init() {
+  // Enable C1visualizer output. Must be done in Init() because the compiler
+  // driver is not fully initialized when passed to the compiler's constructor.
+  CompilerDriver* driver = GetCompilerDriver();
+  if (driver->GetDumpPasses()) {
+    CHECK_EQ(driver->GetThreadCount(), 1U)
+      << "Graph visualizer requires the compiler to run single-threaded. "
+      << "Invoke the compiler with '-j1'.";
     visualizer_output_.reset(new std::ofstream("art.cfg"));
   }
 }
@@ -213,8 +216,9 @@
 
   for (size_t i = 0; i < arraysize(optimizations); ++i) {
     HOptimization* optimization = optimizations[i];
+    visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/false);
     optimization->Run();
-    visualizer.DumpGraph(optimization->GetPassName());
+    visualizer.DumpGraph(optimization->GetPassName(), /*is_after=*/true);
     optimization->Check();
   }
 }
diff --git a/compiler/optimizing/test/ConstantFolding.java b/compiler/optimizing/test/ConstantFolding.java
new file mode 100644
index 0000000..7fac5a9
--- /dev/null
+++ b/compiler/optimizing/test/ConstantFolding.java
@@ -0,0 +1,221 @@
+/*
+* Copyright (C) 2014 The Android Open Source Project
+*
+* Licensed under the Apache License, Version 2.0 (the "License");
+* you may not use this file except in compliance with the License.
+* You may obtain a copy of the License at
+*
+*      http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing, software
+* distributed under the License is distributed on an "AS IS" BASIS,
+* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+* See the License for the specific language governing permissions and
+* limitations under the License.
+*/
+
+public class ConstantFolding {
+
+  /**
+   * Tiny three-register program exercising int constant folding
+   * on negation.
+   */
+
+  // CHECK-START: int ConstantFolding.IntNegation() constant_folding (before)
+  // CHECK:   [[Const42:i[0-9]+]]  IntConstant 42
+  // CHECK:   [[Neg:i[0-9]+]]      Neg [ [[Const42]] ]
+  // CHECK:                        Return [ [[Neg]] ]
+
+  // CHECK-START: int ConstantFolding.IntNegation() constant_folding (after)
+  // CHECK:   [[ConstN42:i[0-9]+]] IntConstant -42
+  // CHECK:                        Return [ [[ConstN42]] ]
+
+  public static int IntNegation() {
+    int x, y;
+    x = 42;
+    y = -x;
+    return y;
+  }
+
+  /**
+   * Tiny three-register program exercising int constant folding
+   * on addition.
+   */
+
+  // CHECK-START: int ConstantFolding.IntAddition1() constant_folding (before)
+  // CHECK:   [[Const1:i[0-9]+]]   IntConstant 1
+  // CHECK:   [[Const2:i[0-9]+]]   IntConstant 2
+  // CHECK:   [[Add:i[0-9]+]]      Add [ [[Const1]] [[Const2]] ]
+  // CHECK:                        Return [ [[Add]] ]
+
+  // CHECK-START: int ConstantFolding.IntAddition1() constant_folding (after)
+  // CHECK:   [[Const3:i[0-9]+]]   IntConstant 3
+  // CHECK:                        Return [ [[Const3]] ]
+
+  public static int IntAddition1() {
+    int a, b, c;
+    a = 1;
+    b = 2;
+    c = a + b;
+    return c;
+  }
+
+ /**
+  * Small three-register program exercising int constant folding
+  * on addition.
+  */
+
+  // CHECK-START: int ConstantFolding.IntAddition2() constant_folding (before)
+  // CHECK:   [[Const1:i[0-9]+]]   IntConstant 1
+  // CHECK:   [[Const2:i[0-9]+]]   IntConstant 2
+  // CHECK:   [[Const5:i[0-9]+]]   IntConstant 5
+  // CHECK:   [[Const6:i[0-9]+]]   IntConstant 6
+  // CHECK:   [[Add1:i[0-9]+]]     Add [ [[Const1]] [[Const2]] ]
+  // CHECK:   [[Add2:i[0-9]+]]     Add [ [[Const5]] [[Const6]] ]
+  // CHECK:   [[Add3:i[0-9]+]]     Add [ [[Add1]] [[Add2]] ]
+  // CHECK:                        Return [ [[Add3]] ]
+
+  // CHECK-START: int ConstantFolding.IntAddition2() constant_folding (after)
+  // CHECK:   [[Const14:i[0-9]+]]  IntConstant 14
+  // CHECK:                        Return [ [[Const14]] ]
+
+  public static int IntAddition2() {
+    int a, b, c;
+    a = 1;
+    b = 2;
+    a += b;
+    b = 5;
+    c = 6;
+    b += c;
+    c = a + b;
+    return c;
+  }
+
+  /**
+   * Tiny three-register program exercising int constant folding
+   * on subtraction.
+   */
+
+  // CHECK-START: int ConstantFolding.IntSubtraction() constant_folding (before)
+  // CHECK:   [[Const5:i[0-9]+]]   IntConstant 5
+  // CHECK:   [[Const2:i[0-9]+]]   IntConstant 2
+  // CHECK:   [[Sub:i[0-9]+]]      Sub [ [[Const5]] [[Const2]] ]
+  // CHECK:                        Return [ [[Sub]] ]
+
+  // CHECK-START: int ConstantFolding.IntSubtraction() constant_folding (after)
+  // CHECK:   [[Const3:i[0-9]+]]   IntConstant 3
+  // CHECK:                        Return [ [[Const3]] ]
+
+  public static int IntSubtraction() {
+    int a, b, c;
+    a = 5;
+    b = 2;
+    c = a - b;
+    return c;
+  }
+
+  /**
+   * Tiny three-register program exercising long constant folding
+   * on addition.
+   */
+
+  // CHECK-START: long ConstantFolding.LongAddition() constant_folding (before)
+  // CHECK:   [[Const1:j[0-9]+]]   LongConstant 1
+  // CHECK:   [[Const2:j[0-9]+]]   LongConstant 2
+  // CHECK:   [[Add:j[0-9]+]]      Add [ [[Const1]] [[Const2]] ]
+  // CHECK:                        Return [ [[Add]] ]
+
+  // CHECK-START: long ConstantFolding.LongAddition() constant_folding (after)
+  // CHECK:   [[Const3:j[0-9]+]]   LongConstant 3
+  // CHECK:                        Return [ [[Const3]] ]
+
+  public static long LongAddition() {
+    long a, b, c;
+    a = 1L;
+    b = 2L;
+    c = a + b;
+    return c;
+  }
+
+  /**
+   * Tiny three-register program exercising long constant folding
+   * on subtraction.
+   */
+
+  // CHECK-START: long ConstantFolding.LongSubtraction() constant_folding (before)
+  // CHECK:   [[Const5:j[0-9]+]]   LongConstant 5
+  // CHECK:   [[Const2:j[0-9]+]]   LongConstant 2
+  // CHECK:   [[Sub:j[0-9]+]]      Sub [ [[Const5]] [[Const2]] ]
+  // CHECK:                        Return [ [[Sub]] ]
+
+  // CHECK-START: long ConstantFolding.LongSubtraction() constant_folding (after)
+  // CHECK:   [[Const3:j[0-9]+]]   LongConstant 3
+  // CHECK:                        Return [ [[Const3]] ]
+
+  public static long LongSubtraction() {
+    long a, b, c;
+    a = 5L;
+    b = 2L;
+    c = a - b;
+    return c;
+  }
+
+  /**
+   * Three-register program with a constant (static) condition.
+   */
+
+  // CHECK-START: int ConstantFolding.StaticCondition() constant_folding (before)
+  // CHECK:   [[Const5:i[0-9]+]]   IntConstant 5
+  // CHECK:   [[Const2:i[0-9]+]]   IntConstant 2
+  // CHECK:   [[Cond:z[0-9]+]]     GreaterThanOrEqual [ [[Const5]] [[Const2]] ]
+  // CHECK:                        If [ [[Cond]] ]
+
+  // CHECK-START: int ConstantFolding.StaticCondition() constant_folding (after)
+  // CHECK:   [[Const1:i[0-9]+]]   IntConstant 1
+  // CHECK:                        If [ [[Const1]] ]
+
+  public static int StaticCondition() {
+    int a, b, c;
+    a = 5;
+    b = 2;
+    if (a < b)
+      c = a + b;
+    else
+      c = a - b;
+    return c;
+  }
+
+  /**
+   * Four-variable program with jumps leading to the creation of many
+   * blocks.
+   *
+   * The intent of this test is to ensure that all constant expressions
+   * are actually evaluated at compile-time, thanks to the reverse
+   * (forward) post-order traversal of the the dominator tree.
+   */
+
+  // CHECK-START: int ConstantFolding.JumpsAndConditionals(boolean) constant_folding (before)
+  // CHECK:   [[Const5:i[0-9]+]]   IntConstant 5
+  // CHECK:   [[Const2:i[0-9]+]]   IntConstant 2
+  // CHECK:   [[Add:i[0-9]+]]      Add [ [[Const5]] [[Const2]] ]
+  // CHECK:   [[Phi:i[0-9]+]]      Phi [ [[Add]] [[Sub:i[0-9]+]] ]
+  // CHECK:                        Return [ [[Phi]] ]
+  // CHECK:   [[Sub]]              Sub [ [[Const5]] [[Const2]] ]
+
+  // CHECK-START: int ConstantFolding.JumpsAndConditionals(boolean) constant_folding (after)
+  // CHECK:   [[Const7:i[0-9]+]]   IntConstant 7
+  // CHECK:   [[Phi:i[0-9]+]]      Phi [ [[Const7]] [[Const3:i[0-9]+]] ]
+  // CHECK:                        Return [ [[Phi]] ]
+  // CHECK:   [[Const3]]           IntConstant 3
+
+  public static int JumpsAndConditionals(boolean cond) {
+    int a, b, c;
+    a = 5;
+    b = 2;
+    if (cond)
+      c = a + b;
+    else
+      c = a - b;
+    return c;
+  }
+}
diff --git a/tools/checker.py b/tools/checker.py
new file mode 100755
index 0000000..82a1e6b
--- /dev/null
+++ b/tools/checker.py
@@ -0,0 +1,570 @@
+#!/usr/bin/env python3
+#
+# Copyright (C) 2014 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+
+# Checker is a testing tool which compiles a given test file and compares the
+# state of the control-flow graph before and after each optimization pass
+# against a set of assertions specified alongside the tests.
+#
+# Tests are written in Java, turned into DEX and compiled with the Optimizing
+# compiler. "Check lines" are comments in the Java file which begin with prefix
+# 'CHECK' followed by a pattern that the engine attempts to match in the
+# compiler-generated output.
+#
+# Assertions are tested in groups which correspond to the individual compiler
+# passes. Each group of check lines therefore must start with a 'CHECK-START'
+# header which specifies the output group it should be tested against. The group
+# name must exactly match one of the groups recognized in the output (they can
+# be listed with the '--list-groups' command-line flag).
+#
+# Check line patterns are treated as plain text rather than regular expressions
+# but are whitespace agnostic.
+#
+# Actual regex patterns can be inserted enclosed in '{{' and '}}' brackets. If
+# curly brackets need to be used inside the body of the regex, they need to be
+# enclosed in round brackets. For example, the pattern '{{foo{2}}}' will parse
+# the invalid regex 'foo{2', but '{{(fo{2})}}' will match 'foo'.
+#
+# Regex patterns can be named and referenced later. A new variable is defined
+# with '[[name:regex]]' and can be referenced with '[[name]]'. Variables are
+# only valid within the scope of the defining group. Within a group they cannot
+# be redefined or used undefined.
+#
+# Example:
+#   The following assertions can be placed in a Java source file:
+#
+#   // CHECK-START: int MyClass.MyMethod() constant_folding (after)
+#   // CHECK:         [[ID:i[0-9]+]] IntConstant {{11|22}}
+#   // CHECK:                        Return [ [[ID]] ]
+#
+#   The engine will attempt to match the check lines against the output of the
+#   group named on the first line. Together they verify that the CFG after
+#   constant folding returns an integer constant with value either 11 or 22.
+#
+
+import argparse
+import os
+import re
+import shutil
+import sys
+import tempfile
+from subprocess import check_call
+
+class CommonEqualityMixin:
+  """Mixin for class equality as equality of the fields."""
+  def __eq__(self, other):
+    return (isinstance(other, self.__class__)
+           and self.__dict__ == other.__dict__)
+
+  def __ne__(self, other):
+    return not self.__eq__(other)
+
+  def __repr__(self):
+    return "<%s: %s>" % (type(self).__name__, str(self.__dict__))
+
+
+class CheckElement(CommonEqualityMixin):
+  """Single element of the check line."""
+
+  class Variant(object):
+    """Supported language constructs."""
+    Text, Pattern, VarRef, VarDef = range(4)
+
+  def __init__(self, variant, name, pattern):
+    self.variant = variant
+    self.name = name
+    self.pattern = pattern
+
+  @staticmethod
+  def parseText(text):
+    return CheckElement(CheckElement.Variant.Text, None, re.escape(text))
+
+  @staticmethod
+  def parsePattern(patternElem):
+    return CheckElement(CheckElement.Variant.Pattern, None, patternElem[2:len(patternElem)-2])
+
+  @staticmethod
+  def parseVariable(varElem):
+    colonPos = varElem.find(":")
+    if colonPos == -1:
+      # Variable reference
+      name = varElem[2:len(varElem)-2]
+      return CheckElement(CheckElement.Variant.VarRef, name, None)
+    else:
+      # Variable definition
+      name = varElem[2:colonPos]
+      body = varElem[colonPos+1:len(varElem)-2]
+      return CheckElement(CheckElement.Variant.VarDef, name, body)
+
+
+class CheckLine(CommonEqualityMixin):
+  """Representation of a single assertion in the check file formed of one or
+     more regex elements. Matching against an output line is successful only
+     if all regex elements can be matched in the given order."""
+
+  def __init__(self, lineContent, lineNo=-1):
+    lineContent = lineContent.strip()
+
+    self.lineNo = lineNo
+    self.content = lineContent
+
+    self.lineParts = self.__parse(lineContent)
+    if not self.lineParts:
+      raise Exception("Empty check line")
+
+  # Returns True if the given Match object was at the beginning of the line.
+  def __isMatchAtStart(self, match):
+    return (match is not None) and (match.start() == 0)
+
+  # Takes in a list of Match objects and returns the minimal start point among
+  # them. If there aren't any successful matches it returns the length of
+  # the searched string.
+  def __firstMatch(self, matches, string):
+    starts = map(lambda m: len(string) if m is None else m.start(), matches)
+    return min(starts)
+
+  # Returns the regex for finding a regex pattern in the check line.
+  def __getPatternRegex(self):
+    rStartSym = "\{\{"
+    rEndSym = "\}\}"
+    rBody = ".+?"
+    return rStartSym + rBody + rEndSym
+
+  # Returns the regex for finding a variable use in the check line.
+  def __getVariableRegex(self):
+    rStartSym = "\[\["
+    rEndSym = "\]\]"
+    rStartOptional = "("
+    rEndOptional = ")?"
+    rName = "[a-zA-Z][a-zA-Z0-9]*"
+    rSeparator = ":"
+    rBody = ".+?"
+    return rStartSym + rName + rStartOptional + rSeparator + rBody + rEndOptional + rEndSym
+
+  # This method parses the content of a check line stripped of the initial
+  # comment symbol and the CHECK keyword.
+  def __parse(self, line):
+    lineParts = []
+    # Loop as long as there is something to parse.
+    while line:
+      # Search for the nearest occurrence of the special markers.
+      matchWhitespace = re.search("\s+", line)
+      matchPattern = re.search(self.__getPatternRegex(), line)
+      matchVariable = re.search(self.__getVariableRegex(), line)
+
+      # If one of the above was identified at the current position, extract them
+      # from the line, parse them and add to the list of line parts.
+      if self.__isMatchAtStart(matchWhitespace):
+        # We want to be whitespace-agnostic so whenever a check line contains
+        # a whitespace, we add a regex pattern for an arbitrary non-zero number
+        # of whitespaces.
+        line = line[matchWhitespace.end():]
+        lineParts.append(CheckElement.parsePattern("{{\s+}}"))
+      elif self.__isMatchAtStart(matchPattern):
+        pattern = line[0:matchPattern.end()]
+        line = line[matchPattern.end():]
+        lineParts.append(CheckElement.parsePattern(pattern))
+      elif self.__isMatchAtStart(matchVariable):
+        var = line[0:matchVariable.end()]
+        line = line[matchVariable.end():]
+        lineParts.append(CheckElement.parseVariable(var))
+      else:
+        # If we're not currently looking at a special marker, this is a plain
+        # text match all the way until the first special marker (or the end
+        # of the line).
+        firstMatch = self.__firstMatch([ matchWhitespace, matchPattern, matchVariable ], line)
+        text = line[0:firstMatch]
+        line = line[firstMatch:]
+        lineParts.append(CheckElement.parseText(text))
+    return lineParts
+
+  # Returns the regex pattern to be matched in the output line. Variable
+  # references are substituted with their current values provided in the
+  # 'varState' argument.
+  # An exception is raised if a referenced variable is undefined.
+  def __generatePattern(self, linePart, varState):
+    if linePart.variant == CheckElement.Variant.VarRef:
+      try:
+        return re.escape(varState[linePart.name])
+      except KeyError:
+        raise Exception("Use of undefined variable '" + linePart.name + "' " +
+                        "(line " + str(self.lineNo))
+    else:
+      return linePart.pattern
+
+  # Attempts to match the check line against a line from the output file with
+  # the given initial variable values. It returns the new variable state if
+  # successful and None otherwise.
+  def match(self, outputLine, initialVarState):
+    initialSearchFrom = 0
+    initialPattern = self.__generatePattern(self.lineParts[0], initialVarState)
+    while True:
+      # Search for the first element on the regex parts list. This will mark
+      # the point on the line from which we will attempt to match the rest of
+      # the check pattern. If this iteration produces only a partial match,
+      # the next iteration will start searching further in the output.
+      firstMatch = re.search(initialPattern, outputLine[initialSearchFrom:])
+      if firstMatch is None:
+        return None
+      matchStart = initialSearchFrom + firstMatch.start()
+      initialSearchFrom += firstMatch.start() + 1
+
+      # Do the full matching on a shadow copy of the variable state. If the
+      # matching fails half-way, we will not need to revert the state.
+      varState = dict(initialVarState)
+
+      # Now try to parse all of the parts of the check line in the right order.
+      # Variable values are updated on-the-fly, meaning that a variable can
+      # be referenced immediately after its definition.
+      fullyMatched = True
+      for part in self.lineParts:
+        pattern = self.__generatePattern(part, varState)
+        match = re.match(pattern, outputLine[matchStart:])
+        if match is None:
+          fullyMatched = False
+          break
+        matchEnd = matchStart + match.end()
+        if part.variant == CheckElement.Variant.VarDef:
+          if part.name in varState:
+            raise Exception("Redefinition of variable '" + part.name + "'" +
+                            " (line " + str(self.lineNo) + ")")
+          varState[part.name] = outputLine[matchStart:matchEnd]
+        matchStart = matchEnd
+
+      # Return the new variable state if all parts were successfully matched.
+      # Otherwise loop and try to find another start point on the same line.
+      if fullyMatched:
+        return varState
+
+
+class CheckGroup(CommonEqualityMixin):
+  """Represents a named collection of check lines which are to be matched
+     against an output group of the same name."""
+
+  def __init__(self, name, lines):
+    if name:
+      self.name = name
+    else:
+      raise Exception("Check group does not have a name")
+    if lines:
+      self.lines = lines
+    else:
+      raise Exception("Check group " + self.name + " does not have a body")
+
+  def __headAndTail(self, list):
+    return list[0], list[1:]
+
+  # The driver of matching inside a group. It simultaneously reads lines from
+  # the output and check groups and attempts to match them against each other
+  # in the correct order.
+  def match(self, outputGroup):
+    readOutputLines = 0
+    lastMatch = 0
+
+    # Check and output lines which remain to be matched.
+    checkLines = self.lines
+    outputLines = outputGroup.body
+    varState = {}
+
+    # Retrieve the next check line.
+    while checkLines:
+      checkLine, checkLines = self.__headAndTail(checkLines)
+      foundMatch = False
+
+      # Retrieve the next output line.
+      while outputLines:
+        outputLine, outputLines = self.__headAndTail(outputLines)
+        readOutputLines += 1
+
+        # Try to match the current lines against each other. If successful,
+        # save the new state of variables and continue to the next check line.
+        newVarState = checkLine.match(outputLine, varState)
+        if newVarState is not None:
+          varState = newVarState
+          lastMatch = readOutputLines
+          foundMatch = True
+          break
+      if not foundMatch:
+        raise Exception("Could not match check line \"" + checkLine.content + "\" from line " +
+                        str(lastMatch+1) + " of the output. [vars=" + str(varState) + "]")
+
+  @staticmethod
+  def parse(name, lines):
+    return CheckGroup(name, list(map(lambda line: CheckLine(line), lines)))
+
+
+class OutputGroup(CommonEqualityMixin):
+  """Represents a named part of the test output against which a check group of
+     the same name is to be matched."""
+
+  def __init__(self, name, body):
+    if name:
+      self.name = name
+    else:
+      raise Exception("Output group does not have a name")
+    if body:
+      self.body = body
+    else:
+      raise Exception("Output group " + self.name + " does not have a body")
+
+
+class FileSplitMixin(object):
+  """Mixin for representing text files which need to be split into smaller
+     chunks before being parsed."""
+
+  def _parseStream(self, stream):
+    lineNo = 0
+    allGroups = []
+    currentGroup = None
+
+    for line in stream:
+      lineNo += 1
+      line = line.strip()
+      if not line:
+        continue
+
+      # Let the child class process the line and return information about it.
+      # The _processLine method can modify the content of the line (or delete it
+      # entirely) and specify whether it starts a new group.
+      processedLine, newGroupName = self._processLine(line, lineNo)
+      if newGroupName is not None:
+        currentGroup = (newGroupName, [])
+        allGroups.append(currentGroup)
+      if processedLine is not None:
+        currentGroup[1].append(processedLine)
+
+    # Finally, take the generated line groups and let the child class process
+    # each one before storing the final outcome.
+    return list(map(lambda group: self._processGroup(group[0], group[1]), allGroups))
+
+
+class CheckFile(FileSplitMixin):
+  """Collection of check groups extracted from the input test file."""
+
+  def __init__(self, prefix, checkStream):
+    self.prefix = prefix
+    self.groups = self._parseStream(checkStream)
+
+  # Attempts to parse a check line. The regex searches for a comment symbol
+  # followed by the CHECK keyword, given attribute and a colon at the very
+  # beginning of the line. Whitespaces are ignored.
+  def _extractLine(self, prefix, line):
+    ignoreWhitespace = "\s*"
+    commentSymbols = ["//", "#"]
+    prefixRegex = ignoreWhitespace + \
+                  "(" + "|".join(commentSymbols) + ")" + \
+                  ignoreWhitespace + \
+                  prefix + ":"
+
+    # The 'match' function succeeds only if the pattern is matched at the
+    # beginning of the line.
+    match = re.match(prefixRegex, line)
+    if match is not None:
+      return line[match.end():].strip()
+    else:
+      return None
+
+  def _processLine(self, line, lineNo):
+    startLine = self._extractLine(self.prefix + "-START", line)
+    if startLine is not None:
+      # Line starts with the CHECK-START keyword, start a new group
+      return (None, startLine)
+    else:
+      # Otherwise try to parse it as a standard CHECK line. If unsuccessful,
+      # _extractLine will return None and the line will be ignored.
+      return (self._extractLine(self.prefix, line), None)
+
+  def _exceptionLineOutsideGroup(self, line, lineNo):
+    raise Exception("Check file line lies outside a group (line " + str(lineNo) + ")")
+
+  def _processGroup(self, name, lines):
+    return CheckGroup.parse(name, lines)
+
+  def match(self, outputFile, printInfo=False):
+    for checkGroup in self.groups:
+      # TODO: Currently does not handle multiple occurrences of the same group
+      # name, e.g. when a pass is run multiple times. It will always try to
+      # match a check group against the first output group of the same name.
+      outputGroup = outputFile.findGroup(checkGroup.name)
+      if outputGroup is None:
+        raise Exception("Group " + checkGroup.name + " not found in the output")
+      if printInfo:
+        print("TEST " + checkGroup.name + "... ", end="", flush=True)
+      try:
+        checkGroup.match(outputGroup)
+        if printInfo:
+          print("PASSED")
+      except Exception as e:
+        if printInfo:
+          print("FAILED!")
+        raise e
+
+
+class OutputFile(FileSplitMixin):
+  """Representation of the output generated by the test and split into groups
+     within which the checks are performed.
+
+     C1visualizer format is parsed with a state machine which differentiates
+     between the 'compilation' and 'cfg' blocks. The former marks the beginning
+     of a method. It is parsed for the method's name but otherwise ignored. Each
+     subsequent CFG block represents one stage of the compilation pipeline and
+     is parsed into an output group named "<method name> <pass name>".
+     """
+
+  class ParsingState:
+    OutsideBlock, InsideCompilationBlock, StartingCfgBlock, InsideCfgBlock = range(4)
+
+  def __init__(self, outputStream):
+    # Initialize the state machine
+    self.lastMethodName = None
+    self.state = OutputFile.ParsingState.OutsideBlock
+    self.groups = self._parseStream(outputStream)
+
+  def _processLine(self, line, lineNo):
+    if self.state == OutputFile.ParsingState.StartingCfgBlock:
+      # Previous line started a new 'cfg' block which means that this one must
+      # contain the name of the pass (this is enforced by C1visualizer).
+      if re.match("name\s+\"[^\"]+\"", line):
+        # Extract the pass name, prepend it with the name of the method and
+        # return as the beginning of a new group.
+        self.state = OutputFile.ParsingState.InsideCfgBlock
+        return (None, self.lastMethodName + " " + line.split("\"")[1])
+      else:
+        raise Exception("Expected group name in output file (line " + str(lineNo) + ")")
+
+    elif self.state == OutputFile.ParsingState.InsideCfgBlock:
+      if line == "end_cfg":
+        self.state = OutputFile.ParsingState.OutsideBlock
+        return (None, None)
+      else:
+        return (line, None)
+
+    elif self.state == OutputFile.ParsingState.InsideCompilationBlock:
+      # Search for the method's name. Format: method "<name>"
+      if re.match("method\s+\"[^\"]+\"", line):
+        self.lastMethodName = line.split("\"")[1]
+      elif line == "end_compilation":
+        self.state = OutputFile.ParsingState.OutsideBlock
+      return (None, None)
+
+    else:  # self.state == OutputFile.ParsingState.OutsideBlock:
+      if line == "begin_cfg":
+        # The line starts a new group but we'll wait until the next line from
+        # which we can extract the name of the pass.
+        if self.lastMethodName is None:
+          raise Exception("Output contains a pass without a method header" +
+                          " (line " + str(lineNo) + ")")
+        self.state = OutputFile.ParsingState.StartingCfgBlock
+        return (None, None)
+      elif line == "begin_compilation":
+        self.state = OutputFile.ParsingState.InsideCompilationBlock
+        return (None, None)
+      else:
+        raise Exception("Output line lies outside a group (line " + str(lineNo) + ")")
+
+  def _processGroup(self, name, lines):
+    return OutputGroup(name, lines)
+
+  def findGroup(self, name):
+    for group in self.groups:
+      if group.name == name:
+        return group
+    return None
+
+
+def ParseArguments():
+  parser = argparse.ArgumentParser()
+  parser.add_argument("test_file", help="the source of the test with checking annotations")
+  parser.add_argument("--check-prefix", dest="check_prefix", default="CHECK", metavar="PREFIX",
+                      help="prefix of checks in the test file (default: CHECK)")
+  parser.add_argument("--list-groups", dest="list_groups", action="store_true",
+                      help="print a list of all groups found in the test output")
+  parser.add_argument("--dump-group", dest="dump_group", metavar="GROUP",
+                      help="print the contents of an output group")
+  return parser.parse_args()
+
+
+class cd:
+  """Helper class which temporarily changes the working directory."""
+
+  def __init__(self, newPath):
+    self.newPath = newPath
+
+  def __enter__(self):
+    self.savedPath = os.getcwd()
+    os.chdir(self.newPath)
+
+  def __exit__(self, etype, value, traceback):
+    os.chdir(self.savedPath)
+
+
+def CompileTest(inputFile, tempFolder):
+  classFolder = tempFolder + "/classes"
+  dexFile = tempFolder + "/test.dex"
+  oatFile = tempFolder + "/test.oat"
+  outputFile = tempFolder + "/art.cfg"
+  os.makedirs(classFolder)
+
+  # Build a DEX from the source file. We pass "--no-optimize" to dx to avoid
+  # interference with its optimizations.
+  check_call(["javac", "-d", classFolder, inputFile])
+  check_call(["dx", "--dex", "--no-optimize", "--output=" + dexFile, classFolder])
+
+  # Run dex2oat and export the HGraph. The output is stored into ${PWD}/art.cfg.
+  with cd(tempFolder):
+    check_call(["dex2oat", "-j1", "--dump-passes", "--compiler-backend=Optimizing",
+                "--android-root=" + os.environ["ANDROID_HOST_OUT"],
+                "--boot-image=" + os.environ["ANDROID_HOST_OUT"] + "/framework/core-optimizing.art",
+                "--runtime-arg", "-Xnorelocate", "--dex-file=" + dexFile, "--oat-file=" + oatFile])
+
+  return outputFile
+
+
+def ListGroups(outputFilename):
+  outputFile = OutputFile(open(outputFilename, "r"))
+  for group in outputFile.groups:
+    print(group.name)
+
+
+def DumpGroup(outputFilename, groupName):
+  outputFile = OutputFile(open(outputFilename, "r"))
+  group = outputFile.findGroup(groupName)
+  if group:
+    print("\n".join(group.body))
+  else:
+    raise Exception("Check group " + groupName + " not found in the output")
+
+
+def RunChecks(checkPrefix, checkFilename, outputFilename):
+  checkFile = CheckFile(checkPrefix, open(checkFilename, "r"))
+  outputFile = OutputFile(open(outputFilename, "r"))
+  checkFile.match(outputFile, True)
+
+
+if __name__ == "__main__":
+  args = ParseArguments()
+  tempFolder = tempfile.mkdtemp()
+
+  try:
+    outputFile = CompileTest(args.test_file, tempFolder)
+    if args.list_groups:
+      ListGroups(outputFile)
+    elif args.dump_group:
+      DumpGroup(outputFile, args.dump_group)
+    else:
+      RunChecks(args.check_prefix, args.test_file, outputFile)
+  finally:
+    shutil.rmtree(tempFolder)
diff --git a/tools/checker_test.py b/tools/checker_test.py
new file mode 100755
index 0000000..f69f9e3
--- /dev/null
+++ b/tools/checker_test.py
@@ -0,0 +1,371 @@
+#!/usr/bin/env python3
+#
+# Copyright (C) 2014 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# This is a test file which exercises all feautres supported by the domain-
+# specific markup language implemented by Checker.
+
+import checker
+import io
+import unittest
+
+
+class TestCheckFile_PrefixExtraction(unittest.TestCase):
+  def __tryParse(self, string):
+    checkFile = checker.CheckFile(None, [])
+    return checkFile._extractLine("CHECK", string)
+
+  def test_InvalidFormat(self):
+    self.assertIsNone(self.__tryParse("CHECK"))
+    self.assertIsNone(self.__tryParse(":CHECK"))
+    self.assertIsNone(self.__tryParse("CHECK:"))
+    self.assertIsNone(self.__tryParse("//CHECK"))
+    self.assertIsNone(self.__tryParse("#CHECK"))
+
+    self.assertIsNotNone(self.__tryParse("//CHECK:foo"))
+    self.assertIsNotNone(self.__tryParse("#CHECK:bar"))
+
+  def test_InvalidLabel(self):
+    self.assertIsNone(self.__tryParse("//ACHECK:foo"))
+    self.assertIsNone(self.__tryParse("#ACHECK:foo"))
+
+  def test_NotFirstOnTheLine(self):
+    self.assertIsNone(self.__tryParse("A// CHECK: foo"))
+    self.assertIsNone(self.__tryParse("A # CHECK: foo"))
+    self.assertIsNone(self.__tryParse("// // CHECK: foo"))
+    self.assertIsNone(self.__tryParse("# # CHECK: foo"))
+
+  def test_WhitespaceAgnostic(self):
+    self.assertIsNotNone(self.__tryParse("  //CHECK: foo"))
+    self.assertIsNotNone(self.__tryParse("//  CHECK: foo"))
+    self.assertIsNotNone(self.__tryParse("    //CHECK: foo"))
+    self.assertIsNotNone(self.__tryParse("//    CHECK: foo"))
+
+
+class TestCheckLine_Parse(unittest.TestCase):
+  def __getRegex(self, checkLine):
+    return "".join(map(lambda x: "(" + x.pattern + ")", checkLine.lineParts))
+
+  def __tryParse(self, string):
+    return checker.CheckLine(string)
+
+  def __parsesTo(self, string, expected):
+    self.assertEqual(expected, self.__getRegex(self.__tryParse(string)))
+
+  def __parsesPattern(self, string, pattern):
+    line = self.__tryParse(string)
+    self.assertEqual(1, len(line.lineParts))
+    self.assertEqual(checker.CheckElement.Variant.Pattern, line.lineParts[0].variant)
+    self.assertEqual(pattern, line.lineParts[0].pattern)
+
+  def __parsesVarRef(self, string, name):
+    line = self.__tryParse(string)
+    self.assertEqual(1, len(line.lineParts))
+    self.assertEqual(checker.CheckElement.Variant.VarRef, line.lineParts[0].variant)
+    self.assertEqual(name, line.lineParts[0].name)
+
+  def __parsesVarDef(self, string, name, body):
+    line = self.__tryParse(string)
+    self.assertEqual(1, len(line.lineParts))
+    self.assertEqual(checker.CheckElement.Variant.VarDef, line.lineParts[0].variant)
+    self.assertEqual(name, line.lineParts[0].name)
+    self.assertEqual(body, line.lineParts[0].pattern)
+
+  def __doesNotParse(self, string, partType):
+    line = self.__tryParse(string)
+    self.assertEqual(1, len(line.lineParts))
+    self.assertNotEqual(partType, line.lineParts[0].variant)
+
+  # Test that individual parts of the line are recognized
+
+  def test_TextOnly(self):
+    self.__parsesTo("foo", "(foo)")
+    self.__parsesTo("  foo  ", "(foo)")
+    self.__parsesTo("f$o^o", "(f\$o\^o)")
+
+  def test_TextWithWhitespace(self):
+    self.__parsesTo("foo bar", "(foo)(\s+)(bar)")
+    self.__parsesTo("foo   bar", "(foo)(\s+)(bar)")
+
+  def test_RegexOnly(self):
+    self.__parsesPattern("{{a?b.c}}", "a?b.c")
+
+  def test_VarRefOnly(self):
+    self.__parsesVarRef("[[ABC]]", "ABC")
+
+  def test_VarDefOnly(self):
+    self.__parsesVarDef("[[ABC:a?b.c]]", "ABC", "a?b.c")
+
+  def test_TextWithRegex(self):
+    self.__parsesTo("foo{{abc}}bar", "(foo)(abc)(bar)")
+
+  def test_TextWithVar(self):
+    self.__parsesTo("foo[[ABC:abc]]bar", "(foo)(abc)(bar)")
+
+  def test_PlainWithRegexAndWhitespaces(self):
+    self.__parsesTo("foo {{abc}}bar", "(foo)(\s+)(abc)(bar)")
+    self.__parsesTo("foo{{abc}} bar", "(foo)(abc)(\s+)(bar)")
+    self.__parsesTo("foo {{abc}} bar", "(foo)(\s+)(abc)(\s+)(bar)")
+
+  def test_PlainWithVarAndWhitespaces(self):
+    self.__parsesTo("foo [[ABC:abc]]bar", "(foo)(\s+)(abc)(bar)")
+    self.__parsesTo("foo[[ABC:abc]] bar", "(foo)(abc)(\s+)(bar)")
+    self.__parsesTo("foo [[ABC:abc]] bar", "(foo)(\s+)(abc)(\s+)(bar)")
+
+  def test_AllKinds(self):
+    self.__parsesTo("foo [[ABC:abc]]{{def}}bar", "(foo)(\s+)(abc)(def)(bar)")
+    self.__parsesTo("foo[[ABC:abc]] {{def}}bar", "(foo)(abc)(\s+)(def)(bar)")
+    self.__parsesTo("foo [[ABC:abc]] {{def}} bar", "(foo)(\s+)(abc)(\s+)(def)(\s+)(bar)")
+
+  # Test that variables and patterns are parsed correctly
+
+  def test_ValidPattern(self):
+    self.__parsesPattern("{{abc}}", "abc")
+    self.__parsesPattern("{{a[b]c}}", "a[b]c")
+    self.__parsesPattern("{{(a{bc})}}", "(a{bc})")
+
+  def test_ValidRef(self):
+    self.__parsesVarRef("[[ABC]]", "ABC")
+    self.__parsesVarRef("[[A1BC2]]", "A1BC2")
+
+  def test_ValidDef(self):
+    self.__parsesVarDef("[[ABC:abc]]", "ABC", "abc")
+    self.__parsesVarDef("[[ABC:ab:c]]", "ABC", "ab:c")
+    self.__parsesVarDef("[[ABC:a[b]c]]", "ABC", "a[b]c")
+    self.__parsesVarDef("[[ABC:(a[bc])]]", "ABC", "(a[bc])")
+
+  def test_Empty(self):
+    self.__doesNotParse("{{}}", checker.CheckElement.Variant.Pattern)
+    self.__doesNotParse("[[]]", checker.CheckElement.Variant.VarRef)
+    self.__doesNotParse("[[:]]", checker.CheckElement.Variant.VarDef)
+
+  def test_InvalidVarName(self):
+    self.__doesNotParse("[[0ABC]]", checker.CheckElement.Variant.VarRef)
+    self.__doesNotParse("[[AB=C]]", checker.CheckElement.Variant.VarRef)
+    self.__doesNotParse("[[ABC=]]", checker.CheckElement.Variant.VarRef)
+    self.__doesNotParse("[[0ABC:abc]]", checker.CheckElement.Variant.VarDef)
+    self.__doesNotParse("[[AB=C:abc]]", checker.CheckElement.Variant.VarDef)
+    self.__doesNotParse("[[ABC=:abc]]", checker.CheckElement.Variant.VarDef)
+
+  def test_BodyMatchNotGreedy(self):
+    self.__parsesTo("{{abc}}{{def}}", "(abc)(def)")
+    self.__parsesTo("[[ABC:abc]][[DEF:def]]", "(abc)(def)")
+
+
+class TestCheckLine_Match(unittest.TestCase):
+  def __matchSingle(self, checkString, outputString, varState={}):
+    checkLine = checker.CheckLine(checkString)
+    newVarState = checkLine.match(outputString, varState)
+    self.assertIsNotNone(newVarState)
+    return newVarState
+
+  def __notMatchSingle(self, checkString, outputString, varState={}):
+    checkLine = checker.CheckLine(checkString)
+    self.assertIsNone(checkLine.match(outputString, varState))
+
+  def test_TextAndWhitespace(self):
+    self.__matchSingle("foo", "foo")
+    self.__matchSingle("foo", "XfooX")
+    self.__matchSingle("foo", "foo bar")
+    self.__notMatchSingle("foo", "zoo")
+
+    self.__matchSingle("foo bar", "foo   bar")
+    self.__matchSingle("foo bar", "abc foo bar def")
+    self.__matchSingle("foo bar", "foo foo bar bar")
+    self.__notMatchSingle("foo bar", "foo abc bar")
+
+  def test_Pattern(self):
+    self.__matchSingle("foo{{A|B}}bar", "fooAbar")
+    self.__matchSingle("foo{{A|B}}bar", "fooBbar")
+    self.__notMatchSingle("foo{{A|B}}bar", "fooCbar")
+
+  def test_VariableReference(self):
+    self.__matchSingle("foo[[X]]bar", "foobar", {"X": ""})
+    self.__matchSingle("foo[[X]]bar", "fooAbar", {"X": "A"})
+    self.__matchSingle("foo[[X]]bar", "fooBbar", {"X": "B"})
+    self.__notMatchSingle("foo[[X]]bar", "foobar", {"X": "A"})
+    self.__notMatchSingle("foo[[X]]bar", "foo bar", {"X": "A"})
+    with self.assertRaises(Exception):
+      self.__matchSingle("foo[[X]]bar", "foobar", {})
+
+  def test_VariableDefinition(self):
+    self.__matchSingle("foo[[X:A|B]]bar", "fooAbar")
+    self.__matchSingle("foo[[X:A|B]]bar", "fooBbar")
+    self.__notMatchSingle("foo[[X:A|B]]bar", "fooCbar")
+
+    env = self.__matchSingle("foo[[X:A.*B]]bar", "fooABbar", {})
+    self.assertEqual(env, {"X": "AB"})
+    env = self.__matchSingle("foo[[X:A.*B]]bar", "fooAxxBbar", {})
+    self.assertEqual(env, {"X": "AxxB"})
+
+    self.__matchSingle("foo[[X:A|B]]bar[[X]]baz", "fooAbarAbaz")
+    self.__matchSingle("foo[[X:A|B]]bar[[X]]baz", "fooBbarBbaz")
+    self.__notMatchSingle("foo[[X:A|B]]bar[[X]]baz", "fooAbarBbaz")
+
+  def test_NoVariableRedefinition(self):
+    with self.assertRaises(Exception):
+      self.__matchSingle("[[X:...]][[X]][[X:...]][[X]]", "foofoobarbar")
+
+  def test_EnvNotChangedOnPartialMatch(self):
+    env = {"Y": "foo"}
+    self.__notMatchSingle("[[X:A]]bar", "Abaz", env)
+    self.assertFalse("X" in env.keys())
+
+  def test_VariableContentEscaped(self):
+    self.__matchSingle("[[X:..]]foo[[X]]", ".*foo.*")
+    self.__notMatchSingle("[[X:..]]foo[[X]]", ".*fooAAAA")
+
+
+class TestCheckGroup_Match(unittest.TestCase):
+  def __matchMulti(self, checkString, outputString):
+    checkGroup = checker.CheckGroup.parse("MyGroup", checkString.splitlines())
+    outputGroup = checker.OutputGroup("MyGroup", outputString.splitlines())
+    return checkGroup.match(outputGroup)
+
+  def __notMatchMulti(self, checkString, outputString):
+    with self.assertRaises(Exception):
+      self.__matchMulti(checkString, outputString)
+
+  def test_TextAndPattern(self):
+    self.__matchMulti("""foo bar
+                         abc {{def}}""",
+                      """foo bar
+                         abc def""");
+    self.__matchMulti("""foo bar
+                         abc {{de.}}""",
+                      """=======
+                         foo bar
+                         =======
+                         abc de#
+                         =======""");
+    self.__notMatchMulti("""//XYZ: foo bar
+                            //XYZ: abc {{def}}""",
+                         """=======
+                            foo bar
+                            =======
+                            abc de#
+                            =======""");
+
+  def test_Variables(self):
+    self.__matchMulti("""foo[[X:.]]bar
+                         abc[[X]]def""",
+                      """foo bar
+                         abc def""");
+    self.__matchMulti("""foo[[X:([0-9]+)]]bar
+                         abc[[X]]def
+                         ### [[X]] ###""",
+                      """foo1234bar
+                         abc1234def
+                         ### 1234 ###""");
+
+  def test_Ordering(self):
+    self.__matchMulti("""foo
+                         bar""",
+                      """foo
+                         bar""")
+    self.__notMatchMulti("""foo
+                            bar""",
+                         """bar
+                            foo""")
+
+class TestOutputFile_Parse(unittest.TestCase):
+  def __parsesTo(self, string, expected):
+    outputStream = io.StringIO(string)
+    return self.assertEqual(checker.OutputFile(outputStream).groups, expected)
+
+  def test_NoInput(self):
+    self.__parsesTo(None, [])
+    self.__parsesTo("", [])
+
+  def test_SingleGroup(self):
+    self.__parsesTo("""begin_compilation
+                         method "MyMethod"
+                       end_compilation
+                       begin_cfg
+                         name "pass1"
+                         foo
+                         bar
+                       end_cfg""",
+                    [ checker.OutputGroup("MyMethod pass1", [ "foo", "bar" ]) ])
+
+  def test_MultipleGroups(self):
+    self.__parsesTo("""begin_compilation
+                         name "xyz1"
+                         method "MyMethod1"
+                         date 1234
+                       end_compilation
+                       begin_cfg
+                         name "pass1"
+                         foo
+                         bar
+                       end_cfg
+                       begin_cfg
+                         name "pass2"
+                         abc
+                         def
+                       end_cfg""",
+                    [ checker.OutputGroup("MyMethod1 pass1", [ "foo", "bar" ]),
+                      checker.OutputGroup("MyMethod1 pass2", [ "abc", "def" ]) ])
+
+    self.__parsesTo("""begin_compilation
+                         name "xyz1"
+                         method "MyMethod1"
+                         date 1234
+                       end_compilation
+                       begin_cfg
+                         name "pass1"
+                         foo
+                         bar
+                       end_cfg
+                       begin_compilation
+                         name "xyz2"
+                         method "MyMethod2"
+                         date 5678
+                       end_compilation
+                       begin_cfg
+                         name "pass2"
+                         abc
+                         def
+                       end_cfg""",
+                    [ checker.OutputGroup("MyMethod1 pass1", [ "foo", "bar" ]),
+                      checker.OutputGroup("MyMethod2 pass2", [ "abc", "def" ]) ])
+
+class TestCheckFile_Parse(unittest.TestCase):
+  def __parsesTo(self, string, expected):
+    checkStream = io.StringIO(string)
+    return self.assertEqual(checker.CheckFile("CHECK", checkStream).groups, expected)
+
+  def test_NoInput(self):
+    self.__parsesTo(None, [])
+    self.__parsesTo("", [])
+
+  def test_SingleGroup(self):
+    self.__parsesTo("""// CHECK-START: Example Group
+                       // CHECK:  foo
+                       // CHECK:    bar""",
+                    [ checker.CheckGroup.parse("Example Group", [ "foo", "bar" ]) ])
+
+  def test_MultipleGroups(self):
+    self.__parsesTo("""// CHECK-START: Example Group1
+                       // CHECK: foo
+                       // CHECK: bar
+                       // CHECK-START: Example Group2
+                       // CHECK: abc
+                       // CHECK: def""",
+                    [ checker.CheckGroup.parse("Example Group1", [ "foo", "bar" ]),
+                      checker.CheckGroup.parse("Example Group2", [ "abc", "def" ]) ])
+
+if __name__ == '__main__':
+  unittest.main()