A question about df_get_live_in

A question about df_get_live_in

[Kaz Kojima]

Hi,

I hope DF/middle-end experts will comment about this.

PR target/40710
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40710

is a wrong code problem on SH.  A delayed slot of a conditional
branch insn is wrongly filled with an insn changing stack pointer
in the failing case.  I've tried to see what is going on.

Before the dbr optimization, the code looks like as

(note 6 1 5 [bb 2] NOTE_INSN_BASIC_BLOCK)
...
(jump_insn 13 12 31 fs/ext3/balloc.c:57 (set (pc)
        (if_then_else (eq (reg:SI 147 t)
                (const_int 0 [0x0]))
            (label_ref:SI 129)
            (pc))) 208 {branch_false} (expr_list:REG_DEAD (reg:SI 147 t)
        (expr_list:REG_BR_PROB (const_int 184 [0xb8])
            (nil))))

(note 31 13 46 [bb 3] NOTE_INSN_BASIC_BLOCK)

(note 46 31 32 NOTE_INSN_DELETED)

(insn 32 46 35 fs/ext3/balloc.c:66 (parallel [
            (asm_operands/v ("") ("") 0 []
                 [] 2935777)
            (clobber (mem:BLK (scratch) [0 A8]))
        ]) -1 (nil))
...
...
(barrier 126 125 129)

(code_label 129 126 14 9 "" [1 uses])

(note 14 129 109 [bb 8] NOTE_INSN_BASIC_BLOCK)

(insn 109 14 15 fs/ext3/balloc.c:58 (set (reg/f:SI 1 r1 [176])
        (mem/u/c:SI (label_ref 146) [0 S4 A32])) 172 {movsi_ie} (expr_list:REG_EQUIV (symbol_ref:SI ("ext3_error") [flags 0x41] <function_decl 0xb7a28d80 ext3_error>)
        (nil)))

(insn 15 109 24 fs/ext3/balloc.c:58 (set (reg/f:SI 15 r15)
        (plus:SI (reg/f:SI 15 r15)
            (const_int -4 [0xfffffffffffffffc]))) 35 {*addsi3_compact} (nil))

reorg.c:fill_slots_from_thread fills that delay slot of insn 13
with insn 15 from bb 8.  Since r15 is the stack pointer register
for SH, this fill makes it wrong when the conditional jmp isn't
taken.  fill_slots_from_thread computes the resource set for
the follow-through block of that jmp insn with

  mark_target_live_regs (get_insns (), opposite_thread, &opposite_needed);

and mark_target_live_regs uses df_get_live_in to get live regs
for the basic block including the opposite_thread insn which is
insn 32.  gdb shows the resulting opposite_needed is

$1 = {memory = 0x1, unch_memory = 0x0, volatil = 0x0, cc = 0x0,
      regs = {0xf6,  0x0, 0x0, 0x0, 0x40000}}

i.e. it seems that df_get_live_in doesn't count r15 as an live
register and fill_slots_from_thread picks insn 15 up as
an eligible insn to fill that delayed slot.
Is this the expected behavior of df_get_live_in?  If so, is
there something problematic in the target?

I thought that the stack pointer register should be live here.
The first part of DF dump in .compgotos which is the last dump
before dbr pass is:

;; Start of basic block ( 0) -> 2
;; bb 2 artificial_defs: { }
;; bb 2 artificial_uses: { u-1(15){ }}
;; lr  in        4 [r4] 5 [r5] 6 [r6] 15 [r15] 146 [pr] 151 []
;; lr  use       4 [r4] 5 [r5] 15 [r15] 146 [pr]
;; lr  def       1 [r1] 2 [r2] 3 [r3] 15 [r15] 147 [t]
;; live  in      4 [r4] 5 [r5] 6 [r6] 146 [pr]
;; live  gen     1 [r1] 2 [r2] 3 [r3] 15 [r15] 147 [t]
;; live  kill   
...
;; End of basic block 2 -> ( 8 3)
;; lr  out       1 [r1] 2 [r2] 3 [r3] 4 [r4] 5 [r5] 6 [r6] 15 [r15] 151 []
;; live  out     1 [r1] 2 [r2] 3 [r3] 4 [r4] 5 [r5] 6 [r6] 15 [r15]
...
;; Start of basic block ( 2) -> 3
;; bb 3 artificial_defs: { }
;; bb 3 artificial_uses: { u-1(15){ }}
;; lr  in        1 [r1] 2 [r2] 4 [r4] 5 [r5] 6 [r6] 15 [r15] 151 []
;; lr  use       1 [r1] 2 [r2] 5 [r5] 15 [r15]
;; lr  def       0 [r0] 1 [r1] 2 [r2] 3 [r3] 7 [r7] 147 [t]
;; live  in      1 [r1] 2 [r2] 4 [r4] 5 [r5] 6 [r6] 15 [r15]
;; live  gen     0 [r0] 1 [r1] 2 [r2] 3 [r3] 7 [r7] 147 [t]
;; live  kill   
...
;; End of basic block 3 -> ( 9 4)
;; lr  out       1 [r1] 2 [r2] 4 [r4] 5 [r5] 6 [r6] 7 [r7] 15 [r15] 151 []
;; live  out     1 [r1] 2 [r2] 4 [r4] 5 [r5] 6 [r6] 7 [r7] 15 [r15]

