Bug 37239 - peeling last iteration of a <= loop
peeling last iteration of a <= loop
Status: NEW
Product: gcc
Classification: Unclassified
Component: tree-optimization
4.3.2
: P3 enhancement
: ---
Assigned To: Not yet assigned to anyone
: missed-optimization
Depends on:
Blocks: 30521 37242 37240
  Show dependency treegraph
 
Reported: 2008-08-26 11:34 UTC by Paolo Bonzini
Modified: 2008-10-04 20:13 UTC (History)
5 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail: 4.4.0 4.2.3
Last reconfirmed: 2008-08-27 11:58:09


Attachments
benchmark (15.79 KB, text/plain)
2008-08-26 11:36 UTC, Paolo Bonzini
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Paolo Bonzini 2008-08-26 11:34:06 UTC
If the condition of the loop is tested within the loop with == or !=, it may be beneficial to peel off the final iteration of the loop by changing the condition to <.

This happens in the attached benchmark's heapsort function where

    while ((maxIdx += maxIdx) <= last) { 
        if (maxIdx != last && numbers[maxIdx] < numbers[maxIdx + 1]) maxIdx++;
        if (tmp >= numbers[maxIdx]) break;
        numbers[top] = numbers[maxIdx];
        top = maxIdx;
    }

can become

    while ((maxIdx += maxIdx) <= last) { 
        if (numbers[maxIdx] < numbers[maxIdx + 1]) maxIdx++;
        if (tmp >= numbers[maxIdx]) break;
        numbers[top] = numbers[maxIdx];
        top = maxIdx;
    }
    if (maxIdx == last && tmp < numbers[maxIdx]) {
        numbers[top] = numbers[maxIdx];
        top = maxIdx;
    }

enabling in turn if-conversion of the first branch.

Performance of the benchmark is (-O3)

    basic               2.990
    peeling only        2.730
    if-conversion only  2.290
    peel+if-convert     2.010   (faster than quicksort!!)

ICC does this optimization.
Comment 1 Paolo Bonzini 2008-08-26 11:36:02 UTC
Created attachment 16148 [details]
benchmark
Comment 2 Richard Biener 2008-08-27 11:58:09 UTC
Hm, I don't know if the loop optimization code can peel the last iteration.
Comment 3 Paolo Bonzini 2008-08-27 12:08:14 UTC
no, it does not and I think it should not except for this particular case (or other similar ones).