Discussion on Alias-Based Optimization 10/30

[CynyuS]

This is the discussion thread for: Type-Based Alias Analysis
Amer Diwan, Kathryn S. McKinley, and J. Eliot B. Moss

Discussion leaders: Jonathan Brown @Smubge, Cynthia Shao @CynyuS, Pedro Pontes Garcia @pedropontesgarcia

[Nikil-Shyamsunder]

I feel that the primary contribution of the paper isn’t the alias analyses themselves, but the new evaluations and benchmarks they use that contextualize alias analyses within the optimizations they use for. The authors argue that static metrics like the "may-alias" set size are misleading because they don’t capture whether the analysis actually improves compiler optimizations. That is, precision isn’t meaningful in isolation from its downstream clients. Instead, they propose dynamic and limit-based evaluations, showing how an alias analysis should be measured by its impact on optimizations like redundant load elimination and by how close it gets to an upper bound of achievable improvement. I also found it striking how much language design influences alias precision: writing a sound alias analysis for a language like C with void pointers is inherently harder than for Java. This suggests that designing languages or type systems that enforce strong aliasing semantics could be just as impactful as designing better analyses themselves.

Discussion question:
If we designed new languages with alias-precision as a first-class goal, what kinds of type or ownership systems might emerge to make alias analysis almost trivial?

[pedropontesgarcia]

Agreed on the evaluations! To answer your question, I think the obvious example is Rust: as the type system prevents multiple mutable references to the same data at the same time, we can consider mutable references to be completely non-aliasing. In this sense, then, writes are always non-aliasing, but reads can definitely be. Going further and preventing aliasing for immutable references, which Rust does not do (as you can have multiple immutable references at the same time) seems somewhat undesirable, as it would possibly result in more copying of data and a loss of flexibility for the programmer. But it's definitely an interesting question!

[maheshejs]

Critique
I enjoyed reading this paper. It’s easy to follow, especially in how it introduces the three techniques for type-based alias analysis (TBAA). Surprisingly, the main content is only about three pages long, with the rest dedicated to the evaluation section. I really like how thorough the evaluation is as it gives more insight into how clients, like redundant load elimination (RLE), benefit from alias analysis, something static evaluation cannot capture. I also appreciated the comparison against an upper bound that represents the best possible performance any alias analysis could achieve for RLE. I was surprised that more sophisticated alias analyses would actually give diminishing returns in practice.

Question
In Section 3.5, thy mention that encapsulation (dope vector accesses used to index open arrays) is the main source of the remaining redundant loads. They note that this comes from a limitation of the representation itself, rather than from TBAA or RLE. That makes me wonder: could TBAA be applied to an IR (LLVM for instance) where encapsulation is lifted?

[pedropontesgarcia]

I think the answer to your question is yes! I would be very curious to see if this does help with redundant loads, as suggested.

[jeffreyqdd]

Critique

This was a fun reach, and I think that baking types into alias analysis is a step in the right direction. The paper put forth solid arguments backed with good analysis -- I especially liked how it used a "shadow heap" to establish an upper bound on redundant loads and to justify that TBAA came quite close to the "best" solution. TBAAalso brought to my attention how destructive concepts like reinterpret_cast in C++ are to compiler optimizations. I wonder if TBAA can still be implemented in C/C++ to a lesser extent (and how does that compare to the current baseline).

On a completely separate note, I'm extremely curious as to how Rust's type system can be used to perform alias analysis since it's impossible to have a mutable view into memory from two variables with intersecting lifetimes in safe Rust.

Question

1. Rust essentially has alias analysis built into the type system. How can compilers take advantage of this information? Does the information provided supportTBAA or does it render TBAA obsolete?

The in-class example would not compile in Rust!

fn foo(a: &mut char, b: &mut char) -> bool { ... }
foo(&mut a, &mut a); // does not compile. a and b must alias different memory locations!

fn bar(a: &char, b: &char) -> bool { ... }
bar(&a, &a); // this is valid rust

[pedropontesgarcia]

Actually, as Prof Sampson pointed out in a discussion, C and C++ consider casting between pointer types as undefined behavior! This means that TBAA is generally valid there too. We will hopefully discuss Rust's proposal in more detail tomorrow, but in essence its compiler does take advantage of the stricter aliasing system, but it didn't for a while due to an LLVM bug.

[jku20]

Critique

The evaluation on this paper is pretty epic. It does a really good job breaking down why the authors felt comfortable stopping where they did in what when presented feels like a pretty simple analysis (at least compared to some of the other ones we've read about). However, I still question why they stop when they do. The argument the authors make after evaluating their cases is that with respect to RLE, the alias false positives their analysis detects aren't impactful. Maybe it's due to a lack of examples, or an absence of a classification of the contrived failure cases the authors mention, but I don't find the authors' argument extremely convincing. Phrase another way, I feel like I am curious about why, qualitatively, the cases which are missed don't hurt RLE's performance.

Question

The authors mostly analyze objected oriented languages, Modula and Java and with strong but in the grand scheme of languages somewhat simple type systems. The authors describe how some languages features, like structural type equality, can hurt the alias analysis when incomplete programs are analyzed. How could other languages' features or languages not following the object oriented paradigm (for example, maybe OCaml) hurt or help this analysis?

[pedropontesgarcia]

I'm not sure I would agree that Java's type system is simple! Generics and ? add dimensions of complexity that did, in fact, break the type system for a while. I am curious to see examples of type system features that could harm TBAA.

[mercure67]

critique

I thought the optimisation presented seems like a reasonable follow-on to type-based programming. I'm a bit curious about some of the results presented in analysis, though. First, they use a simulator for testing the optimised programs --- is there a reason to do this? Or were the problems with using simulated systems not as widely known at the time? Second, they don't seem to cover the effect of their analysis on compilation time. I would think that the effect is perhaps lengthening compilation time a little, but wonder if that's the case.

questions

The paper seems like something 'obvious' for compilers to implement, and the results seem pretty promising. How wide is use of this type of system, and are there notable languages / compilers which don't implement it?

Otherwise, to what extent is this type of alias analysis general to other types of compiler-y things? Like, beyond the realm of incidentally type-unsafe languages --- what about to dynamically typed and/or interpreted languages? Could we still benefit from using these types of metrics on them (albeit in a slightly different way)?

[pedropontesgarcia]

It is possible that some problems that have been identified with simulated systems were not a major consideration back then, the paper is two decades old after all! I am really curious to read more on this, if you'd want to provide some links to the topic. I think one of the takeaways wrt compile time is that this alias analysis is faster than something like a DFA, since it can be done much more statically/locally. But agreed that further evaluation could be helpful here. To answer the question about current usage, in my understanding TBAA is performed widely by compilers, LLVM in particular annotates memory accesses with types to perform it.

[SyphonArch]

Critique

I thought the paper did a good job showing how type information can make alias analysis simpler and still fairly effective. The evaluation feels thorough, with both static and dynamic analyses and even an upper-bound comparison. That said, it also seems quite tied to Modula-3's strong type-safety assumptions. I'm not entirely sure how much of the approach would hold up in more common languages like C or C++, where pointer casting is much looser and type information can be less reliable. It makes me wonder whether the strong results come more from the guarantees of Modula-3 rather than the analysis itself. Which, of course, could be made into an argument for type-safe languages.

Discussion questions

1. How much of the effectiveness of TBAA depends on Modula-3's strict type system, and how might it behave in a less type-safe language?
2. Would it be possible to adapt type-based alias analysis to languages that allow more flexible pointer usage without losing most of its benefits?

[pedropontesgarcia]

I already brought this up in response to a previous comment, but C/C++ generally consider that sort of cast as undefined behavior, so there are no correctness guarantees for it, meaning we can totally perform TBAA (which is cool!). Modula-3 seems to have been chosen since it was a popular-ish language in the academic sphere at the time, despite how foreign it sounds nowadays. To address your questions, I think 1) not much at all, as within the realm of defined behavior it turns out that major typed languages are mostly type-safe (although clearly some languages make it "easier" to walk into undefined land); and 2) I think the answer is probably no, as the moment we consider pointer type casting defined, then we have no guarantees as to what piece of memory, of what size, etc is being accessed.

[natetyoung]

Critique

I agree with most people here that the main contribution of the paper is in the evaluation -- the analysis techniques they presented are interesting, but (by their own evaluation) the more sophisticated techniques do not seem to make much of a difference. I especially like their "limit analysis" showing that most of the gain from RLE has been gotten just with simple techniques.

Questions

My main question is about impact -- does other research now use similar evaluation methods? Do some compilers implement the more sophisticated analyses in this paper despite their small impact on these (small) benchmarks? Is there some case being missed by this paper's benchmarks that is now much more common or impactful?

[CynyuS]

I think the cool thing about this paper is that this simple version of TBAA is now the most widely used analysis, notably within LLVM, and has influenced many different compilers such as Swift. I believe there are more sophisticated alias analyses possible, but this simple analysis is easily scalable and is 'good enough' in that sense. In terms of similar evaluation methods, there are more evaluations on available downstream optimizations, such as LICM, copy propagation, etc! I think some benchmarks this paper might have missed have been addressed in a follow up paper by the same authors, which I think is exciting!

[arw274]

Critique

This paper presented some type-based methods for doing alias analysis. The analysis ideas are fairly straightforward -- what was more interesting to me was their limit analysis for an upper bound on the possible gains. I seldom see this sort of analysis in empirical works, and it's certainly a useful thing to have for gauging just how useful a (simple) technique actually is.

Questions

Given that their simple techniques seem to do quite well, do modern compilers do something much more complicated than this or something fairly simple?

[Smubge]

Modern compilers seem to combine several analyses and utilize them. TBAA enables downstream optimizations ( a signfiicant benefactor), and is still used greatly in the field, with LLVM supporting a TBAA pass and generating TBAA metadata. The version of TBAA discussed in the paper is the most widely used analysis, and influenced many different compilers.

[Mond45]

I find the algorithm interesting in that a seemingly coarse analysis, relying only on type information, can achieve results close to those of a perfect analysis, at least for redundant load elimination (RLE). Its fast time complexity and sufficient analysis quality should make it a practical choice for real compilers. I also agree with others that the paper's strongest contribution lies in its evaluation methodology, especially the upper-bound analysis, which clearly demonstrates how much alias precision could theoretically improve optimization.

However, I believe the paper should also evaluate other downstream optimizations beyond RLE, since different optimizations can vary in their sensitivity to alias precision. I also wonder how well TBAA would perform in less type-safe languages like C++, where arbitrary pointer casting is allowed.

Questions:

• What other downstream optimizations that benefit from alias analysis should be considered here?

• How might TBAA be adapted to remain effective in languages with unsafe pointer casting like C++?

[Smubge]

I agree on your opinion that the paper should evaluate other downstream optimizations beyond RLE. Other downstream optimizations that could benefit from alias analysis that should be considered are loop invariant code motion (LICM), loop unrolling, copy propagation, and global value numbering. Pointed out in the discussion by Prof. Sampson, C and C++ consider casting between pointer types as undefined behavior, meaning that TBAA should be generally valid there too.

[magg1egao]

Critique:
This paper discusses three different type-based alias analyses: Type Decl, FieldTypeDecl, and SMFieldTypeRefs. It argues that compilers can use the programming language type information to figure out when two variables are referring to the same piece of memory (aliasing). What surprised me was how the most simple, type-based method performed almost as well as the much more complex alias analyses. I like how the authors showed how a fast but less precise analysis can still give most of the same optimization benefits. One critique I have is that the paper’s evaluation seems to be limited to one set of Modula-3 benchmarks. While the results are promising, I wish the authors could have done further testing on a wider range of programs or languages.

