安徽理工大学：《算法设计与分析 Algorithm Design and Analysis》课程教学资源（PPT课件讲稿）第6章 代码最优化

6.代码最优化

6.代码最优化

背景知识 二叉树遍历算法的应用递归遍历算法 先序遍历（根左右） 根右左 中序遍历（左根右） 右左根 后序遍历（左右根） 左右根 类后序遍历解决问题 涵

背景知识 ▪ 二叉树遍历算法的应用 递归遍历算法 ▪ 先序遍历（根左右） ▪ 中序遍历（左根右） ▪ 后序遍历（左右根） ▪ 类后序遍历解决问题 根右左 右左根 左右根

代码最优化问题描述 将给定算术表达式翻译成汇编语言代码， 如何翻译得到最优编码？ 汇编语言特点：面向机器的低级语言，机 器不同，汇编语言指令系统不同， 因此针对不同的机器研究算术表达式的最 优化编码问题

一、代码最优化问题描述 ▪ 将给定算术表达式翻译成汇编语言代码， 如何翻译得到最优编码？ ▪ 汇编语言特点：面向机器的低级语言，机 器不同，汇编语言指令系统不同， ▪ 因此针对不同的机器研究算术表达式的最 优化编码问题

模型机A下的最优化代码 模型机A结构如下： 一个累加寄存器R 指令系统包括： >存入指令：store M;将寄存器R的值存入存储单元M > 装入指令：load M;将存储单元M的值存入寄存器R 算术运算指令：opM;R⊙MR ■其中，⊙可以是：add(+),sub(-),mul(*),div(I)

•模型机A下的最优化代码 ▪ 模型机A结构如下： ▪ 一个累加寄存器R ▪ 指令系统包括： ➢ 存入指令：store M；将寄存器R的值存入存储单元M ➢ 装入指令：load M；将存储单元M的值存入寄存器R ➢ 算术运算指令：op M；R⊙M→R  其中，⊙可以是：add （+），sub（-），mul（*），div（/）

例1(a+b)(c+d)的两段代码 2 LOAD a LOAD ADD b ADD d ■ STORE T1 STORE T1 LOAD C ■ LOAD a ADD d ■ ADD b STORE T2 DIV T1 LOAD T1 DIV T2

例1 (a+b)/(c+d)的两段代码 ▪ LOAD a ▪ ADD b ▪ STORE T1 ▪ LOAD c ▪ ADD d ▪ STORE T2 ▪ LOAD T1 ▪ DIV T2 ▪ LOAD c ▪ ADD d ▪ STORE T1 ▪ LOAD a ▪ ADD b ▪ DIV T1 1 2

定义6.1表达式E翻译成某给定机器语言或 汇编语言是最优的，当且仅当这一翻译有 最少的指令条数。 对于(a+b)(c+d)显然第二段代码更优。 影响表达式指令长度的因素？

▪ 定义6.1表达式E翻译成某给定机器语言或 汇编语言是最优的，当且仅当这一翻译有 最少的指令条数。 ▪ 对于(a+b)/(c+d)显然第二段代码更优。 ▪ 影响表达式指令长度的因素？

例2a+b*c的两段代码 2 LOAD LOAD MPY MPY ■ STORE T1 ADD ■ LOAD a ADD T1 利用了加法的交换律 利 b*c+a 吉郎

例2 a+b*c的两段代码 ▪ LOAD b ▪ MPY c ▪ STORE T1 ▪ LOAD a ▪ ADD T1 ▪ LOAD b ▪ MPY c ▪ ADD a 1 2 利用了加法的交换律 b*c+a

例3a*b+c*b的两段代码 1 2 ■ LOAD LOAD MPY b ADD STORE T1 MPY LOAD a MPY b ADD T1 利用了运算的分配律 (a+c)*b=a*b+c*b

例3 a*b+c*b的两段代码 ▪ LOAD c ▪ MPY b ▪ STORE T1 ▪ LOAD a ▪ MPY b ▪ ADD T1 ▪ LOAD a ▪ ADD c ▪ MPY b 1 2 利用了运算的分配律 （a+c）*b=a*b+c*b

例4a*(b*c)+d*c的两段代码 2 LOAD LOAD MPY MPY b STORE T1 ADD LOAD a MPY T1 MPY STORE T1 LOAD d 利用了运算的结合律和 MPY c 分配律 STORE a*(b*c)+d*c LOAD T1 =(a*b)*c+d*c ADD T2 =(a*b+d)*c

例4 a*(b*c)+d*c的两段代码 ▪ LOAD b ▪ MPY c ▪ STORE T1 ▪ LOAD a ▪ MPY T1 ▪ STORE T1 ▪ LOAD d ▪ MPY c ▪ STORE T2 ▪ LOAD T1 ▪ ADD T2 ▪ LOAD a ▪ MPY b ▪ ADD d ▪ MPY c 1 2 利用了运算的结合律和 分配律 a*(b*c)+d*c =(a*b)*c+d*c =(a*b+d)*c

影响表达式代码长度的因素 1.表达式本身的长度 2.表达式中运算的可交换交换律 3.表达式中运算的可分配性分配律 4.表达式中运算的可结合性-结合律 晶 >其中：+-*/，运算中，加法和乘法具有交换 分配和结合性 一

影响表达式代码长度的因素 1. 表达式本身的长度 2. 表达式中运算的可交换-----交换律 3. 表达式中运算的可分配性-----分配律 4. 表达式中运算的可结合性------结合律 ➢ 其中：+ - * /,运算中，加法和乘法具有交换、 分配和结合性