llvm dev - Feb 2021 - loop transforms and function analyses; especially divergence analysis

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.

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.

diff --git a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
index 9d3c8d0f3739..e490c18b2568 100644
--- a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
+++ b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
@@ -2908,6 +2908,10 @@ static bool unswitchLoop(Loop &L, DominatorTree
&DT,
LoopInfo &LI,
   if (L.getHeader()->getParent()->hasOptSize())
     return false;

+  // Skip non-trivial unswitching for targets with divergence.
+  if (TTI.hasBranchDivergence())
+    return false;
+

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.

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.

On Thu, Jan 28, 2021 at 1:39 AM Sameer Sahasrabuddhe via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi all,
>
> 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:
>
> https://bugs.llvm.org/show_bug.cgi?id=48819
>
> The current situation is as follows:
>
> 1. Legacy DA is available in the old pass manager and is used by
> LoopUnswitch for correctness.
> 2. LoopUnswitch is not available in the new pass manager.
> 3. SimpleLoopUnswitch is available in both pass managers.
> 4. SimpleLoopUnswitch does not use any DA, and hence it is broken in both
> pass managers.
>
> 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.
>
> 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.
>
> 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?
>
> 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.
>
> 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.
>
> Sameer.
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210128/d06fdc9c/attachment.html>

---- On Fri, 29 Jan 2021 01:55:44 +0530 Arthur Eubanks <aeubanks at
google.com> wrote ----

 > 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.

Right. But SimpleLoopUnswitch does support the legacy PM, and the check for
divergence is at an internal point independent of the pass manager. So either
way, I have to make sure it plays well with both pass managers. But like you
said, it's not super important, and I can choose to do something simple at
that point.
 
 > 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.

Yeah, that's definitely something we want to consider. But it all depends on
how important are the non-trivial cases in actual programs. We need to keep
track of any potential performance regression from this decision, otherwise it
will get wrongly attributed to the new pass manager. A simple way is to make the
same change in LoopUnswitch with the legacy PM and see how it affects existing
programs.

  > 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.

That is clearly not desirable; divergence analysis is not used frequently enough
to justify the effort.

 > 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.

I assume you mean SimpleLoopUnswitch in your second sentence? Skipping the infra
would undermine the purpose of having that infra in the first place. But even if
we did skip it, divergence analysis will have to be recomputed every time
SimpleLoopUnswitch is invoked, since it's all the other loop passes that
will invalidate it. That would mean at least once per each loop, which sounds
rather costly. That is why I think it would be better to have a second version
that runs on the whole Function once. Then it's up to each specific
compilation flow to decide how to order it relative to the loop passes.

Sameer.

Here's an attempt to add divergence analysis to the new pass manager as the
first step:



https://reviews.llvm.org/D96615



This only introduces the analysis, and does not try to use it with other passes
like SimpleLoopUnswitch. That comes next.



Sameer.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210212/ab78f061/attachment.html>