From patchwork Wed Nov 2 17:16:55 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 690507 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)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3t8FCG4tXhz9vFF for ; Thu, 3 Nov 2016 04:17:11 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=oBZBHPLR; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=CfRJ9kr5pV/nRq0/iJD5/NQmgkMlFhCBtNHH+n745pVUUkxgXI jy7aDAem4xhvg+mRLdlQe3xL13Cqpo3cIV25DK2oTDJWhblGnKQCtCs9fpVdV5kg P5AKDb4FO1VhC18AcjozISZOzb4N9I5wCmNXhpZR827LZovYv4+ogT80E= 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:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=vB1rDosDewbuirHP6A2JheQi85w=; b=oBZBHPLR5F9pmQiQm9sW aBuwpY8oHE1YCNTisALkvxljkg+VbQc6i/KaR4lqydtVoaNDBkRLI4hgUyfXULt4 Qfi1T+N5FyS24eX1V917vPXiyvoaNeFPjuXL1vt/vx52Axpb2CV6JlBzMnKJae9W KU4YpjUK+57ecG6eS3OBBDE= Received: (qmail 70358 invoked by alias); 2 Nov 2016 17:17:01 -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 70348 invoked by uid 89); 2 Nov 2016 17:17:01 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-4.2 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=states X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 02 Nov 2016 17:16:59 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 1A45761B97 for ; Wed, 2 Nov 2016 17:16:58 +0000 (UTC) Received: from reynosa.quesejoda.com (unused [10.10.50.254] (may be forged)) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id uA2HGuwS022958; Wed, 2 Nov 2016 13:16:56 -0400 To: Jeff Law , gcc-patches From: Aldy Hernandez Subject: PR61409: -Wmaybe-uninitialized false-positive with -O2 Message-ID: <8c90256b-a9a1-b849-08ce-9435fdb8c770@redhat.com> Date: Wed, 2 Nov 2016 10:16:55 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.4.0 MIME-Version: 1.0 Hi Jeff. As discussed in the PR, here is a patch exploring your idea of ignoring unguarded uses if we can prove that the guards for such uses are invalidated by the uninitialized operand paths being executed. This is an updated patch from my suggestion in the PR. It bootstraps with no regression on x86-64 Linux, and fixes the PR in question. As the "NOTE:" in the code states, we could be much smarter when invalidating predicates, but for now let's do straight negation which works for the simple case. We could expand on this in the future. OK for trunk? commit 8375d7e28c1a798dd0cc0f487d7fa1068d9eb124 Author: Aldy Hernandez Date: Thu Aug 25 10:44:29 2016 -0400 PR middle-end/61409 * tree-ssa-uninit.c (use_pred_not_overlap_with_undef_path_pred): Remove reference to missing NUM_PREDS in function comment. (can_one_predicate_be_invalidated_p): New. (can_chain_union_be_invalidated_p): New. (flatten_out_predicate_chains): New. (uninit_ops_invalidate_phi_use): New. (is_use_properly_guarded): Call uninit_ops_invalidate_phi_use. diff --git a/gcc/testsuite/gcc.dg/uninit-pr61409.c b/gcc/testsuite/gcc.dg/uninit-pr61409.c new file mode 100644 index 0000000..c27a67b --- /dev/null +++ b/gcc/testsuite/gcc.dg/uninit-pr61409.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -Wuninitialized" } */ + +int *rw; +int line_height; +int pixel_width; +int text_cols; +int width1, width2, width3; + +void *pointer; + +void f (int i, int j) +{ + void *ptr; + if (i) + { + if (j) + return; + ptr = pointer; + } + pixel_width = 1234 + width1 + 2 * width2 + 2 * width3; + *rw = text_cols + line_height; + if (i) + rw=ptr; /* { dg-bogus "uninitialized" "bogus warning" } */ +} diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c index 1344854..37c99a7 100644 --- a/gcc/tree-ssa-uninit.c +++ b/gcc/tree-ssa-uninit.c @@ -1184,11 +1184,10 @@ prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def, transformation which eliminates the merge point thus makes path sensitive analysis unnecessary.) - NUM_PREDS is the number is the number predicate chains, PREDS is - the array of chains, PHI is the phi node whose incoming (undefined) - paths need to be pruned, and UNINIT_OPNDS is the bitmap holding - uninit operand positions. VISITED_PHIS is the pointer set of phi - stmts being checked. */ + PHI is the phi node whose incoming (undefined) paths need to be + pruned, and UNINIT_OPNDS is the bitmap holding uninit operand + positions. VISITED_PHIS is the pointer set of phi stmts being + checked. */ static bool use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds, @@ -2140,6 +2139,158 @@ normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use) return norm_preds; } +/* Return TRUE if PREDICATE can be invalidated by any individual + predicate in WORKLIST. */ + +static bool +can_one_predicate_be_invalidated_p (pred_info predicate, + vec worklist) +{ + for (size_t i = 0; i < worklist.length (); ++i) + { + pred_info *p = worklist[i]; + + /* NOTE: This is a very simple check, and only understands an + exact opposite. So, [i == 0] is currently only invalidated + by [.NOT. i == 0] or [i != 0]. Ideally we should also + invalidate with say [i > 5] or [i == 8]. There is certainly + room for improvement here. */ + if (pred_neg_p (predicate, *p)) + return true; + } + return false; +} + +/* Return TRUE if all USE_PREDS can be invalidated by some predicate + in WORKLIST. */ + +static bool +can_chain_union_be_invalidated_p (pred_chain_union use_preds, + vec worklist) +{ + /* Remember: + PRED_CHAIN_UNION = PRED_CHAIN1 || PRED_CHAIN2 || PRED_CHAIN3 + PRED_CHAIN = PRED_INFO1 && PRED_INFO2 && PRED_INFO3, etc. + + We need to invalidate the entire PRED_CHAIN_UNION, which means, + invalidating every PRED_CHAIN in this union. But to invalidate + an individual PRED_CHAIN, all we need to invalidate is _any_ one + PRED_INFO, by boolean algebra !PRED_INFO1 || !PRED_INFO2... */ + for (size_t i = 0; i < use_preds.length (); ++i) + { + pred_chain c = use_preds[i]; + bool entire_pred_chain_invalidated = false; + for (size_t j = 0; j < c.length (); ++j) + if (can_one_predicate_be_invalidated_p (c[i], worklist)) + { + entire_pred_chain_invalidated = true; + break; + } + if (!entire_pred_chain_invalidated) + return false; + } + return true; +} + +/* Flatten out all the factors in all the pred_chain_union's in PREDS + into a WORKLIST of individual PRED_INFO's. + + N is the number of pred_chain_union's in PREDS. + + Since we are interested in the inverse of the PRED_CHAIN's, by + boolean algebra, an inverse turns those PRED_CHAINS into unions, + which means we can flatten all the factors out for easy access. */ + +static void +flatten_out_predicate_chains (pred_chain_union preds[], size_t n, + vec *worklist) +{ + for (size_t i = 0; i < n; ++i) + { + pred_chain_union u = preds[i]; + for (size_t j = 0; j < u.length (); ++j) + { + pred_chain c = u[j]; + for (size_t k = 0; k < c.length (); ++k) + worklist->safe_push (&c[k]); + } + } +} + +/* Return TRUE if executing the path to some uninitialized operands in + a PHI will invalidate the use of the PHI result later on. + + UNINIT_OPNDS is a bit vector specifying which PHI arguments have + arguments which are considered uninitialized. + + USE_PREDS is the pred_chain_union specifying the guard conditions + for the use of the PHI result. + + What we want to do is disprove each of the guards in the factors of + the USE_PREDS. So if we have: + + # USE_PREDS guards of: + # 1. i > 5 && i < 100 + # 2. j > 10 && j < 88 + + Then proving that the control dependenies for the UNINIT_OPNDS are: + + # [i <= 5] + # .OR. [i >= 100] + # + + ...we can prove that the 1st guard above in USE_PREDS is invalid. + Similarly for the 2nd guard. We return TRUE if we can disprove + both of the guards in USE_PREDS above. */ + +static bool +uninit_ops_invalidate_phi_use (gphi *phi, unsigned uninit_opnds, + pred_chain_union use_preds) +{ + /* Look for the control dependencies of all the uninitialized + operands and build predicates describing them. */ + unsigned i; + pred_chain_union uninit_preds[32]; + memset (uninit_preds, 0, sizeof (pred_chain_union) * 32); + for (i = 0; i < MIN (32, gimple_phi_num_args (phi)); i++) + { + if (!MASK_TEST_BIT (uninit_opnds, i)) + continue; + + edge e = gimple_phi_arg_edge (phi, i); + vec dep_chains[MAX_NUM_CHAINS]; + auto_vec cur_chain; + size_t num_chains = 0; + int num_calls = 0; + + /* Build the control dependency chain for `i'... */ + if (compute_control_dep_chain (find_dom (e->src), + e->src, + dep_chains, + &num_chains, + &cur_chain, + &num_calls)) + { + /* ...and convert it into a set of predicates. */ + convert_control_dep_chain_into_preds (dep_chains, num_chains, + &uninit_preds[i]); + for (size_t j = 0; j < num_chains; ++j) + dep_chains[j].release (); + simplify_preds (&uninit_preds[i], NULL, false); + uninit_preds[i] + = normalize_preds (uninit_preds[i], NULL, false); + } + } + + /* Munge all the predicates into one worklist, and see if we can + invalidate all the chains in USE_PREDs with the predicates in + WORKLIST. */ + auto_vec worklist; + flatten_out_predicate_chains (uninit_preds, i, &worklist); + bool ret = can_chain_union_be_invalidated_p (use_preds, worklist); + return ret; +} + /* Computes the predicates that guard the use and checks if the incoming paths that have empty (or possibly empty) definition can be pruned/filtered. The function returns @@ -2195,6 +2346,13 @@ is_use_properly_guarded (gimple *use_stmt, = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds, visited_phis); + /* We might be able to prove that if the control dependencies + for UNINIT_OPNDS are true, that the control dependencies for + USE_STMT can never be true. */ + if (!is_properly_guarded) + is_properly_guarded |= uninit_ops_invalidate_phi_use (phi, uninit_opnds, + preds); + if (is_properly_guarded) { destroy_predicate_vecs (&preds);