-
Notifications
You must be signed in to change notification settings - Fork 17.9k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
x/tools/go/ssa: add DomPostorder to Function #46941
Comments
CC @alandonovan |
Issue #46942 and this will have the same basic concerns. You may want to consolidate the discussion into 1 proposal. At the moment the example implementation (https://github.com/uber-research/GOCC/blob/master/tools/gocc/thirdparty/src/golang.org/x/tools/go/ssa/dom.go#L72), x/tool/go/ssa has been forked.
|
@timothy-king, thanks for the response.
Not sure I fully understand this question. Please can you elaborate or give an example?
I looked at these possibilities. It would be quite tedious to maintain it outside of SSA. One has to get the CGF (which is not exposed) for each function, and compute its post dominator and pass along that data structure everywhere where a function/basic block. Adding it to SSA is the most natural place and removes unnecessarily reinventing the wheel by others.
Can you show a exmape use case? I still think it will not be the most natural place for this query.
Many compiler analyses and optimizations depend on post dominator and postorder traversal of CFG. It is not a one off case. Look at LLVM for example.
Both really belong to the SSA package as I explained above. |
Carrying around additional analysis results is definitely more work for users of the package. It also tends to lead to less efficient lookups. Carrying around this information is doable and not obviously too onerous in many cases. There are many code attributes can be thought of as natural extensions to the SSA package: the originating ast.Node, a globally unique ID for each ssa.Node, the status of whether a function {can return/always exits/always unwinds}, whether a global is effectively constant post initialization, etc. It is not clear whether we should keep extending the SSA package to include these. Each time we do, the Go team is committing to maintaining this information and API. We are also probably computing these attributes during ssa construction so other checkers and increasing their memory and runtime consumption too. There is a tradeoff being made by including it and we are trying to find the right balance. (FWIW I develop on top of ssa too and carry around analysis results so I understand the complaint that this requires extra work.)
How many users do we expect to take advantage of these functions if they were included in the ssa package? The current evidence I have that the exported functions for dominators in ssa is that there are not many users. Off the top of my head, I can think of nilness, go-flow-levee, and now GOCC. (staticcheck maintains its own fork of ssa so that is a grey area.)
Why would it be more significantly more tedious to maintain this outside of the ssa package? Is there information is not exported for the functions that is required to compute this? What is not there that would be difficult to recover? (An analogous example is that it is difficult to recover all of the ast.Nodes for range statements as this information is partially lost during translation.) How much more tedious are we talking about? (A human day/year for the maintainer of a hypothetical postdominator package?)
An example would be a location where dom.post is computed differently in the GOCC fork. |
@timothy-king committing to maintaining APIs is understandable but let's not make decisions based solely on "maintenance" grounds. Please consider the utilitarian aspect. The APIs I am suggesting have low maintenance and more importantly, they are (almost) already readily available inside the SSA package. It is a matter of exposing them. Dominance, post-dominance (and their frontiers) are quite fundamental building blocks of compiler analysis and these APIs can help develop more static analysis. None of us can be sure how many clones and copies exist around the world including the private repos. It is a no-brainer from a compiler development and researcher viewpoint to have these APIs in the SSA package. The question of "how many people use it" is like the "train station paradox" (the train does not stop because people are not there and people are not there because the train does not stop). |
One alternative would be to include a postdominator analysis outside of the
If you have data points that would help us address this, it would help weighing this proposal against alternatives.
We can work with imperfect proxies (such as open source) to estimate usage.
I think the existing set of users of ssa's dominator related functions will do a decent job of estimating the set of potential future users of dominator and post-dominator related functions. |
My two cents: go/ssa already computes the post-order of the dominator tree, so the only significant change to go/ssa would be the addition of new public API. We should be careful, however, not to mix up the post-order traversal over the dominator tree with the post-dominator tree. I've seen both been mentioned here and in the linked-to commit, and I am no longer sure what OP is asking for. |
@dominikh ,we merged the discussion on post-order traversal over domtree and postdom tree computation as per @timothy-king's suggestion earlier in this (and another) thread.
+1 for this as I have been saying this is just a matter of exposing the API.
That is a reasonable alternative. It however leads to two issues:
I don't have a perfect way to assess this. But IDom is used some 13K times (a lot of clones) and Dominees appears some 8.8K times in githib public repos. |
Apologies for suggesting these threads be merged. I think I have made the conversation more confusing as they are separate decisions.
Yes this is already computed as a side-effect of the dominators. So supporting it is not that significant of a change.
Thank you for suggesting this additional data. I scanned the first 10 pages for Dominees. I was not aware of 6 uses on the first page to build additional tools. After the first page, I saw only clones of x/tools. In the first 10 pages of IDom, I saw clones of the compiler, staticcheck, and x/tools. There were 2 unrelated usages in a generic graph algorithm. Admittedly this is far from an exhaustive search, but I suspect it is telling.
I had not considered this. Having these asymmetric is a bit confusing.
I am not sure whether we need these to be consistent. It may be preferable. An example showing the advantage of consistency would help.
I think that we can probably live with this. This is not considerably different than the situations of x/tools/go/{callgraph,pointer}. Thoughts An example is staticcheck's ir.Function.NoReturn field. This is likely a good example of an extension to include as many checkers directly benefit from an improved control-flow precision due to ir building (which is hard to do after building the ir). Another example, if you look at nilness's use of Dominees, the dominators for one function do not need constructed ahead of time as each function is analyzed once in isolation. This won't be universally true, but other cases can easily build an appropriate cache. Putting this together for my thoughts on these two related proposals:
|
Exposing a DomPostorder method would be trivial: just copy DomPreorder and replace dom.pre with dom.post. I see no reason not to do it. Computing the postdominator tree (#46942) is quite different, since SSA doesn't care about postdominance. |
This proposal has been added to the active column of the proposals project |
/cc @timothy-king |
Based on the discussion above, this proposal seems like a likely accept. The proposal is to add (*Function).DomPostorder next to (*Function).DomPreorder. |
Change https://go.dev/cl/557055 mentions this issue: |
No change in consensus, so accepted. 🎉 The proposal is to add (*Function).DomPostorder next to (*Function).DomPreorder. |
https://pkg.go.dev/golang.org/x/tools/go/ssa#Function
containsDomPreorder()
but lacks a post-order traversal of basic blocks. I found it essential to traverse the basic blocks in post order in an inside-out visit of basic blocks.. It is readily available inside the package, please can we expose it viaDomPostorder
function? My example implementation is here.The text was updated successfully, but these errors were encountered: