[LLVMbugs] [Bug 11429] New: [LLVM, loop-unswitch] Wrong behaviour for switches.

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=11429

             Bug #: 11429
           Summary: [LLVM, loop-unswitch] Wrong behaviour for switches.
           Product: tools
           Version: trunk
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: opt
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: stpworld at narod.ru
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


Created attachment 7642
  --> http://llvm.org/bugs/attachment.cgi?id=7642
Example

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 <example>" for attachment to see how this
problems are appeared now.

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.