过程间稀疏条件类型传播

主要观点:在动态语言 Ruby 中构建有效编译器需精确类型信息,文中展示了对一小部分 Ruby 子集的过程间类型分析,可用于程序优化,此分析非通常的类型推断引擎或检查器,而是跟踪函数间数据流,能识别shout的所有调用者及参数类型等,还介绍了静态单赋值(SSA)形式、有限高度格等概念,以及通过增加调用站点敏感度等可提高分析精度但会降低速度,测试了不同情况下的分析规模和性能等。
关键信息:

  • 定义shout函数,不知obj类型及shout返回类型,添加类型注解作用有限。
  • 分析 SSA 形式,变量在不同逻辑执行时间可能有不同类型,如aInteger[1]变为String["hello"]
  • 常量折叠在某些条件下可行,如在封闭世界假设下可折叠常量,否则不行。
  • SCCP 利用类型信息探索控制流图,可减少分析分支,提高精度。
  • 介绍过程间 SCCP,从应用入口点逐步构建调用图,跟踪参数类型等。
  • 讨论敏感度,如调用站点敏感度和上下文敏感度,增加敏感度会降低分析速度。
  • 处理 Ruby 中的对象和方法查找,选择字段敏感方法跟踪实例变量类型。
  • 生成“折磨测试”来评估分析的扩展性,包括有类和无类的程序测试。
  • 有类程序分析在 2.5 秒内完成,无类程序在 1.3 秒内完成,增加敏感度可能降低速度但分析仍较可行。
    重要细节:
  • 代码中各种函数定义及调用示例,如decisions函数等。
  • 关于有限高度格的图示及解释。
  • 生成“折磨测试”程序的详细过程,包括生成有向无环图(DAG)等。
  • 不同敏感度下的分析步骤对比等。
阅读 6
0 条评论