Bug 4046 - redundant conditional branch
redundant conditional branch
Status: RESOLVED FIXED
Product: gcc
Classification: Unclassified
Component: rtl-optimization
3.0
: P3 normal
: ---
Assigned To: Not yet assigned to anyone
: missed-optimization
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2001-08-17 08:06 UTC by niemayer
Modified: 2003-07-25 17:33 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description niemayer 2001-08-17 08:06:01 UTC
The optimizer wasn't perfect in eliminating
redundant comparisons in gcc-2 (who's perfect anyway? :-) - 
but it seems to have become worse with gcc-3.0...

Release:
gcc-3.0, x86

Environment:
linux (but this doesn't matter)

How-To-Repeat:
take a look at the assembler output of this code:

#define compi2(x, y) \
( \
 ((x) < (y))? -1 : \
 (((x) > (y))? 1 : 0 ) \
)

int testcomp(void) {
   int r = 0;
   for (int x = 0; x < 10; x++) {
      for (int y = 0; y < 10; y++) {
         if (1 == compi(x,y)) {
            r++;
         }
      }
   }
   return r;
}

You'll find that the resulting assmbler code of the inner
if-clause contains a redundant jump when using gcc-2.x
(with -O3 and any other great optimizer switch I tried :-)
e.g.:

        cmpl %edx,%ecx
        jl .L1137
        jle .L1137
        incl %ebx
.L1137

With gcc-3.0 the same case becomes even worse, now there's
an addition redundant comparison:

    cmpl    %edx, %ecx
    jl      .L13
    cmpl    %edx, %ecx
    jle     .L13
    incl    %eax
.L13

When using an inline function like this

inline int compi(const int x, const int y) {
        if (x < y) return -1;
        if (x > y) return 1;
        return 0;
}

instead of the macro, the code gets even worse.

This is somehow a tragedy as it forbids us to just implement
one comparison function instead of operator<, operator> etc.
for each class...
Comment 1 Richard Henderson 2002-04-02 19:53:47 UTC
State-Changed-From-To: open->analyzed
State-Changed-Why: In gcc 3.1, the regression from gcc 2 is gone, i.e. we once again get
    
            jl      .L8
            jle     .L8
            incl    %eax
    .L8:
    
    However, I'm not closing the PR since we really should have
    eliminated one of the branches.
Comment 2 Roger Sayle 2002-07-01 19:51:35 UTC
State-Changed-From-To: analyzed->closed
State-Changed-Why: This problem has now been fixed on mainline CVS by the
    combination of the following two patches.  We now generate
    only a single branch in the GNATS testcase.
    
    2002-07-01  Roger Sayle  <roger@eyesopen.com>
    
            PR opt/4046
            * fold-const.c (fold) [COND_EXPR]: Simplify A ? 0 : 1 to !A,
            A ? B : 0 to A && B and A ? B : 1 into !A || B if both A and
            B are truth values.
    
    2002-06-15  Roger Sayle  <roger@eyesopen.com>
    
            * fold-const.c (comparison_to_compcode): New function to convert
            an comparison TREE CODE into a bit-based representation.
            (compcode_to_comparison): New function to convert from this bit
            based representation back to a comparison TREE CODE.
            (fold_truthop): Simplify (x<y) && (x==y) and related composite
            comparisons.