CmmSink is in O(n^2) in the number of assignment.
Our current implementation of CmmSink is fairly simply and works fairly well for the general case even though it's O(n^2) in nature.
However ever so often we end up with Cmm with a large amount of assignments (e.g. #18814) where it's O(n^2) nature starts to become problematic.
The main issue is that for code similar to the following:
foo_1 = e_1
...
foo_n = e_n
bar_1 = foo_1
...
bar_n = foo_n
We walk over each assignment and perform roughly these steps each time:
- Try to "pick up" the assignment into a list of assignments we could sink.
- If we can't pick up the assignment:
- Try to sink each assignment to a var mentioned on the rhs into the assignment.
The issue here is that sometimes we pick up a large number of assignments. E.g. foo_1 to foo_n. Then when we get to the bar_* assignments when we try to see if we can inline anything we end up walking the whole list of assignments to check if any of them can be inlined. Doing this for n statements then gives us the current O(n^2) behaviour.
Naively we should be able to just look up variables mentioned on the rhs of assignments (eg. foo_n in bar_n = foo_n
) for inlining.
The main hurdle to fix this is that the order of assignments matters. Primarily for determining
dependent assignments. As is described in Note [dependent assignments]
in Sink.hs (duplicated below)
--
-- If our assignment list looks like
--
-- [ y = e, x = ... y ... ]
--
-- We cannot inline x. Remember this list is really in reverse order,
-- so it means x = ... y ...; y = e
--
-- Hence if we inline x, the outer assignment to y will capture the
-- reference in x's right hand side.
--
-- In this case we should rename the y in x's right-hand side,
-- i.e. change the list to [ y = e, x = ... y1 ..., y1 = y ]
-- Now we can go ahead and inline x.
--
-- For now we do nothing, because this would require putting
-- everything inside UniqSM.
--
-- One more variant of this (#7366):
--
-- [ y = e, y = z ]
--
-- If we don't want to inline y = e, because y is used many times, we
-- might still be tempted to inline y = z (because we always inline
-- trivial rhs's). But of course we can't, because y is equal to e,
-- not z.
We could use a UniqSupply to rename variables as outlined in the note above when picking up assignments, which would solve much of this problem.
We need a way to sort assignments such that every variable is assigned before use. We could use UniqDFM for this.
The other issue is that with the current approach of just walking the list of assignment's it's trivial to decide if we should retain/discard assignments from the list. But that seems an easier problem to solve.
All that seems doable. But it's important to note that large assignmentlists are somewhat rare, so it's possible that after all is said and done such a refactor is worse for the general case in the end. So I don't think this is a priority.
But if someone feels like taking a stab at this please do. Even a slightly worse general case might be acceptable if we can improve the worst case by a lot.