<4D F736F F D20B1CFD2B5C9E8BCC65FCDF5D1A95F F>

Transcription

1 毕 业 设 计 ( 论 文 ) 中 文 题 目 : 图 形 化 程 序 切 片 工 具 的 设 计 英 文 题 目 : The Design of Program Slicing Visualization 学 专 院 : 计 算 机 与 信 息 技 术 业 : 计 算 机 科 学 与 技 术 学 生 姓 名 : 王 雪 学 号 : 指 导 教 师 : 于 双 元 冯 晓 兵 2009 年 6 月 日

2 中 文 摘 要 程 序 切 片 是 一 种 抽 象 出 与 给 定 计 算 变 量 有 关 的 语 句 的 分 析 技 术 而 非 形 式 的 讲, 程 序 切 片 是 指 从 程 序 行 为 的 一 个 子 集 开 始, 将 其 缩 小 到 最 小 的 形 式, 使 这 种 形 式 仍 能 表 达 原 程 序 中 所 给 定 子 集 的 行 为 这 种 被 缩 小 的 程 序, 就 叫 切 片 [8] 程 序 切 片 在 程 序 调 试 软 件 维 护 和 程 序 理 解 方 面 起 着 重 要 作 用 现 在 一 种 广 泛 使 用 的 程 序 切 片 算 法 是 由 Horwitz 等 在 文 献 [5] 中 提 到 的 这 种 方 法 基 于 依 赖 图, 使 用 图 可 达 性 算 法 来 自 动 地 计 算 程 序 切 片, 能 够 获 得 更 好 的 切 片 精 度 通 过 图 形 化 的 方 式 给 出 切 片 的 过 程 和 切 片 的 结 果 能 够 提 高 程 序 切 片 工 具 的 实 用 性 但 是, 由 于 依 赖 图 的 规 模 非 常 的 巨 大, 切 片 的 结 果 很 难 在 依 赖 图 上 直 观 的 反 映, 同 时 也 给 切 片 工 具 的 调 试 带 来 了 相 当 的 困 难 本 文 正 是 针 对 这 一 问 题 进 行 讨 论 本 文 首 先 介 绍 了 程 序 切 片 的 相 关 概 念, 阐 述 基 于 依 赖 图 的 切 片 算 法 通 过 实 验 数 据 说 明 规 模 巨 大 的 依 赖 图, 给 图 形 化 程 序 切 片 工 具 带 来 的 挑 战, 同 时 用 户 对 程 序 源 码 分 析 的 需 求, 使 得 本 工 具 需 要 实 现 对 源 码 的 显 示 功 能, 然 后 介 绍 切 片 工 具 的 图 形 化 设 计 过 程, 使 用 层 次 化 结 构 的 设 计 方 式, 给 出 两 种 模 式 的 切 片 图 形 化 结 果 为 了 满 足 普 通 用 户 需 求, 在 控 制 流 图 上 给 出 切 片 的 结 果 ; 对 于 切 片 调 试 开 发 人 员, 对 切 片 过 程 产 生 的 大 规 模 依 赖 图 及 大 量 信 息 表 示 的 图 形 化 给 出 相 应 的 解 决 办 法 本 文 所 论 述 的 程 序 切 片 图 形 化 过 程 已 利 用 画 图 工 具 UdrawGraph 在 Open64 编 译 平 台 上 实 现 该 工 具 对 中 国 科 学 院 计 算 技 术 研 究 所 计 算 机 系 统 结 构 重 点 实 验 室 基 于 Open64 编 译 平 台 上 实 现 的 程 序 分 析 工 具 进 行 图 形 化, 已 达 到 令 人 比 较 满 意 的 效 果 在 本 文 的 最 后, 给 出 该 工 具 应 用 的 示 例 图, 展 示 图 形 化 的 效 果 删 除 的 内 容 : 和 控 制 流 图 删 除 的 内 容 : 或 控 制 流 图 删 除 的 内 容 : 不 得 删 除 的 内 容 : 控 制 流 图 关 键 词 : 程 序 切 片 ; 依 赖 图 ;UdrawGraph; 层 次 化 设 计 ; 交 互 I

3 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

4 目 录 中 文 摘 要... I Abstract... II 目 录... III 第 一 章 绪 论 程 序 切 片 工 具 图 形 化 介 绍 本 文 工 作 论 文 组 织 结 构... 2 第 二 章 程 序 切 片 程 序 切 片 概 念 程 序 切 片 准 则 (slicing criterion) 程 序 切 片 技 术 分 类 静 态 切 片 技 术 (static slicing) 动 态 切 片 技 术 (dynamic slicing) 条 件 切 片 技 术 (conditioned slicing) 程 序 切 片 算 法 及 相 关 概 念 程 序 依 赖 图 (Program Dependence Graph,PDG) 系 统 依 赖 图 (System Dependence Graph,SDG) 调 用 图 (call graph) 程 序 切 片 算 法 控 制 流 图 (Control Flow Graph) 第 三 章 程 序 切 片 工 具 图 形 化 切 片 工 具 图 形 化 意 义 开 发 平 台 图 形 化 工 具 简 介 图 形 化 工 具 选 择 Udraw(Graph) 简 介 Udraw 接 口 第 四 章 切 片 工 具 图 形 化 设 计 Udraw 语 法 表 示 切 片 工 具 图 形 化 层 次 化 设 计 层 次 化 设 计 原 因 层 次 化 设 计 设 计 过 程 及 交 互 实 现 III

5 4.3.1 调 用 图 的 功 能 实 现 函 数 PDG 的 功 能 实 现 控 制 流 图 的 功 能 实 现 交 互 功 能 实 现 本 文 程 序 整 体 流 程 第 五 章 图 形 化 设 计 实 例 调 用 图 的 实 例 实 现 函 数 PDG 的 实 例 实 现 不 包 含 切 片 结 果 的 PDG 显 示 包 含 切 片 结 果 的 PDG 显 示 控 制 流 图 的 实 例 实 现 不 包 含 切 片 结 果 的 控 制 流 图 显 示 包 含 切 片 结 果 的 控 制 流 图 显 示 第 六 章 成 本 资 源 分 析 第 七 章 结 论 参 考 文 献 外 文 文 献 中 文 文 献 参 考 网 址 附 录 IV

