[Bug target/40815] redundant neg instruction caused by loop-invariant

[Bug target/40815] redundant neg instruction caused by loop-invariant

[carrot at google dot com]

------- Comment #1 from carrot at google dot com  2009-07-21 07:15 -------
Created an attachment (id=18234)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18234&action=view)
test case


-- 


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

[Bug target/40815] New: redundant neg instruction caused by loop-invariant

[carrot at google dot com]

Compile following function with options -Os -mthumb -march=armv5te

void bar(char*, char*, int);
void foo(char* left, char* rite, int element)
{
  while (left <= rite)
  {
    rite -= element;
    bar(left, rite, element);
    left += element;
  }
}

Gcc generates:

        push    {r3, r4, r5, r6, r7, lr}
        mov     r5, r0
        mov     r6, r1
        mov     r7, r2
        neg     r4, r2        // A
        b       .L2
.L3:
        add     r6, r6, r4    // B
        mov     r0, r5
        mov     r1, r6
        mov     r2, r7
        bl      bar
        add     r5, r5, r7
.L2:
        cmp     r5, r6
        bls     .L3
        @ sp needed for prologue
        pop     {r3, r4, r5, r6, r7, pc}

Note that instruction A computes (r4 = -r2), and r4 is only used by instruction
B (r6 = r6 + r4), this can be simplified to (r6 = r6 - r7,  r7 contains the
original r2). Thus we can reduce one instruction.

Expression rite -= element was transformed to the following by the gimplify
pass

    element.0 = (unsigned int) element;
    D.2003 = -element.0;
    rite = rite + D.2003;

This form was kept until pass neg.c.156r.loop2_invariant. Then the expression
-element was identified as loop invariant and hoisted out of the loop. So
caused the current result.

Is the transform of gimplify intended? Do we have any chance to merge the
previous expressions back to (rite = rite - element) before loop invariant
pass?


-- 
           Summary: redundant neg instruction caused by loop-invariant
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: carrot at google dot com
 GCC build triplet: i686-linux
  GCC host triplet: i686-linux
GCC target triplet: arm-eabi


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

[Bug target/40815] redundant neg instruction caused by loop-invariant

[steven at gcc dot gnu dot org]

------- Comment #2 from steven at gcc dot gnu dot org  2009-07-21 07:23 -------
You mean to say that all tree optimizers, CSE, CPROP, fwprop, and combine fail
to eliminate this? Wow.  What does the .expand dump look like (compile with
extra flag -fdump-rtl-expand-details, then attach the .expand dump here).


-- 

steven at gcc dot gnu dot org changed:

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


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

[Bug target/40815] redundant neg instruction caused by loop-invariant

[carrot at google dot com]

------- Comment #3 from carrot at google dot com  2009-07-21 07:35 -------
Created an attachment (id=18235)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18235&action=view)
dump of -fdump-rtl-expand-details


-- 


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

[Bug target/40815] redundant neg instruction caused by loop-invariant

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2009-07-21 09:30 -------
    rite = rite + D.2003;

is a POINTER_PLUS_EXPR, there is no POINTER_MINUS_EXPR so the separate negation
is expected at the tree level.  We can fix this as early as during expansion
(D.2003 should be marked as eligible for TER, so expand could look up the
defining expression and expand a MINUS_EXPR instead of a PLUS_EXPR).


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2009-07-21 09:30:31
               date|                            |


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

[Bug middle-end/40815] redundant neg instruction caused by loop-invariant

[ramana at gcc dot gnu dot org]

------- Comment #5 from ramana at gcc dot gnu dot org  2009-09-18 23:46 -------
This should be a middle end bug rather than  a target bug. TER needs to
maintain state regarding the negate_expr (which is in a previous basic block
but only has a single use) and then we could query the def during expand. 


-- 

ramana at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|target                      |middle-end


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

[Bug middle-end/40815] redundant neg instruction caused by loop-invariant

[rearnsha at gcc dot gnu dot org]

-- 

rearnsha at gcc dot gnu dot org changed:

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


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

