[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[pinskia at gcc dot gnu dot org]

------- Comment #18 from pinskia at gcc dot gnu dot org  2005-11-04 15:37 -------
Since this is only a missed optimization (and this was my bug) closing as fixed
for 4.1.0.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|4.0.3                       |4.1.0


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.2                       |4.0.3


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-07-22 21:12 -------
Moving to 4.0.2 pre Mark.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4.5                       |4.0.2


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4.4                       |3.4.5


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-22 19:25 -------
Fixed at least on the mainline.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|3.3.3 3.3.1                 |3.3.3 3.3.1 4.1.0
            Summary|[3.4/4.0/4.1 Regression]    |[3.4/4.0 Regression] missing
                   |missing jump threading      |jump threading because of
                   |because of type changes     |type changes


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[tobi at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |19292
              nThis|                            |


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-22 14:08 -------
One approach is to fix PR 14843.
It is just one approach, so I won't say this PR is blocked by PR 14843.


-- 


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-13 17:28 -------
Subject: Re:  [3.4/4.0 Regression] missing
	jump threading because of type changes

On Mon, 2004-12-13 at 17:13 +0000, kazu at cs dot umass dot edu wrote:

> Sorry, the example was a little bad.  I had something like this in my
> mind.
> 
>   # iftmp.0_1 = PHI <a_1(2), 0(3)>;
> <L4>:;
>   D.1171_13 = iftmp.0_1 + 1;
>   if (D.1171_13 != 0) goto <L8>; else goto <L14>;
> 
> Note that D.1171_13 is partially constant.  I guess we should really
> transform this into
> 
> <bb 2>:
>   a_2 = a_1 + 1;
> 
>   # D.1171_13 = PHI <a_2(2), 1(3)>;
> <L4>:;
>   if (D.1171_13 != 0) goto <L8>; else goto <L14>;
> 
> Of course, if there are a lot of incoming edges that do not have
> constant PHI arguments, sending "+ 1" upstream would cause code bloat.
> We could "fix" this by creating a helper block that does "+ 1" and
> then jump to L4, but things get more and more complicated, and I don't
> know if it's profitable.
Not really.

We should thread the edge coming from block 3.  Again, this is precisely
the kind of thing we can and should be doing in the selection code
now that the SSA updating code can handle it.

> 
> Another thing I've seen blocking a jump threading opportunity is:
> 
> <L4>:;
>   D.1171_13 = global_variable;
>   if (D.1171_13 != 0) goto <L8>; else goto <L14>;
> 
> Where the value of global_variable is known on one of the incoming
> edges of L4.  I guess we need to remove partially redundancy
> associated with this load and shouldn't blame the jump threader.  That
> is, we should transform the code above to
> 
>   D.1171_13 = PHI <...(2), ...(3)>
> <L4>:;
>   if (D.1171_13 != 0) goto <L8>; else goto <L14>;
Again, this should be something we can handle in the threader.  If we
know the value of the global on one more more incoming edges, then
we ought to be able to thread it.  The only reason we do not in cases
like this is because the old SSA updating code couldn't handle this
kind of update because the assignment to D.1171_13 might need to be
preserved on one or more paths.

I don't see anything in these example that can not and should not
be handled by fixing the jump thread selection code.  In fact, they
are all just instances of issues I have already seen and designed
the SSA updating code to property handle.

jeff



-- 


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-13 17:13 -------
Subject: Re:  [3.4/4.0 Regression] missing
 jump threading because of type changes

Hi Jeff,

> No.  The way to handle this is to remove all the nonsense about proving
> that statements in the block are NOPs.  That precondition for threading
> is no longer necessary and just gets in the way of doing a good job
> at optimizing.
> 
> This is a great example of the kind of code I expect the threader to
> be able to handle once that lameness is removed.

Sorry, the example was a little bad.  I had something like this in my
mind.

  # iftmp.0_1 = PHI <a_1(2), 0(3)>;
<L4>:;
  D.1171_13 = iftmp.0_1 + 1;
  if (D.1171_13 != 0) goto <L8>; else goto <L14>;

Note that D.1171_13 is partially constant.  I guess we should really
transform this into

<bb 2>:
  a_2 = a_1 + 1;

  # D.1171_13 = PHI <a_2(2), 1(3)>;
<L4>:;
  if (D.1171_13 != 0) goto <L8>; else goto <L14>;

Of course, if there are a lot of incoming edges that do not have
constant PHI arguments, sending "+ 1" upstream would cause code bloat.
We could "fix" this by creating a helper block that does "+ 1" and
then jump to L4, but things get more and more complicated, and I don't
know if it's profitable.

Another thing I've seen blocking a jump threading opportunity is:

<L4>:;
  D.1171_13 = global_variable;
  if (D.1171_13 != 0) goto <L8>; else goto <L14>;

Where the value of global_variable is known on one of the incoming
edges of L4.  I guess we need to remove partially redundancy
associated with this load and shouldn't blame the jump threader.  That
is, we should transform the code above to

  D.1171_13 = PHI <...(2), ...(3)>
<L4>:;
  if (D.1171_13 != 0) goto <L8>; else goto <L14>;

Kazu Hirata


-- 


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-13 16:33 -------
Subject: Re:  [3.4/4.0 Regression] missing
	jump threading because of type changes

On Sun, 2004-12-12 at 17:42 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-12 17:42 -------
> Another (possibly expensive) approach would be to "ignore" statements whose
> results are used only in the basic block we are threading through.
> 
> Consider:
> 
>   # iftmp.0_1 = PHI <1(2), 0(3), 0(1)>;
> <L4>:;
>   D.1171_13 = (unsigned char) iftmp.0_1;
>   D.1160_14 = (int) D.1171_13;
>   D.1145_16 = (unsigned char) D.1160_14;
>   if (D.1145_16 != 0) goto <L8>; else goto <L14>;
> 
> Note that the LHS of all MODIFY_EXPRs are used only in this basic block.
> So if we get to COND_EXPR and find out that COND_EXPR_COND is a constant
> (due to temporary propagation), then we can safely duplicate this basic block
> and thread an incoming edge (without causing code bloat).
> All the duplicate copies of MODIFY_EXPRs will be removed as dead code.
No.  The way to handle this is to remove all the nonsense about proving
that statements in the block are NOPs.  That precondition for threading
is no longer necessary and just gets in the way of doing a good job
at optimizing.

This is a great example of the kind of code I expect the threader to
be able to handle once that lameness is removed.

jeff




-- 


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-12 17:42 -------
Another (possibly expensive) approach would be to "ignore" statements whose
results are used only in the basic block we are threading through.

Consider:

  # iftmp.0_1 = PHI <1(2), 0(3), 0(1)>;
<L4>:;
  D.1171_13 = (unsigned char) iftmp.0_1;
  D.1160_14 = (int) D.1171_13;
  D.1145_16 = (unsigned char) D.1160_14;
  if (D.1145_16 != 0) goto <L8>; else goto <L14>;

Note that the LHS of all MODIFY_EXPRs are used only in this basic block.
So if we get to COND_EXPR and find out that COND_EXPR_COND is a constant
(due to temporary propagation), then we can safely duplicate this basic block
and thread an incoming edge (without causing code bloat).
All the duplicate copies of MODIFY_EXPRs will be removed as dead code.


-- 


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-12 17:26 -------
> One approach is to go with the phi optimization rewrite which allows it
> to work with > 2 predecessors to the PHI block.

This is done on tree-cleanup-branch.

> Another would be to look at Kazu's work which (IIRC) tried to identify
> typecasts which were fed by PHIs with all constant arguments.  It then
> removed the typecast and original PHI and installed a new PHI with a
> result of the proper type.

The problem of replacing one PHI node with another is filed as PR 14843.


-- 


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-11-25 00:22 -------
Subject: Re:  [3.4/4.0 Regression] missing
	jump threading because of type changes

On Wed, 2004-11-24 at 22:38 +0000, steven at gcc dot gnu dot org wrote:
> ------- Additional Comments From steven at gcc dot gnu dot org  2004-11-24 22:38 -------
> I don't think this is "minor".  We have many places where we have 
> predicates returning "bool", and this PR suggests that we can never 
> thread on their results because of casts. 
>  
> Adding Jeff, this may be a new prey for him after he's done with 
> Bug 15524 ;-) 
There are a number of ways we can attack this.  I don't know if any are
appropriate for 4.0 though.

One approach is to go with the phi optimization rewrite which allows it
to work with > 2 predecessors to the PHI block.

Another would be to look at Kazu's work which (IIRC) tried to identify
typecasts which were fed by PHIs with all constant arguments.  It then
removed the typecast and original PHI and installed a new PHI with a
result of the proper type.

A third would be to revamp the jump threading selection code.   In the
early days of the jump threading code we couldn't handle SSA graph
updates if we threaded through a block with side effects.  The new
SSA graph update code handles that case, so the selection code shouldn't
need to be so conservative anymore.

I think ultimately we'll want to do all three.  The question in my mind
is which (if any) are suitable for gcc 4.0.

jeff




-- 


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-11-24 22:38 -------
I don't think this is "minor".  We have many places where we have 
predicates returning "bool", and this PR suggests that we can never 
thread on their results because of casts. 
 
Adding Jeff, this may be a new prey for him after he's done with 
Bug 15524 ;-) 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com
           Severity|minor                       |normal
   Last reconfirmed|2004-11-20 16:44:20         |2004-11-24 22:38:25
               date|                            |


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

[Bug tree-optimization/18576] [3.4/4.0 Regression] missing jump threading because of type changes

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-11-20 17:56 -------
Hmm, this is 3.4 and 4.0 Regression, 3.3.3 produced:
flow_bb_inside_loop_p:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %ecx
        pushl   %ebx
        movl    12(%ebp), %eax
        xorl    %ebx, %ebx
        cmpl    %eax, %ecx
        je      .L5
        movl    (%ecx), %edx
        cmpl    %edx, (%eax)
        jle     .L4
        movl    4(%eax), %eax
        cmpl    %ecx, (%eax,%edx,4)
        je      .L5
        .p2align 4,,15
.L4:
        movl    %ebx, %eax
        popl    %ebx
        popl    %ebp
        ret
        .p2align 4,,7
.L5:
        movl    $1, %ebx
        jmp     .L4

But 4.0 and 3.4.0 produces:
flow_bb_inside_loop_p:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        movl    %esi, 4(%esp)
        movl    8(%ebp), %ecx
        xorl    %esi, %esi
        movl    %ebx, (%esp)
        movl    12(%ebp), %eax
        cmpl    %eax, %ecx
        je      .L3
        movl    (%ecx), %edx
        xorl    %ebx, %ebx
        cmpl    %edx, (%eax)
        jle     .L5
        movl    4(%eax), %eax
        cmpl    %ecx, (%eax,%edx,4)
        je      .L7
.L5:
        testb   %bl, %bl
        je      .L2
.L3:
        movl    $1, %esi
.L2:
        movl    %esi, %eax
        movl    (%esp), %ebx
        movl    4(%esp), %esi
        movl    %ebp, %esp
        popl    %ebp
        ret
.L7:
        movl    $1, %ebx
        jmp     .L5

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|enhancement                 |minor
      Known to fail|                            |3.4.0 4.0.0
      Known to work|                            |3.3.3
            Summary|missing jump threading      |[3.4/4.0 Regression] missing
                   |because of type changes     |jump threading because of
                   |                            |type changes
   Target Milestone|---                         |3.4.4


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