[Bug tree-optimization/58459] [4.9 regression] Loop invariant is not hoisted out of loop after r202525.

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Value-numbering it is (-good +bad):

-Value numbering _29 stmt = _29 = _7->key;
+Value numbering _29 stmt = _29 = MEM[(struct S *)&a][j_40].key;
 Setting value number of _29 to _29
...
 Value numbering _18 stmt = _18 = _7->key;
-Setting value number of _18 to _29 (changed)
+Setting value number of _18 to _18 (changed)

and this is because

static bool
forward_propagate_addr_expr (tree name, tree rhs)
{
...
      /* If the use is in a deeper loop nest, then we do not want
         to propagate non-invariant ADDR_EXPRs into the loop as that
         is likely adding expression evaluations into the loop.  */
      if (bb_loop_depth (gimple_bb (use_stmt)) > stmt_loop_depth
          && !is_gimple_min_invariant (rhs))
        {
          all = false;
          continue;

so we do not replace the address in the loop.

Value-numbering does some limited forward propagation, but it does not
handle varying addresses.

The best fix would be to SCCVN, another fix is to either propagate into to
all uses or into no uses.  I lean towards all uses (the above is too strict,
forwarding of say &p->a.b.c should not be constrained).  Note that dependence
analysis will also be confused when present with a mix of a[i][j] and *p
addressing.  Which really boils down to canonicalizing everything to
*p style addressing and lowering the address computation ... (as was my
original MEM_REF plan).