Regards,
	kaz

Re: A question about df_get_live_in

[Steven Bosscher]

On Mon, Jul 13, 2009 at 11:46 PM, Kaz Kojima<kkojima@rr.iij4u.or.jp> wrote:
> Hi,
>
> I hope DF/middle-end experts will comment about this.
>
> PR target/40710
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40710
>
> is a wrong code problem on SH.  A delayed slot of a conditional
> branch insn is wrongly filled with an insn changing stack pointer
> in the failing case.  I've tried to see what is going on.

You found out why the dbr-sched pass (reorg.c) needs a rewrite so
badly. DF needs a CFG, and reorg.c refuses to maintain a valid CFG. In
other words, it just doesn't work very well together.  See PR39938,
PR40086, etc...

Basically, as long as on-one is willing to put up the resources to
beat sense into reorg.c, you'll probably continue to find bugs related
to delay slot filling.


Anyway, the bug here is probably somewhere between .compgotos and
reorg, because from your dump we have:

;; Start of basic block ( 0) -> 2
;; live  in      4 [r4] 5 [r5] 6 [r6] 146 [pr]
;; live  out     1 [r1] 2 [r2] 3 [r3] 4 [r4] 5 [r5] 6 [r6] 15 [r15]

;; Start of basic block ( 2) -> 3
;; live  in      1 [r1] 2 [r2] 4 [r4] 5 [r5] 6 [r6] 15 [r15]
;; live  out     1 [r1] 2 [r2] 4 [r4] 5 [r5] 6 [r6] 7 [r7] 15 [r15]

So when the CFG is still valid, r15 is live-out in basic block 2 and
live-in in basic block 3 (which contains insns 32, whatever that means
for an invalid CFG). For which bb does mark_target_live_regs call
df_get_live_in?

Ciao!
Steven

Re: A question about df_get_live_in

[Kaz Kojima]

[I'd like to add kenny to the CC list.]

Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> So when the CFG is still valid, r15 is live-out in basic block 2 and
> live-in in basic block 3 (which contains insns 32, whatever that means
> for an invalid CFG). For which bb does mark_target_live_regs call
> df_get_live_in?

gdb says

920         b = find_basic_block (target, MAX_DELAY_SLOT_LIVE_SEARCH);

returns 2.

Regards,
	kaz

Re: A question about df_get_live_in

[Steven Bosscher]

On Tue, Jul 14, 2009 at 1:17 AM, Kaz Kojima<kkojima@rr.iij4u.or.jp> wrote:
> [I'd like to add kenny to the CC list.]

I doubt he can help you with this one...  When your problem concerns
reorg, you should talk to people like Eric Botcazou or Richard
Sandiford or HP Nillson.  I've added Eric to the CC, to make this a
happier crowd. :-)


> Steven Bosscher <stevenb.gcc@gmail.com> wrote:
>> So when the CFG is still valid, r15 is live-out in basic block 2 and
>> live-in in basic block 3 (which contains insns 32, whatever that means
>> for an invalid CFG). For which bb does mark_target_live_regs call
>> df_get_live_in?
>
> gdb says
>
> 920         b = find_basic_block (target, MAX_DELAY_SLOT_LIVE_SEARCH);
>
> returns 2.

OK, so isn't the bug obvious then? You said: "mark_target_live_regs
uses df_get_live_in to get live regs for the basic block including the
opposite_thread insn which is insn 32.". And you had insn 32 in basic
block 3. So find_basic_block returns the wrong basic block.

reorg.c:find_basic_block uses BLOCK_FOR_INSN, which is not valid after
freeing the CFG. The bug you see occurs now because your backport of
the other DF/reorg fixes (your patch for PR40105) also introduces a
call to free_bb_for_insn which clears BLOCK_FOR_INSN.  And since
find_basic_block skips over NOTE_INSN_BASIC_BLOCK notes (it uses
{prev,next}_nonnote_insn) and basic block 3 doesn't start with a
label, find_basic_block never sees the start of basic block 3.

I am not even sure why it finds basic block 2. Is there a label in
basic block 2 that you were not showing in the original post?

Why does find_basic_block ignore NOTE_INSN_BASIC_BLOCK notes?

Ciao!
Steven

Re: A question about df_get_live_in

[Eric Botcazou]

> I doubt he can help you with this one...  When your problem concerns
> reorg, you should talk to people like Eric Botcazou or Richard
> Sandiford or HP Nillson.  I've added Eric to the CC, to make this a
> happier crowd. :-)

