fiking

背景

为了学习了解 LLVM 的代码，从其官方仓库中下载代码，然后进行配置，生成可执行文件，便于学习代码过程中调试使用。

摘要

本篇论文给出了一大类程序间数据流-分析的问题如何在多项式时间里通过将其转换为一种特殊的图可达问题进行解决的方法。唯一的限制是数据流事件集合必须是有限集的，且数据流函数必须分布在合并操作上（并集或者交集）。这类问题包括–但不限于–经典的分离问题（也被称为“产生/去掉” 或者“位-向量”问题）–如，到达顶点，有效表达式，或者存活变量。此外，我们的技术可以处理的问题种类还包含许多非问题，包括真实存活变量，拷贝传播，和可能未初始化变量。

结果有一个初步的 C 程序（查找可能的未初始化变量）实验研究给出。

定义了两种关系，用于捕获LALR（1）向前看集计算问题的基本结构；以及给出了计算这个集合的高效算法，其是与关系大小相关的线性时间。特别的，对于一个 PASCAL 语法，这个算法的执行性能比通过通用编译器-编译器 YACC 执行这个集合单元小 15%。

当一个语法不是 LALR（1），显式给出的，关系，提供给面向用户的错误消息，其特别给出了向前看问题是怎样出现的。此外，由这些关系导致的有向图中的某些循环表明对于任意 k，这个语法不是 $LR(k)$。

最后，一个经常被发现和使用，但不正确的向前看集合算法同样基于这里第一次定义的另外两个关系。这个算法的形式化定义应该有助于防止重复发现它。

摘要

本文介绍了 PQCC（Production-Quality Compiler Compiler）项目中的一些代码生成问题[8]。采用的方法在几个方面上是独特的。代码序列选择，寄存器分配等需要的机器相关信息，已经以表格的形式，与机器无关的算法分离。这不仅极大地简化了新机器或者语言的代码生成器开发，也为从形式化机器描述如 ISP [1] 自动生成这些表铺平了道路。使用了一个类似解析树的中间程序表示，促进了表达式相关的上下文和数据依赖信息的使用。代码生成过程分成了几个阶段。这使得更简单以及能更好的理解代码生成过程，并且允许对生成代码的质量进行重大改进。讨论了初步确定寻址方式，寄存器和其它位置的分配，以及代码选择场景分析等的算法。这篇文章描述的算法已经在 PQCC 编译器中实现和使用。

如果我们可以写出能保证正确运行，且从不需要调试的程序，将是非常美好的。直到太平的那天，正常的编程周期将涉及编写程序，编译它，执行它，然后调试它的（有点）令人害怕的祸害。一直重复直到程序如预期的工作。

通过插入代码打印选定的感兴趣的变量的值是可以调试程序的。确实，在一些场景下，如调试内核驱动，这个可能是首选的方法。这存在一个低级别的调试器允许单步通过执行程序，一条一条指令的，二进制的显示寄存器和内存内容。

但是更简单的是使用一个源码级的调试器，它允许你单步程序的源码，设置断点，打印变量值，以及也许还有一些其它的功能，如在一个调试器里允许你调用你程序中的函数。问题是如何协调两个完全不同的程序，编译器和调试器，从而可以让程序变成可调试的。

简介

之前大部分的冗余消除算法都可以分为两类。词法算法处理整个程序，但是它们只能识别词法完全相同表达式的计算的冗余，这里说的表达式词法完全相同指的是，将完全相同的运算符应用于完全相同的操作数。另一方面，值标号算法，可以识别词法不同但肯定会计算相同的值的表达式间的冗余。这是通过给表达式赋一个叫值编号的特殊符号的名称来完成的。如果两个表达式的操作数的值编号完全相同，且应用于表达式的操作符完全相同，则表达式接受了相同的值编号然后一定会有相同的值。值编号的相同性允许比词法相同更广泛的优化，但是值标号过去总是限制在基本块中（没有分支的计算序列），或者扩展基本块中（没有连接的计算序列）。

摘要 我们提出一个简单的 SSA 构造算法，它允许直接从抽象语法树或者字节码翻译到一个基于 SSA 的中间表示形式。这个算法不需要事先的分析，且保证在中间表示构造期间是 SSA 的形式。这样允许在构造期间应用基于 SSA 的优化。在完成后，中间表示是最小且纯的 SSA 形式。尽管它很简单，我们算法的运行时间与 Cytron 等人的算法相当。

简介

在优化编译器中，数据结构的选择直接影响了实际程序优化的能力和效率。一个糟糕的数据结构选择会禁掉一些优化或者使得编译变慢，则高级优化特性会变得不受欢迎的。最近，静态单一赋值形式 [AWZ88，RWZ88] 和控制依赖图 [FOW87] 被提出用于表示程序的数据流和控制流属性。这些之前不相关的技术每个都为一类有用的程序优化提供了效率和功能。虽然这些结构都很吸引人，但它们的构建难度和它们的潜在大小阻挡了它们的使用[AJ88]。我们提出一种新的算法可以从任意的控制流图中高效计算出这些数据结构。我们给出了分析和实验证明，复杂度与远程程序大小成线性关系。因此，本文强有力的证明了这些数据结构可以实际应用到优化中。

在程序已经转为静态单一赋值形式后，有两个有用的属性：

1. 一个变量的每个程序员指定变量都会到达该变量的唯一赋值。

2. 第二节描述的该程序包含的 phi 函数，是用于区分沿着不同传入控制流边传入的变量值。

   阅读全文 »

背景

通过翻译编译器相关的论文，学习了解编译器的理论和技术实现，为后续学习开源代码以及设计实现编译器打下理论基础。

背景

为了增加虚拟机方面的理论知识，开始了虚拟机相关的论文翻译和学习。先制定个伟大的目标，前期每周一篇翻译，后续在根据学习情况进行论文的总结精炼。