Daily Research Log

Thursday, April 14, 2022: Submitted final version of thesis to the Graduate School.

Friday, April 1, 2022: Successfully defended my thesis. Only a few small edits to make before submitting to the Graduate School.

Sunday, February 13, 2022: I worked on my thesis outline paperwork today. I have one more section to write on current research in the area, and then I will submit it to the graduate school.

Thursday, February 10, 2022: I met with Dr. Brylow on Teams today to discuss the completion of the coding portion of this project as well as submitting an outline of my thesis to the graduate school. We also discussed the possibility of writing a paper based upon my research and submitting it to a programming languages conference. I am very interested in this possibility.

Thursday, Febrary 3, 2022: Met with Dr. Rubya to discuss my project. Sent Dr. Brylow an update regarding cleaning up the repository and transitioning to writing. Dr. Brylow is satisfied with multi-threaded programs taking a while to finish. He suspects that the Xinu spinlock implementation is the speed bottleneck.

Thursday, January 27, 2022: Met with Dr. Brylow today. We went over my results after figuring out the lock/unlock call issue. We discovered that the version of Xinu that I've been working with did not spawn threads on new cores. We fixed that by setting a static variable to loop around the cores round-robin and spawn each new MiniJava thread on a new core for real concurrent programming.

We revised the ThreadGood and ThreadBad testcases to more closely resemble the testcase given in Adam Mallen's paper. These testcases run as expected, but the ThreadGood testcase takes nearly a minute to complete. I don't know why this is yet. I suspect it has to do with Xinu's scheduler. There may be some changes to monitors to improve their speed. I will investigate this further.

At this point, I will start shifting my time to more writing and less coding. I will meet with Dr. Rubya this Thursday (Feb 3rd).

Thursday, January 20, 2022: Met with Dr. Brylow in person today. we went over my current thesis progress and talked about the ongoing monitor issue with locking and unlocking monitors within synchronized methods. He gave me good feebadk on the thesis and we have a way to move forward with debugging the monitor issue.

Friday, January 14, 2022: I met with Dr. Brylow today. He was able to find Adam Mallen's code for adding lock and unlock to Translate.java. It will take some effort to port over to the latest version of the compiler, but once that is done, things should work well.

I told Dr. Brylow of my intention to have a rough draft of the thesis by the middle of February.

Monday, January 10, 2022: I've added back in Type class constructors without arguments. This lets us revert back some hard-coded constructors in Semant/TypeChecker.java in favor of more "generic" ones. I have investigated further into the issue of _lock and _unlock not working. It seems that the syscalls lock/unlock return an integer on either success or failure. This return value is placed in r0 upon returning from the function. This return value seems to be interfering with the following function's address being calculated and setup to be branched to.

Consider the following example:

L49:
        mov     r0,     r5
        bl      _lock
        // Call sink
        mov     r1,     r0
        mov     r0,     r5
        mov     lr,     pc
        bx      r1
        // Call sink
        bl      _yield

				

I've also been working on chapter 5 of the thesis, regarding access modifiers. I want to get this chapter done within the next day or so. My plan is to have a very rough draft of the entire paper (or as much as possible) by the middle of February.

Wednesday, January 5, 2022: Met with Dr. Brylow today to discuss the progress made over the break.

Thursday, December 30, 2021: As I suspected, it was not difficult to add access modifiers to methods. MiniJava now has public/private fields and methods!

Wednesday, December 29, 2021: I decided to switch gears a bit and put the monitor stuff on the backburner. Today, I have added public and private access modifiers to object fields. This comes from chapter 14 of Appel. He suggests to add a flag in the symbol table for a class to check if a field is public or private. I extended the grammar and parser and have added that private access check in TypeChecker.java. I will try to get this going for pmethods as well. I imagine it will be the same core idea: adding an access modifier flag in the Absyn object and Type object, modifying the grammar, and doing a check in TypeChecker.java.

If nothing else, I can say I extended the compiler to include access modifiers for security reasons. I think that deserves a chapter in the thesis!

I've also been doing some more writing. Today I worked on the parser section of chapter 2. I've also been working on adding outlines to other chapters and have started writing later chapters regarding the thesis' contributions.

