CSE 401 / M501 18sp - Project V - Compiler Additions

Due: Thursday, May 31 at 11 pm. You will "turn in" your project as you did with previous assignments by pushing it to your GitLab repository and providing a suitable tag. The final code and tag must be committed and pushed by the deadline. See the end of this writeup for details.

CSE M 501 students should include these additions along with their final project and submit those together by the deadline given in the CSE M 501 Project Additions assignment description.

Overview

For the final part of the project, extend your MiniJava compiler by adding support for IEEE-754 64-bit floating point numbers. The support should include the new type double, constants, output, assignment, and basic arithmetic operations. You do not need to implement conversions between ints and doubles; doubles essentially live in a parallel numeric universe similar to that occupied by ints, but not interacting with them.

As with the rest of MiniJava, the resulting language should be a proper subset of standard Java, and programs executed with your MiniJava compiler should have the same behavior that they have when executed using javac/java.

You should make appropriate changes to your compiler to scan, parse, type-check, and generate code for programs that use these new floating-point additions.

You should continue to use your CSE 401 gitlab repository to store the code for this part of the compiler project.

Requirements

  • Add Type ::= "double" as a new production. "double" is a new reserved word.
  • Add Expression ::= <DOUBLE_LITERAL> as a new production.
  • Allow parameters, variables, and object fields of type double, and use of double values in assignment statements and as arguments and return values in method calls.
  • Overload the operators "+", "-", "*" and "<" to support double values.
  • Overload System.out.println so it can print double values as well as integers. Numeric output should be formatted as it is in standard Java. We have provided a set of C routines to convert values of type double to strings in the proper format (see the implementation section below).

Restrictions and simplifying assumptions

  • A <DOUBLE_LITERAL> should have the form of a Java decimal floating-point literal containing decimal digits, an optional decimal point, and an optional exponent part consisting of the letter "e" or "E" followed by a signed integer exponent. As in Java, there must be at least one digit and either a decimal point or an exponent (or both). You are not required to implement Java’s "float suffix" ("f", "F", "d", or "D" following the rest of the literal). You may restrict the syntax further if needed so that it can be directly included in an assembly-language program as a floating-point literal (although we don't think additional restrictions should be necessary).
  • You do not need to support implicit or explicit conversions between doubles and integers, including implicit conversions in assignments or method calls, or implicit conversions needed to support mixed-mode arithmetic such as 1 + 2.0.
  • You do not need to deal with unusual double values like NaN and IEEE floating-point infinities.

Implementation

  • You should use the x86-64 SSE registers and instructions to implement doubles using 64-bit IEEE floating-point arithmetic. The web site for the Bryant/O’Hallaron textbook used in CSE 351 has a good introduction to and description of this part of the x86-64 architecture. See http://csapp.cs.cmu.edu/public/waside/waside-sse.pdf. You also may find it useful to write small C functions using doubles and look at the assembly code generated by gcc -S.
  • Generating code to compare doubles can be somewhat tricky if you support the full IEEE standard and Java semantics for floating point, but since you are not required to deal with NaNs and other unusual values, it should not be much more difficult than dealing with integers. However, if you want, you could add a C function to boot.c to do some or all of the work and generate compiled code to call this function as needed.
  • You should use the x86-64 C language calling conventions for functions with double-precision floating point values in their argument lists. Again, see the Bryant/O’Halloron SSE floating-point discussion for details. Note that doubles have a separate set of registers. You will need to be careful with parameter lists that have a mixture of doubles and other values, and you need to be aware of how registers are used when functions are called (i.e., which registers need to be saved and restored across function calls, etc.).
  • Output of doubles is somewhat tricky because the formatting needed to convert a double to a string whose format matches the one used by Java is fairly complex, and not quite the same as that produced by any of the basic C printf format strings. We have provided two files, number_converter.h and number_converter.c, that contain a function convert_double that creates the string representation of a double value using the rules defined by Java. These rules are found in http://docs.oracle.com/javase/8/docs/api/java/lang/Double.html#toString-double-. You do not need to understand how this code works, but it is interesting to see what is needed to do these conversions correctly.
  • You will definitely want to add code to boot.c to implement System.out.println for doubles by calling the supplied formatting functions and then printing the formatted string.
  • You will need to figure out how you want to handle <DOUBLE_LITERAL> constants in your source code, and how to include those constants in your generated code. You could use Java library routines in the compiler to convert constants to binary values of type double, then generate code with hexadecimal or integer values that would assemble to the correct binary data bits. But it's probably (much) simpler to let the assembler handle this by copying the floating-point number into the generated code as a constant data value and let the assembler’s .double directive to do the conversion for you. A line of code that looks like 
    pi:  .double  3.1415926535e0
    can be used to add a labeled constant in a .data section in the generated code. (Note: it is possible that there are edge cases where the assembler and Java might convert the same double literal to binary values that don't agree exactly in the final bit or two. Feel free to ignore those possibilities for this project.)
  • To load an integer constant into a register in the x86-64 architecture, a simple move instruction containing the constant value can be used (e.g., movq $17,%rax). The x86-64 SSE architecture doesn't provide an immediate constant mode that works like this for floating-point values. Instead, the constant value needs to be stored in memory (possibly by using a .double directive as described above), then it needs to be loaded into a register from memory. Because of quirks in the assembler, you may need to explicitly specify the addressing mode in the movsd instruction. For example, to load the constant pi shown above into the xmm0 register, you can use the instruction 
         movsd  pi(%rip),%xmm0

Extra credit

As with the rest of the compiler project, a small amount of extra credit will be awarded for extensions that go beyond these basic requirements. However, do not attempt extra credit extensions until you have the required compiler addition working properly. Extra credit will not be awarded to projects that do not include a substantially correct implementation of double. Some possibilities:

  • Add arrays of doubles. (This one should be quite simple, actually.)
  • Support mixed-mode arithmetic using doubles and ints, and widening conversions from int to double in assignment statements and method argument lists.
  • (harder) Add type casts (int) and (double) to convert between numeric types.
  • Add "built-in" functions like sqrt. The best way to do this probably would be to add additional syntax for Math.sqrt(...) somewhat like the way System.out.println(...) is already done.

What to Hand In

As with previous parts of the project you should include a brief file, called ADDITIONS-NOTES.txt this time, describing anything unusual about your project, including notes about extensions, clever code generation strategies, or other interesting things in this phase of the compiler. You should give a brief description of how much is working and any major surprises (either good or bad) you encountered along the way. In particular, this phase of the project will involve making changes to previously implemented parts of the compiler. Include a brief description of what was done and why it was needed, and whether there were any unanticipated changes required. This file should only discuss this phase of the project. After finishing the project code you will be asked to prepare a (short) summary report about the entire compiler project. Details will be supplied in a separate assignment.

As before you will submit this part of the project by pushing code to your GitLab repository. Once you are satisfied that everything is working properly, create a additions-final tag and push that to the repository. Then we strongly suggest that you create a fresh clone of your repository in some completely different temporary directory, checkout the additions-final tag, and verify that everything works as expect. If necessary, fix any problems back in your regular working copy of the code, push the changes to the repository, and update the additions-final tag to refer to the correct commit in the repository.

Be sure that your boot.c runtime code is in src/runtime/boot.c, and that the number_converter.h and number_converter.c files are also copied into this directory.