This is the mail archive of the
mailing list for the GCC project.
Re: [PATCH] Rework description of DFA scheduler's max_issue()
- From: Vladimir Makarov <vmakarov at redhat dot com>
- To: Eric Botcazou <ebotcazou at libertysurf dot fr>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Thu, 05 Jun 2003 14:26:32 -0400
- Subject: Re: [PATCH] Rework description of DFA scheduler's max_issue()
- References: <firstname.lastname@example.org> <3EDCD57A.D3EF3A7D@redhat.com> <email@example.com>
Eric Botcazou wrote:
> > The algorithm has been reworked already. The solution is on the main
> > line. The complexity of the algorithm has been decreased significantly
> > (in several thousand times for the test case).
> Unfortunately that's not enough to fix the regression: the testcase takes at
> least 20 minutes (I stopped it) on mainline 20030528 with a cross-compiler
> from x86, so imagine on HyperSPARC...
I've reproduced it too. The major problem is in that some insns have
no reservations for hypersparc. When I wrote the function I did not
expect it. My algorithm should be more bulletproof. I am going to
submit the patch for the main line today or tomorrow to solve the
> > The idea of the algorithm is good (and it really improves code, e.g. 2%
> > for SPEICNT2000 for itanium). But the implementation still should be
> > better (insn scheduling complexity can not be less power of two, the
> > current worst case complexity of max_issue is of power maxlookahead).
> That's precisely what I'd like to be added to the description of the
> function: that MAX_LOOKAHEAD**n is the expected worst case behaviour.
The complexity of algorithm in the main line is
MAX_LOOKAHEAD**ISSUE_RATE that was I aimed at. This complexity is true
when all insns processed by max_issue have reservations. I discard
insns whose code is negative (usually they are clobbers and uses) for
this. But I did not expect descriptions in which real insns have
reservation 'nothing' (as in hypersparc). I apologize for this.
> > Another approach is to constrain numbers of tries (I guess that is what
> > you probably working on).
> No, I'm trying to fix the scheduler description for HyperSPARC because I
> think it is the culprit: all the arithmetic instructions are simply not
> taken into account. Declaring a reservation for them makes the problem go
> > It is shame for me that I still did not implement this (but I don't see
> > there is such problem for new max_issue variant on all tests which I tried
> > including yours).
> Hum... are you sure you compiled for HyperSPARC?
No, I've not compiled it for hypersparc. I compiled many tests for
Itanium which has bigger lookahead than sparc. As I wrote if hypersparc
has reservations for all insns, there would be no problem. I apologize
for this, the algorithm should be bulletproof for any correct