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

Refactor: investigate use of worklist in SimpleMonotonicSolver #39

Closed
utting opened this issue Jun 22, 2023 · 3 comments
Closed

Refactor: investigate use of worklist in SimpleMonotonicSolver #39

utting opened this issue Jun 22, 2023 · 3 comments
Assignees
Labels
refactor Refactor to clean up code or design

Comments

@utting
Copy link
Contributor

utting commented Jun 22, 2023

SimpleMonotonicSolver in MonotonicSolver.scala is currently doing several recursive traversals of each graph and returning from a node on the second or greater pass when its value does not change. This could potentially be less efficient than a worklist approach, and could stop short of the true fix point if there are longer chains of dependencies.

Investigate using a worklist algorithm, but also check how to ensure that every node in a procedure is visited at least once.

@utting utting added the refactor Refactor to clean up code or design label Jun 22, 2023
@utting utting self-assigned this Jun 22, 2023
@yousifpatti yousifpatti self-assigned this Jun 30, 2023
@yousifpatti
Copy link
Contributor

Reasons behind the monotonic solver:
Context switching: Because the VSA analysis uses stack context switching, it relies on the order of function entry/exit nodes. Therefore, solver needs to maintain a monotonic approach in traversing the CFG as opposed to all CFG nodes being added.

@l-kent
Copy link
Contributor

l-kent commented Oct 16, 2023

What's the status of this? I think a suitable approach to this would be to port over the WorklistWithReachability (I think that's what it's called) from TIP?

@yousifpatti
Copy link
Contributor

Has been marged into main. Refer to PR: #114

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
refactor Refactor to clean up code or design
Projects
None yet
Development

No branches or pull requests

3 participants