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

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

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

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