Eliminate Virtual Methods In VMCore To Make Value Objects Smaller

[llvmbot]

Bugzilla Link	889
Resolution	FIXED
Resolved on	May 18, 2017 10:42
Version	1.0
OS	All
Blocks	llvm/llvm-project#760
Reporter	LLVM Bugzilla Contributor
CC	@gburgessiv,@jayfoad,@nlewycky,@rnk

Extended Description

After llvm/llvm-project#1164 is fixed, the "print" and "dump" methods will be removed from the Value class. This will leave only the destructor as the only virtual method. The destruction hierarchy could be done using the isa facility. Something like:

Value::~Value() { switch (ValKind) { case Constant: Constant::destroythis((Constant*)this); ... }

This has the potential to shrink all VMCore Value objects by 4 bytes (32-bit platform) or 8 bytes (64-bit platform) by removal of the virtual table pointer from the objects.

[rnk]

r303362

[rnk]

New patch based on r298548 (Mar 22 2017): https://reviews.llvm.org/D31261

It's not good to commit as-is, but it's worth experimenting with.

[llvmbot]

The way I see it, anything that subclasses Value should be part of lib/IR.

It should serialize through bitcode and .ll assembly. I figured your predicate info stuff would persist in the IR, and so it makes sense to derive from Value.

The MemorySSA classes appear to represent analysis results, so IMO they shouldn't be Values.

I would agree if the def/use chains were abstracted out of Value.
We'd end up dyn_casting in some more places, but that would be fine.

Note that this was also gone into, in great detail, during the many-month review of MemorySSA, and the conclusion was that making them Value's made sense, in large part, for this reason.

Even though it is a virtual IR, people also wanted the regular IR functions to mostly work on them, and they do, because they are Value's. For example, replaceAllUses works. Weak handles to them work. etc

I argued that if we were going to do that, we should just make it a part of the regular IR. I lost :) The argument against this is the "everything has to keep it up to date" problem. You can't really make it metadata, so either everything updates it (which is GCC's approach), or you keep it virtual. At the time, keeping it up to date all the time would have been harder.

Note that with an updater these days, keeping it up to date all the time is no longer hard. You just hand it anything you moved or inserted, and it'll do the rest.

Besides the def/use chains, what is needed is an easy way, without complex pointer unions and such, to say "i want to map from things that appear in the IR, or the virtual IR, to something"

IE You really need to be able to create a DenseMap<, something> . This is because the whole point of having them is to associate dataflow facts of some sort with them. Having separate mappings everywhere is an even larger mess. I presume that, anything that abstracted out the def-use would suffice for this.

I don't know enough about how they're used to say whether they should have their own def/use chain infrastructure,

This was originally done, and it was roundly viewed as a mess. I'm going to say this would likely be a non-starter, practically.

attempt to use Value's, or if we should abstract our def/use chains out of Value.

I would say the last, if we don't just make it part of the regular IR.

I think if you solved the def-use abstraction issue, i could solve the rest for MemorySSA.

But it's going to look a lot like Value does now, i also suspect.

The TL;DR is Memory* is a Value because it has a legitimate set of needs that Value solves, from def-use chains to mapping, to etc So either we should provide solutions to those use cases, or leave it a Value.

Your second option (give it it's own def-use infrastructure) is basically "let's kick it off the island" because the issues seem hard :)

I would suggest that LLVM would be better off solving these issues, one way or the other (ie abstracting def-uses out of value, or making memoryssa part of the real IR).

As mentioned, i'm possibly about to need to extend value again, because we have no good way of mapping.

In NewGVN, for proper value-pre, and for complete value numbering, we need to be able to produce Value's that don't exist in the IR, but could. We don't want to put them in the IR.

I've tried making instructions that aren't in BB's to represent these, but it fails, pretty miserably. Our instructions can't live outside BB's for very long, even though it looks like they are supposed to (it's optional). This goes pretty deep, too. We expect, literally everywhere, that getParent on an instruction does not return nullptr, even though, again, it's legal.

It's also not even possible to create certain types of instructions without a basic block.

I am going to try hard here to fix all this, but in the end, it may not work.

[rnk]

The way I see it, anything that subclasses Value should be part of lib/IR. It should serialize through bitcode and .ll assembly. I figured your predicate info stuff would persist in the IR, and so it makes sense to derive from Value.

The MemorySSA classes appear to represent analysis results, so IMO they shouldn't be Values. I don't know enough about how they're used to say whether they should have their own def/use chain infrastructure, attempt to use Value's, or if we should abstract our def/use chains out of Value.

[llvmbot]

I

I took a shot at this, but the MemorySSA classes in include/llvm/Transforms/Utils/MemorySSA.h extend Value, and IR can't depend on Transforms. I think the Value hierarchy is intended to be a closed class hierarchy.

Why? I'm about to extend it again, so ...

Are we sure burying subclasses in Transforms/Utils is the right design?

In transforms? No. Making them subclasses of Value? Yes. I'm not opposed to moving them wherever. But either we should make these part of the IR, or accept that our virtual IRs are going to add Value classes and figure out what we want to do with that.

Otherwise, they have to build their own value and use mechanisms, which doesn't actually work in practice. (i explained why, in grave detail, in the predicateinfo review).

[rnk]

I took a shot at this, but the MemorySSA classes in include/llvm/Transforms/Utils/MemorySSA.h extend Value, and IR can't depend on Transforms. I think the Value hierarchy is intended to be a closed class hierarchy. Are we sure burying subclasses in Transforms/Utils is the right design?

[llvmbot]

I haven't stopped working on that patch, I was asked to make more substantial changes and I haven't had the chance to update it. (I just delivered my EuroLLVM talk 40 minutes ago, so I finally will start having time again.)

PseudoSourceValue is allocated out of a global map, that needs to go. This in turn means that we don't always unique the PSVs in the way that some callers expect, callers who put them into maps and expect them to have equal addresses when they're equivalent. I haven't written the relevant FoldingSet logic for it yet, but that's up next.

[llvmbot]

is there still any interest in devirtualizing Value class?

Yes, I think it's still a worthy goal. Nick did some work on this just a few weeks back:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140224/205984. html

Cool. This patch would help a lot. Too bad it didn't landed in repo.

I applied it to trunk and fixed some compilation issues. Would it make sense to start review process one more time?

[jayfoad]

is there still any interest in devirtualizing Value class?

Yes, I think it's still a worthy goal. Nick did some work on this just a few weeks back:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140224/205984.html

Is it all about only Value class or other classes from LLVMCore too?

It's interesting to do it for Value because they're so ubiquitous that the space savings could be significant. I don't know if it's worth doing it for any other classes. Anyway, this Bugzilla is only about Value.

[llvmbot]

Hi,

is there still any interest in devirtualizing Value class? Is it all about only Value class or other classes from LLVMCore too?

I have some ideas on how to resolve problem with printing values from llvmcore and llvmcodegen but don't want to dig into them if there is no need;)

[llvmbot]

Ok, if anyones reading, I can see those points needing fixing before Value becomes fully non-virtual: -devirtualizing of Value::printCustom, easy one I have got patch ready to be submitted to llvm-commit for review -devirtualizing TerminatorInst TerminatorInst::getSuccessorV(unsigned idx) TerminatorInst::getNumSuccessorsV() TerminatorInst::setSuccessorV(unsigned idx, BasicBlock B) -devirtualizing Instruction::clone_impl -devirtualizing Constant Constant::isNullValue() Constant::isNegativeZeroValue() Constant::destroyConstant() Constant::replaceUsesOfWithOnConstant(Value , Value , Use ); -devirtualizing Value destructor, its toughest and might need series of easy to review patches to make sure everything but no more is covered.

Shall I file separate bugs for those (blocking this one) and if yes, shall they be method or class based?

[llvmbot]

Hehe, sorry missed the discussion between Jay and Gordon. Actually yes Gordon is right, the target for this task seems to me to carry two conflicting goals. Those are two funny sides of virtual destructors versus typenum hierarchy of data structures. First situation hides from base knowledge about subclasses and modules which use them at expense of mythical vftable field, second one couples them tighter together as a bunch in which base knows of all others or at least of leaf classes (with regard to construct-/destructability). Pretty interesting discussion with unobvious conclusion (at least for my humble self).

[llvmbot]

brief solution, accept comments, seems to work for me ;-) Hmm, went back through this, seems no clear solution yet. Might be not 100% ellegant, but works pretty fine:

cons: -needs to destroy members by hand -needs outter deleter who knows all derivatives leaf and inbetweens -enum ty knows all leaf classes as well as inbetweens -needs priv deleters who emulate destructors

