Difference: CS255Spring08Discussions (1 vs. 63)

Revision 632008-03-21 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

Line: 7 to 7
 
Q: What's going to be the metric for our competition, the number of executed gimple statement, or the runtime of the test programs?
Changed:
<
<
A: The metric is the number of executed gimple statements. So please add your work in part 1 at last to count the number.
>
>
A: The metric is the number of executed gimple statements in run-time. So please add your work in part 1 at last to count the number.
 
Q: How can we identify a node with type casting? e.g. D.1570 = (double) D.1569; or a.1 = (unsigned int) a.0;. I want to identify the rhs is a type casting and want to extract the variables as well.

Revision 622008-03-20 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

Line: 7 to 7
 
Q: What's going to be the metric for our competition, the number of executed gimple statement, or the runtime of the test programs?
Changed:
<
<
A:
>
>
A: The metric is the number of executed gimple statements. So please add your work in part 1 at last to count the number.
 
Q: How can we identify a node with type casting? e.g. D.1570 = (double) D.1569; or a.1 = (unsigned int) a.0;. I want to identify the rhs is a type casting and want to extract the variables as well.

Revision 612008-03-20 - BinBao

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.

Added:
>
>

Q: What's going to be the metric for our competition, the number of executed gimple statement, or the runtime of the test programs?

A:

 
Q: How can we identify a node with type casting? e.g. D.1570 = (double) D.1569; or a.1 = (unsigned int) a.0;. I want to identify the rhs is a type casting and want to extract the variables as well.

Revision 602008-03-20 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Q: How can we identify a node with type casting? e.g. D.1570 = (double) D.1569; or a.1 = (unsigned int) a.0;. I want to identify the rhs is a type casting and want to extract the variables as well.
Added:
>
>
A: I would think you'll see a special node representing the cast. A quick look at tree.def found two suspects, each has a unary child, which should be the variable or expression being converted. ChenDing

/* Represents a conversion of type of a value.
   All conversions, including implicit ones, must be
   represented by CONVERT_EXPR or NOP_EXPR nodes.  */
DEFTREECODE (CONVERT_EXPR, "convert_expr", tcc_unary, 1)

/* Represents a conversion expected to require no code to be generated.  */
DEFTREECODE (NOP_EXPR, "nop_expr", tcc_unary, 1)
 
Q: How can we identify definitions and uses of global variables like "int array[32]" in fibonacci.c?

Revision 592008-03-15 - NaushadUzZaman

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: How can we identify a node with type casting? e.g. D.1570 = (double) D.1569; or a.1 = (unsigned int) a.0;. I want to identify the rhs is a type casting and want to extract the variables as well.
 Q: How can we identify definitions and uses of global variables like "int array[32]" in fibonacci.c?

A: Depending on the purpose, usually a compiler traverses the code, examines each node, and stores information as needed.

Revision 582008-03-14 - BinBao

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

CS255/455 Spring 2008 Questions and Answers

Line: 10 to 10
 Can you iterate the nodes and record all the pointers to the defs and uses of a variable of your interest? Then you can traverse your special data structure for these defs and uses. Please elaborate if this does not answer the question.
Added:
>
>
I guess the expected answer would be is_global_var(var);
 
Q: Is there a standard way to handle function calls like printf, scanf or in general var-arg functions ? TREE_CHAIN can lead to variable declarations instead of a chain of arguments, and unless explicit care of those functions is taken (through string matching == printf/scanf), I think we have to resolve to SSA graph to find relevant information (name of operands of functions, especially var-arg functions). What do we do : handle them explicitly, or is there a way to do it I cannot track down (except for SSA)?

Revision 572008-03-13 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 6 to 6
 
Q: How can we identify definitions and uses of global variables like "int array[32]" in fibonacci.c?
Changed:
<
<
A:
>
>
A: Depending on the purpose, usually a compiler traverses the code, examines each node, and stores information as needed. Can you iterate the nodes and record all the pointers to the defs and uses of a variable of your interest? Then you can traverse your special data structure for these defs and uses. Please elaborate if this does not answer the question.
 
Q: Is there a standard way to handle function calls like printf, scanf or in general var-arg functions ? TREE_CHAIN can lead to variable declarations instead of a chain of arguments, and unless explicit care of those functions is taken (through string matching == printf/scanf), I think we have to resolve to SSA graph to find relevant information (name of operands of functions, especially var-arg functions). What do we do : handle them explicitly, or is there a way to do it I cannot track down (except for SSA)?
Line: 161 to 164
 Another problem that the original example shows is what to do when we use complex expressions as arguments to scanf/printf. We can certainly do something more elaborate to make the compiler not only weird but also insistently weird but we don't have to. You don't need to go beyond the requirement. When demonstrating your compiler, do not use complex expressions and instead perhaps explain that yours is a weird compiler, not a weird and wicked compiler. (ChenDing)


Added:
>
>
 Q: How to dump c-like code for a gimple node?

A: Suppose node is the node, use debug_tree(node); to do the dump. I think another useful dump function is dump_node(node, TDF_SLIM, stderr), which prints detailed information about a node.

Added:
>
>
If you want to print out the string representation of the node type, you can use the following trick due to TongxinBai. As an example cute code trick in Gcc, while the tree types are defined in enum tree_code in tree.h, the actual definition is not in tree.h but in tree.def, which includes a list of all node types and their (string) symbols. Looking at the code you'll quickly see how the trick works, and borrowing it you can easily construct an array of type strings (in your program file) as follows:

#define DEFTREECODE(SYM, STRING, TYPE, NARGS)   STRING,
char *type_names[] = {
#include "tree.def"
};

During debugging, you can use the node type as the index into the type_names array and pull up the string name that you so often crave for under the circumstance.

 

Q: How to get the number of parameters of a function call?

Revision 562008-03-13 - BinBao

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

CS255/455 Spring 2008 Questions and Answers

Line: 11 to 11
 Q: Is there a standard way to handle function calls like printf, scanf or in general var-arg functions ? TREE_CHAIN can lead to variable declarations instead of a chain of arguments, and unless explicit care of those functions is taken (through string matching == printf/scanf), I think we have to resolve to SSA graph to find relevant information (name of operands of functions, especially var-arg functions). What do we do : handle them explicitly, or is there a way to do it I cannot track down (except for SSA)?

A: For the project you don't need to handle external functions other than printf/scanf. The usual solution is through special treatment. In addition, there is no use of pointer other than in scanf. Your compiler can take advantage of the property that different variables in the test programs do not alias.

Added:
>
>
Actually, from your discussion, I remember my another concern about function call: they could define global variables or arrays. I guess we need to handle them carefully??????
 
Q: For dead code elimination, can we assume all function calls are essential or do we need to be able to distinguish the difference between calls like "foo(a)" and "bar(&a)"?

Revision 552008-03-13 - StanPark

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.

Added:
>
>

Q: How can we identify definitions and uses of global variables like "int array[32]" in fibonacci.c?
 
Added:
>
>
A:
 
Q: Is there a standard way to handle function calls like printf, scanf or in general var-arg functions ? TREE_CHAIN can lead to variable declarations instead of a chain of arguments, and unless explicit care of those functions is taken (through string matching == printf/scanf), I think we have to resolve to SSA graph to find relevant information (name of operands of functions, especially var-arg functions). What do we do : handle them explicitly, or is there a way to do it I cannot track down (except for SSA)?

Revision 542008-03-12 - NaushadUzZaman

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

CS255/455 Spring 2008 Questions and Answers

Revision 532008-03-12 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 7 to 7
 
