https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68212
Bug ID: 68212
Summary: Loop unroller breaks basic block frequencies
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c
Assignee: unassigned at gcc dot gnu.org
Reporter: kelvin.nilsen at gmail dot com
Target Milestone: ---
Here’s a very simple program to demonstrate the existing problems:
void foo(double *d, unsigned long int n) {
unsigned long int i;
for (i=0;i<n;i++)
d[i*2] = 0.0;
}
Compile using these options and examine the trace files (or insert your own
instrumentation) to verify my findings.
gcc -S -m64 -O3 -fno-tree-vectorize -funroll-loops --param
max-unroll-times=4 -da loop.c
The trace file loop.c.212r.loop2_doloop shows the intermediate representation
immediately following loop unrolling.
Before unrolling, we have the following (i’m providing meaningful names to some
of the compiler-generated temporary variables):
B0: /* the method prologue */
/* fall through to B2 (100% probability) */
B2: /* frequency: 900 */
d[reg 183] = ap[48]; /* fetch incoming argument into register 183 */
n[reg 184] = ap[56];
ivtmp.6[reg 178] = d;
end_of_d[reg 182] = ivtmp.6 + t;
if (o < n) goto B3; /* conditional jump to B3 with probability 91% */
else goto B4; /* “fall through" to B4 with probability 9% */
B3: /* frequency: 819 */
zero_preload[reg 187] = 0.0d;
/* fall through to B5 with probability 100% */
/* aside: the back edge of a loop is assumed to have probability 91%.
* This has the effect of treating the body of the loop as if its
* frequency is the incoming edge’s frequency divided by 0.09.
*/
B5: /* frequency 9100 = 819 (from B3) + 8281 (from B6) */
mem[ivtmp.6] = zero_preload;
ivtmp.6 += 16;
if (ivtmp.6 != end_of_d) goto B6; /* probability 91%, frequency 8281 =
91% of 9100 */
else goto B7; /* probability 9%, frequency 819 = 9% of 9100 */
B6: /* frequency 8281 */
/* no code */
goto B5; /* "fall through" with 100% probability, frequency 8281 */
B7: /* frequency 819 */
/* no code */
goto B4; /* “fall through” with 100% probability, frequency 819 */
B4: /* frequency 900 = 819 (from B7) + 81 (from B2) */
/* no code */
goto B1; /* “fall through” with 100% probability, frequency 900 */
B1: /* the method epilogue */
Note that for each basic block with multiple outgoing flows, the sum of the
probabilities on those outgoing flows always equals 100%.
Also, for any block that has multiple predecessors, the sum of the frequencies
associated with the incoming edges always equals the frequency of that block.
Here’s what the transformed program looks like following loop unrolling:
B0: /* the method prologue */
/* fall through to B2 (100% probability) */
B2: /* frequency 900 */
_16 = n << 4;
ivtmp.6 = d;
_17 = ivtmp.6 + _16;
if (0 < n) goto B3 /* fall-through, probability = 91%, frequency 819 */
else goto B4; /* probability 9%, frequency 81 */
B3: /* frequency 819 */
zero_preload = 0.0;
goto B8; /* fall through, probability 100%, frequency 819 */
B8: /* frequency 819 */
d_length = _17 - ivtmp.6;
extended_length = d_length - 16;
extended_element_count = extended_length >> 4;
mod4_elements = extended_element_count & 0x03;
goto B9; /* fall through, probability 100%, frequency 819 */
B9: /* frequency 819 */
*((double *) ivtmp.6) = zero_preload;
ivtmp.6 += 16;
if (ivtmp.6 == _17) goto B10; /* probability 91%, frequency 745 */
else goto B7; /* fall through, probability 9%, frequency 74 */
B10: /* frequency 745 */
/* no code */
goto BB23; /* fall through, probability 75%, frequency 559 */
/* WRONG: probability should be 100%, frequency should be 745 */
B23: /* frequency 497: WRONG: B10 is the only predecessor, frequency
* should be 559 based on existing B10 information
*/
if (mod4_elements == 0) goto B22; /* 25% probability, frequency 124 */
else goto BB19; /* fall through, probability 100%, frequency 497.
WRONG: should be probability 75%, frequency 373 */
B19: /* frequency: 373. INCONSISTENT with B23 data, but this is a correct
value by some standard. */
if (mod4_elements == 1) goto BB18; /* 33% probability, frequency 123
*/
else goto B15; /* fall-through, probability 100%, frequency 373.
WRONG: should be probability 67%, frequency 250 */
B15: /* frequency: 745. WRONG: only predecessor is B19, should be 373 as B19
is currently described */
if (mod4_elements == 2) goto B14; /* probability 50%, frequency = 373
*/
else goto B11; /* fall through,
