Project Proposal: ChocoPy to Bril

[Smubge]

What will you do?
Research the utility of TBAA for Rust. More specifically, how TBAA metadata could improve optimization in Rust’s LLVM backend, the difficulties of doing so, and whether current LLVM optimizations fully leverage Rust’s type system.

How will you do it?
To evaluate the utility of TBAA for Rust, I will do the following:

1. Study how TBAA works in LLVM and how it is applied in other languages (like C/C++) to inform potential benefits for Rust.
2. Examine Rust’s LLVM IR output (using rustc --emit=llvm-ir) to determine whether and how TBAA metadata is currently used.
3. Modify small Rust test programs to explore aliasing behaviors and inspect resulting optimizations with and without TBAA-related metadata.
   Consult compiler sources: Review relevant parts of rustc_codegen_llvm to understand current TBAA integration and identify missing opportunities.

How will you empirically measure success?
I will measure the differences in generated LLVM IR and resulting performance (e.g., runtime, binary size, optimization passes triggered) with and without TBAA metadata, assess whether Rust’s aliasing semantics could safely permit more aggressive optimizations under TBAA assumptions without violating language safety guarantees. All of these will be supported with code examples and performance data.
Team members:
Me (Jonathan Brown)😃

[sampsyo]

Hi, @Smubge! While this is clearly an interesting area, the project you have described here appears to just be about observing how things currently work—I don't see what you are going to build. You do say that you want to "identify missing opportunities," but again that sounds like just thinking and writing, not implementation. This course project really needs to have an implementation component.

Unfortunately, I think that designing something to implement in this space is pretty hard! So while I'm tempted to say "please come up with an idea for what optimizations you will implement and how you will implement them," I kinda-sorta think the more responsible feedback is more like "maybe you want to go back to the drawing board." That is, unless you have a pre-existing idea of a super-duper-specific change you want to make to the Rust compiler or LLVM, maybe it would be a good idea to pick a different area? As I warned in #594 (comment), this general idea is problematically open-ended and may not be a good idea unless you have a brilliant idea about how to narrow the scope.

Does this make sense?

[Smubge]

Project Proposal: Extending TBAA Integration in Rust’s LLVM Backend
What will you do?
I plan to build a small LLVM pass that adds TBAA metadata to memory operations in the LLVM IR produced by Rust using rustc --emit=llvm-ir. I will show how Rust’s ownership/aliasing rules can be used in TBAA metadata so that more optimizations can be performed. I want to show that Rust’s aliasing guarantees can be represented in a manner that allows LLVM to safely assume when different memory accesses interfere with one another.
How will you do it?
To complete this project, I will:

• Learn how LLVM’s TBAA system works and look at how Clang generates !tbaa metadata for C and C++ programs.

• Research and inspect the LLVM IR that Rust produces (using rustc --emit=llvm-ir -O on test cases) and see where aliasing information is missing.

• Write a LLVM optimization pass in rust using the llvm-sys library that adds TBAA metadata to Rust-generated IR.

• Focus the pass on simple cases, (Ex: distinguishing between fields in a struct or between different primitive types).

• Run the pass on several benchmark programs. Then compare the LLVM IR before and after and check if re-running LLVM’s optimization pipeline with opt -O3 leads to stronger optimizations.

• Ensure overall correctness and that the modified program is not causing any errors.

How will you empirically measure success?
I will consider the project successful if the LLVM IR after applying the pass contains valid and well-formed TBAA metadata in places where it was previously missing. I will consider it more of success if the optimization passes like global value numbering or loop invariant code motion become more effective as a result of this pass. I will measure improvement by looking at changes in the number of memory operations, binary size, and runtime performance across benchmark tests. Even small gains in optimization will show that Rust’s aliasing model can be used more effectively when combined with TBAA.
Team members:
Me (Jonathan Brown)

[sampsyo]

OK! This is getting a bit more concrete, but I still have some questions:

Write a LLVM optimization pass in rust using the llvm-sys library that adds TBAA metadata to Rust-generated IR.

I'm not totally sure how this would work as an LLVM pass. It seems like, if the type information is not available in the IR when originally generated, then a pass would not have any chance of "recovering" this missing information? The only way to "enrich" the IR with more type information would be to have rustc itself generate that in the first place. Am I missing something?

Research and inspect the LLVM IR that Rust produces (using rustc --emit=llvm-ir -O on test cases) and see where aliasing information is missing.

FWIW, this is the riskiest part of the project: there may simply be no obvious place where TBAA information is missing. So if you go down this path, I'll request that you set yourself a deadline to do this initial exploratory "just manually look directly at the IR and think real hard" step, and write a brief summary here of the results. If you catch places where TBAA information is clearly missing, then you can go ahead with this project. If you do not have any evidence of this kind of missing data, then you'll need to pivot again…

[Smubge]