Q: Is there a standard way to handle function calls like printf, scanf or in general var-arg functions ? TREE_CHAIN can lead to variable declarations instead of a chain of arguments, and unless explicit care of those functions is taken (through string matching == printf/scanf), I think we have to resolve to SSA graph to find relevant information (name of operands of functions, especially var-arg functions). What do we do : handle them explicitly, or is there a way to do it I cannot track down (except for SSA)?
Changed:
<
<
A:
>
>
A: For the project you don't need to handle external functions other than printf/scanf. The usual solution is through special treatment. In addition, there is no use of pointer other than in scanf. Your compiler can take advantage of the property that different variables in the test programs do not alias.
 
Q: For dead code elimination, can we assume all function calls are essential or do we need to be able to distinguish the difference between calls like "foo(a)" and "bar(&a)"?
Changed:
<
<
A:
>
>
A: Function calls are a form of control flow and should be preserved in basic dead code elimination, because they may have needed side effects even though the return value has no use. To remove dead calls, one needs an interprocedural form of the transformation, which would be interesting to develop.
 
Q: how can we debug our gcc, more specifically should I use the option -v with the make , make install , or ... ?

A: Use -v with gcc when you do the compilation. See How to debug your compiler.


Added:
>
>
 Q: I followed the advice giving in the project website about using the node to accelerate gcc make and install instructions and it wasn't fun at all waiting in the queue in order to get a free node, especially when I was competing with people whom allocated like 20 or more nodes in order to run a huge giant project, so I decided to switch back to my machine, so should I run: 1) make clean. 2) make. 3) make install. from the obj directory or something else is required ?
Changed:
<
<
A: If you are building the compiler on a different machine, you may need to reconfigure the Makefile by removing the object directory completely and run configure again. See Gcc installation notes.
>
>
A: If you are building the compiler on a different machine, you may need to reconfigure the Makefile by removing the object directory completely and run configure again. See Gcc installation notes.
 
Q: I can't understanding the Lattice part and all the proofs we had in the lectures, also I can't find any explanation for it in our two text books, is there any other recommended resource to relay on?

Revision 522008-03-11 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: Is there a standard way to handle function calls like printf, scanf or in general var-arg functions ? TREE_CHAIN can lead to variable declarations instead of a chain of arguments, and unless explicit care of those functions is taken (through string matching == printf/scanf), I think we have to resolve to SSA graph to find relevant information (name of operands of functions, especially var-arg functions). What do we do : handle them explicitly, or is there a way to do it I cannot track down (except for SSA)?

A:


 Q: For dead code elimination, can we assume all function calls are essential or do we need to be able to distinguish the difference between calls like "foo(a)" and "bar(&a)"?
Added:
>
>
A:
 
Q: how can we debug our gcc, more specifically should I use the option -v with the make , make install , or ... ?

Revision 512008-03-11 - StanPark

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: For dead code elimination, can we assume all function calls are essential or do we need to be able to distinguish the difference between calls like "foo(a)" and "bar(&a)"?


 Q: how can we debug our gcc, more specifically should I use the option -v with the make , make install , or ... ?

A: Use -v with gcc when you do the compilation. See How to debug your compiler.

Revision 502008-03-10 - StanPark

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.

Deleted:
<
<

Q: My compiler can eliminate dead code and produce the optimized gimple tree, but I am getting this error: 'internal compiler error: in purge_dead_edges, at cfgrtl.c:2316' It compiles correctly when I comment out my bsi_remove statement. Is there a particular way to remove statements that will not be reinserted with bsi_remove?
 
Q: how can we debug our gcc, more specifically should I use the option -v with the make , make install , or ... ?

Revision 492008-03-10 - StanPark

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: My compiler can eliminate dead code and produce the optimized gimple tree, but I am getting this error: 'internal compiler error: in purge_dead_edges, at cfgrtl.c:2316' It compiles correctly when I comment out my bsi_remove statement. Is there a particular way to remove statements that will not be reinserted with bsi_remove?


 Q: how can we debug our gcc, more specifically should I use the option -v with the make , make install , or ... ?

A: Use -v with gcc when you do the compilation. See How to debug your compiler.

Revision 482008-03-09 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Q: how can we debug our gcc, more specifically should I use the option -v with the make , make install , or ... ?
Added:
>
>
A: Use -v with gcc when you do the compilation. See How to debug your compiler.
 
Q: I followed the advice giving in the project website about using the node to accelerate gcc make and install instructions and it wasn't fun at all waiting in the queue in order to get a free node, especially when I was competing with people whom allocated like 20 or more nodes in order to run a huge giant project, so I decided to switch back to my machine, so should I run: 1) make clean. 2) make. 3) make install. from the obj directory or something else is required ?

Revision 472008-03-09 - AmalFahad

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: how can we debug our gcc, more specifically should I use the option -v with the make , make install , or ... ?
 Q: I followed the advice giving in the project website about using the node to accelerate gcc make and install instructions and it wasn't fun at all waiting in the queue in order to get a free node, especially when I was competing with people whom allocated like 20 or more nodes in order to run a huge giant project, so I decided to switch back to my machine, so should I run: 1) make clean. 2) make. 3) make install. from the obj directory or something else is required ?

A: If you are building the compiler on a different machine, you may need to reconfigure the Makefile by removing the object directory completely and run configure again. See Gcc installation notes.

Revision 462008-03-07 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 6 to 6
 
Q: I followed the advice giving in the project website about using the node to accelerate gcc make and install instructions and it wasn't fun at all waiting in the queue in order to get a free node, especially when I was competing with people whom allocated like 20 or more nodes in order to run a huge giant project, so I decided to switch back to my machine, so should I run: 1) make clean. 2) make. 3) make install. from the obj directory or something else is required ?
Changed:
<
<
A: Right, making gcc on your own workstation is a better choice. I'm going to do some inevitable competition with them, so don't do any unnecessary competition for our project.
>
>
A: If you are building the compiler on a different machine, you may need to reconfigure the Makefile by removing the object directory completely and run configure again. See Gcc installation notes.
 
Q: I can't understanding the Lattice part and all the proofs we had in the lectures, also I can't find any explanation for it in our two text books, is there any other recommended resource to relay on?

Revision 452008-03-04 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Changed:
<
<
Q: _I followed the advice giving in the project website about using the node to accelerate gcc make and install instructions and it wasn't fun at all waiting in the queue in order to get a free node, especially when I was competing with people whom allocated like 20 or more nodes in order to run a huge giant project, so I decided to switch back to my machine, so should I run: 1) make clean. 2) make. 3) make install. from the obj directory or something else is required ?_
>
>
Q: I followed the advice giving in the project website about using the node to accelerate gcc make and install instructions and it wasn't fun at all waiting in the queue in order to get a free node, especially when I was competing with people whom allocated like 20 or more nodes in order to run a huge giant project, so I decided to switch back to my machine, so should I run: 1) make clean. 2) make. 3) make install. from the obj directory or something else is required ?

A: Right, making gcc on your own workstation is a better choice. I'm going to do some inevitable competition with them, so don't do any unnecessary competition for our project.

 
Q: I can't understanding the Lattice part and all the proofs we had in the lectures, also I can't find any explanation for it in our two text books, is there any other recommended resource to relay on?

Revision 442008-03-03 - AmalFahad

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: _I followed the advice giving in the project website about using the node to accelerate gcc make and install instructions and it wasn't fun at all waiting in the queue in order to get a free node, especially when I was competing with people whom allocated like 20 or more nodes in order to run a huge giant project, so I decided to switch back to my machine, so should I run: 1) make clean. 2) make. 3) make install. from the obj directory or something else is required ?_
 Q: I can't understanding the Lattice part and all the proofs we had in the lectures, also I can't find any explanation for it in our two text books, is there any other recommended resource to relay on?

A: For lattice, you may read some books about discrete mathematics or Lattice on Wiki.

Revision 432008-03-01 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Changed:
<
<
Q: I can't understanding the Lattics part and all the proofs we had in the lectures, also I can't find any explanation for it in our two text books, is there any other recommended resource to relay on?
>
>
Q: I can't understanding the Lattice part and all the proofs we had in the lectures, also I can't find any explanation for it in our two text books, is there any other recommended resource to relay on?

A: For lattice, you may read some books about discrete mathematics or Lattice on Wiki.

 
Q: If z has two dominators then one dominates the other. We didn't end up proving this in the class. Can we get the proof?

Revision 422008-03-01 - AmalFahad

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.

Changed:
<
<
>
>

Q: I can't understanding the Lattics part and all the proofs we had in the lectures, also I can't find any explanation for it in our two text books, is there any other recommended resource to relay on?
 
Q: If z has two dominators then one dominates the other. We didn't end up proving this in the class. Can we get the proof?

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):

Revision 402008-02-29 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

Line: 7 to 7
 
Q: If z has two dominators then one dominates the other. We didn't end up proving this in the class. Can we get the proof?
Changed:
<
<
A Scroll down !
>
>
A: Scroll down !
 
Q: Is there any way to convert a string to tree? e.g. I want to convert an expression "1-2" to a tree.

Revision 392008-02-28 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

Line: 7 to 7
 
Q: If z has two dominators then one dominates the other. We didn't end up proving this in the class. Can we get the proof?
Added:
>
>
A Scroll down !
 
Q: Is there any way to convert a string to tree? e.g. I want to convert an expression "1-2" to a tree.
Line: 157 to 159
 
Q: Is there only one immediate dominator for every block, or might it be the case that there are more?
Changed:
<
<
A: (What follows is a complete rewrite from previous versions of this Q-A, but since it gets big and bloated, please see them using history and if you think you 'd need to, please also restore them or do any wiki-thing you can!)

The definition as we mentioned them in class :

>
>
A: The definitions as mentioned 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.

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

Changed:
<
<
We denote the list of possible dominators of X as DOM(X), with SDOM(X) the strict dominators of X, and with IDOM(X) the immediate dominator(s?) of X.

A node can have more than one different SDOMs. Assume a node X with >=2 SDOMs, and take any pair of them. Name them Y and Z, so {Y,Z} is a subset of SDOM(X).

For Y, Z there exist two options. Either they lie on the same path, or not.

If they are on the same path, only one of them can be closer to X, and it should be the single IDOM. Otherwise, Y==Z. You can see a case like that in this s-dom graph.

>
>
If a block X has two strict dominators, Y and Z, either they are the same or one strictly dominates the other. Here is a proof by contradiction. Assume Y and Z are different, and neither one strictly dominates the other. Take a path from entry to X, which must go through Y and Z. Without loss of generality assume Y appears closest to X on this path, which means that there is a path Y->X without going through Z. Since Z does not strictly dominate Y, there is a path entry->Y without going through Z. The combination of the above two paths, entry->Y->X, does not go through Z, contradicting our assumption that Z (strictly) dominates X.
 
Changed:
<
<
If they are on different paths, say paths y and z to X, then one should also appear on the path of the other, i.e. Y should be in y and z and X should be in y and z, so they can be dominators of X (remember that in order for them to be in DOM(X) they must appear in EVERY path that leads to X). If that was the case though, Y would strictly dominate Z and Z would strictly dominate Y. This is an error in the control flow graph. You can see a case like that in this idom graph.
>
>
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 the following, I analyze why this I think this is a problem inherent in the phrasing we use (even if we used "the" instead of "an" to define immediate dominator) and thus the thing is that the definition is as is because it is sufficient as is, not because one can prove some weird cases wrong. That means that the fact that you asked whether one can rule out the case "both Y and Z are strict dominators of X but the closest one is not the same in the two paths" is something that, as far as I can tell, cannot be done with the tools (logic) we have, unless we add some extra formality, like disallow cycles in the cfg etc. Thus, even if there is more than one immediate dominators, they exist in cases which are errors already ; errors in terms of rationality, not correctness.
>
>
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.
 
Changed:
<
<
I won't bother formality for the following. When I went over the question it seemed pretty reasonable and it was a case I had naturally neglected, since I thought I had taken care of it. In fact, the proof rephrased does not add something new, it is just a different and more understandable phrasing to mention the specific error. Anyway, I started drawing graphs to see how it works and I had hard time picturing that case, because I was adding and removing nodes and edges and it was getting confusing, until I let it settle down to the graph I posted. It seems like it is wrong, but one cannot reason why by those two definitions we have.

So I created the following C program to trick the compiler into generating the graph I have there. Here is the code I wrote, pretty simple and bearing an 1-to-1 correspondence to the graph :

>
>
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) :
 
#include <stdio.h>
Line: 206 to 198
 }
Changed:
<
<
I run gcc, no prob, I get a normal binary. I was expecting to get the effect of while(1); Indeed, that is the case. However, I also try -fdump-tree-gimple , and what a surprise, here is the gimplified code :
>
>
If you run GCC on it, you get a normal binary - no error, everything looks fine. The expected effect is that of while(1); Indeed, that is the case : the paths from B and C to E are actually never taken. If you try -fdump-tree-gimple though, the gimplified code has some unexpected annotations :
 
;; Function main (main)
Line: 242 to 234
 }
Changed:
<
<
I have a correct - i.e. allowed, but bad program, and the compiler just says so. In order to compare, I compile while(1) too ; here is what the compiler thinks about this new stupidity :
>
>
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.

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):

 
#include <stdio.h>
Line: 256 to 250
 }
Changed:
<
<
and the gimplified code:
>
>
The gimplified code is :
 
;; Function main (main)
Line: 269 to 263
 }
Changed:
<
<
As it turns out, compiler does not think I have an error now, like they did mention an error before. The labeled tree node has been marked with ERROR_MARK, and I guess there is a bunch of places in gcc this can happen (just grep it), so I didn't bother trying to track it down exactly.

This is no proof of why I think that the case you asked to rule out cannot be ruled out. The fact that the code is irrational does not mean that the definition does not allow for two immediate dominators. As is, it does, and you can build a problem with that. However, 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. Use the index of the book and you might find more interesting things about the control flow graph. The source comes from languages like C allowing jumps to basic blocks the way we did. I think one can do something like that with exceptions too.

Anyway, to sum up: one cannot rule out the aforementioned case and I think they shouldn't, otherwise they would circumvent the power of some language to express some problems which are not wrong, just irrational. If, however, there is a nice proof why there exists only one immediate dominator, please post it.

A This is quite advanced reasoning with tricky experiments and internal readings of Gcc. Your basic notion is correct that if a block X has two strict dominators, Y and Z, either they are the same or one strictly dominates the other. Here is a proof by contradiction. Assume Y and Z are different, and neither one strictly dominates the other. Take a path from entry to X, which must go through Y and Z. Without loss of generality assume Y appears closest to X on this path, which means that there is a path Y->X without going through Z. Since Z does not strictly dominate Y, there is a path entry->Y without going through Z. The combination of the above two paths, entry->Y->Z, does not go through Z, contradicting our assumption that Z strictly dominates X.

>
>
You can see that the compiler does not object to your intention to create an infinite loop. The reason it did object in the previous example, was an analysis issue.
 
Changed:
<
<
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. (ChenDing)
>
>
Last remarks: Trying a top down approach to the proof (showing that one node will dominate the other) is kind of harder, because, like Tivadar did in class, you can see that you end up with two nodes, one dominating the other but don't grasp why this might be wrong. Graph drawing does help, but probably sticking strictly to the definitions is an ok proof also. Previous attempts, false-alarms and in all the discussion about this subject before being rewritten for the n-th time can be seen through history. This answer to the question has been rewritten by merging Q+A concerning this subject, including a talk with Dr. Ding and Satyaki. I hope the examples make an otherwise nice short and correct proof nicer and more intriguing.
 

Revision 382008-02-27 - NaushadUzZaman

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: If z has two dominators then one dominates the other. We didn't end up proving this in the class. Can we get the proof?


 Q: Is there any way to convert a string to tree? e.g. I want to convert an expression "1-2" to a tree.

A: I don't know any magic function for this. But You may build the tree step by step.

Revision 372008-02-26 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 14 to 14
 A: I think it does not work for variables that look like D.#### since they are temporary compiler variables and do not actually have a name associated with them. Check out print_node_brief in print-tree.c to see how that function deals with getting a string representation of it.

Actually, #### is a unique ID for each declaration, people can use DECL_UID(node) to get that unique number.

Added:
>
>
Another solution, suggested by Tivadar, is to use the address of the tree node representing the temporary variable.
 
Q: Are there functions to change operands of a tree or do we have to build EXPR trees ourselves with some other function?

Revision 362008-02-25 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

Line: 7 to 7
 
Q: Is there any way to convert a string to tree? e.g. I want to convert an expression "1-2" to a tree.
Added:
>
>
A: I don't know any magic function for this. But You may build the tree step by step.
 
Q: Is there a way to get a string representation of a tree, particularly a tree that represents a single variable? get_name() does not work for variables like D.####

Revision 352008-02-25 - BinBao

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

CS255/455 Spring 2008 Questions and Answers

Line: 11 to 11
 Q: Is there a way to get a string representation of a tree, particularly a tree that represents a single variable? get_name() does not work for variables like D.####

A: I think it does not work for variables that look like D.#### since they are temporary compiler variables and do not actually have a name associated with them. Check out print_node_brief in print-tree.c to see how that function deals with getting a string representation of it.

Added:
>
>
Actually, #### is a unique ID for each declaration, people can use DECL_UID(node) to get that unique number.
 
Q: Are there functions to change operands of a tree or do we have to build EXPR trees ourselves with some other function?

Revision 342008-02-25 - ChrisTice

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

CS255/455 Spring 2008 Questions and Answers

Line: 7 to 7
 
Q: Is there any way to convert a string to tree? e.g. I want to convert an expression "1-2" to a tree.
Changed:
<
<
>
>

 Q: Is there a way to get a string representation of a tree, particularly a tree that represents a single variable? get_name() does not work for variables like D.####
Added:
>
>
A: I think it does not work for variables that look like D.#### since they are temporary compiler variables and do not actually have a name associated with them. Check out print_node_brief in print-tree.c to see how that function deals with getting a string representation of it.
 
Q: Are there functions to change operands of a tree or do we have to build EXPR trees ourselves with some other function?

Revision 332008-02-24 - NaushadUzZaman

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: Is there any way to convert a string to tree? e.g. I want to convert an expression "1-2" to a tree.
 Q: Is there a way to get a string representation of a tree, particularly a tree that represents a single variable? get_name() does not work for variables like D.####


Revision 322008-02-24 - StanPark

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: Is there a way to get a string representation of a tree, particularly a tree that represents a single variable? get_name() does not work for variables like D.####


 Q: Are there functions to change operands of a tree or do we have to build EXPR trees ourselves with some other function?

A: There are some macroes named "build0", "build1", .... in tree.h which can be used to build gimple trees. For changing operands, there are 3 steps: build new operands, remove old operands and place new operands.

Revision 312008-02-24 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

Line: 7 to 7
 
Q: Are there functions to change operands of a tree or do we have to build EXPR trees ourselves with some other function?
Added:
>
>
A: There are some macroes named "build0", "build1", .... in tree.h which can be used to build gimple trees. For changing operands, there are 3 steps: build new operands, remove old operands and place new operands.
 
Q: It seems that there are couple of hash table related functions in tree-vn.c, why can't we use that? Or can we write similar ones? (I mean similar hash_f and eq_f, etc).
Added:
>
>
A: Either is OK for the project.
 

Q: How much of tree-vn.c can we use ? For project 3, we need VEC and hash from data structs I guess, but there 's a whole lot of functionality there that might not be considered ssa stuff.

Revision 302008-02-23 - StanPark

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: Are there functions to change operands of a tree or do we have to build EXPR trees ourselves with some other function?


 Q: It seems that there are couple of hash table related functions in tree-vn.c, why can't we use that? Or can we write similar ones? (I mean similar hash_f and eq_f, etc).


Revision 292008-02-23 - RongrongZhong

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: It seems that there are couple of hash table related functions in tree-vn.c, why can't we use that? Or can we write similar ones? (I mean similar hash_f and eq_f, etc).


  Q: How much of tree-vn.c can we use ? For project 3, we need VEC and hash from data structs I guess, but there 's a whole lot of functionality there that might not be considered ssa stuff.

Revision 282008-02-23 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 252 to 252
  Anyway, to sum up: one cannot rule out the aforementioned case and I think they shouldn't, otherwise they would circumvent the power of some language to express some problems which are not wrong, just irrational. If, however, there is a nice proof why there exists only one immediate dominator, please post it.
Added:
>
>
A This is quite advanced reasoning with tricky experiments and internal readings of Gcc. Your basic notion is correct that if a block X has two strict dominators, Y and Z, either they are the same or one strictly dominates the other. Here is a proof by contradiction. Assume Y and Z are different, and neither one strictly dominates the other. Take a path from entry to X, which must go through Y and Z. Without loss of generality assume Y appears closest to X on this path, which means that there is a path Y->X without going through Z. Since Z does not strictly dominate Y, there is a path entry->Y without going through Z. The combination of the above two paths, entry->Y->Z, does not go through Z, contradicting our assumption that Z strictly dominates X.

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. (ChenDing)

 
Q: How do we format a question and an answer?

Revision 272008-02-22 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 8 to 8
  Q: How much of tree-vn.c can we use ? For project 3, we need VEC and hash from data structs I guess, but there 's a whole lot of functionality there that might not be considered ssa stuff.
Changed:
<
<
A:
>
>
A: The name "vn" looks suspicious. You can read the code but you must code your own implementation. You can use the control flow analysis in Gcc but not the value numbering in Gcc.
 
Q: For the scanf function, are the temporary variable statements that we need to move those that have the variables on the right hand side (instead of the left hand side as in the printf)?

Revision 262008-02-22 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

Line: 132 to 132
  A: 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)
Deleted:
<
<
 Q: Is there only one immediate dominator for every block, or might it be the case that there are more?
