1#!/usr/bin/env python3 2 3"""A test case generator for register stackification. 4 5This script exhaustively generates small linear SSA programs, then filters them 6based on heuristics designed to keep interesting multivalue test cases and 7prints them as LLVM IR functions in a FileCheck test file. 8 9The output of this script is meant to be used in conjunction with 10update_llc_test_checks.py. 11 12 ``` 13 ./multivalue-stackify.py > multivalue-stackify.ll 14 ../../../utils/update_llc_test_checks.py multivalue-stackify.ll 15 ``` 16 17Programs are represented internally as lists of operations, where each operation 18is a pair of tuples, the first of which specifies the operation's uses and the 19second of which specifies its defs. 20 21TODO: Before embarking on a rewrite of the register stackifier, an abstract 22interpreter should be written to automatically check that the test assertions 23generated by update_llc_test_checks.py have the same semantics as the functions 24generated by this script. Once that is done, exhaustive testing can be done by 25making `is_interesting` return True. 26""" 27 28 29from itertools import product 30from collections import deque 31 32 33MAX_PROGRAM_OPS = 4 34MAX_PROGRAM_DEFS = 3 35MAX_OP_USES = 2 36 37 38def get_num_defs(program): 39 num_defs = 0 40 for _, defs in program: 41 num_defs += len(defs) 42 return num_defs 43 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 continue 51 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 = 0 59 while True: 60 program = queue.popleft() 61 if len(program) == MAX_PROGRAM_OPS: 62 break 63 for op in possible_ops(program): 64 program_id += 1 65 new_program = program + [op] 66 queue.append(new_program) 67 yield program_id, new_program 68 69 70def get_num_terminal_ops(program): 71 num_terminal_ops = 0 72 for _, defs in program: 73 if len(defs) == 0: 74 num_terminal_ops += 1 75 return num_terminal_ops 76 77 78def get_max_uses(program): 79 num_uses = [0] * MAX_PROGRAM_DEFS 80 for uses, _ in program: 81 for u in uses: 82 num_uses[u] += 1 83 return max(num_uses) 84 85 86def has_unused_op(program): 87 used = [False] * MAX_PROGRAM_DEFS 88 for uses, defs in program[::-1]: 89 if defs and all(not used[d] for d in defs): 90 return True 91 for u in uses: 92 used[u] = True 93 return False 94 95 96def has_multivalue_use(program): 97 is_multi = [False] * MAX_PROGRAM_DEFS 98 for uses, defs in program: 99 if any(is_multi[u] for u in uses): 100 return True 101 if len(defs) >= 2: 102 for d in defs: 103 is_multi[d] = True 104 return False 105 106 107def has_mvp_use(program): 108 is_mvp = [False] * MAX_PROGRAM_DEFS 109 for uses, defs in program: 110 if uses and all(is_mvp[u] for u in uses): 111 return True 112 if len(defs) <= 1: 113 if any(is_mvp[u] for u in uses): 114 return True 115 for d in defs: 116 is_mvp[d] = True 117 return False 118 119 120def is_interesting(program): 121 # Allow only multivalue single-op programs 122 if len(program) == 1: 123 return len(program[0][1]) > 1 124 125 # Reject programs where the last two instructions are identical 126 if len(program) >= 2 and program[-1][0] == program[-2][0]: 127 return False 128 129 # Reject programs with too many ops that don't produce values 130 if get_num_terminal_ops(program) > 2: 131 return False 132 133 # The third use of a value is no more interesting than the second 134 if get_max_uses(program) >= 3: 135 return False 136 137 # Reject nontrivial programs that have unused instructions 138 if has_unused_op(program): 139 return False 140 141 # Reject programs that have boring MVP uses of MVP defs 142 if has_mvp_use(program): 143 return False 144 145 # Otherwise if it has multivalue usage it is interesting 146 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 = 0 166 def_data = [] 167 print(f"define void @{name}() {{") 168 for uses, defs in program: 169 first_arg = tmp 170 # Extract operands 171 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 += 1 175 # Print instruction 176 assignment = "" 177 if len(defs) > 0: 178 assignment = f"%t{tmp} = " 179 result_var = tmp 180 tmp += 1 181 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_data 186 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 continue 205 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