文档结构  
翻译进度:已翻译     翻译赏金:5 元 (?)    ¥ 我要打赏

前言

本文档旨在介绍LLVM中一些重要的类和接口。本文档不打算介绍什么是LLVM,LLVM是如何工作的,还有LLVM的代码分析。本文假设你已经对LLVM有基本的了解,并对转换,或者分析和维护其中的代码感兴趣。

本文档会给你指导方向,让你可以在不断增长的LLVM架构中的代码中,找到你的方向。请注意,阅读本文档并不能替代LLVM源代码的阅读,所以如果你想查找某些类能做些什么,本文档并不能回答你这个问题,所以你还是得查找源码。以下这个链接是LLVM的doxygen文档,可以方便的让你查找想要的东西。

第 1 段(可获 2 积分)

本文第一部分介绍使用LLVM过程中,一些常用的知识点,第二部分将会介绍,LLVM的核心类。在日后的文档手册中,将会继续延伸讲解如何使用扩展库,例如dominator,CFG 控制流,还有一些有用的工具,例如 InstVisitor(doxygen)模版。

 

基本信息

本章节包含使用LLVM过程中,常用的信息,但是并未在API文档中列出。

第 2 段(可获 2 积分)

C++ 标准模版库

LLVM的代码中非常依赖C++的标准模版库(STL), 使用的数量可能比你用的还多。所以,你阅读本文前,你需要对STL有基本的了解,这样才能了解本文提到的技巧和库的功能。网上已经有非常丰富的资料还有书籍来讲解STL,你可以参考如下的资料,本文不再赘述。

  1. cppreference.com - 非常棒的STL手册,还有一些其他C++的库的手册。
  2. C++ In a Nutshell - 这是一本O’Reilly出版的书籍。书中涉及的是最新的库。但是这本书已经发行,所以不再免费下载。
  3. C++ Frequently Asked Questions.
  4. SGI’s STL Programmer’s Guide - 对 STL有详细的介绍.
  5. Bjarne Stroustrup’s C++ Page.
  6. Bruce Eckel’s Thinking in C++, 2nd ed. Volume 2 Revision 4.0 (even better, get the book).
第 3 段(可获 2 积分)

还鼓励您查看LLVM编码标准指南,该指南的重点是如何编写可维护的代码,而不是将您的大括号放在哪里。

其他有用的参考

  1. 跨平台使用静态和共享库

重要和有用的LLVM API

在这里,我们强调一些LLVM API,它们通常是有用的,并且当你编写转换时最好了解一下。

The isa<>cast<> and dyn_cast<> templates

LLVM源代码库广泛使用了一种自定义形式的RTTI。 这些模板与C ++ dynamic_cast <>操作符有许多相似之处,但它们没有一些缺点(主要源自dynamic_cast <>仅适用于具有v-table的类)。 因为它们经常被使用,你必须知道他们做什么以及它们如何工作。 所有这些模板都在llvm/Support/Casting.h (doxygen)文件中定义(请注意,您很少需要直接包含此文件)。

第 4 段(可获 2 积分)

isa<>:

isa<> 操作符就像Java的"instanceof"操作符.它根据一个引用或指针是否指向<>中指定的类类型来返回true或者false.这个操作符在各种约束检查中很有用(下面有例子).

cast<>:

cast<> 操作符是一个"检查过的转换"操作.它将一个指针或引用从基类转换到派生类, 如果类型错误将引发断言错误.这应该在当你相信实例的类型时使用. 一个isa<> 和 cast<> 模板的例子是:

第 5 段(可获 2 积分)
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());
}

请注意,您应该在后面跟着一个cast <>时使用isa <>测试,对于那种情况使用dyn_cast <>运算符。

dyn_cast<>:

dyn_cast <>操作符是一个“检查转换(checking cast)”操作。 它检查操作数是否是指定的类型,如果是这样,返回一个指向它的指针(该操作符不适用于引用)。 如果操作数不是正确的类型,则返回空指针。 因此,这样做非常像C++中的dynamic_cast <>运算符,并且应该在相同的情况下使用。 通常,dyn_cast <>运算符用于if语句或其他一些流程控制语句,如下所示:

第 6 段(可获 2 积分)
if (AllocationInst *AI = dyn_cast<AllocationInst>(Val)) {
  // ...
}

这种形式的if语句有效地组合了调用isa <>和调用cast <>到一个语句中,这是非常方便的。

请注意,dyn_cast <>运算符,如C++的dynamic_cast <>或Java的instanceof运算符,可能会被滥用。 特别是,您不应该使用一系列if/then/else 块来检查许多不同类的变体。 如果您发现自己想要这样做,使用InstVisitor类直接发出指令类型更为清洁也更有效。

第 7 段(可获 2 积分)

cast_or_null<>:

cast_or_null <>操作符与cast <>操作符类似,只是它允许一个空指针作为参数(然后传播)。 这有时可能是有用的,允许您将几个空检查合并为一个。

dyn_cast_or_null<>:

dyn_cast_or_null <>操作符与dyn_cast <>运算符类似,只不过它允许一个空指针作为参数(然后传播)。 这有时可能是有用的,允许您将几个空检查合并为一个。

这五个模板可以与任何类一起使用,无论它们是否具有虚表(v-table)。 如果要添加对这些模板的支持,请参阅文档如何为类层次结构设置LLVM风格的RTTI

 

第 8 段(可获 2 积分)

传递字符串(StringRef和Twine类)

虽然LLVM通常没有做太多的字符串操作,但我们确实有几个处理字符串的重要API。 两个重要的例子是Value类 - 它有指令,函数等的名称以及在LLVM和Clang中广泛使用的StringMap类。

这些是通用类,它们需要能够接受可能包含空字符的字符串。 因此,它们不能简单地使用const char *,并且使用conststd :: string&要求客户端执行通常不必要的堆分配。 相反,许多LLVM API使用StringRef或const Twine&来有效地传递字符串。

第 9 段(可获 2 积分)

StringRef类

StringRef数据类型表示对常量字符串(字符数组和长度)的引用,并支持std :: string上可用的常用操作,但不需要堆分配。

它可以隐式地使用C风格的以null结尾的字符串,std :: string,或显式地使用字符指针和长度来构造。 例如,StringRef find函数声明为:

iterator find(StringRef Key);

客户端可以使用以下任何一种来调用它:

Map.find("foo");                 // Lookup "foo"
Map.find(std::string("bar"));    // Lookup "bar"
Map.find(StringRef("\0baz", 4)); // Lookup "\0baz"
第 10 段(可获 2 积分)

类似地,需要返回字符串的API可能会返回一个StringRef实例,它可以直接使用或者使用str成员函数转换为std :: string。 参阅llvm/ADT/StringRef.h (doxygen)获取更多信息。

您很少直接使用StringRef类,因为它包含指向外部内存的指针,存储该类的实例通常是不安全的(除非您知道外部存储将不会被释放)。 StringRef在LLVM中是小而普遍的,它应该始终是按值传递。

Twine类

 Twine (doxygen) 类对API来说是一种接受连接字符串的有效方式。 例如,一个常见的LLVM范例是根据具有后缀的另一个指令的名称命名一个指令,例如:

第 11 段(可获 2 积分)
New = CmpInst::Create(..., SO->getName() + ".cmp");

Twine类实际上是指向临时(堆栈分配)对象的轻量级rope(译注:rope为一种数据结构)。 作为应用于字符串的加号运算符(即C字符串,std :: string或StringRef)的结果,可以隐式构造Twines。 twine可以延迟字符串的实际连接直到它们实际需要时,此时它可以直接有效地渲染到字符数组中。 这避免了构建字符串连接的临时结果时涉及的不必要的堆分配。 请参阅llvm/ADT/Twine.h (doxygen),这里有更多的信息。

第 12 段(可获 2 积分)

与StringRef一样,Twine对象指向外部内存,几乎不会直接存储或提及。 它们仅用于定义应该能够有效接收连接字符串的函数。

错误处理

正确的错误处理有助于我们识别代码中的错误,并帮助最终用户了解其工具使用中的错误。 错误分为两大类:编程性 可恢复性,它们具有不同的处理和报告策略。

编程性错误

编程性错误是违反程序的不变量或API约定,并表现在程序本身存在错误。 我们的目的是记录不变量,并且当运行时不变量发生改变时,在故障点(提供一些基本诊断)快速中断。

第 13 段(可获 2 积分)

处理编程错误的基本工具是断言和llvm_unreachable函数。 断言用于表示不变条件,并应包括描述不变量的消息:

assert(isPhysReg(R) && "All virt regs should have been allocated already.");

llvm_unreachable函数可用于记录那些不应该被进入(如果程序不变量含有)的控制流程区域:

enum { Foo, Bar, Baz } X = foo();

switch (X) {
  case Foo: /* Handle Foo */; break;
  case Bar: /* Handle Bar */; break;
  default:
    llvm_unreachable("X should be Foo or Bar here");
}
第 14 段(可获 2 积分)

可恢复的错误

可恢复的错误表示程序环境中的错误,例如资源故障(缺少文件,丢弃的网络连接等)或格式错误的输入。 应该检测这些错误并将其传递到编程级别,以便他们得到适当的处理。处理错误可以像向用户报告问题一样简单,也可能涉及尝试恢复。

可恢复的错误使用LLVM的错误(Error)方案进行建模。 该方案表示使用函数返回值的错误,类似于经典的C整数错误代码,或C++的std :: error_code。 但是,Error 类实际上是用户定义的错误类型的轻量级包装,允许附加任意信息来描述错误。 这与C++异常允许抛出用户自定义类型的方式类似。

第 15 段(可获 2 积分)

通过调用Error :: success()创建success值:

Error foo() {
  // Do something.
  // Return success.
  return Error::success();
}

Success值对于构建和返回的开销很小 - 它们对程序性能影响最小。

Failure值使用make_error <T>构建,其中T是从ErrorInfo实用程序继承的任何类:

class MyError : public ErrorInfo<MyError> {
public:
  MyError(std::string Msg) : Msg(Msg) {}
  void log(OStream &OS) const override { OS << "MyError - " << Msg; }
  static char ID;
private:
  std::string Msg;
};

char MyError::ID = 0; // In MyError.cpp

Error bar() {
  if (checkErrorCondition)
    return make_error<MyError>("Error condition detected");

  // No error - proceed with bar.

  // Return success value.
  return Error::success();
}
第 16 段(可获 2 积分)

Error值可以隐式转换为bool:true为error,false为success,习惯使用以下方式:

Error mayFail();

Error foo() {
  if (auto Err = mayFail())
    return Err;
  // Success! We can proceed.
  ...

对于可能失败但需要返回值的功能,可以使用Expected <T>实用程序。 这种类型的值可以用T或者Error来构造。 预期的<T>值也可以隐式转换为布尔值,但与Error的约定相反:true用于success,false为error。如果成功,可以通过解引用运算符访问T值。 如果失败,则可以使用takeError()方法提取错误值。 习惯用法如下:

第 17 段(可获 2 积分)
Expected<float> parseAndSquareRoot(IStream &IS) {
  float f;
  OS >> f;
  if (f < 0)
    return make_error<FloatingPointError>(...);
  return sqrt(f);
}

Error foo(IStream &IS) {
  if (auto SqrtOrErr = parseAndSquartRoot(IS)) {
    float Sqrt = *SqrtOrErr;
    // ...
  } else
    return SqrtOrErr.takeError();
}

所有Error 实例(无论成功或失败),都必须在被销毁之前(通过std :: move或return)检查或移动。 意外丢弃未经检查的错误将导致程序在未检查值的析构函数运行的地方中止,从而易于识别和修复违反此规则的行为。

第 18 段(可获 2 积分)

Success 值一旦被测试后就认为是经过检查的(通过调用布尔转换运算符):

if (auto Err = canFail(...))
  return Err; // Failure value - move error to caller.

// Safe to continue: Err was checked.

相反,以下代码总是导致中止,无论foo的返回值如何:

canFail();
// Program will always abort here, even if canFail() returns Success, since
// the value is not checked.

一旦错误类型的处理程序被激活,就会考虑检查Failure 值:

auto Err = canFail(...);
if (auto Err2 =
     handleErrors(std::move(Err),
       [](std::unique_ptr<MyError> M) {
         // Try to handle 'M'. If successful, return a success value from
         // the handler.
         if (tryToHandle(M))
           return Error::success();

         // We failed to handle 'M' - return it from the handler.
         // This value will be passed back from catchErrors and
         // wind up in Err2, where it will be returned from this function.
         return Error(std::move(M));
       })))
  return Err2;
第 19 段(可获 2 积分)

有关错误及其相关实用程序的更多信息,请参见Error.h头文件。

传递函数和其他可调用对象

有时您可能想要一个传递回调对象的函数。 为了支持lambda表达式和其他函数对象,你不应该使用传统的C方法来获取函数指针和不透明的cookie:

void takeCallback(bool (*Callback)(Function *, void *), void *Cookie);

而是使用以下方法之一:

功能模板

如果您不介意将函数的定义放入头文件中,请将其设置为可调用类型的模板化功能模板。

第 20 段(可获 2 积分)
template<typename Callable>
void takeCallback(Callable Callback) {
  Callback(1, 2, 3);
}

function_ref类模板

function_ref (doxygen) 类模板表示对可调用对象的引用,以可调用类型为模板。 如果在函数返回后不需要保持回调,这是将回调传递给函数的好选择。 这样,function_ref 对应std::function ,StringRef 对应 std::string。

可以从使用参数类型为Param1,Param2,...调用的任何可调用对象隐式构造function_ref<Ret(Param1, Param2, ...)>,并返回一个可转换为类型Ret的值。 例如:

第 21 段(可获 2 积分)
void visitBasicBlocks(Function *F, function_ref<bool (BasicBlock*)> Callback) {
  for (BasicBlock &BB : *F)
    if (Callback(&BB))
      return;
}

可以使用如下调用:

visitBasicBlocks(F, [&](BasicBlock *BB) {
  if (process(BB))
    return isEmpty(BB);
  return false;
});

请注意,function_ref对象包含指向外部内存的指针,因此存储类的实例通常不是安全的(除非您知道外部存储将不会被释放)。 如果您需要此功能,请考虑使用std::function。 function_ref足够小,应该始终按值传递。

第 22 段(可获 2 积分)

DEBUG()宏和-debug选项

通常在你传递值时,你会把一堆调试打印输出和其他代码放入你的传递当中。 在它工作后,你想删除它,但你可能需要在将来再次使用它(以解决你遇到的新的错误)。

当然,因为这样,你不想删除调试打印输出,但是你不希望它们总是干扰你。 一个标准的妥协是注释它们,允许您在将来需要它们时启用它们。

llvm/Support/Debug.h (doxygen)文件提供了一个名为 DEBUG() 的宏,这是一个更好的解决方案。 基本上,您可以将任意代码放入DEBUG宏的参数中,只有在运行'opt'(或任何其他工具)时使用'-debug'命令行参数才会执行该代码。

第 23 段(可获 2 积分)
DEBUG(errs() << "I am here!\n");

然后你可以像这样运行你的传递:

$ opt < a.bc > /dev/null -mypass
<no output>
$ opt < a.bc > /dev/null -mypass -debug
I am here!

使用DEBUG()宏而不是自制的解决方案可以让您不必为通过的调试输出创建“另一个”命令行选项。 请注意,对于非断言构建,DEBUG()宏被禁用,因此它们根本不会导致性能影响(同样的原因,它们也不应包含副作用!)。

关于DEBUG()宏的一个额外的好处是可以直接在gdb中启用或禁用它。 如果程序正在运行,只需从gdb中使用“set DebugFlag = 0”或“set DebugFlag = 1”即可。 如果程序尚未启动,您可以随时使用-debug运行它。

第 24 段(可获 2 积分)

DEBUG_TYPE和-debug-only选项的细粒度调试信息

有时候,您可能会发现自己处于这样一种情况,即允许-debug选项就会打开太多信息(例如在代码生成器上工作时)。 如果要使用更细粒度的控件启用调试信息,则应定义DEBUG_TYPE宏,并使用-debug-only选项,如下所示:

#define DEBUG_TYPE "foo"
DEBUG(errs() << "'foo' debug type\n");
#undef  DEBUG_TYPE
#define DEBUG_TYPE "bar"
DEBUG(errs() << "'bar' debug type\n"));
#undef  DEBUG_TYPE

然后你可以像这样运行你的传递:

第 25 段(可获 2 积分)
$ opt < a.bc > /dev/null -mypass
<no output>
$ opt < a.bc > /dev/null -mypass -debug
'foo' debug type
'bar' debug type
$ opt < a.bc > /dev/null -mypass -debug-only=foo
'foo' debug type
$ opt < a.bc > /dev/null -mypass -debug-only=bar
'bar' debug type
$ opt < a.bc > /dev/null -mypass -debug-only=foo,bar
'foo' debug type
'bar' debug type

当然,实际上,您只应该将DEBUG_TYPE设置在文件的顶部,以指定整个模块的调试类型。 请注意,只有在包含Debug.h之后才能执行此操作,而不是包含任意#include头。 此外,您应该使用比“foo”和“bar”更有意义的名称,因为没有系统可以保证名称不会冲突。 如果两个不同的模块使用相同的字符串,则在指定名称时,它们都将被打开。 例如,这允许使用-debug-only = InstrSched启用指令调度的所有调试信息,即使源存在于多个文件中。 该名称不能包含逗号(,),因为逗号用于分隔-debug-only选项的参数。

第 26 段(可获 2 积分)

出于性能原因,-debug-only不适用于LLVM的优化构建(--enable-optimized)。

DEBUG_WITH_TYPE宏也适用于您想要设置DEBUG_TYPE的情况,但仅适用于一个特定的DEBUG语句。 它需要一个额外的第一个参数,指明要使用的类型。 例如,前面的例子可以写成:

DEBUG_WITH_TYPE("foo", errs() << "'foo' debug type\n");
DEBUG_WITH_TYPE("bar", errs() << "'bar' debug type\n"));

Statistic 类和-stats选项

llvm/ADT/Statistic.h (doxygen)文件提供了一个名为Statistic的类,该类用作统一的方式来跟踪LLVM编译器正在执行的操作以及各种优化的有效性。 查看哪些优化有助于使特定程序运行得更快是有用的。

第 27 段(可获 2 积分)

通常你可以在一些大的程序上运行你的传递,并且你想看看它进行了多少次转换。 虽然您可以手动检查,或使用一些特别的方法,但这非常痛苦并且对大程序来说不是非常有用。 使用统计(Statistic )类使得跟踪该信息变得非常容易,并且所计算的信息以统一的方式呈现,其余的传递被执行。

有很多统计(Statistic )的使用案例,但使用它的基础如下:

  1. 定义你的统计数据:
第 28 段(可获 2 积分)
#define DEBUG_TYPE "mypassname"   // This goes before any #includes.
STATISTIC(NumXForms, "The # of times I did stuff");

STATISTIC宏定义一个静态变量,其名称由第一个参数指定。 传递名称取自DEBUG_TYPE宏,描述取自第二个参数。 定义的变量(在这种情况下为“NumXForms”)的行为类似于无符号整数。

  1. 每当你进行转型时,都会碰到计数器:
++NumXForms;   // I did stuff!

这就是你需要做的一切。 要获得“opt”打印收集的统计信息,请使用“-stats”选项:

第 29 段(可获 2 积分)
$ opt -stats -mypassname < program.bc > /dev/null
... statistics output ...

请注意,为了使用'-stats'选项,必须使用断言来编译LLVM。

当从SPEC基准套件在C文件上运行opt时,它会提供如下报告:

  7646 bitcodewriter   - Number of normal instructions
   725 bitcodewriter   - Number of oversized instructions
129996 bitcodewriter   - Number of bitcode bytes written
  2817 raise           - Number of insts DCEd or constprop'd
  3213 raise           - Number of cast-of-self removed
  5046 raise           - Number of expression trees converted
    75 raise           - Number of other getelementptr's formed
   138 raise           - Number of load/store peepholes
    42 deadtypeelim    - Number of unused typenames removed from symtab
   392 funcresolve     - Number of varargs functions resolved
    27 globaldce       - Number of global variables removed
     2 adce            - Number of basic blocks removed
   134 cee             - Number of branches revectored
    49 cee             - Number of setcc instruction eliminated
   532 gcse            - Number of loads removed
  2919 gcse            - Number of instructions removed
    86 indvars         - Number of canonical indvars added
    87 indvars         - Number of aux indvars removed
    25 instcombine     - Number of dead inst eliminate
   434 instcombine     - Number of insts combined
   248 licm            - Number of load insts hoisted
  1298 licm            - Number of insts hoisted to a loop pre-header
     3 licm            - Number of insts hoisted to multiple loop preds (bad, no loop pre-header)
    75 mem2reg         - Number of alloca's promoted
  1444 cfgsimplify     - Number of blocks simplified
第 30 段(可获 2 积分)

显然,通过这么多的优化,为这个东西制定一个统一的框架是非常好的。可以使您的传递很好地适应框架,使其更易于维护和有用。

调试代码时查看图形

LLVM中的几个重要数据结构是图形:例如由LLVM BasicBlocks制成的CFG,由LLVM MachineBasicBlocks组成的CFG以及指令选择DAG。在许多情况下,在调试编译器的各个部分的同时,立即可视化这些图形比较好。

LLVM提供了一些调试版本中可用的回调来做到这一点。例如,如果调用Function::viewCFG()方法,当前的LLVM工具会弹出一个包含CFG的窗口,其中每个基本块是图中的一个节点,每个节点包含块中的指令。类似地,还存在Function::viewCFGOnly()(不包括指令),MachineFunction::viewCFG()和MachineFunction::viewCFGOnly()和SelectionDAG::viewGraph()方法。例如,在GDB中,通常可以使用call DAG.viewGraph()的方式来弹出一个窗口。或者,您可以在您想调试的地方对代码中的这些函数进行调用。

第 31 段(可获 2 积分)

使其工作需要一些设置。在使用X11的Unix系统上,安装graphviz工具包,并确保您的路径中有“dot”和“gv”。如果您在Mac OS X上运行,请下载并安装Mac OS X Graphviz程序,然后将/Applications/Graphviz.app/Contents/MacOS/(或安装的任意位置)添加到您的路径。在配置,构建或运行LLVM时,这些程序不需要存在,并且可以在主动调试会话期间根据需要安装。

SelectionDAG已被扩展,以便更容易地在大型复杂图形中定位有趣的 节点。在gdb中,如果call DAG.setGraphColor(node, "color"),那么下一个call DAG.viewGraph()将突出显示指定颜色的节点(可以在颜色表中找到可选的颜色)。更复杂的节点属性通过call DAG.setGraphAttrs(node,"attributes")提供(可以在Graph属性中找到选项。)如果要重新启动并清除所有当前图形属性,则可以执行call DAG.clearGraphAttrs()。

第 32 段(可获 2 积分)

请注意,图形可视化功能是从Release版本中编译的,以减少文件大小。 这意味着您需要一个Debug + Asserts或Release + Asserts构建才能使用这些功能。

为任务选择正确的数据结构

LLVM在llvm/ADT/目录中有大量的数据结构,我们通常使用STL数据结构。 本节介绍当您选择一个数据结构时应该考虑的权衡取舍。

第一步是选择自己需要的容器:你想要一个顺序的容器,一个集合的容器,还是一个地图样的容器? 选择容器时最重要的是计划访问容器的算法属性。 基于此,您应该使用:

第 33 段(可获 2 积分)
  • 如果您需要高效地查找基于另一个值的值,则可以使用map型(map-like)容器。map型容器还支持有效的包含查询(无论键是否在map中)。map型容器通常不支持有效的反向映射(值对键的映射)。如果需要,请使用两张map。一些map型容器也支持通过按排序顺序的键进行有效的迭代。map型容器是一种开销很大的类型,只有在需要这些功能之一时才可以使用它们。
  • 如果您需要将一堆东西放入容器中以自动消除重复的容器,则可以将其设置为set型(set-like)容器。一些set型容器通过按顺序排列的元素来支持有效的迭代。set型容器比顺序容器开销更大。
  • 顺序(sequential)容器提供了最有效的方法来添加元素并跟踪它们添加到集合中的顺序。它们允许重复并支持高效的迭代,但不支持基于键的高效查找。
  • 字符串(string)容器是用于字符或字节数组的专用顺序容器或引用结构。
  • 位(bit)容器提供了一种有效的方式来存储和执行数字ID集合的集合操作,同时自动消除重复的数据。位容器对于要存储的每个标识符最多需要1位。
第 34 段(可获 2 积分)

一旦确定了适当类别的容器,您可以通过智能地挑选该类别的成员来微调内存使用,常数因子和缓存访问行为。 请注意,常数因子和缓存行为可能是一个很大的问题。 如果你有一个通常只包含几个元素(但可以包含很多)的向量,例如,使用SmallVector 比vector更好。 这样做避免了(相对而言)昂贵的malloc / free调用,这使得将元素添加到容器的成本降低。

顺序容器(std::vector, std::list等)

第 35 段(可获 2 积分)

根据您的需要,可以为您提供各种顺序的容器。 选择本节中的第一个,它将实现你想要的。

llvm/ADT/ArrayRef.h

llvm::ArrayRef类是在接口中使用的首选类,它接受内存中的元素的顺序列表并且只是读取它们。 通过获取一个ArrayRef,API可以传递一个固定大小的数组,一个std :: vector,一个llvm :: SmallVector以及其他在内存中连续的任意值。

固定大小的数组

固定大小的数组非常简单,非常快。 如果您确切知道有多少元素,或者您对拥有的数据有一个(低)上限,您可以使用它们。

第 36 段(可获 2 积分)

堆分配阵列

堆分配的数组(new [] + delete [])也很简单。 如果元素的数量是可变的,那么它们是有益的,如果你知道在数组被分配之前需要多少个元素,并且数组通常很大(如果不是,则考虑使用SmallVector)。 堆分配阵列的成本是new/delete的成本(也称为malloc / free)。 另请注意,如果您使用构造函数分配类型数组,则将为数组中的每个元素运行构造函数和析构函数(可变大小的向量仅构造实际使用的元素)。

第 37 段(可获 2 积分)

llvm/ADT/TinyPtrVector.h

TinyPtrVector <Type>是一种高度专业化的集合类,它经过优化以避免在矢量有零个或一个元素的情况下进行分配。 它有两个主要的限制:1)它只能保存指针类型的值,2)它不能保存空指针。

由于这个容器是高度专业化的,所以很少使用。

llvm/ADT/SmallVector.h

SmallVector <Type,N>是一个简单的类,它与vector<Type>比较相像:它支持有效的迭代,以内存顺序中排列元素(所以你可以在元素之间进行指针运算),支持高效的push_back / pop_back操作, 支持对其元素的高效随机访问等。

第 38 段(可获 2 积分)

SmallVector的优点是它为对象本身中的一些元素(N)分配空间。 因此,如果SmallVector动态小于N,则不执行malloc。 这在malloc/free调用比元素周围的代码要昂贵得多的情况下,将是一个很大的胜利。

