编译原理与技术 运行环境.ppt

2020 3 1 编译原理与技术 运行环境 1 编译原理与技术 运行环境 2020 3 1 编译原理与技术 运行环境 2 运行环境 存储组织与分配程序单元 运行时内存划分与活动记录静态 动态存储分配动态栈式的过程调用 返回非局部名字的访问参数传递参数传递的方式及其实现 2020 3 1 编译原理与技术 运行环境 3 存储组织与分配 程序单元 fortran的子例程 subroutine pascal的过程 函数 procedure function c的函数程序单元的激活 调用 与终止 返回 程序单元的执行需要 代码段 活动记录 程序单元运行所需的额外信息 如参数 局部数据 返回地址等 2020 3 1 编译原理与技术 运行环境 4 运行时内存划分 代码段 静态数据区 栈 stack 堆 heap 大小可以静态确定 全局 局部静态变量 活动记录栈 动态分配的数据 2020 3 1 编译原理与技术 运行环境 5 活动记录 活动记录 ar activationrecord 是一连续存储区域 用于管理与存放和程序单元执行相关的重要信息 ar中的内容 临时区域 用以保存临时计算结果 局部数据区 源程序中程序单元声明的局部变量对应在此区域 机器状态保存区 存有机器的寄存器 程序指令计数器ip 返回地址 等 2020 3 1 编译原理与技术 运行环境 6 活动记录 ar中的内容 访问链 静态链 当前程序单元可以访问的 静态程序中 外围程序单元的活动记录链 控制链 动态链 程序单元的活动记录按它们的生成 或调用 次序串成链 实在参数 返回值 2020 3 1 编译原理与技术 运行环境 7 活动记录的内容 返回值 returnvalue 实在参数 actualparameter 控制链 controllink 可选的访问链 optionalaccess staticlink 机器状态 savedmachinestatus 局部数据 localdata 临时区 temporaries 2020 3 1 编译原理与技术 运行环境 8 活动记录内容的存取 返回值实在参数控制链 oldbp 可选的访问链机器状态局部数据临时区 ar的基地址bp 2020 3 1 编译原理与技术 运行环境 9 活动记录内容的存取 返回值实在参数控制链 oldbp 可选的访问链机器状态局部数据临时区 bp 偏移 d1 偏移d2 地址 bp d1 地址 bp d2 d1 d2谁正谁负 2020 3 1 编译原理与技术 运行环境 10 静态存储分配 全局变量的存储绑定 ar均在编译时确定且在整个程序执行中保持 不支持 1 动态数据结构2 过程递归调用 实现静态分配的语言 早期 fortran 2020 3 1 编译原理与技术 运行环境 11 callsubsubroutinesubcallsubdatai 10endwrite ii 100end第一次调用sub 输出10第二次调用sub 输出100 e g 1fortran静态存储分配 第一次调用前 第一次调用后 第二次调用后 2020 3 1 编译原理与技术 运行环境 12 动态存储分配 栈式分配 ar在过程被调用 激活 时才在栈 stack 上分配 而在被调用过程 返回 终止时从栈上撤销 过程中 非静态 局部变量的存储绑定在过程执行时有效 过程终止时失效 支持过程递归调用 每次递归调用时 局部变量绑定到不同的存储 2020 3 1 编译原理与技术 运行环境 13 动态存储分配 栈式分配下的ar内容布局 返回值实在参数可选的访问链返回地址调用者bp可选机器状态局部数据临时区 bp 高地址 低地址 长度固定的区域放在ar中间 长度可变的区域放在ar低端 参数 返回值区域放在ar高端 靠近调用者过程的活动记录 既便于双方存取 又适应参数可变情况 栈顶sp 2020 3 1 编译原理与技术 运行环境 14 栈式分配下的过程调用与返回 过程调用 分配被调过程的ar并填入相关信息 然后程序控制转移到被调过程入口 过程a调用过程b的过程调用序列 a的 调用 准备操作 1 3 1 a计算实在参数并放入 对应栈操作 push b的活动记录中 亦可考虑返回值存放空间 2 a将可选的访问链放入 push b的活动记录 3 a将返回地址放入b的活动记录并跳转到过程b的代码入口 开始b的执行 一般通过a中的代码指令 callb 来完成这一步 4 2020 3 1 编译原理与技术 运行环境 15 栈式分配下的过程调用与返回 过程a调用过程b的过程调用序列 b的入口代码 4 6 4 在b自己的ar中保存a的活动记录的基址 即当前bp 对应操作pushbp 并且将这个位置作为b自己ar的基址 对应操作 movsp bp即bp sp 5 保存可选的机器状态 寄存器 6 为局部数据分配空间 对应操作 sublocal size sp 即sp sp local size7 开始 b的执行 至此 b的ar建好 2020 3 1 编译原理与技术 运行环境 16 栈式分配下的过程调用与返回 过程返回 回收分配的被调过程的ar 并将程序控制转移回调用过程继续执行 过程a调用过程b的过程返回序列 b的出口代码 1 2 1 b回收局部数据空间 恢复原先保存的机器状态2 b恢复a的ar基址 取出返回地址将程序控制交回到a 对应操作 movbp spsp bppopbp 恢复调用者a的bpret b执行结束并返回注 x86 linux中的leave和ret组合亦能达到目的 至此 b的ar中除了参数 返回值区域 其余区域全部回收 撤销 了 2020 3 1 编译原理与技术 运行环境 17 栈式分配下的过程调用与返回 过程a调用过程b的过程返回序列 a的 调用 善后代码 3 4 3 a取回返回值以及引用型参数 有的话 4 a调整栈顶sp 主要根据参数个数以及可能有的访问链和可能有的返回值 对应操作 addpara size sp即sp sp para size至此 b的ar区域全部回收 撤销 了 2020 3 1 编译原理与技术 运行环境 18 e g 2栈式存储分配 有c程序如下 voidg inta a 10 voidh inta a 100 g main inta 1000 h 2020 3 1 编译原理与技术 运行环境 19 过程g被调用时 活动记录栈的 大致 内容 e g 2栈式存储分配 返回地址 oldbp a 1000 main程序的ar 返回地址 oldbp a 100 函数h的ar 返回地址 oldbp a 10 函数g的ar bp sp 2020 3 1 编译原理与技术 运行环境 20 e g 3有参函数的活动记录 voidfunc inta intb intc d c a d b bp bp 8 bp 12 bp 4 bp 8 file ar c text globlfunc typefunc functionfunc pushl ebpmovl esp ebpsubl 8 espmovl8 ebp eaxmovl eax 4 ebp movl12 ebp eaxmovl eax 8 ebp leaveret 2020 3 1 编译原理与技术 运行环境 21 有如下c程序 main inti floatf intj scanf d f e g 4 scanf的可变参数 2020 3 1 编译原理与技术 运行环境 22 e g 4 scanf的可变参数 f i 格式串1指针 返回地址 老bp j 格式串2指针 返回地址 老bp scanf的第一次调用时ar scanf的第二次调用时ar 由于c语言采用逆序传递参数 格式串参数将被放在ar中的 固定 位置 即bp 8 而由此参数即可确定待输入值的参数 变量 的个数 从而适应参数个数变化的情况 bp bp 8 2020 3 1 编译原理与技术 运行环境 23 e g 5悬空引用 有c程序如下 main int dangle int p dangle inti return 2020 3 1 编译原理与技术 运行环境 24 非局部变量访问 静态作用域规则vs 动态作用域规则 最接近嵌套 vs 现行单元活动 调用次序 分程序 含有声明和语句 如c的 分程序具有以下特征 可以嵌套 没有参数 控制流沿静态文本进入 流出 采用 最接近嵌套 的规则 2020 3 1 编译原理与技术 运行环境 25 非局部变量访问 e g 6分程序main inta 0 intb 0 localvarofmain intb 1 block1 inta 2 printf d d n a b block2 intb 3 printf d d n a b block3 printf d d n a b printf d d n a b 2020 3 1 编译原理与技术 运行环境 26 分程序的实现 1 按无参过程方式来实现 控制流进入分程序时 在栈上分配局部变量空间 退出时撤销上述空间 e g 6中各变量存储如下 a0 0 b0 0 b1 1 a 进入block1 未进入block2 b 进入block2 未进入block3 a1 2 a0 0 b0 0 b1 1 c 退出block2 进入block3 b2 3 a0 0 b0 0 b1 1 d 退出block3 进入block1 a0 0 b0 0 b1 1 e 退出block1 进入main a0 0 b0 0 2020 3 1 编译原理与技术 运行环境 27 分程序的实现 2 按过程为单位统一分配 将分程序中的局部变量独立地看成过程的局部变量 e g 6中各变量存储如下 两种方案 a0 0 b0 0 b1 1 a a1和b2将先后被分配在同一空间 因为它们的生存期 作用域 不重叠 不嵌套 a1 2 b2 3 a0 0 b0 0 b1 1 b a1和b2将被分配在不同的空间 a1 2 b2 3 2020 3 1 编译原理与技术 运行环境 28 programdynamic static link procedurea vari integer procedureb varj integer procedurec beginb end beginj i c end beginb end begina end 过程嵌套定义语言中非局部名字访问 c b a 主程序 主程序 0 a 1 b 2 c 3 i 2 j 3 嵌套深度 1 嵌套深度 2 嵌套深度 3 嵌套深度 4 e g 7嵌套的过程定义 2020 3 1 编译原理与技术 运行环境 29 过程嵌套定义语言中非局部名字访问 设嵌套深度的初值为0 在 读过 程序单元的名字后 进入程序单元 过程或函数时嵌套深度加1 任何名字 包括变量名和程序单元 过程或函数的名字 的嵌套深度是包围该名字声明或定义的最内层的程序单元体 body 所在的嵌套深度 过程或函数的参数与其局部声明的嵌套深度相同 2020 3 1 编译原理与技术 运行环境 30 使用静态访问链来存取非局部名字非局部变量a的嵌套深度为na 而该变量的使用或引用点的嵌套深度为np 沿当前过程或函数的访问链追踪 np na 次 即可到达包含变量a的过程或函数的活动记录 进一步可存取变量a 运行时栈上操作如下 1 bp 访问链单元的偏移 reg 追踪1次2 reg 访问链单元的偏移 reg 追踪2次 追踪 np na 次最后 通过 reg 变量a的偏移 来存取变量a 局部变量访问无需追踪访问链 e g 7中下划线部分 j i为非局部名字i的一个引用 j为局部变量 为此 需要追踪过程b的访问链1次即可到达过程a的ar从而获取i的值 由定义非局部变量a的过程或函数 名 的嵌套深度 以及由使用该变量的过程或函数 名 的嵌套深度 也能计算出追踪访问链的次数 why 2020 3 1 编译原理与技术 运行环境 31 过程嵌套定义语言中非局部名字访问 访问链的建立在嵌套深度为np的过程x调用嵌套深度为na的过程y 1 np na此时np na 1 即调用者x是父 即最接近的外围 过程 而被调者y为其子过程 这时将过程y的ar中的访问链置为x的ar的基址 对应的运行时栈的操作 pushbp 调用者 父过程 将自己的bp压入栈 2020 3 1 编译原理与技术 运行环境 32 过程嵌套定义语言中非局部名字访问 访问链的建立2 np na这属于内层过程x调用外围过程y 或者两个兄弟过程x y之间的调用 也可能是相同过程 即递归的情况 这时由x的ar追踪访问链 np na 1 次 即可到达嵌套深度为 na 1 的过程z的ar 显然 过程z是过程y的父过程 将这个z的ar的基址填入y的访问链域 对应运行时栈上的操作 1 bp 访问链单元的偏移 reg 追踪1次2 reg 访问链单元的偏移 reg 追踪2次 追踪 np na 1 次最后 pushreg 过程z的活动记录基址入栈 2020 3 1 编译原理与技术 运行环境 33 e g 7嵌套的过程定义 过程的调用次序主程序 a b c b1 过程b第一次被过程c调用时 c需追踪2次访问链才能为找到过程b1的父过程a的ar 具体如下 2020 3 1 编译原理与技术 运行环境 34 控制链 bp 系统 主程序ar e g 7嵌套的过程定义 运行时栈 主程序 2020 3 1 编译原理与技术 运行环境 35 控制链 bp 系统 访问链 bp main 返回地址1 控制链 bp main 局部名字 i 主程序ar 过程a的ar e g 7嵌套的过程定义 运行时栈 主程序 a主程序负责建立a 活动记录中 的访问链 此时该链指向主程序运行时的活动记录 why 此访问链的位置 或偏移 是多少 访问链的地址表示 bp 8在此活动记录中的偏移为8 2020 3 1 编译原理与技术 运行环境 36 控制链 bp 系统 访问链 bp main 返回地址1 控制链 bp main 访问链 bp a 返回地址2 控制链 bp a 局部名字 i 局部名字 j0 主程序ar 过程a的ar 过程b的ar e g 7嵌套的过程定义 运行时栈 主程序 a bb中语句j i如何执行的 j i执行如下 取过程a的活动记录地址 bp 8 r取a中局部变量i的值 r 4 r将该值赋给b的局部变量j r bp 4 2020 3 1 编译原理与技术 运行环境 37 控制链 bp 系统 访问链 bp main 返回地址1 控制链 bp main 访问链 bp a 返回地址2 控制链 bp a 局部名字 i 局部名字 j0 访问链 bp b 返回地址3 控制链 bp b 主程序ar 过程a的ar 过程b的ar 过程c的ar 运行时栈 主程序 a b c 控制链 bp 系统 访问链 bp main 返回地址1 控制链 bp main 访问链 bp a 返回地址2 控制链 bp a 局部名字 i 局部名字 j0 访问链 bp b 返回地址3 控制链 bp b 访问链 bp a 返回地址4 控制链 bp c 局部名字 j1 主程序ar 过程a的ar 过程b的ar 过程c的ar 过程b的ar 1 2 运行时栈 主程序 a b c b1 过程c为过程b1建立访问链 1 bp 8 r2 r 8 r3 pushr 2020 3 1 编译原理与技术 运行环境 39 参数传递 实参与形参 存储单元 左值 存储内容 右值 根据所传递的实参的 内容 参数传递可分为 传值调用 传递实参的右值到形参单元 引用调用 传递实参的左值到形参单元 值 结果调用 传递实参的右值 在控制返回时将右值写回到实参相应左值单元 如果有的话 换名调用 传递实参的 正文 2020 3 1 编译原理与技术 运行环境 40 e g 8参数传递 procedureswap a b a b int temp int begintemp a a b b temp end 讨论下面程序在不同参数传递方式下输出 1 x 10 y 20 swap x y print x y 2 i 10 a i 20 swap i a i print i a i 2020 3 1 编译原理与技术 运行环境 41 e g 8参数传递 讨论下面程序在不同参数传递方式下输出 1 x 10 y 20 swap x y print x y 10 5000 x 20 4000 y 2004 a 2000 b 1990 temp 实参x y和过程swap中形参a b 和局部数据temp的存储分布示意 2020 3 1 编译原理与技术 运行环境 42 e g 8参数传递 传值调用 过程调用 swap x y 传参 形 实结合 10 5000 x 20 4000 y 2004 a 2000 b 1990 temp 10 20 2020 3 1 编译原理与技术 运行环境 43 e g 8参数传递 传值调用 过程调用 swap x y 过程执行temp a 10 5000 x 20 4000 y 10 2004 a 20 2000 b 10 1990 temp 2020 3 1 编译原理与技术 运行环境 44 e g 8参数传递 传值调用 过程调用 swap x y 过程执行a b 10 5000 x 20 4000 y 20 2004 a 20 2000 b 10 1990 temp 2020 3 1 编译原理与技术 运行环境 45 e g 8参数传递 传值调用 过程调用 swap x y 过程执行b temp 10 5000 x 20 4000 y 20 2004 a 10 2000 b 10 1990 temp 2