Changed:
<
<
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: (What follows is a complete rewrite from previous versions of this Q-A, but since it gets big and bloated, please see them using history and if you think you 'd need to, please also restore them or do any wiki-thing you can!)

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.

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

Changed:
<
<
Question was can that "an" be one/some, or should it be every ?
>
>
We denote the list of possible dominators of X as DOM(X), with SDOM(X) the strict dominators of X, and with IDOM(X) the immediate dominator(s?) of X.

A node can have more than one different SDOMs. Assume a node X with >=2 SDOMs, and take any pair of them. Name them Y and Z, so {Y,Z} is a subset of SDOM(X).

For Y, Z there exist two options. Either they lie on the same path, or not.

If they are on the same path, only one of them can be closer to X, and it should be the single IDOM. Otherwise, Y==Z. You can see a case like that in this s-dom graph.

If they are on different paths, say paths y and z to X, then one should also appear on the path of the other, i.e. Y should be in y and z and X should be in y and z, so they can be dominators of X (remember that in order for them to be in DOM(X) they must appear in EVERY path that leads to X). If that was the case though, Y would strictly dominate Z and Z would strictly dominate Y. This is an error in the control flow graph. You can see a case like that in this idom graph.

In the following, I analyze why this I think this is a problem inherent in the phrasing we use (even if we used "the" instead of "an" to define immediate dominator) and thus the thing is that the definition is as is because it is sufficient as is, not because one can prove some weird cases wrong. That means that the fact that you asked whether one can rule out the case "both Y and Z are strict dominators of X but the closest one is not the same in the two paths" is something that, as far as I can tell, cannot be done with the tools (logic) we have, unless we add some extra formality, like disallow cycles in the cfg etc. Thus, even if there is more than one immediate dominators, they exist in cases which are errors already ; errors in terms of rationality, not correctness.

 
Changed:
<
<
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 immediate dominators. Let's denote with SDOM(X) the strict dominators 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 X will definitely have 2 immediate dominators if it has 3. Say IDOM(X)={Y,Z} . Then, there exist two options : either Y and Z 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 and thus one does not exist in the execution path of the other and consequently in all execution paths entering X. Thus, "There can be only one". I hope this is a decent proof.
>
>
I won't bother formality for the following. When I went over the question it seemed pretty reasonable and it was a case I had naturally neglected, since I thought I had taken care of it. In fact, the proof rephrased does not add something new, it is just a different and more understandable phrasing to mention the specific error. Anyway, I started drawing graphs to see how it works and I had hard time picturing that case, because I was adding and removing nodes and edges and it was getting confusing, until I let it settle down to the graph I posted. It seems like it is wrong, but one cannot reason why by those two definitions we have.

So I created the following C program to trick the compiler into generating the graph I have there. Here is the code I wrote, pretty simple and bearing an 1-to-1 correspondence to the graph :

#include <stdio.h>

int main(int argc, char *argv[])
{
  int A, B, C, D, E, F;

  //A: printf - scanf;                                                         
  A = 0;
  printf("Type 0 for false, 1 for true\n");
  scanf("%d",&B);
  //B :                                                                        
  if(B)
  {
   CLABEL: goto DLABEL;
  }
  else
  {
    DLABEL: goto CLABEL;
  }
  E = 0;
  F = 0;
}

I run gcc, no prob, I get a normal binary. I was expecting to get the effect of while(1); Indeed, that is the case. However, I also try -fdump-tree-gimple , and what a surprise, here is the gimplified code :

;; Function main (main)

main (argc, argv)
{
  int B.0;
  int A;
  int B;
  int C;
  int D;
  int E;
  int F;
  void CLABEL = <<< error >>>;
  void DLABEL = <<< error >>>;

  A = 0;
  printf (&"Type 0 for false, 1 for true\n"[0]);
  scanf (&"%d"[0], &B);
  B.0 = B;
  if (B.0 != 0)
    {
      CLABEL:;
      goto DLABEL;
    }
  else
    {
      DLABEL:;
      goto CLABEL;
    }
  E = 0;
  F = 0;
}

I have a correct - i.e. allowed, but bad program, and the compiler just says so. In order to compare, I compile while(1) too ; here is what the compiler thinks about this new stupidity :

#include <stdio.h>

int main(int argc, char *argv[])
{
  while(1)
    ;

  return;
}

and the gimplified code:

;; Function main (main)

main (argc, argv)
{
  <D1865>:;
  goto <D1865>;
  return;
}
 
Changed:
<
<
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)
>
>
As it turns out, compiler does not think I have an error now, like they did mention an error before. The labeled tree node has been marked with ERROR_MARK, and I guess there is a bunch of places in gcc this can happen (just grep it), so I didn't bother trying to track it down exactly.
 
Changed:
<
<
R Oh, you 're right, I had a typo on the "options" description which I didn't notice (and I added some clarifications to make the whole thing more readable). I wanted to say exactly that Y and Z either appear on the same path or not. I corrected the previous version (wiki-like) so if someone was to see the mistake they shall try the history view.
>
>
This is no proof of why I think that the case you asked to rule out cannot be ruled out. The fact that the code is irrational does not mean that the definition does not allow for two immediate dominators. As is, it does, and you can build a problem with that. However, 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. Use the index of the book and you might find more interesting things about the control flow graph. The source comes from languages like C allowing jumps to basic blocks the way we did. I think one can do something like that with exceptions too.
 
Changed:
<
<
R Thanks for the clarification. Correcting in the proof is a good idea. Can the proof rule out the case I had in the last remark, where both Y and Z are strict dominators of X but the closest one is not the same in the two paths? --Main.ChenDing
>
>
Anyway, to sum up: one cannot rule out the aforementioned case and I think they shouldn't, otherwise they would circumvent the power of some language to express some problems which are not wrong, just irrational. If, however, there is a nice proof why there exists only one immediate dominator, please post it.
 

Revision 252008-02-22 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

Line: 157 to 157
  A: A question and an answer start with the bold letter Q and A respectively followed by a colon. Use italic text for the question and normal text for the answer. Use a separator (a horizontal rule) after each question. Add new questions to the beginning of the list.
Deleted:
<
<
META FILEATTACHMENT attachment="idom.png" attr="" comment="Immediate dominator graph" date="1203654671" name="idom.png" path="idom.png" size="11667" stream="idom.png" tmpFilename="/tmp/wBItS4tMlY" user="Main.KonstantinosMenychtas" version="1"

Revision 242008-02-22 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

Line: 157 to 157
  A: A question and an answer start with the bold letter Q and A respectively followed by a colon. Use italic text for the question and normal text for the answer. Use a separator (a horizontal rule) after each question. Add new questions to the beginning of the list.
Added:
>
>
META FILEATTACHMENT attachment="idom.png" attr="" comment="Immediate dominator graph" date="1203654671" name="idom.png" path="idom.png" size="11667" stream="idom.png" tmpFilename="/tmp/wBItS4tMlY" user="Main.KonstantinosMenychtas" version="1"

Revision 232008-02-21 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

Line: 6 to 6
 
Changed:
<
<
Q: For the scanf function, are the temporary variable statements that we need to move those that have the variables on the right hand side (instead of the left hand side as in the printf)?
>
>
Q: How much of tree-vn.c can we use ? For project 3, we need VEC and hash from data structs I guess, but there 's a whole lot of functionality there that might not be considered ssa stuff.

A:


Q: For the scanf function, are the temporary variable statements that we need to move those that have the variables on the right hand side (instead of the left hand side as in the printf)?
  A: Since scanf reads values to variables directly, there is no need to move any temporary variable assignment with scanf. The project description has been adjusted. Thanks for the question. (ChenDing)
Line: 26 to 31
  I am not familiar with NEXT CHAIN (the name seems a macro) but I wonder whether its problem has something to do with the NULL stmt. In addition, if you can print mylist through some function, then I would check how that function iterates through the list in spite of the problem with NEXT CHAIN. Please post what you find. (ChenDing)
Added:
>
>
A NEXT CHAIN is a very useful macro which is used to build an easy to handle list from any tree. However, I have not been able to build such a list of my own, rather I did manage to manipulate, for example, the number of arguments of a var-arg function like printf with its iternal wacky representation. This is what Xiaoming suggests, I hadn't noticed and I found it on my own. I guess your suggestion about the problem explains what I experienced, but I cannot remember. The statement list carries some more information used in some certain occasions (I remember so), but at least I did manage to use it to build a list:

tree lemon_tree = alloc_stmt_list();
tree_stmt_iterator lemon_counter;
tree fools, garden; /* quiz */

append_to_statement_list(fools, &lemon_tree);
append_to_statement_list(garden, &lemon_tree);

for (lemon_counter = tsi_last(lemon_tree); !tsi_end_p (lemon_counter); tsi_prev(&lemon_counter))
{
      tree lemon= tsi_stmt (lemon_counter);
      squeeze(lemon); /* this function just says make use of it */
}

At c-semantics they have some push/pop functions, I didn't use it though. In all, I highly doubt it might be of any use to me again, NEXT CHAIN is important, if somebody can make a concrete build/use-list example with it please post it.

 
Q: Given a tree node, i.e. call expr, how do you extract the function name from the node?

