Bug 15256 - [tree-ssa] Optimize manual bitfield manipilation.
Summary: [tree-ssa] Optimize manual bitfield manipilation.
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: tree-ssa
: P2 enhancement
Target Milestone: 6.0
Assignee: Andrew Pinski
URL:
Keywords: missed-optimization
Depends on: 15459
Blocks: 19466 19987
  Show dependency treegraph
 
Reported: 2004-05-03 08:03 UTC by Kazu Hirata
Modified: 2016-06-29 13:49 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2006-03-02 14:24:48


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Kazu Hirata 2004-05-03 08:03:52 UTC
It would be nice if we can convert foo into bar.

unsigned int
foo (unsigned int eax)
{
  unsigned int edx = eax & 1;
  edx ^= 1;
  eax &= -2;
  eax |= edx;
  return eax;
}

unsigned int
bar (unsigned int eax)
{
  return eax ^ 1;
}

The last SSA form looks like:

foo (eax)
{
  unsigned int edx;

<bb 0>:
  edx_2 = eax_1 & 1;
  edx_3 = edx_2 ^ 1;
  eax_4 = eax_1 & 0fffffffe;
  eax_5 = eax_4 | edx_3;
  return eax_5;

}

This testcase is inspired by

http://gcc.gnu.org/ml/gcc-patches/2004-05/msg00058.html

This sequence of four instructions is a little too tough for the combiner to
chew as it only considers three insturctions at one time.

Note that some people manually implement bitfields
without relying on ":" in a struct.
Comment 1 Andrew Pinski 2004-05-03 11:23:38 UTC
Confirmed.
Comment 2 Segher Boessenkool 2004-05-18 11:45:27 UTC
Subject: Re:  New: [tree-ssa] Optimize manual bitfield manipilation.

The generic rule is

X | (Y ^ Z) == (X | Y) ^ Z      if X & (Y ^ Z) == 0

(because then it is just X ^ Y ^ Z -- dunno if you want to go
that far -- but that sure would be nice).

Segher

(everything should be canonicalized to (n)ands (and maybe xors)...
or == doubt == wrong).

Comment 3 Andrew Pinski 2005-05-01 04:16:42 UTC
If fold optimized the following function:

unsigned int
foo (unsigned int eax)
{
  return (eax & 1) ^ 1 | (eax & 0xfffffffe);
}

Then the tree combiner might be able to optimize the orginal one.
Comment 4 Richard Biener 2011-05-06 13:12:37 UTC
I also see related missed optimizations when lowering regular bitfield
ops:

  <unnamed-unsigned:8> BF.15;
  <unnamed-unsigned:8> BF.14;
  <unnamed-unsigned:8> BF.13;
  <unnamed-unsigned:8> BF.12;
  <unnamed-unsigned:8> BF.11;
  <unnamed-unsigned:8> BF.10;
  <unnamed-unsigned:32> D.2191;
  <unnamed-unsigned:32> BF.9;

<bb 2>:
  BF.9_2 = MEM[(struct S *)this_1(D)];
  D.2191_3 = BF.9_2 & 4294967292;
  BF.9_4 = D.2191_3 | 1;
  MEM[(struct S *)this_1(D)] = BF.9_4;
  BF.10_5 = MEM[(struct S *)this_1(D)];
  BF.10_6 = BF.10_5 | 4;
  BF.11_8 = BF.10_6 & 247;
  BF.12_10 = BF.11_8 | 16;
  BF.13_12 = BF.12_10 & 223;
  BF.14_14 = BF.13_12 | 64;
  BF.15_16 = BF.14_14 & 127;
  MEM[(struct S *)this_1(D)] = BF.15_16;
  return;

we should be able to optimize the |& chain easily (in forwprop, or in
reassoc by noting that we can associate |s last and &s first).
Comment 5 Richard Biener 2011-05-11 14:13:47 UTC
Author: rguenth
Date: Wed May 11 14:13:38 2011
New Revision: 173659

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173659
Log:
2011-05-11  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/15256
	* tree-ssa-forwprop.c (simplify_bitwise_binary): Canonicalize
	(A & B) | C, combine (A op CST1) op CST2.
	(tree_ssa_forward_propagate_single_use_vars): Only bother to
	visit assigns that have uses.

	* gcc.dg/tree-ssa/forwprop-14.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/forwprop-14.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-forwprop.c
Comment 6 Andrew Pinski 2012-02-15 07:47:54 UTC
First we want to fold "(eax & 1) ^ 1" into "(~eax) & 1)" and then we can fold:
"(eax_1 & ~N) | (~eax_1 & N)" into eax ^ N .
Comment 7 Richard Biener 2016-06-29 13:48:39 UTC
Fixed in GCC 6.
Comment 8 Richard Biener 2016-06-29 13:49:11 UTC
Author: rguenth
Date: Wed Jun 29 13:48:39 2016
New Revision: 237852

URL: https://gcc.gnu.org/viewcvs?rev=237852&root=gcc&view=rev
Log:
2016-06-29  Richard Biener  <rguenther@suse.de>

	PR middle-end/15256
	* gcc.dg/tree-ssa/forwprop-34.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/forwprop-34.c
Modified:
    trunk/gcc/testsuite/ChangeLog
Comment 9 Richard Biener 2016-06-29 13:49:27 UTC
.