分享

耽误了一些时间，很抱歉。这里是全文：程序分析-原理部分(全)。

程序分析最传统、可能也是最重要的应用应该在编译优化。有关编译的材料,网上相当 多,其中最权威的包括龙书、虎书、鲸书和Rice出的那本Optimizing Compilers for Modern Architectures。龙书和虎书覆盖编译了很多基础方面,部分章节也讨论优化;而 后两者专門讲优化,程序分析的大部分内容其实都涉及到了。从编译的角度,这份材料可 以作为补充参考,此外这門课在两个方面还有点特色:(1) 对程序分析的体系梳理比较到 位,内容几乎都很直观,便于理解。可以看完这个材料再去看那几本书,很多内容会更清 晰;(2) 这門课的授课老师Ben Hardekopf在指针分析领域有几个重要的工作,对指针分 析介绍得比较全面深入。

这份材料主要的对象是那些对程序分析感兴趣但还没有找到合适材料的同仁。说实话,能 把这个领域的主要内容压缩在几十页的篇幅自己也有点惊讶,然而事实就是如此。有些内 容如果感兴趣希望扩展阅读,后面也列出的重要的参考文献。程序分析是一个相当大的领 域,发表的文章可谓浩如烟海,通过浓缩的方式把精要梳理出来,把重要的文献整理出 来,相信能帮助节省很多自己摸索的时间。通过这份材料或许能给你的工具箱添加一个新 的探索问题的工具。

必须说明这份材料仅仅只是笔记,里面的贴图都来自课程的ppt(网上可以下载)。由于水 平有限可能有错误之处,建议结合ppt对照使用。由于这个领域很大,相信有很多内容没 有涉及到,因此这个文档没有写完,只是由于自身能力局限,只能写到这里。恳请知道更 多内容且有时间的同仁继续补充,最终给大家提供一份这个领域比较全面的资料。

整个材料的提纲如下:

1导言

2 控制流分析

3 数据流分析

4 稀疏分析和SSA

5 指针分析

6 过程间分析

7 集合约束和Andersen Style指针分析

8 类型约束和Steensgaard指针分析

分享

分享

1 导言

1.1 缘起及基本发展

程序分析是一种自动推导程序运行行为的技术，起源于早期以Fortran为代表的高级语言的编译优化需求。计算机的早期发展阶段主要采用接近机器的汇编语言编程。当高级语言最初被引入时，由于当时编译器无法产生高效的代码，高级语言编程的想法曾经受到广泛的质疑，然而以程序分析为基础的编译优化技术随后得到长足发展，高级语言在大多数应用领域取代汇编语言成为人们的常识。编译优化只是程序分析的一种重要应用，程序分析基本思想现已应用到程序安全验证、软件工程、电路综合、操作系统(如微软Singularity项目)以及GPU编程等应用领域。表1.1列举了一些程序分析的应用实例。

表1.1 程序分析举例

1.2 Lingo语言

为了将后续的程序分析技术落实，这里引入一个基本的语言，定义如图1.1所示。首先符号集合的定义，n表示整数集中的元素，b是布尔值(true/false)，x表示程序变量。基本表达式操作符包括算术运算符(+,-,*,/)、关系操作符(<,<=,=,!=)和逻辑运算操作符(&&和||)。表达式包括整数或布尔常量、变量或者各种运算表达式。基本语句包括输入、赋值、NOP(Skip)、循环、选择，此外还定义了语句的组合方法(c;c)，最后一个程序(Prog)就是一个语句(Cmd)。

相对于实际的语言如C，Lingo要简单得多。注意关系操作符中没有>，另外只有两种数据类型(int和bool)，且不支持显式或隐式类型转换。变量定义默认初始化为0/false，除法假设有理想精度。后续为便于讨论各种分析技术还会增加指针和函数调用两种语言特性。

图1.1 Lingo语言定义

下图1.2给出了一个Lingo的例子程序，直观上很快就给出常量传播(程序中哪些位置的哪些变量肯定是常量?)和死代码检查(哪些语句肯定不会被执行?)的分析结果。可见程序分析来源于程序员理解程序时的经验直觉，经验和直觉只有经过升华才会成为具有一定普适性的指导原则，从后续要陆续展开的各种分析框架可以感受到这一点。写小说的强调要源于生活并高于生活，人类其他学科依然，只是演绎的基本思维元素不同。

图1.2 Lingo程序举例

1.3 程序语义模型

既然程序分析是提取和挖掘程序行为，因此首要问题是如何严格界定程序行为。有三大类程序语义模型：基于符号的(denotational)、基于抽象操作(operational)和公理化(Axiomatic)证明。符号模型和公理化证明不知为何物，抽象操作模型则相对直观，基本思想是给定一个程序，设想有一个抽象的虚拟机来执行之，依据不同的输入理论上可能得到无穷个执行轨迹(trace)，每条轨迹对应程序一种可能的运行状态，那么所有执行轨迹的状态总和就构成程序所有可能的行为。

从程序抽象执行轨迹出发来理解程序行为还被用到了其他地方。这里考察的是同一个程序因输入不同可能出现的无穷多执行轨迹，还有一个角度是考察在一台机器(SMP/Multi-core)上运行的多线程程序各个线程间指令的可能交错(interleave)情况，在线程间存在数据竞争的情况下，不同的interleave可能得到不同的执行结果，执行结果对或错的标准由内存模型来界定。尽管解决的问题不同，二者背后都利用了可以设想抽象虚拟机来枚举程序行为这一直觉。

有了虚拟机，那么给定输入，在任意程序点机器的状态就确定了。这里程序点直观上可以理解为程序中语句的位置，如图1.2示例代码中红色数字标识的位置，也就是程序计数器(PC)指向的地址。虚拟机的状态可以用给定PC位置当前所有变量和值的映射关系来描述，如图1.3的定义所示：

图1.3 给定程序点虚拟机状态

给定程序输入，抽象虚拟机模拟执行每条指令就能得到每个程序点的机器状态。图1.4给出了图1.2所示的程序执行到程序点3并推进到5的机器状态：

图1.4 机器状态求解过程示例

如果已知虚拟机在每个程序点的状态，那么每步求解过程合起来就构成了程序的执行轨迹。由这种以虚拟机为基础的操作语义出发，给定一个程序理论上可以分析出所有可能的合理(valid)执行轨迹，从而得到程序所有可能发生(may possibly do)或一定发生(must always do)的行为集合。

1.4 程序分析评价指标

对于很多应用场景，程序分析依据一组约束分析用户关注的局部程序行为，但静态程序分析结果经常是不可判定的，如图1.5所示：

图1.5 程序分析结果的不可判定

图1.5中if语句之后变量x的值是未知，因为有多条路径都可能会修改，在这种情况下程序分析时只能一定程度去近似程序的实际行为，具体有三种操作方式：

1. Sound analysis，对变量的可能取值进行保守假设(over approximation)，如指出变量x取值范围是{0,1}，尽管实际执行结果只会是0。这种情况不会出现误杀，讲究尽可能提高分析的取值范围精度；
2. Complete analysis，和sound analysis相对，力求精确分析(under approximation)，宁信其无，不信其可能有，对图1.5的程序，分析结果变量x的取值范围是{}。这种情况会有误杀情况。
3. 最后一种是不提供正确性保证，对图1.5的程序，分析结果可能是变量x为0，而实际执行结果x可能为1。

后续内容只关注sound analysis。由于这类分析关注某个变量的可能取值范围，当精确分析不可能时，可以对变量值域进行一定抽象分类来分析其取值属性，如{Zero, Non-Zero, Maybe-Zero}、{Even, Odd, Either}等等。

分享

分享