这对于“通常很小(usually small)”的矢量是有好处的(例如,块的predecessors/successors的数量通常小于8)。 另一方面,这使得SmallVector本身的大小很大,所以你不想大量分配它们(这样做会浪费很多空间)。 因此,SmallVectors在堆栈中最有用。

第 39 段(可获 2 积分)

SmallVector还为alloca提供了一个不错的便携式和高效替换。

注意

优先使用SmallVectorImpl <T>作为参数类型。

在不关心“小尺寸(small size)”(大多数?)的API中,优先使用SmallVectorImpl <T>类,它基本上只是“vector header”(和方法),而没有在它之后分配元素。 请注意,SmallVector <T,N>继承自SmallVectorImpl <T>,因此转换是隐式的而且成本为零。 例如。

// BAD: Clients cannot pass e.g. SmallVector<Foo, 4>.
hardcodedSmallSize(SmallVector<Foo, 2> &Out);
// GOOD: Clients can pass any SmallVector<Foo, N>.
allowsAnySmallSize(SmallVectorImpl<Foo> &Out);

void someFunc() {
  SmallVector<Foo, 8> Vec;
  hardcodedSmallSize(Vec); // Error.
  allowsAnySmallSize(Vec); // Works.
}
第 40 段(可获 2 积分)

尽管它具有“Impl”的名称,但由于它非常广泛的使用,它真的不再是“私有实现”了。 像SmallVectorHeader这样的名字会更合适。

<vector>

std :: vector很受欢迎和尊重。 当SmallVector不是以下两种情况:向量的大小通常很大(因此小的优化将很少有用),或者如果你将分配许多向量本身的实例(这会浪费那些不在容器中的元素的存储空间)时,它是有用的。 当与需要向量的代码进行接口时,向量也是有用的:)。

第 41 段(可获 2 积分)

关于std :: vector的一个值得注意的事情是:避免这样的代码:

for ( ... ) {
   std::vector<foo> V;
   // make use of V.
}

相反,应该写为:

std::vector<foo> V;
for ( ... ) {
   // make use of V.
   V.clear();
}

这样做会节省(至少)一次堆的分配并且提高循环每次迭代的效率。

<deque>

std :: deque在某些意义上是一个广义版本的std :: vector。 像std :: vector一样,它提供了不间断的随机访问和其他类似的属性,但它也提供了对列表前端的高效访问。 它不能保证内存元素的连续性。

第 42 段(可获 2 积分)

为了换取这种额外的灵活性,std :: deque具有比std :: vector显著更高的常数因子成本。 如果可能,使用std :: vector或成本更低的东西。

<list>

std :: list是一个非常低效的类,很少使用。 它为插入到其中的每个元素执行堆分配,因此具有非常高的常数因子,特别是对于小数据类型。 std :: list也只支持双向迭代,而不是随机访问迭代。

为了换取这种高成本,std :: list支持高效地访问列表的两端(如std :: deque,但不像std :: vector或SmallVector)。 此外,std :: list的迭代器无效特征比向量类的迭代器无效特性更强:在列表中插入或删除元素不会使迭代器或指针指向列表中的其他元素。

第 43 段(可获 2 积分)

llvm/ADT/ilist.h

ilist <T>实现了一个“侵入式”双向链表。 它是侵入性的,因为它要求元素存储并提供对列表的prev/next指针的访问。

ilist具有与std :: list相同的缺点,另外还需要一个用于元素类型的ilist_traits实现,但它提供了一些新颖的特征。 特别地,它可以有效地存储多态对象,当元素被插入或从列表中移除时通知特征类,并且保证ilist支持常量时间拼接操作。

第 44 段(可获 2 积分)

这些属性正是我们想要的东西,如指令和基本块,这就是为什么这些是用ilist实现的。

感兴趣的相关类将在以下小节中解释:

llvm/ADT/PackedVector.h

对于向量的每个值仅使用少量的位存储是有用的。 除了向量式容器的标准操作之外,还可以执行“或(or)”集合操作。

例如:

enum State {
    None = 0x0,
    FirstCondition = 0x1,
    SecondCondition = 0x2,
    Both = 0x3
};

State get() {
    PackedVector<State, 2> Vec1;
    Vec1.push_back(FirstCondition);

    PackedVector<State, 2> Vec2;
    Vec2.push_back(SecondCondition);

    Vec1 |= Vec2;
    return Vec1[0]; // returns 'Both'.
}
第 45 段(可获 2 积分)

ilist_traits

ilist_traits <T>是ilist <T>的定制机制。 iplist <T>(因此ilist <T>)从这个特征类公开派生。

iplist

iplist <T>是ilist <T>的基类,因此支持稍窄的接口。 值得注意的是,T& 的插入器不存在。

ilist_traits <T>是这个类的公共基类,可以用于各种定制。

llvm/ADT/ilist_node.h

ilist_node <T>以默认方式实现ilist <T>(及类似容器)预期的前向和后向链接。

ilist_node <T>意在嵌入在节点类型T中,通常T公有派生自ilist_node <T>。

第 46 段(可获 2 积分)

哨兵(Sentinels)

ilist有另一个必须考虑的专长。 要成为C ++生态系统中的好公民,它需要支持标准的容器操作,比如开始和结束迭代器等。另外,在非空的ilist的情况下,操作符必须在最终迭代器上正常工作。

这个问题的唯一明智的解决方案是分配一个所谓的哨兵 以及作为结束迭代器的入侵列表,提供了到最后一个元素的反向链接。 然而,遵循C++的约定,除了哨兵之外的操作符++是不合法的,它也不能被解引用。

第 47 段(可获 2 积分)

这些约束允许对ilist如何分配和存储哨兵的一些自由实现。 相应的策略由ilist_traits <T>决定。 默认情况下,当需要哨兵出现时,T将被分配到堆中。

虽然默认策略在大多数情况下足够了,但是当T不提供默认构造函数时,它可能会失效。 此外,在许多ilist的情况下,相关联的哨兵的内存开销被浪费。 为了减轻许多大量的T哨兵的情况,有时候会采取一个伎俩,产生幽灵(ghostly ) 哨兵。

第 48 段(可获 2 积分)

幽灵哨兵是通过专门设计的ilist_traits <T>获得的,在内存中它将哨兵与ilist 实例叠加在一起。 指针运算用于获取哨兵,它相对于ilist的 this 指针。 ilist增加了一个额外的指针,作为前哨的后链。 这是幽灵哨兵中唯一可以合法访问的地方。

其他顺序容器选项

可以使用其他STL容器,如std :: string。

还有各种STL适配器类,如std :: queue,std :: priority_queue,std :: stack等。这些提供对底层容器的简化访问,但不影响容器本身的开销。

第 49 段(可获 2 积分)

字符串型容器

有多种方法可以传递和使用C和C++中的字符串,而且LLVM添加了一些新的选项可供选择。 选择这个列表中的第一个选项,它将实现你想要的,而且他们已经按照相对开销排好序了。

请注意,通常不要 将字符串传递为const char *。 这存在很多问题,包括它们不能表示嵌入的空(“0”)字符,并且不能高效地获取字符串长度。 “const char *”一般替换为StringRef。

有关为API选择字符串容器的更多信息,请参阅传递字符串

第 50 段(可获 2 积分)

llvm/ADT/StringRef.h

StringRef类是一个简单的值类,它包含一个指向字符和长度的指针,并且与ArrayRef类非常相关(但专门用于字符数组)。 因为StringRef自带长度,它可以安全地处理嵌入空字符的字符串,获取长度不需要strlen调用,甚至还有非常方便的API用于对其表示的字符范围进行切片和切割。

StringRef是传递简单字符串的理想选择,其他例如C字符串字面值,std :: string,C数组或SmallVector。 这些情况中的每种都可以有效的隐式转换为StringRef,它不会导致动态执行strlen函数。

第 51 段(可获 2 积分)

StringRef有一些主要的限制,使得强大的字符串容器变得有用:

  1. 您不能直接将StringRef转换为“const char *”,因为无法添加尾随的nul(不同于其他各种强大的类中的.c_str()方法)。
  2. StringRef不拥有或保留底层字符串字节。 因此,这样就很容易导致悬空指针,并且在大多数情况下不适合嵌入数据结构(而是使用std :: string或类似的东西)。
  3. 出于同样的原因,如果方法“计算(computes)”结果字符串,则StringRef不能用作方法的返回值。 而是使用std :: string。
  4. StringRef不允许您改变指向字符串的字节,并且不允许您插入或删除范围中的字节。 对于这样的编辑操作,它与Twine类进行互操作。
第 52 段(可获 2 积分)

由于它的优点和局限性,使得函数使用StringRef,和对象上的方法返回一个指向它所拥有的字符串的StringRef变得非常普遍。

llvm/ADT/Twine.h

Twine类被用作API的中间数据类型,用于处理能够以内联方式构造一系列的串联字符串。 Twine通过在堆栈上形成Twine数据类型(一个简单的值对象)的递归实例作为临时对象,将它们连接在一起形成二叉树,然后在Twine销毁时线性化。 Twine只能安全地用作函数的参数,并且应该始终是一个常量引用,例如:

第 53 段(可获 2 积分)
void foo(const Twine &T);
...
StringRef X = ...
unsigned i = ...
foo(X + "." + Twine(i));

此示例通过将值连接在一起形成“blarg.42”之类的字符串,不会形成包含“blarg”或“blarg.”的中间字符串。

因为Twine是使用堆栈上的临时对象构建的,并且因为这些实例在当前语句的末尾被销毁,本质上它是一个危险的API。 例如,这个简单的变体程序包含未定义的行为,并且可能会崩溃:

void foo(const Twine &T);
...
StringRef X = ...
unsigned i = ...
const Twine &Tmp = X + "." + Twine(i);
foo(Tmp);
第 54 段(可获 2 积分)

因为在调用前临时变量被销毁。 也就是说,Twine的效率要比中间std :: string临时变量更高效,而且它们与StringRef非常相似。 只要知道他们的局限性就行了。

llvm/ADT/SmallString.h

SmallString是SmallVector的子类,它添加了一些方便的使用StringRef作为参数的API,如+ =。 在预分配空间足以容纳其数据的情况下,SmallString避免预先分配内存,并在需要时回调到一般堆分配。 由于它自己拥有字符串数据,所以使用和支持字符串的完全变异是非常安全的。

第 55 段(可获 2 积分)

像SmallVector一样,SmallString一个很大的缺点就是它们的长度运算符。 虽然它们针对小型字符串进行了优化,但它们本身并不是特别小。 这意味着它们对于堆栈上的临时暂存缓冲区非常有用,但通常不应该放入堆中:将SmallString看作是经常分配的堆数据结构或返回值的成员是非常罕见的。

std::string

标准的C++ std :: string类是一个非常通用的、拥有其底层数据的类(如SmallString)。 sizeof(std :: string)是非常合理的,因此它可以嵌入到堆数据结构中并返回值。 另一方面,std :: string对于内联编辑是非常低效的(例如将一堆东西连接在一起),并且由于它由标准库提供,其性能特征取决于很多主机标准库(例如,libc++和MSVC 提供了一个高度优化的字符串类,而GCC包含了一个非常慢的实现)。

第 56 段(可获 2 积分)

std :: string的主要缺点是几乎每个使它们更大的操作都需要分配内存,这是缓慢的。 因此,最好使用SmallVector或Twine作为暂存缓冲区,但是使用std :: string来保存结果。

集合型容器(std :: set,SmallSet,SetVector等)

当您需要将多个值规范化为单个表示时,集合型容器很有用。如何做到这一点有几个不同的选择,其权衡也各不相同。

一个排序的“向量”

如果你打算插入很多元素,然后做很多的查询,一个很好的方法是使用一个带有std :: sort + std :: unique的向量(或其他顺序容器)去除重复的东西。 如果您的使用模式包含这两个不同的阶段(插入然后查询),并且可以与选择一个良好的顺序容器相结合,这种方法效果就非常好。

第 57 段(可获 2 积分)

该组合提供了几个不错的属性:结果数据在内存中是连续的(对于缓存位置有利),分配很少,容易寻址(最终向量中的迭代器只是索引或指针),并且可以有效地查询标准的二进制搜索(例如std :: lower_bound;如果您希望在整个元素范围上比较相等,请使用std :: equal_range)。

llvm/ADT/SmallSet.h

