SPA (Static Program Analysis)

静态程序分析(Static Program Analysis, SPA)的目标很明确:在不实际运行程序的前提下,仅通过源代码获取部分我们感兴趣的程序信息。 例如:

  • 这个变量是否被使用过?
  • 这个表达式的计算结果是否一定是常量?

一般而言,我们可以针对这些具体问题,朴素地编写一些特定的分析代码来达成目标。而研究 SPA 的意义主要在于:

  • 提供一套通用的方法和套路,指导我们按照固定的流程完成分析目标。
  • 提供一套完整的术语体系和理论论证,证明上述方法的有效性,或者明确其适用范围。
程序分析在逻辑上并不十分复杂。对于静态程序分析而言,重点主要是分析速度要快。如果静态分析的耗时甚至超过实际运行一遍程序,那么几乎可以认为这种分析是不可用的。

基础术语

Sound & Complete

假定所有在运行期可能出现的结论共同构成一个 Truth 集合,其中的结论都被称为 Correct。

在静态分析中,有两个重要概念:Sound 和 Complete,可以简单理解为“保全”和“保真”。

  • Sound(保全,Over-approximate):分析结果集合包含所有 Correct 的结论。
  • Complete(保真,Under-approximate):分析结果集合中的所有结论都是 Correct 的。
  • Sound & Complete:分析结果集合既包含所有 Correct 的结论,同时也不包含任何不正确的结论。

