Re: Patch to loop finding code to calculate loop_depth info

[Jeffrey A Law <law at cygnus dot com>]

  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?

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

Once those two issues are resolved I believe the code can be installed.

--

We also need to be careful how we use this information.  Right now it is
possible for non-looping nodes to be physically inside a loop.  Here's a
rather famous example (the pterm_ops loop from eqntott):


.L6:
        movswl (%edi,%ebx,2),%ecx
        movswl (%esi,%ebx,2),%edx
        cmpl $2,%ecx
        jne .L7
        xorl %ecx,%ecx
.L7:
        cmpl $2,%edx
        jne .L8
        xorl %edx,%edx
.L8:
        cmpl %edx,%ecx
        je .L5
        jge .L10
        movl $-1,%eax
        jmp .L13
        .p2align 4,,7
.L10:
        movl $1,%eax
        jmp .L13
        .p2align 4,,7
.L5:
        incl %ebx
        cmpl %eax,%ebx
        jl .L6

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.

[ Long term we'll see those insns between jge .L10 and .L5 physically moved
  out of the loop, but until then we need to be careful. ]

jeff