Thank you.  I was about to leave for vacation but I'll stay for this one. :-)

> reorg.c:find_basic_block uses BLOCK_FOR_INSN, which is not valid after
> freeing the CFG. The bug you see occurs now because your backport of
> the other DF/reorg fixes (your patch for PR40105) also introduces a
> call to free_bb_for_insn which clears BLOCK_FOR_INSN.  And since
> find_basic_block skips over NOTE_INSN_BASIC_BLOCK notes (it uses
> {prev,next}_nonnote_insn) and basic block 3 doesn't start with a
> label, find_basic_block never sees the start of basic block 3.

The call to free_bb_for_insn was already there and init_resource_info resets 
BLOCK_FOR_INSN before using them.  I'll look into this too tomorrow.

-- 
Eric Botcazou

Re: A question about df_get_live_in

[Kaz Kojima]

Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> OK, so isn't the bug obvious then? You said: "mark_target_live_regs
> uses df_get_live_in to get live regs for the basic block including the
> opposite_thread insn which is insn 32.". And you had insn 32 in basic
> block 3. So find_basic_block returns the wrong basic block.
> 
> reorg.c:find_basic_block uses BLOCK_FOR_INSN, which is not valid after
> freeing the CFG. The bug you see occurs now because your backport of
> the other DF/reorg fixes (your patch for PR40105) also introduces a
> call to free_bb_for_insn which clears BLOCK_FOR_INSN.  And since
> find_basic_block skips over NOTE_INSN_BASIC_BLOCK notes (it uses
> {prev,next}_nonnote_insn) and basic block 3 doesn't start with a
> label, find_basic_block never sees the start of basic block 3.

Ugh.

> I am not even sure why it finds basic block 2. Is there a label in
> basic block 2 that you were not showing in the original post?

There are no labels in basic block2.  gdb says it hits the start
of the function and returns with

150       else if (insn == 0)
151         return ENTRY_BLOCK_PTR->next_bb->index;

> Why does find_basic_block ignore NOTE_INSN_BASIC_BLOCK notes?

The same question arises to me.

Regards,
	kaz

Re: A question about df_get_live_in

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 2431 bytes --]

> > Why does find_basic_block ignore NOTE_INSN_BASIC_BLOCK notes?
>
> The same question arises to me.

That's explained in the head comment of find_basic_block: the CFG is destroyed 
by the DBR pass in some controlled way so the strategy is to recompute the 
liveness info starting from data that are still correct given the properties 
of the aforementioned controlled way.

Here we start from the beginning of the function for insn 32 with

;; Start of basic block ( 0) -> 2
;; bb 2 artificial_defs: { }
;; bb 2 artificial_uses: { u-1(15){ }}
;; lr  in        4 [r4] 5 [r5] 6 [r6] 15 [r15] 146 [pr] 151 []
;; lr  use       4 [r4] 5 [r5] 15 [r15] 146 [pr]
;; lr  def       1 [r1] 2 [r2] 3 [r3] 15 [r15] 147 [t]
;; live  in      4 [r4] 5 [r5] 6 [r6] 146 [pr]
;; live  gen     1 [r1] 2 [r2] 3 [r3] 15 [r15] 147 [t]
;; live  kill  

and run into

(insn/f 111 8 112 fs/ext3/balloc.c:51 (set (mem:SI (pre_dec:SI (reg/f:SI 15 
r15)) [0 S4 A32])
        (reg:SI 146 pr)) 171 {movsi_i} (expr_list:REG_DEAD (reg:SI 146 pr)
        (expr_list:REG_INC (reg/f:SI 15 r15)
            (nil))))


