[jsprogrammer]

I'd guess either approach will become stuck in local minima. Ideally, you'd want to check all permutations systematically. Of course, there is probably no polynomial-time algorithm to find the optimal, but adding some basic depth bounds should give a practical implementation that can explore at least some of the space, instead of relying on gut instinct about which approach may or may not be better.

[UniQP]

The permutation problem is not related to IR superoptimization itself.

The goal of an optimization pass is to improve the performance of an average, and that's exactly what the IR superoptimization does.