<div dir="ltr">Hi Chijun,<br><br>I left you my feedback in the doc (+ some nitpicks). Overall, it looks very solid and shows you understand the problem well and know what to expect.<br>Your proposed timeline is reasonable and I don't see any major things to improve there. Don't hesitate to reach out if you have any questions related to my comments (either here or in the document).<br><br>Thanks,<br>Kuba</div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Mar 21, 2018 at 4:23 PM, Chijun Sima <span dir="ltr"><<a href="mailto:simachijun@gmail.com" target="_blank">simachijun@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Kuba,<br>
<br>
Thanks for your clarification on the project in the previous letter.<br>
<br>
I have submitted a proposal draft at the GSoC website, the draft has<br>
been shared with the LLVM organization. I will appreciate it if you<br>
can give me some advice on the proposal. This draft can be viewed by<br>
the organization. (If you do not have access, please mail me, and I<br>
will give you the link.)<br>
<span class="im HOEnZb"><br>
I am looking forward to your reply.<br>
<br>
Regards,<br>
Chijun<br>
<br>
</span><div class="HOEnZb"><div class="h5">2018-03-15 1:42 GMT+08:00 Jakub (Kuba) Kuderski <<a href="mailto:kubakuderski@gmail.com">kubakuderski@gmail.com</a>>:<br>
> Hi Chijun,<br>
><br>
> Great, seems like you did a lot of progress and understand the issues quite<br>
> well!<br>
><br>
>> I have done some early sketch on the API of the new updater class.<br>
>> From my current understanding, to solve the fragmentation problem of<br>
>> the API, the new class first, need to maintain the DomTree and<br>
>> PostDomTree class and deprecate the DefferredDominance class.<br>
><br>
> There are a couple of possibilities here. First, we can come up with a new<br>
> updater class and gradually replace DefferredDominance and and the basic<br>
> incremental update API with it (.applyUpdates()). During this process all<br>
> the classes can coexists which should make it easier to make the transition<br>
> smooth instead of risking breaking multiple places in LLVM at once. The<br>
> other approach would be to modify DefferredDominance and make the transition<br>
> happen in place, which should be also doable. I think that for prototyping<br>
> it would be easier to clone DefferedDominance and replace one use of it at a<br>
> time with the new updater class.<br>
><br>
>>  Second, the API should be something<br>
>> looks like DT.update(updateStrategy::<wbr>lazy,updateKind::delete,A,B) or<br>
>> DT.applyUpdates(<wbr>updateStrategy::lazy,{{ updateKind::delete,A,B }}).<br>
><br>
> Having update strategies as enums sounds very reasonable, but I'd rather we<br>
> didn't teach the DT to do it. I think the existing interface (and the header<br>
> file) is already pretty large and it should make sense to have a separate<br>
> class for the updates that the DT and PDT don't know about at all. I suspect<br>
> that the only thing that might be required would be to expose some<br>
> additional functions from DT and PDT for update pruning, but I'm not sure<br>
> about it at this point.<br>
><br>
>> Third, the API can auto flush() when a query happens, which can make<br>
>> the code easier to maintain. Forth, the updater class can hold an<br>
>> optional PostDomTree and make its status synchronize with the<br>
>> corresponding DomTree (can use lazy updates until query happens) and<br>
>> use information from the DomTree to prune useless updates.<br>
><br>
> Sounds good. One issue we might hit and need to be care about is not to have<br>
> both the updater class and DT in a single function somewhere in the<br>
> codebase. In such cases it is possible to have some pending updates that<br>
> will eventually change DT, but do .dominates() queries on the outdated tree.<br>
> However, this problem exists even today to some extend (with DT and DDT) and<br>
> I don't think it's very serious.<br>
><br>
>> After I read the comments on D41302[1], in which Dave(dmgreen)<br>
>> mentions there is a need to preserve the PostDomTree in the future. I<br>
>> am wondering whether we need to preserve a PostDomTree all the time in<br>
>> the new class?<br>
><br>
> I think that at some point we realized that preserving PDT everywhere is<br>
> quite challenging with the current data structures in LLVM. The issue is<br>
> that for postdominators you have to access predecessors, which requires you<br>
> to track uses instead of just looking up the last instruction within a<br>
> single basic block. What's more, changes anywhere near terminator<br>
> instructions in IR can cause PDT to look completely different every time you<br>
> do it. To do it efficiently, you have to be very lazy about updates and have<br>
> a good strategy for pruning. This project should be a huge step towards it,<br>
> but I think that we have to start with optional PDT anyway.<br>
> Danny and Chandler (cc'd) should remember more about the different<br>
> directions that were considered here.<br>
><br>
>> Moreover, as mentioned in the open projects page[2],<br>
>> the API should be able to specify which trees are actually being<br>
>> updated (none, only DomTree, only PostDomTree, both), while I doubt<br>
>> that if the updater initially holds both the DomTree and PostDomTree<br>
>> for example, it is inappropriate to update only the PostDomTree, which<br>
>> will just break the synchronization between the two trees (DomTree and<br>
>> PostDomTree). Please correct me if I am wrong. :D<br>
><br>
> My intention in the proposal was to say that the updater class can hold (or<br>
> not) two kinds of domtrees -- DT and PDT, and the updates should affect<br>
> whatever is currently available. I hope this is what you are asking about.<br>
> Breaking synchronization between two trees inside the updater class sounds<br>
> like something we really want to avoid.<br>
><br>
> Sincerely,<br>
> Jakub<br>
><br>
> On Mon, Mar 12, 2018 at 4:02 PM, Chijun Sima <<a href="mailto:simachijun@gmail.com">simachijun@gmail.com</a>> wrote:<br>
>><br>
>> Hi Kuba,<br>
>><br>
>> Thanks for your advice in your previous letter.<br>
>><br>
>> During last week, I have read the documents on Doxygen and the source<br>
>> code of the DomTreeBase/DomTree/<wbr>PostDomTree/DeferredDominance class, I<br>
>> believe now I have a much better understanding on the relationship<br>
>> between these classes and how DeferredDominance class performs lazy<br>
>> updates. I have also learnt the current usage and drawbacks of the<br>
>> fragmented API by looking into how several ‘transform util’ functions<br>
>> use these APIs and running the IR tests. Furthermore, I have read the<br>
>> code reviews you mentioned to get the idea of previous approaches on<br>
>> implementing the updater class and so on.<br>
>><br>
>> I have done some early sketch on the API of the new updater class.<br>
>> From my current understanding, to solve the fragmentation problem of<br>
>> the API, the new class first, need to maintain the DomTree and<br>
>> PostDomTree class and deprecate the DeferredDominance class. This<br>
>> approach can save redundant code on calling the update function on<br>
>> both DomTree and PostDomTree. Second, the API should be something<br>
>> looks like DT.update(updateStrategy::<wbr>lazy,updateKind::delete,A,B) or<br>
>> DT.applyUpdates(<wbr>updateStrategy::lazy,{{ updateKind::delete,A,B }}).<br>
>> Third, the API can auto flush() when a query happens, which can make<br>
>> the code easier to maintain. Forth, the updater class can hold an<br>
>> optional PostDomTree and make its status synchronize with the<br>
>> corresponding DomTree (can use lazy updates until query happens) and<br>
>> use information from the DomTree to prune useless updates.<br>
>><br>
>> After I read the comments on D41302[1], in which Dave(dmgreen)<br>
>> mentions there is a need to preserve the PostDomTree in the future. I<br>
>> am wondering whether we need to preserve a PostDomTree all the time in<br>
>> the new class? Moreover, as mentioned in the open projects page[2],<br>
>> the API should be able to specify which trees are actually being<br>
>> updated (none, only DomTree, only PostDomTree, both), while I doubt<br>
>> that if the updater initially holds both the DomTree and PostDomTree<br>
>> for example, it is inappropriate to update only the PostDomTree, which<br>
>> will just break the synchronization between the two trees (DomTree and<br>
>> PostDomTree). Please correct me if I am wrong. :D<br>
>><br>
>> I am preparing to submit the proposal to GSoC this week. At the same<br>
>> time, I will try to figure out something about the way to prune<br>
>> redundant PostDomTree updates.<br>
>><br>
>> I am looking forward to your reply.<br>
>><br>
>><br>
>> Regards,<br>
>><br>
>> Chijun Sima<br>
>><br>
>><br>
>> [1] <a href="https://reviews.llvm.org/D41302?id=127155#inline-361616" rel="noreferrer" target="_blank">https://reviews.llvm.org/<wbr>D41302?id=127155#inline-361616</a><br>
>><br>
>> [2] <a href="https://llvm.org/OpenProjects.html#llvm_domtree_updater" rel="noreferrer" target="_blank">https://llvm.org/OpenProjects.<wbr>html#llvm_domtree_updater</a><br>
>><br>
>> 2018-03-02 11:57 GMT+08:00 Jakub (Kuba) Kuderski <<a href="mailto:kubakuderski@gmail.com">kubakuderski@gmail.com</a>>:<br>
>> > Hi Chijun,<br>
>> ><br>
>> > Thanks for your interest in the project.<br>
>> ><br>
>> >> I have gone through most of the LLVM Kaleidoscope tutorial and I have<br>
>> >> watched the video of the presentation “Dominator Trees and incremental<br>
>> >> updates that transcend time” presented on the 2017 LLVM Developers’<br>
>> >> Meeting. I have also started to understand the algorithm mentioned in<br>
>> >> the comments of the code related to the dominator tree.<br>
>> ><br>
>> ><br>
>> > This sounds like a good start, but I don't think there's strong need to<br>
>> > understand the Depth Based Search algorithm in detail -- grasping the<br>
>> > main<br>
>> > idea behind it should be enough. If you want to have some rough idea on<br>
>> > how<br>
>> > it works you can try to run domtree tests with<br>
>> > -debug-only=dom-tree-builder.<br>
>> > To run just the IR tests for dominators, you can do:<br>
>> > ./unittests/IR/IRTests<br>
>> > --gtest_filter=DominatorTree*. Additionally, you can also play with<br>
>> > Holder.F->viewCFG() and DT->viewGraph() to see what's going on inside<br>
>> > the<br>
>> > tests.<br>
>> ><br>
>> >> I am wondering if there are some other bugs or materials I can go over<br>
>> >> in order to achieve a better understanding on the LLVM’s codebase (or<br>
>> >> the project mentioned above)? Which part of the codebase do you<br>
>> >> recommend to view to learn more about the usage and drawbacks of the<br>
>> >> current dominator tree related API? I would appreciate it.<br>
>> ><br>
>> ><br>
>> > I think that the programmer's manual is extremely useful when you want<br>
>> > to<br>
>> > get more familiar with the code base:<br>
>> > <a href="http://llvm.org/docs/ProgrammersManual.html" rel="noreferrer" target="_blank">http://llvm.org/docs/<wbr>ProgrammersManual.html</a>. I would recommend to focus<br>
>> > on<br>
>> > how to interact with IR, llvm's data structures, and debug utilities.<br>
>> > The most important files related to the projects are probably:<br>
>> > GenericDomTreeConstruction.h, GenericDomTree.h, Dominators.h,<br>
>> > Dominators.cpp.<br>
>> ><br>
>> > If you want to see the incremental API in action, take a look at some<br>
>> > simpler transforms like loop deletion and aggressive dead code<br>
>> > elimination<br>
>> > (ADCE). The problems the project mentions can be seen in various<br>
>> > 'helper'/'utils' functions used by transforms. Take a look at these code<br>
>> > reviews, especially the functions that can accept DT* and/or DDT*:<br>
>> > <a href="https://reviews.llvm.org/D41302" rel="noreferrer" target="_blank">https://reviews.llvm.org/<wbr>D41302</a><br>
>> > <a href="https://reviews.llvm.org/D40146" rel="noreferrer" target="_blank">https://reviews.llvm.org/<wbr>D40146</a><br>
>> > <a href="https://reviews.llvm.org/D42804" rel="noreferrer" target="_blank">https://reviews.llvm.org/<wbr>D42804</a><br>
>> ><br>
>> > I think that it's worth adding that a better API is only one part the<br>
>> > project; the second, perhaps bigger and more fun, is to figure out how<br>
>> > to<br>
>> > prune redundant PostDomTree updates when we have a fully-updated DomTree<br>
>> > available.<br>
>> ><br>
>> > Feel free to ask more questions should you have any -- I and others will<br>
>> > be<br>
>> > more than happy to clarify.<br>
>> ><br>
>> > Best,<br>
>> > Kuba<br>
>> ><br>
>> > On Thu, Mar 1, 2018 at 2:29 PM, Chijun Sima via llvm-dev<br>
>> > <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
>> >><br>
>> >> Hello,<br>
>> >><br>
>> >> I’m an undergraduate student studying CS in the South China University<br>
>> >> of Technology.<br>
>> >><br>
>> >> I have been using clang compiler and related tools since I started<br>
>> >> studying C++ and I would like to work on LLVM in this year’s GSoC. I<br>
>> >> am interested in “Implement a single updater class for Dominators”.<br>
>> >> [1] I have achieved a bronze medal in the 2017 ACM-ICPC Asia Xian<br>
>> >> Regional Contest [2] (being a member of the team “Charizard”) thus I<br>
>> >> think I have some knowledge on basic tree/graph algorithms and data<br>
>> >> structures.<br>
>> >><br>
>> >> I have gone through most of the LLVM Kaleidoscope tutorial and I have<br>
>> >> watched the video of the presentation “Dominator Trees and incremental<br>
>> >> updates that transcend time” presented on the 2017 LLVM Developers’<br>
>> >> Meeting. I have also started to understand the algorithm mentioned in<br>
>> >> the comments of the code related to the dominator tree. I have created<br>
>> >> a Bugzilla account and I am now working on a small bug related to<br>
>> >> syntax warning (Sema).<br>
>> >><br>
>> >> I am wondering if there are some other bugs or materials I can go over<br>
>> >> in order to achieve a better understanding on the LLVM’s codebase (or<br>
>> >> the project mentioned above)? Which part of the codebase do you<br>
>> >> recommend to view to learn more about the usage and drawbacks of the<br>
>> >> current dominator tree related API? I would appreciate it.<br>
>> >><br>
>> >> Best regards,<br>
>> >><br>
>> >> Chijun Sima<br>
>> >><br>
>> >> [1] <a href="https://llvm.org/OpenProjects.html#llvm_domtree_updater" rel="noreferrer" target="_blank">https://llvm.org/OpenProjects.<wbr>html#llvm_domtree_updater</a><br>
>> >> [2] <a href="https://icpc.baylor.edu/regionals/finder/asia-xian-2017/standings" rel="noreferrer" target="_blank">https://icpc.baylor.edu/<wbr>regionals/finder/asia-xian-<wbr>2017/standings</a><br>
>> >> ______________________________<wbr>_________________<br>
>> >> LLVM Developers mailing list<br>
>> >> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>> >> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
>> ><br>
>> ><br>
>> ><br>
>> ><br>
>> > --<br>
>> > Jakub Kuderski<br>
><br>
><br>
><br>
><br>
> --<br>
> Jakub Kuderski<br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div>Jakub Kuderski</div></div>
</div>