Question:
As this paper was published in 1998, I wonder how this concept would work today when applied to modern languages where there are dynamic casts, inferred types, unsafe casts, etc? Would type-based alias analyses still be useful, or would today’s code require more advanced and slower analyses?

[Smubge]

One of the things that I have seen on this discussions is an overall agreement of the simplicity yet significant usefulness of TBAA. The concept does work today, with TBAA being one of the most widely used analyses. LLVM has a TBAA pass as well as generates TBAA metadata. In terms of dynamic typing, TBAA cannot help that much in that area. For inferred type languages such as swift (whose compiler actually uses TBAA), they can still greatly benefit from TBAA. In terms of C/C++ unsafe pointer casting, it was pointed out by Prof. Sampson in discussion that C/C++ consider casting between pointer types as undefined behavior, and therefore TBAA should generally be valid there.

[Jacqueline-Wen]

Critique

As mentioned above, the main value of this paper is the evaluation of type-based alias analysis. This paper was quite interesting to read. I found it really interesting that the simplest form of type-based alias analysis was nearly as performant as the most complex one.
However, the scope of this paper is limited to type-safe languages, meaning that more popular languages like C++ are not covered. The authors also focused on redundant load optimization, further limiting the scope of the project.

Question

• What happens when TBAA is run for languages that aren’t type safe?

• How would different optimizations (not RLE) affect the precision of TBAA?

[Smubge]

Actually, C++ is covered by TBAA as stated in the paper. However, in the first place with languages that aren't type safe, other compiler optimizations would also have alot of problems, making TBAA the least of your worries in that scenario. In terms of different optimizations, this is addressed in a follow-up paper.

[SerenaYZhang]

Critique
As already mentioned by many other students, the paper "Type-Based Alias Analysis" does an exceptional job for its evaluation methods. The authors not only perform static evaluation, but also goes beyond the typical methods and includes dynamic evaluation and limited evaluation. I wonder if this paper inspired any other researchers to perform more rigorous testing and evaluation in their own research papers.

Question
This paper demonstrates that type safety allows for compiler optimizations, leading to measurable performance improvements. When programmers are choosing which programming language to use for a new project, how should programmers weight the pros and cons of choosing a more type safe language vs. a language that might be more suitable or easier to use for the project?

What other factors should programmers consider when choosing a programming language for a new project (ex. libraries/tools, concurrency model, etc.)?

[NingWang0123]

Critique:
Type-based aliasing is elegant and cheap, but its soundness leans on strict type discipline; once casts, reflection, or “top” types (void*, byte buffers) appear, precision drops fast. Deep OO polymorphism and container-heavy code further collapse many accesses into coarse alias sets, and TBAA can’t tell different objects of the same type apart (no instance sensitivity). Across module boundaries or with partial type info, compilers must get conservative and blunt optimization gains.

Question:
Can we layer a speculative, deopt-backed instance-sensitive refinement on top of TBAA using cheap allocation-site partitions and runtime guards—to recover precision in polymorphic hot spots without noticeable compile-time or runtime overhead?

[itingtsai]

Critique:
The paper explains three versions of type-based alias analysis and tests how well they help compiler optimizations. Instead of just looking at static precision numbers, the authors measure real performance changes and compare them to a perfect alias analysis. The paper also shows that simple, type-based methods can give almost the same benefits as complex ones for type-safe languages. However, it only focuses on Modula-3 and one optimization (redundant load elimination), so it’s not clear how well the results would apply to other or less type-safe languages.

Questions:
How might type-based alias analysis perform in modern languages with features like dynamic typing, reflection, or unsafe casts? Could the same evaluation framework be applied to study the effectiveness of other compiler optimizations beyond RLE?

[Smubge]