pros: -doesnt use vfuncs

Best wishes, pawel

[llvmbot]

Devirtualizing an algorithm depends on the Value subclasses being closed relative to that algorithm; if that's not the case, then devirtualization cannot be applied except in special cases (e.g., where unknown subclasses can be treated as an 'everything else' group).

It is possible to extend the class hierarchy and then only invoke similarly extended algorithms. For instance: CodeGen could provide printCustom_CodeGen(), which handles CodeGen value types, and dispatches other value types to printCustom() from VMcore. So long as it can be provided that printCustom() from VMcore is never invoked on a CodeGen extended Value.

The issue here is ensuring that instances from the extended class hierarchy are never passed to algorithms which are not prepared for them. This is very difficult to provide for the destruction algorithm in particular.

To avoid the above landmines, the safest approaches would be to (1.) not attempt this optimization or (2.) move all subclasses of Value into VMcore. Thus, the class hierarchy becomes closed relative to all algorithms.

[jayfoad]

I'm struggling with this because Value, which is in the LLVMCore library, has a subclass PseudoSourceValue, which is in LLVMCodeGen. Any attempt to devirtualize a method like Value::printCustom(), which has an implementation in PseudoSourceValue, seems doomed to create a dependency from LLVMCore to LLVMCodeGen.

Anyone have any bright ideas what to do about this? Thanks.

[lattner]

hi Gordon, this has been on my todo list for awhile, but I think it makes sense to wait until after 2.2 branches for this. Can you please ping me after 2.2 branches? Thanks.

[llvmbot]

destroy.patch Well, here's part of it, hiding the polymorphic constructors. I only hid the abstract destructors; 'delete' is safe on concrete subclasses. The remaining increments would be to:

2. Extend InstrVisitor to dispatch over any Value.
3. Convert Value::destroy to use the dispatcher. 4...n. Devirtualize other methods. n+1. Remove the 'virtual' from ~Value.

Some care needs to be taken since there are Value subclasses not linked into VMCore. (They're in the bitreader and parser.) I think there's nothing here which prevents those, so long as they're directly disposed of by their users.

Probably not worth committing this unless and until the vtable can actually be dropped; it's pointless complexity otherwise.

[lattner]

I think this is a good solution. One minor issue is that the dtor still needs to be marked virtual to avoid tons of GCC warnings. It will be slightly odd to change "delete X"; into X->destroy(), but it seems reasonable to do it. Many "deletions" of objects are implicit through calls like eraseFromParent() anyway, so this seems very reasonable.

[llvmbot]

The approach proposed when this PR was opened is unworkable; when ~Value is invoked, the subclass destructors have already been invoked.

A viable approach might be to protect the Value destructor itself and then invoke the leaf class destructors by hand. For instance:

• protected:
• ~Value();

• public:

• virtual ~Value();
• void destruct() {
• if (Foo* X = dyn_cast(this)) delete X;
• else if (Bar* X = dyn_cast(this)) delete X;
• else if (Baz* X = dyn_cast(this)) delete X;
• else assert(0 && "Unknown Value subclass destructed!");
• }

This requires converting every call to any polymorphic destructor in the Value hierarchy into 'V->destruct()', but I don't believe it suffers any fundamental problems.

[lattner]

that sounds reasonable!

[llvmbot]

What do you mean?

Ok, I am half way done with the changelist for that one, but it seems to fix that one, the definitions of classes that are inherited from Value need to be visible from Value::~Value declaration. All goes fine for all classes except for GetElementPtrConstantExpr whose definition is private to Constants.cpp and thus not visible from Value.cpp. The solution I can see is to move the declaration of GetElementPtr class from Constants.cpp to Constants.h sacrificing the private scope of its declaration but having its destroythis declaration visible from Value.cpp.

[lattner]

What do you mean?

[llvmbot]

This one seems to need to move the definition of GetElementPtrConstantExpr from Constants.cpp (where its defined private per file) to the Constants.h to publish the destroythis method definition. Also please note that Value::SubclassID rather than ValueKind (legacy name prolly) will be used for type checking.

[lattner]

Fixing this would have a high impact on darwin. There, each basic block is 36 bytes which is rounded to 48 by malloc. As such, eliminating the vtable (or any other field) would make basic blocks 33% smaller (48->32 bytes).

-Chris

[llvmbot]

assigned to @rnk