ISA generation algorithm pseudocode

[gussmith23]

Given: a program or set of programs (bitvector compute graphs). Functional description of the FPGA.

Goal: generate an ISA: a set of instructions which can be implemented on the FPGA. Express the input program(s) in terms of the ISA.
Alternatively: we generate

1. ISA
2. ISA impl
3. Mapping from each program in the input to the ISA
   Instructions:

• are at the granularity of an FPGA (logic) slice; that is, one instruction = 1 slice.
  • Note that you can have another ISA on top of the ISA where we can combine instructions to make new (multi-slice) instructions.
• are expressed in the same language as the programs, so the smallest possible instruction is one operator of the input programs.

Algorithm:

1. Insert programs into egraph.
   • Programs are composed of two program node types: variables and operator invocations. Variables are specified by a name and a bitwidth. Operator invocations specify the operator (and, or, xor, etc) and the arguments.
2. Run rewrites to generate ISA expressions.
   ISA instructions in the egraph will be represented by ASTs, which also have two node types: holes and AST operator invocations. Holes, like variables, are the leaves of the expression, and have a bitwidth specifier, but do not have names. Holes can be filled by any type of program expression: a lone variable, or a series of operator invocations. AST operator invocations are just like operator invocations except they operate over ASTs (so, holes or other AST operator invocations.) The apply operator applies a list of arguments (which are program nodes, i.e. vars or operator invocations) to an AST, giving back program nodes.
   We have five rewrites:
   1. The first rewrite converts a variable node to an application of that variable node on an AST consisting of just a hole:
      (var ?name ?bw) -> (apply (hole ?bw) (list (var ?name ?bw)))
   2. The next four rewrites convert an operator invocation node to an apply. One rewrite converts the left child to a hole; one rewrite converts the right child to a hole; one rewrite converts both to holes; one rewrite converts neither to holes.
3. Extract potential ISA instructions.
   Once the above step completes, we can find the potential ISA instructions by finding all instances of (apply ?ast ?args) within the egraph. Each unique ?ast will represent a different potential instruction. E.g. (and (hole) (or (hole) (hole))) is a fused or-and.
   Note that this isn't 100% correct: there's some detail elided. We can get an even more diverse ISA by considering that some holes may be filled by the same variable, e.g. (and (var a) (or (var b) (var a))) in the example above. Thus, part of the ISA instruction generation step should include substituting in variables. This may require further deduplication afterwards.
4. Attempt synthesis on each ISA instruction, to filter down to valid ISA instructions.
   Using synthesis, we can determine whether a slice of the FPGA can be configured to implement each ISA instruction. If one of the potential instructions cannot actually be implemented on a slice, it's dropped from the ISA. In the end, our ISA contains only instructions implementable on a slice of the FPGA.
5. Use the ISA to extract implementations of the programs in terms of the ISA.
   We can now use a standard greedy egraph extraction, which, for each eclass, extracts an enode which can be implemented with ISA instructions. This is easy -- we just check whether synthesis worked for the corresponding instruction. We can break ties using e.g. smallest AST, which will give us an implementation of the program using the least number of slices on the FPGA.

[gussmith23]

Step 4 (synthesis) will likely involve a prioritization step, in which we prioritize which instructions we will attempt to synthesize. This is because, even with the deduplication we'll get from the egraph, there will likely be far too many to synthesize! One simple way to order the instructions will be by their size: we can try to synthesize smaller instructions first, as they'll be more likely to succeed.

[gussmith23]

Steps 4 and 5 can probably be interleaved: i.e. we can run synthesis until we're able to successfully compile our program using the ISA, and then we can run more rounds of synthesis to try and improve the compilation by generating a "better" ISA (i.e. an ISA with bigger instructions, leading to less resource usage).