Revision 222008-02-17 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 8 to 8
  Q: For the scanf function, are the temporary variable statements that we need to move those that have the variables on the right hand side (instead of the left hand side as in the printf)?
Changed:
<
<
A:
>
>
A: Since scanf reads values to variables directly, there is no need to move any temporary variable assignment with scanf. The project description has been adjusted. Thanks for the question. (ChenDing)
 
Line: 20 to 20
 apend_to_statement_list(stmt2, & mylist);
Changed:
<
<
A:
>
>
A: This is interesting. I would think the result might be a bit strange since it may contain three statements, the first being the NULL. Another way is to append stmt2 to stmt1 to create the list, as below
mylist = stmt1
append_to_statement_list(stmt2, & mylist)
I am not familiar with NEXT CHAIN (the name seems a macro) but I wonder whether its problem has something to do with the NULL stmt. In addition, if you can print mylist through some function, then I would check how that function iterates through the list in spite of the problem with NEXT CHAIN. Please post what you find. (ChenDing)
 
Q: Given a tree node, i.e. call expr, how do you extract the function name from the node?
Line: 78 to 82
  Since the requirement did not address this conflict, you can in principle do whatever you want to without losing any points. I would recommend replicating the copy, "j=i" in this example, for each related statement. The solution is equivalent of keeping the copy with the earliest statement if there are no intervening changes to the right-hand operand of the copy statement.
Changed:
<
<
Another problem that the original example shows is what to do when we use complex expressions as arguments to scanf/printf. We can certainly do something more elaborate to make the compiler not only weird but also insistently weird but we don't have to. You don't need to go beyond the requirement. When demonstrating your compiler, do not use complex expressions and instead perhaps explain that yours is a weird compiler, not a weird and wicked compiler.
>
>
Another problem that the original example shows is what to do when we use complex expressions as arguments to scanf/printf. We can certainly do something more elaborate to make the compiler not only weird but also insistently weird but we don't have to. You don't need to go beyond the requirement. When demonstrating your compiler, do not use complex expressions and instead perhaps explain that yours is a weird compiler, not a weird and wicked compiler. (ChenDing)
 
Q: How to dump c-like code for a gimple node?

Revision 212008-02-17 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

Line: 12 to 12
 
Deleted:
<
<
CONFLICT version 19:
 Q: I am trying to build a list of statements linked through NEXT CHAIN, but I cannot get it to work. Any ideas about how this process actually works ? In the excerpt below I just call apend_to_statement_list for my two statements. By append's source code, a new statement list should be built bellow mylist if mylist is initially NULL. This partly works, i.e. if I print mylist I can see stmt1 and stmt, but it keeps saying I cannot retrieve them using NEXT CHAIN...
tree mylist = NULL;

Revision 202008-02-17 - ChetanBhole

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: For the scanf function, are the temporary variable statements that we need to move those that have the variables on the right hand side (instead of the left hand side as in the printf)?

A:


CONFLICT version 19:
 Q: I am trying to build a list of statements linked through NEXT CHAIN, but I cannot get it to work. Any ideas about how this process actually works ? In the excerpt below I just call apend_to_statement_list for my two statements. By append's source code, a new statement list should be built bellow mylist if mylist is initially NULL. This partly works, i.e. if I print mylist I can see stmt1 and stmt, but it keeps saying I cannot retrieve them using NEXT CHAIN...
tree mylist = NULL;

Revision 192008-02-17 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: I am trying to build a list of statements linked through NEXT CHAIN, but I cannot get it to work. Any ideas about how this process actually works ? In the excerpt below I just call apend_to_statement_list for my two statements. By append's source code, a new statement list should be built bellow mylist if mylist is initially NULL. This partly works, i.e. if I print mylist I can see stmt1 and stmt, but it keeps saying I cannot retrieve them using NEXT CHAIN...
tree mylist = NULL;
apend_to_statement_list(stmt1, & mylist);
apend_to_statement_list(stmt2, & mylist);

A:


 Q: Given a tree node, i.e. call expr, how do you extract the function name from the node?

A: I have already got this one. Please refer the following code which already exists in cs255.c

Revision 182008-02-16 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

Line: 34 to 34
 i = 1; j = 2; i.11 = i;
Changed:
<
<
i = i - 1;
>
>
i = i + 1;
 printf (&"i is %d, j is %d\n"[0], i.11, j); printf (&"i is %d, j is %d\n"[0], i, j); return; Since the two printf share one copy stmt of j, how should we move it? I think this is not quite clearly defined in the project description.
Changed:
<
<
A: This is a good example, which exposes several finer points of the requirement. First is what we consider as copies to temporaries. In this example, "i.11=i" is a copy but "j=2" is not because the latter copies from a constant, not a variable. Needless to say that "i=i-1" is not a copy either. The reordering would yield
>
>
A: This is a good example, which exposes several finer points of the requirement. First is what we consider as copies to temporaries. In this example, "i.11=i" is a copy but "j=2" is not because the latter copies from a constant, not a variable. Needless to say that "i=i+1" is not a copy either. The reordering would yield
 
i=1;
j = 2;
Changed:
<
<
i = i - 1;
>
>
i = i + 1;
 printf (&"i is %d, j is %d\n"[0], i, j); i.11 = i; printf (&"i is %d, j is %d\n"[0], i.11, j);
Line: 60 to 60
  Since the requirement did not address this conflict, you can in principle do whatever you want to without losing any points. I would recommend replicating the copy, "j=i" in this example, for each related statement. The solution is equivalent of keeping the copy with the earliest statement if there are no intervening changes to the right-hand operand of the copy statement.
Changed:
<
<
Another problem that the original example shows is what to do when we use complex expressions as arguments to scanf/printf. We can certainly do something more elaborate to make the compiler not only wired but also insistently wired but we don't have to. You don't need to go beyond the requirement. When demonstrating your compiler, do not use complex expressions and instead perhaps explain that yours is a wired compiler, not a wired and wicked compiler.
>
>
Another problem that the original example shows is what to do when we use complex expressions as arguments to scanf/printf. We can certainly do something more elaborate to make the compiler not only weird but also insistently weird but we don't have to. You don't need to go beyond the requirement. When demonstrating your compiler, do not use complex expressions and instead perhaps explain that yours is a weird compiler, not a weird and wicked compiler.
 
Q: How to dump c-like code for a gimple node?

Revision 172008-02-16 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 19 to 17
  if(strcmp (callee_name, "exit"))// the called function is exit() {
Added:
>
>
 
Q: How should we handle this simple case for project 2?
Line: 42 to 41
  Since the two printf share one copy stmt of j, how should we move it? I think this is not quite clearly defined in the project description.
Changed:
<
<
A: Let's focus on the provided ab.c and loop.c first. I'll talk to Chen about this.
>
>
A: This is a good example, which exposes several finer points of the requirement. First is what we consider as copies to temporaries. In this example, "i.11=i" is a copy but "j=2" is not because the latter copies from a constant, not a variable. Needless to say that "i=i-1" is not a copy either. The reordering would yield
i=1;
j = 2;
i = i - 1;
printf (&"i is %d, j is %d\n"[0], i, j);
i.11 = i;
printf (&"i is %d, j is %d\n"[0], i.11, j);
return;

It is fine if you consider constant assignments such as "j=2" a copy. The requirement does not say what to do if two scanf/printf statements have or copy from the same variable as in the following example (slightly changed from the original one)

j=i;
printf("%d", j);
printf("%d", j);
Since the requirement did not address this conflict, you can in principle do whatever you want to without losing any points. I would recommend replicating the copy, "j=i" in this example, for each related statement. The solution is equivalent of keeping the copy with the earliest statement if there are no intervening changes to the right-hand operand of the copy statement.

