Page MenuHomePhabricator

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

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

Details

Summary

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
cases.

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.

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!

include/llvm/Transforms/Utils/MemorySSA.h
572

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

745

SmallPtrSet?

749

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

760

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

lib/Transforms/Utils/MemorySSA.cpp
2396

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

2397

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

2422

Useless braces

2437

Incomplete comment? (And below * 2)

2475

Naming nit: MemorySSAUpdater::getLastDefIn?

2559

"we generate figure out"?

2616

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

2650

if (auto *Defs = ...)

2655

"access, make"

unittests/Transforms/Utils/MemorySSA.cpp
277

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.

include/llvm/Transforms/Utils/MemorySSA.h
741–742

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?

unittests/Transforms/Utils/MemorySSA.cpp
671

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.
include/llvm/Transforms/Utils/MemorySSA.h
741–742

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

lib/Transforms/Utils/MemorySSA.cpp
2475

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.

2616

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

unittests/Transforms/Utils/MemorySSA.cpp
277

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.

include/llvm/Transforms/Utils/MemorySSA.h
756

nit: "just call moveBefore or moveAfter with"

lib/Transforms/Utils/MemorySSA.cpp
2711

Please remove parens

2715

Please remove parens

2715

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() {
entry:
  ; 1 = MemoryDef
  %a = call i8* @bar()
  %b = bitcast i8* %a to i32*
  br i1 undef label %lbb, label %lbc

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

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.

2718

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?

2743

Please remove the extra parens

davide accepted this revision.Jan 27 2017, 3:05 PM
davide added inline comments.
include/llvm/Transforms/Utils/MemorySSA.h
741–742

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.
lib/Transforms/Utils/MemorySSA.cpp
2715

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.

2718

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
lib/Transforms/Utils/MemorySSA.cpp
2718

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

This revision was automatically updated to reflect the committed changes.