LLVM笔记(18) - IR基础详解(二) Instruction

2023-12-03 08:45:10

上节介绍了IR中底层的数据表达方式(Value)及其组织方式(有向图), 有了这个基础就可以理解LLVM IR中的一些基本构成. 本节将要介绍其中的一个基础概念: 指令(Instruction).

LLVM IR指令基础

LLVM使用Instruction来描述一条具体的指令. 与ISA设计类似, 在LLVM中指令可以细分为若干类:

算术与位运算指令: 绝大部分指令可以归属为一元操作数指令(UnaryInstruction)与二元操作数指令(BinaryInstruction).
控制流指令: 包含(函数内)跳转指令(branch/indirect branch), 函数调用与返回(call/invoke/ret), 分支跳转(switch)等改变控制流的指令.
访存指令: 操作内存的指令(load/store).
其它指令: 不同于常见ISA的特有指令, 比如比较指令(icmp), 选择赋值指令(select), 以及维护SSA的必需品phi指令.

关于更多的IR指令介绍可以参见官方文档. 本文假定读者已经对IR有了基础了解, 将更多注重代码实现细节.
所有的指令都从Instruction类继承而来, 不同分类的指令有不同的特性. 我们首先看下其基础结构与实现逻辑, 再针对性介绍几类指令的细节.

通用指令定义

LLVM使用Instruction(defined in include/llvm/IR/Instruction.h)类来描述一条通用指令, 这里的通用的含义是所有指令都具有的行为(比如操作数信息), 具体而言包括:

指令类型.
指令操作数.
指令顺序.

为理解Instruction如何描述这些信息, 我们先来看下其定义, Instruction继承自两个类User与ilist, 其中链表ilist用于串联指令流使其可以被顺序访问.
为支持ilist的组织结构, Instruction包含一个Parent成员保存其所属的基础块指针以及一个用于计算dominance的Order. 另外Instruction还包含了一个DbgLoc用于记录Debug信息.

class Instruction : public User,
                    public ilist_node_with_parent<Instruction, BasicBlock> {
  BasicBlock *Parent;
  DebugLoc DbgLoc;

  mutable unsigned Order = 0;

protected:
  ~Instruction();

public:
  Instruction(const Instruction &) = delete;
  Instruction &operator=(const Instruction &) = delete;

  unsigned getOpcode() const { return getValueID() - InstructionVal; }
  const char *getOpcodeName() const { return getOpcodeName(getOpcode()); }
  static const char* getOpcodeName(unsigned OpCode);

  inline const BasicBlock *getParent() const { return Parent; }
  inline       BasicBlock *getParent()       { return Parent; }
};

指令类型

Instruction::getOpcode()用于返回指令类型, 其值由Value::getValueID()减去Value::InstructionVal得到.
后者在上节提到过, 即Value::SubClassID中大于Value::InstructionVal的枚举值属于指令类型枚举, 它们定义在include/llvm/IR/Instruction.def中.

  enum UnaryOps {
#define  FIRST_UNARY_INST(N)             UnaryOpsBegin = N,
#define HANDLE_UNARY_INST(N, OPC, CLASS) OPC = N,
#define   LAST_UNARY_INST(N)             UnaryOpsEnd = N+1
#include "llvm/IR/Instruction.def"
  };

  enum BinaryOps {
#define  FIRST_BINARY_INST(N)             BinaryOpsBegin = N,
#define HANDLE_BINARY_INST(N, OPC, CLASS) OPC = N,
#define   LAST_BINARY_INST(N)             BinaryOpsEnd = N+1
#include "llvm/IR/Instruction.def"
  };

  enum MemoryOps {
#define  FIRST_MEMORY_INST(N)             MemoryOpsBegin = N,
#define HANDLE_MEMORY_INST(N, OPC, CLASS) OPC = N,
#define   LAST_MEMORY_INST(N)             MemoryOpsEnd = N+1
#include "llvm/IR/Instruction.def"
  };

以上指令的类型对应IR输出可见Instruction::getOpcodeName()(defined in lib/IR/Instruction.cpp).

指令操作数

User类已经定义了一系列访问其依赖的值(操作数), 因此Instruction只需继承User即可, 回顾一下User类接口.
User::getOperand()与User::setOperand()用来获取/修改给定下标的指令的操作数, 如果需要迭代遍历操作数则可以使用User::operands().

class User : public Value {
public:
  Value *getOperand(unsigned i) const {
    assert(i < NumUserOperands && "getOperand() out of range!");
    return getOperandList()[i];
  }

  void setOperand(unsigned i, Value *Val) {
    assert(i < NumUserOperands && "setOperand() out of range!");
    assert((!isa<Constant>((const Value*)this) ||
            isa<GlobalValue>((const Value*)this)) &&
           "Cannot mutate a constant with setOperand!");
    getOperandList()[i] = Val;
  }

  using op_iterator = Use*;
  using const_op_iterator = const Use*;
  using op_range = iterator_range<op_iterator>;
  using const_op_range = iterator_range<const_op_iterator>;

  op_iterator       op_begin()       { return getOperandList(); }
  const_op_iterator op_begin() const { return getOperandList(); }
  op_iterator       op_end()         {
    return getOperandList() + NumUserOperands;
  }
  const_op_iterator op_end()   const {
    return getOperandList() + NumUserOperands;
  }
  op_range operands() {
    return op_range(op_begin(), op_end());
  }
  const_op_range operands() const {
    return const_op_range(op_begin(), op_end());
  }

  ......
};

指令顺序

一般情况下, 一个函数包含若干个基础块, 而一个基础块又包含若干条(线性排布的)指令, 因此需要一个恰当的数据结构来管理指令流. 注意到:

在编译器开发中常常需要在非固定位置插入/删除指令, 意味着单纯的顺序容器不能满足高效修改的需求.
由于底层数据结构(Value)中有向图的设计, 编译器可以高效的查找/更新指令位置, 对随机访问的需求也不大.

基于这个背景, 作为有向图的补充, LLVM使用链表来管理指令流. Instruction使用名为ilist_node_with_parent的链表来链接指令. 这个链表有以下几个特点:

侵入式设计, 即链表节点作为基类被其管理的Instruction类继承, 作为其继承类的一部分, 链表节点的构造也在构造继承类对象时构造.
相比于普通链表还包含一个父节点(parent), 指示其所属的上层对象类型. 继承类需要实现getParent()方法获取其所属的上层对象的指针. 上层对象需要实现getSublistAccess()方法获取链表.
部分包含所有权语义, 即删除链表节点时会同时删除继承类对象(然而构造链表节点时不会).

让我们来看下具体实现, 首先如上文所见Instruction包含一个Parent指针, 指向其所属的基础块. Instruction::getParent()用来返回该指针.
再来看下上层对象BasicBlock怎么返回Instruction链表. 其包含一个SymbolTableList成员.
方法BasicBlock::*getSublistAccess()返回了该链表成员, 注意这个接口是给链表内部逻辑代码使用的, 通常我们使用BasicBlock::getInstList()获取链表.

class BasicBlock final : public Value,
                         public ilist_node_with_parent<BasicBlock, Function> {
public:
  using InstListType = SymbolTableList<Instruction>;

private:
  InstListType InstList;

public:
  using iterator = InstListType::iterator;
  using const_iterator = InstListType::const_iterator;
  using reverse_iterator = InstListType::reverse_iterator;
  using const_reverse_iterator = InstListType::const_reverse_iterator;

  const InstListType &getInstList() const { return InstList; }
        InstListType &getInstList()       { return InstList; }

  /// Returns a pointer to a member of the instruction list.
  static InstListType BasicBlock::*getSublistAccess(Instruction*) {
    return &BasicBlock::InstList;
  }

  ......
};

SymbolTableList(include/llvm/IR/SymbolTableListTraits.h)是iplist_impl的偏特化, 关于iplist的详细介绍可以看这里, 这里我们看下其特化的萃取器SymbolTableListTraits.

template <class T> class SymbolTableList : public iplist_impl<simple_ilist<T>, SymbolTableListTraits<T>> {};

SymbolTableListTraits是一类特殊的traits, 其设计目的是在子节点链表发生变化时通知父节点以及符号表更新, 帮助编译器开发者从繁琐的工作中解脱出来.

template <typename NodeTy> struct SymbolTableListParentType {};

#define DEFINE_SYMBOL_TABLE_PARENT_TYPE(NODE, PARENT)                          \
  template <> struct SymbolTableListParentType<NODE> { using type = PARENT; };
DEFINE_SYMBOL_TABLE_PARENT_TYPE(Instruction, BasicBlock)
DEFINE_SYMBOL_TABLE_PARENT_TYPE(BasicBlock, Function)
DEFINE_SYMBOL_TABLE_PARENT_TYPE(Argument, Function)
DEFINE_SYMBOL_TABLE_PARENT_TYPE(Function, Module)
DEFINE_SYMBOL_TABLE_PARENT_TYPE(GlobalVariable, Module)
DEFINE_SYMBOL_TABLE_PARENT_TYPE(GlobalAlias, Module)
DEFINE_SYMBOL_TABLE_PARENT_TYPE(GlobalIFunc, Module)
#undef DEFINE_SYMBOL_TABLE_PARENT_TYPE

class SymbolTableListTraits : public ilist_alloc_traits<ValueSubClass> {
  using ListTy = SymbolTableList<ValueSubClass>;
  using iterator = typename simple_ilist<ValueSubClass>::iterator;
  using ItemParentClass = typename SymbolTableListParentType<ValueSubClass>::type;

public:
  SymbolTableListTraits() = default;

private:
  ItemParentClass *getListOwner() {
    size_t Offset(size_t(&((ItemParentClass*)nullptr->*ItemParentClass::
                           getSublistAccess(static_cast<ValueSubClass*>(nullptr)))));
    ListTy *Anchor(static_cast<ListTy *>(this));
    return reinterpret_cast<ItemParentClass*>(reinterpret_cast<char*>(Anchor) - Offset);
  }

