[Bug tree-optimization/64322] New: More optimize opportunity for constant folding

[Bug tree-optimization/64322] New: More optimize opportunity for constant folding

[ishiura-compiler at ml dot kwansei.ac.jp]

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

            Bug ID: 64322
           Summary: More optimize opportunity for constant folding
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ishiura-compiler at ml dot kwansei.ac.jp

The two programs (A.c) and (B.c) only differ by one line
(marked by "// <---HERE"), where (B.c) change 0x100000000L to 0L.

Resulting codes by "x86_64-unknown-linux-gnu-gcc-5.0.0 -Os -S"
are different;
the code (A.s) for (A.c) is less optimized than (B.s) for (B.c).
Note that variable c is not referenced at all in this program.

(A.c)
int main (void)
{
          long a = -1L;
 volatile long b =  0L;
 volatile long c = 0x100000000L;      // <---HERE
 a = (1+b >> 63 << 1) / 0x100000000L;

 if (a == 0L);
 else __builtin_abort();

 return 0;
}

(B.c)
int main (void)
{
          long a = -1L;
 volatile long b =  0L;
 volatile long c =  0L;               // <---HERE
 a = (1+b >> 63 << 1) / 0x100000000L;

 if (a == 0L);
 else __builtin_abort();

 return 0;
}

+-----------------------------+-----------------------------+
|(A.s)                        |(B.s)                        |
+-----------------------------+-----------------------------+
|main:                        |main:                        |
|.LFB0:                       |.LFB0:                       |
|  .cfi_startproc             |  .cfi_startproc             |
|  subq  $24, %rsp            |  movq  $0, -24(%rsp)        |
|  .cfi_def_cfa_offset 32     |  movq  $0, -16(%rsp)        |
|  movabsq  $4294967296, %rcx |  movq  -24(%rsp), %rax      |
|  movq  $0, (%rsp)           |                             |
|  movq  %rcx, 8(%rsp)        |                             |
|  movq  (%rsp), %rax         |                             |
|  incq  %rax                 |                             |
|  sarq  $63, %rax            |                             |
|  addq  %rax, %rax           |                             |
|  cqto                       |                             |
|  idivq  %rcx                |                             |
|  testq  %rax, %rax          |                             |
|  je  .L2                    |                             |
|  call  abort                |                             |
|.L2:                         |                             |
|  xorl  %eax, %eax           |  xorl  %eax, %eax           |
|  addq  $24, %rsp            |                             |
|  .cfi_def_cfa_offset 8      |                             |
|  ret                        |  ret                        |
|  .cfi_endproc               |  .cfi_endproc               |
|.LHOTE0:                     |.LHOTE0:                     |
+-----------------------------+-----------------------------+

$ x86_64-unknown-linux-gnu-gcc-5.0.0 -v
Using built-in specs.
COLLECT_GCC=x86_64-unknown-linux-gnu-gcc-5.0.0
COLLECT_LTO_WRAPPER=/usr/local/x86_64-tools/gcc-5.0.0/libexec/gcc/x86_64-unknown-linux-gnu/5.0.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: /home/hassy/gcc/configure
--prefix=/usr/local/x86_64-tools/gcc-5.0.0/
--with-gmp=/usr/local/gmp-5.1.1/ --with-mpfr=/usr/local/mpfr-3.1.2/
--with-mpc=/usr/local/mpc-1.0.1/ --disable-multilib --disable-nls
--enable-languages=c
Thread model: posix
gcc version 5.0.0 20141215 (experimental) (GCC)

[Bug tree-optimization/64322] More optimize opportunity for constant folding

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
First of all, I wonder why already VRP can't handle this.
To do so it would need to add RSHIFT_EXPR to the codes that we handle different
range kinds form (like PLUS_EXPR, BIT_AND_EXPR etc.), and simply if the second
range is range_int_cst_p and the first range is not VR_RANGE, just pretend the
first range is VR_RANGE from min to max value.  Say on the x >> 63 from the
testcase it should figure out the VR is [-1, 0] and thus for double that
[-2, 0] and for division by 0x100000000L that it must be 0.

