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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Adam Nemet via llvm-dev
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
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

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

Adam Nemet via llvm-dev
On 3 May 2018, at 22:09, David Zarzycki via llvm-dev <[hidden email]> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

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

Adam Nemet via llvm-dev


> On May 4, 2018, at 4:34 AM, David Chisnall <[hidden email]> wrote:
>
> On 3 May 2018, at 22:09, David Zarzycki via llvm-dev <[hidden email]> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

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

Adam Nemet via llvm-dev
In reply to this post by Adam Nemet via llvm-dev
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 <[hidden email]> 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
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev