[移动开发]llvm RTTI（Run-Time Type Identification）

摘要

llvm中大量使用了RTTI技术，但并未直接使用C++内置(built-in)的RTTI(static_cast<>/dynamic_cast<>/const_cast<>/reinterpret_cast<>)，而是自行实现了一套RTTI模板（isa<>/cast<>/dyn_cast<>/isa_and_nonnull<>/cast_or_null<>/dyn_cast_or_null<>）。llvm的RTTI的功能和C++内置的RTTI非常相似，最主要的差异是C++内置的RTTI只能用于有v-table的类，而llvm的dyn_cast没有这个限制。

llvm RTTI API 用法

isa<>/isa_and_nonnull<>：用法非常类似Java中的"instanceof"操作符，例如isa<X>(V)，V可以是指针或引用，假设V的类型为Y，如果Y和模板参数中的类型X满足OOP中"isa"语义，既Y isa X，则返回true，否则返回false。isa_and_nonnull<>和isa<>类似，区别在于允许V为空指针（返回false）。

cast<>/cast_or_null<>：将基类的指针或引用转换为派生类类型，例如cast<Y>(V)，V可以是指针或引用，假设V的类型为X，如果模板参数中的Y和类型X满足OOP中"isa"语义，既Y isa X，则将V转换为Y类型并返回，否则产生断言错误。cast_or_null<>和cast<>类似，区别在于允许V为空指针（返回空指针）。

实际使用代码示例如下：

static bool isLoopInvariant(const Value *V, const Loop *L) {
  if (isa<Constant>(V) || isa<Argument>(V) || isa<GlobalValue>(V))
    return true;

  // Otherwise, it must be an instruction...
  return !L->contains(cast<Instruction>(V)->getParent());
}

dyn_cast<>/dyn_cast_or_null<>：将基类的指针转换为派生类类型，例如dyn_cast<Y>(V)，V是指针，假设V的类型为X，如果模板参数中的Y和类型X满足OOP中"isa"语义，既Y isa X，则将V的类型转换为Y类型并返回，否则返回一个空指针。dyn_cast_or_null<>和dyn_cast<>类似，区别在于允许V为空指针（返回空指针）。

实际使用代码示例如下：

if (auto *AI = dyn_cast<AllocationInst>(Val)) {
  // ...
}

llvm RTTI API实现原理

C++内置的RTTI，通过编译器为支持RTTI的类增加了type_info信息实现。llvm的RTTI实现的思路类似，但是具体的实现方法不同。llvm的RTTI实现主要分为2个部分：类继承树和操作符模板。

llvm RTTI 类继承树

要让类继承树支持llvm RTTI，最常用的方式是：

1. 在基类中定义一个enum：xxKind，枚举所有的派生类类型。
2. 在基类中定义一个private的常量成员：const xxKind Kind。
3. 在基类中定义一个public的成员函数：xxKind getKind() const { return Kind; }。
4. 在继承树中所有实体类的构造函数中将Kind初始化为对应的类型。
5. 在继承树中所有实体类中添加一个classof函数，判断传入参数的类型是否和本类满足isa关系。

示例代码如下，从示例中可以看出，本质上是让每个需要使用llvm RTTI的类，提供了一个classof方法。

 class Shape {
 public:
   /// Discriminator for LLVM-style RTTI (dyn_cast<> et al.)
   enum ShapeKind {
     SK_Square,
     SK_Circle
   };
 private:
   const ShapeKind Kind;
 public:
   ShapeKind getKind() const { return Kind; }

   Shape(ShapeKind K) : Kind(K) {}
   virtual double computeArea() = 0;
 };

 class Square : public Shape {
   double SideLength;
 public:
   Square(double S) : Shape(SK_Square), SideLength(S) {}
   double computeArea() override;

  static bool classof(const Shape *S) {
    return S->getKind() == SK_Square;
  }
 };

 class Circle : public Shape {
   double Radius;
 public:
   Circle(double R) : Shape(SK_Circle), Radius(R) {}
   double computeArea() override;

  static bool classof(const Shape *S) {
    return S->getKind() == SK_Circle;
  }
 };

