毕 业 设 计 ( 论 文 ) 中 文 题 目 : 图 形 化 程 序 切 片 工 具 的 设 计 英 文 题 目 : The Design of Program Slicing Visualization 学 专 院 : 计 算 机 与 信 息 技 术 业 : 计 算 机 科 学 与 技 术 学 生 姓 名 : 王 雪 学 号 : 05281260 指 导 教 师 : 于 双 元 冯 晓 兵 2009 年 6 月 日
中 文 摘 要 程 序 切 片 是 一 种 抽 象 出 与 给 定 计 算 变 量 有 关 的 语 句 的 分 析 技 术 而 非 形 式 的 讲, 程 序 切 片 是 指 从 程 序 行 为 的 一 个 子 集 开 始, 将 其 缩 小 到 最 小 的 形 式, 使 这 种 形 式 仍 能 表 达 原 程 序 中 所 给 定 子 集 的 行 为 这 种 被 缩 小 的 程 序, 就 叫 切 片 [8] 程 序 切 片 在 程 序 调 试 软 件 维 护 和 程 序 理 解 方 面 起 着 重 要 作 用 现 在 一 种 广 泛 使 用 的 程 序 切 片 算 法 是 由 Horwitz 等 在 文 献 [5] 中 提 到 的 这 种 方 法 基 于 依 赖 图, 使 用 图 可 达 性 算 法 来 自 动 地 计 算 程 序 切 片, 能 够 获 得 更 好 的 切 片 精 度 通 过 图 形 化 的 方 式 给 出 切 片 的 过 程 和 切 片 的 结 果 能 够 提 高 程 序 切 片 工 具 的 实 用 性 但 是, 由 于 依 赖 图 的 规 模 非 常 的 巨 大, 切 片 的 结 果 很 难 在 依 赖 图 上 直 观 的 反 映, 同 时 也 给 切 片 工 具 的 调 试 带 来 了 相 当 的 困 难 本 文 正 是 针 对 这 一 问 题 进 行 讨 论 本 文 首 先 介 绍 了 程 序 切 片 的 相 关 概 念, 阐 述 基 于 依 赖 图 的 切 片 算 法 通 过 实 验 数 据 说 明 规 模 巨 大 的 依 赖 图, 给 图 形 化 程 序 切 片 工 具 带 来 的 挑 战, 同 时 用 户 对 程 序 源 码 分 析 的 需 求, 使 得 本 工 具 需 要 实 现 对 源 码 的 显 示 功 能, 然 后 介 绍 切 片 工 具 的 图 形 化 设 计 过 程, 使 用 层 次 化 结 构 的 设 计 方 式, 给 出 两 种 模 式 的 切 片 图 形 化 结 果 为 了 满 足 普 通 用 户 需 求, 在 控 制 流 图 上 给 出 切 片 的 结 果 ; 对 于 切 片 调 试 开 发 人 员, 对 切 片 过 程 产 生 的 大 规 模 依 赖 图 及 大 量 信 息 表 示 的 图 形 化 给 出 相 应 的 解 决 办 法 本 文 所 论 述 的 程 序 切 片 图 形 化 过 程 已 利 用 画 图 工 具 UdrawGraph 在 Open64 编 译 平 台 上 实 现 该 工 具 对 中 国 科 学 院 计 算 技 术 研 究 所 计 算 机 系 统 结 构 重 点 实 验 室 基 于 Open64 编 译 平 台 上 实 现 的 程 序 分 析 工 具 进 行 图 形 化, 已 达 到 令 人 比 较 满 意 的 效 果 在 本 文 的 最 后, 给 出 该 工 具 应 用 的 示 例 图, 展 示 图 形 化 的 效 果 删 除 的 内 容 : 和 控 制 流 图 删 除 的 内 容 : 或 控 制 流 图 删 除 的 内 容 : 不 得 删 除 的 内 容 : 控 制 流 图 关 键 词 : 程 序 切 片 ; 依 赖 图 ;UdrawGraph; 层 次 化 设 计 ; 交 互 I
Abstract Program slicing is a method to abstract related statements for given variables of programs. Informally, program slicing is started from a subset of a program s behavior, and reducing that program to a minimal form which still produces that behavior. The reduced program is called a slice [8]. Program slicing is useful in program debugging, software maintenance, and program understanding. At present, the slicing algorithm, proposed by Horwitz, etc[5], is widely used. It mainly uses dependence graphs to present programs and computes program slices automatically by graph reachability algorithms. And its precision is higher than the previous algorithms. It makes program slicing tools more practical if the visualization tools are used to obtain the process and result of the program slices. However, the dependence graphs and control flow graphs are very huge, so it is difficult to show the result of the program slices directly by the dependence graphs or control flow graphs. In addition, it also brings in great difficulties to debug program slicing. This paper tries to address the above problems. The paper firstly describes the concepts of program slicing and slicing algorithms based on the dependence graphs. Then, experiment results are used to show the huge sizes of the dependence graphs, which is a great challenge for the visualization of program slicing. And the display of source codes has to be implemented because the requirement of users. Secondly, the design of program slicing visualization is described. A hierarchical structure is used to solve the large graphs and a large number of information during program slicing. The process of the program slicing visualization is implemented by UdrawGraph on Open64 compiler platform. It visualizes the program slicing tool which is implemented on Open64 compiler platform by Key Laboratory of Computer System and Architecture in ICT-CAS. And the visualization tool achieves satisfied effects. At the end of the paper, an example is given to show the effects of the visualization tool. Key words: program slicing, dependence graph, UdrawGraph, Hierarchical structure, interaction II
目 录 中 文 摘 要... I Abstract... II 目 录... III 第 一 章 绪 论... 1 1.1 程 序 切 片 工 具 图 形 化 介 绍... 1 1.2 本 文 工 作... 1 1.3 论 文 组 织 结 构... 2 第 二 章 程 序 切 片... 3 2.1 程 序 切 片 概 念... 3 2.2 程 序 切 片 准 则 (slicing criterion)... 3 2.3 程 序 切 片 技 术 分 类... 4 2.3.1 静 态 切 片 技 术 (static slicing)... 4 2.3.2 动 态 切 片 技 术 (dynamic slicing)... 5 2.3.3 条 件 切 片 技 术 (conditioned slicing)... 5 2.4 程 序 切 片 算 法 及 相 关 概 念... 5 2.4.1 程 序 依 赖 图 (Program Dependence Graph,PDG)... 6 2.4.2 系 统 依 赖 图 (System Dependence Graph,SDG)... 7 2.4.3 调 用 图 (call graph)... 8 2.4.4 程 序 切 片 算 法... 9 2.4.5 控 制 流 图 (Control Flow Graph)... 12 第 三 章 程 序 切 片 工 具 图 形 化... 14 3.1 切 片 工 具 图 形 化 意 义... 14 3.2 开 发 平 台... 15 3.3 图 形 化 工 具 简 介... 15 3.4 图 形 化 工 具 选 择... 16 3.4.1 Udraw(Graph) 简 介... 16 3.4.2 Udraw 接 口... 16 第 四 章 切 片 工 具 图 形 化 设 计... 18 4.1 Udraw 语 法 表 示... 18 4.2 切 片 工 具 图 形 化 层 次 化 设 计... 19 4.2.1 层 次 化 设 计 原 因... 19 4.2.2 层 次 化 设 计... 21 4.3 设 计 过 程 及 交 互 实 现... 26 III
4.3.1 调 用 图 的 功 能 实 现... 27 4.3.2 函 数 PDG 的 功 能 实 现... 28 4.3.3 控 制 流 图 的 功 能 实 现... 30 4.3.4 交 互 功 能 实 现... 30 4.3.5 本 文 程 序 整 体 流 程... 31 第 五 章 图 形 化 设 计 实 例... 32 5.1 调 用 图 的 实 例 实 现... 32 5.2 函 数 PDG 的 实 例 实 现... 35 5.2.1 不 包 含 切 片 结 果 的 PDG 显 示... 35 5.2.2 包 含 切 片 结 果 的 PDG 显 示... 39 5.3 控 制 流 图 的 实 例 实 现... 39 5.3.1 不 包 含 切 片 结 果 的 控 制 流 图 显 示... 39 5.3.2 包 含 切 片 结 果 的 控 制 流 图 显 示... 40 第 六 章 成 本 资 源 分 析... 42 第 七 章 结 论... 43 参 考 文 献... 44 外 文 文 献... 44 中 文 文 献... 44 参 考 网 址... 45 附 录... 46 IV
第 1 页 第 一 章 绪 论 1.1 程 序 切 片 工 具 图 形 化 介 绍 程 序 切 片 技 术 是 根 据 控 制 流 分 析 和 数 据 流 分 析 而 引 入 的 一 种 系 统 理 解 方 法, 可 以 针 对 一 个 切 片 标 准, 提 取 出 程 序 中 影 响 关 注 点 变 量 值 的 所 有 语 句, 通 过 计 算 源 程 序 中 每 个 关 注 点 的 切 片 来 达 到 对 整 个 程 序 的 分 析 和 理 解 程 序 切 片 技 术 发 展 到 现 在 已 有 很 重 要 的 现 实 意 义, 目 前 主 要 应 用 于 程 序 调 试 程 序 测 试 软 件 维 护 及 逆 向 工 程 等 方 面 图 形 化 技 术 是 当 前 计 算 机 发 展 的 热 点 之 一 计 算 机 应 用 一 个 重 要 的 研 究 方 向 是 把 信 息 用 可 感 知 的 方 法 表 现 出 来 图 形 化 适 用 于 表 示 拥 有 内 在 固 有 关 系 的 数 据 : 数 据 可 以 被 表 示 为 一 个 图 的 结 点, 和 边 表 示 关 系 这 样 的 结 点 边 关 系 图 在 计 算 机 科 学 和 很 多 其 他 领 域 都 有 广 泛 运 用 它 是 一 种 简 单 有 力 优 质 的 抽 象 任 何 可 以 用 有 关 系 的 点 来 模 拟 的 对 象 都 可 以 利 用 图 形 化 技 术 来 表 示 同 很 多 工 具 软 件 一 样, 切 片 工 具 在 开 发 过 程 中, 很 多 工 作 是 测 试 和 调 试 由 于 切 片 过 程 基 于 依 赖 图, 在 遍 历 依 赖 图 的 过 程 中, 由 于 没 有 图 形 可 视 化 的 支 持, 依 赖 图 或 切 片 结 果 中 的 信 息 会 变 得 不 直 观 晦 涩 增 加 了 其 中 的 数 据 结 构 的 理 解 难 度 在 切 片 过 程 中, 一 般 方 法 是 给 出 所 有 结 点 的 编 号, 以 及 各 边 的 源 结 点 和 目 的 结 点 的 编 号, 而 且 很 多 时 候, 只 有 点 和 边 是 不 够 的, 还 需 要 点 和 边 代 表 的 那 些 数 据 项 的 其 他 信 息 所 以 切 片 工 具 的 图 形 化 已 势 在 必 行 1.2 本 文 工 作 切 片 工 具 在 开 发 过 程 中, 由 于 是 基 于 依 赖 图, 在 遍 历 依 赖 图 的 过 程 中, 由 于 没 有 图 形 化 的 支 持, 依 赖 图 或 切 片 结 果 中 的 信 息 会 变 得 不 直 观 晦 涩 增 加 了 程 序 员 对 数 据 结 构 的 理 解 难 度 而 且 切 片 结 果 的 验 证 往 往 运 用 较 大 的 标 准 测 试 集 来 进 行, 更 加 大 了 其 调 试 难 度 从 面 向 用 户 角 度 来 说, 用 户 关 心 的 只 是 程 序 的 源 代 码 和 相 应 的 切 片 结 果, 所 以, 针 对 用 户 这 个 需 求, 设 计 出 相 应 的 图 形 化 结 果, 也 是 非 常 必 要 的 本 文 完 成 的 就 是 程 序 切 片 工 具 的 图 形 化 工 作 本 工 作 是 中 国 科 学 院 计 算 技 术 研 究 所 计 算 机 系 统 结 构 重 点 实 验 室 正 在 进 行 的 工 作 的 一 部 分, 是 基 1
第 2 页 于 Open64 编 译 平 台 上 的 程 序 分 析 工 具 方 面 的 研 发, 其 中 包 括 程 序 切 片 技 术 工 具 的 开 发 目 的 是 将 切 片 过 程 中 的 数 据 结 构 图 形 结 构 用 图 形 化 工 具 进 行 表 示, 简 化 其 理 解 难 度, 同 时 实 现 面 向 用 户 的 源 码 结 构 显 示 本 文 工 作 是 在 Open64 编 译 平 台 上 进 行, 对 其 中 程 序 切 片 工 具 研 发 部 分 进 行 图 形 化 工 作 在 调 研 多 种 图 形 化 工 具 软 件 后, 决 定 选 用 UdrawGraph 作 为 本 文 基 本 图 形 化 工 具,UdrawGraph 的 图 形 用 户 界 面 有 助 于 对 切 片 过 程 的 理 解 UdrawGraph 不 但 具 有 强 大 的 图 形 化 功 能, 还 已 实 现 了 与 Open64 编 译 器 之 间 的 接 口 1.3 论 文 组 织 结 构 本 文 第 二 章 重 点 介 绍 程 序 切 片 相 关 概 念, 程 序 切 片 准 则 和 Horwitz 等 在 文 献 [5] 中 提 到 的 程 序 切 片 的 算 法 由 于 该 算 法 基 于 依 赖 图, 所 以 同 时 介 绍 相 关 调 用 图 程 序 依 赖 图 系 统 依 赖 图 等 方 面 的 内 容 第 三 章 则 对 本 文 使 用 的 图 形 化 工 具 UdrawGraph 进 行 详 细 介 绍, 从 其 功 能 和 用 途 上 指 出 选 择 UdrawGraph 的 优 势 所 在, 以 及 在 Open64 编 译 平 台 上 已 封 装 接 口 的 可 用 性 第 四 章 介 绍 切 片 工 具 图 形 化 设 计 的 具 体 实 现, 本 文 采 用 层 次 化 设 计, 从 整 体 到 部 分 一 层 一 层 进 行, 并 使 用 交 互 功 能 实 现 层 次 之 间 的 相 互 联 系 第 五 章, 介 绍 SPEC CPU2000 中 181.mcf 实 现 的 一 个 实 例, 并 从 实 例 基 础 上 进 一 步 分 析 图 形 化 工 具 第 六 章 进 行 本 工 具 的 成 本 资 源 分 析 最 后, 总 结 全 文, 指 出 此 图 形 化 工 具 的 优 势 2
第 3 页 第 二 章 程 序 切 片 程 序 切 片 的 起 源 是, 鉴 于 很 多 时 候, 程 序 员 只 需 关 心 程 序 行 为 的 一 部 分 比 如, 调 试 时 只 关 心 程 序 出 错 的 一 部 分 子 集, 程 序 修 改 和 维 护 时 只 对 一 部 分 程 序 进 行 升 级 在 这 些 情 况 下, 程 序 员 从 程 序 行 为 开 始, 寻 找 和 修 改 程 序 代 码 的 相 应 部 分, 与 之 不 相 关 的 部 分 被 忽 略 掉 程 序 员 维 护 一 个 很 大 又 不 熟 悉 的 程 序, 又 不 得 不 利 用 其 中 某 些 部 分, 充 分 理 解 整 个 程 序 而 仅 仅 对 其 中 一 小 部 分 进 行 修 改 和 维 护, 这 会 花 费 很 多 没 用 的 时 间 而 大 部 分 程 序 维 护 不 是 由 程 序 设 计 者 进 行 的 而 是 由 其 他 人 进 行, 而 且 67% 的 努 力 都 要 花 费 到 程 序 维 护 上 [16], 从 行 为 上 分 解 程 序 就 势 在 必 行 程 序 切 片 就 应 运 而 生 了 2.1 程 序 切 片 概 念 [8] 程 序 切 片 的 概 念 最 早 由 Mark Weiser 在 1979 博 士 论 文 中 提 出, 他 的 定 义 是 : 程 序 切 片 是 有 经 验 的 程 序 员 用 来 从 程 序 中 抽 象 出 与 给 定 计 算 变 量 有 关 的 语 句 的 分 析 技 术, 它 是 从 程 序 行 为 的 一 个 子 集 开 始, 将 其 缩 小 到 最 小 的 形 式, 使 这 种 形 式 仍 能 表 达 程 序 的 这 种 行 为 这 种 被 缩 小 的 程 序, 就 叫 切 片, 它 是 独 立 的 程 序, 能 够 在 原 程 序 行 为 子 集 范 围 内 准 确 表 达 出 原 程 序 Weiser 定 义 的 切 片 是 一 个 可 执 行 的 程 序, 是 通 过 从 源 程 序 中 移 去 零 条 或 多 条 语 句 来 构 造 的, 最 终 能 够 严 格 地 表 达 出 原 程 序 的 行 为 [5] 后 来,Horwitz 等 人 给 出 的 切 片 定 义 是 : 一 个 程 序 切 片 是 由 程 序 中 的 一 些 语 句 和 判 定 表 达 式 组 成 的 集 合 这 些 语 句 和 判 定 表 达 式 可 能 会 影 响 在 程 序 的 某 个 位 置 ( 常 用 行 号 标 识 )p 上 所 定 义 的 或 所 使 用 的 变 量 v 的 值 (p,v) 称 为 切 片 准 则 (slicing criterion) 2.2 程 序 切 片 准 则 (slicing criterion) 程 序 切 片 需 要 将 程 序 行 为 指 定 为 某 一 特 定 形 式, 如 果 程 序 中 感 兴 趣 的 行 为 可 以 用 变 量 集 在 语 句 集 中 的 值 来 表 示, 那 么 这 种 规 范 就 定 义 为 程 序 准 则 数 据 流 分 析 能 够 找 到 所 有 能 够 影 响 这 种 指 定 行 为 的 程 序 段, 这 些 程 序 段 就 叫 做 程 序 的 切 片 程 序 切 片 准 则 是 程 序 切 片 技 术 的 重 要 方 面, 切 片 准 则 在 程 序 计 算 切 片 时, 起 到 至 关 重 要 的 作 用 程 序 的 切 片 准 则 为 观 察 程 序 行 为 指 定 了 窗 口, 它 是 由 一 个 语 句 和 一 些 3
第 4 页 变 量 所 指 定 通 过 这 个 窗 口 可 以 在 指 定 语 句 执 行 之 前 观 察 到 特 定 变 量 值 的 变 化 如 果 切 片 标 准 中 的 语 句 在 程 序 运 行 过 程 中 执 行 多 次, 那 么 一 系 列 变 量 值 就 会 被 观 察 到 切 片 准 则 是 用 <p,v> 来 表 示,p 表 示 语 句 编 号, 通 过 它 来 观 察 变 量 变 化,v 代 表 这 组 变 量 程 序 切 片 准 则 还 分 为 多 种, 比 较 广 泛 使 用 的 是 静 态 后 向 切 片 准 则 动 态 后 向 切 片 准 则 条 件 切 片 准 则 [10] 静 态 后 向 切 片 准 则 : 构 造 一 个 程 序 P 的 静 态 后 向 切 片 时, 考 虑 的 切 片 准 则 是 一 个 二 元 组 (v,p), 其 中 v 是 一 组 变 量,p 是 程 序 中 的 一 个 兴 趣 点, 程 序 P 的 一 个 切 片 是 任 何 一 个 在 p 点 对 v 中 的 变 量 具 有 与 P 相 同 影 响 的 程 序 动 态 后 向 切 片 准 则 : 构 造 一 个 程 序 P 的 动 态 后 向 切 片 构 造 时, 考 虑 的 切 片 标 准 是 一 个 三 元 组 (v,p,x), 其 中 v 是 变 量 的 集 合,p 是 程 序 P 中 的 一 个 兴 趣 点,x 是 一 个 输 入 序 列, 当 用 x 作 为 程 序 输 入 时, 一 个 动 态 切 片 保 留 P 的 与 p 点 的 变 量 集 合 v 有 关 的 语 句 集 合 条 件 切 片 准 则 : 构 造 一 个 程 序 P 的 条 件 切 片 时, 考 虑 的 切 片 准 则 是 一 个 四 元 组 (I,p,,v), 这 里 I 是 变 量 名 的 集 合, 这 些 变 量 的 值 是 从 输 入 序 列 中 获 得 的,p 是 程 序 P 中 一 个 兴 趣 点, 是 一 个 谓 词, 它 的 自 由 变 量 是 I 的 一 个 子 集,v 是 一 个 变 量 名 的 集 合, 构 造 一 个 程 序 P 的 条 件 切 片 S, 当 在 一 个 满 足 的 初 始 状 态 执 行 时, 条 件 切 片 S 必 须 保 持 程 序 P( 与 v 有 关 ) 的 语 句 集 合 另 外, 还 有 迭 代 切 片 准 则 传 统 的 前 向 切 片 准 则 分 解 切 片 准 则 多 点 切 片 准 则 广 义 切 片 准 则 无 定 型 切 片 对 象 切 片 类 层 次 切 片 对 象 的 状 态 切 片 和 行 为 切 片 等 切 片 准 则 2.3 程 序 切 片 技 术 分 类 从 程 序 切 片 概 念 提 出 到 现 在, 出 现 了 许 多 不 同 的 定 义 以 及 计 算 切 片 的 算 法, 大 体 上 说, 程 序 切 片 技 术 的 发 展 经 历 了 从 静 态 到 动 态 从 前 向 到 后 向 从 单 一 过 程 到 多 个 过 程 从 非 分 布 程 序 到 分 布 式 程 序 等 几 个 阶 段 [12] 2.3.1 静 态 切 片 技 术 (static slicing) 静 态 切 片 技 术 是 指 在 计 算 机 程 序 切 片 时 使 用 的 是 编 译 时 分 析, 不 需 要 真 正 的 程 序 执 行 该 技 术 对 程 序 的 输 入 不 做 任 何 假 设, 所 做 的 分 析 完 全 以 程 序 的 静 态 信 息 为 依 据 使 用 该 技 术 的 时 空 开 销 较 大, 因 为 要 分 析 程 序 所 有 可 能 的 执 行 轨 迹, 所 以 相 对 于 动 态 切 片 技 术, 静 态 切 片 技 术 一 般 用 于 程 4
第 5 页 序 理 解 与 软 件 维 护 方 面 Weiser 最 初 提 出 的 程 序 切 片 概 念 就 是 属 于 静 态 切 片 范 畴 2.3.2 动 态 切 片 技 术 (dynamic slicing) 动 态 切 片 技 术 使 用 的 是 运 行 时 分 析, 在 程 序 运 行 时 应 用, 因 此 切 片 的 计 算 过 程 依 赖 于 程 序 的 具 体 输 入 采 用 这 一 技 术, 每 一 次 的 计 算 开 销 小, 但 每 一 次 的 计 算 都 不 尽 相 同, 因 此 动 态 切 片 技 术 多 用 于 程 序 调 试 测 试 方 面 2.3.3 条 件 切 片 技 术 (conditioned slicing) 目 前 对 程 序 的 理 解 主 要 有 两 种 方 法 : 静 态 分 析 或 者 是 动 态 分 析 但 这 两 种 方 法 都 有 些 过 于 极 端, 前 者 对 程 序 的 理 解 只 局 限 于 对 程 序 源 代 码 的 分 析, 获 得 的 是 静 态 信 息, 过 于 片 面 ; 后 者 对 程 序 的 理 解 则 以 程 序 多 次 运 行 的 测 试 结 果 为 基 础, 这 些 测 试 结 果 依 触 发 程 序 运 转 的 外 界 输 入 的 不 同 而 不 同, 又 过 于 复 杂 Canfora Cimitile 和 Lucia 于 1998 年 提 出 的 条 件 切 片 技 术 避 免 了 上 述 两 个 极 端 Canfora 等 人 提 出 的 条 件 切 片 技 术 通 过 增 加 一 个 条 件 扩 展 了 传 统 的 静 态 切 片 准 则 在 进 行 切 片 算 法 时, 只 有 满 足 该 切 片 条 件 的 那 些 输 入 才 会 被 分 析 这 个 条 件 对 应 着 程 序 的 某 个 或 某 些 初 始 状 态 可 以 看 出, 条 件 切 片 是 一 种 施 加 了 一 定 条 件 的 动 态 切 片 如 果 存 在 从 满 足 切 片 条 件 的 任 一 个 初 始 状 态 出 发 都 不 可 能 被 执 行 的 语 句, 那 么 把 这 些 语 句 去 掉 后, 就 得 到 了 在 这 个 切 片 条 件 下 的 程 序 切 片, 即 条 件 切 片 另 外 还 有 分 解 切 片 技 术 (docomposition slicing), 无 定 型 切 片 技 术 (amorphous slicing), 对 象 切 片 技 术 (object slicing) 等 2.4 程 序 切 片 算 法 及 相 关 概 念 为 了 得 到 程 序 切 片, 从 切 片 的 提 出 到 现 在, 程 序 切 片 算 法 也 经 历 了 很 长 的 发 展 过 程 程 序 切 片 算 法 主 要 有 Weiser 的 基 于 数 据 流 过 程 的 算 法 [8] K.J.Ottenstein 和 L.M. Ottenstein [7] 以 及 Horwitz 的 基 于 程 序 依 赖 图 的 [5] 图 可 达 性 算 法 等 Ottenstein 等 在 1984 年 提 出 了 切 片 准 则 由 一 个 程 序 点 p 和 一 个 在 p 定 义 的 或 使 用 的 变 量 v 构 成, 且 在 一 个 程 序 依 赖 图 上 使 用 图 可 达 性 算 法 来 计 算 切 片, 根 据 他 们 对 切 片 含 义 的 理 解, 切 片 是 由 程 序 中 所 有 可 能 影 响 v 5
第 6 页 在 p 点 值 的 语 句 和 谓 词 构 成 1990 年,Horwitz 等 在 文 献 中 [5] 使 用 依 赖 图 来 计 算 切 片, 他 们 开 发 了 一 种 过 程 间 的 程 序 表 示 系 统 依 赖 图, 并 实 现 了 一 个 基 于 系 统 依 赖 图 的 两 阶 段 图 可 达 性 切 片 算 法, 由 于 在 调 用 点 传 递 的 依 赖 流 信 息 中 包 含 被 调 用 过 程 的 上 下 文 环 境, 所 以 该 算 法 的 计 算 精 度 比 以 前 的 算 法 更 高 目 前, 我 们 主 要 用 的 是 这 种 基 于 依 赖 图 的 方 法 2.4.1 程 序 依 赖 图 (Program Dependence Graph,PDG) 程 序 依 赖 图 (PDG) [5] 是 程 序 的 一 种 图 形 表 示, 它 把 控 制 依 赖 和 数 据 依 赖 包 含 在 单 个 的 结 构 中 对 于 程 序 P 的 程 序 依 赖 图, 用 G p 来 表 示, 是 一 种 由 不 同 边 和 结 点 组 成 的 有 向 图,G p 的 结 点 代 表 程 序 P 中 的 赋 值 语 句 (assignment statements) 和 控 制 谓 词 (control predicates), 同 时 G p 还 包 括 三 类 结 点 : 1 入 口 结 点 (entry vertex) 2 对 于 变 量 x, 存 在 于 程 序 P 的 标 准 控 制 流 图 上,x 在 定 义 之 间 使 用, 存 在 一 个 x 的 初 始 化 定 义 结 点, 这 个 结 点 代 表 从 x 的 初 始 状 态 对 x 进 行 赋 值, 这 个 结 点 用 x:=initialstate(x) 来 表 示 3 对 于 在 P 的 结 尾 语 句 (end statement) 中 的 变 量 x, 存 在 一 个 名 为 最 后 使 用 x 的 结 点, 它 代 表 x 最 后 使 用 的 路 径, 用 FinalUse(x) 来 表 示 G p 的 结 点 代 表 程 序 中 元 素 的 独 立 性, 包 括 控 制 依 赖 和 数 据 依 赖 [5] 控 制 依 赖 边 用 真 或 假 来 标 识, 边 的 起 点 总 是 入 口 结 点 或 谓 词 结 点,G p 包 括 从 v 1 到 v 2 的 控 制 依 赖 边 满 足 如 下 条 件 之 一 :v 1 是 入 口 结 点,v 2 代 表 P 中 没 有 被 嵌 套 或 不 在 条 件 循 环 中 的 结 点 ;v 1 代 表 控 制 谓 词,v 2 代 表 被 嵌 套 或 在 v 1 条 件 循 环 中 的 结 点 从 v 1 到 v 2 的 数 据 依 赖 边, 是 如 果 将 与 v 1 和 v 2 有 关 的 顺 序 颠 倒, 程 序 的 计 算 过 程 将 会 改 变 程 序 中 存 在 数 据 依 赖 边 满 足 如 下 条 件 :v 1 是 定 义 变 量 x 的 结 点,v 2 用 到 变 量 x 在 v 1 到 v 2 的 控 制 路 径 中 不 存 在 重 复 定 义 x 下 图 为 一 段 函 数 的 及 其 程 序 依 赖 图 : 6
第 7 页 ENTRY Sum:=0 i:=1 While i<1 FinalUse(i) FinalUse(sum) Sum:=sum+1 i:=i+1 2.4.2 系 统 依 赖 图 (System Dependence Graph,SDG) 2.4.2.1 系 统 依 赖 图 概 念 系 统 依 赖 图 [5] 是 程 序 依 赖 图 的 拓 展, 表 示 包 括 函 数 间 相 互 调 用 的 语 句 系 统 依 赖 图 有 如 下 性 质 : 1 一 个 完 整 的 系 统 包 括 主 函 数 和 一 系 列 的 其 他 函 数 2 程 序 用 return 结 尾 3 参 数 用 变 量 结 果 在 各 函 数 中 传 递 7
第 8 页 2.4.2.2 函 数 调 用 和 参 数 传 递 [5] 参 数 传 递 模 式 以 五 种 新 类 型 结 点 来 表 示 调 用 点 用 call_site 结 点 来 表 示, 函 数 信 息 的 传 递 参 过 四 种 参 数 结 点, 在 调 用 区 域 内, 函 数 信 息 通 过 结 点 actual_in 和 结 点 actual_out 来 传 递, 这 些 结 点 控 制 依 赖 于 调 用 点, 代 表 赋 值 语 句,actual_in 功 能 是 将 实 参 的 值 复 制 到 调 用 暂 缓 区, actual_out 将 返 回 暂 缓 区 的 值 复 制 给 实 参 同 样, 在 被 调 用 区 域 内 的 信 息 传 递 是 通 过 结 点 formal_in 和 结 点 formal_out 来 完 成 的, 这 两 个 结 点 控 制 依 赖 于 过 程 的 入 口 结 点, 代 表 赋 值 语 句,formal_in 是 将 调 用 暂 存 中 的 值 复 制 给 形 参,formal_out 是 将 形 参 的 值 复 制 给 返 回 暂 存 区 利 用 这 种 模 式, 进 程 间 的 数 据 依 赖 就 限 定 在 从 actual_in 结 点 到 formal_in 结 点, 或 从 formal_out 结 点 到 actual_out 结 点 之 中 将 函 数 间 的 程 序 依 赖 图 联 系 起 来 形 成 系 统 依 赖 图 (SDG), 需 要 添 加 三 种 边 : 调 用 边 (call edge), 从 调 用 点 (call_site) 到 相 应 函 数 的 入 口 结 点 ; parameter_in 边, 从 actual_in 结 点 到 相 应 的 被 调 用 函 数 的 formal_in 结 点 ;parameter_out 边, 从 被 调 用 函 数 的 formal_out 结 点 到 调 用 函 数 的 actual_out 结 点 其 中 调 用 边 是 控 制 依 赖 边,parameter_in 和 parameter_out 边 是 数 据 依 赖 边 在 程 序 切 片 时, 各 结 点 的 属 性 及 结 点 之 间 的 依 赖 关 系, 对 切 片 的 分 析 具 有 至 关 重 要 的 作 用 2.4.3 调 用 图 (call graph) 调 用 图 [18] 是 代 表 程 序 间 调 用 关 系 的 有 向 图 每 个 结 点 代 表 一 个 函 数, 每 条 边 (f,g) 代 表 函 数 f 调 用 函 数 g 图 中 环 代 表 程 序 中 的 递 归 函 数 调 用 图 是 一 个 基 本 程 序 分 析 结 果, 可 用 于 人 们 理 解 程 序 或 用 于 更 进 一 步 分 析 程 序, 例 如 对 某 一 变 量 进 行 流 分 析, 最 简 单 的 应 用 是 找 到 没 有 被 调 用 的 程 序 调 用 图 可 被 定 义 来 表 示 准 确 度 的 改 变, 调 用 图 越 准 确, 真 实 程 序 就 越 准 确, 但 要 在 增 大 时 间 和 内 存 开 销 的 代 价 下, 最 准 确 的 调 用 图 是 完 全 上 下 文 敏 感 (context-sensitive) 的, 这 意 识 着 对 于 每 一 个 函 数, 图 中 包 含 每 一 个 可 活 动 的 调 用 栈 的 独 立 结 点 一 个 完 全 上 下 文 敏 感 的 调 用 图 可 很 容 易 地 进 行 动 态 计 算, 尽 管 要 花 费 大 量 的 内 存, 同 时, 它 通 常 不 能 进 行 静 态 计 算, 因 为 对 一 个 大 程 序 来 说 花 费 时 间 会 很 长 最 不 准 确 的 调 用 图 是 上 下 文 不 敏 感 的 (context-insensitive), 这 意 识 着 每 个 函 数 只 有 一 个 结 点 调 用 图 分 为 动 态 调 用 图 和 静 态 调 用 图 动 态 调 用 图 记 录 程 序 执 行 的 过 程, 例 如, 作 为 描 述 文 件 (profiler) 的 输 出 所 以 动 态 调 用 图 可 以 准 确 8
第 9 页 描 述 但 只 能 描 述 程 序 的 一 个 运 行 分 支 静 态 调 用 图 用 于 描 述 程 序 中 所 有 运 行 分 支 在 切 片 过 程 中, 采 用 的 是 静 态 调 用 图, 来 表 示 各 函 数 之 间 的 调 用 关 系 及 其 中 某 些 特 定 变 量 的 数 据 流 向 2.4.4 程 序 切 片 算 法 目 前 我 们 用 的 程 序 切 片 算 法 主 要 是 在 Horwitz 提 出 的 基 于 依 赖 图 的 算 法 的 基 础 上 进 行 改 进 实 现 的 2.4.4.1 摘 要 信 息 (Summary Information) PDG 中 并 非 所 有 的 路 径 都 是 有 效 的, 最 典 型 的 情 况 就 是 当 后 向 切 片 切 到 一 个 函 数 调 用 的 actual_out 结 点 时, 并 非 所 有 的 actual_in 都 会 影 响 到 它 的 取 值, 这 就 需 要 预 先 分 析 被 调 用 函 数 中 每 个 formal_out 由 哪 些 formal_in 决 定 这 类 信 息 称 为 摘 要 信 息 (summary information) [5] 为 得 到 更 精 确 的 过 程 间 切 片, 我 们 必 须 在 建 立 PDG 时 采 用 过 程 间 数 据 流 分 析 的 结 果, 这 样 才 能 将 一 些 结 点 排 除 在 外 适 当 的 过 程 间 摘 要 信 息 包 含 如 下 集 合, 这 些 都 是 在 每 个 过 程 P 中 被 确 定 的 : GMOD(P): 可 以 被 P 或 被 P 调 用 的 函 数 修 改 的 变 量 的 集 合 GREF(P): 可 以 被 P 或 被 P 调 用 的 函 数 使 用 的 变 量 的 集 合 GMOD 和 GREF 集 是 用 来 确 定 哪 些 参 数 结 点 被 包 含 在 PDG 中, 如 下 所 述 : 对 于 每 一 个 过 程 P, 从 属 于 P 的 入 口 结 点 的 参 数 结 点 包 含 一 个 对 GMOD(P) GREF(P) 中 每 个 变 量 的 formal_in 结 点 和 一 个 对 GMOD (P) 每 个 变 量 的 formal_out 结 点 同 样, 对 于 每 个 P 的 被 调 用 点, 从 属 于 调 用 结 点 的 参 数 结 点 包 含 一 个 对 GMOD(P) GREF(P) 中 每 个 变 量 的 actual_in 结 点 和 对 GMOD(P) 中 每 个 变 量 的 actual_out 结 点 ( 对 于 在 GMOD(P) 中 而 不 在 GREF(P) 中 的 变 量 x, 包 含 一 个 actual_in 结 点 和 一 个 formal_in 结 点 是 必 要 的, 因 为 可 能 会 有 一 条 经 过 P 而 x 没 有 被 修 改 的 执 行 路 径, 这 样 以 来,P 的 关 于 x 最 终 结 果 的 切 片 必 须 包 含 x 的 初 始 值,P 中 必 须 含 有 x 的 formal_in 结 点 和 在 P 被 调 用 点 的 相 应 actual_in 结 点 ) 9
第 10 页 2.4.4.2 程 序 切 片 算 法 Horwitz 等 提 出 的 算 法 的 关 键 方 面 是 利 用 系 统 依 赖 图 中 联 系 语 法 (linkage grammar) 特 有 的 边, 这 些 边 代 表 从 过 程 调 用 产 生 的 actual_in 顶 点 到 actual_out 顶 点 的 传 递 数 据 依 赖, 这 种 边 避 免 了 调 用 上 下 文 (calling context) 问 题, 切 片 选 项 也 可 以 允 许 跨 越 调 用 函 数 进 行, 而 不 用 进 入 调 用 函 数 中 才 能 进 行 程 序 间 切 片 算 法 在 下 面 给 出 如 下 所 述, 关 于 结 点 集 合 S 的 系 统 调 用 图 G 的 计 算 过 来 分 为 两 阶 段 进 行 这 两 个 阶 段 都 要 遍 历 系 统 依 赖 图, 沿 着 某 类 边 来 找 到 能 够 到 达 给 定 结 点 集 的 结 点 的 集 合 阶 段 1 的 遍 历 沿 着 流 边, 控 制 边, 调 用 边 和 parameter_in 边, 但 不 沿 parameter_out 边, 阶 段 2 的 遍 历 沿 着 流 边, 控 制 流 和 parameter_out 边, 但 不 沿 着 调 用 边 和 parameter_in 边 10
第 11 页 procedure MarkVerticesOfSlice(G, S) declare G: a system dependence graph S,S : sets of vertices in G begin /* Phase 1: Do not descend into called procedures */ MarkReachingVertices(G, S, (linkage-exit}) /*Phase 2: Do not ascend to call sites */ S := all marked vertices in G MarkReachingVertices(G, S, (linkage-entry. call) ) end procedure MarkReachingVertices(G, V, Kinds) declare G : a system dependence graph V:asetofverticesinG Kinds : a set of kinds of edges v,w:verticesinv WorkList : a set of vertices in G begin WorkList:= v while WorkList f 0 do Select and remove a vertex v from WorkLht Mark v for each vertex w that is a predecessor of v in G such that thereis anedgew AV whosekindisnot inkinds do Insert w into Work%& od od end 程 序 间 切 片 结 果 包 括 阶 段 1 和 阶 段 2 中 确 定 的 结 点 集 合 以 及 与 之 相 关 的 边 的 集 合 为 了 得 到 关 于 函 数 P 中 结 点 s 的 系 统 依 赖 图 的 切 片, 阶 段 1 和 阶 段 2 可 如 下 表 示 : 11
第 12 页 阶 段 1 阶 段 1 确 定 能 够 到 达 s 的 结 点, 这 些 结 点 存 在 于 函 数 P 或 调 用 P 的 函 数 中 被 P 调 用 的 函 数 的 产 生 的 影 响 没 有 被 完 全 忽 略, 从 actual_in 到 actual_out 结 点 ( 次 要 特 征 图 边 ) 的 流 依 赖 边 的 存 在 使 得 仅 通 过 一 个 函 数 调 用 就 可 找 到 到 达 s 的 结 点, 尽 管 图 遍 历 不 是 真 正 意 义 上 进 入 到 被 调 用 函 数 中 阶 段 2 阶 段 2 确 定 能 够 到 达 s 的 结 点, 这 些 结 点 存 在 于 被 P 调 用 的 函 数 或 被 调 用 函 数 P 的 函 数 调 用 的 函 数 中 由 于 以 上 算 法 是 在 遍 历 SDG 的 基 础 上 进 行 的, 而 我 们 现 在 用 的 是 基 于 PDG 的 算 法, 所 以 在 本 算 法 基 础 上, 进 行 了 改 进, 在 计 算 出 完 整 的 摘 要 信 息 的 前 提 下, 同 样 利 用 本 算 法 进 行 两 遍 式 遍 历 PDG, 得 到 完 整 的 过 程 间 切 片 2.4.5 控 制 流 图 (Control Flow Graph) 基 于 依 赖 图 的 切 片 工 具 的 开 发, 能 够 方 便 程 序 员 对 程 序 的 调 试 和 验 证, 但 正 如 前 文 所 说, 程 序 依 赖 图 不 只 包 括 源 代 码 结 点 本 身, 还 包 含 联 接 各 结 点 之 间 依 存 关 系 的 结 点, 而 这 些 结 点 对 于 用 户 来 说 是 没 有 必 要 的, 用 户 往 往 只 关 心 源 代 码 的 数 据 关 系 及 切 片 结 果 所 以, 只 进 行 基 于 依 赖 图 的 切 片 结 果 显 示 是 不 够 的 在 编 译 器 的 后 端, 往 往 使 用 统 一 的 中 间 语 言 形 式, 本 文 的 编 译 平 台 为 Open64 编 译 平 台, 在 后 文 会 对 其 进 行 介 绍,Open64 使 用 的 中 间 语 言 为 WHIRL 形 式,WHIRL 为 Open64 后 端 的 各 个 步 骤 提 供 了 一 个 统 一 的 界 面, WHIRL 支 持 多 种 编 程 语 言, 包 括 C,C++,Java,Fortran77/95 等, 在 Open64 内 部,WHIRL 形 式 的 中 间 语 言 以 自 定 义 的 数 据 结 构 保 存, 为 了 便 于 编 译 器 的 开 发,Open64 提 供 了 一 系 列 函 数 用 于 查 看 WHIRL 形 式 中 间 语 言 及 将 WHIRL 形 式 中 间 语 言 以 ASCII 形 式 输 出 [1] 控 制 流 图 可 以 通 过 如 下 方 法 来 构 造 : 1) 把 中 间 代 码 划 分 为 基 本 块 (basic block) 每 个 基 本 块 是 满 足 下 列 条 件 的 最 大 的 连 续 指 令 序 列 1 控 制 流 只 能 从 基 本 块 中 的 第 一 个 指 令 进 入 该 块 也 就 是 说, 没 有 跳 转 到 基 本 块 中 间 的 转 移 指 令 2 除 了 基 本 块 的 最 后 一 个 指 令, 控 制 流 在 离 开 基 本 块 之 前 不 会 停 止 或 者 跳 转 2) 基 本 块 形 成 了 流 图 的 结 点, 而 流 图 的 边 指 明 了 哪 些 基 本 块 可 能 紧 随 一 个 基 本 块 之 后 运 行 删 除 的 内 容 : 系 12
第 13 页 当 将 中 间 代 码 程 序 划 分 为 基 本 块 之 后, 用 一 个 流 图 来 表 示 它 们 之 间 的 控 制 流 流 图 的 结 点 就 是 这 些 基 本 块 从 基 本 块 B 到 基 本 块 C 之 间 有 一 条 边 当 且 仅 当 基 本 块 C 的 第 一 个 指 令 可 能 紧 跟 在 B 的 最 后 一 个 指 令 之 后 执 行 存 在 这 样 一 条 边 的 原 因 有 两 种 : 1) 有 一 个 从 B 的 结 尾 跳 转 到 C 的 开 头 的 条 件 或 无 条 件 跳 转 语 句 2) 按 照 原 来 的 语 句 序 列 中 的 顺 序,C 紧 跟 在 B 之 后, 且 B 的 结 尾 不 存 在 无 条 件 跳 转 语 句 我 们 说 B 是 C 的 前 驱, 而 C 是 B 的 一 个 后 继 我 们 通 常 会 增 加 两 个 分 别 称 为 入 口 和 出 口 的 结 点 它 们 不 和 任 何 可 执 行 的 中 间 指 令 对 应 从 入 口 到 流 图 的 第 一 个 可 执 行 结 点 有 一 条 边 从 任 何 包 含 了 可 能 是 程 序 的 最 后 执 行 指 令 的 基 本 块 到 出 口 有 一 条 边 通 过 控 制 流 图 的 基 本 块, 可 提 取 出 程 序 的 源 代 码, 就 可 以 满 足 用 户 的 需 求 它 是 基 于 程 序 源 码 基 础 进 行 的, 在 此 基 础 上 进 行 切 片 前 后 的 结 果 显 示 是 完 全 可 靠 的 13
第 14 页 第 三 章 程 序 切 片 工 具 图 形 化 3.1 切 片 工 具 图 形 化 意 义 同 很 多 工 具 软 件 一 样, 切 片 工 具 在 开 发 过 程 中, 测 试 和 调 试 是 主 要 工 作 由 于 切 片 过 程 基 于 依 赖 图, 在 遍 历 依 赖 图 的 过 程 中, 由 于 没 有 图 形 化 的 支 持, 依 赖 图 或 切 片 结 果 中 的 信 息 会 变 得 不 直 观 晦 涩 增 加 了 其 中 的 数 据 结 构 的 理 解 难 度 而 且 切 片 结 果 的 验 证 往 往 运 用 较 大 的 标 准 测 试 集 来 进 行, 我 们 目 前 用 的 是 SPEC CPU2000 [4] 来 进 行 调 试 和 验 证,SPEC CPU2000 是 标 准 性 能 评 测 公 司 [21] (Standard Performance Evaluation Corporation,SPEC) 于 1999 年 12 月 发 布 的 标 准 测 试 集, 用 于 测 试 计 算 机 处 理 器 存 储 器 体 系 结 构 和 编 译 器 等, 包 含 两 个 测 试 包,CINT2000 和 CFP2000,CINT2000 包 含 12 个 基 于 应 用 程 序 的 用 C 和 C++ 写 成 的 测 试 集, 目 前 主 要 用 的 是 CINT2000 中 的 测 试 包, 而 其 中 最 小 的 测 试 集 181.mcf 也 包 含 有 11 个 C 文 件 和 14 个.h 头 文 件, 包 括 注 释 和 空 行 共 约 3000 行 代 码, 其 他 大 部 分 在 万 行 数 量 级 具 体 数 据 统 计 见 附 录 经 过 统 计, 各 测 试 包 的 PDG 规 模 也 相 当 大, 其 中 的 信 息 量 之 大 可 想 而 知, 这 给 测 试 和 调 试 过 程 造 成 了 很 大 的 困 难, 下 表 则 是 各 用 例 的 PDG 规 模 [4] : 用 例 名 结 点 数 边 数 whirl 语 句 数 mcf 2473 5996 935 bzip2 10371 23986 2574 gzip 16653 39122 2844 gap 154233 374202 8970 parser 90979 225985 10132 vpr 99701 233148 12347 twolf 100474 314066 16915 crafty 524225 2489264 17838 perlbmk 1838451 4507344 27323 vortex 1784580 4102499 32331 gcc 8510581 22528484 120312 art 4047 11830 1165 equake 7768 17813 1325 14
第 15 页 ammp 23856 61412 7809 mesa 270 567 117 表 格 3.1 各 用 例 PDG 规 模 可 以 看 出, 如 果 将 这 些 信 息 采 用 文 本 信 息 表 示, 如 在 切 片 过 程 中, 一 般 方 法 是 给 出 所 有 结 点 的 编 号, 以 及 各 边 的 源 结 点 和 目 的 结 点 的 编 号, 而 且 很 多 时 候, 只 有 点 和 边 是 不 够 的, 还 需 要 点 和 边 代 表 的 那 些 数 据 项 的 其 他 信 息 如 果 只 使 用 单 一 文 本 信 息 来 提 取 用 户 所 需, 结 果 只 能 是 事 倍 功 半 在 如 此 大 的 工 作 量 下, 如 果 把 切 片 过 程 的 数 据 结 构 用 图 形 化 工 具 以 图 形 的 方 式 表 示 出 来, 开 发 人 员 就 可 以 灵 活 而 且 容 易 地 观 察 并 理 解 切 片 过 程 的 数 据 结 构 及 依 赖 图 切 片 结 果 信 息, 从 而 准 确 把 握 切 片 过 程 的 每 一 个 环 节 图 形 化 有 比 较 明 显 的 优 势, 它 可 以 利 用 图 元 的 形 状 颜 色 粗 细 等 图 形 可 视 化 专 有 词 汇, 来 简 洁 高 效 地 表 示 点 和 边 代 表 的 那 些 数 据 项 的 其 他 信 息, 编 程 人 员 可 直 观 地 对 其 进 行 分 析 和 查 询, 大 大 提 高 了 工 作 效 率 另 外, 切 片 工 具 用 户 也 会 面 对 如 此 之 大 的 测 试 程 序, 用 户 的 需 求 是 了 解 源 代 码 各 语 句 之 间 的 关 系 及 在 源 码 基 础 上 了 解 相 关 切 片 结 果 所 以 针 对 切 片 结 果 进 行 基 于 控 制 流 图 的 图 形 化 过 程 也 是 非 常 必 要 的 3.2 开 发 平 台 我 们 的 研 究 平 台 是 Open64 开 放 源 码 编 译 器 它 可 以 对 C C++ 和 Fortran 90/95 编 写 的 程 序 进 行 编 译, 可 以 为 Linux/Interl IA-64,X86, CUDA,MIPS 体 系 结 构 生 成 目 标 代 码 它 遵 从 IA-64 Linux ABI 和 API 规 则 开 放 源 码 以 及 详 细 的 文 档 使 我 们 能 够 快 速 熟 悉 编 译 器 的 构 造 并 根 据 我 们 的 需 要 来 灵 活 修 改, 在 这 个 平 台 上 进 行 切 片 工 具 的 开 发 具 有 一 定 的 优 势 删 除 的 内 容 : 集 删 除 的 内 容 : 获 得 程 序 的 源 码, 删 除 的 内 容 : 基 于 控 制 流 图 的 程 序 源 码 的 基 本 块 虽 然 没 有 PDG 结 点 规 模 那 么 大, 但 正 如 附 录 所 示, 测 试 集 代 码 行 是 以 万 计 的, 这 时 的 信 息 量 也 是 很 巨 大 的, 删 除 的 内 容 : 程 序 源 码 3.3 图 形 化 工 具 简 介 把 一 个 数 学 上 的 图 ( 结 点 和 边 的 集 合 ) 变 成 视 觉 上 可 见 的 图, 如 何 让 交 叉 的 边 数 目 最 少, 如 何 让 结 点 的 发 布 比 较 均 匀 这 个 过 程 是 复 杂 的, 涉 及 到 布 局 算 法 人 们 在 这 一 领 域 开 展 了 很 多 研 究, 为 了 能 画 出 具 有 美 感 的 图, 设 计 了 许 多 算 法 为 了 说 明 这 些 算 法 的 适 应 性, 不 少 画 图 工 具 作 为 这 些 研 究 的 成 果 被 开 发 出 来, 如 Udraw ffgraph DOT 人 们 还 开 发 了 一 些 其 他 的 画 图 工 具, 他 们 在 功 能 上 更 加 专 业 化, 如 主 要 用 来 画 编 译 器 中 的 数 据 结 构 的 VCG 和 dflo 15
第 16 页 图 形 用 户 界 面 (GUI) 技 术 的 发 展, 直 接 促 进 了 图 形 可 视 化 工 具 的 进 步 现 在 能 够 利 用 这 些 工 具 比 较 容 易 的 创 建 一 个 图 形 化 的 用 户 界 面, 可 以 为 一 个 原 先 由 文 本 表 示 的 程 序 加 上 一 个 图 形 的 界 面 来 加 强 用 户 交 互, 把 复 杂 的 信 息 由 一 种 比 较 容 易 理 解 的 方 式 表 示 出 来 切 片 过 程 就 是 一 个 能 从 图 形 用 户 界 面 中 获 益 的 以 文 本 为 基 础 的 信 息 的 过 程, 它 的 图 形 用 户 界 面 有 助 于 对 切 片 过 程 的 理 解 3.4 图 形 化 工 具 选 择 在 图 形 化 过 程 中, 不 可 能 只 单 一 地 显 示 某 一 图 形 文 件, 而 必 须 与 之 进 行 交 互, 这 个 信 息 处 理 的 过 程 是 比 较 复 杂 的, 不 能 够 由 图 形 化 工 具 本 身 完 成, 而 需 由 别 的 程 序 或 进 程 来 完 成, 甚 至 还 要 查 询 相 关 数 据 结 构, 所 以 API 是 必 不 可 少 的 通 过 一 定 范 围 内 的 调 查 [16], 我 了 解 到 Udraw 和 VCG 是 当 前 在 国 际 编 译 研 究 界 比 较 流 行 的 图 形 可 视 化 工 具 Udraw 具 备 API 而 VCG 不 具 备 在 Open64 中, 与 Udraw 的 接 口 已 经 封 装 在 类 davinci 中, 管 道 建 立 和 维 护 的 工 作 已 经 由 该 类 隐 藏 3.4.1 Udraw(Graph) 简 介 Udraw(Graph) 是 德 国 不 来 梅 大 学 (Universität Bremen) 计 算 机 科 学 系 推 出 的 一 个 通 用 的 有 向 图 输 出 工 具 目 标 是 让 所 有 的 应 用 程 序 都 能 在 比 较 短 的 时 间 内 利 用 Udraw 提 供 一 个 图 形 用 户 界 面 这 样 应 用 程 序 的 程 序 员 就 不 必 关 心 图 的 布 局 算 法 和 计 算 机 图 形 学 的 问 题 了, 而 这 些 问 题 常 常 是 图 形 用 户 界 面 设 计 的 难 点 Udraw 通 过 一 种 叫 语 法 表 示 (term presentation) 得 到 待 表 示 的 图 的 信 息, 主 要 是 结 点 和 边 的 集 合 语 法 表 示 是 一 种 纯 文 本 的 ASCII 码 格 式 Udraw 可 以 通 过 语 法 表 示 出 结 点 和 边 的 各 种 属 性, 包 括 颜 色 形 状 文 本 表 示 等, 同 时 还 可 对 相 关 结 点 和 边 进 行 操 作, 如 隐 藏 显 示 结 点 或 边, 标 注 相 关 属 性 等 3.4.2 Udraw 接 口 Udraw 可 以 通 过.daVinci 或.udg 为 后 缀 的 文 件, 也 可 以 通 过 API 从 其 他 应 用 程 序 来 得 到 语 法 表 示 Udraw 同 应 用 程 序 之 间 的 交 互 如 下 图 : 16
第 17 页 应 用 程 序 通 过 建 立 与 Udraw 之 间 的 两 条 管 道 进 行 通 讯 : 一 条 管 道 从 应 用 程 序 到 Udraw, 用 于 应 用 程 序 向 Udraw 发 送 命 令 ; 另 一 条 管 道 从 Udraw 到 应 用 程 序, 用 于 Udraw 向 应 用 程 序 发 送 信 息 ( 包 括 鼠 标 和 键 盘 操 作 的 信 息 ) 17
第 18 页 第 四 章 切 片 工 具 图 形 化 设 计 4.1 Udraw 语 法 表 示 [19] Udraw 采 用 的 语 法 表 示 是 一 种 纯 文 本 的 ASCII 码 格 式, 能 够 对 图 中 结 点 和 边 的 各 种 属 性 进 行 表 示, 并 具 有 很 强 的 交 互 功 能 Udraw 的 语 法 中, 子 语 法 结 构 被 封 装 在 父 语 法 结 构 中, 例 如, parent[child1,child2,child3], 括 号 [ ] 用 于 包 括 一 系 列 逗 号 分 隔 的 子 语 法 这 种 父 子 语 法 结 构 可 用 于 递 归 循 环, 每 个 子 结 构 也 可 以 同 样 有 自 己 的 子 结 构, 如 此 循 环 这 种 符 号 表 示 支 持 了 树 型 结 构 的 递 归 循 环 这 种 语 法 表 示 很 容 易 理 解, 下 面 为 一 简 单 的 Udraw 图 形, 以 此 来 说 明 Udraw 的 语 法 结 构 相 应 Udraw 语 法 格 式 如 下 : 18
第 19 页 4.2 切 片 工 具 图 形 化 层 次 化 设 计 4.2.1 层 次 化 设 计 原 因 在 程 序 切 片 过 程 中, 由 于 引 入 过 程 间 切 片, 单 一 函 数 的 PDG 已 无 法 满 足 要 求, 上 文 中 已 经 列 出 PDG 的 规 模, 可 想 而 知,PDG 信 息 量 之 大, 这 样 以 来, 切 片 过 程 中 对 PDG 的 表 示 就 显 得 力 不 从 心, 结 果 图 太 大 会 造 成 显 示 时 间 过 长, 而 且 结 果 图 包 含 大 量 的 结 点 和 边, 这 些 边 几 乎 占 满 整 个 屏 幕, 而 且 彼 此 交 错, 根 本 无 法 辨 认 结 点 和 边 的 关 系, 更 不 用 说 对 其 进 行 相 关 操 作 在 开 始 试 验 时, 把 整 个 181.mcf 的 所 有 PDG 同 时 显 示 在 一 个 屏 幕 上 后, 程 序 员 简 直 无 从 下 手, 所 以 必 须 采 用 层 次 化 设 计 此 图 为 仅 将 181.mcf 的 main 函 数 PDG 显 示 结 果 : 19
第 20 页 如 图 仅 为 测 试 集 中 最 小 例 子 的 main 函 数 的 PDG 显 示, 由 于 图 信 息 量 太 大, 图 示 仅 能 辨 认 出 基 本 的 结 点 和 边, 其 他 信 息 已 无 从 辨 认, 这 给 程 序 员 的 调 试 过 程 造 成 了 很 大 的 困 难 另 外, 由 于 程 序 员 在 调 试 过 程 中 的 需 求 有 所 不 同, 有 的 时 候 不 需 要 显 示 所 有 函 数 的 PDG 结 果, 有 的 时 候 函 数 PDG 显 示 的 结 果 也 不 同 例 如, 在 切 片 过 程 中, 程 序 员 有 时 只 想 在 调 用 图 的 层 面 上 理 解 切 片 结 果, 在 调 用 图 的 基 础 上, 能 够 很 直 观 地 看 到 各 函 数 的 调 用 关 系 是 否 与 切 片 相 关 等 信 息, 同 时, 函 数 中 种 子 数 目 也 可 同 时 显 示 在 这 一 层 面 上 有 时, 程 序 员 对 同 一 调 用 函 数 需 要 显 示 不 同 的 PDG 结 果, 例 如, 在 没 有 进 行 程 序 切 片 时, 程 序 员 在 调 试 程 序 过 程 中, 需 要 显 示 整 个 函 数 的 PDG 结 果, 而 在 程 序 切 片 之 后, 根 据 不 同 种 子 的 要 求, 需 要 显 示 切 片 之 后 函 数 PDG 的 结 果, 这 样 来 说, 在 程 序 切 片 前 后, 函 数 的 PDG 显 示 结 果 是 不 同 的, 而 且, 程 序 切 片 之 后, 根 据 程 序 员 对 PDG 显 示 的 需 求, 对 各 种 情 况 函 数 PDG 的 显 示 也 是 不 同 的 所 以, 必 须 进 行 层 次 化 设 计 才 能 达 到 程 序 员 的 这 些 需 求 面 向 用 户 层 的 控 制 流 图 的 图 形 化 设 计 同 样 需 要 层 次 化, 控 制 流 图 也 是 以 函 数 为 基 本 单 位, 在 调 用 图 的 基 础 上 进 行 的 第 二 层 的 设 计, 同 函 数 PDG 显 示 要 求 相 似, 控 制 流 图 也 需 要 进 行 切 片 前 和 切 片 后 的 显 示, 根 据 切 片 种 子 的 不 同, 显 示 不 同 的 切 片 结 果 而 且, 控 制 流 图 的 引 入 增 加 了 本 图 形 化 工 具 第 二 层 的 功 能, 用 户 可 以 在 函 数 PDG 和 控 制 流 图 的 显 示 上 进 行 不 同 的 切 换 这 些 功 能 都 要 求 本 工 具 进 行 层 次 化 设 计 20
第 21 页 4.2.2 层 次 化 设 计 4.2.2.1 层 次 化 设 计 总 体 构 架 在 本 文 设 计 中, 由 于 PDG 时 间 和 空 间 开 销 太 大, 所 以 在 实 验 过 程 中 进 行 分 层 显 示 在 整 个 过 程 中, 调 用 图 是 第 一 个 层 次, 在 调 用 图 中 可 对 各 函 数 间 调 用 关 系 进 行 不 同 描 述, 同 时 对 函 数 切 片 结 果 进 行 初 步 表 示 ; 第 二 层 是 单 个 函 数 PDG 和 控 制 流 图 的 显 示 在 第 二 层 中,PDG 和 控 制 流 图 又 可 以 做 不 同 结 果 的 显 示,Udraw 在 与 用 户 交 互 的 基 础 上, 确 定 需 求, 进 行 第 二 层 PDG 和 控 制 流 图 的 不 同 结 果 显 示 在 调 用 图 层 次 中, 除 了 进 行 函 数 间 基 本 调 用 关 系 的 显 示 外, 还 对 函 数 中 种 子 的 情 况 分 类 显 示, 以 便 程 序 员 能 够 在 调 用 图 层 面 上 直 观 地 分 析 出 切 片 种 子 情 况, 另 外, 这 种 显 示 也 方 便 与 各 函 数 进 行 交 互, 进 行 PDG 和 控 制 流 图 不 同 结 果 的 显 由 于 不 同 种 子 对 应 不 同 的 切 片 结 果, 切 片 结 果 也 能 够 反 映 在 调 用 图 层 面 上, 而 程 序 员 往 往 需 要 首 先 在 这 个 层 面 上 了 解 各 函 数 切 片 的 情 况, 所 以 在 调 用 图 层 面 上 还 需 实 现 切 片 结 果 的 显 示 功 能, 这 个 功 能 是 通 过 用 户 需 求 的 不 同, 与 Udraw 进 行 交 互 来 实 现 不 同 结 果 的 显 示 的 在 显 示 函 数 PDG 的 层 次 中, 除 了 实 现 基 本 函 数 PDG 的 显 示 之 外, 还 根 据 程 序 员 需 求 的 不 同, 对 不 同 结 果 PDG 进 行 分 类 显 示 在 调 用 图 层 次 中, 程 序 员 可 通 过 交 互 功 能 对 不 同 种 子 的 相 关 调 用 函 数 进 行 结 果 显 示, 同 样, 在 此 过 程 中, 程 序 员 会 需 要 进 行 切 片 后 的 PDG 结 果 显 示 在 显 示 控 制 流 图 的 层 次 中, 进 行 函 数 切 片 前 和 切 片 后 控 制 流 图 的 显 示, 以 基 本 块 为 单 位 进 行 控 制 流 图 的 图 形 化 工 作 同 样, 在 调 用 图 层 次 中, 用 户 通 过 交 互 功 能 对 不 同 种 子 的 相 关 调 用 函 数 进 行 结 果 显 示, 在 此 基 础 上 进 行 切 片 后 控 制 流 图 结 果 显 示 鉴 于 程 序 员 的 需 求 分 析, 层 次 化 显 示 总 体 设 计 如 下 : 函 数 的 调 用 图 PDG 和 控 制 流 图 是 在 Open64 编 译 器 运 行 过 程 中 生 成 的, 都 采 用 树 型 结 构, 对 应 相 应 的 类 结 构 收 集 相 关 种 子 函 数, 并 收 集 与 种 子 有 关 的 切 片 结 果, 便 于 后 文 显 示 绘 制 函 数 PDG 和 控 制 流 图, 将 函 数 有 关 PDG 结 构 以 Udraw 语 法 格 式 写 入 相 关 Udraw 文 件 中 绘 制 函 数 调 用 图, 显 示 含 有 种 子 的 函 数, 并 分 类 显 示 种 子 及 行 号 在 调 用 图 输 出 后, 激 活 交 互 处 理 功 能, 根 据 用 户 选 择 的 函 数, 输 出 调 用 图 切 片 结 果 或 相 关 PDG 和 控 制 流 图 结 果 Open64 运 行 终 止 后, 相 关 Udraw 文 件 仍 然 保 留, 以 方 便 用 户 手 工 重 21
第 22 页 现 相 关 PDG 和 控 制 流 图 结 构 4.2.2.2 层 次 化 设 计 实 现 函 数 调 用 图 是 在 Open64 编 译 器 运 行 过 程 中 生 成 的, 采 用 树 型 结 构, 以 main 函 数 为 根 结 点, 其 他 的 结 点 和 边 在 main 函 数 的 调 用 过 程 中 生 成, 生 成 后 所 有 结 点 和 边 被 放 在 类 NODE_ITER 中, 类 中 包 含 结 点 与 结 点 结 点 与 边 边 与 边 之 间 的 关 系 所 以, 遍 历 此 树 型 结 构, 就 可 遍 历 整 个 调 用 图 在 图 形 化 调 用 图 过 程 中, 采 用 的 是 调 用 图 结 构 的 深 度 遍 历, 即 递 归 调 用 各 结 点 的 绘 图 子 函 数 而 Udraw 的 语 法 表 示 恰 好 支 持 这 种 递 归 算 法 的 实 现 Udraw 的 语 法 中, 子 语 法 结 构 被 封 装 在 父 语 法 结 构 中, 例 如, parent[child1,child2,child3], 括 号 [ ] 用 于 包 括 一 系 列 逗 号 分 隔 的 子 语 法 这 种 父 子 语 法 结 构 可 用 于 递 归 循 环, 每 个 子 结 构 也 可 以 同 样 有 自 己 的 子 结 构, 如 此 循 环 这 种 符 号 表 示 支 持 了 树 型 结 构 的 递 归 循 环 有 如 下 程 序 段 : int c(){...} int b(){ c();} int a(){ b(); c();} int main(){ a(); c();} 此 程 序 调 用 图 Udraw 语 法 表 示 为 : 22
第 23 页 [l("3",n("",[a("object","3 main\n"),a("color","lightblue")],[l("4",e("",[],l("0",n("",[a("object"," 0 c\n"),a("color","lightblue")],[])))),l("3",e("",[],l("2",n("",[a("object", "2 a\n"),a("color","lightblue")],[l("2",e("",[],r("0"))),l("1",e("",[],l("1",n("",[a("object","1 b\n"),a("color","lightblue")],[l("0",e("",[],r("0"))),])))),])))),]))] 如 上 述 语 法 所 述, 结 点 采 用 淡 蓝 色 表 示, 边 属 性 为 默 认 表 示,Udraw 中 默 认 表 示 为 黑 色 实 线 单 向 箭 前 头 通 过 此 Udraw 语 法 表 示 出 各 结 点 和 边, 并 将 其 写 到 文 件 中, 通 过 Udraw 和 编 译 器 的 接 口, 显 示 到 屏 幕 上 : 同 样, 函 数 PDG 也 是 在 Open64 编 译 器 运 行 过 程 中 生 成 的,PDG 同 样 采 用 树 型 结 构, 以 每 个 函 数 入 口 entry 为 根 结 点, 生 成 其 他 结 点 和 边,PDG 结 点 和 边 及 与 此 相 关 的 属 性 关 系 放 在 类 PDG_DIRECTED_GRAPH16 中, 在 绘 制 函 数 23
第 24 页 PDG 过 程 中, 同 样 遍 历 此 树, 递 归 调 用 PDG 结 点 和 边 的 画 图 函 数, 根 据 不 同 属 性 输 出 显 示 结 果 有 如 下 程 序 段 : #ifdef _PROTO_ cost_t Bea_Compute_red_cost( arc_t *arc ) #else cost_t bea_compute_red_cost( arc ) arc_t *arc; #endif { return arc->cost - arc->tail->potential + arc->head->potential; } 此 函 数 PDG 的 Udraw 语 法 表 示 比 较 复 杂, 显 示 在 屏 幕 上 效 果 图 为 : 24
第 25 页 由 于 图 的 Udraw 语 法 结 构 比 较 复 杂, 此 处 只 做 分 类 叙 述 : 结 点 的 不 同 颜 色 通 过 属 性 语 法 a("color","color") 来 表 示, 同 样 边 的 不 同 属 性 也 通 过 边 的 属 性 语 法 a("edgecolor","edgecolor") 来 表 示, 另 外, 结 点 上 的 显 示 信 息 是 通 过 语 法 a("object","object") 来 标 注 的, 通 过 此 属 性, 可 以 完 成 后 文 将 要 叙 述 的 查 找 功 能, 结 点 的 形 状 此 处 用 椭 圆 形 来 表 示 a("_go","ellipse"), 其 他 属 性 都 与 之 类 似, 仅 对 其 中 一 个 结 点 和 边 的 Udraw 语 法 表 示 如 下 : l("1",n("",[a("object","1"),a("color","lightblue"),a("info","1 ENTRY_VERTEX"),a("_GO","ellipse")],[l("6",e("",[a("EDGECOLOR"," yellow"),a("info","parm_in_edge")] 由 此 可 见, 对 于 很 简 单 的 程 序 段 来 说,PDG 的 表 示 包 括 Udraw 文 件 的 书 写 都 是 很 复 杂 的 一 项 工 程 所 以, 使 用 层 次 化 表 示 及 递 归 算 法 进 行 调 用 图 和 PDG 的 绘 制 是 必 要 的 控 制 流 图 的 显 示 和 函 数 PDG 的 显 示 相 似, 控 制 流 图 的 结 点 和 边 的 相 关 属 性 存 在 于 类 BB_NODE 中, 同 样 采 用 树 型 结 构 存 储, 生 成 过 程 中 遍 历 此 树, 进 行 控 制 流 图 的 绘 制 如 有 如 下 程 序 段 : void main() { int a; int b; int c=a+b; int d=a+c; printf("%d",c); } 此 main 函 数 的 控 制 流 图 如 下 : 25
第 26 页 图 中 只 对 基 本 块 进 行 基 本 区 分, 一 个 基 本 块 为 一 个 结 点, 同 样 使 用 Udraw 的 基 本 语 法 对 其 表 示 如 下 : [ l("bb1", n("1", [a("object","1\n"), a("color","lightblue")], [e("",[],r("bb2")), ])), l("bb2",n("2", [a("object","2\n1 void main()\r\n2 \\{\r\n4 \tint b;\r\n5 \tint c=a+b;\r\n6 \tint d=a+c;\r\n7 \tprintf(\"%d\",c);\r\n"), a("color","lightblue")], [e("",[],r("bb3")), ])), l("bb3", n("3", [a("object","3\n"), a("color","lightblue")], [ ])),] 4.3 设 计 过 程 及 交 互 实 现 从 上 节 看 来, 为 满 足 程 序 员 的 具 体 要 求, 必 须 对 调 用 图 及 PDG 的 结 点 和 边 进 行 分 类 显 示, 才 能 使 程 序 员 在 调 试 切 片 过 程 中 更 直 观 对 其 进 行 把 握 下 面 对 其 功 能 进 行 分 类 介 绍 26
第 27 页 4.3.1 调 用 图 的 功 能 实 现 程 序 员 在 切 片 过 程 中, 分 析 调 用 图 时, 需 要 得 到 如 下 信 息 : 1 各 函 数 之 间 的 基 本 调 用 关 系 ; 2 进 行 切 片 时 函 数 中 的 种 子 情 况 ; 3 根 据 不 同 种 子 进 行 调 用 图 基 础 上 的 切 片 结 果 显 示 ; 4 根 据 不 同 种 子 的 切 片 结 果 显 示 下 层 的 函 数 PDG; 5 如 进 行 无 切 片 结 果 的 PDG 显 示, 设 置 相 关 选 项 基 于 以 上 需 求, 在 图 形 化 调 用 图 过 程 中, 进 行 个 性 化 处 理, 具 体 内 容 如 下 所 述 : 1 由 于 程 序 中 各 函 数 调 用 关 系 比 较 复 杂, 例 如 A 函 数 会 多 次 调 用 B 函 数, 而 在 调 用 图 显 示 过 程 中, 这 种 情 况 是 不 可 避 免 的, 所 以 开 始 时 会 造 成 函 数 间 调 用 的 冗 余 显 示, 显 示 过 程 中 边 的 条 数 代 表 了 函 数 间 的 调 用 次 数, 这 样 以 来 程 序 员 很 难 在 如 此 之 多 的 冗 余 边 中 直 观 看 出 其 调 用 关 系, 所 以, 设 计 之 初, 便 引 入 位 向 量 对 调 用 边 进 行 存 取, 并 仅 显 示 函 数 之 间 的 一 条 调 用 边, 这 样 可 方 便 程 序 员 的 分 析 2 程 序 员 在 调 试 过 程 需 要 了 解 在 调 用 图 层 次 上 种 子 的 情 况, 针 对 这 一 需 求, 我 对 包 含 种 子 的 函 数 进 行 不 同 颜 色 的 显 示, 同 时, 把 种 子 显 示 在 其 子 结 点 中, 方 便 交 互 功 能 的 完 成 3 不 同 种 子 对 应 的 切 片 结 果 是 不 同 的, 在 调 用 图 基 础 上 静 态 显 示 切 片 结 果 的 方 案 是 不 可 行 的, 所 以 在 第 2 步 基 础 上, 通 过 同 不 同 种 子 的 交 互, 用 不 同 颜 色 来 显 示 函 数 切 片 结 果 4 运 用 交 互 功 能 进 行 PDG 显 示 是 层 次 化 设 计 的 基 本 要 求, 但 函 数 PDG 包 含 切 片 前 和 切 片 后 两 种 结 果, 所 以, 在 第 3 步 的 基 础 上, 可 对 函 数 PDG 进 行 切 片 前 或 切 片 后 的 显 示 5 程 序 员 同 样 需 要 对 未 经 切 片 的 函 数 的 PDG 进 行 显 示 并 分 析, 但 在 第 3 和 第 4 步 已 对 函 数 进 行 了 切 片 显 示, 所 以 增 设 一 个 控 制 选 项 可 以 控 制 切 片 前 后 调 用 图 显 示 的 变 化 情 况, 这 里 用 增 设 根 结 点 show_pdg 来 实 现 针 对 程 序 员 的 需 求 进 行 的 图 形 化 处 理 实 例 将 在 下 章 进 行 介 绍 27
第 28 页 4.3.2 函 数 PDG 的 功 能 实 现 4.3.2.1 函 数 PDG 功 能 需 求 在 切 片 过 程 中, 程 序 员 对 函 数 PDG 的 要 求 相 对 调 用 图 更 高, 所 以 图 形 化 PDG 过 程 所 实 现 的 功 能 更 加 具 体 1 函 数 PDG 需 区 分 切 片 前 和 切 片 后 结 果 ; 2 在 进 行 切 片 前 显 示 时, 需 对 不 同 结 点 及 边 进 行 区 别 显 示 ; 3 在 进 行 切 片 后 显 示 时, 需 对 是 否 在 切 片 中 的 结 点 及 边 进 行 区 别 显 示 ; 4 需 对 三 类 种 子 ( 源 种 子 条 件 种 子 终 结 种 子 ) 进 行 相 关 区 别 标 注 ; 5 需 实 现 根 据 不 同 结 点 信 息 进 行 结 点 查 找 的 功 能 ; 6 由 于 结 点 属 性 信 息 量 大, 不 能 同 时 显 示 在 结 点 上, 需 实 现 隐 藏 显 示 功 能 ; 7 由 于 边 上 不 能 进 行 文 本 显 示, 所 以 需 实 现 隐 藏 显 示 功 能 基 于 如 上 需 求, 相 关 实 现 在 下 文 中 介 绍 4.3.2.2 函 数 PDG 功 能 处 理 在 调 用 图 显 示 中, 实 现 两 层 之 间 的 交 互 功 能, 可 实 现 切 片 前 后 函 数 PDG 不 同 显 示 功 能 在 没 有 进 行 切 片, 或 没 有 对 种 子 进 行 选 取 的 的 情 况 下,PDG 显 示 结 果 是 把 PDG 所 有 结 点 和 边 的 信 息 全 部 显 示 出 来, 以 方 便 程 序 员 了 解 函 数 PDG 信 息 具 体 说 来, 是 显 示 各 PDG 结 点 和 边, 标 注 出 各 结 点 和 边 的 相 关 属 性, 把 相 关 信 息 显 示 在 结 点 和 边 的 外 观 上, 包 括 颜 色 形 状 等, 不 同 结 点 和 边 的 属 性 如 表 格 所 示 : 结 点 属 性 ENTRY 结 点 EXIT 结 点 CALL 结 点 WHIRL 结 点 PHI 结 点 MU 结 点 CHI 结 点 28 结 点 颜 色 浅 蓝 色 浅 蓝 色 黄 色 深 绿 色 白 色 白 色 白 色
第 29 页 ACTUAL_IN 结 点 ACTUAL_OUT 结 点 FORMAL_IN 结 点 FORMAL_OUT 结 点 浅 绿 色 浅 粉 色 紫 色 灰 色 表 格 4.1 函 数 PDG 结 点 外 观 属 性 边 属 性 控 制 依 赖 边 数 据 依 赖 边 PARM_IN 边 PARM_OUT 边 边 颜 色 蓝 色 绿 色 黄 色 粉 色 表 格 4.2 函 数 PDG 边 外 观 属 性 由 于 显 示 空 间 的 局 限 性, 把 结 点 的 所 有 信 息 显 示 在 结 点 外 观 上, 会 造 成 显 示 冗 余, 而 且 程 序 员 不 能 很 好 地 对 其 提 取 信 息, 所 以, 我 只 在 结 点 上 显 示 了 关 键 属 性, 包 括 结 点 号 结 点 类 型 函 数 名 WHILR 行 号, 当 然, 不 是 所 有 的 结 点 都 具 有 这 几 种 属 性, 所 以, 不 同 结 点 的 显 示 效 果 不 同 在 进 行 切 片, 或 选 择 含 有 切 片 结 果 的 函 数 时, 函 数 PDG 显 示 则 只 显 示 是 否 在 切 片 中 两 种 情 况, 即 在 切 片 中 的 PDG 结 点 及 边 用 不 同 颜 色 显 示, 不 在 切 片 中 的 PDG 结 点 及 边 则 用 白 色 和 灰 色 显 示, 另 外, 增 加 显 示 种 子 结 点 的 功 能, 种 子 结 点 分 三 类 源 种 子 (source seed) 终 结 种 子 (sink seed) 和 条 件 种 子 (block seed), 将 这 三 类 种 子 结 点 以 双 线 框 框 起, 并 在 OBJECT 结 构 中 显 示 其 种 子 类 别, 方 便 查 找 其 他 属 性 功 能 与 不 含 切 片 结 果 PDG 显 示 相 同 显 示 在 结 点 上 的 属 性 通 过 Udraw 语 法 定 义 的 OBJECT 结 构 来 定 义, OBJECT 结 构 中 表 示 的 信 息 则 输 出 到 屏 幕 上, 而 且 OBJECT 结 构 中 的 信 息 可 以 支 持 对 结 点 的 查 找 功 能, 这 也 是 在 结 点 上 进 行 多 属 性 显 示 的 另 一 个 原 因 用 户 在 切 片 调 试 和 验 证 过 程 中, 需 要 对 某 些 属 性 的 PDG 结 点 进 行 查 找, 而 由 于 函 数 的 PDG 图 相 对 比 较 大, 手 工 查 找 工 作 量 会 很 大, 而 且 准 确 率 不 高, Udraw 对 图 的 操 作 提 供 了 很 多 功 能, 如 查 找 功 能, 而 查 找 的 匹 配 字 段 就 包 含 在 OBJECT 结 构 中 同 时 查 找 功 能 还 提 供 了 精 确 查 找 和 模 糊 匹 配, 这 对 程 序 调 试 人 员 来 说 也 是 很 重 要 的 当 然, 函 数 PDG 中 结 点 和 边 的 属 性 远 远 不 止 于 此, 还 有 其 他 的 属 性 没 有 在 屏 幕 上 输 出, 例 如, 边 的 属 性 等,Udraw 语 法 结 构 中 包 含 了 INFO 结 构, INFO 结 构 中 的 信 息 没 有 在 屏 幕 上 输 出, 但 可 以 按 意 愿 显 示 出 来, 这 对 于 信 息 量 比 较 多 的 PDG 结 点 来 说 也 是 很 重 要 的 功 能 29
第 30 页 4.3.3 控 制 流 图 的 功 能 实 现 用 户 需 要 获 得 的 只 是 程 序 源 代 码 的 控 制 流 关 系 及 切 片 后 程 序 各 语 句 的 切 片 结 果, 所 以 用 图 形 化 控 制 流 图 需 要 实 现 : 1 函 数 各 语 句 之 间 的 控 制 流 关 系 ; 2 切 片 后 控 制 流 图 的 切 片 结 果 ; 针 对 用 户 需 求 图 形 化 过 程 中 进 行 的 处 理 如 下 : 1 在 完 成 函 数 控 制 流 图 显 示 后, 将 其 中 不 含 WHIRL 语 句 的 基 本 块 进 行 删 除, 只 显 示 对 用 户 有 用 的 基 本 块 2 由 于 一 个 基 本 块 中 的 语 句 不 一 定 全 部 在 切 片 中 或 完 全 不 在 切 片 中, 而 Udraw 没 有 对 同 一 结 点 进 行 不 同 属 性 显 示 的 功 能, 所 以 显 示 切 片 结 果 的 过 程 中, 为 了 进 行 切 片 结 果 的 不 同 显 示, 将 基 本 块 再 进 行 分 块 显 示, 使 得 一 个 分 块 中 的 语 句 能 够 统 一 都 在 切 片 结 果 中 或 不 在 切 片 结 果 中 删 除 的 内 容 : 函 4.3.4 交 互 功 能 实 现 在 进 行 调 用 图 函 数 PDG 和 控 制 流 图 功 能 实 现 的 过 程 中, 因 为 应 用 层 次 化 设 计, 在 这 两 层 的 显 示 过 程 中 必 须 进 行 交 互 才 能 实 现 层 次 之 间 的 紧 密 联 系 Udraw 和 编 译 器 的 交 互 API 封 装 在 类 davinci 中, 用 户 对 Udraw 进 行 的 操 作 通 过 API, 传 回 编 译 程 序, 进 行 相 关 操 作, 在 本 工 具 软 件 中, 进 行 两 种 交 互, 分 别 是 显 示 相 关 种 子 函 数 切 片 结 果 和 显 示 相 关 函 数 PDG 和 控 制 流 图 函 数 调 用 图 PDG 和 控 制 流 图 的 显 示 文 件 是 在 编 译 过 程 中 写 在 相 应 udraw 文 件 中 的, 函 数 调 用 图 的 udraw 文 件 直 接 写 在 to_display 文 件 中, 通 过 Udraw 和 编 译 器 的 接 口 类 davinci 中 直 接 输 出 到 屏 幕 上 而 函 数 PDG 和 控 制 流 图 的 相 应 davinci 文 件 则 保 存 在 相 应 的 文 件 夹 中, 方 便 用 户 手 工 重 现 各 种 函 数 PDG 和 控 制 流 图 不 含 切 片 结 果 的 PDG 图 形 文 件 保 存 在 show_pdg 文 件 夹 中, 控 制 流 图 保 存 在 CFG_daVinci 中, 在 进 行 交 互 过 程 中, 利 用 文 件 夹 的 名 称 及 相 应 函 数 的 匹 配 来 调 用 相 关 udraw 图 形 文 件 含 有 切 片 结 果 的 PDG 图 形 文 件 保 存 在 show_pdg_slice 文 件 夹 中, 控 制 流 图 保 存 在 show_cfg_slice 中, 下 级 文 件 夹 为 含 有 种 子 编 号 子 文 件 夹, 在 进 行 交 互 过 程 中, 利 用 选 择 种 子 的 不 同 结 果, 匹 配 到 不 同 切 片 结 果 函 数, 调 用 相 应 函 数 PDG 和 控 制 流 图 在 输 出 的 函 数 调 用 图 上, 单 击 种 子 号, 即 可 显 示 相 关 种 子 的 切 片 结 果, 同 时 对 切 片 结 果 中 的 边 进 行 分 类 显 示, 函 数 PDG 显 示 中, 切 片 结 果 中 的 边 30
第 31 页 为 红 色 标 记, 非 切 片 结 果 中 的 边 灰 色 显 示, 控 制 流 图 的 显 示 中, 切 片 结 果 的 结 点 为 红 色, 非 切 片 结 果 中 结 点 为 蓝 色 由 于 第 二 层 为 函 数 PDG 和 控 制 流 图 的 显 示, 所 以 增 加 控 制 选 项 对 其 进 行 切 片, 用 pdg_drawing 来 进 行 PDG 的 显 示,cfg_drawing 进 行 控 制 流 图 的 显 示, 当 两 个 选 项 都 不 开 时, 切 片 工 具 不 进 行 图 形 化 显 示 4.3.5 本 文 程 序 整 体 流 程 可 以 看 出, 为 实 现 以 上 各 部 分 的 功 能, 不 但 要 充 分 理 解 Open64 编 译 平 台 中 各 类 及 数 据 结 构 及 相 关 函 数, 而 且 要 在 文 件 相 关 函 数 中 添 加 新 的 类 和 函 数, 在 不 影 响 编 译 器 其 他 功 能 的 前 提 下, 实 现 本 工 具 提 供 的 各 功 能 本 文 程 序 整 体 流 程 如 下 : 编 译 器 生 成 调 用 图 生 成 控 制 流 图 生 成 函 数 PDG 设 计 调 用 图 设 计 控 制 流 图 设 计 函 数 PDG 编 译 器 与 udraw 相 关 接 口 udraw 31
第 32 页 第 五 章 图 形 化 设 计 实 例 本 文 所 用 实 例 是 SPEC CPU2000 中 181.mcf,SPEC CPU2000 已 在 前 文 中 介 绍 过, 其 中 的 181.mcf 是 其 中 最 小 的 实 例, 下 文 将 以 它 为 例 来 进 行 实 例 说 明 5.1 调 用 图 的 实 例 实 现 由 于 在 切 片 过 程 中 需 求 不 同, 第 二 层 显 示 函 数 PDG 和 控 制 流 图 需 要 通 过 不 同 开 关 来 切 换, 用 pdg_drawing 和 cfg_drawing 来 控 制 第 二 层 的 不 同 显 示 结 果, 而 在 这 两 个 开 关 的 控 制 下, 第 一 层 调 用 图 的 显 示 是 不 变 的 下 图 是 pdg_drawing=on 情 况 下 的 调 用 图 显 示 结 果 : 图 中 显 示 结 点 号 及 函 数 名, 箭 头 方 向 为 函 数 的 调 用 情 况 在 pdg_drawing 的 情 况 下, 对 程 序 进 行 切 片, 函 数 中 包 含 切 片 结 果 在 调 用 图 中 必 须 对 存 在 程 序 切 片 标 准 中 相 关 种 子 的 函 数 进 行 显 示, 以 方 便 32
第 33 页 切 片 过 程 中 调 试 切 片 时, 种 子 分 为 三 种, 分 别 是 源 种 子 (source seed), 条 件 种 子 (block seed) 和 终 结 种 子 (sink seed), 切 片 的 过 程, 是 要 从 源 种 子 到 终 结 种 子 的 路 径 上, 运 用 一 定 的 规 则 找 到 与 源 种 子 相 关 的 条 件 种 子 在 实 际 应 用 中, 一 般 源 种 子 为 malloc calloc 等 或 fopen freopen, 终 结 种 子 为 exit, 条 件 种 子 则 为 free xfree 或 fclose 在 malloc exit 路 径 上, 运 用 一 定 规 则 找 到 free, 得 到 与 之 相 关 的 切 片, 可 用 于 检 查 内 存 泄 露 问 题 ; 在 fopen exit 路 径 上 找 到 fclose, 得 到 与 之 相 关 的 切 片, 可 用 于 检 查 文 件 打 开 关 闭 的 问 题 对 于 这 三 类 种 子 的 定 义, 可 以 切 片 过 程 中 进 行 设 置 在 设 计 实 验 中, 我 用 的 选 项 是 opencc -O0 -keep -show -WOPT:dce=false -ipa -IPA:dfe=on:cprop=off:aggr_opt:scc_slicing:inline=off:dce=off:p dg_drawing -INLINE:none *.c -Wj,-tt22:0x100 可 以 清 楚 地 看 到,pdg_drawing 为 打 开 状 态, 在 此 状 态 下, 执 行 的 结 果 为 含 有 切 片 结 果 的 调 用 图 显 示 : 本 实 验 为 验 证 内 存 泄 露 的 例 子, 即 源 种 子 为 malloc calloc 或 realloc 上 图 中, 含 有 源 种 子 的 函 数 标 注 为 红 色, 同 时, 用 子 结 点 的 方 法 来 描 述 出 其 中 含 有 源 种 子 的 个 数, 并 显 示 whirl 行 号, 另 一 含 种 子 函 数 33
第 34 页 含 有 三 个 源 种 子 找 到 源 种 子 后, 运 行 程 序 前 向 切 片, 收 集 到 相 关 条 件 种 子 和 终 结 种 子, 再 运 行 程 序 后 向 切 片 收 集 到 相 关 函 数 切 片 结 果 为 进 行 相 关 交 互 功 能, 将 与 源 种 子 有 关 的 切 片 结 果 函 数 分 类 保 存 在 相 关 位 向 量 中, 以 便 后 文 进 行 切 片 结 果 的 显 示 功 能 选 取 其 中 之 一 种 子 后 显 示 函 数 切 片 结 果 : 34
第 35 页 5.2 函 数 PDG 的 实 例 实 现 5.2.1 不 包 含 切 片 结 果 的 PDG 显 示 如 上 文 所 述, 当 打 开 开 关 pdg_drawing 时, 在 未 进 行 切 片 或 函 数 不 包 含 在 切 片 结 果 中 时, 函 数 PDG 显 示 为 全 部 属 性 和 边 的 显 示, 此 内 容 把 函 数 PDG 的 所 有 信 息 都 显 示 出 来, 下 图 为 实 例 中 函 数 bea_compute_red_cost 的 PDG 显 示 的 一 部 分 : 35
第 36 页 图 中 用 不 同 颜 色 结 点 和 边 来 标 注 不 同 PDG 的 属 性, 在 其 中 可 进 行 查 找 功 能 及 显 示 隐 藏 属 性 的 功 能 : 如 查 找 其 中 WHIRL 结 点, 则 输 入 如 下 格 式 : 结 果 显 示 如 下 : 36
第 37 页 INFO 结 构 显 示 信 息 结 构 如 下 : 37
第 38 页 38
第 39 页 5.2.2 包 含 切 片 结 果 的 PDG 显 示 在 进 行 切 片, 或 函 数 包 含 在 切 片 结 果 中,PDG 显 示 则 只 显 示 是 否 在 切 片 中 两 种 情 况, 即 在 切 片 中 的 PDG 结 点 及 边 用 不 同 颜 色 显 示, 不 在 切 片 中 的 PDG 结 点 及 边 则 用 白 色 和 灰 色 显 示, 同 时 显 示 三 类 种 子 结 点 : 源 种 子 条 件 种 子 和 终 结 种 子, 将 这 三 类 种 子 结 点 以 双 线 框 框 起, 效 果 图 如 下 所 示 : 其 他 属 性 功 能 与 不 含 切 片 结 果 PDG 显 示 相 同 5.3 控 制 流 图 的 实 例 实 现 5.3.1 不 包 含 切 片 结 果 的 控 制 流 图 显 示 同 样, 当 打 开 开 关 cfg_drawing 时, 在 未 进 行 切 片 或 函 数 不 包 含 在 切 片 结 果 中 时, 函 数 控 制 流 图 显 示 为 函 数 基 本 块 及 基 控 制 关 系, 此 内 容 把 函 数 控 制 流 关 系 都 显 示 出 来, 下 图 为 实 例 中 函 数 getfree 的 控 制 流 图 显 示 : 39
第 40 页 5.3.2 包 含 切 片 结 果 的 控 制 流 图 显 示 在 进 行 切 片, 或 函 数 包 含 在 切 片 结 果 中, 控 制 流 图 显 示 则 只 显 示 是 否 在 切 片 中 两 种 情 况, 即 在 切 片 中 的 基 本 块 及 用 不 同 颜 色 显 示, 不 在 切 片 中 的 基 本 块 则 不 改 变 颜 色 显 示, 下 图 为 函 数 getfree, 效 果 图 如 下 所 示 : 40
第 41 页 41
第 42 页 第 六 章 成 本 资 源 分 析 本 文 完 成 的 工 作 是 中 国 科 学 院 计 算 技 术 研 究 所 计 算 机 系 统 结 构 重 点 实 验 室 正 在 进 行 的 工 作 的 一 部 分, 此 工 作 是 基 于 Open64 编 译 平 台 上 的 程 序 分 析 工 具 方 面 的 研 发, 其 中 包 括 程 序 切 片 技 术 工 具 的 开 发, 我 做 的 工 作 的 目 的 是 将 切 片 过 程 中 的 数 据 结 构 图 形 结 构 用 图 形 化 工 具 进 行 表 示 由 于 Open64 编 译 器 是 开 源 编 译 软 件, 不 涉 及 源 代 码 的 成 本 问 题, 而 且 在 编 译 器 的 分 析 开 发 过 程 中 用 到 的 工 具 和 算 法 都 是 现 在 学 术 界 普 遍 使 用 的, 没 有 专 利 费 用 等 问 题, 所 以 本 软 件 工 具 在 开 发 过 程 中 不 涉 及 成 本 问 题 而 整 个 实 验 室 对 编 译 分 析 的 贡 献 是 很 大 的, 程 序 切 片 工 具 的 应 用 前 景 不 可 估 量, 而 本 文 从 事 的 工 作 是 其 中 的 比 较 重 要 的 一 环, 这 在 整 个 团 队 中 也 起 到 了 不 可 替 代 的 作 用 未 来 随 着 切 片 工 具 的 广 泛 使 用, 本 图 形 化 工 具 也 将 随 之 得 到 应 用, 随 之 带 来 的 各 种 影 响 也 是 不 言 而 喻 的 本 工 具 完 成 并 应 用 之 后, 使 整 个 团 队 的 工 作 效 率 得 到 提 高 未 应 用 本 工 具 之 前, 在 切 片 过 程 分 析 时, 使 用 纯 文 本 手 工 对 函 数 调 用 图 和 PDG 进 行 绘 制, 分 析 每 个 程 序 用 的 时 间 开 销 很 大, 而 使 用 本 工 具 之 后, 由 于 自 动 生 成 图 形 化 界 面, 省 掉 了 手 工 绘 制 图 的 时 间, 为 程 序 切 片 分 析 做 出 了 贡 献 减 少 了 这 方 面 人 力 资 源, 提 高 了 整 个 团 队 的 工 作 效 率 42
第 43 页 第 七 章 结 论 本 文 主 要 实 现 了 程 序 切 片 工 具 的 图 形 化, 在 Open64 编 译 平 台 上, 实 现 了 程 序 切 片 工 具 与 图 形 化 工 具 的 接 口 本 工 具 从 切 片 工 具 调 试 人 员 的 需 求 出 发, 在 经 过 多 次 修 改 和 补 充 之 后, 经 过 多 次 测 试, 在 切 片 工 具 的 调 试 和 验 证 团 队 中 得 到 广 泛 的 应 用, 为 简 化 其 工 作 做 出 了 贡 献 切 片 工 具 图 形 化 部 分 相 信 能 够 对 编 译 器 的 研 究 做 出 贡 献, 一 个 优 先 的 可 视 化 编 译 器 需 要 几 个 关 键 的 组 件 互 相 之 间 很 好 的 整 合 起 来 形 成 一 个 结 构 这 些 组 件 包 括 : 一 个 易 扩 展 的 编 译 器, 一 个 简 单 又 功 能 足 够 的 中 间 语 言 格 式, 一 个 图 形 用 户 界 面 工 具 包 Open64 就 是 致 力 于 推 动 研 究 的 公 开 源 代 码 的 编 译 器, 采 用 SGI 公 司 精 心 设 计 的 WHIRL 作 为 中 间 语 言 格 式, 可 以 支 持 C C++ FORTRAN90 和 FORTRAN95 等 多 种 语 言 的 编 译 器 前 端 UdrawGraph 又 是 在 学 术 研 究 界 广 泛 使 用 的 图 形 化 工 具 所 以 说 切 片 工 具 图 形 化 部 分 能 够 比 较 好 的 满 足 这 三 个 要 求 现 在 本 文 实 现 的 接 口 和 功 能 已 在 程 序 切 片 过 程 中 得 到 应 用, 解 决 了 许 多 难 题, 大 大 提 高 了 调 试 人 员 的 工 作 效 率 43
第 44 页 参 考 文 献 外 文 文 献 1.Aho, A.V. and Ullman, J.D.,Principles of Compiler design. Addison-Wesley,1977. 2.Gao, G.R., Dehnert, J. and Amaral J.N.,The SGI Pro64 Compiler Infrastructure. 3.Hennessy. J.L. and Patterson, D.,Computer Architecture:A Quantitative Approach, Fourth Edition. Morgan Kaufmann,2006. 4.Henning, J.L., SPEC CPU Suite Growth: An Historical Perspective. 5.Horwitz, S., Reps, T. and Binkley, D., Interprocedural Slicing Using Dependence Graphs. Proceedings of the SIGPLAN 88 Conference on Programming Language Design and Implementation, June 22-24,1988. 6.Muchnick, S.S., Advanced Compiler Design and Implementation. Elsesiver Science,2005. 7.Ottenstein, K.J. and Ottenstein, L.M., the Program Dependence Graph in a Software Development Environment. Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments. (Pittsburgh, PA, Apr. 23-25,1984), ACM SIGPLAN Notices 19(5) pp.177-184(may 1984). 8.Weiser, M., Program Slicing. Proceedings of the 5th international conference on Software engineering,1981:439-449. 中 文 文 献 9. 杜 林. 面 向 对 象 程 序 切 片 技 术 研 究. 山 东 省 教 育 学 院 学 报,2007,6. 10. 李 必 信, 郑 国 梁. 一 种 分 析 和 理 解 程 序 的 方 法 程 序 切 片. 计 算 机 研 究 与 发 展,2000,37(3). 11. 谭 浩 强.C 程 序 设 计 ( 第 三 版 ). 清 华 大 学 出 版 社,2005. 12. 王 伟, 陈 平. 程 序 切 片 技 术 综 述. 学 术 论 坛. 13. 王 燕. 面 向 对 象 的 理 论 与 C++ 实 践. 清 华 大 学 出 版,1997. 14. 张 昊 中.Pathscale 中 编 译 信 息 图 形 化 的 改 进 实 现.2007. 44
第 45 页 15. 张 勇 翔, 李 必 信, 郑 国 梁. 程 序 切 片 技 术 的 研 究 与 应 用. 计 算 机 科 学,2000,27(1). 16. 周 述 康. 面 向 IA-64 体 系 结 构 的 编 译 器 AURORA 的 图 形 可 视 化. 北 京 大 学 学 士 学 位 论 文. 参 考 网 址 17. http://en.wikipedia.org/wiki/benchmark_(computing) 18. http://en.wikipedia.org/wiki/call_graph 19. http://www.informatik.uni-bremen.de/udrawgraph/en/index. html 20. http://www.open64.net 21. http://www.spec.org 22. http://en.wikipedia.org/wiki/control_flow_graph 45
第 46 页 附 录 Benchmark.f.f90.c.h.C 164.gzip 8 1 175.vpr 17 1 176.gcc 210 18 181.mcf 2 1 186.crafty 19 2 CPU2000 197.parser 11 0.5 Integer 252.eon 18 23 253.perlbmk 62 24 254.gap 59 12 255.vortex 53 15 256.bzip2 5 0.01 300.twolf 20 1 CPU2000 FP 168.wupwise 2 171.swim 0.4 172.mgrid 0.5 173.applu 4 177.mesa 50 11 178.galgel 15 179.art 16 183.equake 2 187.facerec 2 188.ammp 13 0.2 189.lucas 3 191.fma3d 60 200.sixtrack 48 301.apsi 7 表 格 附 1 SPEC CPU2000 代 码 行 数 ( 单 位 1000) Benchmark.f.f90.c.h.C CPU2000 164.gzip 14 6 46
第 47 页 Integer 175.vpr 20 21 176.gcc 66 61 181.mcf 11 14 186.crafty 39 4 197.parser 17 1 252.eon 172 151 253.perlbmk 38 58 254.gap 32 31 255.vortex 66 57 256.bzip2 2 1 300.twolf 75 10 CPU2000 FP 168.wupwise 22 171.swim 1 172.mgrid 1 173.applu 1 177.mesa 58 65 178.galgel 38 179.art 9 183.equake 1 187.facerec 11 188.ammp 28 3 189.lucas 1 191.fma3d 101 200.sixtrack 124 301.apsi 1 表 格 附 2 SPEC CPU2000 原 代 码 文 件 数 47