r600-sb
=======

* * * * *

Debugging
---------

### Environment variables

-   **R600\_DEBUG**

    There are new flags:

    -   **sb** - Enable optimization of graphics shaders
    -   **sbcl** - Enable optimization of compute shaders (experimental)
    -   **sbdry** - Dry run, optimize but use source bytecode - 
        useful if you only want to check shader dumps 
        without the risk of lockups and other problems
    -   **sbstat** - Print optimization statistics (only time so far)
    -   **sbdump** - Print IR after some passes.

### Regression debugging

If there are any regressions as compared to the default backend
(R600\_SB=0), it's possible to use the following environment variables
to find the incorrectly optimized shader that causes the regression.

-   **R600\_SB\_DSKIP\_MODE** - allows to skip optimization for some
    shaders
    -   0 - disabled (default)
    -   1 - skip optimization for the shaders in the range
        [R600\_SB\_DSKIP\_START; R600\_SB\_DSKIP\_END], that is,
        optimize only the shaders that are not in this range
    -   2 - optimize only the shaders in the range
        [R600\_SB\_DSKIP\_START; R600\_SB\_DSKIP\_END]

-   **R600\_SB\_DSKIP\_START** - start of the range (1-based)

-   **R600\_SB\_DSKIP\_END** - end of the range (1-based)

Example - optimize only the shaders 5, 6, and 7:

    R600_SB_DSKIP_START=5 R600_SB_DSKIP_END=7 R600_SB_DSKIP_MODE=2

All shaders compiled by the application are numbered starting from 1,
the number of shaders used by the application may be obtained by running
it with "R600_DEBUG=sb,sbstat" - it will print "sb: shader \#index\#"
for each compiled shader.

After figuring out the total number of shaders used by the application,
the variables above allow to use bisection to find the shader that is
the cause of regression. E.g. if the application uses 100 shaders, we
can divide the range [1; 100] and run the application with the
optimization enabled only for the first half of the shaders:

    R600_SB_DSKIP_START=1 R600_SB_DSKIP_END=50 R600_SB_DSKIP_MODE=2 <app>

If the regression is reproduced with these parameters, then the failing
shader is in the range [1; 50], if it's not reproduced - then it's in
the range [51; 100]. Then we can divide the new range again and repeat
the testing, until we'll reduce the range to a single failing shader.

*NOTE: This method relies on the assumption that the application
produces the same sequence of the shaders on each run. It's not always
true - some applications may produce different sequences of the shaders,
in such cases the tools like apitrace may be used to record the trace
with the application, then this method may be applied when replaying the
trace - also this may be faster and/or more convenient than testing the
application itself.*

* * * * *

Intermediate Representation
---------------------------

### Values

All kinds of the operands (literal constants, references to kcache
constants, references to GPRs, etc) are currently represented by the
**value** class (possibly it makes sense to switch to hierarchy of
classes derived from **value** instead, to save some memory).

All values (except some pseudo values like the exec\_mask or predicate
register) represent 32bit scalar values - there are no vector values,
CF/FETCH instructions use groups of 4 values for src and dst operands.

### Nodes

Shader programs are represented using the tree data structure, some
nodes contain a list of subnodes.

#### Control flow nodes

Control flow information is represented using four special node types
(based on the ideas from [[1]](#references) )

-   **region\_node** - single-entry, single-exit region.

    All loops and if's in the program are enclosed in region nodes.
    Region nodes have two containers for phi nodes -
    region\_node::loop\_phi contains the phi expressions to be executed
    at the region entry, region\_node::phi contains the phi expressions
    to be executed at the region exit. It's the only type of the node
    that contains associated phi expressions.

-   **depart\_node** - "depart region \$id after { ... }"

    Depart target region (jump to exit point) after executing contained
    code.

-   **repeat\_node** - "repeat region \$id after { ... }"

    Repeat target region (jump to entry point) after executing contained
    code.

-   **if\_node** - "if (cond) { ... }"

    Execute contained code if condition is true. The difference from
    [[1]](#references) is that we don't have associated phi expressions
    for the **if\_node**, we enclose **if\_node** in the
    **region\_node** and store corresponding phi's in the
    **region\_node**, this allows more uniform handling.

The target region of depart and repeat nodes is always the region where
they are located (possibly in the nested region), there are no arbitrary
jumps/goto's - control flow in the program is always structured.

Typical control flow constructs can be represented as in the following
examples:

GLSL:

    if (cond) {
        < 1 >
    } else {
        < 2 >
    }

IR:

    region #0 {
        depart region #0 after {
            if (cond) {
                depart region #0 after {
                    < 1 >
                }
            }
            < 2 >
        }
        <region #0 phi nodes >
    }

GLSL:

    while (cond) {
        < 1 >
    }

IR:

    region #0 {
        <region #0 loop_phi nodes>
        repeat region #0 after {
            region #1 {
                depart region #1 after {
                    if (!cond) {
                        depart region #0
                    }
                }
            }
            < 1 >
        }
        <region #0 phi nodes>
    }

'Break' and 'continue' inside the loops are directly translated to the
depart and repeat nodes for the corresponding loop region.

This may look a bit too complicated, but in fact this allows more simple
and uniform handling of the control flow.

All loop\_phi and phi nodes for some region always have the same number
of source operands. The number of source operands for
region\_node::loop\_phi nodes is 1 + number of repeat nodes that
reference this region as a target. The number of source operands for
region\_node::phi nodes is equal to the number of depart nodes that
reference this region as a target. All depart/repeat nodes for the
region have unique indices equal to the index of source operand for
phi/loop\_phi nodes.

First source operand for region\_node::loop\_phi nodes (src[0]) is an
incoming value that enters the region from the outside. Each remaining
source operand comes from the corresponding repeat node.

More complex example:

GLSL:

    a = 1;
    while (a < 5) {
        a = a * 2;
        if (b == 3) {
            continue;
        } else {
            a = 6;
        }
        if (c == 4)
            break;
        a = a + 1;
    }

IR with SSA form:

    a.1 = 1;
    region #0 {
        // loop phi values: src[0] - incoming, src[1] - from repeat_1, src[2] - from repeat_2
        region#0 loop_phi: a.2 = phi a.1, a.6, a.3

        repeat_1 region #0 after {
            a.3 = a.2 * 2;
            cond1 = (b == 3);
            region #1 {
                depart_0 region #1 after {
                    if (cond1) {
                        repeat_2 region #0;
                    }
                }
                a.4 = 6;

                region #1 phi: a.5 = phi a.4; // src[0] - from depart_0
            }
            cond2 = (c == 4);
            region #2 {
                depart_0 region #2 after {
                    if (cond2) {
                        depart_0 region #0;
                    }
                }
            }
            a.6 = a.5 + 1;
        }

        region #0 phi: a.7 = phi a.5 // src[0] from depart_0
    }

Phi nodes with single source operand are just copies, they are not
really necessary, but this allows to handle all **depart\_node**s in the
uniform way.

#### Instruction nodes

Instruction nodes represent different kinds of instructions -
**alu\_node**, **cf\_node**, **fetch\_node**, etc. Each of them contains
the "bc" structure where all fields of the bytecode are stored (the type
is **bc\_alu** for **alu\_node**, etc). The operands are represented
using the vectors of pointers to **value** class (node::src, node::dst)

#### SSA-specific nodes

Phi nodes currently don't have special node class, they are stored as
**node**. Destination vector contains a single destination value, source
vector contains 1 or more source values.

Psi nodes [[5], [6]](#references) also don't have a special node class
and stored as **node**. Source vector contains 3 values for each source
operand - the **value** of predicate, **value** of corresponding
PRED\_SEL field, and the source **value** itself.

### Indirect addressing

Special kind of values (VLK\_RELREG) is used to represent indirect
operands. These values don't have SSA versions. The representation is
mostly based on the [[2]](#references). Indirect operand contains the
"offset/address" value (value::rel), (e.g. some SSA version of the AR
register value, though after some passes it may be any value - constant,
register, etc), also it contains the maydef and mayuse vectors of
pointers to **value**s (similar to dst/src vectors in the **node**) to
represent the effects of aliasing in the SSA form.

E.g. if we have the array R5.x ... R8.x and the following instruction :

    MOV R0.x, R[5 + AR].x

then source indirect operand is represented with the VLK\_RELREG value,
value::rel is AR, value::maydef is empty (in fact it always contain the
same number of elements as mayuse to simplify the handling, but they are
NULLs), value::mayuse contains [R5.x, R6.x, R7.x, R8.x] (or the
corresponding SSA versions after ssa\_rename).

Additional "virtual variables" as in [HSSA [2]](#references) are not
used, also there is no special handling for "zero versions". Typical
programs in our case are small, indirect addressing is rare, array sizes
are limited by max gpr number, so we don't really need to use special
tricks to avoid the explosion of value versions. Also this allows more
precise liveness computation for array elements without modifications to
the algorithms.

With the following instruction:

    MOV R[5+AR].x, R0.x

we'll have both maydef and mayuse vectors for dst operand filled with
array values initially: [R5.x, R6.x, R7.x, R8.x]. After the ssa\_rename
pass mayuse will contain previous versions, maydef will contain new
potentially-defined versions.

* * * * *

Passes
------

-   **bc\_parser** - creates the IR from the source bytecode,
    initializes src and dst value vectors for instruction nodes. Most
    ALU nodes have one dst operand and the number of source operands is
    equal to the number of source operands for the ISA instruction.
    Nodes for PREDSETxx instructions have 3 dst operands - dst[0] is dst
    gpr as in the original instruction, other two are pseudo-operands
    that represent possibly updated predicate and exec\_mask. Predicate
    values are used in the predicated alu instructions (node::pred),
    exec\_mask values are used in the if\_nodes (if\_node::cond). Each
    vector operand in the CF/TEX/VTX instructions is represented with 4
    values - components of the vector.

-   **ssa\_prepare** - creates phi expressions.

-   **ssa\_rename** - renames the values (assigns versions).

-   **liveness** - liveness computation, sets 'dead' flag for unused
    nodes and values, optionally computes interference information for
    the values.

-   **dce\_cleanup** - eliminates 'dead' nodes, also removes some
    unnecessary nodes created by bc\_parser, e.g. the nodes for the JUMP
    instructions in the source, containers for ALU groups (they were
    only needed for the ssa\_rename pass)

-   **if\_conversion** - converts control flow with if\_nodes to the
    data flow in cases where it can improve performance (small alu-only
    branches). Both branches are executed speculatively and the phi
    expressions are replaced with conditional moves (CNDxx) to select
    the final value using the same condition predicate as was used by
    the original if\_node. E.g. **if\_node** used dst[2] from PREDSETxx
    instruction, CNDxx now uses dst[0] from the same PREDSETxx
    instruction.

-   **peephole** - peephole optimizations

-   **gvn** - Global Value Numbering [[2]](#references),
    [[3]](#references)

-   **gcm** - Global Code Motion [[3]](#references). Also performs
    grouping of the instructions of the same kind (CF/FETCH/ALU).

-   register allocation passes, some ideas are used from
    [[4]](#references), but implementation is simplified to make it more
    efficient in terms of the compilation speed (e.g. no recursive
    recoloring) while achieving good enough results.

    -   **ra\_split** - prepares the program to register allocation.
        Splits live ranges for constrained values by inserting the
        copies to/from temporary values, so that the live range of the
        constrained values becomes minimal.

    -   **ra\_coalesce** - performs global allocation on registers used
        in CF/FETCH instructions. It's performed first to make sure they
        end up in the same GPR. Also tries to allocate all values
        involved in copies (inserted by the ra\_split pass) to the same
        register, so that the copies may be eliminated.

    -   **ra\_init** - allocates gpr arrays (if indirect addressing is
        used), and remaining values.

-   **post\_scheduler** - ALU scheduler, handles VLIW packing and
    performs the final register allocation for local values inside ALU
    clauses. Eliminates all coalesced copies (if src and dst of the copy
    are allocated to the same register).

-   **ra\_checker** - optional debugging pass that tries to catch basic
    errors of the scheduler or regalloc,

-   **bc\_finalize** - propagates the regalloc information from values
    in node::src and node::dst vectors to the bytecode fields, converts
    control flow structure (region/depart/repeat) to the target
    instructions (JUMP/ELSE/POP,
    LOOP\_START/LOOP\_END/LOOP\_CONTINUE/LOOP\_BREAK).

-   **bc\_builder** - builds final bytecode,

* * * * *

References
----------

[1] ["Tree-Based Code Optimization. A Thesis Proposal", Carl
McConnell](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.4210&rep=rep1&type=pdf)

[2] ["Effective Representation of Aliases and Indirect Memory Operations
in SSA Form", Fred Chow, Sun Chan, Shin-Ming Liu, Raymond Lo, Mark
Streich](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.6974&rep=rep1&type=pdf)

[3] ["Global Code Motion. Global Value Numbering.", Cliff
Click](http://www.cs.washington.edu/education/courses/cse501/06wi/reading/click-pldi95.pdf)

[4] ["Register Allocation for Programs in SSA Form", Sebastian
Hack](http://digbib.ubka.uni-karlsruhe.de/volltexte/documents/6532)

[5] ["An extension to the SSA representation for predicated code",
Francois de
Ferriere](http://www.cdl.uni-saarland.de/ssasem/talks/Francois.de.Ferriere.pdf)

[6] ["Improvements to the Psi-SSA Representation", F. de
Ferriere](http://www.scopesconf.org/scopes-07/presentations/3_Presentation.pdf)