This PR illustrates that a fundamental analysis update was not performed
with the new loop unswitch. This update is also somewhat fundamental to
the core idea of the new loop unswitch -- we actually *update* the CFG
based on the unswitching. In order to do that, we need to update the
loop nest in addition to the domtree.
For some reason, when writing trivial unswitching, I thought that the
loop nest structure cannot be changed by the transformation. But the PR
helps illustrate that it clearly can. I've expanded this to a number of
different test cases that try to cover the different cases of this. When
we unswitch, we move an exit edge of a loop out of the loop. If this
exit edge changes which loop reached by an exit is the innermost loop,
it changes the parent of the loop. Essentially, this transformation may
hoist the inner loop up the nest.
I've added the simple logic to handle this reliably in the trivial
unswitching case. However, in the non-trivial case we have a harder
problem because we may be creating new sibling loops. I'm going to port
these test cases over to it to see if it too is missing some handling
for the hoisting, but the logic to implement it will likely need to be
a bit different, and similar to the logic we already use to hoist the
newly created sibling loops. Due to these differences, I'm sending this
out as a separate patch and then I'll send a follow-up that at least
adds test coverage and maybe adds the necessary logic, re-using what
I've added here if I see a good way to do that.
To better test this loop, could we have a test with deeper nesting going upward more than one loop nest? e.g. A < B < C < D, where D becomes nested in A after unswitch?