如果您的数据结构通常较小且元素相对较小,则SmallSet <Type,N>是一个不错的选择。 该集合具有适用于N个元素的空间(因此,如果集合动态小于N,则不需要malloc操作),并通过简单的线性搜索访问它们。 当集合增长超过N个元素时,它会分配一个更昂贵的表示以保证有效的访问(对于大多数类型,它将回退到 std::set,,但是对于指针来说,它将使用一些更好的东西,如 SmallPtrSet

第 58 段(可获 2 积分)

这个类的神奇之处在于它处理小集合非常高效,但在优雅地处理非常大的集合时也不损失效率。 它的缺点是接口相当小:它仅支持插入,查询和擦除,但不支持迭代。

llvm/ADT/SmallPtrSet.h

SmallPtrSet具有SmallSet的所有优点(并且SmallSet的指针通过SmallPtrSet透明地实现),而且还支持迭代器。 如果执行了多于N个插入,则根据需要分配并增长单个二次探测的哈希表,提供非常高效的访问(具有低常数因子的常量时间插入/删除/查询),并且只有很少的malloc流量。

第 59 段(可获 2 积分)

请注意,与std::set不同,每当插入发生时,SmallPtrSet的迭代器都将失效。 此外,迭代器访问的值不按排序顺序访问。

llvm/ADT/StringSet.h

StringSet是一个围绕StringMap<char>的瘦包装,它可以有效地存储和检索唯一的字符串。

在功能上类似于SmallSet <StringRef>,StringSet也支持迭代。 (迭代器对StringMapEntry <char>进行引用,所以您需要调用i-> getKey()来访问StringSet的项目)另一方面,StringSet不支持范围插入和复制构造, 而SmallSetSmallPtrSet 支持。

第 60 段(可获 2 积分)

llvm/ADT/DenseSet.h

DenseSet是一个简单的二次探测哈希表。 它擅长支持小值:它使用单个分配来保存当前插入到集合中的所有键值对。 DenseSet是一种伟大的使小值(不是简单的指针)唯一的方式(使用 SmallPtrSet指针)。 请注意,DenseSet对DenseMap具有的值类型具有相同的要求。

llvm/ADT/SparseSet.h

SparseSet保存由中等大小的无符号键标识的少量对象。 它使用大量内存,但提供的操作几乎与向量一样快。 典型的键是物理寄存器,虚拟寄存器或编号的基本块。

第 61 段(可获 2 积分)

SparseSet对于需要非常快速清除/查找/插入/擦除的算法并且在小集合上快速迭代非常有用。 它不是用于构建复合数据结构的。

llvm/ADT/SparseMultiSet.h

SparseMultiSet将多集合行为添加到SparseSet,同时保留SparseSet的所需属性。 像SparseSet一样,它通常使用大量的内存,但提供的操作几乎与向量一样快。 典型的键是物理寄存器,虚拟寄存器或编号的基本块。

SparseMultiSet对于需要非常快速清除/查找/插入/删除整个集合的算法以及共享键的元素集合的迭代很有用。 通常比使用复合数据结构(例如vector-of-vectors, map-of-vectors)更高效。 它不是用于构建复合数据结构的。

第 62 段(可获 2 积分)

llvm/ADT/FoldingSet.h

FoldingSet是一个聚合类,它非常适用于定义昂贵的创建或多态对象。它是一个链式哈希表与侵入式链接(某对象都需要继承FoldingSetNode)的组合,它使用SmallVector作为其ID进程的一部分。

考虑一种情况,您要为复杂对象(例如代码生成器中的一个节点)实现“getOrCreateFoo”方法。 客户端描述了要生成什么内容(它知道操作码和所有操作数),但是我们不想“新建”一个节点,然后尝试将其插入到集合中,才发现它已经存在, 此时我们必须删除它并返回已经存在的节点。

第 63 段(可获 2 积分)

为了支持这种风格的客户端,FoldingSet使用可以用于描述我们要查询的元素的FoldingSetNodeID(它包装SmallVector)执行查询。 该查询或者返回与该ID匹配的元素,或者返回一个不透明的ID,指示应该在何处进行插入。 ID的构建通常不需要堆分配。

因为FoldingSet使用侵入式链接,它可以支持该集合中的多态对象(例如,您可以将SDNode实例与LoadSDNodes混合)。 因为元素被单独分配,所以指向元素的指针是稳定的:插入或移除元素不会使任何指向其他元素的指针失效。

第 64 段(可获 2 积分)

<set>

std::set是一个合理的全面集合类,这在处理许多事情上是相当不错的,但没有什么特别突出的优点。 std::set为插入的每个元素分配内存(因此导致了非常密集的malloc),并且通常在集合中为每个元素存储三个指针(因此增加了大量的单个元素空间开销)。 它提供了保证的log(n) 性能,这从复杂性的角度来看并不是特别快(尤其是如果集合的元素比较起来像字符串那样昂贵),并且具有非常高的常数因子用于查找,插入和移除。

第 65 段(可获 2 积分)

std::set 的优点是它的迭代器是稳定的(从集合中删除或插入一个元素不会影响迭代器或指向其他元素的指针),并且该集合的迭代保证按照排序顺序。 如果集合中的元素很大,那么指针和malloc流量的相对开销并不大,但是如果集合的元素很小,那么std::set几乎不是一个好的选择。

llvm/ADT/SetVector.h

LLVM的SetVector<Type>是一个适配器类,它将您选择的集合型容器以及顺序容器组合在一起。它提供的重要属性是使用迭代支持的高效唯一性插入(重复元素将被忽略)。 它通过将元素插入到集合型容器和顺序容器中,使用集合型容器保证唯一性和顺序型容器进行迭代来实现。

第 66 段(可获 2 积分)

SetVector和其他集合之间的区别在于确保迭代顺序与插入SetVector的顺序相匹配。 这个属性对于像指针的集合这样的东西非常重要。 因为指针值是非确定性的(例如,它会根据程序在不同机器上的运行而有所不同),所以集合中的指针将不会按照一个定义良好的顺序迭代。

SetVector的缺点是它需要两倍于正常集合的空间,并且具有来它使用的集合型容器和顺序容器的常数因子之和。 在你需要以确定性顺序迭代元素时使用它。 SetVector删除(线性时间)元素的操作也非常昂贵,除非你使用它的“pop_back”方法,这个方法更快。

第 67 段(可获 2 积分)

SetVector是一个适配器类,默认使用std::vector和大小为16的用于底层容器的SmallSet,所以它是相当昂贵的。 但是,“llvm/ADT/SetVector.h”还提供了一个SallCallSetVector类,它默认使用指定大小的SmallVector和SmallSet。 如果你使用这个,并且如果你的集合动态地小于N,你将节省很多堆流量。

llvm/ADT/UniqueVector.h

UniqueVector类似于SetVector,但它为插入到集合中的每个元素保留唯一的ID。 它内部包含一个map和一个vector,并为插入到集合中的每个值分配一个唯一的ID。

第 68 段(可获 2 积分)

UniqueVector是非常昂贵的:其成本是维护map和vector的成本的总和,它具有高复杂性,高常数因子,并且产生大量的malloc流量。 应该避免使用。

llvm/ADT/ImmutableSet.h

ImmutableSet是基于AVL树的不可变(功能)集合实现。 通过Factory对象完成添加或删除元素,并导致创建一个新的ImmutableSet对象。 如果具有给定内容的ImmutableSet已经存在,则返回现有的; 使用FoldingSetNodeID比较相等。 添加或删除操作的时间和空间复杂度在原始集合的大小上是对数的。

第 69 段(可获 2 积分)

没有返回该集合元素的方法,您只能检查成员资格。

其他集合型容器选项

STL提供了其他几个选项,例如std::multiset和各种“hash_set”,如容器(不管是从C++ TR1还是从SGI库)。 我们从不使用hash_set和unordered_set,因为它们通常非常昂贵(每个插入需要一个malloc),非常不便携。

如果你不想消除重复,那么std::multiset是有用的,但具有 std::set 的所有缺点。 排序的向量(您不删除重复的条目)或其他方法几乎总是更好。

第 70 段(可获 2 积分)

Map型容器(std::map, DenseMap等)

当您想将数据与键相关联时,Map型容器就很有用。 像往常一样,有很多不同的方式来实现这一点。 :)

一个排序的“向量”

如果您的使用模式遵循严格的insert-then-query方法,您可以简单地使用与集合型容器的排序向量相同的方法。 唯一的区别是,您的查询函数(使用std :: lower_bound来获取高效的log(n) 查找)只应该比较键,而不是键和值两者。 这与集合的排序向量具有相同的优点。

第 71 段(可获 2 积分)

llvm/ADT/StringMap.h

字符串通常用作map中的键,并且它们难以有效地支持:它们的可变长度,在进行哈希和比较long型时的低效,复制费用高等。StringMap是专门用于处理这些问题的容器。 它支持将任意范围的字节映射到任意其他对象。

StringMap实现使用二次探测的哈希表,其中桶存储指向堆分配的条目(以及其他一些内容)的指针。 map中的条目必须是堆分配的,因为字符串是可变长度的。 字符串数据(key)和元素对象(value)与紧跟在元素对象之后的字符串数据相同的分配存储。 该容器保证 “(char*)(&Value+1)” 指向一个值的键字符串。

第 72 段(可获 2 积分)

StringMap非常快,原因如下:二次探测对于查找是非常高效的缓存,当查找元素时,不重新计算桶中字符串的哈希值,当查找一个值时,StringMap很少接触无关对象的内存( 即使发生哈希冲突),散列表增长也不会重新计算表中已经存在的字符串的哈希值,并且映射中的每个键值对都存储在单个分配中(字符串数据存储在与一个键值对中值的相同的分配中)。

StringMap还提供了采用字节范围的查询方法,因此只有当值插入到表中时,它才会复制字符串。

第 73 段(可获 2 积分)

然而,StringMap迭代顺序不能保证是确定性的,所以任何需要保证迭代顺序的应用程序都应该使用std :: map代替。

llvm/ADT/IndexedMap.h

IndexedMap是用于将小密集整数(或可映射到小密集整数的值)映射到其他类型的专用容器。 它在内部实现为具有将键映射到密集整数范围的映射函数的向量。

这对于LLVM代码生成器中的虚拟寄存器的情况非常有用:它们具有由编译时常数(第一个虚拟寄存器ID)偏移的密集映射。

第 74 段(可获 2 积分)

llvm/ADT/DenseMap.h

DenseMap是一个简单的二次探测散列表。 它擅长支持小的键和值:它使用单个分配来保存当前插入到map中的所有键值对。 DenseMap是将指针映射到指针或将其他小类型彼此映射的好方法。

然而,您应该注意DenseMap的以下几点。 与map不同,每当插入发生时,DenseMap中的迭代器失效。 此外,由于DenseMap为大量的键/值对分配空间(默认情况下以64开始),如果键或值很大,则会浪费大量空间。 最后,如果尚未支持,则必须对所需的建实现DenseMapInfo的部分专业化。 这需要告诉DenseMap两个特殊的、内部需要的标记值(不能插入到map中)。

第 75 段(可获 2 积分)

DenseMap的 find_as()方法支持使用备用键类型的查找操作。 在正常键类型构建昂贵,但比较操作廉价的情况下,这是有用的。 DenseMapInfo负责为所使用的每个备用键类型定义适当的比较和散列方法。

llvm/IR/ValueMap.h

ValueMap是DenseMap映射Value*(或子类)到另一种类型的包装。 当值被删除或RAUW'ed时,ValueMap将自动更新,以便将新版本的键映射到相同的值,就像键是WeakVH一样。 通过将Config参数传递给ValueMap模板,您可以准确地配置这两个事件如何产生以及还会发生什么。

第 76 段(可获 2 积分)

llvm/ADT/IntervalMap.h

IntervalMap是一个小的键和值的压缩映射。 它映射键间隔而不是单个键,它将自动合并相邻的间隔。 当映射只包含几个间隔时,它们会存储在映射对象本身中以避免分配。

IntervalMap迭代器是相当大的,所以它们不应该作为STL迭代器传递。 重量级迭代器允许较小的数据结构。

<map>

std::map与std::set具有相似的特征:它为每个键值对使用插入到映射中的单个分配,它提供具有非常大的常数因子的log(n) 查找,在映射中的每个键值对占用3个指针的空间,等等。

第 77 段(可获 2 积分)

当您的键或值非常大时,如果需要按排序顺序迭代集合,或者如果在映射中需要稳定的迭代器,std :: map是最有用的(即如果插入或删除另一个元素发生时,它们不会失效)。

llvm/ADT/MapVector.h

MapVector<KeyT,ValueT>提供DenseMap接口的一个子集。 主要的区别是保证迭代顺序是插入顺序,使其成为指针映射上的非确定性迭代的简单(但有些昂贵)的解决方案。

它是通过在键,值对的向量中从键映射到索引来实现的。 这提供了快速的查找和迭代,但有两个主要的缺点:键存储两次,删除元素需要线性时间。 如果需要删除元素,最好使用remove_if()批量删除它们。

第 78 段(可获 2 积分)

llvm/ADT/IntEqClasses.h

IntEqClasses提供了小整数等价类的压缩表示。 最初,范围0..n-1中的每个整数都有自己的等价类。 可以通过将两个类的代表(representative)传递给join(a,b)方法来连接类。 当findLeader()返回相同的代表时,两个整数位于同一个类中。

一旦形成所有等价类,就可以压缩映射,使每个0..n-1整数映射到0..m-1范围内的等价类编号,其中m是等价类的总数。 必须先解压缩映射,然后才能重新编辑。

第 79 段(可获 2 积分)

llvm/ADT/ImmutableMap.h

ImmutableMap是基于AVL树的不可变(功能)映射实现。 添加或删除元素是通过Factory对象完成的,并导致创建一个新的ImmutableMap对象。 如果已经存在具有给定键集合的ImmutableMap,则返回现有键; 相等性通过与FoldingSetNodeID进行比较。 添加或删除操作的时间和空间复杂度在原始映射的大小上是对数的。

其他Map型容器选项

STL提供了其他几个选项,例如std :: multimap和各种“hash_map”,如容器(不管是从C ++ TR1还是从SGI库)。 我们从不使用hash_set和unordered_set,因为它们通常非常昂贵(每个插入需要一个malloc),非常不便携。

第 80 段(可获 2 积分)

如果你想将一个键映射到多个值,std :: multimap是有用的,但它具有std :: map的所有缺点。 排序向量或其他方法几乎总是更好。

位存储容器(BitVector,SparseBitVector)

与其他容器不同,只有两个位存储容器,并且选择何时使用它们是相对简单的。

另外一个选项是std :: vector <bool>:我们不鼓励使用它有两个原因1)许多常见的编译器(例如GCC的常用版本)中的实现是非常低效的,2)C ++标准委员会可能会弃用该容器和/或显著改变它。 无论如何,请不要使用它。

