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

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.

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>

IMO there are only two options that make sense as far as the cost involved.
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.
The second, more expensive, is to compute DA inside SimpleLoopUnswitch
inside the `if (TTI.hasBranchDivergence())` clause, before defaulting to
`return false`.

Alina

On Thu, Jan 28, 2021 at 12:25 PM Arthur Eubanks via llvm-dev <
llvm-dev at lists.llvm.org> 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.
>
> 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
>>
> _______________________________________________
> 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/20210217/1b0b9269/attachment.html>