llvm/test/CodeGen/WebAssembly/multivalue-stackify.py

   1 #!/usr/bin/env python3
   2
   3 """A test case generator for register stackification.
   4
   5 This script exhaustively generates small linear SSA programs, then filters them
   6 based on heuristics designed to keep interesting multivalue test cases and
   7 prints them as LLVM IR functions in a FileCheck test file.
   8
   9 The output of this script is meant to be used in conjunction with
  10 update_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
  17 Programs are represented internally as lists of operations, where each operation
  18 is a pair of tuples, the first of which specifies the operation's uses and the
  19 second of which specifies its defs.
  20
  21 TODO: Before embarking on a rewrite of the register stackifier, an abstract
  22 interpreter should be written to automatically check that the test assertions
  23 generated by update_llc_test_checks.py have the same semantics as the functions
  24 generated by this script. Once that is done, exhaustive testing can be done by
  25 making `is_interesting` return True.
  26 """
  27
  28
  29 from itertools import product
  30 from collections import deque
  31
  32
  33 MAX_PROGRAM_OPS = 4
  34 MAX_PROGRAM_DEFS = 3
  35 MAX_OP_USES = 2
  36
  37
  38 def get_num_defs(program):
  39     num_defs = 0
  40     for _, defs in program:
  41         num_defs += len(defs)
  42     return num_defs
  43
  44
  45 def 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
  55 def 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
  70 def 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
  78 def 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
  86 def 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
  96 def 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
 107 def 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
 120 def 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
 149 def make_llvm_type(num_defs):
 150     if num_defs == 0:
 151         return "void"
 152     else:
 153         return "{" + ", ".join(["i32"] * num_defs) + "}"
 154
 155
 156 def make_llvm_op_name(num_uses, num_defs):
 157     return f"op_{num_uses}_to_{num_defs}"
 158
 159
 160 def make_llvm_args(first_use, num_uses):
 161     return ", ".join([f"i32 %t{first_use + i}" for i in range(num_uses)])
 162
 163
 164 def 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
 192 def 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
 212 if __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()