[Bug tree-optimization/19516] New: missed optimization

[Bug tree-optimization/19516] New: missed optimization

[rguenth at tat dot physik dot uni-tuebingen dot de]

Actually a side-bug of 19507.  The testcase

void bar(void);

void foo(const _Bool *flag)
{
        if (*flag)
                bar();
        if (*flag)
                bar();
}

Should be transformed to (at the tree level):

if (!*flag)
   return;
bar();
if (*flag)
   bar();

this is only done at the RTL level at the moment.

Andrew Pinski reports this works, if we exchange _Bool
for int/short/char.

-- 
           Summary: missed optimization
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at tat dot physik dot uni-tuebingen dot de
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/19516] missed optimization (bool)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-18 23:47 -------
Confirmed, the issue is that DOM does not recognizes that b = *a; if(b) ... c = *a; if (c) ... can be 
changed (note the lacking of the != 0 which would be required for int/char, etc.).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Keywords|                            |alias, missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2005-01-18 23:47:47
               date|                            |
            Summary|missed optimization         |missed optimization (bool)


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

[Bug tree-optimization/19516] missed optimization (bool)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2005-01-22 18:34 -------
This is what I get at the end of tree-ssa optimizations.

foo (flag)
{
  int D.1318;
  _Bool D.1317;

<bb 0>:
  D.1317_2 = *flag_1;
  if (D.1317_2 != 0) goto <L0>; else goto <L1>;

<L0>:;
  bar ();

<L1>:;
  D.1317_4 = *flag_1;
  if (D.1317_4 != 0) goto <L2>; else goto <L3>;

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

<L3>:;
  return;

}

Note that the load immediately after <L1>:; is partially redundant.
I remember Daniel Berlin saying that if PRE is extended to handle
partially redundant load, we can remove the load on one path
to <L1> like so:

<L0>:;
  bar ();
  D.1317_5 = *flag_1;

  D.1317_4 = PHI <D.1317_2(...), D.1317_5(...)>
<L1>:;
  if (D.1317_4 != 0) goto <L2>; else goto <L3>;

At this point, DOM can thread one of the incoming edges to <L1>.

One problem is that PRE will probably be still disabled under -Os
when it is extended to handle partially redundant loads even though
PRE would improve this particular case.


-- 


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

[Bug tree-optimization/19516] missed optimization (bool)

[rguenth at tat dot physik dot uni-tuebingen dot de]

------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2005-01-23 11:13 -------
How comes, that if I change _Bool to int, after tree-optimizations we get

foo (flag)
{
  int D.1121;

<bb 0>:
  D.1121_2 = *flag_1;
  if (D.1121_2 != 0) goto <L0>; else goto <L3>;

<L0>:;
  bar ();
  D.1121_11 = *flag_1;
  if (D.1121_11 != 0) goto <L2>; else goto <L3>;

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

<L3>:;
  return;

}

If your analysis were correct, this shouldn't be possible, no?

-- 


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

[Bug tree-optimization/19516] missed optimization (bool)

[kazu@cs.umass.edu]

------- Additional Comments From kazu at cs dot umass dot edu  2005-02-06 17:49 -------
Hi Richard,

I didn't say that load elimination is the *only* way to take this
optimization opportunity.

DOM *can* thread incoming edges to a basic block with more than COND_EXPR
or SWITCH_EXPR in limited circumstances.

One problem here is that upon taking edge from <bb 0> to <L1>,
DOM does not record that D.1317_2 == 0.

Once we fix that, then D.1317_4 = *flag_1; is folded to D.1317_4 = 0;,
but DOM wants to see an SSA_NAME on rhs on every MODIFY_EXPR leading up to
COND_EXPR or SWITCH_EXPR.

If DOM also knew that D.1317_2 == D.1317_4, it could thread the edge in
question, but I cannot think of an easy way of teaching DOM how to
figure out equivalences of two SSA_NAMEs when we already have a known constant
value.

CCing Jeff as he is the DOM person.


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


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

[Bug tree-optimization/19516] missed optimization (bool)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2005-02-07 06:46 -------
Note that PR 19804 is very closely related.


-- 


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

[Bug tree-optimization/19516] missed optimization (bool)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-02-14 21:05 -------
Note the new jump thread selection code will catch this case.  We get the
following code:

  # BLOCK 0
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  #   VUSE <TMT.0_7>;
  D.1134_2 = *flag_1;
  if (D.1134_2 != 0) goto <L0>; else goto <L3>;
  # SUCC: 1 [46.5%]  (true,exec) 3 [53.5%]  (false,exec)

  # BLOCK 1
  # PRED: 0 [46.5%]  (true,exec)
<L0>:;
  #   TMT.0_9 = V_MAY_DEF <TMT.0_7>;
  bar ();
  #   VUSE <TMT.0_9>;
  D.1134_14 = *flag_1;
  if (D.1134_14 != 0) goto <L2>; else goto <L3>;
  # SUCC: 2 [46.5%]  (true,exec) 3 [53.5%]  (false,exec)

  # BLOCK 2
  # PRED: 1 [46.5%]  (true,exec)
<L2>:;
  #   TMT.0_8 = V_MAY_DEF <TMT.0_9>;
  bar ();
  # SUCC: 3 [100.0%]  (fallthru,exec)

  # BLOCK 3   # PRED: 1 [53.5%]  (false,exec) 2 [100.0%]  (fallthru,exec) 0
[53.5%]  (false,exec)
<L3>:;
  return;


-- 


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

[Bug tree-optimization/19516] missed optimization (bool)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-04-23 01:10 -------
We're performing the requested optimization now.  This should probably be
closed.



-- 


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

[Bug tree-optimization/19516] missed optimization (bool)

[rguenth at gcc dot gnu dot org]

------- Additional Comments From rguenth at gcc dot gnu dot org  2005-04-23 13:49 -------
I guess it will be not possible to fix this for 4.0.1?  Then it is ok to close
the bug as fixed, but please put in a reference to the patch that fixed it.

Thanks for the work,
Richard.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.1.0


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

[Bug tree-optimization/19516] missed optimization (bool)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-04-25 05:05 -------
Subject: Re:  missed optimization (bool)

On Sat, 2005-04-23 at 13:49 +0000, rguenth at gcc dot gnu dot org wrote:
> ------- Additional Comments From rguenth at gcc dot gnu dot org  2005-04-23 13:49 -------
> I guess it will be not possible to fix this for 4.0.1? 
I probably wouldn't recommend it.  I wouldn't want to take the chance
of introducing a wrong-code regression in an attempt to fix a missed
optimization in a minor release.

If someone wants to ponder it further, they'll need to pick up the
tree-ssa-threadupdate changes from earlier this year (to avoid creating
irreducible regions), Diego's vectorizer fix, my reload fix and, of
course the changes to the threading code in tree-ssa-dom.c.


Jeff



-- 


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

[Bug tree-optimization/19516] missed optimization (bool)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-04-25 05:05 -------
Fixed by:

http://gcc.gnu.org/ml/gcc-patches/2005-04/msg02426.html

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |http://gcc.gnu.org/ml/gcc-
                   |                            |patches/2005-
                   |                            |04/msg02426.html
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.1.0


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