Tuesday, December 28, 2021: I have figured out how to insert the lock and unlock calls into method declarations during Translation. However, there seems to be an issue with what arguments are being passed to the lock and unlock calls. We need to access the monitor of an object. Do we pass this to those calls? When running the code, we get BADMON return values, so the monitors are not correctly being passed into lock and unlock.

Monday, December 27, 2021: I have determined that a synchronized function is not being translated correctly. According to Adam Mallen's paper, synchronized method bodies are wrapped in monitor lock and unlock calls during the translation phase. This is not happening. I am trying to figure out how to do this, but I will probably need Dr. Brylow's help.

Sunday, December 26, 2021: I have merged the big-nums branch to the main branch. I have also deleted the concurrency branch because I was unable to rebase with the latest changes from main. Since I didn't do any work on this branch, deleting it was not an issue.

The big-nums branch adds support for large integer numbers (greater than 16 bits). The mov opcode limited us to 12-16 bit numbers. Now we use the ldr pseudo-instruction to let us add larger numbers. What this actually does is, at assemble-time, stores the value of the constant into a word in memory, and loads from that memory location. We will take advantage of this shortcut. This exact solution is something I was looking into implementing within the compiler, but I think it's best that we let the assembler do the work.

Friday, December 24, 2021: I have merged the arm-research branch to the main branch on my fork of the compiler repository. I've created a new branch called concurrency that will focus on getting concurrent operations with monitors working. I will need to re-read Adam Mallen's paper for more details.

