openpower/sv/estimate-compression.py

   1 #! /bin/env python3
   2 # see https://bugs.libre-soc.org/show_bug.cgi?id=532
   3
   4 # Estimate ppc code compression with Libre-SOC encoding attempt v2.
   5
   6
   7 # Copyright 2020 Alexandre Oliva
   8 # Copyright 2020 Luke Kenneth Casson Leighton
   9
  10 # This script is free software; you can redistribute it and/or modify
  11 # it under the terms of the GNU General Public License as published by
  12 # the Free Software Foundation; either version 3, or (at your option)
  13 # any later version.
  14
  15 # This script is distributed in the hope that it will be useful, but
  16 # WITHOUT ANY WARRANTY; without even the implied warranty of
  17 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18 # General Public License for more details.
  19
  20 # You should have received a copy of the GNU General Public License
  21 # along with this script; see the file COPYING3.  If not see
  22 # <http://www.gnu.org/licenses/>.
  23
  24 # Skeleton originally by Alexandre Oliva <oliva@gnu.org>.
  25
  26
  27 # Feed this script the output of objdump -M raw --no-show-raw-insn ppc-prog
  28
  29 # It will look for insns that can be represented in compressed mode,
  30 # according to the encoding rules in the copcond dictionary below.
  31 # Nothing is assumed as to the actual bit-encoding of the insns, this
  32 # is just to experiment with insn selection and get a quick feedback
  33 # loop for the encoding options in compressed mode.
  34
  35 # In this script, the computations of encoding modes and transitions
  36 # are tuned for the simpler model that uses 1-byte nops for
  37 # transitions in and out of compressed mode, placing compressed-mode
  38 # insns at odd addresses.  At (visible) entry points, mode is forced
  39 # to return to uncompressed mode.
  40
  41 # The entire code stream is printed, without any attempt to modify the
  42 # addresses that go along with or in them; we only insert markers for
  43 # the transition points, and for the compressed instructions.
  44
  45 # The really useful information is printed at the end: a summary of
  46 # transition and compressed-insn counts, and the achieved compression
  47 # rate.
  48
  49 import sys
  50 import re
  51
  52 insn = re.compile('\s+(?P<addr>[0-9a-f]+):\s+(?P<opcode>[^ ]+) *(?P<operands>.*)')
  53
  54 opkind = re.compile('(?P<reg>(?P<regkind>[cf]?r)(?P<regnum>[0-9]+))|(?P<immediate>-?[0-9]+)|(?P<branch>[0-9a-f]+)(?: <.*>)?|(?P<offset>-?[0-9]+)\((?P<basereg>r[0-9]+)\)')
  55
  56 def mapop(op):
  57     match = opkind.fullmatch(op)
  58
  59     if match is None:
  60         op = ('other', op)
  61     elif match['reg'] is not None:
  62         op = (match['regkind'], int(match['regnum']))
  63     elif match['immediate'] is not None:
  64         op = ('imm', int (op).bit_length ())
  65     elif match['branch'] is not None:
  66         op = ('pcoff', (int (match['branch'], 16)
  67                         - int (addr, 16)).bit_length ())
  68     elif match['offset'] is not None:
  69         op = ('ofst', mapop(match['offset']), mapop(match['basereg']))
  70     else:
  71         raise "unrecognized operand kind"
  72
  73     return op
  74
  75 def opclass(mop):
  76     return mop[0]
  77 def regno(mop):
  78     if mop[0] in { 'r', 'fr', 'cr' }:
  79         return mop[1]
  80     else:
  81         raise "operand is not a register"
  82
  83 def immbits(mop):
  84     if mop[0] is 'imm':
  85         return mop[1]
  86     else:
  87         raise "operand is not an immediate"
  88
  89 # Following are predicates to be used in copcond, to tell the mode in
  90 # which opcode with ops as operands is to be represented
  91
  92 # Any occurrence of the opcode can be compressed.
  93 def anyops(opcode, ops):
  94     return 1
  95
  96 # Compress iff first and second operands are the same.
  97 def same01(opcode, ops):
  98     if ops[0] == ops[1]:
  99         return 1
 100     else:
 101         return 0
 102
 103 # Registers representable in a made-up 3-bit mapping.
 104 cregs2 = { 1, 2, 3, 4, 5, 6, 7, 31 }
 105
 106 # Return true iff mop is a regular register present in cregs2
 107 def bin2regs3(mop):
 108     return opclass(mop) is 'r' and regno(mop) in cregs2
 109
 110 # Return true iff mop is an immediate of at most 8 bits.
 111 def imm8(mop):
 112     return opclass(mop) is 'imm' and immbits(mop) <= 8
 113
 114 # Compress binary opcodes iff the first two operands (output and first
 115 # input operand) are registers representable in 3 bits in compressed
 116 # mode, and the immediate operand can be represented in 8 bits.
 117 def bin2regs3imm8(opcode, ops):
 118     if bin2regs3(ops[0]) and bin2regs3(ops[1]) and imm8(ops[2]):
 119         return 1
 120     else:
 121         return 0
 122
 123 # Map opcodes that might be compressed to a function that returns the
 124 # mode (index into mode_list below) in which the insn is to be
 125 # represented.  Those not mentioned in copcond are assumed
 126 # Uncomopressed.
 127 copcond = {
 128     # Pretending anything goes, just for demonstration purposes.
 129     'mr': anyops,
 130     'ld': anyops,
 131     'std': anyops,
 132     # Output and first input operand must coincide for these.
 133     'add': same01,
 134     'sub': same01,
 135     # Limiting register and operand range:
 136     'addi': bin2regs3imm8
 137     # Anything else is uncompressed.
 138 }
 139
 140 enter_compressed = 0
 141 leave_compressed = 0
 142 count_compressed = 0
 143 count_uncompressed = 0
 144 current_mode = 0
 145 mode_list = ['Uncompressed', 'Compressed'] # for documentation purposes only
 146
 147 for line in sys.stdin:
 148     if line[-1] is '\n':
 149         line = line[:-1]
 150
 151     match = insn.fullmatch(line)
 152     if match is None:
 153         print(line)
 154         # Switch to uncompressed mode at function boundaries
 155         if current_mode is not 0:
 156             print('<leave compressed mode>')
 157             current_mode = 0
 158             leave_compressed += 1
 159         continue
 160
 161     addr = match['addr']
 162     opcode = match['opcode']
 163     operands = match['operands']
 164
 165     if opcode in copcond:
 166         this_mode = copcond[opcode](opcode,
 167                                     [mapop(op) for op in operands.split(',')])
 168     else:
 169         this_mode = 0
 170
 171     if this_mode is 1:
 172         if current_mode is not 1:
 173             print('\t\tcin.nop')
 174             current_mode = 1
 175             enter_compressed += 1
 176         print(line + ' (c)')
 177         count_compressed += 1
 178     else:
 179         if current_mode is not 0:
 180             print('\t\tcout.nop')
 181             current_mode = 0
 182             leave_compressed += 1
 183         print(line)
 184         count_uncompressed += 1
 185
 186 transition_bytes = 1 * enter_compressed + 1 * leave_compressed
 187 compressed_bytes = 2 * count_compressed
 188 uncompressed_bytes = 4 * count_uncompressed
 189 total_bytes = transition_bytes + compressed_bytes + uncompressed_bytes
 190 original_bytes = 2 * compressed_bytes + uncompressed_bytes
 191
 192 print()
 193 print('Summary')
 194 print('Compressed instructions: %i' % count_compressed)
 195 print('Uncompressed instructions: %i' % count_uncompressed)
 196 print('Transitions into compressed mode: %i' % enter_compressed)
 197 print('Transitions out of compressed mode: %i' % leave_compressed)
 198 print('Compressed size estimate: %i' % total_bytes)
 199 print('Original size: %i' % original_bytes)
 200 print('Compressed/original ratio: %f' % (total_bytes / original_bytes))