Difference: CS255Spring08Discussions (40 vs. 41)

Revision 412008-02-29 - KonstantinosMenychtas

Line: 1 to 1
 
META TOPICPARENT name="CS255Spring08"

CS255/455 Spring 2008 Questions and Answers

Line: 169 to 169
  Given the above lemma (due to Satyaki Mahalanabis), it is easy to show that if Y and Z are strict dominators of X and Y strictly dominates Z, then Z appears closer to X than Y does on every path from entry to X. Otherwise, one can construct a path entry->Y->X without going through Z.
Changed:
<
<
In order to better understand the definition and proof and their implications, here is a graph where there is a single strict dominator, and here is another one where the problem described by Satyaki is depicted: one node "strictly dominates" the other. In fact, this graph is trying to draw a picture where nodes C and D dominate E , C strictly dominate D, D strictly dominate C, but C and D are equal distance from E, ending up with the contradiction mentioned in the lemma. Trying to draw a graph like that pretty much by itself shows why there is a problem with having two immediate dominators: you end up adding and removing nodes and edges, and cannot avoid the contradiction: there will exist a path from A to E where C and D can be bypassed, so they are not even dominators of E, and they are not strict dominators of each other because one does not reside in every path from root to the other. This is not the easiest thing to see, so you can trust your intuition that it's true by the examples above.
>
>
In order to better understand the definition and proof and their implications, here is a graph where there is a single strict dominator, and here is another one where the problem described by Satyaki is depicted: one node "strictly dominates" the other. In fact, this graph is trying to draw a picture where nodes C and D dominate E , C strictly dominates D, D strictly dominates C, but C and D are equal distance from E, ending up with the contradiction mentioned in the lemma. Trying to draw a graph like that pretty much by itself shows why there is a problem with having two immediate dominators: you end up adding and removing nodes and edges, and cannot avoid the contradiction: there will exist a path from A to E where C and D can be bypassed, so they are not even dominators of E, and they are not strict dominators of each other because one does not reside in every path from root to the other. This is not the easiest thing to see, so you can trust your intuition that it's true by the examples above.
  Notice the following from experimentation with GCC. One can create the following C program to trick the compiler into generating something very close to the second graph.Here is a simple program trying to have an one-to-one correspondence with the graph (it actually does not, due to practical reasons mentioned bellow) :
Line: 234 to 234
 }
Changed:
<
<
What happens is that we have a correct program, but there is this weird behavior : though there is a path from C to E and from D to E, the compiler can't take this path, because it sticks to jumping around between C and E. The compiler annotates this as an error during some part of its dominator graph analysis (or possibly later - you can find out yourself ; the labeled tree node has been marked with ERROR_MARK and there are quite some cases you can get this behavior from the compiler, just grep the source). As the Cooper-Torzcon book mentions in p. 480, "Structural Data-Flow Algorithms and Reducibility", there are a bunch of issues with allowing this code in the tree graph and that is why GCC marks it as an error. Use the index of the book and you might find more interesting things about the control flow graph. The problem arises from languages like C allowing jumps to basic blocks the way we did. Maybe one can do something like that with exceptions too. The problem is very interesting, because the classic data flow assumes that all branch directions are possible. If there are special relations between branch tests, for example, if test a is true than test b must be true, then the meet-over-all-path problem requires more precise analysis---type state for example.
>
>
What happens is that we have a correct program, but there is this weird behavior : though there is a path from C to E and from D to E, the compiler can't take this path, because it sticks to jumping around between C and D. The compiler annotates this as an error during some part of its dominator graph analysis (or possibly later - you can find out yourself ; the labeled tree node has been marked with ERROR_MARK and there are quite some cases you can get this behavior from the compiler, just grep the source). As the Cooper-Torzcon book mentions in p. 480, "Structural Data-Flow Algorithms and Reducibility", there are a bunch of issues with allowing this code in the tree graph and that is why GCC marks it as an error. Use the index of the book and you might find more interesting things about the control flow graph. The problem arises from languages like C allowing jumps to basic blocks the way we did. Maybe one can do something like that with exceptions too. The problem is very interesting, because the classic data flow assumes that all branch directions are possible. If there are special relations between branch tests, for example, if test a is true than test b must be true, then the meet-over-all-path problem requires more precise analysis---type state for example.
  As to oppose to the fact that this is indeed an error, versus a similar case with analogous effect but different behavior, we can see what GCC has to say when we try to compile while(1):
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback