189 8069 5689

南京大学《软件分析》-02-IR-创新互联

2 - IR
  1. Compilers and Static Analyzers
  2. AST vs. IR （AST：抽象语法树，在语法分析、词法分析之后的中间表示。）
  3. IR: Three-Address Code (3AC)
  4. 3AC in Real Static Analyzer: Soot
  5. Static Single Assignment (SSA)
  6. Basic Block (BB)
  7. Control Flow Graphs (CFG)
Compilers

输入为 SourceCode

10年的兴隆台网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。成都全网营销的优势是能够根据用户设备显示端的尺寸不同，自动调整兴隆台建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联从事“兴隆台网站设计”,“兴隆台网站推广”以来，每个客户项目都认真落实执行。
  • Scanner - 词法分析-Lexical Analysis - 检查每一个单词（不一定是英文单词）- 里面用到了正则表达式（Regular Expression）- 最后生成Tokens作为语法分析的输入。
  • Parser - 语法分析 - Syntax Analysis - 检查单词之间的语法规则 - Context-Free Grammar（上下无关语法）- 最后生成AST（抽象语法树）。
  • Type Checker - 语义分析 - Sementic Analysis - 检查类型处理合理 - Attribute Grammar - 最后生成Decorated AST（装饰的抽象语法树）。
  • Translator - 翻译 - 最后生成IR（一般是指3D码）。
  • Code Generator - 代码生成器 - 最后生成机器码。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3BhLZcD4-1672029451488)(image_1.0ec8e307.png)]

AST vs. IR

  • AST

    • 表达层次比较高，与语法树非常贴合
    • 依赖于不同的语言
    • 适合快速的类型检查
    • 在控制流信息流分析

  • IR - (“3-address” form)

    • 表达层次比较低，与机器码相近，与汇编相近
    • 与语言相关性不强
    • 压缩且简洁
    • 包含控制流信息
    • 经常被考虑作为静态分析的基础
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uyClofWv-1672029451489)(image_2.6644520b.png)]
Intermediate Representation (IR)

3-Address Code 三地址码。引入临时变量，一般包含三个信息：

  • 名称
  • 常量
  • 编译临时变量

每种指令都有他们自己的三地址码。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JSvcLxJJ-1672029451489)(image_3.6be88b87.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mpkZOisi-1672029451490)(image_4.cdaeea2b.png)]

3AC in Real Static Analyzer: Soot

真实的三地址码，Java的IR，Jimple in Soot。

https://github.com/Sable/soot

Loop循环

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-teAgwV3d-1672029451490)(image_5.b64799b5.png)]
在这里面x和i在soot中，x被优化掉了。所以在三地址码中看到只有i。【又或者说是，i被优化掉了，仅存在一个x，是不是更加合理？】

Do-while 循环

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nAMAPvAh-1672029451490)(image_6.3265c0cb.png)]

Method Call

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3ACqLrVR-1672029451491)(image_7.6fe44518.png)]
前面的前几个变量（r0,r1,r2,r3）是Jimple翻译器用来临时使用的声明的变量，和一些需要用的变量的类型。

r0声明的是MathodCall3AC这个类型，this指向当前这个对象。

Class

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NjRxrsrI-1672029451491)(南京大学《软件分析》.assets/image-20221225180528861.png)]
在PL中，在引用一个变量的时候，它会将变量给加载进来。例如上图的

public static void()
{= 3.14;
    return;
}
Static Single Assignment (SSA)-可选

SSA是IR里面一种经典的转化模式。

  • 给每一个定义一个新的命名。
  • 传递新的变量名到后续的式子使用。
  • 一个变量只有一个精确的定义。
    在这里插入图片描述
    在这里插入图片描述
    以上PPT，针对x0和x1会引入φ（phi-function）这个函数进行统合。
    SSA有典型的特征：
  • 每一个变量（variable）都有自己的一个定义。
  • 如果要用多重的x，会引入一个φ函数。

为什么不SSA？

  • 可能太多φ函数。
Basic Block (BB)
  • 一个BB的入口一定是第一条指令。
  • 一个BB的出口一定是最后一条指令。
  • 满足以上两个条件之后的大的指令集合。

在这里插入图片描述

如何设计一个算法去生成BB块呢？

  • 确定每个BB的入口（Leader）
    • 程序当中的第一个指令是入口（Leader）
    • 任何跳转指令（jump/goto）的目标指令（target）
    • 紧跟在所有跳转指令的后面一条指令
  • 建立BB
    • 一个BB包括一个入口（leader）和Leader后面所有跟随的指令，知道遇到下一个Leader。

在这里插入图片描述

如何在BB基础上建立CFG？

添边。

Control Flow Graphs (CFG)

三地址码最终还是要转化为控制流图CFG。

添边的规则：

  • CFG的结点是BB。
  • 满足跳转指令：从A的结尾到B的开始，添边。
  • 不满足跳转指令的（紧接在跳转指令后的一条指令）需要添加一条边。
  • B紧接着A之后，添边。
    • 除非A的最后一条指令是一条无条件跳转指令（jmp/goto)
  • 将跳转到块替换跳转到指令是合理的。
  • 一个BB可以有多个前驱，也可以有多个后继。
  • 最后需要添加两个结点：Entry和Exit。
    • 入边（Entry）只有一个
    • 出边（Exit）可以有多个

在这里插入图片描述
在这里插入图片描述

小结

在这里插入图片描述

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


网页标题：南京大学《软件分析》-02-IR-创新互联
浏览路径：http://cdxtjz.cn/article/dsjjpo.html

其他资讯