Question on param MAX_PENDING_LIST_LENGTH in sched-deps

[Jeff Law]

On 11/04/14 20:29, Bin.Cheng wrote:
> Hi,
> The parameter MAX_PENDING_LIST_LENGTH is set to 32 by default.  It
> seems to me the length of pending list can't be larger than 32.  But
> in sched-deps.c, below code is used:
>        /* Pending lists can't get larger with a readonly context.  */
>        if (!deps->readonly
>            && ((deps->pending_read_list_length + deps->pending_write_list_length)
>                > MAX_PENDING_LIST_LENGTH))
>
> Since we compares it using ">", the list can have 33 instructions at
> most, which is inconsistent with the parameter name.
>
> Well, it's some kind of nit picking.
Yea, seems like a bit of a nit.  Might be worth fixing as someone might 
size an array based on the param's value only to find out it can have an 
extra element.

>
> Another question.  This parameter is introduced to prevent GCC from
> running for too long time.  I am not clear if the running time is a
> quadratic function of pending list, or a quadratic function of
> dependency nodes?  If it's the latter, could we use the number of
> dependency nodes as the parameter directly?  Because in some cases
> like memory initialization, there are more than 32 store instructions
> in flow, but the dependency are actually very simple.
See:

https://gcc.gnu.org/ml/gcc-patches/2001-07/msg01668.html

I don't recall what part of the algorithm was quadratic, but it should 
be too hard to find out given the thread references the target & the 
testcase.

jeff