Bug 15784 - fold misses binary optimization
Summary: fold misses binary optimization
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.0.0
: P2 enhancement
Target Milestone: 4.1.0
Assignee: James A. Morrison
URL:
Keywords: missed-optimization, patch, TREE
Depends on:
Blocks: 19986 20130
  Show dependency treegraph
 
Reported: 2004-06-02 20:45 UTC by Andrew Pinski
Modified: 2005-03-11 05:03 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2004-12-26 14:40:54


Attachments
not/negate folding testcase (149 bytes, text/plain)
2005-02-11 05:48 UTC, James A. Morrison
Details
Actual fold patch (509 bytes, patch)
2005-02-11 05:51 UTC, James A. Morrison
Details | Diff
fold patch, after rth's complex math patch (495 bytes, patch)
2005-02-12 14:18 UTC, James A. Morrison
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andrew Pinski 2004-06-02 20:45:33 UTC
int f(int x)
{
  return x & ~x;  // should be 0 before getting to the RTL level
}
int h(int x)
{
  return x | ~x; // should be -1 before getting to the RTL level
}
Comment 1 Andrew Pinski 2004-06-02 21:22:37 UTC
int f(int x)
{
  return  ~x + 1; // -x
}
Comment 2 Andrew Pinski 2004-06-02 21:24:23 UTC
int f(int x)
{
  return -1 - x; // ~a
}
Comment 3 Andrew Pinski 2004-06-02 21:25:37 UTC
int f(int x)
{
  return x*9 - x; // x*8
}
Comment 4 Andrew Pinski 2004-06-02 21:26:38 UTC
int f(int x)
{
  return -x - 9; // -9 - x
}
Comment 5 Andrew Pinski 2004-06-02 22:23:56 UTC
int f(int x, int y)
{
  return 0/x; // 0
}
int g(int x, int y)
{
  return 0%x; // 0
}
Comment 6 Andrew Pinski 2004-06-02 22:39:41 UTC
int f(int x, int y)
{
  return x - y - x; // -y
}

#define abs(x) x>0?x:-x
int f(int x, int y)
{
  return (abs(x)) >= 0; //1
}
Comment 7 Andrew Pinski 2004-06-03 00:31:09 UTC
#define abs(x) x>0?x:-x
int f(int x, int y)
{
  return (abs(x)) == 0;
}
Comment 8 Andrew Pinski 2004-06-26 20:22:52 UTC
Confirmed.
Comment 9 Andrew Pinski 2004-06-27 17:25:58 UTC
Note the ones in Comment #0, are fixed by: <http://gcc.gnu.org/ml/gcc-patches/2004-06/
msg02250.html>.
Comment 10 Kazu Hirata 2004-07-04 07:43:49 UTC
Strictly speaking, Comments #6 and #7 do not qualify for "TREE" keyword.
Comment 11 Andrew Pinski 2004-07-04 07:49:27 UTC
Actually they do on PowerPC.
Comment 12 Andrew Pinski 2004-07-04 08:01:17 UTC
oh, here is why the last two happen on PowerPC and not on i?86, there is an abs pattern for POWER so 
we (rs6000) have to a split for the abs so the large number of optimizations can happen before we get 
to the point which we split the insn.  On i686, it is split/expanded right during expand instead of 
waiting until after reload which is what is done on PowerPC.

Also I got all of these by looking into the simplify-rtx.c file so this should be nothing different from 
there.
Comment 13 James A. Morrison 2005-02-11 05:48:45 UTC
Created attachment 8172 [details]
not/negate folding testcase
Comment 14 James A. Morrison 2005-02-11 05:51:28 UTC
Created attachment 8173 [details]
Actual fold patch

 Do the folding.
Comment 15 James A. Morrison 2005-02-12 14:18:51 UTC
Created attachment 8185 [details]
fold patch, after rth's complex math patch
Comment 16 CVS Commits 2005-02-13 06:21:45 UTC
Subject: Bug 15784

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	phython@gcc.gnu.org	2005-02-13 06:21:36

