From patchwork Mon Sep 1 14:01:04 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 384856 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 8B7C01401DB for ; Tue, 2 Sep 2014 00:05:05 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=AFbd0dE9YScG8fYFKFEKrHxLY+9963b6C6BFnotnaUCmsgVQ+kpYU lkoWRlQPiThUpwxtDW35WJQLvHUVUy79QS4efS0LbJ5yK9BRJIZj8KZvTbTjhlg4 2jIMIzpk1f6GcghDalYqZ6xJi4LuBWZDNu2ErM0CUXiGDUzl2szBpM= 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:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=mGuuNKrU0Ju6PyoIThS/uVz3uCA=; b=m+6Bd2MOR+55YUFeTzWn nNSDVUj9mDAlyvRLAj5GW003w2pg07JjljluSNPsnjigH7yNJJvPBtd1JGpsK7N9 hRri4iZjy0lxtDyHYk9ShnbhEYOXURU5TkTkGpkzlqkxxRISt5CY+bdY91u45lw4 qjTdgtAgg1mZ7owclPWuL7c= Received: (qmail 20567 invoked by alias); 1 Sep 2014 14:04:39 -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 20538 invoked by uid 89); 1 Sep 2014 14:04:36 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-4.1 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx2.suse.de Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Mon, 01 Sep 2014 14:04:32 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 17560AC06 for ; Mon, 1 Sep 2014 14:04:29 +0000 (UTC) Date: Mon, 1 Sep 2014 16:01:04 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Avoid inserting dead code in PRE, do less work Message-ID: User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 The following patch tries to work towards fixing PR62291 by moving NEW_SETS/AVAIL_OUT adding strictly to insert_into_preds_of_block and the value / expression we wanted to insert. If doing that for other unrelated expressions this may cause fake partial redundancies to be detected and dead code will be inserted such as for gcc.dg/tree-ssa/ssa-pre-28.c which is now fixed. The idea is that we could now "simulate" insertion and its recursion without actually performing the insertions (which requires AVAIL_OUT) and instead postpone that to elimination time. Well. Idea... Bootstrap and regtest running on x86_64-unknown-linux-gnu. Richard. 2014-09-01 Richard Biener * tree-ssa-pre.c (find_or_generate_expression): Expand comment. (create_expression_by_pieces): Do not add to NEW_SETS or AVAIL_OUT here. (insert_into_preds_of_block): Instead do it here and only for the partial redundant value we inserted. Index: gcc/tree-ssa-pre.c =================================================================== --- gcc/tree-ssa-pre.c (revision 214795) +++ gcc/tree-ssa-pre.c (working copy) @@ -2797,9 +2797,11 @@ find_or_generate_expression (basic_block return NULL_TREE; } - /* It must be a complex expression, so generate it recursively. Note - that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c - where the insert algorithm fails to insert a required expression. */ + /* It must be a complex expression, so generate it recursively. + Note that this is only necessary to handle cases like + gcc.dg/tree-ssa/ssa-pre-28.c where the insert algorithm fails to + insert a required expression because the dependent expression + isn't partially redundant. */ bitmap exprset = value_expressions[lookfor]; bitmap_iterator bi; unsigned int i; @@ -2846,7 +2848,6 @@ create_expression_by_pieces (basic_block unsigned int value_id; gimple_stmt_iterator gsi; tree exprtype = type ? type : get_expr_type (expr); - pre_expr nameexpr; gimple newstmt; switch (expr->kind) @@ -2941,17 +2942,12 @@ create_expression_by_pieces (basic_block { gimple stmt = gsi_stmt (gsi); tree forcedname = gimple_get_lhs (stmt); - pre_expr nameexpr; if (TREE_CODE (forcedname) == SSA_NAME) { bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname)); VN_INFO_GET (forcedname)->valnum = forcedname; VN_INFO (forcedname)->value_id = get_next_value_id (); - nameexpr = get_or_alloc_expr_for_name (forcedname); - add_to_value (VN_INFO (forcedname)->value_id, nameexpr); - bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); - bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); } } gimple_seq_add_seq (stmts, forced_stmts); @@ -2979,12 +2975,6 @@ create_expression_by_pieces (basic_block VN_INFO (name)->valnum = sccvn_valnum_from_value_id (value_id); if (VN_INFO (name)->valnum == NULL_TREE) VN_INFO (name)->valnum = name; - gcc_assert (VN_INFO (name)->valnum != NULL_TREE); - nameexpr = get_or_alloc_expr_for_name (name); - add_to_value (value_id, nameexpr); - if (NEW_SETS (block)) - bitmap_value_replace_in_set (NEW_SETS (block), nameexpr); - bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr); pre_stats.insertions++; if (dump_file && (dump_flags & TDF_DETAILS)) @@ -3061,7 +3051,11 @@ insert_into_preds_of_block (basic_block nophi = true; continue; } - avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr); + pre_expr nameexpr = get_or_alloc_expr_for_name (builtexpr); + avail[pred->dest_idx] = nameexpr; + add_to_value (get_expr_value_id (eprime), nameexpr); + bitmap_value_replace_in_set (NEW_SETS (bprime), nameexpr); + bitmap_value_replace_in_set (AVAIL_OUT (bprime), nameexpr); insertions = true; } else if (eprime->kind == CONSTANT) Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-28.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-28.c (revision 214795) +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-28.c (working copy) @@ -15,7 +15,13 @@ int foo (int i, int b, int result) } /* We should insert i + 1 into the if (b) path as well as the simplified - i + 1 & -2 expression. And do replacement with two PHI temps. */ + i + 1 & -2 expression. And do replacement of the partially + redundant result & mask with one PHI temps. In particular we + should avoid inserting i + 1 into the if (!b) path during + insert iteration 2. */ -/* { dg-final { scan-tree-dump-times "with prephitmp" 2 "pre" } } */ +/* { dg-final { scan-tree-dump-times "Inserted pretmp" 2 "pre" } } */ +/* { dg-final { scan-tree-dump-times "Created phi prephitmp" 1 "pre" } } */ +/* { dg-final { scan-tree-dump-times "with prephitmp" 1 "pre" } } */ +/* { dg-final { scan-tree-dump-times "Starting insert iteration" 2 "pre" } } */ /* { dg-final { cleanup-tree-dump "pre" } } */