[Analysis] Qualify auto variables in for loops (NFC)

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Diff

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120659

show more ...

[Analysis] Use default member initialization (NFC)

Identified with modernize-use-default-member-init.

[DivergenceAnalysis] Simplify inRegion test based on whether the RegionLoop pointer is null or not

More closely matches the documentation

Requested by @nikic

[DivergenceAnalysis] Fix static analyzer warning about dereference of nullptr

We're testing that the RegionLoop pointer is null in the first part of the check, so we need to check that its non-null

[DivergenceAnalysis] Fix static analyzer warning about dereference of nullptr

We're testing that the RegionLoop pointer is null in the first part of the check, so we need to check that its non-null before dereferencing it in a later part of the check.

show more ...

[DA][NFC] Update publication - add remarks

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

[DA][NFC] Update publication - add remarks

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

Reviewed By: sameerds

Differential Revision: https://reviews.llvm.org/D114146

show more ...

[Analysis] Use range-based for loops (NFC)

[NewPM] Introduce (GPU)DivergenceAnalysis in the new pass manager

The GPUDivergenceAnalysis is now renamed to just "DivergenceAnalysis"
since there is no conflict with LegacyDivergenceAnalysis. In t

[NewPM] Introduce (GPU)DivergenceAnalysis in the new pass manager

The GPUDivergenceAnalysis is now renamed to just "DivergenceAnalysis"
since there is no conflict with LegacyDivergenceAnalysis. In the
legacy PM, this analysis can only be used through the legacy DA
serving as a wrapper. It is now made available as a pass in the new
PM, and has no relation with the legacy DA.

The new DA currently cannot handle irreducible control flow; its
presence can cause the analysis to run indefinitely. The analysis is
now modified to detect this and report all instructions in the
function as divergent. This is super conservative, but allows the
analysis to be used without hanging the compiler.

Reviewed By: aeubanks

Differential Revision: https://reviews.llvm.org/D96615

show more ...

[llvm] Use pop_back_val (NFC)

[Analysis, CodeGen, IR] Use contains (NFC)

[Analysis] Remove unused system header includes

Cleanup unused system headers and fix an implicit dependency

[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 exi

[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

show more ...

[DA] conservatively mark the join of every divergent branch

For a loop, a join block is a block that is reachable along multiple
disjoint paths from the exiting block of a loop. If the exit conditio

[DA] conservatively mark the join of every divergent branch

For a loop, a join block is a block that is reachable along multiple
disjoint paths from the exiting block of a loop. If the exit condition
of the loop is divergent, then such join blocks must also be marked
divergent. This currently fails in some cases because not all join
blocks are identified correctly.

The workaround is to conservatively mark every join block of any
branch (not necessarily the exiting block of a loop) as divergent.

https://bugs.llvm.org/show_bug.cgi?id=46372

Reviewed By: simoll

Differential Revision: https://reviews.llvm.org/D81806

show more ...

[DA] propagate loop live-out values that get used in a branch

Values that are uniform within a loop but appear divergent to uses
outside the loop are "tainted" so that such uses are marked
divergent

[DA] propagate loop live-out values that get used in a branch

Values that are uniform within a loop but appear divergent to uses
outside the loop are "tainted" so that such uses are marked
divergent. But if such a use is a branch, then it's divergence needs
to be propagated. The simplest way to do that is to put the branch
back in the main worklist so that it is processed appropriately.

Reviewed By: simoll

Differential Revision: https://reviews.llvm.org/D81822

show more ...

[DA] Don't propagate from unreachable blocks

Summary: Fixes crash that could occur when a divergent terminator has an unreachable parent.

Reviewers: rampitec, nhaehnle, arsenm

Subscribers: jvesely

[DA] Don't propagate from unreachable blocks

Summary: Fixes crash that could occur when a divergent terminator has an unreachable parent.

Reviewers: rampitec, nhaehnle, arsenm

Subscribers: jvesely, wdng, hiraditya, jfb, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D73323

show more ...

[DivergenceAnalysis] Add methods for querying divergence at use

Summary:
The existing isDivergent(Value) methods query whether a value is
divergent at its definition. However even if a value is unif

[DivergenceAnalysis] Add methods for querying divergence at use

Summary:
The existing isDivergent(Value) methods query whether a value is
divergent at its definition. However even if a value is uniform at its
definition, a use of it in another basic block can be divergent because
of divergent control flow between the def and the use.

This patch adds new isDivergent(Use) methods to DivergenceAnalysis,
LegacyDivergenceAnalysis and GPUDivergenceAnalysis.

This might allow D63953 or other similar workarounds to be removed.

Reviewers: alex-t, nhaehnle, arsenm, rtaylor, rampitec, simoll, jingyue

Reviewed By: nhaehnle

Subscribers: jfb, jvesely, wdng, hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D65141

llvm-svn: 367218

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[DA] GPUDivergenceAnalysis for unstructured GPU kernels

Summary:
This is patch #3 of the new DivergenceAnalysis

<https://lists.llvm.org/pipermail/llvm-dev/2018-May/123606.html>

The GPUDivergence

[DA] GPUDivergenceAnalysis for unstructured GPU kernels

Summary:
This is patch #3 of the new DivergenceAnalysis

<https://lists.llvm.org/pipermail/llvm-dev/2018-May/123606.html>

The GPUDivergenceAnalysis is intended to eventually supersede the existing
LegacyDivergenceAnalysis. The existing LegacyDivergenceAnalysis produces
incorrect results on unstructured Control-Flow Graphs:

<https://bugs.llvm.org/show_bug.cgi?id=37185>

This patch adds the option -use-gpu-divergence-analysis to the
LegacyDivergenceAnalysis to turn it into a transparent wrapper for the
GPUDivergenceAnalysis.

Reviewers: nhaehnle

Reviewed By: nhaehnle

Subscribers: jholewinski, jvesely, jfb, llvm-commits, alex-t, sameerds, arsenm, nhaehnle

Differential Revision: https://reviews.llvm.org/D53493

llvm-svn: 348048

show more ...

[TI removal] Switch some newly added code over to use `Instruction`
directly.

llvm-svn: 344768

[DA] DivergenceAnalysis for unstructured, reducible CFGs

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

This patch contains a generic divergence analysis

[DA] DivergenceAnalysis for unstructured, reducible CFGs

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.

Reviewers: nhaehnle

Reviewed By: nhaehnle

Subscribers: sameerds, kristina, nhaehnle, xbolva00, tschuett, mgorny, llvm-commits

Differential Revision: https://reviews.llvm.org/D51491

llvm-svn: 344734

show more ...

DivergenceAnalysis: added debug output

Summary:
This commit does two things:

1. modified the existing DivergenceAnalysis::dump() so it dumps the
whole function with added DIVERGENT: annotations;

DivergenceAnalysis: added debug output

Summary:
This commit does two things:

1. modified the existing DivergenceAnalysis::dump() so it dumps the
whole function with added DIVERGENT: annotations;

2. added code to do that dump if the appropriate -debug-only option is
on.

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D47700

Change-Id: Id97b605aab1fc6f5a11a20c58a99bbe8c565bf83
llvm-svn: 336998

show more ...

Remove redundant includes from lib/Analysis.

llvm-svn: 320617

DivergencyAnalysis patch for review

llvm-svn: 305494

DivergenceAnalysis: Fix crash with no return blocks

The post dominator tree does not have a root node in this case.

llvm-svn: 268933

DivergenceAnalysis: Fix crash with unreachable blocks

Unreachable blocks may not be in the dominator tree,
so don't crash on them.

llvm-svn: 268001