| #!/usr/bin/env python3 |
| |
| """A test case generator for register stackification. |
| |
| This script exhaustively generates small linear SSA programs, then filters them |
| based on heuristics designed to keep interesting multivalue test cases and |
| prints them as LLVM IR functions in a FileCheck test file. |
| |
| The output of this script is meant to be used in conjunction with |
| update_llc_test_checks.py. |
| |
| ``` |
| ./multivalue-stackify.py > multivalue-stackify.ll |
| ../../../utils/update_llc_test_checks.py multivalue-stackify.ll |
| ``` |
| |
| Programs are represented internally as lists of operations, where each operation |
| is a pair of tuples, the first of which specifies the operation's uses and the |
| second of which specifies its defs. |
| |
| TODO: Before embarking on a rewrite of the register stackifier, an abstract |
| interpreter should be written to automatically check that the test assertions |
| generated by update_llc_test_checks.py have the same semantics as the functions |
| generated by this script. Once that is done, exhaustive testing can be done by |
| making `is_interesting` return True. |
| """ |
| |
| |
| from itertools import product |
| from collections import deque |
| |
| |
| MAX_PROGRAM_OPS = 4 |
| MAX_PROGRAM_DEFS = 3 |
| MAX_OP_USES = 2 |
| |
| |
| def get_num_defs(program): |
| num_defs = 0 |
| for _, defs in program: |
| num_defs += len(defs) |
| return num_defs |
| |
| |
| def possible_ops(program): |
| program_defs = get_num_defs(program) |
| for num_defs in range(MAX_PROGRAM_DEFS - program_defs + 1): |
| for num_uses in range(MAX_OP_USES + 1): |
| if num_defs == 0 and num_uses == 0: |
| continue |
| for uses in product(range(program_defs), repeat=num_uses): |
| yield uses, tuple(program_defs + i for i in range(num_defs)) |
| |
| |
| def generate_programs(): |
| queue = deque() |
| queue.append([]) |
| program_id = 0 |
| while True: |
| program = queue.popleft() |
| if len(program) == MAX_PROGRAM_OPS: |
| break |
| for op in possible_ops(program): |
| program_id += 1 |
| new_program = program + [op] |
| queue.append(new_program) |
| yield program_id, new_program |
| |
| |
| def get_num_terminal_ops(program): |
| num_terminal_ops = 0 |
| for _, defs in program: |
| if len(defs) == 0: |
| num_terminal_ops += 1 |
| return num_terminal_ops |
| |
| |
| def get_max_uses(program): |
| num_uses = [0] * MAX_PROGRAM_DEFS |
| for uses, _ in program: |
| for u in uses: |
| num_uses[u] += 1 |
| return max(num_uses) |
| |
| |
| def has_unused_op(program): |
| used = [False] * MAX_PROGRAM_DEFS |
| for uses, defs in program[::-1]: |
| if defs and all(not used[d] for d in defs): |
| return True |
| for u in uses: |
| used[u] = True |
| return False |
| |
| |
| def has_multivalue_use(program): |
| is_multi = [False] * MAX_PROGRAM_DEFS |
| for uses, defs in program: |
| if any(is_multi[u] for u in uses): |
| return True |
| if len(defs) >= 2: |
| for d in defs: |
| is_multi[d] = True |
| return False |
| |
| |
| def has_mvp_use(program): |
| is_mvp = [False] * MAX_PROGRAM_DEFS |
| for uses, defs in program: |
| if uses and all(is_mvp[u] for u in uses): |
| return True |
| if len(defs) <= 1: |
| if any(is_mvp[u] for u in uses): |
| return True |
| for d in defs: |
| is_mvp[d] = True |
| return False |
| |
| |
| def is_interesting(program): |
| # Allow only multivalue single-op programs |
| if len(program) == 1: |
| return len(program[0][1]) > 1 |
| |
| # Reject programs where the last two instructions are identical |
| if len(program) >= 2 and program[-1][0] == program[-2][0]: |
| return False |
| |
| # Reject programs with too many ops that don't produce values |
| if get_num_terminal_ops(program) > 2: |
| return False |
| |
| # The third use of a value is no more interesting than the second |
| if get_max_uses(program) >= 3: |
| return False |
| |
| # Reject nontrivial programs that have unused instructions |
| if has_unused_op(program): |
| return False |
| |
| # Reject programs that have boring MVP uses of MVP defs |
| if has_mvp_use(program): |
| return False |
| |
| # Otherwise if it has multivalue usage it is interesting |
| return has_multivalue_use(program) |
| |
| |
| def make_llvm_type(num_defs): |
| if num_defs == 0: |
| return 'void' |
| else: |
| return '{' + ', '.join(['i32'] * num_defs) + '}' |
| |
| |
| def make_llvm_op_name(num_uses, num_defs): |
| return f'op_{num_uses}_to_{num_defs}' |
| |
| |
| def make_llvm_args(first_use, num_uses): |
| return ', '.join([f'i32 %t{first_use + i}' for i in range(num_uses)]) |
| |
| |
| def print_llvm_program(program, name): |
| tmp = 0 |
| def_data = [] |
| print(f'define void @{name}() {{') |
| for uses, defs in program: |
| first_arg = tmp |
| # Extract operands |
| for use in uses: |
| ret_type, var, idx = def_data[use] |
| print(f' %t{tmp} = extractvalue {ret_type} %t{var}, {idx}') |
| tmp += 1 |
| # Print instruction |
| assignment = '' |
| if len(defs) > 0: |
| assignment = f'%t{tmp} = ' |
| result_var = tmp |
| tmp += 1 |
| ret_type = make_llvm_type(len(defs)) |
| op_name = make_llvm_op_name(len(uses), len(defs)) |
| args = make_llvm_args(first_arg, len(uses)) |
| print(f' {assignment}call {ret_type} @{op_name}({args})') |
| # Update def_data |
| for i in range(len(defs)): |
| def_data.append((ret_type, result_var, i)) |
| print(' ret void') |
| print('}') |
| |
| |
| def print_header(): |
| print('; NOTE: Test functions have been generated by multivalue-stackify.py.') |
| print() |
| print('; RUN: llc < %s -verify-machineinstrs -mattr=+multivalue', |
| '| FileCheck %s') |
| print() |
| print('; Test that the multivalue stackification works') |
| print() |
| print('target triple = "wasm32-unknown-unknown"') |
| print() |
| for num_uses in range(MAX_OP_USES + 1): |
| for num_defs in range(MAX_PROGRAM_DEFS + 1): |
| if num_uses == 0 and num_defs == 0: |
| continue |
| ret_type = make_llvm_type(num_defs) |
| op_name = make_llvm_op_name(num_uses, num_defs) |
| args = make_llvm_args(0, num_uses) |
| print(f'declare {ret_type} @{op_name}({args})') |
| print() |
| |
| |
| if __name__ == '__main__': |
| print_header() |
| for i, program in generate_programs(): |
| if is_interesting(program): |
| print_llvm_program(program, 'f' + str(i)) |
| print() |