Skip to content

LLVM needs a generic update SSA mechanism #589

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
Closed
lattner opened this issue Feb 1, 2004 · 13 comments
Closed

LLVM needs a generic update SSA mechanism #589

lattner opened this issue Feb 1, 2004 · 13 comments

Comments

@lattner
Copy link
Collaborator

lattner commented Feb 1, 2004

Bugzilla Link 217
Resolution FIXED
Resolved on Oct 10, 2009 21:09
Version trunk
OS All
CC @asl,@lattner,@nlewycky

Extended Description

Certain transformations, like tail-duplication (Bug 174) and the correlated
expression elimination pass, fundamentally need to make arbitrary changes to the
CFG AND update the SSA form of expressions. To do this, they need to update
dominators and dominator frontiers as they change the CFG.

Basically the dominator information passes need an 'addEdge/removeEdge'
interface that clients can use to incrementally update the dominator
information. There is a paper that describes how to do this:

http://citeseer.nj.nec.com/sreedhar94efficient.html

... someone should implement it.

Given this functionality, many other transformations would also be able to
incrementally update dominator information, instead of recalculating it, which
would speed up the optimizer as well.

-Chris
@lattner
Copy link
Collaborator Author

lattner commented Feb 26, 2004

Changing all of these bugs who do not have people looking at them to be assigned
to "unassignedbugs", indicating that if someone is feeling ambitious, they can
take ownership of the bug.

If I stole your bug, and you still want it, feel free to take ownership back.

-Chris

3 similar comments
@lattner
Copy link
Collaborator Author

lattner commented Feb 26, 2004

Changing all of these bugs who do not have people looking at them to be assigned
to "unassignedbugs", indicating that if someone is feeling ambitious, they can
take ownership of the bug.

If I stole your bug, and you still want it, feel free to take ownership back.

-Chris

@lattner
Copy link
Collaborator Author

lattner commented Feb 26, 2004

Changing all of these bugs who do not have people looking at them to be assigned
to "unassignedbugs", indicating that if someone is feeling ambitious, they can
take ownership of the bug.

If I stole your bug, and you still want it, feel free to take ownership back.

-Chris

@lattner
Copy link
Collaborator Author

lattner commented Feb 26, 2004

Changing all of these bugs who do not have people looking at them to be assigned
to "unassignedbugs", indicating that if someone is feeling ambitious, they can
take ownership of the bug.

If I stole your bug, and you still want it, feel free to take ownership back.

-Chris

@nlewycky
Copy link
Contributor

I would also like this for my pass in llvm/llvm-bugzilla-archive#807 .

Unfortunately, my compiler theory is no match for this paper. What does it mean
on page 14:
"2. PseudoAffected: This set consists of any /proper/ descendant of a
PossiblyAffected node." Assuming that I have the list of PossiblyAffected
nodes, what are the proper descendants? Every node in the sub-tree?

@nlewycky
Copy link
Contributor

it compiles, but i've never run it.
I tried to implement it and this is as far as I got.

@llvmbot
Copy link
Member

llvmbot commented Apr 11, 2007

Nick,

If you're still interested in this, there's an expanded/clearer version of the
paper at:

http://citeseer.ist.psu.edu/sreedhar95incremental.html

Otherwise, I might tackle this next time I need something to do.

--Owen

@lattner
Copy link
Collaborator Author

lattner commented Apr 15, 2007

Step #​1 complete: Owen removed idom.

@lattner
Copy link
Collaborator Author

lattner commented Oct 10, 2009

Implemented here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20091005/088600.html

Jump threading switched to use it here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20091005/088601.html

@llvmbot
Copy link
Member

llvmbot commented Oct 11, 2009

Chris, I don't think that solves all of what this bug asks for. We're still lacking a generc dominato r update function.

@lattner
Copy link
Collaborator Author

lattner commented Oct 11, 2009

As originator of the bug, I know what it was about. :) Updating domtree wasn't the point, that was seen as a way to get to SSA updates.

@llvmbot
Copy link
Member

llvmbot commented Oct 11, 2009

Would it be worthwhile to split dominator updates into a new PR? It still seems like a useful feature.

@lattner
Copy link
Collaborator Author

lattner commented Oct 11, 2009

Why? If it existed, we still wouldn't use it in the standard optimizer (too slow). Lets wait until there is an actual reason to have it.

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 1, 2021
searlmc1 pushed a commit to ROCm/llvm-project that referenced this issue Feb 10, 2025
@ronlieb
Merge pull request llvm#589 from AMD-Lightning-Internal/upstream_merg…
Loading
Loading status checks…
3e78303 
…e_202502101140

merge main into amd-staging
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@nlewycky @lattner @llvmbot