From patchwork Mon May 18 17:59:45 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1292703 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=hyVfmR9P; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 49Qmxq2rMxz9sPF for ; Tue, 19 May 2020 03:59:57 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3E943388F07C; Mon, 18 May 2020 17:59:55 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3E943388F07C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1589824795; bh=IC7PC9tUnouUgf1Oyg3luGcu0LCOimLmNQKTeBX2ssU=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=hyVfmR9P3YIa6ajpBavbmtFoy2ty6CsFnb2mtOyD/3SS4Qvtx48Fufl4iTmT3DNsu a5vbC8vncKAdafAhuMKzk6I1G2/bEe0xUW7B7y5/wbC3TtQcOAO4CNwnUPQyRfkLSS 284A+qrincqvKdpFaFrC9t6B8OXwtWus41w94TFE= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-1.mimecast.com (us-smtp-1.mimecast.com [207.211.31.81]) by sourceware.org (Postfix) with ESMTP id 015063851C03 for ; Mon, 18 May 2020 17:59:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 015063851C03 Received: from mail-wm1-f70.google.com (mail-wm1-f70.google.com [209.85.128.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-153-bRUdjnwCPaKg2fvGALNPtw-1; Mon, 18 May 2020 13:59:48 -0400 X-MC-Unique: bRUdjnwCPaKg2fvGALNPtw-1 Received: by mail-wm1-f70.google.com with SMTP id 202so113620wmb.8 for ; Mon, 18 May 2020 10:59:48 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:from:subject:message-id:date:user-agent :mime-version:content-language; bh=IC7PC9tUnouUgf1Oyg3luGcu0LCOimLmNQKTeBX2ssU=; b=BoCWgrjWK8Fc4MCJJmlh4CRtBu96RA8FoD5ryqa+vB/DNNswYMxt0G04CDrIEHEIAM 1epDJU3Cc21bVsVEgC+szAvDOenUBSAFIDvq6SK8Tjxfnaz/SDK8XW0jJy0ZSfr0vzq9 d0hGvBerExUONQGXpuM76BrgxC3SmU/2hL3qgPdA48vlC5SnsOyEx0wiPwdFAlnwgTZw DtmiPu58aLr5L1YEMVI8DPT2D5OoEfsiuwEzFh348eOzl0wOwhU4woQfb2KqY8D/Z4bs j10g6SCJmAdiD+6jbmlr6rMaBwU3ff+Fcvyzf9VtYugdZhf/1Moc8151MCzwU4fpcXR2 gw8Q== X-Gm-Message-State: AOAM533riwxSCDPl2zPjpgwfPg/l/CgJEjWK9em/fW8Sl1cWJhrMLlI5 dU/18+uh5kprdfxEdSGDUZ+UZJWrMqkTqg8A1Jtsd6aTW2edbsiAa5d98mLygkNoO7qlm2Gl82L Zm/GQ7QllwB0Y3psjtA== X-Received: by 2002:a5d:6ac1:: with SMTP id u1mr20726046wrw.319.1589824787164; Mon, 18 May 2020 10:59:47 -0700 (PDT) X-Google-Smtp-Source: ABdhPJyR9OJza/XSTIGvgseuEbGa/qC/fD0NX2BGTti78oWXqRvb8MFXqYF0Q0I0m+6kDv92r0nCcg== X-Received: by 2002:a5d:6ac1:: with SMTP id u1mr20726028wrw.319.1589824786949; Mon, 18 May 2020 10:59:46 -0700 (PDT) Received: from abulafia.quesejoda.com ([93.176.151.136]) by smtp.gmail.com with ESMTPSA id u7sm424511wmm.8.2020.05.18.10.59.45 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 18 May 2020 10:59:46 -0700 (PDT) To: Jeff Law Subject: [patch] substitute_and_fold_engine merge with evrp domwalker Message-ID: Date: Mon, 18 May 2020 19:59:45 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0 MIME-Version: 1.0 Content-Language: en-US X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: gcc-patches Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" Howdy. The main evrp domwalker seems cut and pasted from the substitute_and_fold_engine (or was it the other way around?). Albeit, there are a few things that evrp does, like set up ranges, but these can be set up with virtuals, and thus provide a general repository to do all things subst & fold, which I think was the main idea. You will notice that the resulting evrp code becomes a handful of lines calling evrp_analyze to set up ranges. We've been playing with this approach on the ranger branch, and have been able to use it to implement ranger-vrp in 24 lines, all while sharing all the evrp folding code. Granted, the ranger also needs access to vr_values::simplify_using_ranges* which I have abstracted into an independent class and will post as a follow-up. Also, for future-proofing, I have added a gimple statement argument to get_value(). This provides context where a future ranger (evrp, VRP, ranger, whatever) can provide better values depending on the statement we are processing. OK for mainline? Aldy commit f90d4a08986e98cbcb827665d91759488c714075 Author: Aldy Hernandez Date: Tue May 5 13:45:39 2020 +0200 Merge evrp uses of substitute_and_fold_engine into the engine itself. This patch merges the evrp uses of the substitute and fold engine into the engine itself, at least the parts that can be re-used by other engine uses. It also adds a context parameter to get_value() for further use. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 51b5b6c908d..19e2509ab0e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,37 @@ +2020-05-18 Aldy Hernandez + + * gimple-loop-versioning.cc (loop_versioning::name_prop::get_value): + Add stmt parameter. + * gimple-ssa-evrp.c (class evrp_folder): New. + (class evrp_dom_walker): Remove. + (execute_early_vrp): Use evrp_folder instead of evrp_dom_walker. + * tree-ssa-ccp.c (ccp_folder::get_value): Add stmt parameter. + * tree-ssa-copy.c (copy_folder::get_value): Same. + * tree-ssa-propagate.c (substitute_and_fold_engine::replace_uses_in): + Pass stmt to get_value. + (substitute_and_fold_engine::replace_phi_args_in): Same. + (substitute_and_fold_dom_walker::after_dom_children): Call + post_fold_bb. + (substitute_and_fold_dom_walker::foreach_new_stmt_in_bb): New. + (substitute_and_fold_dom_walker::propagate_into_phi_args): New. + (substitute_and_fold_dom_walker::before_dom_children): Adjust to + call virtual functions for folding, pre_folding, and post folding. + Call get_value with PHI. Tweak dump. + * tree-ssa-propagate.h (class substitute_and_fold_engine): + New argument to get_value. + New virtual function pre_fold_bb. + New virtual function post_fold_bb. + New virtual function pre_fold_stmt. + New virtual function post_new_stmt. + New function propagate_into_phi_args. + * tree-vrp.c (vrp_folder::get_value): Add stmt argument. + * vr-values.c (vr_values::extract_range_from_stmt): Adjust dump + output. + (vr_values::fold_cond): New. + (vr_values::simplify_cond_using_ranges_1): Call fold_cond. + * vr-values.h (class vr_values): Add + simplify_cond_using_ranges_when_edge_is_known. + 2020-05-18 Carl Love PR target/94833 diff --git a/gcc/gimple-loop-versioning.cc b/gcc/gimple-loop-versioning.cc index ff6c561f9e2..002b2a68b96 100644 --- a/gcc/gimple-loop-versioning.cc +++ b/gcc/gimple-loop-versioning.cc @@ -277,7 +277,7 @@ private: { public: name_prop (loop_info &li) : m_li (li) {} - tree get_value (tree) FINAL OVERRIDE; + tree get_value (tree, gimple *) FINAL OVERRIDE; private: /* Information about the versioning we've performed on the loop. */ @@ -534,7 +534,8 @@ loop_versioning::lv_dom_walker::after_dom_children (basic_block bb) Return the new value if so, otherwise return null. */ tree -loop_versioning::name_prop::get_value (tree val) +loop_versioning::name_prop::get_value (tree val, + gimple *stmt ATTRIBUTE_UNUSED) { if (TREE_CODE (val) == SSA_NAME && bitmap_bit_p (&m_li.unity_names, SSA_NAME_VERSION (val))) diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c index 599e1459f00..af780fd0519 100644 --- a/gcc/gimple-ssa-evrp.c +++ b/gcc/gimple-ssa-evrp.c @@ -43,273 +43,68 @@ along with GCC; see the file COPYING3. If not see #include "gimple-ssa-evrp-analyze.h" class evrp_folder : public substitute_and_fold_engine -{ - public: - tree get_value (tree) FINAL OVERRIDE; - evrp_folder (class vr_values *vr_values_) : vr_values (vr_values_) { } - bool simplify_stmt_using_ranges (gimple_stmt_iterator *gsi) - { return vr_values->simplify_stmt_using_ranges (gsi); } - class vr_values *vr_values; - - private: - DISABLE_COPY_AND_ASSIGN (evrp_folder); -}; - -tree -evrp_folder::get_value (tree op) -{ - return vr_values->op_with_constant_singleton_value_range (op); -} - -/* evrp_dom_walker visits the basic blocks in the dominance order and set - the Value Ranges (VR) for SSA_NAMEs in the scope. Use this VR to - discover more VRs. */ - -class evrp_dom_walker : public dom_walker { public: - evrp_dom_walker () - : dom_walker (CDI_DOMINATORS), - evrp_range_analyzer (true), - evrp_folder (evrp_range_analyzer.get_vr_values ()) - { - need_eh_cleanup = BITMAP_ALLOC (NULL); - } - ~evrp_dom_walker () - { - BITMAP_FREE (need_eh_cleanup); - } - virtual edge before_dom_children (basic_block); - virtual void after_dom_children (basic_block); - void cleanup (void); - - private: - DISABLE_COPY_AND_ASSIGN (evrp_dom_walker); - bitmap need_eh_cleanup; - auto_vec stmts_to_fixup; - auto_vec stmts_to_remove; - - class evrp_range_analyzer evrp_range_analyzer; - class evrp_folder evrp_folder; + evrp_folder () : m_range_analyzer (/*update_global_ranges=*/true), + m_vr_values (m_range_analyzer.get_vr_values ()) + { + } + + ~evrp_folder () + { + m_vr_values->cleanup_edges_and_switches (); + + if (dump_file) + { + fprintf (dump_file, "\nValue ranges after Early VRP:\n\n"); + m_range_analyzer.dump_all_value_ranges (dump_file); + fprintf (dump_file, "\n"); + } + } + + tree get_value (tree op, gimple *stmt ATTRIBUTE_UNUSED) OVERRIDE + { + return m_vr_values->op_with_constant_singleton_value_range (op); + } + + void pre_fold_bb (basic_block bb) OVERRIDE + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "evrp visiting BB%d\n", bb->index); + m_range_analyzer.enter (bb); + } + + void pre_fold_stmt (gimple *stmt) OVERRIDE + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "evrp visiting stmt "); + print_gimple_stmt (dump_file, stmt, 0); + } + m_range_analyzer.record_ranges_from_stmt (stmt, false); + } + + bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE + { + return m_vr_values->simplify_stmt_using_ranges (gsi); + } + + void post_fold_bb (basic_block bb) OVERRIDE + { + m_range_analyzer.leave (bb); + } + + void post_new_stmt (gimple *stmt) OVERRIDE + { + m_vr_values->set_defs_to_varying (stmt); + } + +private: + DISABLE_COPY_AND_ASSIGN (evrp_folder); + class evrp_range_analyzer m_range_analyzer; + class vr_values *m_vr_values; }; -edge -evrp_dom_walker::before_dom_children (basic_block bb) -{ - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Visiting BB%d\n", bb->index); - - evrp_range_analyzer.enter (bb); - - for (gphi_iterator gpi = gsi_start_phis (bb); - !gsi_end_p (gpi); gsi_next (&gpi)) - { - gphi *phi = gpi.phi (); - tree lhs = PHI_RESULT (phi); - if (virtual_operand_p (lhs)) - continue; - - const value_range_equiv *vr = evrp_range_analyzer.get_value_range (lhs); - /* Mark PHIs whose lhs we fully propagate for removal. */ - tree val; - if (vr->singleton_p (&val) && may_propagate_copy (lhs, val)) - { - stmts_to_remove.safe_push (phi); - continue; - } - } - - edge taken_edge = NULL; - - /* Visit all other stmts and discover any new VRs possible. */ - for (gimple_stmt_iterator gsi = gsi_start_bb (bb); - !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple *stmt = gsi_stmt (gsi); - tree output = NULL_TREE; - gimple *old_stmt = stmt; - bool was_noreturn = (is_gimple_call (stmt) - && gimple_call_noreturn_p (stmt)); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Visiting stmt "); - print_gimple_stmt (dump_file, stmt, 0); - } - - evrp_range_analyzer.record_ranges_from_stmt (stmt, false); - - if (gcond *cond = dyn_cast (stmt)) - { - evrp_range_analyzer.vrp_visit_cond_stmt (cond, &taken_edge); - if (taken_edge) - { - if (taken_edge->flags & EDGE_TRUE_VALUE) - gimple_cond_make_true (cond); - else if (taken_edge->flags & EDGE_FALSE_VALUE) - gimple_cond_make_false (cond); - else - gcc_unreachable (); - update_stmt (stmt); - } - } - else if (stmt_interesting_for_vrp (stmt)) - { - output = get_output_for_vrp (stmt); - if (output) - { - const value_range_equiv *vr - = evrp_range_analyzer.get_value_range (output); - - /* Mark stmts whose output we fully propagate for removal. */ - tree val; - if (vr->singleton_p (&val) - && may_propagate_copy (output, val) - && !stmt_could_throw_p (cfun, stmt) - && !gimple_has_side_effects (stmt)) - { - stmts_to_remove.safe_push (stmt); - continue; - } - } - } - - /* Try folding stmts with the VR discovered. */ - bool did_replace = evrp_folder.replace_uses_in (stmt); - gimple_stmt_iterator prev_gsi = gsi; - gsi_prev (&prev_gsi); - if (fold_stmt (&gsi, follow_single_use_edges) - || did_replace) - { - stmt = gsi_stmt (gsi); - update_stmt (stmt); - did_replace = true; - } - if (evrp_folder.simplify_stmt_using_ranges (&gsi)) - { - stmt = gsi_stmt (gsi); - update_stmt (stmt); - did_replace = true; - } - - if (did_replace) - { - /* If we wound up generating new stmts during folding - drop all their defs to VARYING. We can't easily - process them because we've already instantiated - ranges on uses on STMT that only hold after it. */ - if (gsi_end_p (prev_gsi)) - prev_gsi = gsi_start_bb (bb); - else - gsi_next (&prev_gsi); - while (gsi_stmt (prev_gsi) != gsi_stmt (gsi)) - { - evrp_range_analyzer.get_vr_values () - ->set_defs_to_varying (gsi_stmt (prev_gsi)); - gsi_next (&prev_gsi); - } - - /* If we cleaned up EH information from the statement, - remove EH edges. */ - if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) - bitmap_set_bit (need_eh_cleanup, bb->index); - - /* If we turned a not noreturn call into a noreturn one - schedule it for fixup. */ - if (!was_noreturn - && is_gimple_call (stmt) - && gimple_call_noreturn_p (stmt)) - stmts_to_fixup.safe_push (stmt); - - if (gimple_assign_single_p (stmt)) - { - tree rhs = gimple_assign_rhs1 (stmt); - if (TREE_CODE (rhs) == ADDR_EXPR) - recompute_tree_invariant_for_addr_expr (rhs); - } - } - } - - /* Visit BB successor PHI nodes and replace PHI args. */ - edge e; - edge_iterator ei; - FOR_EACH_EDGE (e, ei, bb->succs) - { - for (gphi_iterator gpi = gsi_start_phis (e->dest); - !gsi_end_p (gpi); gsi_next (&gpi)) - { - gphi *phi = gpi.phi (); - use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); - tree arg = USE_FROM_PTR (use_p); - if (TREE_CODE (arg) != SSA_NAME - || virtual_operand_p (arg)) - continue; - const value_range_equiv - *vr = evrp_range_analyzer.get_value_range (arg); - tree val; - if (vr->singleton_p (&val) && may_propagate_copy (arg, val)) - propagate_value (use_p, val); - } - } - - return taken_edge; -} - -void -evrp_dom_walker::after_dom_children (basic_block bb) -{ - evrp_range_analyzer.leave (bb); -} - -/* Perform any cleanups after the main phase of EVRP has completed. */ - -void -evrp_dom_walker::cleanup (void) -{ - if (dump_file) - { - fprintf (dump_file, "\nValue ranges after Early VRP:\n\n"); - evrp_range_analyzer.dump_all_value_ranges (dump_file); - fprintf (dump_file, "\n"); - } - - /* Remove stmts in reverse order to make debug stmt creation possible. */ - while (! stmts_to_remove.is_empty ()) - { - gimple *stmt = stmts_to_remove.pop (); - if (dump_file && dump_flags & TDF_DETAILS) - { - fprintf (dump_file, "Removing dead stmt "); - print_gimple_stmt (dump_file, stmt, 0); - fprintf (dump_file, "\n"); - } - gimple_stmt_iterator gsi = gsi_for_stmt (stmt); - if (gimple_code (stmt) == GIMPLE_PHI) - remove_phi_node (&gsi, true); - else - { - unlink_stmt_vdef (stmt); - gsi_remove (&gsi, true); - release_defs (stmt); - } - } - - if (!bitmap_empty_p (need_eh_cleanup)) - gimple_purge_all_dead_eh_edges (need_eh_cleanup); - - /* Fixup stmts that became noreturn calls. This may require splitting - blocks and thus isn't possible during the dominator walk. Do this - in reverse order so we don't inadvertedly remove a stmt we want to - fixup by visiting a dominating now noreturn call first. */ - while (!stmts_to_fixup.is_empty ()) - { - gimple *stmt = stmts_to_fixup.pop (); - fixup_noreturn_call (stmt); - } - - evrp_folder.vr_values->cleanup_edges_and_switches (); -} - /* Main entry point for the early vrp pass which is a simplified non-iterative version of vrp where basic blocks are visited in dominance order. Value ranges discovered in early vrp will also be used by ipa-vrp. */ @@ -317,19 +112,17 @@ evrp_dom_walker::cleanup (void) static unsigned int execute_early_vrp () { - /* Ideally this setup code would move into the ctor for the dominator - walk. However, this setup can change the number of blocks which + /* Ideally this setup code would move into the ctor for the folder + However, this setup can change the number of blocks which invalidates the internal arrays that are set up by the dominator - walker. */ + walker in substitute_and_fold_engine. */ loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); scev_initialize (); calculate_dominance_info (CDI_DOMINATORS); - /* Walk stmts in dominance order and propagate VRP. */ - evrp_dom_walker walker; - walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); - walker.cleanup (); + evrp_folder folder; + folder.substitute_and_fold (); scev_finalize (); loop_optimizer_finalize (); @@ -375,4 +168,3 @@ make_pass_early_vrp (gcc::context *ctxt) { return new pass_early_vrp (ctxt); } - diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 320095c49ae..8d5241be71d 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2020-05-05 Aldy Hernandez + + * gcc.dg/tree-ssa/ssa-dse-30.c: Adjust test for folding of memmove + happening later. + 2020-05-18 Uroš Bizjak PR target/95169 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-30.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-30.c index 1d1fe82fda0..9f56b392cdd 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-30.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-30.c @@ -8,9 +8,8 @@ void test_bcopy (const void *s) { char d[33]; - /* Bcopy is transformed into memmove and those calls are expanded - inline in EVRP, before DSE runs, so this test doesn't actually - verify that DSE does its job. */ + /* Bcopy is transformed into memmove before DSE runs, so this test + doesn't actually verify that DSE does its job. */ __builtin_bcopy (s, d, sizeof d); __builtin_bcopy (s, d, sizeof d); @@ -28,4 +27,17 @@ void test_bzero (void) } /* { dg-final { scan-tree-dump-times "builtin_memset" 1 "dse1" } } */ -/* { dg-final { scan-tree-dump-not "builtin_(bcopy|bzero|memcpy|memmove)" "dse1" } } */ + +/* Merging the evrp folder into substitute_and_fold_engine shuffled + the order of gimple_fold a bit, so evrp is no longer folding the + memmove inline. This folding is instead done by forwprop. Thus, I + have remmoved the |memmove in the test below as this is not done + until after dse. + + What happened was that the propagator engine only called gimple + fold if replace_uses_in() was successful. On the other hand, EVRP + called gimple fold regardless. + + If we really care about previous behavior, we could put a call to + gimple ::fold_stmt into evrp_folder::fold_stmt(). */ +/* { dg-final { scan-tree-dump-not "builtin_(bcopy|bzero|memcpy)" "dse1" } } */ diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c index be6647db894..f937f095828 100644 --- a/gcc/tree-ssa-ccp.c +++ b/gcc/tree-ssa-ccp.c @@ -943,7 +943,7 @@ do_dbg_cnt (void) class ccp_folder : public substitute_and_fold_engine { public: - tree get_value (tree) FINAL OVERRIDE; + tree get_value (tree, gimple *) FINAL OVERRIDE; bool fold_stmt (gimple_stmt_iterator *) FINAL OVERRIDE; }; @@ -952,7 +952,7 @@ class ccp_folder : public substitute_and_fold_engine of calling member functions. */ tree -ccp_folder::get_value (tree op) +ccp_folder::get_value (tree op, gimple *stmt ATTRIBUTE_UNUSED) { return get_constant_value (op); } diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c index 71e51fa03ee..9bcb708379e 100644 --- a/gcc/tree-ssa-copy.c +++ b/gcc/tree-ssa-copy.c @@ -492,13 +492,13 @@ init_copy_prop (void) class copy_folder : public substitute_and_fold_engine { public: - tree get_value (tree) FINAL OVERRIDE; + tree get_value (tree, gimple *) FINAL OVERRIDE; }; /* Callback for substitute_and_fold to get at the final copy-of values. */ tree -copy_folder::get_value (tree name) +copy_folder::get_value (tree name, gimple *stmt ATTRIBUTE_UNUSED) { tree val; if (SSA_NAME_VERSION (name) >= n_copy_of) diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c index 2fad2472775..4fda296ef9e 100644 --- a/gcc/tree-ssa-propagate.c +++ b/gcc/tree-ssa-propagate.c @@ -868,7 +868,7 @@ substitute_and_fold_engine::replace_uses_in (gimple *stmt) FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE) { tree tuse = USE_FROM_PTR (use); - tree val = get_value (tuse); + tree val = get_value (tuse, stmt); if (val == tuse || val == NULL_TREE) continue; @@ -903,19 +903,13 @@ substitute_and_fold_engine::replace_phi_args_in (gphi *phi) size_t i; bool replaced = false; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Folding PHI node: "); - print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); - } - for (i = 0; i < gimple_phi_num_args (phi); i++) { tree arg = gimple_phi_arg_def (phi, i); if (TREE_CODE (arg) == SSA_NAME) { - tree val = get_value (arg); + tree val = get_value (arg, phi); if (val && val != arg && may_propagate_copy (arg, val)) { @@ -983,7 +977,10 @@ public: } virtual edge before_dom_children (basic_block); - virtual void after_dom_children (basic_block) {} + virtual void after_dom_children (basic_block bb) + { + substitute_and_fold_engine->post_fold_bb (bb); + } bool something_changed; vec stmts_to_remove; @@ -991,11 +988,64 @@ public: bitmap need_eh_cleanup; class substitute_and_fold_engine *substitute_and_fold_engine; + +private: + void foreach_new_stmt_in_bb (gimple_stmt_iterator old_gsi, + gimple_stmt_iterator new_gsi); }; +/* Call post_new_stmt for each each new statement that has been added + to the current BB. OLD_GSI is the statement iterator before the BB + changes ocurred. NEW_GSI is the iterator which may contain new + statements. */ + +void +substitute_and_fold_dom_walker::foreach_new_stmt_in_bb + (gimple_stmt_iterator old_gsi, + gimple_stmt_iterator new_gsi) +{ + basic_block bb = gsi_bb (new_gsi); + if (gsi_end_p (old_gsi)) + old_gsi = gsi_start_bb (bb); + else + gsi_next (&old_gsi); + while (gsi_stmt (old_gsi) != gsi_stmt (new_gsi)) + { + gimple *stmt = gsi_stmt (old_gsi); + substitute_and_fold_engine->post_new_stmt (stmt); + gsi_next (&old_gsi); + } +} + +void +substitute_and_fold_engine::propagate_into_phi_args (basic_block bb) +{ + edge e; + edge_iterator ei; + /* Visit BB successor PHI nodes and replace PHI args. */ + FOR_EACH_EDGE (e, ei, bb->succs) + { + for (gphi_iterator gpi = gsi_start_phis (e->dest); + !gsi_end_p (gpi); gsi_next (&gpi)) + { + gphi *phi = gpi.phi (); + use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); + tree arg = USE_FROM_PTR (use_p); + if (TREE_CODE (arg) != SSA_NAME + || virtual_operand_p (arg)) + continue; + tree val = get_value (arg, phi); + if (val && may_propagate_copy (arg, val)) + propagate_value (use_p, val); + } + } +} + edge substitute_and_fold_dom_walker::before_dom_children (basic_block bb) { + substitute_and_fold_engine->pre_fold_bb (bb); + /* Propagate known values into PHI nodes. */ for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i); @@ -1005,13 +1055,24 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb) tree res = gimple_phi_result (phi); if (virtual_operand_p (res)) continue; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Folding PHI node: "); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); + } if (res && TREE_CODE (res) == SSA_NAME) { - tree sprime = substitute_and_fold_engine->get_value (res); + tree sprime = substitute_and_fold_engine->get_value (res, phi); if (sprime && sprime != res && may_propagate_copy (res, sprime)) { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Queued PHI for removal. Folds to: "); + print_generic_expr (dump_file, sprime); + fprintf (dump_file, "\n"); + } stmts_to_remove.safe_push (phi); continue; } @@ -1028,12 +1089,20 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb) bool did_replace; gimple *stmt = gsi_stmt (i); + substitute_and_fold_engine->pre_fold_stmt (stmt); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Folding statement: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + /* No point propagating into a stmt we have a value for we can propagate into all uses. Mark it for removal instead. */ tree lhs = gimple_get_lhs (stmt); if (lhs && TREE_CODE (lhs) == SSA_NAME) { - tree sprime = substitute_and_fold_engine->get_value (lhs); + tree sprime = substitute_and_fold_engine->get_value (lhs, stmt); if (sprime && sprime != lhs && may_propagate_copy (lhs, sprime) @@ -1043,6 +1112,12 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb) && (!is_gimple_assign (stmt) || gimple_assign_rhs_code (stmt) != ASSERT_EXPR)) { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Queued stmt for removal. Folds to: "); + print_generic_expr (dump_file, sprime); + fprintf (dump_file, "\n"); + } stmts_to_remove.safe_push (stmt); continue; } @@ -1051,12 +1126,6 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb) /* Replace the statement with its folded version and mark it folded. */ did_replace = false; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Folding statement: "); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); - } - gimple *old_stmt = stmt; bool was_noreturn = (is_gimple_call (stmt) && gimple_call_noreturn_p (stmt)); @@ -1064,6 +1133,9 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb) /* Replace real uses in the statement. */ did_replace |= substitute_and_fold_engine->replace_uses_in (stmt); + gimple_stmt_iterator prev_gsi = i; + gsi_prev (&prev_gsi); + /* If we made a replacement, fold the statement. */ if (did_replace) { @@ -1084,7 +1156,7 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb) specific information. Do this before propagating into the stmt to not disturb pass specific information. */ update_stmt_if_modified (stmt); - if (substitute_and_fold_engine->fold_stmt(&i)) + if (substitute_and_fold_engine->fold_stmt (&i)) { did_replace = true; prop_stats.num_stmts_folded++; @@ -1115,6 +1187,8 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb) /* Now cleanup. */ if (did_replace) { + foreach_new_stmt_in_bb (prev_gsi, i); + /* If we cleaned up EH information from the statement, remove EH edges. */ if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) @@ -1153,6 +1227,9 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb) fprintf (dump_file, "Not folded\n"); } } + + substitute_and_fold_engine->propagate_into_phi_args (bb); + return NULL; } diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h index 0d0f1c2da80..24de43ebc6c 100644 --- a/gcc/tree-ssa-propagate.h +++ b/gcc/tree-ssa-propagate.h @@ -104,12 +104,19 @@ class substitute_and_fold_engine : fold_all_stmts (fold_all_stmts) { } virtual ~substitute_and_fold_engine (void) { } virtual bool fold_stmt (gimple_stmt_iterator *) { return false; } - virtual tree get_value (tree) { return NULL_TREE; } + virtual tree get_value (tree, gimple *) { return NULL_TREE; } bool substitute_and_fold (basic_block = NULL); bool replace_uses_in (gimple *); bool replace_phi_args_in (gphi *); + virtual void pre_fold_bb (basic_block) { } + virtual void post_fold_bb (basic_block) { } + virtual void pre_fold_stmt (gimple *) { } + virtual void post_new_stmt (gimple *) { } + + void propagate_into_phi_args (basic_block); + /* Users like VRP can set this when they want to perform folding for every propagation. */ bool fold_all_stmts; diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 4b5df543c00..68f06b1c934 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -4932,7 +4932,7 @@ class vrp_folder : public substitute_and_fold_engine { public: vrp_folder () : substitute_and_fold_engine (/* Fold all stmts. */ true) { } - tree get_value (tree) FINAL OVERRIDE; + tree get_value (tree, gimple *stmt) FINAL OVERRIDE; bool fold_stmt (gimple_stmt_iterator *) FINAL OVERRIDE; class vr_values *vr_values; @@ -5029,7 +5029,7 @@ vrp_folder::fold_stmt (gimple_stmt_iterator *si) Implemented as a pure wrapper right now, but this will change. */ tree -vrp_folder::get_value (tree op) +vrp_folder::get_value (tree op, gimple *stmt ATTRIBUTE_UNUSED) { return op_with_constant_singleton_value_range (op); } diff --git a/gcc/vr-values.c b/gcc/vr-values.c index 2e3a0788710..e95df78870a 100644 --- a/gcc/vr-values.c +++ b/gcc/vr-values.c @@ -2799,7 +2799,7 @@ vr_values::extract_range_from_stmt (gimple *stmt, edge *taken_edge_p, if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, "\nVisiting statement:\n"); + fprintf (dump_file, "\nextract_range_from_stmt visiting:\n"); print_gimple_stmt (dump_file, stmt, 0, dump_flags); } @@ -3550,6 +3550,30 @@ range_fits_type_p (const value_range_equiv *vr, return true; } +/* If COND can be folded entirely as TRUE or FALSE, rewrite the + conditional as such, and return TRUE. */ + +bool +vr_values::fold_cond (gcond *cond) +{ + /* ?? vrp_folder::fold_predicate_in() is a superset of this. At + some point we should merge all variants of this code. */ + edge taken_edge; + vrp_visit_cond_stmt (cond, &taken_edge); + if (taken_edge) + { + if (taken_edge->flags & EDGE_TRUE_VALUE) + gimple_cond_make_true (cond); + else if (taken_edge->flags & EDGE_FALSE_VALUE) + gimple_cond_make_false (cond); + else + gcc_unreachable (); + update_stmt (cond); + return true; + } + return false; +} + /* Simplify a conditional using a relational operator to an equality test if the range information indicates only one value can satisfy the original conditional. */ @@ -3561,6 +3585,9 @@ vr_values::simplify_cond_using_ranges_1 (gcond *stmt) tree op1 = gimple_cond_rhs (stmt); enum tree_code cond_code = gimple_cond_code (stmt); + if (fold_cond (stmt)) + return true; + if (cond_code != NE_EXPR && cond_code != EQ_EXPR && TREE_CODE (op0) == SSA_NAME diff --git a/gcc/vr-values.h b/gcc/vr-values.h index b4ab4e6f5b8..42ccebcc330 100644 --- a/gcc/vr-values.h +++ b/gcc/vr-values.h @@ -110,6 +110,7 @@ class vr_values bool simplify_bit_ops_using_ranges (gimple_stmt_iterator *, gimple *); bool simplify_min_or_max_using_ranges (gimple_stmt_iterator *, gimple *); bool simplify_cond_using_ranges_1 (gcond *); + bool fold_cond (gcond *); bool simplify_switch_using_ranges (gswitch *); bool simplify_float_conversion_using_ranges (gimple_stmt_iterator *, gimple *);