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

[Sameer Sahasrabuddhe via llvm-dev]

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.