llvm RTTI 操作符模板

simplify_type<>模板

该模板的主要作用是为llvm中的某些特殊类型化简预留模板特例化的扩展，默认实现不对类型做任何的转换，下面是指针和引用类型的转换结果：

simplify_type<X*>::SimpleType -> X*

simplify_type<const X*>::SimpleType -> const X*

simplify_type<X>::SimpleType -> X

template<typename From> struct simplify_type {
  using SimpleType = From; // The real type this represents...

  // An accessor to get the real value...
  static SimpleType &getSimplifiedValue(From &Val) { return Val; }
};

template<typename From> struct simplify_type<const From> {
  using NonConstSimpleType = typename simplify_type<From>::SimpleType;
  using SimpleType =
      typename add_const_past_pointer<NonConstSimpleType>::type;
  using RetType =
      typename add_lvalue_reference_if_not_pointer<SimpleType>::type;

  static RetType getSimplifiedValue(const From& Val) {
    return simplify_type<From>::getSimplifiedValue(const_cast<From&>(Val));
  }
};

llvm中的特殊类型化简的用法有很多，Use化简为Value的示例如下：

/// Allow clients to treat uses just like values when using
/// casting operators.
template <> struct simplify_type<Use> {
  using SimpleType = Value *;

  static SimpleType getSimplifiedValue(Use &Val) { return Val.get(); }
};
template <> struct simplify_type<const Use> {
  using SimpleType = /*const*/ Value *;

  static SimpleType getSimplifiedValue(const Use &Val) { return Val.get(); }
};

isa<>模板

由如下源码可知，对is<X>(V)，若V为引用类型(如A&/const A&)，则提取出的模板参数Y = A；?若V为指针类型(如A*/const A*/...)，则提取出的模板参数Y = A*/const A*/...。

template <class X, class Y> LLVM_NODISCARD inline bool isa(const Y &Val) {
  return isa_impl_wrap<X, const Y,
                       typename simplify_type<const Y>::SimpleType>::doit(Val);
}

上面讲过，simplify_type的作用用于化简特殊类型，特殊类型化简后，可能存在From ！=?SimplifiedType，则会递归调用isa_impl_wrap的如下模板，直到From不能再化简，既From ==?SimplifiedType为止。

template<typename To, typename From, typename SimpleFrom>
struct isa_impl_wrap {
  // When From != SimplifiedType, we can simplify the type some more by using
  // the simplify_type template.
  static bool doit(const From &Val) {
    return isa_impl_wrap<To, SimpleFrom,
      typename simplify_type<SimpleFrom>::SimpleType>::doit(
                          simplify_type<const From>::getSimplifiedValue(Val));
  }
};

?当From ==?SimplifiedType时，会调用isa_impl_wrap的如下模板，接着调用模板isa_impl_cl。

template<typename To, typename FromTy>
struct isa_impl_wrap<To, FromTy, FromTy> {
  // When From == SimpleType, we are as simple as we are going to get.
  static bool doit(const FromTy &Val) {
    return isa_impl_cl<To,FromTy>::doit(Val);
  }
};

紧接着，模板isa_impl_cl通过不同的特例化模板，提取Y的类型（退化指针/const/从智能指针中提取类型等）。下面以智能指针的特例化为例：

template <typename To, typename From>
struct isa_impl_cl<To, const std::unique_ptr<From>> {
  static inline bool doit(const std::unique_ptr<From> &Val) {
    assert(Val && "isa<> used on a null pointer");
    return isa_impl_cl<To, From>::doit(*Val);
  }
};

经过isa_impl_cl的特例化模板，最终会调用到非特例化的模板，实现真正的isa判断。

template?<typename?To,?typename?From>?struct?isa_impl_cl?{

??static?inline?bool?doit(const?From?&Val)?{

????return?isa_impl<To,?From>::doit(Val);

??}

};

在isa_impl中，对To是From的父类的情况，通过enable_if特例化，直接返回true（From isa To）。

template <typename To, typename From>
struct isa_impl<
    To, From, typename std::enable_if<std::is_base_of<To, From>::value>::type> {
  static inline bool doit(const From &) { return true; }
};

对其余情况，则调用类的classof方法（见上述llvm RTTI 类继承树部分）进行判断，至此完成完整的isa功能实现。

template <typename To, typename From, typename Enabler = void>
struct isa_impl {
  static inline bool doit(const From &Val) {
    return To::classof(&Val);
  }
};

cast<>模板

对cast<X>(V)，下面以V的类型为引用进行分析，对cast<X>(V)，若V为引用类型(如A&/const A&)，则提取出的模板参数Y = A&/const A&。cast的实现分为2个部分：返回值类型的确定和类型转换的实现，分别由模板cast_retty和cast_convert_val实现。

template <class X, class Y>
inline typename cast_retty<X, Y>::ret_type cast(Y &Val) {
  assert(isa<X>(Val) && "cast<Ty>() argument of incompatible type!");
  return cast_convert_val<X, Y,
                          typename simplify_type<Y>::SimpleType>::doit(Val);
}

cast_retty模板用于决定cast的返回值类型，cast_retty会调用cast_retty_wrap对类型Y进行化简，再递归调用cast_retty，直到类型Y不能再化简为止。

template<class To, class From>
struct cast_retty {
  using ret_type = typename cast_retty_wrap<
      To, From, typename simplify_type<From>::SimpleType>::ret_type;
};

struct cast_retty_wrap {
  // When the simplified type and the from type are not the same, use the type
  // simplifier to reduce the type, then reuse cast_retty_impl to get the
  // resultant type.
  using ret_type = typename cast_retty<To, SimpleFrom>::ret_type;
};

template<class To, class FromTy>
struct cast_retty_wrap<To, FromTy, FromTy> {
  // When the simplified type is equal to the from type, use it directly.
  using ret_type = typename cast_retty_impl<To,FromTy>::ret_type;
};

接着调用模板cast_retty_impl确定最终的返回值类型，对V为引用类型(如A&/const A&)，会匹配到如下两个特例化的模板。

template<class To, class From> struct cast_retty_impl {
  using ret_type = To &;       // Normal case, return Ty&
};
template<class To, class From> struct cast_retty_impl<To, const From> {
  using ret_type = const To &; // Normal case, return Ty&
};

同样的，当既From ！=?SimpleFrom时，cast_convert_val也会对From类型进行化简，递归调用自身，直到From不能再化简为止。

template<class To, class From, class SimpleFrom> struct cast_convert_val {
  // This is not a simple type, use the template to simplify it...
  static typename cast_retty<To, From>::ret_type doit(From &Val) {
    return cast_convert_val<To, SimpleFrom,
      typename simplify_type<SimpleFrom>::SimpleType>::doit(
                          simplify_type<From>::getSimplifiedValue(Val));
  }
};

当From不能再化简既From ==?SimpleFrom时，会调用cast_convert_val的另一个特例化模板，进行最终的类型转换，至此完成完整的cast功能实现。

template<class To, class FromTy> struct cast_convert_val<To,FromTy,FromTy> {
  // This _is_ a simple type, just cast it.
  static typename cast_retty<To, FromTy>::ret_type doit(const FromTy &Val) {
    typename cast_retty<To, FromTy>::ret_type Res2
     = (typename cast_retty<To, FromTy>::ret_type)const_cast<FromTy&>(Val);
    return Res2;
  }
};

dyn_cast<>

dyn_cast的实现就是组合了isa和cast的功能。

template <class X, class Y>
LLVM_NODISCARD inline typename cast_retty<X, Y *>::ret_type dyn_cast(Y *Val) {
  return isa<X>(Val) ? cast<X>(Val) : nullptr;
}

参考材料

LLVM Programmer’s Manual — LLVM 15.0.0git documentation

How to set up LLVM-style RTTI for your class hierarchy — LLVM 15.0.0git documentation