针对DSP指令生成与二进制翻译的汇编器实现

1、中图分类号 :TP314文献标识码 :A 文章编号 :10092552(2011 03004704针 对 DSP 指令 生 成 与 二 进 制翻译 的 汇 编 器 实现 肖 贺 , 刘 佩林(上 海 交 通 大 学 电 子信息 与 电 气 工程学 院 , 上 海 200240摘 要 :DSP 指 令 生 成 与 优 化 和 二 进 制 翻译 是现 代 编译 工具 值 得 关 注 的 热 点问题 。 针对 DSP 指 令 的 特点 提出一种通用的 DSP 指 令 生 成 (支 持 VLIW 指 令 与 二 进 制 翻译 技术 , 并应用于 GNU 汇编 器 (GAS 。 包含 该 技术 的 汇编

2、 器 PCA (Post Compilation Assembler 先 将 输入 的 汇编 指 令转 化 成 类似 LISP 的中 间语 言 。 PCA 通过 对 此 中 间语 言 分 析以及 窥孔 优 化 , 最 终 生 成高 质 量的 目标 平台 DSP 代 码 。关键词 :DSP 指令 生成 ; VLIW 指令 ; 二 进 制翻译 ; 编 译 后 优 化 ; 窥孔 优 化Implementation of assembler for DSP code generationand binary translationXIAO He , LIU Pei-lin(School of Elec

3、tronic Information and Electrical Engineering , Shanghai Jiaotong University , Shanghai 200240, China Abstract :DSP code generation and optimization , along with binary translation , has become a well-concerning focus of the modern tool chainThis paper , on account of the specialties of DSP instruct

4、ion , proposed a general method of DSP code generating (include VLIW and binary translation , which applied in GNU assembler (GAS GAS with this technology (called PCA first translates source assembly instructions into LISP-like intermediate representation (IR ; by analyzing the behaviors of the IR s

5、tatements and employing post-compilation techniques such as peephole optimization , PCA will produce DSP codes of high quality suitable for the target platformKey words :DSP code generation ; VLIW ; binary translation ; post-compilation optimization ; peephole optimization0引言在现 代 编 译 工 具 的研究中 , 为 了

6、尽 可 能 地 让 编 译器 编 译 出 适 应于 特定 DSP 架 构的 代 码 , 设 计 者 提 出 一 种 编 译 后 优 化 的 方 法 来 控制 编 译器 进行 机 器 相 关 的 优 化 。 编 译 后 优 化 的 方 法有 很 多 , 窥孔 优 化 便 是 其 中 很 重 要 的 一 种 1。 窥孔 优 化 的基 本 思 想 是 考 察 窥孔 窗 中的 一 组 指令 (一 般 是 3 5个 , 对 这 组 指令 进行 局 部 优 化 , 然 后滑 动 窗 的 位 置 , 对 下 一 组 指令 执 行 优 化 操 作 直 到 所 有 指令 扫 描结 束 。 目 前 成 熟 的 D

7、SP 编 译器 通 常 会 采用 窥孔 优 化 技术 来 生成 与机 器 架 构 相关 的 特 殊 指令 和 优 化 代 码 23。 此 外 , 现 代 工 具 链 有 一 个很 有 前 景 的应用 称 之 为 二 进 制翻译 , 也就 是 说 , 某 一 架 构的 汇 编 二 进 制 程 序通 过 特定 的 工 具 能 够被 翻译 为 能 在 另 一 种 架 构 上 执 行的 可 执 行 代 码 , 同 时 保 证 二 进 制 程 序 不 会 有 太 明 显 的 性 能 降 低 。 据研究 45表 明 , 窥孔 优 化 十 分 适 用于 二 进 制翻译 。为 了满足 上 述两 方 面 的 要

8、 求 , 提 出 一 种 采用编 译 后 优 化 技术 生成 特定 DSP 指令 和 完 成 二 进 制翻 译 的 汇 编 器 PCA , 它 将 窥孔 优 化 技术 从 编 译 阶段 推 迟 到 汇 编 链 接 阶段 。 这 样的编 译 结 构有 三 方 面 的 好 处 :首先 , 该 汇 编 器 结 构 为 二 进 制 翻 译 创 造 了 可收稿日 期 :20101027作者简介 :肖 贺 (1986 , 男 , 硕 士研究 生 , 主要 研究 方 向 为 DSP 处理器 体 系 架 构 及 其 编 译器汇 编 器 实现 。 74能 。 其 次 , 该 结 构 提 出 优 化 技术 可 以

9、用于 不同 高 级 编 程 语 言下 的 程 序 优 化 , 也 能 适 用于 高 级 语 言 与 汇 编语 言 混合 编 程 的 情况 。 最 后 , 在 编 译 阶段得 不 到 的 许多 程 序 相关 信息 例 如符 号 信息 , 变 量 存 储 形 式 (内存 或 是 寄 存 器 可 以 在 汇 编 阶段 获 得 , 能 够 更 加 有 效 地 进行 优 化 。1整 体设计提 出 的 汇 编 器 PCA 首先将 汇 编 代 码 (编 译器 生 成 或 者 手 写 汇 编 代 码 翻译 转 化成一 种 通用的中 间 语 言 。 PCA 接 着 采用基于 窥孔 优 化 的 指令翻译 生 成

10、算法 对 中 间 语 言 进行 分析 与 优 化 , 最 终 生成 所需 要 的 目 标 代 码 。 从 流 程 框 架 和 中 间 语 言匹配 两 方 面 对 PCA 展 开 具 体 讨论 。11PCA 流 程框架PCA 是 基 于 GNU 汇 编 器 GAS 而 开 发 的 , 而 GAS 是 以行为 单 位 进行 扫 描 并 生成 最 终 二 进 制 代 码 。 这 种 传 统 的 汇 编 器 结 构 不 适 合 进行 二 进 制翻译 和 构 造 DSP 指令 , PCA 对 此 结 构进行 了 相 应的 调 整 。 PCA 的 工 作 原 理 如 图 1所 示 。图 1PCA 工 作

11、流 程 图源汇 编 代 码 首先 通 过 PCA 的 解 析 单 元 转 换 成 中 间 语 言 IR (Intermediate Representation , 同 时 重 建 程 序 控制 流 信息 , 并 生成 符 号 表 。 被 转 换 过 的中 间 语 言 通 过 窥孔 优 化 算法 与 预 先定 义 的 DSP 架 构 指 令 库 中的 模式 进行 匹配 与 选择 变换 , 同 时 更 新 优 化 后 IR 序 列 的 符 号 表 。 最 后 , PCA 将 最 终 的中 间 语 言 序 列 和 符 号 表 生成 可 执 行 文 件 。12中 间语言 IR 描述 与 匹配PCA

12、采用 类 似 于 GCC 中 RTL 语 言 6的 IR 结 构 作 为 其 中 间 语 言 , 如 图 2所 示 。 可 以 看 出 , IR 结 构 包 含 两 个 部 分 , 操 作 部 分 opcode 和 操 作 数部 分 operands 。图 2IR 结 构图其 中 , opcode 中的 CODE 域 指 定 当前 中 间 语 言 语 句 完 成 的行为 , PCA 定 义 了 一 组 标 准 名 来 指 定 一 些 通用的 操 作 , 例 如 PLUS 表 示 加 法 , MINUS 表 示 减 法 , SHIFT 表 示 移 位 操 作 等等 。 CODE 集 合 亦 可

13、以 根 据 特定 的 DSP 指令 架 构 而 进行 扩 展 。 IR_TYPE域 标 识 指令 模 板 的 分 类 , 该 分 类 使 用于 VLIW 模 板 中 。 operands 部 分指 定特定 操 作下 操 作 数的 特 征 , 其 中 第 一 个 操 作 数为 目 标 操 作 数 , 其 他 为 源 操 作 数 。 它包 含 TYPE , operandx 和 WIDTH 三 个 域 。 TYPE 域 指 定 操 作 数的 类 型 , 例 如 REG 表 示 普 通 寄 存 器 , SPR 表 示特 殊 寄 存 器 , MEM 内存 , 以 及 IMM 表 示 立 即 数 。 o

14、perandx 域 标 识 操 作 数的 名称 , 例 如 REG :r7表 示 某 条 语 句 的 一 个 操 作 数 是 寄 存 器 型 , 名称 是 r7。 不同 的 IR 语 句 中 相 同 的 操 作 数 名称 表 明 了他 们 对 同 一 个 操 作 数进行 了 操 作 。 WIDTH 域 指 定 了 操 作 数的 位 宽 。2具 体实现给 出 了 PCA 的 工 作 流 程 以 及 介 绍 了 中 间 语 言 。 结 合 DSP 指令 特 点 来 详细 说 明 PCA 生成 DSP 指令 代 码 的 过 程 。21控制 流 重 建重 建 输 入 程 序的 控制 流 对 于 汇 编

15、 器 来 说 是 一 个 比较 大 的 挑 战 。 为 了 有 效 地优 化和 解 析源汇 编 代 码 的 功 能 , PCA 首先 需 要 将 直 接 转 换 过 来 的 IR 语 句 分 割 成 不同 的基 本 块 。 具 体 做 法 是 PCA 找 出 跳 转 语 句 , 将 它们 作 为基 本 块 最 后 一 条 语 句 , 并 将 它们 的 跳 转 目 标 作 为基 本 块 的 第 一 条 语 句 , 以 此 来 分 割 IR 程 序 。 接 着 通 过分析 基 本 块 中 各 语 句 的 OPERAND 域 标 识 得它们 的 依 赖 关 系 后 , PCA 以 这 些 被 分 割

16、 的 基 本 块 为基 本 单 元 解 析 并 生成 DSP 指令 。22指令翻译 生 成算法指令翻译 生成 算法的基 本 原 理 是 IR 中 间 语 句 匹配 , 所 谓 的中 间 语 句 匹配 , 是 指 当 汇 编 指令 经 过 解 释 器 转 换 成 中 间 语 句 后 , 该 语 句 的 OPCODE 域 , TYPE 域 和 WIDTH 域 和 某 个 预 先定 义 的 IR 模 板 相 一 致 。 IR 支 持 嵌 套 结 构以进行 复 杂 的 窥孔 优 化 , 即 一 个 IR 语 句 的 操 作 数 可 以 是 一 条 IR 语 句 结 构 。 由 于 IR 语 句 的 作

17、 用 是 改 变 目 标 操 作 数的值 , 那么 IR 语 句 本 身 可 以 等 价 于 一 个 与目 标 操 作 数 相 同 的 一 个 操 作 数 。一 般 来 说 , DSP 指令 可 以 大 致 分 为 两 类 , 一 类 称 为 增 强 指令 , 能 够完 成 很 强 大 的 运 算 操 作 , 另 一 类是 VLIW 指令 , 包 含 多 个 发 射 槽 。 PCA 预 先定 义 复 杂 的 IR 模 板 , 通 过 IR 语 句 合 并 算法 可 以 实现 第 一 类 84指令 ; 通 过指 定 指令 封 包 的 格 式 可 以 实现 第 二 类 指 令 。 对 于 第 一

18、类 增 强 指令 , IR 语 言 模 板 可 以 是 一 系 列简 单 模 板 的 嵌 套 。 第 二 类 指令 的 模 板 为 一 系 列 格 式 的 指令 包 。 而 对 于 普 通非 DSP 指令 来 说 , 翻译过 程 比较 简 单 , 本 文 不 多 赘 述 。指令翻译 生成 算法的 流 程 图 如 图 3所 示 。 图 3的 左 半 部 分 实现 IR 语 句 合 并 生成 DSP 增 强 指令 的 过 程 。 首先 , PCA 会 根 据 DSP 增 强 指令 模 板 生成 IR 语 句 合 并 器 。 IR 语 句 合 并但 与 会 根 据 操 作 数 依 赖 关 系 将 基

19、 本 块 中 符 合 模 板 的 多 条 IR 语 句 合 并起 来 。 如 果 IR 语 句 合 并 单 元 确 实 对 当前 IR 语 句执 行 了 合 并 操 作 , 则 会 对 所 有 参 与 合 并 的 IR 语 句 进行 标 识 , 以 便 PCA 将 参 与 合 并 的 IR 语 句 从 缓 冲 区 内 删 除 , 否 则 , 该 IR 语 句 将 直 接 进 入 下 一 级 模 块 。图 3指令翻译 生成 算法 流 程 图DSP 指令 封装 过 程 如 图 3右 半 部 分 所 示 。 PCA 根 据 预 先定 义 的 DSP 封 包 规 则 , 生成一 个 IR 语 句 封装

20、 器 。 IR 语 句 封装 器接收 IR 语 句 合 并 单 元的 输 出 IR 语 句 , 并 根 据 封 包 规 则 对 这 些 IR 语 句 进行 封 装 。 例 如 , 如 果 当前 的 DSP 架 构 支 持 的 是 支 持 同 时 发 射 3条 指令 , 那么 PCA 会 根 据 IR 语 句 的 依 赖 关 系 将 不 相关 的 IR 语 句 进行 封装 , 若 不存 在 3条这 样 的 指令 , 那么 则 通 过 插 入 NOP 指令 来 进行 封装 。 若 DSP 架 构 不 符 合 VLIW 结 构 , 则 可 通 过指 定 封装规 则 为 一 次 发 射 一 条 指令

21、来 实现 此 DSP 单 发 射 架 构 。 23DSP 指令变 换 匹配不 符 合 DSP 模 板 的 IR 语 句 存 在 两 种 情况 , 一 种 是 通 过 相 应的 变换后 可 以 符 合 某种 DSP 模 板 , 另 一 种 是 无 法 符 合 任 何 DSP 模 板 的 。 由 于 PCA 最 关 注 的 问 题 是 如 何 尽 可 能 多 地 生成 符 合 DSP 模 板 的 指令 , 因此 PCA 尽 量 转 换第 一 类 IR 语 句 为 匹配 IR 语 句 。 对 于 PCA 来 说 , 匹 配 变 换 的 方 法 有 以 下 两 种 。(1 操 作 数 位 置交 换 :

22、DSP 指令 的 源 操 作 数通 常不 具 有 可 交 换 性 , 例 如 , 某 DSP 加 法 指令 要 求 第 一 源 操 作 数为 内存 操 作 数 , 第 二源 操 作 数为 寄 存 器 操 作 , 那么第 一 源 操 作 数为 寄 存 器 , 第 二源 操 作 数为 内存 的 IR 加 法语 句 无 法 直 接 匹配 模 板 生成 相 应的 指令 ; 通 过 交 换 两 源 操 作 数的 位 置 , 可 以 使 该 IR 语 句 匹配 DSP 加 法 模 板 。(2 操 作 数 类 型 转 换 :DSP 指令对 操 作 数 类 型 一 般 有 严 格 的限 定 , 对 于 无 法

23、通 过 置 换 操 作 数 位 置 的 第 一 类 IR 语 句 , PCA 通 过 类 型 变换来匹配 某 些 IR 模 板 ; 例 如 , 某 DSP 移 位 法 指令 要 求所 有的 操 作 数为 寄 存 器 操 作 数 , 对 于 其 中 第 一 源 操 作 数为 立 即 数的 IR 移 位 语 句 , 可 以通 过 在 该 语 句 前 插 入 一 个 将 立 即 数 搬 移 到 寄 存 器 操 作 的语 句 , 然 后再将 此 移 位 语 句 的 所 有 操 作 数 修 改 为 相 应的 寄 存 器 , 以 符 合 DSP 移 位 模 板 生成 特定 的移 位 指令 ,可 以 看 出

24、 , 第 一 种 匹配 方 法 不 会 引 入 额 外 的 代 价 (不 会 增 加 新 的 指令 , 而 第 二 类 匹配 方 法 则 会 带 来 额 外 的 开 销 (插 入新 的 指令 。 在实 际 的 DSP 指 令 生成 过 程 中 , 通 过 权 衡 计 算 匹配 操 作给 PCA 代 码 生成 时 候 带 来 好 处 或 者 额 外 的 开 销 , 可 以 选择 在 特 定 的基 本 块 中 是 否 使 用 该 匹配 操 作 。3结果分析PCA 的 目 标 机 为 AISA , 它 一 款 包 含 DSP 音 频 加 速指令 的 处理器 7。 该 处理器 包 含 两条 流 水线

25、, 一 条 流 水线 执 行 RISC 基 本 指令 集 BASIC INST (包 含 运 算 , 跳 转 , 比较 等 指令 , 另 一 条 流 水线 执 行音 频 扩 展 指令 AUDIO EXTENTION 。 测 试 程 序为 HE-LIX 非 商 用 免 费 的 AAC 解 码器 , 该 源 代 码 中 包 含 了 大 量 的 乘 法 操 作 , 内存 变 量 加 法 操 作 等等 , 且 这 些 运 算 操 作 在 AISA 中有 相 应的 DSP 音 频 加 速指令 与 之 对 应 。31二 进 制翻译 性能 比 较为 了 测 试 PCA 的 二 进 制翻译 能 力 , 使 用

26、 PCA 将 ARM 工 具 链 编 译 生成 的 AAC 解 码二 进 制 程 序 翻 译 为 AISA 可 执 行的 BASIC INST 二 进 制 程 序 。 表 1 94为 测 试 码 流 。表 1HELIX AAC LC (无 SBR 测试 码 流名称 采样 率 比 特 率 声 道 数 长 度 AM_9644kHz 96kbps Mono 20帧 AS_12844kHz 128kbps Stereo 20帧将 ARM 二 进 制 程 序 仅 翻译 为 BASIC INST 程 序 的 原 因 有 两 个 , 一 是 避免 了 AISA 中 DSP 音 频 加 速 指令带 来 的 性

27、 能 提 升 会 对 PCA 翻译 能 力 不 足 产 生 掩 蔽 现 象 ; 二 是 由 于 ARM 基 本 指 令 集 和 BASIC INST 指令 集的 硬 件 运 算 能 力 类 似 , PCA 翻译 前 后 的 二 进 制 程 序的 性 能 比较 的 结 果 能 够较 为 准 确 和 清 晰 地 反 映 出 PCA 的 翻译 能 力 , 实 验 结 果 如表 2所 示 。 表 2PCA 翻译 性能 结 果 比 较 (AS_128测 试 架O0O2静 态指令 动 态指令 静 态指令 动 态指令从表 2的 结 果 可 以 看 出 , 在 arm linux gcc 在 O0选项 编 译

28、 下 的 AAC 在 armulator 上 运 行的动 态指令 数 与 BASIC INST 相 差不 大 , 这 在 很 大 程 度上 归功 于 ARM 的 CPU 架 构 与 AISA 的 BASIC INST 指 令 集 架 构 和 寄 存 器 组织 类 似 , 使得 在 二 进 制翻译过 程 不 会 引 入 太 多 的 额 外 开 销 。 在 arm linux gcc 02选项 下 BASIC INST 的 性 能 相 比 有 所 下 降 , 这 是 因 为 arm linux gcc 在 02选项 会 执 行 与 arm 架 构 相关 的 优 化 策 略 (例 如 指令 乱 序

29、, 而这 些 优 化 策 略 可 能 对 BASIC INST 指令 集 没 有像 ARM 指令 集 一 样 带 来 显著 的 性 能 提 。 从 结 果 来看 , 在 没 有 任 何 加 速指令 情况下 , PCA 将 一 种 基 本 指令 集 和程 序 翻译 为 另 一 种 基 本 指令 集 和程 序的 性 能 良 好 。32DSP 指令 生 成 的 性能 比 较AAC 解 码器 中 包 含 大 量 的 乘 法 和 移 位 , 以 及 内 存 变 量 的 加 减 法 操 作 , 这 些 都 可 以通 过 AISA 的音 频 扩 展 指令 AUDIO EXTENSION 来 加 速 运 算

30、。 通 过 比较 PCA 对 AAC 解 码器 编 译 最 终 仅 生成 BASIC INST 指令 和 同 时 生成 包 含 BASIC INST 与 AUDIO EXTENSION 指令 这两 种 情况下 的 解 码性 能 (动 态指 令 条 数 , 得 出 PCA 生成 DSP 指令 的 能 力 。 这 里特 别 需 要 指 出 , 后 种 情况 (含 AUDIO EXTENTION 指 令 的 二 进 制 程 序 是 PCA 以 第 一 种 情况下 (仅 BAS-IC INST 指令 的 二 进 制 程 序通 过 反 汇 编为 汇 编 文 件 作 为 输 入 , 通 过 DSP 指令翻

31、译 生成 算法 最 终 生成 的 , 结 果 如表 3所 示 。表 3PCA DSP 指令 生 成结 果 比 较测 试 O0O2通 过 表 3的 比较 可 以 很 容 易 看 出 包 含 音 频 加 速 指令 AUDIO EXTENSION 的 AAC 解 码器 解 码 能 力 有 接 近 两 倍 的 性 能 提 升 , 这 一方 面 是 因 为 AISA 的 AUDIO EXTENSION DSP 指令 功 能 强 大 , 非 常 适 合 音 频 应用 ; 另 一方 面 也 说 明 PCA 在 DSP 指令 生成方 面 的 功 能 比较 强 劲 。4结束语根 据设 计实现 了 一 种支 持 VLIW 指令 DSP 汇 编 链 接器 PCA 。 由 于 PCA 在 汇 编 器 这 一 环 节 进行 窥 孔 优 化 , 使得它 能 同 时 实现 二 进 制翻译 工 作 。 PCA 首先将 输 入 的 指令 集 架 构 汇 编语 言 转 换 为中 间 语 言 IR , 并 通 过 基于 窥孔