第 81 段(可获 2 积分)

BitVector

BitVector容器提供了一组动态大小的位操作。 它支持单独的位设置/测试,以及设置操作。 设置操作花费时间O(位向量的大小),但是一次一个字(word)地执行操作,而不是一次一个位。 这使得与其他容器相比,BitVector的设置操作非常快。 当您预计设置位的数量较高时(即密集设置),请使用BitVector。

SmallBitVector

SmallBitVector容器提供与BitVector相同的接口,但它对于仅需要少于25个位的少量位的情况进行了优化。 它也透明地支持较大的位计数,但是比普通的BitVector略低,因此SmallBitVector应该仅在较大的计数很少时使用。

第 82 段(可获 2 积分)

此时,SmallBitVector不支持设置操作(以及或(or)和异或(xor)操作),并且其运算符[]不提供可分配的左值。

SparseBitVector

SparseBitVector容器非常像BitVector,它们之间有一个主要区别:SparseBitVector只存储设置的位。 这使得当集合稀疏时,SparseBitVector比BitVector的空间效率更高,并且使得设置操作的时间复杂度是O(设置的位数)而不是O(总体的大小)。 SparseBitVector的缺点是随机位的设置和测试的时间复杂度是O(N),而在大的SparseBitVectors上,这会比BitVector慢。 在我们的实现中,以排序顺序(前向或反向)设置或测试位最坏的情况的时间复杂度是O(1)。 测试和设置128位(取决于大小)内的当前位的时间复杂度也是O(1)。 作为一般声明,SparseBitVector中的测试/设置位的时间复杂度是O(距离最后一个设置位的距离)。

第 83 段(可获 2 积分)

有用的通用操作提示

本节介绍如何执行一些非常简单的LLVM代码转换。这是为了介绍常见用法的使用案例,展示了LLVM转换的实用性。

因为这是一个“指南(how-to)”部分,你还应该阅读你将要使用的主要类。核心LLVM类层次结构参考包含您应该了解的主要类的详细信息和描述。

基本检查和遍历程序

LLVM编译器基础架构具有许多不同的可能遍历的数据结构。按照C ++标准模板库的例子,用于遍历这些各种数据结构的技术基本相同。对于可枚举的值序列,XXXbegin()函数(或方法)将返回一个指向序列开头的迭代器,XXXend()函数返回一个指向序列的最后一个有效元素的迭代器,还有一些介于这两个操作之间的通用的XXXiterator数据类型。

第 84 段(可获 2 积分)

因为迭代的模式在程序表示的许多不同方面是通用的,所以可以在其上使用标准模板库算法,并且更容易记住如何迭代。 首先,我们将展示一些需要遍历的数据结构的常见示例。 其他数据结构以非常相似的方式遍历。

在函数中迭代BasicBlock

有一个你想以某种方式转换的Function实例是很常见的; 特别是你想操纵它的BasicBlocks。 为了方便起见,您需要遍历构成Function的所有BasicBlocks。 以下是打印BasicBlock的名称及其包含的Instructions个数的示例:

第 85 段(可获 2 积分)
// func is a pointer to a Function instance
for (Function::iterator i = func->begin(), e = func->end(); i != e; ++i)
  // Print out the name of the basic block if it has one, and then the
  // number of instructions that it contains
  errs() << "Basic block (name=" << i->getName() << ") has "
             << i->size() << " instructions.\n";

请注意,可以使用 i 作为一个指针,用于调用Instruction类的成员函数。 这是因为迭代器类的间接寻址运算符被重载。 在上面的代码中,表达式i->size()完全等同于(*i).size(),就像你所期望的那样。

第 86 段(可获 2 积分)

在BasicBlock中迭代指令

就像处理函数中的BasicBlocks一样,可以轻松地迭代构成BasicBlocks的各个指令。 这是一个代码片段,打印出一个BasicBlock中的每个指令:

// blk是一个指向BasicBlock实例的指针
for (BasicBlock::iterator i = blk->begin(), e = blk->end(); i != e; ++i)
   // 下一个语句工作,因为运算符<<(ostream&,...)重载了指令&
   errs() << *i << "\n";

然而,这并不是打印出BasicBlock的内容的最好办法! 由于ostream操作符几乎可以重载为你想要的任何东西,所以你可以在基本块本身调用打印例程:errs()<< * blk <<“\ n”;.

第 87 段(可获 2 积分)

迭代函数中的指令

如果你发现你经常会遍历一个函数的BasicBlocks,然后遍历BasicBlock的指令,那么应该使用InstIterator代替。 您将需要包含llvm/IR/InstIterator.h (doxygen),然后在您的代码中显式实例化InstIterators。 以下是一个小例子,说明如何将函数中的所有指令转储到标准错误流中:  

#include "llvm/IR/InstIterator.h"

// F是一个指向Function实例的指针
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
  errs() << *I << "\n";
第 88 段(可获 2 积分)

这很容易,不是吗? 您还可以使用InstIterator填写其初始内容的工作列表。 例如,如果要初始化一个工作列表以包含函数F中的所有指令,您需要做的就是:

std::set<Instruction*> worklist;
//或者更好的是, SmallPtrSet<Instruction*, 64> worklist;

for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
  worklist.insert(&*I);

STL工作列表现在将包含F指向的函数中的所有指令。

将迭代器转换为类指针(反之亦然)

第 89 段(可获 2 积分)

有时候,当你手头上仅有一个迭代器时,获取一个类实例的引用(或指针)将是有用的。 那么从迭代器中提取一个引用或一个指针就是非常简单的。 假设i是一个BasicBlock::iterator,而j是一个BasicBlock::const_iterator:

Instruction& inst = *i;   // Grab reference to instruction reference
Instruction* pinst = &*i; // Grab pointer to instruction reference
const Instruction& inst = *j;

然而,您将在LLVM框架中使用的迭代器是特殊的:它们将在需要时自动转换为ptr-to-instance类型。 您可以简单地将迭代器分配给适当的指针类型,而不必将迭代器解引用然后获取结果的地址,您通过赋值操作进行解引用和取地址运算(其幕后原理为重载转换机制)。 正如最后一个例子的第二行,

第 90 段(可获 2 积分)
Instruction *pinst = &*i;

在语义上相当于

Instruction *pinst = i;

也可以将类指针转换为相应的迭代器,这是一个恒定的时间操作(非常有效)。 以下代码片段说明了使用由LLVM迭代器提供的转换构造函数。 通过使用这些函数,您可以明确地抓取某些事物的迭代器,而不需要通过某些结构的迭代获取它:

void printNextInstruction(Instruction* inst) {
  BasicBlock::iterator it(inst);
  ++it; // After this line, it refers to the instruction after *inst
  if (it != inst->getParent()->end()) errs() << *it << "\n";
}
第 91 段(可获 2 积分)

不幸的是,这些隐含的转换是有代价的;它们阻止这些迭代器符合标准迭代器约定,并且不能与标准算法和容器一起使用。例如,它们阻止以下代码,其中B是BasicBlock,从编译:

llvm::SmallVector<llvm::Instruction *, 16>(B->begin(), B->end());

因此,这些隐式转换可能会在某天被删除,而operator *更改为返回指针而不是引用。

查找调用函数的位置:一个稍微复杂的例子

假设你正在编写一个FunctionPass,并且想要计算整个模块中的所有位置(即每个函数),其中某个函数(即一些Function *)已经在范围内。稍后您将了解,您可能希望使用InstVisitor以更直接的方式完成此操作,但是,如果您没有使用InstVisitor,则此示例将允许我们探索如何执行此操作。在伪代码中,这是我们想要做的:

第 92 段(可获 2 积分)
initialize callCounter to zero
for each Function f in the Module
  for each BasicBlock b in f
    for each Instruction i in b
      if (i is a CallInst and calls the given function)
        increment callCounter

实际的代码是(记住,因为我们正在编写一个FunctionPass,我们的FunctionPass派生类只需要覆盖runOnFunction方法):

Function* targetFunc = ...;

class OurFunctionPass : public FunctionPass {
  public:
    OurFunctionPass(): callCounter(0) { }

    virtual runOnFunction(Function& F) {
      for (Function::iterator b = F.begin(), be = F.end(); b != be; ++b) {
        for (BasicBlock::iterator i = b->begin(), ie = b->end(); i != ie; ++i) {
          if (CallInst* callInst = dyn_cast<CallInst>(&*i)) {
            // We know we've encountered a call instruction, so we
            // need to determine if it's a call to the
            // function pointed to by m_func or not.
            if (callInst->getCalledFunction() == targetFunc)
              ++callCounter;
          }
        }
      }
    }

  private:
    unsigned callCounter;
};
第 93 段(可获 2 积分)

处理调用(call)和调用(invoke)相同的方式

您可能已经注意到,前面的例子有点过于简单,因为它没有处理由“invoke”指令生成的调用位置。 在这种和其他情况下,您可能会发现要以相同的方式处理CallInsts和InvokeInsts,即使它们最具体的公共基类是Instruction,其中包括了许多不太相关的事情。 对于这些情况,LLVM提供了一个方便的包装类CallSite (doxygen)。它本质上是一个Instruction 指针的包装器,其中一些方法提供了对CALLInsts和InvokeInsts通用的功能。

第 94 段(可获 2 积分)

该类具有“值语义(value semantics)”:应该只传递值,而不是引用给它,不应使用operator new或operator delete进行动态分配或释放。 它的可复制,可分配和可构建非常高效,其成本与裸指针的成本相当。 如果你看看它的定义,它只有一个指针成员。

迭代def-use&use-def链

通常,我们可能有一个Value类(doxygen)的实例,我们想确定哪个用户使用该值。 特定值的所有用户的列表称为def-use链。 例如,假设我们有一个名为F的Function*指向一个特定的函数foo。 查找使用foo的所有指令都像迭代F的def-use一样简单:

第 95 段(可获 2 积分)
Function *F = ...;

for (User *U : F->users()) {
  if (Instruction *Inst = dyn_cast<Instruction>(U)) {
    errs() << "F is used in instruction:\n";
    errs() << *Inst << "\n";
  }

另外,常常有一个用户类(doxygen)的实例,并需要知道它使用什么值。 用户使用的所有值的列表称为use-def链。 类指令的实例是普通用户,因此我们可能需要迭代特定指令使用的所有值(即特定指令的操作数):

第 96 段(可获 2 积分)
Instruction *pi = ...;

for (Use &U : pi->operands()) {
  Value *v = U.get();
  // ...
}

将对象声明为const是实现无突变算法(如分析等)的重要工具。 为了这个目的,上面的迭代器有不同的风格,如Value :: const_use_iterator和Value :: const_op_iterator。 当在const User*的const Value*上调用use/op_begin()时,它们会自动出现。 取消引用后,它们返回const Use*。 否则上述模式保持不变。

Iterating over predecessors & successors of blocks

第 97 段(可获 2 积分)

使用“llvm/IR/CFG.h”中定义的例程来迭代块的前导和后继是非常容易的。 只需使用这样的代码遍历BB的所有前辈:

#include "llvm/Support/CFG.h"
BasicBlock *BB = ...;

for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
  BasicBlock *Pred = *PI;
  // ...
}

同样,为了迭代继承者,使用succ_iterator/succ_begin/succ_end。

做简单的改变

在LLVM基础设施中存在一些值得了解的原始转换操作。 在执行转换时,操作基本块的内容是相当常见的。 本节介绍一些常用的方法,并提供示例代码。

第 98 段(可获 2 积分)

创建和插入新的指令

实例化指令

创建指令是直截了当的:只需调用构造函数进行实例化并提供必要的参数。 例如,AllocaInst只需要一个(const-ptr-to)类型。 从而:

AllocaInst* ai = new AllocaInst(Type::Int32Ty);

创建一个AllocaInst实例表示在运行时在当前堆栈帧中分配一个整数。 每个指令子类都可能有不同的默认参数,这些参数会改变指令的语义,因此请参考doxygen文档,了解您想要实例化的指令子类

第 99 段(可获 2 积分)

命名值

当您能够命名指令的值时,这是非常有用的,因为这有助于您的转换的调试。 当你在最后查看生成的LLVM机器代码,你肯定想要与指令结果相关联的逻辑名称! 通过提供指令构造函数的Name(默认)参数的值,可以将逻辑名称与运行时指令执行结果相关联。 例如,我正在编写一个转换,为堆栈上的整数动态分配空间,并且该整数将被某些其他代码用作某种索引。 为了实现这一点,我在某个函数的第一个BasicBlock的第一个位置放入一个AllocaInst,我打算在同一个函数中使用它。 我可能这样做:

第 100 段(可获 2 积分)
AllocaInst* pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc");

其中,indexLoc现在是指令执行值的逻辑名,它是一个指向运行时栈中的整数的指针。

插入指令

基本上有三种方式将指令插入到形成BasicBlock的现有指令序列中:

  • 插入显式指令列表

    给定一个BasicBlock * pb,一个BasicBlock中的Instruction* pi,以及我们希望在* pi之前插入的新创建的指令,我们执行以下操作:

    BasicBlock *pb = ...;
    Instruction *pi = ...;
    Instruction *newInst = new Instruction(...);
    
    pb->getInstList().insert(pi, newInst); //在pb之前插入newInst
    

    附加到BasicBlock的结尾是如此的普遍,以至于指令类和指令派生类提供了构造函数,该构造函数将指向要附加到的BasicBlock的指针。例如,代码看起来像这样:

    BasicBlock *pb = ...;
    Instruction *newInst = new Instruction(...);
    
    pb->getInstList().push_back(newInst); // 将newInst追加到pb
    

    就变成了:

    BasicBlock *pb = ...;
    Instruction *newInst = new Instruction(..., pb);
    

    这更整洁,特别是当如果你正在创建长指令流时。

  • 插入隐式指令列表

    已经在BasicBlocks中的指令实例与现有指令列表隐含关联:封闭基本块的指令列表。因此,我们可以通过如下方式,完成与上述代码相同的事情,而不必给定一个BasicBlock:

    Instruction *pi = ...;
    Instruction *newInst = new Instruction(...);
    
    pi->getParent()->getInstList().insert(pi, newInst);
    

    实际上,这个步骤顺序如此频繁地发生,使得指令类和指令派生类提供了构造函数,该构造函数接收一个指向指令的指针(作为默认参数),新创建的指令应该在之前发生。也就是说,指令构造函数能够在该指令之前将新创建的实例插入到提供的指令的BasicBlock中。使用具有insertBefore(default)参数的指令构造函数,上述代码变为:

    Instruction* pi = ...;
    Instruction* newInst = new Instruction(..., pi);
    

    这更整洁,特别是当如果您创建了大量指令并将其添加到BasicBlocks时。

  • 使用IRBuilder的一个实例插入

    使用以前的方法插入一些指令可能非常费力。 IRBuilder是一个方便的类,可以用于在一个BasicBlock的末尾或特定的指令之前添加几个指令。它还支持常规折叠和重命名命名寄存器(请参阅IRBuilder的模板参数)。

    下面的例子简单地演示了IRBuilder的使用,在指令pi之前插入了三条指令。前两个指令是调用指令,第三个指令将两个调用的返回值相乘。

    Instruction *pi = ...;
    IRBuilder<> Builder(pi);
    CallInst* callOne = Builder.CreateCall(...);
    CallInst* callTwo = Builder.CreateCall(...);
    Value* result = Builder.CreateMul(callOne, callTwo);
    

    下面的示例类似于上述示例,除了创建的IRBuilder在BasicBlock pb的末尾插入指令。

    BasicBlock *pb = ...;
    IRBuilder<> Builder(pb);
    CallInst* callOne = Builder.CreateCall(...);
    CallInst* callTwo = Builder.CreateCall(...);
    Value* result = Builder.CreateMul(callOne, callTwo);
    

    参见千变万化:代码生成LLVM IR,实际使用IRBuilder。

第 101 段(可获 2 积分)

删除指令

从构成BasicBlock的现有指令序列中删除指令非常简单:只需调用指令的eraseFromParent()方法即可。 例如:

Instruction *I = .. ;
I->eraseFromParent();

这将解除指令与其包含的基本块的关联,并将其删除。 如果您只想从其包含的基本块中取消链接,但不删除它,则可以使用theremoveFromParent()方法。

用另一个值代替指令

更换单独的指令

包含“llvm/Transforms/Utils/BasicBlockUtils.h”允许您使用两个非常有用的替换函数:ReplaceInstWithValue和ReplaceInstWithInst。

第 102 段(可获 2 积分)
删除指令
  • ReplaceInstWithValue

    此函数用一个值替换给定指令的所有使用,然后删除原始指令。 以下示例说明了替换特定AllocaInst(为单个整数分配一个空整数指针的内存)的结果。

    AllocaInst* instToReplace = ...;
    BasicBlock::iterator ii(instToReplace);
    
    ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
                         Constant::getNullValue(PointerType::getUnqual(Type::Int32Ty)));
    
  • ReplaceInstWithInst

    该函数将特定指令替换为另一条指令,将新指令插入到旧指令位置的基本块中,并用新指令替换旧指令的任何用法。 以下示例说明了一个AllocaInst与另一个AllocaInst的替换。

    AllocaInst* instToReplace = ...;
    BasicBlock::iterator ii(instToReplace);
    
    ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii,
                        new AllocaInst(Type::Int32Ty, 0, "ptrToReplacedInt"));
    
第 103 段(可获 2 积分)
替换用户和值的多种使用

您可以使用Value :: replaceAllUsesWith和User :: replaceUsesOfWith一次更改多个使用。 有关更多信息,请参见有关 Value Class 和 User Class 的doxygen文档。

删除全局变量

从模块中删除全局变量与删除指令一样简单。 首先,您必须有一个指向要删除的全局变量的指针。 你可以使用这个指针从它的父模块中删除它。 例如:

GlobalVariable *GV = .. ;

GV->eraseFromParent();
第 104 段(可获 2 积分)

如何创建类型

在生成IR时,可能需要一些复杂的类型。 如果您静态地了解这些类型,您可以使用在llvm/Support/TypeBuilder.h中定义的TypeBuilder <...> :: get()来得到它们。TypeBuilder有两种形式,具体取决于您正在构建交叉编译或本地库使用。 TypeBuilder <T,true>要求T独立于主机环境,这意味着它是从llvm::types (doxygen) 命名空间的类型和由它们构建的指针,函数,数组等构建的。 TypeBuilder <T,false>还允许大小可能取决于主机编译器的本地C类型。 例如,

第 105 段(可获 2 积分)
FunctionType *ft = TypeBuilder<types::i<8>(types::i<32>*), true>::get();

与同等的操作相比读写更容易

std::vector<const Type*> params;
params.push_back(PointerType::getUnqual(Type::Int32Ty));
FunctionType *ft = FunctionType::get(Type::Int8Ty, params, false);

有关详细信息,请参阅类注释

线程和LLVM

本节介绍了LLVM API与客户端应用程序的多线程以及托管应用程序中JIT的交互。

请注意,LLVM对多线程的支持时间不长。 通过版本2.5,支持线程托管应用程序的执行,但不是线程客户端访问API。 虽然现在支持此用例,但客户端必须遵守以下指导原则,以确保在多线程模式下正常运行。

第 106 段(可获 2 积分)

请注意,在Unix平台上,LLVM需要GCC的原子内部函数才能支持线程操作。 如果在没有适当的现代系统编译器的平台上需要具有多线程功能的LLVM,请考虑以单线程模式编译LLVM和LLVM-GCC,并使用最终的编译器构建具有多线程支持的LLVM副本。

结束执行与llvm_shutdown()

当您完成使用LLVM API后,您应该调用llvm_shutdown()来释放用于内部结构的内存。

延迟初始化与ManagedStatic

第 107 段(可获 2 积分)

ManagedStatic是LLVM中的一个实用程序类,用于实现静态资源的静态初始化,例如全局类型表。 在单线程环境中,它实现了一个简单的延迟初始化方案。 然而,当LLVM被编译支持多线程时,它使用双重检查的锁定来实现线程安全的延迟初始化。

用LLVMContext实现隔离

LLVMContext是LLVM API中的不透明类,客户端可以在同一地址空间中同时操作多个独立的LLVM实例。 例如,在假设的编译服务器中,单个翻译单元的编译在概念上独立于所有其他翻译单元,并且期望能够在独立的服务器线程上同时编译传入的翻译单元。 幸运的是,LLVMContext的存在实现了这种场景!

第 108 段(可获 2 积分)

从概念上讲,LLVMContext提供隔离。 LLVM的内存IR中的每个LLVM实体(模块,值,类型,常量等)属于LLVMContext。 不同上下文中的实体不能相互交互:不同上下文中的模块不能链接在一起,不能将函数添加到不同上下文中的模块等。这意味着可以同时编译多个线程,只要两个线程不会对相同上下文中的实体同时进行操作。

实际上,除了Type创建/查找API之外,API中很少有地方需要明确指定LLVMContext。 因为每个类型都引用了自己的上下文,大多数其他实体可以通过查看自己的Type来确定它们属于哪个上下文。 如果要向LLVM IR添加新实体,请尝试维护此接口设计。

第 109 段(可获 2 积分)

线程和JIT

LLVM的“eager”JIT编译器可以安全地在线程程序中使用。 多个线程可以并发调用ExecutionEngine :: getPointerToFunction()或ExecutionEngine :: runFunction(),并且多个线程可以同时运行JIT输出的代码。 用户必须确保只有一个线程在给定的LLVMContext中访问IR,与此同时另一个线程可能会修改它。 一种方法是在JIT外部访问IR时始终保持JIT锁(JIT通过添加CallbackVH来修改IR)。 另一种方法是只从LLVMContext的线程调用getPointerToFunction()。

第 110 段(可获 2 积分)

当JIT配置为懒编译(使用ExecutionEngine :: DisableLazyCompilation(false))时,在函数懒编译(lazily-jitted)更新调用站点之后,会有一个竞争条件。 如果您确保每次只有一个线程可以调用任何特定的懒惰存根( lazy stub),并且JIT锁保护任何IR访问,仍然可以在线程程序中使用懒的JIT,但是我们建议在线程程序中仅使用急切的JIT(eager JIT)。

高级主题

本节介绍了大多数客户端不需要注意的一些高级或晦涩的API。 这些API倾向于管理LLVM系统的内部工作,只需要在异常情况下进行访问。

第 111 段(可获 2 积分)

ValueSymbolTable类

ValueSymbolTable(doxygen)类提供了FunctionModule类用于命名值定义的符号表。 符号表可以为任何提供名称。

请注意,大多数客户端不应该直接访问SymbolTable类。 只有当需要迭代符号表名称时,才应该使用它,这是非常特殊的用途。 请注意,并不是所有的LLVM都有名称,那些没有名称(即它们具有空名称)的符号表不存在。

符号表支持使用begin / end / iterator对符号表中的值进行迭代,并支持查询是否在符号表中具有特定名称(使用lookup)。 TheValueSymbolTable类不会公开public mutator方法,而是简单地在一个值上调用setName,它将自动插入到适当的符号表中。

第 112 段(可获 2 积分)

User 和拥有Use类的内存布局

User (doxygen)类为表达User对其他Value实例的所有权提供了基础。 Use (doxygen) 辅助类用于登记,以便于 O(1) 添加和删除。

User 和 Use 对象之间的交互和关系

User 的子类可以在包含其Use 对象之间进行选择,或者通过指针引用它们。 混合变体(一些Use 与其他 Use 内联挂载)是不切实际的,并且打破了属于同一User的Use对象形成连续数组的不变量。

第 113 段(可获 2 积分)

User (子)类中有两种不同的布局:

  • 布局 a)

    Use 对象位于User对象的内部(相当于固定的偏移量),并且它们的数量固定。

  • 布局 b)

    Use 对象由User对象引用到数组的指针,并且其数量可变。

从v2.4开始,每个布局仍然有一个直接指向Use数组的开头的指针。 虽然布局a)不是强制性的,但为了简单起见,我们坚持这种冗余。 User对象还存储它拥有的Use对象的数量。 (理论上,这个信息也可以根据下面给出的方案进行计算。)

第 114 段(可获 2 积分)