Another problem that the original example shows is what to do when we use complex expressions as arguments to scanf/printf. We can certainly do something more elaborate to make the compiler not only wired but also insistently wired but we don't have to. You don't need to go beyond the requirement. When demonstrating your compiler, do not use complex expressions and instead perhaps explain that yours is a wired compiler, not a wired and wicked compiler.

 
Q: How to dump c-like code for a gimple node?

Revision 162008-02-16 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

Line: 19 to 19
  if(strcmp (callee_name, "exit"))// the called function is exit() {
Changed:
<
<
>
>

 Q: How should we handle this simple case for project 2?
#include <stdio.h>
Line: 42 to 42
  Since the two printf share one copy stmt of j, how should we move it? I think this is not quite clearly defined in the project description.
Changed:
<
<
A:
>
>
A: Let's focus on the provided ab.c and loop.c first. I'll talk to Chen about this.
 
Q: How to dump c-like code for a gimple node?

Revision 152008-02-16 - BinBao

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

CS255/455 Spring 2008 Questions and Answers

Line: 9 to 9
 
Q: Given a tree node, i.e. call expr, how do you extract the function name from the node?
Changed:
<
<
A:
>
>
A: I have already got this one. Please refer the following code which already exists in cs255.c
            if (TREE_CODE (stmt) == CALL_EXPR)
              {
                tree callee_decl = get_callee_fndecl (stmt);
                const char *callee_name = get_name (callee_decl);
                //printf ("Callee: %s\n", callee_name);
                if(!strcmp (callee_name, "exit"))// the called function is exit()
                  {
 
Changed:
<
<
Q: How should we handle this simple case for project 2?
>
>
Q: How should we handle this simple case for project 2?
 
#include <stdio.h>
int main()
Line: 31 to 40
 printf (&"i is %d, j is %d\n"[0], i, j); return;
Changed:
<
<
Since the two printf shares one copy stmt of j, how should we move it? I think this is not quite clearly defined in the project description.
>
>
Since the two printf share one copy stmt of j, how should we move it? I think this is not quite clearly defined in the project description.
  A:

Revision 142008-02-16 - NaushadUzZaman

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

CS255/455 Spring 2008 Questions and Answers

Line: 7 to 7
 


Added:
>
>
Q: Given a tree node, i.e. call expr, how do you extract the function name from the node?

A:

 Q: How should we handle this simple case for project 2?
#include <stdio.h>

Revision 132008-02-15 - BinBao

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.

Added:
>
>

Q: How should we handle this simple case for project 2?
#include <stdio.h>
int main()
{
  int i=1, j=2;
  printf("i is %d, j is %d\n", i++, j);
  printf("i is %d, j is %d\n", i, j);
}
This is the gimple tree for the only BB.
i = 1;
j = 2;
i.11 = i;
i = i - 1;
printf (&"i is %d, j is %d\n"[0], i.11, j);
printf (&"i is %d, j is %d\n"[0], i, j);
return;
Since the two printf shares one copy stmt of j, how should we move it? I think this is not quite clearly defined in the project description.

A:

 
Q: How to dump c-like code for a gimple node?

A: Suppose node is the node, use debug_tree(node); to do the dump.

Changed:
<
<
I think another useful dump function is dump_node(node, TDF_SLIM, stderr), which prints detailed information about a node.
>
>
I think another useful dump function is dump_node(node, TDF_SLIM, stderr), which prints detailed information about a node.
 

Q: How to get the number of parameters of a function call?

Revision 122008-02-15 - BinBao

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

CS255/455 Spring 2008 Questions and Answers

Line: 8 to 9
 Q: How to dump c-like code for a gimple node?

A: Suppose node is the node, use debug_tree(node); to do the dump.

Added:
>
>
I think another useful dump function is dump_node(node, TDF_SLIM, stderr), which prints detailed information about a node.
 

Q: How to get the number of parameters of a function call?

Revision 112008-02-15 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.

Added:
>
>

Q: How to dump c-like code for a gimple node?
 
Added:
>
>
A: Suppose node is the node, use debug_tree(node); to do the dump.
 

Q: How to get the number of parameters of a function call?

Revision 102008-02-14 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.

Added:
>
>

Q: How to get the number of parameters of a function call?

A: Suppose stmt is the function call, then do the following and num_parms is the number .

      tree parms = TREE_OPERAND (stmt, 1);
      int num_parms;
      tree p;
      for (p = parms, num_parms = 0; p; p = TREE_CHAIN (p))
        num_parms++;
 
Changed:
<
<
R: More of remarks and vague ideas than questions: in class we discussed about Chris' idea to perform the a=b-c <=> b=c+1 analysis. I had doubts about the idea because I was thinking "=" more of as an assignment operator, rather than the algebraic equality alternative, which pretty much is what it is in this analysis step. I guess thus, that at this level we can perform an even wider variety of symbolic analysis (something that would resemble what Maple does for the common mathematical notations, but in our case solely for Algebra) and generate an even wider range of possible optimizations one cannot possible expect at first sight. I was wondering though to what extent this actually happens, since the way we program brakes down the simplest algebraic expressions into difficult to track simplified steps. I was also wondering whether one can run any optimizations as (syntax) tree-data structure operations, i.e whether instead of a hash there exists an advanced data structure that keeps the tree-like structure of the syntax tree and optimizations are realized as (for example) rotations, insertions/deletions/pruning etc. After all, after the optimizations we should be able to build a new syntax tree from an optimized version of the code ; does there exist a possible repetitive transformation that does not need intermediate hash-based analysis (maybe I 'm making a hard problem impossible here)?
>
>
Q: More of remarks and vague ideas than questions: in class we discussed about Chris' idea to perform the a=b-c <=> b=c+1 analysis. I had doubts about the idea because I was thinking "=" more of as an assignment operator, rather than the algebraic equality alternative, which pretty much is what it is in this analysis step. I guess thus, that at this level we can perform an even wider variety of symbolic analysis (something that would resemble what Maple does for the common mathematical notations, but in our case solely for Algebra) and generate an even wider range of possible optimizations one cannot possible expect at first sight. I was wondering though to what extent this actually happens, since the way we program brakes down the simplest algebraic expressions into difficult to track simplified steps. I was also wondering whether one can run any optimizations as (syntax) tree-data structure operations, i.e whether instead of a hash there exists an advanced data structure that keeps the tree-like structure of the syntax tree and optimizations are realized as (for example) rotations, insertions/deletions/pruning etc. After all, after the optimizations we should be able to build a new syntax tree from an optimized version of the code ; does there exist a possible repetitive transformation that does not need intermediate hash-based analysis (maybe I 'm making a hard problem impossible here)?
 
Changed:
<
<
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)
>
>
A: 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)
 

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

Revision 92008-02-06 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 27 to 27
  R Oh, you 're right, I had a typo on the "options" description which I didn't notice (and I added some clarifications to make the whole thing more readable). I wanted to say exactly that Y and Z either appear on the same path or not. I corrected the previous version (wiki-like) so if someone was to see the mistake they shall try the history view.
Added:
>
>
R Thanks for the clarification. Correcting in the proof is a good idea. Can the proof rule out the case I had in the last remark, where both Y and Z are strict dominators of X but the closest one is not the same in the two paths? --Main.ChenDing
 
Q: How do we format a question and an answer?

Revision 82008-02-02 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

Line: 21 to 21
  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 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.
>
>
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 immediate dominators. Let's denote with SDOM(X) the strict dominators 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 X will definitely have 2 immediate dominators if it has 3. Say IDOM(X)={Y,Z} . Then, there exist two options : either Y and Z 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 and thus one does not exist in the execution path of the other and consequently in all execution paths entering X. 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)
Added:
>
>
R Oh, you 're right, I had a typo on the "options" description which I didn't notice (and I added some clarifications to make the whole thing more readable). I wanted to say exactly that Y and Z either appear on the same path or not. I corrected the previous version (wiki-like) so if someone was to see the mistake they shall try the history view.
 
