Re: [PATCH] Rework description of DFA scheduler's max_issue()

[Vladimir Makarov <vmakarov at redhat dot 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
problem.
 
> > 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
> away.
> 
> > 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
description.


Vlad