218 lines · python
1#!/usr/bin/env python32 3"""A test case generator for register stackification.4 5This script exhaustively generates small linear SSA programs, then filters them6based on heuristics designed to keep interesting multivalue test cases and7prints them as LLVM IR functions in a FileCheck test file.8 9The output of this script is meant to be used in conjunction with10update_llc_test_checks.py.11 12 ```13 ./multivalue-stackify.py > multivalue-stackify.ll14 ../../../utils/update_llc_test_checks.py multivalue-stackify.ll15 ```16 17Programs are represented internally as lists of operations, where each operation18is a pair of tuples, the first of which specifies the operation's uses and the19second of which specifies its defs.20 21TODO: Before embarking on a rewrite of the register stackifier, an abstract22interpreter should be written to automatically check that the test assertions23generated by update_llc_test_checks.py have the same semantics as the functions24generated by this script. Once that is done, exhaustive testing can be done by25making `is_interesting` return True.26"""27 28 29from itertools import product30from collections import deque31 32 33MAX_PROGRAM_OPS = 434MAX_PROGRAM_DEFS = 335MAX_OP_USES = 236 37 38def get_num_defs(program):39 num_defs = 040 for _, defs in program:41 num_defs += len(defs)42 return num_defs43 44 45def possible_ops(program):46 program_defs = get_num_defs(program)47 for num_defs in range(MAX_PROGRAM_DEFS - program_defs + 1):48 for num_uses in range(MAX_OP_USES + 1):49 if num_defs == 0 and num_uses == 0:50 continue51 for uses in product(range(program_defs), repeat=num_uses):52 yield uses, tuple(program_defs + i for i in range(num_defs))53 54 55def generate_programs():56 queue = deque()57 queue.append([])58 program_id = 059 while True:60 program = queue.popleft()61 if len(program) == MAX_PROGRAM_OPS:62 break63 for op in possible_ops(program):64 program_id += 165 new_program = program + [op]66 queue.append(new_program)67 yield program_id, new_program68 69 70def get_num_terminal_ops(program):71 num_terminal_ops = 072 for _, defs in program:73 if len(defs) == 0:74 num_terminal_ops += 175 return num_terminal_ops76 77 78def get_max_uses(program):79 num_uses = [0] * MAX_PROGRAM_DEFS80 for uses, _ in program:81 for u in uses:82 num_uses[u] += 183 return max(num_uses)84 85 86def has_unused_op(program):87 used = [False] * MAX_PROGRAM_DEFS88 for uses, defs in program[::-1]:89 if defs and all(not used[d] for d in defs):90 return True91 for u in uses:92 used[u] = True93 return False94 95 96def has_multivalue_use(program):97 is_multi = [False] * MAX_PROGRAM_DEFS98 for uses, defs in program:99 if any(is_multi[u] for u in uses):100 return True101 if len(defs) >= 2:102 for d in defs:103 is_multi[d] = True104 return False105 106 107def has_mvp_use(program):108 is_mvp = [False] * MAX_PROGRAM_DEFS109 for uses, defs in program:110 if uses and all(is_mvp[u] for u in uses):111 return True112 if len(defs) <= 1:113 if any(is_mvp[u] for u in uses):114 return True115 for d in defs:116 is_mvp[d] = True117 return False118 119 120def is_interesting(program):121 # Allow only multivalue single-op programs122 if len(program) == 1:123 return len(program[0][1]) > 1124 125 # Reject programs where the last two instructions are identical126 if len(program) >= 2 and program[-1][0] == program[-2][0]:127 return False128 129 # Reject programs with too many ops that don't produce values130 if get_num_terminal_ops(program) > 2:131 return False132 133 # The third use of a value is no more interesting than the second134 if get_max_uses(program) >= 3:135 return False136 137 # Reject nontrivial programs that have unused instructions138 if has_unused_op(program):139 return False140 141 # Reject programs that have boring MVP uses of MVP defs142 if has_mvp_use(program):143 return False144 145 # Otherwise if it has multivalue usage it is interesting146 return has_multivalue_use(program)147 148 149def make_llvm_type(num_defs):150 if num_defs == 0:151 return "void"152 else:153 return "{" + ", ".join(["i32"] * num_defs) + "}"154 155 156def make_llvm_op_name(num_uses, num_defs):157 return f"op_{num_uses}_to_{num_defs}"158 159 160def make_llvm_args(first_use, num_uses):161 return ", ".join([f"i32 %t{first_use + i}" for i in range(num_uses)])162 163 164def print_llvm_program(program, name):165 tmp = 0166 def_data = []167 print(f"define void @{name}() {{")168 for uses, defs in program:169 first_arg = tmp170 # Extract operands171 for use in uses:172 ret_type, var, idx = def_data[use]173 print(f" %t{tmp} = extractvalue {ret_type} %t{var}, {idx}")174 tmp += 1175 # Print instruction176 assignment = ""177 if len(defs) > 0:178 assignment = f"%t{tmp} = "179 result_var = tmp180 tmp += 1181 ret_type = make_llvm_type(len(defs))182 op_name = make_llvm_op_name(len(uses), len(defs))183 args = make_llvm_args(first_arg, len(uses))184 print(f" {assignment}call {ret_type} @{op_name}({args})")185 # Update def_data186 for i in range(len(defs)):187 def_data.append((ret_type, result_var, i))188 print(" ret void")189 print("}")190 191 192def print_header():193 print("; NOTE: Test functions have been generated by multivalue-stackify.py.")194 print()195 print("; RUN: llc < %s -verify-machineinstrs -mattr=+multivalue", "| FileCheck %s")196 print()197 print("; Test that the multivalue stackification works")198 print()199 print('target triple = "wasm32-unknown-unknown"')200 print()201 for num_uses in range(MAX_OP_USES + 1):202 for num_defs in range(MAX_PROGRAM_DEFS + 1):203 if num_uses == 0 and num_defs == 0:204 continue205 ret_type = make_llvm_type(num_defs)206 op_name = make_llvm_op_name(num_uses, num_defs)207 args = make_llvm_args(0, num_uses)208 print(f"declare {ret_type} @{op_name}({args})")209 print()210 211 212if __name__ == "__main__":213 print_header()214 for i, program in generate_programs():215 if is_interesting(program):216 print_llvm_program(program, "f" + str(i))217 print()218