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

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

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>

Hi Kuba,

Thanks for your advice in your previous letter.

During last week, I have read the documents on Doxygen and the source
code of the DomTreeBase/DomTree/PostDomTree/DeferredDominance class, I
believe now I have a much better understanding on the relationship
between these classes and how DeferredDominance class performs lazy
updates. I have also learnt the current usage and drawbacks of the
fragmented API by looking into how several ‘transform util’ functions
use these APIs and running the IR tests. Furthermore, I have read the
code reviews you mentioned to get the idea of previous approaches on
implementing the updater class and so on.

I have done some early sketch on the API of the new updater
class.
>From my current understanding, to solve the fragmentation problem of
the API, the new class first, need to maintain the DomTree and
PostDomTree class and deprecate the DeferredDominance class. This
approach can save redundant code on calling the update function on
both DomTree and PostDomTree. Second, the API should be something
looks like DT.update(updateStrategy::lazy,updateKind::delete,A,B) or
DT.applyUpdates(updateStrategy::lazy,{{ updateKind::delete,A,B }}).
Third, the API can auto flush() when a query happens, which can make
the code easier to maintain. Forth, the updater class can hold an
optional PostDomTree and make its status synchronize with the
corresponding DomTree (can use lazy updates until query happens) and
use information from the DomTree to prune useless updates.

After I read the comments on D41302[1], in which Dave(dmgreen)
mentions there is a need to preserve the PostDomTree in the future. I
am wondering whether we need to preserve a PostDomTree all the time in
the new class? Moreover, as mentioned in the open projects page[2],
the API should be able to specify which trees are actually being
updated (none, only DomTree, only PostDomTree, both), while I doubt
that if the updater initially holds both the DomTree and PostDomTree
for example, it is inappropriate to update only the PostDomTree, which
will just break the synchronization between the two trees (DomTree and
PostDomTree). Please correct me if I am wrong. :D

I am preparing to submit the proposal to GSoC this week. At the same
time, I will try to figure out something about the way to prune
redundant PostDomTree updates.

I am looking forward to your reply.


Regards,

Chijun Sima


[1] https://reviews.llvm.org/D41302?id=127155#inline-361616

[2] https://llvm.org/OpenProjects.html#llvm_domtree_updater

2018-03-02 11:57 GMT+08:00 Jakub (Kuba) Kuderski <kubakuderski at
gmail.com>:
> 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