  static ListTy &getList(ItemParentClass *Par) {
    return Par->*(Par->getSublistAccess((ValueSubClass*)nullptr));
  }

  static ValueSymbolTable *getSymTab(ItemParentClass *Par) {
    return Par ? toPtr(Par->getValueSymbolTable()) : nullptr;
  }

public:
  void addNodeToList(ValueSubClass *V);
  void removeNodeFromList(ValueSubClass *V);
  void transferNodesFromList(SymbolTableListTraits &L2, iterator first, iterator last);
  // private:
  template<typename TPtr> void setSymTabObject(TPtr *, TPtr);
  static ValueSymbolTable *toPtr(ValueSymbolTable *P) { return P; }
  static ValueSymbolTable *toPtr(ValueSymbolTable &R) { return &R; }
};

template <typename ValueSubClass>
void SymbolTableListTraits<ValueSubClass>::addNodeToList(ValueSubClass *V) {
  assert(!V->getParent() && "Value already in a container!!");
  ItemParentClass *Owner = getListOwner();
  V->setParent(Owner);
  invalidateParentIListOrdering(Owner);
  if (V->hasName())
    if (ValueSymbolTable *ST = getSymTab(Owner))
      ST->reinsertValue(V);
}

template <typename ValueSubClass>
void SymbolTableListTraits<ValueSubClass>::removeNodeFromList(ValueSubClass *V) {
  V->setParent(nullptr);
  if (V->hasName())
    if (ValueSymbolTable *ST = getSymTab(getListOwner()))
      ST->removeValueName(V->getValueName());
}

SymbolTableListTraits同样继承自ilist_alloc_traits. 注意这里ValueSubClass是子节点(Instruction), 而ItemParentClass是父节点(BasicBlock), 其定义见宏DEFINE_SYMBOL_TABLE_PARENT_TYPE特化了一系列SymbolTableListParentType模板.
SymbolTableListTraits是如何自动更新链表的关系的呢? 可以通过addNodeToList()简单窥探一下. 通过getListOwner()获取链表父节点, 然后更新节点的Parent为对应值, 再调用invalidateParentIListOrdering()将父节点Order设为非法值.

扩展指令

基于Instruction类扩展出了LLVM IR中的指令, 大致上它们分为若干类.

class name	concrete instruction
UnaryInstruction	只包含单一操作数的指令(使用HANDLE_UNARY_INST宏的指令), 另外Alloca/Load/VAArg/Cast也属于UnaryInstruction.
BinaryOperator	包含二元操作数的指令(HANDLE_BINARY_INST).
CallBase	Call/Invoke/Callbr三类指令.
StoreInst	Store指令.
GetElementPtrInst	GetElementPtr指令.
SelectInst	Select指令.
PHINode	PHI指令.

还有少量指令(CAS指令, 原子读写指令, 矢量shuffle指令)的分类就不一一列举了. 总体而言, LLVM IR按照指令操作数进行分类, 对于一些具有高层语言抽象的指令(phi指令, gep指令)则单独分类.

修改IR

从上文介绍可以发现修改LLVM IR的指令流并不容易. 首先需要新建对象, 正确设置每个操作数, 其次需要将其加入合适的链表, 更新对应父节点的数据结构与符号表.
所幸LLVM提供了名为IRBuilder(defined in include/llvm/IR/IRBuilder.h)的适配器类减轻了我们的开发工作. 以PHI指令为例:

static PHINode *PHINode::Create(Type *Ty, unsigned NumReservedValues,
                                const Twine &NameStr = "",
                                Instruction *InsertBefore = nullptr) {
  return new PHINode(Ty, NumReservedValues, NameStr, InsertBefore);
}

PHINode *IRBuilderBase::CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name = "") {
  PHINode *Phi = PHINode::Create(Ty, NumReservedValues);
  if (isa<FPMathOperator>(Phi))
    setFPAttrs(Phi, nullptr /* MDNode* */, FMF);
  return Insert(Phi, Name);
}

template<typename InstTy>
InstTy *IRBuilderBase::Insert(InstTy *I, const Twine &Name = "") const {
  Inserter.InsertHelper(I, Name, BB, InsertPt);
  SetInstDebugLocation(I);
  return I;
}

template <typename FolderTy = ConstantFolder,
          typename InserterTy = IRBuilderDefaultInserter>
class IRBuilder : public IRBuilderBase {
private:
  FolderTy Folder;
  InserterTy Inserter;

  ......
};

IRBuilder::CreatePHI()调用PHINode类的静态方法Create()创建一个PHINode对象, 然后调用IRBuilder::Insert()将其插入至基础块中.
其插入方式由IRBuilder的模板参数InsertTy指定, 默认使用IRBuilderDefaultInserter, 即在制定位置InsertPt插入指令.

码农公寓