public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities
@ 2004-03-27 16:13 kazu at cs dot umass dot edu
  2004-03-27 16:17 ` [Bug optimization/14753] " pinskia at gcc dot gnu dot org
                   ` (9 more replies)
  0 siblings, 10 replies; 16+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-03-27 16:13 UTC (permalink / raw)
  To: gcc-bugs

void bar (void);

void
foo (unsigned int a)
{
  /* This one is equivalent to a >= (3 << 2).  */
  if ((a >> 2) >= 3)
    bar ();
}

void
baz (unsigned int a)
{
  /* This one is equivalent to a <= 7.  */
  if ((a & ~7) == 0)
    bar ();
}

The last tree in SSA form looks like:

;; Function foo (foo)

foo (a)
{
  unsigned int T.0;

<bb 0>:
  T.0_2 = a_1 >> 2;
  if (T.0_2 > 2) goto <L0>; else goto <L1>;

<L0>:;
  bar () [tail call];

<L1>:;
  return;

}



;; Function baz (baz)

baz (a)
{
  unsigned int T.1;

<bb 0>:
  T.1_2 = a_1 & 0fffffff8;
  if (T.1_2 == 0) goto <L0>; else goto <L1>;

<L0>:;
  bar () [tail call];

<L1>:;
  return;

}

Note that in baz(), if "a" were of int, we would first have to create
a temporary variable holding unsigned version of "a" before we can
use an ordered comparison.

-- 
           Summary: [tree-ssa] some missed forward propagation opportunities
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Keywords: pessimizes-code
          Severity: enhancement
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: kazu at cs dot umass dot edu
                CC: gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
@ 2004-03-27 16:17 ` pinskia at gcc dot gnu dot org
  2004-03-29  2:10 ` kazu at cs dot umass dot edu
                   ` (8 subsequent siblings)
  9 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-03-27 16:17 UTC (permalink / raw)
  To: gcc-bugs


------- Additional Comments From pinskia at gcc dot gnu dot org  2004-03-27 16:17 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-03-27 16:17:57
               date|                            |
   Target Milestone|---                         |tree-ssa


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
  2004-03-27 16:17 ` [Bug optimization/14753] " pinskia at gcc dot gnu dot org
@ 2004-03-29  2:10 ` kazu at cs dot umass dot edu
  2004-03-29 14:27 ` kazu at cs dot umass dot edu
                   ` (7 subsequent siblings)
  9 siblings, 0 replies; 16+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-03-29  2:10 UTC (permalink / raw)
  To: gcc-bugs


------- Additional Comments From kazu at cs dot umass dot edu  2004-03-29 02:09 -------
A slightly more comprehensive list of missing cases.
I am not showing reversed conditions for conciseness.

void bar (void);

void
rshift_gt (unsigned int a)
{
  /* This is equivalent to a >= 23.  */
  if ((a >> 2) > 5)
    bar ();
}

void
rshift_eq (unsigned int a)
{
  /* This is equivalent to a <= 3.  */
  if ((a >> 2) == 0)
    bar ();
}

void
mask_eq (unsigned int a)
{
  /* This is equivalent to a <= 7.  */
  if ((a & ~7) == 0)
    bar ();
}

void
mask_gt (unsigned int a)
{
  /* This is equivalent to a > 15.  */
  if ((a & ~7) > 8)
    bar ();
}

void
not_eq_cst (unsigned int a)
{
  a = ~a;
  if (a == 123)
    bar ();
}

void
not_eq_var (unsigned int a, unsigned int b)
{
  a = ~a;
  b = ~b;
  if (a == b)
    bar ();
}

void
neg_eq_cst (unsigned int a)
{
  a = -a;
  if (a == 123)
    bar ();
}

void
neg_eq_var (unsigned int a, unsigned int b)
{
  a = -a;
  b = -b;
  if (a == b)
    bar ();
}

void
minus_vars (unsigned int a, unsigned int b)
{
  unsigned int tem;

  tem = a - b;
  if (tem == 0)
    bar ();
}

void
xor_vars (unsigned int a, unsigned int b)
{
  unsigned int tem;

  tem = a ^ b;
  if (tem == 0)
    bar ();
}

void
xor_cst (unsigned int a)
{
  a ^= 123;
  if (a == 456)
    bar ();
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
  2004-03-27 16:17 ` [Bug optimization/14753] " pinskia at gcc dot gnu dot org
  2004-03-29  2:10 ` kazu at cs dot umass dot edu
@ 2004-03-29 14:27 ` kazu at cs dot umass dot edu
  2004-03-30  3:56 ` kazu at cs dot umass dot edu
                   ` (6 subsequent siblings)
  9 siblings, 0 replies; 16+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-03-29 14:27 UTC (permalink / raw)
  To: gcc-bugs


