[Bug tree-optimization/15911] New: DOM optimization not performed

[Bug tree-optimization/15911] New: DOM optimization not performed

[dann at godzilla dot ics dot uci dot edu]

On x86_64-unknown-linux-gnu (RHEL3)
using 
gcc version 3.2.3 20030502 (Red Hat Linux 3.2.3-24)
as the bootstrap compiler

The following code does not get optimized: 
(the link_error calls should all be removed)

extern int link_error (int);

int tst2 (int x, int y)
{
  if ((x > 5555) && (y < 6666))
    {
      if (x > 5555)
        if (y < 6666)
          return 1111;
        else
          return link_error (2222);
      else
        if (y < 6666)
          return link_error (3333);
        else
          return link_error (4444);
    }
  else
    return 0;
}

The .t53.vars dump is:

;; Function tst2 (tst2)

tst2 (x, y)
{
  int T.67;
  _Bool T.65;
  _Bool T.64;

<bb 0>:
  T.64 = x > 5555;
  T.65 = y <= 6665;
  if (T.64 && T.65) goto <L0>; else goto <L11>;

<L11>:;
  T.67 = 0;
  goto <bb 7> (<L8>);

<L0>:;
  if (T.64) goto <L1>; else goto <L4>;

<L1>:;
  if (T.65) goto <L12>; else goto <L3>;

<L12>:;
  T.67 = 1111;
  goto <bb 7> (<L8>);

<L3>:;
  T.67 = link_error (2222) [tail call];
  goto <bb 7> (<L8>);

<L4>:;
  if (T.65) goto <L5>; else goto <L6>;

<L5>:;
  T.67 = link_error (3333) [tail call];
  goto <bb 7> (<L8>);

<L6>:;
  T.67 = link_error (4444) [tail call];

<L8>:;
  return T.67;

}

The code is optimized just fine when compiled on i686-linux!
(the dom1 pass removes the link_error calls)
Like so:

;; Function tst2 (tst2)

tst2 (x, y)
{
  int T.49;

<bb 0>:
  if (x <= 5555) goto <L13>; else goto <L0>;

<L13>:;
  T.49 = 0;
  goto <bb 3> (<L9>);

<L0>:;
  if (y > 6665) goto <L8>; else goto <L14>;

<L14>:;
  T.49 = 1111;
  goto <bb 3> (<L9>);

<L8>:;
  T.49 = 0;

<L9>:;
  return T.49;

}

The problems starts with the stage1 compiler (even stage1 is compiled with gcc
-O0). 
The bootstrap succeeds, and the test results are very similar to other results
posted to gcc-testresults. 
This has been around for a while at least 1 month.
I don't have access to another 64-bit platform right now to check if this has
something to do with 64-bit systems.

-- 
           Summary: DOM optimization not performed
           Product: gcc
           Version: 3.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dann at godzilla dot ics dot uci dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/15911] DOM optimization not performed

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-06-10 17:58 -------
This also happens on ia64. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-06-10 17:58:34
               date|                            |


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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-06-10 18:50 -------
This is just like PR 13965.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |13965, 15357
           Severity|normal                      |enhancement
           Keywords|                            |missed-optimization


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

[Bug tree-optimization/15911] DOM optimization not performed

[dann at godzilla dot ics dot uci dot edu]

------- Additional Comments From dann at godzilla dot ics dot uci dot edu  2004-06-10 22:24 -------
Hmmm, adding -march=athlon shows the same problem on i386. 
The problem does not occur 0f -march=i386 is used. 

The difference between the 2 cases above appears in the .t03.original dump:

For i386 the first "if" is translated to:
   if (x > 5555 && y <= 6665)  
