[DA][SDA] SyncDependenceAnalysis re-write
authorSimon Moll <simon.moll@emea.nec.com>
Wed, 30 Sep 2020 15:10:44 +0000 (17:10 +0200)
committerSimon Moll <simon.moll@emea.nec.com>
Wed, 30 Sep 2020 15:36:26 +0000 (17:36 +0200)
commit05ae04c396519cca9ef50d3b9cafb0cd9c87d1d7
treec81bb269d2d9c96d736ddefb1ed89ac53c0ae0aa
parentd6de40f8865e2c016731f9b63d8a0a218ce1b74f
[DA][SDA] SyncDependenceAnalysis re-write

This patch achieves two things:
1. It breaks up the `join_blocks` interface between the SDA to the DA to
   return two separate sets for divergent loops exits and divergent,
disjoint path joins.
2. It updates the SDA algorithm to run in O(n) time and improves the
   precision on divergent loop exits.

This fixes `https://bugs.llvm.org/show_bug.cgi?id=46372` (by virtue of
the improved `join_blocks` interface) and revealed an imprecise expected
result in the `Analysis/DivergenceAnalysis/AMDGPU/hidden_loopdiverge.ll`
test.

Reviewed By: sameerds

Differential Revision: https://reviews.llvm.org/D84413
llvm/include/llvm/Analysis/DivergenceAnalysis.h
llvm/include/llvm/Analysis/SyncDependenceAnalysis.h
llvm/lib/Analysis/DivergenceAnalysis.cpp
llvm/lib/Analysis/SyncDependenceAnalysis.cpp
llvm/test/Analysis/DivergenceAnalysis/AMDGPU/hidden_loopdiverge.ll
llvm/test/Analysis/DivergenceAnalysis/AMDGPU/trivial-join-at-loop-exit.ll