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


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)

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

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?

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

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

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

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.

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

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

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?

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.

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 ?

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)

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.

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?

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.

Edit | Attach | Watch | Print version | History: r62 | r25 < r24 < r23 < r22 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r23 - 2008-02-21 - KonstantinosMenychtas
  • Edit
  • Attach
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback