Array to prod

Array to prod optimization for constant sized arrays.

• To identify arrays that can be converted, we start from constant sized constant arrays and identify all users (including users of users) and all the arrays used by those users and ensure that all of those nodes can be converted.
  • Constructing these sets uses a custom union-find structure since I didn't find a good crate for it
• Converts multi-dimensional arrays into nested products as it makes the transformations easier, SROA can then eliminate these products entirely.
• The optimization can handle partial selections of a function and also has an optional argument for setting a maximum size of array (i.e. total number of elements) that it will convert.
• To allow optional arguments/variable number of arguments in the scheduler, some small tweaks to the scheduler.

We should make sure to test this once forkify is fixed to handle the sorting loop, but if we manually unroll that loop this optimization is able to convert the median entirely into a tower of selects.

requested review from @rarbore2

assigned to @aaronjc4

mentioned in issue #22 (closed)

It is rather shocking that there's not a good simple union find crate that doesn't have a bunch of bells and whistles...

added 5 commits

• 772dc81f...d5985d59 - 4 commits from branch main
• 878956fd - Merge branch 'main' into array-to-prod

Compare with previous version

So it looks like even w/ merging main, forkify still doesn't fork the loop w/ the ifs @xrouth2.

added 1 commit

• 664daa17 - fully unroll / predicate median window

Compare with previous version

resolved all threads

approved this merge request

mentioned in commit 145a016c

merged