Dominance relationship is used widely in many compiler analyses and optimizations. The current API provided by LLVM to update the dominator tree and the post dominator tree is fragmented and different functions using these data structures have to decide how to perform incremental updates.
The aim of this project is:
- The API to update the dominator tree and the post dominator tree using different strategies (lazily/eagerly) is fragmented. Therefore, a single class for abstracting away the tree update strategies and which trees are actually being updated need to be developed.
- By implementing a single updater class, performing faster incremental updates will become possible. First, we can convert functions to update the data structure lazily. Second, we can use the updated dominator tree to prune unnecessary updates to the post dominator tree.