Page MenuHomePhabricator

Introduce a basic MemorySSA updater, that supports insertDef and insertUse operations.

Authored by dberlin on Jan 23 2017, 12:48 PM.



This creates a basic MemorySSA updater that handles arbitrary insertion of uses and defs into MemorySSA.
I will extend it to handle moves (the current splice API).

It can be made to handle arbitrary control flow changes.
Currently, it uses the same updater algorithm from D28934.

The main difference is because MemorySSA is single variable, we have
the complete def and use list, and don't need anyone to give it to us
as part of the API. We also have to rename stores below us in some

If we go that direction in that patch, i will merge all the updater
implementations (using an updater_traits or something to provide the
get* functions we use, called read*/write* in that patch).

Sadly, the current SSAUpdater algorithm is way too slow to use for
what we are doing here.

I have updated the tests we have to basically build memoryssa
incrementally using the updater api, and make sure it still comes out
the same.

I have also added a fairly complex testcase, but a few more coming.

Diff Detail


Event Timeline

dberlin created this revision.Jan 23 2017, 12:48 PM
bryant added a subscriber: bryant.Jan 24 2017, 1:29 PM
  • Update formatting

Mostly just nits; I'm assuming that the algorithm in the paper is correct, and I can't immediately see any issues with the logic here.

Thanks for the patch!

572 ↗(On Diff #85696)

"since iplist's own if you don't change the traits" sounds weird to me

749 ↗(On Diff #85696)

Can this just take a Def in the first place (same for the function below, except Use)

746 ↗(On Diff #85447)


761 ↗(On Diff #85447)

Was this a typo? If not, the AfterUs seems redundant unless it's from the paper you referenced or something.

2437 ↗(On Diff #85696)

Incomplete comment? (And below * 2)

2475 ↗(On Diff #85696)

Naming nit: MemorySSAUpdater::getLastDefIn?

2559 ↗(On Diff #85696)

"we generate figure out"?

2650 ↗(On Diff #85696)

if (auto *Defs = ...)

2655 ↗(On Diff #85696)

"access, make"

2399 ↗(On Diff #85447)

Nit: Since we're doing nothing but returning Result, can this be converted to returning early? (And below)

2400 ↗(On Diff #85447)

else if (!VisitedBlocks.insert(BB))? (will be less sketchy if we swap to early returns)

2425 ↗(On Diff #85447)

Useless braces

2619 ↗(On Diff #85447)

FixupList.append(InsertedPhis.end() - StartingPHISize, InsertedPhis.end());?

277 ↗(On Diff #85447)

Temporary (and below)?

davide added a subscriber: davide.Jan 26 2017, 1:31 PM

I spent a bit of time reviewing this (with particular attention to the marker algorithm) and I think it's correct. Minor comments inline, happy to see this in when George is happy with it.

741–742 ↗(On Diff #85696)

This is just my personal preference, so ignore it if you don't like, but, what about moving the updater to its own separate file?

671 ↗(On Diff #85696)

I assume this #if 0 will go away, right?

dberlin marked 10 inline comments as done.Jan 26 2017, 7:00 PM
dberlin added inline comments.
741–742 ↗(On Diff #85696)

I'll do this as a followup (otherwise it's going to completely screw up the comments here :P)

2475 ↗(On Diff #85696)

I went back and forth on what to call this one.
It used to be named getLastDef or something, but it's really not.
It's the same as the previous two functions, except it starts at the end of the block instead of a memory access.

2619 ↗(On Diff #85447)

thanks, that's the function i was looking for.

277 ↗(On Diff #85447)

Yes, the followup will add the move function

dberlin marked an inline comment as done.
  • Implement MoveBefore.
  • Add moveAfter, refactor to use moveTo internally

Just a few nits. You can consider this a LGTM-with-nits if the concern I raised isn't actually an issue.

770 ↗(On Diff #86013)

nit: "just call moveBefore or moveAfter with"

2729 ↗(On Diff #86013)

Please remove parens

2733 ↗(On Diff #86013)

Please remove parens

2733 ↗(On Diff #86013)

I'm not super familiar with how BB Instruction ordering actually works, so this could totally be a misunderstanding on my part, but I think this might cause issues with operand dominance. Consider:

define void @foo() {
  ; 1 = MemoryDef
  %a = call i8* @bar()
  %b = bitcast i8* %a to i32*
  br i1 undef label %lbb, label %lbc

  ; MemoryUse(1)
  %c = load i32, i32* %b
  br label %lbc

  ret void

updater.moveAfter(Use1, Def1) will make %c dominate %b, since we call TheLoad.moveBefore(EntryBlock, ++TheStore), and ++TheStore == TheBitcast.

Same comment for blocks that only have MemoryPhis, as well.

2736 ↗(On Diff #86013)

Coming into this with no updater-related context outside of this patch, it's mildly surprising to me that MemorySSA's updater moves actual Instructions around in BBs. It makes sense, but can we call that we do this out in the comments, please?

2761 ↗(On Diff #86013)

Please remove the extra parens

davide accepted this revision.Jan 27 2017, 3:05 PM
davide added inline comments.
741–742 ↗(On Diff #85696)

Yeah, feel free to do that in a follow up =)

This revision is now accepted and ready to land.Jan 27 2017, 3:05 PM
dberlin marked 5 inline comments as done.Jan 27 2017, 3:09 PM
dberlin added inline comments.
2733 ↗(On Diff #86013)

Yes, You are correct. It is possible to use moveBefore to generate illegal blocks if you are not careful.
The same is true of basicblock's movebefore.

Essentially, we do what we are told. If you tell us "put this after this def", we put it *right after this def*.

I could change it to also take a basicblock iterator if you are worried we need one.

2736 ↗(On Diff #86013)

We could make it not do that rather than take an iterator above?
Then the user is responsible for ordering it relative to the def.

dberlin added inline comments.Jan 27 2017, 3:25 PM
2736 ↗(On Diff #86013)

i'm definitely going to do this because it simplifies life considerably.

This revision was automatically updated to reflect the committed changes.