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

[Alina Sbirlea via llvm-dev]

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>