the "&&" corresponds to a tree_andif_expr tree
for -march=athlon it is translated to:
   if (#`truth_and_expr' not supported by pp_c_expression#)
here a truth_and_expr tree is used. 

For i386 the && is transformed in cascading ifs, and DOM knows how to deal with
that. 
For athlon the truth_and_expr is transformed to:

  T.0 = x > 5555;
  T.1 = y <= 6665;
  T.2 = T.0 && T.1;
  if (T.2) ....

In this case DOM does not infere that if T.2 is true then T.0 and T.1 are also
true. 

The question is, should "&&" be lowered to different trees depending on the
target architecture? 




-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|enhancement                 |normal


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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-06-10 22:27 -------
Yes we know that this is a problem which is caused by BRANCH_COST, I had a start on a new pass 
which makes the stuff done for BRANCH_COST later and not in fold but my HD died.  I will see if I do 
the pass over the next couple of weeks.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pinskia at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-09-09 03:53 -------
*** Bug 13965 has been marked as a duplicate of this bug. ***

-- 
Bug 15911 depends on bug 13965, which changed state.

Bug 13965 Summary: [tree-ssa] fold takes into account branch target information at tree level
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13965

           What    |Old Value                   |New Value
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |DUPLICATE

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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-08 19:18 -------
I am no longer working on this.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|pinskia at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-07-04 21:41 -------
*** Bug 20065 has been marked as a duplicate of this bug. ***

-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-07-04 21:41 -------
VRP does not work on this either.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dnovillo at gcc dot gnu dot
                   |                            |org
            Summary|DOM optimization not        |VRP/DOM does not like
                   |performed                   |TRUTH_AND_EXPR


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-09-08 18:20 -------

This would be fixable inside VRP.  Essentially we would need to insert chains of
ASSERT_EXPRs to represent various predicates:

  D.1613_3 = x_2 > 5555;
  D.1614_5 = y_4 <= 6665;
  D.1615_6 = D.1613_3 && D.1614_5;
  if (D.1615_6) goto <L0>; else goto <L8>;

At label L0, we know that:

  D.1615_10 = 1;
  D.1613_11 = 1;
  D.1614_12 = 1;
  y_13 = ASSERT_EXPR <y_4, y_4 <= 6665>;
  x_14 = ASSERT_EXPR <x_2, x_2 > 5555>;

which is a bit sickening.  It would be Much Better to avoid creating these
obtuse predicates in fold(), though.

Roger, Jeff, is there some hope for fixing this in fold() for 4.2?  If not, I
can work on VRP to try an understand these chains.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sayle at gcc dot gnu dot org
   Target Milestone|---                         |4.2.0


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-09-08 19:04 -------
Subject: Re:  VRP/DOM does not like
	TRUTH_AND_EXPR

On Thu, 2005-09-08 at 18:20 +0000, dnovillo at gcc dot gnu dot org
wrote:
> ------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-09-08 18:20 -------
> 
> This would be fixable inside VRP.  Essentially we would need to insert chains of
> ASSERT_EXPRs to represent various predicates:
> 
>   D.1613_3 = x_2 > 5555;
>   D.1614_5 = y_4 <= 6665;
>   D.1615_6 = D.1613_3 && D.1614_5;
>   if (D.1615_6) goto <L0>; else goto <L8>;
> 
> At label L0, we know that:
> 
>   D.1615_10 = 1;
>   D.1613_11 = 1;
>   D.1614_12 = 1;
>   y_13 = ASSERT_EXPR <y_4, y_4 <= 6665>;
>   x_14 = ASSERT_EXPR <x_2, x_2 > 5555>;
> 
> which is a bit sickening.  It would be Much Better to avoid creating these
> obtuse predicates in fold(), though.
Well, we have a long standing problem with fold using BRANCH_COST to
determine how best to implement certain conditionals.  But even if that
were removed, it's fairly straightforward for a programmer (or better
yet some automated code generator) to create these "obtuse" predicates.

I think we'd be better off teaching VRP how to cope with this.


Jeff



-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-09-08 19:07 -------
(In reply to comment #10)

> it's fairly straightforward for a programmer (or better
> yet some automated code generator) to create these "obtuse" predicates.
> 
Good point.  I'll work on a fix.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |dnovillo at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[pinskia at gcc dot gnu.org]

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

Bug 15911 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/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #32 from rguenth at gcc dot gnu dot org  2006-10-22 20:16 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #31 from rguenth at gcc dot gnu dot org  2006-10-22 20:11 -------
Subject: Bug 15911

Author: rguenth
Date: Sun Oct 22 20:11:09 2006
New Revision: 117960

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=117960
Log:
2006-10-22  Jeff Law  <law@redhat.com>
        Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/15911
        * tree-vrp.c (extract_code_and_val_from_cond): New function.
        (register_edge_assert_for_1): Likewise.
        (register_edge_assert_for): Handle &&/&/||/| in conditionals.
        (find_conditional_asserts): Adjust for new function signature.
        (find_assert_locations): Likewise.

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

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


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[patchapp at dberlin dot org]

------- Comment #30 from patchapp at dberlin dot org  2006-05-15 19:30 -------
Subject: Bug number PR15911

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00030.html


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #29 from rguenth at gcc dot gnu dot org  2006-05-01 21:12 -------
ca11011 looks like a spurious failure (do I hate that...).


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[dann at godzilla dot ics dot uci dot edu]

------- Comment #28 from dann at godzilla dot ics dot uci dot edu  2006-04-30 19:25 -------
Just a note, fixing the problem in this PR would fix the only remaining failure
for cprop in Brigg's compiler benchmarks.


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #27 from rguenth at gcc dot gnu dot org  2006-04-26 08:47 -------
Compile time and memory usage checking on a set of C++ benchmarks (tramp3d,
DLV, mico and boost) don't show regressions.  I'll leave this here now until
stage1 opens.


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #26 from rguenth at gcc dot gnu dot org  2006-04-25 15:55 -------
Created an attachment (id=11333)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=11333&action=view)
updated patch

This is a cleanup of the patch by Jeff, bootstrapped and regtested on
x86_64-unknown-linux-gnu.  ca11011 fails for me with the patch, all other
languages are fine.

I left the basic structure of the patch as it is reasonable.  Compile-time /
memory checking will be done soon.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #11259|0                           |1
        is obsolete|                            |
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenther at suse dot de]

------- Comment #25 from rguenther at suse dot de  2006-04-20 16:33 -------
Subject: Re:  VRP/DOM does not like TRUTH_AND_EXPR

On Thu, 20 Apr 2006, law at redhat dot com wrote:

> Richard -- is there any chance you could pick up the ball on this PR?  I really
> need to focus on some non-GCC stuff for a while, but don't want this issue to
> get lost in the process.

Yes, it's on my list of things to look at.


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[law at redhat dot com]

------- Comment #24 from law at redhat dot com  2006-04-20 16:24 -------
Richard -- is there any chance you could pick up the ball on this PR?  I really
need to focus on some non-GCC stuff for a while, but don't want this issue to
get lost in the process.

Jeff


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #23 from rguenth at gcc dot gnu dot org  2006-04-17 16:54 -------
It also helps for propagating loop versioning guard information like

int foo(int i, int j)
{
  int res = 0;
  if (i==1 && j==2)
    for (;i>0;--i)
      res += j;
  else
    for (;i>0;--i)
      res += j;
  return res;
}


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[law at redhat dot com]

------- Comment #22 from law at redhat dot com  2006-04-17 16:40 -------
Here's some code which can be clearly improved with the in-progress patch to
add additional ASSERT_EXPRs:

int f(void);
void test(int x) {
   if (x & 1 ? x == 0 : x > 0) f();
}

Right now we generate something like:

        movl    4(%esp), %eax
        testb   $1, %al
        je      .L2
        testl   %eax, %eax
        sete    %al
        testb   %al, %al
        jne     .L9
.L7:
        rep ; ret
        .p2align 4,,7
.L2:
        testl   %eax, %eax
        setg    %al
        testb   %al, %al
        je      .L7
.L9:
        jmp     f

With the work-in-progress patch we generate the  more compact and efficient:

        movl    4(%esp), %eax
        testb   $1, %al
        jne     .L5
        testl   %eax, %eax
        jg      .L7
.L5:
        rep ; ret
        .p2align 4,,7
.L7:
        jmp     f


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[law at redhat dot com]

------- Comment #20 from law at redhat dot com  2006-04-13 18:14 -------
Subject: Re:  VRP/DOM does not like
        TRUTH_AND_EXPR

On Fri, 2006-04-07 at 12:23 +0000, rguenth at gcc dot gnu dot org wrote:
> 
> ------- Comment #19 from rguenth at gcc dot gnu dot org  2006-04-07 12:23 -------
> Jeff, can you send me the patch-in-progress you have for this?  Thanks.
Sorry.  Surgery and been on the road.

Here's what I've been playing with -- I'm not happy with its structure
yet, but should give you a rough idea of what I've been playing with.

In terms of simplifying conditionals -- the improvements are trivial.
Astoundingly trivial.  We also see a small increase in the number of
jumps threaded and blocks merged.

Measuring the number of blocks removed isn't particularly interesting
as we'll count blocks which were created solely to hold ASSERT_EXPRs,
then became trivial forwarders once we removed the ASSERT_EXPRs.

Given the very small improvements we're definitely going to need to
look very closely at the compile-time impact of these changes.  We may
have a case where the compile-time impact is greater than the runtime
benefits.

The TRUTH_NOT_EXPR stuff doesn't trigger in my test bucket, probably
because I don't have many FP tests.   FP stuff is about the only time
I can think of that we'd fail inverting the tense of a comparison and
have to fall back to TRUTH_NOT_EXPR.

I haven't done any bootstrap or regression testing with this patch.


------- Comment #21 from law at redhat dot com  2006-04-13 18:14 -------
Created an attachment (id=11259)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=11259&action=view)


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #19 from rguenth at gcc dot gnu dot org  2006-04-07 12:23 -------
Jeff, can you send me the patch-in-progress you have for this?  Thanks.


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[law at redhat dot com]

------- Comment #18 from law at redhat dot com  2006-03-22 18:13 -------
Subject: Re:  VRP/DOM does not like
        TRUTH_AND_EXPR

