Re: loops

I've looked at this problem a little; part of the problem is defining just
when to add a header node. The example given:


do{
do{
stuff
}while(stuff);
}while(stuff);


can be disambiguated if the front end adds a CFG node for the inner do.
In structured code, even if there is only one header node, the inner/outer
relationship can be disambiguated, as mentioned. In unstructured graphs,
however, truly ambiguous relationships can be derived. For instance, how
to define inner/outer relationships of:


stuff1
if( more ) then
stuff 2
if( other ) goto stuff1
else
stuff3
if( stillother) goto stuff1
endif


so the CFG has the shape:


                    |
      ____ | _________
  / \ | / \
| stuff1 |
| | |
| | |
| more |
| / \ |
| / \ |
| stuff2 stuff3 |
| | | |
| other stillother |
  \/ \ / \/
                  \ /
                    |
                    |


The loop header is 'stuff1', and there are two back edges, but there is no
rhyme nor reason to choose one back edge as the inner over the other.


Another interesting case is:


stuff1
stuff2
if( s2 ) goto stuff1
stuff3
if( s3 ) goto stuff2


so the CFG looks like:


                    |
                    | /\
                stuff1 |
                    | |
            /\ | |
          | stuff2 |
          | | \/
          | stuff3
            \/ |
                    |


>From the classical definition, the loop for the back edge (stuff2->stuff1)
is {stuff1,stuff2,stuff3}, while the loop for the back edge
(stuff3->stuff2) is {stuff2,stuff3}. This satisfies the proper nesting
relationship. However, if we look at the control dependence relations for
this loop (see appropriate citations, ACM TOPLAS '87 and '91), the CD
predicates are ENTRY, stuff2, and stuff3. The CD graph is:


                      ENTRY
                      | \ \
            /\ | \ \
          | stuff3 \ \
            \/ \ | /\ \
                              stuff2 | \
                                      \ \/ |
                                          \ |
                                              \ |
                                                stuff1


Looking at the CD graph, 'stuff3' is the control predicate for the outer
loop, while 'stuff2' is the control predicate for the inner loop; this is
exactly opposite of the classical definition.


Is this of any interest to anyone? probably not.
--

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