Modified files:
	gcc            : ChangeLog fold-const.c 

Log message:
	2005-02-13  James A. Morrison  <phython@gcc.gnu.org>
	
	PR tree-optimization/14303
	PR tree-optimization/15784
	* fold-const.c (fold): Fold ABS_EXPR<x> >= 0 to true, when possible.
	Fold ABS_EXPR<x> < 0 to false.  Fold ABS_EXPR<x> == 0 to x == 0 and
	ABS_EXPR<x> != 0 to x != 0.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7460&r2=2.7461
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fold-const.c.diff?cvsroot=gcc&r1=1.506&r2=1.507

Comment 17 Andrew Pinski 2005-02-16 05:38:26 UTC
Patch here: <http://gcc.gnu.org/ml/gcc-patches/2005-02/msg00905.html>.  Thanks James for 
looking into this.
Comment 18 CVS Commits 2005-03-04 02:49:15 UTC
Subject: Bug 15784

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	phython@gcc.gnu.org	2005-03-04 02:48:32

Modified files:
	gcc            : ChangeLog fold-const.c 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.dg: pr15784-4.c 

Log message:
	2005-03-03  James A. Morrison  <phython@gcc.gnu.org>
	
	PR tree-optimization/15784
	* fold-const.c (fold): Fold ~A + 1 to -1.  Fold -A - 1
	and -1 - A to ~A.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7657&r2=2.7658
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fold-const.c.diff?cvsroot=gcc&r1=1.520&r2=1.521
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5106&r2=1.5107
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/pr15784-4.c.diff?cvsroot=gcc&r1=NONE&r2=1.1

Comment 19 James A. Morrison 2005-03-04 02:55:26 UTC
The binary conditions below are all folded now.
Comment 20 CVS Commits 2005-03-04 06:24:25 UTC
Subject: Bug 15784

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	pinskia@gcc.gnu.org	2005-03-04 06:24:12

Modified files:
	gcc            : ChangeLog fold-const.c 

Log message:
	2005-03-04  Andrew Pinski  <pinskia@physics.uc.edu>
	
	Revert for now:
	2005-03-03  James A. Morrison  <phython@gcc.gnu.org>
	PR tree-optimization/15784
	* fold-const.c (fold): Fold ~A + 1 to -1.  Fold -A - 1
	and -1 - A to ~A.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7662&r2=2.7663
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fold-const.c.diff?cvsroot=gcc&r1=1.522&r2=1.523

Comment 21 Andrew Pinski 2005-03-04 06:26:19 UTC
Reopening as this patch had to reverted as it caused a bootstrap failure on ppc-darwin.  I think there 
really is a latent bug with -1 - A being converted to ~A and then ~A is constant folded to -1 but it 
contains a TREE_OVERFLOW bit turned on which it did not with -1 - A before.  (there might be some 
unsignedness going on that I don't know about).
Comment 22 Steven Bosscher 2005-03-08 00:21:44 UTC
More on the latent bug that the patch for this PR uncovers: 
http://gcc.gnu.org/ml/gcc-patches/2005-03/msg00448.html 
Comment 23 CVS Commits 2005-03-11 04:52:55 UTC
Subject: Bug 15784

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	law@gcc.gnu.org	2005-03-11 04:52:44

Modified files:
	gcc            : ChangeLog fold-const.c stmt.c 

Log message:
	PR tree-optimization/15784
	* fold-const.c (fold): Fold ~A + 1 to -A.  Fold -A - 1
	and -1 - A to ~A.
	
	* stmt.c (expand_case): Don't change index_type.  Convert minval
	to the proper type.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7782&r2=2.7783
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fold-const.c.diff?cvsroot=gcc&r1=1.540&r2=1.541
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/stmt.c.diff?cvsroot=gcc&r1=1.417&r2=1.418

Comment 24 James A. Morrison 2005-03-11 05:03:33 UTC
 Jeff Law rechecked in the patch for this bug.