Submitted by Xinliang David Li on Dec. 3, 2013, 10:54 p.m.

Message ID | CAAkRFZ+zmoGm=v2C4jsiiQgz9gKMdd1pcU5pPeJd+fJHzPU_Rw@mail.gmail.com |
---|---|

State | New |

Headers | show |

On Tue, Dec 3, 2013 at 11:54 PM, Xinliang David Li <davidxl@google.com> wrote: > Done. Retested with the suggested change. > > Ok for trunk? Ok. Thanks, Richard. > thanks, > > David > > On Tue, Dec 3, 2013 at 2:13 AM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Mon, Dec 2, 2013 at 6:38 PM, Xinliang David Li <davidxl@google.com> wrote: >>> Points to solver has a bug that can cause complex constraints to be >>> skipped leading to wrong points-to results. In the case that exposed >>> the problem, there is sd constraint: x = *y which is never processed. >>> 'y''s final points to set is { NULL READONLY ESCAPED NOLOCAL}, but 'x' >>> points-to set is {}. >>> >>> What happens is before 'y'' is processed, it is merged with another >>> node 'z' during cycle elimination (the complex constraints get >>> transferred to 'z'), but 'z' is not marked as 'changed' so it is >>> skipped in a later iteration. >>> >>> The attached patch fixed the problem. The problem is exposed by a >>> large program built with -fprofile-generate in LIPO mode -- so there >>> is no small testcase attached. >>> >>> Bootstrapped and regression tested on x86_64-unknown-linux-gnu, OK for trunk? >> >> Hmm, the unify_nodes call in eliminate_indirect_cycles is supposed to >> set the changed bit... which in this special case (updating of complex >> constraints, not the solution!) doesn't happen because unify_nodes doesn't >> consider this as a change. Which needs to change. >> >> So, can you please update your patch to return a bool from >> merge_node_constraints (any change happened?) and update changed >> accordingly in unify_nodes? >> >> Thanks, >> Richard. >> >>> Index: ChangeLog >>> =================================================================== >>> --- ChangeLog (revision 205579) >>> +++ ChangeLog (working copy) >>> @@ -1,3 +1,8 @@ >>> +2013-12-02 Xinliang David Li <davidxl@google.com> >>> + >>> + * tree-ssa-structalias.c (solve_graph): Mark rep node changed >>> + after cycle elimination. >>> + >>> 2013-12-01 Eric Botcazou <ebotcazou@adacore.com> >>> >>> * config/i386/winnt.c (i386_pe_asm_named_section): Be prepared for an >>> Index: tree-ssa-structalias.c >>> =================================================================== >>> --- tree-ssa-structalias.c (revision 205579) >>> +++ tree-ssa-structalias.c (working copy) >>> @@ -2655,8 +2655,13 @@ solve_graph (constraint_graph_t graph) >>> >>> /* In certain indirect cycle cases, we may merge this >>> variable to another. */ >>> - if (eliminate_indirect_cycles (i) && find (i) != i) >>> - continue; >>> + if (eliminate_indirect_cycles (i)) >>> + { >>> + unsigned int rep = find (i); >>> + bitmap_set_bit (changed, rep); >>> + if (i != rep) >>> + continue; >>> + } >>> >>> /* If the node has changed, we need to process the >>> complex constraints and outgoing edges again. */

Index: tree-ssa-structalias.c =================================================================== --- tree-ssa-structalias.c (revision 205643) +++ tree-ssa-structalias.c (working copy) @@ -892,14 +892,16 @@ constraint_vec_find (vec<constraint_t> v return found; } -/* Union two constraint vectors, TO and FROM. Put the result in TO. */ +/* Union two constraint vectors, TO and FROM. Put the result in TO. + Returns true of TO set is changed. */ -static void +static bool constraint_set_union (vec<constraint_t> *to, vec<constraint_t> *from) { int i; constraint_t c; + bool any_change = false; FOR_EACH_VEC_ELT (*from, i, c) { @@ -907,8 +909,10 @@ constraint_set_union (vec<constraint_t> { unsigned int place = to->lower_bound (c, constraint_less); to->safe_insert (place, c); + any_change = true; } } + return any_change; } /* Expands the solution in SET to all sub-fields of variables included. */ @@ -1028,22 +1032,24 @@ insert_into_complex (constraint_graph_t /* Condense two variable nodes into a single variable node, by moving - all associated info from SRC to TO. */ + all associated info from FROM to TO. Returns true if TO node's + constraint set changes after the merge. */ -static void +static bool merge_node_constraints (constraint_graph_t graph, unsigned int to, unsigned int from) { unsigned int i; constraint_t c; + bool any_change = false; gcc_checking_assert (find (from) == to); /* Move all complex constraints from src node into to node */ FOR_EACH_VEC_ELT (graph->complex[from], i, c) { - /* In complex constraints for node src, we may have either - a = *src, and *src = a, or an offseted constraint which are + /* In complex constraints for node FROM, we may have either + a = *FROM, and *FROM = a, or an offseted constraint which are always added to the rhs node's constraints. */ if (c->rhs.type == DEREF) @@ -1052,9 +1058,12 @@ merge_node_constraints (constraint_graph c->lhs.var = to; else c->rhs.var = to; + } - constraint_set_union (&graph->complex[to], &graph->complex[from]); + any_change = constraint_set_union (&graph->complex[to], + &graph->complex[from]); graph->complex[from].release (); + return any_change; } @@ -1472,7 +1481,11 @@ unify_nodes (constraint_graph_t graph, u stats.unified_vars_static++; merge_graph_nodes (graph, to, from); - merge_node_constraints (graph, to, from); + if (merge_node_constraints (graph, to, from)) + { + if (update_changed) + bitmap_set_bit (changed, to); + } /* Mark TO as changed if FROM was changed. If TO was already marked as changed, decrease the changed count. */ Index: ChangeLog =================================================================== --- ChangeLog (revision 205643) +++ ChangeLog (working copy) @@ -1,3 +1,10 @@ +2013-12-03 Xinliang David Li <davidxl@google.com> + + * tree-ssa-structalias.c (constraint_set_union): Change return type + from void to bool. + (merge_node_constraints): Ditto. + (unify_nodes): Update changed set when constraints set changes. + 2013-12-03 Peter Bergner <bergner@vnet.ibm.com> * config/rs6000/htmintrin.h (_TEXASR_INSTRUCTION_FETCH_CONFLICT): Fix