Page MenuHomePhabricator

[DA] DivergenceAnalysis for unstructured, reducible CFGs
ClosedPublic

Authored by simoll on Aug 30 2018, 8:22 AM.

Details

Summary

This is patch 2 of the new DivergenceAnalysis (https://reviews.llvm.org/D50433).

This patch contains a generic divergence analysis implementation for
unstructured, reducible Control-Flow Graphs. It contains two new classes.
The SyncDependenceAnalysis class lazily computes sync dependences, which
relate divergent branches to points of joining divergent control. The
DivergenceAnalysis class contains the generic divergence analysis
implementation.

Diff Detail

Repository
rL LLVM

Event Timeline

simoll created this revision.Aug 30 2018, 8:22 AM
simoll updated this revision to Diff 163350.Aug 30 2018, 9:12 AM

Removed artifacts from patch #3 (LoopDivergencePrinter). This revision is in sync with the reference revision (https://reviews.llvm.org/D50433).

xbolva00 added inline comments.
include/llvm/Analysis/DivergenceAnalysis.h
122 ↗(On Diff #163350)

return DivergentJoinBlocks.find(&Block) != DivergentJoinBlocks.end();

lib/Analysis/DivergenceAnalysis.cpp
128 ↗(On Diff #163350)

llvm_unreachable

simoll marked 2 inline comments as done.Aug 31 2018, 12:55 AM
simoll updated this revision to Diff 163483.Aug 31 2018, 1:54 AM

This patch should already add the tests for the new analysis, shouldn't it?

This patch should already add the tests for the new analysis, shouldn't it?

This patch does not include any pass front end so we can't use lit for testing. I could add unit tests to test the DA directly or merge this patch with the GPUDivergenceAnalysis patch along with the AMDGPU, NVPTX lit tests.

simoll updated this revision to Diff 165929.Sep 18 2018, 4:08 AM
simoll added a subscriber: sameerds.

This diff in sync with Diff 165927 of the reference revision D50433.

Changes

Attached is git diff against git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@342444.

nhaehnle accepted this revision.Oct 10 2018, 2:34 AM

Sorry it took so long, but I finally got to swap this back in. Looks good to me.

lib/Analysis/DivergenceAnalysis.cpp
29 ↗(On Diff #165929)

Not just branches, but also values.

In AMDGPU, we actually use that information to drive instruction selection.

This revision is now accepted and ready to land.Oct 10 2018, 2:34 AM
simoll updated this revision to Diff 168983.Oct 10 2018, 4:37 AM

NFC. Updated comments in DivergenceAnalysis.cpp.

simoll marked an inline comment as done.Oct 10 2018, 4:38 AM

Intel is ok with the patch as well as far as LV/VPlan is concerned (just talked to Matt Masten about this). I don't have commit rights myself. Can you commit this for me?

Sure, I'll take care of it.

This revision was automatically updated to reflect the committed changes.