Issue 244131
Summary UniformityAnalysis depends on cycle hierarchy in violation of formal definition of uniformity
Labels new issue
Assignees
Reporter jayfoad
    Let me say upfront that this is not a "real world" bug. It is a subtle issue only found by AI-assisted fuzzing and analysis.

Test case:
```llvm
define void @f(i32 inreg %a, i32 inreg %b, i1 inreg %uc, i1 inreg %ux) {
entry:
  %tid = call i32 @llvm.amdgcn.workitem.id.x()
  %div = icmp eq i32 %tid, 0
  br i1 %uc, label %S, label %R      ; uniform; swapping %S/%R flips the result
R:
  br i1 %ux, label %S, label %exit
S:
  %phi = phi i32 [ %a, %entry ], [ %b, %R ], [ %next, %S ]
  %next = add i32 %phi, 1
  br i1 %div, label %S, label %R
exit:
  ret void
}
```
Note that {R,S} is an irreducible cycle. CycleAnalysis gets to make an arbitrary choice about how to represent the cycle hierarchy.

With the test as written, CA picks R as a cycle header and {S} as a child cycle. **UA then reports %phi as uniform.**

With the first branch rewritten as `br i1 %uc, label %R, label %S`, CA picks S as a cycle header. That cycle is "assumed divergent" by UA which then reports %phi as divergent.

My understanding of the [formal definition of uniformity](https://llvm.org/docs/ConvergenceAndUniformity.html#uniformity) is that it has to hold for every possible cycle hierarchy. So UA is wrong to claim %phi is uniform under the first hierarchy since it is divergent under the second hierarchy. In the doc's terminology, %phi is not [m-converged](https://llvm.org/docs/ConvergenceAndUniformity.html#convergence-m-converged).

Cc @ssahasra @he-weiwen @PankajDwivedi-25 
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to