------- Additional Comments From kazu at cs dot umass dot edu  2004-03-29 14:27 -------
One more case.

void
minus_cst (unsigned int a)
{
  unsigned int tem;

  tem = 20 - a;
  if (tem == 5)
    bar ();
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
                   ` (2 preceding siblings ...)
  2004-03-29 14:27 ` kazu at cs dot umass dot edu
@ 2004-03-30  3:56 ` kazu at cs dot umass dot edu
  2004-03-31  2:42 ` kazu at cs dot umass dot edu
                   ` (5 subsequent siblings)
  9 siblings, 0 replies; 16+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-03-30  3:56 UTC (permalink / raw)
  To: gcc-bugs


------- Additional Comments From kazu at cs dot umass dot edu  2004-03-30 03:56 -------
One more case.

void
rotate_cst (unsigned int a)
{
  a = (a << 10) | (a >> 22);
  if (a == 123)
    bar ();
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
                   ` (3 preceding siblings ...)
  2004-03-30  3:56 ` kazu at cs dot umass dot edu
@ 2004-03-31  2:42 ` kazu at cs dot umass dot edu
  2004-04-05 23:42 ` kazu at cs dot umass dot edu
                   ` (4 subsequent siblings)
  9 siblings, 0 replies; 16+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-03-31  2:42 UTC (permalink / raw)
  To: gcc-bugs


------- Additional Comments From kazu at cs dot umass dot edu  2004-03-31 02:42 -------
One more case.

void bar (void);

void
foo (unsigned int a)
{
  if ((a >> 5) & 1)
    bar ();
}

I get:

foo (a)
{
  _Bool T.2;
  unsigned int T.1;
  unsigned int T.0;

<bb 0>:
  T.0_2 = a_1 >> 5;
  T.1_3 = T.0_2 & 1;
  T.2_4 = (_Bool)T.1_3;
  if (T.2_4) goto <L0>; else goto <L1>;

<L0>:;
  bar () [tail call];

<L1>:;
  return;

}

We could have "if (T.1_3 != 0)".
If nothing else, we can eliminate one temporary variable.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
                   ` (4 preceding siblings ...)
  2004-03-31  2:42 ` kazu at cs dot umass dot edu
@ 2004-04-05 23:42 ` kazu at cs dot umass dot edu
  2004-05-04 19:04 ` law at redhat dot com
                   ` (3 subsequent siblings)
  9 siblings, 0 replies; 16+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-04-05 23:42 UTC (permalink / raw)
  To: gcc-bugs


------- Additional Comments From kazu at cs dot umass dot edu  2004-04-05 23:42 -------
Some of these (though not everything) are done in RTL.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |TREE


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
                   ` (5 preceding siblings ...)
  2004-04-05 23:42 ` kazu at cs dot umass dot edu
@ 2004-05-04 19:04 ` law at redhat dot com
  2004-05-17 17:47 ` [Bug tree-optimization/14753] " pinskia at gcc dot gnu dot org
                   ` (2 subsequent siblings)
  9 siblings, 0 replies; 16+ messages in thread
From: law at redhat dot com @ 2004-05-04 19:04 UTC (permalink / raw)
  To: gcc-bugs


------- Additional Comments From law at redhat dot com  2004-05-04 19:04 -------
Subject: Re:  [tree-ssa] some missed forward 
 propagation opportunities

In message <20040331024237.14588.qmail@sources.redhat.com>, "kazu at cs dot uma
ss dot edu" writes:
 >
 >------- Additional Comments From kazu at cs dot umass dot edu  2004-03-31 02:
 >42 -------
 >One more case.
 >
 >void bar (void);
 >
 >void
 >foo (unsigned int a)
 >{
 >  if ((a >> 5) & 1)
 >    bar ();
 >}
 >
 >I get:
 >
 >foo (a)
 >{
 >  _Bool T.2;
 >  unsigned int T.1;
 >  unsigned int T.0;
 >
 ><bb 0>:
 >  T.0_2 = a_1 >> 5;
 >  T.1_3 = T.0_2 & 1;
 >  T.2_4 = (_Bool)T.1_3;
 >  if (T.2_4) goto <L0>; else goto <L1>;
 >
 ><L0>:;
 >  bar () [tail call];
 >
 ><L1>:;
 >  return;
 >
 >}
 >
 >We could have "if (T.1_3 != 0)".
 >If nothing else, we can eliminate one temporary variable.
Well, not only do we get to eliminate a temporary, we then have the ability
to propagate T.1_3 == 0 on one arm of the branch.

It's a pretty trivial extension to the existing forward propagation code
[ It's the inversion of propagating from a TRUTH_NOT_EXPR. ]

On hold pending a merge into the mainline.

jeff




-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug tree-optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
                   ` (6 preceding siblings ...)
  2004-05-04 19:04 ` law at redhat dot com
@ 2004-05-17 17:47 ` pinskia at gcc dot gnu dot org
  2004-05-18 16:29 ` law at redhat dot com
  2004-05-24 17:20 ` pinskia at gcc dot gnu dot org
  9 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-05-17 17:47 UTC (permalink / raw)
  To: gcc-bugs


------- Additional Comments From pinskia at gcc dot gnu dot org  2004-05-17 01:47 -------
Fold should do all of these.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug tree-optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
                   ` (7 preceding siblings ...)
  2004-05-17 17:47 ` [Bug tree-optimization/14753] " pinskia at gcc dot gnu dot org
@ 2004-05-18 16:29 ` law at redhat dot com
  2004-05-24 17:20 ` pinskia at gcc dot gnu dot org
  9 siblings, 0 replies; 16+ messages in thread
From: law at redhat dot com @ 2004-05-18 16:29 UTC (permalink / raw)
  To: gcc-bugs


------- Additional Comments From law at redhat dot com  2004-05-18 03:32 -------
Subject: Re:  [tree-ssa] some missed forward 
 propagation opportunities

In message <20040517014727.21847.qmail@sourceware.org>, "pinskia at gcc dot gnu
 dot org" writes:
 >
 >------- Additional Comments From pinskia at gcc dot gnu dot org  2004-05-17 0
 >1:47 -------
 >Fold should do all of these.
Only if you're combining trees.  And yes, I believe we ought to be combining
trees :-)

jeff



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug tree-optimization/14753] [tree-ssa] some missed forward propagation opportunities
  2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
                   ` (8 preceding siblings ...)
  2004-05-18 16:29 ` law at redhat dot com
@ 2004-05-24 17:20 ` pinskia at gcc dot gnu dot org
  9 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-05-24 17:20 UTC (permalink / raw)
  To: gcc-bugs



-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.5.0                       |---


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug tree-optimization/14753] [tree-ssa] some missed forward propagation opportunities
       [not found] <bug-14753-4@http.gcc.gnu.org/bugzilla/>
                   ` (3 preceding siblings ...)
  2023-06-07  0:40 ` pinskia at gcc dot gnu.org
@ 2023-06-07  3:02 ` pinskia at gcc dot gnu.org
  4 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-06-07  3:02 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753
Bug 14753 depends on bug 110134, which changed state.

Bug 110134 Summary: [10/11/12/13/14 Regression] (-unsigned1) != CST is not optimized to unsigned1 != CST at the gimple level
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110134

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug tree-optimization/14753] [tree-ssa] some missed forward propagation opportunities
       [not found] <bug-14753-4@http.gcc.gnu.org/bugzilla/>
                   ` (2 preceding siblings ...)
  2023-05-15  6:22 ` pinskia at gcc dot gnu.org
@ 2023-06-07  0:40 ` pinskia at gcc dot gnu.org
  2023-06-07  3:02 ` pinskia at gcc dot gnu.org
  4 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-06-07  0:40 UTC (permalink / raw)
  To: gcc-bugs

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |85234, 110134

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #12)
> Summary of the ones still need to be done:
> comment #0:
> * foo
PR 85234 (I think)

> comment #3:
> * rshift_gt
PR 85234 (I think)
> * rshift_eq
PR 85234 (I think)
> * mask_gt
I don't think this has a bug #

> * neg_eq_cst
> * neg_eq_var
PR 110134 (just submitted a patch for that)

> 
> comment #4:
> * minus_cst
I don't think this has a bug #


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85234
[Bug 85234] missed optimisation opportunity for (x >> CST)!=0 is not optimized
to   (((unsigned)x) >=  (1<<CST)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110134
[Bug 110134] [10/11/12/13/14 Regression] (-unsigned1) != CST is not optimized
to unsigned1 != CST at the gimple level

^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug tree-optimization/14753] [tree-ssa] some missed forward propagation opportunities
       [not found] <bug-14753-4@http.gcc.gnu.org/bugzilla/>
  2014-10-31  4:01 ` pinskia at gcc dot gnu.org
  2014-10-31  4:04 ` pinskia at gcc dot gnu.org
@ 2023-05-15  6:22 ` pinskia at gcc dot gnu.org
  2023-06-07  0:40 ` pinskia at gcc dot gnu.org
  2023-06-07  3:02 ` pinskia at gcc dot gnu.org
  4 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-05-15  6:22 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Summary of the ones still need to be done:
comment #0:
* foo
comment #3:
* rshift_gt
* rshift_eq
* mask_gt
* neg_eq_cst
* neg_eq_var

comment #4:
* minus_cst

^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug tree-optimization/14753] [tree-ssa] some missed forward propagation opportunities
       [not found] <bug-14753-4@http.gcc.gnu.org/bugzilla/>
  2014-10-31  4:01 ` pinskia at gcc dot gnu.org
@ 2014-10-31  4:04 ` pinskia at gcc dot gnu.org
  2023-05-15  6:22 ` pinskia at gcc dot gnu.org
                   ` (2 subsequent siblings)
  4 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu.org @ 2014-10-31  4:04 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #9)