莱斯定理(Rice's Theorem):不存在一个通用的判定器,能够完美地判定程序的 Non-trivial 属性。换言之,不存在一个通用的、同时满足 Sound 和 Complete 的程序语义属性判定器。

Trivial 属性是指所有递归可枚举语言(Recursively Enumerable Languages)都满足,或者都不满足的属性。通俗地近似理解,任何必须在运行期才能获得具体结果的程序属性,都可以看作 Non-trivial 属性。

这一定理告诉我们,不应该期望实现一个通用且完美的静态程序分析器。但对于特定任务,如果有足够的已知信息或约束条件,仍然可能实现一个同时满足 Sound 和 Complete 的分析器。

在实践中,我们一般需要做出一定妥协,而妥协的目标只有一个:保证分析结果对我们而言是有意义的。具体而言,我们将这种有意义的分析结果称为 Safe。

一个直观的例子是判断“指针是否为 nullptr”。

显然,对于一般程序中的这一问题,我们无法同时保证 Sound 和 Complete,因为总有一部分指针的取值只有在运行期才能确定,例如通过 main 函数入口由用户传入的值。

莱斯定理可以借助图灵机停机问题来反证:如果希望获得程序的所有属性,首先需要判断某条语句 stmt 是否会被执行。如果该语句不会被执行,那么它自然不会贡献任何信息。而判断 stmt 是否会被执行,本质上就涉及判断 stmt 之前的程序是否会停机。

Dataflow Analysis

Dataflow Analysis 是一类程序分析方法的统称。

从形式上来说,只要分析结果被记录在某种 State 中,并且这个 State 能够沿着 IR 结构进行逻辑上的更新,就可以将其称为 Dataflow Analysis。

宽泛地说,常用的程序分析几乎都可以视为某种 Dataflow Analysis。

其中,Pointer Analysis 通常是较为复杂的一类分析。粗略地说,指针分析的目标是:对于给定的 Program Point,分析该位置处指针 ptr 可能指向的 Object。

Dataflow Analysis 中涉及的主要概念如下。

State

State 用于存储分析过程中获得的信息。

  • State 的值域通常记作 V,称为 Domain。在正式的研究中,会进一步使用 Lattice 来描述值域。
  • State 通常涉及 Top 和 Bottom 两种特殊状态(Lattice 中的术语):
    • Top(\top):通常表示可能处于任意状态,即全集。
    • Bottom(\bot):通常表示没有任何信息,即空集。

PP(Program Point)

Program Point 对应 IR 中的某个元素,用于关联和存储 State。

根据 PP 绑定的对象不同,可以将分析划分为两类:

  • Dense Analysis
    • PP 可以与 Instruction、Operation 或 Basic Block(BB)绑定,用于描述某个程序位置上的信息。
    • 这类分析通常需要沿着指令流逐条分析,才能获得最终结果。
  • Sparse Analysis
    • PP 可以与 Value 绑定,用于描述某个值的相关信息。
    • 这类分析通常只需要沿着 Def-Use Chain 进行传播,可以跳过中间大量无关的指令。

Sensitive

Sensitive 用于描述分析对不同程序执行特征的敏感程度,主要包括以下几类:

  • Flow-sensitive
    • 关注 PP 之前的指令应当被视为有序序列,还是无序集合。
    • Flow-insensitive 意味着不关心指令的执行顺序,先处理哪条指令都可以。
  • Path-sensitive
    • 关注当多条执行路径到达同一个 PP 时,如何处理不同路径上的信息。
    • Path-sensitive 需要为不同路径维护不同的分析结果。
    • Path-insensitive 则需要在控制流汇聚处合并来自不同路径的信息。
  • Context-sensitive
    • 关注当执行路径跨越函数边界时,如何处理来自不同函数调用上下文的信息。
    • 这一概念与 Path-sensitive 类似,只不过关注的是跨函数的调用上下文。

Dataflow Analysis 的执行流程

Dataflow Analysis 的一个重要特点是:分析过程高度模式化,并且有系统的Lattice理论论证来说明其性质。

一般而言,Dataflow Analysis 的执行流程类似于使用一个简单的解释器来执行代码。

我们为每条指令定义一个简单的 State 处理函数,称为 Transfer Function。它根据流入当前指令的信息,计算出执行该指令后的新信息。

典型的分析流程如下:

  1. 初始化 State
    • 为所有需要分析的位置关联一个 PP,并初始化对应的 State。
  2. 遍历 IR,更新 State
    • 从 Entry Point 出发,沿着指令流方向遍历整个 IR,并更新相关 State。
    • 如果沿着指令流遍历,对应 Dense Analysis;如果沿着 Def-Use Chain 传播,则对应 Sparse Analysis。
    • 分析也可以沿着指令流(或 Def-Use Chain)的反方向进行,这种方式称为 Backward Analysis。
  3. 重复分析,直到 State 不再变化
    • 只要某个 PP 的 State 发生变化,就需要重新执行分析,确保可能受其影响的PP被更新。
    • 在满足一定条件时(这个条件比较宽松, 一般都可以满足),可以从理论上证明:无论从哪个点开始遍历,或者在什么时机重新开始遍历,都不会影响算法最终的收敛结果。
    • 实际开发中,通常使用 Worklist 策略维护待遍历节点。其基本原则是:只要 foo.state 发生变化,所有可能受 foo 影响的 PP 都需要重新加入 Worklist,等待再次分析。

如果采用以 BB 为单位的方式组织 State,那么 State 构成的图在整体结构上与 CFG 基本一致。

下面的虚线框描述了如何根据其他 BB 的 State 计算当前 BB 的 State。由于这里需要处理来自不同执行路径的信息,因此还需要通过 Merge 操作合并不同路径上的分析结果。

Read more

内存心智模型

若忽略 Cache 的存在: * 从 Guest 的视角来看,Guest 负责发出 Request(Load/Store 指令),Memory Controller 则在数据 Ready 时通知 Guest。 - Request 通常不会立即得到响应。Memory Controller 会先对请求进行合并,再统一处理。 - Memory Controller 会向物理内存发起 ACTIVATE / READ / WRITE 等操作。每次硬件数据传输都对应某个 Bank 中的 Row。Memory Controller 需要先执行 ACTIVATE,才能进行 READ / WRITE,而 ACTIVATE 通常非常耗时。 * 硬件的单次 READ / WRITE

By Edimetia3D

The Building Blocks of Transformers

Transformer(Attention Is All You Need)最初作为翻译模型出现,并极大地影响了后续深度学习(DL)领域的研究热点。 相比传统的 RNN,Transformer 具有以下特点: 1. 消除了时间维度上的顺序计算依赖:在训练阶段及推理的 Prefill 阶段,不需要沿时间维度依次处理输入中的每个时间点。一方面避免了计算的顺序依赖,另一方面减少了动态控制流,从而极大地提升了计算效率。 1. 计算结构简单:Transformer 使用的基本计算单元非常简单,几乎只有 GEMM、+ - * / 和 Softmax,单个Block内没有复杂的计算流程,整体架构是对基础Block的不断重复,因此,原论文的作者将其称为一个“简单”的模型。 本文不关注训练、推理等 LLM 相关业务,而是重点介绍 Transformer 中典型的基本计算单元,包括它们的逻辑功能与计算方法。 为了简化内容,本文仅关注现代 LLM(2023

By Edimetia3D

Coroutine

从一般概念上说, 协程是特殊的函数调用: 被调用的函数可以在可控的位置被中断,然后在下一次调用时,继续从上次中断的位置继续执行。 本文主要通过Python的协程来介绍协程, 这是我唯一熟悉的一种协程实现. Classic Coroutine 下面的python代码很好的说明了协程的核心功能 def co_routine(): recv0 = yield 996 # hangs here after first coro.send assert recv0 == "Second" yield 711 # hangs here after second coro.send return def main(): coro = co_routine() # Create a new coroutine object value = coro.send(None)

By Edimetia3D