From patchwork Tue Oct 31 12:08:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 160098 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b90f:0:b0:403:3b70:6f57 with SMTP id t15csp187696vqg; Tue, 31 Oct 2023 05:09:23 -0700 (PDT) X-Google-Smtp-Source: AGHT+IE9LAVyUZTF2KYjr/dfEUrkrG8eNDKKGKgy4bw8RHh2UxRm6fYoDs6DkkeXJYJlYjLDLEGP X-Received: by 2002:a67:e1c5:0:b0:45a:de9b:8d44 with SMTP id p5-20020a67e1c5000000b0045ade9b8d44mr10860524vsl.3.1698754163302; Tue, 31 Oct 2023 05:09:23 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1698754163; cv=pass; d=google.com; s=arc-20160816; b=tj4GOrjyOP2e7SXuEDNhrNBOR12eGNohs+MpLItdOyzaYdy5bAxWo/toMnV+zL1/rR iTQ+jVS5PsnpH2WODuIB7GRmg8/SX9huUchWojJWfH3RYdjTfi8ToAKSvE8TeUaIjs0Y UyWBd+LsGkB3v9ouYp8/F5vOqk8TXJRcC1yL9+xQc/nS5jOaJRtPZskse3SKSI4PSIUZ FPHpdnXlgzjjW78TB9jGQhk69dCY3KaW3rQpCPj/lm+DC7XDWVieY5kKCr9eDc7edn6S HbNEut/rSHbujHjL987ujC6hl23JAMPO2bfWw1Wq/B0jQuxdoBSi7tJrwC5nfbOo+W0y MAoA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:message-id:mime-version:subject :to:from:date:dkim-signature:dkim-signature:arc-filter:dmarc-filter :delivered-to; bh=QcUhmMihUjUEY//d6UMBat7+Ohyq1//6ekUjI0bpSEI=; fh=hPrbWPhweUx4V0GV9uXJqbyAzg2ABmTz7kczrAQqMmM=; b=v0S35usKvkX5LUI/GMuFIouqXlZfv2fmZEfEeQlnFMHSGal6nw+JZPGeReEQeyRcXt VBPa6aVJf/oZjYDk05HLlAL+LjrK3/MzPYhp6r1rSDY4O75tSx+VBCyp+RmBNsKnXWhX aT4gwqyChbNfV7sWyNiG3tRWo6nW7iBXs47hTQkOU6aqbwhC1+DAAeMj3nO5glirjb7n sqrk+rCiVnGYW6RiIEbnBvRsUwQQwiJziizpZAezorA/wqNXirSDusus+CjpryQfZKM5 RDZPfm/fP6QY9K2LdvnITfu1RjX8Ue+wX8dkkTIfGMZZlPYhKPNJ9ZJL8O3vEBa6/SNg 9mXQ== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@suse.de header.s=susede2_rsa header.b=QoZGMH9i; dkim=neutral (no key) header.i=@suse.de header.s=susede2_ed25519; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=suse.de Received: from server2.sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id g3-20020a67cf83000000b00452f0775437si78185vsm.240.2023.10.31.05.09.23 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 31 Oct 2023 05:09:23 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@suse.de header.s=susede2_rsa header.b=QoZGMH9i; dkim=neutral (no key) header.i=@suse.de header.s=susede2_ed25519; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=suse.de Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 10F143858439 for ; Tue, 31 Oct 2023 12:09:23 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 802CE3858CDA for ; Tue, 31 Oct 2023 12:08:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 802CE3858CDA Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 802CE3858CDA Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.220.28 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698754141; cv=none; b=dx6jh5/YJOm1BhY/gLNRmWdbWkIjRaRfZZuu8dLaz4Qjtz4Xn7Hs3yiFt7q6ziGnQD/0cn3mXtRb1GKVkLS1TwuKeZCvg5szihi4pCnFdjH4t7tMWzEcWNIpfJ6PucVJb5Xx5nrxjzOb9OoH+isMtY02kpPuZ4OYlIJhnrAx9f0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698754141; c=relaxed/simple; bh=9Z6lywzSOOaMbnF1+iQ/APRqmzK7aX8/Av20UdG5C+U=; h=DKIM-Signature:DKIM-Signature:Date:From:To:Subject:MIME-Version: Message-Id; b=ltpdUCDPe2+D+s1zgCpp7YoKgq00pJhwSayxUTnOplRzQWEMO3o4G8kDQFnkhSWDxJfgl4mwkYkeIFhcshgPvE1czgcTEGe/iBiwa4d1jkgmThqCo3b7VJI9DuzoK4KwC8DRBnI1twOvbOiJPfKXXRZRO7cSrkkSOshx+U9OMsA= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 6630421AE8 for ; Tue, 31 Oct 2023 12:08:58 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1698754138; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=QcUhmMihUjUEY//d6UMBat7+Ohyq1//6ekUjI0bpSEI=; b=QoZGMH9iTKMApGotnZQBsR8pcMBrMZZvzJDoL8gVzi0NxHvgNm7/MEAWWl6ZsVJ/q9eOmb Yxq65ad9yOicCx38/sNCJoDHISfi90yZIFb8OkGSIag6Av6yvhhSF3Y1Z9EQdnEZ3xTPlA ib+YJ0R2n1W0c8xuGWy2SDfnXfXpVxM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1698754138; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=QcUhmMihUjUEY//d6UMBat7+Ohyq1//6ekUjI0bpSEI=; b=zk2lNE5ayN4EYowSOpBtvK7xpMRDCqy7LW35Zn1iNDZCWSnuKAvGQAtsl2EcoDazu7URHq VwQTVu/CnOl8WlBQ== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 4E65D138EF for ; Tue, 31 Oct 2023 12:08:58 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id dRfmEVruQGXCQgAAMHmgww (envelope-from ) for ; Tue, 31 Oct 2023 12:08:58 +0000 Date: Tue, 31 Oct 2023 13:08:57 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/112305 - SCEV cprop and conditional undefined overflow MIME-Version: 1.0 Message-Id: <20231031120858.4E65D138EF@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1781272845498258798 X-GMAIL-MSGID: 1781272845498258798 The following adjusts final value replacement to also rewrite the replacement to defined overflow behavior if there's conditionally evaluated stmts (with possibly undefined overflow), not only when we "folded casts". The patch hooks into expression_expensive for this. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. PR tree-optimization/112305 * tree-scalar-evolution.h (expression_expensive): Adjust. * tree-scalar-evolution.cc (expression_expensive): Record when we see a COND_EXPR. (final_value_replacement_loop): When the replacement contains a COND_EXPR, rewrite it to defined overflow. * tree-sssa-loop-ivopts.cc (may_eliminate_iv): Adjust. * gcc.dg/torture/pr112305.c: New testcase. --- gcc/testsuite/gcc.dg/torture/pr112305.c | 18 ++++++++ gcc/tree-scalar-evolution.cc | 59 +++++++++++++++---------- gcc/tree-scalar-evolution.h | 2 +- gcc/tree-ssa-loop-ivopts.cc | 3 +- 4 files changed, 56 insertions(+), 26 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/pr112305.c diff --git a/gcc/testsuite/gcc.dg/torture/pr112305.c b/gcc/testsuite/gcc.dg/torture/pr112305.c new file mode 100644 index 00000000000..9d363aaac9d --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr112305.c @@ -0,0 +1,18 @@ +/* { dg-do run } */ +/* { dg-require-effective-target int32plus } */ + +int a; +void b() +{ + long c = 3; + unsigned int d = 50253292; + int e = 2147483648; + for (; a < 5; a++) + do { + e += 4; + d -= c; + } while (e < 20); + if (d != -1560359471u) + __builtin_abort (); +} +int main() { b(); } diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc index 95a15fe0988..a6524de7b92 100644 --- a/gcc/tree-scalar-evolution.cc +++ b/gcc/tree-scalar-evolution.cc @@ -3353,11 +3353,13 @@ scev_finalize (void) } /* Returns true if the expression EXPR is considered to be too expensive - for scev_const_prop. */ + for scev_const_prop. Sets *COND_OVERFLOW_P to true when the + expression might contain a sub-expression that is subject to undefined + overflow behavior and conditionally evaluated. */ static bool -expression_expensive_p (tree expr, hash_map &cache, - uint64_t &cost) +expression_expensive_p (tree expr, bool *cond_overflow_p, + hash_map &cache, uint64_t &cost) { enum tree_code code; @@ -3444,7 +3446,7 @@ bitcount_call: } FOR_EACH_CALL_EXPR_ARG (arg, iter, expr) - if (expression_expensive_p (arg, cache, op_cost)) + if (expression_expensive_p (arg, cond_overflow_p, cache, op_cost)) return true; *cache.get (expr) += op_cost; cost += op_cost + 1; @@ -3453,7 +3455,8 @@ bitcount_call: if (code == COND_EXPR) { - if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost) + if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p, + cache, op_cost) || (EXPR_P (TREE_OPERAND (expr, 1)) && EXPR_P (TREE_OPERAND (expr, 2))) /* If either branch has side effects or could trap. */ @@ -3461,11 +3464,13 @@ bitcount_call: || generic_expr_could_trap_p (TREE_OPERAND (expr, 1)) || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0)) || generic_expr_could_trap_p (TREE_OPERAND (expr, 0)) - || expression_expensive_p (TREE_OPERAND (expr, 1), + || expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p, cache, op_cost) - || expression_expensive_p (TREE_OPERAND (expr, 2), + || expression_expensive_p (TREE_OPERAND (expr, 2), cond_overflow_p, cache, op_cost)) return true; + /* Conservatively assume there's overflow for now. */ + *cond_overflow_p = true; *cache.get (expr) += op_cost; cost += op_cost + 1; return false; @@ -3475,12 +3480,14 @@ bitcount_call: { case tcc_binary: case tcc_comparison: - if (expression_expensive_p (TREE_OPERAND (expr, 1), cache, op_cost)) + if (expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p, + cache, op_cost)) return true; /* Fallthru. */ case tcc_unary: - if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost)) + if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p, + cache, op_cost)) return true; *cache.get (expr) += op_cost; cost += op_cost + 1; @@ -3492,11 +3499,12 @@ bitcount_call: } bool -expression_expensive_p (tree expr) +expression_expensive_p (tree expr, bool *cond_overflow_p) { hash_map cache; uint64_t expanded_size = 0; - return (expression_expensive_p (expr, cache, expanded_size) + *cond_overflow_p = false; + return (expression_expensive_p (expr, cond_overflow_p, cache, expanded_size) || expanded_size > cache.elements ()); } @@ -3796,6 +3804,7 @@ final_value_replacement_loop (class loop *loop) niter_num))) def = bit_def; + bool cond_overflow_p; if (!tree_does_not_contain_chrecs (def) || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) /* Moving the computation from the loop may prolong life range @@ -3809,7 +3818,7 @@ final_value_replacement_loop (class loop *loop) he probably knows that n is not large, and does not want it to be turned into n %= 45. */ - || expression_expensive_p (def)) + || expression_expensive_p (def, &cond_overflow_p)) { if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -3834,15 +3843,23 @@ final_value_replacement_loop (class loop *loop) def = unshare_expr (def); remove_phi_node (&psi, false); + /* Create the replacement statements. */ + gimple_seq stmts; + def = force_gimple_operand (def, &stmts, false, NULL_TREE); + gassign *ass = gimple_build_assign (rslt, def); + gimple_set_location (ass, + gimple_phi_arg_location (phi, exit->dest_idx)); + gimple_seq_add_stmt (&stmts, ass); + /* If def's type has undefined overflow and there were folded casts, rewrite all stmts added for def into arithmetics with defined overflow behavior. */ - if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def)) - && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def))) + if ((folded_casts + && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def)) + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def))) + || cond_overflow_p) { - gimple_seq stmts; gimple_stmt_iterator gsi2; - def = force_gimple_operand (def, &stmts, true, NULL_TREE); gsi2 = gsi_start (stmts); while (!gsi_end_p (gsi2)) { @@ -3861,17 +3878,11 @@ final_value_replacement_loop (class loop *loop) } } else - def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE, - true, GSI_SAME_STMT); - - gassign *ass = gimple_build_assign (rslt, def); - gimple_set_location (ass, - gimple_phi_arg_location (phi, exit->dest_idx)); - gsi_insert_before (&gsi, ass, GSI_SAME_STMT); + gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); if (dump_file) { fprintf (dump_file, "\n final stmt:\n "); - print_gimple_stmt (dump_file, ass, 0); + print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (rslt), 0); fprintf (dump_file, "\n"); } } diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index f35ca1bded0..a64ed78fe63 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -36,7 +36,7 @@ extern tree resolve_mixers (class loop *, tree, bool *); extern void gather_stats_on_scev_database (void); extern bool final_value_replacement_loop (class loop *); extern unsigned int scev_const_prop (void); -extern bool expression_expensive_p (tree); +extern bool expression_expensive_p (tree, bool *); extern bool simple_iv_with_niters (class loop *, class loop *, tree, struct affine_iv *, tree *, bool); extern bool simple_iv (class loop *, class loop *, tree, struct affine_iv *, diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc index 98e5b3024db..c3336603778 100644 --- a/gcc/tree-ssa-loop-ivopts.cc +++ b/gcc/tree-ssa-loop-ivopts.cc @@ -5527,7 +5527,8 @@ may_eliminate_iv (struct ivopts_data *data, /* It is unlikely that computing the number of iterations using division would be more profitable than keeping the original induction variable. */ - if (expression_expensive_p (*bound)) + bool cond_overflow_p; + if (expression_expensive_p (*bound, &cond_overflow_p)) return false; /* Sometimes, it is possible to handle the situation that the number of