Optimize how much to unroll a loop body vs how much yosys can optimize it

[j2kun]

On the side of gate-bootstrapped CGGI, we had a path where we fully unrolled all loops before running a circuit optimizer, and for large IRs that was infeasibly slow. We hacked together a different approach in lib/Conversion/MemrefToArith/ExtractLoopBody.cpp that results in only the inner-most body of a loop being optimized via yosys, and retaining the rest of the loop structure.

There is likely an intermediate approach where we can unroll the loop body to a different factor depending on how much yosys is able to optimize it. A decent initial approach might be greedy: starting from no unrolling to a factor of N—say, based on a fixed time budget—and compare the size of the input circuit to the size of the output circuit (this will be a bit fuzzy because the input circuit is not techmapped, but the output circuit is, but I'm hoping relative sizes will be sufficient to compare), and stop once the incremental benefit of unrolling more is plateauing, decreasing, or the time budget is exhausted.

As an outline of the work required for this:

• Write a pass that doesn't unroll at all, but extracts the innermost body of a loop-next, optimizes it with yosys, and inserts it back into the loop body, replacing the old body. The hard part will likely be the booleanization interface, but @asraa is working on that in https://github.com/google/heir/issues/244 and one could extract the loop body first to a separate function in order to use that, then inline the result.
• Upgrade the pass to unroll-and-optimize progressively, and write the results to the terminal so we can plot a few different functions and plot the results look like on a curve to confirm that a greedy approach would actually be appropriate
• Implement the greedy selection.

I'm hoping that, once we incorporate arithmetic circuit optimization, the same pass could be re-used for that and apply to non-CGGI contexts.

[j2kun]

The first step of this is done: optimizing the inner-most body of a loop-nest.

[github-actions[bot]]

This issue has 1 outstanding TODOs:

• lib/Transforms/YosysOptimizer/YosysOptimizer.td:29: add option for the pass to select the unroll factor

This comment was autogenerated by todo-backlinks

[j2kun]

Last step: add a helper script that runs the loop unrolling with lots of different unroll factors, and prints the relative statistics.