[LLVM, loop-unswitch] Wrong behaviour for switches.

[kaomoneus]

Bugzilla Link	11429
Version	trunk
OS	All
Attachments	Example
CC	@asl,@hiraditya

Extended Description

Hello everybody. I found that LoopUnswitch pass process "switch" instruction for first case only. And after it was unswitched, it forgot about this switch. But what about all remained cases? Yes, we set up redoLoop for old Loop each time when it was unswitched, but it doesn't works.
The first reason is that we always try to unswitch FIRST case. Look at LoopUnswitch.cpp, string #​262. Though you can find several FIXMEs here:

// Find a value to unswitch on:
// FIXME: this should chose the most expensive case!
// FIXME: scan for a case with a non-critical edge?
Constant *UnswitchVal = SI->getCaseValue(1);

But I also found few hidden problems related to UnswitchedVals field...

Let's suppose we fixed the previous peace of code.
If I get right, inside the loop, for each check (icmp, switch, select) of loop-invariant-variable (LIC) we do the next:
We created new loop where LIC is replaced with constant. And we asked to redo the old loop, since there are probably exists another values to be unswitched. We also inserted previously unswitched value into UnswitchedVals field to prevent unswitching it again. Note, that it has type "SmallPtrSet<Value *,8>". Also note, that it will CLEARED after LoopUnswitch::runOnLoop finished. So, for new loops UnswitchedVals will EMPTY. Taking all these in account look at next example:

// Initial loop.
for (...) {
...
switch(c) {
case 0: A; break;
}
switch (d) {
case 0: D; break;
}
...
}

Let's unswitch it (1st stage):

if (c == 0)
for (...) {
...
switch (0) { // By now LoopUnswitch just replaces the condition.
case 0: A; break;
}
switch (d) {
case 0: D; break; // Will be unswitched.
}
}
else
for (...) { // Old loop. Will be proceed again (redoLoop = true for it).
...
switch(c) {
case 0: goto unreachable; // UnswitchedVals contains "0", will skipped.
}
switch (d) {
case 0: D; break; // Will skipped too! Since UnswitchedVals contains "0".
}
...
}

But that's not all. Let's suppose that we replaced the type of unswitched vals: "std::map<SwitchInst*, Value*>" instead of "SmallPtrSet<Value*>". And we determine that we need to unswitch second cycle (for "d" == 0). We got the next:

if (c==0)
...
else
if (d == 0)
for (...) { // New loop for "d".
...
switch(c) {
case 0: goto unreachable; // ERROR: UnswitchedVals is EMPTY! Will be unswitched again.
}
switch (0) {
case 0: D; break;
}
...
}
else
for (...) { // Old loop for "d". All is OK here.
switch(c) {
case 0: goto unreachable; // UnswitchedVals["switch(c)"] contains "0", will skipped.
}
switch (0) {
case 0: goto unreachable; // UnswitchedVals["switch(d)"] contains "0", will skipped.
}
}

I propose:

1. Replace type of unswitched vals.
2. Clone what-was-unswitched-info for new cycle.

P.S.: Run "opt -S -loop-unswitch " for attachment to see how this problems are appeared now.

[kaomoneus]

assigned to @kaomoneus