6 第 1 页 第 一 章 绪 论 1.1 程 序 切 片 工 具 图 形 化 介 绍 程 序 切 片 技 术 是 根 据 控 制 流 分 析 和 数 据 流 分 析 而 引 入 的 一 种 系 统 理 解 方 法, 可 以 针 对 一 个 切 片 标 准, 提 取 出 程 序 中 影 响 关 注 点 变 量 值 的 所 有 语 句, 通 过 计 算 源 程 序 中 每 个 关 注 点 的 切 片 来 达 到 对 整 个 程 序 的 分 析 和 理 解 程 序 切 片 技 术 发 展 到 现 在 已 有 很 重 要 的 现 实 意 义, 目 前 主 要 应 用 于 程 序 调 试 程 序 测 试 软 件 维 护 及 逆 向 工 程 等 方 面 图 形 化 技 术 是 当 前 计 算 机 发 展 的 热 点 之 一 计 算 机 应 用 一 个 重 要 的 研 究 方 向 是 把 信 息 用 可 感 知 的 方 法 表 现 出 来 图 形 化 适 用 于 表 示 拥 有 内 在 固 有 关 系 的 数 据 : 数 据 可 以 被 表 示 为 一 个 图 的 结 点, 和 边 表 示 关 系 这 样 的 结 点 边 关 系 图 在 计 算 机 科 学 和 很 多 其 他 领 域 都 有 广 泛 运 用 它 是 一 种 简 单 有 力 优 质 的 抽 象 任 何 可 以 用 有 关 系 的 点 来 模 拟 的 对 象 都 可 以 利 用 图 形 化 技 术 来 表 示 同 很 多 工 具 软 件 一 样, 切 片 工 具 在 开 发 过 程 中, 很 多 工 作 是 测 试 和 调 试 由 于 切 片 过 程 基 于 依 赖 图, 在 遍 历 依 赖 图 的 过 程 中, 由 于 没 有 图 形 可 视 化 的 支 持, 依 赖 图 或 切 片 结 果 中 的 信 息 会 变 得 不 直 观 晦 涩 增 加 了 其 中 的 数 据 结 构 的 理 解 难 度 在 切 片 过 程 中, 一 般 方 法 是 给 出 所 有 结 点 的 编 号, 以 及 各 边 的 源 结 点 和 目 的 结 点 的 编 号, 而 且 很 多 时 候, 只 有 点 和 边 是 不 够 的, 还 需 要 点 和 边 代 表 的 那 些 数 据 项 的 其 他 信 息 所 以 切 片 工 具 的 图 形 化 已 势 在 必 行 1.2 本 文 工 作 切 片 工 具 在 开 发 过 程 中, 由 于 是 基 于 依 赖 图, 在 遍 历 依 赖 图 的 过 程 中, 由 于 没 有 图 形 化 的 支 持, 依 赖 图 或 切 片 结 果 中 的 信 息 会 变 得 不 直 观 晦 涩 增 加 了 程 序 员 对 数 据 结 构 的 理 解 难 度 而 且 切 片 结 果 的 验 证 往 往 运 用 较 大 的 标 准 测 试 集 来 进 行, 更 加 大 了 其 调 试 难 度 从 面 向 用 户 角 度 来 说, 用 户 关 心 的 只 是 程 序 的 源 代 码 和 相 应 的 切 片 结 果, 所 以, 针 对 用 户 这 个 需 求, 设 计 出 相 应 的 图 形 化 结 果, 也 是 非 常 必 要 的 本 文 完 成 的 就 是 程 序 切 片 工 具 的 图 形 化 工 作 本 工 作 是 中 国 科 学 院 计 算 技 术 研 究 所 计 算 机 系 统 结 构 重 点 实 验 室 正 在 进 行 的 工 作 的 一 部 分, 是 基 1

7 第 2 页 于 Open64 编 译 平 台 上 的 程 序 分 析 工 具 方 面 的 研 发, 其 中 包 括 程 序 切 片 技 术 工 具 的 开 发 目 的 是 将 切 片 过 程 中 的 数 据 结 构 图 形 结 构 用 图 形 化 工 具 进 行 表 示, 简 化 其 理 解 难 度, 同 时 实 现 面 向 用 户 的 源 码 结 构 显 示 本 文 工 作 是 在 Open64 编 译 平 台 上 进 行, 对 其 中 程 序 切 片 工 具 研 发 部 分 进 行 图 形 化 工 作 在 调 研 多 种 图 形 化 工 具 软 件 后, 决 定 选 用 UdrawGraph 作 为 本 文 基 本 图 形 化 工 具,UdrawGraph 的 图 形 用 户 界 面 有 助 于 对 切 片 过 程 的 理 解 UdrawGraph 不 但 具 有 强 大 的 图 形 化 功 能, 还 已 实 现 了 与 Open64 编 译 器 之 间 的 接 口 1.3 论 文 组 织 结 构 本 文 第 二 章 重 点 介 绍 程 序 切 片 相 关 概 念, 程 序 切 片 准 则 和 Horwitz 等 在 文 献 [5] 中 提 到 的 程 序 切 片 的 算 法 由 于 该 算 法 基 于 依 赖 图, 所 以 同 时 介 绍 相 关 调 用 图 程 序 依 赖 图 系 统 依 赖 图 等 方 面 的 内 容 第 三 章 则 对 本 文 使 用 的 图 形 化 工 具 UdrawGraph 进 行 详 细 介 绍, 从 其 功 能 和 用 途 上 指 出 选 择 UdrawGraph 的 优 势 所 在, 以 及 在 Open64 编 译 平 台 上 已 封 装 接 口 的 可 用 性 第 四 章 介 绍 切 片 工 具 图 形 化 设 计 的 具 体 实 现, 本 文 采 用 层 次 化 设 计, 从 整 体 到 部 分 一 层 一 层 进 行, 并 使 用 交 互 功 能 实 现 层 次 之 间 的 相 互 联 系 第 五 章, 介 绍 SPEC CPU2000 中 181.mcf 实 现 的 一 个 实 例, 并 从 实 例 基 础 上 进 一 步 分 析 图 形 化 工 具 第 六 章 进 行 本 工 具 的 成 本 资 源 分 析 最 后, 总 结 全 文, 指 出 此 图 形 化 工 具 的 优 势 2

8 第 3 页 第 二 章 程 序 切 片 程 序 切 片 的 起 源 是, 鉴 于 很 多 时 候, 程 序 员 只 需 关 心 程 序 行 为 的 一 部 分 比 如, 调 试 时 只 关 心 程 序 出 错 的 一 部 分 子 集, 程 序 修 改 和 维 护 时 只 对 一 部 分 程 序 进 行 升 级 在 这 些 情 况 下, 程 序 员 从 程 序 行 为 开 始, 寻 找 和 修 改 程 序 代 码 的 相 应 部 分, 与 之 不 相 关 的 部 分 被 忽 略 掉 程 序 员 维 护 一 个 很 大 又 不 熟 悉 的 程 序, 又 不 得 不 利 用 其 中 某 些 部 分, 充 分 理 解 整 个 程 序 而 仅 仅 对 其 中 一 小 部 分 进 行 修 改 和 维 护, 这 会 花 费 很 多 没 用 的 时 间 而 大 部 分 程 序 维 护 不 是 由 程 序 设 计 者 进 行 的 而 是 由 其 他 人 进 行, 而 且 67% 的 努 力 都 要 花 费 到 程 序 维 护 上 [16], 从 行 为 上 分 解 程 序 就 势 在 必 行 程 序 切 片 就 应 运 而 生 了 2.1 程 序 切 片 概 念 [8] 程 序 切 片 的 概 念 最 早 由 Mark Weiser 在 1979 博 士 论 文 中 提 出, 他 的 定 义 是 : 程 序 切 片 是 有 经 验 的 程 序 员 用 来 从 程 序 中 抽 象 出 与 给 定 计 算 变 量 有 关 的 语 句 的 分 析 技 术, 它 是 从 程 序 行 为 的 一 个 子 集 开 始, 将 其 缩 小 到 最 小 的 形 式, 使 这 种 形 式 仍 能 表 达 程 序 的 这 种 行 为 这 种 被 缩 小 的 程 序, 就 叫 切 片, 它 是 独 立 的 程 序, 能 够 在 原 程 序 行 为 子 集 范 围 内 准 确 表 达 出 原 程 序 Weiser 定 义 的 切 片 是 一 个 可 执 行 的 程 序, 是 通 过 从 源 程 序 中 移 去 零 条 或 多 条 语 句 来 构 造 的, 最 终 能 够 严 格 地 表 达 出 原 程 序 的 行 为 [5] 后 来,Horwitz 等 人 给 出 的 切 片 定 义 是 : 一 个 程 序 切 片 是 由 程 序 中 的 一 些 语 句 和 判 定 表 达 式 组 成 的 集 合 这 些 语 句 和 判 定 表 达 式 可 能 会 影 响 在 程 序 的 某 个 位 置 ( 常 用 行 号 标 识 )p 上 所 定 义 的 或 所 使 用 的 变 量 v 的 值 (p,v) 称 为 切 片 准 则 (slicing criterion) 2.2 程 序 切 片 准 则 (slicing criterion) 程 序 切 片 需 要 将 程 序 行 为 指 定 为 某 一 特 定 形 式, 如 果 程 序 中 感 兴 趣 的 行 为 可 以 用 变 量 集 在 语 句 集 中 的 值 来 表 示, 那 么 这 种 规 范 就 定 义 为 程 序 准 则 数 据 流 分 析 能 够 找 到 所 有 能 够 影 响 这 种 指 定 行 为 的 程 序 段, 这 些 程 序 段 就 叫 做 程 序 的 切 片 程 序 切 片 准 则 是 程 序 切 片 技 术 的 重 要 方 面, 切 片 准 则 在 程 序 计 算 切 片 时, 起 到 至 关 重 要 的 作 用 程 序 的 切 片 准 则 为 观 察 程 序 行 为 指 定 了 窗 口, 它 是 由 一 个 语 句 和 一 些 3

