[Mar 22nd Discussion] Type-Based Alias Analysis

[andrewb1999]

This is a discussion thread for Type-based alias analysis by Amer Diwan, Kathryn S. McKinley, and J. Eliot B. Moss. Discussion leads: Andrey Yao and Andrew Butt

[5hubh4m]

This was one of those papers where after you read the abstract the idea seems extremely simple but it would be very hard to think of it by yourself! It seems so obvious in hindsight that one could leverage types to perform alias analysis.

Also loved when I encountered this sentence "A few researchers recently evaluated alias analyses by measuring the execution-time improvement due to an optimization that uses alias analysis". It's wild to think that that wasn't the first thing someone would think to do when evaluating a technique like this.

[andreyyao]

I felt the same way as well when reading the paper! I think it's helpful to keep in mind that the paper is relatively old, as it was written in 1998. A lot of ideas that we take as granted nowadays need to have been proposed by someone .

I also think that while it is not super complicated to show that type based alias analysis is correct, it's not so obvious whether the specific analyses described in this paper are too conservative that they don't offer any speed up. The empirical benchmarks definitely offered evidence that is hard to get from static analysis alone.

[anshumanmohan]

I felt similarly most of the way through the paper but then noticed that they credit Aho et al (i.e. the Dragon Book) with the idea. Old as this paper is, the textbook is 12 years older haha. But yes indeed, the general point stands!

[anshumanmohan]

Spinning off the second part of @5hubh4m's comment, I think an important (and perhaps undersold) contribution of this paper is towards the rigorous analysis of aliasing in particular and compilers in general. It's interesting that they don't state correctness as a goal; this is probably just implied. In any case, I think this is a good worked example of how an optimization needs to be analyzed from different angles. I enjoy in particular that the number of opportunities for RLA that were generated is discussed. Even if the current pass isn't able to take full advantage of this, maybe future passes will.

[sampsyo]

Indeed, this measurement thing is definitely one of the reasons I love this paper!

[michaelmaitland]

Some thoughts I had reading this paper:

I wonder how much (and to what extent) compilers for untyped languages suffer from optimization because the lack of information. Another +1 for typed languages!

What happens in languages that support arbitrary casting. Sometimes we exploit something we know about the system in a way that lets us use one type as another even if this is wrong. How might the ideas in this paper apply to those type of languages? How effective are these methods under this new conservatism? The paper only said the first algorithm must be more conservative -- do the 2nd and 3rd algos work with the same added conservatism?

[charles-rs]

To build on this, i was wondering if there would be some way to extend an "unsafe" language like C/C++ with some kind of annotation where the programmer could promise that a pointer won't be casted. This might be an unfeasible change, but it seems like there would be some kind of patch to get better performance here. I think a more clear explanation of why the algo has to be more conservative could help build a picture of this

[5hubh4m]

It already exists (kind of)

https://gist.github.com/shafik/848ae25ee209f698763cffee272a58f8

[andreyyao]

I think the second and third analyses function as extensions to the first one, and they share the same assumption about the type safety of the language.

Regarding Charles' comment, I think using the analysis with assignments it might be possible to locate the references that resulted from arbitrary pointer castings and then treat them separately. I also imagine that using a flow sensitive analysis might be more feasible in this case.

[sampsyo]

We can expand on this in class, but it is actually illegal (i.e., undefined behavior) to create aliases with different types in C & C++. So TBAA is used pervasively there.

[alaiasolkobreslin]

One part of this paper that I found interesting was its discussion of limit analysis. After reading this paper, it seems so obvious that it useful to determine how many missed optimization opportunities there were in order to evaluate an alias analysis, but I would have never thought of this idea myself! I wonder if there has been any alias analysis research after 1998 that uses this technique?

[sampsyo]

Right! Having an “upper limit” is a super useful thing if you can get it… it lets you know how far you are between the extremes of “nothing” and “completely solves the problem.”

[JonathanDLTran]

I thought it was interesting how the paper evaluates the effectiveness of Type Based Alias Analysis by showing the number of times the redundant load elimination pass utilizes information from the alias analysis pass to eliminate instructions. It seems like a strong method to characterize exactly the impact of the alias analysis pass. I also wondered if the authors considered other possible passes that use alias analysis as well, such as something like dead store elimination, and tried to understand how much their alias analysis pass benefits dead store elimination.

I was also curious how much better more sophisticated"alias analyses do in comparison to the type based alias analysis, particularly in how these more sophisticated passes do when compared in the upper bound evaluations across the benchmarks in the paper. I assume other alias analysis passes are not going to do much better, because of how well type based alias analysis performs relative to the upper bound.

[JonathanDLTran]

After the discussion I was curious why the analysis was done at a high level AST intermediate representation. What changes and further information would be needed to do this analysis at a lower level, such as in LLVM IR, so that the analysis can be used in other optimizations? In addition, if the analysis worked at a high level AST, would it be possible to encode the notion of scope, and do alias analysis for pointer variables that respect the scoping conventions?

[andreyyao]

I think the notion of access paths is much easier to identify in the AST. Also, since this is a flow-insensitive analysis, there is no need to construct a cfg either.

[orkosinha]

I think the paper was really cool. The simplicity of TBAA is really neat, and this paper probably has the most in-depth performance based evaluation section I've seen so far. Limit evaluations Modern compilers like GCC and LLVM seem to also use TBAA, but I was wondering if potentially doing something with memcpy to overwrite reference values in C might break optimizations. I mean, how can you be sure of type safety being upholded in C/C++ and run something using TBAA?

[gsvic]

The idea of type-based alias analysis looks really neat, and I also find the results of the experimental evaluation insightful. Some thoughts regarding the type-safe languages that are suitable for this kind of analyses. There are languages that could not be explicitly considered as type-safe, but they still are. Such an example is Scala. For example, in Scala a variable assignment can be defined either as val i : Int = 4 or val i = 4. In the latter, the type is not explicitly set, however, one cannot assign a String as they could in a non-type-safe language. My question is, could such an analysis be applied in a language like Scala, and if so, how efficient would it be? Interestingly, I found that Scala actually does some kind of alias analysis, but they say that tracking aliases can be up to x5 times slower. More info can be found in the corresponding source file in Scala's GitHub repo.

[andreyyao]

I had a related thought regarding how this work with OCaml, where in most places types are inferred as opposed to explicitly annotated! A sensible approach might be to keep the inferred type information from type checking and use that instead of the declared types of the memory references

[susan-garry]

Echoing the general sentiment in this thread, this was a fun paper to read! The analysis are so simple and seem rather obvious (especially in hindsight), but it is far less obvious that such a simple analysis could produce substantial results, and the techniques for analysis TBAA presented in this paper seem crucial to understanding the true power of such analysis. It also provides an interesting window into the sort of compilers research being conducted in 1998, as well as how it was being conducted.

One thing that I wonder about is if TBAA would perform similarly on other type-safe languages like Java. Java complicates this type-based alias analysis since an expression like p.f can now alias q[i], making it more difficult to say that two access paths do not alias. However, Java also introduces generics, where even if S1 is a subtype of T, List<S1> is not a subtype of List<T> (at least, you can't cast between them), but objects of these two types may still alias. This presents additional constraints (for example, we now have to consider if ArrayList < LinkedList and if S1 < T) that may help TBAA to distinguish between non-aliasing pairs. Since Java is much more widely used in industry, I would be interested to know of any follow-up research on how well TBAA works on more complex languages.

[andreyyao]

You raise some good points about Java! I didn't know that an instance variable can now alias an array indexing. That seems ugly...
I think the part about generics is not a huge concern. You seem to be talking about how subtyping of List<> is invariant, as opposed to covariant or contravariant. I believe this information is already encoded in the subtyping relationship?

[chhzh123]

I also find this paper very easy to understand. The three proposed analyses TypeDecl, FieldTypeDecl, and SMFieldTypeRefs, are all straightforward and intuitive to design and implement. Types do provide lots of information for compilers to do optimization.

Since the authors evaluate the open and closed world assumptions in Fig.12 and show there are no significant differences between the two assumptions, I wonder what the performance will be if using TBAA for C++. Though C/C++ may have arbitrary type casting with pointers, those casting can still be tracked, and the result of each operation should have a concrete type. In that way, maybe TBAA can still be extended to unsafe languages? Another question is also about the reusability: are there any commercial compilers nowadays using alias analysis or TBAA, and whether the analysis speed is still the problem? Have the limitations stated in the introduction part been solved?

[tonyjie]

The paper is cool! I have a kind of basic question here: can type-based alias analysis be applied together with dataflow-based alias analysis we talked on the class? I think it should be able to do that, but maybe it's not worthy because of the inefficiency?

[ayakayorihiro]

Something that I personally found really interesting in this paper is that the run-time improving of incorporating Type-Based Alias Analysis didn't change much between the original TypeDecl analysis and the more precise FieldTypeDecl and SMFieldTypeRefs. It really shows the importance of simple-sounding ideas and a strong evaluation; in my opinion I'd think that "the more precise, the better", but here it shows that higher precision does not necessarily imply better run-time improvement using optimizations. That being said, there are only 10 benchmark programs, so we also don't know how much this holds for a larger set of benchmarks. It would also be interesting to see how these ideas and findings hold up ~24 years later.

[yy665]

I really like this paper since the idea is simple and neat! I also resonate with @5hubh4m that it's surprising no one had ever used type-based approach on this problem before.

One interesting thing I found that SMFieldTypeRefs does not provide any noticeable improvement over FieldTypeDecl. I think the insight could be that analyzing assignments does not really provide much benefit than people thought. It appears to be an evidence against some traditional assignment-based methods on memory aliasing. On the other hand, I feel like being in different fields is a good prior knowledge that highly suggests disjointness. This is helpful for any aggressive memory aliasing solutions.

I also find the introduction of some terminology and evaluation mechanism in this paper to be very valuable. For example, Access Path (AP), Limit and Dynamic analysis.

[zzzDavid]

I also think it's cool that this paper has rigorous evaluations on both the static and dynamic effects of TBAA and also the upper bound. At first, I was curious how to get the "ground truth" of pointer aliasing and later realized that of course, we can just run the program and instrument every load to record its address and value. I think it's a useful way to get an upper bound of an optimization algorithm by profiling it first.