Wednesday, December 22, 2021: Memory offsets are now being calculated with the stack pointer as the base. Tested on a number of testcases. BigArgs.java is still not working >:(

Met with Dr. Brylow on Teams. We discussed next steps for the project. He provided me Adam Mallen's monitor code for Xinu. I've been able to get it running, but there are some issues that are not making it run correctly. The next phase of development will try to get Xinu and MiniJava to work together with concurrent programs. Thesis writing continues. We are working on coming up with a good thesis committee. I will send out some emails to faculty members after the winter break ends.

TODO: Add support for integers larger than 16 bits (i.e. splitting into two words and shifting)

Wednesday, December 15, 2021: Met with Dr. Brylow today. We decided to change design directions and revert to using the stack pointer as the base for all memory offsets. This makes things simpler when compiling functions that use more than 4 arguments. Things were getting too confusing with the stack pointer and weird offsets. We also are now properly calculating the frame size. Before, we were not taking into account the 8 bytes representing the FP and SP being pushed to the stack at the top of each frame.

Monday, December 13, 2021: Work from over the weekend and tonight have fixed a bug that prevented recursion from working. When performing a subtraction, the compiler actually was adding one positive number and one negative number. The Codegen branch for that case erroneously was printing a "+" instead of a "-", thus preventing recursive cases from reducing and eventually terminating. Once this was fixed, simple recursive programs, like Factorial.java, started working. Our implementation of Fibonacci also works, however it does not return back to the main process after printing the nth Fibonacci number. We are getting the correct answer, though, after recursively calculating the nth Fibonacci number.

Test cases like NQueens work if we hard code a value instead of using getchar, which still seems to be broken on the Xinu end. BigArgs still does not work and I do not know why. However, I think we are getting to a very good position going into the winter break. We have enough functionality to start writing.

Wednesday, December 8, 2021: Met with Dr. Brylow today. We figured out a main blocking issue with the compiler. When branching to a calculated address (i.e. branching to an address stored within a register), we were not properly linking back. For example:

Moving the program counter into the link register before branching ensures that we can find our way back to where we started and continue along in the program. With further testing, other bugs were found:

• Some 2s compliment numbers 16bits or less are not properly getting emitted within some instructions like add
• Recursive function calls seems to be broken

Sunday, December 5, 2021: Getting back to work after a hiatus due to Thanksgiving and scheduling conflicts. Some small bugs have been fixed. There were a few typos introduced when transitioning from the Mips to Arm backends of the compiler. Neither of those have fixed some programs from not running. Still working on debugging with BigArgs.java. I have not yet isolated how the Mips 16 byte offset gets introduced into register allocation inside the stack frame. The Appel/Tiger book says that this "shift" should be implemented inside the Frame class for a particular architecture. The only thing that explicitly references 16 is the CONST16 methods. However, I think those methods just make sure we are only using 16bit integers. Otherwise, things might get tricky with larger and larger numbers. I guess this makes sense for a "toy" compiler such as this with no floating point number support.

This will need more study and help from Dr. Brylow.

Writing Update: It is my intention to get a LARGE amount of writing done during the winter break in between semesters. This seems like a good time for this to happen.

Tuesday, November 15, 2021: I have registered for Spring 2022 classes, including COSC 6999.

I fixed some formatting issues with some Tikz figures in Chapter 2 of the thesis.

Coding Update
Can we run the legacy MIPS code on the SPIM simulator or MIPS Xinu? It may be useful to see a working reference implementation. Also, I was wrong! You CAN add constants INSIDE OF an ARM opcode. This simplifies the code so we can remove those un-needed moves and adds! Because of that realization, I have been able to remove any push/pop calls and have fixed an issue where LR was being treated as a special register and not a callee-save register. This was preventing it from being moved on and off the stack appropriately in order to return. Function prologues/epilogues look much neater and closer to the MIPS style.

There is still a problem with argument/return registers. In MIPS, there are separate registers for holding function arguments and function return values. In Arm, r0 serves as both the first argument register and the return value register. I think this is the cause of some of our issues.

Sunday, November 14, 2021: Worked on commenting out the now-unnecessary push/pop code and making sure the original ldr and str opcodes are still present within the frame prologue and epilogue. I am still unable to get proper returning without including push/pop pc, lr. More information will be needed to get the MIPS-style frame behavior. There is still an issue with the new Xinu system call.

Thursday, November 11, 2021: Met with Dr. Brylow and discussed the issue with push/pop registers. We learned that each callee-save register is getting moved onto the stack in MIPS. The redundant moves are eliminated by the compiler optimization, so the essential live-in registers remain. Additionally, it would be difficult to implement "dynamic" push/pop opcodes in frame prologues and epilogues because there is no IR node that represents these opcodes. For now, we will stick with the original design decision of just manually moving registers on and off the stack.

We discussed some administrative paperwork and I emailed Jackie about scheduling a section of COSC 6999: Master's Thesis with Dr. Brylow as the instructor.

Sunday, November 7, 2021: Progress is moving slowly now. I have been busy with work/unmotivated, so I have not made much substantive progress. However, I have identified some issues:

• Both the MIPS and ARM compilers treat functions without any "action" as having a framesize of 0. For example:
  
  public SomeClass init() { return this; }
  
  
  Since MiniJava doesn't really have constructors, this is how we can "get" an object. This code snippet is compiled with a framesize of zero. I suspect that since no variables are declared within the body of the function, no offsets from the stackframe are needed. This is a problem, though, because I need to "get" an object before I can call one of its methods. I still think this has something to do with argument passing. Another issue with this frame setup is that no push/pop opcodes are generated. There must be some limit of the grammar that does not allow for "empty" functions.
• Return values are being stomped on by function epilogues. A return value from a function gets moved into r0, but then gets overridden by the function epilogue using r0 to manipulate the stack pointer. Example:
  
  

  						
  L6:
          ldr     r0,     =L9
          bl      _print
          // Call sink
          bl      _println
          // Call sink
          // THIS ONE
          mov     r0,     #1
          b       L14
  L8:
          ldr     r0,     =L5
          bl      _print
          // Call sink
          bl      _println
          // Call sink
          add     r0,     r5,     #1
          mov     r5,     r0
          b       L7
  L14:
          add     r0,     fp,     Hellorun_run_framesize
          mov     r0,     r4
          mov     r7,     r6
          ldr     r6,     [fp, #-4]
          ldr     r5,     [fp, #-8]
          ldr     r4,     [fp, #-12]
          // return from Hellorun_run
          sub     sp,     fp,     #4
          pop     { fp, lr }
          bx      lr
  												
  						

  
  
  
  Notice how the mov in L6 moves a 1 into r0, the standard ARM return value register. Then the program branches to L14, where r0 gets demolished by the setup for the return. I do not know how to get around this, yet.

Wednesday, November 3, 2021: Walked to Dr. Brylow's office. He was not there.

Wednesday, October 27, 2021: Met with Dr. Brylow today. We had a good discussion and made some design decisions about how to implement Arm frame prologues and epilogue, using push and pop and inline offsets in an effort to eliminate some of the unreadable Mips-era code generation.

Saturday, October 23, 2021: It has become apparent that there are several issues with ARM stack frame generation. The previous MIPS backend is unable to adequately be converted to return from ARM functions as of right now. I will need to discuss with Dr. Brylow more about:

• Creating and destroying stack frames
• Returning from a function
• Returning from a callee function to a caller function
• Whether we need to start using push and pop calls

Wednesday, October 20, 2021: Met with Dr. Brylow today. Showed him my progress on the code and my thesis. He gave me the minijava.c file that implements some of the system calls used by the MiniJava compiler. He also showed me how to compile the output of the MiniJava compiler into Xinu.

There were initially some issues with getting the code to compile, but we can now compile very basic programs. Concurrency features are not yet supported. A bug was discovered with the register allocator. Certain registers were being used that were being overridden by procedure calls. This was resolved. An outstanding issue remains when trying to return from a function call nested within another function call.

TO DO: Keep working on writing. Get all basic functionality working before implementing other "nice-to-have" features, like concurrency. Contact Praveen regarding graduation.

Sunday, October 17, 2021: Arm/Codegen.java is complete, but generates semantically incorrect ARM. One large issue of note is that any generated macros contain a . and are causing issues when assembling. I am trying to track down where a period is getting added to the frame's name, but I am not having much luck as of yet. Once that is solved, there are two more large problems that need to get fixed:

1. Function prologue/epilogue
2. str syntax

Currently, the ARM code generator inherits MIPS-style stack frame allocation, which involves a set of moves and stores to get caller-save registers figured out. This will need to get changed so that ARM push/pop opcodes are called instead. Also, instead of executing a bx 000000de> statement at the end of a function, the ARM code generator uses the MIPS method of subtracting from the stack pointer to move into the scope of the caller function. I am unsure if this works in ARM. I may need to find a way to keep track of the caller and branch to it at the end of the callee.

Saturday, October 16, 2021: Nearly done with Arm/Codegen.java and will begin preliminary testing ASAP. Also, started thinking about organization for Chapters 2 and 3, Background and Related Work chapters.

Friday, October 15, 2021: Continued work on Arm/Codegen.java. Had some realizations about the ARM architecture vs. MIPS, so I needed to refactor a bit of the code. Some legacy things like Frame. ZERO were retained in order to make code emission easier. In the Arm package, Frame.ZERO#0, since MIPS uses a zero register to hold the same value. The easiest solution, to me, was to just set that "register" to the immediate zero value.

Wednesday, October 13, 2021: Had weekly meeting with Dr. Brylow. Had a good discussion and several questions answered. Contacted Alex G. to get a copy of the Research Xinu source.

Code Progress:
Finished initial modifications of Arm/ArmFrame.java, Arm/InReg.java, Arm/InFrame.java. Started working on Arm/Codegen.java. Worked on converting store convention from Mips to Arm.

Writing Progress:
More messing around with formatting. Got the go-ahead from Dr. Brylow to start writing some sections. Will start on Background chapter this week. It is still unclear what the overall goal is of the thesis, but that's okay for now.

Saturday, October 9, 2021: Bookmarked important sections of Dragon Book Chapter 8 and Appel Chapter 8. Started considering how to create Arm Basic Blocks. Wrote a cheatsheet on Arm 32 bit registers.

Friday, October 8, 2021: Read the first half of Dragon Book Chapter 8. Looked more at existing compiler codebase. Began thinking about thesis chapters.

Thursday, October 7, 2021: Dr. Brylow gave me access to the ConcurrentMiniJava compiler GitHub repository. I have forked that repository into my own GitHub account. After doing so, I cloned the repo to my Morbius home directory. I began laying out the Arm package. I have also written a bash script to build the compiler for me. I will need to brush up on my ARM assembly.

TODO: Ask Dr. Brylow for the latest stable version of multicore Embedded Xinu.

Tuesday, October 5, 2021: Compilers: Principles, Techniques, & Tools arrived in the mail. Began skimming the first few chapters. Added to list of sources.

Friday, October 1, 2021: Read Mallen & Brylow compiler paper. Added to list of sources.

Wednesday, September 29, 2021: Met with Dr. Brylow to go over expectations and to discuss a topic. A topic was selected: work on porting the MiniJava compiler to ARM and bring in cryptography and concurrency libraries.

TODO: Read Mallen & Brylow Compiler paper, submit thesis paperwork.