[Bug tree-optimization/18046] Missed jump threading optimization

[Bug tree-optimization/18046] Missed jump threading optimization

[steven at gcc dot gnu dot org]

------- Comment #8 from steven at gcc dot gnu dot org  2005-10-07 21:21 -------
I don't have time to work on these (new job), so unassigning.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|steven 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=18046

[Bug tree-optimization/18046] Missed jump threading optimization

[law at redhat dot com]

------- Comment #9 from law at redhat dot com  2006-03-21 15:57 -------
We've got zero chance of threading the jump in this case until the 
partially redundant load from "i" is removed.

Daniel -- there's a pretty obvious redundant load from the global
variable "i" in this testcase.  I haven't investigated why PRE
is missing this obvious redundancy.

Jeff


-- 

law at redhat dot com changed:

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


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

[Bug tree-optimization/18046] Missed jump threading optimization

[pinskia at gcc dot gnu dot org]

------- Comment #10 from pinskia at gcc dot gnu dot org  2006-03-21 16:05 -------
(In reply to comment #9)
> Daniel -- there's a pretty obvious redundant load from the global
> variable "i" in this testcase.  I haven't investigated why PRE
> is missing this obvious redundancy.

Because tree level load PRE does not handle global variables, there is another
bug about this, PR 23455.


-- 


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

[Bug tree-optimization/18046] Missed jump threading optimization

[dberlin at dberlin dot org]

------- Comment #11 from dberlin at gcc dot gnu dot org  2006-03-21 16:57 -------
Subject: Re:  Missed jump threading
        optimization

On Tue, 2006-03-21 at 15:57 +0000, law at redhat dot com wrote:
> 
> ------- Comment #9 from law at redhat dot com  2006-03-21 15:57 -------
> We've got zero chance of threading the jump in this case until the 
> partially redundant load from "i" is removed.
> 
> Daniel -- there's a pretty obvious redundant load from the global
> variable "i" in this testcase.  I haven't investigated why PRE
> is missing this obvious redundancy.

It doesn't deal with loads from global variables because we need to
place a value number on each "instance" that occurs in the program, but
can't easily because they are all shared.

I will get to it eventually.


> 
> Jeff
> 
> 


-- 


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

[Bug tree-optimization/18046] Missed jump threading optimization

[steven at gcc dot gnu dot org]

------- Comment #12 from steven at gcc dot gnu dot org  2008-09-21 13:58 -------
tree PRE now *does* handle the partially redundant global variable load. This
is the .final_cleanup dump:


;; Function bar (bar)

bar ()
{
  int prephitmp.13;

<bb 2>:
  prephitmp.13 = i;
  switch (prephitmp.13) <default: <L1>, case 0: <L0>>

<L0>:
  foo ();
  prephitmp.13 = i;

<L1>:
  switch (prephitmp.13) <default: <L5>, case 0: <L4>>

<L4>:
  foo (); [tail call]

<L5>:
  return;

}


But we still miss the jump threading opportunity.


-- 


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

[Bug tree-optimization/18046] Missed jump threading optimization

[law at redhat dot com]

------- Comment #13 from law at redhat dot com  2008-09-23 21:55 -------
Subject: Re:  Missed jump threading optimization

steven at gcc dot gnu dot org wrote:
> ------- Comment #12 from steven at gcc dot gnu dot org  2008-09-21 13:58 -------
> tree PRE now *does* handle the partially redundant global variable load. This
> is the .final_cleanup dump:
>
>
> ;; Function bar (bar)
>
> bar ()
> {
>   int prephitmp.13;
>
> <bb 2>:
>   prephitmp.13 = i;
>   switch (prephitmp.13) <default: <L1>, case 0: <L0>>
>
> <L0>:
>   foo ();
>   prephitmp.13 = i;
>
> <L1>:
>   switch (prephitmp.13) <default: <L5>, case 0: <L4>>
>
> <L4>:
>   foo (); [tail call]
>
> <L5>:
>   return;
>
> }
>
>
> But we still miss the jump threading opportunity.
>   
Thanks for the update.  One blocking issue out of the way....

Things have changed a lot since that original bug report.  I believe the 
best solution for this particular case is to lower the switch statements 
early enough to expose the conditionals to DOM & VRP.

The 2nd best approach would be to extend VRP to create a range for the 
default case of a SWITCH and extend the jump threading code in 
tree-vrp.c to handle switch statements (they're currently ignored).  The 
biggest difficulty here would be to avoid dropping to varying too 
quickly.  I think you'd want to sort the cases, then build up a range 
containing all the cases.  If you get a gap in the range, you drop to 
varying.  If after extracting all the ranges you haven't dropped to 
varying, then you invert the range and create the appropriate ASSERT_EXPRs.

I'm not currently working on either solution.

jeff


-- 


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

[Bug tree-optimization/18046] Missed jump threading optimization

[steven at gcc dot gnu dot org]

------- Comment #14 from steven at gcc dot gnu dot org  2010-02-04 22:52 -------
Still not fixed. Still the major source of RTL jump threads.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2008-09-21 13:59:00         |2010-02-04 22:52:40
               date|                            |


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

[Bug tree-optimization/18046] Missed jump threading optimization

[steven at gcc dot gnu dot org]

------- Comment #15 from steven at gcc dot gnu dot org  2010-07-13 10:29 -------
Still not fixed with r162134:

;; Function bar (bar)

bar ()
{
  int prephitmp.4;

<bb 2>:
  prephitmp.4_1 = i;
  switch (prephitmp.4_1) <default: <L2>, case 0: <L0>>

<L0>:
  foo ();
  prephitmp.4_7 = i;

  # prephitmp.4_8 = PHI <prephitmp.4_1(2), prephitmp.4_7(3)>
<L2>:
  switch (prephitmp.4_8) <default: <L6>, case 0: <L4>>

<L4>:
  foo (); [tail call]

<L6>:
  return;

}


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2010-02-04 22:52:40         |2010-07-13 10:29:57
               date|                            |


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

[Bug tree-optimization/18046] Missed jump threading optimization

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2012-03-18 10:29:57         |2012-11-08 10:29:57

--- Comment #17 from Steven Bosscher <steven at gcc dot gnu.org> 2012-11-08 22:29:45 UTC ---
Will be addressed for GCC 4.9 by moving switch lowering to GIMPLE.

[Bug tree-optimization/18046] Missed jump threading optimization

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2010-07-13 10:29:57         |2011-07-19 10:29:57

--- Comment #16 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-07-20 00:33:25 UTC ---
If VRP inserts into the default case the assert that i.1 cannot be what is
other cases are, then I think jump threading could handle this.

[Bug tree-optimization/18046] Missed jump threading optimization

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-04-23 16:57 -------
I'm going to implement lowering of some SWITCH_EXPRs at the tree level.  At  
least the ones that we do not produce a decision tree for now in stmt.c... 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |steven at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2004-10-18 12:52:47         |2005-04-23 16:57:45
               date|                            |


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

[Bug tree-optimization/18046] Missed jump threading optimization

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-10-19 20:16 -------
Subject: Re:  Missed jump threading
	optimization

On Mon, 2004-10-18 at 16:50, stevenb at suse dot de wrote:
> ------- Additional Comments From stevenb at suse dot de  2004-10-18 22:50 -------
> Subject: Re:  Missed jump threading optimization
> 
> Hmm, threading the default case sounds interesting, but the real
> reason why the RTL threader catches this and the tree threader does
> not is because on RTL the test case basically looks like this:
> 
> extern void foo (void);
> extern int i;
> void
> bar (void)
> {
>   if (i == 0)
>     foo ();
> 
>   if (i == 0)
>     foo ();
> }
> 
> Hey, I can thread that!  :-)
> 
> So perhaps we should consider lowering SWITCH_EXPRs with only two
> targets to COND_EXPRs after all...?  That would be quite easy to
> do.
Jan and maybe others have talked about lowering SWITCH_EXPRs
earlier.  I don't recall if it ever got implemented.

jeff



-- 


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

[Bug tree-optimization/18046] Missed jump threading optimization

[stevenb at suse dot de]

------- Additional Comments From stevenb at suse dot de  2004-10-18 22:50 -------
Subject: Re:  Missed jump threading optimization

Hmm, threading the default case sounds interesting, but the real
reason why the RTL threader catches this and the tree threader does
not is because on RTL the test case basically looks like this:

extern void foo (void);
extern int i;
void
bar (void)
{
  if (i == 0)
    foo ();

  if (i == 0)
    foo ();
}

Hey, I can thread that!  :-)

So perhaps we should consider lowering SWITCH_EXPRs with only two
targets to COND_EXPRs after all...?  That would be quite easy to
do.




-- 


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

[Bug tree-optimization/18046] Missed jump threading optimization

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-10-18 18:31 -------
Subject: Re:  Missed jump threading
	optimization

On Mon, 2004-10-18 at 11:30, steven at gcc dot gnu dot org wrote:
> ------- Additional Comments From steven at gcc dot gnu dot org  2004-10-18 17:30 -------
> Diego told me to bug Law.  Obedient as I always am, I hereby 
> do so :-) 
>  
> Jeff, this is a missed jump threading opportunity, the default 
> case can be threaded here.  Any ideas how to fix this? 
I don't see a good way to fix this.  There's lots of interconnected
issues that would need to be addressed.

Clearly we need better range information so that we can determine
that i != 0 on the default case leaving the first switch statement
(or we would need to avoid collapsing empty cases to the default
label until expansion).

Second, we need to rewrite the jump threading selection code; that's
on the queue.  Specifically we need to drop the requirement that
the statements at the start of the intermediate block are nops.
The SSA update code is already prepared to handle this change, so
it really ought to be isolated in the jump threading selection
code.


Given those two improvements we'd have a chance of threading the
default case out of the first switch statement.

jeff





-- 


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

[Bug tree-optimization/18046] Missed jump threading optimization

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-10-18 17:30 -------
Diego told me to bug Law.  Obedient as I always am, I hereby 
do so :-) 
 
Jeff, this is a missed jump threading opportunity, the default 
case can be threaded here.  Any ideas how to fix this? 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com


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

[Bug tree-optimization/18046] Missed jump threading optimization

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-10-18 13:22 -------
Might I propose we don't deal with this as an enhancement
request but as a "normal" bug?  Killing the jump threader
in cfgcleanup.c would be a mighty feat, it's one of the
slowest parts of the cfgcleanup on RTL (and IIRC it's one
of the quadratic bottleneckt).

Otherwise, perhaps I should (have) add(ed) the compile
time hog keyword...

-- 


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

[Bug tree-optimization/18046] Missed jump threading optimization

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-10-18 12:52 -------
Confirmed. To summarize what the code should look like:
extern void foo (void);
extern int i;
void
bar (void)
{
  switch (i)
    {
    case 0:
      foo ();
      break;
    default:
       goto other_block;
    }
                                                                               
                
  switch (i)
    {
    case 0:
      foo ();
      break;
    default:
    other_block:
      break;
    }
}

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-10-18 12:52:47
               date|                            |
            Summary|Missed jump threading       |Missed jump threading
                   |optimization                |optimization


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