[DA][NFC] Update publication - add remarks

[simoll]

Summary

Update the reference publication for the SyncDependenceAnalysis and Divergence Analysis. Fix phrasing, formatting. Add comments on reducible loop limitation.

[sameerds]

Not related to the changes proposed in this review, but it seems the PDT is not used by the implementation. It might be good to take out that dependency.

llvm/lib/Analysis/SyncDependenceAnalysis.cpp

103

Good to see both these points spelled out. We are currently working on an implementation that works with irreducible control flow. It's still a work in progress, but involves the new "CycleInfo" being introduced in D112696. I do believe that the single pass of DFA is a strength that need not be lost when handling irreducible control flow. CycleInfo provides a predictable way to work around the lack of a unique header. One just needs to take extra care about entering the same irreducible loop multiple times when constructing ModifiedPO.

149–151

Is it correct to say that this is not critical for correctness? From what I understood, if other blocks (beyond the loop exit) got interleaved, the implementation will work, but unnecessarily visit and skip the interleaved blocks when walking backwards on the ModifiedPO.

[simoll]

Not related to the changes proposed in this review, but it seems the PDT is not used by the implementation. It might be good to take out that dependency.

All good points. PDT and the comment on strict loop compactness are leftovers. I will remove PDT in a followup patch.

llvm/lib/Analysis/SyncDependenceAnalysis.cpp

103

Regarding irreducibility, the unclear part to me always was whether the analysis result (detected joins, synchronization points) in IR still represents the synchronization we will end up getting with the final binary on actual hardware.
So the issue is not really getting some result but making sure the entire stack agrees on synchronization.

D85603 should help here. However, if a kernel is irreducible and doesn't use the tools of the patch, the documentation says that reconvergence should be maximal, as early as possible - this may be ambiguous in irreducible control (IIUC implementation defined with cycles).

This is less of an issue with reducible loops as there is a (mostly unspoken) mutual understanding where synchronization happens and so all transformations will abide to that. This is starting to fade however as more recent hardware breaks with the traditions on synchronization.

149–151

Correct. Exit blocks must have a lower number than the loop header in the traversal (to account for the virtual edge from header to exit). The PO should take care of all other dependences.
Strict loop compactness is a relic from the earlier implementation that recursed on the loop tree during propagation.

It may help with efficiency though.

[sameerds]

In D114146#3142269, @simoll wrote:

All good points. PDT and the comment on strict loop compactness are leftovers. I will remove PDT in a followup patch.

So will you be rephrasing the compactness in this patch? While I am convinced that it does not affect correctness, I have not thought about whether it affects accuracy, i.e., whether the lack of compactness may result in some places being marked divergent when they aren't.

llvm/lib/Analysis/SyncDependenceAnalysis.cpp

103

Indeed, D85603 is a big part of the work being done for the AMDGPU backend. As part of its cleanup, I am hoping to make some conservative statements about the default behaviour when the intrinsics are not being used. The minimal goal is to gracefully handle irreducible control flow, unlike the current DA implementation where we just give up and assume everything is divergent. More as soon as I am in a confident place to make specific statements.

[simoll]

In D114146#3144499, @sameerds wrote:

In D114146#3142269, @simoll wrote:

All good points. PDT and the comment on strict loop compactness are leftovers. I will remove PDT in a followup patch.

So will you be rephrasing the compactness in this patch? While I am convinced that it does not affect correctness, I have not thought about whether it affects accuracy, i.e., whether the lack of compactness may result in some places being marked divergent when they aren't.

I won't touch the comment on loop compactness in this patch. The change does modify how we think about this, which shouldn't happen in the same commit as an updated reference.
Giving up loop compactness (not the order constraints on the loop header/exits though!) shouldn't even change the result of the analysis tbh.

llvm/lib/Analysis/DivergenceAnalysis.cpp

 // they re-converge.
 //
 // Due to this execution model, some optimizations such as jump
 // threading and loop unswitching can interfere with thread re-convergence.
 // Therefore, an analysis that computes which branches in a GPU program are
 // divergent can help the compiler to selectively run these optimizations.
 //
 // This implementation is derived from the Vectorization Analysis of the
-// Region Vectorizer (RV). That implementation in turn is based on the approach
-// described in
+// Region Vectorizer (RV). The analysis is based on the approach described in
 //
-//   Improving Performance of OpenCL on CPUs
-//   Ralf Karrenberg and Sebastian Hack
-//   CC '12
+//   An abstract interpretation for SPMD divergence
+//       on reducible control flow graphs.
+//   Julian Rosemann, Simon Moll and Sebastian Hack
+//   POPL '21
 //
 // This implementation is generic in the sense that it does
 // not itself identify original sources of divergence.
 // Instead specialized adapter classes, (LoopDivergenceAnalysis) for loops and
 // (DivergenceAnalysis) for functions, identify the sources of divergence
 // (e.g., special variables that hold the thread ID or the iteration variable).
 //
 // The generic implementation propagates divergence to variables that are data

llvm/lib/Analysis/SyncDependenceAnalysis.cpp

 // the set of basic blocks whose phi nodes become divergent due to divergent
 // control. These are the blocks that are reachable by two disjoint paths from
 // the branch or loop exits that have a reaching path that is disjoint from a
 // path to the loop latch.
 //
 // The SyncDependenceAnalysis is used in the DivergenceAnalysis to model
 // control-induced divergence in phi nodes.
 //
