Clarifications
Assignment 1
------------
Q1. I don't have a UTCS Linux account. How do I get one?
A. Follow the instructions given here:
http://www.cs.utexas.edu/facilities/faq/getting_started/
Q2. How sophisticated does our solution need to be?
A. You should generated C code that passes through gcc (on UTCS Linux
machines) and have the same input/output behavior as the original source
program. That is what is expected.
Q3. Can we always assume that the 3-address-code will be valid or do we have
to do some error checking as well ?
A. Yes. You can assume that the 3-address-code will be valid.
Q4. Regarding the grammar of the 3-address-code, can we assume that there is
always only a single space character between tokens or do we need to
handle any amount of white space ?
A. Yes, you can assume a single space character between tokens.
If you are programming in C/C++/Java/Python/Perl/Ruby, you are
recommended to use regular expressions, string tokenizers, or some
parser library. You then do not have to deal with these trivial issues
like number of white spaces.
Q5. Must the converted C code conform to the grammar prescribed?
A. No. The translated code must be valid C accepted by GCC (on UTCS Linux
machines). The generated code has no relation to the given grammar. The
grammar is only for the input source language. You can use gotos,
labels, pointers, variable arguments, memory management, or any other
feature of C.
Assignment 2
------------
Q6. What is the points distribution for various parts of assignment 2?
A. i. Following instructions for hw2.tar.gz, compile.sh, run.sh
(especially the command line arguments) - 10 points.
ii. The example programs - 20 points.
iii. Identifying the CFG - 20 points.
iv. Constant propagation - 25 points.
v. Dead code elimination - 25 points.
Q7. Do we have to remove unreachable code?
A. No. You do not have to remove the following if (0) { ... } This holds
even after constant propagation. You do not have to eliminate code such
as. { a = 2; if (a > 2) { ... } }
Q8. Does the order of command line arguments matter?
A. Yes. -opt=scp,dce means perform Simple constant propagation followed by
Dead code elimination.
Q9. What is the slip days policy for assignment 2?
A. There are no slip days for assignment 2. turnin will be closed at 9:30
AM on Sep 27.
Q10. How should run.sh work?
A. run.sh should accept the command line arguments specified in the
handout. run.sh will be invoked from the hw2 directory. This script
should read 3-address code as input from stdin and write (the CFG, or
C-code or 3-address code, based on the backend) to stdout.
Q11. How closely should the output of the CFG backend match the TA's CFG
output?
A. Your output should be identical to the TA's output, including
whitespaces. Use 'diff' or 'md5sum' to check that the output is
identical.
Q12. What happens to the instruction numbers when an instruction is
removed? Should instructions numbers be in a sequence?
A. No. If you remove an instruction from the stream, it is okay for that
instruction number not to appear in the output.
Q13. Should constant propagation/dead-code elimination handle global
variables? How about arrays?
A. The two analyses for this assignment should handle local scalar
variables, formal parameters and virtual registers. You do not have to
handle arrays (global or local) or structures (global or local).
Q14. Can I use the TA's solution from assignment 1?
A. Yes.
Q15. If we remove a local variable in a function, do we have to modify the
operand to "enter" and "ret" instructions to reflect the change in the
stack size?
A. No.
A16. What examples did you use for grading assignment 2?
A. dce1.c, dce2.c, and scp.c
Assignment 3
------------
Q17. Do we need to handle global/local arrays and structures and global
variables for Partial Redundancy Elimination?
A. PRE is just another scalar optimization. Please see question 13 above.
Q18. What is the distribution of points for the third assignment?
A. 30 points for the written questions (each question carries 10 points),
and 60 points for PRE, 10 points for following instructions (turnin,
compile.sh, run.sh, commandline options, etc.). Example programs to
test your implementation on will be uploaded soon.
Q19. Will optimizations from assignment 2 be checked for assignment 3?
A. No. However, do keep in mind that these optimizations will be needed
for later assignments, where the quality of generated code will be a
criterion for evaluation.
Q20. Do we need to perform local common subexpression elimination before
performing PRE?
A. Yes.
Q21. What instruction numbers do we give for newly added instructions?
A. Give a unique number that is not used elsewhere. A simple solution is
to keep track of the highest instruction/virtual register number used.
Q22. Where are the example programs?
A. pre-example.c.
Q23. The example has some array address computations that are expected to
be PRE-d. Does this contradict answers to question 13 and 17?
A. No. You do not have to to liveness, constant propagation, PRE, etc.
for global variables, global/local structures and arrays. What this
means is, you do not have to figure out that A[2] is a constant, or
(A[3] + i) is a redundant computation. However, you do have to
eliminate redunancy in address computations. For instance,
a = struct1.field1 + i;
b = struct1.field1 + i;
should become
address = struct1_base + field1_offset;
a = *(address) + i;
b = *(address) + i;
You do not have to change this to:
address = struct1_base + field1_offset;
a = *(address) + i;
b = a;
Q24. Do I have to do a move to a virtual register to eliminate a redundant
expression? Is there a better way out?
A. Let us look a simple example.
instr 10: add a#-8 b#-16
instr 11: add a#-8 b#-16
The second computation is redundant. We could replace it with:
instr 11: move (10) (11)
Moving to the virtual register that the instruction would write too
looks a bit unclean. Let us change that to:
instr 11: copy (10)
Yes, we are introducing a new opcode. You can use this opcode in your
representation if you want to.
Assignment 4
------------
Q25. What is the distribution of points for assignment 4? Are there any
example programs?
A. 10 points for correctly following instructions (turnin, compile.sh,
run.sh, command line options). 90 points for SSA. I will grade over
progressively more complex programs. (30 points for simple basic
blocks, 30 points for simple control flow without loops, 30 points for
handling loops). Test your code on test programs from the previous
assignments.
Q26. When is assignment 4 due?
A. Halloween, Wednesday, October 31, 2007, 11:59:59 PM
Q27. Constant propagation is not mentioned in Q25 above. What does that
mean?
A. Sorry, that was a mistake. Here is the new distribution.
10 points - Following instructions. This part has no partial credit.
You get either zero or 10.
60 points - Constructing SSA
(20 - basic blocks, 20 - simple control flow, 20 - loops)
30 points - Performing Sparse simple constant propagation
(10 - basic blocks, 10 - simple control flow, 10 - loops)
Q27. Do we need the offsets in the SSA example given in the handout? i$0
and i$1 share the same memory location on stack. Is this correct?
A. No, This is incorrect. You do not have to show the offsets. The
handout has been updated.
Q28. Do we have to do Sparse simple constant propagation or Sparse
Conditional constant propagation?
A. Sparse simple constant propagation.
Q29. What are the differences between the various types of Constant
propagation?
A. Take a look at this paper. "Constant propagation with conditional
branches", Wegman and Zadeck, TOPLAS 1991. Take a look at figure 5,
and the explanation around it.
Q30. Do we have to translate out of SSA?
A. No.
Q31. Can a phi instruction have more than two operands?
A. Yes.
Q32. What examples were used to grade assignment 4?
A. basicblock.c, if_0.c, if_1.c, loop_0.c, gcd_function.c, and regssmall.c.
Assignment 5
------------
Q33. Do we have a good reason to not follow the ABI?
A. You can simplify the ABI for the code you generate. For example, you
may choose to not use registers r3-r10 for passing parameters, and
instead pass all parameters through the stack. You still have to
follow the ABI while calling functions in io.c.
Q34. Are addresses of formal parameters incorrect in the csc source
provided for the 32-bit version?
A. Yes. They are incorrect. Thank you for discovering this bug.
The starting address of formal parameters is FP+16 in the 64-bit
version. It should have been FP+8 in the 32-bit version provided, but
instead was unchanged and remained at FP+16. It does not really
matter what the offset is. This is because, either way, you will have
to account for this offet when you generate code to conform to the
PowerPC ABI.
However, it is important that the entire class makes the same
assumption regarding the starting address for formal parameters (in
the csc ABI). So, let us assume that formals start at offset FP+8.
Please change your csc source code accordingly, by applying this patch.
The stack from assignment 1 (for the 64-bit csc ABI) is reproduced
below to refresh your memory.
Low +---------------------+
addr. | |
+---------------------+
-32 | ... |
+---------------------+ <---+
-24 | 3rd local | |
+---------------------+ |
-16 | 2nd local | |
+---------------------+ |
- 8 | 1st local | |
+---------------------+ | Stack
FP ----> | FP | | frame
+---------------------+ |
8 | LNK | |
+---------------------+ |
16 | 2nd param | |
+---------------------+ |
24 | 1st param | |
+---------------------+ <---+
| |
+---------------------+ previous frame.
High | |
addr. +---------------------+
Q35. What is the distribution of points?
A. i. Following instructions and turning the assignment in. (10 points)
ii. Register allocation (40 points)
iii. PowerPC backend (50 points)
The PowerPC backend will be graded similar to the first assignment.
Get it to work atleast on all the example programs (and not just
those). Test it on functions that accept more formal parameters than
the number of general purpose registers.
Q36. gcc's asm output is too hard to understand.
A. Make sure that you have removed all the #defines (for long, WriteLong,
etc.) from the source file before calling gcc.
Q37. Does the computation of the interference graph for register allocation
depend of the code not having any dead statements?
A. Yes. You should do dead code elimination before doing register
allocation.
Assignment 6
------------
Q38. Kernels?
A. Please download the tarball again.
http://www.cs.utexas.edu/users/pingali/CS380C/2007fa/assignments/assignment6/assignment6.tar.gz
Q39. Is there a typo in wavefront.c?
A. Yes, Please download the tarball again.
Q40. Is there an example on how to use Omega?
A. Look at these files: input and output.
Last updated: Tue Nov 27 17:34:47 CST 2007