Add tool annotating CFG with simpleperf data

perf2cfg annotates a CFG file with profiling information from simpleperf
data files. The tool outputs an annotated CFG file with the following
added information:
- Methods are annotated with their contribution relative to the total
profile.
- Basic blocks and assembly instructions are annotated with their
contribution relative to the method profile.
- Basic blocks are colored according to their contribution to the method
profile.

The tool does not modify any input file and, assuming c1visualizer can
parse the input CFG file, the annotated CFG file can be opened in
c1visualizer. While the tool does not thoroughly validate the input CFG
file, some checks ensure the input files have all been generated for the
same architecture.

Test: atest --host perf2cfg_test
Test: mypy --strict perf2cfg.py
Test: pylint perf2cfg perf2cfg.py
Change-Id: I86481c412bda56622cc91c0060a513c99f9fb11f

18 files changed, 1666 insertions, 0 deletions

diff --git a/perf2cfg/.style.yapf b/perf2cfg/.style.yapf
new file mode 100644
index 00000000..0e9640c2
--- /dev/null
+++ b/perf2cfg/.style.yapf
@@ -0,0 +1,2 @@
+[style]
+based_on_style = google
diff --git a/perf2cfg/Android.bp b/perf2cfg/Android.bp
new file mode 100644
index 00000000..46e55034
--- /dev/null
+++ b/perf2cfg/Android.bp
@@ -0,0 +1,44 @@
+// Copyright (C) 2020 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.
+
+python_library_host {
+    name: "perf2cfg_library",
+    srcs: [
+        "perf2cfg/*.py",
+    ],
+    libs: [
+        "simpleperf_report_lib",
+    ],
+}
+
+python_binary_host {
+    name: "perf2cfg",
+    srcs: [
+        "perf2cfg.py",
+    ],
+    libs: [
+        "perf2cfg_library",
+    ],
+}
+
+python_test_host {
+    name: "perf2cfg_test",
+    srcs: [
+        "perf2cfg_test.py",
+        "tests/*.py",
+    ],
+    libs: [
+        "perf2cfg_library",
+    ],
+}
diff --git a/perf2cfg/OWNERS b/perf2cfg/OWNERS
new file mode 100644
index 00000000..ce20bb8e
--- /dev/null
+++ b/perf2cfg/OWNERS
@@ -0,0 +1,5 @@
+mast@google.com
+ngeoffray@google.com
+rpl@google.com
+skvadrik@google.com
+vmarko@google.com
diff --git a/perf2cfg/README.md b/perf2cfg/README.md
new file mode 100644
index 00000000..85cbc455
--- /dev/null
+++ b/perf2cfg/README.md
@@ -0,0 +1,121 @@
+# perf2cfg
+
+perf2cfg annotates a control-flow graph (CFG) file with profiling information
+from simpleperf data files. A CFG file can be generated by the Android Runtime
+compiler using the `--dump-cfg=<cfg-file>` option. The tool outputs an
+annotated CFG file with the following added information:
+- Methods are annotated with their contribution relative to the total profile.
+- Basic blocks and assembly instructions are annotated with their contribution
+  relative to the method profile.
+- Basic blocks are colored according to their contribution to the method
+  profile.
+
+The tool does not modify any input files and assumes the input CFG file can be
+parsed by c1visualizer. The input files must have all been generated for the
+same architecture.
+
+## Usage
+
+```
+usage: perf2cfg [-h|--help] --cfg CFG --perf-data PERF_DATA [PERF_DATA ...]
+                [--output-file OUTPUT_FILE] [-e|--events EVENTS]
+                [--primary-event PRIMARY_EVENT]
+
+Annotates a CFG file with profiling information from simpleperf data files.
+
+optional arguments:
+  -h, --help            Show this help message and exit.
+  --output-file OUTPUT_FILE
+                        A path to the output CFG file.
+  -e EVENTS, --events EVENTS
+                        A comma-separated list of events only to use for
+                        annotating a CFG (default: use all events found in
+                        perf data). An error is reported if the events are not
+                        present in perf data.
+  --primary-event PRIMARY_EVENT
+                        The event to be used for basic blocks hotness analysis
+                        (default: cpu-cycles). Basic blocks are color
+                        highlighted according to their hotness. An error is
+                        reported if the primary event is not present in perf
+                        data.
+
+required arguments:
+  --cfg CFG             The CFG file to annotate.
+  --perf-data PERF_DATA [PERF_DATA ...]
+                        The perf data files to extract information from.
+```
+
+### Examples
+
+Annotate a CFG file:
+```
+perf2cfg --cfg art.cfg --perf-data perf.data
+```
+
+Annotate a CFG file with multiple simpleperf data files:
+```
+perf2cfg --cfg art.cfg \
+    --perf-data perf_event1.data perf_event2.data perf_event3.data
+```
+
+Color basic blocks according to cache-misses events:
+```
+perf2cfg --cfg art.cfg --perf-data perf.data \
+    --primary-event cache-misses
+```
+
+Display a subset of events from the simpleperf data file:
+```
+perf2cfg --cfg art.cfg --perf-data perf.data \
+    --events cpu-cycles,cache-misses
+```
+
+## Method annotations
+
+Once the annotated CFG file has been opened in c1visualizer, method annotations
+can be seen by enabling the "Show Package Names" and "Sort List of
+Compilations" options in the top-left "Compiled Methods" panel.
+
+## Basic block coloring
+
+perf2cfg implements basic block coloring by adding specific flags to the output
+CFG file. These flags have the following names and meanings:
+- `LO` (low): the basic block is responsible for 1 to 10% of its method primary
+  event.
+- `MO` (moderate): for 10 to 30%.
+- `CO` (considerable): for 30 to 50%
+- `HI` (high): for 50 to 100%.
+
+To use this feature, custom flags have to be defined in c1visualizer:
+1. Open c1visualizer.
+2. Click on the "Tools" menu entry and "Options" to open the options window.
+3. Click on the "Control Flow Graph" button if it isn't already selected.
+4. On the right of the "Flags" list, click on the "New" button.
+5. Enter "LO" in the text field and press "OK".
+6. Select the newly created flag in the list and click on the color picker
+   button.
+7. Select an appropriate color and press "OK".
+8. Repeat steps 4 to 7 for the remaining flags (MO, CO, and HI).
+
+Alternatively, flags can be defined by editing a properties file located at:
+`~/.c1visualizer/dev/config/Preferences/at/ssw/visualizer/cfg/options/CfgPreferences.properties`.
+The directory hierarchy and the file itself might have to be created.
+
+Replace the file contents with the following line to use a yellow to red
+gradient:
+```
+flagsPreference=LO(255,210,0);MO(253,155,5);CO(253,100,5);HI(245,40,5)
+```
+
+For colorblind people, this green gradient can be used as an alternative:
+```
+flagsPreference=LO(235,235,50);MO(210,210,40);CO(185,185,25);HI(155,155,15)
+```
+
+## Hacking
+
+A diagram of the finite state machine used to parse the input CFG file can be
+generated with the following command (requires Graphviz):
+```
+dot -Tpng doc/FSM.dot -o doc/FSM.png
+```
diff --git a/perf2cfg/doc/FSM.dot b/perf2cfg/doc/FSM.dot
new file mode 100644
index 00000000..43702b0b
--- /dev/null
+++ b/perf2cfg/doc/FSM.dot
@@ -0,0 +1,71 @@
+digraph finite_state_machine {
+    rankdir = "LR";
+
+    node [ shape = "doublecircle" ];
+    "End";
+
+    node [ shape = "point" ];
+    "Init";
+
+    node [ shape = "circle" ];
+    "Init" -> "Start";
+
+    "Start" -> "End" [ label = "EOF" ];
+    "Start" -> "Parse Method Name" [ label = "'begin_compilation'" ];
+    "Start" -> "Error" [ label = "NOT('begin_compilation')" ];
+
+    "Parse Method Name" -> "Skip to CFG"
+        [ label = "method_name IN analyzer.methods" ];
+    "Parse Method Name" -> "Skip Method"
+        [ label = "method_name NOT IN analyzer.methods" ];
+    "Parse Method Name" -> "Error" [ label = "EOF OR NOT('name')" ];
+
+    "Skip Method" -> "End" [ label = "EOF" ];
+    "Skip Method" -> "Parse Method Name" [ label = "'begin_compilation'" ];
+    "Skip Method" -> "Skip Method";
+
+    "Skip to CFG" -> "Start CFG" [ label = "'end_compilation'" ];
+    "Skip to CFG" -> "Skip to CFG";
+    "Skip to CFG" -> "Error" [ label = "EOF" ];
+
+    "Start CFG" -> "Is Disassembly Pass" [ label = "'begin_cfg'" ];
+    "Start CFG" -> "Error" [ label = "EOF OR NOT('begin_cfg')" ];
+
+    "Is Disassembly Pass" -> "Parse Flags"
+        [ label = "'name \"disassembly (after)\"'" ];
+    "Is Disassembly Pass" -> "Skip Pass"
+        [ label = "NOT('name \"disassembly (after)\"')" ];
+    "Is Disassembly Pass" -> "Error" [ label = "EOF OR NOT('name')" ];
+
+    "Skip Pass" -> "End CFG" [ label = "'end_cfg'" ];
+    "Skip Pass" -> "Skip Pass";
+    "Skip Pass" -> "Error" [ label = "EOF" ];
+
+    "Parse Flags" -> "Skip to HIR" [ label = "'flags'" ];
+    "Parse Flags" -> "Parse Flags";
+    "Parse Flags" -> "Error" [ label = "EOF" ];
+
+    "Skip to HIR" -> "HIR Instruction" [ label = "'begin_HIR'" ];
+    "Skip to HIR" -> "Skip to HIR";
+    "Skip to HIR" -> "Error" [ label = "EOF" ];
+
+    "HIR Instruction" -> "HIR Instruction" [ label = "'<|@'" ];
+    "HIR Instruction" -> "End HIR" [ label = "'end_HIR'" ];
+    "HIR Instruction" -> "Disassembly";
+    "HIR Instruction" -> "Error" [ label = "EOF" ];
+
+    "Disassembly" -> "HIR Instruction" [ label = "'<|@'" ];
+    "Disassembly" -> "Disassembly";
+    "Disassembly" -> "Error" [ label = "EOF" ];
+
+    "End HIR" -> "End Block" [ label = "'end_block'" ];
+    "End HIR" -> "Error" [ label = "EOF OR NOT('end_block')" ];
+
+    "End Block" -> "Parse Flags" [ label = "'begin_block'" ];
+    "End Block" -> "End CFG" [ label = "'end_cfg'" ];
+    "End Block" -> "Error" [ label = "EOF OR NOT('begin_block' OR 'end_cfg')" ];
+
+    "End CFG" -> "Is Disassembly Pass" [ label = "'begin_cfg'" ];
+    "End CFG" -> "Parse Method Name" [ label = "'begin_compilation'" ];
+    "End CFG" -> "End" [ label = "EOF" ];
+}
diff --git a/perf2cfg/perf2cfg.py b/perf2cfg/perf2cfg.py
new file mode 100755
index 00000000..b010d1a6
--- /dev/null
+++ b/perf2cfg/perf2cfg.py
@@ -0,0 +1,149 @@
+#!/usr/bin/env python3
+# Copyright (C) 2020 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 script annotates a CFG file with profiling information from simpleperf
+record files.
+
+Example:
+    perf2cfg --cfg bench.cfg --perf-data perf.data
+"""
+
+import argparse
+import logging
+import os
+import sys
+import textwrap
+
+from perf2cfg import analyze
+from perf2cfg import edit
+
+
+def parse_arguments() -> argparse.Namespace:
+    """Parses program arguments.
+
+    Returns:
+        argparse.Namespace: A populated argument namespace.
+    """
+    parser = argparse.ArgumentParser(
+        # Hardcode the usage string as argparse does not display long options
+        # if short ones are specified
+        usage=textwrap.dedent("""\
+        perf2cfg [-h|--help] --cfg CFG --perf-data PERF_DATA [PERF_DATA ...]
+                        [--output-file OUTPUT_FILE] [-e|--events EVENTS]
+                        [--primary-event PRIMARY_EVENT]"""),
+        description='Annotates a CFG file with profiling information from '
+        'simpleperf data files.',
+        add_help=False)
+    required = parser.add_argument_group('required arguments')
+    required.add_argument('--cfg',
+                          required=True,
+                          help='The CFG file to annotate.')
+    required.add_argument(
+        '--perf-data',
+        nargs='+',
+        required=True,
+        help='The perf data files to extract information from.')
+    parser.add_argument('-h',
+                        '--help',
+                        action='help',
+                        default=argparse.SUPPRESS,
+                        help='Show this help message and exit.')
+    parser.add_argument('--output-file', help='A path to the output CFG file.')
+    parser.add_argument(
+        '-e',
+        '--events',
+        type=lambda events: events.split(',') if events else [],
+        help='A comma-separated list of events only to use for annotating a '
+        'CFG (default: use all events found in perf data). An error is '
+        'reported if the events are not present in perf data.')
+    parser.add_argument(
+        '--primary-event',
+        default='cpu-cycles',
+        help='The event to be used for basic blocks hotness analysis '
+        '(default: %(default)s). Basic blocks are color highlighted according '
+        'to their hotness. An error is reported if the primary event is not '
+        'present in perf data.')
+    args = parser.parse_args()
+
+    if not args.output_file:
+        root, ext = os.path.splitext(args.cfg)
+        args.output_file = f'{root}-annotated{ext}'
+
+    return args
+
+
+def analyze_record_files(args: argparse.Namespace) -> analyze.RecordAnalyzer:
+    """Analyzes simpleperf record files.
+
+    Args:
+        args (argparse.Namespace): An argument namespace.
+
+    Returns:
+        analyze.RecordAnalyzer: A RecordAnalyzer object.
+    """
+    analyzer = analyze.RecordAnalyzer(args.events)
+    for record_file in args.perf_data:
+        analyzer.analyze(record_file)
+
+    return analyzer
+
+
+def validate_events(analyzer: analyze.RecordAnalyzer,
+                    args: argparse.Namespace) -> None:
+    """Validates event names given on the command line.
+
+    Args:
+        analyzer (analyze.RecordAnalyzer): A RecordAnalyzer object.
+        args (argparse.Namespace): An argument namespace.
+    """
+    if not analyzer.event_counts:
+        logging.error('The selected events are not present in perf data')
+        sys.exit(1)
+
+    if args.primary_event not in analyzer.event_counts:
+        logging.error(
+            'The selected primary event %s is not present in perf data',
+            args.primary_event)
+        sys.exit(1)
+
+
+def annotate_cfg_file(analyzer: analyze.RecordAnalyzer,
+                      args: argparse.Namespace) -> None:
+    """Annotates a CFG file.
+
+    Args:
+        analyzer (analyze.RecordAnalyzer): A RecordAnalyzer object.
+        args (argparse.Namespace): An argument namespace.
+    """
+    input_stream = open(args.cfg, 'r')
+    output_stream = open(args.output_file, 'w')
+
+    editor = edit.CfgEditor(analyzer, input_stream, output_stream,
+                            args.primary_event)
+    editor.edit()
+
+    input_stream.close()
+    output_stream.close()
+
+
+def main() -> None:
+    """Annotates a CFG file with information from simpleperf record files."""
+    args = parse_arguments()
+    analyzer = analyze_record_files(args)
+    validate_events(analyzer, args)
+    annotate_cfg_file(analyzer, args)
+
+
+if __name__ == '__main__':
+    main()
diff --git a/perf2cfg/perf2cfg/__init__.py b/perf2cfg/perf2cfg/__init__.py
new file mode 100644
index 00000000..c1b565d3
--- /dev/null
+++ b/perf2cfg/perf2cfg/__init__.py
@@ -0,0 +1,13 @@
+# Copyright (C) 2020 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.
diff --git a/perf2cfg/perf2cfg/analyze.py b/perf2cfg/perf2cfg/analyze.py
new file mode 100644
index 00000000..90a4e7b7
--- /dev/null
+++ b/perf2cfg/perf2cfg/analyze.py
@@ -0,0 +1,210 @@
+# Copyright (C) 2020 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.
+"""Classes for extracting profiling information from simpleperf record files.
+
+Example:
+    analyzer = RecordAnalyzer()
+    analyzer.analyze('perf.data')
+
+    for event_name, event_count in analyzer.event_counts.items():
+        print(f'Number of {event_name} events: {event_count}')
+"""
+
+import collections
+import logging
+import sys
+
+from typing import DefaultDict, Dict, Iterable, Iterator, Optional
+
+# Disable import-error as simpleperf_report_lib is not in pylint's `sys.path`
+# pylint: disable=import-error
+import simpleperf_report_lib  # type: ignore
+
+
+class Instruction:
+    """Instruction records profiling information for an assembly instruction.
+
+    Attributes:
+        relative_addr (int): The address of an instruction relative to the
+            start of its method. For arm64, the first instruction of a method
+            will be at the relative address 0, the second at the relative
+            address 4, and so on.
+        event_counts (DefaultDict[str, int]): A mapping of event names to their
+            total number of events for this instruction.
+    """
+
+    def __init__(self, relative_addr: int) -> None:
+        """Instantiates an Instruction.
+
+        Args:
+            relative_addr (int): A relative address.
+        """
+        self.relative_addr = relative_addr
+
+        self.event_counts: DefaultDict[str, int] = collections.defaultdict(int)
+
+    def record_sample(self, event_name: str, event_count: int) -> None:
+        """Records profiling information given by a sample.
+
+        Args:
+            event_name (str): An event name.
+            event_count (int): An event count.
+        """
+        self.event_counts[event_name] += event_count
+
+
+class Method:
+    """Method records profiling information for a compiled method.
+
+    Attributes:
+        name (str): A method name.
+        event_counts (DefaultDict[str, int]): A mapping of event names to their
+            total number of events for this method.
+        instructions (Dict[int, Instruction]): A mapping of relative
+            instruction addresses to their Instruction object.
+    """
+
+    def __init__(self, name: str) -> None:
+        """Instantiates a Method.
+
+        Args:
+            name (str): A method name.
+        """
+        self.name = name
+
+        self.event_counts: DefaultDict[str, int] = collections.defaultdict(int)
+        self.instructions: Dict[int, Instruction] = {}
+
+    def record_sample(self, relative_addr: int, event_name: str,
+                      event_count: int) -> None:
+        """Records profiling information given by a sample.
+
+        Args:
+            relative_addr (int): The relative address of an instruction hit.
+            event_name (str): An event name.
+            event_count (int): An event count.
+        """
+        self.event_counts[event_name] += event_count
+
+        if relative_addr not in self.instructions:
+            self.instructions[relative_addr] = Instruction(relative_addr)
+
+        instruction = self.instructions[relative_addr]
+        instruction.record_sample(event_name, event_count)
+
+
+class RecordAnalyzer:
+    """RecordAnalyzer extracts profiling information from simpleperf record
+    files.
+
+    Multiple record files can be analyzed successively, each containing one or
+    more event types. Samples from odex files are the only ones analyzed, as
+    we're interested by the performance of methods generated by the optimizing
+    compiler.
+
+    Attributes:
+        event_names (Set[str]): A set of event names to analyze. If empty, all
+            events are analyzed.
+        event_counts (DefaultDict[str, int]): A mapping of event names to their
+            total number of events for the analyzed samples.
+        methods (Dict[str, Method]): A mapping of method names to their Method
+            object.
+        report (simpleperf_report_lib.ReportLib): A ReportLib object.
+        target_arch (str): A target architecture determined from the first
+            record file analyzed.
+    """
+
+    def __init__(self, event_names: Optional[Iterable[str]] = None) -> None:
+        """Instantiates a RecordAnalyzer.
+
+        Args:
+            event_names (Optional[Iterable[str]]): An optional iterable of
+                event names to analyze. If empty or falsy, all events are
+                analyzed.
+        """
+        if not event_names:
+            event_names = []
+
+        self.event_names = set(event_names)
+
+        self.event_counts: DefaultDict[str, int] = collections.defaultdict(int)
+        self.methods: Dict[str, Method] = {}
+        self.report: simpleperf_report_lib.ReportLib
+        self.target_arch = ''
+
+    def analyze(self, filename: str) -> None:
+        """Analyzes a perf record file.
+
+        Args:
+            filename (str): The path to a perf record file.
+        """
+        # One ReportLib object needs to be instantiated per record file
+        self.report = simpleperf_report_lib.ReportLib()
+        self.report.SetRecordFile(filename)
+
+        arch = self.report.GetArch()
+        if not self.target_arch:
+            self.target_arch = arch
+        elif self.target_arch != arch:
+            logging.error(
+                'Record file %s is for the architecture %s, expected %s',
+                filename, arch, self.target_arch)
+            self.report.Close()
+            sys.exit(1)
+
+        for sample in self.samples():
+            event = self.report.GetEventOfCurrentSample()
+            if self.event_names and event.name not in self.event_names:
+                continue
+
+            symbol = self.report.GetSymbolOfCurrentSample()
+            relative_addr = symbol.vaddr_in_file - symbol.symbol_addr
+            self.record_sample(symbol.symbol_name, relative_addr, event.name,
+                               sample.period)
+
+        self.report.Close()
+        logging.info('Analyzed %d event(s) for %d method(s)',
+                     len(self.event_counts), len(self.methods))
+
+    def samples(self) -> Iterator[simpleperf_report_lib.SampleStruct]:
+        """Iterates over samples for compiled methods located in odex files.
+
+        Yields:
+            simpleperf_report_lib.SampleStruct: A sample for a compiled method.
+        """
+        sample = self.report.GetNextSample()
+        while sample:
+            symbol = self.report.GetSymbolOfCurrentSample()
+            if symbol.dso_name.endswith('.odex'):
+                yield sample
+
+            sample = self.report.GetNextSample()
+
+    def record_sample(self, method_name: str, relative_addr: int,
+                      event_name: str, event_count: int) -> None:
+        """Records profiling information given by a sample.
+
+        Args:
+            method_name (str): A method name.
+            relative_addr (int): The relative address of an instruction hit.
+            event_name (str): An event name.
+            event_count (int): An event count.
+        """
+        self.event_counts[event_name] += event_count
+
+        if method_name not in self.methods:
+            self.methods[method_name] = Method(method_name)
+
+        method = self.methods[method_name]
+        method.record_sample(relative_addr, event_name, event_count)
diff --git a/perf2cfg/perf2cfg/edit.py b/perf2cfg/perf2cfg/edit.py
new file mode 100644
index 00000000..ae5c581e
--- /dev/null
+++ b/perf2cfg/perf2cfg/edit.py
@@ -0,0 +1,549 @@
+# Copyright (C) 2020 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.
+"""Classes for annotating a CFG file with profiling information.
+
+Attributes:
+    END_INSTRUCTION_MARKER (str): The marker used to indicate the end of a HIR
+        instruction.
+    EOF_MARKER (str): The marker used to indicate that the end-of-file has been
+        reached.
+"""
+
+import collections
+import enum
+import logging
+import os
+import re
+
+from typing import DefaultDict, Iterator, List, TextIO, Tuple
+
+from perf2cfg import analyze
+from perf2cfg import events
+from perf2cfg import exceptions
+from perf2cfg import parse
+
+END_INSTRUCTION_MARKER = '<|@'
+EOF_MARKER = '<EOF>'
+
+
+class State(enum.Enum):
+    """State represents the internal state of a CfgEditor object."""
+    START = 1
+    PARSE_METHOD_NAME = 2
+    SKIP_METHOD = 3
+    SKIP_TO_CFG = 4
+    START_CFG = 5
+    IS_DISASSEMBLY_PASS = 6
+    SKIP_PASS = 7
+    PARSE_FLAGS = 8
+    SKIP_TO_HIR = 9
+    HIR_INSTRUCTION = 10
+    DISASSEMBLY = 11
+    END_HIR = 12
+    END_BLOCK = 13
+    END_CFG = 14
+    END = 15
+
+
+class CfgEditor:
+    """CfgEditor annotates a CFG file with profiling information.
+
+    CfgEditor does *not* edit the input CFG file in place. Instead, it reads
+    the input file line by line, generates annotations from profiling
+    information, and writes an annotated CFG file to a given path.
+
+    CfgEditor includes a CFG file parser based on a finite state machine. This
+    parser supports CFG files in the c1visualizer format dumped by the ART
+    optimizing compiler:
+        - The CFG file must be valid (correctly parsed by c1visualizer).
+        - Each line must contain only one directive.
+        - Disassembly of an IR instruction must end with the `<|@` marker on a
+          newline.
+
+    Attributes:
+        analyzer (analyzer.RecordAnalyzer): A RecordAnalyzer object.
+        input_stream (TextIO): An input CFG text stream.
+        output_stream (TextIO): An output CFG text stream.
+        primary_event (str): An event used to color basic blocks.
+        basic_block_event_counts (DefaultDict[str, int]): A mapping of event
+            names to their total number of events for the current basic block.
+        buffer (List[str]): A list of strings to be written to the output CFG
+            file instead of the current line from the input CFG file.
+        current_method (analyze.Method): A Method object representing the
+            current method being annotated.
+        event_names (List[str]): A list of sorted event names from the
+            analysis.
+        flags_offset (int): An output file offset pointing to the last flags
+            directive seen.
+        isa (str): The instruction set architecture as defined in the input CFG
+            file metadata, or the string "unknown" if no metadata was found.
+        padding (str): A string used to pad assembly instructions with no
+            profiling information.
+        saved_flags (List[str]): A list of strings representing the flags of
+            the current basic block being parsed.
+        state (State): A State value representing the internal state of the
+            parser.
+    """
+
+    def __init__(self,
+                 analyzer: analyze.RecordAnalyzer,
+                 input_stream: TextIO,
+                 output_stream: TextIO,
+                 primary_event: str = 'cpu-cycles') -> None:
+        """Instantiates a CfgEditor.
+
+        Args:
+            analyzer (analyze.RecordAnalyzer): A RecordAnalyzer object. An
+                analysis must have been completed before passing this object to
+                CfgEditor.
+            input_stream (TextIO): An input CFG text stream.
+            output_stream (TextIO): An output CFG text stream.
+            primary_event (str): An event used to color basic blocks.
+        """
+        self.analyzer = analyzer
+        self.input_stream = input_stream
+        self.output_stream = output_stream
+        self.primary_event = primary_event
+
+        self.basic_block_event_counts: DefaultDict[
+            str, int] = collections.defaultdict(int)
+        self.buffer: List[str] = []
+        self.current_method: analyze.Method
+        self.event_names = events.sort_event_names(self.analyzer.event_counts)
+        self.flags_offset = 0
+        self.isa = ''
+        self.padding = ''
+        self.saved_flags: List[str] = []
+        self.state = State.START
+
+    def edit(self) -> None:
+        """Annotates a CFG file with profiling information."""
+        for lineno, raw_line in self.lines():
+            line = raw_line.strip()
+            try:
+                self.parse_line(line)
+            except exceptions.ArchitectureError as ex:
+                logging.error(ex)
+                return
+            except exceptions.ParseError as ex:
+                logging.error('Line %d: %s', lineno, ex)
+                return
+
+            if self.buffer:
+                self.output_stream.write(''.join(self.buffer))
+                self.buffer = []
+            else:
+                self.output_stream.write(raw_line)
+
+        self.parse_line(EOF_MARKER)
+        if self.state != State.END:
+            logging.error('Unexpected end-of-file while parsing the CFG file')
+
+    def lines(self) -> Iterator[Tuple[int, str]]:
+        """Iterates over lines from the input CFG stream.
+
+        Yields:
+            Tuple[int, str]: A line number and a non-empty line.
+        """
+        for lineno, line in enumerate(self.input_stream, 1):
+            if line:
+                yield lineno, line
+
+    def parse_line(self, line: str) -> None:
+        """Parses a line from the input CFG file.
+
+        Args:
+            line (str): A line to parse.
+
+        Raises:
+            exceptions.ParseError: An error occurred during parsing.
+        """
+        if self.state == State.START:
+            if line == EOF_MARKER:
+                self.state = State.END
+            elif line == 'begin_compilation':
+                self.state = State.PARSE_METHOD_NAME
+            else:
+                raise exceptions.ParseError(
+                    'Expected a `begin_compilation` directive')
+
+        elif self.state == State.PARSE_METHOD_NAME:
+            method_name = parse.parse_name(line)
+            if not self.isa:
+                self.set_isa(method_name)
+
+            if method_name in self.analyzer.methods:
+                self.update_current_method(method_name)
+                self.state = State.SKIP_TO_CFG
+            else:
+                # If no profiling information has been recorded for this
+                # method, skip it
+                self.state = State.SKIP_METHOD
+
+        elif self.state == State.SKIP_METHOD:
+            if line == EOF_MARKER:
+                self.state = State.END
+            elif line == 'begin_compilation':
+                self.state = State.PARSE_METHOD_NAME
+
+        elif self.state == State.SKIP_TO_CFG:
+            if line == 'end_compilation':
+                self.state = State.START_CFG
+
+        elif self.state == State.START_CFG:
+            if line == 'begin_cfg':
+                self.state = State.IS_DISASSEMBLY_PASS
+            else:
+                raise exceptions.ParseError('Expected a `begin_cfg` directive')
+
+        elif self.state == State.IS_DISASSEMBLY_PASS:
+            pass_name = parse.parse_name(line)
+            if pass_name == 'disassembly (after)':
+                self.state = State.PARSE_FLAGS
+            else:
+                self.state = State.SKIP_PASS
+
+        elif self.state == State.SKIP_PASS:
+            if line == 'end_cfg':
+                self.state = State.END_CFG
+
+        elif self.state == State.PARSE_FLAGS:
+            if line.startswith('flags'):
+                self.update_saved_flags(line)
+                self.state = State.SKIP_TO_HIR
+
+        elif self.state == State.SKIP_TO_HIR:
+            if line == 'begin_HIR':
+                self.state = State.HIR_INSTRUCTION
+
+        elif self.state == State.HIR_INSTRUCTION:
+            if line.endswith(END_INSTRUCTION_MARKER):
+                # If no disassembly is available for this HIR instruction, skip
+                # it
+                pass
+            elif line == 'end_HIR':
+                self.state = State.END_HIR
+            else:
+                self.state = State.DISASSEMBLY
+
+        elif self.state == State.DISASSEMBLY:
+            if line == END_INSTRUCTION_MARKER:
+                self.state = State.HIR_INSTRUCTION
+            else:
+                self.annotate_instruction(line)
+
+        elif self.state == State.END_HIR:
+            if line == 'end_block':
+                self.annotate_block()
+                self.state = State.END_BLOCK
+            else:
+                raise exceptions.ParseError('Expected a `end_block` directive')
+
+        elif self.state == State.END_BLOCK:
+            if line == 'begin_block':
+                self.state = State.PARSE_FLAGS
+            elif line == 'end_cfg':
+                logging.info('Annotated %s', self.current_method.name)
+                self.state = State.END_CFG
+            else:
+                raise exceptions.ParseError(
+                    'Expected a `begin_block` or `end_cfg` directive')
+
+        elif self.state == State.END_CFG:
+            if line == EOF_MARKER:
+                self.state = State.END
+            elif line == 'begin_cfg':
+                self.state = State.IS_DISASSEMBLY_PASS
+            elif line == 'begin_compilation':
+                self.state = State.PARSE_METHOD_NAME
+
+    def set_isa(self, metadata: str) -> None:
+        """Sets the instruction set architecture.
+
+        Args:
+            metadata (str): The input CFG file metadata.
+
+        Raises:
+            exceptions.ArchitectureError: An error occurred when the input CFG
+                file ISA is incompatible with the target architecture.
+        """
+        match = re.search(r'isa:(\w+)', metadata)
+        if not match:
+            logging.warning(
+                'Could not deduce the CFG file ISA, assuming it is compatible '
+                'with the target architecture %s', self.analyzer.target_arch)
+            self.isa = 'unknown'
+            return
+
+        self.isa = match.group(1)
+
+        # Map CFG file ISAs to compatible target architectures
+        target_archs = {
+            'x86': [r'x86$', r'x86_64$'],
+            'x86_64': [r'x86_64$'],
+            'arm': [r'armv7', r'armv8'],
+            'arm64': [r'aarch64$', r'armv8'],
+        }
+
+        if not any(
+                re.match(target_arch, self.analyzer.target_arch)
+                for target_arch in target_archs[self.isa]):
+            raise exceptions.ArchitectureError(
+                f'The CFG file ISA {self.isa} is incompatible with the target '
+                f'architecture {self.analyzer.target_arch}')
+
+    def update_current_method(self, method_name: str) -> None:
+        """Updates the current method and the padding string.
+
+        Args:
+            method_name (str): The name of a method being annotated.
+        """
+        self.current_method = self.analyzer.methods[method_name]
+
+        annotations = []
+        for event_name in self.event_names:
+            event_count = self.current_method.event_counts[event_name]
+            annotation = self.generate_method_annotation(
+                event_name, event_count)
+            annotations.append(annotation)
+
+        info = ', '.join(annotations)
+        # By default, c1visualizer displays short method names which are built
+        # by finding the first open parenthesis. To keep that behavior intact,
+        # the profiling information is enclosed in square brackets.
+        directive = parse.build_name(f'[{info}] {method_name}')
+        self.buffer.append(f'{directive}\n')
+
+        max_length = 0
+        for event_name in self.event_names:
+            max_event_count = max(
+                instruction.event_counts[event_name]
+                for instruction in self.current_method.instructions.values())
+            annotation = self.generate_instruction_annotation(
+                event_name, max_event_count)
+
+            if len(annotation) > max_length:
+                max_length = len(annotation)
+
+        self.padding = '_' + ' ' * max_length
+
+    def update_saved_flags(self, line: str) -> None:
+        """Updates the saved flags and saves space for a block annotation.
+
+        Args:
+            line (str): A line containing a flags directive.
+        """
+        self.saved_flags = parse.parse_flags(line)
+        self.flags_offset = self.output_stream.tell()
+
+        flags = self.saved_flags.copy()
+        for event_name in self.event_names:
+            # The current method could have only one basic block, making the
+            # maximum block event counts equal to the method ones
+            event_count = self.current_method.event_counts[event_name]
+            annotation = self.generate_block_annotation(event_name, event_count)
+            flags.append(annotation)
+
+        # Save space for a possible performance flag
+        flags.append('LO')
+
+        padding = ' ' * len(parse.build_flags(flags))
+        self.buffer.append(f'{padding}\n')
+
+    def annotate_block(self) -> None:
+        """Annotates a basic block."""
+        flags = []
+        for event_name in self.event_names:
+            event_count = self.basic_block_event_counts[event_name]
+            annotation = self.generate_block_annotation(event_name, event_count)
+            flags.append(annotation)
+
+        flag = self.generate_performance_flag()
+        if flag:
+            flags.append(flag)
+
+        flags.extend(self.saved_flags)
+
+        self.basic_block_event_counts.clear()
+
+        self.output_stream.seek(self.flags_offset)
+        self.output_stream.write(parse.build_flags(flags))
+        self.output_stream.seek(0, os.SEEK_END)
+
+    def annotate_instruction(self, line: str) -> None:
+        """Annotates an instruction.
+
+        Args:
+            line (str): A line containing an instruction to annotate.
+        """
+        addr = parse.parse_address(line)
+
+        instruction = self.current_method.instructions.get(addr)
+        if not instruction:
+            # If no profiling information has been recorded for this
+            # instruction, skip it
+            self.buffer.append(f'{self.padding}{line}\n')
+            return
+
+        for eventno, event_name in enumerate(self.event_names):
+            event_count = instruction.event_counts[event_name]
+            self.basic_block_event_counts[event_name] += event_count
+            annotation = self.generate_padded_instruction_annotation(
+                event_name, event_count)
+
+            if eventno:
+                self.buffer.append(f'{annotation}\n')
+            else:
+                self.buffer.append(f'{annotation} {line}\n')
+
+    def generate_performance_flag(self) -> str:
+        """Generates a performance flag for the current basic block.
+
+        For example, a `LO` (low) flag indicates the block is responsible for 1
+        to 10% of the current method primary event (cpu-cycles by default).
+
+        Returns:
+            str: A performance flag, or an empty string if the block
+                contribution is not high enough.
+        """
+        ranges = [
+            # Low
+            (1, 10, 'LO'),
+            # Moderate
+            (10, 30, 'MO'),
+            # Considerable
+            (30, 50, 'CO'),
+            # High
+            (50, 101, 'HI'),
+        ]
+
+        ratio = 0
+        method_event_count = self.current_method.event_counts[
+            self.primary_event]
+        if method_event_count:
+            ratio = int(self.basic_block_event_counts[self.primary_event] /
+                        method_event_count * 100)
+
+        for start, end, name in ranges:
+            if start <= ratio < end:
+                return name
+
+        return ''
+
+    def generate_padded_instruction_annotation(self, event_name: str,
+                                               event_count: int) -> str:
+        """Generates a padded instruction annotation.
+
+        Args:
+            event_name (str): An event name.
+            event_count (int): An event count.
+
+        Returns:
+            str: A padded instruction annotation.
+        """
+        annotation = self.generate_instruction_annotation(
+            event_name, event_count)
+
+        # Remove one from the final length as a space may be added at the end
+        # of the annotation. The final length will always be positive as the
+        # length of the current padding is one more than the length of the
+        # longest annotation for the current method.
+        padding = ' ' * (len(self.padding) - len(annotation) - 1)
+        parts = annotation.split(':')
+
+        return f'{parts[0]}:{padding}{parts[1]}'
+
+    def generate_method_annotation(self, event_name: str,
+                                   event_count: int) -> str:
+        """Generates a method annotation.
+
+        Method annotations are relative to the whole analysis and exclude the
+        event count.
+
+        Args:
+            event_name (str): An event name.
+            event_count (int): An event count.
+
+        Returns:
+            str: A method annotation.
+        """
+        total_event_count = self.analyzer.event_counts[event_name]
+        return self.generate_annotation(event_name,
+                                        event_count,
+                                        total_event_count,
+                                        include_count=False)
+
+    def generate_block_annotation(self, event_name: str,
+                                  event_count: int) -> str:
+        """Generates a basic block annotation.
+
+        Basic block annotations are relative to the current method and exclude
+        the event count.
+
+        Args:
+            event_name (str): An event name.
+            event_count (int): An event count.
+
+        Returns:
+            str: A basic block annotation.
+        """
+        total_event_count = self.current_method.event_counts[event_name]
+        return self.generate_annotation(event_name,
+                                        event_count,
+                                        total_event_count,
+                                        include_count=False)
+
+    def generate_instruction_annotation(self, event_name: str,
+                                        event_count: int) -> str:
+        """Generates an instruction annotation.
+
+        Instruction annotations are relative to the current method and include
+        the event count.
+
+        Args:
+            event_name (str): An event name.
+            event_count (int): An event count.
+
+        Returns:
+            str: An instruction annotation.
+        """
+        total_event_count = self.current_method.event_counts[event_name]
+        return self.generate_annotation(event_name,
+                                        event_count,
+                                        total_event_count,
+                                        include_count=True)
+
+    # pylint: disable=no-self-use
+    def generate_annotation(self, event_name: str, event_count: int,
+                            total_event_count: int, include_count: bool) -> str:
+        """Generates an annotation.
+
+        Args:
+            event_name (str): An event name.
+            event_count (int): An event count.
+            total_event_count (int): A total event count.
+            include_count (bool): If True, includes the event count alongside
+                the event name and ratio.
+
+        Returns:
+            str: An annotation.
+        """
+        ratio = 0.0
+        if total_event_count:
+            ratio = event_count / total_event_count
+
+        if include_count:
+            return f'{event_name}: {event_count} ({ratio:.2%})'
+
+        return f'{event_name}: {ratio:06.2%}'
diff --git a/perf2cfg/perf2cfg/events.py b/perf2cfg/perf2cfg/events.py
new file mode 100644
index 00000000..ecc5d90a
--- /dev/null
+++ b/perf2cfg/perf2cfg/events.py
@@ -0,0 +1,53 @@
+# Copyright (C) 2020 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.
+"""Sorts event names according to a predefined order.
+
+Attributes:
+    EVENT_SORT_ORDER (List[str]): A list of event names sorted as they should
+        appear in the output CFG file.
+    EVENT_SORT_MAP (Dict[str, int]): A mapping of event names to their index in
+        the event sort order list.
+"""
+
+from typing import Iterable, List
+
+EVENT_SORT_ORDER = [
+    'cpu-cycles',
+    'stalled-cycles-frontend',
+    'stalled-cycles-backend',
+    'instructions',
+    'branch-instructions',
+    'branch-misses',
+    'cache-references',
+    'cache-misses',
+    'task-clock',
+    'context-switches',
+    'page-faults',
+]
+
+EVENT_SORT_MAP = {name: i for i, name in enumerate(EVENT_SORT_ORDER)}
+
+
+def sort_event_names(event_names: Iterable[str]) -> List[str]:
+    """Sorts event names according to a predefined order.
+
+    Args:
+        event_names (Iterable[str]): An iterable of event names.
+
+    Returns:
+        List[str]: A list of sorted event names.
+    """
+    default_index = len(EVENT_SORT_MAP)
+    return sorted(event_names,
+                  key=lambda name: EVENT_SORT_MAP.get(name, default_index))
diff --git a/perf2cfg/perf2cfg/exceptions.py b/perf2cfg/perf2cfg/exceptions.py
new file mode 100644
index 00000000..94a48dc2
--- /dev/null
+++ b/perf2cfg/perf2cfg/exceptions.py
@@ -0,0 +1,24 @@
+# Copyright (C) 2020 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.
+"""Custom exception classes."""
+
+
+class ArchitectureError(Exception):
+    """ArchitectureError is raised when at least two input files were created
+    on systems with different architectures.
+    """
+
+
+class ParseError(Exception):
+    """ParseError is raised when a CFG parsing error occurs."""
diff --git a/perf2cfg/perf2cfg/parse.py b/perf2cfg/perf2cfg/parse.py
new file mode 100644
index 00000000..9e211bef
--- /dev/null
+++ b/perf2cfg/perf2cfg/parse.py
@@ -0,0 +1,131 @@
+# Copyright (C) 2020 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.
+"""Functions to build and parse directives from CFG files."""
+
+import re
+
+from typing import Iterable, List
+
+from perf2cfg import exceptions
+
+
+def build_flags(flags: Iterable[str]) -> str:
+    """Builds a flags directive from a list of arguments.
+
+    Args:
+        flags (Iterable[str]): An iterable of flags.
+
+    Returns:
+        str: A flags directive with the given arguments.
+
+    Examples:
+        >>> parse_flags(['catch_block', 'critical'])
+        '    flags "catch_block" "critical"'
+    """
+    if not flags:
+        return '    flags'
+
+    args = ' '.join(f'"{flag}"' for flag in flags)
+    return f'    flags {args}'
+
+
+def build_name(name: str) -> str:
+    """Builds a name directive from an argument.
+
+    Args:
+        name (str): An argument.
+
+    Returns:
+        str: A name directive with the given argument.
+    """
+    return f'  name "{name}"'
+
+
+def parse_address(line: str) -> int:
+    """Parses an address from a line.
+
+    Args:
+        line (str): A line to parse an address from.
+
+    Returns:
+        int: An instruction address.
+
+    Raises:
+        exceptions.ParseError: An error occurred during parsing.
+
+    Examples:
+        >>> parse_address('0x0000001c: d503201f nop')
+        28
+    """
+    parts = line.split(':', 1)
+    addr = parts[0]
+
+    try:
+        return int(addr, 16)
+    except ValueError:
+        raise exceptions.ParseError('Expected an address')
+
+
+def parse_flags(line: str) -> List[str]:
+    """Parses a flags directive from a line.
+
+    Args:
+        line (str): A line to parse a flags directive from.
+
+    Returns:
+        List[str]: A list of unquoted arguments from a flags directive, or an
+            empty list if no arguments were found.
+
+    Raises:
+        exceptions.ParseError: An error occurred during parsing.
+
+    Example:
+        >>> parse_flags('flags "catch_block" "critical"')
+        ['catch_block', 'critical']
+    """
+    parts = line.split(None, 1)
+    if parts[0] != 'flags':
+        raise exceptions.ParseError('Expected a `flags` directive')
+
+    if len(parts) < 2:
+        return []
+
+    return re.findall(r'\"([^\"]+)\"', parts[1])
+
+
+def parse_name(line: str) -> str:
+    """Parses a name directive from a line.
+
+    Args:
+        line (str): A line to parse a name directive from.
+
+    Returns:
+        str: The unquoted argument of a name directive.
+
+    Raises:
+        exceptions.ParseError: An error occurred during parsing.
+
+    Examples:
+        >>> parse_name('name "disassembly (after)"')
+        'disassembly (after)'
+    """
+    parts = line.split(None, 1)
+    if parts[0] != 'name':
+        raise exceptions.ParseError('Expected a `name` directive')
+
+    if len(parts) < 2:
+        raise exceptions.ParseError(
+            'Expected an argument to the `name` directive')
+
+    return parts[1].strip('"')
diff --git a/perf2cfg/perf2cfg_test.py b/perf2cfg/perf2cfg_test.py
new file mode 100755
index 00000000..d99559b7
--- /dev/null
+++ b/perf2cfg/perf2cfg_test.py
@@ -0,0 +1,20 @@
+#!/usr/bin/env python3
+# Copyright (C) 2020 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.
+
+import unittest
+
+if __name__ == '__main__':
+    # Setting module to None enables test discovery
+    unittest.main(module=None, verbosity=2)
diff --git a/perf2cfg/pylintrc b/perf2cfg/pylintrc
new file mode 100644
index 00000000..7c9f3f33
--- /dev/null
+++ b/perf2cfg/pylintrc
@@ -0,0 +1,17 @@
+# Reference: https://pylint.pycqa.org/en/latest/technical_reference/features.html
+[MASTER]
+
+load-plugins=pylint.extensions.docparams
+
+
+[MESSAGES CONTROL]
+
+disable=design
+
+
+[PARAMETER_DOCUMENTATION]
+
+accept-no-param-doc=no
+accept-no-raise-doc=no
+accept-no-return-doc=no
+accept-no-yields-doc=no
diff --git a/perf2cfg/tests/__init__.py b/perf2cfg/tests/__init__.py
new file mode 100644
index 00000000..c1b565d3
--- /dev/null
+++ b/perf2cfg/tests/__init__.py
@@ -0,0 +1,13 @@
+# Copyright (C) 2020 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.
diff --git a/perf2cfg/tests/test_edit.py b/perf2cfg/tests/test_edit.py
new file mode 100644
index 00000000..4602c02f
--- /dev/null
+++ b/perf2cfg/tests/test_edit.py
@@ -0,0 +1,144 @@
+# Copyright (C) 2020 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.
+import io
+import textwrap
+import unittest
+
+from perf2cfg import analyze
+from perf2cfg import edit
+
+
+def empty_analyzer():
+    return analyze.RecordAnalyzer()
+
+
+def populated_analyzer():
+    analyzer = analyze.RecordAnalyzer()
+    analyzer.target_arch = 'aarch64'
+    samples = [
+        ('void hcf()', 4, 'cpu-cycles', 90),
+        ('void hcf()', 8, 'cpu-cycles', 10),
+        ('void hcf()', 8, 'cache-misses', 100),
+    ]
+
+    for sample in samples:
+        analyzer.record_sample(*sample)
+
+    return analyzer
+
+
+def edit_string(analyzer, input_string):
+    input_stream = io.StringIO(input_string)
+    output_stream = io.StringIO()
+
+    editor = edit.CfgEditor(analyzer, input_stream, output_stream)
+    editor.edit()
+
+    return output_stream
+
+
+class TestEdit(unittest.TestCase):
+
+    def test_empty_file(self):
+        output_stream = edit_string(empty_analyzer(), '')
+        self.assertEqual(output_stream.getvalue(), '')
+
+    def test_wrong_filetype(self):
+        with self.assertLogs() as ctx:
+            edit_string(
+                empty_analyzer(), """<!DOCTYPE html>
+                <html>
+                <head>
+                  <title>I'm not a CFG file</title>
+                </head>
+                </html>""")
+
+        self.assertEqual(
+            ctx.output,
+            ['ERROR:root:Line 1: Expected a `begin_compilation` directive'])
+
+    def test_no_architecture(self):
+        with self.assertLogs() as ctx:
+            edit_string(
+                populated_analyzer(), """begin_compilation
+                  name "void noMetadata()"
+                end_compilation""")
+
+        self.assertEqual(ctx.output, [
+            'WARNING:root:Could not deduce the CFG file ISA, assuming it is '
+            'compatible with the target architecture aarch64'
+        ])
+
+    def test_wrong_architecture(self):
+        with self.assertLogs() as ctx:
+            edit_string(
+                populated_analyzer(), """begin_compilation
+                  name "isa:x86_64"
+                end_compilation""")
+
+        self.assertEqual(ctx.output, [
+            'ERROR:root:The CFG file ISA x86_64 is incompatible with the '
+            'target architecture aarch64'
+        ])
+
+    def test_annotate_method(self):
+        with self.assertLogs() as ctx:
+            output_stream = edit_string(
+                populated_analyzer(),
+                textwrap.dedent("""\
+                    begin_compilation
+                      name "isa:arm64 isa_features:a53,crc,-lse,-fp16,-dotprod,-sve"
+                    end_compilation
+                    begin_compilation
+                      name "void hcf()"
+                    end_compilation
+                    begin_cfg
+                      name "disassembly (after)"
+                      begin_block
+                        flags
+                        begin_HIR
+                          0 0 NOPSlide dex_pc:0 loop:none
+                          0x00000000: d503201f nop
+                          0x00000004: d503201f nop
+                          0x00000008: d503201f nop
+                          <|@
+                        end_HIR
+                      end_block
+                    end_cfg"""))
+
+        self.assertEqual(ctx.output, ['INFO:root:Annotated void hcf()'])
+        self.assertEqual(
+            output_stream.getvalue(),
+            textwrap.dedent("""\
+                begin_compilation
+                  name "isa:arm64 isa_features:a53,crc,-lse,-fp16,-dotprod,-sve"
+                end_compilation
+                begin_compilation
+                  name "[cpu-cycles: 100.00%, cache-misses: 100.00%] void hcf()"
+                end_compilation
+                begin_cfg
+                  name "disassembly (after)"
+                  begin_block
+                    flags "cpu-cycles: 100.00%" "cache-misses: 100.00%" "HI"
+                    begin_HIR
+                      0 0 NOPSlide dex_pc:0 loop:none
+                _                           0x00000000: d503201f nop
+                cpu-cycles:     90 (90.00%) 0x00000004: d503201f nop
+                cache-misses:     0 (0.00%)
+                cpu-cycles:     10 (10.00%) 0x00000008: d503201f nop
+                cache-misses: 100 (100.00%)
+                      <|@
+                    end_HIR
+                  end_block
+                end_cfg"""))
diff --git a/perf2cfg/tests/test_events.py b/perf2cfg/tests/test_events.py
new file mode 100644
index 00000000..9cdcdf5a
--- /dev/null
+++ b/perf2cfg/tests/test_events.py
@@ -0,0 +1,27 @@
+# Copyright (C) 2020 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.
+import random
+import unittest
+
+from perf2cfg import events
+
+
+class TestEvents(unittest.TestCase):
+
+    def test_sort_event_names(self):
+        event_names = events.EVENT_SORT_ORDER.copy()
+        random.shuffle(event_names)
+        got = events.sort_event_names(event_names)
+
+        self.assertEqual(got, events.EVENT_SORT_ORDER)
diff --git a/perf2cfg/tests/test_parse.py b/perf2cfg/tests/test_parse.py
new file mode 100644
index 00000000..40ec243b
--- /dev/null
+++ b/perf2cfg/tests/test_parse.py
@@ -0,0 +1,73 @@
+# Copyright (C) 2020 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.
+import unittest
+
+from perf2cfg import exceptions
+from perf2cfg import parse
+
+
+class TestParse(unittest.TestCase):
+
+    def test_build_flags_without_arguments(self):
+        got = parse.build_flags([])
+        self.assertEqual(got.strip(), 'flags')
+
+    def test_build_flags_with_arguments(self):
+        got = parse.build_flags(['catch_block', 'critical'])
+        self.assertEqual(got.strip(), 'flags "catch_block" "critical"')
+
+    def test_build_name(self):
+        got = parse.build_name('void hcf()')
+        self.assertEqual(got.strip(), 'name "void hcf()"')
+
+    def test_parse_invalid_address_line(self):
+        with self.assertRaises(exceptions.ParseError) as ctx:
+            parse.parse_address(':)')
+
+        self.assertEqual(str(ctx.exception), 'Expected an address')
+
+    def test_parse_valid_address_line(self):
+        got = parse.parse_address('0x0000001c: d503201f nop')
+        self.assertEqual(got, 0x1c)
+
+    def test_parse_flags_wrong_directive(self):
+        with self.assertRaises(exceptions.ParseError) as ctx:
+            parse.parse_flags('name "void hcf()"')
+
+        self.assertEqual(str(ctx.exception), 'Expected a `flags` directive')
+
+    def test_parse_flags_without_arguments(self):
+        got = parse.parse_flags('flags')
+        self.assertEqual(got, [])
+
+    def test_parse_flags_with_arguments(self):
+        got = parse.parse_flags('flags "catch_block" "critical"')
+        self.assertEqual(got, ['catch_block', 'critical'])
+
+    def test_parse_name_wrong_directive(self):
+        with self.assertRaises(exceptions.ParseError) as ctx:
+            parse.parse_name('flags "catch_block" "critical"')
+
+        self.assertEqual(str(ctx.exception), 'Expected a `name` directive')
+
+    def test_parse_name_without_argument(self):
+        with self.assertRaises(exceptions.ParseError) as ctx:
+            parse.parse_name('name')
+
+        self.assertEqual(str(ctx.exception),
+                         'Expected an argument to the `name` directive')
+
+    def test_parse_name_with_argument(self):
+        got = parse.parse_name('name "void hcf()"')
+        self.assertEqual(got, 'void hcf()')