Re: Help w/ CFG/loop optimization problem?

[Jeff Law <law at porcupine dot slc dot redhat dot com>]

In message <A21CD16A-C4F8-11D6-93B1-003065C86F94@apple.com>, Dale Johannesen wr
ites:
 >I've run into an optimization problem with
 >
 >     if (count > 10)
 >         for (i = 0; i < count; ++i)
 >             pcb += i;
 >     else...
It'd really help to have a compilable example.  

 >Basically what happens is the unconditional branch from the 'else'
 >is brought inside the loop by cfg, which prevents the doloop
 >optimization from recognizing this as a valid doloop.  I'm not
 >sure where best to fix this; cfg doesn't seem to know much of
 >anything about loops, and pushing the unconditional branch outside
 >the loop seems outside the loop optimizer's normal view of things.
 >Advice?
Why precisely is the loop not recognized as a valid doloop?   Is it
because we think we have multiple exits from the loop?  Again, the full
dump file and a compilable source example would be helpful.


 >RTL before cfg:
 >(note 27 25 28 NOTE_INSN_LOOP_CONT)
 >
 >(code_label 28 27 74 3 5 "" [0 uses])
 >
 >(note 74 28 29 3 [bb 3] NOTE_INSN_BASIC_BLOCK)
 >
 >(insn 29 74 17 3 0x0 (set (reg/v:SI 121)
 >         (plus:SI (reg/v:SI 121)
 >             (const_int 1 [0x1]))) -1 (nil)
 >     (nil))
 >
 >(code_label 17 29 75 4 3 "" [1 uses])
 >
 >(note 75 17 18 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
 >
 >(insn 18 75 19 4 0x0 (set (reg:CC 123)
 >         (compare:CC (reg/v:SI 121)
 >             (reg/v:SI 118))) -1 (nil)
 >     (nil))
 >
 >(jump_insn 19 18 76 4 0x0 (set (pc)
 >         (if_then_else (lt (reg:CC 123)
 >                 (const_int 0 [0x0]))
 >             (label_ref 22)
 >             (pc))) -1 (nil)
 >     (nil))
 >
 >(note 76 19 20 5 [bb 5] NOTE_INSN_BASIC_BLOCK)
 >
 >(jump_insn 20 76 21 5 0x0 (set (pc)   ... this branch exits the loop
 >         (label_ref 36)) -1 (nil)
 >     (nil))
 >
 >(barrier 21 20 22)
 >
 >(code_label 22 21 77 6 6 "" [1 uses])
 >
 >(note 77 22 33 6 [bb 6] NOTE_INSN_BASIC_BLOCK)
 >
 >(jump_insn 33 77 34 6 0x0 (set (pc)
 >         (label_ref 30)) -1 (nil)
 >     (nil))
 >
 >(barrier 34 33 35)
 >
 >(note 35 34 36 NOTE_INSN_LOOP_END)
 >
 >(code_label 36 35 78 7 4 "" [1 uses])
 >
 >(note 78 36 37 7 [bb 7] NOTE_INSN_BASIC_BLOCK)
 >
 >(jump_insn 37 78 38 7 0x0 (set (pc)     ... and is changed to point to 
 >63 instead of 36
 >         (label_ref 63)) -1 (nil)
 >     (nil))
 >
 >If insn 20 were not changed, it would branch to the next instruction
 >and would be removed, leaving the loop in a clean form.
?!?  It wouldn't branch to the next instruction because of the jump at
insn #33.  Unless that's optimized away.

>From looking at the post-cfg rtl, we thread the jump at insn 19, that
in turn makes the jump at 33 dead.  So indeed we could have just
zapped insn 20 had it not been mucked up.

One potential solution would be to first follow jumps without changing
the loop nest level of the targets.  That would result in the following
transformations:

The jump insn at 19 would be threaded to (code_label 30) [Assuming that
label is at the same loop nest].

That would then make insn 20 jump to the next instruction, so we could
delete it, which would make doloop happy.

I have another theory on how to fix this, but I'd need compilable 
sample code to know if my theory actually works.

jeff