[Bug tree-optimization/23286] missed fully redundant expression

[Bug tree-optimization/23286] missed fully redundant expression

[rguenth at gcc dot gnu.org]

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

--- Comment #31 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-11-16 14:39:50 UTC ---
(In reply to comment #29)
> I intended to work on this for GCC 4.6.  There are many vectorizer failures
> with the v3 patch. My local copy of the patch is at v6 :-)  I'll see if I can
> make some time to "forward-port" the differences between my v3 and v6 to
> Richi's updated patch.

I don't remember if you did send me your v6 privately (I at least can't find
it),
can you simply dump your most current variant here?

Thx.

[Bug tree-optimization/23286] missed fully redundant expression

[pinskia at gcc dot gnu.org]

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

--- Comment #32 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-07-20 00:40:39 UTC ---
Anyone working on this?  I have found this happens internally a bit (after
expanding of bitfields accesses).

[Bug tree-optimization/23286] missed fully redundant expression

[pinskia at gcc dot gnu.org]

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

--- Comment #33 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-07-29 20:11:29 UTC ---
(In reply to comment #26)
> Created attachment 19634 [details]
> updated patch
This patch fails on the trunk now with:
/data/src/gcc-cavium/gcc-4.6-upgrade/src/libstdc++-v3/src/strstream.cc: In
destructor ‘virtual std::strstream::~strstream()’:
/data/src/gcc-cavium/gcc-4.6-upgrade/src/libstdc++-v3/src/strstream.cc:399:3:
error: statement marked for throw in middle of block
# .MEM_23 = VDEF <.MEM_22>
std::strstreambuf::~strstreambuf (D.20970_7);

[Bug tree-optimization/23286] missed fully redundant expression

[rguenth at gcc dot gnu.org]

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

--- Comment #34 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-02-15 11:19:55 UTC ---
*** Bug 52256 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/23286] missed fully redundant expression

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

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

--- Comment #35 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-02-15 15:55:52 UTC ---
Created attachment 26665
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26665
forward ported patch

I made the patch apply and build again (unbootstrapped/tested).

Steven, if you happen to have a "latest" patch around from yours somewhere
I'd appreciate if you can make it appear in my inbox somehow ... I'll integrate
it with my changes.  Thx.

[Bug tree-optimization/23286] missed fully redundant expression

[steven at gcc dot gnu.org]

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

--- Comment #36 from Steven Bosscher <steven at gcc dot gnu.org> 2012-02-15 18:37:40 UTC ---
The patch was on one of the gsyprf machines, which are gone (didn't I already
tell you this before??). So the "latest" patch is lost...

[Bug tree-optimization/23286] missed fully redundant expression

[rguenther at suse dot de]

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

--- Comment #37 from rguenther at suse dot de <rguenther at suse dot de> 2012-02-16 09:37:54 UTC ---
On Wed, 15 Feb 2012, steven at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23286
> 
> --- Comment #36 from Steven Bosscher <steven at gcc dot gnu.org> 2012-02-15 18:37:40 UTC ---
> The patch was on one of the gsyprf machines, which are gone (didn't I already
> tell you this before??). So the "latest" patch is lost...

Not sure, I might simply have forgotten it ;)  I'm going to make the
patch bootstrap again (still fails with the EH problem right now).

[Bug tree-optimization/23286] missed fully redundant expression

[rguenth at gcc dot gnu.org]

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

--- Comment #38 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-02-16 12:44:31 UTC ---
Incremental patch to fix the EH related ICEs:

Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c.orig     2012-02-16 12:08:57.000000000 +0100
+++ gcc/tree-ssa-pre.c  2012-02-16 12:08:50.000000000 +0100
@@ -3937,7 +3937,8 @@ do_hoist_insertion (basic_block block AT
       find_or_generate_expression (block, expr, &stmts, NULL);

       last = gsi_last_bb (block);
-      if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last)))
+      if (gsi_end_p (last)
+         || stmt_ends_bb_p (gsi_stmt (last)))
        gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT);
       else
        gsi_insert_seq_after (&last, stmts, GSI_SAME_STMT);

when hoisting into

  # BLOCK 19
  # PRED: 18 (fallthru,exec)
  [LP 15] D.2722_10 = CYapfBaseT::PfGetSettings (D.2723_9);
  goto <bb 20>;
  # SUCC: 20 (fallthru,exec) 113 (eh,exec)

but of course we'd have to verify we can hoist across such throwing
stmt (it might be a store clobbering what we insert),
so maybe disabling hoisting in that case would be more appropriate.
With

Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c.orig     2012-02-16 12:28:04.000000000 +0100
+++ gcc/tree-ssa-pre.c  2012-02-16 12:27:37.000000000 +0100
@@ -3874,6 +3874,7 @@ do_hoist_insertion (basic_block block AT
   bitmap_iterator bi;
   bitmap_set_t hoistable_set;
   bitmap availout_in_some;
+  gimple_stmt_iterator last;

   /* At least two successors, or else...  */
   gcc_assert (EDGE_COUNT (block->succs) >= 2);
@@ -3886,6 +3887,14 @@ do_hoist_insertion (basic_block block AT
     if (! single_pred_p (e->dest))
       return false;

+  /* Determine the insertion point.  If we cannot safely insert before
+     the last stmt if we'd have to, bail out.  */
+  last = gsi_last_bb (block);
+  if (!gsi_end_p (last)
+      && !is_ctrl_stmt (gsi_stmt (last))
+      && stmt_ends_bb_p (gsi_stmt (last)))
+    return false;
+
   hoistable_set = bitmap_set_new ();
   availout_in_some = BITMAP_ALLOC (&grand_bitmap_obstack);

@@ -3916,7 +3925,6 @@ do_hoist_insertion (basic_block block AT
       pre_expr expr = expression_for_id (i);
       unsigned int value_id = get_expr_value_id (expr);
       gimple_seq stmts = NULL;
-      gimple_stmt_iterator last;

       /* If the value of this expression is not available in at least one
         successor, do not hoist the value.  */
@@ -3936,7 +3944,6 @@ do_hoist_insertion (basic_block block AT

       find_or_generate_expression (block, expr, &stmts, NULL);

-      last = gsi_last_bb (block);
       if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last)))
        gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT);
       else

Which leaves us with

/abuild/rguenther/obj/./gcc/xgcc -B/abuild/rguenther/obj/./gcc/
-B/usr/local/x86_64-unknown-linux-gnu/bin/
-B/usr/local/x86_64-unknown-linux-gnu/lib/ -isystem
/usr/local/x86_64-unknown-linux-gnu/include -isystem
/usr/local/x86_64-unknown-linux-gnu/sys-include    -c -g -O2 -m32 -fpic  -W
-Wall -gnatpg -nostdinc -m32  a-nlrear.ads -o a-nlrear.o

raised STORAGE_ERROR : stack overflow or erroneous memory access
make[9]: *** [a-nlrear.o] Error 1

during stage3 libada build ...

[Bug tree-optimization/23286] missed fully redundant expression

[rguenth at gcc dot gnu.org]

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

--- Comment #39 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-02-20 11:50:00 UTC ---
Apart from that libada bootstrap issue (reproduces with the stage1 compiler),
the testsuite is clean apart from vectorizer testcases which show that
do_hoist_insertion is hoisting stmts across loops


  for (i = 0; i < N; i++) {
    diff = 0;
    for (j = k; j < M; j+=4) {
      diff += in[j+i]*coeff[j];
    }
    out[i] = out[i] + diff;
  }

is turned into

  for (i = 0; i < N; i++) {
    diff = 0;
    tem = out[i];
    for (j = k; j < M; j+=4) {
      diff += in[j+i]*coeff[j];
    }
    out[i] = tem + diff;
  }

which confuses outer loop vectorization enough to make it fail for

FAIL: gcc.dg/vect/vect-outer-fir-big-array.c -flto scan-tree-dump-times vect
"OU
TER LOOP VECTORIZED" 2
FAIL: gcc.dg/vect/vect-outer-fir-lb-big-array.c -flto scan-tree-dump-times vect 
"OUTER LOOP VECTORIZED" 2
FAIL: gcc.dg/vect/vect-outer-fir-lb.c -flto scan-tree-dump-times vect "OUTER
LOO
P VECTORIZED" 2
FAIL: gcc.dg/vect/vect-outer-fir.c -flto scan-tree-dump-times vect "OUTER LOOP
V
ECTORIZED" 2

[Bug tree-optimization/23286] missed fully redundant expression

[aldot at gcc dot gnu.org]

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

--- Comment #40 from Bernhard Reutner-Fischer <aldot at gcc dot gnu.org> 2012-02-23 13:34:37 UTC ---
The ATTRIBUTE_UNUSED of do_hoist_insertion can be removed.

diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 0f777b4..bfc7a92 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -3865,7 +3865,7 @@ do_pre_partial_partial_insertion (basic_block block,
basic_block dom)
    The caller has to make sure that BLOCK has at least two successors.  */

 static bool
-do_hoist_insertion (basic_block block ATTRIBUTE_UNUSED)
+do_hoist_insertion (basic_block block)
 {
   edge e;
   edge_iterator ei;
@@ -3878,6 +3878,13 @@ do_hoist_insertion (basic_block block ATTRIBUTE_UNUSED)
   /* At least two successors, or else...  */
   gcc_assert (EDGE_COUNT (block->succs) >= 2);

+  /* We cheat about AVAIL_OUT in the first block
+     so pretend we are done in the second iteration.  */
+  if (block->prev_bb
+      && block->prev_bb->index == ENTRY_BLOCK
+      && pre_stats.hoist_insert)
+    return false;
+
   /* Check that all successors of BLOCK are dominated by block.
      We could use dominated_by_p() for this, but actually there is a much
      quicker check: any successor that is dominated by BLOCK can't have
@@ -3890,9 +3897,12 @@ do_hoist_insertion (basic_block block ATTRIBUTE_UNUSED)
   availout_in_some = BITMAP_ALLOC (&grand_bitmap_obstack);

   /* A hoistable value must be in ANTIC_IN(block)
-     but not in AVAIL_OUT(BLOCK).  */
+     but not in AVAIL_OUT(BLOCK).
+     To give more opportunity to hoisting,
+     cheat by disregarding AVAIL_OUT of the ENTRY_BLOCK.  */
   bitmap_set_copy (hoistable_set, ANTIC_IN (block));
-  bitmap_set_subtract_values (hoistable_set, AVAIL_OUT (block));
+  if (block->prev_bb && block->prev_bb->index != ENTRY_BLOCK)
+    bitmap_set_subtract_values (hoistable_set, AVAIL_OUT (block));

   /* Short-cut for a common case: hoistable_set is empty.  */
   if (bitmap_empty_p (&hoistable_set->values))


so for a simplified PR5738
$ cat pr5738.c
struct foo
{
  unsigned short *p;
};

#define foo_s s
void
func (struct foo *foo_s, unsigned int *coord, _Bool delta)
{
  unsigned short change;

  if (delta)
    {
      change = *((foo_s)->p++);
      *coord += change;
    }
  else
    {
      change = *((foo_s)->p++);
      *coord += change;
//      *coord += *((foo_s)->p++) << 8;
    }
}

we end up a little bit better, with something like

func (struct foo * sD.1705, unsigned intD.9 * coordD.1706, _BoolD.1685
deltaD.1707)
{
  unsigned intD.9 pretmp.6D.1727;
  short unsigned intD.16 * pretmp.5D.1726;
  short unsigned intD.16 pretmp.4D.1725;
  short unsigned intD.16 * pretmp.3D.1724;
  short unsigned intD.16 changeD.1710;
  unsigned intD.9 D.1718;
  unsigned intD.9 D.1717;
  unsigned intD.9 D.1716;
  short unsigned intD.16 * D.1715;
  short unsigned intD.16 * D.1714;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # VUSE <.MEMD.1720_17(D)>
  # PT = nonlocal escaped 
  pretmp.3D.1724_22 = sD.1705_2(D)->pD.1704;
  # VUSE <.MEMD.1720_17(D)>
  pretmp.4D.1725_23 = *pretmp.3D.1724_22;
  # PT = nonlocal escaped 
  pretmp.5D.1726_24 = pretmp.3D.1724_22 + 2;
  # VUSE <.MEMD.1720_17(D)>
  pretmp.6D.1727_25 = *coordD.1706_6(D);
  pretmp.6D.1727_26 = (unsigned intD.9) pretmp.4D.1725_23;
  pretmp.6D.1727_27 = pretmp.6D.1727_25 + pretmp.6D.1727_26;
  if (deltaD.1707_1(D) != 0)
    goto <bb 3>;
  else
    goto <bb 4>;
  # SUCC: 3 [39.0%]  (true,exec) 4 [61.0%]  (false,exec)

  # BLOCK 3 freq:3900
  # PRED: 2 [39.0%]  (true,exec)
  # .MEMD.1720_18 = VDEF <.MEMD.1720_17(D)>
  sD.1705_2(D)->pD.1704 = pretmp.5D.1726_24;
  # .MEMD.1720_19 = VDEF <.MEMD.1720_18>
  *coordD.1706_6(D) = pretmp.6D.1727_27;
  goto <bb 5>;
  # SUCC: 5 [100.0%]  (fallthru,exec)

  # BLOCK 4 freq:6100
  # PRED: 2 [61.0%]  (false,exec)
  # .MEMD.1720_20 = VDEF <.MEMD.1720_17(D)>
  sD.1705_2(D)->pD.1704 = pretmp.5D.1726_24;
  # .MEMD.1720_21 = VDEF <.MEMD.1720_20>
  *coordD.1706_6(D) = pretmp.6D.1727_27;
  # SUCC: 5 [100.0%]  (fallthru,exec)

  # BLOCK 5 freq:10000
  # PRED: 3 [100.0%]  (fallthru,exec) 4 [100.0%]  (fallthru,exec)
  # .MEMD.1720_16 = PHI <.MEMD.1720_19(3), .MEMD.1720_21(4)>
  # VUSE <.MEMD.1720_16>
  return;
  # SUCC: EXIT [100.0%] 

}
which translates to nearly proper code:

func:
.LFB0:
        .cfi_startproc
        movq    (%rdi), %rax    # sD.1705_2(D)->pD.1704, pretmp.3D.1724
        leaq    2(%rax), %rcx   #, pretmp.5D.1726
        movzwl  (%rax), %eax    # *pretmp.3D.1724_22, pretmp.6D.1727
        addl    (%rsi), %eax    # *coordD.1706_6(D), pretmp.6D.1727
        testb   %dl, %dl        # deltaD.1707
        movq    %rcx, (%rdi)    # pretmp.5D.1726, sD.1705_2(D)->pD.1704
        movl    %eax, (%rsi)    # pretmp.6D.1727, *coordD.1706_6(D)
        je      .L2     #,
        ret
.L2:
        ret
        .cfi_endproc

where the expected code would be something like (i think):

func:
.LFB0:
        .cfi_startproc
        movq    (%rdi), %rax    # sD.1705_2(D)->pD.1704, D.1714
        movzwl  (%rax), %edx    #* D.1714, changeD.1710
        addq    $2, %rax        #, tmp77
        movq    %rax, (%rdi)    # tmp77, sD.1705_2(D)->pD.1704
        addl    %edx, (%rsi)    # changeD.1710, *coordD.1706_6(D)
        ret
        .cfi_endproc
.LFE0:

So we just need to recognize that BB3 and BB4 are identical (everything in BB3
can be hoisted and BB4 is dead).

[Bug tree-optimization/23286] Missed code hoisting optimization

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=23286
Bug 23286 depends on bug 5738, which changed state.

Bug 5738 Summary: Missed code hoisting opportunity
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=5738

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