thr3ads.net - llvm dev - [llvm-dev] RFC: virtual-like methods via LLVM-style RTTI [May 2018]

If this information is useful, please help other people find it:
Share via:

David Zarzycki via llvm-dev

2018-May-03 21:09 UTC

[llvm-dev] RFC: virtual-like methods via LLVM-style RTTI

Hello,

In an effort to help LLVM-style projects save memory, I’ve been toying with some
macros that provide an alternative to C++ vtables that use LLVM-style RTTI
design patterns instead. Is this something that LLVM or sub-projects think is
worth pursuing? Or are the macros below too ugly/problematic? Feedback would be
appreciated.

Thanks,
Dave




//===- llvm/Support/VTable.h - LLVM-style vtables ---------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file provides LLVM_VIRTUAL() and related macros for creating virtual
// methods that demultiplex via LLVM-style RTTI.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_VTABLE_H
#define LLVM_SUPPORT_VTABLE_H

#include <functional>

namespace llvm {

//===----------------------------------------------------------------------===//
//                   LLVM-style VTable Support macros
//===----------------------------------------------------------------------===//

// Virtual method dispatch via LLVM runtime type information. This approach
// requires a little bit more work than native C++ 'virtual' methods,
but the
// memory savings can be well worth it. On non-PIC x86 systems, the same
// number of instructions are generated. On PIC x86 systems, one additional
// instruction is generated to compute (or load) the pointer to the vtable
// (LEA or MOV respectively), and the compiler is smart enough to hoist the
// LEA/MOV outside of loops and cache the result.
//
// For subclasses, virtual methods are declared like so:
//
//   LLVM_VIRTUAL_THUNK(BaseTy, makeSound)
//   void LLVM_VIRTUAL(makeSound)(int howLoud) { /* normal body */ }
//
// For base classes, one must do a little more work. The simplest case is an
// abstract virtual method in a type called 'Base':
//
//   void LLVM_ABSTRACT_VIRTUAL(BaseTy, makeSound)
//
// And then later in the header file, the vtable definition:
//
// LLVM_ABSTRACT_VIRTUAL_BEGIN(BaseTy, makeSound)
// #define BASE_NODE(Ty, ...) LLVM_ABSTRACT_VIRTUAL_SLOT(Ty, makeSound)
// #include <BaseTy.inc>
// LLVM_ABSTRACT_VIRTUAL_END(getKind())
//
//
// Example:
//
// class Cat {
//   ...
//
//   void LLVM_ABSTRACT_VIRTUAL(Base, makeSound)
//
//   LLVM_BASE_VIRTUAL(Base, getOffspringCount)
//   size_t LLVM_VIRTUAL(getOffspringCount)() const {
//     return 0;
//   }
// };
//
//
// class Lion : public Cat {
//   ...
//
//   LLVM_VIRTUAL_THUNK(Base, makeSound)
//   void LLVM_VIRTUAL(makeSound)() {
//     ...
//   }
//
//   LLVM_VIRTUAL_THUNK(Base, getOffspringCount)
//   size_t LLVM_VIRTUAL(getOffspringCount)() const {
//     ...
//   }
// };


#define LLVM_VIRTUAL_THUNK(Ty, BaseTy, Method) \
  template <typename... Args> \
  static auto _virtual_##Method(BaseTy *b, Args... args) -> auto { \
    return static_cast<Ty*>(b) \
      ->_virtualbody_##Method(std::forward<Args>(args)...); \
  }

#define LLVM_VIRTUAL(Method) \
  __attribute__((always_inline)) _virtualbody_##Method

#define LLVM_ABSTRACT_VIRTUAL(BaseTy, Method) \
  __attribute__((noreturn)) \
  LLVM_VIRTUAL(Method)(...) { \
    llvm_unreachable("Unhandled LLVM-virtual method"); \
  } \
  template <typename... Args> \
  auto Method(Args... args) -> auto; \
  LLVM_VIRTUAL_THUNK(BaseTy, BaseTy, Method)

#define LLVM_BASE_VIRTUAL(BaseTy, Method) \
  template <typename... Args> \
  auto Method(Args... args) -> auto; \
  LLVM_VIRTUAL_THUNK(BaseTy, BaseTy, Method)

#define LLVM_ABSTRACT_VIRTUAL_BEGIN(BaseTy, Method) \
  template <typename... Args> \
  auto BaseTy::Method(Args... args) -> auto { \
    static const decltype(&BaseTy::_virtual_##Method<Args...>)
vtable[] = {

#define LLVM_ABSTRACT_VIRTUAL_SLOT(Ty, Method) \
      &Ty::_virtual_##Method<Args...>,

#define LLVM_ABSTRACT_VIRTUAL_END(GetKind) \
    }; \
    return vtable[GetKind](this, std::forward<Args>(args)...); \
  }

} // end namespace llvm

#endif // LLVM_SUPPORT_VTABLE_H

David Chisnall via llvm-dev

