>> Suppose a loop as:
>>
>> void f (std::map<int, int> m)
>> {
>> for (auto it = m.begin (); it != m.end (); ++it) {
>> /* if (b) is semi-invariant. */
>> if (b) {
>> b = do_something(); /* Has effect on b */
>> } else {
>> /* No effect on b */
>> }
>> statements; /* Also no effect on b */
>> }
>> }
>>
>> A transformation, kind of loop split, could be:
>>
>> void f (std::map<int, int> m)
>> {
>> for (auto it = m.begin (); it != m.end (); ++it) {
>> if (b) {
>> b = do_something();
>> } else {
>> ++it;
>> statements;
>> break;
>> }
>> statements;
>> }
>>
>> for (; it != m.end (); ++it) {
>> statements;
>> }
>> }
> So if you consider approaching this from unswitching instead we'd
> unswitch it on if (b) but
> treat the condition as constant only in the 'false' path, thus the
> transformed code would
> look like the following. I believe implementing this in the existing
> unswitching pass
> involves a lot less code than putting it into the splitting pass but
> it would catch
> exactly the same cases?
May not.
Firstly, the following transformation is legal only when "b" is
semi-invariant, which means once a branch of "if (b)" is selected since
certain iteration, execution will always go to that branch in all following
iterations. Most of code in this loop-split patch was composed to check
semi-invariantness of a conditional expression, which must also be needed
in loop-unswitch solution.
Secondly, to duplicate/move an invariant expression out of loop is simple,
for all intermediate computations should already be outside, only need to
handle its result SSA that is inside the loop. But for semi-invariant, we
have to duplicate a tree of statements that contributes to computation of
the condition expression, similar to code hoisting, which make us write
extra code.
And loop-unswitch solution is weaker than loop-split. Suppose initial
value of "b" is true, and is changed to false after some iterations,
not only unswitch does not help that, but also it introduces extra cost
due to enclosing "if (b)".
> if (b)
> {
> for (auto it = m.begin (); it != m.end (); ++it) {
> /* if (b) is non-invariant. */
> if (b) {
> b = do_something(); /* Has effect on b */
> } else {
> /* No effect on b */
> }
> statements; /* Also no effect on b */
> }
> }
> else
> {
> for (auto it = m.begin (); it != m.end (); ++it) {
> /* if (b) is invariant. */
> if (false) {
> b = do_something(); /* Has effect on b */
> } else {
> /* No effect on b */
> }
> statements; /* Also no effect on b */
> }
> }
