Description
This homework exercise builds on the material that was covered in the
Week 5 lecture on assembly code generation, and the Week 6 lab on
runtime organization and functions. This assignment uses a modified
version of the materials for the Week 6 lab. Although the names are the
same, the content is (slightly) different, so be sure that you are using
the right version. You can distinguish the two versions from one
another in several ways. The homework version, for example, includes
this file (hw3.txt) as well as a sample output file, sample.s, and a
simple runtime library, runtime.c, that is written in C.
NOTE: This version of the AsmGen materials can be compiled and executed
on any machine with a suitable implementation of Java. However, the
generated assembly code files are intended to be compiled and executed
on a Linux machine (specifically, on the machines in the Linuxlab).
Other platforms, including both Mac OS and Windows, are NOT SUPPORTED.
Warmup:
——-
As in the Week 6 lab, the supplied code does not include implementations
of the compilation schemes for unary minus (in ast/UMinus.java) or
do…while loops (in ast/DoWhile.java). Be sure that you know how to
complete and test these examples before proceeding.
The version of AsmGen that is provided here eliminates the need for a
special “print” instruction, and instead compiles a statement of the
form “print e;” into a sequence of instructions that first evaluates the
expression e, and then calls a function, “print”, to take care of
printing the value on the terminal. The “print” function is defined in
a small “runtime library” called runtime.c. In particular, this means
that you can now try using AsmGen to compile simple programs in to
assembly language and then use gcc to assemble those programs, together
with code from runtime.c, in to a working executable. For example, you
can use the following commands to compile and run test0.prog:
java AsmGen < test0.prog gcc -o test0 runtime.c out.s ./test0 If you take a peek at the code in runtime.c, you will find that it contains a simple main() function that, in turn, calls Xmain(); the latter is the name that AsmGen uses for the compiled version of the main function in test0.prog. Adding the extra "X" prefix to the names of the global variables and functions in test0.prog like this is a simple (but not foolproof) way to avoid conflicts when multiple entities, written in different languages, share the same name. In a similar way, and for similar reasons, you will also see that the aforementioned "print" function is actually called "Xprint" in runtime.c. As a final note, although it is obviously possible to use Strings like "Xmain" or "Xprint" in the Java code for AsmGen, the preferred way to generate such strings is by using expressions of the form a.name("main"), a.name("print"), or similar, where "a" is an object of type Assembly. This ensures consistency in the way that entities are named and referenced, and would also make it possible to switch, quickly, from the "X" prefix naming convention to some other alternative, if necessary. If you've read, completed, and understood all of the above, then you are ready to move on! Question 1: [15 points] ----------- The new version of the AsmGen code includes support for a form of "for" loop of the form: for (init; test; step) body Each of the init, test, and step portions of a "for" statement is optional, meaning that the programmer can choose to leave that portion of the statement blank. If they are included, however, then init and step portions must be statement expressions (i.e., assignments or calls) while the test must be a boolean valued expression. The body can be any statement (it will often be a block, comprising a list of multiple statements, but this is not required). The following examples illustrate the concrete syntax for "for" loops that is recognized by the supplied parser. Note that only the first example includes all four components: for (i=1; i<10; i=i+1) print i; for (i=1; i<10; ) { print i; i=i+1; } for (;;) { print 1; } The abstract syntax class that is used to represent "for" loops is called "For", and you should inspect its source code in ast/For.java for details of the field names, etc. You will find that it includes implementations of code for printing indented ASTs as well as type checking, but the implementations for code generation are stubs that will trigger a runtime error if a user attempts to compile a program that includes a for loop. Your task in this question is to complete the implementation of "For". Your submission for this part of the assignment should be a carefully commented listing of your implementation [10 points] and a thoughtful description of the steps that you took to verify that your solution was working correctly [5 points]. Question 2: [15 points] ----------- The version of AsmGen that was supplied in the labs does not include code to initialize global variables to the correct values; instead, all global variables are declared using the assembly language ".long" directive with an initial value of zero. We cannot assume that the expressions that are used to initialize global variables will all be simple integer literals. For example, the following is a valid source program: int x = 2; int y = x*x; void main() { print y; } Note that the right hand side of the definition for y is not an integer literal, and not a valid assembly language expression. As a result, we cannot expect just to copy the initial value expressions directly from the source code in to the generated assembly code. One option would be to use an interpreter to evaluate the initial value expressions at compile time and then use those results directly as arguments to the ".long" directive. Instead, for this question, your task is to arrange for the *generated code* to include an extra function definition, called initGlobals(), that will set all of the global variables to the correct initial values. For the example above, the initGlobals function, if written directly in the source language, might look something like this: void initGlobals() { x = 2; y = x*x; } However, for the purposes of this exercise, you are required to generate appropriate target code *without* constructing any new abstract syntax tree structures. As starting points for this task, you are encouraged to review the implementation of the compile() method in ast/Defn.java as well as the implementation of the compileFunction() method in ast/Function.java. As mentioned in the Warmup section of this assignment, in this version of AsmGen, all global variables and functions are assigned names beginning the with the capital letter X in the hopes of avoiding confusion with other names. Specifically, for example, in the assembly code that your solution to this question will generate, the "initGlobals" function will actually appear as "XinitGlobals". As before, you are strongly encouraged to use an expression such as a.name("initGlobals") to generate the output string in this case rather than using the "XinitGlobals" string directly. Your submission for this part of the assignment should be a carefully commented listing of your implementation [10 points] and a thoughtful description of the steps that you took to verify that your solution was working correctly [5 points]. Question 3: [20 points] ----------- The materials that are supplied for this assignment include a sample assembly language output file called "sample.s". This particular file was produced by compiling a source file "sample.prog" with the supplied version of AsmGen. Unfortunately, through a sad and unlikely chain of events, the original source file has since been lost, leaving "sample.s" as the only record of that program. Your task in this question is to study the code in "sample.s" and then reconstruct the original source code for "sample.prog", or at least as close as you can get to that. To accomplish this, you will need to use your understanding of x86-64 assembly language and of the conventions of the System V ABI. You are also welcome to make use of AsmGen as you work to solve this problem. For example, if you think you constructed a program "solution.prog" that you think might, indeed, be a solution, then you can try compiling it with AsmGen (java AsmGen < solution.prog) and comparing the output in out.s with sample.s to see if it really is a match. Do not expect to get everything right first time: be prepared to try multiple experiments, and to break the task down in to multiple steps, each focussed on a different section of code. Your submission for this part of the assignment should include your reconstructed version of sample.prog (or as close as you are able to get) [8 points], as well as a copy of the assembly code in sample.s that you have annotated with diagrams and similar items to document the process that you used to develop your solution [4 points]. In addition, you should also address the following in your answer, labeling these items very clearly to ensure that they are easy to find and identify: - Explain how the original source program might differ from what you have been able to reconstruct in ways that are impossible for you to determine using only the code in sample.s? [3 points] - Identify three different examples of poor code quality in the assembly code for sample.s, and show that you are able to improve on this machine generated code by making (and testing) small patches to fix those issues. [5 points] [And if you're wondering how I might be able to grade this assignment without access to a copy of the original sample.prog: don't worry, I'm sure will be able to find a copy by then in one of my backups ... 🙂 ] Minimum passing grade: ---------------------- You will need to receive at least 15 points, with 5 or more points in at least two of the three questions, to satisfy the minimum grade requirement (i.e., to avoid an F or X for this assignment). ------------------------------------------------------------------------
