Bug 88702

Summary: [8/9/10/11 regression] We do terrible job optimizing IsHTMLWhitespace from Firefox
Product: gcc Reporter: Jan Hubicka <hubicka>
Component: tree-optimizationAssignee: Martin Liška <marxin>
Status: RESOLVED FIXED    
Severity: normal CC: dimhen, egallager, guillaume, jakub, jamborm
Priority: P2 Keywords: missed-optimization
Version: 9.0   
Target Milestone: 11.0   
See Also: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96480
Host: Target:
Build: Known to work:
Known to fail: Last reconfirmed: 2019-10-31 00:00:00
Bug Depends on:    
Bug Blocks: 45375    

Description Jan Hubicka 2019-01-04 23:44:32 UTC
compiling:

int IsHTMLWhitespace(int aChar) {                         
  return aChar == 0x0009 || aChar == 0x000A ||              
         aChar == 0x000C || aChar == 0x000D ||              
         aChar == 0x0020;                                             
}
q(int a,int b, int c)
{
  return IsHTMLWhitespace (a) && IsHTMLWhitespace (b) && IsHTMLWhitespace (c);
}

we do quite funny things by ipa-splitting IsHTMLWhitespace:

IsHTMLWhitespace (int aChar)
{
  unsigned int aChar.1_1;
  unsigned int _2;
  _Bool _3;
  _Bool _4;
  _Bool _5;
  int iftmp.0_6;
  int iftmp.0_8;

  <bb 2> [100.00%]:
  aChar.1_1 = (unsigned int) aChar_7(D);
  _2 = aChar.1_1 + 4294967287;
  _3 = _2 <= 1;
  _4 = aChar_7(D) == 12;
  _5 = _3 | _4;
  if (_5 != 0)
    goto <bb 4>; [46.00%]
  else
    goto <bb 3>; [54.00%]

  <bb 3> [54.00%]:
  iftmp.0_8 = IsHTMLWhitespace.part.0 (aChar_7(D));

  <bb 4> [100.00%]:
  # iftmp.0_6 = PHI <1(2), iftmp.0_8(3)>
  return iftmp.0_6;

}

this is partly caused by the fact that we are not able to optimize early the sequence of compares to shift. In Firefox later we fail to inline the functions and produce some terrible code which slows down rerf-reftest/dep-check-1.html Firefox benchmark
Comment 1 Jakub Jelinek 2019-01-05 01:16:39 UTC
With what options?  I'm getting 3 bit tests both with -O2 and -O3, both when using C and C++.  And get that also if I rewrite the function to use a switch instead.
Comment 2 Jan Hubicka 2019-01-05 01:24:32 UTC
> With what options?  I'm getting 3 bit tests both with -O2 and -O3, both when
> using C and C++.  And get that also if I rewrite the function to use a switch
> instead.

-O2 -flto and then look into release_ssa dump.
In Firefox we then fail to inline things back together. I am debugging
that but already producing that at firstplace is bad.
Comment 3 Jakub Jelinek 2019-01-05 01:48:42 UTC
The only pass that can do about this (at least right now) is reassoc (both 1 and 2), which is too late for inlining.  So, either teach fnsplit not to separate multiple if comparisons of the same variable against constants, or schedule reasoc or just the maybe_optimize_range_tests part thereof in some early pass.
Comment 4 Jan Hubicka 2019-01-05 08:59:30 UTC
> The only pass that can do about this (at least right now) is reassoc (both 1
> and 2), which is too late for inlining.  So, either teach fnsplit not to
> separate multiple if comparisons of the same variable against constants, or
> schedule reasoc or just the maybe_optimize_range_tests part thereof in some
> early pass.

Yep, I also found out about reassoc.
Teaching fnsplit to pattern match this is just a partial solution - we
would still miscalculate size of function body for functions like this
(which indeed look quite common). I will experiment with early reassoc.

I kind of debugged what happens later. Because code is compiled with -O2
and growth gets positive for both inlines and functions are not inline,
we won't inline.
Comment 5 Richard Biener 2019-01-07 09:00:22 UTC
You could also add match.pd rules merging stuff pair-wise...

How's this a regression btw?
Comment 6 Jan Hubicka 2019-01-07 09:10:20 UTC
> You could also add match.pd rules merging stuff pair-wise...
> 
> How's this a regression btw?

I was comparing with GCC 6 build where inlining apparently happened.
I believe inlining happens again - I am waiting for benchmarks to
finish.

Honza
Comment 7 Martin Liška 2019-01-10 13:33:37 UTC
Just for the record, when rewriting the code with switch:

int IsHTMLWhitespace(int aChar) {                         
  switch (aChar) {
  case 0x0009:
  case 0x000A:
  case 0x000C:
  case 0x000D:
  case 0x0020:
    return 1;
  default:
    return 0;
  }
}

one gets a nice bit-test eventually:

  <bb 2> [local count: 1073741824]:
  _4 = (unsigned int) aChar_2(D);
  if (_4 > 32)
    goto <bb 4>; [20.00%]
  else
    goto <bb 3>; [80.00%]

  <bb 3> :
  _6 = 1 << _4;
  _7 = _6 & 4294981120;
  _8 = _7 != 0;
  _5 = (int) _8;

  <bb 4> [local count: 1073741824]:
  # _1 = PHI <_5(3), 0(2)>
  return _1;
Comment 8 Martin Liška 2019-02-05 13:08:45 UTC
Honza can you please create mozilla upstream bug where we can recommend to use switch instead of series of if conditions?
Comment 9 David Malcolm 2019-05-03 13:49:37 UTC
If using a switch is better than a series of tests against constants, would it make sense for the compiler to spot this case, and automatically convert the conditions to a switch?
Comment 10 Martin Liška 2019-05-03 13:51:34 UTC
(In reply to David Malcolm from comment #9)
> If using a switch is better than a series of tests against constants, would
> it make sense for the compiler to spot this case, and automatically convert
> the conditions to a switch?

Yes, we've got a PR for it somewhere..
Comment 11 Eric Gallager 2019-08-27 04:22:13 UTC
(In reply to Martin Liška from comment #10)
> (In reply to David Malcolm from comment #9)
> > If using a switch is better than a series of tests against constants, would
> > it make sense for the compiler to spot this case, and automatically convert
> > the conditions to a switch?
> 
> Yes, we've got a PR for it somewhere..

bug 46935? or bug 14799?
Comment 12 CVS Commits 2020-12-01 10:47:32 UTC
The master branch has been updated by Martin Liska <marxin@gcc.gnu.org>:

https://gcc.gnu.org/g:03eb09292ef228d1d12b5168cdd748583b1f992a

commit r11-5605-g03eb09292ef228d1d12b5168cdd748583b1f992a
Author: Martin Liska <mliska@suse.cz>
Date:   Fri Aug 28 10:26:13 2020 +0200

    Add if-chain to switch conversion pass.
    
    gcc/ChangeLog:
    
            PR tree-optimization/14799
            PR ipa/88702
            * Makefile.in: Add gimple-if-to-switch.o.
            * dbgcnt.def (DEBUG_COUNTER): Add new debug counter.
            * passes.def: Include new pass_if_to_switch pass.
            * timevar.def (TV_TREE_IF_TO_SWITCH): New timevar.
            * tree-pass.h (make_pass_if_to_switch): New.
            * tree-ssa-reassoc.c (struct operand_entry): Move to the header.
            (dump_range_entry): Move to header file.
            (debug_range_entry): Likewise.
            (no_side_effect_bb): Make it global.
            * tree-switch-conversion.h (simple_cluster::simple_cluster):
            Add inline for couple of functions in order to prevent error
            about multiple defined symbols.
            * gimple-if-to-switch.cc: New file.
            * tree-ssa-reassoc.h: New file.
    
    gcc/testsuite/ChangeLog:
    
            PR tree-optimization/14799
            PR ipa/88702
            * gcc.dg/tree-ssa/pr96480.c: Disable if-to-switch conversion.
            * gcc.dg/tree-ssa/reassoc-32.c: Likewise.
            * g++.dg/tree-ssa/if-to-switch-1.C: New test.
            * gcc.dg/tree-ssa/if-to-switch-1.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-2.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-3.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-4.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-5.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-6.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-7.c: New test.
            * gcc.dg/tree-ssa/if-to-switch-8.c: New test.
Comment 13 Martin Liška 2020-12-01 11:14:51 UTC
All right, this test-case will need one more small tweak.
I've got a patch candidate.
Comment 14 CVS Commits 2020-12-02 07:21:26 UTC
The master branch has been updated by Martin Liska <marxin@gcc.gnu.org>:

https://gcc.gnu.org/g:c961e94901eb793b1a18d431a1acf7f682eaf04f

commit r11-5642-gc961e94901eb793b1a18d431a1acf7f682eaf04f
Author: Martin Liska <mliska@suse.cz>
Date:   Tue Dec 1 12:18:46 2020 +0100

    if-to-switch: Support chain with 2 BBs.
    
    As seen in the test-case, even 2 BBs can handle interesting
    cases covered by a jump table or a bit-test.
    
    gcc/ChangeLog:
    
            PR tree-optimization/88702
            * gimple-if-to-switch.cc (pass_if_to_switch::execute):
            Require at least 2 BBs.
            * gimple-if-to-switch.cc (find_conditions): Require
            equal precision for low and high of a range.
    
    gcc/testsuite/ChangeLog:
    
            PR tree-optimization/88702
            * gcc.dg/tree-ssa/if-to-switch-9.c: New test.
Comment 15 Martin Liška 2020-12-02 07:38:46 UTC
Implemented on the current master.