TargetTransformInfo::hasBranchDivergence() only returns true only if the divergence makes sense for the given target.
So, the compile time should be only affected for such targets: AMDGPU, NVPTX etc.

Committed r342719.

MC/Disassembler/AMDGPU passed
Tests fixed

Source cleanup.

Formatting fixed, function renamed.

comitted: r341068
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@341068 91177308-0d34-0410-b5e6-96231b3b80d8

Unnecessary "isReg()" check removed.
Full context unified diff.

Physical registers handling added. Test cases for physical registers added.

Formatting corrected.

In D50433#1214912, @simoll wrote:

In D50433#1214724, @alex-t wrote:

Sorry, i am struggeling to follow.
Do you take the union of the PDF(P) for each immediate predecessor P of X? (where X is a potential join point).
That gives you invalid results.

      A
    /   \
   B     C
 /  \   /  \
D     E     F
 \  /   \  /
   G     H
   \    /
      I

PDF(G) = {E, B}
PDF(H) = {E, C}

PDF(G) join PDF(H) = {E, B, C} (where join is set union).
Yet, there are two disjoint paths from A to I. But A is in none of these sets.

You approach to the Control Dependence Analysis considering CFG only. You operate in terms ob BBs and branches.
I start from the PHI. The idea is simple: each point where 2 values converge has already been found while building SSA and is annotated with the PHI node.
I consider not PHI parent block predecessors PDF but PHI incoming values parent blocks PDFs.

Let's say the phi node in block I reads %x = phi double [ 0.0, %G ], [ 1.0, %H ]. How do you detect the divergence in %x?

'registers' section dropped in test

Formatting. Test corrected.

In D51316#1214831, @arsenm wrote:

Needs tests and comments.

I think I know what cases you are trying to solve, and there's usually a better way. Do you have a specific example?

Change has been split to several separate.
MIR test added

Sorry, i am struggeling to follow.
Do you take the union of the PDF(P) for each immediate predecessor P of X? (where X is a potential join point).
That gives you invalid results.

      A
    /   \
   B     C
 /  \   /  \
D     E     F
 \  /   \  /
   G     H
   \    /
      I

PDF(G) = {E, B}
PDF(H) = {E, C}

PDF(G) join PDF(H) = {E, B, C} (where join is set union).
Yet, there are two disjoint paths from A to I. But A is in none of these sets.

For given branch all the blocks where PHI nodes must be inserted belongs to the branch parent block dominance frontier.

The problem with DF is that it implicitly assumes that there exists a definition at the function entry (see http://www.cs.utexas.edu/~pingali/CS380C/2010/papers/ssaCytron.pdf, comment below last equation of page 17).
So, we would get imprecise results.

I'm not sure that I understand you correct...
I still do not get an idea what do you mean by "imprecise results". The assumption in the paper you have referred looks reasonable.
Let's say we have 2 disjoint paths from Entry to block X and you have a use of some value V in X.

BTW, even with analyzing forward (up-down) and lazy style, for each divergent terminator you have to compute join points.
This is exactly what is done constructing SSA form to find all the blocks where should be PHI nodes.
For given branch all the blocks where PHI nodes must be inserted belongs to the branch parent block dominance frontier.
Why don't you use at least DF information from PDT?
Facing the divergent branch you can compute the blocks set affected by the divergence in linear time by Cooper's "two fingers" algorithm.

I've not done with the source investigation yet but I already have one general objection.
The analysis algorithm is list-based iterative solver and hence it have to be of linear complexity.

In D50433#1209151, @simoll wrote:

• Rebased on current trunk (git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@340397 91177308-0d34-0410-b5e6-96231b3b80d8).
• Fixed divergent loop example in source code (lib/Analysis/DivergenceAnalysis.cpp : 168)

Currently I cannot apply your diff to the trunk explicitly.
Could you tell me the commit or revision number in llvm trunk on which your patch could be applied?
The rebased diff could help as well.
if I could it'd be much more convenient to review.

In D50433#1202387, @simoll wrote:

Ping. Are there any further remarks, change requests or questions?

How do you deal with terminators that have more than two successors? Example:

switch (divInt) {
  case 0:
   v = 1.0; break;
  case 1:
   v = 20.0; break;
  default:
  // do stuff (block D)
  return;
}
// do other stuff, using 'v' (J)

+----A----+
|    |    |
C0  C1    D
\   |    [..]
 \  |
   J

J is control-dependent on A. Therefore, you will erase A from the PDT sets of C0 and C1. However, there exist two disjoint paths from A to J through C0 and C1, which make PHI nodes in J divergent.

In D50433#1193877, @simoll wrote:

A few comments based on my experience of implemented the DA for AMD GPU legacy compiler :)

should I just disable this analysis completely for r600?

My apologies for the delay. Thanks for handling this. LGTM.

I agree isVGPR should be illegal to call for R600

Thanks for catching this

Could you please clarify - why do you consider that check meaningless for r600?
I see that this line : " const SISubtarget &ST = MF->getSubtarget<SISubtarget>(); " is misleading and in fact is not correct.
I'd better check and choose the R600Subtarget or SISubtarget.
If I understand right we need just check which subtarget to retrieve for physregs check.

Sorry for the delay. Just submitted to trunk.
It was not about the reverse patch only. I had to change tests accordingly.

In D45372#1068728, @dstuttard wrote:

I have no idea how to backport yet.
I 'my going to submit revert patch.
This change existed for a few months and I' my not sure what may be broken
if reverted. I have to figure out this. Some precheckin tests needed.

In fact yes. This is the most correct solution. The stuff in
SIFixSGPRCopies.cpp has got to gone.
So it does not make sense to spend efforts on it. Moreover there is no
correct solution at all
unless we implement one more DivergenceAnalysis upon the machine IR.
So, if it's okay I'd prefer to revert.

In general LGTM.
I also concerned about the magic test that has no checks and has no visible side effects on shared data but is necessary to reproduce buggy behavior.
Could you please clarify what do you need it for?

It seems like this patch should be reverted. Recently we have no reliable
way to determine the PHI (or whatever else) divergence on the MI level.
The only correct way is to add the DA algorithm that re-computes all the MI
divergence.
Since we're going to remove the SGPRFix stuff as soon as diverence driven
ISel is ready I consider this patch is not necessary.

I m looking on this.

Hi Samuel,

ready to land

make check-llvm has passed

Following the discussion. The only register classes that appeared necessary according to the test coverage were added.
This preview can be the starting point for the discussion with respect to the proper approach.

One test fixed

One more question - where should R600 reg classes be processed?
Should we implement getRegClass in R600RegisterInfo?
Or it's okay to handle all them in SIRegisterInfo?

Formatting fixed.
DAG divergence verification for "divergent" targets only.

Verification algorithm of linear complexity

This is the preview of the implementation that provide walk-through divergence bits consistency.
Please note that the verification algorithm has polynomial complexity and is expected to be switched ON/OFF by the option (upcoming soon) with default to OFF.

ping @efriedma

Some bugfixes and changes according to the reviewers requirements.