[llvm-dev] [GSOC 2018] Implement a single updater class for Dominators

[Jakub (Kuba) Kuderski via llvm-dev]

Hi Chijun,

Thanks for your interest in the project.

I have gone through most of the LLVM Kaleidoscope tutorial and I have
> watched the video of the presentation “Dominator Trees and incremental
> updates that transcend time” presented on the 2017 LLVM Developers’
> Meeting. I have also started to understand the algorithm mentioned in
> the comments of the code related to the dominator tree.


This sounds like a good start, but I don't think there's strong need to
understand the Depth Based Search algorithm in detail -- grasping the main
idea behind it should be enough. If you want to have some rough idea on how
it works you can try to run domtree tests with -debug-only=dom-tree-builder.
To run just the IR tests for dominators, you can do: ./unittests/IR/IRTests
--gtest_filter=DominatorTree*. Additionally, you can also play with
Holder.F->viewCFG() and DT->viewGraph() to see what's going on inside the
tests.

I am wondering if there are some other bugs or materials I can go over
> in order to achieve a better understanding on the LLVM’s codebase (or
> the project mentioned above)? Which part of the codebase do you
> recommend to view to learn more about the usage and drawbacks of the
> current dominator tree related API? I would appreciate it.


I think that the programmer's manual is extremely useful when you want to
get more familiar with the code base:
http://llvm.org/docs/ProgrammersManual.html. I would recommend to focus on
how to interact with IR, llvm's data structures, and debug utilities.
The most important files related to the projects are probably:
GenericDomTreeConstruction.h, GenericDomTree.h, Dominators.h,
Dominators.cpp.

If you want to see the incremental API in action, take a look at some
simpler transforms like loop deletion and aggressive dead code elimination
(ADCE). The problems the project mentions can be seen in various
'helper'/'utils' functions used by transforms. Take a look at these code
reviews, especially the functions that can accept DT* and/or DDT*:
https://reviews.llvm.org/D41302
https://reviews.llvm.org/D40146
https://reviews.llvm.org/D42804

I think that it's worth adding that a better API is only one part the
project; the second, perhaps bigger and more fun, is to figure out how to
prune redundant PostDomTree updates when we have a fully-updated DomTree
available.

Feel free to ask more questions should you have any -- I and others will be
more than happy to clarify.

Best,
Kuba

On Thu, Mar 1, 2018 at 2:29 PM, Chijun Sima via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Hello,
>
> I’m an undergraduate student studying CS in the South China University
> of Technology.
>
> I have been using clang compiler and related tools since I started
> studying C++ and I would like to work on LLVM in this year’s GSoC. I
> am interested in “Implement a single updater class for Dominators”.
> [1] I have achieved a bronze medal in the 2017 ACM-ICPC Asia Xian
> Regional Contest [2] (being a member of the team “Charizard”) thus I
> think I have some knowledge on basic tree/graph algorithms and data
> structures.
>
> I have gone through most of the LLVM Kaleidoscope tutorial and I have
> watched the video of the presentation “Dominator Trees and incremental
> updates that transcend time” presented on the 2017 LLVM Developers’
> Meeting. I have also started to understand the algorithm mentioned in
> the comments of the code related to the dominator tree. I have created
> a Bugzilla account and I am now working on a small bug related to
> syntax warning (Sema).
>
> I am wondering if there are some other bugs or materials I can go over
> in order to achieve a better understanding on the LLVM’s codebase (or
> the project mentioned above)? Which part of the codebase do you
> recommend to view to learn more about the usage and drawbacks of the
> current dominator tree related API? I would appreciate it.
>
> Best regards,
>
> Chijun Sima
>
> [1] https://llvm.org/OpenProjects.html#llvm_domtree_updater
> [2] https://icpc.baylor.edu/regionals/finder/asia-xian-2017/standings
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>



-- 
Jakub Kuderski
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180301/82e25328/attachment.html>