Q: How do we format a question and an answer?

Revision 72008-02-01 - XiaomingGu

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

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)

Revision 62008-02-01 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

Line: 6 to 6
 
Changed:
<
<
Q: More of remarks and vague ideas than questions: in class we discussed about Chris' idea to perform the a=b-c <=> b=c+1 analysis. I had doubts about the idea because I was thinking "=" more of as an assignment operator, rather than the algebraic equality alternative, which pretty much is what it is in this analysis step. I guess thus, that at this level we can perform an even wider variety of symbolic analysis (something that would resemble what Maple does for the common mathematical notations, but in our case solely for Algebra) and generate an even wider range of possible optimizations one cannot possible expect at first sight. I was wondering though to what extent this actually happens, since the way we program brakes down the simplest algebraic expressions into difficult to track simplified steps. I was also wondering whether one can run any optimizations as (syntax) tree-data structure operations, i.e whether instead of a hash there exists an advanced data structure that keeps the tree-like structure of the syntax tree and optimizations are realized as (for example) rotations, insertions/deletions/pruning etc. After all, after the optimizations we should be able to build a new syntax tree from an optimized version of the code ; does there exist a possible repetetive transformation that does not need intermediate hash-based analysis (maybe I 'm making a hard problem impossible here)?
>
>
R: More of remarks and vague ideas than questions: in class we discussed about Chris' idea to perform the a=b-c <=> b=c+1 analysis. I had doubts about the idea because I was thinking "=" more of as an assignment operator, rather than the algebraic equality alternative, which pretty much is what it is in this analysis step. I guess thus, that at this level we can perform an even wider variety of symbolic analysis (something that would resemble what Maple does for the common mathematical notations, but in our case solely for Algebra) and generate an even wider range of possible optimizations one cannot possible expect at first sight. I was wondering though to what extent this actually happens, since the way we program brakes down the simplest algebraic expressions into difficult to track simplified steps. I was also wondering whether one can run any optimizations as (syntax) tree-data structure operations, i.e whether instead of a hash there exists an advanced data structure that keeps the tree-like structure of the syntax tree and optimizations are realized as (for example) rotations, insertions/deletions/pruning etc. After all, after the optimizations we should be able to build a new syntax tree from an optimized version of the code ; does there exist a possible repetitive transformation that does not need intermediate hash-based analysis (maybe I 'm making a hard problem impossible here)?
 
Changed:
<
<
A:
>
>
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)
 

Q: Is there only one immediate denominator 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 :

Changed:
<
<
A block X is a Denominator of Y in a Control Flow Graph, if X appears on every path that enters Y. We write X>>Y and we say X dominates Y. We also say that if X!=Y , then X "strictly" dominates Y.
>
>
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 Denominator of Y is the strict denominator that is closest to Y in an execution path.
>
>
The Immediate Dominator of Y is the strict denominator 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 donimators 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 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.

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)

 

Revision 52008-01-31 - XiaomingGu

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

CS255/455 Spring 2008 Questions and Answers

Line: 6 to 6
 
Changed:
<
<
Q: More of remarks and vague ideas than questions: in class we discussed about Chris' idea to perform the a=b-c <=> b=c+1 analysis. I had doubts about the idea because I was thinking "=" more of as an assignment operator, rather than the algebraic equality alternative, which pretty much is what it is in this analysis step. I guess thus, that at this level we can perform an even wider variety of symbolic analysis (something that would resemble what Maple does for the common mathematical notations, but in our case solely for Algebra) and generate an even wider range of possible optimizations one cannot possible expect at first sight. I was wondering though to what extent this actually happens, since the way we program brakes down the simplest algebraic expressions into difficult to track simplified steps. I was also wondering whether one can run any optimizations as (syntax) tree-data structure operations, i.e whether instead of a hash there exists an advanced data structure that keeps the tree-like structure of the syntax tree and optimizations are realized as (for example) rotations, insertions/deletions/pruning etc. After all, after the optimizations we should be able to build a new syntax tree from an optimized version of the code ; does there exist a possible repetetive transformation that does not need intermediate hash-based analysis (maybe I 'm making a hard problem impossible here)?
>
>
Q: More of remarks and vague ideas than questions: in class we discussed about Chris' idea to perform the a=b-c <=> b=c+1 analysis. I had doubts about the idea because I was thinking "=" more of as an assignment operator, rather than the algebraic equality alternative, which pretty much is what it is in this analysis step. I guess thus, that at this level we can perform an even wider variety of symbolic analysis (something that would resemble what Maple does for the common mathematical notations, but in our case solely for Algebra) and generate an even wider range of possible optimizations one cannot possible expect at first sight. I was wondering though to what extent this actually happens, since the way we program brakes down the simplest algebraic expressions into difficult to track simplified steps. I was also wondering whether one can run any optimizations as (syntax) tree-data structure operations, i.e whether instead of a hash there exists an advanced data structure that keeps the tree-like structure of the syntax tree and optimizations are realized as (for example) rotations, insertions/deletions/pruning etc. After all, after the optimizations we should be able to build a new syntax tree from an optimized version of the code ; does there exist a possible repetetive transformation that does not need intermediate hash-based analysis (maybe I 'm making a hard problem impossible here)?
  A:
Line: 21 to 21
  Question was can that "an" be one/some, or should it be every ?
Changed:
<
<
We denote the list of possible donimators 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)=IDOM(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,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 donimators 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.
 

Revision 42008-01-30 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Added:
>
>
Q: More of remarks and vague ideas than questions: in class we discussed about Chris' idea to perform the a=b-c <=> b=c+1 analysis. I had doubts about the idea because I was thinking "=" more of as an assignment operator, rather than the algebraic equality alternative, which pretty much is what it is in this analysis step. I guess thus, that at this level we can perform an even wider variety of symbolic analysis (something that would resemble what Maple does for the common mathematical notations, but in our case solely for Algebra) and generate an even wider range of possible optimizations one cannot possible expect at first sight. I was wondering though to what extent this actually happens, since the way we program brakes down the simplest algebraic expressions into difficult to track simplified steps. I was also wondering whether one can run any optimizations as (syntax) tree-data structure operations, i.e whether instead of a hash there exists an advanced data structure that keeps the tree-like structure of the syntax tree and optimizations are realized as (for example) rotations, insertions/deletions/pruning etc. After all, after the optimizations we should be able to build a new syntax tree from an optimized version of the code ; does there exist a possible repetetive transformation that does not need intermediate hash-based analysis (maybe I 'm making a hard problem impossible here)?

A:


Q: Is there only one immediate denominator 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 Denominator of Y in a Control Flow Graph, if X appears on every path that enters Y. We write X >> Y and we say X dominates Y. We also say that if X = Y , then X "strictly" dominates Y.

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

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

We denote the list of possible donimators 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)=IDOM(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,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.


  Q: How do we format a question and an answer?

Revision 32008-01-30 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

Revision 22008-01-29 - KonstantinosMenychtas

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

CS255/455 Spring 2008 Questions and Answers

Revision 12008-01-16 - ChenDing

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

CS255/455 Spring 2008 Questions and Answers

This page is intended for anyone to post questions and everyone to answer them. Please insert questions at the beginning and separate each question with a horizontal rule separator. For other formatting instructions read the answer to this question.


Q: How do we format a question and an answer?

A: A question and an answer start with the bold letter Q and A respectively followed by a colon. Use italic text for the question and normal text for the answer. Use a separator (a horizontal rule) after each question. Add new questions to the beginning of the list.


 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback