From 7451ce80f480ef46c1abdb75b7b3b5dc670d5fed Mon Sep 17 00:00:00 2001 From: Alexandre Oliva Date: Sat, 28 Nov 2020 22:38:27 -0300 Subject: [PATCH] Add lxo/ChangeLog, and throw-away-me-not :-) scripts written for PR532 --- lxo/532/comp16-v2-skel.py | 176 ++++++++++++++++++++++++++++++++++++++ lxo/532/insn-histogram.py | 69 +++++++++++++++ lxo/ChangeLog | 43 ++++++++++ 3 files changed, 288 insertions(+) create mode 100644 lxo/532/comp16-v2-skel.py create mode 100644 lxo/532/insn-histogram.py create mode 100644 lxo/ChangeLog diff --git a/lxo/532/comp16-v2-skel.py b/lxo/532/comp16-v2-skel.py new file mode 100644 index 000000000..471f9c9da --- /dev/null +++ b/lxo/532/comp16-v2-skel.py @@ -0,0 +1,176 @@ +#! /bin/env python3 + +# Feed this script the output of objdump -M raw --no-show-raw-insn ppc-prog + +# It will look for insns that can be represented in compressed mode, +# according to the encoding rules in the copcond dictionary below. +# Nothing is assumed as to the actual bit-encoding of the insns, this +# is just to experiment with insn selection and get a quick feedback +# loop for the encoding options in compressed mode. + +# In this script, the computations of encoding modes and transitions +# are tuned for the simpler model that uses 1-byte nops for +# transitions in and out of compressed mode, placing compressed-mode +# insns at odd addresses. At (visible) entry points, mode is forced +# to return to uncompressed mode. + +# The entire code stream is printed, without any attempt to modify the +# addresses that go along with or in them; we only insert markers for +# the transition points, and for the compressed instructions. + +# The really useful information is printed at the end: a summary of +# transition and compressed-insn counts, and the achieved compression +# rate. + +import sys +import re + +insn = re.compile('\s+(?P[0-9a-f]+):\s+(?P[^ ]+) *(?P.*)') + +opkind = re.compile('(?P(?P[cf]?r)(?P[0-9]+))|(?P-?[0-9]+)|(?P[0-9a-f]+)(?: <.*>)?|(?P-?[0-9]+)\((?Pr[0-9]+)\)') + +def mapop(op): + match = opkind.fullmatch(op) + + if match is None: + op = ('other', op) + elif match['reg'] is not None: + op = (match['regkind'], int(match['regnum'])) + elif match['immediate'] is not None: + op = ('imm', int (op).bit_length ()) + elif match['branch'] is not None: + op = ('pcoff', (int (match['branch'], 16) + - int (addr, 16)).bit_length ()) + elif match['offset'] is not None: + op = ('ofst', mapop(match['offset']), mapop(match['basereg'])) + else: + raise "unrecognized operand kind" + + return op + +def opclass(mop): + return mop[0] +def regno(mop): + if mop[0] in { 'r', 'fr', 'cr' }: + return mop[1] + else: + raise "operand is not a register" + +def immbits(mop): + if mop[0] is 'imm': + return mop[1] + else: + raise "operand is not an immediate" + +# Following are predicates to be used in copcond, to tell the mode in +# which opcode with ops as operands is to be represented + +# Any occurrence of the opcode can be compressed. +def anyops(opcode, ops): + return 1 + +# Compress iff first and second operands are the same. +def same01(opcode, ops): + if ops[0] == ops[1]: + return 1 + else: + return 0 + +# Registers representable in a made-up 3-bit mapping. +cregs2 = { 1, 2, 3, 4, 5, 6, 7, 31 } + +# Return true iff mop is a regular register present in cregs2 +def bin2regs3(mop): + return opclass(mop) is 'r' and regno(mop) in cregs2 + +# Return true iff mop is an immediate of at most 8 bits. +def imm8(mop): + return opclass(mop) is 'imm' and immbits(mop) <= 8 + +# Compress binary opcodes iff the first two operands (output and first +# input operand) are registers representable in 3 bits in compressed +# mode, and the immediate operand can be represented in 8 bits. +def bin2regs3imm8(opcode, ops): + if bin2regs3(ops[0]) and bin2regs3(ops[1]) and imm8(ops[2]): + return 1 + else: + return 0 + +# Map opcodes that might be compressed to a function that returns the +# mode (index into mode_list below) in which the insn is to be +# represented. Those not mentioned in copcond are assumed +# Uncomopressed. +copcond = { + # Pretending anything goes, just for demonstration purposes. + 'mr': anyops, + 'ld': anyops, + 'std': anyops, + # Output and first input operand must coincide for these. + 'add': same01, + 'sub': same01, + # Limiting register and operand range: + 'addi': bin2regs3imm8 + # Anything else is uncompressed. +} + +enter_compressed = 0 +leave_compressed = 0 +count_compressed = 0 +count_uncompressed = 0 +current_mode = 0 +mode_list = ['Uncompressed', 'Compressed'] # for documentation purposes only + +for line in sys.stdin: + if line[-1] is '\n': + line = line[:-1] + + match = insn.fullmatch(line) + if match is None: + print(line) + # Switch to uncompressed mode at function boundaries + if current_mode is not 0: + print('') + current_mode = 0 + leave_compressed += 1 + continue + + addr = match['addr'] + opcode = match['opcode'] + operands = match['operands'] + + if opcode in copcond: + this_mode = copcond[opcode](opcode, + [mapop(op) for op in operands.split(',')]) + else: + this_mode = 0 + + if this_mode is 1: + if current_mode is not 1: + print('\t\tcin.nop') + current_mode = 1 + enter_compressed += 1 + print(line + ' (c)') + count_compressed += 1 + else: + if current_mode is not 0: + print('\t\tcout.nop') + current_mode = 0 + leave_compressed += 1 + print(line) + count_uncompressed += 1 + +transition_bytes = 1 * enter_compressed + 1 * leave_compressed +compressed_bytes = 2 * count_compressed +uncompressed_bytes = 4 * count_uncompressed +total_bytes = transition_bytes + compressed_bytes + uncompressed_bytes +original_bytes = 2 * compressed_bytes + uncompressed_bytes + +print() +print('Summary') +print('Compressed instructions: %i' % count_compressed) +print('Uncompressed instructions: %i' % count_uncompressed) +print('Transitions into compressed mode: %i' % enter_compressed) +print('Transitions out of compressed mode: %i' % leave_compressed) +print('Compressed size estimate: %i' % total_bytes) +print('Original size: %i' % original_bytes) +print('Compressed/original ratio: %f' % (total_bytes / original_bytes)) diff --git a/lxo/532/insn-histogram.py b/lxo/532/insn-histogram.py new file mode 100644 index 000000000..9d6602342 --- /dev/null +++ b/lxo/532/insn-histogram.py @@ -0,0 +1,69 @@ +#! /bin/env python3 + +# Feed this script the output of objdump -M raw --no-show-raw-insn ppc-prog + +# It will print the occurrence count of each opcode, +# and under it, indented by one character, +# the occurrence count of each operand. + +# Registers used as operands or as base addresses are counted +# separately; immediates and offsets are grouped per bit length; +# branch target offsets are grouped by range bit length. + +import sys +import re + +insn = re.compile('\s+(?P[0-9a-f]+):\s+(?P[^ \n]+) *(?P.*)[\n]?') + +opkind = re.compile('(?P-?[0-9]+)|(?P[0-9a-f]+)(?: <.*>)?|(?P-?[0-9]+)\((?Pr[0-9]+)\)') + +histogram = {} + +def count(ops, op): + match = opkind.fullmatch(op) + + if match is None: + op = op + elif match['immediate'] is not None: + op = "%i-bit" % int (op).bit_length () + elif match['branch'] is not None: + op = "%i-bit range" % (int (match['branch'], 16) - int (addr, 16)).bit_length () + elif match['offset'] is not None: + count(ops, match['offset']) + op = match['basereg'] + else: + raise "unrecognized operand kind" + + if op not in ops: + ops[op] = 1 + else: + ops[op] += 1 + +for line in sys.stdin: + match = insn.fullmatch(line) + if match is None: + continue + + addr = match['addr'] + opcode = match['opcode'] + operands = match['operands'] + + if opcode not in histogram: + ops = {} + histogram[opcode] = [1,ops] + else: + histogram[opcode][0] += 1 + ops = histogram[opcode][1] + + if len(operands) > 0: + for operand in operands.split(','): + count(ops, operand) + +hist = list(histogram.items()) +hist.sort(key = (lambda x : x[1][0])) +for x in hist: + print('%6i %s:' % (x[1][0], x[0])) + ops = list(x[1][1].items()) + ops.sort(key = (lambda x : x[1])) + for x in ops: + print(' %6i %s' % (x[1], x[0])) diff --git a/lxo/ChangeLog b/lxo/ChangeLog new file mode 100644 index 000000000..6db83291d --- /dev/null +++ b/lxo/ChangeLog @@ -0,0 +1,43 @@ +2020-11-28 + + * 532: Implemented a skeleton for compression ratio estimation, + initially with the simpler mode switching of the 8-bit nop, + odd-address 16-bit insns. Next, rewrite it for all the complexity + of mode switching envisioned for the "attempt 1" proposal. (2:02) + +2020-11-23 + + * 238: Debating various possibilities of 16-bit encoding. (5:20) + + * 532: Wrote a histogram python script, that breaks counts down + per opcode, and within them, by operands. (2:05) + +2020-11-22 + + * 529: Brought up the possibilities of using 8-bit nops to switch + between modes, so that 16-bit insns would be at odd addresses, so + that we could use the full 16-bits; of using 2-operand insns + instead of 3- for 16-bit mode so as to increase the coverage of + the compact encoding. + * 238: Luke moved the comment above here, where it belonged. + * 529: Elaborated how using actual odd-addresses for 16-bit insns + would be dealt with WRT endianness. Prompted by luke, added it to + the wiki. + * Wiki: Added self to team. (11:50) + +2020-11-21 + + * 532: Wrote patch for binutils to print insn histogram. + * Mission: Restated the proposal of adding "and users" to the + mission statement, next to customers, as those we wish to enable + to trust our products. (6:48) + +2020-11-20 + + Reposted join message to the correct list. + * 238: Started looking into it, from + https://libre-soc.org/openpower/sv/16_bit_compressed/ + +2020-11-19 + + Joined. -- 2.30.2