<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jul 26, 2016, at 7:00 AM, Hal Finkel via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><br class="Apple-interchange-newline"><hr id="zwchr" class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><b class="">From:<span class="Apple-converted-space"> </span></b>"Chandler Carruth" <<a href="mailto:chandlerc@google.com" class="">chandlerc@google.com</a>><br class=""><b class="">To:<span class="Apple-converted-space"> </span></b>"Hal J. Finkel" <<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>>, "Sean Silva" <<a href="mailto:chisophugis@gmail.com" class="">chisophugis@gmail.com</a>><br class=""><b class="">Cc:<span class="Apple-converted-space"> </span></b>"llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>>, "Davide Italiano" <<a href="mailto:dccitaliano@gmail.com" class="">dccitaliano@gmail.com</a>>, "Xinliang David Li" <<a href="mailto:davidxl@google.com" class="">davidxl@google.com</a>><br class=""><b class="">Sent:<span class="Apple-converted-space"> </span></b>Monday, July 25, 2016 5:48:15 PM<br class=""><b class="">Subject:<span class="Apple-converted-space"> </span></b>Re: [llvm-dev] [PM] I think that the new PM needs to learn about inter-analysis dependencies...<br class=""><br class=""><div dir="ltr" class=""><div class="gmail_quote"><div dir="ltr" class="">On Mon, Jul 25, 2016 at 3:40 PM Finkel, Hal J. via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class=""><div class=""><div class=""></div><div class=""><i class=""><font style="color: rgb(51, 51, 51);" class="">Sent from my Verizon Wireless 4G LTE DROID</font></i></div></div></div><div class=""><div class=""><div class=""><br class=""></div><div class="">On Jul 25, 2016 6:16 PM, Sean Silva <<a href="mailto:chisophugis@gmail.com" target="_blank" class="">chisophugis@gmail.com</a>> wrote:</div><div class="">></div><div class="">></div><div class="">></div><div class="">> On Mon, Jul 25, 2016 at 9:27 AM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>> wrote:</div><div class="">>></div><div class="">>></div><div class="">>> ________________________________</div><div class="">>>></div><div class="">>>> From: "Sean Silva" <<a href="mailto:chisophugis@gmail.com" target="_blank" class="">chisophugis@gmail.com</a>></div><div class="">>>> To: "Chandler Carruth" <<a href="mailto:chandlerc@gmail.com" target="_blank" class="">chandlerc@gmail.com</a>></div><div class="">>>> Cc: "Xinliang David Li" <<a href="mailto:davidxl@google.com" target="_blank" class="">davidxl@google.com</a>>, "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>>, "Davide Italiano" <<a href="mailto:dccitaliano@gmail.com" target="_blank" class="">dccitaliano@gmail.com</a>>, "Tim Amini Golling" <<a href="mailto:mehdi.amini@apple.com" target="_blank" class="">mehdi.amini@apple.com</a>>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank" class="">hfinkel@anl.gov</a>>, "Sanjoy Das" <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank" class="">sanjoy@playingwithpointers.com</a>>, "Pete Cooper" <<a href="mailto:peter_cooper@apple.com" target="_blank" class="">peter_cooper@apple.com</a>></div><div class="">>>> Sent: Friday, July 22, 2016 3:55:52 AM</div><div class="">>>> Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...</div><div class="">>>></div><div class="">>>> The more closely I look at this, the more it seems like there may be a useful incremental step in the transition to the new PM: use the new PM analysis machinery in the old PM. If this is possible, it will simplify the old PM and (hopefully) allow an incremental transition to the new PM instead of a flag day transition for the switch.</div><div class="">>>></div><div class="">>>> I.e., AFAICT, the new PM transition is essentially about 2 mostly orthogonal aspects of running optimization pipelines:</div><div class="">>>> 1. Analysis computation and analysis result lifetime management (including avoiding analysis recomputation)</div><div class="">>>> 2. Running transformation passes over their respective IRUnit's in some order</div><div class="">>>></div><div class="">>>> These are conflated in the old PM. In reality, the only interaction between them (with the new PM machinery for 1.) is a small number of places within 2. which need to call 'invalidate'.</div><div class="">>>></div><div class="">>>> I'm pretty sure that 2. is fairly similar in the new PM and old PM (the main difference is that the notion of "adapters" is split out in the new PM). The analysis handling seems to be what makes the old PM so difficult to understand (e.g. it is the cause of the multiple inheritance in the implementation). Trying to unify analyses and transformations (and some questionable (in hindsight) implementation decisions) seems to be the main "problem" with the design of the old PM AFAICT (there are other issues, but they are more "nice to have").</div><div class="">>>></div><div class="">>>> IMO it is an anti-pattern to think of analyses as "passes". There are just "analyses" and "transformations" and they are two separate things. In fact, the `run` method on analyses should probably be called `computeResult` or something like that to avoid confusion.</div><div class="">>></div><div class="">>> This makes sense to me.</div><div class="">>></div><div class="">>> We do currently have some "in between" passes, like LCSSA, which are transformations, but are required by other passes, and transform the IR but whose preservation represents properties of the IR. The particulars of how we handle LCSSA aside (e.g. I think we should preserve it more, perhaps everywhere), how are we planning on handling this class of things?</div><div class="">></div><div class="">></div><div class="">> The new PM doesn't currently have a concept like this. As you mentioned, it is a weird cross between a transformation and an analysis: it can be "invalidated" like an analysis, but "recomputing" it actually mutates the IR like a transformation.</div><div class="">></div><div class="">> I'd like to preface the below with the following:</div><div class="">> No matter how we ultimately address this requirement, my preference is that we do so in a way that applies to the old PM. This is a case where the old PM supports a richer set of functionality than the new PM. By incrementally refactoring the old PM away from its use of this extra capability and towards whatever "new" way there is to do it, we will understand better what it is that we actually need.</div><div class="">></div><div class="">> (and sorry for the brain dump in the rest of this post)</div><div class="">></div><div class="">></div><div class="">></div><div class="">> I have not seen any mention of a solution to this problem besides "we shouldn't do that", which is sort of a cop-out. Here is a strawman proposal:</div><div class="">></div><div class="">> If it isn't too expensive, one simple alternative is to have passes just make a call to a utility function to put things in LCSSA if they need it (this utility would also have to invalidate analyses).</div><div class="">> If that ends up being expensive, we can have a dummy "indicator" analysis IRIsInLCSSAForm which, if cached, means "don't bother to call the utility function". We could maybe just use the LCSSA pass directly to do the transformation. LCSSA could have IRIsInLCSSAForm as an member typedef `IndicatorT` so it can be accessed generically. We could then support an API like:</div><div class=""><br class=""></div></div></div><div class=""><div class=""><div class="">I think this idea makes sense. My understanding is: There is nothing that prevents an analysis results from exposing a utility that transforms IR, and the result can certainly cache whether or not this transformation has been performed.</div></div></div></blockquote><div class=""><br class=""></div><div class="">Somewhat agreed, but I don't actually think this problem is as bad as it seems in practice.</div><div class=""><br class=""></div><div class="">We only have two places that do this (loop simplify and lcssa) and they both *can* be modeled as "check if it is form X, and if not, put it in form X" or as "check if it is form X, and if not, give up on transform". This has been discussed several times, and the direction things have been leaning for a long time has been:</div><div class=""><br class=""></div><div class="">- Make LCSSA increasingly fundamental to the IR and always present, *or* don't require LCSSA at all for transforms. Either of these solve the problem.</div><div class=""><br class=""></div><div class="">- Check for loop-simplified form if necessary, and skip the transformation if not present. Because simplified form is simple to check this seems to work well.</div><div class=""><br class=""></div><div id="DWT47520" class="">Anyways, I don't think we have to solve this problem 100% to make progress on the pass manager. AT no point have I felt particularly blocked on this.<span class="Apple-converted-space"> </span><br class=""></div></div></div></blockquote>Sure, but we need some solution in order to port our current set of passes to the new pipeline. It sounds like you're proposing that we make the passes that require LCSSA exit early if the IR is not in LCSSA form, and then add the LCSSA pass explicitly into the pipeline, or always do the work to actively put the IR into LCSSA form in each pass that requires it (unless someone is going to do the work now to make LCSSA preserved by all other relevant passes)? What do you feel is the preferred path forward here?<br class=""></div></div></blockquote>Recomputing LCSSA in every time might be very expensive and/or also error-prone. Many loop passes assume that *all* loops are in LCSSA form (I remember fixing a related bug in loop-unroll IIRC). Rebuilding LCSSA for all loops in a loop pass quickly leads to a non-linear behavior, and rebuilding it for only the current loop is sometimes not enough (and might be expensive too).</div><div><br class=""></div><div>FWIW, I've been trying to improve this situation, so I'm willing to continue put my efforts into this area. Actually, I think we're almost at a state where all loop passes preserve it.</div><div><br class=""></div><div>Michael<br class=""><blockquote type="cite" class=""><div class=""><div style="font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; font-family: arial, helvetica, sans-serif; font-size: 10pt;" class=""><blockquote style="border-left-width: 2px; border-left-style: solid; border-left-color: rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica, Arial, sans-serif; font-size: 12pt;" class=""><div dir="ltr" class=""><div class="gmail_quote"><div class=""></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204); padding-left: 1ex;"><div class=""><div class=""><div class=""><br class=""></div><div class=""><br class=""></div><div class="">></div><div class="">> ```</div><div class="">><span class="Apple-converted-space"> </span><a href="http://footransformation.cpp/" target="_blank" class="">FooTransformation.cpp</a>:</div><div class="">></div><div class="">> PreservedAnalyses FooTransformation::run(Function &F, AnalysisManager AM) {</div><div class="">> // Must be called before getting analyses, as it might invalidate some.</div><div class="">> canonicalizeIR<LCSSA>(F, AM);</div><div class="">></div><div class="">> ...</div><div class="">> }</div><div class="">></div><div class="">></div><div class="">> include/IR/Canonicalization.h:</div><div class="">></div><div class="">> template <typename CanonicalizationT, typename IRUnitT></div><div class="">> void canonicalizeIR(IRUnitT &IR, AnalysisManager &AM) {</div><div class="">> using IndicatorT = typename CanonicalizationT::IndicatorAnalysis;</div><div class="">> if (<a href="http://am.getcachedresult/" target="_blank" class="">AM.getCachedResult</a><IndicatorT>(IR))</div><div class="">> return;</div><div class="">> CanonicalizationT C;</div><div class="">> PreservedAnalysis PA =<span class="Apple-converted-space"> </span><a href="http://c.run/" target="_blank" class="">C.run</a>(IR, AM);</div><div class="">> <span class="Apple-converted-space"> </span><a href="http://am.invalidate/" target="_blank" class="">AM.invalidate</a>(IR, PA);</div><div class="">> (void)<a href="http://am.getresult/" target="_blank" class="">AM.getResult</a><IndicatorT>(IR);</div><div class="">> }</div><div class="">></div><div class="">> ```</div><div class="">></div><div class="">></div><div class="">> One place that talks about this problem of "requiring a transformation" is <a href="http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf" target="_blank" class="">http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf</a><span class="Apple-converted-space"> </span>on slide 17.</div><div class="">></div><div class="">> One reason it provides for "we shouldn't do that" is that if you think about these things as "canonicalize the IR into a specific form", then when you have N>1 such dependencies (like some passes do on LoopSimplify and LCSSA), one must have a subset of the requirements of the other. I.e. you can't have two canonicalizations that "fight" each other. Using an explicit mutation API like the strawman above is a bit less bulletproof than scheduling based on statically known interferences between canonicalizations (e.g. CanonicalizationA may invalidate CanonicalizationB, but not the reverse, so it would automatically know to run CanonicalizationA before CanonicalizationB), but given that we have relatively few "canonicalizations" (to give them a name) that use this feature of the old PM, it may be livable (at least in the middle-end, it seems like there is just LCSSA, LoopSimplify, BreakCriticalEdges, and LowerSwitch in calls to addPreservedID/addRequiredID).</div><div class="">></div><div class="">> I don't find the "Causes rampant re-running of invalidated analyses" argument in that slide convincing. If a pass needs the IR in LCSSA then it needs it. There isn't much we can do about that.</div><div class="">></div><div class="">></div><div class="">></div><div class="">></div><div class="">> One invariant I'd like to preserve in the new pass manager is that whatever pipeline is provided on the opt command line, we end up running something "valid"; so a cop-out like "if a pass needs LCSSA, you need to make sure to add LCSSA at an appropriate place before it in the pipeline" is not something I think is reasonable (way too error-prone).</div><div class="">></div><div class="">> Small rant:</div><div class="">></div><div class="">> We already are in this error-prone situation in the new PM with the need to call `getCachedResult` to access analyses from a larger IRUnitT (e.g. the situation I explained in the post-commit thread of r274712);</div><div class=""><br class=""></div></div></div><div class=""><div class=""><div class="">Yea, I don't like this either. I think we both agree that we need a better solution to this. I think we should fix this now and then deal with potential concurrency issues when we actually have a design for that so we know what that means.</div></div></div></blockquote><div class=""><br class=""></div><div class="">FWIW, I strongly disagree.</div><div class=""><br class=""></div><div id="DWT47521" class="">I think it would be better to iterate on this once we understand how the new pass manager works. I think exposing the fact that these things are cached is really important and useful, and it makes querying across IR unit boundaries significantly more clear at the call site.</div></div></div></blockquote>To be clear, the current code looks like this:<br class=""><br class="">LoopAccessInfo LoopAccessAnalysis::run(Loop &L, AnalysisManager<Loop> &AM) {<br class=""> const AnalysisManager<Function> &FAM =<br class=""> AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();<br class=""> Function &F = *L.getHeader()->getParent();<br class=""> auto *SE = FAM.getCachedResult<ScalarEvolutionAnalysis>(F);<br class=""> auto *TLI = FAM.getCachedResult<TargetLibraryAnalysis>(F);<br class=""> auto *AA = FAM.getCachedResult<AAManager>(F);<br class=""> auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);<br class=""> auto *LI = FAM.getCachedResult<LoopAnalysis>(F);<br class=""> if (!SE)<br class=""> report_fatal_error(<br class=""> "ScalarEvolution must have been cached at a higher level");<br class=""> if (!AA)<br class=""> report_fatal_error("AliasAnalysis must have been cached at a higher level");<br class=""> if (!DT)<br class=""> report_fatal_error("DominatorTree must have been cached at a higher level");<br class=""> if (!LI)<br class=""> report_fatal_error("LoopInfo must have been cached at a higher level");<br class=""> auto *DI = UseDA ? FAM.getCachedResult<DependenceAnalysis>(F) : nullptr;<br class=""> return LoopAccessInfo(&L, SE, DI, TLI, AA, DT, LI);<br class="">}<br class=""><br class="">I don't find this an acceptable design. These passes are required, and the pass manager should provide them in a reasonable way. Alternatively, the pass needs to exit early if its dependencies are not met.<br class=""><br class=""> -Hal<br class=""><br class="">--<span class="Apple-converted-space"> </span><br class=""><div class=""><span name="x" class=""></span>Hal Finkel<br class="">Assistant Computational Scientist<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory<span name="x" class=""></span><br class=""></div></div><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">LLVM Developers mailing list</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><a href="mailto:llvm-dev@lists.llvm.org" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">llvm-dev@lists.llvm.org</a><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></div></blockquote></div><br class=""></body></html>