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.

Sign up for GitHub

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

Jump to bottom

x/tools/go/pointer: explore Pavlogiannis’s algorithms for APA #39604

Closed
smasher164 opened this issue Jun 16, 2020 · 1 comment
Closed

x/tools/go/pointer: explore Pavlogiannis’s algorithms for APA #39604

smasher164 opened this issue Jun 16, 2020 · 1 comment
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance Tools This label describes issues relating to any tools in the x/tools repository.
Milestone
Unreleased

Comments

@smasher164
Copy link
Member

Andreas Pavlogiannis submitted this paper to CoRR which presents upper and lower bounds for Andersen's pointer analysis and its variants. Additionally, they present several algorithms for solving them. These include

  1. An algorithm to solve exhaustive APA in O(n^3).
  2. An algorithm to solve sparse APA in O(n^(3/2)).
  3. An algorithm to solve bounded APA with a sub-cubic upper bound.
    • They introduce bounded APA as a practical variant, where they bound the number of statements of the form "∗a = b represents an indirect assignment c = b, where c is pointed by a".

Note that these solutions compute reachability on a Dyck graph, which is a flow graph with edges for pointer references and dereferences. We should explore the use of these algorithms in go/pointer’s solver.

Thoughts?
@alandonovan
@smasher164 smasher164 added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Jun 16, 2020
@gopherbot gopherbot added the Tools This label describes issues relating to any tools in the x/tools repository. label Jun 16, 2020
@gopherbot gopherbot added this to the Unreleased milestone Jun 16, 2020
@alandonovan
Copy link
Contributor

go/pointer is unfortunately not in a good state, as pointer analysis, by its nature, requires making assumptions about the internals of other packages, which makes it very fragile. It usually breaks on each Go release, and few people have sufficient understanding of pointer analysis to fix the breakage.

I think we should delete the package altogether.

@golang golang locked and limited conversation to collaborators Apr 20, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance Tools This label describes issues relating to any tools in the x/tools repository.
Projects
None yet
Milestone
Unreleased
Development

No branches or pull requests
3 participants
@alandonovan @gopherbot @smasher164