<html><body><p><font size="2">> </font>One of the problems now is on parsing the pipeline. In the current `PassBuilder`, a function pass is implicitly created and wrapping the subsequent loop passes. If we allow putting `LoopPass` into `LoopNestPass` in the future as described above, what would be a good way to distinguish whether we should choose "function - loopnest - loop" or "function - loop" in this case?<br><br><font size="2">If we allow putting LoopPass into LoopNestPass, then both cases should be supported, and it depends on the use case, similar idea as for "Module - CGCSS - Function" or "Module - Function".</font><br><font face="Menlo-Regular">createModuleToPostOrderCGSCCPassAdaptor</font><font size="2">, </font><font face="Menlo-Regular">createCGSCCToFunctionPassAdaptor</font><font size="2">, </font><font face="Menlo-Regular">createModuleToFunctionPassAdaptor</font><br><br><font face="Menlo-Regular">> </font>As this is my first patch to LLVM, I would also like to ask what would generally be a good time to submit a patch like this. As most of the functionalities are completed but not tested, should I submit the patch as soon as all the existing tests pass and add tests specific to the `LoopNestPass` later so that people can provide feedback on the overall design first, or should I submit the patch after implementing fine-grained tests?<br><br>I prefer submit the patch as soon as all the existing tests pass and add tests specific to the `LoopNestPass` later so that people can provide feedback on the overall design first. You can specify in the description your intention and that tests are planning to be added.<br><br>Regards,<br>Whitney Tsang<br><br><img width="16" height="16" src="cid:1__=8FBB0F21DFC120A48f9e8a93df938690918c8FB@" border="0" alt="Inactive hide details for Ta-Wei Tu ---2020/07/24 06:08:37 AM---Hi, I misunderstood what `addSiblingLoops()` does - the analogy"><font size="2" color="#424282">Ta-Wei Tu ---2020/07/24 06:08:37 AM---Hi, I misunderstood what `addSiblingLoops()` does - the analogy should be</font><br><br><font size="2" color="#5F5F5F">From: </font><font size="2">Ta-Wei Tu <tu.da.wei@gmail.com></font><br><font size="2" color="#5F5F5F">To: </font><font size="2">Ettore Tiotto <etiotto@ca.ibm.com></font><br><font size="2" color="#5F5F5F">Cc: </font><font size="2">Whitney T Tsang <whitneyt@ca.ibm.com>, llvm-dev <llvm-dev@lists.llvm.org>, Whitney Tsang <whitney.uwaterloo@gmail.com></font><br><font size="2" color="#5F5F5F">Date: </font><font size="2">2020/07/24 06:08 AM</font><br><font size="2" color="#5F5F5F">Subject: </font><font size="2">[EXTERNAL] Re: [llvm-dev] Regarding the project "Create LoopNestPass"</font><br><hr width="100%" size="2" align="left" noshade style="color:#8091A5; "><br><br><br>Hi,<br><br>I misunderstood what `addSiblingLoops()` does - the analogy should be something like "addNewLoopNests()" which deals with the insertion of new loop nests into the function. I will add this functionality into `LNPMUpdater`.<br>Also, I just realized that some regression tests rely on the type names of the passes, so `FunctionToLoopNestPassAdaptor` should be implemented separately or the tests will have to be modified.<br>Sorry for the confusion.<br><br>Sincerely,<br>Ta-Wei, Tu<br><br>Ta-Wei Tu <<a href="mailto:tu.da.wei@gmail.com"><u><font color="#0000FF">tu.da.wei@gmail.com</font></u></a>> 於 2020年7月24日 週五 下午1:27寫道：
<ul>Hi,<br><br>I would like to give a quick update on what my current design and implementation go like.<br><br>Basically, the `FunctionToLoopPassAdaptor` is now modified to a generic version `FunctionToLoopUnitPassAdaptor`, which allows re-using the existing codes to implement `FunctionToLoopNestPassAdaptor`, with the help of additional metadata associated with `Loop` and `LoopNest`. Both `FunctionToLoopPassAdaptor` and `FunctionToLoopNestPassAdaptor` are aliases to `FunctionToLoopUnitPassAdaptor` and they operates on `Loop`, and the `FunctionToLoopNestPassAdaptor` will construct the `LoopNest` object lazily for the given `LoopNestPass` to run on.<br><br>The `LNPMUpdater` only support `revisitCurrentLoopNest()` and `markLoopNestAsDeleted()` since other functionalities like `addChildLoops()` and `addSiblingLoops()` that `LPMUpdater` provide don't seem to be meaningful since we're dealing with outer-most `LoopNest`s. Still, an analogy of `addSiblingLoops()` can be implemented as something like `addAllLoopNests()`. What's your opinion on that?<br><br>Currently, `LoopNestToLoopPassAdaptor` is also implemented to allow injecting a `LoopPassManager` into a `LoopNestPassManager`. The reason why I think this is useful is that both `LoopPass` and `LoopNestPass` requires loop canonicalization passes to be run first, and composing both of them and promoting them into a single `FunctionPass` can reduce unnecessary runs of the canonicalization phases. With these, the pipeline can be built like:<br><br>```<br>FunctionPassManager FPM;<br>LoopNestPassManager LNPM;<br>LoopPassManager LPM;<br>LNPM.addPass(SomeLoopNestPass());<br>LPM.addPass(SomeLoopPass());<br>LNPM.addPass(createLoopNestToLoopPassAdaptor(LPM));<br>FPM.addPass(createFunctionToLoopNestPassAdaptor(LNPM));<br><br>// This still works, but the loop canonicalization passes will be run twice:<br>// FPM.addPass(createFunctionToLoopPassAdaptor(LPM));<br>// FPM.addPass(createFunctionToLoopNestPassAdaptor(LNPM));<br>```<br><br>`LoopNestAnalysisManager` and the proxies between `LoopAnalysis`, `LoopNestAnalysis` and `FunctionAnalysis` are also implemented.<br>One of the problems now is on parsing the pipeline. In the current `PassBuilder`, a function pass is implicitly created and wrapping the subsequent loop passes. If we allow putting `LoopPass` into `LoopNestPass` in the future as described above, what would be a good way to distinguish whether we should choose "function - loopnest - loop" or "function - loop" in this case?<br><br>As this is my first patch to LLVM, I would also like to ask what would generally be a good time to submit a patch like this. As most of the functionalities are completed but not tested, should I submit the patch as soon as all the existing tests pass and add tests specific to the `LoopNestPass` later so that people can provide feedback on the overall design first, or should I submit the patch after implementing fine-grained tests?<br><br>What are your thoughts on the design? Thank you very much!<br><br>Sincerely,<br>Ta-Wei Tu<br><br>Ettore Tiotto <<a href="mailto:etiotto@ca.ibm.com" target="_blank"><u><font color="#0000FF">etiotto@ca.ibm.com</font></u></a>> 於 2020年7月21日 週二 下午8:43寫道：<br><font face="Arial">> One question I have is whether the IRUnit LoopNestPass operates on should be Loop or LoopNest, since I'm not quite sure about the usage of LoopNest and why it should be constructed with a ScalarEvolution.</font><font face="Arial"><br></font><font face="Arial"><br>That's a good point, we can make ScalarEvolution optional for LoopNest. Currently, the only use case is to check if the loop nest is perfect, which can provide a more conservative result if ScalarEvolution is not given. <br>Having said that, ScalarEvolution is one of the analyses in LoopStandardAnalysisResults, so all LoopPasses already have access to ScalarEvolution.<br>LoopNest provides some useful utilities, although it is still not at a manual phrase. <br>My personal opinion is all the mechanism of the LoopNest, e.g. LoopNestPassManager, LPMUpdater, etc, should operates on Loop. While IRUnitT which is used by loop nest transformations/analyses should operates on LoopNest.<br>@etiotto What's your opinion on that?</font><br><font face="Arial"> </font><br><font face="Arial">Determining whether a loop nest is perfect is a fundamental feature for LoopNest analysis, and ScalarEvolution is required to catch not-trivial cases. I agree that SE should be always available to a LoopNest pass. The LoopNest analysis should be available to a LoopNest pass manager, and a LoopNest pass IMO should operate on a LoopNest IR unit rather than a Loop. </font><br><font size="2" face="Arial"> </font><br><font face="Arial">Ettore Tiotto<br>IBM Canada Laboratory, 8200 Warden Ave, Markham, ON L6G 1C7, Canada</font><u><font color="#0000FF" face="Arial"><br></font></u><a href="mailto:etiotto@ca.ibm.com" target="_blank"><u><font color="#0000FF" face="Arial">etiotto@ca.ibm.com</font></u></a><font face="Arial"> -- Phone: (905) 413-2387<br><br>“No great discovery was ever made without a bold guess.” - Isaac Newton</font><br><font size="2" face="Arial"> </font><br><font size="2" face="Arial"> </font><br><font size="2" face="Arial">----- Original message -----<br>From: Whitney T Tsang/Toronto/IBM<br>To: Ta-Wei Tu <</font><a href="mailto:tu.da.wei@gmail.com" target="_blank"><u><font size="2" color="#0000FF" face="Arial">tu.da.wei@gmail.com</font></u></a><font size="2" face="Arial">><br>Cc: llvm-dev <</font><a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><u><font size="2" color="#0000FF" face="Arial">llvm-dev@lists.llvm.org</font></u></a><font size="2" face="Arial">>, Whitney Tsang <</font><a href="mailto:whitney.uwaterloo@gmail.com" target="_blank"><u><font size="2" color="#0000FF" face="Arial">whitney.uwaterloo@gmail.com</font></u></a><font size="2" face="Arial">>, Ettore Tiotto/Toronto/IBM@IBMCA<br>Subject: Re: [EXTERNAL] Re: [llvm-dev] Regarding the project "Create LoopNestPass"<br>Date: Sat, Jul 18, 2020 3:32 PM<br> </font><font face="Arial"><br>Hi Ta-Wei,</font><font size="2" face="Arial"><br></font><font face="Arial"><br>> We might also need a LNPMUpdater (LoopNestPassManagerUpdater) which disallows adding inner-loops back into the pipeline, and LoopNestPassManager will simply be PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResult &, LNPMUpdater &>.</font><font size="2" face="Arial"><br></font><font face="Arial"><br>LNPMUpdater should have some functionalities of LPMUpdater, e.g. adding sibling loop nest, revisit the current loop nest, etc. </font><font size="2" face="Arial"><br></font><font face="Arial"><br>> One question I have is whether the IRUnit LoopNestPass operates on should be Loop or LoopNest, since I'm not quite sure about the usage of LoopNest and why it should be constructed with a ScalarEvolution.</font><font size="2" face="Arial"><br></font><font face="Arial"><br>That's a good point, we can make ScalarEvolution optional for LoopNest. Currently, the only use case is to check if the loop nest is perfect, which can provide a more conservative result if ScalarEvolution is not given. <br>Having said that, ScalarEvolution is one of the analyses in LoopStandardAnalysisResults, so all LoopPasses already have access to ScalarEvolution.<br>LoopNest provides some useful utilities, although it is still not at a manual phrase. <br>My personal opinion is all the mechanism of the LoopNest, e.g. LoopNestPassManager, LPMUpdater, etc, should operates on Loop. While IRUnitT which is used by loop nest transformations/analyses should operates on LoopNest.<br>@etiotto What's your opinion on that?</font><font size="2" face="Arial"><br></font><font face="Arial"><br>> Also, it is stated that "we want to create a LoopNestPass, where transformations intended for loop nest can inherit from it" in the original GSoC project description, but I believe that inheriting from a Pass subclass is no longer required in the New Pass Manager. So should we also implement a LoopNestPass subclass that allows implementing loop-nest-passes for the Legacy Pass Manager?</font><font size="2" face="Arial"><br></font><font face="Arial"><br>Right, the wording should be corrected. Given that the New Pass Manager will soon be the default Pass Manager, we should not spend extra effort to create LoopNestPass in Legacy Pass Manager.</font><font size="2" face="Arial"><br></font><font face="Arial"><br>> Finally, I have some questions that might not be very relevant to the project. But currently, how does the LegacyPassManager and the NewPassManager interact? Also, is it possible to add passes designed for LegacyPassManager into the NewPassManager and vice versa? </font><font size="2" face="Arial"><br></font><font face="Arial"><br>Most transformations have both for LegacyPassManager and NewPassManager, and have the actual implementation of the transformations in a separate class, or a static function that can be call by both.<br>e.g. LoopFuseLegacy is for LegacyPassManager , </font><a href="https://llvm.org/doxygen/classllvm_1_1LoopFusePass.html#a971f40ada3f1410759faede02bfbace7" target="_blank"><u><font color="#4665A2" face="Arial">LoopFusePass</font></u></a><font face="Arial"> is for NewPassManager, and both create LoopFuser and do the transformation there.</font><font size="2" face="Arial"><br></font><font face="Arial"><br>Looking forward to your first patch!</font><font size="2" face="Arial"><br></font><font face="Arial"><br>Regards,<br>Whitney Tsang</font><font size="2" face="Arial"><br><br><br></font><font size="2" color="#424282" face="Arial">Ta-Wei Tu ---2020/07/18 07:38:44 AM---Hi, Thanks for your help! I've checked the sources that you mentioned.</font><font size="2" face="Arial"><br></font><font size="2" color="#5F5F5F" face="Arial"><br>From: </font><font size="2" face="Arial">Ta-Wei Tu <</font><a href="mailto:tu.da.wei@gmail.com" target="_blank"><u><font size="2" color="#0000FF" face="Arial">tu.da.wei@gmail.com</font></u></a><font size="2" face="Arial">></font><font size="2" color="#5F5F5F" face="Arial"><br>To: </font><font size="2" face="Arial">Whitney Tsang <</font><a href="mailto:whitney.uwaterloo@gmail.com" target="_blank"><u><font size="2" color="#0000FF" face="Arial">whitney.uwaterloo@gmail.com</font></u></a><font size="2" face="Arial">></font><font size="2" color="#5F5F5F" face="Arial"><br>Cc: </font><font size="2" face="Arial">llvm-dev <</font><a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><u><font size="2" color="#0000FF" face="Arial">llvm-dev@lists.llvm.org</font></u></a><font size="2" face="Arial">>, </font><a href="mailto:whitneyt@ca.ibm.com" target="_blank"><u><font size="2" color="#0000FF" face="Arial">whitneyt@ca.ibm.com</font></u></a><font size="2" color="#5F5F5F" face="Arial"><br>Date: </font><font size="2" face="Arial">2020/07/18 07:38 AM</font><font size="2" color="#5F5F5F" face="Arial"><br>Subject: </font><font size="2" face="Arial">[EXTERNAL] Re: [llvm-dev] Regarding the project "Create LoopNestPass" </font><hr width="100%" size="2" align="left"><font size="2" face="Arial"><br><br></font><font face="Arial"><br>Hi,</font><font size="2" face="Arial"><br></font><font face="Arial"><br>Thanks for your help! I've checked the sources that you mentioned. Currently, I think that I would need to implement a FunctionToLoopNestPassAdaptor which is essentially the same as the FunctionToLoopPassAdaptor but operates only on LI.getTopLevelLoops(). </font><font size="2" face="Arial"><br></font><font face="Arial"><br>We might also need a LNPMUpdater (LoopNestPassManagerUpdater) which disallows adding inner-loops back into the pipeline, and LoopNestPassManager will simply be PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResult &, LNPMUpdater &>.</font><font size="2" face="Arial"><br></font><font face="Arial"><br>One question I have is whether the IRUnit LoopNestPass operates on should be Loop or LoopNest, since I'm not quite sure about the usage of LoopNest and why it should be constructed with a ScalarEvolution.</font><font size="2" face="Arial"><br></font><font face="Arial"><br>Also, it is stated that "we want to create a LoopNestPass, where transformations intended for loop nest can inherit from it" in the original GSoC project description, but I believe that inheriting from a Pass subclass is no longer required in the New Pass Manager. So should we also implement a LoopNestPass subclass that allows implementing loop-nest-passes for the Legacy Pass Manager?</font><font size="2" face="Arial"><br></font><font face="Arial"><br>Finally, I have some questions that might not be very relevant to the project. But currently, how does the LegacyPassManager and the NewPassManager interact? Also, is it possible to add passes designed for LegacyPassManager into the NewPassManager and vice versa? </font><font size="2" face="Arial"><br></font><font face="Arial"><br>What do you think about the plan? I'm quite likely to miss something important, so please kindly correct me if I'm in the wrong direction.</font><font size="2" face="Arial"><br></font><font face="Arial"><br>Thank you very much!<br>Sincerely, Ta-Wei Tu</font><font size="2" face="Arial"><br></font><font face="Arial"><br>Whitney Tsang <</font><a href="mailto:whitney.uwaterloo@gmail.com" target="_blank"><u><font color="#0000FF" face="Arial">whitney.uwaterloo@gmail.com</font></u></a><font face="Arial">> 於 2020年7月15日 週三 下午6:14寫道：</font><font size="2" face="Arial"> </font><br><font color="#121212" face="Helvetica Neue">Hi Wayne,</font><font size="2" face="Arial"><br></font><font color="#121212" face="Helvetica Neue"><br>As far as I know, no one is working on this project. Your contribution is always appreciated.</font><font size="2" face="Arial"><br></font><font color="#121212" face="Helvetica Neue"><br>This project aims to create LoopNestPass in the new pass manager (NPM).<br>In </font><a href="https://www.youtube.com/watch?v=3pRhvQi7Z10" target="_blank"><u><font color="#4178BE" face="Helvetica Neue">https://www.youtube.com/watch?v=3pRhvQi7Z10</font></u></a><font color="#121212" face="Helvetica Neue"> , you can try to follow along to create a LLVM loop pass in NPM.</font><font size="2" face="Arial"><br></font><font color="#121212" face="Helvetica Neue"><br>There exist different kinds of passes in the NPM, e.g. ModulePass, FunctionPass, LoopPass. <br>One or more loop passes can be added in a LoopPassManager, which then can be added in FunctionPassManager through createFunctionToLoopPassAdaptor. <br>Examples can be found in llvm/lib/Passes/PassBuilder.cpp. <br>There exist passes that best operate as a loop nest, e.g. LoopInterchange. For those passes, currently can be written as either FunctionPass or LoopPass.<br>However, choosing one or the other needs to sacrifice the ability of the other. <br>The idea of a LoopNestPass is to combine the benefits of FunctionPass and LoopPass needed for a loop nest.</font><font size="2" face="Arial"><br></font><font color="#121212" face="Helvetica Neue"><br>On top of LoopNest I would suggest to also get familiar with different PassAdaptor classes (e.g. FunctionToLoopPassAdaptor).<br>- llvm/include/llvm/Transforms/Scalar/LoopPassManager.h</font><font size="2" face="Arial"><br></font><font color="#121212" face="Helvetica Neue"><br>I am happy to provide feedback once you have a plan of how to proceed, or review your patches on Phabricator.</font><font size="2" face="Arial"><br></font><font color="#121212" face="Helvetica Neue"><br>Regards,<br>Whitney Tsang</font><font size="2" face="Arial"><br></font><font face="Arial"><br>On Wed, Jul 15, 2020 at 5:49 AM Wayne Tu via llvm-dev <</font><a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><u><font color="#0000FF" face="Arial">llvm-dev@lists.llvm.org</font></u></a><font face="Arial">> wrote:</font><font size="2" face="Arial"> </font><br><font face="Arial">Hi,</font><font size="2" face="Arial"><br></font><font face="Arial"><br>I'm a college student who is quite new to the community and is interested in contributing to the LLVM project. Although I haven't applied to GSoC, I notice that the project "Create LoopNestPass" seems to be unassigned. <br>So I'm curious whether anyone is currently working on it, and if not, is it possible for me to work on it as a side-project?</font><font size="2" face="Arial"><br></font><font face="Arial"><br>I've been programming in C++ for quite a while, and I've walked through the `LoopPass`, `LoopNest`, and some other LLVM classes that I think would probably be related to this project. I've also watched some of the videos in the llvm-dev conference regarding loops, so I now have a rough idea on how to implement the LoopNestPass.</font><font size="2" face="Arial"><br></font><font face="Arial"><br>I'm looking forward to working on this project. </font><font size="2" face="Arial"><br></font><font face="Arial"><br>Thank you very much.</font><font size="2" face="Arial"><br></font><font face="Arial"><br>Sincerely,<br>Ta-Wei Tu<br>_______________________________________________<br>LLVM Developers mailing list</font><u><font size="2" color="#0000FF" face="Arial"><br></font></u><a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><u><font color="#0000FF" face="Arial">llvm-dev@lists.llvm.org</font></u></a><u><font size="2" color="#0000FF" face="Arial"><br></font></u><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank"><u><font color="#0000FF" face="Arial">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</font></u></a><br><font size="2" face="Arial"> </font><br><br><br></ul><BR>
</body></html>