Richard Guenther - [PATCH] Fix PRs 19431 and 21463 (if conversion with loads) (original) (raw)

This is the mail archive of the gcc-patches@gcc.gnu.orgmailing list for the GCC project.

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]
Other format:	[Raw text]

From: Richard Guenther
To: gcc-patches at gcc dot gnu dot org
Date: Thu, 15 Feb 2007 11:14:43 +0100 (CET)
Subject: [PATCH] Fix PRs 19431 and 21463 (if conversion with loads)

This is the second attempt at solving those PRs which finally allows us to optimize

std::max(std::min(a0, c), std::min(std::max(a1, c), b))

into a sequence of MIN/MAX exprs and get rid of the previously forced addressable variables a0, c, a1 and b.

It's got a little bit too ugly as moving loads with only virtual ssa form (and not pre-computing reaching VUSEs as PRE does), but as I expect the number of transformation opportunities pretty low walking virtual operands should be faster than precomputing reaching VUSEs.

There is the possibility to force PRE to do this transformation (in parts) and the new value numbering promises to also handle the more complex cases. Still PRE is running too late (and there's DCE and other cleanup missing after it) to get rid of the addressability and to trigger MIN/MAX conversion in the phiopt pass.

To allow phiopt to do the transformation to MIN/MAX expr we need at least one DCE, one copyprop and one DOM pass (maybe copyprop + CD-DCE would also do). So I put the new pass right before FRE (we are possibly exposing new FRE opportunities) to get all the required cleanup before the first phiopt run.

As with the previous version we get around 3% runtime improvement for tramp3d and selected libstdc++ performance tests. Compile time effects are in the noise for applications tested by the c++tester.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Ok for mainline?

Thanks, Richard.

2007-02-13 Richard Guenther rguenther@suse.de

PR tree-optimization/19431
PR tree-optimization/21463
* tree-pass.h (pass_phiprop): Declare.
* passes.c (init_optimization_passes): New phiprop pass.
* tree-ssa-forwprop.c (struct phiprop_d): New structure.
(phivn_valid_p): New helper function.
(phiprop_insert_phi): Likewise.
(propagate_with_phi): Likewise.
(tree_ssa_phiprop): New propagator propagating loads
through phi nodes if profitable.
(tree_ssa_forward_propagate_single_use_va): Call it.

* gcc.c-torture/execute/20070212-1.c: New testcase.
* gcc.c-torture/execute/20070212-2.c: Likewise.
* gcc.c-torture/execute/20070212-3.c: Likewise.
* gcc.dg/tree-ssa/pr21463.c: Likewise.
* g++.dg/tree-ssa/pr21463.C: Likewise.
* g++.dg/tree-ssa/pr30738.C: Likewise.

Index: tree-pass.h

* tree-pass.h (revision 121946) --- tree-pass.h (working copy) *********** extern struct tree_opt_pass pass_warn_fu * 288,293 **** --- 288,294 ---- extern struct tree_opt_pass pass_warn_function_noreturn; extern struct tree_opt_pass pass_phiopt; extern struct tree_opt_pass pass_forwprop; + extern struct tree_opt_pass pass_phiprop; extern struct tree_opt_pass pass_dse; extern struct tree_opt_pass pass_nrv; extern struct tree_opt_pass pass_mark_used_blocks; Index: passes.c

* passes.c (revision 121946) --- passes.c (working copy) *********** init_optimization_passes (void) * 523,528 **** --- 523,529 ----
/* Initial scalar cleanups. */ NEXT_PASS (pass_ccp); + NEXT_PASS (pass_phiprop); NEXT_PASS (pass_fre); NEXT_PASS (pass_dce); NEXT_PASS (pass_forwprop); Index: testsuite/gcc.c-torture/execute/20070212-1.c

* testsuite/gcc.c-torture/execute/20070212-1.c (revision 0) --- testsuite/gcc.c-torture/execute/20070212-1.c (revision 0) *********** * 0 **** --- 1,26 ---- + struct f + { + int i; + }; + + int g(int i, int c, struct f ff, int p) + { + int t; + if (c) + t = &i; + else + t = &ff->i; + p = 0; + return *t; + } + + extern void abort(void); + + int main() + { + struct f f; + f.i = 1; + if (g(5, 0, &f, &f.i) != 0) + abort (); + return 0; + } Index: testsuite/gcc.c-torture/execute/20070212-2.c

* testsuite/gcc.c-torture/execute/20070212-2.c (revision 0) --- testsuite/gcc.c-torture/execute/20070212-2.c (revision 0) *********** * 0 **** --- 1,19 ---- + int f(int k, int i1, int j1) + { + int f1; + if(k) + f1 = &i1; + else + f1 = &j1; + i1 = 0; + return f1; + } + + extern void abort (void); + + int main() + { + if (f(1, 1, 2) != 0) + abort (); + return 0; + } Index: testsuite/gcc.c-torture/execute/20070212-3.c

* testsuite/gcc.c-torture/execute/20070212-3.c (revision 0) --- testsuite/gcc.c-torture/execute/20070212-3.c (revision 0) *********** * 0 **** --- 1,30 ---- + struct foo { int i; int j; }; + + int bar (struct foo k, int k2, int f, int f2) + { + int p, q; + int res; + if (f) + p = &k->i; + else + p = &k->j; + res = p; + k->i = 1; + if (f2) + q = p; + else + q = &k2; + return res + *q; + } + + extern void abort (void); + + int main() + { + struct foo k; + k.i = 0; + k.j = 1; + if (bar (&k, 1, 1, 1) != 1) + abort (); + return 0; + } Index: testsuite/g++.dg/tree-ssa/pr30738.C

* testsuite/g++.dg/tree-ssa/pr30738.C (revision 0) --- testsuite/g++.dg/tree-ssa/pr30738.C (revision 0) *********** * 0 **** --- 1,17 ---- + /* { dg-do compile } / + / { dg-options "-O -fdump-tree-phiopt1" } / + + template + static inline const T& + min_ref (const T &x, const T &y) + { + return x < y ? x : y; + } + + int test_min_ref (int x, int y) + { + return min_ref (x, y); + } + + / { dg-final { scan-tree-dump "MIN_EXPR" "phiopt1" } } / + / { dg-final { cleanup-tree-dump "phiopt1" } } */ Index: testsuite/g++.dg/tree-ssa/pr21463.C

* testsuite/g++.dg/tree-ssa/pr21463.C (revision 0) --- testsuite/g++.dg/tree-ssa/pr21463.C (revision 0) *********** * 0 **** --- 1,20 ---- + /* { dg-do compile } / + / { dg-options "-O -fdump-tree-phiopt1" } / + + template static inline const T &ref_max(const T &a, const T &b) + { return a<b ? b : a; } + template static inline const T &ref_min(const T &a, const T &b) + { return a<b ? a : b; } + + template struct foo_t { + T a0, a1; + T bar_ref(const T b, const T c) { + return ref_max(ref_min(a0, c), ref_min(ref_max(a1, c), b)); + } + }; + + template struct foo_t; + + / { dg-final { scan-tree-dump-times "MIN_EXPR" 2 "phiopt1" } } / + / { dg-final { scan-tree-dump-times "MAX_EXPR" 2 "phiopt1" } } / + / { dg-final { cleanup-tree-dump "phiopt1" } } */ Index: testsuite/gcc.dg/tree-ssa/pr21463.c

* testsuite/gcc.dg/tree-ssa/pr21463.c (revision 0) --- testsuite/gcc.dg/tree-ssa/pr21463.c (revision 0) *********** * 0 **** --- 1,23 ---- + /* { dg-do compile } / + / { dg-options "-O -fdump-tree-phiprop" } / + + struct f + { + int i; + }; + + int g(int i, int c, struct f ff, int g) + { + int t; + if (c) + t = &i; + else + t = &ff->i; + if (g) + return t; + else + return t; + } + + / { dg-final { scan-tree-dump-not "\t" "phiprop" } } / + /* { dg-final { cleanup-tree-dump "phiprop" } } */ Index: tree-ssa-forwprop.c

*** tree-ssa-forwprop.c (revision 121950) --- tree-ssa-forwprop.c (working copy) *************** struct tree_opt_pass pass_forwprop = { *** 1071,1073 **** --- 1071,1372 ---- | TODO_verify_ssa, /* todo_flags_finish / 0 / letter */ };

/* Structure to keep track of the value of a dereferenced PHI result
and the set of virtual operands used for that dereference. */
struct phiprop_d
{
tree value;
tree vop_stmt;
};
/* Verify if the value recorded for NAME in PHIVN is still valid at
the start of basic block BB. */
static bool
phivn_valid_p (struct phiprop_d *phivn, tree name, basic_block bb)
{
tree vop_stmt = phivn[SSA_NAME_VERSION (name)].vop_stmt;
ssa_op_iter ui;
tree vuse;
/* The def stmts of all virtual uses need to be post-dominated
```
 by bb.  */
```
FOR_EACH_SSA_TREE_OPERAND (vuse, vop_stmt, ui, SSA_OP_VUSE)
```
{
```
```
  tree use_stmt;
```
```
  imm_use_iterator ui2;
```
```
  bool ok = true;
```

  FOR_EACH_IMM_USE_STMT (use_stmt, ui2, vuse)

```
{
```

  /* If BB does not dominate a VDEF, the value is invalid.  */

  if (((TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT

        && !ZERO_SSA_OPERANDS (use_stmt, SSA_OP_VDEF))

       || TREE_CODE (use_stmt) == PHI_NODE)

      && !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (use_stmt), bb))

```
    {
```
```
      ok = false;
```
```
      BREAK_FROM_IMM_USE_STMT (ui2);
```
```
    }
```
```
}
```
```
  if (!ok)
```
```
return false;
```
```
}
```
return true;
}
/* Insert a new phi node for the dereference of PHI at basic_block
BB with the virtual operands from USE_STMT. */
static tree
phiprop_insert_phi (basic_block bb, tree phi, tree use_stmt,

        struct phiprop_d *phivn, size_t n)

{
tree res, new_phi;
edge_iterator ei;
edge e;
/* Build a new PHI node to replace the definition of
```
 the indirect reference lhs.  */
```
res = GIMPLE_STMT_OPERAND (use_stmt, 0);
SSA_NAME_DEF_STMT (res) = new_phi = create_phi_node (res, bb);
/* Add PHI arguments for each edge inserting loads of the
```
 addressable operands.  */
```
FOR_EACH_EDGE (e, ei, bb->preds)
```
{
```
```
  tree old_arg, new_var, tmp;
```

  old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);

  while (TREE_CODE (old_arg) == SSA_NAME

     && (SSA_NAME_VERSION (old_arg) >= n

         || phivn[SSA_NAME_VERSION (old_arg)].value == NULL_TREE))

```
{
```

  tree def_stmt = SSA_NAME_DEF_STMT (old_arg);

  old_arg = GIMPLE_STMT_OPERAND (def_stmt, 1);

```
}
```
```
  if (TREE_CODE (old_arg) == SSA_NAME)
```

/* Reuse a formely created dereference.  */

new_var = phivn[SSA_NAME_VERSION (old_arg)].value;

```
  else
```
```
{
```
```
  old_arg = TREE_OPERAND (old_arg, 0);
```

  new_var = create_tmp_var (TREE_TYPE (old_arg), NULL);

  tmp = build2 (GIMPLE_MODIFY_STMT, void_type_node,

        NULL_TREE, unshare_expr (old_arg));

  if (TREE_CODE (TREE_TYPE (old_arg)) == COMPLEX_TYPE

      || TREE_CODE (TREE_TYPE (old_arg)) == VECTOR_TYPE)

```
    DECL_GIMPLE_REG_P (new_var) = 1;
```
```
  add_referenced_var (new_var);
```

  new_var = make_ssa_name (new_var, tmp);

  GIMPLE_STMT_OPERAND (tmp, 0) = new_var;

```
  bsi_insert_on_edge (e, tmp);
```
```
  update_stmt (tmp);
```
```
  mark_symbols_for_renaming (tmp);
```
```
}
```
```
  add_phi_arg (new_phi, new_var, e);
```
```
}
```
update_stmt (new_phi);
return res;
}
/* Propagate between the phi node arguments of PHI in BB and phi result
users. For now this matches
```
    # p_2 = PHI <&x, &y>
```
```
  <Lx>:;
```
```
p_3 = p_2;
```
```
z_2 = *p_3;
```
and converts it to
```
# z_2 = PHI <x, y>
```
```
  <Lx>:;
```
Returns true if a transformation was done and edge insertions
need to be committed. Global data PHIVN and N is used to track
past transformation results. We need to be especially careful here
with aliasing issues as we are moving memory reads. */
static bool
propagate_with_phi (basic_block bb, tree phi, struct phiprop_d *phivn, size_t n)
{
tree ptr = PHI_RESULT (phi);
tree use_stmt, res = NULL_TREE;
block_stmt_iterator bsi;
imm_use_iterator ui;
use_operand_p arg_p, use;
ssa_op_iter i;
bool phi_inserted;
if (MTAG_P (SSA_NAME_VAR (ptr))
```
  || !POINTER_TYPE_P (TREE_TYPE (ptr))
```

  || !is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr))))

```
return false;
```
/* Check if we can "cheaply" dereference all phi arguments. */
FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
```
{
```
```
  tree arg = USE_FROM_PTR (arg_p);
```

  /* Walk the ssa chain until we reach a ssa name we already

 created a value for or we reach a definition of the form

```
 ssa_name_n = &var;  */
```
```
  while (TREE_CODE (arg) == SSA_NAME
```
```
     && !SSA_NAME_IS_DEFAULT_DEF (arg)
```
```
     && (SSA_NAME_VERSION (arg) >= n
```

         || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE))

```
{
```

  tree def_stmt = SSA_NAME_DEF_STMT (arg);

  if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)

```
    return false;
```

  arg = GIMPLE_STMT_OPERAND (def_stmt, 1);

```
}
```
```
  if ((TREE_CODE (arg) != ADDR_EXPR
```

   /* Avoid to have to decay *&a to a[0] later.  */

   || !is_gimple_reg_type (TREE_TYPE (TREE_OPERAND (arg, 0))))

```
  && !(TREE_CODE (arg) == SSA_NAME
```

       && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE

       && phivn_valid_p (phivn, arg, bb)))

```
return false;
```
```
}
```
/* Find a dereferencing use. First follow (single use) ssa
```
 copy chains for ptr.  */
```
while (single_imm_use (ptr, &use, &use_stmt)

 && TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT

 && GIMPLE_STMT_OPERAND (use_stmt, 1) == ptr

 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME)

ptr = GIMPLE_STMT_OPERAND (use_stmt, 0);

/* Replace the first dereference of *ptr if there is one and if we

 can move the loads to the place of the ptr phi node.  */

phi_inserted = false;
FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
```
{
```
```
  ssa_op_iter ui2;
```
```
  tree vuse;
```

  /* Check whether this is a load of *ptr.  */

  if (!(TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT

    && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME

    && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == INDIRECT_REF

    && TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 0) == ptr

    /* We cannot replace a load that may throw or is volatile.  */

    && !tree_can_throw_internal (use_stmt)))

```
continue;
```

  /* Check if we can move the loads.  The def stmts of all virtual uses

```
 need to be post-dominated by bb.  */
```

  FOR_EACH_SSA_TREE_OPERAND (vuse, use_stmt, ui2, SSA_OP_VUSE)

```
{
```

  tree def_stmt = SSA_NAME_DEF_STMT (vuse);

```
  if (!SSA_NAME_IS_DEFAULT_DEF (vuse)
```
```
      && (bb_for_stmt (def_stmt) == bb
```

      || !dominated_by_p (CDI_DOMINATORS,

                  bb, bb_for_stmt (def_stmt))))

```
    goto next;
```
```
}
```

  /* Found a proper dereference.  Insert a phi node if this

```
 is the first load transformation.  */
```
```
  if (!phi_inserted)
```
```
{
```

  res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n);

  /* Remember the value we created for *ptr.  */

  phivn[SSA_NAME_VERSION (ptr)].value = res;

  phivn[SSA_NAME_VERSION (ptr)].vop_stmt = use_stmt;

  /* Remove old stmt.  The phi is taken care of by DCE, if we

     want to delete it here we also have to delete all intermediate

```
     copies.  */
```
```
  bsi = bsi_for_stmt (use_stmt);
```
```
  bsi_remove (&bsi, 0);
```
```
  phi_inserted = true;
```
```
}
```
```
  else
```
```
{
```

  /* Further replacements are easy, just make a copy out of the

```
     load.  */
```

  GIMPLE_STMT_OPERAND (use_stmt, 1) = res;

```
  update_stmt (use_stmt);
```
```
}
```
next:;

  /* Continue searching for a proper dereference.  */

```
}
```
return phi_inserted;
}
/* Helper walking the dominator tree starting from BB and processing
phi nodes with global data PHIVN and N. */
static bool
tree_ssa_phiprop_1 (basic_block bb, struct phiprop_d *phivn, size_t n)
{
bool did_something = false;
basic_block son;
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))

did_something |= propagate_with_phi (bb, phi, phivn, n);

for (son = first_dom_son (CDI_DOMINATORS, bb);
```
   son;
```

   son = next_dom_son (CDI_DOMINATORS, son))

did_something |= tree_ssa_phiprop_1 (son, phivn, n);

return did_something;
}
/* Main entry for phiprop pass. */
static unsigned int
tree_ssa_phiprop (void)
{
struct phiprop_d *phivn;
calculate_dominance_info (CDI_DOMINATORS);
phivn = XCNEWVEC (struct phiprop_d, num_ssa_names);
if (tree_ssa_phiprop_1 (ENTRY_BLOCK_PTR, phivn, num_ssa_names))
```
bsi_commit_edge_inserts ();
```
free (phivn);
return 0;
}
static bool
gate_phiprop (void)
{
return 1;
}
struct tree_opt_pass pass_phiprop = {
"phiprop", /* name */
gate_phiprop, /* gate */
tree_ssa_phiprop, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
TV_TREE_FORWPROP, /* tv_id */
PROP_cfg | PROP_ssa, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
TODO_dump_func
| TODO_ggc_collect
| TODO_update_ssa
| TODO_verify_ssa, /* todo_flags_finish */
0 /* letter */
};

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]