RFC: Incomplete Draft Patches to Correct Errors in Loop Unrolling Frequencies (bugzilla problem 68212)

[Kelvin Nilsen <kdnilsen at linux dot vnet dot ibm dot com>]

This is a draft patch to partially address the concerns described in 
bugzilla problem report 
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68212). The patch is 
incomplete in the sense that there are some known shortcomings with 
nested loops which I am still working on.  I am sending this out for 
comments at this time because we would like these patches to be 
integrated into the GCC 6 release and want to begin responding to 
community feedback as soon as possible in order to make the integration 
possible.

The problem described in Bugzilla 68212 is that code produced by loop 
unrolling has incorrect block frequencies.  The erroneous block 
frequencies result because block frequencies are not adjusted to account 
for the execution contexts into which they are copied. These incorrect 
frequencies disable and confuse subsequent compiler optimizations.  The 
general idea of how we address this problem is two fold:

 1. Before a loop body is unpeeled into a pre-header location, we 
temporarily adjust the loop body frequencies to represent the values 
appropriate for the context into which the loop body is to be copied.

 2. After unrolling the loop body (by replicating the loop body (N-1) 
times within the loop), we recompute all frequencies associated with 
blocks contained within the loop.

Additional test programs will be added to the bugzilla report and will 
be integrated into the regression test suite as part of the final 
submission of this patch.

ChangeLog:

2015-11-07  Kelvin Nilsen <kelvin@gcc.gnu.org>

        * cfgloopmanip.h
        (in_loop_p): new extern declaration
        (zero_loop_frequencies): new extern declaration
        (increment_loop_frequencies): new extern declaration

        * cfgloopmanip.c
        (in_loop_p): new helper routine
        (zero_loop_frequencies): new helper routine
        (block_ladder_rung): new struct definition for helper routines
        (same_edge_p): new helper routine
        (in_edge_set_p): new helper routine
        (in_call_chain_p): new helper routine
        (recursively_zero_frequency): new helper routine
        (recursion_detected_p): new helper routine
        (in_loop_of_header_p): new helper routine
        (recursively_get_loop_blocks): new helper routine
        (get_loop_blocks): new helper routine
        (in_block_set_p): new helper routine
        (get_exit_edges_from_loop_blocks): new helper routine
        (zero_partial_loop_frequencies): new helper routine
        (recursively_increment_frequency): new helper routine
        (increment_loop_frequencies): new helper routine
        (internal): new helper routine
        (check_loop_frequency_integrity): new helper routine
        (set_zero_probability): added another parameter
        (duplicate_loop_to_header_edge): Add code to recompute loop 
body frequencies after blocks are replicated (unrolled) into the loop 
body. Introduce certain help routines because existing infrastructure 
routines are not reliable during typical executions of 
duplicate_loop_to_header_edge().

        * loop-unroll.c
        (unroll_loop_constant_iterations): After replicating the loop 
body within a loop, recompute the frequencies for all blocks contained 
within the loop.
        (unroll_loop_runtime_iterations):Before copying loop body to 
preheader location, temporarily adjust the loop body frequencies to 
represent the context into which the loop body will be copied. After 
replicating the loop body within a loop, recompute the frequencies for 
all blocks contained within the loop.

Attachment: svn.diffs
Description: Text document