[llvm-dev] loop transforms and function analyses; especially divergence analysis

[Arthur Eubanks via llvm-dev]

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>