tools/binary_size/libsupersize/bcanalyzer.py

#!/usr/bin/env python3
# Copyright 2018 The Chromium Authors
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

"""Runs bcanalyzer to extract data from LLVM Bitcode (BC) files.

IsBitcodeFile():
  Reads the magic header of a file to quickly decide whether it is a BC file.

ParseTag():
  Heuristically parses a single-line tag from bcanalyzer dump (exporeted for
  testing).

RunBcAnalyzerOnIntermediates():
  BulkForkAndCall() target: Given BC file [paths], runs (llvm-)bcanalyzer on
  each path, parses the output, extracts strings, and returns {path: [strings]}.

This file can also be run stand-alone in order to test out the logic on smaller
sample sizes.
"""

import argparse
import os
import re
import subprocess

import parallel
import path_util


# Upper bound on number of bytes per character in strings. 4-byte / 32-bit
# strings are rare and are likely confused with 32-bit int arrays. So by
# default, only accept up to 2-byte / 16-bit strings.
_CHAR_WIDTH_LIMIT = 2

_RE_SPLIT = re.compile(r'=(\d+)')
# <TYPE_BLOCK_ID> children tags that should not be counted as types.
# - <NUMENTRY> is meta data.
# - <STRUCT_NAME> with the following <STRUCT_NAMED> (or other tag) are counted
#   as a single type entry.
_NON_TYPE_TAGS = set(['NUMENTRY', 'STRUCT_NAME'])

# Use bit-fields for tag types: 1 => Opening tag, 2 => Closed tag.
OPENING_TAG = 1
CLOSING_TAG = 2
SELF_CLOSING_TAG = OPENING_TAG | CLOSING_TAG


def _IsOpeningTag(tag_type):
  return tag_type & 1


def _IsClosingTag(tag_type):
  return tag_type & 2


def IsBitcodeFile(path):
  try:
    with open(path, 'rb') as f:
      return f.read(4) == b'BC\xc0\xde'
  except IOError:
    return False


def ParseTag(line):
  """Heuristically parses a single-line tag from bcanalyzer dump.

  Since input data are machine-generated, so we only need "good enough" parsing
  logic that favors simplicity. For example, '</FOO/>' is accepted.

  Args:
    line: Stripped line that may have a single-line tag with trailing text.

  Returns:
    (tag_type, tag, attrib_pos) if successful, else (None) * 3. Details:
    tag_type: One of {OPENING_TAG, CLOSING_TAG, SELF_CLOSING_TAG}.
    tag: The tag name.
    attrib_pos: Position in |line| to start parsing attributes.
  """
  # <TYPE_BLOCK_ID NumWords=103 BlockCodeSize=4>
  #     ==> (OPENING_TAG, 'TYPE_BLOCK_ID', 14).
  # <ARRAY abbrevid=9 op0=1 op1=7/> Trailing text!
  #     ==> (SELF_CLOSING_TAG, 'ARRAY', 6).
  # </TYPE_BLOCK_ID>
  #     ==> (CLOSING_TAG, 'TYPE_BLOCK_ID', 15).

  # Assumes |line| is stripped, i.e., so no indent and no trailing new line.
  if len(line) < 2 or line[0] != '<':
    return (None, None, None)
  tag_type, pos = (CLOSING_TAG, 2) if line[1] == '/' else (OPENING_TAG, 1)
  for i in range(pos, len(line)):
    if not line[i].isalnum() and line[i] != '_':
      if i == pos or not line[i] in ' >/':
        break
      end = line.find('>', i)
      if end < 0:
        break
      if line[end - 1] == '/':
        return (SELF_CLOSING_TAG, line[pos:i], i)
      return (tag_type, line[pos:i], i)
  return (None, None, None)


