사용자:Shinkt m/작업장

컴파일러(compiler) 디자인에서 정적 단일 배정 형식(static single assignment form) (종종 SSA form 혹은 SSA 라 축약) 이란 모든 변수들을 정확한 한번만 배정한 중간 언어 (intermediate representation)이다. 원래의 중간언어에 존재하는 모든 변수들은 모든 정의가 정의 소유의 version 을 가지기 위하여 version 에 분리 되어 진다 (새로운 변수들은 일반적으로 원래의 이름과 아래로 쓰인 이름으로 표현). SSA form 에서는 use-def chains 는 명시적이며 각각 단일 엘리먼트를 포함한다.

정적 단일 배정 은 1980년대 IBM 의 연구진인 Ron Cytron, Jeanne Ferrante, Barry Rosen, Mark Wegman, 그리고 Ken Zadeck 에 의해 개발 되었다.

함수형 언어 컴파일러에서 (Scheme, ML 그리고 Haskell와 같은 함수형 언어) continuation passing style (CPS) 는 일반적으로 C 혹은 Fortran 를 위한 컴파일러에서의 SSA 를 찾기를 위하여 사용 된다. SSA 와 CPS 는 형식적으로 같다. 그래서 하나의 관점에서 형식화된 최적화와 변환은 즉시 다른 것으로 적용 가능 하다.

이득[편집]

SSA 의 주요한 유용함은 변수들의 특성을 간소화 함으로서 어떻게 동시에 간소화와 컴파일러 최적화의 다양한 결과를 향상시키는 것을 할 것인가 이다. 예를 들어 이 코드 조각을 보자.

 y := 1
 y := 2
 x := y

우리는 첫번째 배정이 불필요 하다는 것을 알 수 있다. 그리고 세번째 x에 배정되는 y 의 값은 두번째 y에 배정된 것이 사용 되어 진다. 프로그램은 이것을 결정 짓기 위하여 reaching definition analysis 을 반드시 수행 해야 한다. 그러나 프로그램이 SSA form 이 있다면 둘다 즉각적으로 일어 난다.

 y₁ := 1
 y₂ := 2
 x₁ := y₂

SSA 의 사용에 의하여 활성화 되거나 강력한 향상을 갖는 컴파일러 최적화 알고리즘 :

SSA로 변환[편집]

평범한 코드를 SSA from 으로 바꾸는 것은 각 배정의 표적(target)을 새로운 변수로 대체 하는 간단한 것 이다. 그리고 변수의 각 사용을 도달(변수의) 끝의 변수 의"version"와 교체 하는 일이다. 예를 들어 다음의 control flow graph 를 고려해보자.:

우리는 "x $\leftarrow$ x - 3" 의 좌측의 이름을 변경 할 수 있으며, 다음으로 나오는 x 의 사용을 새로운 이름으로 바꿀 수 있으며, 프로그램은 이와 같은 것을 할 것이다. 우리는 새로운 변수 두개 (한번만 배정되는 변수 : x₁ 와 x₂) 를 만들어 SSA 에서 이것을 활용 할 것이다. 우리는 마찬가지로 모든 다른 변수들에 대해서도 아랫문자를 통해 ( x₂ 와 같은 표현법 ) 을 통해 차이점을 주고, 그리고 우리는 이것을 얻게 된다.:

우리는 한가지를 제외 하곤 어떤 정의가 어디에 참조되어 사용 되는 것인지 구해 낼수 있다 : 아래 블럭에 있는 y의 사용은 y₁ 혹은 y₂ 가 될 수 있다. 제어 흐름에 의존적이다. 그렇다면 우리는 어떤 변수를 사용 할지 어떻게 알수가 있는가?

답은 Φ (Phi) function 불리는 특별한 표현(statement) 을 마지막 블럭의 시작 부분에 더하는 것이다. 이 표현(statement) 은 y₁ 혹은 y₂ 의 선택에 따라 y 에 대한 새로운 정의(y₃)를 생성 할 것이다.:

이제 마지막 블럭의 y 의 사용은 간단히 y₃ 를 사용 한다. 그리고 어떤 흐름이던 옯바른 값을 포함 하고 있다. 당신은 이 시점에서 의문을 갖게 된다. 우리가 x 를 위한 Φ function을 추가 할 수 있을까? 정답은 아니다. 오직 x 의 한가지 version (x₂) 만이 이 위치에 도달 한다. 그래야 문제가 없다.

좀더 일반적인 같은 라인들은 (주어진 중재자 control flow graph) 어떻게 Φ functions 을 어느 곳에 삽입 하라고 말을 할 수 있을까? 그리고 어떤 변수들을 위해서 말인가? 이것은 어려운 질문이다. 그러나 효과적인 해결책 하나가 있다. dominance frontiers 라 불리어지는 개념을 사용한 계산을 통해 가능 하다.

주의: the Φ functions 는 실제로 구현되어지지 않는다. 대신에 그들은 메모리에 같은 위치(혹은 같은 레지스터에 위치 ) 의 모든 변수들(Φ function에 의해 함께 묶여진)의 값을 배치를 하기 위하여 컴파일러를 위한 단순한 표지 이다.

dominance frontiers 를 이용한 최소한의 SSA 계산[편집]

첫째, 우리는 dominator 라는 개념이 필요 하다.: 노드 A 의 통과 없이 노드 B 에 도달 불가능 하다면, '노드 A 는 control flow graph 에서 다른 노드 B 를 엄격하게 지배(dominate) 한다' 라 한다. 이것은 A에 어떤 코드가 존재하던 반드시 B 가 도달 가능 하다면 매우 유용하다. 우리는 A 가 엄격하게 B 를 지배 하거나 혹은 A와 B 가 같다면 'A 는 B 를 지배한다' 라 한다.

이제 우리는 지배 영역(dominance frontier)를 정의 할수 있다.: 만약 노드 B 를 엄격하게 지배하고 있지 않거나 B의 바로 전 블록의 약간을 지배 하고 있다면 (A 가 B의 바로 전 블록이라면) 노드 B 는 노드 A의 지배 영역(dominance frontier)에 있다. A의 관점에서, 이것들은 A를 거치지 않는 다른 제어 경로들 중에서 가장 빨리 출현하는 곳에 위치한 노드들이다.

지배 영역(Dominance frontiers) 들은 Φ functions 이 필요로 하는 정확한 곳을 획득 한다.: 만약 노드 A가 특정 값을 정의 한다면 그 정의 Dominance frontiers capture the precise places at which we need Φ functions: if the node A defines a certain variable, then that definition and that definition alone (or redefinitions) will reach every node A dominates. Only when we leave these nodes and enter the dominance frontier must we account for other flows bringing in other definitions of the same variable. Moreover, no other Φ functions are needed in the control flow graph to deal with A's definitions, and we can do with no less.

One algorithm for computing the dominance frontier set is:

for each node b
    if the number of predecessors of b ≥ 2
        for each p in predecessors of b
            runner := p
            while runner ≠ idom(b)
                add b to runner’s dominance frontier set
                runner := idom(runner)

Note: in the code above, a predecessor of node n is any node from which control is transferred to node n, and idom(n) is the immediate dominator of node n.

There is an efficient algorithm for finding dominance frontiers of each node. This algorithm was originally described in the paper "Efficiently computing static single assignment form and the control dependence graph", by R. Cytron, J. Ferrante, B. Rosen, M. Wegman and F. Zadeck, ACM Trans. on Programming Languages and Systems 13(4) 1991 pp.451–490. Also useful is chapter 19 of the book "Modern compiler implementation in Java" by Andrew Appel (Cambridge University Press, 2002). See the paper for more details.

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of Rice University describe an algorithm in their paper titled A Simple, Fast Dominance Algorithm. The algorithm uses well engineered data structures to improve performance.

Φ 함수들의 수를 축소한 변종[편집]

"Minimal" SSA inserts the minimal number of Φ functions required to ensure that each name is assigned a value exactly once and that each reference (use) of a name in the original program can still refer to a unique name. (The latter requirement is needed to ensure that the compiler can write down a name for each operand in each operation.)

However, some of these Φ functions could be dead. For this reason, minimal SSA does not necessarily produce the fewest number of Φ functions that are needed by a specific procedure. For some types of analysis, these Φ functions are superfluous and can cause the analysis to run less efficiently.

Pruned SSA[편집]

Pruned SSA form is based on a simple observation: Φ functions are only needed for variables that are "live" after the Φ function. (Here, "live" means that the value is used along some path that begins at the Φ function in question.) If a variable is not live, the result of the Φ function cannot be used and the assignment by the Φ function is dead.

Construction of pruned SSA form uses live variable information in the Φ function insertion phase to decide whether a given Φ function is needed. If the original variable name isn't live at the Φ function insertion point, the Φ function isn't inserted.

Another possibility is to treat pruning as a dead code elimination problem. Then, a Φ function is live only if any use in the input program will be rewritten to it, or if it will be used as an argument in another Φ function. When entering SSA form, each use is rewritten to the nearest definition that dominates it. A Φ function will then be considered live as long as it is the nearest definition that dominates at least one use, or at least one argument of a live Φ.

Semi-pruned SSA[편집]

Semi-pruned SSA form ^[1] is an attempt to reduce the number of Φ functions without incurring the relatively high cost of computing live variable information. It is based on the following observation: if a variable is never live upon entry into a basic block, it never needs a Φ function. During SSA construction, Φ functions for any "block-local" variables are omitted.

Computing the set of block-local variables is a simpler and faster procedure than full live variable analysis, making semi-pruned SSA form more efficient to compute than pruned SSA form. On the other hand, pruned SSA form will contain fewer unnecessary Φ functions.

Converting out of SSA form[편집]

As SSA form is no longer useful for direct execution, it is frequently used "on top of" another IR with which it remains in direct correspondence. This can be accomplished by "constructing" SSA as a set of functions which map between parts of the existing IR (basic blocks, instructions, operands, etc.) and its SSA counterpart. When the SSA form is no longer needed, these mapping functions may be discarded, leaving only the now-optimized IR.

Performing optimizations on SSA form usually leads to entangled SSA-Webs, meaning there are phi instructions whose operands do not all have the same root operand. In such cases color-out algorithms are used to come out of SSA. Naive algorithms introduce a copy along each predecessor path which caused a source of different root symbol to be put in phi than the destination of phi. There are multiple algorithms for coming out of SSA with fewer copies, most use interference graphs or some approximation of it to do copy coalescing.

확장[편집]

Extensions to SSA form can be divided into two categories.

Renaming scheme extensions alter the renaming criterion. Recall that SSA form renames each variable when it is assigned a value. Alternative schemes include static single use form (which renames each variable at each statement when it is used) and static single information form (which renames each variable when it is assigned a value, and in each conditional context in which that variable is used).

Feature-specific extensions retain the single assignment property for variables, but incorporate new semantics to model additional features. Some feature-specific extensions model high-level programming language features like arrays, objects and aliased pointers. Other feature-specific extensions model low-level architectural features like speculation and predication.

SSA form 을 사용 하는 컴파일러[편집]

SSA form is a relatively recent development in the compiler community. As such, many older compilers only use SSA form for some part of the compilation or optimization process, but most do not rely on it. Examples of compilers that rely heavily on SSA form include:

The ETH Oberon-2 compiler was one of the first public projects to incorporate "GSA", a variant of SSA.

The LLVM Compiler Infrastructure uses SSA form for all scalar register values (everything except memory) in its primary code representation. SSA form is only eliminated once register allocation occurs, late in the compile process (often at link time).

The open source SGI compiler ORC uses SSA form in its global scalar optimizer, though the code is brought into SSA form before and taken out of SSA form afterwards. ORC uses extensions to SSA form to represent memory in SSA form as well as scalar values.

As of version 4 (released in April 2005) GCC, the GNU Compiler Collection, makes extensive use of SSA. The frontends generate GENERIC code which is then converted into SSA form by the "gimplifier" and optimized by the "middle-end". The backend eventually translates the optimized intermediate code into RTL, executes some more low-level optimizations and finally turns RTL into assembly language.

IBM's open source adaptive Java virtual machine, Jikes RVM, uses extended Array SSA, an extension of SSA that allows analysis of scalars, arrays, and object fields in a unified framework. Extended Array SSA analysis is only enabled at the maximum optimization level, which is applied to the most frequently executed portions of code.

In 2002, researchers modified IBM's JikesRVM (named Jalapeño at the time) to run both standard Java byte-code and a typesafe SSA (SafeTSA) byte-code class files, and demonstrated significant performance benefits to using the SSA byte-code.

Sun Microsystems' Java HotSpot Virtual Machine uses an SSA-based intermediate language in its JIT compiler.
Mono uses SSA in its JIT compiler called Mini.
jackcc is an open-source compiler for the academic instruction set Jackal 3.0. It uses a simple 3-operand code with SSA for its intermediate representation. As an interesting variant, it replaces Φ functions with a so-called SAME instruction, which instructs the register allocator to place the two live ranges into the same physical register.

Although not a compiler, the Boomerang decompiler uses SSA form in its internal representation. SSA is used to simplify expression propagation, identifying parameters and returns, preservation analysis, and more.
Portable.NET uses SSA in its JIT compiler.
libFirm a completely graph based SSA intermediate representation for compilers. libFirm uses SSA form for all scalar register values until code generation by use of a SSA-aware register allocator.

The Illinois Concert Compiler circa 1994 [1] used a variant of SSA called SSU (Static Single Use) which renames each variable when it is assigned a value, and in each conditional context in which that variable is used; essentially the static single information form mentioned above. The SSU form is documented in John Plevyak's Ph.D Thesis.

The COINS compiler uses SSA form optimizations as explained here: http://www.is.titech.ac.jp/~sassa/coins-www-ssa/english/

참고[편집]

↑ Practical Improvements to the Construction and Destruction of Static Single Assignment Form (1998), Preston Briggs, Keith D. Cooper, Timothy J. Harvey, L. Taylor Simpson.

Appel, Andrew W. (1999). 《Modern Compiler Implementation in ML》. Cambridge University Press. ISBN 0-521-58274-1. |id=에 templatestyles stripmarker가 있음(위치 1) (도움말) Also available in Java (ISBN 0-521-82060-X 2002) and C (ISBN 0-521-60765-5, 199 8) versions.
Cooper, Keith D.; & Torczon, Linda. (2003). 《Engineering a Compiler》. Morgan Kaufmann. ISBN 1-55860-698-X. |id=에 templatestyles stripmarker가 있음(위치 1) (도움말) CS1 관리 - 여러 이름 (링크)
Muchnick, Steven S. (1997). 《Advanced Compiler Design and Implementation》. Morgan Kaufmann. ISBN 1-55860-320-4. |id=에 templatestyles stripmarker가 있음(위치 1) (도움말)
Richard A. Kelsey (1995년 3월). “A Correspondence between Continuation Passing Style and Static Single Assignment Form”. 《ACM SIGPLAN Notices》 30 (3): 13–22. doi:10.1145/202530.202532.
Andrew W. Appel (1998년 4월). “SSA is Functional Programming”. 《ACM SIGPLAN Notices》 33 (4): 17–20. doi:10.1145/278283.278285.

외부 링크[편집]

Steven Bosscher and Diego Novillo. GCC gets a new Optimizer Framework. An article about GCC's use of SSA and how it improves over older IRs.
The SSA Bibliography. Extensive catalogue of SSA research papers.

[1] Practical Improvements to the Construction and Destruction of Static Single Assignment Form (1998), Preston Briggs, Keith D. Cooper, Timothy J. Harvey, L. Taylor Simpson.

[1]