Lecture 20: MIPS Assembly Language II
Example: 过 程 调 用 int i; i 是 全 局 静 态 变 量 void set_array(int num) { array 数 组 是 局 部 变 量 int array[10]; for (i = 0; i < 10; i ++) { set_array 是 调 用 过 程 arrar[i] = compare (num, i); } compare 是 被 调 用 过 程 } int compare (int a, int b) compare 是 调 用 过 程 { sub 是 被 调 用 过 程 if ( sub (a, b) >= 0) return 1; else return 0; 问 题 : 过 程 调 用 对 应 的 机 器 代 码 如 何 表 示? } 1. 如 何 从 调 用 程 序 把 参 数 传 递 到 被 调 用 程 序? int sub (int a, int b) { return a-b; } 2. 如 何 从 调 用 程 序 执 行 转 移 到 被 调 用 程 序 执 行? 3. 如 何 从 被 调 用 程 序 返 回 到 调 用 程 序 执 行? 4. 如 何 保 证 调 用 程 序 中 寄 存 器 内 容 不 被 破 坏?
Procedure Call and Stack( 过 程 调 用 和 栈 ) 过 程 调 用 的 执 行 步 骤 ( 假 定 过 程 P 调 用 过 程 Q): compare (num, i); 将 参 数 放 到 Q 能 访 问 到 的 地 方 在 调 用 过 程 P 将 P 中 的 返 回 地 址 存 到 特 定 的 地 方, 将 控 制 转 移 到 过 程 Q 中 完 成 为 Q 的 局 部 变 量 分 配 空 间 ( 局 部 变 量 临 时 保 存 在 栈 中 ) 执 行 过 程 Q 在 被 调 用 过 程 Q 将 Q 执 行 的 返 回 结 果 放 到 P 能 访 问 到 的 地 方 中 完 成 取 出 返 回 地 址, 将 控 制 转 移 到 P, 即 返 回 到 P 中 执 行 MIPS 中 用 于 过 程 调 用 的 指 令 ( 见 MIPS 过 程 调 用 指 令 ) MIPS 规 定 少 量 过 程 调 用 信 息 用 寄 存 器 传 递 ( 见 MIPS 寄 存 器 功 能 定 义 ) 如 果 过 程 中 用 到 的 参 数 超 过 4 个, 返 回 值 超 过 2 个, 怎 么 办? 更 多 的 参 数 和 返 回 值 要 保 存 到 存 储 器 的 特 殊 区 域 中 这 个 特 殊 区 域 为 : 栈 (Stack) 一 般 用 栈 来 传 递 参 数 保 存 返 回 地 址 临 时 存 放 过 程 的 局 部 变 量 等 为 什 么? 便 于 递 归 调 用!
栈 (Stack) 的 概 念 栈 的 基 本 概 念 是 一 个 先 进 后 出 队 列 需 一 个 栈 指 针 指 向 栈 顶 元 素 每 个 元 素 长 度 一 致 用 入 栈 (push) 和 出 栈 (pop) 操 作 访 问 栈 元 素 MIPS 中 栈 的 实 现 用 栈 指 针 寄 存 器 $sp 来 指 示 栈 顶 元 素 每 个 元 素 的 长 度 为 32 位, 即 : 一 个 字 (4 个 字 节 ) 入 栈 和 出 栈 操 作 用 sw / lw 指 令 来 实 现, 需 用 add / sub 指 令 调 整 $sp 的 值, 不 能 像 x86 那 样 自 动 进 行 栈 指 针 的 调 整 ( 有 些 处 理 器 有 专 门 的 push/pop 指 令, 能 自 动 调 整 栈 指 针 如 x86) 栈 生 长 方 向 从 高 低 地 址 增 长, 而 取 数 / 存 数 的 方 向 是 低 高 地 址 ( 大 端 方 式 )» 每 入 栈 1 字,$sp- 4 $sp ; 每 出 栈 1 字,$sp+4 $sp 例 : 若 将 返 回 地 址 $ra 和 参 数 $a0 保 存 到 栈, 则 指 令 序 列 为 : sub $sp, $sp, 8 sw $ra, 4($sp) sw $a0, 0($sp) $sp $ra $a0 高 地 址 栈 增 长 的 方 向 低 地 址
栈 帧 的 概 念 各 过 程 有 自 己 的 栈 区, 称 为 栈 帧 (Stack frame), 即 过 程 的 帧 (procedure frame) 栈 由 若 干 栈 帧 组 成 用 专 门 的 帧 指 针 寄 存 器 指 定 起 始 位 置 当 前 栈 帧 范 围 在 帧 指 针 和 栈 指 针 之 间 程 序 执 行 时, 栈 指 针 可 移 动, 帧 指 针 不 变 所 以 过 程 内 对 栈 信 息 的 访 问 大 多 通 过 帧 指 针 进 行 X86 的 栈 帧 情 况 如 右 图 所 示 假 定 P 调 用 Q P 帧 中 Q 所 用 的 参 数 若 调 用 时 将 返 回 地 址 入 栈, 则 在 P 帧 中 存 放 返 回 地 址 帧 指 针 需 保 存 的 寄 存 器 Q 所 用 的 局 部 和 临 时 变 量 Q 传 给 其 他 过 程 的 参 数 栈 指 针 P frame Q frame
MIPS 中 的 过 程 调 用 ( 假 定 P 调 用 Q) 程 序 可 访 问 的 寄 存 器 组 是 所 有 过 程 共 享 的 资 源, 给 定 时 刻 只 能 被 一 个 过 程 使 用, 因 此 过 程 中 使 用 的 寄 存 器 的 值 不 能 被 另 一 个 过 程 覆 盖! MIPS 的 寄 存 器 使 用 约 定 : 保 存 寄 存 器 $s0 ~$s7 的 值 在 从 被 调 用 过 程 返 回 后 还 要 被 用, 被 调 用 者 需 要 保 留 临 时 寄 存 器 $t0 ~$t9 的 值 在 从 被 调 用 过 程 返 回 后 不 需 要 被 用 ( 需 要 的 话, 由 调 用 者 保 存 ), 被 调 用 者 可 以 随 意 使 用 参 数 寄 存 器 $a0~$a3 在 从 被 调 用 过 程 返 回 后 不 需 要 被 用 ( 需 要 的 话, 由 调 用 者 保 存 在 栈 帧 或 其 他 寄 存 器 中 ), 被 调 用 者 可 以 随 意 使 用 全 局 指 针 寄 存 器 $gp 的 值 不 变 在 过 程 调 用 时 帧 指 针 寄 存 器 $fp 用 栈 指 针 寄 存 器 $sp- 4 来 初 始 化 需 在 被 调 用 过 程 Q 中 入 栈 保 存 的 寄 存 器 ( 称 为 被 调 用 者 保 存 ) 返 回 地 址 $ra ( 如 果 Q 又 调 用 R, 则 $ra 内 容 会 被 破 坏, 故 需 保 存 ) 保 存 寄 存 器 $s0 ~$s7 (Q 返 后 P 可 能 还 会 用 到,Q 中 用 的 话 就 被 破 坏, 故 需 保 存 ) 除 了 上 述 寄 存 器 以 外, 所 有 局 部 数 组 和 结 构 类 型 变 量 也 要 入 栈 保 存 如 果 局 部 变 量 和 临 时 变 量 发 生 寄 存 器 溢 出 ( 寄 存 器 不 够 分 配 ), 则 也 要 入 栈 每 个 处 理 器 对 栈 帧 规 定 的 调 用 者 保 存 和 被 调 用 者 保 存 的 寄 存 器 可 能 不 同 例 : x86 中 返 回 地 址 保 存 在 调 用 过 程 栈 帧 中 ; 而 MIPS 则 在 被 调 用 过 程 栈 帧 中 保 存 x86 中 调 用 参 数 保 存 在 调 用 过 程 栈 帧 中 ; 而 MIPS 则 在 被 调 用 过 程 栈 帧 中 保 存 X86 中 调 用 过 程 的 帧 指 针 保 存 在 被 调 用 过 程 栈 帧 中 ;MIPS 也 一 样
过 程 调 用 时 MIPS 中 的 栈 和 栈 帧 的 变 化
Example in C: swap 假 定 swap 作 为 一 个 过 程 被 调 用,temp 对 应 $t0, 变 量 v 和 k 分 别 对 应 $s0 和 $s1 写 出 对 应 的 MIPS 汇 编 代 码 swap(int v[ ], int k) 问 题 : 上 述 假 设 有 何 问 题? 参 数 v 和 k 应 该 在 $a0 和 $a1 { sll $s2, $a1, 2 ; mulitply k by 4 addu $s2 $s2, $a0 ; address of v[k] int temp; lw $t0, 0($s2) ; load v[k] temp = v[k]; lw $s3, 4($s2) ; load v[k+1] v[k] = v[k+1]; v[k+1] = temp; sw sw $s3, 0($s2) $t0, 4($s2) ; store v[k+1] into v[k] ; store old v[k] into v[k+1] } 在 调 用 过 程 中 用 指 令 jal swap 进 行 swap 调 用 jal --- jump and link ( 跳 转 并 链 接 ) $31 = PC+4 ; $31=$ra goto swap 问 题 1: 若 swap 中 不 保 存 $s2, 则 会 发 生 什 么 情 况? caller 中 $s2 的 值 被 破 坏! 须 在 swap 中 保 存 $s2 问 题 2: 若 swap 中 不 保 存 $t0, 则 会 发 生 什 么 情 况? $t0 约 定 由 caller 保 存, 故 无 须 在 swap 栈 帧 中 保 存 $t0 调 用 程 序 sub $s2,$s3,$s1 jal swap add $s3,$s2,$t0 swap 程 序 jr $ra
swap: MIPS 中 的 一 个 过 程 示 例 swap: addi $sp,$sp, 12 ; 栈 增 长 3 个 sw $31, 8($sp) ; 返 回 地 址 入 栈 sw $s2, 4($sp) ; 保 留 寄 存 器 $s2 入 栈 sw $s3, 0($sp) ; 保 留 寄 存 器 $s3 入 栈... lw $s3, 0($sp) ; 恢 复 $s3 lw $s2, 4($sp) ; 恢 复 $s2 lw $31, 8($sp) ; 恢 复 $31($ra) addi $sp,$sp, 12 ; 退 栈 $sp sll $s2, $a1, 2 ; mulitply k by 4 addu $s2, $s2, $a0 ; address of v[k] lw $t0, 0($s2) ; load v[k] lw $s3, 4($s2) ; load v[k+1] sw $s3, 0($s2) ; store v[k+1] into v[k] sw $t0, 4($s2) ; store old v[k] into v[k+1] jr $31 ; 从 swap 返 回 到 调 用 过 程 问 题 : 是 否 一 定 要 将 返 回 地 址 ($31) 保 存 到 栈 帧 中? $ra $s2 $s3 如 果 swap 是 叶 子 过 程, 则 无 需 保 存 返 回 地 址 到 栈 中, 为 什 么? 如 果 将 所 有 内 部 寄 存 器 都 用 临 时 寄 存 器 ( 如 $t1 等 ), 则 叶 子 过 程 swap 的 栈 帧 为 空, 且 上 述 黑 色 指 令 都 可 去 掉 高 地 址 栈 增 长 的 方 向 $ra 的 内 容 不 会 被 破 坏!
Example: 过 程 调 用 int i; i 是 全 局 静 态 变 量 void set_array(int num) { array 数 组 是 局 部 变 量 int array[10]; for (i = 0; i < 10; i ++) { set_array 是 调 用 过 程 arrar[i] = compare (num, i); } compare 是 被 调 用 过 程 } int compare (int a, int b) { if ( sub (a, b) >= 0) return 1; else return 0; } int sub (int a, int b) { return a-b; } compare 是 调 用 过 程 sub 是 被 调 用 过 程 问 题 1: 编 译 器 如 何 为 全 局 变 量 和 局 部 变 量 分 配 空 间? 问 题 2: 执 行 set_array 的 结 果 是 什 么?
过 程 调 用 时 的 变 量 分 配 全 局 静 态 变 量 一 般 分 配 到 寄 存 器 或 在 R/W 存 储 区 ( 数 组 或 结 构 等 ) 该 例 中 只 有 一 个 简 单 变 量 i, 假 定 分 配 给 $s0 无 需 保 存 和 恢 复! 为 减 少 指 令 条 数, 并 减 少 访 问 内 存 次 数 在 每 个 过 程 的 过 程 体 中 总 是 先 使 用 临 时 寄 存 器 $t0~$t9, 临 时 寄 存 器 不 够 或 者 某 个 值 在 调 用 过 程 返 回 后 还 需 要 用, 就 使 用 保 存 寄 存 器 $s0~$s7 过 程 set_array 的 入 口 参 数 为 num, 没 有 返 回 参 数, 有 一 个 局 部 数 组, 被 调 用 过 程 为 compare, 因 此, 其 栈 帧 中 除 了 保 留 所 用 的 保 存 寄 存 器 外, 必 须 保 留 返 回 地 址 ( 是 否 保 存 $fp 要 看 具 体 情 况, 如 果 确 保 后 面 都 不 用 到 $fp, 则 可 以 不 保 存, 但 为 了 保 证 $fp 的 值 不 被 后 面 的 过 程 覆 盖, 通 常 情 况 下, 应 该 保 存 $fp 的 值 ), 并 给 局 部 数 组 预 留 4 10=40 个 字 节 的 空 间 从 过 程 体 来 看, 从 compare 返 回 后 还 需 要 用 到 数 组 基 地 址, 故 将 其 分 配 给 $s1 因 此 要 用 到 的 保 存 寄 存 器 有 两 个 :$s0 和 $s1, 但 只 需 要 保 存 $s1 另 外 加 上 返 回 地 址 $ra 帧 指 针 $fp 局 部 数 组, 其 栈 帧 空 间 最 少 为 3 4+40=52B
程 序 的 翻 译 链 接 和 加 载 ( 自 学 ) 不 同 的 高 级 语 言 有 不 同 的 编 译 器, 但 生 成 的 汇 编 语 言 一 样 前 面 许 多 例 子 说 明 了 编 译 器 如 何 把 高 级 语 言 语 句 翻 译 成 汇 编 指 令 每 台 机 器 的 汇 编 程 序 功 能 一 样, 与 高 级 语 言 无 关 目 标 文 件 就 是 机 器 语 言 ( 指 令 数 据 及 链 接 说 明 信 息 ) 如 何 链 接? 可 执 行 文 件 要 说 明 代 码 和 数 据 区 多 大, 并 给 出 每 条 指 令 的 机 器 码 及 其 地 址 各 数 据 及 其 地 址 将 多 个 过 程 ( 包 括 库 例 程 ) 的 目 标 文 件 链 接 成 一 个 可 执 行 文 件 加 载 可 执 行 文 件 到 存 储 器, 并 启 动 开 始 执 行 如 何 分 配 代 码 和 数 据 的 地 址? SKIP
复 习 :MIPS 程 序 和 数 据 的 存 储 器 分 配 每 个 MIPS 程 序 都 按 如 下 规 定 进 行 存 储 器 分 配 每 个 可 执 行 文 件 都 按 如 下 规 定 给 出 代 码 和 数 据 的 地 址 栈 区 位 于 堆 栈 高 端, 堆 区 位 于 堆 栈 低 端 静 态 数 据 区 存 放 全 局 变 量 ( 也 称 静 态 变 量 ), 指 所 有 过 程 之 外 声 明 的 变 量 和 用 Static 声 明 的 变 量 ; 从 固 定 的 0x1000 0000 处 开 始 向 高 地 址 存 放 全 局 指 针 $gp 总 是 0x1000 8000, 其 16 位 偏 移 量 的 访 问 范 围 为 0x1000 0000~0x1000 ffff, 可 遍 及 整 个 静 态 数 据 区 的 访 问 Heap 程 序 代 码 从 固 定 的 0x0040 0000 处 开 始 存 放 故 PC 的 初 始 值 为 0x0040 0000 BACK
目 标 文 件 的 链 接 ( 自 学 ) 过 程 A 和 过 程 B 分 别 编 译 汇 编 成 目 标 文 件, 链 接 后 生 成 一 个 可 执 行 文 件 过 程 A 的 目 标 文 件 代 码 的 长 度 为 0x100 数 据 的 长 度 为 0x20 链 接 前 地 址 总 是 从 0 开 始 实 际 是 指 令 机 器 码 0 是 由 x 待 定 的 地 址 0 是 由 B 待 定 的 地 址 链 接 前 地 址 总 是 从 0 开 始 X 的 地 址 待 定 B 的 地 址 待 定
目 标 文 件 的 链 接 ( 自 学 ) 过 程 A 和 过 程 B 分 别 编 译 汇 编 成 目 标 文 件, 链 接 后 生 成 一 个 可 执 行 文 件 过 程 B 的 目 标 文 件 代 码 的 长 度 为 0x200 数 据 的 长 度 为 0x30 0 是 由 Y 待 定 的 地 址 0 是 由 A 待 定 的 地 址
目 标 文 件 的 链 接 ( 自 学 ) 过 程 A 和 过 程 B 分 别 编 译 汇 编 成 目 标 文 件, 链 接 后 生 成 一 个 可 执 行 文 件 生 成 的 可 执 行 文 件 代 码 地 址 总 是 从 0040 0000 开 始 过 程 B 从 A 后 的 0x100 开 始 静 态 区 地 址 从 0x1000 0000 开 始 1000 0000=?+ 1000 8000 过 程 B 从 A 后 的 0x20 开 始 1000 8000+ FFFF 8000=1000 0000H?= 8000 ( 符 号 扩 展 后 为 FFFF 8000) BACK
MIPS 指 令 中 位 的 指 定 和 逻 辑 运 算 ( 自 学 ) 逻 辑 数 据 表 示 用 一 位 表 示 真 :1 -True / 假 :0-False N 位 二 进 制 数 可 表 示 N 个 逻 辑 数 据 逻 辑 运 算 按 位 进 行, 如 : And / Or / Shift Left / Shift Right 等 位 的 指 定 设 置 某 位 的 值 : 清 0: 与 掩 码 (1 101 1) 相 与 置 1: 与 位 串 (0 010 0) 相 或 判 断 某 位 的 值 : 是 否 为 0: 与 位 串 (0 010 0) 相 与 后, 是 否 为 0 是 否 为 1: 与 位 串 ( 0 010 0 ) 相 与 后, 是 否 不 为 0 MIPS 中 的 移 位 指 令 (sll / srl) 例 : srl $t2,$s0,8 $s0 右 移 8 位 后 送 $t2 op rs rt rd shamt func 000000 00000 10000 01010 01000 000010 逻 辑 数 据 和 数 值 数 据 在 形 式 上 并 无 差 别, 也 是 一 串 0/1 序 列, 机 器 本 身 不 能 识 别, 需 靠 指 令 的 类 型 来 识 别 包 括 后 面 所 讲 的 字 符 数 据 等 都 一 样
MIPS 指 令 中 常 数 的 指 定 ( 自 学 ) 程 序 中 经 常 需 要 使 用 常 数, 例 如 : C 编 译 器 gcc 中 52% 的 算 术 指 令 用 到 常 数 电 路 模 拟 程 序 Spice 中 69% 的 算 术 指 令 用 到 常 数 指 令 中 如 何 取 得 常 数 若 程 序 装 入 时, 常 数 已 在 内 存 中, 则 需 用 load 指 令 读 入 寄 存 器 在 指 令 中 用 一 个 立 即 数 来 使 用 常 数 例 1:i=i+4; Assuming variable i ~ $1 则 : addi $1, $1, 4 例 2:if (i<20). ; Assuming variable i ~ $1 则 : slti $3, $1, 20 ; if (i<20) $3=1 else $3=0 如 果 常 数 的 值 用 16 位 无 法 表 示, 怎 么 办? 用 lui 指 令 把 高 16 位 送 到 寄 存 器 的 高 16 位, 再 把 低 16 位 加 到 该 寄 存 器 中 例 3: 将 0000 0000 0011 1101 0000 0000 0000 1000 送 $3 中 则 : lui $3, 61 addi $3, $3, 8
MIPS 指 令 中 如 何 表 示 文 本 字 符 串 ( 自 学 ) 有 些 情 况 下, 程 序 需 要 处 理 文 本 例 如 : 西 文 文 本 由 ASCII 码 字 符 构 成 字 符 串 Java 等 语 言 使 用 Unicode 编 码 构 成 字 符 串 汉 字 文 本 使 用 的 汉 字 编 码 字 符 构 成 字 符 串 字 符 串 的 表 示 由 一 个 个 字 符 组 成, 长 度 不 定 有 三 种 表 示 方 式 :» 字 符 串 的 首 字 节 记 录 长 度» 用 其 他 变 量 来 记 录 长 度 ( 即 : 用 struc 类 型 来 描 述 )» 字 符 串 末 尾 用 一 个 特 殊 字 符 表 示 如 :C 语 言 用 字 符 (NULL) 来 标 记 字 符 串 结 束 如 何 在 指 令 中 表 示 字 符 ASCII 字 符 串, 每 个 字 符 由 8 位 组 成, 用 lb/sb 指 令 存 / 取 一 个 字 节 Unicode 及 汉 字 字 符 都 有 16 位, 用 lh/sh 指 令 存 / 取 两 个 字 节 例 :x[i] = y[j]; variables i,j ~ $1,$2, base address x,y ~ $3,$4 则 : add $5, $3, $1 ; $5=the address of x[i] add $6, $4, $2 ; $6=the address of y[j] lb $7, 0($6) ; $7=y[j] sb $7, 0($5) ; x[i]=$7 SKIP
数 据 类 型 和 MIPS 指 令 的 对 应 ( 自 学 ) C 语 言 中 的 char 为 8 位, Java 语 言 中 的 char 为 16 位 (Unicode)
本 讲 小 结 MIPS 指 令 格 式 R- 类 型 / I- 类 型 / J- 类 型 MIPS 寄 存 器 长 度 / 个 数 / 功 能 分 配 MIPS 操 作 数 寄 存 器 操 作 数 / 存 储 器 操 作 数 / 立 即 数 / 文 本 MIPS 指 令 寻 址 方 式 立 即 数 寻 址 / 寄 存 器 寻 址 / 相 对 寻 址 / 伪 直 接 寻 址 / 偏 移 寻 址 MIPS 指 令 类 型 算 术 / 逻 辑 / 数 据 传 送 / 条 件 分 支 / 无 条 件 转 移 MIPS 汇 编 语 言 形 式 操 作 码 的 表 示 / 寄 存 器 的 表 示 / 存 储 器 数 据 表 示 机 器 语 言 的 解 码 ( 反 汇 编 ) 高 级 语 言 汇 编 语 言 机 器 语 言 之 间 的 转 换 运 算 表 达 式 / If 语 句 / 循 环 / 数 组 访 问 / 过 程 / 堆 栈 / 栈 帧 其 他 指 令 系 统 :PowerPC 80x86 CISC vs. RISC