今年秋天在UCSB旁听一门Program Analysis的课(课程主页：http://www.cs.ucsb.edu/~benh/cs290/),觉得Ben的课程风格很实在，从头到尾没有口水话，几乎是干货。回想之前对Program Analysis感兴趣却常常找不到合适的资料，而这个技术其实在很多方面都比较有用，因此想把这门课程记录下来的笔记陆续发出来，如果有朋友感觉有用，就没有白费一番介绍的力气了。

整个材料计划分两个部分：第一部分是文字内容，从课程材料转述Program Analysis的原理、基本算法。没什么高深的内容(common sense)，但不留心或许体会不到；第二部分是实践，基于Clang+LLVM这个production quality的框架把这些算法实现。希望不仅能提供一些材料，也有一些代码供参考之用。

文字部分提纲如下，基本按照课程思路来：

1 引言

2 控制流分析

3 数据流分析

4 Sparse 分析

5 指针分析

6 过程间分析

7 基于类型和约束的分析(type or constraint based analysis)

事先说明：这个系列仅仅是对UCSB CS290C这门课程的山寨，理解不到位甚至错误的地方，恳请指正。课程网站上的原始材料更有价值，对于悟性好动手能力的强的同学，网站上的材料或许已经足够，此文系列权当狗尾续貂。不管如何，希望能对一些人有用。

存在的疑问：

本次系第一次在弯曲这个平台投文，不清楚其中的规矩，更不知道这个系列是否适合放在这里，麻烦编辑告知。如果可以的话，我最近会把已经写好的部分内容放上来。

分享

分享

在分布式应用系统中，我们首先来做个半学术半胡扯的定义：分布式服务系统和分布式通信系统。

分布式服务系统：基于Client／Server架构的分布式应用系统，例如HTTP Based的互联网系统，云计算系统。

分布式通信系统：基于数据流的分布式应用系统，例如，高端路由器，交换机，防火墙等［广告位，请联系《弯曲评论》］

在上述两种分布式系统的分类中，分布式通信系统是发展比较慢，研究的力度也不太深入的一环。

这里面的主要原因是：

学术界的分布式计算的人更容易朝面向Client／Server的大规模分布式服务系统发展［或曰：混事］［注：例如Google，Facebook，腾讯，淘宝云等等。还有一批人会转到存储领域。

单纯分布式系统的人在通信系统方面的基础相对而言比较弱，而且学校离基本上不可能得到训练。教授们［不说叫兽了］也基本上只停留在文件系统，资源这些说抽象不抽象，说具体不具体的东东上。

那么，分布式通信系统与分布式服务系统的主要区别在哪里？？？

这个世界上，没事的时候在哪里瞎琢磨，并试图做出一个定义的人不多。

分布式服务系统的本质是： Distributed Computing for Persistant Data.

分布式通信系统的本质是： Distributed Computing for Transient Data.

推论：

分布式服务系统处理的就是分布式的磁盘，分布式的Block Data；是死数据；或者隔夜index才产生并分布，多个副本的数据。

分布式通信系统处理的就是分布式的流（Packet Stream）。而这个流是Transient（转眼就逝）的。是风吹竹林；雁过寒潭。

分布式服务系统的精华是对Block Data的分布，负载平衡，容错的把握。

分布式通信系统的精华是对Packet Stream的迅速处理，并Switching［不想用转发这个词，太土。Switching这个词太漂亮］。

分布式服务系统的并行计算必须被［需要呈现给用户的］资源透明性所牵制。

分布式通信系统的分布的目的主要就是并行计算，追求加速比。

那么，分布式通信系统最基本上的单元是什么？

。。。。。。

是Queue！

是的，所谓的分布式通信系统，其实就是分布的队列（Queue）系统

Distributed Queue！

这就应该是所有分布式通信系统的共性。

类似与，所有的分布式服务系统都逃脱不了一个概念的索引：RPC（Remote Procedure Call）。

理解了RPC，不管是云技术，还是雨计算，都能看的透。

理解了Queue，不管是路由器，交换机，防火墙，都TNND一回事。。。。。。

这里，年轻的大宋工程师需要注意的就是：从专业上而言，Distributed （System）是操作系统，或者高级操作系统的知识结构范畴；而Queue是网络系统，或者再大尾巴狼一点，是排队论或者随机过程的知识结构范畴。

Distributed Queue就是所谓交叉工程学的一个典型范例！

得其意，忘其形。

这就是做学问，做工程应该追求的上乘功夫。。。。。。

分享

分享

【陈怀临：这个年轻人很优秀。优秀的不仅仅是能把这些经典论文看完，而是还花心思翻译出来。他的博客是：银河里的星星。其联系方式是phylips@bmy】

分布式领域论文译序

sql&nosql年代记

海量数据的存储计算和查询

一．google论文系列

1.      google系列论文译序

2.      The anatomy of a large-scale hypertextual Web search engine

3.      面向星球的网络搜索：google集群架构

4.      GFS：google文件系统

5.      mapreduce: Simplied Data Processing on Large Clusters

6.      bigtable: A Distributed Storage System for Structured Data

7.      Chubby: The Chubby lock service for loosely-coupled distributed systems

8.      Sawzall:Interpreting the Data–Parallel Analysis with Sawzall

9.      Pregel: A System for Large-Scale Graph Processing

10.  Dremel: Interactive Analysis of WebScale Datasets

11.  Percolator: Large-scale Incremental Processing Using Distributed Transactions and Notifications

12.   MegaStore: Providing Scalable, Highly Available Storage for Interactive Services

13.   Case Study GFS: Evolution on Fast-forward

14.   Google File System II: Dawn of the Multiplying Master Nodes

google系列论文翻译集(合集)

二．分布式理论系列

00.    Appraising Two Decades of Distributed Computing Theory Research

0.      How to Build a Highly Available System Using Consensus

1.      分布式理论系列译序

2.      A brief history of Consensus_ 2PC and Transaction Commit

3.      拜占庭将军问题 –Leslie Lamport

4.      Impossibility of distributed consensus with one faulty process

5.      Leases：租约机制

6.      paxos made simple

7.      2pc-2阶段提交：Notes on Data Base Operating Systems –Jim Gray

8.      3pc-3阶段提交：NONBLOCKING COMMIT PROTOCOLS

9.      Life beyond Distributed Transactions:an Apostate’s Opinion

10.    A Comparison of the Byzantine Agreement Problem and the Transaction Commit Problem –Jim Gray

11.    Uniform consensus is harder than consensus

12.    Consensus on Transaction Commit –Jim Gray & Leslie Lamport

13.     Paxos Made Live – An Engineering Perspective

14.     Fast Paxos –Leslie Lamport

15.    The Part Time Parliament –Leslie Lamport

16.    Time Clocks  and the Ordering of Events in a Distributed System –Leslie Lamport

17.    Distributed Snapshots: Determining Global States of a Distributed System –Leslie Lamport

18.    Virtual Time and Global States of Distributed Systems

19.    Timestamps in Message-Passing Systems That Preserve the Partial Ordering

20.    Fundamentals of Distributed Computing:A Practical Tour of Vector Clock Systems

三．Sql&NoSql理论系列

0.      Towards Robust Distributed Systems：Brewer’s 2000 PODC key notes

1.      CAP理论

2.      Harvest, Yield, and Scalable Tolerant Systems

3.      Brewer’s conjecture and the feasibility of consistent, available, partition- tolerant web services

4.      BASE模型：BASE an Acid Alternative

5.      最终一致性

6.      可扩展性设计模式

7.      可伸缩性原则

8.       MapReduce：一个巨大的倒退

9.       The Five-Minute Rule20 Years Later(and How Flash Memory Changes the Rules)

10.       The Transaction Concept:Virtues and Limitations –Jim Gray

11.      NoSql生态系统

12.      scalability-availability-stability-patterns

四．基本算法和数据结构

1.      大数据量，海量数据处理方法总结

2.      大数据量，海量数据处理方法总结(续)

3.     Consistent Hashing And Random Trees

4.    Merkle Trees

5.    Scalable Bloom Filters

6.    Introduction to Distributed Hash Tables

7.    B-Trees and Relational Database Systems

8.    The log-structured merge-tree

9.    lock free data structure

10.    Data Structures for Spatial Database

11.    Gossip

12.    lock free algorithm

13.    The Graph Traversal Pattern

五．基本系统和实践经验

1.    Berkeley DB white paper

2.    Dynamo: Amazon’s Highly Available Key-value Store

3.    Cassandra – A Decentralized Structured Storage System

4.    PNUTS: Yahoo!’s Hosted Data Serving Platform

5.    Hive – A Petabyte Scale Data Warehouse Using Hadoop

5.    Benchmarking Cloud Serving Systems with YCSB

6.     Designs, Lessons and Advice from Building Large Distributed Systems –Jeff Dean

7. Challenges in Building Large-Scale Information Retrieval Systems –Jeff Dean

8.      Apache Hadoop Goes Realtime at Facebook

9.     Hadoop平台优化综述

六．其他辅助系统

1. The ganglia distributed monitoring system:design, implementation, and experience

2. Chukwa: A large-scale monitoring system

七．其他

Reflections on Trusting Trust –Ken Thompson

Who Needs an Architect?

Go To statements considered harmfull –Edsger W.Dijkstra

No Silver Bullet Essence and Accidents of Software Engineering –Frederick P. Brooks

分享

分享

Jeff Dean, 谷歌院士，业界大牛,他的成就就不多介绍了，大家可以网上查查，但凡Google引以为豪的几个系统架构都少不了他。本文是他在斯坦福演讲的Slides，谷歌的各类系统虽在Google Lab上些资料，但是由Jeff串讲一下也是受益匪浅，现Share给大家：

Youtube上有此次演讲的视频，大家可以去看看。

http://www.youtube.com/watch?v=ulBalk7Od-Q

分享