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

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?

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

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.

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 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))
        num_parms++;


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

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.

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;
}

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.

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?

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 | r36 < r35 < r34 < r33 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r34 - 2008-02-25 - ChrisTice
 
  • Edit
  • Attach
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