[Bug tree-optimization/64322] More optimize opportunity for constant folding

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-12-16
     Ever confirmed|0                           |1

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Well, I rather wonder how the store to an otherwise unused value can affect
the code.  It doesn't on the GIMPLE level.  I suppose RTL somehow invalidly
thinks that after b = 0; c = 0; b is still zero (so it only considers the
two volatiles aliasing but doesn't consider the b volatile).

It seems to be combine optimizing the case with c = 0, not sure why it doens't
with c = 0x1000000L.  Ah, the large constant is split to a reg.

Difference:

-Successfully matched this instruction:
-(set (reg:DI 98)
-    (ashift:DI (reg:DI 94 [ D.1849 ])
-        (const_int 1 [0x1])))
-Successfully matched this instruction:
-(set (reg:DI 97 [ a ])
-    (const_int 0 [0]))
-allowing combination of insns 10, 11 and 12
-original costs 4 + 3 + 0 = 0
-replacement costs 6 + 4 = 10
-deferring deletion of insn with uid = 10.
-modifying insn i2    11: {r98:DI=r94:DI<<0x1;clobber flags:CC;}

Otherwise I agree with Jakub that VRP should be enhanced (it's weak with
handling non-initeger-VR_RANGES for most codes).

But combine probably exposes a RTL simplification so I wonder if we can
add a similar one (after figuring out which one applies) on the GIMPLE level.

Confirmed (at -O2 both codes are bad).

[Bug tree-optimization/64322] More optimize opportunity for constant folding

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
For VRP I'm thinking of (completely untested):
--- gcc/tree-vrp.c.jj    2014-12-01 14:57:30.000000000 +0100
+++ gcc/tree-vrp.c    2014-12-16 10:17:27.543111649 +0100
@@ -2434,6 +2434,7 @@ extract_range_from_binary_expr_1 (value_
       && code != MAX_EXPR
       && code != PLUS_EXPR
       && code != MINUS_EXPR
+      && code != RSHIFT_EXPR
       && (vr0.type == VR_VARYING
       || vr1.type == VR_VARYING
       || vr0.type != vr1.type
@@ -2948,6 +2949,15 @@ extract_range_from_binary_expr_1 (value_
     {
       if (code == RSHIFT_EXPR)
         {
+          /* Even if vr0 is VARYING or otherwise not usable, we can derive
+         useful ranges just from the shift count.  E.g.
+         x >> 63 for signed 64-bit x is always [-1, 0].  */
+          if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
+        {
+          vr0.type = type = VR_RANGE;
+          vr0.min = vrp_val_min (expr_type);
+          vr0.max = vrp_val_max (expr_type);
+        }
           extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
           return;
         }

[Bug tree-optimization/64322] More optimize opportunity for constant folding

[rguenth at gcc dot gnu.org]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="UTF-8", Size: 9784 bytes --]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #3)
> For VRP I'm thinking of (completely untested):
> --- gcc/tree-vrp.c.jj	2014-12-01 14:57:30.000000000 +0100
> +++ gcc/tree-vrp.c	2014-12-16 10:17:27.543111649 +0100
> @@ -2434,6 +2434,7 @@ extract_range_from_binary_expr_1 (value_
>        && code != MAX_EXPR
>        && code != PLUS_EXPR
>        && code != MINUS_EXPR
> +      && code != RSHIFT_EXPR
>        && (vr0.type == VR_VARYING
>  	  || vr1.type == VR_VARYING
>  	  || vr0.type != vr1.type
> @@ -2948,6 +2949,15 @@ extract_range_from_binary_expr_1 (value_
>  	{
>  	  if (code == RSHIFT_EXPR)
>  	    {
> +	      /* Even if vr0 is VARYING or otherwise not usable, we can derive
> +		 useful ranges just from the shift count.  E.g.
> +		 x >> 63 for signed 64-bit x is always [-1, 0].  */
> +	      if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
> +		{
> +		  vr0.type = type = VR_RANGE;
> +		  vr0.min = vrp_val_min (expr_type);
> +		  vr0.max = vrp_val_max (expr_type);
> +		}

Yeah, that should work.  We should probably simply handle all operation
codes that do not explicitely handle non-simple VR_RANGEs by promoting
all operands that way (also handle the single-VR_UNDEFINED op case and
VR_VARYING generally that way).  The DIV and MOD_EXPR cases look like
they would benefit from that.

>  	      extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
>  	      return;
>  	    }
>From gcc-bugs-return-470857-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue Dec 16 11:58:46 2014
Return-Path: <gcc-bugs-return-470857-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 19962 invoked by alias); 16 Dec 2014 11:58:46 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 19911 invoked by uid 48); 16 Dec 2014 11:58:42 -0000
From: "jakub at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/64322] More optimize opportunity for constant folding
Date: Tue, 16 Dec 2014 11:58:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords: missed-optimization
X-Bugzilla-Severity: normal
X-Bugzilla-Who: jakub at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-64322-4-pWR8dwcmwz@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-64322-4@http.gcc.gnu.org/bugzilla/>
References: <bug-64322-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-12/txt/msg01864.txt.bz2
Content-length: 1896

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> (In reply to Jakub Jelinek from comment #3)
> > For VRP I'm thinking of (completely untested):
> > --- gcc/tree-vrp.c.jj	2014-12-01 14:57:30.000000000 +0100
> > +++ gcc/tree-vrp.c	2014-12-16 10:17:27.543111649 +0100
> > @@ -2434,6 +2434,7 @@ extract_range_from_binary_expr_1 (value_
> >        && code != MAX_EXPR
> >        && code != PLUS_EXPR
> >        && code != MINUS_EXPR
> > +      && code != RSHIFT_EXPR
> >        && (vr0.type == VR_VARYING
> >  	  || vr1.type == VR_VARYING
> >  	  || vr0.type != vr1.type
> > @@ -2948,6 +2949,15 @@ extract_range_from_binary_expr_1 (value_
> >  	{
> >  	  if (code == RSHIFT_EXPR)
> >  	    {
> > +	      /* Even if vr0 is VARYING or otherwise not usable, we can derive
> > +		 useful ranges just from the shift count.  E.g.
> > +		 x >> 63 for signed 64-bit x is always [-1, 0].  */
> > +	      if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
> > +		{
> > +		  vr0.type = type = VR_RANGE;
> > +		  vr0.min = vrp_val_min (expr_type);
> > +		  vr0.max = vrp_val_max (expr_type);
> > +		}
> 
> Yeah, that should work.  We should probably simply handle all operation
> codes that do not explicitely handle non-simple VR_RANGEs by promoting
> all operands that way (also handle the single-VR_UNDEFINED op case and
> VR_VARYING generally that way).  The DIV and MOD_EXPR cases look like
> they would benefit from that

DIV and MOD already handle it (DIV quite similarly to this).  And from the list
of codes that extract_range_from_binary_expr_1 handles, I think RSHIFT_EXPR is
the only one that (for certain VR_RANGEs of one argument) can decrease a
VR_VARYING into something narrower and didn't handle arbitrary ranges of the
other operand yet.
>From gcc-bugs-return-470858-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue Dec 16 12:03:44 2014
Return-Path: <gcc-bugs-return-470858-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 22332 invoked by alias); 16 Dec 2014 12:03:44 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 22311 invoked by uid 48); 16 Dec 2014 12:03:40 -0000
From: "will at benfold dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/64329] New: Crash when returning reference from lambda with deduced type
Date: Tue, 16 Dec 2014 12:03:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c++
X-Bugzilla-Version: 4.9.1
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: will at benfold dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter attachments.created
Message-ID: <bug-64329-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-12/txt/msg01865.txt.bz2
Content-length: 2669

https://gcc.gnu.org/bugzilla/show_bug.cgi?idd329

            Bug ID: 64329
           Summary: Crash when returning reference from lambda with
                    deduced type
           Product: gcc
           Version: 4.9.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: will at benfold dot com

Created attachment 34289
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id4289&actioníit
Preprocessed source

I believe the program below is valid and correct, but I see heap corruption at
the end of main() (in  std::map::~map) when I allow the compiler to deduce
return type of the lambda.

Both the parameters to apply() are still alive when the returned lambda is
invoked, so fn(arg) should safely return a valid const ref to a tuple.  If the
return type for the lambda is given explicitly (see comments in code) then
everything is fine, whether it's returning by value or by const ref.

Compiling with "-Wall --std=c++11 -O0 -g3"; optimisation level seems to make no
difference.

----------------------------------------------------------------

#include <functional>
#include <map>
#include <string>
#include <tuple>

typedef std::tuple<std::string, std::string, double> Result;
typedef std::map<int, Result> Argument;
typedef std::function<const Result & (const Argument &)> Function;

std::function<Result ()> apply (const Argument &arg, const Function &fn)
{
  //  No trouble with any of these...
  //  return [&fn, &arg]() -> Result          { return fn(arg); };
  //  return [&fn, &arg]() -> const Result &  { return fn(arg); };
  //  return [&fn, &arg]()                    { Result r = fn(arg); return r;
};

  //  But this causes heap corruption
      return [&fn, &arg]()                    { return fn(arg); };
}

const Result &func (const Argument &arg)
{
  //  std::map::at returns a const ref
  return arg.at(0);
}

int main (int argc, char *argv[])
{
  Argument arg;
  arg[0] = Result("", "a", 0);

  Function f = &func;
  auto g = apply(arg, f);
  g();
  return 0;
}

----------------------------------------------------------------

Using built-in specs.
COLLECT_GCC=/software/thirdparty/gcc/4.9.1-0.el6_64/bin/g++
COLLECT_LTO_WRAPPER=/software/thirdparty/gcc/4.9.1-0.el6_64/libexec/gcc/x86_64-unknown-linux-gnu/4.9.1/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ../configure --prefix=/software/thirdparty/gcc/4.9.1-0.el6_64
--with-system-zlib --enable-shared --enable-threads=posix --enable-laguages=all
--with-ppl --with-cloog --disable-multilib
Thread model: posix
gcc version 4.9.1 (GCC)

[Bug tree-optimization/64322] More optimize opportunity for constant folding

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Wed Dec 17 09:29:12 2014
New Revision: 218812

URL: https://gcc.gnu.org/viewcvs?rev=218812&root=gcc&view=rev
Log:
    PR tree-optimization/64322
    * tree-vrp.c (extract_range_from_binary_expr_1): Attempt to derive
    range for RSHIFT_EXPR even if vr0 range is not VR_RANGE or is symbolic.

    * gcc.dg/tree-ssa/vrp95.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp95.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/64322] More optimize opportunity for constant folding

[jakub at gcc dot gnu.org]

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So, is this fix acceptable to the reporter?  The explanation in the combiner is
that in the first testcase you have multiple uses of the load of 0x100000000L
constant and therefore it is not attempted to be combined with the second use
(division), changing that is undesirable I think, combine is already expensive
as is.

[Bug tree-optimization/64322] More optimize opportunity for constant folding

[rguenther at suse dot de]

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

--- Comment #8 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 17 Dec 2014, jakub at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64322
> 
> --- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> --- So, is 
> this fix acceptable to the reporter?  The explanation in the combiner is 
> that in the first testcase you have multiple uses of the load of 
> 0x100000000L constant and therefore it is not attempted to be combined 
> with the second use (division), changing that is undesirable I think, 
> combine is already expensive as is.

True, though eventually changing this just for constants (thus
(const ...) and CONST_INT and ...) might be worth the additional
overhead.  I can imagine targets that don't support (large)
immediates being pessimized very much otherwise.

[Bug tree-optimization/64322] More optimize opportunity for constant folding

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
   Target Milestone|---                         |5.0
             Status|NEW                         |RESOLVED

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #10)
> (In reply to Martin Liška from comment #9)
> > Can the bug be marked as resolved?
> 
> Did you check?  At -Os we now produce for A
> 
>         movq    $0, -16(%rsp)
>         movl    $1, %eax
>         salq    $32, %rax
>         movq    %rax, -8(%rsp)
>         movq    -16(%rsp), %rax
>         xorl    %eax, %eax
>         ret

 movabs $0x100000000,%rax
is 10 bytes while
 mov    $0x1,%eax
 shl    $0x20,%rax
is also 9 bytes.

Counting instructions on x86_64 with -Os is not always the best thing to do :).

Yes it is fixed and even improved.