2018-May-04 08:34 UTC

head link

[llvm-dev] RFC: virtual-like methods via LLVM-style RTTI

On 3 May 2018, at 22:09, David Zarzycki via llvm-dev <llvm-dev at
lists.llvm.org> wrote:> 
> Hello,
> 
> In an effort to help LLVM-style projects save memory, I’ve been toying with
some macros that provide an alternative to C++ vtables that use LLVM-style RTTI
design patterns instead. Is this something that LLVM or sub-projects think is
worth pursuing? Or are the macros below too ugly/problematic? Feedback would be
appreciated.
It would help to have a little bit of information about how you expect this to
work.  LLVM-style RTTI works by adding a method to the vtable that returns the
kind of the instance and can be used with templates to allow casting.  If you
retain this, then every object still needs the vtable pointer, which appears to
be what you are trying to avoid.  If you don’t have this, then how do you expect
to be able to differentiate instance types?

From your code, it looks as if you’re implementing an inverted vtable structure,
where there is a per-method vtable with per-subclass entries, rather than a
traditional vtable where you have one per class and per-method entries.  Your
total vtable space goes from being NxM to being MxN, which doesn’t sound like an
improvement.  This kind of approach is generally popular in late-bound dynamic
languages with duck typing where you have a lot of methods with few overrides
and it’s worth having a slightly more expensive lookup to have a sparser
structure than the full NxM matrix.  It doesn’t seem appropriate here.

David

David Zarzycki via llvm-dev

2018-May-04 10:49 UTC

head link

[llvm-dev] RFC: virtual-like methods via LLVM-style RTTI

> On May 4, 2018, at 4:34 AM, David Chisnall <David.Chisnall at
cl.cam.ac.uk> wrote:
> 
> On 3 May 2018, at 22:09, David Zarzycki via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>> 
>> Hello,
>> 
>> In an effort to help LLVM-style projects save memory, I’ve been toying
with some macros that provide an alternative to C++ vtables that use LLVM-style
RTTI design patterns instead. Is this something that LLVM or sub-projects think
is worth pursuing? Or are the macros below too ugly/problematic? Feedback would
be appreciated.
> 
> It would help to have a little bit of information about how you expect this
to work.  LLVM-style RTTI works by adding a method to the vtable that returns
the kind of the instance and can be used with templates to allow casting.  If
you retain this, then every object still needs the vtable pointer, which appears
to be what you are trying to avoid.  If you don’t have this, then how do you
expect to be able to differentiate instance types?
> 
> From your code, it looks as if you’re implementing an inverted vtable
structure, where there is a per-method vtable with per-subclass entries, rather
than a traditional vtable where you have one per class and per-method entries. 
Your total vtable space goes from being NxM to being MxN, which doesn’t sound
like an improvement.  This kind of approach is generally popular in late-bound
dynamic languages with duck typing where you have a lot of methods with few
overrides and it’s worth having a slightly more expensive lookup to have a
sparser structure than the full NxM matrix.  It doesn’t seem appropriate here.
Hi David,

The motivating example was/is clang’s Decl type hierarchy. It uses both C++
vtables and LLVM-style getKind()/classof() (which are non-virtual and don’t need
to be virtual). In practice, this represents two RTTI systems: one for virtual
dispatch and one for casting. This patch is about using the LLVM-style getKind()
logic to implement virtual dispatch, thus saving sizeof(void*) per allocated
Decl node, which can add up very, very quickly.

The other motivating reason for this patch is that C++ vtables prevent certain
kinds of object layout optimizations. For example, I could make clang about one
to two percent faster by storing the DeclContext at fixed negative offset rather
than a per-class positive offset. This negative-offset DeclContext optimization
is precedented too (see the Swift compiler DeclContext).

Dave

Reid Kleckner via llvm-dev

2018-May-10 22:21 UTC

head link

[llvm-dev] RFC: virtual-like methods via LLVM-style RTTI

If you can use this to clean up things like Value::deleteValue, that would
be amazing. Go for it. :)

On Thu, May 3, 2018 at 2:09 PM David Zarzycki via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello,
>
> In an effort to help LLVM-style projects save memory, I’ve been toying
> with some macros that provide an alternative to C++ vtables that use
> LLVM-style RTTI design patterns instead. Is this something that LLVM or
> sub-projects think is worth pursuing? Or are the macros below too
> ugly/problematic? Feedback would be appreciated.
>
> Thanks,
> Dave
>
>
>
>
> //===- llvm/Support/VTable.h - LLVM-style vtables ---------------*- C++
> -*-===//
> //
> //                     The LLVM Compiler Infrastructure
> //
> // This file is distributed under the University of Illinois Open Source
> // License. See LICENSE.TXT for details.
> //
>
>
//===----------------------------------------------------------------------===//
> //
> // This file provides LLVM_VIRTUAL() and related macros for creating
> virtual
> // methods that demultiplex via LLVM-style RTTI.
> //
>
>
//===----------------------------------------------------------------------===//
>
> #ifndef LLVM_SUPPORT_VTABLE_H
> #define LLVM_SUPPORT_VTABLE_H
>
> #include <functional>
>
> namespace llvm {
>
>
>
//===----------------------------------------------------------------------===//
> //                   LLVM-style VTable Support macros
>
>
//===----------------------------------------------------------------------===//
>
> // Virtual method dispatch via LLVM runtime type information. This approach
> // requires a little bit more work than native C++ 'virtual'
methods, but
> the
> // memory savings can be well worth it. On non-PIC x86 systems, the same
> // number of instructions are generated. On PIC x86 systems, one additional
> // instruction is generated to compute (or load) the pointer to the vtable
> // (LEA or MOV respectively), and the compiler is smart enough to hoist the
> // LEA/MOV outside of loops and cache the result.
> //
> // For subclasses, virtual methods are declared like so:
> //
> //   LLVM_VIRTUAL_THUNK(BaseTy, makeSound)
> //   void LLVM_VIRTUAL(makeSound)(int howLoud) { /* normal body */ }
> //
> // For base classes, one must do a little more work. The simplest case is
> an
> // abstract virtual method in a type called 'Base':
> //
> //   void LLVM_ABSTRACT_VIRTUAL(BaseTy, makeSound)
> //
> // And then later in the header file, the vtable definition:
> //
> // LLVM_ABSTRACT_VIRTUAL_BEGIN(BaseTy, makeSound)
> // #define BASE_NODE(Ty, ...) LLVM_ABSTRACT_VIRTUAL_SLOT(Ty, makeSound)
> // #include <BaseTy.inc>
> // LLVM_ABSTRACT_VIRTUAL_END(getKind())
> //
> //
> // Example:
> //
> // class Cat {
> //   ...
> //
> //   void LLVM_ABSTRACT_VIRTUAL(Base, makeSound)
> //
> //   LLVM_BASE_VIRTUAL(Base, getOffspringCount)
> //   size_t LLVM_VIRTUAL(getOffspringCount)() const {
> //     return 0;
> //   }
> // };
> //
> //
> // class Lion : public Cat {
> //   ...
> //
> //   LLVM_VIRTUAL_THUNK(Base, makeSound)
> //   void LLVM_VIRTUAL(makeSound)() {
> //     ...
> //   }
> //
> //   LLVM_VIRTUAL_THUNK(Base, getOffspringCount)
> //   size_t LLVM_VIRTUAL(getOffspringCount)() const {
> //     ...
> //   }
> // };
>
>
> #define LLVM_VIRTUAL_THUNK(Ty, BaseTy, Method) \
>   template <typename... Args> \
>   static auto _virtual_##Method(BaseTy *b, Args... args) -> auto { \
>     return static_cast<Ty*>(b) \
>       ->_virtualbody_##Method(std::forward<Args>(args)...); \
>   }
>
> #define LLVM_VIRTUAL(Method) \
>   __attribute__((always_inline)) _virtualbody_##Method
>
> #define LLVM_ABSTRACT_VIRTUAL(BaseTy, Method) \
>   __attribute__((noreturn)) \
>   LLVM_VIRTUAL(Method)(...) { \
>     llvm_unreachable("Unhandled LLVM-virtual method"); \
>   } \
>   template <typename... Args> \
>   auto Method(Args... args) -> auto; \
>   LLVM_VIRTUAL_THUNK(BaseTy, BaseTy, Method)
>
> #define LLVM_BASE_VIRTUAL(BaseTy, Method) \
>   template <typename... Args> \
>   auto Method(Args... args) -> auto; \
>   LLVM_VIRTUAL_THUNK(BaseTy, BaseTy, Method)
>
> #define LLVM_ABSTRACT_VIRTUAL_BEGIN(BaseTy, Method) \
>   template <typename... Args> \
>   auto BaseTy::Method(Args... args) -> auto { \
>     static const decltype(&BaseTy::_virtual_##Method<Args...>)
vtable[] = {
>
> #define LLVM_ABSTRACT_VIRTUAL_SLOT(Ty, Method) \
>       &Ty::_virtual_##Method<Args...>,
>
> #define LLVM_ABSTRACT_VIRTUAL_END(GetKind) \
>     }; \
>     return vtable[GetKind](this, std::forward<Args>(args)...); \
>   }
>
> } // end namespace llvm
>
> #endif // LLVM_SUPPORT_VTABLE_H
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180510/02237f9a/attachment.html>

llvm dev - May 2018 - RFC: virtual-like methods via LLVM-style RTTI

[llvm-dev] RFC: virtual-like methods via LLVM-style RTTI

[llvm-dev] RFC: virtual-like methods via LLVM-style RTTI

[llvm-dev] RFC: virtual-like methods via LLVM-style RTTI

[llvm-dev] RFC: virtual-like methods via LLVM-style RTTI