| Message ID | 20241003160836.2297144-2-quic_apinski@quicinc.com |
|---|---|
| State | New |
| Headers | show |
| Series | [1/3] cfgexpand: Expand comment on when non-var clobbers can show up | expand |
On Thu, Oct 3, 2024 at 6:09 PM Andrew Pinski <quic_apinski@quicinc.com> wrote: > > After fixing loop-im to do the correct overflow rewriting > for pointer types too. We end up with code like: > ``` > _9 = (unsigned long) &g; > _84 = _9 + 18446744073709551615; > _11 = _42 + _84; > _44 = (signed char *) _11; > ... > *_44 = 10; > g ={v} {CLOBBER(eos)}; > ... > n[0] = &f; > *_44 = 8; > g ={v} {CLOBBER(eos)}; > ``` > Which was not being recongized by the scope conflicts code. > This was because it only handled one level walk backs rather than multiple ones. > This fixes it by using a work_list to avoid huge recursion and a visited bitmape to avoid > going into an infinite loops when dealing with loops. Ick. This is now possibly an unbound walk from every use (even duplicate use!). Micro-optimizing would be restricting the INTEGRAL_TYPE_P types to ones matching pointer size. Another micro-optimization would be to track/cache whether a SSA def is based on a pointer, more optimizing to cache what pointer(s!) it is based on. There's testcases in bugzilla somewhere hard on compile-time in this code and I can imagine a trivial degenerate one to trigger the issue. Richard. > Bootstrapped and tested on x86_64-linux-gnu. > > PR tree-optimization/111422 > > gcc/ChangeLog: > > * cfgexpand.cc (add_scope_conflicts_2): Rewrite to be a full walk > of all operands and their uses. > > Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com> > --- > gcc/cfgexpand.cc | 46 +++++++++++++++++++++++++++------------------- > 1 file changed, 27 insertions(+), 19 deletions(-) > > diff --git a/gcc/cfgexpand.cc b/gcc/cfgexpand.cc > index 6c1096363af..2e653d7207c 100644 > --- a/gcc/cfgexpand.cc > +++ b/gcc/cfgexpand.cc > @@ -573,32 +573,40 @@ visit_conflict (gimple *, tree op, tree, void *data) > > /* Helper function for add_scope_conflicts_1. For USE on > a stmt, if it is a SSA_NAME and in its SSA_NAME_DEF_STMT is known to be > - based on some ADDR_EXPR, invoke VISIT on that ADDR_EXPR. */ > + based on some ADDR_EXPR, invoke VISIT on that ADDR_EXPR. Also walk > + the assignments backwards as they might be based on an ADDR_EXPR. */ > > -static inline void > +static void > add_scope_conflicts_2 (tree use, bitmap work, > walk_stmt_load_store_addr_fn visit) > { > - if (TREE_CODE (use) == SSA_NAME > - && (POINTER_TYPE_P (TREE_TYPE (use)) > - || INTEGRAL_TYPE_P (TREE_TYPE (use)))) > + auto_vec<tree, 4> work_list; > + auto_bitmap visited_ssa_names; > + work_list.safe_push (use); > + > + while (!work_list.is_empty()) > { > - gimple *g = SSA_NAME_DEF_STMT (use); > - if (gassign *a = dyn_cast <gassign *> (g)) > + use = work_list.pop(); > + if (!use) > + continue; > + if (TREE_CODE (use) == ADDR_EXPR) > + visit (nullptr, TREE_OPERAND (use, 0), use, work); > + else if (TREE_CODE (use) == SSA_NAME > + && (POINTER_TYPE_P (TREE_TYPE (use)) > + || INTEGRAL_TYPE_P (TREE_TYPE (use)))) > { > - if (tree op = gimple_assign_rhs1 (a)) > - if (TREE_CODE (op) == ADDR_EXPR) > - visit (a, TREE_OPERAND (op, 0), op, work); > + gimple *g = SSA_NAME_DEF_STMT (use); > + if (!bitmap_set_bit (visited_ssa_names, SSA_NAME_VERSION(use))) > + continue; > + if (gassign *a = dyn_cast <gassign *> (g)) > + { > + for (unsigned i = 1; i < gimple_num_ops (g); i++) > + work_list.safe_push (gimple_op (a, i)); > + } > + else if (gphi *p = dyn_cast <gphi *> (g)) > + for (unsigned i = 0; i < gimple_phi_num_args (p); ++i) > + work_list.safe_push (gimple_phi_arg_def (p, i)); > } > - else if (gphi *p = dyn_cast <gphi *> (g)) > - for (unsigned i = 0; i < gimple_phi_num_args (p); ++i) > - if (TREE_CODE (use = gimple_phi_arg_def (p, i)) == SSA_NAME) > - if (gassign *a = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (use))) > - { > - if (tree op = gimple_assign_rhs1 (a)) > - if (TREE_CODE (op) == ADDR_EXPR) > - visit (a, TREE_OPERAND (op, 0), op, work); > - } > } > } > > -- > 2.34.1 >
On Fri, Oct 4, 2024, 12:07 AM Richard Biener <richard.guenther@gmail.com> wrote: > On Thu, Oct 3, 2024 at 6:09 PM Andrew Pinski <quic_apinski@quicinc.com> > wrote: > > > > After fixing loop-im to do the correct overflow rewriting > > for pointer types too. We end up with code like: > > ``` > > _9 = (unsigned long) &g; > > _84 = _9 + 18446744073709551615; > > _11 = _42 + _84; > > _44 = (signed char *) _11; > > ... > > *_44 = 10; > > g ={v} {CLOBBER(eos)}; > > ... > > n[0] = &f; > > *_44 = 8; > > g ={v} {CLOBBER(eos)}; > > ``` > > Which was not being recongized by the scope conflicts code. > > This was because it only handled one level walk backs rather than > multiple ones. > > This fixes it by using a work_list to avoid huge recursion and a visited > bitmape to avoid > > going into an infinite loops when dealing with loops. > > Ick. This is now possibly an unbound walk from every use (even duplicate > use!). > Micro-optimizing would be restricting the INTEGRAL_TYPE_P types to ones > matching pointer size. Another micro-optimization would be to track/cache > whether a SSA def is based on a pointer, more optimizing to cache what > pointer(s!) it is based on. > > There's testcases in bugzilla somewhere hard on compile-time in this code > and I can imagine a trivial degenerate one to trigger the issue. > I was thinking about that too. Adding a cache should easy. Especially one that lives over the whole walk of the basic blocks. And yes stopping at integer sizes which is less than a pointer size seems also a reasonable idea. Note I have a patch on top of this that were vector types and constructs are handled too. Will work on this tomorrow. Thanks, Andrew > Richard. > > > Bootstrapped and tested on x86_64-linux-gnu. > > > > PR tree-optimization/111422 > > > > gcc/ChangeLog: > > > > * cfgexpand.cc (add_scope_conflicts_2): Rewrite to be a full walk > > of all operands and their uses. > > > > Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com> > > --- > > gcc/cfgexpand.cc | 46 +++++++++++++++++++++++++++------------------- > > 1 file changed, 27 insertions(+), 19 deletions(-) > > > > diff --git a/gcc/cfgexpand.cc b/gcc/cfgexpand.cc > > index 6c1096363af..2e653d7207c 100644 > > --- a/gcc/cfgexpand.cc > > +++ b/gcc/cfgexpand.cc > > @@ -573,32 +573,40 @@ visit_conflict (gimple *, tree op, tree, void > *data) > > > > /* Helper function for add_scope_conflicts_1. For USE on > > a stmt, if it is a SSA_NAME and in its SSA_NAME_DEF_STMT is known to > be > > - based on some ADDR_EXPR, invoke VISIT on that ADDR_EXPR. */ > > + based on some ADDR_EXPR, invoke VISIT on that ADDR_EXPR. Also walk > > + the assignments backwards as they might be based on an ADDR_EXPR. */ > > > > -static inline void > > +static void > > add_scope_conflicts_2 (tree use, bitmap work, > > walk_stmt_load_store_addr_fn visit) > > { > > - if (TREE_CODE (use) == SSA_NAME > > - && (POINTER_TYPE_P (TREE_TYPE (use)) > > - || INTEGRAL_TYPE_P (TREE_TYPE (use)))) > > + auto_vec<tree, 4> work_list; > > + auto_bitmap visited_ssa_names; > > + work_list.safe_push (use); > > + > > + while (!work_list.is_empty()) > > { > > - gimple *g = SSA_NAME_DEF_STMT (use); > > - if (gassign *a = dyn_cast <gassign *> (g)) > > + use = work_list.pop(); > > + if (!use) > > + continue; > > + if (TREE_CODE (use) == ADDR_EXPR) > > + visit (nullptr, TREE_OPERAND (use, 0), use, work); > > + else if (TREE_CODE (use) == SSA_NAME > > + && (POINTER_TYPE_P (TREE_TYPE (use)) > > + || INTEGRAL_TYPE_P (TREE_TYPE (use)))) > > { > > - if (tree op = gimple_assign_rhs1 (a)) > > - if (TREE_CODE (op) == ADDR_EXPR) > > - visit (a, TREE_OPERAND (op, 0), op, work); > > + gimple *g = SSA_NAME_DEF_STMT (use); > > + if (!bitmap_set_bit (visited_ssa_names, SSA_NAME_VERSION(use))) > > + continue; > > + if (gassign *a = dyn_cast <gassign *> (g)) > > + { > > + for (unsigned i = 1; i < gimple_num_ops (g); i++) > > + work_list.safe_push (gimple_op (a, i)); > > + } > > + else if (gphi *p = dyn_cast <gphi *> (g)) > > + for (unsigned i = 0; i < gimple_phi_num_args (p); ++i) > > + work_list.safe_push (gimple_phi_arg_def (p, i)); > > } > > - else if (gphi *p = dyn_cast <gphi *> (g)) > > - for (unsigned i = 0; i < gimple_phi_num_args (p); ++i) > > - if (TREE_CODE (use = gimple_phi_arg_def (p, i)) == SSA_NAME) > > - if (gassign *a = dyn_cast <gassign *> (SSA_NAME_DEF_STMT > (use))) > > - { > > - if (tree op = gimple_assign_rhs1 (a)) > > - if (TREE_CODE (op) == ADDR_EXPR) > > - visit (a, TREE_OPERAND (op, 0), op, work); > > - } > > } > > } > > > > -- > > 2.34.1 > > >
diff --git a/gcc/cfgexpand.cc b/gcc/cfgexpand.cc index 6c1096363af..2e653d7207c 100644 --- a/gcc/cfgexpand.cc +++ b/gcc/cfgexpand.cc @@ -573,32 +573,40 @@ visit_conflict (gimple *, tree op, tree, void *data) /* Helper function for add_scope_conflicts_1. For USE on a stmt, if it is a SSA_NAME and in its SSA_NAME_DEF_STMT is known to be - based on some ADDR_EXPR, invoke VISIT on that ADDR_EXPR. */ + based on some ADDR_EXPR, invoke VISIT on that ADDR_EXPR. Also walk + the assignments backwards as they might be based on an ADDR_EXPR. */ -static inline void +static void add_scope_conflicts_2 (tree use, bitmap work, walk_stmt_load_store_addr_fn visit) { - if (TREE_CODE (use) == SSA_NAME - && (POINTER_TYPE_P (TREE_TYPE (use)) - || INTEGRAL_TYPE_P (TREE_TYPE (use)))) + auto_vec<tree, 4> work_list; + auto_bitmap visited_ssa_names; + work_list.safe_push (use); + + while (!work_list.is_empty()) { - gimple *g = SSA_NAME_DEF_STMT (use); - if (gassign *a = dyn_cast <gassign *> (g)) + use = work_list.pop(); + if (!use) + continue; + if (TREE_CODE (use) == ADDR_EXPR) + visit (nullptr, TREE_OPERAND (use, 0), use, work); + else if (TREE_CODE (use) == SSA_NAME + && (POINTER_TYPE_P (TREE_TYPE (use)) + || INTEGRAL_TYPE_P (TREE_TYPE (use)))) { - if (tree op = gimple_assign_rhs1 (a)) - if (TREE_CODE (op) == ADDR_EXPR) - visit (a, TREE_OPERAND (op, 0), op, work); + gimple *g = SSA_NAME_DEF_STMT (use); + if (!bitmap_set_bit (visited_ssa_names, SSA_NAME_VERSION(use))) + continue; + if (gassign *a = dyn_cast <gassign *> (g)) + { + for (unsigned i = 1; i < gimple_num_ops (g); i++) + work_list.safe_push (gimple_op (a, i)); + } + else if (gphi *p = dyn_cast <gphi *> (g)) + for (unsigned i = 0; i < gimple_phi_num_args (p); ++i) + work_list.safe_push (gimple_phi_arg_def (p, i)); } - else if (gphi *p = dyn_cast <gphi *> (g)) - for (unsigned i = 0; i < gimple_phi_num_args (p); ++i) - if (TREE_CODE (use = gimple_phi_arg_def (p, i)) == SSA_NAME) - if (gassign *a = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (use))) - { - if (tree op = gimple_assign_rhs1 (a)) - if (TREE_CODE (op) == ADDR_EXPR) - visit (a, TREE_OPERAND (op, 0), op, work); - } } }
After fixing loop-im to do the correct overflow rewriting for pointer types too. We end up with code like: ``` _9 = (unsigned long) &g; _84 = _9 + 18446744073709551615; _11 = _42 + _84; _44 = (signed char *) _11; ... *_44 = 10; g ={v} {CLOBBER(eos)}; ... n[0] = &f; *_44 = 8; g ={v} {CLOBBER(eos)}; ``` Which was not being recongized by the scope conflicts code. This was because it only handled one level walk backs rather than multiple ones. This fixes it by using a work_list to avoid huge recursion and a visited bitmape to avoid going into an infinite loops when dealing with loops. Bootstrapped and tested on x86_64-linux-gnu. PR tree-optimization/111422 gcc/ChangeLog: * cfgexpand.cc (add_scope_conflicts_2): Rewrite to be a full walk of all operands and their uses. Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com> --- gcc/cfgexpand.cc | 46 +++++++++++++++++++++++++++------------------- 1 file changed, 27 insertions(+), 19 deletions(-)