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

viren@wipro.wipsys.soft.net (Virendra Kumar Mehta) writes:
                                                  ___
                          ---------->/ \<----------
                          | \_1_/ |
                          | | |
                          | _v_ |
                          \__________/ \ |
                                                \_2_/ |
                                                    | |
                                                  _v_ |
                                                / \_________/
                                                \_3_/
|> 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?


Treat as nested loops. In general, when you share headers and the set of
nodes reachable from one back-edge is a subset of the nodes reachable from
some other back-edge, then the loops should be nested.


|> What are the advantages/disadvantages of the two schemes and what kind of
|> optimizations are affected ?


You can push stuff out of the {1,2} loop into {3}. In the example I move
the inner-loop-invariant stuff out, saving 10 executions of "log(x)":


    loop: loop:
        x = x + 1.0; x = x + 1.0;
        y = log(x); ---\ if( x < 10.0 ) goto loop;
        if( x < 10.0 ) goto loop; \--> y = log(x);
        z = z + sin(y); z = z + sin(y);
        if( x < 20.0 ) goto loop; if( x < 20.0 ) goto loop;
        ...use of z... ...use of z...


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


Sure you can. {1,2} always execute before {3}, so they execute AT LEAST as
many times {3}, perhaps more.
--
cliffc@cs.rice.edu -- Massively Scalar Compiler Group, Rice University
--

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