特殊形式的分配运算符(operator new)强制执行以下内存布局:

  • 布局a)通过使用Use []数组预先添加User对象进行建模。

    ...---.---.---.---.-------...
      | P | P | P | P | User
    '''---'---'---'---'-------'''
    
  • 布局b)通过指向Use []数组来建模。

    .-------...
    | User
    '-------'''
        |
        v
        .---.---.---.---...
        | P | P | P | P |
        '---'---'---'---'''
    

(在上图中,'P'表示存储在成员Use :: Prev中的每个Use对象中的Use **)

路标算法(waymarking algorithm)

由于Use对象被剥夺了直接(返回)指向他们的User对象的指针,因此必须有一个快速准确的方法来恢复它。 这是通过以下方案实现的:

Use :: Prev的2个LSB(最低有效位)中的位编码可以查找User对象的开始:

第 115 段(可获 2 积分)
  • 00 - 二进制数字0
  • 01 - 二进制数1
  • 10 - 停止并计算(s)
  • 11 - 全停(S)

给定一个Use*,我们要做的就是不断遍历直到我们遇到停止(stop)而且立即在其后获得一个User ,或者我们必须遍历到下一个停止,并计算这些数字的偏移量:

.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
| 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*)
'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
    |+15                |+10            |+6         |+3     |+1
    |                   |               |           |       | __>
    |                   |               |           | __________>
    |                   |               | ______________________>
    |                   | ______________________________________>
    | __________________________________________________________>
第 116 段(可获 2 积分)

只有有意义的位需要在停止之间存储,所以当有1000个Use 对象与User相关联时,最坏的情况是有20个存储器访问

参考实现

以下Haskell代码片段演示了以上概念:

> import Test.QuickCheck
>
> digits :: Int -> [Char] -> [Char]
> digits 0 acc = '0' : acc
> digits 1 acc = '1' : acc
> digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc
>
> dist :: Int -> [Char] -> [Char]
> dist 0 [] = ['S']
> dist 0 acc = acc
> dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r
> dist n acc = dist (n - 1) $ dist 1 acc
>
> takeLast n ss = reverse $ take n $ reverse ss
>
> test = takeLast 40 $ dist 20 []
>
第 117 段(可获 2 积分)

打印<test>给出:“1s100000s11010s10100s1111s1010s110s11s1S”

反向算法通过检查某个前缀来计算字符串的长度:

> pref :: [Char] -> Int
> pref "S" = 1
> pref ('s':'1':rest) = decode 2 1 rest
> pref (_:rest) = 1 + pref rest
>
> decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest
> decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
> decode walk acc _ = walk + acc
>

现在,如预期的那样,打印<pref test>给出了40。

我们可以使用以下属性来快速检查

> testcase = dist 2000 []
> testcaseLength = length testcase
>
> identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr
>     where arr = takeLast n testcase
>
第 118 段(可获 2 积分)

正如预期的那样<quickCheck identityProp>给出:

*Main> quickCheck identityProp
OK, passed 100 tests.

让我们更详尽一点:

>
> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
>

这是 <deepCheck identityProp>的结果:

*Main> deepCheck identityProp
OK, passed 500 tests.

标记注意事项

为了保持不变,在使用中的每个Use**的2个LSBit 在设置后永远不会改变,Use :: Prev的setter必须在每次修改时重新标记新的Use **。 相应的getter必须剥离标签位。

对于布局b)我们找到一个指针(具有LSBit 设置的User*)代替User 。 这个指针带给我们User。 便携式技巧确保User的第一个字节(如果被解释为指针)从来没有设置LSBit。 (可移植性依赖于所有已知的编译器都将vptr放在实例的第一个字(word)中。)

第 119 段(可获 2 积分)

设计类型层次结构和多态接口

有两种不同的设计模式倾向于导致在C++程序中的类型层次结构中使用虚拟调度方法。第一个是真正的类型层次结构,层次结构中的不同类型模拟功能和语义的特定子集,并且这些类型严格地嵌套在彼此中。在“值(Value )”或“类型(Type )”类型层次结构中可以看到很好的例子。

第二个是在多态接口实现集合中动态调度的愿望。后一种用例可以通过定义一个抽象接口基类来实现派生和覆盖的虚拟调度和继承来建模。然而,这种实施策略强制存在一个“类继承is-a)”关系,实际上并不是有意义的。通常没有一些嵌套层次结构的有用的fan,使得代码可以与上下文相互作用和上下移动。相反,有一个单一的接口被分派到一系列的实现。

第 120 段(可获 2 积分)

第二种使用情况的首选实现策略是泛型编程(有时称为“编译时鸭型(compile-time duck typing)”或“静态多态”)。例如,可以跨符合接口或概念(concept)的任何特定实现来实例化某种类型参数T上的模板。这里的一个很好的例子是任何类型的高度泛化的属性,它在有向图中对节点进行建模。主要通过模板和泛型编程来实现LLVM。这样的模板包括LoopInfoBase和DominatorTreeBase。当这种类型的多态性真正需要动态调度时,您可以使用称为基于概念的多态性( concept-based polymorphism)的技术来概括它。此模式使用非常有限的虚拟调度形式模拟模板的接口和行为,以实现其中的类型擦除。您可以在PassManager.h系统中找到此技术的示例,Sean Parent在其几次讲话和论文中对此进行了更详细的介绍:

第 121 段(可获 2 积分)
  1. 继承是邪恶的基类 - GoingNative 2013大会描述了这种技术,这儿也可能是你开始的最好的地方。
  2. 值语义和基于概念的多态 - C++ Now! 2012年更详细地描述了这种技术。
  3. 肖恩父母的论文和演示文稿 - 一个Github项目,其中包含了对幻灯片,视频,有时是代码的链接。

在确定创建类型层次结构(带标记或虚拟调度)和使用模板或基于概念的多态时,请考虑是否在接口边界上有一个语义上有意义的类型的抽象基类的一些细化。 作为语义模型的部分扩展,如果任何比根抽象接口更精细的谈论都是无意义的,那么您的用例可能更适合多态,您应该避免使用虚拟调度。 然而,可能存在一些需要使用一种或另外一种技术的紧急情况。

第 122 段(可获 2 积分)

如果您需要引入类型层次结构,我们更愿意使用手动标记调度和/或RTTI的明确闭合类型层次结构,而不是C ++代码中更常见的开放继承模型和虚拟调度。 这是因为LLVM很少鼓励库使用者扩展其核心类型,并利用其层次结构的封闭和标签调度特性来生成明显更高效的代码。 我们还发现,大量的类型层次结构的使用更适合基于标签的模式匹配,而不是通过公共接口进行动态调度。 在LLVM中,我们已经构建了自定义的帮助器来促进这种设计。 请参阅本文档关于isa和dyn_cast的部分以及我们介绍如何实现此模式以用于LLVM助手的详细文档

第 123 段(可获 2 积分)

ABI中断检查

检查和断言更改LLVM C++ ABI基于预处理器符号LLVM_ENABLE_ABI_BREAKING_CHECKS - 使用LLVM_ENABLE_ABI_BREAKING_CHECKS构建的LLVM库不是在没有定义的情况下构建ABI兼容的LLVM库。 默认情况下,打开断言也会打开LLVM_ENABLE_ABI_BREAKING_CHECKS,因此默认的+Asserts构建不会与默认的-Asserts构建ABI兼容。 要求+Asserts和-Asserts构建之间的ABI兼容性的客户端应使用CMake或autoconf构建系统来设置LLVM_ENABLE_ABI_BREAKING_CHECKS独立于LLVM_ENABLE_ASSERTIONS。

第 124 段(可获 2 积分)

核心LLVM类层次结构参考

#include "llvm/IR/Type.h"

头文件来源:Type.h

doxygen信息:类型Clases

核心LLVM类是表示被检查或转换的程序的主要手段。 核心LLVM类在include/llvm/IR目录中的头文件中定义,并在lib/IR目录中实现。 值得注意的是,由于历史原因,此库称为libLLVMCore.so,而不是你可能以为的libLLVMIR.so。

类型(Type)类和派生类型

Type是所有类型类的超类。 每个值(Value)都有一个类型。 类型不能直接实例化,只能通过其子类实例化。 某些原始类型(VoidType,LabelType,FloatType和DoubleType)具有隐藏的子类。 它们是隐藏的,因为除了将类与其他子类区分开以外,它们不提供类型类所提供的有用功能。

第 125 段(可获 2 积分)

所有其他类型都是DerivedType的子类。 类型可以命名,但这不是必需的。 任何一个时刻都只有一个给定形状的实例。 这可以使用类型实例的地址相等来判断类型相等。 也就是说,给定两个Type*值,如果指针相同,那么类型是相同的。

重要的公共方法

  • bool isIntegerTy()const:对任何整数类型返回true。
  • bool isFloatingPointTy():如果这是五个浮点类型之一,则返回true。
  • bool isSized():如果类型已知大小,则返回true。 那些没有大小的是抽象类型,标签和void。
第 126 段(可获 2 积分)

重要衍生类型

整数类型(IntegerType)

DerivedType的子类,表示任何位宽的整数类型。 可以表示IntegerType::MIN_INT_BITS(1和IntegerType::MAX_INT_BITS(〜800万)之间的位宽。

  • static const IntegerType * get(unsigned NumBits):获取特定位宽的整数类型。
  • unsigned getBitWidth()const:获取整数类型的位宽度。

顺序类型(SequentialType)

这是由ArrayType,PointerType和VectorType创建的子类。

  • const Type * getElementType()const:返回顺序类型中每个元素的类型。
第 127 段(可获 2 积分)

数组类型(ArrayType)

这是SequentialType的子类,并定义了数组类型的接口。

  • unsigned getNumElements() const: 返回数组中的元素个数。

指针类型(PointerType)

指针类型的SequentialType子类。

向量类型(VectorType)

SequentialType的子类用于向量类型。 向量类型类似于ArrayType,他们的区别是向量类型是第一类类型而ArrayType不是。 向量类型用于向量操作,通常是整数或浮点类型的小向量。

结构体类型(StructType)

用于结构体类型的DerivedTypes子类。

第 128 段(可获 2 积分)

函数类型(FunctionType)

DerivedTypes类的子类用于函数类型。

  • bool isVarArg() const: 如果它是一个vararg函数,则返回true。
  • const Type * getReturnType() const: 返回函数的返回类型。
  • const Type * getParamType (unsigned i): 返回第i个参数的类型。
  • const unsigned getNumParams() const: 返回形式参数的数量。

Module类

#include "llvm/IR/Module.h"

头文件来源: Module.h

doxygen信息: 模块类

Module类代表LLVM程序中的顶级结构。 LLVM模块实际上是原始程序的翻译单元或由链接器合并的多个翻译单元的组合。 Module类跟踪一个 Function 列表,一个 GlobalVariable列表和一个SymbolTable。 此外,它还包含一些有用的成员函数,可以使常用操作变得简单。

第 129 段(可获 2 积分)

Module类的重要公共成员

  • Module::Module(std::string name = "")

    构建模块很容易。 您可以选择为其提供名称(可能是基于翻译单元的名称)。

  • Module::iterator - 用于函数列表迭代器的Typedef

    Module::const_iterator - 用于const_iterator的Typedef。

    begin()end()size()empty()

    这些是转发方法,可以轻松访问Module对象的Function列表的内容。

  • Module::FunctionListType &getFunctionList()

    返回函数列表。 当需要更新列表或执行没有转发方法的复杂操作时,这是必要的。

第 130 段(可获 2 积分)
  • Module::global_iterator - 用于全局变量列表迭代器的Typedef

    Module::const_global_iterator - 用于const_iterator的Typedef。

    global_begin()global_end()global_size()global_empty()

    这些是转发方法,可以轻松访问Module对象的GlobalVariable列表的内容。

  • Module::GlobalListType &getGlobalList()

    返回 GlobalVariable的列表。 当需要更新列表或执行没有转发方法的复杂操作时,这是必要的。

  • SymbolTable *getSymbolTable()

    返回对本模块的SymbolTable的引用。

第 131 段(可获 2 积分)
  • Function *getFunction(StringRef Name) const

    在Module SymbolTable中查找指定的函数。 如果不存在,返回null。

  • Function *getOrInsertFunction(const std::string &Name, const FunctionType *T)

    在Module  SymbolTable中查找指定的函数。 如果不存在,请为函数添加外部声明并返回。

  • std::string getTypeName(const Type *Ty)

    如果指定 Type 的 SymbolTable中至少有一个条目,则返回。 否则返回空字符串。

  • bool addTypeName(const std::string &Name, const Type *Ty)

    SymbolTable映射名称中的条目插入到Ty。 如果已经有这个名称的条目,则返回true并且不修改SymbolTable

第 132 段(可获 2 积分)

Value类

#include "llvm/IR/Value.h"

头文件来源:Value.h

doxygen信息: Value Class

Value类是LLVM源代码中最重要的类。 它表示可以用于(其他事物之中)作为指令的操作数的类型值。 有许多不同类型的值,如常量(Constant),参数(Argument)。 即使指令(Instruction)和函数(Function)也是值。

特定值可能在程序的LLVM表示中被多次使用。 例如,引用参数的函数中的每个指令都“使用”函数的传入参数(由Argument类的实例表示)。 为了跟踪这种关系,Value类保留所有正在使用它的User的列表(User类是LLVM图中可以引用值的所有节点的基类)。 这个使用列表就是LLVM在程序中表示def-use信息的方式,并且可以通过use_ *方法访问,如下所示。

第 133 段(可获 2 积分)

因为LLVM是一个类型化的表示,所以每个LLVM值都是一种类型,而此类型可以通过getType()方法获得。 此外,所有LLVM值都可以命名。 值的“name”是打印在LLVM代码中的符号字符串:

%foo = add i32 1, 2

该指令的名称是“foo”。 请注意,任何值的名称可能会丢失(一个空字符串),因此,名称能用于调试(使源代码更容易阅读,调试打印输出),它们不应用于跟踪值或在它们之间映射。 为此,请使用指向Value本身的指针的std::map。

第 134 段(可获 2 积分)

LLVM的一个重要特点是SSA变量与产生它的操作之间没有区别。因此,对指令产生的值的引用(例如,作为传入参数可用的值)都被表示为指向表示该值的类的实例的直接指针。虽然这可能需要一些时间来适应,但它简化了表示,并使操作更容易。

值类的重要公众成员

  • Value::use_iterator - 用于use-list上的迭代器的类型定义

    Value::const_use_iterator - 用于use-list上的const_iterator的类型定义

    unsigned use_size() - 返回值的用户数量。

    bool use_empty() - 如果没有用户,则返回true。

    use_iterator use_begin() - 获取use-list开头的迭代器。

    use_iterator use_end() - 获取use-list结尾的迭代器。

    User *use_back() - 返回列表中的最后一个元素。

    这些方法是访问LLVM中的def-use信息的接口。与LLVM中的所有其他迭代器一样,命名约定遵循STL定义的约定。

  • Type *getType() const 此方法返回值的类型。

  • bool hasName() const

    std::string getName() const

    void setName(const std::string &Name)

    该系列方法用于访问和分配名称给值,请注意上述注意事项

  • void replaceAllUsesWith(Value *V)

    该方法通过将所有用户的当前值指向“V”来遍历值的使用列表。例如,如果您检测到指令总是产生常量值(例如通过常数合并),则可以用常量替换指令的所有用法:

    Inst->replaceAllUsesWith(ConstVal);
    
第 135 段(可获 2 积分)

User类

#include "llvm/IR/User.h"

头文件来源:User.h

doxygen信息:User Class

超类:Value

User类是可以引用Value的所有LLVM节点的公共基类。 它公开了“操作数”的列表,它们是User所指的所有Value。 User类本身是Value的子类。

用户的操作数直接指向它引用的LLVM Value。 因为LLVM使用静态单一分配(SSA)形式,所以只能有一个定义,允许这种直接连接。 此连接在LLVM中提供use-def信息。

第 136 段(可获 2 积分)

User类的重要公共成员

User类以两种方式公开操作数列表:通过索引访问接口和基于迭代器的接口。

  • Value *getOperand(unsigned i)

    unsigned getNumOperands()

    这两种方法以方便的形式暴露用户的操作数,以便直接访问。

  • User::op_iterator - 用于操作数列表上的迭代器的Typedef

    op_iterator op_begin() - 获取操作数列表开头的迭代器。

    op_iterator op_end() - 获取操作数列表末尾的迭代器。

    这些方法一起组成了用户操作数的基于迭代器的接口。

第 137 段(可获 2 积分)

指令类

#include "llvm/IR/Instruction.h"

头文件来源: Instruction.h

doxygen信息: Instruction Class

父类: UserValue

指令类是所有LLVM指令的公共基类。它只提供几种方法,但是是一个非常常用的类。指令类本身跟踪的主要数据是操作码(指令类型)和指令嵌入的父BasicBlock。为了表示特定类型的指令,可以使用指令的子类。

因为指令类是User类的子类,所以其操作数可以以与其他User类相同的方式进行访问(使用getOperand()/getNumOperands()和 op_begin()/op_end()方法)。指令类的一个重要文件是llvm/Instruction.def文件。该文件包含有关LLVM中各种不同类型指令的元数据。它描述了用作操作码(例如Instruction::Add和Instruction::ICmp)的枚举值以及实现指令的指令的具体子类(例如BinaryOperator和 CmpInst)。不幸的是,在这个文件中使用宏会混淆doxygen,所以这些枚举值在doxygen输出中没有正确显示。

第 138 段(可获 2 积分)

Instruction 类的重要子类

  • BinaryOperator

    该子类表示所有那些其操作数必须是相同类型的两个操作数指令,但比较指令除外。

  • CastInst 这个子类是12个转换指令的父类。 它提供了转换指令的常见操作。
  • CmpInst

    该子类表示两个比较指令ICmpInst(整数操作数)和FCmpInst(浮点操作数)。

  • TerminatorInst

    这个子类是所有终止符指令的父类(可以终止块的那些)。

第 139 段(可获 2 积分)

nstruction 类的重要公有成员

  • BasicBlock *getParent()

    返回此Instruction嵌入的BasicBlock

  • bool mayWriteToMemory()

    如果指令写入内存,则返回true,即它是一个调用(call),释放(free),调用(invoke)或存储(store)。

  • unsigned getOpcode()

    返回Instruction的操作码。

  • Instruction *clone() const

    返回指定指令的另一个实例,除了该指令没有父进程(即它没有嵌入到BasicBlock中),并且没有名称外,其他的都与原始实例相同。

Constant类和子类

第 140 段(可获 2 积分)

常量表示不同类型常量的基类。它继承了ConstantInt,ConstantArray等,用于表示各种类型的常量。 GlobalValue也是一个子类,它表示全局变量或函数的地址。

常数的重要子类  

  • ConstantInt : Constant的这个子类表示任何宽度的整数常数。
    • const APInt& getValue() const: 返回此常量的底层值,一个APInt值。
    • int64_t getSExtValue() const: 通过符号扩展将底层APInt值转换为int64_t。如果APInt的值(而不是位宽)太大,不适合int64_t,则会产生断言。因此,不鼓励使用此方法。
    • uint64_t getZExtValue() const: 通过零扩展将底层APInt值转换为uint64_t。如果APInt的值(不是位宽)太大,不能适应uint64_t,则会导致断言。因此,不鼓励使用此方法。
    • static ConstantInt* get(const APInt& Val): 返回表示Val提供的值的ConstantInt对象。该类型表示为与Val的位宽对应的IntegerType。
    • static ConstantInt* get(const Type *Ty, uint64_t Val): 返回ConstantInt对象,该对象代表Val为整数类型Ty提供的值。
  • ConstantFP : 此类表示浮点常量。
    • double getValue() const: 返回此常量的基础值。
  • ConstantArray :表示一个常量数组。
    • const std::vector<Use> &getValues() const: 返回构成该数组的组件常量向量。
  • ConstantStruct : 这是一个常量结构体。
    • const std::vector<Use> &getValues() const: 返回构成该数组的组件常量向量。
  • GlobalValue : 表示全局变量或函数。在任何一种情况下,该值都是一个常数固定地址(链接后)。
第 141 段(可获 2 积分)

GlobalValue 类

#include "llvm/IR/GlobalValue.h"

头文件来源: GlobalValue.h

doxygen信息: GlobalValue Class

父类: ConstantUserValue

全局值(GlobalVariable 或 Function)是在所有函数体中可见的唯一LLVM值。 因为它们在全局范围内是可见的,所以它们还要遵守与其他不同的翻译单元中定义的全局链接。 为了控制链接过程,GlobalValue知道它们的链接规则。 具体来说,GlobalValues知道它们是否具有由LinkageTypes枚举定义的内部或外部链接。

第 142 段(可获 2 积分)

如果GlobalValue具有内部链接(相当于C中的静态),则在当前翻译单元之外的代码不可见,并且不参与链接。如果它具有外部链接,它对外部代码是可见的,并且参与链接。除了链接信息之外,GlobalValues还会跟踪他们当前所在的模块

因为GlobalValues是内存对象,所以它们总是被它们的地址引用。因此,全局的类型总是指向其内容的指针。使用GetElementPtrInst指令时,请务必记住这一点,因为这个指针必须先被解引用。例如,如果您有一个GlobalVariable(它是一个GlobalValue的子类),它是一个24个int型数组,类型为[24 x i32],那么GlobalVariable就是一个指向该数组的指针。虽然这个数组的第一个元素的地址和GlobalVariable的值是相同的,但是它们的类型不同。 GlobalVariable的类型是[24 x i32]。第一个元素的类型是i32。因此,访问全局值需要首先使用GetElementPtrInst解引用指针,然后可以访问其元素。这在“LLVM语言参考手册”中进行了说明。

第 143 段(可获 2 积分)

GlobalValue 类的重要公共成员

  • bool hasInternalLinkage() const

    bool hasExternalLinkage() const

    void setInternalLinkage(bool HasInternalLinkage)

    这些方法控制GlobalValue的连接特征。

  • Module *getParent()

    这将返回当前嵌入到GlobalValue的模块

Function 类

#include "llvm/IR/Function.h"

头文件来源: Function.h

doxygen信息: Function Class

父类: GlobalValueConstantUserValue

Function类表示LLVM中的单个过程。 它实际上是LLVM层次结构中更复杂的类之一,因为它必须跟踪大量的数据。 该Function类跟踪BasicBlock的列表,一个形式参数列表和一个符号表(SymbolTable)。

第 144 段(可获 2 积分)

BasicBlock列表是Function对象中最常用的部分。该列表对函数中的块进行了隐式排序,指示代码将如何由后端布局。另外,第一个BasicBlock是Function的隐式入口节点。 在LLVM中明确分支到这个初始块是不合法的。 没有隐式的退出节点,实际上可能有单个函数的多个退出节点。 如果BasicBlock列表为空,则表示该函数实际上是一个函数声明:该函数的实体尚未链接。

第 145 段(可获 2 积分)

除了BasicBlock列表之外,Function类还跟踪函数接收到的形式参数的列表。 该容器管理参数节点的生命周期,就像 BasicBlock列表对 BasicBlock一样。

SymbolTable是一种很少使用的LLVM功能,仅在您必须按名称查找值时才使用。 除此之外,SymbolTable在内部使用,以确保函数体中的指令, BasicBlock参数的名称之间不存在冲突。

请注意,Function是一个全局值(GlobalValue),因此也是一个常量(Constant.)。 函数的值是它的地址(链接之后),它被保证是不变的。

第 146 段(可获 2 积分)

函数(Function)的重要公众成员

  • Function(const FunctionType *Ty, LinkageTypes Linkage, const std::string &N = "", Module* Parent = 0)

    构造函数用于当您需要创建新的函数来添加程序。构造函数必须指定要创建的函数的类型以及函数应具有的连接类型。 函数类型参数指定函数的形式参数和返回值。可以使用相同的函数类型值来创建多个函数。 Parent参数指定定义函数的模块。如果提供此参数,该函数将自动插入到该模块的函数列表中。

  • bool isDeclaration()

    返回函数是否​​定义了一个主体。如果函数为“外部”,则该函数不具有主体,因此必须通过与不同翻译单元中定义的函数进行链接来解决。

  • Function::iterator - 用于基本块列表迭代器的类型定义

    Function::const_iterator - 用于const_iterator的类型定义.

    begin()end()size()empty()

    这些是转发方法,可以方便地访问函数对象的BasicBlock列表的内容。

  • Function::BasicBlockListType &getBasicBlockList()

    返回BasicBlock的列表。当需要更新列表或执行没有转发方法的复杂操作时,这是必要的。

  • Function::arg_iterator - 用于参数列表迭代器的类型定义

    Function::const_arg_iterator - 用于const_iterator的类型定义.

    arg_begin()arg_end()arg_size()arg_empty()

    这些是转发方法,可以方便地访问函数对象的参数列表的内容。

  • Function::ArgumentListType &getArgumentList()

    返回参数列表。当需要更新列表或执行没有转发方法的复杂操作时,这是必要的。

  • BasicBlock &getEntryBlock()

    返回该函数的入口BasicBlock。因为函数的入口块始终是第一个块,所以返回函数的第一个块。

  • Type *getReturnType()

    FunctionType *getFunctionType()

    遍历函数的类型并返回函数的返回类型或实际函数的函数类型

  • SymbolTable *getSymbolTable()

    返回一个指向该函数的SymbolTable的指针。

第 147 段(可获 2 积分)

GlobalVariable 类

#include "llvm/IR/GlobalVariable.h"

头文件来源: GlobalVariable.h

doxygen信息: GlobalVariable Class

父类: GlobalValueConstantUserValue

全局变量用GlobalVariable类表示(这真是意外的惊喜)。 像函数一样,GlobalVariable也是GlobalValue的子类,因此它们总是被它们的地址引用(全局值必须存在于内存中,所以它们的“name”是指它们的常量地址)。 有关更多信息,请参阅 GlobalValue。 全局变量可能有一个初始值(它必须是一个常量),如果它们有一个初始化器,它们可能会被自动标记为“常量”(表示它们的内容在运行时不会更改)。

第 148 段(可获 2 积分)

GlobalVariable类的重要公共成员

  • GlobalVariable(const Type *Ty, bool isConstant, LinkageTypes &Linkage, Constant *Initializer = 0, const std::string &Name = "", Module* Parent = 0)

    创建一个新的指定类型的全局变量。如果isConstant为true,则全局变量将在程序中被标记为不可变。 Linkage参数指定变量的链接类型(internal,external,weak,linkonce,appending)。如果链接是InternalLinkage,WeakAnyLinkage,WeakODRLinkage,LinkOnceAnyLinkage或LinkOnceODRLinkage,则所得到的全局变量将具有内部链接。 AppendLinkage将变量的所有实例(以不同的翻译单元)连接在一起,但仅适用于数组。有关链接类型的更多详细信息,请参阅LLVM语言参考。可选地,也可以为全局变量指定初始化器,名称和放置变量的模块。

  • bool isConstant() const

    如果这是一个已知在运行时未被修改的全局变量,则返回true。

  • bool hasInitializer()

    如果此GlobalVariable具有初始化函数,则返回true。

  • Constant *getInitializer()

    返回一个GlobalVariable的初始值。如果没有初始化程序,调用此方法是不合法的。

第 149 段(可获 2 积分)

BasicBlock

#include "llvm/IR/BasicBlock.h"

头文件来源: BasicBlock.h

doxygen信息: BasicBlock Class

父类: Value

该类表示代码的单入口单出口部分,在编译器界通常称为基本块。 BasicBlock类维护一个指令列表,它们形成块的主体。 匹配语言定义,这个指令列表的最后一个元素总是一个结束符指令(TerminatorInst类的子类)。

除了跟踪构成块的指令列表之外,BasicBlock类还跟踪它嵌入到的函数

请注意,BasicBlocks本身是,因为它们由分支指令引用,并且可以转到交换表中。 BasicBlocks有标签类型。

第 150 段(可获 2 积分)

BasicBlock类的重要公共成员

  • BasicBlock(const std::string &Name = "", Function *Parent = 0)

    BasicBlock构造函数用于创建插入函数的新的基本块。构造函数可选地为新块指定一个名称,并将一个函数插入。如果指定了Parent参数,则新的BasicBlock将自动插入指定函数的末尾,如果未指定,则必须将BasicBlock手动插入到该函数中。

  • BasicBlock::iterator - 用于指令列表迭代器的类型定义。BasicBlock::const_iterator - 用于const_iterator的类型定义。

    begin()end()front()back()size()empty() 用于访问指令列表的STL样式函数。

    这些方法和类型定义与相同名称的标准库方法一样具有相同语义的转发函数。这些方法以易于操作的方式暴露基本块的底层指令列表。要获得容器操作的全部补充(包括更新列表的操作),您必须使用getInstList()方法。

  • BasicBlock::InstListType &getInstList()

    此方法用于访问实际保存指令的底层容器。当您要执行的操作在BasicBlock类中没有转发功能时,必须使用此方法。因为没有用于“更新”操作的转发功能,如果要更新一个BasicBlock的内容,则需要使用此功能。

  • Function *getParent()

    返回一个指向Block嵌入的函数的指针,如果它不指向任何内容,则返回空指针。

  • TerminatorInst *getTerminator()

    返回指向出现在BasicBlock结尾处的终结符指令的指针。如果没有终结符指令,或者如果块中的最后一条指令不是终结符,则返回一个空指针。

第 151 段(可获 2 积分)

Argument 类

这是 Value 的子类,定义了一个函数输入的形参接口。Function 维护了一个形参列表。而一个参数包含了指向父函数的指针。

第 152 段(可获 2 积分)

文章评论

喵喵
哇,99%了耶
西安访客
PDF多好滴
班纳睿
老牛了