[Bug tree-optimization/42720] Problematic condition simplification logic at unswitch-loops pass

["jingyu at google dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #1 from jingyu at google dot com  2010-01-29 23:33 -------
The problem also exists on non-FDO use. So I changed the title of the bug.

Since unswitch-loop is set at -O3, I give -O3 to the command line. Parameter
"max-unswitch-level" means we only do unswitch-loop at most once.

$arm-eabi-g++ loop.cpp -O3 --param max-unswitch-level=0 -S

We can see from the assembly code that when "if (obj==0)", the empty loop is
not eliminated.

.LFB0:
        @ args = 0, pretend = 0, frame = 0
        @ frame_needed = 0, uses_anonymous_args = 0
        @ link register save eliminated.
        cmp     r1, #0
        stmfd   sp!, {r4, r5}
.LCFI0:
        mov     r3, r0
        ble     .L11
        cmp     r2, #0  <---"if (obj != 0)" is moved out of loop

        movne   r0, #0
        movne   ip, r0
        beq     .L5
...
.L5:
        add     r2, r2, #1 ;;  if (obj == 0), empty loop
        cmp     r2, r1     ;;
        bne     .L5        ;;
.L11:
        mov     r0, #0
        b       .L3


I made a mistake when I wrote the first bug report for this issue. The
problematic logic is on tree_unswitch_single_loop() (tree-ssa-loop-unswitch.c).

tree_unswitch_single_loop (loop, num):
  check if num > max-unswitch-level, return false.
  check if optimize_loop_for_size_p(loop), return false.
  check if loop is not innermost, return false.
  check if loop size > max_unswitch_insn, return false.
  while(1) {
    find a condition cond inside loop that can be unswitched.
    if cond can be simplified by loop entry checks, simplify cond and continue.
    Otherwise, break
  }
  unswitch loop. Now nloop is a copy of loop.
  ...
  tree_unswitch_single_loop (nloop, num+1);
  tree_unswitch_single_loop (loop, num+1);


Notice that after loop is unswitched, the conditions of loop and nloop are not
simplified. The condition simplification of nloop and loop are expected to be
done on the recursive call of tree_unswitch_single_loop(nloop, num+1), and
tree_unswitch_single_loop (loop, num+1). However, on the recursive call, if
something has changed and makes any "check" fail, the condition simplification
will not be done.

Ideally, we need to simplify loop and nloop conditions immediately after
unswitch. That is the correct thing we want to do. But given the current logic,
I am proposing another type of fix.

There are four checks at the beginning of tree_unswitch_single_loop(). Two
checks may fail during recursive calls:
  check if num > max-unswitch-level, return false.
  check if optimize_loop_for_size_p(loop), return false.

So I think we can simply move these two conditions after condition
simplification loop. It is always good to simplify conditions inside the loop
even if the loop is cold.

I pasted here the patch on gcc-4.4.0. I have tested the patch on the FDO case
and the -O3 case. The empty loop is gone in both cases.

185,192d184
<   /* Do not unswitch too much.  */
<   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
<     {
<       if (dump_file && (dump_flags & TDF_DETAILS))
<       fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
<       return false;
<     }
< 
201,208d192
<   /* Do not unswitch in cold regions.  */
<   if (optimize_loop_for_size_p (loop))
<     {
<       if (dump_file && (dump_flags & TDF_DETAILS))
<       fprintf (dump_file, ";; Not unswitching cold loops\n");
<       return false;
<     }
< 
254a239,254
>   /* Do not unswitch too much.  */
>   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
>     {
>       if (dump_file && (dump_flags & TDF_DETAILS))
>       fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
>       return false;
>     }
> 
>   /* Do not unswitch in cold regions.  */
>   if (optimize_loop_for_size_p (loop))
>     {
>       if (dump_file && (dump_flags & TDF_DETAILS))
>       fprintf (dump_file, ";; Not unswitching cold loops\n");
>       return false;
>     }
> 

Do you think if the patch would work?

Thanks!


-- 

jingyu at google dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |4.5.0 4.4.0
            Summary|Empty loop generated at     |Problematic condition
                   |unswitch-loops with -O2 -   |simplification logic at
                   |fprofile-use                |unswitch-loops pass


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42720