> Fold should do all of these.

Now I will say match-and-simplify should handle all of these. :)


^ permalink raw reply	[flat|nested] 16+ messages in thread
* [Bug tree-optimization/14753] [tree-ssa] some missed forward propagation opportunities
       [not found] <bug-14753-4@http.gcc.gnu.org/bugzilla/>
@ 2014-10-31  4:01 ` pinskia at gcc dot gnu.org
  2014-10-31  4:04 ` pinskia at gcc dot gnu.org
                   ` (3 subsequent siblings)
  4 siblings, 0 replies; 16+ messages in thread
From: pinskia at gcc dot gnu.org @ 2014-10-31  4:01 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14753
Bug 14753 depends on bug 15459, which changed state.

Bug 15459 Summary: [meta-bug] there should be a tree combiner like the rtl one
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=15459

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED


^ permalink raw reply	[flat|nested] 16+ messages in thread
end of thread, other threads:[~2023-06-07  3:02 UTC | newest]

Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-03-27 16:13 [Bug optimization/14753] New: [tree-ssa] some missed forward propagation opportunities kazu at cs dot umass dot edu
2004-03-27 16:17 ` [Bug optimization/14753] " pinskia at gcc dot gnu dot org
2004-03-29  2:10 ` kazu at cs dot umass dot edu
2004-03-29 14:27 ` kazu at cs dot umass dot edu
2004-03-30  3:56 ` kazu at cs dot umass dot edu
2004-03-31  2:42 ` kazu at cs dot umass dot edu
2004-04-05 23:42 ` kazu at cs dot umass dot edu
2004-05-04 19:04 ` law at redhat dot com
2004-05-17 17:47 ` [Bug tree-optimization/14753] " pinskia at gcc dot gnu dot org
2004-05-18 16:29 ` law at redhat dot com
2004-05-24 17:20 ` pinskia at gcc dot gnu dot org
     [not found] <bug-14753-4@http.gcc.gnu.org/bugzilla/>
2014-10-31  4:01 ` pinskia at gcc dot gnu.org
2014-10-31  4:04 ` pinskia at gcc dot gnu.org
2023-05-15  6:22 ` pinskia at gcc dot gnu.org
2023-06-07  0:40 ` pinskia at gcc dot gnu.org
2023-06-07  3:02 ` pinskia at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).