This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: RFC: mips SB-1 DFA scheduler

On Thu, 2004-03-04 at 06:57, Paul Koning wrote:
> My best interpretation is that this hook says how far to look ahead in
> the queue of ready instructions to find the ones that will be issued
> this cycle.  And it seems pretty obvious that you can't rearrange
> instruction issue for a quad issue machine unless you look at
> substantially MORE than 4 ready instructions, right?  Otherwise you're
> basically just issuing FIFO.  That can't be right.  So what am I
> missing? 

A number of target files that define the lookahead hook claim that it is
a measure of the scheduling freedom in the DFA.  This is the
interpretation that I am using.  Once we have 4 instructions that we
want to execute, we need to try all possible permutations of those 4
instructions, otherwise, we may not be able to issue all of them.  This
is because some instructions can only issue to certain units, while
others can issue to multiple units.  A target with fully symmetric or
fully asymmetric units would not need to define the lookahead hook, as
there would be no need to reorder insns before issuing them.

However, I have not studied the code that uses the lookahead hook in
detail, so I can not definitively say that this is correct.

lookahead isn't the number of instructions we look at on the ready
queue.  There is a comment in haifa-sched.c that says
/* The following variable value is maximal number of tries of issuing
   insns for the first cycle multipass insn scheduling.  We define
   this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE).  We would not
   need this constraint if all real insns (with non-negative codes)
   had reservations because in this case the algorithm complexity is
   O(DFA_LOOKAHEAD**ISSUE_RATE).  Unfortunately, the dfa descriptions
   might be incomplete and such insn might occur.  For such
   descriptions, the complexity of algorithm (without the constraint)
   could achieve DFA_LOOKAHEAD ** N , where N is the queue length.  */
The constant appears to be 100.

I don't really see much benefit to investigating this issue any farther,
since my use is consistent with other targets, and I am not aware of any
problems with my use of this hook.  I may spend some time playing with
this number to see if it affects performance.

If it is just the comment that you find confusing, then I can fix that. 
I could replace the current wording with the "scheduling freedom"
wording that is found in other files.

> You can find it here:

Thanks.  I wasn't aware of this.  It looks like Eric asked Chris to
indicate when it was finished, and Chris never said it was finished, so
it never got checked in.

The handling of simple alu instructions appears to be wrong.  There are
two define_insn_reservation's that match simple alu instructions, but
the docs say that the result is undefined when you do this.  There needs
to be a single define_insn_reservation.  Unfortunately, this means we
can't get the latencies right, at least not without a lot of extra work
that I don't plan to do.

This has function units for the hi/lo regs, so we can block multiplies
and divides from issuing together.  I was thinking that normal data
dependencies would cover this.  We can't issue a multiply in parallel
with a divide because the rtl patterns for both indicate that they both
need the hi/lo regs, so the scheduler should already know that they
conflict.  However, I should probably double check this.

Otherwise, they look similar, except that mine has a lot more detail.

If you have any empirical results that show that this DFA scheduler
gives better code than the one I offered, then I would be interested in
seeing that.  I would hope that mine works better because it has more
Jim Wilson, GNU Tools Support,

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]