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

[Vladimir Makarov <vmakarov at redhat dot com>]

Eric Botcazou wrote:
> 
> Hi again Vlad,
> 
> In the process of investigating PR bootstrap/10835 (which I've narrowed down
> to an overly optimistic DFA scheduler description for HyperSPARC), I've
> stumbled upon max_issue(), which is a very interesting beast :-)
> 

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).

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). 
The best approach is to use a dynamic programming (reuse of solution of
subtasks for max_issue during max_issue call or even during one cycle). 
Another approach is to constrain numbers of tries (I guess that is what
you probably working on).  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).

> (And now I remember that you indirectly mentioned it in the course of the
> discussion of PR optimization/10160, the infamous compile time explosion bug
> caused by the tree inliner on SPARC).
> 
> The in-file description of max_issue() is a bit terse and, more importantly,
> it doesn't mention that the function can exhibit exponential behaviour in
> case of a broken scheduler description. Therefore I've reworked it. And in
> the process I've also renamed the 'best' variable into 'max' because 'best'
> is really misleading (it has nothing to do with the best insn).
> 
> (Of course, PR bootstrap/10835 is an example of the exponential behaviour
> with MAX_LOOKAHEAD==3 and n==20).
>
> Compiled on i586-redhat-linux-gnu. I'm requesting approval for mainline and
> 3.3 branch as the first part of the fix for the aforementioned PR which is
> of course a regression from GCC 3.2.x.
> 
> --
> Eric Botcazou
> 
> 2003-05-31  Eric Botcazou  <ebotcazou@libertysurf.fr>
> 
>         PR bootstrap/10835
>         * haifa-sched.c (max_issue): Rework description and mention
>         worst case behaviour. Rename 'best' automatic variable into 'max'.
> 

The best way is to use new max_issue implementation from the main line. 
Thanks for reporting the problem (what I was afraid of the previous
variant of max_issue has really happened).

Vlad