This is an archive of the discontinued LLVM Phabricator instance.

MemorySSA: Link all defs together into an intrusive defslist, to make updater easier
ClosedPublic

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

Details

Summary

This is the first in a series of patches to add a simple, generalized updater to MemorySSA.

For MemorySSA, every def is may-def, instead of the normal must-def.
(the best way to think of memoryssa is "everything is really one variable, with different versions of that variable at different points in the program).
This means when updating, we end up having to do a bunch of work to touch defs below and above us.

In order to support this quickly, i have ilist'd all the defs for each block. ilist supports tags, so this is quite easy. the only slightly messy part is that you can't have two iplists for the same type that differ only whether they have the ownership part enabled or not, because the traits are for the value type.

The verifiers have been updated to test that the def order is correct.

Event Timeline

dberlin created this revision.Jan 23 2017, 12:15 PM
  • Update with more changes from my branch. SpliceAbove is completely broken right now for defs spliced into blocks only with uses, as it does not update downards. I've disabled the test because i'll delete the API as part of the updater

An example where spliceabove is broken:

MemoryUse(0)
use(a)
2= MemoryDef(1)
store b
3 = MemoryDef(2)
store a

Splice store a above use a produces:

3 = MemoryDef(0)
store a
MemoryUse(3)
use(a)
2= MemoryDef(1)
store b

This would work in SSA, because you would just have two variables live at the same time.
However, it does not work for MemorySSA, because only one variable may be live at a time, and therefore, you need to update downwards as well.

The only cases where the effects are truly local is when you splice into the middle of a block that has defs above or below you.

Thanks for the patch! The overall approach here seems solid to me.

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

I dunno how cluttered llvm:: is with random pass/analysis-specific things, but it may be nice to scope these somehow (e.g. in a MSSAHelpers struct or namespace or ...)

573

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

689

Less newlines, please

700

Can this just be a map of const BasicBlock * to unique_ptr<struct { AccessList; DefsList; }> (excuse the not-actual-c++)? Looks like we look both up together a lot, and their lifetimes are sorta-related.

(If it ends up being a big refactor, I'm fine if we do this as a follow-up)

lib/Transforms/Utils/MemorySSA.cpp
1523

Nit: if we're not going to "cache" our old value, I think this can can be sunk to the if.

1533

InsertIntoDef = true

1582

It looks like we have this pattern:

void foo(MemoryAccess *MA) {
  getOrCreateAccessList(MA->getBlock())->add_thing(MA);
  if (!isa<MemoryUse>(MA)) {
    getOrCreateDefsList(MA->getBlock())->add_thing(MA);
  }
}
// Where add_thing is one of {insert, push_back, push_front}.

a lot. Can we maybe factor that out into a insertMemoryAccessBefore/insertMemoryAccessAfter(AccessList::iterator, MemoryAccess *) thing that handles the DefList bits for us?

1613

Looks like we put Phis in this list, too. Is this supposed to push Defs in front of phis?

1614

Please delete this newline (and below)

1642

Is Defs->end() correct here? What if I insert a store before the MemoryUse in

define void @foo() {
  %1 = alloca i8
  ; MemoryUse(liveOnEntry)
  %2 = load i8, i8* %1
  ; 1 = MemoryDef(liveOnEntry)
  store i8 0, i8* %1
}

?

1660

Please remove the extra parens

1661

Same "is Defs->end() correct?" comment

1927

Please remove the extra parens

2384

Is this from clang-format?

unittests/Transforms/Utils/MemorySSA.cpp
488

I'm assuming this is temporary

dberlin marked 12 inline comments as done.Jan 25 2017, 5:03 AM
dberlin added inline comments.
include/llvm/Transforms/Utils/MemorySSA.h
114

Fixed :)

573

I tried to rewrite this into something more understandable.

700

So, i'm not strongly opposed, but note:

We currently guarantee two invariants:

  1. If PerBlockAccesses has your block, then the access list for the block is not empty (and vice versa. If it does not have the block, there are no accesses)
  2. If PerBlockDefs has your block, then the defs list for the block is not empty.

If we put them both together, then obviously we can still maintain invariant 1, but we will break invariant 2.

Breaking that invariant means things will now have to check that the defs list is not null everywhere.

Personally, i don't think it's worth it, but happy to hear another opinion :)
(and obviously, happy to document these invariants)

lib/Transforms/Utils/MemorySSA.cpp
1523

Fixed. We now cache the old value, so we don't do a lookup for every def.

1582

You can't use the AccessList iterator, but we can at least create two helpers

1613

No, fixed.

1642

No, it is not correct.
We have to find the nearest def, above or below, and do before/after.
Writing the helper functions made me realize this as well.

We'll do it the slow way first, then we can make it faster if necessary (we have the block numbering, we could make it note which are defs, and then find the nearest def to the access passed here).
Since this is an update API, i doubt it'll be that slow in practice.

2384

Not sure how it got there

unittests/Transforms/Utils/MemorySSA.cpp
488

Yes, it's going away completely as part of the updater update.

dberlin marked 6 inline comments as done.
  • Update for review comments

Note that insertIntoListsBefore requires the block because the iterator may point at the end.

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

I have no idea what happened here, i'll fix (but clang format sorted it into this order)

  • Remove double include of iterator_range.h
  • Update formatting
bryant added a subscriber: bryant.Jan 25 2017, 9:18 AM

An example where spliceabove is broken:

MemoryUse(0)
use(a)
2= MemoryDef(1)
store b
3 = MemoryDef(2)
store a

Splice store a above use a produces:

3 = MemoryDef(0)
store a
MemoryUse(3)
use(a)
2= MemoryDef(1)
store b

This would work in SSA, because you would just have two variables live at the same time.
However, it does not work for MemorySSA, because only one variable may be live at a time, and therefore, you need to update downwards as well.

The only cases where the effects are truly local is when you splice into the middle of a block that has defs above or below you.

This isn't of much consequence, but I wanted to point out that your example already violates the pre-conditions to spliceMemoryAccessAbove:

// \brief Splice \p What to just before \p Where.
//
// In order to be efficient, the following conditions must be met:
//   - \p Where  dominates \p What,
//   - All memory accesses in [\p Where, \p What) are no-alias with \p What.
//
// TODO: relax the MemoryDef requirement on Where.

Still, a generalized updater is way more useful than a tightly-scoped splicing API.

LGTM after 3 more small nits. Thanks again!

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

Much better, thanks! (Looks like clang-format broke the comment, though. :P)

700

Then I'm happy with our current approach. Documenting the invariants would be nice, too. :)

lib/Transforms/Utils/MemorySSA.cpp
1490

insertIntoListsForBlock?

This revision is now accepted and ready to land.Jan 25 2017, 10:39 AM
dberlin marked an inline comment as done.Jan 25 2017, 11:53 AM
dberlin added inline comments.
lib/Transforms/Utils/MemorySSA.cpp
1490

I just used createMemoryPhi instead

lib/Transforms/Utils/MemorySSA.cpp
1490

WFM

This revision was automatically updated to reflect the committed changes.