[Bug middle-end/40815] redundant neg instruction caused by loop-invariant

[steven at gcc dot gnu dot org]

------- Comment #6 from steven at gcc dot gnu dot org  2010-02-08 16:27 -------
Must be a regression from some version, if POINTER_PLUS_EXPR is the reason for
this extra NEG. Matz knows TER best these days, so matz -> cc.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matz at gcc dot gnu dot org
   Last reconfirmed|2009-07-21 09:30:31         |2010-02-08 16:27:02
               date|                            |


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

[Bug middle-end/40815] redundant neg instruction caused by loop-invariant

[mkuvyrkov at gcc dot gnu dot org]

------- Comment #7 from mkuvyrkov at gcc dot gnu dot org  2010-03-10 19:39 -------
Created an attachment (id=20077)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20077&action=view)
Proposed patch

Richard,

Thank you for the great pointers how to fix this bug.  Here is the proposed
patch to fix it, I am now testing it on both x86_64 and ARM.

One thing I am not sure about in this patch is whether I am forgetting a check
before swapping the operands (to optimize `-a + b' into `b - a') -- is any
check needed for {PLUS, MINUS}_EXPR in this case?

Thank you.


-- 

mkuvyrkov at gcc dot gnu dot org changed:

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


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

[Bug middle-end/40815] redundant neg instruction caused by loop-invariant

[mkuvyrkov at gcc dot gnu dot org]

------- Comment #8 from mkuvyrkov at gcc dot gnu dot org  2010-03-11 08:57 -------
Created an attachment (id=20080)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20080&action=view)
Fixed and tested patch

Well, sure enough the initial patch had an error: `(-a) + (-b)' was getting
optimized into `a + b' instead of (-a) - b.  This new version was tested on
x86_64 without regressions and fixes.  Any comments before I post it to
gcc-patches@ ?

Thanks.


-- 

mkuvyrkov at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #20077|0                           |1
        is obsolete|                            |


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

[Bug middle-end/40815] redundant neg instruction caused by loop-invariant

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2010-03-11 11:19 -------
+                       ops_arr[op_num] = build1 (NOP_EXPR,
+                                                 TREE_TYPE (gimple_assign_lhs
+                                                            (neg)),
+                                                 gimple_assign_rhs1 (neg));

you shouldn't need the conversion.

Btw, as you do not handle POINTER_PLUS_EXPR to compensate the lack of
POINTER_MINUS_EXPR doing the transformation during expansion is bogus.
Instead general re-association should do it.  My original suggestion
was to amend the POINTER_PLUS_EXPR case in expand_expr_real_2 to
lookup the TER expression for treeop1 and in case of it being defined
as -X dispatch to the MINUS_EXPR expansion.


-- 


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

[Bug middle-end/40815] redundant neg instruction caused by loop-invariant

[mkuvyrkov at gcc dot gnu dot org]

------- Comment #10 from mkuvyrkov at gcc dot gnu dot org  2010-04-08 08:20 -------
Subject: Bug 40815

Author: mkuvyrkov
Date: Thu Apr  8 08:20:36 2010
New Revision: 158105

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=158105
Log:
        PR middle-end/40815
        * tree-ssa-reassoc.c (broken_up_substracts): Rename to plus_negates.
        (negate_value): Move code to push elements to broken_up_substracts ...
        (eliminate_plus_minus_pair): ... here.  Push operands that have no
        negative pair to plus_negates.
        (repropagate_negates, init_reassoc, fini_reassoc): Update.

        PR middle-end/40815
        * gcc.dg/tree-ssa/reassoc-19.c: New.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/reassoc-19.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-reassoc.c


-- 


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

[Bug middle-end/40815] redundant neg instruction caused by loop-invariant

[mkuvyrkov at gcc dot gnu dot org]

------- Comment #11 from mkuvyrkov at gcc dot gnu dot org  2010-04-08 08:31 -------
Fixed in the above revision.


-- 

mkuvyrkov at gcc dot gnu dot org changed:

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


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