ethereum
Implementation of Lengauer-Tarjan algorithm to find dominators
This is one step towards fixing https://github.com/ethereum/solidity/issues/13721
The implementation is based on the following paper: https://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf, see appendix B pg. 139.
Why is it still a draft?
Because I still need to address this comment here: https://github.com/ethereum/solidity/pull/14460#discussion_r1291601390 which will require refactor of the current code. Or we could merge it as it is now and refactor it later.
Ah, ok. I thought it was ready and only waiting for a review and that you just forgot to mark it as such :)
Or we could merge it as it is now and refactor it later.
I mean, whether recursion depth will be an issue depends on what we end up using this algorithm for in practice. I think there's a real risk that the graphs do end up being quite large in edge cases, but I haven't actually done any calculation that would prove it. It just seems like I cannot exclude that possibility. You could try to do a very rough estimation of the worst case and if it seems that it's unlikely that it can exhaust the stack, we can also just slap a TODO on it and merge without fixing it.
We'd just have to be careful every time we use it for a new thing. Hitting the limit in some, even not so uncommon edge cases, will likely not be easy to discover in a PR because code we test with is never very large. And I don't have confidence that out external projects are comprehensive enough to hit such cases. So if we get it wrong. we'll just get bug reports when we release and people start actually using it. It won't be the end of the world - it will just crash and not do anything dangerous - but my preference is just to not end up in a situation where I have to worry about it and do things right from the start.
So overall I'd say it depends on how badly we want to merge it. If there's a hurry, TODO is good enough. Otherwise I'd rather still fix it, unless you have an estimate of max depth in our use case showing it's a non-issue.
I mean, merging this and actually using it are still two things. Having an eternal PR like this based on some possible refactoring to address hypotheticals also doesn't really help ;-). So I'd say, let's just merge this and take things from there.
I'll make sure we merge it next week, but I'd still want to take another pass through it before we do. Looking at it now, I remember that there were some questionable things that I wanted to get back to after the stuff I pointed out is fixed. In the end I never did because there were always other important things, but I'll prioritize this PR now.
I converted it to draft since I'm still applying the refactoring to an id-based algorithm and there are some commits that will be moved to another PRs.
You can see how it will be used in this branch: https://github.com/ethereum/solidity/tree/dominator-yul-cfg
By the way, maybe someone will find this useful: An Explanation of Lengauer-Tarjan Dominators Algorithm. The original paper is pretty dense and I found this one more helpful to get a general overview before digging into details.