当前位置:首页 > 服务端 > 【Static Program Analysis

【Static Program Analysis

 

【Static Program Analysis _ JavaClub全栈架构师技术笔记

(a) an if-then-else

(b) a while loop

(c) a natural loop with two exits, e.g. while with an if...break in the middle; non-structured but reducible

(d) an irreducible CFG: a loop with two entry points, e.g. goto into a while or for loop


 

控制流图是代码的一种表征形式。

wiki:

Definition

In a control flow graph each node in the graph represents a basic block, i.e. a straight-line piece of code without any jumps or jump targets; jump targets start a block, and jumps end a block. Directed edges are used to represent jumps in the control flow. There are, in most presentations, two specially designated blocks: the entry block, through which control enters into the flow graph, and the exit block, through which all control flow leaves.[3]

Because of its construction procedure, in a CFG, every edge A→B has the property that:

outdegree(A) > 1 or indegree(B) > 1 (or both). [4]

The CFG can thus be obtained, at least conceptually, by starting from the program's (full) flow graph—i.e. the graph in which every node represents an individual instruction—and performing an edge contraction for every edge that falsifies the predicate above, i.e. contracting every edge whose source has a single exit and whose destination has a single entry. This contraction-based algorithm is of no practical importance, except as a visualization aid for understanding the CFG construction, because the CFG can be more efficiently constructed directly from the program by scanning it for basic blocks.[4]

Example

Consider the following fragment of code:

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0
2: (B) print t0 + " is even."
3: (B) goto 5
4: (C) print t0 + " is odd.”           [jump targets]
5: (D) end program                    [jump targets]
In the above, we have 4 basic blocks:

A from 0 to 1,      [entry block]

B from 2 to 3,      

C at 4,

D at 5.                 [exit block]

A graph for this fragment has edges from A to B, A to C, B to D and C to D.

Reachability

Reachability is a graph property useful in optimization.

If a subgraph is not connected from the subgraph containing the entry block, that subgraph is unreachable during any execution, and so is unreachable code; under normal conditions it can be safely removed.

If the exit block is unreachable from the entry block, an infinite loop may exist. Not all infinite loops are detectable, see Halting problem. A halting order may also exist there.

Unreachable code and infinite loops are possible even if the programmer does not explicitly code them: optimizations like constant propagation and constant folding followed by jump threading can collapse multiple basic blocks into one, cause edges to be removed from a CFG, etc., thus possibly disconnecting parts of the graph.

Domination relationship

A block M dominates a block N if every path from the entry that reaches block N has to pass through block M. The entry block dominates all blocks.

In the reverse direction, block M postdominates block N if every path from N to the exit has to pass through block M. The exit block postdominates all blocks.

It is said that a block M immediately dominates block N if M dominates N, and there is no intervening block P such that M dominates P and P dominates N. In other words, M is the last dominator on all paths from entry to N. Each block has a unique immediate dominator.

Similarly, there is a notion of immediate postdominator, analogous to immediate dominator.

The dominator tree is an ancillary data structure depicting the dominator relationships. There is an arc from Block M to Block N if M is an immediate dominator of N. This graph is a tree, since each block has a unique immediate dominator. This tree is rooted at the entry block. The dominator tree can be calculated efficiently using Lengauer–Tarjan's algorithm.

postdominator tree is analogous to the dominator tree. This tree is rooted at the exit block.

Special edges

back edge is an edge that points to a block that has already been met during a depth-first (DFS) traversal of the graph. Back edges are typical of loops.

critical edge is an edge which is neither the only edge leaving its source block, nor the only edge entering its destination block. These edges must be split: a new block must be created in the middle of the edge, in order to insert computations on the edge without affecting any other edges.

An abnormal edge is an edge whose destination is unknown. Exception handling constructs can produce them. These edges tend to inhibit optimization.

An impossible edge (also known as a fake edge) is an edge which has been added to the graph solely to preserve the property that the exit block postdominates all blocks. It cannot ever be traversed.

Loop management

loop header (sometimes called the entry point of the loop) is a dominator that is the target of a loop-forming back edge. The loop header dominates all blocks in the loop body. A block may be a loop header for more than one loop. A loop may have multiple entry points, in which case it has no "loop header".

Suppose block M is a dominator with several incoming edges, some of them being back edges (so M is a loop header). It is advantageous to several optimization passes to break M up into two blocks Mpre and Mloop. The contents of M and back edges are moved to Mloop, the rest of the edges are moved to point into Mpre, and a new edge from Mpre to Mloop is inserted (so that Mpre is the immediate dominator of Mloop). In the beginning, Mpre would be empty, but passes like loop-invariant code motion could populate it. Mpre is called the loop pre-header, and Mloop would be the loop header.

 






 

作者:max_xbw
来源链接:https://www.cnblogs.com/XBWer/p/7910997.html

版权声明:
1、Java侠(https://www.javaxia.com)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。





本文链接:https://www.javaxia.com/server/125366.html

分享给朋友:

“【Static Program Analysis” 的相关文章

[C++]VC自定义发IP包例子2022年05月17日 20:41:27
常用日志框架介绍2022年05月19日 20:04:06
多线程编程(1)2022年05月20日 21:26:51
Python 查找算法2022年05月20日 21:28:36
python中循环的技巧2022年05月23日 21:49:36
软件工程专业如何就业!2022年05月23日 22:31:42
信息系统项目管理案例22022年05月24日 22:36:24