--- /dev/null
+#! /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<addr>[0-9a-f]+):\s+(?P<opcode>[^ ]+) *(?P<operands>.*)')
+
+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]+)\)')
+
+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('<leave compressed mode>')
+ 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))
--- /dev/null
+#! /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<addr>[0-9a-f]+):\s+(?P<opcode>[^ \n]+) *(?P<operands>.*)[\n]?')
+
+opkind = re.compile('(?P<immediate>-?[0-9]+)|(?P<branch>[0-9a-f]+)(?: <.*>)?|(?P<offset>-?[0-9]+)\((?P<basereg>r[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]))
--- /dev/null
+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.
projects / libreriscv.git / commitdiff