From patchwork Wed Feb 6 13:45:10 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Matz X-Patchwork-Id: 218614 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]) by ozlabs.org (Postfix) with SMTP id 953EB2C02BD for ; Thu, 7 Feb 2013 00:45:41 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1360763142; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Date: From:To:Subject:Message-ID:User-Agent:MIME-Version:Content-Type: Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:Sender:Delivered-To; bh=BKAi30+i+lHWc51kcewH 1sJQ4Io=; b=iz4qbNoigNPGPKWeVoNj+wF4D9lu03kzm3s+UAwspKNcRPhoS3EO /Z2hj2MglO8EZ1GelbmsJLgpGAVKj/xLHbKIcKWi2LLHM1IQ/Q/UXN/jsmDsEw9e hF9ZadvVi7Bh0VFORuaK3Evuyi1uIc9i//46uPAEuBkWtHuNzCLB9cs= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Date:From:To:Subject:Message-ID:User-Agent:MIME-Version:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=GFjAtWKY7VGmwhLtokVyGQCuNEqQXsSxKxTFddl7jYTWzndaGYn3FRSr1GvrFe dh2hEK3xuILSdpr6r4YJebaCiUYmTbJcmguCbCZEZQqOXzlPJMs4q/xNZvVNT64m x65KCnQVXA+ttP2s0ssYAQWKVRqngOhwm5wyIeu75DhZQ=; Received: (qmail 10521 invoked by alias); 6 Feb 2013 13:45:22 -0000 Received: (qmail 10438 invoked by uid 22791); 6 Feb 2013 13:45:20 -0000 X-SWARE-Spam-Status: No, hits=-5.2 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, TW_FN, TW_TM X-Spam-Check-By: sourceware.org Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 06 Feb 2013 13:45:12 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mx2.suse.de (Postfix) with ESMTP id 177B1A51B7 for ; Wed, 6 Feb 2013 14:45:11 +0100 (CET) Date: Wed, 6 Feb 2013 14:45:10 +0100 (CET) From: Michael Matz To: gcc-patches@gcc.gnu.org Subject: Fix PR52448 (cselim with calls) Message-ID: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 X-IsSubscribed: yes 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 Hi, marking of non-trapping accesses currently has an issue when there's a call between the dominated and the dominating access (that makes the former non-trapping), namely when that call frees the accessed memory (or makes it unavailable via other means). Instead of a full-blown algorithm iterating until a fixed point to exactly determine the killed set of accesses I simply clear the whole hash table of seen accesses whenever I see a call, which requires being conservative on backedges (or generally when there are unvisited predecessors, but the current domwalker ensures that domchilds are visited in topological order). Quick clearing is done by using a phase counter. This still retains the important transformation in hmmer, but fixes the bug. Regstrapped on x86_64-linux, okay for trunk? Ciao, Michael. Index: tree-ssa-phiopt.c =================================================================== --- tree-ssa-phiopt.c (revision 195753) +++ tree-ssa-phiopt.c (working copy) @@ -1233,6 +1233,7 @@ abs_replacement (basic_block cond_bb, ba struct name_to_bb { unsigned int ssa_name_ver; + unsigned int phase; bool store; HOST_WIDE_INT offset, size; basic_block bb; @@ -1241,6 +1242,10 @@ struct name_to_bb /* The hash table for remembering what we've seen. */ static htab_t seen_ssa_names; +/* Used for quick clearing of the hash-table when we see calls. + Hash entries with phase < nt_call_phase are invalid. */ +static unsigned int nt_call_phase; + /* The set of MEM_REFs which can't trap. */ static struct pointer_set_t *nontrap_set; @@ -1291,6 +1296,7 @@ add_or_mark_expr (basic_block bb, tree e /* Try to find the last seen MEM_REF through the same SSA_NAME, which can trap. */ map.ssa_name_ver = SSA_NAME_VERSION (name); + map.phase = 0; map.bb = 0; map.store = store; map.offset = tree_low_cst (TREE_OPERAND (exp, 1), 0); @@ -1298,13 +1304,13 @@ add_or_mark_expr (basic_block bb, tree e slot = htab_find_slot (seen_ssa_names, &map, INSERT); n2bb = (struct name_to_bb *) *slot; - if (n2bb) + if (n2bb && n2bb->phase >= nt_call_phase) found_bb = n2bb->bb; /* If we've found a trapping MEM_REF, _and_ it dominates EXP (it's in a basic block on the path from us to the dominator root) then we can't trap. */ - if (found_bb && found_bb->aux == (void *)1) + if (found_bb && (((size_t)found_bb->aux) & 1) == 1) { pointer_set_insert (nontrap, exp); } @@ -1313,12 +1319,14 @@ add_or_mark_expr (basic_block bb, tree e /* EXP might trap, so insert it into the hash table. */ if (n2bb) { + n2bb->phase = nt_call_phase; n2bb->bb = bb; } else { n2bb = XNEW (struct name_to_bb); n2bb->ssa_name_ver = SSA_NAME_VERSION (name); + n2bb->phase = nt_call_phase; n2bb->bb = bb; n2bb->store = store; n2bb->offset = map.offset; @@ -1329,20 +1337,53 @@ add_or_mark_expr (basic_block bb, tree e } } +/* Return true when CALL is a call stmt that definitely doesn't + free any memory or makes it unavailable otherwise. */ +static bool +nonfreeing_call_p (gimple call) +{ + tree fndecl = gimple_call_fndecl (call); + + if (!fndecl || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL) + return false; + + switch (DECL_FUNCTION_CODE (fndecl)) + { + case BUILT_IN_FREE: + case BUILT_IN_STACK_RESTORE: + return false; + default: + return true; + } +} + /* Called by walk_dominator_tree, when entering the block BB. */ static void nt_init_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb) { + edge e; + edge_iterator ei; gimple_stmt_iterator gsi; - /* Mark this BB as being on the path to dominator root. */ - bb->aux = (void*)1; + + /* If we haven't seen all our predecessors, clear the hash-table. */ + FOR_EACH_EDGE (e, ei, bb->preds) + if ((((size_t)e->src->aux) & 2) == 0) + { + nt_call_phase++; + break; + } + + /* Mark this BB as being on the path to dominator root and as visited. */ + bb->aux = (void*)(1 | 2); /* And walk the statements in order. */ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gimple stmt = gsi_stmt (gsi); - if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt)) + if (is_gimple_call (stmt) && !nonfreeing_call_p (stmt)) + nt_call_phase++; + else if (gimple_assign_single_p (stmt) && !gimple_has_volatile_ops (stmt)) { add_or_mark_expr (bb, gimple_assign_lhs (stmt), nontrap_set, true); add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), nontrap_set, false); @@ -1355,7 +1396,7 @@ static void nt_fini_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb) { /* This BB isn't on the path to dominator root anymore. */ - bb->aux = NULL; + bb->aux = (void*)2; } /* This is the entry point of gathering non trapping memory accesses. @@ -1368,6 +1409,7 @@ get_non_trapping (void) struct pointer_set_t *nontrap; struct dom_walk_data walk_data; + nt_call_phase = 0; nontrap = pointer_set_create (); seen_ssa_names = htab_create (128, name_to_bb_hash, name_to_bb_eq, free); @@ -1389,6 +1431,7 @@ get_non_trapping (void) fini_walk_dominator_tree (&walk_data); htab_delete (seen_ssa_names); + clear_aux_for_blocks (); return nontrap; } Index: testsuite/gcc.dg/pr52448.c =================================================================== --- testsuite/gcc.dg/pr52448.c (revision 0) +++ testsuite/gcc.dg/pr52448.c (working copy) @@ -0,0 +1,30 @@ +/* PR tree-optimization/52448 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -ftree-cselim -fdump-tree-cselim-details" } */ + +extern void perhaps_free_something (void); + +void f1 (int *p, int a, int b, int cond, int cond2) +{ + *p = a; + if (cond) + perhaps_free_something (); + if (cond2) + *p = b; +} + +void f2 (int *p, int a, int b, int *cond, int *cond2) +{ + int i; + *p = a; + for (i = 0; cond[i]; i++) + { + if (cond2[i]) + *p = b; + perhaps_free_something (); + } +} + +/* None of the above conditional stores might be made unconditional. */ +/* { dg-final { scan-tree-dump-not "cstore" "cselim" } } */ +/* { dg-final { cleanup-tree-dump "cselim" } } */