def _ParseOpItems(line, pos):
  """Heuristically extracts op0=# op1=# ... values from a single-line tag."""
  # <SETTYPE abbrevid=4 op0=42/>
  #         ^ pos = 8
  #     ==> iter([42]).
  # <CSTRING abbrevid=11 op0=84 op1=101 op2=115 op3=116 op4=56 op5=97/>
  #         ^ pos = 8
  #     ==> iter([84, 101, 115, 116, 56, 97]).
  # <STRING abbrevid=9 op0=1 op1=0 op2=0 op3=1 op4=1 op5=0/>
  #        ^ pos = 7
  #     ==> iter([1, 0, 0, 1, 1, 0]).
  # <DATA op0=8412 op1=101 op2=1150 op3=116 op4=5200 op5=98 op6=0/>
  #      ^ pos = 5
  #     ==> iter([8412, 101, 1150, 116, 5200, 98, 0]).

  # In particular, skip 'abbrevid=#'.
  start = line.index(' op', pos)
  end = line.index('>', start)
  for t in _RE_SPLIT.finditer(line[start:end]):
    yield int(t.group(1))


# Emits uint16 values as a stream of 2 bytes (little-endian).
def _UnpackUint16ListToBytes(items):
  for item in items:
    yield item & 0xFF
    yield (item >> 8) & 0xFF


# Emits uint32 values as a stream of 4 bytes (little-endian).
def _UnpackUint32ListToBytes(items):
  for item in items:
    yield item & 0xFF
    yield (item >> 8) & 0xFF
    yield (item >> 16) & 0xFF
    yield (item >> 24) & 0xFF


class _BcIntArrayType:
  """The specs of an integer array type."""

  # Lookup table to map from width to an unpacker that splits ints into bytes.
  _UNPACKER_MAP = {
    1: iter,
    2: _UnpackUint16ListToBytes,
    4: _UnpackUint32ListToBytes
  }

  def __init__(self, length, width):
    # Number of elements in the array.
    self.length = length
    # Number of bytes per element.
    self.width = width

  def ParseOpItemsAsBytes(self, line, attrib_pos, add_null_at_end):
    """Reads op0=# op=# ... values and returns them as a list of bytes.

    Interprets each op0=# op1=# ... value as a |self.width|-byte integer, splits
    them into component bytes (little-endian), and returns the result as string.

    Args:
      line: Stripped line of single-line tag with op0=# op1=# ... data.
      attrib_pos: Position in |line| where attribute list starts.
      add_null_add_end: Whether to append |'\x00' * self.width|.
    """
    items = _ParseOpItems(line, attrib_pos)
    unpacker = _BcIntArrayType._UNPACKER_MAP[self.width]
    s = bytes(unpacker(items))
    if add_null_at_end:
      s += b'\x00' * self.width
    # Rather stringent check to ensure exact size match.
    assert len(s) == self.length * self.width
    return s