-// -- Summary --
-// The SyncDependenceAnalysis lazily computes sync dependences [3].
-// The analysis evaluates the disjoint path criterion [2] by a reduction
-// to SSA construction. The SSA construction algorithm is implemented as
-// a simple data-flow analysis [1].
-//
-// [1] "A Simple, Fast Dominance Algorithm", SPI '01, Cooper, Harvey and Kennedy
-// [2] "Efficiently Computing Static Single Assignment Form
-//     and the Control Dependence Graph", TOPLAS '91,
-//           Cytron, Ferrante, Rosen, Wegman and Zadeck
-// [3] "Improving Performance of OpenCL on CPUs", CC '12, Karrenberg and Hack
-// [4] "Divergence Analysis", TOPLAS '13, Sampaio, Souza, Collange and Pereira
+//
+// -- Reference --
+// The algorithm is presented in Section 5 of 
+//
+//   An abstract interpretation for SPMD divergence
+//       on reducible control flow graphs.
+//   Julian Rosemann, Simon Moll and Sebastian Hack
+//   POPL '21
+//
 //
 // -- Sync dependence --
-// Sync dependence [4] characterizes the control flow aspect of the
+// Sync dependence characterizes the control flow aspect of the
 // propagation of branch divergence. For example,
 //
 //   %cond = icmp slt i32 %tid, 10
 //   br i1 %cond, label %then, label %else
 // then:
 //   br label %merge
 // else:
 //   br label %merge
 // merge:
 //   %a = phi i32 [ 0, %then ], [ 1, %else ]
 //
 // Suppose %tid holds the thread ID. Although %a is not data dependent on %tid
 // because %tid is not on its use-def chains, %a is sync dependent on %tid
 // because the branch "br i1 %cond" depends on %tid and affects which value %a
 // is assigned to.
 //
+//
 // -- Reduction to SSA construction --
 // There are two disjoint paths from A to X, if a certain variant of SSA
-// construction places a phi node in X under the following set-up scheme [2].
+// construction places a phi node in X under the following set-up scheme.
 //
 // This variant of SSA construction ignores incoming undef values.
 // That is paths from the entry without a definition do not result in
 // phi nodes.
 //
 //       entry
 //     /      \
 //    A        \
 //  /   \       Y
 // B     C     /
 //  \   /  \  /
 //    D     E
 //     \   /
 //       F
+//
 // Assume that A contains a divergent branch. We are interested
 // in the set of all blocks where each block is reachable from A
 // via two disjoint paths. This would be the set {D, F} in this
 // case.
 // To generally reduce this query to SSA construction we introduce
 // a virtual variable x and assign to x different values in each
 // successor block of A.
+//
 //           entry
 //         /      \
 //        A        \
 //      /   \       Y
 // x = 0   x = 1   /
 //      \  /   \  /
 //        D     E
 //         \   /
 //           F
+//
 // Our flavor of SSA construction for x will construct the following
+//
 //            entry
 //          /      \
 //         A        \
 //       /   \       Y
 // x0 = 0   x1 = 1  /
 //       \   /   \ /
-//      x2=phi    E
+//     x2 = phi   E
 //         \     /
-//          x3=phi
+//         x3 = phi
+//
 // The blocks D and F contain phi nodes and are thus each reachable
 // by two disjoins paths from A.
 //
 // -- Remarks --
-// In case of loop exits we need to check the disjoint path criterion for loops
-// [2]. To this end, we check whether the definition of x differs between the
-// loop exit and the loop header (_after_ SSA construction).
+// * In case of loop exits we need to check the disjoint path criterion for loops.
+//   To this end, we check whether the definition of x differs between the
+//   loop exit and the loop header (_after_ SSA construction).
 //
+// -- Known Limitations & Future Work --
+// * The algorithm requires reducible loops because the implementation
+//   implicitly performs a single iteration of the underlying data flow analysis.
+//   This was done for pragmatism, simplicity and speed.
+//
+//   Relevant related work for extending the algorithm to irreducible control:
+//     A simple algorithm for global data flow analysis problems.
+//     Matthew S. Hecht and Jeffrey D. Ullman.
+//     SIAM Journal on Computing, 4(4):519–532, December 1975.
+//
+// * Another reason for requiring reducible loops is that points of
+//   synchronization in irreducible loops aren't 'obvious' - there is no unique
+//   header where threads 'should' synchronize when entering or coming back
+//   around from the latch.
+//
 //===----------------------------------------------------------------------===//
 #include "llvm/Analysis/SyncDependenceAnalysis.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"

 // pretend it had different successors.
 namespace {
 using namespace llvm;
 
 // Custom Post-Order Traveral
 //
 // We cannot use the vanilla (R)PO computation of LLVM because:
 // * We (virtually) modify the CFG.
-// * We want a loop-compact block enumeration, that is the numbers assigned by
-//   the traveral to the blocks of a loop are an interval.
+// * We want a loop-compact block enumeration, that is the numbers assigned to
+//   blocks of a loop form an interval
+//   
 using POCB = std::function<void(const BasicBlock &)>;
 using VisitedSet = std::set<const BasicBlock *>;
 using BlockStack = std::vector<const BasicBlock *>;
 
 // forward
 static void computeLoopPO(const LoopInfo &LI, Loop &Loop, POCB CallBack,
                           VisitedSet &Finalized);