Line: 1 to 1 | ||||||||
---|---|---|---|---|---|---|---|---|

## CS255/455 Spring 2008 Questions and Answers | ||||||||

Line: 11 to 11 | ||||||||

R: Okay let's add a category for remarks and begin them with symbol R. You are right that the optimization of algebraic expressions is not different from the classic problem of mathematics. When we start talking about the equivalence between programs we need to understand the basic semantics of programming languages, which we'll discuss in the last two weeks of the course. (added by ChenDing, 10pm, 1/31)
| ||||||||

Changed: | ||||||||

< < | Q: Is there only one immediate denominator for every block, or might it be the case that there are more? | |||||||

> > | Q: Is there only one immediate dominator for every block, or might it be the case that there are more? | |||||||

A: I quite think that this was what we were asked to work upon in class. So I repeat the definition as we mentioned them in class :
A block X is a Dominator of Y in a Control Flow Graph, if X appears on every path that enters Y. We write X>>Y and say X dominates Y. We also say that if X!=Y , then X "strictly" dominates Y. | ||||||||

Changed: | ||||||||

< < | The Immediate Dominator of Y is the strict denominator that is closest to Y in an execution path. | |||||||

> > | The Immediate Dominator of Y is the strict dominator that is closest to Y in an execution path. | |||||||

Question was can that "an" be one/some, or should it be every ? | ||||||||

Changed: | ||||||||

< < | We denote the list of possible dominators of X as DOM(X) and the immediate denominator of X as IDOM(X). The question we were asked to prove in class was whether IDOM definition possibly allows for two different possible denominators. Let's denote with SDOM(X) the strict denominators of X. Then SDOM(X)=DOM(X)-{X}. Let's assume that the definition of IDOM allows for two different immediate dominators ; if it doesn't allow for two, it certainly cannot allow for more, since it will then also have two. Say IDOM(X)={Y,Z} . Then, there exist two options : either X and Y are on the same execution path, or not. By the property of "closeness in an execution path", only one of the possible predecessors of X in the same path can be closer to X ; That should hold because Y!=X and Z!=X, since the immediate denominator is in SDOM. So either Y==Z or the two immediate dominators reside on different paths. If Y and Z are on different paths, then the do not belong in SDOM, because by definition, Y and Z should appear in every path that enters X, though we just claimed that they reside on different execution paths. Thus, "There can be only one". I hope this is a decent proof. | |||||||

> > | We denote the list of possible dominators of X as DOM(X) and the immediate dominator of X as IDOM(X). The question we were asked to prove in class was whether IDOM definition possibly allows for two different possible dominators. Let's denote with SDOM(X) the strict denominators of X. Then SDOM(X)=DOM(X)-{X}. Let's assume that the definition of IDOM allows for two different immediate dominators ; if it doesn't allow for two, it certainly cannot allow for more, since it will then also have two. Say IDOM(X)={Y,Z} . Then, there exist two options : either X and Y are on the same execution path, or not. By the property of "closeness in an execution path", only one of the possible predecessors of X in the same path can be closer to X ; That should hold because Y!=X and Z!=X, since the immediate dominator is in SDOM. So either Y==Z or the two immediate dominators reside on different paths. If Y and Z are on different paths, then the do not belong in SDOM, because by definition, Y and Z should appear in every path that enters X, though we just claimed that they reside on different execution paths. Thus, "There can be only one". I hope this is a decent proof. | |||||||

R I don't understand the logic completely. Is it possible that Y and Z both appear on two paths from entry to X. Y is closer to X on one path and Z is closer to X on the other? Good try. (added by ChenDing, 10pm, 1/31) |

View topic | History: r63 < r62 < r61 < r60 | More topic actions...

Copyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding URCS? Send feedback

Ideas, requests, problems regarding URCS? Send feedback