9 第 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] 静 态 切 片 技 术 (static slicing) 静 态 切 片 技 术 是 指 在 计 算 机 程 序 切 片 时 使 用 的 是 编 译 时 分 析, 不 需 要 真 正 的 程 序 执 行 该 技 术 对 程 序 的 输 入 不 做 任 何 假 设, 所 做 的 分 析 完 全 以 程 序 的 静 态 信 息 为 依 据 使 用 该 技 术 的 时 空 开 销 较 大, 因 为 要 分 析 程 序 所 有 可 能 的 执 行 轨 迹, 所 以 相 对 于 动 态 切 片 技 术, 静 态 切 片 技 术 一 般 用 于 程 4

10 第 5 页 序 理 解 与 软 件 维 护 方 面 Weiser 最 初 提 出 的 程 序 切 片 概 念 就 是 属 于 静 态 切 片 范 畴 动 态 切 片 技 术 (dynamic slicing) 动 态 切 片 技 术 使 用 的 是 运 行 时 分 析, 在 程 序 运 行 时 应 用, 因 此 切 片 的 计 算 过 程 依 赖 于 程 序 的 具 体 输 入 采 用 这 一 技 术, 每 一 次 的 计 算 开 销 小, 但 每 一 次 的 计 算 都 不 尽 相 同, 因 此 动 态 切 片 技 术 多 用 于 程 序 调 试 测 试 方 面 条 件 切 片 技 术 (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

11 第 6 页 在 p 点 值 的 语 句 和 谓 词 构 成 1990 年,Horwitz 等 在 文 献 中 [5] 使 用 依 赖 图 来 计 算 切 片, 他 们 开 发 了 一 种 过 程 间 的 程 序 表 示 系 统 依 赖 图, 并 实 现 了 一 个 基 于 系 统 依 赖 图 的 两 阶 段 图 可 达 性 切 片 算 法, 由 于 在 调 用 点 传 递 的 依 赖 流 信 息 中 包 含 被 调 用 过 程 的 上 下 文 环 境, 所 以 该 算 法 的 计 算 精 度 比 以 前 的 算 法 更 高 目 前, 我 们 主 要 用 的 是 这 种 基 于 依 赖 图 的 方 法 程 序 依 赖 图 (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

12 第 7 页 ENTRY Sum:=0 i:=1 While i<1 FinalUse(i) FinalUse(sum) Sum:=sum+1 i:=i 系 统 依 赖 图 (System Dependence Graph,SDG) 系 统 依 赖 图 概 念 系 统 依 赖 图 [5] 是 程 序 依 赖 图 的 拓 展, 表 示 包 括 函 数 间 相 互 调 用 的 语 句 系 统 依 赖 图 有 如 下 性 质 : 1 一 个 完 整 的 系 统 包 括 主 函 数 和 一 系 列 的 其 他 函 数 2 程 序 用 return 结 尾 3 参 数 用 变 量 结 果 在 各 函 数 中 传 递 7

13 第 8 页 函 数 调 用 和 参 数 传 递 [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 边 是 数 据 依 赖 边 在 程 序 切 片 时, 各 结 点 的 属 性 及 结 点 之 间 的 依 赖 关 系, 对 切 片 的 分 析 具 有 至 关 重 要 的 作 用 调 用 图 (call graph) 调 用 图 [18] 是 代 表 程 序 间 调 用 关 系 的 有 向 图 每 个 结 点 代 表 一 个 函 数, 每 条 边 (f,g) 代 表 函 数 f 调 用 函 数 g 图 中 环 代 表 程 序 中 的 递 归 函 数 调 用 图 是 一 个 基 本 程 序 分 析 结 果, 可 用 于 人 们 理 解 程 序 或 用 于 更 进 一 步 分 析 程 序, 例 如 对 某 一 变 量 进 行 流 分 析, 最 简 单 的 应 用 是 找 到 没 有 被 调 用 的 程 序 调 用 图 可 被 定 义 来 表 示 准 确 度 的 改 变, 调 用 图 越 准 确, 真 实 程 序 就 越 准 确, 但 要 在 增 大 时 间 和 内 存 开 销 的 代 价 下, 最 准 确 的 调 用 图 是 完 全 上 下 文 敏 感 (context-sensitive) 的, 这 意 识 着 对 于 每 一 个 函 数, 图 中 包 含 每 一 个 可 活 动 的 调 用 栈 的 独 立 结 点 一 个 完 全 上 下 文 敏 感 的 调 用 图 可 很 容 易 地 进 行 动 态 计 算, 尽 管 要 花 费 大 量 的 内 存, 同 时, 它 通 常 不 能 进 行 静 态 计 算, 因 为 对 一 个 大 程 序 来 说 花 费 时 间 会 很 长 最 不 准 确 的 调 用 图 是 上 下 文 不 敏 感 的 (context-insensitive), 这 意 识 着 每 个 函 数 只 有 一 个 结 点 调 用 图 分 为 动 态 调 用 图 和 静 态 调 用 图 动 态 调 用 图 记 录 程 序 执 行 的 过 程, 例 如, 作 为 描 述 文 件 (profiler) 的 输 出 所 以 动 态 调 用 图 可 以 准 确 8

14 第 9 页 描 述 但 只 能 描 述 程 序 的 一 个 运 行 分 支 静 态 调 用 图 用 于 描 述 程 序 中 所 有 运 行 分 支 在 切 片 过 程 中, 采 用 的 是 静 态 调 用 图, 来 表 示 各 函 数 之 间 的 调 用 关 系 及 其 中 某 些 特 定 变 量 的 数 据 流 向 程 序 切 片 算 法 目 前 我 们 用 的 程 序 切 片 算 法 主 要 是 在 Horwitz 提 出 的 基 于 依 赖 图 的 算 法 的 基 础 上 进 行 改 进 实 现 的 摘 要 信 息 (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

15 第 10 页 程 序 切 片 算 法 Horwitz 等 提 出 的 算 法 的 关 键 方 面 是 利 用 系 统 依 赖 图 中 联 系 语 法 (linkage grammar) 特 有 的 边, 这 些 边 代 表 从 过 程 调 用 产 生 的 actual_in 顶 点 到 actual_out 顶 点 的 传 递 数 据 依 赖, 这 种 边 避 免 了 调 用 上 下 文 (calling context) 问 题, 切 片 选 项 也 可 以 允 许 跨 越 调 用 函 数 进 行, 而 不 用 进 入 调 用 函 数 中 才 能 进 行 程 序 间 切 片 算 法 在 下 面 给 出 如 下 所 述, 关 于 结 点 集 合 S 的 系 统 调 用 图 G 的 计 算 过 来 分 为 两 阶 段 进 行 这 两 个 阶 段 都 要 遍 历 系 统 依 赖 图, 沿 着 某 类 边 来 找 到 能 够 到 达 给 定 结 点 集 的 结 点 的 集 合 阶 段 1 的 遍 历 沿 着 流 边, 控 制 边, 调 用 边 和 parameter_in 边, 但 不 沿 parameter_out 边, 阶 段 2 的 遍 历 沿 着 流 边, 控 制 流 和 parameter_out 边, 但 不 沿 着 调 用 边 和 parameter_in 边 10

16 第 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

17 第 12 页 阶 段 1 阶 段 1 确 定 能 够 到 达 s 的 结 点, 这 些 结 点 存 在 于 函 数 P 或 调 用 P 的 函 数 中 被 P 调 用 的 函 数 的 产 生 的 影 响 没 有 被 完 全 忽 略, 从 actual_in 到 actual_out 结 点 ( 次 要 特 征 图 边 ) 的 流 依 赖 边 的 存 在 使 得 仅 通 过 一 个 函 数 调 用 就 可 找 到 到 达 s 的 结 点, 尽 管 图 遍 历 不 是 真 正 意 义 上 进 入 到 被 调 用 函 数 中 阶 段 2 阶 段 2 确 定 能 够 到 达 s 的 结 点, 这 些 结 点 存 在 于 被 P 调 用 的 函 数 或 被 调 用 函 数 P 的 函 数 调 用 的 函 数 中 由 于 以 上 算 法 是 在 遍 历 SDG 的 基 础 上 进 行 的, 而 我 们 现 在 用 的 是 基 于 PDG 的 算 法, 所 以 在 本 算 法 基 础 上, 进 行 了 改 进, 在 计 算 出 完 整 的 摘 要 信 息 的 前 提 下, 同 样 利 用 本 算 法 进 行 两 遍 式 遍 历 PDG, 得 到 完 整 的 过 程 间 切 片 控 制 流 图 (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

18 第 13 页 当 将 中 间 代 码 程 序 划 分 为 基 本 块 之 后, 用 一 个 流 图 来 表 示 它 们 之 间 的 控 制 流 流 图 的 结 点 就 是 这 些 基 本 块 从 基 本 块 B 到 基 本 块 C 之 间 有 一 条 边 当 且 仅 当 基 本 块 C 的 第 一 个 指 令 可 能 紧 跟 在 B 的 最 后 一 个 指 令 之 后 执 行 存 在 这 样 一 条 边 的 原 因 有 两 种 : 1) 有 一 个 从 B 的 结 尾 跳 转 到 C 的 开 头 的 条 件 或 无 条 件 跳 转 语 句 2) 按 照 原 来 的 语 句 序 列 中 的 顺 序,C 紧 跟 在 B 之 后, 且 B 的 结 尾 不 存 在 无 条 件 跳 转 语 句 我 们 说 B 是 C 的 前 驱, 而 C 是 B 的 一 个 后 继 我 们 通 常 会 增 加 两 个 分 别 称 为 入 口 和 出 口 的 结 点 它 们 不 和 任 何 可 执 行 的 中 间 指 令 对 应 从 入 口 到 流 图 的 第 一 个 可 执 行 结 点 有 一 条 边 从 任 何 包 含 了 可 能 是 程 序 的 最 后 执 行 指 令 的 基 本 块 到 出 口 有 一 条 边 通 过 控 制 流 图 的 基 本 块, 可 提 取 出 程 序 的 源 代 码, 就 可 以 满 足 用 户 的 需 求 它 是 基 于 程 序 源 码 基 础 进 行 的, 在 此 基 础 上 进 行 切 片 前 后 的 结 果 显 示 是 完 全 可 靠 的 13

19 第 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 bzip gzip gap parser vpr twolf crafty perlbmk vortex gcc art equake

20 第 15 页 ammp mesa 表 格 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

21 第 16 页 图 形 用 户 界 面 (GUI) 技 术 的 发 展, 直 接 促 进 了 图 形 可 视 化 工 具 的 进 步 现 在 能 够 利 用 这 些 工 具 比 较 容 易 的 创 建 一 个 图 形 化 的 用 户 界 面, 可 以 为 一 个 原 先 由 文 本 表 示 的 程 序 加 上 一 个 图 形 的 界 面 来 加 强 用 户 交 互, 把 复 杂 的 信 息 由 一 种 比 较 容 易 理 解 的 方 式 表 示 出 来 切 片 过 程 就 是 一 个 能 从 图 形 用 户 界 面 中 获 益 的 以 文 本 为 基 础 的 信 息 的 过 程, 它 的 图 形 用 户 界 面 有 助 于 对 切 片 过 程 的 理 解 3.4 图 形 化 工 具 选 择 在 图 形 化 过 程 中, 不 可 能 只 单 一 地 显 示 某 一 图 形 文 件, 而 必 须 与 之 进 行 交 互, 这 个 信 息 处 理 的 过 程 是 比 较 复 杂 的, 不 能 够 由 图 形 化 工 具 本 身 完 成, 而 需 由 别 的 程 序 或 进 程 来 完 成, 甚 至 还 要 查 询 相 关 数 据 结 构, 所 以 API 是 必 不 可 少 的 通 过 一 定 范 围 内 的 调 查 [16], 我 了 解 到 Udraw 和 VCG 是 当 前 在 国 际 编 译 研 究 界 比 较 流 行 的 图 形 可 视 化 工 具 Udraw 具 备 API 而 VCG 不 具 备 在 Open64 中, 与 Udraw 的 接 口 已 经 封 装 在 类 davinci 中, 管 道 建 立 和 维 护 的 工 作 已 经 由 该 类 隐 藏 Udraw(Graph) 简 介 Udraw(Graph) 是 德 国 不 来 梅 大 学 (Universität Bremen) 计 算 机 科 学 系 推 出 的 一 个 通 用 的 有 向 图 输 出 工 具 目 标 是 让 所 有 的 应 用 程 序 都 能 在 比 较 短 的 时 间 内 利 用 Udraw 提 供 一 个 图 形 用 户 界 面 这 样 应 用 程 序 的 程 序 员 就 不 必 关 心 图 的 布 局 算 法 和 计 算 机 图 形 学 的 问 题 了, 而 这 些 问 题 常 常 是 图 形 用 户 界 面 设 计 的 难 点 Udraw 通 过 一 种 叫 语 法 表 示 (term presentation) 得 到 待 表 示 的 图 的 信 息, 主 要 是 结 点 和 边 的 集 合 语 法 表 示 是 一 种 纯 文 本 的 ASCII 码 格 式 Udraw 可 以 通 过 语 法 表 示 出 结 点 和 边 的 各 种 属 性, 包 括 颜 色 形 状 文 本 表 示 等, 同 时 还 可 对 相 关 结 点 和 边 进 行 操 作, 如 隐 藏 显 示 结 点 或 边, 标 注 相 关 属 性 等 Udraw 接 口 Udraw 可 以 通 过.daVinci 或.udg 为 后 缀 的 文 件, 也 可 以 通 过 API 从 其 他 应 用 程 序 来 得 到 语 法 表 示 Udraw 同 应 用 程 序 之 间 的 交 互 如 下 图 : 16

22 第 17 页 应 用 程 序 通 过 建 立 与 Udraw 之 间 的 两 条 管 道 进 行 通 讯 : 一 条 管 道 从 应 用 程 序 到 Udraw, 用 于 应 用 程 序 向 Udraw 发 送 命 令 ; 另 一 条 管 道 从 Udraw 到 应 用 程 序, 用 于 Udraw 向 应 用 程 序 发 送 信 息 ( 包 括 鼠 标 和 键 盘 操 作 的 信 息 ) 17

23 第 18 页 第 四 章 切 片 工 具 图 形 化 设 计 4.1 Udraw 语 法 表 示 [19] Udraw 采 用 的 语 法 表 示 是 一 种 纯 文 本 的 ASCII 码 格 式, 能 够 对 图 中 结 点 和 边 的 各 种 属 性 进 行 表 示, 并 具 有 很 强 的 交 互 功 能 Udraw 的 语 法 中, 子 语 法 结 构 被 封 装 在 父 语 法 结 构 中, 例 如, parent[child1,child2,child3], 括 号 [ ] 用 于 包 括 一 系 列 逗 号 分 隔 的 子 语 法 这 种 父 子 语 法 结 构 可 用 于 递 归 循 环, 每 个 子 结 构 也 可 以 同 样 有 自 己 的 子 结 构, 如 此 循 环 这 种 符 号 表 示 支 持 了 树 型 结 构 的 递 归 循 环 这 种 语 法 表 示 很 容 易 理 解, 下 面 为 一 简 单 的 Udraw 图 形, 以 此 来 说 明 Udraw 的 语 法 结 构 相 应 Udraw 语 法 格 式 如 下 : 18

24 第 19 页 4.2 切 片 工 具 图 形 化 层 次 化 设 计 层 次 化 设 计 原 因 在 程 序 切 片 过 程 中, 由 于 引 入 过 程 间 切 片, 单 一 函 数 的 PDG 已 无 法 满 足 要 求, 上 文 中 已 经 列 出 PDG 的 规 模, 可 想 而 知,PDG 信 息 量 之 大, 这 样 以 来, 切 片 过 程 中 对 PDG 的 表 示 就 显 得 力 不 从 心, 结 果 图 太 大 会 造 成 显 示 时 间 过 长, 而 且 结 果 图 包 含 大 量 的 结 点 和 边, 这 些 边 几 乎 占 满 整 个 屏 幕, 而 且 彼 此 交 错, 根 本 无 法 辨 认 结 点 和 边 的 关 系, 更 不 用 说 对 其 进 行 相 关 操 作 在 开 始 试 验 时, 把 整 个 181.mcf 的 所 有 PDG 同 时 显 示 在 一 个 屏 幕 上 后, 程 序 员 简 直 无 从 下 手, 所 以 必 须 采 用 层 次 化 设 计 此 图 为 仅 将 181.mcf 的 main 函 数 PDG 显 示 结 果 : 19

25 第 20 页 如 图 仅 为 测 试 集 中 最 小 例 子 的 main 函 数 的 PDG 显 示, 由 于 图 信 息 量 太 大, 图 示 仅 能 辨 认 出 基 本 的 结 点 和 边, 其 他 信 息 已 无 从 辨 认, 这 给 程 序 员 的 调 试 过 程 造 成 了 很 大 的 困 难 另 外, 由 于 程 序 员 在 调 试 过 程 中 的 需 求 有 所 不 同, 有 的 时 候 不 需 要 显 示 所 有 函 数 的 PDG 结 果, 有 的 时 候 函 数 PDG 显 示 的 结 果 也 不 同 例 如, 在 切 片 过 程 中, 程 序 员 有 时 只 想 在 调 用 图 的 层 面 上 理 解 切 片 结 果, 在 调 用 图 的 基 础 上, 能 够 很 直 观 地 看 到 各 函 数 的 调 用 关 系 是 否 与 切 片 相 关 等 信 息, 同 时, 函 数 中 种 子 数 目 也 可 同 时 显 示 在 这 一 层 面 上 有 时, 程 序 员 对 同 一 调 用 函 数 需 要 显 示 不 同 的 PDG 结 果, 例 如, 在 没 有 进 行 程 序 切 片 时, 程 序 员 在 调 试 程 序 过 程 中, 需 要 显 示 整 个 函 数 的 PDG 结 果, 而 在 程 序 切 片 之 后, 根 据 不 同 种 子 的 要 求, 需 要 显 示 切 片 之 后 函 数 PDG 的 结 果, 这 样 来 说, 在 程 序 切 片 前 后, 函 数 的 PDG 显 示 结 果 是 不 同 的, 而 且, 程 序 切 片 之 后, 根 据 程 序 员 对 PDG 显 示 的 需 求, 对 各 种 情 况 函 数 PDG 的 显 示 也 是 不 同 的 所 以, 必 须 进 行 层 次 化 设 计 才 能 达 到 程 序 员 的 这 些 需 求 面 向 用 户 层 的 控 制 流 图 的 图 形 化 设 计 同 样 需 要 层 次 化, 控 制 流 图 也 是 以 函 数 为 基 本 单 位, 在 调 用 图 的 基 础 上 进 行 的 第 二 层 的 设 计, 同 函 数 PDG 显 示 要 求 相 似, 控 制 流 图 也 需 要 进 行 切 片 前 和 切 片 后 的 显 示, 根 据 切 片 种 子 的 不 同, 显 示 不 同 的 切 片 结 果 而 且, 控 制 流 图 的 引 入 增 加 了 本 图 形 化 工 具 第 二 层 的 功 能, 用 户 可 以 在 函 数 PDG 和 控 制 流 图 的 显 示 上 进 行 不 同 的 切 换 这 些 功 能 都 要 求 本 工 具 进 行 层 次 化 设 计 20

26 第 21 页 层 次 化 设 计 层 次 化 设 计 总 体 构 架 在 本 文 设 计 中, 由 于 PDG 时 间 和 空 间 开 销 太 大, 所 以 在 实 验 过 程 中 进 行 分 层 显 示 在 整 个 过 程 中, 调 用 图 是 第 一 个 层 次, 在 调 用 图 中 可 对 各 函 数 间 调 用 关 系 进 行 不 同 描 述, 同 时 对 函 数 切 片 结 果 进 行 初 步 表 示 ; 第 二 层 是 单 个 函 数 PDG 和 控 制 流 图 的 显 示 在 第 二 层 中,PDG 和 控 制 流 图 又 可 以 做 不 同 结 果 的 显 示,Udraw 在 与 用 户 交 互 的 基 础 上, 确 定 需 求, 进 行 第 二 层 PDG 和 控 制 流 图 的 不 同 结 果 显 示 在 调 用 图 层 次 中, 除 了 进 行 函 数 间 基 本 调 用 关 系 的 显 示 外, 还 对 函 数 中 种 子 的 情 况 分 类 显 示, 以 便 程 序 员 能 够 在 调 用 图 层 面 上 直 观 地 分 析 出 切 片 种 子 情 况, 另 外, 这 种 显 示 也 方 便 与 各 函 数 进 行 交 互, 进 行 PDG 和 控 制 流 图 不 同 结 果 的 显 由 于 不 同 种 子 对 应 不 同 的 切 片 结 果, 切 片 结 果 也 能 够 反 映 在 调 用 图 层 面 上, 而 程 序 员 往 往 需 要 首 先 在 这 个 层 面 上 了 解 各 函 数 切 片 的 情 况, 所 以 在 调 用 图 层 面 上 还 需 实 现 切 片 结 果 的 显 示 功 能, 这 个 功 能 是 通 过 用 户 需 求 的 不 同, 与 Udraw 进 行 交 互 来 实 现 不 同 结 果 的 显 示 的 在 显 示 函 数 PDG 的 层 次 中, 除 了 实 现 基 本 函 数 PDG 的 显 示 之 外, 还 根 据 程 序 员 需 求 的 不 同, 对 不 同 结 果 PDG 进 行 分 类 显 示 在 调 用 图 层 次 中, 程 序 员 可 通 过 交 互 功 能 对 不 同 种 子 的 相 关 调 用 函 数 进 行 结 果 显 示, 同 样, 在 此 过 程 中, 程 序 员 会 需 要 进 行 切 片 后 的 PDG 结 果 显 示 在 显 示 控 制 流 图 的 层 次 中, 进 行 函 数 切 片 前 和 切 片 后 控 制 流 图 的 显 示, 以 基 本 块 为 单 位 进 行 控 制 流 图 的 图 形 化 工 作 同 样, 在 调 用 图 层 次 中, 用 户 通 过 交 互 功 能 对 不 同 种 子 的 相 关 调 用 函 数 进 行 结 果 显 示, 在 此 基 础 上 进 行 切 片 后 控 制 流 图 结 果 显 示 鉴 于 程 序 员 的 需 求 分 析, 层 次 化 显 示 总 体 设 计 如 下 : 函 数 的 调 用 图 PDG 和 控 制 流 图 是 在 Open64 编 译 器 运 行 过 程 中 生 成 的, 都 采 用 树 型 结 构, 对 应 相 应 的 类 结 构 收 集 相 关 种 子 函 数, 并 收 集 与 种 子 有 关 的 切 片 结 果, 便 于 后 文 显 示 绘 制 函 数 PDG 和 控 制 流 图, 将 函 数 有 关 PDG 结 构 以 Udraw 语 法 格 式 写 入 相 关 Udraw 文 件 中 绘 制 函 数 调 用 图, 显 示 含 有 种 子 的 函 数, 并 分 类 显 示 种 子 及 行 号 在 调 用 图 输 出 后, 激 活 交 互 处 理 功 能, 根 据 用 户 选 择 的 函 数, 输 出 调 用 图 切 片 结 果 或 相 关 PDG 和 控 制 流 图 结 果 Open64 运 行 终 止 后, 相 关 Udraw 文 件 仍 然 保 留, 以 方 便 用 户 手 工 重 21

27 第 22 页 现 相 关 PDG 和 控 制 流 图 结 构 层 次 化 设 计 实 现 函 数 调 用 图 是 在 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

28 第 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

29 第 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

30 第 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

31 第 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

32 第 27 页 调 用 图 的 功 能 实 现 程 序 员 在 切 片 过 程 中, 分 析 调 用 图 时, 需 要 得 到 如 下 信 息 : 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

33 第 28 页 函 数 PDG 的 功 能 实 现 函 数 PDG 功 能 需 求 在 切 片 过 程 中, 程 序 员 对 函 数 PDG 的 要 求 相 对 调 用 图 更 高, 所 以 图 形 化 PDG 过 程 所 实 现 的 功 能 更 加 具 体 1 函 数 PDG 需 区 分 切 片 前 和 切 片 后 结 果 ; 2 在 进 行 切 片 前 显 示 时, 需 对 不 同 结 点 及 边 进 行 区 别 显 示 ; 3 在 进 行 切 片 后 显 示 时, 需 对 是 否 在 切 片 中 的 结 点 及 边 进 行 区 别 显 示 ; 4 需 对 三 类 种 子 ( 源 种 子 条 件 种 子 终 结 种 子 ) 进 行 相 关 区 别 标 注 ; 5 需 实 现 根 据 不 同 结 点 信 息 进 行 结 点 查 找 的 功 能 ; 6 由 于 结 点 属 性 信 息 量 大, 不 能 同 时 显 示 在 结 点 上, 需 实 现 隐 藏 显 示 功 能 ; 7 由 于 边 上 不 能 进 行 文 本 显 示, 所 以 需 实 现 隐 藏 显 示 功 能 基 于 如 上 需 求, 相 关 实 现 在 下 文 中 介 绍 函 数 PDG 功 能 处 理 在 调 用 图 显 示 中, 实 现 两 层 之 间 的 交 互 功 能, 可 实 现 切 片 前 后 函 数 PDG 不 同 显 示 功 能 在 没 有 进 行 切 片, 或 没 有 对 种 子 进 行 选 取 的 的 情 况 下,PDG 显 示 结 果 是 把 PDG 所 有 结 点 和 边 的 信 息 全 部 显 示 出 来, 以 方 便 程 序 员 了 解 函 数 PDG 信 息 具 体 说 来, 是 显 示 各 PDG 结 点 和 边, 标 注 出 各 结 点 和 边 的 相 关 属 性, 把 相 关 信 息 显 示 在 结 点 和 边 的 外 观 上, 包 括 颜 色 形 状 等, 不 同 结 点 和 边 的 属 性 如 表 格 所 示 : 结 点 属 性 ENTRY 结 点 EXIT 结 点 CALL 结 点 WHIRL 结 点 PHI 结 点 MU 结 点 CHI 结 点 28 结 点 颜 色 浅 蓝 色 浅 蓝 色 黄 色 深 绿 色 白 色 白 色 白 色

34 第 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

35 第 30 页 控 制 流 图 的 功 能 实 现 用 户 需 要 获 得 的 只 是 程 序 源 代 码 的 控 制 流 关 系 及 切 片 后 程 序 各 语 句 的 切 片 结 果, 所 以 用 图 形 化 控 制 流 图 需 要 实 现 : 1 函 数 各 语 句 之 间 的 控 制 流 关 系 ; 2 切 片 后 控 制 流 图 的 切 片 结 果 ; 针 对 用 户 需 求 图 形 化 过 程 中 进 行 的 处 理 如 下 : 1 在 完 成 函 数 控 制 流 图 显 示 后, 将 其 中 不 含 WHIRL 语 句 的 基 本 块 进 行 删 除, 只 显 示 对 用 户 有 用 的 基 本 块 2 由 于 一 个 基 本 块 中 的 语 句 不 一 定 全 部 在 切 片 中 或 完 全 不 在 切 片 中, 而 Udraw 没 有 对 同 一 结 点 进 行 不 同 属 性 显 示 的 功 能, 所 以 显 示 切 片 结 果 的 过 程 中, 为 了 进 行 切 片 结 果 的 不 同 显 示, 将 基 本 块 再 进 行 分 块 显 示, 使 得 一 个 分 块 中 的 语 句 能 够 统 一 都 在 切 片 结 果 中 或 不 在 切 片 结 果 中 删 除 的 内 容 : 函 交 互 功 能 实 现 在 进 行 调 用 图 函 数 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

36 第 31 页 为 红 色 标 记, 非 切 片 结 果 中 的 边 灰 色 显 示, 控 制 流 图 的 显 示 中, 切 片 结 果 的 结 点 为 红 色, 非 切 片 结 果 中 结 点 为 蓝 色 由 于 第 二 层 为 函 数 PDG 和 控 制 流 图 的 显 示, 所 以 增 加 控 制 选 项 对 其 进 行 切 片, 用 pdg_drawing 来 进 行 PDG 的 显 示,cfg_drawing 进 行 控 制 流 图 的 显 示, 当 两 个 选 项 都 不 开 时, 切 片 工 具 不 进 行 图 形 化 显 示 本 文 程 序 整 体 流 程 可 以 看 出, 为 实 现 以 上 各 部 分 的 功 能, 不 但 要 充 分 理 解 Open64 编 译 平 台 中 各 类 及 数 据 结 构 及 相 关 函 数, 而 且 要 在 文 件 相 关 函 数 中 添 加 新 的 类 和 函 数, 在 不 影 响 编 译 器 其 他 功 能 的 前 提 下, 实 现 本 工 具 提 供 的 各 功 能 本 文 程 序 整 体 流 程 如 下 : 编 译 器 生 成 调 用 图 生 成 控 制 流 图 生 成 函 数 PDG 设 计 调 用 图 设 计 控 制 流 图 设 计 函 数 PDG 编 译 器 与 udraw 相 关 接 口 udraw 31

37 第 32 页 第 五 章 图 形 化 设 计 实 例 本 文 所 用 实 例 是 SPEC CPU2000 中 181.mcf,SPEC CPU2000 已 在 前 文 中 介 绍 过, 其 中 的 181.mcf 是 其 中 最 小 的 实 例, 下 文 将 以 它 为 例 来 进 行 实 例 说 明 5.1 调 用 图 的 实 例 实 现 由 于 在 切 片 过 程 中 需 求 不 同, 第 二 层 显 示 函 数 PDG 和 控 制 流 图 需 要 通 过 不 同 开 关 来 切 换, 用 pdg_drawing 和 cfg_drawing 来 控 制 第 二 层 的 不 同 显 示 结 果, 而 在 这 两 个 开 关 的 控 制 下, 第 一 层 调 用 图 的 显 示 是 不 变 的 下 图 是 pdg_drawing=on 情 况 下 的 调 用 图 显 示 结 果 : 图 中 显 示 结 点 号 及 函 数 名, 箭 头 方 向 为 函 数 的 调 用 情 况 在 pdg_drawing 的 情 况 下, 对 程 序 进 行 切 片, 函 数 中 包 含 切 片 结 果 在 调 用 图 中 必 须 对 存 在 程 序 切 片 标 准 中 相 关 种 子 的 函 数 进 行 显 示, 以 方 便 32

38 第 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

39 第 34 页 含 有 三 个 源 种 子 找 到 源 种 子 后, 运 行 程 序 前 向 切 片, 收 集 到 相 关 条 件 种 子 和 终 结 种 子, 再 运 行 程 序 后 向 切 片 收 集 到 相 关 函 数 切 片 结 果 为 进 行 相 关 交 互 功 能, 将 与 源 种 子 有 关 的 切 片 结 果 函 数 分 类 保 存 在 相 关 位 向 量 中, 以 便 后 文 进 行 切 片 结 果 的 显 示 功 能 选 取 其 中 之 一 种 子 后 显 示 函 数 切 片 结 果 : 34

40 第 35 页 5.2 函 数 PDG 的 实 例 实 现 不 包 含 切 片 结 果 的 PDG 显 示 如 上 文 所 述, 当 打 开 开 关 pdg_drawing 时, 在 未 进 行 切 片 或 函 数 不 包 含 在 切 片 结 果 中 时, 函 数 PDG 显 示 为 全 部 属 性 和 边 的 显 示, 此 内 容 把 函 数 PDG 的 所 有 信 息 都 显 示 出 来, 下 图 为 实 例 中 函 数 bea_compute_red_cost 的 PDG 显 示 的 一 部 分 : 35

41 第 36 页 图 中 用 不 同 颜 色 结 点 和 边 来 标 注 不 同 PDG 的 属 性, 在 其 中 可 进 行 查 找 功 能 及 显 示 隐 藏 属 性 的 功 能 : 如 查 找 其 中 WHIRL 结 点, 则 输 入 如 下 格 式 : 结 果 显 示 如 下 : 36

42 第 37 页 INFO 结 构 显 示 信 息 结 构 如 下 : 37

43 第 38 页 38

44 第 39 页 包 含 切 片 结 果 的 PDG 显 示 在 进 行 切 片, 或 函 数 包 含 在 切 片 结 果 中,PDG 显 示 则 只 显 示 是 否 在 切 片 中 两 种 情 况, 即 在 切 片 中 的 PDG 结 点 及 边 用 不 同 颜 色 显 示, 不 在 切 片 中 的 PDG 结 点 及 边 则 用 白 色 和 灰 色 显 示, 同 时 显 示 三 类 种 子 结 点 : 源 种 子 条 件 种 子 和 终 结 种 子, 将 这 三 类 种 子 结 点 以 双 线 框 框 起, 效 果 图 如 下 所 示 : 其 他 属 性 功 能 与 不 含 切 片 结 果 PDG 显 示 相 同 5.3 控 制 流 图 的 实 例 实 现 不 包 含 切 片 结 果 的 控 制 流 图 显 示 同 样, 当 打 开 开 关 cfg_drawing 时, 在 未 进 行 切 片 或 函 数 不 包 含 在 切 片 结 果 中 时, 函 数 控 制 流 图 显 示 为 函 数 基 本 块 及 基 控 制 关 系, 此 内 容 把 函 数 控 制 流 关 系 都 显 示 出 来, 下 图 为 实 例 中 函 数 getfree 的 控 制 流 图 显 示 : 39

45 第 40 页 包 含 切 片 结 果 的 控 制 流 图 显 示 在 进 行 切 片, 或 函 数 包 含 在 切 片 结 果 中, 控 制 流 图 显 示 则 只 显 示 是 否 在 切 片 中 两 种 情 况, 即 在 切 片 中 的 基 本 块 及 用 不 同 颜 色 显 示, 不 在 切 片 中 的 基 本 块 则 不 改 变 颜 色 显 示, 下 图 为 函 数 getfree, 效 果 图 如 下 所 示 : 40

46 第 41 页 41

47 第 42 页 第 六 章 成 本 资 源 分 析 本 文 完 成 的 工 作 是 中 国 科 学 院 计 算 技 术 研 究 所 计 算 机 系 统 结 构 重 点 实 验 室 正 在 进 行 的 工 作 的 一 部 分, 此 工 作 是 基 于 Open64 编 译 平 台 上 的 程 序 分 析 工 具 方 面 的 研 发, 其 中 包 括 程 序 切 片 技 术 工 具 的 开 发, 我 做 的 工 作 的 目 的 是 将 切 片 过 程 中 的 数 据 结 构 图 形 结 构 用 图 形 化 工 具 进 行 表 示 由 于 Open64 编 译 器 是 开 源 编 译 软 件, 不 涉 及 源 代 码 的 成 本 问 题, 而 且 在 编 译 器 的 分 析 开 发 过 程 中 用 到 的 工 具 和 算 法 都 是 现 在 学 术 界 普 遍 使 用 的, 没 有 专 利 费 用 等 问 题, 所 以 本 软 件 工 具 在 开 发 过 程 中 不 涉 及 成 本 问 题 而 整 个 实 验 室 对 编 译 分 析 的 贡 献 是 很 大 的, 程 序 切 片 工 具 的 应 用 前 景 不 可 估 量, 而 本 文 从 事 的 工 作 是 其 中 的 比 较 重 要 的 一 环, 这 在 整 个 团 队 中 也 起 到 了 不 可 替 代 的 作 用 未 来 随 着 切 片 工 具 的 广 泛 使 用, 本 图 形 化 工 具 也 将 随 之 得 到 应 用, 随 之 带 来 的 各 种 影 响 也 是 不 言 而 喻 的 本 工 具 完 成 并 应 用 之 后, 使 整 个 团 队 的 工 作 效 率 得 到 提 高 未 应 用 本 工 具 之 前, 在 切 片 过 程 分 析 时, 使 用 纯 文 本 手 工 对 函 数 调 用 图 和 PDG 进 行 绘 制, 分 析 每 个 程 序 用 的 时 间 开 销 很 大, 而 使 用 本 工 具 之 后, 由 于 自 动 生 成 图 形 化 界 面, 省 掉 了 手 工 绘 制 图 的 时 间, 为 程 序 切 片 分 析 做 出 了 贡 献 减 少 了 这 方 面 人 力 资 源, 提 高 了 整 个 团 队 的 工 作 效 率 42

48 第 43 页 第 七 章 结 论 本 文 主 要 实 现 了 程 序 切 片 工 具 的 图 形 化, 在 Open64 编 译 平 台 上, 实 现 了 程 序 切 片 工 具 与 图 形 化 工 具 的 接 口 本 工 具 从 切 片 工 具 调 试 人 员 的 需 求 出 发, 在 经 过 多 次 修 改 和 补 充 之 后, 经 过 多 次 测 试, 在 切 片 工 具 的 调 试 和 验 证 团 队 中 得 到 广 泛 的 应 用, 为 简 化 其 工 作 做 出 了 贡 献 切 片 工 具 图 形 化 部 分 相 信 能 够 对 编 译 器 的 研 究 做 出 贡 献, 一 个 优 先 的 可 视 化 编 译 器 需 要 几 个 关 键 的 组 件 互 相 之 间 很 好 的 整 合 起 来 形 成 一 个 结 构 这 些 组 件 包 括 : 一 个 易 扩 展 的 编 译 器, 一 个 简 单 又 功 能 足 够 的 中 间 语 言 格 式, 一 个 图 形 用 户 界 面 工 具 包 Open64 就 是 致 力 于 推 动 研 究 的 公 开 源 代 码 的 编 译 器, 采 用 SGI 公 司 精 心 设 计 的 WHIRL 作 为 中 间 语 言 格 式, 可 以 支 持 C C++ FORTRAN90 和 FORTRAN95 等 多 种 语 言 的 编 译 器 前 端 UdrawGraph 又 是 在 学 术 研 究 界 广 泛 使 用 的 图 形 化 工 具 所 以 说 切 片 工 具 图 形 化 部 分 能 够 比 较 好 的 满 足 这 三 个 要 求 现 在 本 文 实 现 的 接 口 和 功 能 已 在 程 序 切 片 过 程 中 得 到 应 用, 解 决 了 许 多 难 题, 大 大 提 高 了 调 试 人 员 的 工 作 效 率 43

49 第 44 页 参 考 文 献 外 文 文 献 1.Aho, A.V. and Ullman, J.D.,Principles of Compiler design. Addison-Wesley, 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, 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, Muchnick, S.S., Advanced Compiler Design and Implementation. Elsesiver Science, 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 ,1984), ACM SIGPLAN Notices 19(5) pp (may 1984). 8.Weiser, M., Program Slicing. Proceedings of the 5th international conference on Software engineering,1981: 中 文 文 献 9. 杜 林. 面 向 对 象 程 序 切 片 技 术 研 究. 山 东 省 教 育 学 院 学 报,2007, 李 必 信, 郑 国 梁. 一 种 分 析 和 理 解 程 序 的 方 法 程 序 切 片. 计 算 机 研 究 与 发 展,2000,37(3). 11. 谭 浩 强.C 程 序 设 计 ( 第 三 版 ). 清 华 大 学 出 版 社, 王 伟, 陈 平. 程 序 切 片 技 术 综 述. 学 术 论 坛. 13. 王 燕. 面 向 对 象 的 理 论 与 C++ 实 践. 清 华 大 学 出 版, 张 昊 中.Pathscale 中 编 译 信 息 图 形 化 的 改 进 实 现

50 第 45 页 15. 张 勇 翔, 李 必 信, 郑 国 梁. 程 序 切 片 技 术 的 研 究 与 应 用. 计 算 机 科 学,2000,27(1). 16. 周 述 康. 面 向 IA-64 体 系 结 构 的 编 译 器 AURORA 的 图 形 可 视 化. 北 京 大 学 学 士 学 位 论 文. 参 考 网 址 html

51 第 46 页 附 录 Benchmark.f.f90.c.h.C 164.gzip vpr gcc mcf crafty 19 2 CPU parser Integer 252.eon perlbmk gap vortex bzip twolf 20 1 CPU2000 FP 168.wupwise swim mgrid applu mesa galgel art equake facerec ammp lucas fma3d sixtrack apsi 7 表 格 附 1 SPEC CPU2000 代 码 行 数 ( 单 位 1000) Benchmark.f.f90.c.h.C CPU gzip

52 第 47 页 Integer 175.vpr gcc mcf crafty parser eon perlbmk gap vortex bzip twolf CPU2000 FP 168.wupwise swim mgrid applu mesa galgel art equake facerec ammp lucas fma3d sixtrack apsi 1 表 格 附 2 SPEC CPU2000 原 代 码 文 件 数 47