Skip to content
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

Closed
chabbimilind opened this issue Jun 26, 2021 · 16 comments
Closed

x/tools/go/ssa: add DomPostorder to Function #46941

chabbimilind opened this issue Jun 26, 2021 · 16 comments

Comments

@chabbimilind
Copy link

https://pkg.go.dev/golang.org/x/tools/go/ssa#Function contains DomPreorder() 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 via DomPostorder function? My example implementation is here.

@seankhliao seankhliao changed the title [Proposal] x/tools/go/ssa: Add DomPostorder to Function proposal: x/tools/go/ssa: add DomPostorder to Function Jun 26, 2021
@gopherbot gopherbot added this to the Proposal milestone Jun 26, 2021
@ianlancetaylor ianlancetaylor added this to Incoming in Proposals (old) Jun 27, 2021
@ianlancetaylor
Copy link
Contributor

CC @alandonovan

@findleyr
Copy link
Contributor

CC @timothy-king

@timothy-king
Copy link
Contributor

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.

  1. Are there other changes required for supporting DomPostorder, such as the computation for dom.post not being identical?
  2. Are there alternative implementations that do not require modifying ssa? Roughly how expensive are these alternatives? Both in terms of maintenance and runtime?
  3. Is modifying ssautil to do an after the fact analysis sufficient?
  4. How many users do you expect will take advantage of this feature if we added it?
  5. If DomPostorder was added and proposal: x/tools/go/ssa: add Postdominator to Function/BasicBlock #46942 was not, what would the likely outcome be for you and others?

@chabbimilind
Copy link
Author

chabbimilind commented Jun 28, 2021

@timothy-king, thanks for the response.

  1. Are there other changes required for supporting DomPostorder, such as the computation for dom.post not being identical?

Not sure I fully understand this question. Please can you elaborate or give an example?

Are there alternative implementations that do not require modifying ssa? Roughly how expensive are these alternatives? Both in terms of maintenance and runtime?

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.

Is modifying ssautil to do an after the fact analysis sufficient?

Can you show a exmape use case? I still think it will not be the most natural place for this query.

How many users do you expect will take advantage of this feature if we added it?

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.

If DomPostorder was added and proposal: x/tools/go/ssa: add Postdominator to Function/BasicBlock #46942 was not, what would the likely outcome be for you and others?

Both really belong to the SSA package as I explained above.

@timothy-king
Copy link
Contributor

pass along that data structure everywhere where a function/basic block. Adding it to SSA is the most natural place

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.)

removes unnecessarily reinventing the wheel by others.

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.)

It would be quite tedious to maintain it outside of SSA.
One has to get the CGF (which is not exposed) for each function

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?)

Not sure I fully understand this question. Please can you elaborate or give an example?

An example would be a location where dom.post is computed differently in the GOCC fork.

@chabbimilind
Copy link
Author

@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).

@timothy-king
Copy link
Contributor

One alternative would be to include a postdominator analysis outside of the ssa package (maybe ssautil? maybe its own package?) That could return a summary of the post dominator analysis for a given ssa.Function. This would be similar to how x/tools/go/callgraph works. The main disadvantage is that this would not be carried with the ssa.BasicBlocks themselves. This alternative has advantages including simpler maintenance of ssa, less computation for most users of ssa, and composes with existing packages.

Why would it be more significantly more tedious to maintain this outside of the ssa package?

If you have data points that would help us address this, it would help weighing this proposal against alternatives.

None of us can be sure how many clones and copies exist around the world including the private repos.

We can work with imperfect proxies (such as open source) to estimate usage.

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).

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. (*ssa.BasicBlock).Dominates has been available since at least 2013. At the moment, I am just aware of a small handful of users. I don't expect this to dramatically change if we were to adopt this proposal.

@dominikh
Copy link
Member

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.

@chabbimilind
Copy link
Author

@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.

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.

+1 for this as I have been saying this is just a matter of exposing the API.

@timothy-king

One alternative would be to include a postdominator analysis outside of the ssa package (maybe ssautil? maybe its own package?)

That is a reasonable alternative. It however leads to two issues:

  1. Inconsistency on how we'll use Dominators vs. Post Dominators. For consistency, we need to introduce Dominators as well in this proposed package.
  2. It will lead to a bit verbose use like below (since PostDom is not present on BasicBlock)
    newPackage.getPDom(blockA.Parent()).PostDominates(blockA, blockB) instead of the currently proposed blockA.PostDominates(blockB).

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.

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.

@timothy-king
Copy link
Contributor

Apologies for suggesting these threads be merged. I think I have made the conversation more confusing as they are separate decisions.

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.

Yes this is already computed as a side-effect of the dominators. So supporting it is not that significant of a change.

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.

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.

Inconsistency on how we'll use Dominators vs. Post Dominators.

I had not considered this. Having these asymmetric is a bit confusing.

For consistency, we need to introduce Dominators as well in this proposed package.

I am not sure whether we need these to be consistent. It may be preferable. An example showing the advantage of consistency would help.

It will lead to a bit verbose use like below (since PostDom is not present on BasicBlock)
newPackage.getPDom(blockA.Parent()).PostDominates(blockA, blockB) instead of the currently proposed blockA.PostDominates(blockB).

I think that we can probably live with this. This is not considerably different than the situations of x/tools/go/{callgraph,pointer}.

Thoughts
My personal opinion is that Dominator was exposed prematurely in ssa. Many usages of ssa do not need it [perhaps most?], and I would prefer if it was computed by libraries that specifically know they are going to use it. It is simpler maintaining APIs that do a narrow function. It is hard to remove methods and fields once they have been exposed in popular libraries. This is the situation we are currently in and removing dominator information from the exposed API is now difficult (a v2 would likely be appropriate). For ssa, there are many code attributes we might want to compute and store on the basic blocks, functions, instructions, etc. Further due to how the ssa package largely hides building its elements, this really encourages doing analysis to compute all of the attributes it exposes. (Adding knobs for how to build the ir and what attributes to compute causes other issues.) I want to judiciously add attributes to ssa as removing them is breaking change and computing during building imposes a cost on all users.

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:

  • I am moderately supportive of having post dominators in a different package.
  • I am mildly unsupportive of extending ssa with post-dominators methods.
  • I am moderately supportive of exposing the post-order of the dominator tree.

@adonovan
Copy link
Member

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.

@rsc
Copy link
Contributor

rsc commented Jan 10, 2024

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

@rsc
Copy link
Contributor

rsc commented Jan 18, 2024

/cc @timothy-king

@rsc
Copy link
Contributor

rsc commented Jan 19, 2024

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

The proposal is to add (*Function).DomPostorder next to (*Function).DomPreorder.

@gopherbot
Copy link

Change https://go.dev/cl/557055 mentions this issue: go/ssa: add Function.DomPostorder

@rsc
Copy link
Contributor

rsc commented Jan 26, 2024

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

The proposal is to add (*Function).DomPostorder next to (*Function).DomPreorder.

@rsc rsc changed the title proposal: x/tools/go/ssa: add DomPostorder to Function x/tools/go/ssa: add DomPostorder to Function Jan 26, 2024
@rsc rsc modified the milestones: Proposal, Backlog Jan 26, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Accepted
Development

No branches or pull requests

8 participants