[Bug c/84646] New: Missed optimisation for hoisting conditions outside nested loops

[david at westcontrol dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84646

            Bug ID: 84646
           Summary: Missed optimisation for hoisting conditions outside
                    nested loops
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: david at westcontrol dot com
  Target Milestone: ---

This is a missed optimisation opportunity.  In a discussion about the "best"
way to break out of a nested loop, I tested this code with gcc:

int foo(const int * p, const int * q, int m, int n) {
    int sum = 0;
    bool running = true;
    const int max = 20000;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (running) {
                sum += (p[i] * q[j]);
                if (sum >= max) {
                    running = false;
                    sum = max;
                }
            }
        }
    }
    return sum;
}


The test for "running" is hoisted outside the inner loop, so that the generated
code is changed to approximately:

int foo(const int * p, const int * q, int m, int n) {
    int sum = 0;
    bool running = true;
    const int max = 20000;
    for (int i = 0; i < n; i++) {
loop:
        if (running) {
            for (int j = 0; j < m; j++) {
                sum += (p[i] * q[j]);
                if (sum >= max) {
                    running = false;
                    sum = max;
                    goto loop;
                }
            }
        }
    }
    return sum;
}

This is definitely a good step - avoiding the check for "running" in the inner
loop, and breaking out of it when the max condition is reached is a clear win. 
But it would be even nicer if the check could be hoisted further - the
"running" flag could be completely eliminated to give the transformation:

int foo(const int * p, const int * q, int m, int n) {
    int sum = 0;
    //bool running = true;
    const int max = 20000;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (running) {
                sum += (p[i] * q[j]);
                if (sum >= max) {
                    //running = false;
                    sum = max;
                    goto exit;
                }
            }
        }
    }
exit:
    return sum;
}


Testing was done with -O2 and -O3, on a variety of gcc versions and targets
(thanks, godbolt.org!) up to version 8.0 (trunk at this time).  The generated
code showed approximately the same transformations and optimisations.