Time-stamp: <98/05/12 21:09:50 mitchell>

<h3>Frequently Asked Questions</h3>


<ol>
<p>
<li>
<b>(6/4/98) (JF)</b>
<i>
In Project 2, the assignment stated we should only make Phi functions for
pseudo registers.  This does not seem to 
suffice for constant propagation.  This is because Suif unnecessarily
loads everything into temps before it loads them into pseudo registers.
If we treat every temp as NONCONSTs (we would have to because they aren't 
in SSA form) there would be essentially no instructions that could be
optimized.  See the sample code below.

<ul>
<li>main() {
<li>int a,b,c;
<li>a = 3;
<li>b = 4;
<li>c = a + b;
}
</ul>

<ul>
<li>Procedure main:
<li>	ldc  (s.32)	t4 = 3
<li>	cpy  (s.32)	r1 = t4
<li>	ldc  (s.32)	t5 = 4
<li>	cpy  (s.32)	r2 = t5
<li>	add  (s.32)	t6 = r1, r2
<li>	cpy  (s.32)	r3 = t6
<li>	ldc  (s.32)	t7 = 0
<li>	ret 		t7
</ul>
</i>
<ul>
<li>
You are right, this is a problem with getting initial constants.  To
fix it, you need to propagate the initial constant values from the temp
registers to the pseudo registers.  You still don't need to add Phi functions
or do renaming for the temp registers.
</ul>
</p>

<hr>

<p>
<li>
<b>(6/4/98) (JF)</b>
<i>
In Project 2, is the algorithm for Sparse Conditional Constant Prop. in
the book correct?  Consider the following
<a href="problem.ps">example.</a>  How does symbolic execution
ever reach the assignment to even3 on the second iteration of the loop?
</i>
<li> You have found a mistake in the algorithm in the book (and perhaps
the paper, but its ambiguous).  To fix it, you need to change the Visit_Phi
routine.  If the Lattice value of the Phi expression is lowered, then
the outgoing SSA edges from the Phi assignment need to be placed on SSAWL.
</p>
<hr>

<p>
<li>
<b>(5/12/98) (JF)</b>
<i>
Is the algorithm for renaming in the SSA article correct?
</i>
</i>
<ul>
<li>
YES.  The algorithm assumes all statements are either ordinary 
assignments or Phi functions.  If A is an ordinary assignment (ie not
a Phi function) then the RHS is dealt with in the first loop.  If A
is a Phi function, then the RSH is dealt with in the loop over Succ(X).
</ul>
</p>

<hr>

<p>
<li>
<b>(5/7/98)</b>
<i>
How should we print out variables?
</i>
</i>
<ul>
<li>
I've updated <tt>names.c</tt> and <tt>names.h</tt> to add a new
function <tt>print_variable(simple_reg *)</tt>. 
</ul>
</p>

<hr>

<p>
<li>
<b>(5/7/98)</b>
<i>
Should still we print out the stuff from the first project for project 2? 
</i>
</i>
<ul>
<li>
No.
</ul>
</p>

<hr>

<p>
<li>
<b>(4/16/98)</b>
<i>
How exactly should I print out the three outputs?
</i>
</i>
<ul>
<li>
The three outputs will be three lists, so you can just print them out
one after the other, just make sure that you print them in this order:
CFG, dominator, loops.
</ul>
</p>

<hr>

<p>
<li>
<b>(4/15/98) ****NICK MESS-UP ALERT!****</b>
<i>
What's the definitive answer on basic block names?
</i>
</i>
<ul>
<li>Oh boy, sorry about this. Check the updated answer below on basic
block names. In short, forget what I said about "first executable
instruction"; let's simply make it the first instruction (which might
be a label instruction, or might not be). I think we've gone full
circle, which means this time it's right, hehe.
</ul>
</p>

<hr>

<p>
<li>
<b>(4/15/98) ****NOTE: THIS ANSWER HAS CHANGED, AGAIN!****</b>
<i>
What about empty basic blocks (those with no instructions)?
</i>
</i>
<ul>
<li> If you strictly follow the definition of maximal basic blocks, you
shouldn't run into any problems. If there is a suif label instruction,
but no jumps to this label, then that label does not start a basic
block. If there are two consecutive labels and distinct jumps to each
of the two labels, then each starts a (different) basic block!! 
</ul>
</p>

