sched2 priorities and replacements

Hi,

I'm working on some insn latency changes in the s390 backend and noticed
a regression in the SPEC2006 bzip2 test case that was due to some insns
being scheduled differently.

The sequence in short form before my change is

;;      | insn | prio |
;;      |  823 |    1 | %r1=%r1+0x1                    nothing
;;      |  420 |    1 | %r3=zxn([%r1])                 nothing
;;      |  422 |    1 | [%r1]=%r7                      nothing
;;      |  421 |    0 | %r4=%r3                        nothing
;;      |  423 |    0 | %r7=%r3                        nothing
;;      |  428 |    0 | {pc={(%r6!=%r3)?L424:pc};clobber %cc;} nothing

sched2 detects a memory inc/ref that can be changed in order to get rid
of the dependency 823 -> 420.  After that insn 420 is selected and the
same happens for insn 422 before insn 823 is scheduled at third
position.  Actually, what promotes 420 to the first position in the
ready queue is not the priority but some of the tie breakers.

Now, after my change the situation looks like:

;;      | insn | prio |
;;      |  825 |    6 | %r1=%r1+0x1                    nothing
;;      |  420 |    4 | %r3=zxn([%r1])                 nothing
;;      |  422 |    3 | [%r1]=%r5                      nothing
;;      |  421 |    0 | %r4=%r3                        nothing
;;      |  423 |    0 | %r5=%r3                        nothing
;;      |  428 |    0 | {pc={(%r7!=%r3)?L424:pc};clobber %cc;} nothing
;;   --------------- forward dependences: ------------

The same inc/ref as before is detected but insn 825 still has the
highest priority and will be selected in the next cycle.  Subsequently,
the replacement is reverted and insn 420, 422 are scheduled.  This
introduces a data dependency 825 -> 420 that wasn't there before.

In haifa-sched.c:apply_replacement (), after applying the replacement,
the dependent insn (420) is updated and its scheduling properties are
reset.  Nothing happens with insn 825 however.  I would have expected
that its priority should be recomputed after breaking a dependency since
it is recursively determined by the priority of the dependent insns.

As a quick hack, I did

which prompts a recomputation of 825's priority and helps with my
regression (but doesn't get rid of it completely).  I haven't checked
any other test case but wanted to hear some opinions first.

This looks really basic and I'm rather sure I missed some other
scheduling part that could deal with this kind of situation.  Would
somebody mind elucidating?

Regards
 Robin

ping, any insight on this?

Regards
 Robin

On 10/4/18 9:54 AM, Robin Dapp wrote:
> Hi,
> 
> I'm working on some insn latency changes in the s390 backend and noticed
> a regression in the SPEC2006 bzip2 test case that was due to some insns
> being scheduled differently.
> 
> The sequence in short form before my change is
> 
> ;;      | insn | prio |
> ;;      |  823 |    1 | %r1=%r1+0x1                    nothing
> ;;      |  420 |    1 | %r3=zxn([%r1])                 nothing
> ;;      |  422 |    1 | [%r1]=%r7                      nothing
> ;;      |  421 |    0 | %r4=%r3                        nothing
> ;;      |  423 |    0 | %r7=%r3                        nothing
> ;;      |  428 |    0 | {pc={(%r6!=%r3)?L424:pc};clobber %cc;} nothing
> 
> sched2 detects a memory inc/ref that can be changed in order to get rid
> of the dependency 823 -> 420.  After that insn 420 is selected and the
> same happens for insn 422 before insn 823 is scheduled at third
> position.  Actually, what promotes 420 to the first position in the
> ready queue is not the priority but some of the tie breakers.
> 
> Now, after my change the situation looks like:
> 
> ;;      | insn | prio |
> ;;      |  825 |    6 | %r1=%r1+0x1                    nothing
> ;;      |  420 |    4 | %r3=zxn([%r1])                 nothing
> ;;      |  422 |    3 | [%r1]=%r5                      nothing
> ;;      |  421 |    0 | %r4=%r3                        nothing
> ;;      |  423 |    0 | %r5=%r3                        nothing
> ;;      |  428 |    0 | {pc={(%r7!=%r3)?L424:pc};clobber %cc;} nothing
> ;;   --------------- forward dependences: ------------
> 
> The same inc/ref as before is detected but insn 825 still has the
> highest priority and will be selected in the next cycle.  Subsequently,
> the replacement is reverted and insn 420, 422 are scheduled.  This
> introduces a data dependency 825 -> 420 that wasn't there before.
> 
> In haifa-sched.c:apply_replacement (), after applying the replacement,
> the dependent insn (420) is updated and its scheduling properties are
> reset.  Nothing happens with insn 825 however.  I would have expected
> that its priority should be recomputed after breaking a dependency since
> it is recursively determined by the priority of the dependent insns.
> 
> As a quick hack, I did
> 
> diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
> index 1fdc9df9fb2..1340f34ed9f 100644
> --- a/gcc/haifa-sched.c
> +++ b/gcc/haifa-sched.c
> @@ -4713,7 +4713,18 @@ apply_replacement (dep_t dep, bool immediately)
>        success = validate_change (desc->insn, desc->loc, desc->newval, 0);
>        gcc_assert (success);
> 
> +      rtx_insn *insn = DEP_PRO (dep);
> +      INSN_PRIORITY_STATUS (insn) = -1;
> +      sd_iterator_def sd_it;
> +      sd_it = sd_iterator_start (insn, SD_LIST_FORW);
> +      while (sd_iterator_cond (&sd_it, &dep))
> +       {
> +         DEP_COST (dep) = UNKNOWN_DEP_COST;
> +         sd_iterator_next (&sd_it);
> +       }
> +      priority (insn);
>        update_insn_after_change (desc->insn);
> +
>        if ((TODO_SPEC (desc->insn) & (HARD_DEP | DEP_POSTPONED)) == 0)
>         fix_tick_ready (desc->insn);
> 
> which prompts a recomputation of 825's priority and helps with my
> regression (but doesn't get rid of it completely).  I haven't checked
> any other test case but wanted to hear some opinions first.
> 
> This looks really basic and I'm rather sure I missed some other
> scheduling part that could deal with this kind of situation.  Would
> somebody mind elucidating?
It could well be an oversight.  Bernd S. doesn't chime in much these
days, so I don't necessarily think we'll get an answer from him.

In theory I think we're supposed to call update_insn_after_change.  I
see it doesn't twiddle INSN_PRIORITY_STATUS, but it does reset DEP_DOST,
INSN_COST and INSN_TICK.

So I'd see if we're calling update_insn_after_change appropriately.  And
if so, then I'd consider twiddling it to update INSN_PRIORITY_STATUS in
addition to the things it already does.

jeff