Re: Patch to loop finding code to calculate loop_depth info

[Jan Hubicka <hubicka at atrey dot karlin dot mff dot cuni dot cz>]

> 
>   In message <19991203003217.03624@atrey.karlin.mff.cuni.cz>you write:
>   > This is patch to new loop finding code to also recalculate loop depth
>   > information to basic block headers.
> It's usually called "loop discovery" or "loop detection".
> 
>   > First I wanted to implement it as separate function using the loop
>   > structures but it seems that body is available only as bitmap and it is not
>   > very well suitable for my purposes, also info is very readily available
>   > during the calculation.
>   > So this seems to be easiest solution.
> Agreed.  One of the properties of a depth first traversal of the CFG is that
> the DFS will find innermost loops first, then work its way out to outer loops.
> 
> Most code tends to initialize the loop depth of a block to zero, not
> one.  Is there some reason you initialized the loop depth of non-looping blocks
> to one?

It is. The loop_depth as defined by code calculating N_REFS uses multiplication
by loop_depth to get weighted number of references. Using zero there will cause
instructions outside loops to be never noticed.  Fact is, that our current
behaviour about loop depth is incosistent. I've choosed "1 base", because code
currently using loop_depth field (N_REFS counter) expect it so.  Because you
are the maitainer and you have to take a look to keep thinks to sync, I think
it is up to you to decide what definition is more natural to you.

I will implement any of it.
> 
> Second, it is non-obvious why your code works; in fact I initially thought it
> was wrong!  You should add a comment explaining why the code is correct.
> 
> [ ie, as we work from inner->outer in a loop nest we call find_loop_nodes_find
>   which will increment loop_depth for nodes within the current loop, which
>   happens to enclose inner loops. ]

OK. I will use this text as comment before the clearing code OK?

> Note how the code from jge .L10 up to the label .L5  is not part of the
> looping structure (ie, once we hit jge .L10 we exit the loop).  With the
> old way of computing loop depth all the insns shown will have the same
> loop depth, that is not true with the new code because the block starting
> with .L10 is not part of the natural loop starting at .L6.
> 
> I do not think it matters for current uses, but it is something we need to
> be aware of.

I think so. Current users are register allocators only and there it can improve
the code.

Thank you for reviewing my code...

Honza