5.2. If Statements and Nested If Statements¶
In order for the compiler to software pipeline a loop (and thus improve performance), the only branch that may occur in a loop is a branch back to the top of the loop. Branches for if-then and if-then-else statements or for other control-flow constructs will prevent software pipelining.
The compiler tries to eliminate branches resulting from control-flow constructs when it can, in a process called if-conversion. If-conversion attempts to remove branches associated with if-then and if-then-else statements, by predicating instructions so that they conditionally execute depending on the test in the "if" statement. As long as there are not too many nesting levels, too many condition terms, or too many instructions in the if-then or if-then-else statements, if-conversion usually succeeds.
5.2.1. If-conversion Pseudo-Code Example¶
Let's walk through a pseudo-code example so we can better understand the if-conversion concept. Say we have the following code-snippet:
if (p) x=5; else x=7;
The compiler can if-convert this statement into the following:
[ p] x = 5
[!p] x = 7
Where the [] notation in this pseudo-code indicates conditional execution
of the instruction. In this case, the condition p controls execution of
the statement. Only when the condition is true (that is, not zero), the
instruction will be executed. The condition is also called a predicate.
After if-conversion, the branches are eliminated and the compiler can schedule these statements in any order or in parallel:
[ p] x = 5 [!p] x = 7 [ p] x = 5
or or
[!p] x = 7 [ p] x = 5 || [!p] x = 7
5.2.2. If-conversion Source Code Example¶
Now, let's walk through a real-life source code example that demonstrates if-conversion and look at the assembly code that is produced by the C7000 compiler. In order to software pipeline the "for" loop in this C++ code below, if-conversion must be performed.
Note that the pragmas in the code example below are used to prevent the compiler from vectorizing and generating additional code that is not important for this example.
// if_conversion.cpp
// Compile with "cl7x -mv7100 --opt_level=3 --debug_software_pipeline
// --src_interlist --symdebug:none if_conversion.cpp"
void function_1(int * restrict a, int *restrict b, int *restrict out, int n)
{
#pragma UNROLL(1)
#pragma MUST_ITERATE(1024, ,32)
for (int i = 0; i < n; i++)
{
int result;
if (a[i] < b[i])
result = a[i] + b[i];
else
result = 0;
out [i] = result;
}
}
After compilation, the single-scheduled iteration of the loop in the software pipeline information comment block looks like the following:
;*----------------------------------------------------------------------------*
;* SINGLE SCHEDULED ITERATION
;*
;* ||$C$C65||:
;* 0 TICK ; [A_U]
;* 1 SLDW .D1 *D2++(4),A1 ; [A_D1] |17| ^
;* || SLDW .D2 *D1++(4),A2 ; [A_D2] |17| ^
;* 2 NOP 0x5 ; [A_B]
;* 7 CMPGEW .L1 A2,A1,A0 ; [A_L1] |17| ^
;* 8 [!A0] ADDW .D2 A1,A2,D3 ; [A_D2] |17| ^
;* 9 [ A0] MVKU32 .S1 0,D3 ; [A_S1] |17|
;* 10 STW .D1 D3,*D0++(4) ; [A_D1] |17|
;* || BNL .B1 ||$C$C65|| ; [A_B] |9|
;* 11 ; BRANCHCC OCCURS {||$C$C65||} ; [] |9|
;*----------------------------------------------------------------------------
The instruction [!A0] ADDW.D2 A1,A2,D3 represents the
"then" part of the if statement. The instruction
[A0] MVK32.S1 0,D3 represents the "else" part of the if
statement. The CMPGEW instruction computes the if-condition and
puts the result into a predicate register, which is used to
conditionally execute the ADDW and MVKU32 instructions.
Note that there is no branch associated with the if-then-else statement
because it has been removed by the compiler when it performed if-conversion.
5.2.3. Benefits of if-conversion¶
If-conversion has a couple of benefits on the C7000 architecture. First, branches are eliminated. In general, if there are fewer branches in code executing on C7000, the resulting code will run faster. In addition, when branches are eliminated from inner loops, the compiler is able to software pipeline inner loops. Second, after if-conversion, the compiler can detect that statements from the body of the "then" have no ordering constraints with respect to statements in the body of the "else".
5.2.4. Which if-statements are if-converted¶
The C7000 compiler if-converts small and medium sized "if" statements.
The compiler will if-convert larger if-then and if-then-else statements
when an if-then or if-then-else statement is in an inner loop that might software pipeline.
It will also if-convert larger if-then and if-then-else statements when
larger values of the size/speed tradeoff option are used (--opt_for_speed).
The compiler does not if-convert large "if" statements ("if" statements where the "then" or "else" block is long). If a loop contains an "if" statement that was not converted, a message such as the following is generated:
;*----------------------------------------------------------------------------*
;* SOFTWARE PIPELINE INFORMATION
;* Disqualified loop: Loop contains control code
;*----------------------------------------------------------------------------*
The reason that the compiler does always perform conversion is that when "if" statements are large, if-conversion is not always profitable. For example, consider the following loop containing an "if" statement:
for (i=0; i<n; i++)
{
if (x[i])
{
<large "if" statement body>
}
}
If "x[i]" is usually 0, "x" is sparse. If "x[i]" is usually non-zero, "x" is dense. If "x" is sparse and the body of the "if" statement is long, if-conversion is not profitable. However, if "x" is dense, then if-conversion is profitable. Since the compiler does not know anything about "x", it does not automatically if-convert this "if" statement.
See If-Conversion Improvement for more about if-conversion.