I don't quite understand the change, now that the counters are in unknown state, shouldn't we wait for their arrival so that we can access the registers for the arguments (which may be loaded from memory in the caller)? I think we definitely need these waits at the entry of cs_chain* function.

LGTM

I think a more accurate description of the real problem is: sinking vgpr def which has a loop-variant sgpr source out of divergent loop is wrong for AMDGPU. For other cases, it is still legal to move out of loop. The problem is not specific to nested loops, it also applies to single loop. The test case has been over-simplified and does not show original problem (both .ll and .mir test). We can keep the code as now, but I still think it's better to update the tests to show the real problem to make it easy to revisit the issue.

I think we definitely should do this! just one inline comment.

Thanks for the new version, looks good to me.

In D150246#4341656, @foad wrote:

I think this is OK, but wouldn't it be simpler to transform ((a | c1) << c2) ==> (a << c2) | (c1 << c2) and remove the knownbits check? Or do you think that would make the generated code worse overall?

In D150246#4337140, @arsenm wrote:

Is there a negative test for the common bits case?

fix the issue instead of removing the optimization.

It should help because SelectionDAG::isBaseWithConstantOffset knows how to match OR (if the known bits do not overlap) as well as ADD.

Do you mean we can optimize for shl(or) with the help of knownbits? I think I agree with you. But I am not sure whether it is really helpful in practical cases. The isBaseWithConstantOffset you mentioned specifically designed to work on stack slot access. I am not sure if such patterns can also be observed more broadly. And I think such kind of optimization should be done separately, maybe it should be added in the common LLVM code. And the lit-test should also be redesigned. I would rather fix the problematic transformation first. sounds ok to you?

I guess you are observing code generation bug for AMDGPU? Is it replacing a phi like %1:vgpr = phi %0:sgpr with a %1:vgpr = COPY %0:sgpr? If that is the case, I think this does not sound like a root-fix.

LGTM

Why I cannot reproduce the assertion? I have tried on latest version and a version several days before.

In D147683#4250292, @arsenm wrote:

Does tablegen not infer convergent instructions from the source pattern? I assume not (but I always found this to be a dubious feature)

If not-taken conditional branches are cheap then we could do something like this. It only has one taken branch, when we have finished handling all the active lanes.

  // Inclusive plus-scan v0 into v1. Also leaves the result of the plus-reduction in s3.
  s_mov s0, exec
  s_mov s3, 0 // accumulator
// repeat this section 32 or 64 times:
  s_ff1 s1, s0 // find lowest remaining active lane
  s_cmp_eq s1, -1
  s_cbranch_scc1 end
  s_bitset0 s0, s1
  v_readlane s2, v0, s1
  s_add s3, s2
  v_writelane v1, s3, s1
// end of repeated section
end:

VAL = ... // VGPR
RES = ... // FINAL result of scan, active lanes will write to this VGPR
sum = 0;                               // SGPR, holds the partial sum
for (int lane = 0; lane < 64; lane++) {
    if(IsActive(lane)) {                      // check to see whether lane is active or not 
        elementToadd = readlane(VAL, lane );  // SGPR, read value which we want to add from VAL at lane id
        sum = sum + elementToadd;            // SGPR, update the value
        writelane(RES, sum, lane )          // write value sum(SGPR) to VGPR RES at lane
    } 
}

The idea here is a dangerous way to program our GPU. Please check comment below to see why we should not do this.
A possible safe way is to do something like:

// all the active threads should enter the loop.
do {
 get_first_active_lane()
 bool hasUnprocessedlane = true;
 if (is_first_active_lane) {
   // only the first active lane will go here, other threads will skip to the loop end.
   do the work for this active lane
   hasUnprocessedLane = false;
 }
}  while (hasUnprocessedLane);

The hasUnprocessedLane was used to say that the first active lane being processed in this iteration should exit the loop.

LGTM

I am not sure what your question is:

1. Cycle is assumed to be divergent because it is irreducible. But operations that are always uniform need not be assumed to be divergent. That is this case.
2. Cycle has divergent exit. Value that is always uniform may still be divergent at its used. That is separately handled by temporal divergence.

I am asking for the second. thanks for the explanation.

In D145572#4180384, @sameerds wrote:

In D145572#4180375, @ruiling wrote:

In D145572#4178109, @ronlieb wrote:

LGTM, as this resolves our downstream assertions seen in our CI

Why would this fix an assertion? The description sounds like this is just an improvement. I think we need a reproducer for the assertion.

Please see the comment regarding pushUsers().

In D145572#4178109, @ronlieb wrote:

LGTM, as this resolves our downstream assertions seen in our CI

Thank you for the fix! LGTM

In D144162#4140550, @sameerds wrote:

I agree with @gandhi21299 ... it's best to work through the passes one at a time. But maybe we should not enable each change as it happens. We could put the changes behind a command-line option to switch between DA and UA. One single option that switches whatever passes have been updated, until all passes are updated and we are ready to flip the switch permanently.

