From patchwork Tue Dec 3 22:54:31 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xinliang David Li X-Patchwork-Id: 296349 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 50A352C00A1 for ; Wed, 4 Dec 2013 09:54:51 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; q=dns; s=default; b=UX6RD4Rnh+ke1JbjT8 2MxgFvUxCGPXrZzavpMCPl56LX0nl5/6frq8/VYL+LqknD9g6RX1QrNa3PB504cC +Gwsmy1OsLPMpThWJqLN5xXX/Bon5+nTc0pvXCQgDBiCc4zqBuo43MJ6MwzOTQjY 1CuAoWsj8q5AI0p1rb192TD9o= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; s=default; bh=athNQbxb2KjiKopxfIUJ+R9w Bus=; b=tod0cNvJ2fzEr1ug9+6CsPwyVAj3mfJCbKWDtT469DdPkbPiGHaUfyS/ rDzJ1hUnko9cYoX7vZskVI/qFQUf7x41npynxLoI+RCmASDNPGTijjol9EY/DjJY XmlJOXyu492neO/K1hBGSCMsMx8+2xEFYR8sem/DvVQzV1PVtjY= Received: (qmail 8172 invoked by alias); 3 Dec 2013 22:54:42 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 8157 invoked by uid 89); 3 Dec 2013 22:54:41 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.6 required=5.0 tests=AWL, BAYES_50, RDNS_NONE, SPF_PASS, URIBL_BLOCKED autolearn=no version=3.3.2 X-HELO: mail-we0-f178.google.com Received: from Unknown (HELO mail-we0-f178.google.com) (74.125.82.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Tue, 03 Dec 2013 22:54:40 +0000 Received: by mail-we0-f178.google.com with SMTP id u57so8515581wes.37 for ; Tue, 03 Dec 2013 14:54:31 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=+Zf2bMcxwsYlJuhZnqDksQmlQeTRuJSU/PkaUhh1xgs=; b=YgzfU/FZAMrwX/M2efS+RcfJgguTTgQ1nxzMUrvlNoZVmcFsyu1RjZvOBT0BARYx9G ZqxvFg08l/NMuvq01C+g9/LUGO0yPcjYCEsvCFbSAtFkglNg/z0WS6jXO1HtH6OsvjRC EFEXBycUpmCNmSADl+Th0Eu7JqRikgRTwCsvnsSA8VLVFME7R+4R7ts6k1SI56OFu+9q R+Fq6gFWb592M7CrikL2TRA3XkFZ4i+eAs8hsi6aIIMjyfT68HARZX5FBN7Wt7D/hzzd +5zWS81rzjBe149pLGHcaV2mNGAXnX6GVE1sOuoFlHYAm4kJRqTBWJ2Rm4ARgF7wvl2W kt+w== X-Gm-Message-State: ALoCoQk4aZOyal/JIjprVFp81N1DY0B0SVG596iCphIscxCH1iSlEms9/4Ke7+EdLKLt7+MpkKx8y+DCG9FsoqO7/JDjyswkD0TLWdOY4r2pcWp2s4FRkFWQPwR+CIn2Eagw3eH+YXlJRb16DZ7d+nghekGDl/3n+NaepB29zZwrGw0LpLb7mycaxGllu2Es4VnoUkl7iAtJc93BypkVHuLXO4Izae8Fqw== MIME-Version: 1.0 X-Received: by 10.194.23.201 with SMTP id o9mr4631506wjf.67.1386111271262; Tue, 03 Dec 2013 14:54:31 -0800 (PST) Received: by 10.180.9.98 with HTTP; Tue, 3 Dec 2013 14:54:31 -0800 (PST) In-Reply-To: References: Date: Tue, 3 Dec 2013 14:54:31 -0800 Message-ID: Subject: Re: Fix a bug in points-to solver From: Xinliang David Li To: Richard Biener Cc: GCC Patches X-IsSubscribed: yes Done. Retested with the suggested change. Ok for trunk? thanks, David On Tue, Dec 3, 2013 at 2:13 AM, Richard Biener wrote: > On Mon, Dec 2, 2013 at 6:38 PM, Xinliang David Li 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 >> + >> + * tree-ssa-structalias.c (solve_graph): Mark rep node changed >> + after cycle elimination. >> + >> 2013-12-01 Eric Botcazou >> >> * 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 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 *to, vec *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 { 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 + + * 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 * config/rs6000/htmintrin.h (_TEXASR_INSTRUCTION_FETCH_CONFLICT): Fix