This is an archive of the discontinued LLVM Phabricator instance.

[IR] De-virtualize ~Value to save a vptr
ClosedPublic

Authored by rnk on Mar 22 2017, 2:32 PM.

Details

Summary

Implements PR889

Removing the virtual table pointer from Value saves 1% of RSS when doing
LTO of llc on Linux. The impact on time was positive, but too noisy to
conclusively say that performance improved. Here is a link to the
spreadsheet with the original data:

https://docs.google.com/spreadsheets/d/1F4FHir0qYnV0MEp2sYYp_BuvnJgWlWPhWOwZ6LbW7W4/edit?usp=sharing

This change makes it invalid to directly delete a Value, User, or
Instruction pointer. Instead, such code can be rewritten to a null check
and a call Value::deleteValue(). Value objects tend to have their
lifetimes managed through iplist, so for the most part, this isn't a big deal.
However, there are some places where
LLVM deletes values, and those places had to be migrated to deleteValue.
I have also created llvm::unique_value, which has a custom deleter, so
it can be used in place of std::unique_ptr<Value>.

I had to add the "ValueCallbacks" escape hatch for MemorySSA, which
derives from User outside of lib/IR. Code in IR cannot include MemorySSA
headers or call the MemoryAccess object destructors without introducing
a circular dependency, so we need some level of indirection.
Unfortunately, no class derived from User may have any virtual methods,
because adding a virtual method would break User::getHungOffOperands(),
which assumes that it can find the use list immediately prior to the
User object. I've added a static_assert to the appropriate OperandTraits
templates to help people avoid this trap.

Event Timeline

rnk created this revision.Mar 22 2017, 2:32 PM

Thanks for working on this!

I think we need some way of checking this at compile time, because developers are going to trip over this

#define NO_VIRTUALS_ALLOWED(cls) static_assert(!std::is_polymorphic<cls>::value, #cls " is not allowed to have virtual methods");

class Value /* ... */ { /* ... */ };
NO_VIRTUALS_ALLOWED(Value);

class BasicBlock : public Value, /* ... */ { /* ... */ };
NO_VIRTUALS_ALLOWED(BasicBlock);

might be a good starting point. Can't think of a way to make it automagically apply to subclasses, though.

include/llvm/IR/DerivedUser.h
28 ↗(On Diff #92713)

"instead inherit from DerivedUser instead"?

rnk updated this revision to Diff 94570.Apr 7 2017, 2:55 PM
  • rebase
rnk edited the summary of this revision. (Show Details)May 11 2017, 2:46 PM
rnk added reviewers: pete, dberlin.
rnk updated this revision to Diff 98681.May 11 2017, 2:48 PM
  • rebase after committing GlobalValue and TerminatorInst changes

PTAL, I think this is the final form of this patch. I couldn't come up with a cleaner way to allow MemorySSA to retain it's virtual methods. Trust me, I tried.

Then again, extending the Value/User hierarchy isn't really a supported use case. If we want to let people reuse the use/def list machinery with less work, we can tackle that separately from this change.

pcc added inline comments.May 11 2017, 2:54 PM
llvm/include/llvm/IR/DerivedUser.h
42

Can "ValueCallbacks" just be a function pointer?

rnk added inline comments.May 11 2017, 3:00 PM
llvm/include/llvm/IR/DerivedUser.h
42

It could be, but I had the idea that MemorySSA might prefer to add virtual methods here instead of doing switch dispatch like I ended up doing. Whatever dannyb/gbiv prefer, I'll do that.

llvm/include/llvm/IR/DerivedUser.h
42

We don't have that many virtual methods in Memory*, so I'd be perfectly happy with switch dispatch. If that changes, looks straightforward to swap back to this approach.

(If we take the ValueCallbacks route, though, please make deleteValue and VCallbacks const)

chandlerc requested changes to this revision.May 16 2017, 7:04 PM

Have you checked Polly and Clang for changes needed there? Detailed comments below.

llvm/include/llvm/IR/DerivedUser.h
10–14

Given that this header just defines a class, maybe just move all the comments to the class doxygen and nuke the intro section?

27–29

I'd personally like some moderately strong discouragement of using this and indicate that if we find another way to extend use/def chains it may go away. I just don't want folks outside the project designing things on top of this extension point and then being in a really bad spot if we ever get rid of it.

42

+1 for me FWIW.

llvm/include/llvm/IR/GlobalValue.h
179

Redundant public.

llvm/include/llvm/IR/Instruction.def
192–193

I guess you should match the weird formatting of this file for this patch. We should probably come back and clean up all of this formatting ,but seems weird to deviate here.

llvm/include/llvm/IR/Instruction.h
59

Make this a doxygen comment?

llvm/include/llvm/IR/User.h
96

Add whitespace before the protected?

llvm/include/llvm/IR/Value.def
61

Leave a FIXME comment here to document that this isn't ideal but we don't have any better idea?

llvm/include/llvm/IR/Value.h
209–214

Move this up to the protected region with the constructor?

Also, the trailing comment doesn't seem to add value at this point.

216

No blank line here.

This revision now requires changes to proceed.May 16 2017, 7:04 PM
rnk marked 11 inline comments as done.May 17 2017, 12:18 PM
rnk added inline comments.
llvm/include/llvm/IR/Instruction.h
59

The intention of these trailing comments is to make it so they show up in diagnostic notes when users try to delete a Value*. It looks like this:

C:\src\llvm-project\llvm\unittests\IR\InstructionsTest.cpp(410,10):  error: calling a protected destructor of class 'llvm::Instruction'
  delete I;
         ^
C:\src\llvm-project\llvm\include\llvm/IR/Instruction.h(59,3):  note: declared protected here
  ~Instruction(); // Use deleteValue() to delete a generic Instruction.
  ^
1 error generated.
llvm/include/llvm/IR/User.h
96

Done, I also added the trailing comment so it shows up in notes. People don't often delete a User directly, though.

llvm/include/llvm/IR/Value.h
209–214

See example where it shows up in diagnostic notes but the doxygen one doesn't.

rnk updated this revision to Diff 99337.May 17 2017, 12:19 PM
rnk edited edge metadata.
rnk marked an inline comment as done.
  • Address Chandler's comments
rnk added a comment.May 17 2017, 12:20 PM

Have you checked Polly and Clang for changes needed there? Detailed comments below.

check-polly and check-clang pass for me.

chandlerc accepted this revision.May 17 2017, 2:30 PM

LGTM with some nits! Totally awesome.

llvm/include/llvm/IR/Instruction.h
54–58

Sink this public region down to coalesce it with the one right below the protected detsructor?

59

Neat!

It'd be awesome if there were a non-comment way of doing this, but hey... =]

llvm/include/llvm/IR/User.h
96

Maybe move the public constructor above down so that we don't have the 2 public regions split by a protected one?

llvm/include/llvm/IR/Value.h
208

Redundant public:.

This revision is now accepted and ready to land.May 17 2017, 2:30 PM
rnk marked 3 inline comments as done.May 18 2017, 9:54 AM

Thanks! Time to find out if this breaks something. :)

rnk updated this revision to Diff 99451.May 18 2017, 9:56 AM
  • Adjust access specifiers
This revision was automatically updated to reflect the committed changes.