[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-08-10 18:57 -------
Subject: Re:  [tree-ssa] Merge two "if"s if
	one subsumes the other.

On Sat, 2005-06-11 at 19:16 +0000, pinskia at gcc dot gnu dot org wrote:
> ------- Additional Comments From pinskia at gcc dot gnu dot org  2005-06-11 19:16 -------
> (In reply to comment #3)
> > And it should merge them, too, like for
> 
> I better testcase which shows why we don't convert i > j || i == j into i >= j
> which is reduced from Richard's tramp3d:
> int g(void);
> int h(void);
> int f(int *i, int *j)
> {
>   while (1)
>   {
>     if (*i > *j || *i == *j)
>       break;
>     return g();
>   }
>   return h();
> }

At first I thought we might be able to do this via VRP.  But after more
thought, I don't see this kind of transformation fitting into the VRP
framework.

It wouldn't be terribly hard to write a new optimizer to perform this
transformation, and I would expect it would be pretty efficient.  It
would need to run after copy propagation and DCE since useless
copies would easily get in the way of successful optimization.

I'm pretty sure it could be done with a single pass through the IL.

Jeff



-- 


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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[rguenth at gcc dot gnu dot org]

------- Additional Comments From rguenth at gcc dot gnu dot org  2005-08-11 11:01 -------
Couldn't DOM do this at jump threading time? I.e.

  if (D.1286_3 > D.1287_5) goto <L3>; else goto <L1>;

<L1>:;
  if (D.1286_3 == D.1287_5) goto <L3>; else goto <L2>;

during trying of threading through the jump at L1 merge the
two conditionals?

Just guessing...

-- 


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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-08-11 15:43 -------
Subject: Re:  [tree-ssa] Merge two "if"s if
	one subsumes the other.

On Thu, 2005-08-11 at 11:01 +0000, rguenth at gcc dot gnu dot org wrote:
> ------- Additional Comments From rguenth at gcc dot gnu dot org  2005-08-11 11:01 -------
> Couldn't DOM do this at jump threading time? I.e.
> 
>   if (D.1286_3 > D.1287_5) goto <L3>; else goto <L1>;
> 
> <L1>:;
>   if (D.1286_3 == D.1287_5) goto <L3>; else goto <L2>;
> 
> during trying of threading through the jump at L1 merge the
> two conditionals?
Jump threading isn't particularly well suited for this kind of
optimization.  

jeff




-- 


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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[trt at acm dot org]

------- Additional Comments From trt at acm dot org  2005-08-11 15:52 -------
I think http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21643 is closely related.

-- 


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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-08-11 17:29 -------
Subject: Re:  [tree-ssa] Merge two "if"s if
	one subsumes the other.

On Thu, 2005-08-11 at 15:52 +0000, trt at acm dot org wrote:
> ------- Additional Comments From trt at acm dot org  2005-08-11 15:52 -------
> I think http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21643 is closely related.
It's related.

However, there is a key difference.  In 21643, the object being tested
is a scalar and thus should be subject to optimization by fold-const.c's
range checking optimizations.  ie, the merging of the conditions in the
test should occur well before the SSA optimization path is run.

In 15353 the object being tested is a memory reference and thus we can
not safely merge the tests until later in the optimization path (after
we've exposed the memory loads and proved they're equivalent).

jeff




-- 


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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[pinskia at gcc dot gnu.org]

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

Bug 15353 depends on bug 15357, which changed state.

Bug 15357 Summary: [tree-ssa] combing if statements
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15357

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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2007-04-23 12:47 -------
Mine.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2006-10-24 12:39:16         |2007-04-23 12:47:56
               date|                            |


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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2007-06-12 12:06 -------
Subject: Bug 15353

Author: rguenth
Date: Tue Jun 12 12:06:19 2007
New Revision: 125644

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=125644
Log:
2007-06-12  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/15353
        PR tree-optimization/31657
        * passes.c (init_optimization_passes): Add pass_tree_ifcombine.
        * timevar.def: Add TV_TREE_IFCOMBINE.
        * tree-pass.h (pass_tree_ifcombine): Declare.
        * tree-ssa-ifcombine.c: New file.
        * tree-ssa-phiopt.c (blocks_in_phiopt_order): Export.
        * tree-flow.h (blocks_in_phiopt_order): Declare.
        * Makefile.in (OBJS-common): Add tree-ssa-ifcombine.o.
        (tree-ssa-ifcombine.o): New dependencies.

        * gcc.c-torture/execute/20070424-1.c: New testcase.
        * gcc.dg/tree-ssa/ssa-ifcombine-1.c: Likewise.
        * gcc.dg/tree-ssa/ssa-ifcombine-2.c: Likewise.
        * gcc.dg/tree-ssa/ssa-ifcombine-3.c: Likewise.
        * gcc.dg/tree-ssa/ssa-ifcombine-4.c: Likewise.
        * gcc.dg/tree-ssa/ssa-ifcombine-5.c: Likewise.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/20070424-1.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-1.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-2.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-3.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-4.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-5.c
    trunk/gcc/tree-ssa-ifcombine.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/Makefile.in
    trunk/gcc/passes.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/timevar.def
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-pass.h
    trunk/gcc/tree-ssa-phiopt.c


-- 


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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2007-06-12 12:08 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.3.0


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

[Bug optimization/15353] New: [tree-ssa] Merge two "if"s if one subsumes the other.

[kazu at cs dot umass dot edu]

void bar (void);

void
foo (int a, int b)
{
  do
    {
      if (a < b)
	break;
      if (a != b)
	break;
      bar ();
    }
  while (0);
}

I get:

foo (a, b)
{
<bb 0>:
  if (a_1 < b_2) goto <L2>; else goto <L0>;

<L0>:;
  if (a_1 != b_2) goto <L2>; else goto <L1>;

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

<L2>:;
  return;

}

Note that the second "if" completely subsumes the first.
We would like:

foo (a, b)
{
<bb 0>:
  if (a_1 == b_2) goto <L0>; else goto <L1>;

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

<L1>:;
  return;

}

This comes from shorten_compare from c-common.c.

-- 
           Summary: [tree-ssa] Merge two "if"s if one subsumes the other.
           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=15353

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[pinskia at gcc dot gnu dot org]

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


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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[rguenth at gcc dot gnu dot org]

------- Additional Comments From rguenth at gcc dot gnu dot org  2005-06-11 19:05 -------
And it should merge them, too, like for

 int g(void);
 int h(void);
 int f(int i, int j)
 {
   while (1)
   {
     if (i > j)
       break;
     if (i == j)
       break;
     return g();
   }
   return h();
 }


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at tat dot physik
                   |                            |dot uni-tuebingen dot de


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

[Bug tree-optimization/15353] [tree-ssa] Merge two "if"s if one subsumes the other.

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-06-11 19:16 -------
(In reply to comment #3)
> And it should merge them, too, like for

I better testcase which shows why we don't convert i > j || i == j into i >= j
which is reduced from Richard's tramp3d:
int g(void);
int h(void);
int f(int *i, int *j)
{
  while (1)
  {
    if (*i > *j || *i == *j)
      break;
    return g();
  }
  return h();
}


-- 


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