FWIW, this is the riskiest part of the project: there may simply be no obvious place where TBAA information is missing. So if you go down this path, I'll request that you set yourself a deadline to do this initial exploratory "just manually look directly at the IR and think real hard" step, and write a brief summary here of the results. If you catch places where TBAA information is clearly missing, then you can go ahead with this project. If you do not have any evidence of this kind of missing data, then you'll need to pivot again…

In this case should I come up with another idea? Another idea that I had for a project proposal was the ChocoPy to Bril suggested in project proposals. Would it be alright if I attempt the current idea and if there are clear gaps that exist then I would implement the pass, and if not I could do the ChocoPy to Bril project? Also, sorry for the misunderstanding about the LLVM optimization pass, what I meant was that it would take cases where enough structural info is present in the IR to attach TBAA metadata after the IR is generated and see whether it changes how LICM/other optimizations behave. To be clear, this is not an attempt to reconstruct full Rust Types, but to build a simpler TBAA based on rustc after it emits the LLVM IR (by seeing whats there via the IR, not using Rust's checkings).

[sampsyo]

In this case should I come up with another idea?

I'll have to leave that decision to you. What I'm trying to do here is give you feedback about what constitutes an actionable, evaluatable plan—it's up to you to decide whether you think each given area has such a project idea within it.

Another idea that I had for a project proposal was the ChocoPy to Bril suggested in project proposals. Would it be alright if I attempt the current idea and if there are clear gaps that exist then I would implement the pass, and if not I could do the ChocoPy to Bril project?

This would need to happen quickly. Because we're now 10 days past the proposal deadline, we are now about one month from the full project deadline. It would not be OK, for example, to spend 3 weeks attempting one project, give up, and then spend 1 week doing the other—avoiding that exact scenario is the reason I am being so annoying about forcing students to have a workable plan up front. Do you think you could do enough exploration to have a decision by, say, Monday?

what I meant was that it would take cases where enough structural info is present in the IR to attach TBAA metadata after the IR is generated and see whether it changes how LICM/other optimizations behave. To be clear, this is not an attempt to reconstruct full Rust Types, but to build a simpler TBAA based on rustc after it emits the LLVM IR (by seeing whats there via the IR, not using Rust's checkings).

The trouble here is that we would need to know that this "structural info" actually exists. I don't quite see what this information would consist of. So we would need a specific notion of exactly what this is in order to continue.

[Smubge]

Hello, due to the little information I have found concerning the rust TBAA project. I will be switching to the Chocopy to bril project. I will still try to do the TBAA project in my free time as it seems like a very interesting project. Thank you for helping and guiding me through the decision process.

[sampsyo]

OK! Can you please write a proposal detailing exactly what you will do for this new project?

[Smubge]

Apologies for the delay, I did not see this message.

What will you do?

I will implement a frontend that translates ChocoPy to Bril. I will be utilizing an existing ChocoPy parser and generate correct Bril code for a representative subset of the language.

How will you do it?

I will first use an existing ChocoPy parser, and implement a traversal over the ChocoPy AST that emits Bril instructions, create a mapping from ChocoPy semantics to Bril IR.

How will you measure success?

In order to test this, I will use differential testing, running the same program through the official ChocoPy implementation and the ChocoPy -> Bril.

I will compare how many semantics are covered, how the pipeline works with bril tools, and show examples of ChocoPy programs being compiled to Bril and then executed.

[sampsyo]

OK! Sorry if I am starting to sound like a broken record, but I will still need some more concrete details from you to make this a complete plan.

1. What "existing ChocoPy parser" will you use? You can draft off of the work done in Project Proposal: ChocoPy2Bril #603, which is also attempting the same thing, to find options. I am particularly interested in whether you are going to use the standard JSON format for the ChocoPy AST, and therefore keep the parser in a separate program, or use a more conventional parser as a library.
2. How much of the ChocoPy language will you cover? Which features will be supported vs. unsupported? Recall that this proposal is supposed to act as a "contract" that I can use to judge whether you were successful, so I need to know these specific "goal state" criteria.
3. Where will you get your test cases? How many programs will you use?
4. You say you are going to use differential testing with "the official ChocoPy implementation." Can you provide a link to the exact implementation you are talking about?
5. Are you planning on measuring anything about performance, or just correctness?

[Smubge]

Apologies for the late reply. I just saw this. I am already well started in my project so here is my sketch up.

1. The existing ChocoPy parser that will be used is here
2. Features that I will cover concerning ChocoPy's language will be:

• Types: Integers, Booleans, chars, strings.
• Basic Operations: + - * // % < <= > >= == != and or not
• Local variable assignment and declaration
• If/else and while loops
• Function definition, argument passing, return statements
  Things that will be excluded are but not limited to
• lists
• lambdas
• exceptions

3. My test cases will be obtained from here, pruned to be the test cases that fit the feature implementations . I will use ~20 programs.
4. I realized I am unable to make use of it without being an instructor, so for now I'm going to just make use of python as a baseline.

5. I am not planning on measuring anything about performance, just correctness.