| Issue |
244602
|
| Summary |
[X86] Infinite DAG combine loop with -combiner-topological-sorting: combineOr freezes a BUILD_VECTOR again after it is unfrozen
|
| Labels |
backend:X86,
llvm:hang,
llvm:SelectionDAG
|
| Assignees |
|
| Reporter |
chfast
|
With `-combiner-topological-sorting`, llc does not finish on this function:
```llvm
define i8 @f(i8 %a) {
%v = insertelement <16 x i8> splat (i8 1), i8 %a, i32 0
%o = or <16 x i8> %v, <i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 -1, i8 2, i8 2>
%s = shufflevector <16 x i8> %o, <16 x i8> zeroinitializer, <16 x i32> <i32 0, i32 1, i32 16, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15>
%m = call i8 @llvm.vector.reduce.smax.v16i8(<16 x i8> %s)
ret i8 %m
}
```
`llc -mtriple=x86_64-linux-gnu -combiner-topological-sorting` does not stop. Without the flag, it compiles at once. It also does not stop with `-mtriple=i686-linux-gnu -mattr=+sse2`, `-mattr=+avx2` or `-mattr=+avx512f,+avx512bw`. llc 23 from 2026-06-01 compiles it with the flag.
`-debug-_only_=dagcombine` shows a cycle. Here `1` is `Constant:i8<1>`, `t3` is `%a`, `t219` and `t226` are `freeze undef:i8`, `t14` is the zero vector, and `t25` is the `or` constant with lane 2 undef: `BUILD_VECTOR 2, 2, undef, 2, ..., -1 (lane 13), 2, 2`.
```
Combining: t12: v16i8 = or t218, t25
Combining: t218: v16i8 = freeze t217
... into: t220: v16i8 = BUILD_VECTOR t3, 1, t219, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, t219, 1, 1
Combining: t15: v16i8 = vector_shuffle<0,1,18,3,4,5,6,7,8,9,10,11,12,13,14,15> t12, t14
Replacing.2 t220: v16i8 = BUILD_VECTOR t3, 1, t219, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, t219, 1, 1
With: t222: v16i8 = BUILD_VECTOR t3, 1, undef:i8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, t219, 1, 1
Combining: t12: v16i8 = or t222, t25
Replacing.2 t222: v16i8 = BUILD_VECTOR t3, 1, undef:i8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, t219, 1, 1
With: t224: v16i8 = BUILD_VECTOR t3, 1, undef:i8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, undef:i8, 1, 1
Combining: t12: v16i8 = or t225, t25
Combining: t225: v16i8 = freeze t224
... into: t227: v16i8 = BUILD_VECTOR t3, 1, t226, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, t226, 1, 1
...
```
The cycle:
1. `DAGCombiner::visitFREEZE` pushes the freeze into the BUILD_VECTOR. The undef lanes 2 and 13 become `freeze undef`.
2. The shuffle takes lane 2 from the zero vector. `SimplifyDemandedVectorElts` makes lane 2 of the BUILD_VECTOR undef again.
3. X86 `combineOr` does not demand lane 13 of the first operand, because lane 13 of the constant is all-ones. `SimplifyDemandedVectorElts` makes lane 13 undef. Lane 2 is still demanded (the constant has undef there) and is undef, so the fold puts a new freeze on the operand:
```cpp
// We must freeze the result to prevent OR(poison,-1) -> poison.
// Restrict the fold to prevent infinite loops due to
// SimplifyDemandedVectorElts removing the freeze.
if (!DemandedElts.isAllOnes() &&
!DAG.isGuaranteedNotToBeUndefOrPoison(N0, DemandedElts) &&
TLI.SimplifyDemandedVectorElts(N0, DemandedElts, DCI)) {
SDValue F0 = DAG.getFreeze(N->getOperand(0), ~DemandedElts);
DAG.UpdateNodeOperands(N, F0, N->getOperand(1));
return SDValue(N, 0);
}
```
4. Back to step 1.
The fold came with #215538. When I disable it, this function and the original fuzzer function (a `<64 x i8>` `or` and shuffles, `optsize`) compile with the flag. In the default order the nodes are visited in a different order, and the combine stops.
Found by fuzzing. Topological order is not the default on X86, but this would block enabling it (#83422).
Assisted-by: Claude Code (Claude Opus 5.5)
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs