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.

In fact v_readfirstlane is inserted by the ISel to glue vector input to the unexpected scalar instruction.
This means that compiler user writing valid IR will get unexpected behavior.
Is this documented somewhere?

Preliminary revision illustrating possible approach to keeping divergence information consistent along the DAG transformation

In D35267#1002305, @efriedma wrote:

If we're going to include the "divergent" bit in SDNodes, so we can query it all the time, the bit needs to be correct all the time. The goal of a verifier is to ensure that at any given point, the bits stored in the SelectionDAG are the same as the bits we would compute from scratch. So code still needs to do the right thing to update the divergence bits, if necessary, but the verifier lets us catch mistakes early. This is similar to the way we have a domtree verifier, to ensure transforms correctly update the domtree.

In D35267#998083, @efriedma wrote:

I'd like to see a verifier somewhere that the divergence bit is still correct after DAGCombine (it could be different from what SelectionDAG::createOperands would compute given how ReplaceAllUsesWith works).

Here is alternative implementation based on the TargetLoweringInfo hooks.

1. FunctionLoweringInfo::ValueMap is created during the SelectionDAGBuilder walk through the BasicBlock. So we cannot query live-in register divergence from the CreateOperands => TargetLoweringInfo::isSDNodeSourceOfDivergence. By this point ValueMap has not yet been filled in.

Really? I thought we fill it in before we actually start building the SelectionDAG (in FunctionLoweringInfo::set). But you can move it earlier if you need to.

All above means that we cannot just validate the flag values and assert if it does not match. We have to run iterative solver for each block just before the selection to count the control dependencies and to propagate the flag values.

One more item that should be discussed is the target-specific exceptions to the common divergence modeling algorithm.
For instance in AMDGPU target we have amdgcn.readfirstlane/readlane intrinsics. They accept vector register and return the first or specific lane value.
So both accept naturally divergent VGPR but return the scalar value.
Following the common divergence computing algorithm - "the divergence of operation's result is superposition of the operands divergence" we'd set %scalar = tail call i32 @llvm.amdgcn.readfirstlane(i32 %tid) to divergent that is not true.
In the IR form of the divergence-driven selection we rely on the TargetTransformInfo::isAlwaysUniform hook that was added to interface for this purpose.
It allows the target to declare arbitrary set of target operations as "always uniform" so that the analysis does not count for their operands divergence.

In D35267#985601, @efriedma wrote:

Please also note that this addition does not depend on "tid" or any other divergent data. It is not possible to discover this dependency analyzing individual block. We need CFG information.

Yes, this is what I was getting at with "We should query the IR DivergenceAnalysis to compute isSDNodeSourceOfDivergence for a CopyFromReg from a live-in virtual register."; the nodes which need CFG information are precisely CopyFromReg nodes from virtual registers. Each virtual register created by the SelectionDAGBuilder should correspond to exactly one IR instruction.

In D40547#989137, @nhaehnle wrote:

In D40547#938894, @alex-t wrote:

If I understand everything correct...
The problem you're trying to solve is well known.
You have divergent loop-exit and a value that is uniformly defined inside the loop but used outside the loop.

More or less. However, whether the value is uniform or not doesn't really make a difference: I can change the test case so that %cc is non-uniform, and the same issue occurs. So this isn't really about DivergenceAnalysis.

Could you please look here: https://reviews.llvm.org/D40556

Could you use same approach?

You have 2 blocks: defBlock and useBlock and you want to know:

1. is useBlock is control dependent of defBlock ?
2. if 1 is true is defBlock's termination branch uniform? The set of control dependencies for defBlock is it's post-dominance frontier set The set of control dependencies for useBlock is it's post-dominance frontier set We need to check the branches that are NOT common in 2 sets above.

I don't think this works, but perhaps I'm misunderstanding you. In the test case which I've added, the defBlock is %for.body, and the useBlock is %for.end.

%for.end post-dominates the entire loop, so its post-dominance frontier is empty.

%for.body post-dominates %entry and %end.loop, so its PDF is only %mid.loop.

None of that information seems to help?

Specifically which nodes are a problem here? We should query the IR DivergenceAnalysis to compute isSDNodeSourceOfDivergence for a CopyFromReg from a live-in virtual register. (Not sure there's an existing map from registers to values, but you could easily construct one; basically the inverse of FunctionLoweringInfo::ValueMap.)

In D35267#966245, @efriedma wrote:

In D35267#962949, @alex-t wrote:

This is only true if your original computation is correct, and if DAGCombine/Legalization doesn't create any nodes which are naturally divergent. Neither of those are safe assumptions, I think. DAGCombine and legalization will transform loads and stores, which could end up creating a naturally divergent node.

So, my question is: could you imagine even theoretical sensible transformation that convert the graph in such a way that uniform node will get divergent income?

No, but that isn't the point. The problem is that you could replace a naturally divergent node with an equivalent naturally divergent node, but the new node doesn't have the divergent bit set (since the bit only gets set in DAGCombine for nodes with divergent operands, and naturally divergent nodes might not have divergent operands). Thinking about it a bit more, I guess regular load/store operations are a bad example; if a load produced multiple values given a uniform address, it would be a data race. But I think atomic memory operations could run into this issue? (Consider, for example, the code in DAGTypeLegalizer::PromoteIntRes_Atomic1.)

In D35267#962949, @alex-t wrote:

And some divergent nodes will never be passed to SelectionDAGBuilder::setValue when you build the DAG, due to the way SelectionDAGBuilder handles values with illegal types. But I'm not sure that's a complete list of the issues with the current version, and there's no practical way to check without a verifier.

Even if it creates new DAG pattern it returns it's root that (because of CreateOperands) has correct divergence that will be passed to setValue. Or I did not understand what you meant?

That's not what I meant.

Say you have a call to a divergent function which returns an i64, but i64 isn't legal on your target (so the function effectively returns two values of type i32). We create the call, a couple CopyFromReg nodes, and then a MERGE_VALUES to merge the value. Then you set the MERGE_VALUES to be divergent... but that isn't really helpful: legalization for MERGE_VALUES erases the node, so the "divergent" bit goes away.

This is a draft of the divergence analysis solver on the selection DAG. In the course of discussion the divergence bit verification was requested.
Analysis of the one given block cannot cover control dependencies. Thus the divergence bits set from the IR reflecting control dependencies cannot match those computed on the one isolated block DAG. That's why it is not exactly the verification. The analysis performed on the DAG augments the divergence information passed from the IR.

To start with, let's make sure that we're agreed on terms.
Divergent machine runs a set of threads (warp or wavefront) that execute same set of instructions in same order (SIMT).
Divergent operation operates on "vector" registers such that each register consists of many lanes - each thread operates on the data in corresponding lane.
From the above immediately follows that the only source of divergence is thread ID or any data that is derived from thread ID.
Usually it is a small set of target intrinsics that may be the source of such a data.

In D35267#960250, @efriedma wrote:

Actually, what I'd really like to see here is some sort of verifier for the divergent bit. It should be possible to recompute the divergence of the SelectionDAG at any point from first principles. There's a small set of operations which are fundamentally divergent: CopyFromReg where the register contains a divergent value (you should be able to derive this from DivergenceAnalysis), divergent memory accesses, and some target-specific intrinsics. (Not sure that's a complete list, but should be close.) All other operations are divergent if and only if they have a divergent predecessor.

Divergence bit propagation added to ReplaceAllUsesWith

In D35267#949394, @alex-t wrote:

In D35267#948666, @rampitec wrote:

There actually can be problem with folding the node if we patch it after creation. At least this needs to be checked.

That's true. The problem is that in SelectionDAG::getNode (where the SCEMap insertion is) we have no Value and no chance to check it's divergence.
And this is correct: SelectionDAG is for selection and we should not expose the IR Values to it.

The only way I see is to pass the Divergence parameter to getNode from all the SelectionDAGBuilder visitors. This will be correct but requires to change each of 109 visitors and getNode().

In D35267#949981, @efriedma wrote:

Any DAG transformation that change divergent pattern to not-divergent or vice versa is illegal.

Transforming "x*0 -> 0" is illegal if x is divergent? That seems surprising.

In D35267#948666, @rampitec wrote:

There actually can be problem with folding the node if we patch it after creation. At least this needs to be checked.

In D35267#946933, @efriedma wrote:

Does ReplaceAllUsesWith need to propagate changes to the "IsDivergent" bit?

Attention please! If nobody has objections this will be committed next Friday.

Targets that have no divergence do not depend on Divergence Analysis anymore.

updated according to the comments

If I understand everything correct...
The problem you're trying to solve is well known.
You have divergent loop-exit and a value that is uniformly defined inside the loop but used outside the loop.
In this case different threads would have different values.
Traditional Divergence Analysis cannot handle this. Since definition inside the loop body is uniform the use is uniform as well.
Since the value has no explicit data dependency of the loop index, the PHI-node in the loop header (that is divergent if loop-exit is) does not affect it's divergence formally.
The value in fact does have loop-carried dependency. For example:

In general looks correct to me. You definitely should check the branch itself - not the condition.
In your case (divergent loop-exit) branch itself is divergent because of the control dependency.

Implementation changed according to the reviewers suggestions.

In other words:

In D38754#900094, @MatzeB wrote:

I'm not sure I understand what exactly is going on. dead and kill flags work just as well for subregisters; I don't see a single COPY in your MI excerpt so I'm not sure what is going on or how copy propagation could get it wrong.

Back to initial approach.

r314828

The fix you suggested breaks x86 backend on SingleSource/Benchmarks/Adobe-C++/CMakeFiles/simple_types_loop_invariant.dir/simple_types_loop_invariant.cpp

Fixed according to the Matthias suggestion.

In D38754#893862, @MatzeB wrote:

Do you know whether the situation is already detected by DetectDeadLanes? I'd be more open to add dead code elimination to that pass (as we could run it instead of dead code elimination I believe).

In D38754#893862, @MatzeB wrote:

Reverted back to the simplest approach.

It is really make sense to take care of the V_READFIRSTLANE/V_READLANE destination register under exec == 0 condition in case their source VGPR is re-defined in SI_MASK_BRANCH target block. Otherwise we assume that source VGPR is defined in one of the dominating blocks and contain correct value.

1. Added the code that checks that scalar register produced by V_READFIRSTLANE/V_READLANE

Is really used by some SALU instruction. This is necessary to avoid de-optimization of those cases when the scalar register is distinctly the scalar operand of vector instruction.

Ping. Does anybody going to look at this? :)