Contents

Chapter 1
Introduction

Open64 compiler enables compilation of programs written in multiple languages, for example, FORTRAN, C, C++ to multiple architectures, for instance x86, x86_64, IA-64 to name some. Even though multiple languages are supported by the compiler’s front-end, its back-end operates on a common Intermediate Representation (IR). This IR is WHIRL.

One of the important features in Open64 is the use of common intermediate representation irrespective of the source language. This concept enables common compilation stages to achieve the desired effect over inputs provided in different languages. For instance, a single compiler implementation of the interprocedural analysis stage and loop nest optimization stage optimizes input programs that are provided in different source languages. Futher, optimization passes communicate easily with the common IR and thus the communication overhead between passes is reduced.

Even though the common IR is WHIRL, several forms of WHIRL come to existence via Open64’s gradual lowering compilation process. The main benefit from Open64’s gradual lowering process is in enhancing the expressibility of certain optimizations. Certain optimization may be effective or easily expressible when the input that is applied is at a high level in IR. By not translating code to a low level and by using gradual lowering, open64 enables different granulaties that suit the expressibility of particular optimizations.

WHIRL at its highest levels is much like a high level language program. It is represented using a tree as a hierarchical representation. To enable control flow and data flow analysis, hierarchical WHIRL is lowered to a control flow graph after lowering high-level constructs to a mid-level. To enable SSA optimization, CFGs are translated to SSA form. In its high-level and lower levels, WHIRL consists of WHIRL expressions and statements. Expressions do not cause side-effects and statements may cause side-effects. This design choice also helps in capturing the implicit control flow between statements in the input programs, irrespective of the source language. This document serves to introduce the Open64 compiler developer to a number of compilation concepts in Open64. This document contains a number of examples which developers may find useful. A brief introduction to components in WHIRL is provided in Chapter 2.

Chapter 2
Components of WHIRL

WHIRL consists of WHIRL instructions and WHIRL symbol table. This chapter contains a brief introduction to the general structure shared by every WHIRL instruction. Some of the common instructions in WHIRL are shown with examples. WHIRL symbol table entries are refered by WHIRL instructions. The interface provided for compiler passes to access the symbol table is described in this section. Following sections contains number of examples of different types of WHIRL nodes. Further details of WHIRL may be found in [WHIRL, SYMTAB].

• WHIRL node (WN). A given WHIRL file is organized with Program Units (PUs). PUs can be called as the roots of program code. Program code is represented using WHIRL instructions which are in turn reachable from PU data structure. WHIRL instructions are laid out in tree form. Each node in a WHIRL tree is called a WHIRL Node (WN). A WHIRL node data type is declared by using Open64’s WN structure type. Human readable versions of WN or a WHIRL tree that are obtained using ir_b2a tool or the dump functions generally consists of WN operator, WN types, WN descriptors, Symbol Table entry, Type Table entry and/or other qualifiers when applicable. An example for WN is given below.
  Consider the following human readable version of a WN that loads from a program variable, A.

• Operator, result type and operand type. The type of a WHIRL instruction is its WHIRL operator. Several WHIRL instructions compute results using a set of operands as input, for instance, WNs that correspond to arithmetic operations like +, -. WNs contain a WN operator and typically also contain a result type (plainly refered to as type) and an operand type (also called the descriptor type or desc in short). The WHIRL operator, its result type and the desc type completely describe the type of a given arithmetic WN. The collective property is called the WN’s opcode.
  • The WHIRL operator of a WN can be obtained via the WN_operator utility function.
  • The result type of a WN can be obtained via the WN_ty utility function.
  • The operand types is also called the WN descriptor and it is obtained via the WN_desc utility function.
  • The opcode is obtained via the WN_opcode utility function.
• Control statement operator and miscelleneaus statement operators. An interesting feature in open64 is that WN is used to represent just about every statement (or expressions) in the input program, for instance, control structures like if-else-endif, DO loops. Without loss of generality, Open64 has WN_operators like DO_LOOP, IF, GOTO, CALL, LABEL, COMMENT, PRAGMA etc to enable the use of a single WN structure for expressions, loads, stores, comments, procedure calls. pragmas, and control structures etc. WHIRL control structures are called statements in WHIRL parlance.
• Load, store and address compute operators. As stores cause side-effects they are considered to be stateful. Stores are thus grouped with WHIRL statements. Loads are considered to be side-effect free and they are grouped with WHIRL expressions. Other than loads and stores, Open64 also features operators, for instance, LDA, for representing address computing operations. Stores, loads and address computes can use either direct memory access or indirect memory access. For direct memory accesses, the exact location is known completely at compile time. In case of indirect addressing, the addressed location is a result of a run-time computation. The WN_operator for direct address compute operation is LDA and indirect address compute is ILDA. Direct loads and stores are represented with WN_operators LDID and STID respectively. Indirect loads and stores are represented with WN_operators ILOAD and ISTORE respectively. Examples of loads, stores and address computes are in Sections 2.2.1 and 2.2.2.
  • WNs of all loads and stores specify the type of the object that is being loaded from or stored to.
  • Open64 allows all of its loads and stores to access fields in structures without having to convert structures to a lowered data type. Each load and store may request a specific field in a structure, using a field identifier. This “field_id” can be obtained using the WN_field_id utility function. Nested structures are flattened by the compiler prior to WHIRL instruction creation. Thus loads and stores need only one field_id to refer to any particular entry, even when the type of the structure is hierarchical.
  • For indirect loads and stores, the type of the pointer can also be obtained in addition to type of the object that is being loaded from or stored to.

  Note: It is important fact that there are two data types in case of indirect stores and loads. First is either for the result type, in case of load, or for operand type in case of store. Other is for the type of the addressing pointer.

• WN_kid or operand. An operand of a WN may be obtained using loads to the symbol table when they are program variables. Operands may be also be other WNs, except WNs which are considered as statement types. There are utility functions, WN_kid0, WN_kid1, WN_kid2, WN_kid3, WN_kid4, WN_kid(WN*, int) which should be used to obtain a given operand. The number of kids of a WN should be obtained by using the WN_kid_count utility function.

• Pool based dynamic memory allocation is used to hold WNs during compilation. Open64 uses memory pool management to enable dynamic memory allocation. Open64 provides standard interfaces to create and delete WNs in a memory pool.
• Annotations are possible with WN_Map data structure. Compiler passes may communicate using annotations on a given WHIRL node.

Section 2.1 introduces debugging methods for pass writers. Sections 2.2 contains WHIRL expressions and WHIRL Statement descriptions with examples. For more detail further readings of [WHIRL, SYMTAB] are recommended. Section 2.3 demonstrates interfaces to creating WHIRL nodes with examples, demonstrates iterations over WHIRL nodes and introduces the memory pool dynamic allocation system used in Open64. Section 2.4 demonstrates the interfaces to adding annotations to WHIRL nodes.

2.1 Debugging WHIRL

The compiler provides an option, -keep, which writes out WHIRL of a given source file as a binary file. The file name extension for this binary file is “.B”. The ir_b2a tool is used to translate a WHIRL binary file to human readable form. ir_b2a tool also supports -st option which enables human readable symbol table data in the output. Examples used in this report are generated using the ir_b2a tool (ir_b2a dumps have been edited here for content). Using ir_b2a on high WHIRL is a particularly effective way to understand WHIRL.

Optimization passes in Open64 can printf a human readable version of WHIRL using utility functions for instance, dump_wn, dump_tree. It will be useful to carefully study the result of the following dump routines on small programs prior to working on optimization.

• dump_wn (WN*). This function prints an ASCII version of the WN to standard output. The entire tree is not printed and only the WN content is printed. Symbol table entries referred by WNs are resolved and a human readable character string is printed.
• dump_tree (WN*). This function is similar to dump_wn, but it is recursive on the WHIRL tree. The children of a WN are printed first followed by the parent.
• dump_wn_no_st and dump_tree_no_st. These are similar to the above dump_* routines, but these do not resolve symbol table entries referred in the WN.

Human readable versions of WN or a WHIRL tree that are obtained using ir_b2a tool or the dump functions generally consists of WN operator, WN types, WN descriptors, Symbol Table entry, Type Table entry and/or other qualifiers when applicable. Human readable WHIRL data in this document have been obtained with ir_b2a.

2.2 WHIRL Expressions and Statements

2.2.1 Direct load (LDID) and Direct store (STID)

Scalar loads and stores are said to use direct addressing. Their addresses are at a known location, which is referred by an entry in the symbol table. This entry is a pointer referencing to type ST and it is available in the WN for scalar loads and stores. The utility function WN_st can be used to obtain the ST from a LDID and STID.

• LDID is a leaf WN. It has no children.
• STID is a statement. It is not used as a child in a WN.
• WN_offset, WN_load_offset, WN_store_offset utility functions should be used to obtain the offset of a LDID or STID. All three functions achieve the same effect. But it might be more efficient to use WN_load_offset and WN_store_offset to obtain the offset for LDIDs and STIDs respectively. Compiler optimizations use WN_offset to enable customizations of memory layout for the data from the symbol table.
• WN_kid0 gives the loaded or stored operand.
• WN_ty gives the type of the addressed location.
• WN_desc gives the type of the loaded or the stored operand.

Example for a scalar load:

• The opcode for the example load, F8F8LDID contains the result type, F8, the descriptor type (operand type), F8 and the LDID operator.
• The value 0 after the opcode indicates the offset for the LDID.
• The type of the operand which is stored in memory is F8 (a 8-byte long float in double precision)
• <2,1,A> is the human readable tuple of ST entry in the symbol table for a program variable which was given the name A.
• T<11,.PREDEF_F8,8> is a type tuple of the addressed location in human readable form.

Example for a scalar store:

• The opcode for the example store, I4STID contains the descriptor type, I4 and the STID operator. The result type is a pointer type.
• WN_offset of the STID is 0.
• The type of the variable which is stored in memory is I4 (a 4-bytes long signed integer)
• The type of the addressed location is T<4,.PREDEF_I4,4>.
• The symbol table entry for the result is <1,43,i>.
• The input is WN_kid0 of the store, and is an INTCONST type expression WN, whose type is I4 and the value that it represents is 22.

For examples on scalar loads and stores that are qualified with field_ids, consider the C++ or C structure in Figure 2.1. Loads and stores to structure fields have an additional qualifier, field_id, compared to loads and stores to regular program variables.

2.2.2 Indirect load (ILOAD), store (ISTORE) and related: ARRAY, ILDA

ILOAD and ISTORE are used in situations when accessing arrays and pointers. The example ISTORE in line 9 of Figure 2.2 indicates that the field_id is 0 and also indicates that an 4-byte integer value is stored using a pointer which is a 8-byte type anonymous pointer. Similar reasoning applies to line 18 of Figure 2.2. The LDA operator is used when address of pointer types are required. An example is line 5 in Figure 2.5. Here the variable ’a’ has been renamed by the front-end as ’anon1’. The type of the pointer is of size 8-bytes as per the last field of the type tuple: T<46,anon_ptr., 8> ¹.

ARRAY WNs are used to represent array accessing in WHIRL. One of the children in both the ISTORE and the ILOAD in the Figure 2.2 is an ARRAY WN. A more detailed example of WNs for array access in FORTRAN and C are shown in Figure 2.4 and Figure 2.3 respectively.

• The first integer value in the ARRAY WN is the number of dimensions of the array being accessed. The second integer value is the size of the arrayed data type in bytes. The number of dimensions of the array in Figure 2.4 is three and the size of each array element is four bytes.
• The array access WN has all index variables as kids. One child of the array access in line 20 of Figure 2.4 is the computation for the index variable I. Another child is in line 16 of Figure 2.4 and it represents the computation for the index variable J. The index variables are decremented by 1 in Figure 2.4, because arrays in high WHIRL start from index zero (this is consistent with C language arrays but not with FORTRAN language arrays where the first element of array has index one). Example for C array index variable computation are the LDIDs in lines 31-33 of Figure 2.3. In Figure 2.3, index variables have been converted from their programmer given names to anonymous names, for instance anon1, anon2 and so on.
• Other kids are the base pointer of the array and the sizes of each dimension: for instance, lines 18-21 of Figure 2.3 and lines 11-13 of Figure 2.4.

However, the front-end may not be able to use ARRAYs for array accessing when pointers are used instead of arrays, for instance, as in Figure 2.6. In these instances, the compiler front-end uses lower level address computation WHIRL trees for address generation. The address compute kid of the ISTORE in line 17 of Figure 2.6 computes the address of b[i][j] by first computing b[i] with the ADD WN in line 11, and following that with arithmetic to obtain b[i][j] with the ADD WN in line 16. Notice that the address pointer computation to obtain b[i] needed a 8-byte scaling with the MPY WN in line 9 but the address computation to obtain b[i][j] only needed a scaling of 4-bytes with the MPY in line 15. This is because the size of array elements in b are 4-bytes.

2.2.3 Type conversions

Figure 2.7 contains an example for implicit type conversions and type promotions. Line 13 in Figure 2.7 demonstrates implicit type conversions. It contains an assignment of an integer variable ’a’ to a float variable ’b’. The WHIRL for this line is in the following lines: lines 14-16. The WN that enables the conversion has a WN_operator of CVT, result type of F4 (4-byte float) and operand type of I4 (4-byte integer). Lines 18-22 in Figure 2.7 shows a type promotion of the variable ’b’ to double precision and then adding to the double precision constant (in line 21). Some other relavent examples are in the following lines.

2.2.4 Misc statements: block, conditionals, loops, direct calls, returns, indirect calls

2.2.5 BLOCK operator

A WN whose operator is BLOCK is used to hold a list (doubly linked) of subtrees. The first WN in the list is obtained by using WN_first utility function and the last WN in the list is obtained by using the WN_last utility function. Unlike other WNs, this node does not support WN_kid functions or the WN_kid_count. While direct access of a kid is not supported for WN blocks, iteration over the BLOCK is possible using the WN_next and WN_prev utility functions. An example WN for BLOCK is in Figure 2.8 between lines 6-10 (this BLOCK is enclosed by another block between lines 5-16).

2.2.6 Call and Return

Call parameters are kids for the CALL WN. An example for a C-function call is in Figure 2.8. An example for a FORTRAN-function call is in Figure 2.9. FORTRAN also supports SUBROUTINEs. An example for subroutine calling is in Figure . It is important to see the differences between the way parameters are passed in FORTRAN (Figure 2.9), wherein they are passed by reference, and in C (Figure 2.8), wherein parameters are passed by value. The parameters are passed by using a PARM WN. Notice the difference between PARM WN in line 8 in Figure 2.8 and the PARM WN in line 31 in Figure 2.9. WN_kid0 of these PARM nodes are LDID loading the passed value in case of C and a LDA which passes the reference to the value in case of FORTRAN. The differences between them show in WHIRL only when passing arguments in caller and there is no difference while loading from parameters inside the callee.

The data type of the call is obtained with the WN_ty utility function. The call WN in line 9 of Figure 2.8 computes a result of type I4 (4-byte integer). WN_kid utility functions should be used to get parameters used in the CALL WN. WN_st on the call WN obtaines the ST entry of the called function.

2.2.7 Indirect (function pointer) Call

C supports using function pointers. An example function pointer invocation in C and the corresponding WHIRL is shown in Figure 2.11. The only difference between direct and indirect calls is that WN_kid0 is a load that dereferences the function pointer. The type of the function pointer (type representing the function declarator) is obtained using the WN_ty utility function. Developers are encouraged to study how function pointers are used in open64 to support C++ virtual functions.

2.2.8 If else structure

If-else structures from the input program are represented as binary conditional structures as shown in Figure 2.12. Each if-structure has three kids: WN_kid0 gives the conditional expression, WN_kid1 gives the body that is executed when the condition evaluates to non-zero value and WN_kid2 gives the body that is executes when the condition evaluates to zero value. WN_kid1 and WN_kid2 are BLOCK WHIRL nodes.

2.2.9 FORTRAN DO loop

An example for a FORTRAN DO loop is given in Figure 2.13.

• WN_kid0 gives the ID_NAME containing the name of the induction variable
• WN_kid1 gives the initialization STID statement that sets the initial value to the induction variable
• WN_kid2 gives the conditional expression that checks for the loop end test
• WN_kid3 gives the statement that computes the incrementing step for the induction variable
• Finally, WN_kid4 gives the body of the DO loop

2.2.10 C For loop

An example for a C FOR loop is given in Figure 2.14. Unlike the FORTRAN do loop in Figure 2.13, C for loops are flattened to lower level WHIRL. Lines 9-12 in Figure 2.14 contain the initial assignment to the induction variable, lines 14-25 contain the body, lines 27-31 contains the increment statement and lines 33-47 contain the iteration test.

2.3 WN management

To WN create and delete. There are functions in open64 that ease management of WHIRL nodes, viz to create, delete and iterate over them. While there is a generic create function, there are specialized forms of create functions for commonly encountered WNs which are recommended. Some example create utility function prototypes are presented in Figure 2.15. The first prototype, WN_Ldid, creates a LDID with pointer type given by argument "TYPE_ID desc" and with result type that is extracted from argument "ST* sym". The use of other arguments is explained in Section 2.2.1. The second prototype, WN_Add creates an ADD expression with type specified by argument “TYPE_ID rtype”, left child specified by argument “WN* l” and right child specified by argument “WN* r”. If a WN pointer is no longer necessary, developers can choose to delete the WN by using the WN_Delete function. The prototype for the WN_Delete function is also in Figure 2.15²³.

To WN iterate. Iterating over all WN in a BLOCK in statement order is possible by use of the WN_first, WN_prev and WN_next utility functions (as explained in 2.2.5). Iterating breadth first or depth first over children is possible by using the WN_kid utility functions, along with the WN_kidcount utility function.

To use memory management with memory pools. Open64 enables fixed-sized memory allocation with Memory Pool management. Most passes create a memory pool at start and free the pool at the end of the pass. Use of memory pools is recommended. The procedure to using memory pools are given below.

1. MEM_POOL_Initialize(MEMPOOL* mp, char* name, BOOL* bz). This macro must be invoked prior to using a memory pool. The argument MEMPOOL* mp is a pointer to the yet-to-be-initilialized MEMPOOL. char *name is used to hold a character string that can be used to printf for debugging. BOOL* bz when TRUE initializes the pool to zeroes.
2. MEM_POOL_Push (MEMPOOL* mp). After MEM_POOL_Initialize, MEM_POOL_Push macro must be invoked to enable dynamic allocations from this MEMPOOL. No memory allocation is possible from a MEM_POOL unless MEM_POOL_Initialize and MEM_POOL_Push are called on it.
3. CXX_NEW(constructor, mempool). Once MEM_POOL_Push has been invoked, compiler passes allocate from memory pool using CXX_NEW(constructor, mempool) macro with which a C++ object of a given type “constructor” can be created in the MEM_POOL “mempool”. CXX_NEW_ARRAY (constructor, elements, mempool) macro is used to create an array of “constructor” objects containing “elements” number of elements. CXX_DELETE (pointer, mempool) macro deletes “pointer” from “mempool” and CXX_DELETE_ARRAY (pointer, mempool) deletes arrays from mempool. CXX_* macros refer to C++ new and delete operators to enable memory allocation.
4. MEM_POOL_Pop (MEMPOOL* mp). When a MEM_POOL is no longer required, MEM_POOL_Pop macro is invoked. MEM_POOL_Pop frees all allocations from the argument “MEM_POOL* mp”.
5. WHIRL nodes are typically created in a global memory pool which is separate from the memory pools that developers use for other purposes. Annotation is one such instance. MEM_POOLs are typically used to store annotations or allocate compiler pass-specific data structures.
6. Recommended further reading: Source file comments in osprey/common/util/mempool.h

2.4 Annotations in WHIRL

Annotations are possible for WNs with the use of the WN_MAP_TAB data structure. WN_MAP_TAB is a collection of maps that map a given WN* against its annotation. There is a WN_MAP_TAB for each PU. WN_MAP_TAB holds all annotation tables for its PU and each of the annotation tables are identified witha WN_MAP integral identifier. Developers are pointed to the comments in osprey/common/com/wn_map.h and osprey/common/com/wn_map.cxx. A typical usage scenario for creating a new WN_MAP and adding annotations is given below.

• WN_MAP_Create (MEM_POOL* mp). This creates a new annotation map and returns its id which with type WN_MAP. WN_MAP represents an integral value.
• WN_MAP_Delete (WN_MAP u). This deletes the annotation map identified with the argument “WN_MAP u”.
• WN_MAP_Set (WN_MAP u, WN* wn1, X x). This utility macro is used to set an annotation for argument “WN* wn1” in the map identified by argument “WN_MAP u” to argument “X x”. The type X must either be void *, INT32, or INT64, where INT32 and INT64 are types that hold integers of 32 bits and 64 bits respectively.
• WN_MAP_Get (WN_MAP u, WN* wn1). This utility macro is used to obtain the annotation for “WN* wn1”.
• Recommended further reading: any of the optimization passes which make use of WN_MAP perhaps from osprey/be/lno directory

Chapter 3
WHIRL lowering

3.1 Control flow graph and Control flow analysis: dominators, natural loops

3.2 SSA form

Bibliography

¹The examples in this document are compiled to 64-bit x86_64 object code. Consequently pointers are 8-bytes long. If the examples are compiled to 32-bit object files, the pointers will be 4-bytes long.
²For further prototypes, please refer to the “osprey/common/com/wn.cxx” source file or this web page: http://www-rocq.inria.fr/~pop/doc/common/wn.txt.
³It is important to note that WN is managed as pointers. Developers need to be congnizant of this fact prior to deleting or pointing to or changing the content of a given WHIRL node.