Re: Shoud a subset loop with same header be inner ?

>viren@wipro.wipsys.soft.net (Virendra Kumar Mehta) writes:


> (1)
> ___
> ---------->/ \<----------
> | \___/ |
> | | |
> | | |
> | _v_ |
> \__________/ \ (2) |
> \___/ |
> | |
> | |
> _v_ |
> (3) / \_________/
> \___/


>This situation will arise, e.g. if there is a 'continue' in a while loop.
>My question is, should the loop {1, 2} be treated as an inner loop, nested
>in the outer loop {1, 2, 3} or should the two loops be treated as same?


I believe that {1,2} should be represented as the inner loop of the above
flowgraph. Node 3 is clearly dominated by node 2. I would also like to
believe that "standard" techniques for determining reduced flowgraphs would
detect this, such as using rP numbering to detect backedges etc., but I must
confess that I have forgotten the details of that code.


What the compiler might want to do in this case is insert a preheader
before node 1, say 0' and change the loop from 3->1 to go from 3->0'. This
would allow the usual optimizations to have a landing pad to move code out
of the innermost loop.


>I doubt if treating {1, 2} as an inner loop will serve much purpose, as we
>can't assume that it will execute a higher number of times than the outer
>loop.


Well in general it may make a difference. I could easily write code with
the dreaded GOTO statement to generate this flowgraph, with invariant code
in the innerloop that would be beneficial to "move out".


Regards,
    -- Steven. (steven.parker@acadiau.ca)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.