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',
196        '| FileCheck %s')
197  print()
198  print('; Test that the multivalue stackification works')
199  print()
200  print('target triple = "wasm32-unknown-unknown"')
201  print()
202  for num_uses in range(MAX_OP_USES + 1):
203    for num_defs in range(MAX_PROGRAM_DEFS + 1):
204      if num_uses == 0 and num_defs == 0:
205        continue
206      ret_type = make_llvm_type(num_defs)
207      op_name = make_llvm_op_name(num_uses, num_defs)
208      args = make_llvm_args(0, num_uses)
209      print(f'declare {ret_type} @{op_name}({args})')
210  print()
211
212
213if __name__ == '__main__':
214  print_header()
215  for i, program in generate_programs():
216    if is_interesting(program):
217      print_llvm_program(program, 'f' + str(i))
218      print()
219