On Wed, 2006-03-22 at 09:00 +0000, rguenth at gcc dot gnu dot org wrote:
> 
> ------- Comment #17 from rguenth at gcc dot gnu dot org  2006-03-22 09:00 -------
> Yes, this sounds very reasonable.  Is there a chance you can take a look and
> provide a rough implementation?  I can take on the ball and try to fix
> remaining issues - but as I'm not familiar with the VRP pass a patch to start
> with would be helpful in this sense.
I've actually got a good hunk of a rough implementation the biggest
thing that is missing is pruning of ASSERT_EXPRs for names which are
not used in the subgraph.  Fixing that is actually nontrivial, so we
may just approximate it with pruning based on how many times the LHS
is used.

With any luck I'll be far enough along that I can start the regression
testing when I hop on the airplane this evening.

jeff


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #17 from rguenth at gcc dot gnu dot org  2006-03-22 09:00 -------
Yes, this sounds very reasonable.  Is there a chance you can take a look and
provide a rough implementation?  I can take on the ball and try to fix
remaining issues - but as I'm not familiar with the VRP pass a patch to start
with would be helpful in this sense.

Thanks!
Richard.


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[law at redhat dot com]

------- Comment #16 from law at redhat dot com  2006-03-22 04:57 -------
Subject: Re:  VRP/DOM does not like
        TRUTH_AND_EXPR

On Tue, 2006-03-21 at 16:19 +0000, dnovillo at gcc dot gnu dot org
wrote:
> 
> ------- Comment #13 from dnovillo at gcc dot gnu dot org  2006-03-21 16:19 -------
> (In reply to comment #12)
> > Any updates on this?  It get's in the way of loop versioning conditionals which
> > I now have to decompose manually into chained if's :/
> > 
> Nope.  I'm unlikely to work on this any time soon.  Maybe in another couple of
> months.
FWIW, the idea of recursively creating asserts may work.

given something like

t1 = x > 10;
t2 = y < 30;
t3 = t1 && t2
if (t3)

First we insert any necessary asserts for T3 on the outgoing
edges.  Then we look at how T3 is defined -- it's defined by
a TRUTH_AND_EXPR.  So, we recurse on the arguments of the
TRUTH_AND_EXPR for the true edge.

We proceed to register that T1 must be true, and then recurse
on the definition of T1.  That in turn allows us to realize
that x > 10 must be true as well, so we can register an assert
for x.

The same steps apply to t2.

The net result is that on the true edge we have the following
potential asserts
t3, t3 EQ 1
t1, t1 EQ 1
x, x > 10
t2, t2 EQ 1
y, y < 30

On the false edge we have

t3, t3 EQ 0

No other assertions are possible for the false edge.

There's still a number of loose ends to tie up, but this looks
rather promising and probably a lot easier than try to turn
this into a series of conditionals...

Jeff


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[law at redhat dot com]

------- Comment #15 from law at redhat dot com  2006-03-21 16:57 -------
Subject: Re:  VRP/DOM does not like
        TRUTH_AND_EXPR

On Tue, 2006-03-21 at 16:19 +0000, dnovillo at gcc dot gnu dot org
wrote:
> 
> ------- Comment #13 from dnovillo at gcc dot gnu dot org  2006-03-21 16:19 -------
> (In reply to comment #12)
> > Any updates on this?  It get's in the way of loop versioning conditionals which
> > I now have to decompose manually into chained if's :/
> > 
> Nope.  I'm unlikely to work on this any time soon.  Maybe in another couple of
> months.
How hard would it be to register the asserts for these dependency
change at the same time we register the initial assert.  It seems
there's only two cases we care about.

If we're asserting an SSA_NAME has a nonzero (true) value and the
SSA_NAME is defined by a TRUTH_AND_EXPR, then we know both operands
of the TRUTH_AND_EXPR must also be true (note we would then recurse
on the operands).

Similarly if we're asserting an SSA_NAME is zero (false) and the
SSA_NAME is defined by a TRUTH_OR_EXPR, then we know that both
operands of the TRUTH_OR_EXPR must also be zero (false).  Again
recurse on the operands.

I don't *think* it would be that hard.  

Jeff


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2006-03-21 16:48 -------
And I'm getting lost in decomposing such a conditional into BBs and COND_EXPRs
and GOTOs and adding edges and whatnot.  This sucks.  Where's the helper
routine that I'm not finding?


-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[dnovillo at gcc dot gnu dot org]

------- Comment #13 from dnovillo at gcc dot gnu dot org  2006-03-21 16:19 -------
(In reply to comment #12)
> Any updates on this?  It get's in the way of loop versioning conditionals which
> I now have to decompose manually into chained if's :/
> 
Nope.  I'm unlikely to work on this any time soon.  Maybe in another couple of
months.


-- 

dnovillo at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|dnovillo at gcc dot gnu dot |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2006-03-21 16:02 -------
Any updates on this?  It get's in the way of loop versioning conditionals which
I now have to decompose manually into chained if's :/


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org


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