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

proposal: x/tools/go/ssa: add Postdominator to Function/BasicBlock #46942

Open
chabbimilind opened this issue Jun 26, 2021 · 4 comments
Open

Comments

@chabbimilind
Copy link

https://pkg.go.dev/golang.org/x/tools/go/ssa#Function  does not build or expose post-dominator relationships among its constituent basic basics.

I found it essential to find post dominance in SSA functions for a lock-unlock analysis [here (https://arxiv.org/pdf/2106.01710.pdf).
The code using the post dominance can be seen here.

Constructing and exposing post dominance in an SSA Function is relatively simple. It can reuse most of the code available for dominance. I have an example buildPostdomtree() here.
We need to add APIs such as:

func (b *BasicBlock) PostDominees() []*BasicBlock
func (b *BasicBlock) PostDominates(c *BasicBlock) bool
func (f *Function) PostdomPreorder() []*BasicBlock
func (f *Function) PostdomPostorder() []*BasicBlock {
func (b *BasicBlock) Ipdom() *BasicBlock

All of these are prototyped here.

@seankhliao seankhliao changed the title [Proposal] x/tools/go/ssa: Add Postdominator to Function/BasicBlock. proposal: x/tools/go/ssa: add Postdominator to Function/BasicBlock 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

See response on related issue #46941 (comment).

@adonovan
Copy link
Member

Unlike dominance, the go/ssa package has no need for postdominance, so I don't think it should go to the trouble of computing it. But since go/ssa exposes the control-flow graph, it shouldn't be hard for clients that need it to compute it externally as the need arises.

Once there's an external implementation, we could consider a proposal to move it to a subpackage of go/ssa.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Status: Incoming
Development

No branches or pull requests

6 participants