Although I wanted the optimization for the undef case to be bring back in a more defined way, I think it is acceptable to match with existing divergence analysis. This would help with the transition to uniform analysis, so LGTM. Please also address Jay's suggestion. Could you also add some FIXME around the code like: optimally reporting uniform with undef input should be done in more defined way. In general CFG, it might be broken?

I think it is reasonable to match divergent analysis behavior regarding to undef. The other problem that isUniform() return true for a divergent branch instruction makes me wonder: is it the best way to replace use of divergence analysis with uniform analysis one by one? Although I am optimistic about the quality of uniform analysis, I think it may be more helpful to replace all the occurrences of divergence analysis and fix all the bugs uncovered. Ideally, we would have very little test changes. The reason is that one specific pass may not have enough test coverage. Fixing the bugs after switching all the uses of divergence analysis to uniform analysis will make us more confident that we will less likely cause regression. Any different idea?

I think for this specific case, we should report %8 as uniform, and the branch should also be uniform. But there seems something wrong in the uniform analysis, if you try opt -passes='print<uniformity>' with the test here. We will see both the condition %8 and the conditional branch br i1 %8,... are reported as divergent. but the isUniform() query return true for the branch instruction. I think there should be something wrong in uniform analysis. If the condition is divergent, I think the branch should also be divergent. Another issue I want to point out that the uniform analysis has a subtle difference with divergence analysis. There is some comment in https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/AMDGPU/AMDGPURewriteUndefForPHI.cpp#L13 to explain the issue. I think we need to fill the gap to switch to uniform analysis, otherwise we will regress code generation. The last time we discussed this, I think we want some target specific option in uniform analysis to match this behavior with divergence analysis.

I revisit the problem again. I agree we are allowed to duplicate such intrinsic based on the fact that the intrinsic lower has already support their usage in unstructured CFG. but the case shown that duplicating such intrinsics might not be helpful for generating better code. By making them non-duplicable, we would get simplified usage of control flow intrinsics. Some testing on large set of graphics shaders, the change causes no code generation differences.

rebase with more comment

address review comments.

Use alignment from alloca.

use cast instead of dyn_cast.

In D140537#4035672, @foad wrote:

I like this but it would be nice to have tests showing the effect on DS, FLAT and SCRATCH instructions.

Thanks for the careful review @arsenm, I have fixed most of them. Please help take a second look. Thanks!

address review comments.

rebase and ping.

Update the change to use a new bit in TSFlags

I think it is good to go. Thanks!

ping

In D139780#4022193, @gandhi21299 wrote:

• inserted a check for switch terminator, ...

I don't think just checking for switch terminator would work. My suggestion is don't handle switch here. The pass has never been designed to work with switch terminator, and it needs non-trivial work to support switch terminator in this pass. As we already lower switch terminator before this pass, I think it is not important to support switch terminator in this pass now.

In D140599#4015680, @arsenm wrote:

In D140599#4014542, @ruiling wrote:

In D140599#4014540, @arsenm wrote:

Shouldn't these have been expanded into loads and stores already?

We only split mem transfer intrinsics using a loop if its length is > 1024.

I think InstCombine and/or SROA do some too. Also that threshold is arbitrary, and we could start expanding the small ones in IR too

In D140599#4014540, @arsenm wrote:

Shouldn't these have been expanded into loads and stores already?

In D139780#4004766, @arsenm wrote:

I haven't looked closely but some of these test changes look worse

In D139780#3990936, @gandhi21299 wrote:

@ruiling PDT.getRoot() yields BB4. So for PDT with exactly one root, we should only allow the transformation when its terminator is a branch instruction?

Yes.

This causes the following tests to fail due to insertion of dummy blocks:

Thanks for working on this, but I think it is more reasonable to fix the issue early. The function is showing a problem in our cfg lowering passes for AMDGPU. The cfg lowering are being done by several passes. I know it is very tricky and fragile now, so it is not easy to determine what the right fix should be. For this specific case, the input IR does not have a return block, thus bypass the structurizeCFG pass. The AMDGPUUnifyDivergentExits happened before StructurizeCFG already has some ability to handle infinite loops, but this case was skipped because of the check if (PDT.root_size() <= 1). In this case, BB3 is a root in PDT but it is not a true exit. I would suggest we change this. If there is only one root in PostDominatorTree, please check whether it ends with return/unreachable instruction before we can skip the transformation. If the single root in PDT ends with a branch instruction, we should continue the transformation to insert a dummy return block and insert a control flow edge that is never taken with trick like br i1 true, ..., DummyReturn. By doing this, we should be able to lower the cfg correctly.

I think the best solution for the motivating problem is in the backend, where the load instructions have reached its final form, thus could help more cases. A load in LLVM IR is still subject to either split or combine.