The problem is that resource.c is doing life analysis the old fashioned way, 
i.e. the LR way, with a mere

	      note_stores (PATTERN (real_insn), update_live_status, NULL);

which doesn't take into account PRE_DEC because the register is supposed to be 
live before the PRE_DEC.  It's true for LR but not for LIVE, as the use of the 
stack pointer is considered artificial by the latter.


So I made a mistake when changing back the DF problem to LIVE in

2009-04-27  Richard Sandiford  <rdsandiford@googlemail.com>
            Eric Botcazou  <ebotcazou@adacore.com>

	* resource.c (find_basic_block): Use BLOCK_FOR_INSN to look up
	a label's basic block.
	(mark_target_live_regs): Tidy and rework obsolete comments.
	Change back DF problem to LIVE.  If a label starts a basic block,
	assume that all registers that used to be live then still are.
	(init_resource_info): If a label starts a basic block, set its
	BLOCK_FOR_INSN accordingly.
	(fini_resource_info): Undo the setting of BLOCK_FOR_INSN.

it should be reset to LR.

Patch attached.  I'll give it a whirl on SPARC but not immediately so, Kaz, if 
you can test it on SH in the meantime, you can apply it on all branches.


2009-07-14  Eric Botcazou  <ebotcazou@adacore.com>

	PR rtl-optimization/40710
	* resource.c (mark_target_live_regs): Reset DF problem to LR.


-- 
Eric Botcazou

[-- Attachment #2: pr40710.diff --]
[-- Type: text/x-diff, Size: 1107 bytes --]

Index: resource.c
===================================================================
--- resource.c	(revision 149515)
+++ resource.c	(working copy)
@@ -948,10 +948,11 @@ mark_target_live_regs (rtx insns, rtx ta
 
   /* If we found a basic block, get the live registers from it and update
      them with anything set or killed between its start and the insn before
-     TARGET.  Otherwise, we must assume everything is live.  */
+     TARGET; this custom life analysis is really about registers so we need
+     to use the LR problem.  Otherwise, we must assume everything is live.  */
   if (b != -1)
     {
-      regset regs_live = df_get_live_in (BASIC_BLOCK (b));
+      regset regs_live = DF_LR_IN (BASIC_BLOCK (b));
       rtx start_insn, stop_insn;
 
       /* Compute hard regs live at start of block.  */
@@ -1055,7 +1056,7 @@ mark_target_live_regs (rtx insns, rtx ta
 		{
 		  HARD_REG_SET extra_live;
 
-		  REG_SET_TO_HARD_REG_SET (extra_live, df_get_live_in (bb));
+		  REG_SET_TO_HARD_REG_SET (extra_live, DF_LR_IN (bb));
 		  IOR_HARD_REG_SET (current_live_regs, extra_live);
 		}
 	    }

Re: A question about df_get_live_in

[Kaz Kojima]

Eric Botcazou <ebotcazou@adacore.com> wrote:
> Patch attached.  I'll give it a whirl on SPARC but not immediately so, Kaz, if 
> you can test it on SH in the meantime, you can apply it on all branches.
> 
> 
> 2009-07-14  Eric Botcazou  <ebotcazou@adacore.com>
> 
> 	PR rtl-optimization/40710
> 	* resource.c (mark_target_live_regs): Reset DF problem to LR.

Thanks for taking a look at this!  I've just fired the tests
with it on sh4-unknown-linux-gnu.

Regards,
	kaz

Re: A question about df_get_live_in

[Jeff Law]

Steven Bosscher wrote:
> On Mon, Jul 13, 2009 at 11:46 PM, Kaz Kojima<kkojima@rr.iij4u.or.jp> wrote:
>   
>> Hi,
>>
>> I hope DF/middle-end experts will comment about this.
>>
>> PR target/40710
>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40710
>>
>> is a wrong code problem on SH.  A delayed slot of a conditional
>> branch insn is wrongly filled with an insn changing stack pointer
>> in the failing case.  I've tried to see what is going on.
>>     
>
> You found out why the dbr-sched pass (reorg.c) needs a rewrite so
> badly. DF needs a CFG, and reorg.c refuses to maintain a valid CFG. In
> other words, it just doesn't work very well together.  See PR39938,
> PR40086, etc...
>   
I think most of reorg's issues go away if it were changed to use the 
same dependency information that we build for the schedulers rather than 
trying to build it in an ad-hoc fashion on the fly.  As an added benefit 
it would be a hell of a lot faster.
Jeff