WHIRL SSA Design Document
From Open64 Wiki
Contents |
Objective
The objective of the WHIRL SSA project is to enable SSA information on WHIRL tree. We plan to make the changes incrementally. WHIRL SSA discussed in this document is about to provide a better "DU manager" and facilitate the LNO and IPA where current DU manager is mostly used. In this step, the initial WHIRL SSA info are converted from the CODEREP, not directly calculated from the original WHIRL tree. The topic of replacing CODEREP is not discussed in this document, but it can be considered in the future.
In the initial step of this project, we plan to maintain both current DU manager and provide interfaces to hook it with new SSA manager. This way, we can minimize the changes in the clients of the current DU manager. For each existing optimization, in its analysis phase, SSA will be used to replace current DU manager. There is no change needed in the code transformation phase. After the transformation, both current DU manager and SSA info are updated. We plan to fully integrate SSA manager with existing optimizations after the initial step by replacing current DU with SSA in the analysis phases. After all analysis phases use the SSA info, we can remove current DU manager completely.
Background
The DU/UD implementation in current Open64 has the following disadvantages:
* The structure of DU/UD is flat. This means a traverse of DU/UD change requires to visit all USE/DEF nodes even if the nodes are out of current analyzing/transforming scope. * In current DU manager, DU/UD is incomplete in the presence of alias. The chain can be very long if the aliased defs/uses are added to the list. * Updating current DU manager can be difficult. The result DU/UD may become imprecise after the update. Many dead DU/UD are still kept due to lack of sufficient information during the updating. There are some optimizations can be too complicated to update the DU/UD. In this case, the result DU/UD becomes incomplete, which inhibits later optimizations.
With SSA info attached on WHIRL nodes, we can overcome these problems:
* DU/UD is factored and organized into a tree-based structure in SSA form via the PHI nodes. Once the node is out of current scope, we can ignore its parent or kids during the traversal. * Alias DEF/USE are kept via CHI and MU in SSA. It’s easier and faster than querying the ALIAS MANAGER for every node. * SSA info can be recalculated within a small region ( WHIRL OPR_REGION, OPR_BLOCK, or OPR_IF, OPR_WHILE_DO, OPR_DO_WHILE, OPR_DO_LOOP ) and merged back to the whole function to keep the same precision. As a result, DU/UD info can be calculated or re-calculated within a small region instead of the whole PU. DU/UD can be calculated on demand.
Overview
3.1 Components Overview
3.1.1 WHIRL SSA producer and maintainer
* WHIRL_SSA_MANAGER: Manage the SSA info for a function or a region in the function. * EMITTER: Invoked by the Pre_OPT emitter, generate the SSA info according to the CODEREP. * VERIFIER: Verify the correctness and consistency of the WHIRL SSA info. * UPDATER: Update the SSA info if the WHIRL TREE changed * WRITER and READER: Write/Read WHIRL SSA info to/from WHIRL file (.B, .I, .o, .P, .N, .O)
3.1.2 WHIRL SSA based DU/UD Manager
* Calculate the DU/UD info based on WHIRL SSA. * Can be created on demand. * Can be created on small analysis/transformation scope instead of the whole PU. * NOT updatable (Update SSA info instead). DU/UD caching is in considering but not included in this document. * Re-create once SSA info is updated.
3.1.3 WHIRL SSA to C/F
* WHIRL2C: Convert WHIRL SSA into C program * WHIRL2F: Convert WHIRL SSA into F program
3.1.4 WHIRL SSA consumer
* LNO consumer: Utilize the WHIRL SSA info to perform better analysis in LNO phases. * IPA consumer: At this point, IPA will continue to use original DU/UD chains.
Instead of using SSA info directly, the analyzer or optimizer in LNO/IPA may use the WHIRL SSA based DU/UD Manager.
3.2 Data structure
3.2.1 WHIRL SSA
In order to minimize the impact to all later phases, we do NOT add any new nodes into WHIRL TREE. All SSA info are stored into several tables and referred via the index of the table. Several MAPs are used to connect the WHIRL node with its PHI, CHI, MU and VER info. The Data structures described in C++ can be found in Appendix D.
Data structure:
struct PHI_NODE {
ST_IDX st_idx;
VER_NUM res;
std::vector<VER_NUM> opnds;
};
struct CHI_NODE {
ST_IDX st_idx;
VER_NUM res;
VER_NUM opnd;
};
struct MU_NODE {
ST_IDX st_idx;
VER_NUM opnd;
};
3.2.2 UD/DU based on WHIRL SSA
With WHIRL SSA, we can built more precise DEF and USE information with alias information. The DU/UD information is built on demand.
Data structure:
struct DEF_NODE {
std::pair<ST_IDX, VER_NUM> uniq_idx;
DEF_TYPE type;
WN* wn;
};
struct USE_NODE {
USE_TYPE type;
WN* wn;
};
struct ST_USE_LIST {
std::pair<ST_IDX, VER_NUM> uniq_idx;
USE_LIST use_list;
};
3.3 Interface
3.3.1 WHIRL_SSA_MANAGER
WHIRL_SSA_MANAGER provides functions for emitter to generate kinds of nodes:
PHI_LIST_IDX Add_PHI(WN* wn, const PHI_NODE& phi); CHI_LIST_IDX Add_CHI(WN* wn, const CHI_NODE& chi); MU_LIST_IDX Add_MU (WN* wn, const MU_NODE& mu);
Functions for emitter to generate virtual symbols:
WSSA_ST_IDX New_VIRT_ST(); ST* Get_ST(WSSA_ST_IDX st_idx); VER_NUM Get_Max_Ver(WSSA_ST_IDX st_idx); void Set_Max_Ver(WSSA_ST_IDX st_idx, VER_NUM max_ver); VER_NUM New_Ver(WSSA_ST_IDX st_idx);
Functions for emitter to set the version of symbol used in the WHIRL node:
void Set_WN_Ver(WN* wn, VER_NUM ver); VER_NUM Get_WN_Ver(WN* wn);
Functions for consumer to retrieve the SSA info:
PHI_LIST_ITER WN_PHI_Begin(const WN* wn); PHI_LIST_ITER WN_PHI_End (const WN* wn); CHI_LIST_ITER WN_CHI_Begin(const WN* wn); CHI_LIST_ITER WN_CHI_End (const WN* wn); MU_LIST_ITER WN_MU_Begin (const WN* wn); MU_LIST_ITER WN_MU_End (const WN* wn);
3.3.2 WSSA_DU_MANAGER
WSSA_DU_MANAGER provides functions for consumer to use the DU/UD info:
void Build(BOOL ud, BOOL du); DEF_NODE ST_Get_def(WSSA_ST_IDX st_idx, VER_NUM ver); USE_LIST_ITER ST_Get_Use_Begin(WSSA_ST_IDX st_idx, VER_NUM ver); USE_LIST_ITER ST_Get_Use_End(WSSA_ST_IDX st_idx, VER_NUM ver);
3.3.3 Emitter
Emitter is invoked at by the Pre_OPT emitter. Pre_OPT emitter will emit the WHIRL TREE and SSA emitter will emit the virtual symbols and SSA info:
void Build_SSA_PHI(BB_NODE* bb, WN* wn, WHIRL_SSA_MANAGER& mgr); WSSA_ST_IDX Build_SSA_VIRT(AUX_ID aux_id, WHIRL_SSA_MANAGER& mgr); void Build_MU_CHI_Version_Stmt(WN* wn, WHIRL_SSA_MANAGER& mgr); void Build_MU_CHI_Version_Expr(WN* wn, WHIRL_SSA_MANAGER& mgr);
3.3.4 Verifier
Verifier is used to check the correctness and consistency of the WHIRL SSA info.
void Verify_WHIRL_SSA(const WN* wn, const WHIRL_SSA_MANAGER& mgr);
3.3.5 Updater
Updater is used to update the SSA info in a small region.
void Update_WHIRL_SSA(WN* root, WN* region, WHIRL_SSA_MANAGER& mgr);
3.3.6 WHIRL SSA writer/reader
WHIRL SSA writer/reader is used to write/read SSA info to/from WHIRL IR file.
void Read_WHIRL_SSA(void* handle, PU_Info* pu, WHIRL_SSA_MANAGER& mgr); void Write_WHIRL_SSA(Output_File* handle, PU_Info* pu, const WHIRL_SSA_MANAGER& mgr);
3.3.7 ir_b2a, dump_tree, dump_wn, dump_st
These utilities is used to dump both WHIRL IR, SYMTAB and SSA info. They follow the original interface.
3.3.8 whirl2c, whirl2f
These utilites is used to convert WHIRL with SSA into C or FORTRAN program. They follow the original interface.
3.3.9LNO enhancement
LNO enhancement will use the interface provided by WHIRL_SSA_MANAGER and change the code in LNO.
Detailed Design
4.1 WHIRL_SSA_MANAGER
WHIRL_SSA_MANAGER maintains all SSA related info. They are stored in different tables. Besides these tables, some maps are built to connect the WHIRL node with its SSA info.
* All PHI/CHI/MU/VER data are stored in the tables. The data in tables are accessed via its index. All data in tables are needed to write to file. * Maps maintain the mapping between the WHIRL nodes and entries of the TABLEs. The MAPs are built during generating the
SSA info or reading SSA info from the file.
The code for WHIRL_SSA_MANAGER will be placed in osprey/be/com.
4.1.1 WHIRL_SSA_MANAGER instances
Every function has a pointer to the WHIRL_SSA_MANAGER, which contains the SSA info for this function. SSA info are stored in the ".WHIRL.pu_section" in the IR file with type WT_SSA. WT_SUBSECTIONS will be increased by 1 to contain the new type. In struct pu_info (defined in common/com/pu_info.h), the newly added member of subsect will contain the pointer to the location of the SSA info in file (or mapped memory) or pointer to the WHIRL_SSA_MANAGER object, which contains the SSA info for the function.
The pointer to WHIRL_SSA_MANAGER for current PU can be retrieved via invoking PU_Info_ssa_ptr(Current_Pu_Info).
WHIRL_SSA_MANAGER* PU_Info_ssa_ptr(PU_Info* info);
If needed, WHIRL_SSA_MANAGER can be instantialized directly with a given WN tree.
4.1.2 PHI placement
PHI nodes are placed on the ROOT node of the structured control flow nodes (OPR_IF, OPR_DO_WHILE, OPR_WHILE_DO, OPR_DO_LOOP) and the LABEL, which is the join point of GOTO.
There are two reasons to place the PHI node on the ROOT node of the SCF:
a). These PHI nodes describe the side-effect of the whole SCF node. This will be explained later.
b). In many cases, there is no LABEL after or in the join point of the SCF. In order not to introduce new node, PHI nodes are placed on the ROOT node of the SCF. This also helps keep the backward compatibility.
For example:
The PHI placements for WHIRL SCF and LABEL are listed below:
WHIRL OP PHI in CFG PHI in WHIRL Rules of PHI Result and Operands
OPR_IF Join Point IF Two operands:
after the IF * The first operand is the version defined
in THEN block or active version before the IF
when there is no DEF in THEN block.
* The second operand is the version defined in ELSE
block or active version before the IF when there is
no DEF in ELSE block.
Result:
* Result is the active version after the IF
OPR_WHILE_DO Condition block WHILE_DO Two operands:
* The first operand is the active version before WHILE_DO.
* The second operand is the last version defined in the
BODY block.
Result:
* Result is the active version after the WHILE_DO
OPR_DO_WHILE Body block DO_WHILE Two operands:
* The first operand is the active version before DO_WHILE
* The second operand is the last version defined in the
BODY block. It’s also the active version after the DO_WHILE
Result:
* Result is the first version used in the BODY block.
OPR_DO_LOOP Condition block DO_LOOP Two operands:
* The first operand is the last version defined in INIT
block or the active version before the DO_LOOP if there
is no DEF in INIT block.
* The second operand is the last version defined in
BODY+INCR block
Result:
* Result is the active version after the DO_LOOP
OPR_LABEL Label LABEL Similar to the CFG-based SSA
4.1.3 TABLEs in WHIRL_SSA_MANAGER
* All PHI nodes related with the same WN are connected to form a PHI_LIST. The PHI_LIST are stored in the PHI_TABLE and referred by the PHI_LIST_IDX. * All CHI nodes related with the same WN are connected to form a CHI_LIST. The CHI_LIST are stored in the CHI_TABLE and referred by the CHI_LIST_IDX. * All MU nodes related with the same WN are connected to form a MU_LIST. The MU_LIST are stored in the MU_TABLE and referred by the MU_LIST_IDX.
4.1.4 MAPs in WHIRL_SSA_MANAGER
* PHI_MAP is used to look up the PHI_LIST connected to the given WN. PHI_MAP can be represented as {WN_MAP_IDX -> PHI_LIST_IDX}.
* CHI_MAP is used to look up the CHI_LIST connected to the given WN. CHI_MAP can be represented as {WN_MAP_IDX -> CHI_LIST_IDX}.
* MU_MAP is used to look up the MU_LIST connected to the given WN. MU_MAP can be represented as {WN_MAP_IDX -> MU_LIST_IDX}.
* WN_VER_MAP is used to look up the VERSION used by the WN. WN_VER_MAP can be represented as {WN_MAP_IDX -> VER_NUM}.
4.1.5 SSA Symbol Table
WHIRL SSA will use a separate symbol table from the WHIRL IR symbol table. This table is used to store SSA related info about the real variables, fields in the struct variable and virtual symbols. All SSA nodes, including PHI, CHI and MU will refer the symbols in the SSA symbol table. The WHIRL IR still refer the WHIRL symbol table.
A new field wssa_st_idx will be added to WHIRL SYMBOL to indicate its corresponding SSA_ST_IDX. For global variable, the value of this field will be changed during the compilation.
Each WHIRL symbol has an entry in the SSA symbol table. For example:
Code WHIRL symbol table SSA symbol table
global int a; [101] a: int, size=4, [1] a: st_idx=101, ST
local int a; wssa_st_idx=1 [2] a: st_idx=201, ST
[201] a: int, size=4,
wssa_st_idx=2
Each field in the struct variable will have an entry in the SSA symbol table. For example:
Code WHIRL symbol table SSA symbol table
struct S { [1] s: struct S, size=8, [1] s: st_idx=1, ST
int a; wssa_st_idx=1 [2] s.a: st_idx=1, offset=0, size=4, FIELD
int b; [3] s.b: st_idx=1, offset=4, size=4, FIELD
};
struct S s;
Virtual symbols is an imaginary scalar variable that has indentical alias characteristics as the indirect variable (refer [1]). Virtual Symbols are also stored into the SSA symbol table.
Code WHIRL symbol table SSA symbol table
int a; [1] a: int, size=4, [1] a: st_idx=1, ST
int* p = &a; wssa_st_idx=1 [2] p: st_idx=2, ST
[2] p: int*, size=ptr, [3] &a: st_idx=1, LDA SCALAR VYM
wssa_st_idx=2 [4] def_vsym: st_idx=0, DEFAULT VSYM
[5] ret_vsym: st_idx=0, RETURN VSYM
4.2 WSSA_DU_MANAGER
WSSA_DU_MANAGER maintains the DU/UD info for a given WHIRL tree.
The code for WSSA_DU_MANAGER will be placed in osprey/be/com.
4.2.1 DEF_TABLE and USE_TABLE
These two tables are built to provide the UD and DU information. They are built on-demand. They are built via traversing the given WHIRL tree and save the DEF and USE info about each version of the symbol.
4.2.2 DEF_MAP and USE_MAP
These two maps are used to find out the def/use node (defined/used by PHI, CHI, MU or WN) by a given ST_IDX and VERSION.
4.2.3 EXT_DEF_ITERATOR
EXT_DEF_ITERATOR will expand the PHI or CHI nodes, which can enable the user to traverse the whole DEF tree from a given WN or a pair of ST_IDX and VERSION.
4.2.4 EXT_USE_ITERATOR
EXT_USE_ITERATOR will expand the PHI or CHI nodes, which can enable the user to traverse the whole USE tree from a given WN or a pair of ST_IDX and VERSION.
4.3 Emitter
Emitter is used to convert the SSA info in CODEREP to WHIRL.
The code for CODEREP based emitter will be placed in osprey/be/opt
4.3.1 Process PHI node
1. The Original WHIRL emitter check if BB_LOGIF, BB_DOSTART, BB_REPEATBODY, BB_WHILEEND can raised into high level SCF.
2. Generate and attach PHI nodes(PHI_LIST) when convert to SCF.
BB_WHILEEND convert to WHILE_DO in function Raise_whiledo_stmt, will try to optimize WHILE_DO to DO_LOOP.
* Raise_whiledo_stmt_to_doloop, end BB's PHI_LIST on DO_LOOP WN node * Raise_whiledo_stmt_to_whileloop, end BB's PHI_LIST on WHILE_DO WN node * Raise_if_stmt, record merge BB's PHI_LIST on IF stmt * Raise_doloop_stmt, record end BB's PHI_LIST on DO_LOOP, * Raise_dowhile_stmt, record merge BB's PHI_LIST on DO_WHILE. * Raise_region_stmt, record the PHI_LIST on REGION node
3. When BB can't convert to scf.
* If BB has label record phi node on label. * For BBs have no label, assertion that there should be no phi node for this BB.
4. Provide a function SSA_WHIRL_Copy_PHI(BB*, WN*) called from original WHIRL emitter.
4.3.2. Process MU/CHI node
1. Current implementation: When converting CR and SR to WN node, it makes a WN_MAP, map CR,SR to WN node.
These are existing functions in Pre_OPT EMITTER:
EMITTER::Connect_cr_wn ( STMTREP *stmtrep, WN *wn ); EMITTER::Connect_sr_wn ( CODEREP *coderep, WN *wn );
2. Record MU/CHI/Version on WHIRL node can be separated from original WHIRL emitter's function.
- Add a function Build_MU_CHI_Version, invoked after
EMITTER::Emit->Raise_func_entry. It's like the flow of BUILD DU.
Build_MU_CHI_Version_Stmt(Wn)
{
if(WN_has_mu(wn)) // WN_has_mu has been defined in Open64
STMTREP *stmt = (STMTREP*)WN_MAP_Get( _wn_to_cr_map, wn );
Transalte MU node to SSA WHIRL MU node and map with wn.
if(WN_has_chi(wn)) // WN_has_chu has been defined in Open64
Transalte CHI node to SSA WHIRL CHI node and map with wn.
if(WN_has_ver(wn))
map wn with stmt->lhs.version()
iteraitvely walk the WHIRL tree
{
if ( kid is expr )
call Build_MU_CHI_Version_Expr
else
call Build_MU_CHI_Version_Stmt
}
}
Build_MU_CHI_Version_Expr(Wn)
{
if (WN_has_mu(wn))
Transalte MU node to SSA WHIRL MU node and map with wn.
if(WN_has_ver(wn))
cr = WN_MAP_Get( _wn_to_cr_map, wn );
map wn with cr.version()
}
3. Virtual Symbols are entered into symbol table during the conversion. Max version for each symbol are updated once there is a new version. The value of 0 is still kept for version zero (reference [1]).
4.4 Verifier
Verifier is used to verify the correctness, completeness and consistency of the SSA info. The code for SSA verifier will be placed into osprey/be/com.
4.4.1 Verifier's functionality
Verifier needs to check these problems:
- Completeness. Verifier needs to check the completeness of SSA WHIRL_TREE:
* All variables have been assigned version
* All joint node included in SCF node has PHI nodes
* MU/CHI list is constructed correctly
* Version is correct (smaller than MAX, not overlap)
* Symbol, include the virtual symbol, are aliased
- Consistency.
Verifier needs to check if order of operands in phi-node is consistent with whirl node. Thinking about if-statement, there is a phi-node attached to the node. According to our design, first operand from then-block, and the other operand from else-block. verifier needs to guarantee the phi-node follows the rule:
IF: The PHI node has two operands. The first operand is the last version in THEN block (or last version before the IF if there is no definition). The second operand is the last version in the ELSE block (or last version before IF...). The result is the active version after the IF. DO_LOOP: The PHI node has two operands. The first operand is the last version in INIT block (or last version before the DO_LOOP if there is no definition). The second operand is the last version in (BODY+INCR) block (or last version before DO_LOOP...). The result is the active version after the DO_LOOP. WHILE_DO: The PHI node has two operands. The first operand is the last version before the WHILE_DO. The second operand is the last version of the BODY block. The result is the active version after the WHILE_DO. DO_WHILE: The PHI node has two operands. The first operand is the last version before the DO_WHILE. The second operand is the last version of the BODY block. The result is the first version used in BODY block. The active version after DO_WHILE is the second operand. GOTO: Like traditional PHI definition in CFG. The number of operands equal to the number of GOTOs target to this label. The order of the operands follow the presence of the GOTOs in the WHIRL tree. The value of the version of the operand is the last version before the GOTO. The result is the active version after the LABEL.
- Live-Range overlap:
SSA version live-range overlap is not allowed in our design. Verifier needs to check there is no live-range overlap for constructed SSA WHIRL tree.
4.4.2 Basic Design
1. Prerequisite:
* CFG constructed from SSA WHIRL tree outputted from EMITTER. * Dominator Tree
2. Functions and Description:
* Build_CFG(): this function is used to construct CFG from WHIRL TREE, the major work in this part is to convert SCF node to basic blocks * Build_Dom_Tree(): this function is used construct dom/pdom tree * Verify_Completeness(): this function is to traverse whirl tree and check if all scalar variables has been assigned one version * Verify_Consistence(): this function is to traverse all phi-node attached to whirl-node, and check if predecessor operands in phi-node is consistent. * Verify_LiveRange(): repeat SSA renaming process to detect if the version of the top of renaming stack is the same as current use. Since the renaming phase in Open64 WOPT is based on CODEREP, we need to rewrite this phase using the same algorithm.
4.5 SSA Updater
SSA Updater is used to recalculate the SSA info of a small block (WHIRL SCF, BLOCK or REGION) and make it consistent within the whole WHIRL tree.
The code for SSA updater will be placed into ospret/be/com.
The algorithm is described below:
1. Walk the region tree, find out all ST used (def or use) in the tree 2. Collect the input and output version 3. Original transformation on sub tree and update DU. For new nodes created from original nodes, all SSA info are also copied. For new nodes generate from scratch, if the operation is indirect memory access and corresponding ST has virtual symbols, MUs and CHIs on the virtual symbols will be generated. For direct access, MUs and CHIs will be generated based on the alias information. For SCFs, PHIs are generated. 4. Re-calculate the PHIs on the new tree. If there are GOTOs and LABELs in the block, a CFG might be needed. Otherwise, we can insert PHI nodes directly following the rules describe in 4.1.2. 5. Re-naming the variables, starting version is the max_version of the ST. 6. Adjust the input and output version if necessary 7. Connect the new region tree with original root tree
We assume these preconditions:
* The IR to be transformed should only have one entry node. If there are multiple in-coming edges, PHI nodes are inserted in the entry node. * The IR to be transformed can have multiple out-going edges in its exit nodes. * The transformation does not introduce any new entry node. * The transformation can introduce new out-going edges, but can not introduce new out-going target.
4.6 WHIRL2C/WHIRL2F
WHIRL2C/WHIRL2F is used to convert the IR to source code while keeping the SSA info. WHIRL2C/WHIRL2F will be based on original implementation.
Handle VERSION, PHI, MU, CHI:
* VERSION: For local symbols, it becomes part of the symbol name. For global symbols, it’s discarded (only generate comments). * PHI: Becomes assignment and inserted to the end of all the predecessors (before the branch) * MU: Only generate comments * CHI: Only generate comments
Original Source Source in SSA form Source by WHIRL2C
int d; int foo() { int foo() {
int foo() { int a, b, c; int a1, b2, b3, b4, c2;
int a, b, c; if ( a1 ) { if ( a1 ) {
if ( a ) { b2 = d2; b2 = d; // dv2
b = d; } b4 = b2; //PHI
} else { }
else { b3 = a1; else {
b = a; } b3 = a1;
} b4 = phi(2, 3) b4 = b3; //PHI
c = b; c2 = b4; }
return c; return c2; c2 = b4;
} } return c2;
}
4.7 LNO Enhancement
WHIRL SSA manager is designed to replace the DU manager. LNO will query the DU/UD interface provided by WHIRL SSA manager.
A important issue is to update SSA manager when some transformation was done by LNO. The details about how to update the SSA has been discussed in section 4.4 in this document. Since not all transformations will be rewritten to use the WHIRL SSA at the begining of the project, we have to update the DU manager during the transformation in order not to break later phases which still use the DU.
Utilize WHIRL SSA:
* Use SSA to do the analysis * Transformation, update the DU at the same time * Update SSA
Not Utilize WHIRL SSA:
* Use DU to do the analysis * Transformation, update the DU at the same time * Update SSA
In general, with SSA manager, LNO would be more effective and efficient.
The DU manager does not provide complete information if there is aliased access. It disables some optimization in LNO. An example (the first example in Appendix B) is from vectorization. For which, the compiler intend to verify if a reduction is valid. It examines all USE of the variable inside of the loop and verifies each of them. But the DU manager tells the compiler that some USE information is not available. Actually, there is a possible (irrelevant) aliased access outside of the loop.
Efficiency is improved with SSA manager, as LNO is calculation version of some USE by itself, if a DEF is the only DEF for related USE, and so on.
The changes in LNO depend on the specified optimizations. So far we plan to start from SNL transformations.
Quality Plan
5.1 White Box Testing
We plan to do the white box testing by dump out the SSA info and check the correctness:
* Write simple cases (cover all SCFs, contains goto/truebr/falsebr, cover globals, pointers, arrays) * Compile these cases and dump out SSA info * Compare the SSA info with Master file (verified by hand)
5.2 Black Box Testing
We plan to use the modified whirl2c/whirl2f to do the black box testing
* Use GCC regression test suites as input * Compile these cases and using modified whirl2c/whirl2f to convert them into C/F file * Re-compile the generated C/F file and run it * Check the result by GCC testing framework
Handle version, phi, mu, chi:
* version: becomes part of the symbol name * phi: becomes assignment and inserted to the end of all the predecessors. * mu: discarded * chi: discarded
5.3 Builtin Triage Tools
Builtin dumper
* dump all PHIs, CHIs, MUs * dump WN with SSA info (version, PHIs, CHIs, MUs) * dump WHIRL tree with SSA info (version, PHIs, CHIs, MUs)
Builtin tracing
* trace the WHIRL SSA emitter (CODEREP, WHIRL tree, SSA INFO) * trace the WHIRL SSA updater (WHIRL tree before/after update) * trace the SSA info usage in LNO
Builtin binary search capability
* So far, there is no builtin binary search.
Reference
[1] Fred Chow, Sun Chan, Shin-Ming Liu, Raymond Lo, Mark Streich, Effective Representation of Alias and Indirectly Memory Operands in SSA Form, CC96.