One of the things that I have seen on this discussions is an overall agreement of the simplicity yet significant usefulness of TBAA. The concept does work today, with TBAA being one of the most widely used analyses. LLVM has a TBAA pass as well as generates TBAA metadata. In terms of dynamic typing, TBAA cannot help that much in that area. For inferred type languages such as swift (whose compiler actually uses TBAA), they can still greatly benefit from TBAA. In terms of C/C++ unsafe pointer casting, it was pointed out by Prof. Sampson in discussion that C/C++ consider casting between pointer types as undefined behavior, and therefore TBAA should generally be valid there. Regarding different compiler optimizations beyond RLE, this is addressed in a follow-up paper.

[tf-mac]

Critique:

Section 3.5 details how there is a tradeoff inherent in choosing the fast time bound as opposed to the optimal bound, wherein TBAA only removed between 30 and 90 percent of redundant loads. However, I don't know that the paper justified this tradeoff is worth it, at least without input from the programmer. If the program was run a million times, that ten percent matters significantly.

Questions:

Since this paper was published, has there been analyses that can bridge that missing gap? The authors claim that only a small percentage remain, but could those remaining references lead to large speedups?

[zc579]

Critique
In the current paper, results are primarily self-contained — meaning the proposed approach is evaluated in isolation, without systematic comparison to other state-of-the-art (SOTA) baselines or existing algorithms in the same domain. Thus, it is impossible to determine whether the observed performance gains stem from genuine methodological innovation or simply from different experimental conditions, such as dataset selection, hyperparameter tuning, or preprocessing.
Question
The authors seem to address an existing issue but present it under slightly different terms. This leads to my question: Does the paper truly identify a novel and unsolved problem, or does it merely reframe an existing one?

[Smubge]

In regards to the results of the paper, what is stated is true. The self-contained evaluation ends up being a major methodological limitation. It is my belief that this paper truly identifies a novel and unsolved problem. I understand in the case of re-framing an existing one given the metrics and that the authors did not decide everything from an undecidable context, but this paper has had a significant impact on compiler optimizations as a whole as one of the most widely used analyses.

[az275]

Sorry for the late comment and missing the in-class discussion; I've been sick this week, but I figured better late than never :)

I liked the evaluation section of this paper; I thought the metrics and methodologies used were well justified and reasonably comprehensive, especially for the time. The inclusion of the limit analysis is particularly innovative and interesting, and helps a lot to justify the utility and effectiveness of their alias analyses.

Some questions/comments on the limitations of this work: (1) The authors mention that their analyses are not effective at disambiguating interprocedural aliases. This seems like a hard problem; is there later work that addresses this question? (2) Most of the evaluation focuses on RLE. What about other optimizations? Was RLE chosen to specifically highlight the benefits of type based alias analysis, and would this strategy work well for other optimizations that utilize aliasing? (3) As others have asked: what about behavior on/adaptability to languages that are not type safe?

[Smubge]

There does not seem to be later work by these authors that addresses the question of inter-procedural aliases, and while most of the evaluation does focus on RLE, there is this follow-up paper that talks about the use of other optimizations. In the case of the behavior of languages that are not type safe, there would be problems from other compiler optimizations as well, so in this scenario TBAA would be the least of your worries.

[SolidLao]

Sorry I forgot to reply to this discussion.

This paper is very interesting: a "coarse" analysis, that only using type information, could achieve performance comparable to a perfect analysis. Most of my questions are answered in this discussion chanell and also the class discussion.

My only concern is about the evaluation: different downstrem optimizations have different sensitivities to alias precesion, and evaluating only one optimization (RLE) seems not enough. We would like to see following papers, evaluating this on more downstream optimizations, which could be some interesting evaluation papers.

[NingWang0123]

Critique
It’s a very nice unification of tracing collectors and makes the SATB vs. incremental-update distinction feel principled rather than ad hoc, but it stays fairly abstract: it doesn’t dig into real-world costs of barriers, fragmentation, or specific VM constraints, so the “unified” view is stronger on correctness/structure than on performance realism.

Question
Does the unified framework also account for garbage collectors running on GPUs or highly parallel/multi-CPU systems, where synchronization and memory-access costs are very different?