<hr>

<p>
<li>
<b>(4/15/98)</b>
<i>
Does a RET mark the end of a basic block?
</i>
</i>
<ul>
<li>
A RET is basically a "jump to register". a JMP is a "jump to
label". both transfer control and hence mark the end of a basic block.
Remember, we asked you to add two nodes to the CFG, "entry" and
"exit". So the RET instruction adds an edge from the current basic
block to "exit", whereas a JMP adds an edge from the current basic
block to whatever basic block exists at the label.
</ul>
</p>

<hr>


<p>
<li>
<b>(4/13/98)</b>
<i>
Can I modify doproc.c?
</i>
</i>
<ul>
<li> Sure, you can write whatever code you want and put it in whatever
files you want.
</ul>
</p>

<hr>

<p>
<li>
<b>(4/13/98)</b>
<i>
What do you mean by "concatenation" as far as basic block names?
</i>
</i>
<ul>
<li> Please see the item immediately below this one.
</ul>
</p>

<hr>

<p>
<li>
<b>(4/13/98, updated 4/15/98) ****IMPORTANT****</b>
<i>
What about those darn fall-throughs? simplesuif doesn't give them labels.
</i>
</i>
<ul>
<li> Remember how the original handout specified how to name basic
blocks? The technique we suggested doesn't quite work. (sorry!) Here's a better
way. Assign every basic block a unique name which is 
as follows. If the basic block occurs in
a file named <tt>filename</tt> and in a procedure named
<tt>procname</tt> and the <b>first instruction</b>
is the <tt>n</tt>th instruction the
simplesuif stream, then the basic block is given the name
<tt>filename_procname_n</tt>. Notice this clears up the problem with
fall-throughs not having simplesuif "labels". The implication of this
implementation is that we basically ignore simplesuif labels as far as
naming goes. This is probably as it should be.
</ul>
</p>

<hr>

<p>
<li>
<b>(4/13/98)</b>
<i>
Why?
</i>
</i>
<ul>
<li> Jeeze! The simplesuif instructions you're given obviously must
have labels, right? or else the branches wouldn't go
anywhere. However, there is not a one-to-one relationship between
simplesuif "label instructions" and basic blocks. One of the goals of
this project is to find basic blocks (for the CFG). In this respect,
simplesuif "label instructions" aren't the most important concept
(i.e., they don't suffice to name basic blocks).
</ul>
</p>

<hr>

<p>
<li>
<b>(4/13/98)</b>
<i>
Whassup with the multiway branch?
</i>
<ul>
<li> I don't think any language construct should require a multiway
branch for correctness, but it's not that much work to handle it,
anyway. 
</ul>
</p>

<hr>

<p>
<li>
<b>(4/13/98)</b>
<i>
Can I use the C++ graph implementation in the jumpstart directory? 
</i>
<ul>
<li> Yes, go for it!
</ul>
</p>

<hr>

<p>
<li>
<b>(4/9/98)</b>
<i>Can we make any assumptions about the input to our CFG generator?
I'm wondering if we should handle procedure calls and returns?
</i>
<ul>
<li>
   the only support for "calls and returns" is already in simplesuif;
   it supports calls and returns
<li>
   you don't need to create a basic block boundary at a procedure
call, because C and Fortran only allow returns to a single point
("jump to return register"), so:
<ol>
<li>
basic block boundary
<li>   load ...
<li>   add  ...
<li>   call foo   (no boundary before/after here)
<li>   subtract  ...
<li>
basic block boundary
</ol>
<li>
   you don't need to create an inter-procedural control-flow
   graph. that is, if you have "foo calls bar returns to foo", then
   the calling basic block from procedure "foo" doesn't need to have
   an arrow to the target basic block in procedure "bar", and the
   returning basic block(s) in bar don't need to point back to the
   calling basic block in "foo".
</ul>
</p>

</ol>