----------------------------------------------------------- Copyright (C) 2005 The Coins Project Group (Read COPYING for detailed information.) ----------------------------------------------------------- SSA optimization for LIR (1) OVERVIEW (1-1) Introduction The SSA module includes optimizers on the Static Single Assignment form (SSA form). SSA is a representation where index is attached to every variable so that every definition of each variable in a program becomes unique. At a joining point of the control flow graph where two or more different definitions of a variable reach, a hypothetical function called a phi-function is inserted so that these multiple definitions are merged. Data flow analysis and optimization for sequential execution can be compacted using SSA form. The SSA module is invoked on LIR. (1-2) Translation to SSA form The translation pass of the SSA module translates normal LIR into LIR-level SSA form. Translation into SSA form generally consists of two phases, insertion of phi-functions and the renaming of variables. Three types of SSA form are well known: minimal SSA, semi-pruned SSA and pruned SSA. The algorithms for translating into these forms are almost the same, only the live variable analysis being different. The SSA module can translate into these types of SSA form. See section 2. (1-3) Back translation from SSA form The back translation pass of the SSA module translates LIR-level SSA form into normal LIR. Generally, in the back translation from SSA form, the task of a phi-function is divided into the predecessor basic blocks. Therefore, in most cases, the translation inserts some copy statements for variables used in the phi-function into the predecessor blocks of the basic block where the function resides, and then deletes the phi-function. The SSA module uses the method proposed by Briggs and the three methods proposed by Sreedhar to back translate from SSA form. See section 2. (1-4) Optimization Many optimizations based on SSA form are implemented, such as Common Subexpression Elimination, Constant Propagation, Copy Propagation, Dead Code Elimination and loop-related optimizations. The SSA module also includes tools for optimization, such as Split Critical Edge. You can specify the optimizers, tools and their order of application using the SSA options. See section 2. (1-5) Details For details of the SSA optimization module, see [reference 1]. (2) SSA OPTIONS There are several compile time options for the SSA pass. For any other options of the COINS Compiler Driver, see `READMEcc.txt' or `doc-en/README.driver.en.txt'. -coins:ssa-opt=xxx/yyy/.../zzz Use SSA pass. This is necessary for using the SSA module. There are several optimizations in this module. To invoke the optimization, you should specify the optimizers with this option. Specified optimizers are invoked from left to right. First, as `xxx' you MUST specify to which kind of SSA form you like to translate, such as minimal, semi-pruned or pruned. And then, as `yyy' you can specify the optimizers which the SSA module invokes. You can specify the same optimizer two times, three times, and so on. Only optimizations that you specify are performed in that order. Finally, as `zzz' you MUST specify how to back translate from SSA form. The options are defined as follows: Translation from normal form LIR to SSA form LIR (You MUST specify one of them at the beginning of this SSA option) mini : Translation to Minimal SSA form semi : Translation to Semi-Pruned SSA form prun : Translation to Pruned SSA form (recommended for optimization) Back Translation from SSA form LIR to normal form LIR (You MUST specify one of them at the end of this SSA option) brig : Back translation using Briggs's Method srd1 : Back translation using Sreedhar's Method I srd2 : Back translation using Sreedhar's Method II srd3 : Back translation using Sreedhar's Method III (recommended for optimization) (Options for coalescing are explained later) Optimization cpyp : Copy Propagation cstp : Constant Folding and Propagation with Conditional Branches dce : Dead Code Elimination cse : Common Subexpression Elimination preqp : Global Value Numbering and Partial Redundancy Elimination with Efficient Question Propagation hli : Hoisting Loop-invariant Code osr : Operator Strength Reduction related to Induction Variables and Linear Function Test Replacement ssag : Making SSA graph divex : Divide Expression into Three-Address Code (the right-hand side of assignment will have only one operator) gra : Global Reassociation ebe : Empty Block Elimination rpe : Redundant Phi-function Elimination cbb : Concatenate Basic Blocks esplt : Split Critical Edge lir2c : Make C program from LIR Example: If you specify the option -coins:ssa-opt=prun/cstp/cse/srd3 the SSA module performs the following in that order: 1. make pruned SSA form 2. invoke constant folding and propagation with conditional branches 3. invoke common subexpression elimination 4. back translate using Sreedhar's Method III -coins:ssa-no-change-loop Before the optimizations, the SSA module changes the structure of the loops as follows, by default. This is for making effective loop optimization. 1. merge the several loops that have the same header block 2. insert the preheader 3. change the loop structure from `while' type to `do-while' type (precisely `if-do-while'). The `while' type is a loop such that the header and exit block of the loop are the same block. The above is performed by default. If you DO NOT want to do that, specify this option. -coins:ssa-no-copy-folding During the translation to the SSA form, the SSA module removes and propagates the copy assignment statements such as `x=y', by default. If you DO NOT want to do that, specify this option. -coins:ssa-no-redundant-phi-elimination The SSA module eliminates redundant phi-functions after the translation to the SSA form, by default. A phi-function is redundant if: 1. the names of the target and the arguments of the phi-function are all the same as follows: x1=phi(x1,x1,x1) 2. the names of the arguments of the phi-function are all the same as follows: x1=phi(y1,y1,y1) 3. there are also other cases as follows: x1=phi(y1,y1,x1) or x1=phi(y1,y1,BOTTOM) In the first case, the SSA module just eliminates the phi-function. In the second case, the SSA module eliminates the phi-function and replaces uses of `x1' by `y1' in the statements which are evaluated after the phi-function. For further details, see [reference 1]. If you DO NOT want to do that, specify this option. -coins:ssa-no-sreedhar-coalescing During the back translation from SSA form by Sreedhar's method, the SSA module coalesces copy-related variables in SSA form, by default. This coalescing is proposed by Sreedhar and is called the SSA-based coalescing. This coalescing module is usually unified with Sreedhar's algorithm for back translation from SSA form. But for researchers' convenience, the SSA module can avoid it. If you DO NOT want to do SSA based coalescing, specify this option. -coins:ssa-with-chaitin-coalescing Perform coalescing proposed by Chaitin after the back translation to normal form. This coalesces copy-related variables whose live ranges do not interfere each other. In general, after the back translation from SSA form, there may be some copy assignment statements in the program. Some copy assignment statements only change the names of variables, that is, they are useless. Coalescing these variables eliminates the useless copy assignment statements. This optimization is done in normal form LIR after the back translation from SSA form. If you WANT to do that, specify this option. (This coalescing can be specified after any back translation method. But it may have no effect after the back translation by Sreedhar's Method III since that method does not insert copy assignment statements which can be coalesced by Chaitin's coalescing.) -coins:ssa-no-memory-analysis When Common Subexpression Elimination and/or Global Value Numbering and Partial Redundancy Elimination with Efficient Question Propagation are specified, the SSA module makes a simple alias analysis of memory accesses, by treating the whole memory as a single entity. (cf. section 8 of [reference 1]) If you DO NOT want to do that, specify this option. -coins:ssa-no-replace-by-exp Just before the back translation from SSA form, the SSA module finds the local variables, which are not "live out" from the current basic block and are used only once in the current basic block, and replaces the variables by the expressions which define the variables. (cf. section 5.4.6 "preprocessing for temporary variables" of [reference 1]) If you DO NOT want to do that, specify this option. -coins:trace=SSA.xxxx To output the trace information of this SSA module for debugging, specify the trace level as follows: 1 : Output only the message that the SSA module is invoked 100 : Output the agenda of the SSA module 1500 : Output two kinds of information: (a) The inserted phi-functions when the SSA module translates normal LIR into SSA form. (b) The inserted copy assignment statements when the SSA module back translates SSA form into normal LIR. 2000 : Output general debug information of all optimizers in the SSA module 10000 : Output much information about Sreedhar's Method III The trace information includes the levels less than or equal to what you specified. If you specify trace=SSA.1500 then the SSA module outputs information related to the level `1', `100' and `1500'. -coins:ssa-opt=.../dump/... For compiler developers, the SSA module provides the option `dump' for debugging. This option should be specified within `ssa-opt'. When this option is specified, the SSA module outputs the current LIR into the standard output. For example, if the option is specified as follows: -coins:ssa-opt=prun/dump/srd3/dump the SSA module outputs the LIR (1) after translation into the pruned SSA form, and (2) after back translation from SSA form. References: [1] `Optimization in Static Single Assignment Form - External Specification' which is available on the web page `http//www.coins-project.org/'.