class _BcTypeInfo:
  """Stateful parser of <TYPE_BLOCK_ID>, specialized for integer arrays."""

  # <TYPE_BLOCK_ID NumWords=103 BlockCodeSize=4>
  #   <NUMENTRY op0=9/>                  # Type ids should be in [0, 8].
  #   <INTEGER op0=8/>                   # Type id = 0: int8.
  #   <POINTER abbrevid=4 op0=0 op1=0/>  # Type id = 1: Pointer to type id 0
  #                                      #    ==> int8*.
  #   <ARRAY abbrevid=9 op0=4 op1=0/>    # Type id = 2: Array with 4 elements
  #                                      # of type id 0 ==> int8[4]
  #   <STRUCT_NAME op0=115 op1=116 op2=114/>  # Joins next Tag.
  #   <STRUCT_NAMED abbrevid=8 op0=0 op1=1/>  # Type id = 3: Struct (unused).
  #   <FUNCTION abbrevid=5 op0=0 op1=12/>  # Type id = 4: Function (unused).
  #   <INTEGER op0=16/>                  # Type id = 5: int16.
  #   <POINTER abbrevid=4 op0=5 op1=0/>  # Type id = 6: Pointer to type id 5
  #                                      #    ==> int16*.
  #   <INTEGER op0=32/>                  # Type id = 7: int32.
  #   <ARRAY abbrevid=9 op0=5 op1=4/>    # Type id = 8: Array with 4 elements
  #                                      # of type id 5 ==> int16[4]
  # <TYPE_BLOCK_ID>

  def __init__(self):
    # Auto-incrementing current type id.
    self.cur_type_id = 0
    # Maps from type id (of an integer) to number of bits.
    self.int_types = {}
    # Maps from type id (of an integer array) to _BcIntArrayType.
    self.int_array_types = {}

  def Feed(self, line, tag, attrib_pos):
    """Parses a single-line tag and store integer and integer array types.

    Args:
      line: Stripped line of single-line tag with op0=# op1=# ... data.
      tag: The tag type in |line| (child tag of <TYPE_BLOCK_ID>).
      attrib_pos: Position in |line| where attribute list starts.
    """
    if tag in _NON_TYPE_TAGS:
      return
    if tag == 'INTEGER':
      num_bits = next(_ParseOpItems(line, attrib_pos))  # op0.
      self.int_types[self.cur_type_id] = num_bits
    elif tag == 'ARRAY':
      [size, item_type_id] = list(_ParseOpItems(line, attrib_pos))  # op0, op1.
      bits = self.int_types.get(item_type_id)
      if bits is not None:  # |bits| can be None for non-int arrays.
        self.int_array_types[self.cur_type_id] = _BcIntArrayType(
            size, bits // 8)
    self.cur_type_id += 1

  def GetArrayType(self, idx):
    return self.int_array_types.get(idx)


def _ParseBcAnalyzer(lines):
  """A generator to extract bytes() from bcanalyzer dump of a BC file."""

  # ...
  # <TYPE_BLOCK_ID NumWords=103 BlockCodeSize=4>
  #    ... (See above; parsed by _BcTypeInfo)
  # <TYPE_BLOCK_ID>
  # ...
  # <CONSTANTS_BLOCK NumWords=93 BlockCodeSize=4>
  #   <SETTYPE abbrevid=4 op0=1/>  # Current type id := 1 ==> int8*.
  #   <CE_INBOUNDS_GEP op0=3 op1=4 op2=1 op3=12 op4=57 op5=12 op6=57/>
  #   <SETTYPE abbrevid=4 op0=2/>  # Current type id := 2 ==> int8[4].
  #   <CSTRING abbrevid=11 op0=70 op1=111 op2=111/> record string = 'Foo'
  #   <STRING abbrevid=11 op0=70 op1=111 op2=111 op3=1/>  # {'F','o','o',1}.
  #   <SETTYPE abbrevid=6 op0=7/>    # Current type id := 7 ==> int32.
  #   <INTEGER abbrevid=5 op0=2000/> # Stores 1000.
  #   <INTEGER abbrevid=5 op0=2001/> # Stores -1000.
  #   <SETTYPE abbrevid=4 op0=8/>    # Current type id := 8 ==> int16[4].
  #   <NULL/>
  #   <DATA abbrevid=11 op0=8400 op1=10100 op2=11500 op3=0/>
  # </CONSTANTS_BLOCK>
  # ...

  # Notes:
  # - Only parse first <TYPE_BLOCK_ID> and first <CONSTANTS_BLOCK>.
  # - <CONSTANTS_BLOCK> is stateful: A "current type id" exists, and that's set
  #   by <SETTYPE>, with op0= referring to type id.
  #   - For array lengths one needs to refer to the corresponding <ARRAY>.
  # - Strings / arrays are in <CSTRING>, <STRING>, and <DATA>.
  #   - abbrevid=# is redundant (repeats tag type) and unused
  #   - Character data are stored in op0=# op1=# ..., one per character. These
  #     values should fit in the proper range, and can be fairly large.
  #   - <CSTRING> has implicit 0 at end.
  #   - Data lengths agree with the length in the matching <ARRAY> entry.
  #   - "record string" text is not very useful: It only appears if all
  #     characters are printable.
  # - Signed vs. unsigned types are undistinguished.
  #   - In <INTEGER>, the op0= value is stored as 2 * abs(x) + (signed ? 0 : 1).
  #   - In <ARRAY> of int, values are coerced to unsigned type.
  # - Strings and int arrays are undistinguished.
  #   - <CSTRING>: If an uint8 array happens to end with 0, then this gets used!
  # - Arrays (or integers) of all-0 appear as <NULL/>. Presumably this gets
  #   placed into .bss section.

  STATE_VOID = 0
  STATE_TYPE_BLOCK = 1
  STATE_CONST_BLOCK = 2
  state = STATE_VOID

  type_info = None
  consts_cur_type = None

  # State machine to parse the *first* <TYPE_BLOCK_ID> to initialize
  # |type_info|, then the *first* <CONSTANTS_BLOCK> to yield strings.
  for line in lines:
    line = line.lstrip()
    (tag_type, tag, attrib_pos) = ParseTag(line)
    if tag_type is None:
      continue
    if state == STATE_VOID:
      if _IsOpeningTag(tag_type):
        if tag == 'TYPE_BLOCK_ID':
          if type_info is None:
            state = STATE_TYPE_BLOCK
            type_info = _BcTypeInfo()
        elif tag == 'CONSTANTS_BLOCK':
          if type_info is not None:
            state = STATE_CONST_BLOCK

    elif state == STATE_TYPE_BLOCK:
      if _IsClosingTag(tag_type) and tag == 'TYPE_BLOCK_ID':
        state = STATE_VOID
      else:
        type_info.Feed(line, tag, attrib_pos)

    elif state == STATE_CONST_BLOCK:
      if _IsClosingTag(tag_type) and tag == 'CONSTANTS_BLOCK':
        # Skip remaining data, including subsequent <CONSTANTS_BLOCK>s.
        break
      if tag == 'SETTYPE':
        try:
          consts_cur_type_id = next(_ParseOpItems(line, attrib_pos))  # op0.
        except StopIteration:
          return
        consts_cur_type = type_info.GetArrayType(consts_cur_type_id)
      elif consts_cur_type and consts_cur_type.width <= _CHAR_WIDTH_LIMIT:
        if tag in ['CSTRING', 'STRING', 'DATA']:
          # Exclude 32-bit / 4-byte strings since they're rarely used, and are
          # likely confused with 32-bit int arrays.
          s = consts_cur_type.ParseOpItemsAsBytes(line, attrib_pos,
                                                  tag == 'CSTRING')
          yield (consts_cur_type, s)


class _BcAnalyzerRunner:
  """Helper to run bcanalyzer and extract output lines. """

  def __init__(self, output_directory):
    self._args = [
        path_util.GetBcAnalyzerPath(), '--dump', '--disable-histogram'
    ]
    self._output_directory = output_directory

  def RunOnFile(self, obj_file):
    output = subprocess.check_output(
        self._args + [obj_file], cwd=self._output_directory).decode('ascii')
    return output.splitlines()


# This is a target for BulkForkAndCall().
def RunBcAnalyzerOnIntermediates(target, output_directory):
  """Calls bcanalyzer and returns encoded map from path to strings.

  Args:
    target: A list of BC file paths.
  """
  assert isinstance(target, list)
  runner = _BcAnalyzerRunner(output_directory)
  strings_by_path = {}
  for t in target:
    strings_by_path[t] = [s for _, s in _ParseBcAnalyzer(runner.RunOnFile(t))]
  # Escape strings by repr() so there will be no special characters to interfere
  # parallel.EncodeDictOfLists() and decoding.
  return parallel.EncodeDictOfLists(strings_by_path, value_transform=repr)


def main():
  parser = argparse.ArgumentParser()
  parser.add_argument('--output-directory', default='.')
  parser.add_argument('--char-width-limit', type=int)
  parser.add_argument('objects', type=os.path.realpath, nargs='+')

  args = parser.parse_args()
  base_path = os.path.normpath(args.output_directory)
  runner = _BcAnalyzerRunner(args.output_directory)
  if args.char_width_limit is not None:
    global _CHAR_WIDTH_LIMIT
    _CHAR_WIDTH_LIMIT = args.char_width_limit

  for obj_path in args.objects:
    rel_path = os.path.relpath(obj_path, base_path)
    print('File: %s' % rel_path)
    for cur_type, s in _ParseBcAnalyzer(runner.RunOnFile(obj_path)):
      print('    char%d[%d]: %r' % (cur_type.width * 8, cur_type.length, s))
    print('')


if __name__ == '__main__':
  main()