<div dir="ltr"><div>IMO there are only two options that make sense as far as the cost involved.</div><div>The first, most straight-forward and cheap but a fairly big hammer, is to skip non-trivial unswitching for targets with divergence, as Arthur suggested.</div><div>The second, more expensive, is to compute DA inside SimpleLoopUnswitch inside the `if (TTI.hasBranchDivergence())` clause, before defaulting to `return false`.</div><div><br></div><div>Alina</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Jan 28, 2021 at 12:25 PM Arthur Eubanks via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">There is an option to enable SimpleLoopUnswitch instead of LoopUnswitch in the legacy PM, but I doubt anybody is using that, so I wouldn't worry about it.<br><div><br></div><div>Looking more closely at where divergence analysis is used, it looks like it's only used for non-trivial loop unswitching. In the short term, we could just disable non-trivial unswitching if we detect that the target has divergence. In fact, non-trivial unswitching was only turned on in the new PM recently at -O3.</div><div><br></div><div><font face="monospace">diff --git a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp<br>index 9d3c8d0f3739..e490c18b2568 100644<br>--- a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp<br>+++ b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp<br>@@ -2908,6 +2908,10 @@ static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI,<br>   if (L.getHeader()->getParent()->hasOptSize())<br>     return false;<br><br>+  // Skip non-trivial unswitching for targets with divergence.<br>+  if (TTI.hasBranchDivergence())<br>+    return false;<br>+</font><br></div><div><br></div><div>If we want to add something to LoopStandardAnalysisResults, I believe all loop passes must preserve everything in LoopStandardAnalysisResults, and updating all passes to handle divergence would be a pain. asbirlea should be able to provide more info.</div><div><br></div><div>An alternative is to skip the whole analysis infra and recalculate it on every run of SimpleLoopUnswitch. The LoopUnswitch pass doesn't preserve divergence analysis, so the analysis would be invalidated every time the pass successfully unswitches. If it doesn't unswitch very many loops right now, there could be a large compile time impact.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Jan 28, 2021 at 1:39 AM Sameer Sahasrabuddhe via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi all,<br>
<br>
I have been doing some homework on enabling divergence analysis in the new pass manager. I am focusing only on the new divergence analysis (usually called GPU DA) for now. Adding the appropriate classes was easy enough, but loop unswitching has a problem:<br>
<br>
<a href="https://bugs.llvm.org/show_bug.cgi?id=48819" rel="noreferrer" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=48819</a><br>
<br>
The current situation is as follows:<br>
<br>
1. Legacy DA is available in the old pass manager and is used by LoopUnswitch for correctness.<br>
2. LoopUnswitch is not available in the new pass manager.<br>
3. SimpleLoopUnswitch is available in both pass managers.<br>
4. SimpleLoopUnswitch does not use any DA, and hence it is broken in both pass managers.<br>
<br>
I intend to fix #4 by making the GPU DA available in the new pass manager, and then using whichever DA is available in SimpleLoopUnswitch for the two pass managers respectively.<br>
<br>
The main problem is that the state of any divergence analysis seems under-defined when running a loop pass in either pass manager. For this, I am using the following terms: "invalid" implies that a value previously marked as not divergent has now become divergent due to a transform, while "stale" means that a value previously marked as divergent is now non-divergent due to some transform. The DA being stale does not affect correctness, but being invalid definitely does.<br>
<br>
The LoopUnswitch pass in the legacy pass manager seems to rely on undocumented behaviour to ensure that divergence analysis is made available before loop passes are invoked. But it seems unsafe to assume that the divergence analysis is still valid if any loop transform happens before the LoopUnswitch pass is invoked. Is that something that people just chose to overlook, or am I missing something here? <br>
<br>
In the new pass manager, it seems the equivalent would be to add divergence analysis to LoopStandardAnalysisResults. I tried using getCachedResults on an outer proxy, but that requires that the analysis can "never" be invalidated, which is a more explicit way to force the same question as the previous paragraph.<br>
<br>
If all this is correct, then we could either arrange things so that divergence is updated whenever its dependencies (like dominator tree and loopinfo) are updated, or we need to have a second version of SimpleLoopUnswitch that runs on a function instead of a loop. This version can rely on a simpler statement that loop unswitching does not invalidate divergence and hence the DA need not be updated in the function pass while it is iterating over the loops in that function. The DA may become stale, but that just marks a potential opportunity to rerun the pass on that function.<br>
<br>
Sameer.<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div></div>