Vectorizer: Do tracking to decide whether passthrough is beneficial

[mrcslws]

A subset of Vexpr ops support passthrough. For example, a vectorized_sum and vectorized_prod can choose to passthrough a non-sum or non-prod expression by simply performing a sum of 1 element or a product of 1 element. Similarly, add / multiply / divide / power can trivially perform identity operations (x + 0, x * 1, x / 1, x ** 1, respectively). And any operation without an "identity", e.g. unary operators like exp or log, can be made to support passthrough if you make the operation select a subset of indices, perform the operation, then put the new values back in the vector.

Passthrough is often a good idea because it allows "further down" operations to be vectorized. But sometimes it is pointless and adds unneeded cost. And there's a spectrum of in-between scenarios.

The "try everything" approach of #4 is probably not a good solution here, since for $n$ passthrough values there are $2^n$ possible combinations to pass through. We could potentially group ops, so that n is the number of groups, but still it seems crazy to try every combination of groups.

To address this, it would be useful to have a couple numbers for each passed through value:

• how many value passthroughs occur
• how many times a value is used in a vectorized operation with a non-passthrough value

The first number is bad. The second is good. We would evaluate whether a passthrough is a good idea by using these two numbers. (At the very least, Vexpr ought not to do passthrough when there is zero benefit, i.e. when it does not enable "further down" operations to be vectorized.) For every passthrough, there is a tree of values that "lead up to it". We would gather this data for the full tree. So if the passthrough value has 3 children, then those 3 children are used in a vectorized operation with non-passthrough values, we log 3 "good" counts.

To make this work, the vectorize logic for each op will receive a stack of lists of bools, and it will return a stack of usage data. Each item in the stack corresponds to some ancestor who is doing passthrough and evaluating whether the passthrough is a good idea. Each bool indicates whether a value is a passthrough value. So each vectorize op is responsible for transforming these arrays of bools for "further down" ops (e.g. if a passthrough value is the result of a sum of 3 items, then 1 True passthrough bool will become 3 True passthrough bools).