[wahern]

> its probably hopeless for branch divergence to ever be solved

Here's a partial solution, at least: Huihui Sun, Florian Fey, Jie Zhao, Sergei Gorlatch, "WCCV: improving the vectorization of IF-statements with warp-coherent conditions", 2019, https://www.di.ens.fr/~zhaojie/ics2019.pdf

> WCCV uses two different methods to detect warp-coherent conditions. The first method detects boolean-step conditions based on static affine analysis. Affine analysis is usually used for analyzing memory access patterns [15, 23], while we use affine analysis to analyze the variables and expressions used in conditions in order to detect a boolean-step condition. If the static affine analysis fails, we use the second method based on the branch probability estimation to identify high-probability conditions. We develop a cost model based on the estimated branch probability and branch cost: if a certain branch is more likely to be executed and the corresponding branch cost is greater than a threshold, we treat the corresponding condition as warp-coherent. We use auto-tuning to determine the optimal thresholds for various target platforms and applications.

Specifically, the detection of "boolean-step conditions" looks interesting. The fallback heuristic sounds like one of those things that doesn't extrapolate well in the wider software ecosystem.